Mercurial > hg > ucx / changeset

--- a/src/cx/linked_list.h	Sat May 21 11:22:47 2022 +0200
+++ b/src/cx/linked_list.h	Sat May 21 12:10:25 2022 +0200
@@ -402,25 +402,31 @@
 /**
  * Compares two lists element wise.
  *
+ * The \c follow_ptr flags have the following meaning: if \c false, the pointer denoted by \p loc_data shall
+ * directly be passed to the \p cmp_func.
+ * If \c true, the data at \p loc_data is assumed to be a pointer, dereferenced, and then passed to \p cmp_func.
+ *
  * \note Both list must have the same structure.
  *
  * @param begin_left the begin of the left list (\c NULL denotes an empty list)
  * @param begin_right the begin of the right list  (\c NULL denotes an empty list)
  * @param loc_advance the location of the pointer to advance
  * @param loc_data the location of the \c data pointer within your node struct
- * @param follow_ptr \c false if the pointer denoted by \p loc_data shall be passed to the \p cmp_func.
- * If \c true, the data at \p loc_data is assumed to be a pointer, dereferenced, and then passed to \p cmp_func.
+ * @param follow_ptr_left indicates whether pointers in the left list shall be dereferenced
+ * @param follow_ptr_right indicates whether pointers in the right list shall be dereferenced
  * @param cmp_func the function to compare the elements
- * @return
+ * @return the first non-zero result of invoking \p cmp_func or: negative if the left list is smaller than the
+ * right list, positive if the left list is larger than the right list, zero if both lists are equal.
  */
 int cx_linked_list_compare(
         void const *begin_left,
         void const *begin_right,
         ptrdiff_t loc_advance,
         ptrdiff_t loc_data,
-        bool follow_ptr,
+        bool follow_ptr_left,
+        bool follow_ptr_right,
         CxListComparator cmp_func
-) __attribute__((__nonnull__(6)));
+) __attribute__((__nonnull__(7)));
 
 /**
  * Reverses the order of the nodes in a linked list.

--- a/src/linked_list.c	Sat May 21 11:22:47 2022 +0200
+++ b/src/linked_list.c	Sat May 21 12:10:25 2022 +0200
@@ -38,7 +38,8 @@
 #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(node) (follow_ptr?CX_LL_PTR(node, loc_data):(((char*)node)+loc_data))
+#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)
 
 void *cx_linked_list_at(
         void const *start,
@@ -403,13 +404,16 @@
         void const *begin_right,
         ptrdiff_t loc_advance,
         ptrdiff_t loc_data,
-        bool follow_ptr,
+        bool follow_ptr_left,
+        bool follow_ptr_right,
         CxListComparator cmp_func
 ) {
     void const *left = begin_left, *right = begin_right;
 
     while (left != NULL && right != NULL) {
-        int result = cmp_func(ll_data(left), ll_data(right));
+        void const *left_data = ll_data_f(left, follow_ptr_left);
+        void const *right_data = ll_data_f(right, follow_ptr_right);
+        int result = cmp_func(left_data, right_data);
         if (result != 0) return result;
         left = ll_advance(left);
         right = ll_advance(right);
@@ -468,6 +472,7 @@
     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(
@@ -595,32 +600,17 @@
         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,
-                               false, list->cmpfunc, elem);
-}
-
-static size_t cx_pll_find(
-        struct cx_list_s const *list,
-        void const *elem
-) {
-    return cx_linked_list_find(((cx_linked_list *) list)->begin,
-                               CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
-                               true, list->cmpfunc, elem);
+                               ll->follow_ptr, 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,
-                        false, list->cmpfunc);
-}
-
-static void cx_pll_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,
-                        true, list->cmpfunc);
+                        ll->follow_ptr, list->cmpfunc);
 }
 
 static void cx_ll_reverse(struct cx_list_s *list) {
@@ -636,18 +626,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,
-                                  false, list->cmpfunc);
-}
-
-static int cx_pll_compare(
-        struct cx_list_s const *list,
-        struct cx_list_s const *other
-) {
-    cx_linked_list *left = (cx_linked_list *) list;
-    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,
-                                  true, list->cmpfunc);
+                                  left->follow_ptr, right->follow_ptr, list->cmpfunc);
 }
 
 static bool cx_ll_iter_valid(CxIterator const *iter) {
@@ -766,9 +745,9 @@
         cx_pll_insert_iter,
         cx_ll_remove,
         cx_pll_at,
-        cx_pll_find,
-        cx_pll_sort,
-        cx_pll_compare,
+        cx_ll_find,
+        cx_ll_sort,
+        cx_ll_compare,
         cx_ll_reverse,
         cx_pll_iterator,
 };
@@ -781,6 +760,7 @@
     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;
@@ -797,6 +777,7 @@
     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;

--- a/test/test_list.cpp	Sat May 21 11:22:47 2022 +0200
+++ b/test/test_list.cpp	Sat May 21 12:10:25 2022 +0200
@@ -196,11 +196,11 @@
     auto tc = create_nodes_test_data({2, 4, 6, 9});
     auto la = ta.begin, lb = tb.begin, lc = tc.begin;
 
-    EXPECT_GT(cx_linked_list_compare(la, lb, loc_next, loc_data, false, cmp_int), 0);
-    EXPECT_LT(cx_linked_list_compare(lb, la, loc_next, loc_data, false, cmp_int), 0);
-    EXPECT_GT(cx_linked_list_compare(lc, la, loc_next, loc_data, false, cmp_int), 0);
-    EXPECT_LT(cx_linked_list_compare(la, lc, loc_next, loc_data, false, cmp_int), 0);
-    EXPECT_EQ(cx_linked_list_compare(la, la, loc_next, loc_data, false, cmp_int), 0);
+    EXPECT_GT(cx_linked_list_compare(la, lb, loc_next, loc_data, false, false, cmp_int), 0);
+    EXPECT_LT(cx_linked_list_compare(lb, la, loc_next, loc_data, false, false, cmp_int), 0);
+    EXPECT_GT(cx_linked_list_compare(lc, la, loc_next, loc_data, false, false, cmp_int), 0);
+    EXPECT_LT(cx_linked_list_compare(la, lc, loc_next, loc_data, false, false, cmp_int), 0);
+    EXPECT_EQ(cx_linked_list_compare(la, la, loc_next, loc_data, false, false, cmp_int), 0);
 }
 
 TEST(LinkedList_LowLevel, cx_linked_list_add) {
@@ -555,7 +555,7 @@
     cx_linked_list_reverse(&begin, &end, loc_prev, loc_next);
     EXPECT_EQ(end, orig_begin);
     EXPECT_EQ(begin, orig_end);
-    EXPECT_EQ(cx_linked_list_compare(begin, expected.begin, loc_next, loc_data, 0, cmp_int), 0);
+    EXPECT_EQ(cx_linked_list_compare(begin, expected.begin, loc_next, loc_data, false, false, cmp_int), 0);
 }
 
 class HighLevelTest : public ::testing::Test {
@@ -883,12 +883,24 @@
     verifyCompare(left, right);
 }
 
+TEST_F(LinkedList, cxListCompareWithPtrList) {
+    auto left = linkedListFromTestData();
+    auto right = pointerLinkedListFromTestData();
+    verifyCompare(left, right);
+}
+
 TEST_F(PointerLinkedList, cxListCompare) {
     auto left = pointerLinkedListFromTestData();
     auto right = pointerLinkedListFromTestData();
     verifyCompare(left, right);
 }
 
+TEST_F(PointerLinkedList, cxListCompareWithNormalList) {
+    auto left = pointerLinkedListFromTestData();
+    auto right = linkedListFromTestData();
+    verifyCompare(left, right);
+}
+
 TEST_F(PointerLinkedList, NoDestructor) {
     void *item = cxMalloc(&testingAllocator, sizeof(int));
     auto list = cxPointerLinkedListCreate(cxDefaultAllocator, cmp_int);