diff -r bf817b825ed2 -r e081643aae2a tests/test_list.cpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/tests/test_list.cpp Tue Feb 07 21:55:37 2023 +0100 @@ -0,0 +1,1077 @@ +/* + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "cx/linked_list.h" +#include "cx/array_list.h" +#include "cx/utils.h" +#include "cx/compare.h" +#include "util_allocator.h" + +#include +#include +#include +#include +#include + +struct node { + node *next = nullptr; + node *prev = nullptr; + 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 = nullptr; + + explicit node_test_data(node *begin) : begin(begin) { + auto n = begin; + while (n != nullptr) { + 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{nullptr}; + 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{nullptr}; + 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); + EXPECT_EQ(a.prev, nullptr); + EXPECT_EQ(a.next, &b); + EXPECT_EQ(b.prev, &a); + EXPECT_EQ(b.next, nullptr); + + cx_linked_list_unlink(&a, &b, loc_prev, loc_next); + EXPECT_EQ(a.prev, nullptr); + EXPECT_EQ(a.next, nullptr); + EXPECT_EQ(b.prev, nullptr); + EXPECT_EQ(b.next, nullptr); + + 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); + EXPECT_EQ(a.prev, nullptr); + EXPECT_EQ(a.next, &b); + EXPECT_EQ(b.prev, &a); + EXPECT_EQ(b.next, nullptr); + EXPECT_EQ(c.prev, nullptr); + EXPECT_EQ(c.next, nullptr); +} + +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), nullptr); + + 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), nullptr); + + 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_EQ(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s), 4); + s = -2; + EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s), 4); +} + +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 = nullptr, *end = nullptr; + + cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[0]); + EXPECT_EQ(begin, &nodes[0]); + EXPECT_EQ(end, &nodes[0]); + EXPECT_EQ(nodes[0].prev, nullptr); + EXPECT_EQ(nodes[0].next, nullptr); + + cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[1]); + EXPECT_EQ(begin, &nodes[0]); + EXPECT_EQ(end, &nodes[1]); + EXPECT_EQ(nodes[0].next, &nodes[1]); + EXPECT_EQ(nodes[1].prev, &nodes[0]); + } + + // test with begin only / prev, next + { + node nodes[4]; + void *begin = nullptr; + + cx_linked_list_add(&begin, nullptr, loc_prev, loc_next, &nodes[0]); + EXPECT_EQ(begin, &nodes[0]); + cx_linked_list_add(&begin, nullptr, loc_prev, loc_next, &nodes[1]); + EXPECT_EQ(begin, &nodes[0]); + EXPECT_EQ(nodes[0].next, &nodes[1]); + EXPECT_EQ(nodes[1].prev, &nodes[0]); + + cx_linked_list_add(&begin, nullptr, loc_prev, loc_next, &nodes[2]); + EXPECT_EQ(nodes[1].next, &nodes[2]); + EXPECT_EQ(nodes[2].prev, &nodes[1]); + } + + // test with end only / prev, next + { + node nodes[4]; + void *end = nullptr; + + cx_linked_list_add(nullptr, &end, loc_prev, loc_next, &nodes[0]); + EXPECT_EQ(end, &nodes[0]); + cx_linked_list_add(nullptr, &end, loc_prev, loc_next, &nodes[1]); + EXPECT_EQ(end, &nodes[1]); + EXPECT_EQ(nodes[0].next, &nodes[1]); + EXPECT_EQ(nodes[1].prev, &nodes[0]); + + cx_linked_list_add(nullptr, &end, loc_prev, loc_next, &nodes[2]); + EXPECT_EQ(end, &nodes[2]); + EXPECT_EQ(nodes[1].next, &nodes[2]); + EXPECT_EQ(nodes[2].prev, &nodes[1]); + } + + // test with begin, end / next + { + node nodes[4]; + void *begin = nullptr, *end = nullptr; + + cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[0]); + EXPECT_EQ(begin, &nodes[0]); + EXPECT_EQ(end, &nodes[0]); + cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[1]); + EXPECT_EQ(end, &nodes[1]); + EXPECT_EQ(nodes[0].next, &nodes[1]); + EXPECT_EQ(nodes[1].prev, nullptr); + } +} + +TEST(LinkedList_LowLevel, cx_linked_list_prepend) { + // test with begin, end / prev, next + { + node nodes[4]; + void *begin = nullptr, *end = nullptr; + + cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[0]); + EXPECT_EQ(begin, &nodes[0]); + EXPECT_EQ(end, &nodes[0]); + EXPECT_EQ(nodes[0].prev, nullptr); + EXPECT_EQ(nodes[0].next, nullptr); + + cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[1]); + EXPECT_EQ(begin, &nodes[1]); + EXPECT_EQ(end, &nodes[0]); + EXPECT_EQ(nodes[1].next, &nodes[0]); + EXPECT_EQ(nodes[0].prev, &nodes[1]); + } + + // test with begin only / prev, next + { + node nodes[4]; + void *begin = nullptr; + + cx_linked_list_prepend(&begin, nullptr, loc_prev, loc_next, &nodes[0]); + EXPECT_EQ(begin, &nodes[0]); + cx_linked_list_prepend(&begin, nullptr, loc_prev, loc_next, &nodes[1]); + EXPECT_EQ(begin, &nodes[1]); + EXPECT_EQ(nodes[1].next, &nodes[0]); + EXPECT_EQ(nodes[0].prev, &nodes[1]); + + cx_linked_list_prepend(&begin, nullptr, loc_prev, loc_next, &nodes[2]); + EXPECT_EQ(begin, &nodes[2]); + EXPECT_EQ(nodes[2].next, &nodes[1]); + EXPECT_EQ(nodes[1].prev, &nodes[2]); + } + + // test with end only / prev, next + { + node nodes[4]; + void *end = nullptr; + + cx_linked_list_prepend(nullptr, &end, loc_prev, loc_next, &nodes[0]); + EXPECT_EQ(end, &nodes[0]); + cx_linked_list_prepend(nullptr, &end, loc_prev, loc_next, &nodes[1]); + EXPECT_EQ(end, &nodes[0]); + EXPECT_EQ(nodes[1].next, &nodes[0]); + EXPECT_EQ(nodes[0].prev, &nodes[1]); + + cx_linked_list_prepend(nullptr, &end, loc_prev, loc_next, &nodes[2]); + EXPECT_EQ(end, &nodes[0]); + EXPECT_EQ(nodes[2].next, &nodes[1]); + EXPECT_EQ(nodes[1].prev, &nodes[2]); + } + + // test with begin, end / next + { + node nodes[4]; + void *begin = nullptr, *end = nullptr; + + cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[0]); + EXPECT_EQ(begin, &nodes[0]); + EXPECT_EQ(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]); + EXPECT_EQ(begin, &nodes[2]); + EXPECT_EQ(end, &nodes[0]); + EXPECT_EQ(nodes[1].next, &nodes[0]); + EXPECT_EQ(nodes[2].next, &nodes[1]); + EXPECT_EQ(nodes[1].prev, nullptr); + EXPECT_EQ(nodes[0].prev, nullptr); + } +} + +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]); + EXPECT_EQ(begin, &nodes[0]); + EXPECT_EQ(end, &nodes[2]); + EXPECT_EQ(nodes[1].next, &nodes[3]); + EXPECT_EQ(nodes[2].prev, &nodes[3]); + EXPECT_EQ(nodes[3].prev, &nodes[1]); + EXPECT_EQ(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]); + EXPECT_EQ(begin, &nodes[0]); + EXPECT_EQ(end, &nodes[3]); + EXPECT_EQ(nodes[2].next, &nodes[3]); + EXPECT_EQ(nodes[3].prev, &nodes[2]); + EXPECT_EQ(nodes[3].next, nullptr); + } + + // 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, nullptr, &nodes[3]); + EXPECT_EQ(begin, &nodes[3]); + EXPECT_EQ(end, &nodes[2]); + EXPECT_EQ(nodes[0].prev, &nodes[3]); + EXPECT_EQ(nodes[3].prev, nullptr); + EXPECT_EQ(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], nullptr); + EXPECT_EQ(begin, &nodes[0]); + EXPECT_EQ(end, &nodes[2]); + EXPECT_EQ(nodes[1].next, &nodes[3]); + EXPECT_EQ(nodes[2].prev, &nodes[4]); + EXPECT_EQ(nodes[3].prev, &nodes[1]); + EXPECT_EQ(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], nullptr); + EXPECT_EQ(begin, &nodes[0]); + EXPECT_EQ(end, &nodes[4]); + EXPECT_EQ(nodes[2].next, &nodes[3]); + EXPECT_EQ(nodes[3].prev, &nodes[2]); + EXPECT_EQ(nodes[4].next, nullptr); + } + + // 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, nullptr, &nodes[3], nullptr); + EXPECT_EQ(begin, &nodes[3]); + EXPECT_EQ(end, &nodes[2]); + EXPECT_EQ(nodes[0].prev, &nodes[4]); + EXPECT_EQ(nodes[3].prev, nullptr); + EXPECT_EQ(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), nullptr); + 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); + EXPECT_EQ(begin, first); + EXPECT_EQ(end, third); + EXPECT_EQ(first->prev, nullptr); + EXPECT_EQ(first->next, third); + EXPECT_EQ(third->prev, first); + EXPECT_EQ(third->next, nullptr); + + cx_linked_list_remove(&begin, &end, loc_prev, loc_next, third); + EXPECT_EQ(begin, first); + EXPECT_EQ(end, first); + EXPECT_EQ(first->prev, nullptr); + EXPECT_EQ(first->next, nullptr); + + cx_linked_list_remove(&begin, &end, loc_prev, loc_next, first); + EXPECT_EQ(begin, nullptr); + EXPECT_EQ(end, nullptr); +} + +TEST(LinkedList_LowLevel, cx_linked_list_size) { + EXPECT_EQ(cx_linked_list_size(nullptr, 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) { + 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 = nullptr; + cx_for_n (i, sorted.size()) { + EXPECT_EQ(check->data, sorted[i]); + EXPECT_EQ(check->prev, check_last); + if (i < sorted.size() - 1) { + ASSERT_NE(check->next, nullptr); + } + check_last = check; + check = check->next; + } + EXPECT_EQ(check, nullptr); + EXPECT_EQ(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); + EXPECT_EQ(end, orig_begin); + EXPECT_EQ(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; +protected: + CxTestingAllocator testingAllocator; + + void TearDown() override { + for (auto &&l: lists) cxListDestroy(l); + EXPECT_TRUE(testingAllocator.verify()); + } + + static constexpr size_t testdata_len = 250; + int_test_data testdata; + + auto autofree(CxList *list) const -> CxList * { + if (list != nullptr) lists.insert(list); + return list; + } + + auto linkedListFromTestData() const -> CxList * { + auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int))); + cxListAddArray(list, testdata.data.data(), testdata_len); + return list; + } + + auto pointerLinkedListFromTestData() const -> CxList * { + auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int *))); + cxListStorePointers(list); + // note: cannot use cxListAddArray() because we don't have a list of pointers + cx_for_n(i, testdata_len) cxListAdd(list, &testdata.data[i]); + return list; + } + + auto arrayListFromTestData() const -> CxList * { + auto list = autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), testdata_len)); + cxListAddArray(list, testdata.data.data(), testdata_len); + return list; + } + + void verifyCreate(CxList *list) const { + EXPECT_EQ(list->content_destructor_type, CX_DESTRUCTOR_NONE); + EXPECT_EQ(list->size, 0); + EXPECT_EQ(list->allocator, &testingAllocator); + EXPECT_EQ(list->cmpfunc, cx_cmp_int); + } + + void verifyAdd( + CxList *list, + bool as_pointer + ) { + auto len = testdata_len; + cx_for_n (i, len) EXPECT_EQ(cxListAdd(list, &testdata.data[i]), 0); + EXPECT_EQ(list->size, len); + EXPECT_GE(list->capacity, list->size); + cx_for_n (i, len) EXPECT_EQ(*(int *) cxListAt(list, i), testdata.data[i]); + cx_for_n (i, len) ++testdata.data[i]; + if (as_pointer) { + cx_for_n (i, len) EXPECT_EQ(*(int *) cxListAt(list, i), testdata.data[i]); + } else { + cx_for_n (i, len) EXPECT_EQ(*(int *) cxListAt(list, i), testdata.data[i] - 1); + } + } + + static void verifyInsert(CxList *list) { + int a = 5, b = 47, c = 13, d = 42; + + EXPECT_NE(cxListInsert(list, 1, &a), 0); + EXPECT_EQ(list->size, 0); + EXPECT_EQ(cxListInsert(list, 0, &a), 0); + EXPECT_EQ(list->size, 1); + EXPECT_EQ(cxListInsert(list, 0, &b), 0); + EXPECT_EQ(list->size, 2); + EXPECT_EQ(cxListInsert(list, 1, &c), 0); + EXPECT_EQ(list->size, 3); + EXPECT_EQ(cxListInsert(list, 3, &d), 0); + + ASSERT_EQ(list->size, 4); + EXPECT_GE(list->capacity, list->size); + + EXPECT_EQ(*(int *) cxListAt(list, 0), 47); + EXPECT_EQ(*(int *) cxListAt(list, 1), 13); + EXPECT_EQ(*(int *) cxListAt(list, 2), 5); + EXPECT_EQ(*(int *) cxListAt(list, 3), 42); + } + + static void verifyInsertArray( + CxList *list, + bool pointers = false + ) { + int a[5] = {5, 47, 11, 13, 42}; + int b[5] = {9, 18, 72, 50, 7}; + int *aptr[5]; + int *bptr[5]; + cx_for_n(i, 5) { + aptr[i] = &a[i]; + bptr[i] = &b[i]; + } + + size_t inserted; + + if (pointers) { + inserted = cxListInsertArray(list, 0, aptr, 5); + } else { + inserted = cxListInsertArray(list, 0, a, 5); + } + EXPECT_EQ(inserted, 5); + EXPECT_EQ(*(int *) cxListAt(list, 0), 5); + EXPECT_EQ(*(int *) cxListAt(list, 1), 47); + EXPECT_EQ(*(int *) cxListAt(list, 2), 11); + EXPECT_EQ(*(int *) cxListAt(list, 3), 13); + EXPECT_EQ(*(int *) cxListAt(list, 4), 42); + if (pointers) { + inserted = cxListInsertArray(list, 3, bptr, 5); + } else { + inserted = cxListInsertArray(list, 3, b, 5); + } + EXPECT_EQ(inserted, 5); + EXPECT_EQ(*(int *) cxListAt(list, 0), 5); + EXPECT_EQ(*(int *) cxListAt(list, 1), 47); + EXPECT_EQ(*(int *) cxListAt(list, 2), 11); + EXPECT_EQ(*(int *) cxListAt(list, 3), 9); + EXPECT_EQ(*(int *) cxListAt(list, 4), 18); + EXPECT_EQ(*(int *) cxListAt(list, 5), 72); + EXPECT_EQ(*(int *) cxListAt(list, 6), 50); + EXPECT_EQ(*(int *) cxListAt(list, 7), 7); + EXPECT_EQ(*(int *) cxListAt(list, 8), 13); + EXPECT_EQ(*(int *) cxListAt(list, 9), 42); + } + + void verifyRemove(CxList *list) const { + EXPECT_EQ(cxListRemove(list, 2), 0); + EXPECT_EQ(cxListRemove(list, 4), 0); + EXPECT_EQ(list->size, testdata_len - 2); + EXPECT_GE(list->capacity, list->size); + EXPECT_EQ(*(int *) cxListAt(list, 0), testdata.data[0]); + EXPECT_EQ(*(int *) cxListAt(list, 1), testdata.data[1]); + EXPECT_EQ(*(int *) cxListAt(list, 2), testdata.data[3]); + EXPECT_EQ(*(int *) cxListAt(list, 3), testdata.data[4]); + EXPECT_EQ(*(int *) cxListAt(list, 4), testdata.data[6]); + + EXPECT_EQ(cxListRemove(list, 0), 0); + EXPECT_EQ(list->size, testdata_len - 3); + EXPECT_GE(list->capacity, list->size); + EXPECT_EQ(*(int *) cxListAt(list, 0), testdata.data[1]); + EXPECT_EQ(*(int *) cxListAt(list, 1), testdata.data[3]); + + EXPECT_NE(cxListRemove(list, testdata_len), 0); + } + + void verifyAt(CxList *list) const { + auto len = testdata_len; + EXPECT_EQ(list->size, len); + cx_for_n (i, len) { + EXPECT_EQ(*(int *) cxListAt(list, i), testdata.data[i]); + } + EXPECT_EQ(cxListAt(list, list->size), nullptr); + } + + void verifyFind(CxList *list) const { + cx_for_n (attempt, 25) { + size_t exp = rand() % testdata_len; // NOLINT(cert-msc50-cpp) + int val = testdata.data[exp]; + // randomly picked number could occur earlier in list - find first position + cx_for_n (i, exp) { + if (testdata.data[i] == val) { + exp = i; + break; + } + } + EXPECT_EQ(cxListFind(list, &val), exp); + } + } + + void verifySort(CxList *list) const { + std::array expected{}; + std::partial_sort_copy(testdata.data.begin(), testdata.data.end(), expected.begin(), expected.end()); + cxListSort(list); + cx_for_n (i, testdata_len) ASSERT_EQ(*(int *) cxListAt(list, i), expected[i]); + } + + void verifyIterator(CxList *list) const { + int i = 0; + auto iter = cxListBeginMut(list); + cx_foreach(int*, x, iter) { + ASSERT_EQ(iter.index, (size_t) (i + 1) / 2); + ASSERT_EQ(*x, testdata.data[i]); + if (i % 2 == 1) cxIteratorFlagRemoval(iter); + i++; + } + auto len = testdata_len; + EXPECT_EQ(i, len); + ASSERT_EQ(list->size, len / 2); + cx_for_n(j, len / 2) ASSERT_EQ(*(int *) cxListAt(list, j), testdata.data[j * 2]); + } + + static void verifyInsertViaIterator(CxList *list) { + int newdata[] = {10, 20, 30, 40, 50}; + + auto iter = cxListMutIterator(list, 2); + EXPECT_TRUE(cxIteratorValid(iter)); + EXPECT_EQ(iter.index, 2); + EXPECT_EQ(*(int *) cxIteratorCurrent(iter), 2); + cxListInsertAfter(&iter, &newdata[0]); + EXPECT_TRUE(cxIteratorValid(iter)); + EXPECT_EQ(iter.index, 2); + EXPECT_EQ(*(int *) cxIteratorCurrent(iter), 2); + cxListInsertBefore(&iter, &newdata[1]); + EXPECT_TRUE(cxIteratorValid(iter)); + EXPECT_EQ(iter.index, 3); + EXPECT_EQ(*(int *) cxIteratorCurrent(iter), 2); + + iter = cxListBeginMut(list); + cxListInsertBefore(&iter, &newdata[2]); + EXPECT_TRUE(cxIteratorValid(iter)); + EXPECT_EQ(iter.index, 1); + EXPECT_EQ(*(int *) cxIteratorCurrent(iter), 0); + iter = cxListMutIterator(list, list->size); + cxListInsertBefore(&iter, &newdata[3]); + EXPECT_FALSE(cxIteratorValid(iter)); + EXPECT_EQ(iter.index, 9); + iter = cxListMutIterator(list, list->size); + cxListInsertAfter(&iter, &newdata[4]); + EXPECT_FALSE(cxIteratorValid(iter)); + EXPECT_EQ(iter.index, 10); + + int expdata[] = {30, 0, 1, 20, 2, 10, 3, 4, 40, 50}; + cx_for_n (j, 10) EXPECT_EQ(*(int *) cxListAt(list, j), expdata[j]); + } + + void verifyReverse(CxList *list) const { + cxListReverse(list); + cx_for_n(i, testdata_len) { + ASSERT_EQ(*(int *) cxListAt(list, i), testdata.data[testdata_len - 1 - i]); + } + } + + static void verifyCompare( + CxList *left, + CxList *right + ) { + EXPECT_EQ(cxListCompare(left, right), 0); + int x = 42; + cxListAdd(left, &x); + ASSERT_GT(left->size, right->size); + EXPECT_GT(cxListCompare(left, right), 0); + EXPECT_LT(cxListCompare(right, left), 0); + cxListAdd(right, &x); + ASSERT_EQ(left->size, right->size); + EXPECT_EQ(cxListCompare(left, right), 0); + int a = 5, b = 10; + cxListInsert(left, 15, &a); + cxListInsert(right, 15, &b); + ASSERT_EQ(left->size, right->size); + EXPECT_LT(cxListCompare(left, right), 0); + EXPECT_GT(cxListCompare(right, left), 0); + *(int *) cxListAt(left, 15) = 10; + EXPECT_EQ(cxListCompare(left, right), 0); + } +}; + +class LinkedList : public HighLevelTest { +}; + +class PointerLinkedList : public HighLevelTest { +}; + +class ArrayList : public HighLevelTest { +}; + +TEST_F(PointerLinkedList, cxListStorePointers) { + auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, 47)); + EXPECT_FALSE(cxListIsStoringPointers(list)); + cxListStorePointers(list); + EXPECT_EQ(list->itemsize, sizeof(void *)); + EXPECT_NE(list->cl, nullptr); + EXPECT_NE(list->climpl, nullptr); + EXPECT_TRUE(cxListIsStoringPointers(list)); + cxListStoreObjects(list); + EXPECT_NE(list->cl, nullptr); + EXPECT_EQ(list->climpl, nullptr); + EXPECT_FALSE(cxListIsStoringPointers(list)); +} + +TEST_F(LinkedList, cxLinkedListCreate) { + CxList *list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int))); + ASSERT_NE(list, nullptr); + EXPECT_EQ(list->itemsize, sizeof(int)); + EXPECT_EQ(list->capacity, (size_t) -1); + verifyCreate(list); +} + +TEST_F(ArrayList, cxArrayListCreate) { + CxList *list = autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 8)); + ASSERT_NE(list, nullptr); + EXPECT_EQ(list->itemsize, sizeof(int)); + EXPECT_EQ(list->capacity, 8); + verifyCreate(list); +} + +TEST_F(LinkedList, cxListAdd) { + auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int))); + verifyAdd(list, false); +} + +TEST_F(PointerLinkedList, cxListAdd) { + auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int *))); + cxListStorePointers(list); + verifyAdd(list, true); +} + +TEST_F(ArrayList, cxListAdd) { + auto list = autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 8)); + verifyAdd(list, false); +} + +TEST_F(LinkedList, cxListInsert) { + verifyInsert(autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int)))); +} + +TEST_F(PointerLinkedList, cxListInsert) { + auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int *))); + cxListStorePointers(list); + verifyInsert(list); +} + +TEST_F(ArrayList, cxListInsert) { + verifyInsert(autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 2))); +} + +TEST_F(LinkedList, cxListInsertArray) { + verifyInsertArray(autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int)))); +} + +TEST_F(PointerLinkedList, cxListInsertArray) { + auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int *))); + cxListStorePointers(list); + verifyInsertArray(list, true); +} + +TEST_F(ArrayList, cxListInsertArray) { + verifyInsertArray(autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 4))); +} + +TEST_F(LinkedList, cxListRemove) { + verifyRemove(linkedListFromTestData()); +} + +TEST_F(PointerLinkedList, cxListRemove) { + verifyRemove(pointerLinkedListFromTestData()); +} + +TEST_F(ArrayList, cxListRemove) { + verifyRemove(arrayListFromTestData()); +} + +TEST_F(LinkedList, cxListAt) { + verifyAt(linkedListFromTestData()); +} + +TEST_F(PointerLinkedList, cxListAt) { + verifyAt(pointerLinkedListFromTestData()); +} + +TEST_F(ArrayList, cxListAt) { + verifyAt(arrayListFromTestData()); +} + +TEST_F(LinkedList, cxListFind) { + verifyFind(linkedListFromTestData()); +} + +TEST_F(PointerLinkedList, cxListFind) { + verifyFind(pointerLinkedListFromTestData()); +} + +TEST_F(ArrayList, cxListFind) { + verifyFind(arrayListFromTestData()); +} + +TEST_F(LinkedList, cxListSort) { + verifySort(linkedListFromTestData()); +} + +TEST_F(PointerLinkedList, cxListSort) { + verifySort(pointerLinkedListFromTestData()); +} + +TEST_F(ArrayList, cxListSort) { + verifySort(arrayListFromTestData()); +} + +TEST_F(LinkedList, Iterator) { + verifyIterator(linkedListFromTestData()); +} + +TEST_F(PointerLinkedList, Iterator) { + verifyIterator(pointerLinkedListFromTestData()); +} + +TEST_F(ArrayList, Iterator) { + verifyIterator(arrayListFromTestData()); +} + +TEST_F(LinkedList, InsertViaIterator) { + int fivenums[] = {0, 1, 2, 3, 4, 5}; + CxList *list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int))); + cxListAddArray(list, fivenums, 5); + verifyInsertViaIterator(list); +} + +TEST_F(PointerLinkedList, InsertViaIterator) { + int fivenums[] = {0, 1, 2, 3, 4, 5}; + auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int *))); + cxListStorePointers(list); + // note: cannot use cxListAddArray() because we don't have a list of pointers + cx_for_n(i, 5) cxListAdd(list, &fivenums[i]); + verifyInsertViaIterator(list); +} + +TEST_F(ArrayList, InsertViaIterator) { + int fivenums[] = {0, 1, 2, 3, 4, 5}; + CxList *list = autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 4)); + cxListAddArray(list, fivenums, 5); + verifyInsertViaIterator(list); +} + +TEST_F(LinkedList, cxListReverse) { + verifyReverse(linkedListFromTestData()); +} + +TEST_F(PointerLinkedList, cxListReverse) { + verifyReverse(pointerLinkedListFromTestData()); +} + +TEST_F(ArrayList, cxListReverse) { + verifyReverse(arrayListFromTestData()); +} + +TEST_F(LinkedList, cxListCompare) { + auto left = linkedListFromTestData(); + auto right = linkedListFromTestData(); + verifyCompare(left, right); +} + +TEST_F(LinkedList, cxListCompareWithPtrList) { + auto left = linkedListFromTestData(); + auto right = pointerLinkedListFromTestData(); + verifyCompare(left, right); +} + +TEST_F(LinkedList, cxListCompareWithArrayList) { + auto left = linkedListFromTestData(); + auto right = arrayListFromTestData(); + 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, cxListCompareWithArrayList) { + auto left = pointerLinkedListFromTestData(); + auto right = arrayListFromTestData(); + verifyCompare(left, right); +} + +TEST_F(ArrayList, cxListCompare) { + auto left = arrayListFromTestData(); + auto right = arrayListFromTestData(); + verifyCompare(left, right); +} + +TEST_F(ArrayList, cxListCompareWithPtrList) { + auto left = arrayListFromTestData(); + auto right = pointerLinkedListFromTestData(); + verifyCompare(left, right); +} + +TEST_F(ArrayList, cxListCompareWithNormalList) { + auto left = arrayListFromTestData(); + auto right = linkedListFromTestData(); + verifyCompare(left, right); +} + +TEST_F(PointerLinkedList, NoDestructor) { + void *item = cxMalloc(&testingAllocator, sizeof(int)); + auto list = cxLinkedListCreate(cxDefaultAllocator, cx_cmp_int, sizeof(int *)); + cxListStorePointers(list); + cxListAdd(list, item); + ASSERT_FALSE(testingAllocator.verify()); + cxListDestroy(list); + EXPECT_FALSE(testingAllocator.verify()); + cxFree(&testingAllocator, item); + EXPECT_TRUE(testingAllocator.verify()); +} + +TEST_F(PointerLinkedList, SimpleDestructor) { + int item = 0; + auto list = cxLinkedListCreate(cxDefaultAllocator, cx_cmp_int, sizeof(int *)); + cxListStorePointers(list); + list->content_destructor_type = CX_DESTRUCTOR_SIMPLE; + list->simple_destructor = [](void *elem) { *(int *) elem = 42; }; + cxListAdd(list, &item); + cxListDestroy(list); + EXPECT_EQ(item, 42); +} + +TEST_F(PointerLinkedList, AdvancedDestructor) { + void *item = cxMalloc(&testingAllocator, sizeof(int)); + auto list = cxLinkedListCreate(cxDefaultAllocator, cx_cmp_int, sizeof(int *)); + cxListStorePointers(list); + list->content_destructor_type = CX_DESTRUCTOR_ADVANCED; + list->advanced_destructor.data = &testingAllocator; + list->advanced_destructor.func = (cx_destructor_func2) cxFree; + cxListAdd(list, item); + ASSERT_FALSE(testingAllocator.verify()); + cxListDestroy(list); + EXPECT_TRUE(testingAllocator.verify()); +}