Though the standard template library includes std::map, commonly implemented as a Red Black tree, this alternative provides a transparent mechanism for the user to manage all of the memory used by the tree. More...

#include <RBTree.hxx>

Classes
struct	Node
	The metadata for a tree node. More...

Public Member Functions
	RBTree ()
	Default Constructor.

	RBTree (size_t nodes)
	Default Constructor.

Node *	insert (Key key, Value value)
	Insert a node into the tree from pre-allocated Node pool.

void	insert (Node *node)
	Insert a node into the tree.

void	remove (Node *node)
	Remove a node from the tree.

Node *	remove (Key key)
	Remove a node from the tree.

Node *	find (Key key)
	Find a node based on its lookup key.

Node *	first ()
	Get the first node in the tree.

Node *	last ()
	Get the last node in the tree.

Node *	next (Node *node)
	Get the next node in the tree.

Node *	next (Key key)
	Get the next node in the tree.

Node *	previous (Node *node)
	Get the previous node in the tree.

	~RBTree ()
	Default destructor.

Private Member Functions
Node *	alloc ()
	Allocate a node from the free list.

void	free (Node *node)
	free a node to the free list if it exists.

Key	compare (Node a, Node b)
	Compare two nodes.

	RB_HEAD (tree, Node)
	The datagram tree type.

	RB_GENERATE (tree, Node, entry, compare)
	The datagram tree methods.

	DISALLOW_COPY_AND_ASSIGN (RBTree)

Private Attributes
Node *	freeList
	list of free nodes

struct tree	head
	tree instance

Detailed Description

template<typename Key, typename Value>
class RBTree< Key, Value >

Though the standard template library includes std::map, commonly implemented as a Red Black tree, this alternative provides a transparent mechanism for the user to manage all of the memory used by the tree.

This allows for a instantiation that does not require the dynamic allocation and freeing of small chunks of memory. Note, there is no mutual exclusion locking mechanism built into this class. Mutual exclusion must be handled by the user as needed.

Definition at line 52 of file RBTree.hxx.

Constructor & Destructor Documentation

◆ RBTree() [1/2]

template<typename Key , typename Value >

RBTree< Key, Value >::RBTree ( )

inline

Default Constructor.

Definition at line 57 of file RBTree.hxx.

◆ RBTree() [2/2]

template<typename Key , typename Value >

RBTree< Key, Value >::RBTree ( size_t nodes )

inline

Default Constructor.

Parameters

nodes number of nodes to statically create and track

Definition at line 66 of file RBTree.hxx.

◆ ~RBTree()

template<typename Key , typename Value >

RBTree< Key, Value >::~RBTree ( )

inline

Default destructor.

Definition at line 222 of file RBTree.hxx.

Member Function Documentation

◆ alloc()

template<typename Key , typename Value >

Node * RBTree< Key, Value >::alloc ( )

inlineprivate

Allocate a node from the free list.

Returns: newly allocated node, else NULL if no free nodes left

Definition at line 230 of file RBTree.hxx.

◆ compare()

template<typename Key , typename Value >

Key RBTree< Key, Value >::compare	(	Node *	a,
		Node *	b
	)

inlineprivate

Compare two nodes.

Parameters

a	first of two nodes to compare
b	second of two nodes to compare

Returns: difference between node keys (a->key - b->key)

Definition at line 258 of file RBTree.hxx.

◆ find()

template<typename Key , typename Value >

Node * RBTree< Key, Value >::find ( Key key )

inline

Find a node based on its lookup key.

Parameters

key	key of node to lookup.

Returns: pointer to node found, NULL if not found

Definition at line 168 of file RBTree.hxx.

◆ first()

template<typename Key , typename Value >

Node * RBTree< Key, Value >::first ( )

inline

Get the first node in the tree.

Returns: first node in the tree, NULL if tree is empty

Definition at line 180 of file RBTree.hxx.

◆ free()

template<typename Key , typename Value >

void RBTree< Key, Value >::free ( Node * node )

inlineprivate

free a node to the free list if it exists.

Parameters

node	node to free

Definition at line 244 of file RBTree.hxx.

◆ insert() [1/2]

template<typename Key , typename Value >

Node * RBTree< Key, Value >::insert	(	Key	key,
		Value	value
	)

inline

Insert a node into the tree from pre-allocated Node pool.

Parameters

key	key to insert
value	value to insert

Returns: reference to new node inserted, existing matching node, or NULL if there are no more pre-allocated nodes left

Definition at line 112 of file RBTree.hxx.

◆ insert() [2/2]

template<typename Key , typename Value >

void RBTree< Key, Value >::insert ( Node * node )

inline

Insert a node into the tree.

Parameters

node to insert

Definition at line 135 of file RBTree.hxx.

◆ last()

template<typename Key , typename Value >

Node * RBTree< Key, Value >::last ( )

inline

Get the last node in the tree.

Returns: last node in the tree, NULL if tree is empty

Definition at line 188 of file RBTree.hxx.

◆ next() [1/2]

template<typename Key , typename Value >

Node * RBTree< Key, Value >::next ( Key key )

inline

Get the next node in the tree.

Parameters

key	key of the node to get the next node from

Returns: next node in the tree, NULL if at the end of the tree

Definition at line 206 of file RBTree.hxx.

◆ next() [2/2]

template<typename Key , typename Value >

Node * RBTree< Key, Value >::next ( Node * node )

inline

Get the next node in the tree.

Parameters

node	node to get the next node from

Returns: next node in the tree, NULL if at the end of the tree

Definition at line 197 of file RBTree.hxx.

◆ previous()

template<typename Key , typename Value >

Node * RBTree< Key, Value >::previous ( Node * node )

inline

Get the previous node in the tree.

Parameters

node	node to get the previous node from

Returns: previous node in the tree, NULL if at the beginning of the tree

Definition at line 216 of file RBTree.hxx.

◆ remove() [1/2]

template<typename Key , typename Value >

Node * RBTree< Key, Value >::remove ( Key key )

inline

Remove a node from the tree.

Parameters

key	key for the node to remove

Returns: pointer to node that was removed, NULL if not found

Definition at line 153 of file RBTree.hxx.

◆ remove() [2/2]

template<typename Key , typename Value >

void RBTree< Key, Value >::remove ( Node * node )

inline

Remove a node from the tree.

Parameters

node	node to remove

Definition at line 143 of file RBTree.hxx.

Member Data Documentation

◆ freeList

template<typename Key , typename Value >

Node* RBTree< Key, Value >::freeList

private

list of free nodes

Definition at line 264 of file RBTree.hxx.

◆ head

template<typename Key , typename Value >

struct tree RBTree< Key, Value >::head

private

tree instance

Definition at line 273 of file RBTree.hxx.

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

RBTree.hxx

Classes

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ RBTree() [1/2]

◆ RBTree() [2/2]

◆ ~RBTree()

Member Function Documentation

◆ alloc()

◆ compare()

◆ find()

◆ first()

◆ free()

◆ insert() [1/2]

◆ insert() [2/2]

◆ last()

◆ next() [1/2]

◆ next() [2/2]

◆ previous()

◆ remove() [1/2]

◆ remove() [2/2]

Member Data Documentation

◆ freeList

◆ head