#include <rbtree.h>

Public Member Functions
	RBTree ()

TNKV *	InsertBST (TNKV *newNode)

TNKV *	FindSumGreaterEqual (K key, S *sum)

TNKV *	FindSumGreaterThan (K key, S *sum)

void	UpdateSum (TNKV *node)

COLOR	GetColor (TNKV *const node)

void	SetColor (TNKV *node, COLOR color)

COLOR	GetColorUnconditional (TNKV *const node)

void	SetColorUnconditional (TNKV *node, COLOR color)

void	RotateLeft (TNKV *p)

void	RotateRightThenLeft (TNKV *x)

void	RotateRight (TNKV *p)

void	RotateLeftThenRight (TNKV *x)

void	BalanceInsertion (TNKV *x)

void	Insert (TNKV *newNode)

void	BalanceDeletion (TNKV *node)

TNKV *	DeleteHelper (TNKV *node)

TNKV *	WhichNodeToDelete (TNKV *node)

TNKV *	Delete (TNKV *node)

bool	IsBSTHelper (TNKV *node)

bool	IsBST ()

bool	IsSumCorrectHeler (TNKV *node, V &curSum)

bool	IsSumCorrect ()

bool	IsTreeCorrectHeler (TNKV *node)

bool	IsTreeCorrect ()

bool	IsReachableHelper (TNKV root, TNKV target)

bool	IsReachable (TNKV *target)

S	GetTotalSum ()

TNKV *	FindNodeAtRankFromRight (S capacity)

Private Types
using	TNKV = TreeNode< K, V, S >

Private Attributes
TreeNode< K, V, S > *	root

Detailed Description

template<class K, class V, class S>
class RBTree< K, V, S >

Definition at line 31 of file rbtree.h.

Member Typedef Documentation

◆ TNKV

template<class K , class V , class S >

using RBTree< K, V, S >::TNKV = TreeNode<K, V, S>

private

Definition at line 32 of file rbtree.h.

Constructor & Destructor Documentation

◆ RBTree()

template<class K , class V , class S >

RBTree< K, V, S >::RBTree ( )

inline

Definition at line 38 of file rbtree.h.

Member Function Documentation

◆ BalanceDeletion()

template<class K , class V , class S >

void RBTree< K, V, S >::BalanceDeletion ( TNKV * node )

inline

Definition at line 431 of file rbtree.h.

References BLACK, TreeNode< K, V, S >::color, RBTree< K, V, S >::GetColor(), RBTree< K, V, S >::GetColorUnconditional(), TreeNode< K, V, S >::left, TreeNode< K, V, S >::parent, RED, TreeNode< K, V, S >::right, RBTree< K, V, S >::root, RBTree< K, V, S >::RotateLeft(), RBTree< K, V, S >::RotateLeftThenRight(), RBTree< K, V, S >::RotateRight(), RBTree< K, V, S >::RotateRightThenLeft(), RBTree< K, V, S >::SetColor(), and RBTree< K, V, S >::SetColorUnconditional().

Referenced by RBTree< K, V, S >::Delete().

◆ BalanceInsertion()

template<class K , class V , class S >

void RBTree< K, V, S >::BalanceInsertion ( TNKV * x )

inline

Definition at line 346 of file rbtree.h.

References BLACK, TreeNode< K, V, S >::color, g(), TreeNode< K, V, S >::parent, RED, RBTree< K, V, S >::RotateLeft(), RBTree< K, V, S >::RotateLeftThenRight(), RBTree< K, V, S >::RotateRight(), RBTree< K, V, S >::RotateRightThenLeft(), and RBTree< K, V, S >::SetColorUnconditional().

Referenced by RBTree< K, V, S >::Insert().

◆ Delete()

template<class K , class V , class S >

TNKV* RBTree< K, V, S >::Delete ( TNKV * node )

inline

Definition at line 625 of file rbtree.h.

References RBTree< K, V, S >::BalanceDeletion(), TreeNode< K, V, S >::parent, RBTree< K, V, S >::root, TreeNode< K, V, S >::value, and RBTree< K, V, S >::WhichNodeToDelete().

