ucx: tests/test_tree.c@62d3aecc5bb7

     1 /*

     2  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.

     3  *

     4  * Copyright 2023 Mike Becker, Olaf Wintermann All rights reserved.

     5  *

     6  * Redistribution and use in source and binary forms, with or without

     7  * modification, are permitted provided that the following conditions are met:

     8  *

     9  *   1. Redistributions of source code must retain the above copyright

    10  *      notice, this list of conditions and the following disclaimer.

    11  *

    12  *   2. Redistributions in binary form must reproduce the above copyright

    13  *      notice, this list of conditions and the following disclaimer in the

    14  *      documentation and/or other materials provided with the distribution.

    15  *

    16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"

    17  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE

    18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE

    19  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE

    20  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR

    21  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF

    22  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS

    23  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN

    24  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)

    25  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE

    26  * POSSIBILITY OF SUCH DAMAGE.

    27  */

    29 #include "cx/tree.h"

    31 #include "cx/test.h"

    33 typedef struct tree_node {

    34     struct tree_node *parent;

    35     struct tree_node *next;

    36     struct tree_node *prev;

    37     struct tree_node *children;

    38     int data;

    39 } tree_node;

    41 #define tree_node_layout \

    42     offsetof(tree_node, parent), offsetof(tree_node, children), \

    43     offsetof(tree_node, prev), offsetof(tree_node, next)

    45 #define tree_child_list offsetof(tree_node, children),offsetof(tree_node, next)

    47 CX_TEST(test_tree_link_new_child) {

    48     tree_node parent = {0};

    49     tree_node child = {0};

    51     CX_TEST_DO {

    52         cx_tree_link(&parent, &child, tree_node_layout);

    53         CX_TEST_ASSERT(parent.next == NULL);

    54         CX_TEST_ASSERT(parent.prev == NULL);

    55         CX_TEST_ASSERT(parent.parent == NULL);

    56         CX_TEST_ASSERT(parent.children == &child);

    57         CX_TEST_ASSERT(child.parent == &parent);

    58         CX_TEST_ASSERT(child.next == NULL);

    59         CX_TEST_ASSERT(child.prev == NULL);

    60         CX_TEST_ASSERT(child.children == NULL);

    61     }

    62 }

    64 CX_TEST(test_tree_link_add_child) {

    65     tree_node parent = {0};

    66     tree_node child1 = {0};

    67     tree_node child2 = {0};

    68     tree_node child3 = {0};

    70     CX_TEST_DO {

    71         cx_tree_link(&parent, &child1, tree_node_layout);

    72         cx_tree_link(&parent, &child2, tree_node_layout);

    73         cx_tree_link(&parent, &child3, tree_node_layout);

    74         CX_TEST_ASSERT(parent.next == NULL);

    75         CX_TEST_ASSERT(parent.prev == NULL);

    76         CX_TEST_ASSERT(parent.parent == NULL);

    77         CX_TEST_ASSERT(parent.children == &child3);

    79         CX_TEST_ASSERT(child1.parent == &parent);

    80         CX_TEST_ASSERT(child2.parent == &parent);

    81         CX_TEST_ASSERT(child3.parent == &parent);

    82         CX_TEST_ASSERT(child1.children == NULL);

    83         CX_TEST_ASSERT(child2.children == NULL);

    84         CX_TEST_ASSERT(child3.children == NULL);

    86         CX_TEST_ASSERT(child3.prev == NULL);

    87         CX_TEST_ASSERT(child3.next == &child2);

    88         CX_TEST_ASSERT(child2.prev == &child3);

    89         CX_TEST_ASSERT(child2.next == &child1);

    90         CX_TEST_ASSERT(child1.prev == &child2);

    91         CX_TEST_ASSERT(child1.next == NULL);

    92     }

    93 }

    95 CX_TEST(test_tree_link_move_to_other_parent) {

    96     tree_node parent = {0};

    97     tree_node child1 = {0};

    98     tree_node child2 = {0};

    99     tree_node child3 = {0};

   100     cx_tree_link(&parent, &child1, tree_node_layout);

   101     cx_tree_link(&parent, &child2, tree_node_layout);

   102     cx_tree_link(&parent, &child3, tree_node_layout);

   104     CX_TEST_DO {

   105         cx_tree_link(&child3, &child2, tree_node_layout);

   107         CX_TEST_ASSERT(parent.next == NULL);

   108         CX_TEST_ASSERT(parent.prev == NULL);

   109         CX_TEST_ASSERT(parent.parent == NULL);

   110         CX_TEST_ASSERT(parent.children == &child3);

   112         CX_TEST_ASSERT(child1.parent == &parent);

   113         CX_TEST_ASSERT(child2.parent == &child3);

   114         CX_TEST_ASSERT(child3.parent == &parent);

   115         CX_TEST_ASSERT(child1.children == NULL);

   116         CX_TEST_ASSERT(child2.children == NULL);

   117         CX_TEST_ASSERT(child3.children == &child2);

   119         CX_TEST_ASSERT(child3.prev == NULL);

   120         CX_TEST_ASSERT(child3.next == &child1);

   121         CX_TEST_ASSERT(child1.prev == &child3);

   122         CX_TEST_ASSERT(child1.next == NULL);

   124         CX_TEST_ASSERT(child2.prev == NULL);

   125         CX_TEST_ASSERT(child2.next == NULL);

   126     }

   127 }

   129 CX_TEST(test_tree_unlink) {

   130     tree_node parent = {0};

   131     tree_node child1 = {0};

   132     tree_node child2 = {0};

   133     tree_node child3 = {0};

   134     cx_tree_link(&parent, &child1, tree_node_layout);

   135     cx_tree_link(&parent, &child3, tree_node_layout);

   136     cx_tree_link(&child3, &child2, tree_node_layout);

   138     CX_TEST_DO {

   139         cx_tree_unlink(&child3, tree_node_layout);

   141         CX_TEST_ASSERT(parent.next == NULL);

   142         CX_TEST_ASSERT(parent.prev == NULL);

   143         CX_TEST_ASSERT(parent.parent == NULL);

   144         CX_TEST_ASSERT(parent.children == &child1);

   146         CX_TEST_ASSERT(child1.parent == &parent);

   147         CX_TEST_ASSERT(child1.children == NULL);

   148         CX_TEST_ASSERT(child1.prev == NULL);

   149         CX_TEST_ASSERT(child1.next == NULL);

   151         // child 3 is unlinked

   152         CX_TEST_ASSERT(child3.parent == NULL);

   153         CX_TEST_ASSERT(child3.prev == NULL);

   154         CX_TEST_ASSERT(child3.next == NULL);

   156         // child 2 is still child of the unlinked child 3

   157         CX_TEST_ASSERT(child3.children == &child2);

   158         CX_TEST_ASSERT(child2.parent == &child3);

   159         CX_TEST_ASSERT(child2.children == NULL);

   160         CX_TEST_ASSERT(child2.prev == NULL);

   161         CX_TEST_ASSERT(child2.next == NULL);

   162     }

   163 }

   165 static int test_tree_search_function(void const *n, void const *d) {

   166     tree_node const *node = n;

   167     int data = *((int const*)d);

   169     if (data < node->data) return -1;

   170     else if (data == node->data) return 0;

   171     else return data - node->data;

   172 }

   174 CX_TEST(test_tree_search) {

   175     tree_node root = {0};

   176     tree_node a = {0};

   177     tree_node b = {0};

   178     tree_node c = {0};

   179     tree_node aa = {0};

   180     tree_node ab = {0};

   181     tree_node ba = {0};

   182     tree_node ca = {0};

   183     tree_node cb = {0};

   184     tree_node cc = {0};

   185     tree_node cba = {0};

   187     int testdata[] = {0, 10, 14, 18, 20, 25, 30, 32, 34, 36, 40};

   188     tree_node* testnodes[] = {&root, &a, &aa, &ab, &b, &ba, &c, &ca, &cb, &cba, &cc};

   190     for (unsigned i = 0 ; i <= 10 ; i++) {

   191         testnodes[i]->data = testdata[i];

   192     }

   194     cx_tree_link(&root, &a, tree_node_layout);

   195     cx_tree_link(&root, &b, tree_node_layout);

   196     cx_tree_link(&root, &c, tree_node_layout);

   198     cx_tree_link(&a, &aa, tree_node_layout);

   199     cx_tree_link(&a, &ab, tree_node_layout);

   201     cx_tree_link(&b, &ba, tree_node_layout);

   203     cx_tree_link(&c, &ca, tree_node_layout);

   204     cx_tree_link(&c, &cb, tree_node_layout);

   205     cx_tree_link(&c, &cc, tree_node_layout);

   207     cx_tree_link(&cb, &cba, tree_node_layout);

   209     int s;

   210     int r;

   211     tree_node *n;

   212     CX_TEST_DO {

   213         for (unsigned i = 0 ; i <= 10 ; i++) {

   214             s = testdata[i];

   215             r = cx_tree_search(&root, &s, test_tree_search_function,

   216                                (void **) &n, tree_child_list);

   217             CX_TEST_ASSERT(r == 0);

   218             CX_TEST_ASSERT(n == testnodes[i]);

   219         }

   221         s = -5;

   222         r = cx_tree_search(&root, &s, test_tree_search_function,

   223                            (void **) &n, tree_child_list);

   224         CX_TEST_ASSERT(r < 0);

   225         CX_TEST_ASSERT(n == NULL);

   227         s = 26;

   228         r = cx_tree_search(&root, &s, test_tree_search_function,

   229                            (void **) &n, tree_child_list);

   230         CX_TEST_ASSERT(r > 0);

   231         CX_TEST_ASSERT(n == &ba);

   233         s = 35;

   234         r = cx_tree_search(&root, &s, test_tree_search_function,

   235                            (void **) &n, tree_child_list);

   236         CX_TEST_ASSERT(r > 0);

   237         CX_TEST_ASSERT(n == &cb);

   239         s = 38;

   240         r = cx_tree_search(&root, &s, test_tree_search_function,

   241                            (void **) &n, tree_child_list);

   242         CX_TEST_ASSERT(r > 0);

   243         CX_TEST_ASSERT(n == &cba);

   245         s = 42;

   246         r = cx_tree_search(&root, &s, test_tree_search_function,

   247                            (void **) &n, tree_child_list);

   248         CX_TEST_ASSERT(r > 0);

   249         CX_TEST_ASSERT(n == &cc);

   250     }

   251 }

   253 CX_TEST(test_tree_iterator_create_and_dispose) {

   254     tree_node root;

   255     CX_TEST_DO {

   256         CxTreeIterator iter = cx_tree_iterator(&root, false, tree_child_list);

   257         CX_TEST_ASSERT(!iter.visit_on_exit);

   258         CX_TEST_ASSERT(!iter.exiting);

   259         CX_TEST_ASSERT(iter.counter == 1);

   260         CX_TEST_ASSERT(iter.node == &root);

   261         CX_TEST_ASSERT(!iter.base.mutating);

   262         CX_TEST_ASSERT(!iter.base.remove);

   263         CX_TEST_ASSERT(iter.stack != NULL);

   264         CX_TEST_ASSERT(iter.stack_capacity > 0);

   265         CX_TEST_ASSERT(iter.stack_size == 1);

   266         CX_TEST_ASSERT(iter.depth == 1);

   267         CX_TEST_ASSERT(iter.loc_next == offsetof(tree_node, next));

   268         CX_TEST_ASSERT(iter.loc_children == offsetof(tree_node, children));

   269         cxTreeIteratorDispose(&iter);

   270         CX_TEST_ASSERT(iter.stack == NULL);

   271     }

   272 }

   274 CX_TEST(test_tree_iterator_basic_only_enter) {

   275     tree_node root = {0};

   276     tree_node a = {0};

   277     tree_node b = {0};

   278     tree_node c = {0};

   279     tree_node aa = {0};

   280     tree_node ab = {0};

   281     tree_node ba = {0};

   282     tree_node ca = {0};

   283     tree_node cb = {0};

   284     tree_node cc = {0};

   285     tree_node cba = {0};

   287     cx_tree_link(&root, &a, tree_node_layout);

   288     cx_tree_link(&root, &b, tree_node_layout);

   289     cx_tree_link(&root, &c, tree_node_layout);

   290     cx_tree_link(&a, &aa, tree_node_layout);

   291     cx_tree_link(&a, &ab, tree_node_layout);

   292     cx_tree_link(&b, &ba, tree_node_layout);

   293     cx_tree_link(&c, &ca, tree_node_layout);

   294     cx_tree_link(&c, &cb, tree_node_layout);

   295     cx_tree_link(&c, &cc, tree_node_layout);

   296     cx_tree_link(&cb, &cba, tree_node_layout);

   297     CX_TEST_DO {

   298         CxTreeIterator iter = cx_tree_iterator(&root, false, tree_child_list);

   299         unsigned chk = 0;

   300         cx_foreach(tree_node*, node, iter) {

   301             CX_TEST_ASSERT(node->data == 0);

   302             node->data++;

   303             chk++;

   304             CX_TEST_ASSERT(node == iter.node);

   305             CX_TEST_ASSERT(!iter.exiting);

   306             if (node == &root) {

   307                 CX_TEST_ASSERT(iter.depth == 1);

   308             } else if (node == &a || node == &b || node == &c) {

   309                 CX_TEST_ASSERT(iter.depth == 2);

   310             } else if (node == &cba) {

   311                 CX_TEST_ASSERT(iter.depth == 4);

   312             } else {

   313                 CX_TEST_ASSERT(iter.depth == 3);

   314             }

   315         }

   316         CX_TEST_ASSERT(iter.counter == 11);

   317         CX_TEST_ASSERT(chk == 11);

   318         CX_TEST_ASSERT(iter.stack == NULL);

   319         CX_TEST_ASSERT(root.data == 1);

   320         CX_TEST_ASSERT(a.data == 1);

   321         CX_TEST_ASSERT(b.data == 1);

   322         CX_TEST_ASSERT(c.data == 1);

   323         CX_TEST_ASSERT(aa.data == 1);

   324         CX_TEST_ASSERT(ab.data == 1);

   325         CX_TEST_ASSERT(ba.data == 1);

   326         CX_TEST_ASSERT(ca.data == 1);

   327         CX_TEST_ASSERT(cb.data == 1);

   328         CX_TEST_ASSERT(cc.data == 1);

   329         CX_TEST_ASSERT(cba.data == 1);

   330     }

   331 }

   333 CX_TEST(test_tree_iterator_basic_enter_and_exit) {

   334     tree_node root = {0};

   335     tree_node a = {0};

   336     tree_node b = {0};

   337     tree_node c = {0};

   338     tree_node aa = {0};

   339     tree_node ab = {0};

   340     tree_node ba = {0};

   341     tree_node ca = {0};

   342     tree_node cb = {0};

   343     tree_node cc = {0};

   344     tree_node cba = {0};

   346     cx_tree_link(&root, &a, tree_node_layout);

   347     cx_tree_link(&root, &b, tree_node_layout);

   348     cx_tree_link(&root, &c, tree_node_layout);

   349     cx_tree_link(&a, &aa, tree_node_layout);

   350     cx_tree_link(&a, &ab, tree_node_layout);

   351     cx_tree_link(&b, &ba, tree_node_layout);

   352     cx_tree_link(&c, &ca, tree_node_layout);

   353     cx_tree_link(&c, &cb, tree_node_layout);

   354     cx_tree_link(&c, &cc, tree_node_layout);

   355     cx_tree_link(&cb, &cba, tree_node_layout);

   356     CX_TEST_DO {

   357         CxTreeIterator iter = cx_tree_iterator(&root, true, tree_child_list);

   358         unsigned chk = 0;

   359         cx_foreach(tree_node*, node, iter) {

   360             CX_TEST_ASSERT(iter.exiting || node->data == 0);

   361             node->data++;

   362             chk++;

   363             CX_TEST_ASSERT(node == iter.node);

   364             if (node == &root) {

   365                 CX_TEST_ASSERT(iter.depth == 1);

   366             } else if (node == &a || node == &b || node == &c) {

   367                 CX_TEST_ASSERT(iter.depth == 2);

   368             } else if (node == &cba) {

   369                 CX_TEST_ASSERT(iter.depth == 4);

   370             } else {

   371                 CX_TEST_ASSERT(iter.depth == 3);

   372             }

   373         }

   374         CX_TEST_ASSERT(iter.counter == 11);

   375         CX_TEST_ASSERT(chk == 22);

   376         CX_TEST_ASSERT(iter.stack == NULL);

   377         CX_TEST_ASSERT(root.data == 2);

   378         CX_TEST_ASSERT(a.data == 2);

   379         CX_TEST_ASSERT(b.data == 2);

   380         CX_TEST_ASSERT(c.data == 2);

   381         CX_TEST_ASSERT(aa.data == 2);

   382         CX_TEST_ASSERT(ab.data == 2);

   383         CX_TEST_ASSERT(ba.data == 2);

   384         CX_TEST_ASSERT(ca.data == 2);

   385         CX_TEST_ASSERT(cb.data == 2);

   386         CX_TEST_ASSERT(cc.data == 2);

   387         CX_TEST_ASSERT(cba.data == 2);

   388     }

   389 }

   391 typedef struct test_xml_node {

   392     struct test_xml_node *parent;

   393     struct test_xml_node *next;

   394     struct test_xml_node *prev;

   395     struct test_xml_node *children;

   396     char const* name;

   397 } test_xml_node;

   399 CX_TEST(test_tree_iterator_xml) {

   400     test_xml_node project = {0};

   401     test_xml_node config = {0};

   402     test_xml_node var1 = {0};

   403     test_xml_node var2 = {0};

   404     test_xml_node var3 = {0};

   405     test_xml_node dependency1 = {0};

   406     test_xml_node dependency1make = {0};

   407     test_xml_node dependency2 = {0};

   408     test_xml_node dependency2lang = {0};

   409     test_xml_node dependency2make = {0};

   410     test_xml_node target = {0};

   411     test_xml_node target_feature = {0};

   412     test_xml_node target_feature_dependencies = {0};

   413     test_xml_node target_dependencies = {0};

   415     project.name = "project";

   416     config.name = "config";

   417     var1.name = "var";

   418     var2.name = "var";

   419     var3.name = "var";

   420     dependency1.name = "dependency";

   421     dependency1make.name = "make";

   422     dependency2.name = "dependency";

   423     dependency2lang.name = "lang";

   424     dependency2make.name = "make";

   425     target.name = "target";

   426     target_feature.name = "feature";

   427     target_dependencies.name = "dependencies";

   428     target_feature_dependencies.name = "dependencies";

   430     cx_tree_link(&project, &target, tree_node_layout);

   431     cx_tree_link(&project, &dependency2, tree_node_layout);

   432     cx_tree_link(&project, &dependency1, tree_node_layout);

   433     cx_tree_link(&project, &config, tree_node_layout);

   434     cx_tree_link(&config, &var3, tree_node_layout);

   435     cx_tree_link(&config, &var2, tree_node_layout);

   436     cx_tree_link(&config, &var1, tree_node_layout);

   437     cx_tree_link(&dependency1, &dependency1make, tree_node_layout);

   438     cx_tree_link(&dependency2, &dependency2make, tree_node_layout);

   439     cx_tree_link(&dependency2, &dependency2lang, tree_node_layout);

   440     cx_tree_link(&target, &target_dependencies, tree_node_layout);

   441     cx_tree_link(&target, &target_feature, tree_node_layout);

   442     cx_tree_link(&target_feature, &target_feature_dependencies, tree_node_layout);

   444     char const *expected =

   445             "<project><config><var></var><var></var><var></var></config>"

   446             "<dependency><make></make></dependency><dependency><lang></lang><make></make></dependency>"

   447             "<target><feature><dependencies></dependencies></feature><dependencies></dependencies></target></project>";

   448     char *actual = malloc(512);

   449     CX_TEST_DO {

   450         CxTreeIterator iter = cx_tree_iterator(&project, true, tree_child_list);

   451         size_t i = 0;

   452         cx_foreach(test_xml_node*, node, iter) {

   453             size_t len = strlen(node->name);

   454             actual[i++] = '<';

   455             if (iter.exiting) {

   456                 actual[i++] = '/';

   457             }

   458             memcpy(actual+i, node->name, len);

   459             i += len;

   460             actual[i++] = '>';

   461         }

   462         actual[i] = '\0';

   463         CX_TEST_ASSERT(0 == strcmp(expected, actual));

   464     }

   465     free(actual);

   466 }

   468 CxTestSuite *cx_test_suite_tree_low_level(void) {

   469     CxTestSuite *suite = cx_test_suite_new("tree (low level)");

   471     cx_test_register(suite, test_tree_link_new_child);

   472     cx_test_register(suite, test_tree_link_add_child);

   473     cx_test_register(suite, test_tree_link_move_to_other_parent);

   474     cx_test_register(suite, test_tree_unlink);

   475     cx_test_register(suite, test_tree_search);

   476     cx_test_register(suite, test_tree_iterator_create_and_dispose);

   477     cx_test_register(suite, test_tree_iterator_basic_only_enter);

   478     cx_test_register(suite, test_tree_iterator_basic_enter_and_exit);

   479     cx_test_register(suite, test_tree_iterator_xml);

   481     return suite;

   482 }

Mercurial > hg > ucx / file revision

tests/test_tree.c@62d3aecc5bb7

tests/test_tree.c