--- a/src/cx/tree.h Sun Jul 07 14:56:44 2024 +0200
+++ b/src/cx/tree.h Tue Aug 20 18:02:39 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,
@@ -410,6 +469,192 @@
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