Referenced by AnalyzeInsLevelReuse(), ComputeBlockReuseDistance(), ComputeInsReuseDistance(), and anonymous_namespace{rbtree_test.cpp}::TEST().

◆ DeleteHelper()

template<class K , class V , class S >

TNKV* RBTree< K, V, S >::DeleteHelper ( TNKV * node )

inline

Definition at line 526 of file rbtree.h.

References TreeNode< K, V, S >::key, TreeNode< K, V, S >::left, TreeNode< K, V, S >::parent, TreeNode< K, V, S >::payload, TreeNode< K, V, S >::right, RBTree< K, V, S >::root, and TreeNode< K, V, S >::value.

◆ FindNodeAtRankFromRight()

template<class K , class V , class S >

TNKV* RBTree< K, V, S >::FindNodeAtRankFromRight ( S capacity )

inline

Definition at line 786 of file rbtree.h.

References TreeNode< K, V, S >::left, TreeNode< K, V, S >::right, RBTree< K, V, S >::root, TreeNode< K, V, S >::sum, and TreeNode< K, V, S >::value.

Referenced by AnalyzeInsLevelReuse(), and CheckEvictions().

◆ FindSumGreaterEqual()

template<class K , class V , class S >

TNKV* RBTree< K, V, S >::FindSumGreaterEqual	(	K	key,
		S *	sum
	)

inline

Definition at line 78 of file rbtree.h.

References TreeNode< K, V, S >::key, TreeNode< K, V, S >::left, TreeNode< K, V, S >::right, RBTree< K, V, S >::root, TreeNode< K, V, S >::sum, and TreeNode< K, V, S >::value.

Referenced by anonymous_namespace{rbtree_test.cpp}::TEST().

◆ FindSumGreaterThan()

template<class K , class V , class S >

TNKV* RBTree< K, V, S >::FindSumGreaterThan	(	K	key,
		S *	sum
	)

inline

Definition at line 101 of file rbtree.h.

References TreeNode< K, V, S >::key, TreeNode< K, V, S >::left, TreeNode< K, V, S >::right, RBTree< K, V, S >::root, TreeNode< K, V, S >::sum, and TreeNode< K, V, S >::value.

Referenced by AnalyzeInsLevelReuse(), ComputeBlockReuseDistance(), and ComputeInsReuseDistance().

◆ GetColor()

template<class K , class V , class S >

COLOR RBTree< K, V, S >::GetColor ( TNKV *const node )

inline

Definition at line 128 of file rbtree.h.

References BLACK, and TreeNode< K, V, S >::color.

Referenced by RBTree< K, V, S >::BalanceDeletion().

◆ GetColorUnconditional()

template<class K , class V , class S >

COLOR RBTree< K, V, S >::GetColorUnconditional ( TNKV *const node )

inline

Definition at line 141 of file rbtree.h.

References TreeNode< K, V, S >::color.

Referenced by RBTree< K, V, S >::BalanceDeletion().

◆ GetTotalSum()

template<class K , class V , class S >

S RBTree< K, V, S >::GetTotalSum ( )

inline

Definition at line 777 of file rbtree.h.

References RBTree< K, V, S >::root.

Referenced by CheckEvictions().

◆ Insert()

template<class K , class V , class S >

void RBTree< K, V, S >::Insert ( TNKV * newNode )

inline

Definition at line 426 of file rbtree.h.

References RBTree< K, V, S >::BalanceInsertion(), and RBTree< K, V, S >::InsertBST().

Referenced by AnalyzeInsLevelReuse(), ComputeBlockReuseDistance(), ComputeInsReuseDistance(), and anonymous_namespace{rbtree_test.cpp}::TEST().

◆ InsertBST()

template<class K , class V , class S >

TNKV* RBTree< K, V, S >::InsertBST ( TNKV * newNode )

inline

Definition at line 42 of file rbtree.h.

References TreeNode< K, V, S >::color, TreeNode< K, V, S >::key, TreeNode< K, V, S >::left, TreeNode< K, V, S >::parent, RED, TreeNode< K, V, S >::right, RBTree< K, V, S >::root, TreeNode< K, V, S >::sum, and TreeNode< K, V, S >::value.

Referenced by RBTree< K, V, S >::Insert().

◆ IsBST()

template<class K , class V , class S >

