Mercurial > hg > ucx / file comparison

comparison: tests/test_list.c

tests/test_list.c

changeset 798
7644da6e2d35
child 799
a2a757d225b4
equal deleted inserted replaced
797:e0300c2c4e95 798:7644da6e2d35
1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
3 *
4 * Copyright 2023 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 */
28
29 #include "cx/test.h"
30 #include "util_allocator.h"
31 #include "cx/compare.h"
32
33 #include "cx/array_list.h"
34 #include "cx/linked_list.h"
35
36 #include <stdarg.h>
37
38 typedef struct node {
39 struct node *next;
40 struct node *prev;
41 int data;
42 } node;
43
44 const ptrdiff_t loc_prev = offsetof(struct node, prev);
45 const ptrdiff_t loc_next = offsetof(struct node, next);
46 const ptrdiff_t loc_data = offsetof(struct node, data);
47
48 static node *create_nodes_test_data(size_t len) {
49 node *begin = calloc(1, sizeof(node));
50 void *prev = begin;
51 for (size_t i = 1; i < len; i++) {
52 node *n = calloc(1, sizeof(node));
53 cx_linked_list_link(prev, n, loc_prev, loc_next);
54 prev = n;
55 }
56 return begin;
57 }
58
59 void assign_nodes_test_data(node *n, ...) {
60 va_list ap;
61 va_start(ap, n);
62 while (n != NULL) {
63 n->data = va_arg(ap, int);
64 n = n->next;
65 }
66 va_end(ap);
67 }
68
69 static void destroy_nodes_test_data(node *n) {
70 while (n != NULL) {
71 void *next = n->next;
72 free(n);
73 n = next;
74 }
75 }
76
77 static int *int_test_data(size_t len) {
78 int *data = malloc(len*sizeof(int));
79 for (size_t i = 0 ; i < len ; i++) {
80 data[i] = rand(); // NOLINT(*-msc50-cpp)
81 }
82 return data;
83 }
84
85 CX_TEST(test_linked_list_link_unlink) {
86 node a = {0}, b = {0}, c = {0};
87
88 CX_TEST_DO {
89 cx_linked_list_link(&a, &b, loc_prev, loc_next);
90 CX_TEST_ASSERT(a.prev == NULL);
91 CX_TEST_ASSERT(a.next == &b);
92 CX_TEST_ASSERT(b.prev == &a);
93 CX_TEST_ASSERT(b.next == NULL);
94
95 cx_linked_list_unlink(&a, &b, loc_prev, loc_next);
96 CX_TEST_ASSERT(a.prev == NULL);
97 CX_TEST_ASSERT(a.next == NULL);
98 CX_TEST_ASSERT(b.prev == NULL);
99 CX_TEST_ASSERT(b.next == NULL);
100
101 cx_linked_list_link(&b, &c, loc_prev, loc_next);
102 cx_linked_list_link(&a, &b, loc_prev, loc_next);
103 cx_linked_list_unlink(&b, &c, loc_prev, loc_next);
104 CX_TEST_ASSERT(a.prev == NULL);
105 CX_TEST_ASSERT(a.next == &b);
106 CX_TEST_ASSERT(b.prev == &a);
107 CX_TEST_ASSERT(b.next == NULL);
108 CX_TEST_ASSERT(c.prev == NULL);
109 CX_TEST_ASSERT(c.next == NULL);
110 }
111 }
112
113 CX_TEST(test_linked_list_at) {
114 node a = {0}, b = {0}, c = {0}, d = {0};
115
116 cx_linked_list_link(&a, &b, loc_prev, loc_next);
117 cx_linked_list_link(&b, &c, loc_prev, loc_next);
118 cx_linked_list_link(&c, &d, loc_prev, loc_next);
119
120 CX_TEST_DO {
121 CX_TEST_ASSERT(cx_linked_list_at(&a, 0, loc_next, 0) == &a);
122 CX_TEST_ASSERT(cx_linked_list_at(&a, 0, loc_next, 1) == &b);
123 CX_TEST_ASSERT(cx_linked_list_at(&a, 0, loc_next, 2) == &c);
124 CX_TEST_ASSERT(cx_linked_list_at(&a, 0, loc_next, 3) == &d);
125 CX_TEST_ASSERT(cx_linked_list_at(&a, 0, loc_next, 4) == NULL);
126 CX_TEST_ASSERT(cx_linked_list_at(&b, 1, loc_prev, 0) == &a);
127 CX_TEST_ASSERT(cx_linked_list_at(&b, 1, loc_next, 1) == &b);
128 CX_TEST_ASSERT(cx_linked_list_at(&b, 1, loc_next, 2) == &c);
129 CX_TEST_ASSERT(cx_linked_list_at(&b, 1, loc_next, 3) == &d);
130 CX_TEST_ASSERT(cx_linked_list_at(&b, 1, loc_next, 4) == NULL);
131 CX_TEST_ASSERT(cx_linked_list_at(&d, 3, loc_prev, 0) == &a);
132 CX_TEST_ASSERT(cx_linked_list_at(&d, 3, loc_prev, 1) == &b);
133 }
134 }
135
136 CX_TEST(test_linked_list_find) {
137 void *list = create_nodes_test_data(4);
138 assign_nodes_test_data(list, 2, 4, 6, 8);
139 CX_TEST_DO {
140 int s;
141 s = 2;
142 CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s) == 0);
143 s = 4;
144 CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s) == 1);
145 s = 6;
146 CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s) == 2);
147 s = 8;
148 CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s) == 3);
149 s = 10;
150 CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s) < 0);
151 s = -2;
152 CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s) < 0);
153 }
154 destroy_nodes_test_data(list);
155 }
156
157 CX_TEST(test_linked_list_compare) {
158 void *la = create_nodes_test_data(4);
159 void *lb = create_nodes_test_data(3);
160 void *lc = create_nodes_test_data(4);
161 assign_nodes_test_data(la, 2, 4, 6, 8);
162 assign_nodes_test_data(lb, 2, 4, 6);
163 assign_nodes_test_data(lc, 2, 4, 6, 9);
164 CX_TEST_DO {
165 CX_TEST_ASSERT(cx_linked_list_compare(la, lb, loc_next, loc_data, cx_cmp_int) > 0);
166 CX_TEST_ASSERT(cx_linked_list_compare(lb, la, loc_next, loc_data, cx_cmp_int) < 0);
167 CX_TEST_ASSERT(cx_linked_list_compare(lc, la, loc_next, loc_data, cx_cmp_int) > 0);
168 CX_TEST_ASSERT(cx_linked_list_compare(la, lc, loc_next, loc_data, cx_cmp_int) < 0);
169 CX_TEST_ASSERT(cx_linked_list_compare(la, la, loc_next, loc_data, cx_cmp_int) == 0);
170 }
171 destroy_nodes_test_data(la);
172 destroy_nodes_test_data(lb);
173 destroy_nodes_test_data(lc);
174 }
175
176 CX_TEST(test_linked_list_add) {
177 node nodes[4];
178 void *begin, *end;
179 CX_TEST_DO {
180 // test with begin, end / prev, next
181 memset(nodes, 0, sizeof(node)*4);
182 end = begin = NULL;
183
184 cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[0]);
185 CX_TEST_ASSERT(begin == &nodes[0]);
186 CX_TEST_ASSERT(end == &nodes[0]);
187 CX_TEST_ASSERT(nodes[0].prev == NULL);
188 CX_TEST_ASSERT(nodes[0].next == NULL);
189
190 cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[1]);
191 CX_TEST_ASSERT(begin == &nodes[0]);
192 CX_TEST_ASSERT(end == &nodes[1]);
193 CX_TEST_ASSERT(nodes[0].next == &nodes[1]);
194 CX_TEST_ASSERT(nodes[1].prev == &nodes[0]);
195
196 // test with begin only / prev, next
197 memset(nodes, 0, sizeof(node)*4);
198 end = begin = NULL;
199
200 cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[0]);
201 CX_TEST_ASSERT(begin == &nodes[0]);
202 cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[1]);
203 CX_TEST_ASSERT(begin == &nodes[0]);
204 CX_TEST_ASSERT(nodes[0].next == &nodes[1]);
205 CX_TEST_ASSERT(nodes[1].prev == &nodes[0]);
206
207 cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[2]);
208 CX_TEST_ASSERT(nodes[1].next == &nodes[2]);
209 CX_TEST_ASSERT(nodes[2].prev == &nodes[1]);
210
211 // test with end only / prev, next
212 memset(nodes, 0, sizeof(node)*4);
213 end = begin = NULL;
214
215 cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[0]);
216 CX_TEST_ASSERT(end == &nodes[0]);
217 cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[1]);
218 CX_TEST_ASSERT(end == &nodes[1]);
219 CX_TEST_ASSERT(nodes[0].next == &nodes[1]);
220 CX_TEST_ASSERT(nodes[1].prev == &nodes[0]);
221
222 cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[2]);
223 CX_TEST_ASSERT(end == &nodes[2]);
224 CX_TEST_ASSERT(nodes[1].next == &nodes[2]);
225 CX_TEST_ASSERT(nodes[2].prev == &nodes[1]);
226
227 // test with begin, end / next
228 memset(nodes, 0, sizeof(node)*4);
229 end = begin = NULL;
230
231 cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[0]);
232 CX_TEST_ASSERT(begin == &nodes[0]);
233 CX_TEST_ASSERT(end == &nodes[0]);
234 cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[1]);
235 CX_TEST_ASSERT(end == &nodes[1]);
236 CX_TEST_ASSERT(nodes[0].next == &nodes[1]);
237 CX_TEST_ASSERT(nodes[1].prev == NULL);
238 }
239 }
240
241 CX_TEST(test_linked_list_prepend) {
242 node nodes[4];
243 void *begin, *end;
244 CX_TEST_DO {
245 // test with begin, end / prev, next
246 memset(nodes, 0, sizeof(node) * 4);
247 end = begin = NULL;
248
249 cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[0]);
250 CX_TEST_ASSERT(begin == &nodes[0]);
251 CX_TEST_ASSERT(end == &nodes[0]);
252 CX_TEST_ASSERT(nodes[0].prev == NULL);
253 CX_TEST_ASSERT(nodes[0].next == NULL);
254
255 cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[1]);
256 CX_TEST_ASSERT(begin == &nodes[1]);
257 CX_TEST_ASSERT(end == &nodes[0]);
258 CX_TEST_ASSERT(nodes[1].next == &nodes[0]);
259 CX_TEST_ASSERT(nodes[0].prev == &nodes[1]);
260
261 // test with begin only / prev, next
262 memset(nodes, 0, sizeof(node) * 4);
263 end = begin = NULL;
264
265 cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[0]);
266 CX_TEST_ASSERT(begin == &nodes[0]);
267 cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[1]);
268 CX_TEST_ASSERT(begin == &nodes[1]);
269 CX_TEST_ASSERT(nodes[1].next == &nodes[0]);
270 CX_TEST_ASSERT(nodes[0].prev == &nodes[1]);
271
272 cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[2]);
273 CX_TEST_ASSERT(begin == &nodes[2]);
274 CX_TEST_ASSERT(nodes[2].next == &nodes[1]);
275 CX_TEST_ASSERT(nodes[1].prev == &nodes[2]);
276
277 // test with end only / prev, next
278 memset(nodes, 0, sizeof(node) * 4);
279 end = begin = NULL;
280
281 cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[0]);
282 CX_TEST_ASSERT(end == &nodes[0]);
283 cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[1]);
284 CX_TEST_ASSERT(end == &nodes[0]);
285 CX_TEST_ASSERT(nodes[1].next == &nodes[0]);
286 CX_TEST_ASSERT(nodes[0].prev == &nodes[1]);
287
288 cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[2]);
289 CX_TEST_ASSERT(end == &nodes[0]);
290 CX_TEST_ASSERT(nodes[2].next == &nodes[1]);
291 CX_TEST_ASSERT(nodes[1].prev == &nodes[2]);
292
293 // test with begin, end / next
294 memset(nodes, 0, sizeof(node) * 4);
295 end = begin = NULL;
296
297 cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[0]);
298 CX_TEST_ASSERT(begin == &nodes[0]);
299 CX_TEST_ASSERT(end == &nodes[0]);
300 cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[1]);
301 cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[2]);
302 CX_TEST_ASSERT(begin == &nodes[2]);
303 CX_TEST_ASSERT(end == &nodes[0]);
304 CX_TEST_ASSERT(nodes[1].next == &nodes[0]);
305 CX_TEST_ASSERT(nodes[2].next == &nodes[1]);
306 CX_TEST_ASSERT(nodes[1].prev == NULL);
307 CX_TEST_ASSERT(nodes[0].prev == NULL);
308 }
309 }
310
311 CX_TEST(test_linked_list_insert) {
312 node nodes[4];
313 void *begin, *end;
314 CX_TEST_DO {
315 // insert mid list
316 memset(nodes, 0, sizeof(node) * 4);
317 begin = &nodes[0];
318 end = &nodes[2];
319
320 cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
321 cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
322
323 cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3]);
324 CX_TEST_ASSERT(begin == &nodes[0]);
325 CX_TEST_ASSERT(end == &nodes[2]);
326 CX_TEST_ASSERT(nodes[1].next == &nodes[3]);
327 CX_TEST_ASSERT(nodes[2].prev == &nodes[3]);
328 CX_TEST_ASSERT(nodes[3].prev == &nodes[1]);
329 CX_TEST_ASSERT(nodes[3].next == &nodes[2]);
330
331 // insert end
332 memset(nodes, 0, sizeof(node) * 4);
333 begin = &nodes[0];
334 end = &nodes[2];
335
336 cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
337 cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
338
339 cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3]);
340 CX_TEST_ASSERT(begin == &nodes[0]);
341 CX_TEST_ASSERT(end == &nodes[3]);
342 CX_TEST_ASSERT(nodes[2].next == &nodes[3]);
343 CX_TEST_ASSERT(nodes[3].prev == &nodes[2]);
344 CX_TEST_ASSERT(nodes[3].next == NULL);
345
346 // insert begin
347 memset(nodes, 0, sizeof(node) * 4);
348 begin = &nodes[0];
349 end = &nodes[2];
350
351 cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
352 cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
353
354 cx_linked_list_insert(&begin, &end, loc_prev, loc_next, NULL, &nodes[3]);
355 CX_TEST_ASSERT(begin == &nodes[3]);
356 CX_TEST_ASSERT(end == &nodes[2]);
357 CX_TEST_ASSERT(nodes[0].prev == &nodes[3]);
358 CX_TEST_ASSERT(nodes[3].prev == NULL);
359 CX_TEST_ASSERT(nodes[3].next == &nodes[0]);
360 }
361 }
362
363 CX_TEST(test_linked_list_insert_chain) {
364 node nodes[5];
365 void *begin, *end;
366 CX_TEST_DO {
367 // insert mid list
368 memset(nodes, 0, sizeof(node) * 5);
369 begin = &nodes[0]; end = &nodes[2];
370
371 cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
372 cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
373 cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next);
374
375 cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3], NULL);
376 CX_TEST_ASSERT(begin == &nodes[0]);
377 CX_TEST_ASSERT(end == &nodes[2]);
378 CX_TEST_ASSERT(nodes[1].next == &nodes[3]);
379 CX_TEST_ASSERT(nodes[2].prev == &nodes[4]);
380 CX_TEST_ASSERT(nodes[3].prev == &nodes[1]);
381 CX_TEST_ASSERT(nodes[4].next == &nodes[2]);
382
383 // insert end
384 memset(nodes, 0, sizeof(node) * 5);
385 begin = &nodes[0]; end = &nodes[2];
386
387 cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
388 cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
389 cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next);
390
391 cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3], NULL);
392 CX_TEST_ASSERT(begin == &nodes[0]);
393 CX_TEST_ASSERT(end == &nodes[4]);
394 CX_TEST_ASSERT(nodes[2].next == &nodes[3]);
395 CX_TEST_ASSERT(nodes[3].prev == &nodes[2]);
396 CX_TEST_ASSERT(nodes[4].next == NULL);
397
398 // insert begin
399 memset(nodes, 0, sizeof(node) * 5);
400 begin = &nodes[0]; end = &nodes[2];
401
402 cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
403 cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
404 cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next);
405
406 cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, NULL, &nodes[3], NULL);
407 CX_TEST_ASSERT(begin == &nodes[3]);
408 CX_TEST_ASSERT(end == &nodes[2]);
409 CX_TEST_ASSERT(nodes[0].prev == &nodes[4]);
410 CX_TEST_ASSERT(nodes[3].prev == NULL);
411 CX_TEST_ASSERT(nodes[4].next == &nodes[0]);
412 }
413 }
414
415 CX_TEST(test_linked_list_first) {
416 node *testdata = create_nodes_test_data(3);
417 void *begin = testdata;
418 CX_TEST_DO {
419 CX_TEST_ASSERT(begin == cx_linked_list_first(testdata, loc_prev));
420 CX_TEST_ASSERT(begin == cx_linked_list_first(testdata->next, loc_prev));
421 CX_TEST_ASSERT(begin == cx_linked_list_first(testdata->next->next, loc_prev));
422 }
423 destroy_nodes_test_data(testdata);
424 }
425
426 CX_TEST(test_linked_list_last) {
427 node *testdata = create_nodes_test_data(3);
428 void *end = testdata->next->next;
429 CX_TEST_DO {
430 CX_TEST_ASSERT(end == cx_linked_list_last(testdata, loc_next));
431 CX_TEST_ASSERT(end == cx_linked_list_last(testdata->next, loc_next));
432 CX_TEST_ASSERT(end == cx_linked_list_last(testdata->next->next, loc_next));
433 }
434 destroy_nodes_test_data(testdata);
435 }
436
437 CX_TEST(test_linked_list_prev) {
438 node *testdata = create_nodes_test_data(3);
439 CX_TEST_DO {
440 CX_TEST_ASSERT(cx_linked_list_prev(testdata, loc_next, testdata) == NULL);
441 CX_TEST_ASSERT(cx_linked_list_prev(testdata, loc_next, testdata->next) == testdata);
442 CX_TEST_ASSERT(cx_linked_list_prev(testdata, loc_next, testdata->next->next) == testdata->next);
443 }
444 destroy_nodes_test_data(testdata);
445 }
446
447 CX_TEST(test_linked_list_remove) {
448 node *testdata = create_nodes_test_data(3);
449 assign_nodes_test_data(testdata, 2, 4, 6);
450 node *first = testdata;
451 node *second = first->next;
452 node *third = second->next;
453 void *begin = testdata;
454 void *end = third;
455
456 CX_TEST_DO {
457 cx_linked_list_remove(&begin, &end, loc_prev, loc_next, second);
458 CX_TEST_ASSERT(begin == first);
459 CX_TEST_ASSERT(end == third);
460 CX_TEST_ASSERT(first->prev == NULL);
461 CX_TEST_ASSERT(first->next == third);
462 CX_TEST_ASSERT(third->prev == first);
463 CX_TEST_ASSERT(third->next == NULL);
464
465 cx_linked_list_remove(&begin, &end, loc_prev, loc_next, third);
466 CX_TEST_ASSERT(begin == first);
467 CX_TEST_ASSERT(end == first);
468 CX_TEST_ASSERT(first->prev == NULL);
469 CX_TEST_ASSERT(first->next == NULL);
470
471 cx_linked_list_remove(&begin, &end, loc_prev, loc_next, first);
472 CX_TEST_ASSERT(begin == NULL);
473 CX_TEST_ASSERT(end == NULL);
474 }
475 // list is not intact anymore, we have to free nodes individually
476 free(first);
477 free(second);
478 free(third);
479 }
480
481 CX_TEST(test_linked_list_size) {
482 node *td5 = create_nodes_test_data(5);
483 node *td13 = create_nodes_test_data(13);
484 CX_TEST_DO {
485 CX_TEST_ASSERT(cx_linked_list_size(NULL, loc_next) == 0);
486 CX_TEST_ASSERT(cx_linked_list_size(td5, loc_next) == 5);
487 CX_TEST_ASSERT(cx_linked_list_size(td13, loc_next) == 13);
488 }
489 destroy_nodes_test_data(td5);
490 destroy_nodes_test_data(td13);
491 }
492
493 CX_TEST(test_linked_list_sort_empty) {
494 void *begin = NULL;
495 // cannot assert something, we can just test that it does not crash
496 cx_linked_list_sort(&begin, NULL, loc_prev, loc_next, loc_data, cx_cmp_int);
497 }
498
499 CX_TEST(test_linked_list_sort) {
500 const size_t len = 1500;
501 int *testdata = int_test_data(len);
502 void *scrambled = create_nodes_test_data(len);
503 node *n = scrambled;
504 for (size_t i = 0; i < len; i++) {
505 n->data = testdata[i];
506 n = n->next;
507 }
508 int *sorted = malloc(len*sizeof(int));
509 memcpy(sorted, testdata, len*sizeof(int));
510 qsort(sorted, len, sizeof(int), cx_cmp_int);
511
512 void *begin = scrambled;
513 void *end = cx_linked_list_last(begin, loc_next);
514
515 CX_TEST_DO {
516 cx_linked_list_sort(&begin, &end, loc_prev, loc_next, loc_data, cx_cmp_int);
517 node *check = begin;
518 node *check_last = NULL;
519 for (size_t i = 0; i < len; i++) {
520 CX_TEST_ASSERT(check->data == sorted[i]);
521 CX_TEST_ASSERT(check->prev == check_last);
522 if (i < len - 1) {
523 CX_TEST_ASSERT(check->next != NULL);
524 }
525 check_last = check;
526 check = check->next;
527 }
528 CX_TEST_ASSERT(check == NULL);
529 CX_TEST_ASSERT(end == check_last);
530 }
531 free(scrambled);
532 free(testdata);
533 }
534
535 CX_TEST(test_linked_list_reverse) {
536 void *testdata = create_nodes_test_data(4);
537 void *expected = create_nodes_test_data(4);
538 assign_nodes_test_data(testdata, 2, 4, 6, 8);
539 assign_nodes_test_data(expected, 8, 6, 4, 2);
540 CX_TEST_DO {
541 void *begin = testdata;
542 void *end = cx_linked_list_last(begin, loc_next);
543 void *orig_begin = begin, *orig_end = end;
544
545 cx_linked_list_reverse(&begin, &end, loc_prev, loc_next);
546 CX_TEST_ASSERT(end == orig_begin);
547 CX_TEST_ASSERT(begin == orig_end);
548 CX_TEST_ASSERT(0 == cx_linked_list_compare(begin, expected, loc_next, loc_data, cx_cmp_int));
549 }
550 destroy_nodes_test_data(testdata);
551 destroy_nodes_test_data(expected);
552 }
553
554 CxTestSuite *cx_test_suite_array_list(void) {
555 CxTestSuite *suite = cx_test_suite_new("array_list");
556
557 return suite;
558 }
559
560 CxTestSuite *cx_test_suite_linked_list(void) {
561 CxTestSuite *suite = cx_test_suite_new("linked_list");
562
563 cx_test_register(suite, test_linked_list_link_unlink);
564 cx_test_register(suite, test_linked_list_at);
565 cx_test_register(suite, test_linked_list_find);
566 cx_test_register(suite, test_linked_list_compare);
567 cx_test_register(suite, test_linked_list_add);
568 cx_test_register(suite, test_linked_list_prepend);
569 cx_test_register(suite, test_linked_list_insert);
570 cx_test_register(suite, test_linked_list_insert_chain);
571 cx_test_register(suite, test_linked_list_first);
572 cx_test_register(suite, test_linked_list_last);
573 cx_test_register(suite, test_linked_list_prev);
574 cx_test_register(suite, test_linked_list_remove);
575 cx_test_register(suite, test_linked_list_size);
576 cx_test_register(suite, test_linked_list_sort_empty);
577 cx_test_register(suite, test_linked_list_sort);
578 cx_test_register(suite, test_linked_list_reverse);
579
580 return suite;
581 }
582

Mercurial Repository: ucx

mercurial