Added test, less than functor, better comments, etc. to RB_Tree class

5 files changed, 582 insertions, 287 deletions

diff --git a/ace/Functor_T.h b/ace/Functor_T.h
index 471170262e4..10883b311e0 100644
--- a/ace/Functor_T.h
+++ b/ace/Functor_T.h
@@ -66,6 +66,141 @@ private:
   // Method that is going to be invoked.
 };
 
+/////////////////////////////
+// Unary functor templates //
+/////////////////////////////
+
+template <class OPERAND>
+class ACE_Unary_Functor_Base
+{
+  // = TITLE
+  //    Defines a class template that allows us to invoke a function object
+  //    over a single non-const parameterized type without knowing anything 
+  //    about the function and operand objects except their types.
+  //
+  // = DESCRIPTION
+  //    This class declares an interface to execute a unary operation over a
+  //    single object of the non-const paramterized type.  A class can invoke 
+  //    such operation without knowing anything about it, or how it was 
+  //    implemented.
+  //
+public:
+
+  virtual ~ACE_Unary_Functor_Base () {};
+  // Virtual destructor.
+
+  virtual int execute (OPERAND &operand) = 0;
+  // Invokes the function object.
+
+  virtual ACE_Unary_Functor_Base * clone () = 0;
+  // Creates another object of the same type.
+};
+
+template <class OPERAND>
+class ACE_Const_Unary_Functor_Base
+{
+  // = TITLE
+  //    Defines a class template that allows us to invoke a function object
+  //    over a single parameterized type without knowing anything about 
+  //    the function and operand objects except their types.
+  //
+  // = DESCRIPTION
+  //    This class declares an interface to execute a unary operation over a
+  //    single object of the paramterized type.  A class can invoke such 
+  //    an operation without knowing anything about it, or its implementation.
+  //
+public:
+
+  virtual ~ACE_Const_Unary_Functor_Base () {};
+  // Virtual destructor.
+
+  virtual int execute (const OPERAND &operand) = 0;
+  // Invokes the function object.
+
+  virtual ACE_Const_Unary_Functor_Base * clone () = 0;
+  // Creates another object of the same type.
+};
+
+/////////////////////////////
+// Binary functor templates //
+/////////////////////////////
+
+template <class OPERAND1, class OPERAND2>
+class ACE_Binary_Functor_Base
+{
+  // = TITLE
+  //    Defines a class template that allows us to invoke a binary function 
+  //    object over two non-const parameterized types without knowing anything 
+  //    about the function and operand objects except their types.
+  //
+  // = DESCRIPTION
+  //    This class declares an interface to execute a binary operation over two
+  //    objects of the paramterized non-const types.  A class can invoke such 
+  //    an operation without knowing anything about it, or its implementation.
+  //
+public:
+
+  virtual ~ACE_Binary_Functor_Base () {};
+  // Virtual destructor.
+
+  virtual int execute (OPERAND1 &operand1, OPERAND2 &operand2) = 0;
+  // Invokes the function object.
+
+  virtual ACE_Binary_Functor_Base * clone () = 0;
+  // Creates another object of the same type.
+};
+
+template <class OPERAND1, class OPERAND2>
+class ACE_Const_Binary_Functor_Base
+{
+  // = TITLE
+  //    Defines a class template that allows us to invoke a binary function 
+  //    object over two parameterized types without knowing anything about 
+  //    the function and operand objects except their types.
+  //
+  // = DESCRIPTION
+  //    This class declares an interface to execute a binary operation over two
+  //    objects of the paramterized types.  A class can invoke such 
+  //    an operation without knowing anything about it, or its implementation.
+  //
+public:
+
+  virtual ~ACE_Const_Binary_Functor_Base () {};
+  // Virtual destructor.
+
+  virtual int execute (const OPERAND1 &operand1, const OPERAND2 &operand2) = 0;
+  // Invokes the function object.
+
+  virtual ACE_Const_Binary_Functor_Base * clone () = 0;
+  // Creates another object of the same type.
+};
+
+
+template <class OPERAND1, class OPERAND2>
+class ACE_Less_Than_Functor : 
+  public ACE_Const_Binary_Functor_Base<OPERAND1, OPERAND2>
+{
+  // = TITLE
+  //    Defines a class template that allows us to invoke a binary less than 
+  //    function over two parameterized types without knowing anything about 
+  //    the function and operand objects except their types.
+  //
+  // = DESCRIPTION
+  //    This class depends on the definition 
+  //    objects of the paramterized types.  A class can invoke such 
+  //    an operation without knowing anything about it, or its implementation.
+  //
+public:
+
+  virtual int execute (const OPERAND1 &operand1, const OPERAND2 &operand2);
+  // Invokes the function object.
+
+  virtual 
+    ACE_Const_Binary_Functor_Base<OPERAND1, OPERAND2>
+	  * clone ();
+  // Creates another object of the same type.
+};
+
 
 #if defined (__ACE_INLINE__)
 #include "ace/Functor_T.i"