bool RBTree< K, V, S >::IsBST ( )

inline

Definition at line 688 of file rbtree.h.

References RBTree< K, V, S >::IsBSTHelper(), and RBTree< K, V, S >::root.

Referenced by anonymous_namespace{rbtree_test.cpp}::TEST().

◆ IsBSTHelper()

template<class K , class V , class S >

bool RBTree< K, V, S >::IsBSTHelper ( TNKV * node )

inline

Definition at line 671 of file rbtree.h.

References TreeNode< K, V, S >::key, TreeNode< K, V, S >::left, and TreeNode< K, V, S >::right.

Referenced by RBTree< K, V, S >::IsBST().

◆ IsReachable()

template<class K , class V , class S >

bool RBTree< K, V, S >::IsReachable ( TNKV * target )

inline

Definition at line 773 of file rbtree.h.

References RBTree< K, V, S >::IsReachableHelper(), and RBTree< K, V, S >::root.

◆ IsReachableHelper()

template<class K , class V , class S >

bool RBTree< K, V, S >::IsReachableHelper	(	TNKV *	root,
		TNKV *	target
	)

inline

Definition at line 757 of file rbtree.h.

References RBTree< K, V, S >::root.

Referenced by RBTree< K, V, S >::IsReachable().

◆ IsSumCorrect()

template<class K , class V , class S >

bool RBTree< K, V, S >::IsSumCorrect ( )

inline

Definition at line 719 of file rbtree.h.

References RBTree< K, V, S >::IsSumCorrectHeler(), and RBTree< K, V, S >::root.

Referenced by anonymous_namespace{rbtree_test.cpp}::TEST().

◆ IsSumCorrectHeler()

template<class K , class V , class S >

bool RBTree< K, V, S >::IsSumCorrectHeler	(	TNKV *	node,
		V &	curSum
	)

inline

Definition at line 695 of file rbtree.h.

References TreeNode< K, V, S >::left, TreeNode< K, V, S >::right, TreeNode< K, V, S >::sum, and TreeNode< K, V, S >::value.

Referenced by RBTree< K, V, S >::IsSumCorrect().

◆ IsTreeCorrect()

template<class K , class V , class S >

bool RBTree< K, V, S >::IsTreeCorrect ( )

inline

Definition at line 750 of file rbtree.h.

References RBTree< K, V, S >::IsTreeCorrectHeler(), and RBTree< K, V, S >::root.

Referenced by anonymous_namespace{rbtree_test.cpp}::TEST().

◆ IsTreeCorrectHeler()

template<class K , class V , class S >

bool RBTree< K, V, S >::IsTreeCorrectHeler ( TNKV * node )

inline

Definition at line 727 of file rbtree.h.

References TreeNode< K, V, S >::color, TreeNode< K, V, S >::left, TreeNode< K, V, S >::parent, RED, and TreeNode< K, V, S >::right.

Referenced by RBTree< K, V, S >::IsTreeCorrect().

◆ RotateLeft()

template<class K , class V , class S >

void RBTree< K, V, S >::RotateLeft ( TNKV * p )

inline

Definition at line 166 of file rbtree.h.

References g(), TreeNode< K, V, S >::left, TreeNode< K, V, S >::parent, TreeNode< K, V, S >::right, RBTree< K, V, S >::root, and RBTree< K, V, S >::UpdateSum().

Referenced by RBTree< K, V, S >::BalanceDeletion(), and RBTree< K, V, S >::BalanceInsertion().

◆ RotateLeftThenRight()

template<class K , class V , class S >

void RBTree< K, V, S >::RotateLeftThenRight ( TNKV * x )

inline

Definition at line 308 of file rbtree.h.

References g(), TreeNode< K, V, S >::left, TreeNode< K, V, S >::parent, TreeNode< K, V, S >::right, RBTree< K, V, S >::root, and RBTree< K, V, S >::UpdateSum().

Referenced by RBTree< K, V, S >::BalanceDeletion(), and RBTree< K, V, S >::BalanceInsertion().

◆ RotateRight()

template<class K , class V , class S >

void RBTree< K, V, S >::RotateRight ( TNKV * p )

inline

Definition at line 263 of file rbtree.h.

