changeset
add cx_linked_list_compare() and simplifies some tests
Tue, 28 Dec 2021 14:16:04 +0100
- author
- Mike Becker <universe@uap-core.de>
- date
- Tue, 28 Dec 2021 14:16:04 +0100
- changeset 486
- d7ca126eab7f
- parent 485
- 6a86ad3d8c03
- child 487
- 4bd19279778c
add cx_linked_list_compare() and simplifies some tests
| src/cx/linked_list.h | file | annotate | diff | comparison | revisions | |
| src/linked_list.c | file | annotate | diff | comparison | revisions | |
| test/test_list.c | file | annotate | diff | comparison | revisions |
--- a/src/cx/linked_list.h Mon Dec 27 17:16:32 2021 +0100 +++ b/src/cx/linked_list.h Tue Dec 28 14:16:04 2021 +0100 @@ -382,6 +382,28 @@ CxListComparator cmp_func ) __attribute__((__nonnull__(1, 7))); + +/** + * Compares two lists element wise. + * + * @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 cmp_func the function to compare the elements + * @return + */ +int cx_linked_list_compare( + void *begin_left, + void *begin_right, + ptrdiff_t loc_advance, + ptrdiff_t loc_data, + int follow_ptr, + CxListComparator cmp_func +) __attribute__((__nonnull__(6))); + /** * Reverses the order of the nodes in a linked list. *
--- a/src/linked_list.c Mon Dec 27 17:16:32 2021 +0100 +++ b/src/linked_list.c Tue Dec 28 14:16:04 2021 +0100 @@ -396,6 +396,28 @@ } } +int cx_linked_list_compare( + void *begin_left, + void *begin_right, + ptrdiff_t loc_advance, + ptrdiff_t loc_data, + int follow_ptr, + CxListComparator cmp_func +) { + void *left = begin_left, *right = begin_right; + + while (left != NULL && right != NULL) { + int result = cmp_func(ll_data(left), ll_data(right)); + if (result != 0) return result; + left = ll_advance(left); + right = ll_advance(right); + } + + if (left != NULL) { return 1; } + else if (right != NULL) { return -1; } + else { return 0; } +} + void cx_linked_list_reverse( void **begin, void **end,
--- a/test/test_list.c Mon Dec 27 17:16:32 2021 +0100 +++ b/test/test_list.c Tue Dec 28 14:16:04 2021 +0100 @@ -30,20 +30,55 @@ #include "test_config.h" #include "util_allocator.h" -int cmp_int(int const *l, int const *r) { +int cmp_int( + int const *l, + int const *r +) { int left = *l, right = *r; return left == right ? 0 : (left < right ? -1 : 1); } +struct node { + struct node *next; + struct node *prev; + int data; +}; + +#define nd(name) name = {0} + +const ptrdiff_t loc_prev = offsetof(struct node, prev); +const ptrdiff_t loc_next = offsetof(struct node, next); +const ptrdiff_t loc_data = offsetof(struct node, data); + +struct node *create_test_data( + size_t n, + const int data[] +) { + if (n == 0) return NULL; + struct node *begin = calloc(1, sizeof(struct node)); + struct node *prev = begin; + if (data) begin->data = data[0]; + for (size_t i = 1; i < n; i++) { + struct node *node = calloc(1, sizeof(struct node)); + if (data) node->data = data[i]; + cx_linked_list_link(prev, node, loc_prev, loc_next); + prev = node; + } + return begin; +} + +void destroy_test_data(struct node *begin) { + struct node *node = begin; + while (node) { + struct node *next = node->next; + free(node); + node = next; + } +} + void test_linked_list_link_unlink(void) { - struct node { - void *next; - void *prev; - }; - const ptrdiff_t loc_prev = offsetof(struct node, prev); - const ptrdiff_t loc_next = offsetof(struct node, next); - struct node a = {NULL, NULL}, b = {NULL, NULL}; + struct node nd(a), nd(b), nd(c); cx_linked_list_link(&a, &b, loc_prev, loc_next); CU_ASSERT_PTR_NULL(a.prev) @@ -57,7 +92,6 @@ CU_ASSERT_PTR_NULL(b.prev) CU_ASSERT_PTR_NULL(b.next) - struct node c = {NULL, NULL}; cx_linked_list_link(&b, &c, loc_prev, loc_next); cx_linked_list_link(&a, &b, loc_prev, loc_next); cx_linked_list_unlink(&b, &c, loc_prev, loc_next); @@ -70,22 +104,10 @@ } void test_linked_list_at(void) { - struct node { - void *next; - void *prev; - }; - const ptrdiff_t loc_prev = offsetof(struct node, prev); - const ptrdiff_t loc_next = offsetof(struct node, next); - - struct node a, b, c, d; - a.prev = NULL; - a.next = &b; - b.prev = &a; - b.next = &c; - c.prev = &b; - c.next = &d; - d.prev = &c; - d.next = NULL; + struct node nd(a), nd(b), nd(c), nd(d); + cx_linked_list_link(&a, &b, loc_prev, loc_next); + cx_linked_list_link(&b, &c, loc_prev, loc_next); + cx_linked_list_link(&c, &d, loc_prev, loc_next); CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&a, 0, loc_next, 0), &a) CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&a, 0, loc_next, 1), &b) @@ -103,21 +125,43 @@ CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&d, 3, loc_prev, 1), &b) } +void test_linked_list_compare(void) { + int a[] = {2, 4, 6, 8}; + int b[] = {2, 4, 6}; + int c[] = {2, 4, 6, 9}; + + void *la = create_test_data(4, a); + void *lb = create_test_data(3, b); + void *lc = create_test_data(4, c); + + CU_ASSERT_TRUE(0 < cx_linked_list_compare(la, lb, loc_next, loc_data, + 0, (CxListComparator) cmp_int) + ) + CU_ASSERT_TRUE(0 > cx_linked_list_compare(lb, la, loc_next, loc_data, + 0, (CxListComparator) cmp_int) + ) + CU_ASSERT_TRUE(0 < cx_linked_list_compare(lc, la, loc_next, loc_data, + 0, (CxListComparator) cmp_int) + ) + CU_ASSERT_TRUE(0 > cx_linked_list_compare(la, lc, loc_next, loc_data, + 0, (CxListComparator) cmp_int) + ) + CU_ASSERT_TRUE(0 == cx_linked_list_compare(la, la, loc_next, loc_data, + 0, (CxListComparator) cmp_int) + ) + + destroy_test_data(la); + destroy_test_data(lb); + destroy_test_data(lc); +} + void test_linked_list_add(void) { - struct node { - void *prev; - void *next; - }; - struct node nodes[4]; + void *begin, *end; // test with begin, end / prev, next memset(nodes, 0, 4 * sizeof(struct node)); - void *begin = NULL; - void *end = NULL; - - ptrdiff_t loc_prev = offsetof(struct node, prev); - ptrdiff_t loc_next = offsetof(struct node, next); + begin = end = NULL; cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[0]); CU_ASSERT_PTR_EQUAL(begin, &nodes[0]) @@ -133,8 +177,7 @@ // test with begin only / prev, next memset(nodes, 0, 4 * sizeof(struct node)); - begin = NULL; - end = NULL; + begin = end = NULL; cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[0]); CU_ASSERT_PTR_EQUAL(begin, &nodes[0]) @@ -149,8 +192,7 @@ // test with end only / prev, next memset(nodes, 0, 4 * sizeof(struct node)); - begin = NULL; - end = NULL; + begin = end = NULL; cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[0]); CU_ASSERT_PTR_EQUAL(end, &nodes[0]) @@ -166,8 +208,7 @@ // test with begin, end / next memset(nodes, 0, 4 * sizeof(struct node)); - begin = NULL; - end = NULL; + begin = end = NULL; cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[0]); CU_ASSERT_PTR_EQUAL(begin, &nodes[0]) @@ -179,20 +220,12 @@ } void test_linked_list_prepend(void) { - struct node { - void *prev; - void *next; - }; - struct node nodes[4]; + void *begin, *end; // test with begin, end / prev, next memset(nodes, 0, 4 * sizeof(struct node)); - void *begin = NULL; - void *end = NULL; - - ptrdiff_t loc_prev = offsetof(struct node, prev); - ptrdiff_t loc_next = offsetof(struct node, next); + begin = end = NULL; cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[0]); CU_ASSERT_PTR_EQUAL(begin, &nodes[0]) @@ -208,8 +241,7 @@ // test with begin only / prev, next memset(nodes, 0, 4 * sizeof(struct node)); - begin = NULL; - end = NULL; + begin = end = NULL; cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[0]); CU_ASSERT_PTR_EQUAL(begin, &nodes[0]) @@ -225,8 +257,7 @@ // test with end only / prev, next memset(nodes, 0, 4 * sizeof(struct node)); - begin = NULL; - end = NULL; + begin = end = NULL; cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[0]); CU_ASSERT_PTR_EQUAL(end, &nodes[0]) @@ -242,8 +273,7 @@ // test with begin, end / next memset(nodes, 0, 4 * sizeof(struct node)); - begin = NULL; - end = NULL; + begin = end = NULL; cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[0]); CU_ASSERT_PTR_EQUAL(begin, &nodes[0]) @@ -259,13 +289,6 @@ } void test_linked_list_insert(void) { - struct node { - void *prev; - void *next; - }; - ptrdiff_t loc_prev = offsetof(struct node, prev); - ptrdiff_t loc_next = offsetof(struct node, next); - struct node nodes[4]; void *begin, *end; @@ -317,13 +340,6 @@ } void test_linked_list_insert_chain(void) { - struct node { - void *prev; - void *next; - }; - ptrdiff_t loc_prev = offsetof(struct node, prev); - ptrdiff_t loc_next = offsetof(struct node, next); - struct node nodes[5]; void *begin, *end; @@ -378,138 +394,78 @@ } void test_linked_list_first(void) { - struct node { - int data; - void *prev; - }; - ptrdiff_t loc = offsetof(struct node, prev); - - struct node first = {1, NULL}; - struct node second = {2, &first}; - struct node third = {3, &second}; - - CU_ASSERT_PTR_EQUAL(cx_linked_list_first(&first, loc), &first) - CU_ASSERT_PTR_EQUAL(cx_linked_list_first(&second, loc), &first) - CU_ASSERT_PTR_EQUAL(cx_linked_list_first(&third, loc), &first) + struct node *begin = create_test_data(3, NULL); + CU_ASSERT_PTR_EQUAL(cx_linked_list_first(begin, loc_prev), begin) + CU_ASSERT_PTR_EQUAL(cx_linked_list_first(begin->next, loc_prev), begin) + CU_ASSERT_PTR_EQUAL(cx_linked_list_first(begin->next->next, loc_prev), begin) + destroy_test_data(begin); } void test_linked_list_last(void) { - struct node { - int data; - void *next; - }; - ptrdiff_t loc = offsetof(struct node, next); - - struct node third = {3, NULL}; - struct node second = {2, &third}; - struct node first = {1, &second}; - - CU_ASSERT_PTR_EQUAL(cx_linked_list_last(&first, loc), &third) - CU_ASSERT_PTR_EQUAL(cx_linked_list_last(&second, loc), &third) - CU_ASSERT_PTR_EQUAL(cx_linked_list_last(&third, loc), &third) + struct node *begin = create_test_data(3, NULL); + struct node *end = begin->next->next; + CU_ASSERT_PTR_EQUAL(cx_linked_list_last(begin, loc_next), end) + CU_ASSERT_PTR_EQUAL(cx_linked_list_last(begin->next, loc_next), end) + CU_ASSERT_PTR_EQUAL(cx_linked_list_last(begin->next->next, loc_next), end) + destroy_test_data(begin); } void test_linked_list_prev(void) { - struct node { - void *next; - }; - ptrdiff_t loc = offsetof(struct node, next); - - struct node third = {NULL}; - struct node second = {&third}; - struct node first = {&second}; - - CU_ASSERT_PTR_NULL(cx_linked_list_prev(&first, loc, &first)) - CU_ASSERT_PTR_EQUAL(cx_linked_list_prev(&first, loc, &second), &first) - CU_ASSERT_PTR_EQUAL(cx_linked_list_prev(&first, loc, &third), &second) + struct node *begin = create_test_data(3, NULL); + CU_ASSERT_PTR_NULL(cx_linked_list_prev(begin, loc_next, begin)) + CU_ASSERT_PTR_EQUAL(cx_linked_list_prev(begin, loc_next, begin->next), begin) + CU_ASSERT_PTR_EQUAL(cx_linked_list_prev(begin, loc_next, begin->next->next), begin->next) + destroy_test_data(begin); } void test_linked_list_remove(void) { - struct node { - void *next; - }; - struct dnode { - void *next; - void *prev; - }; - ptrdiff_t loc = offsetof(struct node, next); - ptrdiff_t ploc = offsetof(struct dnode, prev); - - void *begin; - void *end; + void *begin, *end; - // single linked list - struct node third = {NULL}; - struct node second = {&third}; - struct node first = {&second}; - begin = &first; - - cx_linked_list_remove(&begin, NULL, -1, loc, &second); - CU_ASSERT_PTR_EQUAL(begin, &first) - CU_ASSERT_PTR_EQUAL(first.next, &third) - CU_ASSERT_PTR_NULL(third.next) - - cx_linked_list_remove(&begin, NULL, -1, loc, &first); - CU_ASSERT_PTR_EQUAL(begin, &third) - CU_ASSERT_PTR_NULL(third.next) + int data[] = {2, 4, 6}; + begin = create_test_data(3, data); + struct node *first = begin; + struct node *second = first->next; + struct node *third = second->next; + end = third; - cx_linked_list_remove(&begin, NULL, -1, loc, &third); - CU_ASSERT_PTR_NULL(begin) - - // doubly linked list - struct dnode dthird = {NULL , NULL}; - struct dnode dsecond = {&dthird, NULL}; - struct dnode dfirst = {&dsecond, NULL}; - dthird.prev = &dsecond; - dsecond.prev = &dfirst; - begin = &dfirst; - end = &dthird; + cx_linked_list_remove(&begin, &end, loc_prev, loc_next, second); + CU_ASSERT_PTR_EQUAL(begin, first) + CU_ASSERT_PTR_EQUAL(end, third) + CU_ASSERT_PTR_NULL(first->prev) + CU_ASSERT_PTR_EQUAL(first->next, third) + CU_ASSERT_PTR_EQUAL(third->prev, first) + CU_ASSERT_PTR_NULL(third->next) - cx_linked_list_remove(&begin, &end, ploc, loc, &dsecond); - CU_ASSERT_PTR_EQUAL(begin, &dfirst) - CU_ASSERT_PTR_EQUAL(end, &dthird) - CU_ASSERT_PTR_NULL(dfirst.prev) - CU_ASSERT_PTR_EQUAL(dfirst.next, &dthird) - CU_ASSERT_PTR_EQUAL(dthird.prev, &dfirst) - CU_ASSERT_PTR_NULL(dthird.next) + cx_linked_list_remove(&begin, &end, loc_prev, loc_next, third); + CU_ASSERT_PTR_EQUAL(begin, first) + CU_ASSERT_PTR_EQUAL(end, first) + CU_ASSERT_PTR_NULL(first->prev) + CU_ASSERT_PTR_NULL(first->next) - cx_linked_list_remove(&begin, &end, ploc, loc, &dthird); - CU_ASSERT_PTR_EQUAL(begin, &dfirst) - CU_ASSERT_PTR_EQUAL(end, &dfirst) - CU_ASSERT_PTR_NULL(dfirst.prev) - CU_ASSERT_PTR_NULL(dfirst.next) - - cx_linked_list_remove(&begin, &end, ploc, loc, &dfirst); + cx_linked_list_remove(&begin, &end, loc_prev, loc_next, first); CU_ASSERT_PTR_NULL(begin) CU_ASSERT_PTR_NULL(end) + + free(first); + free(second); + free(third); } void test_linked_list_size(void) { - struct node { - void *next; - }; - ptrdiff_t loc = offsetof(struct node, next); + struct node *list; + + CU_ASSERT_PTR_EQUAL(cx_linked_list_size(NULL, loc_next), 0) - struct node first = {NULL}; - struct node second = {NULL}; - struct node third = {NULL}; + list = create_test_data(5, NULL); + CU_ASSERT_EQUAL(cx_linked_list_size(list, loc_next), 5) + destroy_test_data(list); - CU_ASSERT_PTR_EQUAL(cx_linked_list_size(NULL, loc), 0) - CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&first, loc), 1) - first.next = &second; - CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&first, loc), 2) - second.next = &third; - CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&first, loc), 3) - CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&second, loc), 2) + list = create_test_data(13, NULL); + CU_ASSERT_EQUAL(cx_linked_list_size(list, loc_next), 13) + destroy_test_data(list); } void test_linked_list_sort(void) { - struct node { - void *prev; - void *next; - int data; - }; - int expected[] = { 14, 30, 151, 163, 227, 300, 315, 317, 363, 398, 417, 424, 438, 446, 508, 555, 605, 713, 716, 759, 761, 880, 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 1707, 1734, 1771, 1874, 1894, @@ -527,26 +483,16 @@ 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681 }; - struct node *nodes = calloc(100, sizeof(struct node)); - for (int i = 0; i < 100; i++) { - nodes[i].prev = i == 0 ? NULL : &nodes[i - 1]; - nodes[i].next = i == 99 ? NULL : &nodes[i + 1]; - nodes[i].data = scrambled[i]; - } + void *begin = create_test_data(100, scrambled); + void *end = cx_linked_list_last(begin, loc_next); - struct node *begin = &nodes[0]; - struct node *end = &nodes[99]; - - cx_linked_list_sort((void **) &begin, (void **) &end, - offsetof(struct node, prev), - offsetof(struct node, next), - offsetof(struct node, data), + cx_linked_list_sort(&begin, &end, loc_prev, loc_next, loc_data, 0, (CxListComparator) cmp_int); - CU_ASSERT_PTR_NULL(begin->prev) - CU_ASSERT_EQUAL(begin->data, expected[0]) struct node *check = begin; struct node *check_last = NULL; + CU_ASSERT_PTR_NULL(check->prev) + CU_ASSERT_EQUAL(check->data, expected[0]) for (int i = 0; i < 100; i++) { CU_ASSERT_EQUAL(check->data, expected[i]) CU_ASSERT_PTR_EQUAL(check->prev, check_last) @@ -557,53 +503,31 @@ check = check->next; } CU_ASSERT_PTR_NULL(check) - CU_ASSERT_EQUAL(end->data, expected[99]) + CU_ASSERT_PTR_EQUAL(end, check_last) + + destroy_test_data(begin); } void test_linked_list_reverse(void) { - struct node { - void *next; - }; - struct dnode { - void *next; - void *prev; - }; - ptrdiff_t loc = offsetof(struct node, next); - ptrdiff_t ploc = offsetof(struct dnode, prev); + void *begin, *end; - void *begin; - void *end; + int data[] = {2, 4, 6, 8}; + int reversed[] = {8, 6, 4, 2}; - // single linked list - struct node third = {NULL}; - struct node second = {&third}; - struct node first = {&second}; - begin = &first; + void *list = create_test_data(4, data); + void *expected = create_test_data(4, reversed); - cx_linked_list_reverse(&begin, NULL, -1, loc); - CU_ASSERT_PTR_EQUAL(begin, &third) - CU_ASSERT_PTR_EQUAL(third.next, &second) - CU_ASSERT_PTR_EQUAL(second.next, &first) - CU_ASSERT_PTR_NULL(first.next) + begin = list; + end = cx_linked_list_last(list, loc_next); - // doubly linked list - struct dnode dthird = {NULL , NULL}; - struct dnode dsecond = {&dthird, NULL}; - struct dnode dfirst = {&dsecond, NULL}; - dthird.prev = &dsecond; - dsecond.prev = &dfirst; - begin = &dfirst; - end = &dthird; + cx_linked_list_reverse(&begin, &end, loc_prev, loc_next); + CU_ASSERT_PTR_EQUAL(end, list) + CU_ASSERT_PTR_EQUAL(begin, cx_linked_list_first(end, loc_prev)) + CU_ASSERT_TRUE(0 == cx_linked_list_compare(begin, expected, loc_next, loc_data, + 0, (CxListComparator) cmp_int)) - cx_linked_list_reverse(&begin, &end, ploc, loc); - CU_ASSERT_PTR_EQUAL(begin, &dthird) - CU_ASSERT_PTR_EQUAL(end, &dfirst) - CU_ASSERT_PTR_EQUAL(dthird.next, &dsecond) - CU_ASSERT_PTR_EQUAL(dsecond.next, &dfirst) - CU_ASSERT_PTR_NULL(dfirst.next) - CU_ASSERT_PTR_NULL(dthird.prev) - CU_ASSERT_PTR_EQUAL(dsecond.prev, &dthird) - CU_ASSERT_PTR_EQUAL(dfirst.prev, &dsecond) + destroy_test_data(begin); + destroy_test_data(expected); } void test_hl_linked_list_create(void) { @@ -1028,6 +952,7 @@ cu_add_test(suite, test_linked_list_link_unlink); cu_add_test(suite, test_linked_list_at); + cu_add_test(suite, test_linked_list_compare); cu_add_test(suite, test_linked_list_prepend); cu_add_test(suite, test_linked_list_add); cu_add_test(suite, test_linked_list_insert);
