Mercurial > hg > ucx / changeset

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

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

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

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

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

--- 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());
 }