/* -*- C++ -*- */
// $Id$

#include "ace/Synch.h"
#include "ace/Malloc.h"

/////////////////////////////////////////////////////
// template class ACE_RB_Tree_Node<EXT_ID, INT_ID> //
/////////////////////////////////////////////////////

// Key accessor.

template <class EXT_ID, class INT_ID>
ACE_INLINE EXT_ID &
ACE_RB_Tree_Node<EXT_ID, INT_ID>::key ()
{
  ACE_TRACE ("ACE_RB_Tree_Node<EXT_ID, INT_ID>::key");
  return k_;
}


// Item accessor.

template <class EXT_ID, class INT_ID>
ACE_INLINE INT_ID &
ACE_RB_Tree_Node<EXT_ID, INT_ID>::item ()
{
  ACE_TRACE ("ACE_RB_Tree_Node<EXT_ID, INT_ID>:item");
  return t_;
}


// Set color of the node.

template <class EXT_ID, class INT_ID>
ACE_INLINE void
ACE_RB_Tree_Node<EXT_ID, INT_ID>::color (ACE_RB_Tree_Node_Base::RB_Tree_Node_Color c)
{
  ACE_TRACE ("ACE_RB_Tree_Node<EXT_ID, INT_ID>::color mutator");
  color_ = c;
}


// Get color of the node.

template <class EXT_ID, class INT_ID>
ACE_INLINE ACE_RB_Tree_Node_Base::RB_Tree_Node_Color
ACE_RB_Tree_Node<EXT_ID, INT_ID>::color ()
{
  ACE_TRACE ("ACE_RB_Tree_Node<EXT_ID, INT_ID>::color accessor");
  return color_;
}


// Accessor for node's parent pointer.

template <class EXT_ID, class INT_ID>
ACE_INLINE ACE_RB_Tree_Node<EXT_ID, INT_ID> *
ACE_RB_Tree_Node<EXT_ID, INT_ID>::parent ()
{
  ACE_TRACE ("ACE_RB_Tree_Node<EXT_ID, INT_ID>::parent accessor");
  return parent_;
}


// Mutator for node's parent pointer.

template <class EXT_ID, class INT_ID>
ACE_INLINE void
ACE_RB_Tree_Node<EXT_ID, INT_ID>::parent (ACE_RB_Tree_Node<EXT_ID, INT_ID> * p)
{
  ACE_TRACE ("ACE_RB_Tree_Node<EXT_ID, INT_ID>::parent mutator");
  parent_ = p;
}



// Accessor for node's left child pointer.

template <class EXT_ID, class INT_ID>
ACE_INLINE ACE_RB_Tree_Node<EXT_ID, INT_ID> *
ACE_RB_Tree_Node<EXT_ID, INT_ID>::left ()
{
  ACE_TRACE ("ACE_RB_Tree_Node<EXT_ID, INT_ID>::left accessor");
  return left_;
}


// Mutator for node's left child pointer.

template <class EXT_ID, class INT_ID>
ACE_INLINE void
ACE_RB_Tree_Node<EXT_ID, INT_ID>::left (ACE_RB_Tree_Node<EXT_ID, INT_ID> * l)
{
  ACE_TRACE ("ACE_RB_Tree_Node<EXT_ID, INT_ID>::left mutator");
  left_ = l;
}


// Accessor for node's right child pointer.

template <class EXT_ID, class INT_ID>
ACE_INLINE ACE_RB_Tree_Node<EXT_ID, INT_ID> *
ACE_RB_Tree_Node<EXT_ID, INT_ID>::right ()
{
  ACE_TRACE ("ACE_RB_Tree_Node<EXT_ID, INT_ID>::right accessor");
  return right_;
}


// Mutator for node's right child pointer.

