Sat, 16 Apr 2022 20:17:01 +0200
improve testing allocator + add tests for it
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 */
29 #include "cx/linked_list.h"
30 #include "cx/utils.h"
31 #include <stdint.h>
32 #include <string.h>
33 #include <assert.h>
35 /* LOW LEVEL LINKED LIST FUNCTIONS */
37 #define CX_LL_PTR(cur, off) (*(void**)(((char*)cur)+off))
38 #define ll_prev(node) CX_LL_PTR(node, loc_prev)
39 #define ll_next(node) CX_LL_PTR(node, loc_next)
40 #define ll_advance(node) CX_LL_PTR(node, loc_advance)
41 #define ll_data(node) (follow_ptr?CX_LL_PTR(node, loc_data):(((char*)node)+loc_data))
43 void *cx_linked_list_at(
44 void const *start,
45 size_t start_index,
46 ptrdiff_t loc_advance,
47 size_t index
48 ) {
49 assert(start != NULL);
50 assert(loc_advance >= 0);
51 size_t i = start_index;
52 void const *cur = start;
53 while (i != index && cur != NULL) {
54 cur = ll_advance(cur);
55 i < index ? i++ : i--;
56 }
57 return (void *) cur;
58 }
60 size_t cx_linked_list_find(
61 void const *start,
62 ptrdiff_t loc_advance,
63 ptrdiff_t loc_data,
64 bool follow_ptr,
65 CxListComparator cmp_func,
66 void const *elem
67 ) {
68 assert(start != NULL);
69 assert(loc_advance >= 0);
70 assert(loc_data >= 0);
71 assert(cmp_func);
73 void const *node = start;
74 size_t index = 0;
75 do {
76 void *current = ll_data(node);
77 if (cmp_func(current, elem) == 0) {
78 return index;
79 }
80 node = ll_advance(node);
81 index++;
82 } while (node != NULL);
83 return index;
84 }
86 void *cx_linked_list_first(
87 void const *node,
88 ptrdiff_t loc_prev
89 ) {
90 return cx_linked_list_last(node, loc_prev);
91 }
93 void *cx_linked_list_last(
94 void const *node,
95 ptrdiff_t loc_next
96 ) {
97 assert(node != NULL);
98 assert(loc_next >= 0);
100 void const *cur = node;
101 void const *last;
102 do {
103 last = cur;
104 } while ((cur = ll_next(cur)) != NULL);
106 return (void *) last;
107 }
109 void *cx_linked_list_prev(
110 void const *begin,
111 ptrdiff_t loc_next,
112 void const *node
113 ) {
114 assert(begin != NULL);
115 assert(node != NULL);
116 assert(loc_next >= 0);
117 if (begin == node) return NULL;
118 void const *cur = begin;
119 void const *next;
120 while (1) {
121 next = ll_next(cur);
122 if (next == node) return (void *) cur;
123 cur = next;
124 }
125 }
127 void cx_linked_list_link(
128 void *left,
129 void *right,
130 ptrdiff_t loc_prev,
131 ptrdiff_t loc_next
132 ) {
133 assert(loc_next >= 0);
134 ll_next(left) = right;
135 if (loc_prev >= 0) {
136 ll_prev(right) = left;
137 }
138 }
140 void cx_linked_list_unlink(
141 void *left,
142 void *right,
143 ptrdiff_t loc_prev,
144 ptrdiff_t loc_next
145 ) {
146 assert (loc_next >= 0);
147 assert(ll_next(left) == right);
148 ll_next(left) = NULL;
149 if (loc_prev >= 0) {
150 assert(ll_prev(right) == left);
151 ll_prev(right) = NULL;
152 }
153 }
155 void cx_linked_list_add(
156 void **begin,
157 void **end,
158 ptrdiff_t loc_prev,
159 ptrdiff_t loc_next,
160 void *new_node
161 ) {
162 void *last;
163 if (end == NULL) {
164 assert(begin != NULL);
165 last = *begin == NULL ? NULL : cx_linked_list_last(*begin, loc_next);
166 } else {
167 last = *end;
168 }
169 cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, last, new_node, new_node);
170 }
172 void cx_linked_list_prepend(
173 void **begin,
174 void **end,
175 ptrdiff_t loc_prev,
176 ptrdiff_t loc_next,
177 void *new_node
178 ) {
179 cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, NULL, new_node, new_node);
180 }
182 void cx_linked_list_insert(
183 void **begin,
184 void **end,
185 ptrdiff_t loc_prev,
186 ptrdiff_t loc_next,
187 void *node,
188 void *new_node
189 ) {
190 cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, node, new_node, new_node);
191 }
193 void cx_linked_list_insert_chain(
194 void **begin,
195 void **end,
196 ptrdiff_t loc_prev,
197 ptrdiff_t loc_next,
198 void *node,
199 void *insert_begin,
200 void *insert_end
201 ) {
202 // find the end of the chain, if not specified
203 if (insert_end == NULL) {
204 insert_end = cx_linked_list_last(insert_begin, loc_next);
205 }
207 // determine the successor
208 void *successor;
209 if (node == NULL) {
210 assert(begin != NULL || (end != NULL && loc_prev >= 0));
211 if (begin != NULL) {
212 successor = *begin;
213 *begin = insert_begin;
214 } else {
215 successor = *end == NULL ? NULL : cx_linked_list_first(*end, loc_prev);
216 }
217 } else {
218 successor = ll_next(node);
219 cx_linked_list_link(node, insert_begin, loc_prev, loc_next);
220 }
222 if (successor == NULL) {
223 // the list ends with the new chain
224 if (end != NULL) {
225 *end = insert_end;
226 }
227 } else {
228 cx_linked_list_link(insert_end, successor, loc_prev, loc_next);
229 }
230 }
232 void cx_linked_list_remove(
233 void **begin,
234 void **end,
235 ptrdiff_t loc_prev,
236 ptrdiff_t loc_next,
237 void *node
238 ) {
239 assert(node != NULL);
240 assert(loc_next >= 0);
241 assert(loc_prev >= 0 || begin != NULL);
243 // find adjacent nodes
244 void *next = ll_next(node);
245 void *prev;
246 if (loc_prev >= 0) {
247 prev = ll_prev(node);
248 } else {
249 prev = cx_linked_list_prev(*begin, loc_next, node);
250 }
252 // update next pointer of prev node, or set begin
253 if (prev == NULL) {
254 if (begin != NULL) {
255 *begin = next;
256 }
257 } else {
258 ll_next(prev) = next;
259 }
261 // update prev pointer of next node, or set end
262 if (next == NULL) {
263 if (end != NULL) {
264 *end = prev;
265 }
266 } else if (loc_prev >= 0) {
267 ll_prev(next) = prev;
268 }
269 }
271 size_t cx_linked_list_size(
272 void const *node,
273 ptrdiff_t loc_next
274 ) {
275 assert(loc_next >= 0);
276 size_t size = 0;
277 while (node != NULL) {
278 node = ll_next(node);
279 size++;
280 }
281 return size;
282 }
284 static void *cx_linked_list_sort_merge(
285 ptrdiff_t loc_prev,
286 ptrdiff_t loc_next,
287 ptrdiff_t loc_data,
288 bool follow_ptr,
289 size_t length,
290 void *ls,
291 void *le,
292 void *re,
293 CxListComparator cmp_func
294 ) {
295 const size_t sbo_len = 1024;
296 void *sbo[sbo_len];
297 void **sorted = (length >= sbo_len) ? malloc(sizeof(void *) * length) : sbo;
298 if (sorted == NULL) abort();
299 void *rc, *lc;
301 lc = ls;
302 rc = le;
303 size_t n = 0;
304 while (lc && lc != le && rc != re) {
305 if (cmp_func(ll_data(lc), ll_data(rc)) <= 0) {
306 sorted[n] = lc;
307 lc = ll_next(lc);
308 } else {
309 sorted[n] = rc;
310 rc = ll_next(rc);
311 }
312 n++;
313 }
314 while (lc && lc != le) {
315 sorted[n] = lc;
316 lc = ll_next(lc);
317 n++;
318 }
319 while (rc && rc != re) {
320 sorted[n] = rc;
321 rc = ll_next(rc);
322 n++;
323 }
325 // Update pointer
326 if (loc_prev >= 0) ll_prev(sorted[0]) = NULL;
327 cx_for_n (i, length - 1) {
328 cx_linked_list_link(sorted[i], sorted[i + 1], loc_prev, loc_next);
329 }
330 ll_next(sorted[length - 1]) = NULL;
332 void *ret = sorted[0];
333 if (sorted != sbo) {
334 free(sorted);
335 }
336 return ret;
337 }
339 void cx_linked_list_sort( /* NOLINT(misc-no-recursion) - purposely recursive function */
340 void **begin,
341 void **end,
342 ptrdiff_t loc_prev,
343 ptrdiff_t loc_next,
344 ptrdiff_t loc_data,
345 bool follow_ptr,
346 CxListComparator cmp_func
347 ) {
348 assert(begin != NULL);
349 assert(loc_next >= 0);
350 assert(loc_data >= 0);
351 assert(cmp_func);
353 void *lc, *ls, *le, *re;
355 // set start node
356 ls = *begin;
358 // check how many elements are already sorted
359 lc = ls;
360 size_t ln = 1;
361 while (ll_next(lc) != NULL && cmp_func(ll_data(ll_next(lc)), ll_data(lc)) > 0) {
362 lc = ll_next(lc);
363 ln++;
364 }
365 le = ll_next(lc);
367 // if first unsorted node is NULL, the list is already completely sorted
368 if (le != NULL) {
369 void *rc;
370 size_t rn = 1;
371 rc = le;
372 // skip already sorted elements
373 while (ll_next(rc) != NULL && cmp_func(ll_data(ll_next(rc)), ll_data(rc)) > 0) {
374 rc = ll_next(rc);
375 rn++;
376 }
377 re = ll_next(rc);
379 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
380 void *sorted = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, follow_ptr,
381 ln + rn, ls, le, re, cmp_func);
383 // Something left? Sort it!
384 size_t remainder_length = cx_linked_list_size(re, loc_next);
385 if (remainder_length > 0) {
386 void *remainder = re;
387 cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, follow_ptr, cmp_func);
389 // merge sorted list with (also sorted) remainder
390 *begin = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, follow_ptr,
391 ln + rn + remainder_length,
392 sorted, remainder, NULL, cmp_func);
393 } else {
394 // no remainder - we've got our sorted list
395 *begin = sorted;
396 }
397 if (end) *end = cx_linked_list_last(sorted, loc_next);
398 }
399 }
401 int cx_linked_list_compare(
402 void const *begin_left,
403 void const *begin_right,
404 ptrdiff_t loc_advance,
405 ptrdiff_t loc_data,
406 bool follow_ptr,
407 CxListComparator cmp_func
408 ) {
409 void const *left = begin_left, *right = begin_right;
411 while (left != NULL && right != NULL) {
412 int result = cmp_func(ll_data(left), ll_data(right));
413 if (result != 0) return result;
414 left = ll_advance(left);
415 right = ll_advance(right);
416 }
418 if (left != NULL) { return 1; }
419 else if (right != NULL) { return -1; }
420 else { return 0; }
421 }
423 void cx_linked_list_reverse(
424 void **begin,
425 void **end,
426 ptrdiff_t loc_prev,
427 ptrdiff_t loc_next
428 ) {
429 assert(begin != NULL);
430 assert(loc_next >= 0);
432 // swap all links
433 void *prev = NULL;
434 void *cur = *begin;
435 while (cur != NULL) {
436 void *next = ll_next(cur);
438 ll_next(cur) = prev;
439 if (loc_prev >= 0) {
440 ll_prev(cur) = next;
441 }
443 prev = cur;
444 cur = next;
445 }
447 // update begin and end
448 if (end != NULL) {
449 *end = *begin;
450 }
451 *begin = prev;
452 }
454 /* HIGH LEVEL LINKED LIST IMPLEMENTATION */
456 typedef struct cx_linked_list_node cx_linked_list_node;
457 struct cx_linked_list_node {
458 cx_linked_list_node *prev;
459 cx_linked_list_node *next;
460 char payload[];
461 };
463 #define CX_LL_LOC_PREV offsetof(cx_linked_list_node, prev)
464 #define CX_LL_LOC_NEXT offsetof(cx_linked_list_node, next)
465 #define CX_LL_LOC_DATA offsetof(cx_linked_list_node, payload)
467 typedef struct {
468 struct cx_list_s base;
469 cx_linked_list_node *begin;
470 cx_linked_list_node *end;
471 } cx_linked_list;
473 static cx_linked_list_node *cx_ll_node_at(
474 cx_linked_list const *list,
475 size_t index
476 ) {
477 if (index >= list->base.size) {
478 return NULL;
479 } else if (index > list->base.size / 2) {
480 return cx_linked_list_at(list->end, list->base.size - 1, CX_LL_LOC_PREV, index);
481 } else {
482 return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index);
483 }
484 }
486 static int cx_ll_insert_at(
487 struct cx_list_s *list,
488 cx_linked_list_node *node,
489 void const *elem
490 ) {
492 // create the new new_node
493 cx_linked_list_node *new_node = cxMalloc(list->allocator,
494 sizeof(cx_linked_list_node) + list->itemsize);
496 // sortir if failed
497 if (new_node == NULL) return 1;
499 // initialize new new_node
500 new_node->prev = new_node->next = NULL;
501 memcpy(new_node->payload, elem, list->itemsize);
503 // insert
504 cx_linked_list *ll = (cx_linked_list *) list;
505 cx_linked_list_insert_chain(
506 (void **) &ll->begin, (void **) &ll->end,
507 CX_LL_LOC_PREV, CX_LL_LOC_NEXT,
508 node, new_node, new_node
509 );
511 // increase the size and return
512 list->size++;
513 return 0;
514 }
516 static int cx_ll_insert(
517 struct cx_list_s *list,
518 size_t index,
519 void const *elem
520 ) {
521 // out-of bounds check
522 if (index > list->size) return 1;
524 // find position efficiently
525 cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1);
527 // perform insert
528 return cx_ll_insert_at(list, node, elem);
529 }
531 static int cx_ll_add(
532 struct cx_list_s *list,
533 void const *elem
534 ) {
535 return cx_ll_insert(list, list->size, elem);
536 }
538 static int cx_pll_insert(
539 struct cx_list_s *list,
540 size_t index,
541 void const *elem
542 ) {
543 return cx_ll_insert(list, index, &elem);
544 }
546 static int cx_pll_add(
547 struct cx_list_s *list,
548 void const *elem
549 ) {
550 return cx_ll_insert(list, list->size, &elem);
551 }
553 static int cx_ll_remove(
554 struct cx_list_s *list,
555 size_t index
556 ) {
557 cx_linked_list *ll = (cx_linked_list *) list;
558 cx_linked_list_node *node = cx_ll_node_at(ll, index);
560 // out-of-bounds check
561 if (node == NULL) return 1;
563 // remove
564 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
565 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
567 // adjust size
568 list->size--;
570 // free and return
571 cxFree(list->allocator, node);
573 return 0;
574 }
576 static void *cx_ll_at(
577 struct cx_list_s const *list,
578 size_t index
579 ) {
580 cx_linked_list *ll = (cx_linked_list *) list;
581 cx_linked_list_node *node = cx_ll_node_at(ll, index);
582 return node == NULL ? NULL : node->payload;
583 }
585 static void *cx_pll_at(
586 struct cx_list_s const *list,
587 size_t index
588 ) {
589 cx_linked_list *ll = (cx_linked_list *) list;
590 cx_linked_list_node *node = cx_ll_node_at(ll, index);
591 return node == NULL ? NULL : *(void **) node->payload;
592 }
594 static size_t cx_ll_find(
595 struct cx_list_s const *list,
596 void const *elem
597 ) {
598 return cx_linked_list_find(((cx_linked_list *) list)->begin,
599 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
600 false, list->cmpfunc, elem);
601 }
603 static size_t cx_pll_find(
604 struct cx_list_s const *list,
605 void const *elem
606 ) {
607 return cx_linked_list_find(((cx_linked_list *) list)->begin,
608 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
609 true, list->cmpfunc, elem);
610 }
612 static void cx_ll_sort(struct cx_list_s *list) {
613 cx_linked_list *ll = (cx_linked_list *) list;
614 cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end,
615 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
616 false, list->cmpfunc);
617 }
619 static void cx_pll_sort(struct cx_list_s *list) {
620 cx_linked_list *ll = (cx_linked_list *) list;
621 cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end,
622 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
623 true, list->cmpfunc);
624 }
626 static void cx_ll_reverse(struct cx_list_s *list) {
627 cx_linked_list *ll = (cx_linked_list *) list;
628 cx_linked_list_reverse((void **) &ll->begin, (void **) ll->end, CX_LL_LOC_PREV, CX_LL_LOC_NEXT);
629 }
631 static int cx_ll_compare(
632 struct cx_list_s const *list,
633 struct cx_list_s const *other
634 ) {
635 cx_linked_list *left = (cx_linked_list *) list;
636 cx_linked_list *right = (cx_linked_list *) other;
637 return cx_linked_list_compare(left->begin, right->begin,
638 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
639 false, list->cmpfunc);
640 }
642 static int cx_pll_compare(
643 struct cx_list_s const *list,
644 struct cx_list_s const *other
645 ) {
646 cx_linked_list *left = (cx_linked_list *) list;
647 cx_linked_list *right = (cx_linked_list *) other;
648 return cx_linked_list_compare(left->begin, right->begin,
649 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
650 true, list->cmpfunc);
651 }
653 static bool cx_ll_iter_valid(CxIterator const *iter) {
654 return iter->elem_handle != NULL;
655 }
657 static void cx_ll_iter_next(CxIterator *iter) {
658 if (iter->remove) {
659 iter->remove = false;
660 cx_linked_list *ll = iter->src_handle;
661 cx_linked_list_node *node = iter->elem_handle;
662 iter->elem_handle = node->next;
663 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
664 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
665 ll->base.size--;
666 cxFree(ll->base.allocator, node);
667 } else {
668 iter->index++;
669 cx_linked_list_node *node = iter->elem_handle;
670 iter->elem_handle = node->next;
671 }
672 }
674 static void *cx_ll_iter_current(CxIterator const *iter) {
675 cx_linked_list_node *node = iter->elem_handle;
676 return node->payload;
677 }
679 static void *cx_pll_iter_current(CxIterator const *iter) {
680 cx_linked_list_node *node = iter->elem_handle;
681 return *(void **) node->payload;
682 }
684 static CxIterator cx_ll_iterator(
685 struct cx_list_s *list,
686 size_t index
687 ) {
688 CxIterator iter;
689 iter.index = index;
690 iter.src_handle = list;
691 iter.elem_handle = cx_ll_node_at((cx_linked_list const *) list, index);
692 iter.valid = cx_ll_iter_valid;
693 iter.current = cx_ll_iter_current;
694 iter.next = cx_ll_iter_next;
695 iter.remove = false;
696 return iter;
697 }
699 static CxIterator cx_pll_iterator(
700 struct cx_list_s *list,
701 size_t index
702 ) {
703 CxIterator iter = cx_ll_iterator(list, index);
704 iter.current = cx_pll_iter_current;
705 return iter;
706 }
708 static int cx_ll_insert_iter(
709 CxIterator *iter,
710 void const *elem,
711 int prepend
712 ) {
713 struct cx_list_s *list = iter->src_handle;
714 cx_linked_list_node *node = iter->elem_handle;
715 if (node != NULL) {
716 assert(prepend >= 0 && prepend <= 1);
717 cx_linked_list_node *choice[2] = {node, node->prev};
718 int result = cx_ll_insert_at(list, choice[prepend], elem);
719 iter->index += prepend * (0 == result);
720 return result;
721 } else {
722 int result = cx_ll_insert(list, list->size, elem);
723 iter->index = list->size;
724 return result;
725 }
726 }
728 static int cx_pll_insert_iter(
729 CxIterator *iter,
730 void const *elem,
731 int prepend
732 ) {
733 return cx_ll_insert_iter(iter, &elem, prepend);
734 }
736 static cx_list_class cx_linked_list_class = {
737 cx_ll_add,
738 cx_ll_insert,
739 cx_ll_insert_iter,
740 cx_ll_remove,
741 cx_ll_at,
742 cx_ll_find,
743 cx_ll_sort,
744 cx_ll_compare,
745 cx_ll_reverse,
746 cx_ll_iterator
747 };
749 static cx_list_class cx_pointer_linked_list_class = {
750 cx_pll_add,
751 cx_pll_insert,
752 cx_pll_insert_iter,
753 cx_ll_remove,
754 cx_pll_at,
755 cx_pll_find,
756 cx_pll_sort,
757 cx_pll_compare,
758 cx_ll_reverse,
759 cx_pll_iterator,
760 };
762 static CxList *cx_ll_default_destructor(CxList *list) {
763 cx_linked_list *ll = (cx_linked_list *) list;
765 cx_linked_list_node *node = ll->begin;
766 while (node) {
767 void *next = node->next;
768 cxFree(list->allocator, node);
769 node = next;
770 }
772 cxFree(list->allocator, list);
773 return NULL;
774 }
776 CxList *cxLinkedListCreate(
777 CxAllocator const *allocator,
778 CxListComparator comparator,
779 size_t item_size
780 ) {
781 cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list));
782 if (list == NULL)
783 return NULL;
785 list->base.cl = &cx_linked_list_class;
786 list->base.allocator = allocator;
787 list->base.list_destructor = (cx_destructor_func) cx_ll_default_destructor;
788 list->base.cmpfunc = comparator;
789 list->base.itemsize = item_size;
790 list->base.capacity = SIZE_MAX;
792 return (CxList *) list;
793 }
795 CxList *cxPointerLinkedListCreate(
796 CxAllocator const *allocator,
797 CxListComparator comparator
798 ) {
799 cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list));
800 if (list == NULL)
801 return NULL;
803 list->base.cl = &cx_pointer_linked_list_class;
804 list->base.allocator = allocator;
805 list->base.list_destructor = (cx_destructor_func) cx_ll_default_destructor;
806 list->base.cmpfunc = comparator;
807 list->base.itemsize = sizeof(void *);
808 list->base.capacity = SIZE_MAX;
810 return (CxList *) list;
811 }
813 CxList *cxLinkedListFromArray(
814 CxAllocator const *allocator,
815 CxListComparator comparator,
816 size_t item_size,
817 size_t num_items,
818 void const *array
819 ) {
820 CxList *list = cxLinkedListCreate(allocator, comparator, item_size);
821 if (list == NULL) return NULL;
822 cx_for_n (i, num_items) {
823 if (0 != cxListAdd(list, ((const unsigned char *) array) + i * item_size)) {
824 return cx_ll_default_destructor(list);
825 }
826 }
827 return list;
828 }