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