template <class EXT_ID, class INT_ID>
ACE_INLINE void
ACE_RB_Tree_Node<EXT_ID, INT_ID>::right (ACE_RB_Tree_Node<EXT_ID, INT_ID> * r)
{
  ACE_TRACE ("ACE_RB_Tree_Node<EXT_ID, INT_ID>::right mutator");
  right_ = r;
}



////////////////////////////////////////////////////////////////////////
// template class ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> //
////////////////////////////////////////////////////////////////////////


// Initialize an RB Tree.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE int
ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::open (ACE_Allocator *alloc)
{
  ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::open");
  ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);

  // Calling this->close_i () ensures we release previously allocated
  // memory before allocating new memory.
  this->close_i ();

  // If we were passed an allocator use it,
  // otherwise use the default instance.

  if (alloc == 0)
    alloc = ACE_Allocator::instance ();

  this->allocator_ = alloc;

  return 0;
}

// Close down an RB_Tree and release dynamically allocated
// resources.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE int
ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::close (void)
{
  ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::close");
  ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);

  return this->close_i ();
}


// Associate <ext_id> with <int_id>.  If <ext_id> is already in the
// tree then the <ACE_RB_Tree_Node> is not changed.  Returns 0 if a
// new entry is bound successfully, returns 1 if an attempt is made
// to bind an existing entry, and returns -1 if failures occur.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE int
ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::bind (const EXT_ID &item,
                                                           const INT_ID &int_id)
{
  ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::bind (const EXT_ID &item, const INT_ID &int_id)");
  ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);

  // @@ TBD - implement this
  ACE_NOTSUP_RETURN (-1);
}


// Same as a normal bind, except the tree entry is also passed back
// to the caller.  The entry in this case will either be the newly
// created entry, or the existing one.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE int
ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::bind (const EXT_ID &ext_id,
                                                           const INT_ID &int_id,
                                                           ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry)
{
  ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>"
             "::bind (const EXT_ID &ext_id, const INT_ID &int_id, "
             "ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry)");
  ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);

  // @@ TBD - implement this
  ACE_NOTSUP_RETURN (-1);
}


// Associate <ext_id> with <int_id> if and only if <ext_id> is not
// in the tree.  If <ext_id> is already in the tree then the <int_id>
// parameter is assigned the existing value in the tree.  Returns 0
// if a new entry is bound successfully, returns 1 if an attempt is
// made to bind an existing entry, and returns -1 if failures occur.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE int
ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::trybind (const EXT_ID &ext_id,
                                                             INT_ID &int_id)
{
  ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::"
             "trybind (const EXT_ID &ext_id, INT_ID &int_id)");
  ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);

  // @@ TBD - implement this
  ACE_NOTSUP_RETURN (-1);
}


// Same as a normal trybind, except the tree entry is also passed
// back to the caller.  The entry in this case will either be the
// newly created entry, or the existing one.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE int
ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::trybind (const EXT_ID &ext_id,
                                                              INT_ID &int_id,
                                                              ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry)
{
  ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::"
             "trybind (const EXT_ID &ext_id, INT_ID &int_id, "
             "ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry)");
  ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);

  // @@ TBD - implement this
  ACE_NOTSUP_RETURN (-1);
}


// Reassociate <ext_id> with <int_id>.  If <ext_id> is not in the
// tree then behaves just like <bind>.  Returns 0 if a new entry is
// bound successfully, returns 1 if an existing entry was rebound,
// and returns -1 if failures occur.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE int
ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::rebind (const EXT_ID &ext_id,
                                                             const INT_ID &int_id)
{
  ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::"
             "rebind (const EXT_ID &ext_id, const INT_ID &int_id)");
  ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);

  // @@ TBD - implement this
  ACE_NOTSUP_RETURN (-1);
}


// Same as a normal rebind, except the tree entry is also passed back
// to the caller.  The entry in this case will either be the newly
// created entry, or the existing one.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE int
ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::rebind (const EXT_ID &ext_id,
                                                             const INT_ID &int_id,
                                                             ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry)
{
  ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::"
             "rebind (const EXT_ID &ext_id, const INT_ID &int_id, "
             "ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry)");
  ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);

  // @@ TBD - implement this
  ACE_NOTSUP_RETURN (-1);
}


