diff options
Diffstat (limited to 'chromium/net/base/expiring_cache.h')
-rw-r--r-- | chromium/net/base/expiring_cache.h | 218 |
1 files changed, 218 insertions, 0 deletions
diff --git a/chromium/net/base/expiring_cache.h b/chromium/net/base/expiring_cache.h new file mode 100644 index 00000000000..3fbde6594ff --- /dev/null +++ b/chromium/net/base/expiring_cache.h @@ -0,0 +1,218 @@ +// 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 <map> +#include <utility> + +#include "base/basictypes.h" +#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::TimeDelta::FromMinutes(5)); +// // Add another value that expires in 10 minutes. +// cache.Put("key2", "value2", base::TimeTicks::Now(), +// base::TimeTicks::Now() + base::TimeDelta::FromMinutes(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 { + 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() {} + + 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() {} + + // 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 NULL; + + // Immediately remove expired entries. + if (!expiration_comp_(now, it->second.second)) { + Evict(it, now, true); + return NULL; + } + + 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_; + + DISALLOW_COPY_AND_ASSIGN(ExpiringCache); +}; + +} // namespace net + +#endif // NET_BASE_EXPIRING_CACHE_H_ |