1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/tests/test_list.cpp Tue Feb 07 21:55:37 2023 +0100 1.3 @@ -0,0 +1,1077 @@ 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 +}