diff --git a/ace/Functor_T.i b/ace/Functor_T.i
index 6bb3fdeccce..01b93b3dfca 100644
--- a/ace/Functor_T.i
+++ b/ace/Functor_T.i
@@ -26,5 +26,23 @@
 // ============================================================================
 
 
+// Invokes the less than function object.
+
+template <class OPERAND1, class OPERAND2> ACE_INLINE int
+ACE_Less_Than_Functor<OPERAND1, OPERAND2>::execute (const OPERAND1 &operand1, 
+                                                    const OPERAND2 &operand2)
+{
+  return (operand1 < operand2) ? 1 : 0;
+}
+
+// Creates another object of the same type.
+
+template <class OPERAND1, class OPERAND2> ACE_INLINE 
+ACE_Const_Binary_Functor_Base<OPERAND1, OPERAND2> *
+ACE_Less_Than_Functor<OPERAND1, OPERAND2>::clone ()
+{
+  return new ACE_Less_Than_Functor<OPERAND1, OPERAND2>;
+}
+
 
 // EOF
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) */
diff --git a/ace/RB_Tree.h b/ace/RB_Tree.h
index e7a0c2ce470..7728c59d366 100644
--- a/ace/RB_Tree.h
+++ b/ace/RB_Tree.h
@@ -18,28 +18,31 @@
 #define ACE_RB_TREE_H
 
 #include "ace/ACE.h"
+#include "ace/Functor.h"
 
 #if !defined (ACE_LACKS_PRAGMA_ONCE)
 # pragma once
 #endif /* ACE_LACKS_PRAGMA_ONCE */
 
-class RB_Tree_Node_Base
+class ACE_RB_Tree_Node_Base
 {
 public:
   enum RB_Tree_Node_Color {RED, BLACK};
 };
 
 template <class KEY, class T>
-class RB_Tree_Node : public RB_Tree_Node_Base
+class ACE_RB_Tree_Node : public ACE_RB_Tree_Node_Base
 {
   // = TITLE
   //   Implements a node in a Red-Black Tree ADT.
 public:
+
   // Initialization and termination methods.
-  RB_Tree_Node (const KEY &k, const T &t);
+
+  ACE_RB_Tree_Node (const KEY &k, const T &t);
   // Constructor.
 
-  ~RB_Tree_Node (void);
+  ~ACE_RB_Tree_Node (void);
   // Destructor.
 
   KEY &key (void);
@@ -54,22 +57,22 @@ public:
   RB_Tree_Node_Color color (void);
   // Get color of the node.
 
-  RB_Tree_Node<KEY, T> *parent (void);
+  ACE_RB_Tree_Node<KEY, T> *parent (void);
   // Accessor for node's parent pointer.
 
-  void parent (RB_Tree_Node<KEY, T> * p);
+  void parent (ACE_RB_Tree_Node<KEY, T> * p);
   // Mutator for node's parent pointer.
 
-  RB_Tree_Node<KEY, T> *left (void);
+  ACE_RB_Tree_Node<KEY, T> *left (void);
   // Accessor for node's left child pointer.
 
-  void left (RB_Tree_Node<KEY, T> *l);
+  void left (ACE_RB_Tree_Node<KEY, T> *l);
   // Mutator for node's left child pointer.
 
-  RB_Tree_Node<KEY, T> *right (void);
+  ACE_RB_Tree_Node<KEY, T> *right (void);
   // Accessor for node's right child pointer.
 
-  void right (RB_Tree_Node<KEY, T> * r);
+  void right (ACE_RB_Tree_Node<KEY, T> * r);
   // Mutator for node's right child pointer
 
 private:
@@ -83,40 +86,45 @@ private:
   RB_Tree_Node_Color color_;
   // Color of the node.
 
-  RB_Tree_Node<KEY, T> *parent_;
+  ACE_RB_Tree_Node<KEY, T> *parent_;
   // Pointer to node's parent.
 
-  RB_Tree_Node<KEY, T> *left_;
+  ACE_RB_Tree_Node<KEY, T> *left_;
   // Pointer to node's left child.
 
-  RB_Tree_Node<KEY, T> *right_;
-  // Pointer to node's righ child.
+  ACE_RB_Tree_Node<KEY, T> *right_;
+  // Pointer to node's right child.
 };
 
 template <class KEY, class T>
