--- a/tests/test_tree.c Sun Jul 07 14:56:44 2024 +0200 +++ b/tests/test_tree.c Tue Aug 20 18:02:39 2024 +0200 @@ -49,13 +49,58 @@ int data; } tree_node2; +typedef struct tree_node_file { + struct tree_node_file *parent; + struct tree_node_file *next; + struct tree_node_file *prev; + struct tree_node_file *children; + struct tree_node_file *last_child; + char const *path; +} tree_node_file; + +static void *create_tree_node_file( + void const *dptr, + void *allocator) { + if (allocator == NULL) allocator = cxDefaultAllocator; + + 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; + + return node; +} + +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(left->path, right->path, len1) == 0) { + return (int) (len2 - len1); + } else { + return -1; + } + } else { + return -1; + } +} + #define tree_node_layout \ offsetof(tree_node, parent), offsetof(tree_node, children), -1, \ offsetof(tree_node, prev), offsetof(tree_node, next) -#define tree_node2_layout \ - offsetof(tree_node2, parent), offsetof(tree_node2, children),\ - offsetof(tree_node2, last_child), \ - offsetof(tree_node2, prev), offsetof(tree_node2, next) +#define tree_node_full_layout(structname) \ + offsetof(structname, parent), offsetof(structname, children),\ + offsetof(structname, last_child), \ + offsetof(structname, prev), offsetof(structname, next) +#define tree_node2_layout tree_node_full_layout(tree_node2) +#define tree_node_file_layout tree_node_full_layout(tree_node_file) #define tree_children(type) offsetof(type, children), offsetof(type, next) @@ -376,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); @@ -993,6 +1038,433 @@ } } +CX_TEST(test_tree_add_one) { + 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 { + tree_node_file *foo; + int result; + result = cx_tree_add( + "/home/foo/", + tree_node_file_search, + create_tree_node_file, alloc, + (void **) &foo, &root, + tree_node_file_layout + ); + 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, + &failed, &root, + tree_node_file_layout + ); + 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); + + 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); + + 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_existing) { + 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 { + tree_node_file *node; + int result = cx_tree_add( + "/usr/lib/", + tree_node_file_search, + create_tree_node_file, alloc, + (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(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); + } +} + +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, + &failed, &root, tree_node_file_layout + ); + 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); +} + +CX_TEST(test_tree_add_many) { + // adds many elements to an existing tree + + 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 *failed; + + char const *paths[] = { + "/home/foo/", + "/home/foo/bar", + "/usr/lib64/", + "/usr/lib/foo.so" + }; + + size_t processed = cx_tree_add_array( + paths, 4, 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 == 4); + CX_TEST_ASSERT(talloc.alloc_total == 4); + + 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); + tree_node_file *lib64 = usr.last_child; + CX_TEST_ASSERT(lib64 != NULL); + CX_TEST_ASSERT(lib64->path == paths[2]); + CX_TEST_ASSERT(lib64->prev == &lib); + CX_TEST_ASSERT(lib64->parent == &usr); + CX_TEST_ASSERT(lib.children != NULL); + tree_node_file *libfoo = lib.children; + CX_TEST_ASSERT(libfoo != NULL && libfoo->path == paths[3]); + + 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); +} + +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; + + CX_TEST_DO { + char const *paths[] = { + "/usr/", + "/home/", + "/usr/lib/", + "/usr/lib/libbumm.so", + "/var/", + "/var/www/", + "/var/www/vhosts/", + "/var/www/vhosts/live/", + "/var/www/vhosts/live/htdocs/", + "/home/foo/" + }; + + 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/" + }; + + // 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); +} + + CxTestSuite *cx_test_suite_tree_low_level(void) { CxTestSuite *suite = cx_test_suite_new("tree (low level)"); @@ -1016,6 +1488,14 @@ cx_test_register(suite, test_tree_visitor_continue); cx_test_register(suite, test_tree_iterator_continue); 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_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_with_dupl_and_no_match); + cx_test_register(suite, test_tree_add_create_from_array); return suite; }