Mercurial > hg > webserver / file comparison

comparison: src/ucx/cx/tree.h

src/ucx/cx/tree.h

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

Mercurial Repository: webserver

mercurial