| // Copyright 2011 The Chromium Authors |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| // This file contains a template for a Least Recently Used cache that allows |
| // constant-time access to items, but easy identification of the |
| // least-recently-used items for removal. Variations exist to support use as a |
| // Map (`base::LRUCache`), HashMap (`base::HashingLRUCache`), Set |
| // (`base::LRUCacheSet`), or HashSet (`base::HashingLRUCacheSet`). These are |
| // implemented as aliases of `base::internal::LRUCacheBase`, defined at the |
| // bottom of this file. |
| // |
| // The key object (which is identical to the value, in the Set variations) will |
| // be stored twice, so it should support efficient copying. |
| |
| #ifndef BASE_CONTAINERS_LRU_CACHE_H_ |
| #define BASE_CONTAINERS_LRU_CACHE_H_ |
| |
| #include <stddef.h> |
| |
| #include <algorithm> |
| #include <concepts> |
| #include <functional> |
| #include <list> |
| #include <map> |
| #include <type_traits> |
| #include <unordered_map> |
| #include <utility> |
| |
| #include "base/check.h" |
| |
| namespace base { |
| namespace trace_event::internal { |
| |
| template <class LruCacheType> |
| size_t DoEstimateMemoryUsageForLruCache(const LruCacheType&); |
| |
| } // namespace trace_event::internal |
| |
| namespace internal { |
| |
| struct GetKeyFromKVPair { |
| template <typename T1, typename T2> |
| constexpr const T1& operator()(const std::pair<T1, T2>& pair) { |
| return pair.first; |
| } |
| }; |
| |
| // Base class for the LRU cache specializations defined below. |
| template <class ValueType, class GetKeyFromValue, class KeyIndexTemplate> |
| class LRUCacheBase { |
| public: |
| // The contents of the list. This must contain a copy of the key (that may be |
| // extracted via `GetKeyFromValue()(value)` so we can efficiently delete |
| // things given an element of the list. |
| using value_type = ValueType; |
| |
| private: |
| using ValueList = std::list<value_type>; |
| using KeyIndex = |
| typename KeyIndexTemplate::template Type<typename ValueList::iterator>; |
| |
| public: |
| using size_type = typename ValueList::size_type; |
| using key_type = typename KeyIndex::key_type; |
| |
| using iterator = typename ValueList::iterator; |
| using const_iterator = typename ValueList::const_iterator; |
| using reverse_iterator = typename ValueList::reverse_iterator; |
| using const_reverse_iterator = typename ValueList::const_reverse_iterator; |
| |
| enum { NO_AUTO_EVICT = 0 }; |
| |
| // The max_size is the size at which the cache will prune its members to when |
| // a new item is inserted. If the caller wants to manage this itself (for |
| // example, maybe it has special work to do when something is evicted), it |
| // can pass NO_AUTO_EVICT to not restrict the cache size. |
| explicit LRUCacheBase(size_type max_size) : max_size_(max_size) {} |
| |
| // In theory, LRUCacheBase could be copyable, but since copying `ValueList` |
| // might be costly, it's currently move-only to ensure users don't |
| // accidentally incur performance penalties. If you need this to become |
| // copyable, talk to base/ OWNERS. |
| LRUCacheBase(LRUCacheBase&&) noexcept = default; |
| LRUCacheBase& operator=(LRUCacheBase&&) noexcept = default; |
| |
| ~LRUCacheBase() = default; |
| |
| size_type max_size() const { return max_size_; } |
| |
| // Inserts an item into the list. If an existing item has the same key, it is |
| // removed prior to insertion. An iterator indicating the inserted item will |
| // be returned (this will always be the front of the list). |
| // In the map variations of this container, `value_type` is a `std::pair` and |
| // it's preferred to use the `Put(k, v)` overload of this method. |
| iterator Put(value_type&& value) { |
| // Remove any existing item with that key. |
| key_type key = GetKeyFromValue{}(value); |
| typename KeyIndex::iterator index_iter = index_.find(key); |
| if (index_iter != index_.end()) { |
| // Erase the reference to it. The index reference will be replaced in the |
| // code below. |
| Erase(index_iter->second); |
| } else if (max_size_ != NO_AUTO_EVICT) { |
| // New item is being inserted which might make it larger than the maximum |
| // size: kick the oldest thing out if necessary. |
| ShrinkToSize(max_size_ - 1); |
| } |
| |
| ordering_.push_front(std::move(value)); |
| index_.emplace(std::move(key), ordering_.begin()); |
| return ordering_.begin(); |
| } |
| |
| // Inserts an item into the list. If an existing item has the same key, it is |
| // removed prior to insertion. An iterator indicating the inserted item will |
| // be returned (this will always be the front of the list). |
| template <class K, class V> |
| requires(std::same_as<GetKeyFromValue, GetKeyFromKVPair>) |
| iterator Put(K&& key, V&& value) { |
| return Put(value_type{std::forward<K>(key), std::forward<V>(value)}); |
| } |
| |
| // Retrieves the contents of the given key, or end() if not found. This method |
| // has the side effect of moving the requested item to the front of the |
| // recency list. |
| iterator Get(const key_type& key) { |
| typename KeyIndex::iterator index_iter = index_.find(key); |
| if (index_iter == index_.end()) |
| return end(); |
| typename ValueList::iterator iter = index_iter->second; |
| |
| // Move the touched item to the front of the recency ordering. |
| ordering_.splice(ordering_.begin(), ordering_, iter); |
| return ordering_.begin(); |
| } |
| |
| // Retrieves the item associated with a given key and returns it via |
| // result without affecting the ordering (unlike Get()). |
| iterator Peek(const key_type& key) { |
| typename KeyIndex::const_iterator index_iter = index_.find(key); |
| if (index_iter == index_.end()) |
| return end(); |
| return index_iter->second; |
| } |
| |
| const_iterator Peek(const key_type& key) const { |
| typename KeyIndex::const_iterator index_iter = index_.find(key); |
| if (index_iter == index_.end()) |
| return end(); |
| return index_iter->second; |
| } |
| |
| // Exchanges the contents of |this| by the contents of the |other|. |
| void Swap(LRUCacheBase& other) { |
| ordering_.swap(other.ordering_); |
| index_.swap(other.index_); |
| std::swap(max_size_, other.max_size_); |
| } |
| |
| // Erases the item referenced by the given iterator. An iterator to the item |
| // following it will be returned. The iterator must be valid. |
| iterator Erase(iterator pos) { |
| index_.erase(GetKeyFromValue()(*pos)); |
| return ordering_.erase(pos); |
| } |
| |
| // LRUCache entries are often processed in reverse order, so we add this |
| // convenience function (not typically defined by STL containers). |
| reverse_iterator Erase(reverse_iterator pos) { |
| // We have to actually give it the incremented iterator to delete, since |
| // the forward iterator that base() returns is actually one past the item |
| // being iterated over. |
| return reverse_iterator(Erase((++pos).base())); |
| } |
| |
| // Shrinks the cache so it only holds |new_size| items. If |new_size| is |
| // bigger or equal to the current number of items, this will do nothing. |
| void ShrinkToSize(size_type new_size) { |
| for (size_type i = size(); i > new_size; i--) |
| Erase(rbegin()); |
| } |
| |
| // Deletes everything from the cache. |
| void Clear() { |
| index_.clear(); |
| ordering_.clear(); |
| } |
| |
| // Returns the number of elements in the cache. |
| size_type size() const { |
| // We don't use ordering_.size() for the return value because |
| // (as a linked list) it can be O(n). |
| DCHECK(index_.size() == ordering_.size()); |
| return index_.size(); |
| } |
| |
| // Allows iteration over the list. Forward iteration starts with the most |
| // recent item and works backwards. |
| // |
| // Note that since these iterators are actually iterators over a list, you |
| // can keep them as you insert or delete things (as long as you don't delete |
| // the one you are pointing to) and they will still be valid. |
| iterator begin() { return ordering_.begin(); } |
| const_iterator begin() const { return ordering_.begin(); } |
| iterator end() { return ordering_.end(); } |
| const_iterator end() const { return ordering_.end(); } |
| |
| reverse_iterator rbegin() { return ordering_.rbegin(); } |
| const_reverse_iterator rbegin() const { return ordering_.rbegin(); } |
| reverse_iterator rend() { return ordering_.rend(); } |
| const_reverse_iterator rend() const { return ordering_.rend(); } |
| |
| bool empty() const { return ordering_.empty(); } |
| |
| private: |
| template <class LruCacheType> |
| friend size_t trace_event::internal::DoEstimateMemoryUsageForLruCache( |
| const LruCacheType&); |
| |
| ValueList ordering_; |
| // TODO(crbug.com/40069408): Remove annotation once crbug.com/1472363 is |
| // fixed. |
| __attribute__((annotate("blink_gc_plugin_ignore"))) KeyIndex index_; |
| |
| size_type max_size_; |
| }; |
| |
| template <class KeyType, class KeyCompare> |
| struct LRUCacheKeyIndex { |
| template <class ValueType> |
| using Type = std::map<KeyType, ValueType, KeyCompare>; |
| }; |
| |
| template <class KeyType, class KeyHash, class KeyEqual> |
| struct HashingLRUCacheKeyIndex { |
| template <class ValueType> |
| using Type = std::unordered_map<KeyType, ValueType, KeyHash, KeyEqual>; |
| }; |
| |
| } // namespace internal |
| |
| // Implements an LRU cache of `ValueType`, where each value can be uniquely |
| // referenced by `KeyType`. Entries can be iterated in order of |
| // least-recently-used to most-recently-used by iterating from `rbegin()` to |
| // `rend()`, where a "use" is defined as a call to `Put(k, v)` or `Get(k)`. |
| template <class KeyType, class ValueType, class KeyCompare = std::less<KeyType>> |
| using LRUCache = |
| internal::LRUCacheBase<std::pair<KeyType, ValueType>, |
| internal::GetKeyFromKVPair, |
| internal::LRUCacheKeyIndex<KeyType, KeyCompare>>; |
| |
| // Implements an LRU cache of `ValueType`, where each value can be uniquely |
| // referenced by `KeyType`, and `KeyType` may be hashed for O(1) insertion, |
| // removal, and lookup. Entries can be iterated in order of least-recently-used |
| // to most-recently-used by iterating from `rbegin()` to `rend()`, where a "use" |
| // is defined as a call to `Put(k, v)` or `Get(k)`. |
| template <class KeyType, |
| class ValueType, |
| class KeyHash = std::hash<KeyType>, |
| class KeyEqual = std::equal_to<KeyType>> |
| using HashingLRUCache = internal::LRUCacheBase< |
| std::pair<KeyType, ValueType>, |
| internal::GetKeyFromKVPair, |
| internal::HashingLRUCacheKeyIndex<KeyType, KeyHash, KeyEqual>>; |
| |
| // Implements an LRU cache of `ValueType`, where each value is unique. Entries |
| // can be iterated in order of least-recently-used to most-recently-used by |
| // iterating from `rbegin()` to `rend()`, where a "use" is defined as a call to |
| // `Put(v)` or `Get(v)`. |
| template <class ValueType, class Compare = std::less<ValueType>> |
| using LRUCacheSet = |
| internal::LRUCacheBase<ValueType, |
| std::identity, |
| internal::LRUCacheKeyIndex<ValueType, Compare>>; |
| |
| // Implements an LRU cache of `ValueType`, where is value is unique, and may be |
| // hashed for O(1) insertion, removal, and lookup. Entries can be iterated in |
| // order of least-recently-used to most-recently-used by iterating from |
| // `rbegin()` to `rend()`, where a "use" is defined as a call to `Put(v)` or |
| // `Get(v)`. |
| template <class ValueType, |
| class Hash = std::hash<ValueType>, |
| class Equal = std::equal_to<ValueType>> |
| using HashingLRUCacheSet = internal::LRUCacheBase< |
| ValueType, |
| std::identity, |
| internal::HashingLRUCacheKeyIndex<ValueType, Hash, Equal>>; |
| |
| } // namespace base |
| |
| #endif // BASE_CONTAINERS_LRU_CACHE_H_ |