1 #include "test/jemalloc_test.h" 2 3 #include <stdlib.h> 4 5 #include "jemalloc/internal/rb.h" 6 7 #define rbtn_black_height(a_type, a_field, a_rbt, r_height) do { \ 8 a_type *rbp_bh_t; \ 9 for (rbp_bh_t = (a_rbt)->rbt_root, (r_height) = 0; rbp_bh_t != \ 10 NULL; rbp_bh_t = rbtn_left_get(a_type, a_field, \ 11 rbp_bh_t)) { \ 12 if (!rbtn_red_get(a_type, a_field, rbp_bh_t)) { \ 13 (r_height)++; \ 14 } \ 15 } \ 16 } while (0) 17 18 static bool summarize_always_returns_true = false; 19 20 typedef struct node_s node_t; 21 struct node_s { 22 #define NODE_MAGIC 0x9823af7e 23 uint32_t magic; 24 rb_node(node_t) link; 25 /* Order used by nodes. */ 26 uint64_t key; 27 /* 28 * Our made-up summary property is "specialness", with summarization 29 * taking the max. 30 */ 31 uint64_t specialness; 32 33 /* 34 * Used by some of the test randomization to avoid double-removing 35 * nodes. 36 */ 37 bool mid_remove; 38 39 /* 40 * To test searching functionality, we want to temporarily weaken the 41 * ordering to allow non-equal nodes that nevertheless compare equal. 42 */ 43 bool allow_duplicates; 44 45 /* 46 * In check_consistency, it's handy to know a node's rank in the tree; 47 * this tracks it (but only there; not all tests use this). 48 */ 49 int rank; 50 int filtered_rank; 51 52 /* 53 * Replicate the internal structure of the tree, to make sure the 54 * implementation doesn't miss any updates. 55 */ 56 const node_t *summary_lchild; 57 const node_t *summary_rchild; 58 uint64_t summary_max_specialness; 59 }; 60 61 static int 62 node_cmp(const node_t *a, const node_t *b) { 63 int ret; 64 65 expect_u32_eq(a->magic, NODE_MAGIC, "Bad magic"); 66 expect_u32_eq(b->magic, NODE_MAGIC, "Bad magic"); 67 68 ret = (a->key > b->key) - (a->key < b->key); 69 if (ret == 0 && !a->allow_duplicates) { 70 /* 71 * Duplicates are not allowed in the tree, so force an 72 * arbitrary ordering for non-identical items with equal keys, 73 * unless the user is searching and wants to allow the 74 * duplicate. 75 */ 76 ret = (((uintptr_t)a) > ((uintptr_t)b)) 77 - (((uintptr_t)a) < ((uintptr_t)b)); 78 } 79 return ret; 80 } 81 82 static uint64_t 83 node_subtree_specialness(node_t *n, const node_t *lchild, 84 const node_t *rchild) { 85 uint64_t subtree_specialness = n->specialness; 86 if (lchild != NULL 87 && lchild->summary_max_specialness > subtree_specialness) { 88 subtree_specialness = lchild->summary_max_specialness; 89 } 90 if (rchild != NULL 91 && rchild->summary_max_specialness > subtree_specialness) { 92 subtree_specialness = rchild->summary_max_specialness; 93 } 94 return subtree_specialness; 95 } 96 97 static bool 98 node_summarize(node_t *a, const node_t *lchild, const node_t *rchild) { 99 uint64_t new_summary_max_specialness = node_subtree_specialness( 100 a, lchild, rchild); 101 bool changed = (a->summary_lchild != lchild) 102 || (a->summary_rchild != rchild) 103 || (new_summary_max_specialness != a->summary_max_specialness); 104 a->summary_max_specialness = new_summary_max_specialness; 105 a->summary_lchild = lchild; 106 a->summary_rchild = rchild; 107 return changed || summarize_always_returns_true; 108 } 109 110 typedef rb_tree(node_t) tree_t; 111 rb_summarized_proto(static, tree_, tree_t, node_t); 112 rb_summarized_gen(static, tree_, tree_t, node_t, link, node_cmp, 113 node_summarize); 114 115 static bool 116 specialness_filter_node(void *ctx, node_t *node) { 117 uint64_t specialness = *(uint64_t *)ctx; 118 return node->specialness >= specialness; 119 } 120 121 static bool 122 specialness_filter_subtree(void *ctx, node_t *node) { 123 uint64_t specialness = *(uint64_t *)ctx; 124 return node->summary_max_specialness >= specialness; 125 } 126 127 static node_t * 128 tree_iterate_cb(tree_t *tree, node_t *node, void *data) { 129 unsigned *i = (unsigned *)data; 130 node_t *search_node; 131 132 expect_u32_eq(node->magic, NODE_MAGIC, "Bad magic"); 133 134 /* Test rb_search(). */ 135 search_node = tree_search(tree, node); 136 expect_ptr_eq(search_node, node, 137 "tree_search() returned unexpected node"); 138 139 /* Test rb_nsearch(). */ 140 search_node = tree_nsearch(tree, node); 141 expect_ptr_eq(search_node, node, 142 "tree_nsearch() returned unexpected node"); 143 144 /* Test rb_psearch(). */ 145 search_node = tree_psearch(tree, node); 146 expect_ptr_eq(search_node, node, 147 "tree_psearch() returned unexpected node"); 148 149 (*i)++; 150 151 return NULL; 152 } 153 154 TEST_BEGIN(test_rb_empty) { 155 tree_t tree; 156 node_t key; 157 158 tree_new(&tree); 159 160 expect_true(tree_empty(&tree), "Tree should be empty"); 161 expect_ptr_null(tree_first(&tree), "Unexpected node"); 162 expect_ptr_null(tree_last(&tree), "Unexpected node"); 163 164 key.key = 0; 165 key.magic = NODE_MAGIC; 166 expect_ptr_null(tree_search(&tree, &key), "Unexpected node"); 167 168 key.key = 0; 169 key.magic = NODE_MAGIC; 170 expect_ptr_null(tree_nsearch(&tree, &key), "Unexpected node"); 171 172 key.key = 0; 173 key.magic = NODE_MAGIC; 174 expect_ptr_null(tree_psearch(&tree, &key), "Unexpected node"); 175 176 unsigned nodes = 0; 177 tree_iter_filtered(&tree, NULL, &tree_iterate_cb, 178 &nodes, &specialness_filter_node, &specialness_filter_subtree, 179 NULL); 180 expect_u_eq(0, nodes, ""); 181 182 nodes = 0; 183 tree_reverse_iter_filtered(&tree, NULL, &tree_iterate_cb, 184 &nodes, &specialness_filter_node, &specialness_filter_subtree, 185 NULL); 186 expect_u_eq(0, nodes, ""); 187 188 expect_ptr_null(tree_first_filtered(&tree, &specialness_filter_node, 189 &specialness_filter_subtree, NULL), ""); 190 expect_ptr_null(tree_last_filtered(&tree, &specialness_filter_node, 191 &specialness_filter_subtree, NULL), ""); 192 193 key.key = 0; 194 key.magic = NODE_MAGIC; 195 expect_ptr_null(tree_search_filtered(&tree, &key, 196 &specialness_filter_node, &specialness_filter_subtree, NULL), ""); 197 expect_ptr_null(tree_nsearch_filtered(&tree, &key, 198 &specialness_filter_node, &specialness_filter_subtree, NULL), ""); 199 expect_ptr_null(tree_psearch_filtered(&tree, &key, 200 &specialness_filter_node, &specialness_filter_subtree, NULL), ""); 201 } 202 TEST_END 203 204 static unsigned 205 tree_recurse(node_t *node, unsigned black_height, unsigned black_depth) { 206 unsigned ret = 0; 207 node_t *left_node; 208 node_t *right_node; 209 210 if (node == NULL) { 211 return ret; 212 } 213 214 left_node = rbtn_left_get(node_t, link, node); 215 right_node = rbtn_right_get(node_t, link, node); 216 217 expect_ptr_eq(left_node, node->summary_lchild, 218 "summary missed a tree update"); 219 expect_ptr_eq(right_node, node->summary_rchild, 220 "summary missed a tree update"); 221 222 uint64_t expected_subtree_specialness = node_subtree_specialness(node, 223 left_node, right_node); 224 expect_u64_eq(expected_subtree_specialness, 225 node->summary_max_specialness, "Incorrect summary"); 226 227 if (!rbtn_red_get(node_t, link, node)) { 228 black_depth++; 229 } 230 231 /* Red nodes must be interleaved with black nodes. */ 232 if (rbtn_red_get(node_t, link, node)) { 233 if (left_node != NULL) { 234 expect_false(rbtn_red_get(node_t, link, left_node), 235 "Node should be black"); 236 } 237 if (right_node != NULL) { 238 expect_false(rbtn_red_get(node_t, link, right_node), 239 "Node should be black"); 240 } 241 } 242 243 /* Self. */ 244 expect_u32_eq(node->magic, NODE_MAGIC, "Bad magic"); 245 246 /* Left subtree. */ 247 if (left_node != NULL) { 248 ret += tree_recurse(left_node, black_height, black_depth); 249 } else { 250 ret += (black_depth != black_height); 251 } 252 253 /* Right subtree. */ 254 if (right_node != NULL) { 255 ret += tree_recurse(right_node, black_height, black_depth); 256 } else { 257 ret += (black_depth != black_height); 258 } 259 260 return ret; 261 } 262 263 static unsigned 264 tree_iterate(tree_t *tree) { 265 unsigned i; 266 267 i = 0; 268 tree_iter(tree, NULL, tree_iterate_cb, (void *)&i); 269 270 return i; 271 } 272 273 static unsigned 274 tree_iterate_reverse(tree_t *tree) { 275 unsigned i; 276 277 i = 0; 278 tree_reverse_iter(tree, NULL, tree_iterate_cb, (void *)&i); 279 280 return i; 281 } 282 283 static void 284 node_remove(tree_t *tree, node_t *node, unsigned nnodes) { 285 node_t *search_node; 286 unsigned black_height, imbalances; 287 288 tree_remove(tree, node); 289 290 /* Test rb_nsearch(). */ 291 search_node = tree_nsearch(tree, node); 292 if (search_node != NULL) { 293 expect_u64_ge(search_node->key, node->key, 294 "Key ordering error"); 295 } 296 297 /* Test rb_psearch(). */ 298 search_node = tree_psearch(tree, node); 299 if (search_node != NULL) { 300 expect_u64_le(search_node->key, node->key, 301 "Key ordering error"); 302 } 303 304 node->magic = 0; 305 306 rbtn_black_height(node_t, link, tree, black_height); 307 imbalances = tree_recurse(tree->rbt_root, black_height, 0); 308 expect_u_eq(imbalances, 0, "Tree is unbalanced"); 309 expect_u_eq(tree_iterate(tree), nnodes-1, 310 "Unexpected node iteration count"); 311 expect_u_eq(tree_iterate_reverse(tree), nnodes-1, 312 "Unexpected node iteration count"); 313 } 314 315 static node_t * 316 remove_iterate_cb(tree_t *tree, node_t *node, void *data) { 317 unsigned *nnodes = (unsigned *)data; 318 node_t *ret = tree_next(tree, node); 319 320 node_remove(tree, node, *nnodes); 321 322 return ret; 323 } 324 325 static node_t * 326 remove_reverse_iterate_cb(tree_t *tree, node_t *node, void *data) { 327 unsigned *nnodes = (unsigned *)data; 328 node_t *ret = tree_prev(tree, node); 329 330 node_remove(tree, node, *nnodes); 331 332 return ret; 333 } 334 335 static void 336 destroy_cb(node_t *node, void *data) { 337 unsigned *nnodes = (unsigned *)data; 338 339 expect_u_gt(*nnodes, 0, "Destruction removed too many nodes"); 340 (*nnodes)--; 341 } 342 343 TEST_BEGIN(test_rb_random) { 344 enum { 345 NNODES = 25, 346 NBAGS = 500, 347 SEED = 42 348 }; 349 sfmt_t *sfmt; 350 uint64_t bag[NNODES]; 351 tree_t tree; 352 node_t nodes[NNODES]; 353 unsigned i, j, k, black_height, imbalances; 354 355 sfmt = init_gen_rand(SEED); 356 for (i = 0; i < NBAGS; i++) { 357 switch (i) { 358 case 0: 359 /* Insert in order. */ 360 for (j = 0; j < NNODES; j++) { 361 bag[j] = j; 362 } 363 break; 364 case 1: 365 /* Insert in reverse order. */ 366 for (j = 0; j < NNODES; j++) { 367 bag[j] = NNODES - j - 1; 368 } 369 break; 370 default: 371 for (j = 0; j < NNODES; j++) { 372 bag[j] = gen_rand64_range(sfmt, NNODES); 373 } 374 } 375 376 /* 377 * We alternate test behavior with a period of 2 here, and a 378 * period of 5 down below, so there's no cycle in which certain 379 * combinations get omitted. 380 */ 381 summarize_always_returns_true = (i % 2 == 0); 382 383 for (j = 1; j <= NNODES; j++) { 384 /* Initialize tree and nodes. */ 385 tree_new(&tree); 386 for (k = 0; k < j; k++) { 387 nodes[k].magic = NODE_MAGIC; 388 nodes[k].key = bag[k]; 389 nodes[k].specialness = gen_rand64_range(sfmt, 390 NNODES); 391 nodes[k].mid_remove = false; 392 nodes[k].allow_duplicates = false; 393 nodes[k].summary_lchild = NULL; 394 nodes[k].summary_rchild = NULL; 395 nodes[k].summary_max_specialness = 0; 396 } 397 398 /* Insert nodes. */ 399 for (k = 0; k < j; k++) { 400 tree_insert(&tree, &nodes[k]); 401 402 rbtn_black_height(node_t, link, &tree, 403 black_height); 404 imbalances = tree_recurse(tree.rbt_root, 405 black_height, 0); 406 expect_u_eq(imbalances, 0, 407 "Tree is unbalanced"); 408 409 expect_u_eq(tree_iterate(&tree), k+1, 410 "Unexpected node iteration count"); 411 expect_u_eq(tree_iterate_reverse(&tree), k+1, 412 "Unexpected node iteration count"); 413 414 expect_false(tree_empty(&tree), 415 "Tree should not be empty"); 416 expect_ptr_not_null(tree_first(&tree), 417 "Tree should not be empty"); 418 expect_ptr_not_null(tree_last(&tree), 419 "Tree should not be empty"); 420 421 tree_next(&tree, &nodes[k]); 422 tree_prev(&tree, &nodes[k]); 423 } 424 425 /* Remove nodes. */ 426 switch (i % 5) { 427 case 0: 428 for (k = 0; k < j; k++) { 429 node_remove(&tree, &nodes[k], j - k); 430 } 431 break; 432 case 1: 433 for (k = j; k > 0; k--) { 434 node_remove(&tree, &nodes[k-1], k); 435 } 436 break; 437 case 2: { 438 node_t *start; 439 unsigned nnodes = j; 440 441 start = NULL; 442 do { 443 start = tree_iter(&tree, start, 444 remove_iterate_cb, (void *)&nnodes); 445 nnodes--; 446 } while (start != NULL); 447 expect_u_eq(nnodes, 0, 448 "Removal terminated early"); 449 break; 450 } case 3: { 451 node_t *start; 452 unsigned nnodes = j; 453 454 start = NULL; 455 do { 456 start = tree_reverse_iter(&tree, start, 457 remove_reverse_iterate_cb, 458 (void *)&nnodes); 459 nnodes--; 460 } while (start != NULL); 461 expect_u_eq(nnodes, 0, 462 "Removal terminated early"); 463 break; 464 } case 4: { 465 unsigned nnodes = j; 466 tree_destroy(&tree, destroy_cb, &nnodes); 467 expect_u_eq(nnodes, 0, 468 "Destruction terminated early"); 469 break; 470 } default: 471 not_reached(); 472 } 473 } 474 } 475 fini_gen_rand(sfmt); 476 } 477 TEST_END 478 479 static void 480 expect_simple_consistency(tree_t *tree, uint64_t specialness, 481 bool expected_empty, node_t *expected_first, node_t *expected_last) { 482 bool empty; 483 node_t *first; 484 node_t *last; 485 486 empty = tree_empty_filtered(tree, &specialness_filter_node, 487 &specialness_filter_subtree, &specialness); 488 expect_b_eq(expected_empty, empty, ""); 489 490 first = tree_first_filtered(tree, 491 &specialness_filter_node, &specialness_filter_subtree, 492 (void *)&specialness); 493 expect_ptr_eq(expected_first, first, ""); 494 495 last = tree_last_filtered(tree, 496 &specialness_filter_node, &specialness_filter_subtree, 497 (void *)&specialness); 498 expect_ptr_eq(expected_last, last, ""); 499 } 500 501 TEST_BEGIN(test_rb_filter_simple) { 502 enum {FILTER_NODES = 10}; 503 node_t nodes[FILTER_NODES]; 504 for (unsigned i = 0; i < FILTER_NODES; i++) { 505 nodes[i].magic = NODE_MAGIC; 506 nodes[i].key = i; 507 if (i == 0) { 508 nodes[i].specialness = 0; 509 } else { 510 nodes[i].specialness = ffs_u(i); 511 } 512 nodes[i].mid_remove = false; 513 nodes[i].allow_duplicates = false; 514 nodes[i].summary_lchild = NULL; 515 nodes[i].summary_rchild = NULL; 516 nodes[i].summary_max_specialness = 0; 517 } 518 519 summarize_always_returns_true = false; 520 521 tree_t tree; 522 tree_new(&tree); 523 524 /* Should be empty */ 525 expect_simple_consistency(&tree, /* specialness */ 0, /* empty */ true, 526 /* first */ NULL, /* last */ NULL); 527 528 /* Fill in just the odd nodes. */ 529 for (int i = 1; i < FILTER_NODES; i += 2) { 530 tree_insert(&tree, &nodes[i]); 531 } 532 533 /* A search for an odd node should succeed. */ 534 expect_simple_consistency(&tree, /* specialness */ 0, /* empty */ false, 535 /* first */ &nodes[1], /* last */ &nodes[9]); 536 537 /* But a search for an even one should fail. */ 538 expect_simple_consistency(&tree, /* specialness */ 1, /* empty */ true, 539 /* first */ NULL, /* last */ NULL); 540 541 /* Now we add an even. */ 542 tree_insert(&tree, &nodes[4]); 543 expect_simple_consistency(&tree, /* specialness */ 1, /* empty */ false, 544 /* first */ &nodes[4], /* last */ &nodes[4]); 545 546 /* A smaller even, and a larger even. */ 547 tree_insert(&tree, &nodes[2]); 548 tree_insert(&tree, &nodes[8]); 549 550 /* 551 * A first-search (resp. last-search) for an even should switch to the 552 * lower (higher) one, now that it's been added. 553 */ 554 expect_simple_consistency(&tree, /* specialness */ 1, /* empty */ false, 555 /* first */ &nodes[2], /* last */ &nodes[8]); 556 557 /* 558 * If we remove 2, a first-search we should go back to 4, while a 559 * last-search should remain unchanged. 560 */ 561 tree_remove(&tree, &nodes[2]); 562 expect_simple_consistency(&tree, /* specialness */ 1, /* empty */ false, 563 /* first */ &nodes[4], /* last */ &nodes[8]); 564 565 /* Reinsert 2, then find it again. */ 566 tree_insert(&tree, &nodes[2]); 567 expect_simple_consistency(&tree, /* specialness */ 1, /* empty */ false, 568 /* first */ &nodes[2], /* last */ &nodes[8]); 569 570 /* Searching for a multiple of 4 should not have changed. */ 571 expect_simple_consistency(&tree, /* specialness */ 2, /* empty */ false, 572 /* first */ &nodes[4], /* last */ &nodes[8]); 573 574 /* And a multiple of 8 */ 575 expect_simple_consistency(&tree, /* specialness */ 3, /* empty */ false, 576 /* first */ &nodes[8], /* last */ &nodes[8]); 577 578 /* But not a multiple of 16 */ 579 expect_simple_consistency(&tree, /* specialness */ 4, /* empty */ true, 580 /* first */ NULL, /* last */ NULL); 581 } 582 TEST_END 583 584 typedef struct iter_ctx_s iter_ctx_t; 585 struct iter_ctx_s { 586 int ncalls; 587 node_t *last_node; 588 589 int ncalls_max; 590 bool forward; 591 }; 592 593 static node_t * 594 tree_iterate_filtered_cb(tree_t *tree, node_t *node, void *arg) { 595 iter_ctx_t *ctx = (iter_ctx_t *)arg; 596 ctx->ncalls++; 597 expect_u64_ge(node->specialness, 1, 598 "Should only invoke cb on nodes that pass the filter"); 599 if (ctx->last_node != NULL) { 600 if (ctx->forward) { 601 expect_d_lt(node_cmp(ctx->last_node, node), 0, 602 "Incorrect iteration order"); 603 } else { 604 expect_d_gt(node_cmp(ctx->last_node, node), 0, 605 "Incorrect iteration order"); 606 } 607 } 608 ctx->last_node = node; 609 if (ctx->ncalls == ctx->ncalls_max) { 610 return node; 611 } 612 return NULL; 613 } 614 615 static int 616 qsort_node_cmp(const void *ap, const void *bp) { 617 node_t *a = *(node_t **)ap; 618 node_t *b = *(node_t **)bp; 619 return node_cmp(a, b); 620 } 621 622 #define UPDATE_TEST_MAX 100 623 static void 624 check_consistency(tree_t *tree, node_t nodes[UPDATE_TEST_MAX], int nnodes) { 625 uint64_t specialness = 1; 626 627 bool empty; 628 bool real_empty = true; 629 node_t *first; 630 node_t *real_first = NULL; 631 node_t *last; 632 node_t *real_last = NULL; 633 for (int i = 0; i < nnodes; i++) { 634 if (nodes[i].specialness >= specialness) { 635 real_empty = false; 636 if (real_first == NULL 637 || node_cmp(&nodes[i], real_first) < 0) { 638 real_first = &nodes[i]; 639 } 640 if (real_last == NULL 641 || node_cmp(&nodes[i], real_last) > 0) { 642 real_last = &nodes[i]; 643 } 644 } 645 } 646 647 empty = tree_empty_filtered(tree, &specialness_filter_node, 648 &specialness_filter_subtree, &specialness); 649 expect_b_eq(real_empty, empty, ""); 650 651 first = tree_first_filtered(tree, &specialness_filter_node, 652 &specialness_filter_subtree, &specialness); 653 expect_ptr_eq(real_first, first, ""); 654 655 last = tree_last_filtered(tree, &specialness_filter_node, 656 &specialness_filter_subtree, &specialness); 657 expect_ptr_eq(real_last, last, ""); 658 659 for (int i = 0; i < nnodes; i++) { 660 node_t *next_filtered; 661 node_t *real_next_filtered = NULL; 662 node_t *prev_filtered; 663 node_t *real_prev_filtered = NULL; 664 for (int j = 0; j < nnodes; j++) { 665 if (nodes[j].specialness < specialness) { 666 continue; 667 } 668 if (node_cmp(&nodes[j], &nodes[i]) < 0 669 && (real_prev_filtered == NULL 670 || node_cmp(&nodes[j], real_prev_filtered) > 0)) { 671 real_prev_filtered = &nodes[j]; 672 } 673 if (node_cmp(&nodes[j], &nodes[i]) > 0 674 && (real_next_filtered == NULL 675 || node_cmp(&nodes[j], real_next_filtered) < 0)) { 676 real_next_filtered = &nodes[j]; 677 } 678 } 679 next_filtered = tree_next_filtered(tree, &nodes[i], 680 &specialness_filter_node, &specialness_filter_subtree, 681 &specialness); 682 expect_ptr_eq(real_next_filtered, next_filtered, ""); 683 684 prev_filtered = tree_prev_filtered(tree, &nodes[i], 685 &specialness_filter_node, &specialness_filter_subtree, 686 &specialness); 687 expect_ptr_eq(real_prev_filtered, prev_filtered, ""); 688 689 node_t *search_filtered; 690 node_t *real_search_filtered; 691 node_t *nsearch_filtered; 692 node_t *real_nsearch_filtered; 693 node_t *psearch_filtered; 694 node_t *real_psearch_filtered; 695 696 /* 697 * search, nsearch, psearch from a node before nodes[i] in the 698 * ordering. 699 */ 700 node_t before; 701 before.magic = NODE_MAGIC; 702 before.key = nodes[i].key - 1; 703 before.allow_duplicates = false; 704 real_search_filtered = NULL; 705 search_filtered = tree_search_filtered(tree, &before, 706 &specialness_filter_node, &specialness_filter_subtree, 707 &specialness); 708 expect_ptr_eq(real_search_filtered, search_filtered, ""); 709 710 real_nsearch_filtered = (nodes[i].specialness >= specialness ? 711 &nodes[i] : real_next_filtered); 712 nsearch_filtered = tree_nsearch_filtered(tree, &before, 713 &specialness_filter_node, &specialness_filter_subtree, 714 &specialness); 715 expect_ptr_eq(real_nsearch_filtered, nsearch_filtered, ""); 716 717 real_psearch_filtered = real_prev_filtered; 718 psearch_filtered = tree_psearch_filtered(tree, &before, 719 &specialness_filter_node, &specialness_filter_subtree, 720 &specialness); 721 expect_ptr_eq(real_psearch_filtered, psearch_filtered, ""); 722 723 /* search, nsearch, psearch from nodes[i] */ 724 real_search_filtered = (nodes[i].specialness >= specialness ? 725 &nodes[i] : NULL); 726 search_filtered = tree_search_filtered(tree, &nodes[i], 727 &specialness_filter_node, &specialness_filter_subtree, 728 &specialness); 729 expect_ptr_eq(real_search_filtered, search_filtered, ""); 730 731 real_nsearch_filtered = (nodes[i].specialness >= specialness ? 732 &nodes[i] : real_next_filtered); 733 nsearch_filtered = tree_nsearch_filtered(tree, &nodes[i], 734 &specialness_filter_node, &specialness_filter_subtree, 735 &specialness); 736 expect_ptr_eq(real_nsearch_filtered, nsearch_filtered, ""); 737 738 real_psearch_filtered = (nodes[i].specialness >= specialness ? 739 &nodes[i] : real_prev_filtered); 740 psearch_filtered = tree_psearch_filtered(tree, &nodes[i], 741 &specialness_filter_node, &specialness_filter_subtree, 742 &specialness); 743 expect_ptr_eq(real_psearch_filtered, psearch_filtered, ""); 744 745 /* 746 * search, nsearch, psearch from a node equivalent to but 747 * distinct from nodes[i]. 748 */ 749 node_t equiv; 750 equiv.magic = NODE_MAGIC; 751 equiv.key = nodes[i].key; 752 equiv.allow_duplicates = true; 753 real_search_filtered = (nodes[i].specialness >= specialness ? 754 &nodes[i] : NULL); 755 search_filtered = tree_search_filtered(tree, &equiv, 756 &specialness_filter_node, &specialness_filter_subtree, 757 &specialness); 758 expect_ptr_eq(real_search_filtered, search_filtered, ""); 759 760 real_nsearch_filtered = (nodes[i].specialness >= specialness ? 761 &nodes[i] : real_next_filtered); 762 nsearch_filtered = tree_nsearch_filtered(tree, &equiv, 763 &specialness_filter_node, &specialness_filter_subtree, 764 &specialness); 765 expect_ptr_eq(real_nsearch_filtered, nsearch_filtered, ""); 766 767 real_psearch_filtered = (nodes[i].specialness >= specialness ? 768 &nodes[i] : real_prev_filtered); 769 psearch_filtered = tree_psearch_filtered(tree, &equiv, 770 &specialness_filter_node, &specialness_filter_subtree, 771 &specialness); 772 expect_ptr_eq(real_psearch_filtered, psearch_filtered, ""); 773 774 /* 775 * search, nsearch, psearch from a node after nodes[i] in the 776 * ordering. 777 */ 778 node_t after; 779 after.magic = NODE_MAGIC; 780 after.key = nodes[i].key + 1; 781 after.allow_duplicates = false; 782 real_search_filtered = NULL; 783 search_filtered = tree_search_filtered(tree, &after, 784 &specialness_filter_node, &specialness_filter_subtree, 785 &specialness); 786 expect_ptr_eq(real_search_filtered, search_filtered, ""); 787 788 real_nsearch_filtered = real_next_filtered; 789 nsearch_filtered = tree_nsearch_filtered(tree, &after, 790 &specialness_filter_node, &specialness_filter_subtree, 791 &specialness); 792 expect_ptr_eq(real_nsearch_filtered, nsearch_filtered, ""); 793 794 real_psearch_filtered = (nodes[i].specialness >= specialness ? 795 &nodes[i] : real_prev_filtered); 796 psearch_filtered = tree_psearch_filtered(tree, &after, 797 &specialness_filter_node, &specialness_filter_subtree, 798 &specialness); 799 expect_ptr_eq(real_psearch_filtered, psearch_filtered, ""); 800 } 801 802 /* Filtered iteration test setup. */ 803 int nspecial = 0; 804 node_t *sorted_nodes[UPDATE_TEST_MAX]; 805 node_t *sorted_filtered_nodes[UPDATE_TEST_MAX]; 806 for (int i = 0; i < nnodes; i++) { 807 sorted_nodes[i] = &nodes[i]; 808 } 809 qsort(sorted_nodes, nnodes, sizeof(node_t *), &qsort_node_cmp); 810 for (int i = 0; i < nnodes; i++) { 811 sorted_nodes[i]->rank = i; 812 sorted_nodes[i]->filtered_rank = nspecial; 813 if (sorted_nodes[i]->specialness >= 1) { 814 sorted_filtered_nodes[nspecial] = sorted_nodes[i]; 815 nspecial++; 816 } 817 } 818 819 node_t *iter_result; 820 821 iter_ctx_t ctx; 822 ctx.ncalls = 0; 823 ctx.last_node = NULL; 824 ctx.ncalls_max = INT_MAX; 825 ctx.forward = true; 826 827 /* Filtered forward iteration from the beginning. */ 828 iter_result = tree_iter_filtered(tree, NULL, &tree_iterate_filtered_cb, 829 &ctx, &specialness_filter_node, &specialness_filter_subtree, 830 &specialness); 831 expect_ptr_null(iter_result, ""); 832 expect_d_eq(nspecial, ctx.ncalls, ""); 833 /* Filtered forward iteration from a starting point. */ 834 for (int i = 0; i < nnodes; i++) { 835 ctx.ncalls = 0; 836 ctx.last_node = NULL; 837 iter_result = tree_iter_filtered(tree, &nodes[i], 838 &tree_iterate_filtered_cb, &ctx, &specialness_filter_node, 839 &specialness_filter_subtree, &specialness); 840 expect_ptr_null(iter_result, ""); 841 expect_d_eq(nspecial - nodes[i].filtered_rank, ctx.ncalls, ""); 842 } 843 /* Filtered forward iteration from the beginning, with stopping */ 844 for (int i = 0; i < nspecial; i++) { 845 ctx.ncalls = 0; 846 ctx.last_node = NULL; 847 ctx.ncalls_max = i + 1; 848 iter_result = tree_iter_filtered(tree, NULL, 849 &tree_iterate_filtered_cb, &ctx, &specialness_filter_node, 850 &specialness_filter_subtree, &specialness); 851 expect_ptr_eq(sorted_filtered_nodes[i], iter_result, ""); 852 expect_d_eq(ctx.ncalls, i + 1, ""); 853 } 854 /* Filtered forward iteration from a starting point, with stopping. */ 855 for (int i = 0; i < nnodes; i++) { 856 for (int j = 0; j < nspecial - nodes[i].filtered_rank; j++) { 857 ctx.ncalls = 0; 858 ctx.last_node = NULL; 859 ctx.ncalls_max = j + 1; 860 iter_result = tree_iter_filtered(tree, &nodes[i], 861 &tree_iterate_filtered_cb, &ctx, 862 &specialness_filter_node, 863 &specialness_filter_subtree, &specialness); 864 expect_d_eq(j + 1, ctx.ncalls, ""); 865 expect_ptr_eq(sorted_filtered_nodes[ 866 nodes[i].filtered_rank + j], iter_result, ""); 867 } 868 } 869 870 /* Backwards iteration. */ 871 ctx.ncalls = 0; 872 ctx.last_node = NULL; 873 ctx.ncalls_max = INT_MAX; 874 ctx.forward = false; 875 876 /* Filtered backward iteration from the end. */ 877 iter_result = tree_reverse_iter_filtered(tree, NULL, 878 &tree_iterate_filtered_cb, &ctx, &specialness_filter_node, 879 &specialness_filter_subtree, &specialness); 880 expect_ptr_null(iter_result, ""); 881 expect_d_eq(nspecial, ctx.ncalls, ""); 882 /* Filtered backward iteration from a starting point. */ 883 for (int i = 0; i < nnodes; i++) { 884 ctx.ncalls = 0; 885 ctx.last_node = NULL; 886 iter_result = tree_reverse_iter_filtered(tree, &nodes[i], 887 &tree_iterate_filtered_cb, &ctx, &specialness_filter_node, 888 &specialness_filter_subtree, &specialness); 889 expect_ptr_null(iter_result, ""); 890 int surplus_rank = (nodes[i].specialness >= 1 ? 1 : 0); 891 expect_d_eq(nodes[i].filtered_rank + surplus_rank, ctx.ncalls, 892 ""); 893 } 894 /* Filtered backward iteration from the end, with stopping */ 895 for (int i = 0; i < nspecial; i++) { 896 ctx.ncalls = 0; 897 ctx.last_node = NULL; 898 ctx.ncalls_max = i + 1; 899 iter_result = tree_reverse_iter_filtered(tree, NULL, 900 &tree_iterate_filtered_cb, &ctx, &specialness_filter_node, 901 &specialness_filter_subtree, &specialness); 902 expect_ptr_eq(sorted_filtered_nodes[nspecial - i - 1], 903 iter_result, ""); 904 expect_d_eq(ctx.ncalls, i + 1, ""); 905 } 906 /* Filtered backward iteration from a starting point, with stopping. */ 907 for (int i = 0; i < nnodes; i++) { 908 int surplus_rank = (nodes[i].specialness >= 1 ? 1 : 0); 909 for (int j = 0; j < nodes[i].filtered_rank + surplus_rank; 910 j++) { 911 ctx.ncalls = 0; 912 ctx.last_node = NULL; 913 ctx.ncalls_max = j + 1; 914 iter_result = tree_reverse_iter_filtered(tree, 915 &nodes[i], &tree_iterate_filtered_cb, &ctx, 916 &specialness_filter_node, 917 &specialness_filter_subtree, &specialness); 918 expect_d_eq(j + 1, ctx.ncalls, ""); 919 expect_ptr_eq(sorted_filtered_nodes[ 920 nodes[i].filtered_rank - j - 1 + surplus_rank], 921 iter_result, ""); 922 } 923 } 924 } 925 926 static void 927 do_update_search_test(int nnodes, int ntrees, int nremovals, 928 int nupdates) { 929 node_t nodes[UPDATE_TEST_MAX]; 930 assert(nnodes <= UPDATE_TEST_MAX); 931 932 sfmt_t *sfmt = init_gen_rand(12345); 933 for (int i = 0; i < ntrees; i++) { 934 tree_t tree; 935 tree_new(&tree); 936 for (int j = 0; j < nnodes; j++) { 937 nodes[j].magic = NODE_MAGIC; 938 /* 939 * In consistency checking, we increment or decrement a 940 * key and assume that the result is not a key in the 941 * tree. This isn't a *real* concern with 64-bit keys 942 * and a good PRNG, but why not be correct anyways? 943 */ 944 nodes[j].key = 2 * gen_rand64(sfmt); 945 nodes[j].specialness = 0; 946 nodes[j].mid_remove = false; 947 nodes[j].allow_duplicates = false; 948 nodes[j].summary_lchild = NULL; 949 nodes[j].summary_rchild = NULL; 950 nodes[j].summary_max_specialness = 0; 951 tree_insert(&tree, &nodes[j]); 952 } 953 for (int j = 0; j < nremovals; j++) { 954 int victim = (int)gen_rand64_range(sfmt, nnodes); 955 if (!nodes[victim].mid_remove) { 956 tree_remove(&tree, &nodes[victim]); 957 nodes[victim].mid_remove = true; 958 } 959 } 960 for (int j = 0; j < nnodes; j++) { 961 if (nodes[j].mid_remove) { 962 nodes[j].mid_remove = false; 963 nodes[j].key = 2 * gen_rand64(sfmt); 964 tree_insert(&tree, &nodes[j]); 965 } 966 } 967 for (int j = 0; j < nupdates; j++) { 968 uint32_t ind = gen_rand32_range(sfmt, nnodes); 969 nodes[ind].specialness = 1 - nodes[ind].specialness; 970 tree_update_summaries(&tree, &nodes[ind]); 971 check_consistency(&tree, nodes, nnodes); 972 } 973 } 974 } 975 976 TEST_BEGIN(test_rb_update_search) { 977 summarize_always_returns_true = false; 978 do_update_search_test(2, 100, 3, 50); 979 do_update_search_test(5, 100, 3, 50); 980 do_update_search_test(12, 100, 5, 1000); 981 do_update_search_test(100, 1, 50, 500); 982 } 983 TEST_END 984 985 typedef rb_tree(node_t) unsummarized_tree_t; 986 rb_gen(static UNUSED, unsummarized_tree_, unsummarized_tree_t, node_t, link, 987 node_cmp); 988 989 static node_t * 990 unsummarized_tree_iterate_cb(unsummarized_tree_t *tree, node_t *node, 991 void *data) { 992 unsigned *i = (unsigned *)data; 993 (*i)++; 994 return NULL; 995 } 996 /* 997 * The unsummarized and summarized funtionality is implemented via the same 998 * functions; we don't really need to do much more than test that we can exclude 999 * the filtered functionality without anything breaking. 1000 */ 1001 TEST_BEGIN(test_rb_unsummarized) { 1002 unsummarized_tree_t tree; 1003 unsummarized_tree_new(&tree); 1004 unsigned nnodes = 0; 1005 unsummarized_tree_iter(&tree, NULL, &unsummarized_tree_iterate_cb, 1006 &nnodes); 1007 expect_u_eq(0, nnodes, ""); 1008 } 1009 TEST_END 1010 1011 int 1012 main(void) { 1013 return test_no_reentrancy( 1014 test_rb_empty, 1015 test_rb_random, 1016 test_rb_filter_simple, 1017 test_rb_update_search, 1018 test_rb_unsummarized); 1019 } 1020