--- a/tests/test_list.cpp Sun Jan 07 11:01:33 2024 +0100
+++ b/tests/test_list.cpp Tue Jan 09 00:01:03 2024 +0100
@@ -38,523 +38,6 @@
#include <unordered_set>
#include <algorithm>
-struct node {
- node *next = NULL;
- node *prev = NULL;
- int data = 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_test_data {
- node *begin = NULL;
-
- explicit node_test_data(node *begin) : begin(begin) {
- auto n = begin;
- while (n != NULL) {
- nodes.push_back(n);
- n = n->next;
- }
- }
-
- node_test_data(node_test_data &) = delete;
-
- node_test_data(node_test_data &&) = default;
-
- ~node_test_data() {
- for (auto &&n: nodes) delete n;
- }
-
-private:
- std::vector<node *> nodes;
-};
-
-static node_test_data create_nodes_test_data(size_t len) {
- if (len == 0) return node_test_data{NULL};
- auto begin = new node;
- auto prev = begin;
- for (size_t i = 1; i < len; i++) {
- auto n = new node;
- cx_linked_list_link(prev, n, loc_prev, loc_next);
- prev = n;
- }
- return node_test_data{begin};
-}
-
-template<typename InputIter>
-static node_test_data create_nodes_test_data(
- InputIter begin,
- InputIter end
-) {
- if (begin == end) return node_test_data{NULL};
- node *first = new node;
- first->data = *begin;
- node *prev = first;
- begin++;
- for (; begin != end; begin++) {
- auto n = new node;
- n->data = *begin;
- cx_linked_list_link(prev, n, loc_prev, loc_next);
- prev = n;
- }
- return node_test_data{first};
-}
-
-static node_test_data create_nodes_test_data(std::initializer_list<int> data) {
- return create_nodes_test_data(data.begin(), data.end());
-}
-
-template<size_t N>
-struct int_test_data {
- std::array<int, N> data;
-
- int_test_data() {
- cx_for_n (i, N) data[i] = ::rand(); // NOLINT(cert-msc50-cpp)
- }
-};
-
-TEST(LinkedList_LowLevel, link_unlink) {
- node a, b, c;
-
- cx_linked_list_link(&a, &b, loc_prev, loc_next);
- CX_TEST_ASSERT(a.prev == NULL);
- CX_TEST_ASSERT(a.next == &b);
- CX_TEST_ASSERT(b.prev == &a);
- CX_TEST_ASSERT(b.next == NULL);
-
- cx_linked_list_unlink(&a, &b, loc_prev, loc_next);
- CX_TEST_ASSERT(a.prev == NULL);
- CX_TEST_ASSERT(a.next == NULL);
- CX_TEST_ASSERT(b.prev == NULL);
- CX_TEST_ASSERT(b.next == 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);
- CX_TEST_ASSERT(a.prev == NULL);
- CX_TEST_ASSERT(a.next == &b);
- CX_TEST_ASSERT(b.prev == &a);
- CX_TEST_ASSERT(b.next == NULL);
- CX_TEST_ASSERT(c.prev == NULL);
- CX_TEST_ASSERT(c.next == NULL);
-}
-
-TEST(LinkedList_LowLevel, cx_linked_list_at) {
- node a, b, c, 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);
-
- EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 0), &a);
- EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 1), &b);
- EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 2), &c);
- EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 3), &d);
- EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 4), NULL);
-
- EXPECT_EQ(cx_linked_list_at(&b, 1, loc_prev, 0), &a);
- EXPECT_EQ(cx_linked_list_at(&b, 1, loc_next, 1), &b);
- EXPECT_EQ(cx_linked_list_at(&b, 1, loc_next, 2), &c);
- EXPECT_EQ(cx_linked_list_at(&b, 1, loc_next, 3), &d);
- EXPECT_EQ(cx_linked_list_at(&b, 1, loc_next, 4), NULL);
-
- EXPECT_EQ(cx_linked_list_at(&d, 3, loc_prev, 0), &a);
- EXPECT_EQ(cx_linked_list_at(&d, 3, loc_prev, 1), &b);
-}
-
-TEST(LinkedList_LowLevel, cx_linked_list_find) {
- auto testdata = create_nodes_test_data({2, 4, 6, 8});
- auto list = testdata.begin;
- int s;
-
- s = 2;
- EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s), 0);
- s = 4;
- EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s), 1);
- s = 6;
- EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s), 2);
- s = 8;
- EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s), 3);
- s = 10;
- EXPECT_LT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s), 0);
- s = -2;
- EXPECT_LT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s), 0);
-}
-
-TEST(LinkedList_LowLevel, cx_linked_list_compare) {
- auto ta = create_nodes_test_data({2, 4, 6, 8});
- auto tb = create_nodes_test_data({2, 4, 6});
- 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, cx_cmp_int), 0);
- EXPECT_LT(cx_linked_list_compare(lb, la, loc_next, loc_data, cx_cmp_int), 0);
- EXPECT_GT(cx_linked_list_compare(lc, la, loc_next, loc_data, cx_cmp_int), 0);
- EXPECT_LT(cx_linked_list_compare(la, lc, loc_next, loc_data, cx_cmp_int), 0);
- EXPECT_EQ(cx_linked_list_compare(la, la, loc_next, loc_data, cx_cmp_int), 0);
-}
-
-TEST(LinkedList_LowLevel, cx_linked_list_add) {
- // test with begin, end / prev, next
- {
- node nodes[4];
- void *begin = NULL, *end = NULL;
-
- cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[0]);
- CX_TEST_ASSERT(begin == &nodes[0]);
- CX_TEST_ASSERT(end == &nodes[0]);
- CX_TEST_ASSERT(nodes[0].prev == NULL);
- CX_TEST_ASSERT(nodes[0].next == NULL);
-
- cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[1]);
- CX_TEST_ASSERT(begin == &nodes[0]);
- CX_TEST_ASSERT(end == &nodes[1]);
- CX_TEST_ASSERT(nodes[0].next == &nodes[1]);
- CX_TEST_ASSERT(nodes[1].prev == &nodes[0]);
- }
-
- // test with begin only / prev, next
- {
- node nodes[4];
- void *begin = NULL;
-
- cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[0]);
- CX_TEST_ASSERT(begin == &nodes[0]);
- cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[1]);
- CX_TEST_ASSERT(begin == &nodes[0]);
- CX_TEST_ASSERT(nodes[0].next == &nodes[1]);
- CX_TEST_ASSERT(nodes[1].prev == &nodes[0]);
-
- cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[2]);
- CX_TEST_ASSERT(nodes[1].next == &nodes[2]);
- CX_TEST_ASSERT(nodes[2].prev == &nodes[1]);
- }
-
- // test with end only / prev, next
- {
- node nodes[4];
- void *end = NULL;
-
- cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[0]);
- CX_TEST_ASSERT(end == &nodes[0]);
- cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[1]);
- CX_TEST_ASSERT(end == &nodes[1]);
- CX_TEST_ASSERT(nodes[0].next == &nodes[1]);
- CX_TEST_ASSERT(nodes[1].prev == &nodes[0]);
-
- cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[2]);
- CX_TEST_ASSERT(end == &nodes[2]);
- CX_TEST_ASSERT(nodes[1].next == &nodes[2]);
- CX_TEST_ASSERT(nodes[2].prev == &nodes[1]);
- }
-
- // test with begin, end / next
- {
- node nodes[4];
- void *begin = NULL, *end = NULL;
-
- cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[0]);
- CX_TEST_ASSERT(begin == &nodes[0]);
- CX_TEST_ASSERT(end == &nodes[0]);
- cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[1]);
- CX_TEST_ASSERT(end == &nodes[1]);
- CX_TEST_ASSERT(nodes[0].next == &nodes[1]);
- CX_TEST_ASSERT(nodes[1].prev == NULL);
- }
-}
-
-TEST(LinkedList_LowLevel, cx_linked_list_prepend) {
- // test with begin, end / prev, next
- {
- node nodes[4];
- void *begin = NULL, *end = NULL;
-
- cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[0]);
- CX_TEST_ASSERT(begin == &nodes[0]);
- CX_TEST_ASSERT(end == &nodes[0]);
- CX_TEST_ASSERT(nodes[0].prev == NULL);
- CX_TEST_ASSERT(nodes[0].next == NULL);
-
- cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[1]);
- CX_TEST_ASSERT(begin == &nodes[1]);
- CX_TEST_ASSERT(end == &nodes[0]);
- CX_TEST_ASSERT(nodes[1].next == &nodes[0]);
- CX_TEST_ASSERT(nodes[0].prev == &nodes[1]);
- }
-
- // test with begin only / prev, next
- {
- node nodes[4];
- void *begin = NULL;
-
- cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[0]);
- CX_TEST_ASSERT(begin == &nodes[0]);
- cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[1]);
- CX_TEST_ASSERT(begin == &nodes[1]);
- CX_TEST_ASSERT(nodes[1].next == &nodes[0]);
- CX_TEST_ASSERT(nodes[0].prev == &nodes[1]);
-
- cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[2]);
- CX_TEST_ASSERT(begin == &nodes[2]);
- CX_TEST_ASSERT(nodes[2].next == &nodes[1]);
- CX_TEST_ASSERT(nodes[1].prev == &nodes[2]);
- }
-
- // test with end only / prev, next
- {
- node nodes[4];
- void *end = NULL;
-
- cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[0]);
- CX_TEST_ASSERT(end == &nodes[0]);
- cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[1]);
- CX_TEST_ASSERT(end == &nodes[0]);
- CX_TEST_ASSERT(nodes[1].next == &nodes[0]);
- CX_TEST_ASSERT(nodes[0].prev == &nodes[1]);
-
- cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[2]);
- CX_TEST_ASSERT(end == &nodes[0]);
- CX_TEST_ASSERT(nodes[2].next == &nodes[1]);
- CX_TEST_ASSERT(nodes[1].prev == &nodes[2]);
- }
-
- // test with begin, end / next
- {
- node nodes[4];
- void *begin = NULL, *end = NULL;
-
- cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[0]);
- CX_TEST_ASSERT(begin == &nodes[0]);
- CX_TEST_ASSERT(end == &nodes[0]);
- cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[1]);
- cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[2]);
- CX_TEST_ASSERT(begin == &nodes[2]);
- CX_TEST_ASSERT(end == &nodes[0]);
- CX_TEST_ASSERT(nodes[1].next == &nodes[0]);
- CX_TEST_ASSERT(nodes[2].next == &nodes[1]);
- CX_TEST_ASSERT(nodes[1].prev == NULL);
- CX_TEST_ASSERT(nodes[0].prev == NULL);
- }
-}
-
-TEST(LinkedList_LowLevel, cx_linked_list_insert) {
- // insert mid list
- {
- node nodes[4];
- void *begin = &nodes[0], *end = &nodes[2];
-
- cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
- cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
-
- cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3]);
- CX_TEST_ASSERT(begin == &nodes[0]);
- CX_TEST_ASSERT(end == &nodes[2]);
- CX_TEST_ASSERT(nodes[1].next == &nodes[3]);
- CX_TEST_ASSERT(nodes[2].prev == &nodes[3]);
- CX_TEST_ASSERT(nodes[3].prev == &nodes[1]);
- CX_TEST_ASSERT(nodes[3].next == &nodes[2]);
- }
-
- // insert end
- {
- node nodes[4];
- void *begin = &nodes[0], *end = &nodes[2];
-
- cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
- cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
-
- cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3]);
- CX_TEST_ASSERT(begin == &nodes[0]);
- CX_TEST_ASSERT(end == &nodes[3]);
- CX_TEST_ASSERT(nodes[2].next == &nodes[3]);
- CX_TEST_ASSERT(nodes[3].prev == &nodes[2]);
- CX_TEST_ASSERT(nodes[3].next == NULL);
- }
-
- // insert begin
- {
- node nodes[4];
- void *begin = &nodes[0], *end = &nodes[2];
-
- cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
- cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
-
- cx_linked_list_insert(&begin, &end, loc_prev, loc_next, NULL, &nodes[3]);
- CX_TEST_ASSERT(begin == &nodes[3]);
- CX_TEST_ASSERT(end == &nodes[2]);
- CX_TEST_ASSERT(nodes[0].prev == &nodes[3]);
- CX_TEST_ASSERT(nodes[3].prev == NULL);
- CX_TEST_ASSERT(nodes[3].next == &nodes[0]);
- }
-}
-
-TEST(LinkedList_LowLevel, cx_linked_list_insert_chain) {
- // insert mid list
- {
- node nodes[5];
- void *begin = &nodes[0], *end = &nodes[2];
-
- cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
- cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
- cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next);
-
- cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3], NULL);
- CX_TEST_ASSERT(begin == &nodes[0]);
- CX_TEST_ASSERT(end == &nodes[2]);
- CX_TEST_ASSERT(nodes[1].next == &nodes[3]);
- CX_TEST_ASSERT(nodes[2].prev == &nodes[4]);
- CX_TEST_ASSERT(nodes[3].prev == &nodes[1]);
- CX_TEST_ASSERT(nodes[4].next == &nodes[2]);
- }
-
- // insert end
- {
- node nodes[5];
- void *begin = &nodes[0], *end = &nodes[2];
-
- cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
- cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
- cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next);
-
- cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3], NULL);
- CX_TEST_ASSERT(begin == &nodes[0]);
- CX_TEST_ASSERT(end == &nodes[4]);
- CX_TEST_ASSERT(nodes[2].next == &nodes[3]);
- CX_TEST_ASSERT(nodes[3].prev == &nodes[2]);
- CX_TEST_ASSERT(nodes[4].next == NULL);
- }
-
- // insert begin
- {
- node nodes[5];
- void *begin = &nodes[0], *end = &nodes[2];
-
- cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
- cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
- cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next);
-
- cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, NULL, &nodes[3], NULL);
- CX_TEST_ASSERT(begin == &nodes[3]);
- CX_TEST_ASSERT(end == &nodes[2]);
- CX_TEST_ASSERT(nodes[0].prev == &nodes[4]);
- CX_TEST_ASSERT(nodes[3].prev == NULL);
- CX_TEST_ASSERT(nodes[4].next == &nodes[0]);
- }
-}
-
-TEST(LinkedList_LowLevel, cx_linked_list_first) {
- auto testdata = create_nodes_test_data(3);
- auto begin = testdata.begin;
- EXPECT_EQ(cx_linked_list_first(begin, loc_prev), begin);
- EXPECT_EQ(cx_linked_list_first(begin->next, loc_prev), begin);
- EXPECT_EQ(cx_linked_list_first(begin->next->next, loc_prev), begin);
-}
-
-TEST(LinkedList_LowLevel, cx_linked_list_last) {
- auto testdata = create_nodes_test_data(3);
- auto begin = testdata.begin;
- auto end = begin->next->next;
- EXPECT_EQ(cx_linked_list_last(begin, loc_next), end);
- EXPECT_EQ(cx_linked_list_last(begin->next, loc_next), end);
- EXPECT_EQ(cx_linked_list_last(begin->next->next, loc_next), end);
-}
-
-TEST(LinkedList_LowLevel, cx_linked_list_prev) {
- auto testdata = create_nodes_test_data(3);
- auto begin = testdata.begin;
- EXPECT_EQ(cx_linked_list_prev(begin, loc_next, begin), NULL);
- EXPECT_EQ(cx_linked_list_prev(begin, loc_next, begin->next), begin);
- EXPECT_EQ(cx_linked_list_prev(begin, loc_next, begin->next->next), begin->next);
-}
-
-TEST(LinkedList_LowLevel, cx_linked_list_remove) {
- auto testdata = create_nodes_test_data({2, 4, 6});
- auto begin = reinterpret_cast<void *>(testdata.begin);
- auto first = testdata.begin;
- auto second = first->next;
- auto third = second->next;
- auto end = reinterpret_cast<void *>(third);
-
- cx_linked_list_remove(&begin, &end, loc_prev, loc_next, second);
- CX_TEST_ASSERT(begin == first);
- CX_TEST_ASSERT(end == third);
- CX_TEST_ASSERT(first->prev == NULL);
- CX_TEST_ASSERT(first->next == third);
- CX_TEST_ASSERT(third->prev == first);
- CX_TEST_ASSERT(third->next == NULL);
-
- cx_linked_list_remove(&begin, &end, loc_prev, loc_next, third);
- CX_TEST_ASSERT(begin == first);
- CX_TEST_ASSERT(end == first);
- CX_TEST_ASSERT(first->prev == NULL);
- CX_TEST_ASSERT(first->next == NULL);
-
- cx_linked_list_remove(&begin, &end, loc_prev, loc_next, first);
- CX_TEST_ASSERT(begin == NULL);
- CX_TEST_ASSERT(end == NULL);
-}
-
-TEST(LinkedList_LowLevel, cx_linked_list_size) {
- EXPECT_EQ(cx_linked_list_size(NULL, loc_next), 0);
-
- {
- auto testdata = create_nodes_test_data(5);
- EXPECT_EQ(cx_linked_list_size(testdata.begin, loc_next), 5);
- }
-
- {
- auto testdata = create_nodes_test_data(13);
- EXPECT_EQ(cx_linked_list_size(testdata.begin, loc_next), 13);
- }
-}
-
-TEST(LinkedList_LowLevel, cx_linked_list_sort_empty) {
- void *begin = NULL;
- EXPECT_NO_FATAL_FAILURE(
- cx_linked_list_sort(&begin, NULL, loc_prev, loc_next, loc_data, cx_cmp_int);
- );
-}
-
-TEST(LinkedList_LowLevel, cx_linked_list_sort) {
- int_test_data<1500> testdata;
- std::array<int, 1500> sorted{};
- std::partial_sort_copy(testdata.data.begin(), testdata.data.end(), sorted.begin(), sorted.end());
-
- auto scrambled = create_nodes_test_data(testdata.data.begin(), testdata.data.end());
- void *begin = scrambled.begin;
- void *end = cx_linked_list_last(begin, loc_next);
-
- cx_linked_list_sort(&begin, &end, loc_prev, loc_next, loc_data, cx_cmp_int);
-
- node *check = reinterpret_cast<node *>(begin);
- node *check_last = NULL;
- cx_for_n (i, sorted.size()) {
- CX_TEST_ASSERT(check->data == sorted[i]);
- CX_TEST_ASSERT(check->prev == check_last);
- if (i < sorted.size() - 1) {
- ASSERT_NE(check->next, NULL);
- }
- check_last = check;
- check = check->next;
- }
- CX_TEST_ASSERT(check == NULL);
- CX_TEST_ASSERT(end == check_last);
-}
-
-TEST(LinkedList_LowLevel, cx_linked_list_reverse) {
- auto testdata = create_nodes_test_data({2, 4, 6, 8});
- auto expected = create_nodes_test_data({8, 6, 4, 2});
-
- auto begin = reinterpret_cast<void *>(testdata.begin);
- auto end = cx_linked_list_last(begin, loc_next);
- auto orig_begin = begin, orig_end = end;
-
- cx_linked_list_reverse(&begin, &end, loc_prev, loc_next);
- CX_TEST_ASSERT(end == orig_begin);
- CX_TEST_ASSERT(begin == orig_end);
- EXPECT_EQ(cx_linked_list_compare(begin, expected.begin, loc_next, loc_data, cx_cmp_int), 0);
-}
class HighLevelTest : public ::testing::Test {
mutable std::unordered_set<CxList *> lists;