toolkit: comparison ucx/cx/tree.h

-:6691e007cef7
+:473d8cb58a6c
 #include "common.h"
 #include "collection.h"
-#ifdef __cplusplus
+/**
-extern "C" {
+* An element in a visitor queue.
-#endif
+*/
+struct cx_tree_visitor_queue_s {
 /**
-* A depth-first tree iterator.
+* The tree node to visit.
-*
+*/
-* This iterator is not position-aware in a strict sense, as it does not assume
+void *node;
-* 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.
+* The depth of the node.
-* Each node, regardless of the number of passes, is counted only once.
+* The first visited node has depth 1.
-*
+*/
-* @note Objects that are pointed to by an iterator are mutable through that
+size_t depth;
-* iterator. However, if the
+/**
-* underlying data structure is mutated by other means than this iterator (e.g.,
+* The next element in the queue or @c NULL.
-* elements added or removed), the iterator becomes invalid (regardless of what
+*/
-* cxIteratorValid() returns).
+struct cx_tree_visitor_queue_s *next;
-*
+};
-* @see CxIterator
-*/
+/**
-typedef struct cx_tree_iterator_s {
+* An iterator (DFS) or visitor (BFS) for a tree.
+*/
+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;
-/**
-* 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.
+* This includes the currently visited node.
 */
 size_t counter;
+/**
+* The current depth in the tree.
+*/
+size_t depth;
 /**
 * The currently observed node.
 *
 * This is the same what cxIteratorCurrent() would return.
 */
 void *node;
 /**
-* Stores a copy of the pointer to the successor of the visited node.
+* Memory for BFS or DFS-specific data.
-* 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 {
-/**
+struct {
-* Internal stack size.
+/**
-*/
+* Stores a copy of the pointer to the successor of the visited node.
-size_t stack_size;
+* Allows freeing a node on exit without corrupting the iteration.
-/**
+*/
-* The current depth in the tree.
+void *node_next;
-* The node with which the iteration starts has depth 1.
+/**
-*/
+* Internal stack.
-size_t depth;
+* Will be automatically freed once the iterator becomes invalid.
+*
+* If you want to discard the iterator before, you need to manually
+* call cxTreeIteratorDispose().
+*/
+void **stack;
+/**
+* Internal capacity of the stack.
+*/
+size_t stack_capacity;
+};
+struct {
+/**
+* The next element in the visitor queue.
+*/
+struct cx_tree_visitor_queue_s *queue_next;
+/**
+* The last element in the visitor queue.
+*/
+struct cx_tree_visitor_queue_s *queue_last;
+};
 };
+/**
+* Indicates whether the subtree below the current node shall be skipped.
+*/
+bool skip;
+/**
+* Set to true, when the iterator shall visit a node again
+* when all its children have been processed.
+*/
+bool visit_on_exit;
+/**
+* True, if this iterator is currently leaving the node.
+*/
+bool exiting;
+/**
+* Indicates whether the @c iterator (true) or the @c visitor (false) aspect is active.
+*/
+bool use_dfs;
 } CxTreeIterator;
-/**
-* An element in a visitor queue.
-*/
-struct cx_tree_visitor_queue_s {
-/**
-* The tree node to visit.
-*/
-void *node;
-/**
-* The depth of the node.
-* The first visited node has depth 1.
-*/
-size_t depth;
-/**
-* The next element in the queue or @c NULL.
-*/
-struct cx_tree_visitor_queue_s *next;
-};
-/**
-* A breadth-first tree iterator.
-*
-* This iterator needs to maintain a visitor queue that will be automatically
-* freed once the iterator becomes invalid.
-* If you want to discard the iterator before, you MUST manually call
-* cxTreeVisitorDispose().
-*
-* This iterator is not position-aware in a strict sense, as it does not assume
-* a particular order of elements in the tree. However, the iterator keeps track
-* of the number of nodes it has passed in a counter-variable.
-* Each node, regardless of the number of passes, is counted only once.
-*
-* @note Objects that are pointed to by an iterator are mutable through that
-* iterator. However, if the
-* underlying data structure is mutated by other means than this iterator (e.g.,
-* elements added or removed), the iterator becomes invalid (regardless of what
-* cxIteratorValid() returns).
-*
-* @see CxIterator
-*/
-typedef struct cx_tree_visitor_s {
-/**
-* Base members.
-*/
-CX_ITERATOR_BASE;
-/**
-* Indicates whether the subtree below the current node shall be skipped.
-*/
-bool skip;
-/**
-* Offset in the node struct for the children linked list.
-*/
-ptrdiff_t loc_children;
-/**
-* Offset in the node struct for the next pointer.
-*/
-ptrdiff_t loc_next;
-/**
-* The total number of distinct nodes that have been passed so far.
-* This includes the currently visited node.
-*/
-size_t counter;
-/**
-* The currently observed node.
-*
-* This is the same what cxIteratorCurrent() would return.
-*/
-void *node;
-/**
-* The current depth in the tree.
-*/
-size_t depth;
-/**
-* The next element in the visitor queue.
-*/
-struct cx_tree_visitor_queue_s *queue_next;
-/**
-* The last element in the visitor queue.
-*/
-struct cx_tree_visitor_queue_s *queue_last;
-} CxTreeVisitor;
 /**
 * Releases internal memory of the given tree iterator.
 * @param iter the iterator
 */
