test/test_list.c@31bf97fdbf71
test/test_list.c
Sat, 04 Dec 2021 17:38:23 +0100
- author
- Mike Becker <universe@uap-core.de>
- date
- Sat, 04 Dec 2021 17:38:23 +0100
- changeset 475
- 31bf97fdbf71
- parent 474
- 9c1fccda16bc
- child 476
- 60ff4561dc04
- permissions
- -rw-r--r--
add cx_linked_list_first() + cx_linked_list_prepend()
removes concatenating behavior of cx_linked_list_add()
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(int const *l, int const *r) {
34 int left = *l, right = *r;
35 return left == right ? 0 : (left < right ? -1 : 1);
36 }
38 void test_linked_list_at(void) {
39 struct node {
40 void *next;
41 void *prev;
42 };
43 const ptrdiff_t loc_prev = offsetof(struct node, prev);
44 const ptrdiff_t loc_next = offsetof(struct node, next);
46 struct node a, b, c, d;
47 a.prev = NULL;
48 a.next = &b;
49 b.prev = &a;
50 b.next = &c;
51 c.prev = &b;
52 c.next = &d;
53 d.prev = &c;
54 d.next = NULL;
56 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&a, 0, loc_next, 0), &a)
57 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&a, 0, loc_next, 1), &b)
58 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&a, 0, loc_next, 2), &c)
59 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&a, 0, loc_next, 3), &d)
60 CU_ASSERT_PTR_NULL(cx_linked_list_at(&a, 0, loc_next, 4))
62 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&b, 1, loc_prev, 0), &a)
63 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&b, 1, loc_next, 1), &b)
64 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&b, 1, loc_next, 2), &c)
65 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&b, 1, loc_next, 3), &d)
66 CU_ASSERT_PTR_NULL(cx_linked_list_at(&b, 1, loc_next, 4))
68 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&d, 3, loc_prev, 0), &a)
69 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&d, 3, loc_prev, 1), &b)
70 }
72 void test_linked_list_add(void) {
73 struct node {
74 void *prev;
75 void *next;
76 };
78 struct node nodes[4];
80 // test with begin, end / prev, next
81 memset(nodes, 0, 4 * sizeof(struct node));
82 void *begin = NULL;
83 void *end = NULL;
85 ptrdiff_t loc_prev = offsetof(struct node, prev);
86 ptrdiff_t loc_next = offsetof(struct node, next);
88 cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[0]);
89 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
90 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
91 CU_ASSERT_PTR_NULL(nodes[0].prev)
92 CU_ASSERT_PTR_NULL(nodes[0].next)
94 cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[1]);
95 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
96 CU_ASSERT_PTR_EQUAL(end, &nodes[1])
97 CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1])
98 CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[0])
100 // test with begin only / prev, next
101 memset(nodes, 0, 4 * sizeof(struct node));
102 begin = NULL;
103 end = NULL;
105 cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[0]);
106 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
107 cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[1]);
108 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
109 CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1])
110 CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[0])
112 cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[2]);
113 CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[2])
114 CU_ASSERT_PTR_EQUAL(nodes[2].prev, &nodes[1])
116 // test with end only / prev, next
117 memset(nodes, 0, 4 * sizeof(struct node));
118 begin = NULL;
119 end = NULL;
121 cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[0]);
122 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
123 cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[1]);
124 CU_ASSERT_PTR_EQUAL(end, &nodes[1])
125 CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1])
126 CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[0])
128 cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[2]);
129 CU_ASSERT_PTR_EQUAL(end, &nodes[2])
130 CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[2])
131 CU_ASSERT_PTR_EQUAL(nodes[2].prev, &nodes[1])
133 // test with begin, end / next
134 memset(nodes, 0, 4 * sizeof(struct node));
135 begin = NULL;
136 end = NULL;
138 cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[0]);
139 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
140 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
141 cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[1]);
142 CU_ASSERT_PTR_EQUAL(end, &nodes[1])
143 CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1])
144 CU_ASSERT_PTR_NULL(nodes[1].prev)
145 }
147 void test_linked_list_prepend(void) {
148 struct node {
149 void *prev;
150 void *next;
151 };
153 struct node nodes[4];
155 // test with begin, end / prev, next
156 memset(nodes, 0, 4 * sizeof(struct node));
157 void *begin = NULL;
158 void *end = NULL;
160 ptrdiff_t loc_prev = offsetof(struct node, prev);
161 ptrdiff_t loc_next = offsetof(struct node, next);
163 cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[0]);
164 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
165 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
166 CU_ASSERT_PTR_NULL(nodes[0].prev)
167 CU_ASSERT_PTR_NULL(nodes[0].next)
169 cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[1]);
170 CU_ASSERT_PTR_EQUAL(begin, &nodes[1])
171 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
172 CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[0])
173 CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[1])
175 // test with begin only / prev, next
176 memset(nodes, 0, 4 * sizeof(struct node));
177 begin = NULL;
178 end = NULL;
180 cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[0]);
181 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
182 cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[1]);
183 CU_ASSERT_PTR_EQUAL(begin, &nodes[1])
184 CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[0])
185 CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[1])
187 cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[2]);
188 CU_ASSERT_PTR_EQUAL(begin, &nodes[2])
189 CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[1])
190 CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[2])
192 // test with end only / prev, next
193 memset(nodes, 0, 4 * sizeof(struct node));
194 begin = NULL;
195 end = NULL;
197 cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[0]);
198 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
199 cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[1]);
200 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
201 CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[0])
202 CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[1])
204 cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[2]);
205 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
206 CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[1])
207 CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[2])
209 // test with begin, end / next
210 memset(nodes, 0, 4 * sizeof(struct node));
211 begin = NULL;
212 end = NULL;
214 cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[0]);
215 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
216 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
217 cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[1]);
218 cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[2]);
219 CU_ASSERT_PTR_EQUAL(begin, &nodes[2])
220 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
221 CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[0])
222 CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[1])
223 CU_ASSERT_PTR_NULL(nodes[1].prev)
224 CU_ASSERT_PTR_NULL(nodes[0].prev)
225 }
227 void test_linked_list_first(void) {
228 CU_ASSERT_PTR_NULL(cx_linked_list_first(NULL, 0))
230 struct node {
231 int data;
232 void *prev;
233 };
234 ptrdiff_t loc = offsetof(struct node, prev);
236 struct node first = {1, NULL};
237 struct node second = {2, &first};
238 struct node third = {3, &second};
240 CU_ASSERT_PTR_EQUAL(cx_linked_list_first(&first, loc), &first)
241 CU_ASSERT_PTR_EQUAL(cx_linked_list_first(&second, loc), &first)
242 CU_ASSERT_PTR_EQUAL(cx_linked_list_first(&third, loc), &first)
243 }
245 void test_linked_list_last(void) {
246 CU_ASSERT_PTR_NULL(cx_linked_list_last(NULL, 0))
248 struct node {
249 int data;
250 void *next;
251 };
252 ptrdiff_t loc = offsetof(struct node, next);
254 struct node third = {3, NULL};
255 struct node second = {2, &third};
256 struct node first = {1, &second};
258 CU_ASSERT_PTR_EQUAL(cx_linked_list_last(&first, loc), &third)
259 CU_ASSERT_PTR_EQUAL(cx_linked_list_last(&second, loc), &third)
260 CU_ASSERT_PTR_EQUAL(cx_linked_list_last(&third, loc), &third)
261 }
263 void test_linked_list_prev(void) {
264 struct node {
265 void *next;
266 };
267 ptrdiff_t loc = offsetof(struct node, next);
269 struct node third = {NULL};
270 struct node second = {&third};
271 struct node first = {&second};
273 CU_ASSERT_PTR_NULL(cx_linked_list_prev(&first, loc, &first))
274 CU_ASSERT_PTR_EQUAL(cx_linked_list_prev(&first, loc, &second), &first)
275 CU_ASSERT_PTR_EQUAL(cx_linked_list_prev(&first, loc, &third), &second)
276 }
278 void test_linked_list_remove(void) {
279 struct node {
280 void *next;
281 };
282 struct dnode {
283 void *next;
284 void *prev;
285 };
286 ptrdiff_t loc = offsetof(struct node, next);
287 ptrdiff_t ploc = offsetof(struct dnode, prev);
289 void *begin;
290 void *end;
291 void *result;
293 // single linked list
294 struct node third = {NULL};
295 struct node second = {&third};
296 struct node first = {&second};
297 begin = &first;
299 result = cx_linked_list_remove(&begin, NULL, -1, loc, &second);
300 CU_ASSERT_PTR_EQUAL(result, &first)
301 CU_ASSERT_PTR_EQUAL(begin, &first)
302 CU_ASSERT_PTR_EQUAL(first.next, &third)
303 CU_ASSERT_PTR_NULL(second.next)
304 CU_ASSERT_PTR_NULL(third.next)
306 result = cx_linked_list_remove(&begin, NULL, -1, loc, &first);
307 CU_ASSERT_PTR_EQUAL(result, &third)
308 CU_ASSERT_PTR_EQUAL(begin, &third)
309 CU_ASSERT_PTR_NULL(first.next)
310 CU_ASSERT_PTR_NULL(third.next)
312 result = cx_linked_list_remove(&begin, NULL, -1, loc, &third);
313 CU_ASSERT_PTR_NULL(result)
314 CU_ASSERT_PTR_NULL(begin)
315 CU_ASSERT_PTR_NULL(third.next)
317 // doubly linked list
318 struct dnode dthird = {NULL , NULL};
319 struct dnode dsecond = {&dthird, NULL};
320 struct dnode dfirst = {&dsecond, NULL};
321 dthird.prev = &dsecond;
322 dsecond.prev = &dfirst;
323 begin = &dfirst;
324 end = &dthird;
326 result = cx_linked_list_remove(&begin, &end, ploc, loc, &dsecond);
327 CU_ASSERT_PTR_EQUAL(result, &dfirst)
328 CU_ASSERT_PTR_EQUAL(begin, &dfirst)
329 CU_ASSERT_PTR_EQUAL(end, &dthird)
330 CU_ASSERT_PTR_NULL(dfirst.prev)
331 CU_ASSERT_PTR_EQUAL(dfirst.next, &dthird)
332 CU_ASSERT_PTR_NULL(dsecond.prev)
333 CU_ASSERT_PTR_NULL(dsecond.next)
334 CU_ASSERT_PTR_EQUAL(dthird.prev, &dfirst)
335 CU_ASSERT_PTR_NULL(dthird.next)
337 result = cx_linked_list_remove(&begin, &end, ploc, loc, &dthird);
338 CU_ASSERT_PTR_EQUAL(result, &dfirst)
339 CU_ASSERT_PTR_EQUAL(begin, &dfirst)
340 CU_ASSERT_PTR_EQUAL(end, &dfirst)
341 CU_ASSERT_PTR_NULL(dfirst.prev)
342 CU_ASSERT_PTR_NULL(dfirst.next)
343 CU_ASSERT_PTR_NULL(dthird.prev)
344 CU_ASSERT_PTR_NULL(dthird.next)
346 result = cx_linked_list_remove(&begin, &end, ploc, loc, &dfirst);
347 CU_ASSERT_PTR_NULL(result)
348 CU_ASSERT_PTR_NULL(begin)
349 CU_ASSERT_PTR_NULL(end)
350 CU_ASSERT_PTR_NULL(dfirst.next)
351 CU_ASSERT_PTR_NULL(dfirst.prev)
352 }
354 void test_linked_list_size(void) {
355 struct node {
356 void *next;
357 };
358 ptrdiff_t loc = offsetof(struct node, next);
360 struct node first = {NULL};
361 struct node second = {NULL};
362 struct node third = {NULL};
364 CU_ASSERT_PTR_EQUAL(cx_linked_list_size(NULL, loc), 0)
365 CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&first, loc), 1)
366 first.next = &second;
367 CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&first, loc), 2)
368 second.next = &third;
369 CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&first, loc), 3)
370 CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&second, loc), 2)
371 }
373 void test_linked_list_sort(void) {
374 struct node {
375 void *prev;
376 void *next;
377 int data;
378 };
380 int expected[] = {
381 14, 30, 151, 163, 227, 300, 315, 317, 363, 398, 417, 424, 438, 446, 508, 555, 605, 713, 716, 759, 761, 880,
382 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 1707, 1734, 1771, 1874, 1894,
383 1976, 2079, 2124, 2130, 2135, 2266, 2338, 2358, 2430, 2500, 2540, 2542, 2546, 2711, 2733, 2754, 2764, 2797,
384 2888, 2900, 3020, 3053, 3109, 3244, 3275, 3302, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 3675, 3677,
385 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681,
386 4785, 4791, 4801, 4859, 4903, 4973
387 };
388 int scrambled[] = {
389 759, 716, 880, 761, 2358, 2542, 2500, 2540, 2546, 2711, 2430, 1707, 1874, 1771, 1894, 1734, 1976, 2079,
390 2124, 2130, 2135, 2266, 2338, 2733, 2754, 2764, 2797, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 2888,
391 2900, 3020, 3053, 3109, 3244, 3275, 3302, 438, 446, 508, 555, 605, 713, 14, 30, 151, 163, 227, 300,
392 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 315, 317, 363, 398, 417, 424,
393 3675, 3677, 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4785, 4791, 4801, 4859, 4903, 4973,
394 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681
395 };
397 struct node *nodes = calloc(100, sizeof(struct node));
398 for (int i = 0; i < 100; i++) {
399 nodes[i].prev = i == 0 ? NULL : &nodes[i - 1];
400 nodes[i].next = i == 99 ? NULL : &nodes[i + 1];
401 nodes[i].data = scrambled[i];
402 }
404 struct node *begin = &nodes[0];
405 struct node *end = &nodes[99];
407 cx_linked_list_sort((void **) &begin, (void **) &end,
408 offsetof(struct node, prev),
409 offsetof(struct node, next),
410 offsetof(struct node, data),
411 0, (CxListComparator) cmp_int);
413 CU_ASSERT_PTR_NULL(begin->prev)
414 CU_ASSERT_EQUAL(begin->data, expected[0])
415 struct node *check = begin;
416 struct node *check_last = NULL;
417 for (int i = 0; i < 100; i++) {
418 CU_ASSERT_EQUAL(check->data, expected[i])
419 CU_ASSERT_PTR_EQUAL(check->prev, check_last)
420 if (i < 99) {
421 CU_ASSERT_PTR_NOT_NULL(check->next)
422 }
423 check_last = check;
424 check = check->next;
425 }
426 CU_ASSERT_PTR_NULL(check)
427 CU_ASSERT_EQUAL(end->data, expected[99])
428 }
430 void test_linked_list_reverse(void) {
431 struct node {
432 void *next;
433 };
434 struct dnode {
435 void *next;
436 void *prev;
437 };
438 ptrdiff_t loc = offsetof(struct node, next);
439 ptrdiff_t ploc = offsetof(struct dnode, prev);
441 void *begin;
442 void *end;
444 // single linked list
445 struct node third = {NULL};
446 struct node second = {&third};
447 struct node first = {&second};
448 begin = &first;
450 cx_linked_list_reverse(&begin, NULL, -1, loc);
451 CU_ASSERT_PTR_EQUAL(begin, &third)
452 CU_ASSERT_PTR_EQUAL(third.next, &second)
453 CU_ASSERT_PTR_EQUAL(second.next, &first)
454 CU_ASSERT_PTR_NULL(first.next)
456 // doubly linked list
457 struct dnode dthird = {NULL , NULL};
458 struct dnode dsecond = {&dthird, NULL};
459 struct dnode dfirst = {&dsecond, NULL};
460 dthird.prev = &dsecond;
461 dsecond.prev = &dfirst;
462 begin = &dfirst;
463 end = &dthird;
465 cx_linked_list_reverse(&begin, &end, ploc, loc);
466 CU_ASSERT_PTR_EQUAL(begin, &dthird)
467 CU_ASSERT_PTR_EQUAL(end, &dfirst)
468 CU_ASSERT_PTR_EQUAL(dthird.next, &dsecond)
469 CU_ASSERT_PTR_EQUAL(dsecond.next, &dfirst)
470 CU_ASSERT_PTR_NULL(dfirst.next)
471 CU_ASSERT_PTR_NULL(dthird.prev)
472 CU_ASSERT_PTR_EQUAL(dsecond.prev, &dthird)
473 CU_ASSERT_PTR_EQUAL(dfirst.prev, &dsecond)
474 }
476 void test_hl_linked_list_create(void) {
477 cxTestingAllocatorReset();
479 CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
481 CU_ASSERT_EQUAL(list->size, 0)
482 CU_ASSERT_EQUAL(list->capacity, (size_t) -1)
483 CU_ASSERT_PTR_EQUAL(list->allocator, cxTestingAllocator)
484 CU_ASSERT_EQUAL(list->itemsize, sizeof(int))
485 CU_ASSERT_PTR_EQUAL(list->cmpfunc, cmp_int)
487 cxLinkedListDestroy(list);
488 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
489 }
491 void test_hl_linked_list_add(void) {
492 cxTestingAllocatorReset();
494 int data;
495 CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
497 data = 5;
498 CU_ASSERT_EQUAL(cxListAdd(list, &data), 0)
499 data = 47;
500 CU_ASSERT_EQUAL(cxListAdd(list, &data), 0)
501 data = 13;
502 CU_ASSERT_EQUAL(cxListAdd(list, &data), 0)
504 CU_ASSERT_EQUAL(list->size, 3)
505 CU_ASSERT_TRUE(list->capacity >= list->size)
507 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
508 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
509 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
511 cxLinkedListDestroy(list);
512 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
513 }
515 void test_hl_linked_list_insert(void) {
516 cxTestingAllocatorReset();
518 int data;
519 CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
521 data = 5;
522 CU_ASSERT_NOT_EQUAL(cxListInsert(list, 1, &data), 0)
523 CU_ASSERT_EQUAL(list->size, 0)
524 CU_ASSERT_EQUAL(cxListInsert(list, 0, &data), 0)
525 CU_ASSERT_EQUAL(list->size, 1)
526 data = 47;
527 CU_ASSERT_EQUAL(cxListInsert(list, 0, &data), 0)
528 CU_ASSERT_EQUAL(list->size, 2)
529 data = 13;
530 CU_ASSERT_EQUAL(cxListInsert(list, 1, &data), 0)
531 CU_ASSERT_EQUAL(list->size, 3)
532 data = 42;
533 CU_ASSERT_EQUAL(cxListInsert(list, 3, &data), 0)
535 CU_ASSERT_EQUAL(list->size, 4)
536 CU_ASSERT_TRUE(list->capacity >= list->size)
538 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
539 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
540 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 5)
541 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 3), 42)
543 cxLinkedListDestroy(list);
544 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
545 }
547 void test_hl_linked_list_remove(void) {
548 cxTestingAllocatorReset();
550 int data;
551 CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
553 data = 5;
554 cxListAdd(list, &data);
555 data = 47;
556 cxListAdd(list, &data);
557 data = 42;
558 cxListAdd(list, &data);
559 data = 13;
560 cxListAdd(list, &data);
562 CU_ASSERT_EQUAL(list->size, 4)
563 CU_ASSERT_TRUE(list->capacity >= list->size)
565 CU_ASSERT_NOT_EQUAL(cxListRemove(list, 4), 0)
567 CU_ASSERT_EQUAL(cxListRemove(list, 2), 0)
568 CU_ASSERT_EQUAL(list->size, 3)
569 CU_ASSERT_TRUE(list->capacity >= list->size)
570 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
571 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
572 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
574 CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
575 CU_ASSERT_EQUAL(list->size, 2)
576 CU_ASSERT_TRUE(list->capacity >= list->size)
577 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
578 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
580 CU_ASSERT_EQUAL(cxListRemove(list, 1), 0)
581 CU_ASSERT_EQUAL(list->size, 1)
582 CU_ASSERT_TRUE(list->capacity >= list->size)
583 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
585 CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
586 CU_ASSERT_EQUAL(list->size, 0)
587 CU_ASSERT_TRUE(list->capacity >= list->size)
589 CU_ASSERT_NOT_EQUAL(cxListRemove(list, 0), 0)
591 cxLinkedListDestroy(list);
592 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
593 }
595 void test_hl_linked_list_find(void) {
596 cxTestingAllocatorReset();
598 int data, criteria;
599 CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
601 data = 5;
602 cxListAdd(list, &data);
603 data = 47;
604 cxListAdd(list, &data);
605 data = 13;
606 cxListAdd(list, &data);
608 CU_ASSERT_EQUAL(list->size, 3)
609 CU_ASSERT_TRUE(list->capacity >= list->size)
611 criteria = 5;
612 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 0)
613 criteria = 47;
614 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 1)
615 criteria = 13;
616 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 2)
617 criteria = 9000;
618 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 3)
619 criteria = -5;
620 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 3)
622 cxLinkedListDestroy(list);
623 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
624 }
626 void test_hl_linked_list_sort(void) {
627 int expected[] = {
628 14, 30, 151, 163, 227, 300, 315, 317, 363, 398, 417, 424, 438, 446, 508, 555, 605, 713, 716, 759, 761, 880,
629 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 1707, 1734, 1771, 1874, 1894,
630 1976, 2079, 2124, 2130, 2135, 2266, 2338, 2358, 2430, 2500, 2540, 2542, 2546, 2711, 2733, 2754, 2764, 2797,
631 2888, 2900, 3020, 3053, 3109, 3244, 3275, 3302, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 3675, 3677,
632 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681,
633 4785, 4791, 4801, 4859, 4903, 4973
634 };
635 int scrambled[] = {
636 759, 716, 880, 761, 2358, 2542, 2500, 2540, 2546, 2711, 2430, 1707, 1874, 1771, 1894, 1734, 1976, 2079,
637 2124, 2130, 2135, 2266, 2338, 2733, 2754, 2764, 2797, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 2888,
638 2900, 3020, 3053, 3109, 3244, 3275, 3302, 438, 446, 508, 555, 605, 713, 14, 30, 151, 163, 227, 300,
639 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 315, 317, 363, 398, 417, 424,
640 3675, 3677, 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4785, 4791, 4801, 4859, 4903, 4973,
641 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681
642 };
644 cxTestingAllocatorReset();
646 CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
648 for (int i = 0; i < 100; i++) {
649 cxListAdd(list, &scrambled[i]);
650 }
652 cxListSort(list);
654 for (int i = 0; i < 100; i++) {
655 CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), expected[i])
656 }
658 cxLinkedListDestroy(list);
659 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
660 }
662 void test_hl_ptr_linked_list_create(void) {
663 cxTestingAllocatorReset();
665 CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
667 CU_ASSERT_EQUAL(list->size, 0)
668 CU_ASSERT_EQUAL(list->capacity, (size_t) -1)
669 CU_ASSERT_PTR_EQUAL(list->allocator, cxTestingAllocator)
670 CU_ASSERT_EQUAL(list->itemsize, sizeof(void *))
671 CU_ASSERT_PTR_EQUAL(list->cmpfunc, cmp_int)
673 cxLinkedListDestroy(list);
674 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
675 }
677 void test_hl_ptr_linked_list_add(void) {
678 cxTestingAllocatorReset();
680 CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
682 int a = 5, b = 47, c = 13;
684 CU_ASSERT_EQUAL(cxListAdd(list, &a), 0)
685 CU_ASSERT_EQUAL(cxListAdd(list, &b), 0)
686 CU_ASSERT_EQUAL(cxListAdd(list, &c), 0)
688 CU_ASSERT_EQUAL(list->size, 3)
689 CU_ASSERT_TRUE(list->capacity >= list->size)
691 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
692 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
693 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
695 a = 9;
696 b = 10;
697 c = 11;
699 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 9)
700 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 10)
701 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 11)
703 cxLinkedListDestroy(list);
704 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
705 }
707 void test_hl_ptr_linked_list_insert(void) {
708 cxTestingAllocatorReset();
710 CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
712 int a = 5, b = 47, c = 13, d = 42;
714 CU_ASSERT_NOT_EQUAL(cxListInsert(list, 1, &a), 0)
715 CU_ASSERT_EQUAL(list->size, 0)
716 CU_ASSERT_EQUAL(cxListInsert(list, 0, &a), 0)
717 CU_ASSERT_EQUAL(list->size, 1)
718 CU_ASSERT_EQUAL(cxListInsert(list, 0, &b), 0)
719 CU_ASSERT_EQUAL(list->size, 2)
720 CU_ASSERT_EQUAL(cxListInsert(list, 1, &c), 0)
721 CU_ASSERT_EQUAL(list->size, 3)
722 CU_ASSERT_EQUAL(cxListInsert(list, 3, &d), 0)
724 CU_ASSERT_EQUAL(list->size, 4)
725 CU_ASSERT_TRUE(list->capacity >= list->size)
727 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
728 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
729 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 5)
730 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 3), 42)
732 cxLinkedListDestroy(list);
733 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
734 }
736 void test_hl_ptr_linked_list_remove(void) {
737 cxTestingAllocatorReset();
739 int a = 5, b = 47, c = 42, d = 13;
740 CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
742 cxListAdd(list, &a);
743 cxListAdd(list, &b);
744 cxListAdd(list, &c);
745 cxListAdd(list, &d);
747 CU_ASSERT_EQUAL(list->size, 4)
748 CU_ASSERT_TRUE(list->capacity >= list->size)
750 CU_ASSERT_NOT_EQUAL(cxListRemove(list, 4), 0)
752 CU_ASSERT_EQUAL(cxListRemove(list, 2), 0)
753 CU_ASSERT_EQUAL(list->size, 3)
754 CU_ASSERT_TRUE(list->capacity >= list->size)
755 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
756 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
757 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
759 CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
760 CU_ASSERT_EQUAL(list->size, 2)
761 CU_ASSERT_TRUE(list->capacity >= list->size)
762 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
763 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
765 CU_ASSERT_EQUAL(cxListRemove(list, 1), 0)
766 CU_ASSERT_EQUAL(list->size, 1)
767 CU_ASSERT_TRUE(list->capacity >= list->size)
768 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
770 CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
771 CU_ASSERT_EQUAL(list->size, 0)
772 CU_ASSERT_TRUE(list->capacity >= list->size)
774 CU_ASSERT_NOT_EQUAL(cxListRemove(list, 0), 0)
776 cxLinkedListDestroy(list);
777 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
778 }
780 void test_hl_ptr_linked_list_find(void) {
781 cxTestingAllocatorReset();
783 int a = 5, b = 47, c = 13, criteria;
784 CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
786 cxListAdd(list, &a);
787 cxListAdd(list, &b);
788 cxListAdd(list, &c);
790 CU_ASSERT_EQUAL(list->size, 3)
791 CU_ASSERT_TRUE(list->capacity >= list->size)
793 criteria = 5;
794 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 0)
795 criteria = 47;
796 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 1)
797 criteria = 13;
798 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 2)
799 criteria = 9000;
800 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 3)
801 criteria = -5;
802 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 3)
803 b = -5;
804 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 1)
806 cxLinkedListDestroy(list);
807 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
808 }
810 void test_hl_ptr_linked_list_sort(void) {
811 int expected[] = {
812 14, 30, 151, 163, 227, 300, 315, 317, 363, 398, 417, 424, 438, 446, 508, 555, 605, 713, 716, 759, 761, 880,
813 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 1707, 1734, 1771, 1874, 1894,
814 1976, 2079, 2124, 2130, 2135, 2266, 2338, 2358, 2430, 2500, 2540, 2542, 2546, 2711, 2733, 2754, 2764, 2797,
815 2888, 2900, 3020, 3053, 3109, 3244, 3275, 3302, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 3675, 3677,
816 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681,
817 4785, 4791, 4801, 4859, 4903, 4973
818 };
819 int scrambled[] = {
820 759, 716, 880, 761, 2358, 2542, 2500, 2540, 2546, 2711, 2430, 1707, 1874, 1771, 1894, 1734, 1976, 2079,
821 2124, 2130, 2135, 2266, 2338, 2733, 2754, 2764, 2797, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 2888,
822 2900, 3020, 3053, 3109, 3244, 3275, 3302, 438, 446, 508, 555, 605, 713, 14, 30, 151, 163, 227, 300,
823 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 315, 317, 363, 398, 417, 424,
824 3675, 3677, 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4785, 4791, 4801, 4859, 4903, 4973,
825 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681
826 };
828 cxTestingAllocatorReset();
830 CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
832 for (int i = 0; i < 100; i++) {
833 cxListAdd(list, &scrambled[i]);
834 }
836 cxListSort(list);
838 for (int i = 0; i < 100; i++) {
839 CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), expected[i])
840 }
842 cxLinkedListDestroy(list);
843 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
844 }
846 int main() {
847 CU_pSuite suite = NULL;
849 if (CUE_SUCCESS != CU_initialize_registry()) {
850 return CU_get_error();
851 }
853 suite = CU_add_suite("low level linked list", NULL, NULL);
855 cu_add_test(suite, test_linked_list_at);
856 cu_add_test(suite, test_linked_list_prepend);
857 cu_add_test(suite, test_linked_list_add);
858 cu_add_test(suite, test_linked_list_first);
859 cu_add_test(suite, test_linked_list_last);
860 cu_add_test(suite, test_linked_list_prev);
861 cu_add_test(suite, test_linked_list_remove);
862 cu_add_test(suite, test_linked_list_size);
863 cu_add_test(suite, test_linked_list_sort);
864 cu_add_test(suite, test_linked_list_reverse);
866 suite = CU_add_suite("high level linked list", NULL, NULL);
868 cu_add_test(suite, test_hl_linked_list_create);
869 cu_add_test(suite, test_hl_linked_list_add);
870 cu_add_test(suite, test_hl_linked_list_insert);
871 cu_add_test(suite, test_hl_linked_list_remove);
872 cu_add_test(suite, test_hl_linked_list_find);
873 cu_add_test(suite, test_hl_linked_list_sort);
875 suite = CU_add_suite("high level pointer linked list", NULL, NULL);
877 cu_add_test(suite, test_hl_ptr_linked_list_create);
878 cu_add_test(suite, test_hl_ptr_linked_list_add);
879 cu_add_test(suite, test_hl_ptr_linked_list_insert);
880 cu_add_test(suite, test_hl_ptr_linked_list_remove);
881 cu_add_test(suite, test_hl_ptr_linked_list_find);
882 cu_add_test(suite, test_hl_ptr_linked_list_sort);
884 CU_basic_set_mode(UCX_CU_BRM);
886 int exitcode;
887 if (CU_basic_run_tests()) {
888 exitcode = CU_get_error();
889 } else {
890 exitcode = CU_get_number_of_failures() == 0 ? 0 : 1;
891 }
892 CU_cleanup_registry();
893 return exitcode;
894 }
