Intrusive Binary Tree, Node. More...

#include <BalTreeIn.h>

Inheritance diagram for BalTreeInNode< R, N, K, s, n >:

[legend]

Collaboration diagram for BalTreeInNode< R, N, K, s, n >:

[legend]

Protected Member Functions
	BalTreeInNode ()
	Constructor.

virtual	~BalTreeInNode ()
	Destructor.

void	addTo (R &root)
	Add ourself to a tree.

void	addTo (R *root)
	Add ourself to a tree.

bool	check () const override

N *	left () const

N *	next () const

N *	parent () const

N *	prev () const

unsigned	readLock (bool upgrade) const

void	readUnlock (unsigned save) const

void	rebalance () override=0
	Hook to allow Balanced trees to rebalance from current node, just changed.

virtual void	remove ()
	Remove node from whatever tree it is on, if it is on a tree.

void	resort ()

N *	right () const

R *	root () const

N *	rotateLeft ()
	Balance tree with a Left Rotate.

N *	rotateRight ()
	Balance Tree with a Right Rotate.

void	setRoot (C *root)
	Set our Container.

void	setRoot (R *root)

unsigned	writeLock (bool upgrade) const

void	writeUnlock (unsigned save) const

Private Types
typedef class TreeInNode< R, N, K, s, n >	Base

typedef Container< s >	C
	The type of the Container that we are part of.

typedef class BalTreeInNode< R, N, K, s, n >	Node
	Type of Node.

typedef class BalTreeInRoot< R, N, K, s, n >	Root
	Type of Root.

Private Attributes
N *	m_left
	Pointer to left (lesser) child node on tree.

N *	m_parent
	Pointer to parent node on tree.

N *	m_right
	Pointer to right (greater) child node on tree.

R *	m_root
	Pointer to tree we are on.

Friends
class	BalTreeInRoot< R, N, K, s, n >

Detailed Description

template<class R, class N, class K, ContainerThreadSafety s, int n>
class BalTreeInNode< R, N, K, s, n >

Intrusive Binary Tree, Node.

Template Parameters

R	The class that will be the owner of the List. Must derive from TreeInRoot<R, N, K, n>
N	The class that will be the nodes of the List. Must derive from TreeInNode<R, N, K, n>
K	The class defining the Key used to lookup Nodes in the tree.
s	The ContainerThreadSafety value to define the thread safety model of the Container
n	A numerical parameter to allow a give List/Node combination to have multiple list-node relationships. Defaults to 0 if not provided.

Invariant

From TreeInNode:

if m_root == NULL: // Free Node
- m_parent == NULL
- m_left == NULL
- m_right == NULL

if m_root != NULL and m_parent == NULL // Base Node
- m_root->m_base == this
if m_parent != nullptr: // Child Node
- Either m_parent->m_left or parent->m_right == this
if m_left != nullptr
- m_left->m_parent = this
- m_left->m_root == m_root
- m_root->compare(*this, *m_left) <= 0
- m_root->compare(*m_left, *this) >= 0
if m_right != nullptr:
- m_right->m_parent = this
- m_right->m_root == m_root
- m_root->compare(*this, *m_right) >= 0
- m_root->compare(*m_right, *this) <= 0

See also: BalTreeInRoot

Member Typedef Documentation

◆ Base

template<class R , class N , class K , ContainerThreadSafety s, int n>

class TreeInNode< R, N, K, s, n > BalTreeInNode< R, N, K, s, n >::Base

private

◆ C

template<ContainerThreadSafety s>

Container<s> ContainerNode< s >::C

privateinherited

The type of the Container that we are part of.

◆ Node

template<class R , class N , class K , ContainerThreadSafety s, int n>

class BalTreeInNode< R, N, K, s, n > BalTreeInNode< R, N, K, s, n >::Node

private

Type of Node.

◆ Root

template<class R , class N , class K , ContainerThreadSafety s, int n>

class BalTreeInRoot< R, N, K, s, n > BalTreeInNode< R, N, K, s, n >::Root

private

Type of Root.

Constructor & Destructor Documentation

◆ BalTreeInNode()

template<class R , class N , class K , ContainerThreadSafety s, int n>

BalTreeInNode< R, N, K, s, n >::BalTreeInNode ( )

protected

Constructor.

◆ ~BalTreeInNode()

template<class R , class N , class K , ContainerThreadSafety s, int n>

BalTreeInNode< R, N, K, s, n >::~BalTreeInNode ( )

