GCC Code Coverage Report

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