GCC Code Coverage Report

Directory: ./
File: linked_list.c
Date: 2025-12-31 16:19:05
Exec Total Coverage
Lines: 592 592 100.0%
Functions: 56 56 100.0%
Branches: 302 334 90.4%
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 #if __STDC_VERSION__ < 202311L
35 // we cannot simply include stdalign.h
36 // because Solaris is not entirely C11 complaint
37 #ifndef __alignof_is_defined
38 #define alignof _Alignof
39 #define __alignof_is_defined 1
40 #endif
41 #endif
42
43 // LOW LEVEL LINKED LIST FUNCTIONS
44
45 #define CX_LL_PTR(cur, off) (*(void**)(((char*)(cur))+(off)))
46 #define ll_prev(node) CX_LL_PTR(node, loc_prev)
47 #define ll_next(node) CX_LL_PTR(node, loc_next)
48 #define ll_advance(node) CX_LL_PTR(node, loc_advance)
49 #define ll_data(node) (((char*)(node))+loc_data)
50
51 29001 void *cx_linked_list_at(
52 const void *start,
53 size_t start_index,
54 ptrdiff_t loc_advance,
55 size_t index
56 ) {
57 assert(start != NULL);
58 assert(loc_advance >= 0);
59 29001 size_t i = start_index;
60 29001 const void *cur = start;
61
3/4
✓ Branch 0 (7→8) taken 2737056 times.
✓ Branch 1 (7→9) taken 29001 times.
✓ Branch 2 (8→3) taken 2737056 times.
✗ Branch 3 (8→9) not taken.
 2766057 while (i != index && cur != NULL) {
62 2737056 cur = ll_advance(cur);
63
2/2
✓ Branch 0 (3→4) taken 1376447 times.
✓ Branch 1 (3→5) taken 1360609 times.
 2737056 i < index ? i++ : i--;
64 }
65 29001 return (void *) cur;
66 }
67
68 537 void *cx_linked_list_find_c(
69 const void *start,
70 ptrdiff_t loc_advance,
71 ptrdiff_t loc_data,
72 const void *elem,
73 size_t *found_index,
74 cx_compare_func2 cmp_func,
75 void *context
76 ) {
77 assert(start != NULL);
78 assert(loc_advance >= 0);
79 assert(loc_data >= 0);
80 assert(cmp_func);
81
82 537 void *node = (void*) start;
83 537 size_t index = 0;
84 do {
85 45107 void *current = ll_data(node);
86
2/2
✓ Branch 0 (4→5) taken 238 times.
✓ Branch 1 (4→8) taken 44869 times.
 45107 if (cmp_func(current, elem, context) == 0) {
87
1/2
✓ Branch 0 (5→6) taken 238 times.
✗ Branch 1 (5→7) not taken.
 238 if (found_index != NULL) {
88 238 *found_index = index;
89 }
90 238 return node;
91 }
92 44869 node = ll_advance(node);
93 44869 index++;
94
2/2
✓ Branch 0 (8→9) taken 44570 times.
✓ Branch 1 (8→10) taken 299 times.
 44869 } while (node != NULL);
95 299 return NULL;
96 }
97
98 6 void *cx_linked_list_find(
99 const void *start,
100 ptrdiff_t loc_advance,
101 ptrdiff_t loc_data,
102 const void *elem,
103 size_t *found_index,
104 cx_compare_func cmp_func
105 ) {
106 6 cx_compare_func_wrapper wrapper = {cmp_func};
107 6 return cx_linked_list_find_c(start, loc_advance, loc_data,
108 elem, found_index, cx_cmp_wrap, &wrapper);
109 }
110
111 5 void *cx_linked_list_first(
112 const void *node,
113 ptrdiff_t loc_prev
114 ) {
115 5 return cx_linked_list_last(node, loc_prev);
116 }
117
118 82 void *cx_linked_list_last(
119 const void *node,
120 ptrdiff_t loc_next
121 ) {
122 assert(node != NULL);
123 assert(loc_next >= 0);
124
125 82 const void *cur = node;
126 const void *last;
127 do {
128 5169 last = cur;
129
2/2
✓ Branch 0 (3→4) taken 5087 times.
✓ Branch 1 (3→5) taken 82 times.
 5169 } while ((cur = ll_next(cur)) != NULL);
130
131 82 return (void *) last;
132 }
133
134 5 void *cx_linked_list_prev(
135 const void *begin,
136 ptrdiff_t loc_next,
137 const void *node
138 ) {
139 assert(begin != NULL);
140 assert(node != NULL);
141 assert(loc_next >= 0);
142
2/2
✓ Branch 0 (2→3) taken 1 times.
✓ Branch 1 (2→4) taken 4 times.
 5 if (begin == node) return NULL;
143 4 const void *cur = begin;
144 const void *next;
145 while (1) {
146 7 next = ll_next(cur);
147
2/2
✓ Branch 0 (5→6) taken 4 times.
✓ Branch 1 (5→7) taken 3 times.
 7 if (next == node) return (void *) cur;
148 3 cur = next;
149 }
150 }
151
152 1835670 void cx_linked_list_link(
153 void *left,
154 void *right,
155 ptrdiff_t loc_prev,
156 ptrdiff_t loc_next
157 ) {
158 assert(loc_next >= 0);
159 1835670 ll_next(left) = right;
160
2/2
✓ Branch 0 (2→3) taken 1835667 times.
✓ Branch 1 (2→4) taken 3 times.
 1835670 if (loc_prev >= 0) {
161 1835667 ll_prev(right) = left;
162 }
163 1835670 }
164
165 2 void cx_linked_list_unlink(
166 void *left,
167 void *right,
168 ptrdiff_t loc_prev,
169 ptrdiff_t loc_next
170 ) {
171 assert (loc_next >= 0);
172 assert(ll_next(left) == right);
173 2 ll_next(left) = NULL;
174
1/2
✓ Branch 0 (2→3) taken 2 times.
✗ Branch 1 (2→4) not taken.
 2 if (loc_prev >= 0) {
175 assert(ll_prev(right) == left);
176 2 ll_prev(right) = NULL;
177 }
178 2 }
179
180 10 void cx_linked_list_add(
181 void **begin,
182 void **end,
183 ptrdiff_t loc_prev,
184 ptrdiff_t loc_next,
185 void *new_node
186 ) {
187 void *last;
188
2/2
✓ Branch 0 (2→3) taken 3 times.
✓ Branch 1 (2→6) taken 7 times.
 10 if (end == NULL) {
189 assert(begin != NULL);
190
2/2
✓ Branch 0 (3→4) taken 2 times.
✓ Branch 1 (3→5) taken 1 times.
 3 last = *begin == NULL ? NULL : cx_linked_list_last(*begin, loc_next);
191 } else {
192 7 last = *end;
193 }
194 10 cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, last, new_node, new_node);
195 10 }
196
197 11 void cx_linked_list_prepend(
198 void **begin,
199 void **end,
200 ptrdiff_t loc_prev,
201 ptrdiff_t loc_next,
202 void *new_node
203 ) {
204 11 cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, NULL, new_node, new_node);
205 11 }
206
207 3 void cx_linked_list_insert(
208 void **begin,
209 void **end,
210 ptrdiff_t loc_prev,
211 ptrdiff_t loc_next,
212 void *node,
213 void *new_node
214 ) {
215 3 cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, node, new_node, new_node);
216 3 }
217
218 21913 void cx_linked_list_insert_chain(
219 void **begin,
220 void **end,
221 ptrdiff_t loc_prev,
222 ptrdiff_t loc_next,
223 void *node,
224 void *insert_begin,
225 void *insert_end
226 ) {
227 // find the end of the chain, if not specified
228
2/2
✓ Branch 0 (2→3) taken 3 times.
✓ Branch 1 (2→4) taken 21910 times.
 21913 if (insert_end == NULL) {
229 3 insert_end = cx_linked_list_last(insert_begin, loc_next);
230 }
231
232 // determine the successor
233 void *successor;
234
2/2
✓ Branch 0 (4→5) taken 464 times.
✓ Branch 1 (4→10) taken 21449 times.
 21913 if (node == NULL) {
235 assert(begin != NULL || (end != NULL && loc_prev >= 0));
236
2/2
✓ Branch 0 (5→6) taken 460 times.
✓ Branch 1 (5→7) taken 4 times.
 464 if (begin != NULL) {
237 460 successor = *begin;
238 460 *begin = insert_begin;
239 } else {
240
2/2
✓ Branch 0 (7→8) taken 2 times.
✓ Branch 1 (7→9) taken 2 times.
 4 successor = *end == NULL ? NULL : cx_linked_list_first(*end, loc_prev);
241 }
242 } else {
243 21449 successor = ll_next(node);
244 21449 cx_linked_list_link(node, insert_begin, loc_prev, loc_next);
245 }
246
247
2/2
✓ Branch 0 (11→12) taken 21688 times.
✓ Branch 1 (11→14) taken 225 times.
 21913 if (successor == NULL) {
248 // the list ends with the new chain
249
2/2
✓ Branch 0 (12→13) taken 21684 times.
✓ Branch 1 (12→15) taken 4 times.
 21688 if (end != NULL) {
250 21684 *end = insert_end;
251 }
252 } else {
253 225 cx_linked_list_link(insert_end, successor, loc_prev, loc_next);
254 }
255 21913 }
256
257 92 static void *cx_linked_list_insert_sorted_chain_impl(
258 void **begin,
259 void **end,
260 ptrdiff_t loc_prev,
261 ptrdiff_t loc_next,
262 void *insert_begin,
263 cx_compare_func2 cmp_func,
264 void *context,
265 bool allow_duplicates
266 ) {
267 assert(begin != NULL);
268 assert(loc_next >= 0);
269 assert(insert_begin != NULL);
270
271 // strategy: build completely new chains from scratch
272 92 void *source_original = *begin;
273 92 void *source_argument = insert_begin;
274 92 void *new_begin = NULL;
275 92 void *new_end = NULL;
276 92 void *dup_begin = NULL;
277 92 void *dup_end = NULL;
278
279 // determine the new start
280 {
281
2/2
✓ Branch 0 (2→3) taken 82 times.
✓ Branch 1 (2→4) taken 10 times.
 92 int d = source_original == NULL ? 1 : cmp_func(source_original, source_argument, context);
282
2/2
✓ Branch 0 (5→6) taken 71 times.
✓ Branch 1 (5→12) taken 21 times.
 92 if (d <= 0) {
283 // the new chain starts with the original chain
284 71 new_begin = new_end = source_original;
285 71 source_original = ll_next(source_original);
286
2/2
✓ Branch 0 (6→7) taken 2 times.
✓ Branch 1 (6→13) taken 69 times.
 71 if (d == 0) {
287
2/2
✓ Branch 0 (7→8) taken 1 times.
✓ Branch 1 (7→10) taken 1 times.
 2 if (allow_duplicates) {
288 // duplicate allowed, append it to the chain
289 1 cx_linked_list_link(new_end, source_argument, loc_prev, loc_next);
290 1 new_end = source_argument;
291 } else {
292 // duplicate is not allowed, start a duplicate chain with the argument
293 1 dup_begin = dup_end = source_argument;
294 }
295 2 source_argument = ll_next(source_argument);
296 }
297 } else {
298 // input is smaller, or there is no original chain;
299 // start the new chain with the source argument
300 21 new_begin = new_end = source_argument;
301 21 source_argument = ll_next(source_argument);
302 }
303 }
304
305 // now successively compare the elements and add them to the correct chains
306
4/4
✓ Branch 0 (38→39) taken 661 times.
✓ Branch 1 (38→40) taken 37 times.
✓ Branch 2 (39→14) taken 606 times.
✓ Branch 3 (39→40) taken 55 times.
 698 while (source_original != NULL && source_argument != NULL) {
307 606 int d = cmp_func(source_original, source_argument, context);
308
2/2
✓ Branch 0 (15→16) taken 444 times.
✓ Branch 1 (15→26) taken 162 times.
 606 if (d <= 0) {
309 // the original is not larger, add it to the chain
310 444 cx_linked_list_link(new_end, source_original, loc_prev, loc_next);
311 444 new_end = source_original;
312 444 source_original = ll_next(source_original);
313
2/2
✓ Branch 0 (17→18) taken 35 times.
✓ Branch 1 (17→37) taken 409 times.
 444 if (d == 0) {
314
2/2
✓ Branch 0 (18→19) taken 12 times.
✓ Branch 1 (18→21) taken 23 times.
 35 if (allow_duplicates) {
315 // duplicate allowed, append it to the chain
316 12 cx_linked_list_link(new_end, source_argument, loc_prev, loc_next);
317 12 new_end = source_argument;
318 } else {
319 // duplicate is not allowed, append it to the duplicate chain
320
2/2
✓ Branch 0 (21→22) taken 10 times.
✓ Branch 1 (21→23) taken 13 times.
 23 if (dup_end == NULL) {
321 10 dup_begin = dup_end = source_argument;
322 } else {
323 13 cx_linked_list_link(dup_end, source_argument, loc_prev, loc_next);
324 13 dup_end = source_argument;
325 }
326 }
327 35 source_argument = ll_next(source_argument);
328 }
329 } else {
330 // the original is larger, append the source argument to the chain
331 // check if we must discard the source argument as duplicate
332
4/4
✓ Branch 0 (26→27) taken 99 times.
✓ Branch 1 (26→34) taken 63 times.
✓ Branch 2 (28→29) taken 25 times.
✓ Branch 3 (28→34) taken 74 times.
 162 if (!allow_duplicates && cmp_func(new_end, source_argument, context) == 0) {
333
2/2
✓ Branch 0 (29→30) taken 9 times.
✓ Branch 1 (29→31) taken 16 times.
 25 if (dup_end == NULL) {
334 9 dup_begin = dup_end = source_argument;
335 } else {
336 16 cx_linked_list_link(dup_end, source_argument, loc_prev, loc_next);
337 16 dup_end = source_argument;
338 }
339 } else {
340 // no duplicate or duplicates allowed
341 137 cx_linked_list_link(new_end, source_argument, loc_prev, loc_next);
342 137 new_end = source_argument;
343 }
344 162 source_argument = ll_next(source_argument);
345 }
346 }
347
348
2/2
✓ Branch 0 (40→41) taken 55 times.
✓ Branch 1 (40→43) taken 37 times.
 92 if (source_original != NULL) {
349 // something is left from the original chain, append it
350 55 cx_linked_list_link(new_end, source_original, loc_prev, loc_next);
351 55 new_end = cx_linked_list_last(source_original, loc_next);
352
2/2
✓ Branch 0 (43→44) taken 21 times.
✓ Branch 1 (43→58) taken 16 times.
 37 } else if (source_argument != NULL) {
353 // something is left from the input chain;
354 // when we allow duplicates, append it
355
2/2
✓ Branch 0 (44→45) taken 10 times.
✓ Branch 1 (44→47) taken 11 times.
 21 if (allow_duplicates) {
356 10 cx_linked_list_link(new_end, source_argument, loc_prev, loc_next);
357 10 new_end = cx_linked_list_last(source_argument, loc_next);
358 } else {
359 // otherwise we must check one-by-one
360
2/2
✓ Branch 0 (57→48) taken 34 times.
✓ Branch 1 (57→58) taken 11 times.
 45 while (source_argument != NULL) {
361
2/2
✓ Branch 0 (49→50) taken 6 times.
✓ Branch 1 (49→54) taken 28 times.
 34 if (cmp_func(new_end, source_argument, context) == 0) {
362
2/2
✓ Branch 0 (50→51) taken 1 times.
✓ Branch 1 (50→52) taken 5 times.
 6 if (dup_end == NULL) {
363 1 dup_begin = dup_end = source_argument;
364 } else {
365 5 cx_linked_list_link(dup_end, source_argument, loc_prev, loc_next);
366 5 dup_end = source_argument;
367 }
368 } else {
369 28 cx_linked_list_link(new_end, source_argument, loc_prev, loc_next);
370 28 new_end = source_argument;
371 }
372 34 source_argument = ll_next(source_argument);
373 }
374 }
375 }
376
377 // null the next pointers at the end of the chain
378 92 ll_next(new_end) = NULL;
379
2/2
✓ Branch 0 (58→59) taken 21 times.
✓ Branch 1 (58→60) taken 71 times.
 92 if (dup_end != NULL) {
380 21 ll_next(dup_end) = NULL;
381 }
382
383 // null the optional prev pointers
384
1/2
✓ Branch 0 (60→61) taken 92 times.
✗ Branch 1 (60→63) not taken.
 92 if (loc_prev >= 0) {
385 92 ll_prev(new_begin) = NULL;
386
2/2
✓ Branch 0 (61→62) taken 21 times.
✓ Branch 1 (61→63) taken 71 times.
 92 if (dup_begin != NULL) {
387 21 ll_prev(dup_begin) = NULL;
388 }
389 }
390
391 // output
392 92 *begin = new_begin;
393
1/2
✓ Branch 0 (63→64) taken 92 times.
✗ Branch 1 (63→65) not taken.
 92 if (end != NULL) {
394 92 *end = new_end;
395 }
396 92 return dup_begin;
397 }
398
399 2 void cx_linked_list_insert_sorted(
400 void **begin,
401 void **end,
402 ptrdiff_t loc_prev,
403 ptrdiff_t loc_next,
404 void *new_node,
405 cx_compare_func cmp_func
406 ) {
407 assert(ll_next(new_node) == NULL);
408 2 cx_linked_list_insert_sorted_chain(
409 begin, end, loc_prev, loc_next, new_node, cmp_func);
410 2 }
411
412 3 void cx_linked_list_insert_sorted_chain(
413 void **begin,
414 void **end,
415 ptrdiff_t loc_prev,
416 ptrdiff_t loc_next,
417 void *insert_begin,
418 cx_compare_func cmp_func
419 ) {
420 3 cx_compare_func_wrapper wrapper = {cmp_func};
421 3 cx_linked_list_insert_sorted_chain_impl(
422 begin, end, loc_prev, loc_next,
423 insert_begin, cx_cmp_wrap, &wrapper, true);
424 3 }
425
426 3 int cx_linked_list_insert_unique(
427 void **begin,
428 void **end,
429 ptrdiff_t loc_prev,
430 ptrdiff_t loc_next,
431 void *new_node,
432 cx_compare_func cmp_func
433 ) {
434 assert(ll_next(new_node) == NULL);
435 3 return NULL != cx_linked_list_insert_unique_chain(
436 begin, end, loc_prev, loc_next, new_node, cmp_func);
437 }
438
439 4 void *cx_linked_list_insert_unique_chain(
440 void **begin,
441 void **end,
442 ptrdiff_t loc_prev,
443 ptrdiff_t loc_next,
444 void *insert_begin,
445 cx_compare_func cmp_func
446 ) {
447 4 cx_compare_func_wrapper wrapper = {cmp_func};
448 4 return cx_linked_list_insert_sorted_chain_impl(
449 begin, end, loc_prev, loc_next,
450 insert_begin, cx_cmp_wrap, &wrapper, false);
451 }
452
453 1 void cx_linked_list_insert_sorted_c(
454 void **begin,
455 void **end,
456 ptrdiff_t loc_prev,
457 ptrdiff_t loc_next,
458 void *new_node,
459 cx_compare_func2 cmp_func,
460 void *context
461 ) {
462 assert(ll_next(new_node) == NULL);
463 1 cx_linked_list_insert_sorted_chain_c(
464 begin, end, loc_prev, loc_next, new_node, cmp_func, context);
465 1 }
466
467 1 void cx_linked_list_insert_sorted_chain_c(
468 void **begin,
469 void **end,
470 ptrdiff_t loc_prev,
471 ptrdiff_t loc_next,
472 void *insert_begin,
473 cx_compare_func2 cmp_func,
474 void *context
475 ) {
476 1 cx_linked_list_insert_sorted_chain_impl(
477 begin, end, loc_prev, loc_next,
478 insert_begin, cmp_func, context, true);
479 1 }
480
481 1 int cx_linked_list_insert_unique_c(
482 void **begin,
483 void **end,
484 ptrdiff_t loc_prev,
485 ptrdiff_t loc_next,
486 void *new_node,
487 cx_compare_func2 cmp_func,
488 void *context
489 ) {
490 assert(ll_next(new_node) == NULL);
491 1 return NULL != cx_linked_list_insert_unique_chain_c(
492 begin, end, loc_prev, loc_next, new_node, cmp_func, context);
493 }
494
495 1 void *cx_linked_list_insert_unique_chain_c(
496 void **begin,
497 void **end,
498 ptrdiff_t loc_prev,
499 ptrdiff_t loc_next,
500 void *insert_begin,
501 cx_compare_func2 cmp_func,
502 void *context
503 ) {
504 1 return cx_linked_list_insert_sorted_chain_impl(
505 begin, end, loc_prev, loc_next,
506 insert_begin, cmp_func, context, false);
507 }
508
509 349 size_t cx_linked_list_remove_chain(
510 void **begin,
511 void **end,
512 ptrdiff_t loc_prev,
513 ptrdiff_t loc_next,
514 void *node,
515 size_t num
516 ) {
517 assert(node != NULL);
518 assert(loc_next >= 0);
519 assert(loc_prev >= 0 || begin != NULL);
520
521 // easy exit
522
1/2
✗ Branch 0 (2→3) not taken.
✓ Branch 1 (2→4) taken 349 times.
 349 if (num == 0) return 0;
523
524 // find adjacent nodes
525 void *prev;
526
2/2
✓ Branch 0 (4→5) taken 347 times.
✓ Branch 1 (4→6) taken 2 times.
 349 if (loc_prev >= 0) {
527 347 prev = ll_prev(node);
528 } else {
529 2 prev = cx_linked_list_prev(*begin, loc_next, node);
530 }
531
532 349 void *next = ll_next(node);
533 349 size_t removed = 1;
534
4/4
✓ Branch 0 (9→10) taken 100 times.
✓ Branch 1 (9→11) taken 344 times.
✓ Branch 2 (10→8) taken 95 times.
✓ Branch 3 (10→11) taken 5 times.
 444 for (; removed < num && next != NULL ; removed++) {
535 95 next = ll_next(next);
536 }
537
538 // update next pointer of prev node, or set begin
539
2/2
✓ Branch 0 (11→12) taken 34 times.
✓ Branch 1 (11→14) taken 315 times.
 349 if (prev == NULL) {
540
1/2
✓ Branch 0 (12→13) taken 34 times.
✗ Branch 1 (12→15) not taken.
 34 if (begin != NULL) {
541 34 *begin = next;
542 }
543 } else {
544 315 ll_next(prev) = next;
545 }
546
547 // update prev pointer of next node, or set end
548
2/2
✓ Branch 0 (15→16) taken 56 times.
✓ Branch 1 (15→18) taken 293 times.
 349 if (next == NULL) {
549
1/2
✓ Branch 0 (16→17) taken 56 times.
✗ Branch 1 (16→20) not taken.
 56 if (end != NULL) {
550 56 *end = prev;
551 }
552
2/2
✓ Branch 0 (18→19) taken 292 times.
✓ Branch 1 (18→20) taken 1 times.
 293 } else if (loc_prev >= 0) {
553 292 ll_prev(next) = prev;
554 }
555
556 349 return removed;
557 }
558
559 251 void cx_linked_list_remove(
560 void **begin,
561 void **end,
562 ptrdiff_t loc_prev,
563 ptrdiff_t loc_next,
564 void *node
565 ) {
566 251 cx_linked_list_remove_chain(begin, end, loc_prev, loc_next, node, 1);
567 251 }
568
569 1774 size_t cx_linked_list_size(
570 const void *node,
571 ptrdiff_t loc_next
572 ) {
573 assert(loc_next >= 0);
574 1774 size_t size = 0;
575
2/2
✓ Branch 0 (4→3) taken 1797774 times.
✓ Branch 1 (4→5) taken 1774 times.
 1799548 while (node != NULL) {
576 1797774 node = ll_next(node);
577 1797774 size++;
578 }
579 1774 return size;
580 }
581
582 #ifndef CX_LINKED_LIST_SORT_SBO_SIZE
583 #define CX_LINKED_LIST_SORT_SBO_SIZE 1024
584 #endif
585
586 3533 static void cx_linked_list_sort_merge(
587 void **begin,
588 void **end,
589 ptrdiff_t loc_prev,
590 ptrdiff_t loc_next,
591 ptrdiff_t loc_data,
592 size_t length,
593 void *ls,
594 void *le,
595 void *re,
596 cx_compare_func2 cmp_func,
597 void *context
598 ) {
599 void *sbo[CX_LINKED_LIST_SORT_SBO_SIZE];
600 2812 void **sorted = length >= CX_LINKED_LIST_SORT_SBO_SIZE ?
601
2/2
✓ Branch 0 (2→3) taken 721 times.
✓ Branch 1 (2→4) taken 2812 times.
 3533 cxMallocDefault(sizeof(void *) * length) : sbo;
602 − if (sorted == NULL) abort(); // LCOV_EXCL_LINE
603 void *rc, *lc;
604
605 3533 lc = ls;
606 3533 rc = le;
607 3533 size_t n = 0;
608
6/6
✓ Branch 0 (13→14) taken 1444707 times.
✓ Branch 1 (13→16) taken 1687 times.
✓ Branch 2 (14→15) taken 1443969 times.
✓ Branch 3 (14→16) taken 738 times.
✓ Branch 4 (15→8) taken 1442861 times.
✓ Branch 5 (15→16) taken 1108 times.
 1446394 while (lc && lc != le && rc != re) {
609
2/2
✓ Branch 0 (9→10) taken 9111 times.
✓ Branch 1 (9→11) taken 1433750 times.
 1442861 if (cmp_func(ll_data(lc), ll_data(rc), context) <= 0) {
610 9111 sorted[n] = lc;
611 9111 lc = ll_next(lc);
612 } else {
613 1433750 sorted[n] = rc;
614 1433750 rc = ll_next(rc);
615 }
616 1442861 n++;
617 }
618
4/4
✓ Branch 0 (18→19) taken 3192 times.
✓ Branch 1 (18→20) taken 1762 times.
✓ Branch 2 (19→17) taken 1421 times.
✓ Branch 3 (19→20) taken 1771 times.
 4954 while (lc && lc != le) {
619 1421 sorted[n] = lc;
620 1421 lc = ll_next(lc);
621 1421 n++;
622 }
623
4/4
✓ Branch 0 (22→23) taken 369268 times.
✓ Branch 1 (22→24) taken 1771 times.
✓ Branch 2 (23→21) taken 367506 times.
✓ Branch 3 (23→24) taken 1762 times.
 371039 while (rc && rc != re) {
624 367506 sorted[n] = rc;
625 367506 rc = ll_next(rc);
626 367506 n++;
627 }
628
629 // Update pointer
630
1/2
✓ Branch 0 (24→25) taken 3533 times.
✗ Branch 1 (24→26) not taken.
 3533 if (loc_prev >= 0) ll_prev(sorted[0]) = NULL;
631
2/2
✓ Branch 0 (29→27) taken 1808255 times.
✓ Branch 1 (29→30) taken 3533 times.
 1811788 for (size_t i = 0 ; i < length - 1; i++) {
632 1808255 cx_linked_list_link(sorted[i], sorted[i + 1], loc_prev, loc_next);
633 }
634 3533 ll_next(sorted[length - 1]) = NULL;
635
636 3533 *begin = sorted[0];
637 3533 *end = sorted[length - 1];
638
2/2
✓ Branch 0 (30→31) taken 721 times.
✓ Branch 1 (30→32) taken 2812 times.
 3533 if (sorted != sbo) {
639 721 cxFreeDefault(sorted);
640 }
641 3533 }
642
643 1792 void cx_linked_list_sort_c( // NOLINT(misc-no-recursion) - purposely recursive function
644 void **begin,
645 void **end,
646 ptrdiff_t loc_prev,
647 ptrdiff_t loc_next,
648 ptrdiff_t loc_data,
649 cx_compare_func2 cmp_func,
650 void *context
651 ) {
652 assert(begin != NULL);
653 assert(loc_next >= 0);
654 assert(loc_data >= 0);
655 assert(cmp_func);
656
657 void *lc, *ls, *le, *re;
658
659 // set start node
660 1792 ls = *begin;
661
662 // early exit when this list is empty
663
2/2
✓ Branch 0 (2→3) taken 1 times.
✓ Branch 1 (2→4) taken 1791 times.
 1792 if (ls == NULL) return;
664
665 // check how many elements are already sorted
666 1791 lc = ls;
667 1791 size_t ln = 1;
668
4/4
✓ Branch 0 (6→7) taken 4038 times.
✓ Branch 1 (6→9) taken 20 times.
✓ Branch 2 (8→5) taken 2267 times.
✓ Branch 3 (8→9) taken 1771 times.
 4058 while (ll_next(lc) != NULL && cmp_func(ll_data(ll_next(lc)), ll_data(lc), context) > 0) {
669 2267 lc = ll_next(lc);
670 2267 ln++;
671 }
672 1791 le = ll_next(lc);
673
674 // if first unsorted node is NULL, the list is already completely sorted
675
2/2
✓ Branch 0 (9→10) taken 1771 times.
✓ Branch 1 (9→24) taken 20 times.
 1791 if (le != NULL) {
676 void *rc;
677 1771 size_t rn = 1;
678 1771 rc = le;
679 // skip already sorted elements
680
4/4
✓ Branch 0 (12→13) taken 3491 times.
✓ Branch 1 (12→15) taken 9 times.
✓ Branch 2 (14→11) taken 1729 times.
✓ Branch 3 (14→15) taken 1762 times.
 3500 while (ll_next(rc) != NULL && cmp_func(ll_data(ll_next(rc)), ll_data(rc), context) > 0) {
681 1729 rc = ll_next(rc);
682 1729 rn++;
683 }
684 1771 re = ll_next(rc);
685
686 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
687 void *sorted_begin, *sorted_end;
688 1771 cx_linked_list_sort_merge(&sorted_begin, &sorted_end,
689 loc_prev, loc_next, loc_data,
690 ln + rn, ls, le, re, cmp_func,
691 context);
692
693 // Something left? Sort it!
694 1771 size_t remainder_length = cx_linked_list_size(re, loc_next);
695
2/2
✓ Branch 0 (17→18) taken 1762 times.
✓ Branch 1 (17→21) taken 9 times.
 1771 if (remainder_length > 0) {
696 1762 void *remainder = re;
697 1762 cx_linked_list_sort_c(&remainder, NULL, loc_prev, loc_next, loc_data, cmp_func, context);
698
699 // merge sorted list with (also sorted) remainder
700 1762 cx_linked_list_sort_merge(&sorted_begin, &sorted_end,
701 loc_prev, loc_next, loc_data,
702 1762 ln + rn + remainder_length,
703 sorted_begin, remainder, NULL, cmp_func,
704 context);
705 }
706 1771 *begin = sorted_begin;
707
2/2
✓ Branch 0 (21→22) taken 27 times.
✓ Branch 1 (21→23) taken 1744 times.
 1771 if (end) *end = sorted_end;
708 }
709 }
710
711 2 void cx_linked_list_sort(
712 void **begin,
713 void **end,
714 ptrdiff_t loc_prev,
715 ptrdiff_t loc_next,
716 ptrdiff_t loc_data,
717 cx_compare_func cmp_func
718 ) {
719 2 cx_compare_func_wrapper wrapper = {cmp_func};
720 2 cx_linked_list_sort_c(begin, end, loc_prev, loc_next, loc_data, cx_cmp_wrap, &wrapper);
721 2 }
722
723 67 int cx_linked_list_compare_c(
724 const void *begin_left,
725 const void *begin_right,
726 ptrdiff_t loc_advance,
727 ptrdiff_t loc_data,
728 cx_compare_func2 cmp_func,
729 void *context
730 ) {
731 67 const void *left = begin_left, *right = begin_right;
732
733
4/4
✓ Branch 0 (7→8) taken 2210 times.
✓ Branch 1 (7→9) taken 37 times.
✓ Branch 2 (8→3) taken 2200 times.
✓ Branch 3 (8→9) taken 10 times.
 2247 while (left != NULL && right != NULL) {
734 2200 const void *left_data = ll_data(left);
735 2200 const void *right_data = ll_data(right);
736 2200 int result = cmp_func(left_data, right_data, context);
737
2/2
✓ Branch 0 (4→5) taken 20 times.
✓ Branch 1 (4→6) taken 2180 times.
 2200 if (result != 0) return result;
738 2180 left = ll_advance(left);
739 2180 right = ll_advance(right);
740 }
741
742
2/2
✓ Branch 0 (9→10) taken 10 times.
✓ Branch 1 (9→11) taken 37 times.
 47 if (left != NULL) { return 1; }
743
2/2
✓ Branch 0 (11→12) taken 10 times.
✓ Branch 1 (11→13) taken 27 times.
 37 else if (right != NULL) { return -1; }
744 27 else { return 0; }
745 }
746
747 6 int cx_linked_list_compare(
748 const void *begin_left,
749 const void *begin_right,
750 ptrdiff_t loc_advance,
751 ptrdiff_t loc_data,
752 cx_compare_func cmp_func
753 ) {
754 6 cx_compare_func_wrapper wrapper = {cmp_func};
755 6 return cx_linked_list_compare_c(begin_left, begin_right,
756 loc_advance, loc_data, cx_cmp_wrap, &wrapper);
757 }
758
759 5 void cx_linked_list_reverse(
760 void **begin,
761 void **end,
762 ptrdiff_t loc_prev,
763 ptrdiff_t loc_next
764 ) {
765 assert(begin != NULL);
766 assert(loc_next >= 0);
767
768 // swap all links
769 5 void *prev = NULL;
770 5 void *cur = *begin;
771
2/2
✓ Branch 0 (6→3) taken 204 times.
✓ Branch 1 (6→7) taken 5 times.
 209 while (cur != NULL) {
772 204 void *next = ll_next(cur);
773
774 204 ll_next(cur) = prev;
775
1/2
✓ Branch 0 (3→4) taken 204 times.
✗ Branch 1 (3→5) not taken.
 204 if (loc_prev >= 0) {
776 204 ll_prev(cur) = next;
777 }
778
779 204 prev = cur;
780 204 cur = next;
781 }
782
783 // update begin and end
784
1/2
✓ Branch 0 (7→8) taken 5 times.
✗ Branch 1 (7→9) not taken.
 5 if (end != NULL) {
785 5 *end = *begin;
786 }
787 5 *begin = prev;
788 5 }
789
790 // HIGH LEVEL LINKED LIST IMPLEMENTATION
791
792 29041 static void *cx_ll_node_at(
793 const cx_linked_list *list,
794 size_t index
795 ) {
796
2/2
✓ Branch 0 (2→3) taken 55 times.
✓ Branch 1 (2→4) taken 28986 times.
 29041 if (index >= list->base.collection.size) {
797 55 return NULL;
798
2/2
✓ Branch 0 (4→5) taken 19630 times.
✓ Branch 1 (4→7) taken 9356 times.
 28986 } else if (index > list->base.collection.size / 2) {
799 19630 return cx_linked_list_at(list->end, list->base.collection.size - 1, list->loc_prev, index);
800 } else {
801 9356 return cx_linked_list_at(list->begin, 0, list->loc_next, index);
802 }
803 }
804
805 22142 static void *cx_ll_malloc_node(const cx_linked_list *list) {
806 size_t n;
807
2/2
✓ Branch 0 (2→3) taken 12656 times.
✓ Branch 1 (2→4) taken 9486 times.
 22142 if (list->extra_data_len == 0) {
808 12656 n = list->loc_data + list->base.collection.elem_size;
809 } else {
810 9486 n = list->loc_extra + list->extra_data_len;
811 }
812 22142 return cxZalloc(list->base.collection.allocator, n);
813 }
814
815 21886 static int cx_ll_insert_at(
816 struct cx_list_s *list,
817 void *node,
818 const void *elem
819 ) {
820 21886 cx_linked_list *ll = (cx_linked_list *) list;
821
822 // create the new new_node
823 21886 void *new_node = cx_ll_malloc_node(ll);
824
825 // sortir if failed
826
1/2
✗ Branch 0 (3→4) not taken.
✓ Branch 1 (3→5) taken 21886 times.
 21886 if (new_node == NULL) return 1;
827
828 // copy the data
829
2/2
✓ Branch 0 (5→6) taken 21132 times.
✓ Branch 1 (5→7) taken 754 times.
 21886 if (elem != NULL) {
830 21132 memcpy((char*)new_node + ll->loc_data, elem, list->collection.elem_size);
831 }
832
833 // insert
834 21886 cx_linked_list_insert_chain(
835 &ll->begin, &ll->end,
836 21886 ll->loc_prev, ll->loc_next,
837 node, new_node, new_node
838 );
839
840 // increase the size and return
841 21886 list->collection.size++;
842 21886 return 0;
843 }
844
845 117 static size_t cx_ll_insert_array(
846 struct cx_list_s *list,
847 size_t index,
848 const void *array,
849 size_t n
850 ) {
851 // out-of bounds and corner case check
852
2/4
✓ Branch 0 (2→3) taken 117 times.
✗ Branch 1 (2→4) not taken.
✗ Branch 2 (3→4) not taken.
✓ Branch 3 (3→5) taken 117 times.
 117 if (index > list->collection.size || n == 0) return 0;
853
854 // find position efficiently
855
2/2
✓ Branch 0 (5→6) taken 38 times.
✓ Branch 1 (5→7) taken 79 times.
 117 void *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1);
