# HG changeset patch # User Mike Becker # Date 1675884369 -3600 # Node ID 2e6e9d9f2159e843a341fa2d4b81ac8a9f1c60b2 # Parent dfd0403ff8b6865b61f014ad5ac433f0caa0f58e implement swap function for list elements - fixes #218 diff -r dfd0403ff8b6 -r 2e6e9d9f2159 src/array_list.c --- a/src/array_list.c Wed Feb 08 18:56:58 2023 +0100 +++ b/src/array_list.c Wed Feb 08 20:26:09 2023 +0100 @@ -292,6 +292,17 @@ return result; } +static int cx_arl_swap( + struct cx_list_s *list, + size_t i, + size_t j +) { + if (i >= list->size || j >= list->size) return 1; + cx_array_list *arl = (cx_array_list *) list; + cx_array_swap(arl->data, list->itemsize, i, j); + return 0; +} + static void *cx_arl_at( struct cx_list_s const *list, size_t index @@ -420,6 +431,7 @@ cx_arl_insert_array, cx_arl_insert_iter, cx_arl_remove, + cx_arl_swap, cx_arl_at, cx_arl_find, cx_arl_sort, diff -r dfd0403ff8b6 -r 2e6e9d9f2159 src/cx/linked_list.h --- a/src/cx/linked_list.h Wed Feb 08 18:56:58 2023 +0100 +++ b/src/cx/linked_list.h Wed Feb 08 20:26:09 2023 +0100 @@ -46,6 +46,12 @@ #endif /** + * Set this flag to true, if you want to disable the use of SBO for + * linked list swap operations. + */ +extern bool CX_DISABLE_LINKED_LIST_SWAP_SBO; + +/** * Allocates a linked list for storing elements with \p item_size bytes each. * * @remark Elements added to the list are copied, therefore a possible destructor diff -r dfd0403ff8b6 -r 2e6e9d9f2159 src/cx/list.h --- a/src/cx/list.h Wed Feb 08 18:56:58 2023 +0100 +++ b/src/cx/list.h Wed Feb 08 20:26:09 2023 +0100 @@ -164,6 +164,15 @@ ); /** + * Member function for swapping two elements. + */ + int (*swap)( + struct cx_list_s *list, + size_t i, + size_t j + ); + + /** * Member function for element lookup. */ void *(*at)( @@ -401,6 +410,26 @@ } /** + * Swaps two items in the list. + * + * Implementations should only allocate temporary memory for the swap, if + * it is necessary. + * + * @param list the list + * @param i the index of the first element + * @param j the index of the second element + * @return zero on success, non-zero if one of the indices is out of bounds + */ +__attribute__((__nonnull__)) +static inline int cxListSwap( + CxList *list, + size_t i, + size_t j +) { + return list->cl->swap(list, i, j); +} + +/** * Returns a pointer to the element at the specified index. * * @param list the list diff -r dfd0403ff8b6 -r 2e6e9d9f2159 src/linked_list.c --- a/src/linked_list.c Wed Feb 08 18:56:58 2023 +0100 +++ b/src/linked_list.c Wed Feb 08 20:26:09 2023 +0100 @@ -451,6 +451,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; @@ -577,6 +579,126 @@ return 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->itemsize > 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->itemsize); + memcpy(nleft->payload, nright->payload, list->itemsize); + memcpy(nright->payload, buf, list->itemsize); + } + + return 0; +} + static void *cx_ll_at( struct cx_list_s const *list, size_t index @@ -714,6 +836,7 @@ cx_ll_insert_array, cx_ll_insert_iter, cx_ll_remove, + cx_ll_swap, cx_ll_at, cx_ll_find, cx_ll_sort, diff -r dfd0403ff8b6 -r 2e6e9d9f2159 src/list.c --- a/src/list.c Wed Feb 08 18:56:58 2023 +0100 +++ b/src/list.c Wed Feb 08 20:26:09 2023 +0100 @@ -95,6 +95,14 @@ return list->climpl->remove(list, index); } +static int cx_pl_swap( + struct cx_list_s *list, + size_t i, + size_t j +) { + return list->climpl->swap(list, i, j); +} + static void *cx_pl_at( struct cx_list_s const *list, size_t index @@ -155,6 +163,7 @@ cx_pl_insert_array, cx_pl_insert_iter, cx_pl_remove, + cx_pl_swap, cx_pl_at, cx_pl_find, cx_pl_sort, diff -r dfd0403ff8b6 -r 2e6e9d9f2159 test/test_list.cpp --- a/test/test_list.cpp Wed Feb 08 18:56:58 2023 +0100 +++ b/test/test_list.cpp Wed Feb 08 20:26:09 2023 +0100 @@ -697,6 +697,54 @@ EXPECT_NE(cxListRemove(list, testdata_len), 0); } + static void verifySwap(CxList *list) { + ASSERT_EQ(list->size, 0); + + int original[16] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}; + int swapped[16] = {8, 4, 14, 3, 1, 5, 9, 12, 0, 6, 11, 10, 7, 15, 2, 13}; + + // we have to add the items one by one, because it could be a pointer list + cx_for_n(i, 16) { + cxListAdd(list, &original[i]); + } + + int result; + + // execute the test two times with different item sizes + result = cxListSwap(list, 1, 4); + EXPECT_EQ(0, result); + result = cxListSwap(list, 2, 14); + EXPECT_EQ(0, result); + result = cxListSwap(list, 9, 6); + EXPECT_EQ(0, result); + result = cxListSwap(list, 3, 3); + EXPECT_EQ(0, result); + result = cxListSwap(list, 10, 11); + EXPECT_EQ(0, result); + result = cxListSwap(list, 8, 0); + EXPECT_EQ(0, result); + result = cxListSwap(list, 7, 12); + EXPECT_EQ(0, result); + result = cxListSwap(list, 13, 15); + EXPECT_EQ(0, result); + + result = cxListSwap(list, 5, 16); + EXPECT_NE(0, result); + result = cxListSwap(list, 16, 6); + EXPECT_NE(0, result); + result = cxListSwap(list, 16, 17); + EXPECT_NE(0, result); + + auto iter = cxListBegin(list); + cx_foreach(int*, e, iter) { + EXPECT_EQ(*e, swapped[iter.index]); + } + // TODO: replace with backward iterator + cx_for_n(i, 16) { + EXPECT_EQ(*((int *) cxListAt(list, i)), swapped[i]); + } + } + void verifyAt(CxList *list) const { auto len = testdata_len; EXPECT_EQ(list->size, len); @@ -903,6 +951,40 @@ verifyRemove(arrayListFromTestData()); } +TEST_F(LinkedList, cxListSwap) { + verifySwap(autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int)))); +} + +TEST_F(PointerLinkedList, cxListSwap) { + auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int *))); + cxListStorePointers(list); + verifySwap(list); +} + +TEST_F(ArrayList, cxListSwap) { + verifySwap(autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 16))); +} + +TEST_F(LinkedList, cxListSwapNoSBO) { + CX_DISABLE_LINKED_LIST_SWAP_SBO = true; + verifySwap(autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int)))); + CX_DISABLE_LINKED_LIST_SWAP_SBO = false; +} + +TEST_F(PointerLinkedList, cxListSwapNoSBO) { + auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int *))); + cxListStorePointers(list); + CX_DISABLE_LINKED_LIST_SWAP_SBO = true; + verifySwap(list); + CX_DISABLE_LINKED_LIST_SWAP_SBO = false; +} + +TEST_F(ArrayList, cxListSwapNoSBO) { + CX_DISABLE_LINKED_LIST_SWAP_SBO = true; + verifySwap(autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 16))); + CX_DISABLE_LINKED_LIST_SWAP_SBO = false; +} + TEST_F(LinkedList, cxListAt) { verifyAt(linkedListFromTestData()); }