dep/ACE_wrappers/ace/RB_Tree.cpp

   1 // $Id: RB_Tree.cpp 81768 2008-05-23 12:45:54Z sma $
   2
   3 #ifndef ACE_RB_TREE_CPP
   4 #define ACE_RB_TREE_CPP
   5
   6 #include "ace/Global_Macros.h"
   7 #include "ace/RB_Tree.h"
   8 #include "ace/SString.h"
   9
  10 #if !defined (ACE_LACKS_PRAGMA_ONCE)
  11 # pragma once
  12 #endif /* ACE_LACKS_PRAGMA_ONCE */
  13
  14 #if !defined (__ACE_INLINE__)
  15 #include "ace/RB_Tree.inl"
  16 #endif /* __ACE_INLINE__ */
  17
  18 #include "ace/Log_Msg.h"
  19
  20 ACE_BEGIN_VERSIONED_NAMESPACE_DECL
  21
  22 // Constructor.
  23
  24 template <class EXT_ID, class INT_ID>
  25 ACE_RB_Tree_Node<EXT_ID, INT_ID>::ACE_RB_Tree_Node (const EXT_ID &k, const INT_ID &t)
  26   : k_ (k),
  27     t_ (t),
  28     color_ (RED),
  29     parent_ (0),
  30     left_ (0),
  31     right_ (0)
  32 {
  33   ACE_TRACE ("ACE_RB_Tree_Node<EXT_ID, INT_ID>::ACE_RB_Tree_Node (const EXT_ID &k, const INT_ID &t)");
  34 }
  35
  36
  37 // Destructor.
  38
  39 template <class EXT_ID, class INT_ID>
  40 ACE_RB_Tree_Node<EXT_ID, INT_ID>::~ACE_RB_Tree_Node (void)
  41 {
  42   ACE_TRACE ("ACE_RB_Tree_Node<EXT_ID, INT_ID>::~ACE_RB_Tree_Node");
  43 }
  44
  45 // Constructor.
  46
  47 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
  48 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree (ACE_Allocator *alloc)
  49   : root_ (0),
  50     current_size_ (0)
  51 {
  52   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::"
  53              "ACE_RB_Tree (ACE_Allocator *alloc)");
  54   allocator_ = alloc;
  55   if (this->open (alloc) == -1)
  56     ACE_ERROR ((LM_ERROR,
  57                 ACE_TEXT ("ACE_RB_Tree::ACE_RB_Tree\n")));
  58 }
  59
  60 // Copy constructor.
  61
  62 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
  63 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)
  64   : root_ (0),
  65     current_size_ (0)
  66 {
  67   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::"
  68              "ACE_RB_Tree (const ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &rbt)");
  69   ACE_WRITE_GUARD (ACE_LOCK, ace_mon, this->lock_);
  70   allocator_ = rbt.allocator_;
  71
  72   // Make a deep copy of the passed tree.
  73   ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> iter(rbt);
  74
  75   for (iter.first ();
  76
  77        iter.is_done () == 0; iter.next ())
  78     insert_i (*(iter.key ()),
  79               *(iter.item ()));
  80 }
  81
  82 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
  83 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree (
  84     void *location,
  85     ACE_Allocator *alloc
  86 )
  87 {
  88   if (location != this)
  89     {
  90       this->root_ = 0;
  91       this->current_size_ = 0;
  92     }
  93
  94   this->allocator_ = alloc;
  95 }
  96 // Destructor.
  97
  98 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
  99 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::~ACE_RB_Tree ()
 100 {
 101   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::~ACE_RB_Tree");
 102
 103   // Use the locked public method, to be totally safe, as the class
 104   // can be used with an allocator and placement new.
 105   this->close ();
 106 }
 107
 108 // Assignment operator.
 109
 110 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> void
 111 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)
 112 {
 113   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator =");
 114   ACE_WRITE_GUARD (ACE_LOCK, ace_mon, this->lock_);
 115
 116   if (this != &rbt)
 117     {
 118       // Clear out the existing tree.
 119       close_i ();
 120
 121       // Make a deep copy of the passed tree.
 122       ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> iter(rbt);
 123
 124       for (iter.first ();
 125            iter.is_done () == 0;
 126            iter.next ())
 127         insert_i (*(iter.key ()),
 128                   *(iter.item ()));
 129
 130       // Use the same allocator as the rhs.
 131       allocator_ = rbt.allocator_;
 132     }
 133 }
 134 // Less than comparison function for keys, default functor
 135 // implementation returns 1 if k1 < k2, 0 otherwise.
 136
 137 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> int
 138 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::lessthan (const EXT_ID &k1, const EXT_ID &k2)
 139 {
 140   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::lessthan");
 141   return this->compare_keys_ (k1, k2);
 142 }
 143
 144 // Method for right rotation of the tree about a given node.
 145
 146 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>  void
 147 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_rotate_right (ACE_RB_Tree_Node<EXT_ID, INT_ID> *x)
 148 {
 149   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_rotate_right");
 150
 151   if (!x)
 152     ACE_ERROR ((LM_ERROR,
 153                 ACE_TEXT ("%p\n"),
 154                 ACE_TEXT ("\nerror: x is a null pointer in ")
 155                 ACE_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::RB_rotate_right\n")));
 156   else if (! (x->left()))
 157     ACE_ERROR ((LM_ERROR,
 158                 ACE_TEXT ("%p\n"),
 159                 ACE_TEXT ("\nerror: x->left () is a null pointer in ")
 160                 ACE_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::RB_rotate_right\n")));
 161   else
 162     {
 163       ACE_RB_Tree_Node<EXT_ID, INT_ID> * y;
 164       y = x->left ();
 165       x->left (y->right ());
 166       if (y->right ())
 167         y->right ()->parent (x);
 168       y->parent (x->parent ());
 169       if (x->parent ())
 170         {
 171           if (x == x->parent ()->right ())
 172             x->parent ()->right (y);
 173           else
 174             x->parent ()->left (y);
 175         }
 176       else
 177         root_ = y;
 178       y->right (x);
 179       x->parent (y);
 180     }
 181 }
 182
 183 // Method for left rotation of the tree about a given node.
 184
 185 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> void
 186 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_rotate_left (ACE_RB_Tree_Node<EXT_ID, INT_ID> * x)
 187 {
 188   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_rotate_left");
 189
 190   if (! x)
 191     ACE_ERROR ((LM_ERROR,
 192                 ACE_TEXT ("%p\n"),
 193                 ACE_TEXT ("\nerror: x is a null pointer in ")
 194                 ACE_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::RB_rotate_left\n")));
 195   else if (! (x->right()))
 196     ACE_ERROR ((LM_ERROR,
 197                 ACE_TEXT ("%p\n"),
 198                 ACE_TEXT ("\nerror: x->right () is a null pointer ")
 199                 ACE_TEXT ("in ACE_RB_Tree<EXT_ID, INT_ID>::RB_rotate_left\n")));
 200   else
 201     {
 202       ACE_RB_Tree_Node<EXT_ID, INT_ID> * y;
 203       y = x->right ();
 204       x->right (y->left ());
 205       if (y->left ())
 206         y->left ()->parent (x);
 207       y->parent (x->parent ());
 208       if (x->parent ())
 209         {
 210           if (x == x->parent ()->left ())
 211             x->parent ()->left (y);
 212           else
 213             x->parent ()->right (y);
 214         }
 215       else
 216         root_ = y;
 217       y->left (x);
 218       x->parent (y);
 219     }
 220 }
 221
 222 // Method for restoring Red-Black properties after a specific deletion case.
 223
 224 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>  void
 225 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::
 226 RB_delete_fixup (ACE_RB_Tree_Node<EXT_ID, INT_ID> *x,
 227                  ACE_RB_Tree_Node<EXT_ID, INT_ID> *parent)
 228 {
 229   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_delete_fixup");
 230
 231   while (x != this->root_
 232          && (!x
 233              || x->color () == ACE_RB_Tree_Node_Base::BLACK))
 234     {
 235       if (x == parent->left ())
 236         {
 237           ACE_RB_Tree_Node<EXT_ID, INT_ID> *w = parent->right ();
 238           if (w && w->color () == ACE_RB_Tree_Node_Base::RED)
 239             {
 240               w->color (ACE_RB_Tree_Node_Base::BLACK);
 241               parent->color (ACE_RB_Tree_Node_Base::RED);
 242               RB_rotate_left (parent);
 243               w = parent->right ();
 244             }
 245           // CLR pp. 263 says that nil nodes are implicitly colored BLACK
 246           if (w
 247               && (!w->left ()
 248                   || w->left ()->color () == ACE_RB_Tree_Node_Base::BLACK)
 249               && (!w->right ()
 250                   || w->right ()->color () == ACE_RB_Tree_Node_Base::BLACK))
 251             {
 252               w->color (ACE_RB_Tree_Node_Base::RED);
 253               x = parent;
 254               parent = x->parent ();
 255             }
 256           else
 257             {
 258               // CLR pp. 263 says that nil nodes are implicitly colored BLACK
 259               if (w
 260                   && (!w->right ()
 261                       || w->right ()->color () == ACE_RB_Tree_Node_Base::BLACK))
 262                 {
 263                   if (w->left ())
 264                     w->left ()->color (ACE_RB_Tree_Node_Base::BLACK);
 265                   w->color (ACE_RB_Tree_Node_Base::RED);
 266                   RB_rotate_right (w);
 267                   w = parent->right ();
 268                 }
 269               if (w)
 270                 {
 271                   w->color (parent->color ());
 272                   if (w->right ())
 273                     w->right ()->color (ACE_RB_Tree_Node_Base::BLACK);
 274                 }
 275               parent->color (ACE_RB_Tree_Node_Base::BLACK);
 276               RB_rotate_left (parent);
 277               x = root_;
 278             }
 279         }
 280       else
 281         {
 282           ACE_RB_Tree_Node<EXT_ID, INT_ID> *w = parent->left ();
 283           if (w && w->color () == ACE_RB_Tree_Node_Base::RED)
 284             {
 285               w->color (ACE_RB_Tree_Node_Base::BLACK);
 286               parent->color (ACE_RB_Tree_Node_Base::RED);
 287               RB_rotate_right (parent);
 288               w = parent->left ();
 289             }
 290           // CLR pp. 263 says that nil nodes are implicitly colored BLACK
 291           if (w
 292               && (!w->left ()
 293                   || w->left ()->color () == ACE_RB_Tree_Node_Base::BLACK)
 294               && (!w->right ()
 295                   || w->right ()->color () == ACE_RB_Tree_Node_Base::BLACK))
 296             {
 297               w->color (ACE_RB_Tree_Node_Base::RED);
 298               x = parent;
 299               parent = x->parent ();
 300             }
 301           else
 302             {
 303               // CLR pp. 263 says that nil nodes are implicitly colored BLACK
 304               if (w
 305                   && (!w->left ()
 306                       || w->left ()->color () == ACE_RB_Tree_Node_Base::BLACK))
 307                 {
 308                   w->color (ACE_RB_Tree_Node_Base::RED);
 309                   if (w->right ())
 310                     w->right ()->color (ACE_RB_Tree_Node_Base::BLACK);
 311                   RB_rotate_left (w);
 312                   w = parent->left ();
 313                 }
 314               if (w)
 315                 {
 316                   w->color (parent->color ());
 317                   if (w->left ())
 318                     w->left ()->color (ACE_RB_Tree_Node_Base::BLACK);
 319                 }
 320               parent->color (ACE_RB_Tree_Node_Base::BLACK);
 321               RB_rotate_right (parent);
 322               x = root_;
 323             }
 324         }
 325     }
 326
 327   if (x)
 328     x->color (ACE_RB_Tree_Node_Base::BLACK);
 329 }
 330
 331 // Return a pointer to a matching node if there is one, a pointer to
 332 // the node under which to insert the item if the tree is not empty
 333 // and there is no such match, or 0 if the tree is empty.
 334
 335 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> ACE_RB_Tree_Node<EXT_ID, INT_ID> *
 336 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::find_node (const EXT_ID &k, ACE_RB_Tree_Base::RB_SearchResult &result)
 337 {
 338   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::find_node");
 339
 340   // Start at the root.
 341   ACE_RB_Tree_Node<EXT_ID, INT_ID> *current = root_;
 342
 343   while (current)
 344     {
 345       // While there are more nodes to examine.
 346       if (this->lessthan (current->key (), k))
 347         {
 348           // If the search key is greater than the current node's key.
 349           if (current->right ())
 350             // If the right subtree is not empty, search to the right.
 351             current = current->right ();
 352           else
 353             {
 354               // If the right subtree is empty, we're done searching,
 355               // and are positioned to the left of the insertion point.
 356               result = LEFT;
 357               break;
 358             }
 359         }
 360       else if (this->lessthan (k, current->key ()))
 361         {
 362           // Else if the search key is less than the current node's key.
 363           if (current->left ())
 364             // If the left subtree is not empty, search to the left.
 365             current = current->left ();
 366           else
 367             {
 368               // If the left subtree is empty, we're done searching,
 369               // and are positioned to the right of the insertion point.
 370               result = RIGHT;
 371               break;
 372             }
 373         }
 374       else
 375         {
 376           // If the keys match exactly, we're done as well.
 377           result = EXACT;
 378           break;
 379         }
 380     }
 381
 382   return current;
 383 }
 384
 385 // Rebalance the tree after insertion of a node.
 386
 387 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> void
 388 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_rebalance (ACE_RB_Tree_Node<EXT_ID, INT_ID> * x)
 389 {
 390   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_rebalance");
 391
 392   ACE_RB_Tree_Node<EXT_ID, INT_ID> *y = 0;
 393
 394   while (x &&
 395          x->parent ()
 396          && x->parent ()->color () == ACE_RB_Tree_Node_Base::RED)
 397     {
 398       if (! x->parent ()->parent ())
 399         {
 400           // If we got here, something is drastically wrong!
 401           ACE_ERROR ((LM_ERROR,
 402                       ACE_TEXT ("%p\n"),
 403                       ACE_TEXT ("\nerror: parent's parent is null in ")
 404                       ACE_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::RB_rebalance\n")));
 405           return;
 406         }
 407
 408       if (x->parent () == x->parent ()->parent ()->left ())
 409         {
 410           y = x->parent ()->parent ()->right ();
 411           if (y && y->color () == ACE_RB_Tree_Node_Base::RED)
 412             {
 413               // Handle case 1 (see CLR book, pp. 269).
 414               x->parent ()->color (ACE_RB_Tree_Node_Base::BLACK);
 415               y->color (ACE_RB_Tree_Node_Base::BLACK);
 416               x->parent ()->parent ()->color (ACE_RB_Tree_Node_Base::RED);
 417               x = x->parent ()->parent ();
 418             }
 419           else
 420             {
 421               if (x == x->parent ()->right ())
 422                 {
 423                   // Transform case 2 into case 3 (see CLR book, pp. 269).
 424                   x = x->parent ();
 425                   RB_rotate_left (x);
 426                 }
 427
 428               // Handle case 3 (see CLR book, pp. 269).
 429               x->parent ()->color (ACE_RB_Tree_Node_Base::BLACK);
 430               x->parent ()->parent ()->color (ACE_RB_Tree_Node_Base::RED);
 431               RB_rotate_right (x->parent ()->parent ());
 432             }
 433         }
 434       else
 435         {
 436           y = x->parent ()->parent ()->left ();
 437           if (y && y->color () == ACE_RB_Tree_Node_Base::RED)
 438             {
 439               // Handle case 1 (see CLR book, pp. 269).
 440               x->parent ()->color (ACE_RB_Tree_Node_Base::BLACK);
 441               y->color (ACE_RB_Tree_Node_Base::BLACK);
 442               x->parent ()->parent ()->color (ACE_RB_Tree_Node_Base::RED);
 443               x = x->parent ()->parent ();
 444             }
 445           else
 446             {
 447               if (x == x->parent ()->left ())
 448                 {
 449                   // Transform case 2 into case 3 (see CLR book, pp. 269).
 450                   x = x->parent ();
 451                   RB_rotate_right (x);
 452                 }
 453
 454               // Handle case 3 (see CLR book, pp. 269).
 455               x->parent ()->color (ACE_RB_Tree_Node_Base::BLACK);
 456               x->parent ()->parent ()->color (ACE_RB_Tree_Node_Base::RED);
 457               RB_rotate_left (x->parent ()->parent ());
 458             }
 459         }
 460     }
 461 }
 462
 463 // Method to find the successor node of the given node in the tree.
 464
 465 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> ACE_RB_Tree_Node<EXT_ID, INT_ID> *
 466 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_tree_successor (ACE_RB_Tree_Node<EXT_ID, INT_ID> *x) const
 467 {
 468   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_tree_successor");
 469
 470   if (x == 0)
 471     return 0;
 472
 473   if (x->right ())
 474     return RB_tree_minimum (x->right ());
 475
 476   ACE_RB_Tree_Node<EXT_ID, INT_ID> *y = x->parent ();
 477   while ((y) && (x == y->right ()))
 478     {
 479       x = y;
 480       y = y->parent ();
 481     }
 482
 483   return y;
 484 }
 485
 486 // Method to find the predecessor node of the given node in the tree.
 487
 488 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> ACE_RB_Tree_Node<EXT_ID, INT_ID> *
 489 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_tree_predecessor (ACE_RB_Tree_Node<EXT_ID, INT_ID> *x) const
 490 {
 491   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_tree_predecessor");
 492   if (x == 0)
 493     return 0;
 494
 495   if (x->left ())
 496     return RB_tree_maximum (x->left ());
 497
 498   ACE_RB_Tree_Node<EXT_ID, INT_ID> *y = x->parent ();
 499
 500   while ((y) && (x == y->left ()))
 501     {
 502       x = y;
 503       y = y->parent ();
 504     }
 505
 506   return y;
 507 }
 508
 509 // Method to find the minimum node of the subtree rooted at the given node.
 510
 511 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> ACE_RB_Tree_Node<EXT_ID, INT_ID> *
 512 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_tree_minimum (ACE_RB_Tree_Node<EXT_ID, INT_ID> *x) const
 513 {
 514   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_tree_minimum");
 515
 516   while ((x) && (x->left ()))
 517     x = x->left ();
 518
 519   return x;
 520 }
 521
 522 // Method to find the maximum node of the subtree rooted at the given node.
 523
 524 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> ACE_RB_Tree_Node<EXT_ID, INT_ID> *
 525 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_tree_maximum (ACE_RB_Tree_Node<EXT_ID, INT_ID> *x) const
 526 {
 527   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_tree_maximum");
 528
 529   while ((x) && (x->right ()))
 530     x = x->right ();
 531
 532   return x;
 533 }
 534
 535 // Delete children (left and right) of the node. Must be called with
 536 // lock held.
 537 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 538 void ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::delete_children_i
 539   (ACE_RB_Tree_Node<EXT_ID, INT_ID> *parent)
 540 {
 541   if (parent)
 542     {
 543       this->delete_children_i (parent->left ());
 544       this->delete_children_i (parent->right ());
 545       ACE_DES_FREE_TEMPLATE2
 546         (parent->left (),
 547          this->allocator_->free,
 548          ACE_RB_Tree_Node,
 549          EXT_ID, INT_ID);
 550       ACE_DES_FREE_TEMPLATE2
 551         (parent->right (),
 552          this->allocator_->free,
 553          ACE_RB_Tree_Node,
 554          EXT_ID, INT_ID);
 555       parent->left (0);
 556       parent->right (0);
 557     }
 558   return;
 559 }
 560
 561 // Close down an RB_Tree.  this method should only be called with
 562 // locks already held.
 563
 564 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> int
 565 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::close_i ()
 566 {
 567   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::close_i");
 568
 569   this->delete_children_i (this->root_);
 570   ACE_DES_FREE_TEMPLATE2 (this->root_,
 571                           this->allocator()->free,
 572                           ACE_RB_Tree_Node,
 573                           EXT_ID, INT_ID);
 574   this->current_size_ = 0;
 575   this->root_ = 0;
 576   return 0;
 577 }
 578
 579 // Returns a pointer to the item corresponding to the given key, or 0
 580 // if it cannot find the key in the tree.  This method should only be
 581 // called with locks already held.
 582
 583 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> int
 584 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::find_i (const EXT_ID &k,
 585                                                              ACE_RB_Tree_Node<EXT_ID, INT_ID>* &entry, int find_exact)
 586 {
 587   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::find_i");
 588
 589   // Try to find a match.
 590   RB_SearchResult result = LEFT;
 591   ACE_RB_Tree_Node<EXT_ID, INT_ID> *current = find_node (k, result);
 592
 593   if (current)
 594     {
 595       // Found a match
 596       if (!find_exact || result == EXACT)
 597         entry = current;  // Assign the entry for any match.
 598       return (result == EXACT ? 0 : -1);
 599     }
 600   else
 601     // The node is not there.
 602     return -1;
 603 }
 604
 605 // Inserts a *copy* of the key and the item into the tree: both the
 606 // key type EXT_ID and the item type INT_ID must have well defined
 607 // semantics for copy construction and < comparison.  This method
 608 // returns a pointer to the inserted item copy, or 0 if an error
 609 // occurred.  NOTE: if an identical key already exists in the tree, no
 610 // new item is created, and the returned pointer addresses the
 611 // existing item associated with the existing key.  This method should
 612 // only be called with locks already held.
 613
 614 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> INT_ID *
 615 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::insert_i (const EXT_ID &k, const INT_ID &t)
 616 {
 617   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::insert_i (const EXT_ID &k, const INT_ID &t)");
 618
 619   // Find the closest matching node, if there is one.
 620   RB_SearchResult result = LEFT;
 621   ACE_RB_Tree_Node<EXT_ID, INT_ID> *current = find_node (k, result);
 622   if (current)
 623     {
 624       // If the keys match, just return a pointer to the node's item.
 625       if (result == EXACT)
 626         return &current->item ();
 627
 628       // Otherwise if we're to the left of the insertion point, insert
 629       // into the right subtree.
 630       else if (result == LEFT)
 631         {
 632           if (current->right ())
 633             {
 634               // If there is already a right subtree, complain.
 635               ACE_ERROR_RETURN ((LM_ERROR,
 636                                  ACE_TEXT ("%p\n"),
 637                                  ACE_TEXT ("\nright subtree already present in ")
 638                                  ACE_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::insert_i\n")),
 639                                 0);
 640             }
 641           else
 642             {
 643               // The right subtree is empty: insert new node there.
 644               ACE_RB_Tree_Node<EXT_ID, INT_ID> *tmp = 0;
 645
 646               ACE_NEW_MALLOC_RETURN
 647                 (tmp,
 648                  (reinterpret_cast<ACE_RB_Tree_Node<EXT_ID, INT_ID>*>
 649                    (this->allocator_->malloc (sizeof (*tmp)))),
 650                  (ACE_RB_Tree_Node<EXT_ID, INT_ID>) (k, t),
 651                  0);
 652               current->right (tmp);
 653
 654               // If the node was successfully inserted, set its
 655               // parent, rebalance the tree, color the root black, and
 656               // return a pointer to the inserted item.
 657               INT_ID *item = &(current->right ()->item ());
 658               current->right ()->parent (current);
 659               RB_rebalance (current->right ());
 660               root_->color (ACE_RB_Tree_Node_Base::BLACK);
 661               ++current_size_;
 662               return item;
 663             }
 664         }
 665       // Otherwise, we're to the right of the insertion point, so
 666       // insert into the left subtree.
 667       else // (result == RIGHT)
 668         {
 669           if (current->left ())
 670             // If there is already a left subtree, complain.
 671             ACE_ERROR_RETURN ((LM_ERROR,
 672                                ACE_TEXT ("%p\n"),
 673                                ACE_TEXT ("\nleft subtree already present in ")
 674                                ACE_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::insert_i\n")),
 675                               0);
 676           else
 677             {
 678               // The left subtree is empty: insert new node there.
 679               ACE_RB_Tree_Node<EXT_ID, INT_ID> *tmp = 0;
 680               ACE_NEW_MALLOC_RETURN
 681                 (tmp,
 682                  (reinterpret_cast<ACE_RB_Tree_Node<EXT_ID, INT_ID>*>
 683                    (this->allocator_->malloc (sizeof (*tmp)))),
 684                  (ACE_RB_Tree_Node<EXT_ID, INT_ID>) (k, t),
 685                  0);
 686               current->left (tmp);
 687
 688               // If the node was successfully inserted, set its
 689               // parent, rebalance the tree, color the root black, and
 690               // return a pointer to the inserted item.
 691               INT_ID *item = &current->left ()->item ();
 692               current->left ()->parent (current);
 693               RB_rebalance (current->left ());
 694               root_->color (ACE_RB_Tree_Node_Base::BLACK);
 695               ++current_size_;
 696               return item;
 697             }
 698         }
 699     }
 700   else
 701     {
 702       // The tree is empty: insert at the root and color the root
 703       // black.
 704       ACE_NEW_MALLOC_RETURN
 705         (this->root_,
 706          (reinterpret_cast<ACE_RB_Tree_Node<EXT_ID, INT_ID>*>
 707            (this->allocator_->malloc (sizeof (ACE_RB_Tree_Node<EXT_ID, INT_ID>)))),
 708          (ACE_RB_Tree_Node<EXT_ID, INT_ID>) (k, t),
 709          0);
 710       this->root_->color (ACE_RB_Tree_Node_Base::BLACK);
 711       ++current_size_;
 712       return &this->root_->item ();
 713     }
 714 }
 715
 716 // Inserts a *copy* of the key and the item into the tree: both the
 717 // key type EXT_ID and the item type INT_ID must have well defined
 718 // semantics for copy construction.  The default implementation also
 719 // requires that the key type support well defined < semantics.  This
 720 // method passes back a pointer to the inserted (or existing) node,
 721 // and the search status.  If the node already exists, the method
 722 // returns 1.  If the node does not exist, and a new one is
 723 // successfully created, and the method returns 0.  If there was an
 724 // error, the method returns -1.
 725
 726 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> int
 727 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::insert_i (const EXT_ID &k,
 728                                                                const INT_ID &t,
 729                                                                ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry)
 730 {
 731   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::insert_i (const EXT_ID &k, const INT_ID &t, "
 732              "ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry)");
 733
 734   // Find the closest matching node, if there is one.
 735   RB_SearchResult result = LEFT;
 736   ACE_RB_Tree_Node<EXT_ID, INT_ID> *current = find_node (k, result);
 737   if (current)
 738     {
 739       // If the keys match, just return a pointer to the node's item.
 740       if (result == EXACT)
 741         {
 742           entry = current;
 743           return 1;
 744         }
 745       // Otherwise if we're to the left of the insertion
 746       // point, insert into the right subtree.
 747       else if (result == LEFT)
 748         {
 749           if (current->right ())
 750             {
 751               // If there is already a right subtree, complain.
 752               ACE_ERROR_RETURN ((LM_ERROR,
 753                                  ACE_TEXT ("%p\n"),
 754                                  ACE_TEXT ("\nright subtree already present in ")
 755                                  ACE_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::insert_i\n")),
 756                                 -1);
 757             }
 758           else
 759             {
 760               // The right subtree is empty: insert new node there.
 761               ACE_RB_Tree_Node<EXT_ID, INT_ID> *tmp = 0;
 762               ACE_NEW_MALLOC_RETURN
 763                 (tmp,
 764                  (reinterpret_cast<ACE_RB_Tree_Node<EXT_ID, INT_ID>*>
 765                    (this->allocator_->malloc (sizeof (*tmp)))),
 766                  (ACE_RB_Tree_Node<EXT_ID, INT_ID>) (k, t),
 767                  -1);
 768               current->right (tmp);
 769
 770               // If the node was successfully inserted, set its parent, rebalance
 771               // the tree, color the root black, and return a pointer to the
 772               // inserted item.
 773               entry = current->right ();
 774               current->right ()->parent (current);
 775               RB_rebalance (current->right ());
 776               this->root_->color (ACE_RB_Tree_Node_Base::BLACK);
 777               ++this->current_size_;
 778               return 0;
 779             }
 780         }
 781       // Otherwise, we're to the right of the insertion point, so
 782       // insert into the left subtree.
 783       else // (result == RIGHT)
 784         {
 785           if (current->left ())
 786             // If there is already a left subtree, complain.
 787             ACE_ERROR_RETURN ((LM_ERROR,
 788                                ACE_TEXT ("%p\n"),
 789                                ACE_TEXT ("\nleft subtree already present in ")
 790                                ACE_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::insert_i\n")),
 791                               -1);
 792           else
 793             {
 794               // The left subtree is empty: insert new node there.
 795               ACE_RB_Tree_Node<EXT_ID, INT_ID> *tmp = 0;
 796               ACE_NEW_MALLOC_RETURN
 797                 (tmp,
 798                  (reinterpret_cast<ACE_RB_Tree_Node<EXT_ID, INT_ID>*>
 799                    (this->allocator_->malloc (sizeof (*tmp)))),
 800                  (ACE_RB_Tree_Node<EXT_ID, INT_ID>) (k, t),
 801                  -1);
 802               current->left (tmp);
 803               // If the node was successfully inserted, set its
 804               // parent, rebalance the tree, color the root black, and
 805               // return a pointer to the inserted item.
 806               entry = current->left ();
 807               current->left ()->parent (current);
 808               RB_rebalance (current->left ());
 809               this->root_->color (ACE_RB_Tree_Node_Base::BLACK);
 810               ++this->current_size_;
 811               return 0;
 812             }
 813         }
 814     }
 815   else
 816     {
 817       // The tree is empty: insert at the root and color the root black.
 818       ACE_NEW_MALLOC_RETURN
 819         (this->root_,
 820          (reinterpret_cast<ACE_RB_Tree_Node<EXT_ID, INT_ID>*>
 821            (this->allocator_->malloc (sizeof (ACE_RB_Tree_Node<EXT_ID, INT_ID>)))),
 822          (ACE_RB_Tree_Node<EXT_ID, INT_ID>) (k, t),
 823          -1);
 824       this->root_->color (ACE_RB_Tree_Node_Base::BLACK);
 825       ++this->current_size_;
 826       entry = this->root_;
 827       return 0;
 828     }
 829 }
 830
 831 // Removes the item associated with the given key from the tree and
 832 // destroys it.  Returns 1 if it found the item and successfully
 833 // destroyed it, 0 if it did not find the item, or -1 if an error
 834 // occurred.  This method should only be called with locks already
 835 // held.
 836
 837 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>  int
 838 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::remove_i (const EXT_ID &k, INT_ID &i)
 839 {
 840   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::remove_i (const EXT_ID &k, INT_ID &i)");
 841
 842   // Find a matching node, if there is one.
 843   ACE_RB_Tree_Node<EXT_ID, INT_ID> *z;
 844   RB_SearchResult result = LEFT;
 845   z = find_node (k, result);
 846
 847   // If there is a matching node: remove and destroy it.
 848   if (z && result == EXACT)
 849     {
 850       // Return the internal id stored in the deleted node.
 851       i = z->item ();
 852       return -1 == this->remove_i (z) ? -1 : 1;
 853     }
 854
 855   // No matching node was found: return 0.
 856   return 0;
 857 }
 858
 859 /// Recursive function to dump the state of an object.
 860 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> void
 861 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::
 862 dump_i (ACE_RB_Tree_Node<EXT_ID, INT_ID> *node) const
 863 {
 864 #if defined (ACE_HAS_DUMP)
 865   if (node)
 866     {
 867       dump_node_i (*node);
 868
 869       ACE_DEBUG ((LM_DEBUG,  ACE_TEXT ("\ndown left\n")));
 870       this->dump_i (node->left ());
 871       ACE_DEBUG ((LM_DEBUG,  ACE_TEXT ("\nup left\n")));
 872
 873       ACE_DEBUG ((LM_DEBUG,  ACE_TEXT ("\ndown right\n")));
 874       this->dump_i (node->right ());
 875       ACE_DEBUG ((LM_DEBUG,  ACE_TEXT ("\nup right\n")));
 876     }
 877   else
 878     {
 879       ACE_DEBUG ((LM_DEBUG,  ACE_TEXT ("\nNULL POINTER (BLACK)\n")));
 880     }
 881 #else /* !ACE_HAS_DUMP */
 882   ACE_UNUSED_ARG (node);
 883 #endif /* ACE_HAS_DUMP */
 884 }
 885
 886 /// Function to dump node itself.  Does not show parameterized node contents
 887 /// in its basic form, but template specialization can be used to
 888 /// provide definitions for various EXT_ID and INT_ID types.
 889
 890 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> void
 891 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::
 892 dump_node_i (ACE_RB_Tree_Node<EXT_ID, INT_ID> &node) const
 893 {
 894 #if defined (ACE_HAS_DUMP)
 895   const char * color_str = (node.color () == ACE_RB_Tree_Node_Base::RED)
 896                            ? "RED" : "BLACK";
 897
 898   ACE_DEBUG ((LM_DEBUG,  ACE_TEXT (" color=[%s]\n"), color_str));
 899 #else /* !ACE_HAS_DUMP */
 900   ACE_UNUSED_ARG (node);
 901 #endif /* ACE_HAS_DUMP */
 902 }
 903
 904 /// Tests the red-black invariant(s) throughout the whole tree.
 905
 906 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>  int
 907 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::test_invariant (void)
 908 {
 909   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::test_invariant");
 910   ACE_READ_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);
 911
 912   // Recurse from the root, starting with the measured black height at
 913   // 0, and the expected black height at -1, which will cause the
 914   // count from first measured path to a leaf to be used as the
 915   // expected one from that point onward (the key is to check
 916   // consistency).
 917   int expected_black_height = -1;
 918   if (this->test_invariant_recurse (this->root_, expected_black_height, 0) == 0)
 919     {
 920       ACE_DEBUG ((LM_DEBUG, ACE_TEXT ("invariant holds\n")));
 921       return 0;
 922     }
 923
 924   return -1;
 925 }
 926
 927 /// Recursive function to test the red-black invariant(s) at all nodes in a subtree.
 928
 929 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>  int
 930 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::test_invariant_recurse (ACE_RB_Tree_Node<EXT_ID, INT_ID> *x,
 931                                                                              int & expected_black_height,
 932                                                                              int measured_black_height)
 933 {
 934   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::test_invariant_recurse");
 935
 936   if (!x)
 937     {
 938       // Count each leaf (zero pointer) as a black node (per CLR algorithm description).
 939       ++measured_black_height;
 940
 941       if (expected_black_height == -1)
 942         {
 943           expected_black_height = measured_black_height;
 944         }
 945       else if (expected_black_height != measured_black_height)
 946         {
 947           ACE_ERROR_RETURN ((LM_ERROR,
 948                              ACE_TEXT ("\nexpected_black_height = %d but ")
 949                              ACE_TEXT ("\nmeasured_black_height = %d in ")
 950                              ACE_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::test_invariant_recurse\n"),
 951                              expected_black_height, measured_black_height),
 952                             -1);
 953         }
 954
 955       return 0;
 956     }
 957
 958   // Check the invariant that a red node cannot have a red child.
 959   if (x->color () == ACE_RB_Tree_Node_Base::RED)
 960     {
 961       if (x->left () && x->left ()->color () == ACE_RB_Tree_Node_Base::RED)
 962         {
 963           ACE_ERROR_RETURN ((LM_ERROR,
 964                              ACE_TEXT ("%p\n"),
 965                              ACE_TEXT ("\nRED parent has RED left child in ")
 966                              ACE_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::test_invariant_recurse\n")),
 967                             -1);
 968         }
 969
 970       if (x->right () && x->right ()->color () == ACE_RB_Tree_Node_Base::RED)
 971         {
 972           ACE_ERROR_RETURN ((LM_ERROR,
 973                              ACE_TEXT ("%p\n"),
 974                              ACE_TEXT ("\nRED parent has RED right child in ")
 975                              ACE_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::test_invariant_recurse\n")),
 976                             -1);
 977         }
 978     }
 979   else
 980     {
 981       // Count each black node traversed.
 982       ++measured_black_height;
 983     }
 984
 985   return (test_invariant_recurse (x->left (), expected_black_height, measured_black_height) == 0)
 986           ? test_invariant_recurse (x->right (), expected_black_height, measured_black_height)
 987           : -1;
 988 }
 989
 990 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>  int
 991 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::remove_i (ACE_RB_Tree_Node<EXT_ID, INT_ID> *z)
 992 {
 993   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::remove_i (ACE_RB_Tree_Node<EXT_ID, INT_ID> *z)");
 994
 995   // Delete the node and reorganize the tree to satisfy the Red-Black
 996   // properties.
 997
 998   ACE_RB_Tree_Node<EXT_ID, INT_ID> *x;
 999   ACE_RB_Tree_Node<EXT_ID, INT_ID> *y;
1000   ACE_RB_Tree_Node<EXT_ID, INT_ID> *parent;
1001
1002   if (z->left () && z->right ())
1003     y = RB_tree_successor (z);
1004   else
1005     y = z;
1006
1007   if (!y)
1008     return -1;
1009
1010   if (y->left ())
1011     x = y->left ();
1012   else
1013     x = y->right ();
1014
1015   parent = y->parent ();
1016   if (x)
1017     {
1018       x->parent (parent);
1019     }
1020
1021   if (parent)
1022     {
1023       if (y == parent->left ())
1024         parent->left (x);
1025       else
1026         parent->right (x);
1027     }
1028   else
1029     this->root_ = x;
1030
1031   if (y != z)
1032     {
1033       // Replace node z with node y, since y's pointer may well be
1034       // held externally, and be linked with y's key and item.
1035       // We will end up deleting the old unlinked, node z.
1036
1037       ACE_RB_Tree_Node<EXT_ID, INT_ID> *zParent = z->parent ();
1038       ACE_RB_Tree_Node<EXT_ID, INT_ID> *zLeftChild = z->left ();
1039       ACE_RB_Tree_Node<EXT_ID, INT_ID> *zRightChild = z->right ();
1040
1041       if (zParent)
1042         {
1043           if (z == zParent->left ())
1044             {
1045               zParent->left (y);
1046             }
1047           else
1048             {
1049               zParent->right (y);
1050             }
1051         }
1052       else
1053         {
1054           this->root_ = y;
1055         }
1056       y->parent (zParent);
1057
1058       if (zLeftChild)
1059         {
1060           zLeftChild->parent (y);
1061         }
1062       y->left (zLeftChild);
1063
1064       if (zRightChild)
1065         {
1066           zRightChild->parent (y);
1067         }
1068       y->right (zRightChild);
1069
1070       if (parent == z)
1071         {
1072           parent = y;
1073         }
1074
1075       ACE_RB_Tree_Node_Base::RB_Tree_Node_Color yColor = y->color ();
1076       y->color (z->color ());
1077       z->color (yColor);
1078
1079       //Reassign the y pointer to z because the node that y points to will be
1080       //deleted
1081       y = z;
1082     }
1083
1084   // CLR pp. 263 says that nil nodes are implicitly colored BLACK
1085   if (!y || y->color () == ACE_RB_Tree_Node_Base::BLACK)
1086     RB_delete_fixup (x, parent);
1087
1088   y->parent (0);
1089   y->right (0);
1090   y->left (0);
1091   ACE_DES_FREE_TEMPLATE2 (y,
1092                           this->allocator_->free,
1093                           ACE_RB_Tree_Node,
1094                           EXT_ID, INT_ID);
1095   --this->current_size_;
1096
1097   return 0;
1098 }
1099
1100 ACE_ALLOC_HOOK_DEFINE(ACE_RB_Tree_Iterator_Base)
1101
1102 // Constructor.
1103
1104 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
1105 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)
1106   : tree_ (&tree), node_ (0)
1107 {
1108   ACE_TRACE ("ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Iterator_Base (ACE_RB_Tree, int)");
1109
1110   // Position the iterator at the first (or last) node in the tree.
1111   if (set_first)
1112     node_ = tree_->RB_tree_minimum (tree_->root_);
1113   else
1114     node_ = tree_->RB_tree_maximum (tree_->root_);
1115 }
1116
1117 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
1118 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)
1119   : tree_ (&tree), node_ (0)
1120 {
1121   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)");
1122   node_ = entry;
1123 }
1124
1125 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
1126 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)
1127    : tree_ (&tree), node_ (0)
1128 {
1129   ACE_TRACE("ACE_RB_Tree_Iterator_Base (ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &tree, const EXT_ID& key)");
1130   ACE_RB_Tree_Node<EXT_ID, INT_ID>* entry = 0;
1131   tree.find_i(key, entry);
1132   node_ = entry;
1133 }
1134
1135 // Copy constructor.
1136
1137 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
1138 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)
1139   : tree_ (iter.tree_),
1140     node_ (iter.node_)
1141 {
1142   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)");
1143 }
1144
1145 // Assignment operator.
1146
1147 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> void
1148 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)
1149 {
1150   ACE_TRACE ("ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator=");
1151   if (this != &iter)
1152     {
1153       tree_ = iter.tree_;
1154       node_ = iter.node_;
1155     }
1156 }
1157
1158 // Destructor.
1159
1160 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
1161 ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::~ACE_RB_Tree_Iterator_Base ()
1162 {
1163   ACE_TRACE ("ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::~ACE_RB_Tree_Iterator_Base");
1164 }
1165
1166 // Dump the state of an object.
1167
1168 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
1169 void
1170 ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::dump_i (void) const
1171 {
1172   ACE_TRACE ("ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::dump_i");
1173
1174   ACE_DEBUG ((LM_DEBUG, ACE_BEGIN_DUMP, this));
1175   ACE_DEBUG ((LM_DEBUG,  ACE_TEXT ("\nnode_ = %x\n"), this->node_));
1176   ACE_DEBUG ((LM_DEBUG, ACE_END_DUMP));
1177 }
1178
1179
1180 ACE_ALLOC_HOOK_DEFINE(ACE_RB_Tree_Iterator)
1181
1182 // Constructor.
1183
1184 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
1185 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,
1186      int set_first)
1187   : ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> (tree, set_first)
1188 {
1189   ACE_TRACE ("ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Iterator");
1190 }
1191
1192 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
1193 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,
1194      ACE_RB_Tree_Node<EXT_ID, INT_ID>* entry)
1195   : ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> (tree,entry)
1196 {
1197   ACE_TRACE ("ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Iterator");
1198 }
1199
1200 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
1201 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)
1202   : ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>(key,tree)
1203 {
1204   ACE_TRACE ("ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Iterator");
1205 }
1206
1207 // Destructor.
1208
1209 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
1210 ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::~ACE_RB_Tree_Iterator ()
1211 {
1212   ACE_TRACE ("ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::~ACE_RB_Tree_Iterator");
1213 }
1214
1215 ACE_ALLOC_HOOK_DEFINE(ACE_RB_Tree_Reverse_Iterator)
1216
1217 // Constructor.
1218
1219 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
1220 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)
1221   : ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> (tree, set_last ? 0 : 1)
1222 {
1223   ACE_TRACE ("ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Reverse_Iterator");
1224 }
1225
1226 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
1227 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)
1228   : ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> (tree,entry)
1229 {
1230   ACE_TRACE ("ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Reverse_Iterator");
1231 }
1232
1233 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
1234 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)
1235  : ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>(key,tree)
1236 {
1237   ACE_TRACE ("ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Reverse_Iterator");
1238 }
1239
1240 // Destructor.
1241
1242 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
1243 ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::~ACE_RB_Tree_Reverse_Iterator ()
1244 {
1245   ACE_TRACE ("ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::~ACE_RB_Tree_Reverse_Iterator");
1246 }
1247
1248 ACE_END_VERSIONED_NAMESPACE_DECL
1249
1250 #endif /* !ACE_RB_TREE_CPP */