dav: comparison ucx/cx/tree.h

-:b60487c3ec36
+:af685cc9d623
 /**
 * 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.
+* 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.
+* 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
 */
 * 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.
+* when all its children have been processed.
 */
 bool visit_on_exit;
 /**
 * True, if this iterator is currently leaving the node.
 */
 *
 * This is the same what cxIteratorCurrent() would return.
 */
 void *node;
 /**
-* Stores a copy of the next pointer of the visited 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.
 * 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;
 * 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.
 */
 * 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.
+* 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.
+* 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
 */
 /**
 * Releases internal memory of the given tree iterator.
 * @param iter the iterator
 */
 cx_attr_nonnull
-static inline void cxTreeIteratorDispose(CxTreeIterator *iter) {
+CX_EXPORT 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) {
+CX_EXPORT 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.
 *
 #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 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_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_attr_export
+CX_EXPORT void cx_tree_link(void *parent, void *node,
-void cx_tree_link(
+ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
-void *parent,
+ptrdiff_t loc_prev, ptrdiff_t loc_next);
-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 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_attr_export
+CX_EXPORT void cx_tree_unlink(void *node,
-void cx_tree_unlink(
+ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
-void *node,
+ptrdiff_t loc_prev, ptrdiff_t loc_next);
-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
 * 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
+* For example, consider a tree that stores file path information.
-* describing a parent directory of a filename that is searched, shall
+* 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
+* 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.
 * 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
+* For example, consider a tree that stores file path information.
-* describing a parent directory of a filename that is searched, shall
+* 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
+* 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
+* 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
+* 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
+* 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 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_nonnull cx_attr_access_w(5)
-cx_attr_access_w(5)
+CX_EXPORT int cx_tree_search_data(const void *root, size_t depth,
-cx_attr_export
+const void *data, cx_tree_search_data_func sfunc,
-int cx_tree_search_data(
+void **result, ptrdiff_t loc_children, ptrdiff_t loc_next);
-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
+* 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
+* 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 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_nonnull cx_attr_access_w(5)
-cx_attr_access_w(5)
+CX_EXPORT int cx_tree_search(const void *root, size_t depth,
-cx_attr_export
+const void *node, cx_tree_search_func sfunc,
-int cx_tree_search(
+void **result, ptrdiff_t loc_children, ptrdiff_t loc_next);
-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().
+* 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.
 *
 * @param loc_next offset in the node struct for the next pointer
 * @return the new tree iterator
 * @see cxTreeIteratorDispose()
 */
 cx_attr_nodiscard
-cx_attr_export
+CX_EXPORT CxTreeIterator cx_tree_iterator(void *root, bool visit_on_exit,
-CxTreeIterator cx_tree_iterator(
+ptrdiff_t loc_children, ptrdiff_t loc_next);
-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
+* @note A tree visitor needs to maintain a queue of to-be visited nodes, which
-* is allocated using stdlib malloc().
+* 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.
 *
 * @param loc_next offset in the node struct for the next pointer
 * @return the new tree visitor
 * @see cxTreeVisitorDispose()
 */
 cx_attr_nodiscard
-cx_attr_export
+CX_EXPORT CxTreeVisitor cx_tree_visitor(void *root,
-CxTreeVisitor cx_tree_visitor(
+ptrdiff_t loc_children, ptrdiff_t loc_next);
-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 first argument points to the data the node shall contain, and
-* the second argument may be used for additional data (e.g. an allocator).
+* 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.
 */
-cx_attr_export
+CX_EXPORT extern unsigned int cx_tree_add_look_around_depth;
-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
 * @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_nonnull_arg(1, 3, 4, 6, 7) cx_attr_access_w(6)
-cx_attr_access_w(6)
+CX_EXPORT size_t cx_tree_add_iter(struct cx_iterator_base_s *iter, size_t num,
-cx_attr_export
+cx_tree_search_func sfunc, cx_tree_node_create_func cfunc,
-size_t cx_tree_add_iter(
+void *cdata, void **failed, void *root,
-struct cx_iterator_base_s *iter,
+ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
-size_t num,
+ptrdiff_t loc_prev, ptrdiff_t loc_next);
-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
 * @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_nonnull_arg(1, 4, 5, 7, 8) cx_attr_access_w(7)
-cx_attr_access_w(7)
+CX_EXPORT size_t cx_tree_add_array(const void *src, size_t num, size_t elem_size,
-cx_attr_export
+cx_tree_search_func sfunc, cx_tree_node_create_func cfunc,
-size_t cx_tree_add_array(
+void *cdata, void **failed, void *root,
-const void *src,
+ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
-size_t num,
+ptrdiff_t loc_prev, ptrdiff_t loc_next);
-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
+* 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 returned zero and the found node has a parent, the new
+* When @p sfunc returns zero and the found node has a parent, the new
-* node will be added as sibling - otherwise, the new node will be added
+* node will be added as a 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
+* 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 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
 * @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_nonnull_arg(1, 2, 3, 5, 6) cx_attr_access_w(5)
-cx_attr_access_w(5)
+CX_EXPORT int cx_tree_add(const void *src,
-cx_attr_export
+cx_tree_search_func sfunc, cx_tree_node_create_func cfunc,
-int cx_tree_add(
+void *cdata, void **cnode, void *root,
-const void *src,
+ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
-cx_tree_search_func sfunc,
+ptrdiff_t loc_prev, ptrdiff_t loc_next);
-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.
 */
 /**
 * A function to create new nodes.
 *
 * Invocations to this function will receive a pointer to this tree
-* structure as second argument.
+* structure as the second argument.
 *
-* Nodes MAY use #cx_tree_node_base_s as base layout, but do not need to.
+* Nodes MAY use #cx_tree_node_base_s as the base layout, but do not need to.
 */
 cx_tree_node_create_func node_create;
 /**
 * An optional simple destructor for the tree nodes.
 /**
 * Macro to roll out the #cx_tree_node_base_s structure with a custom
 * node type.
 *
-* Must be used as first member in your custom tree struct.
+* 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; \
 * 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)(
+int (*insert_element)(struct cx_tree_s *tree, const void *data);
-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
+* 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)(
+size_t (*insert_many)(struct cx_tree_s *tree, struct cx_iterator_base_s *iter, size_t n);
-struct cx_tree_s *tree,
-struct cx_iterator_base_s *iter,
-size_t n
-);
 /**
 * Member function for finding a node.
 */
-void *(*find)(
+void *(*find)(struct cx_tree_s *tree, const void *subtree, const void *data, size_t depth);
-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.
+* 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
 * @param tree the tree
 * @param node the node to remove
 * @see cxTreeFree()
 */
 cx_attr_nonnull
-cx_attr_export
+CX_EXPORT void cxTreeDestroySubtree(CxTree *tree, void *node);
-void cxTreeDestroySubtree(CxTree *tree, void *node);
 /**
 * Destroys the tree contents.
 *
 * 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
+* 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()
 */
 * 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_attr_export
+CX_EXPORT void cxTreeFree(CxTree *tree);
-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
 *
 * @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)
+* (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_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_nonnull_arg(2, 3, 4) cx_attr_nodiscard  cx_attr_malloc cx_attr_dealloc(cxTreeFree, 1)
-cx_attr_nodiscard
+CX_EXPORT CxTree *cxTreeCreate(const CxAllocator *allocator, cx_tree_node_create_func create_func,
-cx_attr_malloc
+cx_tree_search_func search_func, cx_tree_search_data_func search_data_func,
-cx_attr_dealloc(cxTreeFree, 1)
+ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
-cx_attr_export
+ptrdiff_t loc_prev, ptrdiff_t loc_next);
-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
+* 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.
+* 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 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(\
+#define cxTreeCreateSimple(allocator, create_func, search_func, search_data_func) \
-allocator, create_func, search_func, search_data_func \
+cxTreeCreate(allocator, create_func, search_func, search_data_func, cx_tree_node_base_layout)
-) 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.
+* tree, you need to specify those functions afterward.
 *
 * @param allocator the allocator that was used for nodes of the wrapped tree
-* (if @c NULL, a default stdlib allocator is assumed)
+* (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_nonnull_arg(2) cx_attr_nodiscard  cx_attr_malloc  cx_attr_dealloc(cxTreeFree, 1)
-cx_attr_nodiscard
+CX_EXPORT CxTree *cxTreeCreateWrapped(const CxAllocator *allocator, void *root,
-cx_attr_malloc
+ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
-cx_attr_dealloc(cxTreeFree, 1)
+ptrdiff_t loc_prev, ptrdiff_t loc_next);
-cx_attr_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
 * @param data the data to insert
 * @retval zero success
 * @retval non-zero failure
 */
 cx_attr_nonnull
-static inline int cxTreeInsert(
+CX_EXPORT int cxTreeInsert(CxTree *tree, const void *data);
-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
 * @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(
+CX_EXPORT size_t cxTreeInsertIter(CxTree *tree, CxIteratorBase *iter, size_t n);
-CxTree *tree,
-CxIteratorBase *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
 * @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(
+CX_EXPORT size_t cxTreeInsertArray(CxTree *tree, const void *data, size_t elem_size, size_t n);
-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
 *
 * @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_nonnull cx_attr_nodiscard
-cx_attr_nodiscard
+CX_EXPORT void *cxTreeFind(CxTree *tree, const void *data);
-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.
 * @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_nonnull cx_attr_nodiscard
-cx_attr_nodiscard
+CX_EXPORT void *cxTreeFindInSubtree(CxTree *tree, const void *data, void *subtree_root, size_t max_depth);
-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_nonnull cx_attr_nodiscard
-cx_attr_nodiscard
+CX_EXPORT size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root);
-cx_attr_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_nonnull  cx_attr_nodiscard
-cx_attr_nodiscard
+CX_EXPORT size_t cxTreeSubtreeDepth(CxTree *tree, void *subtree_root);
-cx_attr_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_nonnull cx_attr_nodiscard
-cx_attr_nodiscard
+CX_EXPORT size_t cxTreeDepth(CxTree *tree);
-cx_attr_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 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_nonnull cx_attr_nodiscard
-cx_attr_nodiscard
+CX_EXPORT CxTreeIterator cxTreeIterateSubtree(CxTree *tree, void *node, bool visit_on_exit);
-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_nonnull cx_attr_nodiscard
-cx_attr_nodiscard
+CX_EXPORT CxTreeVisitor cxTreeVisitSubtree(CxTree *tree, void *node);
-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_nonnull cx_attr_nodiscard
-cx_attr_nodiscard
+CX_EXPORT CxTreeIterator cxTreeIterate(CxTree *tree, bool visit_on_exit);
-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_nonnull cx_attr_nodiscard
-cx_attr_nodiscard
+CxTreeVisitor cxTreeVisit(CxTree *tree);
-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
+* 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_attr_export
+CX_EXPORT void cxTreeSetParent(CxTree *tree, void *parent, void *child);
-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.
+* 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
+* 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_attr_export
+CX_EXPORT void cxTreeAddChildNode(CxTree *tree, void *parent, void *child);
-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
+* 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_attr_export
+CX_EXPORT int cxTreeAddChild(CxTree *tree, void *parent, const void *data);
-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.
 *
 * @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
 );
 * @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_attr_export
+CX_EXPORT int cxTreeRemoveNode(CxTree *tree, void *node, cx_tree_relink_func relink_func);
-int cxTreeRemoveNode(
-CxTree *tree,
+/**
-void *node,
+* Removes a node and its subtree from the tree.
-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
-cx_attr_export
+CX_EXPORT void cxTreeRemoveSubtree(CxTree *tree, void *node);
-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.
 * @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_attr_export
+CX_EXPORT int cxTreeDestroyNode(CxTree *tree, void *node, cx_tree_relink_func relink_func);
-int cxTreeDestroyNode(
-CxTree *tree,
-void *node,
-cx_tree_relink_func relink_func
-);
 #ifdef __cplusplus
 } // extern "C"
 #endif

Mercurial > hg > dav / file comparison

comparison: ucx/cx/tree.h

ucx/cx/tree.h