1.1 --- a/src/hash_map.c Fri May 27 17:40:27 2022 +0200
1.2 +++ b/src/hash_map.c Wed Jun 08 21:33:31 2022 +0200
1.3 @@ -30,60 +30,6 @@
1.4 #include "cx/hash_map.h"
1.5 #include "cx/utils.h"
1.6
1.7 -/**
1.8 - * Computes a murmur hash-2.
1.9 - *
1.10 - * @param data the data to hash
1.11 - * @param len the length of the data
1.12 - * @return the murmur hash-2 of the data
1.13 - */
1.14 -static unsigned cx_hash_map_murmur(
1.15 - unsigned char const *data,
1.16 - size_t len
1.17 -) {
1.18 - unsigned m = 0x5bd1e995;
1.19 - unsigned r = 24;
1.20 - unsigned h = 25 ^ len;
1.21 - unsigned i = 0;
1.22 - while (len >= 4) {
1.23 - unsigned k = data[i + 0] & 0xFF;
1.24 - k |= (data[i + 1] & 0xFF) << 8;
1.25 - k |= (data[i + 2] & 0xFF) << 16;
1.26 - k |= (data[i + 3] & 0xFF) << 24;
1.27 -
1.28 - k *= m;
1.29 - k ^= k >> r;
1.30 - k *= m;
1.31 -
1.32 - h *= m;
1.33 - h ^= k;
1.34 -
1.35 - i += 4;
1.36 - len -= 4;
1.37 - }
1.38 -
1.39 - switch (len) {
1.40 - case 3:
1.41 - h ^= (data[i + 2] & 0xFF) << 16;
1.42 - __attribute__((__fallthrough__));
1.43 - case 2:
1.44 - h ^= (data[i + 1] & 0xFF) << 8;
1.45 - __attribute__((__fallthrough__));
1.46 - case 1:
1.47 - h ^= (data[i + 0] & 0xFF);
1.48 - h *= m;
1.49 - __attribute__((__fallthrough__));
1.50 - default:
1.51 - /* do nothing */;
1.52 - }
1.53 -
1.54 - h ^= h >> 13;
1.55 - h *= m;
1.56 - h ^= h >> 15;
1.57 -
1.58 - return h;
1.59 -}
1.60 -
1.61 static void cx_hash_map_clear(struct cx_map_s *map) {
1.62 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
1.63 cx_for_n(i, hash_map->bucket_count) {
1.64 @@ -92,7 +38,7 @@
1.65 do {
1.66 struct cx_hash_map_element_s *next = elem->next;
1.67 // free the key data
1.68 - cxFree(map->allocator, elem->key.data);
1.69 + cxFree(map->allocator, elem->key.data.obj);
1.70 // free the node
1.71 cxFree(map->allocator, elem);
1.72 // proceed
1.73 @@ -119,13 +65,17 @@
1.74
1.75 static int cx_hash_map_put(
1.76 CxMap *map,
1.77 - CxDataPtr key,
1.78 + CxHashKey key,
1.79 void *value
1.80 ) {
1.81 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
1.82 CxAllocator *allocator = map->allocator;
1.83
1.84 - unsigned hash = cx_hash_map_murmur(key.data, key.len);
1.85 + unsigned hash = key.hash;
1.86 + if (hash == 0) {
1.87 + cx_hash_murmur(&key);
1.88 + hash = key.hash;
1.89 + }
1.90
1.91 size_t slot = hash % hash_map->bucket_count;
1.92 struct cx_hash_map_element_s *elm = hash_map->buckets[slot];
1.93 @@ -151,8 +101,8 @@
1.94 if (kd == NULL) {
1.95 return -1;
1.96 }
1.97 - memcpy(kd, key.data, key.len);
1.98 - e->key.data = kd;
1.99 + memcpy(kd, key.data.obj, key.len);
1.100 + e->key.data.obj = kd;
1.101 e->key.len = key.len;
1.102 e->key.hash = hash;
1.103
1.104 @@ -187,7 +137,7 @@
1.105 prev->next = elm->next;
1.106 }
1.107 // free element
1.108 - cxFree(hash_map->base.allocator, elm->key.data);
1.109 + cxFree(hash_map->base.allocator, elm->key.data.obj);
1.110 cxFree(hash_map->base.allocator, elm);
1.111 // decrease size
1.112 hash_map->base.size--;
1.113 @@ -203,19 +153,23 @@
1.114 */
1.115 static void *cx_hash_map_get_remove(
1.116 CxMap *map,
1.117 - CxDataPtr key,
1.118 + CxHashKey key,
1.119 bool remove
1.120 ) {
1.121 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
1.122
1.123 - unsigned hash = cx_hash_map_murmur(key.data, key.len);
1.124 + unsigned hash = key.hash;
1.125 + if (hash == 0) {
1.126 + cx_hash_murmur(&key);
1.127 + hash = key.hash;
1.128 + }
1.129
1.130 size_t slot = hash % hash_map->bucket_count;
1.131 struct cx_hash_map_element_s *elm = hash_map->buckets[slot];
1.132 struct cx_hash_map_element_s *prev = NULL;
1.133 while (elm && elm->key.hash <= hash) {
1.134 if (elm->key.hash == hash && elm->key.len == key.len) {
1.135 - if (memcmp(elm->key.data, key.data, key.len) == 0) {
1.136 + if (memcmp(elm->key.data.obj, key.data.obj, key.len) == 0) {
1.137 void *data = elm->data;
1.138 if (remove) {
1.139 cx_hash_map_unlink(hash_map, slot, prev, elm);
1.140 @@ -232,7 +186,7 @@
1.141
1.142 static void *cx_hash_map_get(
1.143 CxMap const *map,
1.144 - CxDataPtr key
1.145 + CxHashKey key
1.146 ) {
1.147 // we can safely cast, because we know when remove=false, the map stays untouched
1.148 return cx_hash_map_get_remove((CxMap *) map, key, false);
1.149 @@ -240,7 +194,7 @@
1.150
1.151 static void *cx_hash_map_remove(
1.152 CxMap *map,
1.153 - CxDataPtr key
1.154 + CxHashKey key
1.155 ) {
1.156 return cx_hash_map_get_remove(map, key, true);
1.157 }
