#include <avl_tree.hpp>

Inheritance diagram for uavcan::AvlTree< T >:

Classes
struct	Node

Public Member Functions
	AvlTree (IPoolAllocator &allocator, std::size_t allocator_quota)

bool	contains (const T *data) const

size_t	getSize () const

bool	insert (T *data)

bool	isEmpty () const

T *	max () const

void	removeEntry (T *data)

void	walkPostOrder (std::function< void(T *&)> forEach)

virtual	~AvlTree ()

Protected Member Functions
void	postOrderNodeTraverseRecursively (Node n, std::function< void(Node &)> forEach)

Node *	removeNode (Node node, T data)

Static Protected Member Functions
static bool	linkedListContains (Node head, const T data)

Protected Attributes
LimitedPoolAllocator	allocator_

Node *	root_

Private Member Functions
Node *	deleteFromList (Node root, T data)

void	deleteNode (Node *&n)

Node *	insertNode (Node node, Node newNode)

Node *	makeNode (T *payload)

void	postOrderTraverseNodeCleanup (Node *n)

void	postOrderTraverseRecursively (Node n, std::function< void(T &)> forEach)

Private Member Functions inherited from uavcan::Noncopyable
	Noncopyable ()

	~Noncopyable ()

Static Private Member Functions
static void	appendToEndOf (Node head, Node newNode)

static int16_t	balanceOf (Node *n)

static int16_t	heightOf (const Node *n)

static int16_t	maxOf (int16_t a, int16_t b)

static Node *	rotateLeft (Node *x)

static Node *	rotateRight (Node *y)

Private Attributes
size_t	len_ = 0

Detailed Description

template<typename T>
class uavcan::AvlTree< T >

Definition at line 22 of file avl_tree.hpp.

Constructor & Destructor Documentation

◆ AvlTree()

template<typename T >

uavcan::AvlTree< T >::AvlTree	(	IPoolAllocator &	allocator,
		std::size_t	allocator_quota
	)

inline

Definition at line 313 of file avl_tree.hpp.

◆ ~AvlTree()

template<typename T >

virtual uavcan::AvlTree< T >::~AvlTree ( )

inlinevirtual

Definition at line 319 of file avl_tree.hpp.

Member Function Documentation

◆ appendToEndOf()

template<typename T >

static void uavcan::AvlTree< T >::appendToEndOf	(	Node *	head,
		Node *	newNode
	)

inlinestaticprivate

Definition at line 159 of file avl_tree.hpp.

◆ balanceOf()

template<typename T >

static int16_t uavcan::AvlTree< T >::balanceOf ( Node * n )

inlinestaticprivate

Definition at line 79 of file avl_tree.hpp.

◆ contains()

template<typename T >

bool uavcan::AvlTree< T >::contains ( const T * data ) const

inline

Definition at line 366 of file avl_tree.hpp.

◆ deleteFromList()

template<typename T >

Node* uavcan::AvlTree< T >::deleteFromList	(	Node *	root,
		T *	data
	)

inlineprivate

Definition at line 171 of file avl_tree.hpp.

◆ deleteNode()

template<typename T >

void uavcan::AvlTree< T >::deleteNode ( Node *& n )

inlineprivate

Definition at line 71 of file avl_tree.hpp.

◆ getSize()

template<typename T >

size_t uavcan::AvlTree< T >::getSize ( ) const

inline

Definition at line 339 of file avl_tree.hpp.

◆ heightOf()

template<typename T >

static int16_t uavcan::AvlTree< T >::heightOf ( const Node * n )

inlinestaticprivate

Definition at line 38 of file avl_tree.hpp.

◆ insert()

template<typename T >

bool uavcan::AvlTree< T >::insert ( T * data )

inline

Definition at line 328 of file avl_tree.hpp.

◆ insertNode()

template<typename T >

Node* uavcan::AvlTree< T >::insertNode	(	Node *	node,
		Node *	newNode
	)

inlineprivate

Definition at line 118 of file avl_tree.hpp.

◆ isEmpty()

template<typename T >

bool uavcan::AvlTree< T >::isEmpty ( ) const

inline

Definition at line 348 of file avl_tree.hpp.

