Mercurial > hg > ucx / changeset

--- a/src/cx/tree.h	Thu Oct 03 15:42:35 2024 +0200
+++ b/src/cx/tree.h	Thu Oct 03 16:31:09 2024 +0200
@@ -905,11 +905,12 @@
  *
  * Nodes created by \p create_func MUST contain #cx_tree_node_base_s as first
  * member (or at least respect the default offsets specified in the tree
- * struct) and they MUST be allocated with the default stdlib allocator.
+ * struct) and they MUST be allocated with the specified allocator.
  *
  * \note This function will also register an advanced destructor which
- * will free the nodes with the #cxDefaultAllocator.
+ * will free the nodes with the allocator's free() method.
  *
+ * @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
  * @return the new tree
@@ -917,11 +918,16 @@
  */
 __attribute__((__nonnull__, __warn_unused_result__))
 static inline CxTree *cxTreeCreateSimple(
+        const CxAllocator *allocator,
         cx_tree_node_create_func create_func,
         cx_tree_search_func search_func
 ) {
-    return cxTreeCreate(cxDefaultAllocator,
-            create_func, search_func, cx_tree_node_base_layout);
+    return cxTreeCreate(
+            allocator,
+            create_func,
+            search_func,
+            cx_tree_node_base_layout
+    );
 }
 
 /**
@@ -960,9 +966,8 @@
  *
  * \attention This function will only invoke the destructor functions
  * on the nodes, if specified.
- * It will NOT automatically free the nodes with the allocator, because that
- * will cause a double-free in scenarios where this tree structure is wrapping
- * a tree which memory is managed by someone else.
+ * It will NOT additionally free the nodes with the tree's allocator, because
+ * that would cause a double-free in most scenarios.
  *
  * @param tree the tree to destroy
  */
@@ -1034,7 +1039,7 @@
     if (n == 0) return 0;
     if (n == 1) return 0 == cxTreeInsert(tree, data) ? 1 : 0;
     CxIterator iter = cxIterator(data, elem_size, n);
