1 // Copyright 2011 The Chromium Authors 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 Least Recently Used cache that allows 6 // constant-time access to items, but easy identification of the 7 // least-recently-used items for removal. Variations exist to support use as a 8 // Map (`base::LRUCache`), HashMap (`base::HashingLRUCache`), Set 9 // (`base::LRUCacheSet`), or HashSet (`base::HashingLRUCacheSet`). These are 10 // implemented as aliases of `base::internal::LRUCacheBase`, defined at the 11 // bottom of this file. 12 // 13 // The key object (which is identical to the value, in the Set variations) will 14 // be stored twice, so it should support efficient copying. 15 16 #ifndef BASE_CONTAINERS_LRU_CACHE_H_ 17 #define BASE_CONTAINERS_LRU_CACHE_H_ 18 19 #include <stddef.h> 20 21 #include <algorithm> 22 #include <functional> 23 #include <list> 24 #include <map> 25 #include <type_traits> 26 #include <unordered_map> 27 #include <utility> 28 29 #include "base/check.h" 30 31 namespace base { 32 namespace trace_event::internal { 33 34 template <class LruCacheType> 35 size_t DoEstimateMemoryUsageForLruCache(const LruCacheType&); 36 37 } // namespace trace_event::internal 38 39 namespace internal { 40 41 struct GetKeyFromKVPair { 42 template <typename T1, typename T2> operatorGetKeyFromKVPair43 constexpr const T1& operator()(const std::pair<T1, T2>& pair) { 44 return pair.first; 45 } 46 }; 47 48 // Base class for the LRU cache specializations defined below. 49 template <class ValueType, class GetKeyFromValue, class KeyIndexTemplate> 50 class LRUCacheBase { 51 public: 52 // The contents of the list. This must contain a copy of the key (that may be 53 // extracted via `GetKeyFromValue()(value)` so we can efficiently delete 54 // things given an element of the list. 55 using value_type = ValueType; 56 57 private: 58 using ValueList = std::list<value_type>; 59 using KeyIndex = 60 typename KeyIndexTemplate::template Type<typename ValueList::iterator>; 61 62 public: 63 using size_type = typename ValueList::size_type; 64 using key_type = typename KeyIndex::key_type; 65 66 using iterator = typename ValueList::iterator; 67 using const_iterator = typename ValueList::const_iterator; 68 using reverse_iterator = typename ValueList::reverse_iterator; 69 using const_reverse_iterator = typename ValueList::const_reverse_iterator; 70 71 enum { NO_AUTO_EVICT = 0 }; 72 73 // The max_size is the size at which the cache will prune its members to when 74 // a new item is inserted. If the caller wants to manage this itself (for 75 // example, maybe it has special work to do when something is evicted), it 76 // can pass NO_AUTO_EVICT to not restrict the cache size. LRUCacheBase(size_type max_size)77 explicit LRUCacheBase(size_type max_size) : max_size_(max_size) {} 78 79 // In theory, LRUCacheBase could be copyable, but since copying `ValueList` 80 // might be costly, it's currently move-only to ensure users don't 81 // accidentally incur performance penalties. If you need this to become 82 // copyable, talk to base/ OWNERS. 83 LRUCacheBase(LRUCacheBase&&) noexcept = default; 84 LRUCacheBase& operator=(LRUCacheBase&&) noexcept = default; 85 86 ~LRUCacheBase() = default; 87 max_size()88 size_type max_size() const { return max_size_; } 89 90 // Inserts an item into the list. If an existing item has the same key, it is 91 // removed prior to insertion. An iterator indicating the inserted item will 92 // be returned (this will always be the front of the list). 93 // In the map variations of this container, `value_type` is a `std::pair` and 94 // it's preferred to use the `Put(k, v)` overload of this method. Put(value_type && value)95 iterator Put(value_type&& value) { 96 // Remove any existing item with that key. 97 key_type key = GetKeyFromValue{}(value); 98 typename KeyIndex::iterator index_iter = index_.find(key); 99 if (index_iter != index_.end()) { 100 // Erase the reference to it. The index reference will be replaced in the 101 // code below. 102 Erase(index_iter->second); 103 } else if (max_size_ != NO_AUTO_EVICT) { 104 // New item is being inserted which might make it larger than the maximum 105 // size: kick the oldest thing out if necessary. 106 ShrinkToSize(max_size_ - 1); 107 } 108 109 ordering_.push_front(std::move(value)); 110 index_.emplace(std::move(key), ordering_.begin()); 111 return ordering_.begin(); 112 } 113 114 // Inserts an item into the list. If an existing item has the same key, it is 115 // removed prior to insertion. An iterator indicating the inserted item will 116 // be returned (this will always be the front of the list). 117 template < 118 class K, 119 class V, 120 class MapKeyGetter = GetKeyFromKVPair, 121 class = std::enable_if_t<std::is_same_v<MapKeyGetter, GetKeyFromValue>>> Put(K && key,V && value)122 iterator Put(K&& key, V&& value) { 123 return Put(value_type{std::forward<K>(key), std::forward<V>(value)}); 124 } 125 126 // Retrieves the contents of the given key, or end() if not found. This method 127 // has the side effect of moving the requested item to the front of the 128 // recency list. Get(const key_type & key)129 iterator Get(const key_type& key) { 130 typename KeyIndex::iterator index_iter = index_.find(key); 131 if (index_iter == index_.end()) 132 return end(); 133 typename ValueList::iterator iter = index_iter->second; 134 135 // Move the touched item to the front of the recency ordering. 136 ordering_.splice(ordering_.begin(), ordering_, iter); 137 return ordering_.begin(); 138 } 139 140 // Retrieves the item associated with a given key and returns it via 141 // result without affecting the ordering (unlike Get()). Peek(const key_type & key)142 iterator Peek(const key_type& key) { 143 typename KeyIndex::const_iterator index_iter = index_.find(key); 144 if (index_iter == index_.end()) 145 return end(); 146 return index_iter->second; 147 } 148 Peek(const key_type & key)149 const_iterator Peek(const key_type& key) const { 150 typename KeyIndex::const_iterator index_iter = index_.find(key); 151 if (index_iter == index_.end()) 152 return end(); 153 return index_iter->second; 154 } 155 156 // Exchanges the contents of |this| by the contents of the |other|. Swap(LRUCacheBase & other)157 void Swap(LRUCacheBase& other) { 158 ordering_.swap(other.ordering_); 159 index_.swap(other.index_); 160 std::swap(max_size_, other.max_size_); 161 } 162 163 // Erases the item referenced by the given iterator. An iterator to the item 164 // following it will be returned. The iterator must be valid. Erase(iterator pos)165 iterator Erase(iterator pos) { 166 index_.erase(GetKeyFromValue()(*pos)); 167 return ordering_.erase(pos); 168 } 169 170 // LRUCache entries are often processed in reverse order, so we add this 171 // convenience function (not typically defined by STL containers). Erase(reverse_iterator pos)172 reverse_iterator Erase(reverse_iterator pos) { 173 // We have to actually give it the incremented iterator to delete, since 174 // the forward iterator that base() returns is actually one past the item 175 // being iterated over. 176 return reverse_iterator(Erase((++pos).base())); 177 } 178 179 // Shrinks the cache so it only holds |new_size| items. If |new_size| is 180 // bigger or equal to the current number of items, this will do nothing. ShrinkToSize(size_type new_size)181 void ShrinkToSize(size_type new_size) { 182 for (size_type i = size(); i > new_size; i--) 183 Erase(rbegin()); 184 } 185 186 // Deletes everything from the cache. Clear()187 void Clear() { 188 index_.clear(); 189 ordering_.clear(); 190 } 191 192 // Returns the number of elements in the cache. size()193 size_type size() const { 194 // We don't use ordering_.size() for the return value because 195 // (as a linked list) it can be O(n). 196 DCHECK(index_.size() == ordering_.size()); 197 return index_.size(); 198 } 199 200 // Allows iteration over the list. Forward iteration starts with the most 201 // recent item and works backwards. 202 // 203 // Note that since these iterators are actually iterators over a list, you 204 // can keep them as you insert or delete things (as long as you don't delete 205 // the one you are pointing to) and they will still be valid. begin()206 iterator begin() { return ordering_.begin(); } begin()207 const_iterator begin() const { return ordering_.begin(); } end()208 iterator end() { return ordering_.end(); } end()209 const_iterator end() const { return ordering_.end(); } 210 rbegin()211 reverse_iterator rbegin() { return ordering_.rbegin(); } rbegin()212 const_reverse_iterator rbegin() const { return ordering_.rbegin(); } rend()213 reverse_iterator rend() { return ordering_.rend(); } rend()214 const_reverse_iterator rend() const { return ordering_.rend(); } 215 empty()216 bool empty() const { return ordering_.empty(); } 217 218 private: 219 template <class LruCacheType> 220 friend size_t trace_event::internal::DoEstimateMemoryUsageForLruCache( 221 const LruCacheType&); 222 223 ValueList ordering_; 224 // TODO(crbug.com/1472363): Remove annotation once crbug.com/1472363 is fixed. 225 __attribute__((annotate("blink_gc_plugin_ignore"))) KeyIndex index_; 226 227 size_type max_size_; 228 }; 229 230 template <class KeyType, class KeyCompare> 231 struct LRUCacheKeyIndex { 232 template <class ValueType> 233 using Type = std::map<KeyType, ValueType, KeyCompare>; 234 }; 235 236 template <class KeyType, class KeyHash, class KeyEqual> 237 struct HashingLRUCacheKeyIndex { 238 template <class ValueType> 239 using Type = std::unordered_map<KeyType, ValueType, KeyHash, KeyEqual>; 240 }; 241 242 } // namespace internal 243 244 // Implements an LRU cache of `ValueType`, where each value can be uniquely 245 // referenced by `KeyType`. Entries can be iterated in order of 246 // least-recently-used to most-recently-used by iterating from `rbegin()` to 247 // `rend()`, where a "use" is defined as a call to `Put(k, v)` or `Get(k)`. 248 template <class KeyType, class ValueType, class KeyCompare = std::less<KeyType>> 249 using LRUCache = 250 internal::LRUCacheBase<std::pair<KeyType, ValueType>, 251 internal::GetKeyFromKVPair, 252 internal::LRUCacheKeyIndex<KeyType, KeyCompare>>; 253 254 // Implements an LRU cache of `ValueType`, where each value can be uniquely 255 // referenced by `KeyType`, and `KeyType` may be hashed for O(1) insertion, 256 // removal, and lookup. Entries can be iterated in order of least-recently-used 257 // to most-recently-used by iterating from `rbegin()` to `rend()`, where a "use" 258 // is defined as a call to `Put(k, v)` or `Get(k)`. 259 template <class KeyType, 260 class ValueType, 261 class KeyHash = std::hash<KeyType>, 262 class KeyEqual = std::equal_to<KeyType>> 263 using HashingLRUCache = internal::LRUCacheBase< 264 std::pair<KeyType, ValueType>, 265 internal::GetKeyFromKVPair, 266 internal::HashingLRUCacheKeyIndex<KeyType, KeyHash, KeyEqual>>; 267 268 // Implements an LRU cache of `ValueType`, where each value is unique. Entries 269 // can be iterated in order of least-recently-used to most-recently-used by 270 // iterating from `rbegin()` to `rend()`, where a "use" is defined as a call to 271 // `Put(v)` or `Get(v)`. 272 template <class ValueType, class Compare = std::less<ValueType>> 273 using LRUCacheSet = 274 internal::LRUCacheBase<ValueType, 275 std::identity, 276 internal::LRUCacheKeyIndex<ValueType, Compare>>; 277 278 // Implements an LRU cache of `ValueType`, where is value is unique, and may be 279 // hashed for O(1) insertion, removal, and lookup. Entries can be iterated in 280 // order of least-recently-used to most-recently-used by iterating from 281 // `rbegin()` to `rend()`, where a "use" is defined as a call to `Put(v)` or 282 // `Get(v)`. 283 template <class ValueType, 284 class Hash = std::hash<ValueType>, 285 class Equal = std::equal_to<ValueType>> 286 using HashingLRUCacheSet = internal::LRUCacheBase< 287 ValueType, 288 std::identity, 289 internal::HashingLRUCacheKeyIndex<ValueType, Hash, Equal>>; 290 291 } // namespace base 292 293 #endif // BASE_CONTAINERS_LRU_CACHE_H_ 294