1.1 --- a/test/test_list.cpp Tue Feb 07 21:53:06 2023 +0100
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,1077 +0,0 @@
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 - void verifyAt(CxList *list) const {
1.704 - auto len = testdata_len;
1.705 - EXPECT_EQ(list->size, len);
1.706 - cx_for_n (i, len) {
1.707 - EXPECT_EQ(*(int *) cxListAt(list, i), testdata.data[i]);
1.708 - }
1.709 - EXPECT_EQ(cxListAt(list, list->size), nullptr);
1.710 - }
1.711 -
1.712 - void verifyFind(CxList *list) const {
1.713 - cx_for_n (attempt, 25) {
1.714 - size_t exp = rand() % testdata_len; // NOLINT(cert-msc50-cpp)
1.715 - int val = testdata.data[exp];
1.716 - // randomly picked number could occur earlier in list - find first position
1.717 - cx_for_n (i, exp) {
1.718 - if (testdata.data[i] == val) {
1.719 - exp = i;
1.720 - break;
1.721 - }
1.722 - }
1.723 - EXPECT_EQ(cxListFind(list, &val), exp);
1.724 - }
1.725 - }
1.726 -
1.727 - void verifySort(CxList *list) const {
1.728 - std::array<int, testdata_len> expected{};
1.729 - std::partial_sort_copy(testdata.data.begin(), testdata.data.end(), expected.begin(), expected.end());
1.730 - cxListSort(list);
1.731 - cx_for_n (i, testdata_len) ASSERT_EQ(*(int *) cxListAt(list, i), expected[i]);
1.732 - }
1.733 -
1.734 - void verifyIterator(CxList *list) const {
1.735 - int i = 0;
1.736 - auto iter = cxListBeginMut(list);
1.737 - cx_foreach(int*, x, iter) {
1.738 - ASSERT_EQ(iter.index, (size_t) (i + 1) / 2);
1.739 - ASSERT_EQ(*x, testdata.data[i]);
1.740 - if (i % 2 == 1) cxIteratorFlagRemoval(iter);
1.741 - i++;
1.742 - }
1.743 - auto len = testdata_len;
1.744 - EXPECT_EQ(i, len);
1.745 - ASSERT_EQ(list->size, len / 2);
1.746 - cx_for_n(j, len / 2) ASSERT_EQ(*(int *) cxListAt(list, j), testdata.data[j * 2]);
1.747 - }
1.748 -
1.749 - static void verifyInsertViaIterator(CxList *list) {
1.750 - int newdata[] = {10, 20, 30, 40, 50};
1.751 -
1.752 - auto iter = cxListMutIterator(list, 2);
1.753 - EXPECT_TRUE(cxIteratorValid(iter));
1.754 - EXPECT_EQ(iter.index, 2);
1.755 - EXPECT_EQ(*(int *) cxIteratorCurrent(iter), 2);
1.756 - cxListInsertAfter(&iter, &newdata[0]);
1.757 - EXPECT_TRUE(cxIteratorValid(iter));
1.758 - EXPECT_EQ(iter.index, 2);
1.759 - EXPECT_EQ(*(int *) cxIteratorCurrent(iter), 2);
1.760 - cxListInsertBefore(&iter, &newdata[1]);
1.761 - EXPECT_TRUE(cxIteratorValid(iter));
1.762 - EXPECT_EQ(iter.index, 3);
1.763 - EXPECT_EQ(*(int *) cxIteratorCurrent(iter), 2);
1.764 -
1.765 - iter = cxListBeginMut(list);
1.766 - cxListInsertBefore(&iter, &newdata[2]);
1.767 - EXPECT_TRUE(cxIteratorValid(iter));
1.768 - EXPECT_EQ(iter.index, 1);
1.769 - EXPECT_EQ(*(int *) cxIteratorCurrent(iter), 0);
1.770 - iter = cxListMutIterator(list, list->size);
1.771 - cxListInsertBefore(&iter, &newdata[3]);
1.772 - EXPECT_FALSE(cxIteratorValid(iter));
1.773 - EXPECT_EQ(iter.index, 9);
1.774 - iter = cxListMutIterator(list, list->size);
1.775 - cxListInsertAfter(&iter, &newdata[4]);
1.776 - EXPECT_FALSE(cxIteratorValid(iter));
1.777 - EXPECT_EQ(iter.index, 10);
1.778 -
1.779 - int expdata[] = {30, 0, 1, 20, 2, 10, 3, 4, 40, 50};
1.780 - cx_for_n (j, 10) EXPECT_EQ(*(int *) cxListAt(list, j), expdata[j]);
1.781 - }
1.782 -
1.783 - void verifyReverse(CxList *list) const {
1.784 - cxListReverse(list);
1.785 - cx_for_n(i, testdata_len) {
1.786 - ASSERT_EQ(*(int *) cxListAt(list, i), testdata.data[testdata_len - 1 - i]);
1.787 - }
1.788 - }
1.789 -
1.790 - static void verifyCompare(
1.791 - CxList *left,
1.792 - CxList *right
1.793 - ) {
1.794 - EXPECT_EQ(cxListCompare(left, right), 0);
1.795 - int x = 42;
1.796 - cxListAdd(left, &x);
1.797 - ASSERT_GT(left->size, right->size);
1.798 - EXPECT_GT(cxListCompare(left, right), 0);
1.799 - EXPECT_LT(cxListCompare(right, left), 0);
1.800 - cxListAdd(right, &x);
1.801 - ASSERT_EQ(left->size, right->size);
1.802 - EXPECT_EQ(cxListCompare(left, right), 0);
1.803 - int a = 5, b = 10;
1.804 - cxListInsert(left, 15, &a);
1.805 - cxListInsert(right, 15, &b);
1.806 - ASSERT_EQ(left->size, right->size);
1.807 - EXPECT_LT(cxListCompare(left, right), 0);
1.808 - EXPECT_GT(cxListCompare(right, left), 0);
1.809 - *(int *) cxListAt(left, 15) = 10;
1.810 - EXPECT_EQ(cxListCompare(left, right), 0);
1.811 - }
1.812 -};
1.813 -
1.814 -class LinkedList : public HighLevelTest {
1.815 -};
1.816 -
1.817 -class PointerLinkedList : public HighLevelTest {
1.818 -};
1.819 -
1.820 -class ArrayList : public HighLevelTest {
1.821 -};
1.822 -
1.823 -TEST_F(PointerLinkedList, cxListStorePointers) {
1.824 - auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, 47));
1.825 - EXPECT_FALSE(cxListIsStoringPointers(list));
1.826 - cxListStorePointers(list);
1.827 - EXPECT_EQ(list->itemsize, sizeof(void *));
1.828 - EXPECT_NE(list->cl, nullptr);
1.829 - EXPECT_NE(list->climpl, nullptr);
1.830 - EXPECT_TRUE(cxListIsStoringPointers(list));
1.831 - cxListStoreObjects(list);
1.832 - EXPECT_NE(list->cl, nullptr);
1.833 - EXPECT_EQ(list->climpl, nullptr);
1.834 - EXPECT_FALSE(cxListIsStoringPointers(list));
1.835 -}
1.836 -
1.837 -TEST_F(LinkedList, cxLinkedListCreate) {
1.838 - CxList *list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int)));
1.839 - ASSERT_NE(list, nullptr);
1.840 - EXPECT_EQ(list->itemsize, sizeof(int));
1.841 - EXPECT_EQ(list->capacity, (size_t) -1);
1.842 - verifyCreate(list);
1.843 -}
1.844 -
1.845 -TEST_F(ArrayList, cxArrayListCreate) {
1.846 - CxList *list = autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 8));
1.847 - ASSERT_NE(list, nullptr);
1.848 - EXPECT_EQ(list->itemsize, sizeof(int));
1.849 - EXPECT_EQ(list->capacity, 8);
1.850 - verifyCreate(list);
1.851 -}
1.852 -
1.853 -TEST_F(LinkedList, cxListAdd) {
1.854 - auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int)));
1.855 - verifyAdd(list, false);
1.856 -}
1.857 -
1.858 -TEST_F(PointerLinkedList, cxListAdd) {
1.859 - auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int *)));
1.860 - cxListStorePointers(list);
1.861 - verifyAdd(list, true);
1.862 -}
1.863 -
1.864 -TEST_F(ArrayList, cxListAdd) {
1.865 - auto list = autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 8));
1.866 - verifyAdd(list, false);
1.867 -}
1.868 -
1.869 -TEST_F(LinkedList, cxListInsert) {
1.870 - verifyInsert(autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int))));
1.871 -}
1.872 -
1.873 -TEST_F(PointerLinkedList, cxListInsert) {
1.874 - auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int *)));
1.875 - cxListStorePointers(list);
1.876 - verifyInsert(list);
1.877 -}
1.878 -
1.879 -TEST_F(ArrayList, cxListInsert) {
1.880 - verifyInsert(autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 2)));
1.881 -}
1.882 -
1.883 -TEST_F(LinkedList, cxListInsertArray) {
1.884 - verifyInsertArray(autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int))));
1.885 -}
1.886 -
1.887 -TEST_F(PointerLinkedList, cxListInsertArray) {
1.888 - auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int *)));
1.889 - cxListStorePointers(list);
1.890 - verifyInsertArray(list, true);
1.891 -}
1.892 -
1.893 -TEST_F(ArrayList, cxListInsertArray) {
1.894 - verifyInsertArray(autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 4)));
1.895 -}
1.896 -
1.897 -TEST_F(LinkedList, cxListRemove) {
1.898 - verifyRemove(linkedListFromTestData());
1.899 -}
1.900 -
1.901 -TEST_F(PointerLinkedList, cxListRemove) {
1.902 - verifyRemove(pointerLinkedListFromTestData());
1.903 -}
1.904 -
1.905 -TEST_F(ArrayList, cxListRemove) {
1.906 - verifyRemove(arrayListFromTestData());
1.907 -}
1.908 -
1.909 -TEST_F(LinkedList, cxListAt) {
1.910 - verifyAt(linkedListFromTestData());
1.911 -}
1.912 -
1.913 -TEST_F(PointerLinkedList, cxListAt) {
1.914 - verifyAt(pointerLinkedListFromTestData());
1.915 -}
1.916 -
1.917 -TEST_F(ArrayList, cxListAt) {
1.918 - verifyAt(arrayListFromTestData());
1.919 -}
1.920 -
1.921 -TEST_F(LinkedList, cxListFind) {
1.922 - verifyFind(linkedListFromTestData());
1.923 -}
1.924 -
1.925 -TEST_F(PointerLinkedList, cxListFind) {
1.926 - verifyFind(pointerLinkedListFromTestData());
1.927 -}
1.928 -
1.929 -TEST_F(ArrayList, cxListFind) {
1.930 - verifyFind(arrayListFromTestData());
1.931 -}
1.932 -
1.933 -TEST_F(LinkedList, cxListSort) {
1.934 - verifySort(linkedListFromTestData());
1.935 -}
1.936 -
1.937 -TEST_F(PointerLinkedList, cxListSort) {
1.938 - verifySort(pointerLinkedListFromTestData());
1.939 -}
1.940 -
1.941 -TEST_F(ArrayList, cxListSort) {
1.942 - verifySort(arrayListFromTestData());
1.943 -}
1.944 -
1.945 -TEST_F(LinkedList, Iterator) {
1.946 - verifyIterator(linkedListFromTestData());
1.947 -}
1.948 -
1.949 -TEST_F(PointerLinkedList, Iterator) {
1.950 - verifyIterator(pointerLinkedListFromTestData());
1.951 -}
1.952 -
1.953 -TEST_F(ArrayList, Iterator) {
1.954 - verifyIterator(arrayListFromTestData());
1.955 -}
1.956 -
1.957 -TEST_F(LinkedList, InsertViaIterator) {
1.958 - int fivenums[] = {0, 1, 2, 3, 4, 5};
1.959 - CxList *list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int)));
1.960 - cxListAddArray(list, fivenums, 5);
1.961 - verifyInsertViaIterator(list);
1.962 -}
1.963 -
1.964 -TEST_F(PointerLinkedList, InsertViaIterator) {
1.965 - int fivenums[] = {0, 1, 2, 3, 4, 5};
1.966 - auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int *)));
1.967 - cxListStorePointers(list);
1.968 - // note: cannot use cxListAddArray() because we don't have a list of pointers
1.969 - cx_for_n(i, 5) cxListAdd(list, &fivenums[i]);
1.970 - verifyInsertViaIterator(list);
1.971 -}
1.972 -
1.973 -TEST_F(ArrayList, InsertViaIterator) {
1.974 - int fivenums[] = {0, 1, 2, 3, 4, 5};
1.975 - CxList *list = autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 4));
1.976 - cxListAddArray(list, fivenums, 5);
1.977 - verifyInsertViaIterator(list);
1.978 -}
1.979 -
1.980 -TEST_F(LinkedList, cxListReverse) {
1.981 - verifyReverse(linkedListFromTestData());
1.982 -}
1.983 -
1.984 -TEST_F(PointerLinkedList, cxListReverse) {
1.985 - verifyReverse(pointerLinkedListFromTestData());
1.986 -}
1.987 -
1.988 -TEST_F(ArrayList, cxListReverse) {
1.989 - verifyReverse(arrayListFromTestData());
1.990 -}
1.991 -
1.992 -TEST_F(LinkedList, cxListCompare) {
1.993 - auto left = linkedListFromTestData();
1.994 - auto right = linkedListFromTestData();
1.995 - verifyCompare(left, right);
1.996 -}
1.997 -
1.998 -TEST_F(LinkedList, cxListCompareWithPtrList) {
1.999 - auto left = linkedListFromTestData();
1.1000 - auto right = pointerLinkedListFromTestData();
1.1001 - verifyCompare(left, right);
1.1002 -}
1.1003 -
1.1004 -TEST_F(LinkedList, cxListCompareWithArrayList) {
1.1005 - auto left = linkedListFromTestData();
1.1006 - auto right = arrayListFromTestData();
1.1007 - verifyCompare(left, right);
1.1008 -}
1.1009 -
1.1010 -TEST_F(PointerLinkedList, cxListCompare) {
1.1011 - auto left = pointerLinkedListFromTestData();
1.1012 - auto right = pointerLinkedListFromTestData();
1.1013 - verifyCompare(left, right);
1.1014 -}
1.1015 -
1.1016 -TEST_F(PointerLinkedList, cxListCompareWithNormalList) {
1.1017 - auto left = pointerLinkedListFromTestData();
1.1018 - auto right = linkedListFromTestData();
1.1019 - verifyCompare(left, right);
1.1020 -}
1.1021 -
1.1022 -TEST_F(PointerLinkedList, cxListCompareWithArrayList) {
1.1023 - auto left = pointerLinkedListFromTestData();
1.1024 - auto right = arrayListFromTestData();
1.1025 - verifyCompare(left, right);
1.1026 -}
1.1027 -
1.1028 -TEST_F(ArrayList, cxListCompare) {
1.1029 - auto left = arrayListFromTestData();
1.1030 - auto right = arrayListFromTestData();
1.1031 - verifyCompare(left, right);
1.1032 -}
1.1033 -
1.1034 -TEST_F(ArrayList, cxListCompareWithPtrList) {
1.1035 - auto left = arrayListFromTestData();
1.1036 - auto right = pointerLinkedListFromTestData();
1.1037 - verifyCompare(left, right);
1.1038 -}
1.1039 -
1.1040 -TEST_F(ArrayList, cxListCompareWithNormalList) {
1.1041 - auto left = arrayListFromTestData();
1.1042 - auto right = linkedListFromTestData();
1.1043 - verifyCompare(left, right);
1.1044 -}
1.1045 -
1.1046 -TEST_F(PointerLinkedList, NoDestructor) {
1.1047 - void *item = cxMalloc(&testingAllocator, sizeof(int));
1.1048 - auto list = cxLinkedListCreate(cxDefaultAllocator, cx_cmp_int, sizeof(int *));
1.1049 - cxListStorePointers(list);
1.1050 - cxListAdd(list, item);
1.1051 - ASSERT_FALSE(testingAllocator.verify());
1.1052 - cxListDestroy(list);
1.1053 - EXPECT_FALSE(testingAllocator.verify());
1.1054 - cxFree(&testingAllocator, item);
1.1055 - EXPECT_TRUE(testingAllocator.verify());
1.1056 -}
1.1057 -
1.1058 -TEST_F(PointerLinkedList, SimpleDestructor) {
1.1059 - int item = 0;
1.1060 - auto list = cxLinkedListCreate(cxDefaultAllocator, cx_cmp_int, sizeof(int *));
1.1061 - cxListStorePointers(list);
1.1062 - list->content_destructor_type = CX_DESTRUCTOR_SIMPLE;
1.1063 - list->simple_destructor = [](void *elem) { *(int *) elem = 42; };
1.1064 - cxListAdd(list, &item);
1.1065 - cxListDestroy(list);
1.1066 - EXPECT_EQ(item, 42);
1.1067 -}
1.1068 -
1.1069 -TEST_F(PointerLinkedList, AdvancedDestructor) {
1.1070 - void *item = cxMalloc(&testingAllocator, sizeof(int));
1.1071 - auto list = cxLinkedListCreate(cxDefaultAllocator, cx_cmp_int, sizeof(int *));
1.1072 - cxListStorePointers(list);
1.1073 - list->content_destructor_type = CX_DESTRUCTOR_ADVANCED;
1.1074 - list->advanced_destructor.data = &testingAllocator;
1.1075 - list->advanced_destructor.func = (cx_destructor_func2) cxFree;
1.1076 - cxListAdd(list, item);
1.1077 - ASSERT_FALSE(testingAllocator.verify());
1.1078 - cxListDestroy(list);
1.1079 - EXPECT_TRUE(testingAllocator.verify());
1.1080 -}
