ucx: tests/test_tree.c@4f02995ce44e

     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     cx_tree_link(&root, &a, tree_node_layout);

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

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

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

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

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

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

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

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

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

   299     CX_TEST_DO {

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

   301         unsigned chk = 0;

   302         cx_foreach(tree_node*, node, iter) {

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

   304             node->data++;

   305             chk++;

   306             CX_TEST_ASSERT(node == iter.node);

   307             CX_TEST_ASSERT(!iter.exiting);

   308             if (node == &root) {

   309                 CX_TEST_ASSERT(iter.depth == 1);

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

   311                 CX_TEST_ASSERT(iter.depth == 2);

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

   313                 CX_TEST_ASSERT(iter.depth == 4);

   314             } else {

   315                 CX_TEST_ASSERT(iter.depth == 3);

   316             }

   317         }

   318         CX_TEST_ASSERT(iter.counter == 11);

   319         CX_TEST_ASSERT(chk == 11);

   320         CX_TEST_ASSERT(iter.stack == NULL);

   321         CX_TEST_ASSERT(root.data == 1);

   322         CX_TEST_ASSERT(a.data == 1);

   323         CX_TEST_ASSERT(b.data == 1);

   324         CX_TEST_ASSERT(c.data == 1);

   325         CX_TEST_ASSERT(aa.data == 1);

   326         CX_TEST_ASSERT(ab.data == 1);

   327         CX_TEST_ASSERT(ba.data == 1);

   328         CX_TEST_ASSERT(ca.data == 1);

   329         CX_TEST_ASSERT(cb.data == 1);

   330         CX_TEST_ASSERT(cc.data == 1);

   331         CX_TEST_ASSERT(cba.data == 1);

   332     }

   333 }

   335 CX_TEST(test_tree_iterator_basic_enter_and_exit) {

   336     tree_node root = {0};

   337     tree_node a = {0};

   338     tree_node b = {0};

   339     tree_node c = {0};

   340     tree_node aa = {0};

   341     tree_node ab = {0};

   342     tree_node ba = {0};

   343     tree_node ca = {0};

   344     tree_node cb = {0};

   345     tree_node cc = {0};

   346     tree_node cba = {0};

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

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

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

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

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

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

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

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

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

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

   358     CX_TEST_DO {

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

   360         unsigned chk = 0;

   361         cx_foreach(tree_node*, node, iter) {

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

   363             node->data++;

   364             chk++;

   365             CX_TEST_ASSERT(node == iter.node);

   366             if (node == &root) {

   367                 CX_TEST_ASSERT(iter.depth == 1);

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

   369                 CX_TEST_ASSERT(iter.depth == 2);

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

   371                 CX_TEST_ASSERT(iter.depth == 4);

   372             } else {

   373                 CX_TEST_ASSERT(iter.depth == 3);

   374             }

   375         }

   376         CX_TEST_ASSERT(iter.counter == 11);

   377         CX_TEST_ASSERT(chk == 22);

   378         CX_TEST_ASSERT(iter.stack == NULL);

   379         CX_TEST_ASSERT(root.data == 2);

   380         CX_TEST_ASSERT(a.data == 2);

   381         CX_TEST_ASSERT(b.data == 2);

   382         CX_TEST_ASSERT(c.data == 2);

   383         CX_TEST_ASSERT(aa.data == 2);

   384         CX_TEST_ASSERT(ab.data == 2);

   385         CX_TEST_ASSERT(ba.data == 2);

   386         CX_TEST_ASSERT(ca.data == 2);

   387         CX_TEST_ASSERT(cb.data == 2);

   388         CX_TEST_ASSERT(cc.data == 2);

   389         CX_TEST_ASSERT(cba.data == 2);

   390     }

   391 }

   393 typedef struct test_xml_node {

   394     struct test_xml_node *parent;

   395     struct test_xml_node *next;

   396     struct test_xml_node *prev;

   397     struct test_xml_node *children;

   398     char const* name;

   399 } test_xml_node;

   401 CX_TEST(test_tree_iterator_xml) {

   402     test_xml_node project = {0};

   403     test_xml_node config = {0};

   404     test_xml_node var1 = {0};

   405     test_xml_node var2 = {0};

   406     test_xml_node var3 = {0};

   407     test_xml_node dependency1 = {0};

   408     test_xml_node dependency1make = {0};

   409     test_xml_node dependency2 = {0};

   410     test_xml_node dependency2lang = {0};

   411     test_xml_node dependency2make = {0};

   412     test_xml_node target = {0};

   413     test_xml_node target_feature = {0};

   414     test_xml_node target_feature_dependencies = {0};

   415     test_xml_node target_dependencies = {0};

   417     project.name = "project";

   418     config.name = "config";

   419     var1.name = "var";

   420     var2.name = "var";

   421     var3.name = "var";

   422     dependency1.name = "dependency";

   423     dependency1make.name = "make";

   424     dependency2.name = "dependency";

   425     dependency2lang.name = "lang";

   426     dependency2make.name = "make";

   427     target.name = "target";

   428     target_feature.name = "feature";

   429     target_dependencies.name = "dependencies";

   430     target_feature_dependencies.name = "dependencies";

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

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

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

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

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

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

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

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

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

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

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

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

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

   446     char const *expected =

   447             "<project><config><var></var><var></var><var></var></config>"

   448             "<dependency><make></make></dependency><dependency><lang></lang><make></make></dependency>"

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

   450     char *actual = malloc(512);

   451     CX_TEST_DO {

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

   453         size_t i = 0;

   454         cx_foreach(test_xml_node*, node, iter) {

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

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

   457             if (iter.exiting) {

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

   459             }

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

   461             i += len;

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

   463         }

   464         actual[i] = '\0';

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

   466     }

   467     free(actual);

   468 }

   470 CX_TEST(test_tree_iterator_free_nodes) {

   471     CxTestingAllocator talloc;

   472     cx_testing_allocator_init(&talloc);

   473     CxAllocator *alloc = &talloc.base;

   474     CX_TEST_DO {

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

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

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

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

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

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

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

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

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

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

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

   487         cx_tree_link(root, a, tree_node_layout);

   488         cx_tree_link(root, b, tree_node_layout);

   489         cx_tree_link(root, c, tree_node_layout);

   490         cx_tree_link(a, aa, tree_node_layout);

   491         cx_tree_link(a, ab, tree_node_layout);

   492         cx_tree_link(b, ba, tree_node_layout);

   493         cx_tree_link(c, ca, tree_node_layout);

   494         cx_tree_link(c, cb, tree_node_layout);

   495         cx_tree_link(c, cc, tree_node_layout);

   496         cx_tree_link(cb, cba, tree_node_layout);

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

   499         cx_foreach(tree_node *, node, iter) {

   500             if (iter.exiting) {

   501                 cxFree(alloc,node);

   502             }

   503         }

   505         CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));

   506     }

   507     cx_testing_allocator_destroy(&talloc);

   508 }

   510 CxTestSuite *cx_test_suite_tree_low_level(void) {

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

   513     cx_test_register(suite, test_tree_link_new_child);

   514     cx_test_register(suite, test_tree_link_add_child);

   515     cx_test_register(suite, test_tree_link_move_to_other_parent);

   516     cx_test_register(suite, test_tree_unlink);

   517     cx_test_register(suite, test_tree_search);

   518     cx_test_register(suite, test_tree_iterator_create_and_dispose);

   519     cx_test_register(suite, test_tree_iterator_basic_only_enter);

   520     cx_test_register(suite, test_tree_iterator_basic_enter_and_exit);

   521     cx_test_register(suite, test_tree_iterator_xml);

   522     cx_test_register(suite, test_tree_iterator_free_nodes);

   524     return suite;

   525 }

Mercurial > hg > ucx / file revision

tests/test_tree.c@4f02995ce44e

tests/test_tree.c