Mercurial > hg > ucx / changeset

--- a/src/cx/tree.h	Thu Oct 03 16:31:09 2024 +0200
+++ b/src/cx/tree.h	Thu Oct 03 17:39:21 2024 +0200
@@ -436,7 +436,6 @@
  * @return the new tree iterator
  * @see cxTreeIteratorDispose()
  */
-__attribute__((__nonnull__))
 CxTreeIterator cx_tree_iterator(
         void *root,
         bool visit_on_exit,
@@ -462,7 +461,6 @@
  * @return the new tree visitor
  * @see cxTreeVisitorDispose()
  */
-__attribute__((__nonnull__))
 CxTreeVisitor cx_tree_visitor(
         void *root,
         ptrdiff_t loc_children,
@@ -741,6 +739,11 @@
     cx_tree_search_func search;
 
     /**
+     * A function to compare a node with data.
+     */
+    cx_tree_search_data_func search_data;
+
+    /**
      * The number of currently stored elements.
      */
     size_t size;
@@ -878,6 +881,7 @@
  * @param allocator the allocator that shall be used
  * @param create_func a function that creates new nodes
  * @param search_func a function that compares two nodes
+ * @param search_data_func a function that compares a node with data
  * @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
@@ -893,6 +897,7 @@
         const CxAllocator *allocator,
         cx_tree_node_create_func create_func,
         cx_tree_search_func search_func,
+        cx_tree_search_data_func search_data_func,
         ptrdiff_t loc_parent,
         ptrdiff_t loc_children,
         ptrdiff_t loc_last_child,
@@ -913,6 +918,7 @@
  * @param allocator the allocator that shall be used
  * @param create_func a function that creates new nodes
  * @param search_func a function that compares two nodes
+ * @param search_data_func a function that compares a node with data
  * @return the new tree
  * @see cxTreeCreate()
  */
@@ -920,12 +926,14 @@
 static inline CxTree *cxTreeCreateSimple(
         const CxAllocator *allocator,
         cx_tree_node_create_func create_func,
-        cx_tree_search_func search_func
+        cx_tree_search_func search_func,
+        cx_tree_search_data_func search_data_func
 ) {
     return cxTreeCreate(
             allocator,
             create_func,
             search_func,
+            search_data_func,
             cx_tree_node_base_layout
     );
 }
@@ -933,8 +941,7 @@
 /**
  * Creates a new tree structure based on an existing tree.
  *
- * The specified \p allocator will be used for creating the tree struct
- * and SHALL be used by \p create_func to allocate memory for the nodes.
+ * The specified \p allocator will be used for creating the tree struct.
  *
  * \attention This function will create an incompletely defined tree structure
  * where neither the create function, the search function, nor a destructor
@@ -953,6 +960,7 @@
  */
 __attribute__((__nonnull__, __warn_unused_result__))
 CxTree *cxTreeCreateWrapped(
+        const CxAllocator *allocator,
         void *root,
         ptrdiff_t loc_parent,
         ptrdiff_t loc_children,
@@ -1045,7 +1053,7 @@
 /**
  * Searches the data in the specified tree.
  *
- * \remark For this function to work, the tree needs a specified search
+ * \remark For this function to work, the tree needs a specified \c search_data
  * function, which might not be available wrapped trees
  * (see #cxTreeCreateWrapped()).
  *
@@ -1067,7 +1075,7 @@
  * \note When \p subtree_root is not part of the \p tree, the behavior is
  * undefined.
  *
- * \remark For this function to work, the tree needs a specified search
+ * \remark For this function to work, the tree needs a specified \c search_data
  * function, which might not be the case for wrapped trees
  * (see #cxTreeCreateWrapped()).
  *
@@ -1106,6 +1114,15 @@
 size_t cxTreeSubtreeDepth(CxTree *tree, void *subtree_root);
 
 /**
+ * Determines the depth of the entire tree.
+ *
+ * @param tree the tree
+ * @return the tree depth, counting the root as one
+ */
+__attribute__((__nonnull__))
+size_t cxTreeDepth(CxTree *tree);
+
+/**
  * Creates a depth-first iterator for the specified tree.
  *
  * @param tree the tree to iterate
@@ -1179,22 +1196,18 @@
 );
 
 /**
- * Removes a node from the tree.
+ * Removes a node and it's subtree from the tree.
  *
  * If the node is not part of the tree, the behavior is undefined.
  *
- * \note The destructor function, if any, will \em not be invoked.
+ * \note The destructor function, if any, will \em not be invoked. That means
+ * you will need to free the removed subtree by yourself, eventually.
  *
  * @param tree the tree
  * @param node the node to remove
  */
 __attribute__((__nonnull__))
-static inline void cxTreeRemove(
-        CxTree *tree,
-        void *node) {
-    cx_tree_unlink(node, cx_tree_node_layout(tree));
-    tree->size--;
-}
+void cxTreeRemove(CxTree *tree, void *node);
 
 #ifdef __cplusplus
 } // extern "C"

--- a/src/tree.c	Thu Oct 03 16:31:09 2024 +0200
+++ b/src/tree.c	Thu Oct 03 17:39:21 2024 +0200
@@ -241,6 +241,8 @@
     struct cx_tree_iterator_s *iter = it;
     ptrdiff_t const loc_next = iter->loc_next;
     ptrdiff_t const loc_children = iter->loc_children;
+    // protect us from misuse
+    if (!iter->base.valid(iter)) return;
 
     void *children;
 
@@ -326,17 +328,8 @@
     iter.loc_next = loc_next;
     iter.visit_on_exit = visit_on_exit;
 
-    // allocate stack
-    iter.stack_capacity = 16;
-    iter.stack = malloc(sizeof(void *) * 16);
-    iter.depth = 0;
-
-    // visit the root node
-    iter.node = root;
+    // initialize members
     iter.node_next = NULL;
-    iter.counter = 1;
-    iter.depth = 1;
-    iter.stack[0] = root;
     iter.exiting = false;
     iter.skip = false;
 
@@ -348,6 +341,21 @@
     iter.base.next = cx_tree_iter_next;
     iter.base.current = cx_tree_iter_current;
 
+    // visit the root node
+    iter.node = root;
+    if (root != NULL) {
+        iter.stack_capacity = 16;
+        iter.stack = malloc(sizeof(void *) * 16);
+        iter.stack[0] = root;
+        iter.counter = 1;
+        iter.depth = 1;
+    } else {
+        iter.stack_capacity = 0;
+        iter.stack = NULL;
+        iter.counter = 0;
+        iter.depth = 0;
+    }
+
     return iter;
 }
 
@@ -379,6 +387,9 @@
 
 static void cx_tree_visitor_next(void *it) {
     struct cx_tree_visitor_s *iter = it;
+    // protect us from misuse
+    if (!iter->base.valid(iter)) return;
+
     ptrdiff_t const loc_next = iter->loc_next;
     ptrdiff_t const loc_children = iter->loc_children;
 
@@ -438,13 +449,7 @@
     iter.loc_children = loc_children;
     iter.loc_next = loc_next;
 
-    // allocate stack
-    iter.depth = 0;
-
-    // visit the root node
-    iter.node = root;
-    iter.counter = 1;
-    iter.depth = 1;
+    // initialize members
     iter.skip = false;
     iter.queue_next = NULL;
     iter.queue_last = NULL;
@@ -457,6 +462,16 @@
     iter.base.next = cx_tree_visitor_next;
     iter.base.current = cx_tree_visitor_current;
 
+    // visit the root node
+    iter.node = root;
+    if (root != NULL) {
+        iter.counter = 1;
+        iter.depth = 1;
+    } else {
+        iter.counter = 0;
+        iter.depth = 0;
+    }
+
     return iter;
 }
 
@@ -747,11 +762,33 @@
     return ins;
 }
 
