ucx: comparison src/cx/tree.h

-:af0092d8789a
+:e29c1f96646d
 *
 * @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
 );
 );
 /**
 * 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, optional, argument points to an existing node that already
+* the second argument may be used for additional data (e.g. an allocator).
-* contains the data.
-* 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
+* created node or \c NULL when allocation fails.
-* 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.
 *
 * \note the function may leave the node pointers in the struct uninitialized.
-* The caller is responsible to set them according to where the node will be
+* The caller is responsible to set them according to the intended use case.
-* added to the tree.
+*/
-*/
+typedef void *(*cx_tree_node_create_func)(void const *, void *);
-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
 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.
+* 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
 *
 * @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 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 elements obtained from the iterator
+* @return the number of nodes created and added
 * @see cx_tree_add()
 */
-__attribute__((__nonnull__(1, 2, 3, 5)))
+__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 **root,
+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.
 *
-* This function returns the number of elements successfully processed which
+* Once an element cannot be added to the tree, this function returns, storing
-* is not necessarily the number of new nodes created (depending on the
+* the pointer of the created node to \p failed.
-* implementation of \p cfunc).
+* The integer returned by this function denotes the number of elements from
-*
+* the \p src array that have been successfully processed.
-* Once an element cannot be added to the tree, this function returns.
+* When all elements could be processed, a \c NULL pointer will be written to
-* That means, the integer \c n returned by this function means, that the first
+* \p failed.
-* \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
 * @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 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)))
+__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 **root,
+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 and,
+* When a location is found, the \p cfunc will be invoked with \p cdata.
-* in case \p sfunc returned a direct match, the already found node.
+*
-*
+* The node returned by \p cfunc will be linked into the tree.
-* If \p cfunc returns a new node pointer, it will be linked into the tree.
 * When \p sfunc returned a positive integer, the new node will be linked as a
-* child. When \p sfunc returned zero and the found node has a parent, the new
+* child. The other children (now siblings of the new node) are then checked
-* node will be added as sibling - otherwise, the new node will be the new root.
+* with \p sfunc, whether they could be children of the new node and re-linked
-* When \p sfunc returned a negative value, the new node will always be the
+* accordingly.
-* new root.
+*
-*
+* When \p sfunc returned zero and the found node has a parent, the new
-* If \p cfunc returns an existing node found by \p sfunc, this function just
+* node will be added as sibling - otherwise, the new node will be added
-* returns the found node without modifying the tree.
+* as a child.
 *
-* This function may return \c NULL when \p cfunc tries to allocate a new node
+* When \p sfunc returned a negative value, the new node will not be added to
-* but fails to do so.
+* 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
-* The \p root argument shall point to a location where the pointer to the root
+* node that could not be added.
-* 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
+* This function also returns a non-zero value when \p cfunc tries to allocate
-* \p root.
+* 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 root the location where a pointer to the root node is stored
+* @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 a pointer to the new node, to an existing node, or \c NULL
+* @return zero when a new node was created and added to the tree,
-*/
+* non-zero otherwise
-__attribute__((__nonnull__(1, 2, 3, 5)))
+*/
-void *cx_tree_add(
+__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 **root,
+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

Mercurial > hg > ucx / file comparison

comparison: src/cx/tree.h

src/cx/tree.h