# HG changeset patch # User Mike Becker # Date 1653127825 -7200 # Node ID 4373c2a90066b0ceb269dda2d15e98951884edfe # Parent 2946e13c89a415ca84a78ea2165ad6a8877f444f #178 fix that lists of different kind cannot be compared diff -r 2946e13c89a4 -r 4373c2a90066 src/cx/linked_list.h --- 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. diff -r 2946e13c89a4 -r 4373c2a90066 src/linked_list.c --- 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; diff -r 2946e13c89a4 -r 4373c2a90066 test/test_list.cpp --- 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);