UNIXworkcode

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 */ 28 29 #include "cx/tree.h" 30 31 #include "cx/test.h" 32 33 #include "util_allocator.h" 34 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; 42 43 typedef struct tree_node2 { 44 CX_TREE_NODE_BASE(struct tree_node2); 45 int data; 46 } tree_node2; 47 48 typedef struct tree_node_file { 49 struct tree_node_file *parent; 50 struct tree_node_file *next; 51 struct tree_node_file *prev; 52 struct tree_node_file *children; 53 struct tree_node_file *last_child; 54 const char *path; 55 } tree_node_file; 56 57 static void *tree_node_file_create( 58 const void *dptr, 59 void *allocator) { 60 if (allocator == NULL) allocator = (void*) cxDefaultAllocator; 61 62 tree_node_file *node = cxMalloc(allocator, sizeof(tree_node_file)); 63 node->path = dptr; 64 65 // intentionally write garbage into the pointers, it's part of the test 66 node->parent = (void *) 0xf00ba1; 67 node->next = (void *) 0xf00ba2; 68 node->prev = (void *) 0xf00ba3; 69 node->children = (void *) 0xf00ba4; 70 node->last_child = (void *) 0xf00ba5; 71 72 return node; 73 } 74 75 static void *tree_node_file_create_hl( 76 const void *dptr, 77 void *tree) { 78 return tree_node_file_create(dptr, (void*)((CxTree*)tree)->collection.allocator); 79 } 80 81 static int tree_node_file_search(const void *l, const void *r) { 82 const tree_node_file *left = l; 83 const tree_node_file *right = r; 84 size_t len1 = strlen(left->path); 85 size_t len2 = strlen(right->path); 86 if (len1 <= len2) { 87 if (memcmp(left->path, right->path, len1) == 0) { 88 return (int) (len2 - len1); 89 } else { 90 return -1; 91 } 92 } else { 93 return -1; 94 } 95 } 96 97 static int tree_node_file_search_data(const void *l, const void *d) { 98 tree_node_file r; 99 r.path = d; 100 return tree_node_file_search(l, &r); 101 } 102 103 #define tree_node_layout \ 104 offsetof(tree_node, parent), offsetof(tree_node, children), -1, \ 105 offsetof(tree_node, prev), offsetof(tree_node, next) 106 #define tree_node_layout_no_prev \ 107 offsetof(tree_node, parent), offsetof(tree_node, children), -1, -1, \ 108 offsetof(tree_node, next) 109 #define tree_node_full_layout(structname) \ 110 offsetof(structname, parent), offsetof(structname, children),\ 111 offsetof(structname, last_child), \ 112 offsetof(structname, prev), offsetof(structname, next) 113 #define tree_node2_layout cx_tree_node_base_layout 114 #define tree_node_file_layout tree_node_full_layout(tree_node_file) 115 116 #define tree_children(type) offsetof(type, children), offsetof(type, next) 117 118 CX_TEST(test_tree_link_new_child) { 119 tree_node parent = {0}; 120 tree_node child = {0}; 121 122 CX_TEST_DO { 123 cx_tree_link(&parent, &child, tree_node_layout); 124 CX_TEST_ASSERT(parent.next == NULL); 125 CX_TEST_ASSERT(parent.prev == NULL); 126 CX_TEST_ASSERT(parent.parent == NULL); 127 CX_TEST_ASSERT(parent.children == &child); 128 CX_TEST_ASSERT(child.parent == &parent); 129 CX_TEST_ASSERT(child.next == NULL); 130 CX_TEST_ASSERT(child.prev == NULL); 131 CX_TEST_ASSERT(child.children == NULL); 132 } 133 } 134 135 CX_TEST(test_tree_link_add_child) { 136 tree_node parent = {0}; 137 tree_node child1 = {0}; 138 tree_node child2 = {0}; 139 tree_node child3 = {0}; 140 141 CX_TEST_DO { 142 cx_tree_link(&parent, &child1, tree_node_layout); 143 cx_tree_link(&parent, &child2, tree_node_layout); 144 cx_tree_link(&parent, &child3, tree_node_layout); 145 CX_TEST_ASSERT(parent.next == NULL); 146 CX_TEST_ASSERT(parent.prev == NULL); 147 CX_TEST_ASSERT(parent.parent == NULL); 148 CX_TEST_ASSERT(parent.children == &child1); 149 150 CX_TEST_ASSERT(child1.parent == &parent); 151 CX_TEST_ASSERT(child2.parent == &parent); 152 CX_TEST_ASSERT(child3.parent == &parent); 153 CX_TEST_ASSERT(child1.children == NULL); 154 CX_TEST_ASSERT(child2.children == NULL); 155 CX_TEST_ASSERT(child3.children == NULL); 156 157 CX_TEST_ASSERT(child1.prev == NULL); 158 CX_TEST_ASSERT(child1.next == &child2); 159 CX_TEST_ASSERT(child2.prev == &child1); 160 CX_TEST_ASSERT(child2.next == &child3); 161 CX_TEST_ASSERT(child3.prev == &child2); 162 CX_TEST_ASSERT(child3.next == NULL); 163 } 164 } 165 166 CX_TEST(test_tree_link_move_to_other_parent) { 167 tree_node parent = {0}; 168 tree_node child1 = {0}; 169 tree_node child2 = {0}; 170 tree_node child3 = {0}; 171 cx_tree_link(&parent, &child1, tree_node_layout); 172 cx_tree_link(&parent, &child2, tree_node_layout); 173 cx_tree_link(&parent, &child3, tree_node_layout); 174 175 CX_TEST_DO { 176 cx_tree_link(&child3, &child2, tree_node_layout); 177 178 CX_TEST_ASSERT(parent.next == NULL); 179 CX_TEST_ASSERT(parent.prev == NULL); 180 CX_TEST_ASSERT(parent.parent == NULL); 181 CX_TEST_ASSERT(parent.children == &child1); 182 183 CX_TEST_ASSERT(child1.parent == &parent); 184 CX_TEST_ASSERT(child2.parent == &child3); 185 CX_TEST_ASSERT(child3.parent == &parent); 186 CX_TEST_ASSERT(child1.children == NULL); 187 CX_TEST_ASSERT(child2.children == NULL); 188 CX_TEST_ASSERT(child3.children == &child2); 189 190 CX_TEST_ASSERT(child1.prev == NULL); 191 CX_TEST_ASSERT(child1.next == &child3); 192 CX_TEST_ASSERT(child3.prev == &child1); 193 CX_TEST_ASSERT(child3.next == NULL); 194 195 CX_TEST_ASSERT(child2.prev == NULL); 196 CX_TEST_ASSERT(child2.next == NULL); 197 } 198 } 199 200 CX_TEST(test_tree_unlink) { 201 tree_node parent = {0}; 202 tree_node child1 = {0}; 203 tree_node child2 = {0}; 204 tree_node child3 = {0}; 205 tree_node child4 = {0}; 206 cx_tree_link(&parent, &child1, tree_node_layout); 207 cx_tree_link(&parent, &child3, tree_node_layout); 208 cx_tree_link(&parent, &child4, tree_node_layout); 209 cx_tree_link(&child3, &child2, tree_node_layout); 210 211 CX_TEST_DO { 212 cx_tree_unlink(&child3, tree_node_layout); 213 214 CX_TEST_ASSERT(parent.next == NULL); 215 CX_TEST_ASSERT(parent.prev == NULL); 216 CX_TEST_ASSERT(parent.parent == NULL); 217 CX_TEST_ASSERT(parent.children == &child1); 218 219 CX_TEST_ASSERT(child1.parent == &parent); 220 CX_TEST_ASSERT(child1.children == NULL); 221 CX_TEST_ASSERT(child1.prev == NULL); 222 CX_TEST_ASSERT(child1.next == &child4); 223 224 CX_TEST_ASSERT(child4.parent == &parent); 225 CX_TEST_ASSERT(child4.children == NULL); 226 CX_TEST_ASSERT(child4.prev == &child1); 227 CX_TEST_ASSERT(child4.next == NULL); 228 229 // child 3 is unlinked 230 CX_TEST_ASSERT(child3.parent == NULL); 231 CX_TEST_ASSERT(child3.prev == NULL); 232 CX_TEST_ASSERT(child3.next == NULL); 233 234 // child 2 is still child of the unlinked child 3 235 CX_TEST_ASSERT(child3.children == &child2); 236 CX_TEST_ASSERT(child2.parent == &child3); 237 CX_TEST_ASSERT(child2.children == NULL); 238 CX_TEST_ASSERT(child2.prev == NULL); 239 CX_TEST_ASSERT(child2.next == NULL); 240 241 // unlink first child from parent 242 cx_tree_unlink(&child1, tree_node_layout); 243 CX_TEST_ASSERT(parent.next == NULL); 244 CX_TEST_ASSERT(parent.prev == NULL); 245 CX_TEST_ASSERT(parent.parent == NULL); 246 CX_TEST_ASSERT(parent.children == &child4); 247 CX_TEST_ASSERT(child1.parent == NULL); 248 CX_TEST_ASSERT(child4.parent == &parent); 249 CX_TEST_ASSERT(child4.children == NULL); 250 CX_TEST_ASSERT(child4.prev == NULL); 251 CX_TEST_ASSERT(child4.next == NULL); 252 } 253 } 254 255 CX_TEST(test_tree_unlink_no_prev) { 256 tree_node parent = {0}; 257 tree_node child1 = {0}; 258 tree_node child2 = {0}; 259 tree_node child3 = {0}; 260 tree_node child4 = {0}; 261 cx_tree_link(&parent, &child1, tree_node_layout_no_prev); 262 cx_tree_link(&parent, &child3, tree_node_layout_no_prev); 263 cx_tree_link(&parent, &child4, tree_node_layout_no_prev); 264 cx_tree_link(&child3, &child2, tree_node_layout_no_prev); 265 void * const marker = (void*) 0xc0ffee; 266 child1.prev = child2.prev = child3.prev = child4.prev = marker; 267 268 CX_TEST_DO { 269 // in contrast to the other test we here remove child 4 instead of 3! 270 cx_tree_unlink(&child4, tree_node_layout_no_prev); 271 272 CX_TEST_ASSERT(parent.next == NULL); 273 CX_TEST_ASSERT(parent.prev == NULL); 274 CX_TEST_ASSERT(parent.parent == NULL); 275 CX_TEST_ASSERT(parent.children == &child1); 276 277 CX_TEST_ASSERT(child1.parent == &parent); 278 CX_TEST_ASSERT(child1.children == NULL); 279 CX_TEST_ASSERT(child1.prev == marker); 280 CX_TEST_ASSERT(child1.next == &child3); 281 282 // child 4 is unlinked 283 CX_TEST_ASSERT(child4.parent == NULL); 284 CX_TEST_ASSERT(child4.children == NULL); 285 CX_TEST_ASSERT(child4.prev == marker); 286 CX_TEST_ASSERT(child4.next == NULL); 287 288 // unlink first child from parent 289 cx_tree_unlink(&child1, tree_node_layout_no_prev); 290 CX_TEST_ASSERT(parent.next == NULL); 291 CX_TEST_ASSERT(parent.prev == NULL); 292 CX_TEST_ASSERT(parent.parent == NULL); 293 CX_TEST_ASSERT(parent.children == &child3); 294 CX_TEST_ASSERT(child1.parent == NULL); 295 CX_TEST_ASSERT(child3.parent == &parent); 296 CX_TEST_ASSERT(child3.children == &child2); 297 CX_TEST_ASSERT(child3.prev == marker); 298 CX_TEST_ASSERT(child3.next == NULL); 299 } 300 } 301 302 CX_TEST(test_tree2_link_new_child) { 303 tree_node2 parent = {0}; 304 tree_node2 child = {0}; 305 306 CX_TEST_DO { 307 cx_tree_link(&parent, &child, tree_node2_layout); 308 CX_TEST_ASSERT(parent.next == NULL); 309 CX_TEST_ASSERT(parent.prev == NULL); 310 CX_TEST_ASSERT(parent.parent == NULL); 311 CX_TEST_ASSERT(parent.children == &child); 312 CX_TEST_ASSERT(parent.last_child == &child); 313 CX_TEST_ASSERT(child.parent == &parent); 314 CX_TEST_ASSERT(child.next == NULL); 315 CX_TEST_ASSERT(child.prev == NULL); 316 CX_TEST_ASSERT(child.children == NULL); 317 CX_TEST_ASSERT(child.last_child == NULL); 318 } 319 } 320 321 CX_TEST(test_tree2_link_add_child) { 322 tree_node2 parent = {0}; 323 tree_node2 child1 = {0}; 324 tree_node2 child2 = {0}; 325 tree_node2 child3 = {0}; 326 327 CX_TEST_DO { 328 cx_tree_link(&parent, &child1, tree_node2_layout); 329 cx_tree_link(&parent, &child2, tree_node2_layout); 330 cx_tree_link(&parent, &child3, tree_node2_layout); 331 CX_TEST_ASSERT(parent.next == NULL); 332 CX_TEST_ASSERT(parent.prev == NULL); 333 CX_TEST_ASSERT(parent.parent == NULL); 334 CX_TEST_ASSERT(parent.children == &child1); 335 CX_TEST_ASSERT(parent.last_child == &child3); 336 337 CX_TEST_ASSERT(child1.parent == &parent); 338 CX_TEST_ASSERT(child2.parent == &parent); 339 CX_TEST_ASSERT(child3.parent == &parent); 340 CX_TEST_ASSERT(child1.children == NULL); 341 CX_TEST_ASSERT(child2.children == NULL); 342 CX_TEST_ASSERT(child3.children == NULL); 343 CX_TEST_ASSERT(child1.last_child == NULL); 344 CX_TEST_ASSERT(child2.last_child == NULL); 345 CX_TEST_ASSERT(child3.last_child == NULL); 346 347 CX_TEST_ASSERT(child1.prev == NULL); 348 CX_TEST_ASSERT(child1.next == &child2); 349 CX_TEST_ASSERT(child2.prev == &child1); 350 CX_TEST_ASSERT(child2.next == &child3); 351 CX_TEST_ASSERT(child3.prev == &child2); 352 CX_TEST_ASSERT(child3.next == NULL); 353 } 354 } 355 356 CX_TEST(test_tree2_link_move_to_other_parent) { 357 tree_node2 parent = {0}; 358 tree_node2 child1 = {0}; 359 tree_node2 child2 = {0}; 360 tree_node2 child3 = {0}; 361 cx_tree_link(&parent, &child1, tree_node2_layout); 362 cx_tree_link(&parent, &child2, tree_node2_layout); 363 cx_tree_link(&parent, &child3, tree_node2_layout); 364 365 CX_TEST_DO { 366 cx_tree_link(&child3, &child2, tree_node2_layout); 367 368 CX_TEST_ASSERT(parent.next == NULL); 369 CX_TEST_ASSERT(parent.prev == NULL); 370 CX_TEST_ASSERT(parent.parent == NULL); 371 CX_TEST_ASSERT(parent.children == &child1); 372 CX_TEST_ASSERT(parent.last_child == &child3); 373 374 CX_TEST_ASSERT(child1.parent == &parent); 375 CX_TEST_ASSERT(child2.parent == &child3); 376 CX_TEST_ASSERT(child3.parent == &parent); 377 CX_TEST_ASSERT(child1.children == NULL); 378 CX_TEST_ASSERT(child2.children == NULL); 379 CX_TEST_ASSERT(child3.children == &child2); 380 CX_TEST_ASSERT(child1.last_child == NULL); 381 CX_TEST_ASSERT(child2.last_child == NULL); 382 CX_TEST_ASSERT(child3.last_child == &child2); 383 384 CX_TEST_ASSERT(child1.prev == NULL); 385 CX_TEST_ASSERT(child1.next == &child3); 386 CX_TEST_ASSERT(child3.prev == &child1); 387 CX_TEST_ASSERT(child3.next == NULL); 388 389 CX_TEST_ASSERT(child2.prev == NULL); 390 CX_TEST_ASSERT(child2.next == NULL); 391 } 392 } 393 394 CX_TEST(test_tree2_unlink) { 395 tree_node2 parent = {0}; 396 tree_node2 child1 = {0}; 397 tree_node2 child2 = {0}; 398 tree_node2 child3 = {0}; 399 cx_tree_link(&parent, &child1, tree_node2_layout); 400 cx_tree_link(&parent, &child3, tree_node2_layout); 401 cx_tree_link(&child3, &child2, tree_node2_layout); 402 403 CX_TEST_DO { 404 cx_tree_unlink(&child3, tree_node2_layout); 405 406 CX_TEST_ASSERT(parent.next == NULL); 407 CX_TEST_ASSERT(parent.prev == NULL); 408 CX_TEST_ASSERT(parent.parent == NULL); 409 CX_TEST_ASSERT(parent.children == &child1); 410 CX_TEST_ASSERT(parent.last_child == &child1); 411 412 CX_TEST_ASSERT(child1.parent == &parent); 413 CX_TEST_ASSERT(child1.children == NULL); 414 CX_TEST_ASSERT(child1.last_child == NULL); 415 CX_TEST_ASSERT(child1.prev == NULL); 416 CX_TEST_ASSERT(child1.next == NULL); 417 418 // child 3 is unlinked 419 CX_TEST_ASSERT(child3.parent == NULL); 420 CX_TEST_ASSERT(child3.prev == NULL); 421 CX_TEST_ASSERT(child3.next == NULL); 422 423 // child 2 is still child of the unlinked child 3 424 CX_TEST_ASSERT(child3.children == &child2); 425 CX_TEST_ASSERT(child3.last_child == &child2); 426 CX_TEST_ASSERT(child2.parent == &child3); 427 CX_TEST_ASSERT(child2.children == NULL); 428 CX_TEST_ASSERT(child2.last_child == NULL); 429 CX_TEST_ASSERT(child2.prev == NULL); 430 CX_TEST_ASSERT(child2.next == NULL); 431 432 // unlink last child from parent 433 cx_tree_unlink(&child1, tree_node2_layout); 434 CX_TEST_ASSERT(parent.next == NULL); 435 CX_TEST_ASSERT(parent.prev == NULL); 436 CX_TEST_ASSERT(parent.parent == NULL); 437 CX_TEST_ASSERT(parent.children == NULL); 438 CX_TEST_ASSERT(parent.last_child == NULL); 439 CX_TEST_ASSERT(child1.parent == NULL); 440 } 441 } 442 443 static int test_tree_search_function(const void *n, const void *d) { 444 const tree_node *node = n; 445 int data = *((const int *)d); 446 447 if (data < node->data) return -1; 448 else if (data == node->data) return 0; 449 else return data - node->data; 450 } 451 452 CX_TEST(test_tree_search) { 453 tree_node root = {0}; 454 tree_node a = {0}; 455 tree_node b = {0}; 456 tree_node c = {0}; 457 tree_node aa = {0}; 458 tree_node ab = {0}; 459 tree_node ba = {0}; 460 tree_node ca = {0}; 461 tree_node cb = {0}; 462 tree_node cc = {0}; 463 tree_node cba = {0}; 464 465 int testdata[] = {0, 10, 14, 18, 20, 25, 30, 32, 34, 36, 40}; 466 tree_node* testnodes[] = {&root, &a, &aa, &ab, &b, &ba, &c, &ca, &cb, &cba, &cc}; 467 468 for (unsigned i = 0 ; i <= 10 ; i++) { 469 testnodes[i]->data = testdata[i]; 470 } 471 472 cx_tree_link(&root, &a, tree_node_layout); 473 cx_tree_link(&root, &b, tree_node_layout); 474 cx_tree_link(&root, &c, tree_node_layout); 475 476 cx_tree_link(&a, &aa, tree_node_layout); 477 cx_tree_link(&a, &ab, tree_node_layout); 478 479 cx_tree_link(&b, &ba, tree_node_layout); 480 481 cx_tree_link(&c, &ca, tree_node_layout); 482 cx_tree_link(&c, &cb, tree_node_layout); 483 cx_tree_link(&c, &cc, tree_node_layout); 484 485 cx_tree_link(&cb, &cba, tree_node_layout); 486 487 int s; 488 int r; 489 tree_node *n; 490 CX_TEST_DO { 491 for (unsigned i = 0 ; i <= 10 ; i++) { 492 s = testdata[i]; 493 r = cx_tree_search_data(&root, 0, &s, test_tree_search_function, 494 (void **) &n, tree_children(tree_node)); 495 CX_TEST_ASSERT(r == 0); 496 CX_TEST_ASSERT(n == testnodes[i]); 497 } 498 499 s = -5; 500 r = cx_tree_search_data(&root, 0, &s, test_tree_search_function, 501 (void **) &n, tree_children(tree_node)); 502 CX_TEST_ASSERT(r < 0); 503 CX_TEST_ASSERT(n == NULL); 504 505 s = 26; 506 r = cx_tree_search_data(&root, 0, &s, test_tree_search_function, 507 (void **) &n, tree_children(tree_node)); 508 CX_TEST_ASSERT(r > 0); 509 CX_TEST_ASSERT(n == &ba); 510 511 s = 35; 512 r = cx_tree_search_data(&root, 0, &s, test_tree_search_function, 513 (void **) &n, tree_children(tree_node)); 514 CX_TEST_ASSERT(r > 0); 515 CX_TEST_ASSERT(n == &cb); 516 517 s = 38; 518 r = cx_tree_search_data(&root, 0, &s, test_tree_search_function, 519 (void **) &n, tree_children(tree_node)); 520 CX_TEST_ASSERT(r > 0); 521 CX_TEST_ASSERT(n == &cba); 522 523 s = 42; 524 r = cx_tree_search_data(&root, 0, &s, test_tree_search_function, 525 (void **) &n, tree_children(tree_node)); 526 CX_TEST_ASSERT(r > 0); 527 CX_TEST_ASSERT(n == &cc); 528 } 529 } 530 531 CX_TEST(test_tree_search_with_max_depth) { 532 tree_node_file root = {0}; 533 root.path = "/"; 534 tree_node_file usr = {0}; 535 usr.path = "/usr/"; 536 cx_tree_link(&root, &usr, tree_node_file_layout); 537 tree_node_file home = {0}; 538 home.path = "/home/"; 539 cx_tree_link(&root, &home, tree_node_file_layout); 540 tree_node_file doe = {0}; 541 doe.path = "/home/doe/"; 542 cx_tree_link(&home, &doe, tree_node_file_layout); 543 tree_node_file lib = {0}; 544 lib.path = "/usr/lib/"; 545 cx_tree_link(&usr, &lib, tree_node_file_layout); 546 tree_node_file modules = {0}; 547 modules.path = "/usr/lib/modules/"; 548 cx_tree_link(&lib, &modules, tree_node_file_layout); 549 550 CX_TEST_DO { 551 int result; 552 void *found; 553 554 result = cx_tree_search_data( 555 &root, 1, "/", 556 tree_node_file_search_data, &found, 557 tree_children(tree_node_file) 558 ); 559 CX_TEST_ASSERTM(result == 0, "root not found"); 560 CX_TEST_ASSERT(found == &root); 561 562 result = cx_tree_search_data( 563 &root, 1, "/usr/", 564 tree_node_file_search_data, &found, 565 tree_children(tree_node_file) 566 ); 567 CX_TEST_ASSERT(result > 0); 568 CX_TEST_ASSERT(found == &root); 569 570 result = cx_tree_search_data( 571 &root, 2, "/usr/", 572 tree_node_file_search_data, &found, 573 tree_children(tree_node_file) 574 ); 575 CX_TEST_ASSERT(result == 0); 576 CX_TEST_ASSERT(found == &usr); 577 578 result = cx_tree_search_data( 579 &root, 2, "/usr/lib/", 580 tree_node_file_search_data, &found, 581 tree_children(tree_node_file) 582 ); 583 CX_TEST_ASSERT(result > 0); 584 CX_TEST_ASSERT(found == &usr); 585 586 result = cx_tree_search_data( 587 &root, 3, "/usr/lib/", 588 tree_node_file_search_data, &found, 589 tree_children(tree_node_file) 590 ); 591 CX_TEST_ASSERTM(result == 0, "lib not found"); 592 CX_TEST_ASSERT(found == &lib); 593 594 result = cx_tree_search_data( 595 &root, 1, "/home/", 596 tree_node_file_search_data, &found, 597 tree_children(tree_node_file) 598 ); 599 CX_TEST_ASSERT(result > 0); 600 CX_TEST_ASSERT(found == &root); 601 602 result = cx_tree_search_data( 603 &root, 2, "/home/", 604 tree_node_file_search_data, &found, 605 tree_children(tree_node_file) 606 ); 607 CX_TEST_ASSERTM(result == 0, "home not found"); 608 CX_TEST_ASSERT(found == &home); 609 610 result = cx_tree_search_data( 611 &root, 2, "/home/doe/", 612 tree_node_file_search_data, &found, 613 tree_children(tree_node_file) 614 ); 615 CX_TEST_ASSERT(result > 0); 616 CX_TEST_ASSERT(found == &home); 617 618 result = cx_tree_search_data( 619 &root, 3, "/home/doe/", 620 tree_node_file_search_data, &found, 621 tree_children(tree_node_file) 622 ); 623 CX_TEST_ASSERTM(result == 0, "doe not found"); 624 CX_TEST_ASSERT(found == &doe); 625 626 result = cx_tree_search_data( 627 &root, 3, "/usr/lib/modules/", 628 tree_node_file_search_data, &found, 629 tree_children(tree_node_file) 630 ); 631 CX_TEST_ASSERT(result > 0); 632 CX_TEST_ASSERT(found == &lib); 633 634 result = cx_tree_search_data( 635 &root, 4, "/usr/lib/modules/", 636 tree_node_file_search_data, &found, 637 tree_children(tree_node_file) 638 ); 639 CX_TEST_ASSERTM(result == 0, "modules not found (start=root)"); 640 CX_TEST_ASSERT(found == &modules); 641 642 result = cx_tree_search_data( 643 &usr, 3, "/usr/lib/modules/", 644 tree_node_file_search_data, &found, 645 tree_children(tree_node_file) 646 ); 647 CX_TEST_ASSERTM(result == 0, "modules not found (start=usr)"); 648 CX_TEST_ASSERT(found == &modules); 649 } 650 } 651 652 CX_TEST(test_tree_iterator_create_and_dispose) { 653 tree_node root; 654 CX_TEST_DO { 655 CxTreeIterator iter = cx_tree_iterator(&root, false, tree_children(tree_node)); 656 CX_TEST_ASSERT(!iter.visit_on_exit); 657 CX_TEST_ASSERT(!iter.exiting); 658 CX_TEST_ASSERT(iter.counter == 1); 659 CX_TEST_ASSERT(iter.node == &root); 660 CX_TEST_ASSERT(!iter.base.allow_remove); 661 CX_TEST_ASSERT(!iter.base.remove); 662 CX_TEST_ASSERT(iter.stack != NULL); 663 CX_TEST_ASSERT(iter.stack_capacity > 0); 664 CX_TEST_ASSERT(iter.stack_size == 1); 665 CX_TEST_ASSERT(iter.depth == 1); 666 CX_TEST_ASSERT(iter.loc_next == offsetof(tree_node, next)); 667 CX_TEST_ASSERT(iter.loc_children == offsetof(tree_node, children)); 668 cxTreeIteratorDispose(&iter); 669 CX_TEST_ASSERT(iter.stack == NULL); 670 } 671 } 672 673 CX_TEST(test_tree_iterator_create_for_empty_tree) { 674 CX_TEST_DO { 675 CxTreeIterator iter = cx_tree_iterator(NULL, false, tree_children(tree_node)); 676 CX_TEST_ASSERT(!iter.visit_on_exit); 677 CX_TEST_ASSERT(!iter.exiting); 678 CX_TEST_ASSERT(iter.counter == 0); 679 CX_TEST_ASSERT(iter.node == NULL); 680 CX_TEST_ASSERT(!iter.base.allow_remove); 681 CX_TEST_ASSERT(!iter.base.remove); 682 CX_TEST_ASSERT(iter.stack == NULL); 683 CX_TEST_ASSERT(iter.stack_capacity == 0); 684 CX_TEST_ASSERT(iter.stack_size == 0); 685 CX_TEST_ASSERT(iter.depth == 0); 686 CX_TEST_ASSERT(iter.loc_next == offsetof(tree_node, next)); 687 CX_TEST_ASSERT(iter.loc_children == offsetof(tree_node, children)); 688 CX_TEST_ASSERT(!cxIteratorValid(iter)); 689 // disposing this iterator should also be harmless 690 cxTreeIteratorDispose(&iter); 691 } 692 } 693 694 CX_TEST(test_tree_iterator_basic_only_enter) { 695 tree_node root = {0}; 696 tree_node a = {0}; 697 tree_node b = {0}; 698 tree_node c = {0}; 699 tree_node aa = {0}; 700 tree_node ab = {0}; 701 tree_node ba = {0}; 702 tree_node ca = {0}; 703 tree_node cb = {0}; 704 tree_node cc = {0}; 705 tree_node cba = {0}; 706 707 tree_node* expected_order[] = { 708 &root, 709 &a, &aa, &ab, 710 &b, &ba, 711 &c, &ca, &cb, &cba, &cc, 712 }; 713 tree_node* actual_order[16]; // reserve more space in case s.t. goes wrong 714 715 cx_tree_link(&root, &a, tree_node_layout); 716 cx_tree_link(&root, &b, tree_node_layout); 717 cx_tree_link(&root, &c, tree_node_layout); 718 cx_tree_link(&a, &aa, tree_node_layout); 719 cx_tree_link(&a, &ab, tree_node_layout); 720 cx_tree_link(&b, &ba, tree_node_layout); 721 cx_tree_link(&c, &ca, tree_node_layout); 722 cx_tree_link(&c, &cb, tree_node_layout); 723 cx_tree_link(&c, &cc, tree_node_layout); 724 cx_tree_link(&cb, &cba, tree_node_layout); 725 CX_TEST_DO { 726 CxTreeIterator iter = cx_tree_iterator(&root, false, tree_children(tree_node)); 727 unsigned chk = 0; 728 cx_foreach(tree_node*, node, iter) { 729 CX_TEST_ASSERT(node->data == 0); 730 node->data++; 731 actual_order[chk] = node; 732 chk++; 733 CX_TEST_ASSERT(node == iter.node); 734 CX_TEST_ASSERT(!iter.exiting); 735 if (node == &root) { 736 CX_TEST_ASSERT(iter.depth == 1); 737 } else if (node == &a || node == &b || node == &c) { 738 CX_TEST_ASSERT(iter.depth == 2); 739 } else if (node == &cba) { 740 CX_TEST_ASSERT(iter.depth == 4); 741 } else { 742 CX_TEST_ASSERT(iter.depth == 3); 743 } 744 } 745 CX_TEST_ASSERT(iter.counter == 11); 746 CX_TEST_ASSERT(chk == 11); 747 for (unsigned i = 0 ; i < chk ; i++) { 748 CX_TEST_ASSERT(actual_order[i] == expected_order[i]); 749 CX_TEST_ASSERT(actual_order[i]->data == 1); 750 } 751 CX_TEST_ASSERT(iter.stack == NULL); 752 } 753 } 754 755 CX_TEST(test_tree_iterator_basic_enter_and_exit) { 756 tree_node root = {0}; 757 tree_node a = {0}; 758 tree_node b = {0}; 759 tree_node c = {0}; 760 tree_node aa = {0}; 761 tree_node ab = {0}; 762 tree_node ba = {0}; 763 tree_node ca = {0}; 764 tree_node cb = {0}; 765 tree_node cc = {0}; 766 tree_node cba = {0}; 767 768 cx_tree_link(&root, &a, tree_node_layout); 769 cx_tree_link(&root, &b, tree_node_layout); 770 cx_tree_link(&root, &c, tree_node_layout); 771 cx_tree_link(&a, &aa, tree_node_layout); 772 cx_tree_link(&a, &ab, tree_node_layout); 773 cx_tree_link(&b, &ba, tree_node_layout); 774 cx_tree_link(&c, &ca, tree_node_layout); 775 cx_tree_link(&c, &cb, tree_node_layout); 776 cx_tree_link(&c, &cc, tree_node_layout); 777 cx_tree_link(&cb, &cba, tree_node_layout); 778 CX_TEST_DO { 779 CxTreeIterator iter = cx_tree_iterator(&root, true, tree_children(tree_node)); 780 unsigned chk = 0; 781 cx_foreach(tree_node*, node, iter) { 782 CX_TEST_ASSERT(iter.exiting || node->data == 0); 783 node->data++; 784 chk++; 785 CX_TEST_ASSERT(node == iter.node); 786 if (node == &root) { 787 CX_TEST_ASSERT(iter.depth == 1); 788 } else if (node == &a || node == &b || node == &c) { 789 CX_TEST_ASSERT(iter.depth == 2); 790 } else if (node == &cba) { 791 CX_TEST_ASSERT(iter.depth == 4); 792 } else { 793 CX_TEST_ASSERT(iter.depth == 3); 794 } 795 } 796 CX_TEST_ASSERT(iter.counter == 11); 797 CX_TEST_ASSERT(chk == 22); 798 CX_TEST_ASSERT(iter.stack == NULL); 799 CX_TEST_ASSERT(root.data == 2); 800 CX_TEST_ASSERT(a.data == 2); 801 CX_TEST_ASSERT(b.data == 2); 802 CX_TEST_ASSERT(c.data == 2); 803 CX_TEST_ASSERT(aa.data == 2); 804 CX_TEST_ASSERT(ab.data == 2); 805 CX_TEST_ASSERT(ba.data == 2); 806 CX_TEST_ASSERT(ca.data == 2); 807 CX_TEST_ASSERT(cb.data == 2); 808 CX_TEST_ASSERT(cc.data == 2); 809 CX_TEST_ASSERT(cba.data == 2); 810 } 811 } 812 813 CX_TEST(test_tree_iterator_subtree_enter_and_exit) { 814 tree_node root = { 0 }; 815 tree_node a = { 0 }; 816 tree_node b = { 0 }; 817 tree_node c = { 0 }; 818 tree_node aa = { 0 }; 819 tree_node ab = { 0 }; 820 tree_node ba = { 0 }; 821 tree_node ca = { 0 }; 822 tree_node cb = { 0 }; 823 tree_node cc = { 0 }; 824 tree_node cba = { 0 }; 825 826 cx_tree_link(&root, &a, tree_node_layout); 827 cx_tree_link(&root, &b, tree_node_layout); 828 cx_tree_link(&root, &c, tree_node_layout); 829 cx_tree_link(&a, &aa, tree_node_layout); 830 cx_tree_link(&a, &ab, tree_node_layout); 831 cx_tree_link(&b, &ba, tree_node_layout); 832 cx_tree_link(&c, &ca, tree_node_layout); 833 cx_tree_link(&c, &cb, tree_node_layout); 834 cx_tree_link(&c, &cc, tree_node_layout); 835 cx_tree_link(&cb, &cba, tree_node_layout); 836 CX_TEST_DO{ 837 CxTreeIterator iter = cx_tree_iterator(&b, true, tree_children(tree_node)); 838 unsigned chk = 0; 839 cx_foreach(tree_node*, node, iter) { 840 CX_TEST_ASSERT(iter.exiting || node->data == 0); 841 node->data++; 842 chk++; 843 CX_TEST_ASSERT(node == iter.node); 844 if (node == &b) { 845 CX_TEST_ASSERT(iter.depth == 1); 846 } else if (node == &ba) { 847 CX_TEST_ASSERT(iter.depth == 2); 848 } 849 } 850 CX_TEST_ASSERT(iter.counter == 2); 851 CX_TEST_ASSERT(chk == 4); 852 CX_TEST_ASSERT(iter.stack == NULL); 853 CX_TEST_ASSERT(root.data == 0); 854 CX_TEST_ASSERT(a.data == 0); 855 CX_TEST_ASSERT(b.data == 2); 856 CX_TEST_ASSERT(c.data == 0); 857 CX_TEST_ASSERT(aa.data == 0); 858 CX_TEST_ASSERT(ab.data == 0); 859 CX_TEST_ASSERT(ba.data == 2); 860 CX_TEST_ASSERT(ca.data == 0); 861 CX_TEST_ASSERT(cb.data == 0); 862 CX_TEST_ASSERT(cc.data == 0); 863 CX_TEST_ASSERT(cba.data == 0); 864 865 // now perform with other subtree 866 iter = cx_tree_iterator(&c, true, tree_children(tree_node)); 867 chk = 0; 868 cx_foreach(tree_node*, node, iter) { 869 CX_TEST_ASSERT(iter.exiting || node->data == 0); 870 node->data++; 871 chk++; 872 CX_TEST_ASSERT(node == iter.node); 873 if (node == &c) { 874 CX_TEST_ASSERT(iter.depth == 1); 875 } else if (node == &ca || node == &cb || node == &cc) { 876 CX_TEST_ASSERT(iter.depth == 2); 877 } else if (node == &cba) { 878 CX_TEST_ASSERT(iter.depth == 3); 879 } 880 } 881 CX_TEST_ASSERT(iter.counter == 5); 882 CX_TEST_ASSERT(chk == 10); 883 CX_TEST_ASSERT(iter.stack == NULL); 884 CX_TEST_ASSERT(root.data == 0); 885 CX_TEST_ASSERT(a.data == 0); 886 CX_TEST_ASSERT(b.data == 2); 887 CX_TEST_ASSERT(c.data == 2); 888 CX_TEST_ASSERT(aa.data == 0); 889 CX_TEST_ASSERT(ab.data == 0); 890 CX_TEST_ASSERT(ba.data == 2); 891 CX_TEST_ASSERT(ca.data == 2); 892 CX_TEST_ASSERT(cb.data == 2); 893 CX_TEST_ASSERT(cc.data == 2); 894 CX_TEST_ASSERT(cba.data == 2); 895 } 896 } 897 898 typedef struct test_xml_node { 899 struct tree_node base; 900 const char *name; 901 } test_xml_node; 902 903 CX_TEST(test_tree_iterator_xml) { 904 test_xml_node project = {0}; 905 test_xml_node config = {0}; 906 test_xml_node var1 = {0}; 907 test_xml_node var2 = {0}; 908 test_xml_node var3 = {0}; 909 test_xml_node dependency1 = {0}; 910 test_xml_node dependency1make = {0}; 911 test_xml_node dependency2 = {0}; 912 test_xml_node dependency2lang = {0}; 913 test_xml_node dependency2make = {0}; 914 test_xml_node target = {0}; 915 test_xml_node target_feature = {0}; 916 test_xml_node target_feature_dependencies = {0}; 917 test_xml_node target_dependencies = {0}; 918 919 project.name = "project"; 920 config.name = "config"; 921 var1.name = "var"; 922 var2.name = "var"; 923 var3.name = "var"; 924 dependency1.name = "dependency"; 925 dependency1make.name = "make"; 926 dependency2.name = "dependency"; 927 dependency2lang.name = "lang"; 928 dependency2make.name = "make"; 929 target.name = "target"; 930 target_feature.name = "feature"; 931 target_dependencies.name = "dependencies"; 932 target_feature_dependencies.name = "dependencies"; 933 934 cx_tree_link(&project, &config, tree_node_layout); 935 cx_tree_link(&project, &dependency1, tree_node_layout); 936 cx_tree_link(&project, &dependency2, tree_node_layout); 937 cx_tree_link(&project, &target, tree_node_layout); 938 cx_tree_link(&config, &var1, tree_node_layout); 939 cx_tree_link(&config, &var2, tree_node_layout); 940 cx_tree_link(&config, &var3, tree_node_layout); 941 cx_tree_link(&dependency1, &dependency1make, tree_node_layout); 942 cx_tree_link(&dependency2, &dependency2lang, tree_node_layout); 943 cx_tree_link(&dependency2, &dependency2make, tree_node_layout); 944 cx_tree_link(&target, &target_feature, tree_node_layout); 945 cx_tree_link(&target, &target_dependencies, tree_node_layout); 946 cx_tree_link(&target_feature, &target_feature_dependencies, tree_node_layout); 947 948 const char *expected = 949 "<project><config><var></var><var></var><var></var></config>" 950 "<dependency><make></make></dependency><dependency><lang></lang><make></make></dependency>" 951 "<target><feature><dependencies></dependencies></feature><dependencies></dependencies></target></project>"; 952 char *actual = malloc(512); 953 CX_TEST_DO { 954 CxTreeIterator iter = cx_tree_iterator(&project, true, tree_children(tree_node)); 955 size_t i = 0; 956 cx_foreach(test_xml_node*, node, iter) { 957 size_t len = strlen(node->name); 958 actual[i++] = '<'; 959 if (iter.exiting) { 960 actual[i++] = '/'; 961 } 962 memcpy(actual+i, node->name, len); 963 i += len; 964 actual[i++] = '>'; 965 } 966 actual[i] = '\0'; 967 CX_TEST_ASSERT(0 == strcmp(expected, actual)); 968 } 969 free(actual); 970 } 971 972 CX_TEST(test_tree_iterator_free_nodes) { 973 CxTestingAllocator talloc; 974 cx_testing_allocator_init(&talloc); 975 CxAllocator *alloc = &talloc.base; 976 CX_TEST_DO { 977 tree_node *root = cxCalloc(alloc, 1, sizeof(tree_node)); 978 tree_node *a = cxCalloc(alloc, 1, sizeof(tree_node)); 979 tree_node *b = cxCalloc(alloc, 1, sizeof(tree_node)); 980 tree_node *c = cxCalloc(alloc, 1, sizeof(tree_node)); 981 tree_node *aa = cxCalloc(alloc, 1, sizeof(tree_node)); 982 tree_node *ab = cxCalloc(alloc, 1, sizeof(tree_node)); 983 tree_node *ba = cxCalloc(alloc, 1, sizeof(tree_node)); 984 tree_node *ca = cxCalloc(alloc, 1, sizeof(tree_node)); 985 tree_node *cb = cxCalloc(alloc, 1, sizeof(tree_node)); 986 tree_node *cc = cxCalloc(alloc, 1, sizeof(tree_node)); 987 tree_node *cba = cxCalloc(alloc, 1, sizeof(tree_node)); 988 989 cx_tree_link(root, a, tree_node_layout); 990 cx_tree_link(root, b, tree_node_layout); 991 cx_tree_link(root, c, tree_node_layout); 992 cx_tree_link(a, aa, tree_node_layout); 993 cx_tree_link(a, ab, tree_node_layout); 994 cx_tree_link(b, ba, tree_node_layout); 995 cx_tree_link(c, ca, tree_node_layout); 996 cx_tree_link(c, cb, tree_node_layout); 997 cx_tree_link(c, cc, tree_node_layout); 998 cx_tree_link(cb, cba, tree_node_layout); 999 1000 CxTreeIterator iter = cx_tree_iterator(root, true, tree_children(tree_node)); 1001 cx_foreach(tree_node *, node, iter) { 1002 if (iter.exiting) { 1003 cxFree(alloc,node); 1004 } 1005 } 1006 1007 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); 1008 } 1009 cx_testing_allocator_destroy(&talloc); 1010 } 1011 1012 CX_TEST(test_tree_visitor_create_and_dispose) { 1013 tree_node root = {0}; 1014 tree_node child = {0}; 1015 tree_node child2 = {0}; 1016 cx_tree_link(&root, &child, tree_node_layout); 1017 cx_tree_link(&root, &child2, tree_node_layout); 1018 CX_TEST_DO { 1019 CxTreeVisitor iter = cx_tree_visitor(&root, tree_children(tree_node)); 1020 CX_TEST_ASSERT(iter.counter == 1); 1021 CX_TEST_ASSERT(iter.node == &root); 1022 CX_TEST_ASSERT(!iter.base.allow_remove); 1023 CX_TEST_ASSERT(!iter.base.remove); 1024 CX_TEST_ASSERT(iter.depth == 1); 1025 CX_TEST_ASSERT(iter.loc_next == offsetof(tree_node, next)); 1026 CX_TEST_ASSERT(iter.loc_children == offsetof(tree_node, children)); 1027 cxIteratorNext(iter); 1028 CX_TEST_ASSERT(iter.queue_next != NULL); 1029 CX_TEST_ASSERT(iter.queue_last != NULL); 1030 CX_TEST_ASSERT(iter.queue_next->node == &child2); 1031 CX_TEST_ASSERT(iter.queue_last->node == &child2); 1032 cxTreeVisitorDispose(&iter); 1033 CX_TEST_ASSERT(iter.queue_next == NULL); 1034 CX_TEST_ASSERT(iter.queue_last == NULL); 1035 } 1036 } 1037 1038 CX_TEST(test_tree_visitor) { 1039 tree_node root = {0}; 1040 tree_node a = {0}; 1041 tree_node b = {0}; 1042 tree_node c = {0}; 1043 tree_node aa = {0}; 1044 tree_node ab = {0}; 1045 tree_node ba = {0}; 1046 tree_node ca = {0}; 1047 tree_node cb = {0}; 1048 tree_node cc = {0}; 1049 tree_node cba = {0}; 1050 1051 tree_node* expected_order[] = { 1052 &root, 1053 &a, &b, &c, 1054 &aa, &ab, &ba, &ca, &cb, &cc, 1055 &cba 1056 }; 1057 tree_node* actual_order[16]; // reserve more space in case s.t. goes wrong 1058 1059 cx_tree_link(&root, &a, tree_node_layout); 1060 cx_tree_link(&root, &b, tree_node_layout); 1061 cx_tree_link(&root, &c, tree_node_layout); 1062 cx_tree_link(&a, &aa, tree_node_layout); 1063 cx_tree_link(&a, &ab, tree_node_layout); 1064 cx_tree_link(&b, &ba, tree_node_layout); 1065 cx_tree_link(&c, &ca, tree_node_layout); 1066 cx_tree_link(&c, &cb, tree_node_layout); 1067 cx_tree_link(&c, &cc, tree_node_layout); 1068 cx_tree_link(&cb, &cba, tree_node_layout); 1069 CX_TEST_DO { 1070 CxTreeVisitor iter = cx_tree_visitor(&root, tree_children(tree_node)); 1071 unsigned chk = 0; 1072 cx_foreach(tree_node*, node, iter) { 1073 CX_TEST_ASSERT(node->data == 0); 1074 node->data++; 1075 actual_order[chk] = node; 1076 chk++; 1077 CX_TEST_ASSERT(node == iter.node); 1078 if (node == &root) { 1079 CX_TEST_ASSERT(iter.depth == 1); 1080 } else if (node == &a || node == &b || node == &c) { 1081 CX_TEST_ASSERT(iter.depth == 2); 1082 } else if (node == &cba) { 1083 CX_TEST_ASSERT(iter.depth == 4); 1084 } else { 1085 CX_TEST_ASSERT(iter.depth == 3); 1086 } 1087 } 1088 CX_TEST_ASSERT(iter.counter == 11); 1089 CX_TEST_ASSERT(chk == 11); 1090 for (unsigned i = 0 ; i < chk ; i++) { 1091 CX_TEST_ASSERT(actual_order[i] == expected_order[i]); 1092 CX_TEST_ASSERT(actual_order[i]->data == 1); 1093 } 1094 CX_TEST_ASSERT(iter.queue_next == NULL); 1095 CX_TEST_ASSERT(iter.queue_last == NULL); 1096 } 1097 } 1098 1099 CX_TEST(test_tree_visitor_no_children) { 1100 tree_node root = {0}; 1101 1102 CX_TEST_DO { 1103 CxTreeVisitor iter = cx_tree_visitor(&root, tree_children(tree_node)); 1104 unsigned chk = 0; 1105 cx_foreach(tree_node*, node, iter) { 1106 CX_TEST_ASSERT(node == iter.node); 1107 chk++; 1108 } 1109 CX_TEST_ASSERT(iter.counter == 1); 1110 CX_TEST_ASSERT(chk == 1); 1111 CX_TEST_ASSERT(iter.queue_next == NULL); 1112 CX_TEST_ASSERT(iter.queue_last == NULL); 1113 } 1114 } 1115 1116 CX_TEST(test_tree_visitor_no_branching) { 1117 tree_node root = {0}; 1118 tree_node a = {0}; 1119 tree_node b = {0}; 1120 tree_node c = {0}; 1121 1122 tree_node* expected_order[] = { 1123 &root, &a, &b, &c 1124 }; 1125 tree_node* actual_order[4]; 1126 1127 cx_tree_link(&root, &a, tree_node_layout); 1128 cx_tree_link(&a, &b, tree_node_layout); 1129 cx_tree_link(&b, &c, tree_node_layout); 1130 1131 CX_TEST_DO { 1132 CxTreeVisitor iter = cx_tree_visitor(&root, tree_children(tree_node)); 1133 unsigned chk = 0; 1134 cx_foreach(tree_node*, node, iter) { 1135 CX_TEST_ASSERT(node == iter.node); 1136 CX_TEST_ASSERT(node->data == 0); 1137 node->data++; 1138 actual_order[chk] = node; 1139 chk++; 1140 } 1141 CX_TEST_ASSERT(iter.counter == 4); 1142 CX_TEST_ASSERT(chk == 4); 1143 CX_TEST_ASSERT(iter.queue_next == NULL); 1144 CX_TEST_ASSERT(iter.queue_last == NULL); 1145 for (unsigned i = 0 ; i < chk ; i++) { 1146 CX_TEST_ASSERT(actual_order[i] == expected_order[i]); 1147 CX_TEST_ASSERT(actual_order[i]->data == 1); 1148 } 1149 } 1150 } 1151 1152 CX_TEST(test_tree_visitor_subtree) { 1153 tree_node root = {0}; 1154 tree_node a = {0}; 1155 tree_node b = {0}; 1156 tree_node c = {0}; 1157 tree_node ba = {0}; 1158 tree_node bb = {0}; 1159 tree_node bc = {0}; 1160 tree_node bba = {0}; 1161 1162 tree_node* expected_order[] = { 1163 &b, &ba, &bb, &bc, &bba 1164 }; 1165 tree_node* actual_order[5]; 1166 1167 cx_tree_link(&root, &a, tree_node_layout); 1168 cx_tree_link(&root, &b, tree_node_layout); 1169 cx_tree_link(&root, &c, tree_node_layout); 1170 cx_tree_link(&b, &ba, tree_node_layout); 1171 cx_tree_link(&b, &bb, tree_node_layout); 1172 cx_tree_link(&b, &bc, tree_node_layout); 1173 cx_tree_link(&bb, &bba, tree_node_layout); 1174 1175 CX_TEST_DO { 1176 CxTreeVisitor iter = cx_tree_visitor(&b, tree_children(tree_node)); 1177 unsigned chk = 0; 1178 cx_foreach(tree_node*, node, iter) { 1179 CX_TEST_ASSERT(node == iter.node); 1180 CX_TEST_ASSERT(node->data == 0); 1181 node->data++; 1182 actual_order[chk] = node; 1183 chk++; 1184 } 1185 CX_TEST_ASSERT(iter.counter == 5); 1186 CX_TEST_ASSERT(chk == 5); 1187 CX_TEST_ASSERT(iter.queue_next == NULL); 1188 CX_TEST_ASSERT(iter.queue_last == NULL); 1189 for (unsigned i = 0 ; i < chk ; i++) { 1190 CX_TEST_ASSERT(actual_order[i] == expected_order[i]); 1191 CX_TEST_ASSERT(actual_order[i]->data == 1); 1192 } 1193 } 1194 } 1195 1196 CX_TEST(test_tree_visitor_continue) { 1197 tree_node root = {0}; 1198 tree_node a = {0}; 1199 tree_node b = {0}; 1200 tree_node c = {0}; 1201 tree_node aa = {0}; 1202 tree_node ab = {0}; 1203 tree_node ba = {0}; 1204 tree_node ca = {0}; 1205 tree_node cb = {0}; 1206 tree_node cc = {0}; 1207 tree_node cba = {0}; 1208 1209 tree_node* expected_order[] = { 1210 &root, 1211 &a, &b, &c, 1212 &aa, &ab, &ba 1213 }; 1214 tree_node* actual_order[16]; // reserve more space in case s.t. goes wrong 1215 1216 cx_tree_link(&root, &a, tree_node_layout); 1217 cx_tree_link(&root, &b, tree_node_layout); 1218 cx_tree_link(&root, &c, tree_node_layout); 1219 cx_tree_link(&a, &aa, tree_node_layout); 1220 cx_tree_link(&a, &ab, tree_node_layout); 1221 cx_tree_link(&b, &ba, tree_node_layout); 1222 cx_tree_link(&c, &ca, tree_node_layout); 1223 cx_tree_link(&c, &cb, tree_node_layout); 1224 cx_tree_link(&c, &cc, tree_node_layout); 1225 cx_tree_link(&cb, &cba, tree_node_layout); 1226 CX_TEST_DO { 1227 CxTreeVisitor iter = cx_tree_visitor(&root, tree_children(tree_node)); 1228 unsigned chk = 0; 1229 cx_foreach(tree_node*, node, iter) { 1230 CX_TEST_ASSERT(node->data == 0); 1231 node->data++; 1232 actual_order[chk] = node; 1233 chk++; 1234 CX_TEST_ASSERT(node == iter.node); 1235 if (node == &root) { 1236 CX_TEST_ASSERT(iter.depth == 1); 1237 } else if (node == &a || node == &b || node == &c) { 1238 CX_TEST_ASSERT(iter.depth == 2); 1239 } else { 1240 CX_TEST_ASSERT(iter.depth == 3); 1241 } 1242 if (node == &c) { 1243 cxTreeVisitorContinue(iter); 1244 } 1245 } 1246 CX_TEST_ASSERT(iter.counter == 7); 1247 CX_TEST_ASSERT(chk == 7); 1248 for (unsigned i = 0 ; i < chk ; i++) { 1249 CX_TEST_ASSERT(actual_order[i] == expected_order[i]); 1250 CX_TEST_ASSERT(actual_order[i]->data == 1); 1251 } 1252 CX_TEST_ASSERT(ca.data == 0); 1253 CX_TEST_ASSERT(cb.data == 0); 1254 CX_TEST_ASSERT(cc.data == 0); 1255 CX_TEST_ASSERT(cba.data == 0); 1256 CX_TEST_ASSERT(iter.queue_next == NULL); 1257 CX_TEST_ASSERT(iter.queue_last == NULL); 1258 } 1259 } 1260 1261 CX_TEST(test_tree_iterator_continue) { 1262 tree_node root = {0}; 1263 tree_node a = {0}; 1264 tree_node b = {0}; 1265 tree_node c = {0}; 1266 tree_node aa = {0}; 1267 tree_node ab = {0}; 1268 tree_node ba = {0}; 1269 tree_node ca = {0}; 1270 tree_node cb = {0}; 1271 tree_node cc = {0}; 1272 tree_node cba = {0}; 1273 1274 tree_node *expected_order[] = { 1275 &root, 1276 &a, &aa, &ab, 1277 &b, &ba, 1278 &c, 1279 }; 1280 tree_node* actual_order[16]; // reserve more space in case s.t. goes wrong 1281 1282 cx_tree_link(&root, &a, tree_node_layout); 1283 cx_tree_link(&root, &b, tree_node_layout); 1284 cx_tree_link(&root, &c, tree_node_layout); 1285 cx_tree_link(&a, &aa, tree_node_layout); 1286 cx_tree_link(&a, &ab, tree_node_layout); 1287 cx_tree_link(&b, &ba, tree_node_layout); 1288 cx_tree_link(&c, &ca, tree_node_layout); 1289 cx_tree_link(&c, &cb, tree_node_layout); 1290 cx_tree_link(&c, &cc, tree_node_layout); 1291 cx_tree_link(&cb, &cba, tree_node_layout); 1292 CX_TEST_DO { 1293 CxTreeIterator iter = cx_tree_iterator(&root, false, tree_children(tree_node)); 1294 unsigned chk = 0; 1295 cx_foreach(tree_node*, node, iter) { 1296 CX_TEST_ASSERT(node->data == 0); 1297 node->data++; 1298 actual_order[chk] = node; 1299 chk++; 1300 CX_TEST_ASSERT(node == iter.node); 1301 CX_TEST_ASSERT(!iter.exiting); 1302 if (node == &root) { 1303 CX_TEST_ASSERT(iter.depth == 1); 1304 } else if (node == &a || node == &b || node == &c) { 1305 CX_TEST_ASSERT(iter.depth == 2); 1306 } else { 1307 CX_TEST_ASSERT(iter.depth == 3); 1308 } 1309 if (node == &c) { 1310 cxTreeIteratorContinue(iter); 1311 } 1312 } 1313 CX_TEST_ASSERT(iter.counter == 7); 1314 CX_TEST_ASSERT(chk == 7); 1315 for (unsigned i = 0 ; i < chk ; i++) { 1316 CX_TEST_ASSERT(actual_order[i] == expected_order[i]); 1317 CX_TEST_ASSERT(actual_order[i]->data == 1); 1318 } 1319 CX_TEST_ASSERT(ca.data == 0); 1320 CX_TEST_ASSERT(cb.data == 0); 1321 CX_TEST_ASSERT(cc.data == 0); 1322 CX_TEST_ASSERT(cba.data == 0); 1323 CX_TEST_ASSERT(iter.stack == NULL); 1324 } 1325 } 1326 1327 CX_TEST(test_tree_iterator_continue_with_exit) { 1328 tree_node root = {0}; 1329 tree_node a = {0}; 1330 tree_node b = {0}; 1331 tree_node c = {0}; 1332 tree_node aa = {0}; 1333 tree_node ab = {0}; 1334 tree_node ba = {0}; 1335 tree_node ca = {0}; 1336 tree_node cb = {0}; 1337 tree_node cc = {0}; 1338 tree_node cba = {0}; 1339 1340 cx_tree_link(&root, &a, tree_node_layout); 1341 cx_tree_link(&root, &b, tree_node_layout); 1342 cx_tree_link(&root, &c, tree_node_layout); 1343 cx_tree_link(&a, &aa, tree_node_layout); 1344 cx_tree_link(&a, &ab, tree_node_layout); 1345 cx_tree_link(&b, &ba, tree_node_layout); 1346 cx_tree_link(&c, &ca, tree_node_layout); 1347 cx_tree_link(&c, &cb, tree_node_layout); 1348 cx_tree_link(&c, &cc, tree_node_layout); 1349 cx_tree_link(&cb, &cba, tree_node_layout); 1350 CX_TEST_DO { 1351 CxTreeIterator iter = cx_tree_iterator(&root, true, tree_children(tree_node)); 1352 unsigned chk = 0; 1353 cx_foreach(tree_node*, node, iter) { 1354 CX_TEST_ASSERT(iter.exiting || node->data == 0); 1355 node->data++; 1356 chk++; 1357 CX_TEST_ASSERT(node == iter.node); 1358 if (node == &root) { 1359 CX_TEST_ASSERT(iter.depth == 1); 1360 } else if (node == &a || node == &b || node == &c) { 1361 CX_TEST_ASSERT(iter.depth == 2); 1362 } else { 1363 CX_TEST_ASSERT(iter.depth == 3); 1364 } 1365 if (node == &c) { 1366 cxTreeIteratorContinue(iter); 1367 } 1368 } 1369 CX_TEST_ASSERT(iter.counter == 7); 1370 CX_TEST_ASSERT(chk == 14); 1371 CX_TEST_ASSERT(iter.stack == NULL); 1372 CX_TEST_ASSERT(root.data == 2); 1373 CX_TEST_ASSERT(a.data == 2); 1374 CX_TEST_ASSERT(b.data == 2); 1375 CX_TEST_ASSERT(c.data == 2); 1376 CX_TEST_ASSERT(aa.data == 2); 1377 CX_TEST_ASSERT(ab.data == 2); 1378 CX_TEST_ASSERT(ba.data == 2); 1379 CX_TEST_ASSERT(ca.data == 0); 1380 CX_TEST_ASSERT(cb.data == 0); 1381 CX_TEST_ASSERT(cc.data == 0); 1382 CX_TEST_ASSERT(cba.data == 0); 1383 } 1384 } 1385 1386 CX_TEST(test_tree_add_one) { 1387 CxTestingAllocator talloc; 1388 cx_testing_allocator_init(&talloc); 1389 CxAllocator *alloc = &talloc.base; 1390 1391 tree_node_file root = {0}; 1392 root.path = "/"; 1393 tree_node_file usr = {0}; 1394 usr.path = "/usr/"; 1395 cx_tree_link(&root, &usr, tree_node_file_layout); 1396 tree_node_file home = {0}; 1397 home.path = "/home/"; 1398 cx_tree_link(&root, &home, tree_node_file_layout); 1399 tree_node_file lib = {0}; 1400 lib.path = "/usr/lib/"; 1401 cx_tree_link(&usr, &lib, tree_node_file_layout); 1402 1403 CX_TEST_DO { 1404 tree_node_file *foo; 1405 int result; 1406 result = cx_tree_add( 1407 "/home/foo/", 1408 tree_node_file_search, 1409 tree_node_file_create, alloc, 1410 (void **) &foo, &root, 1411 tree_node_file_layout 1412 ); 1413 CX_TEST_ASSERT(result == 0); 1414 CX_TEST_ASSERT(foo != NULL); 1415 const char *bar_path = "/home/foo/bar/"; 1416 void *failed; 1417 size_t added = cx_tree_add_array( 1418 bar_path, 1, sizeof(const char *), 1419 tree_node_file_search, 1420 tree_node_file_create, alloc, 1421 &failed, &root, 1422 tree_node_file_layout 1423 ); 1424 CX_TEST_ASSERT(added == 1); 1425 CX_TEST_ASSERT(failed == NULL); 1426 tree_node_file *bar = foo->children; 1427 CX_TEST_ASSERT(bar != NULL); 1428 CX_TEST_ASSERT(bar->parent == foo); 1429 CX_TEST_ASSERT(bar->path == bar_path); 1430 CX_TEST_ASSERT(foo->parent == &home); 1431 1432 tree_node_file *new_node; 1433 result = cx_tree_add( 1434 "newroot", 1435 tree_node_file_search, 1436 tree_node_file_create, alloc, 1437 (void **) &new_node, &root, 1438 tree_node_file_layout 1439 ); 1440 CX_TEST_ASSERT(0 != result); 1441 CX_TEST_ASSERT(NULL != new_node); 1442 CX_TEST_ASSERT(new_node->children == NULL); 1443 CX_TEST_ASSERT(new_node->parent == NULL); 1444 1445 CX_TEST_ASSERT(talloc.alloc_total == 3); 1446 1447 cxFree(alloc, foo); 1448 cxFree(alloc, bar); 1449 cxFree(alloc, new_node); 1450 1451 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); 1452 } 1453 cx_testing_allocator_destroy(&talloc); 1454 } 1455 1456 CX_TEST(test_tree_add_one_existing) { 1457 CxTestingAllocator talloc; 1458 cx_testing_allocator_init(&talloc); 1459 CxAllocator *alloc = &talloc.base; 1460 1461 tree_node_file root = {0}; 1462 root.path = "/"; 1463 tree_node_file usr = {0}; 1464 usr.path = "/usr/"; 1465 cx_tree_link(&root, &usr, tree_node_file_layout); 1466 tree_node_file home = {0}; 1467 home.path = "/home/"; 1468 cx_tree_link(&root, &home, tree_node_file_layout); 1469 tree_node_file lib = {0}; 1470 lib.path = "/usr/lib/"; 1471 cx_tree_link(&usr, &lib, tree_node_file_layout); 1472 1473 CX_TEST_DO { 1474 tree_node_file *node; 1475 int result = cx_tree_add( 1476 "/usr/lib/", 1477 tree_node_file_search, 1478 tree_node_file_create, alloc, 1479 (void **) &node, &root, 1480 tree_node_file_layout 1481 ); 1482 CX_TEST_ASSERT(result == 0); 1483 CX_TEST_ASSERT(node != &lib); 1484 CX_TEST_ASSERT(node->prev == &lib); 1485 CX_TEST_ASSERT(lib.next == node); 1486 CX_TEST_ASSERT(node->parent == &usr); 1487 CX_TEST_ASSERT(talloc.alloc_total == 1); 1488 cxFree(alloc, node); 1489 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); 1490 } 1491 cx_testing_allocator_destroy(&talloc); 1492 } 1493 1494 CX_TEST(test_tree_add_one_no_match) { 1495 tree_node_file root = {0}; 1496 root.path = "/mnt/"; 1497 1498 CX_TEST_DO { 1499 tree_node_file *node = NULL; 1500 int result = cx_tree_add( 1501 "/usr/lib/", 1502 tree_node_file_search, 1503 tree_node_file_create, NULL, 1504 (void **) &node, &root, 1505 tree_node_file_layout 1506 ); 1507 CX_TEST_ASSERT(result != 0); 1508 CX_TEST_ASSERT(node != NULL); 1509 CX_TEST_ASSERT(node->parent == NULL); 1510 CX_TEST_ASSERT(node->children == NULL); 1511 cxFreeDefault(node); 1512 node = NULL; 1513 size_t added = cx_tree_add_array( 1514 "/", 1, sizeof(const char *), 1515 tree_node_file_search, 1516 tree_node_file_create, NULL, 1517 (void **) &node, &root, 1518 tree_node_file_layout 1519 ); 1520 CX_TEST_ASSERT(added == 0); 1521 CX_TEST_ASSERT(node != NULL); 1522 CX_TEST_ASSERT(node->parent == NULL); 1523 CX_TEST_ASSERT(node->children == NULL); 1524 cxFreeDefault(node); 1525 } 1526 } 1527 1528 CX_TEST(test_tree_add_duplicate_root) { 1529 tree_node_file root = {0}; 1530 root.path = "/"; 1531 CX_TEST_DO { 1532 tree_node_file *node; 1533 int result = cx_tree_add( 1534 "/", 1535 tree_node_file_search, 1536 tree_node_file_create, NULL, 1537 (void **) &node, &root, 1538 tree_node_file_layout 1539 ); 1540 CX_TEST_ASSERT(result == 0); 1541 CX_TEST_ASSERT(root.children == node); 1542 CX_TEST_ASSERT(node->parent == &root); 1543 cxFreeDefault(node); 1544 } 1545 } 1546 1547 CX_TEST(test_tree_add_zero) { 1548 CxTestingAllocator talloc; 1549 cx_testing_allocator_init(&talloc); 1550 CxAllocator *alloc = &talloc.base; 1551 1552 tree_node_file root = {0}; 1553 root.path = "/"; 1554 CX_TEST_DO { 1555 void *failed; 1556 1557 size_t processed = cx_tree_add_array( 1558 (void *) 0xc0ffee, 0, sizeof(void *), 1559 tree_node_file_search, 1560 tree_node_file_create, alloc, 1561 &failed, &root, tree_node_file_layout 1562 ); 1563 CX_TEST_ASSERT(failed == NULL); 1564 CX_TEST_ASSERT(processed == 0); 1565 CX_TEST_ASSERT(talloc.alloc_total == 0); 1566 1567 CxIterator iter = cxIterator(NULL, sizeof(void *), 0, false); 1568 processed = cx_tree_add_iter( 1569 cxIteratorRef(iter), 1570 10, // deliberately specify more than the iter has 1571 tree_node_file_search, 1572 tree_node_file_create, alloc, 1573 &failed, &root, tree_node_file_layout 1574 ); 1575 CX_TEST_ASSERT(processed == 0); 1576 CX_TEST_ASSERT(failed == NULL); 1577 CX_TEST_ASSERT(talloc.alloc_total == 0); 1578 1579 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); 1580 } 1581 cx_testing_allocator_destroy(&talloc); 1582 } 1583 1584 CX_TEST(test_tree_add_many) { 1585 // adds many elements to an existing tree 1586 1587 CxTestingAllocator talloc; 1588 cx_testing_allocator_init(&talloc); 1589 CxAllocator *alloc = &talloc.base; 1590 1591 tree_node_file root = {0}; 1592 root.path = "/"; 1593 tree_node_file usr = {0}; 1594 usr.path = "/usr/"; 1595 cx_tree_link(&root, &usr, tree_node_file_layout); 1596 tree_node_file home = {0}; 1597 home.path = "/home/"; 1598 cx_tree_link(&root, &home, tree_node_file_layout); 1599 tree_node_file lib = {0}; 1600 lib.path = "/usr/lib/"; 1601 cx_tree_link(&usr, &lib, tree_node_file_layout); 1602 1603 CX_TEST_DO { 1604 void *failed; 1605 1606 const char *paths[] = { 1607 "/home/foo/", 1608 "/home/foo/bar", 1609 "/usr/lib64/", 1610 "/usr/lib/foo.so" 1611 }; 1612 1613 size_t processed = cx_tree_add_array( 1614 paths, 4, sizeof(const char *), 1615 tree_node_file_search, 1616 tree_node_file_create, alloc, 1617 &failed, &root, tree_node_file_layout 1618 ); 1619 1620 CX_TEST_ASSERT(failed == NULL); 1621 CX_TEST_ASSERT(processed == 4); 1622 CX_TEST_ASSERT(talloc.alloc_total == 4); 1623 1624 CX_TEST_ASSERT(home.children == home.last_child); 1625 tree_node_file *foo = home.children; 1626 CX_TEST_ASSERT(foo != NULL && foo->path == paths[0]); 1627 CX_TEST_ASSERT(foo->children == foo->last_child); 1628 tree_node_file *bar = foo->children; 1629 CX_TEST_ASSERT(bar != NULL && bar->path == paths[1]); 1630 CX_TEST_ASSERT(usr.children != usr.last_child); 1631 tree_node_file *lib64 = usr.last_child; 1632 CX_TEST_ASSERT(lib64 != NULL); 1633 CX_TEST_ASSERT(lib64->path == paths[2]); 1634 CX_TEST_ASSERT(lib64->prev == &lib); 1635 CX_TEST_ASSERT(lib64->parent == &usr); 1636 CX_TEST_ASSERT(lib.children != NULL); 1637 tree_node_file *libfoo = lib.children; 1638 CX_TEST_ASSERT(libfoo != NULL && libfoo->path == paths[3]); 1639 1640 cxFree(alloc, foo); 1641 cxFree(alloc, bar); 1642 cxFree(alloc, lib64); 1643 cxFree(alloc, libfoo); 1644 1645 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); 1646 } 1647 cx_testing_allocator_destroy(&talloc); 1648 } 1649 1650 CX_TEST(test_tree_add_many_but_not_all) { 1651 CxTestingAllocator talloc; 1652 cx_testing_allocator_init(&talloc); 1653 CxAllocator *alloc = &talloc.base; 1654 1655 tree_node_file root = {0}; 1656 root.path = "/"; 1657 tree_node_file usr = {0}; 1658 usr.path = "/usr/"; 1659 cx_tree_link(&root, &usr, tree_node_file_layout); 1660 tree_node_file home = {0}; 1661 home.path = "/home/"; 1662 cx_tree_link(&root, &home, tree_node_file_layout); 1663 tree_node_file lib = {0}; 1664 lib.path = "/usr/lib/"; 1665 cx_tree_link(&usr, &lib, tree_node_file_layout); 1666 1667 CX_TEST_DO { 1668 void *failed; 1669 1670 const char *paths[] = { 1671 "/home/foo/", 1672 "/home/foo/bar", 1673 "/usr/lib64/", 1674 "/usr/lib/foo.so" 1675 }; 1676 // create iterator for 4 elements, but choose to insert only 3 of them 1677 CxIterator iter = cxIterator(paths, sizeof(const char*), 4, false); 1678 size_t processed = cx_tree_add_iter( 1679 cxIteratorRef(iter), 3, 1680 tree_node_file_search, 1681 tree_node_file_create, alloc, 1682 &failed, &root, tree_node_file_layout 1683 ); 1684 1685 CX_TEST_ASSERT(cxIteratorValid(iter)); 1686 CX_TEST_ASSERT(cxIteratorCurrent(iter) == &paths[3]); 1687 1688 CX_TEST_ASSERT(failed == NULL); 1689 CX_TEST_ASSERT(processed == 3); 1690 CX_TEST_ASSERT(talloc.alloc_total == 3); 1691 1692 CX_TEST_ASSERT(home.children == home.last_child); 1693 tree_node_file *foo = home.children; 1694 CX_TEST_ASSERT(foo != NULL && foo->path == paths[0]); 1695 CX_TEST_ASSERT(foo->children == foo->last_child); 1696 tree_node_file *bar = foo->children; 1697 CX_TEST_ASSERT(bar != NULL && bar->path == paths[1]); 1698 CX_TEST_ASSERT(usr.children != usr.last_child); 1699 tree_node_file *lib64 = usr.last_child; 1700 CX_TEST_ASSERT(lib64 != NULL); 1701 CX_TEST_ASSERT(lib64->path == paths[2]); 1702 CX_TEST_ASSERT(lib64->prev == &lib); 1703 CX_TEST_ASSERT(lib64->parent == &usr); 1704 CX_TEST_ASSERT(lib.children == NULL); 1705 1706 cxFree(alloc, foo); 1707 cxFree(alloc, bar); 1708 cxFree(alloc, lib64); 1709 1710 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); 1711 } 1712 cx_testing_allocator_destroy(&talloc); 1713 } 1714 1715 CX_TEST(test_tree_add_many_with_dupl_and_no_match) { 1716 CxTestingAllocator talloc; 1717 cx_testing_allocator_init(&talloc); 1718 CxAllocator *alloc = &talloc.base; 1719 1720 tree_node_file root = {0}; 1721 root.path = "/mnt/"; 1722 1723 CX_TEST_DO { 1724 tree_node_file *failed; 1725 1726 const char *paths[] = { 1727 "/mnt/sdcard/", 1728 "/mnt/foo/", 1729 "/mnt/sdcard/", 1730 "/home/", 1731 "/usr/" 1732 }; 1733 1734 size_t processed = cx_tree_add_array( 1735 paths, 5, sizeof(const char *), 1736 tree_node_file_search, 1737 tree_node_file_create, alloc, 1738 (void **) &failed, &root, tree_node_file_layout 1739 ); 1740 1741 CX_TEST_ASSERT(processed == 3); 1742 CX_TEST_ASSERT(failed != NULL); 1743 CX_TEST_ASSERT(failed->parent == NULL); 1744 CX_TEST_ASSERT(failed->children == NULL); 1745 CX_TEST_ASSERT(strcmp(failed->path, "/home/") == 0); 1746 cxFree(alloc, failed); 1747 1748 CX_TEST_ASSERT(root.children != root.last_child); 1749 CX_TEST_ASSERT(strcmp(root.children->path, "/mnt/sdcard/") == 0); 1750 CX_TEST_ASSERT(strcmp(root.last_child->path, "/mnt/sdcard/") == 0); 1751 CX_TEST_ASSERT(strcmp(root.children->next->path, "/mnt/foo/") == 0); 1752 CX_TEST_ASSERT(strcmp(root.last_child->prev->path, "/mnt/foo/") == 0); 1753 1754 CxTreeIterator iter = cx_tree_iterator( 1755 &root, true, 1756 offsetof(tree_node_file, children), 1757 offsetof(tree_node_file, next) 1758 ); 1759 cx_foreach(tree_node_file *, node, iter) { 1760 if (iter.exiting) { 1761 if (node != &root) { 1762 cxFree(alloc, node); 1763 } 1764 } 1765 } 1766 1767 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); 1768 } 1769 cx_testing_allocator_destroy(&talloc); 1770 } 1771 1772 static CX_TEST_SUBROUTINE(test_tree_add_create_from_array_impl, 1773 CxAllocator *alloc, const char **paths) { 1774 tree_node_file root = {0}; 1775 root.path = "/"; 1776 1777 void *failed; 1778 size_t processed = cx_tree_add_array( 1779 paths, 10, sizeof(const char *), 1780 tree_node_file_search, 1781 tree_node_file_create, alloc, 1782 &failed, &root, tree_node_file_layout 1783 ); 1784 1785 CX_TEST_ASSERT(failed == NULL); 1786 CX_TEST_ASSERT(processed == 10); 1787 1788 const char *exp_order[] = { 1789 "/", 1790 "/usr/", 1791 "/usr/lib/", 1792 "/usr/lib/libbumm.so", 1793 "/home/", 1794 "/home/foo/", 1795 "/var/", 1796 "/var/www/", 1797 "/var/www/vhosts/", 1798 "/var/www/vhosts/live/", 1799 "/var/www/vhosts/live/htdocs/" 1800 }; 1801 unsigned exp_depth[] = { 1802 1, 1803 2, 1804 3, 1805 4, 1806 2, 1807 3, 1808 2, 1809 3, 1810 4, 1811 5, 1812 6 1813 }; 1814 1815 CxTreeIterator iter = cx_tree_iterator( 1816 &root, true, 1817 offsetof(tree_node_file, children), 1818 offsetof(tree_node_file, next) 1819 ); 1820 cx_foreach(tree_node_file *, node, iter) { 1821 if (iter.exiting) { 1822 if (node != &root) { 1823 cxFree(alloc, node); 1824 } 1825 } else { 1826 CX_TEST_ASSERT(iter.counter <= 11); 1827 CX_TEST_ASSERT(iter.depth == exp_depth[iter.counter - 1]); 1828 CX_TEST_ASSERT(strcmp(node->path, exp_order[iter.counter - 1]) == 0); 1829 } 1830 } 1831 } 1832 1833 CX_TEST(test_tree_add_create_from_array) { 1834 // creates an entirely new tree from an array 1835 1836 CxTestingAllocator talloc; 1837 cx_testing_allocator_init(&talloc); 1838 CxAllocator *alloc = &talloc.base; 1839 1840 CX_TEST_DO { 1841 const char *paths[] = { 1842 "/usr/", 1843 "/home/", 1844 "/usr/lib/", 1845 "/usr/lib/libbumm.so", 1846 "/var/", 1847 "/var/www/", 1848 "/var/www/vhosts/", 1849 "/var/www/vhosts/live/", 1850 "/var/www/vhosts/live/htdocs/", 1851 "/home/foo/" 1852 }; 1853 1854 const char *scrambled_paths[] = { 1855 "/usr/", 1856 "/home/", 1857 "/var/www/vhosts/live/", 1858 "/usr/lib/", 1859 "/var/", 1860 "/var/www/", 1861 "/usr/lib/libbumm.so", 1862 "/var/www/vhosts/", 1863 "/var/www/vhosts/live/htdocs/", 1864 "/home/foo/" 1865 }; 1866 1867 // no matter how the original array is sorted, 1868 // the resulting tree should be the same 1869 CX_TEST_CALL_SUBROUTINE(test_tree_add_create_from_array_impl, alloc, 1870 paths); 1871 CX_TEST_CALL_SUBROUTINE(test_tree_add_create_from_array_impl, alloc, 1872 scrambled_paths); 1873 1874 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); 1875 } 1876 cx_testing_allocator_destroy(&talloc); 1877 } 1878 1879 CX_TEST(test_tree_high_create) { 1880 CxTestingAllocator talloc; 1881 cx_testing_allocator_init(&talloc); 1882 CX_TEST_DO { 1883 CxTree *tree = cxTreeCreate( 1884 &talloc.base, 1885 tree_node_file_create_hl, 1886 tree_node_file_search, 1887 tree_node_file_search_data, 1888 tree_node_file_layout 1889 ); 1890 CX_TEST_ASSERT(tree->cl != NULL); 1891 CX_TEST_ASSERT(tree->collection.allocator == &talloc.base); 1892 CX_TEST_ASSERT(tree->node_create == tree_node_file_create_hl); 1893 CX_TEST_ASSERT(tree->search == tree_node_file_search); 1894 CX_TEST_ASSERT(tree->search_data == tree_node_file_search_data); 1895 CX_TEST_ASSERT(tree->collection.size == 0); 1896 CX_TEST_ASSERT(tree->collection.simple_destructor == NULL); 1897 CX_TEST_ASSERT(tree->collection.advanced_destructor == (cx_destructor_func2) cxFree); 1898 CX_TEST_ASSERT(tree->collection.destructor_data == &talloc.base); 1899 CX_TEST_ASSERT(tree->collection.store_pointer == false); 1900 CX_TEST_ASSERT(tree->collection.sorted == false); 1901 CX_TEST_ASSERT(tree->root == NULL); 1902 CX_TEST_ASSERT(tree->loc_parent == offsetof(tree_node_file, parent)); 1903 CX_TEST_ASSERT(tree->loc_children == offsetof(tree_node_file, children)); 1904 CX_TEST_ASSERT(tree->loc_last_child == offsetof(tree_node_file, last_child)); 1905 CX_TEST_ASSERT(tree->loc_prev == offsetof(tree_node_file, prev)); 1906 CX_TEST_ASSERT(tree->loc_next == offsetof(tree_node_file, next)); 1907 1908 CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc)); 1909 CX_TEST_ASSERT(talloc.alloc_total == 1); 1910 1911 cxTreeFree(tree); 1912 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); 1913 } 1914 cx_testing_allocator_destroy(&talloc); 1915 } 1916 1917 CX_TEST(test_tree_high_create_simple) { 1918 CX_TEST_DO { 1919 CxTree *tree = cxTreeCreateSimple( 1920 NULL, // shall fall back to the default allocator 1921 tree_node_file_create_hl, 1922 tree_node_file_search, 1923 tree_node_file_search_data 1924 ); 1925 CX_TEST_ASSERT(tree->cl != NULL); 1926 CX_TEST_ASSERT(tree->collection.allocator == cxDefaultAllocator); 1927 CX_TEST_ASSERT(tree->node_create == tree_node_file_create_hl); 1928 CX_TEST_ASSERT(tree->search == tree_node_file_search); 1929 CX_TEST_ASSERT(tree->search_data == tree_node_file_search_data); 1930 CX_TEST_ASSERT(tree->collection.size == 0); 1931 CX_TEST_ASSERT(tree->collection.simple_destructor == NULL); 1932 CX_TEST_ASSERT(tree->collection.advanced_destructor == (cx_destructor_func2) cxFree); 1933 CX_TEST_ASSERT(tree->collection.destructor_data == cxDefaultAllocator); 1934 CX_TEST_ASSERT(tree->root == NULL); 1935 CX_TEST_ASSERT(tree->loc_parent == offsetof(struct cx_tree_node_base_s, parent)); 1936 CX_TEST_ASSERT(tree->loc_children == offsetof(struct cx_tree_node_base_s, children)); 1937 CX_TEST_ASSERT(tree->loc_last_child == offsetof(struct cx_tree_node_base_s, last_child)); 1938 CX_TEST_ASSERT(tree->loc_prev == offsetof(struct cx_tree_node_base_s, prev)); 1939 CX_TEST_ASSERT(tree->loc_next == offsetof(struct cx_tree_node_base_s, next)); 1940 cxTreeFree(tree); 1941 } 1942 } 1943 1944 CX_TEST(test_tree_high_create_wrapped) { 1945 tree_node root = {0}, child1 = {0}, child2 = {0}, child3 = {0}; 1946 cx_tree_link(&root, &child1, tree_node_layout); 1947 cx_tree_link(&root, &child2, tree_node_layout); 1948 cx_tree_link(&child1, &child3, tree_node_layout); 1949 CX_TEST_DO { 1950 CxTree *tree = cxTreeCreateWrapped(NULL, &root, tree_node_layout); 1951 CX_TEST_ASSERT(tree->cl != NULL); 1952 CX_TEST_ASSERT(tree->collection.allocator == cxDefaultAllocator); 1953 CX_TEST_ASSERT(tree->node_create == NULL); 1954 CX_TEST_ASSERT(tree->search == NULL); 1955 CX_TEST_ASSERT(tree->search_data == NULL); 1956 CX_TEST_ASSERT(tree->root == &root); 1957 CX_TEST_ASSERT(tree->collection.size == 4); 1958 CX_TEST_ASSERT(tree->collection.simple_destructor == NULL); 1959 CX_TEST_ASSERT(tree->collection.advanced_destructor == NULL); 1960 CX_TEST_ASSERT(tree->collection.destructor_data == NULL); 1961 CX_TEST_ASSERT(tree->loc_parent == offsetof(tree_node, parent)); 1962 CX_TEST_ASSERT(tree->loc_children == offsetof(tree_node, children)); 1963 CX_TEST_ASSERT(tree->loc_last_child == -1); 1964 CX_TEST_ASSERT(tree->loc_prev == offsetof(tree_node, prev)); 1965 CX_TEST_ASSERT(tree->loc_next == offsetof(tree_node, next)); 1966 cxTreeFree(tree); 1967 } 1968 } 1969 1970 CX_TEST(test_tree_high_tree_depth) { 1971 tree_node root = {0}, child1 = {0}, child2 = {0}, child3 = {0}; 1972 cx_tree_link(&root, &child1, tree_node_layout); 1973 cx_tree_link(&root, &child2, tree_node_layout); 1974 cx_tree_link(&child1, &child3, tree_node_layout); 1975 CxTree *tree = cxTreeCreateWrapped(cxDefaultAllocator, &root, tree_node_layout); 1976 CX_TEST_DO { 1977 CX_TEST_ASSERT(cxTreeDepth(tree) == 3); 1978 CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &root) == 3); 1979 CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child1) == 2); 1980 CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child2) == 1); 1981 CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child3) == 1); 1982 1983 CxTree *empty = cxTreeCreate( 1984 cxDefaultAllocator, 1985 tree_node_file_create_hl, 1986 tree_node_file_search, 1987 tree_node_file_search_data, 1988 tree_node_file_layout 1989 ); 1990 CX_TEST_ASSERT(cxTreeDepth(empty) == 0); 1991 cxTreeFree(empty); 1992 } 1993 cxTreeFree(tree); 1994 } 1995 1996 CX_TEST(test_tree_high_set_parent) { 1997 tree_node root = {0}, child1 = {0}, child2 = {0}, child3 = {0}; 1998 CxTree *tree = cxTreeCreateWrapped(cxDefaultAllocator, &root, tree_node_layout); 1999 CX_TEST_DO { 2000 cxTreeSetParent(tree, &root, &child1); 2001 cxTreeSetParent(tree, &root, &child2); 2002 cxTreeSetParent(tree, &child1, &child3); 2003 CX_TEST_ASSERT(cxTreeDepth(tree) == 3); 2004 CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &root) == 3); 2005 CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child1) == 2); 2006 CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child2) == 1); 2007 CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child3) == 1); 2008 2009 cxTreeSetParent(tree, &child2, &child3); 2010 CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &root) == 3); 2011 CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child1) == 1); 2012 CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child2) == 2); 2013 CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child3) == 1); 2014 2015 CxTree *empty = cxTreeCreate( 2016 cxDefaultAllocator, 2017 tree_node_file_create_hl, 2018 tree_node_file_search, 2019 tree_node_file_search_data, 2020 tree_node_file_layout 2021 ); 2022 CX_TEST_ASSERT(cxTreeDepth(empty) == 0); 2023 cxTreeFree(empty); 2024 } 2025 cxTreeFree(tree); 2026 } 2027 2028 CX_TEST(test_tree_high_insert_one) { 2029 CxTestingAllocator talloc; 2030 cx_testing_allocator_init(&talloc); 2031 CxAllocator *alloc = &talloc.base; 2032 2033 CX_TEST_DO { 2034 CxTree *tree = cxTreeCreate( 2035 alloc, tree_node_file_create_hl, 2036 tree_node_file_search, tree_node_file_search_data, 2037 tree_node_file_layout 2038 ); 2039 2040 int result = 0; 2041 result |= cxTreeInsert(tree, "/"); 2042 result |= cxTreeInsert(tree, "/usr/"); 2043 result |= cxTreeInsert(tree, "/home/"); 2044 result |= cxTreeInsert(tree, "/usr/lib/"); 2045 result |= cxTreeInsert(tree, "/home/foo/"); 2046 CX_TEST_ASSERT(result == 0); 2047 CX_TEST_ASSERT(1 == cxTreeInsertArray(tree, "/home/foo/bar/", sizeof(const char*), 1)); 2048 CX_TEST_ASSERT(cxTreeSize(tree) == 6); 2049 CX_TEST_ASSERT(0 != cxTreeInsert(tree, "newroot")); 2050 CX_TEST_ASSERT(cxTreeSize(tree) == 6); 2051 2052 CX_TEST_ASSERT(talloc.alloc_total == 8); 2053 CX_TEST_ASSERT(talloc.free_total == 1); // the one that could not be added 2054 2055 cxTreeFree(tree); 2056 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); 2057 } 2058 cx_testing_allocator_destroy(&talloc); 2059 } 2060 2061 CX_TEST(test_tree_high_insert_many) { 2062 CxTestingAllocator talloc; 2063 cx_testing_allocator_init(&talloc); 2064 CxAllocator *alloc = &talloc.base; 2065 2066 CX_TEST_DO { 2067 CxTree *tree = cxTreeCreate( 2068 alloc, tree_node_file_create_hl, 2069 tree_node_file_search, tree_node_file_search_data, 2070 tree_node_file_layout 2071 ); 2072 2073 const char *paths[] = { 2074 "/", 2075 "/usr/", 2076 "/home/", 2077 "/usr/lib/", 2078 "/home/foo/", 2079 "/home/foo/bar/", 2080 "newroot" 2081 }; 2082 CX_TEST_ASSERT(6 == cxTreeInsertArray(tree, paths, sizeof(const char*), 7)); 2083 CX_TEST_ASSERT(cxTreeSize(tree) == 6); 2084 2085 CX_TEST_ASSERT(talloc.alloc_total == 8); 2086 CX_TEST_ASSERT(talloc.free_total == 1); // the one that could not be added 2087 2088 cxTreeFree(tree); 2089 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); 2090 } 2091 cx_testing_allocator_destroy(&talloc); 2092 } 2093 2094 static void test_tree_remove_node_relink_mock( 2095 void *node, 2096 cx_attr_unused const void *oldp, 2097 cx_attr_unused const void *newp 2098 ) { 2099 tree_node_file * n = node; 2100 // this function fakes the relink logic in below test 2101 if (strcmp(n->path, "/usr/share/") == 0) { 2102 n->path = "/share/"; 2103 } else if (strcmp(n->path, "/usr/lib/") == 0) { 2104 n->path = "/lib/"; 2105 } 2106 } 2107 2108 CX_TEST(test_tree_high_add_find_remove_nodes) { 2109 CxTestingAllocator talloc; 2110 cx_testing_allocator_init(&talloc); 2111 CxAllocator *alloc = &talloc.base; 2112 2113 CX_TEST_DO { 2114 CxTree *tree = cxTreeCreate( 2115 alloc, tree_node_file_create_hl, 2116 tree_node_file_search, tree_node_file_search_data, 2117 tree_node_file_layout 2118 ); 2119 2120 const char *paths[] = { 2121 "/", 2122 "/usr/", 2123 "/home/", 2124 "/usr/lib/", 2125 "/home/foo/", 2126 "/home/foo/bar/" 2127 }; 2128 cxTreeInsertArray(tree, paths, sizeof(const char*), 6); 2129 2130 tree_node_file *foo = cxTreeFind(tree, "/home/foo/"); 2131 CX_TEST_ASSERT(NULL != foo); 2132 CX_TEST_ASSERT(0 == strcmp("/home/foo/", foo->path)); 2133 CX_TEST_ASSERT(NULL != foo->parent); 2134 CX_TEST_ASSERT(0 == strcmp("/home/", foo->parent->path)); 2135 CX_TEST_ASSERT(cxTreeSize(tree) == 6); 2136 2137 CX_TEST_ASSERT(0 == cxTreeAddChild(tree, foo->parent, "/home/baz/")); 2138 tree_node_file *baz = cxTreeFind(tree, "/home/baz/"); 2139 CX_TEST_ASSERT(NULL != baz); 2140 CX_TEST_ASSERT(0 == strcmp("/home/baz/", baz->path)); 2141 CX_TEST_ASSERT(NULL != baz->parent); 2142 CX_TEST_ASSERT(0 == strcmp("/home/", baz->parent->path)); 2143 CX_TEST_ASSERT(cxTreeSize(tree) == 7); 2144 2145 tree_node_file *home = cxTreeFind(tree, "/home/"); 2146 CX_TEST_ASSERT(NULL == cxTreeFindInSubtree(tree, "/usr/", foo, 0)); 2147 tree_node_file *bar = cxTreeFindInSubtree(tree, "/home/foo/bar/", home, 0); 2148 CX_TEST_ASSERT(NULL != bar); 2149 CX_TEST_ASSERT(0 == strcmp("/home/foo/bar/", bar->path)); 2150 CX_TEST_ASSERT(bar->parent == foo); 2151 2152 tree_node_file *share = cxCalloc(alloc, 1, sizeof(tree_node_file)); 2153 share->path = "/usr/share/"; 2154 tree_node_file *usr = cxTreeFind(tree, "/usr/"); 2155 cxTreeAddChildNode(tree, usr, share); 2156 CX_TEST_ASSERT(cxTreeSize(tree) == 8); 2157 2158 cxTreeRemoveSubtree(tree, foo); 2159 CX_TEST_ASSERT(cxTreeSize(tree) == 6); 2160 CX_TEST_ASSERT(foo->children == bar); 2161 CX_TEST_ASSERT(foo->last_child == bar); 2162 CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/foo/")); 2163 CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/foo/bar/")); 2164 CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/bar/")); 2165 2166 CX_TEST_ASSERT(0 == cxTreeRemoveNode(tree, usr, test_tree_remove_node_relink_mock)); 2167 CX_TEST_ASSERT(cxTreeSize(tree) == 5); 2168 CX_TEST_ASSERT(usr->parent == NULL); 2169 CX_TEST_ASSERT(usr->children == NULL); 2170 CX_TEST_ASSERT(usr->last_child == NULL); 2171 CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/")); 2172 CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/lib/")); 2173 CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/share/")); 2174 tree_node_file *relinked_share = cxTreeFind(tree, "/share/"); 2175 tree_node_file *relinked_lib = cxTreeFind(tree, "/lib/"); 2176 CX_TEST_ASSERT(relinked_share != NULL); 2177 CX_TEST_ASSERT(relinked_share->parent == tree->root); 2178 CX_TEST_ASSERT(relinked_lib != NULL); 2179 CX_TEST_ASSERT(relinked_lib->parent == tree->root); 2180 CX_TEST_ASSERT(NULL != cxTreeFind(tree, "/home/")); 2181 2182 2183 cxTreeFree(tree); 2184 // we are not done yet, because we need to free the removed stuff 2185 CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc)); 2186 2187 cxFree(alloc, usr); 2188 // for the subtree, we use a little trick and wrap it in a new tree 2189 CxTree *foo_tree = cxTreeCreateWrapped(alloc, foo, tree_node_file_layout); 2190 foo_tree->collection.allocator = alloc; 2191 cxDefineAdvancedDestructor(foo_tree, cxFree, alloc); 2192 cxTreeFree(foo_tree); 2193 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); 2194 } 2195 cx_testing_allocator_destroy(&talloc); 2196 } 2197 2198 CX_TEST(test_tree_high_add_find_destroy_nodes) { 2199 CxTestingAllocator talloc; 2200 cx_testing_allocator_init(&talloc); 2201 CxAllocator *alloc = &talloc.base; 2202 2203 CX_TEST_DO { 2204 CxTree *tree = cxTreeCreate( 2205 alloc, tree_node_file_create_hl, 2206 tree_node_file_search, tree_node_file_search_data, 2207 tree_node_file_layout 2208 ); 2209 2210 const char *paths[] = { 2211 "/", 2212 "/usr/", 2213 "/home/", 2214 "/usr/lib/", 2215 "/home/foo/", 2216 "/home/foo/bar/" 2217 }; 2218 cxTreeInsertArray(tree, paths, sizeof(const char*), 6); 2219 2220 tree_node_file *foo = cxTreeFind(tree, "/home/foo/"); 2221 CX_TEST_ASSERT(NULL != foo); 2222 CX_TEST_ASSERT(0 == strcmp("/home/foo/", foo->path)); 2223 CX_TEST_ASSERT(NULL != foo->parent); 2224 CX_TEST_ASSERT(0 == strcmp("/home/", foo->parent->path)); 2225 CX_TEST_ASSERT(cxTreeSize(tree) == 6); 2226 2227 CX_TEST_ASSERT(0 == cxTreeAddChild(tree, foo->parent, "/home/baz/")); 2228 tree_node_file *baz = cxTreeFind(tree, "/home/baz/"); 2229 CX_TEST_ASSERT(NULL != baz); 2230 CX_TEST_ASSERT(0 == strcmp("/home/baz/", baz->path)); 2231 CX_TEST_ASSERT(NULL != baz->parent); 2232 CX_TEST_ASSERT(0 == strcmp("/home/", baz->parent->path)); 2233 CX_TEST_ASSERT(cxTreeSize(tree) == 7); 2234 2235 tree_node_file *home = cxTreeFind(tree, "/home/"); 2236 CX_TEST_ASSERT(NULL == cxTreeFindInSubtree(tree, "/usr/", foo, 0)); 2237 tree_node_file *bar = cxTreeFindInSubtree(tree, "/home/foo/bar/", home, 0); 2238 CX_TEST_ASSERT(NULL != bar); 2239 CX_TEST_ASSERT(0 == strcmp("/home/foo/bar/", bar->path)); 2240 CX_TEST_ASSERT(bar->parent == foo); 2241 2242 tree_node_file *share = cxCalloc(alloc, 1, sizeof(tree_node_file)); 2243 share->path = "/usr/share/"; 2244 tree_node_file *usr = cxTreeFind(tree, "/usr/"); 2245 cxTreeAddChildNode(tree, usr, share); 2246 CX_TEST_ASSERT(cxTreeSize(tree) == 8); 2247 2248 cxTreeDestroySubtree(tree, foo); 2249 CX_TEST_ASSERT(cxTreeSize(tree) == 6); 2250 CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/foo/")); 2251 CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/foo/bar/")); 2252 CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/bar/")); 2253 2254 CX_TEST_ASSERT(0 == cxTreeDestroyNode(tree, usr, test_tree_remove_node_relink_mock)); 2255 CX_TEST_ASSERT(cxTreeSize(tree) == 5); 2256 CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/")); 2257 CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/lib/")); 2258 CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/share/")); 2259 tree_node_file *relinked_share = cxTreeFind(tree, "/share/"); 2260 tree_node_file *relinked_lib = cxTreeFind(tree, "/lib/"); 2261 CX_TEST_ASSERT(relinked_share != NULL); 2262 CX_TEST_ASSERT(relinked_share->parent == tree->root); 2263 CX_TEST_ASSERT(relinked_lib != NULL); 2264 CX_TEST_ASSERT(relinked_lib->parent == tree->root); 2265 CX_TEST_ASSERT(NULL != cxTreeFind(tree, "/home/")); 2266 2267 cxTreeFree(tree); 2268 // all memory should be free when using destroy instead of remove 2269 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); 2270 } 2271 cx_testing_allocator_destroy(&talloc); 2272 } 2273 2274 CX_TEST(test_tree_high_remove_or_destroy_root) { 2275 CxTestingAllocator talloc; 2276 cx_testing_allocator_init(&talloc); 2277 CxAllocator *alloc = &talloc.base; 2278 2279 CX_TEST_DO { 2280 CxTree *tree = cxTreeCreate( 2281 alloc, tree_node_file_create_hl, 2282 tree_node_file_search, tree_node_file_search_data, 2283 tree_node_file_layout 2284 ); 2285 2286 const char *paths[] = { 2287 "/", 2288 "/usr/", 2289 "/home/", 2290 "/usr/lib/", 2291 "/home/foo/", 2292 "/home/foo/bar/" 2293 }; 2294 cxTreeInsertArray(tree, paths, sizeof(const char*), 6); 2295 void *root = tree->root; 2296 CX_TEST_ASSERT(0 != cxTreeRemoveNode(tree, root, NULL)); 2297 CX_TEST_ASSERT(tree->root == root); 2298 CX_TEST_ASSERT(cxTreeSize(tree) == 6); 2299 CX_TEST_ASSERT(0 != cxTreeDestroyNode(tree, root, NULL)); 2300 CX_TEST_ASSERT(tree->root == root); 2301 CX_TEST_ASSERT(cxTreeSize(tree) == 6); 2302 cxTreeRemoveSubtree(tree, root); 2303 CX_TEST_ASSERT(cxTreeSize(tree) == 0); 2304 CX_TEST_ASSERT(tree->root == NULL); 2305 CX_TEST_ASSERT(cxTreeDepth(tree) == 0); 2306 cxTreeFree(tree); 2307 CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc)); 2308 CxTree *w = cxTreeCreateWrapped(alloc, root, tree_node_file_layout); 2309 cxDefineAdvancedDestructor(w, cxFree, alloc); 2310 cxTreeDestroySubtree(w, w->root); 2311 CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc)); 2312 cxTreeFree(w); 2313 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); 2314 } 2315 cx_testing_allocator_destroy(&talloc); 2316 } 2317 2318 static void test_tree_high_simple_destructor_func(void *node) { 2319 ((tree_node *)node)->data++; 2320 } 2321 2322 CX_TEST(test_tree_high_simple_destructor) { 2323 tree_node root = {0}, child1 = {0}, child2 = {0}, child3 = {0}; 2324 cx_tree_link(&root, &child1, tree_node_layout); 2325 cx_tree_link(&root, &child2, tree_node_layout); 2326 cx_tree_link(&child1, &child3, tree_node_layout); 2327 CX_TEST_DO { 2328 CxTree *tree = cxTreeCreateWrapped(cxDefaultAllocator, &root, tree_node_layout); 2329 cxDefineDestructor(tree,test_tree_high_simple_destructor_func); 2330 cxTreeDestroyNode(tree, &child1, NULL); 2331 cxTreeFree(tree); 2332 CX_TEST_ASSERT(root.data == 1); 2333 CX_TEST_ASSERT(child1.data == 1); 2334 CX_TEST_ASSERT(child2.data == 1); 2335 CX_TEST_ASSERT(child3.data == 1); 2336 } 2337 } 2338 2339 CX_TEST(test_tree_high_iterator) { 2340 CxTree *tree = cxTreeCreate( 2341 NULL, tree_node_file_create_hl, 2342 tree_node_file_search, tree_node_file_search_data, 2343 tree_node_file_layout 2344 ); 2345 cxTreeInsert(tree, "/"); 2346 cxTreeInsert(tree, "/etc"); 2347 cxTreeInsert(tree, "/home"); 2348 cxTreeInsert(tree, "/home/jane"); 2349 cxTreeInsert(tree, "/usr"); 2350 cxTreeInsert(tree, "/usr/local"); 2351 cxTreeInsert(tree, "/usr/local/lib"); 2352 cxTreeInsert(tree, "/var"); 2353 cxTreeInsert(tree, "/var/lib"); 2354 CX_TEST_DO { 2355 const char *expected_order[] = { 2356 "/", 2357 "/etc", 2358 "/home", 2359 "/home/jane", 2360 "/usr", 2361 "/usr/local", 2362 "/usr/local/lib", 2363 "/var", 2364 "/var/lib", 2365 }; 2366 const char *actual_order[9]; 2367 CxTreeIterator iter = cxTreeIterate(tree, false); 2368 cx_foreach(tree_node_file*, p, iter) { 2369 actual_order[iter.counter-1] = p->path; 2370 } 2371 CX_TEST_ASSERT(iter.counter == 9); 2372 for (unsigned i = 0; i < 9; i++) { 2373 CX_TEST_ASSERT(strcmp(expected_order[i], actual_order[i]) == 0); 2374 } 2375 } 2376 cxTreeFree(tree); 2377 } 2378 2379 CX_TEST(test_tree_high_visitor) { 2380 CxTree *tree = cxTreeCreate( 2381 NULL, tree_node_file_create_hl, 2382 tree_node_file_search, tree_node_file_search_data, 2383 tree_node_file_layout 2384 ); 2385 cxTreeInsert(tree, "/"); 2386 cxTreeInsert(tree, "/etc"); 2387 cxTreeInsert(tree, "/home"); 2388 cxTreeInsert(tree, "/home/jane"); 2389 cxTreeInsert(tree, "/usr"); 2390 cxTreeInsert(tree, "/usr/local"); 2391 cxTreeInsert(tree, "/usr/local/lib"); 2392 cxTreeInsert(tree, "/var"); 2393 cxTreeInsert(tree, "/var/lib"); 2394 CX_TEST_DO { 2395 const char *expected_order[] = { 2396 "/", 2397 "/etc", 2398 "/home", 2399 "/usr", 2400 "/var", 2401 "/home/jane", 2402 "/usr/local", 2403 "/var/lib", 2404 "/usr/local/lib", 2405 }; 2406 const char *actual_order[9]; 2407 CxTreeVisitor iter = cxTreeVisit(tree); 2408 cx_foreach(tree_node_file*, p, iter) { 2409 actual_order[iter.counter-1] = p->path; 2410 } 2411 CX_TEST_ASSERT(iter.counter == 9); 2412 for (unsigned i = 0; i < 9; i++) { 2413 CX_TEST_ASSERT(strcmp(expected_order[i], actual_order[i]) == 0); 2414 } 2415 } 2416 cxTreeFree(tree); 2417 } 2418 2419 CxTestSuite *cx_test_suite_tree_low_level(void) { 2420 CxTestSuite *suite = cx_test_suite_new("tree (low level)"); 2421 2422 cx_test_register(suite, test_tree_link_new_child); 2423 cx_test_register(suite, test_tree_link_add_child); 2424 cx_test_register(suite, test_tree_link_move_to_other_parent); 2425 cx_test_register(suite, test_tree_unlink); 2426 cx_test_register(suite, test_tree_unlink_no_prev); 2427 cx_test_register(suite, test_tree2_link_new_child); 2428 cx_test_register(suite, test_tree2_link_add_child); 2429 cx_test_register(suite, test_tree2_link_move_to_other_parent); 2430 cx_test_register(suite, test_tree2_unlink); 2431 cx_test_register(suite, test_tree_search); 2432 cx_test_register(suite, test_tree_search_with_max_depth); 2433 cx_test_register(suite, test_tree_iterator_create_and_dispose); 2434 cx_test_register(suite, test_tree_iterator_create_for_empty_tree); 2435 cx_test_register(suite, test_tree_iterator_basic_only_enter); 2436 cx_test_register(suite, test_tree_iterator_basic_enter_and_exit); 2437 cx_test_register(suite, test_tree_iterator_subtree_enter_and_exit); 2438 cx_test_register(suite, test_tree_iterator_xml); 2439 cx_test_register(suite, test_tree_iterator_free_nodes); 2440 cx_test_register(suite, test_tree_visitor_create_and_dispose); 2441 cx_test_register(suite, test_tree_visitor); 2442 cx_test_register(suite, test_tree_visitor_no_children); 2443 cx_test_register(suite, test_tree_visitor_no_branching); 2444 cx_test_register(suite, test_tree_visitor_subtree); 2445 cx_test_register(suite, test_tree_visitor_continue); 2446 cx_test_register(suite, test_tree_iterator_continue); 2447 cx_test_register(suite, test_tree_iterator_continue_with_exit); 2448 cx_test_register(suite, test_tree_add_one); 2449 cx_test_register(suite, test_tree_add_one_existing); 2450 cx_test_register(suite, test_tree_add_one_no_match); 2451 cx_test_register(suite, test_tree_add_duplicate_root); 2452 cx_test_register(suite, test_tree_add_zero); 2453 cx_test_register(suite, test_tree_add_many); 2454 cx_test_register(suite, test_tree_add_many_but_not_all); 2455 cx_test_register(suite, test_tree_add_many_with_dupl_and_no_match); 2456 cx_test_register(suite, test_tree_add_create_from_array); 2457 2458 return suite; 2459 } 2460 2461 CxTestSuite *cx_test_suite_tree_high_level(void) { 2462 CxTestSuite *suite = cx_test_suite_new("tree (high level)"); 2463 2464 cx_test_register(suite, test_tree_high_create); 2465 cx_test_register(suite, test_tree_high_create_simple); 2466 cx_test_register(suite, test_tree_high_create_wrapped); 2467 cx_test_register(suite, test_tree_high_tree_depth); 2468 cx_test_register(suite, test_tree_high_set_parent); 2469 cx_test_register(suite, test_tree_high_insert_one); 2470 cx_test_register(suite, test_tree_high_insert_many); 2471 cx_test_register(suite, test_tree_high_add_find_remove_nodes); 2472 cx_test_register(suite, test_tree_high_add_find_destroy_nodes); 2473 cx_test_register(suite, test_tree_high_remove_or_destroy_root); 2474 cx_test_register(suite, test_tree_high_simple_destructor); 2475 cx_test_register(suite, test_tree_high_iterator); 2476 cx_test_register(suite, test_tree_high_visitor); 2477 2478 return suite; 2479 } 2480