Wed, 03 Apr 2024 21:22:23 +0200
implement tree continue - fixes #376
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 */
29 #include "cx/tree.h"
31 #include "cx/test.h"
33 #include "util_allocator.h"
35 typedef struct tree_node {
36 struct tree_node *parent;
37 struct tree_node *next;
38 struct tree_node *prev;
39 struct tree_node *children;
40 int data;
41 } tree_node;
43 #define tree_node_layout \
44 offsetof(tree_node, parent), offsetof(tree_node, children), \
45 offsetof(tree_node, prev), offsetof(tree_node, next)
47 #define tree_child_list offsetof(tree_node, children),offsetof(tree_node, next)
49 CX_TEST(test_tree_link_new_child) {
50 tree_node parent = {0};
51 tree_node child = {0};
53 CX_TEST_DO {
54 cx_tree_link(&parent, &child, tree_node_layout);
55 CX_TEST_ASSERT(parent.next == NULL);
56 CX_TEST_ASSERT(parent.prev == NULL);
57 CX_TEST_ASSERT(parent.parent == NULL);
58 CX_TEST_ASSERT(parent.children == &child);
59 CX_TEST_ASSERT(child.parent == &parent);
60 CX_TEST_ASSERT(child.next == NULL);
61 CX_TEST_ASSERT(child.prev == NULL);
62 CX_TEST_ASSERT(child.children == NULL);
63 }
64 }
66 CX_TEST(test_tree_link_add_child) {
67 tree_node parent = {0};
68 tree_node child1 = {0};
69 tree_node child2 = {0};
70 tree_node child3 = {0};
72 CX_TEST_DO {
73 cx_tree_link(&parent, &child1, tree_node_layout);
74 cx_tree_link(&parent, &child2, tree_node_layout);
75 cx_tree_link(&parent, &child3, tree_node_layout);
76 CX_TEST_ASSERT(parent.next == NULL);
77 CX_TEST_ASSERT(parent.prev == NULL);
78 CX_TEST_ASSERT(parent.parent == NULL);
79 CX_TEST_ASSERT(parent.children == &child3);
81 CX_TEST_ASSERT(child1.parent == &parent);
82 CX_TEST_ASSERT(child2.parent == &parent);
83 CX_TEST_ASSERT(child3.parent == &parent);
84 CX_TEST_ASSERT(child1.children == NULL);
85 CX_TEST_ASSERT(child2.children == NULL);
86 CX_TEST_ASSERT(child3.children == NULL);
88 CX_TEST_ASSERT(child3.prev == NULL);
89 CX_TEST_ASSERT(child3.next == &child2);
90 CX_TEST_ASSERT(child2.prev == &child3);
91 CX_TEST_ASSERT(child2.next == &child1);
92 CX_TEST_ASSERT(child1.prev == &child2);
93 CX_TEST_ASSERT(child1.next == NULL);
94 }
95 }
97 CX_TEST(test_tree_link_move_to_other_parent) {
98 tree_node parent = {0};
99 tree_node child1 = {0};
100 tree_node child2 = {0};
101 tree_node child3 = {0};
102 cx_tree_link(&parent, &child1, tree_node_layout);
103 cx_tree_link(&parent, &child2, tree_node_layout);
104 cx_tree_link(&parent, &child3, tree_node_layout);
106 CX_TEST_DO {
107 cx_tree_link(&child3, &child2, tree_node_layout);
109 CX_TEST_ASSERT(parent.next == NULL);
110 CX_TEST_ASSERT(parent.prev == NULL);
111 CX_TEST_ASSERT(parent.parent == NULL);
112 CX_TEST_ASSERT(parent.children == &child3);
114 CX_TEST_ASSERT(child1.parent == &parent);
115 CX_TEST_ASSERT(child2.parent == &child3);
116 CX_TEST_ASSERT(child3.parent == &parent);
117 CX_TEST_ASSERT(child1.children == NULL);
118 CX_TEST_ASSERT(child2.children == NULL);
119 CX_TEST_ASSERT(child3.children == &child2);
121 CX_TEST_ASSERT(child3.prev == NULL);
122 CX_TEST_ASSERT(child3.next == &child1);
123 CX_TEST_ASSERT(child1.prev == &child3);
124 CX_TEST_ASSERT(child1.next == NULL);
126 CX_TEST_ASSERT(child2.prev == NULL);
127 CX_TEST_ASSERT(child2.next == NULL);
128 }
129 }
131 CX_TEST(test_tree_unlink) {
132 tree_node parent = {0};
133 tree_node child1 = {0};
134 tree_node child2 = {0};
135 tree_node child3 = {0};
136 cx_tree_link(&parent, &child1, tree_node_layout);
137 cx_tree_link(&parent, &child3, tree_node_layout);
138 cx_tree_link(&child3, &child2, tree_node_layout);
140 CX_TEST_DO {
141 cx_tree_unlink(&child3, tree_node_layout);
143 CX_TEST_ASSERT(parent.next == NULL);
144 CX_TEST_ASSERT(parent.prev == NULL);
145 CX_TEST_ASSERT(parent.parent == NULL);
146 CX_TEST_ASSERT(parent.children == &child1);
148 CX_TEST_ASSERT(child1.parent == &parent);
149 CX_TEST_ASSERT(child1.children == NULL);
150 CX_TEST_ASSERT(child1.prev == NULL);
151 CX_TEST_ASSERT(child1.next == NULL);
153 // child 3 is unlinked
154 CX_TEST_ASSERT(child3.parent == NULL);
155 CX_TEST_ASSERT(child3.prev == NULL);
156 CX_TEST_ASSERT(child3.next == NULL);
158 // child 2 is still child of the unlinked child 3
159 CX_TEST_ASSERT(child3.children == &child2);
160 CX_TEST_ASSERT(child2.parent == &child3);
161 CX_TEST_ASSERT(child2.children == NULL);
162 CX_TEST_ASSERT(child2.prev == NULL);
163 CX_TEST_ASSERT(child2.next == NULL);
164 }
165 }
167 static int test_tree_search_function(void const *n, void const *d) {
168 tree_node const *node = n;
169 int data = *((int const*)d);
171 if (data < node->data) return -1;
172 else if (data == node->data) return 0;
173 else return data - node->data;
174 }
176 CX_TEST(test_tree_search) {
177 tree_node root = {0};
178 tree_node a = {0};
179 tree_node b = {0};
180 tree_node c = {0};
181 tree_node aa = {0};
182 tree_node ab = {0};
183 tree_node ba = {0};
184 tree_node ca = {0};
185 tree_node cb = {0};
186 tree_node cc = {0};
187 tree_node cba = {0};
189 int testdata[] = {0, 10, 14, 18, 20, 25, 30, 32, 34, 36, 40};
190 tree_node* testnodes[] = {&root, &a, &aa, &ab, &b, &ba, &c, &ca, &cb, &cba, &cc};
192 for (unsigned i = 0 ; i <= 10 ; i++) {
193 testnodes[i]->data = testdata[i];
194 }
196 cx_tree_link(&root, &a, tree_node_layout);
197 cx_tree_link(&root, &b, tree_node_layout);
198 cx_tree_link(&root, &c, tree_node_layout);
200 cx_tree_link(&a, &aa, tree_node_layout);
201 cx_tree_link(&a, &ab, tree_node_layout);
203 cx_tree_link(&b, &ba, tree_node_layout);
205 cx_tree_link(&c, &ca, tree_node_layout);
206 cx_tree_link(&c, &cb, tree_node_layout);
207 cx_tree_link(&c, &cc, tree_node_layout);
209 cx_tree_link(&cb, &cba, tree_node_layout);
211 int s;
212 int r;
213 tree_node *n;
214 CX_TEST_DO {
215 for (unsigned i = 0 ; i <= 10 ; i++) {
216 s = testdata[i];
217 r = cx_tree_search(&root, &s, test_tree_search_function,
218 (void **) &n, tree_child_list);
219 CX_TEST_ASSERT(r == 0);
220 CX_TEST_ASSERT(n == testnodes[i]);
221 }
223 s = -5;
224 r = cx_tree_search(&root, &s, test_tree_search_function,
225 (void **) &n, tree_child_list);
226 CX_TEST_ASSERT(r < 0);
227 CX_TEST_ASSERT(n == NULL);
229 s = 26;
230 r = cx_tree_search(&root, &s, test_tree_search_function,
231 (void **) &n, tree_child_list);
232 CX_TEST_ASSERT(r > 0);
233 CX_TEST_ASSERT(n == &ba);
235 s = 35;
236 r = cx_tree_search(&root, &s, test_tree_search_function,
237 (void **) &n, tree_child_list);
238 CX_TEST_ASSERT(r > 0);
239 CX_TEST_ASSERT(n == &cb);
241 s = 38;
242 r = cx_tree_search(&root, &s, test_tree_search_function,
243 (void **) &n, tree_child_list);
244 CX_TEST_ASSERT(r > 0);
245 CX_TEST_ASSERT(n == &cba);
247 s = 42;
248 r = cx_tree_search(&root, &s, test_tree_search_function,
249 (void **) &n, tree_child_list);
250 CX_TEST_ASSERT(r > 0);
251 CX_TEST_ASSERT(n == &cc);
252 }
253 }
255 CX_TEST(test_tree_iterator_create_and_dispose) {
256 tree_node root;
257 CX_TEST_DO {
258 CxTreeIterator iter = cx_tree_iterator(&root, false, tree_child_list);
259 CX_TEST_ASSERT(!iter.visit_on_exit);
260 CX_TEST_ASSERT(!iter.exiting);
261 CX_TEST_ASSERT(iter.counter == 1);
262 CX_TEST_ASSERT(iter.node == &root);
263 CX_TEST_ASSERT(!iter.base.mutating);
264 CX_TEST_ASSERT(!iter.base.remove);
265 CX_TEST_ASSERT(iter.stack != NULL);
266 CX_TEST_ASSERT(iter.stack_capacity > 0);
267 CX_TEST_ASSERT(iter.stack_size == 1);
268 CX_TEST_ASSERT(iter.depth == 1);
269 CX_TEST_ASSERT(iter.loc_next == offsetof(tree_node, next));
270 CX_TEST_ASSERT(iter.loc_children == offsetof(tree_node, children));
271 cxTreeIteratorDispose(&iter);
272 CX_TEST_ASSERT(iter.stack == NULL);
273 }
274 }
276 CX_TEST(test_tree_iterator_basic_only_enter) {
277 tree_node root = {0};
278 tree_node a = {0};
279 tree_node b = {0};
280 tree_node c = {0};
281 tree_node aa = {0};
282 tree_node ab = {0};
283 tree_node ba = {0};
284 tree_node ca = {0};
285 tree_node cb = {0};
286 tree_node cc = {0};
287 tree_node cba = {0};
289 tree_node* expected_order[] = {
290 &root,
291 &c, &cc,&cb, &cba,&ca,
292 &b, &ba,
293 &a, &ab, &aa,
294 };
295 tree_node* actual_order[16]; // reserve more space in case s.t. goes wrong
297 cx_tree_link(&root, &a, tree_node_layout);
298 cx_tree_link(&root, &b, tree_node_layout);
299 cx_tree_link(&root, &c, tree_node_layout);
300 cx_tree_link(&a, &aa, tree_node_layout);
301 cx_tree_link(&a, &ab, tree_node_layout);
302 cx_tree_link(&b, &ba, tree_node_layout);
303 cx_tree_link(&c, &ca, tree_node_layout);
304 cx_tree_link(&c, &cb, tree_node_layout);
305 cx_tree_link(&c, &cc, tree_node_layout);
306 cx_tree_link(&cb, &cba, tree_node_layout);
307 CX_TEST_DO {
308 CxTreeIterator iter = cx_tree_iterator(&root, false, tree_child_list);
309 unsigned chk = 0;
310 cx_foreach(tree_node*, node, iter) {
311 CX_TEST_ASSERT(node->data == 0);
312 node->data++;
313 actual_order[chk] = node;
314 chk++;
315 CX_TEST_ASSERT(node == iter.node);
316 CX_TEST_ASSERT(!iter.exiting);
317 if (node == &root) {
318 CX_TEST_ASSERT(iter.depth == 1);
319 } else if (node == &a || node == &b || node == &c) {
320 CX_TEST_ASSERT(iter.depth == 2);
321 } else if (node == &cba) {
322 CX_TEST_ASSERT(iter.depth == 4);
323 } else {
324 CX_TEST_ASSERT(iter.depth == 3);
325 }
326 }
327 CX_TEST_ASSERT(iter.counter == 11);
328 CX_TEST_ASSERT(chk == 11);
329 for (unsigned i = 0 ; i < chk ; i++) {
330 CX_TEST_ASSERT(actual_order[i] == expected_order[i]);
331 CX_TEST_ASSERT(actual_order[i]->data == 1);
332 }
333 CX_TEST_ASSERT(iter.stack == NULL);
334 }
335 }
337 CX_TEST(test_tree_iterator_basic_enter_and_exit) {
338 tree_node root = {0};
339 tree_node a = {0};
340 tree_node b = {0};
341 tree_node c = {0};
342 tree_node aa = {0};
343 tree_node ab = {0};
344 tree_node ba = {0};
345 tree_node ca = {0};
346 tree_node cb = {0};
347 tree_node cc = {0};
348 tree_node cba = {0};
350 cx_tree_link(&root, &a, tree_node_layout);
351 cx_tree_link(&root, &b, tree_node_layout);
352 cx_tree_link(&root, &c, tree_node_layout);
353 cx_tree_link(&a, &aa, tree_node_layout);
354 cx_tree_link(&a, &ab, tree_node_layout);
355 cx_tree_link(&b, &ba, tree_node_layout);
356 cx_tree_link(&c, &ca, tree_node_layout);
357 cx_tree_link(&c, &cb, tree_node_layout);
358 cx_tree_link(&c, &cc, tree_node_layout);
359 cx_tree_link(&cb, &cba, tree_node_layout);
360 CX_TEST_DO {
361 CxTreeIterator iter = cx_tree_iterator(&root, true, tree_child_list);
362 unsigned chk = 0;
363 cx_foreach(tree_node*, node, iter) {
364 CX_TEST_ASSERT(iter.exiting || node->data == 0);
365 node->data++;
366 chk++;
367 CX_TEST_ASSERT(node == iter.node);
368 if (node == &root) {
369 CX_TEST_ASSERT(iter.depth == 1);
370 } else if (node == &a || node == &b || node == &c) {
371 CX_TEST_ASSERT(iter.depth == 2);
372 } else if (node == &cba) {
373 CX_TEST_ASSERT(iter.depth == 4);
374 } else {
375 CX_TEST_ASSERT(iter.depth == 3);
376 }
377 }
378 CX_TEST_ASSERT(iter.counter == 11);
379 CX_TEST_ASSERT(chk == 22);
380 CX_TEST_ASSERT(iter.stack == NULL);
381 CX_TEST_ASSERT(root.data == 2);
382 CX_TEST_ASSERT(a.data == 2);
383 CX_TEST_ASSERT(b.data == 2);
384 CX_TEST_ASSERT(c.data == 2);
385 CX_TEST_ASSERT(aa.data == 2);
386 CX_TEST_ASSERT(ab.data == 2);
387 CX_TEST_ASSERT(ba.data == 2);
388 CX_TEST_ASSERT(ca.data == 2);
389 CX_TEST_ASSERT(cb.data == 2);
390 CX_TEST_ASSERT(cc.data == 2);
391 CX_TEST_ASSERT(cba.data == 2);
392 }
393 }
395 typedef struct test_xml_node {
396 struct test_xml_node *parent;
397 struct test_xml_node *next;
398 struct test_xml_node *prev;
399 struct test_xml_node *children;
400 char const* name;
401 } test_xml_node;
403 CX_TEST(test_tree_iterator_xml) {
404 test_xml_node project = {0};
405 test_xml_node config = {0};
406 test_xml_node var1 = {0};
407 test_xml_node var2 = {0};
408 test_xml_node var3 = {0};
409 test_xml_node dependency1 = {0};
410 test_xml_node dependency1make = {0};
411 test_xml_node dependency2 = {0};
412 test_xml_node dependency2lang = {0};
413 test_xml_node dependency2make = {0};
414 test_xml_node target = {0};
415 test_xml_node target_feature = {0};
416 test_xml_node target_feature_dependencies = {0};
417 test_xml_node target_dependencies = {0};
419 project.name = "project";
420 config.name = "config";
421 var1.name = "var";
422 var2.name = "var";
423 var3.name = "var";
424 dependency1.name = "dependency";
425 dependency1make.name = "make";
426 dependency2.name = "dependency";
427 dependency2lang.name = "lang";
428 dependency2make.name = "make";
429 target.name = "target";
430 target_feature.name = "feature";
431 target_dependencies.name = "dependencies";
432 target_feature_dependencies.name = "dependencies";
434 cx_tree_link(&project, &target, tree_node_layout);
435 cx_tree_link(&project, &dependency2, tree_node_layout);
436 cx_tree_link(&project, &dependency1, tree_node_layout);
437 cx_tree_link(&project, &config, tree_node_layout);
438 cx_tree_link(&config, &var3, tree_node_layout);
439 cx_tree_link(&config, &var2, tree_node_layout);
440 cx_tree_link(&config, &var1, tree_node_layout);
441 cx_tree_link(&dependency1, &dependency1make, tree_node_layout);
442 cx_tree_link(&dependency2, &dependency2make, tree_node_layout);
443 cx_tree_link(&dependency2, &dependency2lang, tree_node_layout);
444 cx_tree_link(&target, &target_dependencies, tree_node_layout);
445 cx_tree_link(&target, &target_feature, tree_node_layout);
446 cx_tree_link(&target_feature, &target_feature_dependencies, tree_node_layout);
448 char const *expected =
449 "<project><config><var></var><var></var><var></var></config>"
450 "<dependency><make></make></dependency><dependency><lang></lang><make></make></dependency>"
451 "<target><feature><dependencies></dependencies></feature><dependencies></dependencies></target></project>";
452 char *actual = malloc(512);
453 CX_TEST_DO {
454 CxTreeIterator iter = cx_tree_iterator(&project, true, tree_child_list);
455 size_t i = 0;
456 cx_foreach(test_xml_node*, node, iter) {
457 size_t len = strlen(node->name);
458 actual[i++] = '<';
459 if (iter.exiting) {
460 actual[i++] = '/';
461 }
462 memcpy(actual+i, node->name, len);
463 i += len;
464 actual[i++] = '>';
465 }
466 actual[i] = '\0';
467 CX_TEST_ASSERT(0 == strcmp(expected, actual));
468 }
469 free(actual);
470 }
472 CX_TEST(test_tree_iterator_free_nodes) {
473 CxTestingAllocator talloc;
474 cx_testing_allocator_init(&talloc);
475 CxAllocator *alloc = &talloc.base;
476 CX_TEST_DO {
477 tree_node *root = cxCalloc(alloc, 1, sizeof(tree_node));
478 tree_node *a = cxCalloc(alloc, 1, sizeof(tree_node));
479 tree_node *b = cxCalloc(alloc, 1, sizeof(tree_node));
480 tree_node *c = cxCalloc(alloc, 1, sizeof(tree_node));
481 tree_node *aa = cxCalloc(alloc, 1, sizeof(tree_node));
482 tree_node *ab = cxCalloc(alloc, 1, sizeof(tree_node));
483 tree_node *ba = cxCalloc(alloc, 1, sizeof(tree_node));
484 tree_node *ca = cxCalloc(alloc, 1, sizeof(tree_node));
485 tree_node *cb = cxCalloc(alloc, 1, sizeof(tree_node));
486 tree_node *cc = cxCalloc(alloc, 1, sizeof(tree_node));
487 tree_node *cba = cxCalloc(alloc, 1, sizeof(tree_node));
489 cx_tree_link(root, a, tree_node_layout);
490 cx_tree_link(root, b, tree_node_layout);
491 cx_tree_link(root, c, tree_node_layout);
492 cx_tree_link(a, aa, tree_node_layout);
493 cx_tree_link(a, ab, tree_node_layout);
494 cx_tree_link(b, ba, tree_node_layout);
495 cx_tree_link(c, ca, tree_node_layout);
496 cx_tree_link(c, cb, tree_node_layout);
497 cx_tree_link(c, cc, tree_node_layout);
498 cx_tree_link(cb, cba, tree_node_layout);
500 CxTreeIterator iter = cx_tree_iterator(root, true, tree_child_list);
501 cx_foreach(tree_node *, node, iter) {
502 if (iter.exiting) {
503 cxFree(alloc,node);
504 }
505 }
507 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
508 }
509 cx_testing_allocator_destroy(&talloc);
510 }
512 CX_TEST(test_tree_visitor_create_and_dispose) {
513 tree_node root;
514 tree_node child;
515 cx_tree_link(&root, &child, tree_node_layout);
516 CX_TEST_DO {
517 CxTreeVisitor iter = cx_tree_visitor(&root, tree_child_list);
518 CX_TEST_ASSERT(iter.counter == 1);
519 CX_TEST_ASSERT(iter.node == &root);
520 CX_TEST_ASSERT(!iter.base.mutating);
521 CX_TEST_ASSERT(!iter.base.remove);
522 CX_TEST_ASSERT(iter.queue_next != NULL);
523 CX_TEST_ASSERT(iter.queue_last != NULL);
524 CX_TEST_ASSERT(iter.depth == 1);
525 CX_TEST_ASSERT(iter.loc_next == offsetof(tree_node, next));
526 CX_TEST_ASSERT(iter.loc_children == offsetof(tree_node, children));
527 cxTreeVisitorDispose(&iter);
528 CX_TEST_ASSERT(iter.queue_next == NULL);
529 CX_TEST_ASSERT(iter.queue_last == NULL);
530 }
531 }
533 CX_TEST(test_tree_visitor) {
534 tree_node root = {0};
535 tree_node a = {0};
536 tree_node b = {0};
537 tree_node c = {0};
538 tree_node aa = {0};
539 tree_node ab = {0};
540 tree_node ba = {0};
541 tree_node ca = {0};
542 tree_node cb = {0};
543 tree_node cc = {0};
544 tree_node cba = {0};
546 tree_node* expected_order[] = {
547 &root,
548 &c, &b, &a,
549 &cc, &cb, &ca, &ba, &ab, &aa,
550 &cba
551 };
552 tree_node* actual_order[16]; // reserve more space in case s.t. goes wrong
554 cx_tree_link(&root, &a, tree_node_layout);
555 cx_tree_link(&root, &b, tree_node_layout);
556 cx_tree_link(&root, &c, tree_node_layout);
557 cx_tree_link(&a, &aa, tree_node_layout);
558 cx_tree_link(&a, &ab, tree_node_layout);
559 cx_tree_link(&b, &ba, tree_node_layout);
560 cx_tree_link(&c, &ca, tree_node_layout);
561 cx_tree_link(&c, &cb, tree_node_layout);
562 cx_tree_link(&c, &cc, tree_node_layout);
563 cx_tree_link(&cb, &cba, tree_node_layout);
564 CX_TEST_DO {
565 CxTreeVisitor iter = cx_tree_visitor(&root, tree_child_list);
566 unsigned chk = 0;
567 cx_foreach(tree_node*, node, iter) {
568 CX_TEST_ASSERT(node->data == 0);
569 node->data++;
570 actual_order[chk] = node;
571 chk++;
572 CX_TEST_ASSERT(node == iter.node);
573 if (node == &root) {
574 CX_TEST_ASSERT(iter.depth == 1);
575 } else if (node == &a || node == &b || node == &c) {
576 CX_TEST_ASSERT(iter.depth == 2);
577 } else if (node == &cba) {
578 CX_TEST_ASSERT(iter.depth == 4);
579 } else {
580 CX_TEST_ASSERT(iter.depth == 3);
581 }
582 }
583 CX_TEST_ASSERT(iter.counter == 11);
584 CX_TEST_ASSERT(chk == 11);
585 for (unsigned i = 0 ; i < chk ; i++) {
586 CX_TEST_ASSERT(actual_order[i] == expected_order[i]);
587 CX_TEST_ASSERT(actual_order[i]->data == 1);
588 }
589 CX_TEST_ASSERT(iter.queue_next == NULL);
590 CX_TEST_ASSERT(iter.queue_last == NULL);
591 }
592 }
594 CX_TEST(test_tree_visitor_no_children) {
595 tree_node root = {0};
597 CX_TEST_DO {
598 CxTreeVisitor iter = cx_tree_visitor(&root, tree_child_list);
599 unsigned chk = 0;
600 cx_foreach(tree_node*, node, iter) {
601 CX_TEST_ASSERT(node == iter.node);
602 chk++;
603 }
604 CX_TEST_ASSERT(iter.counter == 1);
605 CX_TEST_ASSERT(chk == 1);
606 CX_TEST_ASSERT(iter.queue_next == NULL);
607 CX_TEST_ASSERT(iter.queue_last == NULL);
608 }
609 }
611 CX_TEST(test_tree_visitor_no_branching) {
612 tree_node root = {0};
613 tree_node a = {0};
614 tree_node b = {0};
615 tree_node c = {0};
617 tree_node* expected_order[] = {
618 &root, &a, &b, &c
619 };
620 tree_node* actual_order[4];
622 cx_tree_link(&root, &a, tree_node_layout);
623 cx_tree_link(&a, &b, tree_node_layout);
624 cx_tree_link(&b, &c, tree_node_layout);
626 CX_TEST_DO {
627 CxTreeVisitor iter = cx_tree_visitor(&root, tree_child_list);
628 unsigned chk = 0;
629 cx_foreach(tree_node*, node, iter) {
630 CX_TEST_ASSERT(node == iter.node);
631 CX_TEST_ASSERT(node->data == 0);
632 node->data++;
633 actual_order[chk] = node;
634 chk++;
635 }
636 CX_TEST_ASSERT(iter.counter == 4);
637 CX_TEST_ASSERT(chk == 4);
638 CX_TEST_ASSERT(iter.queue_next == NULL);
639 CX_TEST_ASSERT(iter.queue_last == NULL);
640 for (unsigned i = 0 ; i < chk ; i++) {
641 CX_TEST_ASSERT(actual_order[i] == expected_order[i]);
642 CX_TEST_ASSERT(actual_order[i]->data == 1);
643 }
644 }
645 }
647 CX_TEST(test_tree_visitor_continue) {
648 tree_node root = {0};
649 tree_node a = {0};
650 tree_node b = {0};
651 tree_node c = {0};
652 tree_node aa = {0};
653 tree_node ab = {0};
654 tree_node ba = {0};
655 tree_node ca = {0};
656 tree_node cb = {0};
657 tree_node cc = {0};
658 tree_node cba = {0};
660 tree_node* expected_order[] = {
661 &root,
662 &c, &b, &a,
663 &ba, &ab, &aa
664 };
665 tree_node* actual_order[16]; // reserve more space in case s.t. goes wrong
667 cx_tree_link(&root, &a, tree_node_layout);
668 cx_tree_link(&root, &b, tree_node_layout);
669 cx_tree_link(&root, &c, tree_node_layout);
670 cx_tree_link(&a, &aa, tree_node_layout);
671 cx_tree_link(&a, &ab, tree_node_layout);
672 cx_tree_link(&b, &ba, tree_node_layout);
673 cx_tree_link(&c, &ca, tree_node_layout);
674 cx_tree_link(&c, &cb, tree_node_layout);
675 cx_tree_link(&c, &cc, tree_node_layout);
676 cx_tree_link(&cb, &cba, tree_node_layout);
677 CX_TEST_DO {
678 CxTreeVisitor iter = cx_tree_visitor(&root, tree_child_list);
679 unsigned chk = 0;
680 cx_foreach(tree_node*, node, iter) {
681 CX_TEST_ASSERT(node->data == 0);
682 node->data++;
683 actual_order[chk] = node;
684 chk++;
685 CX_TEST_ASSERT(node == iter.node);
686 if (node == &root) {
687 CX_TEST_ASSERT(iter.depth == 1);
688 } else if (node == &a || node == &b || node == &c) {
689 CX_TEST_ASSERT(iter.depth == 2);
690 } else {
691 CX_TEST_ASSERT(iter.depth == 3);
692 }
693 if (node == &c) {
694 cxTreeVisitorContinue(iter);
695 }
696 }
697 CX_TEST_ASSERT(iter.counter == 7);
698 CX_TEST_ASSERT(chk == 7);
699 for (unsigned i = 0 ; i < chk ; i++) {
700 CX_TEST_ASSERT(actual_order[i] == expected_order[i]);
701 CX_TEST_ASSERT(actual_order[i]->data == 1);
702 }
703 CX_TEST_ASSERT(ca.data == 0);
704 CX_TEST_ASSERT(cb.data == 0);
705 CX_TEST_ASSERT(cc.data == 0);
706 CX_TEST_ASSERT(cba.data == 0);
707 CX_TEST_ASSERT(iter.queue_next == NULL);
708 CX_TEST_ASSERT(iter.queue_last == NULL);
709 }
710 }
712 CX_TEST(test_tree_iterator_continue) {
713 tree_node root = {0};
714 tree_node a = {0};
715 tree_node b = {0};
716 tree_node c = {0};
717 tree_node aa = {0};
718 tree_node ab = {0};
719 tree_node ba = {0};
720 tree_node ca = {0};
721 tree_node cb = {0};
722 tree_node cc = {0};
723 tree_node cba = {0};
725 tree_node* expected_order[] = {
726 &root,
727 &c,
728 &b, &ba,
729 &a, &ab, &aa,
730 };
731 tree_node* actual_order[16]; // reserve more space in case s.t. goes wrong
733 cx_tree_link(&root, &a, tree_node_layout);
734 cx_tree_link(&root, &b, tree_node_layout);
735 cx_tree_link(&root, &c, tree_node_layout);
736 cx_tree_link(&a, &aa, tree_node_layout);
737 cx_tree_link(&a, &ab, tree_node_layout);
738 cx_tree_link(&b, &ba, tree_node_layout);
739 cx_tree_link(&c, &ca, tree_node_layout);
740 cx_tree_link(&c, &cb, tree_node_layout);
741 cx_tree_link(&c, &cc, tree_node_layout);
742 cx_tree_link(&cb, &cba, tree_node_layout);
743 CX_TEST_DO {
744 CxTreeIterator iter = cx_tree_iterator(&root, false, tree_child_list);
745 unsigned chk = 0;
746 cx_foreach(tree_node*, node, iter) {
747 CX_TEST_ASSERT(node->data == 0);
748 node->data++;
749 actual_order[chk] = node;
750 chk++;
751 CX_TEST_ASSERT(node == iter.node);
752 CX_TEST_ASSERT(!iter.exiting);
753 if (node == &root) {
754 CX_TEST_ASSERT(iter.depth == 1);
755 } else if (node == &a || node == &b || node == &c) {
756 CX_TEST_ASSERT(iter.depth == 2);
757 } else {
758 CX_TEST_ASSERT(iter.depth == 3);
759 }
760 if (node == &c) {
761 cxTreeIteratorContinue(iter);
762 }
763 }
764 CX_TEST_ASSERT(iter.counter == 7);
765 CX_TEST_ASSERT(chk == 7);
766 for (unsigned i = 0 ; i < chk ; i++) {
767 CX_TEST_ASSERT(actual_order[i] == expected_order[i]);
768 CX_TEST_ASSERT(actual_order[i]->data == 1);
769 }
770 CX_TEST_ASSERT(ca.data == 0);
771 CX_TEST_ASSERT(cb.data == 0);
772 CX_TEST_ASSERT(cc.data == 0);
773 CX_TEST_ASSERT(cba.data == 0);
774 CX_TEST_ASSERT(iter.stack == NULL);
775 }
776 }
778 CX_TEST(test_tree_iterator_continue_with_exit) {
779 tree_node root = {0};
780 tree_node a = {0};
781 tree_node b = {0};
782 tree_node c = {0};
783 tree_node aa = {0};
784 tree_node ab = {0};
785 tree_node ba = {0};
786 tree_node ca = {0};
787 tree_node cb = {0};
788 tree_node cc = {0};
789 tree_node cba = {0};
791 cx_tree_link(&root, &a, tree_node_layout);
792 cx_tree_link(&root, &b, tree_node_layout);
793 cx_tree_link(&root, &c, tree_node_layout);
794 cx_tree_link(&a, &aa, tree_node_layout);
795 cx_tree_link(&a, &ab, tree_node_layout);
796 cx_tree_link(&b, &ba, tree_node_layout);
797 cx_tree_link(&c, &ca, tree_node_layout);
798 cx_tree_link(&c, &cb, tree_node_layout);
799 cx_tree_link(&c, &cc, tree_node_layout);
800 cx_tree_link(&cb, &cba, tree_node_layout);
801 CX_TEST_DO {
802 CxTreeIterator iter = cx_tree_iterator(&root, true, tree_child_list);
803 unsigned chk = 0;
804 cx_foreach(tree_node*, node, iter) {
805 CX_TEST_ASSERT(iter.exiting || node->data == 0);
806 node->data++;
807 chk++;
808 CX_TEST_ASSERT(node == iter.node);
809 if (node == &root) {
810 CX_TEST_ASSERT(iter.depth == 1);
811 } else if (node == &a || node == &b || node == &c) {
812 CX_TEST_ASSERT(iter.depth == 2);
813 } else {
814 CX_TEST_ASSERT(iter.depth == 3);
815 }
816 if (node == &c) {
817 cxTreeIteratorContinue(iter);
818 }
819 }
820 CX_TEST_ASSERT(iter.counter == 7);
821 CX_TEST_ASSERT(chk == 14);
822 CX_TEST_ASSERT(iter.stack == NULL);
823 CX_TEST_ASSERT(root.data == 2);
824 CX_TEST_ASSERT(a.data == 2);
825 CX_TEST_ASSERT(b.data == 2);
826 CX_TEST_ASSERT(c.data == 2);
827 CX_TEST_ASSERT(aa.data == 2);
828 CX_TEST_ASSERT(ab.data == 2);
829 CX_TEST_ASSERT(ba.data == 2);
830 CX_TEST_ASSERT(ca.data == 0);
831 CX_TEST_ASSERT(cb.data == 0);
832 CX_TEST_ASSERT(cc.data == 0);
833 CX_TEST_ASSERT(cba.data == 0);
834 }
835 }
837 CxTestSuite *cx_test_suite_tree_low_level(void) {
838 CxTestSuite *suite = cx_test_suite_new("tree (low level)");
840 cx_test_register(suite, test_tree_link_new_child);
841 cx_test_register(suite, test_tree_link_add_child);
842 cx_test_register(suite, test_tree_link_move_to_other_parent);
843 cx_test_register(suite, test_tree_unlink);
844 cx_test_register(suite, test_tree_search);
845 cx_test_register(suite, test_tree_iterator_create_and_dispose);
846 cx_test_register(suite, test_tree_iterator_basic_only_enter);
847 cx_test_register(suite, test_tree_iterator_basic_enter_and_exit);
848 cx_test_register(suite, test_tree_iterator_xml);
849 cx_test_register(suite, test_tree_iterator_free_nodes);
850 cx_test_register(suite, test_tree_visitor);
851 cx_test_register(suite, test_tree_visitor_no_children);
852 cx_test_register(suite, test_tree_visitor_no_branching);
853 cx_test_register(suite, test_tree_visitor_continue);
854 cx_test_register(suite, test_tree_iterator_continue);
855 cx_test_register(suite, test_tree_iterator_continue_with_exit);
857 return suite;
858 }