A generic AVL tree. More...

#include <avl_tree>

Inheritance diagram for cxx::Avl_tree< Node, Get_key, Compare >:

Collaboration diagram for cxx::Avl_tree< Node, Get_key, Compare >:

Public Types inherited from cxx::Bits::Bst< Node, Get_key, Compare >

typedef Get_key::Key_type	Key_type
	The type of key values used to generate the total order of the elements.

typedef Type_traits< Key_type >::Param_type	Key_param_type
	The type for key parameters.

typedef Fwd	Fwd_iter_ops
	Helper for building forward iterators for different wrapper classes.

typedef Rev	Rev_iter_ops
	Helper for building reverse iterators for different wrapper classes.

typedef __Bst_iter< Node, Node, Fwd >	Iterator
	Forward iterator.

typedef __Bst_iter< Node, Node const, Fwd >	Const_iterator
	Constant forward iterator.

typedef __Bst_iter< Node, Node, Rev >	Rev_iterator
	Backward iterator.

typedef __Bst_iter< Node, Node const, Rev >	Const_rev_iterator
	Constant backward.

Public Member Functions
Pair< Node *, bool >	insert (Node *new_node)
	Insert a new node into this AVL tree.

Node *	remove (Key_param_type key)
	Remove the node with key from the tree.

Node *	erase (Key_param_type key)
	An alias for remove().

	Avl_tree ()=default
	Create an empty AVL tree.

	~Avl_tree () noexcept
	Destroy the tree.

Public Member Functions inherited from cxx::Bits::Bst< Node, Get_key, Compare >
Const_iterator	begin () const
	Get the constant forward iterator for the first element in the set.

Const_iterator	end () const
	Get the end marker for the constant forward iterator.

Iterator	begin ()
	Get the mutable forward iterator for the first element of the set.

Iterator	end ()
	Get the end marker for the mutable forward iterator.

Const_rev_iterator	rbegin () const
	Get the constant backward iterator for the last element in the set.

Const_rev_iterator	rend () const
	Get the end marker for the constant backward iterator.

Rev_iterator	rbegin ()
	Get the mutable backward iterator for the last element of the set.

Rev_iterator	rend ()
	Get the end marker for the mutable backward iterator.

Node *	find_node (Key_param_type key) const
	find the node with the given key.

Node *	lower_bound_node (Key_param_type key) const
	Find the first node with a key not less than the given `key`.

Const_iterator	find (Key_param_type key) const
	find the node with the given key.

template<typename FUNC >
void	remove_all (FUNC &&callback)
	Clear the tree.

Additional Inherited Members
Protected Member Functions inherited from cxx::Bits::Bst< Node, Get_key, Compare >
	Bst ()
	Create an empty tree.

Node *	head () const
	Access the head node as object of type Node.

Static Protected Member Functions inherited from cxx::Bits::Bst< Node, Get_key, Compare >
template<typename FUNC >
static void	remove_tree (Bst_node *head, FUNC &&callback)
	Remove all elements in the subtree of head.

static Key_type	k (Bst_node const *n)
	Get the key value of n.

static Dir	dir (Key_param_type l, Key_param_type r)
	Get the direction to go from `l` to search for `r`.

static Dir	dir (Key_param_type l, Bst_node const *r)
	Get the direction to go from `l` to search for `r`.

static bool	greater (Key_param_type l, Key_param_type r)
	Is l greater than r.

static bool	greater (Key_param_type l, Bst_node const *r)
	Is l greater than r.

static bool	greater (Bst_node const l, Bst_node const r)
	Is l greater than r.

Protected Attributes inherited from cxx::Bits::Bst< Node, Get_key, Compare >
Bst_node *	_head
	The head pointer of the tree.

Detailed Description

template<typename Node, typename Get_key, typename Compare = Lt_functor<typename Get_key::Key_type>>
class cxx::Avl_tree< Node, Get_key, Compare >

A generic AVL tree.

Template Parameters

Node	The data type of the nodes (must inherit from Avl_tree_node).
Get_key	The meta function to get the key value from a node. The implementation uses `Get_key::key_of(ptr_to_node)`. The type of the key values must be defined in `Get_key::Key_type`.
Compare	Binary relation to establish a total order for the nodes of the tree. `Compare()(l, r)` must return true if the key l is smaller than the key r.

This implementation does not provide any memory management. It is the responsibility of the caller to allocate nodes before inserting them and to free them when they are removed or when the tree is destroyed. Conversely, the caller must also ensure that nodes are removed from the tree before they are destroyed.

Examples: tmpfs/lib/src/fs.cc.

Definition at line 111 of file avl_tree.

Member Typedef Documentation

◆ Iterator

template<typename Node , typename Get_key , typename Compare = Lt_functor<typename Get_key::Key_type>>

typedef Bst::Iterator cxx::Avl_tree< Node, Get_key, Compare >::Iterator

Forward iterator for the tree.

Definition at line 141 of file avl_tree.

Member Function Documentation

◆ insert()

template<typename Node , typename Get_key , class Compare >

Pair< Node *, bool > cxx::Avl_tree< Node, Get_key, Compare >::insert ( Node * new_node )

Insert a new node into this AVL tree.

Parameters

new_node A pointer to the new node.

Returns: A pair, with second set to true and first pointing to new_node, on success. If there is already a node with the same key then first points to this node and second is 'false'.

Definition at line 231 of file avl_tree.

Referenced by cxx::Bits::Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY >::insert().

Here is the caller graph for this function:

◆ remove()

template<typename Node , typename Get_key , class Compare >

Node * cxx::Avl_tree< Node, Get_key, Compare >::remove ( Key_param_type key )

inline

Remove the node with key from the tree.

Parameters

key	The key to the node to remove.

Returns: The pointer to the removed node on success, or 0 if no node with the key exists.

Definition at line 293 of file avl_tree.

Referenced by cxx::Avl_tree< Node, Get_key, Compare >::erase(), and cxx::Bits::Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY >::remove().