123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221 |
- // Copyright (c) 2012 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.
- #ifndef NET_BASE_EXPIRING_CACHE_H_
- #define NET_BASE_EXPIRING_CACHE_H_
- #include <stddef.h>
- #include <map>
- #include <utility>
- #include "base/gtest_prod_util.h"
- #include "base/time/time.h"
- namespace net {
- template <typename KeyType,
- typename ValueType,
- typename ExpirationType>
- class NoopEvictionHandler {
- public:
- void Handle(const KeyType& key,
- const ValueType& value,
- const ExpirationType& expiration,
- const ExpirationType& now,
- bool onGet) const {
- }
- };
- // Cache implementation where all entries have an explicit expiration policy. As
- // new items are added, expired items will be removed first.
- // The template types have the following requirements:
- // KeyType must be LessThanComparable, Assignable, and CopyConstructible.
- // ValueType must be CopyConstructible and Assignable.
- // ExpirationType must be CopyConstructible and Assignable.
- // ExpirationCompare is a function class that takes two arguments of the
- // type ExpirationType and returns a bool. If |comp| is an instance of
- // ExpirationCompare, then the expression |comp(current, expiration)| shall
- // return true iff |current| is still valid within |expiration|.
- //
- // A simple use of this class may use base::TimeTicks, which provides a
- // monotonically increasing clock, for the expiration type. Because it's always
- // increasing, std::less<> can be used, which will simply ensure that |now| is
- // sorted before |expiration|:
- //
- // ExpiringCache<std::string, std::string, base::TimeTicks,
- // std::less<base::TimeTicks> > cache(0);
- // // Add a value that expires in 5 minutes
- // cache.Put("key1", "value1", base::TimeTicks::Now(),
- // base::TimeTicks::Now() + base::Minutes(5));
- // // Add another value that expires in 10 minutes.
- // cache.Put("key2", "value2", base::TimeTicks::Now(),
- // base::TimeTicks::Now() + base::Minutes(10));
- //
- // Alternatively, there may be some more complex expiration criteria, at which
- // point a custom functor may be used:
- //
- // struct ComplexExpirationFunctor {
- // bool operator()(const ComplexExpiration& now,
- // const ComplexExpiration& expiration) const;
- // };
- // ExpiringCache<std::string, std::string, ComplexExpiration,
- // ComplexExpirationFunctor> cache(15);
- // // Add a value that expires once the 'sprocket' has 'cog'-ified.
- // cache.Put("key1", "value1", ComplexExpiration("sprocket"),
- // ComplexExpiration("cog"));
- template <typename KeyType,
- typename ValueType,
- typename ExpirationType,
- typename ExpirationCompare,
- typename EvictionHandler = NoopEvictionHandler<KeyType,
- ValueType,
- ExpirationType> >
- class ExpiringCache {
- public:
- ExpiringCache(const ExpiringCache&) = delete;
- ExpiringCache& operator=(const ExpiringCache&) = delete;
- private:
- // Intentionally violate the C++ Style Guide so that EntryMap is known to be
- // a dependent type. Without this, Clang's two-phase lookup complains when
- // using EntryMap::const_iterator, while GCC and MSVC happily resolve the
- // typename.
- // Tuple to represent the value and when it expires.
- typedef std::pair<ValueType, ExpirationType> Entry;
- typedef std::map<KeyType, Entry> EntryMap;
- public:
- typedef KeyType key_type;
- typedef ValueType value_type;
- typedef ExpirationType expiration_type;
- // This class provides a read-only iterator over items in the ExpiringCache
- class Iterator {
- public:
- explicit Iterator(const ExpiringCache& cache)
- : cache_(cache),
- it_(cache_.entries_.begin()) {
- }
- ~Iterator() = default;
- bool HasNext() const { return it_ != cache_.entries_.end(); }
- void Advance() { ++it_; }
- const KeyType& key() const { return it_->first; }
- const ValueType& value() const { return it_->second.first; }
- const ExpirationType& expiration() const { return it_->second.second; }
- private:
- const ExpiringCache& cache_;
- // Use a second layer of type indirection, as both EntryMap and
- // EntryMap::const_iterator are dependent types.
- typedef typename ExpiringCache::EntryMap EntryMap;
- typename EntryMap::const_iterator it_;
- };
- // Constructs an ExpiringCache that stores up to |max_entries|.
- explicit ExpiringCache(size_t max_entries) : max_entries_(max_entries) {}
- ~ExpiringCache() = default;
- // Returns the value matching |key|, which must be valid at the time |now|.
- // Returns NULL if the item is not found or has expired. If the item has
- // expired, it is immediately removed from the cache.
- // Note: The returned pointer remains owned by the ExpiringCache and is
- // invalidated by a call to a non-const method.
- const ValueType* Get(const KeyType& key, const ExpirationType& now) {
- typename EntryMap::iterator it = entries_.find(key);
- if (it == entries_.end())
- return nullptr;
- // Immediately remove expired entries.
- if (!expiration_comp_(now, it->second.second)) {
- Evict(it, now, true);
- return nullptr;
- }
- return &it->second.first;
- }
- // Updates or replaces the value associated with |key|.
- void Put(const KeyType& key,
- const ValueType& value,
- const ExpirationType& now,
- const ExpirationType& expiration) {
- typename EntryMap::iterator it = entries_.find(key);
- if (it == entries_.end()) {
- // Compact the cache if it grew beyond the limit.
- if (entries_.size() == max_entries_ )
- Compact(now);
- // No existing entry. Creating a new one.
- entries_.insert(std::make_pair(key, Entry(value, expiration)));
- } else {
- // Update an existing cache entry.
- it->second.first = value;
- it->second.second = expiration;
- }
- }
- // Empties the cache.
- void Clear() {
- entries_.clear();
- }
- // Returns the number of entries in the cache.
- size_t size() const { return entries_.size(); }
- // Returns the maximum number of entries in the cache.
- size_t max_entries() const { return max_entries_; }
- bool empty() const { return entries_.empty(); }
- private:
- FRIEND_TEST_ALL_PREFIXES(ExpiringCacheTest, Compact);
- FRIEND_TEST_ALL_PREFIXES(ExpiringCacheTest, CustomFunctor);
- // Prunes entries from the cache to bring it below |max_entries()|.
- void Compact(const ExpirationType& now) {
- // Clear out expired entries.
- typename EntryMap::iterator it;
- for (it = entries_.begin(); it != entries_.end(); ) {
- if (!expiration_comp_(now, it->second.second)) {
- Evict(it++, now, false);
- } else {
- ++it;
- }
- }
- if (entries_.size() < max_entries_)
- return;
- // If the cache is still too full, start deleting items 'randomly'.
- for (it = entries_.begin();
- it != entries_.end() && entries_.size() >= max_entries_;) {
- Evict(it++, now, false);
- }
- }
- void Evict(typename EntryMap::iterator it,
- const ExpirationType& now,
- bool on_get) {
- eviction_handler_.Handle(it->first, it->second.first, it->second.second,
- now, on_get);
- entries_.erase(it);
- }
- // Bound on total size of the cache.
- size_t max_entries_;
- EntryMap entries_;
- ExpirationCompare expiration_comp_;
- EvictionHandler eviction_handler_;
- };
- } // namespace net
- #endif // NET_BASE_EXPIRING_CACHE_H_
|