+static void *cx_tree_default_find(
+        CxTree *tree,
+        const void *subtree,
+        const void *data
+) {
+    if (tree->root == NULL) return NULL;
+
+    void *found;
+    if (0 == cx_tree_search_data(
+            subtree,
+            data,
+            tree->search_data,
+            &found,
+            tree->loc_children,
+            tree->loc_next
+    )) {
+        return found;
+    } else {
+        return NULL;
+    }
+}
+
 static cx_tree_class cx_tree_default_class = {
         cx_tree_default_destructor,
         cx_tree_default_insert_element,
         cx_tree_default_insert_many,
-        NULL,
+        cx_tree_default_find,
         cx_tree_default_iterator,
         cx_tree_default_visitor
 };
@@ -760,6 +797,7 @@
         const CxAllocator *allocator,
         cx_tree_node_create_func create_func,
         cx_tree_search_func search_func,
+        cx_tree_search_data_func search_data_func,
         ptrdiff_t loc_parent,
         ptrdiff_t loc_children,
         ptrdiff_t loc_last_child,
@@ -773,6 +811,7 @@
     tree->allocator = allocator;
     tree->node_create = create_func;
     tree->search = search_func;
+    tree->search_data = search_data_func;
     tree->advanced_destructor = (cx_destructor_func2) cxFree;
     tree->destructor_data = (void *) allocator;
     tree->loc_parent = loc_parent;
