toolkit: comparison ucx/cx/tree.h

-:bf7084544cb1
+:7c4b9cba09ca
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */
 /**
-* \file tree.h
+* @file tree.h
-* \brief Interface for tree implementations.
+* @brief Interface for tree implementations.
-* \author Mike Becker
+* @author Mike Becker
-* \author Olaf Wintermann
+* @author Olaf Wintermann
-* \copyright 2-Clause BSD License
+* @copyright 2-Clause BSD License
 */
 #ifndef UCX_TREE_H
 #define UCX_TREE_H
 /**
 * The depth of the node.
 */
 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;
 };
 /**
 /**
 * 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;
 }
 /**
 * 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) {
 struct cx_tree_visitor_queue_s *next = q->next;
 free(q);
 /**
 * 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
 /**
 * 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)
 /**
 * 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
 * @param node the node that shall be linked
 * @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
 * @see cx_tree_unlink()
 */
-__attribute__((__nonnull__))
+cx_attr_nonnull
 void cx_tree_link(
-void *restrict parent,
+void *parent,
-void *restrict node,
+void *node,
 ptrdiff_t loc_parent,
 ptrdiff_t loc_children,
 ptrdiff_t loc_last_child,
 ptrdiff_t loc_prev,
 ptrdiff_t loc_next
 * @param node the node that shall be unlinked from its parent
 * @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
 * @see cx_tree_link()
 */
-__attribute__((__nonnull__))
+cx_attr_nonnull
 void cx_tree_unlink(
 void *node,
 ptrdiff_t loc_parent,
 ptrdiff_t loc_children,
 ptrdiff_t loc_last_child,
 ptrdiff_t loc_prev,
 ptrdiff_t loc_next
 );
 /**
+* 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
+* 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
+* 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
 * return a positive number to indicate that a child node might contain the
 * searched item. On the other hand, if the node denotes a path that is not a
 *
 * @return 0 if the node contains the data,
 * 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
+* 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
+* 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
 * return a positive number to indicate that a child node might contain the
 * searched item. On the other hand, if the node denotes a path that is not a
 * that the search does not need to be continued in that branch.
 *
 * @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);
 /**
 * Searches for data in a tree.
 *
 * closest result which might be a good starting point for adding a new node
 * to the tree (see also #cx_tree_add()).
 *
 * 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
+* 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
+* @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
 * @param loc_children offset in the node struct for the children linked list
 * @param loc_next offset in the node struct for the next pointer
 * @return zero if the node was found exactly, positive if a node was found that
 * 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,
 ptrdiff_t loc_children,
 ptrdiff_t loc_next
 * return a closest result which might be a good starting point for adding the
 * new node to the tree (see also #cx_tree_add()).
 *
 * 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
+* 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
+* @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
 * @param loc_children offset in the node struct for the children linked list
 * @param loc_next offset in the node struct for the next pointer
 * @return zero if the node was found exactly, positive if a node was found that
 * 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,
 ptrdiff_t loc_children,
 ptrdiff_t loc_next
 * @param loc_children offset in the node struct for the children linked list
 * @param loc_next offset in the node struct for the next pointer
 * @return the new tree iterator
 * @see cxTreeIteratorDispose()
 */
+cx_attr_nodiscard
 CxTreeIterator cx_tree_iterator(
 void *root,
 bool visit_on_exit,
 ptrdiff_t loc_children,
 ptrdiff_t loc_next
 * @param loc_children offset in the node struct for the children linked list
 * @param loc_next offset in the node struct for the next pointer
 * @return the new tree visitor
 * @see cxTreeVisitorDispose()
 */
+cx_attr_nodiscard
 CxTreeVisitor cx_tree_visitor(
 void *root,
 ptrdiff_t loc_children,
 ptrdiff_t loc_next
 );
 /**
 * Describes a function that creates a tree node from the specified data.
 * 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 *);
 /**
 * The local search depth for a new subtree when adding multiple elements.
 * The default value is 3.
 * Adds multiple elements efficiently to a tree.
 *
 * 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.
+* from the @p iter that have been successfully processed.
-* When all elements could be processed, a \c NULL pointer will be written to
+* When all elements could be processed, a @c NULL pointer will be written to
-* \p failed.
+* @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
 * started from the root node.
 * Instead, the function checks #cx_tree_add_look_around_depth many parent nodes
 * @param failed location where the pointer to a failed node shall be stored
 * @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 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,
 cx_tree_search_func sfunc,
 cx_tree_node_create_func cfunc,
 /**
 * 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.
+* the @p src array that have been successfully processed.
-* When all elements could be processed, a \c NULL pointer will be written to
+* When all elements could be processed, a @c NULL pointer will be written to
-* \p failed.
+* @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
 * started from the root node.
 * Instead, the function checks #cx_tree_add_look_around_depth many parent nodes
 * again.
 *
 * 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 num the number of elements in the @p src array
-* @param elem_size the size of each element 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
 * @param failed location where the pointer to a failed node shall be stored
 * @param root the root node of the tree
 * @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 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,
 size_t elem_size,
 cx_tree_search_func sfunc,
 /**
 * 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.
+* 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
+* 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
+* 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
+* a new node but fails to do so. In that case, the pointer stored to @p cnode
-* will be \c NULL.
+* will be @c NULL.
 *
 * Multiple elements can be added more efficiently with
 * #cx_tree_add_array() or #cx_tree_add_iter().
 *
 * @param src a pointer to the data
 * @param root the root node of the tree
 * @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 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,
 cx_tree_node_create_func cfunc,
 void *cdata,
 const CxAllocator *allocator;
 /**
 * 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;
 /**
 * A function to create new nodes.
 };
 /**
 * 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; \
 type *children;\
 type *last_child;\
 type *prev;\
 type *next
 /**
 * 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),\
 offsetof(struct cx_tree_node_base_s, children),\
 offsetof(struct cx_tree_node_base_s, last_child),\
 offsetof(struct cx_tree_node_base_s, prev),  \
 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)(
 struct cx_tree_s *tree,
 const void *data
 * Member function for finding a node.
 */
 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);
 };
 /**
 * Common type for all tree implementations.
 */
 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
