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: TimedMap(const base::TimeDelta & lifetime,size_t max_elements)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 ~TimedMap()35 ~TimedMap() {} 36 Add(const KeyType & key,const ValueType & value)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 HasKey(const KeyType & key)44 bool HasKey(const KeyType& key) { 45 ClearExpiredTokens(); 46 return map_.find(key) != map_.end(); 47 } 48 GetValue(const KeyType & key)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 set_clock_for_testing(scoped_ptr<base::TickClock> clock)55 void set_clock_for_testing(scoped_ptr<base::TickClock> clock) { 56 clock_ = clock.Pass(); 57 } 58 59 private: ClearExpiredTokens()60 void ClearExpiredTokens() { 61 while (!expiry_queue_.empty() && 62 expiry_queue_.top().second <= clock_->NowTicks()) 63 ClearOldestToken(); 64 } 65 ClearOldestToken()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. operator()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