Drizzled Public API Documentation

ut0rbt.cc
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   /* FIXME: Doesn't do anything yet */
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   /* Iterate over all the nodes, comparing each node with the prev */
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       /* Case 3 */
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     /* Check if it's anything other than RED or BLACK. */
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   /* Right's new parent was node's parent. */
00170   right->parent = node->parent;
00171 
00172   /* Since root's parent is tree->nil and root->parent->left points
00173   back to root, we can avoid the check. */
00174   if (node == node->parent->left) {
00175     /* Node was on the left of its parent. */
00176     node->parent->left = right;
00177   } else {
00178     /* Node must have been on the right. */
00179     node->parent->right = right;
00180   }
00181 
00182   /* Finally, put node on right's left. */
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   /* Left's new parent was node's parent. */
00206   left->parent = node->parent;
00207 
00208   /* Since root's parent is tree->nil and root->parent->left points
00209   back to root, we can avoid the check. */
00210   if (node == node->parent->right) {
00211       /* Node was on the left of its parent. */
00212             node->parent->right = left;
00213   } else {
00214       /* Node must have been on the left. */
00215             node->parent->left = left;
00216   }
00217 
00218   /* Finally, put node on left's right. */
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   /* Cast away the const. */
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     /* FIXME: We don't handle duplicates (yet)! */
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   /* Regular binary search. */
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   /* Restore the red-black property. */
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         /* Case 1 - change the colors. */
00310         uncle->color = IB_RBT_BLACK;
00311         parent->color = IB_RBT_BLACK;
00312         grand_parent->color = IB_RBT_RED;
00313 
00314         /* Move node up the tree. */
00315         node = grand_parent;
00316 
00317       } else {
00318 
00319         if (node == parent->right) {
00320           /* Right is a black node and node is
00321           to the right, case 2 - move node
00322           up and rotate. */
00323           node = parent;
00324           rbt_rotate_left(nil, node);
00325         }
00326 
00327         grand_parent = node->parent->parent;
00328 
00329         /* Case 3. */
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         /* Case 1 - change the colors. */
00342         uncle->color = IB_RBT_BLACK;
00343         parent->color = IB_RBT_BLACK;
00344         grand_parent->color = IB_RBT_RED;
00345 
00346         /* Move node up the tree. */
00347         node = grand_parent;
00348 
00349       } else {
00350 
00351         if (node == parent->left) {
00352           /* Left is a black node and node is to
00353           the right, case 2 - move node up and
00354           rotate. */
00355           node = parent;
00356           rbt_rotate_right(nil, node);
00357         }
00358 
00359         grand_parent = node->parent->parent;
00360 
00361         /* Case 3. */
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   /* Color the root black. */
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   /* Is there a sub-tree to the right that we can follow. */
00392   if (next != nil) {
00393 
00394     /* Follow the left most links of the current right child. */
00395     while (next->left != nil) {
00396       next = next->left;
00397     }
00398 
00399   } else { /* We will have to go up the tree to find the successor. */
00400     ib_rbt_node_t*  parent = current->parent;
00401 
00402     /* Cast away the const. */
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   /* Is there a sub-tree to the left that we can follow. */
00432   if (prev != nil) {
00433 
00434     /* Follow the right most links of the current left child. */
00435     while (prev->right != nil) {
00436       prev = prev->right;
00437     }
00438 
00439   } else { /* We will have to go up the tree to find the precedecessor. */
00440     ib_rbt_node_t*  parent = current->parent;
00441 
00442     /* Cast away the const. */
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   /* Update the to be ejected node's parent's child pointers. */
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   /* eject is now an orphan but otherwise its pointers
00475   and color are left intact. */
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   /* Update the node pointers. */
00492   node->left = replace->left;
00493   node->right = replace->right;
00494 
00495   /* Update the child node pointers. */
00496   node->left->parent = node;
00497   node->right->parent = node;
00498 
00499   /* Make the parent of replace point to node. */
00500   rbt_eject_node(replace, node);
00501 
00502   /* Swap the colors. */
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     /* Case where the node to be deleted has two children. */
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     /* Remove the successor node and replace with its child. */
00531     rbt_eject_node(successor, child);
00532 
00533     /* Replace the node to delete with its successor node. */
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     /* Replace the node to delete with one of it's children. */
00541     rbt_eject_node(node, child);
00542   }
00543 
00544   /* Reset the node links. */
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   /* Case 3. */
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   /* Since this will violate case 3 because of the change above. */
00579   if (sibling->left->color == IB_RBT_BLACK
00580       && sibling->right->color == IB_RBT_BLACK) {
00581 
00582     node = parent; /* Parent needs to be rebalanced too. */
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   /* Case 3. */
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   /* Since this will violate case 3 because of the change above. */
00638   if (sibling->right->color == IB_RBT_BLACK
00639       && sibling->left->color == IB_RBT_BLACK) {
00640 
00641     node = parent; /* Parent needs to be rebalanced too. */
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   /* Detach node and get the node that will be used
00680   as rebalance start. */
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       /* Did the deletion cause an imbalance in the
00692       parents left sub-tree. */
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   /* Note that we have removed a node from the tree. */
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   /* Create the sentinel (NIL) node. */
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   /* Create the "fake" root, the real root node will be the
00778   left child of this node. */
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   /* Create the node that will hold the value data. */
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   /* Insert in the tree in the usual way. */
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   /* Create the node that will hold the value data */
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   /* If tree is empty */
00840   if (parent->last == NULL) {
00841     parent->last = tree->root;
00842   }
00843 
00844   /* Append the node, the hope here is that the caller knows
00845   what s/he is doing. */
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   /* Regular binary search. */
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   /* Cast away the const. */
00923   rbt_remove_node_and_rebalance(tree, (ib_rbt_node_t*) const_node);
00924 
00925   /* This is to make it easier to do something like this:
00926     ut_free(rbt_remove_node(node));
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   /* Every thing is greater than the NULL root. */
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   /* Every thing is greater than the NULL root. */
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             /* out leftmost node or NULL */
01077   const ib_rbt_t* tree)     /* in: rb 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 (/* No op */; 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     /* Skip duplicates. */
01205     if (rbt_search(dst, &parent, prev->value) != 0) {
01206 
01207       /* Remove and reset the node but preserve
01208       the node (data) value. */
01209       rbt_remove_node_and_rebalance(src, prev);
01210 
01211       /* The nil should be taken from the dst tree. */
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 }