1// Copyright 2014 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 COMPONENTS_COPRESENCE_TIMED_MAP_H_
6#define COMPONENTS_COPRESENCE_TIMED_MAP_H_
7
8#include <map>
9#include <queue>
10#include <utility>
11#include <vector>
12
13#include "base/macros.h"
14#include "base/memory/scoped_ptr.h"
15#include "base/time/default_tick_clock.h"
16#include "base/time/tick_clock.h"
17#include "base/time/time.h"
18#include "base/timer/timer.h"
19
20namespace copresence {
21
22// TimedMap is a map with the added functionality of clearing any
23// key/value pair after its specified lifetime is over.
24template <typename KeyType, typename ValueType>
25class TimedMap {
26 public:
27  TimedMap(const base::TimeDelta& lifetime, size_t max_elements)
28      : kEmptyValue(ValueType()),
29        clock_(new base::DefaultTickClock()),
30        lifetime_(lifetime),
31        max_elements_(max_elements) {
32    timer_.Start(FROM_HERE, lifetime_, this, &TimedMap::ClearExpiredTokens);
33  }
34
35  ~TimedMap() {}
36
37  void Add(const KeyType& key, const ValueType& value) {
38    map_[key] = value;
39    expiry_queue_.push(KeyTimeTuple(key, clock_->NowTicks() + lifetime_));
40    while (map_.size() > max_elements_)
41      ClearOldestToken();
42  }
43
44  bool HasKey(const KeyType& key) {
45    ClearExpiredTokens();
46    return map_.find(key) != map_.end();
47  }
48
49  const ValueType& GetValue(const KeyType& key) {
50    ClearExpiredTokens();
51    typename std::map<KeyType, ValueType>::const_iterator elt = map_.find(key);
52    return elt == map_.end() ? kEmptyValue : elt->second;
53  }
54
55  void set_clock_for_testing(scoped_ptr<base::TickClock> clock) {
56    clock_ = clock.Pass();
57  }
58
59 private:
60  void ClearExpiredTokens() {
61    while (!expiry_queue_.empty() &&
62           expiry_queue_.top().second <= clock_->NowTicks())
63      ClearOldestToken();
64  }
65
66  void ClearOldestToken() {
67    map_.erase(expiry_queue_.top().first);
68    expiry_queue_.pop();
69  }
70
71  typedef std::pair<KeyType, base::TimeTicks> KeyTimeTuple;
72
73  class EarliestFirstComparator {
74   public:
75    // This will sort our queue with the 'earliest' time being the top.
76    bool operator()(const KeyTimeTuple& left, const KeyTimeTuple& right) const {
77      return left.second > right.second;
78    }
79  };
80
81  typedef std::priority_queue<KeyTimeTuple, std::vector<KeyTimeTuple>,
82                              EarliestFirstComparator> ExpiryQueue;
83
84  const ValueType kEmptyValue;
85
86  scoped_ptr<base::TickClock> clock_;
87  base::RepeatingTimer<TimedMap> timer_;
88  const base::TimeDelta lifetime_;
89  const size_t max_elements_;
90  std::map<KeyType, ValueType> map_;
91  // Priority queue with our element keys ordered by the earliest expiring keys
92  // first.
93  ExpiryQueue expiry_queue_;
94
95  DISALLOW_COPY_AND_ASSIGN(TimedMap);
96};
97
98}  // namespace copresence
99
100#endif  // COMPONENTS_COPRESENCE_TIMED_MAP_H_
101