Mercurial > hg > ucx / changeset

--- a/src/cx/tree.h	Mon Aug 19 20:46:36 2024 +0200
+++ b/src/cx/tree.h	Tue Aug 20 11:02:54 2024 +0200
@@ -549,7 +549,14 @@
  * 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.
+ * 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.
+ *
+ * If \p cfunc returns an existing node found by \p sfunc, this function just
+ * returns the found node without modifying the tree.
  *
  * This function may return \c NULL when \p cfunc tries to allocate a new node
  * but fails to do so.
@@ -557,8 +564,7 @@
  * 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.
+ * \p root.
  *
  * Multiple elements can be added more efficiently with
  * #cx_tree_add_array() or #cx_tree_add_iter().

--- a/src/tree.c	Mon Aug 19 20:46:36 2024 +0200
+++ b/src/tree.c	Tue Aug 20 11:02:54 2024 +0200
@@ -445,6 +445,21 @@
     return iter;
 }
 
+static void cx_tree_add_link_duplicate(
+        void **root, void *original, void *duplicate,
+        ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
+        ptrdiff_t loc_prev, ptrdiff_t loc_next
+) {
+    cx_tree_zero_pointers(duplicate, cx_tree_ptr_locations);
+    void *shared_parent = tree_parent(original);
+    if (shared_parent == NULL) {
+        cx_tree_link(duplicate, original, cx_tree_ptr_locations);
+        *root = duplicate;
+    } else {
+        cx_tree_link(shared_parent, duplicate, cx_tree_ptr_locations);
+    }
+}
+
 void *cx_tree_add(
         void const *src,
         cx_tree_search_func sfunc,
@@ -483,14 +498,13 @@
         cx_tree_zero_pointers(node, cx_tree_ptr_locations);
         cx_tree_link(node, *root, cx_tree_ptr_locations);
         *root = node;
-        return node;
     } else if (result == 0) {
         // data already found in the tree, let cfunc decide
         node = cfunc(src, match, cdata);
         if (node == NULL) return NULL;
         if (node != match) {
-            cx_tree_zero_pointers(node, cx_tree_ptr_locations);
-            cx_tree_link(match, node, cx_tree_ptr_locations);
+            cx_tree_add_link_duplicate(
+                    root, match, node, cx_tree_ptr_locations);
         }
     } else {
         // closest match found, add new node as child
@@ -580,8 +594,8 @@
             node = cfunc(elem, match, cdata);
             if (node == NULL) return processed;
             if (node != match) {
-                cx_tree_zero_pointers(node, cx_tree_ptr_locations);
-                cx_tree_link(match, node, cx_tree_ptr_locations);
+                cx_tree_add_link_duplicate(
+                        root, match, node, cx_tree_ptr_locations);
             }
             current_node = node;
         } else {