protectedvirtual

Destructor.

Member Function Documentation

◆ addTo() [1/2]

template<class R , class N , class K , ContainerThreadSafety s, int n>

void TreeInNode< R, N, K, s, n >::addTo ( R & myroot )

protectedinherited

Add ourself to a tree.

Parameters

myroot Tree to add to.

◆ addTo() [2/2]

template<class R , class N , class K , ContainerThreadSafety s, int n>

void TreeInNode< R, N, K, s, n >::addTo ( R * myroot )

protectedinherited

Add ourself to a tree.

Parameters

myroot Tree to add to.

◆ check()

template<class R , class N , class K , ContainerThreadSafety s, int n>

bool BalTreeInNode< R, N, K, s, n >::check ( ) const

inlineoverrideprotectedvirtual

Implements ContainerNode< s >.

◆ left()

template<class R , class N , class K , ContainerThreadSafety s, int n>

N * BalTreeInNode< R, N, K, s, n >::left ( ) const

inlineprotected

◆ next()

template<class R , class N , class K , ContainerThreadSafety s, int n>

N * BalTreeInNode< R, N, K, s, n >::next ( ) const

inlineprotected

◆ parent()

template<class R , class N , class K , ContainerThreadSafety s, int n>

N * BalTreeInNode< R, N, K, s, n >::parent ( ) const

inlineprotected

◆ prev()

template<class R , class N , class K , ContainerThreadSafety s, int n>

N * BalTreeInNode< R, N, K, s, n >::prev ( ) const

inlineprotected

◆ readLock()

template<class R , class N , class K , ContainerThreadSafety s, int n>

unsigned BalTreeInNode< R, N, K, s, n >::readLock ( bool upgrade ) const

inlineprotected

References ContainerNode< s >::readLock().

Here is the call graph for this function:

◆ readUnlock()

template<class R , class N , class K , ContainerThreadSafety s, int n>

void BalTreeInNode< R, N, K, s, n >::readUnlock ( unsigned save ) const

inlineprotected

References ContainerNode< s >::readUnlock().

Here is the call graph for this function:

◆ rebalance()

template<class R , class N , class K , ContainerThreadSafety s, int n>

void BalTreeInNode< R, N, K, s, n >::rebalance ( )

overrideprotectedpure virtual

Hook to allow Balanced trees to rebalance from current node, just changed.

Reimplemented from TreeInNode< R, N, K, s, n >.

Implemented in AATreeInNode< R, N, K, s, n >.

◆ remove()

template<class R , class N , class K , ContainerThreadSafety s, int n>

void TreeInNode< R, N, K, s, n >::remove ( )

inlineprotectedvirtualinherited

Remove node from whatever tree it is on, if it is on a tree.

   Delete Node N

   Simple Cases, Not both childern (x is empty link)

   P     P    P    P    P    P
   | =>  x    | => |    | => |
   N          N    L    N    R
  x x        / x         \
            L             R

   Rebalance at P

More Complicated, as we have both childern

   More Complicated                    Special Case

   P                  P                P        P
   |      =>          |                |   =>   |
   N                  D                N        L
  / \                / \              / \      / \
 L   R              L   R            L   R    A   R
  \                  \              / x
   A                  A            A
    \                  \
     B                  B
      \                  \
       D                  C
      / x
     C

 Rebalance at B.  D might be L if it had no right child in which case rebalance at L

 L < A < B < C < D < N < R

 Link to P either a left or right, or Root if P is NULL.
 x indicates NULL links

◆ resort()

template<class R , class N , class K , ContainerThreadSafety s, int n>

void TreeInNode< R, N, K, s, n >::resort ( )

protectedinherited

◆ right()

template<class R , class N , class K , ContainerThreadSafety s, int n>

N * BalTreeInNode< R, N, K, s, n >::right ( ) const

inlineprotected

◆ root()

template<class R , class N , class K , ContainerThreadSafety s, int n>

R * BalTreeInNode< R, N, K, s, n >::root ( ) const

inlineprotected

◆ rotateLeft()

template<class R , class N , class K , ContainerThreadSafety s, int n>

N * BalTreeInNode< R, N, K, s, n >::rotateLeft ( )

protected

Balance tree with a Left Rotate.

Given A < L < B < R < C
Either P < A, or C < P
(A, B, C are subtrees, relations apply to ALL members in that subtree)

      P                        P
      |                        |
      R    Rotate Right =>     L
     / \   <= Rotate Left     / \
    L   C                    A   R
   / \                          / \
  A   B                        B   C

