--- a/src/ucx/hash_map.c Mon Feb 10 17:44:51 2025 +0100
+++ b/src/ucx/hash_map.c Sun Mar 02 18:10:52 2025 +0100
@@ -27,10 +27,10 @@
*/
#include "cx/hash_map.h"
-#include "cx/utils.h"
#include <string.h>
#include <assert.h>
+#include <errno.h>
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 {
@@ -53,9 +53,9 @@
// invoke the destructor
cx_invoke_destructor(map, elem->data);
// free the key data
- cxFree(map->allocator, (void *) elem->key.data);
+ cxFree(map->collection.allocator, (void *) elem->key.data);
// free the node
- cxFree(map->allocator, elem);
+ cxFree(map->collection.allocator, elem);
// proceed
elem = next;
} while (elem != NULL);
@@ -64,7 +64,7 @@
hash_map->buckets[i] = NULL;
}
}
- map->size = 0;
+ map->collection.size = 0;
}
static void cx_hash_map_destructor(struct cx_map_s *map) {
@@ -72,10 +72,10 @@
// free the buckets
cx_hash_map_clear(map);
- cxFree(map->allocator, hash_map->buckets);
+ cxFree(map->collection.allocator, hash_map->buckets);
// free the map structure
- cxFree(map->allocator, map);
+ cxFree(map->collection.allocator, map);
}
static int cx_hash_map_put(
@@ -84,7 +84,7 @@
void *value
) {
struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
- CxAllocator const *allocator = map->allocator;
+ const CxAllocator *allocator = map->collection.allocator;
unsigned hash = key.hash;
if (hash == 0) {
@@ -103,34 +103,31 @@
if (elm != NULL && elm->key.hash == hash && elm->key.len == key.len &&
memcmp(elm->key.data, key.data, key.len) == 0) {
- // overwrite existing element
- if (map->store_pointer) {
+ // overwrite existing element, but call destructors first
+ cx_invoke_destructor(map, elm->data);
+ if (map->collection.store_pointer) {
memcpy(elm->data, &value, sizeof(void *));
} else {
- memcpy(elm->data, value, map->item_size);
+ memcpy(elm->data, value, map->collection.elem_size);
}
} else {
// allocate new element
struct cx_hash_map_element_s *e = cxMalloc(
allocator,
- sizeof(struct cx_hash_map_element_s) + map->item_size
+ 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->store_pointer) {
+ if (map->collection.store_pointer) {
memcpy(e->data, &value, sizeof(void *));
} else {
- memcpy(e->data, value, map->item_size);
+ memcpy(e->data, value, map->collection.elem_size);
}
// 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;
@@ -145,7 +142,7 @@
e->next = elm;
// increase the size
- map->size++;
+ map->collection.size++;
}
return 0;
@@ -164,26 +161,37 @@
prev->next = elm->next;
}
// free element
- cxFree(hash_map->base.allocator, (void *) elm->key.data);
- cxFree(hash_map->base.allocator, elm);
+ cxFree(hash_map->base.collection.allocator, (void *) elm->key.data);
+ cxFree(hash_map->base.collection.allocator, elm);
// decrease size
- hash_map->base.size--;
+ hash_map->base.collection.size--;
}
/**
* 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,82 +207,87 @@
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 {
- if (map->store_pointer) {
+ 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;
- // struct has to have a compatible signature
- return (struct cx_map_entry_s *) &(iter->kv_data);
+static void *cx_hash_map_iter_current_entry(const void *it) {
+ const CxMapIterator *iter = it;
+ // we have to cast away const, because of the signature
+ return (void*) &iter->entry;
}
-static void *cx_hash_map_iter_current_key(void const *it) {
- struct cx_iterator_s const *iter = it;
- struct cx_hash_map_element_s *elm = iter->elem_handle;
+static void *cx_hash_map_iter_current_key(const void *it) {
+ const CxMapIterator *iter = it;
+ struct cx_hash_map_element_s *elm = iter->elem;
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;
- struct cx_hash_map_element_s *elm = iter->elem_handle;
- if (map->base.store_pointer) {
+static void *cx_hash_map_iter_current_value(const void *it) {
+ const CxMapIterator *iter = it;
+ const CxMap *map = iter->map.c;
+ struct cx_hash_map_element_s *elm = iter->elem;
+ if (map->collection.store_pointer) {
return *(void **) elm->data;
} else {
return elm->data;
}
}
-static bool cx_hash_map_iter_valid(void const *it) {
- struct cx_iterator_s const *iter = it;
- return iter->elem_handle != NULL;
+static bool cx_hash_map_iter_valid(const void *it) {
+ const CxMapIterator *iter = it;
+ return iter->elem != NULL;
}
static void cx_hash_map_iter_next(void *it) {
- struct cx_iterator_s *iter = it;
- struct cx_hash_map_element_s *elm = iter->elem_handle;
+ CxMapIterator *iter = it;
+ CxMap *map = iter->map.m;
+ struct cx_hash_map_s *hmap = (struct cx_hash_map_s *) map;
+ struct cx_hash_map_element_s *elm = iter->elem;
// remove current element, if asked
if (iter->base.remove) {
- // obtain mutable pointer to the map
- struct cx_mut_iterator_s *miter = it;
- struct cx_hash_map_s *map = miter->src_handle;
// clear the flag
iter->base.remove = false;
@@ -284,18 +297,18 @@
// search the previous element
struct cx_hash_map_element_s *prev = NULL;
- if (map->buckets[iter->slot] != elm) {
- prev = map->buckets[iter->slot];
+ if (hmap->buckets[iter->slot] != elm) {
+ prev = hmap->buckets[iter->slot];
while (prev->next != elm) {
prev = prev->next;
}
}
// destroy
- cx_invoke_destructor((struct cx_map_s *) map, elm->data);
+ cx_invoke_destructor(map, elm->data);
// unlink
- cx_hash_map_unlink(map, iter->slot, prev, elm);
+ cx_hash_map_unlink(hmap, iter->slot, prev, elm);
// advance
elm = next;
@@ -306,84 +319,73 @@
}
// search the next bucket, if required
- struct cx_hash_map_s const *map = iter->src_handle;
- while (elm == NULL && ++iter->slot < map->bucket_count) {
- elm = map->buckets[iter->slot];
+ while (elm == NULL && ++iter->slot < hmap->bucket_count) {
+ elm = hmap->buckets[iter->slot];
}
+ iter->elem = elm;
- // fill the struct with the next element
- iter->elem_handle = elm;
- if (elm == NULL) {
- iter->kv_data.key = NULL;
- iter->kv_data.value = NULL;
- } else {
- iter->kv_data.key = &elm->key;
- if (map->base.store_pointer) {
- iter->kv_data.value = *(void **) elm->data;
+ // copy data to a location where the iterator can point to
+ // we need to do it here, because the iterator function call
+ // must not modify the iterator (the parameter is const)
+ if (elm != NULL) {
+ iter->entry.key = &elm->key;
+ if (iter->map.c->collection.store_pointer) {
+ iter->entry.value = *(void **) elm->data;
} else {
- iter->kv_data.value = elm->data;
+ iter->entry.value = elm->data;
}
}
}
-static bool cx_hash_map_iter_flag_rm(void *it) {
- struct cx_iterator_base_s *iter = it;
- if (iter->mutating) {
- iter->remove = true;
- return true;
- } else {
- return false;
- }
-}
-
-static CxIterator cx_hash_map_iterator(
- CxMap const *map,
+static CxMapIterator cx_hash_map_iterator(
+ const CxMap *map,
enum cx_map_iterator_type type
) {
- CxIterator iter;
+ CxMapIterator iter;
- iter.src_handle = map;
- iter.base.valid = cx_hash_map_iter_valid;
- iter.base.next = cx_hash_map_iter_next;
+ iter.map.c = map;
+ iter.elem_count = map->collection.size;
switch (type) {
case CX_MAP_ITERATOR_PAIRS:
+ iter.elem_size = sizeof(CxMapEntry);
iter.base.current = cx_hash_map_iter_current_entry;
break;
case CX_MAP_ITERATOR_KEYS:
+ iter.elem_size = sizeof(CxHashKey);
iter.base.current = cx_hash_map_iter_current_key;
break;
case CX_MAP_ITERATOR_VALUES:
+ iter.elem_size = map->collection.elem_size;
iter.base.current = cx_hash_map_iter_current_value;
break;
default:
- assert(false);
+ assert(false); // LCOV_EXCL_LINE
}
- iter.base.flag_removal = cx_hash_map_iter_flag_rm;
+ iter.base.valid = cx_hash_map_iter_valid;
+ iter.base.next = cx_hash_map_iter_next;
iter.base.remove = false;
iter.base.mutating = false;
iter.slot = 0;
iter.index = 0;
- if (map->size > 0) {
+ if (map->collection.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];
while (elm == NULL) {
elm = hash_map->buckets[++iter.slot];
}
- iter.elem_handle = elm;
- iter.kv_data.key = &elm->key;
- if (map->store_pointer) {
- iter.kv_data.value = *(void **) elm->data;
+ iter.elem = elm;
+ iter.entry.key = &elm->key;
+ if (map->collection.store_pointer) {
+ iter.entry.value = *(void **) elm->data;
} else {
- iter.kv_data.value = elm->data;
+ iter.entry.value = elm->data;
}
} else {
- iter.elem_handle = NULL;
- iter.kv_data.key = NULL;
- iter.kv_data.value = NULL;
+ iter.elem = NULL;
}
return iter;
@@ -399,10 +401,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;
@@ -416,21 +422,20 @@
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;
- map->base.allocator = allocator;
+ map->base.collection.allocator = allocator;
if (itemsize > 0) {
- map->base.store_pointer = false;
- map->base.item_size = itemsize;
+ map->base.collection.elem_size = itemsize;
} else {
- map->base.store_pointer = true;
- map->base.item_size = sizeof(void *);
+ map->base.collection.elem_size = sizeof(void *);
+ map->base.collection.store_pointer = true;
}
return (CxMap *) map;
@@ -438,20 +443,22 @@
int cxMapRehash(CxMap *map) {
struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
- if (map->size > ((hash_map->bucket_count * 3) >> 2)) {
+ if (map->collection.size > ((hash_map->bucket_count * 3) >> 2)) {
- size_t new_bucket_count = (map->size * 5) >> 1;
+ 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->allocator,
+ 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;
@@ -482,7 +489,7 @@
// assign result to the map
hash_map->bucket_count = new_bucket_count;
- cxFree(map->allocator, hash_map->buckets);
+ cxFree(map->collection.allocator, hash_map->buckets);
hash_map->buckets = new_buckets;
}
return 0;