-    return tree->cl->insert_many(tree, cxIteratorRef(iter), n);
+    return cxTreeInsertIter(tree, cxIteratorRef(iter), n);
 }
 
 /**

--- a/src/tree.c	Thu Oct 03 15:42:35 2024 +0200
+++ b/src/tree.c	Thu Oct 03 16:31:09 2024 +0200
@@ -667,7 +667,19 @@
 }
 
 static void cx_tree_default_destructor(CxTree *tree) {
-    // TODO: destroy the nodes
+    if (tree->simple_destructor != NULL || tree->advanced_destructor != NULL) {
+        CxTreeIterator iter = tree->cl->iterator(tree, true);
+        cx_foreach(void *, node, iter) {
+            if (iter.exiting) {
+                if (tree->simple_destructor) {
+                    tree->simple_destructor(node);
+                }
+                if (tree->advanced_destructor) {
+                    tree->advanced_destructor(tree->destructor_data, node);
+                }
+            }
+        }
+    }
     cxFree(tree->allocator, tree);
 }
 
@@ -685,10 +697,60 @@
     return cx_tree_visitor(tree->root, tree->loc_children, tree->loc_next);
 }
 
+static int cx_tree_default_insert_element(
+        CxTree *tree,
+        const void *data
+) {
+    void *node;
+    if (tree->root == NULL) {
+        node = tree->node_create(data, tree);
+        if (node == NULL) return 1;
+        cx_tree_zero_pointers(node, cx_tree_node_layout(tree));
+        tree->root = node;
+        tree->size = 1;
+        return 0;
+    }
+    int result = cx_tree_add(data, tree->search, tree->node_create,
+                tree, &node, tree->root, cx_tree_node_layout(tree));
+    if (0 == result) {
+        tree->size++;
+    } else {
+        cxFree(tree->allocator, node);
+    }
+    return result;
+}
+
+static size_t cx_tree_default_insert_many(
+        CxTree *tree,
+        struct cx_iterator_base_s *iter,
+        size_t n
+) {
+    size_t ins = 0;
+    if (!iter->valid(iter)) return 0;
+    if (tree->root == NULL) {
+        // use the first element from the iter to create the root node
+        void **eptr = iter->current(iter);
+        void *node = tree->node_create(*eptr, tree);
+        if (node == NULL) return 0;
+        cx_tree_zero_pointers(node, cx_tree_node_layout(tree));
+        tree->root = node;
+        ins = 1;
+        iter->next(iter);
+    }
+    void *failed;
+    ins += cx_tree_add_iter(iter, n, tree->search, tree->node_create,
+                                  tree, &failed, tree->root, cx_tree_node_layout(tree));
+    tree->size += ins;
+    if (ins < n) {
+        cxFree(tree->allocator, failed);
+    }
+    return ins;
+}
+
 static cx_tree_class cx_tree_default_class = {
         cx_tree_default_destructor,
-        NULL,
-        NULL,
+        cx_tree_default_insert_element,
+        cx_tree_default_insert_many,
         NULL,
         cx_tree_default_iterator,
         cx_tree_default_visitor

--- a/tests/test_tree.c	Thu Oct 03 15:42:35 2024 +0200
+++ b/tests/test_tree.c	Thu Oct 03 16:31:09 2024 +0200
@@ -72,6 +72,12 @@
     return node;
 }
 
+static void *tree_node_file_create_hl(
+        const void *dptr,
+        void *tree) {
+    return tree_node_file_create(dptr, (void*)((CxTree*)tree)->allocator);
+}
+
 static int tree_node_file_search(const void *l, const void *r) {
     const tree_node_file *left = l;
     const tree_node_file *right = r;
@@ -1532,13 +1538,13 @@
     CX_TEST_DO {
         CxTree *tree = cxTreeCreate(
                 &talloc.base,
-                tree_node_file_create,
+                tree_node_file_create_hl,
                 tree_node_file_search,
                 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);
+        CX_TEST_ASSERT(tree->node_create == tree_node_file_create_hl);
         CX_TEST_ASSERT(tree->search == tree_node_file_search);
         CX_TEST_ASSERT(tree->size == 0);
         CX_TEST_ASSERT(tree->simple_destructor == NULL);
@@ -1563,12 +1569,13 @@
 CX_TEST(test_tree_high_create_simple) {
     CX_TEST_DO {
         CxTree *tree = cxTreeCreateSimple(
-                tree_node_file_create,
+                cxDefaultAllocator,
+                tree_node_file_create_hl,
                 tree_node_file_search
         );
         CX_TEST_ASSERT(tree->cl != NULL);
         CX_TEST_ASSERT(tree->allocator == cxDefaultAllocator);
-        CX_TEST_ASSERT(tree->node_create == tree_node_file_create);
+        CX_TEST_ASSERT(tree->node_create == tree_node_file_create_hl);
         CX_TEST_ASSERT(tree->search == tree_node_file_search);
         CX_TEST_ASSERT(tree->size == 0);
         CX_TEST_ASSERT(tree->simple_destructor == NULL);
@@ -1624,6 +1631,70 @@
     cxTreeDestroy(tree);
 }
 
+CX_TEST(test_tree_high_insert_one) {
+    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_layout
+        );
+
+        int result = 0;
+        result |= cxTreeInsert(tree, "/");
+        result |= cxTreeInsert(tree, "/usr/");
+        result |= cxTreeInsert(tree, "/home/");
+        result |= cxTreeInsert(tree, "/usr/lib/");
+        result |= cxTreeInsert(tree, "/home/foo/");
+        CX_TEST_ASSERT(result == 0);
+        CX_TEST_ASSERT(1 == cxTreeInsertArray(tree, "/home/foo/bar/", sizeof(const char*), 1));
+        CX_TEST_ASSERT(tree->size == 6);
+        CX_TEST_ASSERT(0 != cxTreeInsert(tree, "newroot"));
+        CX_TEST_ASSERT(tree->size == 6);
+
+        CX_TEST_ASSERT(talloc.alloc_total == 8);
+        CX_TEST_ASSERT(talloc.free_total == 1); // the one that could not be added
+
+        cxTreeDestroy(tree);
+        CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
+    }
+    cx_testing_allocator_destroy(&talloc);
+}
+
+CX_TEST(test_tree_high_insert_many) {
+    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_layout
+        );
+
+        const char *paths[] = {
+                "/",
+                "/usr/",
+                "/home/",
+                "/usr/lib/",
+                "/home/foo/",
+                "/home/foo/bar/",
+                "newroot"
+        };
+        CX_TEST_ASSERT(6 == cxTreeInsertArray(tree, paths, sizeof(const char*), 7));
+        CX_TEST_ASSERT(tree->size == 6);
+
+        CX_TEST_ASSERT(talloc.alloc_total == 8);
+        CX_TEST_ASSERT(talloc.free_total == 1); // the one that could not be added
+
+        cxTreeDestroy(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)");
 
@@ -1667,6 +1738,8 @@
     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_insert_one);
+    cx_test_register(suite, test_tree_high_insert_many);
 
     return suite;
 }