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 __attribute__((__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 __attribute__((__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 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 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 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 __attribute__((__nonnull__))
266 void cx_tree_link(
267 void *restrict parent,
268 void *restrict 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 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 __attribute__((__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 * Function pointer for a search function.
302 *
303 * A function of this kind shall check if the specified \p node
304 * contains the given \p data or if one of the children might contain
305 * the data.
306 *
307 * The function should use the returned integer to indicate how close the
308 * match is, where a negative number means that it does not match at all.
309 *
310 * For example if a tree stores file path information, a node that is
311 * describing a parent directory of a filename that is searched, shall
312 * return a positive number to indicate that a child node might contain the
313 * searched item. On the other hand, if the node denotes a path that is not a
314 * prefix of the searched filename, the function would return -1 to indicate
315 * that the search does not need to be continued in that branch.
316 *
317 * @param node the node that is currently investigated
318 * @param data the data that is searched for
319 *
320 * @return 0 if the node contains the data,
321 * positive if one of the children might contain the data,
322 * negative if neither the node, nor the children contains the data
323 */
324 typedef int (*cx_tree_search_data_func)(const void *node, const void *data);
325
326
327 /**
328 * Function pointer for a search function.
329 *
330 * A function of this kind shall check if the specified \p node
331 * contains the same \p data as \p new_node or if one of the children might
332 * contain the data.
333 *
334 * The function should use the returned integer to indicate how close the
335 * match is, where a negative number means that it does not match at all.
336 *
337 * For example if a tree stores file path information, a node that is
338 * describing a parent directory of a filename that is searched, shall
339 * return a positive number to indicate that a child node might contain the
340 * searched item. On the other hand, if the node denotes a path that is not a
341 * prefix of the searched filename, the function would return -1 to indicate
342 * that the search does not need to be continued in that branch.
343 *
344 * @param node the node that is currently investigated
345 * @param new_node a new node with the information which is searched
346 *
347 * @return 0 if \p node contains the same data as \p new_node,
348 * positive if one of the children might contain the data,
349 * negative if neither the node, nor the children contains the data
350 */
351 typedef int (*cx_tree_search_func)(const void *node, const void *new_node);
352
353 /**
354 * Searches for data in a tree.
355 *
356 * When the data cannot be found exactly, the search function might return a
357 * closest result which might be a good starting point for adding a new node
358 * to the tree (see also #cx_tree_add()).
359 *
360 * Depending on the tree structure it is not necessarily guaranteed that the
361 * "closest" match is uniquely defined. This function will search for a node
362 * with the best match according to the \p sfunc (meaning: the return value of
363 * \p sfunc which is closest to zero). If that is also ambiguous, an arbitrary
364 * node matching the criteria is returned.
365 *
366 * @param root the root node
367 * @param data the data to search for
368 * @param sfunc the search function
369 * @param result where the result shall be stored
370 * @param loc_children offset in the node struct for the children linked list
371 * @param loc_next offset in the node struct for the next pointer
372 * @return zero if the node was found exactly, positive if a node was found that
373 * could contain the node (but doesn't right now), negative if the tree does not
374 * contain any node that might be related to the searched data
375 */
376 __attribute__((__nonnull__))
377 int cx_tree_search_data(
378 const void *root,
379 const void *data,
380 cx_tree_search_data_func sfunc,
381 void **result,
382 ptrdiff_t loc_children,
383 ptrdiff_t loc_next
384 );
385
386 /**
387 * Searches for a node in a tree.
388 *
389 * When no node with the same data can be found, the search function might
390 * return a closest result which might be a good starting point for adding the
391 * new node to the tree (see also #cx_tree_add()).
392 *
393 * Depending on the tree structure it is not necessarily guaranteed that the
394 * "closest" match is uniquely defined. This function will search for a node
395 * with the best match according to the \p sfunc (meaning: the return value of
396 * \p sfunc which is closest to zero). If that is also ambiguous, an arbitrary
397 * node matching the criteria is returned.
398 *
399 * @param root the root node
400 * @param node the node to search for
401 * @param sfunc the search function
402 * @param result where the result shall be stored
403 * @param loc_children offset in the node struct for the children linked list
404 * @param loc_next offset in the node struct for the next pointer
405 * @return zero if the node was found exactly, positive if a node was found that
406 * could contain the node (but doesn't right now), negative if the tree does not
407 * contain any node that might be related to the searched data
408 */
409 __attribute__((__nonnull__))
410 int cx_tree_search(
411 const void *root,
412 const void *node,
413 cx_tree_search_func sfunc,
414 void **result,
415 ptrdiff_t loc_children,
416 ptrdiff_t loc_next
417 );
418
419 /**
420 * Creates a depth-first iterator for a tree with the specified root node.
421 *
422 * @note A tree iterator needs to maintain a stack of visited nodes, which is
423 * allocated using stdlib malloc().
424 * When the iterator becomes invalid, this memory is automatically released.
425 * However, if you wish to cancel the iteration before the iterator becomes
426 * invalid by itself, you MUST call cxTreeIteratorDispose() manually to release
427 * the memory.
428 *
429 * @remark The returned iterator does not support cxIteratorFlagRemoval().
430 *
431 * @param root the root node
432 * @param visit_on_exit set to true, when the iterator shall visit a node again
433 * after processing all children
434 * @param loc_children offset in the node struct for the children linked list
435 * @param loc_next offset in the node struct for the next pointer
436 * @return the new tree iterator
437 * @see cxTreeIteratorDispose()
438 */
439 CxTreeIterator cx_tree_iterator(
440 void *root,
441 bool visit_on_exit,
442 ptrdiff_t loc_children,
443 ptrdiff_t loc_next
444 );
445
446 /**
447 * Creates a breadth-first iterator for a tree with the specified root node.
448 *
449 * @note A tree visitor needs to maintain a queue of to be visited nodes, which
450 * is allocated using stdlib malloc().
451 * When the visitor becomes invalid, this memory is automatically released.
452 * However, if you wish to cancel the iteration before the visitor becomes
453 * invalid by itself, you MUST call cxTreeVisitorDispose() manually to release
454 * the memory.
455 *
456 * @remark The returned iterator does not support cxIteratorFlagRemoval().
457 *
458 * @param root the root node
459 * @param loc_children offset in the node struct for the children linked list
460 * @param loc_next offset in the node struct for the next pointer
461 * @return the new tree visitor
462 * @see cxTreeVisitorDispose()
463 */
464 CxTreeVisitor cx_tree_visitor(
465 void *root,
466 ptrdiff_t loc_children,
467 ptrdiff_t loc_next
468 );
469
470 /**
471 * Describes a function that creates a tree node from the specified data.
472 * The first argument points to the data the node shall contain and
473 * the second argument may be used for additional data (e.g. an allocator).
474 * Functions of this type shall either return a new pointer to a newly
475 * created node or \c NULL when allocation fails.
476 *
477 * \note the function may leave the node pointers in the struct uninitialized.
478 * The caller is responsible to set them according to the intended use case.
479 */
480 typedef void *(*cx_tree_node_create_func)(const void *, void *);
481
482 /**
483 * The local search depth for a new subtree when adding multiple elements.
484 * The default value is 3.
485 * This variable is used by #cx_tree_add_array() and #cx_tree_add_iter() to
486 * implement optimized insertion of multiple elements into a tree.
487 */
488 extern unsigned int cx_tree_add_look_around_depth;
489
490 /**
491 * Adds multiple elements efficiently to a tree.
492 *
493 * Once an element cannot be added to the tree, this function returns, leaving
494 * the iterator in a valid state pointing to the element that could not be
495 * added.
496 * Also, the pointer of the created node will be stored to \p failed.
497 * The integer returned by this function denotes the number of elements obtained
498 * from the \p iter that have been successfully processed.
499 * When all elements could be processed, a \c NULL pointer will be written to
500 * \p failed.
501 *
502 * The advantage of this function compared to multiple invocations of
503 * #cx_tree_add() is that the search for the insert locations is not always
504 * started from the root node.
505 * Instead, the function checks #cx_tree_add_look_around_depth many parent nodes
506 * of the current insert location before starting from the root node again.
507 * When the variable is set to zero, only the last found location is checked
508 * again.
509 *
510 * Refer to the documentation of #cx_tree_add() for more details.
511 *
512 * @param iter a pointer to an arbitrary iterator
513 * @param num the maximum number of elements to obtain from the iterator
514 * @param sfunc a search function
515 * @param cfunc a node creation function
516 * @param cdata optional additional data
517 * @param root the root node of the tree
518 * @param failed location where the pointer to a failed node shall be stored
519 * @param loc_parent offset in the node struct for the parent pointer
520 * @param loc_children offset in the node struct for the children linked list
521 * @param loc_last_child optional offset in the node struct for the pointer to
522 * the last child in the linked list (negative if there is no such pointer)
523 * @param loc_prev offset in the node struct for the prev pointer
524 * @param loc_next offset in the node struct for the next pointer
525 * @return the number of nodes created and added
526 * @see cx_tree_add()
527 */
528 __attribute__((__nonnull__(1, 3, 4, 6, 7)))
529 size_t cx_tree_add_iter(
530 struct cx_iterator_base_s *iter,
531 size_t num,
532 cx_tree_search_func sfunc,
533 cx_tree_node_create_func cfunc,
534 void *cdata,
535 void **failed,
536 void *root,
537 ptrdiff_t loc_parent,
538 ptrdiff_t loc_children,
539 ptrdiff_t loc_last_child,
540 ptrdiff_t loc_prev,
541 ptrdiff_t loc_next
542 );
543
544 /**
545 * Adds multiple elements efficiently to a tree.
546 *
547 * Once an element cannot be added to the tree, this function returns, storing
548 * the pointer of the created node to \p failed.
549 * The integer returned by this function denotes the number of elements from
550 * the \p src array that have been successfully processed.
551 * When all elements could be processed, a \c NULL pointer will be written to
552 * \p failed.
553 *
554 * The advantage of this function compared to multiple invocations of
555 * #cx_tree_add() is that the search for the insert locations is not always
556 * started from the root node.
557 * Instead, the function checks #cx_tree_add_look_around_depth many parent nodes
558 * of the current insert location before starting from the root node again.
559 * When the variable is set to zero, only the last found location is checked
560 * again.
561 *
562 * Refer to the documentation of #cx_tree_add() for more details.
563 *
564 * @param src a pointer to the source data array
565 * @param num the number of elements in the \p src array
566 * @param elem_size the size of each element in the \p src array
567 * @param sfunc a search function
568 * @param cfunc a node creation function
569 * @param cdata optional additional data
570 * @param failed location where the pointer to a failed node shall be stored
571 * @param root the root node of the tree
572 * @param loc_parent offset in the node struct for the parent pointer
573 * @param loc_children offset in the node struct for the children linked list
574 * @param loc_last_child optional offset in the node struct for the pointer to
575 * the last child in the linked list (negative if there is no such pointer)
576 * @param loc_prev offset in the node struct for the prev pointer
577 * @param loc_next offset in the node struct for the next pointer
578 * @return the number of array elements successfully processed
579 * @see cx_tree_add()
580 */
581 __attribute__((__nonnull__(1, 4, 5, 7, 8)))
582 size_t cx_tree_add_array(
583 const void *src,
584 size_t num,
585 size_t elem_size,
586 cx_tree_search_func sfunc,
587 cx_tree_node_create_func cfunc,
588 void *cdata,
589 void **failed,
590 void *root,
591 ptrdiff_t loc_parent,
592 ptrdiff_t loc_children,
593 ptrdiff_t loc_last_child,
594 ptrdiff_t loc_prev,
595 ptrdiff_t loc_next
596 );
597
598 /**
599 * Adds data to a tree.
600 *
601 * An adequate location where to add the new tree node is searched with the
602 * specified \p sfunc.
603 *
604 * When a location is found, the \p cfunc will be invoked with \p cdata.
605 *
606 * The node returned by \p cfunc will be linked into the tree.
607 * When \p sfunc returned a positive integer, the new node will be linked as a
608 * child. The other children (now siblings of the new node) are then checked
609 * with \p sfunc, whether they could be children of the new node and re-linked
610 * accordingly.
611 *
612 * When \p sfunc returned zero and the found node has a parent, the new
613 * node will be added as sibling - otherwise, the new node will be added
614 * as a child.
615 *
616 * When \p sfunc returned a negative value, the new node will not be added to
617 * the tree and this function returns a non-zero value.
618 * The caller should check if \p cnode contains a node pointer and deal with the
619 * node that could not be added.
620 *
621 * This function also returns a non-zero value when \p cfunc tries to allocate
622 * a new node but fails to do so. In that case, the pointer stored to \p cnode
623 * will be \c NULL.
624 *
625 * Multiple elements can be added more efficiently with
626 * #cx_tree_add_array() or #cx_tree_add_iter().
627 *
628 * @param src a pointer to the data
629 * @param sfunc a search function
630 * @param cfunc a node creation function
631 * @param cdata optional additional data
632 * @param cnode the location where a pointer to the new node is stored
633 * @param root the root node of the tree
634 * @param loc_parent offset in the node struct for the parent pointer
635 * @param loc_children offset in the node struct for the children linked list
636 * @param loc_last_child optional offset in the node struct for the pointer to
637 * the last child in the linked list (negative if there is no such pointer)
638 * @param loc_prev offset in the node struct for the prev pointer
639 * @param loc_next offset in the node struct for the next pointer
640 * @return zero when a new node was created and added to the tree,
641 * non-zero otherwise
642 */
643 __attribute__((__nonnull__(1, 2, 3, 5, 6)))
644 int cx_tree_add(
645 const void *src,
646 cx_tree_search_func sfunc,
647 cx_tree_node_create_func cfunc,
648 void *cdata,
649 void **cnode,
650 void *root,
651 ptrdiff_t loc_parent,
652 ptrdiff_t loc_children,
653 ptrdiff_t loc_last_child,
654 ptrdiff_t loc_prev,
655 ptrdiff_t loc_next
656 );
657
658
659 /**
660 * Tree class type.
661 */
662 typedef struct cx_tree_class_s cx_tree_class;
663
664 /**
665 * Base structure that can be used for tree nodes in a #CxTree.
666 */
667 struct cx_tree_node_base_s {
668 /**
669 * Pointer to the parent.
670 */
671 struct cx_tree_node_base_s *parent;
672 /**
673 * Pointer to the first child.
674 */
675 struct cx_tree_node_base_s *children;
676 /**
677 * Pointer to the last child.
678 */
679 struct cx_tree_node_base_s *last_child;
680 /**
681 * Pointer to the previous sibling.
682 */
683 struct cx_tree_node_base_s *prev;
684 /**
685 * Pointer to the next sibling.
686 */
687 struct cx_tree_node_base_s *next;
688 };
689
690 /**
691 * Structure for holding the base data of a tree.
692 */
693 struct cx_tree_s {
694 /**
695 * The tree class definition.
696 */
697 const cx_tree_class *cl;
698
699 /**
700 * Allocator to allocate new nodes.
701 */
702 const CxAllocator *allocator;
703
704 /**
705 * A pointer to the root node.
706 *
707 * Will be \c NULL when \c size is 0.
708 */
709 void *root;
710
711 /**
712 * A function to create new nodes.
713 *
714 * Invocations to this function will receive a pointer to this tree
715 * structure as second argument.
716 *
717 * Nodes MAY use #cx_tree_node_base_s as base layout, but do not need to.
718 */
719 cx_tree_node_create_func node_create;
720
721 /**
722 * An optional simple destructor for the tree nodes.
723 */
724 cx_destructor_func simple_destructor;
725
726 /**
727 * An optional advanced destructor for the tree nodes.
728 */
729 cx_destructor_func2 advanced_destructor;
730
731 /**
732 * The pointer to additional data that is passed to the advanced destructor.
733 */
734 void *destructor_data;
735
736 /**
737 * A function to compare two nodes.
738 */
739 cx_tree_search_func search;
740
741 /**
742 * A function to compare a node with data.
743 */
744 cx_tree_search_data_func search_data;
745
746 /**
747 * The number of currently stored elements.
748 */
749 size_t size;
750
751 /**
752 * Offset in the node struct for the parent pointer.
753 */
754 ptrdiff_t loc_parent;
755
756 /**
757 * Offset in the node struct for the children linked list.
758 */
759 ptrdiff_t loc_children;
760
761 /**
762 * Optional offset in the node struct for the pointer to the last child
763 * in the linked list (negative if there is no such pointer).
764 */
765 ptrdiff_t loc_last_child;
766
767 /**
768 * Offset in the node struct for the previous sibling pointer.
769 */
770 ptrdiff_t loc_prev;
771
772 /**
773 * Offset in the node struct for the next sibling pointer.
774 */
775 ptrdiff_t loc_next;
776 };
777
778 /**
779 * Macro to roll out the #cx_tree_node_base_s structure with a custom
780 * node type.
781 */
782 #define CX_TREE_NODE_BASE(type) \
783 type *parent; \
784 type *children;\
785 type *last_child;\
786 type *prev;\
787 type *next
788
789 /**
790 * Macro for specifying the layout of a base node tree.
791 */
792 #define cx_tree_node_base_layout \
793 offsetof(struct cx_tree_node_base_s, parent),\
794 offsetof(struct cx_tree_node_base_s, children),\
795 offsetof(struct cx_tree_node_base_s, last_child),\
796 offsetof(struct cx_tree_node_base_s, prev), \
797 offsetof(struct cx_tree_node_base_s, next)
798
799 /**
800 * Macro for obtaining the node pointer layout for a specific tree.
801 */
802 #define cx_tree_node_layout(tree) \
803 (tree)->loc_parent,\
804 (tree)->loc_children,\
805 (tree)->loc_last_child,\
806 (tree)->loc_prev, \
807 (tree)->loc_next
808
809 /**
810 * The class definition for arbitrary trees.
811 */
812 struct cx_tree_class_s {
813 /**
814 * Destructor function.
815 *
816 * Implementations SHALL invoke the node destructor functions if provided
817 * and SHALL deallocate the tree memory.
818 */
819 void (*destructor)(struct cx_tree_s *);
820
821 /**
822 * Member function for inserting a single element.
823 *
824 * Implementations SHALL NOT simply invoke \p insert_many as this comes
825 * with too much overhead.
826 */
827 int (*insert_element)(
828 struct cx_tree_s *tree,
829 const void *data
830 );
831
832 /**
833 * Member function for inserting multiple elements.
834 *
835 * Implementations SHALL avoid to perform a full search in the tree for
836 * every element even though the source data MAY be unsorted.
837 */
838 size_t (*insert_many)(
839 struct cx_tree_s *tree,
840 struct cx_iterator_base_s *iter,
841 size_t n
842 );
843
844 /**
845 * Member function for finding a node.
846 */
847 void *(*find)(
848 struct cx_tree_s *tree,
849 const void *subtree,
850 const void *data
851 );
852
853 /**
854 * Member function for creating an iterator for the tree.
855 */
856 CxTreeIterator (*iterator)(
857 struct cx_tree_s *tree,
858 bool visit_on_exit
859 );
860
861 /**
862 * Member function for creating a visitor for the tree.
863 */
864 CxTreeVisitor (*visitor)(struct cx_tree_s *tree);
865 };
866
867 /**
868 * Common type for all tree implementations.
869 */
870 typedef struct cx_tree_s CxTree;
871
872 /**
873 * Creates a new tree structure based on the specified layout.
874 *
875 * The specified \p allocator will be used for creating the tree struct
876 * and SHALL be used by \p create_func to allocate memory for the nodes.
877 *
878 * \note This function will also register an advanced destructor which
879 * will free the nodes with the allocator's free() method.
880 *
881 * @param allocator the allocator that shall be used
882 * @param create_func a function that creates new nodes
883 * @param search_func a function that compares two nodes
884 * @param search_data_func a function that compares a node with data
885 * @param loc_parent offset in the node struct for the parent pointer
886 * @param loc_children offset in the node struct for the children linked list
887 * @param loc_last_child optional offset in the node struct for the pointer to
888 * the last child in the linked list (negative if there is no such pointer)
889 * @param loc_prev offset in the node struct for the prev pointer
890 * @param loc_next offset in the node struct for the next pointer
891 * @return the new tree
892 * @see cxTreeCreateSimple()
893 * @see cxTreeCreateWrapped()
894 */
895 __attribute__((__nonnull__, __warn_unused_result__))
896 CxTree *cxTreeCreate(
897 const CxAllocator *allocator,
898 cx_tree_node_create_func create_func,
899 cx_tree_search_func search_func,
900 cx_tree_search_data_func search_data_func,
901 ptrdiff_t loc_parent,
902 ptrdiff_t loc_children,
903 ptrdiff_t loc_last_child,
904 ptrdiff_t loc_prev,
905 ptrdiff_t loc_next
906 );
907
908 /**
909 * Creates a new tree structure based on a default layout.
910 *
911 * Nodes created by \p create_func MUST contain #cx_tree_node_base_s as first
912 * member (or at least respect the default offsets specified in the tree
913 * struct) and they MUST be allocated with the specified allocator.
914 *
915 * \note This function will also register an advanced destructor which
916 * will free the nodes with the allocator's free() method.
917 *
918 * @param allocator the allocator that shall be used
919 * @param create_func a function that creates new nodes
920 * @param search_func a function that compares two nodes
921 * @param search_data_func a function that compares a node with data
922 * @return the new tree
923 * @see cxTreeCreate()
924 */
925 __attribute__((__nonnull__, __warn_unused_result__))
926 static inline CxTree *cxTreeCreateSimple(
927 const CxAllocator *allocator,
928 cx_tree_node_create_func create_func,
929 cx_tree_search_func search_func,
930 cx_tree_search_data_func search_data_func
931 ) {
932 return cxTreeCreate(
933 allocator,
934 create_func,
935 search_func,
936 search_data_func,
937 cx_tree_node_base_layout
938 );
939 }
940
941 /**
942 * Creates a new tree structure based on an existing tree.
943 *
944 * The specified \p allocator will be used for creating the tree struct.
945 *
946 * \attention This function will create an incompletely defined tree structure
947 * where neither the create function, the search function, nor a destructor
948 * will be set. If you wish to use any of this functionality for the wrapped
949 * tree, you need to specify those functions afterwards.
950 *
951 * @param root the root node of the tree that shall be wrapped
952 * @param loc_parent offset in the node struct for the parent pointer
953 * @param loc_children offset in the node struct for the children linked list
954 * @param loc_last_child optional offset in the node struct for the pointer to
955 * the last child in the linked list (negative if there is no such pointer)
956 * @param loc_prev offset in the node struct for the prev pointer
957 * @param loc_next offset in the node struct for the next pointer
958 * @return the new tree
959 * @see cxTreeCreate()
960 */
961 __attribute__((__nonnull__, __warn_unused_result__))
962 CxTree *cxTreeCreateWrapped(
963 const CxAllocator *allocator,
964 void *root,
965 ptrdiff_t loc_parent,
966 ptrdiff_t loc_children,
967 ptrdiff_t loc_last_child,
968 ptrdiff_t loc_prev,
969 ptrdiff_t loc_next
970 );
971
972 /**
973 * Destroys the tree structure.
974 *
975 * \attention This function will only invoke the destructor functions
976 * on the nodes, if specified.
977 * It will NOT additionally free the nodes with the tree's allocator, because
978 * that would cause a double-free in most scenarios.
979 *
980 * @param tree the tree to destroy
981 */
982 __attribute__((__nonnull__))
983 static inline void cxTreeDestroy(CxTree *tree) {
984 tree->cl->destructor(tree);
985 }
986
987 /**
988 * Inserts data into the tree.
989 *
990 * \remark For this function to work, the tree needs specified search and
991 * create functions, which might not be available for wrapped trees
992 * (see #cxTreeCreateWrapped()).
993 *
994 * @param tree the tree
995 * @param data the data to insert
996 * @return zero on success, non-zero on failure
997 */
998 __attribute__((__nonnull__))
999 static inline int cxTreeInsert(
1000 CxTree *tree,
1001 const void *data
1002 ) {
1003 return tree->cl->insert_element(tree, data);
1004 }
1005
1006 /**
1007 * Inserts elements provided by an iterator efficiently into the tree.
1008 *
1009 * \remark For this function to work, the tree needs specified search and
1010 * create functions, which might not be available for wrapped trees
1011 * (see #cxTreeCreateWrapped()).
1012 *
1013 * @param tree the tree
1014 * @param iter the iterator providing the elements
1015 * @param n the maximum number of elements to insert
1016 * @return the number of elements that could be successfully inserted
1017 */
1018 __attribute__((__nonnull__))
1019 static inline size_t cxTreeInsertIter(
1020 CxTree *tree,
1021 struct cx_iterator_base_s *iter,
1022 size_t n
1023 ) {
1024 return tree->cl->insert_many(tree, iter, n);
1025 }
1026
1027 /**
1028 * Inserts an array of data efficiently into the tree.
1029 *
1030 * \remark For this function to work, the tree needs specified search and
1031 * create functions, which might not be available for wrapped trees
1032 * (see #cxTreeCreateWrapped()).
1033 *
1034 * @param tree the tree
1035 * @param data the array of data to insert
1036 * @param elem_size the size of each element in the array
1037 * @param n the number of elements in the array
1038 * @return the number of elements that could be successfully inserted
1039 */
1040 __attribute__((__nonnull__))
1041 static inline size_t cxTreeInsertArray(
1042 CxTree *tree,
1043 const void *data,
1044 size_t elem_size,
1045 size_t n
1046 ) {
1047 if (n == 0) return 0;
1048 if (n == 1) return 0 == cxTreeInsert(tree, data) ? 1 : 0;
1049 CxIterator iter = cxIterator(data, elem_size, n);
1050 return cxTreeInsertIter(tree, cxIteratorRef(iter), n);
1051 }
1052
1053 /**
1054 * Searches the data in the specified tree.
1055 *
1056 * \remark For this function to work, the tree needs a specified \c search_data
1057 * function, which might not be available wrapped trees
1058 * (see #cxTreeCreateWrapped()).
1059 *
1060 * @param tree the tree
1061 * @param data the data to search for
1062 * @return the first matching node, or \c NULL when the data cannot be found
1063 */
1064 __attribute__((__nonnull__))
1065 static inline void *cxTreeFind(
1066 CxTree *tree,
1067 const void *data
1068 ) {
1069 return tree->cl->find(tree, tree->root, data);
1070 }
1071
1072 /**
1073 * Searches the data in the specified subtree.
1074 *
1075 * \note When \p subtree_root is not part of the \p tree, the behavior is
1076 * undefined.
1077 *
1078 * \remark For this function to work, the tree needs a specified \c search_data
1079 * function, which might not be the case for wrapped trees
1080 * (see #cxTreeCreateWrapped()).
1081 *
1082 * @param tree the tree
1083 * @param data the data to search for
1084 * @param subtree_root the node where to start
1085 * @return the first matching node, or \c NULL when the data cannot be found
1086 */
1087 __attribute__((__nonnull__))
1088 static inline void *cxTreeFindInSubtree(
1089 CxTree *tree,
1090 const void *data,
1091 void *subtree_root
1092 ) {
1093 return tree->cl->find(tree, subtree_root, data);
1094 }
1095
1096 /**
1097 * Determines the size of the specified subtree.
1098 *
1099 * @param tree the tree
1100 * @param subtree_root the root node of the subtree
1101 * @return the number of nodes in the specified subtree
1102 */
1103 __attribute__((__nonnull__))
1104 size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root);
1105
1106 /**
1107 * Determines the depth of the specified subtree.
1108 *
1109 * @param tree the tree
1110 * @param subtree_root the root node of the subtree
1111 * @return the tree depth including the \p subtree_root
1112 */
1113 __attribute__((__nonnull__))
1114 size_t cxTreeSubtreeDepth(CxTree *tree, void *subtree_root);
1115
1116 /**
1117 * Determines the depth of the entire tree.
1118 *
1119 * @param tree the tree
1120 * @return the tree depth, counting the root as one
1121 */
1122 __attribute__((__nonnull__))
1123 size_t cxTreeDepth(CxTree *tree);
1124
1125 /**
1126 * Creates a depth-first iterator for the specified tree.
1127 *
1128 * @param tree the tree to iterate
1129 * @param visit_on_exit true, if the iterator shall visit a node again when
1130 * leaving the sub-tree
1131 * @return a tree iterator (depth-first)
1132 * @see cxTreeVisitor()
1133 */
1134 __attribute__((__nonnull__, __warn_unused_result__))
1135 static inline CxTreeIterator cxTreeIterator(
1136 CxTree *tree,
1137 bool visit_on_exit
1138 ) {
1139 return tree->cl->iterator(tree, visit_on_exit);
1140 }
1141
1142 /**
1143 * Creates a breadth-first iterator for the specified tree.
1144 *
1145 * @param tree the tree to iterate
1146 * @return a tree visitor (a.k.a. breadth-first iterator)
1147 * @see cxTreeIterator()
1148 */
1149 __attribute__((__nonnull__, __warn_unused_result__))
1150 static inline CxTreeVisitor cxTreeVisitor(CxTree *tree) {
1151 return tree->cl->visitor(tree);
1152 }
1153
1154 /**
1155 * Adds a new node to the tree.
1156 *
1157 * \attention The node may be externally created, but MUST obey the same rules
1158 * as if it was created by the tree itself with #cxTreeAddChild() (e.g. use
1159 * the same allocator).
1160 *
1161 * @param tree the tree
1162 * @param parent the parent of the node to add
1163 * @param child the node to add
1164 */
1165 __attribute__((__nonnull__))
1166 static inline void cxTreeAddChildNode(
1167 CxTree *tree,
1168 void *parent,
1169 void *child) {
1170 cx_tree_link(parent, child, cx_tree_node_layout(tree));
1171 tree->size++;
1172 }
1173
1174 /**
1175 * Creates a new node and adds it to the tree.
1176 *
1177 * With this function you can decide where exactly the new node shall be added.
1178 * If you specified an appropriate search function, you may want to consider
1179 * leaving this task to the tree by using #cxTreeInsert().
1180 *
1181 * Be aware that adding nodes at arbitrary locations in the tree might cause
1182 * wrong or undesired results when subsequently invoking #cxTreeInsert() and
1183 * the invariant imposed by the search function does not hold any longer.
1184 *
1185 * @param tree the tree
1186 * @param parent the parent node of the new node
1187 * @param data the data that will be submitted to the create function
1188 * @return zero when the new node was created, non-zero on allocation failure
1189 * @see cxTreeInsert()
1190 */
1191 __attribute__((__nonnull__))
1192 int cxTreeAddChild(
1193 CxTree *tree,
1194 void *parent,
1195 const void *data
1196 );
1197
1198 /**
1199 * A function that is invoked when a node needs to be re-linked to a new parent.
1200 *
1201 * When a node is re-linked, sometimes the contents need to be updated.
1202 * This callback is invoked by #cxTreeRemove() so that those updates can be
1203 * applied when re-linking the children of the removed node.
1204 *
1205 * @param node the affected node
1206 * @param old_parent the old parent of the node
1207 * @param new_parent the new parent of the node
1208 */
1209 typedef void (*cx_tree_relink_func)(
1210 void *node,
1211 const void *old_parent,
1212 const void *new_parent
1213 );
1214
1215 /**
1216 * Removes a node and re-links its children to its former parent.
1217 *
1218 * If the node is not part of the tree, the behavior is undefined.
1219 *
1220 * \note The destructor function, if any, will \em not be invoked. That means
1221 * you will need to free the removed node by yourself, eventually.
1222 *
1223 * @param tree the tree
1224 * @param node the node to remove (must not be the root node)
1225 * @param relink_func optional callback to update the content of each re-linked
1226 * node
1227 * @return zero on success, non-zero if \p node is the root node of the tree
1228 */
1229 __attribute__((__nonnull__(1,2)))
1230 int cxTreeRemove(
1231 CxTree *tree,
1232 void *node,
1233 cx_tree_relink_func relink_func
1234 );
1235
1236 /**
1237 * Removes a node and it's subtree from the tree.
1238 *
1239 * If the node is not part of the tree, the behavior is undefined.
1240 *
1241 * \note The destructor function, if any, will \em not be invoked. That means
1242 * you will need to free the removed subtree by yourself, eventually.
1243 *
1244 * @param tree the tree
1245 * @param node the node to remove
1246 */
1247 __attribute__((__nonnull__))
1248 void cxTreeRemoveSubtree(CxTree *tree, void *node);
1249
1250 #ifdef __cplusplus
1251 } // extern "C"
1252 #endif
1253
1254 #endif //UCX_TREE_H
1255