L4Re - L4 Runtime Environment
cxx::Avl_tree< Node, Get_key, Compare > Class Template Reference

A generic AVL tree. More...

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

Public Types

typedef Bst::Iterator Iterator
 Forward iterator for the tree.
 
typedef Bst::Const_iterator Const_iterator
 Constant forward iterator for the tree.
 
typedef Bst::Rev_iterator Rev_iterator
 Backward iterator for the tree.
 
typedef Bst::Const_rev_iterator Const_rev_iterator
 Constant backward iterator for the tree.
 
- 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. More...
 
Node * remove (Key_param_type key)
 Remove the node with key from the tree. More...
 
Node * erase (Key_param_type key)
 An alias for remove().
 
 Avl_tree ()
 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. More...
 
Const_iterator end () const
 Get the end marker for the constant forward iterator. More...
 
Iterator begin ()
 Get the mutable forward iterator for the first element of the set. More...
 
Iterator end ()
 Get the end marker for the mutable forward iterator. More...
 
Const_rev_iterator rbegin () const
 Get the constant backward iterator for the last element in the set. More...
 
Const_rev_iterator rend () const
 Get the end marker for the constant backward iterator. More...
 
Rev_iterator rbegin ()
 Get the mutable backward iterator for the last element of the set. More...
 
Rev_iterator rend ()
 Get the end marker for the mutable backward iterator. More...
 
Node * find_node (Key_param_type key) const
 find the node with the given key. More...
 
Node * lower_bound_node (Key_param_type key) const
 find the first node with a key not less than the given key. More...
 
Const_iterator find (Key_param_type key) const
 find the node with the given key. More...
 
template<typename FUNC >
void remove_all (FUNC &&callback)
 Clear the tree. More...
 

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. More...
 
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. More...
 
static Dir dir (Key_param_type l, Bst_node const *r)
 Get the direction to go from l to search for r. More...
 
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
NodeThe data type of the nodes (must inherit from Avl_tree_node).
Get_keyThe 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.
CompareBinary 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 109 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_nodeA 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 229 of file avl_tree.

◆ 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
keyThe 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 291 of file avl_tree.


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