GCC Code Coverage Report

Directory: ./
File: linked_list.c
Date: 2025-04-06 13:22:55
Exec Total Coverage
Lines: 485 485 100.0%
Functions: 42 42 100.0%
Branches: 263 294 89.5%
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/linked_list.h"
30 #include "cx/compare.h"
31 #include <string.h>
32 #include <assert.h>
33
34 // LOW LEVEL LINKED LIST FUNCTIONS
35
36 #define CX_LL_PTR(cur, off) (*(void**)(((char*)(cur))+(off)))
37 #define ll_prev(node) CX_LL_PTR(node, loc_prev)
38 #define ll_next(node) CX_LL_PTR(node, loc_next)
39 #define ll_advance(node) CX_LL_PTR(node, loc_advance)
40 #define ll_data(node) (((char*)(node))+loc_data)
41
42 7452 void *cx_linked_list_at(
43 const void *start,
44 size_t start_index,
45 ptrdiff_t loc_advance,
46 size_t index
47 ) {
48 assert(start != NULL);
49 assert(loc_advance >= 0);
50 7452 size_t i = start_index;
51 7452 const void *cur = start;
52
3/4
✓ Branch 0 taken 197743 times.
✓ Branch 1 taken 7452 times.
✓ Branch 2 taken 197743 times.
✗ Branch 3 not taken.
 205195 while (i != index && cur != NULL) {
53 197743 cur = ll_advance(cur);
54
2/2
✓ Branch 0 taken 101039 times.
✓ Branch 1 taken 96704 times.
 197743 i < index ? i++ : i--;
55 }
56 7452 return (void *) cur;
57 }
58
59 74 void *cx_linked_list_find(
60 const void *start,
61 ptrdiff_t loc_advance,
62 ptrdiff_t loc_data,
63 cx_compare_func cmp_func,
64 const void *elem,
65 size_t *found_index
66 ) {
67 assert(start != NULL);
68 assert(loc_advance >= 0);
69 assert(loc_data >= 0);
70 assert(cmp_func);
71
72 74 void *node = (void*) start;
73 74 size_t index = 0;
74 do {
75 15404 void *current = ll_data(node);
76
2/2
✓ Branch 1 taken 62 times.
✓ Branch 2 taken 15342 times.
 15404 if (cmp_func(current, elem) == 0) {
77
1/2
✓ Branch 0 taken 62 times.
✗ Branch 1 not taken.
 62 if (found_index != NULL) {
78 62 *found_index = index;
79 }
80 62 return node;
81 }
82 15342 node = ll_advance(node);
83 15342 index++;
84
2/2
✓ Branch 0 taken 15330 times.
✓ Branch 1 taken 12 times.
 15342 } while (node != NULL);
85 12 return NULL;
86 }
87
88 5 void *cx_linked_list_first(
89 const void *node,
90 ptrdiff_t loc_prev
91 ) {
92 5 return cx_linked_list_last(node, loc_prev);
93 }
94
95 35 void *cx_linked_list_last(
96 const void *node,
97 ptrdiff_t loc_next
98 ) {
99 assert(node != NULL);
100 assert(loc_next >= 0);
101
102 35 const void *cur = node;
103 const void *last;
104 do {
105 1565 last = cur;
106
2/2
✓ Branch 0 taken 1530 times.
✓ Branch 1 taken 35 times.
 1565 } while ((cur = ll_next(cur)) != NULL);
107
108 35 return (void *) last;
109 }
110
111 5 void *cx_linked_list_prev(
112 const void *begin,
113 ptrdiff_t loc_next,
114 const void *node
115 ) {
116 assert(begin != NULL);
117 assert(node != NULL);
118 assert(loc_next >= 0);
119
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 4 times.
 5 if (begin == node) return NULL;
120 4 const void *cur = begin;
121 const void *next;
122 while (1) {
123 7 next = ll_next(cur);
124
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 3 times.
 7 if (next == node) return (void *) cur;
125 3 cur = next;
126 }
127 }
128
129 308365 void cx_linked_list_link(
130 void *left,
131 void *right,
132 ptrdiff_t loc_prev,
133 ptrdiff_t loc_next
134 ) {
135 assert(loc_next >= 0);
136 308365 ll_next(left) = right;
137
2/2
✓ Branch 0 taken 308362 times.
✓ Branch 1 taken 3 times.
 308365 if (loc_prev >= 0) {
138 308362 ll_prev(right) = left;
139 }
140 308365 }
141
142 2 void cx_linked_list_unlink(
143 void *left,
144 void *right,
145 ptrdiff_t loc_prev,
146 ptrdiff_t loc_next
147 ) {
148 assert (loc_next >= 0);
149 assert(ll_next(left) == right);
150 2 ll_next(left) = NULL;
151
1/2
✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
 2 if (loc_prev >= 0) {
152 assert(ll_prev(right) == left);
153 2 ll_prev(right) = NULL;
154 }
155 2 }
156
157 10 void cx_linked_list_add(
158 void **begin,
159 void **end,
160 ptrdiff_t loc_prev,
161 ptrdiff_t loc_next,
162 void *new_node
163 ) {
164 void *last;
165
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 7 times.
 10 if (end == NULL) {
166 assert(begin != NULL);
167
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 1 times.
 3 last = *begin == NULL ? NULL : cx_linked_list_last(*begin, loc_next);
168 } else {
169 7 last = *end;
170 }
171 10 cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, last, new_node, new_node);
172 10 }
173
174 11 void cx_linked_list_prepend(
175 void **begin,
176 void **end,
177 ptrdiff_t loc_prev,
178 ptrdiff_t loc_next,
179 void *new_node
180 ) {
181 11 cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, NULL, new_node, new_node);
182 11 }
183
184 3 void cx_linked_list_insert(
185 void **begin,
186 void **end,
187 ptrdiff_t loc_prev,
188 ptrdiff_t loc_next,
189 void *node,
190 void *new_node
191 ) {
192 3 cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, node, new_node, new_node);
193 3 }
194
195 5493 void cx_linked_list_insert_chain(
196 void **begin,
197 void **end,
198 ptrdiff_t loc_prev,
199 ptrdiff_t loc_next,
200 void *node,
201 void *insert_begin,
202 void *insert_end
203 ) {
204 // find the end of the chain, if not specified
205
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 5490 times.
 5493 if (insert_end == NULL) {
206 3 insert_end = cx_linked_list_last(insert_begin, loc_next);
207 }
208
209 // determine the successor
210 void *successor;
211
2/2
✓ Branch 0 taken 89 times.
✓ Branch 1 taken 5404 times.
 5493 if (node == NULL) {
212 assert(begin != NULL || (end != NULL && loc_prev >= 0));
213
2/2
✓ Branch 0 taken 85 times.
✓ Branch 1 taken 4 times.
 89 if (begin != NULL) {
214 85 successor = *begin;
215 85 *begin = insert_begin;
216 } else {
217
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 2 times.
 4 successor = *end == NULL ? NULL : cx_linked_list_first(*end, loc_prev);
218 }
219 } else {
220 5404 successor = ll_next(node);
221 5404 cx_linked_list_link(node, insert_begin, loc_prev, loc_next);
222 }
223
224
2/2
✓ Branch 0 taken 5402 times.
✓ Branch 1 taken 91 times.
 5493 if (successor == NULL) {
225 // the list ends with the new chain
226
2/2
✓ Branch 0 taken 5398 times.
✓ Branch 1 taken 4 times.
 5402 if (end != NULL) {
227 5398 *end = insert_end;
228 }
229 } else {
230 91 cx_linked_list_link(insert_end, successor, loc_prev, loc_next);
231 }
232 5493 }
233
234 2 void cx_linked_list_insert_sorted(
235 void **begin,
236 void **end,
237 ptrdiff_t loc_prev,
238 ptrdiff_t loc_next,
239 void *new_node,
240 cx_compare_func cmp_func
241 ) {
242 assert(ll_next(new_node) == NULL);
243 2 cx_linked_list_insert_sorted_chain(
244 begin, end, loc_prev, loc_next, new_node, cmp_func);
245 2 }
246
247 19 void cx_linked_list_insert_sorted_chain(
248 void **begin,
249 void **end,
250 ptrdiff_t loc_prev,
251 ptrdiff_t loc_next,
252 void *insert_begin,
253 cx_compare_func cmp_func
254 ) {
255 assert(begin != NULL);
256 assert(loc_next >= 0);
257 assert(insert_begin != NULL);
258
259 // track currently observed nodes
260 19 void *dest_prev = NULL;
261 19 void *dest = *begin;
262 19 void *src = insert_begin;
263
264 // special case: list is empty
265
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 17 times.
 19 if (dest == NULL) {
266 2 *begin = src;
267
1/2
✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
 2 if (end != NULL) {
268 2 *end = cx_linked_list_last(src, loc_next);
269 }
270 2 return;
271 }
272
273 // search the list for insertion points
274
4/4
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 13 times.
✓ Branch 2 taken 92 times.
✓ Branch 3 taken 4 times.
 109 while (dest != NULL && src != NULL) {
275 // compare current list node with source node
276 // if less or equal, skip
277
2/2
✓ Branch 1 taken 68 times.
✓ Branch 2 taken 24 times.
 92 if (cmp_func(dest, src) <= 0) {
278 68 dest_prev = dest;
279 68 dest = ll_next(dest);
280 68 continue;
281 }
282
283 // determine chain of elements that can be inserted
284 24 void *end_of_chain = src;
285 24 void *next_in_chain = ll_next(src);
286
2/2
✓ Branch 0 taken 22 times.
✓ Branch 1 taken 12 times.
 34 while (next_in_chain != NULL) {
287 // once we become larger than the list elem, break
288
2/2
✓ Branch 1 taken 12 times.
✓ Branch 2 taken 10 times.
 22 if (cmp_func(dest, next_in_chain) <= 0) {
289 12 break;
290 }
291 // otherwise, we can insert one more
292 10 end_of_chain = next_in_chain;
293 10 next_in_chain = ll_next(next_in_chain);
294 }
295
296 // insert the elements
297
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 21 times.
 24 if (dest_prev == NULL) {
298 // new begin
299 3 *begin = src;
300 } else {
301 21 cx_linked_list_link(dest_prev, src, loc_prev, loc_next);
302 }
303 24 cx_linked_list_link(end_of_chain, dest, loc_prev, loc_next);
304
305 // continue with next
306 24 src = next_in_chain;
307 24 dest_prev = dest;
308 24 dest = ll_next(dest);
309 }
310
311 // insert remaining items
312
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 12 times.
 17 if (src != NULL) {
313 5 cx_linked_list_link(dest_prev, src, loc_prev, loc_next);
314 }
315
316 // determine new end of list, if requested
317
1/2
✓ Branch 0 taken 17 times.
✗ Branch 1 not taken.
 17 if (end != NULL) {
318
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 13 times.
 17 *end = cx_linked_list_last(
319 dest != NULL ? dest : dest_prev, loc_next);
320 }
321 }
322
323 87 size_t cx_linked_list_remove_chain(
324 void **begin,
325 void **end,
326 ptrdiff_t loc_prev,
327 ptrdiff_t loc_next,
328 void *node,
329 size_t num
330 ) {
331 assert(node != NULL);
332 assert(loc_next >= 0);
333 assert(loc_prev >= 0 || begin != NULL);
334
335 // easy exit
336
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 87 times.
 87 if (num == 0) return 0;
337
338 // find adjacent nodes
339 void *prev;
340
2/2
✓ Branch 0 taken 85 times.
✓ Branch 1 taken 2 times.
 87 if (loc_prev >= 0) {
341 85 prev = ll_prev(node);
342 } else {
343 2 prev = cx_linked_list_prev(*begin, loc_next, node);
344 }
345
346 87 void *next = ll_next(node);
347 87 size_t removed = 1;
348
4/4
✓ Branch 0 taken 38 times.
✓ Branch 1 taken 84 times.
✓ Branch 2 taken 35 times.
✓ Branch 3 taken 3 times.
 122 for (; removed < num && next != NULL ; removed++) {
349 35 next = ll_next(next);
350 }
351
352 // update next pointer of prev node, or set begin
353
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 84 times.
 87 if (prev == NULL) {
354
1/2
✓ Branch 0 taken 3 times.
✗ Branch 1 not taken.
 3 if (begin != NULL) {
355 3 *begin = next;
356 }
357 } else {
358 84 ll_next(prev) = next;
359 }
360
361 // update prev pointer of next node, or set end
362
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 80 times.
 87 if (next == NULL) {
363
1/2
✓ Branch 0 taken 7 times.
✗ Branch 1 not taken.
 7 if (end != NULL) {
364 7 *end = prev;
365 }
366
2/2
✓ Branch 0 taken 79 times.
✓ Branch 1 taken 1 times.
 80 } else if (loc_prev >= 0) {
367 79 ll_prev(next) = prev;
368 }
369
370 87 return removed;
371 }
372
373 565 size_t cx_linked_list_size(
374 const void *node,
375 ptrdiff_t loc_next
376 ) {
377 assert(loc_next >= 0);
378 565 size_t size = 0;
379
2/2
✓ Branch 0 taken 297903 times.
✓ Branch 1 taken 565 times.
 298468 while (node != NULL) {
380 297903 node = ll_next(node);
381 297903 size++;
382 }
383 565 return size;
384 }
385
386 #ifndef CX_LINKED_LIST_SORT_SBO_SIZE
387 #define CX_LINKED_LIST_SORT_SBO_SIZE 1024
388 #endif
389
390 1122 static void cx_linked_list_sort_merge(
391 ptrdiff_t loc_prev,
392 ptrdiff_t loc_next,
393 ptrdiff_t loc_data,
394 size_t length,
395 void *ls,
396 void *le,
397 void *re,
398 cx_compare_func cmp_func,
399 void **begin,
400 void **end
401 ) {
402 void *sbo[CX_LINKED_LIST_SORT_SBO_SIZE];
403 1122 void **sorted = length >= CX_LINKED_LIST_SORT_SBO_SIZE ?
404
2/2
✓ Branch 0 taken 117 times.
✓ Branch 1 taken 1005 times.
 1122 malloc(sizeof(void *) * length) : sbo;
405
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1122 times.
 1122 if (sorted == NULL) abort();
406 void *rc, *lc;
407
408 1122 lc = ls;
409 1122 rc = le;
410 1122 size_t n = 0;
411
6/6
✓ Branch 0 taken 243784 times.
✓ Branch 1 taken 542 times.
✓ Branch 2 taken 243554 times.
✓ Branch 3 taken 230 times.
✓ Branch 4 taken 243204 times.
✓ Branch 5 taken 350 times.
 244326 while (lc && lc != le && rc != re) {
412
2/2
✓ Branch 1 taken 2933 times.
✓ Branch 2 taken 240271 times.
 243204 if (cmp_func(ll_data(lc), ll_data(rc)) <= 0) {
413 2933 sorted[n] = lc;
414 2933 lc = ll_next(lc);
415 } else {
416 240271 sorted[n] = rc;
417 240271 rc = ll_next(rc);
418 }
419 243204 n++;
420 }
421
4/4
✓ Branch 0 taken 1030 times.
✓ Branch 1 taken 560 times.
✓ Branch 2 taken 468 times.
✓ Branch 3 taken 562 times.
 1590 while (lc && lc != le) {
422 468 sorted[n] = lc;
423 468 lc = ll_next(lc);
424 468 n++;
425 }
426
4/4
✓ Branch 0 taken 59259 times.
✓ Branch 1 taken 562 times.
✓ Branch 2 taken 58699 times.
✓ Branch 3 taken 560 times.
 59821 while (rc && rc != re) {
427 58699 sorted[n] = rc;
428 58699 rc = ll_next(rc);
429 58699 n++;
430 }
431
432 // Update pointer
433
1/2
✓ Branch 0 taken 1122 times.
✗ Branch 1 not taken.
 1122 if (loc_prev >= 0) ll_prev(sorted[0]) = NULL;
434
2/2
✓ Branch 0 taken 301249 times.
✓ Branch 1 taken 1122 times.
 302371 for (size_t i = 0 ; i < length - 1; i++) {
435 301249 cx_linked_list_link(sorted[i], sorted[i + 1], loc_prev, loc_next);
436 }
437 1122 ll_next(sorted[length - 1]) = NULL;
438
439 1122 *begin = sorted[0];
440 1122 *end = sorted[length - 1];
441
2/2
✓ Branch 0 taken 117 times.
✓ Branch 1 taken 1005 times.
 1122 if (sorted != sbo) {
442 117 free(sorted);
443 }
444 1122 }
445
446 566 void cx_linked_list_sort( // NOLINT(misc-no-recursion) - purposely recursive function
447 void **begin,
448 void **end,
449 ptrdiff_t loc_prev,
450 ptrdiff_t loc_next,
451 ptrdiff_t loc_data,
452 cx_compare_func cmp_func
453 ) {
454 assert(begin != NULL);
455 assert(loc_next >= 0);
456 assert(loc_data >= 0);
457 assert(cmp_func);
458
459 void *lc, *ls, *le, *re;
460
461 // set start node
462 566 ls = *begin;
463
464 // early exit when this list is empty
465
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 565 times.
 566 if (ls == NULL) return;
466
467 // check how many elements are already sorted
468 565 lc = ls;
469 565 size_t ln = 1;
470
4/4
✓ Branch 0 taken 1412 times.
✓ Branch 1 taken 3 times.
✓ Branch 3 taken 850 times.
✓ Branch 4 taken 562 times.
 1415 while (ll_next(lc) != NULL && cmp_func(ll_data(ll_next(lc)), ll_data(lc)) > 0) {
471 850 lc = ll_next(lc);
472 850 ln++;
473 }
474 565 le = ll_next(lc);
475
476 // if first unsorted node is NULL, the list is already completely sorted
477
2/2
✓ Branch 0 taken 562 times.
✓ Branch 1 taken 3 times.
 565 if (le != NULL) {
478 void *rc;
479 562 size_t rn = 1;
480 562 rc = le;
481 // skip already sorted elements
482
4/4
✓ Branch 0 taken 1083 times.
✓ Branch 1 taken 2 times.
✓ Branch 3 taken 523 times.
✓ Branch 4 taken 560 times.
 1085 while (ll_next(rc) != NULL && cmp_func(ll_data(ll_next(rc)), ll_data(rc)) > 0) {
483 523 rc = ll_next(rc);
484 523 rn++;
485 }
486 562 re = ll_next(rc);
487
488 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
489 void *sorted_begin, *sorted_end;
490 562 cx_linked_list_sort_merge(loc_prev, loc_next, loc_data,
491 ln + rn, ls, le, re, cmp_func,
492 &sorted_begin, &sorted_end);
493
494 // Something left? Sort it!
495 562 size_t remainder_length = cx_linked_list_size(re, loc_next);
496
2/2
✓ Branch 0 taken 560 times.
✓ Branch 1 taken 2 times.
 562 if (remainder_length > 0) {
497 560 void *remainder = re;
498 560 cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, cmp_func);
499
500 // merge sorted list with (also sorted) remainder
501 560 cx_linked_list_sort_merge(loc_prev, loc_next, loc_data,
502 560 ln + rn + remainder_length,
503 sorted_begin, remainder, NULL, cmp_func,
504 &sorted_begin, &sorted_end);
505 }
506 562 *begin = sorted_begin;
507
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 558 times.
 562 if (end) *end = sorted_end;
508 }
509 }
510
511 20 int cx_linked_list_compare(
512 const void *begin_left,
513 const void *begin_right,
514 ptrdiff_t loc_advance,
515 ptrdiff_t loc_data,
516 cx_compare_func cmp_func
517 ) {
518 20 const void *left = begin_left, *right = begin_right;
519
520
4/4
✓ Branch 0 taken 565 times.
✓ Branch 1 taken 11 times.
✓ Branch 2 taken 562 times.
✓ Branch 3 taken 3 times.
 576 while (left != NULL && right != NULL) {
521 562 const void *left_data = ll_data(left);
522 562 const void *right_data = ll_data(right);
523 562 int result = cmp_func(left_data, right_data);
524
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 556 times.
 562 if (result != 0) return result;
525 556 left = ll_advance(left);
526 556 right = ll_advance(right);
527 }
528
529
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 11 times.
 14 if (left != NULL) { return 1; }
530
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 8 times.
 11 else if (right != NULL) { return -1; }
531 8 else { return 0; }
532 }
533
534 3 void cx_linked_list_reverse(
535 void **begin,
536 void **end,
537 ptrdiff_t loc_prev,
538 ptrdiff_t loc_next
539 ) {
540 assert(begin != NULL);
541 assert(loc_next >= 0);
542
543 // swap all links
544 3 void *prev = NULL;
545 3 void *cur = *begin;
546
2/2
✓ Branch 0 taken 104 times.
✓ Branch 1 taken 3 times.
 107 while (cur != NULL) {
547 104 void *next = ll_next(cur);
548
549 104 ll_next(cur) = prev;
550
1/2
✓ Branch 0 taken 104 times.
✗ Branch 1 not taken.
 104 if (loc_prev >= 0) {
551 104 ll_prev(cur) = next;
552 }
553
554 104 prev = cur;
555 104 cur = next;
556 }
557
558 // update begin and end
559
1/2
✓ Branch 0 taken 3 times.
✗ Branch 1 not taken.
 3 if (end != NULL) {
560 3 *end = *begin;
561 }
562 3 *begin = prev;
563 3 }
564
565 // HIGH LEVEL LINKED LIST IMPLEMENTATION
566
567 typedef struct cx_linked_list_node cx_linked_list_node;
568 struct cx_linked_list_node {
569 cx_linked_list_node *prev;
570 cx_linked_list_node *next;
571 char payload[];
572 };
573
574 #define CX_LL_LOC_PREV offsetof(cx_linked_list_node, prev)
575 #define CX_LL_LOC_NEXT offsetof(cx_linked_list_node, next)
576 #define CX_LL_LOC_DATA offsetof(cx_linked_list_node, payload)
577
578 typedef struct {
579 struct cx_list_s base;
580 cx_linked_list_node *begin;
581 cx_linked_list_node *end;
582 } cx_linked_list;
583
584 7449 static cx_linked_list_node *cx_ll_node_at(
585 const cx_linked_list *list,
586 size_t index
587 ) {
588
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 7437 times.
 7449 if (index >= list->base.collection.size) {
589 12 return NULL;
590
2/2
✓ Branch 0 taken 5227 times.
✓ Branch 1 taken 2210 times.
 7437 } else if (index > list->base.collection.size / 2) {
591 5227 return cx_linked_list_at(list->end, list->base.collection.size - 1, CX_LL_LOC_PREV, index);
592 } else {
593 2210 return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index);
594 }
595 }
596
597 5502 static cx_linked_list_node *cx_ll_malloc_node(const struct cx_list_s *list) {
598 11004 return cxMalloc(list->collection.allocator,
599 5502 sizeof(cx_linked_list_node) + list->collection.elem_size);
600 }
601
602 5466 static int cx_ll_insert_at(
603 struct cx_list_s *list,
604 cx_linked_list_node *node,
605 const void *elem
606 ) {
607
608 // create the new new_node
609 5466 cx_linked_list_node *new_node = cx_ll_malloc_node(list);
610
611 // sortir if failed
612
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 5466 times.
 5466 if (new_node == NULL) return 1;
613
614 // initialize new new_node
615 5466 new_node->prev = new_node->next = NULL;
616 5466 memcpy(new_node->payload, elem, list->collection.elem_size);
617
618 // insert
619 5466 cx_linked_list *ll = (cx_linked_list *) list;
620 5466 cx_linked_list_insert_chain(
621 5466 (void **) &ll->begin, (void **) &ll->end,
622 CX_LL_LOC_PREV, CX_LL_LOC_NEXT,
623 node, new_node, new_node
624 );
625
626 // increase the size and return
627 5466 list->collection.size++;
628 5466 return 0;
629 }
630
631 3557 static size_t cx_ll_insert_array(
632 struct cx_list_s *list,
633 size_t index,
634 const void *array,
635 size_t n
636 ) {
637 // out-of bounds and corner case check
638
3/4
✓ Branch 0 taken 3555 times.
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 3555 times.
 3557 if (index > list->collection.size || n == 0) return 0;
639
640 // find position efficiently
641
2/2
✓ Branch 0 taken 3485 times.
✓ Branch 1 taken 70 times.
 3555 cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1);
