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