1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
|
// Copyright (c) 2012 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#ifndef NET_BASE_EXPIRING_CACHE_H_
#define NET_BASE_EXPIRING_CACHE_H_
#pragma once
#include <map>
#include <utility>
#include "base/basictypes.h"
#include "base/gtest_prod_util.h"
#include "base/time.h"
namespace net {
// Cache implementation where all entries have an explicit expiration policy. As
// new items are added, expired items will be removed first.
// The template types have the following requirements:
// KeyType must be LessThanComparable, Assignable, and CopyConstructible.
// ValueType must be CopyConstructible and Assignable.
template <typename KeyType, typename ValueType>
class ExpiringCache {
private:
// Intentionally violate the C++ Style Guide so that EntryMap is known to be
// a dependent type. Without this, Clang's two-phase lookup complains when
// using EntryMap::const_iterator, while GCC and MSVC happily resolve the
// typename.
// Tuple to represent the value and when it expires.
typedef std::pair<ValueType, base::TimeTicks> Entry;
typedef std::map<KeyType, Entry> EntryMap;
public:
typedef KeyType key_type;
typedef ValueType value_type;
// This class provides a read-only iterator over items in the ExpiringCache
class Iterator {
public:
explicit Iterator(const ExpiringCache& cache)
: cache_(cache),
it_(cache_.entries_.begin()) {
}
~Iterator() {}
bool HasNext() const { return it_ != cache_.entries_.end(); }
void Advance() { ++it_; }
const KeyType& key() const { return it_->first; }
const ValueType& value() const { return it_->second.first; }
const base::TimeTicks& expiration() const { return it_->second.second; }
private:
const ExpiringCache& cache_;
// Use a second layer of type indirection, as both EntryMap and
// EntryMap::const_iterator are dependent types.
typedef typename ExpiringCache::EntryMap EntryMap;
typename EntryMap::const_iterator it_;
};
// Constructs an ExpiringCache that stores up to |max_entries|.
explicit ExpiringCache(size_t max_entries) : max_entries_(max_entries) {}
~ExpiringCache() {}
// Returns the value matching |key|, which must be valid at the time |now|.
// Returns NULL if the item is not found or has expired. If the item has
// expired, it is immediately removed from the cache.
// Note: The returned pointer remains owned by the ExpiringCache and is
// invalidated by a call to a non-const method.
const ValueType* Get(const KeyType& key, base::TimeTicks now) {
typename EntryMap::iterator it = entries_.find(key);
if (it == entries_.end())
return NULL;
// Immediately remove expired entries.
if (!CanUseEntry(it->second, now)) {
entries_.erase(it);
return NULL;
}
return &it->second.first;
}
// Updates or replaces the value associated with |key|.
void Put(const KeyType& key,
const ValueType& value,
base::TimeTicks now,
base::TimeDelta ttl) {
base::TimeTicks expiration = now + ttl;
typename EntryMap::iterator it = entries_.find(key);
if (it == entries_.end()) {
// Compact the cache if it grew beyond the limit.
if (entries_.size() == max_entries_ )
Compact(now);
// No existing entry. Creating a new one.
entries_.insert(std::make_pair(key, Entry(value, expiration)));
} else {
// Update an existing cache entry.
it->second.first = value;
it->second.second = expiration;
}
}
// Empties the cache.
void Clear() {
entries_.clear();
}
// Returns the number of entries in the cache.
size_t size() const { return entries_.size(); }
// Returns the maximum number of entries in the cache.
size_t max_entries() const { return max_entries_; }
bool empty() const { return entries_.empty(); }
private:
FRIEND_TEST_ALL_PREFIXES(ExpiringCacheTest, Compact);
// Returns true if this cache entry's result is valid at time |now|.
static bool CanUseEntry(const Entry& entry, const base::TimeTicks now) {
return entry.second > now;
}
// Prunes entries from the cache to bring it below |max_entries()|.
void Compact(base::TimeTicks now) {
// Clear out expired entries.
typename EntryMap::iterator it;
for (it = entries_.begin(); it != entries_.end(); ) {
if (!CanUseEntry(it->second, now)) {
entries_.erase(it++);
} else {
++it;
}
}
if (entries_.size() < max_entries_)
return;
// If the cache is still too full, start deleting items 'randomly'.
for (it = entries_.begin();
it != entries_.end() && entries_.size() >= max_entries_;) {
entries_.erase(it++);
}
}
// Bound on total size of the cache.
size_t max_entries_;
EntryMap entries_;
DISALLOW_COPY_AND_ASSIGN(ExpiringCache);
};
} // namespace net
#endif // NET_BASE_EXPIRING_CACHE_H_
|
