Mercurial > hg > ucx / changeset

--- a/docs/Writerside/topics/tree.h.md	Thu Mar 20 20:12:37 2025 +0100
+++ b/docs/Writerside/topics/tree.h.md	Thu Mar 20 20:12:53 2025 +0100
@@ -1,8 +1,33 @@
 # Tree
 
-<warning>
-TODO: intro text
-</warning>
+UCX provides several low-level function 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. 
+
+The following convenience macros allow you to declare and use simple tree structures.
+
+```C
+#define CX_TREE_NODE_BASE(Type)
+
+#define cx_tree_node_base_layout
+```
+
+The `CX_TREE_NODE_BASE` macro declares four pointers of type `Type*`:
+`parent`, `children`, `last_child`, `prev`, and `next`,
+which must be placed as first member into your struct.
+
+You can use it for example like this:
+```C
+typedef struct my_tree_node_s {
+    CX_TREE_NODE_BASE(struct my_tree_node_s);
+    int value;
+    char *desc;
+} MyTreeNode;
+```
+
+The macro `cx_tree_node_base_layout` expands to the offsets of the above-mentioned pointers.
+It will become handy when calling the low-level tree functions which expect all offsets to be passed as arguments. 
+
+Before diving into the function definitions, there are four function pointer declarations you should know.
 
 ```C
 #include <cx/tree.h>
@@ -18,11 +43,23 @@
 
 typedef void (*cx_tree_relink_func)(
         void *node, const void *old_parent, const void *new_parent);
+```
 
-#define CX_TREE_NODE_BASE(type)
+A `cx_tree_node_create_func` takes a pointer to the `data` the new node shall contain, and a `context` (which might be an allocator, for example).
+It shall allocate and return the created node, or `NULL` when node creation is not possible.
 
-#define cx_tree_node_base_layout
-```
+A `cx_tree_search_data_func` shall check if the `node` contains the `data`, or if a child node might contain the data.
+It shall return zero, when `node` contains the `data`.
+When a child node _might_ contain the data, the returned positive number shall indicate how close the match is.
+It is _not_ relevant if the data can actually be found in the subtree - the positive number also indicates that the data could be inserted in that subtree.
+Only when the entire subtree starting with `node` cannot contain the `data`, a negative number is supposed to be returned.
+
+A `cx_tree_search_func` behaves exactly the same, except that it does expect a pointer to the `data` but a pointer to a node structure.
+In combination with the `cx_tree_node_create_func`, when inserting nodes with the high-level functions, a `new_node` is created first,
+and then an appropriate insertion point is searched with the `cx_tree_search_func`.
+
+A `cx_tree_relink_func` is used when an intermediate node is removed from the tree and it's children need to be detached from
+the removed `old_parent` and attached to a `new_parent`.
 
 ## Create
 
@@ -214,7 +251,7 @@
 ```
 
 <warning>
-TODO: document
+TODO: document and mention the destructor support
 </warning>
 
 <seealso>