Mercurial > hg > dav / file comparison

comparison: ucx/cx/tree.h

ucx/cx/tree.h

branch
dav-2
changeset 894
e86049631677
parent 891
4d58cbcc9efa
equal deleted inserted replaced
893:38800d479cd4 894:e86049631677
38 38
39 #include "common.h" 39 #include "common.h"
40 40
41 #include "collection.h" 41 #include "collection.h"
42 42
43 #ifdef __cplusplus 43 /**
44 extern "C" { 44 * An element in a visitor queue.
45 #endif 45 */
46 46 struct cx_tree_visitor_queue_s {
47 /** 47 /**
48 * A depth-first tree iterator. 48 * The tree node to visit.
49 * 49 */
50 * This iterator is not position-aware in a strict sense, as it does not assume 50 void *node;
51 * a particular order of elements in the tree. However, the iterator keeps track 51 /**
52 * of the number of nodes it has passed in a counter-variable. 52 * The depth of the node.
53 * Each node, regardless of the number of passes, is counted only once. 53 * The first visited node has depth 1.
54 * 54 */
55 * @note Objects that are pointed to by an iterator are mutable through that 55 size_t depth;
56 * iterator. However, if the 56 /**
57 * underlying data structure is mutated by other means than this iterator (e.g., 57 * The next element in the queue or @c NULL.
58 * elements added or removed), the iterator becomes invalid (regardless of what 58 */
59 * cxIteratorValid() returns). 59 struct cx_tree_visitor_queue_s *next;
60 * 60 };
61 * @see CxIterator 61
62 */ 62 /**
63 typedef struct cx_tree_iterator_s { 63 * An iterator (DFS) or visitor (BFS) for a tree.
64 */
65 typedef struct cx_tree_combined_iterator_s {
64 /** 66 /**
65 * Base members. 67 * Base members.
66 */ 68 */
67 CX_ITERATOR_BASE; 69 CX_ITERATOR_BASE;
68 /** 70 /**
69 * Indicates whether the subtree below the current node shall be skipped.
70 */
71 bool skip;
72 /**
73 * Set to true, when the iterator shall visit a node again
74 * when all its children have been processed.
75 */
76 bool visit_on_exit;
77 /**
78 * True, if this iterator is currently leaving the node.
79 */
80 bool exiting;
81 /**
82 * Offset in the node struct for the children linked list. 71 * Offset in the node struct for the children linked list.
83 */ 72 */
84 ptrdiff_t loc_children; 73 ptrdiff_t loc_children;
85 /** 74 /**
86 * Offset in the node struct for the next pointer. 75 * Offset in the node struct for the next pointer.
87 */ 76 */
88 ptrdiff_t loc_next; 77 ptrdiff_t loc_next;
89 /** 78 /**
90 * The total number of distinct nodes that have been passed so far. 79 * The total number of distinct nodes that have been passed so far.
91 * This includes the current node. 80 * This includes the currently visited node.
92 */ 81 */
93 size_t counter; 82 size_t counter;
83 /**
84 * The current depth in the tree.
85 */
86 size_t depth;
94 /** 87 /**
95 * The currently observed node. 88 * The currently observed node.
96 * 89 *
97 * This is the same what cxIteratorCurrent() would return. 90 * This is the same what cxIteratorCurrent() would return.
98 */ 91 */
99 void *node; 92 void *node;
100 /** 93 /**
101 * Stores a copy of the pointer to the successor of the visited node. 94 * Memory for BFS or DFS-specific data.
102 * Allows freeing a node on exit without corrupting the iteration. 95 */
103 */
104 void *node_next;
105 /**
106 * Internal stack.
107 * Will be automatically freed once the iterator becomes invalid.
108 *
109 * If you want to discard the iterator before, you need to manually
110 * call cxTreeIteratorDispose().
111 */
112 void **stack;
113 /**
114 * Internal capacity of the stack.
115 */
116 size_t stack_capacity;
117 union { 96 union {
118 /** 97 struct {
119 * Internal stack size. 98 /**
120 */ 99 * Stores a copy of the pointer to the successor of the visited node.
121 size_t stack_size; 100 * Allows freeing a node on exit without corrupting the iteration.
122 /** 101 */
123 * The current depth in the tree. 102 void *node_next;
124 * The node with which the iteration starts has depth 1. 103 /**
125 */ 104 * Internal stack.
126 size_t depth; 105 * Will be automatically freed once the iterator becomes invalid.
106 *
107 * If you want to discard the iterator before, you need to manually
108 * call cxTreeIteratorDispose().
109 */
110 void **stack;
111 /**
112 * Internal capacity of the stack.
113 */
114 size_t stack_capacity;
115 };
116 struct {
117 /**
118 * The next element in the visitor queue.
119 */
120 struct cx_tree_visitor_queue_s *queue_next;
121 /**
122 * The last element in the visitor queue.
123 */
124 struct cx_tree_visitor_queue_s *queue_last;
125 };
127 }; 126 };
127 /**
128 * Indicates whether the subtree below the current node shall be skipped.
129 */
130 bool skip;
131 /**
132 * Set to true, when the iterator shall visit a node again
133 * when all its children have been processed.
134 */
135 bool visit_on_exit;
136 /**
137 * True, if this iterator is currently leaving the node.
138 */
139 bool exiting;
140 /**
141 * Indicates whether the @c iterator (true) or the @c visitor (false) aspect is active.
142 */
143 bool use_dfs;
128 } CxTreeIterator; 144 } CxTreeIterator;
129
130 /**
131 * An element in a visitor queue.
132 */
133 struct cx_tree_visitor_queue_s {
134 /**
135 * The tree node to visit.
136 */
137 void *node;
138 /**
139 * The depth of the node.
140 * The first visited node has depth 1.
141 */
142 size_t depth;
143 /**
144 * The next element in the queue or @c NULL.
145 */
146 struct cx_tree_visitor_queue_s *next;
147 };
148
149 /**
150 * A breadth-first tree iterator.
151 *
152 * This iterator needs to maintain a visitor queue that will be automatically
153 * freed once the iterator becomes invalid.
154 * If you want to discard the iterator before, you MUST manually call
155 * cxTreeVisitorDispose().
156 *
157 * This iterator is not position-aware in a strict sense, as it does not assume
158 * a particular order of elements in the tree. However, the iterator keeps track
159 * of the number of nodes it has passed in a counter-variable.
160 * Each node, regardless of the number of passes, is counted only once.
161 *
162 * @note Objects that are pointed to by an iterator are mutable through that
163 * iterator. However, if the
164 * underlying data structure is mutated by other means than this iterator (e.g.,
165 * elements added or removed), the iterator becomes invalid (regardless of what
166 * cxIteratorValid() returns).
167 *
168 * @see CxIterator
169 */
170 typedef struct cx_tree_visitor_s {
171 /**
172 * Base members.
173 */
174 CX_ITERATOR_BASE;
175 /**
176 * Indicates whether the subtree below the current node shall be skipped.
177 */
178 bool skip;
179 /**
180 * Offset in the node struct for the children linked list.
181 */
182 ptrdiff_t loc_children;
183 /**
184 * Offset in the node struct for the next pointer.
185 */
186 ptrdiff_t loc_next;
187 /**
188 * The total number of distinct nodes that have been passed so far.
189 * This includes the currently visited node.
190 */
191 size_t counter;
192 /**
193 * The currently observed node.
194 *
195 * This is the same what cxIteratorCurrent() would return.
196 */
197 void *node;
198 /**
199 * The current depth in the tree.
200 */
201 size_t depth;
202 /**
203 * The next element in the visitor queue.
204 */
205 struct cx_tree_visitor_queue_s *queue_next;
206 /**
207 * The last element in the visitor queue.
208 */
209 struct cx_tree_visitor_queue_s *queue_last;
210 } CxTreeVisitor;
211 145
212 /** 146 /**
213 * Releases internal memory of the given tree iterator. 147 * Releases internal memory of the given tree iterator.
214 * @param iter the iterator 148 * @param iter the iterator
215 */ 149 */
216 cx_attr_nonnull 150 CX_EXTERN CX_NONNULL
217 CX_EXPORT void cxTreeIteratorDispose(CxTreeIterator *iter); 151 void cxTreeIteratorDispose(CxTreeIterator *iter);
218
219 /**
220 * Releases internal memory of the given tree visitor.
221 * @param visitor the visitor
222 */
223 cx_attr_nonnull
224 CX_EXPORT void cxTreeVisitorDispose(CxTreeVisitor *visitor);
225 152
226 /** 153 /**
227 * Advises the iterator to skip the subtree below the current node and 154 * Advises the iterator to skip the subtree below the current node and
228 * also continues the current loop. 155 * also continues the current loop.
229 * 156 *
230 * @param iterator (@c CxTreeIterator) the iterator 157 * @param iterator (@c CxTreeIterator) the iterator
231 */ 158 */
232 #define cxTreeIteratorContinue(iterator) (iterator).skip = true; continue 159 #define cxTreeIteratorContinue(iterator) (iterator).skip = true; continue
233
234 /**
235 * Advises the visitor to skip the subtree below the current node and
236 * also continues the current loop.
237 *
238 * @param visitor (@c CxTreeVisitor) the visitor
239 */
240 #define cxTreeVisitorContinue(visitor) cxTreeIteratorContinue(visitor)
241 160
242 /** 161 /**
243 * Links a node to a (new) parent. 162 * Links a node to a (new) parent.
244 * 163 *
245 * If the node already has a parent, it is unlinked, first. 164 * If the node already has a parent, it is unlinked, first.
252 * @param loc_children offset in the node struct for the children linked list 171 * @param loc_children offset in the node struct for the children linked list
253 * @param loc_last_child optional offset in the node struct for the pointer to 172 * @param loc_last_child optional offset in the node struct for the pointer to
254 * the last child in the linked list (negative if there is no such pointer) 173 * the last child in the linked list (negative if there is no such pointer)
255 * @param loc_prev optional offset in the node struct for the prev pointer 174 * @param loc_prev optional offset in the node struct for the prev pointer
256 * @param loc_next offset in the node struct for the next pointer 175 * @param loc_next offset in the node struct for the next pointer
257 * @see cx_tree_unlink() 176 * @see cx_tree_remove()
258 */ 177 */
259 cx_attr_nonnull 178 CX_EXTERN CX_NONNULL
260 CX_EXPORT void cx_tree_link(void *parent, void *node, 179 void cx_tree_add(void *parent, void *node,
261 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child, 180 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
262 ptrdiff_t loc_prev, ptrdiff_t loc_next); 181 ptrdiff_t loc_prev, ptrdiff_t loc_next);
263 182
264 /** 183 /**
265 * Unlinks a node from its parent. 184 * Unlinks a node from its parent.
271 * @param loc_children offset in the node struct for the children linked list 190 * @param loc_children offset in the node struct for the children linked list
272 * @param loc_last_child optional offset in the node struct for the pointer to 191 * @param loc_last_child optional offset in the node struct for the pointer to
273 * the last child in the linked list (negative if there is no such pointer) 192 * the last child in the linked list (negative if there is no such pointer)
274 * @param loc_prev optional offset in the node struct for the prev pointer 193 * @param loc_prev optional offset in the node struct for the prev pointer
275 * @param loc_next offset in the node struct for the next pointer 194 * @param loc_next offset in the node struct for the next pointer
276 * @see cx_tree_link() 195 * @see cx_tree_add()
277 */ 196 */
278 cx_attr_nonnull 197 CX_EXTERN CX_NONNULL
279 CX_EXPORT void cx_tree_unlink(void *node, 198 void cx_tree_remove(void *node,
280 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child, 199 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
281 ptrdiff_t loc_prev, ptrdiff_t loc_next); 200 ptrdiff_t loc_prev, ptrdiff_t loc_next);
282 201
283 /** 202 /**
284 * Macro that can be used instead of the magic value for infinite search depth. 203 * Macro that can be used instead of the magic value for infinite search depth.
309 * 228 *
310 * @return 0 if the node contains the data, 229 * @return 0 if the node contains the data,
311 * positive if one of the children might contain the data, 230 * positive if one of the children might contain the data,
312 * negative if neither the node nor the children contains the data 231 * negative if neither the node nor the children contains the data
313 */ 232 */
314 typedef int (*cx_tree_search_data_func)(const void *node, const void *data); 233 typedef int (*cx_tree_search_func)(const void *node, const void *data);
315
316
317 /**
318 * Function pointer for a search function.
319 *
320 * A function of this kind shall check if the specified @p node
321 * contains the same @p data as @p new_node or if one of the children might
322 * contain the data.
323 *
324 * The function should use the returned integer to indicate how close the
325 * match is, where a negative number means that it does not match at all.
326 * Zero means exact match and a positive number is an implementation defined
327 * measure for the distance to an exact match.
328 *
329 * For example, consider a tree that stores file path information.
330 * A node which is describing a parent directory of a searched file shall
331 * return a positive number to indicate that a child node might contain the
332 * searched item. On the other hand, if the node denotes a path that is not a
333 * prefix of the searched filename, the function would return -1 to indicate
334 * that the search does not need to be continued in that branch.
335 *
336 * @param node the node that is currently investigated
337 * @param new_node a new node with the information which is searched
338 *
339 * @return 0 if @p node contains the same data as @p new_node,
340 * positive if one of the children might contain the data,
341 * negative if neither the node nor the children contains the data
342 */
343 typedef int (*cx_tree_search_func)(const void *node, const void *new_node);
344 234
345 /** 235 /**
346 * Searches for data in a tree. 236 * Searches for data in a tree.
347 * 237 *
348 * When the data cannot be found exactly, the search function might return the 238 * When the data cannot be found exactly, the search function might return the
349 * closest result, which might be a good starting point for adding a new node 239 * closest result, which might be a good starting point for adding a new node
350 * to the tree (see also #cx_tree_add()). 240 * to the tree.
351 * 241 *
352 * Depending on the tree structure, it is not necessarily guaranteed that the 242 * Depending on the tree structure, it is not necessarily guaranteed that the
353 * "closest" match is uniquely defined. This function will search for a node 243 * "closest" match is uniquely defined. This function will search for a node
354 * with the best match according to the @p sfunc (meaning: the return value of 244 * with the best match according to the @p sfunc (meaning: the return value of
355 * @p sfunc which is closest to zero). If that is also ambiguous, an arbitrary 245 * @p sfunc which is closest to zero). If that is also ambiguous, an arbitrary
356 * node matching the criteria is returned. 246 * node matching the criteria is returned.
357 * 247 *
358 * @param root the root node 248 * @param root the root node
359 * @param depth the maximum depth (zero=indefinite, one=just root) 249 * @param max_depth the maximum depth (zero=indefinite, one=just root)
360 * @param data the data to search for 250 * @param data the data to search for
361 * @param sfunc the search function 251 * @param sfunc the search function
362 * @param result where the result shall be stored 252 * @param result where the result shall be stored
363 * @param loc_children offset in the node struct for the children linked list 253 * @param loc_children offset in the node struct for the children linked list
364 * @param loc_next offset in the node struct for the next pointer 254 * @param loc_next offset in the node struct for the next pointer
365 * @return zero if the node was found exactly, positive if a node was found that 255 * @return zero if the node was found exactly, positive if a node was found that
366 * could contain the node (but doesn't right now), negative if the tree does not 256 * could contain the node (but doesn't right now), negative if the tree does not
367 * contain any node that might be related to the searched data 257 * contain any node that might be related to the searched data
368 */ 258 */
369 cx_attr_nonnull cx_attr_access_w(5) 259 CX_EXTERN CX_NONNULL_ARG(4, 5) CX_ACCESS_W(5)
370 CX_EXPORT int cx_tree_search_data(const void *root, size_t depth, 260 int cx_tree_search(const void *root, size_t max_depth,
371 const void *data, cx_tree_search_data_func sfunc, 261 const void *data, cx_tree_search_func sfunc, void **result,
372 void **result, ptrdiff_t loc_children, ptrdiff_t loc_next); 262 ptrdiff_t loc_children, ptrdiff_t loc_next);
373
374 /**
375 * Searches for a node in a tree.
376 *
377 * When no node with the same data can be found, the search function might
378 * return the closest result, which might be a good starting point for adding the
379 * new node to the tree (see also #cx_tree_add()).
380 *
381 * Depending on the tree structure, it is not necessarily guaranteed that the
382 * "closest" match is uniquely defined. This function will search for a node
383 * with the best match according to the @p sfunc (meaning: the return value of
384 * @p sfunc which is closest to zero). If that is also ambiguous, an arbitrary
385 * node matching the criteria is returned.
386 *
387 * @param root the root node
388 * @param depth the maximum depth (zero=indefinite, one=just root)
389 * @param node the node to search for
390 * @param sfunc the search function
391 * @param result where the result shall be stored
392 * @param loc_children offset in the node struct for the children linked list
393 * @param loc_next offset in the node struct for the next pointer
394 * @return zero if the node was found exactly, positive if a node was found that
395 * could contain the node (but doesn't right now), negative if the tree does not
396 * contain any node that might be related to the searched data
397 */
398 cx_attr_nonnull cx_attr_access_w(5)
399 CX_EXPORT int cx_tree_search(const void *root, size_t depth,
400 const void *node, cx_tree_search_func sfunc,
401 void **result, ptrdiff_t loc_children, ptrdiff_t loc_next);
402 263
403 /** 264 /**
404 * Creates a depth-first iterator for a tree with the specified root node. 265 * Creates a depth-first iterator for a tree with the specified root node.
405 * 266 *
406 * @note A tree iterator needs to maintain a stack of visited nodes, which is 267 * @note A tree iterator needs to maintain a stack of visited nodes, which is
418 * @param loc_children offset in the node struct for the children linked list 279 * @param loc_children offset in the node struct for the children linked list
419 * @param loc_next offset in the node struct for the next pointer 280 * @param loc_next offset in the node struct for the next pointer
420 * @return the new tree iterator 281 * @return the new tree iterator
421 * @see cxTreeIteratorDispose() 282 * @see cxTreeIteratorDispose()
422 */ 283 */
423 cx_attr_nodiscard 284 CX_EXTERN CX_NODISCARD
424 CX_EXPORT CxTreeIterator cx_tree_iterator(void *root, bool visit_on_exit, 285 CxTreeIterator cx_tree_iterator(void *root, bool visit_on_exit,
425 ptrdiff_t loc_children, ptrdiff_t loc_next); 286 ptrdiff_t loc_children, ptrdiff_t loc_next);
426 287
427 /** 288 /**
428 * Creates a breadth-first iterator for a tree with the specified root node. 289 * Creates a breadth-first iterator for a tree with the specified root node.
429 * 290 *
430 * @note A tree visitor needs to maintain a queue of to-be visited nodes, which 291 * @note A tree visitor needs to maintain a queue of to-be visited nodes, which
431 * is allocated using the cxDefaultAllocator. 292 * is allocated using the cxDefaultAllocator.
432 * When the visitor becomes invalid, this memory is automatically released. 293 * When the visitor becomes invalid, this memory is automatically released.
433 * However, if you wish to cancel the iteration before the visitor becomes 294 * However, if you wish to cancel the iteration before the visitor becomes
434 * invalid by itself, you MUST call cxTreeVisitorDispose() manually to release 295 * invalid by itself, you MUST call cxTreeIteratorDispose() manually to release
435 * the memory. 296 * the memory.
436 * 297 *
437 * @remark The returned iterator does not support cxIteratorFlagRemoval(). 298 * @remark The returned iterator does not support cxIteratorFlagRemoval().
438 * 299 *
439 * @param root the root node 300 * @param root the root node
440 * @param loc_children offset in the node struct for the children linked list 301 * @param loc_children offset in the node struct for the children linked list
441 * @param loc_next offset in the node struct for the next pointer 302 * @param loc_next offset in the node struct for the next pointer
442 * @return the new tree visitor 303 * @return the new tree visitor
443 * @see cxTreeVisitorDispose() 304 * @see cxTreeIteratorDispose()
444 */ 305 */
445 cx_attr_nodiscard 306 CX_EXTERN CX_NODISCARD
446 CX_EXPORT CxTreeVisitor cx_tree_visitor(void *root, 307 CxTreeIterator cx_tree_visitor(void *root,
447 ptrdiff_t loc_children, ptrdiff_t loc_next); 308 ptrdiff_t loc_children, ptrdiff_t loc_next);
448
449 /**
450 * Describes a function that creates a tree node from the specified data.
451 * The first argument points to the data the node shall contain, and
452 * the second argument may be used for additional data (e.g., an allocator).
453 * Functions of this type shall either return a new pointer to a newly
454 * created node or @c NULL when allocation fails.
455 *
456 * @note the function may leave the node pointers in the struct uninitialized.
457 * The caller is responsible to set them according to the intended use case.
458 */
459 typedef void *(*cx_tree_node_create_func)(const void *, void *);
460
461 /**
462 * The local search depth for a new subtree when adding multiple elements.
463 * The default value is 3.
464 * This variable is used by #cx_tree_add_array() and #cx_tree_add_iter() to
465 * implement optimized insertion of multiple elements into a tree.
466 */
467 CX_EXPORT extern unsigned int cx_tree_add_look_around_depth;
468
469 /**
470 * Adds multiple elements efficiently to a tree.
471 *
472 * Once an element cannot be added to the tree, this function returns, leaving
473 * the iterator in a valid state pointing to the element that could not be
474 * added.
475 * Also, the pointer of the created node will be stored to @p failed.
476 * The integer returned by this function denotes the number of elements obtained
477 * from the @p iter that have been successfully processed.
478 * When all elements could be processed, a @c NULL pointer will be written to
479 * @p failed.
480 *
481 * The advantage of this function compared to multiple invocations of
482 * #cx_tree_add() is that the search for the insert locations is not always
483 * started from the root node.
484 * Instead, the function checks #cx_tree_add_look_around_depth many parent nodes
485 * of the current insert location before starting from the root node again.
486 * When the variable is set to zero, only the last found location is checked
487 * again.
488 *
489 * Refer to the documentation of #cx_tree_add() for more details.
490 *
491 * @param iter a pointer to an arbitrary iterator
492 * @param num the maximum number of elements to obtain from the iterator
493 * @param sfunc a search function
494 * @param cfunc a node creation function
495 * @param cdata optional additional data
496 * @param root the root node of the tree
497 * @param failed location where the pointer to a failed node shall be stored
498 * @param loc_parent offset in the node struct for the parent pointer
499 * @param loc_children offset in the node struct for the children linked list
500 * @param loc_last_child optional offset in the node struct for the pointer to
501 * the last child in the linked list (negative if there is no such pointer)
502 * @param loc_prev optional offset in the node struct for the prev pointer
503 * @param loc_next offset in the node struct for the next pointer
504 * @return the number of nodes created and added
505 * @see cx_tree_add()
506 */
507 cx_attr_nonnull_arg(1, 3, 4, 6, 7) cx_attr_access_w(6)
508 CX_EXPORT size_t cx_tree_add_iter(struct cx_iterator_base_s *iter, size_t num,
509 cx_tree_search_func sfunc, cx_tree_node_create_func cfunc,
510 void *cdata, void **failed, void *root,
511 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
512 ptrdiff_t loc_prev, ptrdiff_t loc_next);
513
514 /**
515 * Adds multiple elements efficiently to a tree.
516 *
517 * Once an element cannot be added to the tree, this function returns, storing
518 * the pointer of the created node to @p failed.
519 * The integer returned by this function denotes the number of elements from
520 * the @p src array that have been successfully processed.
521 * When all elements could be processed, a @c NULL pointer will be written to
522 * @p failed.
523 *
524 * The advantage of this function compared to multiple invocations of
525 * #cx_tree_add() is that the search for the insert locations is not always
526 * started from the root node.
527 * Instead, the function checks #cx_tree_add_look_around_depth many parent nodes
528 * of the current insert location before starting from the root node again.
529 * When the variable is set to zero, only the last found location is checked
530 * again.
531 *
532 * Refer to the documentation of #cx_tree_add() for more details.
533 *
534 * @param src a pointer to the source data array
535 * @param num the number of elements in the @p src array
536 * @param elem_size the size of each element in the @p src array
537 * @param sfunc a search function
538 * @param cfunc a node creation function
539 * @param cdata optional additional data
540 * @param failed location where the pointer to a failed node shall be stored
541 * @param root the root node of the tree
542 * @param loc_parent offset in the node struct for the parent pointer
543 * @param loc_children offset in the node struct for the children linked list
544 * @param loc_last_child optional offset in the node struct for the pointer to
545 * the last child in the linked list (negative if there is no such pointer)
546 * @param loc_prev optional offset in the node struct for the prev pointer
547 * @param loc_next offset in the node struct for the next pointer
548 * @return the number of array elements successfully processed
549 * @see cx_tree_add()
550 */
551 cx_attr_nonnull_arg(1, 4, 5, 7, 8) cx_attr_access_w(7)
552 CX_EXPORT size_t cx_tree_add_array(const void *src, size_t num, size_t elem_size,
553 cx_tree_search_func sfunc, cx_tree_node_create_func cfunc,
554 void *cdata, void **failed, void *root,
555 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
556 ptrdiff_t loc_prev, ptrdiff_t loc_next);
557
558 /**
559 * Adds data to a tree.
560 *
561 * An adequate location where to add the new tree node is searched with the
562 * specified @p sfunc.
563 *
564 * When a location is found, the @p cfunc will be invoked with @p cdata.
565 *
566 * The node returned by @p cfunc will be linked into the tree.
567 * When @p sfunc returns a positive integer, the new node will be linked as a
568 * child. The other children (now siblings of the new node) are then checked
569 * with @p sfunc, whether they could be children of the new node and re-linked
570 * accordingly.
571 *
572 * When @p sfunc returns zero and the found node has a parent, the new
573 * node will be added as a sibling - otherwise, the new node will be added
574 * as a child.
575 *
576 * When @p sfunc returns a negative value, the new node will not be added to
577 * the tree, and this function returns a non-zero value.
578 * The caller should check if @p cnode contains a node pointer and deal with the
579 * node that could not be added.
580 *
581 * This function also returns a non-zero value when @p cfunc tries to allocate
582 * a new node but fails to do so. In that case, the pointer stored to @p cnode
583 * will be @c NULL.
584 *
585 * Multiple elements can be added more efficiently with
586 * #cx_tree_add_array() or #cx_tree_add_iter().
587 *
588 * @param src a pointer to the data
589 * @param sfunc a search function
590 * @param cfunc a node creation function
591 * @param cdata optional additional data
592 * @param cnode the location where a pointer to the new node is stored
593 * @param root the root node of the tree
594 * @param loc_parent offset in the node struct for the parent pointer
595 * @param loc_children offset in the node struct for the children linked list
596 * @param loc_last_child optional offset in the node struct for the pointer to
597 * the last child in the linked list (negative if there is no such pointer)
598 * @param loc_prev optional offset in the node struct for the prev pointer
599 * @param loc_next offset in the node struct for the next pointer
600 * @return zero when a new node was created and added to the tree,
601 * non-zero otherwise
602 */
603 cx_attr_nonnull_arg(1, 2, 3, 5, 6) cx_attr_access_w(5)
604 CX_EXPORT int cx_tree_add(const void *src,
605 cx_tree_search_func sfunc, cx_tree_node_create_func cfunc,
606 void *cdata, void **cnode, void *root,
607 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
608 ptrdiff_t loc_prev, ptrdiff_t loc_next);
609
610
611 /**
612 * Tree class type.
613 */
614 typedef struct cx_tree_class_s cx_tree_class;
615 309
616 /** 310 /**
617 * Base structure that can be used for tree nodes in a #CxTree. 311 * Base structure that can be used for tree nodes in a #CxTree.
618 */ 312 */
619 struct cx_tree_node_base_s { 313 struct cx_tree_node_base_s {
640 }; 334 };
641 335
642 /** 336 /**
643 * Structure for holding the base data of a tree. 337 * Structure for holding the base data of a tree.
644 */ 338 */
645 struct cx_tree_s { 339 typedef struct cx_tree_s {
340 /** Base attributes. */
646 CX_COLLECTION_BASE; 341 CX_COLLECTION_BASE;
647 /**
648 * The tree class definition.
649 */
650 const cx_tree_class *cl;
651
652 /** 342 /**
653 * A pointer to the root node. 343 * A pointer to the root node.
654 * 344 *
655 * Will be @c NULL when @c size is 0. 345 * Will be @c NULL when @c size is 0.
656 */ 346 */
657 void *root; 347 void *root;
658 348
659 /** 349 /**
660 * A function to create new nodes. 350 * The size of the node structure.
661 * 351 */
662 * Invocations to this function will receive a pointer to this tree 352 size_t node_size;
663 * structure as the second argument.
664 *
665 * Nodes MAY use #cx_tree_node_base_s as the base layout, but do not need to.
666 */
667 cx_tree_node_create_func node_create;
668
669 /**
670 * A function to compare two nodes.
671 */
672 cx_tree_search_func search;
673
674 /**
675 * A function to compare a node with data.
676 */
677 cx_tree_search_data_func search_data;
678 353
679 /** 354 /**
680 * Offset in the node struct for the parent pointer. 355 * Offset in the node struct for the parent pointer.
681 */ 356 */
682 ptrdiff_t loc_parent; 357 ptrdiff_t loc_parent;
699 374
700 /** 375 /**
701 * Offset in the node struct for the next sibling pointer. 376 * Offset in the node struct for the next sibling pointer.
702 */ 377 */
703 ptrdiff_t loc_next; 378 ptrdiff_t loc_next;
704 }; 379
380 /**
381 * Offset in the node struct where the payload is located.
382 */
383 ptrdiff_t loc_data;
384 } CxTree;
705 385
706 /** 386 /**
707 * Macro to roll out the #cx_tree_node_base_s structure with a custom 387 * Macro to roll out the #cx_tree_node_base_s structure with a custom
708 * node type. 388 * node type.
709 * 389 *
710 * Must be used as the first member in your custom tree struct. 390 * Must be used as the first member in your custom tree struct.
711 * 391 *
712 * @param type the data type for the nodes 392 * @param type the data type for the nodes
713 */ 393 */
714 #define CX_TREE_NODE_BASE(type) \ 394 #define CX_TREE_NODE(type) \
715 type *parent; \ 395 type *parent; \
716 type *children;\ 396 type *children;\
717 type *last_child;\ 397 type *last_child;\
718 type *prev;\ 398 type *prev;\
719 type *next 399 type *next
720 400
721 /** 401 /**
722 * Macro for specifying the layout of a base node tree. 402 * Macro for specifying the layout of a tree node.
723 * 403 *
724 * When your tree uses #CX_TREE_NODE_BASE, you can use this 404 * When your tree uses #CX_TREE_NODE, you can use this
725 * macro in all tree functions that expect the layout parameters 405 * macro in all tree functions that expect the layout parameters
726 * @c loc_parent, @c loc_children, @c loc_last_child, @c loc_prev, 406 * @c loc_parent, @c loc_children, @c loc_last_child, @c loc_prev,
727 * and @c loc_next. 407 * and @c loc_next.
728 */ 408 * @param struct_name the name of the node structure
729 #define cx_tree_node_base_layout \ 409 */
730 offsetof(struct cx_tree_node_base_s, parent),\ 410 #define cx_tree_node_layout(struct_name) \
731 offsetof(struct cx_tree_node_base_s, children),\ 411 offsetof(struct_name, parent),\
732 offsetof(struct cx_tree_node_base_s, last_child),\ 412 offsetof(struct_name, children),\
733 offsetof(struct cx_tree_node_base_s, prev), \ 413 offsetof(struct_name, last_child),\
734 offsetof(struct cx_tree_node_base_s, next) 414 offsetof(struct_name, prev), \
735 415 offsetof(struct_name, next)
736 /**
737 * The class definition for arbitrary trees.
738 */
739 struct cx_tree_class_s {
740 /**
741 * Member function for inserting a single element.
742 *
743 * Implementations SHALL NOT simply invoke @p insert_many as this comes
744 * with too much overhead.
745 */
746 int (*insert_element)(struct cx_tree_s *tree, const void *data);
747
748 /**
749 * Member function for inserting multiple elements.
750 *
751 * Implementations SHALL avoid performing a full search in the tree for
752 * every element even though the source data MAY be unsorted.
753 */
754 size_t (*insert_many)(struct cx_tree_s *tree, struct cx_iterator_base_s *iter, size_t n);
755
756 /**
757 * Member function for finding a node.
758 */
759 void *(*find)(struct cx_tree_s *tree, const void *subtree, const void *data, size_t depth);
760 };
761
762 /**
763 * Common type for all tree implementations.
764 */
765 typedef struct cx_tree_s CxTree;
766
767 416
768 /** 417 /**
769 * Destroys a node and its subtree. 418 * Destroys a node and its subtree.
770 * 419 *
771 * It is guaranteed that the simple destructor is invoked before 420 * It is guaranteed that the simple destructor is invoked before
781 * @attention This function will not free the memory of the nodes with the 430 * @attention This function will not free the memory of the nodes with the
782 * tree's allocator, because that is usually done by the advanced destructor 431 * tree's allocator, because that is usually done by the advanced destructor
783 * and would therefore result in a double-free. 432 * and would therefore result in a double-free.
784 * 433 *
785 * @param tree the tree 434 * @param tree the tree
786 * @param node the node to remove 435 * @param node the node being the root of the subtree to remove
787 * @see cxTreeFree() 436 * @see cxTreeFree()
788 */ 437 */
789 cx_attr_nonnull 438 CX_EXTERN CX_NONNULL
790 CX_EXPORT void cxTreeDestroySubtree(CxTree *tree, void *node); 439 void cxTreeDestroySubtree(CxTree *tree, void *node);
791 440
792 441
793 /** 442 /**
794 * Destroys the tree contents. 443 * Destroys the tree contents.
795 * 444 *
805 * otherwise you will be leaking memory. 454 * otherwise you will be leaking memory.
806 * 455 *
807 * @param tree the tree 456 * @param tree the tree
808 * @see cxTreeDestroySubtree() 457 * @see cxTreeDestroySubtree()
809 */ 458 */
810 #define cxTreeClear(tree) cxTreeDestroySubtree(tree, tree->root) 459 CX_INLINE
460 void cxTreeClear(CxTree *tree) {
461 if (tree->root != NULL) {
462 cxTreeDestroySubtree(tree, tree->root);
463 }
464 }
811 465
812 /** 466 /**
813 * Deallocates the tree structure. 467 * Deallocates the tree structure.
814 * 468 *
815 * The destructor functions are invoked for each node, starting with the leaf 469 * The destructor functions are invoked for each node, starting with the leaf
823 * that would cause a double-free in most scenarios where the advanced 477 * that would cause a double-free in most scenarios where the advanced
824 * destructor is already freeing the memory. 478 * destructor is already freeing the memory.
825 * 479 *
826 * @param tree the tree to free 480 * @param tree the tree to free
827 */ 481 */
828 CX_EXPORT void cxTreeFree(CxTree *tree); 482 CX_EXTERN
829 483 void cxTreeFree(CxTree *tree);
830 /** 484
831 * Creates a new tree structure based on the specified layout. 485 /**
486 * Creates a new tree.
832 * 487 *
833 * The specified @p allocator will be used for creating the tree struct 488 * The specified @p allocator will be used for creating the tree struct
834 * and SHALL be used by @p create_func to allocate memory for the nodes. 489 * @em and the nodes.
835 * 490 *
836 * @note This function will also register an advanced destructor which 491 * When you do not specify an existing @p root, the tree will be created
837 * will free the nodes with the allocator's free() method. 492 * empty. Additionally, cxFree() is registered as the advanced destructor for
838 * 493 * the tree so that all nodes that you will add to the tree are automatically
839 * @param allocator the allocator that shall be used 494 * freed together with the tree.
840 * (if @c NULL, the cxDefaultAllocator will be used) 495 * When @p root is not @c NULL, no destructors are registered automatically.
841 * @param create_func a function that creates new nodes 496 *
842 * @param search_func a function that compares two nodes 497 * @param allocator the allocator to use
843 * @param search_data_func a function that compares a node with data
844 * @param loc_parent offset in the node struct for the parent pointer
845 * @param loc_children offset in the node struct for the children linked list
846 * @param loc_last_child optional offset in the node struct for the pointer to
847 * the last child in the linked list (negative if there is no such pointer)
848 * @param loc_prev optional offset in the node struct for the prev pointer
849 * @param loc_next offset in the node struct for the next pointer
850 * @return the new tree
851 * @see cxTreeCreateSimple()
852 * @see cxTreeCreateWrapped()
853 */
854 cx_attr_nonnull_arg(2, 3, 4) cx_attr_nodiscard cx_attr_malloc cx_attr_dealloc(cxTreeFree, 1)
855 CX_EXPORT CxTree *cxTreeCreate(const CxAllocator *allocator, cx_tree_node_create_func create_func,
856 cx_tree_search_func search_func, cx_tree_search_data_func search_data_func,
857 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
858 ptrdiff_t loc_prev, ptrdiff_t loc_next);
859
860 /**
861 * Creates a new tree structure based on a default layout.
862 *
863 * Nodes created by @p create_func MUST contain #cx_tree_node_base_s as the first
864 * member (or at least respect the default offsets specified in the tree
865 * struct), and they MUST be allocated with the specified allocator.
866 *
867 * @note This function will also register an advanced destructor which
868 * will free the nodes with the allocator's free() method.
869 *
870 * @param allocator (@c CxAllocator*) the allocator that shall be used
871 * @param create_func (@c cx_tree_node_create_func) a function that creates new nodes
872 * @param search_func (@c cx_tree_search_func) a function that compares two nodes
873 * @param search_data_func (@c cx_tree_search_data_func) a function that compares a node with data
874 * @return (@c CxTree*) the new tree
875 * @see cxTreeCreate()
876 */
877 #define cxTreeCreateSimple(allocator, create_func, search_func, search_data_func) \
878 cxTreeCreate(allocator, create_func, search_func, search_data_func, cx_tree_node_base_layout)
879
880 /**
881 * Creates a new tree structure based on an existing tree.
882 *
883 * The specified @p allocator will be used for creating the tree struct.
884 *
885 * @attention This function will create an incompletely defined tree structure
886 * where neither the create function, the search function, nor a destructor
887 * will be set. If you wish to use any of this functionality for the wrapped
888 * tree, you need to specify those functions afterward.
889 *
890 * @param allocator the allocator that was used for nodes of the wrapped tree
891 * (if @c NULL, the cxDefaultAllocator is assumed) 498 * (if @c NULL, the cxDefaultAllocator is assumed)
892 * @param root the root node of the tree that shall be wrapped 499 * @param node_size the complete size of one node
500 * @param elem_size the size of the payload stored in the node
501 * (@c CX_STORE_POINTERS is also supported)
502 * @param root an optional already existing root node
503 * @param loc_data optional offset in the node struct for the payload
504 * (when negative, cxTreeAddData() is not supported)
893 * @param loc_parent offset in the node struct for the parent pointer 505 * @param loc_parent offset in the node struct for the parent pointer
894 * @param loc_children offset in the node struct for the children linked list 506 * @param loc_children offset in the node struct for the children linked list
895 * @param loc_last_child optional offset in the node struct for the pointer to 507 * @param loc_last_child optional offset in the node struct for the pointer to
896 * the last child in the linked list (negative if there is no such pointer) 508 * the last child in the linked list (negative if there is no such pointer)
897 * @param loc_prev optional offset in the node struct for the prev pointer 509 * @param loc_prev optional offset in the node struct for the prev pointer
898 * @param loc_next offset in the node struct for the next pointer 510 * @param loc_next offset in the node struct for the next pointer
899 * @return the new tree 511 * @return the new tree
900 * @see cxTreeCreate() 512 * @see cxTreeCreate()
901 */ 513 */
902 cx_attr_nonnull_arg(2) cx_attr_nodiscard cx_attr_malloc cx_attr_dealloc(cxTreeFree, 1) 514 CX_EXTERN CX_NODISCARD CX_MALLOC CX_DEALLOC(cxTreeFree, 1)
903 CX_EXPORT CxTree *cxTreeCreateWrapped(const CxAllocator *allocator, void *root, 515 CxTree *cxTreeCreate(const CxAllocator *allocator,
516 size_t node_size, size_t elem_size, void *root, ptrdiff_t loc_data,
904 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child, 517 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
905 ptrdiff_t loc_prev, ptrdiff_t loc_next); 518 ptrdiff_t loc_prev, ptrdiff_t loc_next);
906 519
907 /** 520 /**
908 * Inserts data into the tree.
909 *
910 * @remark For this function to work, the tree needs specified search and
911 * create functions, which might not be available for wrapped trees
912 * (see #cxTreeCreateWrapped()).
913 *
914 * @param tree the tree
915 * @param data the data to insert
916 * @retval zero success
917 * @retval non-zero failure
918 */
919 cx_attr_nonnull
920 CX_EXPORT int cxTreeInsert(CxTree *tree, const void *data);
921
922 /**
923 * Inserts elements provided by an iterator efficiently into the tree.
924 *
925 * @remark For this function to work, the tree needs specified search and
926 * create functions, which might not be available for wrapped trees
927 * (see #cxTreeCreateWrapped()).
928 *
929 * @param tree the tree
930 * @param iter the iterator providing the elements
931 * @param n the maximum number of elements to insert
932 * @return the number of elements that could be successfully inserted
933 */
934 cx_attr_nonnull
935 CX_EXPORT size_t cxTreeInsertIter(CxTree *tree, CxIteratorBase *iter, size_t n);
936
937 /**
938 * Inserts an array of data efficiently into the tree.
939 *
940 * @remark For this function to work, the tree needs specified search and
941 * create functions, which might not be available for wrapped trees
942 * (see #cxTreeCreateWrapped()).
943 *
944 * @param tree the tree
945 * @param data the array of data to insert
946 * @param elem_size the size of each element in the array
947 * @param n the number of elements in the array
948 * @return the number of elements that could be successfully inserted
949 */
950 cx_attr_nonnull
951 CX_EXPORT size_t cxTreeInsertArray(CxTree *tree, const void *data, size_t elem_size, size_t n);
952
953 /**
954 * Searches the data in the specified tree.
955 *
956 * @remark For this function to work, the tree needs a specified @c search_data
957 * function, which might not be available wrapped trees
958 * (see #cxTreeCreateWrapped()).
959 *
960 * @param tree the tree
961 * @param data the data to search for
962 * @return the first matching node, or @c NULL when the data cannot be found
963 */
964 cx_attr_nonnull cx_attr_nodiscard
965 CX_EXPORT void *cxTreeFind(CxTree *tree, const void *data);
966
967 /**
968 * Searches the data in the specified subtree. 521 * Searches the data in the specified subtree.
969 * 522 *
970 * When @p max_depth is zero, the depth is not limited. 523 * When @p max_depth is zero, the depth is not limited.
971 * The @p subtree_root itself is on depth 1 and its children have depth 2. 524 * The @p subtree_root itself is on depth 1 and its children have depth 2.
972 * 525 *
973 * @note When @p subtree_root is not part of the @p tree, the behavior is 526 * @note When @p subtree_root is not @c NULL and not part of the @p tree,
974 * undefined. 527 * the behavior is undefined.
975 * 528 *
976 * @remark For this function to work, the tree needs a specified @c search_data 529 * @attention When @p loc_data is not available, this function immediately returns
977 * function, which might not be the case for wrapped trees 530 * @c NULL.
978 * (see #cxTreeCreateWrapped()).
979 * 531 *
980 * @param tree the tree 532 * @param tree the tree
981 * @param data the data to search for 533 * @param data the data to search for
982 * @param subtree_root the node where to start 534 * @param subtree_root the node where to start (@c NULL to start from root)
535 * @param max_depth the maximum search depth
536 * @param use_dfs @c true when depth-first search should be used;
537 * @c false when breadth-first search should be used
538 * @return the first matching node, or @c NULL when the data cannot be found
539 * @see cxTreeFind()
540 */
541 CX_EXTERN CX_NONNULL_ARG(1, 2) CX_NODISCARD
542 void *cxTreeFindInSubtree(CxTree *tree, const void *data, void *subtree_root,
543 size_t max_depth, bool use_dfs);
544
545 /**
546 * Searches the data in the specified tree.
547 *
548 * @attention When @p loc_data is not available, this function immediately returns
549 * @c NULL.
550 *
551 * @param tree the tree
552 * @param data the data to search for
553 * @param use_dfs @c true when depth-first search should be used;
554 * @c false when breadth-first search should be used
555 * @return the first matching node, or @c NULL when the data cannot be found
556 * @see cxTreeFindInSubtree()
557 * @see cxTreeFindFast()
558 */
559 CX_INLINE CX_NONNULL CX_NODISCARD
560 void *cxTreeFind(CxTree *tree, const void *data, bool use_dfs) {
561 if (tree->root == NULL) return NULL;
562 return cxTreeFindInSubtree(tree, data, tree->root, 0, use_dfs);
563 }
564
565 /**
566 * Performs an efficient depth-first search in a branch of the specified tree.
567 *
568 * When @p max_depth is zero, the depth is not limited.
569 * The @p subtree_root itself is on depth 1 and its children have depth 2.
570 *
571 * @note When @p subtree_root is not @c NULL and not part of the @p tree,
572 * the behavior is undefined.
573 *
574 * @param tree the tree
575 * @param data the data to search for
576 * @param sfunc the search function
577 * @param subtree_root the node where to start (@c NULL to start from root)
983 * @param max_depth the maximum search depth 578 * @param max_depth the maximum search depth
984 * @return the first matching node, or @c NULL when the data cannot be found 579 * @return the first matching node, or @c NULL when the data cannot be found
985 */ 580 * @see cxTreeFindInSubtree()
986 cx_attr_nonnull cx_attr_nodiscard 581 */
987 CX_EXPORT void *cxTreeFindInSubtree(CxTree *tree, const void *data, void *subtree_root, size_t max_depth); 582 CX_EXTERN CX_NONNULL CX_NODISCARD
583 void *cxTreeFindFastInSubtree(CxTree *tree, const void *data,
584 cx_tree_search_func sfunc, void *subtree_root, size_t max_depth);
585
586 /**
587 * Performs an efficient depth-first search in the tree.
588 *
589 * @param tree the tree
590 * @param data the data to search for
591 * @param sfunc the search function
592 * @return the first matching node, or @c NULL when the data cannot be found
593 * @see cxTreeFind()
594 */
595 CX_INLINE CX_NONNULL CX_NODISCARD
596 void *cxTreeFindFast(CxTree *tree, const void *data, cx_tree_search_func sfunc) {
597 return cxTreeFindFastInSubtree(tree, data, sfunc, tree->root, 0);
598 }
988 599
989 /** 600 /**
990 * Determines the size of the specified subtree. 601 * Determines the size of the specified subtree.
991 * 602 *
992 * @param tree the tree 603 * @param tree the tree
993 * @param subtree_root the root node of the subtree 604 * @param subtree_root the root node of the subtree
994 * @return the number of nodes in the specified subtree 605 * @return the number of nodes in the specified subtree
995 */ 606 */
996 cx_attr_nonnull cx_attr_nodiscard 607 CX_EXTERN CX_NONNULL CX_NODISCARD
997 CX_EXPORT size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root); 608 size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root);
998 609
999 /** 610 /**
1000 * Determines the depth of the specified subtree. 611 * Determines the depth of the specified subtree.
1001 * 612 *
1002 * @param tree the tree 613 * @param tree the tree
1003 * @param subtree_root the root node of the subtree 614 * @param subtree_root the root node of the subtree
1004 * @return the tree depth including the @p subtree_root 615 * @return the tree depth including the @p subtree_root
1005 */ 616 */
1006 cx_attr_nonnull cx_attr_nodiscard 617 CX_EXTERN CX_NONNULL CX_NODISCARD
1007 CX_EXPORT size_t cxTreeSubtreeDepth(CxTree *tree, void *subtree_root); 618 size_t cxTreeSubtreeDepth(CxTree *tree, void *subtree_root);
1008 619
1009 /** 620 /**
1010 * Determines the size of the entire tree. 621 * Determines the size of the entire tree.
1011 * 622 *
1012 * @param tree the tree 623 * @param tree the tree
1013 * @return the tree size, counting the root as one 624 * @return the tree size, counting the root as one
1014 */ 625 */
1015 cx_attr_nonnull cx_attr_nodiscard 626 CX_EXTERN CX_NONNULL CX_NODISCARD
1016 CX_EXPORT size_t cxTreeSize(CxTree *tree); 627 size_t cxTreeSize(CxTree *tree);
1017 628
1018 /** 629 /**
1019 * Determines the depth of the entire tree. 630 * Determines the depth of the entire tree.
1020 * 631 *
1021 * @param tree the tree 632 * @param tree the tree
1022 * @return the tree depth, counting the root as one 633 * @return the tree depth, counting the root as one
1023 */ 634 */
1024 cx_attr_nonnull cx_attr_nodiscard 635 CX_EXTERN CX_NONNULL CX_NODISCARD
1025 CX_EXPORT size_t cxTreeDepth(CxTree *tree); 636 size_t cxTreeDepth(CxTree *tree);
1026 637
1027 /** 638 /**
1028 * Creates a depth-first iterator for the specified tree starting in @p node. 639 * Creates a depth-first iterator for the specified tree starting in @p node.
1029 * 640 *
1030 * If the node is not part of the tree, the behavior is undefined. 641 * If the node is not part of the tree, the behavior is undefined.
1034 * @param visit_on_exit true, if the iterator shall visit a node again when 645 * @param visit_on_exit true, if the iterator shall visit a node again when
1035 * leaving the subtree 646 * leaving the subtree
1036 * @return a tree iterator (depth-first) 647 * @return a tree iterator (depth-first)
1037 * @see cxTreeVisit() 648 * @see cxTreeVisit()
1038 */ 649 */
1039 cx_attr_nonnull cx_attr_nodiscard 650 CX_EXTERN CX_NONNULL CX_NODISCARD
1040 CX_EXPORT CxTreeIterator cxTreeIterateSubtree(CxTree *tree, void *node, bool visit_on_exit); 651 CxTreeIterator cxTreeIterateSubtree(CxTree *tree, void *node, bool visit_on_exit);
1041 652
1042 /** 653 /**
1043 * Creates a breadth-first iterator for the specified tree starting in @p node. 654 * Creates a breadth-first iterator for the specified tree starting in @p node.
1044 * 655 *
1045 * If the node is not part of the tree, the behavior is undefined. 656 * If the node is not part of the tree, the behavior is undefined.
1047 * @param tree the tree to iterate 658 * @param tree the tree to iterate
1048 * @param node the node where to start 659 * @param node the node where to start
1049 * @return a tree visitor (a.k.a. breadth-first iterator) 660 * @return a tree visitor (a.k.a. breadth-first iterator)
1050 * @see cxTreeIterate() 661 * @see cxTreeIterate()
1051 */ 662 */
1052 cx_attr_nonnull cx_attr_nodiscard 663 CX_EXTERN CX_NONNULL CX_NODISCARD
1053 CX_EXPORT CxTreeVisitor cxTreeVisitSubtree(CxTree *tree, void *node); 664 CxTreeIterator cxTreeVisitSubtree(CxTree *tree, void *node);
1054 665
1055 /** 666 /**
1056 * Creates a depth-first iterator for the specified tree. 667 * Creates a depth-first iterator for the specified tree.
1057 * 668 *
1058 * @param tree the tree to iterate 669 * @param tree the tree to iterate
1059 * @param visit_on_exit true, if the iterator shall visit a node again when 670 * @param visit_on_exit true, if the iterator shall visit a node again when
1060 * leaving the subtree 671 * leaving the subtree
1061 * @return a tree iterator (depth-first) 672 * @return a tree iterator (depth-first)
1062 * @see cxTreeVisit() 673 * @see cxTreeVisit()
1063 */ 674 */
1064 cx_attr_nonnull cx_attr_nodiscard 675 CX_EXTERN CX_NONNULL CX_NODISCARD
1065 CX_EXPORT CxTreeIterator cxTreeIterate(CxTree *tree, bool visit_on_exit); 676 CxTreeIterator cxTreeIterate(CxTree *tree, bool visit_on_exit);
1066 677
1067 /** 678 /**
1068 * Creates a breadth-first iterator for the specified tree. 679 * Creates a breadth-first iterator for the specified tree.
1069 * 680 *
1070 * @param tree the tree to iterate 681 * @param tree the tree to iterate
1071 * @return a tree visitor (a.k.a. breadth-first iterator) 682 * @return a tree visitor (a.k.a. breadth-first iterator)
1072 * @see cxTreeIterate() 683 * @see cxTreeIterate()
1073 */ 684 */
1074 cx_attr_nonnull cx_attr_nodiscard 685 CX_EXTERN CX_NONNULL CX_NODISCARD
1075 CX_EXPORT CxTreeVisitor cxTreeVisit(CxTree *tree); 686 CxTreeIterator cxTreeVisit(CxTree *tree);
1076 687
1077 /** 688 /**
1078 * Sets the (new) parent of the specified child. 689 * Sets the (new) parent of the specified child.
1079 * 690 *
1080 * If the @p child is not already a member of the tree, this function behaves 691 * If the @p child is not already a member of the tree, this function behaves
1081 * as #cxTreeAddChildNode(). 692 * as #cxTreeAddNode().
1082 * 693 *
1083 * @param tree the tree 694 * @param tree the tree
1084 * @param parent the (new) parent of the child 695 * @param parent the (new) parent of the child
1085 * @param child the node to add 696 * @param child the node to add
1086 * @see cxTreeAddChildNode() 697 * @see cxTreeAddNode()
1087 */ 698 */
1088 cx_attr_nonnull 699 CX_EXTERN CX_NONNULL
1089 CX_EXPORT void cxTreeSetParent(CxTree *tree, void *parent, void *child); 700 void cxTreeSetParent(CxTree *tree, void *parent, void *child);
1090 701
1091 /** 702 /**
1092 * Adds a new node to the tree. 703 * Adds a new node to the tree.
1093 * 704 *
1094 * If the @p child is already a member of the tree, the behavior is undefined. 705 * If the @p child is already a member of the tree, the behavior is undefined.
1095 * Use #cxTreeSetParent() if you want to move a subtree to another location. 706 * Use #cxTreeSetParent() if you want to move a subtree to another location.
1096 * 707 *
1097 * @attention The node may be externally created, but MUST obey the same rules 708 * @attention The node may be externally created, but MUST obey the same rules
1098 * as if it was created by the tree itself with #cxTreeAddChild() (e.g., use 709 * as if it was created by the tree itself with #cxTreeAddData() (e.g., use
1099 * the same allocator). 710 * the tree's allocator).
1100 * 711 *
1101 * @param tree the tree 712 * @param tree the tree
1102 * @param parent the parent of the node to add 713 * @param parent the parent of the node to add
1103 * @param child the node to add 714 * @param child the node to add
1104 * @see cxTreeSetParent() 715 * @see cxTreeSetParent()
1105 */ 716 * @see cxTreeAddData()
1106 cx_attr_nonnull 717 */
1107 CX_EXPORT void cxTreeAddChildNode(CxTree *tree, void *parent, void *child); 718 CX_EXTERN CX_NONNULL
719 void cxTreeAddNode(CxTree *tree, void *parent, void *child);
1108 720
1109 /** 721 /**
1110 * Creates a new node and adds it to the tree. 722 * Creates a new node and adds it to the tree.
1111 *
1112 * With this function you can decide where exactly the new node shall be added.
1113 * If you specified an appropriate search function, you may want to consider
1114 * leaving this task to the tree by using #cxTreeInsert().
1115 *
1116 * Be aware that adding nodes at arbitrary locations in the tree might cause
1117 * wrong or undesired results when subsequently invoking #cxTreeInsert(), and
1118 * the invariant imposed by the search function does not hold any longer.
1119 * 723 *
1120 * @param tree the tree 724 * @param tree the tree
1121 * @param parent the parent node of the new node 725 * @param parent the parent node of the new node
1122 * @param data the data that will be submitted to the create function 726 * @param data the data that will be submitted to the create function
1123 * @return zero when the new node was created, non-zero on allocation failure 727 * @return the added node or @c NULL when the allocation failed
1124 * @see cxTreeInsert() 728 * @see cxTreeAdd()
1125 */ 729 */
1126 cx_attr_nonnull 730 CX_EXTERN CX_NONNULL
1127 CX_EXPORT int cxTreeAddChild(CxTree *tree, void *parent, const void *data); 731 void *cxTreeAddData(CxTree *tree, void *parent, const void *data);
732
733 /**
734 * Creates a new node and adds it to the tree.
735 *
736 * @param tree the tree
737 * @param parent the parent node of the new node
738 * @return the added node or @c NULL when the allocation failed
739 */
740 CX_EXTERN CX_NODISCARD CX_NONNULL
741 void *cxTreeCreateNode(CxTree *tree, void *parent);
742
743 /**
744 * Creates a new root node or returns the existing root node.
745 *
746 * @param tree the tree
747 * @return the new root node, the existing root node, or @c NULL when the allocation failed
748 * @see cxTreeCreateRootData()
749 */
750 CX_EXTERN CX_NODISCARD CX_NONNULL
751 void *cxTreeCreateRoot(CxTree *tree);
752
753 /**
754 * Creates a new root node or uses the existing root node and writes the specified data to that node.
755 *
756 * @note This function immediately returns @c NULL when @c loc_data was not initialized with a positive value.
757 *
758 * @param tree the tree
759 * @param data the data for the root node
760 * @return the new root node, the existing root node,
761 * or @c NULL when the allocation failed or the data location is not known
762 * @see cxTreeCreateRoot()
763 */
764 CX_EXTERN CX_NODISCARD CX_NONNULL
765 void *cxTreeCreateRootData(CxTree *tree, const void *data);
766
767 /**
768 * Exchanges the root of the tree.
769 *
770 * @attention The old tree nodes might need to be deallocated by the caller.
771 * On the other hand, when the tree has destructors registered, keep in mind
772 * that they will be applied to the new tree.
773 * In particular, using cxTreeCreate() with a @c NULL root and setting the
774 * root with this function is @em not equivalent to creating the tree with
775 * a reference to an existing root because trees created without a root will
776 * have destructors registered.
777 *
778 * @param tree the tree
779 * @param new_root the new root node
780 * @return the old root node (or @c NULL when the tree was empty)
781 */
782 CX_EXTERN CX_NONNULL_ARG(1) CX_NODISCARD
783 void *cxTreeSetRoot(CxTree *tree, void *new_root);
1128 784
1129 /** 785 /**
1130 * A function that is invoked when a node needs to be re-linked to a new parent. 786 * A function that is invoked when a node needs to be re-linked to a new parent.
1131 * 787 *
1132 * When a node is re-linked, sometimes the contents need to be updated. 788 * When a node is re-linked, sometimes the contents need to be updated.
1156 * @param node the node to remove (must not be the root node) 812 * @param node the node to remove (must not be the root node)
1157 * @param relink_func optional callback to update the content of each re-linked 813 * @param relink_func optional callback to update the content of each re-linked
1158 * node 814 * node
1159 * @return zero on success, non-zero if @p node is the root node of the tree 815 * @return zero on success, non-zero if @p node is the root node of the tree
1160 */ 816 */
1161 cx_attr_nonnull_arg(1, 2) 817 CX_EXTERN CX_NONNULL_ARG(1, 2)
1162 CX_EXPORT int cxTreeRemoveNode(CxTree *tree, void *node, cx_tree_relink_func relink_func); 818 int cxTreeRemoveNode(CxTree *tree, void *node, cx_tree_relink_func relink_func);
1163 819
1164 /** 820 /**
1165 * Removes a node and its subtree from the tree. 821 * Removes a node and its subtree from the tree.
1166 * 822 *
1167 * If the node is not part of the tree, the behavior is undefined. 823 * If the node is not part of the tree, the behavior is undefined.
1170 * you will need to free the removed subtree by yourself, eventually. 826 * you will need to free the removed subtree by yourself, eventually.
1171 * 827 *
1172 * @param tree the tree 828 * @param tree the tree
1173 * @param node the node to remove 829 * @param node the node to remove
1174 */ 830 */
1175 cx_attr_nonnull 831 CX_EXTERN CX_NONNULL
1176 CX_EXPORT void cxTreeRemoveSubtree(CxTree *tree, void *node); 832 void cxTreeRemoveSubtree(CxTree *tree, void *node);
1177 833
1178 /** 834 /**
1179 * Destroys a node and re-links its children to its former parent. 835 * Destroys a node and re-links its children to its former parent.
1180 * 836 *
1181 * If the node is not part of the tree, the behavior is undefined. 837 * If the node is not part of the tree, the behavior is undefined.
1191 * @param node the node to destroy (must not be the root node) 847 * @param node the node to destroy (must not be the root node)
1192 * @param relink_func optional callback to update the content of each re-linked 848 * @param relink_func optional callback to update the content of each re-linked
1193 * node 849 * node
1194 * @return zero on success, non-zero if @p node is the root node of the tree 850 * @return zero on success, non-zero if @p node is the root node of the tree
1195 */ 851 */
1196 cx_attr_nonnull_arg(1, 2) 852 CX_EXTERN CX_NONNULL_ARG(1, 2)
1197 CX_EXPORT int cxTreeDestroyNode(CxTree *tree, void *node, cx_tree_relink_func relink_func); 853 int cxTreeDestroyNode(CxTree *tree, void *node, cx_tree_relink_func relink_func);
1198
1199 #ifdef __cplusplus
1200 } // extern "C"
1201 #endif
1202 854
1203 #endif //UCX_TREE_H 855 #endif //UCX_TREE_H

Mercurial Repository: dav

mercurial