test/test_list.c@a29bdd703e02
test/test_list.c
Mon, 20 Dec 2021 12:10:48 +0100
- author
- Mike Becker <universe@uap-core.de>
- date
- Mon, 20 Dec 2021 12:10:48 +0100
- changeset 479
- a29bdd703e02
- parent 478
- 599770bb6314
- child 482
- 0d998f19d130
- permissions
- -rw-r--r--
add linked list tests for cxListAt()
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_at(void) {
576 cxTestingAllocatorReset();
578 CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
580 int data;
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(*(int*)cxListAt(list, 0), 5)
589 CU_ASSERT_EQUAL(*(int*)cxListAt(list, 1), 47)
590 CU_ASSERT_EQUAL(*(int*)cxListAt(list, 2), 13)
591 CU_ASSERT_PTR_NULL(cxListAt(list, 3))
593 cxLinkedListDestroy(list);
594 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
595 }
597 void test_hl_linked_list_find(void) {
598 cxTestingAllocatorReset();
600 int data, criteria;
601 CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
603 data = 5;
604 cxListAdd(list, &data);
605 data = 47;
606 cxListAdd(list, &data);
607 data = 13;
608 cxListAdd(list, &data);
610 CU_ASSERT_EQUAL(list->size, 3)
611 CU_ASSERT_TRUE(list->capacity >= list->size)
613 criteria = 5;
614 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 0)
615 criteria = 47;
616 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 1)
617 criteria = 13;
618 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 2)
619 criteria = 9000;
620 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 3)
621 criteria = -5;
622 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 3)
624 cxLinkedListDestroy(list);
625 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
626 }
628 void test_hl_linked_list_sort(void) {
629 int expected[] = {
630 14, 30, 151, 163, 227, 300, 315, 317, 363, 398, 417, 424, 438, 446, 508, 555, 605, 713, 716, 759, 761, 880,
631 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 1707, 1734, 1771, 1874, 1894,
632 1976, 2079, 2124, 2130, 2135, 2266, 2338, 2358, 2430, 2500, 2540, 2542, 2546, 2711, 2733, 2754, 2764, 2797,
633 2888, 2900, 3020, 3053, 3109, 3244, 3275, 3302, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 3675, 3677,
634 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681,
635 4785, 4791, 4801, 4859, 4903, 4973
636 };
637 int scrambled[] = {
638 759, 716, 880, 761, 2358, 2542, 2500, 2540, 2546, 2711, 2430, 1707, 1874, 1771, 1894, 1734, 1976, 2079,
639 2124, 2130, 2135, 2266, 2338, 2733, 2754, 2764, 2797, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 2888,
640 2900, 3020, 3053, 3109, 3244, 3275, 3302, 438, 446, 508, 555, 605, 713, 14, 30, 151, 163, 227, 300,
641 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 315, 317, 363, 398, 417, 424,
642 3675, 3677, 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4785, 4791, 4801, 4859, 4903, 4973,
643 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681
644 };
646 cxTestingAllocatorReset();
648 CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
650 for (int i = 0; i < 100; i++) {
651 cxListAdd(list, &scrambled[i]);
652 }
654 cxListSort(list);
656 for (int i = 0; i < 100; i++) {
657 CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), expected[i])
658 }
660 cxLinkedListDestroy(list);
661 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
662 }
664 void test_hl_ptr_linked_list_create(void) {
665 cxTestingAllocatorReset();
667 CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
669 CU_ASSERT_EQUAL(list->size, 0)
670 CU_ASSERT_EQUAL(list->capacity, (size_t) -1)
671 CU_ASSERT_PTR_EQUAL(list->allocator, cxTestingAllocator)
672 CU_ASSERT_EQUAL(list->itemsize, sizeof(void *))
673 CU_ASSERT_PTR_EQUAL(list->cmpfunc, cmp_int)
675 cxLinkedListDestroy(list);
676 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
677 }
679 void test_hl_ptr_linked_list_add(void) {
680 cxTestingAllocatorReset();
682 CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
684 int a = 5, b = 47, c = 13;
686 CU_ASSERT_EQUAL(cxListAdd(list, &a), 0)
687 CU_ASSERT_EQUAL(cxListAdd(list, &b), 0)
688 CU_ASSERT_EQUAL(cxListAdd(list, &c), 0)
690 CU_ASSERT_EQUAL(list->size, 3)
691 CU_ASSERT_TRUE(list->capacity >= list->size)
693 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
694 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
695 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
697 a = 9;
698 b = 10;
699 c = 11;
701 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 9)
702 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 10)
703 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 11)
705 cxLinkedListDestroy(list);
706 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
707 }
709 void test_hl_ptr_linked_list_insert(void) {
710 cxTestingAllocatorReset();
712 CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
714 int a = 5, b = 47, c = 13, d = 42;
716 CU_ASSERT_NOT_EQUAL(cxListInsert(list, 1, &a), 0)
717 CU_ASSERT_EQUAL(list->size, 0)
718 CU_ASSERT_EQUAL(cxListInsert(list, 0, &a), 0)
719 CU_ASSERT_EQUAL(list->size, 1)
720 CU_ASSERT_EQUAL(cxListInsert(list, 0, &b), 0)
721 CU_ASSERT_EQUAL(list->size, 2)
722 CU_ASSERT_EQUAL(cxListInsert(list, 1, &c), 0)
723 CU_ASSERT_EQUAL(list->size, 3)
724 CU_ASSERT_EQUAL(cxListInsert(list, 3, &d), 0)
726 CU_ASSERT_EQUAL(list->size, 4)
727 CU_ASSERT_TRUE(list->capacity >= list->size)
729 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
730 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
731 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 5)
732 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 3), 42)
734 cxLinkedListDestroy(list);
735 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
736 }
738 void test_hl_ptr_linked_list_remove(void) {
739 cxTestingAllocatorReset();
741 int a = 5, b = 47, c = 42, d = 13;
742 CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
744 cxListAdd(list, &a);
745 cxListAdd(list, &b);
746 cxListAdd(list, &c);
747 cxListAdd(list, &d);
749 CU_ASSERT_EQUAL(list->size, 4)
750 CU_ASSERT_TRUE(list->capacity >= list->size)
752 CU_ASSERT_NOT_EQUAL(cxListRemove(list, 4), 0)
754 CU_ASSERT_EQUAL(cxListRemove(list, 2), 0)
755 CU_ASSERT_EQUAL(list->size, 3)
756 CU_ASSERT_TRUE(list->capacity >= list->size)
757 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
758 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
759 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
761 CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
762 CU_ASSERT_EQUAL(list->size, 2)
763 CU_ASSERT_TRUE(list->capacity >= list->size)
764 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
765 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
767 CU_ASSERT_EQUAL(cxListRemove(list, 1), 0)
768 CU_ASSERT_EQUAL(list->size, 1)
769 CU_ASSERT_TRUE(list->capacity >= list->size)
770 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
772 CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
773 CU_ASSERT_EQUAL(list->size, 0)
774 CU_ASSERT_TRUE(list->capacity >= list->size)
776 CU_ASSERT_NOT_EQUAL(cxListRemove(list, 0), 0)
778 cxLinkedListDestroy(list);
779 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
780 }
782 void test_hl_ptr_linked_list_at(void) {
783 cxTestingAllocatorReset();
785 CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
787 int a = 5, b = 47, c = 13;
788 cxListAdd(list, &a);
789 cxListAdd(list, &b);
790 cxListAdd(list, &c);
792 CU_ASSERT_EQUAL(*(int*)cxListAt(list, 0), 5)
793 CU_ASSERT_EQUAL(*(int*)cxListAt(list, 1), 47)
794 CU_ASSERT_EQUAL(*(int*)cxListAt(list, 2), 13)
795 CU_ASSERT_PTR_NULL(cxListAt(list, 3))
797 cxLinkedListDestroy(list);
798 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
799 }
801 void test_hl_ptr_linked_list_find(void) {
802 cxTestingAllocatorReset();
804 int a = 5, b = 47, c = 13, criteria;
805 CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
807 cxListAdd(list, &a);
808 cxListAdd(list, &b);
809 cxListAdd(list, &c);
811 CU_ASSERT_EQUAL(list->size, 3)
812 CU_ASSERT_TRUE(list->capacity >= list->size)
814 criteria = 5;
815 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 0)
816 criteria = 47;
817 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 1)
818 criteria = 13;
819 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 2)
820 criteria = 9000;
821 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 3)
822 criteria = -5;
823 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 3)
824 b = -5;
825 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 1)
827 cxLinkedListDestroy(list);
828 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
829 }
831 void test_hl_ptr_linked_list_sort(void) {
832 int expected[] = {
833 14, 30, 151, 163, 227, 300, 315, 317, 363, 398, 417, 424, 438, 446, 508, 555, 605, 713, 716, 759, 761, 880,
834 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 1707, 1734, 1771, 1874, 1894,
835 1976, 2079, 2124, 2130, 2135, 2266, 2338, 2358, 2430, 2500, 2540, 2542, 2546, 2711, 2733, 2754, 2764, 2797,
836 2888, 2900, 3020, 3053, 3109, 3244, 3275, 3302, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 3675, 3677,
837 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681,
838 4785, 4791, 4801, 4859, 4903, 4973
839 };
840 int scrambled[] = {
841 759, 716, 880, 761, 2358, 2542, 2500, 2540, 2546, 2711, 2430, 1707, 1874, 1771, 1894, 1734, 1976, 2079,
842 2124, 2130, 2135, 2266, 2338, 2733, 2754, 2764, 2797, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 2888,
843 2900, 3020, 3053, 3109, 3244, 3275, 3302, 438, 446, 508, 555, 605, 713, 14, 30, 151, 163, 227, 300,
844 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 315, 317, 363, 398, 417, 424,
845 3675, 3677, 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4785, 4791, 4801, 4859, 4903, 4973,
846 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681
847 };
849 cxTestingAllocatorReset();
851 CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
853 for (int i = 0; i < 100; i++) {
854 cxListAdd(list, &scrambled[i]);
855 }
857 cxListSort(list);
859 for (int i = 0; i < 100; i++) {
860 CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), expected[i])
861 }
863 cxLinkedListDestroy(list);
864 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
865 }
867 int main() {
868 CU_pSuite suite = NULL;
870 if (CUE_SUCCESS != CU_initialize_registry()) {
871 return CU_get_error();
872 }
874 suite = CU_add_suite("low level linked list", NULL, NULL);
876 cu_add_test(suite, test_linked_list_at);
877 cu_add_test(suite, test_linked_list_prepend);
878 cu_add_test(suite, test_linked_list_add);
879 cu_add_test(suite, test_linked_list_first);
880 cu_add_test(suite, test_linked_list_last);
881 cu_add_test(suite, test_linked_list_prev);
882 cu_add_test(suite, test_linked_list_remove);
883 cu_add_test(suite, test_linked_list_size);
884 cu_add_test(suite, test_linked_list_sort);
885 cu_add_test(suite, test_linked_list_reverse);
887 suite = CU_add_suite("high level linked list", NULL, NULL);
889 cu_add_test(suite, test_hl_linked_list_create);
890 cu_add_test(suite, test_hl_linked_list_add);
891 cu_add_test(suite, test_hl_linked_list_insert);
892 cu_add_test(suite, test_hl_linked_list_remove);
893 cu_add_test(suite, test_hl_linked_list_at);
894 cu_add_test(suite, test_hl_linked_list_find);
895 cu_add_test(suite, test_hl_linked_list_sort);
897 suite = CU_add_suite("high level pointer linked list", NULL, NULL);
899 cu_add_test(suite, test_hl_ptr_linked_list_create);
900 cu_add_test(suite, test_hl_ptr_linked_list_add);
901 cu_add_test(suite, test_hl_ptr_linked_list_insert);
902 cu_add_test(suite, test_hl_ptr_linked_list_remove);
903 cu_add_test(suite, test_hl_ptr_linked_list_at);
904 cu_add_test(suite, test_hl_ptr_linked_list_find);
905 cu_add_test(suite, test_hl_ptr_linked_list_sort);
907 CU_basic_set_mode(UCX_CU_BRM);
909 int exitcode;
910 if (CU_basic_run_tests()) {
911 exitcode = CU_get_error();
912 } else {
913 exitcode = CU_get_number_of_failures() == 0 ? 0 : 1;
914 }
915 CU_cleanup_registry();
916 return exitcode;
917 }
