universe@390: /* universe@390: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. universe@390: * universe@390: * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved. universe@390: * universe@390: * Redistribution and use in source and binary forms, with or without universe@390: * modification, are permitted provided that the following conditions are met: universe@390: * universe@390: * 1. Redistributions of source code must retain the above copyright universe@390: * notice, this list of conditions and the following disclaimer. universe@390: * universe@390: * 2. Redistributions in binary form must reproduce the above copyright universe@390: * notice, this list of conditions and the following disclaimer in the universe@390: * documentation and/or other materials provided with the distribution. universe@390: * universe@390: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" universe@390: * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE universe@390: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE universe@390: * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE universe@390: * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR universe@390: * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF universe@390: * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS universe@390: * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN universe@390: * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) universe@390: * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE universe@390: * POSSIBILITY OF SUCH DAMAGE. universe@390: */ universe@390: universe@398: #include "cx/linked_list.h" universe@606: #include "cx/array_list.h" universe@509: #include "cx/utils.h" universe@602: #include "cx/compare.h" universe@422: #include "util_allocator.h" universe@398: universe@517: #include universe@517: #include universe@517: #include universe@517: #include universe@517: #include universe@517: universe@486: struct node { universe@517: node *next = nullptr; universe@517: node *prev = nullptr; universe@517: int data = 0; universe@486: }; universe@486: universe@486: const ptrdiff_t loc_prev = offsetof(struct node, prev); universe@486: const ptrdiff_t loc_next = offsetof(struct node, next); universe@486: const ptrdiff_t loc_data = offsetof(struct node, data); universe@486: universe@517: struct node_test_data { universe@520: node *begin = nullptr; universe@517: universe@520: explicit node_test_data(node *begin) : begin(begin) { universe@520: auto n = begin; universe@520: while (n != nullptr) { universe@520: nodes.push_back(n); universe@520: n = n->next; universe@520: } universe@520: } universe@520: universe@520: node_test_data(node_test_data &) = delete; universe@520: universe@520: node_test_data(node_test_data &&) = default; universe@517: universe@517: ~node_test_data() { universe@520: for (auto &&n: nodes) delete n; universe@486: } universe@520: universe@520: private: universe@520: std::vector nodes; universe@517: }; universe@517: universe@517: static node_test_data create_nodes_test_data(size_t len) { universe@517: if (len == 0) return node_test_data{nullptr}; universe@517: auto begin = new node; universe@517: auto prev = begin; universe@517: for (size_t i = 1; i < len; i++) { universe@517: auto n = new node; universe@517: cx_linked_list_link(prev, n, loc_prev, loc_next); universe@517: prev = n; universe@517: } universe@517: return node_test_data{begin}; universe@486: } universe@486: universe@517: template universe@528: static node_test_data create_nodes_test_data( universe@528: InputIter begin, universe@528: InputIter end universe@528: ) { universe@517: if (begin == end) return node_test_data{nullptr}; universe@517: node *first = new node; universe@517: first->data = *begin; universe@517: node *prev = first; universe@517: begin++; universe@517: for (; begin != end; begin++) { universe@517: auto n = new node; universe@517: n->data = *begin; universe@517: cx_linked_list_link(prev, n, loc_prev, loc_next); universe@517: prev = n; universe@486: } universe@517: return node_test_data{first}; universe@486: } universe@486: universe@517: static node_test_data create_nodes_test_data(std::initializer_list data) { universe@517: return create_nodes_test_data(data.begin(), data.end()); universe@509: } universe@509: universe@517: template universe@517: struct int_test_data { universe@517: std::array data; universe@482: universe@517: int_test_data() { universe@517: cx_for_n (i, N) data[i] = ::rand(); // NOLINT(cert-msc50-cpp) universe@517: } universe@517: }; universe@517: universe@517: TEST(LinkedList_LowLevel, link_unlink) { universe@517: node a, b, c; universe@482: universe@482: cx_linked_list_link(&a, &b, loc_prev, loc_next); universe@517: EXPECT_EQ(a.prev, nullptr); universe@517: EXPECT_EQ(a.next, &b); universe@517: EXPECT_EQ(b.prev, &a); universe@517: EXPECT_EQ(b.next, nullptr); universe@482: universe@482: cx_linked_list_unlink(&a, &b, loc_prev, loc_next); universe@517: EXPECT_EQ(a.prev, nullptr); universe@517: EXPECT_EQ(a.next, nullptr); universe@517: EXPECT_EQ(b.prev, nullptr); universe@517: EXPECT_EQ(b.next, nullptr); universe@482: universe@482: cx_linked_list_link(&b, &c, loc_prev, loc_next); universe@482: cx_linked_list_link(&a, &b, loc_prev, loc_next); universe@482: cx_linked_list_unlink(&b, &c, loc_prev, loc_next); universe@517: EXPECT_EQ(a.prev, nullptr); universe@517: EXPECT_EQ(a.next, &b); universe@517: EXPECT_EQ(b.prev, &a); universe@517: EXPECT_EQ(b.next, nullptr); universe@517: EXPECT_EQ(c.prev, nullptr); universe@517: EXPECT_EQ(c.next, nullptr); universe@482: } universe@482: universe@517: TEST(LinkedList_LowLevel, cx_linked_list_at) { universe@517: node a, b, c, d; universe@486: cx_linked_list_link(&a, &b, loc_prev, loc_next); universe@486: cx_linked_list_link(&b, &c, loc_prev, loc_next); universe@486: cx_linked_list_link(&c, &d, loc_prev, loc_next); universe@438: universe@517: EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 0), &a); universe@517: EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 1), &b); universe@517: EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 2), &c); universe@517: EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 3), &d); universe@517: EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 4), nullptr); universe@438: universe@517: EXPECT_EQ(cx_linked_list_at(&b, 1, loc_prev, 0), &a); universe@517: EXPECT_EQ(cx_linked_list_at(&b, 1, loc_next, 1), &b); universe@517: EXPECT_EQ(cx_linked_list_at(&b, 1, loc_next, 2), &c); universe@517: EXPECT_EQ(cx_linked_list_at(&b, 1, loc_next, 3), &d); universe@517: EXPECT_EQ(cx_linked_list_at(&b, 1, loc_next, 4), nullptr); universe@438: universe@517: EXPECT_EQ(cx_linked_list_at(&d, 3, loc_prev, 0), &a); universe@517: EXPECT_EQ(cx_linked_list_at(&d, 3, loc_prev, 1), &b); universe@438: } universe@438: universe@517: TEST(LinkedList_LowLevel, cx_linked_list_find) { universe@517: auto testdata = create_nodes_test_data({2, 4, 6, 8}); universe@517: auto list = testdata.begin; universe@487: int s; universe@487: universe@487: s = 2; universe@602: EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, false, cx_cmp_int, &s), 0); universe@487: s = 4; universe@602: EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, false, cx_cmp_int, &s), 1); universe@487: s = 6; universe@602: EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, false, cx_cmp_int, &s), 2); universe@487: s = 8; universe@602: EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, false, cx_cmp_int, &s), 3); universe@487: s = 10; universe@602: EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, false, cx_cmp_int, &s), 4); universe@487: s = -2; universe@602: EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, false, cx_cmp_int, &s), 4); universe@487: } universe@487: universe@517: TEST(LinkedList_LowLevel, cx_linked_list_compare) { universe@517: auto ta = create_nodes_test_data({2, 4, 6, 8}); universe@517: auto tb = create_nodes_test_data({2, 4, 6}); universe@517: auto tc = create_nodes_test_data({2, 4, 6, 9}); universe@517: auto la = ta.begin, lb = tb.begin, lc = tc.begin; universe@486: universe@602: EXPECT_GT(cx_linked_list_compare(la, lb, loc_next, loc_data, false, false, cx_cmp_int), 0); universe@602: EXPECT_LT(cx_linked_list_compare(lb, la, loc_next, loc_data, false, false, cx_cmp_int), 0); universe@602: EXPECT_GT(cx_linked_list_compare(lc, la, loc_next, loc_data, false, false, cx_cmp_int), 0); universe@602: EXPECT_LT(cx_linked_list_compare(la, lc, loc_next, loc_data, false, false, cx_cmp_int), 0); universe@602: EXPECT_EQ(cx_linked_list_compare(la, la, loc_next, loc_data, false, false, cx_cmp_int), 0); universe@486: } universe@486: universe@517: TEST(LinkedList_LowLevel, cx_linked_list_add) { universe@517: // test with begin, end / prev, next universe@517: { universe@517: node nodes[4]; universe@517: void *begin = nullptr, *end = nullptr; universe@449: universe@517: cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[0]); universe@517: EXPECT_EQ(begin, &nodes[0]); universe@517: EXPECT_EQ(end, &nodes[0]); universe@517: EXPECT_EQ(nodes[0].prev, nullptr); universe@517: EXPECT_EQ(nodes[0].next, nullptr); universe@449: universe@517: cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[1]); universe@517: EXPECT_EQ(begin, &nodes[0]); universe@517: EXPECT_EQ(end, &nodes[1]); universe@517: EXPECT_EQ(nodes[0].next, &nodes[1]); universe@517: EXPECT_EQ(nodes[1].prev, &nodes[0]); universe@517: } universe@449: olaf@442: // test with begin only / prev, next universe@517: { universe@517: node nodes[4]; universe@517: void *begin = nullptr; universe@449: universe@517: cx_linked_list_add(&begin, nullptr, loc_prev, loc_next, &nodes[0]); universe@517: EXPECT_EQ(begin, &nodes[0]); universe@517: cx_linked_list_add(&begin, nullptr, loc_prev, loc_next, &nodes[1]); universe@517: EXPECT_EQ(begin, &nodes[0]); universe@517: EXPECT_EQ(nodes[0].next, &nodes[1]); universe@517: EXPECT_EQ(nodes[1].prev, &nodes[0]); universe@449: universe@517: cx_linked_list_add(&begin, nullptr, loc_prev, loc_next, &nodes[2]); universe@517: EXPECT_EQ(nodes[1].next, &nodes[2]); universe@517: EXPECT_EQ(nodes[2].prev, &nodes[1]); universe@517: } universe@449: universe@475: // test with end only / prev, next universe@517: { universe@517: node nodes[4]; universe@517: void *end = nullptr; universe@475: universe@517: cx_linked_list_add(nullptr, &end, loc_prev, loc_next, &nodes[0]); universe@517: EXPECT_EQ(end, &nodes[0]); universe@517: cx_linked_list_add(nullptr, &end, loc_prev, loc_next, &nodes[1]); universe@517: EXPECT_EQ(end, &nodes[1]); universe@517: EXPECT_EQ(nodes[0].next, &nodes[1]); universe@517: EXPECT_EQ(nodes[1].prev, &nodes[0]); universe@475: universe@517: cx_linked_list_add(nullptr, &end, loc_prev, loc_next, &nodes[2]); universe@517: EXPECT_EQ(end, &nodes[2]); universe@517: EXPECT_EQ(nodes[1].next, &nodes[2]); universe@517: EXPECT_EQ(nodes[2].prev, &nodes[1]); universe@517: } universe@475: olaf@442: // test with begin, end / next universe@517: { universe@517: node nodes[4]; universe@517: void *begin = nullptr, *end = nullptr; universe@449: universe@517: cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[0]); universe@517: EXPECT_EQ(begin, &nodes[0]); universe@517: EXPECT_EQ(end, &nodes[0]); universe@517: cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[1]); universe@517: EXPECT_EQ(end, &nodes[1]); universe@517: EXPECT_EQ(nodes[0].next, &nodes[1]); universe@517: EXPECT_EQ(nodes[1].prev, nullptr); universe@517: } olaf@442: } olaf@442: universe@517: TEST(LinkedList_LowLevel, cx_linked_list_prepend) { universe@517: // test with begin, end / prev, next universe@517: { universe@517: node nodes[4]; universe@517: void *begin = nullptr, *end = nullptr; universe@475: universe@517: cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[0]); universe@517: EXPECT_EQ(begin, &nodes[0]); universe@517: EXPECT_EQ(end, &nodes[0]); universe@517: EXPECT_EQ(nodes[0].prev, nullptr); universe@517: EXPECT_EQ(nodes[0].next, nullptr); universe@475: universe@517: cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[1]); universe@517: EXPECT_EQ(begin, &nodes[1]); universe@517: EXPECT_EQ(end, &nodes[0]); universe@517: EXPECT_EQ(nodes[1].next, &nodes[0]); universe@517: EXPECT_EQ(nodes[0].prev, &nodes[1]); universe@517: } universe@475: universe@475: // test with begin only / prev, next universe@517: { universe@517: node nodes[4]; universe@517: void *begin = nullptr; universe@475: universe@517: cx_linked_list_prepend(&begin, nullptr, loc_prev, loc_next, &nodes[0]); universe@517: EXPECT_EQ(begin, &nodes[0]); universe@517: cx_linked_list_prepend(&begin, nullptr, loc_prev, loc_next, &nodes[1]); universe@517: EXPECT_EQ(begin, &nodes[1]); universe@517: EXPECT_EQ(nodes[1].next, &nodes[0]); universe@517: EXPECT_EQ(nodes[0].prev, &nodes[1]); universe@475: universe@517: cx_linked_list_prepend(&begin, nullptr, loc_prev, loc_next, &nodes[2]); universe@517: EXPECT_EQ(begin, &nodes[2]); universe@517: EXPECT_EQ(nodes[2].next, &nodes[1]); universe@517: EXPECT_EQ(nodes[1].prev, &nodes[2]); universe@517: } universe@475: universe@475: // test with end only / prev, next universe@517: { universe@517: node nodes[4]; universe@517: void *end = nullptr; universe@475: universe@517: cx_linked_list_prepend(nullptr, &end, loc_prev, loc_next, &nodes[0]); universe@517: EXPECT_EQ(end, &nodes[0]); universe@517: cx_linked_list_prepend(nullptr, &end, loc_prev, loc_next, &nodes[1]); universe@517: EXPECT_EQ(end, &nodes[0]); universe@517: EXPECT_EQ(nodes[1].next, &nodes[0]); universe@517: EXPECT_EQ(nodes[0].prev, &nodes[1]); universe@475: universe@517: cx_linked_list_prepend(nullptr, &end, loc_prev, loc_next, &nodes[2]); universe@517: EXPECT_EQ(end, &nodes[0]); universe@517: EXPECT_EQ(nodes[2].next, &nodes[1]); universe@517: EXPECT_EQ(nodes[1].prev, &nodes[2]); universe@517: } universe@475: universe@475: // test with begin, end / next universe@517: { universe@517: node nodes[4]; universe@517: void *begin = nullptr, *end = nullptr; universe@475: universe@517: cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[0]); universe@517: EXPECT_EQ(begin, &nodes[0]); universe@517: EXPECT_EQ(end, &nodes[0]); universe@517: cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[1]); universe@517: cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[2]); universe@517: EXPECT_EQ(begin, &nodes[2]); universe@517: EXPECT_EQ(end, &nodes[0]); universe@517: EXPECT_EQ(nodes[1].next, &nodes[0]); universe@517: EXPECT_EQ(nodes[2].next, &nodes[1]); universe@517: EXPECT_EQ(nodes[1].prev, nullptr); universe@517: EXPECT_EQ(nodes[0].prev, nullptr); universe@517: } universe@475: } universe@475: universe@517: TEST(LinkedList_LowLevel, cx_linked_list_insert) { universe@517: // insert mid list universe@517: { universe@517: node nodes[4]; universe@517: void *begin = &nodes[0], *end = &nodes[2]; universe@482: universe@517: cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); universe@517: cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); universe@482: universe@517: cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3]); universe@517: EXPECT_EQ(begin, &nodes[0]); universe@517: EXPECT_EQ(end, &nodes[2]); universe@517: EXPECT_EQ(nodes[1].next, &nodes[3]); universe@517: EXPECT_EQ(nodes[2].prev, &nodes[3]); universe@517: EXPECT_EQ(nodes[3].prev, &nodes[1]); universe@517: EXPECT_EQ(nodes[3].next, &nodes[2]); universe@517: } universe@482: universe@482: // insert end universe@517: { universe@517: node nodes[4]; universe@517: void *begin = &nodes[0], *end = &nodes[2]; universe@482: universe@517: cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); universe@517: cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); universe@482: universe@517: cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3]); universe@517: EXPECT_EQ(begin, &nodes[0]); universe@517: EXPECT_EQ(end, &nodes[3]); universe@517: EXPECT_EQ(nodes[2].next, &nodes[3]); universe@517: EXPECT_EQ(nodes[3].prev, &nodes[2]); universe@517: EXPECT_EQ(nodes[3].next, nullptr); universe@517: } universe@482: universe@482: // insert begin universe@517: { universe@517: node nodes[4]; universe@517: void *begin = &nodes[0], *end = &nodes[2]; universe@482: universe@517: cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); universe@517: cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); universe@482: universe@517: cx_linked_list_insert(&begin, &end, loc_prev, loc_next, nullptr, &nodes[3]); universe@517: EXPECT_EQ(begin, &nodes[3]); universe@517: EXPECT_EQ(end, &nodes[2]); universe@517: EXPECT_EQ(nodes[0].prev, &nodes[3]); universe@517: EXPECT_EQ(nodes[3].prev, nullptr); universe@517: EXPECT_EQ(nodes[3].next, &nodes[0]); universe@517: } universe@482: } universe@482: universe@517: TEST(LinkedList_LowLevel, cx_linked_list_insert_chain) { universe@517: // insert mid list universe@517: { universe@517: node nodes[5]; universe@517: void *begin = &nodes[0], *end = &nodes[2]; universe@482: universe@517: cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); universe@517: cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); universe@517: cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next); universe@482: universe@517: cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3], nullptr); universe@517: EXPECT_EQ(begin, &nodes[0]); universe@517: EXPECT_EQ(end, &nodes[2]); universe@517: EXPECT_EQ(nodes[1].next, &nodes[3]); universe@517: EXPECT_EQ(nodes[2].prev, &nodes[4]); universe@517: EXPECT_EQ(nodes[3].prev, &nodes[1]); universe@517: EXPECT_EQ(nodes[4].next, &nodes[2]); universe@517: } universe@482: universe@482: // insert end universe@517: { universe@517: node nodes[5]; universe@517: void *begin = &nodes[0], *end = &nodes[2]; universe@482: universe@517: cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); universe@517: cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); universe@517: cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next); universe@482: universe@517: cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3], nullptr); universe@517: EXPECT_EQ(begin, &nodes[0]); universe@517: EXPECT_EQ(end, &nodes[4]); universe@517: EXPECT_EQ(nodes[2].next, &nodes[3]); universe@517: EXPECT_EQ(nodes[3].prev, &nodes[2]); universe@517: EXPECT_EQ(nodes[4].next, nullptr); universe@517: } universe@482: universe@482: // insert begin universe@517: { universe@517: node nodes[5]; universe@517: void *begin = &nodes[0], *end = &nodes[2]; universe@482: universe@517: cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); universe@517: cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); universe@517: cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next); universe@482: universe@517: cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, nullptr, &nodes[3], nullptr); universe@517: EXPECT_EQ(begin, &nodes[3]); universe@517: EXPECT_EQ(end, &nodes[2]); universe@517: EXPECT_EQ(nodes[0].prev, &nodes[4]); universe@517: EXPECT_EQ(nodes[3].prev, nullptr); universe@517: EXPECT_EQ(nodes[4].next, &nodes[0]); universe@517: } universe@482: } universe@482: universe@517: TEST(LinkedList_LowLevel, cx_linked_list_first) { universe@517: auto testdata = create_nodes_test_data(3); universe@517: auto begin = testdata.begin; universe@517: EXPECT_EQ(cx_linked_list_first(begin, loc_prev), begin); universe@517: EXPECT_EQ(cx_linked_list_first(begin->next, loc_prev), begin); universe@517: EXPECT_EQ(cx_linked_list_first(begin->next->next, loc_prev), begin); universe@475: } universe@475: universe@517: TEST(LinkedList_LowLevel, cx_linked_list_last) { universe@517: auto testdata = create_nodes_test_data(3); universe@517: auto begin = testdata.begin; universe@517: auto end = begin->next->next; universe@517: EXPECT_EQ(cx_linked_list_last(begin, loc_next), end); universe@517: EXPECT_EQ(cx_linked_list_last(begin->next, loc_next), end); universe@517: EXPECT_EQ(cx_linked_list_last(begin->next->next, loc_next), end); universe@456: } universe@456: universe@517: TEST(LinkedList_LowLevel, cx_linked_list_prev) { universe@517: auto testdata = create_nodes_test_data(3); universe@517: auto begin = testdata.begin; universe@517: EXPECT_EQ(cx_linked_list_prev(begin, loc_next, begin), nullptr); universe@517: EXPECT_EQ(cx_linked_list_prev(begin, loc_next, begin->next), begin); universe@517: EXPECT_EQ(cx_linked_list_prev(begin, loc_next, begin->next->next), begin->next); universe@473: } universe@473: universe@517: TEST(LinkedList_LowLevel, cx_linked_list_remove) { universe@517: auto testdata = create_nodes_test_data({2, 4, 6}); universe@517: auto begin = reinterpret_cast(testdata.begin); universe@517: auto first = testdata.begin; universe@517: auto second = first->next; universe@517: auto third = second->next; universe@517: auto end = reinterpret_cast(third); universe@473: universe@486: cx_linked_list_remove(&begin, &end, loc_prev, loc_next, second); universe@517: EXPECT_EQ(begin, first); universe@517: EXPECT_EQ(end, third); universe@517: EXPECT_EQ(first->prev, nullptr); universe@517: EXPECT_EQ(first->next, third); universe@517: EXPECT_EQ(third->prev, first); universe@517: EXPECT_EQ(third->next, nullptr); universe@473: universe@486: cx_linked_list_remove(&begin, &end, loc_prev, loc_next, third); universe@517: EXPECT_EQ(begin, first); universe@517: EXPECT_EQ(end, first); universe@517: EXPECT_EQ(first->prev, nullptr); universe@517: EXPECT_EQ(first->next, nullptr); universe@473: universe@486: cx_linked_list_remove(&begin, &end, loc_prev, loc_next, first); universe@517: EXPECT_EQ(begin, nullptr); universe@517: EXPECT_EQ(end, nullptr); universe@473: } universe@473: universe@517: TEST(LinkedList_LowLevel, cx_linked_list_size) { universe@517: EXPECT_EQ(cx_linked_list_size(nullptr, loc_next), 0); universe@468: universe@517: { universe@517: auto testdata = create_nodes_test_data(5); universe@517: EXPECT_EQ(cx_linked_list_size(testdata.begin, loc_next), 5); universe@517: } universe@468: universe@517: { universe@517: auto testdata = create_nodes_test_data(13); universe@517: EXPECT_EQ(cx_linked_list_size(testdata.begin, loc_next), 13); universe@517: } universe@468: } universe@468: universe@517: TEST(LinkedList_LowLevel, cx_linked_list_sort) { universe@521: int_test_data<1500> testdata; universe@521: std::array sorted{}; universe@517: std::partial_sort_copy(testdata.data.begin(), testdata.data.end(), sorted.begin(), sorted.end()); universe@468: universe@517: auto scrambled = create_nodes_test_data(testdata.data.begin(), testdata.data.end()); universe@517: void *begin = scrambled.begin; universe@486: void *end = cx_linked_list_last(begin, loc_next); universe@468: universe@486: cx_linked_list_sort(&begin, &end, loc_prev, loc_next, loc_data, universe@602: false, cx_cmp_int); universe@468: universe@517: node *check = reinterpret_cast(begin); universe@517: node *check_last = nullptr; universe@517: cx_for_n (i, sorted.size()) { universe@517: EXPECT_EQ(check->data, sorted[i]); universe@517: EXPECT_EQ(check->prev, check_last); universe@517: if (i < sorted.size() - 1) { universe@517: ASSERT_NE(check->next, nullptr); universe@468: } universe@468: check_last = check; universe@468: check = check->next; universe@468: } universe@517: EXPECT_EQ(check, nullptr); universe@517: EXPECT_EQ(end, check_last); universe@468: } universe@468: universe@517: TEST(LinkedList_LowLevel, cx_linked_list_reverse) { universe@517: auto testdata = create_nodes_test_data({2, 4, 6, 8}); universe@517: auto expected = create_nodes_test_data({8, 6, 4, 2}); universe@473: universe@517: auto begin = reinterpret_cast(testdata.begin); universe@517: auto end = cx_linked_list_last(begin, loc_next); universe@517: auto orig_begin = begin, orig_end = end; universe@473: universe@486: cx_linked_list_reverse(&begin, &end, loc_prev, loc_next); universe@517: EXPECT_EQ(end, orig_begin); universe@517: EXPECT_EQ(begin, orig_end); universe@602: EXPECT_EQ(cx_linked_list_compare(begin, expected.begin, loc_next, loc_data, false, false, cx_cmp_int), 0); universe@473: } universe@456: universe@517: class HighLevelTest : public ::testing::Test { universe@517: mutable std::unordered_set lists; universe@517: protected: universe@518: CxTestingAllocator testingAllocator; universe@455: universe@517: void TearDown() override { universe@517: for (auto &&l: lists) cxListDestroy(l); universe@518: EXPECT_TRUE(testingAllocator.verify()); universe@517: } universe@517: universe@517: static constexpr size_t testdata_len = 250; universe@517: int_test_data testdata; universe@517: universe@517: auto autofree(CxList *list) const -> CxList * { universe@606: if (list != nullptr) lists.insert(list); universe@517: return list; universe@517: } universe@517: universe@517: auto linkedListFromTestData() const -> CxList * { universe@606: // TODO: replace with cxListAddArray universe@517: return autofree( universe@517: cxLinkedListFromArray( universe@518: &testingAllocator, universe@602: cx_cmp_int, universe@517: sizeof(int), universe@517: testdata_len, universe@517: testdata.data.data() universe@517: ) universe@517: ); universe@517: } universe@517: universe@517: auto pointerLinkedListFromTestData() const -> CxList * { universe@602: auto list = autofree(cxPointerLinkedListCreate(&testingAllocator, cx_cmp_int)); universe@517: cx_for_n(i, testdata_len) cxListAdd(list, &testdata.data[i]); universe@517: return list; universe@517: } universe@517: universe@606: auto arrayListFromTestData() const -> CxList * { universe@606: auto list = autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), testdata_len)); universe@606: // TODO: replace with cxListAddArray universe@606: cx_for_n(i, testdata_len) cxListAdd(list, &testdata.data[i]); universe@606: return list; universe@606: } universe@606: universe@518: void verifyCreate(CxList *list) const { universe@528: EXPECT_EQ(list->content_destructor_type, CX_DESTRUCTOR_NONE); universe@517: EXPECT_EQ(list->size, 0); universe@518: EXPECT_EQ(list->allocator, &testingAllocator); universe@602: EXPECT_EQ(list->cmpfunc, cx_cmp_int); universe@517: } universe@517: universe@528: void verifyAdd( universe@528: CxList *list, universe@606: bool as_pointer universe@528: ) { universe@517: auto len = testdata_len; universe@517: cx_for_n (i, len) EXPECT_EQ(cxListAdd(list, &testdata.data[i]), 0); universe@517: EXPECT_EQ(list->size, len); universe@517: EXPECT_GE(list->capacity, list->size); universe@517: cx_for_n (i, len) EXPECT_EQ(*(int *) cxListAt(list, i), testdata.data[i]); universe@517: cx_for_n (i, len) ++testdata.data[i]; universe@606: if (as_pointer) { universe@517: cx_for_n (i, len) EXPECT_EQ(*(int *) cxListAt(list, i), testdata.data[i]); universe@517: } else { universe@517: cx_for_n (i, len) EXPECT_EQ(*(int *) cxListAt(list, i), testdata.data[i] - 1); universe@517: } universe@517: } universe@517: universe@517: static void verifyInsert(CxList *list) { universe@517: int a = 5, b = 47, c = 13, d = 42; universe@517: universe@517: EXPECT_NE(cxListInsert(list, 1, &a), 0); universe@517: EXPECT_EQ(list->size, 0); universe@517: EXPECT_EQ(cxListInsert(list, 0, &a), 0); universe@517: EXPECT_EQ(list->size, 1); universe@517: EXPECT_EQ(cxListInsert(list, 0, &b), 0); universe@517: EXPECT_EQ(list->size, 2); universe@517: EXPECT_EQ(cxListInsert(list, 1, &c), 0); universe@517: EXPECT_EQ(list->size, 3); universe@517: EXPECT_EQ(cxListInsert(list, 3, &d), 0); universe@517: universe@611: ASSERT_EQ(list->size, 4); universe@517: EXPECT_GE(list->capacity, list->size); universe@517: universe@517: EXPECT_EQ(*(int *) cxListAt(list, 0), 47); universe@517: EXPECT_EQ(*(int *) cxListAt(list, 1), 13); universe@517: EXPECT_EQ(*(int *) cxListAt(list, 2), 5); universe@517: EXPECT_EQ(*(int *) cxListAt(list, 3), 42); universe@517: } universe@517: universe@517: void verifyRemove(CxList *list) const { universe@517: EXPECT_EQ(cxListRemove(list, 2), 0); universe@517: EXPECT_EQ(cxListRemove(list, 4), 0); universe@517: EXPECT_EQ(list->size, testdata_len - 2); universe@517: EXPECT_GE(list->capacity, list->size); universe@517: EXPECT_EQ(*(int *) cxListAt(list, 0), testdata.data[0]); universe@517: EXPECT_EQ(*(int *) cxListAt(list, 1), testdata.data[1]); universe@517: EXPECT_EQ(*(int *) cxListAt(list, 2), testdata.data[3]); universe@517: EXPECT_EQ(*(int *) cxListAt(list, 3), testdata.data[4]); universe@517: EXPECT_EQ(*(int *) cxListAt(list, 4), testdata.data[6]); universe@517: universe@517: EXPECT_EQ(cxListRemove(list, 0), 0); universe@517: EXPECT_EQ(list->size, testdata_len - 3); universe@517: EXPECT_GE(list->capacity, list->size); universe@517: EXPECT_EQ(*(int *) cxListAt(list, 0), testdata.data[1]); universe@517: EXPECT_EQ(*(int *) cxListAt(list, 1), testdata.data[3]); universe@517: universe@517: EXPECT_NE(cxListRemove(list, testdata_len), 0); universe@517: } universe@517: universe@517: void verifyAt(CxList *list) const { universe@517: auto len = testdata_len; universe@517: EXPECT_EQ(list->size, len); universe@521: cx_for_n (i, len) { universe@521: EXPECT_EQ(*(int *) cxListAt(list, i), testdata.data[i]); universe@521: } universe@517: EXPECT_EQ(cxListAt(list, list->size), nullptr); universe@517: } universe@517: universe@517: void verifyFind(CxList *list) const { universe@517: cx_for_n (attempt, 25) { universe@517: size_t exp = rand() % testdata_len; // NOLINT(cert-msc50-cpp) universe@517: int val = testdata.data[exp]; universe@517: // randomly picked number could occur earlier in list - find first position universe@517: cx_for_n (i, exp) { universe@517: if (testdata.data[i] == val) { universe@517: exp = i; universe@517: break; universe@517: } universe@517: } universe@517: EXPECT_EQ(cxListFind(list, &val), exp); universe@517: } universe@517: } universe@517: universe@517: void verifySort(CxList *list) const { universe@517: std::array expected{}; universe@517: std::partial_sort_copy(testdata.data.begin(), testdata.data.end(), expected.begin(), expected.end()); universe@517: cxListSort(list); universe@517: cx_for_n (i, testdata_len) ASSERT_EQ(*(int *) cxListAt(list, i), expected[i]); universe@517: } universe@517: universe@517: void verifyIterator(CxList *list) const { universe@517: int i = 0; universe@517: CxIterator iter = cxListBegin(list); universe@517: cx_foreach(int*, x, iter) { universe@517: ASSERT_EQ(iter.index, (size_t) (i + 1) / 2); universe@517: ASSERT_EQ(*x, testdata.data[i]); universe@517: if (i % 2 == 1) iter.remove = true; universe@517: i++; universe@517: } universe@517: auto len = testdata_len; universe@517: EXPECT_EQ(i, len); universe@517: ASSERT_EQ(list->size, len / 2); universe@517: cx_for_n(j, len / 2) ASSERT_EQ(*(int *) cxListAt(list, j), testdata.data[j * 2]); universe@517: } universe@517: universe@517: static void verifyInsertViaIterator(CxList *list) { universe@517: int newdata[] = {10, 20, 30, 40, 50}; universe@517: universe@517: CxIterator iter = cxListIterator(list, 2); universe@517: EXPECT_TRUE(cxIteratorValid(&iter)); universe@517: EXPECT_EQ(iter.index, 2); universe@517: EXPECT_EQ(*(int *) cxIteratorCurrent(&iter), 2); universe@517: cxListInsertAfter(&iter, &newdata[0]); universe@517: EXPECT_TRUE(cxIteratorValid(&iter)); universe@517: EXPECT_EQ(iter.index, 2); universe@517: EXPECT_EQ(*(int *) cxIteratorCurrent(&iter), 2); universe@517: cxListInsertBefore(&iter, &newdata[1]); universe@517: EXPECT_TRUE(cxIteratorValid(&iter)); universe@517: EXPECT_EQ(iter.index, 3); universe@517: EXPECT_EQ(*(int *) cxIteratorCurrent(&iter), 2); universe@517: universe@517: iter = cxListBegin(list); universe@517: cxListInsertBefore(&iter, &newdata[2]); universe@517: EXPECT_TRUE(cxIteratorValid(&iter)); universe@517: EXPECT_EQ(iter.index, 1); universe@517: EXPECT_EQ(*(int *) cxIteratorCurrent(&iter), 0); universe@517: iter = cxListIterator(list, list->size); universe@517: cxListInsertBefore(&iter, &newdata[3]); universe@517: EXPECT_FALSE(cxIteratorValid(&iter)); universe@517: EXPECT_EQ(iter.index, 9); universe@517: iter = cxListIterator(list, list->size); universe@517: cxListInsertAfter(&iter, &newdata[4]); universe@517: EXPECT_FALSE(cxIteratorValid(&iter)); universe@517: EXPECT_EQ(iter.index, 10); universe@517: universe@517: int expdata[] = {30, 0, 1, 20, 2, 10, 3, 4, 40, 50}; universe@517: cx_for_n (j, 10) EXPECT_EQ(*(int *) cxListAt(list, j), expdata[j]); universe@517: } universe@521: universe@521: void verifyReverse(CxList *list) const { universe@521: cxListReverse(list); universe@521: cx_for_n(i, testdata_len) { universe@521: ASSERT_EQ(*(int *) cxListAt(list, i), testdata.data[testdata_len - 1 - i]); universe@521: } universe@521: } universe@521: universe@528: static void verifyCompare( universe@528: CxList *left, universe@528: CxList *right universe@528: ) { universe@521: EXPECT_EQ(cxListCompare(left, right), 0); universe@521: int x = 42; universe@521: cxListAdd(left, &x); universe@521: ASSERT_GT(left->size, right->size); universe@521: EXPECT_GT(cxListCompare(left, right), 0); universe@521: EXPECT_LT(cxListCompare(right, left), 0); universe@521: cxListAdd(right, &x); universe@521: ASSERT_EQ(left->size, right->size); universe@521: EXPECT_EQ(cxListCompare(left, right), 0); universe@521: int a = 5, b = 10; universe@521: cxListInsert(left, 15, &a); universe@521: cxListInsert(right, 15, &b); universe@521: ASSERT_EQ(left->size, right->size); universe@521: EXPECT_LT(cxListCompare(left, right), 0); universe@521: EXPECT_GT(cxListCompare(right, left), 0); universe@528: *(int *) cxListAt(left, 15) = 10; universe@521: EXPECT_EQ(cxListCompare(left, right), 0); universe@521: } universe@517: }; universe@517: universe@517: class LinkedList : public HighLevelTest { universe@517: }; universe@517: universe@517: class PointerLinkedList : public HighLevelTest { universe@517: }; universe@517: universe@606: class ArrayList : public HighLevelTest { universe@606: }; universe@606: universe@517: TEST_F(LinkedList, cxLinkedListCreate) { universe@602: CxList *list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int))); universe@606: ASSERT_NE(list, nullptr); universe@517: EXPECT_EQ(list->itemsize, sizeof(int)); universe@606: EXPECT_EQ(list->capacity, (size_t) -1); universe@517: verifyCreate(list); universe@506: } universe@506: universe@517: TEST_F(PointerLinkedList, cxPointerLinkedListCreate) { universe@602: CxList *list = autofree(cxPointerLinkedListCreate(&testingAllocator, cx_cmp_int)); universe@606: ASSERT_NE(list, nullptr); universe@517: EXPECT_EQ(list->itemsize, sizeof(void *)); universe@606: EXPECT_EQ(list->capacity, (size_t) -1); universe@517: verifyCreate(list); universe@455: } universe@455: universe@517: TEST_F(LinkedList, cxLinkedListFromArray) { universe@602: CxList *expected = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int))); universe@517: cx_for_n (i, testdata_len) cxListAdd(expected, &testdata.data[i]); universe@602: CxList *list = autofree(cxLinkedListFromArray(&testingAllocator, cx_cmp_int, sizeof(int), universe@517: testdata_len, testdata.data.data())); universe@606: ASSERT_NE(list, nullptr); universe@606: EXPECT_EQ(list->itemsize, sizeof(int)); universe@606: EXPECT_EQ(list->capacity, (size_t) -1); universe@606: EXPECT_EQ(list->size, testdata_len); universe@517: EXPECT_EQ(cxListCompare(list, expected), 0); universe@498: } universe@498: universe@606: TEST_F(ArrayList, cxArrayListCreate) { universe@606: CxList *list = autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 8)); universe@606: ASSERT_NE(list, nullptr); universe@606: EXPECT_EQ(list->itemsize, sizeof(int)); universe@606: EXPECT_EQ(list->capacity, 8); universe@606: verifyCreate(list); universe@606: } universe@606: universe@517: TEST_F(LinkedList, cxListAdd) { universe@602: CxList *list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int))); universe@517: verifyAdd(list, false); universe@488: } universe@488: universe@517: TEST_F(PointerLinkedList, cxListAdd) { universe@602: CxList *list = autofree(cxPointerLinkedListCreate(&testingAllocator, cx_cmp_int)); universe@517: verifyAdd(list, true); universe@507: } universe@507: universe@606: TEST_F(ArrayList, cxListAdd) { universe@606: CxList *list = autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 8)); universe@606: verifyAdd(list, false); universe@606: } universe@606: universe@517: TEST_F(LinkedList, cxListInsert) { universe@602: verifyInsert(autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int)))); universe@459: } universe@459: universe@517: TEST_F(PointerLinkedList, cxListInsert) { universe@602: verifyInsert(autofree(cxPointerLinkedListCreate(&testingAllocator, cx_cmp_int))); universe@498: } universe@498: universe@606: TEST_F(ArrayList, cxListInsert) { universe@606: verifyInsert(autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 2))); universe@606: } universe@606: universe@517: TEST_F(LinkedList, cxListRemove) { universe@517: verifyRemove(linkedListFromTestData()); universe@498: } universe@498: universe@517: TEST_F(PointerLinkedList, cxListRemove) { universe@517: verifyRemove(pointerLinkedListFromTestData()); universe@509: } universe@459: universe@606: TEST_F(ArrayList, cxListRemove) { universe@606: verifyRemove(arrayListFromTestData()); universe@606: } universe@606: universe@517: TEST_F(LinkedList, cxListAt) { universe@517: verifyAt(linkedListFromTestData()); universe@509: } universe@509: universe@517: TEST_F(PointerLinkedList, cxListAt) { universe@517: verifyAt(pointerLinkedListFromTestData()); universe@459: } universe@459: universe@606: TEST_F(ArrayList, cxListAt) { universe@606: verifyAt(arrayListFromTestData()); universe@606: } universe@606: universe@517: TEST_F(LinkedList, cxListFind) { universe@517: verifyFind(linkedListFromTestData()); universe@509: } universe@509: universe@517: TEST_F(PointerLinkedList, cxListFind) { universe@517: verifyFind(pointerLinkedListFromTestData()); universe@509: } universe@498: universe@606: TEST_F(ArrayList, cxListFind) { universe@606: verifyFind(arrayListFromTestData()); universe@606: } universe@606: universe@517: TEST_F(LinkedList, cxListSort) { universe@517: verifySort(linkedListFromTestData()); universe@498: } universe@498: universe@517: TEST_F(PointerLinkedList, cxListSort) { universe@517: verifySort(pointerLinkedListFromTestData()); universe@479: } universe@479: universe@606: TEST_F(ArrayList, cxListSort) { universe@606: verifySort(arrayListFromTestData()); universe@606: } universe@606: universe@517: TEST_F(LinkedList, Iterator) { universe@517: verifyIterator(linkedListFromTestData()); universe@509: } universe@498: universe@517: TEST_F(PointerLinkedList, Iterator) { universe@517: verifyIterator(pointerLinkedListFromTestData()); universe@498: } universe@498: universe@606: TEST_F(ArrayList, Iterator) { universe@606: verifyIterator(arrayListFromTestData()); universe@606: } universe@606: universe@517: TEST_F(LinkedList, InsertViaIterator) { universe@517: int fivenums[] = {0, 1, 2, 3, 4, 5}; universe@602: CxList *list = autofree(cxLinkedListFromArray(&testingAllocator, cx_cmp_int, sizeof(int), 5, fivenums)); universe@517: verifyInsertViaIterator(list); universe@459: } universe@459: universe@517: TEST_F(PointerLinkedList, InsertViaIterator) { universe@517: int fivenums[] = {0, 1, 2, 3, 4, 5}; universe@602: CxList *list = autofree(cxPointerLinkedListCreate(&testingAllocator, cx_cmp_int)); universe@517: cx_for_n (i, 5) cxListAdd(list, &fivenums[i]); universe@517: verifyInsertViaIterator(list); universe@509: } universe@521: universe@606: TEST_F(ArrayList, InsertViaIterator) { universe@606: int fivenums[] = {0, 1, 2, 3, 4, 5}; universe@606: CxList *list = autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 4)); universe@606: // TODO: replace with cxListAddArray universe@606: cx_for_n (i, 5) cxListAdd(list, &fivenums[i]); universe@606: verifyInsertViaIterator(list); universe@606: } universe@606: universe@521: TEST_F(LinkedList, cxListReverse) { universe@521: verifyReverse(linkedListFromTestData()); universe@521: } universe@521: universe@521: TEST_F(PointerLinkedList, cxListReverse) { universe@521: verifyReverse(pointerLinkedListFromTestData()); universe@521: } universe@521: universe@606: TEST_F(ArrayList, cxListReverse) { universe@606: ASSERT_EQ(1,0); // TODO: remove when implemented universe@606: verifyReverse(arrayListFromTestData()); universe@606: } universe@606: universe@521: TEST_F(LinkedList, cxListCompare) { universe@521: auto left = linkedListFromTestData(); universe@521: auto right = linkedListFromTestData(); universe@521: verifyCompare(left, right); universe@521: } universe@521: universe@552: TEST_F(LinkedList, cxListCompareWithPtrList) { universe@552: auto left = linkedListFromTestData(); universe@552: auto right = pointerLinkedListFromTestData(); universe@552: verifyCompare(left, right); universe@552: } universe@552: universe@606: TEST_F(LinkedList, cxListCompareWithArrayList) { universe@606: auto left = linkedListFromTestData(); universe@606: auto right = arrayListFromTestData(); universe@606: verifyCompare(left, right); universe@606: } universe@606: universe@521: TEST_F(PointerLinkedList, cxListCompare) { universe@521: auto left = pointerLinkedListFromTestData(); universe@521: auto right = pointerLinkedListFromTestData(); universe@521: verifyCompare(left, right); universe@521: } universe@521: universe@552: TEST_F(PointerLinkedList, cxListCompareWithNormalList) { universe@552: auto left = pointerLinkedListFromTestData(); universe@552: auto right = linkedListFromTestData(); universe@552: verifyCompare(left, right); universe@552: } universe@552: universe@606: TEST_F(PointerLinkedList, cxListCompareWithArrayList) { universe@606: auto left = pointerLinkedListFromTestData(); universe@606: auto right = arrayListFromTestData(); universe@606: verifyCompare(left, right); universe@606: } universe@606: universe@606: TEST_F(ArrayList, cxListCompare) { universe@606: ASSERT_EQ(1,0); // TODO: remove when implemented universe@606: auto left = arrayListFromTestData(); universe@606: auto right = arrayListFromTestData(); universe@606: verifyCompare(left, right); universe@606: } universe@606: universe@606: TEST_F(ArrayList, cxListCompareWithPtrList) { universe@606: auto left = arrayListFromTestData(); universe@606: auto right = pointerLinkedListFromTestData(); universe@606: verifyCompare(left, right); universe@606: } universe@606: universe@606: TEST_F(ArrayList, cxListCompareWithNormalList) { universe@606: auto left = arrayListFromTestData(); universe@606: auto right = linkedListFromTestData(); universe@606: verifyCompare(left, right); universe@606: } universe@606: universe@528: TEST_F(PointerLinkedList, NoDestructor) { universe@528: void *item = cxMalloc(&testingAllocator, sizeof(int)); universe@602: auto list = cxPointerLinkedListCreate(cxDefaultAllocator, cx_cmp_int); universe@528: cxListAdd(list, item); universe@528: ASSERT_FALSE(testingAllocator.verify()); universe@528: cxListDestroy(list); universe@528: EXPECT_FALSE(testingAllocator.verify()); universe@528: cxFree(&testingAllocator, item); universe@528: EXPECT_TRUE(testingAllocator.verify()); universe@528: } universe@528: universe@528: TEST_F(PointerLinkedList, SimpleDestructor) { universe@528: int item = 0; universe@602: auto list = cxPointerLinkedListCreate(cxDefaultAllocator, cx_cmp_int); universe@528: list->content_destructor_type = CX_DESTRUCTOR_SIMPLE; universe@528: list->simple_destructor = [](void *elem) { *(int *) elem = 42; }; universe@528: cxListAdd(list, &item); universe@528: cxListDestroy(list); universe@528: EXPECT_EQ(item, 42); universe@528: } universe@528: universe@528: TEST_F(PointerLinkedList, AdvancedDestructor) { universe@528: void *item = cxMalloc(&testingAllocator, sizeof(int)); universe@602: auto list = cxPointerLinkedListCreate(cxDefaultAllocator, cx_cmp_int); universe@528: list->content_destructor_type = CX_DESTRUCTOR_ADVANCED; universe@528: list->advanced_destructor.data = &testingAllocator; universe@528: list->advanced_destructor.func = (cx_destructor_func2) cxFree; universe@528: cxListAdd(list, item); universe@528: ASSERT_FALSE(testingAllocator.verify()); universe@528: cxListDestroy(list); universe@528: EXPECT_TRUE(testingAllocator.verify()); universe@528: }