@@ -787,6 +826,7 @@
 }
 
 CxTree *cxTreeCreateWrapped(
+        const CxAllocator *allocator,
         void *root,
         ptrdiff_t loc_parent,
         ptrdiff_t loc_children,
@@ -794,14 +834,16 @@
         ptrdiff_t loc_prev,
         ptrdiff_t loc_next
 ) {
-    CxTree *tree = malloc(sizeof(CxTree));
+    CxTree *tree = cxMalloc(allocator, sizeof(CxTree));
     if (tree == NULL) return NULL;
 
     tree->cl = &cx_tree_default_class;
     // set the allocator anyway, just in case...
-    tree->allocator = cxDefaultAllocator;
+    tree->allocator = allocator;
     tree->node_create = NULL;
     tree->search = NULL;
+    tree->search_data = NULL;
+    tree->simple_destructor = NULL;
     tree->advanced_destructor = NULL;
     tree->destructor_data = NULL;
     tree->loc_parent = loc_parent;
@@ -849,3 +891,17 @@
     }
     return visitor.depth;
 }
+
+size_t cxTreeDepth(CxTree *tree) {
+    CxTreeVisitor visitor = tree->cl->visitor(tree);
+    while (cxIteratorValid(visitor)) {
+        cxIteratorNext(visitor);
+    }
+    return visitor.depth;
+}
+
+void cxTreeRemove(CxTree *tree, void *node) {
+    size_t subtree_size = cxTreeSubtreeSize(tree, node);
+    cx_tree_unlink(node, cx_tree_node_layout(tree));
+    tree->size -= subtree_size;
+}

--- a/tests/test_tree.c	Thu Oct 03 16:31:09 2024 +0200
+++ b/tests/test_tree.c	Thu Oct 03 17:39:21 2024 +0200
@@ -94,6 +94,12 @@
     }
 }
 
+static int tree_node_file_search_data(const void *l, const void *d) {
+    tree_node_file r;
+    r.path = d;
+    return tree_node_file_search(l, &r);
+}
+
 #define tree_node_layout \
     offsetof(tree_node, parent), offsetof(tree_node, children), -1, \
     offsetof(tree_node, prev), offsetof(tree_node, next)
@@ -1540,12 +1546,14 @@
                 &talloc.base,
                 tree_node_file_create_hl,
                 tree_node_file_search,
+                tree_node_file_search_data,
                 tree_node_file_layout
         );
         CX_TEST_ASSERT(tree->cl != NULL);
         CX_TEST_ASSERT(tree->allocator == &talloc.base);
         CX_TEST_ASSERT(tree->node_create == tree_node_file_create_hl);
         CX_TEST_ASSERT(tree->search == tree_node_file_search);
+        CX_TEST_ASSERT(tree->search_data == tree_node_file_search_data);
         CX_TEST_ASSERT(tree->size == 0);
         CX_TEST_ASSERT(tree->simple_destructor == NULL);
         CX_TEST_ASSERT(tree->advanced_destructor == (cx_destructor_func2) cxFree);
