Mercurial > hg > ucx / changeset

     1.1 --- a/src/cx/linked_list.h	Sat May 21 11:22:47 2022 +0200
     1.2 +++ b/src/cx/linked_list.h	Sat May 21 12:10:25 2022 +0200
     1.3 @@ -402,25 +402,31 @@
     1.4  /**
     1.5   * Compares two lists element wise.
     1.6   *
     1.7 + * The \c follow_ptr flags have the following meaning: if \c false, the pointer denoted by \p loc_data shall
     1.8 + * directly be passed to the \p cmp_func.
     1.9 + * If \c true, the data at \p loc_data is assumed to be a pointer, dereferenced, and then passed to \p cmp_func.
    1.10 + *
    1.11   * \note Both list must have the same structure.
    1.12   *
    1.13   * @param begin_left the begin of the left list (\c NULL denotes an empty list)
    1.14   * @param begin_right the begin of the right list  (\c NULL denotes an empty list)
    1.15   * @param loc_advance the location of the pointer to advance
    1.16   * @param loc_data the location of the \c data pointer within your node struct
    1.17 - * @param follow_ptr \c false if the pointer denoted by \p loc_data shall be passed to the \p cmp_func.
    1.18 - * If \c true, the data at \p loc_data is assumed to be a pointer, dereferenced, and then passed to \p cmp_func.
    1.19 + * @param follow_ptr_left indicates whether pointers in the left list shall be dereferenced
    1.20 + * @param follow_ptr_right indicates whether pointers in the right list shall be dereferenced
    1.21   * @param cmp_func the function to compare the elements
    1.22 - * @return
    1.23 + * @return the first non-zero result of invoking \p cmp_func or: negative if the left list is smaller than the
    1.24 + * right list, positive if the left list is larger than the right list, zero if both lists are equal.
    1.25   */
    1.26  int cx_linked_list_compare(
    1.27          void const *begin_left,
    1.28          void const *begin_right,
    1.29          ptrdiff_t loc_advance,
    1.30          ptrdiff_t loc_data,
    1.31 -        bool follow_ptr,
    1.32 +        bool follow_ptr_left,
    1.33 +        bool follow_ptr_right,
    1.34          CxListComparator cmp_func
    1.35 -) __attribute__((__nonnull__(6)));
    1.36 +) __attribute__((__nonnull__(7)));
    1.37  
    1.38  /**
    1.39   * Reverses the order of the nodes in a linked list.

     2.1 --- a/src/linked_list.c	Sat May 21 11:22:47 2022 +0200
     2.2 +++ b/src/linked_list.c	Sat May 21 12:10:25 2022 +0200
     2.3 @@ -38,7 +38,8 @@
     2.4  #define ll_prev(node) CX_LL_PTR(node, loc_prev)
     2.5  #define ll_next(node) CX_LL_PTR(node, loc_next)
     2.6  #define ll_advance(node) CX_LL_PTR(node, loc_advance)
     2.7 -#define ll_data(node) (follow_ptr?CX_LL_PTR(node, loc_data):(((char*)node)+loc_data))
     2.8 +#define ll_data_f(node, follow_ptr) ((follow_ptr)?CX_LL_PTR(node, loc_data):(((char*)node)+loc_data))
     2.9 +#define ll_data(node) ll_data_f(node,follow_ptr)
    2.10  
    2.11  void *cx_linked_list_at(
    2.12          void const *start,
    2.13 @@ -403,13 +404,16 @@
    2.14          void const *begin_right,
    2.15          ptrdiff_t loc_advance,
    2.16          ptrdiff_t loc_data,
    2.17 -        bool follow_ptr,
    2.18 +        bool follow_ptr_left,
    2.19 +        bool follow_ptr_right,
    2.20          CxListComparator cmp_func
    2.21  ) {
    2.22      void const *left = begin_left, *right = begin_right;
    2.23  
    2.24      while (left != NULL && right != NULL) {
    2.25 -        int result = cmp_func(ll_data(left), ll_data(right));
    2.26 +        void const *left_data = ll_data_f(left, follow_ptr_left);
    2.27 +        void const *right_data = ll_data_f(right, follow_ptr_right);
    2.28 +        int result = cmp_func(left_data, right_data);
    2.29          if (result != 0) return result;
    2.30          left = ll_advance(left);
    2.31          right = ll_advance(right);
    2.32 @@ -468,6 +472,7 @@
    2.33      struct cx_list_s base;
    2.34      cx_linked_list_node *begin;
    2.35      cx_linked_list_node *end;
    2.36 +    bool follow_ptr;
    2.37  } cx_linked_list;
    2.38  
    2.39  static cx_linked_list_node *cx_ll_node_at(
    2.40 @@ -595,32 +600,17 @@
    2.41          struct cx_list_s const *list,
    2.42          void const *elem
    2.43  ) {
    2.44 +    cx_linked_list *ll = (cx_linked_list *) list;
    2.45      return cx_linked_list_find(((cx_linked_list *) list)->begin,
    2.46                                 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
    2.47 -                               false, list->cmpfunc, elem);
    2.48 -}
    2.49 -
    2.50 -static size_t cx_pll_find(
    2.51 -        struct cx_list_s const *list,
    2.52 -        void const *elem
    2.53 -) {
    2.54 -    return cx_linked_list_find(((cx_linked_list *) list)->begin,
    2.55 -                               CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
    2.56 -                               true, list->cmpfunc, elem);
    2.57 +                               ll->follow_ptr, list->cmpfunc, elem);
    2.58  }
    2.59  
    2.60  static void cx_ll_sort(struct cx_list_s *list) {
    2.61      cx_linked_list *ll = (cx_linked_list *) list;
    2.62      cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end,
    2.63                          CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
    2.64 -                        false, list->cmpfunc);
    2.65 -}
    2.66 -
    2.67 -static void cx_pll_sort(struct cx_list_s *list) {
    2.68 -    cx_linked_list *ll = (cx_linked_list *) list;
    2.69 -    cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end,
    2.70 -                        CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
    2.71 -                        true, list->cmpfunc);
    2.72 +                        ll->follow_ptr, list->cmpfunc);
    2.73  }
    2.74  
    2.75  static void cx_ll_reverse(struct cx_list_s *list) {
    2.76 @@ -636,18 +626,7 @@
    2.77      cx_linked_list *right = (cx_linked_list *) other;
    2.78      return cx_linked_list_compare(left->begin, right->begin,
    2.79                                    CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
    2.80 -                                  false, list->cmpfunc);
    2.81 -}
    2.82 -
    2.83 -static int cx_pll_compare(
    2.84 -        struct cx_list_s const *list,
    2.85 -        struct cx_list_s const *other
    2.86 -) {
    2.87 -    cx_linked_list *left = (cx_linked_list *) list;
    2.88 -    cx_linked_list *right = (cx_linked_list *) other;
    2.89 -    return cx_linked_list_compare(left->begin, right->begin,
    2.90 -                                  CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
    2.91 -                                  true, list->cmpfunc);
    2.92 +                                  left->follow_ptr, right->follow_ptr, list->cmpfunc);
    2.93  }
    2.94  
    2.95  static bool cx_ll_iter_valid(CxIterator const *iter) {
    2.96 @@ -766,9 +745,9 @@
    2.97          cx_pll_insert_iter,
    2.98          cx_ll_remove,
    2.99          cx_pll_at,
   2.100 -        cx_pll_find,
   2.101 -        cx_pll_sort,
   2.102 -        cx_pll_compare,
   2.103 +        cx_ll_find,
   2.104 +        cx_ll_sort,
   2.105 +        cx_ll_compare,
   2.106          cx_ll_reverse,
   2.107          cx_pll_iterator,
   2.108  };
   2.109 @@ -781,6 +760,7 @@
   2.110      cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list));
   2.111      if (list == NULL) return NULL;
   2.112  
   2.113 +    list->follow_ptr = false;
   2.114      list->base.cl = &cx_linked_list_class;
   2.115      list->base.allocator = allocator;
   2.116      list->base.cmpfunc = comparator;
   2.117 @@ -797,6 +777,7 @@
   2.118      cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list));
   2.119      if (list == NULL) return NULL;
   2.120  
   2.121 +    list->follow_ptr = true;
   2.122      list->base.cl = &cx_pointer_linked_list_class;
   2.123      list->base.allocator = allocator;
   2.124      list->base.cmpfunc = comparator;

     3.1 --- a/test/test_list.cpp	Sat May 21 11:22:47 2022 +0200
     3.2 +++ b/test/test_list.cpp	Sat May 21 12:10:25 2022 +0200
     3.3 @@ -196,11 +196,11 @@
     3.4      auto tc = create_nodes_test_data({2, 4, 6, 9});
     3.5      auto la = ta.begin, lb = tb.begin, lc = tc.begin;
     3.6  
     3.7 -    EXPECT_GT(cx_linked_list_compare(la, lb, loc_next, loc_data, false, cmp_int), 0);
     3.8 -    EXPECT_LT(cx_linked_list_compare(lb, la, loc_next, loc_data, false, cmp_int), 0);
     3.9 -    EXPECT_GT(cx_linked_list_compare(lc, la, loc_next, loc_data, false, cmp_int), 0);
    3.10 -    EXPECT_LT(cx_linked_list_compare(la, lc, loc_next, loc_data, false, cmp_int), 0);
    3.11 -    EXPECT_EQ(cx_linked_list_compare(la, la, loc_next, loc_data, false, cmp_int), 0);
    3.12 +    EXPECT_GT(cx_linked_list_compare(la, lb, loc_next, loc_data, false, false, cmp_int), 0);
    3.13 +    EXPECT_LT(cx_linked_list_compare(lb, la, loc_next, loc_data, false, false, cmp_int), 0);
    3.14 +    EXPECT_GT(cx_linked_list_compare(lc, la, loc_next, loc_data, false, false, cmp_int), 0);
    3.15 +    EXPECT_LT(cx_linked_list_compare(la, lc, loc_next, loc_data, false, false, cmp_int), 0);
    3.16 +    EXPECT_EQ(cx_linked_list_compare(la, la, loc_next, loc_data, false, false, cmp_int), 0);
    3.17  }
    3.18  
    3.19  TEST(LinkedList_LowLevel, cx_linked_list_add) {
    3.20 @@ -555,7 +555,7 @@
    3.21      cx_linked_list_reverse(&begin, &end, loc_prev, loc_next);
    3.22      EXPECT_EQ(end, orig_begin);
    3.23      EXPECT_EQ(begin, orig_end);
    3.24 -    EXPECT_EQ(cx_linked_list_compare(begin, expected.begin, loc_next, loc_data, 0, cmp_int), 0);
    3.25 +    EXPECT_EQ(cx_linked_list_compare(begin, expected.begin, loc_next, loc_data, false, false, cmp_int), 0);
    3.26  }
    3.27  
    3.28  class HighLevelTest : public ::testing::Test {
    3.29 @@ -883,12 +883,24 @@
    3.30      verifyCompare(left, right);
    3.31  }
    3.32  
    3.33 +TEST_F(LinkedList, cxListCompareWithPtrList) {
    3.34 +    auto left = linkedListFromTestData();
    3.35 +    auto right = pointerLinkedListFromTestData();
    3.36 +    verifyCompare(left, right);
    3.37 +}
    3.38 +
    3.39  TEST_F(PointerLinkedList, cxListCompare) {
    3.40      auto left = pointerLinkedListFromTestData();
    3.41      auto right = pointerLinkedListFromTestData();
    3.42      verifyCompare(left, right);
    3.43  }
    3.44  
    3.45 +TEST_F(PointerLinkedList, cxListCompareWithNormalList) {
    3.46 +    auto left = pointerLinkedListFromTestData();
    3.47 +    auto right = linkedListFromTestData();
    3.48 +    verifyCompare(left, right);
    3.49 +}
    3.50 +
    3.51  TEST_F(PointerLinkedList, NoDestructor) {
    3.52      void *item = cxMalloc(&testingAllocator, sizeof(int));
    3.53      auto list = cxPointerLinkedListCreate(cxDefaultAllocator, cmp_int);