ACE/ace/RB_Tree.inl

   1 // -*- C++ -*-
   2 #include "ace/Guard_T.h"
   3 #include "ace/Malloc_Base.h"
   4 #include "ace/Log_Category.h"
   5
   6 ACE_BEGIN_VERSIONED_NAMESPACE_DECL
   7
   8 /////////////////////////////////////////////////////
   9 // template class ACE_RB_Tree_Node<EXT_ID, INT_ID> //
  10 /////////////////////////////////////////////////////
  11
  12 // Key accessor.
  13 template <class EXT_ID, class INT_ID>
  14 ACE_INLINE EXT_ID &
  15 ACE_RB_Tree_Node<EXT_ID, INT_ID>::key ()
  16 {
  17   ACE_TRACE ("ACE_RB_Tree_Node<EXT_ID, INT_ID>::key");
  18   return k_;
  19 }
  20
  21 // Item accessor.
  22 template <class EXT_ID, class INT_ID>
  23 ACE_INLINE INT_ID &
  24 ACE_RB_Tree_Node<EXT_ID, INT_ID>::item ()
  25 {
  26   ACE_TRACE ("ACE_RB_Tree_Node<EXT_ID, INT_ID>:item");
  27   return t_;
  28 }
  29
  30 // Set color of the node.
  31 template <class EXT_ID, class INT_ID>
  32 ACE_INLINE void
  33 ACE_RB_Tree_Node<EXT_ID, INT_ID>::color (ACE_RB_Tree_Node_Base::RB_Tree_Node_Color c)
  34 {
  35   ACE_TRACE ("ACE_RB_Tree_Node<EXT_ID, INT_ID>::color mutator");
  36   color_ = c;
  37 }
  38
  39 // Get color of the node.
  40 template <class EXT_ID, class INT_ID>
  41 ACE_INLINE ACE_RB_Tree_Node_Base::RB_Tree_Node_Color
  42 ACE_RB_Tree_Node<EXT_ID, INT_ID>::color ()
  43 {
  44   ACE_TRACE ("ACE_RB_Tree_Node<EXT_ID, INT_ID>::color accessor");
  45   return color_;
  46 }
  47
  48 // Accessor for node's parent pointer.
  49 template <class EXT_ID, class INT_ID>
  50 ACE_INLINE ACE_RB_Tree_Node<EXT_ID, INT_ID> *
  51 ACE_RB_Tree_Node<EXT_ID, INT_ID>::parent ()
  52 {
  53   ACE_TRACE ("ACE_RB_Tree_Node<EXT_ID, INT_ID>::parent accessor");
  54   return parent_;
  55 }
  56
  57 // Mutator for node's parent pointer.
  58 template <class EXT_ID, class INT_ID>
  59 ACE_INLINE void
  60 ACE_RB_Tree_Node<EXT_ID, INT_ID>::parent (ACE_RB_Tree_Node<EXT_ID, INT_ID> * p)
  61 {
  62   ACE_TRACE ("ACE_RB_Tree_Node<EXT_ID, INT_ID>::parent mutator");
  63   parent_ = p;
  64 }
  65
  66 // Accessor for node's left child pointer.
  67 template <class EXT_ID, class INT_ID>
  68 ACE_INLINE ACE_RB_Tree_Node<EXT_ID, INT_ID> *
  69 ACE_RB_Tree_Node<EXT_ID, INT_ID>::left ()
  70 {
  71   ACE_TRACE ("ACE_RB_Tree_Node<EXT_ID, INT_ID>::left accessor");
  72   return left_;
  73 }
  74
  75 // Mutator for node's left child pointer.
  76 template <class EXT_ID, class INT_ID>
  77 ACE_INLINE void
  78 ACE_RB_Tree_Node<EXT_ID, INT_ID>::left (ACE_RB_Tree_Node<EXT_ID, INT_ID> * l)
  79 {
  80   ACE_TRACE ("ACE_RB_Tree_Node<EXT_ID, INT_ID>::left mutator");
  81   left_ = l;
  82 }
  83
  84 // Accessor for node's right child pointer.
  85 template <class EXT_ID, class INT_ID>
  86 ACE_INLINE ACE_RB_Tree_Node<EXT_ID, INT_ID> *
  87 ACE_RB_Tree_Node<EXT_ID, INT_ID>::right ()
  88 {
  89   ACE_TRACE ("ACE_RB_Tree_Node<EXT_ID, INT_ID>::right accessor");
  90   return right_;
  91 }
  92
  93 // Mutator for node's right child pointer.
  94 template <class EXT_ID, class INT_ID>
  95 ACE_INLINE void
  96 ACE_RB_Tree_Node<EXT_ID, INT_ID>::right (ACE_RB_Tree_Node<EXT_ID, INT_ID> * r)
  97 {
  98   ACE_TRACE ("ACE_RB_Tree_Node<EXT_ID, INT_ID>::right mutator");
  99   right_ = r;
 100 }
 101
 102 ////////////////////////////////////////////////////////////////////////
 103 // template class ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> //
 104 ////////////////////////////////////////////////////////////////////////
 105
 106
 107 // Initialize an RB Tree.
 108
 109 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 110 ACE_INLINE int
 111 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::open (ACE_Allocator *alloc)
 112 {
 113   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::open");
 114   ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);
 115
 116   // Calling this->close_i () ensures we release previously allocated
 117   // memory before allocating new memory.
 118   this->close_i ();
 119
 120   // If we were passed an allocator use it,
 121   // otherwise use the default instance.
 122
 123   if (alloc == 0)
 124     alloc = ACE_Allocator::instance ();
 125
 126   this->allocator_ = alloc;
 127
 128   return 0;
 129 }
 130
 131 // Close down an RB_Tree and release dynamically allocated
 132 // resources.
 133 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 134 ACE_INLINE int
 135 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::close ()
 136 {
 137   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::close");
 138   ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);
 139
 140   return this->close_i ();
 141 }
 142
 143 // Associate <ext_id> with <int_id>.  If <ext_id> is already in the
 144 // tree then the <ACE_RB_Tree_Node> is not changed.  Returns 0 if a
 145 // new entry is bound successfully, returns 1 if an attempt is made
 146 // to bind an existing entry, and returns -1 if failures occur.
 147 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 148 ACE_INLINE int
 149 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::bind (const EXT_ID &ext_id,
 150                                                            const INT_ID &int_id)
 151 {
 152   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::bind (const EXT_ID &item, const INT_ID &int_id)");
 153   ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);
 154
 155   ACE_RB_Tree_Node<EXT_ID, INT_ID> *entry;
 156   return this->insert_i (ext_id, int_id, entry);
 157 }
 158
 159 // Same as a normal bind, except the tree entry is also passed back
 160 // to the caller.  The entry in this case will either be the newly
 161 // created entry, or the existing one.
 162 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 163 ACE_INLINE int
 164 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::bind (const EXT_ID &ext_id,
 165                                                            const INT_ID &int_id,
 166                                                            ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry)
 167 {
 168   ACE_TRACE ("ACE_RB_Tree::bind (const EXT_ID &ext_id, const INT_ID &int_id, ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry)");
 169   ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);
 170
 171   return this->insert_i (ext_id, int_id, entry);
 172 }
 173
 174 // Associate <ext_id> with <int_id> if and only if <ext_id> is not
 175 // in the tree.  If <ext_id> is already in the tree then the <int_id>
 176 // parameter is assigned the existing value in the tree.  Returns 0
 177 // if a new entry is bound successfully, returns 1 if an attempt is
 178 // made to bind an existing entry, and returns -1 if failures occur.
 179 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 180 ACE_INLINE int
 181 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::trybind (const EXT_ID &ext_id,
 182                                                               INT_ID &int_id)
 183 {
 184   ACE_TRACE ("ACE_RB_Tree::trybind (const EXT_ID &ext_id, INT_ID &int_id)");
 185   ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);
 186
 187   ACE_RB_Tree_Node<EXT_ID, INT_ID> *entry;
 188   int result = this->insert_i (ext_id, int_id, entry);
 189
 190   if (result == 1)
 191     {
 192       int_id = entry->item ();
 193     }
 194
 195   return result;
 196 }
 197
 198 // Same as a normal trybind, except the tree entry is also passed
 199 // back to the caller.  The entry in this case will either be the
 200 // newly created entry, or the existing one.
 201 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 202 ACE_INLINE int
 203 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::trybind (const EXT_ID &ext_id,
 204                                                               INT_ID &int_id,
 205                                                               ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry)
 206 {
 207   ACE_TRACE ("ACE_RB_Tree::trybind (const EXT_ID &ext_id, INT_ID &int_id, ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry)");
 208   ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);
 209
 210   int const result = this->insert_i (ext_id, int_id, entry);
 211
 212   if (result == 1)
 213     {
 214       int_id = entry->item ();
 215     }
 216
 217
 218   return result;
 219 }
 220
 221 // Reassociate <ext_id> with <int_id>.  If <ext_id> is not in the
 222 // tree then behaves just like <bind>.  Returns 0 if a new entry is
 223 // bound successfully, returns 1 if an existing entry was rebound,
 224 // and returns -1 if failures occur.
 225
 226 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 227 ACE_INLINE int
 228 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::rebind (const EXT_ID &ext_id,
 229                                                              const INT_ID &int_id)
 230 {
 231   ACE_TRACE ("ACE_RB_Tree::rebind (const EXT_ID &ext_id, const INT_ID &int_id)");
 232   ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);
 233
 234   ACE_RB_Tree_Node<EXT_ID, INT_ID> *entry;
 235   int result = this->insert_i (ext_id, int_id, entry);
 236
 237   if (result == 1)
 238     {
 239       entry->key () = ext_id;
 240       entry->item () = int_id;
 241     }
 242
 243   return result;
 244 }
 245
 246 // Same as a normal rebind, except the tree entry is also passed back
 247 // to the caller.  The entry in this case will either be the newly
 248 // created entry, or the existing one.
 249 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 250 ACE_INLINE int
 251 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::rebind (const EXT_ID &ext_id,
 252                                                              const INT_ID &int_id,
 253                                                              ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry)
 254 {
 255   ACE_TRACE ("ACE_RB_Tree::rebind (const EXT_ID &ext_id, const INT_ID &int_id, ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry)");
 256   ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);
 257
 258   int const result = this->insert_i (ext_id, int_id, entry);
 259
 260   if (result == 1)
 261     {
 262       entry->key () = ext_id;
 263       entry->item () = int_id;
 264     }
 265
 266   return result;
 267 }
 268
 269 // Associate <ext_id> with <int_id>.  If <ext_id> is not in the tree
 270 // then behaves just like <bind>.  Otherwise, store the old value of
 271 // <int_id> into the "out" parameter and rebind the new parameters.
 272 // Returns 0 if a new entry is bound successfully, returns 1 if an
 273 // existing entry was rebound, and returns -1 if failures occur.
 274
 275 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 276 ACE_INLINE int
 277 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::rebind (const EXT_ID &ext_id,
 278                                                              const INT_ID &int_id,
 279                                                              INT_ID &old_int_id)
 280 {
 281   ACE_TRACE ("ACE_RB_Tree::rebind (const EXT_ID &ext_id, const INT_ID &int_id, INT_ID &old_int_id)");
 282   ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);
 283
 284   ACE_RB_Tree_Node<EXT_ID, INT_ID> *entry;
 285   int result = this->insert_i (ext_id, int_id, entry);
 286
 287   if (result == 1)
 288     {
 289       old_int_id = entry->item ();
 290       entry->key () = ext_id;
 291       entry->item () = int_id;
 292     }
 293
 294   return result;
 295 }
 296
 297
 298 // Same as a normal rebind, except the tree entry is also passed back
 299 // to the caller.  The entry in this case will either be the newly
 300 // created entry, or the existing one.
 301
 302 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 303 ACE_INLINE int
 304 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::rebind (const EXT_ID &ext_id,
 305                                                              const INT_ID &int_id,
 306                                                              INT_ID &old_int_id,
 307                                                              ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry)
 308 {
 309   ACE_TRACE ("ACE_RB_Tree::rebind (const EXT_ID &ext_id, const INT_ID &int_id,INT_ID &old_int_id, ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry)");
 310   ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);
 311
 312   int result = this->insert_i (ext_id, int_id, entry);
 313
 314   if (result == 1)
 315     {
 316       old_int_id = entry->item ();
 317       entry->key () = ext_id;
 318       entry->item () = int_id;
 319     }
 320
 321   return result;
 322 }
 323
 324
 325 // Associate <ext_id> with <int_id>.  If <ext_id> is not in the tree
 326 // then behaves just like <bind>.  Otherwise, store the old values
 327 // of <ext_id> and <int_id> into the "out" parameters and rebind the
 328 // new parameters.  This is very useful if you need to have an
 329 // atomic way of updating <ACE_RB_Tree_Nodes> and you also need
 330 // full control over memory allocation.  Returns 0 if a new entry is
 331 // bound successfully, returns 1 if an existing entry was rebound,
 332 // and returns -1 if failures occur.
 333
 334 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 335 ACE_INLINE int
 336 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::rebind (const EXT_ID &ext_id,
 337                                                              const INT_ID &int_id,
 338                                                              EXT_ID &old_ext_id,
 339                                                              INT_ID &old_int_id)
 340 {
 341   ACE_TRACE ("ACE_RB_Tree::rebind (const EXT_ID &ext_id, const INT_ID &int_id,EXT_ID &old_ext_id, INT_ID &old_int_id)");
 342   ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);
 343
 344   ACE_RB_Tree_Node<EXT_ID, INT_ID> *entry;
 345   int result = this->insert_i (ext_id, int_id, entry);
 346
 347   if (result == 1)
 348     {
 349       old_ext_id = entry->key ();
 350       old_int_id = entry->item ();
 351       entry->key () = ext_id;
 352       entry->item () = int_id;
 353     }
 354
 355   return result;
 356 }
 357
 358
 359 // Same as a normal rebind, except the tree entry is also passed back
 360 // to the caller.  The entry in this case will either be the newly
 361 // created entry, or the existing one.
 362
 363 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 364 ACE_INLINE int
 365 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::rebind (const EXT_ID &ext_id,
 366                                                              const INT_ID &int_id,
 367                                                              EXT_ID &old_ext_id,
 368                                                              INT_ID &old_int_id,
 369                                                              ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry)
 370 {
 371   ACE_TRACE ("ACE_RB_Tree::rebind (const EXT_ID &ext_id, const INT_ID &int_id, EXT_ID &old_ext_id, INT_ID &old_int_id, ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry)");
 372   ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);
 373
 374   int result = this->insert_i (ext_id, int_id, entry);
 375
 376   if (result == 1)
 377     {
 378       old_ext_id = entry->key ();
 379       old_int_id = entry->item ();
 380       entry->key () = ext_id;
 381       entry->item () = int_id;
 382     }
 383
 384   return result;
 385 }
 386
 387
 388 // Locate <ext_id> and pass out parameter via <int_id>.  If found,
 389 // return 0, returns -1 if not found.
 390
 391 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 392 ACE_INLINE int
 393 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::find (const EXT_ID &ext_id,
 394                                                            INT_ID &int_id)
 395 {
 396   ACE_TRACE ("ACE_RB_Tree::find (const EXT_ID &ext_id, INT_ID &int_id)");
 397   ACE_READ_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);
 398
 399   ACE_RB_Tree_Node<EXT_ID, INT_ID> *entry = 0;
 400
 401   int result = this->find_i (ext_id, entry);
 402   if (result == 0)
 403     {
 404       int_id = entry->item ();
 405     }
 406
 407   return result;
 408 }
 409
 410 // Locate <ext_id> and pass out parameter via <entry>.  If found,
 411 // return 0, returns -1 if not found.
 412
 413 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 414 ACE_INLINE int
 415 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::find (const EXT_ID &ext_id,
 416                                                            ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry)
 417 {
 418   ACE_TRACE ("ACE_RB_Tree::find (const EXT_ID &ext_id, ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry)");
 419   ACE_READ_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);
 420
 421   return this->find_i (ext_id, entry);
 422 }
 423
 424
 425 // Unbind (remove) the <ext_id> from the tree.  Don't return the
 426 // <int_id> to the caller (this is useful for collections where the
 427 // <int_id>s are *not* dynamically allocated...).
 428
 429 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 430 ACE_INLINE int
 431 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::unbind (const EXT_ID &ext_id)
 432 {
 433   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::unbind (const EXT_ID &ext_id)");
 434   ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);
 435
 436   INT_ID int_id;
 437   int result = this->remove_i (ext_id, int_id);
 438
 439   // Remap the return codes from the internal method: this
 440   // is maintained this way in support of deprecated methods,
 441   // and will be cleaned up when these methods are removed.
 442   switch (result)
 443     {
 444       case 1:
 445         // If the node was found and deleted, return success.
 446         return 0;
 447       case 0:
 448         // If nothing was found, set errno and break.
 449         errno = ENOENT;
 450         break;
 451       case -1:
 452         // If an error happened, just break.
 453         break;
 454     }
 455
 456   // Return an error if we didn't already return success.
 457   return -1;
 458 }
 459
 460
 461 // Break any association of <ext_id>.  Returns the value of <int_id>
 462 // in case the caller needs to deallocate memory.
 463
 464 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 465 ACE_INLINE int
 466 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::unbind (const EXT_ID &ext_id,
 467                                                              INT_ID &int_id)
 468 {
 469   ACE_TRACE ("ACE_RB_Tree::unbind (const EXT_ID &ext_id, INT_ID &int_id)");
 470   ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);
 471
 472   int result = this->remove_i (ext_id, int_id);
 473
 474   // Remap the return codes from the internal method: this
 475   // is maintained this way in support of deprecated methods,
 476   // and will be cleaned up when these methods are removed.
 477   switch (result)
 478     {
 479       case 1:
 480         // If the node was found and deleted, return success.
 481         return 0;
 482       case 0:
 483         // If nothing was found, set errno and break.
 484         errno = ENOENT;
 485         break;
 486       case -1:
 487         // If an error happened, just break.
 488         break;
 489     }
 490
 491   // Return an error if we didn't already return success.
 492   return -1;
 493 }
 494
 495
 496 // Remove entry from the tree.  This method should be used with *extreme*
 497 // caution, and only for optimization purposes.  The node being passed
 498 // in had better have been allocated by the tree that is unbinding it.
 499 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 500 ACE_INLINE int
 501 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::unbind (ACE_RB_Tree_Node<EXT_ID, INT_ID> *entry)
 502 {
 503   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::unbind (ACE_RB_Tree_Node<EXT_ID, INT_ID> *entry)");
 504   ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);
 505
 506   return this->remove_i (entry);
 507 }
 508
 509
 510 // Returns a reference to the underlying <ACE_LOCK>.  This makes it
 511 // possible to acquire the lock explicitly, which can be useful in
 512 // some cases if you instantiate the <ACE_Atomic_Op> with an
 513 // <ACE_Recursive_Mutex> or <ACE_Process_Mutex>, or if you need to
 514 // guard the state of an iterator.  NOTE: the right name would be
 515 // <lock>, but HP/C++ will choke on that!
 516
 517 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 518 ACE_INLINE ACE_LOCK &
 519 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::mutex ()
 520 {
 521   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::mutex");
 522   return this->lock_;
 523 }
 524
 525
 526 // Dump the state of an object.
 527
 528 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 529 ACE_INLINE void
 530 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::dump () const
 531 {
 532 #if defined (ACE_HAS_DUMP)
 533   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::dump");
 534   ACELIB_DEBUG ((LM_DEBUG, ACE_BEGIN_DUMP, this));
 535   ACELIB_DEBUG ((LM_DEBUG,  ACE_TEXT ("\ncurrent_size_ = %d\n"), this->current_size_));
 536   this->allocator_->dump ();
 537   this->lock_.dump ();
 538   ACELIB_DEBUG ((LM_DEBUG,  ACE_TEXT ("\nDumping nodes from root\n")));
 539   this->dump_i (this->root_);
 540   ACELIB_DEBUG ((LM_DEBUG, ACE_END_DUMP));
 541 #endif /* ACE_HAS_DUMP */
 542 }
 543
 544
 545 // Return forward iterator positioned at first node in tree.
 546
 547 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 548 ACE_INLINE ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>
 549 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::begin ()
 550 {
 551   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::begin");
 552
 553   return ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> (*this);
 554 }
 555
 556
 557 // Return forward iterator positioned at last node in tree.
 558
 559 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 560 ACE_INLINE ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>
 561 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::end ()
 562 {
 563   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::end");
 564
 565   return ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> ();
 566 }
 567
 568
 569 // Return reverse iterator positioned at last node in tree.
 570
 571 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 572 ACE_INLINE ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>
 573 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::rbegin ()
 574 {
 575   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::rbegin");
 576
 577   return ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> (*this);
 578 }
 579
 580
 581 // Return reverse iterator positioned at first node in tree.
 582
 583 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 584 ACE_INLINE ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>
 585 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::rend ()
 586 {
 587   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::rend");
 588
 589   return ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> ();
 590 }
 591
 592
 593 // Returns a pointer to the item corresponding to the given key,
 594 // or 0 if it cannot find the key in the tree.  DEPRECATED.
 595
 596 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 597 ACE_INLINE INT_ID*
 598 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::find (const EXT_ID &k)
 599 {
 600   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::find (const EXT_ID &k)");
 601
 602   // The reinterpret cast is to ensure that when this deprecated
 603   // method is removed, and is replaced (as planned) by a find method
 604   // that takes the same argument signature but returns an int, that
 605   // the compiler will cough if this return macro is not changed to
 606   // just return an int (whose value will be -1).  Please leave this
 607   // as is.
 608   ACE_READ_GUARD_RETURN (ACE_LOCK,
 609                          ace_mon,
 610                          this->lock_,
 611                          reinterpret_cast<INT_ID*> (0L));
 612
 613   ACE_RB_Tree_Node<EXT_ID, INT_ID> *entry = 0;
 614   int result = this->find_i (k, entry);
 615   return (result == 0) ? &(entry->item ()) : 0;
 616 }
 617
 618 // Inserts a *copy* of the key and the item into the tree:
 619 // both the key type EXT_ID and the item type INT_ID must have well
 620 // defined semantics for copy construction and < comparison.
 621 // This method returns a pointer to the inserted item copy,
 622 // or 0 if an error occurred.  NOTE: if an identical key
 623 // already exists in the tree, no new item is created, and
 624 // the returned pointer addresses the existing item
 625 // associated with the existing key.   DEPRECATED.
 626
 627 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 628 ACE_INLINE INT_ID*
 629 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::insert (const EXT_ID &k, const INT_ID &t)
 630 {
 631   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::insert");
 632   ACE_WRITE_GUARD_RETURN (ACE_LOCK,
 633                           ace_mon,
 634                           this->lock_,
 635                           reinterpret_cast<INT_ID*> (0L));
 636
 637   return this->insert_i (k, t);
 638 }
 639
 640
 641 // Removes the item associated with the given key from the
 642 // tree and destroys it.  Returns 1 if it found the item
 643 // and successfully destroyed it, 0 if it did not find the
 644 // item, or -1 if an error occurred.  DEPRECATED.
 645
 646 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 647 ACE_INLINE int
 648 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::remove (const EXT_ID &k)
 649 {
 650   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::remove");
 651   ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);
 652
 653   INT_ID i;
 654   return this->remove_i (k, i);
 655 }
 656
 657
 658 // Destroys all nodes and sets the root pointer null.  DEPRECATED
 659
 660 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 661 ACE_INLINE void
 662 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::clear ()
 663 {
 664   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::clear");
 665   ACE_WRITE_GUARD (ACE_LOCK, ace_mon, this->lock_);
 666
 667   this->close_i ();
 668 }
 669
 670 // Returns the current number of nodes in the tree.
 671
 672 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 673 ACE_INLINE size_t
 674 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::current_size () const
 675 {
 676   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::current_size");
 677   return current_size_;
 678 }
 679
 680
 681 ///////////////////////////////////////////////////////////////////////
 682 // template class                                                    //
 683 // ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> //
 684 ///////////////////////////////////////////////////////////////////////
 685
 686 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 687 ACE_INLINE
 688 ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Iterator_Base ()
 689   : tree_ (0), node_ (0)
 690 {
 691   ACE_TRACE ("ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Iterator_Base ()");
 692 }
 693
 694 // Returns 1 when the iteration has completed, otherwise 0.
 695
 696 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 697 ACE_INLINE int
 698 ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::done () const
 699 {
 700   ACE_TRACE ("ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::done");
 701
 702   return node_ ? 0 : 1;
 703 }
 704
 705
 706 // STL-like iterator dereference operator: returns a reference
 707 // to the node underneath the iterator.
 708
 709 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 710 ACE_INLINE ACE_RB_Tree_Node<EXT_ID, INT_ID> &
 711 ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator* () const
 712 {
 713   ACE_TRACE ("ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator*");
 714   return *(this->node_);
 715 }
 716
 717
 718 // STL-like iterator dereference operator: returns a reference
 719 // to the node underneath the iterator.
 720
 721 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 722 ACE_INLINE ACE_RB_Tree_Node<EXT_ID, INT_ID> *
 723 ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator-> () const
 724 {
 725   ACE_TRACE ("ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator->");
 726   return this->node_;
 727 }
 728
 729
 730 // Returns a reference to the tree over which we're iterating.
 731
 732 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>ACE_INLINE const ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &
 733 ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::tree ()
 734 {
 735   ACE_TRACE ("ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::tree");
 736   return *tree_;
 737 }
 738
 739
 740 // Comparison operator: returns 1 if both iterators point to the same position, otherwise 0.
 741
 742 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 743 ACE_INLINE bool
 744 ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator==
 745   (const ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &rbt) const
 746 {
 747   ACE_TRACE ("ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator==");
 748   return (this->node_ == rbt.node_) ? true : false;
 749 }
 750
 751
 752 // Comparison operator: returns 1 if the iterators point to different positions, otherwise 0.
 753
 754 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 755 ACE_INLINE bool
 756 ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator!=
 757   (const ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &rbt) const
 758 {
 759   ACE_TRACE ("ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator!=");
 760   return (this->node_ == rbt.node_) ? false : true;
 761 }
 762
 763
 764 // Move forward by one element in the tree.  Returns 0 when
 765 // there are no more elements in the tree, otherwise 1.
 766
 767 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 768 ACE_INLINE int
 769 ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::forward_i ()
 770 {
 771   ACE_TRACE ("ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::forward_i");
 772
 773   if (node_)
 774     {
 775       node_ = tree_->RB_tree_successor (node_);
 776     }
 777
 778   return node_ ? 1 : 0;
 779 }
 780
 781
 782 // Move back by one element in the tree.  Returns 0 when
 783 // there are no more elements in the tree, otherwise 1.
 784
 785 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 786 ACE_INLINE int
 787 ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::reverse_i ()
 788 {
 789   ACE_TRACE ("ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::reverse_i");
 790
 791   if (node_)
 792     {
 793       node_ = tree_->RB_tree_predecessor (node_);
 794     }
 795
 796   return node_ ? 1 : 0;
 797 }
 798
 799
 800 //////////////////////////////////////////////////////////////////
 801 // template class                                               //
 802 // ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> //
 803 //////////////////////////////////////////////////////////////////
 804
 805 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 806 ACE_INLINE
 807 ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Iterator ()
 808   : ACE_RB_Tree_Iterator_Base<EXT_ID,INT_ID,COMPARE_KEYS,ACE_LOCK> ()
 809 {
 810   ACE_TRACE ("ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Iterator ()");
 811 }
 812
 813 // Move forward by one element in the tree.  Returns
 814 // 0 when all elements have been seen, else 1.
 815
 816 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 817 ACE_INLINE int
 818 ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::advance ()
 819 {
 820   ACE_TRACE ("ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::advance");
 821
 822   return this->forward_i ();
 823 }
 824
 825
 826 // Dump the state of an object.
 827
 828 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 829 ACE_INLINE void
 830 ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::dump () const
 831 {
 832 #if defined (ACE_HAS_DUMP)
 833   ACE_TRACE ("ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::dump");
 834
 835   this->dump_i ();
 836 #endif /* ACE_HAS_DUMP */
 837 }
 838
 839
 840 // Prefix advance.
 841
 842 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 843 ACE_INLINE ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &
 844 ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator++ ()
 845 {
 846   ACE_TRACE ("ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> operator++ ()");
 847
 848   this->forward_i ();
 849   return *this;
 850 }
 851
 852
 853 // Postfix advance.
 854
 855 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 856 ACE_INLINE ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>
 857 ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator++ (int)
 858 {
 859   ACE_TRACE ("ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> operator++ (int)");
 860
 861   ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> retv (*this);
 862   ++*this;
 863   return retv;
 864 }
 865
 866
 867 // Prefix reverse.
 868
 869 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 870 ACE_INLINE ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &
 871 ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator-- ()
 872 {
 873   ACE_TRACE ("ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> operator-- ()");
 874
 875   this->reverse_i ();
 876   return *this;
 877 }
 878
 879
 880 // Postfix reverse.
 881
 882 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 883 ACE_INLINE ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>
 884 ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator-- (int)
 885 {
 886   ACE_TRACE ("ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> operator-- (int)");
 887
 888   ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> retv (*this);
 889   --*this;
 890   return retv;
 891 }
 892
 893
 894 // Passes back the <entry> under the iterator.  Returns 0 if
 895 // the iteration has completed, otherwise 1.  This method must
 896 // be declared and defined in both the derived forward and
 897 // reverse iterator classes rather than in the base iterator
 898 // class because of a method signature resolution problem
 899 // caused by the existence of the deprecated next ()
 900 // method in the derived forward iterator class.  When that
 901 // deprecated method is removed, this method should be removed
 902 // from the derived classes and placed in the base class.
 903
 904 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 905 ACE_INLINE int
 906 ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::next (ACE_RB_Tree_Node<EXT_ID, INT_ID> *&next_entry) const
 907 {
 908   ACE_TRACE ("ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::next");
 909
 910   if (this->node_)
 911     {
 912       next_entry = this->node_;
 913       return 1;
 914     }
 915
 916   return 0;
 917 }
 918
 919
 920 // Accessor for key of node under iterator (if any). DEPRECATED.
 921
 922 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 923 ACE_INLINE EXT_ID *
 924 ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::key ()
 925 {
 926   ACE_TRACE ("ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::key");
 927   return this->node_ ? (&(this->node_->key ())) : 0;
 928 }
 929
 930
 931 // Accessor for item of node under iterator (if any). DEPRECATED.
 932
 933 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 934 ACE_INLINE INT_ID *
 935 ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::item ()
 936 {
 937   ACE_TRACE ("ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::item");
 938   return this->node_ ? (&(this->node_->item ())) : 0;
 939 }
 940
 941
 942 // Move to the first item in the tree. DEPRECATED.
 943
 944 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 945 ACE_INLINE int
 946 ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::first ()
 947 {
 948   ACE_TRACE ("ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::first");
 949   this->node_ = this->tree_->RB_tree_minimum (this->tree_->root_);
 950   return this->node_ ? 1 : 0;
 951 }
 952
 953
 954 // Move to the last item in the tree. DEPRECATED.
 955
 956 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 957 ACE_INLINE int
 958 ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::last ()
 959 {
 960   ACE_TRACE ("ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::last");
 961   this->node_ = this->tree_->RB_tree_maximum (this->tree_->root_);
 962   return this->node_ ? 1 : 0;
 963 }
 964
 965
 966 // Moves to the next item in the tree,
 967 // returns 1 if there is a next item, 0 otherwise. DEPRECATED.
 968
 969 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 970 ACE_INLINE int
 971 ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::next ()
 972 {
 973   ACE_TRACE ("ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::next");
 974   this->node_ = this->tree_->RB_tree_successor (this->node_);
 975   return this->node_ ? 1 : 0;
 976 }
 977
 978
 979 // Moves to the previous item in the tree,
 980 // returns 1 if there is a previous item, 0 otherwise. DEPRECATED.
 981
 982 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 983 ACE_INLINE int
 984 ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::previous ()
 985 {
 986   ACE_TRACE ("ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::previous");
 987   this->node_ = this->tree_->RB_tree_predecessor (this->node_);
 988   return this->node_ ? 1 : 0;
 989 }
 990
 991
 992 // Returns 0 if the iterator is positioned over a valid ACE_RB_Tree
 993 // node, returns 1 if not. DEPRECATED.
 994
 995 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 996 ACE_INLINE int
 997 ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::is_done ()
 998 {
 999   ACE_TRACE ("ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::is_done");
1000   return this->node_ ? 0 : 1;
1001 }
1002
1003
1004 //////////////////////////////////////////////////////////////////////////
1005 // template class                                                       //
1006 // ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> //
1007 //////////////////////////////////////////////////////////////////////////
1008
1009
1010 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
1011 ACE_INLINE
1012 ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Reverse_Iterator ()
1013   : ACE_RB_Tree_Iterator_Base<EXT_ID,INT_ID,COMPARE_KEYS,ACE_LOCK> ()
1014 {
1015   ACE_TRACE ("ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Reverse_Iterator ()");
1016 }
1017
1018 // Move forward by one element in the tree.  Returns
1019 // 0 when all elements have been seen, else 1.
1020
1021 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
1022 ACE_INLINE int
1023 ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::advance ()
1024 {
1025   ACE_TRACE ("ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::advance");
1026
1027   return this->reverse_i ();
1028 }
1029
1030
1031 // Dump the state of an object.
1032
1033 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
1034 ACE_INLINE void
1035 ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::dump () const
1036 {
1037 #if defined (ACE_HAS_DUMP)
1038   ACE_TRACE ("ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::dump");
1039
1040   this->dump_i ();
1041 #endif /* ACE_HAS_DUMP */
1042 }
1043
1044
1045 // Prefix advance.
1046
1047 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
1048 ACE_INLINE ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &
1049 ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator++ ()
1050 {
1051   ACE_TRACE ("ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator++ ()");
1052
1053   this->reverse_i ();
1054   return *this;
1055 }
1056
1057
1058 // Postfix advance.
1059
1060 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
1061 ACE_INLINE ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>
1062 ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator++ (int)
1063 {
1064   ACE_TRACE ("ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator++ (int)");
1065
1066   ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> retv (*this);
1067   ++*this;
1068   return retv;
1069 }
1070
1071
1072 // Prefix reverse.
1073
1074 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
1075 ACE_INLINE ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &
1076 ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator-- ()
1077 {
1078   ACE_TRACE ("ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator-- ()");
1079
1080   this->forward_i ();
1081   return *this;
1082 }
1083
1084
1085 // Postfix reverse.
1086
1087 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
1088 ACE_INLINE ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>
1089 ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator-- (int)
1090 {
1091   ACE_TRACE ("ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator-- (int)");
1092
1093   ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> retv (*this);
1094   --*this;
1095   return retv;
1096 }
1097
1098
1099 // Passes back the <entry> under the iterator.  Returns 0 if
1100 // the iteration has completed, otherwise 1.  This method must
1101 // be declared and defined in both the derived forward and
1102 // reverse iterator classes rather than in the base iterator
1103 // class because of a method signature resolution problem
1104 // caused by the existence of the deprecated next ()
1105 // method in the derived forward iterator class.  When that
1106 // deprecated method is removed, this method should be removed
1107 // from the derived classes and placed in the base class.
1108
1109 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
1110 ACE_INLINE int
1111 ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::next (ACE_RB_Tree_Node<EXT_ID, INT_ID> *&next_entry) const
1112 {
1113   ACE_TRACE ("ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::next");
1114
1115   if (this->node_)
1116     {
1117       next_entry = this->node_;
1118       return 1;
1119     }
1120
1121   return 0;
1122 }
1123
1124 ACE_END_VERSIONED_NAMESPACE_DECL