--- a/src/ucx/hash_map.c Sat Mar 25 17:18:51 2023 +0100 +++ b/src/ucx/hash_map.c Fri May 05 18:02:11 2023 +0200 @@ -30,6 +30,17 @@ #include "cx/hash_map.h" #include "cx/utils.h" +struct cx_hash_map_element_s { + /** A pointer to the next element in the current bucket. */ + struct cx_hash_map_element_s *next; + + /** The corresponding key. */ + CxHashKey key; + + /** The value data. */ + char data[]; +}; + 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) { @@ -37,8 +48,10 @@ if (elem != NULL) { do { struct cx_hash_map_element_s *next = elem->next; + // invoke the destructor + cx_invoke_destructor(map, elem->data); // free the key data - cxFree(map->allocator, elem->key.data.obj); + cxFree(map->allocator, (void *) elem->key.data); // free the node cxFree(map->allocator, elem); // proceed @@ -69,7 +82,7 @@ void *value ) { struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; - CxAllocator *allocator = map->allocator; + CxAllocator const *allocator = map->allocator; unsigned hash = key.hash; if (hash == 0) { @@ -87,27 +100,37 @@ } if (elm != NULL && elm->key.hash == hash && elm->key.len == key.len && - memcmp(elm->key.data.obj, key.data.obj, key.len) == 0) { + memcmp(elm->key.data, key.data, key.len) == 0) { // overwrite existing element - elm->data = value; + if (map->store_pointer) { + memcpy(elm->data, &value, sizeof(void *)); + } else { + memcpy(elm->data, value, map->item_size); + } } else { // allocate new element - struct cx_hash_map_element_s *e = cxMalloc(allocator, sizeof(struct cx_hash_map_element_s)); + struct cx_hash_map_element_s *e = cxMalloc( + allocator, + sizeof(struct cx_hash_map_element_s) + map->item_size + ); if (e == NULL) { return -1; } // write the value - // TODO: depending on future map features, we may want to copy here - e->data = value; + if (map->store_pointer) { + memcpy(e->data, &value, sizeof(void *)); + } else { + memcpy(e->data, value, map->item_size); + } // copy the key void *kd = cxMalloc(allocator, key.len); if (kd == NULL) { return -1; } - memcpy(kd, key.data.obj, key.len); - e->key.data.obj = kd; + memcpy(kd, key.data, key.len); + e->key.data = kd; e->key.len = key.len; e->key.hash = hash; @@ -139,7 +162,7 @@ prev->next = elm->next; } // free element - cxFree(hash_map->base.allocator, elm->key.data.obj); + cxFree(hash_map->base.allocator, (void *) elm->key.data); cxFree(hash_map->base.allocator, elm); // decrease size hash_map->base.size--; @@ -151,12 +174,14 @@ * @param map the map * @param key the key to look up * @param remove flag indicating whether the looked up entry shall be removed - * @return the value corresponding to the key or \c NULL + * @param destroy flag indicating whether the destructor shall be invoked + * @return a pointer to the value corresponding to the key or \c NULL */ static void *cx_hash_map_get_remove( CxMap *map, CxHashKey key, - bool remove + bool remove, + bool destroy ) { struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; @@ -171,8 +196,17 @@ struct cx_hash_map_element_s *prev = NULL; while (elm && elm->key.hash <= hash) { if (elm->key.hash == hash && elm->key.len == key.len) { - if (memcmp(elm->key.data.obj, key.data.obj, key.len) == 0) { - void *data = elm->data; + if (memcmp(elm->key.data, key.data, key.len) == 0) { + void *data = NULL; + if (destroy) { + cx_invoke_destructor(map, elm->data); + } else { + if (map->store_pointer) { + data = *(void **) elm->data; + } else { + data = elm->data; + } + } if (remove) { cx_hash_map_unlink(hash_map, slot, prev, elm); } @@ -190,15 +224,16 @@ CxMap const *map, CxHashKey key ) { - // we can safely cast, because we know when remove=false, the map stays untouched - return cx_hash_map_get_remove((CxMap *) map, key, false); + // we can safely cast, because we know the map stays untouched + return cx_hash_map_get_remove((CxMap *) map, key, false, false); } static void *cx_hash_map_remove( CxMap *map, - CxHashKey key + CxHashKey key, + bool destroy ) { - return cx_hash_map_get_remove(map, key, true); + return cx_hash_map_get_remove(map, key, true, destroy); } static void *cx_hash_map_iter_current_entry(void const *it) { @@ -215,9 +250,13 @@ 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; struct cx_hash_map_element_s *elm = iter->elem_handle; - // TODO: return a pointer to data if this map is storing copies - return elm->data; + if (map->base.store_pointer) { + return *(void **) elm->data; + } else { + return elm->data; + } } static bool cx_hash_map_iter_valid(void const *it) { @@ -250,6 +289,9 @@ } } + // destroy + cx_invoke_destructor((struct cx_map_s *) map, elm->data); + // unlink cx_hash_map_unlink(map, iter->slot, prev, elm); @@ -274,8 +316,11 @@ iter->kv_data.value = NULL; } else { iter->kv_data.key = &elm->key; - // TODO: pointer to data if this map is storing copies - iter->kv_data.value = elm->data; + if (map->base.store_pointer) { + iter->kv_data.value = *(void **) elm->data; + } else { + iter->kv_data.value = elm->data; + } } } @@ -302,7 +347,7 @@ iter.slot = 0; iter.index = 0; - + if (map->size > 0) { struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; struct cx_hash_map_element_s *elm = hash_map->buckets[0]; @@ -311,8 +356,11 @@ } iter.elem_handle = elm; iter.kv_data.key = &elm->key; - // TODO: pointer to data if this map is storing copies - iter.kv_data.value = elm->data; + if (map->store_pointer) { + iter.kv_data.value = *(void **) elm->data; + } else { + iter.kv_data.value = elm->data; + } } else { iter.elem_handle = NULL; iter.kv_data.key = NULL; @@ -371,7 +419,8 @@ }; CxMap *cxHashMapCreate( - CxAllocator *allocator, + CxAllocator const *allocator, + size_t itemsize, size_t buckets ) { if (buckets == 0) { @@ -379,12 +428,14 @@ buckets = 16; } - struct cx_hash_map_s *map = cxMalloc(allocator, sizeof(struct cx_hash_map_s)); + struct cx_hash_map_s *map = cxCalloc(allocator, 1, + sizeof(struct cx_hash_map_s)); if (map == NULL) return NULL; // initialize hash map members map->bucket_count = buckets; - map->buckets = cxCalloc(allocator, buckets, sizeof(struct cx_hash_map_element_s *)); + map->buckets = cxCalloc(allocator, buckets, + sizeof(struct cx_hash_map_element_s *)); if (map->buckets == NULL) { cxFree(allocator, map); return NULL; @@ -393,7 +444,14 @@ // initialize base members map->base.cl = &cx_hash_map_class; map->base.allocator = allocator; - map->base.size = 0; + + if (itemsize > 0) { + map->base.store_pointer = false; + map->base.item_size = itemsize; + } else { + map->base.store_pointer = true; + map->base.item_size = sizeof(void *); + } return (CxMap *) map; } @@ -403,8 +461,10 @@ if (map->size > ((hash_map->bucket_count * 3) >> 2)) { size_t new_bucket_count = (map->size * 5) >> 1; - struct cx_hash_map_element_s **new_buckets = cxCalloc(map->allocator, - new_bucket_count, sizeof(struct cx_hash_map_element_s *)); + struct cx_hash_map_element_s **new_buckets = cxCalloc( + map->allocator, + new_bucket_count, sizeof(struct cx_hash_map_element_s *) + ); if (new_buckets == NULL) { return 1; @@ -420,7 +480,8 @@ // find position where to insert struct cx_hash_map_element_s *bucket_next = new_buckets[new_slot]; struct cx_hash_map_element_s *bucket_prev = NULL; - while (bucket_next != NULL && bucket_next->key.hash < elm->key.hash) { + while (bucket_next != NULL && + bucket_next->key.hash < elm->key.hash) { bucket_prev = bucket_next; bucket_next = bucket_next->next; }