Mercurial > hg > ucx / changeset

--- a/src/cx/tree.h	Sat Aug 17 11:14:39 2024 +0200
+++ b/src/cx/tree.h	Sun Aug 18 11:26:34 2024 +0200
@@ -412,43 +412,176 @@
 
 /**
  * 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).
+ * 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_fun)(void const*);
+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;
 
-__attribute__((__nonnull__))
+/**
+ * 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
 );

--- a/src/tree.c	Sat Aug 17 11:14:39 2024 +0200
+++ b/src/tree.c	Sun Aug 18 11:26:34 2024 +0200
@@ -429,10 +429,12 @@
 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
 ) {
@@ -440,13 +442,17 @@
     return NULL;
 }
 
+unsigned int cx_tree_add_look_around_depth = 3;
+
 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
 ) {
@@ -459,10 +465,12 @@
         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
 ) {
@@ -474,8 +482,9 @@
     // special case: one element does not need an iterator
     if (num == 1) {
         if (NULL != cx_tree_add(
-                src, sfunc, cfunc, root,
-                loc_parent, loc_children, loc_prev, loc_next)) {
+                src, sfunc, cfunc, cdata, root,
+                loc_parent, loc_children, loc_last_child,
+                loc_prev, loc_next)) {
             return 1;
         } else {
             return 0;
@@ -484,7 +493,8 @@
 
     // otherwise, create iterator and hand over to other function
     CxIterator iter = cxIterator(src, elem_size, num);
-    return cx_tree_add_iter(cxIteratorRef(iter), sfunc, cfunc, root,
-                            loc_parent, loc_children, loc_prev, loc_next);
+    return cx_tree_add_iter(cxIteratorRef(iter), sfunc, cfunc, cdata, root,
+                            loc_parent, loc_children, loc_last_child,
+                            loc_prev, loc_next);
 }