test/test_list.c@60ff4561dc04
test/test_list.c
Mon, 20 Dec 2021 11:17:06 +0100
- author
- Mike Becker <universe@uap-core.de>
- date
- Mon, 20 Dec 2021 11:17:06 +0100
- changeset 476
- 60ff4561dc04
- parent 475
- 31bf97fdbf71
- child 478
- 599770bb6314
- permissions
- -rw-r--r--
change contract of cx_linked_list_remove()
also use cx_linked_list_remove() in high level API
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;
292 // single linked list
293 struct node third = {NULL};
294 struct node second = {&third};
295 struct node first = {&second};
296 begin = &first;
298 cx_linked_list_remove(&begin, NULL, -1, loc, &second);
299 CU_ASSERT_PTR_EQUAL(begin, &first)
300 CU_ASSERT_PTR_EQUAL(first.next, &third)
301 CU_ASSERT_PTR_NULL(third.next)
303 cx_linked_list_remove(&begin, NULL, -1, loc, &first);
304 CU_ASSERT_PTR_EQUAL(begin, &third)
305 CU_ASSERT_PTR_NULL(third.next)
307 cx_linked_list_remove(&begin, NULL, -1, loc, &third);
308 CU_ASSERT_PTR_NULL(begin)
310 // doubly linked list
311 struct dnode dthird = {NULL , NULL};
312 struct dnode dsecond = {&dthird, NULL};
313 struct dnode dfirst = {&dsecond, NULL};
314 dthird.prev = &dsecond;
315 dsecond.prev = &dfirst;
316 begin = &dfirst;
317 end = &dthird;
319 cx_linked_list_remove(&begin, &end, ploc, loc, &dsecond);
320 CU_ASSERT_PTR_EQUAL(begin, &dfirst)
321 CU_ASSERT_PTR_EQUAL(end, &dthird)
322 CU_ASSERT_PTR_NULL(dfirst.prev)
323 CU_ASSERT_PTR_EQUAL(dfirst.next, &dthird)
324 CU_ASSERT_PTR_EQUAL(dthird.prev, &dfirst)
325 CU_ASSERT_PTR_NULL(dthird.next)
327 cx_linked_list_remove(&begin, &end, ploc, loc, &dthird);
328 CU_ASSERT_PTR_EQUAL(begin, &dfirst)
329 CU_ASSERT_PTR_EQUAL(end, &dfirst)
330 CU_ASSERT_PTR_NULL(dfirst.prev)
331 CU_ASSERT_PTR_NULL(dfirst.next)
333 cx_linked_list_remove(&begin, &end, ploc, loc, &dfirst);
334 CU_ASSERT_PTR_NULL(begin)
335 CU_ASSERT_PTR_NULL(end)
336 }
338 void test_linked_list_size(void) {
339 struct node {
340 void *next;
341 };
342 ptrdiff_t loc = offsetof(struct node, next);
344 struct node first = {NULL};
345 struct node second = {NULL};
346 struct node third = {NULL};
348 CU_ASSERT_PTR_EQUAL(cx_linked_list_size(NULL, loc), 0)
349 CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&first, loc), 1)
350 first.next = &second;
351 CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&first, loc), 2)
352 second.next = &third;
353 CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&first, loc), 3)
354 CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&second, loc), 2)
355 }
357 void test_linked_list_sort(void) {
358 struct node {
359 void *prev;
360 void *next;
361 int data;
362 };
364 int expected[] = {
365 14, 30, 151, 163, 227, 300, 315, 317, 363, 398, 417, 424, 438, 446, 508, 555, 605, 713, 716, 759, 761, 880,
366 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 1707, 1734, 1771, 1874, 1894,
367 1976, 2079, 2124, 2130, 2135, 2266, 2338, 2358, 2430, 2500, 2540, 2542, 2546, 2711, 2733, 2754, 2764, 2797,
368 2888, 2900, 3020, 3053, 3109, 3244, 3275, 3302, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 3675, 3677,
369 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681,
370 4785, 4791, 4801, 4859, 4903, 4973
371 };
372 int scrambled[] = {
373 759, 716, 880, 761, 2358, 2542, 2500, 2540, 2546, 2711, 2430, 1707, 1874, 1771, 1894, 1734, 1976, 2079,
374 2124, 2130, 2135, 2266, 2338, 2733, 2754, 2764, 2797, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 2888,
375 2900, 3020, 3053, 3109, 3244, 3275, 3302, 438, 446, 508, 555, 605, 713, 14, 30, 151, 163, 227, 300,
376 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 315, 317, 363, 398, 417, 424,
377 3675, 3677, 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4785, 4791, 4801, 4859, 4903, 4973,
378 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681
379 };
381 struct node *nodes = calloc(100, sizeof(struct node));
382 for (int i = 0; i < 100; i++) {
383 nodes[i].prev = i == 0 ? NULL : &nodes[i - 1];
384 nodes[i].next = i == 99 ? NULL : &nodes[i + 1];
385 nodes[i].data = scrambled[i];
386 }
388 struct node *begin = &nodes[0];
389 struct node *end = &nodes[99];
391 cx_linked_list_sort((void **) &begin, (void **) &end,
392 offsetof(struct node, prev),
393 offsetof(struct node, next),
394 offsetof(struct node, data),
395 0, (CxListComparator) cmp_int);
397 CU_ASSERT_PTR_NULL(begin->prev)
398 CU_ASSERT_EQUAL(begin->data, expected[0])
399 struct node *check = begin;
400 struct node *check_last = NULL;
401 for (int i = 0; i < 100; i++) {
402 CU_ASSERT_EQUAL(check->data, expected[i])
403 CU_ASSERT_PTR_EQUAL(check->prev, check_last)
404 if (i < 99) {
405 CU_ASSERT_PTR_NOT_NULL(check->next)
406 }
407 check_last = check;
408 check = check->next;
409 }
410 CU_ASSERT_PTR_NULL(check)
411 CU_ASSERT_EQUAL(end->data, expected[99])
412 }
414 void test_linked_list_reverse(void) {
415 struct node {
416 void *next;
417 };
418 struct dnode {
419 void *next;
420 void *prev;
421 };
422 ptrdiff_t loc = offsetof(struct node, next);
423 ptrdiff_t ploc = offsetof(struct dnode, prev);
425 void *begin;
426 void *end;
428 // single linked list
429 struct node third = {NULL};
430 struct node second = {&third};
431 struct node first = {&second};
432 begin = &first;
434 cx_linked_list_reverse(&begin, NULL, -1, loc);
435 CU_ASSERT_PTR_EQUAL(begin, &third)
436 CU_ASSERT_PTR_EQUAL(third.next, &second)
437 CU_ASSERT_PTR_EQUAL(second.next, &first)
438 CU_ASSERT_PTR_NULL(first.next)
440 // doubly linked list
441 struct dnode dthird = {NULL , NULL};
442 struct dnode dsecond = {&dthird, NULL};
443 struct dnode dfirst = {&dsecond, NULL};
444 dthird.prev = &dsecond;
445 dsecond.prev = &dfirst;
446 begin = &dfirst;
447 end = &dthird;
449 cx_linked_list_reverse(&begin, &end, ploc, loc);
450 CU_ASSERT_PTR_EQUAL(begin, &dthird)
451 CU_ASSERT_PTR_EQUAL(end, &dfirst)
452 CU_ASSERT_PTR_EQUAL(dthird.next, &dsecond)
453 CU_ASSERT_PTR_EQUAL(dsecond.next, &dfirst)
454 CU_ASSERT_PTR_NULL(dfirst.next)
455 CU_ASSERT_PTR_NULL(dthird.prev)
456 CU_ASSERT_PTR_EQUAL(dsecond.prev, &dthird)
457 CU_ASSERT_PTR_EQUAL(dfirst.prev, &dsecond)
458 }
460 void test_hl_linked_list_create(void) {
461 cxTestingAllocatorReset();
463 CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
465 CU_ASSERT_EQUAL(list->size, 0)
466 CU_ASSERT_EQUAL(list->capacity, (size_t) -1)
467 CU_ASSERT_PTR_EQUAL(list->allocator, cxTestingAllocator)
468 CU_ASSERT_EQUAL(list->itemsize, sizeof(int))
469 CU_ASSERT_PTR_EQUAL(list->cmpfunc, cmp_int)
471 cxLinkedListDestroy(list);
472 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
473 }
475 void test_hl_linked_list_add(void) {
476 cxTestingAllocatorReset();
478 int data;
479 CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
481 data = 5;
482 CU_ASSERT_EQUAL(cxListAdd(list, &data), 0)
483 data = 47;
484 CU_ASSERT_EQUAL(cxListAdd(list, &data), 0)
485 data = 13;
486 CU_ASSERT_EQUAL(cxListAdd(list, &data), 0)
488 CU_ASSERT_EQUAL(list->size, 3)
489 CU_ASSERT_TRUE(list->capacity >= list->size)
491 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
492 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
493 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
495 cxLinkedListDestroy(list);
496 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
497 }
499 void test_hl_linked_list_insert(void) {
500 cxTestingAllocatorReset();
502 int data;
503 CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
505 data = 5;
506 CU_ASSERT_NOT_EQUAL(cxListInsert(list, 1, &data), 0)
507 CU_ASSERT_EQUAL(list->size, 0)
508 CU_ASSERT_EQUAL(cxListInsert(list, 0, &data), 0)
509 CU_ASSERT_EQUAL(list->size, 1)
510 data = 47;
511 CU_ASSERT_EQUAL(cxListInsert(list, 0, &data), 0)
512 CU_ASSERT_EQUAL(list->size, 2)
513 data = 13;
514 CU_ASSERT_EQUAL(cxListInsert(list, 1, &data), 0)
515 CU_ASSERT_EQUAL(list->size, 3)
516 data = 42;
517 CU_ASSERT_EQUAL(cxListInsert(list, 3, &data), 0)
519 CU_ASSERT_EQUAL(list->size, 4)
520 CU_ASSERT_TRUE(list->capacity >= list->size)
522 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
523 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
524 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 5)
525 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 3), 42)
527 cxLinkedListDestroy(list);
528 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
529 }
531 void test_hl_linked_list_remove(void) {
532 cxTestingAllocatorReset();
534 int data;
535 CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
537 data = 5;
538 cxListAdd(list, &data);
539 data = 47;
540 cxListAdd(list, &data);
541 data = 42;
542 cxListAdd(list, &data);
543 data = 13;
544 cxListAdd(list, &data);
546 CU_ASSERT_EQUAL(list->size, 4)
547 CU_ASSERT_TRUE(list->capacity >= list->size)
549 CU_ASSERT_NOT_EQUAL(cxListRemove(list, 4), 0)
551 CU_ASSERT_EQUAL(cxListRemove(list, 2), 0)
552 CU_ASSERT_EQUAL(list->size, 3)
553 CU_ASSERT_TRUE(list->capacity >= list->size)
554 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
555 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
556 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
558 CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
559 CU_ASSERT_EQUAL(list->size, 2)
560 CU_ASSERT_TRUE(list->capacity >= list->size)
561 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
562 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
564 CU_ASSERT_EQUAL(cxListRemove(list, 1), 0)
565 CU_ASSERT_EQUAL(list->size, 1)
566 CU_ASSERT_TRUE(list->capacity >= list->size)
567 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
569 CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
570 CU_ASSERT_EQUAL(list->size, 0)
571 CU_ASSERT_TRUE(list->capacity >= list->size)
573 CU_ASSERT_NOT_EQUAL(cxListRemove(list, 0), 0)
575 cxLinkedListDestroy(list);
576 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
577 }
579 void test_hl_linked_list_find(void) {
580 cxTestingAllocatorReset();
582 int data, criteria;
583 CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
585 data = 5;
586 cxListAdd(list, &data);
587 data = 47;
588 cxListAdd(list, &data);
589 data = 13;
590 cxListAdd(list, &data);
592 CU_ASSERT_EQUAL(list->size, 3)
593 CU_ASSERT_TRUE(list->capacity >= list->size)
595 criteria = 5;
596 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 0)
597 criteria = 47;
598 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 1)
599 criteria = 13;
600 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 2)
601 criteria = 9000;
602 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 3)
603 criteria = -5;
604 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 3)
606 cxLinkedListDestroy(list);
607 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
608 }
610 void test_hl_linked_list_sort(void) {
611 int expected[] = {
612 14, 30, 151, 163, 227, 300, 315, 317, 363, 398, 417, 424, 438, 446, 508, 555, 605, 713, 716, 759, 761, 880,
613 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 1707, 1734, 1771, 1874, 1894,
614 1976, 2079, 2124, 2130, 2135, 2266, 2338, 2358, 2430, 2500, 2540, 2542, 2546, 2711, 2733, 2754, 2764, 2797,
615 2888, 2900, 3020, 3053, 3109, 3244, 3275, 3302, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 3675, 3677,
616 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681,
617 4785, 4791, 4801, 4859, 4903, 4973
618 };
619 int scrambled[] = {
620 759, 716, 880, 761, 2358, 2542, 2500, 2540, 2546, 2711, 2430, 1707, 1874, 1771, 1894, 1734, 1976, 2079,
621 2124, 2130, 2135, 2266, 2338, 2733, 2754, 2764, 2797, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 2888,
622 2900, 3020, 3053, 3109, 3244, 3275, 3302, 438, 446, 508, 555, 605, 713, 14, 30, 151, 163, 227, 300,
623 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 315, 317, 363, 398, 417, 424,
624 3675, 3677, 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4785, 4791, 4801, 4859, 4903, 4973,
625 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681
626 };
628 cxTestingAllocatorReset();
630 CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
632 for (int i = 0; i < 100; i++) {
633 cxListAdd(list, &scrambled[i]);
634 }
636 cxListSort(list);
638 for (int i = 0; i < 100; i++) {
639 CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), expected[i])
640 }
642 cxLinkedListDestroy(list);
643 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
644 }
646 void test_hl_ptr_linked_list_create(void) {
647 cxTestingAllocatorReset();
649 CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
651 CU_ASSERT_EQUAL(list->size, 0)
652 CU_ASSERT_EQUAL(list->capacity, (size_t) -1)
653 CU_ASSERT_PTR_EQUAL(list->allocator, cxTestingAllocator)
654 CU_ASSERT_EQUAL(list->itemsize, sizeof(void *))
655 CU_ASSERT_PTR_EQUAL(list->cmpfunc, cmp_int)
657 cxLinkedListDestroy(list);
658 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
659 }
661 void test_hl_ptr_linked_list_add(void) {
662 cxTestingAllocatorReset();
664 CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
666 int a = 5, b = 47, c = 13;
668 CU_ASSERT_EQUAL(cxListAdd(list, &a), 0)
669 CU_ASSERT_EQUAL(cxListAdd(list, &b), 0)
670 CU_ASSERT_EQUAL(cxListAdd(list, &c), 0)
672 CU_ASSERT_EQUAL(list->size, 3)
673 CU_ASSERT_TRUE(list->capacity >= list->size)
675 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
676 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
677 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
679 a = 9;
680 b = 10;
681 c = 11;
683 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 9)
684 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 10)
685 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 11)
687 cxLinkedListDestroy(list);
688 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
689 }
691 void test_hl_ptr_linked_list_insert(void) {
692 cxTestingAllocatorReset();
694 CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
696 int a = 5, b = 47, c = 13, d = 42;
698 CU_ASSERT_NOT_EQUAL(cxListInsert(list, 1, &a), 0)
699 CU_ASSERT_EQUAL(list->size, 0)
700 CU_ASSERT_EQUAL(cxListInsert(list, 0, &a), 0)
701 CU_ASSERT_EQUAL(list->size, 1)
702 CU_ASSERT_EQUAL(cxListInsert(list, 0, &b), 0)
703 CU_ASSERT_EQUAL(list->size, 2)
704 CU_ASSERT_EQUAL(cxListInsert(list, 1, &c), 0)
705 CU_ASSERT_EQUAL(list->size, 3)
706 CU_ASSERT_EQUAL(cxListInsert(list, 3, &d), 0)
708 CU_ASSERT_EQUAL(list->size, 4)
709 CU_ASSERT_TRUE(list->capacity >= list->size)
711 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
712 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
713 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 5)
714 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 3), 42)
716 cxLinkedListDestroy(list);
717 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
718 }
720 void test_hl_ptr_linked_list_remove(void) {
721 cxTestingAllocatorReset();
723 int a = 5, b = 47, c = 42, d = 13;
724 CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
726 cxListAdd(list, &a);
727 cxListAdd(list, &b);
728 cxListAdd(list, &c);
729 cxListAdd(list, &d);
731 CU_ASSERT_EQUAL(list->size, 4)
732 CU_ASSERT_TRUE(list->capacity >= list->size)
734 CU_ASSERT_NOT_EQUAL(cxListRemove(list, 4), 0)
736 CU_ASSERT_EQUAL(cxListRemove(list, 2), 0)
737 CU_ASSERT_EQUAL(list->size, 3)
738 CU_ASSERT_TRUE(list->capacity >= list->size)
739 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
740 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
741 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
743 CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
744 CU_ASSERT_EQUAL(list->size, 2)
745 CU_ASSERT_TRUE(list->capacity >= list->size)
746 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
747 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
749 CU_ASSERT_EQUAL(cxListRemove(list, 1), 0)
750 CU_ASSERT_EQUAL(list->size, 1)
751 CU_ASSERT_TRUE(list->capacity >= list->size)
752 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
754 CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
755 CU_ASSERT_EQUAL(list->size, 0)
756 CU_ASSERT_TRUE(list->capacity >= list->size)
758 CU_ASSERT_NOT_EQUAL(cxListRemove(list, 0), 0)
760 cxLinkedListDestroy(list);
761 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
762 }
764 void test_hl_ptr_linked_list_find(void) {
765 cxTestingAllocatorReset();
767 int a = 5, b = 47, c = 13, criteria;
768 CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
770 cxListAdd(list, &a);
771 cxListAdd(list, &b);
772 cxListAdd(list, &c);
774 CU_ASSERT_EQUAL(list->size, 3)
775 CU_ASSERT_TRUE(list->capacity >= list->size)
777 criteria = 5;
778 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 0)
779 criteria = 47;
780 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 1)
781 criteria = 13;
782 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 2)
783 criteria = 9000;
784 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 3)
785 criteria = -5;
786 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 3)
787 b = -5;
788 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 1)
790 cxLinkedListDestroy(list);
791 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
792 }
794 void test_hl_ptr_linked_list_sort(void) {
795 int expected[] = {
796 14, 30, 151, 163, 227, 300, 315, 317, 363, 398, 417, 424, 438, 446, 508, 555, 605, 713, 716, 759, 761, 880,
797 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 1707, 1734, 1771, 1874, 1894,
798 1976, 2079, 2124, 2130, 2135, 2266, 2338, 2358, 2430, 2500, 2540, 2542, 2546, 2711, 2733, 2754, 2764, 2797,
799 2888, 2900, 3020, 3053, 3109, 3244, 3275, 3302, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 3675, 3677,
800 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681,
801 4785, 4791, 4801, 4859, 4903, 4973
802 };
803 int scrambled[] = {
804 759, 716, 880, 761, 2358, 2542, 2500, 2540, 2546, 2711, 2430, 1707, 1874, 1771, 1894, 1734, 1976, 2079,
805 2124, 2130, 2135, 2266, 2338, 2733, 2754, 2764, 2797, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 2888,
806 2900, 3020, 3053, 3109, 3244, 3275, 3302, 438, 446, 508, 555, 605, 713, 14, 30, 151, 163, 227, 300,
807 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 315, 317, 363, 398, 417, 424,
808 3675, 3677, 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4785, 4791, 4801, 4859, 4903, 4973,
809 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681
810 };
812 cxTestingAllocatorReset();
814 CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
816 for (int i = 0; i < 100; i++) {
817 cxListAdd(list, &scrambled[i]);
818 }
820 cxListSort(list);
822 for (int i = 0; i < 100; i++) {
823 CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), expected[i])
824 }
826 cxLinkedListDestroy(list);
827 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
828 }
830 int main() {
831 CU_pSuite suite = NULL;
833 if (CUE_SUCCESS != CU_initialize_registry()) {
834 return CU_get_error();
835 }
837 suite = CU_add_suite("low level linked list", NULL, NULL);
839 cu_add_test(suite, test_linked_list_at);
840 cu_add_test(suite, test_linked_list_prepend);
841 cu_add_test(suite, test_linked_list_add);
842 cu_add_test(suite, test_linked_list_first);
843 cu_add_test(suite, test_linked_list_last);
844 cu_add_test(suite, test_linked_list_prev);
845 cu_add_test(suite, test_linked_list_remove);
846 cu_add_test(suite, test_linked_list_size);
847 cu_add_test(suite, test_linked_list_sort);
848 cu_add_test(suite, test_linked_list_reverse);
850 suite = CU_add_suite("high level linked list", NULL, NULL);
852 cu_add_test(suite, test_hl_linked_list_create);
853 cu_add_test(suite, test_hl_linked_list_add);
854 cu_add_test(suite, test_hl_linked_list_insert);
855 cu_add_test(suite, test_hl_linked_list_remove);
856 cu_add_test(suite, test_hl_linked_list_find);
857 cu_add_test(suite, test_hl_linked_list_sort);
859 suite = CU_add_suite("high level pointer linked list", NULL, NULL);
861 cu_add_test(suite, test_hl_ptr_linked_list_create);
862 cu_add_test(suite, test_hl_ptr_linked_list_add);
863 cu_add_test(suite, test_hl_ptr_linked_list_insert);
864 cu_add_test(suite, test_hl_ptr_linked_list_remove);
865 cu_add_test(suite, test_hl_ptr_linked_list_find);
866 cu_add_test(suite, test_hl_ptr_linked_list_sort);
868 CU_basic_set_mode(UCX_CU_BRM);
870 int exitcode;
871 if (CU_basic_run_tests()) {
872 exitcode = CU_get_error();
873 } else {
874 exitcode = CU_get_number_of_failures() == 0 ? 0 : 1;
875 }
876 CU_cleanup_registry();
877 return exitcode;
878 }