856
857 // perform first insert
858
1/2
✗ Branch 0 (9→10) not taken.
✓ Branch 1 (9→11) taken 117 times.
 117 if (0 != cx_ll_insert_at(list, node, array)) return 1;
859
860 // is there more?
861
1/2
✗ Branch 0 (11→12) not taken.
✓ Branch 1 (11→13) taken 117 times.
 117 if (n == 1) return 1;
862
863 // we now know exactly where we are
864 117 cx_linked_list *ll = (cx_linked_list *) list;
865
2/2
✓ Branch 0 (13→14) taken 79 times.
✓ Branch 1 (13→15) taken 38 times.
 117 node = node == NULL ? ((cx_linked_list *) list)->begin : CX_LL_PTR(node, ll->loc_next);
866
867 // we can add the remaining nodes and immediately advance to the inserted node
868 117 const char *source = array;
869
2/2
✓ Branch 0 (23→17) taken 9119 times.
✓ Branch 1 (23→24) taken 117 times.
 9236 for (size_t i = 1; i < n; i++) {
870
2/2
✓ Branch 0 (17→18) taken 8821 times.
✓ Branch 1 (17→19) taken 298 times.
 9119 if (source != NULL) {
871 8821 source += list->collection.elem_size;
872 }
873
1/2
✗ Branch 0 (20→21) not taken.
✓ Branch 1 (20→22) taken 9119 times.
 9119 if (0 != cx_ll_insert_at(list, node, source)) return i;
874 9119 node = CX_LL_PTR(node, ll->loc_next);
875 }
876 117 return n;
877 }
878
879 12646 static void *cx_ll_insert_element(
880 struct cx_list_s *list,
881 size_t index,
882 const void *element
883 ) {
884 // out-of-bounds check
885
2/2
✓ Branch 0 (2→3) taken 8 times.
✓ Branch 1 (2→4) taken 12638 times.
 12646 if (index > list->collection.size) return NULL;
886
887 // find position efficiently
888
2/2
✓ Branch 0 (4→5) taken 12274 times.
✓ Branch 1 (4→6) taken 364 times.
 12638 void *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1);