642
643 // perform first insert
644
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 3555 times.
 3555 if (0 != cx_ll_insert_at(list, node, array)) return 1;
645
646 // is there more?
647
2/2
✓ Branch 0 taken 3534 times.
✓ Branch 1 taken 21 times.
 3555 if (n == 1) return 1;
648
649 // we now know exactly where we are
650
2/2
✓ Branch 0 taken 19 times.
✓ Branch 1 taken 2 times.
 21 node = node == NULL ? ((cx_linked_list *) list)->begin : node->next;
651
652 // we can add the remaining nodes and immediately advance to the inserted node
653 21 const char *source = array;
654
2/2
✓ Branch 0 taken 1905 times.
✓ Branch 1 taken 21 times.
 1926 for (size_t i = 1; i < n; i++) {
655 1905 source += list->collection.elem_size;
656
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 1905 times.
 1905 if (0 != cx_ll_insert_at(list, node, source)) return i;
657 1905 node = node->next;
658 }
659 21 return n;
660 }
661
662 3536 static int cx_ll_insert_element(
663 struct cx_list_s *list,
664 size_t index,
665 const void *element
666 ) {
667 3536 return 1 != cx_ll_insert_array(list, index, element, 1);
668 }
669
670 static _Thread_local cx_compare_func cx_ll_insert_sorted_cmp_func;
671
672 102 static int cx_ll_insert_sorted_cmp_helper(const void *l, const void *r) {
673 102 const cx_linked_list_node *left = l;
674 102 const cx_linked_list_node *right = r;
675 102 return cx_ll_insert_sorted_cmp_func(left->payload, right->payload);
676 }
677
678 16 static size_t cx_ll_insert_sorted(
679 struct cx_list_s *list,
680 const void *array,
681 size_t n
682 ) {
683 // special case
684
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 16 times.
 16 if (n == 0) return 0;
685
686 // create a new chain of nodes
687 16 cx_linked_list_node *chain = cx_ll_malloc_node(list);
688
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 16 times.
 16 if (chain == NULL) return 0;
689
690 16 memcpy(chain->payload, array, list->collection.elem_size);
691 16 chain->prev = NULL;
692 16 chain->next = NULL;
693
694 // add all elements from the array to that chain
695 16 cx_linked_list_node *prev = chain;
696 16 const char *src = array;
697 16 size_t inserted = 1;
698
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 16 times.
 36 for (; inserted < n; inserted++) {
699 20 cx_linked_list_node *next = cx_ll_malloc_node(list);
700
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 20 times.
 20 if (next == NULL) break;
701 20 src += list->collection.elem_size;
702 20 memcpy(next->payload, src, list->collection.elem_size);
703 20 prev->next = next;
704 20 next->prev = prev;
705 20 prev = next;
706 }
707 16 prev->next = NULL;
708
709 // invoke the low level function
710 16 cx_linked_list *ll = (cx_linked_list *) list;
711 16 cx_ll_insert_sorted_cmp_func = list->collection.cmpfunc;
712 16 cx_linked_list_insert_sorted_chain(
713 16 (void **) &ll->begin,
714 16 (void **) &ll->end,
715 CX_LL_LOC_PREV,
716 CX_LL_LOC_NEXT,
717 chain,
718 cx_ll_insert_sorted_cmp_helper
719 );
720
721 // adjust the list metadata
722 16 list->collection.size += inserted;
723
724 16 return inserted;
725 }
726
727 22 static size_t cx_ll_remove(
728 struct cx_list_s *list,
729 size_t index,
730 size_t num,
731 void *targetbuf
732 ) {
733 22 cx_linked_list *ll = (cx_linked_list *) list;
734 22 cx_linked_list_node *node = cx_ll_node_at(ll, index);
735
736 // out-of-bounds check
737
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 20 times.
 22 if (node == NULL) return 0;
738
739 // remove
740 20 size_t removed = cx_linked_list_remove_chain(
741 20 (void **) &ll->begin,
742 20 (void **) &ll->end,
743 CX_LL_LOC_PREV,
744 CX_LL_LOC_NEXT,
745 node,
746 num
747 );
748
749 // adjust size
750 20 list->collection.size -= removed;
751
752 // copy or destroy the removed chain
753
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 4 times.
 20 if (targetbuf == NULL) {
754 16 cx_linked_list_node *n = node;
755
2/2
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 16 times.
 46 for (size_t i = 0; i < removed; i++) {
756 // element destruction
757
8/8
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 10 times.
✓ Branch 2 taken 10 times.
✓ Branch 3 taken 10 times.
✓ Branch 5 taken 4 times.
✓ Branch 6 taken 26 times.
✓ Branch 7 taken 2 times.
✓ Branch 8 taken 2 times.
 30 cx_invoke_destructor(list, n->payload);
758
759 // free the node and advance
760 30 void *next = n->next;
761 30 cxFree(list->collection.allocator, n);
762 30 n = next;
763 }
764 } else {
765 4 char *dest = targetbuf;
766 4 cx_linked_list_node *n = node;
767
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 4 times.
 28 for (size_t i = 0; i < removed; i++) {
768 // copy payload
769 24 memcpy(dest, n->payload, list->collection.elem_size);
770
771 // advance target buffer
772 24 dest += list->collection.elem_size;
773
774 // free the node and advance
775 24 void *next = n->next;
776 24 cxFree(list->collection.allocator, n);
777 24 n = next;
778 }
779 }
780
781 20 return removed;
782 }
783
784 6 static void cx_ll_clear(struct cx_list_s *list) {
785
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 6 if (list->collection.size == 0) return;
786
787 6 cx_linked_list *ll = (cx_linked_list *) list;
788 6 cx_linked_list_node *node = ll->begin;
789
2/2
✓ Branch 0 taken 270 times.
✓ Branch 1 taken 6 times.
 276 while (node != NULL) {
790
8/8
✓ Branch 0 taken 112 times.
✓ Branch 1 taken 158 times.
✓ Branch 2 taken 56 times.
✓ Branch 3 taken 56 times.
✓ Branch 5 taken 142 times.
✓ Branch 6 taken 128 times.
✓ Branch 7 taken 71 times.
✓ Branch 8 taken 71 times.
 270 cx_invoke_destructor(list, node->payload);
791 270 cx_linked_list_node *next = node->next;
792 270 cxFree(list->collection.allocator, node);
793 270 node = next;
794 }
795 6 ll->begin = ll->end = NULL;
796 6 list->collection.size = 0;
797 }
798
799 22 static int cx_ll_swap(
800 struct cx_list_s *list,
801 size_t i,
802 size_t j
803 ) {
804
4/4
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 4 times.
✓ Branch 2 taken 2 times.
✓ Branch 3 taken 16 times.
 22 if (i >= list->collection.size || j >= list->collection.size) return 1;
805
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 14 times.
 16 if (i == j) return 0;
806
807 // perform an optimized search that finds both elements in one run
808 14 cx_linked_list *ll = (cx_linked_list *) list;
809 14 size_t mid = list->collection.size / 2;
810 size_t left, right;
811
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 4 times.
 14 if (i < j) {
812 10 left = i;
813 10 right = j;
814 } else {
815 4 left = j;
816 4 right = i;
817 }
818 14 cx_linked_list_node *nleft = NULL, *nright = NULL;
819
4/4
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 4 times.
✓ Branch 2 taken 2 times.
✓ Branch 3 taken 8 times.
 14 if (left < mid && right < mid) {
820 // case 1: both items left from mid
821 2 nleft = cx_ll_node_at(ll, left);
822 assert(nleft != NULL);
823 2 nright = nleft;
824
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 2 times.
 8 for (size_t c = left; c < right; c++) {
825 6 nright = nright->next;
826 }
827
3/4
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 8 times.
✓ Branch 2 taken 4 times.
✗ Branch 3 not taken.
 12 } else if (left >= mid && right >= mid) {
828 // case 2: both items right from mid
829 4 nright = cx_ll_node_at(ll, right);
830 assert(nright != NULL);
831 4 nleft = nright;
832
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 4 times.
 10 for (size_t c = right; c > left; c--) {
833 6 nleft = nleft->prev;
834 }
835 } else {
836 // case 3: one item left, one item right
837
838 // chose the closest to begin / end
839 size_t closest;
840 size_t other;
841 8 size_t diff2boundary = list->collection.size - right - 1;
842
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
 8 if (left <= diff2boundary) {
843 4 closest = left;
844 4 other = right;
845 4 nleft = cx_ll_node_at(ll, left);
846 } else {
847 4 closest = right;
848 4 other = left;
849 4 diff2boundary = left;
850 4 nright = cx_ll_node_at(ll, right);
851 }
852
853 // is other element closer to us or closer to boundary?
854
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
 8 if (right - left <= diff2boundary) {
855 // search other element starting from already found element
856
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 2 times.
 4 if (closest == left) {
857 2 nright = nleft;
858
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 2 times.
 8 for (size_t c = left; c < right; c++) {
859 6 nright = nright->next;
860 }
861 } else {
862 2 nleft = nright;
863
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 2 times.
 12 for (size_t c = right; c > left; c--) {
864 10 nleft = nleft->prev;
865 }
866 }
867 } else {
868 // search other element starting at the boundary
869
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 2 times.
 4 if (closest == left) {
870 2 nright = cx_ll_node_at(ll, other);
871 } else {
872 2 nleft = cx_ll_node_at(ll, other);
873 }
874 }
875 }
876
877 14 cx_linked_list_node *prev = nleft->prev;
878 14 cx_linked_list_node *next = nright->next;
879 14 cx_linked_list_node *midstart = nleft->next;
880 14 cx_linked_list_node *midend = nright->prev;
881
882
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 12 times.
 14 if (prev == NULL) {
883 2 ll->begin = nright;
884 } else {
885 12 prev->next = nright;
886 }
887 14 nright->prev = prev;
888
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 12 times.
 14 if (midstart == nright) {
889 // special case: both nodes are adjacent
890 2 nright->next = nleft;
891 2 nleft->prev = nright;
892 } else {
893 // likely case: a chain is between the two nodes
894 12 nright->next = midstart;
895 12 midstart->prev = nright;
896 12 midend->next = nleft;
897 12 nleft->prev = midend;
898 }
899 14 nleft->next = next;
900
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 12 times.
 14 if (next == NULL) {
901 2 ll->end = nleft;
902 } else {
903 12 next->prev = nleft;
904 }
905
906 14 return 0;
907 }
908
909 3810 static void *cx_ll_at(
910 const struct cx_list_s *list,
911 size_t index
912 ) {
913 3810 cx_linked_list *ll = (cx_linked_list *) list;
914 3810 cx_linked_list_node *node = cx_ll_node_at(ll, index);
915
2/2
✓ Branch 0 taken 3806 times.
✓ Branch 1 taken 4 times.
 3810 return node == NULL ? NULL : node->payload;
916 }
917
918 70 static size_t cx_ll_find_remove(
919 struct cx_list_s *list,
920 const void *elem,
921 bool remove
922 ) {
923
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 68 times.
 70 if (list->collection.size == 0) return 0;
924
925 size_t index;
926 68 cx_linked_list *ll = ((cx_linked_list *) list);
927 68 cx_linked_list_node *node = cx_linked_list_find(
928 68 ll->begin,
929 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
930 list->collection.cmpfunc, elem,
931 &index
932 );
933
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 58 times.
 68 if (node == NULL) {
934 10 return list->collection.size;
935 }
936
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 54 times.
 58 if (remove) {
937
2/8
✗ Branch 0 not taken.
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 5 not taken.
✓ Branch 6 taken 4 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 4 cx_invoke_destructor(list, node->payload);
938 4 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
939 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
940 4 list->collection.size--;
941 4 cxFree(list->collection.allocator, node);
942 }
943 58 return index;
944 }
945
946 4 static void cx_ll_sort(struct cx_list_s *list) {
947 4 cx_linked_list *ll = (cx_linked_list *) list;
948 4 cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end,
949 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
950 list->collection.cmpfunc);
951 4 }
952
953 2 static void cx_ll_reverse(struct cx_list_s *list) {
954 2 cx_linked_list *ll = (cx_linked_list *) list;
955 2 cx_linked_list_reverse((void **) &ll->begin, (void **) &ll->end, CX_LL_LOC_PREV, CX_LL_LOC_NEXT);
956 2 }
957
958 14 static int cx_ll_compare(
959 const struct cx_list_s *list,
960 const struct cx_list_s *other
961 ) {
962 14 cx_linked_list *left = (cx_linked_list *) list;
963 14 cx_linked_list *right = (cx_linked_list *) other;
964 28 return cx_linked_list_compare(left->begin, right->begin,
965 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
966 14 list->collection.cmpfunc);
967 }
968
969 456 static bool cx_ll_iter_valid(const void *it) {
970 456 const struct cx_iterator_s *iter = it;
971 456 return iter->elem_handle != NULL;
972 }
973
974 2838 static void cx_ll_iter_next(void *it) {
975 2838 struct cx_iterator_s *iter = it;
976
2/2
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 2808 times.
 2838 if (iter->base.remove) {
977 30 iter->base.remove = false;
978 30 struct cx_list_s *list = iter->src_handle.m;
979 30 cx_linked_list *ll = iter->src_handle.m;
980 30 cx_linked_list_node *node = iter->elem_handle;
981 30 iter->elem_handle = node->next;
982
8/8
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 28 times.
✓ Branch 2 taken 1 times.
✓ Branch 3 taken 1 times.
✓ Branch 5 taken 2 times.
✓ Branch 6 taken 28 times.
✓ Branch 7 taken 1 times.
✓ Branch 8 taken 1 times.
 30 cx_invoke_destructor(list, node->payload);
983 30 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
984 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
985 30 list->collection.size--;
986 30 cxFree(list->collection.allocator, node);
987 } else {
988 2808 iter->index++;
989 2808 cx_linked_list_node *node = iter->elem_handle;
990 2808 iter->elem_handle = node->next;
991 }
992 2838 }
993
994 222 static void cx_ll_iter_prev(void *it) {
995 222 struct cx_iterator_s *iter = it;
996
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 194 times.
 222 if (iter->base.remove) {
997 28 iter->base.remove = false;
998 28 struct cx_list_s *list = iter->src_handle.m;
999 28 cx_linked_list *ll = iter->src_handle.m;
1000 28 cx_linked_list_node *node = iter->elem_handle;
1001 28 iter->elem_handle = node->prev;
1002 28 iter->index--;
1003
8/8
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 26 times.
✓ Branch 2 taken 1 times.
✓ Branch 3 taken 1 times.
✓ Branch 5 taken 2 times.
✓ Branch 6 taken 26 times.
✓ Branch 7 taken 1 times.
✓ Branch 8 taken 1 times.
 28 cx_invoke_destructor(list, node->payload);
1004 28 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
1005 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
1006 28 list->collection.size--;
1007 28 cxFree(list->collection.allocator, node);
1008 } else {
1009 194 iter->index--;
1010 194 cx_linked_list_node *node = iter->elem_handle;
1011 194 iter->elem_handle = node->prev;
1012 }
1013 222 }
1014
1015 3084 static void *cx_ll_iter_current(const void *it) {
1016 3084 const struct cx_iterator_s *iter = it;
1017 3084 cx_linked_list_node *node = iter->elem_handle;
1018 3084 return node->payload;
1019 }
1020
1021 114 static CxIterator cx_ll_iterator(
1022 const struct cx_list_s *list,
1023 size_t index,
1024 bool backwards
1025 ) {
1026 CxIterator iter;
1027 114 iter.index = index;
1028 114 iter.src_handle.c = list;
1029 114 iter.elem_handle = cx_ll_node_at((const cx_linked_list *) list, index);
1030 114 iter.elem_size = list->collection.elem_size;
1031 114 iter.elem_count = list->collection.size;
1032 114 iter.base.valid = cx_ll_iter_valid;
1033 114 iter.base.current = cx_ll_iter_current;
1034
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 102 times.
 114 iter.base.next = backwards ? cx_ll_iter_prev : cx_ll_iter_next;
1035 114 iter.base.mutating = false;
1036 114 iter.base.remove = false;
1037 114 return iter;
1038 }
1039
1040 10 static int cx_ll_insert_iter(
1041 CxIterator *iter,
1042 const void *elem,
1043 int prepend
1044 ) {
1045 10 struct cx_list_s *list = iter->src_handle.m;
1046 10 cx_linked_list_node *node = iter->elem_handle;
1047
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 4 times.
 10 if (node != NULL) {
1048 assert(prepend >= 0 && prepend <= 1);
1049 6 cx_linked_list_node *choice[2] = {node, node->prev};
1050 6 int result = cx_ll_insert_at(list, choice[prepend], elem);
1051
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 if (result == 0) {
1052 6 iter->elem_count++;
1053
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 2 times.
 6 if (prepend) {
1054 4 iter->index++;
1055 }
1056 }
1057 6 return result;
1058 } else {
1059 4 int result = cx_ll_insert_element(list, list->collection.size, elem);
1060
1/2
✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
 4 if (result == 0) {
1061 4 iter->elem_count++;
1062 4 iter->index = list->collection.size;
1063 }
1064 4 return result;
1065 }
1066 }
1067
1068 73 static void cx_ll_destructor(CxList *list) {
1069 73 cx_linked_list *ll = (cx_linked_list *) list;
1070
1071 73 cx_linked_list_node *node = ll->begin;
1072
2/2
✓ Branch 0 taken 5116 times.
✓ Branch 1 taken 73 times.
 5189 while (node) {
1073
7/8
✓ Branch 0 taken 25 times.
✓ Branch 1 taken 5091 times.
✓ Branch 2 taken 13 times.
✓ Branch 3 taken 12 times.
✓ Branch 5 taken 1 times.
✓ Branch 6 taken 5115 times.
✓ Branch 7 taken 1 times.
✗ Branch 8 not taken.
 5116 cx_invoke_destructor(list, node->payload);
1074 5116 void *next = node->next;
1075 5116 cxFree(list->collection.allocator, node);
1076 5116 node = next;
1077 }
1078
1079 73 cxFree(list->collection.allocator, list);
1080 73 }
1081
1082 static cx_list_class cx_linked_list_class = {
1083 cx_ll_destructor,
1084 cx_ll_insert_element,
1085 cx_ll_insert_array,
1086 cx_ll_insert_sorted,
1087 cx_ll_insert_iter,
1088 cx_ll_remove,
1089 cx_ll_clear,
1090 cx_ll_swap,
1091 cx_ll_at,
1092 cx_ll_find_remove,
1093 cx_ll_sort,
1094 cx_ll_compare,
1095 cx_ll_reverse,
1096 cx_ll_iterator,
1097 };
1098
1099 73 CxList *cxLinkedListCreate(
1100 const CxAllocator *allocator,
1101 cx_compare_func comparator,
1102 size_t elem_size
1103 ) {
1104
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 68 times.
 73 if (allocator == NULL) {
1105 5 allocator = cxDefaultAllocator;
1106 }
1107
1108 73 cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list));
1109
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 73 times.
 73 if (list == NULL) return NULL;
1110 73 cx_list_init((CxList*)list, &cx_linked_list_class,
1111 allocator, comparator, elem_size);
1112
1113 73 return (CxList *) list;
1114 }
1115