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 it's 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 */
92 size_t counter;
93 /**
94 * The currently observed node.
95 *
96 * This is the same what cxIteratorCurrent() would return.
97 */
98 void *node;
99 /**
100 * Stores a copy of the next pointer of the visited node.
101 * Allows freeing a node on exit without corrupting the iteration.
102 */
103 void *node_next;
104 /**
105 * Internal stack.
106 * Will be automatically freed once the iterator becomes invalid.
107 *
108 * If you want to discard the iterator before, you need to manually
109 * call cxTreeIteratorDispose().
110 */
111 void **stack;
112 /**
113 * Internal capacity of the stack.
114 */
115 size_t stack_capacity;
116 union {
117 /**
118 * Internal stack size.
119 */
120 size_t stack_size;
121 /**
122 * The current depth in the tree.
123 */
124 size_t depth;
125 };
126 } CxTreeIterator;
127
128 /**
129 * An element in a visitor queue.
130 */
131 struct cx_tree_visitor_queue_s {
132 /**
133 * The tree node to visit.
134 */
135 void *node;
136 /**
137 * The depth of the node.
138 */
139 size_t depth;
140 /**
141 * The next element in the queue or @c NULL.
142 */
143 struct cx_tree_visitor_queue_s *next;
144 };
145
146 /**
147 * A breadth-first tree iterator.
148 *
149 * This iterator needs to maintain a visitor queue that will be automatically
150 * freed once the iterator becomes invalid.
151 * If you want to discard the iterator before, you MUST manually call
152 * cxTreeVisitorDispose().
153 *
154 * This iterator is not position-aware in a strict sense, as it does not assume
155 * a particular order of elements in the tree. However, the iterator keeps track
156 * of the number of nodes it has passed in a counter variable.
157 * Each node, regardless of the number of passes, is counted only once.
158 *
159 * @note Objects that are pointed to by an iterator are mutable through that
160 * iterator. However, if the
161 * underlying data structure is mutated by other means than this iterator (e.g.
162 * elements added or removed), the iterator becomes invalid (regardless of what
163 * cxIteratorValid() returns).
164 *
165 * @see CxIterator
166 */
167 typedef struct cx_tree_visitor_s {
168 /**
169 * Base members.
170 */
171 CX_ITERATOR_BASE;
172 /**
173 * Indicates whether the subtree below the current node shall be skipped.
174 */
175 bool skip;
176 /**
177 * Offset in the node struct for the children linked list.
178 */
179 ptrdiff_t loc_children;
180 /**
181 * Offset in the node struct for the next pointer.
182 */
183 ptrdiff_t loc_next;
184 /**
185 * The total number of distinct nodes that have been passed so far.
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
208 /**
209 * Releases internal memory of the given tree iterator.
210 * @param iter the iterator
211 */
212 cx_attr_nonnull
213 static inline void cxTreeIteratorDispose(CxTreeIterator *iter) {
214 free(iter->stack);
215 iter->stack = NULL;
216 }
217
218 /**
219 * Releases internal memory of the given tree visitor.
220 * @param visitor the visitor
221 */
222 cx_attr_nonnull
223 static inline void cxTreeVisitorDispose(CxTreeVisitor *visitor) {
224 struct cx_tree_visitor_queue_s *q = visitor->queue_next;
225 while (q != NULL) {
226 struct cx_tree_visitor_queue_s *next = q->next;
227 free(q);
228 q = next;
229 }
230 }
231
232 /**
233 * Advises the iterator to skip the subtree below the current node and
234 * also continues the current loop.
235 *
236 * @param iterator (@c CxTreeIterator) the iterator
237 */
238 #define cxTreeIteratorContinue(iterator) (iterator).skip = true; continue
239
240 /**
241 * Advises the visitor to skip the subtree below the current node and
242 * also continues the current loop.
243 *
244 * @param visitor (@c CxTreeVisitor) the visitor
245 */
246 #define cxTreeVisitorContinue(visitor) cxTreeIteratorContinue(visitor)
247
248 /**
249 * Links a node to a (new) parent.
250 *
251 * If the node has already a parent, it is unlinked, first.
252 * If the parent has children already, the node is @em appended to the list
253 * of all currently existing children.
254 *
255 * @param parent the parent node
256 * @param node the node that shall be linked
257 * @param loc_parent offset in the node struct for the parent pointer
258 * @param loc_children offset in the node struct for the children linked list
259 * @param loc_last_child optional offset in the node struct for the pointer to
260 * the last child in the linked list (negative if there is no such pointer)
261 * @param loc_prev optional offset in the node struct for the prev pointer
262 * @param loc_next offset in the node struct for the next pointer
263 * @see cx_tree_unlink()
264 */
265 cx_attr_nonnull
266 void cx_tree_link(
267 void *parent,
268 void *node,
269 ptrdiff_t loc_parent,
270 ptrdiff_t loc_children,
271 ptrdiff_t loc_last_child,
272 ptrdiff_t loc_prev,
273 ptrdiff_t loc_next
274 );
275
276 /**
277 * Unlinks a node from its parent.
278 *
279 * If the node has no parent, this function does nothing.
280 *
281 * @param node the node that shall be unlinked from its parent
282 * @param loc_parent offset in the node struct for the parent pointer
283 * @param loc_children offset in the node struct for the children linked list
284 * @param loc_last_child optional offset in the node struct for the pointer to
285 * the last child in the linked list (negative if there is no such pointer)
286 * @param loc_prev optional offset in the node struct for the prev pointer
287 * @param loc_next offset in the node struct for the next pointer
288 * @see cx_tree_link()
289 */
290 cx_attr_nonnull
291 void cx_tree_unlink(
292 void *node,
293 ptrdiff_t loc_parent,
294 ptrdiff_t loc_children,
295 ptrdiff_t loc_last_child,
296 ptrdiff_t loc_prev,
297 ptrdiff_t loc_next
298 );
299
300 /**
301 * Macro that can be used instead of the magic value for infinite search depth.
302 */
303 #define CX_TREE_SEARCH_INFINITE_DEPTH 0
304
305 /**
306 * Function pointer for a search function.
307 *
308 * A function of this kind shall check if the specified @p node
309 * contains the given @p data or if one of the children might contain
310 * the data.
311 *
312 * The function should use the returned integer to indicate how close the
313 * match is, where a negative number means that it does not match at all.
314 * Zero means exact match and a positive number is an implementation defined
315 * measure for the distance to an exact match.
316 *
317 * For example if a tree stores file path information, a node that is
318 * describing a parent directory of a filename that is searched, shall
319 * return a positive number to indicate that a child node might contain the
320 * searched item. On the other hand, if the node denotes a path that is not a
321 * prefix of the searched filename, the function would return -1 to indicate
322 * that the search does not need to be continued in that branch.
323 *
324 * @param node the node that is currently investigated
325 * @param data the data that is searched for
326 *
327 * @return 0 if the node contains the data,
328 * positive if one of the children might contain the data,
329 * negative if neither the node, nor the children contains the data
330 */
331 cx_attr_nonnull
332 typedef int (*cx_tree_search_data_func)(const void *node, const void *data);
333
334
335 /**
336 * Function pointer for a search function.
337 *
338 * A function of this kind shall check if the specified @p node
339 * contains the same @p data as @p new_node or if one of the children might
340 * contain the data.
341 *
342 * The function should use the returned integer to indicate how close the
343 * match is, where a negative number means that it does not match at all.
344 * Zero means exact match and a positive number is an implementation defined
345 * measure for the distance to an exact match.
346 *
347 * For example if a tree stores file path information, a node that is
348 * describing a parent directory of a filename that is searched, shall
349 * return a positive number to indicate that a child node might contain the
350 * searched item. On the other hand, if the node denotes a path that is not a
351 * prefix of the searched filename, the function would return -1 to indicate
352 * that the search does not need to be continued in that branch.
353 *
354 * @param node the node that is currently investigated
355 * @param new_node a new node with the information which is searched
356 *
357 * @return 0 if @p node contains the same data as @p new_node,
358 * positive if one of the children might contain the data,
359 * negative if neither the node, nor the children contains the data
360 */
361 cx_attr_nonnull
362 typedef int (*cx_tree_search_func)(const void *node, const void *new_node);
363
364 /**
365 * Searches for data in a tree.
366 *
367 * When the data cannot be found exactly, the search function might return a
368 * closest result which might be a good starting point for adding a new node
369 * to the tree (see also #cx_tree_add()).
370 *
371 * Depending on the tree structure it is not necessarily guaranteed that the
372 * "closest" match is uniquely defined. This function will search for a node
373 * with the best match according to the @p sfunc (meaning: the return value of
374 * @p sfunc which is closest to zero). If that is also ambiguous, an arbitrary
375 * node matching the criteria is returned.
376 *
377 * @param root the root node
378 * @param depth the maximum depth (zero=indefinite, one=just root)
379 * @param data the data to search for
380 * @param sfunc the search function
381 * @param result where the result shall be stored
382 * @param loc_children offset in the node struct for the children linked list
383 * @param loc_next offset in the node struct for the next pointer
384 * @return zero if the node was found exactly, positive if a node was found that
385 * could contain the node (but doesn't right now), negative if the tree does not
386 * contain any node that might be related to the searched data
387 */
388 cx_attr_nonnull
389 cx_attr_access_w(5)
390 int cx_tree_search_data(
391 const void *root,
392 size_t depth,
393 const void *data,
394 cx_tree_search_data_func sfunc,
395 void **result,
396 ptrdiff_t loc_children,
397 ptrdiff_t loc_next
398 );
399
400 /**
401 * Searches for a node in a tree.
402 *
403 * When no node with the same data can be found, the search function might
404 * return a closest result which might be a good starting point for adding the
405 * new node to the tree (see also #cx_tree_add()).
406 *
407 * Depending on the tree structure it is not necessarily guaranteed that the
408 * "closest" match is uniquely defined. This function will search for a node
409 * with the best match according to the @p sfunc (meaning: the return value of
410 * @p sfunc which is closest to zero). If that is also ambiguous, an arbitrary
411 * node matching the criteria is returned.
412 *
413 * @param root the root node
414 * @param depth the maximum depth (zero=indefinite, one=just root)
415 * @param node the node to search for
416 * @param sfunc the search function
417 * @param result where the result shall be stored
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 zero if the node was found exactly, positive if a node was found that
421 * could contain the node (but doesn't right now), negative if the tree does not
422 * contain any node that might be related to the searched data
423 */
424 cx_attr_nonnull
425 cx_attr_access_w(5)
426 int cx_tree_search(
427 const void *root,
428 size_t depth,
429 const void *node,
430 cx_tree_search_func sfunc,
431 void **result,
432 ptrdiff_t loc_children,
433 ptrdiff_t loc_next
434 );
435
436 /**
437 * Creates a depth-first iterator for a tree with the specified root node.
438 *
439 * @note A tree iterator needs to maintain a stack of visited nodes, which is
440 * allocated using stdlib malloc().
441 * When the iterator becomes invalid, this memory is automatically released.
442 * However, if you wish to cancel the iteration before the iterator becomes
443 * invalid by itself, you MUST call cxTreeIteratorDispose() manually to release
444 * the memory.
445 *
446 * @remark The returned iterator does not support cxIteratorFlagRemoval().
447 *
448 * @param root the root node
449 * @param visit_on_exit set to true, when the iterator shall visit a node again
450 * after processing all children
451 * @param loc_children offset in the node struct for the children linked list
452 * @param loc_next offset in the node struct for the next pointer
453 * @return the new tree iterator
454 * @see cxTreeIteratorDispose()
455 */
456 cx_attr_nodiscard
457 CxTreeIterator cx_tree_iterator(
458 void *root,
459 bool visit_on_exit,
460 ptrdiff_t loc_children,
461 ptrdiff_t loc_next
462 );
463
464 /**
465 * Creates a breadth-first iterator for a tree with the specified root node.
466 *
467 * @note A tree visitor needs to maintain a queue of to be visited nodes, which
468 * is allocated using stdlib malloc().
469 * When the visitor becomes invalid, this memory is automatically released.
470 * However, if you wish to cancel the iteration before the visitor becomes
471 * invalid by itself, you MUST call cxTreeVisitorDispose() manually to release
472 * the memory.
473 *
474 * @remark The returned iterator does not support cxIteratorFlagRemoval().
475 *
476 * @param root the root node
477 * @param loc_children offset in the node struct for the children linked list
478 * @param loc_next offset in the node struct for the next pointer
479 * @return the new tree visitor
480 * @see cxTreeVisitorDispose()
481 */
482 cx_attr_nodiscard
483 CxTreeVisitor cx_tree_visitor(
484 void *root,
485 ptrdiff_t loc_children,
486 ptrdiff_t loc_next
487 );
488
489 /**
490 * Describes a function that creates a tree node from the specified data.
491 * The first argument points to the data the node shall contain and
492 * the second argument may be used for additional data (e.g. an allocator).
493 * Functions of this type shall either return a new pointer to a newly
494 * created node or @c NULL when allocation fails.
495 *
496 * @note the function may leave the node pointers in the struct uninitialized.
497 * The caller is responsible to set them according to the intended use case.
498 */
499 cx_attr_nonnull_arg(1)
500 typedef void *(*cx_tree_node_create_func)(const void *, void *);
501
502 /**
503 * The local search depth for a new subtree when adding multiple elements.
504 * The default value is 3.
505 * This variable is used by #cx_tree_add_array() and #cx_tree_add_iter() to
506 * implement optimized insertion of multiple elements into a tree.
507 */
508 extern unsigned int cx_tree_add_look_around_depth;
509
510 /**
511 * Adds multiple elements efficiently to a tree.
512 *
513 * Once an element cannot be added to the tree, this function returns, leaving
514 * the iterator in a valid state pointing to the element that could not be
515 * added.
516 * Also, the pointer of the created node will be stored to @p failed.
517 * The integer returned by this function denotes the number of elements obtained
518 * from the @p iter that have been successfully processed.
519 * When all elements could be processed, a @c NULL pointer will be written to
520 * @p failed.
521 *
522 * The advantage of this function compared to multiple invocations of
523 * #cx_tree_add() is that the search for the insert locations is not always
524 * started from the root node.
525 * Instead, the function checks #cx_tree_add_look_around_depth many parent nodes
526 * of the current insert location before starting from the root node again.
527 * When the variable is set to zero, only the last found location is checked
528 * again.
529 *
530 * Refer to the documentation of #cx_tree_add() for more details.
531 *
532 * @param iter a pointer to an arbitrary iterator
533 * @param num the maximum number of elements to obtain from the iterator
534 * @param sfunc a search function
535 * @param cfunc a node creation function
536 * @param cdata optional additional data
537 * @param root the root node of the tree
538 * @param failed location where the pointer to a failed node shall be stored
539 * @param loc_parent offset in the node struct for the parent pointer
540 * @param loc_children offset in the node struct for the children linked list
541 * @param loc_last_child optional offset in the node struct for the pointer to
542 * the last child in the linked list (negative if there is no such pointer)
543 * @param loc_prev optional offset in the node struct for the prev pointer
544 * @param loc_next offset in the node struct for the next pointer
545 * @return the number of nodes created and added
546 * @see cx_tree_add()
547 */
548 cx_attr_nonnull_arg(1, 3, 4, 6, 7)
549 cx_attr_access_w(6)
550 size_t cx_tree_add_iter(
551 struct cx_iterator_base_s *iter,
552 size_t num,
553 cx_tree_search_func sfunc,
554 cx_tree_node_create_func cfunc,
555 void *cdata,
556 void **failed,
557 void *root,
558 ptrdiff_t loc_parent,
559 ptrdiff_t loc_children,
560 ptrdiff_t loc_last_child,
561 ptrdiff_t loc_prev,
562 ptrdiff_t loc_next
563 );
564
565 /**
566 * Adds multiple elements efficiently to a tree.
567 *
568 * Once an element cannot be added to the tree, this function returns, storing
569 * the pointer of the created node to @p failed.
570 * The integer returned by this function denotes the number of elements from
571 * the @p src array that have been successfully processed.
572 * When all elements could be processed, a @c NULL pointer will be written to
573 * @p failed.
574 *
575 * The advantage of this function compared to multiple invocations of
576 * #cx_tree_add() is that the search for the insert locations is not always
577 * started from the root node.
578 * Instead, the function checks #cx_tree_add_look_around_depth many parent nodes
579 * of the current insert location before starting from the root node again.
580 * When the variable is set to zero, only the last found location is checked
581 * again.
582 *
583 * Refer to the documentation of #cx_tree_add() for more details.
584 *
585 * @param src a pointer to the source data array
586 * @param num the number of elements in the @p src array
587 * @param elem_size the size of each element in the @p src array
588 * @param sfunc a search function
589 * @param cfunc a node creation function
590 * @param cdata optional additional data
591 * @param failed location where the pointer to a failed node shall be stored
592 * @param root the root node of the tree
593 * @param loc_parent offset in the node struct for the parent pointer
594 * @param loc_children offset in the node struct for the children linked list
595 * @param loc_last_child optional offset in the node struct for the pointer to
596 * the last child in the linked list (negative if there is no such pointer)
597 * @param loc_prev optional offset in the node struct for the prev pointer
598 * @param loc_next offset in the node struct for the next pointer
599 * @return the number of array elements successfully processed
600 * @see cx_tree_add()
601 */
602 cx_attr_nonnull_arg(1, 4, 5, 7, 8)
603 cx_attr_access_w(7)
604 size_t cx_tree_add_array(
605 const void *src,
606 size_t num,
607 size_t elem_size,
608 cx_tree_search_func sfunc,
609 cx_tree_node_create_func cfunc,
610 void *cdata,
611 void **failed,
612 void *root,
613 ptrdiff_t loc_parent,
614 ptrdiff_t loc_children,
615 ptrdiff_t loc_last_child,
616 ptrdiff_t loc_prev,
617 ptrdiff_t loc_next
618 );
619
620 /**
621 * Adds data to a tree.
622 *
623 * An adequate location where to add the new tree node is searched with the
624 * specified @p sfunc.
625 *
626 * When a location is found, the @p cfunc will be invoked with @p cdata.
627 *
628 * The node returned by @p cfunc will be linked into the tree.
629 * When @p sfunc returned a positive integer, the new node will be linked as a
630 * child. The other children (now siblings of the new node) are then checked
631 * with @p sfunc, whether they could be children of the new node and re-linked
632 * accordingly.
633 *
634 * When @p sfunc returned zero and the found node has a parent, the new
635 * node will be added as sibling - otherwise, the new node will be added
636 * as a child.
637 *
638 * When @p sfunc returned a negative value, the new node will not be added to
639 * the tree and this function returns a non-zero value.
640 * The caller should check if @p cnode contains a node pointer and deal with the
641 * node that could not be added.
642 *
643 * This function also returns a non-zero value when @p cfunc tries to allocate
644 * a new node but fails to do so. In that case, the pointer stored to @p cnode
645 * will be @c NULL.
646 *
647 * Multiple elements can be added more efficiently with
648 * #cx_tree_add_array() or #cx_tree_add_iter().
649 *
650 * @param src a pointer to the data
651 * @param sfunc a search function
652 * @param cfunc a node creation function
653 * @param cdata optional additional data
654 * @param cnode the location where a pointer to the new node is stored
655 * @param root the root node of the tree
656 * @param loc_parent offset in the node struct for the parent pointer
657 * @param loc_children offset in the node struct for the children linked list
658 * @param loc_last_child optional offset in the node struct for the pointer to
659 * the last child in the linked list (negative if there is no such pointer)
660 * @param loc_prev optional offset in the node struct for the prev pointer
661 * @param loc_next offset in the node struct for the next pointer
662 * @return zero when a new node was created and added to the tree,
663 * non-zero otherwise
664 */
665 cx_attr_nonnull_arg(1, 2, 3, 5, 6)
666 cx_attr_access_w(5)
667 int cx_tree_add(
668 const void *src,
669 cx_tree_search_func sfunc,
670 cx_tree_node_create_func cfunc,
671 void *cdata,
672 void **cnode,
673 void *root,
674 ptrdiff_t loc_parent,
675 ptrdiff_t loc_children,
676 ptrdiff_t loc_last_child,
677 ptrdiff_t loc_prev,
678 ptrdiff_t loc_next
679 );
680
681
682 /**
683 * Tree class type.
684 */
685 typedef struct cx_tree_class_s cx_tree_class;
686
687 /**
688 * Base structure that can be used for tree nodes in a #CxTree.
689 */
690 struct cx_tree_node_base_s {
691 /**
692 * Pointer to the parent.
693 */
694 struct cx_tree_node_base_s *parent;
695 /**
696 * Pointer to the first child.
697 */
698 struct cx_tree_node_base_s *children;
699 /**
700 * Pointer to the last child.
701 */
702 struct cx_tree_node_base_s *last_child;
703 /**
704 * Pointer to the previous sibling.
705 */
706 struct cx_tree_node_base_s *prev;
707 /**
708 * Pointer to the next sibling.
709 */
710 struct cx_tree_node_base_s *next;
711 };
712
713 /**
714 * Structure for holding the base data of a tree.
715 */
716 struct cx_tree_s {
717 /**
718 * The tree class definition.
719 */
720 const cx_tree_class *cl;
721
722 /**
723 * Allocator to allocate new nodes.
724 */
725 const CxAllocator *allocator;
726
727 /**
728 * A pointer to the root node.
729 *
730 * Will be @c NULL when @c size is 0.
731 */
732 void *root;
733
734 /**
735 * A function to create new nodes.
736 *
737 * Invocations to this function will receive a pointer to this tree
738 * structure as second argument.
739 *
740 * Nodes MAY use #cx_tree_node_base_s as base layout, but do not need to.
741 */
742 cx_tree_node_create_func node_create;
743
744 /**
745 * An optional simple destructor for the tree nodes.
746 */
747 cx_destructor_func simple_destructor;
748
749 /**
750 * An optional advanced destructor for the tree nodes.
751 */
752 cx_destructor_func2 advanced_destructor;
753
754 /**
755 * The pointer to additional data that is passed to the advanced destructor.
756 */
757 void *destructor_data;
758
759 /**
760 * A function to compare two nodes.
761 */
762 cx_tree_search_func search;
763
764 /**
765 * A function to compare a node with data.
766 */
767 cx_tree_search_data_func search_data;
768
769 /**
770 * The number of currently stored elements.
771 */
772 size_t size;
773
774 /**
775 * Offset in the node struct for the parent pointer.
776 */
777 ptrdiff_t loc_parent;
778
779 /**
780 * Offset in the node struct for the children linked list.
781 */
782 ptrdiff_t loc_children;
783
784 /**
785 * Optional offset in the node struct for the pointer to the last child
786 * in the linked list (negative if there is no such pointer).
787 */
788 ptrdiff_t loc_last_child;
789
790 /**
791 * Offset in the node struct for the previous sibling pointer.
792 */
793 ptrdiff_t loc_prev;
794
795 /**
796 * Offset in the node struct for the next sibling pointer.
797 */
798 ptrdiff_t loc_next;
799 };
800
801 /**
802 * Macro to roll out the #cx_tree_node_base_s structure with a custom
803 * node type.
804 *
805 * Must be used as first member in your custom tree struct.
806 *
807 * @param type the data type for the nodes
808 */
809 #define CX_TREE_NODE_BASE(type) \
810 type *parent; \
811 type *children;\
812 type *last_child;\
813 type *prev;\
814 type *next
815
816 /**
817 * Macro for specifying the layout of a base node tree.
818 *
819 * When your tree uses #CX_TREE_NODE_BASE, you can use this
820 * macro in all tree functions that expect the layout parameters
821 * @c loc_parent, @c loc_children, @c loc_last_child, @c loc_prev,
822 * and @c loc_next.
823 */
824 #define cx_tree_node_base_layout \
825 offsetof(struct cx_tree_node_base_s, parent),\
826 offsetof(struct cx_tree_node_base_s, children),\
827 offsetof(struct cx_tree_node_base_s, last_child),\
828 offsetof(struct cx_tree_node_base_s, prev), \
829 offsetof(struct cx_tree_node_base_s, next)
830
831 /**
832 * The class definition for arbitrary trees.
833 */
834 struct cx_tree_class_s {
835 /**
836 * Member function for inserting a single element.
837 *
838 * Implementations SHALL NOT simply invoke @p insert_many as this comes
839 * with too much overhead.
840 */
841 int (*insert_element)(
842 struct cx_tree_s *tree,
843 const void *data
844 );
845
846 /**
847 * Member function for inserting multiple elements.
848 *
849 * Implementations SHALL avoid to perform a full search in the tree for
850 * every element even though the source data MAY be unsorted.
851 */
852 size_t (*insert_many)(
853 struct cx_tree_s *tree,
854 struct cx_iterator_base_s *iter,
855 size_t n
856 );
857
858 /**
859 * Member function for finding a node.
860 */
861 void *(*find)(
862 struct cx_tree_s *tree,
863 const void *subtree,
864 const void *data,
865 size_t depth
866 );
867 };
868
869 /**
870 * Common type for all tree implementations.
871 */
872 typedef struct cx_tree_s CxTree;
873
874
875 /**
876 * Destroys a node and it's subtree.
877 *
878 * It is guaranteed that the simple destructor is invoked before
879 * the advanced destructor, starting with the leaf nodes of the subtree.
880 *
881 * When this function is invoked on the root node of the tree, it destroys the
882 * tree contents, but - in contrast to #cxTreeFree() - not the tree
883 * structure, leaving an empty tree behind.
884 *
885 * @note The destructor function, if any, will @em not be invoked. That means
886 * you will need to free the removed subtree by yourself, eventually.
887 *
888 * @attention This function will not free the memory of the nodes with the
889 * tree's allocator, because that is usually done by the advanced destructor
890 * and would therefore result in a double-free.
891 *
892 * @param tree the tree
893 * @param node the node to remove
894 * @see cxTreeFree()
895 */
896 cx_attr_nonnull
897 void cxTreeDestroySubtree(CxTree *tree, void *node);
898
899
900 /**
901 * Destroys the tree contents.
902 *
903 * It is guaranteed that the simple destructor is invoked before
904 * the advanced destructor, starting with the leaf nodes of the subtree.
905 *
906 * This is a convenience macro for invoking #cxTreeDestroySubtree() on the
907 * root node of the tree.
908 *
909 * @attention Be careful when calling this function when no destructor function
910 * is registered that actually frees the memory of nodes. In that case you will
911 * need a reference to the (former) root node of the tree somewhere or
912 * otherwise you will be leaking memory.
913 *
914 * @param tree the tree
915 * @see cxTreeDestroySubtree()
916 */
917 #define cxTreeClear(tree) cxTreeDestroySubtree(tree, tree->root)
918
919 /**
920 * Deallocates the tree structure.
921 *
922 * The destructor functions are invoked for each node, starting with the leaf
923 * nodes.
924 * It is guaranteed that for each node the simple destructor is invoked before
925 * the advanced destructor.
926 *
927 * @attention This function will only invoke the destructor functions
928 * on the nodes.
929 * It will NOT additionally free the nodes with the tree's allocator, because
930 * that would cause a double-free in most scenarios where the advanced
931 * destructor is already freeing the memory.
932 *
933 * @param tree the tree to free
934 */
935 void cxTreeFree(CxTree *tree);
936
937 /**
938 * Creates a new tree structure based on the specified layout.
939 *
940 * The specified @p allocator will be used for creating the tree struct
941 * and SHALL be used by @p create_func to allocate memory for the nodes.
942 *
943 * @note This function will also register an advanced destructor which
944 * will free the nodes with the allocator's free() method.
945 *
946 * @param allocator the allocator that shall be used
947 * (if @c NULL, a default stdlib allocator will be used)
948 * @param create_func a function that creates new nodes
949 * @param search_func a function that compares two nodes
950 * @param search_data_func a function that compares a node with data
951 * @param loc_parent offset in the node struct for the parent pointer
952 * @param loc_children offset in the node struct for the children linked list
953 * @param loc_last_child optional offset in the node struct for the pointer to
954 * the last child in the linked list (negative if there is no such pointer)
955 * @param loc_prev optional offset in the node struct for the prev pointer
956 * @param loc_next offset in the node struct for the next pointer
957 * @return the new tree
958 * @see cxTreeCreateSimple()
959 * @see cxTreeCreateWrapped()
960 */
961 cx_attr_nonnull_arg(2, 3, 4)
962 cx_attr_nodiscard
963 cx_attr_malloc
964 cx_attr_dealloc(cxTreeFree, 1)
965 CxTree *cxTreeCreate(
966 const CxAllocator *allocator,
967 cx_tree_node_create_func create_func,
968 cx_tree_search_func search_func,
969 cx_tree_search_data_func search_data_func,
970 ptrdiff_t loc_parent,
971 ptrdiff_t loc_children,
972 ptrdiff_t loc_last_child,
973 ptrdiff_t loc_prev,
974 ptrdiff_t loc_next
975 );
976
977 /**
978 * Creates a new tree structure based on a default layout.
979 *
980 * Nodes created by @p create_func MUST contain #cx_tree_node_base_s as first
981 * member (or at least respect the default offsets specified in the tree
982 * struct) and they MUST be allocated with the specified allocator.
983 *
984 * @note This function will also register an advanced destructor which
985 * will free the nodes with the allocator's free() method.
986 *
987 * @param allocator (@c CxAllocator*) the allocator that shall be used
988 * @param create_func (@c cx_tree_node_create_func) a function that creates new nodes
989 * @param search_func (@c cx_tree_search_func) a function that compares two nodes
990 * @param search_data_func (@c cx_tree_search_data_func) a function that compares a node with data
991 * @return (@c CxTree*) the new tree
992 * @see cxTreeCreate()
993 */
994 #define cxTreeCreateSimple(\
995 allocator, create_func, search_func, search_data_func \
996 ) cxTreeCreate(allocator, create_func, search_func, search_data_func, \
997 cx_tree_node_base_layout)
998
999 /**
1000 * Creates a new tree structure based on an existing tree.
1001 *
1002 * The specified @p allocator will be used for creating the tree struct.
1003 *
1004 * @attention This function will create an incompletely defined tree structure
1005 * where neither the create function, the search function, nor a destructor
1006 * will be set. If you wish to use any of this functionality for the wrapped
1007 * tree, you need to specify those functions afterwards.
1008 *
1009 * @param allocator the allocator that was used for nodes of the wrapped tree
1010 * (if @c NULL, a default stdlib allocator is assumed)
1011 * @param root the root node of the tree that shall be wrapped
1012 * @param loc_parent offset in the node struct for the parent pointer
1013 * @param loc_children offset in the node struct for the children linked list
1014 * @param loc_last_child optional offset in the node struct for the pointer to
1015 * the last child in the linked list (negative if there is no such pointer)
1016 * @param loc_prev optional offset in the node struct for the prev pointer
1017 * @param loc_next offset in the node struct for the next pointer
1018 * @return the new tree
1019 * @see cxTreeCreate()
1020 */
1021 cx_attr_nonnull_arg(2)
1022 cx_attr_nodiscard
1023 cx_attr_malloc
1024 cx_attr_dealloc(cxTreeFree, 1)
1025 CxTree *cxTreeCreateWrapped(
1026 const CxAllocator *allocator,
1027 void *root,
1028 ptrdiff_t loc_parent,
1029 ptrdiff_t loc_children,
1030 ptrdiff_t loc_last_child,
1031 ptrdiff_t loc_prev,
1032 ptrdiff_t loc_next
1033 );
1034
1035 /**
1036 * Inserts data into the tree.
1037 *
1038 * @remark For this function to work, the tree needs specified search and
1039 * create functions, which might not be available for wrapped trees
1040 * (see #cxTreeCreateWrapped()).
1041 *
1042 * @param tree the tree
1043 * @param data the data to insert
1044 * @retval zero success
1045 * @retval non-zero failure
1046 */
1047 cx_attr_nonnull
1048 static inline int cxTreeInsert(
1049 CxTree *tree,
1050 const void *data
1051 ) {
1052 return tree->cl->insert_element(tree, data);
1053 }
1054
1055 /**
1056 * Inserts elements provided by an iterator efficiently into the tree.
1057 *
1058 * @remark For this function to work, the tree needs specified search and
1059 * create functions, which might not be available for wrapped trees
1060 * (see #cxTreeCreateWrapped()).
1061 *
1062 * @param tree the tree
1063 * @param iter the iterator providing the elements
1064 * @param n the maximum number of elements to insert
1065 * @return the number of elements that could be successfully inserted
1066 */
1067 cx_attr_nonnull
1068 static inline size_t cxTreeInsertIter(
1069 CxTree *tree,
1070 struct cx_iterator_base_s *iter,
1071 size_t n
1072 ) {
1073 return tree->cl->insert_many(tree, iter, n);
1074 }
1075
1076 /**
1077 * Inserts an array of data efficiently into the tree.
1078 *
1079 * @remark For this function to work, the tree needs specified search and
1080 * create functions, which might not be available for wrapped trees
1081 * (see #cxTreeCreateWrapped()).
1082 *
1083 * @param tree the tree
1084 * @param data the array of data to insert
1085 * @param elem_size the size of each element in the array
1086 * @param n the number of elements in the array
1087 * @return the number of elements that could be successfully inserted
1088 */
1089 cx_attr_nonnull
1090 static inline size_t cxTreeInsertArray(
1091 CxTree *tree,
1092 const void *data,
1093 size_t elem_size,
1094 size_t n
1095 ) {
1096 if (n == 0) return 0;
1097 if (n == 1) return 0 == cxTreeInsert(tree, data) ? 1 : 0;
1098 CxIterator iter = cxIterator(data, elem_size, n);
1099 return cxTreeInsertIter(tree, cxIteratorRef(iter), n);
1100 }
1101
1102 /**
1103 * Searches the data in the specified tree.
1104 *
1105 * @remark For this function to work, the tree needs a specified @c search_data
1106 * function, which might not be available wrapped trees
1107 * (see #cxTreeCreateWrapped()).
1108 *
1109 * @param tree the tree
1110 * @param data the data to search for
1111 * @return the first matching node, or @c NULL when the data cannot be found
1112 */
1113 cx_attr_nonnull
1114 cx_attr_nodiscard
1115 static inline void *cxTreeFind(
1116 CxTree *tree,
1117 const void *data
1118 ) {
1119 return tree->cl->find(tree, tree->root, data, 0);
1120 }
1121
1122 /**
1123 * Searches the data in the specified subtree.
1124 *
1125 * When @p max_depth is zero, the depth is not limited.
1126 * The @p subtree_root itself is on depth 1 and its children have depth 2.
1127 *
1128 * @note When @p subtree_root is not part of the @p tree, the behavior is
1129 * undefined.
1130 *
1131 * @remark For this function to work, the tree needs a specified @c search_data
1132 * function, which might not be the case for wrapped trees
1133 * (see #cxTreeCreateWrapped()).
1134 *
1135 * @param tree the tree
1136 * @param data the data to search for
1137 * @param subtree_root the node where to start
1138 * @param max_depth the maximum search depth
1139 * @return the first matching node, or @c NULL when the data cannot be found
1140 */
1141 cx_attr_nonnull
1142 cx_attr_nodiscard
1143 static inline void *cxTreeFindInSubtree(
1144 CxTree *tree,
1145 const void *data,
1146 void *subtree_root,
1147 size_t max_depth
1148 ) {
1149 return tree->cl->find(tree, subtree_root, data, max_depth);
1150 }
1151
1152 /**
1153 * Determines the size of the specified subtree.
1154 *
1155 * @param tree the tree
1156 * @param subtree_root the root node of the subtree
1157 * @return the number of nodes in the specified subtree
1158 */
1159 cx_attr_nonnull
1160 cx_attr_nodiscard
1161 size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root);
1162
1163 /**
1164 * Determines the depth of the specified subtree.
1165 *
1166 * @param tree the tree
1167 * @param subtree_root the root node of the subtree
1168 * @return the tree depth including the @p subtree_root
1169 */
1170 cx_attr_nonnull
1171 cx_attr_nodiscard
1172 size_t cxTreeSubtreeDepth(CxTree *tree, void *subtree_root);
1173
1174 /**
1175 * Determines the depth of the entire tree.
1176 *
1177 * @param tree the tree
1178 * @return the tree depth, counting the root as one
1179 */
1180 cx_attr_nonnull
1181 cx_attr_nodiscard
1182 size_t cxTreeDepth(CxTree *tree);
1183
1184 /**
1185 * Creates a depth-first iterator for the specified tree starting in @p node.
1186 *
1187 * If the node is not part of the tree, the behavior is undefined.
1188 *
1189 * @param tree the tree to iterate
1190 * @param node the node where to start
1191 * @param visit_on_exit true, if the iterator shall visit a node again when
1192 * leaving the subtree
1193 * @return a tree iterator (depth-first)
1194 * @see cxTreeVisit()
1195 */
1196 cx_attr_nonnull
1197 cx_attr_nodiscard
1198 static inline CxTreeIterator cxTreeIterateSubtree(
1199 CxTree *tree,
1200 void *node,
1201 bool visit_on_exit
1202 ) {
1203 return cx_tree_iterator(
1204 node, visit_on_exit,
1205 tree->loc_children, tree->loc_next
1206 );
1207 }
1208
1209 /**
1210 * Creates a breadth-first iterator for the specified tree starting in @p node.
1211 *
1212 * If the node is not part of the tree, the behavior is undefined.
1213 *
1214 * @param tree the tree to iterate
1215 * @param node the node where to start
1216 * @return a tree visitor (a.k.a. breadth-first iterator)
1217 * @see cxTreeIterate()
1218 */
1219 cx_attr_nonnull
1220 cx_attr_nodiscard
1221 static inline CxTreeVisitor cxTreeVisitSubtree(CxTree *tree, void *node) {
1222 return cx_tree_visitor(
1223 node, tree->loc_children, tree->loc_next
1224 );
1225 }
1226
1227 /**
1228 * Creates a depth-first iterator for the specified tree.
1229 *
1230 * @param tree the tree to iterate
1231 * @param visit_on_exit true, if the iterator shall visit a node again when
1232 * leaving the subtree
1233 * @return a tree iterator (depth-first)
1234 * @see cxTreeVisit()
1235 */
1236 cx_attr_nonnull
1237 cx_attr_nodiscard
1238 static inline CxTreeIterator cxTreeIterate(
1239 CxTree *tree,
1240 bool visit_on_exit
1241 ) {
1242 return cxTreeIterateSubtree(tree, tree->root, visit_on_exit);
1243 }
1244
1245 /**
1246 * Creates a breadth-first iterator for the specified tree.
1247 *
1248 * @param tree the tree to iterate
1249 * @return a tree visitor (a.k.a. breadth-first iterator)
1250 * @see cxTreeIterate()
1251 */
1252 cx_attr_nonnull
1253 cx_attr_nodiscard
1254 static inline CxTreeVisitor cxTreeVisit(CxTree *tree) {
1255 return cxTreeVisitSubtree(tree, tree->root);
1256 }
1257
1258 /**
1259 * Sets the (new) parent of the specified child.
1260 *
1261 * If the @p child is not already member of the tree, this function behaves
1262 * as #cxTreeAddChildNode().
1263 *
1264 * @param tree the tree
1265 * @param parent the (new) parent of the child
1266 * @param child the node to add
1267 * @see cxTreeAddChildNode()
1268 */
1269 cx_attr_nonnull
1270 void cxTreeSetParent(
1271 CxTree *tree,
1272 void *parent,
1273 void *child
1274 );
1275
1276 /**
1277 * Adds a new node to the tree.
1278 *
1279 * If the @p child is already member of the tree, the behavior is undefined.
1280 * Use #cxTreeSetParent() if you want to move a subtree to another location.
1281 *
1282 * @attention The node may be externally created, but MUST obey the same rules
1283 * as if it was created by the tree itself with #cxTreeAddChild() (e.g. use
1284 * the same allocator).
1285 *
1286 * @param tree the tree
1287 * @param parent the parent of the node to add
1288 * @param child the node to add
1289 * @see cxTreeSetParent()
1290 */
1291 cx_attr_nonnull
1292 void cxTreeAddChildNode(
1293 CxTree *tree,
1294 void *parent,
1295 void *child
1296 );
1297
1298 /**
1299 * Creates a new node and adds it to the tree.
1300 *
1301 * With this function you can decide where exactly the new node shall be added.
1302 * If you specified an appropriate search function, you may want to consider
1303 * leaving this task to the tree by using #cxTreeInsert().
1304 *
1305 * Be aware that adding nodes at arbitrary locations in the tree might cause
1306 * wrong or undesired results when subsequently invoking #cxTreeInsert() and
1307 * the invariant imposed by the search function does not hold any longer.
1308 *
1309 * @param tree the tree
1310 * @param parent the parent node of the new node
1311 * @param data the data that will be submitted to the create function
1312 * @return zero when the new node was created, non-zero on allocation failure
1313 * @see cxTreeInsert()
1314 */
1315 cx_attr_nonnull
1316 int cxTreeAddChild(
1317 CxTree *tree,
1318 void *parent,
1319 const void *data
1320 );
1321
1322 /**
1323 * A function that is invoked when a node needs to be re-linked to a new parent.
1324 *
1325 * When a node is re-linked, sometimes the contents need to be updated.
1326 * This callback is invoked by #cxTreeRemoveNode() and #cxTreeDestroyNode()
1327 * so that those updates can be applied when re-linking the children of the
1328 * removed node.
1329 *
1330 * @param node the affected node
1331 * @param old_parent the old parent of the node
1332 * @param new_parent the new parent of the node
1333 */
1334 cx_attr_nonnull
1335 typedef void (*cx_tree_relink_func)(
1336 void *node,
1337 const void *old_parent,
1338 const void *new_parent
1339 );
1340
1341 /**
1342 * Removes a node and re-links its children to its former parent.
1343 *
1344 * If the node is not part of the tree, the behavior is undefined.
1345 *
1346 * @note The destructor function, if any, will @em not be invoked. That means
1347 * you will need to free the removed node by yourself, eventually.
1348 *
1349 * @param tree the tree
1350 * @param node the node to remove (must not be the root node)
1351 * @param relink_func optional callback to update the content of each re-linked
1352 * node
1353 * @return zero on success, non-zero if @p node is the root node of the tree
1354 */
1355 cx_attr_nonnull_arg(1, 2)
1356 int cxTreeRemoveNode(
1357 CxTree *tree,
1358 void *node,
1359 cx_tree_relink_func relink_func
1360 );
1361
1362 /**
1363 * Removes a node and it's subtree from the tree.
1364 *
1365 * If the node is not part of the tree, the behavior is undefined.
1366 *
1367 * @note The destructor function, if any, will @em not be invoked. That means
1368 * you will need to free the removed subtree by yourself, eventually.
1369 *
1370 * @param tree the tree
1371 * @param node the node to remove
1372 */
1373 cx_attr_nonnull
1374 void cxTreeRemoveSubtree(CxTree *tree, void *node);
1375
1376 /**
1377 * Destroys a node and re-links its children to its former parent.
1378 *
1379 * If the node is not part of the tree, the behavior is undefined.
1380 *
1381 * It is guaranteed that the simple destructor is invoked before
1382 * the advanced destructor.
1383 *
1384 * @attention This function will not free the memory of the node with the
1385 * tree's allocator, because that is usually done by the advanced destructor
1386 * and would therefore result in a double-free.
1387 *
1388 * @param tree the tree
1389 * @param node the node to destroy (must not be the root node)
1390 * @param relink_func optional callback to update the content of each re-linked
1391 * node
1392 * @return zero on success, non-zero if @p node is the root node of the tree
1393 */
1394 cx_attr_nonnull_arg(1, 2)
1395 int cxTreeDestroyNode(
1396 CxTree *tree,
1397 void *node,
1398 cx_tree_relink_func relink_func
1399 );
1400
1401 #ifdef __cplusplus
1402 } // extern "C"
1403 #endif
1404
1405 #endif //UCX_TREE_H
1406