dte test coverage


Directory: ./
File: src/util/hashmap.c
Date: 2025-07-19 20:13:10
Exec Total Coverage
Lines: 121 129 93.8%
Functions: 11 11 100.0%
Branches: 52 64 81.2%

Line Branch Exec Source
1 #include <errno.h>
2 #include <stdlib.h>
3 #include <string.h>
4 #include "hashmap.h"
5 #include "arith.h"
6 #include "bit.h"
7 #include "errorcode.h"
8 #include "hash.h"
9 #include "xstring.h"
10
11 enum {
12 MIN_CAPACITY = 8,
13 TOMBSTONE = 0xdead,
14 };
15
16 WARN_UNUSED_RESULT
17 497 static SystemErrno hashmap_resize(HashMap *map, size_t capacity)
18 {
19 497 BUG_ON(capacity < MIN_CAPACITY);
20 497 BUG_ON(capacity <= map->count);
21 497 BUG_ON(!IS_POWER_OF_2(capacity));
22
23 497 const size_t entrysize = sizeof(map->entries[0]);
24
1/2
✓ Branch 0 (8→9) taken 497 times.
✗ Branch 1 (8→21) not taken.
497 if (unlikely(calloc_args_have_ub_overflow(capacity, entrysize))) {
25 return EOVERFLOW;
26 }
27
28 497 HashMapEntry *newtab = calloc(capacity, entrysize); // NOLINT(*-unsafe-functions)
29
1/2
✓ Branch 0 (9→10) taken 497 times.
✗ Branch 1 (9→21) not taken.
497 if (unlikely(!newtab)) {
30 return ENOMEM;
31 }
32
33 497 HashMapEntry *oldtab = map->entries;
34 497 size_t oldlen = map->mask + 1;
35 497 map->entries = newtab;
36 497 map->mask = capacity - 1;
37 497 map->tombstones = 0;
38
39
2/2
✓ Branch 0 (10→11) taken 221 times.
✓ Branch 1 (10→21) taken 276 times.
497 if (!oldtab) {
40 return 0;
41 }
42
43 // Copy the entries to the new table
44
2/2
✓ Branch 0 (19→12) taken 19216 times.
✓ Branch 1 (19→20) taken 221 times.
19437 for (const HashMapEntry *e = oldtab, *end = e + oldlen; e < end; e++) {
45
2/2
✓ Branch 0 (12→13) taken 10990 times.
✓ Branch 1 (12→14) taken 8226 times.
19216 if (!e->key) {
46 10990 continue;
47 }
48 8226 HashMapEntry *newe;
49 9849 for (size_t i = e->hash, j = 1; ; i += j++) {
50 9849 newe = newtab + (i & map->mask);
51
2/2
✓ Branch 0 (15→16) taken 1623 times.
✓ Branch 1 (15→17) taken 8226 times.
9849 if (!newe->key) {
52 break;
53 }
54 }
55 8226 *newe = *e;
56 }
57
58 221 free(oldtab);
59 221 return 0;
60 }
61
62 WARN_UNUSED_RESULT
63 276 static SystemErrno hashmap_do_init(HashMap *map, size_t capacity)
64 {
65 // Accommodate the 75% load factor in the table size, to allow
66 // filling to the requested size without needing to resize()
67 276 capacity += capacity / 3;
68
69
2/2
✓ Branch 0 (2→3) taken 261 times.
✓ Branch 1 (2→4) taken 15 times.
276 if (unlikely(capacity < MIN_CAPACITY)) {
70 261 capacity = MIN_CAPACITY;
71 }
72
73 // Round up the size to the next power of 2, to allow using simple
74 // bitwise ops (instead of modulo) to wrap the hash value and also
75 // to allow quadratic probing with triangular numbers (`i += j++`
76 // in the `for` loops below)
77 276 capacity = next_pow2(capacity);
78
1/2
✓ Branch 0 (4→5) taken 276 times.
✗ Branch 1 (4→6) not taken.
276 if (unlikely(capacity == 0)) {
79 return EOVERFLOW;
80 }
81
82 276 return hashmap_resize(map, capacity);
83 }
84
85 16 void hashmap_init(HashMap *map, size_t capacity, HashMapFlags flags)
86 {
87 16 *map = (HashMap){.flags = flags};
88 16 SystemErrno err = hashmap_do_init(map, capacity);
89
1/2
✗ Branch 0 (3→4) not taken.
✓ Branch 1 (3→5) taken 16 times.
16 if (unlikely(err)) {
90 fatal_error(__func__, err);
91 }
92 16 }
93
94 42563 HashMapEntry *hashmap_find(const HashMap *map, const char *key)
95 {
96
2/2
✓ Branch 0 (2→3) taken 42211 times.
✓ Branch 1 (2→10) taken 352 times.
42563 if (unlikely(!map->entries)) {
97 return NULL;
98 }
99
100 42211 size_t hash = fnv_1a_hash(key, strlen(key));
101 42211 HashMapEntry *e;
102 78082 for (size_t i = hash, j = 1; ; i += j++) {
103 78082 e = map->entries + (i & map->mask);
104
2/2
✓ Branch 0 (4→5) taken 31271 times.
✓ Branch 1 (4→7) taken 46811 times.
78082 if (!e->key) {
105
2/2
✓ Branch 0 (5→6) taken 12182 times.
✓ Branch 1 (5→10) taken 19089 times.
31271 if (e->hash == TOMBSTONE) {
106 12182 continue;
107 }
108 return NULL;
109 }
110
3/4
✓ Branch 0 (7→8) taken 23122 times.
✓ Branch 1 (7→9) taken 23689 times.
✗ Branch 2 (8→9) not taken.
✓ Branch 3 (8→10) taken 23122 times.
46811 if (e->hash == hash && streq(e->key, key)) {
111 return e;
112 }
113 }
114
115 BUG("unexpected loop break");
116 }
117
118 15777 static void hashmap_free_key(const HashMap *map, char *key)
119 {
120
2/2
✓ Branch 0 (2→3) taken 15745 times.
✓ Branch 1 (2→4) taken 32 times.
15777 if (!(map->flags & HMAP_BORROWED_KEYS)) {
121 15745 free(key);
122 }
123 15777 }
124
125 11562 void *hashmap_remove(HashMap *map, const char *key)
126 {
127 11562 HashMapEntry *e = hashmap_find(map, key);
128
2/2
✓ Branch 0 (3→4) taken 11543 times.
✓ Branch 1 (3→6) taken 19 times.
11562 if (!e) {
129 return NULL;
130 }
131
132 11543 hashmap_free_key(map, e->key);
133 11543 e->key = NULL;
134 11543 e->hash = TOMBSTONE;
135 11543 map->count--;
136 11543 map->tombstones++;
137 11543 return e->value;
138 }
139
140 WARN_UNUSED_RESULT
141 15777 static SystemErrno hashmap_do_insert(HashMap *map, char *key, void *value, void **old_value)
142 {
143 15777 SystemErrno err = 0;
144
2/2
✓ Branch 0 (2→3) taken 260 times.
✓ Branch 1 (2→5) taken 15517 times.
15777 if (unlikely(!map->entries)) {
145 260 err = hashmap_do_init(map, 0);
146
1/2
✓ Branch 0 (4→5) taken 260 times.
✗ Branch 1 (4→31) not taken.
260 if (unlikely(err)) {
147 return err;
148 }
149 }
150
151 15777 size_t hash = fnv_1a_hash(key, strlen(key));
152 15777 bool replacing_tombstone_or_existing_value = false;
153 15777 HashMapEntry *e;
154 23338 for (size_t i = hash, j = 1; ; i += j++) {
155 23338 e = map->entries + (i & map->mask);
156
2/2
✓ Branch 0 (6→7) taken 15776 times.
✓ Branch 1 (6→11) taken 7562 times.
23338 if (!e->key) {
157
2/2
✓ Branch 0 (7→8) taken 4770 times.
✓ Branch 1 (7→20) taken 11006 times.
15776 if (e->hash == TOMBSTONE) {
158 4770 replacing_tombstone_or_existing_value = true;
159 4770 BUG_ON(map->tombstones == 0);
160 4770 map->tombstones--;
161 }
162 break;
163 }
164
3/4
✓ Branch 0 (11→12) taken 1 times.
✓ Branch 1 (11→19) taken 7561 times.
✓ Branch 2 (12→13) taken 1 times.
✗ Branch 3 (12→19) not taken.
7562 if (unlikely(e->hash == hash && streq(e->key, key))) {
165 1 replacing_tombstone_or_existing_value = true;
166 // When a caller passes NULL as the "old_value" return param,
167 // it implies there can be no existing entry with the same key
168 // as the one to be inserted.
169 1 BUG_ON(!old_value);
170 1 BUG_ON(!e->value);
171 1 *old_value = e->value;
172 1 hashmap_free_key(map, key);
173 1 key = e->key;
174 1 map->count--;
175 1 break;
176 }
177 }
178
179 15777 const size_t max_load = map->mask - (map->mask / 4);
180 15777 e->key = key;
181 15777 e->value = value;
182 15777 e->hash = hash;
183 15777 map->count++;
184
185
2/2
✓ Branch 0 (20→21) taken 221 times.
✓ Branch 1 (20→31) taken 15556 times.
15777 if (unlikely(map->count + map->tombstones > max_load)) {
186 221 BUG_ON(replacing_tombstone_or_existing_value);
187 221 size_t new_size = map->mask + 1;
188
3/4
✓ Branch 0 (23→24) taken 6 times.
✓ Branch 1 (23→25) taken 215 times.
✗ Branch 2 (24→25) not taken.
✓ Branch 3 (24→27) taken 6 times.
221 if (map->count > map->tombstones || new_size <= 256) {
189 // Only increase the size of the table when the number of
190 // real entries is higher than the number of tombstones.
191 // If the number of real entries is lower, the table is
192 // most likely being filled with tombstones from repeated
193 // insert/remove churn; so we just rehash at the same size
194 // to clean out the tombstones.
195 215 new_size <<= 1;
196
1/2
✗ Branch 0 (25→26) not taken.
✓ Branch 1 (25→27) taken 215 times.
215 if (unlikely(new_size == 0)) {
197 err = EOVERFLOW;
198 goto error;
199 }
200 }
201 221 err = hashmap_resize(map, new_size);
202
1/2
✗ Branch 0 (28→29) not taken.
✓ Branch 1 (28→31) taken 221 times.
221 if (unlikely(err)) {
203 goto error;
204 }
205 }
206
207 return 0;
208
209 error:
210 map->count--;
211 e->key = NULL;
212 e->hash = 0;
213 return err;
214 }
215
216 15485 void *hashmap_insert(HashMap *map, char *key, void *value)
217 {
218 15485 SystemErrno err = hashmap_do_insert(map, key, value, NULL);
219
1/2
✗ Branch 0 (3→4) not taken.
✓ Branch 1 (3→5) taken 15485 times.
15485 if (unlikely(err)) {
220 fatal_error(__func__, err);
221 }
222 15485 return value;
223 }
224
225 292 void *hashmap_insert_or_replace(HashMap *map, char *key, void *value)
226 {
227 292 void *replaced_value = NULL;
228 292 SystemErrno err = hashmap_do_insert(map, key, value, &replaced_value);
229
1/2
✗ Branch 0 (3→4) not taken.
✓ Branch 1 (3→5) taken 292 times.
292 if (unlikely(err)) {
230 fatal_error(__func__, err);
231 }
232 292 return replaced_value;
233 }
234
235 // Remove all entries without freeing the table
236 583 void hashmap_clear(HashMap *map, FreeFunction free_value)
237 {
238
2/2
✓ Branch 0 (2→3) taken 276 times.
✓ Branch 1 (2→13) taken 307 times.
583 if (unlikely(!map->entries)) {
239 return;
240 }
241
242 276 size_t count = 0;
243
2/2
✓ Branch 0 (9→4) taken 4233 times.
✓ Branch 1 (9→10) taken 276 times.
4509 for (HashMapIter it = hashmap_iter(map); hashmap_next(&it); count++) {
244 4233 hashmap_free_key(map, it.entry->key);
245
2/2
✓ Branch 0 (5→6) taken 3774 times.
✓ Branch 1 (5→7) taken 459 times.
4233 if (free_value) {
246 3774 do_free_value(free_value, it.entry->value);
247 }
248 }
249
250 276 BUG_ON(count != map->count);
251 276 size_t len = map->mask + 1;
252 276 map->count = 0;
253 276 memset(map->entries, 0, len * sizeof(*map->entries));
254 }
255
256 565 void hashmap_free(HashMap *map, FreeFunction free_value)
257 {
258 565 hashmap_clear(map, free_value);
259 565 free(map->entries);
260 565 *map = (HashMap){.flags = map->flags};
261 565 }
262