L4Re Operating System Framework
Interface and Usage Documentation
Loading...
Searching...
No Matches
cxx::Bits::Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY > Class Template Reference

Internal: AVL set with internally managed nodes. More...

#include <avl_set>

+ Inheritance diagram for cxx::Bits::Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY >:
+ Collaboration diagram for cxx::Bits::Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY >:

Data Structures

class  Node
 A smart pointer to a tree item. More...
 

Public Types

enum  { E_noent = 2 , E_exist = 17 , E_nomem = 12 , E_inval = 22 }
 Return status constants. More...
 
typedef ITEM_TYPE Item_type
 Type for the items store in the set.
 
typedef GET_KEY Get_key
 Key-getter type to derive the sort key of an internal node.
 
typedef GET_KEY::Key_type Key_type
 Type of the sort key used for the items.
 
typedef Type_traits< Item_type >::Const_type Const_item_type
 Type used for const items within the set.
 
typedef COMPARE Item_compare
 Type for the comparison functor.
 
typedef ALLOC< _Node > Node_allocator
 Type for the node allocator.
 
typedef Avl_set_iter< _Node, Item_type, Fwd > Iterator
 Forward iterator for the set.
 
typedef Avl_set_iter< _Node, Const_item_type, Fwd > Const_iterator
 Constant forward iterator for the set.
 
typedef Avl_set_iter< _Node, Item_type, Rev > Rev_iterator
 Backward iterator for the set.
 
typedef Avl_set_iter< _Node, Const_item_type, Rev > Const_rev_iterator
 Constant backward iterator for the set.
 

Public Member Functions

 Base_avl_set (Node_allocator const &alloc=Node_allocator())
 Create a AVL-tree based set.
 
 Base_avl_set (Base_avl_set const &o)
 Create a copy of an AVL-tree based set.
 
cxx::Pair< Iterator, int > insert (Item_type const &item)
 Insert an item into the set.
 
int remove (Key_type const &item)
 Remove an item from the set.
 
int erase (Key_type const &item)
 Erase the item with the given key.
 
Node find_node (Key_type const &item) const
 Lookup a node equal to item.
 
Node lower_bound_node (Key_type const &key) const
 Find the first node greater or equal to key.
 
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.
 

Detailed Description

template<typename ITEM_TYPE, class COMPARE, template< typename A > class ALLOC, typename GET_KEY>
class cxx::Bits::Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY >

Internal: AVL set with internally managed nodes.

Use Avl_set, Avl_map, or Avl_tree in applications.

