/*
* 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 its 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.
* This includes the current node.
*/
size_t counter;
/**
* The currently observed node.
*
* This is the same what cxIteratorCurrent() would return.
*/
void *node;
/**
* 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;
union {
/**
* Internal stack size.
*/
size_t stack_size;
/**
* The current depth in the tree.
* The node with which the iteration starts has depth 1.
*/
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.
* 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;
};
/**
* 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.
* This includes the currently visited node.
*/
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
*/
cx_attr_nonnull
CX_EXPORT void cxTreeIteratorDispose(CxTreeIterator *iter);
/**
* Releases internal memory of the given tree visitor.
* @param visitor the visitor
*/
cx_attr_nonnull
CX_EXPORT void cxTreeVisitorDispose(CxTreeVisitor *visitor);
/**
* 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
/**
* Advises the visitor to skip the subtree below the current node and
* also continues the current loop.
*
* @param visitor (@c CxTreeVisitor) the visitor
*/
#define cxTreeVisitorContinue(visitor) cxTreeIteratorContinue(visitor)
/**
* 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_unlink()
*/
cx_attr_nonnull
CX_EXPORT void cx_tree_link(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_link()
*/
cx_attr_nonnull
CX_EXPORT 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, 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_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, 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 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 the
* 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
*/
cx_attr_nonnull cx_attr_access_w(5)
CX_EXPORT 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 the 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
*/
cx_attr_nonnull cx_attr_access_w(5)
CX_EXPORT 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 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_attr_nodiscard
CX_EXPORT 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 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()
*/
cx_attr_nodiscard
CX_EXPORT 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.
*/
CX_EXPORT 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()
*/
cx_attr_nonnull_arg(1, 3, 4, 6, 7) cx_attr_access_w(6)
CX_EXPORT 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()
*/
cx_attr_nonnull_arg(1, 4, 5, 7, 8) cx_attr_access_w(7)
CX_EXPORT 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 returns 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 returns zero and the found node has a parent, the new
* node will be added as a sibling - otherwise, the new node will be added
* as a child.
*
* When @p sfunc returns 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
*/
cx_attr_nonnull_arg(1, 2, 3, 5, 6) cx_attr_access_w(5)
CX_EXPORT 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 {
CX_COLLECTION_BASE;
/**
* The tree class definition.
*/
const cx_tree_class *cl;
/**
* 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 the second argument.
*
* Nodes MAY use #cx_tree_node_base_s as the base layout, but do not need to.
*/
cx_tree_node_create_func node_create;
/**
* 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;
/**
* 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.
*
* Must be used as the first member in your custom tree struct.
*
* @param type the data type for the nodes
*/
#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.
*
* When your tree uses #CX_TREE_NODE_BASE, you can use this
* macro in all tree functions that expect the layout parameters
* @c loc_parent, @c loc_children, @c loc_last_child, @c loc_prev,
* and @c loc_next.
*/
#define cx_tree_node_base_layout \
offsetof(struct cx_tree_node_base_s, parent),\
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)
/**
* 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 performing 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;
/**
* 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 to remove
* @see cxTreeFree()
*/
cx_attr_nonnull
CX_EXPORT 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)
/**
* 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_EXPORT void cxTreeFree(CxTree *tree);
/**
* 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
* (if @c NULL, the cxDefaultAllocator will be used)
* @param create_func a function that creates new nodes
* @param search_func a function that compares two nodes
* @param search_data_func a function that compares a node with data
* @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()
*/
cx_attr_nonnull_arg(2, 3, 4) cx_attr_nodiscard cx_attr_malloc cx_attr_dealloc(cxTreeFree, 1)
CX_EXPORT 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 the 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 (@c CxAllocator*) the allocator that shall be used
* @param create_func (@c cx_tree_node_create_func) a function that creates new nodes
* @param search_func (@c cx_tree_search_func) a function that compares two nodes
* @param search_data_func (@c cx_tree_search_data_func) a function that compares a node with data
* @return (@c CxTree*) the new tree
* @see cxTreeCreate()
*/
#define cxTreeCreateSimple(allocator, create_func, search_func, search_data_func) \
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 afterward.
*
* @param allocator the allocator that was used for nodes of the wrapped tree
* (if @c NULL, the cxDefaultAllocator is assumed)
* @param root the root node of the tree that shall be wrapped
* @param loc_parent offset in the node struct for the parent pointer
* @param loc_children offset in the node struct for the children linked list
* @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_attr_nonnull_arg(2) cx_attr_nodiscard cx_attr_malloc cx_attr_dealloc(cxTreeFree, 1)
CX_EXPORT 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
* @retval zero success
* @retval non-zero failure
*/
cx_attr_nonnull
CX_EXPORT int cxTreeInsert(CxTree *tree, const void *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
*/
cx_attr_nonnull
CX_EXPORT size_t cxTreeInsertIter(CxTree *tree, CxIteratorBase *iter, size_t 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
*/
cx_attr_nonnull
CX_EXPORT size_t cxTreeInsertArray(CxTree *tree, const void *data, size_t elem_size, size_t 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
*/
cx_attr_nonnull cx_attr_nodiscard
CX_EXPORT void *cxTreeFind(CxTree *tree, const void *data);
/**
* 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
*/
cx_attr_nonnull cx_attr_nodiscard
CX_EXPORT void *cxTreeFindInSubtree(CxTree *tree, const void *data, void *subtree_root, size_t 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
*/
cx_attr_nonnull cx_attr_nodiscard
CX_EXPORT 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_attr_nonnull cx_attr_nodiscard
CX_EXPORT 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_attr_nonnull cx_attr_nodiscard
CX_EXPORT 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_attr_nonnull cx_attr_nodiscard
CX_EXPORT 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_attr_nonnull cx_attr_nodiscard
CX_EXPORT 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_attr_nonnull cx_attr_nodiscard
CX_EXPORT CxTreeVisitor 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_attr_nonnull cx_attr_nodiscard
CX_EXPORT 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_attr_nonnull cx_attr_nodiscard
CX_EXPORT CxTreeVisitor 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 #cxTreeAddChildNode().
*
* @param tree the tree
* @param parent the (new) parent of the child
* @param child the node to add
* @see cxTreeAddChildNode()
*/
cx_attr_nonnull
CX_EXPORT 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 #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()
*/
cx_attr_nonnull
CX_EXPORT 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()
*/
cx_attr_nonnull
CX_EXPORT 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
*/
cx_attr_nonnull_arg(1, 2)
CX_EXPORT 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_attr_nonnull
CX_EXPORT 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_attr_nonnull_arg(1, 2)
CX_EXPORT int cxTreeDestroyNode(CxTree *tree, void *node, cx_tree_relink_func relink_func);
#ifdef __cplusplus
} // extern "C"
#endif
#endif //UCX_TREE_H