expiring_cache.h 7.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221
  1. // Copyright (c) 2012 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #ifndef NET_BASE_EXPIRING_CACHE_H_
  5. #define NET_BASE_EXPIRING_CACHE_H_
  6. #include <stddef.h>
  7. #include <map>
  8. #include <utility>
  9. #include "base/gtest_prod_util.h"
  10. #include "base/time/time.h"
  11. namespace net {
  12. template <typename KeyType,
  13. typename ValueType,
  14. typename ExpirationType>
  15. class NoopEvictionHandler {
  16. public:
  17. void Handle(const KeyType& key,
  18. const ValueType& value,
  19. const ExpirationType& expiration,
  20. const ExpirationType& now,
  21. bool onGet) const {
  22. }
  23. };
  24. // Cache implementation where all entries have an explicit expiration policy. As
  25. // new items are added, expired items will be removed first.
  26. // The template types have the following requirements:
  27. // KeyType must be LessThanComparable, Assignable, and CopyConstructible.
  28. // ValueType must be CopyConstructible and Assignable.
  29. // ExpirationType must be CopyConstructible and Assignable.
  30. // ExpirationCompare is a function class that takes two arguments of the
  31. // type ExpirationType and returns a bool. If |comp| is an instance of
  32. // ExpirationCompare, then the expression |comp(current, expiration)| shall
  33. // return true iff |current| is still valid within |expiration|.
  34. //
  35. // A simple use of this class may use base::TimeTicks, which provides a
  36. // monotonically increasing clock, for the expiration type. Because it's always
  37. // increasing, std::less<> can be used, which will simply ensure that |now| is
  38. // sorted before |expiration|:
  39. //
  40. // ExpiringCache<std::string, std::string, base::TimeTicks,
  41. // std::less<base::TimeTicks> > cache(0);
  42. // // Add a value that expires in 5 minutes
  43. // cache.Put("key1", "value1", base::TimeTicks::Now(),
  44. // base::TimeTicks::Now() + base::Minutes(5));
  45. // // Add another value that expires in 10 minutes.
  46. // cache.Put("key2", "value2", base::TimeTicks::Now(),
  47. // base::TimeTicks::Now() + base::Minutes(10));
  48. //
  49. // Alternatively, there may be some more complex expiration criteria, at which
  50. // point a custom functor may be used:
  51. //
  52. // struct ComplexExpirationFunctor {
  53. // bool operator()(const ComplexExpiration& now,
  54. // const ComplexExpiration& expiration) const;
  55. // };
  56. // ExpiringCache<std::string, std::string, ComplexExpiration,
  57. // ComplexExpirationFunctor> cache(15);
  58. // // Add a value that expires once the 'sprocket' has 'cog'-ified.
  59. // cache.Put("key1", "value1", ComplexExpiration("sprocket"),
  60. // ComplexExpiration("cog"));
  61. template <typename KeyType,
  62. typename ValueType,
  63. typename ExpirationType,
  64. typename ExpirationCompare,
  65. typename EvictionHandler = NoopEvictionHandler<KeyType,
  66. ValueType,
  67. ExpirationType> >
  68. class ExpiringCache {
  69. public:
  70. ExpiringCache(const ExpiringCache&) = delete;
  71. ExpiringCache& operator=(const ExpiringCache&) = delete;
  72. private:
  73. // Intentionally violate the C++ Style Guide so that EntryMap is known to be
  74. // a dependent type. Without this, Clang's two-phase lookup complains when
  75. // using EntryMap::const_iterator, while GCC and MSVC happily resolve the
  76. // typename.
  77. // Tuple to represent the value and when it expires.
  78. typedef std::pair<ValueType, ExpirationType> Entry;
  79. typedef std::map<KeyType, Entry> EntryMap;
  80. public:
  81. typedef KeyType key_type;
  82. typedef ValueType value_type;
  83. typedef ExpirationType expiration_type;
  84. // This class provides a read-only iterator over items in the ExpiringCache
  85. class Iterator {
  86. public:
  87. explicit Iterator(const ExpiringCache& cache)
  88. : cache_(cache),
  89. it_(cache_.entries_.begin()) {
  90. }
  91. ~Iterator() = default;
  92. bool HasNext() const { return it_ != cache_.entries_.end(); }
  93. void Advance() { ++it_; }
  94. const KeyType& key() const { return it_->first; }
  95. const ValueType& value() const { return it_->second.first; }
  96. const ExpirationType& expiration() const { return it_->second.second; }
  97. private:
  98. const ExpiringCache& cache_;
  99. // Use a second layer of type indirection, as both EntryMap and
  100. // EntryMap::const_iterator are dependent types.
  101. typedef typename ExpiringCache::EntryMap EntryMap;
  102. typename EntryMap::const_iterator it_;
  103. };
  104. // Constructs an ExpiringCache that stores up to |max_entries|.
  105. explicit ExpiringCache(size_t max_entries) : max_entries_(max_entries) {}
  106. ~ExpiringCache() = default;
  107. // Returns the value matching |key|, which must be valid at the time |now|.
  108. // Returns NULL if the item is not found or has expired. If the item has
  109. // expired, it is immediately removed from the cache.
  110. // Note: The returned pointer remains owned by the ExpiringCache and is
  111. // invalidated by a call to a non-const method.
  112. const ValueType* Get(const KeyType& key, const ExpirationType& now) {
  113. typename EntryMap::iterator it = entries_.find(key);
  114. if (it == entries_.end())
  115. return nullptr;
  116. // Immediately remove expired entries.
  117. if (!expiration_comp_(now, it->second.second)) {
  118. Evict(it, now, true);
  119. return nullptr;
  120. }
  121. return &it->second.first;
  122. }
  123. // Updates or replaces the value associated with |key|.
  124. void Put(const KeyType& key,
  125. const ValueType& value,
  126. const ExpirationType& now,
  127. const ExpirationType& expiration) {
  128. typename EntryMap::iterator it = entries_.find(key);
  129. if (it == entries_.end()) {
  130. // Compact the cache if it grew beyond the limit.
  131. if (entries_.size() == max_entries_ )
  132. Compact(now);
  133. // No existing entry. Creating a new one.
  134. entries_.insert(std::make_pair(key, Entry(value, expiration)));
  135. } else {
  136. // Update an existing cache entry.
  137. it->second.first = value;
  138. it->second.second = expiration;
  139. }
  140. }
  141. // Empties the cache.
  142. void Clear() {
  143. entries_.clear();
  144. }
  145. // Returns the number of entries in the cache.
  146. size_t size() const { return entries_.size(); }
  147. // Returns the maximum number of entries in the cache.
  148. size_t max_entries() const { return max_entries_; }
  149. bool empty() const { return entries_.empty(); }
  150. private:
  151. FRIEND_TEST_ALL_PREFIXES(ExpiringCacheTest, Compact);
  152. FRIEND_TEST_ALL_PREFIXES(ExpiringCacheTest, CustomFunctor);
  153. // Prunes entries from the cache to bring it below |max_entries()|.
  154. void Compact(const ExpirationType& now) {
  155. // Clear out expired entries.
  156. typename EntryMap::iterator it;
  157. for (it = entries_.begin(); it != entries_.end(); ) {
  158. if (!expiration_comp_(now, it->second.second)) {
  159. Evict(it++, now, false);
  160. } else {
  161. ++it;
  162. }
  163. }
  164. if (entries_.size() < max_entries_)
  165. return;
  166. // If the cache is still too full, start deleting items 'randomly'.
  167. for (it = entries_.begin();
  168. it != entries_.end() && entries_.size() >= max_entries_;) {
  169. Evict(it++, now, false);
  170. }
  171. }
  172. void Evict(typename EntryMap::iterator it,
  173. const ExpirationType& now,
  174. bool on_get) {
  175. eviction_handler_.Handle(it->first, it->second.first, it->second.second,
  176. now, on_get);
  177. entries_.erase(it);
  178. }
  179. // Bound on total size of the cache.
  180. size_t max_entries_;
  181. EntryMap entries_;
  182. ExpirationCompare expiration_comp_;
  183. EvictionHandler eviction_handler_;
  184. };
  185. } // namespace net
  186. #endif // NET_BASE_EXPIRING_CACHE_H_