1 // Copyright (c) 2011 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 // This file contains a template for a Most Recently Used cache that allows 6 // constant-time access to items using a key, but easy identification of the 7 // least-recently-used items for removal. Each key can only be associated with 8 // one payload item at a time. 9 // 10 // The key object will be stored twice, so it should support efficient copying. 11 // 12 // NOTE: While all operations are O(1), this code is written for 13 // legibility rather than optimality. If future profiling identifies this as 14 // a bottleneck, there is room for smaller values of 1 in the O(1). :] 15 16 #ifndef BASE_CONTAINERS_MRU_CACHE_H_ 17 #define BASE_CONTAINERS_MRU_CACHE_H_ 18 19 #include <stddef.h> 20 21 #include <algorithm> 22 #include <list> 23 #include <map> 24 #include <utility> 25 26 #include "base/containers/hash_tables.h" 27 #include "base/logging.h" 28 #include "base/macros.h" 29 30 namespace base { 31 32 // MRUCacheBase ---------------------------------------------------------------- 33 34 // This template is used to standardize map type containers that can be used 35 // by MRUCacheBase. This level of indirection is necessary because of the way 36 // that template template params and default template params interact. 37 template <class KeyType, class ValueType> 38 struct MRUCacheStandardMap { 39 typedef std::map<KeyType, ValueType> Type; 40 }; 41 42 // Base class for the MRU cache specializations defined below. 43 // The deletor will get called on all payloads that are being removed or 44 // replaced. 45 template <class KeyType, class PayloadType, class DeletorType, 46 template <typename, typename> class MapType = MRUCacheStandardMap> 47 class MRUCacheBase { 48 public: 49 // The payload of the list. This maintains a copy of the key so we can 50 // efficiently delete things given an element of the list. 51 typedef std::pair<KeyType, PayloadType> value_type; 52 53 private: 54 typedef std::list<value_type> PayloadList; 55 typedef typename MapType<KeyType, 56 typename PayloadList::iterator>::Type KeyIndex; 57 58 public: 59 typedef typename PayloadList::size_type size_type; 60 61 typedef typename PayloadList::iterator iterator; 62 typedef typename PayloadList::const_iterator const_iterator; 63 typedef typename PayloadList::reverse_iterator reverse_iterator; 64 typedef typename PayloadList::const_reverse_iterator const_reverse_iterator; 65 66 enum { NO_AUTO_EVICT = 0 }; 67 68 // The max_size is the size at which the cache will prune its members to when 69 // a new item is inserted. If the caller wants to manager this itself (for 70 // example, maybe it has special work to do when something is evicted), it 71 // can pass NO_AUTO_EVICT to not restrict the cache size. 72 explicit MRUCacheBase(size_type max_size) : max_size_(max_size) { 73 } 74 75 MRUCacheBase(size_type max_size, const DeletorType& deletor) 76 : max_size_(max_size), deletor_(deletor) { 77 } 78 79 virtual ~MRUCacheBase() { 80 iterator i = begin(); 81 while (i != end()) 82 i = Erase(i); 83 } 84 85 size_type max_size() const { return max_size_; } 86 87 // Inserts a payload item with the given key. If an existing item has 88 // the same key, it is removed prior to insertion. An iterator indicating the 89 // inserted item will be returned (this will always be the front of the list). 90 // 91 // The payload will be copied. In the case of an OwningMRUCache, this function 92 // will take ownership of the pointer. 93 iterator Put(const KeyType& key, const PayloadType& payload) { 94 // Remove any existing payload with that key. 95 typename KeyIndex::iterator index_iter = index_.find(key); 96 if (index_iter != index_.end()) { 97 // Erase the reference to it. This will call the deletor on the removed 98 // element. The index reference will be replaced in the code below. 99 Erase(index_iter->second); 100 } else if (max_size_ != NO_AUTO_EVICT) { 101 // New item is being inserted which might make it larger than the maximum 102 // size: kick the oldest thing out if necessary. 103 ShrinkToSize(max_size_ - 1); 104 } 105 106 ordering_.push_front(value_type(key, payload)); 107 index_.insert(std::make_pair(key, ordering_.begin())); 108 return ordering_.begin(); 109 } 110 111 // Retrieves the contents of the given key, or end() if not found. This method 112 // has the side effect of moving the requested item to the front of the 113 // recency list. 114 // 115 // TODO(brettw) We may want a const version of this function in the future. 116 iterator Get(const KeyType& key) { 117 typename KeyIndex::iterator index_iter = index_.find(key); 118 if (index_iter == index_.end()) 119 return end(); 120 typename PayloadList::iterator iter = index_iter->second; 121 122 // Move the touched item to the front of the recency ordering. 123 ordering_.splice(ordering_.begin(), ordering_, iter); 124 return ordering_.begin(); 125 } 126 127 // Retrieves the payload associated with a given key and returns it via 128 // result without affecting the ordering (unlike Get). 129 iterator Peek(const KeyType& key) { 130 typename KeyIndex::const_iterator index_iter = index_.find(key); 131 if (index_iter == index_.end()) 132 return end(); 133 return index_iter->second; 134 } 135 136 const_iterator Peek(const KeyType& key) const { 137 typename KeyIndex::const_iterator index_iter = index_.find(key); 138 if (index_iter == index_.end()) 139 return end(); 140 return index_iter->second; 141 } 142 143 // Exchanges the contents of |this| by the contents of the |other|. 144 void Swap(MRUCacheBase& other) { 145 ordering_.swap(other.ordering_); 146 index_.swap(other.index_); 147 std::swap(deletor_, other.deletor_); 148 std::swap(max_size_, other.max_size_); 149 } 150 151 // Erases the item referenced by the given iterator. An iterator to the item 152 // following it will be returned. The iterator must be valid. 153 iterator Erase(iterator pos) { 154 deletor_(pos->second); 155 index_.erase(pos->first); 156 return ordering_.erase(pos); 157 } 158 159 // MRUCache entries are often processed in reverse order, so we add this 160 // convenience function (not typically defined by STL containers). 161 reverse_iterator Erase(reverse_iterator pos) { 162 // We have to actually give it the incremented iterator to delete, since 163 // the forward iterator that base() returns is actually one past the item 164 // being iterated over. 165 return reverse_iterator(Erase((++pos).base())); 166 } 167 168 // Shrinks the cache so it only holds |new_size| items. If |new_size| is 169 // bigger or equal to the current number of items, this will do nothing. 170 void ShrinkToSize(size_type new_size) { 171 for (size_type i = size(); i > new_size; i--) 172 Erase(rbegin()); 173 } 174 175 // Deletes everything from the cache. 176 void Clear() { 177 for (typename PayloadList::iterator i(ordering_.begin()); 178 i != ordering_.end(); ++i) 179 deletor_(i->second); 180 index_.clear(); 181 ordering_.clear(); 182 } 183 184 // Returns the number of elements in the cache. 185 size_type size() const { 186 // We don't use ordering_.size() for the return value because 187 // (as a linked list) it can be O(n). 188 DCHECK(index_.size() == ordering_.size()); 189 return index_.size(); 190 } 191 192 // Allows iteration over the list. Forward iteration starts with the most 193 // recent item and works backwards. 194 // 195 // Note that since these iterators are actually iterators over a list, you 196 // can keep them as you insert or delete things (as long as you don't delete 197 // the one you are pointing to) and they will still be valid. 198 iterator begin() { return ordering_.begin(); } 199 const_iterator begin() const { return ordering_.begin(); } 200 iterator end() { return ordering_.end(); } 201 const_iterator end() const { return ordering_.end(); } 202 203 reverse_iterator rbegin() { return ordering_.rbegin(); } 204 const_reverse_iterator rbegin() const { return ordering_.rbegin(); } 205 reverse_iterator rend() { return ordering_.rend(); } 206 const_reverse_iterator rend() const { return ordering_.rend(); } 207 208 bool empty() const { return ordering_.empty(); } 209 210 private: 211 PayloadList ordering_; 212 KeyIndex index_; 213 214 size_type max_size_; 215 216 DeletorType deletor_; 217 218 DISALLOW_COPY_AND_ASSIGN(MRUCacheBase); 219 }; 220 221 // MRUCache -------------------------------------------------------------------- 222 223 // A functor that does nothing. Used by the MRUCache. 224 template<class PayloadType> 225 class MRUCacheNullDeletor { 226 public: 227 void operator()(const PayloadType& payload) {} 228 }; 229 230 // A container that does not do anything to free its data. Use this when storing 231 // value types (as opposed to pointers) in the list. 232 template <class KeyType, class PayloadType> 233 class MRUCache : public MRUCacheBase<KeyType, 234 PayloadType, 235 MRUCacheNullDeletor<PayloadType> > { 236 private: 237 typedef MRUCacheBase<KeyType, PayloadType, 238 MRUCacheNullDeletor<PayloadType> > ParentType; 239 240 public: 241 // See MRUCacheBase, noting the possibility of using NO_AUTO_EVICT. 242 explicit MRUCache(typename ParentType::size_type max_size) 243 : ParentType(max_size) { 244 } 245 virtual ~MRUCache() { 246 } 247 248 private: 249 DISALLOW_COPY_AND_ASSIGN(MRUCache); 250 }; 251 252 // OwningMRUCache -------------------------------------------------------------- 253 254 template<class PayloadType> 255 class MRUCachePointerDeletor { 256 public: 257 void operator()(const PayloadType& payload) { delete payload; } 258 }; 259 260 // A cache that owns the payload type, which must be a non-const pointer type. 261 // The pointers will be deleted when they are removed, replaced, or when the 262 // cache is destroyed. 263 template <class KeyType, class PayloadType> 264 class OwningMRUCache 265 : public MRUCacheBase<KeyType, 266 PayloadType, 267 MRUCachePointerDeletor<PayloadType> > { 268 private: 269 typedef MRUCacheBase<KeyType, PayloadType, 270 MRUCachePointerDeletor<PayloadType> > ParentType; 271 272 public: 273 // See MRUCacheBase, noting the possibility of using NO_AUTO_EVICT. 274 explicit OwningMRUCache(typename ParentType::size_type max_size) 275 : ParentType(max_size) { 276 } 277 virtual ~OwningMRUCache() { 278 } 279 280 private: 281 DISALLOW_COPY_AND_ASSIGN(OwningMRUCache); 282 }; 283 284 // HashingMRUCache ------------------------------------------------------------ 285 286 template <class KeyType, class ValueType> 287 struct MRUCacheHashMap { 288 typedef base::hash_map<KeyType, ValueType> Type; 289 }; 290 291 // This class is similar to MRUCache, except that it uses base::hash_map as 292 // the map type instead of std::map. Note that your KeyType must be hashable 293 // to use this cache. 294 template <class KeyType, class PayloadType> 295 class HashingMRUCache : public MRUCacheBase<KeyType, 296 PayloadType, 297 MRUCacheNullDeletor<PayloadType>, 298 MRUCacheHashMap> { 299 private: 300 typedef MRUCacheBase<KeyType, PayloadType, 301 MRUCacheNullDeletor<PayloadType>, 302 MRUCacheHashMap> ParentType; 303 304 public: 305 // See MRUCacheBase, noting the possibility of using NO_AUTO_EVICT. 306 explicit HashingMRUCache(typename ParentType::size_type max_size) 307 : ParentType(max_size) { 308 } 309 virtual ~HashingMRUCache() { 310 } 311 312 private: 313 DISALLOW_COPY_AND_ASSIGN(HashingMRUCache); 314 }; 315 316 } // namespace base 317 318 #endif // BASE_CONTAINERS_MRU_CACHE_H_ 319