Sat, 21 May 2022 11:22:47 +0200
#189 implement map iterators
1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
3 *
4 * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 *
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 */
29 #include <errno.h>
30 #include <string.h>
31 #include "cx/hash_map.h"
32 #include "cx/utils.h"
34 /**
35 * Computes a murmur hash-2.
36 *
37 * @param data the data to hash
38 * @param len the length of the data
39 * @return the murmur hash-2 of the data
40 */
41 static unsigned cx_hash_map_murmur(
42 unsigned char const *data,
43 size_t len
44 ) {
45 unsigned m = 0x5bd1e995;
46 unsigned r = 24;
47 unsigned h = 25 ^ len;
48 unsigned i = 0;
49 while (len >= 4) {
50 unsigned k = data[i + 0] & 0xFF;
51 k |= (data[i + 1] & 0xFF) << 8;
52 k |= (data[i + 2] & 0xFF) << 16;
53 k |= (data[i + 3] & 0xFF) << 24;
55 k *= m;
56 k ^= k >> r;
57 k *= m;
59 h *= m;
60 h ^= k;
62 i += 4;
63 len -= 4;
64 }
66 switch (len) {
67 case 3:
68 h ^= (data[i + 2] & 0xFF) << 16;
69 __attribute__((__fallthrough__));
70 case 2:
71 h ^= (data[i + 1] & 0xFF) << 8;
72 __attribute__((__fallthrough__));
73 case 1:
74 h ^= (data[i + 0] & 0xFF);
75 h *= m;
76 __attribute__((__fallthrough__));
77 default:
78 /* do nothing */;
79 }
81 h ^= h >> 13;
82 h *= m;
83 h ^= h >> 15;
85 return h;
86 }
88 static void cx_hash_map_clear(struct cx_map_s *map) {
89 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
90 cx_for_n(i, hash_map->bucket_count) {
91 struct cx_hash_map_element_s *elem = hash_map->buckets[i];
92 if (elem != NULL) {
93 do {
94 struct cx_hash_map_element_s *next = elem->next;
95 // free the key data
96 cxFree(map->allocator, elem->key.data);
97 // free the node
98 cxFree(map->allocator, elem);
99 // proceed
100 elem = next;
101 } while (elem != NULL);
103 // do not leave a dangling pointer
104 hash_map->buckets[i] = NULL;
105 }
106 }
107 map->size = 0;
108 }
110 static void cx_hash_map_destructor(struct cx_map_s *map) {
111 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
113 // free the buckets
114 cx_hash_map_clear(map);
115 cxFree(map->allocator, hash_map->buckets);
117 // free the map structure
118 cxFree(map->allocator, map);
119 }
121 static int cx_hash_map_put(
122 CxMap *map,
123 CxDataPtr key,
124 void *value
125 ) {
126 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
127 CxAllocator *allocator = map->allocator;
129 unsigned hash = cx_hash_map_murmur(key.data, key.len);
131 size_t slot = hash % hash_map->bucket_count;
132 struct cx_hash_map_element_s *elm = hash_map->buckets[slot];
133 struct cx_hash_map_element_s *prev = NULL;
135 while (elm != NULL && elm->key.hash < hash) {
136 prev = elm;
137 elm = elm->next;
138 }
140 if (elm == NULL || elm->key.hash != hash) {
141 struct cx_hash_map_element_s *e = cxMalloc(allocator, sizeof(struct cx_hash_map_element_s));
142 if (e == NULL) {
143 return -1;
144 }
146 // write the value
147 // TODO: depending on future map features, we may want to copy here
148 e->data = value;
150 // copy the key
151 void *kd = cxMalloc(allocator, key.len);
152 if (kd == NULL) {
153 return -1;
154 }
155 memcpy(kd, key.data, key.len);
156 e->key.data = kd;
157 e->key.len = key.len;
158 e->key.hash = hash;
160 // insert the element into the linked list
161 if (prev == NULL) {
162 hash_map->buckets[slot] = e;
163 } else {
164 prev->next = e;
165 }
166 e->next = elm;
168 // increase the size
169 map->size++;
170 } else {
171 // (elem != NULL && elem->key.hash == hash) - overwrite value of existing element
172 elm->data = value;
173 }
175 return 0;
176 }
178 static void cx_hash_map_unlink(
179 struct cx_hash_map_s *hash_map,
180 size_t slot,
181 struct cx_hash_map_element_s *prev,
182 struct cx_hash_map_element_s *elm
183 ) {
184 // unlink
185 if (prev == NULL) {
186 hash_map->buckets[slot] = elm->next;
187 } else {
188 prev->next = elm->next;
189 }
190 // free element
191 cxFree(hash_map->base.allocator, elm->key.data);
192 cxFree(hash_map->base.allocator, elm);
193 // decrease size
194 hash_map->base.size--;
195 }
197 /**
198 * Helper function to avoid code duplication.
199 *
200 * @param map the map
201 * @param key the key to look up
202 * @param remove flag indicating whether the looked up entry shall be removed
203 * @return the value corresponding to the key or \c NULL
204 */
205 static void *cx_hash_map_get_remove(
206 CxMap *map,
207 CxDataPtr key,
208 bool remove
209 ) {
210 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
212 unsigned hash = cx_hash_map_murmur(key.data, key.len);
214 size_t slot = hash % hash_map->bucket_count;
215 struct cx_hash_map_element_s *elm = hash_map->buckets[slot];
216 struct cx_hash_map_element_s *prev = NULL;
217 while (elm && elm->key.hash <= hash) {
218 if (elm->key.hash == hash && elm->key.len == key.len) {
219 if (memcmp(elm->key.data, key.data, key.len) == 0) {
220 void *data = elm->data;
221 if (remove) {
222 cx_hash_map_unlink(hash_map, slot, prev, elm);
223 }
224 return data;
225 }
226 }
227 prev = elm;
228 elm = prev->next;
229 }
231 return NULL;
232 }
234 static void *cx_hash_map_get(
235 CxMap const *map,
236 CxDataPtr key
237 ) {
238 // we can safely cast, because we know when remove=false, the map stays untouched
239 return cx_hash_map_get_remove((CxMap *) map, key, false);
240 }
242 static void *cx_hash_map_remove(
243 CxMap *map,
244 CxDataPtr key
245 ) {
246 return cx_hash_map_get_remove(map, key, true);
247 }
249 static void *cx_hash_map_iter_current_entry(CxIterator const *iter) {
250 // struct has to have a compatible signature
251 struct cx_map_entry_s *entry = (struct cx_map_entry_s *) &(iter->kv_data);
252 return entry;
253 }
255 static void *cx_hash_map_iter_current_key(CxIterator const *iter) {
256 struct cx_hash_map_element_s *elm = iter->elem_handle;
257 return &elm->key;
258 }
260 static void *cx_hash_map_iter_current_value(CxIterator const *iter) {
261 struct cx_hash_map_element_s *elm = iter->elem_handle;
262 // TODO: return a pointer to data if this map is storing copies
263 return elm->data;
264 }
266 static bool cx_hash_map_iter_valid(CxIterator const *iter) {
267 return iter->elem_handle != NULL;
268 }
270 static void cx_hash_map_iter_next(CxIterator *iter) {
271 struct cx_hash_map_s *map = iter->src_handle;
272 struct cx_hash_map_element_s *elm = iter->elem_handle;
274 // remove current element, if asked
275 if (iter->remove) {
276 // clear the flag
277 iter->remove = false;
279 // determine the next element
280 struct cx_hash_map_element_s *next = elm->next;
282 // search the previous element
283 struct cx_hash_map_element_s *prev = NULL;
284 if (map->buckets[iter->slot] != elm) {
285 prev = map->buckets[iter->slot];
286 while (prev->next != elm) {
287 prev = prev->next;
288 }
289 }
291 // unlink
292 cx_hash_map_unlink(map, iter->slot, prev, elm);
294 // advance
295 elm = next;
296 } else {
297 // just advance
298 elm = elm->next;
299 }
301 // do we leave the bucket?
302 if (elm == NULL) {
303 // search the next bucket
304 for (; elm == NULL && iter->slot < map->bucket_count; iter->slot++) {
305 elm = map->buckets[iter->slot];
306 }
307 }
309 // advance the index in any case
310 iter->index++;
312 // fill the struct with the current element
313 iter->elem_handle = elm;
314 if (elm == NULL) {
315 iter->kv_data.key = NULL;
316 iter->kv_data.value = NULL;
317 } else {
318 iter->kv_data.key = &elm->key;
319 // TODO: pointer to data if this map is storing copies
320 iter->kv_data.value = elm->data;
321 }
322 }
324 static CxIterator cx_hash_map_iterator(CxMap *map) {
325 CxIterator iter;
327 iter.src_handle = map;
328 iter.valid = cx_hash_map_iter_valid;
329 iter.next = cx_hash_map_iter_next;
330 iter.current = cx_hash_map_iter_current_entry;
332 iter.slot = 0;
333 iter.index = 0;
334 iter.remove = false;
336 if (map->size > 0) {
337 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
338 struct cx_hash_map_element_s *elem = NULL;
339 for (; elem == NULL; iter.slot++) {
340 elem = hash_map->buckets[iter.slot];
341 }
342 iter.elem_handle = elem;
343 iter.kv_data.key = NULL;
344 iter.kv_data.value = NULL;
345 } else {
346 iter.elem_handle = NULL;
347 iter.kv_data.key = NULL;
348 iter.kv_data.value = NULL;
349 }
351 return iter;
352 }
354 static CxIterator cx_hash_map_iterator_keys(CxMap *map) {
355 CxIterator iter = cx_hash_map_iterator(map);
356 iter.current = cx_hash_map_iter_current_key;
357 return iter;
358 }
360 static CxIterator cx_hash_map_iterator_values(CxMap *map) {
361 CxIterator iter = cx_hash_map_iterator(map);
362 iter.current = cx_hash_map_iter_current_value;
363 return iter;
364 }
366 static cx_map_class cx_hash_map_class = {
367 cx_hash_map_destructor,
368 cx_hash_map_clear,
369 cx_hash_map_put,
370 cx_hash_map_get,
371 cx_hash_map_remove,
372 cx_hash_map_iterator,
373 cx_hash_map_iterator_keys,
374 cx_hash_map_iterator_values,
375 };
377 CxMap *cxHashMapCreate(
378 CxAllocator *allocator,
379 size_t buckets
380 ) {
381 if (buckets == 0) {
382 // implementation defined default
383 buckets = 16;
384 }
386 struct cx_hash_map_s *map = cxMalloc(allocator, sizeof(struct cx_hash_map_s));
387 if (map == NULL) return NULL;
389 // initialize hash map members
390 map->bucket_count = buckets;
391 map->buckets = cxCalloc(allocator, buckets, sizeof(struct cx_hash_map_element_s *));
392 if (map->buckets == NULL) {
393 cxFree(allocator, map);
394 return NULL;
395 }
397 // initialize base members
398 map->base.cl = &cx_hash_map_class;
399 map->base.allocator = allocator;
400 map->base.size = 0;
402 return (CxMap *) map;
403 }