Mercurial > hg > ucx / changeset

     1.1 --- a/src/array_list.c	Wed Feb 08 18:56:58 2023 +0100
     1.2 +++ b/src/array_list.c	Wed Feb 08 20:26:09 2023 +0100
     1.3 @@ -292,6 +292,17 @@
     1.4      return result;
     1.5  }
     1.6  
     1.7 +static int cx_arl_swap(
     1.8 +        struct cx_list_s *list,
     1.9 +        size_t i,
    1.10 +        size_t j
    1.11 +) {
    1.12 +    if (i >= list->size || j >= list->size) return 1;
    1.13 +    cx_array_list *arl = (cx_array_list *) list;
    1.14 +    cx_array_swap(arl->data, list->itemsize, i, j);
    1.15 +    return 0;
    1.16 +}
    1.17 +
    1.18  static void *cx_arl_at(
    1.19          struct cx_list_s const *list,
    1.20          size_t index
    1.21 @@ -420,6 +431,7 @@
    1.22          cx_arl_insert_array,
    1.23          cx_arl_insert_iter,
    1.24          cx_arl_remove,
    1.25 +        cx_arl_swap,
    1.26          cx_arl_at,
    1.27          cx_arl_find,
    1.28          cx_arl_sort,

     2.1 --- a/src/cx/linked_list.h	Wed Feb 08 18:56:58 2023 +0100
     2.2 +++ b/src/cx/linked_list.h	Wed Feb 08 20:26:09 2023 +0100
     2.3 @@ -46,6 +46,12 @@
     2.4  #endif
     2.5  
     2.6  /**
     2.7 + * Set this flag to true, if you want to disable the use of SBO for
     2.8 + * linked list swap operations.
     2.9 + */
    2.10 +extern bool CX_DISABLE_LINKED_LIST_SWAP_SBO;
    2.11 +
    2.12 +/**
    2.13   * Allocates a linked list for storing elements with \p item_size bytes each.
    2.14   *
    2.15   * @remark Elements added to the list are copied, therefore a possible destructor

     3.1 --- a/src/cx/list.h	Wed Feb 08 18:56:58 2023 +0100
     3.2 +++ b/src/cx/list.h	Wed Feb 08 20:26:09 2023 +0100
     3.3 @@ -164,6 +164,15 @@
     3.4      );
     3.5  
     3.6      /**
     3.7 +     * Member function for swapping two elements.
     3.8 +     */
     3.9 +    int (*swap)(
    3.10 +            struct cx_list_s *list,
    3.11 +            size_t i,
    3.12 +            size_t j
    3.13 +    );
    3.14 +
    3.15 +    /**
    3.16       * Member function for element lookup.
    3.17       */
    3.18      void *(*at)(
    3.19 @@ -401,6 +410,26 @@
    3.20  }
    3.21  
    3.22  /**
    3.23 + * Swaps two items in the list.
    3.24 + *
    3.25 + * Implementations should only allocate temporary memory for the swap, if
    3.26 + * it is necessary.
    3.27 + *
    3.28 + * @param list the list
    3.29 + * @param i the index of the first element
    3.30 + * @param j the index of the second element
    3.31 + * @return zero on success, non-zero if one of the indices is out of bounds
    3.32 + */
    3.33 +__attribute__((__nonnull__))
    3.34 +static inline int cxListSwap(
    3.35 +        CxList *list,
    3.36 +        size_t i,
    3.37 +        size_t j
    3.38 +) {
    3.39 +    return list->cl->swap(list, i, j);
    3.40 +}
    3.41 +
    3.42 +/**
    3.43   * Returns a pointer to the element at the specified index.
    3.44   *
    3.45   * @param list the list

     4.1 --- a/src/linked_list.c	Wed Feb 08 18:56:58 2023 +0100
     4.2 +++ b/src/linked_list.c	Wed Feb 08 20:26:09 2023 +0100
     4.3 @@ -451,6 +451,8 @@
     4.4  
     4.5  // HIGH LEVEL LINKED LIST IMPLEMENTATION
     4.6  
     4.7 +bool CX_DISABLE_LINKED_LIST_SWAP_SBO = false;
     4.8 +
     4.9  typedef struct cx_linked_list_node cx_linked_list_node;
    4.10  struct cx_linked_list_node {
    4.11      cx_linked_list_node *prev;
    4.12 @@ -577,6 +579,126 @@
    4.13      return 0;
    4.14  }
    4.15  
    4.16 +#ifndef CX_LINKED_LIST_SWAP_SBO_SIZE
    4.17 +#define CX_LINKED_LIST_SWAP_SBO_SIZE 16
    4.18 +#endif
    4.19 +
    4.20 +static int cx_ll_swap(
    4.21 +        struct cx_list_s *list,
    4.22 +        size_t i,
    4.23 +        size_t j
    4.24 +) {
    4.25 +    if (i >= list->size || j >= list->size) return 1;
    4.26 +    if (i == j) return 0;
    4.27 +
    4.28 +    // perform an optimized search that finds both elements in one run
    4.29 +    cx_linked_list *ll = (cx_linked_list *) list;
    4.30 +    size_t mid = list->size / 2;
    4.31 +    size_t left, right;
    4.32 +    if (i < j) {
    4.33 +        left = i;
    4.34 +        right = j;
    4.35 +    } else {
    4.36 +        left = j;
    4.37 +        right = i;
    4.38 +    }
    4.39 +    cx_linked_list_node *nleft, *nright;
    4.40 +    if (left < mid && right < mid) {
    4.41 +        // case 1: both items left from mid
    4.42 +        nleft = cx_ll_node_at(ll, left);
    4.43 +        nright = nleft;
    4.44 +        for (size_t c = left; c < right; c++) {
    4.45 +            nright = nright->next;
    4.46 +        }
    4.47 +    } else if (left >= mid && right >= mid) {
    4.48 +        // case 2: both items right from mid
    4.49 +        nright = cx_ll_node_at(ll, right);
    4.50 +        nleft = nright;
    4.51 +        for (size_t c = right; c > left; c--) {
    4.52 +            nleft = nleft->prev;
    4.53 +        }
    4.54 +    } else {
    4.55 +        // case 3: one item left, one item right
    4.56 +
    4.57 +        // chose the closest to begin / end
    4.58 +        size_t closest;
    4.59 +        size_t other;
    4.60 +        size_t diff2boundary = list->size - right - 1;
    4.61 +        if (left <= diff2boundary) {
    4.62 +            closest = left;
    4.63 +            other = right;
    4.64 +            nleft = cx_ll_node_at(ll, left);
    4.65 +        } else {
    4.66 +            closest = right;
    4.67 +            other = left;
    4.68 +            diff2boundary = left;
    4.69 +            nright = cx_ll_node_at(ll, right);
    4.70 +        }
    4.71 +
    4.72 +        // is other element closer to us or closer to boundary?
    4.73 +        if (right - left <= diff2boundary) {
    4.74 +            // search other element starting from already found element
    4.75 +            if (closest == left) {
    4.76 +                nright = nleft;
    4.77 +                for (size_t c = left; c < right; c++) {
    4.78 +                    nright = nright->next;
    4.79 +                }
    4.80 +            } else {
    4.81 +                nleft = nright;
    4.82 +                for (size_t c = right; c > left; c--) {
    4.83 +                    nleft = nleft->prev;
    4.84 +                }
    4.85 +            }
    4.86 +        } else {
    4.87 +            // search other element starting at the boundary
    4.88 +            if (closest == left) {
    4.89 +                nright = cx_ll_node_at(ll, other);
    4.90 +            } else {
    4.91 +                nleft = cx_ll_node_at(ll, other);
    4.92 +            }
    4.93 +        }
    4.94 +    }
    4.95 +
    4.96 +    if (list->itemsize > CX_LINKED_LIST_SWAP_SBO_SIZE || CX_DISABLE_LINKED_LIST_SWAP_SBO) {
    4.97 +        cx_linked_list_node *prev = nleft->prev;
    4.98 +        cx_linked_list_node *next = nright->next;
    4.99 +        cx_linked_list_node *midstart = nleft->next;
   4.100 +        cx_linked_list_node *midend = nright->prev;
   4.101 +
   4.102 +        if (prev == NULL) {
   4.103 +            ll->begin = nright;
   4.104 +        } else {
   4.105 +            prev->next = nright;
   4.106 +        }
   4.107 +        nright->prev = prev;
   4.108 +        if (midstart == nright) {
   4.109 +            // special case: both nodes are adjacent
   4.110 +            nright->next = nleft;
   4.111 +            nleft->prev = nright;
   4.112 +        } else {
   4.113 +            // likely case: a chain is between the two nodes
   4.114 +            nright->next = midstart;
   4.115 +            midstart->prev = nright;
   4.116 +            midend->next = nleft;
   4.117 +            nleft->prev = midend;
   4.118 +        }
   4.119 +        nleft->next = next;
   4.120 +        if (next == NULL) {
   4.121 +            ll->end = nleft;
   4.122 +        } else {
   4.123 +            next->prev = nleft;
   4.124 +        }
   4.125 +    } else {
   4.126 +        // swap payloads to avoid relinking
   4.127 +        char buf[CX_LINKED_LIST_SWAP_SBO_SIZE];
   4.128 +        memcpy(buf, nleft->payload, list->itemsize);
   4.129 +        memcpy(nleft->payload, nright->payload, list->itemsize);
   4.130 +        memcpy(nright->payload, buf, list->itemsize);
   4.131 +    }
   4.132 +
   4.133 +    return 0;
   4.134 +}
   4.135 +
   4.136  static void *cx_ll_at(
   4.137          struct cx_list_s const *list,
   4.138          size_t index
   4.139 @@ -714,6 +836,7 @@
   4.140          cx_ll_insert_array,
   4.141          cx_ll_insert_iter,
   4.142          cx_ll_remove,
   4.143 +        cx_ll_swap,
   4.144          cx_ll_at,
   4.145          cx_ll_find,
   4.146          cx_ll_sort,

     5.1 --- a/src/list.c	Wed Feb 08 18:56:58 2023 +0100
     5.2 +++ b/src/list.c	Wed Feb 08 20:26:09 2023 +0100
     5.3 @@ -95,6 +95,14 @@
     5.4      return list->climpl->remove(list, index);
     5.5  }
     5.6  
     5.7 +static int cx_pl_swap(
     5.8 +        struct cx_list_s *list,
     5.9 +        size_t i,
    5.10 +        size_t j
    5.11 +) {
    5.12 +    return list->climpl->swap(list, i, j);
    5.13 +}
    5.14 +
    5.15  static void *cx_pl_at(
    5.16          struct cx_list_s const *list,
    5.17          size_t index
    5.18 @@ -155,6 +163,7 @@
    5.19          cx_pl_insert_array,
    5.20          cx_pl_insert_iter,
    5.21          cx_pl_remove,
    5.22 +        cx_pl_swap,
    5.23          cx_pl_at,
    5.24          cx_pl_find,
    5.25          cx_pl_sort,

     6.1 --- a/test/test_list.cpp	Wed Feb 08 18:56:58 2023 +0100
     6.2 +++ b/test/test_list.cpp	Wed Feb 08 20:26:09 2023 +0100
     6.3 @@ -697,6 +697,54 @@
     6.4          EXPECT_NE(cxListRemove(list, testdata_len), 0);
     6.5      }
     6.6  
     6.7 +    static void verifySwap(CxList *list) {
     6.8 +        ASSERT_EQ(list->size, 0);
     6.9 +
    6.10 +        int original[16] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
    6.11 +        int swapped[16] = {8, 4, 14, 3, 1, 5, 9, 12, 0, 6, 11, 10, 7, 15, 2, 13};
    6.12 +
    6.13 +        // we have to add the items one by one, because it could be a pointer list
    6.14 +        cx_for_n(i, 16) {
    6.15 +            cxListAdd(list, &original[i]);
    6.16 +        }
    6.17 +
    6.18 +        int result;
    6.19 +
    6.20 +        // execute the test two times with different item sizes
    6.21 +        result = cxListSwap(list, 1, 4);
    6.22 +        EXPECT_EQ(0, result);
    6.23 +        result = cxListSwap(list, 2, 14);
    6.24 +        EXPECT_EQ(0, result);
    6.25 +        result = cxListSwap(list, 9, 6);
    6.26 +        EXPECT_EQ(0, result);
    6.27 +        result = cxListSwap(list, 3, 3);
    6.28 +        EXPECT_EQ(0, result);
    6.29 +        result = cxListSwap(list, 10, 11);
    6.30 +        EXPECT_EQ(0, result);
    6.31 +        result = cxListSwap(list, 8, 0);
    6.32 +        EXPECT_EQ(0, result);
    6.33 +        result = cxListSwap(list, 7, 12);
    6.34 +        EXPECT_EQ(0, result);
    6.35 +        result = cxListSwap(list, 13, 15);
    6.36 +        EXPECT_EQ(0, result);
    6.37 +
    6.38 +        result = cxListSwap(list, 5, 16);
    6.39 +        EXPECT_NE(0, result);
    6.40 +        result = cxListSwap(list, 16, 6);
    6.41 +        EXPECT_NE(0, result);
    6.42 +        result = cxListSwap(list, 16, 17);
    6.43 +        EXPECT_NE(0, result);
    6.44 +
    6.45 +        auto iter = cxListBegin(list);
    6.46 +        cx_foreach(int*, e, iter) {
    6.47 +            EXPECT_EQ(*e, swapped[iter.index]);
    6.48 +        }
    6.49 +        // TODO: replace with backward iterator
    6.50 +        cx_for_n(i, 16) {
    6.51 +            EXPECT_EQ(*((int *) cxListAt(list, i)), swapped[i]);
    6.52 +        }
    6.53 +    }
    6.54 +
    6.55      void verifyAt(CxList *list) const {
    6.56          auto len = testdata_len;
    6.57          EXPECT_EQ(list->size, len);
    6.58 @@ -903,6 +951,40 @@
    6.59      verifyRemove(arrayListFromTestData());
    6.60  }
    6.61  
    6.62 +TEST_F(LinkedList, cxListSwap) {
    6.63 +    verifySwap(autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int))));
    6.64 +}
    6.65 +
    6.66 +TEST_F(PointerLinkedList, cxListSwap) {
    6.67 +    auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int *)));
    6.68 +    cxListStorePointers(list);
    6.69 +    verifySwap(list);
    6.70 +}
    6.71 +
    6.72 +TEST_F(ArrayList, cxListSwap) {
    6.73 +    verifySwap(autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 16)));
    6.74 +}
    6.75 +
    6.76 +TEST_F(LinkedList, cxListSwapNoSBO) {
    6.77 +    CX_DISABLE_LINKED_LIST_SWAP_SBO = true;
    6.78 +    verifySwap(autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int))));
    6.79 +    CX_DISABLE_LINKED_LIST_SWAP_SBO = false;
    6.80 +}
    6.81 +
    6.82 +TEST_F(PointerLinkedList, cxListSwapNoSBO) {
    6.83 +    auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int *)));
    6.84 +    cxListStorePointers(list);
    6.85 +    CX_DISABLE_LINKED_LIST_SWAP_SBO = true;
    6.86 +    verifySwap(list);
    6.87 +    CX_DISABLE_LINKED_LIST_SWAP_SBO = false;
    6.88 +}
    6.89 +
    6.90 +TEST_F(ArrayList, cxListSwapNoSBO) {
    6.91 +    CX_DISABLE_LINKED_LIST_SWAP_SBO = true;
    6.92 +    verifySwap(autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 16)));
    6.93 +    CX_DISABLE_LINKED_LIST_SWAP_SBO = false;
    6.94 +}
    6.95 +
    6.96  TEST_F(LinkedList, cxListAt) {
    6.97      verifyAt(linkedListFromTestData());
    6.98  }