ucx: comparison src/cx/tree.h

-:4a220afebad0
+:7d3061f212cb
 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
-typedef void (*cx_tree_node_create_fun)(void const*);
+* the second, optional, argument points to an existing node that already
+* contains the data.
-__attribute__((__nonnull__))
+* The third 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, a pointer to the existing node, or \c NULL when allocation
+* fails.
+* Returning a pointer to the existing node means, that the function decides
+* not to create a new node for the data and that the caller shall continue to
+* use the existing node.
+*/
+typedef void (*cx_tree_node_create_func)(void const *, void const *, void *);
+/**
+* The local search depth for a new subtree when adding multiple elements.
+* The default value is 3.
+* This variable is used by #cx_tree_add_array() and #cx_tree_add_iter() to
+* implement optimized insertion of multiple elements into a tree.
+*/
+extern unsigned int cx_tree_add_look_around_depth;
+/**
+* Adds multiple elements efficiently to a tree.
+*
+* This function returns the number of elements successfully obtained from the
+* iterator, which is not necessarily the number of new nodes created (depending
+* on the implementation of \p cfunc).
+*
+* 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.
+*
+* 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 sfunc a search function
+* @param cfunc a node creation function
+* @param cdata optional additional data
+* @param root the location where a pointer to the root node is 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 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 elements obtained from the iterator
+* @see cx_tree_add()
+*/
+__attribute__((__nonnull__(1, 2, 3, 5)))
 size_t cx_tree_add_iter(
 struct cx_iterator_base_s *iter,
 cx_tree_search_func sfunc,
-cx_tree_node_create_fun cfunc,
+cx_tree_node_create_func cfunc,
+void *cdata,
 void **root,
 ptrdiff_t loc_parent,
 ptrdiff_t loc_children,
+ptrdiff_t loc_last_child,
 ptrdiff_t loc_prev,
 ptrdiff_t loc_next
 );
-__attribute__((__nonnull__))
+/**
+* Adds multiple elements efficiently to a tree.
+*
+* This function returns the number of elements successfully processed which
+* is not necessarily the number of new nodes created (depending on the
+* implementation of \p cfunc).
+*
+* Once an element cannot be added to the tree, this function returns.
+* That means, the integer \c n returned by this function means, that the first
+* \c n elements of \p src will be definitely in the tree.
+*
+* 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 root the location where a pointer to the root node is 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 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()
+*/
+__attribute__((__nonnull__(1, 4, 5, 7)))
 size_t cx_tree_add_array(
 void const *src,
 size_t num,
 size_t elem_size,
 cx_tree_search_func sfunc,
-cx_tree_node_create_fun cfunc,
+cx_tree_node_create_func cfunc,
+void *cdata,
 void **root,
 ptrdiff_t loc_parent,
 ptrdiff_t loc_children,
+ptrdiff_t loc_last_child,
 ptrdiff_t loc_prev,
 ptrdiff_t loc_next
 );
-__attribute__((__nonnull__))
+/**
+* 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 and,
+* in case \p sfunc returned a direct match, the already found node.
+*
+* If \p cfunc returns a new node pointer, it will be linked into the tree.
+* Otherwise, this function just returns the found node.
+*
+* This function may return \c NULL when \p cfunc tries to allocate a new node
+* but fails to do so.
+*
+* The \p root argument shall point to a location where the pointer to the root
+* node is stored. The pointer to the root node may be \c NULL in which case
+* this function will instantly create a new node and write the location to
+* \p root. On the other hand, if \p sfunc returns a negative integer for
+* \c *root, the newly created node will be the new root node.
+*
+* 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 root the location where a pointer to the root node is 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 offset in the node struct for the prev pointer
+* @param loc_next offset in the node struct for the next pointer
+* @return a pointer to the new node, to an existing node, or \c NULL
+*/
+__attribute__((__nonnull__(1, 2, 3, 5)))
 void *cx_tree_add(
 void const *src,
 cx_tree_search_func sfunc,
-cx_tree_node_create_fun cfunc,
+cx_tree_node_create_func cfunc,
+void *cdata,
 void **root,
 ptrdiff_t loc_parent,
 ptrdiff_t loc_children,
+ptrdiff_t loc_last_child,
 ptrdiff_t loc_prev,
 ptrdiff_t loc_next
 );
 #ifdef __cplusplus

Mercurial > hg > ucx / file comparison

comparison: src/cx/tree.h

src/cx/tree.h