@@ -1571,12 +1579,14 @@
         CxTree *tree = cxTreeCreateSimple(
                 cxDefaultAllocator,
                 tree_node_file_create_hl,
-                tree_node_file_search
+                tree_node_file_search,
+                tree_node_file_search_data
         );
         CX_TEST_ASSERT(tree->cl != NULL);
         CX_TEST_ASSERT(tree->allocator == cxDefaultAllocator);
         CX_TEST_ASSERT(tree->node_create == tree_node_file_create_hl);
         CX_TEST_ASSERT(tree->search == tree_node_file_search);
+        CX_TEST_ASSERT(tree->search_data == tree_node_file_search_data);
         CX_TEST_ASSERT(tree->size == 0);
         CX_TEST_ASSERT(tree->simple_destructor == NULL);
         CX_TEST_ASSERT(tree->advanced_destructor == (cx_destructor_func2) cxFree);
@@ -1597,11 +1607,12 @@
     cx_tree_link(&root, &child2, tree_node_layout);
     cx_tree_link(&child1, &child3, tree_node_layout);
     CX_TEST_DO {
-        CxTree *tree = cxTreeCreateWrapped(&root, tree_node_layout);
+        CxTree *tree = cxTreeCreateWrapped(cxDefaultAllocator, &root, tree_node_layout);
         CX_TEST_ASSERT(tree->cl != NULL);
         CX_TEST_ASSERT(tree->allocator == cxDefaultAllocator);
         CX_TEST_ASSERT(tree->node_create == NULL);
         CX_TEST_ASSERT(tree->search == NULL);
+        CX_TEST_ASSERT(tree->search_data == NULL);
         CX_TEST_ASSERT(tree->root == &root);
         CX_TEST_ASSERT(tree->size == 4);
         CX_TEST_ASSERT(tree->simple_destructor == NULL);
@@ -1616,17 +1627,28 @@
     }
 }
 
-CX_TEST(test_tree_high_subtree_depth) {
+CX_TEST(test_tree_high_tree_depth) {
     tree_node root = {0}, child1 = {0}, child2 = {0}, child3 = {0};
     cx_tree_link(&root, &child1, tree_node_layout);
     cx_tree_link(&root, &child2, tree_node_layout);
     cx_tree_link(&child1, &child3, tree_node_layout);
-    CxTree *tree = cxTreeCreateWrapped(&root, tree_node_layout);
+    CxTree *tree = cxTreeCreateWrapped(cxDefaultAllocator, &root, tree_node_layout);
     CX_TEST_DO {
+        CX_TEST_ASSERT(cxTreeDepth(tree) == 3);
         CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &root) == 3);
         CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child1) == 2);
         CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child2) == 1);
         CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child3) == 1);
+
+        CxTree *empty = cxTreeCreate(
+                cxDefaultAllocator,
+                tree_node_file_create_hl,
+                tree_node_file_search,
+                tree_node_file_search_data,
+                tree_node_file_layout
+        );
+        CX_TEST_ASSERT(cxTreeDepth(empty) == 0);
+        cxTreeDestroy(empty);
     }
     cxTreeDestroy(tree);
 }