-class RB_Tree
+class ACE_RB_Tree
 {
   // = TITLE
   //   Implements a Red-Black Tree ADT, according to T. H. Corman,
   //   C. E. Leiserson, and R. L. Rivest, "Introduction to Algorithms"
-  //   1990, MIT, chapter 14
+  //   1990, MIT, chapter 14.
+  //
+  // = Description
+  //   Optional flag passed to constructor indicates whether or not the
+  //   passed functor should be deleted by the ACE_RB_Tree's destructor.
 public:
   // = Initialization and termination methods.
-  RB_Tree (void);
-  // Constructor
+  ACE_RB_Tree (ACE_Const_Binary_Functor_Base<KEY, KEY> *less_than_functor = 0,
+               int free_functor = 0);
+  // Constructor.
 
-  RB_Tree (const RB_Tree<KEY, T> &rbt);
-  // copy constructor.
+  ACE_RB_Tree (const ACE_RB_Tree<KEY, T> &rbt);
+  // Copy constructor.
 
-  virtual ~RB_Tree (void);
-  // Destructor
+  virtual ~ACE_RB_Tree (void);
+  // Destructor.
 
-  void operator= (const RB_Tree<KEY, T> &rbt);
+  void operator= (const ACE_RB_Tree<KEY, T> &rbt);
   // Assignment operator.
 
   virtual int lessthan (const KEY &k1, const KEY &k2);
-  // Lessthan comparison function for keys.  returns 1 if k1 < k2, 0
-  // otherwise.
+  // Less than comparison function for keys.  Default implementation returns 1
+  // if k1 < k2, and 0 otherwise.
 
   T* find (const KEY &k);
   // Returns a pointer to the item corresponding to the
@@ -125,7 +133,8 @@ public:
   T* insert (const KEY &k, const T &t);
   // 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
+  // for copy construction.  The default implementation also requires that
+  // the key type support welll defined < semantics.  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
@@ -138,63 +147,74 @@ public:
   // occurred.
 
   void clear (void);
-  // destroys all nodes and sets the root pointer null.
+  // Destroys all nodes and sets the root pointer null.
 
   // These could all be made private methods by making the corresponding
   // class template instantiations friends, but there are some problems
-  // with this on certain compilers: leave them all public for now
+  // with this on certain compilers: leave them all public for now.
 
 // private:
 
-  void RB_rotate_right (RB_Tree_Node<KEY, T> * x);
+  void RB_rotate_right (ACE_RB_Tree_Node<KEY, T> * x);
   // Method for right rotation of the tree about a given node.
 
-  void RB_rotate_left (RB_Tree_Node<KEY, T> * x);
+  void RB_rotate_left (ACE_RB_Tree_Node<KEY, T> * x);
   // Method for left rotation of the tree about a given node.
 
-  void RB_delete_fixup (RB_Tree_Node<KEY, T> * x);
+  void RB_delete_fixup (ACE_RB_Tree_Node<KEY, T> * x);
   // Method for restoring Red-Black properties after deletion.
 
-  RB_Tree_Node<KEY, T> * RB_tree_successor (RB_Tree_Node<KEY, T> *x) const;
+  ACE_RB_Tree_Node<KEY, T> * 
+    RB_tree_successor (ACE_RB_Tree_Node<KEY, T> *x) const;
   // Method to find the successor node of the given node in the tree.
 
-  RB_Tree_Node<KEY, T> * RB_tree_predecessor (RB_Tree_Node<KEY, T> *x) const;
+  ACE_RB_Tree_Node<KEY, T> * 
+    RB_tree_predecessor (ACE_RB_Tree_Node<KEY, T> *x) const;
   // Method to find the predecessor node of the given node in the
   // tree.
 
-  RB_Tree_Node<KEY, T> * RB_tree_minimum (RB_Tree_Node<KEY, T> *x) const;
+  ACE_RB_Tree_Node<KEY, T> * 
+    RB_tree_minimum (ACE_RB_Tree_Node<KEY, T> *x) const;
   // Method to find the minimum node of the subtree rooted at the
   // given node.
 
-  RB_Tree_Node<KEY, T> * RB_tree_maximum (RB_Tree_Node<KEY, T> *x) const;
+  ACE_RB_Tree_Node<KEY, T> * 
+    RB_tree_maximum (ACE_RB_Tree_Node<KEY, T> *x) const;
   // Method to find the maximum node of the subtree rooted at the
   // given node.
 
-  RB_Tree_Node<KEY, T> * find_node (const KEY &k);
+  ACE_RB_Tree_Node<KEY, T> * find_node (const KEY &k);
   // 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.
 
-  void RB_rebalance (RB_Tree_Node<KEY, T> * x);
+  void RB_rebalance (ACE_RB_Tree_Node<KEY, T> * x);
   // Rebalance the tree after insertion of a node.
 
-  // private members
+  // Private members.
 
-  RB_Tree_Node<KEY, T> *root_;
+  ACE_RB_Tree_Node<KEY, T> *root_;
   // The root of the tree.
+
+  ACE_Const_Binary_Functor_Base<KEY, KEY> *less_than_functor_;
+  // "Less than" functor for comparing nodes in the tree.
+
+  int free_functor_;
+  // Flag indicating whether or not to delete functor in destructor
+  // and assignment operator.
 };
 
 template <class KEY, class T>
