diff -r d7f0b5a9a985 -r 89b2a83728b1 src/hash_map.c --- a/src/hash_map.c Wed May 18 16:26:32 2022 +0200 +++ b/src/hash_map.c Thu May 19 14:30:20 2022 +0200 @@ -26,8 +26,10 @@ * POSSIBILITY OF SUCH DAMAGE. */ +#include #include #include "cx/hash_map.h" +#include "cx/utils.h" /** * Computes a murmur hash-2. @@ -83,23 +85,211 @@ return h; } +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) { + struct cx_hash_map_element_s *elem = hash_map->buckets[i]; + if (elem != NULL) { + do { + struct cx_hash_map_element_s *next = elem->next; + // free the key data + cxFree(map->allocator, elem->key.data); + // free the node + cxFree(map->allocator, elem); + // proceed + elem = next; + } while (elem != NULL); + + // do not leave a dangling pointer + hash_map->buckets[i] = NULL; + } + } + map->size = 0; +} + +static void cx_hash_map_destructor(struct cx_map_s *map) { + struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; + + // free the buckets + cx_hash_map_clear(map); + cxFree(map->allocator, hash_map->buckets); + + // free the map structure + cxFree(map->allocator, map); +} + +static int cx_hash_map_put( + CxMap *map, + CxDataPtr key, + void *value +) { + struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; + CxAllocator *allocator = map->allocator; + + unsigned hash = cx_hash_map_murmur(key.data, key.len); + + size_t slot = hash % hash_map->bucket_count; + struct cx_hash_map_element_s *elm = hash_map->buckets[slot]; + struct cx_hash_map_element_s *prev = NULL; + + while (elm != NULL && elm->key.hash < hash) { + prev = elm; + elm = elm->next; + } + + if (elm == NULL || elm->key.hash != hash) { + struct cx_hash_map_element_s *e = cxMalloc(allocator, sizeof(struct cx_hash_map_element_s)); + if (e == NULL) { + return -1; + } + + // write the value + // TODO: depending on future map features, we may want to copy here + e->data = value; + + // copy the key + void *kd = cxMalloc(allocator, key.len); + if (kd == NULL) { + return -1; + } + memcpy(kd, key.data, key.len); + e->key.data = kd; + e->key.len = key.len; + e->key.hash = hash; + + // insert the element into the linked list + if (prev == NULL) { + hash_map->buckets[slot] = e; + } else { + prev->next = e; + } + e->next = elm; + + // increase the size + map->size++; + } else { + // (elem != NULL && elem->key.hash == hash) - overwrite value of existing element + elm->data = value; + } + + return 0; +} /** - * Creates a hash map key based on the given data. + * Helper function to avoid code duplication. * - * This function implicitly computes the hash. - * - * @attention The data will be copied to the key structure. - * - * @param data the data for the key - * @return the computed key + * @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 */ -static struct cx_hash_map_key_s cx_hash_map_key(CxDataPtr data) { - unsigned char *target = malloc(data.len); - memcpy(target, data.data, data.len); - struct cx_hash_map_key_s key; - key.data.data = target; - key.data.len = data.len; - key.hash = cx_hash_map_murmur(target, data.len); - return key; +static void *cx_hash_map_get_remove( + CxMap *map, + CxDataPtr key, + bool remove +) { + struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; + + unsigned hash = cx_hash_map_murmur(key.data, key.len); + + size_t slot = hash % hash_map->bucket_count; + struct cx_hash_map_element_s *elm = hash_map->buckets[slot]; + 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, key.data, key.len) == 0) { + void *data = elm->data; + if (remove) { + // unlink + if (prev) { + prev->next = elm->next; + } else { + hash_map->buckets[slot] = elm->next; + } + // free element + cxFree(map->allocator, elm->key.data); + cxFree(map->allocator, elm); + // decrease size + map->size--; + } + return data; + } + } + prev = elm; + elm = prev->next; + } + + return NULL; } + +static void *cx_hash_map_get( + CxMap const *map, + CxDataPtr 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); +} + +static void *cx_hash_map_remove( + CxMap *map, + CxDataPtr key +) { + return cx_hash_map_get_remove(map, key, true); +} + +static CxIterator cx_hash_map_iterator(CxMap const *map) { + CxIterator iter; + // TODO: initialize iter + return iter; +} + +static CxIterator cx_hash_map_iterator_keys(CxMap const *map) { + CxIterator iter; + // TODO: initialize iter + return iter; +} + +static CxIterator cx_hash_map_iterator_values(CxMap const *map) { + CxIterator iter; + // TODO: initialize iter + return iter; +} + +static cx_map_class cx_hash_map_class = { + cx_hash_map_destructor, + cx_hash_map_clear, + cx_hash_map_put, + cx_hash_map_get, + cx_hash_map_remove, + cx_hash_map_iterator, + cx_hash_map_iterator_keys, + cx_hash_map_iterator_values, +}; + +CxMap *cxHashMapCreate( + CxAllocator *allocator, + size_t buckets +) { + if (buckets == 0) { + // implementation defined default + buckets = 16; + } + + struct cx_hash_map_s *map = cxMalloc(allocator, 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 *)); + 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; + + return (CxMap *) map; +}