Add the copresence DirectiveHandler.

components/copresence/common/timed_map.h

+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef COMPONENTS_COPRESENCE_COMMON_TIMED_MAP_
+#define COMPONENTS_COPRESENCE_COMMON_TIMED_MAP_
+
+#include <map>
+#include <queue>
+#include <vector>
+
+#include "base/macros.h"
+#include "base/time/time.h"
+#include "base/timer/timer.h"
+
+namespace copresence {
+
+// TimedMap is a map with the added functionality of clearing any
+// key/value pair after their specified lifetime is over.

[Daniel Erat, 2014/07/25 23:09:00]

nit: s/their/its/

[rkc, 2014/07/28 21:01:59]

Done.

+template <typename KeyType, typename ValueType>
+class TimedMap {
+ public:
+  TimedMap(const base::TimeDelta& lifetime, size_t max_elements)
+      : kEmptyValue(ValueType()),
+        lifetime_(lifetime),
+        max_elements_(max_elements) {
+    timer_.Start(FROM_HERE, lifetime_, this, &TimedMap::ClearExpiredTokens);
+  }
+
+  ~TimedMap() {}
+
+  void Add(const KeyType& key, const ValueType& value) {
+    map_[key] = value;
+    expiry_queue_.push(KeyTimeTuple(key, base::Time::Now() + lifetime_));

[Daniel Erat, 2014/07/25 23:09:00]

make this use a base::TickClock instead of calling base::Time::Now() so it'll be
testable

[rkc, 2014/07/28 21:02:00]

Using TimeTicks versus TimeDelta and Time seems, awkward. Still, this seems to
be the only way to make this testable so changing it.
I'll discuss this more offline with you.

Done.

+    while (map_.size() > max_elements_)
+      ClearOldestToken();
+  }
+
+  bool HasKey(const KeyType& key) {
+    ClearExpiredTokens();

[Daniel Erat, 2014/07/25 23:09:01]

mutating the map here and in GetValue() seems a bit strange. why not make these
methods const and then reset |timer_| such that it'll fire when the oldest entry
in the map is due to expire?

[rkc, 2014/07/28 21:01:59]

This method returns synchronously, so even if we reset the timer, it will only
fire 'after' we return here. In which case, we'd have returned an entry that was
already expired.

Since whether an entry has expired or not is really only relevant when we're
'getting' a value, clearing expired entries during that process seemed natural.

The timer is only useful to free memory after we don't need it (in the case of
adding a massive number of entries, then not checking for them again well past
the expiry time); we could completely get rid of it and be functionally
equivalent, just use a bit more memory.

+    return map_.find(key) != map_.end();
+  }
+
+  const ValueType& GetValue(const KeyType& key) {
+    ClearExpiredTokens();
+    typename std::map<KeyType, ValueType>::const_iterator elt = map_.find(key);
+    return elt == map_.end() ? kEmptyValue : elt->second;
+  }
+
+ private:
+  void ClearExpiredTokens() {
+    while (!expiry_queue_.empty() &&
+           expiry_queue_.top().second >= base::Time::Now())

[xiyuan, 2014/07/25 21:02:08]

Should this be "<" to trim keys whose expire time is before now?

[rkc, 2014/07/28 21:02:00]

This is a bug, fixed. Also added unit tests.
Done.

+      ClearOldestToken();
+  }
+
+  void ClearOldestToken() {
+    map_.erase(expiry_queue_.top().first);
+    expiry_queue_.pop();
+  }
+
+  typedef std::pair<KeyType, base::Time> KeyTimeTuple;
+
+  class EarliestFirstComparator {
+   public:
+    // The earlier end_time should be the 'higher' value.

[xiyuan, 2014/07/25 21:02:08]

The comment needs to be updated. What is |end_time|?

[Daniel Erat, 2014/07/25 23:09:00]

nit: s/end_time/end time/ (since i don't think this is referring to a variable
name)

[rkc, 2014/07/28 21:01:59]

Done.

[rkc, 2014/07/28 21:02:00]

Done.

+    bool operator()(const KeyTimeTuple& left, const KeyTimeTuple& right) const {
+      return left.second > right.second;
+    }
+  };
+
+  typedef std::priority_queue<KeyTimeTuple,
+                              std::vector<KeyTimeTuple>,

[Daniel Erat, 2014/07/25 23:09:01]

can you unwrap this? it should fit on the end of the previous line

[rkc, 2014/07/28 21:02:00]

Done, though git cl format will probably break this up again.

+                              EarliestFirstComparator> ExpiryQueue;
+
+  const ValueType kEmptyValue;

[xiyuan, 2014/07/25 21:02:08]

Can we make this a "static" member? Carrying one with each instance seems a bit
wasteful.

[rkc, 2014/07/28 21:01:59]

Can't have global or static const objects in Chrome :-\

+
+  base::RepeatingTimer<TimedMap> timer_;
+  const base::TimeDelta lifetime_;
+  const size_t max_elements_;
+  std::map<KeyType, ValueType> map_;
+  ExpiryQueue expiry_queue_;

[Daniel Erat, 2014/07/25 23:09:01]

add a comment documenting what this contains

[rkc, 2014/07/28 21:02:00]

Done.

+
+  DISALLOW_COPY_AND_ASSIGN(TimedMap);
+};
+
+}  // namespace copresence
+
+#endif  // COMPONENTS_COPRESENCE_COMMON_TIMED_MAP_