--- 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);