Mercurial > hg > ucx / file comparison

comparison: test/test_list.c

test/test_list.c

changeset 517
b3baaf9b7e3c
parent 516
7bcea73303ce
child 518
74d0372f5c6f
equal deleted inserted replaced
516:7bcea73303ce 517:b3baaf9b7e3c
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 */
28
29 #include "cx/linked_list.h"
30 #include "cx/utils.h"
31 #include "test_config.h"
32 #include "util_allocator.h"
33
34 static int cmp_int_impl(
35 int const *l,
36 int const *r
37 ) {
38 int left = *l, right = *r;
39 return left == right ? 0 : (left < right ? -1 : 1);
40 }
41
42 #define cmp_int ((CxListComparator) cmp_int_impl)
43
44 struct node {
45 struct node *next;
46 struct node *prev;
47 int data;
48 };
49
50 #define nd(name) name = {0}
51
52 const ptrdiff_t loc_prev = offsetof(struct node, prev);
53 const ptrdiff_t loc_next = offsetof(struct node, next);
54 const ptrdiff_t loc_data = offsetof(struct node, data);
55
56 static struct node *create_nodes_test_data(
57 size_t n,
58 int const data[]
59 ) {
60 CU_ASSERT_NOT_EQUAL_FATAL(n, 0)
61 struct node *begin = calloc(1, sizeof(struct node));
62 struct node *prev = begin;
63 if (data) begin->data = data[0];
64 for (size_t i = 1; i < n; i++) {
65 struct node *node = calloc(1, sizeof(struct node));
66 if (data) node->data = data[i];
67 cx_linked_list_link(prev, node, loc_prev, loc_next);
68 prev = node;
69 }
70 return begin;
71 }
72
73 static void destroy_nodes_test_data(struct node *begin) {
74 struct node *node = begin;
75 while (node) {
76 struct node *next = node->next;
77 free(node);
78 node = next;
79 }
80 }
81
82 static int *create_ints_test_data(size_t len) {
83 int *data = malloc(sizeof(int) * len);
84 cx_for_n (i, len) data[i] = rand(); // NOLINT(cert-msc50-cpp)
85 return data;
86 }
87
88 void test_linked_list_link_unlink(void) {
89
90 struct node nd(a), nd(b), nd(c);
91
92 cx_linked_list_link(&a, &b, loc_prev, loc_next);
93 CU_ASSERT_PTR_NULL(a.prev)
94 CU_ASSERT_PTR_EQUAL(a.next, &b)
95 CU_ASSERT_PTR_EQUAL(b.prev, &a)
96 CU_ASSERT_PTR_NULL(b.next)
97
98 cx_linked_list_unlink(&a, &b, loc_prev, loc_next);
99 CU_ASSERT_PTR_NULL(a.prev)
100 CU_ASSERT_PTR_NULL(a.next)
101 CU_ASSERT_PTR_NULL(b.prev)
102 CU_ASSERT_PTR_NULL(b.next)
103
104 cx_linked_list_link(&b, &c, loc_prev, loc_next);
105 cx_linked_list_link(&a, &b, loc_prev, loc_next);
106 cx_linked_list_unlink(&b, &c, loc_prev, loc_next);
107 CU_ASSERT_PTR_NULL(a.prev)
108 CU_ASSERT_PTR_EQUAL(a.next, &b)
109 CU_ASSERT_PTR_EQUAL(b.prev, &a)
110 CU_ASSERT_PTR_NULL(b.next)
111 CU_ASSERT_PTR_NULL(c.prev)
112 CU_ASSERT_PTR_NULL(c.next)
113 }
114
115 void test_linked_list_at(void) {
116 struct node nd(a), nd(b), nd(c), nd(d);
117 cx_linked_list_link(&a, &b, loc_prev, loc_next);
118 cx_linked_list_link(&b, &c, loc_prev, loc_next);
119 cx_linked_list_link(&c, &d, loc_prev, loc_next);
120
121 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&a, 0, loc_next, 0), &a)
122 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&a, 0, loc_next, 1), &b)
123 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&a, 0, loc_next, 2), &c)
124 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&a, 0, loc_next, 3), &d)
125 CU_ASSERT_PTR_NULL(cx_linked_list_at(&a, 0, loc_next, 4))
126
127 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&b, 1, loc_prev, 0), &a)
128 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&b, 1, loc_next, 1), &b)
129 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&b, 1, loc_next, 2), &c)
130 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&b, 1, loc_next, 3), &d)
131 CU_ASSERT_PTR_NULL(cx_linked_list_at(&b, 1, loc_next, 4))
132
133 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&d, 3, loc_prev, 0), &a)
134 CU_ASSERT_PTR_EQUAL(cx_linked_list_at(&d, 3, loc_prev, 1), &b)
135 }
136
137 void test_linked_list_find(void) {
138 int data[] = {2, 4, 6, 8};
139 void *list = create_nodes_test_data(4, data);
140 int s;
141
142 s = 2;
143 CU_ASSERT_EQUAL(cx_linked_list_find(list, loc_next, loc_data,
144 false, cmp_int, &s), 0)
145 s = 4;
146 CU_ASSERT_EQUAL(cx_linked_list_find(list, loc_next, loc_data,
147 false, cmp_int, &s), 1)
148 s = 6;
149 CU_ASSERT_EQUAL(cx_linked_list_find(list, loc_next, loc_data,
150 false, cmp_int, &s), 2)
151 s = 8;
152 CU_ASSERT_EQUAL(cx_linked_list_find(list, loc_next, loc_data,
153 false, cmp_int, &s), 3)
154 s = 10;
155 CU_ASSERT_EQUAL(cx_linked_list_find(list, loc_next, loc_data,
156 false, cmp_int, &s), 4)
157 s = -2;
158 CU_ASSERT_EQUAL(cx_linked_list_find(list, loc_next, loc_data,
159 false, cmp_int, &s), 4)
160 }
161
162 void test_linked_list_compare(void) {
163 int a[] = {2, 4, 6, 8};
164 int b[] = {2, 4, 6};
165 int c[] = {2, 4, 6, 9};
166
167 void *la = create_nodes_test_data(4, a);
168 void *lb = create_nodes_test_data(3, b);
169 void *lc = create_nodes_test_data(4, c);
170
171 CU_ASSERT_TRUE(0 < cx_linked_list_compare(la, lb, loc_next, loc_data,
172 false, cmp_int)
173 )
174 CU_ASSERT_TRUE(0 > cx_linked_list_compare(lb, la, loc_next, loc_data,
175 false, cmp_int)
176 )
177 CU_ASSERT_TRUE(0 < cx_linked_list_compare(lc, la, loc_next, loc_data,
178 false, cmp_int)
179 )
180 CU_ASSERT_TRUE(0 > cx_linked_list_compare(la, lc, loc_next, loc_data,
181 false, cmp_int)
182 )
183 CU_ASSERT_TRUE(0 == cx_linked_list_compare(la, la, loc_next, loc_data,
184 false, cmp_int)
185 )
186
187 destroy_nodes_test_data(la);
188 destroy_nodes_test_data(lb);
189 destroy_nodes_test_data(lc);
190 }
191
192 void test_linked_list_add(void) {
193 struct node nodes[4];
194 void *begin, *end;
195
196 // test with begin, end / prev, next
197 memset(nodes, 0, 4 * sizeof(struct node));
198 begin = end = NULL;
199
200 cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[0]);
201 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
202 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
203 CU_ASSERT_PTR_NULL(nodes[0].prev)
204 CU_ASSERT_PTR_NULL(nodes[0].next)
205
206 cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[1]);
207 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
208 CU_ASSERT_PTR_EQUAL(end, &nodes[1])
209 CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1])
210 CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[0])
211
212 // test with begin only / prev, next
213 memset(nodes, 0, 4 * sizeof(struct node));
214 begin = end = NULL;
215
216 cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[0]);
217 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
218 cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[1]);
219 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
220 CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1])
221 CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[0])
222
223 cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[2]);
224 CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[2])
225 CU_ASSERT_PTR_EQUAL(nodes[2].prev, &nodes[1])
226
227 // test with end only / prev, next
228 memset(nodes, 0, 4 * sizeof(struct node));
229 begin = end = NULL;
230
231 cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[0]);
232 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
233 cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[1]);
234 CU_ASSERT_PTR_EQUAL(end, &nodes[1])
235 CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1])
236 CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[0])
237
238 cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[2]);
239 CU_ASSERT_PTR_EQUAL(end, &nodes[2])
240 CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[2])
241 CU_ASSERT_PTR_EQUAL(nodes[2].prev, &nodes[1])
242
243 // test with begin, end / next
244 memset(nodes, 0, 4 * sizeof(struct node));
245 begin = end = NULL;
246
247 cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[0]);
248 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
249 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
250 cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[1]);
251 CU_ASSERT_PTR_EQUAL(end, &nodes[1])
252 CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1])
253 CU_ASSERT_PTR_NULL(nodes[1].prev)
254 }
255
256 void test_linked_list_prepend(void) {
257 struct node nodes[4];
258 void *begin, *end;
259
260 // test with begin, end / prev, next
261 memset(nodes, 0, 4 * sizeof(struct node));
262 begin = end = NULL;
263
264 cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[0]);
265 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
266 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
267 CU_ASSERT_PTR_NULL(nodes[0].prev)
268 CU_ASSERT_PTR_NULL(nodes[0].next)
269
270 cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[1]);
271 CU_ASSERT_PTR_EQUAL(begin, &nodes[1])
272 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
273 CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[0])
274 CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[1])
275
276 // test with begin only / prev, next
277 memset(nodes, 0, 4 * sizeof(struct node));
278 begin = end = NULL;
279
280 cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[0]);
281 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
282 cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[1]);
283 CU_ASSERT_PTR_EQUAL(begin, &nodes[1])
284 CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[0])
285 CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[1])
286
287 cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[2]);
288 CU_ASSERT_PTR_EQUAL(begin, &nodes[2])
289 CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[1])
290 CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[2])
291
292 // test with end only / prev, next
293 memset(nodes, 0, 4 * sizeof(struct node));
294 begin = end = NULL;
295
296 cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[0]);
297 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
298 cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[1]);
299 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
300 CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[0])
301 CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[1])
302
303 cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[2]);
304 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
305 CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[1])
306 CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[2])
307
308 // test with begin, end / next
309 memset(nodes, 0, 4 * sizeof(struct node));
310 begin = end = NULL;
311
312 cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[0]);
313 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
314 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
315 cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[1]);
316 cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[2]);
317 CU_ASSERT_PTR_EQUAL(begin, &nodes[2])
318 CU_ASSERT_PTR_EQUAL(end, &nodes[0])
319 CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[0])
320 CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[1])
321 CU_ASSERT_PTR_NULL(nodes[1].prev)
322 CU_ASSERT_PTR_NULL(nodes[0].prev)
323 }
324
325 void test_linked_list_insert(void) {
326 struct node nodes[4];
327 void *begin, *end;
328
329 // insert mid list
330 memset(nodes, 0, 4 * sizeof(struct node));
331 begin = &nodes[0];
332 end = &nodes[2];
333
334 cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
335 cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
336
337 cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3]);
338 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
339 CU_ASSERT_PTR_EQUAL(end, &nodes[2])
340 CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[3])
341 CU_ASSERT_PTR_EQUAL(nodes[2].prev, &nodes[3])
342 CU_ASSERT_PTR_EQUAL(nodes[3].prev, &nodes[1])
343 CU_ASSERT_PTR_EQUAL(nodes[3].next, &nodes[2])
344
345 // insert end
346 memset(nodes, 0, 4 * sizeof(struct node));
347 begin = &nodes[0];
348 end = &nodes[2];
349
350 cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
351 cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
352
353 cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3]);
354 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
355 CU_ASSERT_PTR_EQUAL(end, &nodes[3])
356 CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[3])
357 CU_ASSERT_PTR_EQUAL(nodes[3].prev, &nodes[2])
358 CU_ASSERT_PTR_NULL(nodes[3].next)
359
360 // insert begin
361 memset(nodes, 0, 4 * sizeof(struct node));
362 begin = &nodes[0];
363 end = &nodes[2];
364
365 cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
366 cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
367
368 cx_linked_list_insert(&begin, &end, loc_prev, loc_next, NULL, &nodes[3]);
369 CU_ASSERT_PTR_EQUAL(begin, &nodes[3])
370 CU_ASSERT_PTR_EQUAL(end, &nodes[2])
371 CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[3])
372 CU_ASSERT_PTR_NULL(nodes[3].prev)
373 CU_ASSERT_PTR_EQUAL(nodes[3].next, &nodes[0])
374 }
375
376 void test_linked_list_insert_chain(void) {
377 struct node nodes[5];
378 void *begin, *end;
379
380 // insert mid list
381 memset(nodes, 0, 5 * sizeof(struct node));
382 begin = &nodes[0];
383 end = &nodes[2];
384
385 cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
386 cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
387 cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next);
388
389 cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3], NULL);
390 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
391 CU_ASSERT_PTR_EQUAL(end, &nodes[2])
392 CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[3])
393 CU_ASSERT_PTR_EQUAL(nodes[2].prev, &nodes[4])
394 CU_ASSERT_PTR_EQUAL(nodes[3].prev, &nodes[1])
395 CU_ASSERT_PTR_EQUAL(nodes[4].next, &nodes[2])
396
397 // insert end
398 memset(nodes, 0, 5 * sizeof(struct node));
399 begin = &nodes[0];
400 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, &nodes[2], &nodes[3], NULL);
407 CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
408 CU_ASSERT_PTR_EQUAL(end, &nodes[4])
409 CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[3])
410 CU_ASSERT_PTR_EQUAL(nodes[3].prev, &nodes[2])
411 CU_ASSERT_PTR_NULL(nodes[4].next)
412
413 // insert begin
414 memset(nodes, 0, 5 * sizeof(struct node));
415 begin = &nodes[0];
416 end = &nodes[2];
417
418 cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
419 cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
420 cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next);
421
422 cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, NULL, &nodes[3], NULL);
423 CU_ASSERT_PTR_EQUAL(begin, &nodes[3])
424 CU_ASSERT_PTR_EQUAL(end, &nodes[2])
425 CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[4])
426 CU_ASSERT_PTR_NULL(nodes[3].prev)
427 CU_ASSERT_PTR_EQUAL(nodes[4].next, &nodes[0])
428 }
429
430 void test_linked_list_first(void) {
431 struct node *begin = create_nodes_test_data(3, NULL);
432 CU_ASSERT_PTR_EQUAL(cx_linked_list_first(begin, loc_prev), begin)
433 CU_ASSERT_PTR_EQUAL(cx_linked_list_first(begin->next, loc_prev), begin)
434 CU_ASSERT_PTR_EQUAL(cx_linked_list_first(begin->next->next, loc_prev), begin)
435 destroy_nodes_test_data(begin);
436 }
437
438 void test_linked_list_last(void) {
439 struct node *begin = create_nodes_test_data(3, NULL);
440 struct node *end = begin->next->next;
441 CU_ASSERT_PTR_EQUAL(cx_linked_list_last(begin, loc_next), end)
442 CU_ASSERT_PTR_EQUAL(cx_linked_list_last(begin->next, loc_next), end)
443 CU_ASSERT_PTR_EQUAL(cx_linked_list_last(begin->next->next, loc_next), end)
444 destroy_nodes_test_data(begin);
445 }
446
447 void test_linked_list_prev(void) {
448 struct node *begin = create_nodes_test_data(3, NULL);
449 CU_ASSERT_PTR_NULL(cx_linked_list_prev(begin, loc_next, begin))
450 CU_ASSERT_PTR_EQUAL(cx_linked_list_prev(begin, loc_next, begin->next), begin)
451 CU_ASSERT_PTR_EQUAL(cx_linked_list_prev(begin, loc_next, begin->next->next), begin->next)
452 destroy_nodes_test_data(begin);
453 }
454
455 void test_linked_list_remove(void) {
456 void *begin, *end;
457
458 int data[] = {2, 4, 6};
459 begin = create_nodes_test_data(3, data);
460 struct node *first = begin;
461 struct node *second = first->next;
462 struct node *third = second->next;
463 end = third;
464
465 cx_linked_list_remove(&begin, &end, loc_prev, loc_next, second);
466 CU_ASSERT_PTR_EQUAL(begin, first)
467 CU_ASSERT_PTR_EQUAL(end, third)
468 CU_ASSERT_PTR_NULL(first->prev)
469 CU_ASSERT_PTR_EQUAL(first->next, third)
470 CU_ASSERT_PTR_EQUAL(third->prev, first)
471 CU_ASSERT_PTR_NULL(third->next)
472
473 cx_linked_list_remove(&begin, &end, loc_prev, loc_next, third);
474 CU_ASSERT_PTR_EQUAL(begin, first)
475 CU_ASSERT_PTR_EQUAL(end, first)
476 CU_ASSERT_PTR_NULL(first->prev)
477 CU_ASSERT_PTR_NULL(first->next)
478
479 cx_linked_list_remove(&begin, &end, loc_prev, loc_next, first);
480 CU_ASSERT_PTR_NULL(begin)
481 CU_ASSERT_PTR_NULL(end)
482
483 free(first);
484 free(second);
485 free(third);
486 }
487
488 void test_linked_list_size(void) {
489 struct node *list;
490
491 CU_ASSERT_PTR_EQUAL(cx_linked_list_size(NULL, loc_next), 0)
492
493 list = create_nodes_test_data(5, NULL);
494 CU_ASSERT_EQUAL(cx_linked_list_size(list, loc_next), 5)
495 destroy_nodes_test_data(list);
496
497 list = create_nodes_test_data(13, NULL);
498 CU_ASSERT_EQUAL(cx_linked_list_size(list, loc_next), 13)
499 destroy_nodes_test_data(list);
500 }
501
502 void test_linked_list_sort(void) {
503 int expected[] = {
504 14, 30, 151, 163, 227, 300, 315, 317, 363, 398, 417, 424, 438, 446, 508, 555, 605, 713, 716, 759, 761, 880,
505 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 1707, 1734, 1771, 1874, 1894,
506 1976, 2079, 2124, 2130, 2135, 2266, 2338, 2358, 2430, 2500, 2540, 2542, 2546, 2711, 2733, 2754, 2764, 2797,
507 2888, 2900, 3020, 3053, 3109, 3244, 3275, 3302, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 3675, 3677,
508 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681,
509 4785, 4791, 4801, 4859, 4903, 4973
510 };
511 int scrambled[] = {
512 759, 716, 880, 761, 2358, 2542, 2500, 2540, 2546, 2711, 2430, 1707, 1874, 1771, 1894, 1734, 1976, 2079,
513 2124, 2130, 2135, 2266, 2338, 2733, 2754, 2764, 2797, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 2888,
514 2900, 3020, 3053, 3109, 3244, 3275, 3302, 438, 446, 508, 555, 605, 713, 14, 30, 151, 163, 227, 300,
515 894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 315, 317, 363, 398, 417, 424,
516 3675, 3677, 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4785, 4791, 4801, 4859, 4903, 4973,
517 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681
518 };
519
520 void *begin = create_nodes_test_data(100, scrambled);
521 void *end = cx_linked_list_last(begin, loc_next);
522
523 cx_linked_list_sort(&begin, &end, loc_prev, loc_next, loc_data,
524 false, cmp_int);
525
526 struct node *check = begin;
527 struct node *check_last = NULL;
528 CU_ASSERT_PTR_NULL(check->prev)
529 CU_ASSERT_EQUAL(check->data, expected[0])
530 cx_for_n (i, 100) {
531 CU_ASSERT_EQUAL(check->data, expected[i])
532 CU_ASSERT_PTR_EQUAL(check->prev, check_last)
533 if (i < 99) {
534 CU_ASSERT_PTR_NOT_NULL(check->next)
535 }
536 check_last = check;
537 check = check->next;
538 }
539 CU_ASSERT_PTR_NULL(check)
540 CU_ASSERT_PTR_EQUAL(end, check_last)
541
542 destroy_nodes_test_data(begin);
543 }
544
545 void test_linked_list_reverse(void) {
546 void *begin, *end;
547
548 int data[] = {2, 4, 6, 8};
549 int reversed[] = {8, 6, 4, 2};
550
551 void *list = create_nodes_test_data(4, data);
552 void *expected = create_nodes_test_data(4, reversed);
553
554 begin = list;
555 end = cx_linked_list_last(list, loc_next);
556
557 cx_linked_list_reverse(&begin, &end, loc_prev, loc_next);
558 CU_ASSERT_PTR_EQUAL(end, list)
559 CU_ASSERT_PTR_EQUAL(begin, cx_linked_list_first(end, loc_prev))
560 CU_ASSERT_TRUE(0 == cx_linked_list_compare(begin, expected, loc_next, loc_data,
561 0, cmp_int))
562
563 destroy_nodes_test_data(begin);
564 destroy_nodes_test_data(expected);
565 }
566
567 static void verify_linked_list_create(CxList *list) {
568 CU_ASSERT_EQUAL(list->size, 0)
569 CU_ASSERT_EQUAL(list->capacity, (size_t) -1)
570 CU_ASSERT_PTR_EQUAL(list->allocator, cxTestingAllocator)
571 CU_ASSERT_PTR_EQUAL(list->cmpfunc, cmp_int)
572
573 cxListDestroy(list);
574 }
575
576 void test_hl_linked_list_create(void) {
577 CxList *list = cxLinkedListCreate(cxTestingAllocator, cmp_int, sizeof(int));
578 CU_ASSERT_EQUAL(list->itemsize, sizeof(int))
579 verify_linked_list_create(list);
580 }
581
582 void test_hl_ptr_linked_list_create(void) {
583 CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int);
584 CU_ASSERT_EQUAL(list->itemsize, sizeof(void *))
585 verify_linked_list_create(list);
586 }
587
588 void test_hl_linked_list_from_array(void) {
589 int data[] = {2, 4, 5, 7, 10, 15};
590
591 CxList *expected = cxLinkedListCreate(cxTestingAllocator, cmp_int, sizeof(int));
592 cx_for_n (i, 5) cxListAdd(expected, &data[i]);
593
594 CxList *list = cxLinkedListFromArray(cxTestingAllocator, cmp_int, sizeof(int), 5, data);
595
596 CU_ASSERT_TRUE(0 == cxListCompare(list, expected))
597
598 cxListDestroy(list);
599 cxListDestroy(expected);
600 }
601
602 static void verify_hl_linked_list_add(
603 CxList *list,
604 int data[],
605 size_t len,
606 bool write_through
607 ) {
608 cx_for_n (i, len) CU_ASSERT_EQUAL(cxListAdd(list, &data[i]), 0)
609 CU_ASSERT_EQUAL(list->size, len)
610 CU_ASSERT_TRUE(list->capacity >= list->size)
611 cx_for_n (i, len) CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), data[i])
612 cx_for_n (i, len) ++data[i];
613 if (write_through) {
614 cx_for_n (i, len) CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), data[i])
615 } else {
616 cx_for_n (i, len) CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), data[i] - 1)
617 }
618 cxListDestroy(list);
619 }
620
621 void test_hl_linked_list_add(void) {
622 CxList *list = cxLinkedListCreate(cxTestingAllocator, cmp_int, sizeof(int));
623 int data[] = {5, 47, 13, 9, 18, 1, 42};
624 verify_hl_linked_list_add(list, data, sizeof(data) / sizeof(int), false);
625 }
626
627 void test_hl_ptr_linked_list_add(void) {
628 CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int);
629 int data[] = {5, 47, 84, 13, 9, 18, 90, 1, 42};
630 verify_hl_linked_list_add(list, data, sizeof(data) / sizeof(int), true);
631 }
632
633 static void verify_hl_linked_list_insert(CxList *list) {
634 int a = 5, b = 47, c = 13, d = 42;
635
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)
645
646 CU_ASSERT_EQUAL(list->size, 4)
647 CU_ASSERT_TRUE(list->capacity >= list->size)
648
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)
653
654 cxListDestroy(list);
655 }
656
657 void test_hl_linked_list_insert(void) {
658 verify_hl_linked_list_insert(cxLinkedListCreate(cxTestingAllocator, cmp_int, sizeof(int)));
659 }
660
661 void test_hl_ptr_linked_list_insert(void) {
662 verify_hl_linked_list_insert(cxPointerLinkedListCreate(cxTestingAllocator, cmp_int));
663 }
664
665 static void verify_hl_linked_list_remove(CxList *list) {
666 CU_ASSERT_EQUAL(list->size, 4)
667 CU_ASSERT_TRUE(list->capacity >= list->size)
668
669 CU_ASSERT_NOT_EQUAL(cxListRemove(list, 4), 0)
670
671 CU_ASSERT_EQUAL(cxListRemove(list, 2), 0)
672 CU_ASSERT_EQUAL(list->size, 3)
673 CU_ASSERT_TRUE(list->capacity >= list->size)
674 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 5)
675 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 47)
676 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 2), 13)
677
678 CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
679 CU_ASSERT_EQUAL(list->size, 2)
680 CU_ASSERT_TRUE(list->capacity >= list->size)
681 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
682 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 1), 13)
683
684 CU_ASSERT_EQUAL(cxListRemove(list, 1), 0)
685 CU_ASSERT_EQUAL(list->size, 1)
686 CU_ASSERT_TRUE(list->capacity >= list->size)
687 CU_ASSERT_EQUAL(*(int *) cxListAt(list, 0), 47)
688
689 CU_ASSERT_EQUAL(cxListRemove(list, 0), 0)
690 CU_ASSERT_EQUAL(list->size, 0)
691 CU_ASSERT_TRUE(list->capacity >= list->size)
692
693 CU_ASSERT_NOT_EQUAL(cxListRemove(list, 0), 0)
694
695 cxListDestroy(list);
696 }
697
698 void test_hl_linked_list_remove(void) {
699 int data[] = {5, 47, 42, 13};
700 CxList *list = cxLinkedListFromArray(cxTestingAllocator, cmp_int,
701 sizeof(int), 4, data);
702 verify_hl_linked_list_remove(list);
703 }
704
705 void test_hl_ptr_linked_list_remove(void) {
706 int a = 5, b = 47, c = 42, d = 13;
707 CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int);
708 cxListAdd(list, &a);
709 cxListAdd(list, &b);
710 cxListAdd(list, &c);
711 cxListAdd(list, &d);
712 verify_hl_linked_list_remove(list);
713 }
714
715 static void verify_hl_linked_list_at(
716 CxList *list,
717 size_t len,
718 int *data
719 ) {
720 CU_ASSERT_EQUAL(list->size, len)
721 cx_for_n (i, len) CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), data[i])
722 CU_ASSERT_PTR_NULL(cxListAt(list, len))
723 free(data);
724 cxListDestroy(list);
725 }
726
727 void test_hl_linked_list_at(void) {
728 size_t len = 100;
729 int *data = create_ints_test_data(len);
730 CxList *list = cxLinkedListFromArray(cxTestingAllocator, cmp_int,
731 sizeof(int), len, data);
732 verify_hl_linked_list_at(list, len, data);
733 }
734
735 void test_hl_ptr_linked_list_at(void) {
736 size_t len = 250;
737 int *data = create_ints_test_data(len);
738 CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int);
739 cx_for_n (i, len) cxListAdd(list, &data[i]);
740 verify_hl_linked_list_at(list, len, data);
741 }
742
743 static void verify_hl_linked_list_find(
744 CxList *list,
745 size_t len,
746 int *data
747 ) {
748 cx_for_n (attempt, 100) {
749 size_t exp = rand() % len; // NOLINT(cert-msc50-cpp)
750 int val = data[exp];
751 cx_for_n (i, exp) {
752 if (data[i] == val) {
753 exp = i;
754 break;
755 }
756 }
757 CU_ASSERT_EQUAL(cxListFind(list, &val), exp)
758 }
759 free(data);
760 cxListDestroy(list);
761 }
762
763 void test_hl_linked_list_find(void) {
764 size_t len = 100;
765 int *data = create_ints_test_data(len);
766 CxList *list = cxLinkedListFromArray(cxTestingAllocator, cmp_int, sizeof(int), len, data);
767 verify_hl_linked_list_find(list, len, data);
768 }
769
770 void test_hl_ptr_linked_list_find(void) {
771 size_t len = 250;
772 int *data = create_ints_test_data(len);
773 CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int);
774 cx_for_n (i, len) cxListAdd(list, &data[i]);
775 verify_hl_linked_list_find(list, len, data);
776 }
777
778 struct sort_test_data {
779 size_t len;
780 int *data;
781 int *sorted;
782 };
783
784 static struct sort_test_data create_sort_test_data(void) {
785 size_t len = 1000;
786 int *data = create_ints_test_data(len);
787 int *sorted = malloc(sizeof(int) * len);
788 memcpy(sorted, data, sizeof(int) * len);
789 qsort(sorted, len, sizeof(int), cmp_int);
790 struct sort_test_data s = {len, data, sorted};
791 return s;
792 }
793
794 static void free_sort_test_data(struct sort_test_data s) {
795 free(s.data);
796 free(s.sorted);
797 }
798
799 static void verify_hl_linked_list_sort(
800 CxList *list,
801 struct sort_test_data td
802 ) {
803 cxListSort(list);
804 cx_for_n (i, td.len) CU_ASSERT_EQUAL_FATAL(*(int *) cxListAt(list, i), td.sorted[i])
805 free_sort_test_data(td);
806 cxListDestroy(list);
807 }
808
809 void test_hl_linked_list_sort(void) {
810 struct sort_test_data td = create_sort_test_data();
811 CxList *list = cxLinkedListFromArray(cxTestingAllocator, cmp_int, sizeof(int), td.len, td.data);
812 verify_hl_linked_list_sort(list, td);
813 }
814
815 void test_hl_ptr_linked_list_sort(void) {
816 struct sort_test_data td = create_sort_test_data();
817 CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int);
818 cx_for_n (i, td.len) cxListAdd(list, &td.data[i]);
819 verify_hl_linked_list_sort(list, td);
820 }
821
822 void verify_hl_linked_list_iterator(CxList *list) {
823 int i = 0;
824 CxIterator iter = cxListBegin(list);
825 cx_foreach(int*, x, iter) {
826 CU_ASSERT_EQUAL(iter.index, (size_t) (i + 1) / 2)
827 CU_ASSERT_EQUAL(*x, i)
828 if (*x % 2 == 1) iter.remove = true;
829 i++;
830 }
831 CU_ASSERT_EQUAL(i, 10)
832 CU_ASSERT_EQUAL_FATAL(list->size, 5)
833 cx_for_n(j, 5) CU_ASSERT_EQUAL(*(int *) cxListAt(list, j), (int) j * 2)
834 cxListDestroy(list);
835 }
836
837 void test_hl_linked_list_iterator(void) {
838 CxList *list = cxLinkedListCreate(cxTestingAllocator, cmp_int, sizeof(int));
839 cx_for_n (i, 10) cxListAdd(list, &i);
840 verify_hl_linked_list_iterator(list);
841 }
842
843 void test_hl_ptr_linked_list_iterator(void) {
844 CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int);
845 int data[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
846 cx_for_n (i, 10) cxListAdd(list, &data[i]);
847 verify_hl_linked_list_iterator(list);
848 }
849
850 static void verify_hl_linked_list_insert_via_iterator(
851 CxList *list,
852 int *testdata
853 ) {
854 CxIterator iter = cxListIterator(list, 2);
855 CU_ASSERT_EQUAL(iter.index, 2)
856 CU_ASSERT_EQUAL(*(int *) cxIteratorCurrent(&iter), 2)
857 size_t i = 4;
858
859 ++i;
860 cxListInsertAfter(&iter, &testdata[i]);
861 CU_ASSERT_EQUAL(iter.index, 2)
862 CU_ASSERT_EQUAL(*(int *) cxIteratorCurrent(&iter), 2)
863 ++i;
864 cxListInsertBefore(&iter, &testdata[i]);
865 CU_ASSERT_EQUAL(iter.index, 3)
866 CU_ASSERT_EQUAL(*(int *) cxIteratorCurrent(&iter), 2)
867
868 iter = cxListBegin(list);
869 ++i;
870 cxListInsertBefore(&iter, &testdata[i]);
871 CU_ASSERT_EQUAL(iter.index, 1)
872 CU_ASSERT_EQUAL(*(int *) cxIteratorCurrent(&iter), 0)
873 iter = cxListIterator(list, list->size);
874 ++i;
875 cxListInsertBefore(&iter, &testdata[i]);
876 CU_ASSERT_EQUAL(iter.index, 9)
877 CU_ASSERT_FALSE(cxIteratorValid(&iter))
878 iter = cxListIterator(list, list->size);
879 ++i;
880 cxListInsertAfter(&iter, &testdata[i]);
881 CU_ASSERT_EQUAL(iter.index, 10)
882 CU_ASSERT_FALSE(cxIteratorValid(&iter))
883
884 int expdata[] = {30, 0, 1, 20, 2, 10, 3, 4, 40, 50};
885 cx_for_n (j, 10) CU_ASSERT_EQUAL(*(int *) cxListAt(list, j), expdata[j])
886 cxListDestroy(list);
887 }
888
889 void test_hl_linked_list_insert_via_iterator(void) {
890 int testdata[] = {0, 1, 2, 3, 4, 10, 20, 30, 40, 50};
891 // only add the first five elements, the remaining five will be inserted
892 CxList *list = cxLinkedListFromArray(cxTestingAllocator, cmp_int, sizeof(int), 5, testdata);
893 verify_hl_linked_list_insert_via_iterator(list, testdata);
894 }
895
896 void test_hl_ptr_linked_list_insert_via_iterator(void) {
897 int testdata[] = {0, 1, 2, 3, 4, 10, 20, 30, 40, 50};
898 CxList *list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int);
899 // only add the first five elements, the remaining five will be inserted
900 cx_for_n (i, 5) cxListAdd(list, &testdata[i]);
901 verify_hl_linked_list_insert_via_iterator(list, testdata);
902 }
903
904 static void test_setup_allocator(void) {
905 cxTestingAllocatorReset();
906 }
907
908 static void test_verify_allocator(void) {
909 CU_ASSERT_TRUE(cxTestingAllocatorVerify())
910 }
911
912 int main() {
913 CU_pSuite suite = NULL;
914
915 if (CUE_SUCCESS != CU_initialize_registry()) {
916 return CU_get_error();
917 }
918
919 suite = CU_add_suite("low level linked list", NULL, NULL);
920
921 cu_add_test(suite, test_linked_list_link_unlink);
922 cu_add_test(suite, test_linked_list_at);
923 cu_add_test(suite, test_linked_list_find);
924 cu_add_test(suite, test_linked_list_compare);
925 cu_add_test(suite, test_linked_list_prepend);
926 cu_add_test(suite, test_linked_list_add);
927 cu_add_test(suite, test_linked_list_insert);
928 cu_add_test(suite, test_linked_list_insert_chain);
929 cu_add_test(suite, test_linked_list_first);
930 cu_add_test(suite, test_linked_list_last);
931 cu_add_test(suite, test_linked_list_prev);
932 cu_add_test(suite, test_linked_list_remove);
933 cu_add_test(suite, test_linked_list_size);
934 cu_add_test(suite, test_linked_list_sort);
935 cu_add_test(suite, test_linked_list_reverse);
936
937 suite = CU_add_suite_with_setup_and_teardown(
938 "high level linked list", NULL, NULL,
939 test_setup_allocator, test_verify_allocator);
940
941 cu_add_test(suite, test_hl_linked_list_create);
942 cu_add_test(suite, test_hl_linked_list_from_array);
943 cu_add_test(suite, test_hl_linked_list_add);
944 cu_add_test(suite, test_hl_linked_list_insert);
945 cu_add_test(suite, test_hl_linked_list_remove);
946 cu_add_test(suite, test_hl_linked_list_at);
947 cu_add_test(suite, test_hl_linked_list_find);
948 cu_add_test(suite, test_hl_linked_list_sort);
949 cu_add_test(suite, test_hl_linked_list_iterator);
950 cu_add_test(suite, test_hl_linked_list_insert_via_iterator);
951
952 suite = CU_add_suite_with_setup_and_teardown(
953 "high level pointer linked list", NULL, NULL,
954 test_setup_allocator, test_verify_allocator);
955
956 cu_add_test(suite, test_hl_ptr_linked_list_create);
957 cu_add_test(suite, test_hl_ptr_linked_list_add);
958 cu_add_test(suite, test_hl_ptr_linked_list_insert);
959 cu_add_test(suite, test_hl_ptr_linked_list_remove);
960 cu_add_test(suite, test_hl_ptr_linked_list_at);
961 cu_add_test(suite, test_hl_ptr_linked_list_find);
962 cu_add_test(suite, test_hl_ptr_linked_list_sort);
963 cu_add_test(suite, test_hl_ptr_linked_list_iterator);
964 cu_add_test(suite, test_hl_ptr_linked_list_insert_via_iterator);
965
966 CU_basic_set_mode(UCX_CU_BRM);
967
968 int exitcode;
969 if (CU_basic_run_tests()) {
970 exitcode = CU_get_error();
971 } else {
972 exitcode = CU_get_number_of_failures() == 0 ? 0 : 1;
973 }
974 CU_cleanup_registry();
975 return exitcode;
976 }

Mercurial Repository: ucx

mercurial