◆ linkedListContains()

template<typename T >

static bool uavcan::AvlTree< T >::linkedListContains	(	Node *	head,
		const T *	data
	)

inlinestaticprotected

Definition at line 301 of file avl_tree.hpp.

◆ makeNode()

template<typename T >

Node* uavcan::AvlTree< T >::makeNode ( T * payload )

inlineprivate

Definition at line 56 of file avl_tree.hpp.

◆ max()

template<typename T >

T* uavcan::AvlTree< T >::max ( ) const

inline

Definition at line 352 of file avl_tree.hpp.

◆ maxOf()

template<typename T >

static int16_t uavcan::AvlTree< T >::maxOf	(	int16_t	a,
		int16_t	b
	)

inlinestaticprivate

Definition at line 87 of file avl_tree.hpp.

◆ postOrderNodeTraverseRecursively()

template<typename T >

void uavcan::AvlTree< T >::postOrderNodeTraverseRecursively	(	Node *	n,
		std::function< void(Node *&)>	forEach
	)

inlineprotected

Definition at line 223 of file avl_tree.hpp.

◆ postOrderTraverseNodeCleanup()

template<typename T >

void uavcan::AvlTree< T >::postOrderTraverseNodeCleanup ( Node * n )

inlineprivate

Definition at line 205 of file avl_tree.hpp.

◆ postOrderTraverseRecursively()

template<typename T >

void uavcan::AvlTree< T >::postOrderTraverseRecursively	(	Node *	n,
		std::function< void(T *&)>	forEach
	)

inlineprivate

Definition at line 46 of file avl_tree.hpp.

◆ removeEntry()

template<typename T >

void uavcan::AvlTree< T >::removeEntry ( T * data )

inline

Definition at line 324 of file avl_tree.hpp.

◆ removeNode()

template<typename T >

Node* uavcan::AvlTree< T >::removeNode	(	Node *	node,
		T *	data
	)

inlineprotected

Definition at line 233 of file avl_tree.hpp.

◆ rotateLeft()

template<typename T >

static Node* uavcan::AvlTree< T >::rotateLeft ( Node * x )

inlinestaticprivate

Definition at line 104 of file avl_tree.hpp.

◆ rotateRight()

template<typename T >

static Node* uavcan::AvlTree< T >::rotateRight ( Node * y )

inlinestaticprivate

Definition at line 91 of file avl_tree.hpp.

◆ walkPostOrder()

template<typename T >

void uavcan::AvlTree< T >::walkPostOrder ( std::function< void(T *&)> forEach )

inline

Definition at line 343 of file avl_tree.hpp.

Member Data Documentation

◆ allocator_

template<typename T >

LimitedPoolAllocator uavcan::AvlTree< T >::allocator_

protected

Definition at line 221 of file avl_tree.hpp.

◆ len_

template<typename T >

size_t uavcan::AvlTree< T >::len_ = 0

private

Definition at line 36 of file avl_tree.hpp.

◆ root_

template<typename T >

Node* uavcan::AvlTree< T >::root_

protected

Definition at line 33 of file avl_tree.hpp.

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

avl_tree.hpp

Classes

Public Member Functions

Protected Member Functions

Static Protected Member Functions

Protected Attributes

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

template<typename T> class uavcan::AvlTree< T >

Constructor & Destructor Documentation

◆ AvlTree()

◆ ~AvlTree()

Member Function Documentation

◆ appendToEndOf()

◆ balanceOf()

◆ contains()

◆ deleteFromList()

◆ deleteNode()

◆ getSize()

◆ heightOf()

◆ insert()

◆ insertNode()

◆ isEmpty()

◆ linkedListContains()

◆ makeNode()

◆ max()

◆ maxOf()

◆ postOrderNodeTraverseRecursively()

◆ postOrderTraverseNodeCleanup()

◆ postOrderTraverseRecursively()

◆ removeEntry()

◆ removeNode()

◆ rotateLeft()

◆ rotateRight()

◆ walkPostOrder()

Member Data Documentation

◆ allocator_

◆ len_

◆ root_

template<typename T>
class uavcan::AvlTree< T >