--- a/tests/test_tree.c Mon Aug 19 18:46:49 2024 +0200
+++ b/tests/test_tree.c Mon Aug 19 20:46:36 2024 +0200
@@ -49,13 +49,66 @@
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 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;
+
+ // 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 *nptr, void const *data) {
+ tree_node_file const *node = nptr;
+ size_t len1 = strlen(node->path);
+ size_t len2 = strlen(data);
+ if (len1 <= len2) {
+ if (memcmp(node->path, data, 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)
@@ -993,6 +1046,257 @@
}
}
+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 {
+ void *newroot = &root;
+
+ tree_node_file *foo = cx_tree_add(
+ "/home/foo/",
+ tree_node_file_search,
+ create_tree_node_file, alloc,
+ &newroot, tree_node_file_layout
+ );
+ CX_TEST_ASSERT(newroot == &root);
+ tree_node_file *bar = cx_tree_add(
+ "/home/foo/bar/",
+ tree_node_file_search,
+ create_tree_node_file, alloc,
+ &newroot, tree_node_file_layout
+ );
+ CX_TEST_ASSERT(newroot == &root);
+
+ CX_TEST_ASSERT(bar->parent == foo);
+ CX_TEST_ASSERT(foo->parent == &home);
+
+ CX_TEST_ASSERT(talloc.alloc_total == 2);
+
+ cxFree(&talloc.base, foo);
+ cxFree(&talloc.base, bar);
+
+ 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);
+ 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;
+
+ tree_node_file *node;
+ node = cx_tree_add(
+ "/usr/lib/",
+ tree_node_file_search,
+ create_tree_node_file, alloc,
+ &newroot, tree_node_file_layout
+ );
+ CX_TEST_ASSERT(newroot == &root);
+ CX_TEST_ASSERT(node == &lib);
+
+ node = cx_tree_add(
+ "/home/",
+ tree_node_file_search,
+ create_tree_node_file, alloc,
+ &newroot, tree_node_file_layout
+ );
+ CX_TEST_ASSERT(newroot == &root);
+ CX_TEST_ASSERT(node == &home);
+
+ 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 *newroot = &root;
+
+ 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,
+ &newroot, tree_node_file_layout
+ );
+ CX_TEST_ASSERT(newroot == &root);
+
+ 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(&talloc.base, foo);
+ cxFree(&talloc.base, bar);
+ cxFree(&talloc.base, lib64);
+ cxFree(&talloc.base, libfoo);
+
+ 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
+ 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/lib/",
+ "/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,
+ &newroot, tree_node_file_layout
+ );
+ CX_TEST_ASSERT(newroot == &root);
+
+ CX_TEST_ASSERT(processed == 4);
+ CX_TEST_ASSERT(talloc.alloc_total == 3);
+
+ 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);
+
+ 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)");
@@ -1016,6 +1320,12 @@
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_to_empty_tree);
+ 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_create_from_array);
return suite;
}