Intrusive Binary Tree, Root. More...

#include <TreeIn.h>

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

[legend]

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

[legend]

Protected Member Functions
	TreeInRoot ()
	Constructor.

virtual	~TreeInRoot ()
	Destructor.

virtual void	add (N &node)
	Add node to our tree, note trees are sorted by the compare member function which needs to be implemented by the user.

void	add (N *node)
	Add node to our tree.

N *	base () const

bool	check () const override

int	compare (N const &node1, N const &node2) const
	Compare Nodes Should return >0 if node2 > node1, and <0 if node2 < node1, 0 if equal.

int	compareKey (N const &node, K key) const
	Compare Key to node Should return >0 if key > node, <0 if key < node, 0 if key == node.

N *	find (K key) const
	find a node

N *	findMinus (K key) const
	find a node, or the node that would be just lower than this node

N *	findPlus (K key) const
	find a node, r the node that would be just above this node.

N *	first () const

N *	last () const

unsigned	readLock (bool upgrade) const

void	readUnlock (unsigned save) const

void	remove (N &node)
	Remove Node from List.

void	remove (N *node)
	Remove Node from List.

unsigned	writeLock (bool upgrade) const

void	writeUnlock (unsigned save) const

Private Types
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_base
	Pointer to root node on tree.

Friends
class	BalTreeInNode< R, N, K, s, n >
	Let Balancer get to us.

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

Detailed Description

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

Intrusive Binary Tree, Root.

Template Parameters

R	The class that will be the owner of the Tree. Must derive from TreeInRoot<R, N, K, n>
N	The class that will be the nodes of the Tree. 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_base != nullptr:
- m_base->m_root == this.
- m_base->m_parent == nullptr

See also: TreeInNode

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

◆ Node

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

class TreeInNode< R, N, K, s, n > TreeInRoot< 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 > TreeInRoot< R, N, K, s, n >::Root

private

Type of TreeInRoot.

Constructor & Destructor Documentation

◆ TreeInRoot()

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

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

protected

Constructor.

Starts us as an empty list.

◆ ~TreeInRoot()

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

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

protectedvirtual

Destructor.

Removes all nodes attached to us.

Doesn't actually call remove on every node to avoid possible unneeded rebalencing, just manually unlinks all nodes.

Member Function Documentation

◆ add() [1/2]

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

void TreeInRoot< R, N, K, s, n >::add ( N & node )

inlineprotectedvirtual

Add node to our tree, note trees are sorted by the compare member function which needs to be implemented by the user.

Parameters

node	The node to add to the list If node is currently on a different list it is removed before being added to the list.

If node is on the requested list, do nothing. If trying to change value and position, use resort

◆ add() [2/2]

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

void TreeInRoot< R, N, K, s, n_ >::add ( N * node )

inlineprotected

Add node to our tree.

Parameters

node	The node to add to the list If node is null, Nothing is done. If node is currently on a list (even us) it is removed before being added to the list

◆ base()

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

N * TreeInRoot< R, N, K, s, n >::base ( ) const

inlineprotected

References TreeInRoot< R, N, K, s, n >::m_base.

◆ check()

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

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

inlineoverrideprotectedvirtual

Implements Container< s >.

◆ compare()

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

int TreeInRoot< R, N, K, s, n >::compare	(	N const &	node1,
		N const &	node2 ) const

protected

Compare Nodes Should return >0 if node2 > node1, and <0 if node2 < node1, 0 if equal.

◆ compareKey()

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

int TreeInRoot< R, N, K, s, n >::compareKey	(	N const &	node,
		K	key ) const

protected

Compare Key to node Should return >0 if key > node, <0 if key < node, 0 if key == node.

◆ find()

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

N * TreeInRoot< R, N, K, s, n >::find ( K key ) const

protected

find a node

◆ findMinus()

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

N * TreeInRoot< R, N, K, s, n >::findMinus ( K key ) const

protected

find a node, or the node that would be just lower than this node

◆ findPlus()

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

N * TreeInRoot< R, N, K, s, n >::findPlus ( K key ) const

protected

find a node, r the node that would be just above this node.

◆ first()

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

N * TreeInRoot< R, N, K, s, n >::first ( ) const

inlineprotected

◆ last()

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

N * TreeInRoot< R, N, K, s, n >::last ( ) const

inlineprotected

◆ readLock()

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

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

inlineprotected

References Container< s >::readLock().

Here is the call graph for this function:

◆ readUnlock()

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

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

inlineprotected

References Container< s >::readUnlock().

Here is the call graph for this function:

◆ remove() [1/2]

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

void TreeInRoot< R, N, K, s, n >::remove ( N & node )

inlineprotected

Remove Node from List.

Parameters

node	node to be removed. If node is not on this list, nothing will be done.

◆ remove() [2/2]

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

void TreeInRoot< R, N, K, s, n_ >::remove ( N * node )

inlineprotected

Remove Node from List.

Parameters

node	Pointer to node to be removed. If node is null, operation will be ignored. If node is not on this list, nothing will be done.

◆ writeLock()

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

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

inlineprotected

References Container< s >::writeLock().

Here is the call graph for this function:

◆ writeUnlock()

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

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

inlineprotected

References Container< 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.

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

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

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

friend

Member Data Documentation

◆ m_base

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

N* TreeInRoot< R, N, K, s, n >::m_base

private

Pointer to root node on tree.

Referenced by TreeInRoot< R, N, K, s, n >::base().

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

Protected Member Functions

Private Types

Private Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ Node

◆ Root

Constructor & Destructor Documentation

◆ TreeInRoot()

◆ ~TreeInRoot()

Member Function Documentation

◆ add() [1/2]

◆ add() [2/2]

◆ base()

◆ check()

◆ compare()

◆ compareKey()

◆ find()

◆ findMinus()

◆ findPlus()

◆ first()

◆ last()

◆ readLock()

◆ readUnlock()

◆ remove() [1/2]

◆ remove() [2/2]

◆ writeLock()

◆ writeUnlock()

Friends And Related Symbol Documentation

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

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

Member Data Documentation

◆ m_base