Tue, 15 Feb 2022 19:41:48 +0100
add new destructor API and apply it to CxList
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 "test_config.h"
31 #include "util_allocator.h"
33 int cmp_int_impl(
34 int const *l,
35 int const *r
36 ) {
37 int left = *l, right = *r;
38 return left == right ? 0 : (left < right ? -1 : 1);
39 }
41 #define cmp_int ((CxListComparator) cmp_int_impl)
43 struct node {
44 struct node *next;
45 struct node *prev;
46 int data;
47 };
49 #define nd(name) name = {0}
51 const ptrdiff_t loc_prev = offsetof(struct node, prev);
52 const ptrdiff_t loc_next = offsetof(struct node, next);
53 const ptrdiff_t loc_data = offsetof(struct node, data);
55 struct node *create_test_data(
56 size_t n,
57 int const data[]
58 ) {
59 if (n == 0) return NULL;
60 struct node *begin = calloc(1, sizeof(struct node));
61 struct node *prev = begin;
62 if (data) begin->data = data[0];
63 for (size_t i = 1; i < n; i++) {
64 struct node *node = calloc(1, sizeof(struct node));
65 if (data) node->data = data[i];
66 cx_linked_list_link(prev, node, loc_prev, loc_next);
67 prev = node;
68 }
69 return begin;
70 }
72 void destroy_test_data(struct node *begin) {
73 struct node *node = begin;
74 while (node) {
75 struct node *next = node->next;
76 free(node);
77 node = next;
78 }
79 }
81 void test_linked_list_link_unlink(void) {
83 struct node nd(a), nd(b), nd(c);
85 cx_linked_list_link(&a, &b, loc_prev, loc_next);
86 CU_ASSERT_PTR_NULL(a.prev)
87 CU_ASSERT_PTR_EQUAL(a.next, &b)
88 CU_ASSERT_PTR_EQUAL(b.prev, &a)
89 CU_ASSERT_PTR_NULL(b.next)
91 cx_linked_list_unlink(&a, &b, loc_prev, loc_next);
92 CU_ASSERT_PTR_NULL(a.prev)
93 CU_ASSERT_PTR_NULL(a.next)
94 CU_ASSERT_PTR_NULL(b.prev)
95 CU_ASSERT_PTR_NULL(b.next)
97 cx_linked_list_link(&b, &c, loc_prev, loc_next);
98 cx_linked_list_link(&a, &b, loc_prev, loc_next);
99 cx_linked_list_unlink(&b, &c, loc_prev, loc_next);
100 CU_ASSERT_PTR_NULL(a.prev)
101 CU_ASSERT_PTR_EQUAL(a.next, &b)
102 CU_ASSERT_PTR_EQUAL(b.prev, &a)
103 CU_ASSERT_PTR_NULL(b.next)
104 CU_ASSERT_PTR_NULL(c.prev)
105 CU_ASSERT_PTR_NULL(c.next)
106 }
108 void test_linked_list_at(void) {
109 struct node nd(a), nd(b), nd(c), nd(d);
110 cx_linked_list_link(&a, &b, loc_prev, loc_next);
111 cx_linked_list_link(&b, &c, loc_prev, loc_next);
112 cx_linked_list_link(&c, &d, loc_prev, loc_next);
114 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&a, 0, loc_next, 0), &a)
115 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&a, 0, loc_next, 1), &b)
116 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&a, 0, loc_next, 2), &c)
117 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&a, 0, loc_next, 3), &d)
118 CU_ASSERT_PTR_NULL(cx_linked_list_at(&a, 0, loc_next, 4))
120 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&b, 1, loc_prev, 0), &a)
121 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&b, 1, loc_next, 1), &b)
122 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&b, 1, loc_next, 2), &c)
123 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&b, 1, loc_next, 3), &d)
124 CU_ASSERT_PTR_NULL(cx_linked_list_at(&b, 1, loc_next, 4))
126 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&d, 3, loc_prev, 0), &a)
127 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&d, 3, loc_prev, 1), &b)
128 }
130 void test_linked_list_find(void) {
131 int data[] = {2, 4, 6, 8};
132 void *list = create_test_data(4, data);
133 int s;
135 s = 2;
136 CU_ASSERT_EQUAL(cx_linked_list_find(list, loc_next, loc_data,
137 false, cmp_int, &s), 0)
138 s = 4;
139 CU_ASSERT_EQUAL(cx_linked_list_find(list, loc_next, loc_data,
140 false, cmp_int, &s), 1)
141 s = 6;
142 CU_ASSERT_EQUAL(cx_linked_list_find(list, loc_next, loc_data,
143 false, cmp_int, &s), 2)
144 s = 8;
145 CU_ASSERT_EQUAL(cx_linked_list_find(list, loc_next, loc_data,
146 false, cmp_int, &s), 3)
147 s = 10;
148 CU_ASSERT_EQUAL(cx_linked_list_find(list, loc_next, loc_data,
149 false, cmp_int, &s), 4)
150 s = -2;
151 CU_ASSERT_EQUAL(cx_linked_list_find(list, loc_next, loc_data,
152 false, cmp_int, &s), 4)
153 }
155 void test_linked_list_compare(void) {
156 int a[] = {2, 4, 6, 8};
157 int b[] = {2, 4, 6};
158 int c[] = {2, 4, 6, 9};
160 void *la = create_test_data(4, a);
161 void *lb = create_test_data(3, b);
162 void *lc = create_test_data(4, c);
164 CU_ASSERT_TRUE(0 < cx_linked_list_compare(la, lb, loc_next, loc_data,
165 false, cmp_int)
166 )
167 CU_ASSERT_TRUE(0 > cx_linked_list_compare(lb, la, loc_next, loc_data,
168 false, cmp_int)
169 )
170 CU_ASSERT_TRUE(0 < cx_linked_list_compare(lc, la, loc_next, loc_data,
171 false, cmp_int)
172 )
173 CU_ASSERT_TRUE(0 > cx_linked_list_compare(la, lc, loc_next, loc_data,
174 false, cmp_int)
175 )
176 CU_ASSERT_TRUE(0 == cx_linked_list_compare(la, la, loc_next, loc_data,
177 false, cmp_int)
178 )
180 destroy_test_data(la);
181 destroy_test_data(lb);
182 destroy_test_data(lc);
183 }
185 void test_linked_list_add(void) {
186 struct node nodes[4];
187 void *begin, *end;
189 // test with begin, end / prev, next
190 memset(nodes, 0, 4 * sizeof(struct node));
191 begin = end = NULL;
193 cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[0]);
194 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
195 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
196 CU_ASSERT_PTR_NULL(nodes[0].prev)
197 CU_ASSERT_PTR_NULL(nodes[0].next)
199 cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[1]);
200 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
201 CU_ASSERT_PTR_EQUAL(end, &nodes[1])
202 CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1])
203 CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[0])
205 // test with begin only / prev, next
206 memset(nodes, 0, 4 * sizeof(struct node));
207 begin = end = NULL;
209 cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[0]);
210 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
211 cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[1]);
212 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
213 CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1])
214 CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[0])
216 cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[2]);
217 CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[2])
218 CU_ASSERT_PTR_EQUAL(nodes[2].prev, &nodes[1])
220 // test with end only / prev, next
221 memset(nodes, 0, 4 * sizeof(struct node));
222 begin = end = NULL;
224 cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[0]);
225 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
226 cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[1]);
227 CU_ASSERT_PTR_EQUAL(end, &nodes[1])
228 CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1])
229 CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[0])
231 cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[2]);
232 CU_ASSERT_PTR_EQUAL(end, &nodes[2])
233 CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[2])
234 CU_ASSERT_PTR_EQUAL(nodes[2].prev, &nodes[1])
236 // test with begin, end / next
237 memset(nodes, 0, 4 * sizeof(struct node));
238 begin = end = NULL;
240 cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[0]);
241 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
242 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
243 cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[1]);
244 CU_ASSERT_PTR_EQUAL(end, &nodes[1])
245 CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1])
246 CU_ASSERT_PTR_NULL(nodes[1].prev)
247 }
249 void test_linked_list_prepend(void) {
250 struct node nodes[4];
251 void *begin, *end;
253 // test with begin, end / prev, next
254 memset(nodes, 0, 4 * sizeof(struct node));
255 begin = end = NULL;
257 cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[0]);
258 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
259 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
260 CU_ASSERT_PTR_NULL(nodes[0].prev)
261 CU_ASSERT_PTR_NULL(nodes[0].next)
263 cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[1]);
264 CU_ASSERT_PTR_EQUAL(begin, &nodes[1])
265 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
266 CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[0])
267 CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[1])
269 // test with begin only / prev, next
270 memset(nodes, 0, 4 * sizeof(struct node));
271 begin = end = NULL;
273 cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[0]);
274 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
275 cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[1]);
276 CU_ASSERT_PTR_EQUAL(begin, &nodes[1])
277 CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[0])
278 CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[1])
280 cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[2]);
281 CU_ASSERT_PTR_EQUAL(begin, &nodes[2])
282 CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[1])
283 CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[2])
285 // test with end only / prev, next
286 memset(nodes, 0, 4 * sizeof(struct node));
287 begin = end = NULL;
289 cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[0]);
290 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
291 cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[1]);
292 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
293 CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[0])
294 CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[1])
296 cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[2]);
297 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
298 CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[1])
299 CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[2])
301 // test with begin, end / next
302 memset(nodes, 0, 4 * sizeof(struct node));
303 begin = end = NULL;
305 cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[0]);
306 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
307 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
308 cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[1]);
309 cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[2]);
310 CU_ASSERT_PTR_EQUAL(begin, &nodes[2])
311 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
312 CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[0])
313 CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[1])
314 CU_ASSERT_PTR_NULL(nodes[1].prev)
315 CU_ASSERT_PTR_NULL(nodes[0].prev)
316 }
318 void test_linked_list_insert(void) {
319 struct node nodes[4];
320 void *begin, *end;
322 // insert mid list
323 memset(nodes, 0, 4 * sizeof(struct node));
324 begin = &nodes[0];
325 end = &nodes[2];
327 cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
328 cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
330 cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3]);
331 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
332 CU_ASSERT_PTR_EQUAL(end, &nodes[2])
333 CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[3])
334 CU_ASSERT_PTR_EQUAL(nodes[2].prev, &nodes[3])
335 CU_ASSERT_PTR_EQUAL(nodes[3].prev, &nodes[1])
336 CU_ASSERT_PTR_EQUAL(nodes[3].next, &nodes[2])
338 // insert end
339 memset(nodes, 0, 4 * sizeof(struct node));
340 begin = &nodes[0];
341 end = &nodes[2];
343 cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
344 cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
346 cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3]);
347 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
348 CU_ASSERT_PTR_EQUAL(end, &nodes[3])
349 CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[3])
350 CU_ASSERT_PTR_EQUAL(nodes[3].prev, &nodes[2])
351 CU_ASSERT_PTR_NULL(nodes[3].next)
353 // insert begin
354 memset(nodes, 0, 4 * sizeof(struct node));
355 begin = &nodes[0];
356 end = &nodes[2];
358 cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
359 cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
361 cx_linked_list_insert(&begin, &end, loc_prev, loc_next, NULL, &nodes[3]);
362 CU_ASSERT_PTR_EQUAL(begin, &nodes[3])
363 CU_ASSERT_PTR_EQUAL(end, &nodes[2])
364 CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[3])
365 CU_ASSERT_PTR_NULL(nodes[3].prev)
366 CU_ASSERT_PTR_EQUAL(nodes[3].next, &nodes[0])
367 }
369 void test_linked_list_insert_chain(void) {
370 struct node nodes[5];
371 void *begin, *end;
373 // insert mid list
374 memset(nodes, 0, 5 * sizeof(struct node));
375 begin = &nodes[0];
376 end = &nodes[2];
378 cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
379 cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
380 cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next);
382 cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3], NULL);
383 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
384 CU_ASSERT_PTR_EQUAL(end, &nodes[2])
385 CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[3])
386 CU_ASSERT_PTR_EQUAL(nodes[2].prev, &nodes[4])
387 CU_ASSERT_PTR_EQUAL(nodes[3].prev, &nodes[1])
388 CU_ASSERT_PTR_EQUAL(nodes[4].next, &nodes[2])
390 // insert end
391 memset(nodes, 0, 5 * sizeof(struct node));
392 begin = &nodes[0];
393 end = &nodes[2];
395 cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
396 cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
397 cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next);
399 cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3], NULL);
400 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
401 CU_ASSERT_PTR_EQUAL(end, &nodes[4])
402 CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[3])
403 CU_ASSERT_PTR_EQUAL(nodes[3].prev, &nodes[2])
404 CU_ASSERT_PTR_NULL(nodes[4].next)
406 // insert begin
407 memset(nodes, 0, 5 * sizeof(struct node));
408 begin = &nodes[0];
409 end = &nodes[2];
411 cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
412 cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
413 cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next);
415 cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, NULL, &nodes[3], NULL);
416 CU_ASSERT_PTR_EQUAL(begin, &nodes[3])
417 CU_ASSERT_PTR_EQUAL(end, &nodes[2])
418 CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[4])
419 CU_ASSERT_PTR_NULL(nodes[3].prev)
420 CU_ASSERT_PTR_EQUAL(nodes[4].next, &nodes[0])
421 }
423 void test_linked_list_first(void) {
424 struct node *begin = create_test_data(3, NULL);
425 CU_ASSERT_PTR_EQUAL(cx_linked_list_first(begin, loc_prev), begin)
426 CU_ASSERT_PTR_EQUAL(cx_linked_list_first(begin->next, loc_prev), begin)
427 CU_ASSERT_PTR_EQUAL(cx_linked_list_first(begin->next->next, loc_prev), begin)
428 destroy_test_data(begin);
429 }
431 void test_linked_list_last(void) {
432 struct node *begin = create_test_data(3, NULL);
433 struct node *end = begin->next->next;
434 CU_ASSERT_PTR_EQUAL(cx_linked_list_last(begin, loc_next), end)
435 CU_ASSERT_PTR_EQUAL(cx_linked_list_last(begin->next, loc_next), end)
436 CU_ASSERT_PTR_EQUAL(cx_linked_list_last(begin->next->next, loc_next), end)
437 destroy_test_data(begin);
438 }
440 void test_linked_list_prev(void) {
441 struct node *begin = create_test_data(3, NULL);
442 CU_ASSERT_PTR_NULL(cx_linked_list_prev(begin, loc_next, begin))
443 CU_ASSERT_PTR_EQUAL(cx_linked_list_prev(begin, loc_next, begin->next), begin)
444 CU_ASSERT_PTR_EQUAL(cx_linked_list_prev(begin, loc_next, begin->next->next), begin->next)
445 destroy_test_data(begin);
446 }
448 void test_linked_list_remove(void) {
449 void *begin, *end;
451 int data[] = {2, 4, 6};
452 begin = create_test_data(3, data);
453 struct node *first = begin;
454 struct node *second = first->next;
455 struct node *third = second->next;
456 end = third;
458 cx_linked_list_remove(&begin, &end, loc_prev, loc_next, second);
459 CU_ASSERT_PTR_EQUAL(begin, first)
460 CU_ASSERT_PTR_EQUAL(end, third)
461 CU_ASSERT_PTR_NULL(first->prev)
462 CU_ASSERT_PTR_EQUAL(first->next, third)
463 CU_ASSERT_PTR_EQUAL(third->prev, first)
464 CU_ASSERT_PTR_NULL(third->next)
466 cx_linked_list_remove(&begin, &end, loc_prev, loc_next, third);
467 CU_ASSERT_PTR_EQUAL(begin, first)
468 CU_ASSERT_PTR_EQUAL(end, first)
469 CU_ASSERT_PTR_NULL(first->prev)
470 CU_ASSERT_PTR_NULL(first->next)
472 cx_linked_list_remove(&begin, &end, loc_prev, loc_next, first);
473 CU_ASSERT_PTR_NULL(begin)
474 CU_ASSERT_PTR_NULL(end)
476 free(first);
477 free(second);
478 free(third);
479 }
481 void test_linked_list_size(void) {
482 struct node *list;
484 CU_ASSERT_PTR_EQUAL(cx_linked_list_size(NULL, loc_next), 0)
486 list = create_test_data(5, NULL);
487 CU_ASSERT_EQUAL(cx_linked_list_size(list, loc_next), 5)
488 destroy_test_data(list);
490 list = create_test_data(13, NULL);
491 CU_ASSERT_EQUAL(cx_linked_list_size(list, loc_next), 13)
492 destroy_test_data(list);
493 }
495 void test_linked_list_sort(void) {
496 int expected[] = {
497 14, 30, 151, 163, 227, 300, 315, 317, 363, 398, 417, 424, 438, 446, 508, 555, 605, 713, 716, 759, 761, 880,
498 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 1707, 1734, 1771, 1874, 1894,
499 1976, 2079, 2124, 2130, 2135, 2266, 2338, 2358, 2430, 2500, 2540, 2542, 2546, 2711, 2733, 2754, 2764, 2797,
500 2888, 2900, 3020, 3053, 3109, 3244, 3275, 3302, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 3675, 3677,
501 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681,
502 4785, 4791, 4801, 4859, 4903, 4973
503 };
504 int scrambled[] = {
505 759, 716, 880, 761, 2358, 2542, 2500, 2540, 2546, 2711, 2430, 1707, 1874, 1771, 1894, 1734, 1976, 2079,
506 2124, 2130, 2135, 2266, 2338, 2733, 2754, 2764, 2797, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 2888,
507 2900, 3020, 3053, 3109, 3244, 3275, 3302, 438, 446, 508, 555, 605, 713, 14, 30, 151, 163, 227, 300,
508 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 315, 317, 363, 398, 417, 424,
509 3675, 3677, 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4785, 4791, 4801, 4859, 4903, 4973,
510 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681
511 };
513 void *begin = create_test_data(100, scrambled);
514 void *end = cx_linked_list_last(begin, loc_next);
516 cx_linked_list_sort(&begin, &end, loc_prev, loc_next, loc_data,
517 false, cmp_int);
519 struct node *check = begin;
520 struct node *check_last = NULL;
521 CU_ASSERT_PTR_NULL(check->prev)
522 CU_ASSERT_EQUAL(check->data, expected[0])
523 for (int i = 0; i < 100; i++) {
524 CU_ASSERT_EQUAL(check->data, expected[i])
525 CU_ASSERT_PTR_EQUAL(check->prev, check_last)
526 if (i < 99) {
527 CU_ASSERT_PTR_NOT_NULL(check->next)
528 }
529 check_last = check;
530 check = check->next;
531 }
532 CU_ASSERT_PTR_NULL(check)
533 CU_ASSERT_PTR_EQUAL(end, check_last)
535 destroy_test_data(begin);
536 }
538 void test_linked_list_reverse(void) {
539 void *begin, *end;
541 int data[] = {2, 4, 6, 8};
542 int reversed[] = {8, 6, 4, 2};
544 void *list = create_test_data(4, data);
545 void *expected = create_test_data(4, reversed);
547 begin = list;
548 end = cx_linked_list_last(list, loc_next);
550 cx_linked_list_reverse(&begin, &end, loc_prev, loc_next);
551 CU_ASSERT_PTR_EQUAL(end, list)
552 CU_ASSERT_PTR_EQUAL(begin, cx_linked_list_first(end, loc_prev))
553 CU_ASSERT_TRUE(0 == cx_linked_list_compare(begin, expected, loc_next, loc_data,
554 0, cmp_int))
556 destroy_test_data(begin);
557 destroy_test_data(expected);
558 }
560 void test_hl_linked_list_create(void) {
561 cxTestingAllocatorReset();
563 CxList *list = cxLinkedListCreate(cxTestingAllocator, cmp_int, sizeof(int));
565 CU_ASSERT_EQUAL(list->size, 0)
566 CU_ASSERT_EQUAL(list->capacity, (size_t) -1)
567 CU_ASSERT_PTR_EQUAL(list->allocator, cxTestingAllocator)
568 CU_ASSERT_EQUAL(list->itemsize, sizeof(int))
569 CU_ASSERT_PTR_EQUAL(list->cmpfunc, cmp_int)
571 cxListDestroy(list);
572 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
573 }
575 void test_hl_ptr_linked_list_create(void) {
576 cxTestingAllocatorReset();
578 CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int);
580 CU_ASSERT_EQUAL(list->size, 0)
581 CU_ASSERT_EQUAL(list->capacity, (size_t) -1)
582 CU_ASSERT_PTR_EQUAL(list->allocator, cxTestingAllocator)
583 CU_ASSERT_EQUAL(list->itemsize, sizeof(void *))
584 CU_ASSERT_PTR_EQUAL(list->cmpfunc, cmp_int)
586 cxListDestroy(list);
587 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
588 }
590 void test_hl_linked_list_from_array(void) {
591 cxTestingAllocatorReset();
593 int data[] = {2, 4, 5, 7, 10, 15};
595 CxList *expected = cxLinkedListCreate(cxTestingAllocator, cmp_int, sizeof(int));
596 for (int i = 0; i < 5; i++) cxListAdd(expected, &data[i]);
598 CxList *list = cxLinkedListFromArray(cxTestingAllocator, cmp_int, sizeof(int), 5, data);
600 CU_ASSERT_TRUE(0 == cxListCompare(list, expected))
602 cxListDestroy(list);
603 cxListDestroy(expected);
604 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
605 }
607 void test_hl_linked_list_add(void) {
608 cxTestingAllocatorReset();
610 int data;
611 CxList *list = cxLinkedListCreate(cxTestingAllocator, cmp_int, sizeof(int));
613 data = 5;
614 CU_ASSERT_EQUAL(cxListAdd(list, &data), 0)
615 data = 47;
616 CU_ASSERT_EQUAL(cxListAdd(list, &data), 0)
617 data = 13;
618 CU_ASSERT_EQUAL(cxListAdd(list, &data), 0)
620 CU_ASSERT_EQUAL(list->size, 3)
621 CU_ASSERT_TRUE(list->capacity >= list->size)
623 int exp[] = {5, 47, 13};
624 CxList *expected = cxLinkedListFromArray(cxTestingAllocator, cmp_int, sizeof(int), 3, exp);
625 CU_ASSERT_TRUE(0 == cxListCompare(list, expected))
627 cxListDestroy(list);
628 cxListDestroy(expected);
629 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
630 }
632 void test_hl_ptr_linked_list_add(void) {
633 cxTestingAllocatorReset();
635 CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int);
637 int a = 5, b = 47, c = 13;
639 CU_ASSERT_EQUAL(cxListAdd(list, &a), 0)
640 CU_ASSERT_EQUAL(cxListAdd(list, &b), 0)
641 CU_ASSERT_EQUAL(cxListAdd(list, &c), 0)
643 CU_ASSERT_EQUAL(list->size, 3)
644 CU_ASSERT_TRUE(list->capacity >= list->size)
646 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
647 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
648 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
650 a = 9;
651 b = 10;
652 c = 11;
654 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 9)
655 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 10)
656 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 11)
658 cxListDestroy(list);
659 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
660 }
662 void test_hl_linked_list_insert(void) {
663 cxTestingAllocatorReset();
665 int data;
666 CxList *list = cxLinkedListCreate(cxTestingAllocator, cmp_int, sizeof(int));
668 data = 5;
669 CU_ASSERT_NOT_EQUAL(cxListInsert(list, 1, &data), 0)
670 CU_ASSERT_EQUAL(list->size, 0)
671 CU_ASSERT_EQUAL(cxListInsert(list, 0, &data), 0)
672 CU_ASSERT_EQUAL(list->size, 1)
673 data = 47;
674 CU_ASSERT_EQUAL(cxListInsert(list, 0, &data), 0)
675 CU_ASSERT_EQUAL(list->size, 2)
676 data = 13;
677 CU_ASSERT_EQUAL(cxListInsert(list, 1, &data), 0)
678 CU_ASSERT_EQUAL(list->size, 3)
679 data = 42;
680 CU_ASSERT_EQUAL(cxListInsert(list, 3, &data), 0)
682 CU_ASSERT_EQUAL(list->size, 4)
683 CU_ASSERT_TRUE(list->capacity >= list->size)
685 int exp[] = {47, 13, 5, 42};
686 CxList *expected = cxLinkedListFromArray(cxTestingAllocator, cmp_int, sizeof(int), 4, exp);
687 CU_ASSERT_TRUE(0 == cxListCompare(list, expected))
689 cxListDestroy(list);
690 cxListDestroy(expected);
691 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
692 }
694 void test_hl_ptr_linked_list_insert(void) {
695 cxTestingAllocatorReset();
697 CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int);
699 int a = 5, b = 47, c = 13, d = 42;
701 CU_ASSERT_NOT_EQUAL(cxListInsert(list, 1, &a), 0)
702 CU_ASSERT_EQUAL(list->size, 0)
703 CU_ASSERT_EQUAL(cxListInsert(list, 0, &a), 0)
704 CU_ASSERT_EQUAL(list->size, 1)
705 CU_ASSERT_EQUAL(cxListInsert(list, 0, &b), 0)
706 CU_ASSERT_EQUAL(list->size, 2)
707 CU_ASSERT_EQUAL(cxListInsert(list, 1, &c), 0)
708 CU_ASSERT_EQUAL(list->size, 3)
709 CU_ASSERT_EQUAL(cxListInsert(list, 3, &d), 0)
711 CU_ASSERT_EQUAL(list->size, 4)
712 CU_ASSERT_TRUE(list->capacity >= list->size)
714 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
715 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
716 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 5)
717 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 3), 42)
719 cxListDestroy(list);
720 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
721 }
723 void test_hl_linked_list_remove(void) {
724 cxTestingAllocatorReset();
726 int data[] = {5, 47, 42, 13};
727 CxList *list = cxLinkedListFromArray(cxTestingAllocator, cmp_int,
728 sizeof(int), 4, data);
730 CU_ASSERT_EQUAL(list->size, 4)
731 CU_ASSERT_TRUE(list->capacity >= list->size)
733 CU_ASSERT_NOT_EQUAL(cxListRemove(list, 4), 0)
735 CU_ASSERT_EQUAL(cxListRemove(list, 2), 0)
736 CU_ASSERT_EQUAL(list->size, 3)
737 CU_ASSERT_TRUE(list->capacity >= list->size)
738 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
739 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
740 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
742 CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
743 CU_ASSERT_EQUAL(list->size, 2)
744 CU_ASSERT_TRUE(list->capacity >= list->size)
745 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
746 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
748 CU_ASSERT_EQUAL(cxListRemove(list, 1), 0)
749 CU_ASSERT_EQUAL(list->size, 1)
750 CU_ASSERT_TRUE(list->capacity >= list->size)
751 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
753 CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
754 CU_ASSERT_EQUAL(list->size, 0)
755 CU_ASSERT_TRUE(list->capacity >= list->size)
757 CU_ASSERT_NOT_EQUAL(cxListRemove(list, 0), 0)
759 cxListDestroy(list);
760 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
761 }
763 void test_hl_ptr_linked_list_remove(void) {
764 cxTestingAllocatorReset();
766 int a = 5, b = 47, c = 42, d = 13;
767 CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int);
769 cxListAdd(list, &a);
770 cxListAdd(list, &b);
771 cxListAdd(list, &c);
772 cxListAdd(list, &d);
774 CU_ASSERT_EQUAL(list->size, 4)
775 CU_ASSERT_TRUE(list->capacity >= list->size)
777 CU_ASSERT_NOT_EQUAL(cxListRemove(list, 4), 0)
779 CU_ASSERT_EQUAL(cxListRemove(list, 2), 0)
780 CU_ASSERT_EQUAL(list->size, 3)
781 CU_ASSERT_TRUE(list->capacity >= list->size)
782 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
783 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
784 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
786 CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
787 CU_ASSERT_EQUAL(list->size, 2)
788 CU_ASSERT_TRUE(list->capacity >= list->size)
789 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
790 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
792 CU_ASSERT_EQUAL(cxListRemove(list, 1), 0)
793 CU_ASSERT_EQUAL(list->size, 1)
794 CU_ASSERT_TRUE(list->capacity >= list->size)
795 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
797 CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
798 CU_ASSERT_EQUAL(list->size, 0)
799 CU_ASSERT_TRUE(list->capacity >= list->size)
801 CU_ASSERT_NOT_EQUAL(cxListRemove(list, 0), 0)
803 cxListDestroy(list);
804 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
805 }
807 void test_hl_linked_list_at(void) {
808 cxTestingAllocatorReset();
810 int data[] = {5, 47, 13};
811 CxList *list = cxLinkedListFromArray(cxTestingAllocator, cmp_int,
812 sizeof(int), 3, data);
814 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
815 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
816 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
817 CU_ASSERT_PTR_NULL(cxListAt(list, 3))
819 cxListDestroy(list);
820 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
821 }
823 void test_hl_ptr_linked_list_at(void) {
824 cxTestingAllocatorReset();
826 CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int);
828 int a = 5, b = 47, c = 13;
829 cxListAdd(list, &a);
830 cxListAdd(list, &b);
831 cxListAdd(list, &c);
833 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
834 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
835 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
836 CU_ASSERT_PTR_NULL(cxListAt(list, 3))
838 cxListDestroy(list);
839 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
840 }
842 void test_hl_linked_list_find(void) {
843 cxTestingAllocatorReset();
845 int data[] = {5, 47, 13};
846 CxList *list = cxLinkedListFromArray(cxTestingAllocator, cmp_int,
847 sizeof(int), 3, data);
848 CU_ASSERT_EQUAL(list->size, 3)
849 CU_ASSERT_TRUE(list->capacity >= list->size)
851 int criteria;
853 criteria = 5;
854 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 0)
855 criteria = 47;
856 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 1)
857 criteria = 13;
858 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 2)
859 criteria = 9000;
860 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 3)
861 criteria = -5;
862 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 3)
864 cxListDestroy(list);
865 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
866 }
868 void test_hl_ptr_linked_list_find(void) {
869 cxTestingAllocatorReset();
871 int a = 5, b = 47, c = 13, criteria;
872 CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int);
874 cxListAdd(list, &a);
875 cxListAdd(list, &b);
876 cxListAdd(list, &c);
878 CU_ASSERT_EQUAL(list->size, 3)
879 CU_ASSERT_TRUE(list->capacity >= list->size)
881 criteria = 5;
882 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 0)
883 criteria = 47;
884 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 1)
885 criteria = 13;
886 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 2)
887 criteria = 9000;
888 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 3)
889 criteria = -5;
890 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 3)
891 b = -5;
892 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 1)
894 cxListDestroy(list);
895 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
896 }
898 void test_hl_linked_list_sort(void) {
899 int expected[] = {
900 14, 30, 151, 163, 227, 300, 315, 317, 363, 398, 417, 424, 438, 446, 508, 555, 605, 713, 716, 759, 761, 880,
901 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 1707, 1734, 1771, 1874, 1894,
902 1976, 2079, 2124, 2130, 2135, 2266, 2338, 2358, 2430, 2500, 2540, 2542, 2546, 2711, 2733, 2754, 2764, 2797,
903 2888, 2900, 3020, 3053, 3109, 3244, 3275, 3302, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 3675, 3677,
904 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681,
905 4785, 4791, 4801, 4859, 4903, 4973
906 };
907 int scrambled[] = {
908 759, 716, 880, 761, 2358, 2542, 2500, 2540, 2546, 2711, 2430, 1707, 1874, 1771, 1894, 1734, 1976, 2079,
909 2124, 2130, 2135, 2266, 2338, 2733, 2754, 2764, 2797, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 2888,
910 2900, 3020, 3053, 3109, 3244, 3275, 3302, 438, 446, 508, 555, 605, 713, 14, 30, 151, 163, 227, 300,
911 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 315, 317, 363, 398, 417, 424,
912 3675, 3677, 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4785, 4791, 4801, 4859, 4903, 4973,
913 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681
914 };
916 cxTestingAllocatorReset();
918 CxList *list = cxLinkedListFromArray(cxTestingAllocator, cmp_int, sizeof(int), 100, scrambled);
919 CxList *exp = cxLinkedListFromArray(cxTestingAllocator, cmp_int, sizeof(int), 100, expected);
921 cxListSort(list);
922 CU_ASSERT_TRUE(0 == cxListCompare(list, exp))
924 cxListDestroy(list);
925 cxListDestroy(exp);
926 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
927 }
929 void test_hl_ptr_linked_list_sort(void) {
930 int expected[] = {
931 14, 30, 151, 163, 227, 300, 315, 317, 363, 398, 417, 424, 438, 446, 508, 555, 605, 713, 716, 759, 761, 880,
932 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 1707, 1734, 1771, 1874, 1894,
933 1976, 2079, 2124, 2130, 2135, 2266, 2338, 2358, 2430, 2500, 2540, 2542, 2546, 2711, 2733, 2754, 2764, 2797,
934 2888, 2900, 3020, 3053, 3109, 3244, 3275, 3302, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 3675, 3677,
935 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681,
936 4785, 4791, 4801, 4859, 4903, 4973
937 };
938 int scrambled[] = {
939 759, 716, 880, 761, 2358, 2542, 2500, 2540, 2546, 2711, 2430, 1707, 1874, 1771, 1894, 1734, 1976, 2079,
940 2124, 2130, 2135, 2266, 2338, 2733, 2754, 2764, 2797, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 2888,
941 2900, 3020, 3053, 3109, 3244, 3275, 3302, 438, 446, 508, 555, 605, 713, 14, 30, 151, 163, 227, 300,
942 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 315, 317, 363, 398, 417, 424,
943 3675, 3677, 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4785, 4791, 4801, 4859, 4903, 4973,
944 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681
945 };
947 cxTestingAllocatorReset();
949 CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int);
951 for (int i = 0; i < 100; i++) {
952 cxListAdd(list, &scrambled[i]);
953 }
955 cxListSort(list);
957 for (int i = 0; i < 100; i++) {
958 CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), expected[i])
959 }
961 cxListDestroy(list);
962 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
963 }
965 void test_hl_linked_list_iterator_impl(CxList *list) {
966 int i = 0;
967 CxIterator iter = cxListBegin(list);
968 cx_foreach(int*, x, iter) {
969 CU_ASSERT_EQUAL(iter.index, (size_t) (i + 1) / 2)
970 CU_ASSERT_EQUAL(*x, i)
971 if (*x % 2 == 1) iter.remove = true;
972 i++;
973 }
974 CU_ASSERT_EQUAL(i, 10)
975 CU_ASSERT_EQUAL_FATAL(list->size, 5)
976 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 0)
977 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 2)
978 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 4)
979 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 3), 6)
980 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 4), 8)
981 cxListDestroy(list);
982 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
983 }
985 void test_hl_linked_list_iterator(void) {
986 cxTestingAllocatorReset();
987 CxList *list = cxLinkedListCreate(cxTestingAllocator, cmp_int, sizeof(int));
988 for (int i = 0; i < 10; i++) {
989 cxListAdd(list, &i);
990 }
991 test_hl_linked_list_iterator_impl(list);
992 }
994 void test_hl_ptr_linked_list_iterator(void) {
995 cxTestingAllocatorReset();
996 CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int);
997 int data[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
998 for (int i = 0; i < 10; i++) {
999 cxListAdd(list, &data[i]);
1000 }
1001 test_hl_linked_list_iterator_impl(list);
1002 }
1004 void test_hl_linked_list_insert_via_iterator(void) {
1005 cxTestingAllocatorReset();
1006 CxList *list = cxLinkedListCreate(cxTestingAllocator, cmp_int, sizeof(int));
1007 for (int i = 0; i < 5; i++) {
1008 cxListAdd(list, &i);
1009 }
1010 CxIterator iter = cxListIterator(list, 2);
1011 CU_ASSERT_EQUAL(iter.index, 2)
1012 CU_ASSERT_EQUAL(*(int *) cxIteratorCurrent(&iter), 2)
1014 int data = 10;
1015 cxListInsertAfter(&iter, &data);
1016 CU_ASSERT_EQUAL(iter.index, 2)
1017 CU_ASSERT_EQUAL(*(int *) cxIteratorCurrent(&iter), 2)
1018 data = 20;
1019 cxListInsertBefore(&iter, &data);
1020 CU_ASSERT_EQUAL(iter.index, 3)
1021 CU_ASSERT_EQUAL(*(int *) cxIteratorCurrent(&iter), 2)
1023 data = 30;
1024 iter = cxListBegin(list);
1025 cxListInsertBefore(&iter, &data);
1026 CU_ASSERT_EQUAL(iter.index, 1)
1027 CU_ASSERT_EQUAL(*(int *) cxIteratorCurrent(&iter), 0)
1028 data = 40;
1029 iter = cxListIterator(list, list->size);
1030 cxListInsertBefore(&iter, &data);
1031 CU_ASSERT_EQUAL(iter.index, 9)
1032 CU_ASSERT_FALSE(cxIteratorValid(&iter))
1033 data = 50;
1034 iter = cxListIterator(list, list->size);
1035 cxListInsertAfter(&iter, &data);
1036 CU_ASSERT_EQUAL(iter.index, 10)
1037 CU_ASSERT_FALSE(cxIteratorValid(&iter))
1039 int expdata[] = {30, 0, 1, 20, 2, 10, 3, 4, 40, 50};
1040 CxList *expected = cxLinkedListFromArray(cxTestingAllocator,
1041 cmp_int, sizeof(int), 10, expdata);
1043 CU_ASSERT_EQUAL(0, cxListCompare(list, expected))
1044 cxListDestroy(list);
1045 cxListDestroy(expected);
1046 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
1047 }
1049 void test_hl_ptr_linked_list_insert_via_iterator(void) {
1050 int testdata[] = {0, 1, 2, 3, 4, 10, 20, 30, 40, 50};
1051 cxTestingAllocatorReset();
1052 CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int);
1053 int i;
1054 for (i = 0; i < 5; i++) {
1055 cxListAdd(list, &testdata[i]);
1056 }
1057 CxIterator iter = cxListIterator(list, 2);
1058 CU_ASSERT_EQUAL(iter.index, 2)
1059 CU_ASSERT_EQUAL(*(int *) cxIteratorCurrent(&iter), 2)
1061 cxListInsertAfter(&iter, &testdata[i++]);
1062 CU_ASSERT_EQUAL(iter.index, 2)
1063 CU_ASSERT_EQUAL(*(int *) cxIteratorCurrent(&iter), 2)
1064 cxListInsertBefore(&iter, &testdata[i++]);
1065 CU_ASSERT_EQUAL(iter.index, 3)
1066 CU_ASSERT_EQUAL(*(int *) cxIteratorCurrent(&iter), 2)
1068 iter = cxListBegin(list);
1069 cxListInsertBefore(&iter, &testdata[i++]);
1070 CU_ASSERT_EQUAL(iter.index, 1)
1071 CU_ASSERT_EQUAL(*(int *) cxIteratorCurrent(&iter), 0)
1072 iter = cxListIterator(list, list->size);
1073 cxListInsertBefore(&iter, &testdata[i++]);
1074 CU_ASSERT_EQUAL(iter.index, 9)
1075 CU_ASSERT_FALSE(cxIteratorValid(&iter))
1076 iter = cxListIterator(list, list->size);
1077 cxListInsertAfter(&iter, &testdata[i++]);
1078 CU_ASSERT_EQUAL(iter.index, 10)
1079 CU_ASSERT_FALSE(cxIteratorValid(&iter))
1081 int expdata[] = {30, 0, 1, 20, 2, 10, 3, 4, 40, 50};
1082 for (i = 0; i < 10; i++) {
1083 CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), expdata[i])
1084 }
1086 cxListDestroy(list);
1087 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
1088 }
1090 int main() {
1091 CU_pSuite suite = NULL;
1093 if (CUE_SUCCESS != CU_initialize_registry()) {
1094 return CU_get_error();
1095 }
1097 suite = CU_add_suite("low level linked list", NULL, NULL);
1099 cu_add_test(suite, test_linked_list_link_unlink);
1100 cu_add_test(suite, test_linked_list_at);
1101 cu_add_test(suite, test_linked_list_find);
1102 cu_add_test(suite, test_linked_list_compare);
1103 cu_add_test(suite, test_linked_list_prepend);
1104 cu_add_test(suite, test_linked_list_add);
1105 cu_add_test(suite, test_linked_list_insert);
1106 cu_add_test(suite, test_linked_list_insert_chain);
1107 cu_add_test(suite, test_linked_list_first);
1108 cu_add_test(suite, test_linked_list_last);
1109 cu_add_test(suite, test_linked_list_prev);
1110 cu_add_test(suite, test_linked_list_remove);
1111 cu_add_test(suite, test_linked_list_size);
1112 cu_add_test(suite, test_linked_list_sort);
1113 cu_add_test(suite, test_linked_list_reverse);
1115 suite = CU_add_suite("high level linked list", NULL, NULL);
1117 cu_add_test(suite, test_hl_linked_list_create);
1118 cu_add_test(suite, test_hl_linked_list_from_array);
1119 cu_add_test(suite, test_hl_linked_list_add);
1120 cu_add_test(suite, test_hl_linked_list_insert);
1121 cu_add_test(suite, test_hl_linked_list_remove);
1122 cu_add_test(suite, test_hl_linked_list_at);
1123 cu_add_test(suite, test_hl_linked_list_find);
1124 cu_add_test(suite, test_hl_linked_list_sort);
1125 cu_add_test(suite, test_hl_linked_list_iterator);
1126 cu_add_test(suite, test_hl_linked_list_insert_via_iterator);
1128 suite = CU_add_suite("high level pointer linked list", NULL, NULL);
1130 cu_add_test(suite, test_hl_ptr_linked_list_create);
1131 cu_add_test(suite, test_hl_ptr_linked_list_add);
1132 cu_add_test(suite, test_hl_ptr_linked_list_insert);
1133 cu_add_test(suite, test_hl_ptr_linked_list_remove);
1134 cu_add_test(suite, test_hl_ptr_linked_list_at);
1135 cu_add_test(suite, test_hl_ptr_linked_list_find);
1136 cu_add_test(suite, test_hl_ptr_linked_list_sort);
1137 cu_add_test(suite, test_hl_ptr_linked_list_iterator);
1138 cu_add_test(suite, test_hl_ptr_linked_list_insert_via_iterator);
1140 CU_basic_set_mode(UCX_CU_BRM);
1142 int exitcode;
1143 if (CU_basic_run_tests()) {
1144 exitcode = CU_get_error();
1145 } else {
1146 exitcode = CU_get_number_of_failures() == 0 ? 0 : 1;
1147 }
1148 CU_cleanup_registry();
1149 return exitcode;
1150 }