GCC Code Coverage Report

Directory: ./
File: common/src/list.c
Date: 2026-11-08 20:01:15
Exec Total Coverage
Lines: 265 266 99.6%
Functions: 21 21 100.0%
Branches: 144 146 98.6%
Line Branch Exec Source
1 /*
2 * Common code for dealing with linked lists.
3 * Copyright © 2021-2026, albinoloverats ~ Software Development
4 * email: webmaster@albinoloverats.net
5 *
6 * This program is free software: you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation, either version 3 of the License, or
9 * (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program. If not, see <http://www.gnu.org/licenses/>.
18 *
19 */
20
21 #include <stdlib.h>
22
23 #include <stdbool.h>
24
25 #include "common.h"
26 #include "mem.h"
27 #include "non-gnu.h"
28 #include "list.h"
29 #include "error.h"
30
31 typedef struct _item_s
32 {
33 struct _item_s *next;
34 const void *data;
35 }
36 item_s;
37
38 typedef struct
39 {
40 item_s *head; /*!< The first item in the list */
41 item_s *tail; /*!< The last item in the list - allows easy appending of items */
42 size_t size; /*!< The number of items in the list - gives constant lookup, so no need to count each time */
43 int (*compare)(const void *, const void *); /*!< How to compare items in the list */
44 bool duplicates:1; /*!< Whether to allow duplicate items in the list */
45 bool sorted:1; /*!< Whether the items should be sorted */
46 }
47 list_private_s;
48
49 typedef struct
50 {
51 item_s *next;
52 }
53 iterator_s;
54
55 89 extern list_t list_init(int c(const void *, const void *), bool dupes, bool sorted)
56 {
57 89 list_private_s *list = m_calloc(sizeof( list_private_s ), sizeof( byte_t ));
58 89 list->size = 0;
59 89 list->compare = c;
60 89 list->duplicates = dupes;
61 89 list->sorted = sorted;
62 89 return list;
63 }
64
65 86 extern void list_deinit_aux(list_t ptr, void f(void *))
66 {
67 69 list_private_s *list_ptr = (list_private_s *)ptr;
68
2/2
✓ Branch 0 taken 19 times.
✓ Branch 1 taken 67 times.
 86 if (!list_ptr)
69 2 return;
70 84 item_s *item = list_ptr->head;
71
2/2
✓ Branch 0 taken 349 times.
✓ Branch 1 taken 84 times.
 433 while (item)
72 {
73
2/2
✓ Branch 0 taken 289 times.
✓ Branch 1 taken 60 times.
 349 if (f)
74 289 f((void *)item->data);
75 349 item_s *next = item->next;
76 349 free(item);
77 190 item = next;
78 }
79 84 free(list_ptr);
80 84 return;
81 }
82
83 3 extern list_t list_copy(list_t ptr, void *c(const void *))
84 {
85 3 list_private_s *list_ptr = (list_private_s *)ptr;
86
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 2 times.
 3 if (!list_ptr)
87 1 return NULL;
88 2 list_t copy = list_init(list_ptr->compare, list_ptr->duplicates, list_ptr->sorted);
89
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 1 times.
 2 if (!list_ptr->size)
90 1 return copy;
91 1 item_s *item = list_ptr->head;
92 do
93 {
94 3 list_append(copy, c(item->data));
95 3 item = item->next;
96 }
97
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 1 times.
 3 while (item);
98 1 return copy;
99 }
100
101 /*
102 * TODO see whether this could be better as a macro
103 */
104 203 extern size_t list_size(list_t ptr)
105 {
106 203 list_private_s *list_ptr = (list_private_s *)ptr;
107
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 202 times.
 203 if (!list_ptr)
108 1 return 0;
109 202 return list_ptr->size;
110 }
111
112 334 extern bool list_append(list_t ptr, const void *d)
113 {
114 175 list_private_s *list_ptr = (list_private_s *)ptr;
115
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 174 times.
 175 if (!list_ptr)
116 1 return false;
117
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 313 times.
 333 if (list_ptr->sorted)
118 20 return list_add(ptr, d);
119
4/4
✓ Branch 0 taken 225 times.
✓ Branch 1 taken 88 times.
✓ Branch 3 taken 161 times.
✓ Branch 4 taken 64 times.
 313 if (!list_ptr->duplicates && list_contains(ptr, d))
120 2 return false;
121 311 item_s *new = m_calloc(sizeof( item_s ), sizeof( byte_t ));
122 311 new->data = d;
123 311 item_s *end = list_ptr->tail;
124
2/2
✓ Branch 0 taken 250 times.
✓ Branch 1 taken 61 times.
 311 if (end)
125 250 end->next = new;
126
2/2
✓ Branch 0 taken 61 times.
✓ Branch 1 taken 250 times.
 311 if (!list_ptr->head)
127 61 list_ptr->head = new;
128 311 list_ptr->tail = new;
129 311 list_ptr->size++;
130 311 return true;
131 }
132
133 7 extern bool list_insert(list_t ptr, size_t i, const void *d)
134 {
135 7 list_private_s *list_ptr = (list_private_s *)ptr;
136
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 6 times.
 7 if (!list_ptr)
137 1 return false;
138
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 5 times.
 6 if (list_ptr->sorted)
139 1 return list_add(ptr, d);
140
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 4 times.
 5 if (i >= list_ptr->size)
141 1 return list_append(ptr, d);
142
4/4
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 1 times.
✓ Branch 3 taken 1 times.
✓ Branch 4 taken 2 times.
 4 if (!list_ptr->duplicates && list_contains(ptr, d))
143 1 return false;
144 3 item_s *new = m_calloc(sizeof( item_s ), sizeof( byte_t ));
145 3 new->data = d;
146 3 item_s *prev = list_ptr->head;
147
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 2 times.
 3 if (i == 0)
148 {
149 1 new->next = prev;
150 1 list_ptr->head = new;
151 }
152 else
153 {
154
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 2 times.
 4 for (size_t j = 0; j < i - 1; j++)
155 2 prev = prev->next;
156 2 item_s *next = prev->next;
157 2 prev->next = new;
158 2 new->next = next;
159 }
160 3 list_ptr->size++;
161 3 return true;
162 }
163
164 192 extern bool list_add(list_t ptr, const void *d)
165 {
166 192 list_private_s *list_ptr = (list_private_s *)ptr;
167
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 191 times.
 192 if (!list_ptr)
168 1 return false;
169
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 190 times.
 191 if (!list_ptr->sorted)
170 1 return list_append(ptr, d);
171
4/4
✓ Branch 0 taken 149 times.
✓ Branch 1 taken 41 times.
✓ Branch 3 taken 2 times.
✓ Branch 4 taken 147 times.
 190 if (!list_ptr->duplicates && list_contains(ptr, d))
172 2 return false;
173 188 item_s *new = m_calloc(sizeof( item_s ), sizeof( byte_t ));
174 188 new->data = d;
175
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 164 times.
 188 if (list_ptr->size == 0)
176 {
177 24 list_ptr->head = new;
178 24 list_ptr->tail = new;
179 }
180
2/2
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 149 times.
 164 else if (list_ptr->size == 1)
181 {
182 15 item_s *prev = list_ptr->head;
183
2/2
✓ Branch 1 taken 8 times.
✓ Branch 2 taken 7 times.
 15 if (list_ptr->compare(new->data, prev->data) <= 0)
184 {
185 8 list_ptr->head = new;
186 8 new->next = prev;
187 }
188 else
189 {
190 7 prev->next = new;
191 7 list_ptr->tail = new;
192 }
193 }
194 else
195 {
196 149 item_s *this = list_ptr->head;
197 149 item_s *prev = NULL;
198 149 bool added = false;
199 do
200 {
201
2/2
✓ Branch 1 taken 111 times.
✓ Branch 2 taken 1365 times.
 1476 if (list_ptr->compare(new->data, this->data) < 0)
202 {
203 111 new->next = this;
204
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 102 times.
 111 if (this == list_ptr->head)
205 9 list_ptr->head = new;
206
1/2
✓ Branch 0 taken 102 times.
✗ Branch 1 not taken.
 102 else if (prev)
207 102 prev->next = new;
208 else
209 ✗ die(_("We’ve reached an unreachable location in the code @ %s:%d:%s"), __FILE__, __LINE__, __func__);
210 111 added = true;
211 111 break;
212 }
213 1365 prev = this;
214 1365 this = this->next;
215 }
216
2/2
✓ Branch 0 taken 1327 times.
✓ Branch 1 taken 38 times.
 1365 while (this);
217
2/2
✓ Branch 0 taken 38 times.
✓ Branch 1 taken 111 times.
 149 if (!added)
218 {
219 38 prev->next = new;
220 38 list_ptr->tail = new;
221 }
222 }
223 188 list_ptr->size++;
224 188 return true;
225 }
226
227 7 extern int list_add_all(list_t ptr, list_t otr, void *c(const void *))
228 {
229 7 list_private_s *list_ptr = (list_private_s *)ptr;
230
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 6 times.
 7 if (!list_ptr)
231 1 return -1;
232 6 list_private_s *list_otr = (list_private_s *)otr;
233
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 5 times.
 6 if (!list_otr)
234 1 return -1;
235
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 4 times.
 5 if (!list_otr->size)
236 1 return 0;
237 4 int r = 0;
238 4 item_s *item = list_otr->head;
239 do
240 {
241
2/2
✓ Branch 2 taken 9 times.
✓ Branch 3 taken 1 times.
 10 if (list_append(list_ptr, c(item->data)))
242 9 r++;
243 10 item = item->next;
244 }
245
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 4 times.
 10 while (item);
246 4 return r;
247 }
248
249 354 extern const void *list_get(list_t ptr, size_t i)
250 {
251 354 list_private_s *list_ptr = (list_private_s *)ptr;
252
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 353 times.
 354 if (!list_ptr)
253 1 return NULL;
254
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 351 times.
 353 if (i >= list_ptr->size)
255 2 return NULL;
256 351 item_s *item = list_ptr->head;
257
2/2
✓ Branch 0 taken 6208 times.
✓ Branch 1 taken 351 times.
 6559 for (size_t j = 0; j < i; j++)
258 6208 item = item->next;
259 351 return item->data;
260 }
261
262 833 extern const void *list_contains(list_t ptr, const void *d)
263 {
264 293 list_private_s *list_ptr = (list_private_s *)ptr;
265
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 292 times.
 293 if (!list_ptr)
266 1 return NULL;
267
2/2
✓ Branch 0 taken 574 times.
✓ Branch 1 taken 258 times.
 832 if (!list_ptr->size)
268 50 return NULL;
269 766 item_s *item = list_ptr->head;
270 do
271 {
272
6/6
✓ Branch 0 taken 6026 times.
✓ Branch 1 taken 9 times.
✓ Branch 2 taken 6023 times.
✓ Branch 3 taken 3 times.
✓ Branch 5 taken 402 times.
✓ Branch 6 taken 5621 times.
 6035 if (item->data == d || (list_ptr->compare && !list_ptr->compare(d, item->data)))
273 411 return item->data;
274 5624 item = item->next;
275 }
276
2/2
✓ Branch 0 taken 5269 times.
✓ Branch 1 taken 355 times.
 5624 while (item);
277 211 return NULL;
278 }
279
280 13 extern const void *list_remove_item(list_t ptr, const void *d)
281 {
282 13 list_private_s *list_ptr = (list_private_s *)ptr;
283
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 12 times.
 13 if (!list_ptr)
284 1 return NULL;
285
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 11 times.
 12 if (!list_ptr->size)
286 1 return NULL;
287 11 void *data = NULL;
288 11 item_s *item = list_ptr->head;
289 11 item_s *prev = NULL;
290 do
291 {
292
6/6
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 5 times.
✓ Branch 2 taken 17 times.
✓ Branch 3 taken 3 times.
✓ Branch 5 taken 5 times.
✓ Branch 6 taken 12 times.
 25 if (item->data == d || (list_ptr->compare && !list_ptr->compare(d, item->data)))
293 {
294 10 data = (void *)item->data;
295
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 6 times.
 10 if (prev)
296 4 prev->next = item->next;
297 else
298 6 list_ptr->head = item->next;
299
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 5 times.
 10 if (item == list_ptr->tail)
300 5 list_ptr->tail = prev;
301 10 list_ptr->size--;
302 10 free(item);
303
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 6 times.
 10 item = prev ? prev->next : list_ptr->head;
304 }
305 else
306 {
307 15 prev = item;
308 15 item = item->next;
309 }
310 }
311
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 11 times.
 25 while (item);
312 11 return data;
313 }
314
315 8 extern const void *list_remove_index(list_t ptr, size_t i)
316 {
317 8 list_private_s *list_ptr = (list_private_s *)ptr;
318
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 7 times.
 8 if (!list_ptr)
319 1 return NULL;
320
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 6 times.
 7 if (i >= list_ptr->size)
321 1 return NULL;
322 6 item_s *item = list_ptr->head;
323 6 item_s *prev = NULL;
324
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 2 times.
 6 if (i == 0)
325 4 list_ptr->head = item->next;
326 else
327 {
328 2 prev = item;
329
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 2 times.
 4 for (size_t j = 0; j < i - 1; j++)
330 2 prev = prev->next;
331 2 item = prev->next;
332 2 item_s *next = item->next;
333 2 prev->next = next;
334 }
335
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 4 times.
 6 if (item == list_ptr->tail)
336
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 2 times.
 2 list_ptr->tail = i == 0 ? NULL : prev;
337 6 const void *data = item->data;
338 6 list_ptr->size--;
339 6 free(item);
340 6 return data;
341 }
342
343 68 extern iter_t list_iterator(list_t ptr)
344 {
345 68 list_private_s *list_ptr = (list_private_s *)ptr;
346
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 67 times.
 68 if (!list_ptr)
347 1 return NULL;
348 67 iterator_s *iter = m_malloc(sizeof (iterator_s));
349 67 iter->next = list_ptr->head;
350 67 return iter;
351 }
352
353 432 extern const void *list_get_next(iter_t ptr)
354 {
355 432 iterator_s *iter_ptr = (iterator_s *)ptr;
356
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 430 times.
 432 if (!iter_ptr)
357 2 return NULL;
358 430 item_s *next = iter_ptr->next;
359
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 429 times.
 430 if (!next)
360 1 return NULL;
361 429 iter_ptr->next = next->next;
362 429 return next->data;
363 }
364
365 475 extern bool list_has_next(iter_t ptr)
366 {
367 475 iterator_s *iter_ptr = (iterator_s *)ptr;
368
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 473 times.
 475 if (!iter_ptr)
369 2 return false;
370 473 return iter_ptr->next;
371 }
372
373 3 extern void list_for_each(list_t ptr, void f(const void *))
374 {
375 3 list_private_s *list_ptr = (list_private_s *)ptr;
376
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 2 times.
 3 if (!list_ptr)
377 1 return;
378
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 1 times.
 2 if (!list_ptr->size)
379 1 return;
380 1 item_s *item = list_ptr->head;
381 do
382 {
383 2 f(item->data);
384 2 item = item->next;
385 }
386
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 1 times.
 2 while (item);
387 1 return;
388 }
389
390 6 static void *list_sort_noop(const void *x)
391 {
392 6 return (void *)x;
393 }
394
395 4 extern void list_sort(list_t ptr)
396 {
397 4 list_private_s *list_ptr = (list_private_s *)ptr;
398
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 3 times.
 4 if (!list_ptr)
399 1 return;
400
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 2 times.
 3 if (!list_ptr->compare)
401 1 return;
402
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 1 times.
 2 if (!list_ptr->size)
403 1 return;
404
405 1 list_private_s *copy = list_init(list_ptr->compare, list_ptr->duplicates, true);
406 1 list_add_all(copy, list_ptr, list_sort_noop);
407
408 1 size_t z = list_ptr->size;
409
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 1 times.
 4 for (size_t i = 0; i < z; i++)
410 3 list_remove_index(list_ptr, 0);
411
412 1 list_ptr->sorted = true;
413 1 list_add_all(list_ptr, copy, list_sort_noop);
414
415 1 list_deinit(copy);
416
417 1 return;
418 }
419
420 2 extern void list_add_comparator(list_t ptr, int c(const void *, const void *))
421 {
422 2 list_private_s *list_ptr = (list_private_s *)ptr;
423
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 1 times.
 2 if (!list_ptr)
424 1 return;
425 1 list_ptr->compare = c;
426 1 return;
427 }
428
429 3 extern int list_compare_integer(const void *a, const void *b)
430 {
431 3 const int64_t *x = a;
432 3 const int64_t *y = b;
433 3 return (*x > *y) - (*x < *y);
434 }
435
436 3 extern int list_compare_decimal(const void *a, const void *b)
437 {
438 //const __float128 *x = a;
439 //const __float128 *y = b;
440 3 const long double *x = a;
441 3 const long double *y = b;
442 3 return (*x > *y) - (*x < *y);
443 }
444