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