GCC Code Coverage Report

Line	Branch	Exec	Source
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		109	static inline void cxTreeIteratorDispose(CxTreeIterator *iter) {
214		109	free(iter->stack);
215		109	iter->stack = NULL;
216		109	}
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
1429