diff -r af0092d8789a -r e29c1f96646d src/tree.c
--- a/src/tree.c	Tue Aug 20 13:53:18 2024 +0200
+++ b/src/tree.c	Tue Aug 20 18:01:03 2024 +0200
@@ -33,7 +33,6 @@
 #include <assert.h>
 
 #define CX_TREE_PTR(cur, off) (*(void**)(((char*)(cur))+(off)))
-#define CX_TREE_PTR(cur, off) (*(void**)(((char*)(cur))+(off)))
 #define tree_parent(node) CX_TREE_PTR(node, loc_parent)
 #define tree_children(node) CX_TREE_PTR(node, loc_children)
 #define tree_last_child(node) CX_TREE_PTR(node, loc_last_child)
@@ -136,7 +135,7 @@
 
 int cx_tree_search(
         void const *root,
-        void const *data,
+        void const *node,
         cx_tree_search_func sfunc,
         void **result,
         ptrdiff_t loc_children,
@@ -146,7 +145,7 @@
     *result = NULL;
 
     // shortcut: compare root before doing anything else
-    ret = sfunc(root, data);
+    ret = sfunc(root, node);
     if (ret < 0) {
         return ret;
     } else if (ret == 0 || tree_children(root) == NULL) {
@@ -175,19 +174,19 @@
     // process the working stack
     while (work_size > 0) {
         // pop element
-        void const *node = work[--work_size];
+        void const *elem = work[--work_size];
 
         // apply the search function
-        ret = sfunc(node, data);
+        ret = sfunc(elem, node);
 
         if (ret == 0) {
             // if found, exit the search
-            *result = (void*) node;
+            *result = (void *) elem;
             work_size = 0;
             break;
         } else if (ret > 0) {
             // if children might contain the data, add them to the stack
-            void *c = tree_children(node);
+            void *c = tree_children(elem);
             while (c != NULL) {
                 cx_array_simple_add(work, c);
                 c = tree_next(c);
@@ -195,7 +194,7 @@
 
             // remember this node in case no child is suitable
             if (ret < ret_candidate) {
-                candidate = (void *) node;
+                candidate = (void *) elem;
                 ret_candidate = ret;
             }
         }
@@ -212,6 +211,22 @@
     return ret;
 }
 
+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
+) {
+    // it is basically the same implementation
+    return cx_tree_search(
+            root, data,
+            (cx_tree_search_func) sfunc,
+            result,
+            loc_children, loc_next);
+}
+
 static bool cx_tree_iter_valid(void const *it) {
     struct cx_tree_iterator_s const *iter = it;
     return iter->node != NULL;
@@ -446,75 +461,80 @@
 }
 
 static void cx_tree_add_link_duplicate(
-        void **root, void *original, void *duplicate,
+        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;
+        cx_tree_link(original, duplicate, cx_tree_ptr_locations);
     } else {
         cx_tree_link(shared_parent, duplicate, cx_tree_ptr_locations);
     }
 }
 
-void *cx_tree_add(
+static void cx_tree_add_link_new(
+        void *parent, void *node, cx_tree_search_func sfunc,
+        ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
+        ptrdiff_t loc_prev, ptrdiff_t loc_next
+) {
+    // check the current children one by one,
+    // if they could be children of the new node
+    void *child = tree_children(parent);
+    while (child != NULL) {
+        void *next = tree_next(child);
+
+        if (sfunc(node, child) > 0) {
+            // the sibling could be a child -> re-link
+            cx_tree_link(node, child, cx_tree_ptr_locations);
+        }
+
+        child = next;
+    }
+
+    // add new node as new child
+    cx_tree_link(parent, node, cx_tree_ptr_locations);
+}
+
+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
 ) {
-    if (*root == NULL) {
-        void *node = cfunc(src, NULL, cdata);
-        if (node == NULL) return NULL;
-        cx_tree_zero_pointers(node, cx_tree_ptr_locations);
-        *root = node;
-        return node;
-    }
+    *cnode = cfunc(src, cdata);
+    if (*cnode == NULL) return 1;
+    cx_tree_zero_pointers(*cnode, cx_tree_ptr_locations);
 
     void *match = NULL;
     int result = cx_tree_search(
-            *root,
-            src,
+            root,
+            *cnode,
             sfunc,
             &match,
             loc_children,
             loc_next
     );
 
-    void *node;
     if (result < 0) {
-        // new node is created as new parent
-        node = cfunc(src, NULL, cdata);
-        if (node == NULL) return NULL;
-        cx_tree_zero_pointers(node, cx_tree_ptr_locations);
-        cx_tree_link(node, *root, cx_tree_ptr_locations);
-        *root = node;
+        // node does not fit into the tree - return non-zero value
+        return 1;
     } 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_add_link_duplicate(
-                    root, match, node, cx_tree_ptr_locations);
-        }
+        // data already found in the tree, link duplicate
+        cx_tree_add_link_duplicate(match, *cnode, cx_tree_ptr_locations);
     } else {
-        // closest match found, add new node as child
-        node = cfunc(src, NULL, cdata);
-        if (node == NULL) return NULL;
-        cx_tree_zero_pointers(node, cx_tree_ptr_locations);
-        cx_tree_link(match, node, cx_tree_ptr_locations);
+        // closest match found, add new node
+        cx_tree_add_link_new(match, *cnode, sfunc, cx_tree_ptr_locations);
     }
 
