Loading...
Searching...
No Matches
avl_map
Go to the documentation of this file.
// vi:set ft=cpp: -*- Mode: C++ -*-
/*
* (c) 2008-2009 Alexander Warg <warg@os.inf.tu-dresden.de>
* economic rights: Technische Universität Dresden (Germany)
*
* License: see LICENSE.spdx (in this directory or the directories above)
*/
#pragma once
#include <l4/cxx/std_alloc>
#include <l4/cxx/std_ops>
#include <l4/cxx/pair>
#include <l4/cxx/avl_set>
namespace cxx {
namespace Bits {
template<typename KEY_TYPE>
struct Avl_map_get_key
{
typedef KEY_TYPE Key_type;
template<typename NODE>
static Key_type const &key_of(NODE const *n)
{ return n->item.first; }
};
}
template< typename KEY_TYPE, typename DATA_TYPE,
template<typename A> class COMPARE = Lt_functor,
template<typename B> class ALLOC = New_allocator >
class Avl_map :
public Bits::Base_avl_set<Pair<KEY_TYPE, DATA_TYPE>,
COMPARE<KEY_TYPE>, ALLOC,
Bits::Avl_map_get_key<KEY_TYPE> >
{
private:
typedef Pair<KEY_TYPE, DATA_TYPE> Local_item_type;
typedef Bits::Base_avl_set<Local_item_type, COMPARE<KEY_TYPE>, ALLOC,
Bits::Avl_map_get_key<KEY_TYPE> > Base_type;
public:
typedef COMPARE<KEY_TYPE> Key_compare;
typedef KEY_TYPE Key_type;
typedef DATA_TYPE Data_type;
typedef typename Base_type::Node Node;
typedef typename Base_type::Node_allocator Node_allocator;
typedef typename Base_type::Iterator Iterator;
typedef typename Base_type::Iterator iterator;
typedef typename Base_type::Const_iterator Const_iterator;
typedef typename Base_type::Const_iterator const_iterator;
typedef typename Base_type::Rev_iterator Rev_iterator;
typedef typename Base_type::Rev_iterator reverse_iterator;
typedef typename Base_type::Const_rev_iterator Const_rev_iterator;
typedef typename Base_type::Const_rev_iterator const_reverse_iterator;
Avl_map(Node_allocator const &alloc = Node_allocator())
: Base_type(alloc)
{}
cxx::Pair<Iterator, int> insert(Key_type const &key, Data_type const &data)
{ return Base_type::insert(Pair<Key_type, Data_type>(key, data)); }
template<typename... Args>
cxx::Pair<Iterator, int> emplace(Args &&...args)
{ return Base_type::emplace(cxx::forward<Args>(args)...); }
Data_type const &operator [] (Key_type const &key) const
{ return this->find_node(key)->second; }
Data_type &operator [] (Key_type const &key)
{
Node n = this->find_node(key);
if (n)
return const_cast< Data_type&>(n->second);
else
return insert(key, Data_type()).first->second;
}
};
}
avl_set
AVL set.
cxx::Avl_map< Region, Hdlr, cxx::Lt_functor, Alloc >::Key_type
Region Key_type
Definition avl_map:59
cxx::Avl_map::Avl_map
Avl_map(Node_allocator const &alloc=Node_allocator())
Create an empty AVL-tree based map.
Definition avl_map:80
cxx::Avl_map< Region, Hdlr, cxx::Lt_functor, Alloc >::Key_compare
cxx::Lt_functor< Region > Key_compare
Definition avl_map:57
cxx::Avl_map< Region, Hdlr, cxx::Lt_functor, Alloc >::Node
Base_type::Node Node
Definition avl_map:63
cxx::Avl_map< Region, Hdlr, cxx::Lt_functor, Alloc >::Node_allocator
Base_type::Node_allocator Node_allocator
Definition avl_map:65
cxx::Avl_map::insert
cxx::Pair< Iterator, int > insert(Key_type const &key, Data_type const &data)
Insert a <key, data> pair into the map.
Definition avl_map:99
cxx::Avl_map< Region, Hdlr, cxx::Lt_functor, Alloc >::Data_type
Hdlr Data_type
Definition avl_map:61
cxx::Avl_map::operator[]
Data_type const & operator[](Key_type const &key) const
Get the data for the given key.
Definition avl_map:111
cxx::Bits::Base_avl_set::Node
A smart pointer to a tree item.
Definition avl_set:173
cxx::Bits::Base_avl_set
Internal: AVL set with internally managed nodes.
Definition avl_set:123
cxx::Bits::Base_avl_set::Iterator
Avl_set_iter< _Node, Item_type, Fwd > Iterator
Forward iterator for the set.
Definition avl_set:225
cxx::Bits::Base_avl_set< Pair< KEY_TYPE, DATA_TYPE >, Lt_functor< KEY_TYPE >, New_allocator, Bits::Avl_map_get_key< KEY_TYPE > >::find_node
Node find_node(Key_type const &item) const
Definition avl_set:324
cxx::Bits::Base_avl_set::Rev_iterator
Avl_set_iter< _Node, Item_type, Rev > Rev_iterator
Backward iterator for the set.
Definition avl_set:231
cxx::Bits::Base_avl_set::Node_allocator
ALLOC< _Node > Node_allocator
Type for the node allocator.
Definition avl_set:208
cxx::Bits::Base_avl_set::Const_rev_iterator
Avl_set_iter< _Node, Const_item_type, Rev > Const_rev_iterator
Constant backward iterator for the set.
Definition avl_set:234
cxx::Bits::Base_avl_set< Local_item_type, COMPARE< KEY_TYPE >, ALLOC, Bits::Avl_map_get_key< KEY_TYPE > >::insert
cxx::Pair< Iterator, int > insert(Item_type const &item)
cxx::Bits::Base_avl_set::Const_iterator
Avl_set_iter< _Node, Const_item_type, Fwd > Const_iterator
Constant forward iterator for the set.
Definition avl_set:228
cxx::New_allocator
Standard allocator based on operator new () .
Definition std_alloc:57
cxx::Bits
Internal helpers for the cxx package.
Definition avl_map:21
cxx
Our C++ library.
Definition arith:11
pair
Pair implementation.
cxx::Bits::Avl_map_get_key
Key-getter for Avl_map.
Definition avl_map:26
cxx::Lt_functor
Generic comparator class that defaults to the less-than operator.
Definition std_ops:19
cxx::Pair
Pair of two values.
Definition pair:28
cxx::Pair::second
Second second
Second value.
Definition pair:37