3 #ifndef DUNE_COMMON_LRU_HH 4 #define DUNE_COMMON_LRU_HH 25 template <
typename _Key,
typename _Tp,
26 typename _Alloc = std::allocator<_Tp> >
27 struct _lru_default_traits
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 allocator::template rebind<std::pair<const key_type, iterator> >::other > map_type;
47 template <
typename _Key,
typename _Tp,
48 typename _Traits = _lru_default_traits<_Key, _Tp> >
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;
60 typedef typename allocator::pointer
pointer;
74 return _data.front().second;
83 return _data.front().second;
92 return _data.back().second;
99 const_reference
back (
int i)
const 102 return _data.back().second;
111 key_type k = _data.front().first;
120 key_type k = _data.back().first;
130 iterator
find (
const key_type & key)
132 const map_iterator it = _index.find(key);
133 if (it == _index.end())
return _data.end();
142 const_iterator
find (
const key_type & key)
const 144 const map_iterator it = _index.find(key);
145 if (it == _index.end())
return _data.end();
160 reference
insert (
const key_type & key, const_reference data)
162 std::pair<key_type, value_type> x(key, data);
164 iterator it = _data.insert(_data.begin(), x);
166 _index.insert(std::make_pair(key,it));
184 reference
touch (
const key_type & key)
187 map_iterator it = _index.find(key);
188 if (it == _index.end())
190 "Failed to touch key " << key <<
", it is not in the lru container");
194 _data.splice(_data.begin(), _data, it->second);
195 return it->second->second;
214 assert(new_size <= size());
216 while (new_size < size())
237 #endif // DUNE_COMMON_LRU_HH allocator::value_type value_type
Definition: lru.hh:59
#define DUNE_UNUSED_PARAMETER(parm)
A macro to mark intentionally unused function parameters with.
Definition: unused.hh:25
allocator::pointer pointer
Definition: lru.hh:60
allocator::const_reference const_reference
Definition: lru.hh:62
void pop_front()
Removes the first element.
Definition: lru.hh:109
Definition of the DUNE_UNUSED macro for the case that config.h is not available.
allocator::reference reference
Definition: lru.hh:63
reference front()
Definition: lru.hh:72
void clear()
Definition: lru.hh:223
const_reference back(int i) const
Definition: lru.hh:99
reference touch(const key_type &key)
mark data associated with key as most recent
Definition: lru.hh:184
allocator::const_pointer const_pointer
Definition: lru.hh:61
A few common exception classes.
Dune namespace.
Definition: alignedallocator.hh:9
iterator find(const key_type &key)
Finds the element whose key is k.
Definition: lru.hh:130
list_type::const_iterator const_iterator
Definition: lru.hh:66
size_type size() const
Retrieve number of entries in the container.
Definition: lru.hh:201
reference insert(const key_type &key)
mark data associated with key as most recent
Definition: lru.hh:174
list_type::iterator iterator
Definition: lru.hh:65
void pop_back()
Removes the last element.
Definition: lru.hh:118
const_iterator find(const key_type &key) const
Finds the element whose key is k.
Definition: lru.hh:142
_Traits::key_type key_type
Definition: lru.hh:58
allocator::size_type size_type
Definition: lru.hh:64
const_reference front() const
Definition: lru.hh:81
Default exception class for range errors.
Definition: exceptions.hh:252
void resize(size_type new_size)
ensure a maximum size of the container
Definition: lru.hh:212
reference insert(const key_type &key, const_reference data)
Insert a value into the container.
Definition: lru.hh:160
LRU Cache Container.
Definition: lru.hh:49
#define DUNE_THROW(E, m)
Definition: exceptions.hh:216
reference back()
Definition: lru.hh:90