# HG changeset patch # User Mike Becker # Date 1767189520 -3600 # Node ID 7d41291b30957dcacda8dfd2c0166af3f3908c03 # Parent a5b7cf49dea755bf8d2bd910d8d45bfe104b5891 complete tree.c testing diff -r a5b7cf49dea7 -r 7d41291b3095 docs/Writerside/topics/tree.h.md --- a/docs/Writerside/topics/tree.h.md Wed Dec 31 13:39:55 2025 +0100 +++ b/docs/Writerside/topics/tree.h.md Wed Dec 31 14:58:40 2025 +0100 @@ -124,15 +124,26 @@ ptrdiff_t loc_children, ptrdiff_t loc_last_child, ptrdiff_t loc_prev, ptrdiff_t loc_next); +void *cxTreeCreateRootData(CxTree *tree, const void *data); + +void *cxTreeCreateRoot(CxTree *tree, void *child); + +void *cxTreeCreateNode(CxTree *tree, void *parent); + void *cxTreeAddData(CxTree *tree, void *parent, const void *data); void cxTreeAddNode(CxTree *tree, void *parent, void *child); void cxTreeSetParent(CxTree *tree, void *parent, void *child); + +void *cxTreeSetRoot(CxTree *tree, void *root); ``` The low-level function `cx_tree_add()` adds a `node` to a new `parent`, unlinking it from its previous parent, if required. +When you have created a high-level tree that is still empty, you can create a root node with `cxTreeCreateRoot()` or `cxTreeCreateRootData()`. +Both functions return an existing root node, if present, and `NULL` when the allocation of a new node failed. + The functions `cxTreeAddData()`, `cxTreeAddNode()`, and `cxTreeSetParent()` are similar to `cx_tree_add()`. The difference between `cxTreeAddData()` and `cxTreeAddNode()` is, that `cxTreeAddData()` uses the allocator of the `CxTree` to create the node first, before adding it. @@ -140,11 +151,19 @@ The difference between `cxTreeSetParent()` and `cxTreeAddNode()` is, that `cxTreeSetParent()` does not increase the tree size, when `child` already had a parent. +When you want to use `cxTreeCreateRootData()` or `cxTreeAddData()`, +the `loc_data` parameter of `cxTreeCreate()` must have been set to a non-negative value. +Otherwise, the functions will return `NULL`. + > Use `cxTreeAddNode()` to add _new_ nodes to the tree and `cxTreeSetParent()` > to relink a subtree of the `tree` with a new parent. > > Using `cxTreeSetParent()` on a `child` which already has a parent in a _different_ tree is a mistake. +The function `cxTreeSetRoot()` returns the current root node of the tree, +or `NULL` when the tree is empty, and sets a new root node. +It is up to the caller to take care of a possibly necessary deallocation of the old tree nodes. +Also, keep in mind that the tree might have destructors registered which will be applied to the nodes belonging to the new root. ## Size and Depth diff -r a5b7cf49dea7 -r 7d41291b3095 src/cx/tree.h --- a/src/cx/tree.h Wed Dec 31 13:39:55 2025 +0100 +++ b/src/cx/tree.h Wed Dec 31 14:58:40 2025 +0100 @@ -484,6 +484,12 @@ * The specified @p allocator will be used for creating the tree struct * @em and the nodes. * + * When you do not specify an existing @p root, the tree will be created + * empty. Additionally, cxFree() is registered as the advanced destructor for + * the tree so that all nodes that you will add to the tree are automatically + * freed together with the tree. + * When @p root is not @c NULL, no destructors are registered automatically. + * * @param allocator the allocator to use * (if @c NULL, the cxDefaultAllocator is assumed) * @param node_size the complete size of one node @@ -720,12 +726,55 @@ CX_EXTERN CX_NONNULL void *cxTreeAddData(CxTree *tree, void *parent, const void *data); -CX_EXTERN CX_NODISCARD +/** + * Creates a new node and adds it to the tree. + * + * @param tree the tree + * @param parent the parent node of the new node + * @return the added node or @c NULL when the allocation failed + */ +CX_EXTERN CX_NODISCARD CX_NONNULL +void *cxTreeCreateNode(CxTree *tree, void *parent); + +/** + * Creates a new root node or returns the existing root node. + * + * @param tree the tree + * @return the new root node, the existing root node, or @c NULL when the allocation failed + * @see cxTreeCreateRootData() + */ +CX_EXTERN CX_NODISCARD CX_NONNULL void *cxTreeCreateRoot(CxTree *tree); -CX_EXTERN CX_NODISCARD +/** + * Creates a new root node or uses the existing root node and writes the specified data to that node. + * + * @note This function immediately returns @c NULL when @c loc_data was not initialized with a positive value. + * + * @param tree the tree + * @param data the data for the root node + * @return the new root node, the existing root node, + * or @c NULL when the allocation failed or the data location is not known + * @see cxTreeCreateRoot() + */ +CX_EXTERN CX_NODISCARD CX_NONNULL void *cxTreeCreateRootData(CxTree *tree, const void *data); +/** + * Exchanges the root of the tree. + * + * @attention The old tree nodes might need to be deallocated by the caller. + * On the other hand, when the tree has destructors registered, keep in mind + * that they will be applied to the new tree. + * In particular, using cxTreeCreate() with a @c NULL root and setting the + * root with this function is @em not equivalent to creating the tree with + * a reference to an existing root because trees created without a root will + * have destructors registered. + * + * @param tree the tree + * @param new_root the new root node + * @return the old root node (or @c NULL when the tree was empty) + */ CX_EXTERN CX_NONNULL_ARG(1) CX_NODISCARD void *cxTreeSetRoot(CxTree *tree, void *new_root); diff -r a5b7cf49dea7 -r 7d41291b3095 src/tree.c --- a/src/tree.c Wed Dec 31 13:39:55 2025 +0100 +++ b/src/tree.c Wed Dec 31 14:58:40 2025 +0100 @@ -314,7 +314,7 @@ // node has children, push the first child onto the stack and enter it if (iter->depth >= iter->stack_capacity) { const size_t newcap = iter->stack_capacity + 8; - if (cxReallocArrayDefault(&iter->stack, newcap, sizeof(void*))) { + if (cxReallocateArrayDefault(&iter->stack, newcap, sizeof(void*))) { // we cannot return an error in this function abort(); // LCOV_EXCL_LINE } @@ -568,10 +568,18 @@ tree->collection.size++; } +void *cxTreeCreateNode(CxTree *tree, void *parent) { + void *node = cxZalloc(tree->collection.allocator, tree->node_size); + if (node == NULL) return NULL; // LCOV_EXCL_LINE + cx_tree_add(parent, node, tree_layout(tree)); + tree->collection.size++; + return node; +} + void *cxTreeAddData(CxTree *tree, void *parent, const void *data) { if (tree->loc_data < 0) return NULL; - void *node = cxZalloc(tree->collection.allocator, tree->node_size); + void *node = cxTreeCreateNode(tree, parent); if (node == NULL) return NULL; // LCOV_EXCL_LINE char *dst = node; @@ -579,8 +587,6 @@ const void *src = cxCollectionStoresPointers(tree) ? (const void*)&data : data; memcpy(dst, src, tree->collection.elem_size); - cx_tree_add(parent, node, tree_layout(tree)); - tree->collection.size++; return node; } diff -r a5b7cf49dea7 -r 7d41291b3095 tests/test_tree.c --- 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;