test/test_list.cpp@e5dc54131d55
test/test_list.cpp
Sat, 16 Apr 2022 22:12:47 +0200
- author
- Mike Becker <universe@uap-core.de>
- date
- Sat, 16 Apr 2022 22:12:47 +0200
- changeset 521
- e5dc54131d55
- parent 520
- f937c6d11d1f
- child 528
- 4fbfac557df8
- permissions
- -rw-r--r--
add test for cxListCompare
Also increases size for low level sort test in order to
exceed the SBO limit.
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(InputIter begin, InputIter end) {
96 if (begin == end) return node_test_data{nullptr};
97 node *first = new node;
98 first->data = *begin;
99 node *prev = first;
100 begin++;
101 for (; begin != end; begin++) {
102 auto n = new node;
103 n->data = *begin;
104 cx_linked_list_link(prev, n, loc_prev, loc_next);
105 prev = n;
106 }
107 return node_test_data{first};
108 }
110 static node_test_data create_nodes_test_data(std::initializer_list<int> data) {
111 return create_nodes_test_data(data.begin(), data.end());
112 }
114 template<size_t N>
115 struct int_test_data {
116 std::array<int, N> data;
118 int_test_data() {
119 cx_for_n (i, N) data[i] = ::rand(); // NOLINT(cert-msc50-cpp)
120 }
121 };
123 TEST(LinkedList_LowLevel, link_unlink) {
124 node a, b, c;
126 cx_linked_list_link(&a, &b, loc_prev, loc_next);
127 EXPECT_EQ(a.prev, nullptr);
128 EXPECT_EQ(a.next, &b);
129 EXPECT_EQ(b.prev, &a);
130 EXPECT_EQ(b.next, nullptr);
132 cx_linked_list_unlink(&a, &b, loc_prev, loc_next);
133 EXPECT_EQ(a.prev, nullptr);
134 EXPECT_EQ(a.next, nullptr);
135 EXPECT_EQ(b.prev, nullptr);
136 EXPECT_EQ(b.next, nullptr);
138 cx_linked_list_link(&b, &c, loc_prev, loc_next);
139 cx_linked_list_link(&a, &b, loc_prev, loc_next);
140 cx_linked_list_unlink(&b, &c, loc_prev, loc_next);
141 EXPECT_EQ(a.prev, nullptr);
142 EXPECT_EQ(a.next, &b);
143 EXPECT_EQ(b.prev, &a);
144 EXPECT_EQ(b.next, nullptr);
145 EXPECT_EQ(c.prev, nullptr);
146 EXPECT_EQ(c.next, nullptr);
147 }
149 TEST(LinkedList_LowLevel, cx_linked_list_at) {
150 node a, b, c, d;
151 cx_linked_list_link(&a, &b, loc_prev, loc_next);
152 cx_linked_list_link(&b, &c, loc_prev, loc_next);
153 cx_linked_list_link(&c, &d, loc_prev, loc_next);
155 EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 0), &a);
156 EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 1), &b);
157 EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 2), &c);
158 EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 3), &d);
159 EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 4), nullptr);
161 EXPECT_EQ(cx_linked_list_at(&b, 1, loc_prev, 0), &a);
162 EXPECT_EQ(cx_linked_list_at(&b, 1, loc_next, 1), &b);
163 EXPECT_EQ(cx_linked_list_at(&b, 1, loc_next, 2), &c);
164 EXPECT_EQ(cx_linked_list_at(&b, 1, loc_next, 3), &d);
165 EXPECT_EQ(cx_linked_list_at(&b, 1, loc_next, 4), nullptr);
167 EXPECT_EQ(cx_linked_list_at(&d, 3, loc_prev, 0), &a);
168 EXPECT_EQ(cx_linked_list_at(&d, 3, loc_prev, 1), &b);
169 }
171 TEST(LinkedList_LowLevel, cx_linked_list_find) {
172 auto testdata = create_nodes_test_data({2, 4, 6, 8});
173 auto list = testdata.begin;
174 int s;
176 s = 2;
177 EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, false, cmp_int, &s), 0);
178 s = 4;
179 EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, false, cmp_int, &s), 1);
180 s = 6;
181 EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, false, cmp_int, &s), 2);
182 s = 8;
183 EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, false, cmp_int, &s), 3);
184 s = 10;
185 EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, false, cmp_int, &s), 4);
186 s = -2;
187 EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, false, cmp_int, &s), 4);
188 }
190 TEST(LinkedList_LowLevel, cx_linked_list_compare) {
191 auto ta = create_nodes_test_data({2, 4, 6, 8});
192 auto tb = create_nodes_test_data({2, 4, 6});
193 auto tc = create_nodes_test_data({2, 4, 6, 9});
194 auto la = ta.begin, lb = tb.begin, lc = tc.begin;
196 EXPECT_GT(cx_linked_list_compare(la, lb, loc_next, loc_data, false, cmp_int), 0);
197 EXPECT_LT(cx_linked_list_compare(lb, la, loc_next, loc_data, false, cmp_int), 0);
198 EXPECT_GT(cx_linked_list_compare(lc, la, loc_next, loc_data, false, cmp_int), 0);
199 EXPECT_LT(cx_linked_list_compare(la, lc, loc_next, loc_data, false, cmp_int), 0);
200 EXPECT_EQ(cx_linked_list_compare(la, la, loc_next, loc_data, false, cmp_int), 0);
201 }
203 TEST(LinkedList_LowLevel, cx_linked_list_add) {
204 // test with begin, end / prev, next
205 {
206 node nodes[4];
207 void *begin = nullptr, *end = nullptr;
209 cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[0]);
210 EXPECT_EQ(begin, &nodes[0]);
211 EXPECT_EQ(end, &nodes[0]);
212 EXPECT_EQ(nodes[0].prev, nullptr);
213 EXPECT_EQ(nodes[0].next, nullptr);
215 cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[1]);
216 EXPECT_EQ(begin, &nodes[0]);
217 EXPECT_EQ(end, &nodes[1]);
218 EXPECT_EQ(nodes[0].next, &nodes[1]);
219 EXPECT_EQ(nodes[1].prev, &nodes[0]);
220 }
222 // test with begin only / prev, next
223 {
224 node nodes[4];
225 void *begin = nullptr;
227 cx_linked_list_add(&begin, nullptr, loc_prev, loc_next, &nodes[0]);
228 EXPECT_EQ(begin, &nodes[0]);
229 cx_linked_list_add(&begin, nullptr, loc_prev, loc_next, &nodes[1]);
230 EXPECT_EQ(begin, &nodes[0]);
231 EXPECT_EQ(nodes[0].next, &nodes[1]);
232 EXPECT_EQ(nodes[1].prev, &nodes[0]);
234 cx_linked_list_add(&begin, nullptr, loc_prev, loc_next, &nodes[2]);
235 EXPECT_EQ(nodes[1].next, &nodes[2]);
236 EXPECT_EQ(nodes[2].prev, &nodes[1]);
237 }
239 // test with end only / prev, next
240 {
241 node nodes[4];
242 void *end = nullptr;
244 cx_linked_list_add(nullptr, &end, loc_prev, loc_next, &nodes[0]);
245 EXPECT_EQ(end, &nodes[0]);
246 cx_linked_list_add(nullptr, &end, loc_prev, loc_next, &nodes[1]);
247 EXPECT_EQ(end, &nodes[1]);
248 EXPECT_EQ(nodes[0].next, &nodes[1]);
249 EXPECT_EQ(nodes[1].prev, &nodes[0]);
251 cx_linked_list_add(nullptr, &end, loc_prev, loc_next, &nodes[2]);
252 EXPECT_EQ(end, &nodes[2]);
253 EXPECT_EQ(nodes[1].next, &nodes[2]);
254 EXPECT_EQ(nodes[2].prev, &nodes[1]);
255 }
257 // test with begin, end / next
258 {
259 node nodes[4];
260 void *begin = nullptr, *end = nullptr;
262 cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[0]);
263 EXPECT_EQ(begin, &nodes[0]);
264 EXPECT_EQ(end, &nodes[0]);
265 cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[1]);
266 EXPECT_EQ(end, &nodes[1]);
267 EXPECT_EQ(nodes[0].next, &nodes[1]);
268 EXPECT_EQ(nodes[1].prev, nullptr);
269 }
270 }
272 TEST(LinkedList_LowLevel, cx_linked_list_prepend) {
273 // test with begin, end / prev, next
274 {
275 node nodes[4];
276 void *begin = nullptr, *end = nullptr;
278 cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[0]);
279 EXPECT_EQ(begin, &nodes[0]);
280 EXPECT_EQ(end, &nodes[0]);
281 EXPECT_EQ(nodes[0].prev, nullptr);
282 EXPECT_EQ(nodes[0].next, nullptr);
284 cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[1]);
285 EXPECT_EQ(begin, &nodes[1]);
286 EXPECT_EQ(end, &nodes[0]);
287 EXPECT_EQ(nodes[1].next, &nodes[0]);
288 EXPECT_EQ(nodes[0].prev, &nodes[1]);
289 }
291 // test with begin only / prev, next
292 {
293 node nodes[4];
294 void *begin = nullptr;
296 cx_linked_list_prepend(&begin, nullptr, loc_prev, loc_next, &nodes[0]);
297 EXPECT_EQ(begin, &nodes[0]);
298 cx_linked_list_prepend(&begin, nullptr, loc_prev, loc_next, &nodes[1]);
299 EXPECT_EQ(begin, &nodes[1]);
300 EXPECT_EQ(nodes[1].next, &nodes[0]);
301 EXPECT_EQ(nodes[0].prev, &nodes[1]);
303 cx_linked_list_prepend(&begin, nullptr, loc_prev, loc_next, &nodes[2]);
304 EXPECT_EQ(begin, &nodes[2]);
305 EXPECT_EQ(nodes[2].next, &nodes[1]);
306 EXPECT_EQ(nodes[1].prev, &nodes[2]);
307 }
309 // test with end only / prev, next
310 {
311 node nodes[4];
312 void *end = nullptr;
314 cx_linked_list_prepend(nullptr, &end, loc_prev, loc_next, &nodes[0]);
315 EXPECT_EQ(end, &nodes[0]);
316 cx_linked_list_prepend(nullptr, &end, loc_prev, loc_next, &nodes[1]);
317 EXPECT_EQ(end, &nodes[0]);
318 EXPECT_EQ(nodes[1].next, &nodes[0]);
319 EXPECT_EQ(nodes[0].prev, &nodes[1]);
321 cx_linked_list_prepend(nullptr, &end, loc_prev, loc_next, &nodes[2]);
322 EXPECT_EQ(end, &nodes[0]);
323 EXPECT_EQ(nodes[2].next, &nodes[1]);
324 EXPECT_EQ(nodes[1].prev, &nodes[2]);
325 }
327 // test with begin, end / next
328 {
329 node nodes[4];
330 void *begin = nullptr, *end = nullptr;
332 cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[0]);
333 EXPECT_EQ(begin, &nodes[0]);
334 EXPECT_EQ(end, &nodes[0]);
335 cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[1]);
336 cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[2]);
337 EXPECT_EQ(begin, &nodes[2]);
338 EXPECT_EQ(end, &nodes[0]);
339 EXPECT_EQ(nodes[1].next, &nodes[0]);
340 EXPECT_EQ(nodes[2].next, &nodes[1]);
341 EXPECT_EQ(nodes[1].prev, nullptr);
342 EXPECT_EQ(nodes[0].prev, nullptr);
343 }
344 }
346 TEST(LinkedList_LowLevel, cx_linked_list_insert) {
347 // insert mid list
348 {
349 node nodes[4];
350 void *begin = &nodes[0], *end = &nodes[2];
352 cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
353 cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
355 cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3]);
356 EXPECT_EQ(begin, &nodes[0]);
357 EXPECT_EQ(end, &nodes[2]);
358 EXPECT_EQ(nodes[1].next, &nodes[3]);
359 EXPECT_EQ(nodes[2].prev, &nodes[3]);
360 EXPECT_EQ(nodes[3].prev, &nodes[1]);
361 EXPECT_EQ(nodes[3].next, &nodes[2]);
362 }
364 // insert end
365 {
366 node nodes[4];
367 void *begin = &nodes[0], *end = &nodes[2];
369 cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
370 cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
372 cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3]);
373 EXPECT_EQ(begin, &nodes[0]);
374 EXPECT_EQ(end, &nodes[3]);
375 EXPECT_EQ(nodes[2].next, &nodes[3]);
376 EXPECT_EQ(nodes[3].prev, &nodes[2]);
377 EXPECT_EQ(nodes[3].next, nullptr);
378 }
380 // insert begin
381 {
382 node nodes[4];
383 void *begin = &nodes[0], *end = &nodes[2];
385 cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
386 cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
388 cx_linked_list_insert(&begin, &end, loc_prev, loc_next, nullptr, &nodes[3]);
389 EXPECT_EQ(begin, &nodes[3]);
390 EXPECT_EQ(end, &nodes[2]);
391 EXPECT_EQ(nodes[0].prev, &nodes[3]);
392 EXPECT_EQ(nodes[3].prev, nullptr);
393 EXPECT_EQ(nodes[3].next, &nodes[0]);
394 }
395 }
397 TEST(LinkedList_LowLevel, cx_linked_list_insert_chain) {
398 // insert mid list
399 {
400 node nodes[5];
401 void *begin = &nodes[0], *end = &nodes[2];
403 cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
404 cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
405 cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next);
407 cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3], nullptr);
408 EXPECT_EQ(begin, &nodes[0]);
409 EXPECT_EQ(end, &nodes[2]);
410 EXPECT_EQ(nodes[1].next, &nodes[3]);
411 EXPECT_EQ(nodes[2].prev, &nodes[4]);
412 EXPECT_EQ(nodes[3].prev, &nodes[1]);
413 EXPECT_EQ(nodes[4].next, &nodes[2]);
414 }
416 // insert end
417 {
418 node nodes[5];
419 void *begin = &nodes[0], *end = &nodes[2];
421 cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
422 cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
423 cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next);
425 cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3], nullptr);
426 EXPECT_EQ(begin, &nodes[0]);
427 EXPECT_EQ(end, &nodes[4]);
428 EXPECT_EQ(nodes[2].next, &nodes[3]);
429 EXPECT_EQ(nodes[3].prev, &nodes[2]);
430 EXPECT_EQ(nodes[4].next, nullptr);
431 }
433 // insert begin
434 {
435 node nodes[5];
436 void *begin = &nodes[0], *end = &nodes[2];
438 cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
439 cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
440 cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next);
442 cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, nullptr, &nodes[3], nullptr);
443 EXPECT_EQ(begin, &nodes[3]);
444 EXPECT_EQ(end, &nodes[2]);
445 EXPECT_EQ(nodes[0].prev, &nodes[4]);
446 EXPECT_EQ(nodes[3].prev, nullptr);
447 EXPECT_EQ(nodes[4].next, &nodes[0]);
448 }
449 }
451 TEST(LinkedList_LowLevel, cx_linked_list_first) {
452 auto testdata = create_nodes_test_data(3);
453 auto begin = testdata.begin;
454 EXPECT_EQ(cx_linked_list_first(begin, loc_prev), begin);
455 EXPECT_EQ(cx_linked_list_first(begin->next, loc_prev), begin);
456 EXPECT_EQ(cx_linked_list_first(begin->next->next, loc_prev), begin);
457 }
459 TEST(LinkedList_LowLevel, cx_linked_list_last) {
460 auto testdata = create_nodes_test_data(3);
461 auto begin = testdata.begin;
462 auto end = begin->next->next;
463 EXPECT_EQ(cx_linked_list_last(begin, loc_next), end);
464 EXPECT_EQ(cx_linked_list_last(begin->next, loc_next), end);
465 EXPECT_EQ(cx_linked_list_last(begin->next->next, loc_next), end);
466 }
468 TEST(LinkedList_LowLevel, cx_linked_list_prev) {
469 auto testdata = create_nodes_test_data(3);
470 auto begin = testdata.begin;
471 EXPECT_EQ(cx_linked_list_prev(begin, loc_next, begin), nullptr);
472 EXPECT_EQ(cx_linked_list_prev(begin, loc_next, begin->next), begin);
473 EXPECT_EQ(cx_linked_list_prev(begin, loc_next, begin->next->next), begin->next);
474 }
476 TEST(LinkedList_LowLevel, cx_linked_list_remove) {
477 auto testdata = create_nodes_test_data({2, 4, 6});
478 auto begin = reinterpret_cast<void *>(testdata.begin);
479 auto first = testdata.begin;
480 auto second = first->next;
481 auto third = second->next;
482 auto end = reinterpret_cast<void *>(third);
484 cx_linked_list_remove(&begin, &end, loc_prev, loc_next, second);
485 EXPECT_EQ(begin, first);
486 EXPECT_EQ(end, third);
487 EXPECT_EQ(first->prev, nullptr);
488 EXPECT_EQ(first->next, third);
489 EXPECT_EQ(third->prev, first);
490 EXPECT_EQ(third->next, nullptr);
492 cx_linked_list_remove(&begin, &end, loc_prev, loc_next, third);
493 EXPECT_EQ(begin, first);
494 EXPECT_EQ(end, first);
495 EXPECT_EQ(first->prev, nullptr);
496 EXPECT_EQ(first->next, nullptr);
498 cx_linked_list_remove(&begin, &end, loc_prev, loc_next, first);
499 EXPECT_EQ(begin, nullptr);
500 EXPECT_EQ(end, nullptr);
501 }
503 TEST(LinkedList_LowLevel, cx_linked_list_size) {
504 EXPECT_EQ(cx_linked_list_size(nullptr, loc_next), 0);
506 {
507 auto testdata = create_nodes_test_data(5);
508 EXPECT_EQ(cx_linked_list_size(testdata.begin, loc_next), 5);
509 }
511 {
512 auto testdata = create_nodes_test_data(13);
513 EXPECT_EQ(cx_linked_list_size(testdata.begin, loc_next), 13);
514 }
515 }
517 TEST(LinkedList_LowLevel, cx_linked_list_sort) {
518 int_test_data<1500> testdata;
519 std::array<int, 1500> sorted{};
520 std::partial_sort_copy(testdata.data.begin(), testdata.data.end(), sorted.begin(), sorted.end());
522 auto scrambled = create_nodes_test_data(testdata.data.begin(), testdata.data.end());
523 void *begin = scrambled.begin;
524 void *end = cx_linked_list_last(begin, loc_next);
526 cx_linked_list_sort(&begin, &end, loc_prev, loc_next, loc_data,
527 false, cmp_int);
529 node *check = reinterpret_cast<node *>(begin);
530 node *check_last = nullptr;
531 cx_for_n (i, sorted.size()) {
532 EXPECT_EQ(check->data, sorted[i]);
533 EXPECT_EQ(check->prev, check_last);
534 if (i < sorted.size() - 1) {
535 ASSERT_NE(check->next, nullptr);
536 }
537 check_last = check;
538 check = check->next;
539 }
540 EXPECT_EQ(check, nullptr);
541 EXPECT_EQ(end, check_last);
542 }
544 TEST(LinkedList_LowLevel, cx_linked_list_reverse) {
545 auto testdata = create_nodes_test_data({2, 4, 6, 8});
546 auto expected = create_nodes_test_data({8, 6, 4, 2});
548 auto begin = reinterpret_cast<void *>(testdata.begin);
549 auto end = cx_linked_list_last(begin, loc_next);
550 auto orig_begin = begin, orig_end = end;
552 cx_linked_list_reverse(&begin, &end, loc_prev, loc_next);
553 EXPECT_EQ(end, orig_begin);
554 EXPECT_EQ(begin, orig_end);
555 EXPECT_EQ(cx_linked_list_compare(begin, expected.begin, loc_next, loc_data, 0, cmp_int), 0);
556 }
558 class HighLevelTest : public ::testing::Test {
559 mutable std::unordered_set<CxList *> lists;
560 protected:
561 CxTestingAllocator testingAllocator;
563 void TearDown() override {
564 for (auto &&l: lists) cxListDestroy(l);
565 EXPECT_TRUE(testingAllocator.verify());
566 }
568 static constexpr size_t testdata_len = 250;
569 int_test_data<testdata_len> testdata;
571 auto autofree(CxList *list) const -> CxList * {
572 lists.insert(list);
573 return list;
574 }
576 auto linkedListFromTestData() const -> CxList * {
577 return autofree(
578 cxLinkedListFromArray(
579 &testingAllocator,
580 cmp_int,
581 sizeof(int),
582 testdata_len,
583 testdata.data.data()
584 )
585 );
586 }
588 auto pointerLinkedListFromTestData() const -> CxList * {
589 auto list = autofree(cxPointerLinkedListCreate(&testingAllocator, cmp_int));
590 cx_for_n(i, testdata_len) cxListAdd(list, &testdata.data[i]);
591 return list;
592 }
594 void verifyCreate(CxList *list) const {
595 EXPECT_EQ(list->size, 0);
596 EXPECT_EQ(list->capacity, (size_t) -1);
597 EXPECT_EQ(list->allocator, &testingAllocator);
598 EXPECT_EQ(list->cmpfunc, cmp_int);
599 }
601 void verifyAdd(CxList *list, bool write_through) {
602 auto len = testdata_len;
603 cx_for_n (i, len) EXPECT_EQ(cxListAdd(list, &testdata.data[i]), 0);
604 EXPECT_EQ(list->size, len);
605 EXPECT_GE(list->capacity, list->size);
606 cx_for_n (i, len) EXPECT_EQ(*(int *) cxListAt(list, i), testdata.data[i]);
607 cx_for_n (i, len) ++testdata.data[i];
608 if (write_through) {
609 cx_for_n (i, len) EXPECT_EQ(*(int *) cxListAt(list, i), testdata.data[i]);
610 } else {
611 cx_for_n (i, len) EXPECT_EQ(*(int *) cxListAt(list, i), testdata.data[i] - 1);
612 }
613 }
615 static void verifyInsert(CxList *list) {
616 int a = 5, b = 47, c = 13, d = 42;
618 EXPECT_NE(cxListInsert(list, 1, &a), 0);
619 EXPECT_EQ(list->size, 0);
620 EXPECT_EQ(cxListInsert(list, 0, &a), 0);
621 EXPECT_EQ(list->size, 1);
622 EXPECT_EQ(cxListInsert(list, 0, &b), 0);
623 EXPECT_EQ(list->size, 2);
624 EXPECT_EQ(cxListInsert(list, 1, &c), 0);
625 EXPECT_EQ(list->size, 3);
626 EXPECT_EQ(cxListInsert(list, 3, &d), 0);
628 EXPECT_EQ(list->size, 4);
629 EXPECT_GE(list->capacity, list->size);
631 EXPECT_EQ(*(int *) cxListAt(list, 0), 47);
632 EXPECT_EQ(*(int *) cxListAt(list, 1), 13);
633 EXPECT_EQ(*(int *) cxListAt(list, 2), 5);
634 EXPECT_EQ(*(int *) cxListAt(list, 3), 42);
635 }
637 void verifyRemove(CxList *list) const {
638 EXPECT_EQ(cxListRemove(list, 2), 0);
639 EXPECT_EQ(cxListRemove(list, 4), 0);
640 EXPECT_EQ(list->size, testdata_len - 2);
641 EXPECT_GE(list->capacity, list->size);
642 EXPECT_EQ(*(int *) cxListAt(list, 0), testdata.data[0]);
643 EXPECT_EQ(*(int *) cxListAt(list, 1), testdata.data[1]);
644 EXPECT_EQ(*(int *) cxListAt(list, 2), testdata.data[3]);
645 EXPECT_EQ(*(int *) cxListAt(list, 3), testdata.data[4]);
646 EXPECT_EQ(*(int *) cxListAt(list, 4), testdata.data[6]);
648 EXPECT_EQ(cxListRemove(list, 0), 0);
649 EXPECT_EQ(list->size, testdata_len - 3);
650 EXPECT_GE(list->capacity, list->size);
651 EXPECT_EQ(*(int *) cxListAt(list, 0), testdata.data[1]);
652 EXPECT_EQ(*(int *) cxListAt(list, 1), testdata.data[3]);
654 EXPECT_NE(cxListRemove(list, testdata_len), 0);
655 }
657 void verifyAt(CxList *list) const {
658 auto len = testdata_len;
659 EXPECT_EQ(list->size, len);
660 cx_for_n (i, len) {
661 EXPECT_EQ(*(int *) cxListAt(list, i), testdata.data[i]);
662 }
663 EXPECT_EQ(cxListAt(list, list->size), nullptr);
664 }
666 void verifyFind(CxList *list) const {
667 cx_for_n (attempt, 25) {
668 size_t exp = rand() % testdata_len; // NOLINT(cert-msc50-cpp)
669 int val = testdata.data[exp];
670 // randomly picked number could occur earlier in list - find first position
671 cx_for_n (i, exp) {
672 if (testdata.data[i] == val) {
673 exp = i;
674 break;
675 }
676 }
677 EXPECT_EQ(cxListFind(list, &val), exp);
678 }
679 }
681 void verifySort(CxList *list) const {
682 std::array<int, testdata_len> expected{};
683 std::partial_sort_copy(testdata.data.begin(), testdata.data.end(), expected.begin(), expected.end());
684 cxListSort(list);
685 cx_for_n (i, testdata_len) ASSERT_EQ(*(int *) cxListAt(list, i), expected[i]);
686 }
688 void verifyIterator(CxList *list) const {
689 int i = 0;
690 CxIterator iter = cxListBegin(list);
691 cx_foreach(int*, x, iter) {
692 ASSERT_EQ(iter.index, (size_t) (i + 1) / 2);
693 ASSERT_EQ(*x, testdata.data[i]);
694 if (i % 2 == 1) iter.remove = true;
695 i++;
696 }
697 auto len = testdata_len;
698 EXPECT_EQ(i, len);
699 ASSERT_EQ(list->size, len / 2);
700 cx_for_n(j, len / 2) ASSERT_EQ(*(int *) cxListAt(list, j), testdata.data[j * 2]);
701 }
703 static void verifyInsertViaIterator(CxList *list) {
704 int newdata[] = {10, 20, 30, 40, 50};
706 CxIterator iter = cxListIterator(list, 2);
707 EXPECT_TRUE(cxIteratorValid(&iter));
708 EXPECT_EQ(iter.index, 2);
709 EXPECT_EQ(*(int *) cxIteratorCurrent(&iter), 2);
710 cxListInsertAfter(&iter, &newdata[0]);
711 EXPECT_TRUE(cxIteratorValid(&iter));
712 EXPECT_EQ(iter.index, 2);
713 EXPECT_EQ(*(int *) cxIteratorCurrent(&iter), 2);
714 cxListInsertBefore(&iter, &newdata[1]);
715 EXPECT_TRUE(cxIteratorValid(&iter));
716 EXPECT_EQ(iter.index, 3);
717 EXPECT_EQ(*(int *) cxIteratorCurrent(&iter), 2);
719 iter = cxListBegin(list);
720 cxListInsertBefore(&iter, &newdata[2]);
721 EXPECT_TRUE(cxIteratorValid(&iter));
722 EXPECT_EQ(iter.index, 1);
723 EXPECT_EQ(*(int *) cxIteratorCurrent(&iter), 0);
724 iter = cxListIterator(list, list->size);
725 cxListInsertBefore(&iter, &newdata[3]);
726 EXPECT_FALSE(cxIteratorValid(&iter));
727 EXPECT_EQ(iter.index, 9);
728 iter = cxListIterator(list, list->size);
729 cxListInsertAfter(&iter, &newdata[4]);
730 EXPECT_FALSE(cxIteratorValid(&iter));
731 EXPECT_EQ(iter.index, 10);
733 int expdata[] = {30, 0, 1, 20, 2, 10, 3, 4, 40, 50};
734 cx_for_n (j, 10) EXPECT_EQ(*(int *) cxListAt(list, j), expdata[j]);
735 }
737 void verifyReverse(CxList *list) const {
738 cxListReverse(list);
739 cx_for_n(i, testdata_len) {
740 ASSERT_EQ(*(int *) cxListAt(list, i), testdata.data[testdata_len - 1 - i]);
741 }
742 }
744 static void verifyCompare(CxList *left, CxList *right) {
745 EXPECT_EQ(cxListCompare(left, right), 0);
746 int x = 42;
747 cxListAdd(left, &x);
748 ASSERT_GT(left->size, right->size);
749 EXPECT_GT(cxListCompare(left, right), 0);
750 EXPECT_LT(cxListCompare(right, left), 0);
751 cxListAdd(right, &x);
752 ASSERT_EQ(left->size, right->size);
753 EXPECT_EQ(cxListCompare(left, right), 0);
754 int a = 5, b = 10;
755 cxListInsert(left, 15, &a);
756 cxListInsert(right, 15, &b);
757 ASSERT_EQ(left->size, right->size);
758 EXPECT_LT(cxListCompare(left, right), 0);
759 EXPECT_GT(cxListCompare(right, left), 0);
760 *(int*)cxListAt(left, 15) = 10;
761 EXPECT_EQ(cxListCompare(left, right), 0);
762 }
763 };
765 class LinkedList : public HighLevelTest {
766 };
768 class PointerLinkedList : public HighLevelTest {
769 };
771 TEST_F(LinkedList, cxLinkedListCreate) {
772 CxList *list = autofree(cxLinkedListCreate(&testingAllocator, cmp_int, sizeof(int)));
773 EXPECT_EQ(list->itemsize, sizeof(int));
774 verifyCreate(list);
775 }
777 TEST_F(PointerLinkedList, cxPointerLinkedListCreate) {
778 CxList *list = autofree(cxPointerLinkedListCreate(&testingAllocator, cmp_int));
779 EXPECT_EQ(list->itemsize, sizeof(void *));
780 verifyCreate(list);
781 }
783 TEST_F(LinkedList, cxLinkedListFromArray) {
784 CxList *expected = autofree(cxLinkedListCreate(&testingAllocator, cmp_int, sizeof(int)));
785 cx_for_n (i, testdata_len) cxListAdd(expected, &testdata.data[i]);
786 CxList *list = autofree(cxLinkedListFromArray(&testingAllocator, cmp_int, sizeof(int),
787 testdata_len, testdata.data.data()));
788 EXPECT_EQ(cxListCompare(list, expected), 0);
789 }
791 TEST_F(LinkedList, cxListAdd) {
792 CxList *list = autofree(cxLinkedListCreate(&testingAllocator, cmp_int, sizeof(int)));
793 verifyAdd(list, false);
794 }
796 TEST_F(PointerLinkedList, cxListAdd) {
797 CxList *list = autofree(cxPointerLinkedListCreate(&testingAllocator, cmp_int));
798 verifyAdd(list, true);
799 }
801 TEST_F(LinkedList, cxListInsert) {
802 verifyInsert(autofree(cxLinkedListCreate(&testingAllocator, cmp_int, sizeof(int))));
803 }
805 TEST_F(PointerLinkedList, cxListInsert) {
806 verifyInsert(autofree(cxPointerLinkedListCreate(&testingAllocator, cmp_int)));
807 }
809 TEST_F(LinkedList, cxListRemove) {
810 verifyRemove(linkedListFromTestData());
811 }
813 TEST_F(PointerLinkedList, cxListRemove) {
814 verifyRemove(pointerLinkedListFromTestData());
815 }
817 TEST_F(LinkedList, cxListAt) {
818 verifyAt(linkedListFromTestData());
819 }
821 TEST_F(PointerLinkedList, cxListAt) {
822 verifyAt(pointerLinkedListFromTestData());
823 }
825 TEST_F(LinkedList, cxListFind) {
826 verifyFind(linkedListFromTestData());
827 }
829 TEST_F(PointerLinkedList, cxListFind) {
830 verifyFind(pointerLinkedListFromTestData());
831 }
833 TEST_F(LinkedList, cxListSort) {
834 verifySort(linkedListFromTestData());
835 }
837 TEST_F(PointerLinkedList, cxListSort) {
838 verifySort(pointerLinkedListFromTestData());
839 }
841 TEST_F(LinkedList, Iterator) {
842 verifyIterator(linkedListFromTestData());
843 }
845 TEST_F(PointerLinkedList, Iterator) {
846 verifyIterator(pointerLinkedListFromTestData());
847 }
849 TEST_F(LinkedList, InsertViaIterator) {
850 int fivenums[] = {0, 1, 2, 3, 4, 5};
851 CxList *list = autofree(cxLinkedListFromArray(&testingAllocator, cmp_int, sizeof(int), 5, fivenums));
852 verifyInsertViaIterator(list);
853 }
855 TEST_F(PointerLinkedList, InsertViaIterator) {
856 int fivenums[] = {0, 1, 2, 3, 4, 5};
857 CxList *list = autofree(cxPointerLinkedListCreate(&testingAllocator, cmp_int));
858 cx_for_n (i, 5) cxListAdd(list, &fivenums[i]);
859 verifyInsertViaIterator(list);
860 }
862 TEST_F(LinkedList, cxListReverse) {
863 verifyReverse(linkedListFromTestData());
864 }
866 TEST_F(PointerLinkedList, cxListReverse) {
867 verifyReverse(pointerLinkedListFromTestData());
868 }
870 TEST_F(LinkedList, cxListCompare) {
871 auto left = linkedListFromTestData();
872 auto right = linkedListFromTestData();
873 verifyCompare(left, right);
874 }
876 TEST_F(PointerLinkedList, cxListCompare) {
877 auto left = pointerLinkedListFromTestData();
878 auto right = pointerLinkedListFromTestData();
879 verifyCompare(left, right);
880 }
