Dune Core Modules (2.8.0)

lru.hh
Go to the documentation of this file.
1// -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*-
2// vi: set et ts=4 sw=2 sts=2:
3#ifndef DUNE_COMMON_LRU_HH
4#define DUNE_COMMON_LRU_HH
5
6#include <list>
7#include <utility>
8#include <map>
9#include <memory>
10
12
18namespace Dune {
19
20 namespace {
21
22 /*
23 hide the default traits in an empty namespace
24 */
25 template <typename Key, typename Tp,
26 typename Alloc = std::allocator<Tp> >
27 struct _lru_default_traits
28 {
29 typedef Key key_type;
30 typedef Alloc allocator;
31 typedef std::list< std::pair<Key, Tp> > list_type;
32 typedef typename list_type::iterator iterator;
33 typedef typename std::less<key_type> cmp;
34 typedef std::map< key_type, iterator, cmp,
35 typename std::allocator_traits<allocator>::template rebind_alloc<std::pair<const key_type, iterator> > > map_type;
36 };
37
38 } // end empty namespace
39
47 template <typename Key, typename Tp,
48 typename Traits = _lru_default_traits<Key, Tp> >
49 class lru
50 {
51 typedef typename Traits::list_type list_type;
52 typedef typename Traits::map_type map_type;
53 typedef typename Traits::allocator allocator;
54 typedef typename map_type::iterator map_iterator;
55 typedef typename map_type::const_iterator const_map_iterator;
56
57 public:
58 typedef typename Traits::key_type key_type;
59 typedef typename allocator::value_type value_type;
60 using pointer = typename allocator::value_type*;
61 using const_pointer = typename allocator::value_type const*;
62 using const_reference = typename allocator::value_type const&;
63 using reference = typename allocator::value_type&;
64 typedef typename allocator::size_type size_type;
65 typedef typename list_type::iterator iterator;
66 typedef typename list_type::const_iterator const_iterator;
67
72 reference front()
73 {
74 return _data.front().second;
75 }
76
81 const_reference front() const
82 {
83 return _data.front().second;
84 }
85
90 reference back()
91 {
92 return _data.back().second;
93 }
94
99 const_reference back ([[maybe_unused]] int i) const
100 {
101 return _data.back().second;
102 }
103
104
109 {
110 key_type k = _data.front().first;
111 _data.pop_front();
112 _index.erase(k);
113 }
117 void pop_back()
118 {
119 key_type k = _data.back().first;
120 _data.pop_back();
121 _index.erase(k);
122 }
123
129 iterator find (const key_type & key)
130 {
131 const map_iterator it = _index.find(key);
132 if (it == _index.end()) return _data.end();
133 return it->second;
134 }
135
141 const_iterator find (const key_type & key) const
142 {
143 const map_iterator it = _index.find(key);
144 if (it == _index.end()) return _data.end();
145 return it->second;
146 }
147
159 reference insert (const key_type & key, const_reference data)
160 {
161 std::pair<key_type, value_type> x(key, data);
162 /* insert item as mru */
163 iterator it = _data.insert(_data.begin(), x);
164 /* store index */
165 _index.insert(std::make_pair(key,it));
166
167 return it->second;
168 }
169
173 reference insert (const key_type & key)
174 {
175 return touch (key);
176 }
177
183 reference touch (const key_type & key)
184 {
185 /* query _index for iterator */
186 map_iterator it = _index.find(key);
187 if (it == _index.end())
189 "Failed to touch key " << key << ", it is not in the lru container");
190 /* update _data
191 move it to the front
192 */
193 _data.splice(_data.begin(), _data, it->second);
194 return it->second->second;
195 }
196
200 size_type size() const
201 {
202 return _data.size();
203 }
204
211 void resize(size_type new_size)
212 {
213 assert(new_size <= size());
214
215 while (new_size < size())
216 pop_back();
217 }
218
222 void clear()
223 {
224 _data.clear();
225 _index.clear();
226 }
227
228 private:
229 list_type _data;
230 map_type _index;
231
232 };
233
234} // namespace Dune
235
236#endif // DUNE_COMMON_LRU_HH
Default exception class for range errors.
Definition: exceptions.hh:252
LRU Cache Container.
Definition: lru.hh:50
void pop_back()
Removes the last element.
Definition: lru.hh:117
iterator find(const key_type &key)
Finds the element whose key is k.
Definition: lru.hh:129
reference insert(const key_type &key)
mark data associated with key as most recent
Definition: lru.hh:173
void resize(size_type new_size)
ensure a maximum size of the container
Definition: lru.hh:211
const_reference front() const
Definition: lru.hh:81
size_type size() const
Retrieve number of entries in the container.
Definition: lru.hh:200
reference back()
Definition: lru.hh:90
void pop_front()
Removes the first element.
Definition: lru.hh:108
reference front()
Definition: lru.hh:72
reference touch(const key_type &key)
mark data associated with key as most recent
Definition: lru.hh:183
reference insert(const key_type &key, const_reference data)
Insert a value into the container.
Definition: lru.hh:159
const_iterator find(const key_type &key) const
Finds the element whose key is k.
Definition: lru.hh:141
const_reference back(int i) const
Definition: lru.hh:99
A few common exception classes.
#define DUNE_THROW(E, m)
Definition: exceptions.hh:216
Dune namespace.
Definition: alignedallocator.hh:11
Creative Commons License   |  Legal Statements / Impressum  |  Hosted by TU Dresden  |  generated with Hugo v0.111.3 (Nov 21, 23:30, 2024)