test/test_list.c@9c1fccda16bc
test/test_list.c
Sat, 09 Oct 2021 11:12:48 +0200
- author
- Mike Becker <universe@uap-core.de>
- date
- Sat, 09 Oct 2021 11:12:48 +0200
- changeset 474
- 9c1fccda16bc
- parent 473
- 1bd4b8c28722
- child 475
- 31bf97fdbf71
- permissions
- -rw-r--r--
remove cxListLast (can be realized via cxListAt and index=size-1)
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_insert(void) {
401 cxTestingAllocatorReset();
403 int data;
404 CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
406 data = 5;
407 CU_ASSERT_NOT_EQUAL(cxListInsert(list, 1, &data), 0)
408 CU_ASSERT_EQUAL(list->size, 0)
409 CU_ASSERT_EQUAL(cxListInsert(list, 0, &data), 0)
410 CU_ASSERT_EQUAL(list->size, 1)
411 data = 47;
412 CU_ASSERT_EQUAL(cxListInsert(list, 0, &data), 0)
413 CU_ASSERT_EQUAL(list->size, 2)
414 data = 13;
415 CU_ASSERT_EQUAL(cxListInsert(list, 1, &data), 0)
416 CU_ASSERT_EQUAL(list->size, 3)
417 data = 42;
418 CU_ASSERT_EQUAL(cxListInsert(list, 3, &data), 0)
420 CU_ASSERT_EQUAL(list->size, 4)
421 CU_ASSERT_TRUE(list->capacity >= list->size)
423 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
424 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
425 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 5)
426 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 3), 42)
428 cxLinkedListDestroy(list);
429 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
430 }
432 void test_hl_linked_list_remove(void) {
433 cxTestingAllocatorReset();
435 int data;
436 CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
438 data = 5;
439 cxListAdd(list, &data);
440 data = 47;
441 cxListAdd(list, &data);
442 data = 42;
443 cxListAdd(list, &data);
444 data = 13;
445 cxListAdd(list, &data);
447 CU_ASSERT_EQUAL(list->size, 4)
448 CU_ASSERT_TRUE(list->capacity >= list->size)
450 CU_ASSERT_NOT_EQUAL(cxListRemove(list, 4), 0)
452 CU_ASSERT_EQUAL(cxListRemove(list, 2), 0)
453 CU_ASSERT_EQUAL(list->size, 3)
454 CU_ASSERT_TRUE(list->capacity >= list->size)
455 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
456 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
457 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
459 CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
460 CU_ASSERT_EQUAL(list->size, 2)
461 CU_ASSERT_TRUE(list->capacity >= list->size)
462 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
463 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
465 CU_ASSERT_EQUAL(cxListRemove(list, 1), 0)
466 CU_ASSERT_EQUAL(list->size, 1)
467 CU_ASSERT_TRUE(list->capacity >= list->size)
468 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
470 CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
471 CU_ASSERT_EQUAL(list->size, 0)
472 CU_ASSERT_TRUE(list->capacity >= list->size)
474 CU_ASSERT_NOT_EQUAL(cxListRemove(list, 0), 0)
476 cxLinkedListDestroy(list);
477 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
478 }
480 void test_hl_linked_list_find(void) {
481 cxTestingAllocatorReset();
483 int data, criteria;
484 CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
486 data = 5;
487 cxListAdd(list, &data);
488 data = 47;
489 cxListAdd(list, &data);
490 data = 13;
491 cxListAdd(list, &data);
493 CU_ASSERT_EQUAL(list->size, 3)
494 CU_ASSERT_TRUE(list->capacity >= list->size)
496 criteria = 5;
497 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 0)
498 criteria = 47;
499 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 1)
500 criteria = 13;
501 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 2)
502 criteria = 9000;
503 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 3)
504 criteria = -5;
505 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 3)
507 cxLinkedListDestroy(list);
508 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
509 }
511 void test_hl_linked_list_sort(void) {
512 int expected[] = {
513 14, 30, 151, 163, 227, 300, 315, 317, 363, 398, 417, 424, 438, 446, 508, 555, 605, 713, 716, 759, 761, 880,
514 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 1707, 1734, 1771, 1874, 1894,
515 1976, 2079, 2124, 2130, 2135, 2266, 2338, 2358, 2430, 2500, 2540, 2542, 2546, 2711, 2733, 2754, 2764, 2797,
516 2888, 2900, 3020, 3053, 3109, 3244, 3275, 3302, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 3675, 3677,
517 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681,
518 4785, 4791, 4801, 4859, 4903, 4973
519 };
520 int scrambled[] = {
521 759, 716, 880, 761, 2358, 2542, 2500, 2540, 2546, 2711, 2430, 1707, 1874, 1771, 1894, 1734, 1976, 2079,
522 2124, 2130, 2135, 2266, 2338, 2733, 2754, 2764, 2797, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 2888,
523 2900, 3020, 3053, 3109, 3244, 3275, 3302, 438, 446, 508, 555, 605, 713, 14, 30, 151, 163, 227, 300,
524 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 315, 317, 363, 398, 417, 424,
525 3675, 3677, 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4785, 4791, 4801, 4859, 4903, 4973,
526 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681
527 };
529 cxTestingAllocatorReset();
531 CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
533 for (int i = 0; i < 100; i++) {
534 cxListAdd(list, &scrambled[i]);
535 }
537 cxListSort(list);
539 for (int i = 0; i < 100; i++) {
540 CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), expected[i])
541 }
543 cxLinkedListDestroy(list);
544 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
545 }
547 void test_hl_ptr_linked_list_create(void) {
548 cxTestingAllocatorReset();
550 CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
552 CU_ASSERT_EQUAL(list->size, 0)
553 CU_ASSERT_EQUAL(list->capacity, (size_t) -1)
554 CU_ASSERT_PTR_EQUAL(list->allocator, cxTestingAllocator)
555 CU_ASSERT_EQUAL(list->itemsize, sizeof(void *))
556 CU_ASSERT_PTR_EQUAL(list->cmpfunc, cmp_int)
558 cxLinkedListDestroy(list);
559 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
560 }
562 void test_hl_ptr_linked_list_add(void) {
563 cxTestingAllocatorReset();
565 CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
567 int a = 5, b = 47, c = 13;
569 CU_ASSERT_EQUAL(cxListAdd(list, &a), 0)
570 CU_ASSERT_EQUAL(cxListAdd(list, &b), 0)
571 CU_ASSERT_EQUAL(cxListAdd(list, &c), 0)
573 CU_ASSERT_EQUAL(list->size, 3)
574 CU_ASSERT_TRUE(list->capacity >= list->size)
576 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
577 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
578 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
580 a = 9;
581 b = 10;
582 c = 11;
584 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 9)
585 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 10)
586 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 11)
588 cxLinkedListDestroy(list);
589 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
590 }
592 void test_hl_ptr_linked_list_insert(void) {
593 cxTestingAllocatorReset();
595 CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
597 int a = 5, b = 47, c = 13, d = 42;
599 CU_ASSERT_NOT_EQUAL(cxListInsert(list, 1, &a), 0)
600 CU_ASSERT_EQUAL(list->size, 0)
601 CU_ASSERT_EQUAL(cxListInsert(list, 0, &a), 0)
602 CU_ASSERT_EQUAL(list->size, 1)
603 CU_ASSERT_EQUAL(cxListInsert(list, 0, &b), 0)
604 CU_ASSERT_EQUAL(list->size, 2)
605 CU_ASSERT_EQUAL(cxListInsert(list, 1, &c), 0)
606 CU_ASSERT_EQUAL(list->size, 3)
607 CU_ASSERT_EQUAL(cxListInsert(list, 3, &d), 0)
609 CU_ASSERT_EQUAL(list->size, 4)
610 CU_ASSERT_TRUE(list->capacity >= list->size)
612 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
613 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
614 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 5)
615 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 3), 42)
617 cxLinkedListDestroy(list);
618 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
619 }
621 void test_hl_ptr_linked_list_remove(void) {
622 cxTestingAllocatorReset();
624 int a = 5, b = 47, c = 42, d = 13;
625 CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
627 cxListAdd(list, &a);
628 cxListAdd(list, &b);
629 cxListAdd(list, &c);
630 cxListAdd(list, &d);
632 CU_ASSERT_EQUAL(list->size, 4)
633 CU_ASSERT_TRUE(list->capacity >= list->size)
635 CU_ASSERT_NOT_EQUAL(cxListRemove(list, 4), 0)
637 CU_ASSERT_EQUAL(cxListRemove(list, 2), 0)
638 CU_ASSERT_EQUAL(list->size, 3)
639 CU_ASSERT_TRUE(list->capacity >= list->size)
640 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
641 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
642 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
644 CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
645 CU_ASSERT_EQUAL(list->size, 2)
646 CU_ASSERT_TRUE(list->capacity >= list->size)
647 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
648 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
650 CU_ASSERT_EQUAL(cxListRemove(list, 1), 0)
651 CU_ASSERT_EQUAL(list->size, 1)
652 CU_ASSERT_TRUE(list->capacity >= list->size)
653 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
655 CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
656 CU_ASSERT_EQUAL(list->size, 0)
657 CU_ASSERT_TRUE(list->capacity >= list->size)
659 CU_ASSERT_NOT_EQUAL(cxListRemove(list, 0), 0)
661 cxLinkedListDestroy(list);
662 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
663 }
665 void test_hl_ptr_linked_list_find(void) {
666 cxTestingAllocatorReset();
668 int a = 5, b = 47, c = 13, criteria;
669 CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
671 cxListAdd(list, &a);
672 cxListAdd(list, &b);
673 cxListAdd(list, &c);
675 CU_ASSERT_EQUAL(list->size, 3)
676 CU_ASSERT_TRUE(list->capacity >= list->size)
678 criteria = 5;
679 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 0)
680 criteria = 47;
681 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 1)
682 criteria = 13;
683 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 2)
684 criteria = 9000;
685 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 3)
686 criteria = -5;
687 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 3)
688 b = -5;
689 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 1)
691 cxLinkedListDestroy(list);
692 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
693 }
695 void test_hl_ptr_linked_list_sort(void) {
696 int expected[] = {
697 14, 30, 151, 163, 227, 300, 315, 317, 363, 398, 417, 424, 438, 446, 508, 555, 605, 713, 716, 759, 761, 880,
698 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 1707, 1734, 1771, 1874, 1894,
699 1976, 2079, 2124, 2130, 2135, 2266, 2338, 2358, 2430, 2500, 2540, 2542, 2546, 2711, 2733, 2754, 2764, 2797,
700 2888, 2900, 3020, 3053, 3109, 3244, 3275, 3302, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 3675, 3677,
701 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681,
702 4785, 4791, 4801, 4859, 4903, 4973
703 };
704 int scrambled[] = {
705 759, 716, 880, 761, 2358, 2542, 2500, 2540, 2546, 2711, 2430, 1707, 1874, 1771, 1894, 1734, 1976, 2079,
706 2124, 2130, 2135, 2266, 2338, 2733, 2754, 2764, 2797, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 2888,
707 2900, 3020, 3053, 3109, 3244, 3275, 3302, 438, 446, 508, 555, 605, 713, 14, 30, 151, 163, 227, 300,
708 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 315, 317, 363, 398, 417, 424,
709 3675, 3677, 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4785, 4791, 4801, 4859, 4903, 4973,
710 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681
711 };
713 cxTestingAllocatorReset();
715 CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
717 for (int i = 0; i < 100; i++) {
718 cxListAdd(list, &scrambled[i]);
719 }
721 cxListSort(list);
723 for (int i = 0; i < 100; i++) {
724 CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), expected[i])
725 }
727 cxLinkedListDestroy(list);
728 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
729 }
731 int main() {
732 CU_pSuite suite = NULL;
734 if (CUE_SUCCESS != CU_initialize_registry()) {
735 return CU_get_error();
736 }
738 suite = CU_add_suite("low level linked list", NULL, NULL);
740 cu_add_test(suite, test_linked_list_at);
741 cu_add_test(suite, test_linked_list_add);
742 cu_add_test(suite, test_linked_list_last);
743 cu_add_test(suite, test_linked_list_prev);
744 cu_add_test(suite, test_linked_list_remove);
745 cu_add_test(suite, test_linked_list_size);
746 cu_add_test(suite, test_linked_list_sort);
747 cu_add_test(suite, test_linked_list_reverse);
749 suite = CU_add_suite("high level linked list", NULL, NULL);
751 cu_add_test(suite, test_hl_linked_list_create);
752 cu_add_test(suite, test_hl_linked_list_add);
753 cu_add_test(suite, test_hl_linked_list_insert);
754 cu_add_test(suite, test_hl_linked_list_remove);
755 cu_add_test(suite, test_hl_linked_list_find);
756 cu_add_test(suite, test_hl_linked_list_sort);
758 suite = CU_add_suite("high level pointer linked list", NULL, NULL);
760 cu_add_test(suite, test_hl_ptr_linked_list_create);
761 cu_add_test(suite, test_hl_ptr_linked_list_add);
762 cu_add_test(suite, test_hl_ptr_linked_list_insert);
763 cu_add_test(suite, test_hl_ptr_linked_list_remove);
764 cu_add_test(suite, test_hl_ptr_linked_list_find);
765 cu_add_test(suite, test_hl_ptr_linked_list_sort);
767 CU_basic_set_mode(UCX_CU_BRM);
769 int exitcode;
770 if (CU_basic_run_tests()) {
771 exitcode = CU_get_error();
772 } else {
773 exitcode = CU_get_number_of_failures() == 0 ? 0 : 1;
774 }
775 CU_cleanup_registry();
776 return exitcode;
777 }
