test/test_list.cpp@4fbfac557df8
test/test_list.cpp
Mon, 18 Apr 2022 17:26:21 +0200
- author
- Mike Becker <universe@uap-core.de>
- date
- Mon, 18 Apr 2022 17:26:21 +0200
- changeset 528
- 4fbfac557df8
- parent 521
- e5dc54131d55
- child 552
- 4373c2a90066
- permissions
- -rw-r--r--
#179 improve API for list content destruction
1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
3 *
4 * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 *
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 */
29 #include "cx/linked_list.h"
30 #include "cx/utils.h"
31 #include "util_allocator.h"
33 #include <gtest/gtest.h>
34 #include <array>
35 #include <vector>
36 #include <unordered_set>
37 #include <algorithm>
39 static int cmp_int_impl(
40 int const *l,
41 int const *r
42 ) {
43 int left = *l, right = *r;
44 return left == right ? 0 : (left < right ? -1 : 1);
45 }
47 #define cmp_int ((CxListComparator) cmp_int_impl)
49 struct node {
50 node *next = nullptr;
51 node *prev = nullptr;
52 int data = 0;
53 };
55 const ptrdiff_t loc_prev = offsetof(struct node, prev);
56 const ptrdiff_t loc_next = offsetof(struct node, next);
57 const ptrdiff_t loc_data = offsetof(struct node, data);
59 struct node_test_data {
60 node *begin = nullptr;
62 explicit node_test_data(node *begin) : begin(begin) {
63 auto n = begin;
64 while (n != nullptr) {
65 nodes.push_back(n);
66 n = n->next;
67 }
68 }
70 node_test_data(node_test_data &) = delete;
72 node_test_data(node_test_data &&) = default;
74 ~node_test_data() {
75 for (auto &&n: nodes) delete n;
76 }
78 private:
79 std::vector<node *> nodes;
80 };
82 static node_test_data create_nodes_test_data(size_t len) {
83 if (len == 0) return node_test_data{nullptr};
84 auto begin = new node;
85 auto prev = begin;
86 for (size_t i = 1; i < len; i++) {
87 auto n = new node;
88 cx_linked_list_link(prev, n, loc_prev, loc_next);
89 prev = n;
90 }
91 return node_test_data{begin};
92 }
94 template<typename InputIter>
95 static node_test_data create_nodes_test_data(
96 InputIter begin,
97 InputIter end
98 ) {
99 if (begin == end) return node_test_data{nullptr};
100 node *first = new node;
101 first->data = *begin;
102 node *prev = first;
103 begin++;
104 for (; begin != end; begin++) {
105 auto n = new node;
106 n->data = *begin;
107 cx_linked_list_link(prev, n, loc_prev, loc_next);
108 prev = n;
109 }
110 return node_test_data{first};
111 }
113 static node_test_data create_nodes_test_data(std::initializer_list<int> data) {
114 return create_nodes_test_data(data.begin(), data.end());
115 }
117 template<size_t N>
118 struct int_test_data {
119 std::array<int, N> data;
121 int_test_data() {
122 cx_for_n (i, N) data[i] = ::rand(); // NOLINT(cert-msc50-cpp)
123 }
124 };
126 TEST(LinkedList_LowLevel, link_unlink) {
127 node a, b, c;
129 cx_linked_list_link(&a, &b, loc_prev, loc_next);
130 EXPECT_EQ(a.prev, nullptr);
131 EXPECT_EQ(a.next, &b);
132 EXPECT_EQ(b.prev, &a);
133 EXPECT_EQ(b.next, nullptr);
135 cx_linked_list_unlink(&a, &b, loc_prev, loc_next);
136 EXPECT_EQ(a.prev, nullptr);
137 EXPECT_EQ(a.next, nullptr);
138 EXPECT_EQ(b.prev, nullptr);
139 EXPECT_EQ(b.next, nullptr);
141 cx_linked_list_link(&b, &c, loc_prev, loc_next);
142 cx_linked_list_link(&a, &b, loc_prev, loc_next);
143 cx_linked_list_unlink(&b, &c, loc_prev, loc_next);
144 EXPECT_EQ(a.prev, nullptr);
145 EXPECT_EQ(a.next, &b);
146 EXPECT_EQ(b.prev, &a);
147 EXPECT_EQ(b.next, nullptr);
148 EXPECT_EQ(c.prev, nullptr);
149 EXPECT_EQ(c.next, nullptr);
150 }
152 TEST(LinkedList_LowLevel, cx_linked_list_at) {
153 node a, b, c, d;
154 cx_linked_list_link(&a, &b, loc_prev, loc_next);
155 cx_linked_list_link(&b, &c, loc_prev, loc_next);
156 cx_linked_list_link(&c, &d, loc_prev, loc_next);
158 EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 0), &a);
159 EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 1), &b);
160 EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 2), &c);
161 EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 3), &d);
162 EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 4), nullptr);
164 EXPECT_EQ(cx_linked_list_at(&b, 1, loc_prev, 0), &a);
165 EXPECT_EQ(cx_linked_list_at(&b, 1, loc_next, 1), &b);
166 EXPECT_EQ(cx_linked_list_at(&b, 1, loc_next, 2), &c);
167 EXPECT_EQ(cx_linked_list_at(&b, 1, loc_next, 3), &d);
168 EXPECT_EQ(cx_linked_list_at(&b, 1, loc_next, 4), nullptr);
170 EXPECT_EQ(cx_linked_list_at(&d, 3, loc_prev, 0), &a);
171 EXPECT_EQ(cx_linked_list_at(&d, 3, loc_prev, 1), &b);
172 }
174 TEST(LinkedList_LowLevel, cx_linked_list_find) {
175 auto testdata = create_nodes_test_data({2, 4, 6, 8});
176 auto list = testdata.begin;
177 int s;
179 s = 2;
180 EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, false, cmp_int, &s), 0);
181 s = 4;
182 EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, false, cmp_int, &s), 1);
183 s = 6;
184 EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, false, cmp_int, &s), 2);
185 s = 8;
186 EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, false, cmp_int, &s), 3);
187 s = 10;
188 EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, false, cmp_int, &s), 4);
189 s = -2;
190 EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, false, cmp_int, &s), 4);
191 }
193 TEST(LinkedList_LowLevel, cx_linked_list_compare) {
194 auto ta = create_nodes_test_data({2, 4, 6, 8});
195 auto tb = create_nodes_test_data({2, 4, 6});
196 auto tc = create_nodes_test_data({2, 4, 6, 9});
197 auto la = ta.begin, lb = tb.begin, lc = tc.begin;
199 EXPECT_GT(cx_linked_list_compare(la, lb, loc_next, loc_data, false, cmp_int), 0);
200 EXPECT_LT(cx_linked_list_compare(lb, la, loc_next, loc_data, false, cmp_int), 0);
201 EXPECT_GT(cx_linked_list_compare(lc, la, loc_next, loc_data, false, cmp_int), 0);
202 EXPECT_LT(cx_linked_list_compare(la, lc, loc_next, loc_data, false, cmp_int), 0);
203 EXPECT_EQ(cx_linked_list_compare(la, la, loc_next, loc_data, false, cmp_int), 0);
204 }
206 TEST(LinkedList_LowLevel, cx_linked_list_add) {
207 // test with begin, end / prev, next
208 {
209 node nodes[4];
210 void *begin = nullptr, *end = nullptr;
212 cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[0]);
213 EXPECT_EQ(begin, &nodes[0]);
214 EXPECT_EQ(end, &nodes[0]);
215 EXPECT_EQ(nodes[0].prev, nullptr);
216 EXPECT_EQ(nodes[0].next, nullptr);
218 cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[1]);
219 EXPECT_EQ(begin, &nodes[0]);
220 EXPECT_EQ(end, &nodes[1]);
221 EXPECT_EQ(nodes[0].next, &nodes[1]);
222 EXPECT_EQ(nodes[1].prev, &nodes[0]);
223 }
225 // test with begin only / prev, next
226 {
227 node nodes[4];
228 void *begin = nullptr;
230 cx_linked_list_add(&begin, nullptr, loc_prev, loc_next, &nodes[0]);
231 EXPECT_EQ(begin, &nodes[0]);
232 cx_linked_list_add(&begin, nullptr, loc_prev, loc_next, &nodes[1]);
233 EXPECT_EQ(begin, &nodes[0]);
234 EXPECT_EQ(nodes[0].next, &nodes[1]);
235 EXPECT_EQ(nodes[1].prev, &nodes[0]);
237 cx_linked_list_add(&begin, nullptr, loc_prev, loc_next, &nodes[2]);
238 EXPECT_EQ(nodes[1].next, &nodes[2]);
239 EXPECT_EQ(nodes[2].prev, &nodes[1]);
240 }
242 // test with end only / prev, next
243 {
244 node nodes[4];
245 void *end = nullptr;
247 cx_linked_list_add(nullptr, &end, loc_prev, loc_next, &nodes[0]);
248 EXPECT_EQ(end, &nodes[0]);
249 cx_linked_list_add(nullptr, &end, loc_prev, loc_next, &nodes[1]);
250 EXPECT_EQ(end, &nodes[1]);
251 EXPECT_EQ(nodes[0].next, &nodes[1]);
252 EXPECT_EQ(nodes[1].prev, &nodes[0]);
254 cx_linked_list_add(nullptr, &end, loc_prev, loc_next, &nodes[2]);
255 EXPECT_EQ(end, &nodes[2]);
256 EXPECT_EQ(nodes[1].next, &nodes[2]);
257 EXPECT_EQ(nodes[2].prev, &nodes[1]);
258 }
260 // test with begin, end / next
261 {
262 node nodes[4];
263 void *begin = nullptr, *end = nullptr;
265 cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[0]);
266 EXPECT_EQ(begin, &nodes[0]);
267 EXPECT_EQ(end, &nodes[0]);
268 cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[1]);
269 EXPECT_EQ(end, &nodes[1]);
270 EXPECT_EQ(nodes[0].next, &nodes[1]);
271 EXPECT_EQ(nodes[1].prev, nullptr);
272 }
273 }
275 TEST(LinkedList_LowLevel, cx_linked_list_prepend) {
276 // test with begin, end / prev, next
277 {
278 node nodes[4];
279 void *begin = nullptr, *end = nullptr;
281 cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[0]);
282 EXPECT_EQ(begin, &nodes[0]);
283 EXPECT_EQ(end, &nodes[0]);
284 EXPECT_EQ(nodes[0].prev, nullptr);
285 EXPECT_EQ(nodes[0].next, nullptr);
287 cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[1]);
288 EXPECT_EQ(begin, &nodes[1]);
289 EXPECT_EQ(end, &nodes[0]);
290 EXPECT_EQ(nodes[1].next, &nodes[0]);
291 EXPECT_EQ(nodes[0].prev, &nodes[1]);
292 }
294 // test with begin only / prev, next
295 {
296 node nodes[4];
297 void *begin = nullptr;
299 cx_linked_list_prepend(&begin, nullptr, loc_prev, loc_next, &nodes[0]);
300 EXPECT_EQ(begin, &nodes[0]);
301 cx_linked_list_prepend(&begin, nullptr, loc_prev, loc_next, &nodes[1]);
302 EXPECT_EQ(begin, &nodes[1]);
303 EXPECT_EQ(nodes[1].next, &nodes[0]);
304 EXPECT_EQ(nodes[0].prev, &nodes[1]);
306 cx_linked_list_prepend(&begin, nullptr, loc_prev, loc_next, &nodes[2]);
307 EXPECT_EQ(begin, &nodes[2]);
308 EXPECT_EQ(nodes[2].next, &nodes[1]);
309 EXPECT_EQ(nodes[1].prev, &nodes[2]);
310 }
312 // test with end only / prev, next
313 {
314 node nodes[4];
315 void *end = nullptr;
317 cx_linked_list_prepend(nullptr, &end, loc_prev, loc_next, &nodes[0]);
318 EXPECT_EQ(end, &nodes[0]);
319 cx_linked_list_prepend(nullptr, &end, loc_prev, loc_next, &nodes[1]);
320 EXPECT_EQ(end, &nodes[0]);
321 EXPECT_EQ(nodes[1].next, &nodes[0]);
322 EXPECT_EQ(nodes[0].prev, &nodes[1]);
324 cx_linked_list_prepend(nullptr, &end, loc_prev, loc_next, &nodes[2]);
325 EXPECT_EQ(end, &nodes[0]);
326 EXPECT_EQ(nodes[2].next, &nodes[1]);
327 EXPECT_EQ(nodes[1].prev, &nodes[2]);
328 }
330 // test with begin, end / next
331 {
332 node nodes[4];
333 void *begin = nullptr, *end = nullptr;
335 cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[0]);
336 EXPECT_EQ(begin, &nodes[0]);
337 EXPECT_EQ(end, &nodes[0]);
338 cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[1]);
339 cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[2]);
340 EXPECT_EQ(begin, &nodes[2]);
341 EXPECT_EQ(end, &nodes[0]);
342 EXPECT_EQ(nodes[1].next, &nodes[0]);
343 EXPECT_EQ(nodes[2].next, &nodes[1]);
344 EXPECT_EQ(nodes[1].prev, nullptr);
345 EXPECT_EQ(nodes[0].prev, nullptr);
346 }
347 }
349 TEST(LinkedList_LowLevel, cx_linked_list_insert) {
350 // insert mid list
351 {
352 node nodes[4];
353 void *begin = &nodes[0], *end = &nodes[2];
355 cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
356 cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
358 cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3]);
359 EXPECT_EQ(begin, &nodes[0]);
360 EXPECT_EQ(end, &nodes[2]);
361 EXPECT_EQ(nodes[1].next, &nodes[3]);
362 EXPECT_EQ(nodes[2].prev, &nodes[3]);
363 EXPECT_EQ(nodes[3].prev, &nodes[1]);
364 EXPECT_EQ(nodes[3].next, &nodes[2]);
365 }
367 // insert end
368 {
369 node nodes[4];
370 void *begin = &nodes[0], *end = &nodes[2];
372 cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
373 cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
375 cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3]);
376 EXPECT_EQ(begin, &nodes[0]);
377 EXPECT_EQ(end, &nodes[3]);
378 EXPECT_EQ(nodes[2].next, &nodes[3]);
379 EXPECT_EQ(nodes[3].prev, &nodes[2]);
380 EXPECT_EQ(nodes[3].next, nullptr);
381 }
383 // insert begin
384 {
385 node nodes[4];
386 void *begin = &nodes[0], *end = &nodes[2];
388 cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
389 cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
391 cx_linked_list_insert(&begin, &end, loc_prev, loc_next, nullptr, &nodes[3]);
392 EXPECT_EQ(begin, &nodes[3]);
393 EXPECT_EQ(end, &nodes[2]);
394 EXPECT_EQ(nodes[0].prev, &nodes[3]);
395 EXPECT_EQ(nodes[3].prev, nullptr);
396 EXPECT_EQ(nodes[3].next, &nodes[0]);
397 }
398 }
400 TEST(LinkedList_LowLevel, cx_linked_list_insert_chain) {
401 // insert mid list
402 {
403 node nodes[5];
404 void *begin = &nodes[0], *end = &nodes[2];
406 cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
407 cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
408 cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next);
410 cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3], nullptr);
411 EXPECT_EQ(begin, &nodes[0]);
412 EXPECT_EQ(end, &nodes[2]);
413 EXPECT_EQ(nodes[1].next, &nodes[3]);
414 EXPECT_EQ(nodes[2].prev, &nodes[4]);
415 EXPECT_EQ(nodes[3].prev, &nodes[1]);
416 EXPECT_EQ(nodes[4].next, &nodes[2]);
417 }
419 // insert end
420 {
421 node nodes[5];
422 void *begin = &nodes[0], *end = &nodes[2];
424 cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
425 cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
426 cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next);
428 cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3], nullptr);
429 EXPECT_EQ(begin, &nodes[0]);
430 EXPECT_EQ(end, &nodes[4]);
431 EXPECT_EQ(nodes[2].next, &nodes[3]);
432 EXPECT_EQ(nodes[3].prev, &nodes[2]);
433 EXPECT_EQ(nodes[4].next, nullptr);
434 }
436 // insert begin
437 {
438 node nodes[5];
439 void *begin = &nodes[0], *end = &nodes[2];
441 cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
442 cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
443 cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next);
445 cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, nullptr, &nodes[3], nullptr);
446 EXPECT_EQ(begin, &nodes[3]);
447 EXPECT_EQ(end, &nodes[2]);
448 EXPECT_EQ(nodes[0].prev, &nodes[4]);
449 EXPECT_EQ(nodes[3].prev, nullptr);
450 EXPECT_EQ(nodes[4].next, &nodes[0]);
451 }
452 }
454 TEST(LinkedList_LowLevel, cx_linked_list_first) {
455 auto testdata = create_nodes_test_data(3);
456 auto begin = testdata.begin;
457 EXPECT_EQ(cx_linked_list_first(begin, loc_prev), begin);
458 EXPECT_EQ(cx_linked_list_first(begin->next, loc_prev), begin);
459 EXPECT_EQ(cx_linked_list_first(begin->next->next, loc_prev), begin);
460 }
462 TEST(LinkedList_LowLevel, cx_linked_list_last) {
463 auto testdata = create_nodes_test_data(3);
464 auto begin = testdata.begin;
465 auto end = begin->next->next;
466 EXPECT_EQ(cx_linked_list_last(begin, loc_next), end);
467 EXPECT_EQ(cx_linked_list_last(begin->next, loc_next), end);
468 EXPECT_EQ(cx_linked_list_last(begin->next->next, loc_next), end);
469 }
471 TEST(LinkedList_LowLevel, cx_linked_list_prev) {
472 auto testdata = create_nodes_test_data(3);
473 auto begin = testdata.begin;
474 EXPECT_EQ(cx_linked_list_prev(begin, loc_next, begin), nullptr);
475 EXPECT_EQ(cx_linked_list_prev(begin, loc_next, begin->next), begin);
476 EXPECT_EQ(cx_linked_list_prev(begin, loc_next, begin->next->next), begin->next);
477 }
479 TEST(LinkedList_LowLevel, cx_linked_list_remove) {
480 auto testdata = create_nodes_test_data({2, 4, 6});
481 auto begin = reinterpret_cast<void *>(testdata.begin);
482 auto first = testdata.begin;
483 auto second = first->next;
484 auto third = second->next;
485 auto end = reinterpret_cast<void *>(third);
487 cx_linked_list_remove(&begin, &end, loc_prev, loc_next, second);
488 EXPECT_EQ(begin, first);
489 EXPECT_EQ(end, third);
490 EXPECT_EQ(first->prev, nullptr);
491 EXPECT_EQ(first->next, third);
492 EXPECT_EQ(third->prev, first);
493 EXPECT_EQ(third->next, nullptr);
495 cx_linked_list_remove(&begin, &end, loc_prev, loc_next, third);
496 EXPECT_EQ(begin, first);
497 EXPECT_EQ(end, first);
498 EXPECT_EQ(first->prev, nullptr);
499 EXPECT_EQ(first->next, nullptr);
501 cx_linked_list_remove(&begin, &end, loc_prev, loc_next, first);
502 EXPECT_EQ(begin, nullptr);
503 EXPECT_EQ(end, nullptr);
504 }
506 TEST(LinkedList_LowLevel, cx_linked_list_size) {
507 EXPECT_EQ(cx_linked_list_size(nullptr, loc_next), 0);
509 {
510 auto testdata = create_nodes_test_data(5);
511 EXPECT_EQ(cx_linked_list_size(testdata.begin, loc_next), 5);
512 }
514 {
515 auto testdata = create_nodes_test_data(13);
516 EXPECT_EQ(cx_linked_list_size(testdata.begin, loc_next), 13);
517 }
518 }
520 TEST(LinkedList_LowLevel, cx_linked_list_sort) {
521 int_test_data<1500> testdata;
522 std::array<int, 1500> sorted{};
523 std::partial_sort_copy(testdata.data.begin(), testdata.data.end(), sorted.begin(), sorted.end());
525 auto scrambled = create_nodes_test_data(testdata.data.begin(), testdata.data.end());
526 void *begin = scrambled.begin;
527 void *end = cx_linked_list_last(begin, loc_next);
529 cx_linked_list_sort(&begin, &end, loc_prev, loc_next, loc_data,
530 false, cmp_int);
532 node *check = reinterpret_cast<node *>(begin);
533 node *check_last = nullptr;
534 cx_for_n (i, sorted.size()) {
535 EXPECT_EQ(check->data, sorted[i]);
536 EXPECT_EQ(check->prev, check_last);
537 if (i < sorted.size() - 1) {
538 ASSERT_NE(check->next, nullptr);
539 }
540 check_last = check;
541 check = check->next;
542 }
543 EXPECT_EQ(check, nullptr);
544 EXPECT_EQ(end, check_last);
545 }
547 TEST(LinkedList_LowLevel, cx_linked_list_reverse) {
548 auto testdata = create_nodes_test_data({2, 4, 6, 8});
549 auto expected = create_nodes_test_data({8, 6, 4, 2});
551 auto begin = reinterpret_cast<void *>(testdata.begin);
552 auto end = cx_linked_list_last(begin, loc_next);
553 auto orig_begin = begin, orig_end = end;
555 cx_linked_list_reverse(&begin, &end, loc_prev, loc_next);
556 EXPECT_EQ(end, orig_begin);
557 EXPECT_EQ(begin, orig_end);
558 EXPECT_EQ(cx_linked_list_compare(begin, expected.begin, loc_next, loc_data, 0, cmp_int), 0);
559 }
561 class HighLevelTest : public ::testing::Test {
562 mutable std::unordered_set<CxList *> lists;
563 protected:
564 CxTestingAllocator testingAllocator;
566 void TearDown() override {
567 for (auto &&l: lists) cxListDestroy(l);
568 EXPECT_TRUE(testingAllocator.verify());
569 }
571 static constexpr size_t testdata_len = 250;
572 int_test_data<testdata_len> testdata;
574 auto autofree(CxList *list) const -> CxList * {
575 lists.insert(list);
576 return list;
577 }
579 auto linkedListFromTestData() const -> CxList * {
580 return autofree(
581 cxLinkedListFromArray(
582 &testingAllocator,
583 cmp_int,
584 sizeof(int),
585 testdata_len,
586 testdata.data.data()
587 )
588 );
589 }
591 auto pointerLinkedListFromTestData() const -> CxList * {
592 auto list = autofree(cxPointerLinkedListCreate(&testingAllocator, cmp_int));
593 cx_for_n(i, testdata_len) cxListAdd(list, &testdata.data[i]);
594 return list;
595 }
597 void verifyCreate(CxList *list) const {
598 EXPECT_EQ(list->content_destructor_type, CX_DESTRUCTOR_NONE);
599 EXPECT_EQ(list->size, 0);
600 EXPECT_EQ(list->capacity, (size_t) -1);
601 EXPECT_EQ(list->allocator, &testingAllocator);
602 EXPECT_EQ(list->cmpfunc, cmp_int);
603 }
605 void verifyAdd(
606 CxList *list,
607 bool write_through
608 ) {
609 auto len = testdata_len;
610 cx_for_n (i, len) EXPECT_EQ(cxListAdd(list, &testdata.data[i]), 0);
611 EXPECT_EQ(list->size, len);
612 EXPECT_GE(list->capacity, list->size);
613 cx_for_n (i, len) EXPECT_EQ(*(int *) cxListAt(list, i), testdata.data[i]);
614 cx_for_n (i, len) ++testdata.data[i];
615 if (write_through) {
616 cx_for_n (i, len) EXPECT_EQ(*(int *) cxListAt(list, i), testdata.data[i]);
617 } else {
618 cx_for_n (i, len) EXPECT_EQ(*(int *) cxListAt(list, i), testdata.data[i] - 1);
619 }
620 }
622 static void verifyInsert(CxList *list) {
623 int a = 5, b = 47, c = 13, d = 42;
625 EXPECT_NE(cxListInsert(list, 1, &a), 0);
626 EXPECT_EQ(list->size, 0);
627 EXPECT_EQ(cxListInsert(list, 0, &a), 0);
628 EXPECT_EQ(list->size, 1);
629 EXPECT_EQ(cxListInsert(list, 0, &b), 0);
630 EXPECT_EQ(list->size, 2);
631 EXPECT_EQ(cxListInsert(list, 1, &c), 0);
632 EXPECT_EQ(list->size, 3);
633 EXPECT_EQ(cxListInsert(list, 3, &d), 0);
635 EXPECT_EQ(list->size, 4);
636 EXPECT_GE(list->capacity, list->size);
638 EXPECT_EQ(*(int *) cxListAt(list, 0), 47);
639 EXPECT_EQ(*(int *) cxListAt(list, 1), 13);
640 EXPECT_EQ(*(int *) cxListAt(list, 2), 5);
641 EXPECT_EQ(*(int *) cxListAt(list, 3), 42);
642 }
644 void verifyRemove(CxList *list) const {
645 EXPECT_EQ(cxListRemove(list, 2), 0);
646 EXPECT_EQ(cxListRemove(list, 4), 0);
647 EXPECT_EQ(list->size, testdata_len - 2);
648 EXPECT_GE(list->capacity, list->size);
649 EXPECT_EQ(*(int *) cxListAt(list, 0), testdata.data[0]);
650 EXPECT_EQ(*(int *) cxListAt(list, 1), testdata.data[1]);
651 EXPECT_EQ(*(int *) cxListAt(list, 2), testdata.data[3]);
652 EXPECT_EQ(*(int *) cxListAt(list, 3), testdata.data[4]);
653 EXPECT_EQ(*(int *) cxListAt(list, 4), testdata.data[6]);
655 EXPECT_EQ(cxListRemove(list, 0), 0);
656 EXPECT_EQ(list->size, testdata_len - 3);
657 EXPECT_GE(list->capacity, list->size);
658 EXPECT_EQ(*(int *) cxListAt(list, 0), testdata.data[1]);
659 EXPECT_EQ(*(int *) cxListAt(list, 1), testdata.data[3]);
661 EXPECT_NE(cxListRemove(list, testdata_len), 0);
662 }
664 void verifyAt(CxList *list) const {
665 auto len = testdata_len;
666 EXPECT_EQ(list->size, len);
667 cx_for_n (i, len) {
668 EXPECT_EQ(*(int *) cxListAt(list, i), testdata.data[i]);
669 }
670 EXPECT_EQ(cxListAt(list, list->size), nullptr);
671 }
673 void verifyFind(CxList *list) const {
674 cx_for_n (attempt, 25) {
675 size_t exp = rand() % testdata_len; // NOLINT(cert-msc50-cpp)
676 int val = testdata.data[exp];
677 // randomly picked number could occur earlier in list - find first position
678 cx_for_n (i, exp) {
679 if (testdata.data[i] == val) {
680 exp = i;
681 break;
682 }
683 }
684 EXPECT_EQ(cxListFind(list, &val), exp);
685 }
686 }
688 void verifySort(CxList *list) const {
689 std::array<int, testdata_len> expected{};
690 std::partial_sort_copy(testdata.data.begin(), testdata.data.end(), expected.begin(), expected.end());
691 cxListSort(list);
692 cx_for_n (i, testdata_len) ASSERT_EQ(*(int *) cxListAt(list, i), expected[i]);
693 }
695 void verifyIterator(CxList *list) const {
696 int i = 0;
697 CxIterator iter = cxListBegin(list);
698 cx_foreach(int*, x, iter) {
699 ASSERT_EQ(iter.index, (size_t) (i + 1) / 2);
700 ASSERT_EQ(*x, testdata.data[i]);
701 if (i % 2 == 1) iter.remove = true;
702 i++;
703 }
704 auto len = testdata_len;
705 EXPECT_EQ(i, len);
706 ASSERT_EQ(list->size, len / 2);
707 cx_for_n(j, len / 2) ASSERT_EQ(*(int *) cxListAt(list, j), testdata.data[j * 2]);
708 }
710 static void verifyInsertViaIterator(CxList *list) {
711 int newdata[] = {10, 20, 30, 40, 50};
713 CxIterator iter = cxListIterator(list, 2);
714 EXPECT_TRUE(cxIteratorValid(&iter));
715 EXPECT_EQ(iter.index, 2);
716 EXPECT_EQ(*(int *) cxIteratorCurrent(&iter), 2);
717 cxListInsertAfter(&iter, &newdata[0]);
718 EXPECT_TRUE(cxIteratorValid(&iter));
719 EXPECT_EQ(iter.index, 2);
720 EXPECT_EQ(*(int *) cxIteratorCurrent(&iter), 2);
721 cxListInsertBefore(&iter, &newdata[1]);
722 EXPECT_TRUE(cxIteratorValid(&iter));
723 EXPECT_EQ(iter.index, 3);
724 EXPECT_EQ(*(int *) cxIteratorCurrent(&iter), 2);
726 iter = cxListBegin(list);
727 cxListInsertBefore(&iter, &newdata[2]);
728 EXPECT_TRUE(cxIteratorValid(&iter));
729 EXPECT_EQ(iter.index, 1);
730 EXPECT_EQ(*(int *) cxIteratorCurrent(&iter), 0);
731 iter = cxListIterator(list, list->size);
732 cxListInsertBefore(&iter, &newdata[3]);
733 EXPECT_FALSE(cxIteratorValid(&iter));
734 EXPECT_EQ(iter.index, 9);
735 iter = cxListIterator(list, list->size);
736 cxListInsertAfter(&iter, &newdata[4]);
737 EXPECT_FALSE(cxIteratorValid(&iter));
738 EXPECT_EQ(iter.index, 10);
740 int expdata[] = {30, 0, 1, 20, 2, 10, 3, 4, 40, 50};
741 cx_for_n (j, 10) EXPECT_EQ(*(int *) cxListAt(list, j), expdata[j]);
742 }
744 void verifyReverse(CxList *list) const {
745 cxListReverse(list);
746 cx_for_n(i, testdata_len) {
747 ASSERT_EQ(*(int *) cxListAt(list, i), testdata.data[testdata_len - 1 - i]);
748 }
749 }
751 static void verifyCompare(
752 CxList *left,
753 CxList *right
754 ) {
755 EXPECT_EQ(cxListCompare(left, right), 0);
756 int x = 42;
757 cxListAdd(left, &x);
758 ASSERT_GT(left->size, right->size);
759 EXPECT_GT(cxListCompare(left, right), 0);
760 EXPECT_LT(cxListCompare(right, left), 0);
761 cxListAdd(right, &x);
762 ASSERT_EQ(left->size, right->size);
763 EXPECT_EQ(cxListCompare(left, right), 0);
764 int a = 5, b = 10;
765 cxListInsert(left, 15, &a);
766 cxListInsert(right, 15, &b);
767 ASSERT_EQ(left->size, right->size);
768 EXPECT_LT(cxListCompare(left, right), 0);
769 EXPECT_GT(cxListCompare(right, left), 0);
770 *(int *) cxListAt(left, 15) = 10;
771 EXPECT_EQ(cxListCompare(left, right), 0);
772 }
773 };
775 class LinkedList : public HighLevelTest {
776 };
778 class PointerLinkedList : public HighLevelTest {
779 };
781 TEST_F(LinkedList, cxLinkedListCreate) {
782 CxList *list = autofree(cxLinkedListCreate(&testingAllocator, cmp_int, sizeof(int)));
783 EXPECT_EQ(list->itemsize, sizeof(int));
784 verifyCreate(list);
785 }
787 TEST_F(PointerLinkedList, cxPointerLinkedListCreate) {
788 CxList *list = autofree(cxPointerLinkedListCreate(&testingAllocator, cmp_int));
789 EXPECT_EQ(list->itemsize, sizeof(void *));
790 verifyCreate(list);
791 }
793 TEST_F(LinkedList, cxLinkedListFromArray) {
794 CxList *expected = autofree(cxLinkedListCreate(&testingAllocator, cmp_int, sizeof(int)));
795 cx_for_n (i, testdata_len) cxListAdd(expected, &testdata.data[i]);
796 CxList *list = autofree(cxLinkedListFromArray(&testingAllocator, cmp_int, sizeof(int),
797 testdata_len, testdata.data.data()));
798 EXPECT_EQ(cxListCompare(list, expected), 0);
799 }
801 TEST_F(LinkedList, cxListAdd) {
802 CxList *list = autofree(cxLinkedListCreate(&testingAllocator, cmp_int, sizeof(int)));
803 verifyAdd(list, false);
804 }
806 TEST_F(PointerLinkedList, cxListAdd) {
807 CxList *list = autofree(cxPointerLinkedListCreate(&testingAllocator, cmp_int));
808 verifyAdd(list, true);
809 }
811 TEST_F(LinkedList, cxListInsert) {
812 verifyInsert(autofree(cxLinkedListCreate(&testingAllocator, cmp_int, sizeof(int))));
813 }
815 TEST_F(PointerLinkedList, cxListInsert) {
816 verifyInsert(autofree(cxPointerLinkedListCreate(&testingAllocator, cmp_int)));
817 }
819 TEST_F(LinkedList, cxListRemove) {
820 verifyRemove(linkedListFromTestData());
821 }
823 TEST_F(PointerLinkedList, cxListRemove) {
824 verifyRemove(pointerLinkedListFromTestData());
825 }
827 TEST_F(LinkedList, cxListAt) {
828 verifyAt(linkedListFromTestData());
829 }
831 TEST_F(PointerLinkedList, cxListAt) {
832 verifyAt(pointerLinkedListFromTestData());
833 }
835 TEST_F(LinkedList, cxListFind) {
836 verifyFind(linkedListFromTestData());
837 }
839 TEST_F(PointerLinkedList, cxListFind) {
840 verifyFind(pointerLinkedListFromTestData());
841 }
843 TEST_F(LinkedList, cxListSort) {
844 verifySort(linkedListFromTestData());
845 }
847 TEST_F(PointerLinkedList, cxListSort) {
848 verifySort(pointerLinkedListFromTestData());
849 }
851 TEST_F(LinkedList, Iterator) {
852 verifyIterator(linkedListFromTestData());
853 }
855 TEST_F(PointerLinkedList, Iterator) {
856 verifyIterator(pointerLinkedListFromTestData());
857 }
859 TEST_F(LinkedList, InsertViaIterator) {
860 int fivenums[] = {0, 1, 2, 3, 4, 5};
861 CxList *list = autofree(cxLinkedListFromArray(&testingAllocator, cmp_int, sizeof(int), 5, fivenums));
862 verifyInsertViaIterator(list);
863 }
865 TEST_F(PointerLinkedList, InsertViaIterator) {
866 int fivenums[] = {0, 1, 2, 3, 4, 5};
867 CxList *list = autofree(cxPointerLinkedListCreate(&testingAllocator, cmp_int));
868 cx_for_n (i, 5) cxListAdd(list, &fivenums[i]);
869 verifyInsertViaIterator(list);
870 }
872 TEST_F(LinkedList, cxListReverse) {
873 verifyReverse(linkedListFromTestData());
874 }
876 TEST_F(PointerLinkedList, cxListReverse) {
877 verifyReverse(pointerLinkedListFromTestData());
878 }
880 TEST_F(LinkedList, cxListCompare) {
881 auto left = linkedListFromTestData();
882 auto right = linkedListFromTestData();
883 verifyCompare(left, right);
884 }
886 TEST_F(PointerLinkedList, cxListCompare) {
887 auto left = pointerLinkedListFromTestData();
888 auto right = pointerLinkedListFromTestData();
889 verifyCompare(left, right);
890 }
892 TEST_F(PointerLinkedList, NoDestructor) {
893 void *item = cxMalloc(&testingAllocator, sizeof(int));
894 auto list = cxPointerLinkedListCreate(cxDefaultAllocator, cmp_int);
895 cxListAdd(list, item);
896 ASSERT_FALSE(testingAllocator.verify());
897 cxListDestroy(list);
898 EXPECT_FALSE(testingAllocator.verify());
899 cxFree(&testingAllocator, item);
900 EXPECT_TRUE(testingAllocator.verify());
901 }
903 TEST_F(PointerLinkedList, SimpleDestructor) {
904 int item = 0;
905 auto list = cxPointerLinkedListCreate(cxDefaultAllocator, cmp_int);
906 list->content_destructor_type = CX_DESTRUCTOR_SIMPLE;
907 list->simple_destructor = [](void *elem) { *(int *) elem = 42; };
908 cxListAdd(list, &item);
909 cxListDestroy(list);
910 EXPECT_EQ(item, 42);
911 }
913 TEST_F(PointerLinkedList, AdvancedDestructor) {
914 void *item = cxMalloc(&testingAllocator, sizeof(int));
915 auto list = cxPointerLinkedListCreate(cxDefaultAllocator, cmp_int);
916 list->content_destructor_type = CX_DESTRUCTOR_ADVANCED;
917 list->advanced_destructor.data = &testingAllocator;
918 list->advanced_destructor.func = (cx_destructor_func2) cxFree;
919 cxListAdd(list, item);
920 ASSERT_FALSE(testingAllocator.verify());
921 cxListDestroy(list);
922 EXPECT_TRUE(testingAllocator.verify());
923 }