@@ -1638,7 +1660,8 @@
 
     CX_TEST_DO {
         CxTree *tree = cxTreeCreate(
-                alloc, tree_node_file_create_hl, tree_node_file_search,
+                alloc, tree_node_file_create_hl,
+                tree_node_file_search, tree_node_file_search_data,
                 tree_node_file_layout
         );
 
@@ -1670,7 +1693,8 @@
 
     CX_TEST_DO {
         CxTree *tree = cxTreeCreate(
-                alloc, tree_node_file_create_hl, tree_node_file_search,
+                alloc, tree_node_file_create_hl,
+                tree_node_file_search, tree_node_file_search_data,
                 tree_node_file_layout
         );
 
@@ -1695,6 +1719,76 @@
     cx_testing_allocator_destroy(&talloc);
 }
 
+CX_TEST(test_tree_high_add_find_remove_nodes) {
+    CxTestingAllocator talloc;
+    cx_testing_allocator_init(&talloc);
+    CxAllocator *alloc = &talloc.base;
+
+    CX_TEST_DO {
+        CxTree *tree = cxTreeCreate(
+                alloc, tree_node_file_create_hl,
+                tree_node_file_search, tree_node_file_search_data,
+                tree_node_file_layout
+        );
+
+        const char *paths[] = {
+                "/",
+                "/usr/",
+                "/home/",
+                "/usr/lib/",
+                "/home/foo/",
+                "/home/foo/bar/"
+        };
+        cxTreeInsertArray(tree, paths, sizeof(const char*), 6);
+
+        tree_node_file *foo = cxTreeFind(tree, "/home/foo/");
+        CX_TEST_ASSERT(NULL != foo);
+        CX_TEST_ASSERT(0 == strcmp("/home/foo/", foo->path));
+        CX_TEST_ASSERT(NULL != foo->parent);
+        CX_TEST_ASSERT(0 == strcmp("/home/", foo->parent->path));
+        CX_TEST_ASSERT(tree->size == 6);
+
+        CX_TEST_ASSERT(0 == cxTreeAddChild(tree, foo->parent, "/home/baz/"));
+        tree_node_file *baz = cxTreeFind(tree, "/home/baz/");
+        CX_TEST_ASSERT(NULL != baz);
+        CX_TEST_ASSERT(0 == strcmp("/home/baz/", baz->path));
+        CX_TEST_ASSERT(NULL != baz->parent);
+        CX_TEST_ASSERT(0 == strcmp("/home/", baz->parent->path));
+        CX_TEST_ASSERT(tree->size == 7);
+
+        tree_node_file *home = cxTreeFind(tree, "/home/");
+        CX_TEST_ASSERT(NULL == cxTreeFindInSubtree(tree, "/usr/", foo));
+        tree_node_file *bar = cxTreeFindInSubtree(tree, "/home/foo/bar/", home);
+        CX_TEST_ASSERT(NULL != bar);
+        CX_TEST_ASSERT(0 == strcmp("/home/foo/bar/", bar->path));
+        CX_TEST_ASSERT(bar->parent == foo);
+
+        tree_node_file *share = cxCalloc(alloc, 1, sizeof(tree_node_file));
+        share->path = "/usr/share/";
+        cxTreeAddChildNode(tree, cxTreeFind(tree, "/usr/"), share);
+        CX_TEST_ASSERT(tree->size == 8);
+
+        cxTreeRemove(tree, foo);
+        CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/foo/"));
+        CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/foo/bar/"));
+        CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/bar/"));
+        CX_TEST_ASSERT(tree->size == 6);
+
+        cxTreeDestroy(tree);
+        // we are not done yet, because we need to free the removed subtree
+        CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc));
+
+        // for this, we use a little trick and wrap the removed subtree
+        CxTree *foo_tree = cxTreeCreateWrapped(alloc, foo, tree_node_file_layout);
+        foo_tree->allocator = alloc;
+        foo_tree->advanced_destructor = (cx_destructor_func2 ) cxFree;
+        foo_tree->destructor_data = alloc;
+        cxTreeDestroy(foo_tree);
+        CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
+    }
+    cx_testing_allocator_destroy(&talloc);
+}
+
 CxTestSuite *cx_test_suite_tree_low_level(void) {
     CxTestSuite *suite = cx_test_suite_new("tree (low level)");
 
@@ -1737,9 +1831,10 @@
     cx_test_register(suite, test_tree_high_create);
     cx_test_register(suite, test_tree_high_create_simple);
     cx_test_register(suite, test_tree_high_create_wrapped);
-    cx_test_register(suite, test_tree_high_subtree_depth);
+    cx_test_register(suite, test_tree_high_tree_depth);
     cx_test_register(suite, test_tree_high_insert_one);
     cx_test_register(suite, test_tree_high_insert_many);
+    cx_test_register(suite, test_tree_high_add_find_remove_nodes);
 
     return suite;
 }