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 <functional> 23 #include <list> 24 #include <map> 25 #include <unordered_map> 26 #include <utility> 27 28 #include "base/logging.h" 29 #include "base/macros.h" 30 31 namespace base { 32 33 // MRUCacheBase ---------------------------------------------------------------- 34 35 // This template is used to standardize map type containers that can be used 36 // by MRUCacheBase. This level of indirection is necessary because of the way 37 // that template template params and default template params interact. 38 template <class KeyType, class ValueType, class CompareType> 39 struct MRUCacheStandardMap { 40 typedef std::map<KeyType, ValueType, CompareType> Type; 41 }; 42 43 // Base class for the MRU cache specializations defined below. 44 template <class KeyType, 45 class PayloadType, 46 class HashOrCompareType, 47 template <typename, typename, typename> class MapType = 48 MRUCacheStandardMap> 49 class MRUCacheBase { 50 public: 51 // The payload of the list. This maintains a copy of the key so we can 52 // efficiently delete things given an element of the list. 53 typedef std::pair<KeyType, PayloadType> value_type; 54 55 private: 56 typedef std::list<value_type> PayloadList; 57 typedef typename MapType<KeyType, 58 typename PayloadList::iterator, 59 HashOrCompareType>::Type KeyIndex; 60 61 public: 62 typedef typename PayloadList::size_type size_type; 63 64 typedef typename PayloadList::iterator iterator; 65 typedef typename PayloadList::const_iterator const_iterator; 66 typedef typename PayloadList::reverse_iterator reverse_iterator; 67 typedef typename PayloadList::const_reverse_iterator const_reverse_iterator; 68 69 enum { NO_AUTO_EVICT = 0 }; 70 71 // The max_size is the size at which the cache will prune its members to when 72 // a new item is inserted. If the caller wants to manager this itself (for 73 // example, maybe it has special work to do when something is evicted), it 74 // can pass NO_AUTO_EVICT to not restrict the cache size. 75 explicit MRUCacheBase(size_type max_size) : max_size_(max_size) {} 76 77 virtual ~MRUCacheBase() {} 78 79 size_type max_size() const { return max_size_; } 80 81 // Inserts a payload item with the given key. If an existing item has 82 // the same key, it is removed prior to insertion. An iterator indicating the 83 // inserted item will be returned (this will always be the front of the list). 84 // 85 // The payload will be forwarded. 86 template <typename Payload> 87 iterator Put(const KeyType& key, Payload&& payload) { 88 // Remove any existing payload with that key. 89 typename KeyIndex::iterator index_iter = index_.find(key); 90 if (index_iter != index_.end()) { 91 // Erase the reference to it. The index reference will be replaced in the 92 // code below. 93 Erase(index_iter->second); 94 } else if (max_size_ != NO_AUTO_EVICT) { 95 // New item is being inserted which might make it larger than the maximum 96 // size: kick the oldest thing out if necessary. 97 ShrinkToSize(max_size_ - 1); 98 } 99 100 ordering_.push_front(value_type(key, std::forward<Payload>(payload))); 101 index_.insert(std::make_pair(key, ordering_.begin())); 102 return ordering_.begin(); 103 } 104 105 // Retrieves the contents of the given key, or end() if not found. This method 106 // has the side effect of moving the requested item to the front of the 107 // recency list. 108 // 109 // TODO(brettw) We may want a const version of this function in the future. 110 iterator Get(const KeyType& key) { 111 typename KeyIndex::iterator index_iter = index_.find(key); 112 if (index_iter == index_.end()) 113 return end(); 114 typename PayloadList::iterator iter = index_iter->second; 115 116 // Move the touched item to the front of the recency ordering. 117 ordering_.splice(ordering_.begin(), ordering_, iter); 118 return ordering_.begin(); 119 } 120 121 // Retrieves the payload associated with a given key and returns it via 122 // result without affecting the ordering (unlike Get). 123 iterator Peek(const KeyType& key) { 124 typename KeyIndex::const_iterator index_iter = index_.find(key); 125 if (index_iter == index_.end()) 126 return end(); 127 return index_iter->second; 128 } 129 130 const_iterator Peek(const KeyType& key) const { 131 typename KeyIndex::const_iterator index_iter = index_.find(key); 132 if (index_iter == index_.end()) 133 return end(); 134 return index_iter->second; 135 } 136 137 // Exchanges the contents of |this| by the contents of the |other|. 138 void Swap(MRUCacheBase& other) { 139 ordering_.swap(other.ordering_); 140 index_.swap(other.index_); 141 std::swap(max_size_, other.max_size_); 142 } 143 144 // Erases the item referenced by the given iterator. An iterator to the item 145 // following it will be returned. The iterator must be valid. 146 iterator Erase(iterator pos) { 147 index_.erase(pos->first); 148 return ordering_.erase(pos); 149 } 150 151 // MRUCache entries are often processed in reverse order, so we add this 152 // convenience function (not typically defined by STL containers). 153 reverse_iterator Erase(reverse_iterator pos) { 154 // We have to actually give it the incremented iterator to delete, since 155 // the forward iterator that base() returns is actually one past the item 156 // being iterated over. 157 return reverse_iterator(Erase((++pos).base())); 158 } 159 160 // Shrinks the cache so it only holds |new_size| items. If |new_size| is 161 // bigger or equal to the current number of items, this will do nothing. 162 void ShrinkToSize(size_type new_size) { 163 for (size_type i = size(); i > new_size; i--) 164 Erase(rbegin()); 165 } 166 167 // Deletes everything from the cache. 168 void Clear() { 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 DISALLOW_COPY_AND_ASSIGN(MRUCacheBase); 206 }; 207 208 // MRUCache -------------------------------------------------------------------- 209 210 // A container that does not do anything to free its data. Use this when storing 211 // value types (as opposed to pointers) in the list. 212 template <class KeyType, class PayloadType> 213 class MRUCache : public MRUCacheBase<KeyType, PayloadType, std::less<KeyType>> { 214 private: 215 using ParentType = MRUCacheBase<KeyType, PayloadType, std::less<KeyType>>; 216 217 public: 218 // See MRUCacheBase, noting the possibility of using NO_AUTO_EVICT. 219 explicit MRUCache(typename ParentType::size_type max_size) 220 : ParentType(max_size) {} 221 virtual ~MRUCache() {} 222 223 private: 224 DISALLOW_COPY_AND_ASSIGN(MRUCache); 225 }; 226 227 // HashingMRUCache ------------------------------------------------------------ 228 229 template <class KeyType, class ValueType, class HashType> 230 struct MRUCacheHashMap { 231 typedef std::unordered_map<KeyType, ValueType, HashType> Type; 232 }; 233 234 // This class is similar to MRUCache, except that it uses std::unordered_map as 235 // the map type instead of std::map. Note that your KeyType must be hashable to 236 // use this cache or you need to provide a hashing class. 237 template <class KeyType, class PayloadType, class HashType = std::hash<KeyType>> 238 class HashingMRUCache 239 : public MRUCacheBase<KeyType, PayloadType, HashType, MRUCacheHashMap> { 240 private: 241 using ParentType = 242 MRUCacheBase<KeyType, PayloadType, HashType, MRUCacheHashMap>; 243 244 public: 245 // See MRUCacheBase, noting the possibility of using NO_AUTO_EVICT. 246 explicit HashingMRUCache(typename ParentType::size_type max_size) 247 : ParentType(max_size) {} 248 virtual ~HashingMRUCache() {} 249 250 private: 251 DISALLOW_COPY_AND_ASSIGN(HashingMRUCache); 252 }; 253 254 } // namespace base 255 256 #endif // BASE_CONTAINERS_MRU_CACHE_H_ 257