--- a/tests/test_tree.c Wed Dec 31 13:39:55 2025 +0100
+++ b/tests/test_tree.c Wed Dec 31 14:58:40 2025 +0100
@@ -443,6 +443,14 @@
int r;
tree_node *n;
CX_TEST_DO {
+ // special case: search an empty tree
+ n = (void*)0x1337;
+ r = cx_tree_search(NULL, 0, &s, test_tree_search_function,
+ (void **) &n, tree_children(tree_node));
+ CX_TEST_ASSERT(r < 0);
+ CX_TEST_ASSERT(n == NULL);
+
+ // search for the test data (exact matches)
for (unsigned i = 0 ; i <= 10 ; i++) {
s = testdata[i];
r = cx_tree_search(&root, 0, &s, test_tree_search_function,
@@ -1049,6 +1057,26 @@
}
}
+CX_TEST(test_tree_visitor_create_for_empty_tree) {
+ CX_TEST_DO {
+ CxTreeIterator iter = cx_tree_visitor(NULL, 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.allow_remove);
+ CX_TEST_ASSERT(!iter.base.remove);
+ CX_TEST_ASSERT(iter.queue_next == NULL);
+ CX_TEST_ASSERT(iter.queue_last == 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_visitor_no_children) {
tree_node root = {0};
@@ -1373,6 +1401,80 @@
cx_testing_allocator_destroy(&talloc);
}
+CX_TEST(test_tree_high_create_root) {
+ CxTestingAllocator talloc;
+ cx_testing_allocator_init(&talloc);
+ CX_TEST_DO {
+ CxTree *tree = cxTreeCreate(
+ &talloc.base,
+ sizeof(tree_node_file),
+ CX_STORE_POINTERS,
+ NULL, -1,
+ cx_tree_node_layout(tree_node_file)
+ );
+
+ CX_TEST_ASSERT(tree->root == NULL);
+ // create root without data
+ tree_node_file *root = cxTreeCreateRoot(tree);
+ CX_TEST_ASSERT(root != NULL);
+ CX_TEST_ASSERT(root == tree->root);
+ // re-create same root (does nothing)
+ tree_node_file *root2 = cxTreeCreateRoot(tree);
+ CX_TEST_ASSERT(root2 == root);
+
+ // next test
+ cxTreeClear(tree);
+
+ // try to create with data, but loc_data is not known
+ root = cxTreeCreateRootData(tree, "/");
+ CX_TEST_ASSERT(root == NULL);
+
+ // set the loc_data
+ tree->loc_data = offsetof(tree_node_file, path);
+ root = cxTreeCreateRootData(tree, "/");
+ CX_TEST_ASSERT(root != NULL);
+ CX_TEST_ASSERT(strcmp(root->path, "/") == 0);
+
+ cxTreeFree(tree);
+ CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
+ }
+}
+
+CX_TEST(test_tree_high_set_root) {
+ CxTestingAllocator talloc;
+ cx_testing_allocator_init(&talloc);
+ CX_TEST_DO {
+ CxTree *tree = cxTreeCreate(
+ &talloc.base,
+ sizeof(tree_node_file),
+ CX_STORE_POINTERS,
+ NULL, -1,
+ cx_tree_node_layout(tree_node_file)
+ );
+
+ CX_TEST_ASSERT(tree->root == NULL);
+
+ tree_node_file *root = cxTreeCreateRoot(tree);
+ CX_TEST_ASSERT(root != NULL);
+ CX_TEST_ASSERT(root == tree->root);
+
+ // create a different root externally
+ tree_node_file *root2 = cxZalloc(&talloc.base, sizeof(tree_node_file));
+
+ // replace the root
+ tree_node_file *old = cxTreeSetRoot(tree, root2);
+ CX_TEST_ASSERT(old == root);
+
+ // free the tree, check that there is memory leaking
+ cxTreeFree(tree);
+ CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc));
+
+ // free the old root, check that memory is fine
+ cxFree(&talloc.base, old);
+ CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
+ }
+}
+
CX_TEST(test_tree_high_tree_depth) {
tree_node root = {0}, child1 = {0}, child2 = {0}, child3 = {0};
cx_tree_add(&root, &child1, tree_node_layout);
@@ -1618,6 +1720,123 @@
cx_testing_allocator_destroy(&talloc);
}
+CX_TEST(test_tree_high_add_find_without_loc_data) {
+ CxTestingAllocator talloc;
+ cx_testing_allocator_init(&talloc);
+ CxAllocator *alloc = &talloc.base;
+ CX_TEST_DO {
+ CxTree *tree = cxTreeCreate(alloc,
+ sizeof(tree_node_file),
+ CX_STORE_POINTERS,
+ NULL, offsetof(tree_node_file, path),
+ cx_tree_node_layout(tree_node_file)
+ );
+ cxSetCompareFunc(tree, strcmp);
+ tree_node_file *root = cxTreeCreateRootData(tree, "/");
+ tree_node_file *home = cxTreeAddData(tree, root, "/home/");
+ tree_node_file *foo = cxTreeAddData(tree, home, "/home/foo/");
+ cxTreeAddData(tree, foo, "/home/foo/bar/");
+ tree_node_file *usr = cxTreeAddData(tree, root, "/usr/");
+ cxTreeAddData(tree, usr, "/usr/lib/");
+
+ void *found = cxTreeFind(tree, "/home/foo/", true);
+ CX_TEST_ASSERT(found == foo);
+
+ // now remove the loc_data
+ tree->loc_data = -1;
+ found = cxTreeFind(tree, "/home/foo/", true);
+ CX_TEST_ASSERT(found == NULL);
+
+ CX_TEST_ASSERT(NULL == cxTreeAddData(tree, root, "/usr/local/"));
+
+ cxTreeFree(tree);
+ CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
+ }
+ cx_testing_allocator_destroy(&talloc);
+}
+
+CX_TEST(test_tree_high_find_max_depth) {
+ CxTree *tree = cxTreeCreate(NULL,
+ sizeof(tree_node_file),
+ CX_STORE_POINTERS,
+ NULL, offsetof(tree_node_file, path),
+ cx_tree_node_layout(tree_node_file)
+ );
+ cxSetCompareFunc(tree, strcmp);
+ tree_node_file *root = cxTreeCreateRootData(tree, "/");
+ tree_node_file *home = cxTreeAddData(tree, root, "/home/");
+ tree_node_file *foo = cxTreeAddData(tree, home, "/home/foo/");
+ tree_node_file *bar = cxTreeAddData(tree, foo, "/home/foo/bar/");
+ tree_node_file *usr = cxTreeAddData(tree, root, "/usr/");
+ cxTreeAddData(tree, usr, "/usr/lib/");
+ CX_TEST_DO {
+ CX_TEST_ASSERT(bar == cxTreeFindInSubtree(tree, "/home/foo/bar/", tree->root, 4, true));
+ CX_TEST_ASSERT(NULL == cxTreeFindInSubtree(tree, "/home/foo/bar/", tree->root, 3, true));
+ CX_TEST_ASSERT(bar == cxTreeFindInSubtree(tree, "/home/foo/bar/", home, 3, true));
+ CX_TEST_ASSERT(NULL == cxTreeFindInSubtree(tree, "/home/foo/bar/", home, 2, true));
+ }
+ cxTreeFree(tree);
+}
+
+CX_TEST(test_tree_high_find_fast) {
+ CxTree *tree = cxTreeCreate(NULL,
+ sizeof(tree_node_file),
+ CX_STORE_POINTERS,
+ NULL, offsetof(tree_node_file, path),
+ cx_tree_node_layout(tree_node_file)
+ );
+ cxSetCompareFunc(tree, strcmp);
+ tree_node_file *root = cxTreeCreateRootData(tree, "/");
+ tree_node_file *home = cxTreeAddData(tree, root, "/home/");
+ tree_node_file *foo = cxTreeAddData(tree, home, "/home/foo/");
+ tree_node_file *bar = cxTreeAddData(tree, foo, "/home/foo/bar/");
+ tree_node_file *baz = cxTreeAddData(tree, home, "/home/baz/");
+ tree_node_file *usr = cxTreeAddData(tree, root, "/usr/");
+ tree_node_file *lib = cxTreeAddData(tree, usr, "/usr/lib/");
+ CX_TEST_DO {
+ // test that loc_data not needed for FindFast!
+ tree->loc_data = -1;
+
+ // find from root
+ CX_TEST_ASSERT(root == cxTreeFindFast(tree, "/",
+ tree_node_file_search_func));
+ CX_TEST_ASSERT(home == cxTreeFindFast(tree, "/home/",
+ tree_node_file_search_func));
+ CX_TEST_ASSERT(foo == cxTreeFindFast(tree, "/home/foo/",
+ tree_node_file_search_func));
+ CX_TEST_ASSERT(bar == cxTreeFindFast(tree, "/home/foo/bar/",
+ tree_node_file_search_func));
+ CX_TEST_ASSERT(usr == cxTreeFindFast(tree, "/usr/",
+ tree_node_file_search_func));
+ CX_TEST_ASSERT(lib == cxTreeFindFast(tree, "/usr/lib/",
+ tree_node_file_search_func));
+
+ // find from correct subtree
+ CX_TEST_ASSERT(foo == cxTreeFindFastInSubtree(tree, "/home/foo/",
+ tree_node_file_search_func, home, 0));
+ CX_TEST_ASSERT(bar == cxTreeFindFastInSubtree(tree, "/home/foo/bar/",
+ tree_node_file_search_func, home, 0));
+ CX_TEST_ASSERT(lib == cxTreeFindFastInSubtree(tree, "/usr/lib/",
+ tree_node_file_search_func, usr, 0));
+
+ // find in wrong subtree
+ CX_TEST_ASSERT(NULL == cxTreeFindFastInSubtree(tree, "/home/foo/",
+ tree_node_file_search_func, usr, 0));
+ CX_TEST_ASSERT(NULL == cxTreeFindFastInSubtree(tree, "/home/foo/bar/",
+ tree_node_file_search_func, baz, 0));
+ CX_TEST_ASSERT(NULL == cxTreeFindFastInSubtree(tree, "/usr/lib/",
+ tree_node_file_search_func, home, 0));
+
+ // some tests with max depth
+ // -------------------------
+ CX_TEST_ASSERT(bar == cxTreeFindFastInSubtree(tree, "/home/foo/bar/", tree_node_file_search_func, tree->root, 4));
+ CX_TEST_ASSERT(NULL == cxTreeFindFastInSubtree(tree, "/home/foo/bar/", tree_node_file_search_func, tree->root, 3));
+ CX_TEST_ASSERT(bar == cxTreeFindFastInSubtree(tree, "/home/foo/bar/", tree_node_file_search_func, home, 3));
+ CX_TEST_ASSERT(NULL == cxTreeFindFastInSubtree(tree, "/home/foo/bar/", tree_node_file_search_func, home, 2));
+ }
+ cxTreeFree(tree);
+}
+
CX_TEST(test_tree_high_remove_or_destroy_root) {
CxTestingAllocator talloc;
cx_testing_allocator_init(&talloc);
@@ -1733,6 +1952,44 @@
cxTreeFree(tree);
}
+CX_TEST(test_tree_high_iterator_large_depth) {
+ CxTree *tree = cxTreeCreate(NULL,
+ sizeof(tree_node),
+ sizeof(int),
+ NULL, offsetof(tree_node, data),
+ tree_node_layout
+ );
+ int c = 0;
+ tree_node *root = cxTreeCreateRootData(tree, &c);
+ unsigned depths[6] = {10, 20, 15, 30, 25, 5};
+ for (unsigned b = 0 ; b < 3 ; b++) {
+ c++;
+ tree_node *branch = cxTreeAddData(tree, root, &c);
+ tree_node *p = branch;
+ for (unsigned d = 0; d < depths[b*2+0] ; d++) {
+ c++;
+ p = cxTreeAddData(tree, p, &c);
+ }
+ p = branch;
+ for (unsigned d = 0; d < depths[b*2+1] ; d++) {
+ c++;
+ p = cxTreeAddData(tree, p, &c);
+ }
+ }
+ CX_TEST_DO {
+ CX_TEST_ASSERT(cxTreeSize(tree) == 109);
+ CX_TEST_ASSERT(cxTreeSubtreeSize(tree, root) == 109);
+ CX_TEST_ASSERT(cxTreeSubtreeSize(tree, root->children) == 1+depths[0]+depths[1]);
+ CX_TEST_ASSERT(cxTreeSubtreeSize(tree, root->children->next) == 1+depths[2]+depths[3]);
+ CX_TEST_ASSERT(cxTreeSubtreeSize(tree, root->children->next->next) == 1+depths[4]+depths[5]);
+ CxTreeIterator iter = cxTreeIterate(tree, false);
+ cx_foreach(tree_node*, n, iter) {
+ CX_TEST_ASSERT((size_t)n->data == iter.counter - 1);
+ }
+ }
+ cxTreeFree(tree);
+}
+
CX_TEST(test_tree_high_visitor) {
CxTree *tree = cxTreeCreate(NULL,
sizeof(tree_node_file),
@@ -1798,6 +2055,7 @@
cx_test_register(suite, test_tree_iterator_free_nodes);
cx_test_register(suite, test_tree_visitor_create_and_dispose);
cx_test_register(suite, test_tree_visitor);
+ cx_test_register(suite, test_tree_visitor_create_for_empty_tree);
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_subtree);
@@ -1812,13 +2070,19 @@
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_root);
+ cx_test_register(suite, test_tree_high_set_root);
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_add_find_remove_nodes);
cx_test_register(suite, test_tree_high_add_find_destroy_nodes);
+ cx_test_register(suite, test_tree_high_add_find_without_loc_data);
+ cx_test_register(suite, test_tree_high_find_max_depth);
+ cx_test_register(suite, test_tree_high_find_fast);
cx_test_register(suite, test_tree_high_remove_or_destroy_root);
cx_test_register(suite, test_tree_high_simple_destructor);
cx_test_register(suite, test_tree_high_iterator);
+ cx_test_register(suite, test_tree_high_iterator_large_depth);
cx_test_register(suite, test_tree_high_visitor);
return suite;