Rotate Right moves the current node to the right of the node on its left Rotate Left moves the current to to the left of the node on its right.

Caller should have an upgradable read-lock

Anyone walking the tree should have a readLock that we will wait to be released.

Returns: New subtree root after rotation.

◆ rotateRight()

template<class R , class N , class K , ContainerThreadSafety s, int n>

N * BalTreeInNode< R, N, K, s, n >::rotateRight ( )

protected

Balance Tree with a Right Rotate.

See also: rotateLeft

Returns: new subtree root after rotation.

◆ setRoot() [1/2]

template<ContainerThreadSafety s>

void ContainerNode< s >::setRoot ( C * root )

inlineprotectedinherited

Set our Container.

Used to allow to Node to record what Container it is in. Used only if safety method need resources from the Container, like a Mutex

If an operation changes the root of a node, then it needs to save the original root to exit the critical section on that container that it entered before the operation.

Referenced by ContainerNode< s >::ContainerNode(), DListInNode< R, N, s, n >::setRoot(), ListInNode< R, N, s, n >::setRoot(), and TreeInNode< R, N, K, s, n >::setRoot().

Here is the caller graph for this function:

◆ setRoot() [2/2]

template<class R , class N , class K , ContainerThreadSafety s, int n>

void TreeInNode< R, N, K, s, n >::setRoot ( R * root )

inlineprotectedinherited

References TreeInNode< R, N, K, s, n >::m_root, TreeInNode< R, N, K, s, n >::root(), and ContainerNode< s >::setRoot().

Here is the call graph for this function:

◆ writeLock()

template<class R , class N , class K , ContainerThreadSafety s, int n>

unsigned BalTreeInNode< R, N, K, s, n >::writeLock ( bool upgrade ) const

inlineprotected

References ContainerNode< s >::writeLock().

Here is the call graph for this function:

◆ writeUnlock()

template<class R , class N , class K , ContainerThreadSafety s, int n>

void BalTreeInNode< R, N, K, s, n >::writeUnlock ( unsigned save ) const

inlineprotected

References ContainerNode< s >::writeUnlock().

Here is the call graph for this function:

Friends And Related Symbol Documentation

◆ BalTreeInRoot< R, N, K, s, n >

template<class R , class N , class K , ContainerThreadSafety s, int n>

friend class BalTreeInRoot< R, N, K, s, n >

friend

Member Data Documentation

◆ m_left

template<class R , class N , class K , ContainerThreadSafety s, int n>

N* TreeInNode< R, N, K, s, n >::m_left

privateinherited

Pointer to left (lesser) child node on tree.

Referenced by TreeInNode< R, N, K, s, n >::left().

◆ m_parent

template<class R , class N , class K , ContainerThreadSafety s, int n>

N* TreeInNode< R, N, K, s, n >::m_parent

privateinherited

Pointer to parent node on tree.

Referenced by TreeInNode< R, N, K, s, n >::parent().

◆ m_right

template<class R , class N , class K , ContainerThreadSafety s, int n>

N* TreeInNode< R, N, K, s, n >::m_right

privateinherited

Pointer to right (greater) child node on tree.

Referenced by TreeInNode< R, N, K, s, n >::right().

◆ m_root

template<class R , class N , class K , ContainerThreadSafety s, int n>

R* TreeInNode< R, N, K, s, n >::m_root

privateinherited

Pointer to tree we are on.

Referenced by TreeInNode< R, N, K, s, n >::root(), and TreeInNode< R, N, K, s, n >::setRoot().

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

Protected Member Functions

Private Types

Private Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ Base

◆ C

◆ Node

◆ Root

Constructor & Destructor Documentation

◆ BalTreeInNode()

◆ ~BalTreeInNode()

Member Function Documentation

◆ addTo() [1/2]

◆ addTo() [2/2]

◆ check()

◆ left()

◆ next()

◆ parent()

◆ prev()

◆ readLock()

◆ readUnlock()

◆ rebalance()

◆ remove()

◆ resort()

◆ right()

◆ root()

◆ rotateLeft()

◆ rotateRight()

◆ setRoot() [1/2]

◆ setRoot() [2/2]

◆ writeLock()

◆ writeUnlock()

Friends And Related Symbol Documentation

◆ BalTreeInRoot< R, N, K, s, n >

Member Data Documentation

◆ m_left

◆ m_parent

◆ m_right

◆ m_root