net/base/expiring_cache.h

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