dune-common  2.2.0
lru.hh
Go to the documentation of this file.
1 #ifndef DUNE_COMMON_LRU_HH
2 #define DUNE_COMMON_LRU_HH
3 
4 #include <list>
5 #include <utility>
6 #include <map>
7 
13 namespace Dune {
14 
15 namespace {
16 
17 /*
18  hide the default traits in an empty namespace
19  */
20 template <typename _Key, typename _Tp,
21  typename _Alloc = std::allocator<_Tp> >
22 struct _lru_default_traits
23 {
24  typedef _Key key_type;
25  typedef _Alloc allocator;
26  typedef std::list< std::pair<_Key, _Tp> > list_type;
27  typedef typename list_type::iterator iterator;
28  typedef typename std::less<key_type> cmp;
29  typedef std::map< key_type, iterator, cmp,
30  typename allocator::template rebind<std::pair<const key_type, iterator> >::other > map_type;
31 };
32 
33 } // end empty namespace
34 
42 template <typename _Key, typename _Tp,
43  typename _Traits = _lru_default_traits<_Key, _Tp> >
44 class lru
45 {
46  typedef typename _Traits::list_type list_type;
47  typedef typename _Traits::map_type map_type;
48  typedef typename _Traits::allocator allocator;
49  typedef typename map_type::iterator map_iterator;
50  typedef typename map_type::const_iterator const_map_iterator;
51 
52 public:
53  typedef typename _Traits::key_type key_type;
54  typedef typename allocator::value_type value_type;
55  typedef typename allocator::pointer pointer;
56  typedef typename allocator::const_pointer const_pointer;
57  typedef typename allocator::const_reference const_reference;
58  typedef typename allocator::reference reference;
59  typedef typename allocator::size_type size_type;
60  typedef typename list_type::iterator iterator;
61  typedef typename list_type::const_iterator const_iterator;
62 
68  {
69  return _data.front().second;
70  }
71 
77  {
78  return _data.front().second;
79  }
80 
86  {
87  return _data.back().second;
88  }
89 
94  const_reference back (int i) const
95  {
96  return _data.back().second;
97  }
98 
99 
103  const void pop_front()
104  {
105  key_type k = _data.front().first;
106  _data.pop_front();
107  _index.erase(k);
108  }
112  const void pop_back()
113  {
114  key_type k = _data.back().first;
115  _data.pop_back();
116  _index.erase(k);
117  }
118 
124  iterator find (const key_type & key)
125  {
126  const map_iterator it = _index.find(key);
127  if (it == _index.end()) return _data.end();
128  return it->second;
129  }
130 
136  const_iterator find (const key_type & key) const
137  {
138  const map_iterator it = _index.find(key);
139  if (it == _index.end()) return _data.end();
140  return it->second;
141  }
142 
154  {
155  std::pair<key_type, value_type> x(key, data);
156  /* insert item as mru */
157  iterator it = _data.insert(_data.begin(), x);
158  /* store index */
159  _index.insert(std::make_pair(key,it));
160 
161  return it->second;
162  }
163 
167  reference insert (const key_type & key)
168  {
169  return touch (key);
170  }
171 
177  reference touch (const key_type & key)
178  {
179  /* query _index for iterator */
180  iterator it = _index[key];
181  /* update _data
182  move it to the front
183  */
184  _data.splice(_data.begin(), _data, it);
185  return it->second;
186  }
187 
191  size_type size() const
192  {
193  return _data.size();
194  }
195 
199  void resize(size_type new_size)
200  {
201  assert(new_size <= size());
202 
203  while (new_size < size())
204  pop_back();
205  }
206 
210  void clear()
211  {
212  _data.clear();
213  _index.clear();
214  }
215 
216 private:
217  list_type _data;
218  map_type _index;
219 
220 };
221 
222 } // namespace Dune
223 
224 #endif // DUNE_COMMON_LRU_HH