Intrusive Binary Tree, Node. More...

#include <AATreeIn.h>

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

[legend]

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

[legend]

Protected Member Functions
	AATreeInNode ()
	Constructor.

virtual	~AATreeInNode ()
	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
	AATree Balancing.

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 ()

N *	rotateRight ()

void	setRoot (C *root)
	Set our Container.

void	setRoot (R *root)

unsigned	writeLock (bool upgrade) const

void	writeUnlock (unsigned save) const

Protected Attributes
int	level = 0
	Node Level.

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

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

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

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

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	AATreeInRoot< R, N, K, s, n >

Detailed Description

template<class R, class N, class K, ContainerThreadSafety s, int n>
class AATreeInNode< 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

New:

if m_right == nullptr:
- level == 1
- m_left == nullptr
if m_left != nullptr:
- m_left->m_level + 1 == level
- m_right != nullptr = if m_right != nullptr:
- m_right->m_level == m_level || m_right->m_level + 1 == m_level
- if m_right->m_right != nullptr:
  - m_right->m_right->m_level < m_level // only 1 stay at level in a row in a row)
if level > 1:
- m_left != nullptr
- m_right != nullptr

Simplified if null items have level == 0

m_level == m_left->m_level + 1
m_level == m_right->m_level + 1 || m_right->m_right->m_level + 1

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: AATreeInRoot

Member Typedef Documentation

◆ Base

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

class BalTreeInNode< R, N, K, s, n > AATreeInNode< 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 AATreeInNode< R, N, K, s, n > AATreeInNode< R, N, K, s, n >::Node

private

Type of DListIInNode.

◆ Root

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

class AATreeInRoot< R, N, K, s, n > AATreeInNode< R, N, K, s, n >::Root

private

Type of TreeInRoot.

Constructor & Destructor Documentation

◆ AATreeInNode()

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

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

protected

Constructor.

◆ ~AATreeInNode()

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

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

protectedvirtual

Destructor.

Remove us from we are on, if any.

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 AATreeInNode< R, N, K, s, n >::check ( ) const

overrideprotectedvirtual

Implements ContainerNode< s >.

◆ left()

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

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

inlineprotected

◆ next()

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

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

inlineprotected

◆ parent()

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

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

inlineprotected

◆ prev()

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

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

inlineprotected

◆ readLock()

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

unsigned AATreeInNode< 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 AATreeInNode< 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 AATreeInNode< R, N, K, s, n >::rebalance ( )

overrideprotectedvirtual

AATree Balancing.

Basic Rules

Invariant

AATrees have the following invariants:

leaf nodes have level = 1
left child have level = parent - 1
right child have level = parent - 1, or parent
right child of right child has level < grandparent (only 1 == in a row)
if level > 1, has both left and right.

Implementation of Rules (reversing to look Up not down)

Let L be the level of our Left child node Let R be the level of our Right child node Let G be the level of our Right-Right grandchild node.

Non-existent nodes have a level of 0

Our level needs to be L+1
This value needs to be R+1, or G+1 (so R == L or G == L)
If this isn't possible, need to rotate to make this possible.
If L > R then our children our out of balance and we need to move nodes from the left to the right, so rotate to the right
if L == R or L == G, then our level = L+1, and can move up the tree
Else (L too much smaller than R) our children are out of balance so rotate to the left.

Rule Check:

Satisfied, Leaf Nodes have no Left, or Left+1 = 1
Satisfied, Our basic rule, our level = Left+1
Satisfied, If L == R, then we are Right+1, if L == G then we are Right or Right+1
Satisfied, Since G can't be > L, we can't be == G.
Satisfied, If left empty, we are level 1, if right empty, then left must be empty or we can't get L == R or L == G

Implements BalTreeInNode< 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 * AATreeInNode< R, N, K, s, n >::right ( ) const

inlineprotected

◆ root()

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

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

inlineprotected

◆ rotateLeft()

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

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

inlineprotected

◆ rotateRight()

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

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

inlineprotected

◆ 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 AATreeInNode< 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 AATreeInNode< 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

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

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

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

friend

Member Data Documentation

◆ level

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

int AATreeInNode< R, N, K, s, n >::level = 0

protected

Node Level.

◆ 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

Protected Attributes

Private Types

Private Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ Base

◆ C

◆ Node

◆ Root

Constructor & Destructor Documentation

◆ AATreeInNode()

◆ ~AATreeInNode()

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

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

Member Data Documentation

◆ level

◆ m_left

◆ m_parent

◆ m_right

◆ m_root