Mercurial > hg > toolkit / file comparison

comparison: ucx/linked_list.c

ucx/linked_list.c

changeset 431
bb7da585debc
parent 324
ce13a778654a
child 440
7c4b9cba09ca
equal deleted inserted replaced
169:fe49cff3c571 431:bb7da585debc
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/linked_list.h"
30 #include "cx/utils.h"
31 #include "cx/compare.h"
32 #include <string.h>
33 #include <assert.h>
34
35 // LOW LEVEL LINKED LIST FUNCTIONS
36
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) (((char*)(node))+loc_data)
42
43 void *cx_linked_list_at(
44 const void *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 const void *cur = start;
53 while (i != index && cur != NULL) {
54 cur = ll_advance(cur);
55 i < index ? i++ : i--;
56 }
57 return (void *) cur;
58 }
59
60 ssize_t cx_linked_list_find(
61 const void *start,
62 ptrdiff_t loc_advance,
63 ptrdiff_t loc_data,
64 cx_compare_func cmp_func,
65 const void *elem
66 ) {
67 void *dummy;
68 return cx_linked_list_find_node(
69 &dummy, start,
70 loc_advance, loc_data,
71 cmp_func, elem
72 );
73 }
74
75 ssize_t cx_linked_list_find_node(
76 void **result,
77 const void *start,
78 ptrdiff_t loc_advance,
79 ptrdiff_t loc_data,
80 cx_compare_func cmp_func,
81 const void *elem
82 ) {
83 assert(result != NULL);
84 assert(start != NULL);
85 assert(loc_advance >= 0);
86 assert(loc_data >= 0);
87 assert(cmp_func);
88
89 const void *node = start;
90 ssize_t index = 0;
91 do {
92 void *current = ll_data(node);
93 if (cmp_func(current, elem) == 0) {
94 *result = (void*) node;
95 return index;
96 }
97 node = ll_advance(node);
98 index++;
99 } while (node != NULL);
100 *result = NULL;
101 return -1;
102 }
103
104 void *cx_linked_list_first(
105 const void *node,
106 ptrdiff_t loc_prev
107 ) {
108 return cx_linked_list_last(node, loc_prev);
109 }
110
111 void *cx_linked_list_last(
112 const void *node,
113 ptrdiff_t loc_next
114 ) {
115 assert(node != NULL);
116 assert(loc_next >= 0);
117
118 const void *cur = node;
119 const void *last;
120 do {
121 last = cur;
122 } while ((cur = ll_next(cur)) != NULL);
123
124 return (void *) last;
125 }
126
127 void *cx_linked_list_prev(
128 const void *begin,
129 ptrdiff_t loc_next,
130 const void *node
131 ) {
132 assert(begin != NULL);
133 assert(node != NULL);
134 assert(loc_next >= 0);
135 if (begin == node) return NULL;
136 const void *cur = begin;
137 const void *next;
138 while (1) {
139 next = ll_next(cur);
140 if (next == node) return (void *) cur;
141 cur = next;
142 }
143 }
144
145 void cx_linked_list_link(
146 void *left,
147 void *right,
148 ptrdiff_t loc_prev,
149 ptrdiff_t loc_next
150 ) {
151 assert(loc_next >= 0);
152 ll_next(left) = right;
153 if (loc_prev >= 0) {
154 ll_prev(right) = left;
155 }
156 }
157
158 void cx_linked_list_unlink(
159 void *left,
160 void *right,
161 ptrdiff_t loc_prev,
162 ptrdiff_t loc_next
163 ) {
164 assert (loc_next >= 0);
165 assert(ll_next(left) == right);
166 ll_next(left) = NULL;
167 if (loc_prev >= 0) {
168 assert(ll_prev(right) == left);
169 ll_prev(right) = NULL;
170 }
171 }
172
173 void cx_linked_list_add(
174 void **begin,
175 void **end,
176 ptrdiff_t loc_prev,
177 ptrdiff_t loc_next,
178 void *new_node
179 ) {
180 void *last;
181 if (end == NULL) {
182 assert(begin != NULL);
183 last = *begin == NULL ? NULL : cx_linked_list_last(*begin, loc_next);
184 } else {
185 last = *end;
186 }
187 cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, last, new_node, new_node);
188 }
189
190 void cx_linked_list_prepend(
191 void **begin,
192 void **end,
193 ptrdiff_t loc_prev,
194 ptrdiff_t loc_next,
195 void *new_node
196 ) {
197 cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, NULL, new_node, new_node);
198 }
199
200 void cx_linked_list_insert(
201 void **begin,
202 void **end,
203 ptrdiff_t loc_prev,
204 ptrdiff_t loc_next,
205 void *node,
206 void *new_node
207 ) {
208 cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, node, new_node, new_node);
209 }
210
211 void cx_linked_list_insert_chain(
212 void **begin,
213 void **end,
214 ptrdiff_t loc_prev,
215 ptrdiff_t loc_next,
216 void *node,
217 void *insert_begin,
218 void *insert_end
219 ) {
220 // find the end of the chain, if not specified
221 if (insert_end == NULL) {
222 insert_end = cx_linked_list_last(insert_begin, loc_next);
223 }
224
225 // determine the successor
226 void *successor;
227 if (node == NULL) {
228 assert(begin != NULL || (end != NULL && loc_prev >= 0));
229 if (begin != NULL) {
230 successor = *begin;
231 *begin = insert_begin;
232 } else {
233 successor = *end == NULL ? NULL : cx_linked_list_first(*end, loc_prev);
234 }
235 } else {
236 successor = ll_next(node);
237 cx_linked_list_link(node, insert_begin, loc_prev, loc_next);
238 }
239
240 if (successor == NULL) {
241 // the list ends with the new chain
242 if (end != NULL) {
243 *end = insert_end;
244 }
245 } else {
246 cx_linked_list_link(insert_end, successor, loc_prev, loc_next);
247 }
248 }
249
250 void cx_linked_list_insert_sorted(
251 void **begin,
252 void **end,
253 ptrdiff_t loc_prev,
254 ptrdiff_t loc_next,
255 void *new_node,
256 cx_compare_func cmp_func
257 ) {
258 assert(ll_next(new_node) == NULL);
259 cx_linked_list_insert_sorted_chain(
260 begin, end, loc_prev, loc_next, new_node, cmp_func);
261 }
262
263 void cx_linked_list_insert_sorted_chain(
264 void **begin,
265 void **end,
266 ptrdiff_t loc_prev,
267 ptrdiff_t loc_next,
268 void *insert_begin,
269 cx_compare_func cmp_func
270 ) {
271 assert(begin != NULL);
272 assert(loc_next >= 0);
273 assert(insert_begin != NULL);
274
275 // track currently observed nodes
276 void *dest_prev = NULL;
277 void *dest = *begin;
278 void *src = insert_begin;
279
280 // special case: list is empty
281 if (dest == NULL) {
282 *begin = src;
283 if (end != NULL) {
284 *end = cx_linked_list_last(src, loc_next);
285 }
286 return;
287 }
288
289 // search the list for insertion points
290 while (dest != NULL && src != NULL) {
291 // compare current list node with source node
292 // if less or equal, skip
293 if (cmp_func(dest, src) <= 0) {
294 dest_prev = dest;
295 dest = ll_next(dest);
296 continue;
297 }
298
299 // determine chain of elements that can be inserted
300 void *end_of_chain = src;
301 void *next_in_chain = ll_next(src);
302 while (next_in_chain != NULL) {
303 // once we become larger than the list elem, break
304 if (cmp_func(dest, next_in_chain) <= 0) {
305 break;
306 }
307 // otherwise, we can insert one more
308 end_of_chain = next_in_chain;
309 next_in_chain = ll_next(next_in_chain);
310 }
311
312 // insert the elements
313 if (dest_prev == NULL) {
314 // new begin
315 *begin = src;
316 } else {
317 cx_linked_list_link(dest_prev, src, loc_prev, loc_next);
318 }
319 cx_linked_list_link(end_of_chain, dest, loc_prev, loc_next);
320
321 // continue with next
322 src = next_in_chain;
323 dest_prev = dest;
324 dest = ll_next(dest);
325 }
326
327 // insert remaining items
328 if (src != NULL) {
329 cx_linked_list_link(dest_prev, src, loc_prev, loc_next);
330 }
331
332 // determine new end of list, if requested
333 if (end != NULL) {
334 *end = cx_linked_list_last(
335 dest != NULL ? dest : dest_prev, loc_next);
336 }
337 }
338
339 void cx_linked_list_remove(
340 void **begin,
341 void **end,
342 ptrdiff_t loc_prev,
343 ptrdiff_t loc_next,
344 void *node
345 ) {
346 assert(node != NULL);
347 assert(loc_next >= 0);
348 assert(loc_prev >= 0 || begin != NULL);
349
350 // find adjacent nodes
351 void *next = ll_next(node);
352 void *prev;
353 if (loc_prev >= 0) {
354 prev = ll_prev(node);
355 } else {
356 prev = cx_linked_list_prev(*begin, loc_next, node);
357 }
358
359 // update next pointer of prev node, or set begin
360 if (prev == NULL) {
361 if (begin != NULL) {
362 *begin = next;
363 }
364 } else {
365 ll_next(prev) = next;
366 }
367
368 // update prev pointer of next node, or set end
369 if (next == NULL) {
370 if (end != NULL) {
371 *end = prev;
372 }
373 } else if (loc_prev >= 0) {
374 ll_prev(next) = prev;
375 }
376 }
377
378 size_t cx_linked_list_size(
379 const void *node,
380 ptrdiff_t loc_next
381 ) {
382 assert(loc_next >= 0);
383 size_t size = 0;
384 while (node != NULL) {
385 node = ll_next(node);
386 size++;
387 }
388 return size;
389 }
390
391 #ifndef CX_LINKED_LIST_SORT_SBO_SIZE
392 #define CX_LINKED_LIST_SORT_SBO_SIZE 1024
393 #endif
394
395 static void cx_linked_list_sort_merge(
396 ptrdiff_t loc_prev,
397 ptrdiff_t loc_next,
398 ptrdiff_t loc_data,
399 size_t length,
400 void *ls,
401 void *le,
402 void *re,
403 cx_compare_func cmp_func,
404 void **begin,
405 void **end
406 ) {
407 void *sbo[CX_LINKED_LIST_SORT_SBO_SIZE];
408 void **sorted = length >= CX_LINKED_LIST_SORT_SBO_SIZE ?
409 malloc(sizeof(void *) * length) : sbo;
410 if (sorted == NULL) abort();
411 void *rc, *lc;
412
413 lc = ls;
414 rc = le;
415 size_t n = 0;
416 while (lc && lc != le && rc != re) {
417 if (cmp_func(ll_data(lc), ll_data(rc)) <= 0) {
418 sorted[n] = lc;
419 lc = ll_next(lc);
420 } else {
421 sorted[n] = rc;
422 rc = ll_next(rc);
423 }
424 n++;
425 }
426 while (lc && lc != le) {
427 sorted[n] = lc;
428 lc = ll_next(lc);
429 n++;
430 }
431 while (rc && rc != re) {
432 sorted[n] = rc;
433 rc = ll_next(rc);
434 n++;
435 }
436
437 // Update pointer
438 if (loc_prev >= 0) ll_prev(sorted[0]) = NULL;
439 cx_for_n (i, length - 1) {
440 cx_linked_list_link(sorted[i], sorted[i + 1], loc_prev, loc_next);
441 }
442 ll_next(sorted[length - 1]) = NULL;
443
444 *begin = sorted[0];
445 *end = sorted[length-1];
446 if (sorted != sbo) {
447 free(sorted);
448 }
449 }
450
451 void cx_linked_list_sort( // NOLINT(misc-no-recursion) - purposely recursive function
452 void **begin,
453 void **end,
454 ptrdiff_t loc_prev,
455 ptrdiff_t loc_next,
456 ptrdiff_t loc_data,
457 cx_compare_func cmp_func
458 ) {
459 assert(begin != NULL);
460 assert(loc_next >= 0);
461 assert(loc_data >= 0);
462 assert(cmp_func);
463
464 void *lc, *ls, *le, *re;
465
466 // set start node
467 ls = *begin;
468
469 // early exit when this list is empty
470 if (ls == NULL) return;
471
472 // check how many elements are already sorted
473 lc = ls;
474 size_t ln = 1;
475 while (ll_next(lc) != NULL && cmp_func(ll_data(ll_next(lc)), ll_data(lc)) > 0) {
476 lc = ll_next(lc);
477 ln++;
478 }
479 le = ll_next(lc);
480
481 // if first unsorted node is NULL, the list is already completely sorted
482 if (le != NULL) {
483 void *rc;
484 size_t rn = 1;
485 rc = le;
486 // skip already sorted elements
487 while (ll_next(rc) != NULL && cmp_func(ll_data(ll_next(rc)), ll_data(rc)) > 0) {
488 rc = ll_next(rc);
489 rn++;
490 }
491 re = ll_next(rc);
492
493 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
494 void *sorted_begin, *sorted_end;
495 cx_linked_list_sort_merge(loc_prev, loc_next, loc_data,
496 ln + rn, ls, le, re, cmp_func,
497 &sorted_begin, &sorted_end);
498
499 // Something left? Sort it!
500 size_t remainder_length = cx_linked_list_size(re, loc_next);
501 if (remainder_length > 0) {
502 void *remainder = re;
503 cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, cmp_func);
504
505 // merge sorted list with (also sorted) remainder
506 cx_linked_list_sort_merge(loc_prev, loc_next, loc_data,
507 ln + rn + remainder_length,
508 sorted_begin, remainder, NULL, cmp_func,
509 &sorted_begin, &sorted_end);
510 }
511 *begin = sorted_begin;
512 if (end) *end = sorted_end;
513 }
514 }
515
516 int cx_linked_list_compare(
517 const void *begin_left,
518 const void *begin_right,
519 ptrdiff_t loc_advance,
520 ptrdiff_t loc_data,
521 cx_compare_func cmp_func
522 ) {
523 const void *left = begin_left, *right = begin_right;
524
525 while (left != NULL && right != NULL) {
526 const void *left_data = ll_data(left);
527 const void *right_data = ll_data(right);
528 int result = cmp_func(left_data, right_data);
529 if (result != 0) return result;
530 left = ll_advance(left);
531 right = ll_advance(right);
532 }
533
534 if (left != NULL) { return 1; }
535 else if (right != NULL) { return -1; }
536 else { return 0; }
537 }
538
539 void cx_linked_list_reverse(
540 void **begin,
541 void **end,
542 ptrdiff_t loc_prev,
543 ptrdiff_t loc_next
544 ) {
545 assert(begin != NULL);
546 assert(loc_next >= 0);
547
548 // swap all links
549 void *prev = NULL;
550 void *cur = *begin;
551 while (cur != NULL) {
552 void *next = ll_next(cur);
553
554 ll_next(cur) = prev;
555 if (loc_prev >= 0) {
556 ll_prev(cur) = next;
557 }
558
559 prev = cur;
560 cur = next;
561 }
562
563 // update begin and end
564 if (end != NULL) {
565 *end = *begin;
566 }
567 *begin = prev;
568 }
569
570 // HIGH LEVEL LINKED LIST IMPLEMENTATION
571
572 typedef struct cx_linked_list_node cx_linked_list_node;
573 struct cx_linked_list_node {
574 cx_linked_list_node *prev;
575 cx_linked_list_node *next;
576 char payload[];
577 };
578
579 #define CX_LL_LOC_PREV offsetof(cx_linked_list_node, prev)
580 #define CX_LL_LOC_NEXT offsetof(cx_linked_list_node, next)
581 #define CX_LL_LOC_DATA offsetof(cx_linked_list_node, payload)
582
583 typedef struct {
584 struct cx_list_s base;
585 cx_linked_list_node *begin;
586 cx_linked_list_node *end;
587 } cx_linked_list;
588
589 static cx_linked_list_node *cx_ll_node_at(
590 const cx_linked_list *list,
591 size_t index
592 ) {
593 if (index >= list->base.collection.size) {
594 return NULL;
595 } else if (index > list->base.collection.size / 2) {
596 return cx_linked_list_at(list->end, list->base.collection.size - 1, CX_LL_LOC_PREV, index);
597 } else {
598 return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index);
599 }
600 }
601
602 static cx_linked_list_node *cx_ll_malloc_node(const struct cx_list_s *list) {
603 return cxMalloc(list->collection.allocator,
604 sizeof(cx_linked_list_node) + list->collection.elem_size);
605 }
606
607 static int cx_ll_insert_at(
608 struct cx_list_s *list,
609 cx_linked_list_node *node,
610 const void *elem
611 ) {
612
613 // create the new new_node
614 cx_linked_list_node *new_node = cx_ll_malloc_node(list);
615
616 // sortir if failed
617 if (new_node == NULL) return 1;
618
619 // initialize new new_node
620 new_node->prev = new_node->next = NULL;
621 memcpy(new_node->payload, elem, list->collection.elem_size);
622
623 // insert
624 cx_linked_list *ll = (cx_linked_list *) list;
625 cx_linked_list_insert_chain(
626 (void **) &ll->begin, (void **) &ll->end,
627 CX_LL_LOC_PREV, CX_LL_LOC_NEXT,
628 node, new_node, new_node
629 );
630
631 // increase the size and return
632 list->collection.size++;
633 return 0;
634 }
635
636 static size_t cx_ll_insert_array(
637 struct cx_list_s *list,
638 size_t index,
639 const void *array,
640 size_t n
641 ) {
642 // out-of bounds and corner case check
643 if (index > list->collection.size || n == 0) return 0;
644
645 // find position efficiently
646 cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1);
647
648 // perform first insert
649 if (0 != cx_ll_insert_at(list, node, array)) {
650 return 1;
651 }
652
653 // is there more?
654 if (n == 1) return 1;
655
656 // we now know exactly where we are
657 node = node == NULL ? ((cx_linked_list *) list)->begin : node->next;
658
659 // we can add the remaining nodes and immediately advance to the inserted node
660 const char *source = array;
661 for (size_t i = 1; i < n; i++) {
662 source += list->collection.elem_size;
663 if (0 != cx_ll_insert_at(list, node, source)) {
664 return i;
665 }
666 node = node->next;
667 }
668 return n;
669 }
670
671 static int cx_ll_insert_element(
672 struct cx_list_s *list,
673 size_t index,
674 const void *element
675 ) {
676 return 1 != cx_ll_insert_array(list, index, element, 1);
677 }
678
679 static _Thread_local cx_compare_func cx_ll_insert_sorted_cmp_func;
680
681 static int cx_ll_insert_sorted_cmp_helper(const void *l, const void *r) {
682 const cx_linked_list_node *left = l;
683 const cx_linked_list_node *right = r;
684 return cx_ll_insert_sorted_cmp_func(left->payload, right->payload);
685 }
686
687 static size_t cx_ll_insert_sorted(
688 struct cx_list_s *list,
689 const void *array,
690 size_t n
691 ) {
692 // special case
693 if (n == 0) return 0;
694
695 // create a new chain of nodes
696 cx_linked_list_node *chain = cx_ll_malloc_node(list);
697 if (chain == NULL) return 0;
698
699 memcpy(chain->payload, array, list->collection.elem_size);
700 chain->prev = NULL;
701 chain->next = NULL;
702
703 // add all elements from the array to that chain
704 cx_linked_list_node *prev = chain;
705 const char *src = array;
706 size_t inserted = 1;
707 for (; inserted < n; inserted++) {
708 cx_linked_list_node *next = cx_ll_malloc_node(list);
709 if (next == NULL) break;
710 src += list->collection.elem_size;
711 memcpy(next->payload, src, list->collection.elem_size);
712 prev->next = next;
713 next->prev = prev;
714 prev = next;
715 }
716 prev->next = NULL;
717
718 // invoke the low level function
719 cx_linked_list *ll = (cx_linked_list *) list;
720 cx_ll_insert_sorted_cmp_func = list->collection.cmpfunc;
721 cx_linked_list_insert_sorted_chain(
722 (void **) &ll->begin,
723 (void **) &ll->end,
724 CX_LL_LOC_PREV,
725 CX_LL_LOC_NEXT,
726 chain,
727 cx_ll_insert_sorted_cmp_helper
728 );
729
730 // adjust the list metadata
731 list->collection.size += inserted;
732
733 return inserted;
734 }
735
736 static int cx_ll_remove(
737 struct cx_list_s *list,
738 size_t index
739 ) {
740 cx_linked_list *ll = (cx_linked_list *) list;
741 cx_linked_list_node *node = cx_ll_node_at(ll, index);
742
743 // out-of-bounds check
744 if (node == NULL) return 1;
745
746 // element destruction
747 cx_invoke_destructor(list, node->payload);
748
749 // remove
750 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
751 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
752
753 // adjust size
754 list->collection.size--;
755
756 // free and return
757 cxFree(list->collection.allocator, node);
758
759 return 0;
760 }
761
762 static void cx_ll_clear(struct cx_list_s *list) {
763 if (list->collection.size == 0) return;
764
765 cx_linked_list *ll = (cx_linked_list *) list;
766 cx_linked_list_node *node = ll->begin;
767 while (node != NULL) {
768 cx_invoke_destructor(list, node->payload);
769 cx_linked_list_node *next = node->next;
770 cxFree(list->collection.allocator, node);
771 node = next;
772 }
773 ll->begin = ll->end = NULL;
774 list->collection.size = 0;
775 }
776
777 #ifndef CX_LINKED_LIST_SWAP_SBO_SIZE
778 #define CX_LINKED_LIST_SWAP_SBO_SIZE 128
779 #endif
780 unsigned cx_linked_list_swap_sbo_size = CX_LINKED_LIST_SWAP_SBO_SIZE;
781
782 static int cx_ll_swap(
783 struct cx_list_s *list,
784 size_t i,
785 size_t j
786 ) {
787 if (i >= list->collection.size || j >= list->collection.size) return 1;
788 if (i == j) return 0;
789
790 // perform an optimized search that finds both elements in one run
791 cx_linked_list *ll = (cx_linked_list *) list;
792 size_t mid = list->collection.size / 2;
793 size_t left, right;
794 if (i < j) {
795 left = i;
796 right = j;
797 } else {
798 left = j;
799 right = i;
800 }
801 cx_linked_list_node *nleft, *nright;
802 if (left < mid && right < mid) {
803 // case 1: both items left from mid
804 nleft = cx_ll_node_at(ll, left);
805 assert(nleft != NULL);
806 nright = nleft;
807 for (size_t c = left; c < right; c++) {
808 nright = nright->next;
809 }
810 } else if (left >= mid && right >= mid) {
811 // case 2: both items right from mid
812 nright = cx_ll_node_at(ll, right);
813 assert(nright != NULL);
814 nleft = nright;
815 for (size_t c = right; c > left; c--) {
816 nleft = nleft->prev;
817 }
818 } else {
819 // case 3: one item left, one item right
820
821 // chose the closest to begin / end
822 size_t closest;
823 size_t other;
824 size_t diff2boundary = list->collection.size - right - 1;
825 if (left <= diff2boundary) {
826 closest = left;
827 other = right;
828 nleft = cx_ll_node_at(ll, left);
829 } else {
830 closest = right;
831 other = left;
832 diff2boundary = left;
833 nright = cx_ll_node_at(ll, right);
834 }
835
836 // is other element closer to us or closer to boundary?
837 if (right - left <= diff2boundary) {
838 // search other element starting from already found element
839 if (closest == left) {
840 nright = nleft;
841 for (size_t c = left; c < right; c++) {
842 nright = nright->next;
843 }
844 } else {
845 nleft = nright;
846 for (size_t c = right; c > left; c--) {
847 nleft = nleft->prev;
848 }
849 }
850 } else {
851 // search other element starting at the boundary
852 if (closest == left) {
853 nright = cx_ll_node_at(ll, other);
854 } else {
855 nleft = cx_ll_node_at(ll, other);
856 }
857 }
858 }
859
860 if (list->collection.elem_size > CX_LINKED_LIST_SWAP_SBO_SIZE) {
861 cx_linked_list_node *prev = nleft->prev;
862 cx_linked_list_node *next = nright->next;
863 cx_linked_list_node *midstart = nleft->next;
864 cx_linked_list_node *midend = nright->prev;
865
866 if (prev == NULL) {
867 ll->begin = nright;
868 } else {
869 prev->next = nright;
870 }
871 nright->prev = prev;
872 if (midstart == nright) {
873 // special case: both nodes are adjacent
874 nright->next = nleft;
875 nleft->prev = nright;
876 } else {
877 // likely case: a chain is between the two nodes
878 nright->next = midstart;
879 midstart->prev = nright;
880 midend->next = nleft;
881 nleft->prev = midend;
882 }
883 nleft->next = next;
884 if (next == NULL) {
885 ll->end = nleft;
886 } else {
887 next->prev = nleft;
888 }
889 } else {
890 // swap payloads to avoid relinking
891 char buf[CX_LINKED_LIST_SWAP_SBO_SIZE];
892 memcpy(buf, nleft->payload, list->collection.elem_size);
893 memcpy(nleft->payload, nright->payload, list->collection.elem_size);
894 memcpy(nright->payload, buf, list->collection.elem_size);
895 }
896
897 return 0;
898 }
899
900 static void *cx_ll_at(
901 const struct cx_list_s *list,
902 size_t index
903 ) {
904 cx_linked_list *ll = (cx_linked_list *) list;
905 cx_linked_list_node *node = cx_ll_node_at(ll, index);
906 return node == NULL ? NULL : node->payload;
907 }
908
909 static ssize_t cx_ll_find_remove(
910 struct cx_list_s *list,
911 const void *elem,
912 bool remove
913 ) {
914 if (remove) {
915 cx_linked_list *ll = ((cx_linked_list *) list);
916 cx_linked_list_node *node;
917 ssize_t index = cx_linked_list_find_node(
918 (void **) &node,
919 ll->begin,
920 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
921 list->collection.cmpfunc, elem
922 );
923 if (node != NULL) {
924 cx_invoke_destructor(list, node->payload);
925 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
926 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
927 list->collection.size--;
928 cxFree(list->collection.allocator, node);
929 }
930 return index;
931 } else {
932 return cx_linked_list_find(
933 ((cx_linked_list *) list)->begin,
934 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
935 list->collection.cmpfunc, elem
936 );
937 }
938 }
939
940 static void cx_ll_sort(struct cx_list_s *list) {
941 cx_linked_list *ll = (cx_linked_list *) list;
942 cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end,
943 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
944 list->collection.cmpfunc);
945 }
946
947 static void cx_ll_reverse(struct cx_list_s *list) {
948 cx_linked_list *ll = (cx_linked_list *) list;
949 cx_linked_list_reverse((void **) &ll->begin, (void **) &ll->end, CX_LL_LOC_PREV, CX_LL_LOC_NEXT);
950 }
951
952 static int cx_ll_compare(
953 const struct cx_list_s *list,
954 const struct cx_list_s *other
955 ) {
956 cx_linked_list *left = (cx_linked_list *) list;
957 cx_linked_list *right = (cx_linked_list *) other;
958 return cx_linked_list_compare(left->begin, right->begin,
959 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
960 list->collection.cmpfunc);
961 }
962
963 static bool cx_ll_iter_valid(const void *it) {
964 const struct cx_iterator_s *iter = it;
965 return iter->elem_handle != NULL;
966 }
967
968 static void cx_ll_iter_next(void *it) {
969 struct cx_iterator_s *iter = it;
970 if (iter->base.remove) {
971 iter->base.remove = false;
972 struct cx_list_s *list = iter->src_handle.m;
973 cx_linked_list *ll = iter->src_handle.m;
974 cx_linked_list_node *node = iter->elem_handle;
975 iter->elem_handle = node->next;
976 cx_invoke_destructor(list, node->payload);
977 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
978 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
979 list->collection.size--;
980 cxFree(list->collection.allocator, node);
981 } else {
982 iter->index++;
983 cx_linked_list_node *node = iter->elem_handle;
984 iter->elem_handle = node->next;
985 }
986 }
987
988 static void cx_ll_iter_prev(void *it) {
989 struct cx_iterator_s *iter = it;
990 if (iter->base.remove) {
991 iter->base.remove = false;
992 struct cx_list_s *list = iter->src_handle.m;
993 cx_linked_list *ll = iter->src_handle.m;
994 cx_linked_list_node *node = iter->elem_handle;
995 iter->elem_handle = node->prev;
996 iter->index--;
997 cx_invoke_destructor(list, node->payload);
998 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
999 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
1000 list->collection.size--;
1001 cxFree(list->collection.allocator, node);
1002 } else {
1003 iter->index--;
1004 cx_linked_list_node *node = iter->elem_handle;
1005 iter->elem_handle = node->prev;
1006 }
1007 }
1008
1009 static void *cx_ll_iter_current(const void *it) {
1010 const struct cx_iterator_s *iter = it;
1011 cx_linked_list_node *node = iter->elem_handle;
1012 return node->payload;
1013 }
1014
1015 static CxIterator cx_ll_iterator(
1016 const struct cx_list_s *list,
1017 size_t index,
1018 bool backwards
1019 ) {
1020 CxIterator iter;
1021 iter.index = index;
1022 iter.src_handle.c = list;
1023 iter.elem_handle = cx_ll_node_at((const cx_linked_list *) list, index);
1024 iter.elem_size = list->collection.elem_size;
1025 iter.elem_count = list->collection.size;
1026 iter.base.valid = cx_ll_iter_valid;
1027 iter.base.current = cx_ll_iter_current;
1028 iter.base.next = backwards ? cx_ll_iter_prev : cx_ll_iter_next;
1029 iter.base.mutating = false;
1030 iter.base.remove = false;
1031 return iter;
1032 }
1033
1034 static int cx_ll_insert_iter(
1035 CxIterator *iter,
1036 const void *elem,
1037 int prepend
1038 ) {
1039 struct cx_list_s *list = iter->src_handle.m;
1040 cx_linked_list_node *node = iter->elem_handle;
1041 if (node != NULL) {
1042 assert(prepend >= 0 && prepend <= 1);
1043 cx_linked_list_node *choice[2] = {node, node->prev};
1044 int result = cx_ll_insert_at(list, choice[prepend], elem);
1045 if (result == 0) {
1046 iter->elem_count++;
1047 if (prepend) {
1048 iter->index++;
1049 }
1050 }
1051 return result;
1052 } else {
1053 int result = cx_ll_insert_element(list, list->collection.size, elem);
1054 if (result == 0) {
1055 iter->elem_count++;
1056 iter->index = list->collection.size;
1057 }
1058 return result;
1059 }
1060 }
1061
1062 static void cx_ll_destructor(CxList *list) {
1063 cx_linked_list *ll = (cx_linked_list *) list;
1064
1065 cx_linked_list_node *node = ll->begin;
1066 while (node) {
1067 cx_invoke_destructor(list, node->payload);
1068 void *next = node->next;
1069 cxFree(list->collection.allocator, node);
1070 node = next;
1071 }
1072
1073 cxFree(list->collection.allocator, list);
1074 }
1075
1076 static cx_list_class cx_linked_list_class = {
1077 cx_ll_destructor,
1078 cx_ll_insert_element,
1079 cx_ll_insert_array,
1080 cx_ll_insert_sorted,
1081 cx_ll_insert_iter,
1082 cx_ll_remove,
1083 cx_ll_clear,
1084 cx_ll_swap,
1085 cx_ll_at,
1086 cx_ll_find_remove,
1087 cx_ll_sort,
1088 cx_ll_compare,
1089 cx_ll_reverse,
1090 cx_ll_iterator,
1091 };
1092
1093 CxList *cxLinkedListCreate(
1094 const CxAllocator *allocator,
1095 cx_compare_func comparator,
1096 size_t elem_size
1097 ) {
1098 if (allocator == NULL) {
1099 allocator = cxDefaultAllocator;
1100 }
1101
1102 cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list));
1103 if (list == NULL) return NULL;
1104
1105 list->base.cl = &cx_linked_list_class;
1106 list->base.collection.allocator = allocator;
1107
1108 if (elem_size > 0) {
1109 list->base.collection.elem_size = elem_size;
1110 list->base.collection.cmpfunc = comparator;
1111 } else {
1112 list->base.collection.cmpfunc = comparator == NULL ? cx_cmp_ptr : comparator;
1113 cxListStorePointers((CxList *) list);
1114 }
1115
1116 return (CxList *) list;
1117 }

Mercurial Repository: toolkit

mercurial