-    return node;
+    return 0;
 }
 
 unsigned int cx_tree_add_look_around_depth = 3;
@@ -524,39 +544,34 @@
         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
 ) {
+    // erase the failed pointer
+    *failed = NULL;
+
     // iter not valid? cancel...
     if (!iter->valid(iter)) return 0;
 
     size_t processed = 0;
-    void *current_node = *root;
-    void *elem;
-
-    // if there is no root, yet - process the first node from the iter
-    // as the new root node
-    if (current_node == NULL) {
-        elem = *(void **) (iter->current(iter));
-        // no node in tree, yet - add a new one
-        current_node = cfunc(elem, NULL, cdata);
-        // node creation failed - stop processing
-        if (current_node == NULL) return 0;
-        cx_tree_zero_pointers(current_node, cx_tree_ptr_locations);
-        *root = current_node;
-        processed++;
-        iter->next(iter);
-    }
+    void *current_node = root;
+    void const *elem;
 
     for (void **eptr;
          iter->valid(iter) && (eptr = iter->current(iter)) != NULL;
          iter->next(iter)) {
         elem = *eptr;
 
+        // create the new node
+        void *new_node = cfunc(elem, cdata);
+        if (new_node == NULL) return processed;
+        cx_tree_zero_pointers(new_node, cx_tree_ptr_locations);
+
         // start searching from current node
         void *match;
         int result;
@@ -564,14 +579,13 @@
         cx_tree_add_look_around_retry:
         result = cx_tree_search(
                 current_node,
-                elem,
+                new_node,
                 sfunc,
                 &match,
                 loc_children,
                 loc_next
         );
 
-        void *node;
         if (result < 0) {
             // traverse upwards and try to find better parents
             void *parent = tree_parent(current_node);
@@ -581,35 +595,23 @@
                     current_node = parent;
                 } else {
                     // look around retries exhausted, start from the root
-                    current_node = *root;
+                    current_node = root;
                 }
                 goto cx_tree_add_look_around_retry;
             } else {
-                // no parents. so we (try to) create a new root node
-                void *new_root = cfunc(elem, NULL, cdata);
-                if (new_root == NULL) return processed;
-                cx_tree_zero_pointers(new_root, cx_tree_ptr_locations);
-                cx_tree_link(new_root, current_node, cx_tree_ptr_locations);
-                current_node = new_root;
-                *root = new_root;
+                // no parents. so we failed
+                *failed = new_node;
+                return processed;
             }
         } else if (result == 0) {
-            // data already found in the tree, let cfunc decide
-            node = cfunc(elem, match, cdata);
-            if (node == NULL) return processed;
-            if (node != match) {
-                cx_tree_add_link_duplicate(
-                        root, match, node, cx_tree_ptr_locations);
-            }
-            current_node = node;
+            // data already found in the tree, link duplicate
+            cx_tree_add_link_duplicate(match, new_node, cx_tree_ptr_locations);
+            // but stick with the original match, in case we needed a new root
+            current_node = match;
         } else {
             // closest match found, add new node as child
-            node = cfunc(elem, NULL, cdata);
-            if (node == NULL) return processed;
-            cx_tree_zero_pointers(node, cx_tree_ptr_locations);
-            cx_tree_link(match, node, cx_tree_ptr_locations);
-            // but make the match current and not the new node
-            // (usually saves one traversal when a lot of siblings are added)
+            cx_tree_add_link_new(match, new_node, sfunc,
+                                 cx_tree_ptr_locations);
             current_node = match;
         }
 
@@ -625,13 +627,17 @@
         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
 ) {
+    // erase failed pointer
+    *failed = NULL;
+
     // super special case: zero elements
     if (num == 0) {
         return 0;
@@ -639,19 +645,22 @@
 
     // special case: one element does not need an iterator
     if (num == 1) {
-        if (NULL != cx_tree_add(
-                src, sfunc, cfunc, cdata, root,
+        void *node;
+        if (0 == cx_tree_add(
+                src, sfunc, cfunc, cdata, &node, root,
                 loc_parent, loc_children, loc_last_child,
                 loc_prev, loc_next)) {
             return 1;
         } else {
+            *failed = node;
             return 0;
         }
     }
 
     // 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, cdata, root,
+    return cx_tree_add_iter(cxIteratorRef(iter), sfunc,
+                            cfunc, cdata, failed, root,
                             loc_parent, loc_children, loc_last_child,
                             loc_prev, loc_next);
 }