1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
3 *
4 * Copyright 2024 Mike Becker, Olaf Wintermann All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 *
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 */
28 /**
29 * @file tree.h
30 * @brief Interface for tree implementations.
31 * @author Mike Becker
32 * @author Olaf Wintermann
33 * @copyright 2-Clause BSD License
34 */
35
36 #ifndef UCX_TREE_H
37 #define UCX_TREE_H
38
39 #include "common.h"
40
41 #include "collection.h"
42
43 #ifdef __cplusplus
44 extern "C" {
45 #endif
46
47 /**
48 * A depth-first tree iterator.
49 *
50 * This iterator is not position-aware in a strict sense, as it does not assume
51 * a particular order of elements in the tree. However, the iterator keeps track
52 * of the number of nodes it has passed in a counter-variable.
53 * Each node, regardless of the number of passes, is counted only once.
54 *
55 * @note Objects that are pointed to by an iterator are mutable through that
56 * iterator. However, if the
57 * underlying data structure is mutated by other means than this iterator (e.g.,
58 * elements added or removed), the iterator becomes invalid (regardless of what
59 * cxIteratorValid() returns).
60 *
61 * @see CxIterator
62 */
63 typedef struct cx_tree_iterator_s {
64 /**
65 * Base members.
66 */
67 CX_ITERATOR_BASE;
68 /**
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.
83 */
84 ptrdiff_t loc_children;
85 /**
86 * Offset in the node struct for the next pointer.
87 */
88 ptrdiff_t loc_next;
89 /**
90 * The total number of distinct nodes that have been passed so far.
91 * This includes the current node.
92 */
93 size_t counter;
94 /**
95 * The currently observed node.
96 *
97 * This is the same what cxIteratorCurrent() would return.
98 */
99 void *node;
100 /**
101 * Stores a copy of the pointer to the successor of the visited node.
102 * Allows freeing a node on exit without corrupting the iteration.
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 {
118 /**
119 * Internal stack size.
120 */
121 size_t stack_size;
122 /**
123 * The current depth in the tree.
124 * The node with which the iteration starts has depth 1.
125 */
126 size_t depth;
127 };
128 } 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
212 /**
213 * Releases internal memory of the given tree iterator.
214 * @param iter the iterator
215 */
216 cx_attr_nonnull
217 CX_EXPORT 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
226 /**
227 * Advises the iterator to skip the subtree below the current node and
228 * also continues the current loop.
229 *
230 * @param iterator (@c CxTreeIterator) the iterator
231 */
232 #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
242 /**
243 * Links a node to a (new) parent.
244 *
245 * If the node already has a parent, it is unlinked, first.
246 * If the parent has children already, the node is @em appended to the list
247 * of all currently existing children.
248 *
249 * @param parent the parent node
250 * @param node the node that shall be linked
251 * @param loc_parent offset in the node struct for the parent pointer
252 * @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
254 * 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
256 * @param loc_next offset in the node struct for the next pointer
257 * @see cx_tree_unlink()
258 */
259 cx_attr_nonnull
260 CX_EXPORT void cx_tree_link(void *parent, void *node,
261 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
262 ptrdiff_t loc_prev, ptrdiff_t loc_next);
263
264 /**
265 * Unlinks a node from its parent.
266 *
267 * If the node has no parent, this function does nothing.
268 *
269 * @param node the node that shall be unlinked from its parent
270 * @param loc_parent offset in the node struct for the parent pointer
271 * @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
273 * 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
275 * @param loc_next offset in the node struct for the next pointer
276 * @see cx_tree_link()
277 */
278 cx_attr_nonnull
279 CX_EXPORT void cx_tree_unlink(void *node,
280 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
281 ptrdiff_t loc_prev, ptrdiff_t loc_next);
282
283 /**
284 * Macro that can be used instead of the magic value for infinite search depth.
285 */
286 #define CX_TREE_SEARCH_INFINITE_DEPTH 0
287
288 /**
289 * Function pointer for a search function.
290 *
291 * A function of this kind shall check if the specified @p node
292 * contains the given @p data or if one of the children might contain
293 * the data.
294 *
295 * The function should use the returned integer to indicate how close the
296 * match is, where a negative number means that it does not match at all.
297 * Zero means exact match and a positive number is an implementation defined
298 * measure for the distance to an exact match.
299 *
300 * For example, consider a tree that stores file path information.
301 * A node which is describing a parent directory of a searched file shall
302 * return a positive number to indicate that a child node might contain the
303 * searched item. On the other hand, if the node denotes a path that is not a
304 * prefix of the searched filename, the function would return -1 to indicate
305 * that the search does not need to be continued in that branch.
306 *
307 * @param node the node that is currently investigated
308 * @param data the data that is searched for
309 *
310 * @return 0 if the node contains the data,
311 * positive if one of the children might contain the data,
312 * negative if neither the node nor the children contains the data
313 */
314 typedef int (*cx_tree_search_data_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
345 /**
346 * Searches for data in a tree.
347 *
348 * 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
350 * to the tree (see also #cx_tree_add()).
351 *
352 * 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
354 * 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
356 * node matching the criteria is returned.
357 *
358 * @param root the root node
359 * @param depth the maximum depth (zero=indefinite, one=just root)
360 * @param data the data to search for
361 * @param sfunc the search function
362 * @param result where the result shall be stored
363 * @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
365 * @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
367 * contain any node that might be related to the searched data
368 */
369 cx_attr_nonnull cx_attr_access_w(5)
370 CX_EXPORT int cx_tree_search_data(const void *root, size_t depth,
371 const void *data, cx_tree_search_data_func sfunc,
372 void **result, 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
403 /**
404 * Creates a depth-first iterator for a tree with the specified root node.
405 *
406 * @note A tree iterator needs to maintain a stack of visited nodes, which is
407 * allocated using the cxDefaultAllocator.
408 * When the iterator becomes invalid, this memory is automatically released.
409 * However, if you wish to cancel the iteration before the iterator becomes
410 * invalid by itself, you MUST call cxTreeIteratorDispose() manually to release
411 * the memory.
412 *
413 * @remark The returned iterator does not support cxIteratorFlagRemoval().
414 *
415 * @param root the root node
416 * @param visit_on_exit set to true, when the iterator shall visit a node again
417 * after processing all children
418 * @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
420 * @return the new tree iterator
421 * @see cxTreeIteratorDispose()
422 */
423 cx_attr_nodiscard
424 CX_EXPORT CxTreeIterator cx_tree_iterator(void *root, bool visit_on_exit,
425 ptrdiff_t loc_children, ptrdiff_t loc_next);
426
427 /**
428 * Creates a breadth-first iterator for a tree with the specified root node.
429 *
430 * @note A tree visitor needs to maintain a queue of to-be visited nodes, which
431 * is allocated using the cxDefaultAllocator.
432 * When the visitor becomes invalid, this memory is automatically released.
433 * However, if you wish to cancel the iteration before the visitor becomes
434 * invalid by itself, you MUST call cxTreeVisitorDispose() manually to release
435 * the memory.
436 *
437 * @remark The returned iterator does not support cxIteratorFlagRemoval().
438 *
439 * @param root the root node
440 * @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
442 * @return the new tree visitor
443 * @see cxTreeVisitorDispose()
444 */
445 cx_attr_nodiscard
446 CX_EXPORT CxTreeVisitor cx_tree_visitor(void *root,
447 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
616 /**
617 * Base structure that can be used for tree nodes in a #CxTree.
618 */
619 struct cx_tree_node_base_s {
620 /**
621 * Pointer to the parent.
622 */
623 struct cx_tree_node_base_s *parent;
624 /**
625 * Pointer to the first child.
626 */
627 struct cx_tree_node_base_s *children;
628 /**
629 * Pointer to the last child.
630 */
631 struct cx_tree_node_base_s *last_child;
632 /**
633 * Pointer to the previous sibling.
634 */
635 struct cx_tree_node_base_s *prev;
636 /**
637 * Pointer to the next sibling.
638 */
639 struct cx_tree_node_base_s *next;
640 };
641
642 /**
643 * Structure for holding the base data of a tree.
644 */
645 struct cx_tree_s {
646 CX_COLLECTION_BASE;
647 /**
648 * The tree class definition.
649 */
650 const cx_tree_class *cl;
651
652 /**
653 * A pointer to the root node.
654 *
655 * Will be @c NULL when @c size is 0.
656 */
657 void *root;
658
659 /**
660 * A function to create new nodes.
661 *
662 * Invocations to this function will receive a pointer to this tree
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
679 /**
680 * Offset in the node struct for the parent pointer.
681 */
682 ptrdiff_t loc_parent;
683
684 /**
685 * Offset in the node struct for the children linked list.
686 */
687 ptrdiff_t loc_children;
688
689 /**
690 * Optional offset in the node struct for the pointer to the last child
691 * in the linked list (negative if there is no such pointer).
692 */
693 ptrdiff_t loc_last_child;
694
695 /**
696 * Offset in the node struct for the previous sibling pointer.
697 */
698 ptrdiff_t loc_prev;
699
700 /**
701 * Offset in the node struct for the next sibling pointer.
702 */
703 ptrdiff_t loc_next;
704 };
705
706 /**
707 * Macro to roll out the #cx_tree_node_base_s structure with a custom
708 * node type.
709 *
710 * Must be used as the first member in your custom tree struct.
711 *
712 * @param type the data type for the nodes
713 */
714 #define CX_TREE_NODE_BASE(type) \
715 type *parent; \
716 type *children;\
717 type *last_child;\
718 type *prev;\
719 type *next
720
721 /**
722 * Macro for specifying the layout of a base node tree.
723 *
724 * When your tree uses #CX_TREE_NODE_BASE, you can use this
725 * macro in all tree functions that expect the layout parameters
726 * @c loc_parent, @c loc_children, @c loc_last_child, @c loc_prev,
727 * and @c loc_next.
728 */
729 #define cx_tree_node_base_layout \
730 offsetof(struct cx_tree_node_base_s, parent),\
731 offsetof(struct cx_tree_node_base_s, children),\
732 offsetof(struct cx_tree_node_base_s, last_child),\
733 offsetof(struct cx_tree_node_base_s, prev), \
734 offsetof(struct cx_tree_node_base_s, next)
735
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
768 /**
769 * Destroys a node and its subtree.
770 *
771 * It is guaranteed that the simple destructor is invoked before
772 * the advanced destructor, starting with the leaf nodes of the subtree.
773 *
774 * When this function is invoked on the root node of the tree, it destroys the
775 * tree contents, but - in contrast to #cxTreeFree() - not the tree
776 * structure, leaving an empty tree behind.
777 *
778 * @note The destructor function, if any, will @em not be invoked. That means
779 * you will need to free the removed subtree by yourself, eventually.
780 *
781 * @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
783 * and would therefore result in a double-free.
784 *
785 * @param tree the tree
786 * @param node the node to remove
787 * @see cxTreeFree()
788 */
789 cx_attr_nonnull
790 CX_EXPORT void cxTreeDestroySubtree(CxTree *tree, void *node);
791
792
793 /**
794 * Destroys the tree contents.
795 *
796 * It is guaranteed that the simple destructor is invoked before
797 * the advanced destructor, starting with the leaf nodes of the subtree.
798 *
799 * This is a convenience macro for invoking #cxTreeDestroySubtree() on the
800 * root node of the tree.
801 *
802 * @attention Be careful when calling this function when no destructor function
803 * is registered that actually frees the memory of nodes. In that case you will
804 * need a reference to the (former) root node of the tree somewhere, or
805 * otherwise you will be leaking memory.
806 *
807 * @param tree the tree
808 * @see cxTreeDestroySubtree()
809 */
810 #define cxTreeClear(tree) cxTreeDestroySubtree(tree, tree->root)
811
812 /**
813 * Deallocates the tree structure.
814 *
815 * The destructor functions are invoked for each node, starting with the leaf
816 * nodes.
817 * It is guaranteed that for each node the simple destructor is invoked before
818 * the advanced destructor.
819 *
820 * @attention This function will only invoke the destructor functions
821 * on the nodes.
822 * It will NOT additionally free the nodes with the tree's allocator, because
823 * that would cause a double-free in most scenarios where the advanced
824 * destructor is already freeing the memory.
825 *
826 * @param tree the tree to free
827 */
828 CX_EXPORT void cxTreeFree(CxTree *tree);
829
830 /**
831 * Creates a new tree structure based on the specified layout.
832 *
833 * 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.
835 *
836 * @note This function will also register an advanced destructor which
837 * will free the nodes with the allocator's free() method.
838 *
839 * @param allocator the allocator that shall be used
840 * (if @c NULL, the cxDefaultAllocator will be used)
841 * @param create_func a function that creates new nodes
842 * @param search_func a function that compares two nodes
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)
892 * @param root the root node of the tree that shall be wrapped
893 * @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
895 * @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)
897 * @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
899 * @return the new tree
900 * @see cxTreeCreate()
901 */
902 cx_attr_nonnull_arg(2) cx_attr_nodiscard cx_attr_malloc cx_attr_dealloc(cxTreeFree, 1)
903 CX_EXPORT CxTree *cxTreeCreateWrapped(const CxAllocator *allocator, void *root,
904 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
905 ptrdiff_t loc_prev, ptrdiff_t loc_next);
906
907 /**
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.
969 *
970 * 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.
972 *
973 * @note When @p subtree_root is not part of the @p tree, the behavior is
974 * undefined.
975 *
976 * @remark For this function to work, the tree needs a specified @c search_data
977 * function, which might not be the case for wrapped trees
978 * (see #cxTreeCreateWrapped()).
979 *
980 * @param tree the tree
981 * @param data the data to search for
982 * @param subtree_root the node where to start
983 * @param max_depth the maximum search depth
984 * @return the first matching node, or @c NULL when the data cannot be found
985 */
986 cx_attr_nonnull cx_attr_nodiscard
987 CX_EXPORT void *cxTreeFindInSubtree(CxTree *tree, const void *data, void *subtree_root, size_t max_depth);
988
989 /**
990 * Determines the size of the specified subtree.
991 *
992 * @param tree the tree
993 * @param subtree_root the root node of the subtree
994 * @return the number of nodes in the specified subtree
995 */
996 cx_attr_nonnull cx_attr_nodiscard
997 CX_EXPORT size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root);
998
999 /**
1000 * Determines the depth of the specified subtree.
1001 *
1002 * @param tree the tree
1003 * @param subtree_root the root node of the subtree
1004 * @return the tree depth including the @p subtree_root
1005 */
1006 cx_attr_nonnull cx_attr_nodiscard
1007 CX_EXPORT size_t cxTreeSubtreeDepth(CxTree *tree, void *subtree_root);
1008
1009 /**
1010 * Determines the size of the entire tree.
1011 *
1012 * @param tree the tree
1013 * @return the tree size, counting the root as one
1014 */
1015 cx_attr_nonnull cx_attr_nodiscard
1016 CX_EXPORT size_t cxTreeSize(CxTree *tree);
1017
1018 /**
1019 * Determines the depth of the entire tree.
1020 *
1021 * @param tree the tree
1022 * @return the tree depth, counting the root as one
1023 */
1024 cx_attr_nonnull cx_attr_nodiscard
1025 CX_EXPORT size_t cxTreeDepth(CxTree *tree);
1026
1027 /**
1028 * Creates a depth-first iterator for the specified tree starting in @p node.
1029 *
1030 * If the node is not part of the tree, the behavior is undefined.
1031 *
1032 * @param tree the tree to iterate
1033 * @param node the node where to start
1034 * @param visit_on_exit true, if the iterator shall visit a node again when
1035 * leaving the subtree
1036 * @return a tree iterator (depth-first)
1037 * @see cxTreeVisit()
1038 */
1039 cx_attr_nonnull cx_attr_nodiscard
1040 CX_EXPORT CxTreeIterator cxTreeIterateSubtree(CxTree *tree, void *node, bool visit_on_exit);
1041
1042 /**
1043 * Creates a breadth-first iterator for the specified tree starting in @p node.
1044 *
1045 * If the node is not part of the tree, the behavior is undefined.
1046 *
1047 * @param tree the tree to iterate
1048 * @param node the node where to start
1049 * @return a tree visitor (a.k.a. breadth-first iterator)
1050 * @see cxTreeIterate()
1051 */
1052 cx_attr_nonnull cx_attr_nodiscard
1053 CX_EXPORT CxTreeVisitor cxTreeVisitSubtree(CxTree *tree, void *node);
1054
1055 /**
1056 * Creates a depth-first iterator for the specified tree.
1057 *
1058 * @param tree the tree to iterate
1059 * @param visit_on_exit true, if the iterator shall visit a node again when
1060 * leaving the subtree
1061 * @return a tree iterator (depth-first)
1062 * @see cxTreeVisit()
1063 */
1064 cx_attr_nonnull cx_attr_nodiscard
1065 CX_EXPORT CxTreeIterator cxTreeIterate(CxTree *tree, bool visit_on_exit);
1066
1067 /**
1068 * Creates a breadth-first iterator for the specified tree.
1069 *
1070 * @param tree the tree to iterate
1071 * @return a tree visitor (a.k.a. breadth-first iterator)
1072 * @see cxTreeIterate()
1073 */
1074 cx_attr_nonnull cx_attr_nodiscard
1075 CX_EXPORT CxTreeVisitor cxTreeVisit(CxTree *tree);
1076
1077 /**
1078 * Sets the (new) parent of the specified child.
1079 *
1080 * If the @p child is not already a member of the tree, this function behaves
1081 * as #cxTreeAddChildNode().
1082 *
1083 * @param tree the tree
1084 * @param parent the (new) parent of the child
1085 * @param child the node to add
1086 * @see cxTreeAddChildNode()
1087 */
1088 cx_attr_nonnull
1089 CX_EXPORT void cxTreeSetParent(CxTree *tree, void *parent, void *child);
1090
1091 /**
1092 * Adds a new node to the tree.
1093 *
1094 * 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.
1096 *
1097 * @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
1099 * the same allocator).
1100 *
1101 * @param tree the tree
1102 * @param parent the parent of the node to add
1103 * @param child the node to add
1104 * @see cxTreeSetParent()
1105 */
1106 cx_attr_nonnull
1107 CX_EXPORT void cxTreeAddChildNode(CxTree *tree, void *parent, void *child);
1108
1109 /**
1110 * 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 *
1120 * @param tree the tree
1121 * @param parent the parent node of the new node
1122 * @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
1124 * @see cxTreeInsert()
1125 */
1126 cx_attr_nonnull
1127 CX_EXPORT int cxTreeAddChild(CxTree *tree, void *parent, const void *data);
1128
1129 /**
1130 * A function that is invoked when a node needs to be re-linked to a new parent.
1131 *
1132 * When a node is re-linked, sometimes the contents need to be updated.
1133 * This callback is invoked by #cxTreeRemoveNode() and #cxTreeDestroyNode()
1134 * so that those updates can be applied when re-linking the children of the
1135 * removed node.
1136 *
1137 * @param node the affected node
1138 * @param old_parent the old parent of the node
1139 * @param new_parent the new parent of the node
1140 */
1141 typedef void (*cx_tree_relink_func)(
1142 void *node,
1143 const void *old_parent,
1144 const void *new_parent
1145 );
1146
1147 /**
1148 * Removes a node and re-links its children to its former parent.
1149 *
1150 * If the node is not part of the tree, the behavior is undefined.
1151 *
1152 * @note The destructor function, if any, will @em not be invoked. That means
1153 * you will need to free the removed node by yourself, eventually.
1154 *
1155 * @param tree the tree
1156 * @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
1158 * node
1159 * @return zero on success, non-zero if @p node is the root node of the tree
1160 */
1161 cx_attr_nonnull_arg(1, 2)
1162 CX_EXPORT int cxTreeRemoveNode(CxTree *tree, void *node, cx_tree_relink_func relink_func);
1163
1164 /**
1165 * Removes a node and its subtree from the tree.
1166 *
1167 * If the node is not part of the tree, the behavior is undefined.
1168 *
1169 * @note The destructor function, if any, will @em not be invoked. That means
1170 * you will need to free the removed subtree by yourself, eventually.
1171 *
1172 * @param tree the tree
1173 * @param node the node to remove
1174 */
1175 cx_attr_nonnull
1176 CX_EXPORT void cxTreeRemoveSubtree(CxTree *tree, void *node);
1177
1178 /**
1179 * Destroys a node and re-links its children to its former parent.
1180 *
1181 * If the node is not part of the tree, the behavior is undefined.
1182 *
1183 * It is guaranteed that the simple destructor is invoked before
1184 * the advanced destructor.
1185 *
1186 * @attention This function will not free the memory of the node with the
1187 * tree's allocator, because that is usually done by the advanced destructor
1188 * and would therefore result in a double-free.
1189 *
1190 * @param tree the tree
1191 * @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
1193 * node
1194 * @return zero on success, non-zero if @p node is the root node of the tree
1195 */
1196 cx_attr_nonnull_arg(1, 2)
1197 CX_EXPORT int cxTreeDestroyNode(CxTree *tree, void *node, cx_tree_relink_func relink_func);
1198
1199 #ifdef __cplusplus
1200 } // extern "C"
1201 #endif
1202
1203 #endif //UCX_TREE_H
1204