1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/tests/test_list.cpp Wed Feb 08 20:26:26 2023 +0100
1.3 @@ -0,0 +1,1159 @@
1.4 +/*
1.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
1.6 + *
1.7 + * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
1.8 + *
1.9 + * Redistribution and use in source and binary forms, with or without
1.10 + * modification, are permitted provided that the following conditions are met:
1.11 + *
1.12 + * 1. Redistributions of source code must retain the above copyright
1.13 + * notice, this list of conditions and the following disclaimer.
1.14 + *
1.15 + * 2. Redistributions in binary form must reproduce the above copyright
1.16 + * notice, this list of conditions and the following disclaimer in the
1.17 + * documentation and/or other materials provided with the distribution.
1.18 + *
1.19 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
1.20 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
1.21 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
1.22 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
1.23 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
1.24 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
1.25 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
1.26 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
1.27 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
1.28 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
1.29 + * POSSIBILITY OF SUCH DAMAGE.
1.30 + */
1.31 +
1.32 +#include "cx/linked_list.h"
1.33 +#include "cx/array_list.h"
1.34 +#include "cx/utils.h"
1.35 +#include "cx/compare.h"
1.36 +#include "util_allocator.h"
1.37 +
1.38 +#include <gtest/gtest.h>
1.39 +#include <array>
1.40 +#include <vector>
1.41 +#include <unordered_set>
1.42 +#include <algorithm>
1.43 +
1.44 +struct node {
1.45 + node *next = nullptr;
1.46 + node *prev = nullptr;
1.47 + int data = 0;
1.48 +};
1.49 +
1.50 +const ptrdiff_t loc_prev = offsetof(struct node, prev);
1.51 +const ptrdiff_t loc_next = offsetof(struct node, next);
1.52 +const ptrdiff_t loc_data = offsetof(struct node, data);
1.53 +
1.54 +struct node_test_data {
1.55 + node *begin = nullptr;
1.56 +
1.57 + explicit node_test_data(node *begin) : begin(begin) {
1.58 + auto n = begin;
1.59 + while (n != nullptr) {
1.60 + nodes.push_back(n);
1.61 + n = n->next;
1.62 + }
1.63 + }
1.64 +
1.65 + node_test_data(node_test_data &) = delete;
1.66 +
1.67 + node_test_data(node_test_data &&) = default;
1.68 +
1.69 + ~node_test_data() {
1.70 + for (auto &&n: nodes) delete n;
1.71 + }
1.72 +
1.73 +private:
1.74 + std::vector<node *> nodes;
1.75 +};
1.76 +
1.77 +static node_test_data create_nodes_test_data(size_t len) {
1.78 + if (len == 0) return node_test_data{nullptr};
1.79 + auto begin = new node;
1.80 + auto prev = begin;
1.81 + for (size_t i = 1; i < len; i++) {
1.82 + auto n = new node;
1.83 + cx_linked_list_link(prev, n, loc_prev, loc_next);
1.84 + prev = n;
1.85 + }
1.86 + return node_test_data{begin};
1.87 +}
1.88 +
1.89 +template<typename InputIter>
1.90 +static node_test_data create_nodes_test_data(
1.91 + InputIter begin,
1.92 + InputIter end
1.93 +) {
1.94 + if (begin == end) return node_test_data{nullptr};
1.95 + node *first = new node;
1.96 + first->data = *begin;
1.97 + node *prev = first;
1.98 + begin++;
1.99 + for (; begin != end; begin++) {
1.100 + auto n = new node;
1.101 + n->data = *begin;
1.102 + cx_linked_list_link(prev, n, loc_prev, loc_next);
1.103 + prev = n;
1.104 + }
1.105 + return node_test_data{first};
1.106 +}
1.107 +
1.108 +static node_test_data create_nodes_test_data(std::initializer_list<int> data) {
1.109 + return create_nodes_test_data(data.begin(), data.end());
1.110 +}
1.111 +
1.112 +template<size_t N>
1.113 +struct int_test_data {
1.114 + std::array<int, N> data;
1.115 +
1.116 + int_test_data() {
1.117 + cx_for_n (i, N) data[i] = ::rand(); // NOLINT(cert-msc50-cpp)
1.118 + }
1.119 +};
1.120 +
1.121 +TEST(LinkedList_LowLevel, link_unlink) {
1.122 + node a, b, c;
1.123 +
1.124 + cx_linked_list_link(&a, &b, loc_prev, loc_next);
1.125 + EXPECT_EQ(a.prev, nullptr);
1.126 + EXPECT_EQ(a.next, &b);
1.127 + EXPECT_EQ(b.prev, &a);
1.128 + EXPECT_EQ(b.next, nullptr);
1.129 +
1.130 + cx_linked_list_unlink(&a, &b, loc_prev, loc_next);
1.131 + EXPECT_EQ(a.prev, nullptr);
1.132 + EXPECT_EQ(a.next, nullptr);
1.133 + EXPECT_EQ(b.prev, nullptr);
1.134 + EXPECT_EQ(b.next, nullptr);
1.135 +
1.136 + cx_linked_list_link(&b, &c, loc_prev, loc_next);
1.137 + cx_linked_list_link(&a, &b, loc_prev, loc_next);
1.138 + cx_linked_list_unlink(&b, &c, loc_prev, loc_next);
1.139 + EXPECT_EQ(a.prev, nullptr);
1.140 + EXPECT_EQ(a.next, &b);
1.141 + EXPECT_EQ(b.prev, &a);
1.142 + EXPECT_EQ(b.next, nullptr);
1.143 + EXPECT_EQ(c.prev, nullptr);
1.144 + EXPECT_EQ(c.next, nullptr);
1.145 +}
1.146 +
1.147 +TEST(LinkedList_LowLevel, cx_linked_list_at) {
1.148 + node a, b, c, d;
1.149 + cx_linked_list_link(&a, &b, loc_prev, loc_next);
1.150 + cx_linked_list_link(&b, &c, loc_prev, loc_next);
1.151 + cx_linked_list_link(&c, &d, loc_prev, loc_next);
1.152 +
1.153 + EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 0), &a);
1.154 + EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 1), &b);
1.155 + EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 2), &c);
1.156 + EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 3), &d);
1.157 + EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 4), nullptr);
1.158 +
1.159 + EXPECT_EQ(cx_linked_list_at(&b, 1, loc_prev, 0), &a);
1.160 + EXPECT_EQ(cx_linked_list_at(&b, 1, loc_next, 1), &b);
1.161 + EXPECT_EQ(cx_linked_list_at(&b, 1, loc_next, 2), &c);
1.162 + EXPECT_EQ(cx_linked_list_at(&b, 1, loc_next, 3), &d);
1.163 + EXPECT_EQ(cx_linked_list_at(&b, 1, loc_next, 4), nullptr);
1.164 +
1.165 + EXPECT_EQ(cx_linked_list_at(&d, 3, loc_prev, 0), &a);
1.166 + EXPECT_EQ(cx_linked_list_at(&d, 3, loc_prev, 1), &b);
1.167 +}
1.168 +
1.169 +TEST(LinkedList_LowLevel, cx_linked_list_find) {
1.170 + auto testdata = create_nodes_test_data({2, 4, 6, 8});
1.171 + auto list = testdata.begin;
1.172 + int s;
1.173 +
1.174 + s = 2;
1.175 + EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s), 0);
1.176 + s = 4;
1.177 + EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s), 1);
1.178 + s = 6;
1.179 + EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s), 2);
1.180 + s = 8;
1.181 + EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s), 3);
1.182 + s = 10;
1.183 + EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s), 4);
1.184 + s = -2;
1.185 + EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s), 4);
1.186 +}
1.187 +
1.188 +TEST(LinkedList_LowLevel, cx_linked_list_compare) {
1.189 + auto ta = create_nodes_test_data({2, 4, 6, 8});
1.190 + auto tb = create_nodes_test_data({2, 4, 6});
1.191 + auto tc = create_nodes_test_data({2, 4, 6, 9});
1.192 + auto la = ta.begin, lb = tb.begin, lc = tc.begin;
1.193 +
1.194 + EXPECT_GT(cx_linked_list_compare(la, lb, loc_next, loc_data, cx_cmp_int), 0);
1.195 + EXPECT_LT(cx_linked_list_compare(lb, la, loc_next, loc_data, cx_cmp_int), 0);
1.196 + EXPECT_GT(cx_linked_list_compare(lc, la, loc_next, loc_data, cx_cmp_int), 0);
1.197 + EXPECT_LT(cx_linked_list_compare(la, lc, loc_next, loc_data, cx_cmp_int), 0);
1.198 + EXPECT_EQ(cx_linked_list_compare(la, la, loc_next, loc_data, cx_cmp_int), 0);
1.199 +}
1.200 +
1.201 +TEST(LinkedList_LowLevel, cx_linked_list_add) {
1.202 + // test with begin, end / prev, next
1.203 + {
1.204 + node nodes[4];
1.205 + void *begin = nullptr, *end = nullptr;
1.206 +
1.207 + cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[0]);
1.208 + EXPECT_EQ(begin, &nodes[0]);
1.209 + EXPECT_EQ(end, &nodes[0]);
1.210 + EXPECT_EQ(nodes[0].prev, nullptr);
1.211 + EXPECT_EQ(nodes[0].next, nullptr);
1.212 +
1.213 + cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[1]);
1.214 + EXPECT_EQ(begin, &nodes[0]);
1.215 + EXPECT_EQ(end, &nodes[1]);
1.216 + EXPECT_EQ(nodes[0].next, &nodes[1]);
1.217 + EXPECT_EQ(nodes[1].prev, &nodes[0]);
1.218 + }
1.219 +
1.220 + // test with begin only / prev, next
1.221 + {
1.222 + node nodes[4];
1.223 + void *begin = nullptr;
1.224 +
1.225 + cx_linked_list_add(&begin, nullptr, loc_prev, loc_next, &nodes[0]);
1.226 + EXPECT_EQ(begin, &nodes[0]);
1.227 + cx_linked_list_add(&begin, nullptr, loc_prev, loc_next, &nodes[1]);
1.228 + EXPECT_EQ(begin, &nodes[0]);
1.229 + EXPECT_EQ(nodes[0].next, &nodes[1]);
1.230 + EXPECT_EQ(nodes[1].prev, &nodes[0]);
1.231 +
1.232 + cx_linked_list_add(&begin, nullptr, loc_prev, loc_next, &nodes[2]);
1.233 + EXPECT_EQ(nodes[1].next, &nodes[2]);
1.234 + EXPECT_EQ(nodes[2].prev, &nodes[1]);
1.235 + }
1.236 +
1.237 + // test with end only / prev, next
1.238 + {
1.239 + node nodes[4];
1.240 + void *end = nullptr;
1.241 +
1.242 + cx_linked_list_add(nullptr, &end, loc_prev, loc_next, &nodes[0]);
1.243 + EXPECT_EQ(end, &nodes[0]);
1.244 + cx_linked_list_add(nullptr, &end, loc_prev, loc_next, &nodes[1]);
1.245 + EXPECT_EQ(end, &nodes[1]);
1.246 + EXPECT_EQ(nodes[0].next, &nodes[1]);
1.247 + EXPECT_EQ(nodes[1].prev, &nodes[0]);
1.248 +
1.249 + cx_linked_list_add(nullptr, &end, loc_prev, loc_next, &nodes[2]);
1.250 + EXPECT_EQ(end, &nodes[2]);
1.251 + EXPECT_EQ(nodes[1].next, &nodes[2]);
1.252 + EXPECT_EQ(nodes[2].prev, &nodes[1]);
1.253 + }
1.254 +
1.255 + // test with begin, end / next
1.256 + {
1.257 + node nodes[4];
1.258 + void *begin = nullptr, *end = nullptr;
1.259 +
1.260 + cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[0]);
1.261 + EXPECT_EQ(begin, &nodes[0]);
1.262 + EXPECT_EQ(end, &nodes[0]);
1.263 + cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[1]);
1.264 + EXPECT_EQ(end, &nodes[1]);
1.265 + EXPECT_EQ(nodes[0].next, &nodes[1]);
1.266 + EXPECT_EQ(nodes[1].prev, nullptr);
1.267 + }
1.268 +}
1.269 +
1.270 +TEST(LinkedList_LowLevel, cx_linked_list_prepend) {
1.271 + // test with begin, end / prev, next
1.272 + {
1.273 + node nodes[4];
1.274 + void *begin = nullptr, *end = nullptr;
1.275 +
1.276 + cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[0]);
1.277 + EXPECT_EQ(begin, &nodes[0]);
1.278 + EXPECT_EQ(end, &nodes[0]);
1.279 + EXPECT_EQ(nodes[0].prev, nullptr);
1.280 + EXPECT_EQ(nodes[0].next, nullptr);
1.281 +
1.282 + cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[1]);
1.283 + EXPECT_EQ(begin, &nodes[1]);
1.284 + EXPECT_EQ(end, &nodes[0]);
1.285 + EXPECT_EQ(nodes[1].next, &nodes[0]);
1.286 + EXPECT_EQ(nodes[0].prev, &nodes[1]);
1.287 + }
1.288 +
1.289 + // test with begin only / prev, next
1.290 + {
1.291 + node nodes[4];
1.292 + void *begin = nullptr;
1.293 +
1.294 + cx_linked_list_prepend(&begin, nullptr, loc_prev, loc_next, &nodes[0]);
1.295 + EXPECT_EQ(begin, &nodes[0]);
1.296 + cx_linked_list_prepend(&begin, nullptr, loc_prev, loc_next, &nodes[1]);
1.297 + EXPECT_EQ(begin, &nodes[1]);
1.298 + EXPECT_EQ(nodes[1].next, &nodes[0]);
1.299 + EXPECT_EQ(nodes[0].prev, &nodes[1]);
1.300 +
1.301 + cx_linked_list_prepend(&begin, nullptr, loc_prev, loc_next, &nodes[2]);
1.302 + EXPECT_EQ(begin, &nodes[2]);
1.303 + EXPECT_EQ(nodes[2].next, &nodes[1]);
1.304 + EXPECT_EQ(nodes[1].prev, &nodes[2]);
1.305 + }
1.306 +
1.307 + // test with end only / prev, next
1.308 + {
1.309 + node nodes[4];
1.310 + void *end = nullptr;
1.311 +
1.312 + cx_linked_list_prepend(nullptr, &end, loc_prev, loc_next, &nodes[0]);
1.313 + EXPECT_EQ(end, &nodes[0]);
1.314 + cx_linked_list_prepend(nullptr, &end, loc_prev, loc_next, &nodes[1]);
1.315 + EXPECT_EQ(end, &nodes[0]);
1.316 + EXPECT_EQ(nodes[1].next, &nodes[0]);
1.317 + EXPECT_EQ(nodes[0].prev, &nodes[1]);
1.318 +
1.319 + cx_linked_list_prepend(nullptr, &end, loc_prev, loc_next, &nodes[2]);
1.320 + EXPECT_EQ(end, &nodes[0]);
1.321 + EXPECT_EQ(nodes[2].next, &nodes[1]);
1.322 + EXPECT_EQ(nodes[1].prev, &nodes[2]);
1.323 + }
1.324 +
1.325 + // test with begin, end / next
1.326 + {
1.327 + node nodes[4];
1.328 + void *begin = nullptr, *end = nullptr;
1.329 +
1.330 + cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[0]);
1.331 + EXPECT_EQ(begin, &nodes[0]);
1.332 + EXPECT_EQ(end, &nodes[0]);
1.333 + cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[1]);
1.334 + cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[2]);
1.335 + EXPECT_EQ(begin, &nodes[2]);
1.336 + EXPECT_EQ(end, &nodes[0]);
1.337 + EXPECT_EQ(nodes[1].next, &nodes[0]);
1.338 + EXPECT_EQ(nodes[2].next, &nodes[1]);
1.339 + EXPECT_EQ(nodes[1].prev, nullptr);
1.340 + EXPECT_EQ(nodes[0].prev, nullptr);
1.341 + }
1.342 +}
1.343 +
1.344 +TEST(LinkedList_LowLevel, cx_linked_list_insert) {
1.345 + // insert mid list
1.346 + {
1.347 + node nodes[4];
1.348 + void *begin = &nodes[0], *end = &nodes[2];
1.349 +
1.350 + cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
1.351 + cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
1.352 +
1.353 + cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3]);
1.354 + EXPECT_EQ(begin, &nodes[0]);
1.355 + EXPECT_EQ(end, &nodes[2]);
1.356 + EXPECT_EQ(nodes[1].next, &nodes[3]);
1.357 + EXPECT_EQ(nodes[2].prev, &nodes[3]);
1.358 + EXPECT_EQ(nodes[3].prev, &nodes[1]);
1.359 + EXPECT_EQ(nodes[3].next, &nodes[2]);
1.360 + }
1.361 +
1.362 + // insert end
1.363 + {
1.364 + node nodes[4];
1.365 + void *begin = &nodes[0], *end = &nodes[2];
1.366 +
1.367 + cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
1.368 + cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
1.369 +
1.370 + cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3]);
1.371 + EXPECT_EQ(begin, &nodes[0]);
1.372 + EXPECT_EQ(end, &nodes[3]);
1.373 + EXPECT_EQ(nodes[2].next, &nodes[3]);
1.374 + EXPECT_EQ(nodes[3].prev, &nodes[2]);
1.375 + EXPECT_EQ(nodes[3].next, nullptr);
1.376 + }
1.377 +
1.378 + // insert begin
1.379 + {
1.380 + node nodes[4];
1.381 + void *begin = &nodes[0], *end = &nodes[2];
1.382 +
1.383 + cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
1.384 + cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
1.385 +
1.386 + cx_linked_list_insert(&begin, &end, loc_prev, loc_next, nullptr, &nodes[3]);
1.387 + EXPECT_EQ(begin, &nodes[3]);
1.388 + EXPECT_EQ(end, &nodes[2]);
1.389 + EXPECT_EQ(nodes[0].prev, &nodes[3]);
1.390 + EXPECT_EQ(nodes[3].prev, nullptr);
1.391 + EXPECT_EQ(nodes[3].next, &nodes[0]);
1.392 + }
1.393 +}
1.394 +
1.395 +TEST(LinkedList_LowLevel, cx_linked_list_insert_chain) {
1.396 + // insert mid list
1.397 + {
1.398 + node nodes[5];
1.399 + void *begin = &nodes[0], *end = &nodes[2];
1.400 +
1.401 + cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
1.402 + cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
1.403 + cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next);
1.404 +
1.405 + cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3], nullptr);
1.406 + EXPECT_EQ(begin, &nodes[0]);
1.407 + EXPECT_EQ(end, &nodes[2]);
1.408 + EXPECT_EQ(nodes[1].next, &nodes[3]);
1.409 + EXPECT_EQ(nodes[2].prev, &nodes[4]);
1.410 + EXPECT_EQ(nodes[3].prev, &nodes[1]);
1.411 + EXPECT_EQ(nodes[4].next, &nodes[2]);
1.412 + }
1.413 +
1.414 + // insert end
1.415 + {
1.416 + node nodes[5];
1.417 + void *begin = &nodes[0], *end = &nodes[2];
1.418 +
1.419 + cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
1.420 + cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
1.421 + cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next);
1.422 +
1.423 + cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3], nullptr);
1.424 + EXPECT_EQ(begin, &nodes[0]);
1.425 + EXPECT_EQ(end, &nodes[4]);
1.426 + EXPECT_EQ(nodes[2].next, &nodes[3]);
1.427 + EXPECT_EQ(nodes[3].prev, &nodes[2]);
1.428 + EXPECT_EQ(nodes[4].next, nullptr);
1.429 + }
1.430 +
1.431 + // insert begin
1.432 + {
1.433 + node nodes[5];
1.434 + void *begin = &nodes[0], *end = &nodes[2];
1.435 +
1.436 + cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
1.437 + cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
1.438 + cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next);
1.439 +
1.440 + cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, nullptr, &nodes[3], nullptr);
1.441 + EXPECT_EQ(begin, &nodes[3]);
1.442 + EXPECT_EQ(end, &nodes[2]);
1.443 + EXPECT_EQ(nodes[0].prev, &nodes[4]);
1.444 + EXPECT_EQ(nodes[3].prev, nullptr);
1.445 + EXPECT_EQ(nodes[4].next, &nodes[0]);
1.446 + }
1.447 +}
1.448 +
1.449 +TEST(LinkedList_LowLevel, cx_linked_list_first) {
1.450 + auto testdata = create_nodes_test_data(3);
1.451 + auto begin = testdata.begin;
1.452 + EXPECT_EQ(cx_linked_list_first(begin, loc_prev), begin);
1.453 + EXPECT_EQ(cx_linked_list_first(begin->next, loc_prev), begin);
1.454 + EXPECT_EQ(cx_linked_list_first(begin->next->next, loc_prev), begin);
1.455 +}
1.456 +
1.457 +TEST(LinkedList_LowLevel, cx_linked_list_last) {
1.458 + auto testdata = create_nodes_test_data(3);
1.459 + auto begin = testdata.begin;
1.460 + auto end = begin->next->next;
1.461 + EXPECT_EQ(cx_linked_list_last(begin, loc_next), end);
1.462 + EXPECT_EQ(cx_linked_list_last(begin->next, loc_next), end);
1.463 + EXPECT_EQ(cx_linked_list_last(begin->next->next, loc_next), end);
1.464 +}
1.465 +
1.466 +TEST(LinkedList_LowLevel, cx_linked_list_prev) {
1.467 + auto testdata = create_nodes_test_data(3);
1.468 + auto begin = testdata.begin;
1.469 + EXPECT_EQ(cx_linked_list_prev(begin, loc_next, begin), nullptr);
1.470 + EXPECT_EQ(cx_linked_list_prev(begin, loc_next, begin->next), begin);
1.471 + EXPECT_EQ(cx_linked_list_prev(begin, loc_next, begin->next->next), begin->next);
1.472 +}
1.473 +
1.474 +TEST(LinkedList_LowLevel, cx_linked_list_remove) {
1.475 + auto testdata = create_nodes_test_data({2, 4, 6});
1.476 + auto begin = reinterpret_cast<void *>(testdata.begin);
1.477 + auto first = testdata.begin;
1.478 + auto second = first->next;
1.479 + auto third = second->next;
1.480 + auto end = reinterpret_cast<void *>(third);
1.481 +
1.482 + cx_linked_list_remove(&begin, &end, loc_prev, loc_next, second);
1.483 + EXPECT_EQ(begin, first);
1.484 + EXPECT_EQ(end, third);
1.485 + EXPECT_EQ(first->prev, nullptr);
1.486 + EXPECT_EQ(first->next, third);
1.487 + EXPECT_EQ(third->prev, first);
1.488 + EXPECT_EQ(third->next, nullptr);
1.489 +
1.490 + cx_linked_list_remove(&begin, &end, loc_prev, loc_next, third);
1.491 + EXPECT_EQ(begin, first);
1.492 + EXPECT_EQ(end, first);
1.493 + EXPECT_EQ(first->prev, nullptr);
1.494 + EXPECT_EQ(first->next, nullptr);
1.495 +
1.496 + cx_linked_list_remove(&begin, &end, loc_prev, loc_next, first);
1.497 + EXPECT_EQ(begin, nullptr);
1.498 + EXPECT_EQ(end, nullptr);
1.499 +}
1.500 +
1.501 +TEST(LinkedList_LowLevel, cx_linked_list_size) {
1.502 + EXPECT_EQ(cx_linked_list_size(nullptr, loc_next), 0);
1.503 +
1.504 + {
1.505 + auto testdata = create_nodes_test_data(5);
1.506 + EXPECT_EQ(cx_linked_list_size(testdata.begin, loc_next), 5);
1.507 + }
1.508 +
1.509 + {
1.510 + auto testdata = create_nodes_test_data(13);
1.511 + EXPECT_EQ(cx_linked_list_size(testdata.begin, loc_next), 13);
1.512 + }
1.513 +}
1.514 +
1.515 +TEST(LinkedList_LowLevel, cx_linked_list_sort) {
1.516 + int_test_data<1500> testdata;
1.517 + std::array<int, 1500> sorted{};
1.518 + std::partial_sort_copy(testdata.data.begin(), testdata.data.end(), sorted.begin(), sorted.end());
1.519 +
1.520 + auto scrambled = create_nodes_test_data(testdata.data.begin(), testdata.data.end());
1.521 + void *begin = scrambled.begin;
1.522 + void *end = cx_linked_list_last(begin, loc_next);
1.523 +
1.524 + cx_linked_list_sort(&begin, &end, loc_prev, loc_next, loc_data, cx_cmp_int);
1.525 +
1.526 + node *check = reinterpret_cast<node *>(begin);
1.527 + node *check_last = nullptr;
1.528 + cx_for_n (i, sorted.size()) {
1.529 + EXPECT_EQ(check->data, sorted[i]);
1.530 + EXPECT_EQ(check->prev, check_last);
1.531 + if (i < sorted.size() - 1) {
1.532 + ASSERT_NE(check->next, nullptr);
1.533 + }
1.534 + check_last = check;
1.535 + check = check->next;
1.536 + }
1.537 + EXPECT_EQ(check, nullptr);
1.538 + EXPECT_EQ(end, check_last);
1.539 +}
1.540 +
1.541 +TEST(LinkedList_LowLevel, cx_linked_list_reverse) {
1.542 + auto testdata = create_nodes_test_data({2, 4, 6, 8});
1.543 + auto expected = create_nodes_test_data({8, 6, 4, 2});
1.544 +
1.545 + auto begin = reinterpret_cast<void *>(testdata.begin);
1.546 + auto end = cx_linked_list_last(begin, loc_next);
1.547 + auto orig_begin = begin, orig_end = end;
1.548 +
1.549 + cx_linked_list_reverse(&begin, &end, loc_prev, loc_next);
1.550 + EXPECT_EQ(end, orig_begin);
1.551 + EXPECT_EQ(begin, orig_end);
1.552 + EXPECT_EQ(cx_linked_list_compare(begin, expected.begin, loc_next, loc_data, cx_cmp_int), 0);
1.553 +}
1.554 +
1.555 +class HighLevelTest : public ::testing::Test {
1.556 + mutable std::unordered_set<CxList *> lists;
1.557 +protected:
1.558 + CxTestingAllocator testingAllocator;
1.559 +
1.560 + void TearDown() override {
1.561 + for (auto &&l: lists) cxListDestroy(l);
1.562 + EXPECT_TRUE(testingAllocator.verify());
1.563 + }
1.564 +
1.565 + static constexpr size_t testdata_len = 250;
1.566 + int_test_data<testdata_len> testdata;
1.567 +
1.568 + auto autofree(CxList *list) const -> CxList * {
1.569 + if (list != nullptr) lists.insert(list);
1.570 + return list;
1.571 + }
1.572 +
1.573 + auto linkedListFromTestData() const -> CxList * {
1.574 + auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int)));
1.575 + cxListAddArray(list, testdata.data.data(), testdata_len);
1.576 + return list;
1.577 + }
1.578 +
1.579 + auto pointerLinkedListFromTestData() const -> CxList * {
1.580 + auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int *)));
1.581 + cxListStorePointers(list);
1.582 + // note: cannot use cxListAddArray() because we don't have a list of pointers
1.583 + cx_for_n(i, testdata_len) cxListAdd(list, &testdata.data[i]);
1.584 + return list;
1.585 + }
1.586 +
1.587 + auto arrayListFromTestData() const -> CxList * {
1.588 + auto list = autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), testdata_len));
1.589 + cxListAddArray(list, testdata.data.data(), testdata_len);
1.590 + return list;
1.591 + }
1.592 +
1.593 + void verifyCreate(CxList *list) const {
1.594 + EXPECT_EQ(list->content_destructor_type, CX_DESTRUCTOR_NONE);
1.595 + EXPECT_EQ(list->size, 0);
1.596 + EXPECT_EQ(list->allocator, &testingAllocator);
1.597 + EXPECT_EQ(list->cmpfunc, cx_cmp_int);
1.598 + }
1.599 +
1.600 + void verifyAdd(
1.601 + CxList *list,
1.602 + bool as_pointer
1.603 + ) {
1.604 + auto len = testdata_len;
1.605 + cx_for_n (i, len) EXPECT_EQ(cxListAdd(list, &testdata.data[i]), 0);
1.606 + EXPECT_EQ(list->size, len);
1.607 + EXPECT_GE(list->capacity, list->size);
1.608 + cx_for_n (i, len) EXPECT_EQ(*(int *) cxListAt(list, i), testdata.data[i]);
1.609 + cx_for_n (i, len) ++testdata.data[i];
1.610 + if (as_pointer) {
1.611 + cx_for_n (i, len) EXPECT_EQ(*(int *) cxListAt(list, i), testdata.data[i]);
1.612 + } else {
1.613 + cx_for_n (i, len) EXPECT_EQ(*(int *) cxListAt(list, i), testdata.data[i] - 1);
1.614 + }
1.615 + }
1.616 +
1.617 + static void verifyInsert(CxList *list) {
1.618 + int a = 5, b = 47, c = 13, d = 42;
1.619 +
1.620 + EXPECT_NE(cxListInsert(list, 1, &a), 0);
1.621 + EXPECT_EQ(list->size, 0);
1.622 + EXPECT_EQ(cxListInsert(list, 0, &a), 0);
1.623 + EXPECT_EQ(list->size, 1);
1.624 + EXPECT_EQ(cxListInsert(list, 0, &b), 0);
1.625 + EXPECT_EQ(list->size, 2);
1.626 + EXPECT_EQ(cxListInsert(list, 1, &c), 0);
1.627 + EXPECT_EQ(list->size, 3);
1.628 + EXPECT_EQ(cxListInsert(list, 3, &d), 0);
1.629 +
1.630 + ASSERT_EQ(list->size, 4);
1.631 + EXPECT_GE(list->capacity, list->size);
1.632 +
1.633 + EXPECT_EQ(*(int *) cxListAt(list, 0), 47);
1.634 + EXPECT_EQ(*(int *) cxListAt(list, 1), 13);
1.635 + EXPECT_EQ(*(int *) cxListAt(list, 2), 5);
1.636 + EXPECT_EQ(*(int *) cxListAt(list, 3), 42);
1.637 + }
1.638 +
1.639 + static void verifyInsertArray(
1.640 + CxList *list,
1.641 + bool pointers = false
1.642 + ) {
1.643 + int a[5] = {5, 47, 11, 13, 42};
1.644 + int b[5] = {9, 18, 72, 50, 7};
1.645 + int *aptr[5];
1.646 + int *bptr[5];
1.647 + cx_for_n(i, 5) {
1.648 + aptr[i] = &a[i];
1.649 + bptr[i] = &b[i];
1.650 + }
1.651 +
1.652 + size_t inserted;
1.653 +
1.654 + if (pointers) {
1.655 + inserted = cxListInsertArray(list, 0, aptr, 5);
1.656 + } else {
1.657 + inserted = cxListInsertArray(list, 0, a, 5);
1.658 + }
1.659 + EXPECT_EQ(inserted, 5);
1.660 + EXPECT_EQ(*(int *) cxListAt(list, 0), 5);
1.661 + EXPECT_EQ(*(int *) cxListAt(list, 1), 47);
1.662 + EXPECT_EQ(*(int *) cxListAt(list, 2), 11);
1.663 + EXPECT_EQ(*(int *) cxListAt(list, 3), 13);
1.664 + EXPECT_EQ(*(int *) cxListAt(list, 4), 42);
1.665 + if (pointers) {
1.666 + inserted = cxListInsertArray(list, 3, bptr, 5);
1.667 + } else {
1.668 + inserted = cxListInsertArray(list, 3, b, 5);
1.669 + }
1.670 + EXPECT_EQ(inserted, 5);
1.671 + EXPECT_EQ(*(int *) cxListAt(list, 0), 5);
1.672 + EXPECT_EQ(*(int *) cxListAt(list, 1), 47);
1.673 + EXPECT_EQ(*(int *) cxListAt(list, 2), 11);
1.674 + EXPECT_EQ(*(int *) cxListAt(list, 3), 9);
1.675 + EXPECT_EQ(*(int *) cxListAt(list, 4), 18);
1.676 + EXPECT_EQ(*(int *) cxListAt(list, 5), 72);
1.677 + EXPECT_EQ(*(int *) cxListAt(list, 6), 50);
1.678 + EXPECT_EQ(*(int *) cxListAt(list, 7), 7);
1.679 + EXPECT_EQ(*(int *) cxListAt(list, 8), 13);
1.680 + EXPECT_EQ(*(int *) cxListAt(list, 9), 42);
1.681 + }
1.682 +
1.683 + void verifyRemove(CxList *list) const {
1.684 + EXPECT_EQ(cxListRemove(list, 2), 0);
1.685 + EXPECT_EQ(cxListRemove(list, 4), 0);
1.686 + EXPECT_EQ(list->size, testdata_len - 2);
1.687 + EXPECT_GE(list->capacity, list->size);
1.688 + EXPECT_EQ(*(int *) cxListAt(list, 0), testdata.data[0]);
1.689 + EXPECT_EQ(*(int *) cxListAt(list, 1), testdata.data[1]);
1.690 + EXPECT_EQ(*(int *) cxListAt(list, 2), testdata.data[3]);
1.691 + EXPECT_EQ(*(int *) cxListAt(list, 3), testdata.data[4]);
1.692 + EXPECT_EQ(*(int *) cxListAt(list, 4), testdata.data[6]);
1.693 +
1.694 + EXPECT_EQ(cxListRemove(list, 0), 0);
1.695 + EXPECT_EQ(list->size, testdata_len - 3);
1.696 + EXPECT_GE(list->capacity, list->size);
1.697 + EXPECT_EQ(*(int *) cxListAt(list, 0), testdata.data[1]);
1.698 + EXPECT_EQ(*(int *) cxListAt(list, 1), testdata.data[3]);
1.699 +
1.700 + EXPECT_NE(cxListRemove(list, testdata_len), 0);
1.701 + }
1.702 +
1.703 + static void verifySwap(CxList *list) {
1.704 + ASSERT_EQ(list->size, 0);
1.705 +
1.706 + int original[16] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
1.707 + int swapped[16] = {8, 4, 14, 3, 1, 5, 9, 12, 0, 6, 11, 10, 7, 15, 2, 13};
1.708 +
1.709 + // we have to add the items one by one, because it could be a pointer list
1.710 + cx_for_n(i, 16) {
1.711 + cxListAdd(list, &original[i]);
1.712 + }
1.713 +
1.714 + int result;
1.715 +
1.716 + // execute the test two times with different item sizes
1.717 + result = cxListSwap(list, 1, 4);
1.718 + EXPECT_EQ(0, result);
1.719 + result = cxListSwap(list, 2, 14);
1.720 + EXPECT_EQ(0, result);
1.721 + result = cxListSwap(list, 9, 6);
1.722 + EXPECT_EQ(0, result);
1.723 + result = cxListSwap(list, 3, 3);
1.724 + EXPECT_EQ(0, result);
1.725 + result = cxListSwap(list, 10, 11);
1.726 + EXPECT_EQ(0, result);
1.727 + result = cxListSwap(list, 8, 0);
1.728 + EXPECT_EQ(0, result);
1.729 + result = cxListSwap(list, 7, 12);
1.730 + EXPECT_EQ(0, result);
1.731 + result = cxListSwap(list, 13, 15);
1.732 + EXPECT_EQ(0, result);
1.733 +
1.734 + result = cxListSwap(list, 5, 16);
1.735 + EXPECT_NE(0, result);
1.736 + result = cxListSwap(list, 16, 6);
1.737 + EXPECT_NE(0, result);
1.738 + result = cxListSwap(list, 16, 17);
1.739 + EXPECT_NE(0, result);
1.740 +
1.741 + auto iter = cxListBegin(list);
1.742 + cx_foreach(int*, e, iter) {
1.743 + EXPECT_EQ(*e, swapped[iter.index]);
1.744 + }
1.745 + // TODO: replace with backward iterator
1.746 + cx_for_n(i, 16) {
1.747 + EXPECT_EQ(*((int *) cxListAt(list, i)), swapped[i]);
1.748 + }
1.749 + }
1.750 +
1.751 + void verifyAt(CxList *list) const {
1.752 + auto len = testdata_len;
1.753 + EXPECT_EQ(list->size, len);
1.754 + cx_for_n (i, len) {
1.755 + EXPECT_EQ(*(int *) cxListAt(list, i), testdata.data[i]);
1.756 + }
1.757 + EXPECT_EQ(cxListAt(list, list->size), nullptr);
1.758 + }
1.759 +
1.760 + void verifyFind(CxList *list) const {
1.761 + cx_for_n (attempt, 25) {
1.762 + size_t exp = rand() % testdata_len; // NOLINT(cert-msc50-cpp)
1.763 + int val = testdata.data[exp];
1.764 + // randomly picked number could occur earlier in list - find first position
1.765 + cx_for_n (i, exp) {
1.766 + if (testdata.data[i] == val) {
1.767 + exp = i;
1.768 + break;
1.769 + }
1.770 + }
1.771 + EXPECT_EQ(cxListFind(list, &val), exp);
1.772 + }
1.773 + }
1.774 +
1.775 + void verifySort(CxList *list) const {
1.776 + std::array<int, testdata_len> expected{};
1.777 + std::partial_sort_copy(testdata.data.begin(), testdata.data.end(), expected.begin(), expected.end());
1.778 + cxListSort(list);
1.779 + cx_for_n (i, testdata_len) ASSERT_EQ(*(int *) cxListAt(list, i), expected[i]);
1.780 + }
1.781 +
1.782 + void verifyIterator(CxList *list) const {
1.783 + int i = 0;
1.784 + auto iter = cxListBeginMut(list);
1.785 + cx_foreach(int*, x, iter) {
1.786 + ASSERT_EQ(iter.index, (size_t) (i + 1) / 2);
1.787 + ASSERT_EQ(*x, testdata.data[i]);
1.788 + if (i % 2 == 1) cxIteratorFlagRemoval(iter);
1.789 + i++;
1.790 + }
1.791 + auto len = testdata_len;
1.792 + EXPECT_EQ(i, len);
1.793 + ASSERT_EQ(list->size, len / 2);
1.794 + cx_for_n(j, len / 2) ASSERT_EQ(*(int *) cxListAt(list, j), testdata.data[j * 2]);
1.795 + }
1.796 +
1.797 + static void verifyInsertViaIterator(CxList *list) {
1.798 + int newdata[] = {10, 20, 30, 40, 50};
1.799 +
1.800 + auto iter = cxListMutIterator(list, 2);
1.801 + EXPECT_TRUE(cxIteratorValid(iter));
1.802 + EXPECT_EQ(iter.index, 2);
1.803 + EXPECT_EQ(*(int *) cxIteratorCurrent(iter), 2);
1.804 + cxListInsertAfter(&iter, &newdata[0]);
1.805 + EXPECT_TRUE(cxIteratorValid(iter));
1.806 + EXPECT_EQ(iter.index, 2);
1.807 + EXPECT_EQ(*(int *) cxIteratorCurrent(iter), 2);
1.808 + cxListInsertBefore(&iter, &newdata[1]);
1.809 + EXPECT_TRUE(cxIteratorValid(iter));
1.810 + EXPECT_EQ(iter.index, 3);
1.811 + EXPECT_EQ(*(int *) cxIteratorCurrent(iter), 2);
1.812 +
1.813 + iter = cxListBeginMut(list);
1.814 + cxListInsertBefore(&iter, &newdata[2]);
1.815 + EXPECT_TRUE(cxIteratorValid(iter));
1.816 + EXPECT_EQ(iter.index, 1);
1.817 + EXPECT_EQ(*(int *) cxIteratorCurrent(iter), 0);
1.818 + iter = cxListMutIterator(list, list->size);
1.819 + cxListInsertBefore(&iter, &newdata[3]);
1.820 + EXPECT_FALSE(cxIteratorValid(iter));
1.821 + EXPECT_EQ(iter.index, 9);
1.822 + iter = cxListMutIterator(list, list->size);
1.823 + cxListInsertAfter(&iter, &newdata[4]);
1.824 + EXPECT_FALSE(cxIteratorValid(iter));
1.825 + EXPECT_EQ(iter.index, 10);
1.826 +
1.827 + int expdata[] = {30, 0, 1, 20, 2, 10, 3, 4, 40, 50};
1.828 + cx_for_n (j, 10) EXPECT_EQ(*(int *) cxListAt(list, j), expdata[j]);
1.829 + }
1.830 +
1.831 + void verifyReverse(CxList *list) const {
1.832 + cxListReverse(list);
1.833 + cx_for_n(i, testdata_len) {
1.834 + ASSERT_EQ(*(int *) cxListAt(list, i), testdata.data[testdata_len - 1 - i]);
1.835 + }
1.836 + }
1.837 +
1.838 + static void verifyCompare(
1.839 + CxList *left,
1.840 + CxList *right
1.841 + ) {
1.842 + EXPECT_EQ(cxListCompare(left, right), 0);
1.843 + int x = 42;
1.844 + cxListAdd(left, &x);
1.845 + ASSERT_GT(left->size, right->size);
1.846 + EXPECT_GT(cxListCompare(left, right), 0);
1.847 + EXPECT_LT(cxListCompare(right, left), 0);
1.848 + cxListAdd(right, &x);
1.849 + ASSERT_EQ(left->size, right->size);
1.850 + EXPECT_EQ(cxListCompare(left, right), 0);
1.851 + int a = 5, b = 10;
1.852 + cxListInsert(left, 15, &a);
1.853 + cxListInsert(right, 15, &b);
1.854 + ASSERT_EQ(left->size, right->size);
1.855 + EXPECT_LT(cxListCompare(left, right), 0);
1.856 + EXPECT_GT(cxListCompare(right, left), 0);
1.857 + *(int *) cxListAt(left, 15) = 10;
1.858 + EXPECT_EQ(cxListCompare(left, right), 0);
1.859 + }
1.860 +};
1.861 +
1.862 +class LinkedList : public HighLevelTest {
1.863 +};
1.864 +
1.865 +class PointerLinkedList : public HighLevelTest {
1.866 +};
1.867 +
1.868 +class ArrayList : public HighLevelTest {
1.869 +};
1.870 +
1.871 +TEST_F(PointerLinkedList, cxListStorePointers) {
1.872 + auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, 47));
1.873 + EXPECT_FALSE(cxListIsStoringPointers(list));
1.874 + cxListStorePointers(list);
1.875 + EXPECT_EQ(list->itemsize, sizeof(void *));
1.876 + EXPECT_NE(list->cl, nullptr);
1.877 + EXPECT_NE(list->climpl, nullptr);
1.878 + EXPECT_TRUE(cxListIsStoringPointers(list));
1.879 + cxListStoreObjects(list);
1.880 + EXPECT_NE(list->cl, nullptr);
1.881 + EXPECT_EQ(list->climpl, nullptr);
1.882 + EXPECT_FALSE(cxListIsStoringPointers(list));
1.883 +}
1.884 +
1.885 +TEST_F(LinkedList, cxLinkedListCreate) {
1.886 + CxList *list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int)));
1.887 + ASSERT_NE(list, nullptr);
1.888 + EXPECT_EQ(list->itemsize, sizeof(int));
1.889 + EXPECT_EQ(list->capacity, (size_t) -1);
1.890 + verifyCreate(list);
1.891 +}
1.892 +
1.893 +TEST_F(ArrayList, cxArrayListCreate) {
1.894 + CxList *list = autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 8));
1.895 + ASSERT_NE(list, nullptr);
1.896 + EXPECT_EQ(list->itemsize, sizeof(int));
1.897 + EXPECT_EQ(list->capacity, 8);
1.898 + verifyCreate(list);
1.899 +}
1.900 +
1.901 +TEST_F(LinkedList, cxListAdd) {
1.902 + auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int)));
1.903 + verifyAdd(list, false);
1.904 +}
1.905 +
1.906 +TEST_F(PointerLinkedList, cxListAdd) {
1.907 + auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int *)));
1.908 + cxListStorePointers(list);
1.909 + verifyAdd(list, true);
1.910 +}
1.911 +
1.912 +TEST_F(ArrayList, cxListAdd) {
1.913 + auto list = autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 8));
1.914 + verifyAdd(list, false);
1.915 +}
1.916 +
1.917 +TEST_F(LinkedList, cxListInsert) {
1.918 + verifyInsert(autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int))));
1.919 +}
1.920 +
1.921 +TEST_F(PointerLinkedList, cxListInsert) {
1.922 + auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int *)));
1.923 + cxListStorePointers(list);
1.924 + verifyInsert(list);
1.925 +}
1.926 +
1.927 +TEST_F(ArrayList, cxListInsert) {
1.928 + verifyInsert(autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 2)));
1.929 +}
1.930 +
1.931 +TEST_F(LinkedList, cxListInsertArray) {
1.932 + verifyInsertArray(autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int))));
1.933 +}
1.934 +
1.935 +TEST_F(PointerLinkedList, cxListInsertArray) {
1.936 + auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int *)));
1.937 + cxListStorePointers(list);
1.938 + verifyInsertArray(list, true);
1.939 +}
1.940 +
1.941 +TEST_F(ArrayList, cxListInsertArray) {
1.942 + verifyInsertArray(autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 4)));
1.943 +}
1.944 +
1.945 +TEST_F(LinkedList, cxListRemove) {
1.946 + verifyRemove(linkedListFromTestData());
1.947 +}
1.948 +
1.949 +TEST_F(PointerLinkedList, cxListRemove) {
1.950 + verifyRemove(pointerLinkedListFromTestData());
1.951 +}
1.952 +
1.953 +TEST_F(ArrayList, cxListRemove) {
1.954 + verifyRemove(arrayListFromTestData());
1.955 +}
1.956 +
1.957 +TEST_F(LinkedList, cxListSwap) {
1.958 + verifySwap(autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int))));
1.959 +}
1.960 +
1.961 +TEST_F(PointerLinkedList, cxListSwap) {
1.962 + auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int *)));
1.963 + cxListStorePointers(list);
1.964 + verifySwap(list);
1.965 +}
1.966 +
1.967 +TEST_F(ArrayList, cxListSwap) {
1.968 + verifySwap(autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 16)));
1.969 +}
1.970 +
1.971 +TEST_F(LinkedList, cxListSwapNoSBO) {
1.972 + CX_DISABLE_LINKED_LIST_SWAP_SBO = true;
1.973 + verifySwap(autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int))));
1.974 + CX_DISABLE_LINKED_LIST_SWAP_SBO = false;
1.975 +}
1.976 +
1.977 +TEST_F(PointerLinkedList, cxListSwapNoSBO) {
1.978 + auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int *)));
1.979 + cxListStorePointers(list);
1.980 + CX_DISABLE_LINKED_LIST_SWAP_SBO = true;
1.981 + verifySwap(list);
1.982 + CX_DISABLE_LINKED_LIST_SWAP_SBO = false;
1.983 +}
1.984 +
1.985 +TEST_F(ArrayList, cxListSwapNoSBO) {
1.986 + CX_DISABLE_LINKED_LIST_SWAP_SBO = true;
1.987 + verifySwap(autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 16)));
1.988 + CX_DISABLE_LINKED_LIST_SWAP_SBO = false;
1.989 +}
1.990 +
1.991 +TEST_F(LinkedList, cxListAt) {
1.992 + verifyAt(linkedListFromTestData());
1.993 +}
1.994 +
1.995 +TEST_F(PointerLinkedList, cxListAt) {
1.996 + verifyAt(pointerLinkedListFromTestData());
1.997 +}
1.998 +
1.999 +TEST_F(ArrayList, cxListAt) {
1.1000 + verifyAt(arrayListFromTestData());
1.1001 +}
1.1002 +
1.1003 +TEST_F(LinkedList, cxListFind) {
1.1004 + verifyFind(linkedListFromTestData());
1.1005 +}
1.1006 +
1.1007 +TEST_F(PointerLinkedList, cxListFind) {
1.1008 + verifyFind(pointerLinkedListFromTestData());
1.1009 +}
1.1010 +
1.1011 +TEST_F(ArrayList, cxListFind) {
1.1012 + verifyFind(arrayListFromTestData());
1.1013 +}
1.1014 +
1.1015 +TEST_F(LinkedList, cxListSort) {
1.1016 + verifySort(linkedListFromTestData());
1.1017 +}
1.1018 +
1.1019 +TEST_F(PointerLinkedList, cxListSort) {
1.1020 + verifySort(pointerLinkedListFromTestData());
1.1021 +}
1.1022 +
1.1023 +TEST_F(ArrayList, cxListSort) {
1.1024 + verifySort(arrayListFromTestData());
1.1025 +}
1.1026 +
1.1027 +TEST_F(LinkedList, Iterator) {
1.1028 + verifyIterator(linkedListFromTestData());
1.1029 +}
1.1030 +
1.1031 +TEST_F(PointerLinkedList, Iterator) {
1.1032 + verifyIterator(pointerLinkedListFromTestData());
1.1033 +}
1.1034 +
1.1035 +TEST_F(ArrayList, Iterator) {
1.1036 + verifyIterator(arrayListFromTestData());
1.1037 +}
1.1038 +
1.1039 +TEST_F(LinkedList, InsertViaIterator) {
1.1040 + int fivenums[] = {0, 1, 2, 3, 4, 5};
1.1041 + CxList *list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int)));
1.1042 + cxListAddArray(list, fivenums, 5);
1.1043 + verifyInsertViaIterator(list);
1.1044 +}
1.1045 +
1.1046 +TEST_F(PointerLinkedList, InsertViaIterator) {
1.1047 + int fivenums[] = {0, 1, 2, 3, 4, 5};
1.1048 + auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int *)));
1.1049 + cxListStorePointers(list);
1.1050 + // note: cannot use cxListAddArray() because we don't have a list of pointers
1.1051 + cx_for_n(i, 5) cxListAdd(list, &fivenums[i]);
1.1052 + verifyInsertViaIterator(list);
1.1053 +}
1.1054 +
1.1055 +TEST_F(ArrayList, InsertViaIterator) {
1.1056 + int fivenums[] = {0, 1, 2, 3, 4, 5};
1.1057 + CxList *list = autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 4));
1.1058 + cxListAddArray(list, fivenums, 5);
1.1059 + verifyInsertViaIterator(list);
1.1060 +}
1.1061 +
1.1062 +TEST_F(LinkedList, cxListReverse) {
1.1063 + verifyReverse(linkedListFromTestData());
1.1064 +}
1.1065 +
1.1066 +TEST_F(PointerLinkedList, cxListReverse) {
1.1067 + verifyReverse(pointerLinkedListFromTestData());
1.1068 +}
1.1069 +
1.1070 +TEST_F(ArrayList, cxListReverse) {
1.1071 + verifyReverse(arrayListFromTestData());
1.1072 +}
1.1073 +
1.1074 +TEST_F(LinkedList, cxListCompare) {
1.1075 + auto left = linkedListFromTestData();
1.1076 + auto right = linkedListFromTestData();
1.1077 + verifyCompare(left, right);
1.1078 +}
1.1079 +
1.1080 +TEST_F(LinkedList, cxListCompareWithPtrList) {
1.1081 + auto left = linkedListFromTestData();
1.1082 + auto right = pointerLinkedListFromTestData();
1.1083 + verifyCompare(left, right);
1.1084 +}
1.1085 +
1.1086 +TEST_F(LinkedList, cxListCompareWithArrayList) {
1.1087 + auto left = linkedListFromTestData();
1.1088 + auto right = arrayListFromTestData();
1.1089 + verifyCompare(left, right);
1.1090 +}
1.1091 +
1.1092 +TEST_F(PointerLinkedList, cxListCompare) {
1.1093 + auto left = pointerLinkedListFromTestData();
1.1094 + auto right = pointerLinkedListFromTestData();
1.1095 + verifyCompare(left, right);
1.1096 +}
1.1097 +
1.1098 +TEST_F(PointerLinkedList, cxListCompareWithNormalList) {
1.1099 + auto left = pointerLinkedListFromTestData();
1.1100 + auto right = linkedListFromTestData();
1.1101 + verifyCompare(left, right);
1.1102 +}
1.1103 +
1.1104 +TEST_F(PointerLinkedList, cxListCompareWithArrayList) {
1.1105 + auto left = pointerLinkedListFromTestData();
1.1106 + auto right = arrayListFromTestData();
1.1107 + verifyCompare(left, right);
1.1108 +}
1.1109 +
1.1110 +TEST_F(ArrayList, cxListCompare) {
1.1111 + auto left = arrayListFromTestData();
1.1112 + auto right = arrayListFromTestData();
1.1113 + verifyCompare(left, right);
1.1114 +}
1.1115 +
1.1116 +TEST_F(ArrayList, cxListCompareWithPtrList) {
1.1117 + auto left = arrayListFromTestData();
1.1118 + auto right = pointerLinkedListFromTestData();
1.1119 + verifyCompare(left, right);
1.1120 +}
1.1121 +
1.1122 +TEST_F(ArrayList, cxListCompareWithNormalList) {
1.1123 + auto left = arrayListFromTestData();
1.1124 + auto right = linkedListFromTestData();
1.1125 + verifyCompare(left, right);
1.1126 +}
1.1127 +
1.1128 +TEST_F(PointerLinkedList, NoDestructor) {
1.1129 + void *item = cxMalloc(&testingAllocator, sizeof(int));
1.1130 + auto list = cxLinkedListCreate(cxDefaultAllocator, cx_cmp_int, sizeof(int *));
1.1131 + cxListStorePointers(list);
1.1132 + cxListAdd(list, item);
1.1133 + ASSERT_FALSE(testingAllocator.verify());
1.1134 + cxListDestroy(list);
1.1135 + EXPECT_FALSE(testingAllocator.verify());
1.1136 + cxFree(&testingAllocator, item);
1.1137 + EXPECT_TRUE(testingAllocator.verify());
1.1138 +}
1.1139 +
1.1140 +TEST_F(PointerLinkedList, SimpleDestructor) {
1.1141 + int item = 0;
1.1142 + auto list = cxLinkedListCreate(cxDefaultAllocator, cx_cmp_int, sizeof(int *));
1.1143 + cxListStorePointers(list);
1.1144 + list->content_destructor_type = CX_DESTRUCTOR_SIMPLE;
1.1145 + list->simple_destructor = [](void *elem) { *(int *) elem = 42; };
1.1146 + cxListAdd(list, &item);
1.1147 + cxListDestroy(list);
1.1148 + EXPECT_EQ(item, 42);
1.1149 +}
1.1150 +
1.1151 +TEST_F(PointerLinkedList, AdvancedDestructor) {
1.1152 + void *item = cxMalloc(&testingAllocator, sizeof(int));
1.1153 + auto list = cxLinkedListCreate(cxDefaultAllocator, cx_cmp_int, sizeof(int *));
1.1154 + cxListStorePointers(list);
1.1155 + list->content_destructor_type = CX_DESTRUCTOR_ADVANCED;
1.1156 + list->advanced_destructor.data = &testingAllocator;
1.1157 + list->advanced_destructor.func = (cx_destructor_func2) cxFree;
1.1158 + cxListAdd(list, item);
1.1159 + ASSERT_FALSE(testingAllocator.verify());
1.1160 + cxListDestroy(list);
1.1161 + EXPECT_TRUE(testingAllocator.verify());
1.1162 +}
