GCC Code Coverage Report

Directory: ./
File: kv_list.c
Date: 2025-12-31 16:19:05
Exec Total Coverage
Lines: 328 328 100.0%
Functions: 38 38 100.0%
Branches: 93 98 94.9%
Line Branch Exec Source
1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
3 *
4 * Copyright 2025 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/kv_list.h"
30 #include "cx/hash_map.h"
31 #include "cx/linked_list.h"
32
33 #include <string.h>
34 #include <assert.h>
35
36 typedef struct cx_kv_list_s cx_kv_list;
37
38 struct cx_kv_list_map_s {
39 struct cx_hash_map_s map_base;
40 /** Back-reference to the list. */
41 cx_kv_list *list;
42 };
43
44 struct cx_kv_list_s {
45 struct cx_linked_list_s list;
46 /** The lookup map - stores pointers to the nodes. */
47 struct cx_kv_list_map_s *map;
48 const cx_list_class *list_methods;
49 const cx_map_class *map_methods;
50 cx_destructor_func list_destr;
51 cx_destructor_func2 list_destr2;
52 void *list_destr_data;
53 cx_destructor_func map_destr;
54 cx_destructor_func2 map_destr2;
55 void *map_destr_data;
56 };
57
58 9425 static void cx_kv_list_destructor_wrapper(void *list_ptr, void *elem) {
59 9425 const cx_kv_list *kv_list = list_ptr;
60 // list destructor is already called with proper deref of the elem
61
2/2
✓ Branch 0 (2→3) taken 164 times.
✓ Branch 1 (2→4) taken 9261 times.
 9425 if (kv_list->list_destr) {
62 164 kv_list->list_destr(elem);
63 }
64
2/2
✓ Branch 0 (4→5) taken 152 times.
✓ Branch 1 (4→6) taken 9273 times.
 9425 if (kv_list->list_destr2) {
65 152 kv_list->list_destr2(kv_list->list_destr_data, elem);
66 }
67
2/2
✓ Branch 0 (6→7) taken 851 times.
✓ Branch 1 (6→8) taken 8574 times.
 9425 if (kv_list->map_destr) {
68 851 kv_list->map_destr(elem);
69 }
70
2/2
✓ Branch 0 (8→9) taken 7 times.
✓ Branch 1 (8→10) taken 9418 times.
 9425 if (kv_list->map_destr2) {
71 7 kv_list->map_destr2(kv_list->map_destr_data, elem);
72 }
73 9425 }
74
75 531 static void cx_kv_list_update_destructors(cx_kv_list *list) {
76 // we copy the destructors to our custom fields and register
77 // an own destructor function which invokes all these
78
2/2
✓ Branch 0 (2→3) taken 8 times.
✓ Branch 1 (2→4) taken 523 times.
 531 if (list->list.base.collection.simple_destructor != NULL) {
79 8 list->list_destr = list->list.base.collection.simple_destructor;
80 8 list->list.base.collection.simple_destructor = NULL;
81 }
82
2/2
✓ Branch 0 (4→5) taken 278 times.
✓ Branch 1 (4→6) taken 253 times.
 531 if (list->list.base.collection.advanced_destructor != cx_kv_list_destructor_wrapper) {
83 278 list->list_destr2 = list->list.base.collection.advanced_destructor;
84 278 list->list_destr_data = list->list.base.collection.destructor_data;
85 278 list->list.base.collection.advanced_destructor = cx_kv_list_destructor_wrapper;
86 278 list->list.base.collection.destructor_data = list;
87 }
88
2/2
✓ Branch 0 (6→7) taken 160 times.
✓ Branch 1 (6→8) taken 371 times.
 531 if (list->map->map_base.base.collection.simple_destructor != NULL) {
89 160 list->map_destr = list->map->map_base.base.collection.simple_destructor;
90 160 list->map->map_base.base.collection.simple_destructor = NULL;
91 }
92
2/2
✓ Branch 0 (8→9) taken 4 times.
✓ Branch 1 (8→10) taken 527 times.
 531 if (list->map->map_base.base.collection.advanced_destructor != NULL) {
93 4 list->map_destr2 = list->map->map_base.base.collection.advanced_destructor;
94 4 list->map_destr_data = list->map->map_base.base.collection.destructor_data;
95 4 list->map->map_base.base.collection.advanced_destructor = NULL;
96 4 list->map->map_base.base.collection.destructor_data = NULL;
97 }
98 531 }
99
100 1744 static CxHashKey *cx_kv_list_loc_key(cx_kv_list *list, void *node_data) {
101 1744 return (CxHashKey*)((char*)node_data - list->list.loc_data + list->list.loc_extra);
102 }
103
104 113 static void cx_kvl_deallocate(struct cx_list_s *list) {
105 113 cx_kv_list *kv_list = (cx_kv_list*)list;
106 // patch the destructors
107 113 cx_kv_list_update_destructors(kv_list);
108 113 kv_list->map_methods->deallocate(&kv_list->map->map_base.base);
109 // then free the list, now the destructors may be called
110 113 kv_list->list_methods->deallocate(list);
111 113 }
112
113 4617 static void *cx_kvl_insert_element(
114 struct cx_list_s *list,
115 size_t index,
116 const void *data
117 ) {
118 4617 cx_kv_list *kv_list = (cx_kv_list*)list;
119 4617 return kv_list->list_methods->insert_element(list, index, data);
120 }
121
122 34 static size_t cx_kvl_insert_array(
123 struct cx_list_s *list,
124 size_t index,
125 const void *data,
126 size_t n
127 ) {
128 34 cx_kv_list *kv_list = (cx_kv_list*)list;
129 34 return kv_list->list_methods->insert_array(list, index, data, n);
130 }
131
132 20 static size_t cx_kvl_insert_sorted(
133 struct cx_list_s *list,
134 const void *sorted_data,
135 size_t n
136 ) {
137 20 cx_kv_list *kv_list = (cx_kv_list*)list;
138 20 return kv_list->list_methods->insert_sorted(list, sorted_data, n);
139 }
140
141 20 static size_t cx_kvl_insert_unique(
142 struct cx_list_s *list,
143 const void *sorted_data,
144 size_t n
145 ) {
146 20 cx_kv_list *kv_list = (cx_kv_list*)list;
147 20 return kv_list->list_methods->insert_unique(list, sorted_data, n);
148 }
149
150 10 static int cx_kvl_insert_iter(
151 struct cx_iterator_s *iter,
152 const void *elem,
153 int prepend
154 ) {
155 10 cx_kv_list *kv_list = iter->src_handle;
156 10 return kv_list->list_methods->insert_iter(iter, elem, prepend);
157 }
158
159 58 static size_t cx_kvl_remove(
160 struct cx_list_s *list,
161 size_t index,
162 size_t num,
163 void *targetbuf
164 ) {
165 58 cx_kv_list *kv_list = (cx_kv_list*)list;
166 // patch the destructors
167 // we also have to do that when targetbuf is NULL,
168 // because we do not want wrong destructors to be called when we remove keys from the map
169 58 cx_kv_list_update_destructors(kv_list);
170 // iterate through the elements first and remove their keys from the map
171 58 CxIterator iter = kv_list->list_methods->iterator(list, index, false);
172
4/4
✓ Branch 0 (11→12) taken 96 times.
✓ Branch 1 (11→14) taken 44 times.
✓ Branch 2 (13→5) taken 82 times.
✓ Branch 3 (13→14) taken 14 times.
 140 for (size_t i = 0; i < num && cxIteratorValid(iter); i++) {
173 82 void *node_data = cxIteratorCurrent(iter);
174 82 CxHashKey *key = cx_kv_list_loc_key(kv_list, node_data);
175 // when the hash is zero, there is no key assigned to that element
176
2/2
✓ Branch 0 (7→8) taken 15 times.
✓ Branch 1 (7→9) taken 67 times.
 82 if (key->hash != 0) {
177 15 kv_list->map_methods->remove(&kv_list->map->map_base.base, *key, NULL);
178 }
179 82 cxIteratorNext(iter);
180 }
181 58 return kv_list->list_methods->remove(list, index, num, targetbuf);
182 }
183
184 10 static void cx_kvl_clear(struct cx_list_s *list) {
185 10 cx_kv_list *kv_list = (cx_kv_list*)list;
186 // patch the destructors
187 10 cx_kv_list_update_destructors(kv_list);
188 // clear the list
189 10 kv_list->list_methods->clear(list);
190 // then clear the map
191 10 kv_list->map_methods->clear(&kv_list->map->map_base.base);
192 10 }
193
194 22 static int cx_kvl_swap(
195 struct cx_list_s *list,
196 size_t i,
197 size_t j
198 ) {
199 22 cx_kv_list *kv_list = (cx_kv_list*)list;
200 22 return kv_list->list_methods->swap(list, i, j);
201 }
202
203 6905 static void *cx_kvl_at(
204 const struct cx_list_s *list,
205 size_t index
206 ) {
207 6905 const cx_kv_list *kv_list = (const cx_kv_list*)list;
208 6905 return kv_list->list_methods->at(list, index);
209 }
210
211 120 static size_t cx_kvl_find_remove(
212 struct cx_list_s *list,
213 const void *elem,
214 bool remove
215 ) {
216 120 cx_kv_list *kv_list = (cx_kv_list*)list;
217 // we do not use the original list methods,
218 // because that would need two passes for removal
219 // (the first to find the index, the second to get a pointer)
220
2/2
✓ Branch 0 (2→3) taken 1 times.
✓ Branch 1 (2→4) taken 119 times.
 120 if (list->collection.size == 0) return 0;
221
222 size_t index;
223 119 cx_linked_list *ll = &kv_list->list;
224 119 char *node = cx_linked_list_find_c(
225 119 ll->begin,
226 119 ll->loc_next, ll->loc_data,
227 elem, &index,
228 cx_list_compare_wrapper,
229 list
230 );
231
2/2
✓ Branch 0 (5→6) taken 41 times.
✓ Branch 1 (5→7) taken 78 times.
 119 if (node == NULL) {
232 41 return list->collection.size;
233 }
234
2/2
✓ Branch 0 (7→8) taken 10 times.
✓ Branch 1 (7→18) taken 68 times.
 78 if (remove) {
235 10 cx_kv_list_update_destructors(kv_list);
236
2/2
✓ Branch 0 (9→10) taken 3 times.
✓ Branch 1 (9→11) taken 7 times.
 10 cx_invoke_advanced_destructor(list, node + ll->loc_data);
237 10 cx_linked_list_remove(&ll->begin, &ll->end,
238 10 ll->loc_prev, ll->loc_next, node);
239 10 CxHashKey *key = cx_kv_list_loc_key(kv_list, node + ll->loc_data);
240
2/2
✓ Branch 0 (15→16) taken 4 times.
✓ Branch 1 (15→17) taken 6 times.
 10 if (key->hash != 0) {
241 4 kv_list->map_methods->remove(&kv_list->map->map_base.base, *key, NULL);
242 }
243 10 list->collection.size--;
244 10 cxFree(list->collection.allocator, node);
245 }
246 78 return index;
247 }
248
249 4 static void cx_kvl_sort(struct cx_list_s *list) {
250 4 cx_kv_list *kv_list = (cx_kv_list*)list;
251 4 kv_list->list_methods->sort(list);
252 4 }
253
254 2 static void cx_kvl_reverse(struct cx_list_s *list) {
255 2 cx_kv_list *kv_list = (cx_kv_list*)list;
256 2 kv_list->list_methods->reverse(list);
257 2 }
258
259 2595 static void cx_kvl_list_iter_next(void *it) {
260 2595 struct cx_iterator_s *iter = it;
261
2/2
✓ Branch 0 (2→3) taken 59 times.
✓ Branch 1 (2→7) taken 2536 times.
 2595 if (iter->base.remove) {
262 // remove the assigned key from the map before calling the actual function
263 59 cx_kv_list *kv_list = iter->src_handle;
264 59 cx_kv_list_update_destructors(kv_list);
265 59 char *node = iter->elem_handle;
266 59 CxHashKey *key = cx_kv_list_loc_key(kv_list, node + kv_list->list.loc_data);
267
2/2
✓ Branch 0 (5→6) taken 1 times.
✓ Branch 1 (5→7) taken 58 times.
 59 if (key->hash != 0) {
268 1 kv_list->map_methods->remove(&kv_list->map->map_base.base, *key, NULL);
269 }
270 }
271 // note that we do not clear the remove flag, because the next_impl will do that
272 2595 iter->base.next_impl(it);
273 2595 }
274
275 109 static struct cx_iterator_s cx_kvl_iterator(
276 const struct cx_list_s *list,
277 size_t index,
278 bool backward
279 ) {
280 109 const cx_kv_list *kv_list = (const cx_kv_list*)list;
281 109 struct cx_iterator_s iter = kv_list->list_methods->iterator(list, index, backward);
282 109 iter.base.next_impl = iter.base.next;
283 109 iter.base.next = cx_kvl_list_iter_next;
284 109 return iter;
285 }
286
287 165 static void cx_kvl_map_deallocate(struct cx_map_s *map) {
288 165 cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list;
289 165 cx_kv_list_update_destructors(kv_list);
290 165 kv_list->map_methods->deallocate(map);
291 165 kv_list->list_methods->deallocate(&kv_list->list.base);
292 165 }
293
294 3 static void cx_kvl_map_clear(struct cx_map_s *map) {
295 3 cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list;
296 3 cx_kv_list_update_destructors(kv_list);
297 3 kv_list->list_methods->clear(&kv_list->list.base);
298 3 kv_list->map_methods->clear(map);
299 3 }
300
301 326 static void *cx_kvl_map_get(const CxMap *map, CxHashKey key) {
302 326 cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list;
303 326 void *node_data = kv_list->map_methods->get(map, key);
304 − if (node_data == NULL) return NULL; // LCOV_EXCL_LINE
305 // return the node data
306
2/2
✓ Branch 0 (5→6) taken 261 times.
✓ Branch 1 (5→7) taken 41 times.
 302 return kv_list->list.base.collection.store_pointer ? *(void**)node_data : node_data;
307 }
308
309 913 static int cx_kvl_map_remove(CxMap *map, CxHashKey key, void *targetbuf) {
310 913 cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list;
311
312 void *node_data;
313
2/2
✓ Branch 0 (3→4) taken 799 times.
✓ Branch 1 (3→5) taken 114 times.
 913 if (kv_list->map_methods->remove(map, key, &node_data)) {
314 799 return 1;
315 }
316 // we cannot just call a list method (because we don't have the index)
317 // and tbh. we also don't want to (because it's not performant when we
318 // can have the node ptr directly instead)
319 // therefore, we re-implement the logic ourselves
320
321 // check if the outside caller want's us to return or to destroy the element
322
2/2
✓ Branch 0 (5→6) taken 112 times.
✓ Branch 1 (5→11) taken 2 times.
 114 if (targetbuf == NULL) {
323 // patch the destructors and invoke them through the wrapper
324 112 cx_kv_list_update_destructors(kv_list);
325
2/2
✓ Branch 0 (7→8) taken 102 times.
✓ Branch 1 (7→9) taken 10 times.
 112 cx_invoke_advanced_destructor(&kv_list->list.base, node_data);
326 } else {
327 // copy the element to the target buffer
328 2 memcpy(targetbuf, node_data, kv_list->list.base.collection.elem_size);
329 }
330
331 // calculate the address of the node
332 114 void *node_ptr = (char*)node_data - kv_list->list.loc_data;
333
334 // unlink the node
335 114 cx_linked_list_remove(
336 &kv_list->list.begin,
337 &kv_list->list.end,
338 114 kv_list->list.loc_prev,
339 114 kv_list->list.loc_next,
340 node_ptr
341 );
342
343 // decrement the list's size
344 114 kv_list->list.base.collection.size--;
345
346 // deallocate the node
347 114 cxFree(kv_list->list.base.collection.allocator, node_ptr);
348
349 114 return 0;
350 }
351
352 897 static CxMapEntry cx_kvl_map_put(CxMap *map, CxHashKey key, void *value) {
353 897 cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list;
354 // if the hash has not yet been computed, do it now
355
2/2
✓ Branch 0 (2→3) taken 1 times.
✓ Branch 1 (2→4) taken 896 times.
 897 if (key.hash == 0) {
356 1 cx_hash_murmur(&key);
357 }
358
359 // remove any existing element first
360 897 cx_kvl_map_remove(map, key, NULL);
361
362 // now reserve new memory in the map
363 897 CxMapEntry map_entry = kv_list->map_methods->put(map, key, NULL);
364 − if (map_entry.key == NULL) return (CxMapEntry){NULL, NULL}; // LCOV_EXCL_LINE
365
366 // insert the data into the list (which most likely destroys the sorted property)
367 897 kv_list->list.base.collection.sorted = false;
368 897 void *node_data = kv_list->list_methods->insert_element(
369 &kv_list->list.base, kv_list->list.base.collection.size,
370
2/2
✓ Branch 0 (9→10) taken 850 times.
✓ Branch 1 (9→11) taken 47 times.
 897 kv_list->list.base.collection.store_pointer ? &value : value);
371 − if (node_data == NULL) { // LCOV_EXCL_START
372 // non-destructively remove the key again
373 void *dummy;
374 − kv_list->map_methods->remove(&kv_list->map->map_base.base, key, &dummy);
375 − return (CxMapEntry){NULL, NULL};
376 } // LCOV_EXCL_STOP
377
378 // write the node pointer to the map entry
379 897 *(void**)map_entry.value = node_data;
380
381 // copy the key to the node data
382 897 CxHashKey *key_ptr = cx_kv_list_loc_key(kv_list, node_data);
383 897 *key_ptr = *map_entry.key;
384
385 // we must return an entry that points to the node data!
386 897 return (CxMapEntry ){key_ptr, node_data};
387 }
388
389 661 static void *cx_kvl_iter_current_entry(const void *it) {
390 661 const CxMapIterator *iter = it;
391 661 return (void*)&iter->entry;
392 }
393
394 1 static void *cx_kvl_iter_current_key(const void *it) {
395 1 const CxMapEntry *entry = cx_kvl_iter_current_entry(it);
396 1 return (void*)entry->key;
397 }
398
399 3 static void *cx_kvl_iter_current_value(const void *it) {
400 3 const CxMapEntry *entry = cx_kvl_iter_current_entry(it);
401 3 return entry->value;
402 }
403
404 656 static void cx_kvl_iter_next(void *it) {
405 656 CxMapIterator *iter = it;
406 656 cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)iter->map)->list;
407
408 // find the next list entry that has a key assigned
409 656 CxHashKey *key = NULL;
410 656 char *next = iter->elem;
411 while (true) {
412 657 next = *(char**)(next + kv_list->list.loc_next);
413
2/2
✓ Branch 0 (3→4) taken 132 times.
✓ Branch 1 (3→5) taken 525 times.
 657 if (next == NULL) break;
414 525 key = cx_kv_list_loc_key(kv_list, next + kv_list->list.loc_data);
415
2/2
✓ Branch 0 (6→7) taken 524 times.
✓ Branch 1 (6→8) taken 1 times.
 525 if (key->hash != 0) break;
416 }
417
418 // remove previous element if requested
419
2/2
✓ Branch 0 (9→10) taken 1 times.
✓ Branch 1 (9→20) taken 655 times.
 656 if (iter->base.remove) {
420 1 iter->base.remove = false;
421 1 cx_kv_list_update_destructors(kv_list);
422 1 char *elem = iter->elem;
423 1 char *elem_data = elem + kv_list->list.loc_data;
424 1 CxHashKey *elem_key = cx_kv_list_loc_key(kv_list, elem_data);
425 // key is guaranteed to exist because iterator only iterates over elems with a key
426 1 kv_list->map_methods->remove(&kv_list->map->map_base.base, *elem_key, NULL);
427
1/2
✓ Branch 0 (13→14) taken 1 times.
✗ Branch 1 (13→15) not taken.
 1 cx_invoke_advanced_destructor(&kv_list->list.base, elem_data);
428 1 cx_linked_list_remove(
429 &kv_list->list.begin,
430 &kv_list->list.end,
431 1 kv_list->list.loc_prev,
432 1 kv_list->list.loc_next,
433 elem
434 );
435 1 cxFree(kv_list->list.base.collection.allocator, elem);
436 1 kv_list->list.base.collection.size--;
437 1 iter->index--;
438 1 iter->elem_count--;
439 }
440
441 // advance to the next element, if any
442
2/2
✓ Branch 0 (20→21) taken 132 times.
✓ Branch 1 (20→22) taken 524 times.
 656 if (next == NULL) {
443 132 iter->index = kv_list->list.base.collection.size;
444 132 iter->elem = NULL;
445 132 iter->entry = (CxMapEntry){NULL, NULL};
446 132 return;
447 }
448 524 iter->index++;
449 524 iter->elem = next;
450 524 iter->entry.key = key;
451
2/2
✓ Branch 0 (22→23) taken 522 times.
✓ Branch 1 (22→24) taken 2 times.
 524 if (kv_list->list.base.collection.store_pointer) {
452 522 iter->entry.value = *(void**)(next + kv_list->list.loc_data);
453 } else {
454 2 iter->entry.value = (void*)(next + kv_list->list.loc_data);
455 }
456 }
457
458 680 static bool cx_kvl_iter_valid(const void *it) {
459 680 const CxMapIterator *iter = it;
460 680 return iter->elem != NULL;
461 }
462
463 166 static CxMapIterator cx_kvl_map_iterator(const CxMap *map, enum cx_map_iterator_type type) {
464 166 CxMapIterator iter = {0};
465
466 166 iter.type = type;
467 166 iter.map = (CxMap*)map;
468 // although we iterate over the list, we only report that many elements that have a key in the map
469 166 iter.elem_count = map->collection.size;
470
471
3/4
✓ Branch 0 (2→3) taken 164 times.
✓ Branch 1 (2→4) taken 1 times.
✓ Branch 2 (2→5) taken 1 times.
✗ Branch 3 (2→6) not taken.
 166 switch (type) {
472 164 case CX_MAP_ITERATOR_PAIRS:
473 164 iter.elem_size = sizeof(CxMapEntry);
474 164 iter.base.current = cx_kvl_iter_current_entry;
475 164 break;
476 1 case CX_MAP_ITERATOR_KEYS:
477 1 iter.elem_size = sizeof(CxHashKey);
478 1 iter.base.current = cx_kvl_iter_current_key;
479 1 break;
480 1 case CX_MAP_ITERATOR_VALUES:
481 1 iter.elem_size = map->collection.elem_size;
482 1 iter.base.current = cx_kvl_iter_current_value;
483 1 break;
484 166 default:
485 assert(false); // LCOV_EXCL_LINE
486 }
487
488 166 iter.base.allow_remove = true;
489 166 iter.base.next = cx_kvl_iter_next;
490 166 iter.base.valid = cx_kvl_iter_valid;
491
492 // find the first list entry that has a key assigned
493 166 cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list;
494 166 CxHashKey *key = NULL;
495 166 char *next = kv_list->list.begin;
496
2/2
✓ Branch 0 (11→7) taken 141 times.
✓ Branch 1 (11→12) taken 29 times.
 170 while (next != NULL) {
497 141 key = cx_kv_list_loc_key(kv_list, next + kv_list->list.loc_data);
498
2/2
✓ Branch 0 (8→9) taken 137 times.
✓ Branch 1 (8→10) taken 4 times.
 141 if (key->hash != 0) break;
499 4 next = *(char**)(next + kv_list->list.loc_next);
500 }
501
2/2
✓ Branch 0 (12→13) taken 29 times.
✓ Branch 1 (12→14) taken 137 times.
 166 if (next == NULL) {
502 29 iter.elem = NULL;
503 29 iter.entry = (CxMapEntry){NULL, NULL};
504 } else {
505 137 iter.elem = next;
506 137 iter.entry.key = key;
507
2/2
✓ Branch 0 (14→15) taken 135 times.
✓ Branch 1 (14→16) taken 2 times.
 137 if (kv_list->list.base.collection.store_pointer) {
508 135 iter.entry.value = *(void**)(next + kv_list->list.loc_data);
509 } else {
510 2 iter.entry.value = (void*)(next + kv_list->list.loc_data);
511 }
512 }
513
514 166 return iter;
515 }
516
517 4 static int cx_kvl_change_capacity(struct cx_list_s *list,
518 CX_UNUSED size_t cap) {
519 // since our backing list is a linked list, we don't need to do much here,
520 // but rehashing the map is quite useful
521 4 cx_kv_list *kv_list = (cx_kv_list*)list;
522 4 cxMapRehash(&kv_list->map->map_base.base);
523 4 return 0;
524 }
525
526 static cx_list_class cx_kv_list_class = {
527 cx_kvl_deallocate,
528 cx_kvl_insert_element,
529 cx_kvl_insert_array,
530 cx_kvl_insert_sorted,
531 cx_kvl_insert_unique,
532 cx_kvl_insert_iter,
533 cx_kvl_remove,
534 cx_kvl_clear,
535 cx_kvl_swap,
536 cx_kvl_at,
537 cx_kvl_find_remove,
538 cx_kvl_sort,
539 NULL,
540 cx_kvl_reverse,
541 cx_kvl_change_capacity,
542 cx_kvl_iterator,
543 };
544
545 static cx_map_class cx_kv_map_class = {
546 cx_kvl_map_deallocate,
547 cx_kvl_map_clear,
548 cx_kvl_map_put,
549 cx_kvl_map_get,
550 cx_kvl_map_remove,
551 cx_kvl_map_iterator,
552 };
553
554 278 CxList *cxKvListCreate(
555 const CxAllocator *allocator,
556 size_t elem_size
557 ) {
558
2/2
✓ Branch 0 (2→3) taken 37 times.
✓ Branch 1 (2→4) taken 241 times.
 278 if (allocator == NULL) {
559 37 allocator = cxDefaultAllocator;
560 }
561
562 // create a normal linked list and a normal hash map, first
563 278 CxList *list = cxLinkedListCreate(allocator, elem_size);
564 − if (list == NULL) return NULL; // LCOV_EXCL_LINE
565 278 cx_linked_list *ll = (cx_linked_list*)list;
566 278 cx_linked_list_extra_data(ll, sizeof(CxHashKey));
567 278 CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 0);
568 − if (map == NULL) { // LCOV_EXCL_START
569 − cxListFree(list);
570 − return NULL;
571 } // LCOV_EXCL_STOP
572
573 // patch the kv-list class with the compare function of the linked list
574 // this allows cxListCompare() to optimize comparisons between linked lists and kv-list
575 278 cx_kv_list_class.compare = list->cl->compare;
576
577 // reallocate the map to add memory for the list back-reference
578 278 struct cx_kv_list_map_s *kv_map = cxRealloc(allocator, map, sizeof(struct cx_kv_list_map_s));
579
580 // reallocate the list to add memory for storing the metadata
581 278 cx_kv_list *kv_list = cxRealloc(allocator, list, sizeof(struct cx_kv_list_s));
582
583 // if any of the reallocations failed, we bail out
584
2/4
✓ Branch 0 (14→15) taken 278 times.
✗ Branch 1 (14→17) not taken.
✓ Branch 2 (15→16) taken 278 times.
✗ Branch 3 (15→17) not taken.
 278 if (kv_map != NULL && kv_list != NULL) {
585 278 map = (CxMap*) kv_map;
586 278 list = (CxList*) kv_list;
587 } else { // LCOV_EXCL_START
588 − cxListFree(list);
589 − cxMapFree(map);
590 − return NULL;
591 } // LCOV_EXCL_STOP
592
593 // zero the custom destructor information
594 278 memset((char*)kv_list + offsetof(cx_kv_list, list_destr), 0, sizeof(void*)*6);
595
596 // combine the list and the map aspect
597 278 kv_list->map = kv_map;
598 278 kv_map->list = kv_list;
599
600 // remember the base methods and override them
601 278 kv_list->map_methods = map->cl;
602 278 map->cl = &cx_kv_map_class;
603 278 kv_list->list_methods = list->cl;
604 278 list->cl = &cx_kv_list_class;
605
606 278 return list;
607 }
608
609 165 CxMap *cxKvListCreateAsMap(
610 const CxAllocator *allocator,
611 size_t elem_size
612 ) {
613 165 CxList *list = cxKvListCreate(allocator, elem_size);
614
1/2
✓ Branch 0 (3→4) taken 165 times.
✗ Branch 1 (3→5) not taken.
 165 return list == NULL ? NULL : cxKvListAsMap(list);
615 }
616
617 11 CxList *cxKvListAsList(CxMap *map) {
618 11 return &((struct cx_kv_list_map_s*)map)->list->list.base;
619 }
620
621 189 CxMap *cxKvListAsMap(CxList *list) {
622 189 return &((cx_kv_list*)list)->map->map_base.base;
623 }
624
625 19 int cx_kv_list_set_key(CxList *list, size_t index, CxHashKey key) {
626 19 cx_kv_list *kv_list = (cx_kv_list*)list;
627 19 void *node_data = kv_list->list_methods->at(list, index);
628
2/2
✓ Branch 0 (3→4) taken 1 times.
✓ Branch 1 (3→5) taken 18 times.
 19 if (node_data == NULL) {
629 1 return 1;
630 }
631 // if the hash has not yet been computed, do it now
632
2/2
✓ Branch 0 (5→6) taken 1 times.
✓ Branch 1 (5→7) taken 17 times.
 18 if (key.hash == 0) {
633 1 cx_hash_murmur(&key);
634 }
635
636 // check if the key is already assigned
637 18 void *existing = kv_list->map_methods->get(&kv_list->map->map_base.base, key);
638
2/2
✓ Branch 0 (8→9) taken 1 times.
✓ Branch 1 (8→10) taken 17 times.
 18 if (existing == node_data) {
639 1 return 0; // nothing to do
640 }
641
2/2
✓ Branch 0 (10→11) taken 1 times.
✓ Branch 1 (10→12) taken 16 times.
 17 if (existing != NULL) {
642 // the key is already assigned to another node, we disallow re-assignment
643 1 return 1;
644 }
645
646 // add the key to the map
647 16 const CxMapEntry entry = kv_list->map_methods->put(
648 16 &kv_list->map->map_base.base, key, node_data);
649 − if (entry.key == NULL) return 1; // LCOV_EXCL_LINE
650
651 // write the key to the list's node
652 16 CxHashKey *loc_key = cx_kv_list_loc_key(kv_list, node_data);
653 16 *loc_key = *entry.key;
654
655 16 return 0;
656 }
657
658 5 int cxKvListRemoveKey(CxList *list, size_t index) {
659 5 cx_kv_list *kv_list = (cx_kv_list*)list;
660 5 void *node_data = kv_list->list_methods->at(list, index);
661
2/2
✓ Branch 0 (3→4) taken 1 times.
✓ Branch 1 (3→5) taken 4 times.
 5 if (node_data == NULL) {
662 1 return 1;
663 }
664 4 CxHashKey *loc_key = cx_kv_list_loc_key(kv_list, node_data);
665
2/2
✓ Branch 0 (6→7) taken 1 times.
✓ Branch 1 (6→8) taken 3 times.
 4 if (loc_key->hash == 0) {
666 1 return 0;
667 }
668 3 kv_list->map_methods->remove(&kv_list->map->map_base.base, *loc_key, NULL);
669 // also zero the memory in the list node,
670 // but don't free the key data (that was done by the map remove)
671 3 memset(loc_key, 0, sizeof(CxHashKey));
672 3 return 0;
673 }
674
675 4 const CxHashKey *cxKvListGetKey(CxList *list, size_t index) {
676 4 cx_kv_list *kv_list = (cx_kv_list*)list;
677 4 void *node_data = kv_list->list_methods->at(list, index);
678
2/2
✓ Branch 0 (3→4) taken 1 times.
✓ Branch 1 (3→5) taken 3 times.
 4 if (node_data == NULL) {
679 1 return NULL;
680 }
681 3 CxHashKey *key = cx_kv_list_loc_key(kv_list, node_data);
682
2/2
✓ Branch 0 (6→7) taken 1 times.
✓ Branch 1 (6→8) taken 2 times.
 3 if (key->hash == 0) {
683 1 return NULL;
684 }
685 2 return key;
686 }
687
688 6 int cx_kv_list_insert(CxList *list, size_t index, CxHashKey key, void *value) {
689 // assume we are losing the sorted property
690 6 list->collection.sorted = false;
691
692 6 cx_kv_list *kv_list = (cx_kv_list*)list;
693
694 // reserve memory in the map
695 6 CxMapEntry map_entry = kv_list->map_methods->put(&kv_list->map->map_base.base, key, NULL);
696 − if (map_entry.key == NULL) return 1; // LCOV_EXCL_LINE
697
698 // insert the node
699 6 void *node_data = kv_list->list_methods->insert_element(&kv_list->list.base, index,
700
2/2
✓ Branch 0 (5→6) taken 3 times.
✓ Branch 1 (5→7) taken 3 times.
 6 kv_list->list.base.collection.store_pointer ? &value : value);
701 − if (node_data == NULL) { // LCOV_EXCL_START
702 // non-destructively remove the key again
703 void *dummy;
704 − kv_list->map_methods->remove(&kv_list->map->map_base.base, key, &dummy);
705 − return 1;
706 } // LCOV_EXCL_STOP
707 6 *(void**)map_entry.value = node_data;
708
709 // write the key to the node
710 6 CxHashKey *loc_key = cx_kv_list_loc_key(kv_list, node_data);
711 6 *loc_key = *map_entry.key;
712
713 6 return 0;
714 }
715