Mercurial > hg > ucx / changeset

--- a/src/cx/tree.h	Sun Oct 06 12:40:44 2024 +0200
+++ b/src/cx/tree.h	Sun Oct 06 13:37:05 2024 +0200
@@ -811,14 +811,6 @@
  */
 struct cx_tree_class_s {
     /**
-     * Destructor function.
-     *
-     * Implementations SHALL invoke the node destructor functions if provided
-     * and SHALL deallocate the tree memory.
-     */
-    void (*destructor)(struct cx_tree_s *);
-
-    /**
      * Member function for inserting a single element.
      *
      * Implementations SHALL NOT simply invoke \p insert_many as this comes
@@ -970,21 +962,6 @@
 );
 
 /**
- * Destroys the tree structure.
- *
- * \attention This function will only invoke the destructor functions
- * on the nodes, if specified.
- * 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
- */
-__attribute__((__nonnull__))
-static inline void cxTreeDestroy(CxTree *tree) {
-    tree->cl->destructor(tree);
-}
-
-/**
  * Inserts data into the tree.
  *
  * \remark For this function to work, the tree needs specified search and
@@ -1199,8 +1176,9 @@
  * A function that is invoked when a node needs to be re-linked to a new parent.
  *
  * When a node is re-linked, sometimes the contents need to be updated.
- * This callback is invoked by #cxTreeRemove() so that those updates can be
- * applied when re-linking the children of the removed node.
+ * This callback is invoked by #cxTreeRemoveNode() and #cxTreeDestroyNode()
+ * so that those updates can be applied when re-linking the children of the
+ * removed node.
  *
  * @param node the affected node
  * @param old_parent the old parent of the node
@@ -1227,7 +1205,7 @@
  * @return zero on success, non-zero if \p node is the root node of the tree
  */
 __attribute__((__nonnull__(1,2)))
-int cxTreeRemove(
+int cxTreeRemoveNode(
         CxTree *tree,
         void *node,
         cx_tree_relink_func relink_func
@@ -1247,6 +1225,99 @@
 __attribute__((__nonnull__))
 void cxTreeRemoveSubtree(CxTree *tree, void *node);
 
+/**
+ * Destroys a node and re-links its children to its former parent.
+ *
+ * If the node is not part of the tree, the behavior is undefined.
+ *
+ * It is guaranteed that the simple destructor is invoked before
+ * the advanced destructor.
+ *
+ * \attention This function will not free the memory of the node with the
+ * tree's allocator, because that is usually done by the advanced destructor
+ * and would therefore result in a double-free.
+ *
+ * @param tree the tree
+ * @param node the node to destroy (must not be the root node)
+ * @param relink_func optional callback to update the content of each re-linked
+ * node
+ * @return zero on success, non-zero if \p node is the root node of the tree
+ */
+__attribute__((__nonnull__(1,2)))
+int cxTreeDestroyNode(
+        CxTree *tree,
+        void *node,
+        cx_tree_relink_func relink_func
+);
+
+/**
+ * Destroys a node and it's subtree.
+ *
+ * It is guaranteed that the simple destructor is invoked before
+ * the advanced destructor, starting with the leaf nodes of the subtree.
+ *
+ * When this function is invoked on the root node of the tree, it destroys the
+ * tree contents, but - in contrast to #cxTreeDestroy() - not the tree
+ * structure, leaving an empty tree behind.
+ *
+ * \note The destructor function, if any, will \em not be invoked. That means
+ * you will need to free the removed subtree by yourself, eventually.
+ *
+ * \attention This function will not free the memory of the nodes with the
+ * tree's allocator, because that is usually done by the advanced destructor
+ * and would therefore result in a double-free.
+ *
+ * @param tree the tree
+ * @param node the node to remove
+ * @see cxTreeDestroy()
+ */
+__attribute__((__nonnull__))
+void cxTreeDestroySubtree(CxTree *tree, void *node);
+
+
+/**
+ * Destroys the tree contents.
+ *
+ * It is guaranteed that the simple destructor is invoked before
+ * the advanced destructor, starting with the leaf nodes of the subtree.
+ *
+ * This is a convenience macro for invoking #cxTreeDestroySubtree() on the
+ * root node of the tree.
+ *
+ * \attention Be careful when calling this function when no destructor function
+ * is registered that actually frees the memory of nodes. In that case you will
+ * need a reference to the (former) root node of the tree somewhere or
+ * otherwise you will be leaking memory.
+ *
+ * @param tree the tree
+ * @see cxTreeDestroySubtree()
+ */
+#define cxTreeClear(tree) cxTreeDestroySubtree(tree, tree->root)
+
+/**
+ * Destroys the tree structure.
+ *
+ * The destructor functions are invoked for each node, starting with the leaf
+ * nodes.
+ * It is guaranteed that for each node the simple destructor is invoked before
+ * the advanced destructor.
+ *
+ * \attention This function will only invoke the destructor functions
+ * on the nodes.
+ * It will NOT additionally free the nodes with the tree's allocator, because
+ * that would cause a double-free in most scenarios where the advanced
+ * destructor is already freeing the memory.
+ *
+ * @param tree the tree to destroy
+ */
+__attribute__((__nonnull__))
+static inline void cxTreeDestroy(CxTree *tree) {
+    if (tree->root != NULL) {
+        cxTreeDestroySubtree(tree, tree->root);
+    }
+    cxFree(tree->allocator, tree);
+}
+
 #ifdef __cplusplus
 } // extern "C"
 #endif

--- a/src/tree.c	Sun Oct 06 12:40:44 2024 +0200
+++ b/src/tree.c	Sun Oct 06 13:37:05 2024 +0200
@@ -681,23 +681,6 @@
                             loc_prev, loc_next);
 }
 
