diff -r 921f83a8943f -r d218607f5a7e src/ucx/linked_list.c --- a/src/ucx/linked_list.c Sat Mar 25 17:18:51 2023 +0100 +++ b/src/ucx/linked_list.c Fri May 05 18:02:11 2023 +0200 @@ -28,7 +28,6 @@ #include "cx/linked_list.h" #include "cx/utils.h" -#include #include #include @@ -38,8 +37,7 @@ #define ll_prev(node) CX_LL_PTR(node, loc_prev) #define ll_next(node) CX_LL_PTR(node, loc_next) #define ll_advance(node) CX_LL_PTR(node, loc_advance) -#define ll_data_f(node, follow_ptr) ((follow_ptr)?CX_LL_PTR(node, loc_data):(((char*)(node))+loc_data)) -#define ll_data(node) ll_data_f(node,follow_ptr) +#define ll_data(node) (((char*)(node))+loc_data) void *cx_linked_list_at( void const *start, @@ -58,12 +56,11 @@ return (void *) cur; } -size_t cx_linked_list_find( +ssize_t cx_linked_list_find( void const *start, ptrdiff_t loc_advance, ptrdiff_t loc_data, - bool follow_ptr, - CxListComparator cmp_func, + cx_compare_func cmp_func, void const *elem ) { assert(start != NULL); @@ -72,7 +69,7 @@ assert(cmp_func); void const *node = start; - size_t index = 0; + ssize_t index = 0; do { void *current = ll_data(node); if (cmp_func(current, elem) == 0) { @@ -81,7 +78,7 @@ node = ll_advance(node); index++; } while (node != NULL); - return index; + return -1; } void *cx_linked_list_first( @@ -282,20 +279,23 @@ return size; } +#ifndef CX_LINKED_LIST_SORT_SBO_SIZE +#define CX_LINKED_LIST_SORT_SBO_SIZE 1024 +#endif + static void *cx_linked_list_sort_merge( ptrdiff_t loc_prev, ptrdiff_t loc_next, ptrdiff_t loc_data, - bool follow_ptr, size_t length, void *ls, void *le, void *re, - CxListComparator cmp_func + cx_compare_func cmp_func ) { - const size_t sbo_len = 1024; - void *sbo[sbo_len]; - void **sorted = (length >= sbo_len) ? malloc(sizeof(void *) * length) : sbo; + void *sbo[CX_LINKED_LIST_SORT_SBO_SIZE]; + void **sorted = length >= CX_LINKED_LIST_SORT_SBO_SIZE ? + malloc(sizeof(void *) * length) : sbo; if (sorted == NULL) abort(); void *rc, *lc; @@ -343,8 +343,7 @@ ptrdiff_t loc_prev, ptrdiff_t loc_next, ptrdiff_t loc_data, - bool follow_ptr, - CxListComparator cmp_func + cx_compare_func cmp_func ) { assert(begin != NULL); assert(loc_next >= 0); @@ -378,17 +377,17 @@ re = ll_next(rc); // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them - void *sorted = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, follow_ptr, + void *sorted = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, ln + rn, ls, le, re, cmp_func); // Something left? Sort it! size_t remainder_length = cx_linked_list_size(re, loc_next); if (remainder_length > 0) { void *remainder = re; - cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, follow_ptr, cmp_func); + cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, cmp_func); // merge sorted list with (also sorted) remainder - *begin = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, follow_ptr, + *begin = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, ln + rn + remainder_length, sorted, remainder, NULL, cmp_func); } else { @@ -404,15 +403,13 @@ void const *begin_right, ptrdiff_t loc_advance, ptrdiff_t loc_data, - bool follow_ptr_left, - bool follow_ptr_right, - CxListComparator cmp_func + cx_compare_func cmp_func ) { void const *left = begin_left, *right = begin_right; while (left != NULL && right != NULL) { - void const *left_data = ll_data_f(left, follow_ptr_left); - void const *right_data = ll_data_f(right, follow_ptr_right); + void const *left_data = ll_data(left); + void const *right_data = ll_data(right); int result = cmp_func(left_data, right_data); if (result != 0) return result; left = ll_advance(left); @@ -457,6 +454,8 @@ // HIGH LEVEL LINKED LIST IMPLEMENTATION +bool CX_DISABLE_LINKED_LIST_SWAP_SBO = false; + typedef struct cx_linked_list_node cx_linked_list_node; struct cx_linked_list_node { cx_linked_list_node *prev; @@ -472,7 +471,6 @@ struct cx_list_s base; cx_linked_list_node *begin; cx_linked_list_node *end; - bool follow_ptr; } cx_linked_list; static cx_linked_list_node *cx_ll_node_at( @@ -496,14 +494,14 @@ // create the new new_node cx_linked_list_node *new_node = cxMalloc(list->allocator, - sizeof(cx_linked_list_node) + list->itemsize); + sizeof(cx_linked_list_node) + list->item_size); // sortir if failed if (new_node == NULL) return 1; // initialize new new_node new_node->prev = new_node->next = NULL; - memcpy(new_node->payload, elem, list->itemsize); + memcpy(new_node->payload, elem, list->item_size); // insert cx_linked_list *ll = (cx_linked_list *) list; @@ -518,55 +516,47 @@ return 0; } -static int cx_ll_insert( +static size_t cx_ll_insert_array( struct cx_list_s *list, size_t index, - void const *elem + void const *array, + size_t n ) { - // out-of bounds check - if (index > list->size) return 1; + // out-of bounds and corner case check + if (index > list->size || n == 0) return 0; // find position efficiently cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1); - // perform insert - return cx_ll_insert_at(list, node, elem); -} + // perform first insert + if (0 != cx_ll_insert_at(list, node, array)) { + return 1; + } + + // is there more? + if (n == 1) return 1; -static int cx_ll_add( - struct cx_list_s *list, - void const *elem -) { - return cx_ll_insert(list, list->size, elem); -} + // we now know exactly where we are + node = node == NULL ? ((cx_linked_list *) list)->begin : node->next; -static size_t cx_ll_add_array( - struct cx_list_s *list, - void const *array, - size_t n -) { - // TODO: redirect to cx_ll_insert_array - cx_for_n (i, n) { - if (cx_ll_add(list, ((char const *) array) + i * list->itemsize)) { + // we can add the remaining nodes and immedately advance to the inserted node + char const *source = array; + for (size_t i = 1; i < n; i++) { + source += list->item_size; + if (0 != cx_ll_insert_at(list, node, source)) { return i; } + node = node->next; } return n; } -static int cx_pll_insert( +static int cx_ll_insert_element( struct cx_list_s *list, size_t index, - void const *elem + void const *element ) { - return cx_ll_insert(list, index, &elem); -} - -static int cx_pll_add( - struct cx_list_s *list, - void const *elem -) { - return cx_ll_insert(list, list->size, &elem); + return 1 != cx_ll_insert_array(list, index, element, 1); } static int cx_ll_remove( @@ -579,6 +569,9 @@ // out-of-bounds check if (node == NULL) return 1; + // element destruction + cx_invoke_destructor(list, node->payload); + // remove cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end, CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node); @@ -592,6 +585,141 @@ return 0; } +static void cx_ll_clear(struct cx_list_s *list) { + if (list->size == 0) return; + + cx_linked_list *ll = (cx_linked_list *) list; + cx_linked_list_node *node = ll->begin; + while (node != NULL) { + cx_invoke_destructor(list, node->payload); + cx_linked_list_node *next = node->next; + cxFree(list->allocator, node); + node = next; + } + ll->begin = ll->end = NULL; + list->size = 0; +} + +#ifndef CX_LINKED_LIST_SWAP_SBO_SIZE +#define CX_LINKED_LIST_SWAP_SBO_SIZE 16 +#endif + +static int cx_ll_swap( + struct cx_list_s *list, + size_t i, + size_t j +) { + if (i >= list->size || j >= list->size) return 1; + if (i == j) return 0; + + // perform an optimized search that finds both elements in one run + cx_linked_list *ll = (cx_linked_list *) list; + size_t mid = list->size / 2; + size_t left, right; + if (i < j) { + left = i; + right = j; + } else { + left = j; + right = i; + } + cx_linked_list_node *nleft, *nright; + if (left < mid && right < mid) { + // case 1: both items left from mid + nleft = cx_ll_node_at(ll, left); + nright = nleft; + for (size_t c = left; c < right; c++) { + nright = nright->next; + } + } else if (left >= mid && right >= mid) { + // case 2: both items right from mid + nright = cx_ll_node_at(ll, right); + nleft = nright; + for (size_t c = right; c > left; c--) { + nleft = nleft->prev; + } + } else { + // case 3: one item left, one item right + + // chose the closest to begin / end + size_t closest; + size_t other; + size_t diff2boundary = list->size - right - 1; + if (left <= diff2boundary) { + closest = left; + other = right; + nleft = cx_ll_node_at(ll, left); + } else { + closest = right; + other = left; + diff2boundary = left; + nright = cx_ll_node_at(ll, right); + } + + // is other element closer to us or closer to boundary? + if (right - left <= diff2boundary) { + // search other element starting from already found element + if (closest == left) { + nright = nleft; + for (size_t c = left; c < right; c++) { + nright = nright->next; + } + } else { + nleft = nright; + for (size_t c = right; c > left; c--) { + nleft = nleft->prev; + } + } + } else { + // search other element starting at the boundary + if (closest == left) { + nright = cx_ll_node_at(ll, other); + } else { + nleft = cx_ll_node_at(ll, other); + } + } + } + + if (list->item_size > CX_LINKED_LIST_SWAP_SBO_SIZE || CX_DISABLE_LINKED_LIST_SWAP_SBO) { + cx_linked_list_node *prev = nleft->prev; + cx_linked_list_node *next = nright->next; + cx_linked_list_node *midstart = nleft->next; + cx_linked_list_node *midend = nright->prev; + + if (prev == NULL) { + ll->begin = nright; + } else { + prev->next = nright; + } + nright->prev = prev; + if (midstart == nright) { + // special case: both nodes are adjacent + nright->next = nleft; + nleft->prev = nright; + } else { + // likely case: a chain is between the two nodes + nright->next = midstart; + midstart->prev = nright; + midend->next = nleft; + nleft->prev = midend; + } + nleft->next = next; + if (next == NULL) { + ll->end = nleft; + } else { + next->prev = nleft; + } + } else { + // swap payloads to avoid relinking + char buf[CX_LINKED_LIST_SWAP_SBO_SIZE]; + memcpy(buf, nleft->payload, list->item_size); + memcpy(nleft->payload, nright->payload, list->item_size); + memcpy(nright->payload, buf, list->item_size); + } + + return 0; +} + static void *cx_ll_at( struct cx_list_s const *list, size_t index @@ -601,30 +729,20 @@ return node == NULL ? NULL : node->payload; } -static void *cx_pll_at( - struct cx_list_s const *list, - size_t index -) { - cx_linked_list *ll = (cx_linked_list *) list; - cx_linked_list_node *node = cx_ll_node_at(ll, index); - return node == NULL ? NULL : *(void **) node->payload; -} - -static size_t cx_ll_find( +static ssize_t cx_ll_find( struct cx_list_s const *list, void const *elem ) { - cx_linked_list *ll = (cx_linked_list *) list; return cx_linked_list_find(((cx_linked_list *) list)->begin, CX_LL_LOC_NEXT, CX_LL_LOC_DATA, - ll->follow_ptr, list->cmpfunc, elem); + list->cmpfunc, elem); } static void cx_ll_sort(struct cx_list_s *list) { cx_linked_list *ll = (cx_linked_list *) list; cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end, CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA, - ll->follow_ptr, list->cmpfunc); + list->cmpfunc); } static void cx_ll_reverse(struct cx_list_s *list) { @@ -640,7 +758,7 @@ cx_linked_list *right = (cx_linked_list *) other; return cx_linked_list_compare(left->begin, right->begin, CX_LL_LOC_NEXT, CX_LL_LOC_DATA, - left->follow_ptr, right->follow_ptr, list->cmpfunc); + list->cmpfunc); } static bool cx_ll_iter_valid(void const *it) { @@ -653,13 +771,15 @@ if (itbase->remove) { itbase->remove = false; struct cx_mut_iterator_s *iter = it; + struct cx_list_s *list = iter->src_handle; cx_linked_list *ll = iter->src_handle; cx_linked_list_node *node = iter->elem_handle; iter->elem_handle = node->next; + cx_invoke_destructor(list, node->payload); cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end, CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node); - ll->base.size--; - cxFree(ll->base.allocator, node); + list->size--; + cxFree(list->allocator, node); } else { struct cx_iterator_s *iter = it; iter->index++; @@ -668,18 +788,35 @@ } } +static void cx_ll_iter_prev(void *it) { + struct cx_iterator_base_s *itbase = it; + if (itbase->remove) { + itbase->remove = false; + struct cx_mut_iterator_s *iter = it; + struct cx_list_s *list = iter->src_handle; + cx_linked_list *ll = iter->src_handle; + cx_linked_list_node *node = iter->elem_handle; + iter->elem_handle = node->prev; + iter->index--; + cx_invoke_destructor(list, node->payload); + cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end, + CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node); + list->size--; + cxFree(list->allocator, node); + } else { + struct cx_iterator_s *iter = it; + iter->index--; + cx_linked_list_node *node = iter->elem_handle; + iter->elem_handle = node->prev; + } +} + static void *cx_ll_iter_current(void const *it) { struct cx_iterator_s const *iter = it; cx_linked_list_node *node = iter->elem_handle; return node->payload; } -static void *cx_pll_iter_current(void const *it) { - struct cx_iterator_s const *iter = it; - cx_linked_list_node *node = iter->elem_handle; - return *(void **) node->payload; -} - static bool cx_ll_iter_flag_rm(void *it) { struct cx_iterator_base_s *iter = it; if (iter->mutating) { @@ -692,7 +829,8 @@ static CxIterator cx_ll_iterator( struct cx_list_s const *list, - size_t index + size_t index, + bool backwards ) { CxIterator iter; iter.index = index; @@ -700,44 +838,13 @@ iter.elem_handle = cx_ll_node_at((cx_linked_list const *) list, index); iter.base.valid = cx_ll_iter_valid; iter.base.current = cx_ll_iter_current; - iter.base.next = cx_ll_iter_next; + iter.base.next = backwards ? cx_ll_iter_prev : cx_ll_iter_next; iter.base.flag_removal = cx_ll_iter_flag_rm; iter.base.mutating = false; iter.base.remove = false; return iter; } -static CxIterator cx_pll_iterator( - struct cx_list_s const *list, - size_t index -) { - CxIterator iter = cx_ll_iterator(list, index); - iter.base.current = cx_pll_iter_current; - return iter; -} - -static CxMutIterator cx_ll_mut_iterator( - struct cx_list_s *list, - size_t index -) { - CxIterator it = cx_ll_iterator(list, index); - it.base.mutating = true; - - // we know the iterators share the same memory layout - CxMutIterator iter; - memcpy(&iter, &it, sizeof(CxMutIterator)); - return iter; -} - -static CxMutIterator cx_pll_mut_iterator( - struct cx_list_s *list, - size_t index -) { - CxMutIterator iter = cx_ll_mut_iterator(list, index); - iter.base.current = cx_pll_iter_current; - return iter; -} - static int cx_ll_insert_iter( CxMutIterator *iter, void const *elem, @@ -752,20 +859,12 @@ iter->index += prepend * (0 == result); return result; } else { - int result = cx_ll_insert(list, list->size, elem); + int result = cx_ll_insert_element(list, list->size, elem); iter->index = list->size; return result; } } -static int cx_pll_insert_iter( - CxMutIterator *iter, - void const *elem, - int prepend -) { - return cx_ll_insert_iter(iter, &elem, prepend); -} - static void cx_ll_destructor(CxList *list) { cx_linked_list *ll = (cx_linked_list *) list; @@ -780,67 +879,41 @@ static cx_list_class cx_linked_list_class = { cx_ll_destructor, - cx_ll_add, - cx_ll_add_array, - cx_ll_insert, + cx_ll_insert_element, + cx_ll_insert_array, cx_ll_insert_iter, cx_ll_remove, + cx_ll_clear, + cx_ll_swap, cx_ll_at, cx_ll_find, cx_ll_sort, cx_ll_compare, cx_ll_reverse, cx_ll_iterator, - cx_ll_mut_iterator, -}; - -static cx_list_class cx_pointer_linked_list_class = { - cx_ll_destructor, - cx_pll_add, - cx_ll_add_array, - cx_pll_insert, - cx_pll_insert_iter, - cx_ll_remove, - cx_pll_at, - cx_ll_find, - cx_ll_sort, - cx_ll_compare, - cx_ll_reverse, - cx_pll_iterator, - cx_pll_mut_iterator, }; CxList *cxLinkedListCreate( CxAllocator const *allocator, - CxListComparator comparator, + cx_compare_func comparator, size_t item_size ) { + if (allocator == NULL) { + allocator = cxDefaultAllocator; + } + cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list)); if (list == NULL) return NULL; - list->follow_ptr = false; list->base.cl = &cx_linked_list_class; list->base.allocator = allocator; list->base.cmpfunc = comparator; - list->base.itemsize = item_size; - list->base.capacity = SIZE_MAX; + + if (item_size > 0) { + list->base.item_size = item_size; + } else { + cxListStorePointers((CxList *) list); + } return (CxList *) list; } - -CxList *cxPointerLinkedListCreate( - CxAllocator const *allocator, - CxListComparator comparator -) { - cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list)); - if (list == NULL) return NULL; - - list->follow_ptr = true; - list->base.cl = &cx_pointer_linked_list_class; - list->base.allocator = allocator; - list->base.cmpfunc = comparator; - list->base.itemsize = sizeof(void *); - list->base.capacity = SIZE_MAX; - - return (CxList *) list; -}