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 */
28
29 #include "cx/hash_map.h"
30
31 #include <string.h>
32 #include <assert.h>
33 #include <errno.h>
34
35 struct cx_hash_map_element_s {
36 /** A pointer to the next element in the current bucket. */
37 struct cx_hash_map_element_s *next;
38
39 /** The corresponding key. */
40 CxHashKey key;
41
42 /** The value data. */
43 char data[];
44 };
45
46 static void cx_hash_map_clear(struct cx_map_s *map) {
47 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
48 for (size_t i = 0; i < hash_map->bucket_count; i++) {
49 struct cx_hash_map_element_s *elem = hash_map->buckets[i];
50 if (elem != NULL) {
51 do {
52 struct cx_hash_map_element_s *next = elem->next;
53 // invoke the destructor
54 cx_invoke_destructor(map, elem->data);
55 // free the key data
56 cxFree(map->collection.allocator, (void *) elem->key.data);
57 // free the node
58 cxFree(map->collection.allocator, elem);
59 // proceed
60 elem = next;
61 } while (elem != NULL);
62
63 // do not leave a dangling pointer
64 hash_map->buckets[i] = NULL;
65 }
66 }
67 map->collection.size = 0;
68 }
69
70 static void cx_hash_map_destructor(struct cx_map_s *map) {
71 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
72
73 // free the buckets
74 cx_hash_map_clear(map);
75 cxFree(map->collection.allocator, hash_map->buckets);
76
77 // free the map structure
78 cxFree(map->collection.allocator, map);
79 }
80
81 static void *cx_hash_map_put(
82 CxMap *map,
83 CxHashKey key,
84 void *value
85 ) {
86 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
87 const CxAllocator *allocator = map->collection.allocator;
88
89 uint64_t hash = key.hash;
90 if (hash == 0) {
91 cx_hash_murmur(&key);
92 hash = key.hash;
93 }
94
95 size_t slot = hash % hash_map->bucket_count;
96 struct cx_hash_map_element_s *elm = hash_map->buckets[slot];
97 struct cx_hash_map_element_s *prev = NULL;
98
99 while (elm != NULL && elm->key.hash < hash) {
100 prev = elm;
101 elm = elm->next;
102 }
103
104 if (elm != NULL && cx_hash_key_cmp(&elm->key, &key) == 0) {
105 // overwrite existing element, but call destructors first
106 cx_invoke_destructor(map, elm->data);
107 if (value == NULL) {
108 memset(elm->data, 0, map->collection.elem_size);
109 } else if (map->collection.store_pointer) {
110 memcpy(elm->data, &value, sizeof(void *));
111 } else {
112 memcpy(elm->data, value, map->collection.elem_size);
113 }
114 } else {
115 // allocate new element
116 struct cx_hash_map_element_s *e = cxMalloc(
117 allocator,
118 sizeof(struct cx_hash_map_element_s) + map->collection.elem_size
119 );
120 if (e == NULL) return NULL; // LCOV_EXCL_LINE
121
122 // write the value
123 if (value == NULL) {
124 memset(e->data, 0, map->collection.elem_size);
125 } else if (map->collection.store_pointer) {
126 memcpy(e->data, &value, sizeof(void *));
127 } else {
128 memcpy(e->data, value, map->collection.elem_size);
129 }
130
131 // copy the key
132 void *kd = cxMalloc(allocator, key.len);
133 if (kd == NULL) { // LCOV_EXCL_START
134 cxFree(allocator, e);
135 return NULL;
136 } // LCOV_EXCL_STOP
137 memcpy(kd, key.data, key.len);
138 e->key.data = kd;
139 e->key.len = key.len;
140 e->key.hash = hash;
141
142 // insert the element into the linked list
143 if (prev == NULL) {
144 hash_map->buckets[slot] = e;
145 } else {
146 prev->next = e;
147 }
148 e->next = elm;
149 elm = e;
150
151 // increase the size
152 map->collection.size++;
153 }
154
155 // return pointer to the element
156 return elm->data;
157 }
158
159 static void cx_hash_map_unlink(
160 struct cx_hash_map_s *hash_map,
161 size_t slot,
162 struct cx_hash_map_element_s *prev,
163 struct cx_hash_map_element_s *elm
164 ) {
165 // unlink
166 if (prev == NULL) {
167 hash_map->buckets[slot] = elm->next;
168 } else {
169 prev->next = elm->next;
170 }
171 // free element
172 cxFree(hash_map->base.collection.allocator, (void *) elm->key.data);
173 cxFree(hash_map->base.collection.allocator, elm);
174 // decrease size
175 hash_map->base.collection.size--;
176 }
177
178 /**
179 * Helper function to avoid code duplication.
180 *
181 * If @p remove is true, and @p targetbuf is @c NULL, the element
182 * will be destroyed when found.
183 *
184 * If @p remove is true, and @p targetbuf is set, the element will
185 * be copied to that buffer and no destructor function is called.
186 *
187 * If @p remove is false, @p targetbuf must not be non-null and
188 * either the pointer, when the map is storing pointers, is copied
189 * to the target buffer, or a pointer to the stored object will
190 * be copied to the target buffer.
191 *
192 * @param map the map
193 * @param key the key to look up
194 * @param targetbuf see description
195 * @param remove flag indicating whether the looked up entry shall be removed
196 * @return zero, if the key was found, non-zero otherwise
197 */
198 static int cx_hash_map_get_remove(
199 CxMap *map,
200 CxHashKey key,
201 void *targetbuf,
202 bool remove
203 ) {
204 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
205
206 uint64_t hash = key.hash;
207 if (hash == 0) {
208 cx_hash_murmur(&key);
209 hash = key.hash;
210 }
211
212 size_t slot = hash % hash_map->bucket_count;
213 struct cx_hash_map_element_s *elm = hash_map->buckets[slot];
214 struct cx_hash_map_element_s *prev = NULL;
215 while (elm && elm->key.hash <= hash) {
216 if (cx_hash_key_cmp(&elm->key, &key) == 0) {
217 if (remove) {
218 if (targetbuf == NULL) {
219 cx_invoke_destructor(map, elm->data);
220 } else {
221 memcpy(targetbuf, elm->data, map->collection.elem_size);
222 }
223 cx_hash_map_unlink(hash_map, slot, prev, elm);
224 } else {
225 assert(targetbuf != NULL);
226 void *data = NULL;
227 if (map->collection.store_pointer) {
228 data = *(void **) elm->data;
229 } else {
230 data = elm->data;
231 }
232 memcpy(targetbuf, &data, sizeof(void *));
233 }
234 return 0;
235 }
236 prev = elm;
237 elm = prev->next;
238 }
239
240 return 1;
241 }
242
243 static void *cx_hash_map_get(
244 const CxMap *map,
245 CxHashKey key
246 ) {
247 // we can safely cast, because we know the map stays untouched
248 void *ptr = NULL;
249 int found = cx_hash_map_get_remove((CxMap *) map, key, &ptr, false);
250 return found == 0 ? ptr : NULL;
251 }
252
253 static int cx_hash_map_remove(
254 CxMap *map,
255 CxHashKey key,
256 void *targetbuf
257 ) {
258 return cx_hash_map_get_remove(map, key, targetbuf, true);
259 }
260
261 static void *cx_hash_map_iter_current_entry(const void *it) {
262 const CxMapIterator *iter = it;
263 // we have to cast away const, because of the signature
264 return (void*) &iter->entry;
265 }
266
267 static void *cx_hash_map_iter_current_key(const void *it) {
268 const CxMapIterator *iter = it;
269 return (void*) iter->entry.key;
270 }
271
272 static void *cx_hash_map_iter_current_value(const void *it) {
273 const CxMapIterator *iter = it;
274 return iter->entry.value;
275 }
276
277 static bool cx_hash_map_iter_valid(const void *it) {
278 const CxMapIterator *iter = it;
279 return iter->elem != NULL;
280 }
281
282 static void cx_hash_map_iter_next(void *it) {
283 CxMapIterator *iter = it;
284 CxMap *map = iter->map;
285 struct cx_hash_map_s *hmap = (struct cx_hash_map_s *) map;
286 struct cx_hash_map_element_s *elm = iter->elem;
287
288 // remove current element, if asked
289 if (iter->base.remove) {
290
291 // clear the flag
292 iter->base.remove = false;
293
294 // determine the next element
295 struct cx_hash_map_element_s *next = elm->next;
296
297 // search the previous element
298 struct cx_hash_map_element_s *prev = NULL;
299 if (hmap->buckets[iter->slot] != elm) {
300 prev = hmap->buckets[iter->slot];
301 while (prev->next != elm) {
302 prev = prev->next;
303 }
304 }
305
306 // destroy
307 cx_invoke_destructor(map, elm->data);
308
309 // unlink
310 cx_hash_map_unlink(hmap, iter->slot, prev, elm);
311 iter->elem_count--;
312
313 // advance
314 elm = next;
315 } else {
316 // just advance
317 elm = elm->next;
318 iter->index++;
319 }
320
321 // search the next bucket, if required
322 while (elm == NULL && ++iter->slot < hmap->bucket_count) {
323 elm = hmap->buckets[iter->slot];
324 }
325 iter->elem = elm;
326
327 // copy data to a location where the iterator can point to
328 // we need to do it here, because the iterator function call
329 // must not modify the iterator (the parameter is const)
330 if (elm != NULL) {
331 iter->entry.key = &elm->key;
332 if (map->collection.store_pointer) {
333 iter->entry.value = *(void **) elm->data;
334 } else {
335 iter->entry.value = elm->data;
336 }
337 }
338 }
339
340 static CxMapIterator cx_hash_map_iterator(
341 const CxMap *map,
342 enum cx_map_iterator_type type
343 ) {
344 CxMapIterator iter;
345
346 iter.map = (CxMap*) map;
347 iter.elem_count = map->collection.size;
348
349 switch (type) {
350 case CX_MAP_ITERATOR_PAIRS:
351 iter.elem_size = sizeof(CxMapEntry);
352 iter.base.current = cx_hash_map_iter_current_entry;
353 break;
354 case CX_MAP_ITERATOR_KEYS:
355 iter.elem_size = sizeof(CxHashKey);
356 iter.base.current = cx_hash_map_iter_current_key;
357 break;
358 case CX_MAP_ITERATOR_VALUES:
359 iter.elem_size = map->collection.elem_size;
360 iter.base.current = cx_hash_map_iter_current_value;
361 break;
362 default:
363 assert(false); // LCOV_EXCL_LINE
364 }
365
366 iter.base.valid = cx_hash_map_iter_valid;
367 iter.base.next = cx_hash_map_iter_next;
368 iter.base.remove = false;
369 iter.base.allow_remove = true;
370
371 iter.slot = 0;
372 iter.index = 0;
373
374 if (map->collection.size > 0) {
375 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
376 struct cx_hash_map_element_s *elm = hash_map->buckets[0];
377 while (elm == NULL) {
378 elm = hash_map->buckets[++iter.slot];
379 }
380 iter.elem = elm;
381 iter.entry.key = &elm->key;
382 if (map->collection.store_pointer) {
383 iter.entry.value = *(void **) elm->data;
384 } else {
385 iter.entry.value = elm->data;
386 }
387 } else {
388 iter.elem = NULL;
389 }
390
391 return iter;
392 }
393
394 static cx_map_class cx_hash_map_class = {
395 cx_hash_map_destructor,
396 cx_hash_map_clear,
397 cx_hash_map_put,
398 cx_hash_map_get,
399 cx_hash_map_remove,
400 cx_hash_map_iterator,
401 };
402
403 CxMap *cxHashMapCreate(
404 const CxAllocator *allocator,
405 size_t itemsize,
406 size_t buckets
407 ) {
408 if (allocator == NULL) {
409 allocator = cxDefaultAllocator;
410 }
411
412 if (buckets == 0) {
413 // implementation defined default
414 buckets = 16;
415 }
416
417 struct cx_hash_map_s *map = cxCalloc(allocator, 1,
418 sizeof(struct cx_hash_map_s));
419 if (map == NULL) return NULL;
420
421 // initialize hash map members
422 map->bucket_count = buckets;
423 map->buckets = cxCalloc(allocator, buckets,
424 sizeof(struct cx_hash_map_element_s *));
425 if (map->buckets == NULL) { // LCOV_EXCL_START
426 cxFree(allocator, map);
427 return NULL;
428 } // LCOV_EXCL_STOP
429
430 // initialize base members
431 map->base.cl = &cx_hash_map_class;
432 map->base.collection.allocator = allocator;
433
434 if (itemsize > 0) {
435 map->base.collection.elem_size = itemsize;
436 } else {
437 map->base.collection.elem_size = sizeof(void *);
438 map->base.collection.store_pointer = true;
439 }
440
441 return (CxMap *) map;
442 }
443
444 int cxMapRehash(CxMap *map) {
445 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
446 if (map->collection.size > ((hash_map->bucket_count * 3) >> 2)) {
447
448 size_t new_bucket_count = (map->collection.size * 5) >> 1;
449 if (new_bucket_count < hash_map->bucket_count) {
450 // LCOV_EXCL_START
451 errno = EOVERFLOW;
452 return 1;
453 } // LCOV_EXCL_STOP
454 struct cx_hash_map_element_s **new_buckets = cxCalloc(
455 map->collection.allocator,
456 new_bucket_count, sizeof(struct cx_hash_map_element_s *)
457 );
458
459 if (new_buckets == NULL) return 1; // LCOV_EXCL_LINE
460
461 // iterate through the elements and assign them to their new slots
462 for (size_t slot = 0; slot < hash_map->bucket_count; slot++) {
463 struct cx_hash_map_element_s *elm = hash_map->buckets[slot];
464 while (elm != NULL) {
465 struct cx_hash_map_element_s *next = elm->next;
466 size_t new_slot = elm->key.hash % new_bucket_count;
467
468 // find position where to insert
469 struct cx_hash_map_element_s *bucket_next = new_buckets[new_slot];
470 struct cx_hash_map_element_s *bucket_prev = NULL;
471 while (bucket_next != NULL &&
472 bucket_next->key.hash < elm->key.hash) {
473 bucket_prev = bucket_next;
474 bucket_next = bucket_next->next;
475 }
476
477 // insert
478 if (bucket_prev == NULL) {
479 elm->next = new_buckets[new_slot];
480 new_buckets[new_slot] = elm;
481 } else {
482 bucket_prev->next = elm;
483 elm->next = bucket_next;
484 }
485
486 // advance
487 elm = next;
488 }
489 }
490
491 // assign result to the map
492 hash_map->bucket_count = new_bucket_count;
493 cxFree(map->collection.allocator, hash_map->buckets);
494 hash_map->buckets = new_buckets;
495 }
496 return 0;
497 }
498