tests/test_tree.c@1f636de4a63f
tests/test_tree.c
Mon, 19 Aug 2024 20:46:36 +0200
- author
- Mike Becker <universe@uap-core.de>
- date
- Mon, 19 Aug 2024 20:46:36 +0200
- branch
- feature/tree_add
- changeset 866
- 1f636de4a63f
- parent 862
- 387414a7afd8
- child 871
- e29c1f96646d
- permissions
- -rw-r--r--
complete cx_tree_add() implementations
resolves #390 - but we still need more test coverage
/* * 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; typedef struct tree_node_file { struct tree_node_file *parent; struct tree_node_file *next; struct tree_node_file *prev; struct tree_node_file *children; struct tree_node_file *last_child; char const *path; } tree_node_file; static void *create_tree_node_file( void const *dptr, void const *nptr, void *allocator) { if (allocator == NULL) allocator = cxDefaultAllocator; char const *data = dptr; tree_node_file const *existing = nptr; if (existing != NULL && strcmp(existing->path, data) == 0) { return (void *) existing; } else { tree_node_file *node = cxMalloc(allocator, sizeof(tree_node_file)); node->path = data; // intentionally write garbage into the pointers, it's part of the test node->parent = (void *) 0xf00ba1; node->next = (void *) 0xf00ba2; node->prev = (void *) 0xf00ba3; node->children = (void *) 0xf00ba4; node->last_child = (void *) 0xf00ba5; return node; } } static int tree_node_file_search(void const *nptr, void const *data) { tree_node_file const *node = nptr; size_t len1 = strlen(node->path); size_t len2 = strlen(data); if (len1 <= len2) { if (memcmp(node->path, data, len1) == 0) { return (int) (len2 - len1); } else { return -1; } } else { return -1; } } #define tree_node_layout \ offsetof(tree_node, parent), offsetof(tree_node, children), -1, \ offsetof(tree_node, prev), offsetof(tree_node, next) #define tree_node_full_layout(structname) \ offsetof(structname, parent), offsetof(structname, children),\ offsetof(structname, last_child), \ offsetof(structname, prev), offsetof(structname, next) #define tree_node2_layout tree_node_full_layout(tree_node2) #define tree_node_file_layout tree_node_full_layout(tree_node_file) #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); } } CX_TEST(test_tree_add_one) { CxTestingAllocator talloc; cx_testing_allocator_init(&talloc); CxAllocator *alloc = &talloc.base; tree_node_file root = {0}; root.path = "/"; tree_node_file usr = {0}; usr.path = "/usr/"; cx_tree_link(&root, &usr, tree_node_file_layout); tree_node_file home = {0}; home.path = "/home/"; cx_tree_link(&root, &home, tree_node_file_layout); tree_node_file lib = {0}; lib.path = "/usr/lib/"; cx_tree_link(&usr, &lib, tree_node_file_layout); CX_TEST_DO { void *newroot = &root; tree_node_file *foo = cx_tree_add( "/home/foo/", tree_node_file_search, create_tree_node_file, alloc, &newroot, tree_node_file_layout ); CX_TEST_ASSERT(newroot == &root); tree_node_file *bar = cx_tree_add( "/home/foo/bar/", tree_node_file_search, create_tree_node_file, alloc, &newroot, tree_node_file_layout ); CX_TEST_ASSERT(newroot == &root); CX_TEST_ASSERT(bar->parent == foo); CX_TEST_ASSERT(foo->parent == &home); CX_TEST_ASSERT(talloc.alloc_total == 2); cxFree(&talloc.base, foo); cxFree(&talloc.base, bar); CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); } cx_testing_allocator_destroy(&talloc); } CX_TEST(test_tree_add_one_to_empty_tree) { tree_node_file *node = NULL; CX_TEST_DO { tree_node_file *root = NULL; char const *data = "/home/foo/bar/"; node = cx_tree_add( data, tree_node_file_search, create_tree_node_file, NULL, (void **) &root, tree_node_file_layout ); CX_TEST_ASSERT(root != NULL); CX_TEST_ASSERT(root->path == data); CX_TEST_ASSERT(root->next == NULL); CX_TEST_ASSERT(root->prev == NULL); CX_TEST_ASSERT(root->children == NULL); CX_TEST_ASSERT(root->last_child == NULL); CX_TEST_ASSERT(root->parent == NULL); } free(node); } CX_TEST(test_tree_add_one_existing) { CxTestingAllocator talloc; cx_testing_allocator_init(&talloc); CxAllocator *alloc = &talloc.base; tree_node_file root = {0}; root.path = "/"; tree_node_file usr = {0}; usr.path = "/usr/"; cx_tree_link(&root, &usr, tree_node_file_layout); tree_node_file home = {0}; home.path = "/home/"; cx_tree_link(&root, &home, tree_node_file_layout); tree_node_file lib = {0}; lib.path = "/usr/lib/"; cx_tree_link(&usr, &lib, tree_node_file_layout); CX_TEST_DO { void *newroot = &root; tree_node_file *node; node = cx_tree_add( "/usr/lib/", tree_node_file_search, create_tree_node_file, alloc, &newroot, tree_node_file_layout ); CX_TEST_ASSERT(newroot == &root); CX_TEST_ASSERT(node == &lib); node = cx_tree_add( "/home/", tree_node_file_search, create_tree_node_file, alloc, &newroot, tree_node_file_layout ); CX_TEST_ASSERT(newroot == &root); CX_TEST_ASSERT(node == &home); CX_TEST_ASSERT(talloc.alloc_total == 0); CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); } cx_testing_allocator_destroy(&talloc); } CX_TEST(test_tree_add_many) { // adds many elements to an existing tree CxTestingAllocator talloc; cx_testing_allocator_init(&talloc); CxAllocator *alloc = &talloc.base; tree_node_file root = {0}; root.path = "/"; tree_node_file usr = {0}; usr.path = "/usr/"; cx_tree_link(&root, &usr, tree_node_file_layout); tree_node_file home = {0}; home.path = "/home/"; cx_tree_link(&root, &home, tree_node_file_layout); tree_node_file lib = {0}; lib.path = "/usr/lib/"; cx_tree_link(&usr, &lib, tree_node_file_layout); CX_TEST_DO { void *newroot = &root; char const *paths[] = { "/home/foo/", "/home/foo/bar", "/usr/lib64/", "/usr/lib/foo.so" }; size_t processed = cx_tree_add_array( paths, 4, sizeof(char const *), tree_node_file_search, create_tree_node_file, alloc, &newroot, tree_node_file_layout ); CX_TEST_ASSERT(newroot == &root); CX_TEST_ASSERT(processed == 4); CX_TEST_ASSERT(talloc.alloc_total == 4); CX_TEST_ASSERT(home.children == home.last_child); tree_node_file *foo = home.children; CX_TEST_ASSERT(foo != NULL && foo->path == paths[0]); CX_TEST_ASSERT(foo->children == foo->last_child); tree_node_file *bar = foo->children; CX_TEST_ASSERT(bar != NULL && bar->path == paths[1]); CX_TEST_ASSERT(usr.children != usr.last_child); tree_node_file *lib64 = usr.last_child; CX_TEST_ASSERT(lib64 != NULL); CX_TEST_ASSERT(lib64->path == paths[2]); CX_TEST_ASSERT(lib64->prev == &lib); CX_TEST_ASSERT(lib64->parent == &usr); CX_TEST_ASSERT(lib.children != NULL); tree_node_file *libfoo = lib.children; CX_TEST_ASSERT(libfoo != NULL && libfoo->path == paths[3]); cxFree(&talloc.base, foo); cxFree(&talloc.base, bar); cxFree(&talloc.base, lib64); cxFree(&talloc.base, libfoo); CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); } cx_testing_allocator_destroy(&talloc); } CX_TEST(test_tree_add_many_skip_duplicates) { // adds many elements to an existing tree CxTestingAllocator talloc; cx_testing_allocator_init(&talloc); CxAllocator *alloc = &talloc.base; tree_node_file root = {0}; root.path = "/"; tree_node_file usr = {0}; usr.path = "/usr/"; cx_tree_link(&root, &usr, tree_node_file_layout); tree_node_file home = {0}; home.path = "/home/"; cx_tree_link(&root, &home, tree_node_file_layout); tree_node_file lib = {0}; lib.path = "/usr/lib/"; cx_tree_link(&usr, &lib, tree_node_file_layout); CX_TEST_DO { void *newroot = &root; char const *paths[] = { "/home/foo/", "/home/foo/bar", "/usr/lib/", "/usr/lib/foo.so" }; size_t processed = cx_tree_add_array( paths, 4, sizeof(char const *), tree_node_file_search, create_tree_node_file, alloc, &newroot, tree_node_file_layout ); CX_TEST_ASSERT(newroot == &root); CX_TEST_ASSERT(processed == 4); CX_TEST_ASSERT(talloc.alloc_total == 3); CX_TEST_ASSERT(home.children == home.last_child); tree_node_file *foo = home.children; CX_TEST_ASSERT(foo != NULL && foo->path == paths[0]); CX_TEST_ASSERT(foo->children == foo->last_child); tree_node_file *bar = foo->children; CX_TEST_ASSERT(bar != NULL && bar->path == paths[1]); CX_TEST_ASSERT(usr.children == usr.last_child); CX_TEST_ASSERT(usr.children == &lib); CX_TEST_ASSERT(lib.children != NULL); tree_node_file *libfoo = lib.children; CX_TEST_ASSERT(libfoo != NULL && libfoo->path == paths[3]); cxFree(&talloc.base, foo); cxFree(&talloc.base, bar); cxFree(&talloc.base, libfoo); CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); } cx_testing_allocator_destroy(&talloc); } CX_TEST(test_tree_add_create_from_array) { // creates an entirely new tree from an array CX_TEST_DO { } } 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); cx_test_register(suite, test_tree_add_one); cx_test_register(suite, test_tree_add_one_existing); cx_test_register(suite, test_tree_add_one_to_empty_tree); cx_test_register(suite, test_tree_add_many); cx_test_register(suite, test_tree_add_many_skip_duplicates); cx_test_register(suite, test_tree_add_create_from_array); return suite; }
