--- a/ucx/cx/tree.h Tue Dec 30 21:39:38 2025 +0100
+++ b/ucx/cx/tree.h Wed Dec 31 16:41:16 2025 +0100
@@ -40,93 +40,6 @@
#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.
*/
@@ -147,36 +60,14 @@
};
/**
- * 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
+ * An iterator (DFS) or visitor (BFS) for a tree.
*/
-typedef struct cx_tree_visitor_s {
+typedef struct cx_tree_combined_iterator_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;
@@ -190,38 +81,74 @@
*/
size_t counter;
/**
+ * The current depth in the tree.
+ */
+ size_t depth;
+ /**
* The currently observed node.
*
* This is the same what cxIteratorCurrent() would return.
*/
void *node;
/**
- * The current depth in the tree.
- */
- size_t depth;
- /**
- * The next element in the visitor queue.
+ * Memory for BFS or DFS-specific data.
*/
- struct cx_tree_visitor_queue_s *queue_next;
+ union {
+ struct {
+ /**
+ * Stores a copy of the pointer to the successor of the visited node.
+ * Allows freeing a node on exit without corrupting the iteration.
+ */
+ void *node_next;
+ /**
+ * Internal stack.
+ * Will be automatically freed once the iterator becomes invalid.
+ *
+ * If you want to discard the iterator before, you need to manually
+ * call cxTreeIteratorDispose().
+ */
+ void **stack;
+ /**
+ * Internal capacity of the stack.
+ */
+ size_t stack_capacity;
+ };
+ struct {
+ /**
+ * The next element in the visitor queue.
+ */
+ struct cx_tree_visitor_queue_s *queue_next;
+ /**
+ * The last element in the visitor queue.
+ */
+ struct cx_tree_visitor_queue_s *queue_last;
+ };
+ };
/**
- * The last element in the visitor queue.
+ * 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.
*/
- struct cx_tree_visitor_queue_s *queue_last;
-} CxTreeVisitor;
+ bool visit_on_exit;
+ /**
+ * True, if this iterator is currently leaving the node.
+ */
+ bool exiting;
+ /**
+ * Indicates whether the @c iterator (true) or the @c visitor (false) aspect is active.
+ */
+ bool use_dfs;
+} CxTreeIterator;
/**
* Releases internal memory of the given tree iterator.
* @param iter the iterator
*/
-cx_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);
+CX_EXTERN CX_NONNULL
+void cxTreeIteratorDispose(CxTreeIterator *iter);
/**
* Advises the iterator to skip the subtree below the current node and
@@ -232,14 +159,6 @@
#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.
@@ -254,10 +173,10 @@
* 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()
+ * @see cx_tree_remove()
*/
-cx_attr_nonnull
-CX_EXPORT void cx_tree_link(void *parent, void *node,
+CX_EXTERN CX_NONNULL
+void cx_tree_add(void *parent, void *node,
ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
ptrdiff_t loc_prev, ptrdiff_t loc_next);
@@ -273,10 +192,10 @@
* 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()
+ * @see cx_tree_add()
*/
-cx_attr_nonnull
-CX_EXPORT void cx_tree_unlink(void *node,
+CX_EXTERN CX_NONNULL
+void cx_tree_remove(void *node,
ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
ptrdiff_t loc_prev, ptrdiff_t loc_next);
@@ -311,43 +230,14 @@
* 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);
+typedef int (*cx_tree_search_func)(const void *node, const void *data);
/**
* Searches for data in a tree.
*
* When the data cannot be found exactly, the search function might return the
* closest result, which might be a good starting point for adding a new node
- * to the tree (see also #cx_tree_add()).
+ * to the tree.
*
* Depending on the tree structure, it is not necessarily guaranteed that the
* "closest" match is uniquely defined. This function will search for a node
@@ -356,7 +246,7 @@
* node matching the criteria is returned.
*
* @param root the root node
- * @param depth the maximum depth (zero=indefinite, one=just root)
+ * @param max_depth the maximum depth (zero=indefinite, one=just root)
* @param data the data to search for
* @param sfunc the search function
* @param result where the result shall be stored
@@ -366,39 +256,10 @@
* 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);
+CX_EXTERN CX_NONNULL_ARG(4, 5) CX_ACCESS_W(5)
+int cx_tree_search(const void *root, size_t max_depth,
+ const void *data, cx_tree_search_func sfunc, void **result,
+ ptrdiff_t loc_children, ptrdiff_t loc_next);
/**
* Creates a depth-first iterator for a tree with the specified root node.
@@ -420,8 +281,8 @@
* @return the new tree iterator
* @see cxTreeIteratorDispose()
*/
-cx_attr_nodiscard
-CX_EXPORT CxTreeIterator cx_tree_iterator(void *root, bool visit_on_exit,
+CX_EXTERN CX_NODISCARD
+CxTreeIterator cx_tree_iterator(void *root, bool visit_on_exit,
ptrdiff_t loc_children, ptrdiff_t loc_next);
/**
@@ -431,7 +292,7 @@
* 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
+ * invalid by itself, you MUST call cxTreeIteratorDispose() manually to release
* the memory.
*
* @remark The returned iterator does not support cxIteratorFlagRemoval().
@@ -440,178 +301,11 @@
* @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()
+ * @see cxTreeIteratorDispose()
*/
-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;
+CX_EXTERN CX_NODISCARD
+CxTreeIterator cx_tree_visitor(void *root,
+ ptrdiff_t loc_children, ptrdiff_t loc_next);
/**
* Base structure that can be used for tree nodes in a #CxTree.
@@ -642,14 +336,10 @@
/**
* Structure for holding the base data of a tree.
*/
-struct cx_tree_s {
+typedef struct cx_tree_s {
+ /** Base attributes. */
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.
@@ -657,24 +347,9 @@
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.
+ * The size of the node structure.
*/
- 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;
+ size_t node_size;
/**
* Offset in the node struct for the parent pointer.
@@ -701,7 +376,12 @@
* Offset in the node struct for the next sibling pointer.
*/
ptrdiff_t loc_next;
-};
+
+ /**
+ * Offset in the node struct where the payload is located.
+ */
+ ptrdiff_t loc_data;
+} CxTree;
/**
* Macro to roll out the #cx_tree_node_base_s structure with a custom
@@ -711,7 +391,7 @@
*
* @param type the data type for the nodes
*/
-#define CX_TREE_NODE_BASE(type) \
+#define CX_TREE_NODE(type) \
type *parent; \
type *children;\
type *last_child;\
@@ -719,51 +399,20 @@
type *next
/**
- * Macro for specifying the layout of a base node tree.
+ * Macro for specifying the layout of a tree node.
*
- * When your tree uses #CX_TREE_NODE_BASE, you can use this
+ * When your tree uses #CX_TREE_NODE, you can use this
* macro in all tree functions that expect the layout parameters
* @c loc_parent, @c loc_children, @c loc_last_child, @c loc_prev,
* and @c loc_next.
- */
-#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.
+ * @param struct_name the name of the node structure
*/
-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;
-
+#define cx_tree_node_layout(struct_name) \
+ offsetof(struct_name, parent),\
+ offsetof(struct_name, children),\
+ offsetof(struct_name, last_child),\
+ offsetof(struct_name, prev), \
+ offsetof(struct_name, next)
/**
* Destroys a node and its subtree.
@@ -783,11 +432,11 @@
* and would therefore result in a double-free.
*
* @param tree the tree
- * @param node the node to remove
+ * @param node the node being the root of the subtree to remove
* @see cxTreeFree()
*/
-cx_attr_nonnull
-CX_EXPORT void cxTreeDestroySubtree(CxTree *tree, void *node);
+CX_EXTERN CX_NONNULL
+void cxTreeDestroySubtree(CxTree *tree, void *node);
/**
@@ -807,7 +456,12 @@
* @param tree the tree
* @see cxTreeDestroySubtree()
*/
-#define cxTreeClear(tree) cxTreeDestroySubtree(tree, tree->root)
+CX_INLINE
+void cxTreeClear(CxTree *tree) {
+ if (tree->root != NULL) {
+ cxTreeDestroySubtree(tree, tree->root);
+ }
+}
/**
* Deallocates the tree structure.
@@ -825,71 +479,29 @@
*
* @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);
+CX_EXTERN
+void cxTreeFree(CxTree *tree);
/**
- * Creates a new tree structure based on a default layout.
+ * Creates a new tree.
*
- * 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.
+ * The specified @p allocator will be used for creating the tree struct
+ * @em and the nodes.
*
- * @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.
+ * When you do not specify an existing @p root, the tree will be created
+ * empty. Additionally, cxFree() is registered as the advanced destructor for
+ * the tree so that all nodes that you will add to the tree are automatically
+ * freed together with the tree.
+ * When @p root is not @c NULL, no destructors are registered automatically.
*
- * 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
+ * @param allocator the allocator to use
* (if @c NULL, the cxDefaultAllocator is assumed)
- * @param root the root node of the tree that shall be wrapped
+ * @param node_size the complete size of one node
+ * @param elem_size the size of the payload stored in the node
+ * (@c CX_STORE_POINTERS is also supported)
+ * @param root an optional already existing root node
+ * @param loc_data optional offset in the node struct for the payload
+ * (when negative, cxTreeAddData() is not supported)
* @param loc_parent offset in the node struct for the parent pointer
* @param loc_children offset in the node struct for the children linked list
* @param loc_last_child optional offset in the node struct for the pointer to
@@ -899,92 +511,91 @@
* @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,
+CX_EXTERN CX_NODISCARD CX_MALLOC CX_DEALLOC(cxTreeFree, 1)
+CxTree *cxTreeCreate(const CxAllocator *allocator,
+ size_t node_size, size_t elem_size, void *root, ptrdiff_t loc_data,
ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
ptrdiff_t loc_prev, ptrdiff_t loc_next);
/**
- * 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.
+ * @note When @p subtree_root is not @c NULL and not part of the @p tree,
+ * the behavior is undefined.
+ *
+ * @attention When @p loc_data is not available, this function immediately returns
+ * @c NULL.
*
- * @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 (@c NULL to start from root)
+ * @param max_depth the maximum search depth
+ * @param use_dfs @c true when depth-first search should be used;
+ * @c false when breadth-first search should be used
+ * @return the first matching node, or @c NULL when the data cannot be found
+ * @see cxTreeFind()
+ */
+CX_EXTERN CX_NONNULL_ARG(1, 2) CX_NODISCARD
+void *cxTreeFindInSubtree(CxTree *tree, const void *data, void *subtree_root,
+ size_t max_depth, bool use_dfs);
+
+/**
+ * Searches the data in the specified tree.
+ *
+ * @attention When @p loc_data is not available, this function immediately returns
+ * @c NULL.
*
* @param tree the tree
* @param data the data to search for
- * @param subtree_root the node where to start
+ * @param use_dfs @c true when depth-first search should be used;
+ * @c false when breadth-first search should be used
+ * @return the first matching node, or @c NULL when the data cannot be found
+ * @see cxTreeFindInSubtree()
+ * @see cxTreeFindFast()
+ */
+CX_INLINE CX_NONNULL CX_NODISCARD
+void *cxTreeFind(CxTree *tree, const void *data, bool use_dfs) {
+ if (tree->root == NULL) return NULL;
+ return cxTreeFindInSubtree(tree, data, tree->root, 0, use_dfs);
+}
+
+/**
+ * Performs an efficient depth-first search in a branch of the specified tree.
+ *
+ * When @p max_depth is zero, the depth is not limited.
+ * The @p subtree_root itself is on depth 1 and its children have depth 2.
+ *
+ * @note When @p subtree_root is not @c NULL and not part of the @p tree,
+ * the behavior is undefined.
+ *
+ * @param tree the tree
+ * @param data the data to search for
+ * @param sfunc the search function
+ * @param subtree_root the node where to start (@c NULL to start from root)
* @param max_depth the maximum search depth
* @return the first matching node, or @c NULL when the data cannot be found
+ * @see cxTreeFindInSubtree()
*/
-cx_attr_nonnull cx_attr_nodiscard
-CX_EXPORT void *cxTreeFindInSubtree(CxTree *tree, const void *data, void *subtree_root, size_t max_depth);
+CX_EXTERN CX_NONNULL CX_NODISCARD
+void *cxTreeFindFastInSubtree(CxTree *tree, const void *data,
+ cx_tree_search_func sfunc, void *subtree_root, size_t max_depth);
+
+/**
+ * Performs an efficient depth-first search in the tree.
+ *
+ * @param tree the tree
+ * @param data the data to search for
+ * @param sfunc the search function
+ * @return the first matching node, or @c NULL when the data cannot be found
+ * @see cxTreeFind()
+ */
+CX_INLINE CX_NONNULL CX_NODISCARD
+void *cxTreeFindFast(CxTree *tree, const void *data, cx_tree_search_func sfunc) {
+ return cxTreeFindFastInSubtree(tree, data, sfunc, tree->root, 0);
+}
/**
* Determines the size of the specified subtree.
@@ -993,8 +604,8 @@
* @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);
+CX_EXTERN CX_NONNULL CX_NODISCARD
+size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root);
/**
* Determines the depth of the specified subtree.
@@ -1003,8 +614,8 @@
* @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);
+CX_EXTERN CX_NONNULL CX_NODISCARD
+size_t cxTreeSubtreeDepth(CxTree *tree, void *subtree_root);
/**
* Determines the size of the entire tree.
@@ -1012,8 +623,8 @@
* @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);
+CX_EXTERN CX_NONNULL CX_NODISCARD
+size_t cxTreeSize(CxTree *tree);
/**
* Determines the depth of the entire tree.
@@ -1021,8 +632,8 @@
* @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);
+CX_EXTERN CX_NONNULL CX_NODISCARD
+size_t cxTreeDepth(CxTree *tree);
/**
* Creates a depth-first iterator for the specified tree starting in @p node.
@@ -1036,8 +647,8 @@
* @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);
+CX_EXTERN CX_NONNULL CX_NODISCARD
+CxTreeIterator cxTreeIterateSubtree(CxTree *tree, void *node, bool visit_on_exit);
/**
* Creates a breadth-first iterator for the specified tree starting in @p node.
@@ -1049,8 +660,8 @@
* @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);
+CX_EXTERN CX_NONNULL CX_NODISCARD
+CxTreeIterator cxTreeVisitSubtree(CxTree *tree, void *node);
/**
* Creates a depth-first iterator for the specified tree.
@@ -1061,8 +672,8 @@
* @return a tree iterator (depth-first)
* @see cxTreeVisit()
*/
-cx_attr_nonnull cx_attr_nodiscard
-CX_EXPORT CxTreeIterator cxTreeIterate(CxTree *tree, bool visit_on_exit);
+CX_EXTERN CX_NONNULL CX_NODISCARD
+CxTreeIterator cxTreeIterate(CxTree *tree, bool visit_on_exit);
/**
* Creates a breadth-first iterator for the specified tree.
@@ -1071,22 +682,22 @@
* @return a tree visitor (a.k.a. breadth-first iterator)
* @see cxTreeIterate()
*/
-cx_attr_nonnull cx_attr_nodiscard
-CX_EXPORT CxTreeVisitor cxTreeVisit(CxTree *tree);
+CX_EXTERN CX_NONNULL CX_NODISCARD
+CxTreeIterator cxTreeVisit(CxTree *tree);
/**
* Sets the (new) parent of the specified child.
*
* If the @p child is not already a member of the tree, this function behaves
- * as #cxTreeAddChildNode().
+ * as #cxTreeAddNode().
*
* @param tree the tree
* @param parent the (new) parent of the child
* @param child the node to add
- * @see cxTreeAddChildNode()
+ * @see cxTreeAddNode()
*/
-cx_attr_nonnull
-CX_EXPORT void cxTreeSetParent(CxTree *tree, void *parent, void *child);
+CX_EXTERN CX_NONNULL
+void cxTreeSetParent(CxTree *tree, void *parent, void *child);
/**
* Adds a new node to the tree.
@@ -1095,36 +706,81 @@
* 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).
+ * as if it was created by the tree itself with #cxTreeAddData() (e.g., use
+ * the tree's allocator).
*
* @param tree the tree
* @param parent the parent of the node to add
* @param child the node to add
* @see cxTreeSetParent()
+ * @see cxTreeAddData()
*/
-cx_attr_nonnull
-CX_EXPORT void cxTreeAddChildNode(CxTree *tree, void *parent, void *child);
+CX_EXTERN CX_NONNULL
+void cxTreeAddNode(CxTree *tree, void *parent, void *child);
+
+/**
+ * Creates a new node and adds it to the tree.
+ *
+ * @param tree the tree
+ * @param parent the parent node of the new node
+ * @param data the data that will be submitted to the create function
+ * @return the added node or @c NULL when the allocation failed
+ * @see cxTreeAdd()
+ */
+CX_EXTERN CX_NONNULL
+void *cxTreeAddData(CxTree *tree, void *parent, const void *data);
/**
* Creates a new node and adds it to the tree.
*
- * 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().
+ * @param tree the tree
+ * @param parent the parent node of the new node
+ * @return the added node or @c NULL when the allocation failed
+ */
+CX_EXTERN CX_NODISCARD CX_NONNULL
+void *cxTreeCreateNode(CxTree *tree, void *parent);
+
+/**
+ * Creates a new root node or returns the existing root node.
*
- * 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
+ * @return the new root node, the existing root node, or @c NULL when the allocation failed
+ * @see cxTreeCreateRootData()
+ */
+CX_EXTERN CX_NODISCARD CX_NONNULL
+void *cxTreeCreateRoot(CxTree *tree);
+
+/**
+ * Creates a new root node or uses the existing root node and writes the specified data to that node.
+ *
+ * @note This function immediately returns @c NULL when @c loc_data was not initialized with a positive value.
*
* @param tree the tree
- * @param 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()
+ * @param data the data for the root node
+ * @return the new root node, the existing root node,
+ * or @c NULL when the allocation failed or the data location is not known
+ * @see cxTreeCreateRoot()
*/
-cx_attr_nonnull
-CX_EXPORT int cxTreeAddChild(CxTree *tree, void *parent, const void *data);
+CX_EXTERN CX_NODISCARD CX_NONNULL
+void *cxTreeCreateRootData(CxTree *tree, const void *data);
+
+/**
+ * Exchanges the root of the tree.
+ *
+ * @attention The old tree nodes might need to be deallocated by the caller.
+ * On the other hand, when the tree has destructors registered, keep in mind
+ * that they will be applied to the new tree.
+ * In particular, using cxTreeCreate() with a @c NULL root and setting the
+ * root with this function is @em not equivalent to creating the tree with
+ * a reference to an existing root because trees created without a root will
+ * have destructors registered.
+ *
+ * @param tree the tree
+ * @param new_root the new root node
+ * @return the old root node (or @c NULL when the tree was empty)
+ */
+CX_EXTERN CX_NONNULL_ARG(1) CX_NODISCARD
+void *cxTreeSetRoot(CxTree *tree, void *new_root);
/**
* A function that is invoked when a node needs to be re-linked to a new parent.
@@ -1158,8 +814,8 @@
* 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);
+CX_EXTERN CX_NONNULL_ARG(1, 2)
+int cxTreeRemoveNode(CxTree *tree, void *node, cx_tree_relink_func relink_func);
/**
* Removes a node and its subtree from the tree.
@@ -1172,8 +828,8 @@
* @param tree the tree
* @param node the node to remove
*/
-cx_attr_nonnull
-CX_EXPORT void cxTreeRemoveSubtree(CxTree *tree, void *node);
+CX_EXTERN CX_NONNULL
+void cxTreeRemoveSubtree(CxTree *tree, void *node);
/**
* Destroys a node and re-links its children to its former parent.
@@ -1193,11 +849,7 @@
* 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
+CX_EXTERN CX_NONNULL_ARG(1, 2)
+int cxTreeDestroyNode(CxTree *tree, void *node, cx_tree_relink_func relink_func);
#endif //UCX_TREE_H