cookmem::RedBlackTree< Node > Class Template Reference

#include <rbtree.h>

Public Types
typedef Node	NodeType
typedef NodeType::ValueType	ValueType

Public Member Functions
void	add (void *ptr, ValueType value)
NodeType *	getRoot ()
NodeType *	remove (ValueType &size, ValueType limit=~static_cast< ValueType >(0))
void	remove (void *ptr)
bool	contains (void *ptr)
bool	canGrowInPlace (void *ptr, ValueType newValue)
bool	isEmpty () const

Detailed Description

template<class Node>
class cookmem::RedBlackTree< Node >

This class defines a Red-Black Tree.

Template Parameters

Node	Any classes similar to PtrRBNode

Member Typedef Documentation

NodeType

template<class Node >

typedef Node cookmem::RedBlackTree< Node >::NodeType

The type of the tree nodes.

ValueType

template<class Node >

typedef NodeType::ValueType cookmem::RedBlackTree< Node >::ValueType

The type of the node values.

Member Function Documentation

add()

template<class Node >

void cookmem::RedBlackTree< Node >::add ( void *  ptr, ValueType  value  )

inline

Add a pointer to the search tree.

Note that the size of the pointer must be at least (7 * sizeof(size_t)).

Parameters

ptr	the pointer to be added to the red-black tree.
value	the size of the pointer

canGrowInPlace()

template<class Node >

bool cookmem::RedBlackTree< Node >::canGrowInPlace ( void *  ptr, ValueType  newValue  )

inline

Check if a node in the tree can take a larger value without changing its position in the tree. If so, the caller can update the value in place instead of removing the node and adding it back.

Parameters

ptr	the pointer stored in the tree.
newValue	the new value, which must be larger than the current value.

Returns

true if the value can be updated in place.

contains()

template<class Node >

bool cookmem::RedBlackTree< Node >::contains ( void *  ptr )

inline

Check if the pointer is stored in the tree.

Parameters

ptr	the pointer to be searched.

getRoot()

template<class Node >

NodeType * cookmem::RedBlackTree< Node >::getRoot ( )

inline

Get the root node. This is mostly for testing.

Returns

the root node, or nullptr if the tree is empty.

isEmpty()

template<class Node >

bool cookmem::RedBlackTree< Node >::isEmpty ( ) const

inline

Check if the tree is empty.

Returns

true if the tree is empty. false otherwise.

remove() [1/2]

template<class Node >

NodeType * cookmem::RedBlackTree< Node >::remove ( ValueType &  size, ValueType  limit = ~static_cast<ValueType> (0)  )

inline

Remove a node based on the size information. The node obtained has the size that at least the size obtained.

Parameters

[in,out]	size	search key. If the node is found, the actual size of the pointer is returned.
	limit	the node must be smaller than this value. Otherwise nothing is removed.

Returns

the node matching the search key that is at least the size of the provided. This node is also removed from the tree.

remove() [2/2]

template<class Node >

void cookmem::RedBlackTree< Node >::remove ( void *  ptr )

inline

Remove a node based on the pointer info.

Parameters

ptr	the pointer to be removed from the tree

---

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

• rbtree.h