diff -r af0092d8789a -r e29c1f96646d tests/test_tree.c
--- a/tests/test_tree.c	Tue Aug 20 13:53:18 2024 +0200
+++ b/tests/test_tree.c	Tue Aug 20 18:01:03 2024 +0200
@@ -60,37 +60,29 @@
 
 static void *create_tree_node_file(
         void const *dptr,
-        void const *nptr,
         void *allocator) {
     if (allocator == NULL) allocator = cxDefaultAllocator;
 
-    char const *data = dptr;
-    tree_node_file const *existing = nptr;
-
-    if (existing != NULL && strcmp(existing->path, data) == 0) {
-        return (void *) existing;
-    } else {
-        tree_node_file *node = cxMalloc(allocator, sizeof(tree_node_file));
-
-        node->path = data;
+    tree_node_file *node = cxMalloc(allocator, sizeof(tree_node_file));
+    node->path = dptr;
 
-        // intentionally write garbage into the pointers, it's part of the test
-        node->parent = (void *) 0xf00ba1;
-        node->next = (void *) 0xf00ba2;
-        node->prev = (void *) 0xf00ba3;
-        node->children = (void *) 0xf00ba4;
-        node->last_child = (void *) 0xf00ba5;
+    // intentionally write garbage into the pointers, it's part of the test
+    node->parent = (void *) 0xf00ba1;
+    node->next = (void *) 0xf00ba2;
+    node->prev = (void *) 0xf00ba3;
+    node->children = (void *) 0xf00ba4;
+    node->last_child = (void *) 0xf00ba5;
 
-        return node;
-    }
+    return node;
 }
 
