cbase coverage

src/
File: src/list/private/l_base.c
Date: 2024-07-26 20:57:32
Lines:
231/231
100.0%
Functions:
26/26
100.0%
Branches:
150/150
100.0%
Line Branch Exec Source
1 #include <stdlib.h>
2 #include <stddef.h>
3 #include <stdint.h>
4 #include <stdbool.h>
5 #include <stdio.h>
6 #include <errno.h>
7
8 #include "global.h"
9 #include "list.h"
10 #include "l_internal.h"
11 #include "type.h"
12
13 /**
14 * @brief Allocates and sets up list
15 *
16 * @param type The type of structures contained in the list
17 * @param connect_destroy when the object is destroyed, should the data be
18 * @return list_t* The set up list.
19 *
20 * @warning If returns NULL, allocation failed
21 */
22 82 list_t* list_create(const type_t* type, bool connect_destroy) {
23 82 list_t* self = (list_t*)malloc(sizeof(*_self));
24 82 _type = type;
25
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 81 times.
 82 if (_type == NULL)
26 1 _type = ptr_type;
27 82 _head.next = &_tail;
28 82 _head.prev = NULL;
29 82 _head.data = NULL;
30 82 _tail.prev = &_head;
31 82 _tail.next = NULL;
32 82 _tail.data = NULL;
33 82 _iter = &_head;
34 82 _index = -1;
35 82 _size = 0;
36 82 _connect_destroy = connect_destroy;
37 82 _ordered = false;
38 82 _reversed = false;
39 82 return (list_t*)_self;
40 }
41
42 /**
43 * @brief Takes down and frees list
44 *
45 * @param self The list
46 * @return uint8_t Status code
47 * [EXIT_SUCCESS]
48 */
49 82 void list_destroy(list_t* self) {
50 82 list_clear(self);
51 82 free(_self);
52 82 }
53
54 /**
55 * @brief Creates a copy of this list
56 *
57 * @param self The list
58 * @return list_t* The copy
59 */
60 3 list_t* list_copy(const list_t* self) {
61 3 list_t* other = list_create(_type, _connect_destroy);
62 3 __list_node_t* n = &_head;
63
2/2
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 3 times.
 33 while ((n = n->next) != &_tail)
64 30 list_append(other, type_copy(_type, n->data));
65
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 2 times.
 3 if (_reversed)
66 1 list_reverse(other);
67
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 1 times.
 3 if (_ordered)
68 2 list_order(other);
69 3 return other;
70 }
71
72 /**
73 * @brief The number of items are in the list
74 *
75 * @param self The list
76 * @return size_t The number of items in the list
77 */
78 37 size_t list_size(const list_t* self) {
79 37 return _size;
80 }
81
82 /**
83 * @brief Moves the list iterator to the head
84 *
85 * @param self The list
86 * @return uint8_t Status code
87 * [EXIT_SUCCESS]
88 */
89 235 uint8_t list_head(list_t* self) {
90 235 _iter = &_head;
91 235 _index = -1;
92 235 return EXIT_SUCCESS;
93 }
94
95 /**
96 * @brief Moves the list iterator to the tail
97 *
98 * @param self The list
99 * @return uint8_t Status code
100 * [EXIT_SUCCESS]
101 */
102 1711 uint8_t list_tail(list_t* self) {
103 1711 _iter = &_tail;
104 1711 _index = _size;
105 1711 return EXIT_SUCCESS;
106 }
107
108 /**
109 * @brief Moves the list iterator to the specified index
110 *
111 * @param self The list
112 * @param index The index to go to
113 * @return uint8_t Status code
114 * [EXIT_SUCCESS, ERANGE]
115 */
116 1928 uint8_t list_goto(list_t* self, size_t index) {
117
2/2
✓ Branch 0 taken 85 times.
✓ Branch 1 taken 1843 times.
 1928 if (index >= _size)
118 85 return ERANGE;
119
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 1842 times.
 1843 if (_iter == &_head)
120 1 list_next(self, NULL);
121
2/2
✓ Branch 0 taken 47 times.
✓ Branch 1 taken 1843 times.
 1890 while (_index < index) {
122 47 list_next(self, NULL);
123 }
124
2/2
✓ Branch 0 taken 1706 times.
✓ Branch 1 taken 1843 times.
 3549 while (_index > index) {
125 1706 list_prev(self, NULL);
126 }
127 1843 return EXIT_SUCCESS;
128 }
129
130 /**
131 * @brief Retrieves the item from the list at specified index and
132 *
133 * @param self The list
134 * @param item Out pointer for the item retrieved
135 * @param index The index of item to retrieve
136 * @return uint8_t Status code
137 * [EXIT_SUCCESS, ERANGE]
138 */
139 35 uint8_t list_at(const list_t* self, list_item_t** item, size_t index) {
140 35 __list_node_t* n = _head.next;
141 35 size_t index2 = 0;
142
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 34 times.
 35 if (index >= _size)
143 1 return ERANGE;
144
145 // If the iterator is closer jump there.
146
2/2
✓ Branch 0 taken 25 times.
✓ Branch 1 taken 9 times.
 34 if (_index <= index) {
147 25 n = _iter;
148 25 index2 = _index;
149 }
150
151 // Move forward to the item
152
2/2
✓ Branch 0 taken 36 times.
✓ Branch 1 taken 34 times.
 70 while (index2++ < index)
153 36 n = n->next;
154 34 *item = n->data;
155 34 return EXIT_SUCCESS;
156 }
157
158 /**
159 * @brief Retrieves the next item from the list and
160 * @brief increments the list iterator
161 *
162 * @param self The list
163 * @param item Out pointer for the item retrieved
164 * @return uint8_t Status code
165 * [EXIT_SUCCESS, ERANGE]
166 */
167 2277 uint8_t list_next(list_t* self, list_item_t** item) {
168
2/2
✓ Branch 1 taken 125 times.
✓ Branch 2 taken 2152 times.
 2277 if (!list_has_next(self))
169 125 return ERANGE;
170 2152 _iter = _iter->next;
171 2152 _index++;
172
2/2
✓ Branch 0 taken 2042 times.
✓ Branch 1 taken 110 times.
 2152 if (item != NULL)
173 2042 *item = _iter->data;
174 2152 return EXIT_SUCCESS;
175 }
176
177 /**
178 * @brief Retrieves the previous item from the list and
179 * @brief decrements the list iterator
180 *
181 * @param self The list
182 * @param item Out pointer for the item retrieved
183 * @return uint8_t Status code
184 * [EXIT_SUCCESS, ERANGE]
185 */
186 1718 uint8_t list_prev(list_t* self, list_item_t** item) {
187
2/2
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 1717 times.
 1718 if (!list_has_prev(self))
188 1 return ERANGE;
189 1717 _iter = _iter->prev;
190 1717 _index--;
191
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 1707 times.
 1717 if (item != NULL)
192 10 *item = _iter->data;
193 1717 return EXIT_SUCCESS;
194 }
195
196 /**
197 * @brief If list has next item retrievable
198 *
199 * @param self The list
200 * @return true
201 * @return false
202 */
203 2292 bool list_has_next(const list_t* self) {
204
4/4
✓ Branch 0 taken 2287 times.
✓ Branch 1 taken 5 times.
✓ Branch 2 taken 2160 times.
✓ Branch 3 taken 127 times.
 2292 return _iter != &_tail && _iter->next != &_tail;
205 }
206
207 /**
208 * @brief If list has next item retrievable
209 *
210 * @param self The list
211 * @return true
212 * @return false
213 */
214 1721 bool list_has_prev(const list_t* self) {
215
4/4
✓ Branch 0 taken 1718 times.
✓ Branch 1 taken 3 times.
✓ Branch 2 taken 1717 times.
✓ Branch 3 taken 1 times.
 1721 return _iter != &_head && _iter->prev != &_head;
216 }
217
218 /**
219 * @brief Append an item to the end of the list
220 *
221 * @param self The list
222 * @param item The item to append
223 * @return uint8_t Status code
224 * [EXIT_SUCCESS, ENOMEM, ENOTSUP, *ERANGE]
225 * @warning Append is not allowed for ordered lists, instead use insert
226 */
227 1591 uint8_t list_append(list_t* self, list_item_t* item) {
228
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 1590 times.
 1591 if (_ordered)
229 1 return ENOTSUP;
230 1590 return list_place(self, item, _size);
231 }
232
233 /**
234 * @brief Places an item at specified index of the list
235 *
236 * @param self The list
237 * @param item The item to place
238 * @param index The index to place item at
239 * @return uint8_t Status code
240 * [EXIT_SUCCESS, ENOMEM, ENOTSUP, ERANGE]
241 * @warning Place is not allowed for ordered lists, instead use insert
242 */
243 1612 uint8_t list_place(list_t* self, list_item_t* item, size_t index) {
244
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 1611 times.
 1612 if (_ordered)
245 1 return ENOTSUP;
246 uint8_t err;
247
2/2
✓ Branch 0 taken 1600 times.
✓ Branch 1 taken 11 times.
 1611 if (index == _size) {
248 1600 list_tail(self);
249 } else {
250
2/2
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 10 times.
 11 if ((err = list_goto(self, index)))
251 1 return err;
252 }
253 1610 return __list_node_insert(self, item);
254 }
255
256 /**
257 * @brief Inserts an item into the list
258 * @note For unordered lists item is placed at iterator
259 *
260 * @param self The list
261 * @param item The item to insert
262 * @return uint8_t Status code
263 * [EXIT_SUCCESS, ERANGE, ENOMEM]
264 */
265 217 uint8_t list_insert(list_t* self, list_item_t* item) {
266
4/4
✓ Branch 0 taken 197 times.
✓ Branch 1 taken 20 times.
✓ Branch 2 taken 177 times.
✓ Branch 3 taken 20 times.
 217 if (_ordered && _size > 0) {
267 177 list_item_t* item2 = NULL;
268 177 list_head(self);
269 177 list_next(self, &item2);
270 177 while (
271
4/4
✓ Branch 0 taken 461 times.
✓ Branch 1 taken 143 times.
✓ Branch 3 taken 438 times.
✓ Branch 4 taken 23 times.
 604 (!_reversed && type_cmp(_type, item, item2) > 0) ||
272
4/4
✓ Branch 0 taken 143 times.
✓ Branch 1 taken 23 times.
✓ Branch 3 taken 76 times.
✓ Branch 4 taken 67 times.
 166 (_reversed && type_cmp(_type, item, item2) < 0)
273 ) {
274
2/2
✓ Branch 1 taken 87 times.
✓ Branch 2 taken 427 times.
 514 if (list_next(self, &item2)) {
275 87 list_tail(self);
276 87 break;
277 }
278 }
279 }
280 217 return __list_node_insert(self, item);
281 }
282
283 /**
284 * @brief Deletes all items from the list
285 *
286 * @param self The list
287 * @return uint8_t Status code
288 * [EXIT_SUCCESS, *ERANGE]
289 */
290 84 uint8_t list_clear(list_t* self) {
291
2/2
✓ Branch 1 taken 1804 times.
✓ Branch 2 taken 84 times.
 1888 while (!list_delete(self, 0));
292 84 return EXIT_SUCCESS;
293 }
294
295 /**
296 * @brief Delete item a specified index from the list
297 *
298 * @param self The list
299 * @param index The index of the item to delete
300 * @return uint8_t Status code
301 * [EXIT_SUCCESS, ERANGE]
302 */
303 1898 uint8_t list_delete(list_t* self, size_t index) {
304 uint8_t err;
305
2/2
✓ Branch 1 taken 84 times.
✓ Branch 2 taken 1814 times.
 1898 if ((err = list_goto(self, index)))
306 84 return err;
307 1814 return __list_node_delete(self, _iter);
308 }
309
310 /**
311 * @brief Removes first instance of item from the list
312 *
313 * @param self The list
314 * @param item The item to remove from the list
315 * @return uint8_t Status code
316 * [EXIT_SUCCESS, ENOENT, *ERANGE]
317 */
318 6 uint8_t list_remove(list_t* self, const list_item_t* item) {
319 list_item_t* item2;
320 6 list_head(self);
321
2/2
✓ Branch 1 taken 39 times.
✓ Branch 2 taken 1 times.
 46 while (!list_next(self, &item2)) {
322
2/2
✓ Branch 1 taken 3 times.
✓ Branch 2 taken 36 times.
 39 if (!type_cmp(_type, item, item2)) {
323 3 __list_node_delete(self, _iter);
324 3 return EXIT_SUCCESS;
325 36 } else if (
326
2/2
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 21 times.
 36 _ordered &&
327
4/4
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 17 times.
✓ Branch 3 taken 3 times.
✓ Branch 4 taken 1 times.
 21 ((!_reversed && type_cmp(_type, item, item2) < 0) ||
328
4/4
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 17 times.
✓ Branch 3 taken 16 times.
✓ Branch 4 taken 1 times.
 20 (_reversed && type_cmp(_type, item, item2) > 0))
329 ) {
330 break;
331 }
332 }
333 3 return ENOENT;
334 }
335
336 /**
337 * @brief Removes all instances of item from the list
338 *
339 * @param self The list
340 * @param item The item to remove from the list
341 * @return uint8_t Status code
342 * [EXIT_SUCCESS, ENOENT, *ERANGE]
343 */
344 7 uint8_t list_purge(list_t* self, const list_item_t* item) {
345 7 bool found = false;
346 7 list_head(self);
347
2/2
✓ Branch 1 taken 52 times.
✓ Branch 2 taken 4 times.
 56 while (!list_next(self, NULL)) {
348
4/4
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 2 times.
✓ Branch 3 taken 10 times.
✓ Branch 4 taken 50 times.
 62 while (_iter != &_tail && !type_cmp(_type, item, _iter->data)) {
349 10 __list_node_delete(self, _iter);
350 10 found = true;
351 }
352 52 if (
353
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 20 times.
 52 _ordered &&
354
4/4
✓ Branch 0 taken 17 times.
✓ Branch 1 taken 15 times.
✓ Branch 3 taken 15 times.
✓ Branch 4 taken 2 times.
 32 ((!_reversed && type_cmp(_type, item, _iter->data) < 0) ||
355
4/4
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 15 times.
✓ Branch 3 taken 14 times.
✓ Branch 4 taken 1 times.
 30 (_reversed && type_cmp(_type, item, _iter->data) > 0))
356 ) {
357 break;
358 }
359 }
360
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 5 times.
 7 if (!found)
361 2 return ENOENT;
362 5 return EXIT_SUCCESS;
363 }
364
365 /**
366 * @brief Reverses the order of the items in the list
367 *
368 * @param self The list
369 * @return uint8_t Status code
370 * [EXIT_SUCCESS]
371 */
372 11 uint8_t list_reverse(list_t* self) {
373 11 __list_node_t* n1 = &_head;
374 11 __list_node_t* n2 = &_tail;
375
4/4
✓ Branch 0 taken 35 times.
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 25 times.
✓ Branch 3 taken 10 times.
 36 while (n1 != n2 && n2->next != n1) {
376 list_item_t* temp;
377 25 temp = n1->data;
378 25 n1->data = n2->data;
379 25 n2->data = temp;
380 25 n1 = n1->next;
381 25 n2 = n2->prev;
382 }
383 11 _reversed = !_reversed;
384 11 return EXIT_SUCCESS;
385 }
386
387 /**
388 * @brief Orders the items of the list and redefines the list as ordered
389 *
390 * @param self The list
391 * @return uint8_t Status code
392 * [EXIT_SUCCESS]
393 */
394 25 uint8_t list_order(list_t* self) {
395 25 _ordered = true;
396 25 __list_node_t* n = &_head;
397
4/4
✓ Branch 0 taken 140 times.
✓ Branch 1 taken 22 times.
✓ Branch 2 taken 137 times.
✓ Branch 3 taken 3 times.
 162 while ((n = n->next) != &_tail && n->next != &_tail) {
398 137 if (
399
4/4
✓ Branch 0 taken 81 times.
✓ Branch 1 taken 56 times.
✓ Branch 3 taken 36 times.
✓ Branch 4 taken 45 times.
 137 (_reversed && type_cmp(_type, n->data, n->next->data) < 0) ||
400
4/4
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 36 times.
✓ Branch 3 taken 21 times.
✓ Branch 4 taken 35 times.
 92 (!_reversed && type_cmp(_type, n->data, n->next->data) > 0)
401 ) {
402 66 void* tmp = n->data;
403 66 n->data = n->next->data;
404 66 n->next->data = tmp;
405
2/2
✓ Branch 0 taken 55 times.
✓ Branch 1 taken 11 times.
 66 if (n->prev != &_head)
406 55 n = n->prev->prev;
407 }
408 }
409 25 return EXIT_SUCCESS;
410 }
411
412 /**
413 * @brief Redefine the current list as unordered
414 *
415 * @param self The list
416 * @return uint8_t Status code
417 * [EXIT_SUCCESS]
418 */
419 1 uint8_t list_unorder(list_t* self) {
420 1 _ordered = false;
421 1 return EXIT_SUCCESS;
422 }
423
424 /**
425 * @brief Finds the index of the first instance of specified item in the list
426 *
427 * @param self The list
428 * @param index Out pointer for the index
429 * @param item the item to find
430 * @return uint8_t Status code
431 * [EXIT_SUCCESS, ENOENT]
432 */
433 41 uint8_t list_indexof(
434 const list_t* self,
435 size_t* index,
436 const list_item_t* item
437 ) {
438 41 __list_node_t* n = &_head;
439 41 size_t index2 = 0;
440
2/2
✓ Branch 0 taken 219 times.
✓ Branch 1 taken 3 times.
 222 while ((n = n->next) != &_tail) {
441
2/2
✓ Branch 1 taken 36 times.
✓ Branch 2 taken 183 times.
 219 if (!type_cmp(_type, item, n->data)) {
442
2/2
✓ Branch 0 taken 27 times.
✓ Branch 1 taken 9 times.
 36 if (index != NULL)
443 27 *index = index2;
444 36 return EXIT_SUCCESS;
445 183 } else if (
446
2/2
✓ Branch 0 taken 174 times.
✓ Branch 1 taken 9 times.
 183 _ordered &&
447
4/4
✓ Branch 0 taken 124 times.
✓ Branch 1 taken 50 times.
✓ Branch 3 taken 123 times.
✓ Branch 4 taken 1 times.
 174 ((!_reversed && type_cmp(_type, item, n->data) < 0) ||
448
4/4
✓ Branch 0 taken 50 times.
✓ Branch 1 taken 123 times.
✓ Branch 3 taken 49 times.
✓ Branch 4 taken 1 times.
 173 (_reversed && type_cmp(_type, item, n->data) > 0))
449 ) {
450 break;
451 }
452 181 index2++;
453 }
454 5 return ENOENT;
455 }
456
457 /**
458 * @brief If the list contains the specified item
459 *
460 * @param self The list
461 * @param item The item to check for
462 * @return true
463 * @return false
464 */
465 10 bool list_contains(const list_t* self, const list_item_t* item) {
466 10 return list_indexof(self, NULL, item) == EXIT_SUCCESS;
467 }
468
469 /**
470 * @brief Compares two lists
471 *
472 * @param self The list
473 * @param other The list to compare to
474 * @return int
475 * >0: self > other
476 * <0: self < other
477 * =0: self = other
478 */
479 9 int list_cmp(const list_t* self, const list_t* other) {
480 9 __list_node_t* n1 = &_head;
481 9 __list_node_t* n2 = &(((__list_t*)other)->head);
482 9 int cmp = 0;
483 9 const type_t* type = _type;
484
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 8 times.
 9 if (type != (((__list_t*)other)->type))
485 1 type = ptr_type;
486 9 while (
487 117 (n1 = n1->next) != &_tail &&
488
6/6
✓ Branch 0 taken 57 times.
✓ Branch 1 taken 3 times.
✓ Branch 2 taken 56 times.
✓ Branch 3 taken 1 times.
✓ Branch 4 taken 51 times.
✓ Branch 5 taken 5 times.
 116 (n2 = n2->next) != &(((__list_t*)other)->tail) &&
489 56 !(cmp = type_cmp(type, n1->data, n2->data))
490 );
491
4/4
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 6 times.
✓ Branch 2 taken 1 times.
✓ Branch 3 taken 2 times.
 9 if (n1 == &_tail && n2->next != &(((__list_t*)other)->tail))
492 1 cmp = -1;
493
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 7 times.
 8 else if (n2 == &(((__list_t*)other)->tail))
494 1 cmp = 1;
495 9 return cmp;
496 }
497
498 /**
499 * @brief Returns the type with this list
500 *
501 * @param self The list
502 * @return const type_t* The type with this list
503 */
504 2 const type_t* list_typeof(const list_t* self) {
505 2 return _type;
506 }
507
508 /**
509 * @brief Inserts item node at the current iterator location
510 *
511 * @param self The list
512 * @param item The item to insert
513 * @return uint8_t Status code
514 * [EXIT_SUCCESS, ENOMEM]
515 */
516 1827 uint8_t __list_node_insert(list_t* self, list_item_t* item) {
517 1827 __list_node_t* n = (__list_node_t*)malloc(sizeof(*n));
518
2/2
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 1797 times.
 1827 if (_iter == &_head) {
519
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 21 times.
 30 if (_size > 0)
520 9 list_next(self, NULL);
521 else
522 21 list_tail(self);
523 }
524 1827 n->data = item;
525 1827 n->next = _iter;
526 1827 n->prev = _iter->prev;
527 1827 n->next->prev = n;
528 1827 n->prev->next = n;
529 1827 _iter = n;
530 1827 _size++;
531 1827 return EXIT_SUCCESS;
532 }
533
534 /**
535 * @brief Deletes specified node from the list
536 *
537 * @param self The list
538 * @param n The node to delete
539 * @return uint8_t Status code
540 * [EXIT_SUCCESS]
541 */
542 1827 uint8_t __list_node_delete(list_t* self, __list_node_t* n) {
543 1827 n->prev->next = n->next;
544 1827 n->next->prev = n->prev;
545 1827 _size--;
546 1827 _iter = n->next;
547
2/2
✓ Branch 0 taken 1611 times.
✓ Branch 1 taken 216 times.
 1827 if (_connect_destroy)
548 1611 type_destroy(_type, n->data);
549 1827 free(n);
550 1827 return EXIT_SUCCESS;
551 }
552
553 /**
554 * @brief Prints the list to stdout
555 *
556 * @param f The file to write to
557 * @param self The list
558 */
559 1 void __list_print(FILE* f, const list_t* self) {
560 1 rope_t* rope = type_repr(list_type, self);
561 1 char* str = rope_str(rope);
562 1 fprintf(f, "%s\n", str);
563 1 free(str);
564 1 rope_destroy(rope);
565 1 }
566