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 LOCAL UNITTEST_RESULT test_treebase_node_8()
 382 {
 383         treebase_node_t node0, node1, node2, node3;
 384         test_treebase_node_expected_t expected;
 385         Bool ok;
 386         UNITTEST_RESULT ret = UNITTEST_RESULT_PASS;
 387
 388         treebase_node_initialize(&node0);
 389         treebase_node_initialize(&node1);
 390         treebase_node_initialize(&node2);
 391         treebase_node_initialize(&node3);
 392
 393         treebase_node_insertbefore(&node0, &node1, NULL);
 394         treebase_node_insertbefore(&node0, &node2, &node1);
 395         treebase_node_insertbefore(&node0, &node3, NULL);
 396
 397         /**/
 398         expected.parent = NULL;
 399         expected.next = NULL;
 400         expected.prev = NULL;
 401         expected.first = &node2;
 402         expected.last = &node3;
 403         expected.has_child = True;
 404         ok = test_treebase_node_commoncheck(&node0, &expected, "node0");
 405         if (ok == False) {
 406                 ret = UNITTEST_RESULT_FAIL;
 407         }
 408         /**/
 409         expected.parent = &node0;
 410         expected.next = &node3;
 411         expected.prev = &node2;
 412         expected.first = NULL;
 413         expected.last = NULL;
 414         expected.has_child = False;
 415         ok = test_treebase_node_commoncheck(&node1, &expected, "node1");
 416         if (ok == False) {
 417                 ret = UNITTEST_RESULT_FAIL;
 418         }
 419         /**/
 420         expected.parent = &node0;
 421         expected.next = &node1;
 422         expected.prev = NULL;
 423         expected.first = NULL;
 424         expected.last = NULL;
 425         expected.has_child = False;
 426         ok = test_treebase_node_commoncheck(&node2, &expected, "node2");
 427         if (ok == False) {
 428                 ret = UNITTEST_RESULT_FAIL;
 429         }
 430         /**/
 431         expected.parent = &node0;
 432         expected.next = NULL;
 433         expected.prev = &node1;
 434         expected.first = NULL;
 435         expected.last = NULL;
 436         expected.has_child = False;
 437         ok = test_treebase_node_commoncheck(&node3, &expected, "node3");
 438         if (ok == False) {
 439                 ret = UNITTEST_RESULT_FAIL;
 440         }
 441
 442         treebase_node_finalize(&node3);
 443         treebase_node_finalize(&node2);
 444         treebase_node_finalize(&node1);
 445         treebase_node_finalize(&node0);
 446
 447         return ret;
 448 }
 449
 450 /* treebase_preordertraversal_t */
 451
 452 typedef struct {
 453         Bool cont;
 454         treebase_node_t *node;
 455         TREEBASE_TRAVERSAL_DIRECTION dir;
 456 } test_treebase_preordertraversal_expected_t;
 457
 458 LOCAL UNITTEST_RESULT test_treebase_preordertraversal_common(treebase_node_t *root, test_treebase_preordertraversal_expected_t *expected, W expected_len)
 459 {
 460         treebase_node_t *node_result;
 461         treebase_preordertraversal_t traversal;
 462         TREEBASE_TRAVERSAL_DIRECTION dir;
 463         Bool cont;
 464         UNITTEST_RESULT ret = UNITTEST_RESULT_PASS;
 465         W i;
 466
 467         treebase_preordertraversal_initialize(&traversal, root);
 468
 469         for (i = 0;; i++) {
 470                 cont = treebase_preordertraversal_next(&traversal, &node_result, &dir);
 471                 if (i < expected_len) {
 472                         if (expected[i].cont != cont) {
 473                                 printf("%d: cont is not expected\n", i);
 474                                 ret = UNITTEST_RESULT_FAIL;
 475                         }
 476                         if (expected[i].node != node_result) {
 477                                 printf("%d: node is not expected\n", i);
 478                                 ret = UNITTEST_RESULT_FAIL;
 479                         }
 480                         if (expected[i].dir != dir) {
 481                                 printf("%d: direction is not expected\n", i);
 482                                 ret = UNITTEST_RESULT_FAIL;
 483                         }
 484                 }
 485
 486                 if (cont == False) {
 487                         break;
 488                 }
 489         }
 490         if (i != expected_len) {
 491                 printf("node number check fail: expected = %d, result = %d\n", expected_len, i);
 492                 ret = UNITTEST_RESULT_FAIL;
 493         }
 494
 495         treebase_preordertraversal_finalize(&traversal);
 496
 497         return ret;
 498 }
 499
 500 LOCAL UNITTEST_RESULT test_treebase_preordertraversal_1()
 501 {
 502         treebase_node_t node0, node1, node2, node3, node4;
 503         test_treebase_preordertraversal_expected_t expected[] = {
 504                 { True, &node0, TREEBASE_TRAVERSAL_DIRECTION_DOWN },
 505                 { True, &node1, TREEBASE_TRAVERSAL_DIRECTION_DOWN },
 506                 { True, &node2, TREEBASE_TRAVERSAL_DIRECTION_DOWN },
 507                 { True, &node2, TREEBASE_TRAVERSAL_DIRECTION_UP },
 508                 { True, &node3, TREEBASE_TRAVERSAL_DIRECTION_DOWN },
 509                 { True, &node3, TREEBASE_TRAVERSAL_DIRECTION_UP },
 510                 { True, &node4, TREEBASE_TRAVERSAL_DIRECTION_DOWN },
 511                 { True, &node4, TREEBASE_TRAVERSAL_DIRECTION_UP },
 512                 { True, &node1, TREEBASE_TRAVERSAL_DIRECTION_UP },
 513                 { True, &node0, TREEBASE_TRAVERSAL_DIRECTION_UP },
 514         };
 515         W expected_len = sizeof(expected) / sizeof(test_treebase_preordertraversal_expected_t);
 516         UNITTEST_RESULT ret;
 517
 518         treebase_node_initialize(&node0);
 519         treebase_node_initialize(&node1);
 520         treebase_node_initialize(&node2);
 521         treebase_node_initialize(&node3);
 522         treebase_node_initialize(&node4);
 523
 524         treebase_node_appendchild(&node0, &node1);
 525         treebase_node_appendchild(&node1, &node2);
 526         treebase_node_appendchild(&node1, &node3);
 527         treebase_node_appendchild(&node1, &node4);
 528
 529         ret = test_treebase_preordertraversal_common(&node0, expected, expected_len);
 530
 531         treebase_node_finalize(&node4);
 532         treebase_node_finalize(&node3);
 533         treebase_node_finalize(&node2);
 534         treebase_node_finalize(&node1);
 535         treebase_node_finalize(&node0);
 536
 537         return ret;
 538 }
 539
 540
 541 EXPORT VOID test_treebase_main(unittest_driver_t *driver)
 542 {
 543         UNITTEST_DRIVER_REGIST(driver, test_treebase_node_1);
 544         UNITTEST_DRIVER_REGIST(driver, test_treebase_node_2);
 545         UNITTEST_DRIVER_REGIST(driver, test_treebase_node_3);
 546         UNITTEST_DRIVER_REGIST(driver, test_treebase_node_4);
 547         UNITTEST_DRIVER_REGIST(driver, test_treebase_node_5);
 548         UNITTEST_DRIVER_REGIST(driver, test_treebase_node_6);
 549         UNITTEST_DRIVER_REGIST(driver, test_treebase_node_7);
 550         UNITTEST_DRIVER_REGIST(driver, test_treebase_node_8);
 551         UNITTEST_DRIVER_REGIST(driver, test_treebase_preordertraversal_1);
 552 }