00001
00002
00003 #ifndef DUNE_COMMON_LRU_HH
00004 #define DUNE_COMMON_LRU_HH
00005
00006 #include <list>
00007 #include <utility>
00008 #include <map>
00009
00010 #include <dune/common/exceptions.hh>
00011
00017 namespace Dune {
00018
00019 namespace {
00020
00021
00022
00023
00024 template <typename _Key, typename _Tp,
00025 typename _Alloc = std::allocator<_Tp> >
00026 struct _lru_default_traits
00027 {
00028 typedef _Key key_type;
00029 typedef _Alloc allocator;
00030 typedef std::list< std::pair<_Key, _Tp> > list_type;
00031 typedef typename list_type::iterator iterator;
00032 typedef typename std::less<key_type> cmp;
00033 typedef std::map< key_type, iterator, cmp,
00034 typename allocator::template rebind<std::pair<const key_type, iterator> >::other > map_type;
00035 };
00036
00037 }
00038
00046 template <typename _Key, typename _Tp,
00047 typename _Traits = _lru_default_traits<_Key, _Tp> >
00048 class lru
00049 {
00050 typedef typename _Traits::list_type list_type;
00051 typedef typename _Traits::map_type map_type;
00052 typedef typename _Traits::allocator allocator;
00053 typedef typename map_type::iterator map_iterator;
00054 typedef typename map_type::const_iterator const_map_iterator;
00055
00056 public:
00057 typedef typename _Traits::key_type key_type;
00058 typedef typename allocator::value_type value_type;
00059 typedef typename allocator::pointer pointer;
00060 typedef typename allocator::const_pointer const_pointer;
00061 typedef typename allocator::const_reference const_reference;
00062 typedef typename allocator::reference reference;
00063 typedef typename allocator::size_type size_type;
00064 typedef typename list_type::iterator iterator;
00065 typedef typename list_type::const_iterator const_iterator;
00066
00071 reference front()
00072 {
00073 return _data.front().second;
00074 }
00075
00080 const_reference front() const
00081 {
00082 return _data.front().second;
00083 }
00084
00089 reference back()
00090 {
00091 return _data.back().second;
00092 }
00093
00098 const_reference back (int i) const
00099 {
00100 return _data.back().second;
00101 }
00102
00103
00107 void pop_front()
00108 {
00109 key_type k = _data.front().first;
00110 _data.pop_front();
00111 _index.erase(k);
00112 }
00116 void pop_back()
00117 {
00118 key_type k = _data.back().first;
00119 _data.pop_back();
00120 _index.erase(k);
00121 }
00122
00128 iterator find (const key_type & key)
00129 {
00130 const map_iterator it = _index.find(key);
00131 if (it == _index.end()) return _data.end();
00132 return it->second;
00133 }
00134
00140 const_iterator find (const key_type & key) const
00141 {
00142 const map_iterator it = _index.find(key);
00143 if (it == _index.end()) return _data.end();
00144 return it->second;
00145 }
00146
00158 reference insert (const key_type & key, const_reference data)
00159 {
00160 std::pair<key_type, value_type> x(key, data);
00161
00162 iterator it = _data.insert(_data.begin(), x);
00163
00164 _index.insert(std::make_pair(key,it));
00165
00166 return it->second;
00167 }
00168
00172 reference insert (const key_type & key)
00173 {
00174 return touch (key);
00175 }
00176
00182 reference touch (const key_type & key)
00183 {
00184
00185 map_iterator it = _index.find(key);
00186 if (it == _index.end())
00187 DUNE_THROW(Dune::RangeError,
00188 "Failed to touch key " << key << ", it is not in the lru container");
00189
00190
00191
00192 _data.splice(_data.begin(), _data, it->second);
00193 return it->second->second;
00194 }
00195
00199 size_type size() const
00200 {
00201 return _data.size();
00202 }
00203
00210 void resize(size_type new_size)
00211 {
00212 assert(new_size <= size());
00213
00214 while (new_size < size())
00215 pop_back();
00216 }
00217
00221 void clear()
00222 {
00223 _data.clear();
00224 _index.clear();
00225 }
00226
00227 private:
00228 list_type _data;
00229 map_type _index;
00230
00231 };
00232
00233 }
00234
00235 #endif // DUNE_COMMON_LRU_HH