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, |
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 } |