References g(), TreeNode< K, V, S >::left, TreeNode< K, V, S >::parent, TreeNode< K, V, S >::right, RBTree< K, V, S >::root, and RBTree< K, V, S >::UpdateSum().

Referenced by RBTree< K, V, S >::BalanceDeletion(), and RBTree< K, V, S >::BalanceInsertion().

◆ RotateRightThenLeft()

template<class K , class V , class S >

void RBTree< K, V, S >::RotateRightThenLeft ( TNKV * x )

inline

Definition at line 210 of file rbtree.h.

References g(), TreeNode< K, V, S >::left, TreeNode< K, V, S >::parent, TreeNode< K, V, S >::right, RBTree< K, V, S >::root, and RBTree< K, V, S >::UpdateSum().

Referenced by RBTree< K, V, S >::BalanceDeletion(), and RBTree< K, V, S >::BalanceInsertion().

◆ SetColor()

template<class K , class V , class S >

void RBTree< K, V, S >::SetColor	(	TNKV *	node,
		COLOR	color
	)

inline

Definition at line 135 of file rbtree.h.

References TreeNode< K, V, S >::color.

Referenced by RBTree< K, V, S >::BalanceDeletion().

◆ SetColorUnconditional()

template<class K , class V , class S >

void RBTree< K, V, S >::SetColorUnconditional	(	TNKV *	node,
		COLOR	color
	)

inline

Definition at line 146 of file rbtree.h.

References TreeNode< K, V, S >::color.

Referenced by RBTree< K, V, S >::BalanceDeletion(), and RBTree< K, V, S >::BalanceInsertion().

◆ UpdateSum()

template<class K , class V , class S >

void RBTree< K, V, S >::UpdateSum ( TNKV * node )

inline

Definition at line 124 of file rbtree.h.

References TreeNode< K, V, S >::left, TreeNode< K, V, S >::right, TreeNode< K, V, S >::sum, and TreeNode< K, V, S >::value.

Referenced by RBTree< K, V, S >::RotateLeft(), RBTree< K, V, S >::RotateLeftThenRight(), RBTree< K, V, S >::RotateRight(), and RBTree< K, V, S >::RotateRightThenLeft().

◆ WhichNodeToDelete()

template<class K , class V , class S >

TNKV* RBTree< K, V, S >::WhichNodeToDelete ( TNKV * node )

inline

Definition at line 583 of file rbtree.h.

References TreeNode< K, V, S >::key, TreeNode< K, V, S >::left, TreeNode< K, V, S >::parent, TreeNode< K, V, S >::payload, TreeNode< K, V, S >::right, TreeNode< K, V, S >::sum, and TreeNode< K, V, S >::value.

Referenced by RBTree< K, V, S >::Delete().

Member Data Documentation

◆ root

template<class K , class V , class S >

TreeNode<K, V, S>* RBTree< K, V, S >::root

private

Definition at line 35 of file rbtree.h.

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

src/rbtree.h

Public Member Functions

Private Types

Private Attributes

Detailed Description

template<class K, class V, class S> class RBTree< K, V, S >

Member Typedef Documentation

◆ TNKV

Constructor & Destructor Documentation

◆ RBTree()

Member Function Documentation

◆ BalanceDeletion()

◆ BalanceInsertion()

◆ Delete()

◆ DeleteHelper()

◆ FindNodeAtRankFromRight()

◆ FindSumGreaterEqual()

◆ FindSumGreaterThan()

◆ GetColor()

◆ GetColorUnconditional()

◆ GetTotalSum()

◆ Insert()

◆ InsertBST()

◆ IsBST()

◆ IsBSTHelper()

◆ IsReachable()

◆ IsReachableHelper()

◆ IsSumCorrect()

◆ IsSumCorrectHeler()

◆ IsTreeCorrect()

◆ IsTreeCorrectHeler()

◆ RotateLeft()

◆ RotateLeftThenRight()

◆ RotateRight()

◆ RotateRightThenLeft()

◆ SetColor()

◆ SetColorUnconditional()

◆ UpdateSum()

◆ WhichNodeToDelete()

Member Data Documentation

◆ root

template<class K, class V, class S>
class RBTree< K, V, S >