changeset
migrate list tests to gtest
Sat, 16 Apr 2022 18:02:10 +0200
- author
- Mike Becker <universe@uap-core.de>
- date
- Sat, 16 Apr 2022 18:02:10 +0200
- changeset 517
- b3baaf9b7e3c
- parent 516
- 7bcea73303ce
- child 518
- 74d0372f5c6f
migrate list tests to gtest
| test/CMakeLists.txt | file | annotate | diff | comparison | revisions | |
| test/test_config.h | file | annotate | diff | comparison | revisions | |
| test/test_list.c | file | annotate | diff | comparison | revisions | |
| test/test_list.cpp | file | annotate | diff | comparison | revisions |
--- a/test/CMakeLists.txt Sat Apr 16 17:28:36 2022 +0200 +++ b/test/CMakeLists.txt Sat Apr 16 18:02:10 2022 +0200 @@ -1,27 +1,3 @@ -# Transitional support for CTest written tests -message(CHECK_START "Searching for CUnit test framework") - -find_path(CUNIT_INCLUDE_DIR NAMES CUnit/CUnit.h) -find_library(CUNIT_LIBRARY NAMES cunit libcunit cunitlib) -include(FindPackageHandleStandardArgs) -find_package_handle_standard_args(CUnit DEFAULT_MSG CUNIT_LIBRARY CUNIT_INCLUDE_DIR) - -if (CUNIT_FOUND) - message(CHECK_PASS "found: compiling tests.") - set(TESTS - test_list - ) - - foreach (test ${TESTS}) - add_executable(${test} ${test}.c) - target_link_libraries(${test} PRIVATE ucx_static ${CUNIT_LIBRARY}) - target_include_directories(${test} PRIVATE ${CUNIT_INCLUDE_DIR}) - add_test(NAME ${test} COMMAND ${test} WORKING_DIRECTORY "${CMAKE_CURRENT_BINARY_DIR}") - endforeach () -else () - message(CHECK_FAIL "not found: CUnit tests will not be available.") -endif () - # Load Google Test Framework set(CMAKE_CXX_STANDARD 11) @@ -39,8 +15,10 @@ add_executable(ucxtest test_allocator.cpp + test_list.cpp test_tree.cpp selftest.cpp + util_allocator.c ) target_link_libraries(ucxtest PRIVATE ucx_static gtest_main) gtest_discover_tests(ucxtest)
--- a/test/test_config.h Sat Apr 16 17:28:36 2022 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,38 +0,0 @@ -/* - * 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. - */ - -#ifndef UCX_TEST_CONFIG_H -#define UCX_TEST_CONFIG_H - -#include <CUnit/Basic.h> - -#define UCX_CU_BRM CU_BRM_NORMAL - -#define cu_add_test(suite, name) CU_add_test(suite, #name, name) - -#endif /* UCX_TEST_CONFIG_H */
--- a/test/test_list.c Sat Apr 16 17:28:36 2022 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,976 +0,0 @@ -/* - * 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/utils.h" -#include "test_config.h" -#include "util_allocator.h" - -static int cmp_int_impl( - int const *l, - int const *r -) { - int left = *l, right = *r; - return left == right ? 0 : (left < right ? -1 : 1); -} - -#define cmp_int ((CxListComparator) cmp_int_impl) - -struct node { - struct node *next; - struct node *prev; - int data; -}; - -#define nd(name) name = {0} - -const ptrdiff_t loc_prev = offsetof(struct node, prev); -const ptrdiff_t loc_next = offsetof(struct node, next); -const ptrdiff_t loc_data = offsetof(struct node, data); - -static struct node *create_nodes_test_data( - size_t n, - int const data[] -) { - CU_ASSERT_NOT_EQUAL_FATAL(n, 0) - struct node *begin = calloc(1, sizeof(struct node)); - struct node *prev = begin; - if (data) begin->data = data[0]; - for (size_t i = 1; i < n; i++) { - struct node *node = calloc(1, sizeof(struct node)); - if (data) node->data = data[i]; - cx_linked_list_link(prev, node, loc_prev, loc_next); - prev = node; - } - return begin; -} - -static void destroy_nodes_test_data(struct node *begin) { - struct node *node = begin; - while (node) { - struct node *next = node->next; - free(node); - node = next; - } -} - -static int *create_ints_test_data(size_t len) { - int *data = malloc(sizeof(int) * len); - cx_for_n (i, len) data[i] = rand(); // NOLINT(cert-msc50-cpp) - return data; -} - -void test_linked_list_link_unlink(void) { - - struct node nd(a), nd(b), nd(c); - - cx_linked_list_link(&a, &b, loc_prev, loc_next); - CU_ASSERT_PTR_NULL(a.prev) - CU_ASSERT_PTR_EQUAL(a.next, &b) - CU_ASSERT_PTR_EQUAL(b.prev, &a) - CU_ASSERT_PTR_NULL(b.next) - - cx_linked_list_unlink(&a, &b, loc_prev, loc_next); - CU_ASSERT_PTR_NULL(a.prev) - CU_ASSERT_PTR_NULL(a.next) - CU_ASSERT_PTR_NULL(b.prev) - CU_ASSERT_PTR_NULL(b.next) - - 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); - CU_ASSERT_PTR_NULL(a.prev) - CU_ASSERT_PTR_EQUAL(a.next, &b) - CU_ASSERT_PTR_EQUAL(b.prev, &a) - CU_ASSERT_PTR_NULL(b.next) - CU_ASSERT_PTR_NULL(c.prev) - CU_ASSERT_PTR_NULL(c.next) -} - -void test_linked_list_at(void) { - struct node nd(a), nd(b), nd(c), nd(d); - cx_linked_list_link(&a, &b, loc_prev, loc_next); - cx_linked_list_link(&b, &c, loc_prev, loc_next); - cx_linked_list_link(&c, &d, loc_prev, loc_next); - - CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&a, 0, loc_next, 0), &a) - CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&a, 0, loc_next, 1), &b) - CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&a, 0, loc_next, 2), &c) - CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&a, 0, loc_next, 3), &d) - CU_ASSERT_PTR_NULL(cx_linked_list_at(&a, 0, loc_next, 4)) - - CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&b, 1, loc_prev, 0), &a) - CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&b, 1, loc_next, 1), &b) - CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&b, 1, loc_next, 2), &c) - CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&b, 1, loc_next, 3), &d) - CU_ASSERT_PTR_NULL(cx_linked_list_at(&b, 1, loc_next, 4)) - - CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&d, 3, loc_prev, 0), &a) - CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&d, 3, loc_prev, 1), &b) -} - -void test_linked_list_find(void) { - int data[] = {2, 4, 6, 8}; - void *list = create_nodes_test_data(4, data); - int s; - - s = 2; - CU_ASSERT_EQUAL(cx_linked_list_find(list, loc_next, loc_data, - false, cmp_int, &s), 0) - s = 4; - CU_ASSERT_EQUAL(cx_linked_list_find(list, loc_next, loc_data, - false, cmp_int, &s), 1) - s = 6; - CU_ASSERT_EQUAL(cx_linked_list_find(list, loc_next, loc_data, - false, cmp_int, &s), 2) - s = 8; - CU_ASSERT_EQUAL(cx_linked_list_find(list, loc_next, loc_data, - false, cmp_int, &s), 3) - s = 10; - CU_ASSERT_EQUAL(cx_linked_list_find(list, loc_next, loc_data, - false, cmp_int, &s), 4) - s = -2; - CU_ASSERT_EQUAL(cx_linked_list_find(list, loc_next, loc_data, - false, cmp_int, &s), 4) -} - -void test_linked_list_compare(void) { - int a[] = {2, 4, 6, 8}; - int b[] = {2, 4, 6}; - int c[] = {2, 4, 6, 9}; - - void *la = create_nodes_test_data(4, a); - void *lb = create_nodes_test_data(3, b); - void *lc = create_nodes_test_data(4, c); - - CU_ASSERT_TRUE(0 < cx_linked_list_compare(la, lb, loc_next, loc_data, - false, cmp_int) - ) - CU_ASSERT_TRUE(0 > cx_linked_list_compare(lb, la, loc_next, loc_data, - false, cmp_int) - ) - CU_ASSERT_TRUE(0 < cx_linked_list_compare(lc, la, loc_next, loc_data, - false, cmp_int) - ) - CU_ASSERT_TRUE(0 > cx_linked_list_compare(la, lc, loc_next, loc_data, - false, cmp_int) - ) - CU_ASSERT_TRUE(0 == cx_linked_list_compare(la, la, loc_next, loc_data, - false, cmp_int) - ) - - destroy_nodes_test_data(la); - destroy_nodes_test_data(lb); - destroy_nodes_test_data(lc); -} - -void test_linked_list_add(void) { - struct node nodes[4]; - void *begin, *end; - - // test with begin, end / prev, next - memset(nodes, 0, 4 * sizeof(struct node)); - begin = end = NULL; - - cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[0]); - CU_ASSERT_PTR_EQUAL(begin, &nodes[0]) - CU_ASSERT_PTR_EQUAL(end, &nodes[0]) - CU_ASSERT_PTR_NULL(nodes[0].prev) - CU_ASSERT_PTR_NULL(nodes[0].next) - - cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[1]); - CU_ASSERT_PTR_EQUAL(begin, &nodes[0]) - CU_ASSERT_PTR_EQUAL(end, &nodes[1]) - CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1]) - CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[0]) - - // test with begin only / prev, next - memset(nodes, 0, 4 * sizeof(struct node)); - begin = end = NULL; - - cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[0]); - CU_ASSERT_PTR_EQUAL(begin, &nodes[0]) - cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[1]); - CU_ASSERT_PTR_EQUAL(begin, &nodes[0]) - CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1]) - CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[0]) - - cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[2]); - CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[2]) - CU_ASSERT_PTR_EQUAL(nodes[2].prev, &nodes[1]) - - // test with end only / prev, next - memset(nodes, 0, 4 * sizeof(struct node)); - begin = end = NULL; - - cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[0]); - CU_ASSERT_PTR_EQUAL(end, &nodes[0]) - cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[1]); - CU_ASSERT_PTR_EQUAL(end, &nodes[1]) - CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1]) - CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[0]) - - cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[2]); - CU_ASSERT_PTR_EQUAL(end, &nodes[2]) - CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[2]) - CU_ASSERT_PTR_EQUAL(nodes[2].prev, &nodes[1]) - - // test with begin, end / next - memset(nodes, 0, 4 * sizeof(struct node)); - begin = end = NULL; - - cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[0]); - CU_ASSERT_PTR_EQUAL(begin, &nodes[0]) - CU_ASSERT_PTR_EQUAL(end, &nodes[0]) - cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[1]); - CU_ASSERT_PTR_EQUAL(end, &nodes[1]) - CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1]) - CU_ASSERT_PTR_NULL(nodes[1].prev) -} - -void test_linked_list_prepend(void) { - struct node nodes[4]; - void *begin, *end; - - // test with begin, end / prev, next - memset(nodes, 0, 4 * sizeof(struct node)); - begin = end = NULL; - - cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[0]); - CU_ASSERT_PTR_EQUAL(begin, &nodes[0]) - CU_ASSERT_PTR_EQUAL(end, &nodes[0]) - CU_ASSERT_PTR_NULL(nodes[0].prev) - CU_ASSERT_PTR_NULL(nodes[0].next) - - cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[1]); - CU_ASSERT_PTR_EQUAL(begin, &nodes[1]) - CU_ASSERT_PTR_EQUAL(end, &nodes[0]) - CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[0]) - CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[1]) - - // test with begin only / prev, next - memset(nodes, 0, 4 * sizeof(struct node)); - begin = end = NULL; - - cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[0]); - CU_ASSERT_PTR_EQUAL(begin, &nodes[0]) - cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[1]); - CU_ASSERT_PTR_EQUAL(begin, &nodes[1]) - CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[0]) - CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[1]) - - cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[2]); - CU_ASSERT_PTR_EQUAL(begin, &nodes[2]) - CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[1]) - CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[2]) - - // test with end only / prev, next - memset(nodes, 0, 4 * sizeof(struct node)); - begin = end = NULL; - - cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[0]); - CU_ASSERT_PTR_EQUAL(end, &nodes[0]) - cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[1]); - CU_ASSERT_PTR_EQUAL(end, &nodes[0]) - CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[0]) - CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[1]) - - cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[2]); - CU_ASSERT_PTR_EQUAL(end, &nodes[0]) - CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[1]) - CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[2]) - - // test with begin, end / next - memset(nodes, 0, 4 * sizeof(struct node)); - begin = end = NULL; - - cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[0]); - CU_ASSERT_PTR_EQUAL(begin, &nodes[0]) - CU_ASSERT_PTR_EQUAL(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]); - CU_ASSERT_PTR_EQUAL(begin, &nodes[2]) - CU_ASSERT_PTR_EQUAL(end, &nodes[0]) - CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[0]) - CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[1]) - CU_ASSERT_PTR_NULL(nodes[1].prev) - CU_ASSERT_PTR_NULL(nodes[0].prev) -} - -void test_linked_list_insert(void) { - struct node nodes[4]; - void *begin, *end; - - // insert mid list - memset(nodes, 0, 4 * sizeof(struct node)); - 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]); - CU_ASSERT_PTR_EQUAL(begin, &nodes[0]) - CU_ASSERT_PTR_EQUAL(end, &nodes[2]) - CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[3]) - CU_ASSERT_PTR_EQUAL(nodes[2].prev, &nodes[3]) - CU_ASSERT_PTR_EQUAL(nodes[3].prev, &nodes[1]) - CU_ASSERT_PTR_EQUAL(nodes[3].next, &nodes[2]) - - // insert end - memset(nodes, 0, 4 * sizeof(struct node)); - 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]); - CU_ASSERT_PTR_EQUAL(begin, &nodes[0]) - CU_ASSERT_PTR_EQUAL(end, &nodes[3]) - CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[3]) - CU_ASSERT_PTR_EQUAL(nodes[3].prev, &nodes[2]) - CU_ASSERT_PTR_NULL(nodes[3].next) - - // insert begin - memset(nodes, 0, 4 * sizeof(struct node)); - 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]); - CU_ASSERT_PTR_EQUAL(begin, &nodes[3]) - CU_ASSERT_PTR_EQUAL(end, &nodes[2]) - CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[3]) - CU_ASSERT_PTR_NULL(nodes[3].prev) - CU_ASSERT_PTR_EQUAL(nodes[3].next, &nodes[0]) -} - -void test_linked_list_insert_chain(void) { - struct node nodes[5]; - void *begin, *end; - - // insert mid list - memset(nodes, 0, 5 * sizeof(struct node)); - 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); - CU_ASSERT_PTR_EQUAL(begin, &nodes[0]) - CU_ASSERT_PTR_EQUAL(end, &nodes[2]) - CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[3]) - CU_ASSERT_PTR_EQUAL(nodes[2].prev, &nodes[4]) - CU_ASSERT_PTR_EQUAL(nodes[3].prev, &nodes[1]) - CU_ASSERT_PTR_EQUAL(nodes[4].next, &nodes[2]) - - // insert end - memset(nodes, 0, 5 * sizeof(struct node)); - 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); - CU_ASSERT_PTR_EQUAL(begin, &nodes[0]) - CU_ASSERT_PTR_EQUAL(end, &nodes[4]) - CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[3]) - CU_ASSERT_PTR_EQUAL(nodes[3].prev, &nodes[2]) - CU_ASSERT_PTR_NULL(nodes[4].next) - - // insert begin - memset(nodes, 0, 5 * sizeof(struct node)); - 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); - CU_ASSERT_PTR_EQUAL(begin, &nodes[3]) - CU_ASSERT_PTR_EQUAL(end, &nodes[2]) - CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[4]) - CU_ASSERT_PTR_NULL(nodes[3].prev) - CU_ASSERT_PTR_EQUAL(nodes[4].next, &nodes[0]) -} - -void test_linked_list_first(void) { - struct node *begin = create_nodes_test_data(3, NULL); - CU_ASSERT_PTR_EQUAL(cx_linked_list_first(begin, loc_prev), begin) - CU_ASSERT_PTR_EQUAL(cx_linked_list_first(begin->next, loc_prev), begin) - CU_ASSERT_PTR_EQUAL(cx_linked_list_first(begin->next->next, loc_prev), begin) - destroy_nodes_test_data(begin); -} - -void test_linked_list_last(void) { - struct node *begin = create_nodes_test_data(3, NULL); - struct node *end = begin->next->next; - CU_ASSERT_PTR_EQUAL(cx_linked_list_last(begin, loc_next), end) - CU_ASSERT_PTR_EQUAL(cx_linked_list_last(begin->next, loc_next), end) - CU_ASSERT_PTR_EQUAL(cx_linked_list_last(begin->next->next, loc_next), end) - destroy_nodes_test_data(begin); -} - -void test_linked_list_prev(void) { - struct node *begin = create_nodes_test_data(3, NULL); - CU_ASSERT_PTR_NULL(cx_linked_list_prev(begin, loc_next, begin)) - CU_ASSERT_PTR_EQUAL(cx_linked_list_prev(begin, loc_next, begin->next), begin) - CU_ASSERT_PTR_EQUAL(cx_linked_list_prev(begin, loc_next, begin->next->next), begin->next) - destroy_nodes_test_data(begin); -} - -void test_linked_list_remove(void) { - void *begin, *end; - - int data[] = {2, 4, 6}; - begin = create_nodes_test_data(3, data); - struct node *first = begin; - struct node *second = first->next; - struct node *third = second->next; - end = third; - - cx_linked_list_remove(&begin, &end, loc_prev, loc_next, second); - CU_ASSERT_PTR_EQUAL(begin, first) - CU_ASSERT_PTR_EQUAL(end, third) - CU_ASSERT_PTR_NULL(first->prev) - CU_ASSERT_PTR_EQUAL(first->next, third) - CU_ASSERT_PTR_EQUAL(third->prev, first) - CU_ASSERT_PTR_NULL(third->next) - - cx_linked_list_remove(&begin, &end, loc_prev, loc_next, third); - CU_ASSERT_PTR_EQUAL(begin, first) - CU_ASSERT_PTR_EQUAL(end, first) - CU_ASSERT_PTR_NULL(first->prev) - CU_ASSERT_PTR_NULL(first->next) - - cx_linked_list_remove(&begin, &end, loc_prev, loc_next, first); - CU_ASSERT_PTR_NULL(begin) - CU_ASSERT_PTR_NULL(end) - - free(first); - free(second); - free(third); -} - -void test_linked_list_size(void) { - struct node *list; - - CU_ASSERT_PTR_EQUAL(cx_linked_list_size(NULL, loc_next), 0) - - list = create_nodes_test_data(5, NULL); - CU_ASSERT_EQUAL(cx_linked_list_size(list, loc_next), 5) - destroy_nodes_test_data(list); - - list = create_nodes_test_data(13, NULL); - CU_ASSERT_EQUAL(cx_linked_list_size(list, loc_next), 13) - destroy_nodes_test_data(list); -} - -void test_linked_list_sort(void) { - int expected[] = { - 14, 30, 151, 163, 227, 300, 315, 317, 363, 398, 417, 424, 438, 446, 508, 555, 605, 713, 716, 759, 761, 880, - 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 1707, 1734, 1771, 1874, 1894, - 1976, 2079, 2124, 2130, 2135, 2266, 2338, 2358, 2430, 2500, 2540, 2542, 2546, 2711, 2733, 2754, 2764, 2797, - 2888, 2900, 3020, 3053, 3109, 3244, 3275, 3302, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 3675, 3677, - 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681, - 4785, 4791, 4801, 4859, 4903, 4973 - }; - int scrambled[] = { - 759, 716, 880, 761, 2358, 2542, 2500, 2540, 2546, 2711, 2430, 1707, 1874, 1771, 1894, 1734, 1976, 2079, - 2124, 2130, 2135, 2266, 2338, 2733, 2754, 2764, 2797, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 2888, - 2900, 3020, 3053, 3109, 3244, 3275, 3302, 438, 446, 508, 555, 605, 713, 14, 30, 151, 163, 227, 300, - 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 315, 317, 363, 398, 417, 424, - 3675, 3677, 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4785, 4791, 4801, 4859, 4903, 4973, - 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681 - }; - - void *begin = create_nodes_test_data(100, scrambled); - void *end = cx_linked_list_last(begin, loc_next); - - cx_linked_list_sort(&begin, &end, loc_prev, loc_next, loc_data, - false, cmp_int); - - struct node *check = begin; - struct node *check_last = NULL; - CU_ASSERT_PTR_NULL(check->prev) - CU_ASSERT_EQUAL(check->data, expected[0]) - cx_for_n (i, 100) { - CU_ASSERT_EQUAL(check->data, expected[i]) - CU_ASSERT_PTR_EQUAL(check->prev, check_last) - if (i < 99) { - CU_ASSERT_PTR_NOT_NULL(check->next) - } - check_last = check; - check = check->next; - } - CU_ASSERT_PTR_NULL(check) - CU_ASSERT_PTR_EQUAL(end, check_last) - - destroy_nodes_test_data(begin); -} - -void test_linked_list_reverse(void) { - void *begin, *end; - - int data[] = {2, 4, 6, 8}; - int reversed[] = {8, 6, 4, 2}; - - void *list = create_nodes_test_data(4, data); - void *expected = create_nodes_test_data(4, reversed); - - begin = list; - end = cx_linked_list_last(list, loc_next); - - cx_linked_list_reverse(&begin, &end, loc_prev, loc_next); - CU_ASSERT_PTR_EQUAL(end, list) - CU_ASSERT_PTR_EQUAL(begin, cx_linked_list_first(end, loc_prev)) - CU_ASSERT_TRUE(0 == cx_linked_list_compare(begin, expected, loc_next, loc_data, - 0, cmp_int)) - - destroy_nodes_test_data(begin); - destroy_nodes_test_data(expected); -} - -static void verify_linked_list_create(CxList *list) { - CU_ASSERT_EQUAL(list->size, 0) - CU_ASSERT_EQUAL(list->capacity, (size_t) -1) - CU_ASSERT_PTR_EQUAL(list->allocator, cxTestingAllocator) - CU_ASSERT_PTR_EQUAL(list->cmpfunc, cmp_int) - - cxListDestroy(list); -} - -void test_hl_linked_list_create(void) { - CxList *list = cxLinkedListCreate(cxTestingAllocator, cmp_int, sizeof(int)); - CU_ASSERT_EQUAL(list->itemsize, sizeof(int)) - verify_linked_list_create(list); -} - -void test_hl_ptr_linked_list_create(void) { - CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int); - CU_ASSERT_EQUAL(list->itemsize, sizeof(void *)) - verify_linked_list_create(list); -} - -void test_hl_linked_list_from_array(void) { - int data[] = {2, 4, 5, 7, 10, 15}; - - CxList *expected = cxLinkedListCreate(cxTestingAllocator, cmp_int, sizeof(int)); - cx_for_n (i, 5) cxListAdd(expected, &data[i]); - - CxList *list = cxLinkedListFromArray(cxTestingAllocator, cmp_int, sizeof(int), 5, data); - - CU_ASSERT_TRUE(0 == cxListCompare(list, expected)) - - cxListDestroy(list); - cxListDestroy(expected); -} - -static void verify_hl_linked_list_add( - CxList *list, - int data[], - size_t len, - bool write_through -) { - cx_for_n (i, len) CU_ASSERT_EQUAL(cxListAdd(list, &data[i]), 0) - CU_ASSERT_EQUAL(list->size, len) - CU_ASSERT_TRUE(list->capacity >= list->size) - cx_for_n (i, len) CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), data[i]) - cx_for_n (i, len) ++data[i]; - if (write_through) { - cx_for_n (i, len) CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), data[i]) - } else { - cx_for_n (i, len) CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), data[i] - 1) - } - cxListDestroy(list); -} - -void test_hl_linked_list_add(void) { - CxList *list = cxLinkedListCreate(cxTestingAllocator, cmp_int, sizeof(int)); - int data[] = {5, 47, 13, 9, 18, 1, 42}; - verify_hl_linked_list_add(list, data, sizeof(data) / sizeof(int), false); -} - -void test_hl_ptr_linked_list_add(void) { - CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int); - int data[] = {5, 47, 84, 13, 9, 18, 90, 1, 42}; - verify_hl_linked_list_add(list, data, sizeof(data) / sizeof(int), true); -} - -static void verify_hl_linked_list_insert(CxList *list) { - int a = 5, b = 47, c = 13, d = 42; - - CU_ASSERT_NOT_EQUAL(cxListInsert(list, 1, &a), 0) - CU_ASSERT_EQUAL(list->size, 0) - CU_ASSERT_EQUAL(cxListInsert(list, 0, &a), 0) - CU_ASSERT_EQUAL(list->size, 1) - CU_ASSERT_EQUAL(cxListInsert(list, 0, &b), 0) - CU_ASSERT_EQUAL(list->size, 2) - CU_ASSERT_EQUAL(cxListInsert(list, 1, &c), 0) - CU_ASSERT_EQUAL(list->size, 3) - CU_ASSERT_EQUAL(cxListInsert(list, 3, &d), 0) - - CU_ASSERT_EQUAL(list->size, 4) - CU_ASSERT_TRUE(list->capacity >= list->size) - - CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47) - CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13) - CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 5) - CU_ASSERT_EQUAL(*(int *) cxListAt(list, 3), 42) - - cxListDestroy(list); -} - -void test_hl_linked_list_insert(void) { - verify_hl_linked_list_insert(cxLinkedListCreate(cxTestingAllocator, cmp_int, sizeof(int))); -} - -void test_hl_ptr_linked_list_insert(void) { - verify_hl_linked_list_insert(cxPointerLinkedListCreate(cxTestingAllocator, cmp_int)); -} - -static void verify_hl_linked_list_remove(CxList *list) { - CU_ASSERT_EQUAL(list->size, 4) - CU_ASSERT_TRUE(list->capacity >= list->size) - - CU_ASSERT_NOT_EQUAL(cxListRemove(list, 4), 0) - - CU_ASSERT_EQUAL(cxListRemove(list, 2), 0) - CU_ASSERT_EQUAL(list->size, 3) - CU_ASSERT_TRUE(list->capacity >= list->size) - CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5) - CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47) - CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13) - - CU_ASSERT_EQUAL(cxListRemove(list, 0), 0) - CU_ASSERT_EQUAL(list->size, 2) - CU_ASSERT_TRUE(list->capacity >= list->size) - CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47) - CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13) - - CU_ASSERT_EQUAL(cxListRemove(list, 1), 0) - CU_ASSERT_EQUAL(list->size, 1) - CU_ASSERT_TRUE(list->capacity >= list->size) - CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47) - - CU_ASSERT_EQUAL(cxListRemove(list, 0), 0) - CU_ASSERT_EQUAL(list->size, 0) - CU_ASSERT_TRUE(list->capacity >= list->size) - - CU_ASSERT_NOT_EQUAL(cxListRemove(list, 0), 0) - - cxListDestroy(list); -} - -void test_hl_linked_list_remove(void) { - int data[] = {5, 47, 42, 13}; - CxList *list = cxLinkedListFromArray(cxTestingAllocator, cmp_int, - sizeof(int), 4, data); - verify_hl_linked_list_remove(list); -} - -void test_hl_ptr_linked_list_remove(void) { - int a = 5, b = 47, c = 42, d = 13; - CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int); - cxListAdd(list, &a); - cxListAdd(list, &b); - cxListAdd(list, &c); - cxListAdd(list, &d); - verify_hl_linked_list_remove(list); -} - -static void verify_hl_linked_list_at( - CxList *list, - size_t len, - int *data -) { - CU_ASSERT_EQUAL(list->size, len) - cx_for_n (i, len) CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), data[i]) - CU_ASSERT_PTR_NULL(cxListAt(list, len)) - free(data); - cxListDestroy(list); -} - -void test_hl_linked_list_at(void) { - size_t len = 100; - int *data = create_ints_test_data(len); - CxList *list = cxLinkedListFromArray(cxTestingAllocator, cmp_int, - sizeof(int), len, data); - verify_hl_linked_list_at(list, len, data); -} - -void test_hl_ptr_linked_list_at(void) { - size_t len = 250; - int *data = create_ints_test_data(len); - CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int); - cx_for_n (i, len) cxListAdd(list, &data[i]); - verify_hl_linked_list_at(list, len, data); -} - -static void verify_hl_linked_list_find( - CxList *list, - size_t len, - int *data -) { - cx_for_n (attempt, 100) { - size_t exp = rand() % len; // NOLINT(cert-msc50-cpp) - int val = data[exp]; - cx_for_n (i, exp) { - if (data[i] == val) { - exp = i; - break; - } - } - CU_ASSERT_EQUAL(cxListFind(list, &val), exp) - } - free(data); - cxListDestroy(list); -} - -void test_hl_linked_list_find(void) { - size_t len = 100; - int *data = create_ints_test_data(len); - CxList *list = cxLinkedListFromArray(cxTestingAllocator, cmp_int, sizeof(int), len, data); - verify_hl_linked_list_find(list, len, data); -} - -void test_hl_ptr_linked_list_find(void) { - size_t len = 250; - int *data = create_ints_test_data(len); - CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int); - cx_for_n (i, len) cxListAdd(list, &data[i]); - verify_hl_linked_list_find(list, len, data); -} - -struct sort_test_data { - size_t len; - int *data; - int *sorted; -}; - -static struct sort_test_data create_sort_test_data(void) { - size_t len = 1000; - int *data = create_ints_test_data(len); - int *sorted = malloc(sizeof(int) * len); - memcpy(sorted, data, sizeof(int) * len); - qsort(sorted, len, sizeof(int), cmp_int); - struct sort_test_data s = {len, data, sorted}; - return s; -} - -static void free_sort_test_data(struct sort_test_data s) { - free(s.data); - free(s.sorted); -} - -static void verify_hl_linked_list_sort( - CxList *list, - struct sort_test_data td -) { - cxListSort(list); - cx_for_n (i, td.len) CU_ASSERT_EQUAL_FATAL(*(int *) cxListAt(list, i), td.sorted[i]) - free_sort_test_data(td); - cxListDestroy(list); -} - -void test_hl_linked_list_sort(void) { - struct sort_test_data td = create_sort_test_data(); - CxList *list = cxLinkedListFromArray(cxTestingAllocator, cmp_int, sizeof(int), td.len, td.data); - verify_hl_linked_list_sort(list, td); -} - -void test_hl_ptr_linked_list_sort(void) { - struct sort_test_data td = create_sort_test_data(); - CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int); - cx_for_n (i, td.len) cxListAdd(list, &td.data[i]); - verify_hl_linked_list_sort(list, td); -} - -void verify_hl_linked_list_iterator(CxList *list) { - int i = 0; - CxIterator iter = cxListBegin(list); - cx_foreach(int*, x, iter) { - CU_ASSERT_EQUAL(iter.index, (size_t) (i + 1) / 2) - CU_ASSERT_EQUAL(*x, i) - if (*x % 2 == 1) iter.remove = true; - i++; - } - CU_ASSERT_EQUAL(i, 10) - CU_ASSERT_EQUAL_FATAL(list->size, 5) - cx_for_n(j, 5) CU_ASSERT_EQUAL(*(int *) cxListAt(list, j), (int) j * 2) - cxListDestroy(list); -} - -void test_hl_linked_list_iterator(void) { - CxList *list = cxLinkedListCreate(cxTestingAllocator, cmp_int, sizeof(int)); - cx_for_n (i, 10) cxListAdd(list, &i); - verify_hl_linked_list_iterator(list); -} - -void test_hl_ptr_linked_list_iterator(void) { - CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int); - int data[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; - cx_for_n (i, 10) cxListAdd(list, &data[i]); - verify_hl_linked_list_iterator(list); -} - -static void verify_hl_linked_list_insert_via_iterator( - CxList *list, - int *testdata -) { - CxIterator iter = cxListIterator(list, 2); - CU_ASSERT_EQUAL(iter.index, 2) - CU_ASSERT_EQUAL(*(int *) cxIteratorCurrent(&iter), 2) - size_t i = 4; - - ++i; - cxListInsertAfter(&iter, &testdata[i]); - CU_ASSERT_EQUAL(iter.index, 2) - CU_ASSERT_EQUAL(*(int *) cxIteratorCurrent(&iter), 2) - ++i; - cxListInsertBefore(&iter, &testdata[i]); - CU_ASSERT_EQUAL(iter.index, 3) - CU_ASSERT_EQUAL(*(int *) cxIteratorCurrent(&iter), 2) - - iter = cxListBegin(list); - ++i; - cxListInsertBefore(&iter, &testdata[i]); - CU_ASSERT_EQUAL(iter.index, 1) - CU_ASSERT_EQUAL(*(int *) cxIteratorCurrent(&iter), 0) - iter = cxListIterator(list, list->size); - ++i; - cxListInsertBefore(&iter, &testdata[i]); - CU_ASSERT_EQUAL(iter.index, 9) - CU_ASSERT_FALSE(cxIteratorValid(&iter)) - iter = cxListIterator(list, list->size); - ++i; - cxListInsertAfter(&iter, &testdata[i]); - CU_ASSERT_EQUAL(iter.index, 10) - CU_ASSERT_FALSE(cxIteratorValid(&iter)) - - int expdata[] = {30, 0, 1, 20, 2, 10, 3, 4, 40, 50}; - cx_for_n (j, 10) CU_ASSERT_EQUAL(*(int *) cxListAt(list, j), expdata[j]) - cxListDestroy(list); -} - -void test_hl_linked_list_insert_via_iterator(void) { - int testdata[] = {0, 1, 2, 3, 4, 10, 20, 30, 40, 50}; - // only add the first five elements, the remaining five will be inserted - CxList *list = cxLinkedListFromArray(cxTestingAllocator, cmp_int, sizeof(int), 5, testdata); - verify_hl_linked_list_insert_via_iterator(list, testdata); -} - -void test_hl_ptr_linked_list_insert_via_iterator(void) { - int testdata[] = {0, 1, 2, 3, 4, 10, 20, 30, 40, 50}; - CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int); - // only add the first five elements, the remaining five will be inserted - cx_for_n (i, 5) cxListAdd(list, &testdata[i]); - verify_hl_linked_list_insert_via_iterator(list, testdata); -} - -static void test_setup_allocator(void) { - cxTestingAllocatorReset(); -} - -static void test_verify_allocator(void) { - CU_ASSERT_TRUE(cxTestingAllocatorVerify()) -} - -int main() { - CU_pSuite suite = NULL; - - if (CUE_SUCCESS != CU_initialize_registry()) { - return CU_get_error(); - } - - suite = CU_add_suite("low level linked list", NULL, NULL); - - cu_add_test(suite, test_linked_list_link_unlink); - cu_add_test(suite, test_linked_list_at); - cu_add_test(suite, test_linked_list_find); - cu_add_test(suite, test_linked_list_compare); - cu_add_test(suite, test_linked_list_prepend); - cu_add_test(suite, test_linked_list_add); - cu_add_test(suite, test_linked_list_insert); - cu_add_test(suite, test_linked_list_insert_chain); - cu_add_test(suite, test_linked_list_first); - cu_add_test(suite, test_linked_list_last); - cu_add_test(suite, test_linked_list_prev); - cu_add_test(suite, test_linked_list_remove); - cu_add_test(suite, test_linked_list_size); - cu_add_test(suite, test_linked_list_sort); - cu_add_test(suite, test_linked_list_reverse); - - suite = CU_add_suite_with_setup_and_teardown( - "high level linked list", NULL, NULL, - test_setup_allocator, test_verify_allocator); - - cu_add_test(suite, test_hl_linked_list_create); - cu_add_test(suite, test_hl_linked_list_from_array); - cu_add_test(suite, test_hl_linked_list_add); - cu_add_test(suite, test_hl_linked_list_insert); - cu_add_test(suite, test_hl_linked_list_remove); - cu_add_test(suite, test_hl_linked_list_at); - cu_add_test(suite, test_hl_linked_list_find); - cu_add_test(suite, test_hl_linked_list_sort); - cu_add_test(suite, test_hl_linked_list_iterator); - cu_add_test(suite, test_hl_linked_list_insert_via_iterator); - - suite = CU_add_suite_with_setup_and_teardown( - "high level pointer linked list", NULL, NULL, - test_setup_allocator, test_verify_allocator); - - cu_add_test(suite, test_hl_ptr_linked_list_create); - cu_add_test(suite, test_hl_ptr_linked_list_add); - cu_add_test(suite, test_hl_ptr_linked_list_insert); - cu_add_test(suite, test_hl_ptr_linked_list_remove); - cu_add_test(suite, test_hl_ptr_linked_list_at); - cu_add_test(suite, test_hl_ptr_linked_list_find); - cu_add_test(suite, test_hl_ptr_linked_list_sort); - cu_add_test(suite, test_hl_ptr_linked_list_iterator); - cu_add_test(suite, test_hl_ptr_linked_list_insert_via_iterator); - - CU_basic_set_mode(UCX_CU_BRM); - - int exitcode; - if (CU_basic_run_tests()) { - exitcode = CU_get_error(); - } else { - exitcode = CU_get_number_of_failures() == 0 ? 0 : 1; - } - CU_cleanup_registry(); - return exitcode; -}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/test_list.cpp Sat Apr 16 18:02:10 2022 +0200 @@ -0,0 +1,827 @@ +/* + * 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/utils.h" +#include "util_allocator.h" + +#include <gtest/gtest.h> +#include <array> +#include <vector> +#include <unordered_set> +#include <algorithm> + +static int cmp_int_impl( + int const *l, + int const *r +) { + int left = *l, right = *r; + return left == right ? 0 : (left < right ? -1 : 1); +} + +#define cmp_int ((CxListComparator) cmp_int_impl) + +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; + + explicit node_test_data(node *begin) : begin(begin) {} + node_test_data(node_test_data&) = delete; + node_test_data(node_test_data&&) = default; + + ~node_test_data() { + auto n = begin; + while (n != nullptr) { + auto next = n->next; + delete n; + n = next; + } + } +}; + +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<typename InputIter> +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<int> data) { + return create_nodes_test_data(data.begin(), data.end()); +} + +template<size_t N> +struct int_test_data { + std::array<int, N> data; + + int_test_data() { + cx_for_n (i, N) data[i] = ::rand(); // NOLINT(cert-msc50-cpp) + } +}; + +TEST(LinkedList_LowLevel, link_unlink) { + node a, b, c; + + cx_linked_list_link(&a, &b, loc_prev, loc_next); + 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, false, cmp_int, &s), 0); + s = 4; + EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, false, cmp_int, &s), 1); + s = 6; + EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, false, cmp_int, &s), 2); + s = 8; + EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, false, cmp_int, &s), 3); + s = 10; + EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, false, cmp_int, &s), 4); + s = -2; + EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, false, 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, false, cmp_int), 0); + EXPECT_LT(cx_linked_list_compare(lb, la, loc_next, loc_data, false, cmp_int), 0); + EXPECT_GT(cx_linked_list_compare(lc, la, loc_next, loc_data, false, cmp_int), 0); + EXPECT_LT(cx_linked_list_compare(la, lc, loc_next, loc_data, false, cmp_int), 0); + EXPECT_EQ(cx_linked_list_compare(la, la, loc_next, loc_data, false, 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<void *>(testdata.begin); + auto first = testdata.begin; + auto second = first->next; + auto third = second->next; + auto end = reinterpret_cast<void *>(third); + + cx_linked_list_remove(&begin, &end, loc_prev, loc_next, second); + 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<1000> testdata; + std::array<int, 1000> 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, + false, cmp_int); + + node *check = reinterpret_cast<node *>(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<void *>(testdata.begin); + auto end = cx_linked_list_last(begin, loc_next); + auto orig_begin = begin, orig_end = end; + + cx_linked_list_reverse(&begin, &end, loc_prev, loc_next); + EXPECT_EQ(end, orig_begin); + EXPECT_EQ(begin, orig_end); + EXPECT_EQ(cx_linked_list_compare(begin, expected.begin, loc_next, loc_data, 0, cmp_int), 0); +} + +class HighLevelTest : public ::testing::Test { + mutable std::unordered_set<CxList *> lists; +protected: + void SetUp() override { + cxTestingAllocatorReset(); + } + + void TearDown() override { + for (auto &&l: lists) cxListDestroy(l); + EXPECT_TRUE(cxTestingAllocatorVerify()); + } + + static constexpr size_t testdata_len = 250; + int_test_data<testdata_len> testdata; + + auto autofree(CxList *list) const -> CxList * { + lists.insert(list); + return list; + } + + auto linkedListFromTestData() const -> CxList * { + return autofree( + cxLinkedListFromArray( + cxTestingAllocator, + cmp_int, + sizeof(int), + testdata_len, + testdata.data.data() + ) + ); + } + + auto pointerLinkedListFromTestData() const -> CxList * { + auto list = autofree(cxPointerLinkedListCreate(cxTestingAllocator, cmp_int)); + cx_for_n(i, testdata_len) cxListAdd(list, &testdata.data[i]); + return list; + } + + static void verifyCreate(CxList *list) { + EXPECT_EQ(list->size, 0); + EXPECT_EQ(list->capacity, (size_t) -1); + EXPECT_EQ(list->allocator, cxTestingAllocator); + EXPECT_EQ(list->cmpfunc, cmp_int); + } + + void verifyAdd(CxList *list, bool write_through) { + 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 (write_through) { + 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); + + EXPECT_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); + } + + 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, list->size) 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<int, testdata_len> 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; + CxIterator iter = cxListBegin(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) iter.remove = true; + 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}; + + CxIterator iter = cxListIterator(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 = cxListBegin(list); + cxListInsertBefore(&iter, &newdata[2]); + EXPECT_TRUE(cxIteratorValid(&iter)); + EXPECT_EQ(iter.index, 1); + EXPECT_EQ(*(int *) cxIteratorCurrent(&iter), 0); + iter = cxListIterator(list, list->size); + cxListInsertBefore(&iter, &newdata[3]); + EXPECT_FALSE(cxIteratorValid(&iter)); + EXPECT_EQ(iter.index, 9); + iter = cxListIterator(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]); + } +}; + +class LinkedList : public HighLevelTest { +}; + +class PointerLinkedList : public HighLevelTest { +}; + +TEST_F(LinkedList, cxLinkedListCreate) { + CxList *list = autofree(cxLinkedListCreate(cxTestingAllocator, cmp_int, sizeof(int))); + EXPECT_EQ(list->itemsize, sizeof(int)); + verifyCreate(list); +} + +TEST_F(PointerLinkedList, cxPointerLinkedListCreate) { + CxList *list = autofree(cxPointerLinkedListCreate(cxTestingAllocator, cmp_int)); + EXPECT_EQ(list->itemsize, sizeof(void *)); + verifyCreate(list); +} + +TEST_F(LinkedList, cxLinkedListFromArray) { + CxList *expected = autofree(cxLinkedListCreate(cxTestingAllocator, cmp_int, sizeof(int))); + cx_for_n (i, testdata_len) cxListAdd(expected, &testdata.data[i]); + CxList *list = autofree(cxLinkedListFromArray(cxTestingAllocator, cmp_int, sizeof(int), + testdata_len, testdata.data.data())); + EXPECT_EQ(cxListCompare(list, expected), 0); +} + +TEST_F(LinkedList, cxListAdd) { + CxList *list = autofree(cxLinkedListCreate(cxTestingAllocator, cmp_int, sizeof(int))); + verifyAdd(list, false); +} + +TEST_F(PointerLinkedList, cxListAdd) { + CxList *list = autofree(cxPointerLinkedListCreate(cxTestingAllocator, cmp_int)); + verifyAdd(list, true); +} + +TEST_F(LinkedList, cxListInsert) { + verifyInsert(autofree(cxLinkedListCreate(cxTestingAllocator, cmp_int, sizeof(int)))); +} + +TEST_F(PointerLinkedList, cxListInsert) { + verifyInsert(autofree(cxPointerLinkedListCreate(cxTestingAllocator, cmp_int))); +} + +TEST_F(LinkedList, cxListRemove) { + verifyRemove(linkedListFromTestData()); +} + +TEST_F(PointerLinkedList, cxListRemove) { + verifyRemove(pointerLinkedListFromTestData()); +} + +TEST_F(LinkedList, cxListAt) { + verifyAt(linkedListFromTestData()); +} + +TEST_F(PointerLinkedList, cxListAt) { + verifyAt(pointerLinkedListFromTestData()); +} + +TEST_F(LinkedList, cxListFind) { + verifyFind(linkedListFromTestData()); +} + +TEST_F(PointerLinkedList, cxListFind) { + verifyFind(pointerLinkedListFromTestData()); +} + +TEST_F(LinkedList, cxListSort) { + verifySort(linkedListFromTestData()); +} + +TEST_F(PointerLinkedList, cxListSort) { + verifySort(pointerLinkedListFromTestData()); +} + +TEST_F(LinkedList, Iterator) { + verifyIterator(linkedListFromTestData()); +} + +TEST_F(PointerLinkedList, Iterator) { + verifyIterator(pointerLinkedListFromTestData()); +} + +TEST_F(LinkedList, InsertViaIterator) { + int fivenums[] = {0, 1, 2, 3, 4, 5}; + CxList *list = autofree(cxLinkedListFromArray(cxTestingAllocator, cmp_int, sizeof(int), 5, fivenums)); + verifyInsertViaIterator(list); +} + +TEST_F(PointerLinkedList, InsertViaIterator) { + int fivenums[] = {0, 1, 2, 3, 4, 5}; + CxList *list = autofree(cxPointerLinkedListCreate(cxTestingAllocator, cmp_int)); + cx_for_n (i, 5) cxListAdd(list, &fivenums[i]); + verifyInsertViaIterator(list); +}
