components/copresence/timed_map.h

   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
  20 namespace copresence {
  21
  22 // TimedMap is a map with the added functionality of clearing any
  23 // key/value pair after its specified lifetime is over.
  24 // TODO(ckehoe): Why is this interface so different from std::map?
  25 template <typename KeyType, typename ValueType>
  26 class TimedMap {
  27  public:
  28   TimedMap(const base::TimeDelta& lifetime, size_t max_elements)
  29       : kEmptyValue(ValueType()),
  30         clock_(new base::DefaultTickClock()),
  31         lifetime_(lifetime),
  32         max_elements_(max_elements) {
  33     timer_.Start(FROM_HERE, lifetime_, this, &TimedMap::ClearExpiredTokens);
  34   }
  35
  36   ~TimedMap() {}
  37
  38   void Add(const KeyType& key, const ValueType& value) {
  39     map_[key] = value;
  40     expiry_queue_.push(KeyTimeTuple(key, clock_->NowTicks() + lifetime_));
  41     while (map_.size() > max_elements_)
  42       ClearOldestToken();
  43   }
  44
  45   bool HasKey(const KeyType& key) {
  46     ClearExpiredTokens();
  47     return map_.find(key) != map_.end();
  48   }
  49
  50   const ValueType& GetValue(const KeyType& key) {
  51     ClearExpiredTokens();
  52     auto elt = map_.find(key);
  53     return elt == map_.end() ? kEmptyValue : elt->second;
  54   }
  55
  56   ValueType* GetMutableValue(const KeyType& key) {
  57     ClearExpiredTokens();
  58     auto elt = map_.find(key);
  59     return elt == map_.end() ? nullptr : &(elt->second);
  60   }
  61
  62   // TODO(ckehoe): Add a unit test for this.
  63   size_t Erase(const KeyType& key) {
  64     return map_.erase(key);
  65   }
  66
  67   void set_clock_for_testing(scoped_ptr<base::TickClock> clock) {
  68     clock_ = clock.Pass();
  69   }
  70
  71  private:
  72   void ClearExpiredTokens() {
  73     while (!expiry_queue_.empty() &&
  74            expiry_queue_.top().second <= clock_->NowTicks())
  75       ClearOldestToken();
  76   }
  77
  78   void ClearOldestToken() {
  79     map_.erase(expiry_queue_.top().first);
  80     expiry_queue_.pop();
  81   }
  82
  83   using KeyTimeTuple = std::pair<KeyType, base::TimeTicks>;
  84
  85   class EarliestFirstComparator {
  86    public:
  87     // This will sort our queue with the 'earliest' time being the top.
  88     bool operator()(const KeyTimeTuple& left, const KeyTimeTuple& right) const {
  89       return left.second > right.second;
  90     }
  91   };
  92
  93   using ExpiryQueue = std::priority_queue<
  94       KeyTimeTuple, std::vector<KeyTimeTuple>, EarliestFirstComparator>;
  95
  96   const ValueType kEmptyValue;
  97
  98   scoped_ptr<base::TickClock> clock_;
  99   base::RepeatingTimer<TimedMap> timer_;
 100   const base::TimeDelta lifetime_;
 101   const size_t max_elements_;
 102   std::map<KeyType, ValueType> map_;
 103   // Priority queue with our element keys ordered by the earliest expiring keys
 104   // first.
 105   ExpiryQueue expiry_queue_;
 106
 107   DISALLOW_COPY_AND_ASSIGN(TimedMap);
 108 };
 109
 110 }  // namespace copresence
 111
 112 #endif  // COMPONENTS_COPRESENCE_TIMED_MAP_H_