dte test coverage

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