diff -r e0300c2c4e95 -r 7644da6e2d35 tests/test_list.cpp --- 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 #include -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 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 -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 data) { - return create_nodes_test_data(data.begin(), data.end()); -} - -template -struct int_test_data { - std::array 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(testdata.begin); - auto first = testdata.begin; - auto second = first->next; - auto third = second->next; - auto end = reinterpret_cast(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 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(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(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 lists;