--- a/tests/test_tree.c Tue Dec 30 13:50:55 2025 +0100
+++ b/tests/test_tree.c Tue Dec 30 21:44:23 2025 +0100
@@ -41,7 +41,7 @@
} tree_node;
typedef struct tree_node2 {
- CX_TREE_NODE_BASE(struct tree_node2);
+ CX_TREE_NODE(struct tree_node2);
int data;
} tree_node2;
@@ -54,37 +54,13 @@
const char *path;
} tree_node_file;
-static void *tree_node_file_create(
- const void *dptr,
- void *allocator) {
- if (allocator == NULL) allocator = (void*) 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 void *tree_node_file_create_hl(
- const void *dptr,
- void *tree) {
- return tree_node_file_create(dptr, (void*)((CxTree*)tree)->collection.allocator);
-}
-
-static int tree_node_file_search(const void *l, const void *r) {
+static int tree_node_file_search_func(const void *l, const void *d) {
const tree_node_file *left = l;
- const tree_node_file *right = r;
+ const char *right = d;
size_t len1 = strlen(left->path);
- size_t len2 = strlen(right->path);
+ size_t len2 = strlen(right);
if (len1 <= len2) {
- if (memcmp(left->path, right->path, len1) == 0) {
+ if (memcmp(left->path, right, len1) == 0) {
return (int) (len2 - len1);
} else {
return -1;
@@ -94,54 +70,33 @@
}
}
-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)
#define tree_node_layout_no_prev \
offsetof(tree_node, parent), offsetof(tree_node, children), -1, -1, \
offsetof(tree_node, 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 cx_tree_node_base_layout
-#define tree_node_file_layout tree_node_full_layout(tree_node_file)
-
#define tree_children(type) offsetof(type, children), offsetof(type, next)
-CX_TEST(test_tree_link_new_child) {
- tree_node parent = {0};
- tree_node child = {0};
-
- CX_TEST_DO {
- cx_tree_link(&parent, &child, tree_node_layout);
- CX_TEST_ASSERT(parent.next == NULL);
- CX_TEST_ASSERT(parent.prev == NULL);
- CX_TEST_ASSERT(parent.parent == NULL);
- CX_TEST_ASSERT(parent.children == &child);
- CX_TEST_ASSERT(child.parent == &parent);
- CX_TEST_ASSERT(child.next == NULL);
- CX_TEST_ASSERT(child.prev == NULL);
- CX_TEST_ASSERT(child.children == NULL);
- }
-}
-
-CX_TEST(test_tree_link_add_child) {
+CX_TEST(test_tree_add) {
tree_node parent = {0};
tree_node child1 = {0};
tree_node child2 = {0};
tree_node child3 = {0};
CX_TEST_DO {
- cx_tree_link(&parent, &child1, tree_node_layout);
- cx_tree_link(&parent, &child2, tree_node_layout);
- cx_tree_link(&parent, &child3, tree_node_layout);
+ cx_tree_add(&parent, &child1, tree_node_layout);
+ CX_TEST_ASSERT(parent.next == NULL);
+ CX_TEST_ASSERT(parent.prev == NULL);
+ CX_TEST_ASSERT(parent.parent == NULL);
+ CX_TEST_ASSERT(parent.children == &child1);
+ CX_TEST_ASSERT(child1.parent == &parent);
+ CX_TEST_ASSERT(child1.next == NULL);
+ CX_TEST_ASSERT(child1.prev == NULL);
+ CX_TEST_ASSERT(child1.children == NULL);
+
+ cx_tree_add(&parent, &child2, tree_node_layout);
+ cx_tree_add(&parent, &child3, tree_node_layout);
CX_TEST_ASSERT(parent.next == NULL);
CX_TEST_ASSERT(parent.prev == NULL);
CX_TEST_ASSERT(parent.parent == NULL);
@@ -163,17 +118,17 @@
}
}
-CX_TEST(test_tree_link_move_to_other_parent) {
+CX_TEST(test_tree_add_move_to_other_parent) {
tree_node parent = {0};
tree_node child1 = {0};
tree_node child2 = {0};
tree_node child3 = {0};
- cx_tree_link(&parent, &child1, tree_node_layout);
- cx_tree_link(&parent, &child2, tree_node_layout);
- cx_tree_link(&parent, &child3, tree_node_layout);
+ cx_tree_add(&parent, &child1, tree_node_layout);
+ cx_tree_add(&parent, &child2, tree_node_layout);
+ cx_tree_add(&parent, &child3, tree_node_layout);
CX_TEST_DO {
- cx_tree_link(&child3, &child2, tree_node_layout);
+ cx_tree_add(&child3, &child2, tree_node_layout);
CX_TEST_ASSERT(parent.next == NULL);
CX_TEST_ASSERT(parent.prev == NULL);
@@ -197,19 +152,19 @@
}
}
-CX_TEST(test_tree_unlink) {
+CX_TEST(test_tree_remove) {
tree_node parent = {0};
tree_node child1 = {0};
tree_node child2 = {0};
tree_node child3 = {0};
tree_node child4 = {0};
- cx_tree_link(&parent, &child1, tree_node_layout);
- cx_tree_link(&parent, &child3, tree_node_layout);
- cx_tree_link(&parent, &child4, tree_node_layout);
- cx_tree_link(&child3, &child2, tree_node_layout);
+ cx_tree_add(&parent, &child1, tree_node_layout);
+ cx_tree_add(&parent, &child3, tree_node_layout);
+ cx_tree_add(&parent, &child4, tree_node_layout);
+ cx_tree_add(&child3, &child2, tree_node_layout);
CX_TEST_DO {
- cx_tree_unlink(&child3, tree_node_layout);
+ cx_tree_remove(&child3, tree_node_layout);
CX_TEST_ASSERT(parent.next == NULL);
CX_TEST_ASSERT(parent.prev == NULL);
@@ -239,7 +194,7 @@
CX_TEST_ASSERT(child2.next == NULL);
// unlink first child from parent
- cx_tree_unlink(&child1, tree_node_layout);
+ cx_tree_remove(&child1, tree_node_layout);
CX_TEST_ASSERT(parent.next == NULL);
CX_TEST_ASSERT(parent.prev == NULL);
CX_TEST_ASSERT(parent.parent == NULL);
@@ -252,22 +207,22 @@
}
}
-CX_TEST(test_tree_unlink_no_prev) {
+CX_TEST(test_tree_remove_no_prev) {
tree_node parent = {0};
tree_node child1 = {0};
tree_node child2 = {0};
tree_node child3 = {0};
tree_node child4 = {0};
- cx_tree_link(&parent, &child1, tree_node_layout_no_prev);
- cx_tree_link(&parent, &child3, tree_node_layout_no_prev);
- cx_tree_link(&parent, &child4, tree_node_layout_no_prev);
- cx_tree_link(&child3, &child2, tree_node_layout_no_prev);
+ cx_tree_add(&parent, &child1, tree_node_layout_no_prev);
+ cx_tree_add(&parent, &child3, tree_node_layout_no_prev);
+ cx_tree_add(&parent, &child4, tree_node_layout_no_prev);
+ cx_tree_add(&child3, &child2, tree_node_layout_no_prev);
void * const marker = (void*) 0xc0ffee;
child1.prev = child2.prev = child3.prev = child4.prev = marker;
CX_TEST_DO {
// in contrast to the other test we here remove child 4 instead of 3!
- cx_tree_unlink(&child4, tree_node_layout_no_prev);
+ cx_tree_remove(&child4, tree_node_layout_no_prev);
CX_TEST_ASSERT(parent.next == NULL);
CX_TEST_ASSERT(parent.prev == NULL);
@@ -286,7 +241,7 @@
CX_TEST_ASSERT(child4.next == NULL);
// unlink first child from parent
- cx_tree_unlink(&child1, tree_node_layout_no_prev);
+ cx_tree_remove(&child1, tree_node_layout_no_prev);
CX_TEST_ASSERT(parent.next == NULL);
CX_TEST_ASSERT(parent.prev == NULL);
CX_TEST_ASSERT(parent.parent == NULL);
@@ -304,7 +259,7 @@
tree_node2 child = {0};
CX_TEST_DO {
- cx_tree_link(&parent, &child, tree_node2_layout);
+ cx_tree_add(&parent, &child, cx_tree_node_layout(tree_node2));
CX_TEST_ASSERT(parent.next == NULL);
CX_TEST_ASSERT(parent.prev == NULL);
CX_TEST_ASSERT(parent.parent == NULL);
@@ -325,9 +280,9 @@
tree_node2 child3 = {0};
CX_TEST_DO {
- cx_tree_link(&parent, &child1, tree_node2_layout);
- cx_tree_link(&parent, &child2, tree_node2_layout);
- cx_tree_link(&parent, &child3, tree_node2_layout);
+ cx_tree_add(&parent, &child1, cx_tree_node_layout(tree_node2));
+ cx_tree_add(&parent, &child2, cx_tree_node_layout(tree_node2));
+ cx_tree_add(&parent, &child3, cx_tree_node_layout(tree_node2));
CX_TEST_ASSERT(parent.next == NULL);
CX_TEST_ASSERT(parent.prev == NULL);
CX_TEST_ASSERT(parent.parent == NULL);
@@ -358,12 +313,12 @@
tree_node2 child1 = {0};
tree_node2 child2 = {0};
tree_node2 child3 = {0};
- cx_tree_link(&parent, &child1, tree_node2_layout);
- cx_tree_link(&parent, &child2, tree_node2_layout);
- cx_tree_link(&parent, &child3, tree_node2_layout);
+ cx_tree_add(&parent, &child1, cx_tree_node_layout(tree_node2));
+ cx_tree_add(&parent, &child2, cx_tree_node_layout(tree_node2));
+ cx_tree_add(&parent, &child3, cx_tree_node_layout(tree_node2));
CX_TEST_DO {
- cx_tree_link(&child3, &child2, tree_node2_layout);
+ cx_tree_add(&child3, &child2, cx_tree_node_layout(tree_node2));
CX_TEST_ASSERT(parent.next == NULL);
CX_TEST_ASSERT(parent.prev == NULL);
@@ -396,12 +351,12 @@
tree_node2 child1 = {0};
tree_node2 child2 = {0};
tree_node2 child3 = {0};
- cx_tree_link(&parent, &child1, tree_node2_layout);
- cx_tree_link(&parent, &child3, tree_node2_layout);
- cx_tree_link(&child3, &child2, tree_node2_layout);
+ cx_tree_add(&parent, &child1, cx_tree_node_layout(tree_node2));
+ cx_tree_add(&parent, &child3, cx_tree_node_layout(tree_node2));
+ cx_tree_add(&child3, &child2, cx_tree_node_layout(tree_node2));
CX_TEST_DO {
- cx_tree_unlink(&child3, tree_node2_layout);
+ cx_tree_remove(&child3, cx_tree_node_layout(tree_node2));
CX_TEST_ASSERT(parent.next == NULL);
CX_TEST_ASSERT(parent.prev == NULL);
@@ -430,7 +385,7 @@
CX_TEST_ASSERT(child2.next == NULL);
// unlink last child from parent
- cx_tree_unlink(&child1, tree_node2_layout);
+ cx_tree_remove(&child1, cx_tree_node_layout(tree_node2));
CX_TEST_ASSERT(parent.next == NULL);
CX_TEST_ASSERT(parent.prev == NULL);
CX_TEST_ASSERT(parent.parent == NULL);
@@ -469,20 +424,20 @@
testnodes[i]->data = testdata[i];
}
- cx_tree_link(&root, &a, tree_node_layout);
- cx_tree_link(&root, &b, tree_node_layout);
- cx_tree_link(&root, &c, tree_node_layout);
+ cx_tree_add(&root, &a, tree_node_layout);
+ cx_tree_add(&root, &b, tree_node_layout);
+ cx_tree_add(&root, &c, tree_node_layout);
- cx_tree_link(&a, &aa, tree_node_layout);
- cx_tree_link(&a, &ab, tree_node_layout);
+ cx_tree_add(&a, &aa, tree_node_layout);
+ cx_tree_add(&a, &ab, tree_node_layout);
- cx_tree_link(&b, &ba, tree_node_layout);
+ cx_tree_add(&b, &ba, tree_node_layout);
- cx_tree_link(&c, &ca, tree_node_layout);
- cx_tree_link(&c, &cb, tree_node_layout);
- cx_tree_link(&c, &cc, tree_node_layout);
+ cx_tree_add(&c, &ca, tree_node_layout);
+ cx_tree_add(&c, &cb, tree_node_layout);
+ cx_tree_add(&c, &cc, tree_node_layout);
- cx_tree_link(&cb, &cba, tree_node_layout);
+ cx_tree_add(&cb, &cba, tree_node_layout);
int s;
int r;
@@ -490,38 +445,38 @@
CX_TEST_DO {
for (unsigned i = 0 ; i <= 10 ; i++) {
s = testdata[i];
- r = cx_tree_search_data(&root, 0, &s, test_tree_search_function,
+ r = cx_tree_search(&root, 0, &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_data(&root, 0, &s, test_tree_search_function,
+ r = cx_tree_search(&root, 0, &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_data(&root, 0, &s, test_tree_search_function,
+ r = cx_tree_search(&root, 0, &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_data(&root, 0, &s, test_tree_search_function,
+ r = cx_tree_search(&root, 0, &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_data(&root, 0, &s, test_tree_search_function,
+ r = cx_tree_search(&root, 0, &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_data(&root, 0, &s, test_tree_search_function,
+ r = cx_tree_search(&root, 0, &s, test_tree_search_function,
(void **) &n, tree_children(tree_node));
CX_TEST_ASSERT(r > 0);
CX_TEST_ASSERT(n == &cc);
@@ -533,115 +488,115 @@
root.path = "/";
tree_node_file usr = {0};
usr.path = "/usr/";
- cx_tree_link(&root, &usr, tree_node_file_layout);
+ cx_tree_add(&root, &usr, cx_tree_node_layout(tree_node_file));
tree_node_file home = {0};
home.path = "/home/";
- cx_tree_link(&root, &home, tree_node_file_layout);
+ cx_tree_add(&root, &home, cx_tree_node_layout(tree_node_file));
tree_node_file doe = {0};
doe.path = "/home/doe/";
- cx_tree_link(&home, &doe, tree_node_file_layout);
+ cx_tree_add(&home, &doe, cx_tree_node_layout(tree_node_file));
tree_node_file lib = {0};
lib.path = "/usr/lib/";
- cx_tree_link(&usr, &lib, tree_node_file_layout);
+ cx_tree_add(&usr, &lib, cx_tree_node_layout(tree_node_file));
tree_node_file modules = {0};
modules.path = "/usr/lib/modules/";
- cx_tree_link(&lib, &modules, tree_node_file_layout);
+ cx_tree_add(&lib, &modules, cx_tree_node_layout(tree_node_file));
CX_TEST_DO {
int result;
void *found;
- result = cx_tree_search_data(
+ result = cx_tree_search(
&root, 1, "/",
- tree_node_file_search_data, &found,
+ tree_node_file_search_func, &found,
tree_children(tree_node_file)
);
CX_TEST_ASSERTM(result == 0, "root not found");
CX_TEST_ASSERT(found == &root);
- result = cx_tree_search_data(
+ result = cx_tree_search(
&root, 1, "/usr/",
- tree_node_file_search_data, &found,
+ tree_node_file_search_func, &found,
tree_children(tree_node_file)
);
CX_TEST_ASSERT(result > 0);
CX_TEST_ASSERT(found == &root);
- result = cx_tree_search_data(
+ result = cx_tree_search(
&root, 2, "/usr/",
- tree_node_file_search_data, &found,
+ tree_node_file_search_func, &found,
tree_children(tree_node_file)
);
CX_TEST_ASSERT(result == 0);
CX_TEST_ASSERT(found == &usr);
- result = cx_tree_search_data(
+ result = cx_tree_search(
&root, 2, "/usr/lib/",
- tree_node_file_search_data, &found,
+ tree_node_file_search_func, &found,
tree_children(tree_node_file)
);
CX_TEST_ASSERT(result > 0);
CX_TEST_ASSERT(found == &usr);
- result = cx_tree_search_data(
+ result = cx_tree_search(
&root, 3, "/usr/lib/",
- tree_node_file_search_data, &found,
+ tree_node_file_search_func, &found,
tree_children(tree_node_file)
);
CX_TEST_ASSERTM(result == 0, "lib not found");
CX_TEST_ASSERT(found == &lib);
- result = cx_tree_search_data(
+ result = cx_tree_search(
&root, 1, "/home/",
- tree_node_file_search_data, &found,
+ tree_node_file_search_func, &found,
tree_children(tree_node_file)
);
CX_TEST_ASSERT(result > 0);
CX_TEST_ASSERT(found == &root);
- result = cx_tree_search_data(
+ result = cx_tree_search(
&root, 2, "/home/",
- tree_node_file_search_data, &found,
+ tree_node_file_search_func, &found,
tree_children(tree_node_file)
);
CX_TEST_ASSERTM(result == 0, "home not found");
CX_TEST_ASSERT(found == &home);
- result = cx_tree_search_data(
+ result = cx_tree_search(
&root, 2, "/home/doe/",
- tree_node_file_search_data, &found,
+ tree_node_file_search_func, &found,
tree_children(tree_node_file)
);
CX_TEST_ASSERT(result > 0);
CX_TEST_ASSERT(found == &home);
- result = cx_tree_search_data(
+ result = cx_tree_search(
&root, 3, "/home/doe/",
- tree_node_file_search_data, &found,
+ tree_node_file_search_func, &found,
tree_children(tree_node_file)
);
CX_TEST_ASSERTM(result == 0, "doe not found");
CX_TEST_ASSERT(found == &doe);
- result = cx_tree_search_data(
+ result = cx_tree_search(
&root, 3, "/usr/lib/modules/",
- tree_node_file_search_data, &found,
+ tree_node_file_search_func, &found,
tree_children(tree_node_file)
);
CX_TEST_ASSERT(result > 0);
CX_TEST_ASSERT(found == &lib);
- result = cx_tree_search_data(
+ result = cx_tree_search(
&root, 4, "/usr/lib/modules/",
- tree_node_file_search_data, &found,
+ tree_node_file_search_func, &found,
tree_children(tree_node_file)
);
CX_TEST_ASSERTM(result == 0, "modules not found (start=root)");
CX_TEST_ASSERT(found == &modules);
- result = cx_tree_search_data(
+ result = cx_tree_search(
&usr, 3, "/usr/lib/modules/",
- tree_node_file_search_data, &found,
+ tree_node_file_search_func, &found,
tree_children(tree_node_file)
);
CX_TEST_ASSERTM(result == 0, "modules not found (start=usr)");
@@ -661,7 +616,6 @@
CX_TEST_ASSERT(!iter.base.remove);
CX_TEST_ASSERT(iter.stack != NULL);
CX_TEST_ASSERT(iter.stack_capacity > 0);
- CX_TEST_ASSERT(iter.stack_size == 1);
CX_TEST_ASSERT(iter.depth == 1);
CX_TEST_ASSERT(iter.loc_next == offsetof(tree_node, next));
CX_TEST_ASSERT(iter.loc_children == offsetof(tree_node, children));
@@ -681,7 +635,6 @@
CX_TEST_ASSERT(!iter.base.remove);
CX_TEST_ASSERT(iter.stack == NULL);
CX_TEST_ASSERT(iter.stack_capacity == 0);
- CX_TEST_ASSERT(iter.stack_size == 0);
CX_TEST_ASSERT(iter.depth == 0);
CX_TEST_ASSERT(iter.loc_next == offsetof(tree_node, next));
CX_TEST_ASSERT(iter.loc_children == offsetof(tree_node, children));
@@ -712,16 +665,16 @@
};
tree_node* actual_order[16]; // reserve more space in case s.t. goes wrong
- cx_tree_link(&root, &a, tree_node_layout);
- cx_tree_link(&root, &b, tree_node_layout);
- cx_tree_link(&root, &c, tree_node_layout);
- cx_tree_link(&a, &aa, tree_node_layout);
- cx_tree_link(&a, &ab, tree_node_layout);
- cx_tree_link(&b, &ba, tree_node_layout);
- cx_tree_link(&c, &ca, tree_node_layout);
- cx_tree_link(&c, &cb, tree_node_layout);
- cx_tree_link(&c, &cc, tree_node_layout);
- cx_tree_link(&cb, &cba, tree_node_layout);
+ cx_tree_add(&root, &a, tree_node_layout);
+ cx_tree_add(&root, &b, tree_node_layout);
+ cx_tree_add(&root, &c, tree_node_layout);
+ cx_tree_add(&a, &aa, tree_node_layout);
+ cx_tree_add(&a, &ab, tree_node_layout);
+ cx_tree_add(&b, &ba, tree_node_layout);
+ cx_tree_add(&c, &ca, tree_node_layout);
+ cx_tree_add(&c, &cb, tree_node_layout);
+ cx_tree_add(&c, &cc, tree_node_layout);
+ cx_tree_add(&cb, &cba, tree_node_layout);
CX_TEST_DO {
CxTreeIterator iter = cx_tree_iterator(&root, false, tree_children(tree_node));
unsigned chk = 0;
@@ -765,16 +718,16 @@
tree_node cc = {0};
tree_node cba = {0};
- cx_tree_link(&root, &a, tree_node_layout);
- cx_tree_link(&root, &b, tree_node_layout);
- cx_tree_link(&root, &c, tree_node_layout);
- cx_tree_link(&a, &aa, tree_node_layout);
- cx_tree_link(&a, &ab, tree_node_layout);
- cx_tree_link(&b, &ba, tree_node_layout);
- cx_tree_link(&c, &ca, tree_node_layout);
- cx_tree_link(&c, &cb, tree_node_layout);
- cx_tree_link(&c, &cc, tree_node_layout);
- cx_tree_link(&cb, &cba, tree_node_layout);
+ cx_tree_add(&root, &a, tree_node_layout);
+ cx_tree_add(&root, &b, tree_node_layout);
+ cx_tree_add(&root, &c, tree_node_layout);
+ cx_tree_add(&a, &aa, tree_node_layout);
+ cx_tree_add(&a, &ab, tree_node_layout);
+ cx_tree_add(&b, &ba, tree_node_layout);
+ cx_tree_add(&c, &ca, tree_node_layout);
+ cx_tree_add(&c, &cb, tree_node_layout);
+ cx_tree_add(&c, &cc, tree_node_layout);
+ cx_tree_add(&cb, &cba, tree_node_layout);
CX_TEST_DO {
CxTreeIterator iter = cx_tree_iterator(&root, true, tree_children(tree_node));
unsigned chk = 0;
@@ -823,16 +776,16 @@
tree_node cc = { 0 };
tree_node cba = { 0 };
- cx_tree_link(&root, &a, tree_node_layout);
- cx_tree_link(&root, &b, tree_node_layout);
- cx_tree_link(&root, &c, tree_node_layout);
- cx_tree_link(&a, &aa, tree_node_layout);
- cx_tree_link(&a, &ab, tree_node_layout);
- cx_tree_link(&b, &ba, tree_node_layout);
- cx_tree_link(&c, &ca, tree_node_layout);
- cx_tree_link(&c, &cb, tree_node_layout);
- cx_tree_link(&c, &cc, tree_node_layout);
- cx_tree_link(&cb, &cba, tree_node_layout);
+ cx_tree_add(&root, &a, tree_node_layout);
+ cx_tree_add(&root, &b, tree_node_layout);
+ cx_tree_add(&root, &c, tree_node_layout);
+ cx_tree_add(&a, &aa, tree_node_layout);
+ cx_tree_add(&a, &ab, tree_node_layout);
+ cx_tree_add(&b, &ba, tree_node_layout);
+ cx_tree_add(&c, &ca, tree_node_layout);
+ cx_tree_add(&c, &cb, tree_node_layout);
+ cx_tree_add(&c, &cc, tree_node_layout);
+ cx_tree_add(&cb, &cba, tree_node_layout);
CX_TEST_DO{
CxTreeIterator iter = cx_tree_iterator(&b, true, tree_children(tree_node));
unsigned chk = 0;
@@ -931,19 +884,19 @@
target_dependencies.name = "dependencies";
target_feature_dependencies.name = "dependencies";
- cx_tree_link(&project, &config, tree_node_layout);
- cx_tree_link(&project, &dependency1, tree_node_layout);
- cx_tree_link(&project, &dependency2, tree_node_layout);
- cx_tree_link(&project, &target, tree_node_layout);
- cx_tree_link(&config, &var1, tree_node_layout);
- cx_tree_link(&config, &var2, tree_node_layout);
- cx_tree_link(&config, &var3, tree_node_layout);
- cx_tree_link(&dependency1, &dependency1make, tree_node_layout);
- cx_tree_link(&dependency2, &dependency2lang, tree_node_layout);
- cx_tree_link(&dependency2, &dependency2make, tree_node_layout);
- cx_tree_link(&target, &target_feature, tree_node_layout);
- cx_tree_link(&target, &target_dependencies, tree_node_layout);
- cx_tree_link(&target_feature, &target_feature_dependencies, tree_node_layout);
+ cx_tree_add(&project, &config, tree_node_layout);
+ cx_tree_add(&project, &dependency1, tree_node_layout);
+ cx_tree_add(&project, &dependency2, tree_node_layout);
+ cx_tree_add(&project, &target, tree_node_layout);
+ cx_tree_add(&config, &var1, tree_node_layout);
+ cx_tree_add(&config, &var2, tree_node_layout);
+ cx_tree_add(&config, &var3, tree_node_layout);
+ cx_tree_add(&dependency1, &dependency1make, tree_node_layout);
+ cx_tree_add(&dependency2, &dependency2lang, tree_node_layout);
+ cx_tree_add(&dependency2, &dependency2make, tree_node_layout);
+ cx_tree_add(&target, &target_feature, tree_node_layout);
+ cx_tree_add(&target, &target_dependencies, tree_node_layout);
+ cx_tree_add(&target_feature, &target_feature_dependencies, tree_node_layout);
const char *expected =
"<project><config><var></var><var></var><var></var></config>"
@@ -986,16 +939,16 @@
tree_node *cc = cxCalloc(alloc, 1, sizeof(tree_node));
tree_node *cba = cxCalloc(alloc, 1, sizeof(tree_node));
- cx_tree_link(root, a, tree_node_layout);
- cx_tree_link(root, b, tree_node_layout);
- cx_tree_link(root, c, tree_node_layout);
- cx_tree_link(a, aa, tree_node_layout);
- cx_tree_link(a, ab, tree_node_layout);
- cx_tree_link(b, ba, tree_node_layout);
- cx_tree_link(c, ca, tree_node_layout);
- cx_tree_link(c, cb, tree_node_layout);
- cx_tree_link(c, cc, tree_node_layout);
- cx_tree_link(cb, cba, tree_node_layout);
+ cx_tree_add(root, a, tree_node_layout);
+ cx_tree_add(root, b, tree_node_layout);
+ cx_tree_add(root, c, tree_node_layout);
+ cx_tree_add(a, aa, tree_node_layout);
+ cx_tree_add(a, ab, tree_node_layout);
+ cx_tree_add(b, ba, tree_node_layout);
+ cx_tree_add(c, ca, tree_node_layout);
+ cx_tree_add(c, cb, tree_node_layout);
+ cx_tree_add(c, cc, tree_node_layout);
+ cx_tree_add(cb, cba, tree_node_layout);
CxTreeIterator iter = cx_tree_iterator(root, true, tree_children(tree_node));
cx_foreach(tree_node *, node, iter) {
@@ -1013,10 +966,10 @@
tree_node root = {0};
tree_node child = {0};
tree_node child2 = {0};
- cx_tree_link(&root, &child, tree_node_layout);
- cx_tree_link(&root, &child2, tree_node_layout);
+ cx_tree_add(&root, &child, tree_node_layout);
+ cx_tree_add(&root, &child2, tree_node_layout);
CX_TEST_DO {
- CxTreeVisitor iter = cx_tree_visitor(&root, tree_children(tree_node));
+ CxTreeIterator iter = cx_tree_visitor(&root, tree_children(tree_node));
CX_TEST_ASSERT(iter.counter == 1);
CX_TEST_ASSERT(iter.node == &root);
CX_TEST_ASSERT(!iter.base.allow_remove);
@@ -1029,7 +982,7 @@
CX_TEST_ASSERT(iter.queue_last != NULL);
CX_TEST_ASSERT(iter.queue_next->node == &child2);
CX_TEST_ASSERT(iter.queue_last->node == &child2);
- cxTreeVisitorDispose(&iter);
+ cxTreeIteratorDispose(&iter);
CX_TEST_ASSERT(iter.queue_next == NULL);
CX_TEST_ASSERT(iter.queue_last == NULL);
}
@@ -1056,18 +1009,18 @@
};
tree_node* actual_order[16]; // reserve more space in case s.t. goes wrong
- cx_tree_link(&root, &a, tree_node_layout);
- cx_tree_link(&root, &b, tree_node_layout);
- cx_tree_link(&root, &c, tree_node_layout);
- cx_tree_link(&a, &aa, tree_node_layout);
- cx_tree_link(&a, &ab, tree_node_layout);
- cx_tree_link(&b, &ba, tree_node_layout);
- cx_tree_link(&c, &ca, tree_node_layout);
- cx_tree_link(&c, &cb, tree_node_layout);
- cx_tree_link(&c, &cc, tree_node_layout);
- cx_tree_link(&cb, &cba, tree_node_layout);
+ cx_tree_add(&root, &a, tree_node_layout);
+ cx_tree_add(&root, &b, tree_node_layout);
+ cx_tree_add(&root, &c, tree_node_layout);
+ cx_tree_add(&a, &aa, tree_node_layout);
+ cx_tree_add(&a, &ab, tree_node_layout);
+ cx_tree_add(&b, &ba, tree_node_layout);
+ cx_tree_add(&c, &ca, tree_node_layout);
+ cx_tree_add(&c, &cb, tree_node_layout);
+ cx_tree_add(&c, &cc, tree_node_layout);
+ cx_tree_add(&cb, &cba, tree_node_layout);
CX_TEST_DO {
- CxTreeVisitor iter = cx_tree_visitor(&root, tree_children(tree_node));
+ CxTreeIterator iter = cx_tree_visitor(&root, tree_children(tree_node));
unsigned chk = 0;
cx_foreach(tree_node*, node, iter) {
CX_TEST_ASSERT(node->data == 0);
@@ -1100,7 +1053,7 @@
tree_node root = {0};
CX_TEST_DO {
- CxTreeVisitor iter = cx_tree_visitor(&root, tree_children(tree_node));
+ CxTreeIterator iter = cx_tree_visitor(&root, tree_children(tree_node));
unsigned chk = 0;
cx_foreach(tree_node*, node, iter) {
CX_TEST_ASSERT(node == iter.node);
@@ -1124,12 +1077,12 @@
};
tree_node* actual_order[4];
- cx_tree_link(&root, &a, tree_node_layout);
- cx_tree_link(&a, &b, tree_node_layout);
- cx_tree_link(&b, &c, tree_node_layout);
+ cx_tree_add(&root, &a, tree_node_layout);
+ cx_tree_add(&a, &b, tree_node_layout);
+ cx_tree_add(&b, &c, tree_node_layout);
CX_TEST_DO {
- CxTreeVisitor iter = cx_tree_visitor(&root, tree_children(tree_node));
+ CxTreeIterator iter = cx_tree_visitor(&root, tree_children(tree_node));
unsigned chk = 0;
cx_foreach(tree_node*, node, iter) {
CX_TEST_ASSERT(node == iter.node);
@@ -1164,16 +1117,16 @@
};
tree_node* actual_order[5];
- cx_tree_link(&root, &a, tree_node_layout);
- cx_tree_link(&root, &b, tree_node_layout);
- cx_tree_link(&root, &c, tree_node_layout);
- cx_tree_link(&b, &ba, tree_node_layout);
- cx_tree_link(&b, &bb, tree_node_layout);
- cx_tree_link(&b, &bc, tree_node_layout);
- cx_tree_link(&bb, &bba, tree_node_layout);
+ cx_tree_add(&root, &a, tree_node_layout);
+ cx_tree_add(&root, &b, tree_node_layout);
+ cx_tree_add(&root, &c, tree_node_layout);
+ cx_tree_add(&b, &ba, tree_node_layout);
+ cx_tree_add(&b, &bb, tree_node_layout);
+ cx_tree_add(&b, &bc, tree_node_layout);
+ cx_tree_add(&bb, &bba, tree_node_layout);
CX_TEST_DO {
- CxTreeVisitor iter = cx_tree_visitor(&b, tree_children(tree_node));
+ CxTreeIterator iter = cx_tree_visitor(&b, tree_children(tree_node));
unsigned chk = 0;
cx_foreach(tree_node*, node, iter) {
CX_TEST_ASSERT(node == iter.node);
@@ -1213,18 +1166,18 @@
};
tree_node* actual_order[16]; // reserve more space in case s.t. goes wrong
- cx_tree_link(&root, &a, tree_node_layout);
- cx_tree_link(&root, &b, tree_node_layout);
- cx_tree_link(&root, &c, tree_node_layout);
- cx_tree_link(&a, &aa, tree_node_layout);
- cx_tree_link(&a, &ab, tree_node_layout);
- cx_tree_link(&b, &ba, tree_node_layout);
- cx_tree_link(&c, &ca, tree_node_layout);
- cx_tree_link(&c, &cb, tree_node_layout);
- cx_tree_link(&c, &cc, tree_node_layout);
- cx_tree_link(&cb, &cba, tree_node_layout);
+ cx_tree_add(&root, &a, tree_node_layout);
+ cx_tree_add(&root, &b, tree_node_layout);
+ cx_tree_add(&root, &c, tree_node_layout);
+ cx_tree_add(&a, &aa, tree_node_layout);
+ cx_tree_add(&a, &ab, tree_node_layout);
+ cx_tree_add(&b, &ba, tree_node_layout);
+ cx_tree_add(&c, &ca, tree_node_layout);
+ cx_tree_add(&c, &cb, tree_node_layout);
+ cx_tree_add(&c, &cc, tree_node_layout);
+ cx_tree_add(&cb, &cba, tree_node_layout);
CX_TEST_DO {
- CxTreeVisitor iter = cx_tree_visitor(&root, tree_children(tree_node));
+ CxTreeIterator iter = cx_tree_visitor(&root, tree_children(tree_node));
unsigned chk = 0;
cx_foreach(tree_node*, node, iter) {
CX_TEST_ASSERT(node->data == 0);
@@ -1240,7 +1193,7 @@
CX_TEST_ASSERT(iter.depth == 3);
}
if (node == &c) {
- cxTreeVisitorContinue(iter);
+ cxTreeIteratorContinue(iter);
}
}
CX_TEST_ASSERT(iter.counter == 7);
@@ -1279,16 +1232,16 @@
};
tree_node* actual_order[16]; // reserve more space in case s.t. goes wrong
- cx_tree_link(&root, &a, tree_node_layout);
- cx_tree_link(&root, &b, tree_node_layout);
- cx_tree_link(&root, &c, tree_node_layout);
- cx_tree_link(&a, &aa, tree_node_layout);
- cx_tree_link(&a, &ab, tree_node_layout);
- cx_tree_link(&b, &ba, tree_node_layout);
- cx_tree_link(&c, &ca, tree_node_layout);
- cx_tree_link(&c, &cb, tree_node_layout);
- cx_tree_link(&c, &cc, tree_node_layout);
- cx_tree_link(&cb, &cba, tree_node_layout);
+ cx_tree_add(&root, &a, tree_node_layout);
+ cx_tree_add(&root, &b, tree_node_layout);
+ cx_tree_add(&root, &c, tree_node_layout);
+ cx_tree_add(&a, &aa, tree_node_layout);
+ cx_tree_add(&a, &ab, tree_node_layout);
+ cx_tree_add(&b, &ba, tree_node_layout);
+ cx_tree_add(&c, &ca, tree_node_layout);
+ cx_tree_add(&c, &cb, tree_node_layout);
+ cx_tree_add(&c, &cc, tree_node_layout);
+ cx_tree_add(&cb, &cba, tree_node_layout);
CX_TEST_DO {
CxTreeIterator iter = cx_tree_iterator(&root, false, tree_children(tree_node));
unsigned chk = 0;
@@ -1337,16 +1290,16 @@
tree_node cc = {0};
tree_node cba = {0};
- cx_tree_link(&root, &a, tree_node_layout);
- cx_tree_link(&root, &b, tree_node_layout);
- cx_tree_link(&root, &c, tree_node_layout);
- cx_tree_link(&a, &aa, tree_node_layout);
- cx_tree_link(&a, &ab, tree_node_layout);
- cx_tree_link(&b, &ba, tree_node_layout);
- cx_tree_link(&c, &ca, tree_node_layout);
- cx_tree_link(&c, &cb, tree_node_layout);
- cx_tree_link(&c, &cc, tree_node_layout);
- cx_tree_link(&cb, &cba, tree_node_layout);
+ cx_tree_add(&root, &a, tree_node_layout);
+ cx_tree_add(&root, &b, tree_node_layout);
+ cx_tree_add(&root, &c, tree_node_layout);
+ cx_tree_add(&a, &aa, tree_node_layout);
+ cx_tree_add(&a, &ab, tree_node_layout);
+ cx_tree_add(&b, &ba, tree_node_layout);
+ cx_tree_add(&c, &ca, tree_node_layout);
+ cx_tree_add(&c, &cb, tree_node_layout);
+ cx_tree_add(&c, &cc, tree_node_layout);
+ cx_tree_add(&cb, &cba, tree_node_layout);
CX_TEST_DO {
CxTreeIterator iter = cx_tree_iterator(&root, true, tree_children(tree_node));
unsigned chk = 0;
@@ -1383,520 +1336,25 @@
}
}
-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,
- tree_node_file_create, alloc,
- (void **) &foo, &root,
- tree_node_file_layout
- );
- CX_TEST_ASSERT(result == 0);
- CX_TEST_ASSERT(foo != NULL);
- const char *bar_path = "/home/foo/bar/";
- void *failed;
- size_t added = cx_tree_add_array(
- bar_path, 1, sizeof(const char *),
- tree_node_file_search,
- tree_node_file_create, 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,
- tree_node_file_create, 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,
- tree_node_file_create, 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,
- tree_node_file_create, 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);
- cxFreeDefault(node);
- node = NULL;
- size_t added = cx_tree_add_array(
- "/", 1, sizeof(const char *),
- tree_node_file_search,
- tree_node_file_create, 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);
- cxFreeDefault(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,
- tree_node_file_create, 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);
- cxFreeDefault(node);
- }
-}
-
-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,
- tree_node_file_create, 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),
- 10, // deliberately specify more than the iter has
- tree_node_file_search,
- tree_node_file_create, 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;
-
- const char *paths[] = {
- "/home/foo/",
- "/home/foo/bar",
- "/usr/lib64/",
- "/usr/lib/foo.so"
- };
-
- size_t processed = cx_tree_add_array(
- paths, 4, sizeof(const char *),
- tree_node_file_search,
- tree_node_file_create, 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_but_not_all) {
- 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;
-
- const char *paths[] = {
- "/home/foo/",
- "/home/foo/bar",
- "/usr/lib64/",
- "/usr/lib/foo.so"
- };
- // create iterator for 4 elements, but choose to insert only 3 of them
- CxIterator iter = cxIterator(paths, sizeof(const char*), 4);
- size_t processed = cx_tree_add_iter(
- cxIteratorRef(iter), 3,
- tree_node_file_search,
- tree_node_file_create, alloc,
- &failed, &root, tree_node_file_layout
- );
-
- CX_TEST_ASSERT(cxIteratorValid(iter));
- CX_TEST_ASSERT(cxIteratorCurrent(iter) == &paths[3]);
-
- CX_TEST_ASSERT(failed == NULL);
- CX_TEST_ASSERT(processed == 3);
- 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);
- 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);
-
- cxFree(alloc, foo);
- cxFree(alloc, bar);
- cxFree(alloc, lib64);
-
- 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;
-
- const char *paths[] = {
- "/mnt/sdcard/",
- "/mnt/foo/",
- "/mnt/sdcard/",
- "/home/",
- "/usr/"
- };
-
- size_t processed = cx_tree_add_array(
- paths, 5, sizeof(const char *),
- tree_node_file_search,
- tree_node_file_create, 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, const char **paths) {
- tree_node_file root = {0};
- root.path = "/";
-
- void *failed;
- size_t processed = cx_tree_add_array(
- paths, 10, sizeof(const char *),
- tree_node_file_search,
- tree_node_file_create, alloc,
- &failed, &root, tree_node_file_layout
- );
-
- CX_TEST_ASSERT(failed == NULL);
- CX_TEST_ASSERT(processed == 10);
-
- const char *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 {
- const char *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/"
- };
-
- const char *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);
-}
-
CX_TEST(test_tree_high_create) {
CxTestingAllocator talloc;
cx_testing_allocator_init(&talloc);
CX_TEST_DO {
CxTree *tree = cxTreeCreate(
&talloc.base,
- tree_node_file_create_hl,
- tree_node_file_search,
- tree_node_file_search_data,
- tree_node_file_layout
+ sizeof(tree_node_file),
+ CX_STORE_POINTERS,
+ NULL, offsetof(tree_node_file, path),
+ cx_tree_node_layout(tree_node_file)
);
- CX_TEST_ASSERT(tree->cl != NULL);
CX_TEST_ASSERT(tree->collection.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->node_size == sizeof(tree_node_file));
+ CX_TEST_ASSERT(tree->collection.elem_size == sizeof(void*));
CX_TEST_ASSERT(tree->collection.size == 0);
CX_TEST_ASSERT(tree->collection.simple_destructor == NULL);
CX_TEST_ASSERT(tree->collection.advanced_destructor == (cx_destructor_func2) cxFree);
CX_TEST_ASSERT(tree->collection.destructor_data == &talloc.base);
- CX_TEST_ASSERT(tree->collection.store_pointer == false);
+ CX_TEST_ASSERT(tree->collection.store_pointer == true);
CX_TEST_ASSERT(tree->collection.sorted == false);
CX_TEST_ASSERT(tree->root == NULL);
CX_TEST_ASSERT(tree->loc_parent == offsetof(tree_node_file, parent));
@@ -1904,6 +1362,7 @@
CX_TEST_ASSERT(tree->loc_last_child == offsetof(tree_node_file, last_child));
CX_TEST_ASSERT(tree->loc_prev == offsetof(tree_node_file, prev));
CX_TEST_ASSERT(tree->loc_next == offsetof(tree_node_file, next));
+ CX_TEST_ASSERT(tree->loc_data == offsetof(tree_node_file, path));
CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc));
CX_TEST_ASSERT(talloc.alloc_total == 1);
@@ -1914,65 +1373,13 @@
cx_testing_allocator_destroy(&talloc);
}
-CX_TEST(test_tree_high_create_simple) {
- CX_TEST_DO {
- CxTree *tree = cxTreeCreateSimple(
- NULL, // shall fall back to the default allocator
- tree_node_file_create_hl,
- tree_node_file_search,
- tree_node_file_search_data
- );
- CX_TEST_ASSERT(tree->cl != NULL);
- CX_TEST_ASSERT(tree->collection.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->collection.size == 0);
- CX_TEST_ASSERT(tree->collection.simple_destructor == NULL);
- CX_TEST_ASSERT(tree->collection.advanced_destructor == (cx_destructor_func2) cxFree);
- CX_TEST_ASSERT(tree->collection.destructor_data == cxDefaultAllocator);
- CX_TEST_ASSERT(tree->root == NULL);
- CX_TEST_ASSERT(tree->loc_parent == offsetof(struct cx_tree_node_base_s, parent));
- CX_TEST_ASSERT(tree->loc_children == offsetof(struct cx_tree_node_base_s, children));
- CX_TEST_ASSERT(tree->loc_last_child == offsetof(struct cx_tree_node_base_s, last_child));
- CX_TEST_ASSERT(tree->loc_prev == offsetof(struct cx_tree_node_base_s, prev));
- CX_TEST_ASSERT(tree->loc_next == offsetof(struct cx_tree_node_base_s, next));
- cxTreeFree(tree);
- }
-}
-
-CX_TEST(test_tree_high_create_wrapped) {
- 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);
- CX_TEST_DO {
- CxTree *tree = cxTreeCreateWrapped(NULL, &root, tree_node_layout);
- CX_TEST_ASSERT(tree->cl != NULL);
- CX_TEST_ASSERT(tree->collection.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->collection.size == 4);
- CX_TEST_ASSERT(tree->collection.simple_destructor == NULL);
- CX_TEST_ASSERT(tree->collection.advanced_destructor == NULL);
- CX_TEST_ASSERT(tree->collection.destructor_data == NULL);
- CX_TEST_ASSERT(tree->loc_parent == offsetof(tree_node, parent));
- CX_TEST_ASSERT(tree->loc_children == offsetof(tree_node, children));
- CX_TEST_ASSERT(tree->loc_last_child == -1);
- CX_TEST_ASSERT(tree->loc_prev == offsetof(tree_node, prev));
- CX_TEST_ASSERT(tree->loc_next == offsetof(tree_node, next));
- cxTreeFree(tree);
- }
-}
-
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(cxDefaultAllocator, &root, tree_node_layout);
+ cx_tree_add(&root, &child1, tree_node_layout);
+ cx_tree_add(&root, &child2, tree_node_layout);
+ cx_tree_add(&child1, &child3, tree_node_layout);
+ CxTree *tree = cxTreeCreate(cxDefaultAllocator, sizeof(tree_node),
+ sizeof(int), &root, offsetof(tree_node, data), tree_node_layout);
CX_TEST_DO {
CX_TEST_ASSERT(cxTreeDepth(tree) == 3);
CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &root) == 3);
@@ -1980,13 +1387,8 @@
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
- );
+ CxTree *empty = cxTreeCreate(cxDefaultAllocator, sizeof(tree_node),
+ sizeof(int), NULL, offsetof(tree_node, data), tree_node_layout);
CX_TEST_ASSERT(cxTreeDepth(empty) == 0);
cxTreeFree(empty);
}
@@ -1995,7 +1397,8 @@
CX_TEST(test_tree_high_set_parent) {
tree_node root = {0}, child1 = {0}, child2 = {0}, child3 = {0};
- CxTree *tree = cxTreeCreateWrapped(cxDefaultAllocator, &root, tree_node_layout);
+ CxTree *tree = cxTreeCreate(cxDefaultAllocator, sizeof(tree_node),
+ sizeof(int), &root, offsetof(tree_node, data), tree_node_layout);
CX_TEST_DO {
cxTreeSetParent(tree, &root, &child1);
cxTreeSetParent(tree, &root, &child2);
@@ -2012,85 +1415,14 @@
CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child2) == 2);
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
- );
+ CxTree *empty = cxTreeCreate(cxDefaultAllocator, sizeof(tree_node),
+ sizeof(int), NULL, offsetof(tree_node, data), tree_node_layout);
CX_TEST_ASSERT(cxTreeDepth(empty) == 0);
cxTreeFree(empty);
}
cxTreeFree(tree);
}
-CX_TEST(test_tree_high_insert_one) {
- 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
- );
-
- int result = 0;
- result |= cxTreeInsert(tree, "/");
- result |= cxTreeInsert(tree, "/usr/");
- result |= cxTreeInsert(tree, "/home/");
- result |= cxTreeInsert(tree, "/usr/lib/");
- result |= cxTreeInsert(tree, "/home/foo/");
- CX_TEST_ASSERT(result == 0);
- CX_TEST_ASSERT(1 == cxTreeInsertArray(tree, "/home/foo/bar/", sizeof(const char*), 1));
- CX_TEST_ASSERT(cxTreeSize(tree) == 6);
- CX_TEST_ASSERT(0 != cxTreeInsert(tree, "newroot"));
- CX_TEST_ASSERT(cxTreeSize(tree) == 6);
-
- CX_TEST_ASSERT(talloc.alloc_total == 8);
- CX_TEST_ASSERT(talloc.free_total == 1); // the one that could not be added
-
- cxTreeFree(tree);
- CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
- }
- cx_testing_allocator_destroy(&talloc);
-}
-
-CX_TEST(test_tree_high_insert_many) {
- 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/",
- "newroot"
- };
- CX_TEST_ASSERT(6 == cxTreeInsertArray(tree, paths, sizeof(const char*), 7));
- CX_TEST_ASSERT(cxTreeSize(tree) == 6);
-
- CX_TEST_ASSERT(talloc.alloc_total == 8);
- CX_TEST_ASSERT(talloc.free_total == 1); // the one that could not be added
-
- cxTreeFree(tree);
- CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
- }
- cx_testing_allocator_destroy(&talloc);
-}
-
static void test_tree_remove_node_relink_mock(
void *node,
CX_UNUSED const void *oldp,
@@ -2105,167 +1437,182 @@
}
}
+static CX_TEST_SUBROUTINE(validate_tree_high_add_find_remove_nodes,
+ CxAllocator *alloc, bool use_dfs) {
+ CxTree *tree = cxTreeCreate(alloc,
+ sizeof(tree_node_file),
+ CX_STORE_POINTERS,
+ NULL, offsetof(tree_node_file, path),
+ cx_tree_node_layout(tree_node_file)
+ );
+ cxSetCompareFunc(tree, strcmp);
+
+ {
+ tree_node_file *root = cxTreeCreateRootData(tree, "/");
+ tree_node_file *home = cxTreeAddData(tree, root, "/home/");
+ tree_node_file *foo = cxTreeAddData(tree, home, "/home/foo/");
+ cxTreeAddData(tree, foo, "/home/foo/bar/");
+ tree_node_file *usr = cxTreeAddData(tree, root, "/usr/");
+ cxTreeAddData(tree, usr, "/usr/lib/");
+ }
+
+ tree_node_file *foo = cxTreeFind(tree, "/home/foo/", use_dfs);
+ 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(cxTreeSize(tree) == 6);
+
+ CX_TEST_ASSERT(NULL != cxTreeAddData(tree, foo->parent, "/home/baz/"));
+ tree_node_file *baz = cxTreeFind(tree, "/home/baz/", use_dfs);
+ 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(cxTreeSize(tree) == 7);
+
+ tree_node_file *home = cxTreeFind(tree, "/home/", use_dfs);
+ CX_TEST_ASSERT(NULL == cxTreeFindInSubtree(tree, "/usr/", foo, 0, use_dfs));
+ tree_node_file *bar = cxTreeFindInSubtree(tree, "/home/foo/bar/", home, 0, use_dfs);
+ 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/";
+ tree_node_file *usr = cxTreeFind(tree, "/usr/", use_dfs);
+ cxTreeAddNode(tree, usr, share);
+ CX_TEST_ASSERT(cxTreeSize(tree) == 8);
+
+ cxTreeRemoveSubtree(tree, foo);
+ CX_TEST_ASSERT(cxTreeSize(tree) == 6);
+ CX_TEST_ASSERT(foo->children == bar);
+ CX_TEST_ASSERT(foo->last_child == bar);
+ CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/foo/", use_dfs));
+ CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/foo/bar/", use_dfs));
+ CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/bar/", use_dfs));
+
+ CX_TEST_ASSERT(0 == cxTreeRemoveNode(tree, usr, test_tree_remove_node_relink_mock));
+ CX_TEST_ASSERT(cxTreeSize(tree) == 5);
+ CX_TEST_ASSERT(usr->parent == NULL);
+ CX_TEST_ASSERT(usr->children == NULL);
+ CX_TEST_ASSERT(usr->last_child == NULL);
+ CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/", use_dfs));
+ CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/lib/", use_dfs));
+ CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/share/", use_dfs));
+ tree_node_file *relinked_share = cxTreeFind(tree, "/share/", use_dfs);
+ tree_node_file *relinked_lib = cxTreeFind(tree, "/lib/", use_dfs);
+ CX_TEST_ASSERT(relinked_share != NULL);
+ CX_TEST_ASSERT(relinked_share->parent == tree->root);
+ CX_TEST_ASSERT(relinked_lib != NULL);
+ CX_TEST_ASSERT(relinked_lib->parent == tree->root);
+ CX_TEST_ASSERT(NULL != cxTreeFind(tree, "/home/", use_dfs));
+ cxTreeFree(tree);
+
+ // we are not done yet, because we need to free the removed stuff
+ cxFree(alloc, usr);
+ // for the subtree, we use a little trick and wrap it in a new tree
+ CxTree *foo_tree = cxTreeCreate(alloc,
+ sizeof(tree_node_file),
+ CX_STORE_POINTERS,
+ foo, offsetof(tree_node_file, path),
+ cx_tree_node_layout(tree_node_file)
+ );
+ cxSetAdvancedDestructor(foo_tree, cxFree, alloc);
+ cxTreeFree(foo_tree);
+}
+
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(cxTreeSize(tree) == 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(cxTreeSize(tree) == 7);
-
- tree_node_file *home = cxTreeFind(tree, "/home/");
- CX_TEST_ASSERT(NULL == cxTreeFindInSubtree(tree, "/usr/", foo, 0));
- tree_node_file *bar = cxTreeFindInSubtree(tree, "/home/foo/bar/", home, 0);
- 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/";
- tree_node_file *usr = cxTreeFind(tree, "/usr/");
- cxTreeAddChildNode(tree, usr, share);
- CX_TEST_ASSERT(cxTreeSize(tree) == 8);
-
- cxTreeRemoveSubtree(tree, foo);
- CX_TEST_ASSERT(cxTreeSize(tree) == 6);
- CX_TEST_ASSERT(foo->children == bar);
- CX_TEST_ASSERT(foo->last_child == bar);
- 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(0 == cxTreeRemoveNode(tree, usr, test_tree_remove_node_relink_mock));
- CX_TEST_ASSERT(cxTreeSize(tree) == 5);
- CX_TEST_ASSERT(usr->parent == NULL);
- CX_TEST_ASSERT(usr->children == NULL);
- CX_TEST_ASSERT(usr->last_child == NULL);
- CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/"));
- CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/lib/"));
- CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/share/"));
- tree_node_file *relinked_share = cxTreeFind(tree, "/share/");
- tree_node_file *relinked_lib = cxTreeFind(tree, "/lib/");
- CX_TEST_ASSERT(relinked_share != NULL);
- CX_TEST_ASSERT(relinked_share->parent == tree->root);
- CX_TEST_ASSERT(relinked_lib != NULL);
- CX_TEST_ASSERT(relinked_lib->parent == tree->root);
- CX_TEST_ASSERT(NULL != cxTreeFind(tree, "/home/"));
-
-
- cxTreeFree(tree);
- // we are not done yet, because we need to free the removed stuff
- CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc));
-
- cxFree(alloc, usr);
- // for the subtree, we use a little trick and wrap it in a new tree
- CxTree *foo_tree = cxTreeCreateWrapped(alloc, foo, tree_node_file_layout);
- foo_tree->collection.allocator = alloc;
- cxSetAdvancedDestructor(foo_tree, cxFree, alloc);
- cxTreeFree(foo_tree);
+ CX_TEST_CALL_SUBROUTINE(validate_tree_high_add_find_remove_nodes, alloc, true);
+ CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
+ CX_TEST_CALL_SUBROUTINE(validate_tree_high_add_find_remove_nodes, alloc, false);
CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
}
cx_testing_allocator_destroy(&talloc);
}
+static CX_TEST_SUBROUTINE(validate_tree_high_add_find_destroy_nodes,
+ CxAllocator *alloc, bool use_dfs) {
+ CxTree *tree = cxTreeCreate(alloc,
+ sizeof(tree_node_file),
+ CX_STORE_POINTERS,
+ NULL, offsetof(tree_node_file, path),
+ cx_tree_node_layout(tree_node_file)
+ );
+ cxSetCompareFunc(tree, strcmp);
+
+ {
+ tree_node_file *root = cxTreeCreateRootData(tree, "/");
+ tree_node_file *home = cxTreeAddData(tree, root, "/home/");
+ tree_node_file *foo = cxTreeAddData(tree, home, "/home/foo/");
+ cxTreeAddData(tree, foo, "/home/foo/bar/");
+ tree_node_file *usr = cxTreeAddData(tree, root, "/usr/");
+ cxTreeAddData(tree, usr, "/usr/lib/");
+ }
+
+ tree_node_file *foo = cxTreeFind(tree, "/home/foo/", use_dfs);
+ 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(cxTreeSize(tree) == 6);
+
+ CX_TEST_ASSERT(NULL != cxTreeAddData(tree, foo->parent, "/home/baz/"));
+ tree_node_file *baz = cxTreeFind(tree, "/home/baz/", use_dfs);
+ 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(cxTreeSize(tree) == 7);
+
+ tree_node_file *home = cxTreeFind(tree, "/home/", use_dfs);
+ CX_TEST_ASSERT(NULL == cxTreeFindInSubtree(tree, "/usr/", foo, 0, use_dfs));
+ tree_node_file *bar = cxTreeFindInSubtree(tree, "/home/foo/bar/", home, 0, use_dfs);
+ 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/";
+ tree_node_file *usr = cxTreeFind(tree, "/usr/", use_dfs);
+ cxTreeAddNode(tree, usr, share);
+ CX_TEST_ASSERT(cxTreeSize(tree) == 8);
+
+ cxTreeDestroySubtree(tree, foo);
+ CX_TEST_ASSERT(cxTreeSize(tree) == 6);
+ CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/foo/", use_dfs));
+ CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/foo/bar/", use_dfs));
+ CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/bar/", use_dfs));
+
+ CX_TEST_ASSERT(0 == cxTreeDestroyNode(tree, usr, test_tree_remove_node_relink_mock));
+ CX_TEST_ASSERT(cxTreeSize(tree) == 5);
+ CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/", use_dfs));
+ CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/lib/", use_dfs));
+ CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/share/", use_dfs));
+ tree_node_file *relinked_share = cxTreeFind(tree, "/share/", use_dfs);
+ tree_node_file *relinked_lib = cxTreeFind(tree, "/lib/", use_dfs);
+ CX_TEST_ASSERT(relinked_share != NULL);
+ CX_TEST_ASSERT(relinked_share->parent == tree->root);
+ CX_TEST_ASSERT(relinked_lib != NULL);
+ CX_TEST_ASSERT(relinked_lib->parent == tree->root);
+ CX_TEST_ASSERT(NULL != cxTreeFind(tree, "/home/", use_dfs));
+
+ cxTreeFree(tree);
+}
+
CX_TEST(test_tree_high_add_find_destroy_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(cxTreeSize(tree) == 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(cxTreeSize(tree) == 7);
-
- tree_node_file *home = cxTreeFind(tree, "/home/");
- CX_TEST_ASSERT(NULL == cxTreeFindInSubtree(tree, "/usr/", foo, 0));
- tree_node_file *bar = cxTreeFindInSubtree(tree, "/home/foo/bar/", home, 0);
- 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/";
- tree_node_file *usr = cxTreeFind(tree, "/usr/");
- cxTreeAddChildNode(tree, usr, share);
- CX_TEST_ASSERT(cxTreeSize(tree) == 8);
-
- cxTreeDestroySubtree(tree, foo);
- CX_TEST_ASSERT(cxTreeSize(tree) == 6);
- 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(0 == cxTreeDestroyNode(tree, usr, test_tree_remove_node_relink_mock));
- CX_TEST_ASSERT(cxTreeSize(tree) == 5);
- CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/"));
- CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/lib/"));
- CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/share/"));
- tree_node_file *relinked_share = cxTreeFind(tree, "/share/");
- tree_node_file *relinked_lib = cxTreeFind(tree, "/lib/");
- CX_TEST_ASSERT(relinked_share != NULL);
- CX_TEST_ASSERT(relinked_share->parent == tree->root);
- CX_TEST_ASSERT(relinked_lib != NULL);
- CX_TEST_ASSERT(relinked_lib->parent == tree->root);
- CX_TEST_ASSERT(NULL != cxTreeFind(tree, "/home/"));
-
- cxTreeFree(tree);
- // all memory should be free when using destroy instead of remove
+ CX_TEST_CALL_SUBROUTINE(validate_tree_high_add_find_destroy_nodes, alloc, true);
+ CX_TEST_CALL_SUBROUTINE(validate_tree_high_add_find_destroy_nodes, alloc, false);
CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
}
cx_testing_allocator_destroy(&talloc);
@@ -2277,21 +1624,21 @@
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
+ CxTree *tree = cxTreeCreate(alloc,
+ sizeof(tree_node_file),
+ CX_STORE_POINTERS,
+ NULL, offsetof(tree_node_file, path),
+ cx_tree_node_layout(tree_node_file)
);
- const char *paths[] = {
- "/",
- "/usr/",
- "/home/",
- "/usr/lib/",
- "/home/foo/",
- "/home/foo/bar/"
- };
- cxTreeInsertArray(tree, paths, sizeof(const char*), 6);
+ {
+ tree_node_file *root = cxTreeCreateRootData(tree, "/");
+ tree_node_file *home = cxTreeAddData(tree, root, "/home/");
+ tree_node_file *foo = cxTreeAddData(tree, home, "/home/foo/");
+ cxTreeAddData(tree, foo, "/home/foo/bar/");
+ tree_node_file *usr = cxTreeAddData(tree, root, "/usr/");
+ cxTreeAddData(tree, usr, "/usr/lib/");
+ }
void *root = tree->root;
CX_TEST_ASSERT(0 != cxTreeRemoveNode(tree, root, NULL));
CX_TEST_ASSERT(tree->root == root);
@@ -2305,7 +1652,13 @@
CX_TEST_ASSERT(cxTreeDepth(tree) == 0);
cxTreeFree(tree);
CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc));
- CxTree *w = cxTreeCreateWrapped(alloc, root, tree_node_file_layout);
+
+ CxTree *w = cxTreeCreate(alloc,
+ sizeof(tree_node_file),
+ CX_STORE_POINTERS,
+ root, offsetof(tree_node_file, path),
+ cx_tree_node_layout(tree_node_file)
+ );
cxSetAdvancedDestructor(w, cxFree, alloc);
cxTreeDestroySubtree(w, w->root);
CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc));
@@ -2321,11 +1674,12 @@
CX_TEST(test_tree_high_simple_destructor) {
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);
+ cx_tree_add(&root, &child1, tree_node_layout);
+ cx_tree_add(&root, &child2, tree_node_layout);
+ cx_tree_add(&child1, &child3, tree_node_layout);
CX_TEST_DO {
- CxTree *tree = cxTreeCreateWrapped(cxDefaultAllocator, &root, tree_node_layout);
+ CxTree *tree = cxTreeCreate(cxDefaultAllocator, sizeof(tree_node),
+ sizeof(int), &root, offsetof(tree_node, data), tree_node_layout);
cxSetDestructor(tree,test_tree_high_simple_destructor_func);
cxTreeDestroyNode(tree, &child1, NULL);
cxTreeFree(tree);
@@ -2337,20 +1691,23 @@
}
CX_TEST(test_tree_high_iterator) {
- CxTree *tree = cxTreeCreate(
- NULL, tree_node_file_create_hl,
- tree_node_file_search, tree_node_file_search_data,
- tree_node_file_layout
+ CxTree *tree = cxTreeCreate(NULL,
+ sizeof(tree_node_file),
+ CX_STORE_POINTERS,
+ NULL, offsetof(tree_node_file, path),
+ cx_tree_node_layout(tree_node_file)
);
- cxTreeInsert(tree, "/");
- cxTreeInsert(tree, "/etc");
- cxTreeInsert(tree, "/home");
- cxTreeInsert(tree, "/home/jane");
- cxTreeInsert(tree, "/usr");
- cxTreeInsert(tree, "/usr/local");
- cxTreeInsert(tree, "/usr/local/lib");
- cxTreeInsert(tree, "/var");
- cxTreeInsert(tree, "/var/lib");
+ {
+ tree_node_file *root = cxTreeCreateRootData(tree, "/");
+ cxTreeAddData(tree, root, "/etc");
+ tree_node_file *home = cxTreeAddData(tree, root, "/home");
+ cxTreeAddData(tree, home, "/home/jane");
+ tree_node_file *usr = cxTreeAddData(tree, root, "/usr");
+ cxTreeAddData(tree, usr, "/usr/local");
+ cxTreeAddData(tree, usr, "/usr/local/lib");
+ tree_node_file *var = cxTreeAddData(tree, root, "/var");
+ cxTreeAddData(tree, var, "/var/lib");
+ }
CX_TEST_DO {
const char *expected_order[] = {
"/",
@@ -2377,20 +1734,23 @@
}
CX_TEST(test_tree_high_visitor) {
- CxTree *tree = cxTreeCreate(
- NULL, tree_node_file_create_hl,
- tree_node_file_search, tree_node_file_search_data,
- tree_node_file_layout
+ CxTree *tree = cxTreeCreate(NULL,
+ sizeof(tree_node_file),
+ CX_STORE_POINTERS,
+ NULL, offsetof(tree_node_file, path),
+ cx_tree_node_layout(tree_node_file)
);
- cxTreeInsert(tree, "/");
- cxTreeInsert(tree, "/etc");
- cxTreeInsert(tree, "/home");
- cxTreeInsert(tree, "/home/jane");
- cxTreeInsert(tree, "/usr");
- cxTreeInsert(tree, "/usr/local");
- cxTreeInsert(tree, "/usr/local/lib");
- cxTreeInsert(tree, "/var");
- cxTreeInsert(tree, "/var/lib");
+ {
+ tree_node_file *root = cxTreeCreateRootData(tree, "/");
+ cxTreeAddData(tree, root, "/etc");
+ tree_node_file *home = cxTreeAddData(tree, root, "/home");
+ cxTreeAddData(tree, home, "/home/jane");
+ tree_node_file *usr = cxTreeAddData(tree, root, "/usr");
+ tree_node_file *usr_local = cxTreeAddData(tree, usr, "/usr/local");
+ cxTreeAddData(tree, usr_local, "/usr/local/lib");
+ tree_node_file *var = cxTreeAddData(tree, root, "/var");
+ cxTreeAddData(tree, var, "/var/lib");
+ }
CX_TEST_DO {
const char *expected_order[] = {
"/",
@@ -2404,7 +1764,7 @@
"/usr/local/lib",
};
const char *actual_order[9];
- CxTreeVisitor iter = cxTreeVisit(tree);
+ CxTreeIterator iter = cxTreeVisit(tree);
cx_foreach(tree_node_file*, p, iter) {
actual_order[iter.counter-1] = p->path;
}
@@ -2419,11 +1779,10 @@
CxTestSuite *cx_test_suite_tree_low_level(void) {
CxTestSuite *suite = cx_test_suite_new("tree (low level)");
- cx_test_register(suite, test_tree_link_new_child);
- cx_test_register(suite, test_tree_link_add_child);
- cx_test_register(suite, test_tree_link_move_to_other_parent);
- cx_test_register(suite, test_tree_unlink);
- cx_test_register(suite, test_tree_unlink_no_prev);
+ cx_test_register(suite, test_tree_add);
+ cx_test_register(suite, test_tree_add_move_to_other_parent);
+ cx_test_register(suite, test_tree_remove);
+ cx_test_register(suite, test_tree_remove_no_prev);
cx_test_register(suite, test_tree2_link_new_child);
cx_test_register(suite, test_tree2_link_add_child);
cx_test_register(suite, test_tree2_link_move_to_other_parent);
@@ -2445,15 +1804,6 @@
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_but_not_all);
- 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;
}
@@ -2462,18 +1812,14 @@
CxTestSuite *suite = cx_test_suite_new("tree (high level)");
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_tree_depth);
- cx_test_register(suite, test_tree_high_set_parent);
- 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);
- cx_test_register(suite, test_tree_high_add_find_destroy_nodes);
- cx_test_register(suite, test_tree_high_remove_or_destroy_root);
- cx_test_register(suite, test_tree_high_simple_destructor);
- cx_test_register(suite, test_tree_high_iterator);
- cx_test_register(suite, test_tree_high_visitor);
+ // cx_test_register(suite, test_tree_high_set_parent);
+ // cx_test_register(suite, test_tree_high_add_find_remove_nodes);
+ // cx_test_register(suite, test_tree_high_add_find_destroy_nodes);
+ // cx_test_register(suite, test_tree_high_remove_or_destroy_root);
+ // cx_test_register(suite, test_tree_high_simple_destructor);
+ // cx_test_register(suite, test_tree_high_iterator);
+ // cx_test_register(suite, test_tree_high_visitor);
return suite;
}