+* 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.
+* 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
 * @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 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,
 cx_tree_search_func search_func,
 cx_tree_search_data_func search_data_func,
 );
 /**
 * 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 allocator (@c CxAllocator*) the allocator that shall be used
-* @param create_func a function that creates new nodes
+* @param create_func (@c cx_tree_node_create_func) a function that creates new nodes
-* @param search_func a function that compares two nodes
+* @param search_func (@c cx_tree_search_func) a function that compares two nodes
-* @param search_data_func a function that compares a node with data
+* @param search_data_func (@c cx_tree_search_data_func)  a function that compares a node with data
-* @return the new tree
+* @return (@c CxTree*) the new tree
 * @see cxTreeCreate()
 */
-__attribute__((__nonnull__, __warn_unused_result__))
+#define cxTreeCreateSimple(\
-static inline CxTree *cxTreeCreateSimple(
+allocator, create_func, search_func, search_data_func \
-const CxAllocator *allocator,
+) cxTreeCreate(allocator, create_func, search_func, search_data_func, \
-cx_tree_node_create_func create_func,
+cx_tree_node_base_layout)
-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.
+* 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,
 ptrdiff_t loc_parent,
 ptrdiff_t loc_children,
 ptrdiff_t loc_prev,
 ptrdiff_t loc_next
 );
 /**
-* 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
 ) {
 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
+* @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__))
+cx_attr_nonnull
 static inline size_t cxTreeInsertIter(
 CxTree *tree,
 struct cx_iterator_base_s *iter,
 size_t n
 ) {
 }
 /**
 * 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()).
 *
 * @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__))
+cx_attr_nonnull
 static inline size_t cxTreeInsertArray(
 CxTree *tree,
 const void *data,
 size_t elem_size,
 size_t n
 }
 /**
 * 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);
 }
 /**
 * 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__))
+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
+* @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);
 /**
 * Determines the depth of the entire tree.
 *
 * @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__))
+cx_attr_nonnull
-static inline CxTreeIterator cxTreeIterator(
+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);
 }
 /**
 * 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 cxTreeIterator()
+* @see cxTreeIterate()
 */
-__attribute__((__nonnull__, __warn_unused_result__))
+cx_attr_nonnull
-static inline CxTreeVisitor cxTreeVisitor(CxTree *tree) {
+cx_attr_nodiscard
-return tree->cl->visitor(tree);
+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) {
+void *child
-cx_tree_link(parent, child, cx_tree_node_layout(tree));
+);
-tree->size++;
-}
 /**
 * Creates a new node and adds it to the tree.
 *
 * With this function you can decide where exactly the new node shall be added.
 * @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__))
+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 #cxTreeRemove() so that those updates can be
+* This callback is invoked by #cxTreeRemoveNode() and #cxTreeDestroyNode()
-* applied when re-linking the children of the removed node.
+* 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
+* @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)))
+cx_attr_nonnull_arg(1, 2)
-int cxTreeRemove(
+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
+* @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

Mercurial > hg > toolkit / file comparison

comparison: ucx/cx/tree.h

ucx/cx/tree.h