dte test coverage

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