Mercurial > hg > toolkit / file comparison

comparison: ucx/linked_list.c

ucx/linked_list.c

branch
newapi
changeset 253
087cc9216f28
parent 187
24ce2c326d85
equal deleted inserted replaced
252:7d176764756d 253:087cc9216f28
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[];
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
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 {
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->item_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
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->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->size--;
778 cxFree(list->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->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,
892 cx_ll_insert_iter, 935 cx_ll_insert_iter,
893 cx_ll_remove, 936 cx_ll_remove,
894 cx_ll_clear, 937 cx_ll_clear,
895 cx_ll_swap, 938 cx_ll_swap,
896 cx_ll_at, 939 cx_ll_at,
897 cx_ll_find, 940 cx_ll_find_remove,
898 cx_ll_sort, 941 cx_ll_sort,
899 cx_ll_compare, 942 cx_ll_compare,
900 cx_ll_reverse, 943 cx_ll_reverse,
901 cx_ll_iterator, 944 cx_ll_iterator,
902 }; 945 };
913 cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list)); 956 cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list));
914 if (list == NULL) return NULL; 957 if (list == NULL) return NULL;
915 958
916 list->base.cl = &cx_linked_list_class; 959 list->base.cl = &cx_linked_list_class;
917 list->base.allocator = allocator; 960 list->base.allocator = allocator;
918 list->base.cmpfunc = comparator;
919 961
920 if (item_size > 0) { 962 if (item_size > 0) {
921 list->base.item_size = item_size; 963 list->base.item_size = item_size;
922 } else { 964 list->base.cmpfunc = comparator;
965 } else {
966 list->base.cmpfunc = comparator == NULL ? cx_cmp_ptr : comparator;
923 cxListStorePointers((CxList *) list); 967 cxListStorePointers((CxList *) list);
924 } 968 }
925 969
926 return (CxList *) list; 970 return (CxList *) list;
927 } 971 }

Mercurial Repository: toolkit

mercurial