test/test_list.c@0d3c6075f82c
test/test_list.c
Sat, 09 Apr 2022 18:02:53 +0200
- author
- Mike Becker <universe@uap-core.de>
- date
- Sat, 09 Apr 2022 18:02:53 +0200
- changeset 509
- 0d3c6075f82c
- parent 507
- 2e8878770de0
- permissions
- -rw-r--r--
#129 - remove test code duplication
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 "test_config.h"
32 #include "util_allocator.h"
34 static int cmp_int_impl(
35 int const *l,
36 int const *r
37 ) {
38 int left = *l, right = *r;
39 return left == right ? 0 : (left < right ? -1 : 1);
40 }
42 #define cmp_int ((CxListComparator) cmp_int_impl)
44 struct node {
45 struct node *next;
46 struct node *prev;
47 int data;
48 };
50 #define nd(name) name = {0}
52 const ptrdiff_t loc_prev = offsetof(struct node, prev);
53 const ptrdiff_t loc_next = offsetof(struct node, next);
54 const ptrdiff_t loc_data = offsetof(struct node, data);
56 static struct node *create_nodes_test_data(
57 size_t n,
58 int const data[]
59 ) {
60 CU_ASSERT_NOT_EQUAL_FATAL(n, 0)
61 struct node *begin = calloc(1, sizeof(struct node));
62 struct node *prev = begin;
63 if (data) begin->data = data[0];
64 for (size_t i = 1; i < n; i++) {
65 struct node *node = calloc(1, sizeof(struct node));
66 if (data) node->data = data[i];
67 cx_linked_list_link(prev, node, loc_prev, loc_next);
68 prev = node;
69 }
70 return begin;
71 }
73 static void destroy_nodes_test_data(struct node *begin) {
74 struct node *node = begin;
75 while (node) {
76 struct node *next = node->next;
77 free(node);
78 node = next;
79 }
80 }
82 static int *create_ints_test_data(size_t len) {
83 int *data = malloc(sizeof(int) * len);
84 cx_for_n (i, len) data[i] = rand(); // NOLINT(cert-msc50-cpp)
85 return data;
86 }
88 void test_linked_list_link_unlink(void) {
90 struct node nd(a), nd(b), nd(c);
92 cx_linked_list_link(&a, &b, loc_prev, loc_next);
93 CU_ASSERT_PTR_NULL(a.prev)
94 CU_ASSERT_PTR_EQUAL(a.next, &b)
95 CU_ASSERT_PTR_EQUAL(b.prev, &a)
96 CU_ASSERT_PTR_NULL(b.next)
98 cx_linked_list_unlink(&a, &b, loc_prev, loc_next);
99 CU_ASSERT_PTR_NULL(a.prev)
100 CU_ASSERT_PTR_NULL(a.next)
101 CU_ASSERT_PTR_NULL(b.prev)
102 CU_ASSERT_PTR_NULL(b.next)
104 cx_linked_list_link(&b, &c, loc_prev, loc_next);
105 cx_linked_list_link(&a, &b, loc_prev, loc_next);
106 cx_linked_list_unlink(&b, &c, loc_prev, loc_next);
107 CU_ASSERT_PTR_NULL(a.prev)
108 CU_ASSERT_PTR_EQUAL(a.next, &b)
109 CU_ASSERT_PTR_EQUAL(b.prev, &a)
110 CU_ASSERT_PTR_NULL(b.next)
111 CU_ASSERT_PTR_NULL(c.prev)
112 CU_ASSERT_PTR_NULL(c.next)
113 }
115 void test_linked_list_at(void) {
116 struct node nd(a), nd(b), nd(c), nd(d);
117 cx_linked_list_link(&a, &b, loc_prev, loc_next);
118 cx_linked_list_link(&b, &c, loc_prev, loc_next);
119 cx_linked_list_link(&c, &d, loc_prev, loc_next);
121 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&a, 0, loc_next, 0), &a)
122 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&a, 0, loc_next, 1), &b)
123 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&a, 0, loc_next, 2), &c)
124 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&a, 0, loc_next, 3), &d)
125 CU_ASSERT_PTR_NULL(cx_linked_list_at(&a, 0, loc_next, 4))
127 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&b, 1, loc_prev, 0), &a)
128 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&b, 1, loc_next, 1), &b)
129 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&b, 1, loc_next, 2), &c)
130 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&b, 1, loc_next, 3), &d)
131 CU_ASSERT_PTR_NULL(cx_linked_list_at(&b, 1, loc_next, 4))
133 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&d, 3, loc_prev, 0), &a)
134 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&d, 3, loc_prev, 1), &b)
135 }
137 void test_linked_list_find(void) {
138 int data[] = {2, 4, 6, 8};
139 void *list = create_nodes_test_data(4, data);
140 int s;
142 s = 2;
143 CU_ASSERT_EQUAL(cx_linked_list_find(list, loc_next, loc_data,
144 false, cmp_int, &s), 0)
145 s = 4;
146 CU_ASSERT_EQUAL(cx_linked_list_find(list, loc_next, loc_data,
147 false, cmp_int, &s), 1)
148 s = 6;
149 CU_ASSERT_EQUAL(cx_linked_list_find(list, loc_next, loc_data,
150 false, cmp_int, &s), 2)
151 s = 8;
152 CU_ASSERT_EQUAL(cx_linked_list_find(list, loc_next, loc_data,
153 false, cmp_int, &s), 3)
154 s = 10;
155 CU_ASSERT_EQUAL(cx_linked_list_find(list, loc_next, loc_data,
156 false, cmp_int, &s), 4)
157 s = -2;
158 CU_ASSERT_EQUAL(cx_linked_list_find(list, loc_next, loc_data,
159 false, cmp_int, &s), 4)
160 }
162 void test_linked_list_compare(void) {
163 int a[] = {2, 4, 6, 8};
164 int b[] = {2, 4, 6};
165 int c[] = {2, 4, 6, 9};
167 void *la = create_nodes_test_data(4, a);
168 void *lb = create_nodes_test_data(3, b);
169 void *lc = create_nodes_test_data(4, c);
171 CU_ASSERT_TRUE(0 < cx_linked_list_compare(la, lb, loc_next, loc_data,
172 false, cmp_int)
173 )
174 CU_ASSERT_TRUE(0 > cx_linked_list_compare(lb, la, loc_next, loc_data,
175 false, cmp_int)
176 )
177 CU_ASSERT_TRUE(0 < cx_linked_list_compare(lc, la, loc_next, loc_data,
178 false, cmp_int)
179 )
180 CU_ASSERT_TRUE(0 > cx_linked_list_compare(la, lc, loc_next, loc_data,
181 false, cmp_int)
182 )
183 CU_ASSERT_TRUE(0 == cx_linked_list_compare(la, la, loc_next, loc_data,
184 false, cmp_int)
185 )
187 destroy_nodes_test_data(la);
188 destroy_nodes_test_data(lb);
189 destroy_nodes_test_data(lc);
190 }
192 void test_linked_list_add(void) {
193 struct node nodes[4];
194 void *begin, *end;
196 // test with begin, end / prev, next
197 memset(nodes, 0, 4 * sizeof(struct node));
198 begin = end = NULL;
200 cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[0]);
201 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
202 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
203 CU_ASSERT_PTR_NULL(nodes[0].prev)
204 CU_ASSERT_PTR_NULL(nodes[0].next)
206 cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[1]);
207 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
208 CU_ASSERT_PTR_EQUAL(end, &nodes[1])
209 CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1])
210 CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[0])
212 // test with begin only / prev, next
213 memset(nodes, 0, 4 * sizeof(struct node));
214 begin = end = NULL;
216 cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[0]);
217 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
218 cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[1]);
219 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
220 CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1])
221 CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[0])
223 cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[2]);
224 CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[2])
225 CU_ASSERT_PTR_EQUAL(nodes[2].prev, &nodes[1])
227 // test with end only / prev, next
228 memset(nodes, 0, 4 * sizeof(struct node));
229 begin = end = NULL;
231 cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[0]);
232 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
233 cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[1]);
234 CU_ASSERT_PTR_EQUAL(end, &nodes[1])
235 CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1])
236 CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[0])
238 cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[2]);
239 CU_ASSERT_PTR_EQUAL(end, &nodes[2])
240 CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[2])
241 CU_ASSERT_PTR_EQUAL(nodes[2].prev, &nodes[1])
243 // test with begin, end / next
244 memset(nodes, 0, 4 * sizeof(struct node));
245 begin = end = NULL;
247 cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[0]);
248 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
249 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
250 cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[1]);
251 CU_ASSERT_PTR_EQUAL(end, &nodes[1])
252 CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1])
253 CU_ASSERT_PTR_NULL(nodes[1].prev)
254 }
256 void test_linked_list_prepend(void) {
257 struct node nodes[4];
258 void *begin, *end;
260 // test with begin, end / prev, next
261 memset(nodes, 0, 4 * sizeof(struct node));
262 begin = end = NULL;
264 cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[0]);
265 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
266 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
267 CU_ASSERT_PTR_NULL(nodes[0].prev)
268 CU_ASSERT_PTR_NULL(nodes[0].next)
270 cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[1]);
271 CU_ASSERT_PTR_EQUAL(begin, &nodes[1])
272 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
273 CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[0])
274 CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[1])
276 // test with begin only / prev, next
277 memset(nodes, 0, 4 * sizeof(struct node));
278 begin = end = NULL;
280 cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[0]);
281 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
282 cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[1]);
283 CU_ASSERT_PTR_EQUAL(begin, &nodes[1])
284 CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[0])
285 CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[1])
287 cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[2]);
288 CU_ASSERT_PTR_EQUAL(begin, &nodes[2])
289 CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[1])
290 CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[2])
292 // test with end only / prev, next
293 memset(nodes, 0, 4 * sizeof(struct node));
294 begin = end = NULL;
296 cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[0]);
297 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
298 cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[1]);
299 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
300 CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[0])
301 CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[1])
303 cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[2]);
304 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
305 CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[1])
306 CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[2])
308 // test with begin, end / next
309 memset(nodes, 0, 4 * sizeof(struct node));
310 begin = end = NULL;
312 cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[0]);
313 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
314 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
315 cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[1]);
316 cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[2]);
317 CU_ASSERT_PTR_EQUAL(begin, &nodes[2])
318 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
319 CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[0])
320 CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[1])
321 CU_ASSERT_PTR_NULL(nodes[1].prev)
322 CU_ASSERT_PTR_NULL(nodes[0].prev)
323 }
325 void test_linked_list_insert(void) {
326 struct node nodes[4];
327 void *begin, *end;
329 // insert mid list
330 memset(nodes, 0, 4 * sizeof(struct node));
331 begin = &nodes[0];
332 end = &nodes[2];
334 cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
335 cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
337 cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3]);
338 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
339 CU_ASSERT_PTR_EQUAL(end, &nodes[2])
340 CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[3])
341 CU_ASSERT_PTR_EQUAL(nodes[2].prev, &nodes[3])
342 CU_ASSERT_PTR_EQUAL(nodes[3].prev, &nodes[1])
343 CU_ASSERT_PTR_EQUAL(nodes[3].next, &nodes[2])
345 // insert end
346 memset(nodes, 0, 4 * sizeof(struct node));
347 begin = &nodes[0];
348 end = &nodes[2];
350 cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
351 cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
353 cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3]);
354 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
355 CU_ASSERT_PTR_EQUAL(end, &nodes[3])
356 CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[3])
357 CU_ASSERT_PTR_EQUAL(nodes[3].prev, &nodes[2])
358 CU_ASSERT_PTR_NULL(nodes[3].next)
360 // insert begin
361 memset(nodes, 0, 4 * sizeof(struct node));
362 begin = &nodes[0];
363 end = &nodes[2];
365 cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
366 cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
368 cx_linked_list_insert(&begin, &end, loc_prev, loc_next, NULL, &nodes[3]);
369 CU_ASSERT_PTR_EQUAL(begin, &nodes[3])
370 CU_ASSERT_PTR_EQUAL(end, &nodes[2])
371 CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[3])
372 CU_ASSERT_PTR_NULL(nodes[3].prev)
373 CU_ASSERT_PTR_EQUAL(nodes[3].next, &nodes[0])
374 }
376 void test_linked_list_insert_chain(void) {
377 struct node nodes[5];
378 void *begin, *end;
380 // insert mid list
381 memset(nodes, 0, 5 * sizeof(struct node));
382 begin = &nodes[0];
383 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);
387 cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next);
389 cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3], NULL);
390 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
391 CU_ASSERT_PTR_EQUAL(end, &nodes[2])
392 CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[3])
393 CU_ASSERT_PTR_EQUAL(nodes[2].prev, &nodes[4])
394 CU_ASSERT_PTR_EQUAL(nodes[3].prev, &nodes[1])
395 CU_ASSERT_PTR_EQUAL(nodes[4].next, &nodes[2])
397 // insert end
398 memset(nodes, 0, 5 * sizeof(struct node));
399 begin = &nodes[0];
400 end = &nodes[2];
402 cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
403 cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
404 cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next);
406 cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3], NULL);
407 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
408 CU_ASSERT_PTR_EQUAL(end, &nodes[4])
409 CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[3])
410 CU_ASSERT_PTR_EQUAL(nodes[3].prev, &nodes[2])
411 CU_ASSERT_PTR_NULL(nodes[4].next)
413 // insert begin
414 memset(nodes, 0, 5 * sizeof(struct node));
415 begin = &nodes[0];
416 end = &nodes[2];
418 cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
419 cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
420 cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next);
422 cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, NULL, &nodes[3], NULL);
423 CU_ASSERT_PTR_EQUAL(begin, &nodes[3])
424 CU_ASSERT_PTR_EQUAL(end, &nodes[2])
425 CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[4])
426 CU_ASSERT_PTR_NULL(nodes[3].prev)
427 CU_ASSERT_PTR_EQUAL(nodes[4].next, &nodes[0])
428 }
430 void test_linked_list_first(void) {
431 struct node *begin = create_nodes_test_data(3, NULL);
432 CU_ASSERT_PTR_EQUAL(cx_linked_list_first(begin, loc_prev), begin)
433 CU_ASSERT_PTR_EQUAL(cx_linked_list_first(begin->next, loc_prev), begin)
434 CU_ASSERT_PTR_EQUAL(cx_linked_list_first(begin->next->next, loc_prev), begin)
435 destroy_nodes_test_data(begin);
436 }
438 void test_linked_list_last(void) {
439 struct node *begin = create_nodes_test_data(3, NULL);
440 struct node *end = begin->next->next;
441 CU_ASSERT_PTR_EQUAL(cx_linked_list_last(begin, loc_next), end)
442 CU_ASSERT_PTR_EQUAL(cx_linked_list_last(begin->next, loc_next), end)
443 CU_ASSERT_PTR_EQUAL(cx_linked_list_last(begin->next->next, loc_next), end)
444 destroy_nodes_test_data(begin);
445 }
447 void test_linked_list_prev(void) {
448 struct node *begin = create_nodes_test_data(3, NULL);
449 CU_ASSERT_PTR_NULL(cx_linked_list_prev(begin, loc_next, begin))
450 CU_ASSERT_PTR_EQUAL(cx_linked_list_prev(begin, loc_next, begin->next), begin)
451 CU_ASSERT_PTR_EQUAL(cx_linked_list_prev(begin, loc_next, begin->next->next), begin->next)
452 destroy_nodes_test_data(begin);
453 }
455 void test_linked_list_remove(void) {
456 void *begin, *end;
458 int data[] = {2, 4, 6};
459 begin = create_nodes_test_data(3, data);
460 struct node *first = begin;
461 struct node *second = first->next;
462 struct node *third = second->next;
463 end = third;
465 cx_linked_list_remove(&begin, &end, loc_prev, loc_next, second);
466 CU_ASSERT_PTR_EQUAL(begin, first)
467 CU_ASSERT_PTR_EQUAL(end, third)
468 CU_ASSERT_PTR_NULL(first->prev)
469 CU_ASSERT_PTR_EQUAL(first->next, third)
470 CU_ASSERT_PTR_EQUAL(third->prev, first)
471 CU_ASSERT_PTR_NULL(third->next)
473 cx_linked_list_remove(&begin, &end, loc_prev, loc_next, third);
474 CU_ASSERT_PTR_EQUAL(begin, first)
475 CU_ASSERT_PTR_EQUAL(end, first)
476 CU_ASSERT_PTR_NULL(first->prev)
477 CU_ASSERT_PTR_NULL(first->next)
479 cx_linked_list_remove(&begin, &end, loc_prev, loc_next, first);
480 CU_ASSERT_PTR_NULL(begin)
481 CU_ASSERT_PTR_NULL(end)
483 free(first);
484 free(second);
485 free(third);
486 }
488 void test_linked_list_size(void) {
489 struct node *list;
491 CU_ASSERT_PTR_EQUAL(cx_linked_list_size(NULL, loc_next), 0)
493 list = create_nodes_test_data(5, NULL);
494 CU_ASSERT_EQUAL(cx_linked_list_size(list, loc_next), 5)
495 destroy_nodes_test_data(list);
497 list = create_nodes_test_data(13, NULL);
498 CU_ASSERT_EQUAL(cx_linked_list_size(list, loc_next), 13)
499 destroy_nodes_test_data(list);
500 }
502 void test_linked_list_sort(void) {
503 int expected[] = {
504 14, 30, 151, 163, 227, 300, 315, 317, 363, 398, 417, 424, 438, 446, 508, 555, 605, 713, 716, 759, 761, 880,
505 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 1707, 1734, 1771, 1874, 1894,
506 1976, 2079, 2124, 2130, 2135, 2266, 2338, 2358, 2430, 2500, 2540, 2542, 2546, 2711, 2733, 2754, 2764, 2797,
507 2888, 2900, 3020, 3053, 3109, 3244, 3275, 3302, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 3675, 3677,
508 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681,
509 4785, 4791, 4801, 4859, 4903, 4973
510 };
511 int scrambled[] = {
512 759, 716, 880, 761, 2358, 2542, 2500, 2540, 2546, 2711, 2430, 1707, 1874, 1771, 1894, 1734, 1976, 2079,
513 2124, 2130, 2135, 2266, 2338, 2733, 2754, 2764, 2797, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 2888,
514 2900, 3020, 3053, 3109, 3244, 3275, 3302, 438, 446, 508, 555, 605, 713, 14, 30, 151, 163, 227, 300,
515 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 315, 317, 363, 398, 417, 424,
516 3675, 3677, 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4785, 4791, 4801, 4859, 4903, 4973,
517 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681
518 };
520 void *begin = create_nodes_test_data(100, scrambled);
521 void *end = cx_linked_list_last(begin, loc_next);
523 cx_linked_list_sort(&begin, &end, loc_prev, loc_next, loc_data,
524 false, cmp_int);
526 struct node *check = begin;
527 struct node *check_last = NULL;
528 CU_ASSERT_PTR_NULL(check->prev)
529 CU_ASSERT_EQUAL(check->data, expected[0])
530 cx_for_n (i, 100) {
531 CU_ASSERT_EQUAL(check->data, expected[i])
532 CU_ASSERT_PTR_EQUAL(check->prev, check_last)
533 if (i < 99) {
534 CU_ASSERT_PTR_NOT_NULL(check->next)
535 }
536 check_last = check;
537 check = check->next;
538 }
539 CU_ASSERT_PTR_NULL(check)
540 CU_ASSERT_PTR_EQUAL(end, check_last)
542 destroy_nodes_test_data(begin);
543 }
545 void test_linked_list_reverse(void) {
546 void *begin, *end;
548 int data[] = {2, 4, 6, 8};
549 int reversed[] = {8, 6, 4, 2};
551 void *list = create_nodes_test_data(4, data);
552 void *expected = create_nodes_test_data(4, reversed);
554 begin = list;
555 end = cx_linked_list_last(list, loc_next);
557 cx_linked_list_reverse(&begin, &end, loc_prev, loc_next);
558 CU_ASSERT_PTR_EQUAL(end, list)
559 CU_ASSERT_PTR_EQUAL(begin, cx_linked_list_first(end, loc_prev))
560 CU_ASSERT_TRUE(0 == cx_linked_list_compare(begin, expected, loc_next, loc_data,
561 0, cmp_int))
563 destroy_nodes_test_data(begin);
564 destroy_nodes_test_data(expected);
565 }
567 static void verify_linked_list_create(CxList *list) {
568 CU_ASSERT_EQUAL(list->size, 0)
569 CU_ASSERT_EQUAL(list->capacity, (size_t) -1)
570 CU_ASSERT_PTR_EQUAL(list->allocator, cxTestingAllocator)
571 CU_ASSERT_PTR_EQUAL(list->cmpfunc, cmp_int)
573 cxListDestroy(list);
574 }
576 void test_hl_linked_list_create(void) {
577 CxList *list = cxLinkedListCreate(cxTestingAllocator, cmp_int, sizeof(int));
578 CU_ASSERT_EQUAL(list->itemsize, sizeof(int))
579 verify_linked_list_create(list);
580 }
582 void test_hl_ptr_linked_list_create(void) {
583 CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int);
584 CU_ASSERT_EQUAL(list->itemsize, sizeof(void *))
585 verify_linked_list_create(list);
586 }
588 void test_hl_linked_list_from_array(void) {
589 int data[] = {2, 4, 5, 7, 10, 15};
591 CxList *expected = cxLinkedListCreate(cxTestingAllocator, cmp_int, sizeof(int));
592 cx_for_n (i, 5) cxListAdd(expected, &data[i]);
594 CxList *list = cxLinkedListFromArray(cxTestingAllocator, cmp_int, sizeof(int), 5, data);
596 CU_ASSERT_TRUE(0 == cxListCompare(list, expected))
598 cxListDestroy(list);
599 cxListDestroy(expected);
600 }
602 static void verify_hl_linked_list_add(
603 CxList *list,
604 int data[],
605 size_t len,
606 bool write_through
607 ) {
608 cx_for_n (i, len) CU_ASSERT_EQUAL(cxListAdd(list, &data[i]), 0)
609 CU_ASSERT_EQUAL(list->size, len)
610 CU_ASSERT_TRUE(list->capacity >= list->size)
611 cx_for_n (i, len) CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), data[i])
612 cx_for_n (i, len) ++data[i];
613 if (write_through) {
614 cx_for_n (i, len) CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), data[i])
615 } else {
616 cx_for_n (i, len) CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), data[i] - 1)
617 }
618 cxListDestroy(list);
619 }
621 void test_hl_linked_list_add(void) {
622 CxList *list = cxLinkedListCreate(cxTestingAllocator, cmp_int, sizeof(int));
623 int data[] = {5, 47, 13, 9, 18, 1, 42};
624 verify_hl_linked_list_add(list, data, sizeof(data) / sizeof(int), false);
625 }
627 void test_hl_ptr_linked_list_add(void) {
628 CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int);
629 int data[] = {5, 47, 84, 13, 9, 18, 90, 1, 42};
630 verify_hl_linked_list_add(list, data, sizeof(data) / sizeof(int), true);
631 }
633 static void verify_hl_linked_list_insert(CxList *list) {
634 int a = 5, b = 47, c = 13, d = 42;
636 CU_ASSERT_NOT_EQUAL(cxListInsert(list, 1, &a), 0)
637 CU_ASSERT_EQUAL(list->size, 0)
638 CU_ASSERT_EQUAL(cxListInsert(list, 0, &a), 0)
639 CU_ASSERT_EQUAL(list->size, 1)
640 CU_ASSERT_EQUAL(cxListInsert(list, 0, &b), 0)
641 CU_ASSERT_EQUAL(list->size, 2)
642 CU_ASSERT_EQUAL(cxListInsert(list, 1, &c), 0)
643 CU_ASSERT_EQUAL(list->size, 3)
644 CU_ASSERT_EQUAL(cxListInsert(list, 3, &d), 0)
646 CU_ASSERT_EQUAL(list->size, 4)
647 CU_ASSERT_TRUE(list->capacity >= list->size)
649 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
650 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
651 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 5)
652 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 3), 42)
654 cxListDestroy(list);
655 }
657 void test_hl_linked_list_insert(void) {
658 verify_hl_linked_list_insert(cxLinkedListCreate(cxTestingAllocator, cmp_int, sizeof(int)));
659 }
661 void test_hl_ptr_linked_list_insert(void) {
662 verify_hl_linked_list_insert(cxPointerLinkedListCreate(cxTestingAllocator, cmp_int));
663 }
665 static void verify_hl_linked_list_remove(CxList *list) {
666 CU_ASSERT_EQUAL(list->size, 4)
667 CU_ASSERT_TRUE(list->capacity >= list->size)
669 CU_ASSERT_NOT_EQUAL(cxListRemove(list, 4), 0)
671 CU_ASSERT_EQUAL(cxListRemove(list, 2), 0)
672 CU_ASSERT_EQUAL(list->size, 3)
673 CU_ASSERT_TRUE(list->capacity >= list->size)
674 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
675 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
676 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
678 CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
679 CU_ASSERT_EQUAL(list->size, 2)
680 CU_ASSERT_TRUE(list->capacity >= list->size)
681 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
682 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
684 CU_ASSERT_EQUAL(cxListRemove(list, 1), 0)
685 CU_ASSERT_EQUAL(list->size, 1)
686 CU_ASSERT_TRUE(list->capacity >= list->size)
687 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
689 CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
690 CU_ASSERT_EQUAL(list->size, 0)
691 CU_ASSERT_TRUE(list->capacity >= list->size)
693 CU_ASSERT_NOT_EQUAL(cxListRemove(list, 0), 0)
695 cxListDestroy(list);
696 }
698 void test_hl_linked_list_remove(void) {
699 int data[] = {5, 47, 42, 13};
700 CxList *list = cxLinkedListFromArray(cxTestingAllocator, cmp_int,
701 sizeof(int), 4, data);
702 verify_hl_linked_list_remove(list);
703 }
705 void test_hl_ptr_linked_list_remove(void) {
706 int a = 5, b = 47, c = 42, d = 13;
707 CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int);
708 cxListAdd(list, &a);
709 cxListAdd(list, &b);
710 cxListAdd(list, &c);
711 cxListAdd(list, &d);
712 verify_hl_linked_list_remove(list);
713 }
715 static void verify_hl_linked_list_at(
716 CxList *list,
717 size_t len,
718 int *data
719 ) {
720 CU_ASSERT_EQUAL(list->size, len)
721 cx_for_n (i, len) CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), data[i])
722 CU_ASSERT_PTR_NULL(cxListAt(list, len))
723 free(data);
724 cxListDestroy(list);
725 }
727 void test_hl_linked_list_at(void) {
728 size_t len = 100;
729 int *data = create_ints_test_data(len);
730 CxList *list = cxLinkedListFromArray(cxTestingAllocator, cmp_int,
731 sizeof(int), len, data);
732 verify_hl_linked_list_at(list, len, data);
733 }
735 void test_hl_ptr_linked_list_at(void) {
736 size_t len = 250;
737 int *data = create_ints_test_data(len);
738 CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int);
739 cx_for_n (i, len) cxListAdd(list, &data[i]);
740 verify_hl_linked_list_at(list, len, data);
741 }
743 static void verify_hl_linked_list_find(
744 CxList *list,
745 size_t len,
746 int *data
747 ) {
748 cx_for_n (attempt, 100) {
749 size_t exp = rand() % len; // NOLINT(cert-msc50-cpp)
750 int val = data[exp];
751 cx_for_n (i, exp) {
752 if (data[i] == val) {
753 exp = i;
754 break;
755 }
756 }
757 CU_ASSERT_EQUAL(cxListFind(list, &val), exp)
758 }
759 free(data);
760 cxListDestroy(list);
761 }
763 void test_hl_linked_list_find(void) {
764 size_t len = 100;
765 int *data = create_ints_test_data(len);
766 CxList *list = cxLinkedListFromArray(cxTestingAllocator, cmp_int, sizeof(int), len, data);
767 verify_hl_linked_list_find(list, len, data);
768 }
770 void test_hl_ptr_linked_list_find(void) {
771 size_t len = 250;
772 int *data = create_ints_test_data(len);
773 CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int);
774 cx_for_n (i, len) cxListAdd(list, &data[i]);
775 verify_hl_linked_list_find(list, len, data);
776 }
778 struct sort_test_data {
779 size_t len;
780 int *data;
781 int *sorted;
782 };
784 static struct sort_test_data create_sort_test_data(void) {
785 size_t len = 1000;
786 int *data = create_ints_test_data(len);
787 int *sorted = malloc(sizeof(int) * len);
788 memcpy(sorted, data, sizeof(int) * len);
789 qsort(sorted, len, sizeof(int), cmp_int);
790 struct sort_test_data s = {len, data, sorted};
791 return s;
792 }
794 static void free_sort_test_data(struct sort_test_data s) {
795 free(s.data);
796 free(s.sorted);
797 }
799 static void verify_hl_linked_list_sort(
800 CxList *list,
801 struct sort_test_data td
802 ) {
803 cxListSort(list);
804 cx_for_n (i, td.len) CU_ASSERT_EQUAL_FATAL(*(int *) cxListAt(list, i), td.sorted[i])
805 free_sort_test_data(td);
806 cxListDestroy(list);
807 }
809 void test_hl_linked_list_sort(void) {
810 struct sort_test_data td = create_sort_test_data();
811 CxList *list = cxLinkedListFromArray(cxTestingAllocator, cmp_int, sizeof(int), td.len, td.data);
812 verify_hl_linked_list_sort(list, td);
813 }
815 void test_hl_ptr_linked_list_sort(void) {
816 struct sort_test_data td = create_sort_test_data();
817 CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int);
818 cx_for_n (i, td.len) cxListAdd(list, &td.data[i]);
819 verify_hl_linked_list_sort(list, td);
820 }
822 void verify_hl_linked_list_iterator(CxList *list) {
823 int i = 0;
824 CxIterator iter = cxListBegin(list);
825 cx_foreach(int*, x, iter) {
826 CU_ASSERT_EQUAL(iter.index, (size_t) (i + 1) / 2)
827 CU_ASSERT_EQUAL(*x, i)
828 if (*x % 2 == 1) iter.remove = true;
829 i++;
830 }
831 CU_ASSERT_EQUAL(i, 10)
832 CU_ASSERT_EQUAL_FATAL(list->size, 5)
833 cx_for_n(j, 5) CU_ASSERT_EQUAL(*(int *) cxListAt(list, j), (int) j * 2)
834 cxListDestroy(list);
835 }
837 void test_hl_linked_list_iterator(void) {
838 CxList *list = cxLinkedListCreate(cxTestingAllocator, cmp_int, sizeof(int));
839 cx_for_n (i, 10) cxListAdd(list, &i);
840 verify_hl_linked_list_iterator(list);
841 }
843 void test_hl_ptr_linked_list_iterator(void) {
844 CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int);
845 int data[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
846 cx_for_n (i, 10) cxListAdd(list, &data[i]);
847 verify_hl_linked_list_iterator(list);
848 }
850 static void verify_hl_linked_list_insert_via_iterator(
851 CxList *list,
852 int *testdata
853 ) {
854 CxIterator iter = cxListIterator(list, 2);
855 CU_ASSERT_EQUAL(iter.index, 2)
856 CU_ASSERT_EQUAL(*(int *) cxIteratorCurrent(&iter), 2)
857 size_t i = 4;
859 ++i;
860 cxListInsertAfter(&iter, &testdata[i]);
861 CU_ASSERT_EQUAL(iter.index, 2)
862 CU_ASSERT_EQUAL(*(int *) cxIteratorCurrent(&iter), 2)
863 ++i;
864 cxListInsertBefore(&iter, &testdata[i]);
865 CU_ASSERT_EQUAL(iter.index, 3)
866 CU_ASSERT_EQUAL(*(int *) cxIteratorCurrent(&iter), 2)
868 iter = cxListBegin(list);
869 ++i;
870 cxListInsertBefore(&iter, &testdata[i]);
871 CU_ASSERT_EQUAL(iter.index, 1)
872 CU_ASSERT_EQUAL(*(int *) cxIteratorCurrent(&iter), 0)
873 iter = cxListIterator(list, list->size);
874 ++i;
875 cxListInsertBefore(&iter, &testdata[i]);
876 CU_ASSERT_EQUAL(iter.index, 9)
877 CU_ASSERT_FALSE(cxIteratorValid(&iter))
878 iter = cxListIterator(list, list->size);
879 ++i;
880 cxListInsertAfter(&iter, &testdata[i]);
881 CU_ASSERT_EQUAL(iter.index, 10)
882 CU_ASSERT_FALSE(cxIteratorValid(&iter))
884 int expdata[] = {30, 0, 1, 20, 2, 10, 3, 4, 40, 50};
885 cx_for_n (j, 10) CU_ASSERT_EQUAL(*(int *) cxListAt(list, j), expdata[j])
886 cxListDestroy(list);
887 }
889 void test_hl_linked_list_insert_via_iterator(void) {
890 int testdata[] = {0, 1, 2, 3, 4, 10, 20, 30, 40, 50};
891 // only add the first five elements, the remaining five will be inserted
892 CxList *list = cxLinkedListFromArray(cxTestingAllocator, cmp_int, sizeof(int), 5, testdata);
893 verify_hl_linked_list_insert_via_iterator(list, testdata);
894 }
896 void test_hl_ptr_linked_list_insert_via_iterator(void) {
897 int testdata[] = {0, 1, 2, 3, 4, 10, 20, 30, 40, 50};
898 CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int);
899 // only add the first five elements, the remaining five will be inserted
900 cx_for_n (i, 5) cxListAdd(list, &testdata[i]);
901 verify_hl_linked_list_insert_via_iterator(list, testdata);
902 }
904 static void test_setup_allocator(void) {
905 cxTestingAllocatorReset();
906 }
908 static void test_verify_allocator(void) {
909 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
910 }
912 int main() {
913 CU_pSuite suite = NULL;
915 if (CUE_SUCCESS != CU_initialize_registry()) {
916 return CU_get_error();
917 }
919 suite = CU_add_suite("low level linked list", NULL, NULL);
921 cu_add_test(suite, test_linked_list_link_unlink);
922 cu_add_test(suite, test_linked_list_at);
923 cu_add_test(suite, test_linked_list_find);
924 cu_add_test(suite, test_linked_list_compare);
925 cu_add_test(suite, test_linked_list_prepend);
926 cu_add_test(suite, test_linked_list_add);
927 cu_add_test(suite, test_linked_list_insert);
928 cu_add_test(suite, test_linked_list_insert_chain);
929 cu_add_test(suite, test_linked_list_first);
930 cu_add_test(suite, test_linked_list_last);
931 cu_add_test(suite, test_linked_list_prev);
932 cu_add_test(suite, test_linked_list_remove);
933 cu_add_test(suite, test_linked_list_size);
934 cu_add_test(suite, test_linked_list_sort);
935 cu_add_test(suite, test_linked_list_reverse);
937 suite = CU_add_suite_with_setup_and_teardown(
938 "high level linked list", NULL, NULL,
939 test_setup_allocator, test_verify_allocator);
941 cu_add_test(suite, test_hl_linked_list_create);
942 cu_add_test(suite, test_hl_linked_list_from_array);
943 cu_add_test(suite, test_hl_linked_list_add);
944 cu_add_test(suite, test_hl_linked_list_insert);
945 cu_add_test(suite, test_hl_linked_list_remove);
946 cu_add_test(suite, test_hl_linked_list_at);
947 cu_add_test(suite, test_hl_linked_list_find);
948 cu_add_test(suite, test_hl_linked_list_sort);
949 cu_add_test(suite, test_hl_linked_list_iterator);
950 cu_add_test(suite, test_hl_linked_list_insert_via_iterator);
952 suite = CU_add_suite_with_setup_and_teardown(
953 "high level pointer linked list", NULL, NULL,
954 test_setup_allocator, test_verify_allocator);
956 cu_add_test(suite, test_hl_ptr_linked_list_create);
957 cu_add_test(suite, test_hl_ptr_linked_list_add);
958 cu_add_test(suite, test_hl_ptr_linked_list_insert);
959 cu_add_test(suite, test_hl_ptr_linked_list_remove);
960 cu_add_test(suite, test_hl_ptr_linked_list_at);
961 cu_add_test(suite, test_hl_ptr_linked_list_find);
962 cu_add_test(suite, test_hl_ptr_linked_list_sort);
963 cu_add_test(suite, test_hl_ptr_linked_list_iterator);
964 cu_add_test(suite, test_hl_ptr_linked_list_insert_via_iterator);
966 CU_basic_set_mode(UCX_CU_BRM);
968 int exitcode;
969 if (CU_basic_run_tests()) {
970 exitcode = CU_get_error();
971 } else {
972 exitcode = CU_get_number_of_failures() == 0 ? 0 : 1;
973 }
974 CU_cleanup_registry();
975 return exitcode;
976 }