889
890 // perform first insert
891
1/2
✗ Branch 0 (8→9) not taken.
✓ Branch 1 (8→10) taken 12638 times.
 12638 if (cx_ll_insert_at(list, node, element)) return NULL;
892
893 // return a pointer to the data of the inserted node
894 12638 cx_linked_list *ll = (cx_linked_list *) list;
895
2/2
✓ Branch 0 (10→11) taken 364 times.
✓ Branch 1 (10→12) taken 12274 times.
 12638 if (node == NULL) {
896 364 return (char*)(ll->begin) + ll->loc_data;
897 } else {
898 12274 char *next = CX_LL_PTR(node, ll->loc_next);
899 12274 return next + ll->loc_data;
900 }
901 }
902
903 787 static int cx_ll_insert_sorted_cmp_helper(const void *l, const void *r, void *c) {
904 787 cx_linked_list *list = c;
905 787 const char *left = (const char*)l + list->loc_data;
906 787 const char *right = (const char*)r + list->loc_data;
907 787 return cx_list_compare_wrapper(left, right, list);
908 }
909
910 83 static size_t cx_ll_insert_sorted_impl(
911 struct cx_list_s *list,
912 const void *array,
913 size_t n,
914 bool allow_duplicates
915 ) {
916 83 cx_linked_list *ll = (cx_linked_list *) list;
917
918 // special case
919
1/2
✗ Branch 0 (2→3) not taken.
✓ Branch 1 (2→4) taken 83 times.
 83 if (n == 0) return 0;
920
921 // create a new chain of nodes
922 83 void *chain = cx_ll_malloc_node(ll);
923
1/2
✗ Branch 0 (5→6) not taken.
✓ Branch 1 (5→7) taken 83 times.
 83 if (chain == NULL) return 0;
924
925 83 memcpy((char*)chain + ll->loc_data, array, list->collection.elem_size);
926
927 // add all elements from the array to that chain
928 83 void *prev = chain;
929 83 const char *src = array;
930 83 size_t inserted = 1;
931
2/2
✓ Branch 0 (12→8) taken 173 times.
✓ Branch 1 (12→13) taken 83 times.
 256 for (; inserted < n; inserted++) {
932 173 void *next = cx_ll_malloc_node(ll);
933
1/2
✗ Branch 0 (9→10) not taken.
✓ Branch 1 (9→11) taken 173 times.
 173 if (next == NULL) break;
934 173 src += list->collection.elem_size;
935 173 memcpy((char*)next + ll->loc_data, src, list->collection.elem_size);
936 173 CX_LL_PTR(prev, ll->loc_next) = next;
937 173 CX_LL_PTR(next, ll->loc_prev) = prev;
938 173 prev = next;
939 }
940 83 CX_LL_PTR(prev, ll->loc_next) = NULL;
941
942 // invoke the low-level function
943 83 void *duplicates = cx_linked_list_insert_sorted_chain_impl(
944 &ll->begin,
945 &ll->end,
946 83 ll->loc_prev,
947 83 ll->loc_next,
948 chain,
949 cx_ll_insert_sorted_cmp_helper,
950 list,
951 allow_duplicates
952 );
953 83 list->collection.size += inserted;
954
2/2
✓ Branch 0 (14→15) taken 42 times.
✓ Branch 1 (14→19) taken 41 times.
 83 if (!allow_duplicates) {
955 // free the nodes that did not make it into the list
956
2/2
✓ Branch 0 (18→16) taken 50 times.
✓ Branch 1 (18→19) taken 42 times.
 92 while (duplicates != NULL) {
957 50 void *next = CX_LL_PTR(duplicates, ll->loc_next);
958 50 cxFree(list->collection.allocator, duplicates);
959 50 duplicates = next;
960 50 list->collection.size--;
961 }
962 }
963
964 83 return inserted;
965 }
966
967 41 static size_t cx_ll_insert_sorted(
968 struct cx_list_s *list,
969 const void *array,
970 size_t n
971 ) {
972 41 return cx_ll_insert_sorted_impl(list, array, n, true);
973 }
974
975 42 static size_t cx_ll_insert_unique(
976 struct cx_list_s *list,
977 const void *array,
978 size_t n
979 ) {
980 42 return cx_ll_insert_sorted_impl(list, array, n, false);
981 }
982
983 120 static size_t cx_ll_remove(
984 struct cx_list_s *list,
985 size_t index,
986 size_t num,
987 void *targetbuf
988 ) {
989 120 cx_linked_list *ll = (cx_linked_list *) list;
990 120 void *node = cx_ll_node_at(ll, index);
991
992 // out-of-bounds check
993
2/2
✓ Branch 0 (3→4) taken 24 times.
✓ Branch 1 (3→5) taken 96 times.
 120 if (node == NULL) return 0;
994
995 // remove
996 96 size_t removed = cx_linked_list_remove_chain(
997 (void **) &ll->begin,
998 (void **) &ll->end,
999 96 ll->loc_prev,
1000 96 ll->loc_next,
1001 node,
1002 num
1003 );
1004
1005 // adjust size
1006 96 list->collection.size -= removed;
1007
1008 // copy or destroy the removed chain
1009
2/2
✓ Branch 0 (6→7) taken 60 times.
✓ Branch 1 (6→21) taken 36 times.
 96 if (targetbuf == NULL) {
1010 60 char *n = node;
1011
2/2
✓ Branch 0 (20→8) taken 113 times.
✓ Branch 1 (20→25) taken 60 times.
 173 for (size_t i = 0; i < removed; i++) {
1012 // element destruction
1013
8/8
✓ Branch 0 (8→9) taken 20 times.
✓ Branch 1 (8→13) taken 93 times.
✓ Branch 2 (9→10) taken 10 times.
✓ Branch 3 (9→11) taken 10 times.
✓ Branch 4 (13→14) taken 45 times.
✓ Branch 5 (13→18) taken 68 times.
✓ Branch 6 (14→15) taken 17 times.
✓ Branch 7 (14→16) taken 28 times.
 113 cx_invoke_destructor(list, n + ll->loc_data);
1014
1015 // free the node and advance
1016 113 void *next = CX_LL_PTR(n, ll->loc_next);
1017 113 cxFree(list->collection.allocator, n);
1018 113 n = next;
1019 }
1020 } else {
1021 36 char *dest = targetbuf;
1022 36 char *n = node;
1023
2/2
✓ Branch 0 (24→22) taken 77 times.
✓ Branch 1 (24→25) taken 36 times.
 113 for (size_t i = 0; i < removed; i++) {
1024 // copy payload
1025 77 memcpy(dest, n + ll->loc_data, list->collection.elem_size);
1026
1027 // advance target buffer
1028 77 dest += list->collection.elem_size;
1029
1030 // free the node and advance
1031 77 void *next = CX_LL_PTR(n, ll->loc_next);
1032 77 cxFree(list->collection.allocator, n);
1033 77 n = next;
1034 }
1035 }
1036
1037 96 return removed;
1038 }
1039
1040 21 static void cx_ll_clear(struct cx_list_s *list) {
1041
1/2
✗ Branch 0 (2→3) not taken.
✓ Branch 1 (2→4) taken 21 times.
 21 if (list->collection.size == 0) return;
1042
1043 21 cx_linked_list *ll = (cx_linked_list *) list;
1044 21 char *node = ll->begin;
1045
2/2
✓ Branch 0 (17→5) taken 561 times.
✓ Branch 1 (17→18) taken 21 times.
 582 while (node != NULL) {
1046
8/8
✓ Branch 0 (5→6) taken 112 times.
✓ Branch 1 (5→10) taken 449 times.
✓ Branch 2 (6→7) taken 56 times.
✓ Branch 3 (6→8) taken 56 times.
✓ Branch 4 (10→11) taken 425 times.
✓ Branch 5 (10→15) taken 136 times.
✓ Branch 6 (11→12) taken 211 times.
✓ Branch 7 (11→13) taken 214 times.
 561 cx_invoke_destructor(list, node + ll->loc_data);
1047 561 void *next = CX_LL_PTR(node, ll->loc_next);
1048 561 cxFree(list->collection.allocator, node);
1049 561 node = next;
1050 }
1051 21 ll->begin = ll->end = NULL;
1052 21 list->collection.size = 0;
1053 }
1054
1055 44 static int cx_ll_swap(
1056 struct cx_list_s *list,
1057 size_t i,
1058 size_t j
1059 ) {
1060
4/4
✓ Branch 0 (2→3) taken 36 times.
✓ Branch 1 (2→4) taken 8 times.
✓ Branch 2 (3→4) taken 4 times.
✓ Branch 3 (3→5) taken 32 times.
 44 if (i >= list->collection.size || j >= list->collection.size) return 1;
1061
2/2
✓ Branch 0 (5→6) taken 4 times.
✓ Branch 1 (5→7) taken 28 times.
 32 if (i == j) return 0;
1062
1063 // perform an optimized search that finds both elements in one run
1064 28 cx_linked_list *ll = (cx_linked_list *) list;
1065 28 size_t mid = list->collection.size / 2;
1066 size_t left, right;
1067
2/2
✓ Branch 0 (7→8) taken 20 times.
✓ Branch 1 (7→9) taken 8 times.
 28 if (i < j) {
1068 20 left = i;
1069 20 right = j;
1070 } else {
1071 8 left = j;
1072 8 right = i;
1073 }
1074 28 void *nleft = NULL, *nright = NULL;
1075
4/4
✓ Branch 0 (10→11) taken 20 times.
✓ Branch 1 (10→17) taken 8 times.
✓ Branch 2 (11→12) taken 4 times.
✓ Branch 3 (11→17) taken 16 times.
 28 if (left < mid && right < mid) {
1076 // case 1: both items left from mid
1077 4 nleft = cx_ll_node_at(ll, left);
1078 assert(nleft != NULL);
1079 4 nright = nleft;
1080
2/2
✓ Branch 0 (15→14) taken 12 times.
✓ Branch 1 (15→16) taken 4 times.
 16 for (size_t c = left; c < right; c++) {
1081 12 nright = CX_LL_PTR(nright, ll->loc_next);
1082 }
1083
3/4
✓ Branch 0 (17→18) taken 8 times.
✓ Branch 1 (17→24) taken 16 times.
✓ Branch 2 (18→19) taken 8 times.
✗ Branch 3 (18→24) not taken.
 24 } else if (left >= mid && right >= mid) {
1084 // case 2: both items right from mid
1085 8 nright = cx_ll_node_at(ll, right);
1086 assert(nright != NULL);
1087 8 nleft = nright;
1088
2/2
✓ Branch 0 (22→21) taken 12 times.
✓ Branch 1 (22→23) taken 8 times.
 20 for (size_t c = right; c > left; c--) {
1089 12 nleft = CX_LL_PTR(nleft, ll->loc_prev);
1090 }
1091 } else {
1092 // case 3: one item left, one item right
1093
1094 // chose the closest to begin / end
1095 size_t closest;
1096 size_t other;
1097 16 size_t diff2boundary = list->collection.size - right - 1;
1098
2/2
✓ Branch 0 (24→25) taken 8 times.
✓ Branch 1 (24→26) taken 8 times.
 16 if (left <= diff2boundary) {
1099 8 closest = left;
1100 8 other = right;
1101 8 nleft = cx_ll_node_at(ll, left);
1102 } else {
1103 8 closest = right;
1104 8 other = left;
1105 8 diff2boundary = left;
1106 8 nright = cx_ll_node_at(ll, right);
1107 }
1108
1109 // is other element closer to us or closer to boundary?
1110
2/2
✓ Branch 0 (27→28) taken 8 times.
✓ Branch 1 (27→35) taken 8 times.
 16 if (right - left <= diff2boundary) {
1111 // search other element starting from already found element
1112
2/2
✓ Branch 0 (28→29) taken 4 times.
✓ Branch 1 (28→32) taken 4 times.
 8 if (closest == left) {
1113 4 nright = nleft;
1114
2/2
✓ Branch 0 (31→30) taken 12 times.
✓ Branch 1 (31→38) taken 4 times.
 16 for (size_t c = left; c < right; c++) {
1115 12 nright = CX_LL_PTR(nright, ll->loc_next);
1116 }
1117 } else {
1118 4 nleft = nright;
1119
2/2
✓ Branch 0 (34→33) taken 20 times.
✓ Branch 1 (34→38) taken 4 times.
 24 for (size_t c = right; c > left; c--) {
1120 20 nleft = CX_LL_PTR(nleft, ll->loc_prev);
1121 }
1122 }
1123 } else {
1124 // search other element starting at the boundary
1125
2/2
✓ Branch 0 (35→36) taken 4 times.
✓ Branch 1 (35→37) taken 4 times.
 8 if (closest == left) {
1126 4 nright = cx_ll_node_at(ll, other);
1127 } else {
1128 4 nleft = cx_ll_node_at(ll, other);
1129 }
1130 }
1131 }
1132
1133 28 void *prev = CX_LL_PTR(nleft, ll->loc_prev);
1134 28 void *next = CX_LL_PTR(nright, ll->loc_next);
1135 28 void *midstart = CX_LL_PTR(nleft, ll->loc_next);
1136 28 void *midend = CX_LL_PTR(nright, ll->loc_prev);
1137
1138
2/2
✓ Branch 0 (38→39) taken 4 times.
✓ Branch 1 (38→40) taken 24 times.
 28 if (prev == NULL) {
1139 4 ll->begin = nright;
1140 } else {
1141 24 CX_LL_PTR(prev, ll->loc_next) = nright;
1142 }
1143 28 CX_LL_PTR(nright, ll->loc_prev) = prev;
1144
2/2
✓ Branch 0 (41→42) taken 4 times.
✓ Branch 1 (41→43) taken 24 times.
 28 if (midstart == nright) {
1145 // special case: both nodes are adjacent
1146 4 CX_LL_PTR(nright, ll->loc_next) = nleft;
1147 4 CX_LL_PTR(nleft, ll->loc_prev) = nright;
1148 } else {
1149 // likely case: a chain is between the two nodes
1150 24 CX_LL_PTR(nright, ll->loc_next) = midstart;
1151 24 CX_LL_PTR(midstart, ll->loc_prev) = nright;
1152 24 CX_LL_PTR(midend, ll->loc_next) = nleft;
1153 24 CX_LL_PTR(nleft, ll->loc_prev) = midend;
1154 }
1155 28 CX_LL_PTR(nleft, ll->loc_next) = next;
1156
2/2
✓ Branch 0 (44→45) taken 4 times.
✓ Branch 1 (44→46) taken 24 times.
 28 if (next == NULL) {
1157 4 ll->end = nleft;
1158 } else {
1159 24 CX_LL_PTR(next, ll->loc_prev) = nleft;
1160 }
1161
1162 28 return 0;
1163 }
1164
1165 16130 static void *cx_ll_at(
1166 const struct cx_list_s *list,
1167 size_t index
1168 ) {
1169 16130 cx_linked_list *ll = (cx_linked_list *) list;
1170 16130 char *node = cx_ll_node_at(ll, index);
1171
2/2
✓ Branch 0 (3→4) taken 16121 times.
✓ Branch 1 (3→5) taken 9 times.
 16130 return node == NULL ? NULL : node + ll->loc_data;
1172 }
1173
1174 408 static size_t cx_ll_find_remove(
1175 struct cx_list_s *list,
1176 const void *elem,
1177 bool remove
1178 ) {
1179
2/2
✓ Branch 0 (2→3) taken 2 times.
✓ Branch 1 (2→4) taken 406 times.
 408 if (list->collection.size == 0) return 0;
1180
1181 size_t index;
1182 406 cx_linked_list *ll = (cx_linked_list *) list;
1183 406 char *node = cx_linked_list_find_c(
1184 406 ll->begin,
1185 406 ll->loc_next, ll->loc_data,
1186 elem, &index,
1187 cx_list_compare_wrapper,
1188 list);
1189
2/2
✓ Branch 0 (5→6) taken 254 times.
✓ Branch 1 (5→7) taken 152 times.
 406 if (node == NULL) {
1190 254 return list->collection.size;
1191 }
1192
2/2
✓ Branch 0 (7→8) taken 6 times.
✓ Branch 1 (7→20) taken 146 times.
 152 if (remove) {
1193
2/8
✗ Branch 0 (8→9) not taken.
✓ Branch 1 (8→13) taken 6 times.
✗ Branch 2 (9→10) not taken.
✗ Branch 3 (9→11) not taken.
✗ Branch 4 (13→14) not taken.
✓ Branch 5 (13→18) taken 6 times.
✗ Branch 6 (14→15) not taken.
✗ Branch 7 (14→16) not taken.
 6 cx_invoke_destructor(list, node + ll->loc_data);
1194 6 cx_linked_list_remove(&ll->begin, &ll->end,
1195 6 ll->loc_prev, ll->loc_next, node);
1196 6 list->collection.size--;
1197 6 cxFree(list->collection.allocator, node);
1198 }
1199 152 return index;
1200 }
1201
1202 27 static void cx_ll_sort(struct cx_list_s *list) {
1203 27 cx_linked_list *ll = (cx_linked_list *) list;
1204 27 cx_linked_list_sort_c(&ll->begin, &ll->end,
1205 27 ll->loc_prev, ll->loc_next, ll->loc_data,
1206 cx_list_compare_wrapper, list);
1207 27 }
1208
1209 4 static void cx_ll_reverse(struct cx_list_s *list) {
1210 4 cx_linked_list *ll = (cx_linked_list *) list;
1211 4 cx_linked_list_reverse(&ll->begin, &ll->end, ll->loc_prev, ll->loc_next);
1212 4 }
1213
1214 56 static int cx_ll_compare(
1215 const struct cx_list_s *list,
1216 const struct cx_list_s *other
1217 ) {
1218 56 cx_linked_list *left = (cx_linked_list *) list;
1219 56 cx_linked_list *right = (cx_linked_list *) other;
1220 assert(left->loc_next == right->loc_next);
1221 assert(left->loc_data == right->loc_data);
1222 112 return cx_linked_list_compare_c(left->begin, right->begin,
1223 56 left->loc_next, left->loc_data,
1224 cx_list_compare_wrapper, (void*)list);
1225 }
1226
1227 2402 static bool cx_ll_iter_valid(const void *it) {
1228 2402 const struct cx_iterator_s *iter = it;
1229 2402 return iter->elem_handle != NULL;
1230 }
1231
1232 9934 static void cx_ll_iter_next(void *it) {
1233 9934 struct cx_iterator_s *iter = it;
1234 9934 cx_linked_list *ll = iter->src_handle;
1235
2/2
✓ Branch 0 (2→3) taken 61 times.
✓ Branch 1 (2→15) taken 9873 times.
 9934 if (iter->base.remove) {
1236 61 iter->base.remove = false;
1237 61 struct cx_list_s *list = iter->src_handle;
1238 61 char *node = iter->elem_handle;
1239 61 iter->elem_handle = CX_LL_PTR(node, ll->loc_next);
1240
8/8
✓ Branch 0 (3→4) taken 2 times.
✓ Branch 1 (3→8) taken 59 times.
✓ Branch 2 (4→5) taken 1 times.
✓ Branch 3 (4→6) taken 1 times.
✓ Branch 4 (8→9) taken 33 times.
✓ Branch 5 (8→13) taken 28 times.
✓ Branch 6 (9→10) taken 16 times.
✓ Branch 7 (9→11) taken 17 times.
 61 cx_invoke_destructor(list, node + ll->loc_data);
1241 61 cx_linked_list_remove(&ll->begin, &ll->end,
1242 61 ll->loc_prev, ll->loc_next, node);
1243 61 list->collection.size--;
1244 61 iter->elem_count--;
1245 61 cxFree(list->collection.allocator, node);
1246 } else {
1247 9873 iter->index++;
1248 9873 void *node = iter->elem_handle;
1249 9873 iter->elem_handle = CX_LL_PTR(node, ll->loc_next);
1250 }
1251 9934 }
1252
1253 412 static void cx_ll_iter_prev(void *it) {
1254 412 struct cx_iterator_s *iter = it;
1255 412 cx_linked_list *ll = iter->src_handle;
1256
2/2
✓ Branch 0 (2→3) taken 56 times.
✓ Branch 1 (2→15) taken 356 times.
 412 if (iter->base.remove) {
1257 56 iter->base.remove = false;
1258 56 struct cx_list_s *list = iter->src_handle;
1259 56 char *node = iter->elem_handle;
1260 56 iter->elem_handle = CX_LL_PTR(node, ll->loc_prev);
1261 56 iter->index--;
1262
8/8
✓ Branch 0 (3→4) taken 2 times.
✓ Branch 1 (3→8) taken 54 times.
✓ Branch 2 (4→5) taken 1 times.
✓ Branch 3 (4→6) taken 1 times.
✓ Branch 4 (8→9) taken 30 times.
✓ Branch 5 (8→13) taken 26 times.
✓ Branch 6 (9→10) taken 15 times.
✓ Branch 7 (9→11) taken 15 times.
 56 cx_invoke_destructor(list, node + ll->loc_data);
1263 56 cx_linked_list_remove(&ll->begin, &ll->end,
1264 56 ll->loc_prev, ll->loc_next, node);
1265 56 list->collection.size--;
1266 56 iter->elem_count--;
1267 56 cxFree(list->collection.allocator, node);
1268 } else {
1269 356 iter->index--;
1270 356 char *node = iter->elem_handle;
1271 356 iter->elem_handle = CX_LL_PTR(node, ll->loc_prev);
1272 }
1273 412 }
1274
1275 10948 static void *cx_ll_iter_current(const void *it) {
1276 10948 const struct cx_iterator_s *iter = it;
1277 10948 const cx_linked_list *ll = iter->src_handle;
1278 10948 char *node = iter->elem_handle;
1279 10948 return node + ll->loc_data;
1280 }
1281
1282 443 static CxIterator cx_ll_iterator(
1283 const struct cx_list_s *list,
1284 size_t index,
1285 bool backwards
1286 ) {
1287 CxIterator iter;
1288 443 iter.index = index;
1289 443 iter.src_handle = (void*)list;
1290 443 iter.elem_handle = cx_ll_node_at((const cx_linked_list *) list, index);
1291 443 iter.elem_size = list->collection.elem_size;
1292 443 iter.elem_count = list->collection.size;
1293 443 iter.base.valid = cx_ll_iter_valid;
1294 443 iter.base.current = cx_ll_iter_current;
1295
2/2
✓ Branch 0 (3→4) taken 22 times.
✓ Branch 1 (3→5) taken 421 times.
 443 iter.base.next = backwards ? cx_ll_iter_prev : cx_ll_iter_next;
1296 443 iter.base.allow_remove = true;
1297 443 iter.base.remove = false;
1298 443 return iter;
1299 }
1300
1301 20 static int cx_ll_insert_iter(
1302 CxIterator *iter,
1303 const void *elem,
1304 int prepend
1305 ) {
1306 20 struct cx_list_s *list = iter->src_handle;
1307 20 cx_linked_list *ll = iter->src_handle;
1308 20 void *node = iter->elem_handle;
1309
2/2
✓ Branch 0 (2→3) taken 12 times.
✓ Branch 1 (2→8) taken 8 times.
 20 if (node != NULL) {
1310 assert(prepend >= 0 && prepend <= 1);
1311 12 void *choice[2] = {node, CX_LL_PTR(node, ll->loc_prev)};
1312 12 int result = cx_ll_insert_at(list, choice[prepend], elem);
1313
1/2
✓ Branch 0 (4→5) taken 12 times.
✗ Branch 1 (4→7) not taken.
 12 if (result == 0) {
1314 12 iter->elem_count++;
1315
2/2
✓ Branch 0 (5→6) taken 8 times.
✓ Branch 1 (5→7) taken 4 times.
 12 if (prepend) {
1316 8 iter->index++;
1317 }
1318 }
1319 12 return result;
1320 } else {
1321
1/2
✗ Branch 0 (9→10) not taken.
✓ Branch 1 (9→11) taken 8 times.
 8 if (cx_ll_insert_element(list, list->collection.size, elem) == NULL) {
1322 − return 1; // LCOV_EXCL_LINE
1323 }
1324 8 iter->elem_count++;
1325 8 iter->index = list->collection.size;
1326 8 return 0;
1327 }
1328 }
1329
1330 476 static void cx_ll_destructor(CxList *list) {
1331 476 cx_linked_list *ll = (cx_linked_list *) list;
1332
1333 476 char *node = ll->begin;
1334
2/2
✓ Branch 0 (15→3) taken 21093 times.
✓ Branch 1 (15→16) taken 476 times.
 21569 while (node) {
1335
8/8
✓ Branch 0 (3→4) taken 25 times.
✓ Branch 1 (3→8) taken 21068 times.
✓ Branch 2 (4→5) taken 13 times.
✓ Branch 3 (4→6) taken 12 times.
✓ Branch 4 (8→9) taken 9578 times.
✓ Branch 5 (8→13) taken 11515 times.
✓ Branch 6 (9→10) taken 5473 times.
✓ Branch 7 (9→11) taken 4105 times.
 21093 cx_invoke_destructor(list, node + ll->loc_data);
1336 21093 void *next = CX_LL_PTR(node, ll->loc_next);
1337 21093 cxFree(list->collection.allocator, node);
1338 21093 node = next;
1339 }
1340
1341 476 cxFree(list->collection.allocator, list);
1342 476 }
1343
1344 static cx_list_class cx_linked_list_class = {
1345 cx_ll_destructor,
1346 cx_ll_insert_element,
1347 cx_ll_insert_array,
1348 cx_ll_insert_sorted,
1349 cx_ll_insert_unique,
1350 cx_ll_insert_iter,
1351 cx_ll_remove,
1352 cx_ll_clear,
1353 cx_ll_swap,
1354 cx_ll_at,
1355 cx_ll_find_remove,
1356 cx_ll_sort,
1357 cx_ll_compare,
1358 cx_ll_reverse,
1359 NULL, // no overallocation supported
1360 cx_ll_iterator,
1361 };
1362
1363 476 CxList *cxLinkedListCreate(
1364 const CxAllocator *allocator,
1365 size_t elem_size
1366 ) {
1367
2/2
✓ Branch 0 (2→3) taken 3 times.
✓ Branch 1 (2→4) taken 473 times.
 476 if (allocator == NULL) {
1368 3 allocator = cxDefaultAllocator;
1369 }
1370
1371 476 cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list));
1372
1/2
✗ Branch 0 (5→6) not taken.
✓ Branch 1 (5→7) taken 476 times.
 476 if (list == NULL) return NULL;
1373 476 list->loc_prev = 0;
1374 476 list->loc_next = sizeof(void*);
1375 476 list->loc_data = sizeof(void*)*2;
1376 476 list->loc_extra = -1;
1377 476 list->extra_data_len = 0;
1378 476 cx_list_init((CxList*)list, &cx_linked_list_class,
1379 allocator, elem_size);
1380
1381 476 return (CxList *) list;
1382 }
1383
1384 278 void cx_linked_list_extra_data(cx_linked_list *list, size_t len) {
1385 278 list->extra_data_len = len;
1386
1387 278 off_t loc_extra = list->loc_data + (off_t) list->base.collection.elem_size;
1388 278 size_t alignment = alignof(void*);
1389 278 size_t padding = alignment - ((size_t)loc_extra % alignment);
1390 278 list->loc_extra = loc_extra + (off_t) padding;
1391 278 }
1392