dune-common
2.2.0
|
00001 #ifndef DUNE_COMMON_LRU_HH 00002 #define DUNE_COMMON_LRU_HH 00003 00004 #include <list> 00005 #include <utility> 00006 #include <map> 00007 00013 namespace Dune { 00014 00015 namespace { 00016 00017 /* 00018 hide the default traits in an empty namespace 00019 */ 00020 template <typename _Key, typename _Tp, 00021 typename _Alloc = std::allocator<_Tp> > 00022 struct _lru_default_traits 00023 { 00024 typedef _Key key_type; 00025 typedef _Alloc allocator; 00026 typedef std::list< std::pair<_Key, _Tp> > list_type; 00027 typedef typename list_type::iterator iterator; 00028 typedef typename std::less<key_type> cmp; 00029 typedef std::map< key_type, iterator, cmp, 00030 typename allocator::template rebind<std::pair<const key_type, iterator> >::other > map_type; 00031 }; 00032 00033 } // end empty namespace 00034 00042 template <typename _Key, typename _Tp, 00043 typename _Traits = _lru_default_traits<_Key, _Tp> > 00044 class lru 00045 { 00046 typedef typename _Traits::list_type list_type; 00047 typedef typename _Traits::map_type map_type; 00048 typedef typename _Traits::allocator allocator; 00049 typedef typename map_type::iterator map_iterator; 00050 typedef typename map_type::const_iterator const_map_iterator; 00051 00052 public: 00053 typedef typename _Traits::key_type key_type; 00054 typedef typename allocator::value_type value_type; 00055 typedef typename allocator::pointer pointer; 00056 typedef typename allocator::const_pointer const_pointer; 00057 typedef typename allocator::const_reference const_reference; 00058 typedef typename allocator::reference reference; 00059 typedef typename allocator::size_type size_type; 00060 typedef typename list_type::iterator iterator; 00061 typedef typename list_type::const_iterator const_iterator; 00062 00067 reference front() 00068 { 00069 return _data.front().second; 00070 } 00071 00076 const_reference front() const 00077 { 00078 return _data.front().second; 00079 } 00080 00085 reference back() 00086 { 00087 return _data.back().second; 00088 } 00089 00094 const_reference back (int i) const 00095 { 00096 return _data.back().second; 00097 } 00098 00099 00103 const void pop_front() 00104 { 00105 key_type k = _data.front().first; 00106 _data.pop_front(); 00107 _index.erase(k); 00108 } 00112 const void pop_back() 00113 { 00114 key_type k = _data.back().first; 00115 _data.pop_back(); 00116 _index.erase(k); 00117 } 00118 00124 iterator find (const key_type & key) 00125 { 00126 const map_iterator it = _index.find(key); 00127 if (it == _index.end()) return _data.end(); 00128 return it->second; 00129 } 00130 00136 const_iterator find (const key_type & key) const 00137 { 00138 const map_iterator it = _index.find(key); 00139 if (it == _index.end()) return _data.end(); 00140 return it->second; 00141 } 00142 00153 reference insert (const key_type & key, const_reference data) 00154 { 00155 std::pair<key_type, value_type> x(key, data); 00156 /* insert item as mru */ 00157 iterator it = _data.insert(_data.begin(), x); 00158 /* store index */ 00159 _index.insert(std::make_pair(key,it)); 00160 00161 return it->second; 00162 } 00163 00167 reference insert (const key_type & key) 00168 { 00169 return touch (key); 00170 } 00171 00177 reference touch (const key_type & key) 00178 { 00179 /* query _index for iterator */ 00180 iterator it = _index[key]; 00181 /* update _data 00182 move it to the front 00183 */ 00184 _data.splice(_data.begin(), _data, it); 00185 return it->second; 00186 } 00187 00191 size_type size() const 00192 { 00193 return _data.size(); 00194 } 00195 00199 void resize(size_type new_size) 00200 { 00201 assert(new_size <= size()); 00202 00203 while (new_size < size()) 00204 pop_back(); 00205 } 00206 00210 void clear() 00211 { 00212 _data.clear(); 00213 _index.clear(); 00214 } 00215 00216 private: 00217 list_type _data; 00218 map_type _index; 00219 00220 }; 00221 00222 } // namespace Dune 00223 00224 #endif // DUNE_COMMON_LRU_HH