ucx: tests/test_tree.c@a39e410a05e6

     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 #include "util_allocator.h"

    35 typedef struct tree_node {

    36     struct tree_node *parent;

    37     struct tree_node *next;

    38     struct tree_node *prev;

    39     struct tree_node *children;

    40     int data;

    41 } tree_node;

    43 #define tree_node_layout \

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

    45     offsetof(tree_node, prev), offsetof(tree_node, next)

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

    49 CX_TEST(test_tree_link_new_child) {

    50     tree_node parent = {0};

    51     tree_node child = {0};

    53     CX_TEST_DO {

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

    55         CX_TEST_ASSERT(parent.next == NULL);

    56         CX_TEST_ASSERT(parent.prev == NULL);

    57         CX_TEST_ASSERT(parent.parent == NULL);

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

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

    60         CX_TEST_ASSERT(child.next == NULL);

    61         CX_TEST_ASSERT(child.prev == NULL);

    62         CX_TEST_ASSERT(child.children == NULL);

    63     }

    64 }

    66 CX_TEST(test_tree_link_add_child) {

    67     tree_node parent = {0};

    68     tree_node child1 = {0};

    69     tree_node child2 = {0};

    70     tree_node child3 = {0};

    72     CX_TEST_DO {

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

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

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

    76         CX_TEST_ASSERT(parent.next == NULL);

    77         CX_TEST_ASSERT(parent.prev == NULL);

    78         CX_TEST_ASSERT(parent.parent == NULL);

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

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

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

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

    84         CX_TEST_ASSERT(child1.children == NULL);

    85         CX_TEST_ASSERT(child2.children == NULL);

    86         CX_TEST_ASSERT(child3.children == NULL);

    88         CX_TEST_ASSERT(child3.prev == NULL);

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

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

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

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

    93         CX_TEST_ASSERT(child1.next == NULL);

    94     }

    95 }

    97 CX_TEST(test_tree_link_move_to_other_parent) {

    98     tree_node parent = {0};

    99     tree_node child1 = {0};

   100     tree_node child2 = {0};

   101     tree_node child3 = {0};

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

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

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

   106     CX_TEST_DO {

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

   109         CX_TEST_ASSERT(parent.next == NULL);

   110         CX_TEST_ASSERT(parent.prev == NULL);

   111         CX_TEST_ASSERT(parent.parent == NULL);

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

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

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

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

   117         CX_TEST_ASSERT(child1.children == NULL);

   118         CX_TEST_ASSERT(child2.children == NULL);

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

   121         CX_TEST_ASSERT(child3.prev == NULL);

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

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

   124         CX_TEST_ASSERT(child1.next == NULL);

   126         CX_TEST_ASSERT(child2.prev == NULL);

   127         CX_TEST_ASSERT(child2.next == NULL);

   128     }

   129 }

   131 CX_TEST(test_tree_unlink) {

   132     tree_node parent = {0};

   133     tree_node child1 = {0};

   134     tree_node child2 = {0};

   135     tree_node child3 = {0};

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

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

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

   140     CX_TEST_DO {

   141         cx_tree_unlink(&child3, tree_node_layout);

   143         CX_TEST_ASSERT(parent.next == NULL);

   144         CX_TEST_ASSERT(parent.prev == NULL);

   145         CX_TEST_ASSERT(parent.parent == NULL);

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

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

   149         CX_TEST_ASSERT(child1.children == NULL);

   150         CX_TEST_ASSERT(child1.prev == NULL);

   151         CX_TEST_ASSERT(child1.next == NULL);

   153         // child 3 is unlinked

   154         CX_TEST_ASSERT(child3.parent == NULL);

   155         CX_TEST_ASSERT(child3.prev == NULL);

   156         CX_TEST_ASSERT(child3.next == NULL);

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

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

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

   161         CX_TEST_ASSERT(child2.children == NULL);

   162         CX_TEST_ASSERT(child2.prev == NULL);

   163         CX_TEST_ASSERT(child2.next == NULL);

   164     }

   165 }

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

   168     tree_node const *node = n;

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

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

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

   173     else return data - node->data;

   174 }

   176 CX_TEST(test_tree_search) {

   177     tree_node root = {0};

   178     tree_node a = {0};

   179     tree_node b = {0};

   180     tree_node c = {0};

   181     tree_node aa = {0};

   182     tree_node ab = {0};

   183     tree_node ba = {0};

   184     tree_node ca = {0};

   185     tree_node cb = {0};

   186     tree_node cc = {0};

   187     tree_node cba = {0};

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

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

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

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

   194     }

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

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

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

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

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

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

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

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

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

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

   211     int s;

   212     int r;

   213     tree_node *n;

   214     CX_TEST_DO {

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

   216             s = testdata[i];

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

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

   219             CX_TEST_ASSERT(r == 0);

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

   221         }

   223         s = -5;

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

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

   226         CX_TEST_ASSERT(r < 0);

   227         CX_TEST_ASSERT(n == NULL);

   229         s = 26;

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

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

   232         CX_TEST_ASSERT(r > 0);

   233         CX_TEST_ASSERT(n == &ba);

   235         s = 35;

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

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

   238         CX_TEST_ASSERT(r > 0);

   239         CX_TEST_ASSERT(n == &cb);

   241         s = 38;

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

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

   244         CX_TEST_ASSERT(r > 0);

   245         CX_TEST_ASSERT(n == &cba);

   247         s = 42;

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

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

   250         CX_TEST_ASSERT(r > 0);

   251         CX_TEST_ASSERT(n == &cc);

   252     }

   253 }

   255 CX_TEST(test_tree_iterator_create_and_dispose) {

   256     tree_node root;

   257     CX_TEST_DO {

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

   259         CX_TEST_ASSERT(!iter.visit_on_exit);

   260         CX_TEST_ASSERT(!iter.exiting);

   261         CX_TEST_ASSERT(iter.counter == 1);

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

   263         CX_TEST_ASSERT(!iter.base.mutating);

   264         CX_TEST_ASSERT(!iter.base.remove);

   265         CX_TEST_ASSERT(iter.stack != NULL);

   266         CX_TEST_ASSERT(iter.stack_capacity > 0);

   267         CX_TEST_ASSERT(iter.stack_size == 1);

   268         CX_TEST_ASSERT(iter.depth == 1);

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

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

   271         cxTreeIteratorDispose(&iter);

   272         CX_TEST_ASSERT(iter.stack == NULL);

   273     }

   274 }

   276 CX_TEST(test_tree_iterator_basic_only_enter) {

   277     tree_node root = {0};

   278     tree_node a = {0};

   279     tree_node b = {0};

   280     tree_node c = {0};

   281     tree_node aa = {0};

   282     tree_node ab = {0};

   283     tree_node ba = {0};

   284     tree_node ca = {0};

   285     tree_node cb = {0};

   286     tree_node cc = {0};

   287     tree_node cba = {0};

   289     tree_node* expected_order[] = {

   290             &root,

   291             &c, &cc,&cb, &cba,&ca,

   292             &b, &ba,

   293             &a, &ab, &aa,

   294     };

   295     tree_node* actual_order[16]; // reserve more space in case s.t. goes wrong

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

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

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

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

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

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

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

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

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

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

   307     CX_TEST_DO {

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

   309         unsigned chk = 0;

   310         cx_foreach(tree_node*, node, iter) {

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

   312             node->data++;

   313             actual_order[chk] = node;

   314             chk++;

   315             CX_TEST_ASSERT(node == iter.node);

   316             CX_TEST_ASSERT(!iter.exiting);

   317             if (node == &root) {

   318                 CX_TEST_ASSERT(iter.depth == 1);

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

   320                 CX_TEST_ASSERT(iter.depth == 2);

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

   322                 CX_TEST_ASSERT(iter.depth == 4);

   323             } else {

   324                 CX_TEST_ASSERT(iter.depth == 3);

   325             }

   326         }

   327         CX_TEST_ASSERT(iter.counter == 11);

   328         CX_TEST_ASSERT(chk == 11);

   329         for (unsigned i = 0 ; i < chk ; i++) {

   330             CX_TEST_ASSERT(actual_order[i] == expected_order[i]);

   331             CX_TEST_ASSERT(actual_order[i]->data == 1);

   332         }

   333         CX_TEST_ASSERT(iter.stack == NULL);

   334     }

   335 }

   337 CX_TEST(test_tree_iterator_basic_enter_and_exit) {

   338     tree_node root = {0};

   339     tree_node a = {0};

   340     tree_node b = {0};

   341     tree_node c = {0};

   342     tree_node aa = {0};

   343     tree_node ab = {0};

   344     tree_node ba = {0};

   345     tree_node ca = {0};

   346     tree_node cb = {0};

   347     tree_node cc = {0};

   348     tree_node cba = {0};

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

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

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

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

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

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

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

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

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

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

   360     CX_TEST_DO {

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

   362         unsigned chk = 0;

   363         cx_foreach(tree_node*, node, iter) {

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

   365             node->data++;

   366             chk++;

   367             CX_TEST_ASSERT(node == iter.node);

   368             if (node == &root) {

   369                 CX_TEST_ASSERT(iter.depth == 1);

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

   371                 CX_TEST_ASSERT(iter.depth == 2);

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

   373                 CX_TEST_ASSERT(iter.depth == 4);

   374             } else {

   375                 CX_TEST_ASSERT(iter.depth == 3);

   376             }

   377         }

   378         CX_TEST_ASSERT(iter.counter == 11);

   379         CX_TEST_ASSERT(chk == 22);

   380         CX_TEST_ASSERT(iter.stack == NULL);

   381         CX_TEST_ASSERT(root.data == 2);

   382         CX_TEST_ASSERT(a.data == 2);

   383         CX_TEST_ASSERT(b.data == 2);

   384         CX_TEST_ASSERT(c.data == 2);

   385         CX_TEST_ASSERT(aa.data == 2);

   386         CX_TEST_ASSERT(ab.data == 2);

   387         CX_TEST_ASSERT(ba.data == 2);

   388         CX_TEST_ASSERT(ca.data == 2);

   389         CX_TEST_ASSERT(cb.data == 2);

   390         CX_TEST_ASSERT(cc.data == 2);

   391         CX_TEST_ASSERT(cba.data == 2);

   392     }

   393 }

   395 typedef struct test_xml_node {

   396     struct test_xml_node *parent;

   397     struct test_xml_node *next;

   398     struct test_xml_node *prev;

   399     struct test_xml_node *children;

   400     char const* name;

   401 } test_xml_node;

   403 CX_TEST(test_tree_iterator_xml) {

   404     test_xml_node project = {0};

   405     test_xml_node config = {0};

   406     test_xml_node var1 = {0};

   407     test_xml_node var2 = {0};

   408     test_xml_node var3 = {0};

   409     test_xml_node dependency1 = {0};

   410     test_xml_node dependency1make = {0};

   411     test_xml_node dependency2 = {0};

   412     test_xml_node dependency2lang = {0};

   413     test_xml_node dependency2make = {0};

   414     test_xml_node target = {0};

   415     test_xml_node target_feature = {0};

   416     test_xml_node target_feature_dependencies = {0};

   417     test_xml_node target_dependencies = {0};

   419     project.name = "project";

   420     config.name = "config";

   421     var1.name = "var";

   422     var2.name = "var";

   423     var3.name = "var";

   424     dependency1.name = "dependency";

   425     dependency1make.name = "make";

   426     dependency2.name = "dependency";

   427     dependency2lang.name = "lang";

   428     dependency2make.name = "make";

   429     target.name = "target";

   430     target_feature.name = "feature";

   431     target_dependencies.name = "dependencies";

   432     target_feature_dependencies.name = "dependencies";

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

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

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

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

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

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

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

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

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

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

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

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

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

   448     char const *expected =

   449             "<project><config><var></var><var></var><var></var></config>"

   450             "<dependency><make></make></dependency><dependency><lang></lang><make></make></dependency>"

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

   452     char *actual = malloc(512);

   453     CX_TEST_DO {

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

   455         size_t i = 0;

   456         cx_foreach(test_xml_node*, node, iter) {

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

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

   459             if (iter.exiting) {

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

   461             }

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

   463             i += len;

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

   465         }

   466         actual[i] = '\0';

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

   468     }

   469     free(actual);

   470 }

   472 CX_TEST(test_tree_iterator_free_nodes) {

   473     CxTestingAllocator talloc;

   474     cx_testing_allocator_init(&talloc);

   475     CxAllocator *alloc = &talloc.base;

   476     CX_TEST_DO {

   477         tree_node *root = cxCalloc(alloc, 1, sizeof(tree_node));

   478         tree_node *a = cxCalloc(alloc, 1, sizeof(tree_node));

   479         tree_node *b = cxCalloc(alloc, 1, sizeof(tree_node));

   480         tree_node *c = cxCalloc(alloc, 1, sizeof(tree_node));

   481         tree_node *aa = cxCalloc(alloc, 1, sizeof(tree_node));

   482         tree_node *ab = cxCalloc(alloc, 1, sizeof(tree_node));

   483         tree_node *ba = cxCalloc(alloc, 1, sizeof(tree_node));

   484         tree_node *ca = cxCalloc(alloc, 1, sizeof(tree_node));

   485         tree_node *cb = cxCalloc(alloc, 1, sizeof(tree_node));

   486         tree_node *cc = cxCalloc(alloc, 1, sizeof(tree_node));

   487         tree_node *cba = cxCalloc(alloc, 1, sizeof(tree_node));

   489         cx_tree_link(root, a, tree_node_layout);

   490         cx_tree_link(root, b, tree_node_layout);

   491         cx_tree_link(root, c, tree_node_layout);

   492         cx_tree_link(a, aa, tree_node_layout);

   493         cx_tree_link(a, ab, tree_node_layout);

   494         cx_tree_link(b, ba, tree_node_layout);

   495         cx_tree_link(c, ca, tree_node_layout);

   496         cx_tree_link(c, cb, tree_node_layout);

   497         cx_tree_link(c, cc, tree_node_layout);

   498         cx_tree_link(cb, cba, tree_node_layout);

   500         CxTreeIterator iter = cx_tree_iterator(root, true, tree_child_list);

   501         cx_foreach(tree_node *, node, iter) {

   502             if (iter.exiting) {

   503                 cxFree(alloc,node);

   504             }

   505         }

   507         CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));

   508     }

   509     cx_testing_allocator_destroy(&talloc);

   510 }

   512 CX_TEST(test_tree_visitor_create_and_dispose) {

   513     tree_node root;

   514     tree_node child;

   515     cx_tree_link(&root, &child, tree_node_layout);

   516     CX_TEST_DO {

   517         CxTreeVisitor iter = cx_tree_visitor(&root, tree_child_list);

   518         CX_TEST_ASSERT(iter.counter == 1);

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

   520         CX_TEST_ASSERT(!iter.base.mutating);

   521         CX_TEST_ASSERT(!iter.base.remove);

   522         CX_TEST_ASSERT(iter.queue_next != NULL);

   523         CX_TEST_ASSERT(iter.queue_last != NULL);

   524         CX_TEST_ASSERT(iter.depth == 1);

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

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

   527         cxTreeVisitorDispose(&iter);

   528         CX_TEST_ASSERT(iter.queue_next == NULL);

   529         CX_TEST_ASSERT(iter.queue_last == NULL);

   530     }

   531 }

   533 CX_TEST(test_tree_visitor) {

   534     tree_node root = {0};

   535     tree_node a = {0};

   536     tree_node b = {0};

   537     tree_node c = {0};

   538     tree_node aa = {0};

   539     tree_node ab = {0};

   540     tree_node ba = {0};

   541     tree_node ca = {0};

   542     tree_node cb = {0};

   543     tree_node cc = {0};

   544     tree_node cba = {0};

   546     tree_node* expected_order[] = {

   547             &root,

   548             &c, &b, &a,

   549             &cc, &cb, &ca, &ba, &ab, &aa,

   550             &cba

   551     };

   552     tree_node* actual_order[16]; // reserve more space in case s.t. goes wrong

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

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

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

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

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

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

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

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

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

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

   564     CX_TEST_DO {

   565         CxTreeVisitor iter = cx_tree_visitor(&root, tree_child_list);

   566         unsigned chk = 0;

   567         cx_foreach(tree_node*, node, iter) {

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

   569             node->data++;

   570             actual_order[chk] = node;

   571             chk++;

   572             CX_TEST_ASSERT(node == iter.node);

   573             if (node == &root) {

   574                 CX_TEST_ASSERT(iter.depth == 1);

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

   576                 CX_TEST_ASSERT(iter.depth == 2);

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

   578                 CX_TEST_ASSERT(iter.depth == 4);

   579             } else {

   580                 CX_TEST_ASSERT(iter.depth == 3);

   581             }

   582         }

   583         CX_TEST_ASSERT(iter.counter == 11);

   584         CX_TEST_ASSERT(chk == 11);

   585         for (unsigned i = 0 ; i < chk ; i++) {

   586             CX_TEST_ASSERT(actual_order[i] == expected_order[i]);

   587             CX_TEST_ASSERT(actual_order[i]->data == 1);

   588         }

   589         CX_TEST_ASSERT(iter.queue_next == NULL);

   590         CX_TEST_ASSERT(iter.queue_last == NULL);

   591     }

   592 }

   594 CX_TEST(test_tree_visitor_no_children) {

   595     tree_node root = {0};

   597     CX_TEST_DO {

   598         CxTreeVisitor iter = cx_tree_visitor(&root, tree_child_list);

   599         unsigned chk = 0;

   600         cx_foreach(tree_node*, node, iter) {

   601             CX_TEST_ASSERT(node == iter.node);

   602             chk++;

   603         }

   604         CX_TEST_ASSERT(iter.counter == 1);

   605         CX_TEST_ASSERT(chk == 1);

   606         CX_TEST_ASSERT(iter.queue_next == NULL);

   607         CX_TEST_ASSERT(iter.queue_last == NULL);

   608     }

   609 }

   611 CX_TEST(test_tree_visitor_no_branching) {

   612     tree_node root = {0};

   613     tree_node a = {0};

   614     tree_node b = {0};

   615     tree_node c = {0};

   617     tree_node* expected_order[] = {

   618             &root, &a, &b, &c

   619     };

   620     tree_node* actual_order[4];

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

   623     cx_tree_link(&a, &b, tree_node_layout);

   624     cx_tree_link(&b, &c, tree_node_layout);

   626     CX_TEST_DO {

   627         CxTreeVisitor iter = cx_tree_visitor(&root, tree_child_list);

   628         unsigned chk = 0;

   629         cx_foreach(tree_node*, node, iter) {

   630             CX_TEST_ASSERT(node == iter.node);

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

   632             node->data++;

   633             actual_order[chk] = node;

   634             chk++;

   635         }

   636         CX_TEST_ASSERT(iter.counter == 4);

   637         CX_TEST_ASSERT(chk == 4);

   638         CX_TEST_ASSERT(iter.queue_next == NULL);

   639         CX_TEST_ASSERT(iter.queue_last == NULL);

   640         for (unsigned i = 0 ; i < chk ; i++) {

   641             CX_TEST_ASSERT(actual_order[i] == expected_order[i]);

   642             CX_TEST_ASSERT(actual_order[i]->data == 1);

   643         }

   644     }

   645 }

   647 CxTestSuite *cx_test_suite_tree_low_level(void) {

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

   650     cx_test_register(suite, test_tree_link_new_child);

   651     cx_test_register(suite, test_tree_link_add_child);

   652     cx_test_register(suite, test_tree_link_move_to_other_parent);

   653     cx_test_register(suite, test_tree_unlink);

   654     cx_test_register(suite, test_tree_search);

   655     cx_test_register(suite, test_tree_iterator_create_and_dispose);

   656     cx_test_register(suite, test_tree_iterator_basic_only_enter);

   657     cx_test_register(suite, test_tree_iterator_basic_enter_and_exit);

   658     cx_test_register(suite, test_tree_iterator_xml);

   659     cx_test_register(suite, test_tree_iterator_free_nodes);

   660     cx_test_register(suite, test_tree_visitor);

   661     cx_test_register(suite, test_tree_visitor_no_children);

   662     cx_test_register(suite, test_tree_visitor_no_branching);

   664     return suite;

   665 }

Mercurial > hg > ucx / file revision

tests/test_tree.c@a39e410a05e6

tests/test_tree.c