L4Re Operating System Framework
Interface and Usage Documentation
Loading...
Searching...
No Matches
avl_map
Go to the documentation of this file.
1// vi:set ft=cpp: -*- Mode: C++ -*-
6/*
7 * (c) 2008-2009 Alexander Warg <warg@os.inf.tu-dresden.de>
8 * economic rights: Technische Universität Dresden (Germany)
9 *
10 * This file is part of TUD:OS and distributed under the terms of the
11 * GNU General Public License 2.
12 * Please see the COPYING-GPL-2 file for details.
13 *
14 * As a special exception, you may use this file as part of a free software
15 * library without restriction. Specifically, if other files instantiate
16 * templates or use macros or inline functions from this file, or you compile
17 * this file and link it with other files to produce an executable, this
18 * file does not by itself cause the resulting executable to be covered by
19 * the GNU General Public License. This exception does not however
20 * invalidate any other reasons why the executable file might be covered by
21 * the GNU General Public License.
22 */
23
24#pragma once
25
26#include <l4/cxx/std_alloc>
27#include <l4/cxx/std_ops>
28#include <l4/cxx/pair>
29#include <l4/cxx/avl_set>
30
31namespace cxx {
32namespace Bits {
33
35template<typename KEY_TYPE>
37{
38 typedef KEY_TYPE Key_type;
39 template<typename NODE>
40 static Key_type const &key_of(NODE const *n)
41 { return n->item.first; }
42};
43}
44
53template< typename KEY_TYPE, typename DATA_TYPE,
54 template<typename A> class COMPARE = Lt_functor,
55 template<typename B> class ALLOC = New_allocator >
56class Avl_map :
57 public Bits::Base_avl_set<Pair<KEY_TYPE, DATA_TYPE>,
58 COMPARE<KEY_TYPE>, ALLOC,
59 Bits::Avl_map_get_key<KEY_TYPE> >
60{
61private:
62 typedef Pair<KEY_TYPE, DATA_TYPE> Local_item_type;
65
66public:
68 typedef COMPARE<KEY_TYPE> Key_compare;
70 typedef KEY_TYPE Key_type;
72 typedef DATA_TYPE Data_type;
74 typedef typename Base_type::Node Node;
77
78 typedef typename Base_type::Iterator Iterator;
79 typedef typename Base_type::Iterator iterator;
80 typedef typename Base_type::Const_iterator Const_iterator;
81 typedef typename Base_type::Const_iterator const_iterator;
82 typedef typename Base_type::Rev_iterator Rev_iterator;
83 typedef typename Base_type::Rev_iterator reverse_iterator;
84 typedef typename Base_type::Const_rev_iterator Const_rev_iterator;
85 typedef typename Base_type::Const_rev_iterator const_reverse_iterator;
86
92 : Base_type(alloc)
93 {}
94
112
113 template<typename... Args>
114 cxx::Pair<Iterator, int> emplace(Args &&...args)
115 { return Base_type::emplace(cxx::forward<Args>(args)...); }
116
122 Data_type const &operator [] (Key_type const &key) const
123 { return this->find_node(key)->second; }
124
135 {
136 Node n = this->find_node(key);
137 if (n)
138 return const_cast<Data_type&>(n->second);
139 else
140 return insert(key, Data_type()).first->second;
141 }
142};
143
144}
145
AVL set.
AVL tree based associative container.
Definition avl_map:60
KEY_TYPE Key_type
Type of the key values.
Definition avl_map:70
Avl_map(Node_allocator const &alloc=Node_allocator())
Create an empty AVL-tree based map.
Definition avl_map:91
COMPARE< KEY_TYPE > Key_compare
Type of the comparison functor.
Definition avl_map:68
Base_type::Node Node
Return type for find.
Definition avl_map:74
Base_type::Node_allocator Node_allocator
Type of the allocator.
Definition avl_map:76
cxx::Pair< Iterator, int > insert(Key_type const &key, Data_type const &data)
Insert a <key, data> pair into the map.
Definition avl_map:110
DATA_TYPE Data_type
Type of the data values.
Definition avl_map:72
Data_type const & operator[](Key_type const &key) const
Get the data for the given key.
Definition avl_map:122
A smart pointer to a tree item.
Definition avl_set:184
Internal: AVL set with internally managed nodes.
Definition avl_set:134
Avl_set_iter< _Node, Item_type, Fwd > Iterator
Forward iterator for the set.
Definition avl_set:236
Node find_node(Key_type const &item) const
Lookup a node equal to item.
Definition avl_set:335
Avl_set_iter< _Node, Item_type, Rev > Rev_iterator
Backward iterator for the set.
Definition avl_set:242
ALLOC< _Node > Node_allocator
Type for the node allocator.
Definition avl_set:219
Avl_set_iter< _Node, Const_item_type, Rev > Const_rev_iterator
Constant backward iterator for the set.
Definition avl_set:245
cxx::Pair< Iterator, int > insert(Item_type const &item)
Insert an item into the set.
Definition avl_set:423
Avl_set_iter< _Node, Const_item_type, Fwd > Const_iterator
Constant forward iterator for the set.
Definition avl_set:239
Standard allocator based on operator new () .
Definition std_alloc:68
Our C++ library.
Definition arith:22
Pair implementation.
Key-getter for Avl_map.
Definition avl_map:37
Generic comparator class that defaults to the less-than operator.
Definition std_ops:30
Pair of two values.
Definition pair:39