15f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// Copyright 2014 The Chromium Authors. All rights reserved. 25f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 35f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// found in the LICENSE file. 45f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 56e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)#ifndef COMPONENTS_COPRESENCE_TIMED_MAP_H_ 66e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)#define COMPONENTS_COPRESENCE_TIMED_MAP_H_ 75f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 85f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)#include <map> 95f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)#include <queue> 105f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)#include <utility> 115f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)#include <vector> 125f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 135f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)#include "base/macros.h" 146e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)#include "base/memory/scoped_ptr.h" 155f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)#include "base/time/default_tick_clock.h" 165f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)#include "base/time/tick_clock.h" 175f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)#include "base/time/time.h" 185f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)#include "base/timer/timer.h" 195f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 205f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)namespace copresence { 215f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 225f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// TimedMap is a map with the added functionality of clearing any 235f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// key/value pair after its specified lifetime is over. 245f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)template <typename KeyType, typename ValueType> 255f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)class TimedMap { 265f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) public: 275f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) TimedMap(const base::TimeDelta& lifetime, size_t max_elements) 285f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) : kEmptyValue(ValueType()), 295f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) clock_(new base::DefaultTickClock()), 305f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) lifetime_(lifetime), 315f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) max_elements_(max_elements) { 325f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) timer_.Start(FROM_HERE, lifetime_, this, &TimedMap::ClearExpiredTokens); 335f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) } 345f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 355f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) ~TimedMap() {} 365f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 375f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) void Add(const KeyType& key, const ValueType& value) { 385f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) map_[key] = value; 395f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) expiry_queue_.push(KeyTimeTuple(key, clock_->NowTicks() + lifetime_)); 405f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) while (map_.size() > max_elements_) 415f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) ClearOldestToken(); 425f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) } 435f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 445f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) bool HasKey(const KeyType& key) { 455f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) ClearExpiredTokens(); 465f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) return map_.find(key) != map_.end(); 475f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) } 485f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 495f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) const ValueType& GetValue(const KeyType& key) { 505f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) ClearExpiredTokens(); 515f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) typename std::map<KeyType, ValueType>::const_iterator elt = map_.find(key); 525f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) return elt == map_.end() ? kEmptyValue : elt->second; 535f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) } 545f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 556e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) void set_clock_for_testing(scoped_ptr<base::TickClock> clock) { 566e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) clock_ = clock.Pass(); 576e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) } 585f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 595f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) private: 605f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) void ClearExpiredTokens() { 615f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) while (!expiry_queue_.empty() && 625f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) expiry_queue_.top().second <= clock_->NowTicks()) 635f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) ClearOldestToken(); 645f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) } 655f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 665f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) void ClearOldestToken() { 675f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) map_.erase(expiry_queue_.top().first); 685f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) expiry_queue_.pop(); 695f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) } 705f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 715f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) typedef std::pair<KeyType, base::TimeTicks> KeyTimeTuple; 725f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 735f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) class EarliestFirstComparator { 745f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) public: 755f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) // This will sort our queue with the 'earliest' time being the top. 765f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) bool operator()(const KeyTimeTuple& left, const KeyTimeTuple& right) const { 775f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) return left.second > right.second; 785f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) } 795f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) }; 805f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 815f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) typedef std::priority_queue<KeyTimeTuple, std::vector<KeyTimeTuple>, 825f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) EarliestFirstComparator> ExpiryQueue; 835f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 845f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) const ValueType kEmptyValue; 855f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 866e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) scoped_ptr<base::TickClock> clock_; 875f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) base::RepeatingTimer<TimedMap> timer_; 885f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) const base::TimeDelta lifetime_; 895f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) const size_t max_elements_; 905f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) std::map<KeyType, ValueType> map_; 915f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) // Priority queue with our element keys ordered by the earliest expiring keys 925f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) // first. 935f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) ExpiryQueue expiry_queue_; 945f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 955f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) DISALLOW_COPY_AND_ASSIGN(TimedMap); 965f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)}; 975f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 985f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)} // namespace copresence 995f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 1006e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)#endif // COMPONENTS_COPRESENCE_TIMED_MAP_H_ 101