* POSSIBILITY OF SUCH DAMAGE.
*/
-#include <string.h>
#include "cx/hash_map.h"
#include "cx/utils.h"
+#include <string.h>
+#include <assert.h>
+
struct cx_hash_map_element_s {
/** A pointer to the next element in the current bucket. */
struct cx_hash_map_element_s *next;
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
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) {
}
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
- if (map->store_pointers) {
+ if (map->store_pointer) {
memcpy(elm->data, &value, sizeof(void *));
} else {
- memcpy(elm->data, value, map->itemsize);
+ 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) + map->itemsize
+ sizeof(struct cx_hash_map_element_s) + map->item_size
);
if (e == NULL) {
return -1;
}
// write the value
- if (map->store_pointers) {
+ if (map->store_pointer) {
memcpy(e->data, &value, sizeof(void *));
} else {
- memcpy(e->data, value, map->itemsize);
+ memcpy(e->data, value, map->item_size);
}
// copy the key
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;
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--;
* @param map the map
* @param key the key to look up
* @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
*/
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;
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) {
+ if (memcmp(elm->key.data, key.data, key.len) == 0) {
void *data = NULL;
- if (map->store_pointers) {
- data = *(void **) elm->data;
- } else if (!remove) {
- data = elm->data;
+ 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);
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) {
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_pointers) {
+ if (map->base.store_pointer) {
return *(void **) elm->data;
} else {
return elm->data;
}
}
+ // destroy
+ cx_invoke_destructor((struct cx_map_s *) map, elm->data);
+
// unlink
cx_hash_map_unlink(map, iter->slot, prev, elm);
iter->kv_data.value = NULL;
} else {
iter->kv_data.key = &elm->key;
- if (map->base.store_pointers) {
+ if (map->base.store_pointer) {
iter->kv_data.value = *(void **) elm->data;
} else {
iter->kv_data.value = elm->data;
}
}
-static CxIterator cx_hash_map_iterator(CxMap const *map) {
+static CxIterator cx_hash_map_iterator(
+ CxMap const *map,
+ enum cx_map_iterator_type type
+) {
CxIterator iter;
iter.src_handle = map;
iter.base.valid = cx_hash_map_iter_valid;
iter.base.next = cx_hash_map_iter_next;
- iter.base.current = cx_hash_map_iter_current_entry;
+
+ switch (type) {
+ case CX_MAP_ITERATOR_PAIRS:
+ iter.base.current = cx_hash_map_iter_current_entry;
+ break;
+ case CX_MAP_ITERATOR_KEYS:
+ iter.base.current = cx_hash_map_iter_current_key;
+ break;
+ case CX_MAP_ITERATOR_VALUES:
+ iter.base.current = cx_hash_map_iter_current_value;
+ break;
+ default:
+ assert(false);
+ }
+
iter.base.flag_removal = cx_hash_map_iter_flag_rm;
iter.base.remove = false;
iter.base.mutating = false;
}
iter.elem_handle = elm;
iter.kv_data.key = &elm->key;
- if (map->store_pointers) {
+ if (map->store_pointer) {
iter.kv_data.value = *(void **) elm->data;
} else {
iter.kv_data.value = elm->data;
return iter;
}
-static CxIterator cx_hash_map_iterator_keys(CxMap const *map) {
- CxIterator iter = cx_hash_map_iterator(map);
- iter.base.current = cx_hash_map_iter_current_key;
- return iter;
-}
-
-static CxIterator cx_hash_map_iterator_values(CxMap const *map) {
- CxIterator iter = cx_hash_map_iterator(map);
- iter.base.current = cx_hash_map_iter_current_value;
- return iter;
-}
-
-static CxMutIterator cx_hash_map_mut_iterator(CxMap *map) {
- CxIterator it = cx_hash_map_iterator(map);
- it.base.mutating = true;
-
- // we know the iterators share the same memory layout
- CxMutIterator iter;
- memcpy(&iter, &it, sizeof(CxMutIterator));
- return iter;
-}
-
-static CxMutIterator cx_hash_map_mut_iterator_keys(CxMap *map) {
- CxMutIterator iter = cx_hash_map_mut_iterator(map);
- iter.base.current = cx_hash_map_iter_current_key;
- return iter;
-}
-
-static CxMutIterator cx_hash_map_mut_iterator_values(CxMap *map) {
- CxMutIterator iter = cx_hash_map_mut_iterator(map);
- iter.base.current = cx_hash_map_iter_current_value;
- return iter;
-}
-
static cx_map_class cx_hash_map_class = {
cx_hash_map_destructor,
cx_hash_map_clear,
cx_hash_map_get,
cx_hash_map_remove,
cx_hash_map_iterator,
- cx_hash_map_iterator_keys,
- cx_hash_map_iterator_values,
- cx_hash_map_mut_iterator,
- cx_hash_map_mut_iterator_keys,
- cx_hash_map_mut_iterator_values,
};
CxMap *cxHashMapCreate(
- CxAllocator *allocator,
+ CxAllocator const *allocator,
size_t itemsize,
size_t buckets
) {
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;
// initialize base members
map->base.cl = &cx_hash_map_class;
map->base.allocator = allocator;
- map->base.size = 0;
if (itemsize > 0) {
- map->base.store_pointers = false;
- map->base.itemsize = itemsize;
+ map->base.store_pointer = false;
+ map->base.item_size = itemsize;
} else {
- map->base.store_pointers = true;
- map->base.itemsize = sizeof(void *);
+ map->base.store_pointer = true;
+ map->base.item_size = sizeof(void *);
}
return (CxMap *) map;
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;
// 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;
}