src/cx/tree.h

/*
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
 *
 * Copyright 2024 Mike Becker, Olaf Wintermann All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 *   1. Redistributions of source code must retain the above copyright
 *      notice, this list of conditions and the following disclaimer.
 *
 *   2. Redistributions in binary form must reproduce the above copyright
 *      notice, this list of conditions and the following disclaimer in the
 *      documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * 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
 * \brief Interface for tree implementations.
 * \author Mike Becker
 * \author Olaf Wintermann
 * \copyright 2-Clause BSD License
 */

#ifndef UCX_TREE_H
#define UCX_TREE_H

#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 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__))
void cx_tree_link(
        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 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__))
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
 * 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
 * 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.
 * 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
 * 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 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__))
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
);

/**
 * 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 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__))
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
);

/**
 * 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 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)))
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 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)))
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 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)))
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 {
    /**
     * 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,
            size_t depth
    );
};

/**
 * 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 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__))
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 allocator the allocator that was used for nodes of the wrapped tree
 * @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 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__))
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
);

/**
 * 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, 0);
}

/**
 * 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.
 *
 * \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
 * @param max_depth the maximum search depth
 * @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,
        size_t max_depth
) {
    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__))
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 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()
 */
__attribute__((__nonnull__, __warn_unused_result__))
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()
 */
__attribute__((__nonnull__, __warn_unused_result__))
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 subtree
 * @return a tree iterator (depth-first)
 * @see cxTreeVisit()
 */
__attribute__((__nonnull__, __warn_unused_result__))
static inline CxTreeIterator cxTreeIterate(
        CxTree *tree,
        bool 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 cxTreeIterate()
 */
__attribute__((__nonnull__, __warn_unused_result__))
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()
 */
__attribute__((__nonnull__))
void cxTreeSetParent(
        CxTree *tree,
        void *parent,
        void *child
);

/**
 * Adds a new node to the tree.
 *
 * 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__))
void cxTreeAddChildNode(
        CxTree *tree,
        void *parent,
        void *child
);

/**
 * 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 #cxTreeRemoveNode() and #cxTreeDestroyNode()
 * so that those updates can be applied when re-linking the children of the
 * removed node.
 *
 * @param node the affected node
 * @param old_parent the old parent of the node
 * @param new_parent the new parent of the node
 */
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 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
 * 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);

/**
 * 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
 */
__attribute__((__nonnull__(1,2)))
int cxTreeDestroyNode(
        CxTree *tree,
        void *node,
        cx_tree_relink_func relink_func
);

/**
 * 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 #cxTreeDestroy() - 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 cxTreeDestroy()
 */
__attribute__((__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)

/**
 * Destroys 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 destroy
 */
__attribute__((__nonnull__))
static inline void cxTreeDestroy(CxTree *tree) {
    if (tree->root != NULL) {
        cxTreeDestroySubtree(tree, tree->root);
    }
    cxFree(tree->allocator, tree);
}

#ifdef __cplusplus
} // extern "C"
#endif

#endif //UCX_TREE_H