GCC Code Coverage Report

Directory: ./
File: list.c
Date: 2025-11-30 14:18:36
Exec Total Coverage
Lines: 555 555 100.0%
Functions: 84 84 100.0%
Branches: 267 300 89.0%
Line Branch Exec Source
1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
3 *
4 * Copyright 2021 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/list.h"
30
31 #include <string.h>
32 #include <assert.h>
33
34 // <editor-fold desc="Store Pointers Functionality">
35
36 static _Thread_local cx_compare_func cx_pl_cmpfunc_impl;
37
38 47227 static int cx_pl_cmpfunc(
39 const void *l,
40 const void *r
41 ) {
42 // l and r are guaranteed to be non-NULL pointing to the list's memory
43 47227 void *const *lptr = l;
44 47227 void *const *rptr = r;
45 47227 const void *left = *lptr;
46 47227 const void *right = *rptr;
47
2/2
✓ Branch 0 (2→3) taken 2 times.
✓ Branch 1 (2→7) taken 47225 times.
 47227 if (left == NULL) {
48 // NULL is smaller than any value except NULL
49
2/2
✓ Branch 0 (3→4) taken 1 times.
✓ Branch 1 (3→5) taken 1 times.
 2 return right == NULL ? 0 : -1;
50
2/2
✓ Branch 0 (7→8) taken 4 times.
✓ Branch 1 (7→9) taken 47221 times.
 47225 } else if (right == NULL) {
51 // any value is larger than NULL
52 4 return 1;
53 }
54 47221 return cx_pl_cmpfunc_impl(left, right);
55 }
56
57 334 static void cx_pl_hack_cmpfunc(const struct cx_list_s *list) {
58 // cast away const - this is the hacky thing
59 334 struct cx_collection_s *l = (struct cx_collection_s*) &list->collection;
60 334 cx_pl_cmpfunc_impl = l->cmpfunc;
61 334 l->cmpfunc = cx_pl_cmpfunc;
62 334 }
63
64 334 static void cx_pl_unhack_cmpfunc(const struct cx_list_s *list) {
65 // cast away const - this is the hacky thing
66 334 struct cx_collection_s *l = (struct cx_collection_s*) &list->collection;
67 334 l->cmpfunc = cx_pl_cmpfunc_impl;
68 334 }
69
70 191 static void cx_pl_destructor(struct cx_list_s *list) {
71 191 list->climpl->deallocate(list);
72 191 }
73
74 13122 static void *cx_pl_insert_element(
75 struct cx_list_s *list,
76 size_t index,
77 const void *element
78 ) {
79 13122 return list->climpl->insert_element(list, index, &element);
80 }
81
82 46 static size_t cx_pl_insert_array(
83 struct cx_list_s *list,
84 size_t index,
85 const void *array,
86 size_t n
87 ) {
88 46 return list->climpl->insert_array(list, index, array, n);
89 }
90
91 50 static size_t cx_pl_insert_sorted(
92 struct cx_list_s *list,
93 const void *array,
94 size_t n
95 ) {
96 50 cx_pl_hack_cmpfunc(list);
97 50 size_t result = list->climpl->insert_sorted(list, array, n);
98 50 cx_pl_unhack_cmpfunc(list);
99 50 return result;
100 }
101
102 50 static size_t cx_pl_insert_unique(
103 struct cx_list_s *list,
104 const void *array,
105 size_t n
106 ) {
107 50 cx_pl_hack_cmpfunc(list);
108 50 size_t result = list->climpl->insert_unique(list, array, n);
109 50 cx_pl_unhack_cmpfunc(list);
110 50 return result;
111 }
112
113 15 static int cx_pl_insert_iter(
114 struct cx_iterator_s *iter,
115 const void *elem,
116 int prepend
117 ) {
118 15 struct cx_list_s *list = iter->src_handle;
119 15 return list->climpl->insert_iter(iter, &elem, prepend);
120 }
121
122 84 static size_t cx_pl_remove(
123 struct cx_list_s *list,
124 size_t index,
125 size_t num,
126 void *targetbuf
127 ) {
128 84 return list->climpl->remove(list, index, num, targetbuf);
129 }
130
131 12 static void cx_pl_clear(struct cx_list_s *list) {
132 12 list->climpl->clear(list);
133 12 }
134
135 55 static int cx_pl_swap(
136 struct cx_list_s *list,
137 size_t i,
138 size_t j
139 ) {
140 55 return list->climpl->swap(list, i, j);
141 }
142
143 9026 static void *cx_pl_at(
144 const struct cx_list_s *list,
145 size_t index
146 ) {
147 9026 void **ptr = list->climpl->at(list, index);
148
2/2
✓ Branch 0 (3→4) taken 9023 times.
✓ Branch 1 (3→5) taken 3 times.
 9026 return ptr == NULL ? NULL : *ptr;
149 }
150
151 205 static size_t cx_pl_find_remove(
152 struct cx_list_s *list,
153 const void *elem,
154 bool remove
155 ) {
156 205 cx_pl_hack_cmpfunc(list);
157 205 size_t ret = list->climpl->find_remove(list, &elem, remove);
158 205 cx_pl_unhack_cmpfunc(list);
159 205 return ret;
160 }
161
162 15 static void cx_pl_sort(struct cx_list_s *list) {
163 15 cx_pl_hack_cmpfunc(list);
164 15 list->climpl->sort(list);
165 15 cx_pl_unhack_cmpfunc(list);
166 15 }
167
168 14 static int cx_pl_compare(
169 const struct cx_list_s *list,
170 const struct cx_list_s *other
171 ) {
172 14 cx_pl_hack_cmpfunc(list);
173 14 int ret = list->climpl->compare(list, other);
174 14 cx_pl_unhack_cmpfunc(list);
175 14 return ret;
176 }
177
178 3 static void cx_pl_reverse(struct cx_list_s *list) {
179 3 list->climpl->reverse(list);
180 3 }
181
182 5378 static void *cx_pl_iter_current(const void *it) {
183 5378 const struct cx_iterator_s *iter = it;
184 5378 void **ptr = iter->base.current_impl(it);
185
1/2
✓ Branch 0 (3→4) taken 5378 times.
✗ Branch 1 (3→5) not taken.
 5378 return ptr == NULL ? NULL : *ptr;
186 }
187
188 6 static int cx_pl_change_capacity(struct cx_list_s *list, size_t cap) {
189
2/2
✓ Branch 0 (2→3) taken 2 times.
✓ Branch 1 (2→4) taken 4 times.
 6 if (list->climpl->change_capacity == NULL) {
190 2 return 0;
191 } else {
192 4 return list->climpl->change_capacity(list, cap);
193 }
194 }
195
196 238 static struct cx_iterator_s cx_pl_iterator(
197 const struct cx_list_s *list,
198 size_t index,
199 bool backwards
200 ) {
201 238 struct cx_iterator_s iter = list->climpl->iterator(list, index, backwards);
202 238 iter.base.current_impl = iter.base.current;
203 238 iter.base.current = cx_pl_iter_current;
204 238 return iter;
205 }
206
207 static cx_list_class cx_pointer_list_class = {
208 cx_pl_destructor,
209 cx_pl_insert_element,
210 cx_pl_insert_array,
211 cx_pl_insert_sorted,
212 cx_pl_insert_unique,
213 cx_pl_insert_iter,
214 cx_pl_remove,
215 cx_pl_clear,
216 cx_pl_swap,
217 cx_pl_at,
218 cx_pl_find_remove,
219 cx_pl_sort,
220 cx_pl_compare,
221 cx_pl_reverse,
222 cx_pl_change_capacity,
223 cx_pl_iterator,
224 };
225 // </editor-fold>
226
227 // <editor-fold desc="empty list implementation">
228
229 2 static void cx_emptyl_noop(cx_attr_unused CxList *list) {
230 // this is a noop, but MUST be implemented
231 2 }
232
233 2 static void *cx_emptyl_at(
234 cx_attr_unused const struct cx_list_s *list,
235 cx_attr_unused size_t index
236 ) {
237 2 return NULL;
238 }
239
240 2 static size_t cx_emptyl_find_remove(
241 cx_attr_unused struct cx_list_s *list,
242 cx_attr_unused const void *elem,
243 cx_attr_unused bool remove
244 ) {
245 2 return 0;
246 }
247
248 12 static bool cx_emptyl_iter_valid(cx_attr_unused const void *iter) {
249 12 return false;
250 }
251
252 12 static CxIterator cx_emptyl_iterator(
253 const struct cx_list_s *list,
254 size_t index,
255 cx_attr_unused bool backwards
256 ) {
257 12 CxIterator iter = {0};
258 12 iter.src_handle = (void*) list;
259 12 iter.index = index;
260 12 iter.base.valid = cx_emptyl_iter_valid;
261 12 return iter;
262 }
263
264 static cx_list_class cx_empty_list_class = {
265 cx_emptyl_noop,
266 NULL,
267 NULL,
268 NULL,
269 NULL,
270 NULL,
271 NULL,
272 cx_emptyl_noop,
273 NULL,
274 cx_emptyl_at,
275 cx_emptyl_find_remove,
276 cx_emptyl_noop,
277 NULL,
278 cx_emptyl_noop,
279 NULL,
280 cx_emptyl_iterator,
281 };
282
283 CxList cx_empty_list = {
284 {
285 NULL,
286 NULL,
287 0,
288 0,
289 NULL,
290 NULL,
291 NULL,
292 false,
293 true,
294 },
295 &cx_empty_list_class,
296 NULL
297 };
298
299 CxList *const cxEmptyList = &cx_empty_list;
300
301 // </editor-fold>
302
303 #define invoke_list_func(name, list, ...) \
304 ((list)->climpl == NULL ? (list)->cl->name : (list)->climpl->name) \
305 (list, __VA_ARGS__)
306
307 67 size_t cx_list_default_insert_array(
308 struct cx_list_s *list,
309 size_t index,
310 const void *data,
311 size_t n
312 ) {
313 67 const char *src = data;
314 67 size_t i = 0;
315
2/2
✓ Branch 0 (12→3) taken 741 times.
✓ Branch 1 (12→13) taken 67 times.
 808 for (; i < n; i++) {
316
3/4
✓ Branch 0 (3→4) taken 661 times.
✓ Branch 1 (3→5) taken 80 times.
✗ Branch 2 (7→8) not taken.
✓ Branch 3 (7→9) taken 741 times.
 741 if (NULL == invoke_list_func(
317 insert_element, list, index + i, src)
318 ) {
319 − return i; // LCOV_EXCL_LINE
320 }
321
2/2
✓ Branch 0 (9→10) taken 701 times.
✓ Branch 1 (9→11) taken 40 times.
 741 if (src != NULL) {
322 701 src += list->collection.elem_size;
323 }
324 }
325 67 return i;
326 }
327
328 83 static size_t cx_list_default_insert_sorted_impl(
329 struct cx_list_s *list,
330 const void *sorted_data,
331 size_t n,
332 bool allow_duplicates
333 ) {
334 // corner case
335
1/2
✗ Branch 0 (2→3) not taken.
✓ Branch 1 (2→4) taken 83 times.
 83 if (n == 0) return 0;
336
337 83 size_t elem_size = list->collection.elem_size;
338 83 cx_compare_func cmp = list->collection.cmpfunc;
339 83 const char *src = sorted_data;
340
341 // track indices and number of inserted items
342 83 size_t di = 0, si = 0, processed = 0;
343
344 // search the list for insertion points
345
2/2
✓ Branch 0 (49→5) taken 603 times.
✓ Branch 1 (49→50) taken 31 times.
 634 while (di < list->collection.size) {
346
2/2
✓ Branch 0 (5→6) taken 311 times.
✓ Branch 1 (5→7) taken 292 times.
 603 const void *list_elm = invoke_list_func(at, list, di);
347
348 // compare the current list element with the first source element
349 // if less, skip the list elements
350 // if equal, skip the list elements and optionally the source elements
351 {
352 603 int d = cmp(list_elm, src);
353
2/2
✓ Branch 0 (10→11) taken 494 times.
✓ Branch 1 (10→21) taken 109 times.
 603 if (d <= 0) {
354
4/4
✓ Branch 0 (11→12) taken 250 times.
✓ Branch 1 (11→20) taken 244 times.
✓ Branch 2 (12→13) taken 20 times.
✓ Branch 3 (12→20) taken 230 times.
 494 if (!allow_duplicates && d == 0) {
355 20 src += elem_size;
356 20 si++;
357 20 processed++; // we also count duplicates for the return value
358
4/4
✓ Branch 0 (15→16) taken 16 times.
✓ Branch 1 (15→18) taken 8 times.
✓ Branch 2 (17→14) taken 4 times.
✓ Branch 3 (17→18) taken 12 times.
 24 while (si < n && cmp(list_elm, src) == 0) {
359 4 src += elem_size;
360 4 si++;
361 4 processed++;
362 }
363
2/2
✓ Branch 0 (18→19) taken 8 times.
✓ Branch 1 (18→20) taken 12 times.
 20 if (processed == n) {
364 8 return processed;
365 }
366 }
367 486 di++;
368 486 continue;
369 }
370 }
371
372 // determine the number of consecutive elements that can be inserted
373 109 size_t ins = 1, skip = 0;
374 109 const char *next = src;
375
2/2
✓ Branch 0 (32→22) taken 125 times.
✓ Branch 1 (32→33) taken 44 times.
 169 while (++si < n) {
376
2/2
✓ Branch 0 (22→23) taken 77 times.
✓ Branch 1 (22→28) taken 48 times.
 125 if (!allow_duplicates) {
377 // skip duplicates within the source
378
2/2
✓ Branch 0 (24→25) taken 21 times.
✓ Branch 1 (24→26) taken 56 times.
 77 if (cmp(next, next + elem_size) == 0) {
379 21 next += elem_size;
380 21 skip++;
381 21 continue;
382 } else {
383
2/2
✓ Branch 0 (26→27) taken 17 times.
✓ Branch 1 (26→28) taken 39 times.
 56 if (skip > 0) {
384 // if we had to skip something, we must wait for the next run
385 17 next += elem_size;
386 17 break;
387 }
388 }
389 }
390 87 next += elem_size;
391 // once we become larger than the list elem, break
392
2/2
✓ Branch 0 (29→30) taken 48 times.
✓ Branch 1 (29→31) taken 39 times.
 87 if (cmp(list_elm, next) <= 0) {
393 48 break;
394 }
395 // otherwise, we can insert one more
396 39 ins++;
397 }
398
399 // insert the elements at location si
400
2/2
✓ Branch 0 (33→34) taken 79 times.
✓ Branch 1 (33→40) taken 30 times.
 109 if (ins == 1) {
401
3/4
✓ Branch 0 (34→35) taken 43 times.
✓ Branch 1 (34→36) taken 36 times.
✗ Branch 2 (38→39) not taken.
✓ Branch 3 (38→46) taken 79 times.
 79 if (NULL == invoke_list_func(insert_element, list, di, src)) {
402 − return processed; // LCOV_EXCL_LINE
403 }
404 } else {
405
2/2
✓ Branch 0 (40→41) taken 16 times.
✓ Branch 1 (40→42) taken 14 times.
 30 size_t r = invoke_list_func(insert_array, list, di, src, ins);
406
1/2
✗ Branch 0 (44→45) not taken.
✓ Branch 1 (44→46) taken 30 times.
 30 if (r < ins) {
407 − return processed + r; // LCOV_EXCL_LINE
408 }
409 }
410 109 processed += ins + skip;
411 109 di += ins;
412
413 // everything inserted?
414
2/2
✓ Branch 0 (46→47) taken 44 times.
✓ Branch 1 (46→48) taken 65 times.
 109 if (processed == n) {
415 44 return processed;
416 }
417 65 src = next;
418 }
419
420 // insert remaining items
421
1/2
✓ Branch 0 (50→51) taken 31 times.
✗ Branch 1 (50→76) not taken.
 31 if (si < n) {
422
2/2
✓ Branch 0 (51→52) taken 17 times.
✓ Branch 1 (51→57) taken 14 times.
 31 if (allow_duplicates) {
423
2/2
✓ Branch 0 (52→53) taken 9 times.
✓ Branch 1 (52→54) taken 8 times.
 17 processed += invoke_list_func(insert_array, list, di, src, n - si);
424 } else {
425
4/4
✓ Branch 0 (57→58) taken 9 times.
✓ Branch 1 (57→62) taken 5 times.
✓ Branch 2 (58→59) taken 5 times.
✓ Branch 3 (58→60) taken 4 times.
 14 const void *last = di == 0 ? NULL : invoke_list_func(at, list, di - 1);
426
2/2
✓ Branch 0 (75→64) taken 37 times.
✓ Branch 1 (75→76) taken 14 times.
 51 for (; si < n; si++) {
427 // skip duplicates within the source
428
4/4
✓ Branch 0 (64→65) taken 32 times.
✓ Branch 1 (64→67) taken 5 times.
✓ Branch 2 (66→67) taken 27 times.
✓ Branch 3 (66→74) taken 5 times.
 37 if (last == NULL || cmp(last, src) != 0) {
429
3/4
✓ Branch 0 (67→68) taken 26 times.
✓ Branch 1 (67→69) taken 6 times.
✗ Branch 2 (71→72) not taken.
✓ Branch 3 (71→73) taken 32 times.
 32 if (NULL == invoke_list_func(insert_element, list, di, src)) {
430 − return processed; // LCOV_EXCL_LINE
431 }
432 32 last = src;
433 32 di++;
434 }
435 37 processed++;
436 37 src += elem_size;
437 }
438 }
439 }
440
441 31 return processed;
442 }
443
444 41 size_t cx_list_default_insert_sorted(
445 struct cx_list_s *list,
446 const void *sorted_data,
447 size_t n
448 ) {
449 41 return cx_list_default_insert_sorted_impl(list, sorted_data, n, true);
450 }
451
452 42 size_t cx_list_default_insert_unique(
453 struct cx_list_s *list,
454 const void *sorted_data,
455 size_t n
456 ) {
457 42 return cx_list_default_insert_sorted_impl(list, sorted_data, n, false);
458 }
459
460 4 void cx_list_default_sort(struct cx_list_s *list) {
461 4 size_t elem_size = list->collection.elem_size;
462 4 size_t list_size = list->collection.size;
463 4 void *tmp = cxMallocDefault(elem_size * list_size);
464 − if (tmp == NULL) abort(); // LCOV_EXCL_LINE
465
466 // copy elements from source array
467 4 char *loc = tmp;
468
2/2
✓ Branch 0 (11→6) taken 1000 times.
✓ Branch 1 (11→12) taken 4 times.
 1004 for (size_t i = 0; i < list_size; i++) {
469
2/2
✓ Branch 0 (6→7) taken 500 times.
✓ Branch 1 (6→8) taken 500 times.
 1000 void *src = invoke_list_func(at, list, i);
470 1000 memcpy(loc, src, elem_size);
471 1000 loc += elem_size;
472 }
473
474 // qsort
475 4 qsort(tmp, list_size, elem_size,
476 4 list->collection.cmpfunc);
477
478 // copy elements back
479 4 loc = tmp;
480
2/2
✓ Branch 0 (19→14) taken 1000 times.
✓ Branch 1 (19→20) taken 4 times.
 1004 for (size_t i = 0; i < list_size; i++) {
481
2/2
✓ Branch 0 (14→15) taken 500 times.
✓ Branch 1 (14→16) taken 500 times.
 1000 void *dest = invoke_list_func(at, list, i);
482 1000 memcpy(dest, loc, elem_size);
483 1000 loc += elem_size;
484 }
485
486 4 cxFreeDefault(tmp);
487 4 }
488
489 44 int cx_list_default_swap(struct cx_list_s *list, size_t i, size_t j) {
490
2/2
✓ Branch 0 (2→3) taken 4 times.
✓ Branch 1 (2→4) taken 40 times.
 44 if (i == j) return 0;
491
2/2
✓ Branch 0 (4→5) taken 8 times.
✓ Branch 1 (4→6) taken 32 times.
 40 if (i >= list->collection.size) return 1;
492
2/2
✓ Branch 0 (6→7) taken 4 times.
✓ Branch 1 (6→8) taken 28 times.
 32 if (j >= list->collection.size) return 1;
493
494 28 size_t elem_size = list->collection.elem_size;
495
496 28 void *tmp = cxMallocDefault(elem_size);
497 − if (tmp == NULL) return 1; // LCOV_EXCL_LINE
498
499
2/2
✓ Branch 0 (11→12) taken 14 times.
✓ Branch 1 (11→13) taken 14 times.
 28 void *ip = invoke_list_func(at, list, i);
500
2/2
✓ Branch 0 (15→16) taken 14 times.
✓ Branch 1 (15→17) taken 14 times.
 28 void *jp = invoke_list_func(at, list, j);
501
502 28 memcpy(tmp, ip, elem_size);
503 28 memcpy(ip, jp, elem_size);
504 28 memcpy(jp, tmp, elem_size);
505
506 28 cxFreeDefault(tmp);
507
508 28 return 0;
509 }
510
511 471 void cx_list_init(
512 struct cx_list_s *list,
513 struct cx_list_class_s *cl,
514 const struct cx_allocator_s *allocator,
515 cx_compare_func comparator,
516 size_t elem_size
517 ) {
518 471 list->cl = cl;
519 471 list->collection.allocator = allocator;
520 471 list->collection.cmpfunc = comparator;
521
2/2
✓ Branch 0 (2→3) taken 278 times.
✓ Branch 1 (2→4) taken 193 times.
 471 if (elem_size > 0) {
522 278 list->collection.elem_size = elem_size;
523 } else {
524 193 list->collection.elem_size = sizeof(void *);
525
2/2
✓ Branch 0 (4→5) taken 6 times.
✓ Branch 1 (4→6) taken 187 times.
 193 if (list->collection.cmpfunc == NULL) {
526 6 list->collection.cmpfunc = cx_cmp_ptr;
527 }
528 193 list->collection.store_pointer = true;
529 193 list->climpl = list->cl;
530 193 list->cl = &cx_pointer_list_class;
531 }
532 471 }
533
534 249 int cxListCompare(
535 const CxList *list,
536 const CxList *other
537 ) {
538 249 bool cannot_optimize = false;
539
540 // if one is storing pointers but the other is not
541 249 cannot_optimize |= list->collection.store_pointer ^ other->collection.store_pointer;
542
543 // if one class is wrapped but the other is not
544 249 cannot_optimize |= (list->climpl == NULL) ^ (other->climpl == NULL);
545
546 // if the compare functions do not match or both are NULL
547
2/2
✓ Branch 0 (2→3) taken 125 times.
✓ Branch 1 (2→10) taken 124 times.
 249 if (!cannot_optimize) {
548
2/2
✓ Branch 0 (3→4) taken 42 times.
✓ Branch 1 (3→5) taken 83 times.
 125 cx_compare_func list_cmp = (cx_compare_func) (list->climpl != NULL ?
549 125 list->climpl->compare : list->cl->compare);
550
2/2
✓ Branch 0 (6→7) taken 42 times.
✓ Branch 1 (6→8) taken 83 times.
 125 cx_compare_func other_cmp = (cx_compare_func) (other->climpl != NULL ?
551 125 other->climpl->compare : other->cl->compare);
552 125 cannot_optimize |= list_cmp != other_cmp;
553 125 cannot_optimize |= list_cmp == NULL;
554 }
555
556
2/2
✓ Branch 0 (10→11) taken 210 times.
✓ Branch 1 (10→30) taken 39 times.
 249 if (cannot_optimize) {
557 // lists are definitely different - cannot use internal compare function
558
2/2
✓ Branch 0 (11→12) taken 152 times.
✓ Branch 1 (11→26) taken 58 times.
 210 if (list->collection.size == other->collection.size) {
559 152 CxIterator left = list->cl->iterator(list, 0, false);
560 152 CxIterator right = other->cl->iterator(other, 0, false);
561
2/2
✓ Branch 0 (23→15) taken 4948 times.
✓ Branch 1 (23→24) taken 98 times.
 5046 for (size_t i = 0; i < list->collection.size; i++) {
562 4948 void *leftValue = cxIteratorCurrent(left);
563 4948 void *rightValue = cxIteratorCurrent(right);
564 4948 int d = list->collection.cmpfunc(leftValue, rightValue);
565
2/2
✓ Branch 0 (18→19) taken 54 times.
✓ Branch 1 (18→20) taken 4894 times.
 4948 if (d != 0) {
566 54 return d;
567 }
568 4894 cxIteratorNext(left);
569 4894 cxIteratorNext(right);
570 }
571 98 return 0;
572 } else {
573
2/2
✓ Branch 0 (26→27) taken 29 times.
✓ Branch 1 (26→28) taken 29 times.
 58 return list->collection.size < other->collection.size ? -1 : 1;
574 }
575 } else {
576 // lists are compatible
577 39 return list->cl->compare(list, other);
578 }
579 }
580
581 653 size_t cxListSize(const CxList *list) {
582 653 return list->collection.size;
583 }
584
585 14888 int cxListAdd(CxList *list, const void *elem) {
586 14888 list->collection.sorted = false;
587 14888 return list->cl->insert_element(list, list->collection.size, elem) == NULL;
588 }
589
590 104 size_t cxListAddArray(CxList *list, const void *array, size_t n) {
591 104 list->collection.sorted = false;
592 104 return list->cl->insert_array(list, list->collection.size, array, n);
593 }
594
595 94 int cxListInsert(CxList *list, size_t index, const void *elem) {
596 94 list->collection.sorted = false;
597 94 return list->cl->insert_element(list, index, elem) == NULL;
598 }
599
600 12 void *cxListEmplaceAt(CxList *list, size_t index) {
601 12 list->collection.sorted = false;
602 12 return list->cl->insert_element(list, index, NULL);
603 }
604
605 416 void *cxListEmplace(CxList *list) {
606 416 list->collection.sorted = false;
607 416 return list->cl->insert_element(list, list->collection.size, NULL);
608 }
609
610 120 static bool cx_list_emplace_iterator_valid(const void *it) {
611 120 const CxIterator *iter = it;
612 120 return iter->index < iter->elem_count;
613 }
614
615 71 CxIterator cxListEmplaceArrayAt(CxList *list, size_t index, size_t n) {
616 71 list->collection.sorted = false;
617 71 size_t c = list->cl->insert_array(list, index, NULL, n);
618 71 CxIterator iter = list->cl->iterator(list, index, false);
619 // tweak the fields of this iterator
620 71 iter.elem_count = c;
621 71 iter.index = 0;
622 // replace the valid function to abort iteration when c is reached
623 71 iter.base.valid = cx_list_emplace_iterator_valid;
624 // if we are storing pointers, we want to return the pure pointers.
625 // therefore, we must unwrap the "current" method
626
2/2
✓ Branch 0 (4→5) taken 36 times.
✓ Branch 1 (4→6) taken 35 times.
 71 if (list->collection.store_pointer) {
627 36 iter.base.current = iter.base.current_impl;
628 }
629 71 return iter;
630 }
631
632 61 CxIterator cxListEmplaceArray(CxList *list, size_t n) {
633 61 return cxListEmplaceArrayAt(list, list->collection.size, n);
634 }
635
636 70 int cxListInsertSorted(CxList *list, const void *elem) {
637 assert(cxCollectionSorted(list));
638 70 list->collection.sorted = true;
639
2/2
✓ Branch 0 (2→3) taken 35 times.
✓ Branch 1 (2→4) taken 35 times.
 70 const void *data = list->collection.store_pointer ? &elem : elem;
640 70 return list->cl->insert_sorted(list, data, 1) == 0;
641 }
642
643 100 int cxListInsertUnique(CxList *list, const void *elem) {
644
4/4
✓ Branch 0 (2→3) taken 40 times.
✓ Branch 1 (2→4) taken 60 times.
✓ Branch 2 (3→4) taken 10 times.
✓ Branch 3 (3→9) taken 30 times.
 100 if (cxCollectionSorted(list)) {
645 70 list->collection.sorted = true;
646
2/2
✓ Branch 0 (4→5) taken 35 times.
✓ Branch 1 (4→6) taken 35 times.
 70 const void *data = list->collection.store_pointer ? &elem : elem;
647 70 return list->cl->insert_unique(list, data, 1) == 0;
648 } else {
649
2/2
✓ Branch 0 (10→11) taken 10 times.
✓ Branch 1 (10→12) taken 20 times.
 30 if (cxListContains(list, elem)) {
650 10 return 0;
651 } else {
652 20 return cxListAdd(list, elem);
653 }
654 }
655 }
656
657 20 size_t cxListInsertArray(CxList *list, size_t index, const void *array, size_t n) {
658 20 list->collection.sorted = false;
659 20 return list->cl->insert_array(list, index, array, n);
660 }
661
662 37 size_t cxListInsertSortedArray(CxList *list, const void *array, size_t n) {
663 assert(cxCollectionSorted(list));
664 37 list->collection.sorted = true;
665 37 return list->cl->insert_sorted(list, array, n);
666 }
667
668 66 size_t cxListInsertUniqueArray(CxList *list, const void *array, size_t n) {
669
4/4
✓ Branch 0 (2→3) taken 33 times.
✓ Branch 1 (2→4) taken 33 times.
✓ Branch 2 (3→4) taken 3 times.
✓ Branch 3 (3→6) taken 30 times.
 66 if (cxCollectionSorted(list)) {
670 36 list->collection.sorted = true;
671 36 return list->cl->insert_unique(list, array, n);
672 } else {
673 30 const char *source = array;
674
2/2
✓ Branch 0 (16→7) taken 150 times.
✓ Branch 1 (16→17) taken 30 times.
 180 for (size_t i = 0 ; i < n; i++) {
675 // note: this also checks elements added in a previous iteration
676 150 const void *data = list->collection.store_pointer ?
677
2/2
✓ Branch 0 (7→8) taken 75 times.
✓ Branch 1 (7→9) taken 75 times.
 150 *((const void**)source) : source;
678
2/2
✓ Branch 0 (11→12) taken 130 times.
✓ Branch 1 (11→15) taken 20 times.
 150 if (!cxListContains(list, data)) {
679
1/2
✗ Branch 0 (13→14) not taken.
✓ Branch 1 (13→15) taken 130 times.
 130 if (cxListAdd(list, data)) {
680 − return i; // LCOV_EXCL_LINE
681 }
682 }
683 150 source += list->collection.elem_size;
684 }
685 30 return n;
686 }
687 }
688
689 12 int cxListInsertAfter(CxIterator *iter, const void *elem) {
690 12 CxList* list = (CxList*)iter->src_handle;
691 12 list->collection.sorted = false;
692 12 return list->cl->insert_iter(iter, elem, 0);
693 }
694
695 18 int cxListInsertBefore(CxIterator *iter, const void *elem) {
696 18 CxList* list = (CxList*)iter->src_handle;
697 18 list->collection.sorted = false;
698 18 return list->cl->insert_iter(iter, elem, 1);
699 }
700
701 63 int cxListRemove(CxList *list, size_t index) {
702 63 return list->cl->remove(list, index, 1, NULL) == 0;
703 }
704
705 33 int cxListRemoveAndGet(CxList *list, size_t index, void *targetbuf) {
706 33 return list->cl->remove(list, index, 1, targetbuf) == 0;
707 }
708
709 18 int cxListRemoveAndGetFirst(CxList *list, void *targetbuf) {
710 18 return list->cl->remove(list, 0, 1, targetbuf) == 0;
711 }
712
713 18 int cxListRemoveAndGetLast(CxList *list, void *targetbuf) {
714 // note: index may wrap - member function will catch that
715 18 return list->cl->remove(list, list->collection.size - 1, 1, targetbuf) == 0;
716 }
717
718 31 size_t cxListRemoveArray(CxList *list, size_t index, size_t num) {
719 31 return list->cl->remove(list, index, num, NULL);
720 }
721
722 13 size_t cxListRemoveArrayAndGet(CxList *list, size_t index, size_t num, void *targetbuf) {
723 13 return list->cl->remove(list, index, num, targetbuf);
724 }
725
726 29 void cxListClear(CxList *list) {
727 29 list->cl->clear(list);
728 29 list->collection.sorted = true; // empty lists are always sorted
729 29 }
730
731 111 int cxListSwap(CxList *list, size_t i, size_t j) {
732 111 list->collection.sorted = false;
733 111 return list->cl->swap(list, i, j);
734 }
735
736 18177 void *cxListAt(const CxList *list, size_t index) {
737 18177 return list->cl->at(list, index);
738 }
739
740 6 void *cxListFirst(const CxList *list) {
741 6 return list->cl->at(list, 0);
742 }
743
744 9 void *cxListLast(const CxList *list) {
745 9 return list->cl->at(list, list->collection.size - 1);
746 }
747
748 18 int cxListSet(CxList *list, size_t index, const void *elem) {
749
2/2
✓ Branch 0 (2→3) taken 6 times.
✓ Branch 1 (2→4) taken 12 times.
 18 if (index >= list->collection.size) {
750 6 return 1;
751 }
752
753
2/2
✓ Branch 0 (4→5) taken 6 times.
✓ Branch 1 (4→7) taken 6 times.
 12 if (list->collection.store_pointer) {
754 // For pointer collections, always use climpl
755 6 void **target = list->climpl->at(list, index);
756 6 *target = (void *)elem;
757 } else {
758 6 void *target = list->cl->at(list, index);
759 6 memcpy(target, elem, list->collection.elem_size);
760 }
761
762 12 return 0;
763 }
764
765 37 CxIterator cxListIteratorAt(const CxList *list, size_t index) {
766
2/2
✓ Branch 0 (2→3) taken 1 times.
✓ Branch 1 (2→4) taken 36 times.
 37 if (list == NULL) list = cxEmptyList;
767 37 return list->cl->iterator(list, index, false);
768 }
769
770 19 CxIterator cxListBackwardsIteratorAt(const CxList *list, size_t index) {
771
2/2
✓ Branch 0 (2→3) taken 1 times.
✓ Branch 1 (2→4) taken 18 times.
 19 if (list == NULL) list = cxEmptyList;
772 19 return list->cl->iterator(list, index, true);
773 }
774
775 100 CxIterator cxListIterator(const CxList *list) {
776
2/2
✓ Branch 0 (2→3) taken 1 times.
✓ Branch 1 (2→4) taken 99 times.
 100 if (list == NULL) list = cxEmptyList;
777 100 return list->cl->iterator(list, 0, false);
778 }
779
780 18 CxIterator cxListBackwardsIterator(const CxList *list) {
781
2/2
✓ Branch 0 (2→3) taken 1 times.
✓ Branch 1 (2→4) taken 17 times.
 18 if (list == NULL) list = cxEmptyList;
782 18 return list->cl->iterator(list, list->collection.size - 1, true);
783 }
784
785 183 size_t cxListFind(const CxList *list, const void *elem) {
786 183 return list->cl->find_remove((CxList*)list, elem, false);
787 }
788
789 486 bool cxListContains(const CxList* list, const void* elem) {
790 486 return list->cl->find_remove((CxList*)list, elem, false) < list->collection.size;
791 }
792
793 774 bool cxListIndexValid(const CxList *list, size_t index) {
794 774 return index < list->collection.size;
795 }
796
797 32 size_t cxListFindRemove(CxList *list, const void *elem) {
798 32 return list->cl->find_remove(list, elem, true);
799 }
800
801 36 void cxListSort(CxList *list) {
802
2/2
✓ Branch 0 (2→3) taken 1 times.
✓ Branch 1 (2→4) taken 35 times.
 36 if (list->collection.sorted) return;
803 35 list->cl->sort(list);
804 35 list->collection.sorted = true;
805 }
806
807 6 void cxListReverse(CxList *list) {
808 // still sorted, but not according to the cmp_func
809 6 list->collection.sorted = false;
810 6 list->cl->reverse(list);
811 6 }
812
813 461 void cxListFree(CxList *list) {
814
2/2
✓ Branch 0 (2→3) taken 1 times.
✓ Branch 1 (2→4) taken 460 times.
 461 if (list == NULL) return;
815 460 list->cl->deallocate(list);
816 }
817
818 30 static void cx_list_pop_uninitialized_elements(CxList *list, size_t n) {
819 30 cx_destructor_func destr_bak = list->collection.simple_destructor;
820 30 cx_destructor_func2 destr2_bak = list->collection.advanced_destructor;
821 30 list->collection.simple_destructor = NULL;
822 30 list->collection.advanced_destructor = NULL;
823
2/2
✓ Branch 0 (2→3) taken 6 times.
✓ Branch 1 (2→4) taken 24 times.
 30 if (n == 1) {
824 6 cxListRemove(list, list->collection.size - 1);
825 } else {
826 24 cxListRemoveArray(list,list->collection.size - n, n);
827 }
828 30 list->collection.simple_destructor = destr_bak;
829 30 list->collection.advanced_destructor = destr2_bak;
830 30 }
831
832 19 static void* cx_list_simple_clone_func(void *dst, const void *src, const CxAllocator *al, void *data) {
833 19 size_t elem_size = *(size_t*)data;
834
1/2
✗ Branch 0 (2→3) not taken.
✓ Branch 1 (2→4) taken 19 times.
 19 if (dst == NULL) dst = cxMalloc(al, elem_size);
835
1/2
✓ Branch 0 (4→5) taken 19 times.
✗ Branch 1 (4→6) not taken.
 19 if (dst != NULL) memcpy(dst, src, elem_size);
836 19 return dst;
837 }
838
839 #define use_simple_clone_func(list) cx_list_simple_clone_func, NULL, (void*)&((list)->collection.elem_size)
840
841 51 int cxListClone(CxList *dst, const CxList *src, cx_clone_func clone_func,
842 const CxAllocator *clone_allocator, void *data) {
843
2/2
✓ Branch 0 (2→3) taken 1 times.
✓ Branch 1 (2→4) taken 50 times.
 51 if (clone_allocator == NULL) clone_allocator = cxDefaultAllocator;
844
845 // remember the original size
846 51 size_t orig_size = dst->collection.size;
847
848 // first, try to allocate the memory in the new list
849 51 CxIterator empl_iter = cxListEmplaceArray(dst, src->collection.size);
850
851 // get an iterator over the source elements
852 51 CxIterator src_iter = cxListIterator(src);
853
854 // now clone the elements
855 51 size_t cloned = empl_iter.elem_count;
856
2/2
✓ Branch 0 (20→7) taken 441 times.
✓ Branch 1 (20→21) taken 27 times.
 468 for (size_t i = 0 ; i < empl_iter.elem_count; i++) {
857 441 void *src_elem = cxIteratorCurrent(src_iter);
858 441 void **dest_memory = cxIteratorCurrent(empl_iter);
859
2/2
✓ Branch 0 (9→10) taken 268 times.
✓ Branch 1 (9→11) taken 173 times.
 441 void *target = cxCollectionStoresPointers(dst) ? NULL : dest_memory;
860 441 void *dest_ptr = clone_func(target, src_elem, clone_allocator, data);
861
2/2
✓ Branch 0 (13→14) taken 24 times.
✓ Branch 1 (13→15) taken 417 times.
 441 if (dest_ptr == NULL) {
862 24 cloned = i;
863 24 break;
864 }
865
2/2
✓ Branch 0 (15→16) taken 256 times.
✓ Branch 1 (15→17) taken 161 times.
 417 if (cxCollectionStoresPointers(dst)) {
866 256 *dest_memory = dest_ptr;
867 }
868 417 cxIteratorNext(src_iter);
869 417 cxIteratorNext(empl_iter);
870 }
871
872 // if we could not clone everything, free the allocated memory
873 // (disable the destructors!)
874
2/2
✓ Branch 0 (21→22) taken 24 times.
✓ Branch 1 (21→24) taken 27 times.
 51 if (cloned < src->collection.size) {
875 24 cx_list_pop_uninitialized_elements(dst,
876 24 dst->collection.size - cloned - orig_size);
877 24 return 1;
878 }
879
880 // set the sorted flag when we know it's sorted
881
3/4
✓ Branch 0 (24→25) taken 1 times.
✓ Branch 1 (24→27) taken 26 times.
✓ Branch 2 (25→26) taken 1 times.
✗ Branch 3 (25→27) not taken.
 27 if (orig_size == 0 && src->collection.sorted) {
882 1 dst->collection.sorted = true;
883 }
884
885 27 return 0;
886 }
887
888 5 int cxListDifference(CxList *dst,
889 const CxList *minuend, const CxList *subtrahend,
890 cx_clone_func clone_func, const CxAllocator *clone_allocator, void *data) {
891
2/2
✓ Branch 0 (2→3) taken 1 times.
✓ Branch 1 (2→4) taken 4 times.
 5 if (clone_allocator == NULL) clone_allocator = cxDefaultAllocator;
892
893 // optimize for sorted collections
894
4/8
✓ Branch 0 (4→5) taken 2 times.
✓ Branch 1 (4→6) taken 3 times.
✗ Branch 2 (5→6) not taken.
✓ Branch 3 (5→35) taken 2 times.
✗ Branch 4 (6→7) not taken.
✓ Branch 5 (6→8) taken 3 times.
✗ Branch 6 (7→8) not taken.
✗ Branch 7 (7→35) not taken.
 5 if (cxCollectionSorted(minuend) && cxCollectionSorted(subtrahend)) {
895 3 bool dst_was_empty = cxCollectionSize(dst) == 0;
896
897 3 CxIterator min_iter = cxListIterator(minuend);
898 3 CxIterator sub_iter = cxListIterator(subtrahend);
899
2/2
✓ Branch 0 (33→11) taken 188 times.
✓ Branch 1 (33→34) taken 2 times.
 190 while (cxIteratorValid(min_iter)) {
900 188 void *min_elem = cxIteratorCurrent(min_iter);
901 void *sub_elem;
902 int d;
903
2/2
✓ Branch 0 (13→14) taken 187 times.
✓ Branch 1 (13→16) taken 1 times.
 188 if (cxIteratorValid(sub_iter)) {
904 187 sub_elem = cxIteratorCurrent(sub_iter);
905 187 cx_compare_func cmp = subtrahend->collection.cmpfunc;
906 187 d = cmp(sub_elem, min_elem);
907 } else {
908 // no more elements in the subtrahend,
909 // i.e., the min_elem is larger than any elem of the subtrahend
910 1 d = 1;
911 }
912
2/2
✓ Branch 0 (17→18) taken 25 times.
✓ Branch 1 (17→19) taken 163 times.
 188 if (d == 0) {
913 // is contained, so skip it
914 25 cxIteratorNext(min_iter);
915
2/2
✓ Branch 0 (19→20) taken 94 times.
✓ Branch 1 (19→21) taken 69 times.
 163 } else if (d < 0) {
916 // subtrahend is smaller than minuend,
917 // check the next element
918 94 cxIteratorNext(sub_iter);
919 } else {
920 // subtrahend is larger than the dst element,
921 // clone the minuend and advance
922 69 void **dst_mem = cxListEmplace(dst);
923
2/2
✓ Branch 0 (22→23) taken 67 times.
✓ Branch 1 (22→24) taken 2 times.
 69 void *target = cxCollectionStoresPointers(dst) ? NULL : dst_mem;
924 69 void* dst_ptr = clone_func(target, min_elem, clone_allocator, data);
925
2/2
✓ Branch 0 (26→27) taken 1 times.
✓ Branch 1 (26→29) taken 68 times.
 69 if (dst_ptr == NULL) {
926 1 cx_list_pop_uninitialized_elements(dst, 1);
927 1 return 1;
928 }
929
2/2
✓ Branch 0 (29→30) taken 66 times.
✓ Branch 1 (29→31) taken 2 times.
 68 if (cxCollectionStoresPointers(dst)) {
930 66 *dst_mem = dst_ptr;
931 }
932 68 cxIteratorNext(min_iter);
933 }
934 }
935
936 // if dst was empty, it is now guaranteed to be sorted
937 2 dst->collection.sorted = dst_was_empty;
938 } else {
939 2 CxIterator min_iter = cxListIterator(minuend);
940
3/4
✓ Branch 0 (52→53) taken 93 times.
✓ Branch 1 (52→55) taken 1 times.
✓ Branch 2 (54→37) taken 93 times.
✗ Branch 3 (54→55) not taken.
 94 cx_foreach(void *, elem, min_iter) {
941
2/2
✓ Branch 0 (38→39) taken 26 times.
✓ Branch 1 (38→40) taken 67 times.
 93 if (cxListContains(subtrahend, elem)) {
942 26 continue;
943 }
944 67 void **dst_mem = cxListEmplace(dst);
945
1/2
✓ Branch 0 (41→42) taken 67 times.
✗ Branch 1 (41→43) not taken.
 67 void *target = cxCollectionStoresPointers(dst) ? NULL : dst_mem;
946 67 void* dst_ptr = clone_func(target, elem, clone_allocator, data);
947
2/2
✓ Branch 0 (45→46) taken 1 times.
✓ Branch 1 (45→48) taken 66 times.
 67 if (dst_ptr == NULL) {
948 1 cx_list_pop_uninitialized_elements(dst, 1);
949 1 return 1;
950 }
951
1/2
✓ Branch 0 (48→49) taken 66 times.
✗ Branch 1 (48→50) not taken.
 66 if (cxCollectionStoresPointers(dst)) {
952 66 *dst_mem = dst_ptr;
953 }
954 }
955 }
956
957 3 return 0;
958 }
959
960 5 int cxListIntersection(CxList *dst,
961 const CxList *src, const CxList *other,
962 cx_clone_func clone_func, const CxAllocator *clone_allocator, void *data) {
963
2/2
✓ Branch 0 (2→3) taken 1 times.
✓ Branch 1 (2→4) taken 4 times.
 5 if (clone_allocator == NULL) clone_allocator = cxDefaultAllocator;
964
965 // optimize for sorted collections
966
4/8
✓ Branch 0 (4→5) taken 2 times.
✓ Branch 1 (4→6) taken 3 times.
✗ Branch 2 (5→6) not taken.
✓ Branch 3 (5→34) taken 2 times.
✗ Branch 4 (6→7) not taken.
✓ Branch 5 (6→8) taken 3 times.
✗ Branch 6 (7→8) not taken.
✗ Branch 7 (7→34) not taken.
 5 if (cxCollectionSorted(src) && cxCollectionSorted(other)) {
967 3 bool dst_was_empty = cxCollectionSize(dst) == 0;
968
969 3 CxIterator src_iter = cxListIterator(src);
970 3 CxIterator other_iter = cxListIterator(other);
971
4/4
✓ Branch 0 (30→31) taken 200 times.
✓ Branch 1 (30→33) taken 1 times.
✓ Branch 2 (32→11) taken 199 times.
✓ Branch 3 (32→33) taken 1 times.
 201 while (cxIteratorValid(src_iter) && cxIteratorValid(other_iter)) {
972 199 void *src_elem = cxIteratorCurrent(src_iter);
973 199 void *other_elem = cxIteratorCurrent(other_iter);
974 199 int d = src->collection.cmpfunc(src_elem, other_elem);
975
2/2
✓ Branch 0 (14→15) taken 28 times.
✓ Branch 1 (14→26) taken 171 times.
 199 if (d == 0) {
976 // is contained, clone it
977 28 void **dst_mem = cxListEmplace(dst);
978
2/2
✓ Branch 0 (16→17) taken 25 times.
✓ Branch 1 (16→18) taken 3 times.
 28 void *target = cxCollectionStoresPointers(dst) ? NULL : dst_mem;
979 28 void* dst_ptr = clone_func(target, src_elem, clone_allocator, data);
980
2/2
✓ Branch 0 (20→21) taken 1 times.
✓ Branch 1 (20→23) taken 27 times.
 28 if (dst_ptr == NULL) {
981 1 cx_list_pop_uninitialized_elements(dst, 1);
982 1 return 1;
983 }
984
2/2
✓ Branch 0 (23→24) taken 24 times.
✓ Branch 1 (23→25) taken 3 times.
 27 if (cxCollectionStoresPointers(dst)) {
985 24 *dst_mem = dst_ptr;
986 }
987 27 cxIteratorNext(src_iter);
988
2/2
✓ Branch 0 (26→27) taken 74 times.
✓ Branch 1 (26→28) taken 97 times.
 171 } else if (d < 0) {
989 // the other element is larger, skip the source element
990 74 cxIteratorNext(src_iter);
991 } else {
992 // the source element is larger, try to find it in the other list
993 97 cxIteratorNext(other_iter);
994 }
995 }
996
997 // if dst was empty, it is now guaranteed to be sorted
998 2 dst->collection.sorted = dst_was_empty;
999 } else {
1000 2 CxIterator src_iter = cxListIterator(src);
1001
3/4
✓ Branch 0 (51→52) taken 89 times.
✓ Branch 1 (51→54) taken 1 times.
✓ Branch 2 (53→36) taken 89 times.
✗ Branch 3 (53→54) not taken.
 90 cx_foreach(void *, elem, src_iter) {
1002
2/2
✓ Branch 0 (37→38) taken 64 times.
✓ Branch 1 (37→39) taken 25 times.
 89 if (!cxListContains(other, elem)) {
1003 64 continue;
1004 }
1005 25 void **dst_mem = cxListEmplace(dst);
1006
1/2
✓ Branch 0 (40→41) taken 25 times.
✗ Branch 1 (40→42) not taken.
 25 void *target = cxCollectionStoresPointers(dst) ? NULL : dst_mem;
1007 25 void* dst_ptr = clone_func(target, elem, clone_allocator, data);
1008
2/2
✓ Branch 0 (44→45) taken 1 times.
✓ Branch 1 (44→47) taken 24 times.
 25 if (dst_ptr == NULL) {
1009 1 cx_list_pop_uninitialized_elements(dst, 1);
1010 1 return 1;
1011 }
1012
1/2
✓ Branch 0 (47→48) taken 24 times.
✗ Branch 1 (47→49) not taken.
 24 if (cxCollectionStoresPointers(dst)) {
1013 24 *dst_mem = dst_ptr;
1014 }
1015 }
1016 }
1017
1018 3 return 0;
1019 }
1020
1021 5 int cxListUnion(CxList *dst,
1022 const CxList *src, const CxList *other,
1023 cx_clone_func clone_func, const CxAllocator *clone_allocator, void *data) {
1024
2/2
✓ Branch 0 (2→3) taken 1 times.
✓ Branch 1 (2→4) taken 4 times.
 5 if (clone_allocator == NULL) clone_allocator = cxDefaultAllocator;
1025
1026 // optimize for sorted collections
1027
4/8
✓ Branch 0 (4→5) taken 2 times.
✓ Branch 1 (4→6) taken 3 times.
✗ Branch 2 (5→6) not taken.
✓ Branch 3 (5→43) taken 2 times.
✗ Branch 4 (6→7) not taken.
✓ Branch 5 (6→8) taken 3 times.
✗ Branch 6 (7→8) not taken.
✗ Branch 7 (7→43) not taken.
 5 if (cxCollectionSorted(src) && cxCollectionSorted(other)) {
1028 3 bool dst_was_empty = cxCollectionSize(dst) == 0;
1029
1030 3 CxIterator src_iter = cxListIterator(src);
1031 3 CxIterator other_iter = cxListIterator(other);
1032
4/4
✓ Branch 0 (39→11) taken 161 times.
✓ Branch 1 (39→40) taken 3 times.
✓ Branch 2 (41→11) taken 1 times.
✓ Branch 3 (41→42) taken 2 times.
 164 while (cxIteratorValid(src_iter) || cxIteratorValid(other_iter)) {
1033 162 void *src_elem = NULL, *other_elem = NULL;
1034 int d;
1035
2/2
✓ Branch 0 (12→13) taken 1 times.
✓ Branch 1 (12→15) taken 161 times.
 162 if (!cxIteratorValid(src_iter)) {
1036 1 other_elem = cxIteratorCurrent(other_iter);
1037 1 d = 1;
1038
2/2
✓ Branch 0 (16→17) taken 1 times.
✓ Branch 1 (16→19) taken 160 times.
 161 } else if (!cxIteratorValid(other_iter)) {
1039 1 src_elem = cxIteratorCurrent(src_iter);
1040 1 d = -1;
1041 } else {
1042 160 src_elem = cxIteratorCurrent(src_iter);
1043 160 other_elem = cxIteratorCurrent(other_iter);
1044 160 d = src->collection.cmpfunc(src_elem, other_elem);
1045 }
1046 void *clone_from;
1047
2/2
✓ Branch 0 (22→23) taken 67 times.
✓ Branch 1 (22→24) taken 95 times.
 162 if (d < 0) {
1048 // source element is smaller clone it
1049 67 clone_from = src_elem;
1050 67 cxIteratorNext(src_iter);
1051
2/2
✓ Branch 0 (24→25) taken 24 times.
✓ Branch 1 (24→27) taken 71 times.
 95 } else if (d == 0) {
1052 // both elements are equal, clone from the source, skip other
1053 24 clone_from = src_elem;
1054 24 cxIteratorNext(src_iter);
1055 24 cxIteratorNext(other_iter);
1056 } else {
1057 // the other element is smaller, clone it
1058 71 clone_from = other_elem;
1059 71 cxIteratorNext(other_iter);
1060 }
1061 162 void **dst_mem = cxListEmplace(dst);
1062
2/2
✓ Branch 0 (29→30) taken 153 times.
✓ Branch 1 (29→31) taken 9 times.
 162 void *target = cxCollectionStoresPointers(dst) ? NULL : dst_mem;
1063 162 void* dst_ptr = clone_func(target, clone_from, clone_allocator, data);
1064
2/2
✓ Branch 0 (33→34) taken 1 times.
✓ Branch 1 (33→36) taken 161 times.
 162 if (dst_ptr == NULL) {
1065 1 cx_list_pop_uninitialized_elements(dst, 1);
1066 1 return 1;
1067 }
1068
2/2
✓ Branch 0 (36→37) taken 152 times.
✓ Branch 1 (36→38) taken 9 times.
 161 if (cxCollectionStoresPointers(dst)) {
1069 152 *dst_mem = dst_ptr;
1070 }
1071 }
1072
1073 // if dst was empty, it is now guaranteed to be sorted
1074 2 dst->collection.sorted = dst_was_empty;
1075 } else {
1076
1/2
✗ Branch 0 (44→45) not taken.
✓ Branch 1 (44→46) taken 2 times.
 2 if (cxListClone(dst, src, clone_func, clone_allocator, data)) {
1077 1 return 1;
1078 }
1079 2 CxIterator other_iter = cxListIterator(other);
1080
3/4
✓ Branch 0 (63→64) taken 73 times.
✓ Branch 1 (63→66) taken 1 times.
✓ Branch 2 (65→48) taken 73 times.
✗ Branch 3 (65→66) not taken.
 74 cx_foreach(void *, elem, other_iter) {
1081
2/2
✓ Branch 0 (49→50) taken 20 times.
✓ Branch 1 (49→51) taken 53 times.
 73 if (cxListContains(src, elem)) {
1082 20 continue;
1083 }
1084 53 void **dst_mem = cxListEmplace(dst);
1085
1/2
✓ Branch 0 (52→53) taken 53 times.
✗ Branch 1 (52→54) not taken.
 53 void *target = cxCollectionStoresPointers(dst) ? NULL : dst_mem;
1086 53 void* dst_ptr = clone_func(target, elem, clone_allocator, data);
1087
2/2
✓ Branch 0 (56→57) taken 1 times.
✓ Branch 1 (56→59) taken 52 times.
 53 if (dst_ptr == NULL) {
1088 1 cx_list_pop_uninitialized_elements(dst, 1);
1089 1 return 1;
1090 }
1091
1/2
✓ Branch 0 (59→60) taken 52 times.
✗ Branch 1 (59→61) not taken.
 52 if (cxCollectionStoresPointers(dst)) {
1092 52 *dst_mem = dst_ptr;
1093 }
1094 }
1095 }
1096
1097 3 return 0;
1098 }
1099
1100 1 int cxListCloneSimple(CxList *dst, const CxList *src) {
1101 1 return cxListClone(dst, src, use_simple_clone_func(src));
1102 }
1103
1104 1 int cxListDifferenceSimple(CxList *dst, const CxList *minuend, const CxList *subtrahend) {
1105 1 return cxListDifference(dst, minuend, subtrahend, use_simple_clone_func(minuend));
1106 }
1107
1108 1 int cxListIntersectionSimple(CxList *dst, const CxList *src, const CxList *other) {
1109 1 return cxListIntersection(dst, src, other, use_simple_clone_func(src));
1110 }
1111
1112 1 int cxListUnionSimple(CxList *dst, const CxList *src, const CxList *other) {
1113 1 return cxListUnion(dst, src, other, use_simple_clone_func(src));
1114 }
1115
1116 12 int cxListReserve(CxList *list, size_t capacity) {
1117
2/2
✓ Branch 0 (2→3) taken 2 times.
✓ Branch 1 (2→4) taken 10 times.
 12 if (list->cl->change_capacity == NULL) {
1118 2 return 0;
1119 }
1120
2/2
✓ Branch 0 (4→5) taken 5 times.
✓ Branch 1 (4→6) taken 5 times.
 10 if (capacity <= cxCollectionSize(list)) {
1121 5 return 0;
1122 }
1123 5 return list->cl->change_capacity(list, capacity);
1124 }
1125
1126 6 int cxListShrink(CxList *list) {
1127
2/2
✓ Branch 0 (2→3) taken 1 times.
✓ Branch 1 (2→4) taken 5 times.
 6 if (list->cl->change_capacity == NULL) {
1128 1 return 0;
1129 }
1130 5 return list->cl->change_capacity(list, cxCollectionSize(list));
1131 }
1132