test/test_list.c@599770bb6314
test/test_list.c
Mon, 20 Dec 2021 11:58:36 +0100
- author
- Mike Becker <universe@uap-core.de>
- date
- Mon, 20 Dec 2021 11:58:36 +0100
- changeset 478
- 599770bb6314
- parent 476
- 60ff4561dc04
- child 479
- a29bdd703e02
- permissions
- -rw-r--r--
add more nonnull attributes
This also changes the contract for last/first in the sense that these
functions now also require a valid pointer.
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 struct node {
229 int data;
230 void *prev;
231 };
232 ptrdiff_t loc = offsetof(struct node, prev);
234 struct node first = {1, NULL};
235 struct node second = {2, &first};
236 struct node third = {3, &second};
238 CU_ASSERT_PTR_EQUAL(cx_linked_list_first(&first, loc), &first)
239 CU_ASSERT_PTR_EQUAL(cx_linked_list_first(&second, loc), &first)
240 CU_ASSERT_PTR_EQUAL(cx_linked_list_first(&third, loc), &first)
241 }
243 void test_linked_list_last(void) {
244 struct node {
245 int data;
246 void *next;
247 };
248 ptrdiff_t loc = offsetof(struct node, next);
250 struct node third = {3, NULL};
251 struct node second = {2, &third};
252 struct node first = {1, &second};
254 CU_ASSERT_PTR_EQUAL(cx_linked_list_last(&first, loc), &third)
255 CU_ASSERT_PTR_EQUAL(cx_linked_list_last(&second, loc), &third)
256 CU_ASSERT_PTR_EQUAL(cx_linked_list_last(&third, loc), &third)
257 }
259 void test_linked_list_prev(void) {
260 struct node {
261 void *next;
262 };
263 ptrdiff_t loc = offsetof(struct node, next);
265 struct node third = {NULL};
266 struct node second = {&third};
267 struct node first = {&second};
269 CU_ASSERT_PTR_NULL(cx_linked_list_prev(&first, loc, &first))
270 CU_ASSERT_PTR_EQUAL(cx_linked_list_prev(&first, loc, &second), &first)
271 CU_ASSERT_PTR_EQUAL(cx_linked_list_prev(&first, loc, &third), &second)
272 }
274 void test_linked_list_remove(void) {
275 struct node {
276 void *next;
277 };
278 struct dnode {
279 void *next;
280 void *prev;
281 };
282 ptrdiff_t loc = offsetof(struct node, next);
283 ptrdiff_t ploc = offsetof(struct dnode, prev);
285 void *begin;
286 void *end;
288 // single linked list
289 struct node third = {NULL};
290 struct node second = {&third};
291 struct node first = {&second};
292 begin = &first;
294 cx_linked_list_remove(&begin, NULL, -1, loc, &second);
295 CU_ASSERT_PTR_EQUAL(begin, &first)
296 CU_ASSERT_PTR_EQUAL(first.next, &third)
297 CU_ASSERT_PTR_NULL(third.next)
299 cx_linked_list_remove(&begin, NULL, -1, loc, &first);
300 CU_ASSERT_PTR_EQUAL(begin, &third)
301 CU_ASSERT_PTR_NULL(third.next)
303 cx_linked_list_remove(&begin, NULL, -1, loc, &third);
304 CU_ASSERT_PTR_NULL(begin)
306 // doubly linked list
307 struct dnode dthird = {NULL , NULL};
308 struct dnode dsecond = {&dthird, NULL};
309 struct dnode dfirst = {&dsecond, NULL};
310 dthird.prev = &dsecond;
311 dsecond.prev = &dfirst;
312 begin = &dfirst;
313 end = &dthird;
315 cx_linked_list_remove(&begin, &end, ploc, loc, &dsecond);
316 CU_ASSERT_PTR_EQUAL(begin, &dfirst)
317 CU_ASSERT_PTR_EQUAL(end, &dthird)
318 CU_ASSERT_PTR_NULL(dfirst.prev)
319 CU_ASSERT_PTR_EQUAL(dfirst.next, &dthird)
320 CU_ASSERT_PTR_EQUAL(dthird.prev, &dfirst)
321 CU_ASSERT_PTR_NULL(dthird.next)
323 cx_linked_list_remove(&begin, &end, ploc, loc, &dthird);
324 CU_ASSERT_PTR_EQUAL(begin, &dfirst)
325 CU_ASSERT_PTR_EQUAL(end, &dfirst)
326 CU_ASSERT_PTR_NULL(dfirst.prev)
327 CU_ASSERT_PTR_NULL(dfirst.next)
329 cx_linked_list_remove(&begin, &end, ploc, loc, &dfirst);
330 CU_ASSERT_PTR_NULL(begin)
331 CU_ASSERT_PTR_NULL(end)
332 }
334 void test_linked_list_size(void) {
335 struct node {
336 void *next;
337 };
338 ptrdiff_t loc = offsetof(struct node, next);
340 struct node first = {NULL};
341 struct node second = {NULL};
342 struct node third = {NULL};
344 CU_ASSERT_PTR_EQUAL(cx_linked_list_size(NULL, loc), 0)
345 CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&first, loc), 1)
346 first.next = &second;
347 CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&first, loc), 2)
348 second.next = &third;
349 CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&first, loc), 3)
350 CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&second, loc), 2)
351 }
353 void test_linked_list_sort(void) {
354 struct node {
355 void *prev;
356 void *next;
357 int data;
358 };
360 int expected[] = {
361 14, 30, 151, 163, 227, 300, 315, 317, 363, 398, 417, 424, 438, 446, 508, 555, 605, 713, 716, 759, 761, 880,
362 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 1707, 1734, 1771, 1874, 1894,
363 1976, 2079, 2124, 2130, 2135, 2266, 2338, 2358, 2430, 2500, 2540, 2542, 2546, 2711, 2733, 2754, 2764, 2797,
364 2888, 2900, 3020, 3053, 3109, 3244, 3275, 3302, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 3675, 3677,
365 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681,
366 4785, 4791, 4801, 4859, 4903, 4973
367 };
368 int scrambled[] = {
369 759, 716, 880, 761, 2358, 2542, 2500, 2540, 2546, 2711, 2430, 1707, 1874, 1771, 1894, 1734, 1976, 2079,
370 2124, 2130, 2135, 2266, 2338, 2733, 2754, 2764, 2797, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 2888,
371 2900, 3020, 3053, 3109, 3244, 3275, 3302, 438, 446, 508, 555, 605, 713, 14, 30, 151, 163, 227, 300,
372 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 315, 317, 363, 398, 417, 424,
373 3675, 3677, 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4785, 4791, 4801, 4859, 4903, 4973,
374 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681
375 };
377 struct node *nodes = calloc(100, sizeof(struct node));
378 for (int i = 0; i < 100; i++) {
379 nodes[i].prev = i == 0 ? NULL : &nodes[i - 1];
380 nodes[i].next = i == 99 ? NULL : &nodes[i + 1];
381 nodes[i].data = scrambled[i];
382 }
384 struct node *begin = &nodes[0];
385 struct node *end = &nodes[99];
387 cx_linked_list_sort((void **) &begin, (void **) &end,
388 offsetof(struct node, prev),
389 offsetof(struct node, next),
390 offsetof(struct node, data),
391 0, (CxListComparator) cmp_int);
393 CU_ASSERT_PTR_NULL(begin->prev)
394 CU_ASSERT_EQUAL(begin->data, expected[0])
395 struct node *check = begin;
396 struct node *check_last = NULL;
397 for (int i = 0; i < 100; i++) {
398 CU_ASSERT_EQUAL(check->data, expected[i])
399 CU_ASSERT_PTR_EQUAL(check->prev, check_last)
400 if (i < 99) {
401 CU_ASSERT_PTR_NOT_NULL(check->next)
402 }
403 check_last = check;
404 check = check->next;
405 }
406 CU_ASSERT_PTR_NULL(check)
407 CU_ASSERT_EQUAL(end->data, expected[99])
408 }
410 void test_linked_list_reverse(void) {
411 struct node {
412 void *next;
413 };
414 struct dnode {
415 void *next;
416 void *prev;
417 };
418 ptrdiff_t loc = offsetof(struct node, next);
419 ptrdiff_t ploc = offsetof(struct dnode, prev);
421 void *begin;
422 void *end;
424 // single linked list
425 struct node third = {NULL};
426 struct node second = {&third};
427 struct node first = {&second};
428 begin = &first;
430 cx_linked_list_reverse(&begin, NULL, -1, loc);
431 CU_ASSERT_PTR_EQUAL(begin, &third)
432 CU_ASSERT_PTR_EQUAL(third.next, &second)
433 CU_ASSERT_PTR_EQUAL(second.next, &first)
434 CU_ASSERT_PTR_NULL(first.next)
436 // doubly linked list
437 struct dnode dthird = {NULL , NULL};
438 struct dnode dsecond = {&dthird, NULL};
439 struct dnode dfirst = {&dsecond, NULL};
440 dthird.prev = &dsecond;
441 dsecond.prev = &dfirst;
442 begin = &dfirst;
443 end = &dthird;
445 cx_linked_list_reverse(&begin, &end, ploc, loc);
446 CU_ASSERT_PTR_EQUAL(begin, &dthird)
447 CU_ASSERT_PTR_EQUAL(end, &dfirst)
448 CU_ASSERT_PTR_EQUAL(dthird.next, &dsecond)
449 CU_ASSERT_PTR_EQUAL(dsecond.next, &dfirst)
450 CU_ASSERT_PTR_NULL(dfirst.next)
451 CU_ASSERT_PTR_NULL(dthird.prev)
452 CU_ASSERT_PTR_EQUAL(dsecond.prev, &dthird)
453 CU_ASSERT_PTR_EQUAL(dfirst.prev, &dsecond)
454 }
456 void test_hl_linked_list_create(void) {
457 cxTestingAllocatorReset();
459 CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
461 CU_ASSERT_EQUAL(list->size, 0)
462 CU_ASSERT_EQUAL(list->capacity, (size_t) -1)
463 CU_ASSERT_PTR_EQUAL(list->allocator, cxTestingAllocator)
464 CU_ASSERT_EQUAL(list->itemsize, sizeof(int))
465 CU_ASSERT_PTR_EQUAL(list->cmpfunc, cmp_int)
467 cxLinkedListDestroy(list);
468 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
469 }
471 void test_hl_linked_list_add(void) {
472 cxTestingAllocatorReset();
474 int data;
475 CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
477 data = 5;
478 CU_ASSERT_EQUAL(cxListAdd(list, &data), 0)
479 data = 47;
480 CU_ASSERT_EQUAL(cxListAdd(list, &data), 0)
481 data = 13;
482 CU_ASSERT_EQUAL(cxListAdd(list, &data), 0)
484 CU_ASSERT_EQUAL(list->size, 3)
485 CU_ASSERT_TRUE(list->capacity >= list->size)
487 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
488 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
489 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
491 cxLinkedListDestroy(list);
492 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
493 }
495 void test_hl_linked_list_insert(void) {
496 cxTestingAllocatorReset();
498 int data;
499 CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
501 data = 5;
502 CU_ASSERT_NOT_EQUAL(cxListInsert(list, 1, &data), 0)
503 CU_ASSERT_EQUAL(list->size, 0)
504 CU_ASSERT_EQUAL(cxListInsert(list, 0, &data), 0)
505 CU_ASSERT_EQUAL(list->size, 1)
506 data = 47;
507 CU_ASSERT_EQUAL(cxListInsert(list, 0, &data), 0)
508 CU_ASSERT_EQUAL(list->size, 2)
509 data = 13;
510 CU_ASSERT_EQUAL(cxListInsert(list, 1, &data), 0)
511 CU_ASSERT_EQUAL(list->size, 3)
512 data = 42;
513 CU_ASSERT_EQUAL(cxListInsert(list, 3, &data), 0)
515 CU_ASSERT_EQUAL(list->size, 4)
516 CU_ASSERT_TRUE(list->capacity >= list->size)
518 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
519 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
520 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 5)
521 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 3), 42)
523 cxLinkedListDestroy(list);
524 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
525 }
527 void test_hl_linked_list_remove(void) {
528 cxTestingAllocatorReset();
530 int data;
531 CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
533 data = 5;
534 cxListAdd(list, &data);
535 data = 47;
536 cxListAdd(list, &data);
537 data = 42;
538 cxListAdd(list, &data);
539 data = 13;
540 cxListAdd(list, &data);
542 CU_ASSERT_EQUAL(list->size, 4)
543 CU_ASSERT_TRUE(list->capacity >= list->size)
545 CU_ASSERT_NOT_EQUAL(cxListRemove(list, 4), 0)
547 CU_ASSERT_EQUAL(cxListRemove(list, 2), 0)
548 CU_ASSERT_EQUAL(list->size, 3)
549 CU_ASSERT_TRUE(list->capacity >= list->size)
550 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
551 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
552 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
554 CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
555 CU_ASSERT_EQUAL(list->size, 2)
556 CU_ASSERT_TRUE(list->capacity >= list->size)
557 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
558 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
560 CU_ASSERT_EQUAL(cxListRemove(list, 1), 0)
561 CU_ASSERT_EQUAL(list->size, 1)
562 CU_ASSERT_TRUE(list->capacity >= list->size)
563 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
565 CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
566 CU_ASSERT_EQUAL(list->size, 0)
567 CU_ASSERT_TRUE(list->capacity >= list->size)
569 CU_ASSERT_NOT_EQUAL(cxListRemove(list, 0), 0)
571 cxLinkedListDestroy(list);
572 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
573 }
575 void test_hl_linked_list_find(void) {
576 cxTestingAllocatorReset();
578 int data, criteria;
579 CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
581 data = 5;
582 cxListAdd(list, &data);
583 data = 47;
584 cxListAdd(list, &data);
585 data = 13;
586 cxListAdd(list, &data);
588 CU_ASSERT_EQUAL(list->size, 3)
589 CU_ASSERT_TRUE(list->capacity >= list->size)
591 criteria = 5;
592 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 0)
593 criteria = 47;
594 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 1)
595 criteria = 13;
596 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 2)
597 criteria = 9000;
598 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 3)
599 criteria = -5;
600 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 3)
602 cxLinkedListDestroy(list);
603 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
604 }
606 void test_hl_linked_list_sort(void) {
607 int expected[] = {
608 14, 30, 151, 163, 227, 300, 315, 317, 363, 398, 417, 424, 438, 446, 508, 555, 605, 713, 716, 759, 761, 880,
609 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 1707, 1734, 1771, 1874, 1894,
610 1976, 2079, 2124, 2130, 2135, 2266, 2338, 2358, 2430, 2500, 2540, 2542, 2546, 2711, 2733, 2754, 2764, 2797,
611 2888, 2900, 3020, 3053, 3109, 3244, 3275, 3302, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 3675, 3677,
612 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681,
613 4785, 4791, 4801, 4859, 4903, 4973
614 };
615 int scrambled[] = {
616 759, 716, 880, 761, 2358, 2542, 2500, 2540, 2546, 2711, 2430, 1707, 1874, 1771, 1894, 1734, 1976, 2079,
617 2124, 2130, 2135, 2266, 2338, 2733, 2754, 2764, 2797, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 2888,
618 2900, 3020, 3053, 3109, 3244, 3275, 3302, 438, 446, 508, 555, 605, 713, 14, 30, 151, 163, 227, 300,
619 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 315, 317, 363, 398, 417, 424,
620 3675, 3677, 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4785, 4791, 4801, 4859, 4903, 4973,
621 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681
622 };
624 cxTestingAllocatorReset();
626 CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
628 for (int i = 0; i < 100; i++) {
629 cxListAdd(list, &scrambled[i]);
630 }
632 cxListSort(list);
634 for (int i = 0; i < 100; i++) {
635 CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), expected[i])
636 }
638 cxLinkedListDestroy(list);
639 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
640 }
642 void test_hl_ptr_linked_list_create(void) {
643 cxTestingAllocatorReset();
645 CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
647 CU_ASSERT_EQUAL(list->size, 0)
648 CU_ASSERT_EQUAL(list->capacity, (size_t) -1)
649 CU_ASSERT_PTR_EQUAL(list->allocator, cxTestingAllocator)
650 CU_ASSERT_EQUAL(list->itemsize, sizeof(void *))
651 CU_ASSERT_PTR_EQUAL(list->cmpfunc, cmp_int)
653 cxLinkedListDestroy(list);
654 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
655 }
657 void test_hl_ptr_linked_list_add(void) {
658 cxTestingAllocatorReset();
660 CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
662 int a = 5, b = 47, c = 13;
664 CU_ASSERT_EQUAL(cxListAdd(list, &a), 0)
665 CU_ASSERT_EQUAL(cxListAdd(list, &b), 0)
666 CU_ASSERT_EQUAL(cxListAdd(list, &c), 0)
668 CU_ASSERT_EQUAL(list->size, 3)
669 CU_ASSERT_TRUE(list->capacity >= list->size)
671 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
672 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
673 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
675 a = 9;
676 b = 10;
677 c = 11;
679 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 9)
680 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 10)
681 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 11)
683 cxLinkedListDestroy(list);
684 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
685 }
687 void test_hl_ptr_linked_list_insert(void) {
688 cxTestingAllocatorReset();
690 CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
692 int a = 5, b = 47, c = 13, d = 42;
694 CU_ASSERT_NOT_EQUAL(cxListInsert(list, 1, &a), 0)
695 CU_ASSERT_EQUAL(list->size, 0)
696 CU_ASSERT_EQUAL(cxListInsert(list, 0, &a), 0)
697 CU_ASSERT_EQUAL(list->size, 1)
698 CU_ASSERT_EQUAL(cxListInsert(list, 0, &b), 0)
699 CU_ASSERT_EQUAL(list->size, 2)
700 CU_ASSERT_EQUAL(cxListInsert(list, 1, &c), 0)
701 CU_ASSERT_EQUAL(list->size, 3)
702 CU_ASSERT_EQUAL(cxListInsert(list, 3, &d), 0)
704 CU_ASSERT_EQUAL(list->size, 4)
705 CU_ASSERT_TRUE(list->capacity >= list->size)
707 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
708 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
709 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 5)
710 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 3), 42)
712 cxLinkedListDestroy(list);
713 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
714 }
716 void test_hl_ptr_linked_list_remove(void) {
717 cxTestingAllocatorReset();
719 int a = 5, b = 47, c = 42, d = 13;
720 CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
722 cxListAdd(list, &a);
723 cxListAdd(list, &b);
724 cxListAdd(list, &c);
725 cxListAdd(list, &d);
727 CU_ASSERT_EQUAL(list->size, 4)
728 CU_ASSERT_TRUE(list->capacity >= list->size)
730 CU_ASSERT_NOT_EQUAL(cxListRemove(list, 4), 0)
732 CU_ASSERT_EQUAL(cxListRemove(list, 2), 0)
733 CU_ASSERT_EQUAL(list->size, 3)
734 CU_ASSERT_TRUE(list->capacity >= list->size)
735 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
736 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
737 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
739 CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
740 CU_ASSERT_EQUAL(list->size, 2)
741 CU_ASSERT_TRUE(list->capacity >= list->size)
742 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
743 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
745 CU_ASSERT_EQUAL(cxListRemove(list, 1), 0)
746 CU_ASSERT_EQUAL(list->size, 1)
747 CU_ASSERT_TRUE(list->capacity >= list->size)
748 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
750 CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
751 CU_ASSERT_EQUAL(list->size, 0)
752 CU_ASSERT_TRUE(list->capacity >= list->size)
754 CU_ASSERT_NOT_EQUAL(cxListRemove(list, 0), 0)
756 cxLinkedListDestroy(list);
757 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
758 }
760 void test_hl_ptr_linked_list_find(void) {
761 cxTestingAllocatorReset();
763 int a = 5, b = 47, c = 13, criteria;
764 CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
766 cxListAdd(list, &a);
767 cxListAdd(list, &b);
768 cxListAdd(list, &c);
770 CU_ASSERT_EQUAL(list->size, 3)
771 CU_ASSERT_TRUE(list->capacity >= list->size)
773 criteria = 5;
774 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 0)
775 criteria = 47;
776 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 1)
777 criteria = 13;
778 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 2)
779 criteria = 9000;
780 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 3)
781 criteria = -5;
782 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 3)
783 b = -5;
784 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 1)
786 cxLinkedListDestroy(list);
787 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
788 }
790 void test_hl_ptr_linked_list_sort(void) {
791 int expected[] = {
792 14, 30, 151, 163, 227, 300, 315, 317, 363, 398, 417, 424, 438, 446, 508, 555, 605, 713, 716, 759, 761, 880,
793 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 1707, 1734, 1771, 1874, 1894,
794 1976, 2079, 2124, 2130, 2135, 2266, 2338, 2358, 2430, 2500, 2540, 2542, 2546, 2711, 2733, 2754, 2764, 2797,
795 2888, 2900, 3020, 3053, 3109, 3244, 3275, 3302, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 3675, 3677,
796 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681,
797 4785, 4791, 4801, 4859, 4903, 4973
798 };
799 int scrambled[] = {
800 759, 716, 880, 761, 2358, 2542, 2500, 2540, 2546, 2711, 2430, 1707, 1874, 1771, 1894, 1734, 1976, 2079,
801 2124, 2130, 2135, 2266, 2338, 2733, 2754, 2764, 2797, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 2888,
802 2900, 3020, 3053, 3109, 3244, 3275, 3302, 438, 446, 508, 555, 605, 713, 14, 30, 151, 163, 227, 300,
803 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 315, 317, 363, 398, 417, 424,
804 3675, 3677, 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4785, 4791, 4801, 4859, 4903, 4973,
805 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681
806 };
808 cxTestingAllocatorReset();
810 CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
812 for (int i = 0; i < 100; i++) {
813 cxListAdd(list, &scrambled[i]);
814 }
816 cxListSort(list);
818 for (int i = 0; i < 100; i++) {
819 CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), expected[i])
820 }
822 cxLinkedListDestroy(list);
823 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
824 }
826 int main() {
827 CU_pSuite suite = NULL;
829 if (CUE_SUCCESS != CU_initialize_registry()) {
830 return CU_get_error();
831 }
833 suite = CU_add_suite("low level linked list", NULL, NULL);
835 cu_add_test(suite, test_linked_list_at);
836 cu_add_test(suite, test_linked_list_prepend);
837 cu_add_test(suite, test_linked_list_add);
838 cu_add_test(suite, test_linked_list_first);
839 cu_add_test(suite, test_linked_list_last);
840 cu_add_test(suite, test_linked_list_prev);
841 cu_add_test(suite, test_linked_list_remove);
842 cu_add_test(suite, test_linked_list_size);
843 cu_add_test(suite, test_linked_list_sort);
844 cu_add_test(suite, test_linked_list_reverse);
846 suite = CU_add_suite("high level linked list", NULL, NULL);
848 cu_add_test(suite, test_hl_linked_list_create);
849 cu_add_test(suite, test_hl_linked_list_add);
850 cu_add_test(suite, test_hl_linked_list_insert);
851 cu_add_test(suite, test_hl_linked_list_remove);
852 cu_add_test(suite, test_hl_linked_list_find);
853 cu_add_test(suite, test_hl_linked_list_sort);
855 suite = CU_add_suite("high level pointer linked list", NULL, NULL);
857 cu_add_test(suite, test_hl_ptr_linked_list_create);
858 cu_add_test(suite, test_hl_ptr_linked_list_add);
859 cu_add_test(suite, test_hl_ptr_linked_list_insert);
860 cu_add_test(suite, test_hl_ptr_linked_list_remove);
861 cu_add_test(suite, test_hl_ptr_linked_list_find);
862 cu_add_test(suite, test_hl_ptr_linked_list_sort);
864 CU_basic_set_mode(UCX_CU_BRM);
866 int exitcode;
867 if (CU_basic_run_tests()) {
868 exitcode = CU_get_error();
869 } else {
870 exitcode = CU_get_number_of_failures() == 0 ? 0 : 1;
871 }
872 CU_cleanup_registry();
873 return exitcode;
874 }
