Thu, 05 Dec 2024 01:54:12 +0100
simplify how the json parser works
relates to #431 and fixes several errors related to issue #475
/* * 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 */ cx_attr_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 */ cx_attr_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() */ cx_attr_nonnull 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 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 */ cx_attr_nonnull 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 */ cx_attr_nonnull 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 */ cx_attr_nonnull cx_attr_access_w(5) 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 */ cx_attr_nonnull cx_attr_access_w(5) 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() */ cx_attr_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 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() */ cx_attr_nodiscard 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. */ cx_attr_nonnull_arg(1) 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() */ cx_attr_nonnull_arg(1, 3, 4, 6, 7) cx_attr_access_w(6) 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) 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 */ cx_attr_nonnull_arg(1, 2, 3, 5, 6) cx_attr_access_w(5) 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. */ cx_attr_nonnull 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. */ cx_attr_nonnull size_t (*insert_many)( struct cx_tree_s *tree, struct cx_iterator_base_s *iter, size_t n ); /** * Member function for finding a node. */ cx_attr_nonnull 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 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 #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 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 */ static inline void cxTreeFree(CxTree *tree) { if (tree == NULL) return; if (tree->root != NULL) { cxTreeClear(tree); } cxFree(tree->allocator, 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, a default stdlib allocator 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) 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() */ #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 afterwards. * * @param allocator the allocator that was used for nodes of the wrapped tree * (if \c NULL, a default stdlib allocator 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) 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 */ cx_attr_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 */ cx_attr_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 */ cx_attr_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 */ cx_attr_nonnull cx_attr_nodiscard 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 */ cx_attr_nonnull cx_attr_nodiscard 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 */ cx_attr_nonnull cx_attr_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_attr_nonnull cx_attr_nodiscard 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 */ cx_attr_nonnull cx_attr_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_attr_nonnull cx_attr_nodiscard 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() */ cx_attr_nonnull cx_attr_nodiscard 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() */ cx_attr_nonnull cx_attr_nodiscard 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() */ cx_attr_nonnull cx_attr_nodiscard 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() */ cx_attr_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() */ cx_attr_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() */ cx_attr_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 */ cx_attr_nonnull 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) 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 */ cx_attr_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_attr_nonnull_arg(1, 2) int cxTreeDestroyNode( CxTree *tree, void *node, cx_tree_relink_func relink_func ); #ifdef __cplusplus } // extern "C" #endif #endif //UCX_TREE_H