GCC Code Coverage Report

Directory: ./
File: array_list.c
Date: 2025-11-30 14:18:36
Exec Total Coverage
Lines: 482 482 100.0%
Functions: 35 35 100.0%
Branches: 266 290 91.7%
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/array_list.h"
30 #include "cx/compare.h"
31 #include <assert.h>
32 #include <string.h>
33 #include <errno.h>
34
35 // Default array reallocator
36
37 12 static void *cx_array_default_realloc(
38 void *array,
39 cx_attr_unused size_t old_capacity,
40 size_t new_capacity,
41 size_t elem_size,
42 cx_attr_unused CxArrayReallocator *alloc
43 ) {
44 size_t n;
45 // LCOV_EXCL_START
46 − if (cx_szmul(new_capacity, elem_size, &n)) {
47 − errno = EOVERFLOW;
48 − return NULL;
49 } // LCOV_EXCL_STOP
50 12 return cxReallocDefault(array, n);
51 }
52
53 CxArrayReallocator cx_array_default_reallocator_impl = {
54 cx_array_default_realloc, NULL, NULL
55 };
56
57 CxArrayReallocator *cx_array_default_reallocator = &cx_array_default_reallocator_impl;
58
59 // Stack-aware array reallocator
60
61 300 static void *cx_array_advanced_realloc(
62 void *array,
63 size_t old_capacity,
64 size_t new_capacity,
65 size_t elem_size,
66 cx_attr_unused CxArrayReallocator *alloc
67 ) {
68 // check for overflow
69 size_t n;
70 // LCOV_EXCL_START
71 − if (cx_szmul(new_capacity, elem_size, &n)) {
72 − errno = EOVERFLOW;
73 − return NULL;
74 } // LCOV_EXCL_STOP
75
76 // retrieve the pointer to the actual allocator
77 300 const CxAllocator *al = alloc->allocator;
78
79 // check if the array is still located on the stack
80 void *newmem;
81
2/2
✓ Branch 0 (5→6) taken 2 times.
✓ Branch 1 (5→10) taken 298 times.
 300 if (array == alloc->stack_ptr) {
82 2 newmem = cxMalloc(al, n);
83
2/4
✓ Branch 0 (7→8) taken 2 times.
✗ Branch 1 (7→11) not taken.
✓ Branch 2 (8→9) taken 2 times.
✗ Branch 3 (8→11) not taken.
 2 if (newmem != NULL && array != NULL) {
84 2 memcpy(newmem, array, old_capacity*elem_size);
85 }
86 } else {
87 298 newmem = cxRealloc(al, array, n);
88 }
89 300 return newmem;
90 }
91
92 1003 struct cx_array_reallocator_s cx_array_reallocator(
93 const struct cx_allocator_s *allocator,
94 const void *stack_ptr
95 ) {
96
2/2
✓ Branch 0 (2→3) taken 323 times.
✓ Branch 1 (2→4) taken 680 times.
 1003 if (allocator == NULL) {
97 323 allocator = cxDefaultAllocator;
98 }
99 1003 return (struct cx_array_reallocator_s) {
100 cx_array_advanced_realloc,
101 allocator, stack_ptr,
102 };
103 }
104
105 // LOW LEVEL ARRAY LIST FUNCTIONS
106
107 /**
108 * Intelligently calculates a new capacity, reserving some more
109 * elements than required to prevent too many allocations.
110 *
111 * @param current_capacity the current capacity of the array
112 * @param needed_capacity the required capacity of the array
113 * @return the new capacity
114 */
115 799 static size_t cx_array_grow_capacity(
116 size_t current_capacity,
117 size_t needed_capacity
118 ) {
119
2/2
✓ Branch 0 (2→3) taken 531 times.
✓ Branch 1 (2→4) taken 268 times.
 799 if (current_capacity >= needed_capacity) {
120 531 return current_capacity;
121 }
122 268 size_t cap = needed_capacity;
123 size_t alignment;
124
2/2
✓ Branch 0 (4→5) taken 224 times.
✓ Branch 1 (4→6) taken 44 times.
 268 if (cap < 128) alignment = 16;
125
2/2
✓ Branch 0 (6→7) taken 41 times.
✓ Branch 1 (6→8) taken 3 times.
 44 else if (cap < 1024) alignment = 64;
126
2/2
✓ Branch 0 (8→9) taken 2 times.
✓ Branch 1 (8→10) taken 1 times.
 3 else if (cap < 8192) alignment = 512;
127 1 else alignment = 1024;
128 268 return cap - (cap % alignment) + alignment;
129 }
130
131 712 int cx_array_reserve(
132 void **array,
133 void *size,
134 void *capacity,
135 unsigned width,
136 size_t elem_size,
137 size_t elem_count,
138 CxArrayReallocator *reallocator
139 ) {
140 // assert pointers
141 assert(array != NULL);
142 assert(size != NULL);
143 assert(capacity != NULL);
144
145 // default reallocator
146
2/2
✓ Branch 0 (2→3) taken 7 times.
✓ Branch 1 (2→4) taken 705 times.
 712 if (reallocator == NULL) {
147 7 reallocator = cx_array_default_reallocator;
148 }
149
150 // determine size and capacity
151 size_t oldcap;
152 size_t oldsize;
153 size_t max_size;
154
4/4
✓ Branch 0 (4→5) taken 711 times.
✓ Branch 1 (4→6) taken 1 times.
✓ Branch 2 (5→6) taken 420 times.
✓ Branch 3 (5→7) taken 291 times.
 712 if (width == 0 || width == sizeof(size_t)) {
155 421 oldcap = *(size_t*) capacity;
156 421 oldsize = *(size_t*) size;
157 421 max_size = SIZE_MAX;
158
2/2
✓ Branch 0 (7→8) taken 4 times.
✓ Branch 1 (7→9) taken 287 times.
 291 } else if (width == sizeof(uint16_t)) {
159 4 oldcap = *(uint16_t*) capacity;
160 4 oldsize = *(uint16_t*) size;
161 4 max_size = UINT16_MAX;
162
2/2
✓ Branch 0 (9→10) taken 3 times.
✓ Branch 1 (9→11) taken 284 times.
 287 } else if (width == sizeof(uint8_t)) {
163 3 oldcap = *(uint8_t*) capacity;
164 3 oldsize = *(uint8_t*) size;
165 3 max_size = UINT8_MAX;
166 }
167 #if CX_WORDSIZE == 64
168
2/2
✓ Branch 0 (11→12) taken 283 times.
✓ Branch 1 (11→13) taken 1 times.
 284 else if (width == sizeof(uint32_t)) {
169 283 oldcap = *(uint32_t*) capacity;
170 283 oldsize = *(uint32_t*) size;
171 283 max_size = UINT32_MAX;
172 }
173 #endif
174 else {
175 1 errno = EINVAL;
176 1 return 1;
177 }
178
179 // assert that the array is allocated when it has capacity
180 assert(*array != NULL || oldcap == 0);
181
182 // check for overflow
183
2/2
✓ Branch 0 (14→15) taken 2 times.
✓ Branch 1 (14→16) taken 709 times.
 711 if (elem_count > max_size - oldsize) {
184 2 errno = EOVERFLOW;
185 2 return 1;
186 }
187
188 // determine new capacity
189 709 size_t newcap = oldsize + elem_count;
190
191 // reallocate if possible
192
2/2
✓ Branch 0 (16→17) taken 292 times.
✓ Branch 1 (16→29) taken 417 times.
 709 if (newcap > oldcap) {
193 292 void *newmem = reallocator->realloc(
194 *array, oldcap, newcap, elem_size, reallocator
195 );
196
1/2
✗ Branch 0 (18→19) not taken.
✓ Branch 1 (18→20) taken 292 times.
 292 if (newmem == NULL) {
197 − return 1; // LCOV_EXCL_LINE
198 }
199
200 // store new pointer
201 292 *array = newmem;
202
203 // store new capacity
204
4/4
✓ Branch 0 (20→21) taken 291 times.
✓ Branch 1 (20→22) taken 1 times.
✓ Branch 2 (21→22) taken 285 times.
✓ Branch 3 (21→23) taken 6 times.
 292 if (width == 0 || width == sizeof(size_t)) {
205 286 *(size_t*) capacity = newcap;
206
2/2
✓ Branch 0 (23→24) taken 2 times.
✓ Branch 1 (23→25) taken 4 times.
 6 } else if (width == sizeof(uint16_t)) {
207 2 *(uint16_t*) capacity = (uint16_t) newcap;
208
2/2
✓ Branch 0 (25→26) taken 1 times.
✓ Branch 1 (25→27) taken 3 times.
 4 } else if (width == sizeof(uint8_t)) {
209 1 *(uint8_t*) capacity = (uint8_t) newcap;
210 }
211 #if CX_WORDSIZE == 64
212
1/2
✓ Branch 0 (27→28) taken 3 times.
✗ Branch 1 (27→29) not taken.
 3 else if (width == sizeof(uint32_t)) {
213 3 *(uint32_t*) capacity = (uint32_t) newcap;
214 }
215 #endif
216 }
217
218 709 return 0;
219 }
220
221 484 int cx_array_copy(
222 void **target,
223 void *size,
224 void *capacity,
225 unsigned width,
226 size_t index,
227 const void *src,
228 size_t elem_size,
229 size_t elem_count,
230 CxArrayReallocator *reallocator
231 ) {
232 // assert pointers
233 assert(target != NULL);
234 assert(size != NULL);
235 assert(capacity != NULL);
236 assert(src != NULL);
237
238 // default reallocator
239
2/2
✓ Branch 0 (2→3) taken 4 times.
✓ Branch 1 (2→4) taken 480 times.
 484 if (reallocator == NULL) {
240 4 reallocator = cx_array_default_reallocator;
241 }
242
243 // determine size and capacity
244 size_t oldcap;
245 size_t oldsize;
246 size_t max_size;
247
4/4
✓ Branch 0 (4→5) taken 398 times.
✓ Branch 1 (4→6) taken 86 times.
✓ Branch 2 (5→6) taken 350 times.
✓ Branch 3 (5→7) taken 48 times.
 484 if (width == 0 || width == sizeof(size_t)) {
248 436 oldcap = *(size_t*) capacity;
249 436 oldsize = *(size_t*) size;
250 436 max_size = SIZE_MAX;
251
2/2
✓ Branch 0 (7→8) taken 3 times.
✓ Branch 1 (7→9) taken 45 times.
 48 } else if (width == sizeof(uint16_t)) {
252 3 oldcap = *(uint16_t*) capacity;
253 3 oldsize = *(uint16_t*) size;
254 3 max_size = UINT16_MAX;
255
2/2
✓ Branch 0 (9→10) taken 4 times.
✓ Branch 1 (9→11) taken 41 times.
 45 } else if (width == sizeof(uint8_t)) {
256 4 oldcap = *(uint8_t*) capacity;
257 4 oldsize = *(uint8_t*) size;
258 4 max_size = UINT8_MAX;
259 }
260 #if CX_WORDSIZE == 64
261
2/2
✓ Branch 0 (11→12) taken 40 times.
✓ Branch 1 (11→13) taken 1 times.
 41 else if (width == sizeof(uint32_t)) {
262 40 oldcap = *(uint32_t*) capacity;
263 40 oldsize = *(uint32_t*) size;
264 40 max_size = UINT32_MAX;
265 }
266 #endif
267 else {
268 1 errno = EINVAL;
269 1 return 1;
270 }
271
272 // assert that the array is allocated when it has capacity
273 assert(*target != NULL || oldcap == 0);
274
275 // check for overflow
276
4/4
✓ Branch 0 (14→15) taken 482 times.
✓ Branch 1 (14→16) taken 1 times.
✓ Branch 2 (15→16) taken 1 times.
✓ Branch 3 (15→17) taken 481 times.
 483 if (index > max_size || elem_count > max_size - index) {
277 2 errno = EOVERFLOW;
278 2 return 1;
279 }
280
281 // check if resize is required
282 481 const size_t minsize = index + elem_count;
283 481 const size_t newsize = oldsize < minsize ? minsize : oldsize;
284
285 // reallocate if necessary
286 481 const size_t newcap = cx_array_grow_capacity(oldcap, newsize);
287
2/2
✓ Branch 0 (18→19) taken 5 times.
✓ Branch 1 (18→29) taken 476 times.
 481 if (newcap > oldcap) {
288 // check if we need to repair the src pointer
289 5 uintptr_t targetaddr = (uintptr_t) *target;
290 5 uintptr_t srcaddr = (uintptr_t) src;
291 5 bool repairsrc = targetaddr <= srcaddr
292
4/4
✓ Branch 0 (19→20) taken 3 times.
✓ Branch 1 (19→22) taken 2 times.
✓ Branch 2 (20→21) taken 1 times.
✓ Branch 3 (20→22) taken 2 times.
 5 && srcaddr < targetaddr + oldcap * elem_size;
293
294 // perform reallocation
295 5 void *newmem = reallocator->realloc(
296 *target, oldcap, newcap, elem_size, reallocator
297 );
298
1/2
✗ Branch 0 (24→25) not taken.
✓ Branch 1 (24→26) taken 5 times.
 5 if (newmem == NULL) {
299 − return 1; // LCOV_EXCL_LINE
300 }
301
302 // repair src pointer, if necessary
303
2/2
✓ Branch 0 (26→27) taken 1 times.
✓ Branch 1 (26→28) taken 4 times.
 5 if (repairsrc) {
304 1 src = ((char *) newmem) + (srcaddr - targetaddr);
305 }
306
307 // store new pointer
308 5 *target = newmem;
309 }
310
311 // determine target pointer
312 481 char *start = *target;
313 481 start += index * elem_size;
314
315 // copy elements and set new size
316 // note: no overflow check here, b/c we cannot get here w/o allocation
317 481 memmove(start, src, elem_count * elem_size);
318
319 // if any of size or capacity changed, store them back
320
3/4
✓ Branch 0 (29→30) taken 86 times.
✓ Branch 1 (29→31) taken 395 times.
✗ Branch 2 (30→31) not taken.
✓ Branch 3 (30→40) taken 86 times.
 481 if (newsize != oldsize || newcap != oldcap) {
321
3/4
✓ Branch 0 (31→32) taken 395 times.
✗ Branch 1 (31→33) not taken.
✓ Branch 2 (32→33) taken 350 times.
✓ Branch 3 (32→34) taken 45 times.
 395 if (width == 0 || width == sizeof(size_t)) {
322 350 *(size_t*) capacity = newcap;
323 350 *(size_t*) size = newsize;
324
2/2
✓ Branch 0 (34→35) taken 2 times.
✓ Branch 1 (34→36) taken 43 times.
 45 } else if (width == sizeof(uint16_t)) {
325 2 *(uint16_t*) capacity = (uint16_t) newcap;
326 2 *(uint16_t*) size = (uint16_t) newsize;
327
2/2
✓ Branch 0 (36→37) taken 3 times.
✓ Branch 1 (36→38) taken 40 times.
 43 } else if (width == sizeof(uint8_t)) {
328 3 *(uint8_t*) capacity = (uint8_t) newcap;
329 3 *(uint8_t*) size = (uint8_t) newsize;
330 }
331 #if CX_WORDSIZE == 64
332
1/2
✓ Branch 0 (38→39) taken 40 times.
✗ Branch 1 (38→40) not taken.
 40 else if (width == sizeof(uint32_t)) {
333 40 *(uint32_t*) capacity = (uint32_t) newcap;
334 40 *(uint32_t*) size = (uint32_t) newsize;
335 }
336 #endif
337 }
338
339 // return successfully
340 481 return 0;
341 }
342
343 70 static int cx_array_insert_sorted_impl(
344 void **target,
345 size_t *size,
346 size_t *capacity,
347 cx_compare_func cmp_func,
348 const void *sorted_data,
349 size_t elem_size,
350 size_t elem_count,
351 CxArrayReallocator *reallocator,
352 bool allow_duplicates
353 ) {
354 // assert pointers
355 assert(target != NULL);
356 assert(size != NULL);
357 assert(capacity != NULL);
358 assert(cmp_func != NULL);
359 assert(sorted_data != NULL);
360
361 // default reallocator
362
2/2
✓ Branch 0 (2→3) taken 23 times.
✓ Branch 1 (2→4) taken 47 times.
 70 if (reallocator == NULL) {
363 23 reallocator = cx_array_default_reallocator;
364 }
365
366 // corner case
367
1/2
✗ Branch 0 (4→5) not taken.
✓ Branch 1 (4→6) taken 70 times.
 70 if (elem_count == 0) return 0;
368
369 // overflow check
370 // LCOV_EXCL_START
371 − if (elem_count > SIZE_MAX - *size) {
372 − errno = EOVERFLOW;
373 − return 1;
374 }
375 // LCOV_EXCL_STOP
376
377 // store some counts
378 70 const size_t old_size = *size;
379 70 const size_t old_capacity = *capacity;
380 // the necessary capacity is the worst case assumption, including duplicates
381 70 const size_t needed_capacity = cx_array_grow_capacity(old_capacity, old_size + elem_count);
382
383 // if we need more than we have, try a reallocation
384
2/2
✓ Branch 0 (9→10) taken 15 times.
✓ Branch 1 (9→14) taken 55 times.
 70 if (needed_capacity > old_capacity) {
385 15 void *new_mem = reallocator->realloc(
386 *target, old_capacity, needed_capacity, elem_size, reallocator
387 );
388
1/2
✗ Branch 0 (11→12) not taken.
✓ Branch 1 (11→13) taken 15 times.
 15 if (new_mem == NULL) {
389 // give it up right away, there is no contract
390 // that requires us to insert as much as we can
391 − return 1; // LCOV_EXCL_LINE
392 }
393 15 *target = new_mem;
394 15 *capacity = needed_capacity;
395 }
396
397 // now we have guaranteed that we can insert everything
398 70 size_t new_size = old_size + elem_count;
399 70 *size = new_size;
400
401 // declare the source and destination indices/pointers
402 70 size_t si = 0, di = 0;
403 70 const char *src = sorted_data;
404 70 char *dest = *target;
405
406 // find the first insertion point
407 70 di = cx_array_binary_search_sup(dest, old_size, elem_size, src, cmp_func);
408 70 dest += di * elem_size;
409
410 // move the remaining elements in the array completely to the right
411 // we will call it the "buffer" for parked elements
412 70 size_t buf_size = old_size - di;
413 70 size_t bi = new_size - buf_size;
414 70 char *bptr = ((char *) *target) + bi * elem_size;
415 70 memmove(bptr, dest, buf_size * elem_size);
416
417 // while there are both source and buffered elements left,
418 // copy them interleaving
419
3/4
✓ Branch 0 (41→42) taken 126 times.
✗ Branch 1 (41→43) not taken.
✓ Branch 2 (42→16) taken 99 times.
✓ Branch 3 (42→43) taken 27 times.
 126 while (si < elem_count && bi < new_size) {
420 // determine how many source elements can be inserted.
421 // the first element that shall not be inserted is the smallest element
422 // that is strictly larger than the first buffered element
423 // (located at the index of the infimum plus one).
424 // the infimum is guaranteed to exist:
425 // - if all src elements are larger,
426 // there is no buffer, and this loop is skipped
427 // - if any src element is smaller or equal, the infimum exists
428 // - when all src elements that are smaller are copied, the second part
429 // of this loop body will copy the remaining buffer (emptying it)
430 // Therefore, the buffer can never contain an element that is smaller
431 // than any element in the source and the infimum exists.
432 size_t copy_len, bytes_copied;
433 99 copy_len = cx_array_binary_search_inf(
434 src, elem_count - si, elem_size, bptr, cmp_func
435 );
436 99 copy_len++;
437
438 // copy the source elements
439
1/2
✓ Branch 0 (17→18) taken 99 times.
✗ Branch 1 (17→37) not taken.
 99 if (copy_len > 0) {
440
2/2
✓ Branch 0 (18→19) taken 46 times.
✓ Branch 1 (18→20) taken 53 times.
 99 if (allow_duplicates) {
441 // we can copy the entire chunk
442 46 bytes_copied = copy_len * elem_size;
443 46 memcpy(dest, src, bytes_copied);
444 46 dest += bytes_copied;
445 46 src += bytes_copied;
446 46 si += copy_len;
447 46 di += copy_len;
448 } else {
449 // first, check the end of the source chunk
450 // for being a duplicate of the bptr
451 53 const char *end_of_src = src + (copy_len - 1) * elem_size;
452 53 size_t skip_len = 0;
453
4/4
✓ Branch 0 (22→23) taken 60 times.
✓ Branch 1 (22→25) taken 13 times.
✓ Branch 2 (24→21) taken 20 times.
✓ Branch 3 (24→25) taken 40 times.
 73 while (copy_len > 0 && cmp_func(bptr, end_of_src) == 0) {
454 20 end_of_src -= elem_size;
455 20 skip_len++;
456 20 copy_len--;
457 }
458
2/2
✓ Branch 0 (25→26) taken 49 times.
✓ Branch 1 (25→27) taken 4 times.
 53 char *last = dest == *target ? NULL : dest - elem_size;
459 // then iterate through the source chunk
460 // and skip all duplicates with the last element in the array
461 53 size_t more_skipped = 0;
462
2/2
✓ Branch 0 (35→29) taken 73 times.
✓ Branch 1 (35→36) taken 53 times.
 126 for (unsigned j = 0; j < copy_len; j++) {
463
4/4
✓ Branch 0 (29→30) taken 69 times.
✓ Branch 1 (29→33) taken 4 times.
✓ Branch 2 (31→32) taken 13 times.
✓ Branch 3 (31→33) taken 56 times.
 73 if (last != NULL && cmp_func(last, src) == 0) {
464 // duplicate - skip
465 13 src += elem_size;
466 13 si++;
467 13 more_skipped++;
468 } else {
469 60 memcpy(dest, src, elem_size);
470 60 src += elem_size;
471 60 last = dest;
472 60 dest += elem_size;
473 60 si++;
474 60 di++;
475 }
476 }
477 // skip the previously identified elements as well
478 53 src += skip_len * elem_size;
479 53 si += skip_len;
480 53 skip_len += more_skipped;
481 // reduce the actual size by the number of skipped elements
482 53 *size -= skip_len;
483 }
484 }
485
486 // when all source elements are in place, we are done
487
2/2
✓ Branch 0 (37→38) taken 43 times.
✓ Branch 1 (37→39) taken 56 times.
 99 if (si >= elem_count) break;
488
489 // determine how many buffered elements need to be restored
490 56 copy_len = cx_array_binary_search_sup(
491 bptr,
492 new_size - bi,
493 elem_size,
494 src,
495 cmp_func
496 );
497
498 // restore the buffered elements
499 56 bytes_copied = copy_len * elem_size;
500 56 memmove(dest, bptr, bytes_copied);
501 56 dest += bytes_copied;
502 56 bptr += bytes_copied;
503 56 di += copy_len;
504 56 bi += copy_len;
505 }
506
507 // still source elements left?
508
2/2
✓ Branch 0 (43→44) taken 27 times.
✓ Branch 1 (43→59) taken 43 times.
 70 if (si < elem_count) {
509
2/2
✓ Branch 0 (44→45) taken 15 times.
✓ Branch 1 (44→46) taken 12 times.
 27 if (allow_duplicates) {
510 // duplicates allowed or nothing inserted yet: simply copy everything
511 15 memcpy(dest, src, elem_size * (elem_count - si));
512 } else {
513 // we must check the remaining source elements one by one
514 // to skip the duplicates.
515 // Note that no source element can equal the last element in the
516 // destination, because that would have created an insertion point
517 // and a buffer, s.t. the above loop already handled the duplicates
518
2/2
✓ Branch 0 (58→47) taken 18 times.
✓ Branch 1 (58→59) taken 12 times.
 30 while (si < elem_count) {
519 // find a chain of elements that can be copied
520 18 size_t copy_len = 1, skip_len = 0;
521 {
522 18 const char *left_src = src;
523
2/2
✓ Branch 0 (56→48) taken 28 times.
✓ Branch 1 (56→57) taken 11 times.
 39 while (si + copy_len < elem_count) {
524 28 const char *right_src = left_src + elem_size;
525 28 int d = cmp_func(left_src, right_src);
526
2/2
✓ Branch 0 (49→50) taken 20 times.
✓ Branch 1 (49→53) taken 8 times.
 28 if (d < 0) {
527
2/2
✓ Branch 0 (50→51) taken 6 times.
✓ Branch 1 (50→52) taken 14 times.
 20 if (skip_len > 0) {
528 // new larger element found;
529 // handle it in the next cycle
530 6 break;
531 }
532 14 left_src += elem_size;
533 14 copy_len++;
534
2/2
✓ Branch 0 (53→54) taken 7 times.
✓ Branch 1 (53→55) taken 1 times.
 8 } else if (d == 0) {
535 7 left_src += elem_size;
536 7 skip_len++;
537 } else {
538 1 break;
539 }
540 }
541 }
542 18 size_t bytes_copied = copy_len * elem_size;
543 18 memcpy(dest, src, bytes_copied);
544 18 dest += bytes_copied;
545 18 src += bytes_copied + skip_len * elem_size;
546 18 si += copy_len + skip_len;
547 18 di += copy_len;
548 18 *size -= skip_len;
549 }
550 }
551 }
552
553 // buffered elements need to be moved when we skipped duplicates
554 70 size_t total_skipped = new_size - *size;
555
4/4
✓ Branch 0 (59→60) taken 43 times.
✓ Branch 1 (59→62) taken 27 times.
✓ Branch 2 (60→61) taken 10 times.
✓ Branch 3 (60→62) taken 33 times.
 70 if (bi < new_size && total_skipped > 0) {
556 // move the remaining buffer to the end of the array
557 10 memmove(dest, bptr, elem_size * (new_size - bi));
558 }
559
560 70 return 0;
561 }
562
563 37 int cx_array_insert_sorted(
564 void **target,
565 size_t *size,
566 size_t *capacity,
567 cx_compare_func cmp_func,
568 const void *sorted_data,
569 size_t elem_size,
570 size_t elem_count,
571 CxArrayReallocator *reallocator
572 ) {
573 37 return cx_array_insert_sorted_impl(target, size, capacity,
574 cmp_func, sorted_data, elem_size, elem_count, reallocator, true);
575 }
576
577 33 int cx_array_insert_unique(
578 void **target,
579 size_t *size,
580 size_t *capacity,
581 cx_compare_func cmp_func,
582 const void *sorted_data,
583 size_t elem_size,
584 size_t elem_count,
585 CxArrayReallocator *reallocator
586 ) {
587 33 return cx_array_insert_sorted_impl(target, size, capacity,
588 cmp_func, sorted_data, elem_size, elem_count, reallocator, false);
589 }
590
591 // implementation that finds ANY index
592 765 static size_t cx_array_binary_search_inf_impl(
593 const void *arr,
594 size_t size,
595 size_t elem_size,
596 const void *elem,
597 cx_compare_func cmp_func
598 ) {
599 // special case: empty array
600
2/2
✓ Branch 0 (2→3) taken 69 times.
✓ Branch 1 (2→4) taken 696 times.
 765 if (size == 0) return 0;
601
602 // declare a variable that will contain the compare results
603 int result;
604
605 // cast the array pointer to something we can use offsets with
606 696 const char *array = arr;
607
608 // check the first array element
609 696 result = cmp_func(elem, array);
610
2/2
✓ Branch 0 (5→6) taken 39 times.
✓ Branch 1 (5→7) taken 657 times.
 696 if (result < 0) {
611 39 return size;
612
2/2
✓ Branch 0 (7→8) taken 44 times.
✓ Branch 1 (7→9) taken 613 times.
 657 } else if (result == 0) {
613 44 return 0;
614 }
615
616 // special case: there is only one element and that is smaller
617
2/2
✓ Branch 0 (9→10) taken 50 times.
✓ Branch 1 (9→11) taken 563 times.
 613 if (size == 1) return 0;
618
619 // check the last array element
620 563 result = cmp_func(elem, array + elem_size * (size - 1));
621
2/2
✓ Branch 0 (12→13) taken 45 times.
✓ Branch 1 (12→14) taken 518 times.
 563 if (result >= 0) {
622 45 return size - 1;
623 }
624
625 // the element is now guaranteed to be somewhere in the list
626 // so start the binary search
627 518 size_t left_index = 1;
628 518 size_t right_index = size - 1;
629 size_t pivot_index;
630
631
2/2
✓ Branch 0 (21→15) taken 2643 times.
✓ Branch 1 (21→22) taken 452 times.
 3095 while (left_index <= right_index) {
632 2643 pivot_index = left_index + (right_index - left_index) / 2;
633 2643 const char *arr_elem = array + pivot_index * elem_size;
634 2643 result = cmp_func(elem, arr_elem);
635
2/2
✓ Branch 0 (16→17) taken 66 times.
✓ Branch 1 (16→18) taken 2577 times.
 2643 if (result == 0) {
636 // found it!
637 66 return pivot_index;
638
2/2
✓ Branch 0 (18→19) taken 1174 times.
✓ Branch 1 (18→20) taken 1403 times.
 2577 } else if (result < 0) {
639 // element is smaller than pivot, continue search left
640 1174 right_index = pivot_index - 1;
641 } else {
642 // element is larger than pivot, continue search right
643 1403 left_index = pivot_index + 1;
644 }
645 }
646
647 // report the largest upper bound
648
2/2
✓ Branch 0 (22→23) taken 298 times.
✓ Branch 1 (22→24) taken 154 times.
 452 return result < 0 ? (pivot_index - 1) : pivot_index;
649 }
650
651 202 size_t cx_array_binary_search_inf(
652 const void *arr,
653 size_t size,
654 size_t elem_size,
655 const void *elem,
656 cx_compare_func cmp_func
657 ) {
658 202 size_t index = cx_array_binary_search_inf_impl(
659 arr, size, elem_size, elem, cmp_func);
660 // in case of equality, report the largest index
661 202 const char *e = ((const char *) arr) + (index + 1) * elem_size;
662
4/4
✓ Branch 0 (5→6) taken 130 times.
✓ Branch 1 (5→8) taken 77 times.
✓ Branch 2 (7→4) taken 5 times.
✓ Branch 3 (7→8) taken 125 times.
 207 while (index + 1 < size && cmp_func(e, elem) == 0) {
663 5 e += elem_size;
664 5 index++;
665 }
666 202 return index;
667 }
668
669 88 size_t cx_array_binary_search(
670 const void *arr,
671 size_t size,
672 size_t elem_size,
673 const void *elem,
674 cx_compare_func cmp_func
675 ) {
676 88 size_t index = cx_array_binary_search_inf(
677 arr, size, elem_size, elem, cmp_func
678 );
679
4/4
✓ Branch 0 (3→4) taken 80 times.
✓ Branch 1 (3→7) taken 8 times.
✓ Branch 2 (5→6) taken 69 times.
✓ Branch 3 (5→7) taken 11 times.
 168 if (index < size &&
680 80 cmp_func(((const char *) arr) + index * elem_size, elem) == 0) {
681 69 return index;
682 } else {
683 19 return size;
684 }
685 }
686
687 563 size_t cx_array_binary_search_sup(
688 const void *arr,
689 size_t size,
690 size_t elem_size,
691 const void *elem,
692 cx_compare_func cmp_func
693 ) {
694 563 size_t index = cx_array_binary_search_inf_impl(
695 arr, size, elem_size, elem, cmp_func
696 );
697 563 const char *e = ((const char *) arr) + index * elem_size;
698
2/2
✓ Branch 0 (3→4) taken 97 times.
✓ Branch 1 (3→5) taken 466 times.
 563 if (index == size) {
699 // no infimum means the first element is supremum
700 97 return 0;
701
2/2
✓ Branch 0 (6→7) taken 28 times.
✓ Branch 1 (6→13) taken 438 times.
 466 } else if (cmp_func(e, elem) == 0) {
702 // found an equal element, search the smallest index
703 28 e -= elem_size; // e now contains the element at index-1
704
4/4
✓ Branch 0 (9→10) taken 28 times.
✓ Branch 1 (9→12) taken 1 times.
✓ Branch 2 (11→8) taken 1 times.
✓ Branch 3 (11→12) taken 27 times.
 29 while (index > 0 && cmp_func(e, elem) == 0) {
705 1 e -= elem_size;
706 1 index--;
707 }
708 28 return index;
709 } else {
710 // we already have the largest index of the infimum (by design)
711 // the next element is the supremum (or there is no supremum)
712 438 return index + 1;
713 }
714 }
715
716 #ifndef CX_ARRAY_SWAP_SBO_SIZE
717 #define CX_ARRAY_SWAP_SBO_SIZE 128
718 #endif
719 const unsigned cx_array_swap_sbo_size = CX_ARRAY_SWAP_SBO_SIZE;
720
721 67 void cx_array_swap(
722 void *arr,
723 size_t elem_size,
724 size_t idx1,
725 size_t idx2
726 ) {
727 assert(arr != NULL);
728
729 // short circuit
730
2/2
✓ Branch 0 (2→3) taken 2 times.
✓ Branch 1 (2→4) taken 65 times.
 67 if (idx1 == idx2) return;
731
732 char sbo_mem[CX_ARRAY_SWAP_SBO_SIZE];
733 void *tmp;
734
735 // decide if we can use the local buffer
736
2/2
✓ Branch 0 (4→5) taken 1 times.
✓ Branch 1 (4→8) taken 64 times.
 65 if (elem_size > CX_ARRAY_SWAP_SBO_SIZE) {
737 1 tmp = cxMallocDefault(elem_size);
738 // we don't want to enforce error handling
739
1/2
✗ Branch 0 (6→7) not taken.
✓ Branch 1 (6→9) taken 1 times.
 1 if (tmp == NULL) abort();
740 } else {
741 64 tmp = sbo_mem;
742 }
743
744 // calculate memory locations
745 65 char *left = arr, *right = arr;
746 65 left += idx1 * elem_size;
747 65 right += idx2 * elem_size;
748
749 // three-way swap
750 65 memcpy(tmp, left, elem_size);
751 65 memcpy(left, right, elem_size);
752 65 memcpy(right, tmp, elem_size);
753
754 // free dynamic memory, if it was needed
755
2/2
✓ Branch 0 (9→10) taken 1 times.
✓ Branch 1 (9→11) taken 64 times.
 65 if (tmp != sbo_mem) {
756 1 cxFreeDefault(tmp);
757 }
758 }
759
760 // HIGH LEVEL ARRAY LIST FUNCTIONS
761
762 typedef struct {
763 struct cx_list_s base;
764 void *data;
765 size_t capacity;
766 CxArrayReallocator reallocator;
767 } cx_array_list;
768
769 179 static void cx_arl_destructor(struct cx_list_s *list) {
770 179 cx_array_list *arl = (cx_array_list *) list;
771
772 179 char *ptr = arl->data;
773
774
2/2
✓ Branch 0 (2→3) taken 5 times.
✓ Branch 1 (2→10) taken 174 times.
 179 if (list->collection.simple_destructor) {
775
2/2
✓ Branch 0 (9→4) taken 25 times.
✓ Branch 1 (9→10) taken 5 times.
 30 for (size_t i = 0; i < list->collection.size; i++) {
776
2/2
✓ Branch 0 (4→5) taken 13 times.
✓ Branch 1 (4→6) taken 12 times.
 25 cx_invoke_simple_destructor(list, ptr);
777 25 ptr += list->collection.elem_size;
778 }
779 }
780
2/2
✓ Branch 0 (10→11) taken 15 times.
✓ Branch 1 (10→18) taken 164 times.
 179 if (list->collection.advanced_destructor) {
781
2/2
✓ Branch 0 (17→12) taken 127 times.
✓ Branch 1 (17→18) taken 15 times.
 142 for (size_t i = 0; i < list->collection.size; i++) {
782
1/2
✓ Branch 0 (12→13) taken 127 times.
✗ Branch 1 (12→14) not taken.
 127 cx_invoke_advanced_destructor(list, ptr);
783 127 ptr += list->collection.elem_size;
784 }
785 }
786
787 179 cxFree(list->collection.allocator, arl->data);
788 179 cxFree(list->collection.allocator, list);
789 179 }
790
791 6101 static size_t cx_arl_insert_array(
792 struct cx_list_s *list,
793 size_t index,
794 const void *array,
795 size_t n
796 ) {
797 // out of bounds and special case check
798
3/4
✓ Branch 0 (2→3) taken 6097 times.
✓ Branch 1 (2→4) taken 4 times.
✗ Branch 2 (3→4) not taken.
✓ Branch 3 (3→5) taken 6097 times.
 6101 if (index > list->collection.size || n == 0) return 0;
799
800 // get a correctly typed pointer to the list
801 6097 cx_array_list *arl = (cx_array_list *) list;
802
803 // guarantee enough capacity
804
2/2
✓ Branch 0 (5→6) taken 248 times.
✓ Branch 1 (5→11) taken 5849 times.
 6097 if (arl->capacity < list->collection.size + n) {
805 248 const size_t new_capacity = cx_array_grow_capacity(arl->capacity,list->collection.size + n);
806
1/2
✗ Branch 0 (8→9) not taken.
✓ Branch 1 (8→10) taken 248 times.
 248 if (cxReallocateArray(
807 list->collection.allocator,
808 &arl->data, new_capacity,
809 list->collection.elem_size)
810 ) {
811 − return 0; // LCOV_EXCL_LINE
812 }
813 248 arl->capacity = new_capacity;
814 }
815
816 // determine insert position
817 6097 char *arl_data = arl->data;
818 6097 char *insert_pos = arl_data + index * list->collection.elem_size;
819
820 // do we need to move some elements?
821
2/2
✓ Branch 0 (11→12) taken 148 times.
✓ Branch 1 (11→13) taken 5949 times.
 6097 if (index < list->collection.size) {
822 148 size_t elems_to_move = list->collection.size - index;
823 148 char *target = insert_pos + n * list->collection.elem_size;
824 148 memmove(target, insert_pos, elems_to_move * list->collection.elem_size);
825 }
826
827 // place the new elements, if any
828
2/2
✓ Branch 0 (13→14) taken 6031 times.
✓ Branch 1 (13→15) taken 66 times.
 6097 if (array != NULL) {
829 6031 memcpy(insert_pos, array, n * list->collection.elem_size);
830 }
831 6097 list->collection.size += n;
832
833 6097 return n;
834 }
835
836 25 static size_t cx_arl_insert_sorted(
837 struct cx_list_s *list,
838 const void *sorted_data,
839 size_t n
840 ) {
841 // get a correctly typed pointer to the list
842 25 cx_array_list *arl = (cx_array_list *) list;
843
844
1/2
✗ Branch 0 (3→4) not taken.
✓ Branch 1 (3→5) taken 25 times.
 25 if (cx_array_insert_sorted(
845 &arl->data,
846 &list->collection.size,
847 &arl->capacity,
848 25 list->collection.cmpfunc,
849 sorted_data,
850 25 list->collection.elem_size,
851 n,
852 &arl->reallocator
853 )) {
854 // array list implementation is "all or nothing"
855 − return 0; // LCOV_EXCL_LINE
856 } else {
857 25 return n;
858 }
859 }
860
861 22 static size_t cx_arl_insert_unique(
862 struct cx_list_s *list,
863 const void *sorted_data,
864 size_t n
865 ) {
866 // get a correctly typed pointer to the list
867 22 cx_array_list *arl = (cx_array_list *) list;
868
869
1/2
✗ Branch 0 (3→4) not taken.
✓ Branch 1 (3→5) taken 22 times.
 22 if (cx_array_insert_unique(
870 &arl->data,
871 &list->collection.size,
872 &arl->capacity,
873 22 list->collection.cmpfunc,
874 sorted_data,
875 22 list->collection.elem_size,
876 n,
877 &arl->reallocator
878 )) {
879 // array list implementation is "all or nothing"
880 − return 0; // LCOV_EXCL_LINE
881 } else {
882 22 return n;
883 }
884 }
885
886 6033 static void *cx_arl_insert_element(
887 struct cx_list_s *list,
888 size_t index,
889 const void *element
890 ) {
891
2/2
✓ Branch 0 (3→4) taken 6029 times.
✓ Branch 1 (3→5) taken 4 times.
 6033 if (cx_arl_insert_array(list, index, element, 1) == 1) {
892 6029 return ((char*)((cx_array_list *) list)->data) + index * list->collection.elem_size;
893 } else {
894 4 return NULL;
895 }
896 }
897
898 10 static int cx_arl_insert_iter(
899 struct cx_iterator_s *iter,
900 const void *elem,
901 int prepend
902 ) {
903 10 struct cx_list_s *list = iter->src_handle;
904
2/2
✓ Branch 0 (2→3) taken 6 times.
✓ Branch 1 (2→9) taken 4 times.
 10 if (iter->index < list->collection.size) {
905
1/2
✗ Branch 0 (4→5) not taken.
✓ Branch 1 (4→6) taken 6 times.
 6 if (cx_arl_insert_element(list,
906 6 iter->index + 1 - prepend, elem) == NULL) {
907 − return 1; // LCOV_EXCL_LINE
908 }
909 6 iter->elem_count++;
910
2/2
✓ Branch 0 (6→7) taken 4 times.
✓ Branch 1 (6→8) taken 2 times.
 6 if (prepend != 0) {
911 4 iter->index++;
912 4 iter->elem_handle = ((char *) iter->elem_handle) + list->collection.elem_size;
913 }
914 6 return 0;
915 } else {
916
1/2
✗ Branch 0 (10→11) not taken.
✓ Branch 1 (10→12) taken 4 times.
 4 if (cx_arl_insert_element(list, list->collection.size, elem) == NULL) {
917 − return 1; // LCOV_EXCL_LINE
918 }
919 4 iter->elem_count++;
920 4 iter->index = list->collection.size;
921 4 return 0;
922 }
923 }
924
925 118 static size_t cx_arl_remove(
926 struct cx_list_s *list,
927 size_t index,
928 size_t num,
929 void *targetbuf
930 ) {
931 118 cx_array_list *arl = (cx_array_list *) list;
932
933 // out-of-bounds check
934 size_t remove;
935
2/2
✓ Branch 0 (2→3) taken 12 times.
✓ Branch 1 (2→4) taken 106 times.
 118 if (index >= list->collection.size) {
936 12 remove = 0;
937
2/2
✓ Branch 0 (4→5) taken 2 times.
✓ Branch 1 (4→6) taken 104 times.
 106 } else if (index + num > list->collection.size) {
938 2 remove = list->collection.size - index;
939 } else {
940 104 remove = num;
941 }
942
943 // easy exit
944
2/2
✓ Branch 0 (7→8) taken 12 times.
✓ Branch 1 (7→9) taken 106 times.
 118 if (remove == 0) return 0;
945
946 // destroy or copy contents
947
2/2
✓ Branch 0 (9→10) taken 90 times.
✓ Branch 1 (9→23) taken 16 times.
 106 if (targetbuf == NULL) {
948
2/2
✓ Branch 0 (22→11) taken 128 times.
✓ Branch 1 (22→24) taken 90 times.
 218 for (size_t idx = index; idx < index + remove; idx++) {
949
8/8
✓ Branch 0 (11→12) taken 24 times.
✓ Branch 1 (11→16) taken 104 times.
✓ Branch 2 (12→13) taken 12 times.
✓ Branch 3 (12→14) taken 12 times.
✓ Branch 4 (16→17) taken 8 times.
✓ Branch 5 (16→21) taken 120 times.
✓ Branch 6 (17→18) taken 4 times.
✓ Branch 7 (17→19) taken 4 times.
 128 cx_invoke_destructor(
950 list,
951 ((char *) arl->data) + idx * list->collection.elem_size
952 );
953 }
954 } else {
955 16 memcpy(
956 targetbuf,
957 16 ((char *) arl->data) + index * list->collection.elem_size,
958 16 remove * list->collection.elem_size
959 );
960 }
961
962 // short-circuit removal of last elements
963
2/2
✓ Branch 0 (24→25) taken 20 times.
✓ Branch 1 (24→26) taken 86 times.
 106 if (index + remove == list->collection.size) {
964 20 list->collection.size -= remove;
965 20 return remove;
966 }
967
968 // just move the elements to the left
969 86 cx_array_copy(
970 &arl->data,
971 86 &list->collection.size,
972 86 &arl->capacity,
973 0,
974 index,
975 86 ((char *) arl->data) + (index + remove) * list->collection.elem_size,
976 86 list->collection.elem_size,
977 86 list->collection.size - index - remove,
978 &arl->reallocator
979 );
980
981 // decrease the size
982 86 list->collection.size -= remove;
983
984 86 return remove;
985 }
986
987 10 static void cx_arl_clear(struct cx_list_s *list) {
988
1/2
✗ Branch 0 (2→3) not taken.
✓ Branch 1 (2→4) taken 10 times.
 10 if (list->collection.size == 0) return;
989
990 10 cx_array_list *arl = (cx_array_list *) list;
991 10 char *ptr = arl->data;
992
993
2/2
✓ Branch 0 (4→5) taken 2 times.
✓ Branch 1 (4→12) taken 8 times.
 10 if (list->collection.simple_destructor) {
994
2/2
✓ Branch 0 (11→6) taken 112 times.
✓ Branch 1 (11→12) taken 2 times.
 114 for (size_t i = 0; i < list->collection.size; i++) {
995
2/2
✓ Branch 0 (6→7) taken 56 times.
✓ Branch 1 (6→8) taken 56 times.
 112 cx_invoke_simple_destructor(list, ptr);
996 112 ptr += list->collection.elem_size;
997 }
998 }
999
2/2
✓ Branch 0 (12→13) taken 2 times.
✓ Branch 1 (12→20) taken 8 times.
 10 if (list->collection.advanced_destructor) {
1000
2/2
✓ Branch 0 (19→14) taken 142 times.
✓ Branch 1 (19→20) taken 2 times.
 144 for (size_t i = 0; i < list->collection.size; i++) {
1001
2/2
✓ Branch 0 (14→15) taken 71 times.
✓ Branch 1 (14→16) taken 71 times.
 142 cx_invoke_advanced_destructor(list, ptr);
1002 142 ptr += list->collection.elem_size;
1003 }
1004 }
1005
1006 10 memset(arl->data, 0, list->collection.size * list->collection.elem_size);
1007 10 list->collection.size = 0;
1008 }
1009
1010 23 static int cx_arl_swap(
1011 struct cx_list_s *list,
1012 size_t i,
1013 size_t j
1014 ) {
1015
4/4
✓ Branch 0 (2→3) taken 19 times.
✓ Branch 1 (2→4) taken 4 times.
✓ Branch 2 (3→4) taken 2 times.
✓ Branch 3 (3→5) taken 17 times.
 23 if (i >= list->collection.size || j >= list->collection.size) return 1;
1016 17 cx_array_list *arl = (cx_array_list *) list;
1017 17 cx_array_swap(arl->data, list->collection.elem_size, i, j);
1018 17 return 0;
1019 }
1020
1021 8004 static void *cx_arl_at(
1022 const struct cx_list_s *list,
1023 size_t index
1024 ) {
1025
2/2
✓ Branch 0 (2→3) taken 7996 times.
✓ Branch 1 (2→4) taken 8 times.
 8004 if (index < list->collection.size) {
1026 7996 const cx_array_list *arl = (const cx_array_list *) list;
1027 7996 char *space = arl->data;
1028 7996 return space + index * list->collection.elem_size;
1029 } else {
1030 8 return NULL;
1031 }
1032 }
1033
1034 175 static size_t cx_arl_find_remove(
1035 struct cx_list_s *list,
1036 const void *elem,
1037 bool remove
1038 ) {
1039 assert(list != NULL);
1040 assert(list->collection.cmpfunc != NULL);
1041
1/2
✗ Branch 0 (2→3) not taken.
✓ Branch 1 (2→4) taken 175 times.
 175 if (list->collection.size == 0) return 0;
1042 175 char *cur = ((const cx_array_list *) list)->data;
1043
1044 // optimize with binary search, when sorted
1045
2/2
✓ Branch 0 (4→5) taken 8 times.
✓ Branch 1 (4→10) taken 167 times.
 175 if (list->collection.sorted) {
1046 8 size_t i = cx_array_binary_search(
1047 cur,
1048 8 list->collection.size,
1049 8 list->collection.elem_size,
1050 elem,
1051 8 list->collection.cmpfunc
1052 );
1053
4/4
✓ Branch 0 (6→7) taken 4 times.
✓ Branch 1 (6→9) taken 4 times.
✓ Branch 2 (7→8) taken 2 times.
✓ Branch 3 (7→9) taken 2 times.
 8 if (remove && i < list->collection.size) {
1054 2 cx_arl_remove(list, i, 1, NULL);
1055 }
1056 8 return i;
1057 }
1058
1059 // fallback: linear search
1060
2/2
✓ Branch 0 (17→11) taken 16947 times.
✓ Branch 1 (17→18) taken 83 times.
 17030 for (size_t i = 0; i < list->collection.size; i++) {
1061
2/2
✓ Branch 0 (12→13) taken 84 times.
✓ Branch 1 (12→16) taken 16863 times.
 16947 if (0 == list->collection.cmpfunc(elem, cur)) {
1062
2/2
✓ Branch 0 (13→14) taken 2 times.
✓ Branch 1 (13→15) taken 82 times.
 84 if (remove) {
1063 2 cx_arl_remove(list, i, 1, NULL);
1064 }
1065 84 return i;
1066 }
1067 16863 cur += list->collection.elem_size;
1068 }
1069 83 return list->collection.size;
1070 }
1071
1072 4 static void cx_arl_sort(struct cx_list_s *list) {
1073 assert(list->collection.cmpfunc != NULL);
1074 4 qsort(((cx_array_list *) list)->data,
1075 list->collection.size,
1076 list->collection.elem_size,
1077 4 list->collection.cmpfunc
1078 );
1079 4 }
1080
1081 18 static int cx_arl_compare(
1082 const struct cx_list_s *list,
1083 const struct cx_list_s *other
1084 ) {
1085 assert(list->collection.cmpfunc != NULL);
1086
2/2
✓ Branch 0 (2→3) taken 14 times.
✓ Branch 1 (2→10) taken 4 times.
 18 if (list->collection.size == other->collection.size) {
1087 14 const char *left = ((const cx_array_list *) list)->data;
1088 14 const char *right = ((const cx_array_list *) other)->data;
1089
2/2
✓ Branch 0 (8→4) taken 371 times.
✓ Branch 1 (8→9) taken 10 times.
 381 for (size_t i = 0; i < list->collection.size; i++) {
1090 371 int d = list->collection.cmpfunc(left, right);
1091
2/2
✓ Branch 0 (5→6) taken 4 times.
✓ Branch 1 (5→7) taken 367 times.
 371 if (d != 0) {
1092 4 return d;
1093 }
1094 367 left += list->collection.elem_size;
1095 367 right += other->collection.elem_size;
1096 }
1097 10 return 0;
1098 } else {
1099
2/2
✓ Branch 0 (10→11) taken 2 times.
✓ Branch 1 (10→12) taken 2 times.
 4 return list->collection.size < other->collection.size ? -1 : 1;
1100 }
1101 }
1102
1103 2 static void cx_arl_reverse(struct cx_list_s *list) {
1104
1/2
✗ Branch 0 (2→3) not taken.
✓ Branch 1 (2→4) taken 2 times.
 2 if (list->collection.size < 2) return;
1105 2 void *data = ((const cx_array_list *) list)->data;
1106 2 size_t half = list->collection.size / 2;
1107
2/2
✓ Branch 0 (7→5) taken 50 times.
✓ Branch 1 (7→8) taken 2 times.
 52 for (size_t i = 0; i < half; i++) {
1108 50 cx_array_swap(data, list->collection.elem_size, i, list->collection.size - 1 - i);
1109 }
1110 }
1111
1112 525 static bool cx_arl_iter_valid(const void *it) {
1113 525 const struct cx_iterator_s *iter = it;
1114 525 const struct cx_list_s *list = iter->src_handle;
1115 525 return iter->index < list->collection.size;
1116 }
1117
1118 5777 static void *cx_arl_iter_current(const void *it) {
1119 5777 const struct cx_iterator_s *iter = it;
1120 5777 return iter->elem_handle;
1121 }
1122
1123 5462 static void cx_arl_iter_next(void *it) {
1124 5462 struct cx_iterator_s *iter = it;
1125
2/2
✓ Branch 0 (2→3) taken 30 times.
✓ Branch 1 (2→5) taken 5432 times.
 5462 if (iter->base.remove) {
1126 30 iter->base.remove = false;
1127 30 cx_arl_remove(iter->src_handle, iter->index, 1, NULL);
1128 30 iter->elem_count--;
1129 } else {
1130 5432 iter->index++;
1131 5432 iter->elem_handle =
1132 5432 ((char *) iter->elem_handle)
1133 5432 + ((const struct cx_list_s *) iter->src_handle)->collection.elem_size;
1134 }
1135 5462 }
1136
1137 222 static void cx_arl_iter_prev(void *it) {
1138 222 struct cx_iterator_s *iter = it;
1139
2/2
✓ Branch 0 (2→3) taken 28 times.
✓ Branch 1 (2→5) taken 194 times.
 222 if (iter->base.remove) {
1140 28 iter->base.remove = false;
1141 28 cx_arl_remove(iter->src_handle, iter->index, 1, NULL);
1142 28 iter->elem_count--;
1143 }
1144 222 iter->index--;
1145 222 cx_array_list *list = iter->src_handle;
1146
2/2
✓ Branch 0 (5→6) taken 214 times.
✓ Branch 1 (5→7) taken 8 times.
 222 if (iter->index < list->base.collection.size) {
1147 214 iter->elem_handle = ((char *) list->data)
1148 214 + iter->index * list->base.collection.elem_size;
1149 }
1150 222 }
1151
1152 4 static int cx_arl_change_capacity(
1153 struct cx_list_s *list,
1154 size_t new_capacity
1155 ) {
1156 4 cx_array_list *arl = (cx_array_list *)list;
1157 4 return cxReallocateArray(list->collection.allocator,
1158 &arl->data, new_capacity, list->collection.elem_size);
1159 }
1160
1161 242 static struct cx_iterator_s cx_arl_iterator(
1162 const struct cx_list_s *list,
1163 size_t index,
1164 bool backwards
1165 ) {
1166 struct cx_iterator_s iter;
1167
1168 242 iter.index = index;
1169 242 iter.src_handle = (void*)list;
1170 242 iter.elem_handle = cx_arl_at(list, index);
1171 242 iter.elem_size = list->collection.elem_size;
1172 242 iter.elem_count = list->collection.size;
1173 242 iter.base.valid = cx_arl_iter_valid;
1174 242 iter.base.current = cx_arl_iter_current;
1175
2/2
✓ Branch 0 (3→4) taken 12 times.
✓ Branch 1 (3→5) taken 230 times.
 242 iter.base.next = backwards ? cx_arl_iter_prev : cx_arl_iter_next;
1176 242 iter.base.remove = false;
1177 242 iter.base.allow_remove = true;
1178
1179 242 return iter;
1180 }
1181
1182 static cx_list_class cx_array_list_class = {
1183 cx_arl_destructor,
1184 cx_arl_insert_element,
1185 cx_arl_insert_array,
1186 cx_arl_insert_sorted,
1187 cx_arl_insert_unique,
1188 cx_arl_insert_iter,
1189 cx_arl_remove,
1190 cx_arl_clear,
1191 cx_arl_swap,
1192 cx_arl_at,
1193 cx_arl_find_remove,
1194 cx_arl_sort,
1195 cx_arl_compare,
1196 cx_arl_reverse,
1197 cx_arl_change_capacity,
1198 cx_arl_iterator,
1199 };
1200
1201 179 CxList *cxArrayListCreate(
1202 const CxAllocator *allocator,
1203 cx_compare_func comparator,
1204 size_t elem_size,
1205 size_t initial_capacity
1206 ) {
1207
2/2
✓ Branch 0 (2→3) taken 20 times.
✓ Branch 1 (2→4) taken 159 times.
 179 if (allocator == NULL) {
1208 20 allocator = cxDefaultAllocator;
1209 }
1210
1211 179 cx_array_list *list = cxCalloc(allocator, 1, sizeof(cx_array_list));
1212
1/2
✗ Branch 0 (5→6) not taken.
✓ Branch 1 (5→7) taken 179 times.
 179 if (list == NULL) return NULL;
1213 179 cx_list_init((CxList*)list, &cx_array_list_class,
1214 allocator, comparator, elem_size);
1215 179 list->capacity = initial_capacity;
1216
1217 // allocate the array after the real elem_size is known
1218 179 list->data = cxCalloc(allocator, initial_capacity,
1219 list->base.collection.elem_size);
1220 − if (list->data == NULL) { // LCOV_EXCL_START
1221 − cxFree(allocator, list);
1222 − return NULL;
1223 } // LCOV_EXCL_STOP
1224
1225 // configure the reallocator
1226 179 list->reallocator = cx_array_reallocator(allocator, NULL);
1227
1228 179 return (CxList *) list;
1229 }
1230