// Associate <ext_id> with <int_id>.  If <ext_id> is not in the tree
// then behaves just like <bind>.  Otherwise, store the old value of
// <int_id> into the "out" parameter and rebind the new parameters.
// Returns 0 if a new entry is bound successfully, returns 1 if an
// existing entry was rebound, and returns -1 if failures occur.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE int
ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::rebind (const EXT_ID &ext_id,
                                                             const INT_ID &int_id,
                                                             INT_ID &old_int_id)
{
  ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::"
             "rebind (const EXT_ID &ext_id, const INT_ID &int_id, INT_ID &old_int_id)");
  ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);

  // @@ TBD - implement this
  ACE_NOTSUP_RETURN (-1);
}


// Same as a normal rebind, except the tree entry is also passed back
// to the caller.  The entry in this case will either be the newly
// created entry, or the existing one.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE int
ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::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)
{
  ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::"
             "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)");
  ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);

  // @@ TBD - implement this
  ACE_NOTSUP_RETURN (-1);
}


// Associate <ext_id> with <int_id>.  If <ext_id> is not in the tree
// then behaves just like <bind>.  Otherwise, store the old values
// of <ext_id> and <int_id> into the "out" parameters and rebind the
// new parameters.  This is very useful if you need to have an
// atomic way of updating <ACE_RB_Tree_Nodes> and you also need
// full control over memory allocation.  Returns 0 if a new entry is
// bound successfully, returns 1 if an existing entry was rebound,
// and returns -1 if failures occur.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE int
ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::rebind (const EXT_ID &ext_id,
                                                             const INT_ID &int_id,
                                                             EXT_ID &old_ext_id,
                                                             INT_ID &old_int_id)
{
  ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::"
             "rebind (const EXT_ID &ext_id, const INT_ID &int_id,"
             "EXT_ID &old_ext_id, INT_ID &old_int_id)");
  ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);

  // @@ TBD - implement this
  ACE_NOTSUP_RETURN (-1);
}


// Same as a normal rebind, except the tree entry is also passed back
// to the caller.  The entry in this case will either be the newly
// created entry, or the existing one.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE int
ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::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)
{
  ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::"
             "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)");
  ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);

  // @@ TBD - implement this
  ACE_NOTSUP_RETURN (-1);
}


// Locate <ext_id> and pass out parameter via <int_id>.  If found,
// return 0, returns -1 if not found.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE int
ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::find (const EXT_ID &ext_id,
                                                           INT_ID &int_id)
{
  ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::"
             "find (const EXT_ID &ext_id, INT_ID &int_id)");
  ACE_READ_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);

  ACE_RB_Tree_Node<EXT_ID, INT_ID> *entry = 0;

  int result = this->find_i (ext_id, entry);
  if (result == 0)
    {
      int_id = entry->item ();
    }

  return result;
}

// Locate <ext_id> and pass out parameter via <entry>.  If found,
// return 0, returns -1 if not found.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE int
ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::find (const EXT_ID &ext_id,
                                                           ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry)
{
  ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::"
             "find (const EXT_ID &ext_id, ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry)");
  ACE_READ_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);

  return this->find_i (ext_id, entry);
}


// Unbind (remove) the <ext_id> from the tree.  Don't return the
// <int_id> to the caller (this is useful for collections where the
// <int_id>s are *not* dynamically allocated...).

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE int
ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::unbind (const EXT_ID &ext_id)
{
  ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::unbind (const EXT_ID &ext_id)");
  ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);

  INT_ID int_id;
  int result = this->remove_i (ext_id, int_id);

  // Remap the return codes from the internal method: this
  // is maintained this way in support of deprecated methods,
  // and will be cleaned up when these methods are removed.
  switch (result)
    {
      case 1:
        // If the node was found and deleted, return success.
        return 0;
      case 0:
        // If nothing was found, set errno and break.
        errno = ENOENT;
        break;
      case -1:
        // If an error happened, just break.
        break;
    }

  // Return an error if we didn't already return success.
  return -1;
}


