# HG changeset patch # User Mike Becker # Date 1727969961 -7200 # Node ID 39aa4f106a7198bbf7472c01b65225b8deb97749 # Parent cdc49211d87fc5e0e12d7c623cf95a8f7c201584 complete implementation of remaining high level tree functions relates to #166 diff -r cdc49211d87f -r 39aa4f106a71 src/cx/tree.h --- a/src/cx/tree.h Thu Oct 03 16:31:09 2024 +0200 +++ b/src/cx/tree.h Thu Oct 03 17:39:21 2024 +0200 @@ -436,7 +436,6 @@ * @return the new tree iterator * @see cxTreeIteratorDispose() */ -__attribute__((__nonnull__)) CxTreeIterator cx_tree_iterator( void *root, bool visit_on_exit, @@ -462,7 +461,6 @@ * @return the new tree visitor * @see cxTreeVisitorDispose() */ -__attribute__((__nonnull__)) CxTreeVisitor cx_tree_visitor( void *root, ptrdiff_t loc_children, @@ -741,6 +739,11 @@ cx_tree_search_func search; /** + * A function to compare a node with data. + */ + cx_tree_search_data_func search_data; + + /** * The number of currently stored elements. */ size_t size; @@ -878,6 +881,7 @@ * @param allocator the allocator that shall be used * @param create_func a function that creates new nodes * @param search_func a function that compares two nodes + * @param search_data_func a function that compares a node with data * @param loc_parent offset in the node struct for the parent pointer * @param loc_children offset in the node struct for the children linked list * @param loc_last_child optional offset in the node struct for the pointer to @@ -893,6 +897,7 @@ const CxAllocator *allocator, cx_tree_node_create_func create_func, cx_tree_search_func search_func, + cx_tree_search_data_func search_data_func, ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child, @@ -913,6 +918,7 @@ * @param allocator the allocator that shall be used * @param create_func a function that creates new nodes * @param search_func a function that compares two nodes + * @param search_data_func a function that compares a node with data * @return the new tree * @see cxTreeCreate() */ @@ -920,12 +926,14 @@ static inline CxTree *cxTreeCreateSimple( const CxAllocator *allocator, cx_tree_node_create_func create_func, - cx_tree_search_func search_func + cx_tree_search_func search_func, + cx_tree_search_data_func search_data_func ) { return cxTreeCreate( allocator, create_func, search_func, + search_data_func, cx_tree_node_base_layout ); } @@ -933,8 +941,7 @@ /** * Creates a new tree structure based on an existing tree. * - * 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. + * The specified \p allocator will be used for creating the tree struct. * * \attention This function will create an incompletely defined tree structure * where neither the create function, the search function, nor a destructor @@ -953,6 +960,7 @@ */ __attribute__((__nonnull__, __warn_unused_result__)) CxTree *cxTreeCreateWrapped( + const CxAllocator *allocator, void *root, ptrdiff_t loc_parent, ptrdiff_t loc_children, @@ -1045,7 +1053,7 @@ /** * Searches the data in the specified tree. * - * \remark For this function to work, the tree needs a specified search + * \remark For this function to work, the tree needs a specified \c search_data * function, which might not be available wrapped trees * (see #cxTreeCreateWrapped()). * @@ -1067,7 +1075,7 @@ * \note When \p subtree_root is not part of the \p tree, the behavior is * undefined. * - * \remark For this function to work, the tree needs a specified search + * \remark For this function to work, the tree needs a specified \c search_data * function, which might not be the case for wrapped trees * (see #cxTreeCreateWrapped()). * @@ -1106,6 +1114,15 @@ size_t cxTreeSubtreeDepth(CxTree *tree, void *subtree_root); /** + * Determines the depth of the entire tree. + * + * @param tree the tree + * @return the tree depth, counting the root as one + */ +__attribute__((__nonnull__)) +size_t cxTreeDepth(CxTree *tree); + +/** * Creates a depth-first iterator for the specified tree. * * @param tree the tree to iterate @@ -1179,22 +1196,18 @@ ); /** - * Removes a node from the tree. + * Removes a node and it's subtree from the tree. * * If the node is not part of the tree, the behavior is undefined. * - * \note The destructor function, if any, will \em not be invoked. + * \note The destructor function, if any, will \em not be invoked. That means + * you will need to free the removed subtree by yourself, eventually. * * @param tree the tree * @param node the node to remove */ __attribute__((__nonnull__)) -static inline void cxTreeRemove( - CxTree *tree, - void *node) { - cx_tree_unlink(node, cx_tree_node_layout(tree)); - tree->size--; -} +void cxTreeRemove(CxTree *tree, void *node); #ifdef __cplusplus } // extern "C" diff -r cdc49211d87f -r 39aa4f106a71 src/tree.c --- a/src/tree.c Thu Oct 03 16:31:09 2024 +0200 +++ b/src/tree.c Thu Oct 03 17:39:21 2024 +0200 @@ -241,6 +241,8 @@ struct cx_tree_iterator_s *iter = it; ptrdiff_t const loc_next = iter->loc_next; ptrdiff_t const loc_children = iter->loc_children; + // protect us from misuse + if (!iter->base.valid(iter)) return; void *children; @@ -326,17 +328,8 @@ iter.loc_next = loc_next; iter.visit_on_exit = visit_on_exit; - // allocate stack - iter.stack_capacity = 16; - iter.stack = malloc(sizeof(void *) * 16); - iter.depth = 0; - - // visit the root node - iter.node = root; + // initialize members iter.node_next = NULL; - iter.counter = 1; - iter.depth = 1; - iter.stack[0] = root; iter.exiting = false; iter.skip = false; @@ -348,6 +341,21 @@ iter.base.next = cx_tree_iter_next; iter.base.current = cx_tree_iter_current; + // visit the root node + iter.node = root; + if (root != NULL) { + iter.stack_capacity = 16; + iter.stack = malloc(sizeof(void *) * 16); + iter.stack[0] = root; + iter.counter = 1; + iter.depth = 1; + } else { + iter.stack_capacity = 0; + iter.stack = NULL; + iter.counter = 0; + iter.depth = 0; + } + return iter; } @@ -379,6 +387,9 @@ static void cx_tree_visitor_next(void *it) { struct cx_tree_visitor_s *iter = it; + // protect us from misuse + if (!iter->base.valid(iter)) return; + ptrdiff_t const loc_next = iter->loc_next; ptrdiff_t const loc_children = iter->loc_children; @@ -438,13 +449,7 @@ iter.loc_children = loc_children; iter.loc_next = loc_next; - // allocate stack - iter.depth = 0; - - // visit the root node - iter.node = root; - iter.counter = 1; - iter.depth = 1; + // initialize members iter.skip = false; iter.queue_next = NULL; iter.queue_last = NULL; @@ -457,6 +462,16 @@ iter.base.next = cx_tree_visitor_next; iter.base.current = cx_tree_visitor_current; + // visit the root node + iter.node = root; + if (root != NULL) { + iter.counter = 1; + iter.depth = 1; + } else { + iter.counter = 0; + iter.depth = 0; + } + return iter; } @@ -747,11 +762,33 @@ return ins; } +static void *cx_tree_default_find( + CxTree *tree, + const void *subtree, + const void *data +) { + if (tree->root == NULL) return NULL; + + void *found; + if (0 == cx_tree_search_data( + subtree, + data, + tree->search_data, + &found, + tree->loc_children, + tree->loc_next + )) { + return found; + } else { + return NULL; + } +} + static cx_tree_class cx_tree_default_class = { cx_tree_default_destructor, cx_tree_default_insert_element, cx_tree_default_insert_many, - NULL, + cx_tree_default_find, cx_tree_default_iterator, cx_tree_default_visitor }; @@ -760,6 +797,7 @@ const CxAllocator *allocator, cx_tree_node_create_func create_func, cx_tree_search_func search_func, + cx_tree_search_data_func search_data_func, ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child, @@ -773,6 +811,7 @@ tree->allocator = allocator; tree->node_create = create_func; tree->search = search_func; + tree->search_data = search_data_func; tree->advanced_destructor = (cx_destructor_func2) cxFree; tree->destructor_data = (void *) allocator; tree->loc_parent = loc_parent; @@ -787,6 +826,7 @@ } CxTree *cxTreeCreateWrapped( + const CxAllocator *allocator, void *root, ptrdiff_t loc_parent, ptrdiff_t loc_children, @@ -794,14 +834,16 @@ ptrdiff_t loc_prev, ptrdiff_t loc_next ) { - CxTree *tree = malloc(sizeof(CxTree)); + CxTree *tree = cxMalloc(allocator, sizeof(CxTree)); if (tree == NULL) return NULL; tree->cl = &cx_tree_default_class; // set the allocator anyway, just in case... - tree->allocator = cxDefaultAllocator; + tree->allocator = allocator; tree->node_create = NULL; tree->search = NULL; + tree->search_data = NULL; + tree->simple_destructor = NULL; tree->advanced_destructor = NULL; tree->destructor_data = NULL; tree->loc_parent = loc_parent; @@ -849,3 +891,17 @@ } return visitor.depth; } + +size_t cxTreeDepth(CxTree *tree) { + CxTreeVisitor visitor = tree->cl->visitor(tree); + while (cxIteratorValid(visitor)) { + cxIteratorNext(visitor); + } + return visitor.depth; +} + +void cxTreeRemove(CxTree *tree, void *node) { + size_t subtree_size = cxTreeSubtreeSize(tree, node); + cx_tree_unlink(node, cx_tree_node_layout(tree)); + tree->size -= subtree_size; +} diff -r cdc49211d87f -r 39aa4f106a71 tests/test_tree.c --- a/tests/test_tree.c Thu Oct 03 16:31:09 2024 +0200 +++ b/tests/test_tree.c Thu Oct 03 17:39:21 2024 +0200 @@ -94,6 +94,12 @@ } } +static int tree_node_file_search_data(const void *l, const void *d) { + tree_node_file r; + r.path = d; + return tree_node_file_search(l, &r); +} + #define tree_node_layout \ offsetof(tree_node, parent), offsetof(tree_node, children), -1, \ offsetof(tree_node, prev), offsetof(tree_node, next) @@ -1540,12 +1546,14 @@ &talloc.base, tree_node_file_create_hl, tree_node_file_search, + tree_node_file_search_data, 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_hl); CX_TEST_ASSERT(tree->search == tree_node_file_search); + CX_TEST_ASSERT(tree->search_data == tree_node_file_search_data); CX_TEST_ASSERT(tree->size == 0); CX_TEST_ASSERT(tree->simple_destructor == NULL); CX_TEST_ASSERT(tree->advanced_destructor == (cx_destructor_func2) cxFree); @@ -1571,12 +1579,14 @@ CxTree *tree = cxTreeCreateSimple( cxDefaultAllocator, tree_node_file_create_hl, - tree_node_file_search + tree_node_file_search, + tree_node_file_search_data ); CX_TEST_ASSERT(tree->cl != NULL); CX_TEST_ASSERT(tree->allocator == cxDefaultAllocator); CX_TEST_ASSERT(tree->node_create == tree_node_file_create_hl); CX_TEST_ASSERT(tree->search == tree_node_file_search); + CX_TEST_ASSERT(tree->search_data == tree_node_file_search_data); CX_TEST_ASSERT(tree->size == 0); CX_TEST_ASSERT(tree->simple_destructor == NULL); CX_TEST_ASSERT(tree->advanced_destructor == (cx_destructor_func2) cxFree); @@ -1597,11 +1607,12 @@ 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); + CxTree *tree = cxTreeCreateWrapped(cxDefaultAllocator, &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->search_data == NULL); CX_TEST_ASSERT(tree->root == &root); CX_TEST_ASSERT(tree->size == 4); CX_TEST_ASSERT(tree->simple_destructor == NULL); @@ -1616,17 +1627,28 @@ } } -CX_TEST(test_tree_high_subtree_depth) { +CX_TEST(test_tree_high_tree_depth) { 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); - CxTree *tree = cxTreeCreateWrapped(&root, tree_node_layout); + CxTree *tree = cxTreeCreateWrapped(cxDefaultAllocator, &root, tree_node_layout); CX_TEST_DO { + CX_TEST_ASSERT(cxTreeDepth(tree) == 3); CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &root) == 3); CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child1) == 2); CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child2) == 1); CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child3) == 1); + + CxTree *empty = cxTreeCreate( + cxDefaultAllocator, + tree_node_file_create_hl, + tree_node_file_search, + tree_node_file_search_data, + tree_node_file_layout + ); + CX_TEST_ASSERT(cxTreeDepth(empty) == 0); + cxTreeDestroy(empty); } cxTreeDestroy(tree); } @@ -1638,7 +1660,8 @@ CX_TEST_DO { CxTree *tree = cxTreeCreate( - alloc, tree_node_file_create_hl, tree_node_file_search, + alloc, tree_node_file_create_hl, + tree_node_file_search, tree_node_file_search_data, tree_node_file_layout ); @@ -1670,7 +1693,8 @@ CX_TEST_DO { CxTree *tree = cxTreeCreate( - alloc, tree_node_file_create_hl, tree_node_file_search, + alloc, tree_node_file_create_hl, + tree_node_file_search, tree_node_file_search_data, tree_node_file_layout ); @@ -1695,6 +1719,76 @@ cx_testing_allocator_destroy(&talloc); } +CX_TEST(test_tree_high_add_find_remove_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/"; + cxTreeAddChildNode(tree, cxTreeFind(tree, "/usr/"), share); + CX_TEST_ASSERT(tree->size == 8); + + cxTreeRemove(tree, foo); + 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); + + cxTreeDestroy(tree); + // we are not done yet, because we need to free the removed subtree + CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc)); + + // for this, we use a little trick and wrap the removed subtree + CxTree *foo_tree = cxTreeCreateWrapped(alloc, foo, tree_node_file_layout); + foo_tree->allocator = alloc; + foo_tree->advanced_destructor = (cx_destructor_func2 ) cxFree; + foo_tree->destructor_data = alloc; + cxTreeDestroy(foo_tree); + CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); + } + cx_testing_allocator_destroy(&talloc); +} + CxTestSuite *cx_test_suite_tree_low_level(void) { CxTestSuite *suite = cx_test_suite_new("tree (low level)"); @@ -1737,9 +1831,10 @@ 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); - cx_test_register(suite, test_tree_high_subtree_depth); + cx_test_register(suite, test_tree_high_tree_depth); 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); return suite; }