dte test coverage


Directory: ./
File: src/util/hashmap.c
Date: 2025-09-07 23:01:39
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 9848 for (size_t i = e->hash, j = 1; ; i += j++) {
50 9848 newe = newtab + (i & map->mask);
51
2/2
✓ Branch 0 (15→16) taken 1622 times.
✓ Branch 1 (15→17) taken 8226 times.
9848 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 FATAL_ERROR_ON(err, err);
90 16 }
91
92 42563 HashMapEntry *hashmap_find(const HashMap *map, const char *key)
93 {
94
2/2
✓ Branch 0 (2→3) taken 42211 times.
✓ Branch 1 (2→10) taken 352 times.
42563 if (unlikely(!map->entries)) {
95 return NULL;
96 }
97
98 42211 size_t hash = fnv_1a_hash(key, strlen(key));
99 42211 HashMapEntry *e;
100 78078 for (size_t i = hash, j = 1; ; i += j++) {
101 78078 e = map->entries + (i & map->mask);
102
2/2
✓ Branch 0 (4→5) taken 31273 times.
✓ Branch 1 (4→7) taken 46805 times.
78078 if (!e->key) {
103
2/2
✓ Branch 0 (5→6) taken 12182 times.
✓ Branch 1 (5→10) taken 19091 times.
31273 if (e->hash == TOMBSTONE) {
104 12182 continue;
105 }
106 return NULL;
107 }
108
3/4
✓ Branch 0 (7→8) taken 23120 times.
✓ Branch 1 (7→9) taken 23685 times.
✗ Branch 2 (8→9) not taken.
✓ Branch 3 (8→10) taken 23120 times.
46805 if (e->hash == hash && streq(e->key, key)) {
109 return e;
110 }
111 }
112
113 BUG("unexpected loop break");
114 }
115
116 15780 static void hashmap_free_key(const HashMap *map, char *key)
117 {
118
2/2
✓ Branch 0 (2→3) taken 15745 times.
✓ Branch 1 (2→4) taken 35 times.
15780 if (!(map->flags & HMAP_BORROWED_KEYS)) {
119 15745 free(key);
120 }
121 15780 }
122
123 11562 void *hashmap_remove(HashMap *map, const char *key)
124 {
125 11562 HashMapEntry *e = hashmap_find(map, key);
126
2/2
✓ Branch 0 (3→4) taken 11543 times.
✓ Branch 1 (3→6) taken 19 times.
11562 if (!e) {
127 return NULL;
128 }
129
130 11543 hashmap_free_key(map, e->key);
131 11543 e->key = NULL;
132 11543 e->hash = TOMBSTONE;
133 11543 map->count--;
134 11543 map->tombstones++;
135 11543 return e->value;
136 }
137
138 WARN_UNUSED_RESULT
139 15780 static SystemErrno hashmap_do_insert(HashMap *map, char *key, void *value, void **old_value)
140 {
141 15780 SystemErrno err = 0;
142
2/2
✓ Branch 0 (2→3) taken 260 times.
✓ Branch 1 (2→5) taken 15520 times.
15780 if (unlikely(!map->entries)) {
143 260 err = hashmap_do_init(map, 0);
144
1/2
✓ Branch 0 (4→5) taken 260 times.
✗ Branch 1 (4→31) not taken.
260 if (unlikely(err)) {
145 return err;
146 }
147 }
148
149 15780 size_t hash = fnv_1a_hash(key, strlen(key));
150 15780 bool replacing_tombstone_or_existing_value = false;
151 15780 HashMapEntry *e;
152 23339 for (size_t i = hash, j = 1; ; i += j++) {
153 23339 e = map->entries + (i & map->mask);
154
2/2
✓ Branch 0 (6→7) taken 15779 times.
✓ Branch 1 (6→11) taken 7560 times.
23339 if (!e->key) {
155
2/2
✓ Branch 0 (7→8) taken 4770 times.
✓ Branch 1 (7→20) taken 11009 times.
15779 if (e->hash == TOMBSTONE) {
156 4770 replacing_tombstone_or_existing_value = true;
157 4770 BUG_ON(map->tombstones == 0);
158 4770 map->tombstones--;
159 }
160 break;
161 }
162
3/4
✓ Branch 0 (11→12) taken 1 times.
✓ Branch 1 (11→19) taken 7559 times.
✓ Branch 2 (12→13) taken 1 times.
✗ Branch 3 (12→19) not taken.
7560 if (unlikely(e->hash == hash && streq(e->key, key))) {
163 1 replacing_tombstone_or_existing_value = true;
164 // When a caller passes NULL as the "old_value" return param,
165 // it implies there can be no existing entry with the same key
166 // as the one to be inserted.
167 1 BUG_ON(!old_value);
168 1 BUG_ON(!e->value);
169 1 *old_value = e->value;
170 1 hashmap_free_key(map, key);
171 1 key = e->key;
172 1 map->count--;
173 1 break;
174 }
175 }
176
177 15780 const size_t max_load = map->mask - (map->mask / 4);
178 15780 e->key = key;
179 15780 e->value = value;
180 15780 e->hash = hash;
181 15780 map->count++;
182
183
2/2
✓ Branch 0 (20→21) taken 221 times.
✓ Branch 1 (20→31) taken 15559 times.
15780 if (unlikely(map->count + map->tombstones > max_load)) {
184 221 BUG_ON(replacing_tombstone_or_existing_value);
185 221 size_t new_size = map->mask + 1;
186
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) {
187 // Only increase the size of the table when the number of
188 // real entries is higher than the number of tombstones.
189 // If the number of real entries is lower, the table is
190 // most likely being filled with tombstones from repeated
191 // insert/remove churn; so we just rehash at the same size
192 // to clean out the tombstones.
193 215 new_size <<= 1;
194
1/2
✗ Branch 0 (25→26) not taken.
✓ Branch 1 (25→27) taken 215 times.
215 if (unlikely(new_size == 0)) {
195 err = EOVERFLOW;
196 goto error;
197 }
198 }
199 221 err = hashmap_resize(map, new_size);
200
1/2
✗ Branch 0 (28→29) not taken.
✓ Branch 1 (28→31) taken 221 times.
221 if (unlikely(err)) {
201 goto error;
202 }
203 }
204
205 return 0;
206
207 error:
208 map->count--;
209 e->key = NULL;
210 e->hash = 0;
211 return err;
212 }
213
214 15488 void *hashmap_insert(HashMap *map, char *key, void *value)
215 {
216 15488 SystemErrno err = hashmap_do_insert(map, key, value, NULL);
217
1/2
✗ Branch 0 (3→4) not taken.
✓ Branch 1 (3→5) taken 15488 times.
15488 FATAL_ERROR_ON(err, err);
218 15488 return value;
219 }
220
221 292 void *hashmap_insert_or_replace(HashMap *map, char *key, void *value)
222 {
223 292 void *replaced_value = NULL;
224 292 SystemErrno err = hashmap_do_insert(map, key, value, &replaced_value);
225
1/2
✗ Branch 0 (3→4) not taken.
✓ Branch 1 (3→5) taken 292 times.
292 FATAL_ERROR_ON(err, err);
226 292 return replaced_value;
227 }
228
229 // Remove all entries without freeing the table
230 583 void hashmap_clear(HashMap *map, FreeFunction free_value)
231 {
232
2/2
✓ Branch 0 (2→3) taken 276 times.
✓ Branch 1 (2→13) taken 307 times.
583 if (unlikely(!map->entries)) {
233 return;
234 }
235
236 276 size_t count = 0;
237
2/2
✓ Branch 0 (9→4) taken 4236 times.
✓ Branch 1 (9→10) taken 276 times.
4512 for (HashMapIter it = hashmap_iter(map); hashmap_next(&it); count++) {
238 4236 hashmap_free_key(map, it.entry->key);
239
2/2
✓ Branch 0 (5→6) taken 3777 times.
✓ Branch 1 (5→7) taken 459 times.
4236 if (free_value) {
240 3777 do_free_value(free_value, it.entry->value);
241 }
242 }
243
244 276 BUG_ON(count != map->count);
245 276 size_t len = map->mask + 1;
246 276 map->count = 0;
247 276 memset(map->entries, 0, len * sizeof(*map->entries));
248 }
249
250 565 void hashmap_free(HashMap *map, FreeFunction free_value)
251 {
252 565 hashmap_clear(map, free_value);
253 565 free(map->entries);
254 565 *map = (HashMap){.flags = map->flags};
255 565 }
256