--- a/tests/test_tree.c Sun Jul 07 14:20:28 2024 +0200
+++ b/tests/test_tree.c Sun Jul 07 14:56:44 2024 +0200
@@ -40,11 +40,24 @@
int data;
} tree_node;
+typedef struct tree_node2 {
+ struct tree_node2 *parent;
+ struct tree_node2 *next;
+ struct tree_node2 *prev;
+ struct tree_node2 *children;
+ struct tree_node2 *last_child;
+ int data;
+} tree_node2;
+
#define tree_node_layout \
- offsetof(tree_node, parent), offsetof(tree_node, children), \
+ 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_child_list offsetof(tree_node, children),offsetof(tree_node, next)
+#define tree_children(type) offsetof(type, children), offsetof(type, next)
CX_TEST(test_tree_link_new_child) {
tree_node parent = {0};
@@ -76,7 +89,7 @@
CX_TEST_ASSERT(parent.next == NULL);
CX_TEST_ASSERT(parent.prev == NULL);
CX_TEST_ASSERT(parent.parent == NULL);
- CX_TEST_ASSERT(parent.children == &child3);
+ CX_TEST_ASSERT(parent.children == &child1);
CX_TEST_ASSERT(child1.parent == &parent);
CX_TEST_ASSERT(child2.parent == &parent);
@@ -85,12 +98,12 @@
CX_TEST_ASSERT(child2.children == NULL);
CX_TEST_ASSERT(child3.children == NULL);
- CX_TEST_ASSERT(child3.prev == NULL);
- CX_TEST_ASSERT(child3.next == &child2);
- CX_TEST_ASSERT(child2.prev == &child3);
- CX_TEST_ASSERT(child2.next == &child1);
- CX_TEST_ASSERT(child1.prev == &child2);
- CX_TEST_ASSERT(child1.next == NULL);
+ CX_TEST_ASSERT(child1.prev == NULL);
+ CX_TEST_ASSERT(child1.next == &child2);
+ CX_TEST_ASSERT(child2.prev == &child1);
+ CX_TEST_ASSERT(child2.next == &child3);
+ CX_TEST_ASSERT(child3.prev == &child2);
+ CX_TEST_ASSERT(child3.next == NULL);
}
}
@@ -109,7 +122,7 @@
CX_TEST_ASSERT(parent.next == NULL);
CX_TEST_ASSERT(parent.prev == NULL);
CX_TEST_ASSERT(parent.parent == NULL);
- CX_TEST_ASSERT(parent.children == &child3);
+ CX_TEST_ASSERT(parent.children == &child1);
CX_TEST_ASSERT(child1.parent == &parent);
CX_TEST_ASSERT(child2.parent == &child3);
@@ -118,10 +131,10 @@
CX_TEST_ASSERT(child2.children == NULL);
CX_TEST_ASSERT(child3.children == &child2);
- CX_TEST_ASSERT(child3.prev == NULL);
- CX_TEST_ASSERT(child3.next == &child1);
- CX_TEST_ASSERT(child1.prev == &child3);
- CX_TEST_ASSERT(child1.next == NULL);
+ CX_TEST_ASSERT(child1.prev == NULL);
+ CX_TEST_ASSERT(child1.next == &child3);
+ CX_TEST_ASSERT(child3.prev == &child1);
+ CX_TEST_ASSERT(child3.next == NULL);
CX_TEST_ASSERT(child2.prev == NULL);
CX_TEST_ASSERT(child2.next == NULL);
@@ -161,6 +174,155 @@
CX_TEST_ASSERT(child2.children == NULL);
CX_TEST_ASSERT(child2.prev == NULL);
CX_TEST_ASSERT(child2.next == NULL);
+
+ // unlink last child from parent
+ cx_tree_unlink(&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 == NULL);
+ CX_TEST_ASSERT(child1.parent == NULL);
+ }
+}
+
+CX_TEST(test_tree2_link_new_child) {
+ tree_node2 parent = {0};
+ tree_node2 child = {0};
+
+ CX_TEST_DO {
+ cx_tree_link(&parent, &child, tree_node2_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(parent.last_child == &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_ASSERT(child.last_child == NULL);
+ }
+}
+
+CX_TEST(test_tree2_link_add_child) {
+ tree_node2 parent = {0};
+ tree_node2 child1 = {0};
+ tree_node2 child2 = {0};
+ 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_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(parent.last_child == &child3);
+
+ CX_TEST_ASSERT(child1.parent == &parent);
+ CX_TEST_ASSERT(child2.parent == &parent);
+ CX_TEST_ASSERT(child3.parent == &parent);
+ CX_TEST_ASSERT(child1.children == NULL);
+ CX_TEST_ASSERT(child2.children == NULL);
+ CX_TEST_ASSERT(child3.children == NULL);
+ CX_TEST_ASSERT(child1.last_child == NULL);
+ CX_TEST_ASSERT(child2.last_child == NULL);
+ CX_TEST_ASSERT(child3.last_child == NULL);
+
+ CX_TEST_ASSERT(child1.prev == NULL);
+ CX_TEST_ASSERT(child1.next == &child2);
+ CX_TEST_ASSERT(child2.prev == &child1);
+ CX_TEST_ASSERT(child2.next == &child3);
+ CX_TEST_ASSERT(child3.prev == &child2);
+ CX_TEST_ASSERT(child3.next == NULL);
+ }
+}
+
+CX_TEST(test_tree2_link_move_to_other_parent) {
+ tree_node2 parent = {0};
+ 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_TEST_DO {
+ cx_tree_link(&child3, &child2, tree_node2_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(parent.last_child == &child3);
+
+ CX_TEST_ASSERT(child1.parent == &parent);
+ CX_TEST_ASSERT(child2.parent == &child3);
+ CX_TEST_ASSERT(child3.parent == &parent);
+ CX_TEST_ASSERT(child1.children == NULL);
+ CX_TEST_ASSERT(child2.children == NULL);
+ CX_TEST_ASSERT(child3.children == &child2);
+ CX_TEST_ASSERT(child1.last_child == NULL);
+ CX_TEST_ASSERT(child2.last_child == NULL);
+ CX_TEST_ASSERT(child3.last_child == &child2);
+
+ CX_TEST_ASSERT(child1.prev == NULL);
+ CX_TEST_ASSERT(child1.next == &child3);
+ CX_TEST_ASSERT(child3.prev == &child1);
+ CX_TEST_ASSERT(child3.next == NULL);
+
+ CX_TEST_ASSERT(child2.prev == NULL);
+ CX_TEST_ASSERT(child2.next == NULL);
+ }
+}
+
+CX_TEST(test_tree2_unlink) {
+ tree_node2 parent = {0};
+ 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_TEST_DO {
+ cx_tree_unlink(&child3, tree_node2_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(parent.last_child == &child1);
+
+ CX_TEST_ASSERT(child1.parent == &parent);
+ CX_TEST_ASSERT(child1.children == NULL);
+ CX_TEST_ASSERT(child1.last_child == NULL);
+ CX_TEST_ASSERT(child1.prev == NULL);
+ CX_TEST_ASSERT(child1.next == NULL);
+
+ // child 3 is unlinked
+ CX_TEST_ASSERT(child3.parent == NULL);
+ CX_TEST_ASSERT(child3.prev == NULL);
+ CX_TEST_ASSERT(child3.next == NULL);
+
+ // child 2 is still child of the unlinked child 3
+ CX_TEST_ASSERT(child3.children == &child2);
+ CX_TEST_ASSERT(child3.last_child == &child2);
+ CX_TEST_ASSERT(child2.parent == &child3);
+ CX_TEST_ASSERT(child2.children == NULL);
+ CX_TEST_ASSERT(child2.last_child == NULL);
+ CX_TEST_ASSERT(child2.prev == NULL);
+ CX_TEST_ASSERT(child2.next == NULL);
+
+ // unlink last child from parent
+ cx_tree_unlink(&child1, tree_node2_layout);
+ CX_TEST_ASSERT(parent.next == NULL);
+ CX_TEST_ASSERT(parent.prev == NULL);
+ CX_TEST_ASSERT(parent.parent == NULL);
+ CX_TEST_ASSERT(parent.children == NULL);
+ CX_TEST_ASSERT(parent.last_child == NULL);
+ CX_TEST_ASSERT(child1.parent == NULL);
}
}
@@ -215,38 +377,38 @@
for (unsigned i = 0 ; i <= 10 ; i++) {
s = testdata[i];
r = cx_tree_search(&root, &s, test_tree_search_function,
- (void **) &n, tree_child_list);
+ (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,
- (void **) &n, tree_child_list);
+ (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,
- (void **) &n, tree_child_list);
+ (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,
- (void **) &n, tree_child_list);
+ (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,
- (void **) &n, tree_child_list);
+ (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,
- (void **) &n, tree_child_list);
+ (void **) &n, tree_children(tree_node));
CX_TEST_ASSERT(r > 0);
CX_TEST_ASSERT(n == &cc);
}
@@ -255,7 +417,7 @@
CX_TEST(test_tree_iterator_create_and_dispose) {
tree_node root;
CX_TEST_DO {
- CxTreeIterator iter = cx_tree_iterator(&root, false, tree_child_list);
+ CxTreeIterator iter = cx_tree_iterator(&root, false, tree_children(tree_node));
CX_TEST_ASSERT(!iter.visit_on_exit);
CX_TEST_ASSERT(!iter.exiting);
CX_TEST_ASSERT(iter.counter == 1);
@@ -288,9 +450,9 @@
tree_node* expected_order[] = {
&root,
- &c, &cc,&cb, &cba,&ca,
+ &a, &aa, &ab,
&b, &ba,
- &a, &ab, &aa,
+ &c, &ca, &cb, &cba, &cc,
};
tree_node* actual_order[16]; // reserve more space in case s.t. goes wrong
@@ -305,7 +467,7 @@
cx_tree_link(&c, &cc, tree_node_layout);
cx_tree_link(&cb, &cba, tree_node_layout);
CX_TEST_DO {
- CxTreeIterator iter = cx_tree_iterator(&root, false, tree_child_list);
+ CxTreeIterator iter = cx_tree_iterator(&root, false, tree_children(tree_node));
unsigned chk = 0;
cx_foreach(tree_node*, node, iter) {
CX_TEST_ASSERT(node->data == 0);
@@ -358,7 +520,7 @@
cx_tree_link(&c, &cc, tree_node_layout);
cx_tree_link(&cb, &cba, tree_node_layout);
CX_TEST_DO {
- CxTreeIterator iter = cx_tree_iterator(&root, true, tree_child_list);
+ CxTreeIterator iter = cx_tree_iterator(&root, true, tree_children(tree_node));
unsigned chk = 0;
cx_foreach(tree_node*, node, iter) {
CX_TEST_ASSERT(iter.exiting || node->data == 0);
@@ -393,10 +555,7 @@
}
typedef struct test_xml_node {
- struct test_xml_node *parent;
- struct test_xml_node *next;
- struct test_xml_node *prev;
- struct test_xml_node *children;
+ struct tree_node base;
char const* name;
} test_xml_node;
@@ -431,18 +590,18 @@
target_dependencies.name = "dependencies";
target_feature_dependencies.name = "dependencies";
- cx_tree_link(&project, &target, tree_node_layout);
- cx_tree_link(&project, &dependency2, tree_node_layout);
+ cx_tree_link(&project, &config, tree_node_layout);
cx_tree_link(&project, &dependency1, tree_node_layout);
- cx_tree_link(&project, &config, tree_node_layout);
- cx_tree_link(&config, &var3, 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, &var1, 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(&dependency2, &dependency2lang, 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, &target_feature, tree_node_layout);
cx_tree_link(&target_feature, &target_feature_dependencies, tree_node_layout);
char const *expected =
@@ -451,7 +610,7 @@
"<target><feature><dependencies></dependencies></feature><dependencies></dependencies></target></project>";
char *actual = malloc(512);
CX_TEST_DO {
- CxTreeIterator iter = cx_tree_iterator(&project, true, tree_child_list);
+ CxTreeIterator iter = cx_tree_iterator(&project, true, tree_children(tree_node));
size_t i = 0;
cx_foreach(test_xml_node*, node, iter) {
size_t len = strlen(node->name);
@@ -497,7 +656,7 @@
cx_tree_link(c, cc, tree_node_layout);
cx_tree_link(cb, cba, tree_node_layout);
- CxTreeIterator iter = cx_tree_iterator(root, true, tree_child_list);
+ CxTreeIterator iter = cx_tree_iterator(root, true, tree_children(tree_node));
cx_foreach(tree_node *, node, iter) {
if (iter.exiting) {
cxFree(alloc,node);
@@ -514,7 +673,7 @@
tree_node child;
cx_tree_link(&root, &child, tree_node_layout);
CX_TEST_DO {
- CxTreeVisitor iter = cx_tree_visitor(&root, tree_child_list);
+ CxTreeVisitor 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.mutating);
@@ -545,8 +704,8 @@
tree_node* expected_order[] = {
&root,
- &c, &b, &a,
- &cc, &cb, &ca, &ba, &ab, &aa,
+ &a, &b, &c,
+ &aa, &ab, &ba, &ca, &cb, &cc,
&cba
};
tree_node* actual_order[16]; // reserve more space in case s.t. goes wrong
@@ -562,7 +721,7 @@
cx_tree_link(&c, &cc, tree_node_layout);
cx_tree_link(&cb, &cba, tree_node_layout);
CX_TEST_DO {
- CxTreeVisitor iter = cx_tree_visitor(&root, tree_child_list);
+ CxTreeVisitor iter = cx_tree_visitor(&root, tree_children(tree_node));
unsigned chk = 0;
cx_foreach(tree_node*, node, iter) {
CX_TEST_ASSERT(node->data == 0);
@@ -595,7 +754,7 @@
tree_node root = {0};
CX_TEST_DO {
- CxTreeVisitor iter = cx_tree_visitor(&root, tree_child_list);
+ CxTreeVisitor iter = cx_tree_visitor(&root, tree_children(tree_node));
unsigned chk = 0;
cx_foreach(tree_node*, node, iter) {
CX_TEST_ASSERT(node == iter.node);
@@ -624,7 +783,7 @@
cx_tree_link(&b, &c, tree_node_layout);
CX_TEST_DO {
- CxTreeVisitor iter = cx_tree_visitor(&root, tree_child_list);
+ CxTreeVisitor iter = cx_tree_visitor(&root, tree_children(tree_node));
unsigned chk = 0;
cx_foreach(tree_node*, node, iter) {
CX_TEST_ASSERT(node == iter.node);
@@ -659,8 +818,8 @@
tree_node* expected_order[] = {
&root,
- &c, &b, &a,
- &ba, &ab, &aa
+ &a, &b, &c,
+ &aa, &ab, &ba
};
tree_node* actual_order[16]; // reserve more space in case s.t. goes wrong
@@ -675,7 +834,7 @@
cx_tree_link(&c, &cc, tree_node_layout);
cx_tree_link(&cb, &cba, tree_node_layout);
CX_TEST_DO {
- CxTreeVisitor iter = cx_tree_visitor(&root, tree_child_list);
+ CxTreeVisitor iter = cx_tree_visitor(&root, tree_children(tree_node));
unsigned chk = 0;
cx_foreach(tree_node*, node, iter) {
CX_TEST_ASSERT(node->data == 0);
@@ -722,11 +881,11 @@
tree_node cc = {0};
tree_node cba = {0};
- tree_node* expected_order[] = {
+ tree_node *expected_order[] = {
&root,
+ &a, &aa, &ab,
+ &b, &ba,
&c,
- &b, &ba,
- &a, &ab, &aa,
};
tree_node* actual_order[16]; // reserve more space in case s.t. goes wrong
@@ -741,7 +900,7 @@
cx_tree_link(&c, &cc, tree_node_layout);
cx_tree_link(&cb, &cba, tree_node_layout);
CX_TEST_DO {
- CxTreeIterator iter = cx_tree_iterator(&root, false, tree_child_list);
+ CxTreeIterator iter = cx_tree_iterator(&root, false, tree_children(tree_node));
unsigned chk = 0;
cx_foreach(tree_node*, node, iter) {
CX_TEST_ASSERT(node->data == 0);
@@ -799,7 +958,7 @@
cx_tree_link(&c, &cc, tree_node_layout);
cx_tree_link(&cb, &cba, tree_node_layout);
CX_TEST_DO {
- CxTreeIterator iter = cx_tree_iterator(&root, true, tree_child_list);
+ CxTreeIterator iter = cx_tree_iterator(&root, true, tree_children(tree_node));
unsigned chk = 0;
cx_foreach(tree_node*, node, iter) {
CX_TEST_ASSERT(iter.exiting || node->data == 0);
@@ -841,6 +1000,10 @@
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_tree2_link_new_child);
+ cx_test_register(suite, test_tree2_link_add_child);
+ cx_test_register(suite, test_tree2_link_move_to_other_parent);
+ cx_test_register(suite, test_tree2_unlink);
cx_test_register(suite, test_tree_search);
cx_test_register(suite, test_tree_iterator_create_and_dispose);
cx_test_register(suite, test_tree_iterator_basic_only_enter);