--- a/ucx/cx/tree.h Sun Jan 05 17:41:39 2025 +0100
+++ b/ucx/cx/tree.h Sun Jan 05 22:00:39 2025 +0100
@@ -26,11 +26,11 @@
* POSSIBILITY OF SUCH DAMAGE.
*/
/**
- * \file tree.h
- * \brief Interface for tree implementations.
- * \author Mike Becker
- * \author Olaf Wintermann
- * \copyright 2-Clause BSD License
+ * @file tree.h
+ * @brief Interface for tree implementations.
+ * @author Mike Becker
+ * @author Olaf Wintermann
+ * @copyright 2-Clause BSD License
*/
#ifndef UCX_TREE_H
@@ -138,7 +138,7 @@
*/
size_t depth;
/**
- * The next element in the queue or \c NULL.
+ * The next element in the queue or @c NULL.
*/
struct cx_tree_visitor_queue_s *next;
};
@@ -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) {
@@ -233,7 +233,7 @@
* Advises the iterator to skip the subtree below the current node and
* also continues the current loop.
*
- * @param iterator the iterator
+ * @param iterator (@c CxTreeIterator) the iterator
*/
#define cxTreeIteratorContinue(iterator) (iterator).skip = true; continue
@@ -241,7 +241,7 @@
* Advises the visitor to skip the subtree below the current node and
* also continues the current loop.
*
- * @param visitor the visitor
+ * @param visitor (@c CxTreeVisitor) the visitor
*/
#define cxTreeVisitorContinue(visitor) cxTreeIteratorContinue(visitor)
@@ -249,7 +249,7 @@
* Links a node to a (new) parent.
*
* If the node has already a parent, it is unlinked, first.
- * If the parent has children already, the node is \em appended to the list
+ * If the parent has children already, the node is @em appended to the list
* of all currently existing children.
*
* @param parent the parent node
@@ -258,14 +258,14 @@
* @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 offset in the node struct for the prev 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
* @see cx_tree_unlink()
*/
-__attribute__((__nonnull__))
+cx_attr_nonnull
void cx_tree_link(
- void *restrict parent,
- void *restrict node,
+ void *parent,
+ void *node,
ptrdiff_t loc_parent,
ptrdiff_t loc_children,
ptrdiff_t loc_last_child,
@@ -283,11 +283,11 @@
* @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 offset in the node struct for the prev 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
* @see cx_tree_link()
*/
-__attribute__((__nonnull__))
+cx_attr_nonnull
void cx_tree_unlink(
void *node,
ptrdiff_t loc_parent,
@@ -298,14 +298,21 @@
);
/**
+ * Macro that can be used instead of the magic value for infinite search depth.
+ */
+#define CX_TREE_SEARCH_INFINITE_DEPTH 0
+
+/**
* Function pointer for a search function.
*
- * A function of this kind shall check if the specified \p node
- * contains the given \p data or if one of the children might contain
+ * A function of this kind shall check if the specified @p node
+ * contains the given @p data or if one of the children might contain
* the data.
*
* The function should use the returned integer to indicate how close the
* match is, where a negative number means that it does not match at all.
+ * Zero means exact match and a positive number is an implementation defined
+ * measure for the distance to an exact match.
*
* For example if a tree stores file path information, a node that is
* describing a parent directory of a filename that is searched, shall
@@ -321,18 +328,21 @@
* 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);
/**
* Function pointer for a search function.
*
- * A function of this kind shall check if the specified \p node
- * contains the same \p data as \p new_node or if one of the children might
+ * A function of this kind shall check if the specified @p node
+ * contains the same @p data as @p new_node or if one of the children might
* contain the data.
*
* The function should use the returned integer to indicate how close the
* match is, where a negative number means that it does not match at all.
+ * Zero means exact match and a positive number is an implementation defined
+ * measure for the distance to an exact match.
*
* For example if a tree stores file path information, a node that is
* describing a parent directory of a filename that is searched, shall
@@ -344,10 +354,11 @@
* @param node the node that is currently investigated
* @param new_node a new node with the information which is searched
*
- * @return 0 if \p node contains the same data as \p new_node,
+ * @return 0 if @p node contains the same data as @p new_node,
* 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);
/**
@@ -359,11 +370,12 @@
*
* Depending on the tree structure it is not necessarily guaranteed that the
* "closest" match is uniquely defined. This function will search for a node
- * with the best match according to the \p sfunc (meaning: the return value of
- * \p sfunc which is closest to zero). If that is also ambiguous, an arbitrary
+ * with the best match according to the @p sfunc (meaning: the return value of
+ * @p sfunc which is closest to zero). If that is also ambiguous, an arbitrary
* node matching the criteria is returned.
*
* @param root the root node
+ * @param depth the maximum depth (zero=indefinite, one=just root)
* @param data the data to search for
* @param sfunc the search function
* @param result where the result shall be stored
@@ -373,9 +385,11 @@
* 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,
const void *data,
cx_tree_search_data_func sfunc,
void **result,
@@ -392,11 +406,12 @@
*
* Depending on the tree structure it is not necessarily guaranteed that the
* "closest" match is uniquely defined. This function will search for a node
- * with the best match according to the \p sfunc (meaning: the return value of
- * \p sfunc which is closest to zero). If that is also ambiguous, an arbitrary
+ * with the best match according to the @p sfunc (meaning: the return value of
+ * @p sfunc which is closest to zero). If that is also ambiguous, an arbitrary
* node matching the criteria is returned.
*
* @param root the root node
+* @param depth the maximum depth (zero=indefinite, one=just root)
* @param node the node to search for
* @param sfunc the search function
* @param result where the result shall be stored
@@ -406,9 +421,11 @@
* 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,
const void *node,
cx_tree_search_func sfunc,
void **result,
@@ -436,6 +453,7 @@
* @return the new tree iterator
* @see cxTreeIteratorDispose()
*/
+cx_attr_nodiscard
CxTreeIterator cx_tree_iterator(
void *root,
bool visit_on_exit,
@@ -461,6 +479,7 @@
* @return the new tree visitor
* @see cxTreeVisitorDispose()
*/
+cx_attr_nodiscard
CxTreeVisitor cx_tree_visitor(
void *root,
ptrdiff_t loc_children,
@@ -472,11 +491,12 @@
* The first argument points to the data the node shall contain and
* the second argument may be used for additional data (e.g. an allocator).
* Functions of this type shall either return a new pointer to a newly
- * created node or \c NULL when allocation fails.
+ * created node or @c NULL when allocation fails.
*
- * \note the function may leave the node pointers in the struct uninitialized.
+ * @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 *);
/**
@@ -493,11 +513,11 @@
* Once an element cannot be added to the tree, this function returns, leaving
* the iterator in a valid state pointing to the element that could not be
* added.
- * Also, the pointer of the created node will be stored to \p failed.
+ * Also, the pointer of the created node will be stored to @p failed.
* The integer returned by this function denotes the number of elements obtained
- * from the \p iter that have been successfully processed.
- * When all elements could be processed, a \c NULL pointer will be written to
- * \p failed.
+ * from the @p iter that have been successfully processed.
+ * When all elements could be processed, a @c NULL pointer will be written to
+ * @p failed.
*
* The advantage of this function compared to multiple invocations of
* #cx_tree_add() is that the search for the insert locations is not always
@@ -520,12 +540,13 @@
* @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 offset in the node struct for the prev 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 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,
@@ -545,11 +566,11 @@
* Adds multiple elements efficiently to a tree.
*
* Once an element cannot be added to the tree, this function returns, storing
- * the pointer of the created node to \p failed.
+ * the pointer of the created node to @p failed.
* The integer returned by this function denotes the number of elements from
- * the \p src array that have been successfully processed.
- * When all elements could be processed, a \c NULL pointer will be written to
- * \p failed.
+ * the @p src array that have been successfully processed.
+ * When all elements could be processed, a @c NULL pointer will be written to
+ * @p failed.
*
* The advantage of this function compared to multiple invocations of
* #cx_tree_add() is that the search for the insert locations is not always
@@ -562,8 +583,8 @@
* Refer to the documentation of #cx_tree_add() for more details.
*
* @param src a pointer to the source data array
- * @param num the number of elements in the \p src array
- * @param elem_size the size of each element in the \p src array
+ * @param num the number of elements in the @p src array
+ * @param elem_size the size of each element in the @p src array
* @param sfunc a search function
* @param cfunc a node creation function
* @param cdata optional additional data
@@ -573,12 +594,13 @@
* @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 offset in the node struct for the prev 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 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,
@@ -599,28 +621,28 @@
* Adds data to a tree.
*
* An adequate location where to add the new tree node is searched with the
- * specified \p sfunc.
+ * specified @p sfunc.
*
- * When a location is found, the \p cfunc will be invoked with \p cdata.
+ * When a location is found, the @p cfunc will be invoked with @p cdata.
*
- * The node returned by \p cfunc will be linked into the tree.
- * When \p sfunc returned a positive integer, the new node will be linked as a
+ * The node returned by @p cfunc will be linked into the tree.
+ * When @p sfunc returned a positive integer, the new node will be linked as a
* child. The other children (now siblings of the new node) are then checked
- * with \p sfunc, whether they could be children of the new node and re-linked
+ * with @p sfunc, whether they could be children of the new node and re-linked
* accordingly.
*
- * When \p sfunc returned zero and the found node has a parent, the new
+ * When @p sfunc returned zero and the found node has a parent, the new
* node will be added as sibling - otherwise, the new node will be added
* as a child.
*
- * When \p sfunc returned a negative value, the new node will not be added to
+ * When @p sfunc returned a negative value, the new node will not be added to
* the tree and this function returns a non-zero value.
- * The caller should check if \p cnode contains a node pointer and deal with the
+ * The caller should check if @p cnode contains a node pointer and deal with the
* node that could not be added.
*
- * This function also returns a non-zero value when \p cfunc tries to allocate
- * a new node but fails to do so. In that case, the pointer stored to \p cnode
- * will be \c NULL.
+ * This function also returns a non-zero value when @p cfunc tries to allocate
+ * a new node but fails to do so. In that case, the pointer stored to @p cnode
+ * will be @c NULL.
*
* Multiple elements can be added more efficiently with
* #cx_tree_add_array() or #cx_tree_add_iter().
@@ -635,12 +657,13 @@
* @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 offset in the node struct for the prev 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 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,
@@ -704,7 +727,7 @@
/**
* A pointer to the root node.
*
- * Will be \c NULL when \c size is 0.
+ * Will be @c NULL when @c size is 0.
*/
void *root;
@@ -778,6 +801,10 @@
/**
* Macro to roll out the #cx_tree_node_base_s structure with a custom
* node type.
+ *
+ * Must be used as first member in your custom tree struct.
+ *
+ * @param type the data type for the nodes
*/
#define CX_TREE_NODE_BASE(type) \
type *parent; \
@@ -788,6 +815,11 @@
/**
* Macro for specifying the layout of a base node tree.
+ *
+ * When your tree uses #CX_TREE_NODE_BASE, you can use this
+ * macro in all tree functions that expect the layout parameters
+ * @c loc_parent, @c loc_children, @c loc_last_child, @c loc_prev,
+ * and @c loc_next.
*/
#define cx_tree_node_base_layout \
offsetof(struct cx_tree_node_base_s, parent),\
@@ -797,31 +829,13 @@
offsetof(struct cx_tree_node_base_s, next)
/**
- * Macro for obtaining the node pointer layout for a specific tree.
- */
-#define cx_tree_node_layout(tree) \
- (tree)->loc_parent,\
- (tree)->loc_children,\
- (tree)->loc_last_child,\
- (tree)->loc_prev, \
- (tree)->loc_next
-
-/**
* The class definition for arbitrary trees.
*/
struct cx_tree_class_s {
/**
- * Destructor function.
- *
- * Implementations SHALL invoke the node destructor functions if provided
- * and SHALL deallocate the tree memory.
- */
- void (*destructor)(struct cx_tree_s *);
-
- /**
* Member function for inserting a single element.
*
- * Implementations SHALL NOT simply invoke \p insert_many as this comes
+ * Implementations SHALL NOT simply invoke @p insert_many as this comes
* with too much overhead.
*/
int (*insert_element)(
@@ -847,21 +861,9 @@
void *(*find)(
struct cx_tree_s *tree,
const void *subtree,
- const void *data
+ const void *data,
+ size_t depth
);
-
- /**
- * Member function for creating an iterator for the tree.
- */
- CxTreeIterator (*iterator)(
- struct cx_tree_s *tree,
- bool visit_on_exit
- );
-
- /**
- * Member function for creating a visitor for the tree.
- */
- CxTreeVisitor (*visitor)(struct cx_tree_s *tree);
};
/**
@@ -869,16 +871,80 @@
*/
typedef struct cx_tree_s CxTree;
+
+/**
+ * Destroys a node and it's subtree.
+ *
+ * It is guaranteed that the simple destructor is invoked before
+ * the advanced destructor, starting with the leaf nodes of the subtree.
+ *
+ * When this function is invoked on the root node of the tree, it destroys the
+ * tree contents, but - in contrast to #cxTreeFree() - not the tree
+ * structure, leaving an empty tree behind.
+ *
+ * @note The destructor function, if any, will @em not be invoked. That means
+ * you will need to free the removed subtree by yourself, eventually.
+ *
+ * @attention This function will not free the memory of the nodes 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 remove
+ * @see cxTreeFree()
+ */
+cx_attr_nonnull
+void cxTreeDestroySubtree(CxTree *tree, void *node);
+
+
+/**
+ * Destroys the tree contents.
+ *
+ * It is guaranteed that the simple destructor is invoked before
+ * the advanced destructor, starting with the leaf nodes of the subtree.
+ *
+ * This is a convenience macro for invoking #cxTreeDestroySubtree() on the
+ * root node of the tree.
+ *
+ * @attention Be careful when calling this function when no destructor function
+ * is registered that actually frees the memory of nodes. In that case you will
+ * need a reference to the (former) root node of the tree somewhere or
+ * otherwise you will be leaking memory.
+ *
+ * @param tree the tree
+ * @see cxTreeDestroySubtree()
+ */
+#define cxTreeClear(tree) cxTreeDestroySubtree(tree, tree->root)
+
+/**
+ * Deallocates the tree structure.
+ *
+ * The destructor functions are invoked for each node, starting with the leaf
+ * nodes.
+ * It is guaranteed that for each node the simple destructor is invoked before
+ * the advanced destructor.
+ *
+ * @attention This function will only invoke the destructor functions
+ * on the nodes.
+ * It will NOT additionally free the nodes with the tree's allocator, because
+ * that would cause a double-free in most scenarios where the advanced
+ * destructor is already freeing the memory.
+ *
+ * @param tree the tree to free
+ */
+void cxTreeFree(CxTree *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.
+ * 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
+ * @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
+ * (if @c NULL, a default stdlib allocator will 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
@@ -886,13 +952,16 @@
* @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 offset in the node struct for the prev 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__))
+cx_attr_nonnull_arg(2, 3, 4)
+cx_attr_nodiscard
+cx_attr_malloc
+cx_attr_dealloc(cxTreeFree, 1)
CxTree *cxTreeCreate(
const CxAllocator *allocator,
cx_tree_node_create_func create_func,
@@ -908,57 +977,51 @@
/**
* 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
+ * 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
+ * @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
+ * @param allocator (@c CxAllocator*) the allocator that shall be used
+ * @param create_func (@c cx_tree_node_create_func) a function that creates new nodes
+ * @param search_func (@c cx_tree_search_func) a function that compares two nodes
+ * @param search_data_func (@c cx_tree_search_data_func) a function that compares a node with data
+ * @return (@c CxTree*) 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
- );
-}
+#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.
+ * The specified @p allocator will be used for creating the tree struct.
*
- * \attention This function will create an incompletely defined tree structure
+ * @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
+ * (if @c NULL, a default stdlib allocator is assumed)
* @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 offset in the node struct for the prev 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__))
+cx_attr_nonnull_arg(2)
+cx_attr_nodiscard
+cx_attr_malloc
+cx_attr_dealloc(cxTreeFree, 1)
CxTree *cxTreeCreateWrapped(
const CxAllocator *allocator,
void *root,
@@ -970,32 +1033,18 @@
);
/**
- * Destroys the tree structure.
- *
- * \attention This function will only invoke the destructor functions
- * on the nodes, if specified.
- * It will NOT additionally free the nodes with the tree's allocator, because
- * that would cause a double-free in most scenarios.
- *
- * @param tree the tree to destroy
- */
-__attribute__((__nonnull__))
-static inline void cxTreeDestroy(CxTree *tree) {
- tree->cl->destructor(tree);
-}
-
-/**
* Inserts data into the tree.
*
- * \remark For this function to work, the tree needs specified search and
+ * @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
+ * @retval zero success
+ * @retval non-zero failure
*/
-__attribute__((__nonnull__))
+cx_attr_nonnull
static inline int cxTreeInsert(
CxTree *tree,
const void *data
@@ -1006,7 +1055,7 @@
/**
* Inserts elements provided by an iterator efficiently into the tree.
*
- * \remark For this function to work, the tree needs specified search and
+ * @remark For this function to work, the tree needs specified search and
* create functions, which might not be available for wrapped trees
* (see #cxTreeCreateWrapped()).
*
@@ -1015,7 +1064,7 @@
* @param n the maximum number of elements to insert
* @return the number of elements that could be successfully inserted
*/
-__attribute__((__nonnull__))
+cx_attr_nonnull
static inline size_t cxTreeInsertIter(
CxTree *tree,
struct cx_iterator_base_s *iter,
@@ -1027,7 +1076,7 @@
/**
* Inserts an array of data efficiently into the tree.
*
- * \remark For this function to work, the tree needs specified search and
+ * @remark For this function to work, the tree needs specified search and
* create functions, which might not be available for wrapped trees
* (see #cxTreeCreateWrapped()).
*
@@ -1037,7 +1086,7 @@
* @param n the number of elements in the array
* @return the number of elements that could be successfully inserted
*/
-__attribute__((__nonnull__))
+cx_attr_nonnull
static inline size_t cxTreeInsertArray(
CxTree *tree,
const void *data,
@@ -1053,44 +1102,51 @@
/**
* Searches the data in the specified tree.
*
- * \remark For this function to work, the tree needs a specified \c search_data
+ * @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
+ * @return the first matching node, or @c NULL when the data cannot be found
*/
-__attribute__((__nonnull__))
+cx_attr_nonnull
+cx_attr_nodiscard
static inline void *cxTreeFind(
CxTree *tree,
const void *data
) {
- return tree->cl->find(tree, tree->root, data);
+ return tree->cl->find(tree, tree->root, data, 0);
}
/**
* Searches the data in the specified subtree.
*
- * \note When \p subtree_root is not part of the \p tree, the behavior is
+ * 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
+ * @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
- * @return the first matching node, or \c NULL when the data cannot be found
+ * @param max_depth the maximum search depth
+ * @return the first matching node, or @c NULL when the data cannot be found
*/
-__attribute__((__nonnull__))
+cx_attr_nonnull
+cx_attr_nodiscard
static inline void *cxTreeFindInSubtree(
CxTree *tree,
const void *data,
- void *subtree_root
+ void *subtree_root,
+ size_t max_depth
) {
- return tree->cl->find(tree, subtree_root, data);
+ return tree->cl->find(tree, subtree_root, data, max_depth);
}
/**
@@ -1100,7 +1156,8 @@
* @param subtree_root the root node of the subtree
* @return the number of nodes in the specified subtree
*/
-__attribute__((__nonnull__))
+cx_attr_nonnull
+cx_attr_nodiscard
size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root);
/**
@@ -1108,9 +1165,10 @@
*
* @param tree the tree
* @param subtree_root the root node of the subtree
- * @return the tree depth including the \p subtree_root
+ * @return the tree depth including the @p subtree_root
*/
-__attribute__((__nonnull__))
+cx_attr_nonnull
+cx_attr_nodiscard
size_t cxTreeSubtreeDepth(CxTree *tree, void *subtree_root);
/**
@@ -1119,24 +1177,69 @@
* @param tree the tree
* @return the tree depth, counting the root as one
*/
-__attribute__((__nonnull__))
+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 sub-tree
+ * leaving the subtree
* @return a tree iterator (depth-first)
- * @see cxTreeVisitor()
+ * @see cxTreeVisit()
*/
-__attribute__((__nonnull__, __warn_unused_result__))
-static inline CxTreeIterator cxTreeIterator(
+cx_attr_nonnull
+cx_attr_nodiscard
+static inline CxTreeIterator cxTreeIterate(
CxTree *tree,
bool visit_on_exit
) {
- return tree->cl->iterator(tree, visit_on_exit);
+ return cxTreeIterateSubtree(tree, tree->root, visit_on_exit);
}
/**
@@ -1144,32 +1247,53 @@
*
* @param tree the tree to iterate
* @return a tree visitor (a.k.a. breadth-first iterator)
- * @see cxTreeIterator()
+ * @see cxTreeIterate()
*/
-__attribute__((__nonnull__, __warn_unused_result__))
-static inline CxTreeVisitor cxTreeVisitor(CxTree *tree) {
- return tree->cl->visitor(tree);
+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.
*
- * \attention The node may be externally created, but MUST obey the same rules
+ * 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__))
-static inline void cxTreeAddChildNode(
+cx_attr_nonnull
+void cxTreeAddChildNode(
CxTree *tree,
void *parent,
- void *child) {
- cx_tree_link(parent, child, cx_tree_node_layout(tree));
- tree->size++;
-}
+ void *child
+);
/**
* Creates a new node and adds it to the tree.
@@ -1188,7 +1312,7 @@
* @return zero when the new node was created, non-zero on allocation failure
* @see cxTreeInsert()
*/
-__attribute__((__nonnull__))
+cx_attr_nonnull
int cxTreeAddChild(
CxTree *tree,
void *parent,
@@ -1199,13 +1323,15 @@
* 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 #cxTreeRemove() so that those updates can be
- * applied when re-linking the children of the removed node.
+ * 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,
@@ -1217,17 +1343,17 @@
*
* 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
+ * @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
+ * @return zero on success, non-zero if @p node is the root node of the tree
*/
-__attribute__((__nonnull__(1,2)))
-int cxTreeRemove(
+cx_attr_nonnull_arg(1, 2)
+int cxTreeRemoveNode(
CxTree *tree,
void *node,
cx_tree_relink_func relink_func
@@ -1238,15 +1364,40 @@
*
* 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
+ * @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__))
+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