Intrusive Binary Tree, Node. More...

#include <TreeIn.h>

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

[legend]

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

[legend]

Protected Member Functions
	TreeInNode ()
	Constructor.

virtual	~TreeInNode ()
	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
	Return node next in sort sequence.

N *	parent () const

N *	prev () const
	Return previous node in sort sequence.

unsigned	readLock (bool upgrade) const

void	readUnlock (unsigned save) const

virtual void	rebalance ()
	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
	Return pointer to tree we are on.

void	setRoot (C *root)
	Set our Container.

void	setRoot (R *root)

unsigned	writeLock (bool upgrade) const

void	writeUnlock (unsigned save) const

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

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

typedef class TreeInRoot< 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	BalTreeInNode< R, N, K, s, n >
	Let Balancer get to us.

class	TreeInRoot< R, N, K, s, n >

Detailed Description

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

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

Tree Structure

Summary:

Root:
- Base pointer to the Base node of the Tree
Node
- (Red) Nodes have a Root pointer to the Root structure for the tree
- (Blue) Parent pointer to the Node leading to the base of the Tree.
  - The node will be on the Left or Right of that Parent.
  - The Base node will have a null parent.
- Left pointer to the subtree of Nodes that are less than this node
- Right pointer to the subtree of Nodes that are greater than this node

Member Typedef Documentation

◆ 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 TreeInNode< R, N, K, s, n > TreeInNode< R, N, K, s, n >::Node

private

Type of DListIInNode.

◆ Root

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

class TreeInRoot< R, N, K, s, n > TreeInNode< R, N, K, s, n >::Root

private

Type of TreeInRoot.

Constructor & Destructor Documentation

◆ TreeInNode()

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

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

protected

Constructor.

◆ ~TreeInNode()

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

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

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 )

protected

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 )

protected

Add ourself to a tree.

Parameters

myroot Tree to add to.

◆ check()

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

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

inlineoverrideprotectedvirtual

Implements ContainerNode< s >.

◆ left()

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

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

inlineprotected

References TreeInNode< R, N, K, s, n >::m_left.

◆ next()

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

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

inlineprotected

Return node next in sort sequence.

◆ parent()

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

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

inlineprotected

References TreeInNode< R, N, K, s, n >::m_parent.

◆ prev()

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

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

inlineprotected

Return previous node in sort sequence.

◆ readLock()

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

unsigned TreeInNode< 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 TreeInNode< 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>

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

inlineprotectedvirtual

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

Reimplemented in AATreeInNode< R, N, K, s, n >, and 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 ( )

inlineprotectedvirtual

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

protected

◆ right()

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

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

inlineprotected

References TreeInNode< R, N, K, s, n >::m_right.

◆ root()

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

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

inlineprotected

Return pointer to tree we are on.

References TreeInNode< R, N, K, s, n >::m_root.

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

Here is the caller graph for this function:

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

inlineprotected

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 TreeInNode< 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 TreeInNode< 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

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

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

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

friend

Let Balancer get to us.

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

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

friend class TreeInRoot< 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

private

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

private

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

private

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

private

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

◆ C

◆ Node

◆ Root

Constructor & Destructor Documentation

◆ TreeInNode()

◆ ~TreeInNode()

Member Function Documentation

◆ addTo() [1/2]

◆ addTo() [2/2]

◆ check()

◆ left()

◆ next()

◆ parent()

◆ prev()

◆ readLock()

◆ readUnlock()

◆ rebalance()

◆ remove()

◆ resort()

◆ right()

◆ root()

◆ setRoot() [1/2]

◆ setRoot() [2/2]

◆ writeLock()

◆ writeUnlock()

Friends And Related Symbol Documentation

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

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

Member Data Documentation

◆ m_left

◆ m_parent

◆ m_right

◆ m_root