Mercurial > hg > dav / file comparison

comparison: ucx/linked_list.c

ucx/linked_list.c

changeset 854
1c8401ece69e
parent 852
83fdf679df99
equal deleted inserted replaced
853:2ad93ebdc8d9 854:1c8401ece69e
54 i < index ? i++ : i--; 54 i < index ? i++ : i--;
55 } 55 }
56 return (void *) cur; 56 return (void *) cur;
57 } 57 }
58 58
59 ssize_t cx_linked_list_find( 59 void *cx_linked_list_find(
60 const void *start, 60 const void *start,
61 ptrdiff_t loc_advance, 61 ptrdiff_t loc_advance,
62 ptrdiff_t loc_data, 62 ptrdiff_t loc_data,
63 cx_compare_func cmp_func, 63 cx_compare_func cmp_func,
64 const void *elem 64 const void *elem,
65 ) { 65 size_t *found_index
66 void *dummy; 66 ) {
67 return cx_linked_list_find_node(
68 &dummy, start,
69 loc_advance, loc_data,
70 cmp_func, elem
71 );
72 }
73
74 ssize_t cx_linked_list_find_node(
75 void **result,
76 const void *start,
77 ptrdiff_t loc_advance,
78 ptrdiff_t loc_data,
79 cx_compare_func cmp_func,
80 const void *elem
81 ) {
82 assert(result != NULL);
83 assert(start != NULL); 67 assert(start != NULL);
84 assert(loc_advance >= 0); 68 assert(loc_advance >= 0);
85 assert(loc_data >= 0); 69 assert(loc_data >= 0);
86 assert(cmp_func); 70 assert(cmp_func);
87 71
88 const void *node = start; 72 void *node = (void*) start;
89 ssize_t index = 0; 73 size_t index = 0;
90 do { 74 do {
91 void *current = ll_data(node); 75 void *current = ll_data(node);
92 if (cmp_func(current, elem) == 0) { 76 if (cmp_func(current, elem) == 0) {
93 *result = (void *) node; 77 if (found_index != NULL) {
94 return index; 78 *found_index = index;
79 }
80 return node;
95 } 81 }
96 node = ll_advance(node); 82 node = ll_advance(node);
97 index++; 83 index++;
98 } while (node != NULL); 84 } while (node != NULL);
99 *result = NULL; 85 return NULL;
100 return -1;
101 } 86 }
102 87
103 void *cx_linked_list_first( 88 void *cx_linked_list_first(
104 const void *node, 89 const void *node,
105 ptrdiff_t loc_prev 90 ptrdiff_t loc_prev
808 node = next; 793 node = next;
809 } 794 }
810 ll->begin = ll->end = NULL; 795 ll->begin = ll->end = NULL;
811 list->collection.size = 0; 796 list->collection.size = 0;
812 } 797 }
813
814 #ifndef CX_LINKED_LIST_SWAP_SBO_SIZE
815 #define CX_LINKED_LIST_SWAP_SBO_SIZE 128
816 #endif
817 const unsigned cx_linked_list_swap_sbo_size = CX_LINKED_LIST_SWAP_SBO_SIZE;
818 798
819 static int cx_ll_swap( 799 static int cx_ll_swap(
820 struct cx_list_s *list, 800 struct cx_list_s *list,
821 size_t i, 801 size_t i,
822 size_t j 802 size_t j
892 nleft = cx_ll_node_at(ll, other); 872 nleft = cx_ll_node_at(ll, other);
893 } 873 }
894 } 874 }
895 } 875 }
896 876
897 if (list->collection.elem_size > CX_LINKED_LIST_SWAP_SBO_SIZE) { 877 cx_linked_list_node *prev = nleft->prev;
898 cx_linked_list_node *prev = nleft->prev; 878 cx_linked_list_node *next = nright->next;
899 cx_linked_list_node *next = nright->next; 879 cx_linked_list_node *midstart = nleft->next;
900 cx_linked_list_node *midstart = nleft->next; 880 cx_linked_list_node *midend = nright->prev;
901 cx_linked_list_node *midend = nright->prev; 881
902 882 if (prev == NULL) {
903 if (prev == NULL) { 883 ll->begin = nright;
904 ll->begin = nright; 884 } else {
905 } else { 885 prev->next = nright;
906 prev->next = nright; 886 }
907 } 887 nright->prev = prev;
908 nright->prev = prev; 888 if (midstart == nright) {
909 if (midstart == nright) { 889 // special case: both nodes are adjacent
910 // special case: both nodes are adjacent 890 nright->next = nleft;
911 nright->next = nleft; 891 nleft->prev = nright;
912 nleft->prev = nright; 892 } else {
913 } else { 893 // likely case: a chain is between the two nodes
914 // likely case: a chain is between the two nodes 894 nright->next = midstart;
915 nright->next = midstart; 895 midstart->prev = nright;
916 midstart->prev = nright; 896 midend->next = nleft;
917 midend->next = nleft; 897 nleft->prev = midend;
918 nleft->prev = midend; 898 }
919 } 899 nleft->next = next;
920 nleft->next = next; 900 if (next == NULL) {
921 if (next == NULL) { 901 ll->end = nleft;
922 ll->end = nleft; 902 } else {
923 } else { 903 next->prev = nleft;
924 next->prev = nleft;
925 }
926 } else {
927 // swap payloads to avoid relinking
928 char buf[CX_LINKED_LIST_SWAP_SBO_SIZE];
929 memcpy(buf, nleft->payload, list->collection.elem_size);
930 memcpy(nleft->payload, nright->payload, list->collection.elem_size);
931 memcpy(nright->payload, buf, list->collection.elem_size);
932 } 904 }
933 905
934 return 0; 906 return 0;
935 } 907 }
936 908
941 cx_linked_list *ll = (cx_linked_list *) list; 913 cx_linked_list *ll = (cx_linked_list *) list;
942 cx_linked_list_node *node = cx_ll_node_at(ll, index); 914 cx_linked_list_node *node = cx_ll_node_at(ll, index);
943 return node == NULL ? NULL : node->payload; 915 return node == NULL ? NULL : node->payload;
944 } 916 }
945 917
946 static ssize_t cx_ll_find_remove( 918 static size_t cx_ll_find_remove(
947 struct cx_list_s *list, 919 struct cx_list_s *list,
948 const void *elem, 920 const void *elem,
949 bool remove 921 bool remove
950 ) { 922 ) {
923 size_t index;
924 cx_linked_list *ll = ((cx_linked_list *) list);
925 cx_linked_list_node *node = cx_linked_list_find(
926 ll->begin,
927 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
928 list->collection.cmpfunc, elem,
929 &index
930 );
931 if (node == NULL) {
932 return list->collection.size;
933 }
951 if (remove) { 934 if (remove) {
952 cx_linked_list *ll = ((cx_linked_list *) list); 935 cx_invoke_destructor(list, node->payload);
953 cx_linked_list_node *node; 936 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
954 ssize_t index = cx_linked_list_find_node( 937 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
955 (void **) &node, 938 list->collection.size--;
956 ll->begin, 939 cxFree(list->collection.allocator, node);
957 CX_LL_LOC_NEXT, CX_LL_LOC_DATA, 940 }
958 list->collection.cmpfunc, elem 941 return index;
959 );
960 if (node != NULL) {
961 cx_invoke_destructor(list, node->payload);
962 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
963 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
964 list->collection.size--;
965 cxFree(list->collection.allocator, node);
966 }
967 return index;
968 } else {
969 return cx_linked_list_find(
970 ((cx_linked_list *) list)->begin,
971 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
972 list->collection.cmpfunc, elem
973 );
974 }
975 } 942 }
976 943
977 static void cx_ll_sort(struct cx_list_s *list) { 944 static void cx_ll_sort(struct cx_list_s *list) {
978 cx_linked_list *ll = (cx_linked_list *) list; 945 cx_linked_list *ll = (cx_linked_list *) list;
979 cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end, 946 cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end,
1136 allocator = cxDefaultAllocator; 1103 allocator = cxDefaultAllocator;
1137 } 1104 }
1138 1105
1139 cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list)); 1106 cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list));
1140 if (list == NULL) return NULL; 1107 if (list == NULL) return NULL;
1141 1108 cx_list_init((CxList*)list, &cx_linked_list_class,
1142 list->base.cl = &cx_linked_list_class; 1109 allocator, comparator, elem_size);
1143 list->base.collection.allocator = allocator;
1144
1145 if (elem_size > 0) {
1146 list->base.collection.elem_size = elem_size;
1147 list->base.collection.cmpfunc = comparator;
1148 } else {
1149 list->base.collection.cmpfunc = comparator == NULL ? cx_cmp_ptr : comparator;
1150 cxListStorePointers((CxList *) list);
1151 }
1152 1110
1153 return (CxList *) list; 1111 return (CxList *) list;
1154 } 1112 }

Mercurial Repository: dav

mercurial