diff options
Diffstat (limited to 'storage/innodb_plugin/ut/ut0rbt.c')
| -rw-r--r-- | storage/innodb_plugin/ut/ut0rbt.c | 1249 |
1 files changed, 1249 insertions, 0 deletions
diff --git a/storage/innodb_plugin/ut/ut0rbt.c b/storage/innodb_plugin/ut/ut0rbt.c new file mode 100644 index 00000000000..3d7bc91e714 --- /dev/null +++ b/storage/innodb_plugin/ut/ut0rbt.c @@ -0,0 +1,1249 @@ +/***************************************************************************** + +Copyright (c) 2006, 2009, Innobase Oy. All Rights Reserved. + +This program is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free Software +Foundation; version 2 of the License. + +This program is distributed in the hope that it will be useful, but WITHOUT +ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS +FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. + +You should have received a copy of the GNU General Public License along with +this program; if not, write to the Free Software Foundation, Inc., 59 Temple +Place, Suite 330, Boston, MA 02111-1307 USA + +*****************************************************************************/ + +/*******************************************************************//** +@file ut/ut0rbt.c +Red-Black tree implementation + +Created 2007-03-20 Sunny Bains +***********************************************************************/ + +#include "ut0rbt.h" + +/************************************************************************ +Definition of a red-black tree +============================== + +A red-black tree is a binary search tree which has the following +red-black properties: + + 1. Every node is either red or black. + 2. Every leaf (NULL - in our case tree->nil) is black. + 3. If a node is red, then both its children are black. + 4. Every simple path from a node to a descendant leaf contains the + same number of black nodes. + + from (3) above, the implication is that on any path from the root + to a leaf, red nodes must not be adjacent. + + However, any number of black nodes may appear in a sequence. */ + +#if defined(IB_RBT_TESTING) +#warning "Testing enabled!" +#endif + +#define ROOT(t) (t->root->left) +#define SIZEOF_NODE(t) ((sizeof(ib_rbt_node_t) + t->sizeof_value) - 1) + +/****************************************************************//** +Print out the sub-tree recursively. */ +static +void +rbt_print_subtree( +/*==============*/ + const ib_rbt_t* tree, /*!< in: tree to traverse */ + const ib_rbt_node_t* node, /*!< in: node to print */ + ib_rbt_print_node print) /*!< in: print key function */ +{ + /* FIXME: Doesn't do anything yet */ + if (node != tree->nil) { + print(node); + rbt_print_subtree(tree, node->left, print); + rbt_print_subtree(tree, node->right, print); + } +} + +/****************************************************************//** +Verify that the keys are in order. +@return TRUE of OK. FALSE if not ordered */ +static +ibool +rbt_check_ordering( +/*===============*/ + const ib_rbt_t* tree) /*!< in: tree to verfify */ +{ + const ib_rbt_node_t* node; + const ib_rbt_node_t* prev = NULL; + + /* Iterate over all the nodes, comparing each node with the prev */ + for (node = rbt_first(tree); node; node = rbt_next(tree, prev)) { + + if (prev && tree->compare(prev->value, node->value) >= 0) { + return(FALSE); + } + + prev = node; + } + + return(TRUE); +} + +/****************************************************************//** +Check that every path from the root to the leaves has the same count. +Count is expressed in the number of black nodes. +@return 0 on failure else black height of the subtree */ +static +ibool +rbt_count_black_nodes( +/*==================*/ + const ib_rbt_t* tree, /*!< in: tree to verify */ + const ib_rbt_node_t* node) /*!< in: start of sub-tree */ +{ + ulint result; + + if (node != tree->nil) { + ulint left_height = rbt_count_black_nodes(tree, node->left); + + ulint right_height = rbt_count_black_nodes(tree, node->right); + + if (left_height == 0 + || right_height == 0 + || left_height != right_height) { + + result = 0; + } else if (node->color == IB_RBT_RED) { + + /* Case 3 */ + if (node->left->color != IB_RBT_BLACK + || node->right->color != IB_RBT_BLACK) { + + result = 0; + } else { + result = left_height; + } + /* Check if it's anything other than RED or BLACK. */ + } else if (node->color != IB_RBT_BLACK) { + + result = 0; + } else { + + result = right_height + 1; + } + } else { + result = 1; + } + + return(result); +} + +/****************************************************************//** +Turn the node's right child's left sub-tree into node's right sub-tree. +This will also make node's right child it's parent. */ +static +void +rbt_rotate_left( +/*============*/ + const ib_rbt_node_t* nil, /*!< in: nil node of the tree */ + ib_rbt_node_t* node) /*!< in: node to rotate */ +{ + ib_rbt_node_t* right = node->right; + + node->right = right->left; + + if (right->left != nil) { + right->left->parent = node; + } + + /* Right's new parent was node's parent. */ + right->parent = node->parent; + + /* Since root's parent is tree->nil and root->parent->left points + back to root, we can avoid the check. */ + if (node == node->parent->left) { + /* Node was on the left of its parent. */ + node->parent->left = right; + } else { + /* Node must have been on the right. */ + node->parent->right = right; + } + + /* Finally, put node on right's left. */ + right->left = node; + node->parent = right; +} + +/****************************************************************//** +Turn the node's left child's right sub-tree into node's left sub-tree. +This also make node's left child it's parent. */ +static +void +rbt_rotate_right( +/*=============*/ + const ib_rbt_node_t* nil, /*!< in: nil node of tree */ + ib_rbt_node_t* node) /*!< in: node to rotate */ +{ + ib_rbt_node_t* left = node->left; + + node->left = left->right; + + if (left->right != nil) { + left->right->parent = node; + } + + /* Left's new parent was node's parent. */ + left->parent = node->parent; + + /* Since root's parent is tree->nil and root->parent->left points + back to root, we can avoid the check. */ + if (node == node->parent->right) { + /* Node was on the left of its parent. */ + node->parent->right = left; + } else { + /* Node must have been on the left. */ + node->parent->left = left; + } + + /* Finally, put node on left's right. */ + left->right = node; + node->parent = left; +} + +/****************************************************************//** +Append a node to the tree. +@return inserted node */ +static +ib_rbt_node_t* +rbt_tree_add_child( +/*===============*/ + const ib_rbt_t* tree, /*!< in: rbt tree */ + ib_rbt_bound_t* parent, /*!< in: node's parent */ + ib_rbt_node_t* node) /*!< in: node to add */ +{ + /* Cast away the const. */ + ib_rbt_node_t* last = (ib_rbt_node_t*) parent->last; + + if (last == tree->root || parent->result < 0) { + last->left = node; + } else { + /* FIXME: We don't handle duplicates (yet)! */ + ut_a(parent->result != 0); + + last->right = node; + } + + node->parent = last; + + return(node); +} + +/****************************************************************//** +Generic binary tree insert +@return inserted node */ +static +ib_rbt_node_t* +rbt_tree_insert( +/*============*/ + ib_rbt_t* tree, /*!< in: rb tree */ + const void* key, /*!< in: key for ordering */ + ib_rbt_node_t* node) /*!< in: node hold the insert value */ +{ + ib_rbt_bound_t parent; + ib_rbt_node_t* current = ROOT(tree); + + parent.result = 0; + parent.last = tree->root; + + /* Regular binary search. */ + while (current != tree->nil) { + + parent.last = current; + parent.result = tree->compare(key, current->value); + + if (parent.result < 0) { + current = current->left; + } else { + current = current->right; + } + } + + ut_a(current == tree->nil); + + rbt_tree_add_child(tree, &parent, node); + + return(node); +} + +/****************************************************************//** +Balance a tree after inserting a node. */ +static +void +rbt_balance_tree( +/*=============*/ + const ib_rbt_t* tree, /*!< in: tree to balance */ + ib_rbt_node_t* node) /*!< in: node that was inserted */ +{ + const ib_rbt_node_t* nil = tree->nil; + ib_rbt_node_t* parent = node->parent; + + /* Restore the red-black property. */ + node->color = IB_RBT_RED; + + while (node != ROOT(tree) && parent->color == IB_RBT_RED) { + ib_rbt_node_t* grand_parent = parent->parent; + + if (parent == grand_parent->left) { + ib_rbt_node_t* uncle = grand_parent->right; + + if (uncle->color == IB_RBT_RED) { + + /* Case 1 - change the colors. */ + uncle->color = IB_RBT_BLACK; + parent->color = IB_RBT_BLACK; + grand_parent->color = IB_RBT_RED; + + /* Move node up the tree. */ + node = grand_parent; + + } else { + + if (node == parent->right) { + /* Right is a black node and node is + to the right, case 2 - move node + up and rotate. */ + node = parent; + rbt_rotate_left(nil, node); + } + + grand_parent = node->parent->parent; + + /* Case 3. */ + node->parent->color = IB_RBT_BLACK; + grand_parent->color = IB_RBT_RED; + + rbt_rotate_right(nil, grand_parent); + } + + } else { + ib_rbt_node_t* uncle = grand_parent->left; + + if (uncle->color == IB_RBT_RED) { + + /* Case 1 - change the colors. */ + uncle->color = IB_RBT_BLACK; + parent->color = IB_RBT_BLACK; + grand_parent->color = IB_RBT_RED; + + /* Move node up the tree. */ + node = grand_parent; + + } else { + + if (node == parent->left) { + /* Left is a black node and node is to + the right, case 2 - move node up and + rotate. */ + node = parent; + rbt_rotate_right(nil, node); + } + + grand_parent = node->parent->parent; + + /* Case 3. */ + node->parent->color = IB_RBT_BLACK; + grand_parent->color = IB_RBT_RED; + + rbt_rotate_left(nil, grand_parent); + } + } + + parent = node->parent; + } + + /* Color the root black. */ + ROOT(tree)->color = IB_RBT_BLACK; +} + +/****************************************************************//** +Find the given node's successor. +@return successor node or NULL if no successor */ +static +ib_rbt_node_t* +rbt_find_successor( +/*===============*/ + const ib_rbt_t* tree, /*!< in: rb tree */ + const ib_rbt_node_t* current)/*!< in: this is declared const + because it can be called via + rbt_next() */ +{ + const ib_rbt_node_t* nil = tree->nil; + ib_rbt_node_t* next = current->right; + + /* Is there a sub-tree to the right that we can follow. */ + if (next != nil) { + + /* Follow the left most links of the current right child. */ + while (next->left != nil) { + next = next->left; + } + + } else { /* We will have to go up the tree to find the successor. */ + ib_rbt_node_t* parent = current->parent; + + /* Cast away the const. */ + next = (ib_rbt_node_t*) current; + + while (parent != tree->root && next == parent->right) { + next = parent; + parent = next->parent; + } + + next = (parent == tree->root) ? NULL : parent; + } + + return(next); +} + +/****************************************************************//** +Find the given node's precedecessor. +@return predecessor node or NULL if no predecesor */ +static +ib_rbt_node_t* +rbt_find_predecessor( +/*=================*/ + const ib_rbt_t* tree, /*!< in: rb tree */ + const ib_rbt_node_t* current) /*!< in: this is declared const + because it can be called via + rbt_prev() */ +{ + const ib_rbt_node_t* nil = tree->nil; + ib_rbt_node_t* prev = current->left; + + /* Is there a sub-tree to the left that we can follow. */ + if (prev != nil) { + + /* Follow the right most links of the current left child. */ + while (prev->right != nil) { + prev = prev->right; + } + + } else { /* We will have to go up the tree to find the precedecessor. */ + ib_rbt_node_t* parent = current->parent; + + /* Cast away the const. */ + prev = (ib_rbt_node_t*)current; + + while (parent != tree->root && prev == parent->left) { + prev = parent; + parent = prev->parent; + } + + prev = (parent == tree->root) ? NULL : parent; + } + + return(prev); +} + +/****************************************************************//** +Replace node with child. After applying transformations eject becomes +an orphan. */ +static +void +rbt_eject_node( +/*===========*/ + ib_rbt_node_t* eject, /*!< in: node to eject */ + ib_rbt_node_t* node) /*!< in: node to replace with */ +{ + /* Update the to be ejected node's parent's child pointers. */ + if (eject->parent->left == eject) { + eject->parent->left = node; + } else if (eject->parent->right == eject) { + eject->parent->right = node; + } else { + ut_a(0); + } + /* eject is now an orphan but otherwise its pointers + and color are left intact. */ + + node->parent = eject->parent; +} + +/****************************************************************//** +Replace a node with another node. */ +static +void +rbt_replace_node( +/*=============*/ + ib_rbt_node_t* replace, /*!< in: node to replace */ + ib_rbt_node_t* node) /*!< in: node to replace with */ +{ + ib_rbt_color_t color = node->color; + + /* Update the node pointers. */ + node->left = replace->left; + node->right = replace->right; + + /* Update the child node pointers. */ + node->left->parent = node; + node->right->parent = node; + + /* Make the parent of replace point to node. */ + rbt_eject_node(replace, node); + + /* Swap the colors. */ + node->color = replace->color; + replace->color = color; +} + +/****************************************************************//** +Detach node from the tree replacing it with one of it's children. +@return the child node that now occupies the position of the detached node */ +static +ib_rbt_node_t* +rbt_detach_node( +/*============*/ + const ib_rbt_t* tree, /*!< in: rb tree */ + ib_rbt_node_t* node) /*!< in: node to detach */ +{ + ib_rbt_node_t* child; + const ib_rbt_node_t* nil = tree->nil; + + if (node->left != nil && node->right != nil) { + /* Case where the node to be deleted has two children. */ + ib_rbt_node_t* successor = rbt_find_successor(tree, node); + + ut_a(successor != nil); + ut_a(successor->parent != nil); + ut_a(successor->left == nil); + + child = successor->right; + + /* Remove the successor node and replace with its child. */ + rbt_eject_node(successor, child); + + /* Replace the node to delete with its successor node. */ + rbt_replace_node(node, successor); + } else { + ut_a(node->left == nil || node->right == nil); + + child = (node->left != nil) ? node->left : node->right; + + /* Replace the node to delete with one of it's children. */ + rbt_eject_node(node, child); + } + + /* Reset the node links. */ + node->parent = node->right = node->left = tree->nil; + + return(child); +} + +/****************************************************************//** +Rebalance the right sub-tree after deletion. +@return node to rebalance if more rebalancing required else NULL */ +static +ib_rbt_node_t* +rbt_balance_right( +/*==============*/ + const ib_rbt_node_t* nil, /*!< in: rb tree nil node */ + ib_rbt_node_t* parent, /*!< in: parent node */ + ib_rbt_node_t* sibling)/*!< in: sibling node */ +{ + ib_rbt_node_t* node = NULL; + + ut_a(sibling != nil); + + /* Case 3. */ + if (sibling->color == IB_RBT_RED) { + + parent->color = IB_RBT_RED; + sibling->color = IB_RBT_BLACK; + + rbt_rotate_left(nil, parent); + + sibling = parent->right; + + ut_a(sibling != nil); + } + + /* Since this will violate case 3 because of the change above. */ + if (sibling->left->color == IB_RBT_BLACK + && sibling->right->color == IB_RBT_BLACK) { + + node = parent; /* Parent needs to be rebalanced too. */ + sibling->color = IB_RBT_RED; + + } else { + if (sibling->right->color == IB_RBT_BLACK) { + + ut_a(sibling->left->color == IB_RBT_RED); + + sibling->color = IB_RBT_RED; + sibling->left->color = IB_RBT_BLACK; + + rbt_rotate_right(nil, sibling); + + sibling = parent->right; + ut_a(sibling != nil); + } + + sibling->color = parent->color; + sibling->right->color = IB_RBT_BLACK; + + parent->color = IB_RBT_BLACK; + + rbt_rotate_left(nil, parent); + } + + return(node); +} + +/****************************************************************//** +Rebalance the left sub-tree after deletion. +@return node to rebalance if more rebalancing required else NULL */ +static +ib_rbt_node_t* +rbt_balance_left( +/*=============*/ + const ib_rbt_node_t* nil, /*!< in: rb tree nil node */ + ib_rbt_node_t* parent, /*!< in: parent node */ + ib_rbt_node_t* sibling)/*!< in: sibling node */ +{ + ib_rbt_node_t* node = NULL; + + ut_a(sibling != nil); + + /* Case 3. */ + if (sibling->color == IB_RBT_RED) { + + parent->color = IB_RBT_RED; + sibling->color = IB_RBT_BLACK; + + rbt_rotate_right(nil, parent); + sibling = parent->left; + + ut_a(sibling != nil); + } + + /* Since this will violate case 3 because of the change above. */ + if (sibling->right->color == IB_RBT_BLACK + && sibling->left->color == IB_RBT_BLACK) { + + node = parent; /* Parent needs to be rebalanced too. */ + sibling->color = IB_RBT_RED; + + } else { + if (sibling->left->color == IB_RBT_BLACK) { + + ut_a(sibling->right->color == IB_RBT_RED); + + sibling->color = IB_RBT_RED; + sibling->right->color = IB_RBT_BLACK; + + rbt_rotate_left(nil, sibling); + + sibling = parent->left; + + ut_a(sibling != nil); + } + + sibling->color = parent->color; + sibling->left->color = IB_RBT_BLACK; + + parent->color = IB_RBT_BLACK; + + rbt_rotate_right(nil, parent); + } + + return(node); +} + +/****************************************************************//** +Delete the node and rebalance the tree if necessary */ +static +void +rbt_remove_node_and_rebalance( +/*==========================*/ + ib_rbt_t* tree, /*!< in: rb tree */ + ib_rbt_node_t* node) /*!< in: node to remove */ +{ + /* Detach node and get the node that will be used + as rebalance start. */ + ib_rbt_node_t* child = rbt_detach_node(tree, node); + + if (node->color == IB_RBT_BLACK) { + ib_rbt_node_t* last = child; + + ROOT(tree)->color = IB_RBT_RED; + + while (child && child->color == IB_RBT_BLACK) { + ib_rbt_node_t* parent = child->parent; + + /* Did the deletion cause an imbalance in the + parents left sub-tree. */ + if (parent->left == child) { + + child = rbt_balance_right( + tree->nil, parent, parent->right); + + } else if (parent->right == child) { + + child = rbt_balance_left( + tree->nil, parent, parent->left); + + } else { + ut_error; + } + + if (child) { + last = child; + } + } + + ut_a(last); + + last->color = IB_RBT_BLACK; + ROOT(tree)->color = IB_RBT_BLACK; + } + + /* Note that we have removed a node from the tree. */ + --tree->n_nodes; +} + +/****************************************************************//** +Recursively free the nodes. */ +static +void +rbt_free_node( +/*==========*/ + ib_rbt_node_t* node, /*!< in: node to free */ + ib_rbt_node_t* nil) /*!< in: rb tree nil node */ +{ + if (node != nil) { + rbt_free_node(node->left, nil); + rbt_free_node(node->right, nil); + + ut_free(node); + } +} + +/****************************************************************//** +Free all the nodes and free the tree. */ +UNIV_INTERN +void +rbt_free( +/*=====*/ + ib_rbt_t* tree) /*!< in: rb tree to free */ +{ + rbt_free_node(tree->root, tree->nil); + ut_free(tree->nil); + ut_free(tree); +} + +/****************************************************************//** +Create an instance of a red black tree. +@return an empty rb tree */ +UNIV_INTERN +ib_rbt_t* +rbt_create( +/*=======*/ + size_t sizeof_value, /*!< in: sizeof data item */ + ib_rbt_compare compare) /*!< in: fn to compare items */ +{ + ib_rbt_t* tree; + ib_rbt_node_t* node; + + tree = (ib_rbt_t*) ut_malloc(sizeof(*tree)); + memset(tree, 0, sizeof(*tree)); + + tree->sizeof_value = sizeof_value; + + /* Create the sentinel (NIL) node. */ + node = tree->nil = (ib_rbt_node_t*) ut_malloc(sizeof(*node)); + memset(node, 0, sizeof(*node)); + + node->color = IB_RBT_BLACK; + node->parent = node->left = node->right = node; + + /* Create the "fake" root, the real root node will be the + left child of this node. */ + node = tree->root = (ib_rbt_node_t*) ut_malloc(sizeof(*node)); + memset(node, 0, sizeof(*node)); + + node->color = IB_RBT_BLACK; + node->parent = node->left = node->right = tree->nil; + + tree->compare = compare; + + return(tree); +} + +/****************************************************************//** +Generic insert of a value in the rb tree. +@return inserted node */ +UNIV_INTERN +const ib_rbt_node_t* +rbt_insert( +/*=======*/ + ib_rbt_t* tree, /*!< in: rb tree */ + const void* key, /*!< in: key for ordering */ + const void* value) /*!< in: value of key, this value + is copied to the node */ +{ + ib_rbt_node_t* node; + + /* Create the node that will hold the value data. */ + node = (ib_rbt_node_t*) ut_malloc(SIZEOF_NODE(tree)); + + memcpy(node->value, value, tree->sizeof_value); + node->parent = node->left = node->right = tree->nil; + + /* Insert in the tree in the usual way. */ + rbt_tree_insert(tree, key, node); + rbt_balance_tree(tree, node); + + ++tree->n_nodes; + + return(node); +} + +/****************************************************************//** +Add a new node to the tree, useful for data that is pre-sorted. +@return appended node */ +UNIV_INTERN +const ib_rbt_node_t* +rbt_add_node( +/*=========*/ + ib_rbt_t* tree, /*!< in: rb tree */ + ib_rbt_bound_t* parent, /*!< in: bounds */ + const void* value) /*!< in: this value is copied + to the node */ +{ + ib_rbt_node_t* node; + + /* Create the node that will hold the value data */ + node = (ib_rbt_node_t*) ut_malloc(SIZEOF_NODE(tree)); + + memcpy(node->value, value, tree->sizeof_value); + node->parent = node->left = node->right = tree->nil; + + /* If tree is empty */ + if (parent->last == NULL) { + parent->last = tree->root; + } + + /* Append the node, the hope here is that the caller knows + what s/he is doing. */ + rbt_tree_add_child(tree, parent, node); + rbt_balance_tree(tree, node); + + ++tree->n_nodes; + +#if defined(IB_RBT_TESTING) + ut_a(rbt_validate(tree)); +#endif + return(node); +} + +/****************************************************************//** +Find a matching node in the rb tree. +@return NULL if not found else the node where key was found */ +UNIV_INTERN +const ib_rbt_node_t* +rbt_lookup( +/*=======*/ + const ib_rbt_t* tree, /*!< in: rb tree */ + const void* key) /*!< in: key to use for search */ +{ + const ib_rbt_node_t* current = ROOT(tree); + + /* Regular binary search. */ + while (current != tree->nil) { + int result = tree->compare(key, current->value); + + if (result < 0) { + current = current->left; + } else if (result > 0) { + current = current->right; + } else { + break; + } + } + + return(current != tree->nil ? current : NULL); +} + +/****************************************************************//** +Delete a node from the red black tree, identified by key. +@return TRUE if success FALSE if not found */ +UNIV_INTERN +ibool +rbt_delete( +/*=======*/ + ib_rbt_t* tree, /*!< in: rb tree */ + const void* key) /*!< in: key to delete */ +{ + ibool deleted = FALSE; + ib_rbt_node_t* node = (ib_rbt_node_t*) rbt_lookup(tree, key); + + if (node) { + rbt_remove_node_and_rebalance(tree, node); + + ut_free(node); + deleted = TRUE; + } + + return(deleted); +} + +/****************************************************************//** +Remove a node from the rb tree, the node is not free'd, that is the +callers responsibility. +@return deleted node but without the const */ +UNIV_INTERN +ib_rbt_node_t* +rbt_remove_node( +/*============*/ + ib_rbt_t* tree, /*!< in: rb tree */ + const ib_rbt_node_t* const_node) /*!< in: node to delete, this + is a fudge and declared const + because the caller can access + only const nodes */ +{ + /* Cast away the const. */ + rbt_remove_node_and_rebalance(tree, (ib_rbt_node_t*) const_node); + + /* This is to make it easier to do something like this: + ut_free(rbt_remove_node(node)); + */ + + return((ib_rbt_node_t*) const_node); +} + +/****************************************************************//** +Find the node that has the lowest key that is >= key. +@return node satisfying the lower bound constraint or NULL */ +UNIV_INTERN +const ib_rbt_node_t* +rbt_lower_bound( +/*============*/ + const ib_rbt_t* tree, /*!< in: rb tree */ + const void* key) /*!< in: key to search */ +{ + ib_rbt_node_t* lb_node = NULL; + ib_rbt_node_t* current = ROOT(tree); + + while (current != tree->nil) { + int result = tree->compare(key, current->value); + + if (result > 0) { + + current = current->right; + + } else if (result < 0) { + + lb_node = current; + current = current->left; + + } else { + lb_node = current; + break; + } + } + + return(lb_node); +} + +/****************************************************************//** +Find the node that has the greatest key that is <= key. +@return node satisfying the upper bound constraint or NULL */ +UNIV_INTERN +const ib_rbt_node_t* +rbt_upper_bound( +/*============*/ + const ib_rbt_t* tree, /*!< in: rb tree */ + const void* key) /*!< in: key to search */ +{ + ib_rbt_node_t* ub_node = NULL; + ib_rbt_node_t* current = ROOT(tree); + + while (current != tree->nil) { + int result = tree->compare(key, current->value); + + if (result > 0) { + + ub_node = current; + current = current->right; + + } else if (result < 0) { + + current = current->left; + + } else { + ub_node = current; + break; + } + } + + return(ub_node); +} + +/****************************************************************//** +Find the node that has the greatest key that is <= key. +@return value of result */ +UNIV_INTERN +int +rbt_search( +/*=======*/ + const ib_rbt_t* tree, /*!< in: rb tree */ + ib_rbt_bound_t* parent, /*!< in: search bounds */ + const void* key) /*!< in: key to search */ +{ + ib_rbt_node_t* current = ROOT(tree); + + /* Every thing is greater than the NULL root. */ + parent->result = 1; + parent->last = NULL; + + while (current != tree->nil) { + + parent->last = current; + parent->result = tree->compare(key, current->value); + + if (parent->result > 0) { + current = current->right; + } else if (parent->result < 0) { + current = current->left; + } else { + break; + } + } + + return(parent->result); +} + +/****************************************************************//** +Find the node that has the greatest key that is <= key. But use the +supplied comparison function. +@return value of result */ +UNIV_INTERN +int +rbt_search_cmp( +/*===========*/ + const ib_rbt_t* tree, /*!< in: rb tree */ + ib_rbt_bound_t* parent, /*!< in: search bounds */ + const void* key, /*!< in: key to search */ + ib_rbt_compare compare) /*!< in: fn to compare items */ +{ + ib_rbt_node_t* current = ROOT(tree); + + /* Every thing is greater than the NULL root. */ + parent->result = 1; + parent->last = NULL; + + while (current != tree->nil) { + + parent->last = current; + parent->result = compare(key, current->value); + + if (parent->result > 0) { + current = current->right; + } else if (parent->result < 0) { + current = current->left; + } else { + break; + } + } + + return(parent->result); +} + +/****************************************************************//** +Get the leftmost node. +Return the left most node in the tree. */ +UNIV_INTERN +const ib_rbt_node_t* +rbt_first( +/*======*/ + const ib_rbt_t* tree) /* in: rb tree */ +{ + ib_rbt_node_t* first = NULL; + ib_rbt_node_t* current = ROOT(tree); + + while (current != tree->nil) { + first = current; + current = current->left; + } + + return(first); +} + +/****************************************************************//** +Return the right most node in the tree. +@return the rightmost node or NULL */ +UNIV_INTERN +const ib_rbt_node_t* +rbt_last( +/*=====*/ + const ib_rbt_t* tree) /*!< in: rb tree */ +{ + ib_rbt_node_t* last = NULL; + ib_rbt_node_t* current = ROOT(tree); + + while (current != tree->nil) { + last = current; + current = current->right; + } + + return(last); +} + +/****************************************************************//** +Return the next node. +@return node next from current */ +UNIV_INTERN +const ib_rbt_node_t* +rbt_next( +/*=====*/ + const ib_rbt_t* tree, /*!< in: rb tree */ + const ib_rbt_node_t* current)/*!< in: current node */ +{ + return(current ? rbt_find_successor(tree, current) : NULL); +} + +/****************************************************************//** +Return the previous node. +@return node prev from current */ +UNIV_INTERN +const ib_rbt_node_t* +rbt_prev( +/*=====*/ + const ib_rbt_t* tree, /*!< in: rb tree */ + const ib_rbt_node_t* current)/*!< in: current node */ +{ + return(current ? rbt_find_predecessor(tree, current) : NULL); +} + +/****************************************************************//** +Reset the tree. Delete all the nodes. */ +UNIV_INTERN +void +rbt_clear( +/*======*/ + ib_rbt_t* tree) /*!< in: rb tree */ +{ + rbt_free_node(ROOT(tree), tree->nil); + + tree->n_nodes = 0; + tree->root->left = tree->root->right = tree->nil; +} + +/****************************************************************//** +Merge the node from dst into src. Return the number of nodes merged. +@return no. of recs merged */ +UNIV_INTERN +ulint +rbt_merge_uniq( +/*===========*/ + ib_rbt_t* dst, /*!< in: dst rb tree */ + const ib_rbt_t* src) /*!< in: src rb tree */ +{ + ib_rbt_bound_t parent; + ulint n_merged = 0; + const ib_rbt_node_t* src_node = rbt_first(src); + + if (rbt_empty(src) || dst == src) { + return(0); + } + + for (/* No op */; src_node; src_node = rbt_next(src, src_node)) { + + if (rbt_search(dst, &parent, src_node->value) != 0) { + rbt_add_node(dst, &parent, src_node->value); + ++n_merged; + } + } + + return(n_merged); +} + +/****************************************************************//** +Merge the node from dst into src. Return the number of nodes merged. +Delete the nodes from src after copying node to dst. As a side effect +the duplicates will be left untouched in the src. +@return no. of recs merged */ +UNIV_INTERN +ulint +rbt_merge_uniq_destructive( +/*=======================*/ + ib_rbt_t* dst, /*!< in: dst rb tree */ + ib_rbt_t* src) /*!< in: src rb tree */ +{ + ib_rbt_bound_t parent; + ib_rbt_node_t* src_node; + ulint old_size = rbt_size(dst); + + if (rbt_empty(src) || dst == src) { + return(0); + } + + for (src_node = (ib_rbt_node_t*) rbt_first(src); src_node; /* */) { + ib_rbt_node_t* prev = src_node; + + src_node = (ib_rbt_node_t*)rbt_next(src, prev); + + /* Skip duplicates. */ + if (rbt_search(dst, &parent, prev->value) != 0) { + + /* Remove and reset the node but preserve + the node (data) value. */ + rbt_remove_node_and_rebalance(src, prev); + + /* The nil should be taken from the dst tree. */ + prev->parent = prev->left = prev->right = dst->nil; + rbt_tree_add_child(dst, &parent, prev); + rbt_balance_tree(dst, prev); + + ++dst->n_nodes; + } + } + +#if defined(IB_RBT_TESTING) + ut_a(rbt_validate(dst)); + ut_a(rbt_validate(src)); +#endif + return(rbt_size(dst) - old_size); +} + +/****************************************************************//** +Check that every path from the root to the leaves has the same count and +the tree nodes are in order. +@return TRUE if OK FALSE otherwise */ +UNIV_INTERN +ibool +rbt_validate( +/*=========*/ + const ib_rbt_t* tree) /*!< in: RB tree to validate */ +{ + if (rbt_count_black_nodes(tree, ROOT(tree)) > 0) { + return(rbt_check_ordering(tree)); + } + + return(FALSE); +} + +/****************************************************************//** +Iterate over the tree in depth first order. */ +UNIV_INTERN +void +rbt_print( +/*======*/ + const ib_rbt_t* tree, /*!< in: tree to traverse */ + ib_rbt_print_node print) /*!< in: print function */ +{ + rbt_print_subtree(tree, ROOT(tree), print); +} |