Mercurial > hg > ucx / file comparison

comparison: src/linked_list.c

src/linked_list.c

changeset 1367
6b3d52dd176e
parent 1360
8b29d732f97b
equal deleted inserted replaced
1366:70ce877c838a 1367:6b3d52dd176e
562 *begin = prev; 562 *begin = prev;
563 } 563 }
564 564
565 // HIGH LEVEL LINKED LIST IMPLEMENTATION 565 // HIGH LEVEL LINKED LIST IMPLEMENTATION
566 566
567 typedef struct cx_linked_list_node cx_linked_list_node; 567 static void *cx_ll_node_at(
568 // IMPORTANT: the layout must stay exactly like this, because kv_list.c uses that!
569 struct cx_linked_list_node {
570 cx_linked_list_node *prev;
571 cx_linked_list_node *next;
572 char payload[];
573 };
574
575 #define CX_LL_LOC_PREV offsetof(cx_linked_list_node, prev)
576 #define CX_LL_LOC_NEXT offsetof(cx_linked_list_node, next)
577 #define CX_LL_LOC_DATA offsetof(cx_linked_list_node, payload)
578
579 typedef struct {
580 struct cx_list_s base;
581 cx_linked_list_node *begin;
582 cx_linked_list_node *end;
583 } cx_linked_list;
584
585 static cx_linked_list_node *cx_ll_node_at(
586 const cx_linked_list *list, 568 const cx_linked_list *list,
587 size_t index 569 size_t index
588 ) { 570 ) {
589 if (index >= list->base.collection.size) { 571 if (index >= list->base.collection.size) {
590 return NULL; 572 return NULL;
591 } else if (index > list->base.collection.size / 2) { 573 } else if (index > list->base.collection.size / 2) {
592 return cx_linked_list_at(list->end, list->base.collection.size - 1, CX_LL_LOC_PREV, index); 574 return cx_linked_list_at(list->end, list->base.collection.size - 1, list->loc_prev, index);
593 } else { 575 } else {
594 return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index); 576 return cx_linked_list_at(list->begin, 0, list->loc_next, index);
595 } 577 }
596 } 578 }
597 579
598 static cx_linked_list_node *cx_ll_malloc_node(const struct cx_list_s *list) { 580 static void *cx_ll_malloc_node(const cx_linked_list *list) {
599 return cxMalloc(list->collection.allocator, 581 return cxZalloc(list->base.collection.allocator,
600 sizeof(cx_linked_list_node) + list->collection.elem_size); 582 list->loc_data + list->base.collection.elem_size + list->extra_data_len);
601 } 583 }
602 584
603 static int cx_ll_insert_at( 585 static int cx_ll_insert_at(
604 struct cx_list_s *list, 586 struct cx_list_s *list,
605 cx_linked_list_node *node, 587 void *node,
606 const void *elem 588 const void *elem
607 ) { 589 ) {
590 cx_linked_list *ll = (cx_linked_list *) list;
608 591
609 // create the new new_node 592 // create the new new_node
610 cx_linked_list_node *new_node = cx_ll_malloc_node(list); 593 void *new_node = cx_ll_malloc_node(ll);
611 594
612 // sortir if failed 595 // sortir if failed
613 if (new_node == NULL) return 1; 596 if (new_node == NULL) return 1;
614 597
615 // initialize new new_node 598 // copy the data
616 new_node->prev = new_node->next = NULL;
617 if (elem != NULL) { 599 if (elem != NULL) {
618 memcpy(new_node->payload, elem, list->collection.elem_size); 600 memcpy((char*)new_node + ll->loc_data, elem, list->collection.elem_size);
619 } 601 }
620 602
621 // insert 603 // insert
622 cx_linked_list *ll = (cx_linked_list *) list;
623 cx_linked_list_insert_chain( 604 cx_linked_list_insert_chain(
624 (void **) &ll->begin, (void **) &ll->end, 605 &ll->begin, &ll->end,
625 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, 606 ll->loc_prev, ll->loc_next,
626 node, new_node, new_node 607 node, new_node, new_node
627 ); 608 );
628 609
629 // increase the size and return 610 // increase the size and return
630 list->collection.size++; 611 list->collection.size++;
639 ) { 620 ) {
640 // out-of bounds and corner case check 621 // out-of bounds and corner case check
641 if (index > list->collection.size || n == 0) return 0; 622 if (index > list->collection.size || n == 0) return 0;
642 623
643 // find position efficiently 624 // find position efficiently
644 cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1); 625 void *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1);
645 626
646 // perform first insert 627 // perform first insert
647 if (0 != cx_ll_insert_at(list, node, array)) return 1; 628 if (0 != cx_ll_insert_at(list, node, array)) return 1;
648 629
649 // is there more? 630 // is there more?
650 if (n == 1) return 1; 631 if (n == 1) return 1;
651 632
652 // we now know exactly where we are 633 // we now know exactly where we are
653 node = node == NULL ? ((cx_linked_list *) list)->begin : node->next; 634 cx_linked_list *ll = (cx_linked_list *) list;
635 node = node == NULL ? ((cx_linked_list *) list)->begin : CX_LL_PTR(node, ll->loc_next);
654 636
655 // we can add the remaining nodes and immediately advance to the inserted node 637 // we can add the remaining nodes and immediately advance to the inserted node
656 const char *source = array; 638 const char *source = array;
657 for (size_t i = 1; i < n; i++) { 639 for (size_t i = 1; i < n; i++) {
658 source += list->collection.elem_size; 640 source += list->collection.elem_size;
659 if (0 != cx_ll_insert_at(list, node, source)) return i; 641 if (0 != cx_ll_insert_at(list, node, source)) return i;
660 node = node->next; 642 node = CX_LL_PTR(node, ll->loc_next);
661 } 643 }
662 return n; 644 return n;
663 } 645 }
664 646
665 static void *cx_ll_insert_element( 647 static void *cx_ll_insert_element(
669 ) { 651 ) {
670 // out-of-bounds check 652 // out-of-bounds check
671 if (index > list->collection.size) return NULL; 653 if (index > list->collection.size) return NULL;
672 654
673 // find position efficiently 655 // find position efficiently
674 cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1); 656 void *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1);
675 657
676 // perform first insert 658 // perform first insert
677 if (cx_ll_insert_at(list, node, element)) return NULL; 659 if (cx_ll_insert_at(list, node, element)) return NULL;
678 660
679 // return a pointer to the data of the inserted node 661 // return a pointer to the data of the inserted node
662 cx_linked_list *ll = (cx_linked_list *) list;
680 if (node == NULL) { 663 if (node == NULL) {
681 return ((cx_linked_list *) list)->begin->payload; 664 return (char*)(ll->begin) + ll->loc_data;
682 } else { 665 } else {
683 return node->next->payload; 666 char *next = CX_LL_PTR(node, ll->loc_next);
667 return next + ll->loc_data;
684 } 668 }
685 } 669 }
686 670
687 static _Thread_local cx_compare_func cx_ll_insert_sorted_cmp_func; 671 static _Thread_local cx_compare_func cx_ll_insert_sorted_cmp_func;
672 static _Thread_local off_t cx_ll_insert_sorted_loc_data;
688 673
689 static int cx_ll_insert_sorted_cmp_helper(const void *l, const void *r) { 674 static int cx_ll_insert_sorted_cmp_helper(const void *l, const void *r) {
690 const cx_linked_list_node *left = l; 675 const char *left = (const char*)l + cx_ll_insert_sorted_loc_data;
691 const cx_linked_list_node *right = r; 676 const char *right = (const char*)r + cx_ll_insert_sorted_loc_data;
692 return cx_ll_insert_sorted_cmp_func(left->payload, right->payload); 677 return cx_ll_insert_sorted_cmp_func(left, right);
693 } 678 }
694 679
695 static size_t cx_ll_insert_sorted( 680 static size_t cx_ll_insert_sorted(
696 struct cx_list_s *list, 681 struct cx_list_s *list,
697 const void *array, 682 const void *array,
698 size_t n 683 size_t n
699 ) { 684 ) {
685 cx_linked_list *ll = (cx_linked_list *) list;
686
700 // special case 687 // special case
701 if (n == 0) return 0; 688 if (n == 0) return 0;
702 689
703 // create a new chain of nodes 690 // create a new chain of nodes
704 cx_linked_list_node *chain = cx_ll_malloc_node(list); 691 void *chain = cx_ll_malloc_node(ll);
705 if (chain == NULL) return 0; 692 if (chain == NULL) return 0;
706 693
707 memcpy(chain->payload, array, list->collection.elem_size); 694 memcpy((char*)chain + ll->loc_data, array, list->collection.elem_size);
708 chain->prev = NULL;
709 chain->next = NULL;
710 695
711 // add all elements from the array to that chain 696 // add all elements from the array to that chain
712 cx_linked_list_node *prev = chain; 697 void *prev = chain;
713 const char *src = array; 698 const char *src = array;
714 size_t inserted = 1; 699 size_t inserted = 1;
715 for (; inserted < n; inserted++) { 700 for (; inserted < n; inserted++) {
716 cx_linked_list_node *next = cx_ll_malloc_node(list); 701 void *next = cx_ll_malloc_node(ll);
717 if (next == NULL) break; 702 if (next == NULL) break;
718 src += list->collection.elem_size; 703 src += list->collection.elem_size;
719 memcpy(next->payload, src, list->collection.elem_size); 704 memcpy((char*)next + ll->loc_data, src, list->collection.elem_size);
720 prev->next = next; 705 CX_LL_PTR(prev, ll->loc_next) = next;
721 next->prev = prev; 706 CX_LL_PTR(next, ll->loc_prev) = prev;
722 prev = next; 707 prev = next;
723 } 708 }
724 prev->next = NULL; 709 CX_LL_PTR(prev, ll->loc_next) = NULL;
725 710
726 // invoke the low level function 711 // invoke the low level function
727 cx_linked_list *ll = (cx_linked_list *) list;
728 cx_ll_insert_sorted_cmp_func = list->collection.cmpfunc; 712 cx_ll_insert_sorted_cmp_func = list->collection.cmpfunc;
713 cx_ll_insert_sorted_loc_data = ll->loc_data;
729 cx_linked_list_insert_sorted_chain( 714 cx_linked_list_insert_sorted_chain(
730 (void **) &ll->begin, 715 &ll->begin,
731 (void **) &ll->end, 716 &ll->end,
732 CX_LL_LOC_PREV, 717 ll->loc_prev,
733 CX_LL_LOC_NEXT, 718 ll->loc_next,
734 chain, 719 chain,
735 cx_ll_insert_sorted_cmp_helper 720 cx_ll_insert_sorted_cmp_helper
736 ); 721 );
737 722
738 // adjust the list metadata 723 // adjust the list metadata
746 size_t index, 731 size_t index,
747 size_t num, 732 size_t num,
748 void *targetbuf 733 void *targetbuf
749 ) { 734 ) {
750 cx_linked_list *ll = (cx_linked_list *) list; 735 cx_linked_list *ll = (cx_linked_list *) list;
751 cx_linked_list_node *node = cx_ll_node_at(ll, index); 736 void *node = cx_ll_node_at(ll, index);
752 737
753 // out-of-bounds check 738 // out-of-bounds check
754 if (node == NULL) return 0; 739 if (node == NULL) return 0;
755 740
756 // remove 741 // remove
757 size_t removed = cx_linked_list_remove_chain( 742 size_t removed = cx_linked_list_remove_chain(
758 (void **) &ll->begin, 743 (void **) &ll->begin,
759 (void **) &ll->end, 744 (void **) &ll->end,
760 CX_LL_LOC_PREV, 745 ll->loc_prev,
761 CX_LL_LOC_NEXT, 746 ll->loc_next,
762 node, 747 node,
763 num 748 num
764 ); 749 );
765 750
766 // adjust size 751 // adjust size
767 list->collection.size -= removed; 752 list->collection.size -= removed;
768 753
769 // copy or destroy the removed chain 754 // copy or destroy the removed chain
770 if (targetbuf == NULL) { 755 if (targetbuf == NULL) {
771 cx_linked_list_node *n = node; 756 char *n = node;
772 for (size_t i = 0; i < removed; i++) { 757 for (size_t i = 0; i < removed; i++) {
773 // element destruction 758 // element destruction
774 cx_invoke_destructor(list, n->payload); 759 cx_invoke_destructor(list, n + ll->loc_data);
775 760
776 // free the node and advance 761 // free the node and advance
777 void *next = n->next; 762 void *next = CX_LL_PTR(n, ll->loc_next);
778 cxFree(list->collection.allocator, n); 763 cxFree(list->collection.allocator, n);
779 n = next; 764 n = next;
780 } 765 }
781 } else { 766 } else {
782 char *dest = targetbuf; 767 char *dest = targetbuf;
783 cx_linked_list_node *n = node; 768 char *n = node;
784 for (size_t i = 0; i < removed; i++) { 769 for (size_t i = 0; i < removed; i++) {
785 // copy payload 770 // copy payload
786 memcpy(dest, n->payload, list->collection.elem_size); 771 memcpy(dest, n + ll->loc_data, list->collection.elem_size);
787 772
788 // advance target buffer 773 // advance target buffer
789 dest += list->collection.elem_size; 774 dest += list->collection.elem_size;
790 775
791 // free the node and advance 776 // free the node and advance
792 void *next = n->next; 777 void *next = CX_LL_PTR(n, ll->loc_next);
793 cxFree(list->collection.allocator, n); 778 cxFree(list->collection.allocator, n);
794 n = next; 779 n = next;
795 } 780 }
796 } 781 }
797 782
800 785
801 static void cx_ll_clear(struct cx_list_s *list) { 786 static void cx_ll_clear(struct cx_list_s *list) {
802 if (list->collection.size == 0) return; 787 if (list->collection.size == 0) return;
803 788
804 cx_linked_list *ll = (cx_linked_list *) list; 789 cx_linked_list *ll = (cx_linked_list *) list;
805 cx_linked_list_node *node = ll->begin; 790 char *node = ll->begin;
806 while (node != NULL) { 791 while (node != NULL) {
807 cx_invoke_destructor(list, node->payload); 792 cx_invoke_destructor(list, node + ll->loc_data);
808 cx_linked_list_node *next = node->next; 793 void *next = CX_LL_PTR(node, ll->loc_next);
809 cxFree(list->collection.allocator, node); 794 cxFree(list->collection.allocator, node);
810 node = next; 795 node = next;
811 } 796 }
812 ll->begin = ll->end = NULL; 797 ll->begin = ll->end = NULL;
813 list->collection.size = 0; 798 list->collection.size = 0;
830 right = j; 815 right = j;
831 } else { 816 } else {
832 left = j; 817 left = j;
833 right = i; 818 right = i;
834 } 819 }
835 cx_linked_list_node *nleft = NULL, *nright = NULL; 820 void *nleft = NULL, *nright = NULL;
836 if (left < mid && right < mid) { 821 if (left < mid && right < mid) {
837 // case 1: both items left from mid 822 // case 1: both items left from mid
838 nleft = cx_ll_node_at(ll, left); 823 nleft = cx_ll_node_at(ll, left);
839 assert(nleft != NULL); 824 assert(nleft != NULL);
840 nright = nleft; 825 nright = nleft;
841 for (size_t c = left; c < right; c++) { 826 for (size_t c = left; c < right; c++) {
842 nright = nright->next; 827 nright = CX_LL_PTR(nright, ll->loc_next);
843 } 828 }
844 } else if (left >= mid && right >= mid) { 829 } else if (left >= mid && right >= mid) {
845 // case 2: both items right from mid 830 // case 2: both items right from mid
846 nright = cx_ll_node_at(ll, right); 831 nright = cx_ll_node_at(ll, right);
847 assert(nright != NULL); 832 assert(nright != NULL);
848 nleft = nright; 833 nleft = nright;
849 for (size_t c = right; c > left; c--) { 834 for (size_t c = right; c > left; c--) {
850 nleft = nleft->prev; 835 nleft = CX_LL_PTR(nleft, ll->loc_prev);
851 } 836 }
852 } else { 837 } else {
853 // case 3: one item left, one item right 838 // case 3: one item left, one item right
854 839
855 // chose the closest to begin / end 840 // chose the closest to begin / end
871 if (right - left <= diff2boundary) { 856 if (right - left <= diff2boundary) {
872 // search other element starting from already found element 857 // search other element starting from already found element
873 if (closest == left) { 858 if (closest == left) {
874 nright = nleft; 859 nright = nleft;
875 for (size_t c = left; c < right; c++) { 860 for (size_t c = left; c < right; c++) {
876 nright = nright->next; 861 nright = CX_LL_PTR(nright, ll->loc_next);
877 } 862 }
878 } else { 863 } else {
879 nleft = nright; 864 nleft = nright;
880 for (size_t c = right; c > left; c--) { 865 for (size_t c = right; c > left; c--) {
881 nleft = nleft->prev; 866 nleft = CX_LL_PTR(nleft, ll->loc_prev);
882 } 867 }
883 } 868 }
884 } else { 869 } else {
885 // search other element starting at the boundary 870 // search other element starting at the boundary
886 if (closest == left) { 871 if (closest == left) {
889 nleft = cx_ll_node_at(ll, other); 874 nleft = cx_ll_node_at(ll, other);
890 } 875 }
891 } 876 }
892 } 877 }
893 878
894 cx_linked_list_node *prev = nleft->prev; 879 void *prev = CX_LL_PTR(nleft, ll->loc_prev);
895 cx_linked_list_node *next = nright->next; 880 void *next = CX_LL_PTR(nright, ll->loc_next);
896 cx_linked_list_node *midstart = nleft->next; 881 void *midstart = CX_LL_PTR(nleft, ll->loc_next);
897 cx_linked_list_node *midend = nright->prev; 882 void *midend = CX_LL_PTR(nright, ll->loc_prev);
898 883
899 if (prev == NULL) { 884 if (prev == NULL) {
900 ll->begin = nright; 885 ll->begin = nright;
901 } else { 886 } else {
902 prev->next = nright; 887 CX_LL_PTR(prev, ll->loc_next) = nright;
903 } 888 }
904 nright->prev = prev; 889 CX_LL_PTR(nright, ll->loc_prev) = prev;
905 if (midstart == nright) { 890 if (midstart == nright) {
906 // special case: both nodes are adjacent 891 // special case: both nodes are adjacent
907 nright->next = nleft; 892 CX_LL_PTR(nright, ll->loc_next) = nleft;
908 nleft->prev = nright; 893 CX_LL_PTR(nleft, ll->loc_prev) = nright;
909 } else { 894 } else {
910 // likely case: a chain is between the two nodes 895 // likely case: a chain is between the two nodes
911 nright->next = midstart; 896 CX_LL_PTR(nright, ll->loc_next) = midstart;
912 midstart->prev = nright; 897 CX_LL_PTR(midstart, ll->loc_prev) = nright;
913 midend->next = nleft; 898 CX_LL_PTR(midend, ll->loc_next) = nleft;
914 nleft->prev = midend; 899 CX_LL_PTR(nleft, ll->loc_prev) = midend;
915 } 900 }
916 nleft->next = next; 901 CX_LL_PTR(nleft, ll->loc_next) = next;
917 if (next == NULL) { 902 if (next == NULL) {
918 ll->end = nleft; 903 ll->end = nleft;
919 } else { 904 } else {
920 next->prev = nleft; 905 CX_LL_PTR(next, ll->loc_prev) = nleft;
921 } 906 }
922 907
923 return 0; 908 return 0;
924 } 909 }
925 910
926 static void *cx_ll_at( 911 static void *cx_ll_at(
927 const struct cx_list_s *list, 912 const struct cx_list_s *list,
928 size_t index 913 size_t index
929 ) { 914 ) {
930 cx_linked_list *ll = (cx_linked_list *) list; 915 cx_linked_list *ll = (cx_linked_list *) list;
931 cx_linked_list_node *node = cx_ll_node_at(ll, index); 916 char *node = cx_ll_node_at(ll, index);
932 return node == NULL ? NULL : node->payload; 917 return node == NULL ? NULL : node + ll->loc_data;
933 } 918 }
934 919
935 static size_t cx_ll_find_remove( 920 static size_t cx_ll_find_remove(
936 struct cx_list_s *list, 921 struct cx_list_s *list,
937 const void *elem, 922 const void *elem,
938 bool remove 923 bool remove
939 ) { 924 ) {
940 if (list->collection.size == 0) return 0; 925 if (list->collection.size == 0) return 0;
941 926
942 size_t index; 927 size_t index;
943 cx_linked_list *ll = ((cx_linked_list *) list); 928 cx_linked_list *ll = (cx_linked_list *) list;
944 cx_linked_list_node *node = cx_linked_list_find( 929 char *node = cx_linked_list_find(
945 ll->begin, 930 ll->begin,
946 CX_LL_LOC_NEXT, CX_LL_LOC_DATA, 931 ll->loc_next, ll->loc_data,
947 list->collection.cmpfunc, elem, 932 list->collection.cmpfunc, elem,
948 &index 933 &index
949 ); 934 );
950 if (node == NULL) { 935 if (node == NULL) {
951 return list->collection.size; 936 return list->collection.size;
952 } 937 }
953 if (remove) { 938 if (remove) {
954 cx_invoke_destructor(list, node->payload); 939 cx_invoke_destructor(list, node + ll->loc_data);
955 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end, 940 cx_linked_list_remove(&ll->begin, &ll->end,
956 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node); 941 ll->loc_prev, ll->loc_next, node);
957 list->collection.size--; 942 list->collection.size--;
958 cxFree(list->collection.allocator, node); 943 cxFree(list->collection.allocator, node);
959 } 944 }
960 return index; 945 return index;
961 } 946 }
962 947
963 static void cx_ll_sort(struct cx_list_s *list) { 948 static void cx_ll_sort(struct cx_list_s *list) {
964 cx_linked_list *ll = (cx_linked_list *) list; 949 cx_linked_list *ll = (cx_linked_list *) list;
965 cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end, 950 cx_linked_list_sort(&ll->begin, &ll->end,
966 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA, 951 ll->loc_prev, ll->loc_next, ll->loc_data,
967 list->collection.cmpfunc); 952 list->collection.cmpfunc);
968 } 953 }
969 954
970 static void cx_ll_reverse(struct cx_list_s *list) { 955 static void cx_ll_reverse(struct cx_list_s *list) {
971 cx_linked_list *ll = (cx_linked_list *) list; 956 cx_linked_list *ll = (cx_linked_list *) list;
972 cx_linked_list_reverse((void **) &ll->begin, (void **) &ll->end, CX_LL_LOC_PREV, CX_LL_LOC_NEXT); 957 cx_linked_list_reverse(&ll->begin, &ll->end, ll->loc_prev, ll->loc_next);
973 } 958 }
974 959
975 static int cx_ll_compare( 960 static int cx_ll_compare(
976 const struct cx_list_s *list, 961 const struct cx_list_s *list,
977 const struct cx_list_s *other 962 const struct cx_list_s *other
978 ) { 963 ) {
979 cx_linked_list *left = (cx_linked_list *) list; 964 cx_linked_list *left = (cx_linked_list *) list;
980 cx_linked_list *right = (cx_linked_list *) other; 965 cx_linked_list *right = (cx_linked_list *) other;
966 assert(left->loc_next == right->loc_next);
967 assert(left->loc_data == right->loc_data);
981 return cx_linked_list_compare(left->begin, right->begin, 968 return cx_linked_list_compare(left->begin, right->begin,
982 CX_LL_LOC_NEXT, CX_LL_LOC_DATA, 969 left->loc_next, left->loc_data,
983 list->collection.cmpfunc); 970 list->collection.cmpfunc);
984 } 971 }
985 972
986 static bool cx_ll_iter_valid(const void *it) { 973 static bool cx_ll_iter_valid(const void *it) {
987 const struct cx_iterator_s *iter = it; 974 const struct cx_iterator_s *iter = it;
992 struct cx_iterator_s *iter = it; 979 struct cx_iterator_s *iter = it;
993 if (iter->base.remove) { 980 if (iter->base.remove) {
994 iter->base.remove = false; 981 iter->base.remove = false;
995 struct cx_list_s *list = iter->src_handle.m; 982 struct cx_list_s *list = iter->src_handle.m;
996 cx_linked_list *ll = iter->src_handle.m; 983 cx_linked_list *ll = iter->src_handle.m;
997 cx_linked_list_node *node = iter->elem_handle; 984 char *node = iter->elem_handle;
998 iter->elem_handle = node->next; 985 iter->elem_handle = CX_LL_PTR(node, ll->loc_next);
999 cx_invoke_destructor(list, node->payload); 986 cx_invoke_destructor(list, node + ll->loc_data);
1000 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end, 987 cx_linked_list_remove(&ll->begin, &ll->end,
1001 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node); 988 ll->loc_prev, ll->loc_next, node);
1002 list->collection.size--; 989 list->collection.size--;
1003 cxFree(list->collection.allocator, node); 990 cxFree(list->collection.allocator, node);
1004 } else { 991 } else {
992 const cx_linked_list *ll = iter->src_handle.c;
1005 iter->index++; 993 iter->index++;
1006 cx_linked_list_node *node = iter->elem_handle; 994 void *node = iter->elem_handle;
1007 iter->elem_handle = node->next; 995 iter->elem_handle = CX_LL_PTR(node, ll->loc_next);
1008 } 996 }
1009 } 997 }
1010 998
1011 static void cx_ll_iter_prev(void *it) { 999 static void cx_ll_iter_prev(void *it) {
1012 struct cx_iterator_s *iter = it; 1000 struct cx_iterator_s *iter = it;
1013 if (iter->base.remove) { 1001 if (iter->base.remove) {
1014 iter->base.remove = false; 1002 iter->base.remove = false;
1015 struct cx_list_s *list = iter->src_handle.m; 1003 struct cx_list_s *list = iter->src_handle.m;
1016 cx_linked_list *ll = iter->src_handle.m; 1004 cx_linked_list *ll = iter->src_handle.m;
1017 cx_linked_list_node *node = iter->elem_handle; 1005 char *node = iter->elem_handle;
1018 iter->elem_handle = node->prev; 1006 iter->elem_handle = CX_LL_PTR(node, ll->loc_prev);
1019 iter->index--; 1007 iter->index--;
1020 cx_invoke_destructor(list, node->payload); 1008 cx_invoke_destructor(list, node + ll->loc_data);
1021 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end, 1009 cx_linked_list_remove(&ll->begin, &ll->end,
1022 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node); 1010 ll->loc_prev, ll->loc_next, node);
1023 list->collection.size--; 1011 list->collection.size--;
1024 cxFree(list->collection.allocator, node); 1012 cxFree(list->collection.allocator, node);
1025 } else { 1013 } else {
1014 const cx_linked_list *ll = iter->src_handle.c;
1026 iter->index--; 1015 iter->index--;
1027 cx_linked_list_node *node = iter->elem_handle; 1016 char *node = iter->elem_handle;
1028 iter->elem_handle = node->prev; 1017 iter->elem_handle = CX_LL_PTR(node, ll->loc_prev);
1029 } 1018 }
1030 } 1019 }
1031 1020
1032 static void *cx_ll_iter_current(const void *it) { 1021 static void *cx_ll_iter_current(const void *it) {
1033 const struct cx_iterator_s *iter = it; 1022 const struct cx_iterator_s *iter = it;
1034 cx_linked_list_node *node = iter->elem_handle; 1023 const cx_linked_list *ll = iter->src_handle.c;
1035 return node->payload; 1024 char *node = iter->elem_handle;
1025 return node + ll->loc_data;
1036 } 1026 }
1037 1027
1038 static CxIterator cx_ll_iterator( 1028 static CxIterator cx_ll_iterator(
1039 const struct cx_list_s *list, 1029 const struct cx_list_s *list,
1040 size_t index, 1030 size_t index,
1058 CxIterator *iter, 1048 CxIterator *iter,
1059 const void *elem, 1049 const void *elem,
1060 int prepend 1050 int prepend
1061 ) { 1051 ) {
1062 struct cx_list_s *list = iter->src_handle.m; 1052 struct cx_list_s *list = iter->src_handle.m;
1063 cx_linked_list_node *node = iter->elem_handle; 1053 cx_linked_list *ll = iter->src_handle.m;
1054 void *node = iter->elem_handle;
1064 if (node != NULL) { 1055 if (node != NULL) {
1065 assert(prepend >= 0 && prepend <= 1); 1056 assert(prepend >= 0 && prepend <= 1);
1066 cx_linked_list_node *choice[2] = {node, node->prev}; 1057 void *choice[2] = {node, CX_LL_PTR(node, ll->loc_prev)};
1067 int result = cx_ll_insert_at(list, choice[prepend], elem); 1058 int result = cx_ll_insert_at(list, choice[prepend], elem);
1068 if (result == 0) { 1059 if (result == 0) {
1069 iter->elem_count++; 1060 iter->elem_count++;
1070 if (prepend) { 1061 if (prepend) {
1071 iter->index++; 1062 iter->index++;
1083 } 1074 }
1084 1075
1085 static void cx_ll_destructor(CxList *list) { 1076 static void cx_ll_destructor(CxList *list) {
1086 cx_linked_list *ll = (cx_linked_list *) list; 1077 cx_linked_list *ll = (cx_linked_list *) list;
1087 1078
1088 cx_linked_list_node *node = ll->begin; 1079 char *node = ll->begin;
1089 while (node) { 1080 while (node) {
1090 cx_invoke_destructor(list, node->payload); 1081 cx_invoke_destructor(list, node + ll->loc_data);
1091 void *next = node->next; 1082 void *next = CX_LL_PTR(node, ll->loc_next);
1092 cxFree(list->collection.allocator, node); 1083 cxFree(list->collection.allocator, node);
1093 node = next; 1084 node = next;
1094 } 1085 }
1095 1086
1096 cxFree(list->collection.allocator, list); 1087 cxFree(list->collection.allocator, list);
1122 allocator = cxDefaultAllocator; 1113 allocator = cxDefaultAllocator;
1123 } 1114 }
1124 1115
1125 cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list)); 1116 cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list));
1126 if (list == NULL) return NULL; 1117 if (list == NULL) return NULL;
1118 list->extra_data_len = 0;
1119 list->loc_prev = 0;
1120 list->loc_next = sizeof(void*);
1121 list->loc_data = sizeof(void*)*2;
1127 cx_list_init((CxList*)list, &cx_linked_list_class, 1122 cx_list_init((CxList*)list, &cx_linked_list_class,
1128 allocator, comparator, elem_size); 1123 allocator, comparator, elem_size);
1129 1124
1130 return (CxList *) list; 1125 return (CxList *) list;
1131 } 1126 }

Mercurial Repository: ucx

mercurial