cxx::Bits::Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY > Class Template Reference

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, Node_allocator const &alloc=Node_allocator())
	Create a copy of an AVL-tree based set.
Base_avl_set &	operator= (Base_avl_set const &o)
	Copy assignment operator of an AVL-tree based set.
cxx::Pair< Iterator, int >	insert (Item_type const &item)
	Insert an item into the set.
template<typename... Args>
cxx::Pair< Iterator, int >	emplace (Args &&... args)
	Emplace an item into the set.
void	clear () noexcept
	Remove all items from 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 >

AVL set with internally managed nodes.

Definition at line 127 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 138 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

alloc

Node allocator.

Create an empty set (AVL-tree based).

Definition at line 268 of file avl_set.

Base_avl_set() [2/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 ( Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY > const & o, Node_allocator const & alloc = Node_allocator() )

inline

Create a copy of an AVL-tree based set.

Parameters

o	The set to copy.
alloc	Node allocator.

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

Definition at line 283 of file avl_set.

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 431 of file avl_set.

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 417 of file avl_set.

emplace()

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

template<typename... Args>

cxx::Pair< Iterator, int > cxx::Bits::Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY >::emplace

(

Args &&...

args

)

Emplace an item into the set.

Parameters

args	Constructor arguments for the item constructor.

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.

The element will always be constructed, even if there is already an existing element in the set. In case of such a collision the newly created element will then be immediately destructed.

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 438 of file avl_set.

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 424 of file avl_set.

Referenced by insert().

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

item	The key of the item to remove.

Definition at line 384 of file avl_set.

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

item	The 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 395 of file avl_set.

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

item	The 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 485 of file avl_set.

References E_exist, E_nomem, end(), cxx::Pair< First, Second >::first, and cxx::Pair< First, Second >::second.

Here is the call 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

key	Minimum 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 406 of file avl_set.

operator=()

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

Base_avl_set & cxx::Bits::Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY >::operator= ( Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY > const & o )

inline

Copy assignment operator of an AVL-tree based set.

Parameters

o	The set to copy-assign.

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

Definition at line 295 of file avl_set.

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 459 of file avl_set.

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 445 of file avl_set.

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

item	The item to remove.

Return values

0	Success
-E_noent	Item does not exist

Definition at line 366 of file avl_set.

Referenced by cxx::Bits::Base_avl_set< Local_item_type, COMPARE< KEY_TYPE >, ALLOC, Bits::Avl_map_get_key< KEY_TYPE > >::erase().

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 466 of file avl_set.

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 452 of file avl_set.

---

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

• l4/cxx/avl_set