diff -r ae61523bce20 -r 2f71f4ee247a ucx/cx/tree.h
--- a/ucx/cx/tree.h	Thu Oct 03 18:52:51 2024 +0200
+++ b/ucx/cx/tree.h	Sun Oct 06 18:18:04 2024 +0200
@@ -38,30 +38,1215 @@
 
 #include "common.h"
 
+#include "collection.h"
+
 #ifdef __cplusplus
 extern "C" {
 #endif
 
+/**
+ * A depth-first tree iterator.
+ *
+ * This iterator is not position-aware in a strict sense, as it does not assume
+ * a particular order of elements in the tree. However, the iterator keeps track
+ * of the number of nodes it has passed in a counter variable.
+ * Each node, regardless of the number of passes, is counted only once.
+ *
+ * @note Objects that are pointed to by an iterator are mutable through that
+ * iterator. However, if the
+ * underlying data structure is mutated by other means than this iterator (e.g.
+ * elements added or removed), the iterator becomes invalid (regardless of what
+ * cxIteratorValid() returns).
+ *
+ * @see CxIterator
+ */
+typedef struct cx_tree_iterator_s {
+    /**
+     * Base members.
+     */
+    CX_ITERATOR_BASE;
+    /**
+     * Indicates whether the subtree below the current node shall be skipped.
+     */
+    bool skip;
+    /**
+     * Set to true, when the iterator shall visit a node again
+     * when all it's children have been processed.
+     */
+    bool visit_on_exit;
+    /**
+     * True, if this iterator is currently leaving the node.
+     */
+    bool exiting;
+    /**
+     * Offset in the node struct for the children linked list.
+     */
+    ptrdiff_t loc_children;
+    /**
+     * Offset in the node struct for the next pointer.
+     */
+    ptrdiff_t loc_next;
+    /**
+     * The total number of distinct nodes that have been passed so far.
+     */
+    size_t counter;
+    /**
+     * The currently observed node.
+     *
+     * This is the same what cxIteratorCurrent() would return.
+     */
+    void *node;
+    /**
+     * Stores a copy of the next pointer of the visited node.
+     * Allows freeing a node on exit without corrupting the iteration.
+     */
+    void *node_next;
+    /**
+     * Internal stack.
+     * Will be automatically freed once the iterator becomes invalid.
+     *
+     * If you want to discard the iterator before, you need to manually
+     * call cxTreeIteratorDispose().
+     */
+    void **stack;
+    /**
+     * Internal capacity of the stack.
+     */
+    size_t stack_capacity;
+    union {
+        /**
+         * Internal stack size.
+         */
+        size_t stack_size;
+        /**
+         * The current depth in the tree.
+         */
+        size_t depth;
+    };
+} CxTreeIterator;
 
+/**
+ * An element in a visitor queue.
+ */
+struct cx_tree_visitor_queue_s {
+    /**
+     * The tree node to visit.
+     */
+    void *node;
+    /**
+     * The depth of the node.
+     */
+    size_t depth;
+    /**
+     * The next element in the queue or \c NULL.
+     */
+    struct cx_tree_visitor_queue_s *next;
+};
+
+/**
+ * A breadth-first tree iterator.
+ *
+ * This iterator needs to maintain a visitor queue that will be automatically
+ * freed once the iterator becomes invalid.
+ * If you want to discard the iterator before, you MUST manually call
+ * cxTreeVisitorDispose().
+ *
+ * This iterator is not position-aware in a strict sense, as it does not assume
+ * a particular order of elements in the tree. However, the iterator keeps track
+ * of the number of nodes it has passed in a counter variable.
+ * Each node, regardless of the number of passes, is counted only once.
+ *
+ * @note Objects that are pointed to by an iterator are mutable through that
+ * iterator. However, if the
+ * underlying data structure is mutated by other means than this iterator (e.g.
+ * elements added or removed), the iterator becomes invalid (regardless of what
+ * cxIteratorValid() returns).
+ *
+ * @see CxIterator
+ */
+typedef struct cx_tree_visitor_s {
+    /**
+     * Base members.
+     */
+    CX_ITERATOR_BASE;
+    /**
+     * Indicates whether the subtree below the current node shall be skipped.
+     */
+    bool skip;
+    /**
+     * Offset in the node struct for the children linked list.
+     */
+    ptrdiff_t loc_children;
+    /**
+     * Offset in the node struct for the next pointer.
+     */
+    ptrdiff_t loc_next;
+    /**
+     * The total number of distinct nodes that have been passed so far.
+     */
+    size_t counter;
+    /**
+     * The currently observed node.
+     *
+     * This is the same what cxIteratorCurrent() would return.
+     */
+    void *node;
+    /**
+     * The current depth in the tree.
+     */
+    size_t depth;
+    /**
+     * The next element in the visitor queue.
+     */
+    struct cx_tree_visitor_queue_s *queue_next;
+    /**
+     * The last element in the visitor queue.
+     */
+    struct cx_tree_visitor_queue_s *queue_last;
+} CxTreeVisitor;
+
+/**
+ * Releases internal memory of the given tree iterator.
+ * @param iter the iterator
+ */
+ __attribute__((__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__))
+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);
+        q = next;
+    }
+}
+
+/**
+ * Advises the iterator to skip the subtree below the current node and
+ * also continues the current loop.
+ *
+ * @param iterator 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
+ */
+#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
+ * 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_next offset in the node struct for the next pointer
+ * @see cx_tree_unlink()
+ */
 __attribute__((__nonnull__))
 void cx_tree_link(
-        void * restrict parent,
-        void * restrict node,
+        void *restrict parent,
+        void *restrict node,
         ptrdiff_t loc_parent,
         ptrdiff_t loc_children,
+        ptrdiff_t loc_last_child,
         ptrdiff_t loc_prev,
         ptrdiff_t loc_next
 );
 
