test/test_list.c@1bd4b8c28722
test/test_list.c
Fri, 08 Oct 2021 19:47:31 +0200
- author
- Mike Becker <universe@uap-core.de>
- date
- Fri, 08 Oct 2021 19:47:31 +0200
- changeset 473
- 1bd4b8c28722
- parent 469
- 0458bff0b1cd
- child 474
- 9c1fccda16bc
- permissions
- -rw-r--r--
add cx_linked_list_{prev, remove, reverse}
changes assertions for some low level methods (loc_next is now always mandatory)
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_EQUAL(nodes[0].prev, NULL)
92 CU_ASSERT_PTR_EQUAL(nodes[0].next, NULL)
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 begin, end / next
117 memset(nodes, 0, 4 * sizeof(struct node));
118 begin = NULL;
119 end = NULL;
121 cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[0]);
122 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
123 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
124 cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[1]);
125 CU_ASSERT_PTR_EQUAL(end, &nodes[1])
126 CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1])
127 CU_ASSERT_PTR_NULL(nodes[1].prev)
128 }
130 void test_linked_list_last(void) {
131 CU_ASSERT_PTR_NULL(cx_linked_list_last(NULL, 0))
133 struct node {
134 int data;
135 void *next;
136 };
137 ptrdiff_t loc = offsetof(struct node, next);
139 struct node third = {3, NULL};
140 struct node second = {2, &third};
141 struct node first = {1, &second};
143 CU_ASSERT_PTR_EQUAL(cx_linked_list_last(&first, loc), &third)
144 CU_ASSERT_PTR_EQUAL(cx_linked_list_last(&second, loc), &third)
145 CU_ASSERT_PTR_EQUAL(cx_linked_list_last(&third, loc), &third)
146 }
148 void test_linked_list_prev(void) {
149 struct node {
150 void *next;
151 };
152 ptrdiff_t loc = offsetof(struct node, next);
154 struct node third = {NULL};
155 struct node second = {&third};
156 struct node first = {&second};
158 CU_ASSERT_PTR_NULL(cx_linked_list_prev(&first, loc, &first))
159 CU_ASSERT_PTR_EQUAL(cx_linked_list_prev(&first, loc, &second), &first)
160 CU_ASSERT_PTR_EQUAL(cx_linked_list_prev(&first, loc, &third), &second)
161 }
163 void test_linked_list_remove(void) {
164 struct node {
165 void *next;
166 };
167 struct dnode {
168 void *next;
169 void *prev;
170 };
171 ptrdiff_t loc = offsetof(struct node, next);
172 ptrdiff_t ploc = offsetof(struct dnode, prev);
174 void *begin;
175 void *end;
176 void *result;
178 // single linked list
179 struct node third = {NULL};
180 struct node second = {&third};
181 struct node first = {&second};
182 begin = &first;
184 result = cx_linked_list_remove(&begin, NULL, -1, loc, &second);
185 CU_ASSERT_PTR_EQUAL(result, &first)
186 CU_ASSERT_PTR_EQUAL(begin, &first)
187 CU_ASSERT_PTR_EQUAL(first.next, &third)
188 CU_ASSERT_PTR_NULL(second.next)
189 CU_ASSERT_PTR_NULL(third.next)
191 result = cx_linked_list_remove(&begin, NULL, -1, loc, &first);
192 CU_ASSERT_PTR_EQUAL(result, &third)
193 CU_ASSERT_PTR_EQUAL(begin, &third)
194 CU_ASSERT_PTR_NULL(first.next)
195 CU_ASSERT_PTR_NULL(third.next)
197 result = cx_linked_list_remove(&begin, NULL, -1, loc, &third);
198 CU_ASSERT_PTR_NULL(result)
199 CU_ASSERT_PTR_NULL(begin)
200 CU_ASSERT_PTR_NULL(third.next)
202 // doubly linked list
203 struct dnode dthird = {NULL , NULL};
204 struct dnode dsecond = {&dthird, NULL};
205 struct dnode dfirst = {&dsecond, NULL};
206 dthird.prev = &dsecond;
207 dsecond.prev = &dfirst;
208 begin = &dfirst;
209 end = &dthird;
211 result = cx_linked_list_remove(&begin, &end, ploc, loc, &dsecond);
212 CU_ASSERT_PTR_EQUAL(result, &dfirst)
213 CU_ASSERT_PTR_EQUAL(begin, &dfirst)
214 CU_ASSERT_PTR_EQUAL(end, &dthird)
215 CU_ASSERT_PTR_NULL(dfirst.prev)
216 CU_ASSERT_PTR_EQUAL(dfirst.next, &dthird)
217 CU_ASSERT_PTR_NULL(dsecond.prev)
218 CU_ASSERT_PTR_NULL(dsecond.next)
219 CU_ASSERT_PTR_EQUAL(dthird.prev, &dfirst)
220 CU_ASSERT_PTR_NULL(dthird.next)
222 result = cx_linked_list_remove(&begin, &end, ploc, loc, &dthird);
223 CU_ASSERT_PTR_EQUAL(result, &dfirst)
224 CU_ASSERT_PTR_EQUAL(begin, &dfirst)
225 CU_ASSERT_PTR_EQUAL(end, &dfirst)
226 CU_ASSERT_PTR_NULL(dfirst.prev)
227 CU_ASSERT_PTR_NULL(dfirst.next)
228 CU_ASSERT_PTR_NULL(dthird.prev)
229 CU_ASSERT_PTR_NULL(dthird.next)
231 result = cx_linked_list_remove(&begin, &end, ploc, loc, &dfirst);
232 CU_ASSERT_PTR_NULL(result)
233 CU_ASSERT_PTR_NULL(begin)
234 CU_ASSERT_PTR_NULL(end)
235 CU_ASSERT_PTR_NULL(dfirst.next)
236 CU_ASSERT_PTR_NULL(dfirst.prev)
237 }
239 void test_linked_list_size(void) {
240 struct node {
241 void *next;
242 };
243 ptrdiff_t loc = offsetof(struct node, next);
245 struct node first = {NULL};
246 struct node second = {NULL};
247 struct node third = {NULL};
249 CU_ASSERT_PTR_EQUAL(cx_linked_list_size(NULL, loc), 0)
250 CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&first, loc), 1)
251 first.next = &second;
252 CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&first, loc), 2)
253 second.next = &third;
254 CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&first, loc), 3)
255 CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&second, loc), 2)
256 }
258 void test_linked_list_sort(void) {
259 struct node {
260 void *prev;
261 void *next;
262 int data;
263 };
265 int expected[] = {
266 14, 30, 151, 163, 227, 300, 315, 317, 363, 398, 417, 424, 438, 446, 508, 555, 605, 713, 716, 759, 761, 880,
267 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 1707, 1734, 1771, 1874, 1894,
268 1976, 2079, 2124, 2130, 2135, 2266, 2338, 2358, 2430, 2500, 2540, 2542, 2546, 2711, 2733, 2754, 2764, 2797,
269 2888, 2900, 3020, 3053, 3109, 3244, 3275, 3302, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 3675, 3677,
270 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681,
271 4785, 4791, 4801, 4859, 4903, 4973
272 };
273 int scrambled[] = {
274 759, 716, 880, 761, 2358, 2542, 2500, 2540, 2546, 2711, 2430, 1707, 1874, 1771, 1894, 1734, 1976, 2079,
275 2124, 2130, 2135, 2266, 2338, 2733, 2754, 2764, 2797, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 2888,
276 2900, 3020, 3053, 3109, 3244, 3275, 3302, 438, 446, 508, 555, 605, 713, 14, 30, 151, 163, 227, 300,
277 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 315, 317, 363, 398, 417, 424,
278 3675, 3677, 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4785, 4791, 4801, 4859, 4903, 4973,
279 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681
280 };
282 struct node *nodes = calloc(100, sizeof(struct node));
283 for (int i = 0; i < 100; i++) {
284 nodes[i].prev = i == 0 ? NULL : &nodes[i - 1];
285 nodes[i].next = i == 99 ? NULL : &nodes[i + 1];
286 nodes[i].data = scrambled[i];
287 }
289 struct node *begin = &nodes[0];
290 struct node *end = &nodes[99];
292 cx_linked_list_sort((void **) &begin, (void **) &end,
293 offsetof(struct node, prev),
294 offsetof(struct node, next),
295 offsetof(struct node, data),
296 0, (CxListComparator) cmp_int);
298 CU_ASSERT_PTR_NULL(begin->prev)
299 CU_ASSERT_EQUAL(begin->data, expected[0])
300 struct node *check = begin;
301 struct node *check_last = NULL;
302 for (int i = 0; i < 100; i++) {
303 CU_ASSERT_EQUAL(check->data, expected[i])
304 CU_ASSERT_PTR_EQUAL(check->prev, check_last)
305 if (i < 99) {
306 CU_ASSERT_PTR_NOT_NULL(check->next)
307 }
308 check_last = check;
309 check = check->next;
310 }
311 CU_ASSERT_PTR_NULL(check)
312 CU_ASSERT_EQUAL(end->data, expected[99])
313 }
315 void test_linked_list_reverse(void) {
316 struct node {
317 void *next;
318 };
319 struct dnode {
320 void *next;
321 void *prev;
322 };
323 ptrdiff_t loc = offsetof(struct node, next);
324 ptrdiff_t ploc = offsetof(struct dnode, prev);
326 void *begin;
327 void *end;
329 // single linked list
330 struct node third = {NULL};
331 struct node second = {&third};
332 struct node first = {&second};
333 begin = &first;
335 cx_linked_list_reverse(&begin, NULL, -1, loc);
336 CU_ASSERT_PTR_EQUAL(begin, &third)
337 CU_ASSERT_PTR_EQUAL(third.next, &second)
338 CU_ASSERT_PTR_EQUAL(second.next, &first)
339 CU_ASSERT_PTR_NULL(first.next)
341 // doubly linked list
342 struct dnode dthird = {NULL , NULL};
343 struct dnode dsecond = {&dthird, NULL};
344 struct dnode dfirst = {&dsecond, NULL};
345 dthird.prev = &dsecond;
346 dsecond.prev = &dfirst;
347 begin = &dfirst;
348 end = &dthird;
350 cx_linked_list_reverse(&begin, &end, ploc, loc);
351 CU_ASSERT_PTR_EQUAL(begin, &dthird)
352 CU_ASSERT_PTR_EQUAL(end, &dfirst)
353 CU_ASSERT_PTR_EQUAL(dthird.next, &dsecond)
354 CU_ASSERT_PTR_EQUAL(dsecond.next, &dfirst)
355 CU_ASSERT_PTR_NULL(dfirst.next)
356 CU_ASSERT_PTR_NULL(dthird.prev)
357 CU_ASSERT_PTR_EQUAL(dsecond.prev, &dthird)
358 CU_ASSERT_PTR_EQUAL(dfirst.prev, &dsecond)
359 }
361 void test_hl_linked_list_create(void) {
362 cxTestingAllocatorReset();
364 CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
366 CU_ASSERT_EQUAL(list->size, 0)
367 CU_ASSERT_EQUAL(list->capacity, (size_t) -1)
368 CU_ASSERT_PTR_EQUAL(list->allocator, cxTestingAllocator)
369 CU_ASSERT_EQUAL(list->itemsize, sizeof(int))
370 CU_ASSERT_PTR_EQUAL(list->cmpfunc, cmp_int)
372 cxLinkedListDestroy(list);
373 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
374 }
376 void test_hl_linked_list_add(void) {
377 cxTestingAllocatorReset();
379 int data;
380 CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
382 data = 5;
383 CU_ASSERT_EQUAL(cxListAdd(list, &data), 0)
384 data = 47;
385 CU_ASSERT_EQUAL(cxListAdd(list, &data), 0)
386 data = 13;
387 CU_ASSERT_EQUAL(cxListAdd(list, &data), 0)
389 CU_ASSERT_EQUAL(list->size, 3)
390 CU_ASSERT_TRUE(list->capacity >= list->size)
392 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
393 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
394 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
396 cxLinkedListDestroy(list);
397 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
398 }
400 void test_hl_linked_list_last(void) {
401 cxTestingAllocatorReset();
403 int data;
404 CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
406 CU_ASSERT_PTR_NULL(cxListLast(list))
408 data = 5;
409 CU_ASSERT_EQUAL(cxListAdd(list, &data), 0)
410 CU_ASSERT_EQUAL(*(int *) cxListLast(list), 5)
412 data = 47;
413 CU_ASSERT_EQUAL(cxListAdd(list, &data), 0)
414 CU_ASSERT_EQUAL(*(int *) cxListLast(list), 47)
416 cxLinkedListDestroy(list);
417 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
418 }
420 void test_hl_linked_list_insert(void) {
421 cxTestingAllocatorReset();
423 int data;
424 CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
426 data = 5;
427 CU_ASSERT_NOT_EQUAL(cxListInsert(list, 1, &data), 0)
428 CU_ASSERT_EQUAL(list->size, 0)
429 CU_ASSERT_EQUAL(cxListInsert(list, 0, &data), 0)
430 CU_ASSERT_EQUAL(list->size, 1)
431 data = 47;
432 CU_ASSERT_EQUAL(cxListInsert(list, 0, &data), 0)
433 CU_ASSERT_EQUAL(list->size, 2)
434 data = 13;
435 CU_ASSERT_EQUAL(cxListInsert(list, 1, &data), 0)
436 CU_ASSERT_EQUAL(list->size, 3)
437 data = 42;
438 CU_ASSERT_EQUAL(cxListInsert(list, 3, &data), 0)
440 CU_ASSERT_EQUAL(list->size, 4)
441 CU_ASSERT_TRUE(list->capacity >= list->size)
443 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
444 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
445 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 5)
446 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 3), 42)
448 cxLinkedListDestroy(list);
449 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
450 }
452 void test_hl_linked_list_remove(void) {
453 cxTestingAllocatorReset();
455 int data;
456 CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
458 data = 5;
459 cxListAdd(list, &data);
460 data = 47;
461 cxListAdd(list, &data);
462 data = 42;
463 cxListAdd(list, &data);
464 data = 13;
465 cxListAdd(list, &data);
467 CU_ASSERT_EQUAL(list->size, 4)
468 CU_ASSERT_TRUE(list->capacity >= list->size)
470 CU_ASSERT_NOT_EQUAL(cxListRemove(list, 4), 0)
472 CU_ASSERT_EQUAL(cxListRemove(list, 2), 0)
473 CU_ASSERT_EQUAL(list->size, 3)
474 CU_ASSERT_TRUE(list->capacity >= list->size)
475 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
476 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
477 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
479 CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
480 CU_ASSERT_EQUAL(list->size, 2)
481 CU_ASSERT_TRUE(list->capacity >= list->size)
482 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
483 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
485 CU_ASSERT_EQUAL(cxListRemove(list, 1), 0)
486 CU_ASSERT_EQUAL(list->size, 1)
487 CU_ASSERT_TRUE(list->capacity >= list->size)
488 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
490 CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
491 CU_ASSERT_EQUAL(list->size, 0)
492 CU_ASSERT_TRUE(list->capacity >= list->size)
494 CU_ASSERT_NOT_EQUAL(cxListRemove(list, 0), 0)
496 cxLinkedListDestroy(list);
497 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
498 }
500 void test_hl_linked_list_find(void) {
501 cxTestingAllocatorReset();
503 int data, criteria;
504 CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
506 data = 5;
507 cxListAdd(list, &data);
508 data = 47;
509 cxListAdd(list, &data);
510 data = 13;
511 cxListAdd(list, &data);
513 CU_ASSERT_EQUAL(list->size, 3)
514 CU_ASSERT_TRUE(list->capacity >= list->size)
516 criteria = 5;
517 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 0)
518 criteria = 47;
519 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 1)
520 criteria = 13;
521 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 2)
522 criteria = 9000;
523 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 3)
524 criteria = -5;
525 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 3)
527 cxLinkedListDestroy(list);
528 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
529 }
531 void test_hl_linked_list_sort(void) {
532 int expected[] = {
533 14, 30, 151, 163, 227, 300, 315, 317, 363, 398, 417, 424, 438, 446, 508, 555, 605, 713, 716, 759, 761, 880,
534 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 1707, 1734, 1771, 1874, 1894,
535 1976, 2079, 2124, 2130, 2135, 2266, 2338, 2358, 2430, 2500, 2540, 2542, 2546, 2711, 2733, 2754, 2764, 2797,
536 2888, 2900, 3020, 3053, 3109, 3244, 3275, 3302, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 3675, 3677,
537 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681,
538 4785, 4791, 4801, 4859, 4903, 4973
539 };
540 int scrambled[] = {
541 759, 716, 880, 761, 2358, 2542, 2500, 2540, 2546, 2711, 2430, 1707, 1874, 1771, 1894, 1734, 1976, 2079,
542 2124, 2130, 2135, 2266, 2338, 2733, 2754, 2764, 2797, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 2888,
543 2900, 3020, 3053, 3109, 3244, 3275, 3302, 438, 446, 508, 555, 605, 713, 14, 30, 151, 163, 227, 300,
544 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 315, 317, 363, 398, 417, 424,
545 3675, 3677, 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4785, 4791, 4801, 4859, 4903, 4973,
546 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681
547 };
549 cxTestingAllocatorReset();
551 CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
553 for (int i = 0; i < 100; i++) {
554 cxListAdd(list, &scrambled[i]);
555 }
557 cxListSort(list);
559 for (int i = 0; i < 100; i++) {
560 CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), expected[i])
561 }
563 cxLinkedListDestroy(list);
564 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
565 }
567 void test_hl_ptr_linked_list_create(void) {
568 cxTestingAllocatorReset();
570 CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
572 CU_ASSERT_EQUAL(list->size, 0)
573 CU_ASSERT_EQUAL(list->capacity, (size_t) -1)
574 CU_ASSERT_PTR_EQUAL(list->allocator, cxTestingAllocator)
575 CU_ASSERT_EQUAL(list->itemsize, sizeof(void *))
576 CU_ASSERT_PTR_EQUAL(list->cmpfunc, cmp_int)
578 cxLinkedListDestroy(list);
579 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
580 }
582 void test_hl_ptr_linked_list_add(void) {
583 cxTestingAllocatorReset();
585 CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
587 int a = 5, b = 47, c = 13;
589 CU_ASSERT_EQUAL(cxListAdd(list, &a), 0)
590 CU_ASSERT_EQUAL(cxListAdd(list, &b), 0)
591 CU_ASSERT_EQUAL(cxListAdd(list, &c), 0)
593 CU_ASSERT_EQUAL(list->size, 3)
594 CU_ASSERT_TRUE(list->capacity >= list->size)
596 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
597 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
598 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
600 a = 9;
601 b = 10;
602 c = 11;
604 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 9)
605 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 10)
606 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 11)
608 cxLinkedListDestroy(list);
609 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
610 }
612 void test_hl_ptr_linked_list_last(void) {
613 cxTestingAllocatorReset();
615 CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
616 CU_ASSERT_PTR_NULL(cxListLast(list))
618 int a = 5, b = 47;
620 CU_ASSERT_EQUAL(cxListAdd(list, &a), 0)
621 CU_ASSERT_EQUAL(*(int *) cxListLast(list), 5)
622 CU_ASSERT_EQUAL(cxListAdd(list, &b), 0)
623 CU_ASSERT_EQUAL(*(int *) cxListLast(list), 47)
625 cxLinkedListDestroy(list);
626 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
627 }
629 void test_hl_ptr_linked_list_insert(void) {
630 cxTestingAllocatorReset();
632 CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
634 int a = 5, b = 47, c = 13, d = 42;
636 CU_ASSERT_NOT_EQUAL(cxListInsert(list, 1, &a), 0)
637 CU_ASSERT_EQUAL(list->size, 0)
638 CU_ASSERT_EQUAL(cxListInsert(list, 0, &a), 0)
639 CU_ASSERT_EQUAL(list->size, 1)
640 CU_ASSERT_EQUAL(cxListInsert(list, 0, &b), 0)
641 CU_ASSERT_EQUAL(list->size, 2)
642 CU_ASSERT_EQUAL(cxListInsert(list, 1, &c), 0)
643 CU_ASSERT_EQUAL(list->size, 3)
644 CU_ASSERT_EQUAL(cxListInsert(list, 3, &d), 0)
646 CU_ASSERT_EQUAL(list->size, 4)
647 CU_ASSERT_TRUE(list->capacity >= list->size)
649 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
650 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
651 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 5)
652 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 3), 42)
654 cxLinkedListDestroy(list);
655 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
656 }
658 void test_hl_ptr_linked_list_remove(void) {
659 cxTestingAllocatorReset();
661 int a = 5, b = 47, c = 42, d = 13;
662 CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
664 cxListAdd(list, &a);
665 cxListAdd(list, &b);
666 cxListAdd(list, &c);
667 cxListAdd(list, &d);
669 CU_ASSERT_EQUAL(list->size, 4)
670 CU_ASSERT_TRUE(list->capacity >= list->size)
672 CU_ASSERT_NOT_EQUAL(cxListRemove(list, 4), 0)
674 CU_ASSERT_EQUAL(cxListRemove(list, 2), 0)
675 CU_ASSERT_EQUAL(list->size, 3)
676 CU_ASSERT_TRUE(list->capacity >= list->size)
677 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
678 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
679 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
681 CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
682 CU_ASSERT_EQUAL(list->size, 2)
683 CU_ASSERT_TRUE(list->capacity >= list->size)
684 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
685 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
687 CU_ASSERT_EQUAL(cxListRemove(list, 1), 0)
688 CU_ASSERT_EQUAL(list->size, 1)
689 CU_ASSERT_TRUE(list->capacity >= list->size)
690 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
692 CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
693 CU_ASSERT_EQUAL(list->size, 0)
694 CU_ASSERT_TRUE(list->capacity >= list->size)
696 CU_ASSERT_NOT_EQUAL(cxListRemove(list, 0), 0)
698 cxLinkedListDestroy(list);
699 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
700 }
702 void test_hl_ptr_linked_list_find(void) {
703 cxTestingAllocatorReset();
705 int a = 5, b = 47, c = 13, criteria;
706 CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
708 cxListAdd(list, &a);
709 cxListAdd(list, &b);
710 cxListAdd(list, &c);
712 CU_ASSERT_EQUAL(list->size, 3)
713 CU_ASSERT_TRUE(list->capacity >= list->size)
715 criteria = 5;
716 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 0)
717 criteria = 47;
718 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 1)
719 criteria = 13;
720 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 2)
721 criteria = 9000;
722 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 3)
723 criteria = -5;
724 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 3)
725 b = -5;
726 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 1)
728 cxLinkedListDestroy(list);
729 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
730 }
732 void test_hl_ptr_linked_list_sort(void) {
733 int expected[] = {
734 14, 30, 151, 163, 227, 300, 315, 317, 363, 398, 417, 424, 438, 446, 508, 555, 605, 713, 716, 759, 761, 880,
735 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 1707, 1734, 1771, 1874, 1894,
736 1976, 2079, 2124, 2130, 2135, 2266, 2338, 2358, 2430, 2500, 2540, 2542, 2546, 2711, 2733, 2754, 2764, 2797,
737 2888, 2900, 3020, 3053, 3109, 3244, 3275, 3302, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 3675, 3677,
738 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681,
739 4785, 4791, 4801, 4859, 4903, 4973
740 };
741 int scrambled[] = {
742 759, 716, 880, 761, 2358, 2542, 2500, 2540, 2546, 2711, 2430, 1707, 1874, 1771, 1894, 1734, 1976, 2079,
743 2124, 2130, 2135, 2266, 2338, 2733, 2754, 2764, 2797, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 2888,
744 2900, 3020, 3053, 3109, 3244, 3275, 3302, 438, 446, 508, 555, 605, 713, 14, 30, 151, 163, 227, 300,
745 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 315, 317, 363, 398, 417, 424,
746 3675, 3677, 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4785, 4791, 4801, 4859, 4903, 4973,
747 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681
748 };
750 cxTestingAllocatorReset();
752 CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
754 for (int i = 0; i < 100; i++) {
755 cxListAdd(list, &scrambled[i]);
756 }
758 cxListSort(list);
760 for (int i = 0; i < 100; i++) {
761 CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), expected[i])
762 }
764 cxLinkedListDestroy(list);
765 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
766 }
768 int main() {
769 CU_pSuite suite = NULL;
771 if (CUE_SUCCESS != CU_initialize_registry()) {
772 return CU_get_error();
773 }
775 suite = CU_add_suite("low level linked list", NULL, NULL);
777 cu_add_test(suite, test_linked_list_at);
778 cu_add_test(suite, test_linked_list_add);
779 cu_add_test(suite, test_linked_list_last);
780 cu_add_test(suite, test_linked_list_prev);
781 cu_add_test(suite, test_linked_list_remove);
782 cu_add_test(suite, test_linked_list_size);
783 cu_add_test(suite, test_linked_list_sort);
784 cu_add_test(suite, test_linked_list_reverse);
786 suite = CU_add_suite("high level linked list", NULL, NULL);
788 cu_add_test(suite, test_hl_linked_list_create);
789 cu_add_test(suite, test_hl_linked_list_add);
790 cu_add_test(suite, test_hl_linked_list_last);
791 cu_add_test(suite, test_hl_linked_list_insert);
792 cu_add_test(suite, test_hl_linked_list_remove);
793 cu_add_test(suite, test_hl_linked_list_find);
794 cu_add_test(suite, test_hl_linked_list_sort);
796 suite = CU_add_suite("high level pointer linked list", NULL, NULL);
798 cu_add_test(suite, test_hl_ptr_linked_list_create);
799 cu_add_test(suite, test_hl_ptr_linked_list_add);
800 cu_add_test(suite, test_hl_ptr_linked_list_last);
801 cu_add_test(suite, test_hl_ptr_linked_list_insert);
802 cu_add_test(suite, test_hl_ptr_linked_list_remove);
803 cu_add_test(suite, test_hl_ptr_linked_list_find);
804 cu_add_test(suite, test_hl_ptr_linked_list_sort);
806 CU_basic_set_mode(UCX_CU_BRM);
808 int exitcode;
809 if (CU_basic_run_tests()) {
810 exitcode = CU_get_error();
811 } else {
812 exitcode = CU_get_number_of_failures() == 0 ? 0 : 1;
813 }
814 CU_cleanup_registry();
815 return exitcode;
816 }
