DUNE PDELab (git)

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// SPDX-FileCopyrightInfo: Copyright © DUNE Project contributors, see file LICENSE.md in module root
4// SPDX-License-Identifier: LicenseRef-GPL-2.0-only-with-DUNE-exception
5#ifndef DUNE_COMMON_LRU_HH
6#define DUNE_COMMON_LRU_HH
7
8#include <list>
9#include <utility>
10#include <map>
11#include <memory>
12
14
20namespace Dune {
21
22 namespace {
23
24 /*
25 hide the default traits in an empty namespace
26 */
27 template <typename Key, typename Tp,
28 typename Alloc = std::allocator<Tp> >
29 struct _lru_default_traits
30 {
31 typedef Key key_type;
32 typedef Alloc allocator;
33 typedef std::list< std::pair<Key, Tp> > list_type;
34 typedef typename list_type::iterator iterator;
35 typedef typename std::less<key_type> cmp;
36 typedef std::map< key_type, iterator, cmp,
37 typename std::allocator_traits<allocator>::template rebind_alloc<std::pair<const key_type, iterator> > > map_type;
38 };
39
40 } // end empty namespace
41
49 template <typename Key, typename Tp,
50 typename Traits = _lru_default_traits<Key, Tp> >
51 class lru
52 {
53 typedef typename Traits::list_type list_type;
54 typedef typename Traits::map_type map_type;
55 typedef typename Traits::allocator allocator;
56 typedef typename map_type::iterator map_iterator;
57 typedef typename map_type::const_iterator const_map_iterator;
58
59 public:
60 typedef typename Traits::key_type key_type;
61 typedef typename allocator::value_type value_type;
62 using pointer = typename allocator::value_type*;
63 using const_pointer = typename allocator::value_type const*;
64 using const_reference = typename allocator::value_type const&;
65 using reference = typename allocator::value_type&;
66 typedef typename allocator::size_type size_type;
67 typedef typename list_type::iterator iterator;
68 typedef typename list_type::const_iterator const_iterator;
69
74 reference front()
75 {
76 return _data.front().second;
77 }
78
83 const_reference front() const
84 {
85 return _data.front().second;
86 }
87
92 reference back()
93 {
94 return _data.back().second;
95 }
96
101 const_reference back ([[maybe_unused]] int i) const
102 {
103 return _data.back().second;
104 }
105
106
111 {
112 key_type k = _data.front().first;
113 _data.pop_front();
114 _index.erase(k);
115 }
119 void pop_back()
120 {
121 key_type k = _data.back().first;
122 _data.pop_back();
123 _index.erase(k);
124 }
125
131 iterator find (const key_type & key)
132 {
133 const map_iterator it = _index.find(key);
134 if (it == _index.end()) return _data.end();
135 return it->second;
136 }
137
143 const_iterator find (const key_type & key) const
144 {
145 const map_iterator it = _index.find(key);
146 if (it == _index.end()) return _data.end();
147 return it->second;
148 }
149
161 reference insert (const key_type & key, const_reference data)
162 {
163 std::pair<key_type, value_type> x(key, data);
164 /* insert item as mru */
165 iterator it = _data.insert(_data.begin(), x);
166 /* store index */
167 _index.insert(std::make_pair(key,it));
168
169 return it->second;
170 }
171
175 reference insert (const key_type & key)
176 {
177 return touch (key);
178 }
179
185 reference touch (const key_type & key)
186 {
187 /* query _index for iterator */
188 map_iterator it = _index.find(key);
189 if (it == _index.end())
191 "Failed to touch key " << key << ", it is not in the lru container");
192 /* update _data
193 move it to the front
194 */
195 _data.splice(_data.begin(), _data, it->second);
196 return it->second->second;
197 }
198
202 size_type size() const
203 {
204 return _data.size();
205 }
206
213 void resize(size_type new_size)
214 {
215 assert(new_size <= size());
216
217 while (new_size < size())
218 pop_back();
219 }
220
224 void clear()
225 {
226 _data.clear();
227 _index.clear();
228 }
229
230 private:
231 list_type _data;
232 map_type _index;
233
234 };
235
236} // namespace Dune
237
238#endif // DUNE_COMMON_LRU_HH
Default exception class for range errors.
Definition: exceptions.hh:254
LRU Cache Container.
Definition: lru.hh:52
void pop_back()
Removes the last element.
Definition: lru.hh:119
iterator find(const key_type &key)
Finds the element whose key is k.
Definition: lru.hh:131
reference insert(const key_type &key)
mark data associated with key as most recent
Definition: lru.hh:175
void resize(size_type new_size)
ensure a maximum size of the container
Definition: lru.hh:213
const_reference front() const
Definition: lru.hh:83
size_type size() const
Retrieve number of entries in the container.
Definition: lru.hh:202
reference back()
Definition: lru.hh:92
void pop_front()
Removes the first element.
Definition: lru.hh:110
reference front()
Definition: lru.hh:74
reference touch(const key_type &key)
mark data associated with key as most recent
Definition: lru.hh:185
reference insert(const key_type &key, const_reference data)
Insert a value into the container.
Definition: lru.hh:161
const_iterator find(const key_type &key) const
Finds the element whose key is k.
Definition: lru.hh:143
const_reference back(int i) const
Definition: lru.hh:101
A few common exception classes.
#define DUNE_THROW(E, m)
Definition: exceptions.hh:218
Dune namespace.
Definition: alignedallocator.hh:13
Creative Commons License   |  Legal Statements / Impressum  |  Hosted by TU Dresden  |  generated with Hugo v0.111.3 (Nov 23, 23:29, 2024)