// Break any association of <ext_id>.  Returns the value of <int_id>
// in case the caller needs to deallocate memory.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE int
ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::unbind (const EXT_ID &ext_id,
                                                             INT_ID &int_id)
{
  ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::"
             "unbind (const EXT_ID &ext_id, INT_ID &int_id)");
  ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);

  int result = this->remove_i (ext_id, int_id);

  // Remap the return codes from the internal method: this
  // is maintained this way in support of deprecated methods,
  // and will be cleaned up when these methods are removed.
  switch (result)
    {
      case 1:
        // If the node was found and deleted, return success.
        return 0;
      case 0:
        // If nothing was found, set errno and break.
        errno = ENOENT;
        break;
      case -1:
        // If an error happened, just break.
        break;
    }

  // Return an error if we didn't already return success.
  return -1;
}


// Remove entry from the tree.  This method should be used with *extreme*
// caution, and only for optimization purposes.  The node being passed
// in had better have been allocated by the tree that is unbinding it.
template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE int
ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::unbind (ACE_RB_Tree_Node<EXT_ID, INT_ID> *entry)
{
  ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::unbind (ACE_RB_Tree_Node<EXT_ID, INT_ID> *entry)");
  ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);

  return this->remove_i (entry);
}


// Returns a reference to the underlying <ACE_LOCK>.  This makes it
// possible to acquire the lock explicitly, which can be useful in
// some cases if you instantiate the <ACE_Atomic_Op> with an
// <ACE_Recursive_Mutex> or <ACE_Process_Mutex>, or if you need to
// guard the state of an iterator.  NOTE: the right name would be
// <lock>, but HP/C++ will choke on that!

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE ACE_LOCK &
ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::mutex (void)
{
  ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::mutex");
  return this->lock_;
}


// Dump the state of an object.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE void
ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::dump (void) const
{
  ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::dump");
  ACE_DEBUG ((LM_DEBUG, ACE_BEGIN_DUMP, this));
  ACE_DEBUG ((LM_DEBUG,  ASYS_TEXT ("\ncurrent_size_ = %d"), this->current_size_));
  this->allocator_->dump ();
  this->lock_.dump ();
  ACE_DEBUG ((LM_DEBUG, ACE_END_DUMP));
}


// Return forward iterator positioned at first node in tree.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>
ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::begin (void)
{
  ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::begin");

  return ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> (*this);
}


// Return forward iterator positioned at last node in tree.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>
ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::end (void)
{
  ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::end");

  return ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> (*this, 0);
}


// Return reverse iterator positioned at last node in tree.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>
ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::rbegin (void)
{
  ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::rbegin");

  return ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> (*this);
}


// Return reverse iterator positioned at first node in tree.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>
ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::rend (void)
{
  ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::rend");

  return ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> (*this, 0);
}


// Returns a pointer to the item corresponding to the given key,
// or 0 if it cannot find the key in the tree.  DEPRECATED.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE INT_ID*
ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::find (const EXT_ID &k)
{
  ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::find (const EXT_ID &k)");

  // The reinterpret cast is to ensure that when this deprecated method is removed, and
  // is replaced (as planned) by a find method that takes the same argument signature
  // but returns an int, that the compiler will cough if this return macro is not
  // changed to just return an int (whose value will be -1).  Please leave this as is.
  ACE_READ_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, ACE_reinterpret_cast(INT_ID*, 0L));

  ACE_RB_Tree_Node<EXT_ID, INT_ID> *entry;
  int result = this->find_i (k, entry);
  return (result == 0) ? &(entry->item ()) : 0;
}

