GCC Code Coverage Report

Directory: ./
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 100.0% 177 / 6 / 183
Functions: 100.0% 29 / 0 / 29
Branches: 85.0% 102 / 0 / 120
map.c
Line Branch Exec Source
1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
3 *
4 * Copyright 2023 Mike Becker, Olaf Wintermann All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 *
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 */
28
29 #include "cx/map.h"
30 #include <string.h>
31
32 #include "cx/list.h"
33
34 // <editor-fold desc="empty map implementation">
35
36 2 static void cx_empty_map_noop(CX_UNUSED CxMap *map) {
37 // this is a noop, but MUST be implemented
38 2 }
39
40 1 static void *cx_empty_map_get(
41 CX_UNUSED const CxMap *map,
42 CX_UNUSED CxHashKey key
43 ) {
44 1 return NULL;
45 }
46
47 24 static bool cx_empty_map_iter_valid(CX_UNUSED const void *iter) {
48 24 return false;
49 }
50
51 12 static CxMapIterator cx_empty_map_iterator(
52 const struct cx_map_s *map,
53 CX_UNUSED enum cx_map_iterator_type type
54 ) {
55 12 CxMapIterator iter = {0};
56 12 iter.map = (CxMap*) map;
57 12 iter.base.valid = cx_empty_map_iter_valid;
58 12 return iter;
59 }
60
61 static struct cx_map_class_s cx_empty_map_class = {
62 cx_empty_map_noop,
63 cx_empty_map_noop,
64 NULL,
65 cx_empty_map_get,
66 NULL,
67 cx_empty_map_iterator
68 };
69
70 CxMap cx_empty_map = {
71 {
72 NULL,
73 0,
74 0,
75 NULL,
76 NULL,
77 NULL,
78 NULL,
79 NULL,
80 NULL,
81 false,
82 true
83 },
84 &cx_empty_map_class
85 };
86
87 CxMap *const cxEmptyMap = &cx_empty_map;
88
89 // </editor-fold>
90
91 10 void cxMapClear(CxMap *map) {
92 10 map->cl->clear(map);
93 10 }
94
95 489 size_t cxMapSize(const CxMap *map) {
96 489 return map->collection.size;
97 }
98
99 28 CxMapIterator cxMapIteratorValues(const CxMap *map) {
100
2/2
✓ Branch 2 → 3 taken 2 times.
✓ Branch 2 → 4 taken 26 times.
 28 if (map == NULL) map = cxEmptyMap;
101 28 return map->cl->iterator(map, CX_MAP_ITERATOR_VALUES);
102 }
103
104 27 CxMapIterator cxMapIteratorKeys(const CxMap *map) {
105
2/2
✓ Branch 2 → 3 taken 2 times.
✓ Branch 2 → 4 taken 25 times.
 27 if (map == NULL) map = cxEmptyMap;
106 27 return map->cl->iterator(map, CX_MAP_ITERATOR_KEYS);
107 }
108
109 254 CxMapIterator cxMapIterator(const CxMap *map) {
110
2/2
✓ Branch 2 → 3 taken 2 times.
✓ Branch 2 → 4 taken 252 times.
 254 if (map == NULL) map = cxEmptyMap;
111 254 return map->cl->iterator(map, CX_MAP_ITERATOR_PAIRS);
112 }
113
114 1038 int cx_map_put(CxMap *map, CxHashKey key, void *value) {
115 1038 return map->cl->put(map, key, value).key == NULL;
116 }
117
118 187 void *cx_map_emplace(CxMap *map, CxHashKey key) {
119 187 const CxMapEntry entry = map->cl->put(map, key, NULL);
120
1/2
✗ Branch 3 → 4 not taken.
✓ Branch 3 → 5 taken 187 times.
 187 if (entry.key == NULL) return NULL;
121 187 return entry.value;
122 }
123
124 634 void *cx_map_get(const CxMap *map, CxHashKey key) {
125 634 return map->cl->get(map, key);
126 }
127
128 44 int cx_map_remove(CxMap *map, CxHashKey key, void *targetbuf) {
129 44 return map->cl->remove(map, key, targetbuf);
130 }
131
132 251 void cxMapFree(CxMap *map) {
133
1/2
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 251 times.
 251 if (map == NULL) return;
134 251 map->cl->deallocate(map);
135 }
136
137 6 static void cx_map_remove_uninitialized_entry(CxMap *map, CxHashKey key) {
138 6 cx_destructor_func destr_bak = map->collection.simple_destructor;
139 6 cx_destructor_func2 destr2_bak = map->collection.advanced_destructor;
140 6 map->collection.simple_destructor = NULL;
141 6 map->collection.advanced_destructor = NULL;
142 6 cxMapRemove(map, key);
143 6 map->collection.simple_destructor = destr_bak;
144 6 map->collection.advanced_destructor = destr2_bak;
145 6 }
146
147 15 static void* cx_map_shallow_clone_func(void *dst, const void *src, const CxAllocator *al, void *data) {
148 15 size_t elem_size = *(size_t*)data;
149
1/2
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 15 times.
 15 if (dst == NULL) dst = cxMalloc(al, elem_size);
150
1/2
✓ Branch 4 → 5 taken 15 times.
✗ Branch 4 → 6 not taken.
 15 if (dst != NULL) memcpy(dst, src, elem_size);
151 15 return dst;
152 }
153
154 #define use_shallow_clone_func(map) cx_map_shallow_clone_func, NULL, (void*)&((map)->collection.elem_size)
155
156 26 int cxMapClone(CxMap *dst, const CxMap *src, cx_clone_func clone_func,
157 const CxAllocator *clone_allocator, void *data) {
158
2/2
✓ Branch 2 → 3 taken 3 times.
✓ Branch 2 → 4 taken 23 times.
 26 if (clone_allocator == NULL) clone_allocator = cxDefaultAllocator;
159 26 CxMapIterator src_iter = cxMapIterator(src);
160
2/2
✓ Branch 24 → 6 taken 138 times.
✓ Branch 24 → 25 taken 25 times.
 163 for (size_t i = 0; i < cxMapSize(src); i++) {
161 138 const CxMapEntry *entry = cxIteratorCurrent(src_iter);
162 276 void **dst_mem = cxMapEmplace(dst, *(entry->key));
163
1/2
✗ Branch 10 → 11 not taken.
✓ Branch 10 → 12 taken 138 times.
 138 if (dst_mem == NULL) {
164 − return 1; // LCOV_EXCL_LINE
165 }
166
2/2
✓ Branch 12 → 13 taken 128 times.
✓ Branch 12 → 14 taken 10 times.
 138 void *target = cxCollectionStoresPointers(dst) ? NULL : dst_mem;
167 138 void *dst_ptr = clone_func(target, entry->value, clone_allocator, data);
168
2/2
✓ Branch 16 → 17 taken 1 time.
✓ Branch 16 → 19 taken 137 times.
 138 if (dst_ptr == NULL) {
169 1 cx_map_remove_uninitialized_entry(dst, *(entry->key));
170 1 return 1;
171 }
172
2/2
✓ Branch 19 → 20 taken 128 times.
✓ Branch 19 → 21 taken 9 times.
 137 if (cxCollectionStoresPointers(dst)) {
173 128 *dst_mem = dst_ptr;
174 }
175 137 cxIteratorNext(src_iter);
176 }
177 25 return 0;
178 }
179
180 5 int cxMapDifference(CxMap *dst, const CxMap *minuend, const CxMap *subtrahend,
181 cx_clone_func clone_func, const CxAllocator *clone_allocator, void *data) {
182
2/2
✓ Branch 2 → 3 taken 4 times.
✓ Branch 2 → 4 taken 1 time.
 5 if (clone_allocator == NULL) clone_allocator = cxDefaultAllocator;
183
184 5 CxMapIterator src_iter = cxMapIterator(minuend);
185
3/4
✓ Branch 27 → 28 taken 17 times.
✓ Branch 27 → 30 taken 4 times.
✓ Branch 29 → 6 taken 17 times.
✗ Branch 29 → 30 not taken.
 21 cx_foreach(const CxMapEntry *, entry, src_iter) {
186
2/2
✓ Branch 9 → 10 taken 7 times.
✓ Branch 9 → 11 taken 10 times.
 34 if (cxMapContains(subtrahend, *entry->key)) {
187 7 continue;
188 }
189 20 void** dst_mem = cxMapEmplace(dst, *entry->key);
190
1/2
✗ Branch 14 → 15 not taken.
✓ Branch 14 → 16 taken 10 times.
 10 if (dst_mem == NULL) {
191 − return 1; // LCOV_EXCL_LINE
192 }
193
2/2
✓ Branch 16 → 17 taken 4 times.
✓ Branch 16 → 18 taken 6 times.
 10 void *target = cxCollectionStoresPointers(dst) ? NULL : dst_mem;
194 10 void* dst_ptr = clone_func(target, entry->value, clone_allocator, data);
195
2/2
✓ Branch 20 → 21 taken 1 time.
✓ Branch 20 → 23 taken 9 times.
 10 if (dst_ptr == NULL) {
196 1 cx_map_remove_uninitialized_entry(dst, *(entry->key));
197 1 return 1;
198 }
199
2/2
✓ Branch 23 → 24 taken 4 times.
✓ Branch 23 → 25 taken 5 times.
 9 if (cxCollectionStoresPointers(dst)) {
200 4 *dst_mem = dst_ptr;
201 }
202 }
203 4 return 0;
204 }
205
206 4 int cxMapListDifference(CxMap *dst, const CxMap *src, const CxList *keys,
207 cx_clone_func clone_func, const CxAllocator *clone_allocator, void *data) {
208
1/2
✓ Branch 2 → 3 taken 4 times.
✗ Branch 2 → 4 not taken.
 4 if (clone_allocator == NULL) clone_allocator = cxDefaultAllocator;
209
210 4 CxMapIterator src_iter = cxMapIterator(src);
211
3/4
✓ Branch 25 → 26 taken 13 times.
✓ Branch 25 → 28 taken 3 times.
✓ Branch 27 → 6 taken 13 times.
✗ Branch 27 → 28 not taken.
 16 cx_foreach(const CxMapEntry *, entry, src_iter) {
212
2/2
✓ Branch 7 → 8 taken 4 times.
✓ Branch 7 → 9 taken 9 times.
 13 if (cxListContains(keys, entry->key)) {
213 4 continue;
214 }
215 18 void** dst_mem = cxMapEmplace(dst, *entry->key);
216
1/2
✗ Branch 12 → 13 not taken.
✓ Branch 12 → 14 taken 9 times.
 9 if (dst_mem == NULL) {
217 − return 1; // LCOV_EXCL_LINE
218 }
219
2/2
✓ Branch 14 → 15 taken 2 times.
✓ Branch 14 → 16 taken 7 times.
 9 void *target = cxCollectionStoresPointers(dst) ? NULL : dst_mem;
220 9 void* dst_ptr = clone_func(target, entry->value, clone_allocator, data);
221
2/2
✓ Branch 18 → 19 taken 1 time.
✓ Branch 18 → 21 taken 8 times.
 9 if (dst_ptr == NULL) {
222 1 cx_map_remove_uninitialized_entry(dst, *(entry->key));
223 1 return 1;
224 }
225
2/2
✓ Branch 21 → 22 taken 2 times.
✓ Branch 21 → 23 taken 6 times.
 8 if (cxCollectionStoresPointers(dst)) {
226 2 *dst_mem = dst_ptr;
227 }
228 }
229 3 return 0;
230 }
231
232 5 int cxMapIntersection(CxMap *dst, const CxMap *src, const CxMap *other,
233 cx_clone_func clone_func, const CxAllocator *clone_allocator, void *data) {
234
2/2
✓ Branch 2 → 3 taken 4 times.
✓ Branch 2 → 4 taken 1 time.
 5 if (clone_allocator == NULL) clone_allocator = cxDefaultAllocator;
235
236 5 CxMapIterator src_iter = cxMapIterator(src);
237
3/4
✓ Branch 27 → 28 taken 17 times.
✓ Branch 27 → 30 taken 4 times.
✓ Branch 29 → 6 taken 17 times.
✗ Branch 29 → 30 not taken.
 21 cx_foreach(const CxMapEntry *, entry, src_iter) {
238
2/2
✓ Branch 9 → 10 taken 8 times.
✓ Branch 9 → 11 taken 9 times.
 34 if (!cxMapContains(other, *entry->key)) {
239 8 continue;
240 }
241 18 void** dst_mem = cxMapEmplace(dst, *entry->key);
242
1/2
✗ Branch 14 → 15 not taken.
✓ Branch 14 → 16 taken 9 times.
 9 if (dst_mem == NULL) {
243 − return 1; // LCOV_EXCL_LINE
244 }
245
2/2
✓ Branch 16 → 17 taken 4 times.
✓ Branch 16 → 18 taken 5 times.
 9 void *target = cxCollectionStoresPointers(dst) ? NULL : dst_mem;
246 9 void* dst_ptr = clone_func(target, entry->value, clone_allocator, data);
247
2/2
✓ Branch 20 → 21 taken 1 time.
✓ Branch 20 → 23 taken 8 times.
 9 if (dst_ptr == NULL) {
248 1 cx_map_remove_uninitialized_entry(dst, *(entry->key));
249 1 return 1;
250 }
251
2/2
✓ Branch 23 → 24 taken 4 times.
✓ Branch 23 → 25 taken 4 times.
 8 if (cxCollectionStoresPointers(dst)) {
252 4 *dst_mem = dst_ptr;
253 }
254 }
255 4 return 0;
256 }
257
258 4 int cxMapListIntersection(CxMap *dst, const CxMap *src, const CxList *keys,
259 cx_clone_func clone_func, const CxAllocator *clone_allocator, void *data) {
260
1/2
✓ Branch 2 → 3 taken 4 times.
✗ Branch 2 → 4 not taken.
 4 if (clone_allocator == NULL) clone_allocator = cxDefaultAllocator;
261
262 4 CxMapIterator src_iter = cxMapIterator(src);
263
3/4
✓ Branch 25 → 26 taken 14 times.
✓ Branch 25 → 28 taken 3 times.
✓ Branch 27 → 6 taken 14 times.
✗ Branch 27 → 28 not taken.
 17 cx_foreach(const CxMapEntry *, entry, src_iter) {
264
2/2
✓ Branch 7 → 8 taken 6 times.
✓ Branch 7 → 9 taken 8 times.
 14 if (!cxListContains(keys, entry->key)) {
265 6 continue;
266 }
267 16 void** dst_mem = cxMapEmplace(dst, *entry->key);
268
1/2
✗ Branch 12 → 13 not taken.
✓ Branch 12 → 14 taken 8 times.
 8 if (dst_mem == NULL) {
269 − return 1; // LCOV_EXCL_LINE
270 }
271
2/2
✓ Branch 14 → 15 taken 2 times.
✓ Branch 14 → 16 taken 6 times.
 8 void *target = cxCollectionStoresPointers(dst) ? NULL : dst_mem;
272 8 void* dst_ptr = clone_func(target, entry->value, clone_allocator, data);
273
2/2
✓ Branch 18 → 19 taken 1 time.
✓ Branch 18 → 21 taken 7 times.
 8 if (dst_ptr == NULL) {
274 1 cx_map_remove_uninitialized_entry(dst, *(entry->key));
275 1 return 1;
276 }
277
2/2
✓ Branch 21 → 22 taken 2 times.
✓ Branch 21 → 23 taken 5 times.
 7 if (cxCollectionStoresPointers(dst)) {
278 2 *dst_mem = dst_ptr;
279 }
280 }
281 3 return 0;
282 }
283
284 4 int cxMapUnion(CxMap *dst, const CxMap *src,
285 cx_clone_func clone_func, const CxAllocator *clone_allocator, void *data) {
286
2/2
✓ Branch 2 → 3 taken 3 times.
✓ Branch 2 → 4 taken 1 time.
 4 if (clone_allocator == NULL) clone_allocator = cxDefaultAllocator;
287
288 4 CxMapIterator src_iter = cxMapIterator(src);
289
3/4
✓ Branch 27 → 28 taken 13 times.
✓ Branch 27 → 30 taken 3 times.
✓ Branch 29 → 6 taken 13 times.
✗ Branch 29 → 30 not taken.
 16 cx_foreach(const CxMapEntry *, entry, src_iter) {
290
2/2
✓ Branch 9 → 10 taken 4 times.
✓ Branch 9 → 11 taken 9 times.
 26 if (cxMapContains(dst, *entry->key)) {
291 4 continue;
292 }
293 18 void** dst_mem = cxMapEmplace(dst, *entry->key);
294
1/2
✗ Branch 14 → 15 not taken.
✓ Branch 14 → 16 taken 9 times.
 9 if (dst_mem == NULL) {
295 − return 1; // LCOV_EXCL_LINE
296 }
297
2/2
✓ Branch 16 → 17 taken 2 times.
✓ Branch 16 → 18 taken 7 times.
 9 void *target = cxCollectionStoresPointers(dst) ? NULL : dst_mem;
298 9 void* dst_ptr = clone_func(target, entry->value, clone_allocator, data);
299
2/2
✓ Branch 20 → 21 taken 1 time.
✓ Branch 20 → 23 taken 8 times.
 9 if (dst_ptr == NULL) {
300 1 cx_map_remove_uninitialized_entry(dst, *(entry->key));
301 1 return 1;
302 }
303
2/2
✓ Branch 23 → 24 taken 2 times.
✓ Branch 23 → 25 taken 6 times.
 8 if (cxCollectionStoresPointers(dst)) {
304 2 *dst_mem = dst_ptr;
305 }
306 }
307 3 return 0;
308 }
309
310 1 int cxMapCloneShallow(CxMap *dst, const CxMap *src) {
311 1 return cxMapClone(dst, src, use_shallow_clone_func(src));
312 }
313
314 1 int cxMapDifferenceShallow(CxMap *dst, const CxMap *minuend, const CxMap *subtrahend) {
315 1 return cxMapDifference(dst, minuend, subtrahend, use_shallow_clone_func(minuend));
316 }
317
318 1 int cxMapListDifferenceShallow(CxMap *dst, const CxMap *src, const CxList *keys) {
319 1 return cxMapListDifference(dst, src, keys, use_shallow_clone_func(src));
320 }
321
322 1 int cxMapIntersectionShallow(CxMap *dst, const CxMap *src, const CxMap *other) {
323 1 return cxMapIntersection(dst, src, other, use_shallow_clone_func(src));
324 }
325
326 1 int cxMapListIntersectionShallow(CxMap *dst, const CxMap *src, const CxList *keys) {
327 1 return cxMapListIntersection(dst, src, keys, use_shallow_clone_func(src));
328 }
329
330 1 int cxMapUnionShallow(CxMap *dst, const CxMap *src) {
331 1 return cxMapUnion(dst, src, use_shallow_clone_func(src));
332 }
333
334 125 int cxMapCompare(const CxMap *map, const CxMap *other) {
335 // compare map sizes
336 125 const size_t size_left = cxMapSize(map);
337 125 const size_t size_right = cxMapSize(other);
338
2/2
✓ Branch 4 → 5 taken 10 times.
✓ Branch 4 → 6 taken 115 times.
 125 if (size_left < size_right) {
339 10 return -1;
340
2/2
✓ Branch 6 → 7 taken 8 times.
✓ Branch 6 → 8 taken 107 times.
 115 } else if (size_left > size_right) {
341 8 return 1;
342 }
343
344 // iterate through the first map
345 107 CxMapIterator iter = cxMapIterator(map);
346
3/4
✓ Branch 22 → 23 taken 297 times.
✓ Branch 22 → 25 taken 87 times.
✓ Branch 24 → 10 taken 297 times.
✗ Branch 24 → 25 not taken.
 384 cx_foreach(const CxMapEntry *, entry, iter) {
347 297 const void *value_left = entry->value;
348 594 const void *value_right = cxMapGet(other, *entry->key);
349 // if the other map does not have the key, we are done
350
2/2
✓ Branch 13 → 14 taken 8 times.
✓ Branch 13 → 15 taken 289 times.
 297 if (value_right == NULL) {
351 8 return -1;
352 }
353 // compare the values
354
2/2
✓ Branch 15 → 16 taken 40 times.
✓ Branch 15 → 17 taken 249 times.
 289 const int d = cx_invoke_compare_func(map, value_left, value_right);
355
2/2
✓ Branch 18 → 19 taken 12 times.
✓ Branch 18 → 20 taken 277 times.
 289 if (d != 0) {
356 12 return d;
357 }
358 }
359
360 87 return 0;
361 }
362