Home | History | Annotate | Download | only in base 
      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_
    219