1.1 --- a/src/hash_map.c Wed May 18 16:26:32 2022 +0200
1.2 +++ b/src/hash_map.c Thu May 19 14:30:20 2022 +0200
1.3 @@ -26,8 +26,10 @@
1.4 * POSSIBILITY OF SUCH DAMAGE.
1.5 */
1.6
1.7 +#include <errno.h>
1.8 #include <string.h>
1.9 #include "cx/hash_map.h"
1.10 +#include "cx/utils.h"
1.11
1.12 /**
1.13 * Computes a murmur hash-2.
1.14 @@ -83,23 +85,211 @@
1.15 return h;
1.16 }
1.17
1.18 +static void cx_hash_map_clear(struct cx_map_s *map) {
1.19 + struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
1.20 + cx_for_n(i, hash_map->bucket_count) {
1.21 + struct cx_hash_map_element_s *elem = hash_map->buckets[i];
1.22 + if (elem != NULL) {
1.23 + do {
1.24 + struct cx_hash_map_element_s *next = elem->next;
1.25 + // free the key data
1.26 + cxFree(map->allocator, elem->key.data);
1.27 + // free the node
1.28 + cxFree(map->allocator, elem);
1.29 + // proceed
1.30 + elem = next;
1.31 + } while (elem != NULL);
1.32 +
1.33 + // do not leave a dangling pointer
1.34 + hash_map->buckets[i] = NULL;
1.35 + }
1.36 + }
1.37 + map->size = 0;
1.38 +}
1.39 +
1.40 +static void cx_hash_map_destructor(struct cx_map_s *map) {
1.41 + struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
1.42 +
1.43 + // free the buckets
1.44 + cx_hash_map_clear(map);
1.45 + cxFree(map->allocator, hash_map->buckets);
1.46 +
1.47 + // free the map structure
1.48 + cxFree(map->allocator, map);
1.49 +}
1.50 +
1.51 +static int cx_hash_map_put(
1.52 + CxMap *map,
1.53 + CxDataPtr key,
1.54 + void *value
1.55 +) {
1.56 + struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
1.57 + CxAllocator *allocator = map->allocator;
1.58 +
1.59 + unsigned hash = cx_hash_map_murmur(key.data, key.len);
1.60 +
1.61 + size_t slot = hash % hash_map->bucket_count;
1.62 + struct cx_hash_map_element_s *elm = hash_map->buckets[slot];
1.63 + struct cx_hash_map_element_s *prev = NULL;
1.64 +
1.65 + while (elm != NULL && elm->key.hash < hash) {
1.66 + prev = elm;
1.67 + elm = elm->next;
1.68 + }
1.69 +
1.70 + if (elm == NULL || elm->key.hash != hash) {
1.71 + struct cx_hash_map_element_s *e = cxMalloc(allocator, sizeof(struct cx_hash_map_element_s));
1.72 + if (e == NULL) {
1.73 + return -1;
1.74 + }
1.75 +
1.76 + // write the value
1.77 + // TODO: depending on future map features, we may want to copy here
1.78 + e->data = value;
1.79 +
1.80 + // copy the key
1.81 + void *kd = cxMalloc(allocator, key.len);
1.82 + if (kd == NULL) {
1.83 + return -1;
1.84 + }
1.85 + memcpy(kd, key.data, key.len);
1.86 + e->key.data = kd;
1.87 + e->key.len = key.len;
1.88 + e->key.hash = hash;
1.89 +
1.90 + // insert the element into the linked list
1.91 + if (prev == NULL) {
1.92 + hash_map->buckets[slot] = e;
1.93 + } else {
1.94 + prev->next = e;
1.95 + }
1.96 + e->next = elm;
1.97 +
1.98 + // increase the size
1.99 + map->size++;
1.100 + } else {
1.101 + // (elem != NULL && elem->key.hash == hash) - overwrite value of existing element
1.102 + elm->data = value;
1.103 + }
1.104 +
1.105 + return 0;
1.106 +}
1.107
1.108 /**
1.109 - * Creates a hash map key based on the given data.
1.110 + * Helper function to avoid code duplication.
1.111 *
1.112 - * This function implicitly computes the hash.
1.113 - *
1.114 - * @attention The data will be copied to the key structure.
1.115 - *
1.116 - * @param data the data for the key
1.117 - * @return the computed key
1.118 + * @param map the map
1.119 + * @param key the key to look up
1.120 + * @param remove flag indicating whether the looked up entry shall be removed
1.121 + * @return the value corresponding to the key or \c NULL
1.122 */
1.123 -static struct cx_hash_map_key_s cx_hash_map_key(CxDataPtr data) {
1.124 - unsigned char *target = malloc(data.len);
1.125 - memcpy(target, data.data, data.len);
1.126 - struct cx_hash_map_key_s key;
1.127 - key.data.data = target;
1.128 - key.data.len = data.len;
1.129 - key.hash = cx_hash_map_murmur(target, data.len);
1.130 - return key;
1.131 +static void *cx_hash_map_get_remove(
1.132 + CxMap *map,
1.133 + CxDataPtr key,
1.134 + bool remove
1.135 +) {
1.136 + struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
1.137 +
1.138 + unsigned hash = cx_hash_map_murmur(key.data, key.len);
1.139 +
1.140 + size_t slot = hash % hash_map->bucket_count;
1.141 + struct cx_hash_map_element_s *elm = hash_map->buckets[slot];
1.142 + struct cx_hash_map_element_s *prev = NULL;
1.143 + while (elm && elm->key.hash <= hash) {
1.144 + if (elm->key.hash == hash && elm->key.len == key.len) {
1.145 + if (memcmp(elm->key.data, key.data, key.len) == 0) {
1.146 + void *data = elm->data;
1.147 + if (remove) {
1.148 + // unlink
1.149 + if (prev) {
1.150 + prev->next = elm->next;
1.151 + } else {
1.152 + hash_map->buckets[slot] = elm->next;
1.153 + }
1.154 + // free element
1.155 + cxFree(map->allocator, elm->key.data);
1.156 + cxFree(map->allocator, elm);
1.157 + // decrease size
1.158 + map->size--;
1.159 + }
1.160 + return data;
1.161 + }
1.162 + }
1.163 + prev = elm;
1.164 + elm = prev->next;
1.165 + }
1.166 +
1.167 + return NULL;
1.168 }
1.169 +
1.170 +static void *cx_hash_map_get(
1.171 + CxMap const *map,
1.172 + CxDataPtr key
1.173 +) {
1.174 + // we can safely cast, because we know when remove=false, the map stays untouched
1.175 + return cx_hash_map_get_remove((CxMap *) map, key, false);
1.176 +}
1.177 +
1.178 +static void *cx_hash_map_remove(
1.179 + CxMap *map,
1.180 + CxDataPtr key
1.181 +) {
1.182 + return cx_hash_map_get_remove(map, key, true);
1.183 +}
1.184 +
1.185 +static CxIterator cx_hash_map_iterator(CxMap const *map) {
1.186 + CxIterator iter;
1.187 + // TODO: initialize iter
1.188 + return iter;
1.189 +}
1.190 +
1.191 +static CxIterator cx_hash_map_iterator_keys(CxMap const *map) {
1.192 + CxIterator iter;
1.193 + // TODO: initialize iter
1.194 + return iter;
1.195 +}
1.196 +
1.197 +static CxIterator cx_hash_map_iterator_values(CxMap const *map) {
1.198 + CxIterator iter;
1.199 + // TODO: initialize iter
1.200 + return iter;
1.201 +}
1.202 +
1.203 +static cx_map_class cx_hash_map_class = {
1.204 + cx_hash_map_destructor,
1.205 + cx_hash_map_clear,
1.206 + cx_hash_map_put,
1.207 + cx_hash_map_get,
1.208 + cx_hash_map_remove,
1.209 + cx_hash_map_iterator,
1.210 + cx_hash_map_iterator_keys,
1.211 + cx_hash_map_iterator_values,
1.212 +};
1.213 +
1.214 +CxMap *cxHashMapCreate(
1.215 + CxAllocator *allocator,
1.216 + size_t buckets
1.217 +) {
1.218 + if (buckets == 0) {
1.219 + // implementation defined default
1.220 + buckets = 16;
1.221 + }
1.222 +
1.223 + struct cx_hash_map_s *map = cxMalloc(allocator, sizeof(struct cx_hash_map_s));
1.224 + if (map == NULL) return NULL;
1.225 +
1.226 + // initialize hash map members
1.227 + map->bucket_count = buckets;
1.228 + map->buckets = cxCalloc(allocator, buckets, sizeof(struct cx_hash_map_element_s *));
1.229 + if (map->buckets == NULL) {
1.230 + cxFree(allocator, map);
1.231 + return NULL;
1.232 + }
1.233 +
1.234 + // initialize base members
1.235 + map->base.cl = &cx_hash_map_class;
1.236 + map->base.allocator = allocator;
1.237 + map->base.size = 0;
1.238 +
1.239 + return (CxMap *) map;
1.240 +}