Template Parameters
ITEM_TYPEThe type of the items to be stored in the set.
COMPAREThe relation to define the partial order, default is to use operator '<'.
ALLOCThe allocator to use for the nodes of the AVL set.
GET_KEYSort-key getter (must provide the Key_type and sort-key for an item (of ITEM_TYPE).

Definition at line 133 of file avl_set.

Member Enumeration Documentation

◆ anonymous enum

template<typename ITEM_TYPE , class COMPARE , template< typename A > class ALLOC, typename GET_KEY >
anonymous enum

Return status constants.

These constants are compatible with the L4 error codes, see l4_error_code_t.

Enumerator
E_noent 

Item does not exist.

E_exist 

Item exists already.

E_nomem 

Memory allocation failed.

E_inval 

Internal error.

Definition at line 144 of file avl_set.

Constructor & Destructor Documentation

◆ Base_avl_set() [1/2]

template<typename ITEM_TYPE , class COMPARE , template< typename A > class ALLOC, typename GET_KEY >
cxx::Bits::Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY >::Base_avl_set ( Node_allocator const &  alloc = Node_allocator())
inlineexplicit

Create a AVL-tree based set.

Parameters
allocNode allocator.

Create an empty set (AVL-tree based).

Definition at line 254 of file avl_set.

◆ Base_avl_set() [2/2]

template<typename Item , class Compare , template< typename A > class Alloc, typename KEY_TYPE >
cxx::Bits::Base_avl_set< Item, Compare, Alloc, KEY_TYPE >::Base_avl_set ( Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY > const &  o)
inline

Create a copy of an AVL-tree based set.

Parameters
oThe set to copy.

Creates a deep copy of the set with all its items.

Definition at line 413 of file avl_set.

References cxx::Bits::Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY >::begin(), cxx::Bits::Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY >::end(), and cxx::Bits::Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY >::insert().

+ Here is the call graph for this function:

Member Function Documentation

◆ begin() [1/2]

template<typename ITEM_TYPE , class COMPARE , template< typename A > class ALLOC, typename GET_KEY >
Iterator cxx::Bits::Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY >::begin ( )
inline

Get the mutable forward iterator for the first element of the set.

Returns
The mutable forward iterator for the first element of the set.

Definition at line 367 of file avl_set.

References cxx::Bits::Bst< Node, Get_key, Compare >::begin().

+ Here is the call graph for this function:

◆ begin() [2/2]

template<typename ITEM_TYPE , class COMPARE , template< typename A > class ALLOC, typename GET_KEY >
Const_iterator cxx::Bits::Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY >::begin ( ) const
inline

Get the constant forward iterator for the first element in the set.

Returns
Constant forward iterator for the first element in the set.

Definition at line 356 of file avl_set.

References cxx::Bits::Bst< Node, Get_key, Compare >::begin().

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

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

◆ end() [1/2]

template<typename ITEM_TYPE , class COMPARE , template< typename A > class ALLOC, typename GET_KEY >
Iterator cxx::Bits::Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY >::end ( )
inline

Get the end marker for the mutable forward iterator.

Returns
The end marker for mutable forward iterator.

Definition at line 372 of file avl_set.

References cxx::Bits::Bst< Node, Get_key, Compare >::end().

+ Here is the call graph for this function:

◆ end() [2/2]

template<typename ITEM_TYPE , class COMPARE , template< typename A > class ALLOC, typename GET_KEY >
Const_iterator cxx::Bits::Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY >::end ( ) const
inline

Get the end marker for the constant forward iterator.

Returns
The end marker for the constant forward iterator.

Definition at line 361 of file avl_set.

References cxx::Bits::Bst< Node, Get_key, Compare >::end().

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

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

◆ erase()

template<typename ITEM_TYPE , class COMPARE , template< typename A > class ALLOC, typename GET_KEY >
int cxx::Bits::Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY >::erase ( Key_type const &  item)
inline

Erase the item with the given key.

Parameters
itemThe key of the item to remove.

Definition at line 324 of file avl_set.

References cxx::Bits::Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY >::remove().

+ Here is the call graph for this function:

◆ find_node()

template<typename ITEM_TYPE , class COMPARE , template< typename A > class ALLOC, typename GET_KEY >
Node cxx::Bits::Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY >::find_node ( Key_type const &  item) const
inline

Lookup a node equal to item.

Parameters
itemThe value to search for.
Returns
A smart pointer to the element found. If no element was found the smart pointer will be invalid.

Definition at line 335 of file avl_set.

References cxx::Bits::Bst< Node, Get_key, Compare >::find_node().

Referenced by cxx::Avl_map< KEY_TYPE, DATA_TYPE, COMPARE, ALLOC >::operator[](), and cxx::Avl_map< KEY_TYPE, DATA_TYPE, COMPARE, ALLOC >::operator[]().

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

◆ insert()

template<typename ITEM_TYPE , class COMPARE , template< typename A > class ALLOC, typename GET_KEY >
Pair< typename Base_avl_set< Item, Compare, Alloc, KEY_TYPE >::Iterator, int > cxx::Bits::Base_avl_set< Item, Compare, Alloc, KEY_TYPE >::insert ( Item_type const &  item)

Insert an item into the set.

Parameters
itemThe item to insert.
Returns
A pair of iterator (first) and return value (second). second will be 0 if the element was inserted into the set and -#E_exist if the element was already in the set and the set was therefore not updated. In both cases, first contains an iterator that points to the element. second may also be -#E_nomem when memory for the node could not be allocated. first is then invalid.

Insert a new item into the set, each item can only be once in the set.

Definition at line 423 of file avl_set.

References cxx::Pair< First, Second >::first, cxx::Avl_tree< Node, Get_key, Compare >::insert(), and cxx::Pair< First, Second >::second.

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

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

◆ lower_bound_node()

template<typename ITEM_TYPE , class COMPARE , template< typename A > class ALLOC, typename GET_KEY >
Node cxx::Bits::Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY >::lower_bound_node ( Key_type const &  key) const
inline

Find the first node greater or equal to key.

Parameters
keyMinimum key to look for.
Returns
Smart pointer to the first node greater or equal to key. Will be invalid if no such element was found.

Definition at line 346 of file avl_set.

References cxx::Bits::Bst< Node, Get_key, Compare >::lower_bound_node().

+ Here is the call graph for this function:

◆ rbegin() [1/2]

template<typename ITEM_TYPE , class COMPARE , template< typename A > class ALLOC, typename GET_KEY >
Rev_iterator cxx::Bits::Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY >::rbegin ( )
inline

Get the mutable backward iterator for the last element of the set.

Returns
The mutable backward iterator for the last element of the set.

Definition at line 389 of file avl_set.

References cxx::Bits::Bst< Node, Get_key, Compare >::rbegin().

+ Here is the call graph for this function:

◆ rbegin() [2/2]

template<typename ITEM_TYPE , class COMPARE , template< typename A > class ALLOC, typename GET_KEY >
Const_rev_iterator cxx::Bits::Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY >::rbegin ( ) const
inline

Get the constant backward iterator for the last element in the set.

Returns
The constant backward iterator for the last element in the set.

Definition at line 378 of file avl_set.

References cxx::Bits::Bst< Node, Get_key, Compare >::rbegin().

+ Here is the call graph for this function:

◆ remove()

template<typename ITEM_TYPE , class COMPARE , template< typename A > class ALLOC, typename GET_KEY >
int cxx::Bits::Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY >::remove ( Key_type const &  item)
inline

Remove an item from the set.

Parameters
itemThe item to remove.
Return values
0Success
-E_noentItem does not exist

Definition at line 306 of file avl_set.

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

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

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

◆ rend() [1/2]

template<typename ITEM_TYPE , class COMPARE , template< typename A > class ALLOC, typename GET_KEY >
Rev_iterator cxx::Bits::Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY >::rend ( )
inline

Get the end marker for the mutable backward iterator.

Returns
The end marker for mutable backward iterator.

Definition at line 394 of file avl_set.

References cxx::Bits::Bst< Node, Get_key, Compare >::rend().

+ Here is the call graph for this function:

◆ rend() [2/2]

template<typename ITEM_TYPE , class COMPARE , template< typename A > class ALLOC, typename GET_KEY >
Const_rev_iterator cxx::Bits::Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY >::rend ( ) const
inline

Get the end marker for the constant backward iterator.

Returns
The end marker for the constant backward iterator.

Definition at line 383 of file avl_set.

References cxx::Bits::Bst< Node, Get_key, Compare >::rend().

+ Here is the call graph for this function:

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