dte test coverage

Directory: ./
Coverage: low: ≥ 0% medium: ≥ 50.0% high: ≥ 85.0%
Coverage Exec / Excl / Total
Lines: 93.8% 121 / 0 / 129
Functions: 100.0% 11 / 0 / 11
Branches: 81.2% 52 / 16 / 80
src/util/hashmap.c
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 501 static SystemErrno hashmap_resize(HashMap *map, size_t capacity)
18 {
19 501 BUG_ON(capacity < MIN_CAPACITY);
20 501 BUG_ON(capacity <= map->count);
21 501 BUG_ON(!IS_POWER_OF_2(capacity));
22
23 501 const size_t entrysize = sizeof(map->entries[0]);
24
1/2
✓ Branch 8 → 9 taken 501 times.
✗ Branch 8 → 21 not taken.
 501 if (unlikely(calloc_args_have_ub_overflow(capacity, entrysize))) {
25 return EOVERFLOW;
26 }
27
28 501 HashMapEntry *newtab = calloc(capacity, entrysize); // NOLINT(*-unsafe-functions)
29
1/2
✓ Branch 9 → 10 taken 501 times.
✗ Branch 9 → 21 not taken.
 501 if (unlikely(!newtab)) {
30 return ENOMEM;
31 }
32
33 501 HashMapEntry *oldtab = map->entries;
34 501 size_t oldlen = map->mask + 1;
35 501 map->entries = newtab;
36 501 map->mask = capacity - 1;
37 501 map->tombstones = 0;
38
39
2/2
✓ Branch 10 → 11 taken 222 times.
✓ Branch 10 → 21 taken 279 times.
 501 if (!oldtab) {
40 return 0;
41 }
42
43 // Copy the entries to the new table
44
2/2
✓ Branch 19 → 12 taken 19224 times.
✓ Branch 19 → 20 taken 222 times.
 19446 for (const HashMapEntry *e = oldtab, *end = e + oldlen; e < end; e++) {
45
2/2
✓ Branch 12 → 13 taken 10991 times.
✓ Branch 12 → 14 taken 8233 times.
 19224 if (!e->key) {
46 10991 continue;
47 }
48 8233 HashMapEntry *newe;
49 9855 for (size_t i = e->hash, j = 1; ; i += j++) {
50 9855 newe = newtab + (i & map->mask);
51
2/2
✓ Branch 15 → 16 taken 1622 times.
✓ Branch 15 → 17 taken 8233 times.
 9855 if (!newe->key) {
52 break;
53 }
54 }
55 8233 *newe = *e;
56 }
57
58 222 free(oldtab);
59 222 return 0;
60 }
61
62 WARN_UNUSED_RESULT
63 279 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 279 capacity += capacity / 3;
68
69
2/2
✓ Branch 2 → 3 taken 264 times.
✓ Branch 2 → 4 taken 15 times.
 279 if (unlikely(capacity < MIN_CAPACITY)) {
70 264 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 279 capacity = next_pow2(capacity);
78
1/2
✓ Branch 4 → 5 taken 279 times.
✗ Branch 4 → 6 not taken.
 279 if (unlikely(capacity == 0)) {
79 return EOVERFLOW;
80 }
81
82 279 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 3 → 4 not taken.
✓ Branch 3 → 5 taken 16 times.
 16 FATAL_ERROR_ON(err, err);
90 16 }
91
92 42698 HashMapEntry *hashmap_find(const HashMap *map, const char *key)
93 {
94
2/2
✓ Branch 2 → 3 taken 42344 times.
✓ Branch 2 → 10 taken 354 times.
 42698 if (unlikely(!map->entries)) {
95 return NULL;
96 }
97
98 42344 size_t hash = fnv_1a_hash(key, strlen(key));
99 42344 HashMapEntry *e;
100 79765 for (size_t i = hash, j = 1; ; i += j++) {
101 79765 e = map->entries + (i & map->mask);
102
2/2
✓ Branch 4 → 5 taken 31346 times.
✓ Branch 4 → 7 taken 48419 times.
 79765 if (!e->key) {
103
2/2
✓ Branch 5 → 6 taken 12182 times.
✓ Branch 5 → 10 taken 19164 times.
 31346 if (e->hash == TOMBSTONE) {
104 12182 continue;
105 }
106 return NULL;
107 }
108
3/4
✓ Branch 7 → 8 taken 23180 times.
✓ Branch 7 → 9 taken 25239 times.
✗ Branch 8 → 9 not taken.
✓ Branch 8 → 10 taken 23180 times.
 48419 if (e->hash == hash && streq(e->key, key)) {
109 return e;
110 }
111 }
112
113 BUG("unexpected loop break");
114 }
115
116 15805 static void hashmap_free_key(const HashMap *map, char *key)
117 {
118
2/2
✓ Branch 2 → 3 taken 15770 times.
✓ Branch 2 → 4 taken 35 times.
 15805 if (!(map->flags & HMAP_BORROWED_KEYS)) {
119 15770 free(key);
120 }
121 15805 }
122
123 11562 void *hashmap_remove(HashMap *map, const char *key)
124 {
125 11562 HashMapEntry *e = hashmap_find(map, key);
126
2/2
✓ Branch 3 → 4 taken 11543 times.
✓ Branch 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 15805 static SystemErrno hashmap_do_insert(HashMap *map, char *key, void *value, void **old_value)
140 {
141 15805 SystemErrno err = 0;
142
2/2
✓ Branch 2 → 3 taken 263 times.
✓ Branch 2 → 5 taken 15542 times.
 15805 if (unlikely(!map->entries)) {
143 263 err = hashmap_do_init(map, 0);
144
1/2
✓ Branch 4 → 5 taken 263 times.
✗ Branch 4 → 31 not taken.
 263 if (unlikely(err)) {
145 return err;
146 }
147 }
148
149 15805 size_t hash = fnv_1a_hash(key, strlen(key));
150 15805 bool replacing_tombstone_or_existing_value = false;
151 15805 HashMapEntry *e;
152 23427 for (size_t i = hash, j = 1; ; i += j++) {
153 23427 e = map->entries + (i & map->mask);
154
2/2
✓ Branch 6 → 7 taken 15804 times.
✓ Branch 6 → 11 taken 7623 times.
 23427 if (!e->key) {
155
2/2
✓ Branch 7 → 8 taken 4770 times.
✓ Branch 7 → 20 taken 11034 times.
 15804 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 11 → 12 taken 1 time.
✓ Branch 11 → 19 taken 7622 times.
✓ Branch 12 → 13 taken 1 time.
✗ Branch 12 → 19 not taken.
 7623 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 15805 const size_t max_load = map->mask - (map->mask / 4);
178 15805 e->key = key;
179 15805 e->value = value;
180 15805 e->hash = hash;
181 15805 map->count++;
182
183
2/2
✓ Branch 20 → 21 taken 222 times.
✓ Branch 20 → 31 taken 15583 times.
 15805 if (unlikely(map->count + map->tombstones > max_load)) {
184 222 BUG_ON(replacing_tombstone_or_existing_value);
185 222 size_t new_size = map->mask + 1;
186
3/4
✓ Branch 23 → 24 taken 6 times.
✓ Branch 23 → 25 taken 216 times.
✗ Branch 24 → 25 not taken.
✓ Branch 24 → 27 taken 6 times.
 222 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 216 new_size <<= 1;
194
1/2
✗ Branch 25 → 26 not taken.
✓ Branch 25 → 27 taken 216 times.
 216 if (unlikely(new_size == 0)) {
195 ✗ err = EOVERFLOW;
196 ✗ goto error;
197 }
198 }
199 222 err = hashmap_resize(map, new_size);
200
1/2
✗ Branch 28 → 29 not taken.
✓ Branch 28 → 31 taken 222 times.
 222 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 15510 void *hashmap_insert(HashMap *map, char *key, void *value)
215 {
216 15510 SystemErrno err = hashmap_do_insert(map, key, value, NULL);
217
1/2
✗ Branch 3 → 4 not taken.
✓ Branch 3 → 5 taken 15510 times.
 15510 FATAL_ERROR_ON(err, err);
218 15510 return value;
219 }
220
221 295 void *hashmap_insert_or_replace(HashMap *map, char *key, void *value)
222 {
223 295 void *replaced_value = NULL;
224 295 SystemErrno err = hashmap_do_insert(map, key, value, &replaced_value);
225
1/2
✗ Branch 3 → 4 not taken.
✓ Branch 3 → 5 taken 295 times.
 295 FATAL_ERROR_ON(err, err);
226 295 return replaced_value;
227 }
228
229 // Remove all entries without freeing the table
230 589 void hashmap_clear(HashMap *map, FreeFunction free_value)
231 {
232
2/2
✓ Branch 2 → 3 taken 279 times.
✓ Branch 2 → 13 taken 310 times.
 589 if (unlikely(!map->entries)) {
233 return;
234 }
235
236 279 size_t count = 0;
237
2/2
✓ Branch 9 → 4 taken 4261 times.
✓ Branch 9 → 10 taken 279 times.
 4540 for (HashMapIter it = hashmap_iter(map); hashmap_next(&it); count++) {
238 4261 hashmap_free_key(map, it.entry->key);
239
2/2
✓ Branch 5 → 6 taken 3799 times.
✓ Branch 5 → 7 taken 462 times.
 4261 if (free_value) {
240 3799 do_free_value(free_value, it.entry->value);
241 }
242 }
243
244 279 BUG_ON(count != map->count);
245 279 size_t len = map->mask + 1;
246 279 map->count = 0;
247 279 memset(map->entries, 0, len * sizeof(*map->entries));
248 }
249
250 571 void hashmap_free(HashMap *map, FreeFunction free_value)
251 {
252 571 hashmap_clear(map, free_value);
253 571 free(map->entries);
254 571 *map = (HashMap){.flags = map->flags};
255 571 }
256