1.1 --- a/tests/test_list.cpp Sun Jan 07 11:01:33 2024 +0100
1.2 +++ b/tests/test_list.cpp Tue Jan 09 00:01:03 2024 +0100
1.3 @@ -38,523 +38,6 @@
1.4 #include <unordered_set>
1.5 #include <algorithm>
1.6
1.7 -struct node {
1.8 - node *next = NULL;
1.9 - node *prev = NULL;
1.10 - int data = 0;
1.11 -};
1.12 -
1.13 -const ptrdiff_t loc_prev = offsetof(struct node, prev);
1.14 -const ptrdiff_t loc_next = offsetof(struct node, next);
1.15 -const ptrdiff_t loc_data = offsetof(struct node, data);
1.16 -
1.17 -struct node_test_data {
1.18 - node *begin = NULL;
1.19 -
1.20 - explicit node_test_data(node *begin) : begin(begin) {
1.21 - auto n = begin;
1.22 - while (n != NULL) {
1.23 - nodes.push_back(n);
1.24 - n = n->next;
1.25 - }
1.26 - }
1.27 -
1.28 - node_test_data(node_test_data &) = delete;
1.29 -
1.30 - node_test_data(node_test_data &&) = default;
1.31 -
1.32 - ~node_test_data() {
1.33 - for (auto &&n: nodes) delete n;
1.34 - }
1.35 -
1.36 -private:
1.37 - std::vector<node *> nodes;
1.38 -};
1.39 -
1.40 -static node_test_data create_nodes_test_data(size_t len) {
1.41 - if (len == 0) return node_test_data{NULL};
1.42 - auto begin = new node;
1.43 - auto prev = begin;
1.44 - for (size_t i = 1; i < len; i++) {
1.45 - auto n = new node;
1.46 - cx_linked_list_link(prev, n, loc_prev, loc_next);
1.47 - prev = n;
1.48 - }
1.49 - return node_test_data{begin};
1.50 -}
1.51 -
1.52 -template<typename InputIter>
1.53 -static node_test_data create_nodes_test_data(
1.54 - InputIter begin,
1.55 - InputIter end
1.56 -) {
1.57 - if (begin == end) return node_test_data{NULL};
1.58 - node *first = new node;
1.59 - first->data = *begin;
1.60 - node *prev = first;
1.61 - begin++;
1.62 - for (; begin != end; begin++) {
1.63 - auto n = new node;
1.64 - n->data = *begin;
1.65 - cx_linked_list_link(prev, n, loc_prev, loc_next);
1.66 - prev = n;
1.67 - }
1.68 - return node_test_data{first};
1.69 -}
1.70 -
1.71 -static node_test_data create_nodes_test_data(std::initializer_list<int> data) {
1.72 - return create_nodes_test_data(data.begin(), data.end());
1.73 -}
1.74 -
1.75 -template<size_t N>
1.76 -struct int_test_data {
1.77 - std::array<int, N> data;
1.78 -
1.79 - int_test_data() {
1.80 - cx_for_n (i, N) data[i] = ::rand(); // NOLINT(cert-msc50-cpp)
1.81 - }
1.82 -};
1.83 -
1.84 -TEST(LinkedList_LowLevel, link_unlink) {
1.85 - node a, b, c;
1.86 -
1.87 - cx_linked_list_link(&a, &b, loc_prev, loc_next);
1.88 - CX_TEST_ASSERT(a.prev == NULL);
1.89 - CX_TEST_ASSERT(a.next == &b);
1.90 - CX_TEST_ASSERT(b.prev == &a);
1.91 - CX_TEST_ASSERT(b.next == NULL);
1.92 -
1.93 - cx_linked_list_unlink(&a, &b, loc_prev, loc_next);
1.94 - CX_TEST_ASSERT(a.prev == NULL);
1.95 - CX_TEST_ASSERT(a.next == NULL);
1.96 - CX_TEST_ASSERT(b.prev == NULL);
1.97 - CX_TEST_ASSERT(b.next == NULL);
1.98 -
1.99 - cx_linked_list_link(&b, &c, loc_prev, loc_next);
1.100 - cx_linked_list_link(&a, &b, loc_prev, loc_next);
1.101 - cx_linked_list_unlink(&b, &c, loc_prev, loc_next);
1.102 - CX_TEST_ASSERT(a.prev == NULL);
1.103 - CX_TEST_ASSERT(a.next == &b);
1.104 - CX_TEST_ASSERT(b.prev == &a);
1.105 - CX_TEST_ASSERT(b.next == NULL);
1.106 - CX_TEST_ASSERT(c.prev == NULL);
1.107 - CX_TEST_ASSERT(c.next == NULL);
1.108 -}
1.109 -
1.110 -TEST(LinkedList_LowLevel, cx_linked_list_at) {
1.111 - node a, b, c, d;
1.112 - cx_linked_list_link(&a, &b, loc_prev, loc_next);
1.113 - cx_linked_list_link(&b, &c, loc_prev, loc_next);
1.114 - cx_linked_list_link(&c, &d, loc_prev, loc_next);
1.115 -
1.116 - EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 0), &a);
1.117 - EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 1), &b);
1.118 - EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 2), &c);
1.119 - EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 3), &d);
1.120 - EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 4), NULL);
1.121 -
1.122 - EXPECT_EQ(cx_linked_list_at(&b, 1, loc_prev, 0), &a);
1.123 - EXPECT_EQ(cx_linked_list_at(&b, 1, loc_next, 1), &b);
1.124 - EXPECT_EQ(cx_linked_list_at(&b, 1, loc_next, 2), &c);
1.125 - EXPECT_EQ(cx_linked_list_at(&b, 1, loc_next, 3), &d);
1.126 - EXPECT_EQ(cx_linked_list_at(&b, 1, loc_next, 4), NULL);
1.127 -
1.128 - EXPECT_EQ(cx_linked_list_at(&d, 3, loc_prev, 0), &a);
1.129 - EXPECT_EQ(cx_linked_list_at(&d, 3, loc_prev, 1), &b);
1.130 -}
1.131 -
1.132 -TEST(LinkedList_LowLevel, cx_linked_list_find) {
1.133 - auto testdata = create_nodes_test_data({2, 4, 6, 8});
1.134 - auto list = testdata.begin;
1.135 - int s;
1.136 -
1.137 - s = 2;
1.138 - EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s), 0);
1.139 - s = 4;
1.140 - EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s), 1);
1.141 - s = 6;
1.142 - EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s), 2);
1.143 - s = 8;
1.144 - EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s), 3);
1.145 - s = 10;
1.146 - EXPECT_LT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s), 0);
1.147 - s = -2;
1.148 - EXPECT_LT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s), 0);
1.149 -}
1.150 -
1.151 -TEST(LinkedList_LowLevel, cx_linked_list_compare) {
1.152 - auto ta = create_nodes_test_data({2, 4, 6, 8});
1.153 - auto tb = create_nodes_test_data({2, 4, 6});
1.154 - auto tc = create_nodes_test_data({2, 4, 6, 9});
1.155 - auto la = ta.begin, lb = tb.begin, lc = tc.begin;
1.156 -
1.157 - EXPECT_GT(cx_linked_list_compare(la, lb, loc_next, loc_data, cx_cmp_int), 0);
1.158 - EXPECT_LT(cx_linked_list_compare(lb, la, loc_next, loc_data, cx_cmp_int), 0);
1.159 - EXPECT_GT(cx_linked_list_compare(lc, la, loc_next, loc_data, cx_cmp_int), 0);
1.160 - EXPECT_LT(cx_linked_list_compare(la, lc, loc_next, loc_data, cx_cmp_int), 0);
1.161 - EXPECT_EQ(cx_linked_list_compare(la, la, loc_next, loc_data, cx_cmp_int), 0);
1.162 -}
1.163 -
1.164 -TEST(LinkedList_LowLevel, cx_linked_list_add) {
1.165 - // test with begin, end / prev, next
1.166 - {
1.167 - node nodes[4];
1.168 - void *begin = NULL, *end = NULL;
1.169 -
1.170 - cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[0]);
1.171 - CX_TEST_ASSERT(begin == &nodes[0]);
1.172 - CX_TEST_ASSERT(end == &nodes[0]);
1.173 - CX_TEST_ASSERT(nodes[0].prev == NULL);
1.174 - CX_TEST_ASSERT(nodes[0].next == NULL);
1.175 -
1.176 - cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[1]);
1.177 - CX_TEST_ASSERT(begin == &nodes[0]);
1.178 - CX_TEST_ASSERT(end == &nodes[1]);
1.179 - CX_TEST_ASSERT(nodes[0].next == &nodes[1]);
1.180 - CX_TEST_ASSERT(nodes[1].prev == &nodes[0]);
1.181 - }
1.182 -
1.183 - // test with begin only / prev, next
1.184 - {
1.185 - node nodes[4];
1.186 - void *begin = NULL;
1.187 -
1.188 - cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[0]);
1.189 - CX_TEST_ASSERT(begin == &nodes[0]);
1.190 - cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[1]);
1.191 - CX_TEST_ASSERT(begin == &nodes[0]);
1.192 - CX_TEST_ASSERT(nodes[0].next == &nodes[1]);
1.193 - CX_TEST_ASSERT(nodes[1].prev == &nodes[0]);
1.194 -
1.195 - cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[2]);
1.196 - CX_TEST_ASSERT(nodes[1].next == &nodes[2]);
1.197 - CX_TEST_ASSERT(nodes[2].prev == &nodes[1]);
1.198 - }
1.199 -
1.200 - // test with end only / prev, next
1.201 - {
1.202 - node nodes[4];
1.203 - void *end = NULL;
1.204 -
1.205 - cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[0]);
1.206 - CX_TEST_ASSERT(end == &nodes[0]);
1.207 - cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[1]);
1.208 - CX_TEST_ASSERT(end == &nodes[1]);
1.209 - CX_TEST_ASSERT(nodes[0].next == &nodes[1]);
1.210 - CX_TEST_ASSERT(nodes[1].prev == &nodes[0]);
1.211 -
1.212 - cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[2]);
1.213 - CX_TEST_ASSERT(end == &nodes[2]);
1.214 - CX_TEST_ASSERT(nodes[1].next == &nodes[2]);
1.215 - CX_TEST_ASSERT(nodes[2].prev == &nodes[1]);
1.216 - }
1.217 -
1.218 - // test with begin, end / next
1.219 - {
1.220 - node nodes[4];
1.221 - void *begin = NULL, *end = NULL;
1.222 -
1.223 - cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[0]);
1.224 - CX_TEST_ASSERT(begin == &nodes[0]);
1.225 - CX_TEST_ASSERT(end == &nodes[0]);
1.226 - cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[1]);
1.227 - CX_TEST_ASSERT(end == &nodes[1]);
1.228 - CX_TEST_ASSERT(nodes[0].next == &nodes[1]);
1.229 - CX_TEST_ASSERT(nodes[1].prev == NULL);
1.230 - }
1.231 -}
1.232 -
1.233 -TEST(LinkedList_LowLevel, cx_linked_list_prepend) {
1.234 - // test with begin, end / prev, next
1.235 - {
1.236 - node nodes[4];
1.237 - void *begin = NULL, *end = NULL;
1.238 -
1.239 - cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[0]);
1.240 - CX_TEST_ASSERT(begin == &nodes[0]);
1.241 - CX_TEST_ASSERT(end == &nodes[0]);
1.242 - CX_TEST_ASSERT(nodes[0].prev == NULL);
1.243 - CX_TEST_ASSERT(nodes[0].next == NULL);
1.244 -
1.245 - cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[1]);
1.246 - CX_TEST_ASSERT(begin == &nodes[1]);
1.247 - CX_TEST_ASSERT(end == &nodes[0]);
1.248 - CX_TEST_ASSERT(nodes[1].next == &nodes[0]);
1.249 - CX_TEST_ASSERT(nodes[0].prev == &nodes[1]);
1.250 - }
1.251 -
1.252 - // test with begin only / prev, next
1.253 - {
1.254 - node nodes[4];
1.255 - void *begin = NULL;
1.256 -
1.257 - cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[0]);
1.258 - CX_TEST_ASSERT(begin == &nodes[0]);
1.259 - cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[1]);
1.260 - CX_TEST_ASSERT(begin == &nodes[1]);
1.261 - CX_TEST_ASSERT(nodes[1].next == &nodes[0]);
1.262 - CX_TEST_ASSERT(nodes[0].prev == &nodes[1]);
1.263 -
1.264 - cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[2]);
1.265 - CX_TEST_ASSERT(begin == &nodes[2]);
1.266 - CX_TEST_ASSERT(nodes[2].next == &nodes[1]);
1.267 - CX_TEST_ASSERT(nodes[1].prev == &nodes[2]);
1.268 - }
1.269 -
1.270 - // test with end only / prev, next
1.271 - {
1.272 - node nodes[4];
1.273 - void *end = NULL;
1.274 -
1.275 - cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[0]);
1.276 - CX_TEST_ASSERT(end == &nodes[0]);
1.277 - cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[1]);
1.278 - CX_TEST_ASSERT(end == &nodes[0]);
1.279 - CX_TEST_ASSERT(nodes[1].next == &nodes[0]);
1.280 - CX_TEST_ASSERT(nodes[0].prev == &nodes[1]);
1.281 -
1.282 - cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[2]);
1.283 - CX_TEST_ASSERT(end == &nodes[0]);
1.284 - CX_TEST_ASSERT(nodes[2].next == &nodes[1]);
1.285 - CX_TEST_ASSERT(nodes[1].prev == &nodes[2]);
1.286 - }
1.287 -
1.288 - // test with begin, end / next
1.289 - {
1.290 - node nodes[4];
1.291 - void *begin = NULL, *end = NULL;
1.292 -
1.293 - cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[0]);
1.294 - CX_TEST_ASSERT(begin == &nodes[0]);
1.295 - CX_TEST_ASSERT(end == &nodes[0]);
1.296 - cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[1]);
1.297 - cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[2]);
1.298 - CX_TEST_ASSERT(begin == &nodes[2]);
1.299 - CX_TEST_ASSERT(end == &nodes[0]);
1.300 - CX_TEST_ASSERT(nodes[1].next == &nodes[0]);
1.301 - CX_TEST_ASSERT(nodes[2].next == &nodes[1]);
1.302 - CX_TEST_ASSERT(nodes[1].prev == NULL);
1.303 - CX_TEST_ASSERT(nodes[0].prev == NULL);
1.304 - }
1.305 -}
1.306 -
1.307 -TEST(LinkedList_LowLevel, cx_linked_list_insert) {
1.308 - // insert mid list
1.309 - {
1.310 - node nodes[4];
1.311 - void *begin = &nodes[0], *end = &nodes[2];
1.312 -
1.313 - cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
1.314 - cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
1.315 -
1.316 - cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3]);
1.317 - CX_TEST_ASSERT(begin == &nodes[0]);
1.318 - CX_TEST_ASSERT(end == &nodes[2]);
1.319 - CX_TEST_ASSERT(nodes[1].next == &nodes[3]);
1.320 - CX_TEST_ASSERT(nodes[2].prev == &nodes[3]);
1.321 - CX_TEST_ASSERT(nodes[3].prev == &nodes[1]);
1.322 - CX_TEST_ASSERT(nodes[3].next == &nodes[2]);
1.323 - }
1.324 -
1.325 - // insert end
1.326 - {
1.327 - node nodes[4];
1.328 - void *begin = &nodes[0], *end = &nodes[2];
1.329 -
1.330 - cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
1.331 - cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
1.332 -
1.333 - cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3]);
1.334 - CX_TEST_ASSERT(begin == &nodes[0]);
1.335 - CX_TEST_ASSERT(end == &nodes[3]);
1.336 - CX_TEST_ASSERT(nodes[2].next == &nodes[3]);
1.337 - CX_TEST_ASSERT(nodes[3].prev == &nodes[2]);
1.338 - CX_TEST_ASSERT(nodes[3].next == NULL);
1.339 - }
1.340 -
1.341 - // insert begin
1.342 - {
1.343 - node nodes[4];
1.344 - void *begin = &nodes[0], *end = &nodes[2];
1.345 -
1.346 - cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
1.347 - cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
1.348 -
1.349 - cx_linked_list_insert(&begin, &end, loc_prev, loc_next, NULL, &nodes[3]);
1.350 - CX_TEST_ASSERT(begin == &nodes[3]);
1.351 - CX_TEST_ASSERT(end == &nodes[2]);
1.352 - CX_TEST_ASSERT(nodes[0].prev == &nodes[3]);
1.353 - CX_TEST_ASSERT(nodes[3].prev == NULL);
1.354 - CX_TEST_ASSERT(nodes[3].next == &nodes[0]);
1.355 - }
1.356 -}
1.357 -
1.358 -TEST(LinkedList_LowLevel, cx_linked_list_insert_chain) {
1.359 - // insert mid list
1.360 - {
1.361 - node nodes[5];
1.362 - void *begin = &nodes[0], *end = &nodes[2];
1.363 -
1.364 - cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
1.365 - cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
1.366 - cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next);
1.367 -
1.368 - cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3], NULL);
1.369 - CX_TEST_ASSERT(begin == &nodes[0]);
1.370 - CX_TEST_ASSERT(end == &nodes[2]);
1.371 - CX_TEST_ASSERT(nodes[1].next == &nodes[3]);
1.372 - CX_TEST_ASSERT(nodes[2].prev == &nodes[4]);
1.373 - CX_TEST_ASSERT(nodes[3].prev == &nodes[1]);
1.374 - CX_TEST_ASSERT(nodes[4].next == &nodes[2]);
1.375 - }
1.376 -
1.377 - // insert end
1.378 - {
1.379 - node nodes[5];
1.380 - void *begin = &nodes[0], *end = &nodes[2];
1.381 -
1.382 - cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
1.383 - cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
1.384 - cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next);
1.385 -
1.386 - cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3], NULL);
1.387 - CX_TEST_ASSERT(begin == &nodes[0]);
1.388 - CX_TEST_ASSERT(end == &nodes[4]);
1.389 - CX_TEST_ASSERT(nodes[2].next == &nodes[3]);
1.390 - CX_TEST_ASSERT(nodes[3].prev == &nodes[2]);
1.391 - CX_TEST_ASSERT(nodes[4].next == NULL);
1.392 - }
1.393 -
1.394 - // insert begin
1.395 - {
1.396 - node nodes[5];
1.397 - void *begin = &nodes[0], *end = &nodes[2];
1.398 -
1.399 - cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
1.400 - cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
1.401 - cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next);
1.402 -
1.403 - cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, NULL, &nodes[3], NULL);
1.404 - CX_TEST_ASSERT(begin == &nodes[3]);
1.405 - CX_TEST_ASSERT(end == &nodes[2]);
1.406 - CX_TEST_ASSERT(nodes[0].prev == &nodes[4]);
1.407 - CX_TEST_ASSERT(nodes[3].prev == NULL);
1.408 - CX_TEST_ASSERT(nodes[4].next == &nodes[0]);
1.409 - }
1.410 -}
1.411 -
1.412 -TEST(LinkedList_LowLevel, cx_linked_list_first) {
1.413 - auto testdata = create_nodes_test_data(3);
1.414 - auto begin = testdata.begin;
1.415 - EXPECT_EQ(cx_linked_list_first(begin, loc_prev), begin);
1.416 - EXPECT_EQ(cx_linked_list_first(begin->next, loc_prev), begin);
1.417 - EXPECT_EQ(cx_linked_list_first(begin->next->next, loc_prev), begin);
1.418 -}
1.419 -
1.420 -TEST(LinkedList_LowLevel, cx_linked_list_last) {
1.421 - auto testdata = create_nodes_test_data(3);
1.422 - auto begin = testdata.begin;
1.423 - auto end = begin->next->next;
1.424 - EXPECT_EQ(cx_linked_list_last(begin, loc_next), end);
1.425 - EXPECT_EQ(cx_linked_list_last(begin->next, loc_next), end);
1.426 - EXPECT_EQ(cx_linked_list_last(begin->next->next, loc_next), end);
1.427 -}
1.428 -
1.429 -TEST(LinkedList_LowLevel, cx_linked_list_prev) {
1.430 - auto testdata = create_nodes_test_data(3);
1.431 - auto begin = testdata.begin;
1.432 - EXPECT_EQ(cx_linked_list_prev(begin, loc_next, begin), NULL);
1.433 - EXPECT_EQ(cx_linked_list_prev(begin, loc_next, begin->next), begin);
1.434 - EXPECT_EQ(cx_linked_list_prev(begin, loc_next, begin->next->next), begin->next);
1.435 -}
1.436 -
1.437 -TEST(LinkedList_LowLevel, cx_linked_list_remove) {
1.438 - auto testdata = create_nodes_test_data({2, 4, 6});
1.439 - auto begin = reinterpret_cast<void *>(testdata.begin);
1.440 - auto first = testdata.begin;
1.441 - auto second = first->next;
1.442 - auto third = second->next;
1.443 - auto end = reinterpret_cast<void *>(third);
1.444 -
1.445 - cx_linked_list_remove(&begin, &end, loc_prev, loc_next, second);
1.446 - CX_TEST_ASSERT(begin == first);
1.447 - CX_TEST_ASSERT(end == third);
1.448 - CX_TEST_ASSERT(first->prev == NULL);
1.449 - CX_TEST_ASSERT(first->next == third);
1.450 - CX_TEST_ASSERT(third->prev == first);
1.451 - CX_TEST_ASSERT(third->next == NULL);
1.452 -
1.453 - cx_linked_list_remove(&begin, &end, loc_prev, loc_next, third);
1.454 - CX_TEST_ASSERT(begin == first);
1.455 - CX_TEST_ASSERT(end == first);
1.456 - CX_TEST_ASSERT(first->prev == NULL);
1.457 - CX_TEST_ASSERT(first->next == NULL);
1.458 -
1.459 - cx_linked_list_remove(&begin, &end, loc_prev, loc_next, first);
1.460 - CX_TEST_ASSERT(begin == NULL);
1.461 - CX_TEST_ASSERT(end == NULL);
1.462 -}
1.463 -
1.464 -TEST(LinkedList_LowLevel, cx_linked_list_size) {
1.465 - EXPECT_EQ(cx_linked_list_size(NULL, loc_next), 0);
1.466 -
1.467 - {
1.468 - auto testdata = create_nodes_test_data(5);
1.469 - EXPECT_EQ(cx_linked_list_size(testdata.begin, loc_next), 5);
1.470 - }
1.471 -
1.472 - {
1.473 - auto testdata = create_nodes_test_data(13);
1.474 - EXPECT_EQ(cx_linked_list_size(testdata.begin, loc_next), 13);
1.475 - }
1.476 -}
1.477 -
1.478 -TEST(LinkedList_LowLevel, cx_linked_list_sort_empty) {
1.479 - void *begin = NULL;
1.480 - EXPECT_NO_FATAL_FAILURE(
1.481 - cx_linked_list_sort(&begin, NULL, loc_prev, loc_next, loc_data, cx_cmp_int);
1.482 - );
1.483 -}
1.484 -
1.485 -TEST(LinkedList_LowLevel, cx_linked_list_sort) {
1.486 - int_test_data<1500> testdata;
1.487 - std::array<int, 1500> sorted{};
1.488 - std::partial_sort_copy(testdata.data.begin(), testdata.data.end(), sorted.begin(), sorted.end());
1.489 -
1.490 - auto scrambled = create_nodes_test_data(testdata.data.begin(), testdata.data.end());
1.491 - void *begin = scrambled.begin;
1.492 - void *end = cx_linked_list_last(begin, loc_next);
1.493 -
1.494 - cx_linked_list_sort(&begin, &end, loc_prev, loc_next, loc_data, cx_cmp_int);
1.495 -
1.496 - node *check = reinterpret_cast<node *>(begin);
1.497 - node *check_last = NULL;
1.498 - cx_for_n (i, sorted.size()) {
1.499 - CX_TEST_ASSERT(check->data == sorted[i]);
1.500 - CX_TEST_ASSERT(check->prev == check_last);
1.501 - if (i < sorted.size() - 1) {
1.502 - ASSERT_NE(check->next, NULL);
1.503 - }
1.504 - check_last = check;
1.505 - check = check->next;
1.506 - }
1.507 - CX_TEST_ASSERT(check == NULL);
1.508 - CX_TEST_ASSERT(end == check_last);
1.509 -}
1.510 -
1.511 -TEST(LinkedList_LowLevel, cx_linked_list_reverse) {
1.512 - auto testdata = create_nodes_test_data({2, 4, 6, 8});
1.513 - auto expected = create_nodes_test_data({8, 6, 4, 2});
1.514 -
1.515 - auto begin = reinterpret_cast<void *>(testdata.begin);
1.516 - auto end = cx_linked_list_last(begin, loc_next);
1.517 - auto orig_begin = begin, orig_end = end;
1.518 -
1.519 - cx_linked_list_reverse(&begin, &end, loc_prev, loc_next);
1.520 - CX_TEST_ASSERT(end == orig_begin);
1.521 - CX_TEST_ASSERT(begin == orig_end);
1.522 - EXPECT_EQ(cx_linked_list_compare(begin, expected.begin, loc_next, loc_data, cx_cmp_int), 0);
1.523 -}
1.524
1.525 class HighLevelTest : public ::testing::Test {
1.526 mutable std::unordered_set<CxList *> lists;
