# HG changeset patch # User Mike Becker # Date 1728147947 -7200 # Node ID f4e00bb3f3b2dc88ce8427bbd5a8aafc1a105804 # Parent f49f8a7060aa4c5d8fd1df1d31310cbfc1d0f9f5 implement cxTreeRemove() with re-link function fixes #437 diff -r f49f8a7060aa -r f4e00bb3f3b2 src/cx/tree.h --- 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. diff -r f49f8a7060aa -r f4e00bb3f3b2 src/tree.c --- 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; } diff -r f49f8a7060aa -r f4e00bb3f3b2 tests/test_tree.c --- 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);