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 508 static SystemErrno hashmap_resize(HashMap *map, size_t capacity)
18 {
19 508 BUG_ON(capacity < MIN_CAPACITY);
20 508 BUG_ON(capacity <= map->count);
21 508 BUG_ON(!IS_POWER_OF_2(capacity));
22
23 508 const size_t entrysize = sizeof(map->entries[0]);
24
1/2
✓ Branch 8 → 9 taken 508 times.
✗ Branch 8 → 21 not taken.
 508 if (unlikely(calloc_args_have_ub_overflow(capacity, entrysize))) {
25 return EOVERFLOW;
26 }
27
28 508 HashMapEntry *newtab = calloc(capacity, entrysize); // NOLINT(*-unsafe-functions)
29
1/2
✓ Branch 9 → 10 taken 508 times.
✗ Branch 9 → 21 not taken.
 508 if (unlikely(!newtab)) {
30 return ENOMEM;
31 }
32
33 508 HashMapEntry *oldtab = map->entries;
34 508 size_t oldlen = map->mask + 1;
35 508 map->entries = newtab;
36 508 map->mask = capacity - 1;
37 508 map->tombstones = 0;
38
39
2/2
✓ Branch 10 → 11 taken 227 times.
✓ Branch 10 → 21 taken 281 times.
 508 if (!oldtab) {
40 return 0;
41 }
42
43 // Copy the entries to the new table
44
2/2
✓ Branch 19 → 12 taken 19304 times.
✓ Branch 19 → 20 taken 227 times.
 19531 for (const HashMapEntry *e = oldtab, *end = e + oldlen; e < end; e++) {
45
2/2
✓ Branch 12 → 13 taken 11006 times.
✓ Branch 12 → 14 taken 8298 times.
 19304 if (!e->key) {
46 11006 continue;
47 }
48 8298 HashMapEntry *newe;
49 9926 for (size_t i = e->hash, j = 1; ; i += j++) {
50 9926 newe = newtab + (i & map->mask);
51
2/2
✓ Branch 15 → 16 taken 1628 times.
✓ Branch 15 → 17 taken 8298 times.
 9926 if (!newe->key) {
52 break;
53 }
54 }
55 8298 *newe = *e;
56 }
57
58 227 free(oldtab);
59 227 return 0;
60 }
61
62 WARN_UNUSED_RESULT
63 281 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 281 capacity += capacity / 3;
68
69
2/2
✓ Branch 2 → 3 taken 266 times.
✓ Branch 2 → 4 taken 15 times.
 281 if (unlikely(capacity < MIN_CAPACITY)) {
70 266 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 281 capacity = next_pow2(capacity);
78
1/2
✓ Branch 4 → 5 taken 281 times.
✗ Branch 4 → 6 not taken.
 281 if (unlikely(capacity == 0)) {
79 return EOVERFLOW;
80 }
81
82 281 return hashmap_resize(map, capacity);
83 }
84
85 27 HashMap hashmap_new(size_t capacity, HashMapFlags flags)
86 {
87 27 HashMap map = {.flags = flags};
88 27 SystemErrno err = hashmap_do_init(&map, capacity);
89
1/2
✗ Branch 3 → 4 not taken.
✓ Branch 3 → 5 taken 27 times.
 27 FATAL_ERROR_ON(err, err);
90 27 return map;
91 }
92
93 42972 HashMapEntry *hashmap_find(const HashMap *map, const char *key)
94 {
95
2/2
✓ Branch 2 → 3 taken 42616 times.
✓ Branch 2 → 10 taken 356 times.
 42972 if (unlikely(!map->entries)) {
96 return NULL;
97 }
98
99 42616 size_t hash = fnv_1a_hash(key, strlen(key));
100 42616 HashMapEntry *e;
101 80311 for (size_t i = hash, j = 1; ; i += j++) {
102 80311 e = map->entries + (i & map->mask);
103
2/2
✓ Branch 4 → 5 taken 31435 times.
✓ Branch 4 → 7 taken 48876 times.
 80311 if (!e->key) {
104
2/2
✓ Branch 5 → 6 taken 12182 times.
✓ Branch 5 → 10 taken 19253 times.
 31435 if (e->hash == TOMBSTONE) {
105 12182 continue;
106 }
107 return NULL;
108 }
109
3/4
✓ Branch 7 → 8 taken 23363 times.
✓ Branch 7 → 9 taken 25513 times.
✗ Branch 8 → 9 not taken.
✓ Branch 8 → 10 taken 23363 times.
 48876 if (e->hash == hash && streq(e->key, key)) {
110 return e;
111 }
112 }
113
114 BUG("unexpected loop break");
115 }
116
117 15865 static void hashmap_free_key(const HashMap *map, char *key)
118 {
119
2/2
✓ Branch 2 → 3 taken 15796 times.
✓ Branch 2 → 4 taken 69 times.
 15865 if (!(map->flags & HMAP_BORROWED_KEYS)) {
120 15796 free(key);
121 }
122 15865 }
123
124 11562 void *hashmap_remove(HashMap *map, const char *key)
125 {
126 11562 HashMapEntry *e = hashmap_find(map, key);
127
2/2
✓ Branch 3 → 4 taken 11543 times.
✓ Branch 3 → 6 taken 19 times.
 11562 if (!e) {
128 return NULL;
129 }
130
131 11543 hashmap_free_key(map, e->key);
132 11543 e->key = NULL;
133 11543 e->hash = TOMBSTONE;
134 11543 map->count--;
135 11543 map->tombstones++;
136 11543 return e->value;
137 }
138
139 WARN_UNUSED_RESULT
140 15865 static SystemErrno hashmap_do_insert(HashMap *map, char *key, void *value, void **old_value)
141 {
142 15865 SystemErrno err = 0;
143
2/2
✓ Branch 2 → 3 taken 254 times.
✓ Branch 2 → 5 taken 15611 times.
 15865 if (unlikely(!map->entries)) {
144 254 err = hashmap_do_init(map, 0);
145
1/2
✓ Branch 4 → 5 taken 254 times.
✗ Branch 4 → 31 not taken.
 254 if (unlikely(err)) {
146 return err;
147 }
148 }
149
150 15865 size_t hash = fnv_1a_hash(key, strlen(key));
151 15865 bool replacing_tombstone_or_existing_value = false;
152 15865 HashMapEntry *e;
153 23561 for (size_t i = hash, j = 1; ; i += j++) {
154 23561 e = map->entries + (i & map->mask);
155
2/2
✓ Branch 6 → 7 taken 15864 times.
✓ Branch 6 → 11 taken 7697 times.
 23561 if (!e->key) {
156
2/2
✓ Branch 7 → 8 taken 4770 times.
✓ Branch 7 → 20 taken 11094 times.
 15864 if (e->hash == TOMBSTONE) {
157 4770 replacing_tombstone_or_existing_value = true;
158 4770 BUG_ON(map->tombstones == 0);
159 4770 map->tombstones--;
160 }
161 break;
162 }
163
3/4
✓ Branch 11 → 12 taken 1 time.
✓ Branch 11 → 19 taken 7696 times.
✓ Branch 12 → 13 taken 1 time.
✗ Branch 12 → 19 not taken.
 7697 if (unlikely(e->hash == hash && streq(e->key, key))) {
164 1 replacing_tombstone_or_existing_value = true;
165 // When a caller passes NULL as the "old_value" return param,
166 // it implies there can be no existing entry with the same key
167 // as the one to be inserted.
168 1 BUG_ON(!old_value);
169 1 BUG_ON(!e->value);
170 1 *old_value = e->value;
171 1 hashmap_free_key(map, key);
172 1 key = e->key;
173 1 map->count--;
174 1 break;
175 }
176 }
177
178 15865 const size_t max_load = map->mask - (map->mask / 4);
179 15865 e->key = key;
180 15865 e->value = value;
181 15865 e->hash = hash;
182 15865 map->count++;
183
184
2/2
✓ Branch 20 → 21 taken 227 times.
✓ Branch 20 → 31 taken 15638 times.
 15865 if (unlikely(map->count + map->tombstones > max_load)) {
185 227 BUG_ON(replacing_tombstone_or_existing_value);
186 227 size_t new_size = map->mask + 1;
187
3/4
✓ Branch 23 → 24 taken 6 times.
✓ Branch 23 → 25 taken 221 times.
✗ Branch 24 → 25 not taken.
✓ Branch 24 → 27 taken 6 times.
 227 if (map->count > map->tombstones || new_size <= 256) {
188 // Only increase the size of the table when the number of
189 // real entries is higher than the number of tombstones.
190 // If the number of real entries is lower, the table is
191 // most likely being filled with tombstones from repeated
192 // insert/remove churn; so we just rehash at the same size
193 // to clean out the tombstones.
194 221 new_size <<= 1;
195
1/2
✗ Branch 25 → 26 not taken.
✓ Branch 25 → 27 taken 221 times.
 221 if (unlikely(new_size == 0)) {
196 ✗ err = EOVERFLOW;
197 ✗ goto error;
198 }
199 }
200 227 err = hashmap_resize(map, new_size);
201
1/2
✗ Branch 28 → 29 not taken.
✓ Branch 28 → 31 taken 227 times.
 227 if (unlikely(err)) {
202 ✗ goto error;
203 }
204 }
205
206 return 0;
207
208 ✗ error:
209 ✗ map->count--;
210 ✗ e->key = NULL;
211 ✗ e->hash = 0;
212 ✗ return err;
213 }
214
215 15561 void *hashmap_insert(HashMap *map, char *key, void *value)
216 {
217 15561 SystemErrno err = hashmap_do_insert(map, key, value, NULL);
218
1/2
✗ Branch 3 → 4 not taken.
✓ Branch 3 → 5 taken 15561 times.
 15561 FATAL_ERROR_ON(err, err);
219 15561 return value;
220 }
221
222 304 void *hashmap_insert_or_replace(HashMap *map, char *key, void *value)
223 {
224 304 void *replaced_value = NULL;
225 304 SystemErrno err = hashmap_do_insert(map, key, value, &replaced_value);
226
1/2
✗ Branch 3 → 4 not taken.
✓ Branch 3 → 5 taken 304 times.
 304 FATAL_ERROR_ON(err, err);
227 304 return replaced_value;
228 }
229
230 // Remove all entries without freeing the table
231 595 void hashmap_clear(HashMap *map, FreeFunction free_value)
232 {
233
2/2
✓ Branch 2 → 3 taken 281 times.
✓ Branch 2 → 13 taken 314 times.
 595 if (unlikely(!map->entries)) {
234 return;
235 }
236
237 281 size_t count = 0;
238
2/2
✓ Branch 9 → 4 taken 4321 times.
✓ Branch 9 → 10 taken 281 times.
 4602 for (HashMapIter it = hashmap_iter(map); hashmap_next(&it); count++) {
239 4321 hashmap_free_key(map, it.entry->key);
240
2/2
✓ Branch 5 → 6 taken 3859 times.
✓ Branch 5 → 7 taken 462 times.
 4321 if (free_value) {
241 3859 do_free_value(free_value, it.entry->value);
242 }
243 }
244
245 281 BUG_ON(count != map->count);
246 281 size_t len = map->mask + 1;
247 281 map->count = 0;
248 281 memset(map->entries, 0, len * sizeof(*map->entries));
249 }
250
251 577 void hashmap_free(HashMap *map, FreeFunction free_value)
252 {
253 577 hashmap_clear(map, free_value);
254 577 free(map->entries);
255 577 *map = (HashMap){.flags = map->flags};
256 577 }
257