--- a/tests/test_tree.c Tue Aug 20 13:53:18 2024 +0200
+++ b/tests/test_tree.c Tue Aug 20 18:01:03 2024 +0200
@@ -60,37 +60,29 @@
static void *create_tree_node_file(
void const *dptr,
- void const *nptr,
void *allocator) {
if (allocator == NULL) allocator = cxDefaultAllocator;
- char const *data = dptr;
- tree_node_file const *existing = nptr;
-
- if (existing != NULL && strcmp(existing->path, data) == 0) {
- return (void *) existing;
- } else {
- tree_node_file *node = cxMalloc(allocator, sizeof(tree_node_file));
-
- node->path = data;
+ tree_node_file *node = cxMalloc(allocator, sizeof(tree_node_file));
+ node->path = dptr;
- // intentionally write garbage into the pointers, it's part of the test
- node->parent = (void *) 0xf00ba1;
- node->next = (void *) 0xf00ba2;
- node->prev = (void *) 0xf00ba3;
- node->children = (void *) 0xf00ba4;
- node->last_child = (void *) 0xf00ba5;
+ // intentionally write garbage into the pointers, it's part of the test
+ node->parent = (void *) 0xf00ba1;
+ node->next = (void *) 0xf00ba2;
+ node->prev = (void *) 0xf00ba3;
+ node->children = (void *) 0xf00ba4;
+ node->last_child = (void *) 0xf00ba5;
- return node;
- }
+ return node;
}
-static int tree_node_file_search(void const *nptr, void const *data) {
- tree_node_file const *node = nptr;
- size_t len1 = strlen(node->path);
- size_t len2 = strlen(data);
+static int tree_node_file_search(void const *l, void const *r) {
+ tree_node_file const *left = l;
+ tree_node_file const *right = r;
+ size_t len1 = strlen(left->path);
+ size_t len2 = strlen(right->path);
if (len1 <= len2) {
- if (memcmp(node->path, data, len1) == 0) {
+ if (memcmp(left->path, right->path, len1) == 0) {
return (int) (len2 - len1);
} else {
return -1;
@@ -429,38 +421,38 @@
CX_TEST_DO {
for (unsigned i = 0 ; i <= 10 ; i++) {
s = testdata[i];
- r = cx_tree_search(&root, &s, test_tree_search_function,
+ r = cx_tree_search_data(&root, &s, test_tree_search_function,
(void **) &n, tree_children(tree_node));
CX_TEST_ASSERT(r == 0);
CX_TEST_ASSERT(n == testnodes[i]);
}
s = -5;
- r = cx_tree_search(&root, &s, test_tree_search_function,
+ r = cx_tree_search_data(&root, &s, test_tree_search_function,
(void **) &n, tree_children(tree_node));
CX_TEST_ASSERT(r < 0);
CX_TEST_ASSERT(n == NULL);
s = 26;
- r = cx_tree_search(&root, &s, test_tree_search_function,
+ r = cx_tree_search_data(&root, &s, test_tree_search_function,
(void **) &n, tree_children(tree_node));
CX_TEST_ASSERT(r > 0);
CX_TEST_ASSERT(n == &ba);
s = 35;
- r = cx_tree_search(&root, &s, test_tree_search_function,
+ r = cx_tree_search_data(&root, &s, test_tree_search_function,
(void **) &n, tree_children(tree_node));
CX_TEST_ASSERT(r > 0);
CX_TEST_ASSERT(n == &cb);
s = 38;
- r = cx_tree_search(&root, &s, test_tree_search_function,
+ r = cx_tree_search_data(&root, &s, test_tree_search_function,
(void **) &n, tree_children(tree_node));
CX_TEST_ASSERT(r > 0);
CX_TEST_ASSERT(n == &cba);
s = 42;
- r = cx_tree_search(&root, &s, test_tree_search_function,
+ r = cx_tree_search_data(&root, &s, test_tree_search_function,
(void **) &n, tree_children(tree_node));
CX_TEST_ASSERT(r > 0);
CX_TEST_ASSERT(n == &cc);
@@ -1064,60 +1056,58 @@
cx_tree_link(&usr, &lib, tree_node_file_layout);
CX_TEST_DO {
- void *newroot = &root;
-
- tree_node_file *foo = cx_tree_add(
+ tree_node_file *foo;
+ int result;
+ result = cx_tree_add(
"/home/foo/",
tree_node_file_search,
create_tree_node_file, alloc,
- &newroot, tree_node_file_layout
+ (void **) &foo, &root,
+ tree_node_file_layout
);
- CX_TEST_ASSERT(newroot == &root);
- tree_node_file *bar = cx_tree_add(
- "/home/foo/bar/",
+ CX_TEST_ASSERT(result == 0);
+ CX_TEST_ASSERT(foo != NULL);
+ char const *bar_path = "/home/foo/bar/";
+ void *failed;
+ size_t added = cx_tree_add_array(
+ bar_path, 1, sizeof(char const *),
tree_node_file_search,
create_tree_node_file, alloc,
- &newroot, tree_node_file_layout
+ &failed, &root,
+ tree_node_file_layout
);
- CX_TEST_ASSERT(newroot == &root);
-
+ CX_TEST_ASSERT(added == 1);
+ CX_TEST_ASSERT(failed == NULL);
+ tree_node_file *bar = foo->children;
+ CX_TEST_ASSERT(bar != NULL);
CX_TEST_ASSERT(bar->parent == foo);
+ CX_TEST_ASSERT(bar->path == bar_path);
CX_TEST_ASSERT(foo->parent == &home);
- CX_TEST_ASSERT(talloc.alloc_total == 2);
+ tree_node_file *new_node;
+ result = cx_tree_add(
+ "newroot",
+ tree_node_file_search,
+ create_tree_node_file, alloc,
+ (void **) &new_node, &root,
+ tree_node_file_layout
+ );
+ CX_TEST_ASSERT(0 != result);
+ CX_TEST_ASSERT(NULL != new_node);
+ CX_TEST_ASSERT(new_node->children == NULL);
+ CX_TEST_ASSERT(new_node->parent == NULL);
- cxFree(&talloc.base, foo);
- cxFree(&talloc.base, bar);
+ CX_TEST_ASSERT(talloc.alloc_total == 3);
+
+ cxFree(alloc, foo);
+ cxFree(alloc, bar);
+ cxFree(alloc, new_node);
CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
}
cx_testing_allocator_destroy(&talloc);
}
-CX_TEST(test_tree_add_one_to_empty_tree) {
- tree_node_file *node = NULL;
- CX_TEST_DO {
- tree_node_file *root = NULL;
- char const *data = "/home/foo/bar/";
-
- node = cx_tree_add(
- data,
- tree_node_file_search,
- create_tree_node_file, NULL,
- (void **) &root, tree_node_file_layout
- );
-
- CX_TEST_ASSERT(root != NULL);
- CX_TEST_ASSERT(root->path == data);
- CX_TEST_ASSERT(root->next == NULL);
- CX_TEST_ASSERT(root->prev == NULL);
- CX_TEST_ASSERT(root->children == NULL);
- CX_TEST_ASSERT(root->last_child == NULL);
- CX_TEST_ASSERT(root->parent == NULL);
- }
- free(node);
-}
-
CX_TEST(test_tree_add_one_existing) {
CxTestingAllocator talloc;
cx_testing_allocator_init(&talloc);
@@ -1136,28 +1126,109 @@
cx_tree_link(&usr, &lib, tree_node_file_layout);
CX_TEST_DO {
- void *newroot = &root;
-
tree_node_file *node;
- node = cx_tree_add(
+ int result = cx_tree_add(
"/usr/lib/",
tree_node_file_search,
create_tree_node_file, alloc,
- &newroot, tree_node_file_layout
+ (void **) &node, &root,
+ tree_node_file_layout
+ );
+ CX_TEST_ASSERT(result == 0);
+ CX_TEST_ASSERT(node != &lib);
+ CX_TEST_ASSERT(node->prev == &lib);
+ CX_TEST_ASSERT(lib.next == node);
+ CX_TEST_ASSERT(node->parent == &usr);
+ CX_TEST_ASSERT(talloc.alloc_total == 1);
+ cxFree(alloc, node);
+ CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
+ }
+ cx_testing_allocator_destroy(&talloc);
+}
+
+CX_TEST(test_tree_add_one_no_match) {
+ tree_node_file root = {0};
+ root.path = "/mnt/";
+
+ CX_TEST_DO {
+ tree_node_file *node = NULL;
+ int result = cx_tree_add(
+ "/usr/lib/",
+ tree_node_file_search,
+ create_tree_node_file, NULL,
+ (void **) &node, &root,
+ tree_node_file_layout
);
- CX_TEST_ASSERT(newroot == &root);
- CX_TEST_ASSERT(node == &lib);
+ CX_TEST_ASSERT(result != 0);
+ CX_TEST_ASSERT(node != NULL);
+ CX_TEST_ASSERT(node->parent == NULL);
+ CX_TEST_ASSERT(node->children == NULL);
+ free(node);
+ node = NULL;
+ size_t added = cx_tree_add_array(
+ "/", 1, sizeof(char const *),
+ tree_node_file_search,
+ create_tree_node_file, NULL,
+ (void **) &node, &root,
+ tree_node_file_layout
+ );
+ CX_TEST_ASSERT(added == 0);
+ CX_TEST_ASSERT(node != NULL);
+ CX_TEST_ASSERT(node->parent == NULL);
+ CX_TEST_ASSERT(node->children == NULL);
+ free(node);
+ }
+}
- node = cx_tree_add(
- "/home/",
+CX_TEST(test_tree_add_duplicate_root) {
+ tree_node_file root = {0};
+ root.path = "/";
+ CX_TEST_DO {
+ tree_node_file *node;
+ int result = cx_tree_add(
+ "/",
+ tree_node_file_search,
+ create_tree_node_file, NULL,
+ (void **) &node, &root,
+ tree_node_file_layout
+ );
+ CX_TEST_ASSERT(result == 0);
+ CX_TEST_ASSERT(root.children == node);
+ CX_TEST_ASSERT(node->parent == &root);
+ }
+}
+
+CX_TEST(test_tree_add_zero) {
+ CxTestingAllocator talloc;
+ cx_testing_allocator_init(&talloc);
+ CxAllocator *alloc = &talloc.base;
+
+ tree_node_file root = {0};
+ root.path = "/";
+ CX_TEST_DO {
+ void *failed;
+
+ size_t processed = cx_tree_add_array(
+ (void *) 0xc0ffee, 0, sizeof(void *),
tree_node_file_search,
create_tree_node_file, alloc,
- &newroot, tree_node_file_layout
+ &failed, &root, tree_node_file_layout
);
- CX_TEST_ASSERT(newroot == &root);
- CX_TEST_ASSERT(node == &home);
+ CX_TEST_ASSERT(failed == NULL);
+ CX_TEST_ASSERT(processed == 0);
+ CX_TEST_ASSERT(talloc.alloc_total == 0);
+ CxIterator iter = cxIterator(NULL, sizeof(void *), 0);
+ processed = cx_tree_add_iter(
+ cxIteratorRef(iter),
+ tree_node_file_search,
+ create_tree_node_file, alloc,
+ &failed, &root, tree_node_file_layout
+ );
+ CX_TEST_ASSERT(processed == 0);
+ CX_TEST_ASSERT(failed == NULL);
CX_TEST_ASSERT(talloc.alloc_total == 0);
+
CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
}
cx_testing_allocator_destroy(&talloc);
@@ -1183,7 +1254,7 @@
cx_tree_link(&usr, &lib, tree_node_file_layout);
CX_TEST_DO {
- void *newroot = &root;
+ void *failed;
char const *paths[] = {
"/home/foo/",
@@ -1196,10 +1267,10 @@
paths, 4, sizeof(char const *),
tree_node_file_search,
create_tree_node_file, alloc,
- &newroot, tree_node_file_layout
+ &failed, &root, tree_node_file_layout
);
- CX_TEST_ASSERT(newroot == &root);
+ CX_TEST_ASSERT(failed == NULL);
CX_TEST_ASSERT(processed == 4);
CX_TEST_ASSERT(talloc.alloc_total == 4);
@@ -1219,83 +1290,180 @@
tree_node_file *libfoo = lib.children;
CX_TEST_ASSERT(libfoo != NULL && libfoo->path == paths[3]);
- cxFree(&talloc.base, foo);
- cxFree(&talloc.base, bar);
- cxFree(&talloc.base, lib64);
- cxFree(&talloc.base, libfoo);
+ cxFree(alloc, foo);
+ cxFree(alloc, bar);
+ cxFree(alloc, lib64);
+ cxFree(alloc, libfoo);
+
+ CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
+ }
+ cx_testing_allocator_destroy(&talloc);
+}
+
+CX_TEST(test_tree_add_many_with_dupl_and_no_match) {
+ CxTestingAllocator talloc;
+ cx_testing_allocator_init(&talloc);
+ CxAllocator *alloc = &talloc.base;
+
+ tree_node_file root = {0};
+ root.path = "/mnt/";
+
+ CX_TEST_DO {
+ tree_node_file *failed;
+
+ char const *paths[] = {
+ "/mnt/sdcard/",
+ "/mnt/foo/",
+ "/mnt/sdcard/",
+ "/home/",
+ "/usr/"
+ };
+
+ size_t processed = cx_tree_add_array(
+ paths, 5, sizeof(char const *),
+ tree_node_file_search,
+ create_tree_node_file, alloc,
+ (void **) &failed, &root, tree_node_file_layout
+ );
+
+ CX_TEST_ASSERT(processed == 3);
+ CX_TEST_ASSERT(failed != NULL);
+ CX_TEST_ASSERT(failed->parent == NULL);
+ CX_TEST_ASSERT(failed->children == NULL);
+ CX_TEST_ASSERT(strcmp(failed->path, "/home/") == 0);
+ cxFree(alloc, failed);
+
+ CX_TEST_ASSERT(root.children != root.last_child);
+ CX_TEST_ASSERT(strcmp(root.children->path, "/mnt/sdcard/") == 0);
+ CX_TEST_ASSERT(strcmp(root.last_child->path, "/mnt/sdcard/") == 0);
+ CX_TEST_ASSERT(strcmp(root.children->next->path, "/mnt/foo/") == 0);
+ CX_TEST_ASSERT(strcmp(root.last_child->prev->path, "/mnt/foo/") == 0);
+
+ CxTreeIterator iter = cx_tree_iterator(
+ &root, true,
+ offsetof(tree_node_file, children),
+ offsetof(tree_node_file, next)
+ );
+ cx_foreach(tree_node_file *, node, iter) {
+ if (iter.exiting) {
+ if (node != &root) {
+ cxFree(alloc, node);
+ }
+ }
+ }
CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
}
cx_testing_allocator_destroy(&talloc);
}
-CX_TEST(test_tree_add_many_skip_duplicates) {
- // adds many elements to an existing tree
+static CX_TEST_SUBROUTINE(test_tree_add_create_from_array_impl,
+ CxAllocator *alloc, char const **paths) {
+ tree_node_file root = {0};
+ root.path = "/";
+
+ void *failed;
+ size_t processed = cx_tree_add_array(
+ paths, 10, sizeof(char const *),
+ tree_node_file_search,
+ create_tree_node_file, alloc,
+ &failed, &root, tree_node_file_layout
+ );
+
+ CX_TEST_ASSERT(failed == NULL);
+ CX_TEST_ASSERT(processed == 10);
+
+ char const *exp_order[] = {
+ "/",
+ "/usr/",
+ "/usr/lib/",
+ "/usr/lib/libbumm.so",
+ "/home/",
+ "/home/foo/",
+ "/var/",
+ "/var/www/",
+ "/var/www/vhosts/",
+ "/var/www/vhosts/live/",
+ "/var/www/vhosts/live/htdocs/"
+ };
+ unsigned exp_depth[] = {
+ 1,
+ 2,
+ 3,
+ 4,
+ 2,
+ 3,
+ 2,
+ 3,
+ 4,
+ 5,
+ 6
+ };
+
+ CxTreeIterator iter = cx_tree_iterator(
+ &root, true,
+ offsetof(tree_node_file, children),
+ offsetof(tree_node_file, next)
+ );
+ cx_foreach(tree_node_file *, node, iter) {
+ if (iter.exiting) {
+ if (node != &root) {
+ cxFree(alloc, node);
+ }
+ } else {
+ CX_TEST_ASSERT(iter.counter <= 11);
+ CX_TEST_ASSERT(iter.depth == exp_depth[iter.counter - 1]);
+ CX_TEST_ASSERT(strcmp(node->path, exp_order[iter.counter - 1]) == 0);
+ }
+ }
+}
+
+CX_TEST(test_tree_add_create_from_array) {
+ // creates an entirely new tree from an array
+
CxTestingAllocator talloc;
cx_testing_allocator_init(&talloc);
CxAllocator *alloc = &talloc.base;
- tree_node_file root = {0};
- root.path = "/";
- tree_node_file usr = {0};
- usr.path = "/usr/";
- cx_tree_link(&root, &usr, tree_node_file_layout);
- tree_node_file home = {0};
- home.path = "/home/";
- cx_tree_link(&root, &home, tree_node_file_layout);
- tree_node_file lib = {0};
- lib.path = "/usr/lib/";
- cx_tree_link(&usr, &lib, tree_node_file_layout);
-
CX_TEST_DO {
- void *newroot = &root;
-
char const *paths[] = {
- "/home/foo/",
- "/home/foo/bar",
+ "/usr/",
+ "/home/",
"/usr/lib/",
- "/usr/lib/foo.so"
+ "/usr/lib/libbumm.so",
+ "/var/",
+ "/var/www/",
+ "/var/www/vhosts/",
+ "/var/www/vhosts/live/",
+ "/var/www/vhosts/live/htdocs/",
+ "/home/foo/"
};
- size_t processed = cx_tree_add_array(
- paths, 4, sizeof(char const *),
- tree_node_file_search,
- create_tree_node_file, alloc,
- &newroot, tree_node_file_layout
- );
- CX_TEST_ASSERT(newroot == &root);
-
- CX_TEST_ASSERT(processed == 4);
- CX_TEST_ASSERT(talloc.alloc_total == 3);
+ char const *scrambled_paths[] = {
+ "/usr/",
+ "/home/",
+ "/var/www/vhosts/live/",
+ "/usr/lib/",
+ "/var/",
+ "/var/www/",
+ "/usr/lib/libbumm.so",
+ "/var/www/vhosts/",
+ "/var/www/vhosts/live/htdocs/",
+ "/home/foo/"
+ };
- CX_TEST_ASSERT(home.children == home.last_child);
- tree_node_file *foo = home.children;
- CX_TEST_ASSERT(foo != NULL && foo->path == paths[0]);
- CX_TEST_ASSERT(foo->children == foo->last_child);
- tree_node_file *bar = foo->children;
- CX_TEST_ASSERT(bar != NULL && bar->path == paths[1]);
- CX_TEST_ASSERT(usr.children == usr.last_child);
- CX_TEST_ASSERT(usr.children == &lib);
- CX_TEST_ASSERT(lib.children != NULL);
- tree_node_file *libfoo = lib.children;
- CX_TEST_ASSERT(libfoo != NULL && libfoo->path == paths[3]);
-
- cxFree(&talloc.base, foo);
- cxFree(&talloc.base, bar);
- cxFree(&talloc.base, libfoo);
+ // no matter how the original array is sorted,
+ // the resulting tree should be the same
+ CX_TEST_CALL_SUBROUTINE(test_tree_add_create_from_array_impl, alloc,
+ paths);
+ CX_TEST_CALL_SUBROUTINE(test_tree_add_create_from_array_impl, alloc,
+ scrambled_paths);
CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
}
cx_testing_allocator_destroy(&talloc);
}
-CX_TEST(test_tree_add_create_from_array) {
- // creates an entirely new tree from an array
- CX_TEST_DO {
-
- }
-}
-
CxTestSuite *cx_test_suite_tree_low_level(void) {
CxTestSuite *suite = cx_test_suite_new("tree (low level)");
@@ -1322,9 +1490,11 @@
cx_test_register(suite, test_tree_iterator_continue_with_exit);
cx_test_register(suite, test_tree_add_one);
cx_test_register(suite, test_tree_add_one_existing);
- cx_test_register(suite, test_tree_add_one_to_empty_tree);
+ cx_test_register(suite, test_tree_add_one_no_match);
+ cx_test_register(suite, test_tree_add_duplicate_root);
+ cx_test_register(suite, test_tree_add_zero);
cx_test_register(suite, test_tree_add_many);
- cx_test_register(suite, test_tree_add_many_skip_duplicates);
+ cx_test_register(suite, test_tree_add_many_with_dupl_and_no_match);
cx_test_register(suite, test_tree_add_create_from_array);
return suite;