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
15namespace net {
16
17template <typename KeyType,
18          typename ValueType,
19          typename ExpirationType>
20class 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"));
67template <typename KeyType,
68          typename ValueType,
69          typename ExpirationType,
70          typename ExpirationCompare,
71          typename EvictionHandler = NoopEvictionHandler<KeyType,
72                                                         ValueType,
73                                                         ExpirationType> >
74class 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