Mercurial > hg > ucx / file revision

/*
 * 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"

/**
 * An element in a visitor queue.
 */
struct cx_tree_visitor_queue_s {
    /**
     * The tree node to visit.
     */
    void *node;
    /**
     * The depth of the node.
     * The first visited node has depth 1.
     */
    size_t depth;
    /**
     * The next element in the queue or @c NULL.
     */
    struct cx_tree_visitor_queue_s *next;
};

typedef struct cx_tree_combined_iterator_s {
    /**
     * Base members.
     */
    CX_ITERATOR_BASE;
    /**
     * 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.
     * This includes the currently visited node.
     */
    size_t counter;
    /**
     * The current depth in the tree.
     */
    size_t depth;
    /**
     * The currently observed node.
     *
     * This is the same what cxIteratorCurrent() would return.
     */
    void *node;
    /**
     * Memory for BFS or DFS-specific data.
     */
    union {
        struct {
            /**
             * Stores a copy of the pointer to the successor 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;
        };
        struct {
            /**
             * 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;
        };
    };
    /**
     * 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 its children have been processed.
     */
    bool visit_on_exit;
    /**
     * True, if this iterator is currently leaving the node.
     */
    bool exiting;
    /**
     * Indicates whether the @c iterator (true) or the @c visitor (false) aspect is active.
     */
    bool use_dfs;
} CxTreeIterator;

/**
 * Releases internal memory of the given tree iterator.
 * @param iter the iterator
 */
CX_EXTERN CX_NONNULL
void cxTreeIteratorDispose(CxTreeIterator *iter);

/**
 * Advises the iterator to skip the subtree below the current node and
 * also continues the current loop.
 *
 * @param iterator (@c CxTreeIterator) the iterator
 */
#define cxTreeIteratorContinue(iterator) (iterator).skip = true; continue

/**
 * Links a node to a (new) parent.
 *
 * If the node already has 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_remove()
 */
CX_EXTERN CX_NONNULL
void cx_tree_add(void *parent, void *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_add()
 */
CX_EXTERN CX_NONNULL
void cx_tree_remove(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, consider a tree that stores file path information.
 * A node which is describing a parent directory of a searched file 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_func)(const void *node, const void *data);

/**
 * Searches for data in a tree.
 *
 * When the data cannot be found exactly, the search function might return the
 * closest result, which might be a good starting point for adding a new node
 * to the tree.
 *
 * 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 max_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
 */
CX_EXTERN CX_NONNULL_ARG(4, 5) CX_ACCESS_W(5)
int cx_tree_search(const void *root, size_t max_depth,
        const void *data, 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 the cxDefaultAllocator.
 * 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()
 */
CX_EXTERN CX_NODISCARD
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 the cxDefaultAllocator.
 * 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 cxTreeIteratorDispose() 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 cxTreeIteratorDispose()
 */
CX_EXTERN CX_NODISCARD
CxTreeIterator cx_tree_visitor(void *root,
        ptrdiff_t loc_children, ptrdiff_t loc_next);

/**
 * 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.
 */
typedef struct cx_tree_s {
    CX_COLLECTION_BASE;
    /**
     * A pointer to the root node.
     *
     * Will be @c NULL when @c size is 0.
     */
    void *root;

    /**
     * The size of the node structure.
     */
    size_t node_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;

    /**
     * Offset in the node struct where the payload is located.
     */
    ptrdiff_t loc_data;
} CxTree;

/**
 * Macro to roll out the #cx_tree_node_base_s structure with a custom
 * node type.
 *
 * Must be used as the first member in your custom tree struct.
 *
 * @param type the data type for the nodes
 */
#define CX_TREE_NODE(type) \
    type *parent; \
    type *children;\
    type *last_child;\
    type *prev;\
    type *next

/**
 * Macro for specifying the layout of a tree node.
 *
 * When your tree uses #CX_TREE_NODE, 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.
 * @param struct_name the name of the node structure
 */
#define cx_tree_node_layout(struct_name) \
    offsetof(struct_name, parent),\
    offsetof(struct_name, children),\
    offsetof(struct_name, last_child),\
    offsetof(struct_name, prev),  \
    offsetof(struct_name, next)

/**
 * Destroys a node and its subtree.
 *
 * It is guaranteed that the simple destructor is invoked before
 * the advanced destructor, starting with the leaf nodes of the subtree.
 *
 * When this function is invoked on the root node of the tree, it destroys the
 * tree contents, but - in contrast to #cxTreeFree() - not the tree
 * structure, leaving an empty tree behind.
 *
 * @note The destructor function, if any, will @em not be invoked. That means
 * you will need to free the removed subtree by yourself, eventually.
 *
 * @attention This function will not free the memory of the nodes with the
 * tree's allocator, because that is usually done by the advanced destructor
 * and would therefore result in a double-free.
 *
 * @param tree the tree
 * @param node the node being the root of the subtree to remove
 * @see cxTreeFree()
 */
CX_EXTERN CX_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()
 */
CX_INLINE
void cxTreeClear(CxTree *tree) {
    if (tree->root != NULL) {
        cxTreeDestroySubtree(tree, tree->root);
    }
}

/**
 * Deallocates the tree structure.
 *
 * The destructor functions are invoked for each node, starting with the leaf
 * nodes.
 * It is guaranteed that for each node the simple destructor is invoked before
 * the advanced destructor.
 *
 * @attention This function will only invoke the destructor functions
 * on the nodes.
 * It will NOT additionally free the nodes with the tree's allocator, because
 * that would cause a double-free in most scenarios where the advanced
 * destructor is already freeing the memory.
 *
 * @param tree the tree to free
 */
CX_EXTERN
void cxTreeFree(CxTree *tree);

/**
 * Creates a new tree.
 *
 * The specified @p allocator will be used for creating the tree struct
 * @em and the nodes.
 *
 * When you do not specify an existing @p root, the tree will be created
 * empty. Additionally, cxFree() is registered as the advanced destructor for
 * the tree so that all nodes that you will add to the tree are automatically
 * freed together with the tree.
 * When @p root is not @c NULL, no destructors are registered automatically.
 *
 * @param allocator the allocator to use
 * (if @c NULL, the cxDefaultAllocator is assumed)
 * @param node_size the complete size of one node
 * @param elem_size the size of the payload stored in the node
 * (@c CX_STORE_POINTERS is also supported)
 * @param root an optional already existing root node
 * @param loc_data optional offset in the node struct for the payload
 * (when negative, cxTreeAddData() is not supported)
 * @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()
 */
CX_EXTERN CX_NODISCARD  CX_MALLOC  CX_DEALLOC(cxTreeFree, 1)
CxTree *cxTreeCreate(const CxAllocator *allocator,
        size_t node_size, size_t elem_size, void *root, ptrdiff_t loc_data,
        ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
        ptrdiff_t loc_prev, ptrdiff_t loc_next);

/**
 * 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 @c NULL and not part of the @p tree,
 * the behavior is undefined.
 *
 * @attention When @p loc_data is not available, this function immediately returns
 * @c NULL.
 *
 * @param tree the tree
 * @param data the data to search for
 * @param subtree_root the node where to start (@c NULL to start from root)
 * @param max_depth the maximum search depth
 * @param use_dfs @c true when depth-first search should be used;
 * @c false when breadth-first search should be used
 * @return the first matching node, or @c NULL when the data cannot be found
 * @see cxTreeFind()
 */
CX_EXTERN CX_NONNULL_ARG(1, 2) CX_NODISCARD
void *cxTreeFindInSubtree(CxTree *tree, const void *data, void *subtree_root,
        size_t max_depth, bool use_dfs);

/**
 * Searches the data in the specified tree.
 *
 * @attention When @p loc_data is not available, this function immediately returns
 * @c NULL.
 *
 * @param tree the tree
 * @param data the data to search for
 * @param use_dfs @c true when depth-first search should be used;
 * @c false when breadth-first search should be used
 * @return the first matching node, or @c NULL when the data cannot be found
 * @see cxTreeFindInSubtree()
 * @see cxTreeFindFast()
 */
CX_INLINE CX_NONNULL CX_NODISCARD
void *cxTreeFind(CxTree *tree, const void *data, bool use_dfs) {
    if (tree->root == NULL) return NULL;
    return cxTreeFindInSubtree(tree, data, tree->root, 0, use_dfs);
}

/**
 * Performs an efficient depth-first search in a branch of the specified tree.
 *
 * 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 @c NULL and not part of the @p tree,
 * the behavior is undefined.
 *
 * @param tree the tree
 * @param data the data to search for
 * @param sfunc the search function
 * @param subtree_root the node where to start (@c NULL to start from root)
 * @param max_depth the maximum search depth
 * @return the first matching node, or @c NULL when the data cannot be found
 * @see cxTreeFindInSubtree()
 */
CX_EXTERN CX_NONNULL CX_NODISCARD
void *cxTreeFindFastInSubtree(CxTree *tree, const void *data,
        cx_tree_search_func sfunc, void *subtree_root, size_t max_depth);

/**
 * Performs an efficient depth-first search in the tree.
 *
 * @param tree the tree
 * @param data the data to search for
 * @param sfunc the search function
 * @return the first matching node, or @c NULL when the data cannot be found
 * @see cxTreeFind()
 */
CX_INLINE CX_NONNULL CX_NODISCARD
void *cxTreeFindFast(CxTree *tree, const void *data, cx_tree_search_func sfunc) {
    return cxTreeFindFastInSubtree(tree, data, sfunc, tree->root, 0);
}

/**
 * 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
 */
CX_EXTERN CX_NONNULL CX_NODISCARD
size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root);

/**
 * Determines the depth of the specified subtree.
 *
 * @param tree the tree
 * @param subtree_root the root node of the subtree
 * @return the tree depth including the @p subtree_root
 */
CX_EXTERN CX_NONNULL CX_NODISCARD
size_t cxTreeSubtreeDepth(CxTree *tree, void *subtree_root);

/**
 * Determines the size of the entire tree.
 *
 * @param tree the tree
 * @return the tree size, counting the root as one
 */
CX_EXTERN CX_NONNULL CX_NODISCARD
size_t cxTreeSize(CxTree *tree);

/**
 * Determines the depth of the entire tree.
 *
 * @param tree the tree
 * @return the tree depth, counting the root as one
 */
CX_EXTERN CX_NONNULL CX_NODISCARD
size_t cxTreeDepth(CxTree *tree);

/**
 * Creates a depth-first iterator for the specified tree starting in @p node.
 *
 * If the node is not part of the tree, the behavior is undefined.
 *
 * @param tree the tree to iterate
 * @param node the node where to start
 * @param visit_on_exit true, if the iterator shall visit a node again when
 * leaving the subtree
 * @return a tree iterator (depth-first)
 * @see cxTreeVisit()
 */
CX_EXTERN CX_NONNULL CX_NODISCARD
CxTreeIterator cxTreeIterateSubtree(CxTree *tree, void *node, bool visit_on_exit);

/**
 * Creates a breadth-first iterator for the specified tree starting in @p node.
 *
 * If the node is not part of the tree, the behavior is undefined.
 *
 * @param tree the tree to iterate
 * @param node the node where to start
 * @return a tree visitor (a.k.a. breadth-first iterator)
 * @see cxTreeIterate()
 */
CX_EXTERN CX_NONNULL CX_NODISCARD
CxTreeIterator cxTreeVisitSubtree(CxTree *tree, void *node);

/**
 * 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()
 */
CX_EXTERN CX_NONNULL CX_NODISCARD
CxTreeIterator cxTreeIterate(CxTree *tree, bool 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()
 */
CX_EXTERN CX_NONNULL CX_NODISCARD
CxTreeIterator cxTreeVisit(CxTree *tree);

/**
 * Sets the (new) parent of the specified child.
 *
 * If the @p child is not already a member of the tree, this function behaves
 * as #cxTreeAddNode().
 *
 * @param tree the tree
 * @param parent the (new) parent of the child
 * @param child the node to add
 * @see cxTreeAddNode()
 */
CX_EXTERN CX_NONNULL
void cxTreeSetParent(CxTree *tree, void *parent, void *child);

/**
 * Adds a new node to the tree.
 *
 * If the @p child is already a 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 #cxTreeAddData() (e.g., use
 * the tree's allocator).
 *
 * @param tree the tree
 * @param parent the parent of the node to add
 * @param child the node to add
 * @see cxTreeSetParent()
 * @see cxTreeAddData()
 */
CX_EXTERN CX_NONNULL
void cxTreeAddNode(CxTree *tree, void *parent, void *child);

/**
 * Creates a new node and adds it to the tree.
 *
 * @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 the added node or @c NULL when the allocation failed
 * @see cxTreeAdd()
 */
CX_EXTERN CX_NONNULL
void *cxTreeAddData(CxTree *tree, void *parent, const void *data);

/**
 * Creates a new node and adds it to the tree.
 *
 * @param tree the tree
 * @param parent the parent node of the new node
 * @return the added node or @c NULL when the allocation failed
 */
CX_EXTERN CX_NODISCARD CX_NONNULL
void *cxTreeCreateNode(CxTree *tree, void *parent);

/**
 * Creates a new root node or returns the existing root node.
 *
 * @param tree the tree
 * @return the new root node, the existing root node, or @c NULL when the allocation failed
 * @see cxTreeCreateRootData()
 */
CX_EXTERN CX_NODISCARD CX_NONNULL
void *cxTreeCreateRoot(CxTree *tree);

/**
 * Creates a new root node or uses the existing root node and writes the specified data to that node.
 *
 * @note This function immediately returns @c NULL when @c loc_data was not initialized with a positive value.
 *
 * @param tree the tree
 * @param data the data for the root node
 * @return the new root node, the existing root node,
 * or @c NULL when the allocation failed or the data location is not known
 * @see cxTreeCreateRoot()
 */
CX_EXTERN CX_NODISCARD CX_NONNULL
void *cxTreeCreateRootData(CxTree *tree, const void *data);

/**
 * Exchanges the root of the tree.
 *
 * @attention The old tree nodes might need to be deallocated by the caller.
 * On the other hand, when the tree has destructors registered, keep in mind
 * that they will be applied to the new tree.
 * In particular, using cxTreeCreate() with a @c NULL root and setting the
 * root with this function is @em not equivalent to creating the tree with
 * a reference to an existing root because trees created without a root will
 * have destructors registered.
 *
 * @param tree the tree
 * @param new_root the new root node
 * @return the old root node (or @c NULL when the tree was empty)
 */
CX_EXTERN CX_NONNULL_ARG(1) CX_NODISCARD
void *cxTreeSetRoot(CxTree *tree, void *new_root);

/**
 * 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
 */
CX_EXTERN CX_NONNULL_ARG(1, 2)
int cxTreeRemoveNode(CxTree *tree, void *node, cx_tree_relink_func relink_func);

/**
 * Removes a node and its 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
 */
CX_EXTERN CX_NONNULL
void cxTreeRemoveSubtree(CxTree *tree, void *node);

/**
 * Destroys a node and re-links its children to its former parent.
 *
 * If the node is not part of the tree, the behavior is undefined.
 *
 * It is guaranteed that the simple destructor is invoked before
 * the advanced destructor.
 *
 * @attention This function will not free the memory of the node with the
 * tree's allocator, because that is usually done by the advanced destructor
 * and would therefore result in a double-free.
 *
 * @param tree the tree
 * @param node the node to destroy (must not be the root node)
 * @param relink_func optional callback to update the content of each re-linked
 * node
 * @return zero on success, non-zero if @p node is the root node of the tree
 */
CX_EXTERN CX_NONNULL_ARG(1, 2)
int cxTreeDestroyNode(CxTree *tree, void *node, cx_tree_relink_func relink_func);

#endif //UCX_TREE_H