Mercurial > hg > ucx / file comparison

comparison: docs/Writerside/topics/tree.h.md

docs/Writerside/topics/tree.h.md

changeset 1681
56e76fbac167
parent 1605
55b13f583356
equal deleted inserted replaced
1680:1aa21afb8763 1681:56e76fbac167
1 # Tree 1 # Tree
2 2
3 UCX provides several low-level functions for working with arbitrary tree structures, 3 UCX provides several low-level functions for working with arbitrary tree structures,
4 as well as some high-level functions for trees that induce a certain order on the data they store. 4 as well as some high-level functions for trees that induce a certain order on the data they store.
5 5
6 The following convenience macros allow you to declare and use simple tree structures. 6 The following convenience macro allows you to declare and use simple tree structures.
7 7
8 ```C 8 ```C
9 #define CX_TREE_NODE_BASE(Type) 9 #define CX_TREE_NODE(Type)
10 10 ```
11 #define cx_tree_node_base_layout 11
12 ``` 12 It declares four pointers of type `Type*`:
13 13 `parent`, `children`, `last_child`, `prev`, and `next`.
14 The `CX_TREE_NODE_BASE` macro declares four pointers of type `Type*`: 14 It can be placed anywhere in your node structure, but it is recommended
15 `parent`, `children`, `last_child`, `prev`, and `next`, 15 to use them as first members to avoid padding issues.
16 which must be placed as first member into your struct.
17 16
18 You can use it, for example, like this: 17 You can use it, for example, like this:
19 ```C 18 ```C
20 typedef struct my_tree_node_s { 19 typedef struct my_tree_node_s {
21 CX_TREE_NODE_BASE(struct my_tree_node_s); 20 CX_TREE_NODE(struct my_tree_node_s);
22 int value; 21 int value;
23 char *desc; 22 char *desc;
24 } MyTreeNode; 23 } MyTreeNode;
25 ``` 24 ```
26 25
27 The macro `cx_tree_node_base_layout` expands to the offsets of the above-mentioned pointers. 26 The macro `cx_tree_node_layout(name)` 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. 27 It will become handy when calling the low-level tree functions which expect all offsets to be passed as arguments.
29 28
30 > In all functions, the `last_child` and `prev` pointers are completely optional. 29 > In all functions, the `last_child` and `prev` pointers are completely optional.
31 > If your tree structure does not contain the `last_child` pointer, the last child will be determined by 30 > If your tree structure does not contain the `last_child` pointer, the last child will be determined by
32 > traversing all children from the first child. 31 > traversing all children from the first child.
33 > The same happens when it does not have a `prev` pointer, and the left sibling of a child is needed. 32 > The same happens when it does not have a `prev` pointer, and the left sibling of a child is needed.
34 > The `children` pointer (which points to the first child), and the `next` pointer are mandatory, 33 > The `children` pointer (which points to the first child), and the `next` pointer are mandatory,
35 > and so is the `parent` pointer. 34 > and so is the `parent` pointer.
36 35
37 Before diving into the function definitions, there are four function pointer declarations you should know.
38
39 ```C
40 #include <cx/tree.h>
41
42 typedef void *(*cx_tree_node_create_func)(
43 const void *data, void *context);
44
45 typedef int (*cx_tree_search_data_func)(
46 const void *node, const void *data);
47
48 typedef int (*cx_tree_search_func)(
49 const void *node, const void *new_node);
50
51 typedef void (*cx_tree_relink_func)(
52 void *node, const void *old_parent, const void *new_parent);
53 ```
54
55 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).
56 It shall allocate and return the created node, or `NULL` when node creation is not possible.
57
58 A `cx_tree_search_data_func` shall check if the `node` contains the `data`, or if a child node might contain the data.
59 It shall return zero, when `node` contains the `data`.
60 When a child node _might_ contain the data, the returned positive number shall indicate how close the match is.
61 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.
62 Only when the entire subtree starting with `node` cannot contain the `data`, a negative number is supposed to be returned.
63
64 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.
65 In combination with the `cx_tree_node_create_func`, when inserting nodes with the high-level functions, a `new_node` is created first,
66 and then an appropriate insertion point is searched with the `cx_tree_search_func`.
67
68 A `cx_tree_relink_func` is called when an intermediate node was removed from the tree and it's children need to be detached from
69 the removed `old_parent` and attached to a `new_parent`.
70 The function is called for every child of the removed node and can be used, for example, to update the contents of the node when needed.
71
72 ## Create 36 ## Create
73 37
74 ```C 38 ```C
75 #include <cx/tree.h> 39 #include <cx/tree.h>
76 40
77 CxTree *cxTreeCreate(const CxAllocator *allocator, 41 CxTree *cxTreeCreate(const CxAllocator *allocator,
78 cx_tree_node_create_func create_func, 42 size_t node_size, size_t elem_size,
79 cx_tree_search_func search_func, 43 void *root, ptrdiff_t loc_data,
80 cx_tree_search_data_func search_data_func, 44 ptrdiff_t loc_parent, ptrdiff_t loc_children,
81 ptrdiff_t loc_parent, 45 ptrdiff_t loc_last_child,
82 ptrdiff_t loc_children, ptrdiff_t loc_last_child,
83 ptrdiff_t loc_prev, ptrdiff_t loc_next); 46 ptrdiff_t loc_prev, ptrdiff_t loc_next);
84 47 ```
85 CxTree *cxTreeCreateSimple(const CxAllocator *allocator, 48
86 cx_tree_node_create_func create_func, 49 The function `cxTreeCreate()` creates a `CxTree` structure with the specified layout.
87 cx_tree_search_func search_func, 50 You can use the `cx_tree_node_layout()` macro to fill in the locations starting with `loc_parent`.
88 cx_tree_search_data_func search_data_func); 51
89 52 > The `node_size` is used by `cxTreeCreateRootData()` and `cxTreeAddData()` to allocate memory for new tree nodes.
90 CxTree *cxTreeCreateWrapped(const CxAllocator *allocator, 53 > The `elem_size` is used to copy the data into the new node.
91 void *root, 54 > See [below](#add-nodes) for details.
92 ptrdiff_t loc_parent, 55
93 ptrdiff_t loc_children, ptrdiff_t loc_last_child, 56 The `loc_data` location is optional.
94 ptrdiff_t loc_prev, ptrdiff_t loc_next); 57 If specified, the functions `cxTreeCreateRootData()`, `cxTreeAddData()`, `cxTreeFind()`, and `cxTreeFindInSubtree()`
95 ``` 58 will resolve the location to copy or compare the data.
96 59 A location of zero means that a pointer to the entire node is used
97 The function `cxTreeCreate()` creates a `CxTree` structure 60 (in that case the `elem_size` MUST be a positive number and SHOULD equal the `node_size`).
98 where each node created by the `create_func` has the layout specified by the offset arguments. 61
99 The function `cxTreeCreateSimple()` is exactly the same, except that it assumes the `cx_tree_node_base_layout`. 62 If your tree structure does not have a `last_child` or a `prev` pointer,
100
101 In both cases the tree will be created empty, that is with no nodes, not even a root node.
102 On the other hand, `cxTreeCreateWrapped()` creates a `CxTree` structure with the specified layout and `root` node
103 where `root` may already be the root of a larger tree.
104
105 If your wrapped tree structure does not have a `last_child` or a `prev` pointer,
106 you may specify a negative location to indicate the missing pointer. 63 you may specify a negative location to indicate the missing pointer.
107 All other pointers are mandatory and a non-negative location is expected. 64 All other pointers are mandatory and a non-negative location is expected.
108 65
109 Note that a wrapped tree by default has no create or search functions assigned. 66 The `root` node is optional.
110 Therefore, if you wish to use one of the functions below that needs those function pointers set, 67 If not specified, the tree is initialized empty and `cxFree` is registered as advanced destructor.
111 you will have to set them manually by assigning to the respective fields in the `CxTree` structure. 68 If a `root` is specified, the initial tree size is calculated and stored in the collection's metadata.
69 Also, no destructors are specified and the nodes will not be deallocated when destroying the tree to avoid
70 use-after-free bugs when the `root` is still in use elsewhere.
112 71
113 ### Example for wrapping a libxml2 tree 72 ### Example for wrapping a libxml2 tree
114 73
115 In this example we wrap the XML tree of the commonly used libxml2 library. 74 In this example we wrap the XML tree of the commonly used libxml2 library.
116 75
117 ```C 76 ```C
118 #include <libxml/tree.h> 77 #include <libxml/tree.h>
119 #include <cx/tree.h> 78 #include <cx/tree.h>
120 79
121 CxTree *wrap_xml_tree(xmlNode *root) { 80 CxTree *wrap_xml_tree(xmlNode *root) {
122 return cxTreeCreateWrapped( 81 return cxTreeCreate(
123 cxDefaultAllocator, // or you can just write NULL 82 cxDefaultAllocator, // or you can just write NULL
124 root, 83 sizeof(xmlNode), sizeof(xmlNode), root, 0,
125 offsetof(xmlNode, parent), 84 offsetof(xmlNode, parent),
126 offsetof(xmlNode, children), 85 offsetof(xmlNode, children),
127 offsetof(xmlNode, last), 86 offsetof(xmlNode, last),
128 offsetof(xmlNode, prev), 87 offsetof(xmlNode, prev),
129 offsetof(xmlNode, next) 88 offsetof(xmlNode, next)
130 ); 89 );
131 } 90 }
132 ``` 91 ```
133
134 You do not need to specify any function pointers or destructors in the `CxTree` structure,
135 if you just want to use the resulting `CxTree` for [iterating](#iterator-and-visitor) over the nodes.
136 92
137 You can, for example, print the XML structure with the following code: 93 You can, for example, print the XML structure with the following code:
138 94
139 ```C 95 ```C
140 // continued from above 96 // continued from above
162 ## Add Nodes 118 ## Add Nodes
163 119
164 ```C 120 ```C
165 #include <cx/tree.h> 121 #include <cx/tree.h>
166 122
167 void cx_tree_link(void *parent, void *node, ptrdiff_t loc_parent, 123 void cx_tree_add(void *parent, void *node, ptrdiff_t loc_parent,
168 ptrdiff_t loc_children, ptrdiff_t loc_last_child, 124 ptrdiff_t loc_children, ptrdiff_t loc_last_child,
169 ptrdiff_t loc_prev, ptrdiff_t loc_next); 125 ptrdiff_t loc_prev, ptrdiff_t loc_next);
170 126
171 extern unsigned int cx_tree_add_look_around_depth; 127 void *cxTreeAddData(CxTree *tree, void *parent, const void *data);
172 128
173 size_t cx_tree_add_iter(struct cx_iterator_base_s *iter, size_t n, 129 void cxTreeAddNode(CxTree *tree, void *parent, void *child);
174 cx_tree_search_func sfunc, cx_tree_node_create_func cfunc,
175 void *cdata, void **failed, void *root,
176 ptrdiff_t loc_parent,
177 ptrdiff_t loc_children, ptrdiff_t loc_last_child,
178 ptrdiff_t loc_prev, ptrdiff_t loc_next);
179
180 size_t cx_tree_add_array(const void *src, size_t n, size_t elem_size,
181 cx_tree_search_func sfunc, cx_tree_node_create_func cfunc,
182 void *cdata, void **failed, void *root,
183 ptrdiff_t loc_parent,
184 ptrdiff_t loc_children, ptrdiff_t loc_last_child,
185 ptrdiff_t loc_prev, ptrdiff_t loc_next);
186
187 int cx_tree_add(const void *src,
188 cx_tree_search_func sfunc, cx_tree_node_create_func cfunc,
189 void *cdata, void **cnode, void *root,
190 ptrdiff_t loc_parent,
191 ptrdiff_t loc_children, ptrdiff_t loc_last_child,
192 ptrdiff_t loc_prev, ptrdiff_t loc_next);
193 ```
194
195 The low-level function `cx_tree_link()` adds a `node` to a new `parent`, unlinking it from its previous parent, if required.
196
197 The functions `cx_tree_add_array()` and `cx_tree_add_iter()` are equivalent,
198 except that the former adds `n` items of size `elem_size` from the `src` array,
199 and the latter adds _up to_ `n` items from the iterator `iter`.
200 For each element, the `cfun` is called with the element as first argument and the `cdata` context as second argument.
201 The `cfun` function is supposed to return a node for which then the `sfunc` is used to find the location where to insert the node.
202 If a node could not be added, because `sfunc` always returns a negative number, it is stored at the location where `failed` points to.
203
204 > The functions `cx_tree_add_array()` and `cx_tree_add_iter()` are optimized for adding multiple nodes to
205 > the same subtree without starting the search all over from the root node.
206 > This behavior can be controlled with `cx_tree_add_look_around_depth`, which specifies for how many parent nodes
207 > the algorithm backtracks in the current subtree before restarting the search from the root node.
208
209 The function `cx_tree_add()` is similar to the other add-functions,
210 except that it does only add one single item to the tree and always stores the created node at the location where `cnode` points to.
211
212 > By design, the add-functions can only be used to add children to the tree.
213 > If you want to add a new root node, this is much easier by simply calling `cx_tree_link(newroot, oldroot, layout...)` .
214
215 The following high-level functions can be used to add nodes to a `CxTree`.
216
217 ```C
218 #include <cx/tree.h>
219
220 int cxTreeAddChild(CxTree *tree, void *parent, const void *data);
221
222 void cxTreeAddChildNode(CxTree *tree, void *parent, void *child);
223 130
224 void cxTreeSetParent(CxTree *tree, void *parent, void *child); 131 void cxTreeSetParent(CxTree *tree, void *parent, void *child);
225 132 ```
226 int cxTreeInsert(CxTree *tree, const void *data); 133
227 134 The low-level function `cx_tree_add()` adds a `node` to a new `parent`, unlinking it from its previous parent, if required.
228 size_t cxTreeInsertIter(CxTree *tree, CxIteratorBase *iter, size_t n); 135
229 136 The functions `cxTreeAddData()`, `cxTreeAddNode()`, and `cxTreeSetParent()` are similar to `cx_tree_add()`.
230 size_t cxTreeInsertArray(CxTree *tree, const void *data, 137 The difference between `cxTreeAddData()` and `cxTreeAddNode()` is,
231 size_t elem_size, size_t n); 138 that `cxTreeAddData()` uses the allocator of the `CxTree` to create the node first, before adding it.
232 ``` 139 The function returns `NULL` in case the creation of the node fails, or the created node when creation was successful.
233 140 The difference between `cxTreeSetParent()` and `cxTreeAddNode()` is,
234 The functions `cxTreeAddChild()`, `cxTreeAddChildNode()`, and `cxTreeSetParent()` are similar to `cx_tree_link()`.
235 The difference between `cxTreeAddChild()` and `cxTreeAddChildNode()` is,
236 that `cxTreeAddChild()` uses the `cx_tree_node_create_func` of the `CxTree` to create the node first, before adding it.
237 The function returns non-zero in case the creation of the node fails.
238 The difference between `cxTreeSetParent()` and `cxTreeAddChildNode()` is,
239 that `cxTreeSetParent()` does not increase the tree size, when `child` already had a parent. 141 that `cxTreeSetParent()` does not increase the tree size, when `child` already had a parent.
240 142
241 > Use `cxTreeAddChildNode()` to add _new_ nodes to the tree and `cxTreeSetParent()` 143 > Use `cxTreeAddNode()` to add _new_ nodes to the tree and `cxTreeSetParent()`
242 > to relink a subtree of the `tree` with a new parent. 144 > to relink a subtree of the `tree` with a new parent.
243 > 145 >
244 > Using `cxTreeSetParent()` on a `child` which already has a parent in a _different_ tree is a mistake. 146 > Using `cxTreeSetParent()` on a `child` which already has a parent in a _different_ tree is a mistake.
245 147
246 The functions `cxTreeInsert()`, `cxTreeInsertIter()`, and `cxTreeInsertArray()` behave
247 like `cx_tree_add()`, `cx_tree_add_iter()`, and `cx_tree_add_array()`.
248 As creation context `cdata` for the `cx_tree_node_create_func` a pointer to the `CxTree` is passed.
249 Instead of returning a `failed` node, like the low-level functions, the high-level functions automatically free the memory for the failed node.
250 148
251 ## Size and Depth 149 ## Size and Depth
252 150
253 ```C 151 ```C
254 #include <cx/tree.h> 152 #include <cx/tree.h>
153
154 size_t cx_tree_size(void *root,
155 ptrdiff_t loc_children, ptrdiff_t loc_next);
156
157 size_t cx_tree_depth(void *root,
158 ptrdiff_t loc_children, ptrdiff_t loc_next);
255 159
256 size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root); 160 size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root);
257 161
258 size_t cxTreeSubtreeDepth(CxTree *tree, void *subtree_root); 162 size_t cxTreeSubtreeDepth(CxTree *tree, void *subtree_root);
259 163
267 The function `cxTreeSubtreeDepth()` reports the maximum depth of the subtree starting with `subtree_root`. 171 The function `cxTreeSubtreeDepth()` reports the maximum depth of the subtree starting with `subtree_root`.
268 If the `subtree_root` does not have any children, this results in a depth of one. 172 If the `subtree_root` does not have any children, this results in a depth of one.
269 173
270 The functions `cxTreeSize()` and `cxTreeDepth()` are equivalent to `cxTreeSubtreeSize()` and `cxTreeSubtreeDepth()`, respectively, where `subtree_root` is the root node of the entire tree. 174 The functions `cxTreeSize()` and `cxTreeDepth()` are equivalent to `cxTreeSubtreeSize()` and `cxTreeSubtreeDepth()`, respectively, where `subtree_root` is the root node of the entire tree.
271 175
272 > Passing a `NULL` pointer as `subtree_root` makes those functions return zero. 176 The functions `cx_tree_size()` and `cx_tree_depth()` are the low-level counterparts.
177
178 > Passing a `NULL` pointer as `root` or `subtree_root` makes those functions return zero.
179
180 > Since the size of a `CxTree` is stored in the [collection](collection.h.md) metadata, `cxTreeSize()` is actually a constant time operation.
181 > This is not the case for `cxTreeSubtreeSize()` or `cx_tree_size()` where the size has to be calculated by traversing the tree.
273 182
274 ## Search 183 ## Search
275 184
276 ```C 185 ```C
277 #include <cx/tree.h> 186 #include <cx/tree.h>
278 187
279 #define CX_TREE_SEARCH_INFINITE_DEPTH 188 #define CX_TREE_SEARCH_INFINITE_DEPTH 0
280 189
281 int cx_tree_search_data(const void *root, size_t max_depth, 190 typedef int (*cx_tree_search_func)(
282 const void *data, cx_tree_search_data_func sfunc, 191 const void *node, const void *data);
283 void **result, ptrdiff_t loc_children, ptrdiff_t loc_next);
284 192
285 int cx_tree_search(const void *root, size_t max_depth, 193 int cx_tree_search(const void *root, size_t max_depth,
286 const void *node, cx_tree_search_func sfunc, 194 const void *data, cx_tree_search_func sfunc, void **result,
287 void **result, ptrdiff_t loc_children, ptrdiff_t loc_next); 195 bool use_dfs, ptrdiff_t loc_children, ptrdiff_t loc_next);
196
197 void *cxTreeFindFast(CxTree *tree, const void *data,
198 cx_tree_search_func sfunc);
288 199
289 void *cxTreeFind(CxTree *tree, const void *data); 200 void *cxTreeFind(CxTree *tree, const void *data, bool use_dfs);
290 201
291 void *cxTreeFindInSubtree(CxTree *tree, const void *data, 202 void *cxTreeFindInSubtree(CxTree *tree, const void *data,
292 void *subtree_root, size_t max_depth); 203 void *subtree_root, size_t max_depth, bool use_dfs);
293 ``` 204 ```
294 205
295 The functions `cx_tree_search_data()` and `cx_tree_search()` are equivalent, 206 The function `cx_tree_search()` efficiently finds a node in the tree.
296 except that `cx_tree_search_data()` compares a currently investigated node against the `data` with the specified `cx_tree_search_data_func`,
297 and `cx_tree_search()` compares against a `node` with the specified `cx_tree_search_func`.
298
299 Usually you the latter is rarely needed.
300 It is used, for example, by `cx_tree_add()` to find the correct position where to add a freshly created node.
301 207
302 The search proceeds as follows, starting with the `root` node: 208 The search proceeds as follows, starting with the `root` node:
303 209
304 1. The current node is compared with `data` / `node` using the `sfunc`. 210 1. The current node is compared with `data` using the `sfunc`.
305 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`. 211 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`.
306 3. If `sfunc` returns a negative number, the entire subtree is skipped. 212 3. If `sfunc` returns a negative number, the entire subtree is skipped.
307 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`. 213 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`.
308 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 214 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
309 215
310 > If the `sfunc` implements some kind of metric, the search functions will return the best match in the tree with respect to that metric. 216 > If the `sfunc` implements some kind of metric, the search functions will return the best match in the tree with respect to that metric.
311 > 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. 217 > 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.
312 > This is exactly how `cx_tree_add()` finds the best position to add a node to the tree. 218
313 219 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).
314 The function `cxTreeFind()` uses the `search_data_func` of the `CxTree` 220
315 to find the `data` in the tree, and returns a pointer to the node when the data was found (or `NULL`, otherwise). 221 The function `cxTreeFind()` instead traverses the entire tree (either with breadth-first search or depth-first search)
316 222 and compares the `data` with the collections [comparator function](collection.h.md#comparator-functions).
317 The function `cxTreeFindInSubtree()` is equivalent, except that it restricts the search to nodes 223 For this it is necessary that the `loc_data` was specified when creating the tree, or the function will immediately return `NULL`.
224
225 The functions `cxTreeFindFastInSubtree()` and `cxTreeFindInSubtree()` are similar, except that they restrict the search to nodes
318 in the subtree starting with (and including) `subtree_root`, and skipping all nodes below the `max_depth`. 226 in the subtree starting with (and including) `subtree_root`, and skipping all nodes below the `max_depth`.
319 Note, that the `max_depth` is specified in relation to the `subtree_root` and not in relation to the entire tree. 227 Note, that the `max_depth` is specified in relation to the `subtree_root` and not in relation to the entire tree.
320 228
321 ## Iterator and Visitor 229 ## Iterator and Visitor
322 230
323 ```C 231 ```C
324 #include <cx/tree.h> 232 #include <cx/tree.h>
329 CxTreeIterator cxTreeIterate(CxTree *tree, bool visit_on_exit); 237 CxTreeIterator cxTreeIterate(CxTree *tree, bool visit_on_exit);
330 238
331 CxTreeIterator cxTreeIterateSubtree(CxTree *tree, 239 CxTreeIterator cxTreeIterateSubtree(CxTree *tree,
332 void *node, bool visit_on_exit); 240 void *node, bool visit_on_exit);
333 241
242 CxTreeIterator cx_tree_visitor(void *root,
243 ptrdiff_t loc_children, ptrdiff_t loc_next);
244
245 CxTreeIterator cxTreeVisit(CxTree *tree);
246
247 CxTreeIterator cxTreeVisitSubtree(CxTree *tree, void *node)
248
334 #define cxTreeIteratorContinue(iter) 249 #define cxTreeIteratorContinue(iter)
335 250
336 void cxTreeIteratorDispose(CxTreeIterator *iter); 251 void cxTreeIteratorDispose(CxTreeIterator *iter);
337
338
339 CxTreeVisitor cx_tree_visitor(void *root,
340 ptrdiff_t loc_children, ptrdiff_t loc_next);
341
342 CxTreeVisitor cxTreeVisit(CxTree *tree);
343
344 CxTreeVisitor cxTreeVisitSubtree(CxTree *tree, void *node)
345
346 #define cxTreeVisitorContinue(visitor)
347
348 void cxTreeVisitorDispose(CxTreeVisitor *visitor);
349 ``` 252 ```
350 253
351 There are two different kinds of iterators for trees: one for depth-first iteration and one for breadth-first iteration. 254 There are two different kinds of iterators for trees: one for depth-first iteration and one for breadth-first iteration.
352 255
353 The `CxTreeIterator` is performing a depth-first iteration with the capability of visiting a node twice: 256 An iterator created with the _iterate_ functions is performing a depth-first iteration with the capability of visiting a node twice:
354 first when the iterator enters the node coming from its parent, and secondly when the iterator tracks back from its last child. 257 first when the iterator enters the node coming from its parent, and secondly when the iterator tracks back from its last child.
355 This behavior is controlled via the `visit_on_exit` argument. 258 This behavior is controlled via the `visit_on_exit` argument.
356 When set to `true`, the iterators `exiting` flag can be checked during iteration to see whether the iterator is currently entering or leaving the node. 259 When set to `true`, the iterators `exiting` flag can be checked during iteration to see whether the iterator is currently entering or leaving the node.
357 The above [example](#example-for-wrapping-a-libxml2-tree) for iterating through an XML tree illustrates this. 260 The above [example](#example-for-wrapping-a-libxml2-tree) for iterating through an XML tree illustrates this.
358 261
359 On the other hand, the `CxTreeVisitor` performs a breadth-first iteration and visits every node only once. 262 On the other hand, an iterator created with the _visit_ functions performs a breadth-first iteration and visits every node only once.
360 263
361 Both iterators do not support the removal of nodes. 264 Both iterators do not support the removal of nodes.
362 265
363 Since tree iteration needs to keep track of a stack (depth-first) or queue (breadth-first), internal memory is allocated. 266 Since tree iteration needs to keep track of a stack (depth-first) or queue (breadth-first), internal memory is allocated.
364 This memory is _automatically_ disposed of when the iteration _completes_. 267 This memory is _automatically_ disposed of when the iteration _completes_.
365 If you break from the iteration early, you must call `cxTreeIteratorDispose()` or `cxTreeVisitorDispose()`, respectively, to deallocate the memory. 268 If you break from the iteration early, you must call `cxTreeIteratorDispose()` to deallocate the memory.
366 269
367 > It is recommended to always invoke the dispose functions, even when it seems not necessary. 270 > It is recommended to always invoke the dispose functions, even when it seems not necessary.
368 > 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. 271 > 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.
369 >{style="note"} 272 >{style="note"}
370 273
371 The macros `cxTreeIteratorContinue()` and `cxTreeVisitorContinue()` equivalently instruct the iterator/visitor to skip the subtree below the currently inspected node. 274 The macro `cxTreeIteratorContinue()` instruct the iterator to skip the subtree below the currently inspected node.
275
276 > In contrast to iterators over [lists](list.h.md#iterators) or [maps](map.h.md#iterators),
277 > a tree iterator is _always_ iterating over the nodes.
278 > That means, the pointer in a `cx_foreach` loop is always expected to be a pointer to a node and not a pointer to
279 > the element / payload within the node.
280 >
281 >{style="warning"}
372 282
373 ## Remove 283 ## Remove
374 284
375 ```C 285 ```C
376 #include <cx/tree.h> 286 #include <cx/tree.h>
377 287
378 void cx_tree_unlink(void *node, ptrdiff_t loc_parent, 288 typedef void (*cx_tree_relink_func)(
289 void *node, const void *old_parent, const void *new_parent);
290
291 void cx_tree_remove(void *node, ptrdiff_t loc_parent,
379 ptrdiff_t loc_children, ptrdiff_t loc_last_child, 292 ptrdiff_t loc_children, ptrdiff_t loc_last_child,
380 ptrdiff_t loc_prev, ptrdiff_t loc_next); 293 ptrdiff_t loc_prev, ptrdiff_t loc_next);
381 294
382 int cxTreeRemoveNode(CxTree *tree, void *node, 295 int cxTreeRemoveNode(CxTree *tree, void *node,
383 cx_tree_relink_func relink_func); 296 cx_tree_relink_func relink_func);
384 297
385 void cxTreeRemoveSubtree(CxTree *tree, void *node); 298 void cxTreeRemoveSubtree(CxTree *tree, void *node);
386 ``` 299 ```
387 300
388 The low-level function `cx_tree_unlink()` removes the specified `node`, 301 The low-level function `cx_tree_remove()` removes the specified `node`,
389 as well as the entire subtree beneath that node, from its parent. 302 as well as the entire subtree beneath that node, from its parent.
390 The high-level counterpart is `cxTreeRemoveSubtree()`. 303 The high-level counterpart is `cxTreeRemoveSubtree()`.
391 304
392 The function `cxTreeRemoveNode()`, on the other hand, _only_ removes the `node` from the tree, 305 The function `cxTreeRemoveNode()`, on the other hand, _only_ removes the `node` from the tree,
393 links all children of `node` to the former parent of `node`, 306 links all children of `node` to the former parent of `node`,
401 ## Dispose 314 ## Dispose
402 315
403 ```C 316 ```C
404 #include <cx/tree.h> 317 #include <cx/tree.h>
405 318
319 typedef void (*cx_tree_relink_func)(
320 void *node, const void *old_parent, const void *new_parent);
321
406 int cxTreeDestroyNode(CxTree *tree, void *node, 322 int cxTreeDestroyNode(CxTree *tree, void *node,
407 cx_tree_relink_func relink_func); 323 cx_tree_relink_func relink_func);
408 324
409 void cxTreeDestroySubtree(CxTree *tree, void *node); 325 void cxTreeDestroySubtree(CxTree *tree, void *node);
410 326
424 340
425 The function `cxTreeClear()` is a shorthand for invoking `cxTreeDestroySubtree()` on the root node of the tree. 341 The function `cxTreeClear()` is a shorthand for invoking `cxTreeDestroySubtree()` on the root node of the tree.
426 342
427 The function `cxTreeFree()` behaves like `cxTreeClear()` and then deallocates the memory for the `CxTree` structure. 343 The function `cxTreeFree()` behaves like `cxTreeClear()` and then deallocates the memory for the `CxTree` structure.
428 344
429 > Although `CxTree` supports the general concept of [destructor functions](collection.h.md#destructor-functions), 345 > In contrast to other collections, the destructor functions of a `CxTree` are _always_ invoked with pointers to the _nodes_
430 > it is not based on `CX_COLLECTION_BASE`. 346 > and not to pointers to the elements / the payload of the nodes.
431 > Therefore, the `cxSetDestructor()` and `cxSetAdvancedDestructor()` macros cannot be used on a `CxTree` and 347 >
432 > the fields must be set manually. 348 > Also, the nodes are _not_ deallocated by the tree and _MUST_ be deallocated by the destructor functions.
433 >{style="note"} 349 > When the tree was created by `cxTreeCreate()` without specifying an existing `root` node, `cxFree` is automatically used as the destructor function.
350 > {style="note"}
434 351
435 <seealso> 352 <seealso>
436 <category ref="apidoc"> 353 <category ref="apidoc">
437 <a href="https://ucx.sourceforge.io/api/tree_8h.html">tree.h</a> 354 <a href="https://ucx.sourceforge.io/api/tree_8h.html">tree.h</a>
438 </category> 355 </category>

Mercurial Repository: ucx

mercurial