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 template <typename KeyType, typename ValueType>
  25 class 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     auto 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_