-class RB_Tree_Iterator
+class ACE_RB_Tree_Iterator
 {
   // = TITLE
   //   Implements an iterator for a Red-Black Tree ADT.
 public:
   // = Initialization and termination methods.
-  RB_Tree_Iterator (const RB_Tree<KEY, T> &tree);
+  ACE_RB_Tree_Iterator (const ACE_RB_Tree<KEY, T> &tree);
   // Constructor.
 
-  ~RB_Tree_Iterator (void);
+  ~ACE_RB_Tree_Iterator (void);
   // Destructor.
 
   KEY *key (void);
@@ -216,22 +236,24 @@ public:
   // Move to the previous item in the tree.
 
   int is_done (void);
-  // Returns 0 if the iterator is positioned over a valid RB_Tree
+  // Returns 0 if the iterator is positioned over a valid ACE_RB_Tree
   // node, returns 1 if not.
 
 private:
   // = Declare private and do not define.
 
-  // Explicitly prevent assignment and copy construction of iterators
-  ACE_UNIMPLEMENTED_FUNC (RB_Tree_Iterator (const RB_Tree_Iterator<KEY, T> &))
-  ACE_UNIMPLEMENTED_FUNC (void operator = (const RB_Tree_Iterator<KEY, T> &))
+  // Explicitly prevent assignment and copy construction of iterators.
+  ACE_UNIMPLEMENTED_FUNC (
+    ACE_RB_Tree_Iterator (const ACE_RB_Tree_Iterator<KEY, T> &))
+  ACE_UNIMPLEMENTED_FUNC (
+    void operator = (const ACE_RB_Tree_Iterator<KEY, T> &))
 
   // Private members.
 
-  const RB_Tree<KEY, T> &tree_;
-  // Reference to the RB_Tree over which we're iterating.
+  const ACE_RB_Tree<KEY, T> &tree_;
+  // Reference to the ACE_RB_Tree over which we're iterating.
 
-  RB_Tree_Node <KEY, T> *node_;
+  ACE_RB_Tree_Node <KEY, T> *node_;
   // Pointer to the node currently under the iterator.
 
 };
