ucx: comparison src/cx/tree.h

-:387414a7afd8
+:d607a184925a
 *
 * @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_func)(void const *node, void const *data);
+typedef int (*cx_tree_search_data_func)(void const *node, void const *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.
+*
+* For example if a tree stores file path information, a node that is
+* describing a parent directory of a filename that is searched, shall
+* return a positive number to indicate that a child node might contain the
+* searched item. On the other hand, if the node denotes a path that is not a
+* prefix of the searched filename, the function would return -1 to indicate
+* that the search does not need to be continued in that branch.
+*
+* @param node the node that is currently investigated
+* @param new_node a new node with the information which is searched
+*
+* @return 0 if \p node contains the same data as \p new_node,
+* positive if one of the children might contain the data,
+* negative if neither the node, nor the children contains the data
+*/
+typedef int (*cx_tree_search_func)(void const *node, void const *new_node);
 /**
 * Searches for data in a tree.
 *
 * When the data cannot be found exactly, the search function might return a
 * closest result which might be a good starting point for adding a new node
-* to the tree.
+* 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
 * @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
 */
 __attribute__((__nonnull__))
+int cx_tree_search_data(
+void const *root,
+void const *data,
+cx_tree_search_data_func sfunc,
+void **result,
+ptrdiff_t loc_children,
+ptrdiff_t loc_next
+);
+/**
+* Searches for a node in a tree.
+*
+* When no node with the same data can be found, the search function might
+* return a closest result which might be a good starting point for adding the
+* new node to the tree (see also #cx_tree_add()).
+*
+* Depending on the tree structure it is not necessarily guaranteed that the
+* "closest" match is uniquely defined. This function will search for a node
+* with the best match according to the \p sfunc (meaning: the return value of
+* \p sfunc which is closest to zero). If that is also ambiguous, an arbitrary
+* node matching the criteria is returned.
+*
+* @param root the root node
+* @param 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
+*/
+__attribute__((__nonnull__))
 int cx_tree_search(
 void const *root,
-void const *data,
+void const *node,
 cx_tree_search_func sfunc,
 void **result,
 ptrdiff_t loc_children,
 ptrdiff_t loc_next
 );
 void *root,
 ptrdiff_t loc_children,
 ptrdiff_t loc_next
 );
+/**
+* Describes a function that creates a tree node from the specified data.
+* The first argument points to the data the node shall contain and
+* the 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)(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.
+*
+* 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 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 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()
+*/
+__attribute__((__nonnull__(1, 2, 3, 5, 6)))
+size_t cx_tree_add_iter(
+struct cx_iterator_base_s *iter,
+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 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, 8)))
+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_func cfunc,
+void *cdata,
+void **failed,
+void *root,
+ptrdiff_t loc_parent,
+ptrdiff_t loc_children,
+ptrdiff_t loc_last_child,
+ptrdiff_t loc_prev,
+ptrdiff_t loc_next
+);
+/**
+* Adds data to a tree.
+*
+* An adequate location where to add the new tree node is searched with the
+* specified \p sfunc.
+*
+* When a location is found, the \p cfunc will be invoked with \p cdata.
+*
+* The node returned by \p cfunc will be linked into the tree.
+* When \p sfunc returned a positive integer, the new node will be linked as a
+* child. The other children (now siblings of the new node) are then checked
+* with \p sfunc, whether they could be children of the new node and re-linked
+* accordingly.
+*
+* When \p sfunc returned zero and the found node has a parent, the new
+* node will be added as sibling - otherwise, the new node will be added
+* as a child.
+*
+* When \p sfunc returned a negative value, the new node will not be added to
+* the tree and this function returns a non-zero value.
+* The caller should check if \p cnode contains a node pointer and deal with the
+* node that could not be added.
+*
+* This function also returns a non-zero value when \p cfunc tries to allocate
+* a new node but fails to do so. In that case, the pointer stored to \p cnode
+* will be \c NULL.
+*
+* Multiple elements can be added more efficiently with
+* #cx_tree_add_array() or #cx_tree_add_iter().
+*
+* @param src a pointer to the data
+* @param sfunc a search function
+* @param cfunc a node creation function
+* @param cdata optional additional data
+* @param cnode the location where a pointer to the new node is stored
+* @param root the root node of the tree
+* @param loc_parent offset in the node struct for the parent pointer
+* @param loc_children offset in the node struct for the children linked list
+* @param loc_last_child optional offset in the node struct for the pointer to
+* the last child in the linked list (negative if there is no such pointer)
+* @param loc_prev 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
+*/
+__attribute__((__nonnull__(1, 2, 3, 5, 6)))
+int cx_tree_add(
+void const *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
+);
 #ifdef __cplusplus
 } // extern "C"
 #endif
 #endif //UCX_TREE_H

Mercurial > hg > ucx / file comparison

comparison: src/cx/tree.h

src/cx/tree.h