#include <ace/RB_Tree.h>
template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> class ACE_RB_Tree : public ACE_RB_Tree_Base {
public:
friend class ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>; friend class ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>; friend class ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>;typedef EXT_ID KEY;
typedef INT_ID VALUE;
typedef ACE_RB_Tree_Node<EXT_ID, INT_ID> ENTRY;
typedef ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> ITERATOR; typedef ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> REVERSE_ITERATOR; typedef ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> iterator; typedef ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> reverse_iterator;ACE_RB_Tree (ACE_Allocator *alloc = 0);
ACE_RB_Tree ( const ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &rbt );
int open (ACE_Allocator *alloc = 0);
int close (void);
virtual ~ACE_RB_Tree (void);
int bind (const EXT_ID &item, const INT_ID &int_id);
int bind ( const EXT_ID &ext_id, const INT_ID &int_id, ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry );
int trybind (const EXT_ID &ext_id, INT_ID &int_id);
int trybind ( const EXT_ID &ext_id, INT_ID &int_id, ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry );
int rebind (const EXT_ID &ext_id, const INT_ID &int_id);
int rebind ( const EXT_ID &ext_id, const INT_ID &int_id, ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry );
int rebind ( const EXT_ID &ext_id, const INT_ID &int_id, INT_ID &old_int_id );
int 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 );
int rebind ( const EXT_ID &ext_id, const INT_ID &int_id, EXT_ID &old_ext_id, INT_ID &old_int_id );
int 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 );
int find (const EXT_ID &ext_id, INT_ID &int_id);
int find ( const EXT_ID &ext_id, ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry );
int unbind (const EXT_ID &ext_id);
int unbind (const EXT_ID &ext_id, INT_ID &int_id);
int unbind (ACE_RB_Tree_Node<EXT_ID, INT_ID> *entry);
size_t current_size (void);
void operator= ( const ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &rbt );
virtual int lessthan (const EXT_ID &k1, const EXT_ID &k2);
ACE_LOCK &mutex (void);
void dump (void) const;
ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> begin ( void );
ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> end ( void );
ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> rbegin ( void );
ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> rend ( void );
INT_ID* find (const EXT_ID &k);
INT_ID* insert (const EXT_ID &k, const INT_ID &t);
int remove (const EXT_ID &k);
void clear (void);
protected:
void RB_rotate_right (ACE_RB_Tree_Node<EXT_ID, INT_ID> * x);
void RB_rotate_left (ACE_RB_Tree_Node<EXT_ID, INT_ID> * x);
void RB_delete_fixup (ACE_RB_Tree_Node<EXT_ID, INT_ID> * x);
RB_tree_successor (ACE_RB_Tree_Node<EXT_ID, INT_ID> *x) const;
RB_tree_predecessor (ACE_RB_Tree_Node<EXT_ID, INT_ID> *x) const;
RB_tree_minimum (ACE_RB_Tree_Node<EXT_ID, INT_ID> *x) const;
RB_tree_maximum (ACE_RB_Tree_Node<EXT_ID, INT_ID> *x) const;
find_node (const EXT_ID &k, RB_SearchResult &result);
void RB_rebalance (ACE_RB_Tree_Node<EXT_ID, INT_ID> * x);
int close_i (void);
int find_i ( const EXT_ID &ext_id, ACE_RB_Tree_Node<EXT_ID, INT_ID>* &entry );
INT_ID* insert_i (const EXT_ID &k, const INT_ID &t);
int insert_i ( const EXT_ID &k, const INT_ID &t, ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry );
int remove_i (const EXT_ID &k, INT_ID &i);
int remove_i (ACE_RB_Tree_Node<EXT_ID, INT_ID> *z);
private:
ACE_Allocator *allocator_;
ACE_LOCK lock_;
ACE_RB_Tree_Node<EXT_ID, INT_ID> *root_;
COMPARE_KEYS compare_keys_;
size_t current_size_;
};
typedef ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> ITERATOR;
typedef ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> REVERSE_ITERATOR;
typedef ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> iterator;
typedef ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> reverse_iterator;
ACE_RB_Tree (ACE_Allocator *alloc = 0);
ACE_RB_Tree (
const ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &rbt
);
int open (ACE_Allocator *alloc = 0);
int close (void);
virtual ~ACE_RB_Tree (void);
int bind (const EXT_ID &item, const INT_ID &int_id);
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.
int bind (
const EXT_ID &ext_id,
const INT_ID &int_id,
ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry
);
int trybind (const EXT_ID &ext_id, INT_ID &int_id);
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.
int trybind (
const EXT_ID &ext_id,
INT_ID &int_id,
ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry
);
int rebind (const EXT_ID &ext_id, const INT_ID &int_id);
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.
int rebind (
const EXT_ID &ext_id,
const INT_ID &int_id,
ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry
);
int rebind (
const EXT_ID &ext_id,
const INT_ID &int_id,
INT_ID &old_int_id
);
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.
int 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
);
int rebind (
const EXT_ID &ext_id,
const INT_ID &int_id,
EXT_ID &old_ext_id,
INT_ID &old_int_id
);
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.
int 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
);
int find (const EXT_ID &ext_id, INT_ID &int_id);
ext_id
and pass out parameter via int_id
. If found,
return 0, returns -1 if not found.
int find (
const EXT_ID &ext_id,
ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry
);
ext_id
and pass out parameter via entry
. If found,
return 0, returns -1 if not found.
int unbind (const EXT_ID &ext_id);
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...)
int unbind (const EXT_ID &ext_id, INT_ID &int_id);
ext_id
. Returns the value of int_id
in case the caller needs to deallocate memory.
int unbind (ACE_RB_Tree_Node<EXT_ID, INT_ID> *entry);
size_t current_size (void);
void operator= (
const ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &rbt
);
virtual int lessthan (const EXT_ID &k1, const EXT_ID &k2);
ACE_LOCK &mutex (void);
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!
void dump (void) const;
ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> begin (
void
);
ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> end (
void
);
ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> rbegin (
void
);
ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> rend (
void
);
INT_ID* find (const EXT_ID &k);
DEPRECATED: signature will change to become
int find (const EXT_ID &ext_id); which will return
0 if the ext_id
is in the tree, otherwise -1.
INT_ID* insert (const EXT_ID &k, const INT_ID &t);
semantics. 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
int remove (const EXT_ID &k);
void clear (void);
void RB_rotate_right (ACE_RB_Tree_Node<EXT_ID, INT_ID> * x);
void RB_rotate_left (ACE_RB_Tree_Node<EXT_ID, INT_ID> * x);
void RB_delete_fixup (ACE_RB_Tree_Node<EXT_ID, INT_ID> * x);
RB_tree_successor (ACE_RB_Tree_Node<EXT_ID, INT_ID> *x) const;
RB_tree_predecessor (ACE_RB_Tree_Node<EXT_ID, INT_ID> *x) const;
RB_tree_minimum (ACE_RB_Tree_Node<EXT_ID, INT_ID> *x) const;
RB_tree_maximum (ACE_RB_Tree_Node<EXT_ID, INT_ID> *x) const;
find_node (const EXT_ID &k, RB_SearchResult &result);
void RB_rebalance (ACE_RB_Tree_Node<EXT_ID, INT_ID> * x);
int close_i (void);
int find_i (
const EXT_ID &ext_id,
ACE_RB_Tree_Node<EXT_ID, INT_ID>* &entry
);
INT_ID* insert_i (const EXT_ID &k, const INT_ID &t);
semantics. 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.
int insert_i (
const EXT_ID &k,
const INT_ID &t,
ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry
);
semantics. This method passes back
a pointer to the inserted (or existing) node, and the search status. If
the node already exists, the method returns 1. If the node does not
exist, and a new one is successfully created, and the method returns 0.
If there was an error, the method returns -1.
int remove_i (const EXT_ID &k, INT_ID &i);
int remove_i (ACE_RB_Tree_Node<EXT_ID, INT_ID> *z);
ACE_Allocator *allocator_;
ACE_LOCK lock_;
ACE_RB_Tree
.
ACE_RB_Tree_Node<EXT_ID, INT_ID> *root_;
COMPARE_KEYS compare_keys_;
size_t current_size_;
This class uses an ACE_Allocator
to allocate memory. The
user can make this a persistent class by providing an
ACE_Allocator
with a persistable memory pool.