# HG changeset patch # User Mike Becker # Date 1728214625 -7200 # Node ID 72db8e42b95e3212cc9dde8cbb02a89c1086e272 # Parent 9533fc293aea39d6b3f141a16b84e7a1552d5db3 implement cxTreeDestroyNode and cxTreeDestroySubtree - resolves #438 diff -r 9533fc293aea -r 72db8e42b95e src/cx/tree.h --- 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 diff -r 9533fc293aea -r 72db8e42b95e src/tree.c --- 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; + } +} diff -r 9533fc293aea -r 72db8e42b95e tests/test_tree.c --- 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);