Mercurial > hg > ucx / changeset

     1.1 --- a/test/CMakeLists.txt	Sat Apr 16 17:28:36 2022 +0200
     1.2 +++ b/test/CMakeLists.txt	Sat Apr 16 18:02:10 2022 +0200
     1.3 @@ -1,27 +1,3 @@
     1.4 -# Transitional support for CTest written tests
     1.5 -message(CHECK_START "Searching for CUnit test framework")
     1.6 -
     1.7 -find_path(CUNIT_INCLUDE_DIR NAMES CUnit/CUnit.h)
     1.8 -find_library(CUNIT_LIBRARY NAMES cunit libcunit cunitlib)
     1.9 -include(FindPackageHandleStandardArgs)
    1.10 -find_package_handle_standard_args(CUnit DEFAULT_MSG CUNIT_LIBRARY CUNIT_INCLUDE_DIR)
    1.11 -
    1.12 -if (CUNIT_FOUND)
    1.13 -    message(CHECK_PASS "found: compiling tests.")
    1.14 -    set(TESTS
    1.15 -            test_list
    1.16 -    )
    1.17 -
    1.18 -    foreach (test ${TESTS})
    1.19 -        add_executable(${test} ${test}.c)
    1.20 -        target_link_libraries(${test} PRIVATE ucx_static ${CUNIT_LIBRARY})
    1.21 -        target_include_directories(${test} PRIVATE ${CUNIT_INCLUDE_DIR})
    1.22 -        add_test(NAME ${test} COMMAND ${test} WORKING_DIRECTORY "${CMAKE_CURRENT_BINARY_DIR}")
    1.23 -    endforeach ()
    1.24 -else ()
    1.25 -    message(CHECK_FAIL "not found: CUnit tests will not be available.")
    1.26 -endif ()
    1.27 -
    1.28  # Load Google Test Framework
    1.29  set(CMAKE_CXX_STANDARD 11)
    1.30  
    1.31 @@ -39,8 +15,10 @@
    1.32  
    1.33  add_executable(ucxtest
    1.34          test_allocator.cpp
    1.35 +        test_list.cpp
    1.36          test_tree.cpp
    1.37          selftest.cpp
    1.38 +        util_allocator.c
    1.39          )
    1.40  target_link_libraries(ucxtest PRIVATE ucx_static gtest_main)
    1.41  gtest_discover_tests(ucxtest)

     2.1 --- a/test/test_config.h	Sat Apr 16 17:28:36 2022 +0200
     2.2 +++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.3 @@ -1,38 +0,0 @@
     2.4 -/*
     2.5 - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
     2.6 - *
     2.7 - * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
     2.8 - *
     2.9 - * Redistribution and use in source and binary forms, with or without
    2.10 - * modification, are permitted provided that the following conditions are met:
    2.11 - *
    2.12 - *   1. Redistributions of source code must retain the above copyright
    2.13 - *      notice, this list of conditions and the following disclaimer.
    2.14 - *
    2.15 - *   2. Redistributions in binary form must reproduce the above copyright
    2.16 - *      notice, this list of conditions and the following disclaimer in the
    2.17 - *      documentation and/or other materials provided with the distribution.
    2.18 - *
    2.19 - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
    2.20 - * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    2.21 - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
    2.22 - * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
    2.23 - * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
    2.24 - * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
    2.25 - * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
    2.26 - * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
    2.27 - * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
    2.28 - * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
    2.29 - * POSSIBILITY OF SUCH DAMAGE.
    2.30 - */
    2.31 -
    2.32 -#ifndef UCX_TEST_CONFIG_H
    2.33 -#define UCX_TEST_CONFIG_H
    2.34 -
    2.35 -#include <CUnit/Basic.h>
    2.36 -
    2.37 -#define UCX_CU_BRM CU_BRM_NORMAL
    2.38 -
    2.39 -#define cu_add_test(suite, name) CU_add_test(suite, #name, name)
    2.40 -
    2.41 -#endif /* UCX_TEST_CONFIG_H */

     3.1 --- a/test/test_list.c	Sat Apr 16 17:28:36 2022 +0200
     3.2 +++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.3 @@ -1,976 +0,0 @@
     3.4 -/*
     3.5 - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
     3.6 - *
     3.7 - * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
     3.8 - *
     3.9 - * Redistribution and use in source and binary forms, with or without
    3.10 - * modification, are permitted provided that the following conditions are met:
    3.11 - *
    3.12 - *   1. Redistributions of source code must retain the above copyright
    3.13 - *      notice, this list of conditions and the following disclaimer.
    3.14 - *
    3.15 - *   2. Redistributions in binary form must reproduce the above copyright
    3.16 - *      notice, this list of conditions and the following disclaimer in the
    3.17 - *      documentation and/or other materials provided with the distribution.
    3.18 - *
    3.19 - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
    3.20 - * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    3.21 - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
    3.22 - * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
    3.23 - * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
    3.24 - * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
    3.25 - * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
    3.26 - * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
    3.27 - * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
    3.28 - * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
    3.29 - * POSSIBILITY OF SUCH DAMAGE.
    3.30 - */
    3.31 -
    3.32 -#include "cx/linked_list.h"
    3.33 -#include "cx/utils.h"
    3.34 -#include "test_config.h"
    3.35 -#include "util_allocator.h"
    3.36 -
    3.37 -static int cmp_int_impl(
    3.38 -        int const *l,
    3.39 -        int const *r
    3.40 -) {
    3.41 -    int left = *l, right = *r;
    3.42 -    return left == right ? 0 : (left < right ? -1 : 1);
    3.43 -}
    3.44 -
    3.45 -#define cmp_int ((CxListComparator) cmp_int_impl)
    3.46 -
    3.47 -struct node {
    3.48 -    struct node *next;
    3.49 -    struct node *prev;
    3.50 -    int data;
    3.51 -};
    3.52 -
    3.53 -#define nd(name) name = {0}
    3.54 -
    3.55 -const ptrdiff_t loc_prev = offsetof(struct node, prev);
    3.56 -const ptrdiff_t loc_next = offsetof(struct node, next);
    3.57 -const ptrdiff_t loc_data = offsetof(struct node, data);
    3.58 -
    3.59 -static struct node *create_nodes_test_data(
    3.60 -        size_t n,
    3.61 -        int const data[]
    3.62 -) {
    3.63 -    CU_ASSERT_NOT_EQUAL_FATAL(n, 0)
    3.64 -    struct node *begin = calloc(1, sizeof(struct node));
    3.65 -    struct node *prev = begin;
    3.66 -    if (data) begin->data = data[0];
    3.67 -    for (size_t i = 1; i < n; i++) {
    3.68 -        struct node *node = calloc(1, sizeof(struct node));
    3.69 -        if (data) node->data = data[i];
    3.70 -        cx_linked_list_link(prev, node, loc_prev, loc_next);
    3.71 -        prev = node;
    3.72 -    }
    3.73 -    return begin;
    3.74 -}
    3.75 -
    3.76 -static void destroy_nodes_test_data(struct node *begin) {
    3.77 -    struct node *node = begin;
    3.78 -    while (node) {
    3.79 -        struct node *next = node->next;
    3.80 -        free(node);
    3.81 -        node = next;
    3.82 -    }
    3.83 -}
    3.84 -
    3.85 -static int *create_ints_test_data(size_t len) {
    3.86 -    int *data = malloc(sizeof(int) * len);
    3.87 -    cx_for_n (i, len) data[i] = rand(); // NOLINT(cert-msc50-cpp)
    3.88 -    return data;
    3.89 -}
    3.90 -
    3.91 -void test_linked_list_link_unlink(void) {
    3.92 -
    3.93 -    struct node nd(a), nd(b), nd(c);
    3.94 -
    3.95 -    cx_linked_list_link(&a, &b, loc_prev, loc_next);
    3.96 -    CU_ASSERT_PTR_NULL(a.prev)
    3.97 -    CU_ASSERT_PTR_EQUAL(a.next, &b)
    3.98 -    CU_ASSERT_PTR_EQUAL(b.prev, &a)
    3.99 -    CU_ASSERT_PTR_NULL(b.next)
   3.100 -
   3.101 -    cx_linked_list_unlink(&a, &b, loc_prev, loc_next);
   3.102 -    CU_ASSERT_PTR_NULL(a.prev)
   3.103 -    CU_ASSERT_PTR_NULL(a.next)
   3.104 -    CU_ASSERT_PTR_NULL(b.prev)
   3.105 -    CU_ASSERT_PTR_NULL(b.next)
   3.106 -
   3.107 -    cx_linked_list_link(&b, &c, loc_prev, loc_next);
   3.108 -    cx_linked_list_link(&a, &b, loc_prev, loc_next);
   3.109 -    cx_linked_list_unlink(&b, &c, loc_prev, loc_next);
   3.110 -    CU_ASSERT_PTR_NULL(a.prev)
   3.111 -    CU_ASSERT_PTR_EQUAL(a.next, &b)
   3.112 -    CU_ASSERT_PTR_EQUAL(b.prev, &a)
   3.113 -    CU_ASSERT_PTR_NULL(b.next)
   3.114 -    CU_ASSERT_PTR_NULL(c.prev)
   3.115 -    CU_ASSERT_PTR_NULL(c.next)
   3.116 -}
   3.117 -
   3.118 -void test_linked_list_at(void) {
   3.119 -    struct node nd(a), nd(b), nd(c), nd(d);
   3.120 -    cx_linked_list_link(&a, &b, loc_prev, loc_next);
   3.121 -    cx_linked_list_link(&b, &c, loc_prev, loc_next);
   3.122 -    cx_linked_list_link(&c, &d, loc_prev, loc_next);
   3.123 -
   3.124 -    CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&a, 0, loc_next, 0), &a)
   3.125 -    CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&a, 0, loc_next, 1), &b)
   3.126 -    CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&a, 0, loc_next, 2), &c)
   3.127 -    CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&a, 0, loc_next, 3), &d)
   3.128 -    CU_ASSERT_PTR_NULL(cx_linked_list_at(&a, 0, loc_next, 4))
   3.129 -
   3.130 -    CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&b, 1, loc_prev, 0), &a)
   3.131 -    CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&b, 1, loc_next, 1), &b)
   3.132 -    CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&b, 1, loc_next, 2), &c)
   3.133 -    CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&b, 1, loc_next, 3), &d)
   3.134 -    CU_ASSERT_PTR_NULL(cx_linked_list_at(&b, 1, loc_next, 4))
   3.135 -
   3.136 -    CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&d, 3, loc_prev, 0), &a)
   3.137 -    CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&d, 3, loc_prev, 1), &b)
   3.138 -}
   3.139 -
   3.140 -void test_linked_list_find(void) {
   3.141 -    int data[] = {2, 4, 6, 8};
   3.142 -    void *list = create_nodes_test_data(4, data);
   3.143 -    int s;
   3.144 -
   3.145 -    s = 2;
   3.146 -    CU_ASSERT_EQUAL(cx_linked_list_find(list, loc_next, loc_data,
   3.147 -                                        false, cmp_int, &s), 0)
   3.148 -    s = 4;
   3.149 -    CU_ASSERT_EQUAL(cx_linked_list_find(list, loc_next, loc_data,
   3.150 -                                        false, cmp_int, &s), 1)
   3.151 -    s = 6;
   3.152 -    CU_ASSERT_EQUAL(cx_linked_list_find(list, loc_next, loc_data,
   3.153 -                                        false, cmp_int, &s), 2)
   3.154 -    s = 8;
   3.155 -    CU_ASSERT_EQUAL(cx_linked_list_find(list, loc_next, loc_data,
   3.156 -                                        false, cmp_int, &s), 3)
   3.157 -    s = 10;
   3.158 -    CU_ASSERT_EQUAL(cx_linked_list_find(list, loc_next, loc_data,
   3.159 -                                        false, cmp_int, &s), 4)
   3.160 -    s = -2;
   3.161 -    CU_ASSERT_EQUAL(cx_linked_list_find(list, loc_next, loc_data,
   3.162 -                                        false, cmp_int, &s), 4)
   3.163 -}
   3.164 -
   3.165 -void test_linked_list_compare(void) {
   3.166 -    int a[] = {2, 4, 6, 8};
   3.167 -    int b[] = {2, 4, 6};
   3.168 -    int c[] = {2, 4, 6, 9};
   3.169 -
   3.170 -    void *la = create_nodes_test_data(4, a);
   3.171 -    void *lb = create_nodes_test_data(3, b);
   3.172 -    void *lc = create_nodes_test_data(4, c);
   3.173 -
   3.174 -    CU_ASSERT_TRUE(0 < cx_linked_list_compare(la, lb, loc_next, loc_data,
   3.175 -                                              false, cmp_int)
   3.176 -    )
   3.177 -    CU_ASSERT_TRUE(0 > cx_linked_list_compare(lb, la, loc_next, loc_data,
   3.178 -                                              false, cmp_int)
   3.179 -    )
   3.180 -    CU_ASSERT_TRUE(0 < cx_linked_list_compare(lc, la, loc_next, loc_data,
   3.181 -                                              false, cmp_int)
   3.182 -    )
   3.183 -    CU_ASSERT_TRUE(0 > cx_linked_list_compare(la, lc, loc_next, loc_data,
   3.184 -                                              false, cmp_int)
   3.185 -    )
   3.186 -    CU_ASSERT_TRUE(0 == cx_linked_list_compare(la, la, loc_next, loc_data,
   3.187 -                                               false, cmp_int)
   3.188 -    )
   3.189 -
   3.190 -    destroy_nodes_test_data(la);
   3.191 -    destroy_nodes_test_data(lb);
   3.192 -    destroy_nodes_test_data(lc);
   3.193 -}
   3.194 -
   3.195 -void test_linked_list_add(void) {
   3.196 -    struct node nodes[4];
   3.197 -    void *begin, *end;
   3.198 -
   3.199 -    // test with begin, end / prev, next
   3.200 -    memset(nodes, 0, 4 * sizeof(struct node));
   3.201 -    begin = end = NULL;
   3.202 -
   3.203 -    cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[0]);
   3.204 -    CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
   3.205 -    CU_ASSERT_PTR_EQUAL(end, &nodes[0])
   3.206 -    CU_ASSERT_PTR_NULL(nodes[0].prev)
   3.207 -    CU_ASSERT_PTR_NULL(nodes[0].next)
   3.208 -
   3.209 -    cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[1]);
   3.210 -    CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
   3.211 -    CU_ASSERT_PTR_EQUAL(end, &nodes[1])
   3.212 -    CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1])
   3.213 -    CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[0])
   3.214 -
   3.215 -    // test with begin only / prev, next
   3.216 -    memset(nodes, 0, 4 * sizeof(struct node));
   3.217 -    begin = end = NULL;
   3.218 -
   3.219 -    cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[0]);
   3.220 -    CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
   3.221 -    cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[1]);
   3.222 -    CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
   3.223 -    CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1])
   3.224 -    CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[0])
   3.225 -
   3.226 -    cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[2]);
   3.227 -    CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[2])
   3.228 -    CU_ASSERT_PTR_EQUAL(nodes[2].prev, &nodes[1])
   3.229 -
   3.230 -    // test with end only / prev, next
   3.231 -    memset(nodes, 0, 4 * sizeof(struct node));
   3.232 -    begin = end = NULL;
   3.233 -
   3.234 -    cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[0]);
   3.235 -    CU_ASSERT_PTR_EQUAL(end, &nodes[0])
   3.236 -    cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[1]);
   3.237 -    CU_ASSERT_PTR_EQUAL(end, &nodes[1])
   3.238 -    CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1])
   3.239 -    CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[0])
   3.240 -
   3.241 -    cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[2]);
   3.242 -    CU_ASSERT_PTR_EQUAL(end, &nodes[2])
   3.243 -    CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[2])
   3.244 -    CU_ASSERT_PTR_EQUAL(nodes[2].prev, &nodes[1])
   3.245 -
   3.246 -    // test with begin, end / next
   3.247 -    memset(nodes, 0, 4 * sizeof(struct node));
   3.248 -    begin = end = NULL;
   3.249 -
   3.250 -    cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[0]);
   3.251 -    CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
   3.252 -    CU_ASSERT_PTR_EQUAL(end, &nodes[0])
   3.253 -    cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[1]);
   3.254 -    CU_ASSERT_PTR_EQUAL(end, &nodes[1])
   3.255 -    CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1])
   3.256 -    CU_ASSERT_PTR_NULL(nodes[1].prev)
   3.257 -}
   3.258 -
   3.259 -void test_linked_list_prepend(void) {
   3.260 -    struct node nodes[4];
   3.261 -    void *begin, *end;
   3.262 -
   3.263 -    // test with begin, end / prev, next
   3.264 -    memset(nodes, 0, 4 * sizeof(struct node));
   3.265 -    begin = end = NULL;
   3.266 -
   3.267 -    cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[0]);
   3.268 -    CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
   3.269 -    CU_ASSERT_PTR_EQUAL(end, &nodes[0])
   3.270 -    CU_ASSERT_PTR_NULL(nodes[0].prev)
   3.271 -    CU_ASSERT_PTR_NULL(nodes[0].next)
   3.272 -
   3.273 -    cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[1]);
   3.274 -    CU_ASSERT_PTR_EQUAL(begin, &nodes[1])
   3.275 -    CU_ASSERT_PTR_EQUAL(end, &nodes[0])
   3.276 -    CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[0])
   3.277 -    CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[1])
   3.278 -
   3.279 -    // test with begin only / prev, next
   3.280 -    memset(nodes, 0, 4 * sizeof(struct node));
   3.281 -    begin = end = NULL;
   3.282 -
   3.283 -    cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[0]);
   3.284 -    CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
   3.285 -    cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[1]);
   3.286 -    CU_ASSERT_PTR_EQUAL(begin, &nodes[1])
   3.287 -    CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[0])
   3.288 -    CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[1])
   3.289 -
   3.290 -    cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[2]);
   3.291 -    CU_ASSERT_PTR_EQUAL(begin, &nodes[2])
   3.292 -    CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[1])
   3.293 -    CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[2])
   3.294 -
   3.295 -    // test with end only / prev, next
   3.296 -    memset(nodes, 0, 4 * sizeof(struct node));
   3.297 -    begin = end = NULL;
   3.298 -
   3.299 -    cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[0]);
   3.300 -    CU_ASSERT_PTR_EQUAL(end, &nodes[0])
   3.301 -    cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[1]);
   3.302 -    CU_ASSERT_PTR_EQUAL(end, &nodes[0])
   3.303 -    CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[0])
   3.304 -    CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[1])
   3.305 -
   3.306 -    cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[2]);
   3.307 -    CU_ASSERT_PTR_EQUAL(end, &nodes[0])
   3.308 -    CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[1])
   3.309 -    CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[2])
   3.310 -
   3.311 -    // test with begin, end / next
   3.312 -    memset(nodes, 0, 4 * sizeof(struct node));
   3.313 -    begin = end = NULL;
   3.314 -
   3.315 -    cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[0]);
   3.316 -    CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
   3.317 -    CU_ASSERT_PTR_EQUAL(end, &nodes[0])
   3.318 -    cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[1]);
   3.319 -    cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[2]);
   3.320 -    CU_ASSERT_PTR_EQUAL(begin, &nodes[2])
   3.321 -    CU_ASSERT_PTR_EQUAL(end, &nodes[0])
   3.322 -    CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[0])
   3.323 -    CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[1])
   3.324 -    CU_ASSERT_PTR_NULL(nodes[1].prev)
   3.325 -    CU_ASSERT_PTR_NULL(nodes[0].prev)
   3.326 -}
   3.327 -
   3.328 -void test_linked_list_insert(void) {
   3.329 -    struct node nodes[4];
   3.330 -    void *begin, *end;
   3.331 -
   3.332 -    // insert mid list
   3.333 -    memset(nodes, 0, 4 * sizeof(struct node));
   3.334 -    begin = &nodes[0];
   3.335 -    end = &nodes[2];
   3.336 -
   3.337 -    cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
   3.338 -    cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
   3.339 -
   3.340 -    cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3]);
   3.341 -    CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
   3.342 -    CU_ASSERT_PTR_EQUAL(end, &nodes[2])
   3.343 -    CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[3])
   3.344 -    CU_ASSERT_PTR_EQUAL(nodes[2].prev, &nodes[3])
   3.345 -    CU_ASSERT_PTR_EQUAL(nodes[3].prev, &nodes[1])
   3.346 -    CU_ASSERT_PTR_EQUAL(nodes[3].next, &nodes[2])
   3.347 -
   3.348 -    // insert end
   3.349 -    memset(nodes, 0, 4 * sizeof(struct node));
   3.350 -    begin = &nodes[0];
   3.351 -    end = &nodes[2];
   3.352 -
   3.353 -    cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
   3.354 -    cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
   3.355 -
   3.356 -    cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3]);
   3.357 -    CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
   3.358 -    CU_ASSERT_PTR_EQUAL(end, &nodes[3])
   3.359 -    CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[3])
   3.360 -    CU_ASSERT_PTR_EQUAL(nodes[3].prev, &nodes[2])
   3.361 -    CU_ASSERT_PTR_NULL(nodes[3].next)
   3.362 -
   3.363 -    // insert begin
   3.364 -    memset(nodes, 0, 4 * sizeof(struct node));
   3.365 -    begin = &nodes[0];
   3.366 -    end = &nodes[2];
   3.367 -
   3.368 -    cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
   3.369 -    cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
   3.370 -
   3.371 -    cx_linked_list_insert(&begin, &end, loc_prev, loc_next, NULL, &nodes[3]);
   3.372 -    CU_ASSERT_PTR_EQUAL(begin, &nodes[3])
   3.373 -    CU_ASSERT_PTR_EQUAL(end, &nodes[2])
   3.374 -    CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[3])
   3.375 -    CU_ASSERT_PTR_NULL(nodes[3].prev)
   3.376 -    CU_ASSERT_PTR_EQUAL(nodes[3].next, &nodes[0])
   3.377 -}
   3.378 -
   3.379 -void test_linked_list_insert_chain(void) {
   3.380 -    struct node nodes[5];
   3.381 -    void *begin, *end;
   3.382 -
   3.383 -    // insert mid list
   3.384 -    memset(nodes, 0, 5 * sizeof(struct node));
   3.385 -    begin = &nodes[0];
   3.386 -    end = &nodes[2];
   3.387 -
   3.388 -    cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
   3.389 -    cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
   3.390 -    cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next);
   3.391 -
   3.392 -    cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3], NULL);
   3.393 -    CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
   3.394 -    CU_ASSERT_PTR_EQUAL(end, &nodes[2])
   3.395 -    CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[3])
   3.396 -    CU_ASSERT_PTR_EQUAL(nodes[2].prev, &nodes[4])
   3.397 -    CU_ASSERT_PTR_EQUAL(nodes[3].prev, &nodes[1])
   3.398 -    CU_ASSERT_PTR_EQUAL(nodes[4].next, &nodes[2])
   3.399 -
   3.400 -    // insert end
   3.401 -    memset(nodes, 0, 5 * sizeof(struct node));
   3.402 -    begin = &nodes[0];
   3.403 -    end = &nodes[2];
   3.404 -
   3.405 -    cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
   3.406 -    cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
   3.407 -    cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next);
   3.408 -
   3.409 -    cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3], NULL);
   3.410 -    CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
   3.411 -    CU_ASSERT_PTR_EQUAL(end, &nodes[4])
   3.412 -    CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[3])
   3.413 -    CU_ASSERT_PTR_EQUAL(nodes[3].prev, &nodes[2])
   3.414 -    CU_ASSERT_PTR_NULL(nodes[4].next)
   3.415 -
   3.416 -    // insert begin
   3.417 -    memset(nodes, 0, 5 * sizeof(struct node));
   3.418 -    begin = &nodes[0];
   3.419 -    end = &nodes[2];
   3.420 -
   3.421 -    cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
   3.422 -    cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
   3.423 -    cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next);
   3.424 -
   3.425 -    cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, NULL, &nodes[3], NULL);
   3.426 -    CU_ASSERT_PTR_EQUAL(begin, &nodes[3])
   3.427 -    CU_ASSERT_PTR_EQUAL(end, &nodes[2])
   3.428 -    CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[4])
   3.429 -    CU_ASSERT_PTR_NULL(nodes[3].prev)
   3.430 -    CU_ASSERT_PTR_EQUAL(nodes[4].next, &nodes[0])
   3.431 -}
   3.432 -
   3.433 -void test_linked_list_first(void) {
   3.434 -    struct node *begin = create_nodes_test_data(3, NULL);
   3.435 -    CU_ASSERT_PTR_EQUAL(cx_linked_list_first(begin, loc_prev), begin)
   3.436 -    CU_ASSERT_PTR_EQUAL(cx_linked_list_first(begin->next, loc_prev), begin)
   3.437 -    CU_ASSERT_PTR_EQUAL(cx_linked_list_first(begin->next->next, loc_prev), begin)
   3.438 -    destroy_nodes_test_data(begin);
   3.439 -}
   3.440 -
   3.441 -void test_linked_list_last(void) {
   3.442 -    struct node *begin = create_nodes_test_data(3, NULL);
   3.443 -    struct node *end = begin->next->next;
   3.444 -    CU_ASSERT_PTR_EQUAL(cx_linked_list_last(begin, loc_next), end)
   3.445 -    CU_ASSERT_PTR_EQUAL(cx_linked_list_last(begin->next, loc_next), end)
   3.446 -    CU_ASSERT_PTR_EQUAL(cx_linked_list_last(begin->next->next, loc_next), end)
   3.447 -    destroy_nodes_test_data(begin);
   3.448 -}
   3.449 -
   3.450 -void test_linked_list_prev(void) {
   3.451 -    struct node *begin = create_nodes_test_data(3, NULL);
   3.452 -    CU_ASSERT_PTR_NULL(cx_linked_list_prev(begin, loc_next, begin))
   3.453 -    CU_ASSERT_PTR_EQUAL(cx_linked_list_prev(begin, loc_next, begin->next), begin)
   3.454 -    CU_ASSERT_PTR_EQUAL(cx_linked_list_prev(begin, loc_next, begin->next->next), begin->next)
   3.455 -    destroy_nodes_test_data(begin);
   3.456 -}
   3.457 -
   3.458 -void test_linked_list_remove(void) {
   3.459 -    void *begin, *end;
   3.460 -
   3.461 -    int data[] = {2, 4, 6};
   3.462 -    begin = create_nodes_test_data(3, data);
   3.463 -    struct node *first = begin;
   3.464 -    struct node *second = first->next;
   3.465 -    struct node *third = second->next;
   3.466 -    end = third;
   3.467 -
   3.468 -    cx_linked_list_remove(&begin, &end, loc_prev, loc_next, second);
   3.469 -    CU_ASSERT_PTR_EQUAL(begin, first)
   3.470 -    CU_ASSERT_PTR_EQUAL(end, third)
   3.471 -    CU_ASSERT_PTR_NULL(first->prev)
   3.472 -    CU_ASSERT_PTR_EQUAL(first->next, third)
   3.473 -    CU_ASSERT_PTR_EQUAL(third->prev, first)
   3.474 -    CU_ASSERT_PTR_NULL(third->next)
   3.475 -
   3.476 -    cx_linked_list_remove(&begin, &end, loc_prev, loc_next, third);
   3.477 -    CU_ASSERT_PTR_EQUAL(begin, first)
   3.478 -    CU_ASSERT_PTR_EQUAL(end, first)
   3.479 -    CU_ASSERT_PTR_NULL(first->prev)
   3.480 -    CU_ASSERT_PTR_NULL(first->next)
   3.481 -
   3.482 -    cx_linked_list_remove(&begin, &end, loc_prev, loc_next, first);
   3.483 -    CU_ASSERT_PTR_NULL(begin)
   3.484 -    CU_ASSERT_PTR_NULL(end)
   3.485 -
   3.486 -    free(first);
   3.487 -    free(second);
   3.488 -    free(third);
   3.489 -}
   3.490 -
   3.491 -void test_linked_list_size(void) {
   3.492 -    struct node *list;
   3.493 -
   3.494 -    CU_ASSERT_PTR_EQUAL(cx_linked_list_size(NULL, loc_next), 0)
   3.495 -
   3.496 -    list = create_nodes_test_data(5, NULL);
   3.497 -    CU_ASSERT_EQUAL(cx_linked_list_size(list, loc_next), 5)
   3.498 -    destroy_nodes_test_data(list);
   3.499 -
   3.500 -    list = create_nodes_test_data(13, NULL);
   3.501 -    CU_ASSERT_EQUAL(cx_linked_list_size(list, loc_next), 13)
   3.502 -    destroy_nodes_test_data(list);
   3.503 -}
   3.504 -
   3.505 -void test_linked_list_sort(void) {
   3.506 -    int expected[] = {
   3.507 -            14, 30, 151, 163, 227, 300, 315, 317, 363, 398, 417, 424, 438, 446, 508, 555, 605, 713, 716, 759, 761, 880,
   3.508 -            894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 1707, 1734, 1771, 1874, 1894,
   3.509 -            1976, 2079, 2124, 2130, 2135, 2266, 2338, 2358, 2430, 2500, 2540, 2542, 2546, 2711, 2733, 2754, 2764, 2797,
   3.510 -            2888, 2900, 3020, 3053, 3109, 3244, 3275, 3302, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 3675, 3677,
   3.511 -            3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681,
   3.512 -            4785, 4791, 4801, 4859, 4903, 4973
   3.513 -    };
   3.514 -    int scrambled[] = {
   3.515 -            759, 716, 880, 761, 2358, 2542, 2500, 2540, 2546, 2711, 2430, 1707, 1874, 1771, 1894, 1734, 1976, 2079,
   3.516 -            2124, 2130, 2135, 2266, 2338, 2733, 2754, 2764, 2797, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 2888,
   3.517 -            2900, 3020, 3053, 3109, 3244, 3275, 3302, 438, 446, 508, 555, 605, 713, 14, 30, 151, 163, 227, 300,
   3.518 -            894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 315, 317, 363, 398, 417, 424,
   3.519 -            3675, 3677, 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4785, 4791, 4801, 4859, 4903, 4973,
   3.520 -            4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681
   3.521 -    };
   3.522 -
   3.523 -    void *begin = create_nodes_test_data(100, scrambled);
   3.524 -    void *end = cx_linked_list_last(begin, loc_next);
   3.525 -
   3.526 -    cx_linked_list_sort(&begin, &end, loc_prev, loc_next, loc_data,
   3.527 -                        false, cmp_int);
   3.528 -
   3.529 -    struct node *check = begin;
   3.530 -    struct node *check_last = NULL;
   3.531 -    CU_ASSERT_PTR_NULL(check->prev)
   3.532 -    CU_ASSERT_EQUAL(check->data, expected[0])
   3.533 -    cx_for_n (i, 100) {
   3.534 -        CU_ASSERT_EQUAL(check->data, expected[i])
   3.535 -        CU_ASSERT_PTR_EQUAL(check->prev, check_last)
   3.536 -        if (i < 99) {
   3.537 -            CU_ASSERT_PTR_NOT_NULL(check->next)
   3.538 -        }
   3.539 -        check_last = check;
   3.540 -        check = check->next;
   3.541 -    }
   3.542 -    CU_ASSERT_PTR_NULL(check)
   3.543 -    CU_ASSERT_PTR_EQUAL(end, check_last)
   3.544 -
   3.545 -    destroy_nodes_test_data(begin);
   3.546 -}
   3.547 -
   3.548 -void test_linked_list_reverse(void) {
   3.549 -    void *begin, *end;
   3.550 -
   3.551 -    int data[] = {2, 4, 6, 8};
   3.552 -    int reversed[] = {8, 6, 4, 2};
   3.553 -
   3.554 -    void *list = create_nodes_test_data(4, data);
   3.555 -    void *expected = create_nodes_test_data(4, reversed);
   3.556 -
   3.557 -    begin = list;
   3.558 -    end = cx_linked_list_last(list, loc_next);
   3.559 -
   3.560 -    cx_linked_list_reverse(&begin, &end, loc_prev, loc_next);
   3.561 -    CU_ASSERT_PTR_EQUAL(end, list)
   3.562 -    CU_ASSERT_PTR_EQUAL(begin, cx_linked_list_first(end, loc_prev))
   3.563 -    CU_ASSERT_TRUE(0 == cx_linked_list_compare(begin, expected, loc_next, loc_data,
   3.564 -                                               0, cmp_int))
   3.565 -
   3.566 -    destroy_nodes_test_data(begin);
   3.567 -    destroy_nodes_test_data(expected);
   3.568 -}
   3.569 -
   3.570 -static void verify_linked_list_create(CxList *list) {
   3.571 -    CU_ASSERT_EQUAL(list->size, 0)
   3.572 -    CU_ASSERT_EQUAL(list->capacity, (size_t) -1)
   3.573 -    CU_ASSERT_PTR_EQUAL(list->allocator, cxTestingAllocator)
   3.574 -    CU_ASSERT_PTR_EQUAL(list->cmpfunc, cmp_int)
   3.575 -
   3.576 -    cxListDestroy(list);
   3.577 -}
   3.578 -
   3.579 -void test_hl_linked_list_create(void) {
   3.580 -    CxList *list = cxLinkedListCreate(cxTestingAllocator, cmp_int, sizeof(int));
   3.581 -    CU_ASSERT_EQUAL(list->itemsize, sizeof(int))
   3.582 -    verify_linked_list_create(list);
   3.583 -}
   3.584 -
   3.585 -void test_hl_ptr_linked_list_create(void) {
   3.586 -    CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int);
   3.587 -    CU_ASSERT_EQUAL(list->itemsize, sizeof(void *))
   3.588 -    verify_linked_list_create(list);
   3.589 -}
   3.590 -
   3.591 -void test_hl_linked_list_from_array(void) {
   3.592 -    int data[] = {2, 4, 5, 7, 10, 15};
   3.593 -
   3.594 -    CxList *expected = cxLinkedListCreate(cxTestingAllocator, cmp_int, sizeof(int));
   3.595 -    cx_for_n (i, 5) cxListAdd(expected, &data[i]);
   3.596 -
   3.597 -    CxList *list = cxLinkedListFromArray(cxTestingAllocator, cmp_int, sizeof(int), 5, data);
   3.598 -
   3.599 -    CU_ASSERT_TRUE(0 == cxListCompare(list, expected))
   3.600 -
   3.601 -    cxListDestroy(list);
   3.602 -    cxListDestroy(expected);
   3.603 -}
   3.604 -
   3.605 -static void verify_hl_linked_list_add(
   3.606 -        CxList *list,
   3.607 -        int data[],
   3.608 -        size_t len,
   3.609 -        bool write_through
   3.610 -) {
   3.611 -    cx_for_n (i, len) CU_ASSERT_EQUAL(cxListAdd(list, &data[i]), 0)
   3.612 -    CU_ASSERT_EQUAL(list->size, len)
   3.613 -    CU_ASSERT_TRUE(list->capacity >= list->size)
   3.614 -    cx_for_n (i, len) CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), data[i])
   3.615 -    cx_for_n (i, len) ++data[i];
   3.616 -    if (write_through) {
   3.617 -        cx_for_n (i, len) CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), data[i])
   3.618 -    } else {
   3.619 -        cx_for_n (i, len) CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), data[i] - 1)
   3.620 -    }
   3.621 -    cxListDestroy(list);
   3.622 -}
   3.623 -
   3.624 -void test_hl_linked_list_add(void) {
   3.625 -    CxList *list = cxLinkedListCreate(cxTestingAllocator, cmp_int, sizeof(int));
   3.626 -    int data[] = {5, 47, 13, 9, 18, 1, 42};
   3.627 -    verify_hl_linked_list_add(list, data, sizeof(data) / sizeof(int), false);
   3.628 -}
   3.629 -
   3.630 -void test_hl_ptr_linked_list_add(void) {
   3.631 -    CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int);
   3.632 -    int data[] = {5, 47, 84, 13, 9, 18, 90, 1, 42};
   3.633 -    verify_hl_linked_list_add(list, data, sizeof(data) / sizeof(int), true);
   3.634 -}
   3.635 -
   3.636 -static void verify_hl_linked_list_insert(CxList *list) {
   3.637 -    int a = 5, b = 47, c = 13, d = 42;
   3.638 -
   3.639 -    CU_ASSERT_NOT_EQUAL(cxListInsert(list, 1, &a), 0)
   3.640 -    CU_ASSERT_EQUAL(list->size, 0)
   3.641 -    CU_ASSERT_EQUAL(cxListInsert(list, 0, &a), 0)
   3.642 -    CU_ASSERT_EQUAL(list->size, 1)
   3.643 -    CU_ASSERT_EQUAL(cxListInsert(list, 0, &b), 0)
   3.644 -    CU_ASSERT_EQUAL(list->size, 2)
   3.645 -    CU_ASSERT_EQUAL(cxListInsert(list, 1, &c), 0)
   3.646 -    CU_ASSERT_EQUAL(list->size, 3)
   3.647 -    CU_ASSERT_EQUAL(cxListInsert(list, 3, &d), 0)
   3.648 -
   3.649 -    CU_ASSERT_EQUAL(list->size, 4)
   3.650 -    CU_ASSERT_TRUE(list->capacity >= list->size)
   3.651 -
   3.652 -    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
   3.653 -    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
   3.654 -    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 5)
   3.655 -    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 3), 42)
   3.656 -
   3.657 -    cxListDestroy(list);
   3.658 -}
   3.659 -
   3.660 -void test_hl_linked_list_insert(void) {
   3.661 -    verify_hl_linked_list_insert(cxLinkedListCreate(cxTestingAllocator, cmp_int, sizeof(int)));
   3.662 -}
   3.663 -
   3.664 -void test_hl_ptr_linked_list_insert(void) {
   3.665 -    verify_hl_linked_list_insert(cxPointerLinkedListCreate(cxTestingAllocator, cmp_int));
   3.666 -}
   3.667 -
   3.668 -static void verify_hl_linked_list_remove(CxList *list) {
   3.669 -    CU_ASSERT_EQUAL(list->size, 4)
   3.670 -    CU_ASSERT_TRUE(list->capacity >= list->size)
   3.671 -
   3.672 -    CU_ASSERT_NOT_EQUAL(cxListRemove(list, 4), 0)
   3.673 -
   3.674 -    CU_ASSERT_EQUAL(cxListRemove(list, 2), 0)
   3.675 -    CU_ASSERT_EQUAL(list->size, 3)
   3.676 -    CU_ASSERT_TRUE(list->capacity >= list->size)
   3.677 -    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
   3.678 -    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
   3.679 -    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
   3.680 -
   3.681 -    CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
   3.682 -    CU_ASSERT_EQUAL(list->size, 2)
   3.683 -    CU_ASSERT_TRUE(list->capacity >= list->size)
   3.684 -    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
   3.685 -    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
   3.686 -
   3.687 -    CU_ASSERT_EQUAL(cxListRemove(list, 1), 0)
   3.688 -    CU_ASSERT_EQUAL(list->size, 1)
   3.689 -    CU_ASSERT_TRUE(list->capacity >= list->size)
   3.690 -    CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
   3.691 -
   3.692 -    CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
   3.693 -    CU_ASSERT_EQUAL(list->size, 0)
   3.694 -    CU_ASSERT_TRUE(list->capacity >= list->size)
   3.695 -
   3.696 -    CU_ASSERT_NOT_EQUAL(cxListRemove(list, 0), 0)
   3.697 -
   3.698 -    cxListDestroy(list);
   3.699 -}
   3.700 -
   3.701 -void test_hl_linked_list_remove(void) {
   3.702 -    int data[] = {5, 47, 42, 13};
   3.703 -    CxList *list = cxLinkedListFromArray(cxTestingAllocator, cmp_int,
   3.704 -                                         sizeof(int), 4, data);
   3.705 -    verify_hl_linked_list_remove(list);
   3.706 -}
   3.707 -
   3.708 -void test_hl_ptr_linked_list_remove(void) {
   3.709 -    int a = 5, b = 47, c = 42, d = 13;
   3.710 -    CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int);
   3.711 -    cxListAdd(list, &a);
   3.712 -    cxListAdd(list, &b);
   3.713 -    cxListAdd(list, &c);
   3.714 -    cxListAdd(list, &d);
   3.715 -    verify_hl_linked_list_remove(list);
   3.716 -}
   3.717 -
   3.718 -static void verify_hl_linked_list_at(
   3.719 -        CxList *list,
   3.720 -        size_t len,
   3.721 -        int *data
   3.722 -) {
   3.723 -    CU_ASSERT_EQUAL(list->size, len)
   3.724 -    cx_for_n (i, len) CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), data[i])
   3.725 -    CU_ASSERT_PTR_NULL(cxListAt(list, len))
   3.726 -    free(data);
   3.727 -    cxListDestroy(list);
   3.728 -}
   3.729 -
   3.730 -void test_hl_linked_list_at(void) {
   3.731 -    size_t len = 100;
   3.732 -    int *data = create_ints_test_data(len);
   3.733 -    CxList *list = cxLinkedListFromArray(cxTestingAllocator, cmp_int,
   3.734 -                                         sizeof(int), len, data);
   3.735 -    verify_hl_linked_list_at(list, len, data);
   3.736 -}
   3.737 -
   3.738 -void test_hl_ptr_linked_list_at(void) {
   3.739 -    size_t len = 250;
   3.740 -    int *data = create_ints_test_data(len);
   3.741 -    CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int);
   3.742 -    cx_for_n (i, len) cxListAdd(list, &data[i]);
   3.743 -    verify_hl_linked_list_at(list, len, data);
   3.744 -}
   3.745 -
   3.746 -static void verify_hl_linked_list_find(
   3.747 -        CxList *list,
   3.748 -        size_t len,
   3.749 -        int *data
   3.750 -) {
   3.751 -    cx_for_n (attempt, 100) {
   3.752 -        size_t exp = rand() % len; // NOLINT(cert-msc50-cpp)
   3.753 -        int val = data[exp];
   3.754 -        cx_for_n (i, exp) {
   3.755 -            if (data[i] == val) {
   3.756 -                exp = i;
   3.757 -                break;
   3.758 -            }
   3.759 -        }
   3.760 -        CU_ASSERT_EQUAL(cxListFind(list, &val), exp)
   3.761 -    }
   3.762 -    free(data);
   3.763 -    cxListDestroy(list);
   3.764 -}
   3.765 -
   3.766 -void test_hl_linked_list_find(void) {
   3.767 -    size_t len = 100;
   3.768 -    int *data = create_ints_test_data(len);
   3.769 -    CxList *list = cxLinkedListFromArray(cxTestingAllocator, cmp_int, sizeof(int), len, data);
   3.770 -    verify_hl_linked_list_find(list, len, data);
   3.771 -}
   3.772 -
   3.773 -void test_hl_ptr_linked_list_find(void) {
   3.774 -    size_t len = 250;
   3.775 -    int *data = create_ints_test_data(len);
   3.776 -    CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int);
   3.777 -    cx_for_n (i, len) cxListAdd(list, &data[i]);
   3.778 -    verify_hl_linked_list_find(list, len, data);
   3.779 -}
   3.780 -
   3.781 -struct sort_test_data {
   3.782 -    size_t len;
   3.783 -    int *data;
   3.784 -    int *sorted;
   3.785 -};
   3.786 -
   3.787 -static struct sort_test_data create_sort_test_data(void) {
   3.788 -    size_t len = 1000;
   3.789 -    int *data = create_ints_test_data(len);
   3.790 -    int *sorted = malloc(sizeof(int) * len);
   3.791 -    memcpy(sorted, data, sizeof(int) * len);
   3.792 -    qsort(sorted, len, sizeof(int), cmp_int);
   3.793 -    struct sort_test_data s = {len, data, sorted};
   3.794 -    return s;
   3.795 -}
   3.796 -
   3.797 -static void free_sort_test_data(struct sort_test_data s) {
   3.798 -    free(s.data);
   3.799 -    free(s.sorted);
   3.800 -}
   3.801 -
   3.802 -static void verify_hl_linked_list_sort(
   3.803 -        CxList *list,
   3.804 -        struct sort_test_data td
   3.805 -) {
   3.806 -    cxListSort(list);
   3.807 -    cx_for_n (i, td.len) CU_ASSERT_EQUAL_FATAL(*(int *) cxListAt(list, i), td.sorted[i])
   3.808 -    free_sort_test_data(td);
   3.809 -    cxListDestroy(list);
   3.810 -}
   3.811 -
   3.812 -void test_hl_linked_list_sort(void) {
   3.813 -    struct sort_test_data td = create_sort_test_data();
   3.814 -    CxList *list = cxLinkedListFromArray(cxTestingAllocator, cmp_int, sizeof(int), td.len, td.data);
   3.815 -    verify_hl_linked_list_sort(list, td);
   3.816 -}
   3.817 -
   3.818 -void test_hl_ptr_linked_list_sort(void) {
   3.819 -    struct sort_test_data td = create_sort_test_data();
   3.820 -    CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int);
   3.821 -    cx_for_n (i, td.len) cxListAdd(list, &td.data[i]);
   3.822 -    verify_hl_linked_list_sort(list, td);
   3.823 -}
   3.824 -
   3.825 -void verify_hl_linked_list_iterator(CxList *list) {
   3.826 -    int i = 0;
   3.827 -    CxIterator iter = cxListBegin(list);
   3.828 -    cx_foreach(int*, x, iter) {
   3.829 -        CU_ASSERT_EQUAL(iter.index, (size_t) (i + 1) / 2)
   3.830 -        CU_ASSERT_EQUAL(*x, i)
   3.831 -        if (*x % 2 == 1) iter.remove = true;
   3.832 -        i++;
   3.833 -    }
   3.834 -    CU_ASSERT_EQUAL(i, 10)
   3.835 -    CU_ASSERT_EQUAL_FATAL(list->size, 5)
   3.836 -    cx_for_n(j, 5) CU_ASSERT_EQUAL(*(int *) cxListAt(list, j), (int) j * 2)
   3.837 -    cxListDestroy(list);
   3.838 -}
   3.839 -
   3.840 -void test_hl_linked_list_iterator(void) {
   3.841 -    CxList *list = cxLinkedListCreate(cxTestingAllocator, cmp_int, sizeof(int));
   3.842 -    cx_for_n (i, 10) cxListAdd(list, &i);
   3.843 -    verify_hl_linked_list_iterator(list);
   3.844 -}
   3.845 -
   3.846 -void test_hl_ptr_linked_list_iterator(void) {
   3.847 -    CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int);
   3.848 -    int data[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
   3.849 -    cx_for_n (i, 10) cxListAdd(list, &data[i]);
   3.850 -    verify_hl_linked_list_iterator(list);
   3.851 -}
   3.852 -
   3.853 -static void verify_hl_linked_list_insert_via_iterator(
   3.854 -        CxList *list,
   3.855 -        int *testdata
   3.856 -) {
   3.857 -    CxIterator iter = cxListIterator(list, 2);
   3.858 -    CU_ASSERT_EQUAL(iter.index, 2)
   3.859 -    CU_ASSERT_EQUAL(*(int *) cxIteratorCurrent(&iter), 2)
   3.860 -    size_t i = 4;
   3.861 -
   3.862 -    ++i;
   3.863 -    cxListInsertAfter(&iter, &testdata[i]);
   3.864 -    CU_ASSERT_EQUAL(iter.index, 2)
   3.865 -    CU_ASSERT_EQUAL(*(int *) cxIteratorCurrent(&iter), 2)
   3.866 -    ++i;
   3.867 -    cxListInsertBefore(&iter, &testdata[i]);
   3.868 -    CU_ASSERT_EQUAL(iter.index, 3)
   3.869 -    CU_ASSERT_EQUAL(*(int *) cxIteratorCurrent(&iter), 2)
   3.870 -
   3.871 -    iter = cxListBegin(list);
   3.872 -    ++i;
   3.873 -    cxListInsertBefore(&iter, &testdata[i]);
   3.874 -    CU_ASSERT_EQUAL(iter.index, 1)
   3.875 -    CU_ASSERT_EQUAL(*(int *) cxIteratorCurrent(&iter), 0)
   3.876 -    iter = cxListIterator(list, list->size);
   3.877 -    ++i;
   3.878 -    cxListInsertBefore(&iter, &testdata[i]);
   3.879 -    CU_ASSERT_EQUAL(iter.index, 9)
   3.880 -    CU_ASSERT_FALSE(cxIteratorValid(&iter))
   3.881 -    iter = cxListIterator(list, list->size);
   3.882 -    ++i;
   3.883 -    cxListInsertAfter(&iter, &testdata[i]);
   3.884 -    CU_ASSERT_EQUAL(iter.index, 10)
   3.885 -    CU_ASSERT_FALSE(cxIteratorValid(&iter))
   3.886 -
   3.887 -    int expdata[] = {30, 0, 1, 20, 2, 10, 3, 4, 40, 50};
   3.888 -    cx_for_n (j, 10) CU_ASSERT_EQUAL(*(int *) cxListAt(list, j), expdata[j])
   3.889 -    cxListDestroy(list);
   3.890 -}
   3.891 -
   3.892 -void test_hl_linked_list_insert_via_iterator(void) {
   3.893 -    int testdata[] = {0, 1, 2, 3, 4, 10, 20, 30, 40, 50};
   3.894 -    // only add the first five elements, the remaining five will be inserted
   3.895 -    CxList *list = cxLinkedListFromArray(cxTestingAllocator, cmp_int, sizeof(int), 5, testdata);
   3.896 -    verify_hl_linked_list_insert_via_iterator(list, testdata);
   3.897 -}
   3.898 -
   3.899 -void test_hl_ptr_linked_list_insert_via_iterator(void) {
   3.900 -    int testdata[] = {0, 1, 2, 3, 4, 10, 20, 30, 40, 50};
   3.901 -    CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int);
   3.902 -    // only add the first five elements, the remaining five will be inserted
   3.903 -    cx_for_n (i, 5) cxListAdd(list, &testdata[i]);
   3.904 -    verify_hl_linked_list_insert_via_iterator(list, testdata);
   3.905 -}
   3.906 -
   3.907 -static void test_setup_allocator(void) {
   3.908 -    cxTestingAllocatorReset();
   3.909 -}
   3.910 -
   3.911 -static void test_verify_allocator(void) {
   3.912 -    CU_ASSERT_TRUE(cxTestingAllocatorVerify())
   3.913 -}
   3.914 -
   3.915 -int main() {
   3.916 -    CU_pSuite suite = NULL;
   3.917 -
   3.918 -    if (CUE_SUCCESS != CU_initialize_registry()) {
   3.919 -        return CU_get_error();
   3.920 -    }
   3.921 -
   3.922 -    suite = CU_add_suite("low level linked list", NULL, NULL);
   3.923 -
   3.924 -    cu_add_test(suite, test_linked_list_link_unlink);
   3.925 -    cu_add_test(suite, test_linked_list_at);
   3.926 -    cu_add_test(suite, test_linked_list_find);
   3.927 -    cu_add_test(suite, test_linked_list_compare);
   3.928 -    cu_add_test(suite, test_linked_list_prepend);
   3.929 -    cu_add_test(suite, test_linked_list_add);
   3.930 -    cu_add_test(suite, test_linked_list_insert);
   3.931 -    cu_add_test(suite, test_linked_list_insert_chain);
   3.932 -    cu_add_test(suite, test_linked_list_first);
   3.933 -    cu_add_test(suite, test_linked_list_last);
   3.934 -    cu_add_test(suite, test_linked_list_prev);
   3.935 -    cu_add_test(suite, test_linked_list_remove);
   3.936 -    cu_add_test(suite, test_linked_list_size);
   3.937 -    cu_add_test(suite, test_linked_list_sort);
   3.938 -    cu_add_test(suite, test_linked_list_reverse);
   3.939 -
   3.940 -    suite = CU_add_suite_with_setup_and_teardown(
   3.941 -            "high level linked list", NULL, NULL,
   3.942 -            test_setup_allocator, test_verify_allocator);
   3.943 -
   3.944 -    cu_add_test(suite, test_hl_linked_list_create);
   3.945 -    cu_add_test(suite, test_hl_linked_list_from_array);
   3.946 -    cu_add_test(suite, test_hl_linked_list_add);
   3.947 -    cu_add_test(suite, test_hl_linked_list_insert);
   3.948 -    cu_add_test(suite, test_hl_linked_list_remove);
   3.949 -    cu_add_test(suite, test_hl_linked_list_at);
   3.950 -    cu_add_test(suite, test_hl_linked_list_find);
   3.951 -    cu_add_test(suite, test_hl_linked_list_sort);
   3.952 -    cu_add_test(suite, test_hl_linked_list_iterator);
   3.953 -    cu_add_test(suite, test_hl_linked_list_insert_via_iterator);
   3.954 -
   3.955 -    suite = CU_add_suite_with_setup_and_teardown(
   3.956 -            "high level pointer linked list", NULL, NULL,
   3.957 -            test_setup_allocator, test_verify_allocator);
   3.958 -
   3.959 -    cu_add_test(suite, test_hl_ptr_linked_list_create);
   3.960 -    cu_add_test(suite, test_hl_ptr_linked_list_add);
   3.961 -    cu_add_test(suite, test_hl_ptr_linked_list_insert);
   3.962 -    cu_add_test(suite, test_hl_ptr_linked_list_remove);
   3.963 -    cu_add_test(suite, test_hl_ptr_linked_list_at);
   3.964 -    cu_add_test(suite, test_hl_ptr_linked_list_find);
   3.965 -    cu_add_test(suite, test_hl_ptr_linked_list_sort);
   3.966 -    cu_add_test(suite, test_hl_ptr_linked_list_iterator);
   3.967 -    cu_add_test(suite, test_hl_ptr_linked_list_insert_via_iterator);
   3.968 -
   3.969 -    CU_basic_set_mode(UCX_CU_BRM);
   3.970 -
   3.971 -    int exitcode;
   3.972 -    if (CU_basic_run_tests()) {
   3.973 -        exitcode = CU_get_error();
   3.974 -    } else {
   3.975 -        exitcode = CU_get_number_of_failures() == 0 ? 0 : 1;
   3.976 -    }
   3.977 -    CU_cleanup_registry();
   3.978 -    return exitcode;
   3.979 -}

     4.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     4.2 +++ b/test/test_list.cpp	Sat Apr 16 18:02:10 2022 +0200
     4.3 @@ -0,0 +1,827 @@
     4.4 +/*
     4.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
     4.6 + *
     4.7 + * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
     4.8 + *
     4.9 + * Redistribution and use in source and binary forms, with or without
    4.10 + * modification, are permitted provided that the following conditions are met:
    4.11 + *
    4.12 + *   1. Redistributions of source code must retain the above copyright
    4.13 + *      notice, this list of conditions and the following disclaimer.
    4.14 + *
    4.15 + *   2. Redistributions in binary form must reproduce the above copyright
    4.16 + *      notice, this list of conditions and the following disclaimer in the
    4.17 + *      documentation and/or other materials provided with the distribution.
    4.18 + *
    4.19 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
    4.20 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    4.21 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
    4.22 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
    4.23 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
    4.24 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
    4.25 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
    4.26 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
    4.27 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
    4.28 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
    4.29 + * POSSIBILITY OF SUCH DAMAGE.
    4.30 + */
    4.31 +
    4.32 +#include "cx/linked_list.h"
    4.33 +#include "cx/utils.h"
    4.34 +#include "util_allocator.h"
    4.35 +
    4.36 +#include <gtest/gtest.h>
    4.37 +#include <array>
    4.38 +#include <vector>
    4.39 +#include <unordered_set>
    4.40 +#include <algorithm>
    4.41 +
    4.42 +static int cmp_int_impl(
    4.43 +        int const *l,
    4.44 +        int const *r
    4.45 +) {
    4.46 +    int left = *l, right = *r;
    4.47 +    return left == right ? 0 : (left < right ? -1 : 1);
    4.48 +}
    4.49 +
    4.50 +#define cmp_int ((CxListComparator) cmp_int_impl)
    4.51 +
    4.52 +struct node {
    4.53 +    node *next = nullptr;
    4.54 +    node *prev = nullptr;
    4.55 +    int data = 0;
    4.56 +};
    4.57 +
    4.58 +const ptrdiff_t loc_prev = offsetof(struct node, prev);
    4.59 +const ptrdiff_t loc_next = offsetof(struct node, next);
    4.60 +const ptrdiff_t loc_data = offsetof(struct node, data);
    4.61 +
    4.62 +struct node_test_data {
    4.63 +    node *begin;
    4.64 +
    4.65 +    explicit node_test_data(node *begin) : begin(begin) {}
    4.66 +    node_test_data(node_test_data&) = delete;
    4.67 +    node_test_data(node_test_data&&) = default;
    4.68 +
    4.69 +    ~node_test_data() {
    4.70 +        auto n = begin;
    4.71 +        while (n != nullptr) {
    4.72 +            auto next = n->next;
    4.73 +            delete n;
    4.74 +            n = next;
    4.75 +        }
    4.76 +    }
    4.77 +};
    4.78 +
    4.79 +static node_test_data create_nodes_test_data(size_t len) {
    4.80 +    if (len == 0) return node_test_data{nullptr};
    4.81 +    auto begin = new node;
    4.82 +    auto prev = begin;
    4.83 +    for (size_t i = 1; i < len; i++) {
    4.84 +        auto n = new node;
    4.85 +        cx_linked_list_link(prev, n, loc_prev, loc_next);
    4.86 +        prev = n;
    4.87 +    }
    4.88 +    return node_test_data{begin};
    4.89 +}
    4.90 +
    4.91 +template<typename InputIter>
    4.92 +static node_test_data create_nodes_test_data(InputIter begin, InputIter end) {
    4.93 +    if (begin == end) return node_test_data{nullptr};
    4.94 +    node *first = new node;
    4.95 +    first->data = *begin;
    4.96 +    node *prev = first;
    4.97 +    begin++;
    4.98 +    for (; begin != end; begin++) {
    4.99 +        auto n = new node;
   4.100 +        n->data = *begin;
   4.101 +        cx_linked_list_link(prev, n, loc_prev, loc_next);
   4.102 +        prev = n;
   4.103 +    }
   4.104 +    return node_test_data{first};
   4.105 +}
   4.106 +
   4.107 +static node_test_data create_nodes_test_data(std::initializer_list<int> data) {
   4.108 +    return create_nodes_test_data(data.begin(), data.end());
   4.109 +}
   4.110 +
   4.111 +template<size_t N>
   4.112 +struct int_test_data {
   4.113 +    std::array<int, N> data;
   4.114 +
   4.115 +    int_test_data() {
   4.116 +        cx_for_n (i, N) data[i] = ::rand(); // NOLINT(cert-msc50-cpp)
   4.117 +    }
   4.118 +};
   4.119 +
   4.120 +TEST(LinkedList_LowLevel, link_unlink) {
   4.121 +    node a, b, c;
   4.122 +
   4.123 +    cx_linked_list_link(&a, &b, loc_prev, loc_next);
   4.124 +    EXPECT_EQ(a.prev, nullptr);
   4.125 +    EXPECT_EQ(a.next, &b);
   4.126 +    EXPECT_EQ(b.prev, &a);
   4.127 +    EXPECT_EQ(b.next, nullptr);
   4.128 +
   4.129 +    cx_linked_list_unlink(&a, &b, loc_prev, loc_next);
   4.130 +    EXPECT_EQ(a.prev, nullptr);
   4.131 +    EXPECT_EQ(a.next, nullptr);
   4.132 +    EXPECT_EQ(b.prev, nullptr);
   4.133 +    EXPECT_EQ(b.next, nullptr);
   4.134 +
   4.135 +    cx_linked_list_link(&b, &c, loc_prev, loc_next);
   4.136 +    cx_linked_list_link(&a, &b, loc_prev, loc_next);
   4.137 +    cx_linked_list_unlink(&b, &c, loc_prev, loc_next);
   4.138 +    EXPECT_EQ(a.prev, nullptr);
   4.139 +    EXPECT_EQ(a.next, &b);
   4.140 +    EXPECT_EQ(b.prev, &a);
   4.141 +    EXPECT_EQ(b.next, nullptr);
   4.142 +    EXPECT_EQ(c.prev, nullptr);
   4.143 +    EXPECT_EQ(c.next, nullptr);
   4.144 +}
   4.145 +
   4.146 +TEST(LinkedList_LowLevel, cx_linked_list_at) {
   4.147 +    node a, b, c, d;
   4.148 +    cx_linked_list_link(&a, &b, loc_prev, loc_next);
   4.149 +    cx_linked_list_link(&b, &c, loc_prev, loc_next);
   4.150 +    cx_linked_list_link(&c, &d, loc_prev, loc_next);
   4.151 +
   4.152 +    EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 0), &a);
   4.153 +    EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 1), &b);
   4.154 +    EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 2), &c);
   4.155 +    EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 3), &d);
   4.156 +    EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 4), nullptr);
   4.157 +
   4.158 +    EXPECT_EQ(cx_linked_list_at(&b, 1, loc_prev, 0), &a);
   4.159 +    EXPECT_EQ(cx_linked_list_at(&b, 1, loc_next, 1), &b);
   4.160 +    EXPECT_EQ(cx_linked_list_at(&b, 1, loc_next, 2), &c);
   4.161 +    EXPECT_EQ(cx_linked_list_at(&b, 1, loc_next, 3), &d);
   4.162 +    EXPECT_EQ(cx_linked_list_at(&b, 1, loc_next, 4), nullptr);
   4.163 +
   4.164 +    EXPECT_EQ(cx_linked_list_at(&d, 3, loc_prev, 0), &a);
   4.165 +    EXPECT_EQ(cx_linked_list_at(&d, 3, loc_prev, 1), &b);
   4.166 +}
   4.167 +
   4.168 +TEST(LinkedList_LowLevel, cx_linked_list_find) {
   4.169 +    auto testdata = create_nodes_test_data({2, 4, 6, 8});
   4.170 +    auto list = testdata.begin;
   4.171 +    int s;
   4.172 +
   4.173 +    s = 2;
   4.174 +    EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, false, cmp_int, &s), 0);
   4.175 +    s = 4;
   4.176 +    EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, false, cmp_int, &s), 1);
   4.177 +    s = 6;
   4.178 +    EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, false, cmp_int, &s), 2);
   4.179 +    s = 8;
   4.180 +    EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, false, cmp_int, &s), 3);
   4.181 +    s = 10;
   4.182 +    EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, false, cmp_int, &s), 4);
   4.183 +    s = -2;
   4.184 +    EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, false, cmp_int, &s), 4);
   4.185 +}
   4.186 +
   4.187 +TEST(LinkedList_LowLevel, cx_linked_list_compare) {
   4.188 +    auto ta = create_nodes_test_data({2, 4, 6, 8});
   4.189 +    auto tb = create_nodes_test_data({2, 4, 6});
   4.190 +    auto tc = create_nodes_test_data({2, 4, 6, 9});
   4.191 +    auto la = ta.begin, lb = tb.begin, lc = tc.begin;
   4.192 +
   4.193 +    EXPECT_GT(cx_linked_list_compare(la, lb, loc_next, loc_data, false, cmp_int), 0);
   4.194 +    EXPECT_LT(cx_linked_list_compare(lb, la, loc_next, loc_data, false, cmp_int), 0);
   4.195 +    EXPECT_GT(cx_linked_list_compare(lc, la, loc_next, loc_data, false, cmp_int), 0);
   4.196 +    EXPECT_LT(cx_linked_list_compare(la, lc, loc_next, loc_data, false, cmp_int), 0);
   4.197 +    EXPECT_EQ(cx_linked_list_compare(la, la, loc_next, loc_data, false, cmp_int), 0);
   4.198 +}
   4.199 +
   4.200 +TEST(LinkedList_LowLevel, cx_linked_list_add) {
   4.201 +    // test with begin, end / prev, next
   4.202 +    {
   4.203 +        node nodes[4];
   4.204 +        void *begin = nullptr, *end = nullptr;
   4.205 +
   4.206 +        cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[0]);
   4.207 +        EXPECT_EQ(begin, &nodes[0]);
   4.208 +        EXPECT_EQ(end, &nodes[0]);
   4.209 +        EXPECT_EQ(nodes[0].prev, nullptr);
   4.210 +        EXPECT_EQ(nodes[0].next, nullptr);
   4.211 +
   4.212 +        cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[1]);
   4.213 +        EXPECT_EQ(begin, &nodes[0]);
   4.214 +        EXPECT_EQ(end, &nodes[1]);
   4.215 +        EXPECT_EQ(nodes[0].next, &nodes[1]);
   4.216 +        EXPECT_EQ(nodes[1].prev, &nodes[0]);
   4.217 +    }
   4.218 +
   4.219 +    // test with begin only / prev, next
   4.220 +    {
   4.221 +        node nodes[4];
   4.222 +        void *begin = nullptr;
   4.223 +
   4.224 +        cx_linked_list_add(&begin, nullptr, loc_prev, loc_next, &nodes[0]);
   4.225 +        EXPECT_EQ(begin, &nodes[0]);
   4.226 +        cx_linked_list_add(&begin, nullptr, loc_prev, loc_next, &nodes[1]);
   4.227 +        EXPECT_EQ(begin, &nodes[0]);
   4.228 +        EXPECT_EQ(nodes[0].next, &nodes[1]);
   4.229 +        EXPECT_EQ(nodes[1].prev, &nodes[0]);
   4.230 +
   4.231 +        cx_linked_list_add(&begin, nullptr, loc_prev, loc_next, &nodes[2]);
   4.232 +        EXPECT_EQ(nodes[1].next, &nodes[2]);
   4.233 +        EXPECT_EQ(nodes[2].prev, &nodes[1]);
   4.234 +    }
   4.235 +
   4.236 +    // test with end only / prev, next
   4.237 +    {
   4.238 +        node nodes[4];
   4.239 +        void *end = nullptr;
   4.240 +
   4.241 +        cx_linked_list_add(nullptr, &end, loc_prev, loc_next, &nodes[0]);
   4.242 +        EXPECT_EQ(end, &nodes[0]);
   4.243 +        cx_linked_list_add(nullptr, &end, loc_prev, loc_next, &nodes[1]);
   4.244 +        EXPECT_EQ(end, &nodes[1]);
   4.245 +        EXPECT_EQ(nodes[0].next, &nodes[1]);
   4.246 +        EXPECT_EQ(nodes[1].prev, &nodes[0]);
   4.247 +
   4.248 +        cx_linked_list_add(nullptr, &end, loc_prev, loc_next, &nodes[2]);
   4.249 +        EXPECT_EQ(end, &nodes[2]);
   4.250 +        EXPECT_EQ(nodes[1].next, &nodes[2]);
   4.251 +        EXPECT_EQ(nodes[2].prev, &nodes[1]);
   4.252 +    }
   4.253 +
   4.254 +    // test with begin, end / next
   4.255 +    {
   4.256 +        node nodes[4];
   4.257 +        void *begin = nullptr, *end = nullptr;
   4.258 +
   4.259 +        cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[0]);
   4.260 +        EXPECT_EQ(begin, &nodes[0]);
   4.261 +        EXPECT_EQ(end, &nodes[0]);
   4.262 +        cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[1]);
   4.263 +        EXPECT_EQ(end, &nodes[1]);
   4.264 +        EXPECT_EQ(nodes[0].next, &nodes[1]);
   4.265 +        EXPECT_EQ(nodes[1].prev, nullptr);
   4.266 +    }
   4.267 +}
   4.268 +
   4.269 +TEST(LinkedList_LowLevel, cx_linked_list_prepend) {
   4.270 +    // test with begin, end / prev, next
   4.271 +    {
   4.272 +        node nodes[4];
   4.273 +        void *begin = nullptr, *end = nullptr;
   4.274 +
   4.275 +        cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[0]);
   4.276 +        EXPECT_EQ(begin, &nodes[0]);
   4.277 +        EXPECT_EQ(end, &nodes[0]);
   4.278 +        EXPECT_EQ(nodes[0].prev, nullptr);
   4.279 +        EXPECT_EQ(nodes[0].next, nullptr);
   4.280 +
   4.281 +        cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[1]);
   4.282 +        EXPECT_EQ(begin, &nodes[1]);
   4.283 +        EXPECT_EQ(end, &nodes[0]);
   4.284 +        EXPECT_EQ(nodes[1].next, &nodes[0]);
   4.285 +        EXPECT_EQ(nodes[0].prev, &nodes[1]);
   4.286 +    }
   4.287 +
   4.288 +    // test with begin only / prev, next
   4.289 +    {
   4.290 +        node nodes[4];
   4.291 +        void *begin = nullptr;
   4.292 +
   4.293 +        cx_linked_list_prepend(&begin, nullptr, loc_prev, loc_next, &nodes[0]);
   4.294 +        EXPECT_EQ(begin, &nodes[0]);
   4.295 +        cx_linked_list_prepend(&begin, nullptr, loc_prev, loc_next, &nodes[1]);
   4.296 +        EXPECT_EQ(begin, &nodes[1]);
   4.297 +        EXPECT_EQ(nodes[1].next, &nodes[0]);
   4.298 +        EXPECT_EQ(nodes[0].prev, &nodes[1]);
   4.299 +
   4.300 +        cx_linked_list_prepend(&begin, nullptr, loc_prev, loc_next, &nodes[2]);
   4.301 +        EXPECT_EQ(begin, &nodes[2]);
   4.302 +        EXPECT_EQ(nodes[2].next, &nodes[1]);
   4.303 +        EXPECT_EQ(nodes[1].prev, &nodes[2]);
   4.304 +    }
   4.305 +
   4.306 +    // test with end only / prev, next
   4.307 +    {
   4.308 +        node nodes[4];
   4.309 +        void *end = nullptr;
   4.310 +
   4.311 +        cx_linked_list_prepend(nullptr, &end, loc_prev, loc_next, &nodes[0]);
   4.312 +        EXPECT_EQ(end, &nodes[0]);
   4.313 +        cx_linked_list_prepend(nullptr, &end, loc_prev, loc_next, &nodes[1]);
   4.314 +        EXPECT_EQ(end, &nodes[0]);
   4.315 +        EXPECT_EQ(nodes[1].next, &nodes[0]);
   4.316 +        EXPECT_EQ(nodes[0].prev, &nodes[1]);
   4.317 +
   4.318 +        cx_linked_list_prepend(nullptr, &end, loc_prev, loc_next, &nodes[2]);
   4.319 +        EXPECT_EQ(end, &nodes[0]);
   4.320 +        EXPECT_EQ(nodes[2].next, &nodes[1]);
   4.321 +        EXPECT_EQ(nodes[1].prev, &nodes[2]);
   4.322 +    }
   4.323 +
   4.324 +    // test with begin, end / next
   4.325 +    {
   4.326 +        node nodes[4];
   4.327 +        void *begin = nullptr, *end = nullptr;
   4.328 +
   4.329 +        cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[0]);
   4.330 +        EXPECT_EQ(begin, &nodes[0]);
   4.331 +        EXPECT_EQ(end, &nodes[0]);
   4.332 +        cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[1]);
   4.333 +        cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[2]);
   4.334 +        EXPECT_EQ(begin, &nodes[2]);
   4.335 +        EXPECT_EQ(end, &nodes[0]);
   4.336 +        EXPECT_EQ(nodes[1].next, &nodes[0]);
   4.337 +        EXPECT_EQ(nodes[2].next, &nodes[1]);
   4.338 +        EXPECT_EQ(nodes[1].prev, nullptr);
   4.339 +        EXPECT_EQ(nodes[0].prev, nullptr);
   4.340 +    }
   4.341 +}
   4.342 +
   4.343 +TEST(LinkedList_LowLevel, cx_linked_list_insert) {
   4.344 +    // insert mid list
   4.345 +    {
   4.346 +        node nodes[4];
   4.347 +        void *begin = &nodes[0], *end = &nodes[2];
   4.348 +
   4.349 +        cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
   4.350 +        cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
   4.351 +
   4.352 +        cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3]);
   4.353 +        EXPECT_EQ(begin, &nodes[0]);
   4.354 +        EXPECT_EQ(end, &nodes[2]);
   4.355 +        EXPECT_EQ(nodes[1].next, &nodes[3]);
   4.356 +        EXPECT_EQ(nodes[2].prev, &nodes[3]);
   4.357 +        EXPECT_EQ(nodes[3].prev, &nodes[1]);
   4.358 +        EXPECT_EQ(nodes[3].next, &nodes[2]);
   4.359 +    }
   4.360 +
   4.361 +    // insert end
   4.362 +    {
   4.363 +        node nodes[4];
   4.364 +        void *begin = &nodes[0], *end = &nodes[2];
   4.365 +
   4.366 +        cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
   4.367 +        cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
   4.368 +
   4.369 +        cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3]);
   4.370 +        EXPECT_EQ(begin, &nodes[0]);
   4.371 +        EXPECT_EQ(end, &nodes[3]);
   4.372 +        EXPECT_EQ(nodes[2].next, &nodes[3]);
   4.373 +        EXPECT_EQ(nodes[3].prev, &nodes[2]);
   4.374 +        EXPECT_EQ(nodes[3].next, nullptr);
   4.375 +    }
   4.376 +
   4.377 +    // insert begin
   4.378 +    {
   4.379 +        node nodes[4];
   4.380 +        void *begin = &nodes[0], *end = &nodes[2];
   4.381 +
   4.382 +        cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
   4.383 +        cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
   4.384 +
   4.385 +        cx_linked_list_insert(&begin, &end, loc_prev, loc_next, nullptr, &nodes[3]);
   4.386 +        EXPECT_EQ(begin, &nodes[3]);
   4.387 +        EXPECT_EQ(end, &nodes[2]);
   4.388 +        EXPECT_EQ(nodes[0].prev, &nodes[3]);
   4.389 +        EXPECT_EQ(nodes[3].prev, nullptr);
   4.390 +        EXPECT_EQ(nodes[3].next, &nodes[0]);
   4.391 +    }
   4.392 +}
   4.393 +
   4.394 +TEST(LinkedList_LowLevel, cx_linked_list_insert_chain) {
   4.395 +    // insert mid list
   4.396 +    {
   4.397 +        node nodes[5];
   4.398 +        void *begin = &nodes[0], *end = &nodes[2];
   4.399 +
   4.400 +        cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
   4.401 +        cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
   4.402 +        cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next);
   4.403 +
   4.404 +        cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3], nullptr);
   4.405 +        EXPECT_EQ(begin, &nodes[0]);
   4.406 +        EXPECT_EQ(end, &nodes[2]);
   4.407 +        EXPECT_EQ(nodes[1].next, &nodes[3]);
   4.408 +        EXPECT_EQ(nodes[2].prev, &nodes[4]);
   4.409 +        EXPECT_EQ(nodes[3].prev, &nodes[1]);
   4.410 +        EXPECT_EQ(nodes[4].next, &nodes[2]);
   4.411 +    }
   4.412 +
   4.413 +    // insert end
   4.414 +    {
   4.415 +        node nodes[5];
   4.416 +        void *begin = &nodes[0], *end = &nodes[2];
   4.417 +
   4.418 +        cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
   4.419 +        cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
   4.420 +        cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next);
   4.421 +
   4.422 +        cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3], nullptr);
   4.423 +        EXPECT_EQ(begin, &nodes[0]);
   4.424 +        EXPECT_EQ(end, &nodes[4]);
   4.425 +        EXPECT_EQ(nodes[2].next, &nodes[3]);
   4.426 +        EXPECT_EQ(nodes[3].prev, &nodes[2]);
   4.427 +        EXPECT_EQ(nodes[4].next, nullptr);
   4.428 +    }
   4.429 +
   4.430 +    // insert begin
   4.431 +    {
   4.432 +        node nodes[5];
   4.433 +        void *begin = &nodes[0], *end = &nodes[2];
   4.434 +
   4.435 +        cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
   4.436 +        cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
   4.437 +        cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next);
   4.438 +
   4.439 +        cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, nullptr, &nodes[3], nullptr);
   4.440 +        EXPECT_EQ(begin, &nodes[3]);
   4.441 +        EXPECT_EQ(end, &nodes[2]);
   4.442 +        EXPECT_EQ(nodes[0].prev, &nodes[4]);
   4.443 +        EXPECT_EQ(nodes[3].prev, nullptr);
   4.444 +        EXPECT_EQ(nodes[4].next, &nodes[0]);
   4.445 +    }
   4.446 +}
   4.447 +
   4.448 +TEST(LinkedList_LowLevel, cx_linked_list_first) {
   4.449 +    auto testdata = create_nodes_test_data(3);
   4.450 +    auto begin = testdata.begin;
   4.451 +    EXPECT_EQ(cx_linked_list_first(begin, loc_prev), begin);
   4.452 +    EXPECT_EQ(cx_linked_list_first(begin->next, loc_prev), begin);
   4.453 +    EXPECT_EQ(cx_linked_list_first(begin->next->next, loc_prev), begin);
   4.454 +}
   4.455 +
   4.456 +TEST(LinkedList_LowLevel, cx_linked_list_last) {
   4.457 +    auto testdata = create_nodes_test_data(3);
   4.458 +    auto begin = testdata.begin;
   4.459 +    auto end = begin->next->next;
   4.460 +    EXPECT_EQ(cx_linked_list_last(begin, loc_next), end);
   4.461 +    EXPECT_EQ(cx_linked_list_last(begin->next, loc_next), end);
   4.462 +    EXPECT_EQ(cx_linked_list_last(begin->next->next, loc_next), end);
   4.463 +}
   4.464 +
   4.465 +TEST(LinkedList_LowLevel, cx_linked_list_prev) {
   4.466 +    auto testdata = create_nodes_test_data(3);
   4.467 +    auto begin = testdata.begin;
   4.468 +    EXPECT_EQ(cx_linked_list_prev(begin, loc_next, begin), nullptr);
   4.469 +    EXPECT_EQ(cx_linked_list_prev(begin, loc_next, begin->next), begin);
   4.470 +    EXPECT_EQ(cx_linked_list_prev(begin, loc_next, begin->next->next), begin->next);
   4.471 +}
   4.472 +
   4.473 +TEST(LinkedList_LowLevel, cx_linked_list_remove) {
   4.474 +    auto testdata = create_nodes_test_data({2, 4, 6});
   4.475 +    auto begin = reinterpret_cast<void *>(testdata.begin);
   4.476 +    auto first = testdata.begin;
   4.477 +    auto second = first->next;
   4.478 +    auto third = second->next;
   4.479 +    auto end = reinterpret_cast<void *>(third);
   4.480 +
   4.481 +    cx_linked_list_remove(&begin, &end, loc_prev, loc_next, second);
   4.482 +    EXPECT_EQ(begin, first);
   4.483 +    EXPECT_EQ(end, third);
   4.484 +    EXPECT_EQ(first->prev, nullptr);
   4.485 +    EXPECT_EQ(first->next, third);
   4.486 +    EXPECT_EQ(third->prev, first);
   4.487 +    EXPECT_EQ(third->next, nullptr);
   4.488 +
   4.489 +    cx_linked_list_remove(&begin, &end, loc_prev, loc_next, third);
   4.490 +    EXPECT_EQ(begin, first);
   4.491 +    EXPECT_EQ(end, first);
   4.492 +    EXPECT_EQ(first->prev, nullptr);
   4.493 +    EXPECT_EQ(first->next, nullptr);
   4.494 +
   4.495 +    cx_linked_list_remove(&begin, &end, loc_prev, loc_next, first);
   4.496 +    EXPECT_EQ(begin, nullptr);
   4.497 +    EXPECT_EQ(end, nullptr);
   4.498 +}
   4.499 +
   4.500 +TEST(LinkedList_LowLevel, cx_linked_list_size) {
   4.501 +    EXPECT_EQ(cx_linked_list_size(nullptr, loc_next), 0);
   4.502 +
   4.503 +    {
   4.504 +        auto testdata = create_nodes_test_data(5);
   4.505 +        EXPECT_EQ(cx_linked_list_size(testdata.begin, loc_next), 5);
   4.506 +    }
   4.507 +
   4.508 +    {
   4.509 +        auto testdata = create_nodes_test_data(13);
   4.510 +        EXPECT_EQ(cx_linked_list_size(testdata.begin, loc_next), 13);
   4.511 +    }
   4.512 +}
   4.513 +
   4.514 +TEST(LinkedList_LowLevel, cx_linked_list_sort) {
   4.515 +    int_test_data<1000> testdata;
   4.516 +    std::array<int, 1000> sorted{};
   4.517 +    std::partial_sort_copy(testdata.data.begin(), testdata.data.end(), sorted.begin(), sorted.end());
   4.518 +
   4.519 +    auto scrambled = create_nodes_test_data(testdata.data.begin(), testdata.data.end());
   4.520 +    void *begin = scrambled.begin;
   4.521 +    void *end = cx_linked_list_last(begin, loc_next);
   4.522 +
   4.523 +    cx_linked_list_sort(&begin, &end, loc_prev, loc_next, loc_data,
   4.524 +                        false, cmp_int);
   4.525 +
   4.526 +    node *check = reinterpret_cast<node *>(begin);
   4.527 +    node *check_last = nullptr;
   4.528 +    cx_for_n (i, sorted.size()) {
   4.529 +        EXPECT_EQ(check->data, sorted[i]);
   4.530 +        EXPECT_EQ(check->prev, check_last);
   4.531 +        if (i < sorted.size() - 1) {
   4.532 +            ASSERT_NE(check->next, nullptr);
   4.533 +        }
   4.534 +        check_last = check;
   4.535 +        check = check->next;
   4.536 +    }
   4.537 +    EXPECT_EQ(check, nullptr);
   4.538 +    EXPECT_EQ(end, check_last);
   4.539 +}
   4.540 +
   4.541 +TEST(LinkedList_LowLevel, cx_linked_list_reverse) {
   4.542 +    auto testdata = create_nodes_test_data({2, 4, 6, 8});
   4.543 +    auto expected = create_nodes_test_data({8, 6, 4, 2});
   4.544 +
   4.545 +    auto begin = reinterpret_cast<void *>(testdata.begin);
   4.546 +    auto end = cx_linked_list_last(begin, loc_next);
   4.547 +    auto orig_begin = begin, orig_end = end;
   4.548 +
   4.549 +    cx_linked_list_reverse(&begin, &end, loc_prev, loc_next);
   4.550 +    EXPECT_EQ(end, orig_begin);
   4.551 +    EXPECT_EQ(begin, orig_end);
   4.552 +    EXPECT_EQ(cx_linked_list_compare(begin, expected.begin, loc_next, loc_data, 0, cmp_int), 0);
   4.553 +}
   4.554 +
   4.555 +class HighLevelTest : public ::testing::Test {
   4.556 +    mutable std::unordered_set<CxList *> lists;
   4.557 +protected:
   4.558 +    void SetUp() override {
   4.559 +        cxTestingAllocatorReset();
   4.560 +    }
   4.561 +
   4.562 +    void TearDown() override {
   4.563 +        for (auto &&l: lists) cxListDestroy(l);
   4.564 +        EXPECT_TRUE(cxTestingAllocatorVerify());
   4.565 +    }
   4.566 +
   4.567 +    static constexpr size_t testdata_len = 250;
   4.568 +    int_test_data<testdata_len> testdata;
   4.569 +
   4.570 +    auto autofree(CxList *list) const -> CxList * {
   4.571 +        lists.insert(list);
   4.572 +        return list;
   4.573 +    }
   4.574 +
   4.575 +    auto linkedListFromTestData() const -> CxList * {
   4.576 +        return autofree(
   4.577 +                cxLinkedListFromArray(
   4.578 +                        cxTestingAllocator,
   4.579 +                        cmp_int,
   4.580 +                        sizeof(int),
   4.581 +                        testdata_len,
   4.582 +                        testdata.data.data()
   4.583 +                )
   4.584 +        );
   4.585 +    }
   4.586 +
   4.587 +    auto pointerLinkedListFromTestData() const -> CxList * {
   4.588 +        auto list = autofree(cxPointerLinkedListCreate(cxTestingAllocator, cmp_int));
   4.589 +        cx_for_n(i, testdata_len) cxListAdd(list, &testdata.data[i]);
   4.590 +        return list;
   4.591 +    }
   4.592 +
   4.593 +    static void verifyCreate(CxList *list) {
   4.594 +        EXPECT_EQ(list->size, 0);
   4.595 +        EXPECT_EQ(list->capacity, (size_t) -1);
   4.596 +        EXPECT_EQ(list->allocator, cxTestingAllocator);
   4.597 +        EXPECT_EQ(list->cmpfunc, cmp_int);
   4.598 +    }
   4.599 +
   4.600 +    void verifyAdd(CxList *list, bool write_through) {
   4.601 +        auto len = testdata_len;
   4.602 +        cx_for_n (i, len) EXPECT_EQ(cxListAdd(list, &testdata.data[i]), 0);
   4.603 +        EXPECT_EQ(list->size, len);
   4.604 +        EXPECT_GE(list->capacity, list->size);
   4.605 +        cx_for_n (i, len) EXPECT_EQ(*(int *) cxListAt(list, i), testdata.data[i]);
   4.606 +        cx_for_n (i, len) ++testdata.data[i];
   4.607 +        if (write_through) {
   4.608 +            cx_for_n (i, len) EXPECT_EQ(*(int *) cxListAt(list, i), testdata.data[i]);
   4.609 +        } else {
   4.610 +            cx_for_n (i, len) EXPECT_EQ(*(int *) cxListAt(list, i), testdata.data[i] - 1);
   4.611 +        }
   4.612 +    }
   4.613 +
   4.614 +    static void verifyInsert(CxList *list) {
   4.615 +        int a = 5, b = 47, c = 13, d = 42;
   4.616 +
   4.617 +        EXPECT_NE(cxListInsert(list, 1, &a), 0);
   4.618 +        EXPECT_EQ(list->size, 0);
   4.619 +        EXPECT_EQ(cxListInsert(list, 0, &a), 0);
   4.620 +        EXPECT_EQ(list->size, 1);
   4.621 +        EXPECT_EQ(cxListInsert(list, 0, &b), 0);
   4.622 +        EXPECT_EQ(list->size, 2);
   4.623 +        EXPECT_EQ(cxListInsert(list, 1, &c), 0);
   4.624 +        EXPECT_EQ(list->size, 3);
   4.625 +        EXPECT_EQ(cxListInsert(list, 3, &d), 0);
   4.626 +
   4.627 +        EXPECT_EQ(list->size, 4);
   4.628 +        EXPECT_GE(list->capacity, list->size);
   4.629 +
   4.630 +        EXPECT_EQ(*(int *) cxListAt(list, 0), 47);
   4.631 +        EXPECT_EQ(*(int *) cxListAt(list, 1), 13);
   4.632 +        EXPECT_EQ(*(int *) cxListAt(list, 2), 5);
   4.633 +        EXPECT_EQ(*(int *) cxListAt(list, 3), 42);
   4.634 +    }
   4.635 +
   4.636 +    void verifyRemove(CxList *list) const {
   4.637 +        EXPECT_EQ(cxListRemove(list, 2), 0);
   4.638 +        EXPECT_EQ(cxListRemove(list, 4), 0);
   4.639 +        EXPECT_EQ(list->size, testdata_len - 2);
   4.640 +        EXPECT_GE(list->capacity, list->size);
   4.641 +        EXPECT_EQ(*(int *) cxListAt(list, 0), testdata.data[0]);
   4.642 +        EXPECT_EQ(*(int *) cxListAt(list, 1), testdata.data[1]);
   4.643 +        EXPECT_EQ(*(int *) cxListAt(list, 2), testdata.data[3]);
   4.644 +        EXPECT_EQ(*(int *) cxListAt(list, 3), testdata.data[4]);
   4.645 +        EXPECT_EQ(*(int *) cxListAt(list, 4), testdata.data[6]);
   4.646 +
   4.647 +        EXPECT_EQ(cxListRemove(list, 0), 0);
   4.648 +        EXPECT_EQ(list->size, testdata_len - 3);
   4.649 +        EXPECT_GE(list->capacity, list->size);
   4.650 +        EXPECT_EQ(*(int *) cxListAt(list, 0), testdata.data[1]);
   4.651 +        EXPECT_EQ(*(int *) cxListAt(list, 1), testdata.data[3]);
   4.652 +
   4.653 +        EXPECT_NE(cxListRemove(list, testdata_len), 0);
   4.654 +    }
   4.655 +
   4.656 +    void verifyAt(CxList *list) const {
   4.657 +        auto len = testdata_len;
   4.658 +        EXPECT_EQ(list->size, len);
   4.659 +        cx_for_n (i, list->size) EXPECT_EQ(*(int *) cxListAt(list, i), testdata.data[i]);
   4.660 +        EXPECT_EQ(cxListAt(list, list->size), nullptr);
   4.661 +    }
   4.662 +
   4.663 +    void verifyFind(CxList *list) const {
   4.664 +        cx_for_n (attempt, 25) {
   4.665 +            size_t exp = rand() % testdata_len; // NOLINT(cert-msc50-cpp)
   4.666 +            int val = testdata.data[exp];
   4.667 +            // randomly picked number could occur earlier in list - find first position
   4.668 +            cx_for_n (i, exp) {
   4.669 +                if (testdata.data[i] == val) {
   4.670 +                    exp = i;
   4.671 +                    break;
   4.672 +                }
   4.673 +            }
   4.674 +            EXPECT_EQ(cxListFind(list, &val), exp);
   4.675 +        }
   4.676 +    }
   4.677 +
   4.678 +    void verifySort(CxList *list) const {
   4.679 +        std::array<int, testdata_len> expected{};
   4.680 +        std::partial_sort_copy(testdata.data.begin(), testdata.data.end(), expected.begin(), expected.end());
   4.681 +        cxListSort(list);
   4.682 +        cx_for_n (i, testdata_len) ASSERT_EQ(*(int *) cxListAt(list, i), expected[i]);
   4.683 +    }
   4.684 +
   4.685 +    void verifyIterator(CxList *list) const {
   4.686 +        int i = 0;
   4.687 +        CxIterator iter = cxListBegin(list);
   4.688 +        cx_foreach(int*, x, iter) {
   4.689 +            ASSERT_EQ(iter.index, (size_t) (i + 1) / 2);
   4.690 +            ASSERT_EQ(*x, testdata.data[i]);
   4.691 +            if (i % 2 == 1) iter.remove = true;
   4.692 +            i++;
   4.693 +        }
   4.694 +        auto len = testdata_len;
   4.695 +        EXPECT_EQ(i, len);
   4.696 +        ASSERT_EQ(list->size, len / 2);
   4.697 +        cx_for_n(j, len / 2) ASSERT_EQ(*(int *) cxListAt(list, j), testdata.data[j * 2]);
   4.698 +    }
   4.699 +
   4.700 +    static void verifyInsertViaIterator(CxList *list) {
   4.701 +        int newdata[] = {10, 20, 30, 40, 50};
   4.702 +
   4.703 +        CxIterator iter = cxListIterator(list, 2);
   4.704 +        EXPECT_TRUE(cxIteratorValid(&iter));
   4.705 +        EXPECT_EQ(iter.index, 2);
   4.706 +        EXPECT_EQ(*(int *) cxIteratorCurrent(&iter), 2);
   4.707 +        cxListInsertAfter(&iter, &newdata[0]);
   4.708 +        EXPECT_TRUE(cxIteratorValid(&iter));
   4.709 +        EXPECT_EQ(iter.index, 2);
   4.710 +        EXPECT_EQ(*(int *) cxIteratorCurrent(&iter), 2);
   4.711 +        cxListInsertBefore(&iter, &newdata[1]);
   4.712 +        EXPECT_TRUE(cxIteratorValid(&iter));
   4.713 +        EXPECT_EQ(iter.index, 3);
   4.714 +        EXPECT_EQ(*(int *) cxIteratorCurrent(&iter), 2);
   4.715 +
   4.716 +        iter = cxListBegin(list);
   4.717 +        cxListInsertBefore(&iter, &newdata[2]);
   4.718 +        EXPECT_TRUE(cxIteratorValid(&iter));
   4.719 +        EXPECT_EQ(iter.index, 1);
   4.720 +        EXPECT_EQ(*(int *) cxIteratorCurrent(&iter), 0);
   4.721 +        iter = cxListIterator(list, list->size);
   4.722 +        cxListInsertBefore(&iter, &newdata[3]);
   4.723 +        EXPECT_FALSE(cxIteratorValid(&iter));
   4.724 +        EXPECT_EQ(iter.index, 9);
   4.725 +        iter = cxListIterator(list, list->size);
   4.726 +        cxListInsertAfter(&iter, &newdata[4]);
   4.727 +        EXPECT_FALSE(cxIteratorValid(&iter));
   4.728 +        EXPECT_EQ(iter.index, 10);
   4.729 +
   4.730 +        int expdata[] = {30, 0, 1, 20, 2, 10, 3, 4, 40, 50};
   4.731 +        cx_for_n (j, 10) EXPECT_EQ(*(int *) cxListAt(list, j), expdata[j]);
   4.732 +    }
   4.733 +};
   4.734 +
   4.735 +class LinkedList : public HighLevelTest {
   4.736 +};
   4.737 +
   4.738 +class PointerLinkedList : public HighLevelTest {
   4.739 +};
   4.740 +
   4.741 +TEST_F(LinkedList, cxLinkedListCreate) {
   4.742 +    CxList *list = autofree(cxLinkedListCreate(cxTestingAllocator, cmp_int, sizeof(int)));
   4.743 +    EXPECT_EQ(list->itemsize, sizeof(int));
   4.744 +    verifyCreate(list);
   4.745 +}
   4.746 +
   4.747 +TEST_F(PointerLinkedList, cxPointerLinkedListCreate) {
   4.748 +    CxList *list = autofree(cxPointerLinkedListCreate(cxTestingAllocator, cmp_int));
   4.749 +    EXPECT_EQ(list->itemsize, sizeof(void *));
   4.750 +    verifyCreate(list);
   4.751 +}
   4.752 +
   4.753 +TEST_F(LinkedList, cxLinkedListFromArray) {
   4.754 +    CxList *expected = autofree(cxLinkedListCreate(cxTestingAllocator, cmp_int, sizeof(int)));
   4.755 +    cx_for_n (i, testdata_len) cxListAdd(expected, &testdata.data[i]);
   4.756 +    CxList *list = autofree(cxLinkedListFromArray(cxTestingAllocator, cmp_int, sizeof(int),
   4.757 +                                                  testdata_len, testdata.data.data()));
   4.758 +    EXPECT_EQ(cxListCompare(list, expected), 0);
   4.759 +}
   4.760 +
   4.761 +TEST_F(LinkedList, cxListAdd) {
   4.762 +    CxList *list = autofree(cxLinkedListCreate(cxTestingAllocator, cmp_int, sizeof(int)));
   4.763 +    verifyAdd(list, false);
   4.764 +}
   4.765 +
   4.766 +TEST_F(PointerLinkedList, cxListAdd) {
   4.767 +    CxList *list = autofree(cxPointerLinkedListCreate(cxTestingAllocator, cmp_int));
   4.768 +    verifyAdd(list, true);
   4.769 +}
   4.770 +
   4.771 +TEST_F(LinkedList, cxListInsert) {
   4.772 +    verifyInsert(autofree(cxLinkedListCreate(cxTestingAllocator, cmp_int, sizeof(int))));
   4.773 +}
   4.774 +
   4.775 +TEST_F(PointerLinkedList, cxListInsert) {
   4.776 +    verifyInsert(autofree(cxPointerLinkedListCreate(cxTestingAllocator, cmp_int)));
   4.777 +}
   4.778 +
   4.779 +TEST_F(LinkedList, cxListRemove) {
   4.780 +    verifyRemove(linkedListFromTestData());
   4.781 +}
   4.782 +
   4.783 +TEST_F(PointerLinkedList, cxListRemove) {
   4.784 +    verifyRemove(pointerLinkedListFromTestData());
   4.785 +}
   4.786 +
   4.787 +TEST_F(LinkedList, cxListAt) {
   4.788 +    verifyAt(linkedListFromTestData());
   4.789 +}
   4.790 +
   4.791 +TEST_F(PointerLinkedList, cxListAt) {
   4.792 +    verifyAt(pointerLinkedListFromTestData());
   4.793 +}
   4.794 +
   4.795 +TEST_F(LinkedList, cxListFind) {
   4.796 +    verifyFind(linkedListFromTestData());
   4.797 +}
   4.798 +
   4.799 +TEST_F(PointerLinkedList, cxListFind) {
   4.800 +    verifyFind(pointerLinkedListFromTestData());
   4.801 +}
   4.802 +
   4.803 +TEST_F(LinkedList, cxListSort) {
   4.804 +    verifySort(linkedListFromTestData());
   4.805 +}
   4.806 +
   4.807 +TEST_F(PointerLinkedList, cxListSort) {
   4.808 +    verifySort(pointerLinkedListFromTestData());
   4.809 +}
   4.810 +
   4.811 +TEST_F(LinkedList, Iterator) {
   4.812 +    verifyIterator(linkedListFromTestData());
   4.813 +}
   4.814 +
   4.815 +TEST_F(PointerLinkedList, Iterator) {
   4.816 +    verifyIterator(pointerLinkedListFromTestData());
   4.817 +}
   4.818 +
   4.819 +TEST_F(LinkedList, InsertViaIterator) {
   4.820 +    int fivenums[] = {0, 1, 2, 3, 4, 5};
   4.821 +    CxList *list = autofree(cxLinkedListFromArray(cxTestingAllocator, cmp_int, sizeof(int), 5, fivenums));
   4.822 +    verifyInsertViaIterator(list);
   4.823 +}
   4.824 +
   4.825 +TEST_F(PointerLinkedList, InsertViaIterator) {
   4.826 +    int fivenums[] = {0, 1, 2, 3, 4, 5};
   4.827 +    CxList *list = autofree(cxPointerLinkedListCreate(cxTestingAllocator, cmp_int));
   4.828 +    cx_for_n (i, 5) cxListAdd(list, &fivenums[i]);
   4.829 +    verifyInsertViaIterator(list);
   4.830 +}