comparison: docs/Writerside/topics/tree.h.md
docs/Writerside/topics/tree.h.md
- changeset 1254
- 6a342294499b
- parent 1252
- 14c227b28a96
- child 1255
- a9d730c8b94a
equal
deleted
inserted
replaced
| 1253:2819ae724034 | 1254:6a342294499b |
|---|---|
| 1 # Tree | 1 # Tree |
| 2 | 2 |
| 3 <warning> | 3 UCX provides several low-level function for working with arbitrary tree structures, |
| 4 TODO: intro text | 4 as well as some high-level functions for trees that induce a certain order on the data they store. |
| 5 </warning> | 5 |
| 6 The following convenience macros allow you to declare and use simple tree structures. | |
| 7 | |
| 8 ```C | |
| 9 #define CX_TREE_NODE_BASE(Type) | |
| 10 | |
| 11 #define cx_tree_node_base_layout | |
| 12 ``` | |
| 13 | |
| 14 The `CX_TREE_NODE_BASE` macro declares four pointers of type `Type*`: | |
| 15 `parent`, `children`, `last_child`, `prev`, and `next`, | |
| 16 which must be placed as first member into your struct. | |
| 17 | |
| 18 You can use it for example like this: | |
| 19 ```C | |
| 20 typedef struct my_tree_node_s { | |
| 21 CX_TREE_NODE_BASE(struct my_tree_node_s); | |
| 22 int value; | |
| 23 char *desc; | |
| 24 } MyTreeNode; | |
| 25 ``` | |
| 26 | |
| 27 The macro `cx_tree_node_base_layout` expands to the offsets of the above-mentioned pointers. | |
| 28 It will become handy when calling the low-level tree functions which expect all offsets to be passed as arguments. | |
| 29 | |
| 30 Before diving into the function definitions, there are four function pointer declarations you should know. | |
| 6 | 31 |
| 7 ```C | 32 ```C |
| 8 #include <cx/tree.h> | 33 #include <cx/tree.h> |
| 9 | 34 |
| 10 typedef void *(*cx_tree_node_create_func)( | 35 typedef void *(*cx_tree_node_create_func)( |
| 16 typedef int (*cx_tree_search_func)( | 41 typedef int (*cx_tree_search_func)( |
| 17 const void *node, const void *new_node); | 42 const void *node, const void *new_node); |
| 18 | 43 |
| 19 typedef void (*cx_tree_relink_func)( | 44 typedef void (*cx_tree_relink_func)( |
| 20 void *node, const void *old_parent, const void *new_parent); | 45 void *node, const void *old_parent, const void *new_parent); |
| 21 | 46 ``` |
| 22 #define CX_TREE_NODE_BASE(type) | 47 |
| 23 | 48 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). |
| 24 #define cx_tree_node_base_layout | 49 It shall allocate and return the created node, or `NULL` when node creation is not possible. |
| 25 ``` | 50 |
| 51 A `cx_tree_search_data_func` shall check if the `node` contains the `data`, or if a child node might contain the data. | |
| 52 It shall return zero, when `node` contains the `data`. | |
| 53 When a child node _might_ contain the data, the returned positive number shall indicate how close the match is. | |
| 54 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. | |
| 55 Only when the entire subtree starting with `node` cannot contain the `data`, a negative number is supposed to be returned. | |
| 56 | |
| 57 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. | |
| 58 In combination with the `cx_tree_node_create_func`, when inserting nodes with the high-level functions, a `new_node` is created first, | |
| 59 and then an appropriate insertion point is searched with the `cx_tree_search_func`. | |
| 60 | |
| 61 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 | |
| 62 the removed `old_parent` and attached to a `new_parent`. | |
| 26 | 63 |
| 27 ## Create | 64 ## Create |
| 28 | 65 |
| 29 ```C | 66 ```C |
| 30 #include <cx/tree.h> | 67 #include <cx/tree.h> |
| 212 | 249 |
| 213 void cxTreeFree(CxTree *tree); | 250 void cxTreeFree(CxTree *tree); |
| 214 ``` | 251 ``` |
| 215 | 252 |
| 216 <warning> | 253 <warning> |
| 217 TODO: document | 254 TODO: document and mention the destructor support |
| 218 </warning> | 255 </warning> |
| 219 | 256 |
| 220 <seealso> | 257 <seealso> |
| 221 <category ref="apidoc"> | 258 <category ref="apidoc"> |
| 222 <a href="https://ucx.sourceforge.io/api/tree_8h.html">tree.h</a> | 259 <a href="https://ucx.sourceforge.io/api/tree_8h.html">tree.h</a> |
