--- a/src/cx/tree.h Tue Aug 20 13:53:18 2024 +0200
+++ b/src/cx/tree.h Tue Aug 20 18:01:03 2024 +0200
@@ -321,15 +321,41 @@
* 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
@@ -348,9 +374,42 @@
* 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,
@@ -413,21 +472,14 @@
/**
* 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
- * contains the data.
- * The third argument may be used for additional data (e.g. an allocator).
+ * 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, 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.
+ * 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 where the node will be
- * added to the tree.
+ * The caller is responsible to set them according to the intended use case.
*/
-typedef void *(*cx_tree_node_create_func)(void const *, void const *, void *);
+typedef void *(*cx_tree_node_create_func)(void const *, void *);
/**
* The local search depth for a new subtree when adding multiple elements.
@@ -440,13 +492,14 @@
/**
* 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
@@ -462,23 +515,25 @@
* @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,
@@ -489,13 +544,12 @@
/**
* 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.
+ * 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
@@ -513,7 +567,8 @@
* @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
@@ -523,7 +578,7 @@
* @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,
@@ -531,7 +586,8 @@
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,
@@ -545,26 +601,26 @@
* 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.
+ * When a location is found, the \p cfunc will be invoked with \p cdata.
*
- * If \p cfunc returns a new node pointer, it will be linked into the tree.
+ * 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. 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 the new root.
- * When \p sfunc returned a negative value, the new node will always be the
- * new root.
+ * 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.
*
- * If \p cfunc returns an existing node found by \p sfunc, this function just
- * returns the found node without modifying the tree.
+ * 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.
*
- * This function may return \c NULL when \p cfunc tries to allocate a new node
- * but fails to do so.
+ * 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.
*
- * 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.
+ * 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().
@@ -573,22 +629,25 @@
* @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,