etl::intrusive_avl_tree_base< ID_ > Class Template Reference

#include <intrusive_avl_tree.h>

Classes
struct	link_type

Public Types
enum	{ ID = ID_ }

Public Member Functions
ETL_NODISCARD bool	empty () const ETL_NOEXCEPT
ETL_NODISCARD size_t	size () const ETL_NOEXCEPT
void	clear () ETL_NOEXCEPT
void	swap (intrusive_avl_tree_base &other) ETL_NOEXCEPT

Protected Member Functions
	intrusive_avl_tree_base () ETL_NOEXCEPT
	Default constructor.
	~intrusive_avl_tree_base ()
ETL_NODISCARD link_type *	get_root () ETL_NOEXCEPT
ETL_NODISCARD const link_type *	get_root () const ETL_NOEXCEPT
ETL_NODISCARD link_type &	get_origin () ETL_NOEXCEPT
const link_type &	get_origin () const ETL_NOEXCEPT
template<typename TValue, typename TIterator, typename TBinaryCompare>
void	assign_impl (TIterator first, TIterator last, TBinaryCompare binary_comp)
template<typename TValue, typename TCompare, typename TFactory>
etl::pair< TValue *, bool >	find_or_insert_impl (TCompare comp, TFactory factory)

Static Protected Member Functions
template<typename TLink>
static ETL_NODISCARD TLink *	get_origin (TLink *link) ETL_NOEXCEPT
static ETL_NODISCARD bool	is_real_link (const link_type *link) ETL_NOEXCEPT
template<typename TLink>
static ETL_NODISCARD TLink *	begin_impl (TLink &origin) ETL_NOEXCEPT
template<typename TLink>
static ETL_NODISCARD TLink *	end_impl (TLink &origin) ETL_NOEXCEPT
template<typename TLink>
static ETL_NODISCARD TLink *	find_extremum_impl (TLink *curr, const bool is_max) ETL_NOEXCEPT
template<typename TLink>
static ETL_NODISCARD TLink *	next_in_order_impl (TLink *curr) ETL_NOEXCEPT
template<typename TLink>
static ETL_NODISCARD TLink *	prev_in_order_impl (TLink *curr) ETL_NOEXCEPT
template<typename TLink, typename Visitor>
static void	visit_in_order_impl (TLink *curr, const bool is_reverse, Visitor visitor)
template<typename TLink, typename Visitor>
static void	visit_post_order_impl (TLink *curr, const bool is_reverse, Visitor visitor)
template<typename TLink, typename Visitor>
static void	visit_pre_order_impl (TLink *curr, const bool is_reverse, Visitor visitor)
static ETL_NODISCARD int_fast8_t	get_balance_factor_impl (const link_type *const curr) ETL_NOEXCEPT
template<typename TLink>
static ETL_NODISCARD TLink *	get_parent_impl (TLink *const curr) ETL_NOEXCEPT
template<typename TLink>
static ETL_NODISCARD TLink *	get_child_impl (TLink *const curr, const bool is_right) ETL_NOEXCEPT
template<typename TValue, typename TLink, typename TCompare>
static TValue *	find_impl (TLink *const root, TCompare comp)
template<bool IsUpper, typename TValue, typename TLink, typename TCompare>
static TValue *	find_bound_impl (TLink *const root, TCompare comp)
static void	erase_impl (link_type *const z_link) ETL_NOEXCEPT

Friends
void	swap (intrusive_avl_tree_base &lhs, intrusive_avl_tree_base &rhs) ETL_NOEXCEPT

Detailed Description

template<size_t ID_>
class etl::intrusive_avl_tree_base< ID_ >

Base for intrusive AVL tree. Stores elements derived from 'intrusive_avl_tree_base<ID>::link_type'.

Template Parameters

ID_	The link ID that the value is derived from.

Constructor & Destructor Documentation

~intrusive_avl_tree_base()

template<size_t ID_>

etl::intrusive_avl_tree_base< ID_ >::~intrusive_avl_tree_base ( )

inlineprotected

Destructor of a tree. Complexity: O(N). All existing nodes will stay alive but will be completely unlinked from the tree (and from each other). If you want more control on what happens with still linked tree nodes, then enumerate and unlink (aka "erase") them first (potentially moving to somewhere else). If needed, the whole content of the tree could be O(1) effectively moved to another tree, leaving this tree as empty - use C++11 move constructor of the tree.

Member Function Documentation

clear()

template<size_t ID_>

void etl::intrusive_avl_tree_base< ID_ >::clear ( )

inline

Unlinks all current items, leaving this tree in the empty state. Complexity: O(N). Operation invalidates all existing iterators.

Note that the same "clear all" effect could be achieved by using the erase method for each item, but b/c of intermediate tree rebalancing complexity will be higher - O(N*log(N)).

empty()

template<size_t ID_>

ETL_NODISCARD bool etl::intrusive_avl_tree_base< ID_ >::empty ( ) const

inline

Checks if the tree is in the empty state. Complexity: O(1).

size()

template<size_t ID_>

ETL_NODISCARD size_t etl::intrusive_avl_tree_base< ID_ >::size ( ) const

inline

Returns the number of elements. Complexity: O(1).

swap()

template<size_t ID_>

void etl::intrusive_avl_tree_base< ID_ >::swap ( intrusive_avl_tree_base< ID_ > & other )

inline

Swap with another tree. Complexity: O(1). Does nothing in case of self-swap (when this == &other).

Friends And Related Symbol Documentation

swap

template<size_t ID_>

void swap ( intrusive_avl_tree_base< ID_ > & lhs, intrusive_avl_tree_base< ID_ > & rhs )

friend

Swaps the trees. Complexity: O(1). Does nothing in case of self-swap (when &lhs == &rhs).

---

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

• include/etl/intrusive_avl_tree.h