diff --git a/ace/RB_Tree.i b/ace/RB_Tree.i
index ce6c15dfa0a..b423d77d5dd 100644
--- a/ace/RB_Tree.i
+++ b/ace/RB_Tree.i
@@ -1,152 +1,185 @@
 /* -*- C++ -*- */
 // $Id$
 
-/////////////////////////////////////////
-// template class RB_Tree_Node<KEY, T> //
-/////////////////////////////////////////
+/////////////////////////////////////////////
+// template class ACE_RB_Tree_Node<KEY, T> //
+/////////////////////////////////////////////
+
+// Key accessor.
 
 template <class KEY, class T> ACE_INLINE KEY &
-RB_Tree_Node<KEY, T>::key ()
+ACE_RB_Tree_Node<KEY, T>::key ()
 {
   return k_;
 }
-  // key accessor
+
+
+// Item accessor.
 
 template <class KEY, class T> ACE_INLINE T &
-RB_Tree_Node<KEY, T>::item ()
+ACE_RB_Tree_Node<KEY, T>::item ()
 {
   return t_;
 }
-  // item accessor
+
+
+// Set color of the node.
 
 template <class KEY, class T> ACE_INLINE void
-RB_Tree_Node<KEY, T>::color (RB_Tree_Node_Base::RB_Tree_Node_Color c)
+ACE_RB_Tree_Node<KEY, T>::color (ACE_RB_Tree_Node_Base::RB_Tree_Node_Color c)
 {
   color_ = c;
 }
-  // set color of the node
+
+
+// Get color of the node.
 
 template <class KEY, class T>
-ACE_INLINE RB_Tree_Node_Base::RB_Tree_Node_Color
-RB_Tree_Node<KEY, T>::color ()
+ACE_INLINE ACE_RB_Tree_Node_Base::RB_Tree_Node_Color
+ACE_RB_Tree_Node<KEY, T>::color ()
 {
   return color_;
 }
-  // get color of the node
 
 
-template <class KEY, class T> ACE_INLINE RB_Tree_Node<KEY, T> *
-RB_Tree_Node<KEY, T>::parent ()
+// Accessor for node's parent pointer.
+
+template <class KEY, class T> ACE_INLINE ACE_RB_Tree_Node<KEY, T> *
+ACE_RB_Tree_Node<KEY, T>::parent ()
 {
   return parent_;
 }
-  // accessor for node's parent pointer
+
+
+// Mutator for node's parent pointer.
 
 template <class KEY, class T> ACE_INLINE void
-RB_Tree_Node<KEY, T>::parent (RB_Tree_Node<KEY, T> * p)
+ACE_RB_Tree_Node<KEY, T>::parent (ACE_RB_Tree_Node<KEY, T> * p)
 {
   parent_ = p;
 }
-  // mutator for node's parent pointer
+  
+
+
+// Accessor for node's left child pointer.
 
-template <class KEY, class T> ACE_INLINE RB_Tree_Node<KEY, T> *
-RB_Tree_Node<KEY, T>::left ()
+template <class KEY, class T> ACE_INLINE ACE_RB_Tree_Node<KEY, T> *
+ACE_RB_Tree_Node<KEY, T>::left ()
 {
   return left_;
 }
-  // accessor for node's left child pointer
+
+
+// Mutator for node's left child pointer.
 
 template <class KEY, class T> ACE_INLINE void
-RB_Tree_Node<KEY, T>::left (RB_Tree_Node<KEY, T> * l)
+ACE_RB_Tree_Node<KEY, T>::left (ACE_RB_Tree_Node<KEY, T> * l)
 {
   left_ = l;
 }
-  // mutator for node's left child pointer
 
-template <class KEY, class T> ACE_INLINE RB_Tree_Node<KEY, T> *
-RB_Tree_Node<KEY, T>::right ()
+
+// Accessor for node's right child pointer.
+
+template <class KEY, class T> ACE_INLINE ACE_RB_Tree_Node<KEY, T> *
+ACE_RB_Tree_Node<KEY, T>::right ()
 {
   return right_;
 }