-cx_attr_nonnull
+CX_EXTERN CX_NONNULL
-CX_EXPORT void cxTreeIteratorDispose(CxTreeIterator *iter);
+void cxTreeIteratorDispose(CxTreeIterator *iter);
-/**
-* Releases internal memory of the given tree visitor.
-* @param visitor the visitor
-*/
-cx_attr_nonnull
-CX_EXPORT void cxTreeVisitorDispose(CxTreeVisitor *visitor);
 /**
 * Advises the iterator to skip the subtree below the current node and
 * also continues the current loop.
 *
 * @param iterator (@c CxTreeIterator) the iterator
 */
 #define cxTreeIteratorContinue(iterator) (iterator).skip = true; continue
-/**
-* Advises the visitor to skip the subtree below the current node and
-* also continues the current loop.
-*
-* @param visitor (@c CxTreeVisitor) the visitor
-*/
-#define cxTreeVisitorContinue(visitor) cxTreeIteratorContinue(visitor)
 /**
 * Links a node to a (new) parent.
 *
 * If the node already has a parent, it is unlinked, first.
 * @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()
+* @see cx_tree_remove()
 */
-cx_attr_nonnull
+CX_EXTERN CX_NONNULL
-CX_EXPORT void cx_tree_link(void *parent, void *node,
+void cx_tree_add(void *parent, void *node,
 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
 ptrdiff_t loc_prev, ptrdiff_t loc_next);
 /**
 * Unlinks a node from its parent.
 * @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()
+* @see cx_tree_add()
 */
-cx_attr_nonnull
+CX_EXTERN CX_NONNULL
-CX_EXPORT void cx_tree_unlink(void *node,
+void cx_tree_remove(void *node,
 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
 ptrdiff_t loc_prev, ptrdiff_t loc_next);
 /**
 * Macro that can be used instead of the magic value for infinite search depth.
 *
 * @return 0 if the node contains the data,
 * positive if one of the children might contain the data,
 * negative if neither the node nor the children contains the data
 */
-typedef int (*cx_tree_search_data_func)(const void *node, const void *data);
+typedef int (*cx_tree_search_func)(const void *node, const void *data);
-/**
-* Function pointer for a search function.
-*
-* A function of this kind shall check if the specified @p node
-* contains the same @p data as @p new_node or if one of the children might
-* contain the data.
-*
-* The function should use the returned integer to indicate how close the
-* match is, where a negative number means that it does not match at all.
-* Zero means exact match and a positive number is an implementation defined
-* measure for the distance to an exact match.
-*
-* For example, consider a tree that stores file path information.
-* A node which is describing a parent directory of a searched file shall
-* return a positive number to indicate that a child node might contain the
-* searched item. On the other hand, if the node denotes a path that is not a
-* prefix of the searched filename, the function would return -1 to indicate
-* that the search does not need to be continued in that branch.
-*
-* @param node the node that is currently investigated
-* @param new_node a new node with the information which is searched
-*
-* @return 0 if @p node contains the same data as @p new_node,
-* positive if one of the children might contain the data,
-* negative if neither the node nor the children contains the data
-*/
-typedef int (*cx_tree_search_func)(const void *node, const void *new_node);
 /**
 * Searches for data in a tree.
 *
 * When the data cannot be found exactly, the search function might return the
 * closest result, which might be a good starting point for adding a new node
-* to the tree (see also #cx_tree_add()).
+* to the tree.
 *
 * Depending on the tree structure, it is not necessarily guaranteed that the
 * "closest" match is uniquely defined. This function will search for a node
 * with the best match according to the @p sfunc (meaning: the return value of
 * @p sfunc which is closest to zero). If that is also ambiguous, an arbitrary
 * node matching the criteria is returned.
 *
 * @param root the root node
-* @param 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
 * @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_EXTERN CX_NONNULL_ARG(4, 5) CX_ACCESS_W(5)
-CX_EXPORT int cx_tree_search_data(const void *root, size_t depth,
+int cx_tree_search(const void *root, size_t max_depth,
-const void *data, cx_tree_search_data_func sfunc,
+const void *data, cx_tree_search_func sfunc, void **result,
-void **result, ptrdiff_t loc_children, ptrdiff_t loc_next);
+ptrdiff_t loc_children, ptrdiff_t loc_next);
-/**
-* Searches for a node in a tree.
-*
-* When no node with the same data can be found, the search function might
-* return the closest result, which might be a good starting point for adding the
-* new node to the tree (see also #cx_tree_add()).
-*
-* Depending on the tree structure, it is not necessarily guaranteed that the
-* "closest" match is uniquely defined. This function will search for a node
-* with the best match according to the @p sfunc (meaning: the return value of
-* @p sfunc which is closest to zero). If that is also ambiguous, an arbitrary
-* node matching the criteria is returned.
-*
-* @param root the root node
-* @param depth the maximum depth (zero=indefinite, one=just root)
-* @param node the node to search for
-* @param sfunc the search function
-* @param result where the result shall be stored
-* @param loc_children offset in the node struct for the children linked list
-* @param loc_next offset in the node struct for the next pointer
-* @return zero if the node was found exactly, positive if a node was found that
-* could contain the node (but doesn't right now), negative if the tree does not
-* contain any node that might be related to the searched data
-*/
-cx_attr_nonnull cx_attr_access_w(5)
-CX_EXPORT int cx_tree_search(const void *root, size_t depth,
-const void *node, cx_tree_search_func sfunc,
-void **result, ptrdiff_t loc_children, ptrdiff_t loc_next);
 /**
 * Creates a depth-first iterator for a tree with the specified root node.
 *
 * @note A tree iterator needs to maintain a stack of visited nodes, which is
 * @param loc_children offset in the node struct for the children linked list
 * @param loc_next offset in the node struct for the next pointer
 * @return the new tree iterator
 * @see cxTreeIteratorDispose()
 */
-cx_attr_nodiscard
+CX_EXTERN CX_NODISCARD
-CX_EXPORT CxTreeIterator cx_tree_iterator(void *root, bool visit_on_exit,
+CxTreeIterator cx_tree_iterator(void *root, bool visit_on_exit,
 ptrdiff_t loc_children, ptrdiff_t loc_next);
 /**
 * Creates a breadth-first iterator for a tree with the specified root node.
 *
 * @note A tree visitor needs to maintain a queue of to-be visited nodes, which
 * is allocated using the cxDefaultAllocator.
 * When the visitor becomes invalid, this memory is automatically released.
 * However, if you wish to cancel the iteration before the visitor becomes
-* invalid by itself, you MUST call cxTreeVisitorDispose() manually to release
+* invalid by itself, you MUST call cxTreeIteratorDispose() manually to release
 * the memory.
 *
 * @remark The returned iterator does not support cxIteratorFlagRemoval().
 *
 * @param root the root node
 * @param loc_children offset in the node struct for the children linked list
 * @param loc_next offset in the node struct for the next pointer
 * @return the new tree visitor
-* @see cxTreeVisitorDispose()
+* @see cxTreeIteratorDispose()
 */
-cx_attr_nodiscard
+CX_EXTERN CX_NODISCARD
-CX_EXPORT CxTreeVisitor cx_tree_visitor(void *root,
+CxTreeIterator cx_tree_visitor(void *root,
 ptrdiff_t loc_children, ptrdiff_t loc_next);
-/**
-* Describes a function that creates a tree node from the specified data.
-* The first argument points to the data the node shall contain, and
-* the second argument may be used for additional data (e.g., an allocator).
-* Functions of this type shall either return a new pointer to a newly
-* created node or @c NULL when allocation fails.
-*
-* @note the function may leave the node pointers in the struct uninitialized.
-* The caller is responsible to set them according to the intended use case.
-*/
-typedef void *(*cx_tree_node_create_func)(const void *, void *);
-/**
-* The local search depth for a new subtree when adding multiple elements.
-* The default value is 3.
-* This variable is used by #cx_tree_add_array() and #cx_tree_add_iter() to
-* implement optimized insertion of multiple elements into a tree.
-*/
-CX_EXPORT extern unsigned int cx_tree_add_look_around_depth;
-/**
-* Adds multiple elements efficiently to a tree.
-*
-* Once an element cannot be added to the tree, this function returns, leaving
-* the iterator in a valid state pointing to the element that could not be
-* added.
-* Also, the pointer of the created node will be stored to @p failed.
-* The integer returned by this function denotes the number of elements obtained
-* from the @p iter that have been successfully processed.
-* When all elements could be processed, a @c NULL pointer will be written to
-* @p failed.
-*
-* The advantage of this function compared to multiple invocations of
-* #cx_tree_add() is that the search for the insert locations is not always
-* started from the root node.
-* Instead, the function checks #cx_tree_add_look_around_depth many parent nodes
-* of the current insert location before starting from the root node again.
-* When the variable is set to zero, only the last found location is checked
-* again.
-*
-* Refer to the documentation of #cx_tree_add() for more details.
-*
-* @param iter a pointer to an arbitrary iterator
-* @param num the maximum number of elements to obtain from the iterator
-* @param sfunc a search function
-* @param cfunc a node creation function
-* @param cdata optional additional data
-* @param root the root node of the tree
-* @param failed location where the pointer to a failed node shall be stored
-* @param loc_parent offset in the node struct for the parent pointer
-* @param loc_children offset in the node struct for the children linked list
-* @param loc_last_child optional offset in the node struct for the pointer to
-* the last child in the linked list (negative if there is no such pointer)
-* @param loc_prev optional offset in the node struct for the prev pointer
-* @param loc_next offset in the node struct for the next pointer
-* @return the number of nodes created and added
-* @see cx_tree_add()
-*/
-cx_attr_nonnull_arg(1, 3, 4, 6, 7) cx_attr_access_w(6)
-CX_EXPORT size_t cx_tree_add_iter(struct cx_iterator_base_s *iter, size_t num,
-cx_tree_search_func sfunc, cx_tree_node_create_func cfunc,
-void *cdata, void **failed, void *root,
-ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
-ptrdiff_t loc_prev, ptrdiff_t loc_next);
-/**
-* Adds multiple elements efficiently to a tree.
-*
-* Once an element cannot be added to the tree, this function returns, storing
-* the pointer of the created node to @p failed.
-* The integer returned by this function denotes the number of elements from
-* the @p src array that have been successfully processed.
-* When all elements could be processed, a @c NULL pointer will be written to
-* @p failed.
-*
-* The advantage of this function compared to multiple invocations of
-* #cx_tree_add() is that the search for the insert locations is not always
-* started from the root node.
-* Instead, the function checks #cx_tree_add_look_around_depth many parent nodes
-* of the current insert location before starting from the root node again.
-* When the variable is set to zero, only the last found location is checked
-* again.
-*
-* Refer to the documentation of #cx_tree_add() for more details.
-*
-* @param src a pointer to the source data array
-* @param num the number of elements in the @p src array
-* @param elem_size the size of each element in the @p src array
-* @param sfunc a search function
-* @param cfunc a node creation function
-* @param cdata optional additional data
-* @param failed location where the pointer to a failed node shall be stored
-* @param root the root node of the tree
-* @param loc_parent offset in the node struct for the parent pointer
-* @param loc_children offset in the node struct for the children linked list
-* @param loc_last_child optional offset in the node struct for the pointer to
-* the last child in the linked list (negative if there is no such pointer)
-* @param loc_prev optional offset in the node struct for the prev pointer
-* @param loc_next offset in the node struct for the next pointer
-* @return the number of array elements successfully processed
-* @see cx_tree_add()
-*/
-cx_attr_nonnull_arg(1, 4, 5, 7, 8) cx_attr_access_w(7)
-CX_EXPORT size_t cx_tree_add_array(const void *src, size_t num, size_t elem_size,
-cx_tree_search_func sfunc, cx_tree_node_create_func cfunc,
-void *cdata, void **failed, void *root,
-ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
-ptrdiff_t loc_prev, ptrdiff_t loc_next);
-/**
-* Adds data to a tree.
-*
-* An adequate location where to add the new tree node is searched with the
-* specified @p sfunc.
-*
-* When a location is found, the @p cfunc will be invoked with @p cdata.
-*
-* The node returned by @p cfunc will be linked into the tree.
-* When @p sfunc returns a positive integer, the new node will be linked as a
-* child. The other children (now siblings of the new node) are then checked
-* with @p sfunc, whether they could be children of the new node and re-linked
-* accordingly.
-*
-* When @p sfunc returns zero and the found node has a parent, the new
-* node will be added as a sibling - otherwise, the new node will be added
-* as a child.
-*
-* When @p sfunc returns a negative value, the new node will not be added to
-* the tree, and this function returns a non-zero value.
-* The caller should check if @p cnode contains a node pointer and deal with the
-* node that could not be added.
-*
-* This function also returns a non-zero value when @p cfunc tries to allocate
-* a new node but fails to do so. In that case, the pointer stored to @p cnode
-* will be @c NULL.
-*
-* Multiple elements can be added more efficiently with
-* #cx_tree_add_array() or #cx_tree_add_iter().
-*
-* @param src a pointer to the data
-* @param sfunc a search function
-* @param cfunc a node creation function
-* @param cdata optional additional data
-* @param cnode the location where a pointer to the new node is stored
-* @param root the root node of the tree
-* @param loc_parent offset in the node struct for the parent pointer
-* @param loc_children offset in the node struct for the children linked list
-* @param loc_last_child optional offset in the node struct for the pointer to
-* the last child in the linked list (negative if there is no such pointer)
-* @param loc_prev optional offset in the node struct for the prev pointer
-* @param loc_next offset in the node struct for the next pointer
-* @return zero when a new node was created and added to the tree,
-* non-zero otherwise
-*/
-cx_attr_nonnull_arg(1, 2, 3, 5, 6) cx_attr_access_w(5)
-CX_EXPORT int cx_tree_add(const void *src,
-cx_tree_search_func sfunc, cx_tree_node_create_func cfunc,
-void *cdata, void **cnode, void *root,
-ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
-ptrdiff_t loc_prev, ptrdiff_t loc_next);
-/**
-* Tree class type.
-*/
-typedef struct cx_tree_class_s cx_tree_class;
 /**
 * Base structure that can be used for tree nodes in a #CxTree.
 */
 struct cx_tree_node_base_s {
 };
 /**
 * 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.
 */
 void *root;
 /**
-* A function to create new nodes.
+* The size of the node structure.
-*
+*/
-* Invocations to this function will receive a pointer to this tree
+size_t node_size;
-* structure as the second argument.
-*
-* Nodes MAY use #cx_tree_node_base_s as the base layout, but do not need to.
-*/
-cx_tree_node_create_func node_create;
-/**
-* A function to compare two nodes.
-*/
-cx_tree_search_func search;
-/**
-* A function to compare a node with data.
-*/
-cx_tree_search_data_func search_data;
 /**
 * Offset in the node struct for the parent pointer.
 */
 ptrdiff_t loc_parent;
 /**
 * Offset in the node struct for the next sibling pointer.
 */
 ptrdiff_t loc_next;
-};
+/**
+* Offset in the node struct where the payload is located.
+*/
+ptrdiff_t loc_data;
+} CxTree;
 /**
 * Macro to roll out the #cx_tree_node_base_s structure with a custom
 * node type.
 *
 * Must be used as the first member in your custom tree struct.
 *
 * @param type the data type for the nodes
 */
-#define CX_TREE_NODE_BASE(type) \
+#define CX_TREE_NODE(type) \
 type *parent; \
 type *children;\
 type *last_child;\
 type *prev;\
 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.
-*/
+* @param struct_name the name of the node structure
-#define cx_tree_node_base_layout \
+*/
-offsetof(struct cx_tree_node_base_s, parent),\
+#define cx_tree_node_layout(struct_name) \
-offsetof(struct cx_tree_node_base_s, children),\
+offsetof(struct_name, parent),\
-offsetof(struct cx_tree_node_base_s, last_child),\
+offsetof(struct_name, children),\
-offsetof(struct cx_tree_node_base_s, prev),  \
+offsetof(struct_name, last_child),\
-offsetof(struct cx_tree_node_base_s, next)
+offsetof(struct_name, prev),  \
+offsetof(struct_name, next)
-/**
-* The class definition for arbitrary trees.
-*/
-struct cx_tree_class_s {
-/**
-* Member function for inserting a single element.
-*
-* Implementations SHALL NOT simply invoke @p insert_many as this comes
-* with too much overhead.
-*/
-int (*insert_element)(struct cx_tree_s *tree, const void *data);
-/**
-* Member function for inserting multiple elements.
-*
-* Implementations SHALL avoid performing a full search in the tree for
-* every element even though the source data MAY be unsorted.
-*/
-size_t (*insert_many)(struct cx_tree_s *tree, struct cx_iterator_base_s *iter, size_t n);
-/**
-* Member function for finding a node.
-*/
-void *(*find)(struct cx_tree_s *tree, const void *subtree, const void *data, size_t depth);
-};
-/**
-* Common type for all tree implementations.
-*/
-typedef struct cx_tree_s CxTree;
 /**
 * Destroys a node and its subtree.
 *
 * It is guaranteed that the simple destructor is invoked before
 * @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
+* @param node the node being the root of the subtree to remove
 * @see cxTreeFree()
 */
-cx_attr_nonnull
+CX_EXTERN CX_NONNULL
-CX_EXPORT void cxTreeDestroySubtree(CxTree *tree, void *node);
+void cxTreeDestroySubtree(CxTree *tree, void *node);
 /**
 * Destroys the tree contents.
 *
 * otherwise you will be leaking memory.
 *
 * @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.
 *
 * The destructor functions are invoked for each node, starting with the leaf
 * that would cause a double-free in most scenarios where the advanced
 * destructor is already freeing the memory.
 *
 * @param tree the tree to free
 */
-CX_EXPORT void cxTreeFree(CxTree *tree);
+CX_EXTERN
+void cxTreeFree(CxTree *tree);
-/**
-* Creates a new tree structure based on the specified layout.
+/**
+* Creates a new tree.
 *
 * 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.
+* @em and the nodes.
 *
-* @note This function will also register an advanced destructor which
+* When you do not specify an existing @p root, the tree will be created
-* will free the nodes with the allocator's free() method.
+* 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
-* @param allocator the allocator that shall be used
+* freed together with the tree.
-* (if @c NULL, the cxDefaultAllocator will be used)
+* When @p root is not @c NULL, no destructors are registered automatically.
-* @param create_func a function that creates new nodes
+*
-* @param search_func a function that compares two nodes
+* @param allocator the allocator to use
-* @param search_data_func a function that compares a node with data
-* @param loc_parent offset in the node struct for the parent pointer
-* @param loc_children offset in the node struct for the children linked list
-* @param loc_last_child optional offset in the node struct for the pointer to
-* the last child in the linked list (negative if there is no such pointer)
-* @param loc_prev optional offset in the node struct for the prev pointer
-* @param loc_next offset in the node struct for the next pointer
-* @return the new tree
-* @see cxTreeCreateSimple()
-* @see cxTreeCreateWrapped()
-*/
-cx_attr_nonnull_arg(2, 3, 4) cx_attr_nodiscard  cx_attr_malloc cx_attr_dealloc(cxTreeFree, 1)
-CX_EXPORT CxTree *cxTreeCreate(const CxAllocator *allocator, cx_tree_node_create_func create_func,
-cx_tree_search_func search_func, cx_tree_search_data_func search_data_func,
-ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
-ptrdiff_t loc_prev, ptrdiff_t loc_next);
-/**
-* Creates a new tree structure based on a default layout.
-*
-* Nodes created by @p create_func MUST contain #cx_tree_node_base_s as the first
-* member (or at least respect the default offsets specified in the tree
-* struct), and they MUST be allocated with the specified allocator.
-*
-* @note This function will also register an advanced destructor which
-* will free the nodes with the allocator's free() method.
-*
-* @param allocator (@c CxAllocator*) the allocator that shall be used
-* @param create_func (@c cx_tree_node_create_func) a function that creates new nodes
-* @param search_func (@c cx_tree_search_func) a function that compares two nodes
-* @param search_data_func (@c cx_tree_search_data_func)  a function that compares a node with data
-* @return (@c CxTree*) the new tree
-* @see cxTreeCreate()
-*/
-#define cxTreeCreateSimple(allocator, create_func, search_func, search_data_func) \
-cxTreeCreate(allocator, create_func, search_func, search_data_func, cx_tree_node_base_layout)
-/**
-* Creates a new tree structure based on an existing tree.
-*
-* The specified @p allocator will be used for creating the tree struct.
-*
-* @attention This function will create an incompletely defined tree structure
-* where neither the create function, the search function, nor a destructor
-* will be set. If you wish to use any of this functionality for the wrapped
-* tree, you need to specify those functions afterward.
-*
-* @param allocator the allocator that was used for nodes of the wrapped tree
 * (if @c NULL, the cxDefaultAllocator is assumed)
-* @param root the root node of the tree that shall be wrapped
+* @param node_size the complete size of one node
+* @param elem_size the size of the payload stored in the node
+* (@c CX_STORE_POINTERS is also supported)
+* @param root an optional already existing root node
+* @param loc_data optional offset in the node struct for the payload
+* (when negative, cxTreeAddData() is not supported)
 * @param loc_parent offset in the node struct for the parent pointer
 * @param loc_children offset in the node struct for the children linked list
 * @param loc_last_child optional offset in the node struct for the pointer to
 * the last child in the linked list (negative if there is no such pointer)
 * @param loc_prev optional offset in the node struct for the prev pointer
 * @param loc_next offset in the node struct for the next pointer
 * @return the new tree
 * @see cxTreeCreate()
 */
-cx_attr_nonnull_arg(2) cx_attr_nodiscard  cx_attr_malloc  cx_attr_dealloc(cxTreeFree, 1)
+CX_EXTERN CX_NODISCARD  CX_MALLOC  CX_DEALLOC(cxTreeFree, 1)
-CX_EXPORT CxTree *cxTreeCreateWrapped(const CxAllocator *allocator, void *root,
+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
+* @note When @p subtree_root is not @c NULL and not part of the @p tree,
-* undefined.
+* the behavior is undefined.
 *
-* @remark For this function to work, the tree needs a specified @c search_data
+* @attention When @p loc_data is not available, this function immediately returns
-* function, which might not be the case for wrapped trees
+* @c NULL.
-* (see #cxTreeCreateWrapped()).
 *
 * @param tree the tree
 * @param data the data to search for
-* @param subtree_root the node where to start
+* @param subtree_root the node where to start (@c NULL to start from root)
+* @param max_depth the maximum search depth
+* @param use_dfs @c true when depth-first search should be used;
+* @c false when breadth-first search should be used
+* @return the first matching node, or @c NULL when the data cannot be found
+* @see cxTreeFind()
+*/
+CX_EXTERN CX_NONNULL_ARG(1, 2) CX_NODISCARD
+void *cxTreeFindInSubtree(CxTree *tree, const void *data, void *subtree_root,
+size_t max_depth, bool use_dfs);
+/**
+* Searches the data in the specified tree.
+*
+* @attention When @p loc_data is not available, this function immediately returns
+* @c NULL.
+*
+* @param tree the tree
+* @param data the data to search for
+* @param use_dfs @c true when depth-first search should be used;
+* @c false when breadth-first search should be used
+* @return the first matching node, or @c NULL when the data cannot be found
+* @see cxTreeFindInSubtree()
+* @see cxTreeFindFast()
+*/
+CX_INLINE CX_NONNULL CX_NODISCARD
+void *cxTreeFind(CxTree *tree, const void *data, bool use_dfs) {
+if (tree->root == NULL) return NULL;
+return cxTreeFindInSubtree(tree, data, tree->root, 0, use_dfs);
+}
+/**
+* Performs an efficient depth-first search in a branch of the specified tree.
+*
+* When @p max_depth is zero, the depth is not limited.
+* The @p subtree_root itself is on depth 1 and its children have depth 2.
+*
+* @note When @p subtree_root is not @c NULL and not part of the @p tree,
+* the behavior is undefined.
+*
+* @param tree the tree
+* @param data the data to search for
+* @param sfunc the search function
+* @param subtree_root the node where to start (@c NULL to start from root)
 * @param max_depth the maximum search depth
 * @return the first matching node, or @c NULL when the data cannot be found
-*/
+* @see cxTreeFindInSubtree()
-cx_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.
 *
 * @param tree the tree
 * @param subtree_root the root node of the subtree
 * @return the number of nodes in the specified subtree
 */
-cx_attr_nonnull cx_attr_nodiscard
+CX_EXTERN CX_NONNULL CX_NODISCARD
-CX_EXPORT size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root);
+size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root);
 /**
 * Determines the depth of the specified subtree.
 *
 * @param tree the tree
 * @param subtree_root the root node of the subtree
 * @return the tree depth including the @p subtree_root
 */
-cx_attr_nonnull  cx_attr_nodiscard
+CX_EXTERN CX_NONNULL CX_NODISCARD
-CX_EXPORT size_t cxTreeSubtreeDepth(CxTree *tree, void *subtree_root);
+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_EXTERN CX_NONNULL CX_NODISCARD
-CX_EXPORT size_t cxTreeSize(CxTree *tree);
+size_t cxTreeSize(CxTree *tree);
 /**
 * Determines the depth of the entire tree.
 *
 * @param tree the tree
 * @return the tree depth, counting the root as one
 */
-cx_attr_nonnull cx_attr_nodiscard
+CX_EXTERN CX_NONNULL CX_NODISCARD
-CX_EXPORT size_t cxTreeDepth(CxTree *tree);
+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_nodiscard
+CX_EXTERN CX_NONNULL CX_NODISCARD
-CX_EXPORT CxTreeIterator cxTreeIterateSubtree(CxTree *tree, void *node, bool visit_on_exit);
+CxTreeIterator cxTreeIterateSubtree(CxTree *tree, void *node, bool visit_on_exit);
 /**
 * Creates a breadth-first iterator for the specified tree starting in @p node.
 *
 * If the node is not part of the tree, the behavior is undefined.
 * @param tree the tree to iterate
 * @param node the node where to start
 * @return a tree visitor (a.k.a. breadth-first iterator)
 * @see cxTreeIterate()
 */
-cx_attr_nonnull cx_attr_nodiscard
+CX_EXTERN CX_NONNULL CX_NODISCARD
-CX_EXPORT CxTreeVisitor cxTreeVisitSubtree(CxTree *tree, void *node);
+CxTreeIterator cxTreeVisitSubtree(CxTree *tree, void *node);
 /**
 * Creates a depth-first iterator for the specified tree.
 *
 * @param tree the tree to iterate
 * @param visit_on_exit true, if the iterator shall visit a node again when
 * leaving the subtree
 * @return a tree iterator (depth-first)
 * @see cxTreeVisit()
 */
-cx_attr_nonnull cx_attr_nodiscard
+CX_EXTERN CX_NONNULL CX_NODISCARD
-CX_EXPORT CxTreeIterator cxTreeIterate(CxTree *tree, bool visit_on_exit);
+CxTreeIterator cxTreeIterate(CxTree *tree, bool visit_on_exit);
 /**
 * Creates a breadth-first iterator for the specified tree.
 *
 * @param tree the tree to iterate
 * @return a tree visitor (a.k.a. breadth-first iterator)
 * @see cxTreeIterate()
 */
-cx_attr_nonnull cx_attr_nodiscard
+CX_EXTERN CX_NONNULL CX_NODISCARD
-CX_EXPORT CxTreeVisitor cxTreeVisit(CxTree *tree);
+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_EXTERN CX_NONNULL
-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 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 #cxTreeAddData() (e.g., use
-* the same allocator).
+* 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.
-*
-* 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
+* @return the added node or @c NULL when the allocation failed
-* @see cxTreeInsert()
+* @see cxTreeAdd()
 */
-cx_attr_nonnull
+CX_EXTERN CX_NONNULL
-CX_EXPORT int cxTreeAddChild(CxTree *tree, void *parent, const void *data);
+void *cxTreeAddData(CxTree *tree, void *parent, const void *data);
+/**
+* Creates a new node and adds it to the tree.
+*
+* @param tree the tree
+* @param parent the parent node of the new node
+* @return the added node or @c NULL when the allocation failed
+*/
+CX_EXTERN CX_NODISCARD CX_NONNULL
+void *cxTreeCreateNode(CxTree *tree, void *parent);
+/**
+* Creates a new root node or returns the existing root node.
+*
+* @param tree the tree
+* @return the new root node, the existing root node, or @c NULL when the allocation failed
+* @see cxTreeCreateRootData()
+*/
+CX_EXTERN CX_NODISCARD CX_NONNULL
+void *cxTreeCreateRoot(CxTree *tree);
+/**
+* Creates a new root node or uses the existing root node and writes the specified data to that node.
+*
+* @note This function immediately returns @c NULL when @c loc_data was not initialized with a positive value.
+*
+* @param tree the tree
+* @param data the data for the root node
+* @return the new root node, the existing root node,
+* or @c NULL when the allocation failed or the data location is not known
+* @see cxTreeCreateRoot()
+*/
+CX_EXTERN CX_NODISCARD CX_NONNULL
+void *cxTreeCreateRootData(CxTree *tree, const void *data);
+/**
+* Exchanges the root of the tree.
+*
+* @attention The old tree nodes might need to be deallocated by the caller.
+* On the other hand, when the tree has destructors registered, keep in mind
+* that they will be applied to the new tree.
+* In particular, using cxTreeCreate() with a @c NULL root and setting the
+* root with this function is @em not equivalent to creating the tree with
+* a reference to an existing root because trees created without a root will
+* have destructors registered.
+*
+* @param tree the tree
+* @param new_root the new root node
+* @return the old root node (or @c NULL when the tree was empty)
+*/
+CX_EXTERN CX_NONNULL_ARG(1) CX_NODISCARD
+void *cxTreeSetRoot(CxTree *tree, void *new_root);
 /**
 * A function that is invoked when a node needs to be re-linked to a new parent.
 *
 * When a node is re-linked, sometimes the contents need to be updated.
 * @param node the node to remove (must not be the root node)
 * @param relink_func optional callback to update the content of each re-linked
 * node
 * @return zero on success, non-zero if @p node is the root node of the tree
 */
-cx_attr_nonnull_arg(1, 2)
+CX_EXTERN CX_NONNULL_ARG(1, 2)
-CX_EXPORT int cxTreeRemoveNode(CxTree *tree, void *node, cx_tree_relink_func relink_func);
+int cxTreeRemoveNode(CxTree *tree, void *node, cx_tree_relink_func relink_func);
 /**
 * Removes a node and its subtree from the tree.
 *
 * If the node is not part of the tree, the behavior is undefined.
 * 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_EXTERN CX_NONNULL
-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 node the node to destroy (must not be the root node)
 * @param relink_func optional callback to update the content of each re-linked
 * node
 * @return zero on success, non-zero if @p node is the root node of the tree
 */
-cx_attr_nonnull_arg(1, 2)
+CX_EXTERN CX_NONNULL_ARG(1, 2)
-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
 #endif //UCX_TREE_H

Mercurial > hg > toolkit / file comparison

comparison: ucx/cx/tree.h

ucx/cx/tree.h