comparison: src/hash_map.c
src/hash_map.c
- changeset 563
- 69a83fad8a35
- parent 562
- fd3368c20413
- child 573
- 3f3a0d19db58
equal
deleted
inserted
replaced
| 562:fd3368c20413 | 563:69a83fad8a35 |
|---|---|
| 28 | 28 |
| 29 #include <string.h> | 29 #include <string.h> |
| 30 #include "cx/hash_map.h" | 30 #include "cx/hash_map.h" |
| 31 #include "cx/utils.h" | 31 #include "cx/utils.h" |
| 32 | 32 |
| 33 /** | |
| 34 * Computes a murmur hash-2. | |
| 35 * | |
| 36 * @param data the data to hash | |
| 37 * @param len the length of the data | |
| 38 * @return the murmur hash-2 of the data | |
| 39 */ | |
| 40 static unsigned cx_hash_map_murmur( | |
| 41 unsigned char const *data, | |
| 42 size_t len | |
| 43 ) { | |
| 44 unsigned m = 0x5bd1e995; | |
| 45 unsigned r = 24; | |
| 46 unsigned h = 25 ^ len; | |
| 47 unsigned i = 0; | |
| 48 while (len >= 4) { | |
| 49 unsigned k = data[i + 0] & 0xFF; | |
| 50 k |= (data[i + 1] & 0xFF) << 8; | |
| 51 k |= (data[i + 2] & 0xFF) << 16; | |
| 52 k |= (data[i + 3] & 0xFF) << 24; | |
| 53 | |
| 54 k *= m; | |
| 55 k ^= k >> r; | |
| 56 k *= m; | |
| 57 | |
| 58 h *= m; | |
| 59 h ^= k; | |
| 60 | |
| 61 i += 4; | |
| 62 len -= 4; | |
| 63 } | |
| 64 | |
| 65 switch (len) { | |
| 66 case 3: | |
| 67 h ^= (data[i + 2] & 0xFF) << 16; | |
| 68 __attribute__((__fallthrough__)); | |
| 69 case 2: | |
| 70 h ^= (data[i + 1] & 0xFF) << 8; | |
| 71 __attribute__((__fallthrough__)); | |
| 72 case 1: | |
| 73 h ^= (data[i + 0] & 0xFF); | |
| 74 h *= m; | |
| 75 __attribute__((__fallthrough__)); | |
| 76 default: | |
| 77 /* do nothing */; | |
| 78 } | |
| 79 | |
| 80 h ^= h >> 13; | |
| 81 h *= m; | |
| 82 h ^= h >> 15; | |
| 83 | |
| 84 return h; | |
| 85 } | |
| 86 | |
| 87 static void cx_hash_map_clear(struct cx_map_s *map) { | 33 static void cx_hash_map_clear(struct cx_map_s *map) { |
| 88 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; | 34 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; |
| 89 cx_for_n(i, hash_map->bucket_count) { | 35 cx_for_n(i, hash_map->bucket_count) { |
| 90 struct cx_hash_map_element_s *elem = hash_map->buckets[i]; | 36 struct cx_hash_map_element_s *elem = hash_map->buckets[i]; |
| 91 if (elem != NULL) { | 37 if (elem != NULL) { |
| 92 do { | 38 do { |
| 93 struct cx_hash_map_element_s *next = elem->next; | 39 struct cx_hash_map_element_s *next = elem->next; |
| 94 // free the key data | 40 // free the key data |
| 95 cxFree(map->allocator, elem->key.data); | 41 cxFree(map->allocator, elem->key.data.obj); |
| 96 // free the node | 42 // free the node |
| 97 cxFree(map->allocator, elem); | 43 cxFree(map->allocator, elem); |
| 98 // proceed | 44 // proceed |
| 99 elem = next; | 45 elem = next; |
| 100 } while (elem != NULL); | 46 } while (elem != NULL); |
| 117 cxFree(map->allocator, map); | 63 cxFree(map->allocator, map); |
| 118 } | 64 } |
| 119 | 65 |
| 120 static int cx_hash_map_put( | 66 static int cx_hash_map_put( |
| 121 CxMap *map, | 67 CxMap *map, |
| 122 CxDataPtr key, | 68 CxHashKey key, |
| 123 void *value | 69 void *value |
| 124 ) { | 70 ) { |
| 125 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; | 71 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; |
| 126 CxAllocator *allocator = map->allocator; | 72 CxAllocator *allocator = map->allocator; |
| 127 | 73 |
| 128 unsigned hash = cx_hash_map_murmur(key.data, key.len); | 74 unsigned hash = key.hash; |
| 75 if (hash == 0) { | |
| 76 cx_hash_murmur(&key); | |
| 77 hash = key.hash; | |
| 78 } | |
| 129 | 79 |
| 130 size_t slot = hash % hash_map->bucket_count; | 80 size_t slot = hash % hash_map->bucket_count; |
| 131 struct cx_hash_map_element_s *elm = hash_map->buckets[slot]; | 81 struct cx_hash_map_element_s *elm = hash_map->buckets[slot]; |
| 132 struct cx_hash_map_element_s *prev = NULL; | 82 struct cx_hash_map_element_s *prev = NULL; |
| 133 | 83 |
| 149 // copy the key | 99 // copy the key |
| 150 void *kd = cxMalloc(allocator, key.len); | 100 void *kd = cxMalloc(allocator, key.len); |
| 151 if (kd == NULL) { | 101 if (kd == NULL) { |
| 152 return -1; | 102 return -1; |
| 153 } | 103 } |
| 154 memcpy(kd, key.data, key.len); | 104 memcpy(kd, key.data.obj, key.len); |
| 155 e->key.data = kd; | 105 e->key.data.obj = kd; |
| 156 e->key.len = key.len; | 106 e->key.len = key.len; |
| 157 e->key.hash = hash; | 107 e->key.hash = hash; |
| 158 | 108 |
| 159 // insert the element into the linked list | 109 // insert the element into the linked list |
| 160 if (prev == NULL) { | 110 if (prev == NULL) { |
| 185 hash_map->buckets[slot] = elm->next; | 135 hash_map->buckets[slot] = elm->next; |
| 186 } else { | 136 } else { |
| 187 prev->next = elm->next; | 137 prev->next = elm->next; |
| 188 } | 138 } |
| 189 // free element | 139 // free element |
| 190 cxFree(hash_map->base.allocator, elm->key.data); | 140 cxFree(hash_map->base.allocator, elm->key.data.obj); |
| 191 cxFree(hash_map->base.allocator, elm); | 141 cxFree(hash_map->base.allocator, elm); |
| 192 // decrease size | 142 // decrease size |
| 193 hash_map->base.size--; | 143 hash_map->base.size--; |
| 194 } | 144 } |
| 195 | 145 |
| 201 * @param remove flag indicating whether the looked up entry shall be removed | 151 * @param remove flag indicating whether the looked up entry shall be removed |
| 202 * @return the value corresponding to the key or \c NULL | 152 * @return the value corresponding to the key or \c NULL |
| 203 */ | 153 */ |
| 204 static void *cx_hash_map_get_remove( | 154 static void *cx_hash_map_get_remove( |
| 205 CxMap *map, | 155 CxMap *map, |
| 206 CxDataPtr key, | 156 CxHashKey key, |
| 207 bool remove | 157 bool remove |
| 208 ) { | 158 ) { |
| 209 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; | 159 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; |
| 210 | 160 |
| 211 unsigned hash = cx_hash_map_murmur(key.data, key.len); | 161 unsigned hash = key.hash; |
| 162 if (hash == 0) { | |
| 163 cx_hash_murmur(&key); | |
| 164 hash = key.hash; | |
| 165 } | |
| 212 | 166 |
| 213 size_t slot = hash % hash_map->bucket_count; | 167 size_t slot = hash % hash_map->bucket_count; |
| 214 struct cx_hash_map_element_s *elm = hash_map->buckets[slot]; | 168 struct cx_hash_map_element_s *elm = hash_map->buckets[slot]; |
| 215 struct cx_hash_map_element_s *prev = NULL; | 169 struct cx_hash_map_element_s *prev = NULL; |
| 216 while (elm && elm->key.hash <= hash) { | 170 while (elm && elm->key.hash <= hash) { |
| 217 if (elm->key.hash == hash && elm->key.len == key.len) { | 171 if (elm->key.hash == hash && elm->key.len == key.len) { |
| 218 if (memcmp(elm->key.data, key.data, key.len) == 0) { | 172 if (memcmp(elm->key.data.obj, key.data.obj, key.len) == 0) { |
| 219 void *data = elm->data; | 173 void *data = elm->data; |
| 220 if (remove) { | 174 if (remove) { |
| 221 cx_hash_map_unlink(hash_map, slot, prev, elm); | 175 cx_hash_map_unlink(hash_map, slot, prev, elm); |
| 222 } | 176 } |
| 223 return data; | 177 return data; |
| 230 return NULL; | 184 return NULL; |
| 231 } | 185 } |
| 232 | 186 |
| 233 static void *cx_hash_map_get( | 187 static void *cx_hash_map_get( |
| 234 CxMap const *map, | 188 CxMap const *map, |
| 235 CxDataPtr key | 189 CxHashKey key |
| 236 ) { | 190 ) { |
| 237 // we can safely cast, because we know when remove=false, the map stays untouched | 191 // we can safely cast, because we know when remove=false, the map stays untouched |
| 238 return cx_hash_map_get_remove((CxMap *) map, key, false); | 192 return cx_hash_map_get_remove((CxMap *) map, key, false); |
| 239 } | 193 } |
| 240 | 194 |
| 241 static void *cx_hash_map_remove( | 195 static void *cx_hash_map_remove( |
| 242 CxMap *map, | 196 CxMap *map, |
| 243 CxDataPtr key | 197 CxHashKey key |
| 244 ) { | 198 ) { |
| 245 return cx_hash_map_get_remove(map, key, true); | 199 return cx_hash_map_get_remove(map, key, true); |
| 246 } | 200 } |
| 247 | 201 |
| 248 static void *cx_hash_map_iter_current_entry(CxIterator const *iter) { | 202 static void *cx_hash_map_iter_current_entry(CxIterator const *iter) { |
