test/test_list.c@0458bff0b1cd
test/test_list.c
Wed, 06 Oct 2021 14:10:19 +0200
- author
- Mike Becker <universe@uap-core.de>
- date
- Wed, 06 Oct 2021 14:10:19 +0200
- changeset 469
- 0458bff0b1cd
- parent 468
- 75ae1dccd101
- child 473
- 1bd4b8c28722
- permissions
- -rw-r--r--
add high level list sort and inlines method invocation functions
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, -1))
132 CU_ASSERT_PTR_NULL(cx_linked_list_last(NULL, 0))
134 struct node {
135 int data;
136 void *next;
137 };
138 ptrdiff_t loc = offsetof(struct node, next);
140 struct node third = {3, NULL};
141 struct node second = {2, &third};
142 struct node first = {1, &second};
144 CU_ASSERT_PTR_EQUAL(cx_linked_list_last(&first, loc), &third)
145 CU_ASSERT_PTR_EQUAL(cx_linked_list_last(&second, loc), &third)
146 CU_ASSERT_PTR_EQUAL(cx_linked_list_last(&third, loc), &third)
147 }
149 void test_linked_list_size(void) {
150 struct node {
151 void *next;
152 };
153 ptrdiff_t loc = offsetof(struct node, next);
155 struct node first = {NULL};
156 struct node second = {NULL};
157 struct node third = {NULL};
159 CU_ASSERT_PTR_EQUAL(cx_linked_list_size(NULL, loc), 0)
160 CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&first, loc), 1)
161 first.next = &second;
162 CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&first, loc), 2)
163 second.next = &third;
164 CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&first, loc), 3)
165 CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&second, loc), 2)
166 }
168 void test_linked_list_sort(void) {
169 struct node {
170 void *prev;
171 void *next;
172 int data;
173 };
175 int expected[] = {
176 14, 30, 151, 163, 227, 300, 315, 317, 363, 398, 417, 424, 438, 446, 508, 555, 605, 713, 716, 759, 761, 880,
177 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 1707, 1734, 1771, 1874, 1894,
178 1976, 2079, 2124, 2130, 2135, 2266, 2338, 2358, 2430, 2500, 2540, 2542, 2546, 2711, 2733, 2754, 2764, 2797,
179 2888, 2900, 3020, 3053, 3109, 3244, 3275, 3302, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 3675, 3677,
180 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681,
181 4785, 4791, 4801, 4859, 4903, 4973
182 };
183 int scrambled[] = {
184 759, 716, 880, 761, 2358, 2542, 2500, 2540, 2546, 2711, 2430, 1707, 1874, 1771, 1894, 1734, 1976, 2079,
185 2124, 2130, 2135, 2266, 2338, 2733, 2754, 2764, 2797, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 2888,
186 2900, 3020, 3053, 3109, 3244, 3275, 3302, 438, 446, 508, 555, 605, 713, 14, 30, 151, 163, 227, 300,
187 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 315, 317, 363, 398, 417, 424,
188 3675, 3677, 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4785, 4791, 4801, 4859, 4903, 4973,
189 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681
190 };
192 struct node *nodes = calloc(100, sizeof(struct node));
193 for (int i = 0; i < 100; i++) {
194 nodes[i].prev = i == 0 ? NULL : &nodes[i - 1];
195 nodes[i].next = i == 99 ? NULL : &nodes[i + 1];
196 nodes[i].data = scrambled[i];
197 }
199 struct node *begin = &nodes[0];
200 struct node *end = &nodes[99];
202 cx_linked_list_sort((void **) &begin, (void **) &end,
203 offsetof(struct node, prev),
204 offsetof(struct node, next),
205 offsetof(struct node, data),
206 0, (CxListComparator) cmp_int);
208 CU_ASSERT_PTR_NULL(begin->prev)
209 CU_ASSERT_EQUAL(begin->data, expected[0])
210 struct node *check = begin;
211 struct node *check_last = NULL;
212 for (int i = 0 ; i < 100 ; i++) {
213 CU_ASSERT_EQUAL(check->data, expected[i])
214 CU_ASSERT_PTR_EQUAL(check->prev, check_last)
215 if (i < 99) {
216 CU_ASSERT_PTR_NOT_NULL(check->next)
217 }
218 check_last = check;
219 check = check->next;
220 }
221 CU_ASSERT_PTR_NULL(check)
222 CU_ASSERT_EQUAL(end->data, expected[99])
223 }
226 void test_hl_linked_list_create(void) {
227 cxTestingAllocatorReset();
229 CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
231 CU_ASSERT_EQUAL(list->size, 0)
232 CU_ASSERT_EQUAL(list->capacity, (size_t) -1)
233 CU_ASSERT_PTR_EQUAL(list->allocator, cxTestingAllocator)
234 CU_ASSERT_EQUAL(list->itemsize, sizeof(int))
235 CU_ASSERT_PTR_EQUAL(list->cmpfunc, cmp_int)
237 cxLinkedListDestroy(list);
238 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
239 }
241 void test_hl_linked_list_add(void) {
242 cxTestingAllocatorReset();
244 int data;
245 CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
247 data = 5;
248 CU_ASSERT_EQUAL(cxListAdd(list, &data), 0)
249 data = 47;
250 CU_ASSERT_EQUAL(cxListAdd(list, &data), 0)
251 data = 13;
252 CU_ASSERT_EQUAL(cxListAdd(list, &data), 0)
254 CU_ASSERT_EQUAL(list->size, 3)
255 CU_ASSERT_TRUE(list->capacity >= list->size)
257 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
258 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
259 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
261 cxLinkedListDestroy(list);
262 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
263 }
265 void test_hl_linked_list_last(void) {
266 cxTestingAllocatorReset();
268 int data;
269 CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
271 CU_ASSERT_PTR_NULL(cxListLast(list))
273 data = 5;
274 CU_ASSERT_EQUAL(cxListAdd(list, &data), 0)
275 CU_ASSERT_EQUAL(*(int *) cxListLast(list), 5)
277 data = 47;
278 CU_ASSERT_EQUAL(cxListAdd(list, &data), 0)
279 CU_ASSERT_EQUAL(*(int *) cxListLast(list), 47)
281 cxLinkedListDestroy(list);
282 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
283 }
285 void test_hl_linked_list_insert(void) {
286 cxTestingAllocatorReset();
288 int data;
289 CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
291 data = 5;
292 CU_ASSERT_NOT_EQUAL(cxListInsert(list, 1, &data), 0)
293 CU_ASSERT_EQUAL(list->size, 0)
294 CU_ASSERT_EQUAL(cxListInsert(list, 0, &data), 0)
295 CU_ASSERT_EQUAL(list->size, 1)
296 data = 47;
297 CU_ASSERT_EQUAL(cxListInsert(list, 0, &data), 0)
298 CU_ASSERT_EQUAL(list->size, 2)
299 data = 13;
300 CU_ASSERT_EQUAL(cxListInsert(list, 1, &data), 0)
301 CU_ASSERT_EQUAL(list->size, 3)
302 data = 42;
303 CU_ASSERT_EQUAL(cxListInsert(list, 3, &data), 0)
305 CU_ASSERT_EQUAL(list->size, 4)
306 CU_ASSERT_TRUE(list->capacity >= list->size)
308 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
309 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
310 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 5)
311 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 3), 42)
313 cxLinkedListDestroy(list);
314 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
315 }
317 void test_hl_linked_list_remove(void) {
318 cxTestingAllocatorReset();
320 int data;
321 CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
323 data = 5;
324 cxListAdd(list, &data);
325 data = 47;
326 cxListAdd(list, &data);
327 data = 42;
328 cxListAdd(list, &data);
329 data = 13;
330 cxListAdd(list, &data);
332 CU_ASSERT_EQUAL(list->size, 4)
333 CU_ASSERT_TRUE(list->capacity >= list->size)
335 CU_ASSERT_NOT_EQUAL(cxListRemove(list, 4), 0)
337 CU_ASSERT_EQUAL(cxListRemove(list, 2), 0)
338 CU_ASSERT_EQUAL(list->size, 3)
339 CU_ASSERT_TRUE(list->capacity >= list->size)
340 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
341 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
342 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
344 CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
345 CU_ASSERT_EQUAL(list->size, 2)
346 CU_ASSERT_TRUE(list->capacity >= list->size)
347 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
348 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
350 CU_ASSERT_EQUAL(cxListRemove(list, 1), 0)
351 CU_ASSERT_EQUAL(list->size, 1)
352 CU_ASSERT_TRUE(list->capacity >= list->size)
353 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
355 CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
356 CU_ASSERT_EQUAL(list->size, 0)
357 CU_ASSERT_TRUE(list->capacity >= list->size)
359 CU_ASSERT_NOT_EQUAL(cxListRemove(list, 0), 0)
361 cxLinkedListDestroy(list);
362 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
363 }
365 void test_hl_linked_list_find(void) {
366 cxTestingAllocatorReset();
368 int data, criteria;
369 CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
371 data = 5;
372 cxListAdd(list, &data);
373 data = 47;
374 cxListAdd(list, &data);
375 data = 13;
376 cxListAdd(list, &data);
378 CU_ASSERT_EQUAL(list->size, 3)
379 CU_ASSERT_TRUE(list->capacity >= list->size)
381 criteria = 5;
382 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 0)
383 criteria = 47;
384 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 1)
385 criteria = 13;
386 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 2)
387 criteria = 9000;
388 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 3)
389 criteria = -5;
390 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 3)
392 cxLinkedListDestroy(list);
393 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
394 }
396 void test_hl_linked_list_sort(void) {
397 int expected[] = {
398 14, 30, 151, 163, 227, 300, 315, 317, 363, 398, 417, 424, 438, 446, 508, 555, 605, 713, 716, 759, 761, 880,
399 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 1707, 1734, 1771, 1874, 1894,
400 1976, 2079, 2124, 2130, 2135, 2266, 2338, 2358, 2430, 2500, 2540, 2542, 2546, 2711, 2733, 2754, 2764, 2797,
401 2888, 2900, 3020, 3053, 3109, 3244, 3275, 3302, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 3675, 3677,
402 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681,
403 4785, 4791, 4801, 4859, 4903, 4973
404 };
405 int scrambled[] = {
406 759, 716, 880, 761, 2358, 2542, 2500, 2540, 2546, 2711, 2430, 1707, 1874, 1771, 1894, 1734, 1976, 2079,
407 2124, 2130, 2135, 2266, 2338, 2733, 2754, 2764, 2797, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 2888,
408 2900, 3020, 3053, 3109, 3244, 3275, 3302, 438, 446, 508, 555, 605, 713, 14, 30, 151, 163, 227, 300,
409 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 315, 317, 363, 398, 417, 424,
410 3675, 3677, 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4785, 4791, 4801, 4859, 4903, 4973,
411 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681
412 };
414 cxTestingAllocatorReset();
416 CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
418 for (int i = 0 ; i < 100 ; i++) {
419 cxListAdd(list, &scrambled[i]);
420 }
422 cxListSort(list);
424 for (int i = 0 ; i < 100 ; i++) {
425 CU_ASSERT_EQUAL(*(int*)cxListAt(list, i), expected[i])
426 }
428 cxLinkedListDestroy(list);
429 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
430 }
432 void test_hl_ptr_linked_list_create(void) {
433 cxTestingAllocatorReset();
435 CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
437 CU_ASSERT_EQUAL(list->size, 0)
438 CU_ASSERT_EQUAL(list->capacity, (size_t) -1)
439 CU_ASSERT_PTR_EQUAL(list->allocator, cxTestingAllocator)
440 CU_ASSERT_EQUAL(list->itemsize, sizeof(void *))
441 CU_ASSERT_PTR_EQUAL(list->cmpfunc, cmp_int)
443 cxLinkedListDestroy(list);
444 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
445 }
447 void test_hl_ptr_linked_list_add(void) {
448 cxTestingAllocatorReset();
450 CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
452 int a = 5, b = 47, c = 13;
454 CU_ASSERT_EQUAL(cxListAdd(list, &a), 0)
455 CU_ASSERT_EQUAL(cxListAdd(list, &b), 0)
456 CU_ASSERT_EQUAL(cxListAdd(list, &c), 0)
458 CU_ASSERT_EQUAL(list->size, 3)
459 CU_ASSERT_TRUE(list->capacity >= list->size)
461 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
462 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
463 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
465 a = 9;
466 b = 10;
467 c = 11;
469 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 9)
470 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 10)
471 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 11)
473 cxLinkedListDestroy(list);
474 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
475 }
477 void test_hl_ptr_linked_list_last(void) {
478 cxTestingAllocatorReset();
480 CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
481 CU_ASSERT_PTR_NULL(cxListLast(list))
483 int a = 5, b = 47;
485 CU_ASSERT_EQUAL(cxListAdd(list, &a), 0)
486 CU_ASSERT_EQUAL(*(int *) cxListLast(list), 5)
487 CU_ASSERT_EQUAL(cxListAdd(list, &b), 0)
488 CU_ASSERT_EQUAL(*(int *) cxListLast(list), 47)
490 cxLinkedListDestroy(list);
491 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
492 }
494 void test_hl_ptr_linked_list_insert(void) {
495 cxTestingAllocatorReset();
497 CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
499 int a = 5, b = 47, c = 13, d = 42;
501 CU_ASSERT_NOT_EQUAL(cxListInsert(list, 1, &a), 0)
502 CU_ASSERT_EQUAL(list->size, 0)
503 CU_ASSERT_EQUAL(cxListInsert(list, 0, &a), 0)
504 CU_ASSERT_EQUAL(list->size, 1)
505 CU_ASSERT_EQUAL(cxListInsert(list, 0, &b), 0)
506 CU_ASSERT_EQUAL(list->size, 2)
507 CU_ASSERT_EQUAL(cxListInsert(list, 1, &c), 0)
508 CU_ASSERT_EQUAL(list->size, 3)
509 CU_ASSERT_EQUAL(cxListInsert(list, 3, &d), 0)
511 CU_ASSERT_EQUAL(list->size, 4)
512 CU_ASSERT_TRUE(list->capacity >= list->size)
514 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
515 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
516 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 5)
517 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 3), 42)
519 cxLinkedListDestroy(list);
520 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
521 }
523 void test_hl_ptr_linked_list_remove(void) {
524 cxTestingAllocatorReset();
526 int a = 5, b = 47, c = 42, d = 13;
527 CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
529 cxListAdd(list, &a);
530 cxListAdd(list, &b);
531 cxListAdd(list, &c);
532 cxListAdd(list, &d);
534 CU_ASSERT_EQUAL(list->size, 4)
535 CU_ASSERT_TRUE(list->capacity >= list->size)
537 CU_ASSERT_NOT_EQUAL(cxListRemove(list, 4), 0)
539 CU_ASSERT_EQUAL(cxListRemove(list, 2), 0)
540 CU_ASSERT_EQUAL(list->size, 3)
541 CU_ASSERT_TRUE(list->capacity >= list->size)
542 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
543 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
544 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
546 CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
547 CU_ASSERT_EQUAL(list->size, 2)
548 CU_ASSERT_TRUE(list->capacity >= list->size)
549 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
550 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
552 CU_ASSERT_EQUAL(cxListRemove(list, 1), 0)
553 CU_ASSERT_EQUAL(list->size, 1)
554 CU_ASSERT_TRUE(list->capacity >= list->size)
555 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
557 CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
558 CU_ASSERT_EQUAL(list->size, 0)
559 CU_ASSERT_TRUE(list->capacity >= list->size)
561 CU_ASSERT_NOT_EQUAL(cxListRemove(list, 0), 0)
563 cxLinkedListDestroy(list);
564 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
565 }
567 void test_hl_ptr_linked_list_find(void) {
568 cxTestingAllocatorReset();
570 int a = 5, b = 47, c = 13, criteria;
571 CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
573 cxListAdd(list, &a);
574 cxListAdd(list, &b);
575 cxListAdd(list, &c);
577 CU_ASSERT_EQUAL(list->size, 3)
578 CU_ASSERT_TRUE(list->capacity >= list->size)
580 criteria = 5;
581 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 0)
582 criteria = 47;
583 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 1)
584 criteria = 13;
585 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 2)
586 criteria = 9000;
587 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 3)
588 criteria = -5;
589 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 3)
590 b = -5;
591 CU_ASSERT_EQUAL(cxListFind(list, &criteria), 1)
593 cxLinkedListDestroy(list);
594 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
595 }
597 void test_hl_ptr_linked_list_sort(void) {
598 int expected[] = {
599 14, 30, 151, 163, 227, 300, 315, 317, 363, 398, 417, 424, 438, 446, 508, 555, 605, 713, 716, 759, 761, 880,
600 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 1707, 1734, 1771, 1874, 1894,
601 1976, 2079, 2124, 2130, 2135, 2266, 2338, 2358, 2430, 2500, 2540, 2542, 2546, 2711, 2733, 2754, 2764, 2797,
602 2888, 2900, 3020, 3053, 3109, 3244, 3275, 3302, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 3675, 3677,
603 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681,
604 4785, 4791, 4801, 4859, 4903, 4973
605 };
606 int scrambled[] = {
607 759, 716, 880, 761, 2358, 2542, 2500, 2540, 2546, 2711, 2430, 1707, 1874, 1771, 1894, 1734, 1976, 2079,
608 2124, 2130, 2135, 2266, 2338, 2733, 2754, 2764, 2797, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 2888,
609 2900, 3020, 3053, 3109, 3244, 3275, 3302, 438, 446, 508, 555, 605, 713, 14, 30, 151, 163, 227, 300,
610 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 315, 317, 363, 398, 417, 424,
611 3675, 3677, 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4785, 4791, 4801, 4859, 4903, 4973,
612 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681
613 };
615 cxTestingAllocatorReset();
617 CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
619 for (int i = 0 ; i < 100 ; i++) {
620 cxListAdd(list, &scrambled[i]);
621 }
623 cxListSort(list);
625 for (int i = 0 ; i < 100 ; i++) {
626 CU_ASSERT_EQUAL(*(int*)cxListAt(list, i), expected[i])
627 }
629 cxLinkedListDestroy(list);
630 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
631 }
633 int main() {
634 CU_pSuite suite = NULL;
636 if (CUE_SUCCESS != CU_initialize_registry()) {
637 return CU_get_error();
638 }
640 suite = CU_add_suite("low level linked list", NULL, NULL);
642 cu_add_test(suite, test_linked_list_at);
643 cu_add_test(suite, test_linked_list_add);
644 cu_add_test(suite, test_linked_list_last);
645 cu_add_test(suite, test_linked_list_size);
646 cu_add_test(suite, test_linked_list_sort);
648 suite = CU_add_suite("high level linked list", NULL, NULL);
650 cu_add_test(suite, test_hl_linked_list_create);
651 cu_add_test(suite, test_hl_linked_list_add);
652 cu_add_test(suite, test_hl_linked_list_last);
653 cu_add_test(suite, test_hl_linked_list_insert);
654 cu_add_test(suite, test_hl_linked_list_remove);
655 cu_add_test(suite, test_hl_linked_list_find);
656 cu_add_test(suite, test_hl_linked_list_sort);
658 suite = CU_add_suite("high level pointer linked list", NULL, NULL);
660 cu_add_test(suite, test_hl_ptr_linked_list_create);
661 cu_add_test(suite, test_hl_ptr_linked_list_add);
662 cu_add_test(suite, test_hl_ptr_linked_list_last);
663 cu_add_test(suite, test_hl_ptr_linked_list_insert);
664 cu_add_test(suite, test_hl_ptr_linked_list_remove);
665 cu_add_test(suite, test_hl_ptr_linked_list_find);
666 cu_add_test(suite, test_hl_ptr_linked_list_sort);
668 CU_basic_set_mode(UCX_CU_BRM);
670 int exitcode;
671 if (CU_basic_run_tests()) {
672 exitcode = CU_get_error();
673 } else {
674 exitcode = CU_get_number_of_failures() == 0 ? 0 : 1;
675 }
676 CU_cleanup_registry();
677 return exitcode;
678 }
