diff -r bbe2925eb590 -r 83fdf679df99 ucx/hash_map.c --- a/ucx/hash_map.c Thu Nov 28 17:53:13 2024 +0100 +++ b/ucx/hash_map.c Mon Jan 06 21:18:36 2025 +0100 @@ -27,10 +27,10 @@ */ #include "cx/hash_map.h" -#include "cx/utils.h" #include #include +#include struct cx_hash_map_element_s { /** A pointer to the next element in the current bucket. */ @@ -45,7 +45,7 @@ static void cx_hash_map_clear(struct cx_map_s *map) { struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; - cx_for_n(i, hash_map->bucket_count) { + for (size_t i = 0; i < hash_map->bucket_count; i++) { struct cx_hash_map_element_s *elem = hash_map->buckets[i]; if (elem != NULL) { do { @@ -84,7 +84,7 @@ void *value ) { struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; - CxAllocator const *allocator = map->collection.allocator; + const CxAllocator *allocator = map->collection.allocator; unsigned hash = key.hash; if (hash == 0) { @@ -115,9 +115,7 @@ allocator, sizeof(struct cx_hash_map_element_s) + map->collection.elem_size ); - if (e == NULL) { - return -1; - } + if (e == NULL) return -1; // write the value if (map->collection.store_pointer) { @@ -128,9 +126,7 @@ // copy the key void *kd = cxMalloc(allocator, key.len); - if (kd == NULL) { - return -1; - } + if (kd == NULL) return -1; memcpy(kd, key.data, key.len); e->key.data = kd; e->key.len = key.len; @@ -173,17 +169,28 @@ /** * Helper function to avoid code duplication. * + * If @p remove is true, and @p targetbuf is @c NULL, the element + * will be destroyed when found. + * + * If @p remove is true, and @p targetbuf is set, the element will + * be copied to that buffer and no destructor function is called. + * + * If @p remove is false, @p targetbuf must not be non-null and + * either the pointer, when the map is storing pointers, is copied + * to the target buffer, or a pointer to the stored object will + * be copied to the target buffer. + * * @param map the map * @param key the key to look up + * @param targetbuf see description * @param remove flag indicating whether the looked up entry shall be removed - * @param destroy flag indicating whether the destructor shall be invoked - * @return a pointer to the value corresponding to the key or \c NULL + * @return zero, if the key was found, non-zero otherwise */ -static void *cx_hash_map_get_remove( +static int cx_hash_map_get_remove( CxMap *map, CxHashKey key, - bool remove, - bool destroy + void *targetbuf, + bool remove ) { struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; @@ -199,60 +206,66 @@ while (elm && elm->key.hash <= hash) { if (elm->key.hash == hash && elm->key.len == key.len) { if (memcmp(elm->key.data, key.data, key.len) == 0) { - void *data = NULL; - if (destroy) { - cx_invoke_destructor(map, elm->data); + if (remove) { + if (targetbuf == NULL) { + cx_invoke_destructor(map, elm->data); + } else { + memcpy(targetbuf, elm->data, map->collection.elem_size); + } + cx_hash_map_unlink(hash_map, slot, prev, elm); } else { + assert(targetbuf != NULL); + void *data = NULL; if (map->collection.store_pointer) { data = *(void **) elm->data; } else { data = elm->data; } + memcpy(targetbuf, &data, sizeof(void *)); } - if (remove) { - cx_hash_map_unlink(hash_map, slot, prev, elm); - } - return data; + return 0; } } prev = elm; elm = prev->next; } - return NULL; + return 1; } static void *cx_hash_map_get( - CxMap const *map, + const CxMap *map, CxHashKey key ) { // we can safely cast, because we know the map stays untouched - return cx_hash_map_get_remove((CxMap *) map, key, false, false); + void *ptr = NULL; + int found = cx_hash_map_get_remove((CxMap *) map, key, &ptr, false); + return found == 0 ? ptr : NULL; } -static void *cx_hash_map_remove( +static int cx_hash_map_remove( CxMap *map, CxHashKey key, - bool destroy + void *targetbuf ) { - return cx_hash_map_get_remove(map, key, true, destroy); + return cx_hash_map_get_remove(map, key, targetbuf, true); } -static void *cx_hash_map_iter_current_entry(void const *it) { - struct cx_iterator_s const *iter = it; +static void *cx_hash_map_iter_current_entry(const void *it) { + const struct cx_iterator_s *iter = it; // struct has to have a compatible signature return (struct cx_map_entry_s *) &(iter->kv_data); } -static void *cx_hash_map_iter_current_key(void const *it) { - struct cx_iterator_s const *iter = it; +static void *cx_hash_map_iter_current_key(const void *it) { + const struct cx_iterator_s *iter = it; struct cx_hash_map_element_s *elm = iter->elem_handle; return &elm->key; } -static void *cx_hash_map_iter_current_value(void const *it) { - struct cx_iterator_s const *iter = it; - struct cx_hash_map_s const *map = iter->src_handle.c; +static void *cx_hash_map_iter_current_value(const void *it) { + const struct cx_iterator_s *iter = it; + const struct cx_hash_map_s *map = iter->src_handle.c; struct cx_hash_map_element_s *elm = iter->elem_handle; if (map->base.collection.store_pointer) { return *(void **) elm->data; @@ -261,8 +274,8 @@ } } -static bool cx_hash_map_iter_valid(void const *it) { - struct cx_iterator_s const *iter = it; +static bool cx_hash_map_iter_valid(const void *it) { + const struct cx_iterator_s *iter = it; return iter->elem_handle != NULL; } @@ -324,7 +337,7 @@ } static CxIterator cx_hash_map_iterator( - CxMap const *map, + const CxMap *map, enum cx_map_iterator_type type ) { CxIterator iter; @@ -346,7 +359,7 @@ iter.base.current = cx_hash_map_iter_current_value; break; default: - assert(false); + assert(false); // LCOV_EXCL_LINE } iter.base.valid = cx_hash_map_iter_valid; @@ -389,10 +402,14 @@ }; CxMap *cxHashMapCreate( - CxAllocator const *allocator, + const CxAllocator *allocator, size_t itemsize, size_t buckets ) { + if (allocator == NULL) { + allocator = cxDefaultAllocator; + } + if (buckets == 0) { // implementation defined default buckets = 16; @@ -406,10 +423,10 @@ map->bucket_count = buckets; map->buckets = cxCalloc(allocator, buckets, sizeof(struct cx_hash_map_element_s *)); - if (map->buckets == NULL) { + if (map->buckets == NULL) { // LCOV_EXCL_START cxFree(allocator, map); return NULL; - } + } // LCOV_EXCL_STOP // initialize base members map->base.cl = &cx_hash_map_class; @@ -431,17 +448,19 @@ if (map->collection.size > ((hash_map->bucket_count * 3) >> 2)) { size_t new_bucket_count = (map->collection.size * 5) >> 1; + if (new_bucket_count < hash_map->bucket_count) { + errno = EOVERFLOW; + return 1; + } struct cx_hash_map_element_s **new_buckets = cxCalloc( map->collection.allocator, new_bucket_count, sizeof(struct cx_hash_map_element_s *) ); - if (new_buckets == NULL) { - return 1; - } + if (new_buckets == NULL) return 1; // iterate through the elements and assign them to their new slots - cx_for_n(slot, hash_map->bucket_count) { + for (size_t slot = 0; slot < hash_map->bucket_count; slot++) { struct cx_hash_map_element_s *elm = hash_map->buckets[slot]; while (elm != NULL) { struct cx_hash_map_element_s *next = elm->next;