dte test coverage


Directory: ./
File: src/util/hashmap.c
Date: 2025-07-01 18:22:46
Exec Total Coverage
Lines: 119 127 93.7%
Functions: 11 11 100.0%
Branches: 51 62 82.3%

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