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; }