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 /**
647 * The tree class definition.
648 */
649 const cx_tree_class *cl;
650
651 /**
652 * Allocator to allocate new nodes.
653 */
654 const CxAllocator *allocator;
655
656 /**
657 * A pointer to the root node.
658 *
659 * Will be @c NULL when @c size is 0.
660 */
661 void *root;
662
663 /**
664 * A function to create new nodes.
665 *
666 * Invocations to this function will receive a pointer to this tree
667 * structure as the second argument.
668 *
669 * Nodes MAY use #cx_tree_node_base_s as the base layout, but do not need to.
670 */
671 cx_tree_node_create_func node_create;
672
673 /**
674 * An optional simple destructor for the tree nodes.
675 */
676 cx_destructor_func simple_destructor;
677
678 /**
679 * An optional advanced destructor for the tree nodes.
680 */
681 cx_destructor_func2 advanced_destructor;
682
683 /**
684 * The pointer to additional data that is passed to the advanced destructor.
685 */
686 void *destructor_data;
687
688 /**
689 * A function to compare two nodes.
690 */
691 cx_tree_search_func search;
692
693 /**
694 * A function to compare a node with data.
695 */
696 cx_tree_search_data_func search_data;
697
698 /**
699 * The number of currently stored elements.
700 */
701 size_t size;
702
703 /**
704 * Offset in the node struct for the parent pointer.
705 */
706 ptrdiff_t loc_parent;
707
708 /**
709 * Offset in the node struct for the children linked list.
710 */
711 ptrdiff_t loc_children;
712
713 /**
714 * Optional offset in the node struct for the pointer to the last child
715 * in the linked list (negative if there is no such pointer).
716 */
717 ptrdiff_t loc_last_child;
718
719 /**
720 * Offset in the node struct for the previous sibling pointer.
721 */
722 ptrdiff_t loc_prev;
723
724 /**
725 * Offset in the node struct for the next sibling pointer.
726 */
727 ptrdiff_t loc_next;
728 };
729
730 /**
731 * Macro to roll out the #cx_tree_node_base_s structure with a custom
732 * node type.
733 *
734 * Must be used as the first member in your custom tree struct.
735 *
736 * @param type the data type for the nodes
737 */
738 #define CX_TREE_NODE_BASE(type) \
739 type *parent; \
740 type *children;\
741 type *last_child;\
742 type *prev;\
743 type *next
744
745 /**
746 * Macro for specifying the layout of a base node tree.
747 *
748 * When your tree uses #CX_TREE_NODE_BASE, you can use this
749 * macro in all tree functions that expect the layout parameters
750 * @c loc_parent, @c loc_children, @c loc_last_child, @c loc_prev,
751 * and @c loc_next.
752 */
753 #define cx_tree_node_base_layout \
754 offsetof(struct cx_tree_node_base_s, parent),\
755 offsetof(struct cx_tree_node_base_s, children),\
756 offsetof(struct cx_tree_node_base_s, last_child),\
757 offsetof(struct cx_tree_node_base_s, prev), \
758 offsetof(struct cx_tree_node_base_s, next)
759
760 /**
761 * The class definition for arbitrary trees.
762 */
763 struct cx_tree_class_s {
764 /**
765 * Member function for inserting a single element.
766 *
767 * Implementations SHALL NOT simply invoke @p insert_many as this comes
768 * with too much overhead.
769 */
770 int (*insert_element)(struct cx_tree_s *tree, const void *data);
771
772 /**
773 * Member function for inserting multiple elements.
774 *
775 * Implementations SHALL avoid performing a full search in the tree for
776 * every element even though the source data MAY be unsorted.
777 */
778 size_t (*insert_many)(struct cx_tree_s *tree, struct cx_iterator_base_s *iter, size_t n);
779
780 /**
781 * Member function for finding a node.
782 */
783 void *(*find)(struct cx_tree_s *tree, const void *subtree, const void *data, size_t depth);
784 };
785
786 /**
787 * Common type for all tree implementations.
788 */
789 typedef struct cx_tree_s CxTree;
790
791
792 /**
793 * Destroys a node and its subtree.
794 *
795 * It is guaranteed that the simple destructor is invoked before
796 * the advanced destructor, starting with the leaf nodes of the subtree.
797 *
798 * When this function is invoked on the root node of the tree, it destroys the
799 * tree contents, but - in contrast to #cxTreeFree() - not the tree
800 * structure, leaving an empty tree behind.
801 *
802 * @note The destructor function, if any, will @em not be invoked. That means
803 * you will need to free the removed subtree by yourself, eventually.
804 *
805 * @attention This function will not free the memory of the nodes with the
806 * tree's allocator, because that is usually done by the advanced destructor
807 * and would therefore result in a double-free.
808 *
809 * @param tree the tree
810 * @param node the node to remove
811 * @see cxTreeFree()
812 */
813 cx_attr_nonnull
814 CX_EXPORT void cxTreeDestroySubtree(CxTree *tree, void *node);
815
816
817 /**
818 * Destroys the tree contents.
819 *
820 * It is guaranteed that the simple destructor is invoked before
821 * the advanced destructor, starting with the leaf nodes of the subtree.
822 *
823 * This is a convenience macro for invoking #cxTreeDestroySubtree() on the
824 * root node of the tree.
825 *
826 * @attention Be careful when calling this function when no destructor function
827 * is registered that actually frees the memory of nodes. In that case you will
828 * need a reference to the (former) root node of the tree somewhere, or
829 * otherwise you will be leaking memory.
830 *
831 * @param tree the tree
832 * @see cxTreeDestroySubtree()
833 */
834 #define cxTreeClear(tree) cxTreeDestroySubtree(tree, tree->root)
835
836 /**
837 * Deallocates the tree structure.
838 *
839 * The destructor functions are invoked for each node, starting with the leaf
840 * nodes.
841 * It is guaranteed that for each node the simple destructor is invoked before
842 * the advanced destructor.
843 *
844 * @attention This function will only invoke the destructor functions
845 * on the nodes.
846 * It will NOT additionally free the nodes with the tree's allocator, because
847 * that would cause a double-free in most scenarios where the advanced
848 * destructor is already freeing the memory.
849 *
850 * @param tree the tree to free
851 */
852 CX_EXPORT void cxTreeFree(CxTree *tree);
853
854 /**
855 * Creates a new tree structure based on the specified layout.
856 *
857 * The specified @p allocator will be used for creating the tree struct
858 * and SHALL be used by @p create_func to allocate memory for the nodes.
859 *
860 * @note This function will also register an advanced destructor which
861 * will free the nodes with the allocator's free() method.
862 *
863 * @param allocator the allocator that shall be used
864 * (if @c NULL, the cxDefaultAllocator will be used)
865 * @param create_func a function that creates new nodes
866 * @param search_func a function that compares two nodes
867 * @param search_data_func a function that compares a node with data
868 * @param loc_parent offset in the node struct for the parent pointer
869 * @param loc_children offset in the node struct for the children linked list
870 * @param loc_last_child optional offset in the node struct for the pointer to
871 * the last child in the linked list (negative if there is no such pointer)
872 * @param loc_prev optional offset in the node struct for the prev pointer
873 * @param loc_next offset in the node struct for the next pointer
874 * @return the new tree
875 * @see cxTreeCreateSimple()
876 * @see cxTreeCreateWrapped()
877 */
878 cx_attr_nonnull_arg(2, 3, 4) cx_attr_nodiscard cx_attr_malloc cx_attr_dealloc(cxTreeFree, 1)
879 CX_EXPORT CxTree *cxTreeCreate(const CxAllocator *allocator, cx_tree_node_create_func create_func,
880 cx_tree_search_func search_func, cx_tree_search_data_func search_data_func,
881 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
882 ptrdiff_t loc_prev, ptrdiff_t loc_next);
883
884 /**
885 * Creates a new tree structure based on a default layout.
886 *
887 * Nodes created by @p create_func MUST contain #cx_tree_node_base_s as the first
888 * member (or at least respect the default offsets specified in the tree
889 * struct), and they MUST be allocated with the specified allocator.
890 *
891 * @note This function will also register an advanced destructor which
892 * will free the nodes with the allocator's free() method.
893 *
894 * @param allocator (@c CxAllocator*) the allocator that shall be used
895 * @param create_func (@c cx_tree_node_create_func) a function that creates new nodes
896 * @param search_func (@c cx_tree_search_func) a function that compares two nodes
897 * @param search_data_func (@c cx_tree_search_data_func) a function that compares a node with data
898 * @return (@c CxTree*) the new tree
899 * @see cxTreeCreate()
900 */
901 #define cxTreeCreateSimple(allocator, create_func, search_func, search_data_func) \
902 cxTreeCreate(allocator, create_func, search_func, search_data_func, cx_tree_node_base_layout)
903
904 /**
905 * Creates a new tree structure based on an existing tree.
906 *
907 * The specified @p allocator will be used for creating the tree struct.
908 *
909 * @attention This function will create an incompletely defined tree structure
910 * where neither the create function, the search function, nor a destructor
911 * will be set. If you wish to use any of this functionality for the wrapped
912 * tree, you need to specify those functions afterward.
913 *
914 * @param allocator the allocator that was used for nodes of the wrapped tree
915 * (if @c NULL, the cxDefaultAllocator is assumed)
916 * @param root the root node of the tree that shall be wrapped
917 * @param loc_parent offset in the node struct for the parent pointer
918 * @param loc_children offset in the node struct for the children linked list
919 * @param loc_last_child optional offset in the node struct for the pointer to
920 * the last child in the linked list (negative if there is no such pointer)
921 * @param loc_prev optional offset in the node struct for the prev pointer
922 * @param loc_next offset in the node struct for the next pointer
923 * @return the new tree
924 * @see cxTreeCreate()
925 */
926 cx_attr_nonnull_arg(2) cx_attr_nodiscard cx_attr_malloc cx_attr_dealloc(cxTreeFree, 1)
927 CX_EXPORT CxTree *cxTreeCreateWrapped(const CxAllocator *allocator, void *root,
928 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
929 ptrdiff_t loc_prev, ptrdiff_t loc_next);
930
931 /**
932 * Inserts data into the tree.
933 *
934 * @remark For this function to work, the tree needs specified search and
935 * create functions, which might not be available for wrapped trees
936 * (see #cxTreeCreateWrapped()).
937 *
938 * @param tree the tree
939 * @param data the data to insert
940 * @retval zero success
941 * @retval non-zero failure
942 */
943 cx_attr_nonnull
944 CX_EXPORT int cxTreeInsert(CxTree *tree, const void *data);
945
946 /**
947 * Inserts elements provided by an iterator efficiently into the tree.
948 *
949 * @remark For this function to work, the tree needs specified search and
950 * create functions, which might not be available for wrapped trees
951 * (see #cxTreeCreateWrapped()).
952 *
953 * @param tree the tree
954 * @param iter the iterator providing the elements
955 * @param n the maximum number of elements to insert
956 * @return the number of elements that could be successfully inserted
957 */
958 cx_attr_nonnull
959 CX_EXPORT size_t cxTreeInsertIter(CxTree *tree, CxIteratorBase *iter, size_t n);
960
961 /**
962 * Inserts an array of data efficiently into the tree.
963 *
964 * @remark For this function to work, the tree needs specified search and
965 * create functions, which might not be available for wrapped trees
966 * (see #cxTreeCreateWrapped()).
967 *
968 * @param tree the tree
969 * @param data the array of data to insert
970 * @param elem_size the size of each element in the array
971 * @param n the number of elements in the array
972 * @return the number of elements that could be successfully inserted
973 */
974 cx_attr_nonnull
975 CX_EXPORT size_t cxTreeInsertArray(CxTree *tree, const void *data, size_t elem_size, size_t n);
976
977 /**
978 * Searches the data in the specified tree.
979 *
980 * @remark For this function to work, the tree needs a specified @c search_data
981 * function, which might not be available wrapped trees
982 * (see #cxTreeCreateWrapped()).
983 *
984 * @param tree the tree
985 * @param data the data to search for
986 * @return the first matching node, or @c NULL when the data cannot be found
987 */
988 cx_attr_nonnull cx_attr_nodiscard
989 CX_EXPORT void *cxTreeFind(CxTree *tree, const void *data);
990
991 /**
992 * Searches the data in the specified subtree.
993 *
994 * When @p max_depth is zero, the depth is not limited.
995 * The @p subtree_root itself is on depth 1 and its children have depth 2.
996 *
997 * @note When @p subtree_root is not part of the @p tree, the behavior is
998 * undefined.
999 *
1000 * @remark For this function to work, the tree needs a specified @c search_data
1001 * function, which might not be the case for wrapped trees
1002 * (see #cxTreeCreateWrapped()).
1003 *
1004 * @param tree the tree
1005 * @param data the data to search for
1006 * @param subtree_root the node where to start
1007 * @param max_depth the maximum search depth
1008 * @return the first matching node, or @c NULL when the data cannot be found
1009 */
1010 cx_attr_nonnull cx_attr_nodiscard
1011 CX_EXPORT void *cxTreeFindInSubtree(CxTree *tree, const void *data, void *subtree_root, size_t max_depth);
1012
1013 /**
1014 * Determines the size of the specified subtree.
1015 *
1016 * @param tree the tree
1017 * @param subtree_root the root node of the subtree
1018 * @return the number of nodes in the specified subtree
1019 */
1020 cx_attr_nonnull cx_attr_nodiscard
1021 CX_EXPORT size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root);
1022
1023 /**
1024 * Determines the depth of the specified subtree.
1025 *
1026 * @param tree the tree
1027 * @param subtree_root the root node of the subtree
1028 * @return the tree depth including the @p subtree_root
1029 */
1030 cx_attr_nonnull cx_attr_nodiscard
1031 CX_EXPORT size_t cxTreeSubtreeDepth(CxTree *tree, void *subtree_root);
1032
1033 /**
1034 * Determines the size of the entire tree.
1035 *
1036 * @param tree the tree
1037 * @return the tree size, counting the root as one
1038 */
1039 cx_attr_nonnull cx_attr_nodiscard
1040 CX_EXPORT size_t cxTreeSize(CxTree *tree);
1041
1042 /**
1043 * Determines the depth of the entire tree.
1044 *
1045 * @param tree the tree
1046 * @return the tree depth, counting the root as one
1047 */
1048 cx_attr_nonnull cx_attr_nodiscard
1049 CX_EXPORT size_t cxTreeDepth(CxTree *tree);
1050
1051 /**
1052 * Creates a depth-first iterator for the specified tree starting in @p node.
1053 *
1054 * If the node is not part of the tree, the behavior is undefined.
1055 *
1056 * @param tree the tree to iterate
1057 * @param node the node where to start
1058 * @param visit_on_exit true, if the iterator shall visit a node again when
1059 * leaving the subtree
1060 * @return a tree iterator (depth-first)
1061 * @see cxTreeVisit()
1062 */
1063 cx_attr_nonnull cx_attr_nodiscard
1064 CX_EXPORT CxTreeIterator cxTreeIterateSubtree(CxTree *tree, void *node, bool visit_on_exit);
1065
1066 /**
1067 * Creates a breadth-first iterator for the specified tree starting in @p node.
1068 *
1069 * If the node is not part of the tree, the behavior is undefined.
1070 *
1071 * @param tree the tree to iterate
1072 * @param node the node where to start
1073 * @return a tree visitor (a.k.a. breadth-first iterator)
1074 * @see cxTreeIterate()
1075 */
1076 cx_attr_nonnull cx_attr_nodiscard
1077 CX_EXPORT CxTreeVisitor cxTreeVisitSubtree(CxTree *tree, void *node);
1078
1079 /**
1080 * Creates a depth-first iterator for the specified tree.
1081 *
1082 * @param tree the tree to iterate
1083 * @param visit_on_exit true, if the iterator shall visit a node again when
1084 * leaving the subtree
1085 * @return a tree iterator (depth-first)
1086 * @see cxTreeVisit()
1087 */
1088 cx_attr_nonnull cx_attr_nodiscard
1089 CX_EXPORT CxTreeIterator cxTreeIterate(CxTree *tree, bool visit_on_exit);
1090
1091 /**
1092 * Creates a breadth-first iterator for the specified tree.
1093 *
1094 * @param tree the tree to iterate
1095 * @return a tree visitor (a.k.a. breadth-first iterator)
1096 * @see cxTreeIterate()
1097 */
1098 cx_attr_nonnull cx_attr_nodiscard
1099 CX_EXPORT CxTreeVisitor cxTreeVisit(CxTree *tree);
1100
1101 /**
1102 * Sets the (new) parent of the specified child.
1103 *
1104 * If the @p child is not already a member of the tree, this function behaves
1105 * as #cxTreeAddChildNode().
1106 *
1107 * @param tree the tree
1108 * @param parent the (new) parent of the child
1109 * @param child the node to add
1110 * @see cxTreeAddChildNode()
1111 */
1112 cx_attr_nonnull
1113 CX_EXPORT void cxTreeSetParent(CxTree *tree, void *parent, void *child);
1114
1115 /**
1116 * Adds a new node to the tree.
1117 *
1118 * If the @p child is already a member of the tree, the behavior is undefined.
1119 * Use #cxTreeSetParent() if you want to move a subtree to another location.
1120 *
1121 * @attention The node may be externally created, but MUST obey the same rules
1122 * as if it was created by the tree itself with #cxTreeAddChild() (e.g., use
1123 * the same allocator).
1124 *
1125 * @param tree the tree
1126 * @param parent the parent of the node to add
1127 * @param child the node to add
1128 * @see cxTreeSetParent()
1129 */
1130 cx_attr_nonnull
1131 CX_EXPORT void cxTreeAddChildNode(CxTree *tree, void *parent, void *child);
1132
1133 /**
1134 * Creates a new node and adds it to the tree.
1135 *
1136 * With this function you can decide where exactly the new node shall be added.
1137 * If you specified an appropriate search function, you may want to consider
1138 * leaving this task to the tree by using #cxTreeInsert().
1139 *
1140 * Be aware that adding nodes at arbitrary locations in the tree might cause
1141 * wrong or undesired results when subsequently invoking #cxTreeInsert(), and
1142 * the invariant imposed by the search function does not hold any longer.
1143 *
1144 * @param tree the tree
1145 * @param parent the parent node of the new node
1146 * @param data the data that will be submitted to the create function
1147 * @return zero when the new node was created, non-zero on allocation failure
1148 * @see cxTreeInsert()
1149 */
1150 cx_attr_nonnull
1151 CX_EXPORT int cxTreeAddChild(CxTree *tree, void *parent, const void *data);
1152
1153 /**
1154 * A function that is invoked when a node needs to be re-linked to a new parent.
1155 *
1156 * When a node is re-linked, sometimes the contents need to be updated.
1157 * This callback is invoked by #cxTreeRemoveNode() and #cxTreeDestroyNode()
1158 * so that those updates can be applied when re-linking the children of the
1159 * removed node.
1160 *
1161 * @param node the affected node
1162 * @param old_parent the old parent of the node
1163 * @param new_parent the new parent of the node
1164 */
1165 typedef void (*cx_tree_relink_func)(
1166 void *node,
1167 const void *old_parent,
1168 const void *new_parent
1169 );
1170
1171 /**
1172 * Removes a node and re-links its children to its former parent.
1173 *
1174 * If the node is not part of the tree, the behavior is undefined.
1175 *
1176 * @note The destructor function, if any, will @em not be invoked. That means
1177 * you will need to free the removed node by yourself, eventually.
1178 *
1179 * @param tree the tree
1180 * @param node the node to remove (must not be the root node)
1181 * @param relink_func optional callback to update the content of each re-linked
1182 * node
1183 * @return zero on success, non-zero if @p node is the root node of the tree
1184 */
1185 cx_attr_nonnull_arg(1, 2)
1186 CX_EXPORT int cxTreeRemoveNode(CxTree *tree, void *node, cx_tree_relink_func relink_func);
1187
1188 /**
1189 * Removes a node and its subtree from the tree.
1190 *
1191 * If the node is not part of the tree, the behavior is undefined.
1192 *
1193 * @note The destructor function, if any, will @em not be invoked. That means
1194 * you will need to free the removed subtree by yourself, eventually.
1195 *
1196 * @param tree the tree
1197 * @param node the node to remove
1198 */
1199 cx_attr_nonnull
1200 CX_EXPORT void cxTreeRemoveSubtree(CxTree *tree, void *node);
1201
1202 /**
1203 * Destroys a node and re-links its children to its former parent.
1204 *
1205 * If the node is not part of the tree, the behavior is undefined.
1206 *
1207 * It is guaranteed that the simple destructor is invoked before
1208 * the advanced destructor.
1209 *
1210 * @attention This function will not free the memory of the node with the
1211 * tree's allocator, because that is usually done by the advanced destructor
1212 * and would therefore result in a double-free.
1213 *
1214 * @param tree the tree
1215 * @param node the node to destroy (must not be the root node)
1216 * @param relink_func optional callback to update the content of each re-linked
1217 * node
1218 * @return zero on success, non-zero if @p node is the root node of the tree
1219 */
1220 cx_attr_nonnull_arg(1, 2)
1221 CX_EXPORT int cxTreeDestroyNode(CxTree *tree, void *node, cx_tree_relink_func relink_func);
1222
1223 #ifdef __cplusplus
1224 } // extern "C"
1225 #endif
1226
1227 #endif //UCX_TREE_H
1228