test/test_list.cpp@7df0bcaecffa
test/test_list.cpp
Tue, 04 Oct 2022 19:25:07 +0200
- author
- Mike Becker <universe@uap-core.de>
- date
- Tue, 04 Oct 2022 19:25:07 +0200
- changeset 591
- 7df0bcaecffa
- parent 552
- 4373c2a90066
- child 602
- 3b071ea0e9cf
- permissions
- -rw-r--r--
fix over-optimization of strstr
1. it's actually less performant to frequently read bytes
from an array instead of using the native word length
2. the SBO buffer should be local and not static to allow
multi-threading usage
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, false, cmp_int), 0);
200 EXPECT_LT(cx_linked_list_compare(lb, la, loc_next, loc_data, false, false, cmp_int), 0);
201 EXPECT_GT(cx_linked_list_compare(lc, la, loc_next, loc_data, false, false, cmp_int), 0);
202 EXPECT_LT(cx_linked_list_compare(la, lc, loc_next, loc_data, false, false, cmp_int), 0);
203 EXPECT_EQ(cx_linked_list_compare(la, la, loc_next, loc_data, false, 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, false, false, 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(LinkedList, cxListCompareWithPtrList) {
887 auto left = linkedListFromTestData();
888 auto right = pointerLinkedListFromTestData();
889 verifyCompare(left, right);
890 }
892 TEST_F(PointerLinkedList, cxListCompare) {
893 auto left = pointerLinkedListFromTestData();
894 auto right = pointerLinkedListFromTestData();
895 verifyCompare(left, right);
896 }
898 TEST_F(PointerLinkedList, cxListCompareWithNormalList) {
899 auto left = pointerLinkedListFromTestData();
900 auto right = linkedListFromTestData();
901 verifyCompare(left, right);
902 }
904 TEST_F(PointerLinkedList, NoDestructor) {
905 void *item = cxMalloc(&testingAllocator, sizeof(int));
906 auto list = cxPointerLinkedListCreate(cxDefaultAllocator, cmp_int);
907 cxListAdd(list, item);
908 ASSERT_FALSE(testingAllocator.verify());
909 cxListDestroy(list);
910 EXPECT_FALSE(testingAllocator.verify());
911 cxFree(&testingAllocator, item);
912 EXPECT_TRUE(testingAllocator.verify());
913 }
915 TEST_F(PointerLinkedList, SimpleDestructor) {
916 int item = 0;
917 auto list = cxPointerLinkedListCreate(cxDefaultAllocator, cmp_int);
918 list->content_destructor_type = CX_DESTRUCTOR_SIMPLE;
919 list->simple_destructor = [](void *elem) { *(int *) elem = 42; };
920 cxListAdd(list, &item);
921 cxListDestroy(list);
922 EXPECT_EQ(item, 42);
923 }
925 TEST_F(PointerLinkedList, AdvancedDestructor) {
926 void *item = cxMalloc(&testingAllocator, sizeof(int));
927 auto list = cxPointerLinkedListCreate(cxDefaultAllocator, cmp_int);
928 list->content_destructor_type = CX_DESTRUCTOR_ADVANCED;
929 list->advanced_destructor.data = &testingAllocator;
930 list->advanced_destructor.func = (cx_destructor_func2) cxFree;
931 cxListAdd(list, item);
932 ASSERT_FALSE(testingAllocator.verify());
933 cxListDestroy(list);
934 EXPECT_TRUE(testingAllocator.verify());
935 }
