diff -r c2d05cf1a062 -r a2757c6427cc docs/Writerside/topics/tree.h.md --- a/docs/Writerside/topics/tree.h.md Wed Dec 31 15:25:30 2025 +0100 +++ b/docs/Writerside/topics/tree.h.md Wed Dec 31 16:01:08 2025 +0100 @@ -1,7 +1,7 @@ # Tree UCX provides several low-level functions for working with arbitrary tree structures, -as well as some high-level functions for trees that induce a certain order on the data they store. +as well as some high-level functions for trees with a configurable node layout. The following convenience macro allows you to declare and use simple tree structures. @@ -139,17 +139,19 @@ void *cxTreeSetRoot(CxTree *tree, void *root); ``` +The above functions are used to add nodes to a tree. + 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. +The difference between `cxTreeAddData()` and `cxTreeAddNode()` is +that `cxTreeAddData()` uses the allocator of the `CxTree` to create the node first before adding it. The function returns `NULL` in case the creation of the node fails, or the created node when creation was successful. -The difference between `cxTreeSetParent()` and `cxTreeAddNode()` is, -that `cxTreeSetParent()` does not increase the tree size, when `child` already had a parent. +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. @@ -215,6 +217,10 @@ void *cxTreeFindFast(CxTree *tree, const void *data, cx_tree_search_func sfunc); + +void *cxTreeFindFastInSubtree(CxTree *tree, const void *data, + cx_tree_search_func sfunc, + void *subtree_root, size_t max_depth); void *cxTreeFind(CxTree *tree, const void *data, bool use_dfs); @@ -227,15 +233,15 @@ The search proceeds as follows, starting with the `root` node: 1. The current node is compared with `data` using the `sfunc`. -2. If `sfunc` returns zero, a matching node has been found and the pointer to that node is stored at the location given by `result`. +2. If `sfunc` returns zero, a matching node has been found, and the pointer to that node is stored at the location given by `result`. 3. If `sfunc` returns a negative number, the entire subtree is skipped. 4. If `sfunc` returns a positive number, the subtree is searched, unless the number is larger than the number of an already searched subtree. The best match will be stored at the location given by `result`. -5. The return value will be the return value of the `sfunc` for node that was stored in the `result`, or a negative number when no match was found +5. The return value will be the return value of the `sfunc` for node, that was stored in the `result`, or a negative number when no match was found > If the `sfunc` implements some kind of metric, the search functions will return the best match in the tree with respect to that metric. > When a positive number is returned, it means that a new node with the searched data could be added as a child of the found node. -The function `cxTreeFindFast()` uses the `sfunc` to find the `data` in the tree, and returns a pointer to the node when the data was found (or `NULL`, otherwise). +The function `cxTreeFindFast()` uses the `sfunc` to find the `data` in the tree and returns a pointer to the node when the data was found (or `NULL`, otherwise). The function `cxTreeFind()` instead traverses the entire tree (either with breadth-first search or depth-first search) and compares the `data` with the collections [comparator function](collection.h.md#comparator-functions). @@ -243,7 +249,7 @@ The functions `cxTreeFindFastInSubtree()` and `cxTreeFindInSubtree()` are similar, except that they restrict the search to nodes in the subtree starting with (and including) `subtree_root`, and skipping all nodes below the `max_depth`. -Note, that the `max_depth` is specified in relation to the `subtree_root` and not in relation to the entire tree. +Note that the `max_depth` is specified in relation to the `subtree_root` and not in relation to the entire tree. ## Iterator and Visitor @@ -290,7 +296,7 @@ > In the best case it just does nothing, but calling them guarantees that no memory can be leaking, even when your code will change in the future. >{style="note"} -The macro `cxTreeIteratorContinue()` instruct the iterator to skip the subtree below the currently inspected node. +The macro `cxTreeIteratorContinue()` instructs the iterator to skip the subtree below the currently inspected node. > In contrast to iterators over [lists](list.h.md#iterators) or [maps](map.h.md#iterators), > a tree iterator is _always_ iterating over the nodes. @@ -324,7 +330,7 @@ The function `cxTreeRemoveNode()`, on the other hand, _only_ removes the `node` from the tree, links all children of `node` to the former parent of `node`, and calls the optional `relink_func` for every former child of `node` which will be relinked to a new parent. -Therefore, calling `cxTreeRemoveNode()` on the `root` node is an error and the function returns non-zero. +Therefore, calling `cxTreeRemoveNode()` on the `root` node is an error, and the function returns non-zero. In all other cases, the function returns zero. > When your tree is storing a scene graph, for example, a possible use-case for the `relink_func` might be updating @@ -357,7 +363,7 @@ The function `cxTreeDestroySubtree()` performs the above actions for the entire subtree starting with `node`. The order in which the destructor functions for the nodes of the subtree are called is determined by a [tree iterator](#iterator-and-visitor). -The function `cxTreeClear()` is a shorthand for invoking `cxTreeDestroySubtree()` on the root node of the tree. +The function `cxTreeClear()` is short for invoking `cxTreeDestroySubtree()` on the root node of the tree if it exists. The function `cxTreeFree()` behaves like `cxTreeClear()` and then deallocates the memory for the `CxTree` structure.