Mercurial > hg > ucx / changeset

--- a/src/cx/tree.h	Wed Oct 02 19:11:40 2024 +0200
+++ b/src/cx/tree.h	Thu Oct 03 15:38:05 2024 +0200
@@ -701,14 +701,14 @@
     /**
      * Allocator to allocate new nodes.
      */
-    CxAllocator *allocator;
+    const CxAllocator *allocator;
 
     /**
      * A pointer to the root node.
      *
      * Will be \c NULL when \c size is 0.
      */
-    struct cx_tree_node_base_s *root;
+    void *root;
 
     /**
      * A function to create new nodes.
@@ -872,7 +872,7 @@
  * 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.
  *
- * \note This function will also register a simple destructor which
+ * \note This function will also register an advanced destructor which
  * will free the nodes with the allocator's free() method.
  *
  * @param allocator the allocator that shall be used
@@ -907,8 +907,8 @@
  * member (or at least respect the default offsets specified in the tree
  * struct) and they MUST be allocated with the default stdlib allocator.
  *
- * \note This function will also register a simple destructor which
- * will free the nodes with the default stdlib allocator.
+ * \note This function will also register an advanced destructor which
+ * will free the nodes with the #cxDefaultAllocator.
  *
  * @param create_func a function that creates new nodes
  * @param search_func a function that compares two nodes
@@ -1081,6 +1081,16 @@
 }
 
 /**
+ * Determines the size of the specified subtree.
+ *
+ * @param tree the tree
+ * @param subtree_root the root node of the subtree
+ * @return the number of nodes in the specified subtree
+ */
+__attribute__((__nonnull__))
+size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root);
+
+/**
  * Creates a depth-first iterator for the specified tree.
  *
  * @param tree the tree to iterate

--- a/src/tree.c	Wed Oct 02 19:11:40 2024 +0200
+++ b/src/tree.c	Thu Oct 03 15:38:05 2024 +0200
@@ -666,6 +666,91 @@
                             loc_prev, loc_next);
 }
 
+static void cx_tree_default_destructor(CxTree *tree) {
+    // TODO: destroy the nodes
+    cxFree(tree->allocator, tree);
+}
+
+static CxTreeIterator cx_tree_default_iterator(
+        CxTree *tree,
+        bool visit_on_exit
+) {
+    return cx_tree_iterator(
+            tree->root, visit_on_exit,
+            tree->loc_children, tree->loc_next
+    );
+}
+
+static CxTreeVisitor cx_tree_default_visitor(CxTree *tree) {
+    return cx_tree_visitor(tree->root, tree->loc_children, tree->loc_next);
+}
+
+static cx_tree_class cx_tree_default_class = {
+        cx_tree_default_destructor,
+        NULL,
+        NULL,
+        NULL,
+        cx_tree_default_iterator,
+        cx_tree_default_visitor
+};
+
+CxTree *cxTreeCreate(
+        const CxAllocator *allocator,
+        cx_tree_node_create_func create_func,
+        cx_tree_search_func search_func,
+        ptrdiff_t loc_parent,
+        ptrdiff_t loc_children,
+        ptrdiff_t loc_last_child,
+        ptrdiff_t loc_prev,
+        ptrdiff_t loc_next
+) {
+    CxTree *tree = cxMalloc(allocator, sizeof(CxTree));
+    if (tree == NULL) return NULL;
+
+    tree->cl = &cx_tree_default_class;
+    tree->allocator = allocator;
+    tree->node_create = create_func;
+    tree->search = search_func;
+    tree->advanced_destructor = (cx_destructor_func2) cxFree;
+    tree->destructor_data = (void *) allocator;
+    tree->loc_parent = loc_parent;
+    tree->loc_children = loc_children;
+    tree->loc_last_child = loc_last_child;
+    tree->loc_prev = loc_prev;
+    tree->loc_next = loc_next;
+    tree->root = NULL;
+    tree->size = 0;
+
+    return tree;
+}
+
+CxTree *cxTreeCreateWrapped(
+        void *root,
+        ptrdiff_t loc_parent,
+        ptrdiff_t loc_children,
+        ptrdiff_t loc_last_child,
+        ptrdiff_t loc_prev,
+        ptrdiff_t loc_next
+) {
+    CxTree *tree = malloc(sizeof(CxTree));
+    if (tree == NULL) return NULL;
+
+    tree->cl = &cx_tree_default_class;
+    // set the allocator anyway, just in case...
+    tree->allocator = cxDefaultAllocator;
+    tree->node_create = NULL;
+    tree->search = NULL;
+    tree->advanced_destructor = NULL;
+    tree->destructor_data = NULL;
+    tree->loc_parent = loc_parent;
+    tree->loc_children = loc_children;
+    tree->loc_last_child = loc_last_child;
+    tree->loc_prev = loc_prev;
+    tree->loc_next = loc_next;
+    tree->root = root;
+    tree->size = cxTreeSubtreeSize(tree, root);
+    return tree;
+}
 
 int cxTreeAddChild(
         CxTree *tree,
@@ -678,3 +763,15 @@
     tree->size++;
     return 0;
 }
+
+size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root) {
+    CxTreeVisitor visitor = cx_tree_visitor(
+            subtree_root,
+            tree->loc_children,
+            tree->loc_next
+    );
+    while (cxIteratorValid(visitor)) {
+        cxIteratorNext(visitor);
+    }
+    return visitor.counter;
+}

--- a/tests/test_tree.c	Wed Oct 02 19:11:40 2024 +0200
+++ b/tests/test_tree.c	Thu Oct 03 15:38:05 2024 +0200
@@ -54,7 +54,7 @@
     const char *path;
 } tree_node_file;
 
-static void *create_tree_node_file(
+static void *tree_node_file_create(
         const void *dptr,
         void *allocator) {
     if (allocator == NULL) allocator = cxDefaultAllocator;
@@ -1057,7 +1057,7 @@
         result = cx_tree_add(
                 "/home/foo/",
                 tree_node_file_search,
-                create_tree_node_file, alloc,
+                tree_node_file_create, alloc,
                 (void **) &foo, &root,
                 tree_node_file_layout
         );
@@ -1068,7 +1068,7 @@
         size_t added = cx_tree_add_array(
                 bar_path, 1, sizeof(const char *),
                 tree_node_file_search,
-                create_tree_node_file, alloc,
+                tree_node_file_create, alloc,
                 &failed, &root,
                 tree_node_file_layout
         );
@@ -1084,7 +1084,7 @@
         result = cx_tree_add(
                 "newroot",
                 tree_node_file_search,
-                create_tree_node_file, alloc,
+                tree_node_file_create, alloc,
                 (void **) &new_node, &root,
                 tree_node_file_layout
         );
@@ -1126,7 +1126,7 @@
         int result = cx_tree_add(
                 "/usr/lib/",
                 tree_node_file_search,
-                create_tree_node_file, alloc,
+                tree_node_file_create, alloc,
                 (void **) &node, &root,
                 tree_node_file_layout
         );
@@ -1151,7 +1151,7 @@
         int result = cx_tree_add(
                 "/usr/lib/",
                 tree_node_file_search,
-                create_tree_node_file, NULL,
+                tree_node_file_create, NULL,
                 (void **) &node, &root,
                 tree_node_file_layout
         );
@@ -1164,7 +1164,7 @@
         size_t added = cx_tree_add_array(
                 "/", 1, sizeof(const char *),
                 tree_node_file_search,
-                create_tree_node_file, NULL,
+                tree_node_file_create, NULL,
                 (void **) &node, &root,
                 tree_node_file_layout
         );
@@ -1184,7 +1184,7 @@
         int result = cx_tree_add(
                 "/",
                 tree_node_file_search,
-                create_tree_node_file, NULL,
+                tree_node_file_create, NULL,
                 (void **) &node, &root,
                 tree_node_file_layout
         );
@@ -1207,7 +1207,7 @@
         size_t processed = cx_tree_add_array(
                 (void *) 0xc0ffee, 0, sizeof(void *),
                 tree_node_file_search,
-                create_tree_node_file, alloc,
+                tree_node_file_create, alloc,
                 &failed, &root, tree_node_file_layout
         );
         CX_TEST_ASSERT(failed == NULL);
@@ -1219,7 +1219,7 @@
                 cxIteratorRef(iter),
                 10, // deliberately specify more than the iter has
                 tree_node_file_search,
-                create_tree_node_file, alloc,
+                tree_node_file_create, alloc,
                 &failed, &root, tree_node_file_layout
         );
         CX_TEST_ASSERT(processed == 0);
@@ -1263,7 +1263,7 @@
         size_t processed = cx_tree_add_array(
                 paths, 4, sizeof(const char *),
                 tree_node_file_search,
-                create_tree_node_file, alloc,
+                tree_node_file_create, alloc,
                 &failed, &root, tree_node_file_layout
         );
 
@@ -1328,7 +1328,7 @@
         size_t processed = cx_tree_add_iter(
                 cxIteratorRef(iter), 3,
                 tree_node_file_search,
-                create_tree_node_file, alloc,
+                tree_node_file_create, alloc,
                 &failed, &root, tree_node_file_layout
         );
 
@@ -1384,7 +1384,7 @@
         size_t processed = cx_tree_add_array(
                 paths, 5, sizeof(const char *),
                 tree_node_file_search,
-                create_tree_node_file, alloc,
+                tree_node_file_create, alloc,
                 (void **) &failed, &root, tree_node_file_layout
         );
 
@@ -1428,7 +1428,7 @@
     size_t processed = cx_tree_add_array(
             paths, 10, sizeof(const char *),
             tree_node_file_search,
-            create_tree_node_file, alloc,
+            tree_node_file_create, alloc,
             &failed, &root, tree_node_file_layout
     );
 
@@ -1526,6 +1526,88 @@
     cx_testing_allocator_destroy(&talloc);
 }
 
+CX_TEST(test_tree_high_create) {
+    CxTestingAllocator talloc;
+    cx_testing_allocator_init(&talloc);
+    CX_TEST_DO {
+        CxTree *tree = cxTreeCreate(
+                &talloc.base,
+                tree_node_file_create,
+                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->search == tree_node_file_search);
+        CX_TEST_ASSERT(tree->size == 0);
+        CX_TEST_ASSERT(tree->simple_destructor == NULL);
+        CX_TEST_ASSERT(tree->advanced_destructor == (cx_destructor_func2) cxFree);
+        CX_TEST_ASSERT(tree->destructor_data == &talloc.base);
+        CX_TEST_ASSERT(tree->root == NULL);
+        CX_TEST_ASSERT(tree->loc_parent == offsetof(tree_node_file, parent));
+        CX_TEST_ASSERT(tree->loc_children == offsetof(tree_node_file, children));
+        CX_TEST_ASSERT(tree->loc_last_child == offsetof(tree_node_file, last_child));
+        CX_TEST_ASSERT(tree->loc_prev == offsetof(tree_node_file, prev));
+        CX_TEST_ASSERT(tree->loc_next == offsetof(tree_node_file, next));
+
+        CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc));
+        CX_TEST_ASSERT(talloc.alloc_total == 1);
+
+        cxTreeDestroy(tree);
+        CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
+    }
+    cx_testing_allocator_destroy(&talloc);
+}
+
+CX_TEST(test_tree_high_create_simple) {
+    CX_TEST_DO {
+        CxTree *tree = cxTreeCreateSimple(
+                tree_node_file_create,
+                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->search == tree_node_file_search);
+        CX_TEST_ASSERT(tree->size == 0);
+        CX_TEST_ASSERT(tree->simple_destructor == NULL);
+        CX_TEST_ASSERT(tree->advanced_destructor == (cx_destructor_func2) cxFree);
+        CX_TEST_ASSERT(tree->destructor_data == cxDefaultAllocator);
+        CX_TEST_ASSERT(tree->root == NULL);
+        CX_TEST_ASSERT(tree->loc_parent == offsetof(struct cx_tree_node_base_s, parent));
+        CX_TEST_ASSERT(tree->loc_children == offsetof(struct cx_tree_node_base_s, children));
+        CX_TEST_ASSERT(tree->loc_last_child == offsetof(struct cx_tree_node_base_s, last_child));
+        CX_TEST_ASSERT(tree->loc_prev == offsetof(struct cx_tree_node_base_s, prev));
+        CX_TEST_ASSERT(tree->loc_next == offsetof(struct cx_tree_node_base_s, next));
+        cxTreeDestroy(tree);
+    }
+}
+
+CX_TEST(test_tree_high_create_wrapped) {
+    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);
+    CX_TEST_DO {
+        CxTree *tree = cxTreeCreateWrapped(&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->root == &root);
+        CX_TEST_ASSERT(tree->size == 4);
+        CX_TEST_ASSERT(tree->simple_destructor == NULL);
+        CX_TEST_ASSERT(tree->advanced_destructor == NULL);
+        CX_TEST_ASSERT(tree->destructor_data == NULL);
+        CX_TEST_ASSERT(tree->loc_parent == offsetof(tree_node, parent));
+        CX_TEST_ASSERT(tree->loc_children == offsetof(tree_node, children));
+        CX_TEST_ASSERT(tree->loc_last_child == -1);
+        CX_TEST_ASSERT(tree->loc_prev == offsetof(tree_node, prev));
+        CX_TEST_ASSERT(tree->loc_next == offsetof(tree_node, next));
+        cxTreeDestroy(tree);
+    }
+}
 
 CxTestSuite *cx_test_suite_tree_low_level(void) {
     CxTestSuite *suite = cx_test_suite_new("tree (low level)");
@@ -1562,3 +1644,13 @@
 
     return suite;
 }
+
+CxTestSuite *cx_test_suite_tree_high_level(void) {
+    CxTestSuite *suite = cx_test_suite_new("tree (high level)");
+
+    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);
+
+    return suite;
+}

--- a/tests/ucxtest.c	Wed Oct 02 19:11:40 2024 +0200
+++ b/tests/ucxtest.c	Thu Oct 03 15:38:05 2024 +0200
@@ -40,11 +40,10 @@
 CxTestSuite *cx_test_suite_empty_list(void);
 CxTestSuite *cx_test_suite_array_list(void);
 CxTestSuite *cx_test_suite_linked_list(void);
-
 CxTestSuite *cx_test_suite_array_list_defaulted_funcs(void);
-
 CxTestSuite *cx_test_suite_linked_list_defaulted_funcs(void);
 CxTestSuite *cx_test_suite_tree_low_level(void);
+CxTestSuite *cx_test_suite_tree_high_level(void);
 CxTestSuite *cx_test_suite_mempool(void);
 CxTestSuite *cx_test_suite_hash_map(void);
 
@@ -72,6 +71,7 @@
             cx_test_suite_array_list_defaulted_funcs(),
             cx_test_suite_linked_list_defaulted_funcs(),
             cx_test_suite_tree_low_level(),
+            cx_test_suite_tree_high_level(),
             cx_test_suite_mempool(),
             cx_test_suite_hash_map()
     );