Mercurial > hg > ucx / changeset

--- a/src/tree.c	Mon Aug 19 18:46:49 2024 +0200
+++ b/src/tree.c	Mon Aug 19 20:46:36 2024 +0200
@@ -40,6 +40,26 @@
 #define tree_prev(node) CX_TREE_PTR(node, loc_prev)
 #define tree_next(node) CX_TREE_PTR(node, loc_next)
 
+#define cx_tree_ptr_locations \
+    loc_parent, loc_children, loc_last_child, loc_prev, loc_next
+
+static void cx_tree_zero_pointers(
+        void *node,
+        ptrdiff_t loc_parent,
+        ptrdiff_t loc_children,
+        ptrdiff_t loc_last_child,
+        ptrdiff_t loc_prev,
+        ptrdiff_t loc_next
+) {
+    tree_parent(node) = NULL;
+    tree_prev(node) = NULL;
+    tree_next(node) = NULL;
+    tree_children(node) = NULL;
+    if (loc_last_child >= 0) {
+        tree_last_child(node) = NULL;
+    }
+}
+
 void cx_tree_link(
         void *restrict parent,
         void *restrict node,
@@ -52,8 +72,7 @@
     void *current_parent = tree_parent(node);
     if (current_parent == parent) return;
     if (current_parent != NULL) {
-        cx_tree_unlink(node, loc_parent, loc_children, loc_last_child,
-                       loc_prev, loc_next);
+        cx_tree_unlink(node, cx_tree_ptr_locations);
     }
 
     if (tree_children(parent) == NULL) {
@@ -438,8 +457,50 @@
         ptrdiff_t loc_prev,
         ptrdiff_t loc_next
 ) {
-    // TODO: implement
-    return NULL;
+    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;
+    }
+
+    void *match = NULL;
+    int result = cx_tree_search(
+            *root,
+            src,
+            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;
+        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);
+        }
+    } 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);
+    }
+
+    return node;
 }
 
 unsigned int cx_tree_add_look_around_depth = 3;
@@ -456,8 +517,87 @@
         ptrdiff_t loc_prev,
         ptrdiff_t loc_next
 ) {
-    // TODO: implement
-    return 0;
+    size_t processed = 0;
+    void *current_node = *root;
+    for (void **eptr;
+         iter->valid(iter) && (eptr = iter->current(iter)) != NULL;
+         iter->next(iter)) {
+        void *elem = *eptr;
+
+        if (current_node == NULL) {
+            // no node in tree, yet - add a new one
+            current_node = cfunc(elem, NULL, cdata);
+            // node creation failed - stop processing
+            if (current_node == NULL) {
+                // but honestly... nothing should have been processed
+                assert(processed == 0);
+                return 0;
+            }
+            cx_tree_zero_pointers(current_node, cx_tree_ptr_locations);
+            *root = current_node;
+            processed++;
+            continue;
+        }
+
+        // start searching from current node
+        void *match;
+        int result;
+        unsigned int look_around_retries = cx_tree_add_look_around_depth;
+        cx_tree_add_look_around_retry:
+        result = cx_tree_search(
+                current_node,
+                elem,
+                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);
+            if (parent != NULL) {
+                if (look_around_retries > 0) {
+                    look_around_retries--;
+                    current_node = parent;
+                } else {
+                    // look around retries exhausted, start from the 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;
+            }
+        } 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_zero_pointers(node, cx_tree_ptr_locations);
+                cx_tree_link(match, node, cx_tree_ptr_locations);
+            }
+            current_node = node;
+        } 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)
+            current_node = match;
+        }
+
+        processed++;
+    }
+    return processed;
 }
 
 size_t cx_tree_add_array(

--- a/tests/test_tree.c	Mon Aug 19 18:46:49 2024 +0200
+++ b/tests/test_tree.c	Mon Aug 19 20:46:36 2024 +0200
@@ -49,13 +49,66 @@
     int data;
 } tree_node2;
 
