Loading...
Searching...
No Matches
cxx::Avl_tree< Node, Get_key, Compare > Class Template Reference

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

typedef Bst::Iterator | Iterator
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.
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

| 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.
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 100 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 130 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 220 of file avl_tree.

References cxx::Bits::Bst< Node, Get_key, Compare >::dir(), cxx::Bits::Bst< Node, Get_key, Compare >::greater(), and cxx::Bits::Direction::N.

Here is the call 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 282 of file avl_tree.

References cxx::Bits::Bst< Node, Get_key, Compare >::dir(), cxx::Bits::Bst< Node, Get_key, Compare >::greater(), cxx::Bits::Direction::L, and cxx::Bits::Direction::N.

Referenced by cxx::Avl_tree< Entry, Names_get_key >::erase().

Here is the call graph for this function:
Here is the caller graph for this function:

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

- l4/cxx/avl_tree