summaryrefslogtreecommitdiff
path: root/ace/RB_Tree.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'ace/RB_Tree.cpp')
-rw-r--r--ace/RB_Tree.cpp463
1 files changed, 275 insertions, 188 deletions
diff --git a/ace/RB_Tree.cpp b/ace/RB_Tree.cpp
index 3e03de0d05f..642638e33b4 100644
--- a/ace/RB_Tree.cpp
+++ b/ace/RB_Tree.cpp
@@ -13,12 +13,15 @@
ACE_RCSID(ace, RB_Tree, "$Id$")
-/////////////////////////////////////////
-// template class RB_Tree_Node<KEY, T> //
-/////////////////////////////////////////
+/////////////////////////////////////////////
+// template class ACE_RB_Tree_Node<KEY, T> //
+/////////////////////////////////////////////
+
+
+// Constructor.
template <class KEY, class T>
-RB_Tree_Node<KEY, T>::RB_Tree_Node (const KEY &k, const T &t)
+ACE_RB_Tree_Node<KEY, T>::ACE_RB_Tree_Node (const KEY &k, const T &t)
: k_ (k)
, t_ (t)
, color_ (RED)
@@ -27,222 +30,286 @@ RB_Tree_Node<KEY, T>::RB_Tree_Node (const KEY &k, const T &t)
, right_ (0)
{
}
- // constructor
+
+
+// Destructor.
template <class KEY, class T>
-RB_Tree_Node<KEY, T>::~RB_Tree_Node ()
+ACE_RB_Tree_Node<KEY, T>::~ACE_RB_Tree_Node ()
{
- // delete left sub-tree
+ // Delete left sub-tree.
delete left_;
- // delete right sub_tree
+ // Delete right sub_tree.
delete right_;
}
- // destructor
-////////////////////////////////////
-// template class RB_Tree<KEY, T> //
-////////////////////////////////////
+////////////////////////////////////////
+// template class ACE_RB_Tree<KEY, T> //
+////////////////////////////////////////
+
+// Constructor.
template <class KEY, class T>
-RB_Tree<KEY, T>::RB_Tree ()
- : root_ (0)
+ACE_RB_Tree<KEY, T>::ACE_RB_Tree (
+ ACE_Const_Binary_Functor_Base<KEY, KEY> *less_than_functor,
+ int free_functor)
+ : root_ (0),
+ less_than_functor_ (less_than_functor),
+ free_functor_ (free_functor)
{
+ if (less_than_functor_ == 0)
+ {
+ less_than_functor_ = new ACE_Less_Than_Functor<KEY, KEY>;
+ free_functor_ = 1;
+ }
}
- // constructor
+
+
+// Copy constructor.
template <class KEY, class T>
-RB_Tree<KEY, T>::RB_Tree (const RB_Tree<KEY, T> &rbt)
+ACE_RB_Tree<KEY, T>::ACE_RB_Tree (const ACE_RB_Tree<KEY, T> &rbt)
: root_ (0)
{
- // make a deep copy of the passed tree
- RB_Tree_Iterator<KEY, T> iter(rbt);
+ // Make a copy of the comparison functor.
+ less_than_functor_ = (rbt.less_than_functor_ == 0)
+ ? 0 : rbt.less_than_functor_->clone ();
+ free_functor_ = 1;
+
+ // Make a deep copy of the passed tree.
+ ACE_RB_Tree_Iterator<KEY, T> iter(rbt);
for (iter.first (); iter.is_done () == 0; iter.next ())
{
insert (*(iter.key ()), *(iter.item ()));
}
}
- // copy constructor
+
+
+// Destructor.
template <class KEY, class T>
-RB_Tree<KEY, T>::~RB_Tree ()
+ACE_RB_Tree<KEY, T>::~ACE_RB_Tree ()
{
- // clear away all nodes in the tree
+ // Free the comparison functor if needed.
+ if (free_functor_)
+ {
+ delete less_than_functor_;
+ }
+
+ // Clear away all nodes in the tree.
clear ();
}
- // destructor
+
+
+// Assignment operator.
template <class KEY, class T> void
-RB_Tree<KEY, T>::operator = (const RB_Tree<KEY, T> &rbt)
+ACE_RB_Tree<KEY, T>::operator = (const ACE_RB_Tree<KEY, T> &rbt)
{
- // clear out the existing tree
+ // Free the comparison functor if needed.
+ if (free_functor_)
+ {
+ delete less_than_functor_;
+ }
+
+ // Make a copy of the passed tree's comparison functor.
+ less_than_functor_ = (rbt.less_than_functor_ == 0)
+ ? 0 : rbt.less_than_functor_->clone ();
+ free_functor_ = 1;
+
+ // Clear out the existing tree.
clear ();
- // make a deep copy of the passed tree
- RB_Tree_Iterator<KEY, T> iter(rbt);
+ // Make a deep copy of the passed tree.
+ ACE_RB_Tree_Iterator<KEY, T> iter(rbt);
for (iter.first (); iter.is_done () == 0; iter.next ())
{
insert (*(iter.key ()), *(iter.item ()));
}
}
- // assignment operator
+
+// Less than comparison function for keys, default
+// functor implementation returns 1 if k1 < k2, 0 otherwise.
template <class KEY, class T> int
-RB_Tree<KEY, T>::lessthan (const KEY &k1, const KEY &k2)
+ACE_RB_Tree<KEY, T>::lessthan (const KEY &k1, const KEY &k2)
{
- return k1 < k2;
+ if (less_than_functor_ == 0)
+ {
+ ACE_ERROR_RETURN ((LM_ERROR, ASYS_TEXT ("%p\n"),
+ ASYS_TEXT ("\nNull comparison functor pointer.\n")),
+ 0);
+ }
+ else
+ {
+ return less_than_functor_->execute (k1, k2);
+ }
}
- // lessthan comparison function for keys.
- // returns 1 if k1 < k2, 0 otherwise
+
+
+// Returns a pointer to the item corresponding to the
+// given key, or 0 if it cannot find the key in the tree.
template <class KEY, class T> T*
-RB_Tree<KEY, T>::find (const KEY &k)
+ACE_RB_Tree<KEY, T>::find (const KEY &k)
{
- // find the closest matching node, if there is one
- RB_Tree_Node<KEY, T> *current = find_node (k);
+ // Find the closest matching node, if there is one.
+ ACE_RB_Tree_Node<KEY, T> *current = find_node (k);
if (current)
{
- // if a nearest matching node was returned
+ // If a nearest matching node was returned.
if (this->lessthan (current->key (), k)
|| this->lessthan (k, current->key ()))
{
- // if the keys differ, there is no match: return 0
+ // If the keys differ, there is no match: return 0.
return 0;
}
else
{
- // else, the keys match: return a pointer to the node's item
+ // The keys match: return a pointer to the node's item.
return &(current->item ());
}
}
else
{
- // else, the tree is empty: return 0
+ // The tree is empty: return 0.
return 0;
}
}
- // Returns a pointer to the item corresponding to the
- // given key, or 0 if it cannot find the key in the tree.
+
+
+
+// Inserts a *copy* of the key and the item into the tree:
+// both the key type KEY and the item type T must have well
+// defined semantics for copy construction and < comparison.
+// This method returns a pointer to the inserted item copy,
+// or 0 if an error occurred. NOTE: if an identical key
+// already exists in the tree, no new item is created, and
+// the returned pointer addresses the existing item
+// associated with the existing key.
template <class KEY, class T> T*
-RB_Tree<KEY, T>::insert (const KEY &k, const T &t)
+ACE_RB_Tree<KEY, T>::insert (const KEY &k, const T &t)
{
- // find the closest matching node, if there is one
- RB_Tree_Node<KEY, T> *current = find_node (k);
+ // Find the closest matching node, if there is one.
+ ACE_RB_Tree_Node<KEY, T> *current = find_node (k);
if (current)
{
if (this->lessthan (current->key (), k))
{
- // if a nearest matching node has a key less than the insertion key
+ // If a nearest matching node has a key less than the insertion key.
if (current->right ())
{
- // if there is already a right subtree, complain
+ // If there is already a right subtree, complain.
ACE_ERROR_RETURN ((LM_ERROR, ASYS_TEXT ("%p\n"),
ASYS_TEXT ("\nright subtree already present in "
- "RB_Tree<KEY, T>::insert\n")), 0);
+ "ACE_RB_Tree<KEY, T>::insert\n")), 0);
}
else
{
- // else, the right subtree is empty: insert new node there
- current->right (new RB_Tree_Node<KEY, T> (k, t));
+ // The right subtree is empty: insert new node there.
+ current->right (new ACE_RB_Tree_Node<KEY, T> (k, t));
if (current->right ())
{
- // if the node was successfully inserted, set its parent, rebalance the
- // tree, color the root black, and return a pointer to the inserted item
+ // If the node was successfully inserted, set its parent, rebalance
+ // the tree, color the root black, and return a pointer to the
+ // inserted item.
T *item = &(current->right ()->item ());
current->right ()->parent (current);
RB_rebalance (current->right ());
- root_->color (RB_Tree_Node_Base::BLACK);
+ root_->color (ACE_RB_Tree_Node_Base::BLACK);
return item;
}
else
{
- // else, memory allocation failed
+ // Memory allocation failed.
ACE_ERROR_RETURN ((LM_ERROR, ASYS_TEXT ("%p\n"),
ASYS_TEXT ("\nmemory allocation to current->right_ failed "
- "in RB_Tree<KEY, T>::insert\n")), 0);
+ "in ACE_RB_Tree<KEY, T>::insert\n")), 0);
}
}
}
else if (this->lessthan (k, current->key ()))
{
- // if a nearest matching node has a key greater than the insertion key
+ // If a nearest matching node has a key greater than the insertion key.
if (current->left ())
{
- // if there is already a left subtree, complain
+ // If there is already a left subtree, complain.
ACE_ERROR_RETURN ((LM_ERROR, ASYS_TEXT ("%p\n"),
ASYS_TEXT ("\nleft subtree already present in "
- "RB_Tree<KEY, T>::insert\n")), 0);
+ "ACE_RB_Tree<KEY, T>::insert\n")), 0);
}
else
{
- // else, the right subtree is empty: insert new node there
- current->left (new RB_Tree_Node<KEY, T> (k, t));
+ // The right subtree is empty: insert new node there.
+ current->left (new ACE_RB_Tree_Node<KEY, T> (k, t));
if (current->left ())
{
- // if the node was successfully inserted, set its parent, rebalance the
- // tree, color the root black, and return a pointer to the inserted item
+ // If the node was successfully inserted, set its parent, rebalance
+ // the tree, color the root black, and return a pointer to the
+ // inserted item.
T *item = &(current->left ()->item ());
current->left ()->parent (current);
RB_rebalance (current->left ());
- root_->color (RB_Tree_Node_Base::BLACK);
+ root_->color (ACE_RB_Tree_Node_Base::BLACK);
return item;
}
else
{
- // else, memory allocation failed
+ // Memory allocation failed.
ACE_ERROR_RETURN ((LM_ERROR, ASYS_TEXT ("%p\n"),
ASYS_TEXT ("\nmemory allocation to current->left_ failed in "
- "RB_Tree<KEY, T>::insert\n")), 0);
+ "ACE_RB_Tree<KEY, T>::insert\n")), 0);
}
}
}
else
{
- // else, the keys match: return a pointer to the node's item
+ // The keys match: return a pointer to the node's item.
return &(current->item ());
}
}
else
{
- // else, the tree is empty: insert at the root and color the root black
- root_ = new RB_Tree_Node<KEY, T> (k, t);
+ // The tree is empty: insert at the root and color the root black.
+ root_ = new ACE_RB_Tree_Node<KEY, T> (k, t);
if (root_)
{
- root_->color (RB_Tree_Node_Base::BLACK);
+ root_->color (ACE_RB_Tree_Node_Base::BLACK);
return &(root_->item ());
}
else
{
ACE_ERROR_RETURN ((LM_ERROR, ASYS_TEXT ("%p\n"),
ASYS_TEXT ("\nmemory allocation to root_ failed in "
- "RB_Tree<KEY, T>::insert\n")), 0);
+ "ACE_RB_Tree<KEY, T>::insert\n")), 0);
}
}
}
- // Inserts a *copy* of the key and the item into the tree:
- // both the key type KEY and the item type T must have well
- // defined semantics for copy construction and < comparison.
- // This method returns a pointer to the inserted item copy,
- // or 0 if an error occurred. NOTE: if an identical key
- // already exists in the tree, no new item is created, and
- // the returned pointer addresses the existing item
- // associated with the existing key.
+
+
+// Removes the item associated with the given key from the
+// tree and destroys it. Returns 1 if it found the item
+// and successfully destroyed it, 0 if it did not find the
+// item, or -1 if an error occurred.
template <class KEY, class T> int
-RB_Tree<KEY, T>::remove (const KEY &k)
+ACE_RB_Tree<KEY, T>::remove (const KEY &k)
{
- // find a matching node, if there is one
- RB_Tree_Node<KEY, T> *x, *z = find_node (k);
+ // Find a matching node, if there is one.
+ ACE_RB_Tree_Node<KEY, T> *x, *z;
+
+ z = find_node (k);
if ((z) && (! this->lessthan (z->key (), k))
&& (! this->lessthan (k, z->key ())))
{
- // there is a matching node: remove and destroy it
- RB_Tree_Node<KEY, T> *y;
+ // There is a matching node: remove and destroy it.
+ ACE_RB_Tree_Node<KEY, T> *y;
if ((z->left ()) && (z->right ()))
{
y = RB_tree_successor (z);
@@ -259,7 +326,10 @@ RB_Tree<KEY, T>::remove (const KEY &k)
{
x = y->right ();
}
- x->parent (y->parent ());
+ if (x)
+ {
+ x->parent (y->parent ());
+ }
if (y->parent ())
{
if (y == y->parent ()->left ())
@@ -277,11 +347,11 @@ RB_Tree<KEY, T>::remove (const KEY &k)
}
if (y != z)
{
- // copy the elements of y into z
+ // Copy the elements of y into z.
z->key () = y->key ();
z->item () = y->item ();
}
- if (y->color () == RB_Tree_Node_Base::BLACK)
+ if (y->color () == ACE_RB_Tree_Node_Base::BLACK)
{
RB_delete_fixup (x);
}
@@ -293,34 +363,32 @@ RB_Tree<KEY, T>::remove (const KEY &k)
}
else
{
- // else, no matching node was found: return 0
+ // No matching node was found: return 0.
return 0;
}
}
- // removes the item associated with the given key from the
- // tree and destroys it. Returns 1 if it found the item
- // and successfully destroyed it, 0 if it did not find the
- // item, or -1 if an error occurred.
+// Method for right rotation of the tree about a given node.
+
template <class KEY, class T> void
-RB_Tree<KEY, T>::RB_rotate_right (RB_Tree_Node<KEY, T> * x)
+ACE_RB_Tree<KEY, T>::RB_rotate_right (ACE_RB_Tree_Node<KEY, T> * x)
{
if (! x)
{
ACE_ERROR ((LM_ERROR, ASYS_TEXT ("%p\n"),
ASYS_TEXT ("\nerror: x is a null pointer in "
- "RB_Tree<KEY, T>::RB_rotate_right\n")));
+ "ACE_RB_Tree<KEY, T>::RB_rotate_right\n")));
}
else if (! (x->left()))
{
ACE_ERROR ((LM_ERROR, ASYS_TEXT ("%p\n"),
ASYS_TEXT ("\nerror: x->left () is a null pointer in "
- "RB_Tree<KEY, T>::RB_rotate_right\n")));
+ "ACE_RB_Tree<KEY, T>::RB_rotate_right\n")));
}
else
{
- RB_Tree_Node<KEY, T> * y;
+ ACE_RB_Tree_Node<KEY, T> * y;
y = x->left ();
x->left (y->right ());
if (y->right ())
@@ -347,27 +415,28 @@ RB_Tree<KEY, T>::RB_rotate_right (RB_Tree_Node<KEY, T> * x)
x->parent (y);
}
}
- // method for right rotation of the tree about a given node
+// Method for left rotation of the tree about a given node.
+
template <class KEY, class T> void
-RB_Tree<KEY, T>::RB_rotate_left (RB_Tree_Node<KEY, T> * x)
+ACE_RB_Tree<KEY, T>::RB_rotate_left (ACE_RB_Tree_Node<KEY, T> * x)
{
if (! x)
{
ACE_ERROR ((LM_ERROR, ASYS_TEXT ("%p\n"),
ASYS_TEXT ("\nerror: x is a null pointer in "
- "RB_Tree<KEY, T>::RB_rotate_left\n")));
+ "ACE_RB_Tree<KEY, T>::RB_rotate_left\n")));
}
else if (! (x->right()))
{
ACE_ERROR ((LM_ERROR, ASYS_TEXT ("%p\n"),
ASYS_TEXT ("\nerror: x->right () is a null pointer "
- "in RB_Tree<KEY, T>::RB_rotate_left\n")));
+ "in ACE_RB_Tree<KEY, T>::RB_rotate_left\n")));
}
else
{
- RB_Tree_Node<KEY, T> * y;
+ ACE_RB_Tree_Node<KEY, T> * y;
y = x->right ();
x->right (y->left ());
if (y->left ())
@@ -394,73 +463,75 @@ RB_Tree<KEY, T>::RB_rotate_left (RB_Tree_Node<KEY, T> * x)
x->parent (y);
}
}
- // method for left rotation of the tree about a given node
+
+
+// Method for restoring Red-Black properties after deletion.
template <class KEY, class T> void
-RB_Tree<KEY, T>::RB_delete_fixup (RB_Tree_Node<KEY, T> * x)
+ACE_RB_Tree<KEY, T>::RB_delete_fixup (ACE_RB_Tree_Node<KEY, T> * x)
{
- while ((x) && (x->parent ()) && (x->color () == RB_Tree_Node_Base::BLACK))
+ while ((x) && (x->parent ()) && (x->color () == ACE_RB_Tree_Node_Base::BLACK))
{
if (x == x->parent ()->left ())
{
- RB_Tree_Node<KEY, T> *w = x->parent ()->right ();
- if (w->color () == RB_Tree_Node_Base::RED)
+ ACE_RB_Tree_Node<KEY, T> *w = x->parent ()->right ();
+ if (w->color () == ACE_RB_Tree_Node_Base::RED)
{
- w->color (RB_Tree_Node_Base::BLACK);
- x->parent ()->color (RB_Tree_Node_Base::RED);
+ w->color (ACE_RB_Tree_Node_Base::BLACK);
+ x->parent ()->color (ACE_RB_Tree_Node_Base::RED);
RB_rotate_left (x->parent ());
w = x->parent ()->right ();
}
- if ((w->left ()->color () == RB_Tree_Node_Base::BLACK) &&
- (w->right ()->color () == RB_Tree_Node_Base::BLACK))
+ if ((w->left ()->color () == ACE_RB_Tree_Node_Base::BLACK) &&
+ (w->right ()->color () == ACE_RB_Tree_Node_Base::BLACK))
{
- w->color (RB_Tree_Node_Base::RED);
+ w->color (ACE_RB_Tree_Node_Base::RED);
x = x->parent ();
}
else
{
- if (w->right ()->color () == RB_Tree_Node_Base::BLACK)
+ if (w->right ()->color () == ACE_RB_Tree_Node_Base::BLACK)
{
- w->left ()->color (RB_Tree_Node_Base::BLACK);
- w->color (RB_Tree_Node_Base::RED);
+ w->left ()->color (ACE_RB_Tree_Node_Base::BLACK);
+ w->color (ACE_RB_Tree_Node_Base::RED);
RB_rotate_right (w);
w = x->parent ()->right ();
}
w->color (x->parent ()->color ());
- x->parent ()->color (RB_Tree_Node_Base::BLACK);
- w->right ()->color (RB_Tree_Node_Base::BLACK);
+ x->parent ()->color (ACE_RB_Tree_Node_Base::BLACK);
+ w->right ()->color (ACE_RB_Tree_Node_Base::BLACK);
RB_rotate_left (x->parent ());
x = root_;
}
}
else
{
- RB_Tree_Node<KEY, T> *w = x->parent ()->left ();
- if (w->color () == RB_Tree_Node_Base::RED)
+ ACE_RB_Tree_Node<KEY, T> *w = x->parent ()->left ();
+ if (w->color () == ACE_RB_Tree_Node_Base::RED)
{
- w->color (RB_Tree_Node_Base::BLACK);
- x->parent ()->color (RB_Tree_Node_Base::RED);
+ w->color (ACE_RB_Tree_Node_Base::BLACK);
+ x->parent ()->color (ACE_RB_Tree_Node_Base::RED);
RB_rotate_right (x->parent ());
w = x->parent ()->left ();
}
- if ((w->left ()->color () == RB_Tree_Node_Base::BLACK) &&
- (w->right ()->color () == RB_Tree_Node_Base::BLACK))
+ if ((w->left ()->color () == ACE_RB_Tree_Node_Base::BLACK) &&
+ (w->right ()->color () == ACE_RB_Tree_Node_Base::BLACK))
{
- w->color (RB_Tree_Node_Base::RED);
+ w->color (ACE_RB_Tree_Node_Base::RED);
x = x->parent ();
}
else
{
- if (w->left ()->color () == RB_Tree_Node_Base::BLACK)
+ if (w->left ()->color () == ACE_RB_Tree_Node_Base::BLACK)
{
- w->right ()->color (RB_Tree_Node_Base::BLACK);
- w->color (RB_Tree_Node_Base::RED);
+ w->right ()->color (ACE_RB_Tree_Node_Base::BLACK);
+ w->color (ACE_RB_Tree_Node_Base::RED);
RB_rotate_left (w);
w = x->parent ()->left ();
}
w->color (x->parent ()->color ());
- x->parent ()->color (RB_Tree_Node_Base::BLACK);
- w->left ()->color (RB_Tree_Node_Base::BLACK);
+ x->parent ()->color (ACE_RB_Tree_Node_Base::BLACK);
+ w->left ()->color (ACE_RB_Tree_Node_Base::BLACK);
RB_rotate_right (x->parent ());
x = root_;
}
@@ -469,143 +540,150 @@ RB_Tree<KEY, T>::RB_delete_fixup (RB_Tree_Node<KEY, T> * x)
if (x)
{
- x->color (RB_Tree_Node_Base::BLACK);
+ x->color (ACE_RB_Tree_Node_Base::BLACK);
}
}
- // method for restoring Red-Black properties after deletion
-template <class KEY, class T> RB_Tree_Node<KEY, T> *
-RB_Tree<KEY, T>::find_node (const KEY &k)
+
+
+// Return a pointer to a matching node if there is one,
+// a pointer to the node under which to insert the item
+// if the tree is not empty and there is no such match,
+// or 0 if the tree is empty.
+
+template <class KEY, class T> ACE_RB_Tree_Node<KEY, T> *
+ACE_RB_Tree<KEY, T>::find_node (const KEY &k)
{
- RB_Tree_Node<KEY, T> *current = root_;
+ ACE_RB_Tree_Node<KEY, T> *current = root_;
while (current)
{
- // while there are more nodes to examine
+ // While there are more nodes to examine.
if (this->lessthan (current->key (), k))
{
- // if the search key is greater than the current node's key
+ // If the search key is greater than the current node's key.
if (current->right ())
{
- // if the right subtree is not empty, search to the right
+ // If the right subtree is not empty, search to the right.
current = current->right ();
}
else
{
- // if the right subtree is empty, we're done
+ // If the right subtree is empty, we're done.
break;
}
}
else if (this->lessthan (k, current->key ()))
{
- // else if the search key is less than the current node's key
+ // Else if the search key is less than the current node's key.
if (current->left ())
{
- // if the left subtree is not empty, search to the left
+ // If the left subtree is not empty, search to the left.
current = current->left ();
}
else
{
- // if the left subtree is empty, we're done
+ // If the left subtree is empty, we're done.
break;
}
}
else
{
- // if the keys match, we're done
+ // If the keys match, we're done.
break;
}
}
return current;
}
- // returns a pointer to a matching node if there is one,
- // a pointer to the node under which to insert the item
- // if the tree is not empty and there is no such match,
- // or 0 if the tree is empty.
+
+
+// Rebalance the tree after insertion of a node.
template <class KEY, class T> void
-RB_Tree<KEY, T>::RB_rebalance (RB_Tree_Node<KEY, T> * x)
+ACE_RB_Tree<KEY, T>::RB_rebalance (ACE_RB_Tree_Node<KEY, T> * x)
{
- RB_Tree_Node<KEY, T> *y = 0;
+ ACE_RB_Tree_Node<KEY, T> *y = 0;
while ((x) && (x->parent ())
- && (x->parent ()->color () == RB_Tree_Node_Base::RED))
+ && (x->parent ()->color () == ACE_RB_Tree_Node_Base::RED))
{
if (! x->parent ()->parent ())
{
- // if we got here, something is drastically wrong!
+ // If we got here, something is drastically wrong!
ACE_ERROR ((LM_ERROR, ASYS_TEXT ("%p\n"),
ASYS_TEXT ("\nerror: parent's parent is null in "
- "RB_Tree<KEY, T>::RB_rebalance\n")));
+ "ACE_RB_Tree<KEY, T>::RB_rebalance\n")));
return;
}
if (x->parent () == x->parent ()->parent ()->left ())
{
y = x->parent ()->parent ()->right ();
- if (y && (y->color () == RB_Tree_Node_Base::RED))
+ if (y && (y->color () == ACE_RB_Tree_Node_Base::RED))
{
- // handle case 1 (see CLR book, pp. 269)
- x->parent ()->color (RB_Tree_Node_Base::BLACK);
- y->color (RB_Tree_Node_Base::BLACK);
- x->parent ()->parent ()->color (RB_Tree_Node_Base::RED);
+ // Handle case 1 (see CLR book, pp. 269).
+ x->parent ()->color (ACE_RB_Tree_Node_Base::BLACK);
+ y->color (ACE_RB_Tree_Node_Base::BLACK);
+ x->parent ()->parent ()->color (ACE_RB_Tree_Node_Base::RED);
x = x->parent ()->parent ();
}
else
{
if (x == x->parent ()->right ())
{
- // transform case 2 into case 3 (see CLR book, pp. 269)
+ // Transform case 2 into case 3 (see CLR book, pp. 269).
x = x->parent ();
RB_rotate_left (x);
}
- // handle case 3 (see CLR book, pp. 269)
- x->parent ()->color (RB_Tree_Node_Base::BLACK);
- x->parent ()->parent ()->color (RB_Tree_Node_Base::RED);
+ // Handle case 3 (see CLR book, pp. 269).
+ x->parent ()->color (ACE_RB_Tree_Node_Base::BLACK);
+ x->parent ()->parent ()->color (ACE_RB_Tree_Node_Base::RED);
RB_rotate_right (x->parent ()->parent ());
}
}
else
{
y = x->parent ()->parent ()->left ();
- if (y && (y->color () == RB_Tree_Node_Base::RED))
+ if (y && (y->color () == ACE_RB_Tree_Node_Base::RED))
{
- // handle case 1 (see CLR book, pp. 269)
- x->parent ()->color (RB_Tree_Node_Base::BLACK);
- y->color (RB_Tree_Node_Base::BLACK);
- x->parent ()->parent ()->color (RB_Tree_Node_Base::RED);
+ // Handle case 1 (see CLR book, pp. 269).
+ x->parent ()->color (ACE_RB_Tree_Node_Base::BLACK);
+ y->color (ACE_RB_Tree_Node_Base::BLACK);
+ x->parent ()->parent ()->color (ACE_RB_Tree_Node_Base::RED);
x = x->parent ()->parent ();
}
else
{
if (x == x->parent ()->left ())
{
- // transform case 2 into case 3 (see CLR book, pp. 269)
+ // Transform case 2 into case 3 (see CLR book, pp. 269).
x = x->parent ();
RB_rotate_right (x);
}
- // handle case 3 (see CLR book, pp. 269)
- x->parent ()->color (RB_Tree_Node_Base::BLACK);
- x->parent ()->parent ()->color (RB_Tree_Node_Base::RED);
+ // Handle case 3 (see CLR book, pp. 269).
+ x->parent ()->color (ACE_RB_Tree_Node_Base::BLACK);
+ x->parent ()->parent ()->color (ACE_RB_Tree_Node_Base::RED);
RB_rotate_left (x->parent ()->parent ());
}
}
}
}
- // rebalance the tree after insertion of a node
-template <class KEY, class T> RB_Tree_Node<KEY, T> *
-RB_Tree<KEY, T>::RB_tree_successor (RB_Tree_Node<KEY, T> *x) const
+
+// Method to find the successor node of the given node in the tree.
+
+template <class KEY, class T> ACE_RB_Tree_Node<KEY, T> *
+ACE_RB_Tree<KEY, T>::RB_tree_successor (ACE_RB_Tree_Node<KEY, T> *x) const
{
if (x->right ())
{
return RB_tree_minimum (x->right ());
}
- RB_Tree_Node<KEY, T> *y = x->parent ();
+ ACE_RB_Tree_Node<KEY, T> *y = x->parent ();
while ((y) && (x == y->right ()))
{
x = y;
@@ -614,17 +692,19 @@ RB_Tree<KEY, T>::RB_tree_successor (RB_Tree_Node<KEY, T> *x) const
return y;
}
- // method to find the successor node of the given node in the tree
-template <class KEY, class T> RB_Tree_Node<KEY, T> *
-RB_Tree<KEY, T>::RB_tree_predecessor (RB_Tree_Node<KEY, T> *x) const
+
+// Method to find the predecessor node of the given node in the tree.
+
+template <class KEY, class T> ACE_RB_Tree_Node<KEY, T> *
+ACE_RB_Tree<KEY, T>::RB_tree_predecessor (ACE_RB_Tree_Node<KEY, T> *x) const
{
if (x->left ())
{
return RB_tree_maximum (x->left ());
}
- RB_Tree_Node<KEY, T> *y = x->parent ();
+ ACE_RB_Tree_Node<KEY, T> *y = x->parent ();
while ((y) && (x == y->left ()))
{
x = y;
@@ -633,10 +713,12 @@ RB_Tree<KEY, T>::RB_tree_predecessor (RB_Tree_Node<KEY, T> *x) const
return y;
}
- // method to find the predecessor node of the given node in the tree
-template <class KEY, class T> RB_Tree_Node<KEY, T> *
-RB_Tree<KEY, T>::RB_tree_minimum (RB_Tree_Node<KEY, T> *x) const
+
+// Method to find the minimum node of the subtree rooted at the given node.
+
+template <class KEY, class T> ACE_RB_Tree_Node<KEY, T> *
+ACE_RB_Tree<KEY, T>::RB_tree_minimum (ACE_RB_Tree_Node<KEY, T> *x) const
{
while ((x) && (x->left ()))
{
@@ -645,11 +727,12 @@ RB_Tree<KEY, T>::RB_tree_minimum (RB_Tree_Node<KEY, T> *x) const
return x;
}
- // method to find the minimum node of the subtree rooted at the given node
-template <class KEY, class T> RB_Tree_Node<KEY, T> *
-RB_Tree<KEY, T>::RB_tree_maximum (RB_Tree_Node<KEY, T> *x) const
+// Method to find the maximum node of the subtree rooted at the given node.
+
+template <class KEY, class T> ACE_RB_Tree_Node<KEY, T> *
+ACE_RB_Tree<KEY, T>::RB_tree_maximum (ACE_RB_Tree_Node<KEY, T> *x) const
{
while ((x) && (x->right ()))
{
@@ -658,28 +741,32 @@ RB_Tree<KEY, T>::RB_tree_maximum (RB_Tree_Node<KEY, T> *x) const
return x;
}
- // method to find the maximum node of the subtree rooted at the given node
-/////////////////////////////////////////////
-// template class RB_Tree_Iterator<KEY, T> //
-/////////////////////////////////////////////
+
+/////////////////////////////////////////////////
+// template class ACE_RB_Tree_Iterator<KEY, T> //
+/////////////////////////////////////////////////
+
+
+// Constructor.
template <class KEY, class T>
-RB_Tree_Iterator<KEY, T>::RB_Tree_Iterator (const RB_Tree<KEY, T> &tree)
+ACE_RB_Tree_Iterator<KEY, T>::ACE_RB_Tree_Iterator (const ACE_RB_Tree<KEY, T> &tree)
: tree_ (tree), node_ (0)
{
- // position the iterator at the first node in the tree
+ // Position the iterator at the first node in the tree.
first ();
}
- // constructor
+
+
+// Destructor.
template <class KEY, class T>
-RB_Tree_Iterator<KEY, T>::~RB_Tree_Iterator ()
+ACE_RB_Tree_Iterator<KEY, T>::~ACE_RB_Tree_Iterator ()
{
}
- // destructor
#endif /* !defined (ACE_RB_TREE_C) */
View Lorry Controller Status