+/**
+ * Unlinks a node from its parent.
+ *
+ * If the node has no parent, this function does nothing.
+ *
+ * @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_next offset in the node struct for the next pointer
+ * @see cx_tree_link()
+ */
 __attribute__((__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
+);
+
+/**
+ * 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
+ * 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.
+ *
+ * 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
+ * prefix of the searched filename, the function would return -1 to indicate
+ * that the search does not need to be continued in that branch.
+ *
+ * @param node the node that is currently investigated
+ * @param data the data that is searched for
+ *
+ * @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
+ */
+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
+ * 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.
+ *
+ * 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
+ * prefix of the searched filename, the function would return -1 to indicate
+ * 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,
+ * positive if one of the children might contain the data,
+ * negative if neither the node, nor the children contains the data
+ */
+typedef int (*cx_tree_search_func)(const void *node, const void *new_node);
+
+/**
+ * Searches for data in a tree.
+ *
+ * When the data cannot be found exactly, the search function might return a
+ * 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
+ * \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 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__))
+int cx_tree_search_data(
+        const void *root,
+        const void *data,
+        cx_tree_search_data_func sfunc,
+        void **result,
+        ptrdiff_t loc_children,
+        ptrdiff_t loc_next
+);
+
+/**
+ * Searches for a node in a tree.
+ *
+ * When no node with the same data can be found, the search function might
+ * 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
+ * \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 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__))
+int cx_tree_search(
+        const void *root,
+        const void *node,
+        cx_tree_search_func sfunc,
+        void **result,
+        ptrdiff_t loc_children,
+        ptrdiff_t loc_next
+);
+
+/**
+ * Creates a depth-first iterator for a tree with the specified root node.
+ *
+ * @note A tree iterator needs to maintain a stack of visited nodes, which is
+ * allocated using stdlib malloc().
+ * When the iterator becomes invalid, this memory is automatically released.
+ * However, if you wish to cancel the iteration before the iterator becomes
+ * invalid by itself, you MUST call cxTreeIteratorDispose() manually to release
+ * the memory.
+ *
+ * @remark The returned iterator does not support cxIteratorFlagRemoval().
+ *
+ * @param root the root node
+ * @param visit_on_exit set to true, when the iterator shall visit a node again
+ * after processing all children
+ * @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()
+ */
+CxTreeIterator cx_tree_iterator(
+        void *root,
+        bool visit_on_exit,
+        ptrdiff_t loc_children,
+        ptrdiff_t loc_next
+);
+
+/**
+ * Creates a breadth-first iterator for a tree with the specified root node.
+ *
+ * @note A tree visitor needs to maintain a queue of to be visited nodes, which
+ * is allocated using stdlib malloc().
+ * When the visitor becomes invalid, this memory is automatically released.
+ * However, if you wish to cancel the iteration before the visitor becomes
+ * invalid by itself, you MUST call cxTreeVisitorDispose() manually to release
+ * the memory.
+ *
+ * @remark The returned iterator does not support cxIteratorFlagRemoval().
+ *
+ * @param root the root node
+ * @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()
+ */
+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.
+ *
+ * \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.
+ */
+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.
+ * This variable is used by #cx_tree_add_array() and #cx_tree_add_iter() to
+ * implement optimized insertion of multiple elements into a tree.
+ */
+extern unsigned int cx_tree_add_look_around_depth;
+
+/**
+ * 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.
+ * 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.
+ *
+ * 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
+ * of the current insert location before starting from the root node again.
+ * When the variable is set to zero, only the last found location is checked
+ * again.
+ *
+ * Refer to the documentation of #cx_tree_add() for more details.
+ *
+ * @param iter a pointer to an arbitrary iterator
+ * @param num the maximum number of elements to obtain from the iterator
+ * @param sfunc a search function
+ * @param cfunc a node creation function
+ * @param cdata optional additional data
+ * @param root the root node of the tree
+ * @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_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)))
+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,
+        void *cdata,
+        void **failed,
+        void *root,
+        ptrdiff_t loc_parent,
+        ptrdiff_t loc_children,
+        ptrdiff_t loc_last_child,
+        ptrdiff_t loc_prev,
+        ptrdiff_t loc_next
+);
+
+/**
+ * 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 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 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
+ * of the current insert location before starting from the root node again.
+ * When the variable is set to zero, only the last found location is checked
+ * 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 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_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)))
+size_t cx_tree_add_array(
+        const void *src,
+        size_t num,
+        size_t elem_size,
+        cx_tree_search_func sfunc,
+        cx_tree_node_create_func cfunc,
+        void *cdata,
+        void **failed,
+        void *root,
+        ptrdiff_t loc_parent,
+        ptrdiff_t loc_children,
+        ptrdiff_t loc_last_child,
+        ptrdiff_t loc_prev,
+        ptrdiff_t loc_next
+);
+
+/**
+ * Adds data to a tree.
+ *
+ * An adequate location where to add the new tree node is searched with the
+ * specified \p sfunc.
+ *
+ * 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
+ * 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
+ * accordingly.
+ *
+ * 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
+ * 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
+ * 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.
+ *
+ * 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 sfunc a search function
+ * @param cfunc a node creation function
+ * @param cdata optional additional data
+ * @param cnode the location where a pointer to the new node is 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_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)))
+int cx_tree_add(
+        const void *src,
+        cx_tree_search_func sfunc,
+        cx_tree_node_create_func cfunc,
+        void *cdata,
+        void **cnode,
+        void *root,
+        ptrdiff_t loc_parent,
+        ptrdiff_t loc_children,
+        ptrdiff_t loc_last_child,
         ptrdiff_t loc_prev,
         ptrdiff_t loc_next
 );
 
+
+/**
+ * Tree class type.
+ */
+typedef struct cx_tree_class_s cx_tree_class;
+
+/**
+ * Base structure that can be used for tree nodes in a #CxTree.
+ */
+struct cx_tree_node_base_s {
+    /**
+     * Pointer to the parent.
+     */
+    struct cx_tree_node_base_s *parent;
+    /**
+     * Pointer to the first child.
+     */
+    struct cx_tree_node_base_s *children;
+    /**
+     * Pointer to the last child.
+     */
+    struct cx_tree_node_base_s *last_child;
+    /**
+     * Pointer to the previous sibling.
+     */
+    struct cx_tree_node_base_s *prev;
+    /**
+     * Pointer to the next sibling.
+     */
+    struct cx_tree_node_base_s *next;
+};
+
+/**
+ * Structure for holding the base data of a tree.
+ */
+struct cx_tree_s {
+    /**
+     * The tree class definition.
+     */
+    const cx_tree_class *cl;
+
+    /**
+     * Allocator to allocate new nodes.
+     */
+    const CxAllocator *allocator;
+
+    /**
+     * A pointer to the root node.
+     *
+     * Will be \c NULL when \c size is 0.
+     */
+    void *root;
+
+    /**
+     * A function to create new nodes.
+     *
+     * Invocations to this function will receive a pointer to this tree
+     * structure as second argument.
+     *
+     * Nodes MAY use #cx_tree_node_base_s as base layout, but do not need to.
+     */
+    cx_tree_node_create_func node_create;
+
+    /**
+     * An optional simple destructor for the tree nodes.
+     */
+    cx_destructor_func simple_destructor;
+
+    /**
+     * An optional advanced destructor for the tree nodes.
+     */
+    cx_destructor_func2 advanced_destructor;
+
+    /**
+     * The pointer to additional data that is passed to the advanced destructor.
+     */
+    void *destructor_data;
+
+    /**
+     * A function to compare two nodes.
+     */
+    cx_tree_search_func search;
+
+    /**
+     * A function to compare a node with data.
+     */
+    cx_tree_search_data_func search_data;
+
+    /**
+     * The number of currently stored elements.
+     */
+    size_t size;
+
+    /**
+     * Offset in the node struct for the parent pointer.
+     */
+    ptrdiff_t loc_parent;
+
+    /**
+     * Offset in the node struct for the children linked list.
+     */
+    ptrdiff_t loc_children;
+
+    /**
+     * Optional offset in the node struct for the pointer to the last child
+     * in the linked list (negative if there is no such pointer).
+     */
+    ptrdiff_t loc_last_child;
+
+    /**
+     * Offset in the node struct for the previous sibling pointer.
+     */
+    ptrdiff_t loc_prev;
+
+    /**
+     * Offset in the node struct for the next sibling pointer.
+     */
+    ptrdiff_t loc_next;
+};
+
+/**
+ * Macro to roll out the #cx_tree_node_base_s structure with a custom
+ * node type.
+ */
+#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.
+ */
+#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
+     * with too much overhead.
+     */
+    int (*insert_element)(
+            struct cx_tree_s *tree,
+            const void *data
+    );
+
+    /**
+     * Member function for inserting multiple elements.
+     *
+     * Implementations SHALL avoid to perform a full search in the tree for
+     * every element even though the source data MAY be unsorted.
+     */
+    size_t (*insert_many)(
+            struct cx_tree_s *tree,
+            struct cx_iterator_base_s *iter,
+            size_t n
+    );
+
+    /**
+     * Member function for finding a node.
+     */
+    void *(*find)(
+            struct cx_tree_s *tree,
+            const void *subtree,
+            const void *data
+    );
+
+    /**
+     * 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;
+
+/**
+ * Creates a new tree structure based on the specified layout.
+ *
+ * The specified \p allocator will be used for creating the tree struct
+ * and SHALL be used by \p create_func to allocate memory for the nodes.
+ *
+ * \note This function will also register an advanced destructor which
+ * will free the nodes with the allocator's free() method.
+ *
+ * @param allocator the allocator that shall be used
+ * @param create_func a function that creates new nodes
+ * @param search_func a function that compares two nodes
+ * @param search_data_func a function that compares a node with data
+ * @param loc_parent offset in the node struct for the parent pointer
+ * @param loc_children offset in the node struct for the children linked list
+ * @param loc_last_child optional offset in the node struct for the pointer to
+ * the last child in the linked list (negative if there is no such pointer)
+ * @param loc_prev offset in the node struct for the prev pointer
+ * @param loc_next offset in the node struct for the next pointer
+ * @return the new tree
+ * @see cxTreeCreateSimple()
+ * @see cxTreeCreateWrapped()
+ */
+__attribute__((__nonnull__, __warn_unused_result__))
+CxTree *cxTreeCreate(
+        const CxAllocator *allocator,
+        cx_tree_node_create_func create_func,
+        cx_tree_search_func search_func,
+        cx_tree_search_data_func search_data_func,
+        ptrdiff_t loc_parent,
+        ptrdiff_t loc_children,
+        ptrdiff_t loc_last_child,
+        ptrdiff_t loc_prev,
+        ptrdiff_t loc_next
+);
+
+/**
+ * Creates a new tree structure based on a default layout.
+ *
+ * Nodes created by \p create_func MUST contain #cx_tree_node_base_s as first
+ * member (or at least respect the default offsets specified in the tree
+ * struct) and they MUST be allocated with the specified allocator.
+ *
+ * \note This function will also register an advanced destructor which
+ * will free the nodes with the allocator's free() method.
+ *
+ * @param allocator the allocator that shall be used
+ * @param create_func a function that creates new nodes
+ * @param search_func a function that compares two nodes
+ * @param search_data_func a function that compares a node with data
+ * @return the new tree
+ * @see cxTreeCreate()
+ */
+__attribute__((__nonnull__, __warn_unused_result__))
+static inline CxTree *cxTreeCreateSimple(
+        const CxAllocator *allocator,
+        cx_tree_node_create_func create_func,
+        cx_tree_search_func search_func,
+        cx_tree_search_data_func search_data_func
+) {
+    return cxTreeCreate(
+            allocator,
+            create_func,
+            search_func,
+            search_data_func,
+            cx_tree_node_base_layout
+    );
+}
+
+/**
+ * Creates a new tree structure based on an existing tree.
+ *
+ * The specified \p allocator will be used for creating the tree struct.
+ *
+ * \attention This function will create an incompletely defined tree structure
+ * where neither the create function, the search function, nor a destructor
+ * will be set. If you wish to use any of this functionality for the wrapped
+ * tree, you need to specify those functions afterwards.
+ *
+ * @param 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_next offset in the node struct for the next pointer
+ * @return the new tree
+ * @see cxTreeCreate()
+ */
+__attribute__((__nonnull__, __warn_unused_result__))
+CxTree *cxTreeCreateWrapped(
+        const CxAllocator *allocator,
+        void *root,
+        ptrdiff_t loc_parent,
+        ptrdiff_t loc_children,
+        ptrdiff_t loc_last_child,
+        ptrdiff_t loc_prev,
+        ptrdiff_t loc_next
+);
+
+/**
+ * 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
+ * create functions, which might not be available for wrapped trees
+ * (see #cxTreeCreateWrapped()).
+ *
+ * @param tree the tree
+ * @param data the data to insert
+ * @return zero on success, non-zero on failure
+ */
+__attribute__((__nonnull__))
+static inline int cxTreeInsert(
+        CxTree *tree,
+        const void *data
+) {
+    return tree->cl->insert_element(tree, data);
+}
+
+/**
+ * Inserts elements provided by an iterator efficiently into the tree.
+ *
+ * \remark For this function to work, the tree needs specified search and
+ * create functions, which might not be available for wrapped trees
+ * (see #cxTreeCreateWrapped()).
+ *
+ * @param tree the tree
+ * @param iter the iterator providing the elements
+ * @param n the maximum number of elements to insert
+ * @return the number of elements that could be successfully inserted
+ */
+__attribute__((__nonnull__))
+static inline size_t cxTreeInsertIter(
+        CxTree *tree,
+        struct cx_iterator_base_s *iter,
+        size_t n
+) {
+    return tree->cl->insert_many(tree, iter, n);
+}
+
+/**
+ * Inserts an array of data efficiently into the tree.
+ *
+ * \remark For this function to work, the tree needs specified search and
+ * create functions, which might not be available for wrapped trees
+ * (see #cxTreeCreateWrapped()).
+ *
+ * @param tree the tree
+ * @param data the array of data to insert
+ * @param elem_size the size of each element in the array
+ * @param n the number of elements in the array
+ * @return the number of elements that could be successfully inserted
+ */
+__attribute__((__nonnull__))
+static inline size_t cxTreeInsertArray(
+        CxTree *tree,
+        const void *data,
+        size_t elem_size,
+        size_t n
+) {
+    if (n == 0) return 0;
+    if (n == 1) return 0 == cxTreeInsert(tree, data) ? 1 : 0;
+    CxIterator iter = cxIterator(data, elem_size, n);
+    return cxTreeInsertIter(tree, cxIteratorRef(iter), n);
+}
+
+/**
+ * Searches the data in the specified tree.
+ *
+ * \remark For this function to work, the tree needs a specified \c search_data
+ * function, which might not be available wrapped trees
+ * (see #cxTreeCreateWrapped()).
+ *
+ * @param tree the tree
+ * @param data the data to search for
+ * @return the first matching node, or \c NULL when the data cannot be found
+ */
+__attribute__((__nonnull__))
+static inline void *cxTreeFind(
+        CxTree *tree,
+        const void *data
+) {
+    return tree->cl->find(tree, tree->root, data);
+}
+
+/**
+ * Searches the data in the specified subtree.
+ *
+ * \note When \p subtree_root is not part of the \p tree, the behavior is
+ * undefined.
+ *
+ * \remark For this function to work, the tree needs a specified \c search_data
+ * function, which might not be the case for wrapped trees
+ * (see #cxTreeCreateWrapped()).
+ *
+ * @param tree the tree
+ * @param data the data to search for
+ * @param subtree_root the node where to start
+ * @return the first matching node, or \c NULL when the data cannot be found
+ */
+__attribute__((__nonnull__))
+static inline void *cxTreeFindInSubtree(
+        CxTree *tree,
+        const void *data,
+        void *subtree_root
+) {
+    return tree->cl->find(tree, subtree_root, data);
+}
+
+/**
+ * Determines the size of the specified subtree.
+ *
+ * @param tree the tree
+ * @param subtree_root the root node of the subtree
+ * @return the number of nodes in the specified subtree
+ */
+__attribute__((__nonnull__))
+size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root);
+
+/**
+ * Determines the depth of the specified subtree.
+ *
+ * @param tree the tree
+ * @param subtree_root the root node of the subtree
+ * @return the tree depth including the \p subtree_root
+ */
+__attribute__((__nonnull__))
+size_t cxTreeSubtreeDepth(CxTree *tree, void *subtree_root);
+
+/**
+ * Determines the depth of the entire tree.
+ *
+ * @param tree the tree
+ * @return the tree depth, counting the root as one
+ */
+__attribute__((__nonnull__))
+size_t cxTreeDepth(CxTree *tree);
+
+/**
+ * Creates a depth-first iterator for the specified tree.
+ *
+ * @param tree the tree to iterate
+ * @param visit_on_exit true, if the iterator shall visit a node again when
+ * leaving the sub-tree
+ * @return a tree iterator (depth-first)
+ * @see cxTreeVisitor()
+ */
+__attribute__((__nonnull__, __warn_unused_result__))
+static inline CxTreeIterator cxTreeIterator(
+        CxTree *tree,
+        bool visit_on_exit
+) {
+    return tree->cl->iterator(tree, 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()
+ */
+__attribute__((__nonnull__, __warn_unused_result__))
+static inline CxTreeVisitor cxTreeVisitor(CxTree *tree) {
+    return tree->cl->visitor(tree);
+}
+
+/**
+ * Adds a new node to the tree.
+ *
+ * \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
+ */
+__attribute__((__nonnull__))
+static inline void cxTreeAddChildNode(
+        CxTree *tree,
+        void *parent,
+        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.
+ * If you specified an appropriate search function, you may want to consider
+ * leaving this task to the tree by using #cxTreeInsert().
+ *
+ * Be aware that adding nodes at arbitrary locations in the tree might cause
+ * wrong or undesired results when subsequently invoking #cxTreeInsert() and
+ * the invariant imposed by the search function does not hold any longer.
+ *
+ * @param tree the tree
+ * @param parent the parent node of the new node
+ * @param data the data that will be submitted to the create function
+ * @return zero when the new node was created, non-zero on allocation failure
+ * @see cxTreeInsert()
+ */
+__attribute__((__nonnull__))
+int cxTreeAddChild(
+        CxTree *tree,
+        void *parent,
+        const void *data
+);
+
+/**
+ * A function that is invoked when a node needs to be re-linked to a new parent.
+ *
+ * When a node is re-linked, sometimes the contents need to be updated.
+ * This callback is invoked by #cxTreeRemove() so that those updates can be
+ * applied when re-linking the children of the removed node.
+ *
+ * @param node the affected node
+ * @param old_parent the old parent of the node
+ * @param new_parent the new parent of the node
+ */
+typedef void (*cx_tree_relink_func)(
+        void *node,
+        const void *old_parent,
+        const void *new_parent
+);
+
+/**
+ * Removes a node and re-links its children to its former parent.
+ *
+ * If the node is not part of the tree, the behavior is undefined.
+ *
+ * \note The destructor function, if any, will \em not be invoked. That means
+ * you will need to free the removed node by yourself, eventually.
+ *
+ * @param tree the tree
+ * @param node the node to remove (must not be the root node)
+ * @param relink_func optional callback to update the content of each re-linked
+ * node
+ * @return zero on success, non-zero if \p node is the root node of the tree
+ */
+__attribute__((__nonnull__(1,2)))
+int cxTreeRemove(
+        CxTree *tree,
+        void *node,
+        cx_tree_relink_func relink_func
+);
+
+/**
+ * Removes a node and it's subtree from the tree.
+ *
+ * If the node is not part of the tree, the behavior is undefined.
+ *
+ * \note The destructor function, if any, will \em not be invoked. That means
+ * you will need to free the removed subtree by yourself, eventually.
+ *
+ * @param tree the tree
+ * @param node the node to remove
+ */
+__attribute__((__nonnull__))
+void cxTreeRemoveSubtree(CxTree *tree, void *node);
+
 #ifdef __cplusplus
 } // extern "C"
 #endif