-  // accessor for node's right child pointer
+
+
+// Mutator for node's right child pointer.
 
 template <class KEY, class T> ACE_INLINE void
-RB_Tree_Node<KEY, T>::right (RB_Tree_Node<KEY, T> * r)
+ACE_RB_Tree_Node<KEY, T>::right (ACE_RB_Tree_Node<KEY, T> * r)
 {
   right_ = r;
 }
-  // mutator for node's right child pointer
 
 
-////////////////////////////////////
-// template class RB_Tree<KEY, T> //
-////////////////////////////////////
+
+////////////////////////////////////////
+// template class ACE_RB_Tree<KEY, T> //
+////////////////////////////////////////
+
+
+// Destroys all nodes and sets the root pointer null.
 
 template <class KEY, class T> ACE_INLINE void
-RB_Tree<KEY, T>::clear ()
+ACE_RB_Tree<KEY, T>::clear ()
 {
   delete root_;
   root_ = 0;
 }
-  // destroys all nodes and sets the root pointer null.
 
 
-/////////////////////////////////////////////
-// template class RB_Tree_Iterator<KEY, T> //
-/////////////////////////////////////////////
 
+/////////////////////////////////////////////////
+// template class ACE_RB_Tree_Iterator<KEY, T> //
+/////////////////////////////////////////////////
 
 
+// Accessor for key of node under iterator (if any).
+
 template <class KEY, class T> ACE_INLINE KEY *
-RB_Tree_Iterator<KEY, T>::key ()
+ACE_RB_Tree_Iterator<KEY, T>::key ()
 {
   return node_ ? (&(node_->key ())) : 0;
 }
-  // accessor for key of node under iterator (if any)
+
+
+// Accessor for item of node under iterator (if any).
 
 template <class KEY, class T> ACE_INLINE T *
-RB_Tree_Iterator<KEY, T>::item ()
+ACE_RB_Tree_Iterator<KEY, T>::item ()
 {
   return node_ ? (&(node_->item ())) : 0;
 }
-  // accessor for item of node under iterator (if any)
+
+
+// Move to the first item in the tree.
 
 template <class KEY, class T> ACE_INLINE int
-RB_Tree_Iterator<KEY, T>::first ()
+ACE_RB_Tree_Iterator<KEY, T>::first ()
 {
   node_ = tree_.RB_tree_minimum (tree_.root_);
   return node_ ? 1 : 0;
 }
-  // move to the first item in the tree
+
+
+// Move to the last item in the tree.
 
 template <class KEY, class T> ACE_INLINE int
-RB_Tree_Iterator<KEY, T>::last ()
+ACE_RB_Tree_Iterator<KEY, T>::last ()
 {
   node_ = tree_.RB_tree_maximum (tree_.root_);
   return node_ ? 1 : 0;
 }
-  // move to the last item in the tree
+
+
+// Moves to the next item in the tree,
+// returns 1 if there is a next item, 0 otherwise.
 
 template <class KEY, class T> ACE_INLINE int
-RB_Tree_Iterator<KEY, T>::next ()
+ACE_RB_Tree_Iterator<KEY, T>::next ()
 {
   node_ = tree_.RB_tree_successor (node_);
   return node_ ? 1 : 0;
 }
-  // move to the next item in the tree
-  // returns 1 if there is a next item, 0 otherwise
+
+
+// Moves to the previous item in the tree,
+// returns 1 if there is a previous item, 0 otherwise.
 
 template <class KEY, class T> ACE_INLINE int
-RB_Tree_Iterator<KEY, T>::previous ()
+ACE_RB_Tree_Iterator<KEY, T>::previous ()
 {
   node_ = tree_.RB_tree_predecessor (node_);
   return node_ ? 1 : 0;
 }
-  // move to the previous item in the tree
-  // returns 1 if there is a previous item, 0 otherwise
 
 template <class KEY, class T> ACE_INLINE int
-RB_Tree_Iterator<KEY, T>::is_done ()
+ACE_RB_Tree_Iterator<KEY, T>::is_done ()
 {
   return node_ ? 0 : 1;
 }