00001
00024
00032 #include "ut0rbt.h"
00033
00034
00053 #if defined(IB_RBT_TESTING)
00054 #warning "Testing enabled!"
00055 #endif
00056
00057 #define ROOT(t) (t->root->left)
00058 #define SIZEOF_NODE(t) ((sizeof(ib_rbt_node_t) + t->sizeof_value) - 1)
00059
00060
00062 static
00063 void
00064 rbt_print_subtree(
00065
00066 const ib_rbt_t* tree,
00067 const ib_rbt_node_t* node,
00068 ib_rbt_print_node print)
00069 {
00070
00071 if (node != tree->nil) {
00072 print(node);
00073 rbt_print_subtree(tree, node->left, print);
00074 rbt_print_subtree(tree, node->right, print);
00075 }
00076 }
00077
00078
00081 static
00082 ibool
00083 rbt_check_ordering(
00084
00085 const ib_rbt_t* tree)
00086 {
00087 const ib_rbt_node_t* node;
00088 const ib_rbt_node_t* prev = NULL;
00089
00090
00091 for (node = rbt_first(tree); node; node = rbt_next(tree, prev)) {
00092
00093 if (prev && tree->compare(prev->value, node->value) >= 0) {
00094 return(FALSE);
00095 }
00096
00097 prev = node;
00098 }
00099
00100 return(TRUE);
00101 }
00102
00103
00107 static
00108 ibool
00109 rbt_count_black_nodes(
00110
00111 const ib_rbt_t* tree,
00112 const ib_rbt_node_t* node)
00113 {
00114 ulint result;
00115
00116 if (node != tree->nil) {
00117 ulint left_height = rbt_count_black_nodes(tree, node->left);
00118
00119 ulint right_height = rbt_count_black_nodes(tree, node->right);
00120
00121 if (left_height == 0
00122 || right_height == 0
00123 || left_height != right_height) {
00124
00125 result = 0;
00126 } else if (node->color == IB_RBT_RED) {
00127
00128
00129 if (node->left->color != IB_RBT_BLACK
00130 || node->right->color != IB_RBT_BLACK) {
00131
00132 result = 0;
00133 } else {
00134 result = left_height;
00135 }
00136
00137 } else if (node->color != IB_RBT_BLACK) {
00138
00139 result = 0;
00140 } else {
00141
00142 result = right_height + 1;
00143 }
00144 } else {
00145 result = 1;
00146 }
00147
00148 return(result);
00149 }
00150
00151
00154 static
00155 void
00156 rbt_rotate_left(
00157
00158 const ib_rbt_node_t* nil,
00159 ib_rbt_node_t* node)
00160 {
00161 ib_rbt_node_t* right = node->right;
00162
00163 node->right = right->left;
00164
00165 if (right->left != nil) {
00166 right->left->parent = node;
00167 }
00168
00169
00170 right->parent = node->parent;
00171
00172
00173
00174 if (node == node->parent->left) {
00175
00176 node->parent->left = right;
00177 } else {
00178
00179 node->parent->right = right;
00180 }
00181
00182
00183 right->left = node;
00184 node->parent = right;
00185 }
00186
00187
00190 static
00191 void
00192 rbt_rotate_right(
00193
00194 const ib_rbt_node_t* nil,
00195 ib_rbt_node_t* node)
00196 {
00197 ib_rbt_node_t* left = node->left;
00198
00199 node->left = left->right;
00200
00201 if (left->right != nil) {
00202 left->right->parent = node;
00203 }
00204
00205
00206 left->parent = node->parent;
00207
00208
00209
00210 if (node == node->parent->right) {
00211
00212 node->parent->right = left;
00213 } else {
00214
00215 node->parent->left = left;
00216 }
00217
00218
00219 left->right = node;
00220 node->parent = left;
00221 }
00222
00223
00225 static
00226 ib_rbt_node_t*
00227 rbt_tree_add_child(
00228
00229 const ib_rbt_t* tree,
00230 ib_rbt_bound_t* parent,
00231 ib_rbt_node_t* node)
00232 {
00233
00234 ib_rbt_node_t* last = (ib_rbt_node_t*) parent->last;
00235
00236 if (last == tree->root || parent->result < 0) {
00237 last->left = node;
00238 } else {
00239
00240 ut_a(parent->result != 0);
00241
00242 last->right = node;
00243 }
00244
00245 node->parent = last;
00246
00247 return(node);
00248 }
00249
00250
00252 static
00253 ib_rbt_node_t*
00254 rbt_tree_insert(
00255
00256 ib_rbt_t* tree,
00257 const void* key,
00258 ib_rbt_node_t* node)
00259 {
00260 ib_rbt_bound_t parent;
00261 ib_rbt_node_t* current = ROOT(tree);
00262
00263 parent.result = 0;
00264 parent.last = tree->root;
00265
00266
00267 while (current != tree->nil) {
00268
00269 parent.last = current;
00270 parent.result = tree->compare(key, current->value);
00271
00272 if (parent.result < 0) {
00273 current = current->left;
00274 } else {
00275 current = current->right;
00276 }
00277 }
00278
00279 ut_a(current == tree->nil);
00280
00281 rbt_tree_add_child(tree, &parent, node);
00282
00283 return(node);
00284 }
00285
00286
00288 static
00289 void
00290 rbt_balance_tree(
00291
00292 const ib_rbt_t* tree,
00293 ib_rbt_node_t* node)
00294 {
00295 const ib_rbt_node_t* nil = tree->nil;
00296 ib_rbt_node_t* parent = node->parent;
00297
00298
00299 node->color = IB_RBT_RED;
00300
00301 while (node != ROOT(tree) && parent->color == IB_RBT_RED) {
00302 ib_rbt_node_t* grand_parent = parent->parent;
00303
00304 if (parent == grand_parent->left) {
00305 ib_rbt_node_t* uncle = grand_parent->right;
00306
00307 if (uncle->color == IB_RBT_RED) {
00308
00309
00310 uncle->color = IB_RBT_BLACK;
00311 parent->color = IB_RBT_BLACK;
00312 grand_parent->color = IB_RBT_RED;
00313
00314
00315 node = grand_parent;
00316
00317 } else {
00318
00319 if (node == parent->right) {
00320
00321
00322
00323 node = parent;
00324 rbt_rotate_left(nil, node);
00325 }
00326
00327 grand_parent = node->parent->parent;
00328
00329
00330 node->parent->color = IB_RBT_BLACK;
00331 grand_parent->color = IB_RBT_RED;
00332
00333 rbt_rotate_right(nil, grand_parent);
00334 }
00335
00336 } else {
00337 ib_rbt_node_t* uncle = grand_parent->left;
00338
00339 if (uncle->color == IB_RBT_RED) {
00340
00341
00342 uncle->color = IB_RBT_BLACK;
00343 parent->color = IB_RBT_BLACK;
00344 grand_parent->color = IB_RBT_RED;
00345
00346
00347 node = grand_parent;
00348
00349 } else {
00350
00351 if (node == parent->left) {
00352
00353
00354
00355 node = parent;
00356 rbt_rotate_right(nil, node);
00357 }
00358
00359 grand_parent = node->parent->parent;
00360
00361
00362 node->parent->color = IB_RBT_BLACK;
00363 grand_parent->color = IB_RBT_RED;
00364
00365 rbt_rotate_left(nil, grand_parent);
00366 }
00367 }
00368
00369 parent = node->parent;
00370 }
00371
00372
00373 ROOT(tree)->color = IB_RBT_BLACK;
00374 }
00375
00376
00379 static
00380 ib_rbt_node_t*
00381 rbt_find_successor(
00382
00383 const ib_rbt_t* tree,
00384 const ib_rbt_node_t* current)
00387 {
00388 const ib_rbt_node_t* nil = tree->nil;
00389 ib_rbt_node_t* next = current->right;
00390
00391
00392 if (next != nil) {
00393
00394
00395 while (next->left != nil) {
00396 next = next->left;
00397 }
00398
00399 } else {
00400 ib_rbt_node_t* parent = current->parent;
00401
00402
00403 next = (ib_rbt_node_t*) current;
00404
00405 while (parent != tree->root && next == parent->right) {
00406 next = parent;
00407 parent = next->parent;
00408 }
00409
00410 next = (parent == tree->root) ? NULL : parent;
00411 }
00412
00413 return(next);
00414 }
00415
00416
00419 static
00420 ib_rbt_node_t*
00421 rbt_find_predecessor(
00422
00423 const ib_rbt_t* tree,
00424 const ib_rbt_node_t* current)
00427 {
00428 const ib_rbt_node_t* nil = tree->nil;
00429 ib_rbt_node_t* prev = current->left;
00430
00431
00432 if (prev != nil) {
00433
00434
00435 while (prev->right != nil) {
00436 prev = prev->right;
00437 }
00438
00439 } else {
00440 ib_rbt_node_t* parent = current->parent;
00441
00442
00443 prev = (ib_rbt_node_t*)current;
00444
00445 while (parent != tree->root && prev == parent->left) {
00446 prev = parent;
00447 parent = prev->parent;
00448 }
00449
00450 prev = (parent == tree->root) ? NULL : parent;
00451 }
00452
00453 return(prev);
00454 }
00455
00456
00459 static
00460 void
00461 rbt_eject_node(
00462
00463 ib_rbt_node_t* eject,
00464 ib_rbt_node_t* node)
00465 {
00466
00467 if (eject->parent->left == eject) {
00468 eject->parent->left = node;
00469 } else if (eject->parent->right == eject) {
00470 eject->parent->right = node;
00471 } else {
00472 ut_a(0);
00473 }
00474
00475
00476
00477 node->parent = eject->parent;
00478 }
00479
00480
00482 static
00483 void
00484 rbt_replace_node(
00485
00486 ib_rbt_node_t* replace,
00487 ib_rbt_node_t* node)
00488 {
00489 ib_rbt_color_t color = node->color;
00490
00491
00492 node->left = replace->left;
00493 node->right = replace->right;
00494
00495
00496 node->left->parent = node;
00497 node->right->parent = node;
00498
00499
00500 rbt_eject_node(replace, node);
00501
00502
00503 node->color = replace->color;
00504 replace->color = color;
00505 }
00506
00507
00510 static
00511 ib_rbt_node_t*
00512 rbt_detach_node(
00513
00514 const ib_rbt_t* tree,
00515 ib_rbt_node_t* node)
00516 {
00517 ib_rbt_node_t* child;
00518 const ib_rbt_node_t* nil = tree->nil;
00519
00520 if (node->left != nil && node->right != nil) {
00521
00522 ib_rbt_node_t* successor = rbt_find_successor(tree, node);
00523
00524 ut_a(successor != nil);
00525 ut_a(successor->parent != nil);
00526 ut_a(successor->left == nil);
00527
00528 child = successor->right;
00529
00530
00531 rbt_eject_node(successor, child);
00532
00533
00534 rbt_replace_node(node, successor);
00535 } else {
00536 ut_a(node->left == nil || node->right == nil);
00537
00538 child = (node->left != nil) ? node->left : node->right;
00539
00540
00541 rbt_eject_node(node, child);
00542 }
00543
00544
00545 node->parent = node->right = node->left = tree->nil;
00546
00547 return(child);
00548 }
00549
00550
00553 static
00554 ib_rbt_node_t*
00555 rbt_balance_right(
00556
00557 const ib_rbt_node_t* nil,
00558 ib_rbt_node_t* parent,
00559 ib_rbt_node_t* sibling)
00560 {
00561 ib_rbt_node_t* node = NULL;
00562
00563 ut_a(sibling != nil);
00564
00565
00566 if (sibling->color == IB_RBT_RED) {
00567
00568 parent->color = IB_RBT_RED;
00569 sibling->color = IB_RBT_BLACK;
00570
00571 rbt_rotate_left(nil, parent);
00572
00573 sibling = parent->right;
00574
00575 ut_a(sibling != nil);
00576 }
00577
00578
00579 if (sibling->left->color == IB_RBT_BLACK
00580 && sibling->right->color == IB_RBT_BLACK) {
00581
00582 node = parent;
00583 sibling->color = IB_RBT_RED;
00584
00585 } else {
00586 if (sibling->right->color == IB_RBT_BLACK) {
00587
00588 ut_a(sibling->left->color == IB_RBT_RED);
00589
00590 sibling->color = IB_RBT_RED;
00591 sibling->left->color = IB_RBT_BLACK;
00592
00593 rbt_rotate_right(nil, sibling);
00594
00595 sibling = parent->right;
00596 ut_a(sibling != nil);
00597 }
00598
00599 sibling->color = parent->color;
00600 sibling->right->color = IB_RBT_BLACK;
00601
00602 parent->color = IB_RBT_BLACK;
00603
00604 rbt_rotate_left(nil, parent);
00605 }
00606
00607 return(node);
00608 }
00609
00610
00613 static
00614 ib_rbt_node_t*
00615 rbt_balance_left(
00616
00617 const ib_rbt_node_t* nil,
00618 ib_rbt_node_t* parent,
00619 ib_rbt_node_t* sibling)
00620 {
00621 ib_rbt_node_t* node = NULL;
00622
00623 ut_a(sibling != nil);
00624
00625
00626 if (sibling->color == IB_RBT_RED) {
00627
00628 parent->color = IB_RBT_RED;
00629 sibling->color = IB_RBT_BLACK;
00630
00631 rbt_rotate_right(nil, parent);
00632 sibling = parent->left;
00633
00634 ut_a(sibling != nil);
00635 }
00636
00637
00638 if (sibling->right->color == IB_RBT_BLACK
00639 && sibling->left->color == IB_RBT_BLACK) {
00640
00641 node = parent;
00642 sibling->color = IB_RBT_RED;
00643
00644 } else {
00645 if (sibling->left->color == IB_RBT_BLACK) {
00646
00647 ut_a(sibling->right->color == IB_RBT_RED);
00648
00649 sibling->color = IB_RBT_RED;
00650 sibling->right->color = IB_RBT_BLACK;
00651
00652 rbt_rotate_left(nil, sibling);
00653
00654 sibling = parent->left;
00655
00656 ut_a(sibling != nil);
00657 }
00658
00659 sibling->color = parent->color;
00660 sibling->left->color = IB_RBT_BLACK;
00661
00662 parent->color = IB_RBT_BLACK;
00663
00664 rbt_rotate_right(nil, parent);
00665 }
00666
00667 return(node);
00668 }
00669
00670
00672 static
00673 void
00674 rbt_remove_node_and_rebalance(
00675
00676 ib_rbt_t* tree,
00677 ib_rbt_node_t* node)
00678 {
00679
00680
00681 ib_rbt_node_t* child = rbt_detach_node(tree, node);
00682
00683 if (node->color == IB_RBT_BLACK) {
00684 ib_rbt_node_t* last = child;
00685
00686 ROOT(tree)->color = IB_RBT_RED;
00687
00688 while (child && child->color == IB_RBT_BLACK) {
00689 ib_rbt_node_t* parent = child->parent;
00690
00691
00692
00693 if (parent->left == child) {
00694
00695 child = rbt_balance_right(
00696 tree->nil, parent, parent->right);
00697
00698 } else if (parent->right == child) {
00699
00700 child = rbt_balance_left(
00701 tree->nil, parent, parent->left);
00702
00703 } else {
00704 ut_error;
00705 }
00706
00707 if (child) {
00708 last = child;
00709 }
00710 }
00711
00712 ut_a(last);
00713
00714 last->color = IB_RBT_BLACK;
00715 ROOT(tree)->color = IB_RBT_BLACK;
00716 }
00717
00718
00719 --tree->n_nodes;
00720 }
00721
00722
00724 static
00725 void
00726 rbt_free_node(
00727
00728 ib_rbt_node_t* node,
00729 ib_rbt_node_t* nil)
00730 {
00731 if (node != nil) {
00732 rbt_free_node(node->left, nil);
00733 rbt_free_node(node->right, nil);
00734
00735 ut_free(node);
00736 }
00737 }
00738
00739
00741 UNIV_INTERN
00742 void
00743 rbt_free(
00744
00745 ib_rbt_t* tree)
00746 {
00747 rbt_free_node(tree->root, tree->nil);
00748 ut_free(tree->nil);
00749 ut_free(tree);
00750 }
00751
00752
00755 UNIV_INTERN
00756 ib_rbt_t*
00757 rbt_create(
00758
00759 size_t sizeof_value,
00760 ib_rbt_compare compare)
00761 {
00762 ib_rbt_t* tree;
00763 ib_rbt_node_t* node;
00764
00765 tree = (ib_rbt_t*) ut_malloc(sizeof(*tree));
00766 memset(tree, 0, sizeof(*tree));
00767
00768 tree->sizeof_value = sizeof_value;
00769
00770
00771 node = tree->nil = (ib_rbt_node_t*) ut_malloc(sizeof(*node));
00772 memset(node, 0, sizeof(*node));
00773
00774 node->color = IB_RBT_BLACK;
00775 node->parent = node->left = node->right = node;
00776
00777
00778
00779 node = tree->root = (ib_rbt_node_t*) ut_malloc(sizeof(*node));
00780 memset(node, 0, sizeof(*node));
00781
00782 node->color = IB_RBT_BLACK;
00783 node->parent = node->left = node->right = tree->nil;
00784
00785 tree->compare = compare;
00786
00787 return(tree);
00788 }
00789
00790
00793 UNIV_INTERN
00794 const ib_rbt_node_t*
00795 rbt_insert(
00796
00797 ib_rbt_t* tree,
00798 const void* key,
00799 const void* value)
00801 {
00802 ib_rbt_node_t* node;
00803
00804
00805 node = (ib_rbt_node_t*) ut_malloc(SIZEOF_NODE(tree));
00806
00807 memcpy(node->value, value, tree->sizeof_value);
00808 node->parent = node->left = node->right = tree->nil;
00809
00810
00811 rbt_tree_insert(tree, key, node);
00812 rbt_balance_tree(tree, node);
00813
00814 ++tree->n_nodes;
00815
00816 return(node);
00817 }
00818
00819
00822 UNIV_INTERN
00823 const ib_rbt_node_t*
00824 rbt_add_node(
00825
00826 ib_rbt_t* tree,
00827 ib_rbt_bound_t* parent,
00828 const void* value)
00830 {
00831 ib_rbt_node_t* node;
00832
00833
00834 node = (ib_rbt_node_t*) ut_malloc(SIZEOF_NODE(tree));
00835
00836 memcpy(node->value, value, tree->sizeof_value);
00837 node->parent = node->left = node->right = tree->nil;
00838
00839
00840 if (parent->last == NULL) {
00841 parent->last = tree->root;
00842 }
00843
00844
00845
00846 rbt_tree_add_child(tree, parent, node);
00847 rbt_balance_tree(tree, node);
00848
00849 ++tree->n_nodes;
00850
00851 #if defined(IB_RBT_TESTING)
00852 ut_a(rbt_validate(tree));
00853 #endif
00854 return(node);
00855 }
00856
00857
00860 UNIV_INTERN
00861 const ib_rbt_node_t*
00862 rbt_lookup(
00863
00864 const ib_rbt_t* tree,
00865 const void* key)
00866 {
00867 const ib_rbt_node_t* current = ROOT(tree);
00868
00869
00870 while (current != tree->nil) {
00871 int result = tree->compare(key, current->value);
00872
00873 if (result < 0) {
00874 current = current->left;
00875 } else if (result > 0) {
00876 current = current->right;
00877 } else {
00878 break;
00879 }
00880 }
00881
00882 return(current != tree->nil ? current : NULL);
00883 }
00884
00885
00888 UNIV_INTERN
00889 ibool
00890 rbt_delete(
00891
00892 ib_rbt_t* tree,
00893 const void* key)
00894 {
00895 ibool deleted = FALSE;
00896 ib_rbt_node_t* node = (ib_rbt_node_t*) rbt_lookup(tree, key);
00897
00898 if (node) {
00899 rbt_remove_node_and_rebalance(tree, node);
00900
00901 ut_free(node);
00902 deleted = TRUE;
00903 }
00904
00905 return(deleted);
00906 }
00907
00908
00912 UNIV_INTERN
00913 ib_rbt_node_t*
00914 rbt_remove_node(
00915
00916 ib_rbt_t* tree,
00917 const ib_rbt_node_t* const_node)
00921 {
00922
00923 rbt_remove_node_and_rebalance(tree, (ib_rbt_node_t*) const_node);
00924
00925
00926
00927
00928
00929 return((ib_rbt_node_t*) const_node);
00930 }
00931
00932
00935 UNIV_INTERN
00936 const ib_rbt_node_t*
00937 rbt_lower_bound(
00938
00939 const ib_rbt_t* tree,
00940 const void* key)
00941 {
00942 ib_rbt_node_t* lb_node = NULL;
00943 ib_rbt_node_t* current = ROOT(tree);
00944
00945 while (current != tree->nil) {
00946 int result = tree->compare(key, current->value);
00947
00948 if (result > 0) {
00949
00950 current = current->right;
00951
00952 } else if (result < 0) {
00953
00954 lb_node = current;
00955 current = current->left;
00956
00957 } else {
00958 lb_node = current;
00959 break;
00960 }
00961 }
00962
00963 return(lb_node);
00964 }
00965
00966
00969 UNIV_INTERN
00970 const ib_rbt_node_t*
00971 rbt_upper_bound(
00972
00973 const ib_rbt_t* tree,
00974 const void* key)
00975 {
00976 ib_rbt_node_t* ub_node = NULL;
00977 ib_rbt_node_t* current = ROOT(tree);
00978
00979 while (current != tree->nil) {
00980 int result = tree->compare(key, current->value);
00981
00982 if (result > 0) {
00983
00984 ub_node = current;
00985 current = current->right;
00986
00987 } else if (result < 0) {
00988
00989 current = current->left;
00990
00991 } else {
00992 ub_node = current;
00993 break;
00994 }
00995 }
00996
00997 return(ub_node);
00998 }
00999
01000
01003 UNIV_INTERN
01004 int
01005 rbt_search(
01006
01007 const ib_rbt_t* tree,
01008 ib_rbt_bound_t* parent,
01009 const void* key)
01010 {
01011 ib_rbt_node_t* current = ROOT(tree);
01012
01013
01014 parent->result = 1;
01015 parent->last = NULL;
01016
01017 while (current != tree->nil) {
01018
01019 parent->last = current;
01020 parent->result = tree->compare(key, current->value);
01021
01022 if (parent->result > 0) {
01023 current = current->right;
01024 } else if (parent->result < 0) {
01025 current = current->left;
01026 } else {
01027 break;
01028 }
01029 }
01030
01031 return(parent->result);
01032 }
01033
01034
01038 UNIV_INTERN
01039 int
01040 rbt_search_cmp(
01041
01042 const ib_rbt_t* tree,
01043 ib_rbt_bound_t* parent,
01044 const void* key,
01045 ib_rbt_compare compare)
01046 {
01047 ib_rbt_node_t* current = ROOT(tree);
01048
01049
01050 parent->result = 1;
01051 parent->last = NULL;
01052
01053 while (current != tree->nil) {
01054
01055 parent->last = current;
01056 parent->result = compare(key, current->value);
01057
01058 if (parent->result > 0) {
01059 current = current->right;
01060 } else if (parent->result < 0) {
01061 current = current->left;
01062 } else {
01063 break;
01064 }
01065 }
01066
01067 return(parent->result);
01068 }
01069
01070
01072 UNIV_INTERN
01073 const ib_rbt_node_t*
01074 rbt_first(
01075
01076
01077 const ib_rbt_t* tree)
01078 {
01079 ib_rbt_node_t* first = NULL;
01080 ib_rbt_node_t* current = ROOT(tree);
01081
01082 while (current != tree->nil) {
01083 first = current;
01084 current = current->left;
01085 }
01086
01087 return(first);
01088 }
01089
01090
01093 UNIV_INTERN
01094 const ib_rbt_node_t*
01095 rbt_last(
01096
01097 const ib_rbt_t* tree)
01098 {
01099 ib_rbt_node_t* last = NULL;
01100 ib_rbt_node_t* current = ROOT(tree);
01101
01102 while (current != tree->nil) {
01103 last = current;
01104 current = current->right;
01105 }
01106
01107 return(last);
01108 }
01109
01110
01113 UNIV_INTERN
01114 const ib_rbt_node_t*
01115 rbt_next(
01116
01117 const ib_rbt_t* tree,
01118 const ib_rbt_node_t* current)
01119 {
01120 return(current ? rbt_find_successor(tree, current) : NULL);
01121 }
01122
01123
01126 UNIV_INTERN
01127 const ib_rbt_node_t*
01128 rbt_prev(
01129
01130 const ib_rbt_t* tree,
01131 const ib_rbt_node_t* current)
01132 {
01133 return(current ? rbt_find_predecessor(tree, current) : NULL);
01134 }
01135
01136
01138 UNIV_INTERN
01139 void
01140 rbt_clear(
01141
01142 ib_rbt_t* tree)
01143 {
01144 rbt_free_node(ROOT(tree), tree->nil);
01145
01146 tree->n_nodes = 0;
01147 tree->root->left = tree->root->right = tree->nil;
01148 }
01149
01150
01153 UNIV_INTERN
01154 ulint
01155 rbt_merge_uniq(
01156
01157 ib_rbt_t* dst,
01158 const ib_rbt_t* src)
01159 {
01160 ib_rbt_bound_t parent;
01161 ulint n_merged = 0;
01162 const ib_rbt_node_t* src_node = rbt_first(src);
01163
01164 if (rbt_empty(src) || dst == src) {
01165 return(0);
01166 }
01167
01168 for (; src_node; src_node = rbt_next(src, src_node)) {
01169
01170 if (rbt_search(dst, &parent, src_node->value) != 0) {
01171 rbt_add_node(dst, &parent, src_node->value);
01172 ++n_merged;
01173 }
01174 }
01175
01176 return(n_merged);
01177 }
01178
01179
01184 UNIV_INTERN
01185 ulint
01186 rbt_merge_uniq_destructive(
01187
01188 ib_rbt_t* dst,
01189 ib_rbt_t* src)
01190 {
01191 ib_rbt_bound_t parent;
01192 ib_rbt_node_t* src_node;
01193 ulint old_size = rbt_size(dst);
01194
01195 if (rbt_empty(src) || dst == src) {
01196 return(0);
01197 }
01198
01199 for (src_node = (ib_rbt_node_t*) rbt_first(src); src_node; ) {
01200 ib_rbt_node_t* prev = src_node;
01201
01202 src_node = (ib_rbt_node_t*)rbt_next(src, prev);
01203
01204
01205 if (rbt_search(dst, &parent, prev->value) != 0) {
01206
01207
01208
01209 rbt_remove_node_and_rebalance(src, prev);
01210
01211
01212 prev->parent = prev->left = prev->right = dst->nil;
01213 rbt_tree_add_child(dst, &parent, prev);
01214 rbt_balance_tree(dst, prev);
01215
01216 ++dst->n_nodes;
01217 }
01218 }
01219
01220 #if defined(IB_RBT_TESTING)
01221 ut_a(rbt_validate(dst));
01222 ut_a(rbt_validate(src));
01223 #endif
01224 return(rbt_size(dst) - old_size);
01225 }
01226
01227
01231 UNIV_INTERN
01232 ibool
01233 rbt_validate(
01234
01235 const ib_rbt_t* tree)
01236 {
01237 if (rbt_count_black_nodes(tree, ROOT(tree)) > 0) {
01238 return(rbt_check_ordering(tree));
01239 }
01240
01241 return(FALSE);
01242 }
01243
01244
01246 UNIV_INTERN
01247 void
01248 rbt_print(
01249
01250 const ib_rbt_t* tree,
01251 ib_rbt_print_node print)
01252 {
01253 rbt_print_subtree(tree, ROOT(tree), print);
01254 }