diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-19 00:47:55 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-19 00:47:55 +0000 |
commit | 26a029d407be480d791972afb5975cf62c9360a6 (patch) | |
tree | f435a8308119effd964b339f76abb83a57c29483 /gfx/angle/checkout/src/common/third_party/base/anglebase/containers/mru_cache.h | |
parent | Initial commit. (diff) | |
download | firefox-26a029d407be480d791972afb5975cf62c9360a6.tar.xz firefox-26a029d407be480d791972afb5975cf62c9360a6.zip |
Adding upstream version 124.0.1.upstream/124.0.1
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'gfx/angle/checkout/src/common/third_party/base/anglebase/containers/mru_cache.h')
-rw-r--r-- | gfx/angle/checkout/src/common/third_party/base/anglebase/containers/mru_cache.h | 275 |
1 files changed, 275 insertions, 0 deletions
diff --git a/gfx/angle/checkout/src/common/third_party/base/anglebase/containers/mru_cache.h b/gfx/angle/checkout/src/common/third_party/base/anglebase/containers/mru_cache.h new file mode 100644 index 0000000000..30b564aff6 --- /dev/null +++ b/gfx/angle/checkout/src/common/third_party/base/anglebase/containers/mru_cache.h @@ -0,0 +1,275 @@ +// Copyright (c) 2011 The Chromium Authors. All rights reserved. +// 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 Most Recently Used cache that allows +// constant-time access to items using a key, but easy identification of the +// least-recently-used items for removal. Each key can only be associated with +// one payload item at a time. +// +// The key object will be stored twice, so it should support efficient copying. +// +// NOTE: While all operations are O(1), this code is written for +// legibility rather than optimality. If future profiling identifies this as +// a bottleneck, there is room for smaller values of 1 in the O(1). :] + +#ifndef ANGLEBASE_CONTAINERS_MRU_CACHE_H_ +#define ANGLEBASE_CONTAINERS_MRU_CACHE_H_ + +#include <stddef.h> + +#include <algorithm> +#include <functional> +#include <list> +#include <map> +#include <unordered_map> +#include <utility> + +#include "anglebase/logging.h" +#include "anglebase/macros.h" + +namespace angle +{ + +namespace base +{ + +// MRUCacheBase ---------------------------------------------------------------- + +// This template is used to standardize map type containers that can be used +// by MRUCacheBase. This level of indirection is necessary because of the way +// that template template params and default template params interact. +template <class KeyType, class ValueType, class CompareType> +struct MRUCacheStandardMap +{ + typedef std::map<KeyType, ValueType, CompareType> Type; +}; + +// Base class for the MRU cache specializations defined below. +template <class KeyType, + class PayloadType, + class HashOrCompareType, + template <typename, typename, typename> class MapType = MRUCacheStandardMap> +class MRUCacheBase +{ + public: + // The payload of the list. This maintains a copy of the key so we can + // efficiently delete things given an element of the list. + typedef std::pair<KeyType, PayloadType> value_type; + + private: + typedef std::list<value_type> PayloadList; + typedef + typename MapType<KeyType, typename PayloadList::iterator, HashOrCompareType>::Type KeyIndex; + + public: + typedef typename PayloadList::size_type size_type; + + typedef typename PayloadList::iterator iterator; + typedef typename PayloadList::const_iterator const_iterator; + typedef typename PayloadList::reverse_iterator reverse_iterator; + typedef typename PayloadList::const_reverse_iterator 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 manager 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 MRUCacheBase(size_type max_size) : max_size_(max_size) {} + + virtual ~MRUCacheBase() {} + + size_type max_size() const { return max_size_; } + + // Inserts a payload item with the given key. 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). + // + // The payload will be forwarded. + template <typename Payload> + iterator Put(const KeyType &key, Payload &&payload) + { + // Remove any existing payload with that key. + 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_.emplace_front(key, std::forward<Payload>(payload)); + index_.emplace(key, ordering_.begin()); + return ordering_.begin(); + } + + // 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 KeyType &key) + { + typename KeyIndex::iterator index_iter = index_.find(key); + if (index_iter == index_.end()) + return end(); + typename PayloadList::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 payload associated with a given key and returns it via + // result without affecting the ordering (unlike Get). + iterator Peek(const KeyType &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 KeyType &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(MRUCacheBase &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(pos->first); + return ordering_.erase(pos); + } + + // MRUCache 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: + PayloadList ordering_; + KeyIndex index_; + + size_type max_size_; + + DISALLOW_COPY_AND_ASSIGN(MRUCacheBase); +}; + +// MRUCache -------------------------------------------------------------------- + +// A container that does not do anything to free its data. Use this when storing +// value types (as opposed to pointers) in the list. +template <class KeyType, class PayloadType, class CompareType = std::less<KeyType>> +class MRUCache : public MRUCacheBase<KeyType, PayloadType, CompareType> +{ + private: + using ParentType = MRUCacheBase<KeyType, PayloadType, CompareType>; + + public: + // See MRUCacheBase, noting the possibility of using NO_AUTO_EVICT. + explicit MRUCache(typename ParentType::size_type max_size) : ParentType(max_size) {} + virtual ~MRUCache() {} + + private: + DISALLOW_COPY_AND_ASSIGN(MRUCache); +}; + +// HashingMRUCache ------------------------------------------------------------ + +template <class KeyType, class ValueType, class HashType> +struct MRUCacheHashMap +{ + typedef std::unordered_map<KeyType, ValueType, HashType> Type; +}; + +// This class is similar to MRUCache, except that it uses std::unordered_map as +// the map type instead of std::map. Note that your KeyType must be hashable to +// use this cache or you need to provide a hashing class. +template <class KeyType, class PayloadType, class HashType = std::hash<KeyType>> +class HashingMRUCache : public MRUCacheBase<KeyType, PayloadType, HashType, MRUCacheHashMap> +{ + private: + using ParentType = MRUCacheBase<KeyType, PayloadType, HashType, MRUCacheHashMap>; + + public: + // See MRUCacheBase, noting the possibility of using NO_AUTO_EVICT. + explicit HashingMRUCache(typename ParentType::size_type max_size) : ParentType(max_size) {} + virtual ~HashingMRUCache() override {} + + private: + DISALLOW_COPY_AND_ASSIGN(HashingMRUCache); +}; + +} // namespace base + +} // namespace angle + +#endif // ANGLEBASE_CONTAINERS_MRU_CACHE_H_ |