// Inserts a *copy* of the key and the item into the tree:
// both the key type EXT_ID and the item type INT_ID must have well
// defined semantics for copy construction and < comparison.
// This method returns a pointer to the inserted item copy,
// or 0 if an error occurred.  NOTE: if an identical key
// already exists in the tree, no new item is created, and
// the returned pointer addresses the existing item
// associated with the existing key.   DEPRECATED.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE INT_ID*
ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::insert (const EXT_ID &k, const INT_ID &t)
{
  ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::insert");
  ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, ACE_reinterpret_cast(INT_ID*, 0L));

  return this->insert_i (k, t);
}


// Removes the item associated with the given key from the
// tree and destroys it.  Returns 1 if it found the item
// and successfully destroyed it, 0 if it did not find the
// item, or -1 if an error occurred.  DEPRECATED.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE int
ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::remove (const EXT_ID &k)
{
  ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::remove");
  ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);

  INT_ID i;
  return this->remove_i (k, i);
}


// Destroys all nodes and sets the root pointer null.  DEPRECATED

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE void
ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::clear ()
{
  ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::clear");
  ACE_WRITE_GUARD (ACE_LOCK, ace_mon, this->lock_);

  this->close_i ();
}

// Returns the current number of nodes in the tree.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE size_t
ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::current_size ()
{
  ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::current_size");
  return current_size_;
}


///////////////////////////////////////////////////////////////////////
// template class                                                    //
// ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> //
///////////////////////////////////////////////////////////////////////

// Passes back the <entry> under the iterator.  Returns 0 if
// the iteration has completed, otherwise 1.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE int
ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::next (ACE_RB_Tree_Node<EXT_ID, INT_ID> *&next_entry) const
{
  ACE_TRACE ("ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::next");

  if (this->node_)
    {
      next_entry = this->node_;
      return 1;
    }

  return 0;
}


// Returns 1 when the iteration has completed, otherwise 0.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE int
ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::done (void) const
{
  ACE_TRACE ("ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::done");

  return node_ ? 0 : 1;
}


// STL-like iterator dereference operator: returns a reference
// to the node underneath the iterator.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE ACE_RB_Tree_Node<EXT_ID, INT_ID> &
ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator* (void) const
{
  ACE_TRACE ("ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator*");
  return *(this->node_);
}


// Returns a reference to the tree over which we're iterating.

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> &
ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::tree (void)
{
  ACE_TRACE ("ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::tree");
  return tree_;
}


// Comparison operator: returns 1 if both iterators point to the same position, otherwise 0.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE int
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> &rbt) const
{
  ACE_TRACE ("ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator==");
  return (this->node_ == rbt.node_) ? 1 : 0;
}


// Comparison operator: returns 1 if the iterators point to different positions, otherwise 0.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE int
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> &rbt) const
{
  ACE_TRACE ("ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator!=");
  return (this->node_ == rbt.node_) ? 0 : 1;
}


// Move forward by one element in the tree.  Returns 0 when
// there are no more elements in the tree, otherwise 1.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE int
ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::forward_i (void)
{
  ACE_TRACE ("ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::forward_i");

  node_ = tree_.RB_tree_successor (node_);
  return node_ ? 1 : 0;
}


// Move back by one element in the tree.  Returns 0 when
// there are no more elements in the tree, otherwise 1.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE int
ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::reverse_i (void)
{
  ACE_TRACE ("ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::reverse_i");

  node_ = tree_.RB_tree_predecessor (node_);
  return node_ ? 1 : 0;
}


// Dump the state of an object.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE void
ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::dump_i (void) const
{
  ACE_TRACE ("ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::dump_i");

  ACE_DEBUG ((LM_DEBUG, ACE_BEGIN_DUMP, this));
  ACE_DEBUG ((LM_DEBUG,  ASYS_TEXT ("node_ = %x"), this->node_));
  ACE_DEBUG ((LM_DEBUG, ACE_END_DUMP));
}


//////////////////////////////////////////////////////////////////
// template class                                               //
// ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> //
//////////////////////////////////////////////////////////////////