-static void cx_tree_default_destructor(CxTree *tree) {
-    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);
-}
-
 static CxTreeIterator cx_tree_default_iterator(
         CxTree *tree,
         bool visit_on_exit
@@ -785,7 +768,6 @@
 }
 
 static cx_tree_class cx_tree_default_class = {
-        cx_tree_default_destructor,
         cx_tree_default_insert_element,
         cx_tree_default_insert_many,
         cx_tree_default_find,
@@ -901,7 +883,7 @@
     return visitor.depth;
 }
 
-int cxTreeRemove(
+int cxTreeRemoveNode(
         CxTree *tree,
         void *node,
         cx_tree_relink_func relink_func
@@ -957,3 +939,44 @@
     cx_tree_unlink(node, cx_tree_node_layout(tree));
     tree->size -= subtree_size;
 }
+
+int cxTreeDestroyNode(
+        CxTree *tree,
+        void *node,
+        cx_tree_relink_func relink_func
+) {
+    int result = cxTreeRemoveNode(tree, node, relink_func);
+    if (result == 0) {
+        if (tree->simple_destructor) {
+            tree->simple_destructor(node);
+        }
+        if (tree->advanced_destructor) {
+            tree->advanced_destructor(tree->destructor_data, node);
+        }
+        return 0;
+    } else {
+        return result;
+    }
+}
+
+void cxTreeDestroySubtree(CxTree *tree, void *node) {
+    cx_tree_unlink(node, cx_tree_node_layout(tree));
+    CxTreeIterator iter = cx_tree_iterator(
+            node, true,
+            tree->loc_children, tree->loc_next
+    );
+    cx_foreach(void *, child, iter) {
+        if (iter.exiting) {
+            if (tree->simple_destructor) {
+                tree->simple_destructor(child);
+            }
+            if (tree->advanced_destructor) {
+                tree->advanced_destructor(tree->destructor_data, child);
+            }
+        }
+    }
+    tree->size -= iter.counter;
+    if (node == tree->root) {
+        tree->root = NULL;
+    }
+}

--- a/tests/test_tree.c	Sun Oct 06 12:40:44 2024 +0200
+++ b/tests/test_tree.c	Sun Oct 06 13:37:05 2024 +0200
@@ -1792,7 +1792,7 @@
         CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/foo/bar/"));
         CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/bar/"));
 
-        CX_TEST_ASSERT(0 == cxTreeRemove(tree, usr, test_tree_remove_node_relink_mock));
+        CX_TEST_ASSERT(0 == cxTreeRemoveNode(tree, usr, test_tree_remove_node_relink_mock));
         CX_TEST_ASSERT(tree->size == 5);
         CX_TEST_ASSERT(usr->parent == NULL);
         CX_TEST_ASSERT(usr->children == NULL);
@@ -1825,6 +1825,83 @@
     cx_testing_allocator_destroy(&talloc);
 }
 
+CX_TEST(test_tree_high_add_find_destroy_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/";
+        tree_node_file *usr = cxTreeFind(tree, "/usr/");
+        cxTreeAddChildNode(tree, usr, share);
+        CX_TEST_ASSERT(tree->size == 8);
+
+        cxTreeDestroySubtree(tree, foo);
+        CX_TEST_ASSERT(tree->size == 6);
+        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(0 == cxTreeDestroyNode(tree, usr, test_tree_remove_node_relink_mock));
+        CX_TEST_ASSERT(tree->size == 5);
+        CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/"));
+        CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/lib/"));
+        CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/share/"));
+        tree_node_file *relinked_share = cxTreeFind(tree, "/share/");
+        tree_node_file *relinked_lib = cxTreeFind(tree, "/lib/");
+        CX_TEST_ASSERT(relinked_share != NULL);
+        CX_TEST_ASSERT(relinked_share->parent == tree->root);
+        CX_TEST_ASSERT(relinked_lib != NULL);
+        CX_TEST_ASSERT(relinked_lib->parent == tree->root);
+        CX_TEST_ASSERT(NULL != cxTreeFind(tree, "/home/"));
+
+
+        cxTreeDestroy(tree);
+        // all memory should be free when using destroy instead of remove
+        CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
+    }
+    cx_testing_allocator_destroy(&talloc);
+}
+
 CX_TEST(test_tree_high_remove_root) {
     CxTestingAllocator talloc;
     cx_testing_allocator_init(&talloc);
@@ -1847,7 +1924,7 @@
         };
         cxTreeInsertArray(tree, paths, sizeof(const char*), 6);
         void *root = tree->root;
-        CX_TEST_ASSERT(0 != cxTreeRemove(tree, root, NULL));
+        CX_TEST_ASSERT(0 != cxTreeRemoveNode(tree, root, NULL));
         CX_TEST_ASSERT(tree->root == root);
         CX_TEST_ASSERT(tree->size == 6);
         cxTreeRemoveSubtree(tree, root);
@@ -1931,6 +2008,7 @@
     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);
+    cx_test_register(suite, test_tree_high_add_find_destroy_nodes);
     cx_test_register(suite, test_tree_high_remove_root);
     cx_test_register(suite, test_tree_high_simple_destructor);