GCC Code Coverage Report

Directory: ./
File: list.c
Date: 2025-04-06 13:22:55
Exec Total Coverage
Lines: 199 201 99.0%
Functions: 32 32 100.0%
Branches: 75 86 87.2%
Line Branch Exec Source
1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
3 *
4 * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 *
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 */
28
29 #include "cx/list.h"
30
31 #include <string.h>
32
33 // <editor-fold desc="Store Pointers Functionality">
34
35 static _Thread_local cx_compare_func cx_pl_cmpfunc_impl;
36
37 31453 static int cx_pl_cmpfunc(
38 const void *l,
39 const void *r
40 ) {
41 31453 void *const *lptr = l;
42 31453 void *const *rptr = r;
43
1/2
✓ Branch 0 taken 31453 times.
✗ Branch 1 not taken.
 31453 const void *left = lptr == NULL ? NULL : *lptr;
44
1/2
✓ Branch 0 taken 31453 times.
✗ Branch 1 not taken.
 31453 const void *right = rptr == NULL ? NULL : *rptr;
45 31453 return cx_pl_cmpfunc_impl(left, right);
46 }
47
48 120 static void cx_pl_hack_cmpfunc(const struct cx_list_s *list) {
49 // cast away const - this is the hacky thing
50 120 struct cx_collection_s *l = (struct cx_collection_s*) &list->collection;
51 120 cx_pl_cmpfunc_impl = l->cmpfunc;
52 120 l->cmpfunc = cx_pl_cmpfunc;
53 120 }
54
55 120 static void cx_pl_unhack_cmpfunc(const struct cx_list_s *list) {
56 // cast away const - this is the hacky thing
57 120 struct cx_collection_s *l = (struct cx_collection_s*) &list->collection;
58 120 l->cmpfunc = cx_pl_cmpfunc_impl;
59 120 }
60
61 72 static void cx_pl_destructor(struct cx_list_s *list) {
62 72 list->climpl->deallocate(list);
63 72 }
64
65 5384 static int cx_pl_insert_element(
66 struct cx_list_s *list,
67 size_t index,
68 const void *element
69 ) {
70 5384 return list->climpl->insert_element(list, index, &element);
71 }
72
73 8 static size_t cx_pl_insert_array(
74 struct cx_list_s *list,
75 size_t index,
76 const void *array,
77 size_t n
78 ) {
79 8 return list->climpl->insert_array(list, index, array, n);
80 }
81
82 32 static size_t cx_pl_insert_sorted(
83 struct cx_list_s *list,
84 const void *array,
85 size_t n
86 ) {
87 32 cx_pl_hack_cmpfunc(list);
88 32 size_t result = list->climpl->insert_sorted(list, array, n);
89 32 cx_pl_unhack_cmpfunc(list);
90 32 return result;
91 }
92
93 10 static int cx_pl_insert_iter(
94 struct cx_iterator_s *iter,
95 const void *elem,
96 int prepend
97 ) {
98 10 struct cx_list_s *list = iter->src_handle.m;
99 10 return list->climpl->insert_iter(iter, &elem, prepend);
100 }
101
102 22 static size_t cx_pl_remove(
103 struct cx_list_s *list,
104 size_t index,
105 size_t num,
106 void *targetbuf
107 ) {
108 22 return list->climpl->remove(list, index, num, targetbuf);
109 }
110
111 6 static void cx_pl_clear(struct cx_list_s *list) {
112 6 list->climpl->clear(list);
113 6 }
114
115 44 static int cx_pl_swap(
116 struct cx_list_s *list,
117 size_t i,
118 size_t j
119 ) {
120 44 return list->climpl->swap(list, i, j);
121 }
122
123 2698 static void *cx_pl_at(
124 const struct cx_list_s *list,
125 size_t index
126 ) {
127 2698 void **ptr = list->climpl->at(list, index);
128
2/2
✓ Branch 0 taken 2696 times.
✓ Branch 1 taken 2 times.
 2698 return ptr == NULL ? NULL : *ptr;
129 }
130
131 68 static size_t cx_pl_find_remove(
132 struct cx_list_s *list,
133 const void *elem,
134 bool remove
135 ) {
136 68 cx_pl_hack_cmpfunc(list);
137 68 size_t ret = list->climpl->find_remove(list, &elem, remove);
138 68 cx_pl_unhack_cmpfunc(list);
139 68 return ret;
140 }
141
142 6 static void cx_pl_sort(struct cx_list_s *list) {
143 6 cx_pl_hack_cmpfunc(list);
144 6 list->climpl->sort(list);
145 6 cx_pl_unhack_cmpfunc(list);
146 6 }
147
148 14 static int cx_pl_compare(
149 const struct cx_list_s *list,
150 const struct cx_list_s *other
151 ) {
152 14 cx_pl_hack_cmpfunc(list);
153 14 int ret = list->climpl->compare(list, other);
154 14 cx_pl_unhack_cmpfunc(list);
155 14 return ret;
156 }
157
158 2 static void cx_pl_reverse(struct cx_list_s *list) {
159 2 list->climpl->reverse(list);
160 2 }
161
162 3084 static void *cx_pl_iter_current(const void *it) {
163 3084 const struct cx_iterator_s *iter = it;
164 3084 void **ptr = iter->base.current_impl(it);
165
1/2
✓ Branch 0 taken 3084 times.
✗ Branch 1 not taken.
 3084 return ptr == NULL ? NULL : *ptr;
166 }
167
168 112 static struct cx_iterator_s cx_pl_iterator(
169 const struct cx_list_s *list,
170 size_t index,
171 bool backwards
172 ) {
173 112 struct cx_iterator_s iter = list->climpl->iterator(list, index, backwards);
174 112 iter.base.current_impl = iter.base.current;
175 112 iter.base.current = cx_pl_iter_current;
176 112 return iter;
177 }
178
179 static cx_list_class cx_pointer_list_class = {
180 cx_pl_destructor,
181 cx_pl_insert_element,
182 cx_pl_insert_array,
183 cx_pl_insert_sorted,
184 cx_pl_insert_iter,
185 cx_pl_remove,
186 cx_pl_clear,
187 cx_pl_swap,
188 cx_pl_at,
189 cx_pl_find_remove,
190 cx_pl_sort,
191 cx_pl_compare,
192 cx_pl_reverse,
193 cx_pl_iterator,
194 };
195 // </editor-fold>
196
197 // <editor-fold desc="empty list implementation">
198
199 2 static void cx_emptyl_noop(cx_attr_unused CxList *list) {
200 // this is a noop, but MUST be implemented
201 2 }
202
203 2 static void *cx_emptyl_at(
204 cx_attr_unused const struct cx_list_s *list,
205 cx_attr_unused size_t index
206 ) {
207 2 return NULL;
208 }
209
210 2 static size_t cx_emptyl_find_remove(
211 cx_attr_unused struct cx_list_s *list,
212 cx_attr_unused const void *elem,
213 cx_attr_unused bool remove
214 ) {
215 2 return 0;
216 }
217
218 8 static bool cx_emptyl_iter_valid(cx_attr_unused const void *iter) {
219 8 return false;
220 }
221
222 10 static CxIterator cx_emptyl_iterator(
223 const struct cx_list_s *list,
224 size_t index,
225 cx_attr_unused bool backwards
226 ) {
227 10 CxIterator iter = {0};
228 10 iter.src_handle.c = list;
229 10 iter.index = index;
230 10 iter.base.valid = cx_emptyl_iter_valid;
231 10 return iter;
232 }
233
234 static cx_list_class cx_empty_list_class = {
235 cx_emptyl_noop,
236 NULL,
237 NULL,
238 NULL,
239 NULL,
240 NULL,
241 cx_emptyl_noop,
242 NULL,
243 cx_emptyl_at,
244 cx_emptyl_find_remove,
245 cx_emptyl_noop,
246 NULL,
247 cx_emptyl_noop,
248 cx_emptyl_iterator,
249 };
250
251 CxList cx_empty_list = {
252 {
253 NULL,
254 NULL,
255 0,
256 0,
257 NULL,
258 NULL,
259 NULL,
260 false,
261 true,
262 },
263 &cx_empty_list_class,
264 NULL
265 };
266
267 CxList *const cxEmptyList = &cx_empty_list;
268
269 // </editor-fold>
270
271 #define invoke_list_func(name, list, ...) \
272 ((list)->climpl == NULL ? (list)->cl->name : (list)->climpl->name) \
273 (list, __VA_ARGS__)
274
275 40 size_t cx_list_default_insert_array(
276 struct cx_list_s *list,
277 size_t index,
278 const void *data,
279 size_t n
280 ) {
281 40 size_t elem_size = list->collection.elem_size;
282 40 const char *src = data;
283 40 size_t i = 0;
284
2/2
✓ Branch 0 taken 654 times.
✓ Branch 1 taken 40 times.
 694 for (; i < n; i++) {
285
3/4
✓ Branch 0 taken 610 times.
✓ Branch 1 taken 44 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 654 times.
 654 if (0 != invoke_list_func(
286 insert_element, list, index + i,
287 ✗ src + (i * elem_size))) return i;
288 }
289 40 return i;
290 }
291
292 32 size_t cx_list_default_insert_sorted(
293 struct cx_list_s *list,
294 const void *sorted_data,
295 size_t n
296 ) {
297 // corner case
298
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 32 times.
 32 if (n == 0) return 0;
299
300 32 size_t elem_size = list->collection.elem_size;
301 32 cx_compare_func cmp = list->collection.cmpfunc;
302 32 const char *src = sorted_data;
303
304 // track indices and number of inserted items
305 32 size_t di = 0, si = 0, inserted = 0;
306
307 // search the list for insertion points
308
2/2
✓ Branch 0 taken 164 times.
✓ Branch 1 taken 12 times.
 176 for (; di < list->collection.size; di++) {
309
2/2
✓ Branch 0 taken 82 times.
✓ Branch 1 taken 82 times.
 164 const void *list_elm = invoke_list_func(at, list, di);
310
311 // compare current list element with first source element
312 // if less or equal, skip
313
2/2
✓ Branch 1 taken 124 times.
✓ Branch 2 taken 40 times.
 164 if (cmp(list_elm, src) <= 0) {
314 124 continue;
315 }
316
317 // determine number of consecutive elements that can be inserted
318 40 size_t ins = 1;
319 40 const char *next = src;
320
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 20 times.
 60 while (++si < n) {
321 40 next += elem_size;
322 // once we become larger than the list elem, break
323
2/2
✓ Branch 1 taken 20 times.
✓ Branch 2 taken 20 times.
 40 if (cmp(list_elm, next) <= 0) {
324 20 break;
325 }
326 // otherwise, we can insert one more
327 20 ins++;
328 }
329
330 // insert the elements at location si
331
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 16 times.
 40 if (ins == 1) {
332
3/4
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 12 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 24 times.
 24 if (0 != invoke_list_func(
333 ✗ insert_element, list, di, src)) return inserted;
334 } else {
335
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 8 times.
 16 size_t r = invoke_list_func(insert_array, list, di, src, ins);
336
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 16 times.
 16 if (r < ins) return inserted + r;
337 }
338 40 inserted += ins;
339 40 di += ins;
340
341 // everything inserted?
342
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 20 times.
 40 if (inserted == n) return inserted;
343 20 src = next;
344 }
345
346 // insert remaining items
347
1/2
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
 12 if (si < n) {
348
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
 12 inserted += invoke_list_func(insert_array, list, di, src, n - si);
349 }
350
351 12 return inserted;
352 }
353
354 4 void cx_list_default_sort(struct cx_list_s *list) {
355 4 size_t elem_size = list->collection.elem_size;
356 4 size_t list_size = list->collection.size;
357 4 void *tmp = malloc(elem_size * list_size);
358
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4 times.
 4 if (tmp == NULL) abort();
359
360 // copy elements from source array
361 4 char *loc = tmp;
362
2/2
✓ Branch 0 taken 1000 times.
✓ Branch 1 taken 4 times.
 1004 for (size_t i = 0; i < list_size; i++) {
363
2/2
✓ Branch 0 taken 500 times.
✓ Branch 1 taken 500 times.
 1000 void *src = invoke_list_func(at, list, i);
364 1000 memcpy(loc, src, elem_size);
365 1000 loc += elem_size;
366 }
367
368 // qsort
369 4 qsort(tmp, list_size, elem_size,
370 4 list->collection.cmpfunc);
371
372 // copy elements back
373 4 loc = tmp;
374
2/2
✓ Branch 0 taken 1000 times.
✓ Branch 1 taken 4 times.
 1004 for (size_t i = 0; i < list_size; i++) {
375
2/2
✓ Branch 0 taken 500 times.
✓ Branch 1 taken 500 times.
 1000 void *dest = invoke_list_func(at, list, i);
376 1000 memcpy(dest, loc, elem_size);
377 1000 loc += elem_size;
378 }
379
380 4 free(tmp);
381 4 }
382
383 44 int cx_list_default_swap(struct cx_list_s *list, size_t i, size_t j) {
384
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 40 times.
 44 if (i == j) return 0;
385
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 32 times.
 40 if (i >= list->collection.size) return 1;
386
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 28 times.
 32 if (j >= list->collection.size) return 1;
387
388 28 size_t elem_size = list->collection.elem_size;
389
390 28 void *tmp = malloc(elem_size);
391
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 28 times.
 28 if (tmp == NULL) return 1;
392
393
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 14 times.
 28 void *ip = invoke_list_func(at, list, i);
394
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 14 times.
 28 void *jp = invoke_list_func(at, list, j);
395
396 28 memcpy(tmp, ip, elem_size);
397 28 memcpy(ip, jp, elem_size);
398 28 memcpy(jp, tmp, elem_size);
399
400 28 free(tmp);
401
402 28 return 0;
403 }
404
405 153 void cx_list_init(
406 struct cx_list_s *list,
407 struct cx_list_class_s *cl,
408 const struct cx_allocator_s *allocator,
409 cx_compare_func comparator,
410 size_t elem_size
411 ) {
412 153 list->cl = cl;
413 153 list->collection.allocator = allocator;
414 153 list->collection.cmpfunc = comparator;
415
2/2
✓ Branch 0 taken 81 times.
✓ Branch 1 taken 72 times.
 153 if (elem_size > 0) {
416 81 list->collection.elem_size = elem_size;
417 } else {
418 72 list->collection.elem_size = sizeof(void *);
419
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 70 times.
 72 if (list->collection.cmpfunc == NULL) {
420 2 list->collection.cmpfunc = cx_cmp_ptr;
421 }
422 72 list->collection.store_pointer = true;
423 72 list->climpl = list->cl;
424 72 list->cl = &cx_pointer_list_class;
425 }
426 153 }
427
428 177 int cxListCompare(
429 const CxList *list,
430 const CxList *other
431 ) {
432 177 bool cannot_optimize = false;
433
434 // if one is storing pointers but the other is not
435 177 cannot_optimize |= list->collection.store_pointer ^ other->collection.store_pointer;
436
437 // if one class is wrapped but the other is not
438 177 cannot_optimize |= (list->climpl == NULL) ^ (other->climpl == NULL);
439
440 // if the compare functions do not match or both are NULL
441
2/2
✓ Branch 0 taken 93 times.
✓ Branch 1 taken 84 times.
 177 if (!cannot_optimize) {
442
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 65 times.
 93 cx_compare_func list_cmp = (cx_compare_func) (list->climpl != NULL ?
443 93 list->climpl->compare : list->cl->compare);
444
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 65 times.
 93 cx_compare_func other_cmp = (cx_compare_func) (other->climpl != NULL ?
445 93 other->climpl->compare : other->cl->compare);
446 93 cannot_optimize |= list_cmp != other_cmp;
447 93 cannot_optimize |= list_cmp == NULL;
448 }
449
450
2/2
✓ Branch 0 taken 149 times.
✓ Branch 1 taken 28 times.
 177 if (cannot_optimize) {
451 // lists are definitely different - cannot use internal compare function
452
2/2
✓ Branch 0 taken 105 times.
✓ Branch 1 taken 44 times.
 149 if (list->collection.size == other->collection.size) {
453 105 CxIterator left = list->cl->iterator(list, 0, false);
454 105 CxIterator right = other->cl->iterator(other, 0, false);
455
2/2
✓ Branch 0 taken 3184 times.
✓ Branch 1 taken 65 times.
 3249 for (size_t i = 0; i < list->collection.size; i++) {
456 3184 void *leftValue = cxIteratorCurrent(left);
457 3184 void *rightValue = cxIteratorCurrent(right);
458 3184 int d = list->collection.cmpfunc(leftValue, rightValue);
459
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 3144 times.
 3184 if (d != 0) {
460 40 return d;
461 }
462 3144 cxIteratorNext(left);
463 3144 cxIteratorNext(right);
464 }
465 65 return 0;
466 } else {
467
2/2
✓ Branch 0 taken 22 times.
✓ Branch 1 taken 22 times.
 44 return list->collection.size < other->collection.size ? -1 : 1;
468 }
469 } else {
470 // lists are compatible
471 28 return list->cl->compare(list, other);
472 }
473 }
474
475 29 CxIterator cxListMutIteratorAt(
476 CxList *list,
477 size_t index
478 ) {
479 29 CxIterator it = list->cl->iterator(list, index, false);
480 29 it.base.mutating = true;
481 29 return it;
482 }
483
484 13 CxIterator cxListMutBackwardsIteratorAt(
485 CxList *list,
486 size_t index
487 ) {
488 13 CxIterator it = list->cl->iterator(list, index, true);
489 13 it.base.mutating = true;
490 13 return it;
491 }
492
493 154 void cxListFree(CxList *list) {
494
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 154 times.
 154 if (list == NULL) return;
495 154 list->cl->deallocate(list);
496 }
497