-static int tree_node_file_search(void const *nptr, void const *data) {
-    tree_node_file const *node = nptr;
-    size_t len1 = strlen(node->path);
-    size_t len2 = strlen(data);
+static int tree_node_file_search(void const *l, void const *r) {
+    tree_node_file const *left = l;
+    tree_node_file const *right = r;
+    size_t len1 = strlen(left->path);
+    size_t len2 = strlen(right->path);
     if (len1 <= len2) {
-        if (memcmp(node->path, data, len1) == 0) {
+        if (memcmp(left->path, right->path, len1) == 0) {
             return (int) (len2 - len1);
         } else {
             return -1;
@@ -429,38 +421,38 @@
     CX_TEST_DO {
         for (unsigned i = 0 ; i <= 10 ; i++) {
             s = testdata[i];
-            r = cx_tree_search(&root, &s, test_tree_search_function,
+            r = cx_tree_search_data(&root, &s, test_tree_search_function,
                                (void **) &n, tree_children(tree_node));
             CX_TEST_ASSERT(r == 0);
             CX_TEST_ASSERT(n == testnodes[i]);
         }
 
         s = -5;
-        r = cx_tree_search(&root, &s, test_tree_search_function,
+        r = cx_tree_search_data(&root, &s, test_tree_search_function,
                            (void **) &n, tree_children(tree_node));
         CX_TEST_ASSERT(r < 0);
         CX_TEST_ASSERT(n == NULL);
 
         s = 26;
-        r = cx_tree_search(&root, &s, test_tree_search_function,
+        r = cx_tree_search_data(&root, &s, test_tree_search_function,
                            (void **) &n, tree_children(tree_node));
         CX_TEST_ASSERT(r > 0);
         CX_TEST_ASSERT(n == &ba);
 
         s = 35;
-        r = cx_tree_search(&root, &s, test_tree_search_function,
+        r = cx_tree_search_data(&root, &s, test_tree_search_function,
                            (void **) &n, tree_children(tree_node));
         CX_TEST_ASSERT(r > 0);
         CX_TEST_ASSERT(n == &cb);
 
         s = 38;
-        r = cx_tree_search(&root, &s, test_tree_search_function,
+        r = cx_tree_search_data(&root, &s, test_tree_search_function,
                            (void **) &n, tree_children(tree_node));
         CX_TEST_ASSERT(r > 0);
         CX_TEST_ASSERT(n == &cba);
 
         s = 42;
-        r = cx_tree_search(&root, &s, test_tree_search_function,
+        r = cx_tree_search_data(&root, &s, test_tree_search_function,
                            (void **) &n, tree_children(tree_node));
         CX_TEST_ASSERT(r > 0);
         CX_TEST_ASSERT(n == &cc);
@@ -1064,60 +1056,58 @@
     cx_tree_link(&usr, &lib, tree_node_file_layout);
 
     CX_TEST_DO {
-        void *newroot = &root;
-
-        tree_node_file *foo = cx_tree_add(
+        tree_node_file *foo;
+        int result;
+        result = cx_tree_add(
                 "/home/foo/",
                 tree_node_file_search,
                 create_tree_node_file, alloc,
-                &newroot, tree_node_file_layout
+                (void **) &foo, &root,
+                tree_node_file_layout
         );
-        CX_TEST_ASSERT(newroot == &root);
-        tree_node_file *bar = cx_tree_add(
-                "/home/foo/bar/",
+        CX_TEST_ASSERT(result == 0);
+        CX_TEST_ASSERT(foo != NULL);
+        char const *bar_path = "/home/foo/bar/";
+        void *failed;
+        size_t added = cx_tree_add_array(
+                bar_path, 1, sizeof(char const *),
                 tree_node_file_search,
                 create_tree_node_file, alloc,
-                &newroot, tree_node_file_layout
+                &failed, &root,
+                tree_node_file_layout
         );
-        CX_TEST_ASSERT(newroot == &root);
-
+        CX_TEST_ASSERT(added == 1);
+        CX_TEST_ASSERT(failed == NULL);
+        tree_node_file *bar = foo->children;
+        CX_TEST_ASSERT(bar != NULL);
         CX_TEST_ASSERT(bar->parent == foo);
+        CX_TEST_ASSERT(bar->path == bar_path);
         CX_TEST_ASSERT(foo->parent == &home);
 
-        CX_TEST_ASSERT(talloc.alloc_total == 2);
+        tree_node_file *new_node;
+        result = cx_tree_add(
+                "newroot",
+                tree_node_file_search,
+                create_tree_node_file, alloc,
+                (void **) &new_node, &root,
+                tree_node_file_layout
+        );
+        CX_TEST_ASSERT(0 != result);
+        CX_TEST_ASSERT(NULL != new_node);
+        CX_TEST_ASSERT(new_node->children == NULL);
+        CX_TEST_ASSERT(new_node->parent == NULL);
 
-        cxFree(&talloc.base, foo);
-        cxFree(&talloc.base, bar);
+        CX_TEST_ASSERT(talloc.alloc_total == 3);
+
+        cxFree(alloc, foo);
+        cxFree(alloc, bar);
+        cxFree(alloc, new_node);
 
         CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
     }
     cx_testing_allocator_destroy(&talloc);
 }
 
-CX_TEST(test_tree_add_one_to_empty_tree) {
-    tree_node_file *node = NULL;
-    CX_TEST_DO {
-        tree_node_file *root = NULL;
-        char const *data = "/home/foo/bar/";
-
-        node = cx_tree_add(
-                data,
-                tree_node_file_search,
-                create_tree_node_file, NULL,
-                (void **) &root, tree_node_file_layout
-        );
-
-        CX_TEST_ASSERT(root != NULL);
-        CX_TEST_ASSERT(root->path == data);
-        CX_TEST_ASSERT(root->next == NULL);
-        CX_TEST_ASSERT(root->prev == NULL);
-        CX_TEST_ASSERT(root->children == NULL);
-        CX_TEST_ASSERT(root->last_child == NULL);
-        CX_TEST_ASSERT(root->parent == NULL);
-    }
-    free(node);
-}
-
 CX_TEST(test_tree_add_one_existing) {
     CxTestingAllocator talloc;
     cx_testing_allocator_init(&talloc);
@@ -1136,28 +1126,109 @@
     cx_tree_link(&usr, &lib, tree_node_file_layout);
 
     CX_TEST_DO {
-        void *newroot = &root;
-
         tree_node_file *node;
-        node = cx_tree_add(
+        int result = cx_tree_add(
                 "/usr/lib/",
                 tree_node_file_search,
                 create_tree_node_file, alloc,
-                &newroot, tree_node_file_layout
+                (void **) &node, &root,
+                tree_node_file_layout
+        );
+        CX_TEST_ASSERT(result == 0);
+        CX_TEST_ASSERT(node != &lib);
+        CX_TEST_ASSERT(node->prev == &lib);
+        CX_TEST_ASSERT(lib.next == node);
+        CX_TEST_ASSERT(node->parent == &usr);
+        CX_TEST_ASSERT(talloc.alloc_total == 1);
+        cxFree(alloc, node);
+        CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
+    }
+    cx_testing_allocator_destroy(&talloc);
+}
+
+CX_TEST(test_tree_add_one_no_match) {
+    tree_node_file root = {0};
+    root.path = "/mnt/";
+
+    CX_TEST_DO {
+        tree_node_file *node = NULL;
+        int result = cx_tree_add(
+                "/usr/lib/",
+                tree_node_file_search,
+                create_tree_node_file, NULL,
+                (void **) &node, &root,
+                tree_node_file_layout
         );
-        CX_TEST_ASSERT(newroot == &root);
-        CX_TEST_ASSERT(node == &lib);
+        CX_TEST_ASSERT(result != 0);
+        CX_TEST_ASSERT(node != NULL);
+        CX_TEST_ASSERT(node->parent == NULL);
+        CX_TEST_ASSERT(node->children == NULL);
+        free(node);
+        node = NULL;
+        size_t added = cx_tree_add_array(
+                "/", 1, sizeof(char const *),
+                tree_node_file_search,
+                create_tree_node_file, NULL,
+                (void **) &node, &root,
+                tree_node_file_layout
+        );
+        CX_TEST_ASSERT(added == 0);
+        CX_TEST_ASSERT(node != NULL);
+        CX_TEST_ASSERT(node->parent == NULL);
+        CX_TEST_ASSERT(node->children == NULL);
+        free(node);
+    }
+}
 
-        node = cx_tree_add(
-                "/home/",
+CX_TEST(test_tree_add_duplicate_root) {
+    tree_node_file root = {0};
+    root.path = "/";
+    CX_TEST_DO {
+        tree_node_file *node;
+        int result = cx_tree_add(
+                "/",
+                tree_node_file_search,
+                create_tree_node_file, NULL,
+                (void **) &node, &root,
+                tree_node_file_layout
+        );
+        CX_TEST_ASSERT(result == 0);
+        CX_TEST_ASSERT(root.children == node);
+        CX_TEST_ASSERT(node->parent == &root);
+    }
+}
+
+CX_TEST(test_tree_add_zero) {
+    CxTestingAllocator talloc;
+    cx_testing_allocator_init(&talloc);
+    CxAllocator *alloc = &talloc.base;
+
+    tree_node_file root = {0};
+    root.path = "/";
+    CX_TEST_DO {
+        void *failed;
+
+        size_t processed = cx_tree_add_array(
+                (void *) 0xc0ffee, 0, sizeof(void *),
                 tree_node_file_search,
                 create_tree_node_file, alloc,
-                &newroot, tree_node_file_layout
+                &failed, &root, tree_node_file_layout
         );
-        CX_TEST_ASSERT(newroot == &root);
-        CX_TEST_ASSERT(node == &home);
+        CX_TEST_ASSERT(failed == NULL);
+        CX_TEST_ASSERT(processed == 0);
+        CX_TEST_ASSERT(talloc.alloc_total == 0);
 
+        CxIterator iter = cxIterator(NULL, sizeof(void *), 0);
+        processed = cx_tree_add_iter(
+                cxIteratorRef(iter),
+                tree_node_file_search,
+                create_tree_node_file, alloc,
+                &failed, &root, tree_node_file_layout
+        );
+        CX_TEST_ASSERT(processed == 0);
+        CX_TEST_ASSERT(failed == NULL);
         CX_TEST_ASSERT(talloc.alloc_total == 0);
+
         CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
     }
     cx_testing_allocator_destroy(&talloc);
@@ -1183,7 +1254,7 @@
     cx_tree_link(&usr, &lib, tree_node_file_layout);
 
     CX_TEST_DO {
-        void *newroot = &root;
+        void *failed;
 
         char const *paths[] = {
                 "/home/foo/",
@@ -1196,10 +1267,10 @@
                 paths, 4, sizeof(char const *),
                 tree_node_file_search,
                 create_tree_node_file, alloc,
-                &newroot, tree_node_file_layout
+                &failed, &root, tree_node_file_layout
         );
-        CX_TEST_ASSERT(newroot == &root);
 
+        CX_TEST_ASSERT(failed == NULL);
         CX_TEST_ASSERT(processed == 4);
         CX_TEST_ASSERT(talloc.alloc_total == 4);
 
@@ -1219,83 +1290,180 @@
         tree_node_file *libfoo = lib.children;
         CX_TEST_ASSERT(libfoo != NULL && libfoo->path == paths[3]);
 
-        cxFree(&talloc.base, foo);
-        cxFree(&talloc.base, bar);
-        cxFree(&talloc.base, lib64);
-        cxFree(&talloc.base, libfoo);
+        cxFree(alloc, foo);
+        cxFree(alloc, bar);
+        cxFree(alloc, lib64);
+        cxFree(alloc, libfoo);
+
+        CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
+    }
+    cx_testing_allocator_destroy(&talloc);
+}
+
+CX_TEST(test_tree_add_many_with_dupl_and_no_match) {
+    CxTestingAllocator talloc;
+    cx_testing_allocator_init(&talloc);
+    CxAllocator *alloc = &talloc.base;
+
+    tree_node_file root = {0};
+    root.path = "/mnt/";
+
+    CX_TEST_DO {
+        tree_node_file *failed;
+
+        char const *paths[] = {
+                "/mnt/sdcard/",
+                "/mnt/foo/",
+                "/mnt/sdcard/",
+                "/home/",
+                "/usr/"
+        };
+
+        size_t processed = cx_tree_add_array(
+                paths, 5, sizeof(char const *),
+                tree_node_file_search,
+                create_tree_node_file, alloc,
+                (void **) &failed, &root, tree_node_file_layout
+        );
+
+        CX_TEST_ASSERT(processed == 3);
+        CX_TEST_ASSERT(failed != NULL);
+        CX_TEST_ASSERT(failed->parent == NULL);
+        CX_TEST_ASSERT(failed->children == NULL);
+        CX_TEST_ASSERT(strcmp(failed->path, "/home/") == 0);
+        cxFree(alloc, failed);
+
+        CX_TEST_ASSERT(root.children != root.last_child);
+        CX_TEST_ASSERT(strcmp(root.children->path, "/mnt/sdcard/") == 0);
+        CX_TEST_ASSERT(strcmp(root.last_child->path, "/mnt/sdcard/") == 0);
+        CX_TEST_ASSERT(strcmp(root.children->next->path, "/mnt/foo/") == 0);
+        CX_TEST_ASSERT(strcmp(root.last_child->prev->path, "/mnt/foo/") == 0);
+
+        CxTreeIterator iter = cx_tree_iterator(
+                &root, true,
+                offsetof(tree_node_file, children),
+                offsetof(tree_node_file, next)
+        );
+        cx_foreach(tree_node_file *, node, iter) {
+            if (iter.exiting) {
+                if (node != &root) {
+                    cxFree(alloc, node);
+                }
+            }
+        }
 
         CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
     }
     cx_testing_allocator_destroy(&talloc);
 }
 
-CX_TEST(test_tree_add_many_skip_duplicates) {
-    // adds many elements to an existing tree
+static CX_TEST_SUBROUTINE(test_tree_add_create_from_array_impl,
+                          CxAllocator *alloc, char const **paths) {
+    tree_node_file root = {0};
+    root.path = "/";
+
+    void *failed;
+    size_t processed = cx_tree_add_array(
+            paths, 10, sizeof(char const *),
+            tree_node_file_search,
+            create_tree_node_file, alloc,
+            &failed, &root, tree_node_file_layout
+    );
+
+    CX_TEST_ASSERT(failed == NULL);
+    CX_TEST_ASSERT(processed == 10);
+
+    char const *exp_order[] = {
+            "/",
+            "/usr/",
+            "/usr/lib/",
+            "/usr/lib/libbumm.so",
+            "/home/",
+            "/home/foo/",
+            "/var/",
+            "/var/www/",
+            "/var/www/vhosts/",
+            "/var/www/vhosts/live/",
+            "/var/www/vhosts/live/htdocs/"
+    };
+    unsigned exp_depth[] = {
+            1,
+            2,
+            3,
+            4,
+            2,
+            3,
+            2,
+            3,
+            4,
+            5,
+            6
+    };
+
+    CxTreeIterator iter = cx_tree_iterator(
+            &root, true,
+            offsetof(tree_node_file, children),
+            offsetof(tree_node_file, next)
+    );
+    cx_foreach(tree_node_file *, node, iter) {
+        if (iter.exiting) {
+            if (node != &root) {
+                cxFree(alloc, node);
+            }
+        } else {
+            CX_TEST_ASSERT(iter.counter <= 11);
+            CX_TEST_ASSERT(iter.depth == exp_depth[iter.counter - 1]);
+            CX_TEST_ASSERT(strcmp(node->path, exp_order[iter.counter - 1]) == 0);
+        }
+    }
+}
+
+CX_TEST(test_tree_add_create_from_array) {
+    // creates an entirely new tree from an array
+
     CxTestingAllocator talloc;
     cx_testing_allocator_init(&talloc);
     CxAllocator *alloc = &talloc.base;
 
-    tree_node_file root = {0};
-    root.path = "/";
-    tree_node_file usr = {0};
-    usr.path = "/usr/";
-    cx_tree_link(&root, &usr, tree_node_file_layout);
-    tree_node_file home = {0};
-    home.path = "/home/";
-    cx_tree_link(&root, &home, tree_node_file_layout);
-    tree_node_file lib = {0};
-    lib.path = "/usr/lib/";
-    cx_tree_link(&usr, &lib, tree_node_file_layout);
-
     CX_TEST_DO {
-        void *newroot = &root;
-
         char const *paths[] = {
-                "/home/foo/",
-                "/home/foo/bar",
+                "/usr/",
+                "/home/",
                 "/usr/lib/",
-                "/usr/lib/foo.so"
+                "/usr/lib/libbumm.so",
+                "/var/",
+                "/var/www/",
+                "/var/www/vhosts/",
+                "/var/www/vhosts/live/",
+                "/var/www/vhosts/live/htdocs/",
+                "/home/foo/"
         };
 
-        size_t processed = cx_tree_add_array(
-                paths, 4, sizeof(char const *),
-                tree_node_file_search,
-                create_tree_node_file, alloc,
-                &newroot, tree_node_file_layout
-        );
-        CX_TEST_ASSERT(newroot == &root);
-
-        CX_TEST_ASSERT(processed == 4);
-        CX_TEST_ASSERT(talloc.alloc_total == 3);
+        char const *scrambled_paths[] = {
+                "/usr/",
+                "/home/",
+                "/var/www/vhosts/live/",
+                "/usr/lib/",
+                "/var/",
+                "/var/www/",
+                "/usr/lib/libbumm.so",
+                "/var/www/vhosts/",
+                "/var/www/vhosts/live/htdocs/",
+                "/home/foo/"
+        };
 
-        CX_TEST_ASSERT(home.children == home.last_child);
-        tree_node_file *foo = home.children;
-        CX_TEST_ASSERT(foo != NULL && foo->path == paths[0]);
-        CX_TEST_ASSERT(foo->children == foo->last_child);
-        tree_node_file *bar = foo->children;
-        CX_TEST_ASSERT(bar != NULL && bar->path == paths[1]);
-        CX_TEST_ASSERT(usr.children == usr.last_child);
-        CX_TEST_ASSERT(usr.children == &lib);
-        CX_TEST_ASSERT(lib.children != NULL);
-        tree_node_file *libfoo = lib.children;
-        CX_TEST_ASSERT(libfoo != NULL && libfoo->path == paths[3]);
-
-        cxFree(&talloc.base, foo);
-        cxFree(&talloc.base, bar);
-        cxFree(&talloc.base, libfoo);
+        // no matter how the original array is sorted,
+        // the resulting tree should be the same
+        CX_TEST_CALL_SUBROUTINE(test_tree_add_create_from_array_impl, alloc,
+                                paths);
+        CX_TEST_CALL_SUBROUTINE(test_tree_add_create_from_array_impl, alloc,
+                                scrambled_paths);
 
         CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
     }
     cx_testing_allocator_destroy(&talloc);
 }
 
-CX_TEST(test_tree_add_create_from_array) {
-    // creates an entirely new tree from an array
-    CX_TEST_DO {
-
-    }
-}
-
 
 CxTestSuite *cx_test_suite_tree_low_level(void) {
     CxTestSuite *suite = cx_test_suite_new("tree (low level)");
@@ -1322,9 +1490,11 @@
     cx_test_register(suite, test_tree_iterator_continue_with_exit);
     cx_test_register(suite, test_tree_add_one);
     cx_test_register(suite, test_tree_add_one_existing);
-    cx_test_register(suite, test_tree_add_one_to_empty_tree);
+    cx_test_register(suite, test_tree_add_one_no_match);
+    cx_test_register(suite, test_tree_add_duplicate_root);
+    cx_test_register(suite, test_tree_add_zero);
     cx_test_register(suite, test_tree_add_many);
-    cx_test_register(suite, test_tree_add_many_skip_duplicates);
+    cx_test_register(suite, test_tree_add_many_with_dupl_and_no_match);
     cx_test_register(suite, test_tree_add_create_from_array);
 
     return suite;