tests/test_tree.c@98af3fbc847f
tests/test_tree.c
Sun, 03 Nov 2024 16:08:15 +0100
- author
- Mike Becker <universe@uap-core.de>
- date
- Sun, 03 Nov 2024 16:08:15 +0100
- changeset 980
- 98af3fbc847f
- parent 931
- be71809e69d1
- permissions
- -rw-r--r--
remove obsolete reference to previously removed cxPropertiesInput()
/* * 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 { CX_TREE_NODE_BASE(struct tree_node2); 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; const char *path; } tree_node_file; static void *tree_node_file_create( const void *dptr, void *allocator) { if (allocator == NULL) allocator = cxDefaultAllocator; tree_node_file *node = cxMalloc(allocator, sizeof(tree_node_file)); node->path = dptr; // 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 void *tree_node_file_create_hl( const void *dptr, void *tree) { return tree_node_file_create(dptr, (void*)((CxTree*)tree)->allocator); } static int tree_node_file_search(const void *l, const void *r) { const tree_node_file *left = l; const tree_node_file *right = r; size_t len1 = strlen(left->path); size_t len2 = strlen(right->path); if (len1 <= len2) { if (memcmp(left->path, right->path, len1) == 0) { return (int) (len2 - len1); } else { return -1; } } else { return -1; } } static int tree_node_file_search_data(const void *l, const void *d) { tree_node_file r; r.path = d; return tree_node_file_search(l, &r); } #define tree_node_layout \ offsetof(tree_node, parent), offsetof(tree_node, children), -1, \ offsetof(tree_node, prev), offsetof(tree_node, next) #define tree_node_layout_no_prev \ offsetof(tree_node, parent), offsetof(tree_node, children), -1, -1, \ 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 cx_tree_node_base_layout #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}; tree_node child4 = {0}; cx_tree_link(&parent, &child1, tree_node_layout); cx_tree_link(&parent, &child3, tree_node_layout); cx_tree_link(&parent, &child4, 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 == &child4); CX_TEST_ASSERT(child4.parent == &parent); CX_TEST_ASSERT(child4.children == NULL); CX_TEST_ASSERT(child4.prev == &child1); CX_TEST_ASSERT(child4.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 first 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 == &child4); CX_TEST_ASSERT(child1.parent == NULL); CX_TEST_ASSERT(child4.parent == &parent); CX_TEST_ASSERT(child4.children == NULL); CX_TEST_ASSERT(child4.prev == NULL); CX_TEST_ASSERT(child4.next == NULL); } } CX_TEST(test_tree_unlink_no_prev) { tree_node parent = {0}; tree_node child1 = {0}; tree_node child2 = {0}; tree_node child3 = {0}; tree_node child4 = {0}; cx_tree_link(&parent, &child1, tree_node_layout_no_prev); cx_tree_link(&parent, &child3, tree_node_layout_no_prev); cx_tree_link(&parent, &child4, tree_node_layout_no_prev); cx_tree_link(&child3, &child2, tree_node_layout_no_prev); void * const marker = (void*) 0xc0ffee; child1.prev = child2.prev = child3.prev = child4.prev = marker; CX_TEST_DO { // in contrast to the other test we here remove child 4 instead of 3! cx_tree_unlink(&child4, tree_node_layout_no_prev); 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 == marker); CX_TEST_ASSERT(child1.next == &child3); // child 4 is unlinked CX_TEST_ASSERT(child4.parent == NULL); CX_TEST_ASSERT(child4.children == NULL); CX_TEST_ASSERT(child4.prev == marker); CX_TEST_ASSERT(child4.next == NULL); // unlink first child from parent cx_tree_unlink(&child1, tree_node_layout_no_prev); CX_TEST_ASSERT(parent.next == NULL); CX_TEST_ASSERT(parent.prev == NULL); CX_TEST_ASSERT(parent.parent == NULL); CX_TEST_ASSERT(parent.children == &child3); CX_TEST_ASSERT(child1.parent == NULL); CX_TEST_ASSERT(child3.parent == &parent); CX_TEST_ASSERT(child3.children == &child2); CX_TEST_ASSERT(child3.prev == marker); CX_TEST_ASSERT(child3.next == 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(const void *n, const void *d) { const tree_node *node = n; int data = *((const int *)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_data(&root, 0, &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_data(&root, 0, &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_data(&root, 0, &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_data(&root, 0, &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_data(&root, 0, &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_data(&root, 0, &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_search_with_max_depth) { 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 doe = {0}; doe.path = "/home/doe/"; cx_tree_link(&home, &doe, tree_node_file_layout); tree_node_file lib = {0}; lib.path = "/usr/lib/"; cx_tree_link(&usr, &lib, tree_node_file_layout); tree_node_file modules = {0}; modules.path = "/usr/lib/modules/"; cx_tree_link(&lib, &modules, tree_node_file_layout); CX_TEST_DO { int result; void *found; result = cx_tree_search_data( &root, 1, "/", tree_node_file_search_data, &found, tree_children(tree_node_file) ); CX_TEST_ASSERTM(result == 0, "root not found"); CX_TEST_ASSERT(found == &root); result = cx_tree_search_data( &root, 1, "/usr/", tree_node_file_search_data, &found, tree_children(tree_node_file) ); CX_TEST_ASSERT(result > 0); CX_TEST_ASSERT(found == &root); result = cx_tree_search_data( &root, 2, "/usr/", tree_node_file_search_data, &found, tree_children(tree_node_file) ); CX_TEST_ASSERT(result == 0); CX_TEST_ASSERT(found == &usr); result = cx_tree_search_data( &root, 2, "/usr/lib/", tree_node_file_search_data, &found, tree_children(tree_node_file) ); CX_TEST_ASSERT(result > 0); CX_TEST_ASSERT(found == &usr); result = cx_tree_search_data( &root, 3, "/usr/lib/", tree_node_file_search_data, &found, tree_children(tree_node_file) ); CX_TEST_ASSERTM(result == 0, "lib not found"); CX_TEST_ASSERT(found == &lib); result = cx_tree_search_data( &root, 1, "/home/", tree_node_file_search_data, &found, tree_children(tree_node_file) ); CX_TEST_ASSERT(result > 0); CX_TEST_ASSERT(found == &root); result = cx_tree_search_data( &root, 2, "/home/", tree_node_file_search_data, &found, tree_children(tree_node_file) ); CX_TEST_ASSERTM(result == 0, "home not found"); CX_TEST_ASSERT(found == &home); result = cx_tree_search_data( &root, 2, "/home/doe/", tree_node_file_search_data, &found, tree_children(tree_node_file) ); CX_TEST_ASSERT(result > 0); CX_TEST_ASSERT(found == &home); result = cx_tree_search_data( &root, 3, "/home/doe/", tree_node_file_search_data, &found, tree_children(tree_node_file) ); CX_TEST_ASSERTM(result == 0, "doe not found"); CX_TEST_ASSERT(found == &doe); result = cx_tree_search_data( &root, 3, "/usr/lib/modules/", tree_node_file_search_data, &found, tree_children(tree_node_file) ); CX_TEST_ASSERT(result > 0); CX_TEST_ASSERT(found == &lib); result = cx_tree_search_data( &root, 4, "/usr/lib/modules/", tree_node_file_search_data, &found, tree_children(tree_node_file) ); CX_TEST_ASSERTM(result == 0, "modules not found (start=root)"); CX_TEST_ASSERT(found == &modules); result = cx_tree_search_data( &usr, 3, "/usr/lib/modules/", tree_node_file_search_data, &found, tree_children(tree_node_file) ); CX_TEST_ASSERTM(result == 0, "modules not found (start=usr)"); CX_TEST_ASSERT(found == &modules); } } 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_create_for_empty_tree) { CX_TEST_DO { CxTreeIterator iter = cx_tree_iterator(NULL, false, tree_children(tree_node)); CX_TEST_ASSERT(!iter.visit_on_exit); CX_TEST_ASSERT(!iter.exiting); CX_TEST_ASSERT(iter.counter == 0); CX_TEST_ASSERT(iter.node == NULL); 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 == 0); CX_TEST_ASSERT(iter.depth == 0); CX_TEST_ASSERT(iter.loc_next == offsetof(tree_node, next)); CX_TEST_ASSERT(iter.loc_children == offsetof(tree_node, children)); CX_TEST_ASSERT(!cxIteratorValid(iter)); // disposing this iterator should also be harmless cxTreeIteratorDispose(&iter); } } 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; const char *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); const char *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 { tree_node_file *foo; int result; result = cx_tree_add( "/home/foo/", tree_node_file_search, tree_node_file_create, alloc, (void **) &foo, &root, tree_node_file_layout ); CX_TEST_ASSERT(result == 0); CX_TEST_ASSERT(foo != NULL); const char *bar_path = "/home/foo/bar/"; void *failed; size_t added = cx_tree_add_array( bar_path, 1, sizeof(const char *), tree_node_file_search, tree_node_file_create, alloc, &failed, &root, tree_node_file_layout ); CX_TEST_ASSERT(added == 1); CX_TEST_ASSERT(failed == NULL); tree_node_file *bar = foo->children; CX_TEST_ASSERT(bar != NULL); CX_TEST_ASSERT(bar->parent == foo); CX_TEST_ASSERT(bar->path == bar_path); CX_TEST_ASSERT(foo->parent == &home); tree_node_file *new_node; result = cx_tree_add( "newroot", tree_node_file_search, tree_node_file_create, alloc, (void **) &new_node, &root, tree_node_file_layout ); CX_TEST_ASSERT(0 != result); CX_TEST_ASSERT(NULL != new_node); CX_TEST_ASSERT(new_node->children == NULL); CX_TEST_ASSERT(new_node->parent == NULL); CX_TEST_ASSERT(talloc.alloc_total == 3); cxFree(alloc, foo); cxFree(alloc, bar); cxFree(alloc, new_node); CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); } cx_testing_allocator_destroy(&talloc); } 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 { tree_node_file *node; int result = cx_tree_add( "/usr/lib/", tree_node_file_search, tree_node_file_create, alloc, (void **) &node, &root, tree_node_file_layout ); CX_TEST_ASSERT(result == 0); CX_TEST_ASSERT(node != &lib); CX_TEST_ASSERT(node->prev == &lib); CX_TEST_ASSERT(lib.next == node); CX_TEST_ASSERT(node->parent == &usr); CX_TEST_ASSERT(talloc.alloc_total == 1); cxFree(alloc, node); CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); } cx_testing_allocator_destroy(&talloc); } CX_TEST(test_tree_add_one_no_match) { tree_node_file root = {0}; root.path = "/mnt/"; CX_TEST_DO { tree_node_file *node = NULL; int result = cx_tree_add( "/usr/lib/", tree_node_file_search, tree_node_file_create, NULL, (void **) &node, &root, tree_node_file_layout ); CX_TEST_ASSERT(result != 0); CX_TEST_ASSERT(node != NULL); CX_TEST_ASSERT(node->parent == NULL); CX_TEST_ASSERT(node->children == NULL); free(node); node = NULL; size_t added = cx_tree_add_array( "/", 1, sizeof(const char *), tree_node_file_search, tree_node_file_create, NULL, (void **) &node, &root, tree_node_file_layout ); CX_TEST_ASSERT(added == 0); CX_TEST_ASSERT(node != NULL); CX_TEST_ASSERT(node->parent == NULL); CX_TEST_ASSERT(node->children == NULL); free(node); } } CX_TEST(test_tree_add_duplicate_root) { tree_node_file root = {0}; root.path = "/"; CX_TEST_DO { tree_node_file *node; int result = cx_tree_add( "/", tree_node_file_search, tree_node_file_create, NULL, (void **) &node, &root, tree_node_file_layout ); CX_TEST_ASSERT(result == 0); CX_TEST_ASSERT(root.children == node); CX_TEST_ASSERT(node->parent == &root); free(node); } } CX_TEST(test_tree_add_zero) { CxTestingAllocator talloc; cx_testing_allocator_init(&talloc); CxAllocator *alloc = &talloc.base; tree_node_file root = {0}; root.path = "/"; CX_TEST_DO { void *failed; size_t processed = cx_tree_add_array( (void *) 0xc0ffee, 0, sizeof(void *), tree_node_file_search, tree_node_file_create, alloc, &failed, &root, tree_node_file_layout ); CX_TEST_ASSERT(failed == NULL); CX_TEST_ASSERT(processed == 0); CX_TEST_ASSERT(talloc.alloc_total == 0); CxIterator iter = cxIterator(NULL, sizeof(void *), 0); processed = cx_tree_add_iter( cxIteratorRef(iter), 10, // deliberately specify more than the iter has tree_node_file_search, tree_node_file_create, alloc, &failed, &root, tree_node_file_layout ); CX_TEST_ASSERT(processed == 0); CX_TEST_ASSERT(failed == NULL); 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 *failed; const char *paths[] = { "/home/foo/", "/home/foo/bar", "/usr/lib64/", "/usr/lib/foo.so" }; size_t processed = cx_tree_add_array( paths, 4, sizeof(const char *), tree_node_file_search, tree_node_file_create, alloc, &failed, &root, tree_node_file_layout ); CX_TEST_ASSERT(failed == NULL); 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(alloc, foo); cxFree(alloc, bar); cxFree(alloc, lib64); cxFree(alloc, libfoo); CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); } cx_testing_allocator_destroy(&talloc); } CX_TEST(test_tree_add_many_but_not_all) { 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 *failed; const char *paths[] = { "/home/foo/", "/home/foo/bar", "/usr/lib64/", "/usr/lib/foo.so" }; // create iterator for 4 elements, but choose to insert only 3 of them CxIterator iter = cxIterator(paths, sizeof(const char*), 4); size_t processed = cx_tree_add_iter( cxIteratorRef(iter), 3, tree_node_file_search, tree_node_file_create, alloc, &failed, &root, tree_node_file_layout ); CX_TEST_ASSERT(cxIteratorValid(iter)); CX_TEST_ASSERT(cxIteratorCurrent(iter) == &paths[3]); CX_TEST_ASSERT(failed == NULL); CX_TEST_ASSERT(processed == 3); 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); 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); cxFree(alloc, foo); cxFree(alloc, bar); cxFree(alloc, lib64); CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); } cx_testing_allocator_destroy(&talloc); } CX_TEST(test_tree_add_many_with_dupl_and_no_match) { CxTestingAllocator talloc; cx_testing_allocator_init(&talloc); CxAllocator *alloc = &talloc.base; tree_node_file root = {0}; root.path = "/mnt/"; CX_TEST_DO { tree_node_file *failed; const char *paths[] = { "/mnt/sdcard/", "/mnt/foo/", "/mnt/sdcard/", "/home/", "/usr/" }; size_t processed = cx_tree_add_array( paths, 5, sizeof(const char *), tree_node_file_search, tree_node_file_create, alloc, (void **) &failed, &root, tree_node_file_layout ); CX_TEST_ASSERT(processed == 3); CX_TEST_ASSERT(failed != NULL); CX_TEST_ASSERT(failed->parent == NULL); CX_TEST_ASSERT(failed->children == NULL); CX_TEST_ASSERT(strcmp(failed->path, "/home/") == 0); cxFree(alloc, failed); CX_TEST_ASSERT(root.children != root.last_child); CX_TEST_ASSERT(strcmp(root.children->path, "/mnt/sdcard/") == 0); CX_TEST_ASSERT(strcmp(root.last_child->path, "/mnt/sdcard/") == 0); CX_TEST_ASSERT(strcmp(root.children->next->path, "/mnt/foo/") == 0); CX_TEST_ASSERT(strcmp(root.last_child->prev->path, "/mnt/foo/") == 0); CxTreeIterator iter = cx_tree_iterator( &root, true, offsetof(tree_node_file, children), offsetof(tree_node_file, next) ); cx_foreach(tree_node_file *, node, iter) { if (iter.exiting) { if (node != &root) { cxFree(alloc, node); } } } CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); } cx_testing_allocator_destroy(&talloc); } static CX_TEST_SUBROUTINE(test_tree_add_create_from_array_impl, CxAllocator *alloc, const char **paths) { tree_node_file root = {0}; root.path = "/"; void *failed; size_t processed = cx_tree_add_array( paths, 10, sizeof(const char *), tree_node_file_search, tree_node_file_create, alloc, &failed, &root, tree_node_file_layout ); CX_TEST_ASSERT(failed == NULL); CX_TEST_ASSERT(processed == 10); const char *exp_order[] = { "/", "/usr/", "/usr/lib/", "/usr/lib/libbumm.so", "/home/", "/home/foo/", "/var/", "/var/www/", "/var/www/vhosts/", "/var/www/vhosts/live/", "/var/www/vhosts/live/htdocs/" }; unsigned exp_depth[] = { 1, 2, 3, 4, 2, 3, 2, 3, 4, 5, 6 }; CxTreeIterator iter = cx_tree_iterator( &root, true, offsetof(tree_node_file, children), offsetof(tree_node_file, next) ); cx_foreach(tree_node_file *, node, iter) { if (iter.exiting) { if (node != &root) { cxFree(alloc, node); } } else { CX_TEST_ASSERT(iter.counter <= 11); CX_TEST_ASSERT(iter.depth == exp_depth[iter.counter - 1]); CX_TEST_ASSERT(strcmp(node->path, exp_order[iter.counter - 1]) == 0); } } } CX_TEST(test_tree_add_create_from_array) { // creates an entirely new tree from an array CxTestingAllocator talloc; cx_testing_allocator_init(&talloc); CxAllocator *alloc = &talloc.base; CX_TEST_DO { const char *paths[] = { "/usr/", "/home/", "/usr/lib/", "/usr/lib/libbumm.so", "/var/", "/var/www/", "/var/www/vhosts/", "/var/www/vhosts/live/", "/var/www/vhosts/live/htdocs/", "/home/foo/" }; const char *scrambled_paths[] = { "/usr/", "/home/", "/var/www/vhosts/live/", "/usr/lib/", "/var/", "/var/www/", "/usr/lib/libbumm.so", "/var/www/vhosts/", "/var/www/vhosts/live/htdocs/", "/home/foo/" }; // no matter how the original array is sorted, // the resulting tree should be the same CX_TEST_CALL_SUBROUTINE(test_tree_add_create_from_array_impl, alloc, paths); CX_TEST_CALL_SUBROUTINE(test_tree_add_create_from_array_impl, alloc, scrambled_paths); CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); } cx_testing_allocator_destroy(&talloc); } CX_TEST(test_tree_high_create) { CxTestingAllocator talloc; cx_testing_allocator_init(&talloc); CX_TEST_DO { CxTree *tree = cxTreeCreate( &talloc.base, tree_node_file_create_hl, tree_node_file_search, tree_node_file_search_data, tree_node_file_layout ); CX_TEST_ASSERT(tree->cl != NULL); CX_TEST_ASSERT(tree->allocator == &talloc.base); CX_TEST_ASSERT(tree->node_create == tree_node_file_create_hl); CX_TEST_ASSERT(tree->search == tree_node_file_search); CX_TEST_ASSERT(tree->search_data == tree_node_file_search_data); CX_TEST_ASSERT(tree->size == 0); CX_TEST_ASSERT(tree->simple_destructor == NULL); CX_TEST_ASSERT(tree->advanced_destructor == (cx_destructor_func2) cxFree); CX_TEST_ASSERT(tree->destructor_data == &talloc.base); CX_TEST_ASSERT(tree->root == NULL); CX_TEST_ASSERT(tree->loc_parent == offsetof(tree_node_file, parent)); CX_TEST_ASSERT(tree->loc_children == offsetof(tree_node_file, children)); CX_TEST_ASSERT(tree->loc_last_child == offsetof(tree_node_file, last_child)); CX_TEST_ASSERT(tree->loc_prev == offsetof(tree_node_file, prev)); CX_TEST_ASSERT(tree->loc_next == offsetof(tree_node_file, next)); CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc)); CX_TEST_ASSERT(talloc.alloc_total == 1); cxTreeDestroy(tree); CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); } cx_testing_allocator_destroy(&talloc); } CX_TEST(test_tree_high_create_simple) { CX_TEST_DO { CxTree *tree = cxTreeCreateSimple( cxDefaultAllocator, tree_node_file_create_hl, tree_node_file_search, tree_node_file_search_data ); CX_TEST_ASSERT(tree->cl != NULL); CX_TEST_ASSERT(tree->allocator == cxDefaultAllocator); CX_TEST_ASSERT(tree->node_create == tree_node_file_create_hl); CX_TEST_ASSERT(tree->search == tree_node_file_search); CX_TEST_ASSERT(tree->search_data == tree_node_file_search_data); CX_TEST_ASSERT(tree->size == 0); CX_TEST_ASSERT(tree->simple_destructor == NULL); CX_TEST_ASSERT(tree->advanced_destructor == (cx_destructor_func2) cxFree); CX_TEST_ASSERT(tree->destructor_data == cxDefaultAllocator); CX_TEST_ASSERT(tree->root == NULL); CX_TEST_ASSERT(tree->loc_parent == offsetof(struct cx_tree_node_base_s, parent)); CX_TEST_ASSERT(tree->loc_children == offsetof(struct cx_tree_node_base_s, children)); CX_TEST_ASSERT(tree->loc_last_child == offsetof(struct cx_tree_node_base_s, last_child)); CX_TEST_ASSERT(tree->loc_prev == offsetof(struct cx_tree_node_base_s, prev)); CX_TEST_ASSERT(tree->loc_next == offsetof(struct cx_tree_node_base_s, next)); cxTreeDestroy(tree); } } CX_TEST(test_tree_high_create_wrapped) { tree_node root = {0}, child1 = {0}, child2 = {0}, child3 = {0}; cx_tree_link(&root, &child1, tree_node_layout); cx_tree_link(&root, &child2, tree_node_layout); cx_tree_link(&child1, &child3, tree_node_layout); CX_TEST_DO { CxTree *tree = cxTreeCreateWrapped(cxDefaultAllocator, &root, tree_node_layout); CX_TEST_ASSERT(tree->cl != NULL); CX_TEST_ASSERT(tree->allocator == cxDefaultAllocator); CX_TEST_ASSERT(tree->node_create == NULL); CX_TEST_ASSERT(tree->search == NULL); CX_TEST_ASSERT(tree->search_data == NULL); CX_TEST_ASSERT(tree->root == &root); CX_TEST_ASSERT(tree->size == 4); CX_TEST_ASSERT(tree->simple_destructor == NULL); CX_TEST_ASSERT(tree->advanced_destructor == NULL); CX_TEST_ASSERT(tree->destructor_data == NULL); CX_TEST_ASSERT(tree->loc_parent == offsetof(tree_node, parent)); CX_TEST_ASSERT(tree->loc_children == offsetof(tree_node, children)); CX_TEST_ASSERT(tree->loc_last_child == -1); CX_TEST_ASSERT(tree->loc_prev == offsetof(tree_node, prev)); CX_TEST_ASSERT(tree->loc_next == offsetof(tree_node, next)); cxTreeDestroy(tree); } } CX_TEST(test_tree_high_tree_depth) { tree_node root = {0}, child1 = {0}, child2 = {0}, child3 = {0}; cx_tree_link(&root, &child1, tree_node_layout); cx_tree_link(&root, &child2, tree_node_layout); cx_tree_link(&child1, &child3, tree_node_layout); CxTree *tree = cxTreeCreateWrapped(cxDefaultAllocator, &root, tree_node_layout); CX_TEST_DO { CX_TEST_ASSERT(cxTreeDepth(tree) == 3); CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &root) == 3); CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child1) == 2); CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child2) == 1); CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child3) == 1); CxTree *empty = cxTreeCreate( cxDefaultAllocator, tree_node_file_create_hl, tree_node_file_search, tree_node_file_search_data, tree_node_file_layout ); CX_TEST_ASSERT(cxTreeDepth(empty) == 0); cxTreeDestroy(empty); } cxTreeDestroy(tree); } CX_TEST(test_tree_high_set_parent) { tree_node root = {0}, child1 = {0}, child2 = {0}, child3 = {0}; CxTree *tree = cxTreeCreateWrapped(cxDefaultAllocator, &root, tree_node_layout); CX_TEST_DO { cxTreeSetParent(tree, &root, &child1); cxTreeSetParent(tree, &root, &child2); cxTreeSetParent(tree, &child1, &child3); CX_TEST_ASSERT(cxTreeDepth(tree) == 3); CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &root) == 3); CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child1) == 2); CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child2) == 1); CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child3) == 1); cxTreeSetParent(tree, &child2, &child3); CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &root) == 3); CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child1) == 1); CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child2) == 2); CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child3) == 1); CxTree *empty = cxTreeCreate( cxDefaultAllocator, tree_node_file_create_hl, tree_node_file_search, tree_node_file_search_data, tree_node_file_layout ); CX_TEST_ASSERT(cxTreeDepth(empty) == 0); cxTreeDestroy(empty); } cxTreeDestroy(tree); } CX_TEST(test_tree_high_insert_one) { CxTestingAllocator talloc; cx_testing_allocator_init(&talloc); CxAllocator *alloc = &talloc.base; CX_TEST_DO { CxTree *tree = cxTreeCreate( alloc, tree_node_file_create_hl, tree_node_file_search, tree_node_file_search_data, tree_node_file_layout ); int result = 0; result |= cxTreeInsert(tree, "/"); result |= cxTreeInsert(tree, "/usr/"); result |= cxTreeInsert(tree, "/home/"); result |= cxTreeInsert(tree, "/usr/lib/"); result |= cxTreeInsert(tree, "/home/foo/"); CX_TEST_ASSERT(result == 0); CX_TEST_ASSERT(1 == cxTreeInsertArray(tree, "/home/foo/bar/", sizeof(const char*), 1)); CX_TEST_ASSERT(tree->size == 6); CX_TEST_ASSERT(0 != cxTreeInsert(tree, "newroot")); CX_TEST_ASSERT(tree->size == 6); CX_TEST_ASSERT(talloc.alloc_total == 8); CX_TEST_ASSERT(talloc.free_total == 1); // the one that could not be added cxTreeDestroy(tree); CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); } cx_testing_allocator_destroy(&talloc); } CX_TEST(test_tree_high_insert_many) { CxTestingAllocator talloc; cx_testing_allocator_init(&talloc); CxAllocator *alloc = &talloc.base; CX_TEST_DO { CxTree *tree = cxTreeCreate( alloc, tree_node_file_create_hl, tree_node_file_search, tree_node_file_search_data, tree_node_file_layout ); const char *paths[] = { "/", "/usr/", "/home/", "/usr/lib/", "/home/foo/", "/home/foo/bar/", "newroot" }; CX_TEST_ASSERT(6 == cxTreeInsertArray(tree, paths, sizeof(const char*), 7)); CX_TEST_ASSERT(tree->size == 6); CX_TEST_ASSERT(talloc.alloc_total == 8); CX_TEST_ASSERT(talloc.free_total == 1); // the one that could not be added cxTreeDestroy(tree); CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); } cx_testing_allocator_destroy(&talloc); } static void test_tree_remove_node_relink_mock( void *node, __attribute__((__unused__)) const void *oldp, __attribute__((__unused__)) const void *newp ) { tree_node_file * n = node; // this function fakes the relink logic in below test if (strcmp(n->path, "/usr/share/") == 0) { n->path = "/share/"; } else if (strcmp(n->path, "/usr/lib/") == 0) { n->path = "/lib/"; } } CX_TEST(test_tree_high_add_find_remove_nodes) { CxTestingAllocator talloc; cx_testing_allocator_init(&talloc); CxAllocator *alloc = &talloc.base; CX_TEST_DO { CxTree *tree = cxTreeCreate( alloc, tree_node_file_create_hl, tree_node_file_search, tree_node_file_search_data, tree_node_file_layout ); const char *paths[] = { "/", "/usr/", "/home/", "/usr/lib/", "/home/foo/", "/home/foo/bar/" }; cxTreeInsertArray(tree, paths, sizeof(const char*), 6); tree_node_file *foo = cxTreeFind(tree, "/home/foo/"); CX_TEST_ASSERT(NULL != foo); CX_TEST_ASSERT(0 == strcmp("/home/foo/", foo->path)); CX_TEST_ASSERT(NULL != foo->parent); CX_TEST_ASSERT(0 == strcmp("/home/", foo->parent->path)); CX_TEST_ASSERT(tree->size == 6); CX_TEST_ASSERT(0 == cxTreeAddChild(tree, foo->parent, "/home/baz/")); tree_node_file *baz = cxTreeFind(tree, "/home/baz/"); CX_TEST_ASSERT(NULL != baz); CX_TEST_ASSERT(0 == strcmp("/home/baz/", baz->path)); CX_TEST_ASSERT(NULL != baz->parent); CX_TEST_ASSERT(0 == strcmp("/home/", baz->parent->path)); CX_TEST_ASSERT(tree->size == 7); tree_node_file *home = cxTreeFind(tree, "/home/"); CX_TEST_ASSERT(NULL == cxTreeFindInSubtree(tree, "/usr/", foo, 0)); tree_node_file *bar = cxTreeFindInSubtree(tree, "/home/foo/bar/", home, 0); CX_TEST_ASSERT(NULL != bar); CX_TEST_ASSERT(0 == strcmp("/home/foo/bar/", bar->path)); CX_TEST_ASSERT(bar->parent == foo); tree_node_file *share = cxCalloc(alloc, 1, sizeof(tree_node_file)); share->path = "/usr/share/"; tree_node_file *usr = cxTreeFind(tree, "/usr/"); cxTreeAddChildNode(tree, usr, share); CX_TEST_ASSERT(tree->size == 8); cxTreeRemoveSubtree(tree, foo); CX_TEST_ASSERT(tree->size == 6); CX_TEST_ASSERT(foo->children == bar); CX_TEST_ASSERT(foo->last_child == bar); CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/foo/")); CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/foo/bar/")); CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/bar/")); CX_TEST_ASSERT(0 == cxTreeRemoveNode(tree, usr, test_tree_remove_node_relink_mock)); CX_TEST_ASSERT(tree->size == 5); CX_TEST_ASSERT(usr->parent == NULL); CX_TEST_ASSERT(usr->children == NULL); CX_TEST_ASSERT(usr->last_child == NULL); CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/")); CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/lib/")); CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/share/")); tree_node_file *relinked_share = cxTreeFind(tree, "/share/"); tree_node_file *relinked_lib = cxTreeFind(tree, "/lib/"); CX_TEST_ASSERT(relinked_share != NULL); CX_TEST_ASSERT(relinked_share->parent == tree->root); CX_TEST_ASSERT(relinked_lib != NULL); CX_TEST_ASSERT(relinked_lib->parent == tree->root); CX_TEST_ASSERT(NULL != cxTreeFind(tree, "/home/")); cxTreeDestroy(tree); // we are not done yet, because we need to free the removed stuff CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc)); cxFree(alloc, usr); // for the subtree, we use a little trick and wrap it in a new tree CxTree *foo_tree = cxTreeCreateWrapped(alloc, foo, tree_node_file_layout); foo_tree->allocator = alloc; foo_tree->advanced_destructor = (cx_destructor_func2 ) cxFree; foo_tree->destructor_data = alloc; cxTreeDestroy(foo_tree); CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); } cx_testing_allocator_destroy(&talloc); } CX_TEST(test_tree_high_add_find_destroy_nodes) { CxTestingAllocator talloc; cx_testing_allocator_init(&talloc); CxAllocator *alloc = &talloc.base; CX_TEST_DO { CxTree *tree = cxTreeCreate( alloc, tree_node_file_create_hl, tree_node_file_search, tree_node_file_search_data, tree_node_file_layout ); const char *paths[] = { "/", "/usr/", "/home/", "/usr/lib/", "/home/foo/", "/home/foo/bar/" }; cxTreeInsertArray(tree, paths, sizeof(const char*), 6); tree_node_file *foo = cxTreeFind(tree, "/home/foo/"); CX_TEST_ASSERT(NULL != foo); CX_TEST_ASSERT(0 == strcmp("/home/foo/", foo->path)); CX_TEST_ASSERT(NULL != foo->parent); CX_TEST_ASSERT(0 == strcmp("/home/", foo->parent->path)); CX_TEST_ASSERT(tree->size == 6); CX_TEST_ASSERT(0 == cxTreeAddChild(tree, foo->parent, "/home/baz/")); tree_node_file *baz = cxTreeFind(tree, "/home/baz/"); CX_TEST_ASSERT(NULL != baz); CX_TEST_ASSERT(0 == strcmp("/home/baz/", baz->path)); CX_TEST_ASSERT(NULL != baz->parent); CX_TEST_ASSERT(0 == strcmp("/home/", baz->parent->path)); CX_TEST_ASSERT(tree->size == 7); tree_node_file *home = cxTreeFind(tree, "/home/"); CX_TEST_ASSERT(NULL == cxTreeFindInSubtree(tree, "/usr/", foo, 0)); tree_node_file *bar = cxTreeFindInSubtree(tree, "/home/foo/bar/", home, 0); CX_TEST_ASSERT(NULL != bar); CX_TEST_ASSERT(0 == strcmp("/home/foo/bar/", bar->path)); CX_TEST_ASSERT(bar->parent == foo); tree_node_file *share = cxCalloc(alloc, 1, sizeof(tree_node_file)); share->path = "/usr/share/"; tree_node_file *usr = cxTreeFind(tree, "/usr/"); cxTreeAddChildNode(tree, usr, share); CX_TEST_ASSERT(tree->size == 8); cxTreeDestroySubtree(tree, foo); CX_TEST_ASSERT(tree->size == 6); CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/foo/")); CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/foo/bar/")); CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/bar/")); CX_TEST_ASSERT(0 == cxTreeDestroyNode(tree, usr, test_tree_remove_node_relink_mock)); CX_TEST_ASSERT(tree->size == 5); CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/")); CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/lib/")); CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/share/")); tree_node_file *relinked_share = cxTreeFind(tree, "/share/"); tree_node_file *relinked_lib = cxTreeFind(tree, "/lib/"); CX_TEST_ASSERT(relinked_share != NULL); CX_TEST_ASSERT(relinked_share->parent == tree->root); CX_TEST_ASSERT(relinked_lib != NULL); CX_TEST_ASSERT(relinked_lib->parent == tree->root); CX_TEST_ASSERT(NULL != cxTreeFind(tree, "/home/")); cxTreeDestroy(tree); // all memory should be free when using destroy instead of remove CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); } cx_testing_allocator_destroy(&talloc); } CX_TEST(test_tree_high_remove_or_destroy_root) { CxTestingAllocator talloc; cx_testing_allocator_init(&talloc); CxAllocator *alloc = &talloc.base; CX_TEST_DO { CxTree *tree = cxTreeCreate( alloc, tree_node_file_create_hl, tree_node_file_search, tree_node_file_search_data, tree_node_file_layout ); const char *paths[] = { "/", "/usr/", "/home/", "/usr/lib/", "/home/foo/", "/home/foo/bar/" }; cxTreeInsertArray(tree, paths, sizeof(const char*), 6); void *root = tree->root; CX_TEST_ASSERT(0 != cxTreeRemoveNode(tree, root, NULL)); CX_TEST_ASSERT(tree->root == root); CX_TEST_ASSERT(tree->size == 6); CX_TEST_ASSERT(0 != cxTreeDestroyNode(tree, root, NULL)); CX_TEST_ASSERT(tree->root == root); CX_TEST_ASSERT(tree->size == 6); cxTreeRemoveSubtree(tree, root); CX_TEST_ASSERT(tree->size == 0); CX_TEST_ASSERT(tree->root == NULL); CX_TEST_ASSERT(cxTreeDepth(tree) == 0); cxTreeDestroy(tree); CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc)); CxTree *w = cxTreeCreateWrapped(alloc, root, tree_node_file_layout); w->advanced_destructor = (cx_destructor_func2) cxFree; w->destructor_data = alloc; cxTreeDestroySubtree(w, w->root); CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc)); cxFree(alloc, w); CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); } cx_testing_allocator_destroy(&talloc); } static void test_tree_high_simple_destructor_func(void *node) { ((tree_node *)node)->data++; } CX_TEST(test_tree_high_simple_destructor) { tree_node root = {0}, child1 = {0}, child2 = {0}, child3 = {0}; cx_tree_link(&root, &child1, tree_node_layout); cx_tree_link(&root, &child2, tree_node_layout); cx_tree_link(&child1, &child3, tree_node_layout); CX_TEST_DO { CxTree *tree = cxTreeCreateWrapped(cxDefaultAllocator, &root, tree_node_layout); tree->simple_destructor = test_tree_high_simple_destructor_func; cxTreeDestroyNode(tree, &child1, NULL); cxTreeDestroy(tree); CX_TEST_ASSERT(root.data == 1); CX_TEST_ASSERT(child1.data == 1); CX_TEST_ASSERT(child2.data == 1); CX_TEST_ASSERT(child3.data == 1); } } 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_tree_unlink_no_prev); 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_search_with_max_depth); cx_test_register(suite, test_tree_iterator_create_and_dispose); cx_test_register(suite, test_tree_iterator_create_for_empty_tree); 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_no_match); cx_test_register(suite, test_tree_add_duplicate_root); cx_test_register(suite, test_tree_add_zero); cx_test_register(suite, test_tree_add_many); cx_test_register(suite, test_tree_add_many_but_not_all); cx_test_register(suite, test_tree_add_many_with_dupl_and_no_match); cx_test_register(suite, test_tree_add_create_from_array); return suite; } CxTestSuite *cx_test_suite_tree_high_level(void) { CxTestSuite *suite = cx_test_suite_new("tree (high level)"); cx_test_register(suite, test_tree_high_create); cx_test_register(suite, test_tree_high_create_simple); cx_test_register(suite, test_tree_high_create_wrapped); cx_test_register(suite, test_tree_high_tree_depth); cx_test_register(suite, test_tree_high_set_parent); cx_test_register(suite, test_tree_high_insert_one); cx_test_register(suite, test_tree_high_insert_many); cx_test_register(suite, test_tree_high_add_find_remove_nodes); cx_test_register(suite, test_tree_high_add_find_destroy_nodes); cx_test_register(suite, test_tree_high_remove_or_destroy_root); cx_test_register(suite, test_tree_high_simple_destructor); return suite; }
