dune-common  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 
18 namespace 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 
73  {
74  return _data.front().second;
75  }
76 
82  {
83  return _data.front().second;
84  }
85 
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 
108  void pop_front()
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 
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
A few common exception classes.
#define DUNE_THROW(E, m)
Definition: exceptions.hh:216
Dune namespace.
Definition: alignedallocator.hh:11
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
list_type::const_iterator const_iterator
Definition: lru.hh:66
void resize(size_type new_size)
ensure a maximum size of the container
Definition: lru.hh:211
allocator::size_type size_type
Definition: lru.hh:64
list_type::iterator iterator
Definition: lru.hh:65
allocator::value_type value_type
Definition: lru.hh:59
const_reference front() const
Definition: lru.hh:81
const_reference back([[maybe_unused]] int i) const
Definition: lru.hh:99
typename allocator::value_type const * const_pointer
Definition: lru.hh:61
size_type size() const
Retrieve number of entries in the container.
Definition: lru.hh:200
typename allocator::value_type & reference
Definition: lru.hh:63
reference back()
Definition: lru.hh:90
void pop_front()
Removes the first element.
Definition: lru.hh:108
reference front()
Definition: lru.hh:72
void clear()
Definition: lru.hh:222
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
typename allocator::value_type * pointer
Definition: lru.hh:60
const_iterator find(const key_type &key) const
Finds the element whose key is k.
Definition: lru.hh:141
typename allocator::value_type const & const_reference
Definition: lru.hh:62
Traits::key_type key_type
Definition: lru.hh:58