cookmem::PtrRBNode Class Reference

#include <rbtree.h>

Public Types
typedef PtrRBNode	SelfType
typedef std::size_t	ValueType

Public Member Functions
void	init (ValueType value, SelfType *parentNode)
ValueType	getValue () const
SelfType **	getChildren ()
SelfType *const *	getChildren () const
SelfType *	getLeft ()
const SelfType *	getLeft () const
void	setLeft (SelfType *left)
SelfType *	getRight ()
const SelfType *	getRight () const
void	setRight (SelfType *right)
SelfType *	getParent ()
const SelfType *	getParent () const
void	setParent (SelfType *parentNode)
void	addList (SelfType *other)
bool	hasList () const
bool	isInList () const
SelfType *	getNext ()
const SelfType *	getNext () const
SelfType *	removeFromList ()
void	unlinkFromList ()
SelfType *	promoteFirstListNode ()
bool	isRed () const
void	setRed (bool red)

Detailed Description

The node of RedBlackTree, which is stored in the memory being tracked.

The memory pool places this node at the start of a free chunk, so its layout must match the chunk header: the second word (m_size) is both the value of the node and the size field of the chunk. The memory must be at least sizeof(PtrRBNode) (7 words) large.

Nodes with the same value are kept in a doubly linked list (DLL) attached to the one node that is in the tree.

Member Typedef Documentation

SelfType

typedef PtrRBNode cookmem::PtrRBNode::SelfType

The type of this node.

ValueType

typedef std::size_t cookmem::PtrRBNode::ValueType

The type of the value (the size of the memory).

Member Function Documentation

addList()

void cookmem::PtrRBNode::addList ( SelfType *  other )

inline

Add a node of the same value to the DLL of this tree node.

A list node uses m_children[0] as the pointer to its previous node, which is either another list node or the tree node itself. List nodes do not use m_parent or m_children[1].

getChildren() [1/2]

SelfType ** cookmem::PtrRBNode::getChildren ( )

inline

Get the left and right child pointers as an array.

getChildren() [2/2]

SelfType *const * cookmem::PtrRBNode::getChildren ( ) const

inline

Get the left and right child pointers as an array.

getLeft() [1/2]

SelfType * cookmem::PtrRBNode::getLeft ( )

inline

Get the left child, or the previous node for a list node.

getLeft() [2/2]

const SelfType * cookmem::PtrRBNode::getLeft ( ) const

inline

Get the left child, or the previous node for a list node.

getNext() [1/2]

SelfType * cookmem::PtrRBNode::getNext ( )

inline

Get the next node in the DLL of nodes with the same value.

getNext() [2/2]

const SelfType * cookmem::PtrRBNode::getNext ( ) const

inline

Get the next node in the DLL of nodes with the same value.

getParent() [1/2]

SelfType * cookmem::PtrRBNode::getParent ( )

inline

Get the parent node, or nullptr for the root.

getParent() [2/2]

const SelfType * cookmem::PtrRBNode::getParent ( ) const

inline

Get the parent node, or nullptr for the root.

getRight() [1/2]

SelfType * cookmem::PtrRBNode::getRight ( )

inline

Get the right child.

getRight() [2/2]

const SelfType * cookmem::PtrRBNode::getRight ( ) const

inline

Get the right child.

getValue()

ValueType cookmem::PtrRBNode::getValue ( ) const

inline

Get the value of the node.

hasList()

bool cookmem::PtrRBNode::hasList ( ) const

inline

Check if this tree node has a DLL of nodes with the same value.

init()

void cookmem::PtrRBNode::init ( ValueType  value, SelfType *  parentNode  )

inline

Initialize the node as a red leaf.

Parameters

value	the value of the node.
parentNode	the parent node, or nullptr for the root.

isInList()

bool cookmem::PtrRBNode::isInList ( ) const

inline

Check if this node is in the DLL of a tree node, rather than being a node of the tree itself.

isRed()

bool cookmem::PtrRBNode::isRed ( ) const

inline

Check if the node is red.

promoteFirstListNode()

SelfType * cookmem::PtrRBNode::promoteFirstListNode ( )

inline

Replace the tree node with the first node in its DLL. The first list node takes over the position, color and the rest of the list, so this takes constant time. The list must not be empty.

Returns

the replacement node, which is now a tree node.

removeFromList()

SelfType * cookmem::PtrRBNode::removeFromList ( )

inline

Remove the first node in the DLL of this tree node. The list must not be empty.

Returns

the node removed.

setLeft()

void cookmem::PtrRBNode::setLeft ( SelfType *  left )

inline

Set the left child.

setParent()

void cookmem::PtrRBNode::setParent ( SelfType *  parentNode )

inline

Set the parent node.

setRed()

void cookmem::PtrRBNode::setRed ( bool  red )

inline

Set the node to be red or black.

setRight()

void cookmem::PtrRBNode::setRight ( SelfType *  right )

inline

Set the right child.

unlinkFromList()

void cookmem::PtrRBNode::unlinkFromList ( )

inline

Unlink this list node from the DLL it is in.

---

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

• rbtree.h