--- a/src/cx/tree.h Thu Nov 07 20:22:56 2024 +0100
+++ b/src/cx/tree.h Thu Nov 07 22:46:58 2024 +0100
@@ -209,7 +209,7 @@
* Releases internal memory of the given tree iterator.
* @param iter the iterator
*/
- __attribute__((__nonnull__))
+cx_attr_nonnull
static inline void cxTreeIteratorDispose(CxTreeIterator *iter) {
free(iter->stack);
iter->stack = NULL;
@@ -219,7 +219,7 @@
* Releases internal memory of the given tree visitor.
* @param visitor the visitor
*/
-__attribute__((__nonnull__))
+cx_attr_nonnull
static inline void cxTreeVisitorDispose(CxTreeVisitor *visitor) {
struct cx_tree_visitor_queue_s *q = visitor->queue_next;
while (q != NULL) {
@@ -262,7 +262,7 @@
* @param loc_next offset in the node struct for the next pointer
* @see cx_tree_unlink()
*/
-__attribute__((__nonnull__))
+cx_attr_nonnull
void cx_tree_link(
void *restrict parent,
void *restrict node,
@@ -287,7 +287,7 @@
* @param loc_next offset in the node struct for the next pointer
* @see cx_tree_link()
*/
-__attribute__((__nonnull__))
+cx_attr_nonnull
void cx_tree_unlink(
void *node,
ptrdiff_t loc_parent,
@@ -328,6 +328,7 @@
* positive if one of the children might contain the data,
* negative if neither the node, nor the children contains the data
*/
+cx_attr_nonnull
typedef int (*cx_tree_search_data_func)(const void *node, const void *data);
@@ -357,6 +358,7 @@
* positive if one of the children might contain the data,
* negative if neither the node, nor the children contains the data
*/
+cx_attr_nonnull
typedef int (*cx_tree_search_func)(const void *node, const void *new_node);
/**
@@ -383,7 +385,8 @@
* could contain the node (but doesn't right now), negative if the tree does not
* contain any node that might be related to the searched data
*/
-__attribute__((__nonnull__))
+cx_attr_nonnull
+cx_attr_access_w(5)
int cx_tree_search_data(
const void *root,
size_t depth,
@@ -418,7 +421,8 @@
* could contain the node (but doesn't right now), negative if the tree does not
* contain any node that might be related to the searched data
*/
-__attribute__((__nonnull__))
+cx_attr_nonnull
+cx_attr_access_w(5)
int cx_tree_search(
const void *root,
size_t depth,
@@ -449,6 +453,7 @@
* @return the new tree iterator
* @see cxTreeIteratorDispose()
*/
+cx_attr_nodiscard
CxTreeIterator cx_tree_iterator(
void *root,
bool visit_on_exit,
@@ -474,6 +479,7 @@
* @return the new tree visitor
* @see cxTreeVisitorDispose()
*/
+cx_attr_nodiscard
CxTreeVisitor cx_tree_visitor(
void *root,
ptrdiff_t loc_children,
@@ -490,6 +496,7 @@
* \note the function may leave the node pointers in the struct uninitialized.
* The caller is responsible to set them according to the intended use case.
*/
+cx_attr_nonnull_arg(1)
typedef void *(*cx_tree_node_create_func)(const void *, void *);
/**
@@ -538,7 +545,8 @@
* @return the number of nodes created and added
* @see cx_tree_add()
*/
-__attribute__((__nonnull__(1, 3, 4, 6, 7)))
+cx_attr_nonnull_arg(1, 3, 4, 6, 7)
+cx_attr_access_w(6)
size_t cx_tree_add_iter(
struct cx_iterator_base_s *iter,
size_t num,
@@ -591,7 +599,8 @@
* @return the number of array elements successfully processed
* @see cx_tree_add()
*/
-__attribute__((__nonnull__(1, 4, 5, 7, 8)))
+cx_attr_nonnull_arg(1, 4, 5, 7, 8)
+cx_attr_access_w(7)
size_t cx_tree_add_array(
const void *src,
size_t num,
@@ -653,7 +662,8 @@
* @return zero when a new node was created and added to the tree,
* non-zero otherwise
*/
-__attribute__((__nonnull__(1, 2, 3, 5, 6)))
+cx_attr_nonnull_arg(1, 2, 3, 5, 6)
+cx_attr_access_w(5)
int cx_tree_add(
const void *src,
cx_tree_search_func sfunc,
@@ -829,6 +839,7 @@
* Implementations SHALL NOT simply invoke \p insert_many as this comes
* with too much overhead.
*/
+ cx_attr_nonnull
int (*insert_element)(
struct cx_tree_s *tree,
const void *data
@@ -840,6 +851,7 @@
* Implementations SHALL avoid to perform a full search in the tree for
* every element even though the source data MAY be unsorted.
*/
+ cx_attr_nonnull
size_t (*insert_many)(
struct cx_tree_s *tree,
struct cx_iterator_base_s *iter,
@@ -849,6 +861,7 @@
/**
* Member function for finding a node.
*/
+ cx_attr_nonnull
void *(*find)(
struct cx_tree_s *tree,
const void *subtree,
@@ -862,461 +875,6 @@
*/
typedef struct cx_tree_s CxTree;
-/**
- * Creates a new tree structure based on the specified layout.
- *
- * The specified \p allocator will be used for creating the tree struct
- * and SHALL be used by \p create_func to allocate memory for the nodes.
- *
- * \note This function will also register an advanced destructor which
- * will free the nodes with the allocator's free() method.
- *
- * @param allocator the allocator that shall be used
- * @param create_func a function that creates new nodes
- * @param search_func a function that compares two nodes
- * @param search_data_func a function that compares a node with data
- * @param loc_parent offset in the node struct for the parent pointer
- * @param loc_children offset in the node struct for the children linked list
- * @param loc_last_child optional offset in the node struct for the pointer to
- * the last child in the linked list (negative if there is no such pointer)
- * @param loc_prev optional offset in the node struct for the prev pointer
- * @param loc_next offset in the node struct for the next pointer
- * @return the new tree
- * @see cxTreeCreateSimple()
- * @see cxTreeCreateWrapped()
- */
-__attribute__((__nonnull__, __warn_unused_result__))
-CxTree *cxTreeCreate(
- const CxAllocator *allocator,
- cx_tree_node_create_func create_func,
- cx_tree_search_func search_func,
- cx_tree_search_data_func search_data_func,
- ptrdiff_t loc_parent,
- ptrdiff_t loc_children,
- ptrdiff_t loc_last_child,
- ptrdiff_t loc_prev,
- ptrdiff_t loc_next
-);
-
-/**
- * Creates a new tree structure based on a default layout.
- *
- * Nodes created by \p create_func MUST contain #cx_tree_node_base_s as first
- * member (or at least respect the default offsets specified in the tree
- * struct) and they MUST be allocated with the specified allocator.
- *
- * \note This function will also register an advanced destructor which
- * will free the nodes with the allocator's free() method.
- *
- * @param allocator the allocator that shall be used
- * @param create_func a function that creates new nodes
- * @param search_func a function that compares two nodes
- * @param search_data_func a function that compares a node with data
- * @return the new tree
- * @see cxTreeCreate()
- */
-__attribute__((__nonnull__, __warn_unused_result__))
-static inline CxTree *cxTreeCreateSimple(
- const CxAllocator *allocator,
- cx_tree_node_create_func create_func,
- cx_tree_search_func search_func,
- cx_tree_search_data_func search_data_func
-) {
- return cxTreeCreate(
- allocator,
- create_func,
- search_func,
- search_data_func,
- cx_tree_node_base_layout
- );
-}
-
-/**
- * Creates a new tree structure based on an existing tree.
- *
- * The specified \p allocator will be used for creating the tree struct.
- *
- * \attention This function will create an incompletely defined tree structure
- * where neither the create function, the search function, nor a destructor
- * will be set. If you wish to use any of this functionality for the wrapped
- * tree, you need to specify those functions afterwards.
- *
- * @param allocator the allocator that was used for nodes of the wrapped tree
- * @param root the root node of the tree that shall be wrapped
- * @param loc_parent offset in the node struct for the parent pointer
- * @param loc_children offset in the node struct for the children linked list
- * @param loc_last_child optional offset in the node struct for the pointer to
- * the last child in the linked list (negative if there is no such pointer)
- * @param loc_prev optional offset in the node struct for the prev pointer
- * @param loc_next offset in the node struct for the next pointer
- * @return the new tree
- * @see cxTreeCreate()
- */
-__attribute__((__nonnull__, __warn_unused_result__))
-CxTree *cxTreeCreateWrapped(
- const CxAllocator *allocator,
- void *root,
- ptrdiff_t loc_parent,
- ptrdiff_t loc_children,
- ptrdiff_t loc_last_child,
- ptrdiff_t loc_prev,
- ptrdiff_t loc_next
-);
-
-/**
- * Inserts data into the tree.
- *
- * \remark For this function to work, the tree needs specified search and
- * create functions, which might not be available for wrapped trees
- * (see #cxTreeCreateWrapped()).
- *
- * @param tree the tree
- * @param data the data to insert
- * @return zero on success, non-zero on failure
- */
-__attribute__((__nonnull__))
-static inline int cxTreeInsert(
- CxTree *tree,
- const void *data
-) {
- return tree->cl->insert_element(tree, data);
-}
-
-/**
- * Inserts elements provided by an iterator efficiently into the tree.
- *
- * \remark For this function to work, the tree needs specified search and
- * create functions, which might not be available for wrapped trees
- * (see #cxTreeCreateWrapped()).
- *
- * @param tree the tree
- * @param iter the iterator providing the elements
- * @param n the maximum number of elements to insert
- * @return the number of elements that could be successfully inserted
- */
-__attribute__((__nonnull__))
-static inline size_t cxTreeInsertIter(
- CxTree *tree,
- struct cx_iterator_base_s *iter,
- size_t n
-) {
- return tree->cl->insert_many(tree, iter, n);
-}
-
-/**
- * Inserts an array of data efficiently into the tree.
- *
- * \remark For this function to work, the tree needs specified search and
- * create functions, which might not be available for wrapped trees
- * (see #cxTreeCreateWrapped()).
- *
- * @param tree the tree
- * @param data the array of data to insert
- * @param elem_size the size of each element in the array
- * @param n the number of elements in the array
- * @return the number of elements that could be successfully inserted
- */
-__attribute__((__nonnull__))
-static inline size_t cxTreeInsertArray(
- CxTree *tree,
- const void *data,
- size_t elem_size,
- size_t n
-) {
- if (n == 0) return 0;
- if (n == 1) return 0 == cxTreeInsert(tree, data) ? 1 : 0;
- CxIterator iter = cxIterator(data, elem_size, n);
- return cxTreeInsertIter(tree, cxIteratorRef(iter), n);
-}
-
-/**
- * Searches the data in the specified tree.
- *
- * \remark For this function to work, the tree needs a specified \c search_data
- * function, which might not be available wrapped trees
- * (see #cxTreeCreateWrapped()).
- *
- * @param tree the tree
- * @param data the data to search for
- * @return the first matching node, or \c NULL when the data cannot be found
- */
-__attribute__((__nonnull__))
-static inline void *cxTreeFind(
- CxTree *tree,
- const void *data
-) {
- return tree->cl->find(tree, tree->root, data, 0);
-}
-
-/**
- * Searches the data in the specified subtree.
- *
- * When \p max_depth is zero, the depth is not limited.
- * The \p subtree_root itself is on depth 1 and its children have depth 2.
- *
- * \note When \p subtree_root is not part of the \p tree, the behavior is
- * undefined.
- *
- * \remark For this function to work, the tree needs a specified \c search_data
- * function, which might not be the case for wrapped trees
- * (see #cxTreeCreateWrapped()).
- *
- * @param tree the tree
- * @param data the data to search for
- * @param subtree_root the node where to start
- * @param max_depth the maximum search depth
- * @return the first matching node, or \c NULL when the data cannot be found
- */
-__attribute__((__nonnull__))
-static inline void *cxTreeFindInSubtree(
- CxTree *tree,
- const void *data,
- void *subtree_root,
- size_t max_depth
-) {
- return tree->cl->find(tree, subtree_root, data, max_depth);
-}
-
-/**
- * Determines the size of the specified subtree.
- *
- * @param tree the tree
- * @param subtree_root the root node of the subtree
- * @return the number of nodes in the specified subtree
- */
-__attribute__((__nonnull__))
-size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root);
-
-/**
- * Determines the depth of the specified subtree.
- *
- * @param tree the tree
- * @param subtree_root the root node of the subtree
- * @return the tree depth including the \p subtree_root
- */
-__attribute__((__nonnull__))
-size_t cxTreeSubtreeDepth(CxTree *tree, void *subtree_root);
-
-/**
- * Determines the depth of the entire tree.
- *
- * @param tree the tree
- * @return the tree depth, counting the root as one
- */
-__attribute__((__nonnull__))
-size_t cxTreeDepth(CxTree *tree);
-
-/**
- * Creates a depth-first iterator for the specified tree starting in \p node.
- *
- * If the node is not part of the tree, the behavior is undefined.
- *
- * @param tree the tree to iterate
- * @param node the node where to start
- * @param visit_on_exit true, if the iterator shall visit a node again when
- * leaving the subtree
- * @return a tree iterator (depth-first)
- * @see cxTreeVisit()
- */
-__attribute__((__nonnull__, __warn_unused_result__))
-static inline CxTreeIterator cxTreeIterateSubtree(
- CxTree *tree,
- void *node,
- bool visit_on_exit
-) {
- return cx_tree_iterator(
- node, visit_on_exit,
- tree->loc_children, tree->loc_next
- );
-}
-
-/**
- * Creates a breadth-first iterator for the specified tree starting in \p node.
- *
- * If the node is not part of the tree, the behavior is undefined.
- *
- * @param tree the tree to iterate
- * @param node the node where to start
- * @return a tree visitor (a.k.a. breadth-first iterator)
- * @see cxTreeIterate()
- */
-__attribute__((__nonnull__, __warn_unused_result__))
-static inline CxTreeVisitor cxTreeVisitSubtree(CxTree *tree, void *node) {
- return cx_tree_visitor(
- node, tree->loc_children, tree->loc_next
- );
-}
-
-/**
- * Creates a depth-first iterator for the specified tree.
- *
- * @param tree the tree to iterate
- * @param visit_on_exit true, if the iterator shall visit a node again when
- * leaving the subtree
- * @return a tree iterator (depth-first)
- * @see cxTreeVisit()
- */
-__attribute__((__nonnull__, __warn_unused_result__))
-static inline CxTreeIterator cxTreeIterate(
- CxTree *tree,
- bool visit_on_exit
-) {
- return cxTreeIterateSubtree(tree, tree->root, visit_on_exit);
-}
-
-/**
- * Creates a breadth-first iterator for the specified tree.
- *
- * @param tree the tree to iterate
- * @return a tree visitor (a.k.a. breadth-first iterator)
- * @see cxTreeIterate()
- */
-__attribute__((__nonnull__, __warn_unused_result__))
-static inline CxTreeVisitor cxTreeVisit(CxTree *tree) {
- return cxTreeVisitSubtree(tree, tree->root);
-}
-
-/**
- * Sets the (new) parent of the specified child.
- *
- * If the \p child is not already member of the tree, this function behaves
- * as #cxTreeAddChildNode().
- *
- * @param tree the tree
- * @param parent the (new) parent of the child
- * @param child the node to add
- * @see cxTreeAddChildNode()
- */
-__attribute__((__nonnull__))
-void cxTreeSetParent(
- CxTree *tree,
- void *parent,
- void *child
-);
-
-/**
- * Adds a new node to the tree.
- *
- * If the \p child is already member of the tree, the behavior is undefined.
- * Use #cxTreeSetParent() if you want to move a subtree to another location.
- *
- * \attention The node may be externally created, but MUST obey the same rules
- * as if it was created by the tree itself with #cxTreeAddChild() (e.g. use
- * the same allocator).
- *
- * @param tree the tree
- * @param parent the parent of the node to add
- * @param child the node to add
- * @see cxTreeSetParent()
- */
-__attribute__((__nonnull__))
-void cxTreeAddChildNode(
- CxTree *tree,
- void *parent,
- void *child
-);
-
-/**
- * Creates a new node and adds it to the tree.
- *
- * With this function you can decide where exactly the new node shall be added.
- * If you specified an appropriate search function, you may want to consider
- * leaving this task to the tree by using #cxTreeInsert().
- *
- * Be aware that adding nodes at arbitrary locations in the tree might cause
- * wrong or undesired results when subsequently invoking #cxTreeInsert() and
- * the invariant imposed by the search function does not hold any longer.
- *
- * @param tree the tree
- * @param parent the parent node of the new node
- * @param data the data that will be submitted to the create function
- * @return zero when the new node was created, non-zero on allocation failure
- * @see cxTreeInsert()
- */
-__attribute__((__nonnull__))
-int cxTreeAddChild(
- CxTree *tree,
- void *parent,
- const void *data
-);
-
-/**
- * A function that is invoked when a node needs to be re-linked to a new parent.
- *
- * When a node is re-linked, sometimes the contents need to be updated.
- * This callback is invoked by #cxTreeRemoveNode() and #cxTreeDestroyNode()
- * so that those updates can be applied when re-linking the children of the
- * removed node.
- *
- * @param node the affected node
- * @param old_parent the old parent of the node
- * @param new_parent the new parent of the node
- */
-typedef void (*cx_tree_relink_func)(
- void *node,
- const void *old_parent,
- const void *new_parent
-);
-
-/**
- * Removes a node and re-links its children to its former parent.
- *
- * If the node is not part of the tree, the behavior is undefined.
- *
- * \note The destructor function, if any, will \em not be invoked. That means
- * you will need to free the removed node by yourself, eventually.
- *
- * @param tree the tree
- * @param node the node to remove (must not be the root node)
- * @param relink_func optional callback to update the content of each re-linked
- * node
- * @return zero on success, non-zero if \p node is the root node of the tree
- */
-__attribute__((__nonnull__(1,2)))
-int cxTreeRemoveNode(
- CxTree *tree,
- void *node,
- cx_tree_relink_func relink_func
-);
-
-/**
- * Removes a node and it's subtree from the tree.
- *
- * If the node is not part of the tree, the behavior is undefined.
- *
- * \note The destructor function, if any, will \em not be invoked. That means
- * you will need to free the removed subtree by yourself, eventually.
- *
- * @param tree the tree
- * @param node the node to remove
- */
-__attribute__((__nonnull__))
-void cxTreeRemoveSubtree(CxTree *tree, void *node);
-
-/**
- * Destroys a node and re-links its children to its former parent.
- *
- * If the node is not part of the tree, the behavior is undefined.
- *
- * It is guaranteed that the simple destructor is invoked before
- * the advanced destructor.
- *
- * \attention This function will not free the memory of the node with the
- * tree's allocator, because that is usually done by the advanced destructor
- * and would therefore result in a double-free.
- *
- * @param tree the tree
- * @param node the node to destroy (must not be the root node)
- * @param relink_func optional callback to update the content of each re-linked
- * node
- * @return zero on success, non-zero if \p node is the root node of the tree
- */
-__attribute__((__nonnull__(1,2)))
-int cxTreeDestroyNode(
- CxTree *tree,
- void *node,
- cx_tree_relink_func relink_func
-);
/**
* Destroys a node and it's subtree.
@@ -1339,7 +897,7 @@
* @param node the node to remove
* @see cxTreeDestroy()
*/
-__attribute__((__nonnull__))
+cx_attr_nonnull
void cxTreeDestroySubtree(CxTree *tree, void *node);
@@ -1378,14 +936,475 @@
*
* @param tree the tree to destroy
*/
-__attribute__((__nonnull__))
static inline void cxTreeDestroy(CxTree *tree) {
+ if (tree == NULL) return;
if (tree->root != NULL) {
- cxTreeDestroySubtree(tree, tree->root);
+ cxTreeClear(tree);
}
cxFree(tree->allocator, tree);
}
+/**
+ * Creates a new tree structure based on the specified layout.
+ *
+ * The specified \p allocator will be used for creating the tree struct
+ * and SHALL be used by \p create_func to allocate memory for the nodes.
+ *
+ * \note This function will also register an advanced destructor which
+ * will free the nodes with the allocator's free() method.
+ *
+ * @param allocator the allocator that shall be used
+ * @param create_func a function that creates new nodes
+ * @param search_func a function that compares two nodes
+ * @param search_data_func a function that compares a node with data
+ * @param loc_parent offset in the node struct for the parent pointer
+ * @param loc_children offset in the node struct for the children linked list
+ * @param loc_last_child optional offset in the node struct for the pointer to
+ * the last child in the linked list (negative if there is no such pointer)
+ * @param loc_prev optional offset in the node struct for the prev pointer
+ * @param loc_next offset in the node struct for the next pointer
+ * @return the new tree
+ * @see cxTreeCreateSimple()
+ * @see cxTreeCreateWrapped()
+ */
+cx_attr_nonnull
+cx_attr_nodiscard
+cx_attr_malloc
+cx_attr_dealloc(cxTreeDestroy, 1)
+CxTree *cxTreeCreate(
+ const CxAllocator *allocator,
+ cx_tree_node_create_func create_func,
+ cx_tree_search_func search_func,
+ cx_tree_search_data_func search_data_func,
+ ptrdiff_t loc_parent,
+ ptrdiff_t loc_children,
+ ptrdiff_t loc_last_child,
+ ptrdiff_t loc_prev,
+ ptrdiff_t loc_next
+);
+
+/**
+ * Creates a new tree structure based on a default layout.
+ *
+ * Nodes created by \p create_func MUST contain #cx_tree_node_base_s as first
+ * member (or at least respect the default offsets specified in the tree
+ * struct) and they MUST be allocated with the specified allocator.
+ *
+ * \note This function will also register an advanced destructor which
+ * will free the nodes with the allocator's free() method.
+ *
+ * @param allocator the allocator that shall be used
+ * @param create_func a function that creates new nodes
+ * @param search_func a function that compares two nodes
+ * @param search_data_func a function that compares a node with data
+ * @return the new tree
+ * @see cxTreeCreate()
+ */
+#define cxTreeCreateSimple(\
+ allocator, create_func, search_func, search_data_func \
+) cxTreeCreate(allocator, create_func, search_func, search_data_func, \
+cx_tree_node_base_layout)
+
+/**
+ * Creates a new tree structure based on an existing tree.
+ *
+ * The specified \p allocator will be used for creating the tree struct.
+ *
+ * \attention This function will create an incompletely defined tree structure
+ * where neither the create function, the search function, nor a destructor
+ * will be set. If you wish to use any of this functionality for the wrapped
+ * tree, you need to specify those functions afterwards.
+ *
+ * @param allocator the allocator that was used for nodes of the wrapped tree
+ * @param root the root node of the tree that shall be wrapped
+ * @param loc_parent offset in the node struct for the parent pointer
+ * @param loc_children offset in the node struct for the children linked list
+ * @param loc_last_child optional offset in the node struct for the pointer to
+ * the last child in the linked list (negative if there is no such pointer)
+ * @param loc_prev optional offset in the node struct for the prev pointer
+ * @param loc_next offset in the node struct for the next pointer
+ * @return the new tree
+ * @see cxTreeCreate()
+ */
+cx_attr_nonnull
+cx_attr_nodiscard
+cx_attr_malloc
+cx_attr_dealloc(cxTreeDestroy, 1)
+CxTree *cxTreeCreateWrapped(
+ const CxAllocator *allocator,
+ void *root,
+ ptrdiff_t loc_parent,
+ ptrdiff_t loc_children,
+ ptrdiff_t loc_last_child,
+ ptrdiff_t loc_prev,
+ ptrdiff_t loc_next
+);
+
+/**
+ * Inserts data into the tree.
+ *
+ * \remark For this function to work, the tree needs specified search and
+ * create functions, which might not be available for wrapped trees
+ * (see #cxTreeCreateWrapped()).
+ *
+ * @param tree the tree
+ * @param data the data to insert
+ * @return zero on success, non-zero on failure
+ */
+cx_attr_nonnull
+static inline int cxTreeInsert(
+ CxTree *tree,
+ const void *data
+) {
+ return tree->cl->insert_element(tree, data);
+}
+
+/**
+ * Inserts elements provided by an iterator efficiently into the tree.
+ *
+ * \remark For this function to work, the tree needs specified search and
+ * create functions, which might not be available for wrapped trees
+ * (see #cxTreeCreateWrapped()).
+ *
+ * @param tree the tree
+ * @param iter the iterator providing the elements
+ * @param n the maximum number of elements to insert
+ * @return the number of elements that could be successfully inserted
+ */
+cx_attr_nonnull
+static inline size_t cxTreeInsertIter(
+ CxTree *tree,
+ struct cx_iterator_base_s *iter,
+ size_t n
+) {
+ return tree->cl->insert_many(tree, iter, n);
+}
+
+/**
+ * Inserts an array of data efficiently into the tree.
+ *
+ * \remark For this function to work, the tree needs specified search and
+ * create functions, which might not be available for wrapped trees
+ * (see #cxTreeCreateWrapped()).
+ *
+ * @param tree the tree
+ * @param data the array of data to insert
+ * @param elem_size the size of each element in the array
+ * @param n the number of elements in the array
+ * @return the number of elements that could be successfully inserted
+ */
+cx_attr_nonnull
+static inline size_t cxTreeInsertArray(
+ CxTree *tree,
+ const void *data,
+ size_t elem_size,
+ size_t n
+) {
+ if (n == 0) return 0;
+ if (n == 1) return 0 == cxTreeInsert(tree, data) ? 1 : 0;
+ CxIterator iter = cxIterator(data, elem_size, n);
+ return cxTreeInsertIter(tree, cxIteratorRef(iter), n);
+}
+
+/**
+ * Searches the data in the specified tree.
+ *
+ * \remark For this function to work, the tree needs a specified \c search_data
+ * function, which might not be available wrapped trees
+ * (see #cxTreeCreateWrapped()).
+ *
+ * @param tree the tree
+ * @param data the data to search for
+ * @return the first matching node, or \c NULL when the data cannot be found
+ */
+cx_attr_nonnull
+cx_attr_nodiscard
+static inline void *cxTreeFind(
+ CxTree *tree,
+ const void *data
+) {
+ return tree->cl->find(tree, tree->root, data, 0);
+}
+
+/**
+ * Searches the data in the specified subtree.
+ *
+ * When \p max_depth is zero, the depth is not limited.
+ * The \p subtree_root itself is on depth 1 and its children have depth 2.
+ *
+ * \note When \p subtree_root is not part of the \p tree, the behavior is
+ * undefined.
+ *
+ * \remark For this function to work, the tree needs a specified \c search_data
+ * function, which might not be the case for wrapped trees
+ * (see #cxTreeCreateWrapped()).
+ *
+ * @param tree the tree
+ * @param data the data to search for
+ * @param subtree_root the node where to start
+ * @param max_depth the maximum search depth
+ * @return the first matching node, or \c NULL when the data cannot be found
+ */
+cx_attr_nonnull
+cx_attr_nodiscard
+static inline void *cxTreeFindInSubtree(
+ CxTree *tree,
+ const void *data,
+ void *subtree_root,
+ size_t max_depth
+) {
+ return tree->cl->find(tree, subtree_root, data, max_depth);
+}
+
+/**
+ * Determines the size of the specified subtree.
+ *
+ * @param tree the tree
+ * @param subtree_root the root node of the subtree
+ * @return the number of nodes in the specified subtree
+ */
+cx_attr_nonnull
+cx_attr_nodiscard
+size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root);
+
+/**
+ * Determines the depth of the specified subtree.
+ *
+ * @param tree the tree
+ * @param subtree_root the root node of the subtree
+ * @return the tree depth including the \p subtree_root
+ */
+cx_attr_nonnull
+cx_attr_nodiscard
+size_t cxTreeSubtreeDepth(CxTree *tree, void *subtree_root);
+
+/**
+ * Determines the depth of the entire tree.
+ *
+ * @param tree the tree
+ * @return the tree depth, counting the root as one
+ */
+cx_attr_nonnull
+cx_attr_nodiscard
+size_t cxTreeDepth(CxTree *tree);
+
+/**
+ * Creates a depth-first iterator for the specified tree starting in \p node.
+ *
+ * If the node is not part of the tree, the behavior is undefined.
+ *
+ * @param tree the tree to iterate
+ * @param node the node where to start
+ * @param visit_on_exit true, if the iterator shall visit a node again when
+ * leaving the subtree
+ * @return a tree iterator (depth-first)
+ * @see cxTreeVisit()
+ */
+cx_attr_nonnull
+cx_attr_nodiscard
+static inline CxTreeIterator cxTreeIterateSubtree(
+ CxTree *tree,
+ void *node,
+ bool visit_on_exit
+) {
+ return cx_tree_iterator(
+ node, visit_on_exit,
+ tree->loc_children, tree->loc_next
+ );
+}
+
+/**
+ * Creates a breadth-first iterator for the specified tree starting in \p node.
+ *
+ * If the node is not part of the tree, the behavior is undefined.
+ *
+ * @param tree the tree to iterate
+ * @param node the node where to start
+ * @return a tree visitor (a.k.a. breadth-first iterator)
+ * @see cxTreeIterate()
+ */
+cx_attr_nonnull
+cx_attr_nodiscard
+static inline CxTreeVisitor cxTreeVisitSubtree(CxTree *tree, void *node) {
+ return cx_tree_visitor(
+ node, tree->loc_children, tree->loc_next
+ );
+}
+
+/**
+ * Creates a depth-first iterator for the specified tree.
+ *
+ * @param tree the tree to iterate
+ * @param visit_on_exit true, if the iterator shall visit a node again when
+ * leaving the subtree
+ * @return a tree iterator (depth-first)
+ * @see cxTreeVisit()
+ */
+cx_attr_nonnull
+cx_attr_nodiscard
+static inline CxTreeIterator cxTreeIterate(
+ CxTree *tree,
+ bool visit_on_exit
+) {
+ return cxTreeIterateSubtree(tree, tree->root, visit_on_exit);
+}
+
+/**
+ * Creates a breadth-first iterator for the specified tree.
+ *
+ * @param tree the tree to iterate
+ * @return a tree visitor (a.k.a. breadth-first iterator)
+ * @see cxTreeIterate()
+ */
+cx_attr_nonnull
+cx_attr_nodiscard
+static inline CxTreeVisitor cxTreeVisit(CxTree *tree) {
+ return cxTreeVisitSubtree(tree, tree->root);
+}
+
+/**
+ * Sets the (new) parent of the specified child.
+ *
+ * If the \p child is not already member of the tree, this function behaves
+ * as #cxTreeAddChildNode().
+ *
+ * @param tree the tree
+ * @param parent the (new) parent of the child
+ * @param child the node to add
+ * @see cxTreeAddChildNode()
+ */
+cx_attr_nonnull
+void cxTreeSetParent(
+ CxTree *tree,
+ void *parent,
+ void *child
+);
+
+/**
+ * Adds a new node to the tree.
+ *
+ * If the \p child is already member of the tree, the behavior is undefined.
+ * Use #cxTreeSetParent() if you want to move a subtree to another location.
+ *
+ * \attention The node may be externally created, but MUST obey the same rules
+ * as if it was created by the tree itself with #cxTreeAddChild() (e.g. use
+ * the same allocator).
+ *
+ * @param tree the tree
+ * @param parent the parent of the node to add
+ * @param child the node to add
+ * @see cxTreeSetParent()
+ */
+cx_attr_nonnull
+void cxTreeAddChildNode(
+ CxTree *tree,
+ void *parent,
+ void *child
+);
+
+/**
+ * Creates a new node and adds it to the tree.
+ *
+ * With this function you can decide where exactly the new node shall be added.
+ * If you specified an appropriate search function, you may want to consider
+ * leaving this task to the tree by using #cxTreeInsert().
+ *
+ * Be aware that adding nodes at arbitrary locations in the tree might cause
+ * wrong or undesired results when subsequently invoking #cxTreeInsert() and
+ * the invariant imposed by the search function does not hold any longer.
+ *
+ * @param tree the tree
+ * @param parent the parent node of the new node
+ * @param data the data that will be submitted to the create function
+ * @return zero when the new node was created, non-zero on allocation failure
+ * @see cxTreeInsert()
+ */
+cx_attr_nonnull
+int cxTreeAddChild(
+ CxTree *tree,
+ void *parent,
+ const void *data
+);
+
+/**
+ * A function that is invoked when a node needs to be re-linked to a new parent.
+ *
+ * When a node is re-linked, sometimes the contents need to be updated.
+ * This callback is invoked by #cxTreeRemoveNode() and #cxTreeDestroyNode()
+ * so that those updates can be applied when re-linking the children of the
+ * removed node.
+ *
+ * @param node the affected node
+ * @param old_parent the old parent of the node
+ * @param new_parent the new parent of the node
+ */
+cx_attr_nonnull
+typedef void (*cx_tree_relink_func)(
+ void *node,
+ const void *old_parent,
+ const void *new_parent
+);
+
+/**
+ * Removes a node and re-links its children to its former parent.
+ *
+ * If the node is not part of the tree, the behavior is undefined.
+ *
+ * \note The destructor function, if any, will \em not be invoked. That means
+ * you will need to free the removed node by yourself, eventually.
+ *
+ * @param tree the tree
+ * @param node the node to remove (must not be the root node)
+ * @param relink_func optional callback to update the content of each re-linked
+ * node
+ * @return zero on success, non-zero if \p node is the root node of the tree
+ */
+cx_attr_nonnull_arg(1, 2)
+int cxTreeRemoveNode(
+ CxTree *tree,
+ void *node,
+ cx_tree_relink_func relink_func
+);
+
+/**
+ * Removes a node and it's subtree from the tree.
+ *
+ * If the node is not part of the tree, the behavior is undefined.
+ *
+ * \note The destructor function, if any, will \em not be invoked. That means
+ * you will need to free the removed subtree by yourself, eventually.
+ *
+ * @param tree the tree
+ * @param node the node to remove
+ */
+cx_attr_nonnull
+void cxTreeRemoveSubtree(CxTree *tree, void *node);
+
+/**
+ * Destroys a node and re-links its children to its former parent.
+ *
+ * If the node is not part of the tree, the behavior is undefined.
+ *
+ * It is guaranteed that the simple destructor is invoked before
+ * the advanced destructor.
+ *
+ * \attention This function will not free the memory of the node with the
+ * tree's allocator, because that is usually done by the advanced destructor
+ * and would therefore result in a double-free.
+ *
+ * @param tree the tree
+ * @param node the node to destroy (must not be the root node)
+ * @param relink_func optional callback to update the content of each re-linked
+ * node
+ * @return zero on success, non-zero if \p node is the root node of the tree
+ */
+cx_attr_nonnull_arg(1, 2)
+int cxTreeDestroyNode(
+ CxTree *tree,
+ void *node,
+ cx_tree_relink_func relink_func
+);
+
#ifdef __cplusplus
} // extern "C"
#endif