+typedef struct tree_node_file {
+    struct tree_node_file *parent;
+    struct tree_node_file *next;
+    struct tree_node_file *prev;
+    struct tree_node_file *children;
+    struct tree_node_file *last_child;
+    char const *path;
+} tree_node_file;
+
+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;
+
+        // 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;
+    }
+}
+
+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);
+    if (len1 <= len2) {
+        if (memcmp(node->path, data, len1) == 0) {
+            return (int) (len2 - len1);
+        } else {
+            return -1;
+        }
+    } else {
+        return -1;
+    }
+}
+
 #define tree_node_layout \
     offsetof(tree_node, parent), offsetof(tree_node, children), -1, \
     offsetof(tree_node, prev), offsetof(tree_node, next)
-#define tree_node2_layout \
-    offsetof(tree_node2, parent), offsetof(tree_node2, children),\
-    offsetof(tree_node2, last_child), \
-    offsetof(tree_node2, prev), offsetof(tree_node2, next)
+#define tree_node_full_layout(structname) \
+    offsetof(structname, parent), offsetof(structname, children),\
+    offsetof(structname, last_child), \
+    offsetof(structname, prev), offsetof(structname, next)
+#define tree_node2_layout tree_node_full_layout(tree_node2)
+#define tree_node_file_layout tree_node_full_layout(tree_node_file)
 
 #define tree_children(type) offsetof(type, children), offsetof(type, next)
 
@@ -993,6 +1046,257 @@
     }
 }
 
+CX_TEST(test_tree_add_one) {
+    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;
+
+        tree_node_file *foo = cx_tree_add(
+                "/home/foo/",
+                tree_node_file_search,
+                create_tree_node_file, alloc,
+                &newroot, tree_node_file_layout
+        );
+        CX_TEST_ASSERT(newroot == &root);
+        tree_node_file *bar = cx_tree_add(
+                "/home/foo/bar/",
+                tree_node_file_search,
+                create_tree_node_file, alloc,
+                &newroot, tree_node_file_layout
+        );
+        CX_TEST_ASSERT(newroot == &root);
+
+        CX_TEST_ASSERT(bar->parent == foo);
+        CX_TEST_ASSERT(foo->parent == &home);
+
+        CX_TEST_ASSERT(talloc.alloc_total == 2);
+
+        cxFree(&talloc.base, foo);
+        cxFree(&talloc.base, bar);
+
+        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);
+    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;
+
+        tree_node_file *node;
+        node = cx_tree_add(
+                "/usr/lib/",
+                tree_node_file_search,
+                create_tree_node_file, alloc,
+                &newroot, tree_node_file_layout
+        );
+        CX_TEST_ASSERT(newroot == &root);
+        CX_TEST_ASSERT(node == &lib);
+
+        node = cx_tree_add(
+                "/home/",
+                tree_node_file_search,
+                create_tree_node_file, alloc,
+                &newroot, tree_node_file_layout
+        );
+        CX_TEST_ASSERT(newroot == &root);
+        CX_TEST_ASSERT(node == &home);
+
+        CX_TEST_ASSERT(talloc.alloc_total == 0);
+        CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
+    }
+    cx_testing_allocator_destroy(&talloc);
+}
+
+CX_TEST(test_tree_add_many) {
+    // adds many elements to an existing tree
+
+    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/lib64/",
+                "/usr/lib/foo.so"
+        };
+
+        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 == 4);
+
+        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);
+        tree_node_file *lib64 = usr.last_child;
+        CX_TEST_ASSERT(lib64 != NULL);
+        CX_TEST_ASSERT(lib64->path == paths[2]);
+        CX_TEST_ASSERT(lib64->prev == &lib);
+        CX_TEST_ASSERT(lib64->parent == &usr);
+        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, lib64);
+        cxFree(&talloc.base, libfoo);
+
+        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
+    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/lib/",
+                "/usr/lib/foo.so"
+        };
+
+        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);
+
+        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);
+
+        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)");
 
@@ -1016,6 +1320,12 @@
     cx_test_register(suite, test_tree_visitor_continue);
     cx_test_register(suite, test_tree_iterator_continue);
     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_many);
+    cx_test_register(suite, test_tree_add_many_skip_duplicates);
+    cx_test_register(suite, test_tree_add_create_from_array);
 
     return suite;
 }