dte test coverage

Directory: ./
Coverage: low: ≥ 0% medium: ≥ 50.0% high: ≥ 85.0%
Coverage Exec / Excl / Total
Lines: 93.5% 115 / 0 / 123
Functions: 100.0% 10 / 0 / 10
Branches: 75.9% 44 / 14 / 72
src/util/intmap.c
Line Branch Exec Source
1 #include <errno.h>
2 #include <stdlib.h>
3 #include <string.h>
4 #include "intmap.h"
5 #include "arith.h"
6 #include "bit.h"
7 #include "debug.h"
8 #include "errorcode.h"
9
10 const char tombstone[16] = "TOMBSTONE";
11
12 enum {
13 MIN_CAPACITY = 8,
14 };
15
16 2013 static size_t hash_key(uint32_t k)
17 {
18 2013 k = ((k >> 16) ^ k) * 0x45d9f3b;
19 2013 k = ((k >> 16) ^ k) * 0x45d9f3b;
20 2013 k = (k >> 16) ^ k;
21 2013 return k;
22 }
23
24 WARN_UNUSED_RESULT
25 36 static SystemErrno intmap_resize(IntMap *map, size_t capacity)
26 {
27 36 BUG_ON(capacity < MIN_CAPACITY);
28 36 BUG_ON(capacity <= map->count);
29 36 BUG_ON(!IS_POWER_OF_2(capacity));
30
31 36 const size_t entrysize = sizeof(map->entries[0]);
32
1/2
✓ Branch 8 → 9 taken 36 times.
✗ Branch 8 → 22 not taken.
 36 if (unlikely(calloc_args_have_ub_overflow(capacity, entrysize))) {
33 return EOVERFLOW;
34 }
35
36 36 IntMapEntry *newtab = calloc(capacity, entrysize); // NOLINT(*-unsafe-functions)
37
1/2
✓ Branch 9 → 10 taken 36 times.
✗ Branch 9 → 22 not taken.
 36 if (unlikely(!newtab)) {
38 return ENOMEM;
39 }
40
41 36 IntMapEntry *oldtab = map->entries;
42 36 size_t oldlen = map->mask + 1;
43 36 map->entries = newtab;
44 36 map->mask = capacity - 1;
45 36 map->tombstones = 0;
46
47
2/2
✓ Branch 10 → 11 taken 1 time.
✓ Branch 10 → 22 taken 35 times.
 36 if (!oldtab) {
48 return 0;
49 }
50
51 // Copy the entries to the new table
52
2/2
✓ Branch 20 → 12 taken 8 times.
✓ Branch 20 → 21 taken 1 time.
 9 for (const IntMapEntry *e = oldtab, *end = e + oldlen; e < end; e++) {
53
3/4
✓ Branch 12 → 13 taken 8 times.
✗ Branch 12 → 14 not taken.
✓ Branch 13 → 14 taken 1 time.
✓ Branch 13 → 15 taken 7 times.
 8 if (!e->value || e->value == tombstone) {
54 1 continue;
55 }
56 7 IntMapEntry *newe;
57 9 for (size_t i = hash_key(e->key), j = 1; ; i += j++) {
58 9 newe = newtab + (i & map->mask);
59
2/2
✓ Branch 16 → 17 taken 2 times.
✓ Branch 16 → 18 taken 7 times.
 9 if (!newe->key) {
60 break;
61 }
62 }
63 7 *newe = *e;
64 }
65
66 1 free(oldtab);
67 1 return 0;
68 }
69
70 WARN_UNUSED_RESULT
71 35 static SystemErrno intmap_do_init(IntMap *map, size_t capacity)
72 {
73 // Accommodate the 75% load factor in the table size, to allow
74 // filling to the requested size without needing to resize()
75 35 capacity += capacity / 3;
76
77
2/2
✓ Branch 2 → 3 taken 2 times.
✓ Branch 2 → 4 taken 33 times.
 35 if (unlikely(capacity < MIN_CAPACITY)) {
78 2 capacity = MIN_CAPACITY;
79 }
80
81 35 capacity = next_pow2(capacity);
82
1/2
✓ Branch 4 → 5 taken 35 times.
✗ Branch 4 → 6 not taken.
 35 if (unlikely(capacity == 0)) {
83 return EOVERFLOW;
84 }
85
86 35 *map = (IntMap){.entries = NULL};
87 35 return intmap_resize(map, capacity);
88 }
89
90 34 IntMap intmap_new(size_t capacity)
91 {
92 34 IntMap map;
93 34 SystemErrno err = intmap_do_init(&map, capacity);
94
1/2
✗ Branch 3 → 4 not taken.
✓ Branch 3 → 5 taken 34 times.
 34 FATAL_ERROR_ON(err, err);
95 34 return map;
96 }
97
98 17 IntMapEntry *intmap_find(const IntMap *map, uint32_t key)
99 {
100
2/2
✓ Branch 2 → 3 taken 15 times.
✓ Branch 2 → 9 taken 2 times.
 17 if (unlikely(!map->entries)) {
101 return NULL;
102 }
103
104 15 size_t hash = hash_key(key);
105 15 IntMapEntry *e;
106 35 for (size_t i = hash, j = 1; ; i += j++) {
107 35 e = map->entries + (i & map->mask);
108
2/2
✓ Branch 4 → 5 taken 32 times.
✓ Branch 4 → 9 taken 3 times.
 35 if (!e->value) {
109 return NULL;
110 }
111
2/2
✓ Branch 5 → 6 taken 2 times.
✓ Branch 5 → 7 taken 30 times.
 32 if (e->value == tombstone) {
112 2 continue;
113 }
114
2/2
✓ Branch 7 → 8 taken 18 times.
✓ Branch 7 → 9 taken 12 times.
 30 if (e->key == key) {
115 return e;
116 }
117 }
118
119 BUG("unexpected loop break");
120 }
121
122 2 void *intmap_remove(IntMap *map, uint32_t key)
123 {
124 2 IntMapEntry *e = intmap_find(map, key);
125
1/2
✓ Branch 3 → 4 taken 2 times.
✗ Branch 3 → 5 not taken.
 2 if (!e) {
126 return NULL;
127 }
128
129 2 void *value = e->value;
130 2 e->key = 0;
131 2 e->value = (char*)tombstone;
132 2 map->count--;
133 2 map->tombstones++;
134 2 return value;
135 }
136
137 WARN_UNUSED_RESULT
138 1991 static SystemErrno intmap_do_insert(IntMap *map, uint32_t key, void *value, void **old_value)
139 {
140 1991 SystemErrno err = 0;
141
2/2
✓ Branch 2 → 3 taken 1 time.
✓ Branch 2 → 5 taken 1990 times.
 1991 if (unlikely(!map->entries)) {
142 1 err = intmap_do_init(map, 0);
143
1/2
✓ Branch 4 → 5 taken 1 time.
✗ Branch 4 → 27 not taken.
 1 if (unlikely(err)) {
144 return err;
145 }
146 }
147
148 1991 size_t hash = hash_key(key);
149 1991 bool replacing_tombstone_or_existing_value = false;
150 1991 IntMapEntry *e;
151 3285 for (size_t i = hash, j = 1; ; i += j++) {
152 3285 e = map->entries + (i & map->mask);
153
2/2
✓ Branch 6 → 7 taken 1295 times.
✓ Branch 6 → 16 taken 1990 times.
 3285 if (!e->value) {
154 break;
155 }
156
2/2
✓ Branch 7 → 8 taken 1 time.
✓ Branch 7 → 11 taken 1294 times.
 1295 if (e->value == tombstone) {
157 1 replacing_tombstone_or_existing_value = true;
158 1 BUG_ON(map->tombstones == 0);
159 1 map->tombstones--;
160 }
161
2/2
✓ Branch 11 → 12 taken 1 time.
✓ Branch 11 → 15 taken 1294 times.
 1295 if (unlikely(e->key == key)) {
162 1 replacing_tombstone_or_existing_value = true;
163 1 BUG_ON(!e->value);
164 1 *old_value = e->value;
165 1 key = e->key;
166 1 map->count--;
167 1 break;
168 }
169 }
170
171 1991 const size_t max_load = map->mask - (map->mask / 4);
172 1991 e->key = key;
173 1991 e->value = value;
174 1991 map->count++;
175
176
2/2
✓ Branch 16 → 17 taken 1 time.
✓ Branch 16 → 27 taken 1990 times.
 1991 if (unlikely(map->count + map->tombstones > max_load)) {
177 1 BUG_ON(replacing_tombstone_or_existing_value);
178 1 size_t new_size = map->mask + 1;
179
1/4
✗ Branch 19 → 20 not taken.
✓ Branch 19 → 21 taken 1 time.
✗ Branch 20 → 21 not taken.
✗ Branch 20 → 23 not taken.
 1 if (map->count > map->tombstones || new_size <= 256) {
180 // Only increase the size of the table when the number of
181 // real entries is higher than the number of tombstones
182 1 new_size <<= 1;
183
1/2
✗ Branch 21 → 22 not taken.
✓ Branch 21 → 23 taken 1 time.
 1 if (unlikely(new_size == 0)) {
184 ✗ err = EOVERFLOW;
185 ✗ goto error;
186 }
187 }
188 1 err = intmap_resize(map, new_size);
189
1/2
✗ Branch 24 → 25 not taken.
✓ Branch 24 → 27 taken 1 time.
 1 if (unlikely(err)) {
190 ✗ goto error;
191 }
192 }
193
194 return 0;
195
196 ✗ error:
197 ✗ map->count--;
198 ✗ e->key = 0;
199 ✗ e->value = NULL;
200 ✗ return err;
201 }
202
203 1991 void *intmap_insert_or_replace(IntMap *map, uint32_t key, void *value)
204 {
205 1991 void *replaced_value = NULL;
206 1991 SystemErrno err = intmap_do_insert(map, key, value, &replaced_value);
207
1/2
✗ Branch 3 → 4 not taken.
✓ Branch 3 → 5 taken 1991 times.
 1991 FATAL_ERROR_ON(err, err);
208 1991 return replaced_value;
209 }
210
211 // Remove all entries without freeing the table
212 36 static void intmap_clear(IntMap *map, FreeFunction free_value)
213 {
214
2/2
✓ Branch 2 → 3 taken 35 times.
✓ Branch 2 → 12 taken 1 time.
 36 if (unlikely(!map->entries)) {
215 return;
216 }
217
218
1/2
✓ Branch 3 → 4 taken 35 times.
✗ Branch 3 → 11 not taken.
 35 if (free_value) {
219 35 size_t count = 0;
220
2/2
✓ Branch 8 → 5 taken 1988 times.
✓ Branch 8 → 9 taken 35 times.
 2023 for (IntMapIter it = intmap_iter(map); intmap_next(&it); count++) {
221 1988 do_free_value(free_value, it.entry->value);
222 }
223 35 BUG_ON(count != map->count);
224 }
225
226 35 size_t len = map->mask + 1;
227 35 map->count = 0;
228 35 memset(map->entries, 0, len * sizeof(*map->entries));
229 }
230
231 36 void intmap_free(IntMap *map, FreeFunction free_value)
232 {
233 36 intmap_clear(map, free_value);
234 36 free(map->entries);
235 36 *map = (IntMap){.entries = NULL};
236 36 }
237