Mercurial > hg > dav / file comparison

comparison: ucx/linked_list.c

ucx/linked_list.c

branch
ucx-3.1
changeset 816
839fefbdedc7
parent 776
96555c0ed875
equal deleted inserted replaced
815:1f40ca07ae1b 816:839fefbdedc7
26 * POSSIBILITY OF SUCH DAMAGE. 26 * POSSIBILITY OF SUCH DAMAGE.
27 */ 27 */
28 28
29 #include "cx/linked_list.h" 29 #include "cx/linked_list.h"
30 #include "cx/utils.h" 30 #include "cx/utils.h"
31 #include "cx/compare.h"
31 #include <string.h> 32 #include <string.h>
32 #include <assert.h> 33 #include <assert.h>
33 34
34 // LOW LEVEL LINKED LIST FUNCTIONS 35 // LOW LEVEL LINKED LIST FUNCTIONS
35 36
61 ptrdiff_t loc_advance, 62 ptrdiff_t loc_advance,
62 ptrdiff_t loc_data, 63 ptrdiff_t loc_data,
63 cx_compare_func cmp_func, 64 cx_compare_func cmp_func,
64 void const *elem 65 void const *elem
65 ) { 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 void const *start,
78 ptrdiff_t loc_advance,
79 ptrdiff_t loc_data,
80 cx_compare_func cmp_func,
81 void const *elem
82 ) {
83 assert(result != NULL);
66 assert(start != NULL); 84 assert(start != NULL);
67 assert(loc_advance >= 0); 85 assert(loc_advance >= 0);
68 assert(loc_data >= 0); 86 assert(loc_data >= 0);
69 assert(cmp_func); 87 assert(cmp_func);
70 88
71 void const *node = start; 89 void const *node = start;
72 ssize_t index = 0; 90 ssize_t index = 0;
73 do { 91 do {
74 void *current = ll_data(node); 92 void *current = ll_data(node);
75 if (cmp_func(current, elem) == 0) { 93 if (cmp_func(current, elem) == 0) {
94 *result = (void*) node;
76 return index; 95 return index;
77 } 96 }
78 node = ll_advance(node); 97 node = ll_advance(node);
79 index++; 98 index++;
80 } while (node != NULL); 99 } while (node != NULL);
100 *result = NULL;
81 return -1; 101 return -1;
82 } 102 }
83 103
84 void *cx_linked_list_first( 104 void *cx_linked_list_first(
85 void const *node, 105 void const *node,
458 *begin = prev; 478 *begin = prev;
459 } 479 }
460 480
461 // HIGH LEVEL LINKED LIST IMPLEMENTATION 481 // HIGH LEVEL LINKED LIST IMPLEMENTATION
462 482
463 bool CX_DISABLE_LINKED_LIST_SWAP_SBO = false;
464
465 typedef struct cx_linked_list_node cx_linked_list_node; 483 typedef struct cx_linked_list_node cx_linked_list_node;
466 struct cx_linked_list_node { 484 struct cx_linked_list_node {
467 cx_linked_list_node *prev; 485 cx_linked_list_node *prev;
468 cx_linked_list_node *next; 486 cx_linked_list_node *next;
469 char payload[]; 487 char payload[];
481 499
482 static cx_linked_list_node *cx_ll_node_at( 500 static cx_linked_list_node *cx_ll_node_at(
483 cx_linked_list const *list, 501 cx_linked_list const *list,
484 size_t index 502 size_t index
485 ) { 503 ) {
486 if (index >= list->base.size) { 504 if (index >= list->base.collection.size) {
487 return NULL; 505 return NULL;
488 } else if (index > list->base.size / 2) { 506 } else if (index > list->base.collection.size / 2) {
489 return cx_linked_list_at(list->end, list->base.size - 1, CX_LL_LOC_PREV, index); 507 return cx_linked_list_at(list->end, list->base.collection.size - 1, CX_LL_LOC_PREV, index);
490 } else { 508 } else {
491 return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index); 509 return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index);
492 } 510 }
493 } 511 }
494 512
497 cx_linked_list_node *node, 515 cx_linked_list_node *node,
498 void const *elem 516 void const *elem
499 ) { 517 ) {
500 518
501 // create the new new_node 519 // create the new new_node
502 cx_linked_list_node *new_node = cxMalloc(list->allocator, 520 cx_linked_list_node *new_node = cxMalloc(list->collection.allocator,
503 sizeof(cx_linked_list_node) + list->item_size); 521 sizeof(cx_linked_list_node) + list->collection.elem_size);
504 522
505 // sortir if failed 523 // sortir if failed
506 if (new_node == NULL) return 1; 524 if (new_node == NULL) return 1;
507 525
508 // initialize new new_node 526 // initialize new new_node
509 new_node->prev = new_node->next = NULL; 527 new_node->prev = new_node->next = NULL;
510 memcpy(new_node->payload, elem, list->item_size); 528 memcpy(new_node->payload, elem, list->collection.elem_size);
511 529
512 // insert 530 // insert
513 cx_linked_list *ll = (cx_linked_list *) list; 531 cx_linked_list *ll = (cx_linked_list *) list;
514 cx_linked_list_insert_chain( 532 cx_linked_list_insert_chain(
515 (void **) &ll->begin, (void **) &ll->end, 533 (void **) &ll->begin, (void **) &ll->end,
516 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, 534 CX_LL_LOC_PREV, CX_LL_LOC_NEXT,
517 node, new_node, new_node 535 node, new_node, new_node
518 ); 536 );
519 537
520 // increase the size and return 538 // increase the size and return
521 list->size++; 539 list->collection.size++;
522 return 0; 540 return 0;
523 } 541 }
524 542
525 static size_t cx_ll_insert_array( 543 static size_t cx_ll_insert_array(
526 struct cx_list_s *list, 544 struct cx_list_s *list,
527 size_t index, 545 size_t index,
528 void const *array, 546 void const *array,
529 size_t n 547 size_t n
530 ) { 548 ) {
531 // out-of bounds and corner case check 549 // out-of bounds and corner case check
532 if (index > list->size || n == 0) return 0; 550 if (index > list->collection.size || n == 0) return 0;
533 551
534 // find position efficiently 552 // find position efficiently
535 cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1); 553 cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1);
536 554
537 // perform first insert 555 // perform first insert
546 node = node == NULL ? ((cx_linked_list *) list)->begin : node->next; 564 node = node == NULL ? ((cx_linked_list *) list)->begin : node->next;
547 565
548 // we can add the remaining nodes and immedately advance to the inserted node 566 // we can add the remaining nodes and immedately advance to the inserted node
549 char const *source = array; 567 char const *source = array;
550 for (size_t i = 1; i < n; i++) { 568 for (size_t i = 1; i < n; i++) {
551 source += list->item_size; 569 source += list->collection.elem_size;
552 if (0 != cx_ll_insert_at(list, node, source)) { 570 if (0 != cx_ll_insert_at(list, node, source)) {
553 return i; 571 return i;
554 } 572 }
555 node = node->next; 573 node = node->next;
556 } 574 }
581 // remove 599 // remove
582 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end, 600 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
583 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node); 601 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
584 602
585 // adjust size 603 // adjust size
586 list->size--; 604 list->collection.size--;
587 605
588 // free and return 606 // free and return
589 cxFree(list->allocator, node); 607 cxFree(list->collection.allocator, node);
590 608
591 return 0; 609 return 0;
592 } 610 }
593 611
594 static void cx_ll_clear(struct cx_list_s *list) { 612 static void cx_ll_clear(struct cx_list_s *list) {
595 if (list->size == 0) return; 613 if (list->collection.size == 0) return;
596 614
597 cx_linked_list *ll = (cx_linked_list *) list; 615 cx_linked_list *ll = (cx_linked_list *) list;
598 cx_linked_list_node *node = ll->begin; 616 cx_linked_list_node *node = ll->begin;
599 while (node != NULL) { 617 while (node != NULL) {
600 cx_invoke_destructor(list, node->payload); 618 cx_invoke_destructor(list, node->payload);
601 cx_linked_list_node *next = node->next; 619 cx_linked_list_node *next = node->next;
602 cxFree(list->allocator, node); 620 cxFree(list->collection.allocator, node);
603 node = next; 621 node = next;
604 } 622 }
605 ll->begin = ll->end = NULL; 623 ll->begin = ll->end = NULL;
606 list->size = 0; 624 list->collection.size = 0;
607 } 625 }
608 626
609 #ifndef CX_LINKED_LIST_SWAP_SBO_SIZE 627 #ifndef CX_LINKED_LIST_SWAP_SBO_SIZE
610 #define CX_LINKED_LIST_SWAP_SBO_SIZE 128 628 #define CX_LINKED_LIST_SWAP_SBO_SIZE 128
611 #endif 629 #endif
630 unsigned cx_linked_list_swap_sbo_size = CX_LINKED_LIST_SWAP_SBO_SIZE;
612 631
613 static int cx_ll_swap( 632 static int cx_ll_swap(
614 struct cx_list_s *list, 633 struct cx_list_s *list,
615 size_t i, 634 size_t i,
616 size_t j 635 size_t j
617 ) { 636 ) {
618 if (i >= list->size || j >= list->size) return 1; 637 if (i >= list->collection.size || j >= list->collection.size) return 1;
619 if (i == j) return 0; 638 if (i == j) return 0;
620 639
621 // perform an optimized search that finds both elements in one run 640 // perform an optimized search that finds both elements in one run
622 cx_linked_list *ll = (cx_linked_list *) list; 641 cx_linked_list *ll = (cx_linked_list *) list;
623 size_t mid = list->size / 2; 642 size_t mid = list->collection.size / 2;
624 size_t left, right; 643 size_t left, right;
625 if (i < j) { 644 if (i < j) {
626 left = i; 645 left = i;
627 right = j; 646 right = j;
628 } else { 647 } else {
631 } 650 }
632 cx_linked_list_node *nleft, *nright; 651 cx_linked_list_node *nleft, *nright;
633 if (left < mid && right < mid) { 652 if (left < mid && right < mid) {
634 // case 1: both items left from mid 653 // case 1: both items left from mid
635 nleft = cx_ll_node_at(ll, left); 654 nleft = cx_ll_node_at(ll, left);
655 assert(nleft != NULL);
636 nright = nleft; 656 nright = nleft;
637 for (size_t c = left; c < right; c++) { 657 for (size_t c = left; c < right; c++) {
638 nright = nright->next; 658 nright = nright->next;
639 } 659 }
640 } else if (left >= mid && right >= mid) { 660 } else if (left >= mid && right >= mid) {
641 // case 2: both items right from mid 661 // case 2: both items right from mid
642 nright = cx_ll_node_at(ll, right); 662 nright = cx_ll_node_at(ll, right);
663 assert(nright != NULL);
643 nleft = nright; 664 nleft = nright;
644 for (size_t c = right; c > left; c--) { 665 for (size_t c = right; c > left; c--) {
645 nleft = nleft->prev; 666 nleft = nleft->prev;
646 } 667 }
647 } else { 668 } else {
648 // case 3: one item left, one item right 669 // case 3: one item left, one item right
649 670
650 // chose the closest to begin / end 671 // chose the closest to begin / end
651 size_t closest; 672 size_t closest;
652 size_t other; 673 size_t other;
653 size_t diff2boundary = list->size - right - 1; 674 size_t diff2boundary = list->collection.size - right - 1;
654 if (left <= diff2boundary) { 675 if (left <= diff2boundary) {
655 closest = left; 676 closest = left;
656 other = right; 677 other = right;
657 nleft = cx_ll_node_at(ll, left); 678 nleft = cx_ll_node_at(ll, left);
658 } else { 679 } else {
684 nleft = cx_ll_node_at(ll, other); 705 nleft = cx_ll_node_at(ll, other);
685 } 706 }
686 } 707 }
687 } 708 }
688 709
689 if (list->item_size > CX_LINKED_LIST_SWAP_SBO_SIZE || CX_DISABLE_LINKED_LIST_SWAP_SBO) { 710 if (list->collection.elem_size > CX_LINKED_LIST_SWAP_SBO_SIZE) {
690 cx_linked_list_node *prev = nleft->prev; 711 cx_linked_list_node *prev = nleft->prev;
691 cx_linked_list_node *next = nright->next; 712 cx_linked_list_node *next = nright->next;
692 cx_linked_list_node *midstart = nleft->next; 713 cx_linked_list_node *midstart = nleft->next;
693 cx_linked_list_node *midend = nright->prev; 714 cx_linked_list_node *midend = nright->prev;
694 715
716 next->prev = nleft; 737 next->prev = nleft;
717 } 738 }
718 } else { 739 } else {
719 // swap payloads to avoid relinking 740 // swap payloads to avoid relinking
720 char buf[CX_LINKED_LIST_SWAP_SBO_SIZE]; 741 char buf[CX_LINKED_LIST_SWAP_SBO_SIZE];
721 memcpy(buf, nleft->payload, list->item_size); 742 memcpy(buf, nleft->payload, list->collection.elem_size);
722 memcpy(nleft->payload, nright->payload, list->item_size); 743 memcpy(nleft->payload, nright->payload, list->collection.elem_size);
723 memcpy(nright->payload, buf, list->item_size); 744 memcpy(nright->payload, buf, list->collection.elem_size);
724 } 745 }
725 746
726 return 0; 747 return 0;
727 } 748 }
728 749
733 cx_linked_list *ll = (cx_linked_list *) list; 754 cx_linked_list *ll = (cx_linked_list *) list;
734 cx_linked_list_node *node = cx_ll_node_at(ll, index); 755 cx_linked_list_node *node = cx_ll_node_at(ll, index);
735 return node == NULL ? NULL : node->payload; 756 return node == NULL ? NULL : node->payload;
736 } 757 }
737 758
738 static ssize_t cx_ll_find( 759 static ssize_t cx_ll_find_remove(
739 struct cx_list_s const *list, 760 struct cx_list_s *list,
740 void const *elem 761 void const *elem,
741 ) { 762 bool remove
742 return cx_linked_list_find(((cx_linked_list *) list)->begin, 763 ) {
743 CX_LL_LOC_NEXT, CX_LL_LOC_DATA, 764 if (remove) {
744 list->cmpfunc, elem); 765 cx_linked_list *ll = ((cx_linked_list *) list);
766 cx_linked_list_node *node;
767 ssize_t index = cx_linked_list_find_node(
768 (void **) &node,
769 ll->begin,
770 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
771 list->collection.cmpfunc, elem
772 );
773 if (node != NULL) {
774 cx_invoke_destructor(list, node->payload);
775 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
776 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
777 list->collection.size--;
778 cxFree(list->collection.allocator, node);
779 }
780 return index;
781 } else {
782 return cx_linked_list_find(
783 ((cx_linked_list *) list)->begin,
784 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
785 list->collection.cmpfunc, elem
786 );
787 }
745 } 788 }
746 789
747 static void cx_ll_sort(struct cx_list_s *list) { 790 static void cx_ll_sort(struct cx_list_s *list) {
748 cx_linked_list *ll = (cx_linked_list *) list; 791 cx_linked_list *ll = (cx_linked_list *) list;
749 cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end, 792 cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end,
750 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA, 793 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
751 list->cmpfunc); 794 list->collection.cmpfunc);
752 } 795 }
753 796
754 static void cx_ll_reverse(struct cx_list_s *list) { 797 static void cx_ll_reverse(struct cx_list_s *list) {
755 cx_linked_list *ll = (cx_linked_list *) list; 798 cx_linked_list *ll = (cx_linked_list *) list;
756 cx_linked_list_reverse((void **) &ll->begin, (void **) &ll->end, CX_LL_LOC_PREV, CX_LL_LOC_NEXT); 799 cx_linked_list_reverse((void **) &ll->begin, (void **) &ll->end, CX_LL_LOC_PREV, CX_LL_LOC_NEXT);
762 ) { 805 ) {
763 cx_linked_list *left = (cx_linked_list *) list; 806 cx_linked_list *left = (cx_linked_list *) list;
764 cx_linked_list *right = (cx_linked_list *) other; 807 cx_linked_list *right = (cx_linked_list *) other;
765 return cx_linked_list_compare(left->begin, right->begin, 808 return cx_linked_list_compare(left->begin, right->begin,
766 CX_LL_LOC_NEXT, CX_LL_LOC_DATA, 809 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
767 list->cmpfunc); 810 list->collection.cmpfunc);
768 } 811 }
769 812
770 static bool cx_ll_iter_valid(void const *it) { 813 static bool cx_ll_iter_valid(void const *it) {
771 struct cx_iterator_s const *iter = it; 814 struct cx_iterator_s const *iter = it;
772 return iter->elem_handle != NULL; 815 return iter->elem_handle != NULL;
773 } 816 }
774 817
775 static void cx_ll_iter_next(void *it) { 818 static void cx_ll_iter_next(void *it) {
776 struct cx_iterator_base_s *itbase = it; 819 struct cx_iterator_s *iter = it;
777 if (itbase->remove) { 820 if (iter->base.remove) {
778 itbase->remove = false; 821 iter->base.remove = false;
779 struct cx_mut_iterator_s *iter = it; 822 struct cx_list_s *list = iter->src_handle.m;
780 struct cx_list_s *list = iter->src_handle; 823 cx_linked_list *ll = iter->src_handle.m;
781 cx_linked_list *ll = iter->src_handle;
782 cx_linked_list_node *node = iter->elem_handle; 824 cx_linked_list_node *node = iter->elem_handle;
783 iter->elem_handle = node->next; 825 iter->elem_handle = node->next;
784 cx_invoke_destructor(list, node->payload); 826 cx_invoke_destructor(list, node->payload);
785 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end, 827 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
786 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node); 828 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
787 list->size--; 829 list->collection.size--;
788 cxFree(list->allocator, node); 830 cxFree(list->collection.allocator, node);
789 } else { 831 } else {
790 struct cx_iterator_s *iter = it;
791 iter->index++; 832 iter->index++;
792 cx_linked_list_node *node = iter->elem_handle; 833 cx_linked_list_node *node = iter->elem_handle;
793 iter->elem_handle = node->next; 834 iter->elem_handle = node->next;
794 } 835 }
795 } 836 }
796 837
797 static void cx_ll_iter_prev(void *it) { 838 static void cx_ll_iter_prev(void *it) {
798 struct cx_iterator_base_s *itbase = it; 839 struct cx_iterator_s *iter = it;
799 if (itbase->remove) { 840 if (iter->base.remove) {
800 itbase->remove = false; 841 iter->base.remove = false;
801 struct cx_mut_iterator_s *iter = it; 842 struct cx_list_s *list = iter->src_handle.m;
802 struct cx_list_s *list = iter->src_handle; 843 cx_linked_list *ll = iter->src_handle.m;
803 cx_linked_list *ll = iter->src_handle;
804 cx_linked_list_node *node = iter->elem_handle; 844 cx_linked_list_node *node = iter->elem_handle;
805 iter->elem_handle = node->prev; 845 iter->elem_handle = node->prev;
806 iter->index--; 846 iter->index--;
807 cx_invoke_destructor(list, node->payload); 847 cx_invoke_destructor(list, node->payload);
808 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end, 848 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
809 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node); 849 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
810 list->size--; 850 list->collection.size--;
811 cxFree(list->allocator, node); 851 cxFree(list->collection.allocator, node);
812 } else { 852 } else {
813 struct cx_iterator_s *iter = it;
814 iter->index--; 853 iter->index--;
815 cx_linked_list_node *node = iter->elem_handle; 854 cx_linked_list_node *node = iter->elem_handle;
816 iter->elem_handle = node->prev; 855 iter->elem_handle = node->prev;
817 } 856 }
818 } 857 }
821 struct cx_iterator_s const *iter = it; 860 struct cx_iterator_s const *iter = it;
822 cx_linked_list_node *node = iter->elem_handle; 861 cx_linked_list_node *node = iter->elem_handle;
823 return node->payload; 862 return node->payload;
824 } 863 }
825 864
826 static bool cx_ll_iter_flag_rm(void *it) {
827 struct cx_iterator_base_s *iter = it;
828 if (iter->mutating) {
829 iter->remove = true;
830 return true;
831 } else {
832 return false;
833 }
834 }
835
836 static CxIterator cx_ll_iterator( 865 static CxIterator cx_ll_iterator(
837 struct cx_list_s const *list, 866 struct cx_list_s const *list,
838 size_t index, 867 size_t index,
839 bool backwards 868 bool backwards
840 ) { 869 ) {
841 CxIterator iter; 870 CxIterator iter;
842 iter.index = index; 871 iter.index = index;
843 iter.src_handle = list; 872 iter.src_handle.c = list;
844 iter.elem_handle = cx_ll_node_at((cx_linked_list const *) list, index); 873 iter.elem_handle = cx_ll_node_at((cx_linked_list const *) list, index);
874 iter.elem_size = list->collection.elem_size;
875 iter.elem_count = list->collection.size;
845 iter.base.valid = cx_ll_iter_valid; 876 iter.base.valid = cx_ll_iter_valid;
846 iter.base.current = cx_ll_iter_current; 877 iter.base.current = cx_ll_iter_current;
847 iter.base.next = backwards ? cx_ll_iter_prev : cx_ll_iter_next; 878 iter.base.next = backwards ? cx_ll_iter_prev : cx_ll_iter_next;
848 iter.base.flag_removal = cx_ll_iter_flag_rm;
849 iter.base.mutating = false; 879 iter.base.mutating = false;
850 iter.base.remove = false; 880 iter.base.remove = false;
851 return iter; 881 return iter;
852 } 882 }
853 883
854 static int cx_ll_insert_iter( 884 static int cx_ll_insert_iter(
855 CxMutIterator *iter, 885 CxIterator *iter,
856 void const *elem, 886 void const *elem,
857 int prepend 887 int prepend
858 ) { 888 ) {
859 struct cx_list_s *list = iter->src_handle; 889 struct cx_list_s *list = iter->src_handle.m;
860 cx_linked_list_node *node = iter->elem_handle; 890 cx_linked_list_node *node = iter->elem_handle;
861 if (node != NULL) { 891 if (node != NULL) {
862 assert(prepend >= 0 && prepend <= 1); 892 assert(prepend >= 0 && prepend <= 1);
863 cx_linked_list_node *choice[2] = {node, node->prev}; 893 cx_linked_list_node *choice[2] = {node, node->prev};
864 int result = cx_ll_insert_at(list, choice[prepend], elem); 894 int result = cx_ll_insert_at(list, choice[prepend], elem);
865 iter->index += prepend * (0 == result); 895 iter->index += prepend * (0 == result);
866 return result; 896 return result;
867 } else { 897 } else {
868 int result = cx_ll_insert_element(list, list->size, elem); 898 int result = cx_ll_insert_element(list, list->collection.size, elem);
869 iter->index = list->size; 899 iter->index = list->collection.size;
870 return result; 900 return result;
871 } 901 }
872 } 902 }
873 903
874 static void cx_ll_destructor(CxList *list) { 904 static void cx_ll_destructor(CxList *list) {
876 906
877 cx_linked_list_node *node = ll->begin; 907 cx_linked_list_node *node = ll->begin;
878 while (node) { 908 while (node) {
879 cx_invoke_destructor(list, node->payload); 909 cx_invoke_destructor(list, node->payload);
880 void *next = node->next; 910 void *next = node->next;
881 cxFree(list->allocator, node); 911 cxFree(list->collection.allocator, node);
882 node = next; 912 node = next;
883 } 913 }
884 914
885 cxFree(list->allocator, list); 915 cxFree(list->collection.allocator, list);
886 } 916 }
887 917
888 static cx_list_class cx_linked_list_class = { 918 static cx_list_class cx_linked_list_class = {
889 cx_ll_destructor, 919 cx_ll_destructor,
890 cx_ll_insert_element, 920 cx_ll_insert_element,
892 cx_ll_insert_iter, 922 cx_ll_insert_iter,
893 cx_ll_remove, 923 cx_ll_remove,
894 cx_ll_clear, 924 cx_ll_clear,
895 cx_ll_swap, 925 cx_ll_swap,
896 cx_ll_at, 926 cx_ll_at,
897 cx_ll_find, 927 cx_ll_find_remove,
898 cx_ll_sort, 928 cx_ll_sort,
899 cx_ll_compare, 929 cx_ll_compare,
900 cx_ll_reverse, 930 cx_ll_reverse,
901 cx_ll_iterator, 931 cx_ll_iterator,
902 }; 932 };
903 933
904 CxList *cxLinkedListCreate( 934 CxList *cxLinkedListCreate(
905 CxAllocator const *allocator, 935 CxAllocator const *allocator,
906 cx_compare_func comparator, 936 cx_compare_func comparator,
907 size_t item_size 937 size_t elem_size
908 ) { 938 ) {
909 if (allocator == NULL) { 939 if (allocator == NULL) {
910 allocator = cxDefaultAllocator; 940 allocator = cxDefaultAllocator;
911 } 941 }
912 942
913 cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list)); 943 cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list));
914 if (list == NULL) return NULL; 944 if (list == NULL) return NULL;
915 945
916 list->base.cl = &cx_linked_list_class; 946 list->base.cl = &cx_linked_list_class;
917 list->base.allocator = allocator; 947 list->base.collection.allocator = allocator;
918 list->base.cmpfunc = comparator; 948
919 949 if (elem_size > 0) {
920 if (item_size > 0) { 950 list->base.collection.elem_size = elem_size;
921 list->base.item_size = item_size; 951 list->base.collection.cmpfunc = comparator;
922 } else { 952 } else {
953 list->base.collection.cmpfunc = comparator == NULL ? cx_cmp_ptr : comparator;
923 cxListStorePointers((CxList *) list); 954 cxListStorePointers((CxList *) list);
924 } 955 }
925 956
926 return (CxList *) list; 957 return (CxList *) list;
927 } 958 }

Mercurial Repository: dav

mercurial