Main Page   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members   File Members   Related Pages  

RB_Tree.cpp

Go to the documentation of this file.
00001 // $Id: RB_Tree.cpp,v 1.1.1.4 2003/02/21 18:36:32 chad Exp $
00002 
00003 // RB_Tree.cpp
00004 
00005 #ifndef ACE_RB_TREE_C
00006 #define ACE_RB_TREE_C
00007 
00008 #include "ace/RB_Tree.h"
00009 #include "ace/SString.h"
00010 
00011 #if !defined (ACE_LACKS_PRAGMA_ONCE)
00012 # pragma once
00013 #endif /* ACE_LACKS_PRAGMA_ONCE */
00014 
00015 #if !defined (__ACE_INLINE__)
00016 #include "ace/RB_Tree.i"
00017 #endif /* __ACE_INLINE__ */
00018 
00019 ACE_RCSID(ace, RB_Tree, "$Id: RB_Tree.cpp,v 1.1.1.4 2003/02/21 18:36:32 chad Exp $")
00020 
00021 // Constructor.
00022 
00023 template <class EXT_ID, class INT_ID>
00024 ACE_RB_Tree_Node<EXT_ID, INT_ID>::ACE_RB_Tree_Node (const EXT_ID &k, const INT_ID &t)
00025   : k_ (k),
00026     t_ (t),
00027     color_ (RED),
00028     parent_ (0),
00029     left_ (0),
00030     right_ (0)
00031 {
00032   ACE_TRACE ("ACE_RB_Tree_Node<EXT_ID, INT_ID>::ACE_RB_Tree_Node (const EXT_ID &k, const INT_ID &t)");
00033 }
00034 
00035 
00036 // Destructor.
00037 
00038 template <class EXT_ID, class INT_ID>
00039 ACE_RB_Tree_Node<EXT_ID, INT_ID>::~ACE_RB_Tree_Node (void)
00040 {
00041   ACE_TRACE ("ACE_RB_Tree_Node<EXT_ID, INT_ID>::~ACE_RB_Tree_Node");
00042 
00043   // Delete left sub-tree.
00044   delete left_;
00045 
00046   // Delete right sub_tree.
00047   delete right_;
00048 }
00049 
00050 // Constructor.
00051 
00052 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
00053 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree (ACE_Allocator *alloc)
00054   : allocator_ (alloc),
00055     root_ (0),
00056     current_size_ (0)
00057 {
00058   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::"
00059              "ACE_RB_Tree (ACE_Allocator *alloc)");
00060   if (this->open (alloc) == -1)
00061     ACE_ERROR ((LM_ERROR,
00062                 ACE_LIB_TEXT ("ACE_RB_Tree::ACE_RB_Tree\n")));
00063 }
00064 
00065 // Copy constructor.
00066 
00067 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
00068 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree (const ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &rbt)
00069   : allocator_ (rbt.allocator_),
00070     root_ (0),
00071     current_size_ (0)
00072 {
00073   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::"
00074              "ACE_RB_Tree (const ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &rbt)");
00075   ACE_WRITE_GUARD (ACE_LOCK, ace_mon, this->lock_);
00076 
00077   // Make a deep copy of the passed tree.
00078   ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> iter(rbt);
00079 
00080   for (iter.first ();
00081 
00082        iter.is_done () == 0; iter.next ())
00083     insert_i (*(iter.key ()),
00084               *(iter.item ()));
00085 }
00086 
00087 // Destructor.
00088 
00089 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
00090 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::~ACE_RB_Tree ()
00091 {
00092   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::~ACE_RB_Tree");
00093 
00094   // Use the locked public method, to be totally safe, as the class
00095   // can be used with an allocator and placement new.
00096   this->close ();
00097 }
00098 
00099 // Assignment operator.
00100 
00101 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> void
00102 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator = (const ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &rbt)
00103 {
00104   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator =");
00105   ACE_WRITE_GUARD (ACE_LOCK, ace_mon, this->lock_);
00106 
00107   if (this != &rbt)
00108     {
00109       // Clear out the existing tree.
00110       close_i ();
00111 
00112       // Make a deep copy of the passed tree.
00113       ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> iter(rbt);
00114 
00115       for (iter.first ();
00116            iter.is_done () == 0;
00117            iter.next ())
00118         insert_i (*(iter.key ()),
00119                   *(iter.item ()));
00120 
00121       // Use the same allocator as the rhs.
00122       allocator_ = rbt.allocator_;
00123     }
00124 }
00125 // Less than comparison function for keys, default functor
00126 // implementation returns 1 if k1 < k2, 0 otherwise.
00127 
00128 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> int
00129 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::lessthan (const EXT_ID &k1, const EXT_ID &k2)
00130 {
00131   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::lessthan");
00132   return this->compare_keys_ (k1, k2);
00133 }
00134 
00135 // Method for right rotation of the tree about a given node.
00136 
00137 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>  void
00138 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_rotate_right (ACE_RB_Tree_Node<EXT_ID, INT_ID> *x)
00139 {
00140   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_rotate_right");
00141 
00142   if (!x)
00143     ACE_ERROR ((LM_ERROR,
00144                 ACE_LIB_TEXT ("%p\n"),
00145                 ACE_LIB_TEXT ("\nerror: x is a null pointer in ")
00146                 ACE_LIB_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::RB_rotate_right\n")));
00147   else if (! (x->left()))
00148     ACE_ERROR ((LM_ERROR,
00149                 ACE_LIB_TEXT ("%p\n"),
00150                 ACE_LIB_TEXT ("\nerror: x->left () is a null pointer in ")
00151                 ACE_LIB_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::RB_rotate_right\n")));
00152   else
00153     {
00154       ACE_RB_Tree_Node<EXT_ID, INT_ID> * y;
00155       y = x->left ();
00156       x->left (y->right ());
00157       if (y->right ())
00158         y->right ()->parent (x);
00159       y->parent (x->parent ());
00160       if (x->parent ())
00161         {
00162           if (x == x->parent ()->right ())
00163             x->parent ()->right (y);
00164           else
00165             x->parent ()->left (y);
00166         }
00167       else
00168         root_ = y;
00169       y->right (x);
00170       x->parent (y);
00171     }
00172 }
00173 
00174 // Method for left rotation of the tree about a given node.
00175 
00176 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> void
00177 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_rotate_left (ACE_RB_Tree_Node<EXT_ID, INT_ID> * x)
00178 {
00179   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_rotate_left");
00180 
00181   if (! x)
00182     ACE_ERROR ((LM_ERROR,
00183                 ACE_LIB_TEXT ("%p\n"),
00184                 ACE_LIB_TEXT ("\nerror: x is a null pointer in ")
00185                 ACE_LIB_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::RB_rotate_left\n")));
00186   else if (! (x->right()))
00187     ACE_ERROR ((LM_ERROR,
00188                 ACE_LIB_TEXT ("%p\n"),
00189                 ACE_LIB_TEXT ("\nerror: x->right () is a null pointer ")
00190                 ACE_LIB_TEXT ("in ACE_RB_Tree<EXT_ID, INT_ID>::RB_rotate_left\n")));
00191   else
00192     {
00193       ACE_RB_Tree_Node<EXT_ID, INT_ID> * y;
00194       y = x->right ();
00195       x->right (y->left ());
00196       if (y->left ())
00197         y->left ()->parent (x);
00198       y->parent (x->parent ());
00199       if (x->parent ())
00200         {
00201           if (x == x->parent ()->left ())
00202             x->parent ()->left (y);
00203           else
00204             x->parent ()->right (y);
00205         }
00206       else
00207         root_ = y;
00208       y->left (x);
00209       x->parent (y);
00210     }
00211 }
00212 
00213 // Method for restoring Red-Black properties after a specific deletion case.
00214 
00215 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>  void
00216 
00217 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_delete_fixup (ACE_RB_Tree_Node<EXT_ID, INT_ID> *x,
00218                  ACE_RB_Tree_Node<EXT_ID, INT_ID> *parent)
00219 {
00220   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_delete_fixup");
00221 
00222   while (x != this->root_
00223          && (!x
00224              || x->color () == ACE_RB_Tree_Node_Base::BLACK))
00225     {
00226       if (x == parent->left ())
00227         {
00228           ACE_RB_Tree_Node<EXT_ID, INT_ID> *w = parent->right ();
00229           if (w && w->color () == ACE_RB_Tree_Node_Base::RED)
00230             {
00231               w->color (ACE_RB_Tree_Node_Base::BLACK);
00232               parent->color (ACE_RB_Tree_Node_Base::RED);
00233               RB_rotate_left (parent);
00234               w = parent->right ();
00235             }
00236           // CLR pp. 263 says that nil nodes are implicitly colored BLACK
00237           if (w
00238               && (!w->left ()
00239                   || w->left ()->color () == ACE_RB_Tree_Node_Base::BLACK)
00240               && (!w->right ()
00241                   || w->right ()->color () == ACE_RB_Tree_Node_Base::BLACK))
00242             {
00243               w->color (ACE_RB_Tree_Node_Base::RED);
00244               x = parent;
00245               parent = x->parent ();
00246             }
00247           else
00248             {
00249               // CLR pp. 263 says that nil nodes are implicitly colored BLACK
00250               if (w
00251                   && (!w->right ()
00252                       || w->right ()->color () == ACE_RB_Tree_Node_Base::BLACK))
00253                 {
00254                   if (w->left ())
00255                     w->left ()->color (ACE_RB_Tree_Node_Base::BLACK);
00256                   w->color (ACE_RB_Tree_Node_Base::RED);
00257                   RB_rotate_right (w);
00258                   w = parent->right ();
00259                 }
00260               if (w)
00261                 {
00262                   w->color (parent->color ());
00263                   if (w->right ())
00264                     w->right ()->color (ACE_RB_Tree_Node_Base::BLACK);
00265                 }
00266               parent->color (ACE_RB_Tree_Node_Base::BLACK);
00267               RB_rotate_left (parent);
00268               x = root_;
00269             }
00270         }
00271       else
00272         {
00273           ACE_RB_Tree_Node<EXT_ID, INT_ID> *w = parent->left ();
00274           if (w && w->color () == ACE_RB_Tree_Node_Base::RED)
00275             {
00276               w->color (ACE_RB_Tree_Node_Base::BLACK);
00277               parent->color (ACE_RB_Tree_Node_Base::RED);
00278               RB_rotate_right (parent);
00279               w = parent->left ();
00280             }
00281           // CLR pp. 263 says that nil nodes are implicitly colored BLACK
00282           if (w
00283               && (!w->left ()
00284                   || w->left ()->color () == ACE_RB_Tree_Node_Base::BLACK)
00285               && (!w->right ()
00286                   || w->right ()->color () == ACE_RB_Tree_Node_Base::BLACK))
00287             {
00288               w->color (ACE_RB_Tree_Node_Base::RED);
00289               x = parent;
00290               parent = x->parent ();
00291             }
00292           else
00293             {
00294               // CLR pp. 263 says that nil nodes are implicitly colored BLACK
00295               if (w
00296                   && (!w->left ()
00297                       || w->left ()->color () == ACE_RB_Tree_Node_Base::BLACK))
00298                 {
00299                   w->color (ACE_RB_Tree_Node_Base::RED);
00300                   if (w->right ())
00301                     w->right ()->color (ACE_RB_Tree_Node_Base::BLACK);
00302                   RB_rotate_left (w);
00303                   w = parent->left ();
00304                 }
00305               if (w)
00306                 {
00307                   w->color (parent->color ());
00308                   if (w->left ())
00309                     w->left ()->color (ACE_RB_Tree_Node_Base::BLACK);
00310                 }
00311               parent->color (ACE_RB_Tree_Node_Base::BLACK);
00312               RB_rotate_right (parent);
00313               x = root_;
00314             }
00315         }
00316     }
00317 
00318   if (x)
00319     x->color (ACE_RB_Tree_Node_Base::BLACK);
00320 }
00321 
00322 // Return a pointer to a matching node if there is one, a pointer to
00323 // the node under which to insert the item if the tree is not empty
00324 // and there is no such match, or 0 if the tree is empty.
00325 
00326 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> ACE_RB_Tree_Node<EXT_ID, INT_ID> *
00327 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::find_node (const EXT_ID &k, ACE_RB_Tree_Base::RB_SearchResult &result)
00328 {
00329   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::find_node");
00330 
00331   // Start at the root.
00332   ACE_RB_Tree_Node<EXT_ID, INT_ID> *current = root_;
00333 
00334   while (current)
00335     {
00336       // While there are more nodes to examine.
00337       if (this->lessthan (current->key (), k))
00338         {
00339           // If the search key is greater than the current node's key.
00340           if (current->right ())
00341             // If the right subtree is not empty, search to the right.
00342             current = current->right ();
00343           else
00344             {
00345               // If the right subtree is empty, we're done searching,
00346               // and are positioned to the left of the insertion point.
00347               result = LEFT;
00348               break;
00349             }
00350         }
00351       else if (this->lessthan (k, current->key ()))
00352         {
00353           // Else if the search key is less than the current node's key.
00354           if (current->left ())
00355             // If the left subtree is not empty, search to the left.
00356             current = current->left ();
00357           else
00358             {
00359               // If the left subtree is empty, we're done searching,
00360               // and are positioned to the right of the insertion point.
00361               result = RIGHT;
00362               break;
00363             }
00364         }
00365       else
00366         {
00367           // If the keys match exactly, we're done as well.
00368           result = EXACT;
00369           break;
00370         }
00371     }
00372 
00373   return current;
00374 }
00375 
00376 // Rebalance the tree after insertion of a node.
00377 
00378 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> void
00379 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_rebalance (ACE_RB_Tree_Node<EXT_ID, INT_ID> * x)
00380 {
00381   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_rebalance");
00382 
00383   ACE_RB_Tree_Node<EXT_ID, INT_ID> *y = 0;
00384 
00385   while (x &&
00386          x->parent ()
00387          && x->parent ()->color () == ACE_RB_Tree_Node_Base::RED)
00388     {
00389       if (! x->parent ()->parent ())
00390         {
00391           // If we got here, something is drastically wrong!
00392           ACE_ERROR ((LM_ERROR,
00393                       ACE_LIB_TEXT ("%p\n"),
00394                       ACE_LIB_TEXT ("\nerror: parent's parent is null in ")
00395                       ACE_LIB_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::RB_rebalance\n")));
00396           return;
00397         }
00398 
00399       if (x->parent () == x->parent ()->parent ()->left ())
00400         {
00401           y = x->parent ()->parent ()->right ();
00402           if (y && y->color () == ACE_RB_Tree_Node_Base::RED)
00403             {
00404               // Handle case 1 (see CLR book, pp. 269).
00405               x->parent ()->color (ACE_RB_Tree_Node_Base::BLACK);
00406               y->color (ACE_RB_Tree_Node_Base::BLACK);
00407               x->parent ()->parent ()->color (ACE_RB_Tree_Node_Base::RED);
00408               x = x->parent ()->parent ();
00409             }
00410           else
00411             {
00412               if (x == x->parent ()->right ())
00413                 {
00414                   // Transform case 2 into case 3 (see CLR book, pp. 269).
00415                   x = x->parent ();
00416                   RB_rotate_left (x);
00417                 }
00418 
00419               // Handle case 3 (see CLR book, pp. 269).
00420               x->parent ()->color (ACE_RB_Tree_Node_Base::BLACK);
00421               x->parent ()->parent ()->color (ACE_RB_Tree_Node_Base::RED);
00422               RB_rotate_right (x->parent ()->parent ());
00423             }
00424         }
00425       else
00426         {
00427           y = x->parent ()->parent ()->left ();
00428           if (y && y->color () == ACE_RB_Tree_Node_Base::RED)
00429             {
00430               // Handle case 1 (see CLR book, pp. 269).
00431               x->parent ()->color (ACE_RB_Tree_Node_Base::BLACK);
00432               y->color (ACE_RB_Tree_Node_Base::BLACK);
00433               x->parent ()->parent ()->color (ACE_RB_Tree_Node_Base::RED);
00434               x = x->parent ()->parent ();
00435             }
00436           else
00437             {
00438               if (x == x->parent ()->left ())
00439                 {
00440                   // Transform case 2 into case 3 (see CLR book, pp. 269).
00441                   x = x->parent ();
00442                   RB_rotate_right (x);
00443                 }
00444 
00445               // Handle case 3 (see CLR book, pp. 269).
00446               x->parent ()->color (ACE_RB_Tree_Node_Base::BLACK);
00447               x->parent ()->parent ()->color (ACE_RB_Tree_Node_Base::RED);
00448               RB_rotate_left (x->parent ()->parent ());
00449             }
00450         }
00451     }
00452 }
00453 
00454 // Method to find the successor node of the given node in the tree.
00455 
00456 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> ACE_RB_Tree_Node<EXT_ID, INT_ID> *
00457 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_tree_successor (ACE_RB_Tree_Node<EXT_ID, INT_ID> *x) const
00458 {
00459   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_tree_successor");
00460 
00461   if (x == 0)
00462     return 0;
00463 
00464   if (x->right ())
00465     return RB_tree_minimum (x->right ());
00466 
00467   ACE_RB_Tree_Node<EXT_ID, INT_ID> *y = x->parent ();
00468   while ((y) && (x == y->right ()))
00469     {
00470       x = y;
00471       y = y->parent ();
00472     }
00473 
00474   return y;
00475 }
00476 
00477 // Method to find the predecessor node of the given node in the tree.
00478 
00479 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> ACE_RB_Tree_Node<EXT_ID, INT_ID> *
00480 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_tree_predecessor (ACE_RB_Tree_Node<EXT_ID, INT_ID> *x) const
00481 {
00482   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_tree_predecessor");
00483   if (x == 0)
00484     return 0;
00485 
00486   if (x->left ())
00487     return RB_tree_maximum (x->left ());
00488 
00489   ACE_RB_Tree_Node<EXT_ID, INT_ID> *y = x->parent ();
00490 
00491   while ((y) && (x == y->left ()))
00492     {
00493       x = y;
00494       y = y->parent ();
00495     }
00496 
00497   return y;
00498 }
00499 
00500 // Method to find the minimum node of the subtree rooted at the given node.
00501 
00502 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> ACE_RB_Tree_Node<EXT_ID, INT_ID> *
00503 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_tree_minimum (ACE_RB_Tree_Node<EXT_ID, INT_ID> *x) const
00504 {
00505   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_tree_minimum");
00506 
00507   while ((x) && (x->left ()))
00508     x = x->left ();
00509 
00510   return x;
00511 }
00512 
00513 // Method to find the maximum node of the subtree rooted at the given node.
00514 
00515 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> ACE_RB_Tree_Node<EXT_ID, INT_ID> *
00516 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_tree_maximum (ACE_RB_Tree_Node<EXT_ID, INT_ID> *x) const
00517 {
00518   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_tree_maximum");
00519 
00520   while ((x) && (x->right ()))
00521     x = x->right ();
00522 
00523   return x;
00524 }
00525 
00526 // Close down an RB_Tree.  this method should only be called with
00527 // locks already held.
00528 
00529 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> int
00530 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::close_i ()
00531 {
00532   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::close_i");
00533 
00534   delete root_;
00535   current_size_ = 0;
00536   root_ = 0;
00537 
00538   return 0;
00539 }
00540 
00541 // Returns a pointer to the item corresponding to the given key, or 0
00542 // if it cannot find the key in the tree.  This method should only be
00543 // called with locks already held.
00544 
00545 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> int
00546 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::find_i (const EXT_ID &k,
00547                                                              ACE_RB_Tree_Node<EXT_ID, INT_ID>* &entry, int find_exact)
00548 {
00549   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::find_i");
00550 
00551   // Try to find a match.
00552   RB_SearchResult result = LEFT;
00553   ACE_RB_Tree_Node<EXT_ID, INT_ID> *current = find_node (k, result);
00554 
00555   if (current)
00556     {
00557       // Found a match
00558       if (!find_exact || result == EXACT)
00559         entry = current;  // Assign the entry for any match.
00560       return (result == EXACT ? 0 : -1);
00561     }
00562   else
00563     // The node is not there.
00564     return -1;
00565 }
00566 
00567 // Inserts a *copy* of the key and the item into the tree: both the
00568 // key type EXT_ID and the item type INT_ID must have well defined
00569 // semantics for copy construction and < comparison.  This method
00570 // returns a pointer to the inserted item copy, or 0 if an error
00571 // occurred.  NOTE: if an identical key already exists in the tree, no
00572 // new item is created, and the returned pointer addresses the
00573 // existing item associated with the existing key.  This method should
00574 // only be called with locks already held.
00575 
00576 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> INT_ID *
00577 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::insert_i (const EXT_ID &k, const INT_ID &t)
00578 {
00579   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::insert_i (const EXT_ID &k, const INT_ID &t)");
00580 
00581   // Find the closest matching node, if there is one.
00582   RB_SearchResult result = LEFT;
00583   ACE_RB_Tree_Node<EXT_ID, INT_ID> *current = find_node (k, result);
00584   if (current)
00585     {
00586       // If the keys match, just return a pointer to the node's item.
00587       if (result == EXACT)
00588         return &current->item ();
00589 
00590       // Otherwise if we're to the left of the insertion point, insert
00591       // into the right subtree.
00592       else if (result == LEFT)
00593         {
00594           if (current->right ())
00595             {
00596               // If there is already a right subtree, complain.
00597               ACE_ERROR_RETURN ((LM_ERROR,
00598                                  ACE_LIB_TEXT ("%p\n"),
00599                                  ACE_LIB_TEXT ("\nright subtree already present in ")
00600                                  ACE_LIB_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::insert_i\n")),
00601                                 0);
00602             }
00603           else
00604             {
00605               // The right subtree is empty: insert new node there.
00606               ACE_RB_Tree_Node<EXT_ID, INT_ID> *tmp = 0;
00607 
00608               ACE_NEW_RETURN (tmp,
00609                               (ACE_RB_Tree_Node<EXT_ID, INT_ID>) (k, t),
00610                               0);
00611               current->right (tmp);
00612 
00613               // If the node was successfully inserted, set its
00614               // parent, rebalance the tree, color the root black, and
00615               // return a pointer to the inserted item.
00616               INT_ID *item = &(current->right ()->item ());
00617               current->right ()->parent (current);
00618               RB_rebalance (current->right ());
00619               root_->color (ACE_RB_Tree_Node_Base::BLACK);
00620               ++current_size_;
00621               return item;
00622             }
00623         }
00624       // Otherwise, we're to the right of the insertion point, so
00625       // insert into the left subtree.
00626       else // (result == RIGHT)
00627         {
00628           if (current->left ())
00629             // If there is already a left subtree, complain.
00630             ACE_ERROR_RETURN ((LM_ERROR,
00631                                ACE_LIB_TEXT ("%p\n"),
00632                                ACE_LIB_TEXT ("\nleft subtree already present in ")
00633                                ACE_LIB_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::insert_i\n")),
00634                               0);
00635           else
00636             {
00637               // The left subtree is empty: insert new node there.
00638               ACE_RB_Tree_Node<EXT_ID, INT_ID> *tmp = 0;
00639               ACE_NEW_RETURN (tmp,
00640                               (ACE_RB_Tree_Node<EXT_ID, INT_ID>) (k, t),
00641                               0);
00642               current->left (tmp);
00643 
00644               // If the node was successfully inserted, set its
00645               // parent, rebalance the tree, color the root black, and
00646               // return a pointer to the inserted item.
00647               INT_ID *item = &current->left ()->item ();
00648               current->left ()->parent (current);
00649               RB_rebalance (current->left ());
00650               root_->color (ACE_RB_Tree_Node_Base::BLACK);
00651               ++current_size_;
00652               return item;
00653             }
00654         }
00655     }
00656   else
00657     {
00658       // The tree is empty: insert at the root and color the root
00659       // black.
00660       ACE_NEW_RETURN (root_,
00661                       (ACE_RB_Tree_Node<EXT_ID, INT_ID>) (k, t),
00662                       0);
00663       if (root_)
00664         {
00665           root_->color (ACE_RB_Tree_Node_Base::BLACK);
00666           ++current_size_;
00667           return &root_->item ();
00668         }
00669     }
00670   return 0;
00671 }
00672 
00673 // Inserts a *copy* of the key and the item into the tree: both the
00674 // key type EXT_ID and the item type INT_ID must have well defined
00675 // semantics for copy construction.  The default implementation also
00676 // requires that the key type support well defined < semantics.  This
00677 // method passes back a pointer to the inserted (or existing) node,
00678 // and the search status.  If the node already exists, the method
00679 // returns 1.  If the node does not exist, and a new one is
00680 // successfully created, and the method returns 0.  If there was an
00681 // error, the method returns -1.
00682 
00683 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> int
00684 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::insert_i (const EXT_ID &k,
00685                                                                const INT_ID &t,
00686                                                                ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry)
00687 {
00688   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::insert_i (const EXT_ID &k, const INT_ID &t, "
00689              "ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry)");
00690 
00691   // Find the closest matching node, if there is one.
00692   RB_SearchResult result = LEFT;
00693   ACE_RB_Tree_Node<EXT_ID, INT_ID> *current = find_node (k, result);
00694   if (current)
00695     {
00696       // If the keys match, just return a pointer to the node's item.
00697       if (result == EXACT)
00698         {
00699           entry = current;
00700           return 1;
00701         }
00702       // Otherwise if we're to the left of the insertion
00703       // point, insert into the right subtree.
00704       else if (result == LEFT)
00705         {
00706           if (current->right ())
00707             {
00708               // If there is already a right subtree, complain.
00709               ACE_ERROR_RETURN ((LM_ERROR,
00710                                  ACE_LIB_TEXT ("%p\n"),
00711                                  ACE_LIB_TEXT ("\nright subtree already present in ")
00712                                  ACE_LIB_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::insert_i\n")),
00713                                 -1);
00714             }
00715           else
00716             {
00717               // The right subtree is empty: insert new node there.
00718               ACE_RB_Tree_Node<EXT_ID, INT_ID> *tmp = 0;
00719               ACE_NEW_RETURN (tmp,
00720                               (ACE_RB_Tree_Node<EXT_ID, INT_ID>) (k, t),
00721                               -1);
00722               current->right (tmp);
00723 
00724               // If the node was successfully inserted, set its parent, rebalance
00725               // the tree, color the root black, and return a pointer to the
00726               // inserted item.
00727               entry = current->right ();
00728               current->right ()->parent (current);
00729               RB_rebalance (current->right ());
00730               root_->color (ACE_RB_Tree_Node_Base::BLACK);
00731               ++current_size_;
00732               return 0;
00733             }
00734         }
00735       // Otherwise, we're to the right of the insertion point, so
00736       // insert into the left subtree.
00737       else // (result == RIGHT)
00738         {
00739           if (current->left ())
00740             // If there is already a left subtree, complain.
00741             ACE_ERROR_RETURN ((LM_ERROR,
00742                                ACE_LIB_TEXT ("%p\n"),
00743                                ACE_LIB_TEXT ("\nleft subtree already present in ")
00744                                ACE_LIB_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::insert_i\n")),
00745                               -1);
00746           else
00747             {
00748               // The left subtree is empty: insert new node there.
00749               ACE_RB_Tree_Node<EXT_ID, INT_ID> *tmp = 0;
00750               ACE_NEW_RETURN (tmp,
00751                               (ACE_RB_Tree_Node<EXT_ID, INT_ID>) (k, t),
00752                               -1);
00753               current->left (tmp);
00754               // If the node was successfully inserted, set its
00755               // parent, rebalance the tree, color the root black, and
00756               // return a pointer to the inserted item.
00757               entry = current->left ();
00758               current->left ()->parent (current);
00759               RB_rebalance (current->left ());
00760               root_->color (ACE_RB_Tree_Node_Base::BLACK);
00761               ++current_size_;
00762               return 0;
00763             }
00764         }
00765     }
00766   else
00767     {
00768       // The tree is empty: insert at the root and color the root black.
00769       ACE_NEW_RETURN (root_,
00770                       (ACE_RB_Tree_Node<EXT_ID, INT_ID>) (k, t),
00771                       -1);
00772       root_->color (ACE_RB_Tree_Node_Base::BLACK);
00773       ++current_size_;
00774       entry = root_;
00775       return 0;
00776     }
00777 }
00778 
00779 // Removes the item associated with the given key from the tree and
00780 // destroys it.  Returns 1 if it found the item and successfully
00781 // destroyed it, 0 if it did not find the item, or -1 if an error
00782 // occurred.  This method should only be called with locks already
00783 // held.
00784 
00785 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>  int
00786 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::remove_i (const EXT_ID &k, INT_ID &i)
00787 {
00788   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::remove_i (const EXT_ID &k, INT_ID &i)");
00789 
00790   // Find a matching node, if there is one.
00791   ACE_RB_Tree_Node<EXT_ID, INT_ID> *z;
00792   RB_SearchResult result = LEFT;
00793   z = find_node (k, result);
00794 
00795   // If there is a matching node: remove and destroy it.
00796   if (z && result == EXACT)
00797     {
00798       // Return the internal id stored in the deleted node.
00799       i = z->item ();
00800       return -1 == this->remove_i (z) ? -1 : 1;
00801     }
00802   else
00803   {
00804     // No matching node was found: return 0.
00805     return 0;
00806   }
00807 }
00808 
00809 /// Recursive function to dump the state of an object.
00810 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> void
00811 
00812 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::dump_i (ACE_RB_Tree_Node<EXT_ID, INT_ID> *node) const
00813 {
00814   if (node)
00815     {
00816       dump_node_i (*node);
00817 
00818       ACE_DEBUG ((LM_DEBUG,  ACE_LIB_TEXT ("\ndown left\n")));
00819       this->dump_i (node->left ());
00820       ACE_DEBUG ((LM_DEBUG,  ACE_LIB_TEXT ("\nup left\n")));
00821 
00822       ACE_DEBUG ((LM_DEBUG,  ACE_LIB_TEXT ("\ndown right\n")));
00823       this->dump_i (node->right ());
00824       ACE_DEBUG ((LM_DEBUG,  ACE_LIB_TEXT ("\nup right\n")));
00825     }
00826   else
00827     {
00828       ACE_DEBUG ((LM_DEBUG,  ACE_LIB_TEXT ("\nNULL POINTER (BLACK)\n")));
00829     }
00830 }
00831 
00832 
00833 /// Function to dump node itself.  Does not show parameterized node contents
00834 /// in its basic form, but template specialization can be used to
00835 /// provide definitions for various EXT_ID and INT_ID types.
00836 
00837 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> void
00838 
00839 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::dump_node_i (ACE_RB_Tree_Node<EXT_ID, INT_ID> &node) const
00840 {
00841   const char * color_str = (node.color () == ACE_RB_Tree_Node_Base::RED)
00842                            ? "RED" : "BLACK";
00843 
00844   ACE_DEBUG ((LM_DEBUG,  ACE_LIB_TEXT (" color=[%s]\n"), color_str));
00845 }
00846 
00847 /// Tests the red-black invariant(s) throughout the whole tree.
00848 
00849 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>  int
00850 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::test_invariant (void)
00851 {
00852   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::test_invariant");
00853   ACE_READ_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);
00854 
00855   // Recurse from the root, starting with the measured black height at
00856   // 0, and the expected black height at -1, which will cause the
00857   // count from first measured path to a leaf to be used as the
00858   // expected one from that point onward (the key is to check
00859   // consistency).
00860   int expected_black_height = -1;
00861   if (this->test_invariant_recurse (this->root_, expected_black_height, 0) == 0)
00862     {
00863       ACE_DEBUG ((LM_DEBUG, ACE_LIB_TEXT ("invariant holds\n")));
00864       return 0;
00865     }
00866 
00867   return -1;
00868 }
00869 
00870 /// Recursive function to test the red-black invariant(s) at all nodes in a subtree.
00871 
00872 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>  int
00873 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::test_invariant_recurse (ACE_RB_Tree_Node<EXT_ID, INT_ID> *x,
00874                                                                              int & expected_black_height,
00875                                                                              int measured_black_height)
00876 {
00877   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::test_invariant_recurse");
00878 
00879   if (!x)
00880     {
00881       // Count each leaf (zero pointer) as a black node (per CLR algorithm description).
00882       ++measured_black_height;
00883 
00884       if (expected_black_height == -1)
00885         {
00886           expected_black_height = measured_black_height;
00887         }
00888       else if (expected_black_height != measured_black_height)
00889         {
00890           ACE_ERROR_RETURN ((LM_ERROR,
00891                              ACE_LIB_TEXT ("\nexpected_black_height = %d but ")
00892                              ACE_LIB_TEXT ("\nmeasured_black_height = %d in ")
00893                              ACE_LIB_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::test_invariant_recurse\n"),
00894                              expected_black_height, measured_black_height),
00895                             -1);
00896         }
00897 
00898       return 0;
00899     }
00900 
00901   // Check the invariant that a red node cannot have a red child.
00902   if (x->color () == ACE_RB_Tree_Node_Base::RED)
00903     {
00904       if (x->left () && x->left ()->color () == ACE_RB_Tree_Node_Base::RED)
00905         {
00906           ACE_ERROR_RETURN ((LM_ERROR,
00907                              ACE_LIB_TEXT ("%p\n"),
00908                              ACE_LIB_TEXT ("\nRED parent has RED left child in ")
00909                              ACE_LIB_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::test_invariant_recurse\n")),
00910                             -1);
00911         }
00912 
00913       if (x->right () && x->right ()->color () == ACE_RB_Tree_Node_Base::RED)
00914         {
00915           ACE_ERROR_RETURN ((LM_ERROR,
00916                              ACE_LIB_TEXT ("%p\n"),
00917                              ACE_LIB_TEXT ("\nRED parent has RED right child in ")
00918                              ACE_LIB_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::test_invariant_recurse\n")),
00919                             -1);
00920         }
00921     }
00922   else
00923     {
00924       // Count each black node traversed.
00925       ++measured_black_height;
00926     }
00927 
00928   return (test_invariant_recurse (x->left (), expected_black_height, measured_black_height) == 0)
00929           ? test_invariant_recurse (x->right (), expected_black_height, measured_black_height)
00930           : -1;
00931 }
00932 
00933 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>  int
00934 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::remove_i (ACE_RB_Tree_Node<EXT_ID, INT_ID> *z)
00935 {
00936   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::remove_i (ACE_RB_Tree_Node<EXT_ID, INT_ID> *z)");
00937 
00938   // Delete the node and reorganize the tree to satisfy the Red-Black
00939   // properties.
00940 
00941   ACE_RB_Tree_Node<EXT_ID, INT_ID> *x;
00942   ACE_RB_Tree_Node<EXT_ID, INT_ID> *y;
00943   ACE_RB_Tree_Node<EXT_ID, INT_ID> *parent;
00944 
00945   if (z->left () && z->right ())
00946     y = RB_tree_successor (z);
00947   else
00948     y = z;
00949 
00950   if (y->left ())
00951     x = y->left ();
00952   else
00953     x = y->right ();
00954 
00955   parent = y->parent ();
00956   if (x)
00957     {
00958       x->parent (parent);
00959     }
00960 
00961   if (parent)
00962     {
00963       if (y == parent->left ())
00964         parent->left (x);
00965       else
00966         parent->right (x);
00967     }
00968   else
00969     this->root_ = x;
00970 
00971   if (y != z)
00972     {
00973       // Copy the elements of y into z.
00974       z->key () = y->key ();
00975       z->item () = y->item ();
00976     }
00977 
00978   // CLR pp. 263 says that nil nodes are implicitly colored BLACK
00979   if (!y || y->color () == ACE_RB_Tree_Node_Base::BLACK)
00980     RB_delete_fixup (x, parent);
00981 
00982   y->parent (0);
00983   y->right (0);
00984   y->left (0);
00985   delete y;
00986   --current_size_;
00987 
00988   return 0;
00989 }
00990 
00991 ACE_ALLOC_HOOK_DEFINE(ACE_RB_Tree_Iterator_Base)
00992 
00993 // Constructor.
00994 
00995 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
00996 ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Iterator_Base (const ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &tree, int set_first)
00997   : tree_ (&tree), node_ (0)
00998 {
00999   ACE_TRACE ("ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Iterator_Base (ACE_RB_Tree, int)");
01000 
01001   // Position the iterator at the first (or last) node in the tree.
01002   if (set_first)
01003     node_ = tree_->RB_tree_minimum (tree_->root_);
01004   else
01005     node_ = tree_->RB_tree_maximum (tree_->root_);
01006 }
01007 
01008 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
01009 ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Iterator_Base (const ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &tree, ACE_RB_Tree_Node<EXT_ID, INT_ID>* entry)
01010   : tree_ (&tree), node_ (0)
01011 {
01012   ACE_TRACE ("ACE_RB_Tree_Iterator_Base(const ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &tree, ACE_RB_Tree_Node<EXT_ID, INT_ID>* entry)");
01013   node_ = entry;
01014 }
01015 
01016 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
01017 ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Iterator_Base (const EXT_ID& key,ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &tree)
01018    : tree_ (&tree), node_ (0)
01019 {
01020   ACE_TRACE("ACE_RB_Tree_Iterator_Base (ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &tree, const EXT_ID& key)");
01021   ACE_RB_Tree_Node<EXT_ID, INT_ID>* entry;
01022   tree.find_i(key, entry);
01023   node_ = entry;
01024 }
01025 
01026 // Copy constructor.
01027 
01028 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
01029 ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Iterator_Base (const ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &iter)
01030   : tree_ (iter.tree_),
01031     node_ (iter.node_)
01032 {
01033   ACE_TRACE ("ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Iterator_Base (ACE_RB_Tree_Iterator_Base)");
01034 }
01035 
01036 // Assignment operator.
01037 
01038 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> void
01039 ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator= (const ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &iter)
01040 {
01041   ACE_TRACE ("ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator=");
01042   if (this != &iter)
01043     {
01044       tree_ = iter.tree_;
01045       node_ = iter.node_;
01046     }
01047 }
01048 
01049 // Destructor.
01050 
01051 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
01052 ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::~ACE_RB_Tree_Iterator_Base ()
01053 {
01054   ACE_TRACE ("ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::~ACE_RB_Tree_Iterator_Base");
01055 }
01056 
01057 ACE_ALLOC_HOOK_DEFINE(ACE_RB_Tree_Iterator)
01058 
01059 // Constructor.
01060 
01061 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
01062 ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Iterator (const ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &tree,
01063      int set_first)
01064   : ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> (tree, set_first)
01065 {
01066   ACE_TRACE ("ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Iterator");
01067 }
01068 
01069 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
01070 ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Iterator (const ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &tree,
01071      ACE_RB_Tree_Node<EXT_ID, INT_ID>* entry)
01072   : ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> (tree,entry)
01073 {
01074   ACE_TRACE ("ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Iterator");
01075 }
01076 
01077 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
01078 ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Iterator (const EXT_ID& key,ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &tree)
01079   : ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>(key,tree)
01080 {
01081   ACE_TRACE ("ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Iterator");
01082 }
01083 
01084 // Destructor.
01085 
01086 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
01087 ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::~ACE_RB_Tree_Iterator ()
01088 {
01089   ACE_TRACE ("ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::~ACE_RB_Tree_Iterator");
01090 }
01091 
01092 ACE_ALLOC_HOOK_DEFINE(ACE_RB_Tree_Reverse_Iterator)
01093 
01094 // Constructor.
01095 
01096 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
01097 ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Reverse_Iterator (const ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &tree, int set_last)
01098   : ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> (tree, set_last ? 0 : 1)
01099 {
01100   ACE_TRACE ("ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Reverse_Iterator");
01101 }
01102 
01103 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
01104 ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Reverse_Iterator (const ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &tree, ACE_RB_Tree_Node<EXT_ID, INT_ID>* entry) 
01105   : ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> (tree,entry)
01106 {
01107   ACE_TRACE ("ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Reverse_Iterator");
01108 }
01109 
01110 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
01111 ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Reverse_Iterator (const EXT_ID& key,ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &tree)
01112  : ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>(key,tree)
01113 {
01114   ACE_TRACE ("ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Reverse_Iterator");
01115 }
01116 
01117 // Destructor.
01118 
01119 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
01120 ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::~ACE_RB_Tree_Reverse_Iterator ()
01121 {
01122   ACE_TRACE ("ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::~ACE_RB_Tree_Reverse_Iterator");
01123 }
01124 
01125 
01126 #endif /* !defined (ACE_RB_TREE_C) */

Generated on Mon Jun 16 11:20:57 2003 for ACE by doxygen1.2.14 written by Dimitri van Heesch, © 1997-2002