src/coll/test_treebase.c

   1 /*
   2  * test_treebase.c
   3  *
   4  * Copyright (c) 2013-2014 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 LOCAL UNITTEST_RESULT test_treebase_node_7()
 313 {
 314         treebase_node_t node0, node1, node2, node3;
 315         test_treebase_node_expected_t expected;
 316         Bool ok;
 317         UNITTEST_RESULT ret = UNITTEST_RESULT_PASS;
 318
 319         treebase_node_initialize(&node0);
 320         treebase_node_initialize(&node1);
 321         treebase_node_initialize(&node2);
 322         treebase_node_initialize(&node3);
 323
 324         treebase_node_insertbefore(&node0, &node1, NULL);
 325         treebase_node_insertbefore(&node0, &node2, NULL);
 326         treebase_node_insertbefore(&node0, &node3, &node2);
 327
 328         /**/
 329         expected.parent = NULL;
 330         expected.next = NULL;
 331         expected.prev = NULL;
 332         expected.first = &node1;
 333         expected.last = &node2;
 334         expected.has_child = True;
 335         ok = test_treebase_node_commoncheck(&node0, &expected, "node0");
 336         if (ok == False) {
 337                 ret = UNITTEST_RESULT_FAIL;
 338         }
 339         /**/
 340         expected.parent = &node0;
 341         expected.next = &node3;
 342         expected.prev = NULL;
 343         expected.first = NULL;
 344         expected.last = NULL;
 345         expected.has_child = False;
 346         ok = test_treebase_node_commoncheck(&node1, &expected, "node1");
 347         if (ok == False) {
 348                 ret = UNITTEST_RESULT_FAIL;
 349         }
 350         /**/
 351         expected.parent = &node0;
 352         expected.next = NULL;
 353         expected.prev = &node3;
 354         expected.first = NULL;
 355         expected.last = NULL;
 356         expected.has_child = False;
 357         ok = test_treebase_node_commoncheck(&node2, &expected, "node2");
 358         if (ok == False) {
 359                 ret = UNITTEST_RESULT_FAIL;
 360         }
 361         /**/
 362         expected.parent = &node0;
 363         expected.next = &node2;
 364         expected.prev = &node1;
 365         expected.first = NULL;
 366         expected.last = NULL;
 367         expected.has_child = False;
 368         ok = test_treebase_node_commoncheck(&node3, &expected, "node3");
 369         if (ok == False) {
 370                 ret = UNITTEST_RESULT_FAIL;
 371         }
 372
 373         treebase_node_finalize(&node3);
 374         treebase_node_finalize(&node2);
 375         treebase_node_finalize(&node1);
 376         treebase_node_finalize(&node0);
 377
 378         return ret;
 379 }
 380
 381 /* treebase_preordertraversal_t */
 382
 383 typedef struct {
 384         Bool cont;
 385         treebase_node_t *node;
 386         TREEBASE_TRAVERSAL_DIRECTION dir;
 387 } test_treebase_preordertraversal_expected_t;
 388
 389 LOCAL UNITTEST_RESULT test_treebase_preordertraversal_common(treebase_node_t *root, test_treebase_preordertraversal_expected_t *expected, W expected_len)
 390 {
 391         treebase_node_t *node_result;
 392         treebase_preordertraversal_t traversal;
 393         TREEBASE_TRAVERSAL_DIRECTION dir;
 394         Bool cont;
 395         UNITTEST_RESULT ret = UNITTEST_RESULT_PASS;
 396         W i;
 397
 398         treebase_preordertraversal_initialize(&traversal, root);
 399
 400         for (i = 0;; i++) {
 401                 cont = treebase_preordertraversal_next(&traversal, &node_result, &dir);
 402                 if (i < expected_len) {
 403                         if (expected[i].cont != cont) {
 404                                 printf("%d: cont is not expected\n", i);
 405                                 ret = UNITTEST_RESULT_FAIL;
 406                         }
 407                         if (expected[i].node != node_result) {
 408                                 printf("%d: node is not expected\n", i);
 409                                 ret = UNITTEST_RESULT_FAIL;
 410                         }
 411                         if (expected[i].dir != dir) {
 412                                 printf("%d: direction is not expected\n", i);
 413                                 ret = UNITTEST_RESULT_FAIL;
 414                         }
 415                 }
 416
 417                 if (cont == False) {
 418                         break;
 419                 }
 420         }
 421         if (i != expected_len) {
 422                 printf("node number check fail: expected = %d, result = %d\n", expected_len, i);
 423                 ret = UNITTEST_RESULT_FAIL;
 424         }
 425
 426         treebase_preordertraversal_finalize(&traversal);
 427
 428         return ret;
 429 }
 430
 431 LOCAL UNITTEST_RESULT test_treebase_preordertraversal_1()
 432 {
 433         treebase_node_t node0, node1, node2, node3, node4;
 434         test_treebase_preordertraversal_expected_t expected[] = {
 435                 { True, &node0, TREEBASE_TRAVERSAL_DIRECTION_DOWN },
 436                 { True, &node1, TREEBASE_TRAVERSAL_DIRECTION_DOWN },
 437                 { True, &node2, TREEBASE_TRAVERSAL_DIRECTION_DOWN },
 438                 { True, &node2, TREEBASE_TRAVERSAL_DIRECTION_UP },
 439                 { True, &node3, TREEBASE_TRAVERSAL_DIRECTION_DOWN },
 440                 { True, &node3, TREEBASE_TRAVERSAL_DIRECTION_UP },
 441                 { True, &node4, TREEBASE_TRAVERSAL_DIRECTION_DOWN },
 442                 { True, &node4, TREEBASE_TRAVERSAL_DIRECTION_UP },
 443                 { True, &node1, TREEBASE_TRAVERSAL_DIRECTION_UP },
 444                 { True, &node0, TREEBASE_TRAVERSAL_DIRECTION_UP },
 445         };
 446         W expected_len = sizeof(expected) / sizeof(test_treebase_preordertraversal_expected_t);
 447         UNITTEST_RESULT ret;
 448
 449         treebase_node_initialize(&node0);
 450         treebase_node_initialize(&node1);
 451         treebase_node_initialize(&node2);
 452         treebase_node_initialize(&node3);
 453         treebase_node_initialize(&node4);
 454
 455         treebase_node_appendchild(&node0, &node1);
 456         treebase_node_appendchild(&node1, &node2);
 457         treebase_node_appendchild(&node1, &node3);
 458         treebase_node_appendchild(&node1, &node4);
 459
 460         ret = test_treebase_preordertraversal_common(&node0, expected, expected_len);
 461
 462         treebase_node_finalize(&node4);
 463         treebase_node_finalize(&node3);
 464         treebase_node_finalize(&node2);
 465         treebase_node_finalize(&node1);
 466         treebase_node_finalize(&node0);
 467
 468         return ret;
 469 }
 470
 471
 472 EXPORT VOID test_treebase_main(unittest_driver_t *driver)
 473 {
 474         UNITTEST_DRIVER_REGIST(driver, test_treebase_node_1);
 475         UNITTEST_DRIVER_REGIST(driver, test_treebase_node_2);
 476         UNITTEST_DRIVER_REGIST(driver, test_treebase_node_3);
 477         UNITTEST_DRIVER_REGIST(driver, test_treebase_node_4);
 478         UNITTEST_DRIVER_REGIST(driver, test_treebase_node_5);
 479         UNITTEST_DRIVER_REGIST(driver, test_treebase_node_6);
 480         UNITTEST_DRIVER_REGIST(driver, test_treebase_node_7);
 481         UNITTEST_DRIVER_REGIST(driver, test_treebase_preordertraversal_1);
 482 }