tests/test_tree.c@387414a7afd8
tests/test_tree.c
Sun, 07 Jul 2024 14:56:44 +0200
- author
- Mike Becker <universe@uap-core.de>
- date
- Sun, 07 Jul 2024 14:56:44 +0200
- changeset 862
- 387414a7afd8
- parent 854
- fe0d69d72bcd
- child 866
- 1f636de4a63f
- permissions
- -rw-r--r--
change cx_tree_link() from prepending to appending children - fixes #391
/* * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. * * Copyright 2023 Mike Becker, Olaf Wintermann All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: * * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE * POSSIBILITY OF SUCH DAMAGE. */ #include "cx/tree.h" #include "cx/test.h" #include "util_allocator.h" typedef struct tree_node { struct tree_node *parent; struct tree_node *next; struct tree_node *prev; struct tree_node *children; int data; } tree_node; typedef struct tree_node2 { struct tree_node2 *parent; struct tree_node2 *next; struct tree_node2 *prev; struct tree_node2 *children; struct tree_node2 *last_child; int data; } tree_node2; #define tree_node_layout \ offsetof(tree_node, parent), offsetof(tree_node, children), -1, \ offsetof(tree_node, prev), offsetof(tree_node, next) #define tree_node2_layout \ offsetof(tree_node2, parent), offsetof(tree_node2, children),\ offsetof(tree_node2, last_child), \ offsetof(tree_node2, prev), offsetof(tree_node2, next) #define tree_children(type) offsetof(type, children), offsetof(type, next) CX_TEST(test_tree_link_new_child) { tree_node parent = {0}; tree_node child = {0}; CX_TEST_DO { cx_tree_link(&parent, &child, tree_node_layout); CX_TEST_ASSERT(parent.next == NULL); CX_TEST_ASSERT(parent.prev == NULL); CX_TEST_ASSERT(parent.parent == NULL); CX_TEST_ASSERT(parent.children == &child); CX_TEST_ASSERT(child.parent == &parent); CX_TEST_ASSERT(child.next == NULL); CX_TEST_ASSERT(child.prev == NULL); CX_TEST_ASSERT(child.children == NULL); } } CX_TEST(test_tree_link_add_child) { tree_node parent = {0}; tree_node child1 = {0}; tree_node child2 = {0}; tree_node child3 = {0}; CX_TEST_DO { cx_tree_link(&parent, &child1, tree_node_layout); cx_tree_link(&parent, &child2, tree_node_layout); cx_tree_link(&parent, &child3, tree_node_layout); CX_TEST_ASSERT(parent.next == NULL); CX_TEST_ASSERT(parent.prev == NULL); CX_TEST_ASSERT(parent.parent == NULL); CX_TEST_ASSERT(parent.children == &child1); CX_TEST_ASSERT(child1.parent == &parent); CX_TEST_ASSERT(child2.parent == &parent); CX_TEST_ASSERT(child3.parent == &parent); CX_TEST_ASSERT(child1.children == NULL); CX_TEST_ASSERT(child2.children == NULL); CX_TEST_ASSERT(child3.children == NULL); CX_TEST_ASSERT(child1.prev == NULL); CX_TEST_ASSERT(child1.next == &child2); CX_TEST_ASSERT(child2.prev == &child1); CX_TEST_ASSERT(child2.next == &child3); CX_TEST_ASSERT(child3.prev == &child2); CX_TEST_ASSERT(child3.next == NULL); } } CX_TEST(test_tree_link_move_to_other_parent) { tree_node parent = {0}; tree_node child1 = {0}; tree_node child2 = {0}; tree_node child3 = {0}; cx_tree_link(&parent, &child1, tree_node_layout); cx_tree_link(&parent, &child2, tree_node_layout); cx_tree_link(&parent, &child3, tree_node_layout); CX_TEST_DO { cx_tree_link(&child3, &child2, tree_node_layout); CX_TEST_ASSERT(parent.next == NULL); CX_TEST_ASSERT(parent.prev == NULL); CX_TEST_ASSERT(parent.parent == NULL); CX_TEST_ASSERT(parent.children == &child1); CX_TEST_ASSERT(child1.parent == &parent); CX_TEST_ASSERT(child2.parent == &child3); CX_TEST_ASSERT(child3.parent == &parent); CX_TEST_ASSERT(child1.children == NULL); CX_TEST_ASSERT(child2.children == NULL); CX_TEST_ASSERT(child3.children == &child2); CX_TEST_ASSERT(child1.prev == NULL); CX_TEST_ASSERT(child1.next == &child3); CX_TEST_ASSERT(child3.prev == &child1); CX_TEST_ASSERT(child3.next == NULL); CX_TEST_ASSERT(child2.prev == NULL); CX_TEST_ASSERT(child2.next == NULL); } } CX_TEST(test_tree_unlink) { tree_node parent = {0}; tree_node child1 = {0}; tree_node child2 = {0}; tree_node child3 = {0}; cx_tree_link(&parent, &child1, tree_node_layout); cx_tree_link(&parent, &child3, tree_node_layout); cx_tree_link(&child3, &child2, tree_node_layout); CX_TEST_DO { cx_tree_unlink(&child3, tree_node_layout); CX_TEST_ASSERT(parent.next == NULL); CX_TEST_ASSERT(parent.prev == NULL); CX_TEST_ASSERT(parent.parent == NULL); CX_TEST_ASSERT(parent.children == &child1); CX_TEST_ASSERT(child1.parent == &parent); CX_TEST_ASSERT(child1.children == NULL); CX_TEST_ASSERT(child1.prev == NULL); CX_TEST_ASSERT(child1.next == NULL); // child 3 is unlinked CX_TEST_ASSERT(child3.parent == NULL); CX_TEST_ASSERT(child3.prev == NULL); CX_TEST_ASSERT(child3.next == NULL); // child 2 is still child of the unlinked child 3 CX_TEST_ASSERT(child3.children == &child2); CX_TEST_ASSERT(child2.parent == &child3); CX_TEST_ASSERT(child2.children == NULL); CX_TEST_ASSERT(child2.prev == NULL); CX_TEST_ASSERT(child2.next == NULL); // unlink last child from parent cx_tree_unlink(&child1, tree_node_layout); CX_TEST_ASSERT(parent.next == NULL); CX_TEST_ASSERT(parent.prev == NULL); CX_TEST_ASSERT(parent.parent == NULL); CX_TEST_ASSERT(parent.children == NULL); CX_TEST_ASSERT(child1.parent == NULL); } } CX_TEST(test_tree2_link_new_child) { tree_node2 parent = {0}; tree_node2 child = {0}; CX_TEST_DO { cx_tree_link(&parent, &child, tree_node2_layout); CX_TEST_ASSERT(parent.next == NULL); CX_TEST_ASSERT(parent.prev == NULL); CX_TEST_ASSERT(parent.parent == NULL); CX_TEST_ASSERT(parent.children == &child); CX_TEST_ASSERT(parent.last_child == &child); CX_TEST_ASSERT(child.parent == &parent); CX_TEST_ASSERT(child.next == NULL); CX_TEST_ASSERT(child.prev == NULL); CX_TEST_ASSERT(child.children == NULL); CX_TEST_ASSERT(child.last_child == NULL); } } CX_TEST(test_tree2_link_add_child) { tree_node2 parent = {0}; tree_node2 child1 = {0}; tree_node2 child2 = {0}; tree_node2 child3 = {0}; CX_TEST_DO { cx_tree_link(&parent, &child1, tree_node2_layout); cx_tree_link(&parent, &child2, tree_node2_layout); cx_tree_link(&parent, &child3, tree_node2_layout); CX_TEST_ASSERT(parent.next == NULL); CX_TEST_ASSERT(parent.prev == NULL); CX_TEST_ASSERT(parent.parent == NULL); CX_TEST_ASSERT(parent.children == &child1); CX_TEST_ASSERT(parent.last_child == &child3); CX_TEST_ASSERT(child1.parent == &parent); CX_TEST_ASSERT(child2.parent == &parent); CX_TEST_ASSERT(child3.parent == &parent); CX_TEST_ASSERT(child1.children == NULL); CX_TEST_ASSERT(child2.children == NULL); CX_TEST_ASSERT(child3.children == NULL); CX_TEST_ASSERT(child1.last_child == NULL); CX_TEST_ASSERT(child2.last_child == NULL); CX_TEST_ASSERT(child3.last_child == NULL); CX_TEST_ASSERT(child1.prev == NULL); CX_TEST_ASSERT(child1.next == &child2); CX_TEST_ASSERT(child2.prev == &child1); CX_TEST_ASSERT(child2.next == &child3); CX_TEST_ASSERT(child3.prev == &child2); CX_TEST_ASSERT(child3.next == NULL); } } CX_TEST(test_tree2_link_move_to_other_parent) { tree_node2 parent = {0}; tree_node2 child1 = {0}; tree_node2 child2 = {0}; tree_node2 child3 = {0}; cx_tree_link(&parent, &child1, tree_node2_layout); cx_tree_link(&parent, &child2, tree_node2_layout); cx_tree_link(&parent, &child3, tree_node2_layout); CX_TEST_DO { cx_tree_link(&child3, &child2, tree_node2_layout); CX_TEST_ASSERT(parent.next == NULL); CX_TEST_ASSERT(parent.prev == NULL); CX_TEST_ASSERT(parent.parent == NULL); CX_TEST_ASSERT(parent.children == &child1); CX_TEST_ASSERT(parent.last_child == &child3); CX_TEST_ASSERT(child1.parent == &parent); CX_TEST_ASSERT(child2.parent == &child3); CX_TEST_ASSERT(child3.parent == &parent); CX_TEST_ASSERT(child1.children == NULL); CX_TEST_ASSERT(child2.children == NULL); CX_TEST_ASSERT(child3.children == &child2); CX_TEST_ASSERT(child1.last_child == NULL); CX_TEST_ASSERT(child2.last_child == NULL); CX_TEST_ASSERT(child3.last_child == &child2); CX_TEST_ASSERT(child1.prev == NULL); CX_TEST_ASSERT(child1.next == &child3); CX_TEST_ASSERT(child3.prev == &child1); CX_TEST_ASSERT(child3.next == NULL); CX_TEST_ASSERT(child2.prev == NULL); CX_TEST_ASSERT(child2.next == NULL); } } CX_TEST(test_tree2_unlink) { tree_node2 parent = {0}; tree_node2 child1 = {0}; tree_node2 child2 = {0}; tree_node2 child3 = {0}; cx_tree_link(&parent, &child1, tree_node2_layout); cx_tree_link(&parent, &child3, tree_node2_layout); cx_tree_link(&child3, &child2, tree_node2_layout); CX_TEST_DO { cx_tree_unlink(&child3, tree_node2_layout); CX_TEST_ASSERT(parent.next == NULL); CX_TEST_ASSERT(parent.prev == NULL); CX_TEST_ASSERT(parent.parent == NULL); CX_TEST_ASSERT(parent.children == &child1); CX_TEST_ASSERT(parent.last_child == &child1); CX_TEST_ASSERT(child1.parent == &parent); CX_TEST_ASSERT(child1.children == NULL); CX_TEST_ASSERT(child1.last_child == NULL); CX_TEST_ASSERT(child1.prev == NULL); CX_TEST_ASSERT(child1.next == NULL); // child 3 is unlinked CX_TEST_ASSERT(child3.parent == NULL); CX_TEST_ASSERT(child3.prev == NULL); CX_TEST_ASSERT(child3.next == NULL); // child 2 is still child of the unlinked child 3 CX_TEST_ASSERT(child3.children == &child2); CX_TEST_ASSERT(child3.last_child == &child2); CX_TEST_ASSERT(child2.parent == &child3); CX_TEST_ASSERT(child2.children == NULL); CX_TEST_ASSERT(child2.last_child == NULL); CX_TEST_ASSERT(child2.prev == NULL); CX_TEST_ASSERT(child2.next == NULL); // unlink last child from parent cx_tree_unlink(&child1, tree_node2_layout); CX_TEST_ASSERT(parent.next == NULL); CX_TEST_ASSERT(parent.prev == NULL); CX_TEST_ASSERT(parent.parent == NULL); CX_TEST_ASSERT(parent.children == NULL); CX_TEST_ASSERT(parent.last_child == NULL); CX_TEST_ASSERT(child1.parent == NULL); } } static int test_tree_search_function(void const *n, void const *d) { tree_node const *node = n; int data = *((int const*)d); if (data < node->data) return -1; else if (data == node->data) return 0; else return data - node->data; } CX_TEST(test_tree_search) { tree_node root = {0}; tree_node a = {0}; tree_node b = {0}; tree_node c = {0}; tree_node aa = {0}; tree_node ab = {0}; tree_node ba = {0}; tree_node ca = {0}; tree_node cb = {0}; tree_node cc = {0}; tree_node cba = {0}; int testdata[] = {0, 10, 14, 18, 20, 25, 30, 32, 34, 36, 40}; tree_node* testnodes[] = {&root, &a, &aa, &ab, &b, &ba, &c, &ca, &cb, &cba, &cc}; for (unsigned i = 0 ; i <= 10 ; i++) { testnodes[i]->data = testdata[i]; } cx_tree_link(&root, &a, tree_node_layout); cx_tree_link(&root, &b, tree_node_layout); cx_tree_link(&root, &c, tree_node_layout); cx_tree_link(&a, &aa, tree_node_layout); cx_tree_link(&a, &ab, tree_node_layout); cx_tree_link(&b, &ba, tree_node_layout); cx_tree_link(&c, &ca, tree_node_layout); cx_tree_link(&c, &cb, tree_node_layout); cx_tree_link(&c, &cc, tree_node_layout); cx_tree_link(&cb, &cba, tree_node_layout); int s; int r; tree_node *n; CX_TEST_DO { for (unsigned i = 0 ; i <= 10 ; i++) { s = testdata[i]; r = cx_tree_search(&root, &s, test_tree_search_function, (void **) &n, tree_children(tree_node)); CX_TEST_ASSERT(r == 0); CX_TEST_ASSERT(n == testnodes[i]); } s = -5; r = cx_tree_search(&root, &s, test_tree_search_function, (void **) &n, tree_children(tree_node)); CX_TEST_ASSERT(r < 0); CX_TEST_ASSERT(n == NULL); s = 26; r = cx_tree_search(&root, &s, test_tree_search_function, (void **) &n, tree_children(tree_node)); CX_TEST_ASSERT(r > 0); CX_TEST_ASSERT(n == &ba); s = 35; r = cx_tree_search(&root, &s, test_tree_search_function, (void **) &n, tree_children(tree_node)); CX_TEST_ASSERT(r > 0); CX_TEST_ASSERT(n == &cb); s = 38; r = cx_tree_search(&root, &s, test_tree_search_function, (void **) &n, tree_children(tree_node)); CX_TEST_ASSERT(r > 0); CX_TEST_ASSERT(n == &cba); s = 42; r = cx_tree_search(&root, &s, test_tree_search_function, (void **) &n, tree_children(tree_node)); CX_TEST_ASSERT(r > 0); CX_TEST_ASSERT(n == &cc); } } CX_TEST(test_tree_iterator_create_and_dispose) { tree_node root; CX_TEST_DO { CxTreeIterator iter = cx_tree_iterator(&root, false, tree_children(tree_node)); CX_TEST_ASSERT(!iter.visit_on_exit); CX_TEST_ASSERT(!iter.exiting); CX_TEST_ASSERT(iter.counter == 1); CX_TEST_ASSERT(iter.node == &root); CX_TEST_ASSERT(!iter.base.mutating); CX_TEST_ASSERT(!iter.base.remove); CX_TEST_ASSERT(iter.stack != NULL); CX_TEST_ASSERT(iter.stack_capacity > 0); CX_TEST_ASSERT(iter.stack_size == 1); CX_TEST_ASSERT(iter.depth == 1); CX_TEST_ASSERT(iter.loc_next == offsetof(tree_node, next)); CX_TEST_ASSERT(iter.loc_children == offsetof(tree_node, children)); cxTreeIteratorDispose(&iter); CX_TEST_ASSERT(iter.stack == NULL); } } CX_TEST(test_tree_iterator_basic_only_enter) { tree_node root = {0}; tree_node a = {0}; tree_node b = {0}; tree_node c = {0}; tree_node aa = {0}; tree_node ab = {0}; tree_node ba = {0}; tree_node ca = {0}; tree_node cb = {0}; tree_node cc = {0}; tree_node cba = {0}; tree_node* expected_order[] = { &root, &a, &aa, &ab, &b, &ba, &c, &ca, &cb, &cba, &cc, }; tree_node* actual_order[16]; // reserve more space in case s.t. goes wrong cx_tree_link(&root, &a, tree_node_layout); cx_tree_link(&root, &b, tree_node_layout); cx_tree_link(&root, &c, tree_node_layout); cx_tree_link(&a, &aa, tree_node_layout); cx_tree_link(&a, &ab, tree_node_layout); cx_tree_link(&b, &ba, tree_node_layout); cx_tree_link(&c, &ca, tree_node_layout); cx_tree_link(&c, &cb, tree_node_layout); cx_tree_link(&c, &cc, tree_node_layout); cx_tree_link(&cb, &cba, tree_node_layout); CX_TEST_DO { CxTreeIterator iter = cx_tree_iterator(&root, false, tree_children(tree_node)); unsigned chk = 0; cx_foreach(tree_node*, node, iter) { CX_TEST_ASSERT(node->data == 0); node->data++; actual_order[chk] = node; chk++; CX_TEST_ASSERT(node == iter.node); CX_TEST_ASSERT(!iter.exiting); if (node == &root) { CX_TEST_ASSERT(iter.depth == 1); } else if (node == &a || node == &b || node == &c) { CX_TEST_ASSERT(iter.depth == 2); } else if (node == &cba) { CX_TEST_ASSERT(iter.depth == 4); } else { CX_TEST_ASSERT(iter.depth == 3); } } CX_TEST_ASSERT(iter.counter == 11); CX_TEST_ASSERT(chk == 11); for (unsigned i = 0 ; i < chk ; i++) { CX_TEST_ASSERT(actual_order[i] == expected_order[i]); CX_TEST_ASSERT(actual_order[i]->data == 1); } CX_TEST_ASSERT(iter.stack == NULL); } } CX_TEST(test_tree_iterator_basic_enter_and_exit) { tree_node root = {0}; tree_node a = {0}; tree_node b = {0}; tree_node c = {0}; tree_node aa = {0}; tree_node ab = {0}; tree_node ba = {0}; tree_node ca = {0}; tree_node cb = {0}; tree_node cc = {0}; tree_node cba = {0}; cx_tree_link(&root, &a, tree_node_layout); cx_tree_link(&root, &b, tree_node_layout); cx_tree_link(&root, &c, tree_node_layout); cx_tree_link(&a, &aa, tree_node_layout); cx_tree_link(&a, &ab, tree_node_layout); cx_tree_link(&b, &ba, tree_node_layout); cx_tree_link(&c, &ca, tree_node_layout); cx_tree_link(&c, &cb, tree_node_layout); cx_tree_link(&c, &cc, tree_node_layout); cx_tree_link(&cb, &cba, tree_node_layout); CX_TEST_DO { CxTreeIterator iter = cx_tree_iterator(&root, true, tree_children(tree_node)); unsigned chk = 0; cx_foreach(tree_node*, node, iter) { CX_TEST_ASSERT(iter.exiting || node->data == 0); node->data++; chk++; CX_TEST_ASSERT(node == iter.node); if (node == &root) { CX_TEST_ASSERT(iter.depth == 1); } else if (node == &a || node == &b || node == &c) { CX_TEST_ASSERT(iter.depth == 2); } else if (node == &cba) { CX_TEST_ASSERT(iter.depth == 4); } else { CX_TEST_ASSERT(iter.depth == 3); } } CX_TEST_ASSERT(iter.counter == 11); CX_TEST_ASSERT(chk == 22); CX_TEST_ASSERT(iter.stack == NULL); CX_TEST_ASSERT(root.data == 2); CX_TEST_ASSERT(a.data == 2); CX_TEST_ASSERT(b.data == 2); CX_TEST_ASSERT(c.data == 2); CX_TEST_ASSERT(aa.data == 2); CX_TEST_ASSERT(ab.data == 2); CX_TEST_ASSERT(ba.data == 2); CX_TEST_ASSERT(ca.data == 2); CX_TEST_ASSERT(cb.data == 2); CX_TEST_ASSERT(cc.data == 2); CX_TEST_ASSERT(cba.data == 2); } } typedef struct test_xml_node { struct tree_node base; char const* name; } test_xml_node; CX_TEST(test_tree_iterator_xml) { test_xml_node project = {0}; test_xml_node config = {0}; test_xml_node var1 = {0}; test_xml_node var2 = {0}; test_xml_node var3 = {0}; test_xml_node dependency1 = {0}; test_xml_node dependency1make = {0}; test_xml_node dependency2 = {0}; test_xml_node dependency2lang = {0}; test_xml_node dependency2make = {0}; test_xml_node target = {0}; test_xml_node target_feature = {0}; test_xml_node target_feature_dependencies = {0}; test_xml_node target_dependencies = {0}; project.name = "project"; config.name = "config"; var1.name = "var"; var2.name = "var"; var3.name = "var"; dependency1.name = "dependency"; dependency1make.name = "make"; dependency2.name = "dependency"; dependency2lang.name = "lang"; dependency2make.name = "make"; target.name = "target"; target_feature.name = "feature"; target_dependencies.name = "dependencies"; target_feature_dependencies.name = "dependencies"; cx_tree_link(&project, &config, tree_node_layout); cx_tree_link(&project, &dependency1, tree_node_layout); cx_tree_link(&project, &dependency2, tree_node_layout); cx_tree_link(&project, &target, tree_node_layout); cx_tree_link(&config, &var1, tree_node_layout); cx_tree_link(&config, &var2, tree_node_layout); cx_tree_link(&config, &var3, tree_node_layout); cx_tree_link(&dependency1, &dependency1make, tree_node_layout); cx_tree_link(&dependency2, &dependency2lang, tree_node_layout); cx_tree_link(&dependency2, &dependency2make, tree_node_layout); cx_tree_link(&target, &target_feature, tree_node_layout); cx_tree_link(&target, &target_dependencies, tree_node_layout); cx_tree_link(&target_feature, &target_feature_dependencies, tree_node_layout); char const *expected = "<project><config><var></var><var></var><var></var></config>" "<dependency><make></make></dependency><dependency><lang></lang><make></make></dependency>" "<target><feature><dependencies></dependencies></feature><dependencies></dependencies></target></project>"; char *actual = malloc(512); CX_TEST_DO { CxTreeIterator iter = cx_tree_iterator(&project, true, tree_children(tree_node)); size_t i = 0; cx_foreach(test_xml_node*, node, iter) { size_t len = strlen(node->name); actual[i++] = '<'; if (iter.exiting) { actual[i++] = '/'; } memcpy(actual+i, node->name, len); i += len; actual[i++] = '>'; } actual[i] = '\0'; CX_TEST_ASSERT(0 == strcmp(expected, actual)); } free(actual); } CX_TEST(test_tree_iterator_free_nodes) { CxTestingAllocator talloc; cx_testing_allocator_init(&talloc); CxAllocator *alloc = &talloc.base; CX_TEST_DO { tree_node *root = cxCalloc(alloc, 1, sizeof(tree_node)); tree_node *a = cxCalloc(alloc, 1, sizeof(tree_node)); tree_node *b = cxCalloc(alloc, 1, sizeof(tree_node)); tree_node *c = cxCalloc(alloc, 1, sizeof(tree_node)); tree_node *aa = cxCalloc(alloc, 1, sizeof(tree_node)); tree_node *ab = cxCalloc(alloc, 1, sizeof(tree_node)); tree_node *ba = cxCalloc(alloc, 1, sizeof(tree_node)); tree_node *ca = cxCalloc(alloc, 1, sizeof(tree_node)); tree_node *cb = cxCalloc(alloc, 1, sizeof(tree_node)); tree_node *cc = cxCalloc(alloc, 1, sizeof(tree_node)); tree_node *cba = cxCalloc(alloc, 1, sizeof(tree_node)); cx_tree_link(root, a, tree_node_layout); cx_tree_link(root, b, tree_node_layout); cx_tree_link(root, c, tree_node_layout); cx_tree_link(a, aa, tree_node_layout); cx_tree_link(a, ab, tree_node_layout); cx_tree_link(b, ba, tree_node_layout); cx_tree_link(c, ca, tree_node_layout); cx_tree_link(c, cb, tree_node_layout); cx_tree_link(c, cc, tree_node_layout); cx_tree_link(cb, cba, tree_node_layout); CxTreeIterator iter = cx_tree_iterator(root, true, tree_children(tree_node)); cx_foreach(tree_node *, node, iter) { if (iter.exiting) { cxFree(alloc,node); } } CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); } cx_testing_allocator_destroy(&talloc); } CX_TEST(test_tree_visitor_create_and_dispose) { tree_node root; tree_node child; cx_tree_link(&root, &child, tree_node_layout); CX_TEST_DO { CxTreeVisitor iter = cx_tree_visitor(&root, tree_children(tree_node)); CX_TEST_ASSERT(iter.counter == 1); CX_TEST_ASSERT(iter.node == &root); CX_TEST_ASSERT(!iter.base.mutating); CX_TEST_ASSERT(!iter.base.remove); CX_TEST_ASSERT(iter.queue_next != NULL); CX_TEST_ASSERT(iter.queue_last != NULL); CX_TEST_ASSERT(iter.depth == 1); CX_TEST_ASSERT(iter.loc_next == offsetof(tree_node, next)); CX_TEST_ASSERT(iter.loc_children == offsetof(tree_node, children)); cxTreeVisitorDispose(&iter); CX_TEST_ASSERT(iter.queue_next == NULL); CX_TEST_ASSERT(iter.queue_last == NULL); } } CX_TEST(test_tree_visitor) { tree_node root = {0}; tree_node a = {0}; tree_node b = {0}; tree_node c = {0}; tree_node aa = {0}; tree_node ab = {0}; tree_node ba = {0}; tree_node ca = {0}; tree_node cb = {0}; tree_node cc = {0}; tree_node cba = {0}; tree_node* expected_order[] = { &root, &a, &b, &c, &aa, &ab, &ba, &ca, &cb, &cc, &cba }; tree_node* actual_order[16]; // reserve more space in case s.t. goes wrong cx_tree_link(&root, &a, tree_node_layout); cx_tree_link(&root, &b, tree_node_layout); cx_tree_link(&root, &c, tree_node_layout); cx_tree_link(&a, &aa, tree_node_layout); cx_tree_link(&a, &ab, tree_node_layout); cx_tree_link(&b, &ba, tree_node_layout); cx_tree_link(&c, &ca, tree_node_layout); cx_tree_link(&c, &cb, tree_node_layout); cx_tree_link(&c, &cc, tree_node_layout); cx_tree_link(&cb, &cba, tree_node_layout); CX_TEST_DO { CxTreeVisitor iter = cx_tree_visitor(&root, tree_children(tree_node)); unsigned chk = 0; cx_foreach(tree_node*, node, iter) { CX_TEST_ASSERT(node->data == 0); node->data++; actual_order[chk] = node; chk++; CX_TEST_ASSERT(node == iter.node); if (node == &root) { CX_TEST_ASSERT(iter.depth == 1); } else if (node == &a || node == &b || node == &c) { CX_TEST_ASSERT(iter.depth == 2); } else if (node == &cba) { CX_TEST_ASSERT(iter.depth == 4); } else { CX_TEST_ASSERT(iter.depth == 3); } } CX_TEST_ASSERT(iter.counter == 11); CX_TEST_ASSERT(chk == 11); for (unsigned i = 0 ; i < chk ; i++) { CX_TEST_ASSERT(actual_order[i] == expected_order[i]); CX_TEST_ASSERT(actual_order[i]->data == 1); } CX_TEST_ASSERT(iter.queue_next == NULL); CX_TEST_ASSERT(iter.queue_last == NULL); } } CX_TEST(test_tree_visitor_no_children) { tree_node root = {0}; CX_TEST_DO { CxTreeVisitor iter = cx_tree_visitor(&root, tree_children(tree_node)); unsigned chk = 0; cx_foreach(tree_node*, node, iter) { CX_TEST_ASSERT(node == iter.node); chk++; } CX_TEST_ASSERT(iter.counter == 1); CX_TEST_ASSERT(chk == 1); CX_TEST_ASSERT(iter.queue_next == NULL); CX_TEST_ASSERT(iter.queue_last == NULL); } } CX_TEST(test_tree_visitor_no_branching) { tree_node root = {0}; tree_node a = {0}; tree_node b = {0}; tree_node c = {0}; tree_node* expected_order[] = { &root, &a, &b, &c }; tree_node* actual_order[4]; cx_tree_link(&root, &a, tree_node_layout); cx_tree_link(&a, &b, tree_node_layout); cx_tree_link(&b, &c, tree_node_layout); CX_TEST_DO { CxTreeVisitor iter = cx_tree_visitor(&root, tree_children(tree_node)); unsigned chk = 0; cx_foreach(tree_node*, node, iter) { CX_TEST_ASSERT(node == iter.node); CX_TEST_ASSERT(node->data == 0); node->data++; actual_order[chk] = node; chk++; } CX_TEST_ASSERT(iter.counter == 4); CX_TEST_ASSERT(chk == 4); CX_TEST_ASSERT(iter.queue_next == NULL); CX_TEST_ASSERT(iter.queue_last == NULL); for (unsigned i = 0 ; i < chk ; i++) { CX_TEST_ASSERT(actual_order[i] == expected_order[i]); CX_TEST_ASSERT(actual_order[i]->data == 1); } } } CX_TEST(test_tree_visitor_continue) { tree_node root = {0}; tree_node a = {0}; tree_node b = {0}; tree_node c = {0}; tree_node aa = {0}; tree_node ab = {0}; tree_node ba = {0}; tree_node ca = {0}; tree_node cb = {0}; tree_node cc = {0}; tree_node cba = {0}; tree_node* expected_order[] = { &root, &a, &b, &c, &aa, &ab, &ba }; tree_node* actual_order[16]; // reserve more space in case s.t. goes wrong cx_tree_link(&root, &a, tree_node_layout); cx_tree_link(&root, &b, tree_node_layout); cx_tree_link(&root, &c, tree_node_layout); cx_tree_link(&a, &aa, tree_node_layout); cx_tree_link(&a, &ab, tree_node_layout); cx_tree_link(&b, &ba, tree_node_layout); cx_tree_link(&c, &ca, tree_node_layout); cx_tree_link(&c, &cb, tree_node_layout); cx_tree_link(&c, &cc, tree_node_layout); cx_tree_link(&cb, &cba, tree_node_layout); CX_TEST_DO { CxTreeVisitor iter = cx_tree_visitor(&root, tree_children(tree_node)); unsigned chk = 0; cx_foreach(tree_node*, node, iter) { CX_TEST_ASSERT(node->data == 0); node->data++; actual_order[chk] = node; chk++; CX_TEST_ASSERT(node == iter.node); if (node == &root) { CX_TEST_ASSERT(iter.depth == 1); } else if (node == &a || node == &b || node == &c) { CX_TEST_ASSERT(iter.depth == 2); } else { CX_TEST_ASSERT(iter.depth == 3); } if (node == &c) { cxTreeVisitorContinue(iter); } } CX_TEST_ASSERT(iter.counter == 7); CX_TEST_ASSERT(chk == 7); for (unsigned i = 0 ; i < chk ; i++) { CX_TEST_ASSERT(actual_order[i] == expected_order[i]); CX_TEST_ASSERT(actual_order[i]->data == 1); } CX_TEST_ASSERT(ca.data == 0); CX_TEST_ASSERT(cb.data == 0); CX_TEST_ASSERT(cc.data == 0); CX_TEST_ASSERT(cba.data == 0); CX_TEST_ASSERT(iter.queue_next == NULL); CX_TEST_ASSERT(iter.queue_last == NULL); } } CX_TEST(test_tree_iterator_continue) { tree_node root = {0}; tree_node a = {0}; tree_node b = {0}; tree_node c = {0}; tree_node aa = {0}; tree_node ab = {0}; tree_node ba = {0}; tree_node ca = {0}; tree_node cb = {0}; tree_node cc = {0}; tree_node cba = {0}; tree_node *expected_order[] = { &root, &a, &aa, &ab, &b, &ba, &c, }; tree_node* actual_order[16]; // reserve more space in case s.t. goes wrong cx_tree_link(&root, &a, tree_node_layout); cx_tree_link(&root, &b, tree_node_layout); cx_tree_link(&root, &c, tree_node_layout); cx_tree_link(&a, &aa, tree_node_layout); cx_tree_link(&a, &ab, tree_node_layout); cx_tree_link(&b, &ba, tree_node_layout); cx_tree_link(&c, &ca, tree_node_layout); cx_tree_link(&c, &cb, tree_node_layout); cx_tree_link(&c, &cc, tree_node_layout); cx_tree_link(&cb, &cba, tree_node_layout); CX_TEST_DO { CxTreeIterator iter = cx_tree_iterator(&root, false, tree_children(tree_node)); unsigned chk = 0; cx_foreach(tree_node*, node, iter) { CX_TEST_ASSERT(node->data == 0); node->data++; actual_order[chk] = node; chk++; CX_TEST_ASSERT(node == iter.node); CX_TEST_ASSERT(!iter.exiting); if (node == &root) { CX_TEST_ASSERT(iter.depth == 1); } else if (node == &a || node == &b || node == &c) { CX_TEST_ASSERT(iter.depth == 2); } else { CX_TEST_ASSERT(iter.depth == 3); } if (node == &c) { cxTreeIteratorContinue(iter); } } CX_TEST_ASSERT(iter.counter == 7); CX_TEST_ASSERT(chk == 7); for (unsigned i = 0 ; i < chk ; i++) { CX_TEST_ASSERT(actual_order[i] == expected_order[i]); CX_TEST_ASSERT(actual_order[i]->data == 1); } CX_TEST_ASSERT(ca.data == 0); CX_TEST_ASSERT(cb.data == 0); CX_TEST_ASSERT(cc.data == 0); CX_TEST_ASSERT(cba.data == 0); CX_TEST_ASSERT(iter.stack == NULL); } } CX_TEST(test_tree_iterator_continue_with_exit) { tree_node root = {0}; tree_node a = {0}; tree_node b = {0}; tree_node c = {0}; tree_node aa = {0}; tree_node ab = {0}; tree_node ba = {0}; tree_node ca = {0}; tree_node cb = {0}; tree_node cc = {0}; tree_node cba = {0}; cx_tree_link(&root, &a, tree_node_layout); cx_tree_link(&root, &b, tree_node_layout); cx_tree_link(&root, &c, tree_node_layout); cx_tree_link(&a, &aa, tree_node_layout); cx_tree_link(&a, &ab, tree_node_layout); cx_tree_link(&b, &ba, tree_node_layout); cx_tree_link(&c, &ca, tree_node_layout); cx_tree_link(&c, &cb, tree_node_layout); cx_tree_link(&c, &cc, tree_node_layout); cx_tree_link(&cb, &cba, tree_node_layout); CX_TEST_DO { CxTreeIterator iter = cx_tree_iterator(&root, true, tree_children(tree_node)); unsigned chk = 0; cx_foreach(tree_node*, node, iter) { CX_TEST_ASSERT(iter.exiting || node->data == 0); node->data++; chk++; CX_TEST_ASSERT(node == iter.node); if (node == &root) { CX_TEST_ASSERT(iter.depth == 1); } else if (node == &a || node == &b || node == &c) { CX_TEST_ASSERT(iter.depth == 2); } else { CX_TEST_ASSERT(iter.depth == 3); } if (node == &c) { cxTreeIteratorContinue(iter); } } CX_TEST_ASSERT(iter.counter == 7); CX_TEST_ASSERT(chk == 14); CX_TEST_ASSERT(iter.stack == NULL); CX_TEST_ASSERT(root.data == 2); CX_TEST_ASSERT(a.data == 2); CX_TEST_ASSERT(b.data == 2); CX_TEST_ASSERT(c.data == 2); CX_TEST_ASSERT(aa.data == 2); CX_TEST_ASSERT(ab.data == 2); CX_TEST_ASSERT(ba.data == 2); CX_TEST_ASSERT(ca.data == 0); CX_TEST_ASSERT(cb.data == 0); CX_TEST_ASSERT(cc.data == 0); CX_TEST_ASSERT(cba.data == 0); } } CxTestSuite *cx_test_suite_tree_low_level(void) { CxTestSuite *suite = cx_test_suite_new("tree (low level)"); cx_test_register(suite, test_tree_link_new_child); cx_test_register(suite, test_tree_link_add_child); cx_test_register(suite, test_tree_link_move_to_other_parent); cx_test_register(suite, test_tree_unlink); cx_test_register(suite, test_tree2_link_new_child); cx_test_register(suite, test_tree2_link_add_child); cx_test_register(suite, test_tree2_link_move_to_other_parent); cx_test_register(suite, test_tree2_unlink); cx_test_register(suite, test_tree_search); cx_test_register(suite, test_tree_iterator_create_and_dispose); cx_test_register(suite, test_tree_iterator_basic_only_enter); cx_test_register(suite, test_tree_iterator_basic_enter_and_exit); cx_test_register(suite, test_tree_iterator_xml); cx_test_register(suite, test_tree_iterator_free_nodes); cx_test_register(suite, test_tree_visitor); cx_test_register(suite, test_tree_visitor_no_children); cx_test_register(suite, test_tree_visitor_no_branching); cx_test_register(suite, test_tree_visitor_continue); cx_test_register(suite, test_tree_iterator_continue); cx_test_register(suite, test_tree_iterator_continue_with_exit); return suite; }
