Mercurial > hg > dav / file comparison

comparison: ucx/linked_list.c

ucx/linked_list.c

branch
dav-2
changeset 891
4d58cbcc9efa
parent 889
42cdbf9bbd49
equal deleted inserted replaced
890:e77ccf1c4bb3 891:4d58cbcc9efa
29 #include "cx/linked_list.h" 29 #include "cx/linked_list.h"
30 #include "cx/compare.h" 30 #include "cx/compare.h"
31 #include <string.h> 31 #include <string.h>
32 #include <assert.h> 32 #include <assert.h>
33 33
34 #if __STDC_VERSION__ < 202311L
35 // we cannot simply include stdalign.h
36 // because Solaris is not entirely C11 complaint
37 #ifndef __alignof_is_defined
38 #define alignof _Alignof
39 #define __alignof_is_defined 1
40 #endif
41 #endif
42
34 // LOW LEVEL LINKED LIST FUNCTIONS 43 // LOW LEVEL LINKED LIST FUNCTIONS
35 44
36 #define CX_LL_PTR(cur, off) (*(void**)(((char*)(cur))+(off))) 45 #define CX_LL_PTR(cur, off) (*(void**)(((char*)(cur))+(off)))
37 #define ll_prev(node) CX_LL_PTR(node, loc_prev) 46 #define ll_prev(node) CX_LL_PTR(node, loc_prev)
38 #define ll_next(node) CX_LL_PTR(node, loc_next) 47 #define ll_next(node) CX_LL_PTR(node, loc_next)
54 i < index ? i++ : i--; 63 i < index ? i++ : i--;
55 } 64 }
56 return (void *) cur; 65 return (void *) cur;
57 } 66 }
58 67
68 void *cx_linked_list_find_c(
69 const void *start,
70 ptrdiff_t loc_advance,
71 ptrdiff_t loc_data,
72 const void *elem,
73 size_t *found_index,
74 cx_compare_func2 cmp_func,
75 void *context
76 ) {
77 assert(start != NULL);
78 assert(loc_advance >= 0);
79 assert(loc_data >= 0);
80 assert(cmp_func);
81
82 void *node = (void*) start;
83 size_t index = 0;
84 do {
85 void *current = ll_data(node);
86 if (cmp_func(current, elem, context) == 0) {
87 if (found_index != NULL) {
88 *found_index = index;
89 }
90 return node;
91 }
92 node = ll_advance(node);
93 index++;
94 } while (node != NULL);
95 return NULL;
96 }
97
59 void *cx_linked_list_find( 98 void *cx_linked_list_find(
60 const void *start, 99 const void *start,
61 ptrdiff_t loc_advance, 100 ptrdiff_t loc_advance,
62 ptrdiff_t loc_data, 101 ptrdiff_t loc_data,
63 cx_compare_func cmp_func,
64 const void *elem, 102 const void *elem,
65 size_t *found_index 103 size_t *found_index,
66 ) { 104 cx_compare_func cmp_func
67 assert(start != NULL); 105 ) {
68 assert(loc_advance >= 0); 106 cx_compare_func_wrapper wrapper = {cmp_func};
69 assert(loc_data >= 0); 107 return cx_linked_list_find_c(start, loc_advance, loc_data,
70 assert(cmp_func); 108 elem, found_index, cx_ccmp_wrap, &wrapper);
71
72 void *node = (void*) start;
73 size_t index = 0;
74 do {
75 void *current = ll_data(node);
76 if (cmp_func(current, elem) == 0) {
77 if (found_index != NULL) {
78 *found_index = index;
79 }
80 return node;
81 }
82 node = ll_advance(node);
83 index++;
84 } while (node != NULL);
85 return NULL;
86 } 109 }
87 110
88 void *cx_linked_list_first( 111 void *cx_linked_list_first(
89 const void *node, 112 const void *node,
90 ptrdiff_t loc_prev 113 ptrdiff_t loc_prev
229 } else { 252 } else {
230 cx_linked_list_link(insert_end, successor, loc_prev, loc_next); 253 cx_linked_list_link(insert_end, successor, loc_prev, loc_next);
231 } 254 }
232 } 255 }
233 256
234 void cx_linked_list_insert_sorted(
235 void **begin,
236 void **end,
237 ptrdiff_t loc_prev,
238 ptrdiff_t loc_next,
239 void *new_node,
240 cx_compare_func cmp_func
241 ) {
242 assert(ll_next(new_node) == NULL);
243 cx_linked_list_insert_sorted_chain(
244 begin, end, loc_prev, loc_next, new_node, cmp_func);
245 }
246
247 static void *cx_linked_list_insert_sorted_chain_impl( 257 static void *cx_linked_list_insert_sorted_chain_impl(
248 void **begin, 258 void **begin,
249 void **end, 259 void **end,
250 ptrdiff_t loc_prev, 260 ptrdiff_t loc_prev,
251 ptrdiff_t loc_next, 261 ptrdiff_t loc_next,
252 void *insert_begin, 262 void *insert_begin,
253 cx_compare_func cmp_func, 263 cx_compare_func2 cmp_func,
264 void *context,
254 bool allow_duplicates 265 bool allow_duplicates
255 ) { 266 ) {
256 assert(begin != NULL); 267 assert(begin != NULL);
257 assert(loc_next >= 0); 268 assert(loc_next >= 0);
258 assert(insert_begin != NULL); 269 assert(insert_begin != NULL);
265 void *dup_begin = NULL; 276 void *dup_begin = NULL;
266 void *dup_end = NULL; 277 void *dup_end = NULL;
267 278
268 // determine the new start 279 // determine the new start
269 { 280 {
270 int d = source_original == NULL ? 1 : cmp_func(source_original, source_argument); 281 int d = source_original == NULL ? 1 : cmp_func(source_original, source_argument, context);
271 if (d <= 0) { 282 if (d <= 0) {
272 // the new chain starts with the original chain 283 // the new chain starts with the original chain
273 new_begin = new_end = source_original; 284 new_begin = new_end = source_original;
274 source_original = ll_next(source_original); 285 source_original = ll_next(source_original);
275 if (d == 0) { 286 if (d == 0) {
291 } 302 }
292 } 303 }
293 304
294 // now successively compare the elements and add them to the correct chains 305 // now successively compare the elements and add them to the correct chains
295 while (source_original != NULL && source_argument != NULL) { 306 while (source_original != NULL && source_argument != NULL) {
296 int d = cmp_func(source_original, source_argument); 307 int d = cmp_func(source_original, source_argument, context);
297 if (d <= 0) { 308 if (d <= 0) {
298 // the original is not larger, add it to the chain 309 // the original is not larger, add it to the chain
299 cx_linked_list_link(new_end, source_original, loc_prev, loc_next); 310 cx_linked_list_link(new_end, source_original, loc_prev, loc_next);
300 new_end = source_original; 311 new_end = source_original;
301 source_original = ll_next(source_original); 312 source_original = ll_next(source_original);
316 source_argument = ll_next(source_argument); 327 source_argument = ll_next(source_argument);
317 } 328 }
318 } else { 329 } else {
319 // the original is larger, append the source argument to the chain 330 // the original is larger, append the source argument to the chain
320 // check if we must discard the source argument as duplicate 331 // check if we must discard the source argument as duplicate
321 if (!allow_duplicates && cmp_func(new_end, source_argument) == 0) { 332 if (!allow_duplicates && cmp_func(new_end, source_argument, context) == 0) {
322 if (dup_end == NULL) { 333 if (dup_end == NULL) {
323 dup_begin = dup_end = source_argument; 334 dup_begin = dup_end = source_argument;
324 } else { 335 } else {
325 cx_linked_list_link(dup_end, source_argument, loc_prev, loc_next); 336 cx_linked_list_link(dup_end, source_argument, loc_prev, loc_next);
326 dup_end = source_argument; 337 dup_end = source_argument;
345 cx_linked_list_link(new_end, source_argument, loc_prev, loc_next); 356 cx_linked_list_link(new_end, source_argument, loc_prev, loc_next);
346 new_end = cx_linked_list_last(source_argument, loc_next); 357 new_end = cx_linked_list_last(source_argument, loc_next);
347 } else { 358 } else {
348 // otherwise we must check one-by-one 359 // otherwise we must check one-by-one
349 while (source_argument != NULL) { 360 while (source_argument != NULL) {
350 if (cmp_func(new_end, source_argument) == 0) { 361 if (cmp_func(new_end, source_argument, context) == 0) {
351 if (dup_end == NULL) { 362 if (dup_end == NULL) {
352 dup_begin = dup_end = source_argument; 363 dup_begin = dup_end = source_argument;
353 } else { 364 } else {
354 cx_linked_list_link(dup_end, source_argument, loc_prev, loc_next); 365 cx_linked_list_link(dup_end, source_argument, loc_prev, loc_next);
355 dup_end = source_argument; 366 dup_end = source_argument;
383 *end = new_end; 394 *end = new_end;
384 } 395 }
385 return dup_begin; 396 return dup_begin;
386 } 397 }
387 398
399 void cx_linked_list_insert_sorted(
400 void **begin,
401 void **end,
402 ptrdiff_t loc_prev,
403 ptrdiff_t loc_next,
404 void *new_node,
405 cx_compare_func cmp_func
406 ) {
407 assert(ll_next(new_node) == NULL);
408 cx_linked_list_insert_sorted_chain(
409 begin, end, loc_prev, loc_next, new_node, cmp_func);
410 }
411
388 void cx_linked_list_insert_sorted_chain( 412 void cx_linked_list_insert_sorted_chain(
389 void **begin, 413 void **begin,
390 void **end, 414 void **end,
391 ptrdiff_t loc_prev, 415 ptrdiff_t loc_prev,
392 ptrdiff_t loc_next, 416 ptrdiff_t loc_next,
393 void *insert_begin, 417 void *insert_begin,
394 cx_compare_func cmp_func 418 cx_compare_func cmp_func
395 ) { 419 ) {
420 cx_compare_func_wrapper wrapper = {cmp_func};
396 cx_linked_list_insert_sorted_chain_impl( 421 cx_linked_list_insert_sorted_chain_impl(
397 begin, end, loc_prev, loc_next, 422 begin, end, loc_prev, loc_next,
398 insert_begin, cmp_func, true); 423 insert_begin, cx_ccmp_wrap, &wrapper, true);
399 } 424 }
400 425
401 int cx_linked_list_insert_unique( 426 int cx_linked_list_insert_unique(
402 void **begin, 427 void **begin,
403 void **end, 428 void **end,
417 ptrdiff_t loc_prev, 442 ptrdiff_t loc_prev,
418 ptrdiff_t loc_next, 443 ptrdiff_t loc_next,
419 void *insert_begin, 444 void *insert_begin,
420 cx_compare_func cmp_func 445 cx_compare_func cmp_func
421 ) { 446 ) {
447 cx_compare_func_wrapper wrapper = {cmp_func};
422 return cx_linked_list_insert_sorted_chain_impl( 448 return cx_linked_list_insert_sorted_chain_impl(
423 begin, end, loc_prev, loc_next, 449 begin, end, loc_prev, loc_next,
424 insert_begin, cmp_func, false); 450 insert_begin, cx_ccmp_wrap, &wrapper, false);
451 }
452
453 void cx_linked_list_insert_sorted_c(
454 void **begin,
455 void **end,
456 ptrdiff_t loc_prev,
457 ptrdiff_t loc_next,
458 void *new_node,
459 cx_compare_func2 cmp_func,
460 void *context
461 ) {
462 assert(ll_next(new_node) == NULL);
463 cx_linked_list_insert_sorted_chain_c(
464 begin, end, loc_prev, loc_next, new_node, cmp_func, context);
465 }
466
467 void cx_linked_list_insert_sorted_chain_c(
468 void **begin,
469 void **end,
470 ptrdiff_t loc_prev,
471 ptrdiff_t loc_next,
472 void *insert_begin,
473 cx_compare_func2 cmp_func,
474 void *context
475 ) {
476 cx_linked_list_insert_sorted_chain_impl(
477 begin, end, loc_prev, loc_next,
478 insert_begin, cmp_func, context, true);
479 }
480
481 int cx_linked_list_insert_unique_c(
482 void **begin,
483 void **end,
484 ptrdiff_t loc_prev,
485 ptrdiff_t loc_next,
486 void *new_node,
487 cx_compare_func2 cmp_func,
488 void *context
489 ) {
490 assert(ll_next(new_node) == NULL);
491 return NULL != cx_linked_list_insert_unique_chain_c(
492 begin, end, loc_prev, loc_next, new_node, cmp_func, context);
493 }
494
495 void *cx_linked_list_insert_unique_chain_c(
496 void **begin,
497 void **end,
498 ptrdiff_t loc_prev,
499 ptrdiff_t loc_next,
500 void *insert_begin,
501 cx_compare_func2 cmp_func,
502 void *context
503 ) {
504 return cx_linked_list_insert_sorted_chain_impl(
505 begin, end, loc_prev, loc_next,
506 insert_begin, cmp_func, context, false);
425 } 507 }
426 508
427 size_t cx_linked_list_remove_chain( 509 size_t cx_linked_list_remove_chain(
428 void **begin, 510 void **begin,
429 void **end, 511 void **end,
500 #ifndef CX_LINKED_LIST_SORT_SBO_SIZE 582 #ifndef CX_LINKED_LIST_SORT_SBO_SIZE
501 #define CX_LINKED_LIST_SORT_SBO_SIZE 1024 583 #define CX_LINKED_LIST_SORT_SBO_SIZE 1024
502 #endif 584 #endif
503 585
504 static void cx_linked_list_sort_merge( 586 static void cx_linked_list_sort_merge(
587 void **begin,
588 void **end,
505 ptrdiff_t loc_prev, 589 ptrdiff_t loc_prev,
506 ptrdiff_t loc_next, 590 ptrdiff_t loc_next,
507 ptrdiff_t loc_data, 591 ptrdiff_t loc_data,
508 size_t length, 592 size_t length,
509 void *ls, 593 void *ls,
510 void *le, 594 void *le,
511 void *re, 595 void *re,
512 cx_compare_func cmp_func, 596 cx_compare_func2 cmp_func,
513 void **begin, 597 void *context
514 void **end
515 ) { 598 ) {
516 void *sbo[CX_LINKED_LIST_SORT_SBO_SIZE]; 599 void *sbo[CX_LINKED_LIST_SORT_SBO_SIZE];
517 void **sorted = length >= CX_LINKED_LIST_SORT_SBO_SIZE ? 600 void **sorted = length >= CX_LINKED_LIST_SORT_SBO_SIZE ?
518 cxMallocDefault(sizeof(void *) * length) : sbo; 601 cxMallocDefault(sizeof(void *) * length) : sbo;
519 if (sorted == NULL) abort(); 602 if (sorted == NULL) abort(); // LCOV_EXCL_LINE
520 void *rc, *lc; 603 void *rc, *lc;
521 604
522 lc = ls; 605 lc = ls;
523 rc = le; 606 rc = le;
524 size_t n = 0; 607 size_t n = 0;
525 while (lc && lc != le && rc != re) { 608 while (lc && lc != le && rc != re) {
526 if (cmp_func(ll_data(lc), ll_data(rc)) <= 0) { 609 if (cmp_func(ll_data(lc), ll_data(rc), context) <= 0) {
527 sorted[n] = lc; 610 sorted[n] = lc;
528 lc = ll_next(lc); 611 lc = ll_next(lc);
529 } else { 612 } else {
530 sorted[n] = rc; 613 sorted[n] = rc;
531 rc = ll_next(rc); 614 rc = ll_next(rc);
555 if (sorted != sbo) { 638 if (sorted != sbo) {
556 cxFreeDefault(sorted); 639 cxFreeDefault(sorted);
557 } 640 }
558 } 641 }
559 642
560 void cx_linked_list_sort( // NOLINT(misc-no-recursion) - purposely recursive function 643 void cx_linked_list_sort_c( // NOLINT(misc-no-recursion) - purposely recursive function
561 void **begin, 644 void **begin,
562 void **end, 645 void **end,
563 ptrdiff_t loc_prev, 646 ptrdiff_t loc_prev,
564 ptrdiff_t loc_next, 647 ptrdiff_t loc_next,
565 ptrdiff_t loc_data, 648 ptrdiff_t loc_data,
566 cx_compare_func cmp_func 649 cx_compare_func2 cmp_func,
650 void *context
567 ) { 651 ) {
568 assert(begin != NULL); 652 assert(begin != NULL);
569 assert(loc_next >= 0); 653 assert(loc_next >= 0);
570 assert(loc_data >= 0); 654 assert(loc_data >= 0);
571 assert(cmp_func); 655 assert(cmp_func);
579 if (ls == NULL) return; 663 if (ls == NULL) return;
580 664
581 // check how many elements are already sorted 665 // check how many elements are already sorted
582 lc = ls; 666 lc = ls;
583 size_t ln = 1; 667 size_t ln = 1;
584 while (ll_next(lc) != NULL && cmp_func(ll_data(ll_next(lc)), ll_data(lc)) > 0) { 668 while (ll_next(lc) != NULL && cmp_func(ll_data(ll_next(lc)), ll_data(lc), context) > 0) {
585 lc = ll_next(lc); 669 lc = ll_next(lc);
586 ln++; 670 ln++;
587 } 671 }
588 le = ll_next(lc); 672 le = ll_next(lc);
589 673
591 if (le != NULL) { 675 if (le != NULL) {
592 void *rc; 676 void *rc;
593 size_t rn = 1; 677 size_t rn = 1;
594 rc = le; 678 rc = le;
595 // skip already sorted elements 679 // skip already sorted elements
596 while (ll_next(rc) != NULL && cmp_func(ll_data(ll_next(rc)), ll_data(rc)) > 0) { 680 while (ll_next(rc) != NULL && cmp_func(ll_data(ll_next(rc)), ll_data(rc), context) > 0) {
597 rc = ll_next(rc); 681 rc = ll_next(rc);
598 rn++; 682 rn++;
599 } 683 }
600 re = ll_next(rc); 684 re = ll_next(rc);
601 685
602 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them 686 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
603 void *sorted_begin, *sorted_end; 687 void *sorted_begin, *sorted_end;
604 cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, 688 cx_linked_list_sort_merge(&sorted_begin, &sorted_end,
689 loc_prev, loc_next, loc_data,
605 ln + rn, ls, le, re, cmp_func, 690 ln + rn, ls, le, re, cmp_func,
606 &sorted_begin, &sorted_end); 691 context);
607 692
608 // Something left? Sort it! 693 // Something left? Sort it!
609 size_t remainder_length = cx_linked_list_size(re, loc_next); 694 size_t remainder_length = cx_linked_list_size(re, loc_next);
610 if (remainder_length > 0) { 695 if (remainder_length > 0) {
611 void *remainder = re; 696 void *remainder = re;
612 cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, cmp_func); 697 cx_linked_list_sort_c(&remainder, NULL, loc_prev, loc_next, loc_data, cmp_func, context);
613 698
614 // merge sorted list with (also sorted) remainder 699 // merge sorted list with (also sorted) remainder
615 cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, 700 cx_linked_list_sort_merge(&sorted_begin, &sorted_end,
701 loc_prev, loc_next, loc_data,
616 ln + rn + remainder_length, 702 ln + rn + remainder_length,
617 sorted_begin, remainder, NULL, cmp_func, 703 sorted_begin, remainder, NULL, cmp_func,
618 &sorted_begin, &sorted_end); 704 context);
619 } 705 }
620 *begin = sorted_begin; 706 *begin = sorted_begin;
621 if (end) *end = sorted_end; 707 if (end) *end = sorted_end;
622 } 708 }
709 }
710
711 void cx_linked_list_sort(
712 void **begin,
713 void **end,
714 ptrdiff_t loc_prev,
715 ptrdiff_t loc_next,
716 ptrdiff_t loc_data,
717 cx_compare_func cmp_func
718 ) {
719 cx_compare_func_wrapper wrapper = {cmp_func};
720 cx_linked_list_sort_c(begin, end, loc_prev, loc_next, loc_data, cx_ccmp_wrap, &wrapper);
721 }
722
723 int cx_linked_list_compare_c(
724 const void *begin_left,
725 const void *begin_right,
726 ptrdiff_t loc_advance,
727 ptrdiff_t loc_data,
728 cx_compare_func2 cmp_func,
729 void *context
730 ) {
731 const void *left = begin_left, *right = begin_right;
732
733 while (left != NULL && right != NULL) {
734 const void *left_data = ll_data(left);
735 const void *right_data = ll_data(right);
736 int result = cmp_func(left_data, right_data, context);
737 if (result != 0) return result;
738 left = ll_advance(left);
739 right = ll_advance(right);
740 }
741
742 if (left != NULL) { return 1; }
743 else if (right != NULL) { return -1; }
744 else { return 0; }
623 } 745 }
624 746
625 int cx_linked_list_compare( 747 int cx_linked_list_compare(
626 const void *begin_left, 748 const void *begin_left,
627 const void *begin_right, 749 const void *begin_right,
628 ptrdiff_t loc_advance, 750 ptrdiff_t loc_advance,
629 ptrdiff_t loc_data, 751 ptrdiff_t loc_data,
630 cx_compare_func cmp_func 752 cx_compare_func cmp_func
631 ) { 753 ) {
632 const void *left = begin_left, *right = begin_right; 754 cx_compare_func_wrapper wrapper = {cmp_func};
633 755 return cx_linked_list_compare_c(begin_left, begin_right,
634 while (left != NULL && right != NULL) { 756 loc_advance, loc_data, cx_ccmp_wrap, &wrapper);
635 const void *left_data = ll_data(left);
636 const void *right_data = ll_data(right);
637 int result = cmp_func(left_data, right_data);
638 if (result != 0) return result;
639 left = ll_advance(left);
640 right = ll_advance(right);
641 }
642
643 if (left != NULL) { return 1; }
644 else if (right != NULL) { return -1; }
645 else { return 0; }
646 } 757 }
647 758
648 void cx_linked_list_reverse( 759 void cx_linked_list_reverse(
649 void **begin, 760 void **begin,
650 void **end, 761 void **end,
690 return cx_linked_list_at(list->begin, 0, list->loc_next, index); 801 return cx_linked_list_at(list->begin, 0, list->loc_next, index);
691 } 802 }
692 } 803 }
693 804
694 static void *cx_ll_malloc_node(const cx_linked_list *list) { 805 static void *cx_ll_malloc_node(const cx_linked_list *list) {
695 return cxZalloc(list->base.collection.allocator, 806 size_t n;
696 list->loc_data + list->base.collection.elem_size + list->extra_data_len); 807 if (list->extra_data_len == 0) {
808 n = list->loc_data + list->base.collection.elem_size;
809 } else {
810 n = list->loc_extra + list->extra_data_len;
811 }
812 return cxZalloc(list->base.collection.allocator, n);
697 } 813 }
698 814
699 static int cx_ll_insert_at( 815 static int cx_ll_insert_at(
700 struct cx_list_s *list, 816 struct cx_list_s *list,
701 void *node, 817 void *node,
782 char *next = CX_LL_PTR(node, ll->loc_next); 898 char *next = CX_LL_PTR(node, ll->loc_next);
783 return next + ll->loc_data; 899 return next + ll->loc_data;
784 } 900 }
785 } 901 }
786 902
787 static _Thread_local cx_compare_func cx_ll_insert_sorted_cmp_func; 903 static int cx_ll_insert_sorted_cmp_helper(const void *l, const void *r, void *c) {
788 static _Thread_local off_t cx_ll_insert_sorted_loc_data; 904 cx_linked_list *list = c;
789 905 const char *left = (const char*)l + list->loc_data;
790 static int cx_ll_insert_sorted_cmp_helper(const void *l, const void *r) { 906 const char *right = (const char*)r + list->loc_data;
791 const char *left = (const char*)l + cx_ll_insert_sorted_loc_data; 907 return cx_list_compare_wrapper(left, right, list);
792 const char *right = (const char*)r + cx_ll_insert_sorted_loc_data;
793 return cx_ll_insert_sorted_cmp_func(left, right);
794 } 908 }
795 909
796 static size_t cx_ll_insert_sorted_impl( 910 static size_t cx_ll_insert_sorted_impl(
797 struct cx_list_s *list, 911 struct cx_list_s *list,
798 const void *array, 912 const void *array,
823 CX_LL_PTR(next, ll->loc_prev) = prev; 937 CX_LL_PTR(next, ll->loc_prev) = prev;
824 prev = next; 938 prev = next;
825 } 939 }
826 CX_LL_PTR(prev, ll->loc_next) = NULL; 940 CX_LL_PTR(prev, ll->loc_next) = NULL;
827 941
828 // invoke the low level function 942 // invoke the low-level function
829 cx_ll_insert_sorted_cmp_func = list->collection.cmpfunc; 943 void *duplicates = cx_linked_list_insert_sorted_chain_impl(
830 cx_ll_insert_sorted_loc_data = ll->loc_data; 944 &ll->begin,
831 if (allow_duplicates) { 945 &ll->end,
832 cx_linked_list_insert_sorted_chain( 946 ll->loc_prev,
833 &ll->begin, 947 ll->loc_next,
834 &ll->end, 948 chain,
835 ll->loc_prev, 949 cx_ll_insert_sorted_cmp_helper,
836 ll->loc_next, 950 list,
837 chain, 951 allow_duplicates
838 cx_ll_insert_sorted_cmp_helper 952 );
839 ); 953 list->collection.size += inserted;
840 list->collection.size += inserted; 954 if (!allow_duplicates) {
841 } else {
842 void *duplicates = cx_linked_list_insert_unique_chain(
843 &ll->begin,
844 &ll->end,
845 ll->loc_prev,
846 ll->loc_next,
847 chain,
848 cx_ll_insert_sorted_cmp_helper
849 );
850 list->collection.size += inserted;
851 // free the nodes that did not make it into the list 955 // free the nodes that did not make it into the list
852 while (duplicates != NULL) { 956 while (duplicates != NULL) {
853 void *next = CX_LL_PTR(duplicates, ll->loc_next); 957 void *next = CX_LL_PTR(duplicates, ll->loc_next);
854 cxFree(list->collection.allocator, duplicates); 958 cxFree(list->collection.allocator, duplicates);
855 duplicates = next; 959 duplicates = next;
1074 ) { 1178 ) {
1075 if (list->collection.size == 0) return 0; 1179 if (list->collection.size == 0) return 0;
1076 1180
1077 size_t index; 1181 size_t index;
1078 cx_linked_list *ll = (cx_linked_list *) list; 1182 cx_linked_list *ll = (cx_linked_list *) list;
1079 char *node = cx_linked_list_find( 1183 char *node = cx_linked_list_find_c(
1080 ll->begin, 1184 ll->begin,
1081 ll->loc_next, ll->loc_data, 1185 ll->loc_next, ll->loc_data,
1082 list->collection.cmpfunc, elem, 1186 elem, &index,
1083 &index 1187 cx_list_compare_wrapper,
1084 ); 1188 list);
1085 if (node == NULL) { 1189 if (node == NULL) {
1086 return list->collection.size; 1190 return list->collection.size;
1087 } 1191 }
1088 if (remove) { 1192 if (remove) {
1089 cx_invoke_destructor(list, node + ll->loc_data); 1193 cx_invoke_destructor(list, node + ll->loc_data);
1095 return index; 1199 return index;
1096 } 1200 }
1097 1201
1098 static void cx_ll_sort(struct cx_list_s *list) { 1202 static void cx_ll_sort(struct cx_list_s *list) {
1099 cx_linked_list *ll = (cx_linked_list *) list; 1203 cx_linked_list *ll = (cx_linked_list *) list;
1100 cx_linked_list_sort(&ll->begin, &ll->end, 1204 cx_linked_list_sort_c(&ll->begin, &ll->end,
1101 ll->loc_prev, ll->loc_next, ll->loc_data, 1205 ll->loc_prev, ll->loc_next, ll->loc_data,
1102 list->collection.cmpfunc); 1206 cx_list_compare_wrapper, list);
1103 } 1207 }
1104 1208
1105 static void cx_ll_reverse(struct cx_list_s *list) { 1209 static void cx_ll_reverse(struct cx_list_s *list) {
1106 cx_linked_list *ll = (cx_linked_list *) list; 1210 cx_linked_list *ll = (cx_linked_list *) list;
1107 cx_linked_list_reverse(&ll->begin, &ll->end, ll->loc_prev, ll->loc_next); 1211 cx_linked_list_reverse(&ll->begin, &ll->end, ll->loc_prev, ll->loc_next);
1113 ) { 1217 ) {
1114 cx_linked_list *left = (cx_linked_list *) list; 1218 cx_linked_list *left = (cx_linked_list *) list;
1115 cx_linked_list *right = (cx_linked_list *) other; 1219 cx_linked_list *right = (cx_linked_list *) other;
1116 assert(left->loc_next == right->loc_next); 1220 assert(left->loc_next == right->loc_next);
1117 assert(left->loc_data == right->loc_data); 1221 assert(left->loc_data == right->loc_data);
1118 return cx_linked_list_compare(left->begin, right->begin, 1222 return cx_linked_list_compare_c(left->begin, right->begin,
1119 left->loc_next, left->loc_data, 1223 left->loc_next, left->loc_data,
1120 list->collection.cmpfunc); 1224 cx_list_compare_wrapper, (void*)list);
1121 } 1225 }
1122 1226
1123 static bool cx_ll_iter_valid(const void *it) { 1227 static bool cx_ll_iter_valid(const void *it) {
1124 const struct cx_iterator_s *iter = it; 1228 const struct cx_iterator_s *iter = it;
1125 return iter->elem_handle != NULL; 1229 return iter->elem_handle != NULL;
1213 } 1317 }
1214 } 1318 }
1215 return result; 1319 return result;
1216 } else { 1320 } else {
1217 if (cx_ll_insert_element(list, list->collection.size, elem) == NULL) { 1321 if (cx_ll_insert_element(list, list->collection.size, elem) == NULL) {
1218 return 1; 1322 return 1; // LCOV_EXCL_LINE
1219 } 1323 }
1220 iter->elem_count++; 1324 iter->elem_count++;
1221 iter->index = list->collection.size; 1325 iter->index = list->collection.size;
1222 return 0; 1326 return 0;
1223 } 1327 }
1250 cx_ll_at, 1354 cx_ll_at,
1251 cx_ll_find_remove, 1355 cx_ll_find_remove,
1252 cx_ll_sort, 1356 cx_ll_sort,
1253 cx_ll_compare, 1357 cx_ll_compare,
1254 cx_ll_reverse, 1358 cx_ll_reverse,
1359 NULL, // no overallocation supported
1255 cx_ll_iterator, 1360 cx_ll_iterator,
1256 }; 1361 };
1257 1362
1258 CxList *cxLinkedListCreate( 1363 CxList *cxLinkedListCreate(
1259 const CxAllocator *allocator, 1364 const CxAllocator *allocator,
1260 cx_compare_func comparator,
1261 size_t elem_size 1365 size_t elem_size
1262 ) { 1366 ) {
1263 if (allocator == NULL) { 1367 if (allocator == NULL) {
1264 allocator = cxDefaultAllocator; 1368 allocator = cxDefaultAllocator;
1265 } 1369 }
1266 1370
1267 cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list)); 1371 cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list));
1268 if (list == NULL) return NULL; 1372 if (list == NULL) return NULL;
1269 list->extra_data_len = 0;
1270 list->loc_prev = 0; 1373 list->loc_prev = 0;
1271 list->loc_next = sizeof(void*); 1374 list->loc_next = sizeof(void*);
1272 list->loc_data = sizeof(void*)*2; 1375 list->loc_data = sizeof(void*)*2;
1376 list->loc_extra = -1;
1377 list->extra_data_len = 0;
1273 cx_list_init((CxList*)list, &cx_linked_list_class, 1378 cx_list_init((CxList*)list, &cx_linked_list_class,
1274 allocator, comparator, elem_size); 1379 allocator, elem_size);
1275 1380
1276 return (CxList *) list; 1381 return (CxList *) list;
1277 } 1382 }
1383
1384 void cx_linked_list_extra_data(cx_linked_list *list, size_t len) {
1385 list->extra_data_len = len;
1386
1387 off_t loc_extra = list->loc_data + list->base.collection.elem_size;
1388 size_t alignment = alignof(void*);
1389 size_t padding = alignment - (loc_extra % alignment);
1390 list->loc_extra = loc_extra + padding;
1391 }

Mercurial Repository: dav

mercurial