Mercurial > hg > ucx / changeset

--- a/src/cx/tree.h	Sat Oct 05 14:42:14 2024 +0200
+++ b/src/cx/tree.h	Sat Oct 05 19:05:47 2024 +0200
@@ -1196,6 +1196,44 @@
 );
 
 /**
+ * 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.
+ *
+ * @param node the affected node
+ * @param old_parent the old parent of the node
+ * @param new_parent the new parent of the node
+ */
+typedef void (*cx_tree_relink_func)(
+        void *node,
+        const void *old_parent,
+        const void *new_parent
+);
+
+/**
+ * Removes a node and re-links its children to its former parent.
+ *
+ * If the node is not part of the tree, the behavior is undefined.
+ *
+ * \note The destructor function, if any, will \em not be invoked. That means
+ * you will need to free the removed node by yourself, eventually.
+ *
+ * @param tree the tree
+ * @param node the node to remove (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 cxTreeRemove(
+        CxTree *tree,
+        void *node,
+        cx_tree_relink_func relink_func
+);
+
+/**
  * Removes a node and it's subtree from the tree.
  *
  * If the node is not part of the tree, the behavior is undefined.

--- a/src/tree.c	Sat Oct 05 14:42:14 2024 +0200
+++ b/src/tree.c	Sat Oct 05 19:05:47 2024 +0200
@@ -900,10 +900,48 @@
     return visitor.depth;
 }
 
-int cxTreeRemove(CxTree *tree, void *node) {
+int cxTreeRemove(
+        CxTree *tree,
+        void *node,
+        cx_tree_relink_func relink_func
+) {
     if (node == tree->root) return 1;
 
+    // determine the new parent
+    ptrdiff_t loc_parent = tree->loc_parent;
+    void *new_parent = tree_parent(node);
 
+    // first, unlink from the parent
+    cx_tree_unlink(node, cx_tree_node_layout(tree));
+
+    // then relink each child
+    ptrdiff_t loc_children = tree->loc_children;
+    ptrdiff_t loc_next = tree->loc_next;
+    void *child = tree_children(node);
+    while (child != NULL) {
+        // forcibly set the parent to NULL - we do not use the unlink function
+        // because that would unnecessarily modify the children linked list
+        tree_parent(child) = NULL;
+
+        // update contents, if required
+        if (relink_func != NULL) {
+            relink_func(child, node, new_parent);
+        }
+
+        // link to new parent
+        cx_tree_link(new_parent, child, cx_tree_node_layout(tree));
+
+        // proceed to next child
+        child = tree_next(child);
+    }
+
+    // clear the linked list of the removed node
+    tree_children(node) = NULL;
+    ptrdiff_t loc_last_child = tree->loc_last_child;
+    if (loc_last_child >= 0) tree_last_child(node) = NULL;
+
+    // the tree now has one member less
+    tree->size--;
 
     return 0;
 }

--- a/tests/test_tree.c	Sat Oct 05 14:42:14 2024 +0200
+++ b/tests/test_tree.c	Sat Oct 05 19:05:47 2024 +0200
@@ -1719,6 +1719,20 @@
     cx_testing_allocator_destroy(&talloc);
 }
 
+static void test_tree_remove_node_relink_mock(
+        void *node,
+        __attribute__((__unused__)) const void *oldp,
+        __attribute__((__unused__)) const void *newp
+) {
+    tree_node_file * n = node;
+    // this function fakes the relink logic in below test
+    if (strcmp(n->path, "/usr/share/") == 0) {
+        n->path = "/share/";
+    } else if (strcmp(n->path, "/usr/lib/") == 0) {
+        n->path = "/lib/";
+    }
+}
+
 CX_TEST(test_tree_high_add_find_remove_nodes) {
     CxTestingAllocator talloc;
     cx_testing_allocator_init(&talloc);
@@ -1765,20 +1779,41 @@
 
         tree_node_file *share = cxCalloc(alloc, 1, sizeof(tree_node_file));
         share->path = "/usr/share/";
-        cxTreeAddChildNode(tree, cxTreeFind(tree, "/usr/"), share);
+        tree_node_file *usr = cxTreeFind(tree, "/usr/");
+        cxTreeAddChildNode(tree, usr, share);
         CX_TEST_ASSERT(tree->size == 8);
 
         cxTreeRemoveSubtree(tree, foo);
+        CX_TEST_ASSERT(tree->size == 6);
+        CX_TEST_ASSERT(foo->children == bar);
+        CX_TEST_ASSERT(foo->last_child == bar);
         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);
+
+        CX_TEST_ASSERT(0 == cxTreeRemove(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);
+        CX_TEST_ASSERT(usr->last_child == NULL);
+        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);
-        // we are not done yet, because we need to free the removed subtree
+        // we are not done yet, because we need to free the removed stuff
         CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc));
 
-        // for this, we use a little trick and wrap the removed subtree
+        cxFree(alloc, usr);
+        // for the subtree, we use a little trick and wrap it in a new tree
         CxTree *foo_tree = cxTreeCreateWrapped(alloc, foo, tree_node_file_layout);
         foo_tree->allocator = alloc;
         foo_tree->advanced_destructor = (cx_destructor_func2 ) cxFree;
@@ -1811,6 +1846,9 @@
         };
         cxTreeInsertArray(tree, paths, sizeof(const char*), 6);
         void *root = tree->root;
+        CX_TEST_ASSERT(0 != cxTreeRemove(tree, root, NULL));
+        CX_TEST_ASSERT(tree->root == root);
+        CX_TEST_ASSERT(tree->size == 6);
         cxTreeRemoveSubtree(tree, root);
         CX_TEST_ASSERT(tree->size == 0);
         CX_TEST_ASSERT(tree->root == NULL);