RBTreeBase Class Reference

Base class for red-black tree implementation. More...

#include <RBTree.h>

Inheritance diagram for RBTreeBase:

Collaboration diagram for RBTreeBase:

List of all members.

Classes
class	EntryBase
	Tree node represented by this class. More...
Public Member Functions
bool	Validate ()
	Validate the tree.
Protected Member Functions
virtual int	Compare (EntryBase *e1, EntryBase *e2)=0
	This method should be overloaded in derived class.
virtual int	Compare (EntryBase *e, void *key)=0
	This method should be overloaded in derived class.
EntryBase *	InsertNode (EntryBase *node)
	Insert node in the tree.
EntryBase *	GetNextNode (EntryBase *node=0)
	Get next tree node during the tree traversal.
EntryBase *	Lookup (void *key)
	Lookup tree node by key.
void	Delete (EntryBase *entry)
	Delete a node from the tree.
EntryBase *	Lowest ()
	Get the node with the lowest value.
EntryBase *	Highest ()
	Get the node with the highest value.

---

Detailed Description

Base class for red-black tree implementation.

---

Member Function Documentation

virtual int RBTreeBase::Compare	(	EntryBase *	e1,
		EntryBase *	e2
	)		[protected, pure virtual]

This method should be overloaded in derived class.

It must compare two nodes.

Parameters:

e1	The first node to compare.
e2	The second node to compare.

Returns:

Positive value if e1 greater than e2, negative value if e1 less than e2, zero if e1 equal to e2.

Implemented in RBTree< T, Comparator, key_t, KeyComparator >, and RBTree< CacheEntry,&CacheEntry::Compare, Addr,&CacheEntry::Compare >.

virtual int RBTreeBase::Compare	(	EntryBase *	e,
		void *	key
	)		[protected, pure virtual]

This method should be overloaded in derived class.

It must compare a node with a key.

Parameters:

e	Node to compare.
key	Pointer to a key.

Returns:

Positive value if key is greater than e, negative value if key is less than e, zero if key is equal to e.

Implemented in RBTree< T, Comparator, key_t, KeyComparator >, and RBTree< CacheEntry,&CacheEntry::Compare, Addr,&CacheEntry::Compare >.

void RBTreeBase::Delete

(

EntryBase *

entry

)

[protected]

Delete a node from the tree.

Parameters:

entry

Node to delete.

RBTreeBase::EntryBase * RBTreeBase::GetNextNode

(

EntryBase *

node = 0

)

[protected]

Get next tree node during the tree traversal.

Parameters:

node	Previously visited node. Can be NULL to get the first node.

Returns:

Next node. NULL if all nodes traversed.

RBTreeBase::EntryBase * RBTreeBase::Highest

(

)

[protected]

Get the node with the highest value.

Returns:

Node with the highest value, NULL if the tree is empty.

Reimplemented in RBTree< T, Comparator, key_t, KeyComparator >, and RBTree< CacheEntry,&CacheEntry::Compare, Addr,&CacheEntry::Compare >.

RBTreeBase::EntryBase * RBTreeBase::InsertNode

(

EntryBase *

node

)

[protected]

Insert node in the tree.

This method either inserts the node or finds existing node with the same key.

Parameters:

node	Node to insert.

Returns:

Either node if it was inserted or existing node with the same key (node is not inserted in the tree in such case).

RBTreeBase::EntryBase * RBTreeBase::Lookup

(

void *

key

)

[protected]

Lookup tree node by key.

Parameters:

key	Pointer to key.

Returns:

Pointer to found node, 0 if nothing is found.

RBTreeBase::EntryBase * RBTreeBase::Lowest

(

)

[protected]

Get the node with the lowest value.

Returns:

Node with the lowest value, NULL if the tree is empty.

Reimplemented in RBTree< T, Comparator, key_t, KeyComparator >, and RBTree< CacheEntry,&CacheEntry::Compare, Addr,&CacheEntry::Compare >.

bool RBTreeBase::Validate

(

)

Validate the tree.

This method is intended for tree implementation troubleshooting and normally is not required to be used.

Returns:

true if the tree is valid red-black tree, false if there are some rules violations or dis-integrity.

---

The documentation for this class was generated from the following files:

• include/common/RBTree.h
• lib/common/RBTree.cpp