Mercurial > hg > ucx / changeset

--- 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
 

--- 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);
 

--- 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;
 }
 

--- 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;