src/coll/test_treebase.c

   1 /*
   2  * test_treebase.c
   3  *
   4  * Copyright (c) 2013 project bchan
   5  *
   6  * This software is provided 'as-is', without any express or implied
   7  * warranty. In no event will the authors be held liable for any damages
   8  * arising from the use of this software.
   9  *
  10  * Permission is granted to anyone to use this software for any purpose,
  11  * including commercial applications, and to alter it and redistribute it
  12  * freely, subject to the following restrictions:
  13  *
  14  * 1. The origin of this software must not be misrepresented; you must not
  15  *    claim that you wrote the original software. If you use this software
  16  *    in a product, an acknowledgment in the product documentation would be
  17  *    appreciated but is not required.
  18  *
  19  * 2. Altered source versions must be plainly marked as such, and must not be
  20  *    misrepresented as being the original software.
  21  *
  22  * 3. This notice may not be removed or altered from any source
  23  *    distribution.
  24  *
  25  */
  26
  27 #include "test_coll.h"
  28
  29 #include "treebase.h"
  30
  31 #include        <basic.h>
  32 #include        <bstdio.h>
  33
  34 #include    <unittest_driver.h>
  35
  36 typedef struct {
  37         treebase_node_t *parent;
  38         treebase_node_t *next;
  39         treebase_node_t *prev;
  40         treebase_node_t *first;
  41         treebase_node_t *last;
  42         Bool has_child;
  43 } test_treebase_node_expected_t;
  44
  45 LOCAL Bool test_treebase_node_commoncheck(treebase_node_t *node, test_treebase_node_expected_t *expected, UB *msg)
  46 {
  47         treebase_node_t *node1;
  48         Bool ret = True, ok;
  49
  50         node1 = treebase_node_getparent(node);
  51         if (node1 != expected->parent) {
  52                 printf("%s: parent is not expected\n", msg);
  53                 ret = False;
  54         }
  55         node1 = treebase_node_getnextsibling(node);
  56         if (node1 != expected->next) {
  57                 printf("%s: next sibling is not expected\n", msg);
  58                 ret = False;
  59         }
  60         node1 = treebase_node_getprevsibling(node);
  61         if (node1 != expected->prev) {
  62                 printf("%s: prev sibling is not expected\n", msg);
  63                 ret = False;
  64         }
  65         node1 = treebase_node_getfirstchild(node);
  66         if (node1 != expected->first) {
  67                 printf("%s: first child is not expected\n", msg);
  68                 ret = False;
  69         }
  70         node1 = treebase_node_getlastchild(node);
  71         if (node1 != expected->last) {
  72                 printf("%s: last child is not expected\n", msg);
  73                 ret = False;
  74         }
  75         ok = treebase_node_haschild(node);
  76         if (ok != expected->has_child) {
  77                 printf("%s: has child is not expected\n", msg);
  78                 ret = False;
  79         }
  80
  81         return ret;
  82 }
  83
  84 LOCAL UNITTEST_RESULT test_treebase_node_1()
  85 {
  86         treebase_node_t node;
  87
  88         treebase_node_initialize(&node);
  89         treebase_node_finalize(&node);
  90
  91         return UNITTEST_RESULT_PASS;
  92 }
  93
  94 LOCAL UNITTEST_RESULT test_treebase_node_2()
  95 {
  96         treebase_node_t node;
  97         test_treebase_node_expected_t expected;
  98         Bool ok;
  99         UNITTEST_RESULT ret = UNITTEST_RESULT_PASS;
 100
 101         treebase_node_initialize(&node);
 102
 103         expected.parent = NULL;
 104         expected.next = NULL;
 105         expected.prev = NULL;
 106         expected.first = NULL;
 107         expected.last = NULL;
 108         expected.has_child = False;
 109         ok = test_treebase_node_commoncheck(&node, &expected, "node");
 110         if (ok == False) {
 111                 ret = UNITTEST_RESULT_FAIL;
 112         }
 113
 114         treebase_node_finalize(&node);
 115
 116         return ret;
 117 }
 118
 119 LOCAL UNITTEST_RESULT test_treebase_node_3()
 120 {
 121         treebase_node_t node0, node1;
 122         test_treebase_node_expected_t expected;
 123         Bool ok;
 124         UNITTEST_RESULT ret = UNITTEST_RESULT_PASS;
 125
 126         treebase_node_initialize(&node0);
 127         treebase_node_initialize(&node1);
 128
 129         treebase_node_appendchild(&node0, &node1);
 130
 131         /**/
 132         expected.parent = NULL;
 133         expected.next = NULL;
 134         expected.prev = NULL;
 135         expected.first = &node1;
 136         expected.last = &node1;
 137         expected.has_child = True;
 138         ok = test_treebase_node_commoncheck(&node0, &expected, "node0");
 139         if (ok == False) {
 140                 ret = UNITTEST_RESULT_FAIL;
 141         }
 142         /**/
 143         expected.parent = &node0;
 144         expected.next = NULL;
 145         expected.prev = NULL;
 146         expected.first = NULL;
 147         expected.last = NULL;
 148         expected.has_child = False;
 149         ok = test_treebase_node_commoncheck(&node1, &expected, "node1");
 150         if (ok == False) {
 151                 ret = UNITTEST_RESULT_FAIL;
 152         }
 153
 154         treebase_node_finalize(&node1);
 155         treebase_node_finalize(&node0);
 156
 157         return ret;
 158 }
 159
 160 LOCAL UNITTEST_RESULT test_treebase_node_4()
 161 {
 162         treebase_node_t node0, node1;
 163         test_treebase_node_expected_t expected;
 164         Bool ok;
 165         UNITTEST_RESULT ret = UNITTEST_RESULT_PASS;
 166
 167         treebase_node_initialize(&node0);
 168         treebase_node_initialize(&node1);
 169
 170         treebase_node_appendchild(&node0, &node1);
 171         treebase_node_remove(&node1);
 172
 173         /**/
 174         expected.parent = NULL;
 175         expected.next = NULL;
 176         expected.prev = NULL;
 177         expected.first = NULL;
 178         expected.last = NULL;
 179         expected.has_child = False;
 180         ok = test_treebase_node_commoncheck(&node0, &expected, "node0");
 181         if (ok == False) {
 182                 ret = UNITTEST_RESULT_FAIL;
 183         }
 184         /**/
 185         expected.parent = NULL;
 186         expected.next = NULL;
 187         expected.prev = NULL;
 188         expected.first = NULL;
 189         expected.last = NULL;
 190         expected.has_child = False;
 191         ok = test_treebase_node_commoncheck(&node1, &expected, "node1");
 192         if (ok == False) {
 193                 ret = UNITTEST_RESULT_FAIL;
 194         }
 195
 196         treebase_node_finalize(&node1);
 197         treebase_node_finalize(&node0);
 198
 199         return ret;
 200 }
 201
 202 LOCAL UNITTEST_RESULT test_treebase_node_5()
 203 {
 204         treebase_node_t node0, node1, node2;
 205         test_treebase_node_expected_t expected;
 206         Bool ok;
 207         UNITTEST_RESULT ret = UNITTEST_RESULT_PASS;
 208
 209         treebase_node_initialize(&node0);
 210         treebase_node_initialize(&node1);
 211         treebase_node_initialize(&node2);
 212
 213         treebase_node_appendchild(&node0, &node1);
 214         treebase_node_appendchild(&node0, &node2);
 215
 216         /**/
 217         expected.parent = NULL;
 218         expected.next = NULL;
 219         expected.prev = NULL;
 220         expected.first = &node1;
 221         expected.last = &node2;
 222         expected.has_child = True;
 223         ok = test_treebase_node_commoncheck(&node0, &expected, "node0");
 224         if (ok == False) {
 225                 ret = UNITTEST_RESULT_FAIL;
 226         }
 227         /**/
 228         expected.parent = &node0;
 229         expected.next = &node2;
 230         expected.prev = NULL;
 231         expected.first = NULL;
 232         expected.last = NULL;
 233         expected.has_child = False;
 234         ok = test_treebase_node_commoncheck(&node1, &expected, "node1");
 235         if (ok == False) {
 236                 ret = UNITTEST_RESULT_FAIL;
 237         }
 238         /**/
 239         expected.parent = &node0;
 240         expected.next = NULL;
 241         expected.prev = &node1;
 242         expected.first = NULL;
 243         expected.last = NULL;
 244         expected.has_child = False;
 245         ok = test_treebase_node_commoncheck(&node2, &expected, "node2");
 246         if (ok == False) {
 247                 ret = UNITTEST_RESULT_FAIL;
 248         }
 249
 250         treebase_node_finalize(&node2);
 251         treebase_node_finalize(&node1);
 252         treebase_node_finalize(&node0);
 253
 254         return ret;
 255 }
 256
 257 LOCAL UNITTEST_RESULT test_treebase_node_6()
 258 {
 259         treebase_node_t node0, node1, node2;
 260         test_treebase_node_expected_t expected;
 261         Bool ok;
 262         UNITTEST_RESULT ret = UNITTEST_RESULT_PASS;
 263
 264         treebase_node_initialize(&node0);
 265         treebase_node_initialize(&node1);
 266         treebase_node_initialize(&node2);
 267
 268         treebase_node_appendchild(&node0, &node1);
 269         treebase_node_appendchild(&node1, &node2);
 270
 271         /**/
 272         expected.parent = NULL;
 273         expected.next = NULL;
 274         expected.prev = NULL;
 275         expected.first = &node1;
 276         expected.last = &node1;
 277         expected.has_child = True;
 278         ok = test_treebase_node_commoncheck(&node0, &expected, "node0");
 279         if (ok == False) {
 280                 ret = UNITTEST_RESULT_FAIL;
 281         }
 282         /**/
 283         expected.parent = &node0;
 284         expected.next = NULL;
 285         expected.prev = NULL;
 286         expected.first = &node2;
 287         expected.last = &node2;
 288         expected.has_child = True;
 289         ok = test_treebase_node_commoncheck(&node1, &expected, "node1");
 290         if (ok == False) {
 291                 ret = UNITTEST_RESULT_FAIL;
 292         }
 293         /**/
 294         expected.parent = &node1;
 295         expected.next = NULL;
 296         expected.prev = NULL;
 297         expected.first = NULL;
 298         expected.last = NULL;
 299         expected.has_child = False;
 300         ok = test_treebase_node_commoncheck(&node2, &expected, "node2");
 301         if (ok == False) {
 302                 ret = UNITTEST_RESULT_FAIL;
 303         }
 304
 305         treebase_node_finalize(&node2);
 306         treebase_node_finalize(&node1);
 307         treebase_node_finalize(&node0);
 308
 309         return ret;
 310 }
 311
 312 /* treebase_preordertraversal_t */
 313
 314 typedef struct {
 315         Bool cont;
 316         treebase_node_t *node;
 317         TREEBASE_TRAVERSAL_DIRECTION dir;
 318 } test_treebase_preordertraversal_expected_t;
 319
 320 LOCAL UNITTEST_RESULT test_treebase_preordertraversal_common(treebase_node_t *root, test_treebase_preordertraversal_expected_t *expected, W expected_len)
 321 {
 322         treebase_node_t *node_result;
 323         treebase_preordertraversal_t traversal;
 324         TREEBASE_TRAVERSAL_DIRECTION dir;
 325         Bool cont;
 326         UNITTEST_RESULT ret = UNITTEST_RESULT_PASS;
 327         W i;
 328
 329         treebase_preordertraversal_initialize(&traversal, root);
 330
 331         for (i = 0;; i++) {
 332                 cont = treebase_preordertraversal_next(&traversal, &node_result, &dir);
 333                 if (i < expected_len) {
 334                         if (expected[i].cont != cont) {
 335                                 printf("%d: cont is not expected\n", i);
 336                                 ret = UNITTEST_RESULT_FAIL;
 337                         }
 338                         if (expected[i].node != node_result) {
 339                                 printf("%d: node is not expected\n", i);
 340                                 ret = UNITTEST_RESULT_FAIL;
 341                         }
 342                         if (expected[i].dir != dir) {
 343                                 printf("%d: direction is not expected\n", i);
 344                                 ret = UNITTEST_RESULT_FAIL;
 345                         }
 346                 }
 347
 348                 if (cont == False) {
 349                         break;
 350                 }
 351         }
 352         if (i != expected_len) {
 353                 printf("node number check fail: expected = %d, result = %d\n", expected_len, i);
 354                 ret = UNITTEST_RESULT_FAIL;
 355         }
 356
 357         treebase_preordertraversal_finalize(&traversal);
 358
 359         return ret;
 360 }
 361
 362 LOCAL UNITTEST_RESULT test_treebase_preordertraversal_1()
 363 {
 364         treebase_node_t node0, node1, node2, node3, node4;
 365         test_treebase_preordertraversal_expected_t expected[] = {
 366                 { True, &node0, TREEBASE_TRAVERSAL_DIRECTION_DOWN },
 367                 { True, &node1, TREEBASE_TRAVERSAL_DIRECTION_DOWN },
 368                 { True, &node2, TREEBASE_TRAVERSAL_DIRECTION_DOWN },
 369                 { True, &node2, TREEBASE_TRAVERSAL_DIRECTION_UP },
 370                 { True, &node3, TREEBASE_TRAVERSAL_DIRECTION_DOWN },
 371                 { True, &node3, TREEBASE_TRAVERSAL_DIRECTION_UP },
 372                 { True, &node4, TREEBASE_TRAVERSAL_DIRECTION_DOWN },
 373                 { True, &node4, TREEBASE_TRAVERSAL_DIRECTION_UP },
 374                 { True, &node1, TREEBASE_TRAVERSAL_DIRECTION_UP },
 375                 { True, &node0, TREEBASE_TRAVERSAL_DIRECTION_UP },
 376         };
 377         W expected_len = sizeof(expected) / sizeof(test_treebase_preordertraversal_expected_t);
 378         UNITTEST_RESULT ret;
 379
 380         treebase_node_initialize(&node0);
 381         treebase_node_initialize(&node1);
 382         treebase_node_initialize(&node2);
 383         treebase_node_initialize(&node3);
 384         treebase_node_initialize(&node4);
 385
 386         treebase_node_appendchild(&node0, &node1);
 387         treebase_node_appendchild(&node1, &node2);
 388         treebase_node_appendchild(&node1, &node3);
 389         treebase_node_appendchild(&node1, &node4);
 390
 391         ret = test_treebase_preordertraversal_common(&node0, expected, expected_len);
 392
 393         treebase_node_finalize(&node4);
 394         treebase_node_finalize(&node3);
 395         treebase_node_finalize(&node2);
 396         treebase_node_finalize(&node1);
 397         treebase_node_finalize(&node0);
 398
 399         return ret;
 400 }
 401
 402
 403 EXPORT VOID test_treebase_main(unittest_driver_t *driver)
 404 {
 405         UNITTEST_DRIVER_REGIST(driver, test_treebase_node_1);
 406         UNITTEST_DRIVER_REGIST(driver, test_treebase_node_2);
 407         UNITTEST_DRIVER_REGIST(driver, test_treebase_node_3);
 408         UNITTEST_DRIVER_REGIST(driver, test_treebase_node_4);
 409         UNITTEST_DRIVER_REGIST(driver, test_treebase_node_5);
 410         UNITTEST_DRIVER_REGIST(driver, test_treebase_node_6);
 411         UNITTEST_DRIVER_REGIST(driver, test_treebase_preordertraversal_1);
 412 }