1.1 --- a/src/cx/tree.h Sun Oct 03 13:07:48 2021 +0200
1.2 +++ b/src/cx/tree.h Sun Oct 03 14:06:57 2021 +0200
1.3 @@ -25,6 +25,14 @@
1.4 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
1.5 * POSSIBILITY OF SUCH DAMAGE.
1.6 */
1.7 +/**
1.8 + * \file tree.h
1.9 + * \brief Interface for tree implementations.
1.10 + * \author Olaf Wintermann
1.11 + * \author Mike Becker
1.12 + * \version 3.0
1.13 + * \copyright 2-Clause BSD License
1.14 + */
1.15
1.16 #ifndef UCX_TREE_H
1.17 #define UCX_TREE_H
1.18 @@ -36,23 +44,93 @@
1.19 #ifdef __cplusplus
1.20 extern "C" {
1.21 #endif
1.22 -
1.23 -void* cx_tree_last(void *node, ptrdiff_t loc_next);
1.24 -
1.25 -int cx_tree_add_node(void *node, ptrdiff_t loc_parent, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node);
1.26
1.27 -int cx_tree_add_child_node(
1.28 - void *parent,
1.29 - ptrdiff_t loc_parent,
1.30 - ptrdiff_t loc_prev,
1.31 - ptrdiff_t loc_next,
1.32 - void **children_begin,
1.33 - void **children_end,
1.34 - void *new_node);
1.35 +/**
1.36 + * Adds a sibling to the current tree node.
1.37 + *
1.38 + * In case your struct does not have a \p prev or a \p parent pointer,
1.39 + * specify a negative location. The location of the \p next pointer is
1.40 + * mandatory.
1.41 + *
1.42 + * \attention Do not use this function to add siblings in a tree where the
1.43 + * nodes store a pointer to the last sibling because that would not be modified by this function.
1.44 + *
1.45 + * \remark If yo do not provide a location to the parent pointer, a call to this function is
1.46 + * effectively the same as a call to cx_linked_list_add().
1.47 + *
1.48 + * @param node a pointer to the node
1.49 + * @param loc_prev the location of a \c prev pointer within your node struct
1.50 + * @param loc_next the location of a \c next pointer within your node struct
1.51 + * @param loc_parent the location of a \c parent pointer within your node struct
1.52 + * @param new_node the new node that shall be added as a sibling
1.53 + */
1.54 +void cx_tree_add_sibling(void *node,
1.55 + ptrdiff_t loc_prev, ptrdiff_t loc_next,
1.56 + ptrdiff_t loc_parent,
1.57 + void *new_node)
1.58 +__attribute__((__nonnull__));
1.59 +
1.60 +/**
1.61 + * Adds a node to the list of children.
1.62 + *
1.63 + * \par Example with a full structure
1.64 + * A full tree node structure may look like this:
1.65 + * \code
1.66 + * typedef struct MyTreeNode MyTreeNode;
1.67 + * struct MyTreeNode {
1.68 + * MyTreeNode* parent;
1.69 + * MyTreeNode* first_child;
1.70 + * MyTreeNode* last_child;
1.71 + * MyTreeNode* prev_sibling;
1.72 + * MyTreeNode* next_sibling;
1.73 + * // ...contents...
1.74 + * }
1.75 + * \endcode
1.76 + * Adding a new child to a node with the above structure can be performed with the following call:
1.77 + * \code
1.78 + * MyTreeNode *node, *child; // given
1.79 + * cx_tree_add_child(&node->first_child, &node->last_child,
1.80 + * offsetof(MyTreeNode, prev_sibling), offsetof(MyTreeNode, next_sibling),
1.81 + * child, offsetof(MyTreeNode, parent), node);
1.82 + * \endcode
1.83 + *
1.84 + * \par Example with a reduced structure
1.85 + * The minimal reasonable structure with parent pointer looks like this:
1.86 + * \code
1.87 + * typedef struct MyTreeNode MyTreeNode;
1.88 + * struct MyTreeNode {
1.89 + * MyTreeNode* parent;
1.90 + * MyTreeNode* children;
1.91 + * MyTreeNode* next_sibling;
1.92 + * // ...contents...
1.93 + * }
1.94 + * \endcode
1.95 + * This simplifies the function call to:
1.96 + * \code
1.97 + * MyTreeNode *node, *child; // given
1.98 + * cx_tree_add_child(&node->children, NULL, -1, offsetof(MyTreeNode, next_sibling),
1.99 + * child, offsetof(MyTreeNode, parent), node);
1.100 + * \endcode
1.101 + *
1.102 + * \remark If your tree structure does not possess a parent pointer, a call to this function is
1.103 + * effectively the same as a call to cx_linked_list_add().
1.104 + *
1.105 + * @param children_begin a pointer to the begin node pointer (if your list has one)
1.106 + * @param children_end a pointer to the end node pointer (if your list has one)
1.107 + * @param loc_prev the location of a \c prev pointer within your node struct
1.108 + * @param loc_next the location of a \c next pointer within your node struct
1.109 + * @param new_node a pointer to the node that shall be appended
1.110 + * @param loc_parent the location of a \c parent pointer within your node struct
1.111 + * @param parent the parent node
1.112 + */
1.113 +void cx_tree_add_child(void **children_begin, void **children_end,
1.114 + ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node,
1.115 + ptrdiff_t loc_parent, void *parent)
1.116 +__attribute__((__nonnull__ (5)));
1.117
1.118
1.119 #ifdef __cplusplus
1.120 -}
1.121 +} /* extern "C" */
1.122 #endif
1.123
1.124 #endif /* UCX_TREE_H */
