X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/f89671e0bd7450461d70d5ced6079123e73c2a63..16c3ee2d2a61e399f24130eb97c27b830023a9f0:/src/xbt/dict.cpp diff --git a/src/xbt/dict.cpp b/src/xbt/dict.cpp index 256c277615..f1e73d31dc 100644 --- a/src/xbt/dict.cpp +++ b/src/xbt/dict.cpp @@ -1,6 +1,6 @@ /* dict - a generic dictionary, variation over hash table */ -/* Copyright (c) 2004-2019. The SimGrid Team. All rights reserved. */ +/* Copyright (c) 2004-2023. The SimGrid Team. All rights reserved. */ /* This program is free software; you can redistribute it and/or modify it * under the terms of the license (GNU LGPL) which comes with this package. */ @@ -8,20 +8,40 @@ #include "xbt/dict.h" #include "dict_private.h" #include "simgrid/Exception.hpp" -#include "src/xbt_modinter.h" #include "xbt/ex.h" #include "xbt/log.h" #include "xbt/mallocator.h" #include "xbt/str.h" #include "xbt/string.hpp" +#include #include #include +#include XBT_LOG_NEW_DEFAULT_SUBCATEGORY(xbt_dict, xbt, "Dictionaries provide the same functionalities as hash tables"); constexpr int MAX_FILL_PERCENT = 80; +/** Handle the dict mallocators init/fini cycle. */ +static void xbt_dict_postexit() +{ + if (dict_elm_mallocator != nullptr) { + xbt_mallocator_free(dict_elm_mallocator); + dict_elm_mallocator = nullptr; + } +} +static void xbt_dict_preinit() +{ + static std::mutex init_mutex; + const std::scoped_lock lock(init_mutex); + if (dict_elm_mallocator == nullptr) { + dict_elm_mallocator = + xbt_mallocator_new(256, dict_elm_mallocator_new_f, dict_elm_mallocator_free_f, dict_elm_mallocator_reset_f); + atexit(xbt_dict_postexit); + } +} + /** * @brief Constructor * @param free_ctn function to call with (@a data as argument) when @a data is removed from the dictionary @@ -33,8 +53,7 @@ constexpr int MAX_FILL_PERCENT = 80; */ xbt_dict_t xbt_dict_new_homogeneous(void_f_pvoid_t free_ctn) { - if (dict_elm_mallocator == nullptr) - xbt_dict_preinit(); + xbt_dict_preinit(); // Make sure that the module is intialized xbt_dict_t dict; @@ -79,7 +98,7 @@ void xbt_dict_free(xbt_dict_t * dict) } /** Returns the amount of elements in the dict */ -unsigned int xbt_dict_size(xbt_dict_t dict) +unsigned int xbt_dict_size(const_xbt_dict_t dict) { return (dict != nullptr ? static_cast(dict->count) : static_cast(0)); } @@ -90,21 +109,22 @@ static void xbt_dict_rehash(xbt_dict_t dict) const unsigned oldsize = dict->table_size + 1; unsigned newsize = oldsize * 2; - xbt_dictelm_t *currcell = (xbt_dictelm_t *) xbt_realloc((char *) dict->table, newsize * sizeof(xbt_dictelm_t)); - memset(&currcell[oldsize], 0, oldsize * sizeof(xbt_dictelm_t)); /* zero second half */ + auto* newtable = static_cast(xbt_realloc(dict->table, newsize * sizeof(xbt_dictelm_t))); + std::fill(newtable + oldsize, newtable + newsize, nullptr); /* zero second half */ newsize--; dict->table_size = newsize; - dict->table = currcell; + dict->table = newtable; XBT_DEBUG("REHASH (%u->%u)", oldsize, newsize); - for (unsigned i = 0; i < oldsize; i++, currcell++) { + for (unsigned i = 0; i < oldsize; i++) { + xbt_dictelm_t* currcell = &newtable[i]; if (*currcell == nullptr) /* empty cell */ continue; xbt_dictelm_t *twincell = currcell + oldsize; xbt_dictelm_t *pprev = currcell; xbt_dictelm_t bucklet = *currcell; - for (; bucklet != nullptr; bucklet = *pprev) { + while (bucklet != nullptr) { /* Since we use "& size" instead of "%size" and since the size was doubled, each bucklet of this cell must either: - stay in cell i (ie, currcell) - go to the cell i+oldsize (ie, twincell) */ @@ -117,6 +137,7 @@ static void xbt_dict_rehash(xbt_dict_t dict) } else { pprev = &bucklet->next; } + bucklet = *pprev; } if (*currcell == nullptr) /* everything moved */ @@ -130,13 +151,11 @@ static void xbt_dict_rehash(xbt_dict_t dict) * @param key the key to set the new data * @param key_len the size of the @a key * @param data the data to add in the dict - * @param free_ctn unused parameter (kept for compatibility) * * Set the @a data in the structure under the @a key, which can be any kind of data, as long as its length is provided * in @a key_len. */ -void xbt_dict_set_ext(xbt_dict_t dict, const char* key, int key_len, void* data, - XBT_ATTRIB_UNUSED void_f_pvoid_t free_ctn) +void xbt_dict_set_ext(xbt_dict_t dict, const char* key, int key_len, void* data) { unsigned int hash_code = xbt_str_hash_ext(key, key_len); @@ -178,13 +197,12 @@ void xbt_dict_set_ext(xbt_dict_t dict, const char* key, int key_len, void* data, * @param dict the dict * @param key the key to set the new data * @param data the data to add in the dict - * @param free_ctn unused parameter (kept for compatibility) * * set the @a data in the structure under the @a key, which is a null terminated string. */ -void xbt_dict_set(xbt_dict_t dict, const char *key, void *data, void_f_pvoid_t free_ctn) +void xbt_dict_set(xbt_dict_t dict, const char* key, void* data) { - xbt_dict_set_ext(dict, key, strlen(key), data, free_ctn); + xbt_dict_set_ext(dict, key, strlen(key), data); } /** @@ -195,29 +213,12 @@ void xbt_dict_set(xbt_dict_t dict, const char *key, void *data, void_f_pvoid_t f * @param key_len the size of the @a key * @return the data that we are looking for * - * Search the given @a key. Throws std::out_of_range when not found. + * Search the given @a key. Returns nullptr when not found. */ -void *xbt_dict_get_ext(xbt_dict_t dict, const char *key, int key_len) +void* xbt_dict_get_or_null_ext(const_xbt_dict_t dict, const char* key, int key_len) { unsigned int hash_code = xbt_str_hash_ext(key, key_len); - xbt_dictelm_t current = dict->table[hash_code & dict->table_size]; - - while (current != nullptr && (hash_code != current->hash_code || key_len != current->key_len - || memcmp(key, current->key, key_len))) { - current = current->next; - } - - if (current == nullptr) - throw std::out_of_range(simgrid::xbt::string_printf("key %.*s not found", key_len, key)); - - return current->content; -} - -/** @brief like xbt_dict_get_ext(), but returning nullptr when not found */ -void *xbt_dict_get_or_null_ext(xbt_dict_t dict, const char *key, int key_len) -{ - unsigned int hash_code = xbt_str_hash_ext(key, key_len); - xbt_dictelm_t current = dict->table[hash_code & dict->table_size]; + const s_xbt_dictelm* current = dict->table[hash_code & dict->table_size]; while (current != nullptr && (hash_code != current->hash_code || key_len != current->key_len || memcmp(key, current->key, key_len))) { @@ -230,24 +231,6 @@ void *xbt_dict_get_or_null_ext(xbt_dict_t dict, const char *key, int key_len) return current->content; } -/** - * @brief retrieve the key associated to that object. Warning, that's a linear search - * - * Returns nullptr if the object cannot be found - */ -char *xbt_dict_get_key(xbt_dict_t dict, const void *data) -{ - for (int i = 0; i <= dict->table_size; i++) { - xbt_dictelm_t current = dict->table[i]; - while (current != nullptr) { - if (current->content == data) - return current->key; - current = current->next; - } - } - return nullptr; -} - /** * @brief Retrieve data from the dict (null-terminated key) * @@ -255,12 +238,16 @@ char *xbt_dict_get_key(xbt_dict_t dict, const void *data) * @param key the key to find data * @return the data that we are looking for * - * Search the given @a key. Throws std::out_of_range when not found. - * Check xbt_dict_get_or_null() for a version returning nullptr without exception when not found. + * Search the given @a key. Returns nullptr when not found. */ -void *xbt_dict_get(xbt_dict_t dict, const char *key) +void* xbt_dict_get_or_null(const_xbt_dict_t dict, const char* key) { - return xbt_dict_get_elm(dict, key)->content; + const s_xbt_dictelm* current = xbt_dict_get_elm_or_null(dict, key); + + if (current == nullptr) + return nullptr; + + return current->content; } /** @@ -270,36 +257,9 @@ void *xbt_dict_get(xbt_dict_t dict, const char *key) * @param key the key to find data * @return the s_xbt_dictelm_t that we are looking for * - * Search the given @a key. Throws std::out_of_range when not found. - * Check xbt_dict_get_or_null() for a version returning nullptr without exception when not found. + * Search the given @a key. Returns nullptr when not found. */ -xbt_dictelm_t xbt_dict_get_elm(xbt_dict_t dict, const char *key) -{ - xbt_dictelm_t current = xbt_dict_get_elm_or_null(dict, key); - - if (current == nullptr) - throw std::out_of_range(simgrid::xbt::string_printf("key %s not found", key)); - - return current; -} - -/** - * @brief like xbt_dict_get(), but returning nullptr when not found - */ -void *xbt_dict_get_or_null(xbt_dict_t dict, const char *key) -{ - xbt_dictelm_t current = xbt_dict_get_elm_or_null(dict, key); - - if (current == nullptr) - return nullptr; - - return current->content; -} - -/** - * @brief like xbt_dict_get_elm(), but returning nullptr when not found - */ -xbt_dictelm_t xbt_dict_get_elm_or_null(xbt_dict_t dict, const char *key) +xbt_dictelm_t xbt_dict_get_elm_or_null(const_xbt_dict_t dict, const char* key) { unsigned int hash_code = xbt_str_hash(key); xbt_dictelm_t current = dict->table[hash_code & dict->table_size]; @@ -347,45 +307,11 @@ void xbt_dict_remove_ext(xbt_dict_t dict, const char *key, int key_len) dict->count--; } -/** - * @brief Remove data from the dict (null-terminated key) - * - * @param dict the dict - * @param key the key of the data to be removed - * - * Remove the entry associated with the given @a key - */ -void xbt_dict_remove(xbt_dict_t dict, const char *key) -{ - xbt_dict_remove_ext(dict, key, strlen(key)); -} - -/** @brief Remove all data from the dict */ -void xbt_dict_reset(xbt_dict_t dict) -{ - if (dict->count == 0) - return; - - for (int i = 0; i <= dict->table_size; i++) { - xbt_dictelm_t previous = nullptr; - xbt_dictelm_t current = dict->table[i]; - while (current != nullptr) { - previous = current; - current = current->next; - xbt_dictelm_free(dict, previous); - } - dict->table[i] = nullptr; - } - - dict->count = 0; - dict->fill = 0; -} - /** * @brief Return the number of elements in the dict. * @param dict a dictionary */ -int xbt_dict_length(xbt_dict_t dict) +int xbt_dict_length(const_xbt_dict_t dict) { return dict->count; } @@ -393,31 +319,7 @@ int xbt_dict_length(xbt_dict_t dict) /** * @brief test if the dict is empty or not */ -int xbt_dict_is_empty(xbt_dict_t dict) +int xbt_dict_is_empty(const_xbt_dict_t dict) { return not dict || (xbt_dict_length(dict) == 0); } - -/** - * Create the dict mallocators. - * This is an internal XBT function called during the lib initialization. - * It can be used several times to recreate the mallocator, for example when you switch to MC mode - */ -void xbt_dict_preinit() -{ - if (dict_elm_mallocator == nullptr) - dict_elm_mallocator = xbt_mallocator_new(256, dict_elm_mallocator_new_f, dict_elm_mallocator_free_f, - dict_elm_mallocator_reset_f); -} - -/** - * Destroy the dict mallocators. - * This is an internal XBT function during the lib initialization - */ -void xbt_dict_postexit() -{ - if (dict_elm_mallocator != nullptr) { - xbt_mallocator_free(dict_elm_mallocator); - dict_elm_mallocator = nullptr; - } -}