L4Re Operating System Framework
Interface and Usage Documentation
|
AVL tree based associative container. More...
#include <avl_map>
Public Types | |
typedef COMPARE< KEY_TYPE > | Key_compare |
Type of the comparison functor. | |
typedef KEY_TYPE | Key_type |
Type of the key values. | |
typedef DATA_TYPE | Data_type |
Type of the data values. | |
typedef Base_type::Node | Node |
Return type for find. | |
typedef Base_type::Node_allocator | Node_allocator |
Type of the allocator. | |
Public Types inherited from cxx::Bits::Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY > | |
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 | |
Avl_map (Node_allocator const &alloc=Node_allocator()) | |
Create an empty AVL-tree based map. | |
cxx::Pair< Iterator, int > | insert (Key_type const &key, Data_type const &data) |
Insert a <key, data> pair into the map. | |
Data_type const & | operator[] (Key_type const &key) const |
Get the data for the given key. | |
Data_type & | operator[] (Key_type const &key) |
Get or insert data for the given key. | |
Public Member Functions inherited from cxx::Bits::Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY > | |
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. | |
AVL tree based associative container.
KEY_TYPE | Type of the key values. |
DATA_TYPE | Type of the data values. |
COMPARE | Type comparison functor for the key values. |
ALLOC | Type of the allocator used for the nodes. |
|
inline |
|
inline |
Insert a <key, data> pair into the map.
key | The key value. |
data | The data value to insert. |
first
) and return value (second
). second
will be 0 if the element was inserted into the set and -#E_exist
if the key 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 new node could not be allocated. first
is then invalid. Definition at line 110 of file avl_map.
References cxx::Bits::Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY >::insert().
Referenced by cxx::Avl_map< KEY_TYPE, DATA_TYPE, COMPARE, ALLOC >::operator[]().
|
inline |
Get or insert data for the given key.
key | The key value to use for lookup. |
Definition at line 134 of file avl_map.
References cxx::Bits::Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY >::find_node(), and cxx::Avl_map< KEY_TYPE, DATA_TYPE, COMPARE, ALLOC >::insert().
|
inline |
Get the data for the given key.
key | The key value to use for lookup. |
Definition at line 122 of file avl_map.
References cxx::Bits::Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY >::find_node().