// Move forward by one element in the tree.  Returns
// 0 when all elements have been seen, else 1.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE int
ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::advance (void)
{
  ACE_TRACE ("ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::advance");

  return this->forward_i ();
}


// Dump the state of an object.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE void
ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::dump (void) const
{
  ACE_TRACE ("ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::dump");

  this->dump_i ();
}


// Prefix advance.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &
ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator++ (void)
{
  ACE_TRACE ("ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> operator++ (void)");

  this->forward_i ();
  return *this;
}


// Postfix advance.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>
ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator++ (int)
{
  ACE_TRACE ("ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> operator++ (int)");

  ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> retv (*this);
  this->forward_i ();
  return retv;
}


// Prefix reverse.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &
ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator-- (void)
{
  ACE_TRACE ("ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> operator-- (void)");

  this->reverse_i ();
  return *this;
}


// Postfix reverse.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>
ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator-- (int)
{
  ACE_TRACE ("ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> operator-- (int)");

  ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> retv (*this);
  this->reverse_i ();
  return retv;
}


// Accessor for key of node under iterator (if any). DEPRECATED.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE EXT_ID *
ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::key ()
{
  ACE_TRACE ("ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::key");
  return node_ ? (&(node_->key ())) : 0;
}


// Accessor for item of node under iterator (if any). DEPRECATED.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE INT_ID *
ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::item ()
{
  ACE_TRACE ("ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::item");
  return node_ ? (&(node_->item ())) : 0;
}


// Move to the first item in the tree. DEPRECATED.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE int
ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::first ()
{
  ACE_TRACE ("ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::first");
  node_ = tree_.RB_tree_minimum (tree_.root_);
  return node_ ? 1 : 0;
}


// Move to the last item in the tree. DEPRECATED.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE int
ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::last ()
{
  ACE_TRACE ("ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::last");
  node_ = tree_.RB_tree_maximum (tree_.root_);
  return node_ ? 1 : 0;
}


// Moves to the next item in the tree,
// returns 1 if there is a next item, 0 otherwise. DEPRECATED.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE int
ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::next ()
{
  ACE_TRACE ("ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::next");
  node_ = tree_.RB_tree_successor (node_);
  return node_ ? 1 : 0;
}


// Moves to the previous item in the tree,
// returns 1 if there is a previous item, 0 otherwise. DEPRECATED.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE int
ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::previous ()
{
  ACE_TRACE ("ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::previous");
  node_ = tree_.RB_tree_predecessor (node_);
  return node_ ? 1 : 0;
}


// Returns 0 if the iterator is positioned over a valid ACE_RB_Tree
// node, returns 1 if not. DEPRECATED.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE int
ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::is_done ()
{
  ACE_TRACE ("ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::is_done");
  return node_ ? 0 : 1;
}


//////////////////////////////////////////////////////////////////////////
// template class                                                       //
// ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> //
//////////////////////////////////////////////////////////////////////////


// Move forward by one element in the tree.  Returns
// 0 when all elements have been seen, else 1.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE int
ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::advance (void)
{
  ACE_TRACE ("ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::advance");

  return this->reverse_i ();
}


// Dump the state of an object.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE void
ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::dump (void) const
{
  ACE_TRACE ("ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::dump");

  this->dump_i ();
}


// Prefix advance.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &
ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator++ (void)
{
  ACE_TRACE ("ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator++ (void)");

  this->reverse_i ();
  return *this;
}


// Postfix advance.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>
ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator++ (int)
{
  ACE_TRACE ("ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator++ (int)");

  ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> retv (*this);
  this->reverse_i ();
  return retv;
}


// Prefix reverse.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &
ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator-- (void)
{
  ACE_TRACE ("ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator-- (void)");

  this->forward_i ();
  return *this;
}


// Postfix reverse.

template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>
ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator-- (int)
{
  ACE_TRACE ("ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator-- (int)");

  ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> retv (*this);
  this->forward_i ();
  return retv;
}