Mercurial > hg > ucx / changeset

--- a/src/cx/tree.h	Sun Jan 05 13:44:02 2025 +0100
+++ b/src/cx/tree.h	Sun Jan 05 13:54:09 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;
 };
@@ -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
@@ -305,8 +305,8 @@
 /**
  * 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
@@ -335,8 +335,8 @@
 /**
  * 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
@@ -354,7 +354,7 @@
  * @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
  */
@@ -370,8 +370,8 @@
  *
  * 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
@@ -406,8 +406,8 @@
  *
  * 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
@@ -491,9 +491,9 @@
  * 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)
@@ -513,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
@@ -566,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
@@ -583,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
@@ -621,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().
@@ -727,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;
 
@@ -801,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; \
@@ -811,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),\
@@ -820,26 +829,15 @@
     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 {
     /**
      * 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.
      */
-    cx_attr_nonnull
     int (*insert_element)(
             struct cx_tree_s *tree,
             const void *data
@@ -851,7 +849,6 @@
      * 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,
@@ -861,7 +858,6 @@
     /**
      * Member function for finding a node.
      */
-    cx_attr_nonnull
     void *(*find)(
             struct cx_tree_s *tree,
             const void *subtree,
@@ -886,10 +882,10 @@
  * 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
+ * @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
+ * @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.
  *
@@ -910,7 +906,7 @@
  * 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
+ * @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.
@@ -928,7 +924,7 @@
  * 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
+ * @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
@@ -947,14 +943,14 @@
 /**
  * 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)
+ * (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
@@ -987,18 +983,18 @@
 /**
  * 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()
  */
 #define cxTreeCreateSimple(\
@@ -1009,15 +1005,15 @@
 /**
  * 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)
+ * (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
@@ -1045,13 +1041,14 @@
 /**
  * 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
  */
 cx_attr_nonnull
 static inline int cxTreeInsert(
@@ -1064,7 +1061,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()).
  *
@@ -1085,7 +1082,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()).
  *
@@ -1111,13 +1108,13 @@
 /**
  * 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
  */
 cx_attr_nonnull
 cx_attr_nodiscard
@@ -1131,13 +1128,13 @@
 /**
  * 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.
+ * 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
+ * @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()).
  *
@@ -1145,7 +1142,7 @@
  * @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
+ * @return the first matching node, or @c NULL when the data cannot be found
  */
 cx_attr_nonnull
 cx_attr_nodiscard
@@ -1174,7 +1171,7 @@
  *
  * @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
  */
 cx_attr_nonnull
 cx_attr_nodiscard
@@ -1191,7 +1188,7 @@
 size_t cxTreeDepth(CxTree *tree);
 
 /**
- * Creates a depth-first iterator for the specified tree starting in \p node.
+ * 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.
  *
@@ -1216,7 +1213,7 @@
 }
 
 /**
- * Creates a breadth-first iterator for the specified tree starting in \p node.
+ * 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.
  *
@@ -1267,7 +1264,7 @@
 /**
  * Sets the (new) parent of the specified child.
  *
- * If the \p child is not already member of the tree, this function behaves
+ * If the @p child is not already member of the tree, this function behaves
  * as #cxTreeAddChildNode().
  *
  * @param tree the tree
@@ -1285,10 +1282,10 @@
 /**
  * Adds a new node to the tree.
  *
- * If the \p child is already member of the tree, the behavior is undefined.
+ * 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
+ * @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).
  *
@@ -1352,14 +1349,14 @@
  *
  * 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
  */
 cx_attr_nonnull_arg(1, 2)
 int cxTreeRemoveNode(
@@ -1373,7 +1370,7 @@
  *
  * 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
@@ -1390,7 +1387,7 @@
  * 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
+ * @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.
  *
@@ -1398,7 +1395,7 @@
  * @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
+ * @return zero on success, non-zero if @p node is the root node of the tree
  */
 cx_attr_nonnull_arg(1, 2)
 int cxTreeDestroyNode(

--- a/src/tree.c	Sun Jan 05 13:44:02 2025 +0100
+++ b/src/tree.c	Sun Jan 05 13:54:09 2025 +0100
@@ -42,6 +42,13 @@
 #define cx_tree_ptr_locations \
     loc_parent, loc_children, loc_last_child, loc_prev, loc_next
 
+#define cx_tree_node_layout(tree) \
+    (tree)->loc_parent,\
+    (tree)->loc_children,\
+    (tree)->loc_last_child,\
+    (tree)->loc_prev,  \
+    (tree)->loc_next
+
 static void cx_tree_zero_pointers(
         void *node,
         ptrdiff_t loc_parent,