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
|
// Copyright 2014 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 COMPONENTS_COPRESENCE_TIMED_MAP_H_
#define COMPONENTS_COPRESENCE_TIMED_MAP_H_
#include <stddef.h>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include "base/macros.h"
#include "base/memory/scoped_ptr.h"
#include "base/time/default_tick_clock.h"
#include "base/time/tick_clock.h"
#include "base/time/time.h"
#include "base/timer/timer.h"
namespace copresence {
// TimedMap is a map with the added functionality of clearing any
// key/value pair after its specified lifetime is over.
// TODO(ckehoe): Why is this interface so different from std::map?
template <typename KeyType, typename ValueType>
class TimedMap {
public:
TimedMap(const base::TimeDelta& lifetime, size_t max_elements)
: kEmptyValue(ValueType()),
clock_(new base::DefaultTickClock()),
lifetime_(lifetime),
max_elements_(max_elements) {
timer_.Start(FROM_HERE, lifetime_, this, &TimedMap::ClearExpiredTokens);
}
~TimedMap() {}
void Add(const KeyType& key, const ValueType& value) {
map_[key] = value;
expiry_queue_.push(KeyTimeTuple(key, clock_->NowTicks() + lifetime_));
while (map_.size() > max_elements_)
ClearOldestToken();
}
bool HasKey(const KeyType& key) {
ClearExpiredTokens();
return map_.find(key) != map_.end();
}
const ValueType& GetValue(const KeyType& key) {
ClearExpiredTokens();
auto elt = map_.find(key);
return elt == map_.end() ? kEmptyValue : elt->second;
}
ValueType* GetMutableValue(const KeyType& key) {
ClearExpiredTokens();
auto elt = map_.find(key);
return elt == map_.end() ? nullptr : &(elt->second);
}
// TODO(ckehoe): Add a unit test for this.
size_t Erase(const KeyType& key) {
return map_.erase(key);
}
void set_clock_for_testing(scoped_ptr<base::TickClock> clock) {
clock_ = std::move(clock);
}
private:
void ClearExpiredTokens() {
while (!expiry_queue_.empty() &&
expiry_queue_.top().second <= clock_->NowTicks())
ClearOldestToken();
}
void ClearOldestToken() {
map_.erase(expiry_queue_.top().first);
expiry_queue_.pop();
}
using KeyTimeTuple = std::pair<KeyType, base::TimeTicks>;
class EarliestFirstComparator {
public:
// This will sort our queue with the 'earliest' time being the top.
bool operator()(const KeyTimeTuple& left, const KeyTimeTuple& right) const {
return left.second > right.second;
}
};
using ExpiryQueue = std::priority_queue<
KeyTimeTuple, std::vector<KeyTimeTuple>, EarliestFirstComparator>;
const ValueType kEmptyValue;
scoped_ptr<base::TickClock> clock_;
base::RepeatingTimer timer_;
const base::TimeDelta lifetime_;
const size_t max_elements_;
std::map<KeyType, ValueType> map_;
// Priority queue with our element keys ordered by the earliest expiring keys
// first.
ExpiryQueue expiry_queue_;
DISALLOW_COPY_AND_ASSIGN(TimedMap);
};
} // namespace copresence
#endif // COMPONENTS_COPRESENCE_TIMED_MAP_H_
|
