Mercurial > hg > ucx / file comparison

comparison: src/cx/tree.h

src/cx/tree.h

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

Mercurial Repository: ucx

mercurial