← Back to branch summary

~alinuxninja/nginx-edge/trunk

« back to all changes in this revision

Viewing changes to debian/modules/ngx_pagespeed/psol/include/third_party/chromium/src/net/base/expiring_cache.h

  • Committer: Vivian
  • Date: 2015-12-04 18:20:11 UTC
  • Revision ID: git-v1:a36f2bc32e884f7473b3a47040e5411306144d7d
* Do not extract psol.tar.gz

Show diffs side-by-side

added added

removed removed

Lines of Context:
debian/modules/ngx_pagespeed/psol/include/third_party/chromium/src/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_