--- 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);