Add an associative map type that allows values to expire after certain durations.

BUG=114343


Review URL: http://codereview.chromium.org/9407001

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@123454 0039d316-1c4b-4281-b951-d872f2087c98

3 files changed, 409 insertions, 0 deletions

diff --git a/net/base/expiring_cache.h b/net/base/expiring_cache.h
new file mode 100644
index 0000000..cb2d537
--- /dev/null
+++ b/net/base/expiring_cache.h
@@ -0,0 +1,162 @@
+// Copyright (c) 2012 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 NET_BASE_EXPIRING_CACHE_H_
+#define NET_BASE_EXPIRING_CACHE_H_
+#pragma once
+
+#include <map>
+#include <utility>
+
+#include "base/basictypes.h"
+#include "base/gtest_prod_util.h"
+#include "base/time.h"
+
+namespace net {
+
+// Cache implementation where all entries have an explicit expiration policy. As
+// new items are added, expired items will be removed first.
+// The template types have the following requirements:
+//  KeyType must be LessThanComparable, Assignable, and CopyConstructible.
+//  ValueType must be CopyConstructible and Assignable.
+template <typename KeyType, typename ValueType>
+class ExpiringCache {
+ private:
+  // Intentionally violate the C++ Style Guide so that EntryMap is known to be
+  // a dependent type. Without this, Clang's two-phase lookup complains when
+  // using EntryMap::const_iterator, while GCC and MSVC happily resolve the
+  // typename.
+
+  // Tuple to represent the value and when it expires.
+  typedef std::pair<ValueType, base::TimeTicks> Entry;
+  typedef std::map<KeyType, Entry> EntryMap;
+
+ public:
+  typedef KeyType key_type;
+  typedef ValueType value_type;
+
+  // This class provides a read-only iterator over items in the ExpiringCache
+  class Iterator {
+   public:
+    explicit Iterator(const ExpiringCache& cache)
+        : cache_(cache),
+          it_(cache_.entries_.begin()) {
+    }
+    ~Iterator() {}
+
+    bool HasNext() const { return it_ != cache_.entries_.end(); }
+    void Advance() { ++it_; }
+
+    const KeyType& key() const { return it_->first; }
+    const ValueType& value() const { return it_->second.first; }
+    const base::TimeTicks& expiration() const { return it_->second.second; }
+
+   private:
+    const ExpiringCache& cache_;
+
+    // Use a second layer of type indirection, as both EntryMap and
+    // EntryMap::const_iterator are dependent types.
+    typedef typename ExpiringCache::EntryMap EntryMap;
+    typename EntryMap::const_iterator it_;
+  };
+
+
+  // Constructs an ExpiringCache that stores up to |max_entries|.
+  explicit ExpiringCache(size_t max_entries) : max_entries_(max_entries) {}
+  ~ExpiringCache() {}
+
+  // Returns the value matching |key|, which must be valid at the time |now|.
+  // Returns NULL if the item is not found or has expired. If the item has
+  // expired, it is immediately removed from the cache.
+  // Note: The returned pointer remains owned by the ExpiringCache and is
+  // invalidated by a call to a non-const method.
+  const ValueType* Get(const KeyType& key, base::TimeTicks now) {
+    typename EntryMap::iterator it = entries_.find(key);
+    if (it == entries_.end())
+      return NULL;
+
+    // Immediately remove expired entries.
+    if (!CanUseEntry(it->second, now)) {
+      entries_.erase(it);
+      return NULL;
+    }
+
+    return &it->second.first;
+  }
+
+  // Updates or replaces the value associated with |key|.
+  void Put(const KeyType& key,
+           const ValueType& value,
+           base::TimeTicks now,
+           base::TimeDelta ttl) {
+    base::TimeTicks expiration = now + ttl;
+    typename EntryMap::iterator it = entries_.find(key);
+    if (it == entries_.end()) {
+      // Compact the cache if it grew beyond the limit.
+      if (entries_.size() == max_entries_ )
+        Compact(now);
+
+      // No existing entry. Creating a new one.
+      entries_.insert(std::make_pair(key, Entry(value, expiration)));
+    } else {
+      // Update an existing cache entry.
+      it->second.first = value;
+      it->second.second = expiration;
+    }
+  }
+
+  // Empties the cache.
+  void Clear() {
+    entries_.clear();
+  }
+
+  // Returns the number of entries in the cache.
+  size_t size() const { return entries_.size(); }
+
+  // Returns the maximum number of entries in the cache.
+  size_t max_entries() const { return max_entries_; }
+
+  bool empty() const { return entries_.empty(); }
+
+ private:
+  FRIEND_TEST_ALL_PREFIXES(ExpiringCacheTest, Compact);
+
+  // Returns true if this cache entry's result is valid at time |now|.
+  static bool CanUseEntry(const Entry& entry, const base::TimeTicks now) {
+    return entry.second > now;
+  }
+
+  // Prunes entries from the cache to bring it below |max_entries()|.
+  void Compact(base::TimeTicks now) {
+    // Clear out expired entries.
+    typename EntryMap::iterator it;
+    for (it = entries_.begin(); it != entries_.end(); ) {
+      if (!CanUseEntry(it->second, now)) {
+        entries_.erase(it++);
+      } else {
+        ++it;
+      }
+    }
+
+    if (entries_.size() < max_entries_)
+      return;
+
+    // If the cache is still too full, start deleting items 'randomly'.
+    for (it = entries_.begin();
+         it != entries_.end() && entries_.size() >= max_entries_;) {
+      entries_.erase(it++);
+    }
+  }
+
+  // Bound on total size of the cache.
+  size_t max_entries_;
+
+  EntryMap entries_;
+
+  DISALLOW_COPY_AND_ASSIGN(ExpiringCache);
+};
+
+}  // namespace net
+
+#endif  // NET_BASE_EXPIRING_CACHE_H_
diff --git a/net/base/expiring_cache_unittest.cc b/net/base/expiring_cache_unittest.cc
new file mode 100644
index 0000000..364af81
--- /dev/null
+++ b/net/base/expiring_cache_unittest.cc
@@ -0,0 +1,245 @@
+// Copyright (c) 2012 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.
+
+#include "net/base/expiring_cache.h"
+
+#include "base/stl_util.h"
+#include "base/stringprintf.h"
+#include "testing/gmock/include/gmock/gmock.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+using testing::Pointee;
+using testing::StrEq;
+
+namespace net {
+
+namespace {
+
+const int kMaxCacheEntries = 10;
+typedef ExpiringCache<std::string, std::string> Cache;
+
+}  // namespace
+
+TEST(ExpiringCacheTest, Basic) {
+  const base::TimeDelta kTTL = base::TimeDelta::FromSeconds(10);
+
+  Cache cache(kMaxCacheEntries);
+
+  // Start at t=0.
+  base::TimeTicks now;
+  EXPECT_EQ(0U, cache.size());
+
+  // Add an entry at t=0
+  EXPECT_FALSE(cache.Get("entry1", now));
+  cache.Put("entry1", "test1", now, kTTL);
+  EXPECT_THAT(cache.Get("entry1", now), Pointee(StrEq("test1")));
+  EXPECT_EQ(1U, cache.size());
+
+  // Advance to t=5.
+  now += base::TimeDelta::FromSeconds(5);
+
+  // Add an entry at t=5.
+  EXPECT_FALSE(cache.Get("entry2", now));
+  cache.Put("entry2", "test2", now, kTTL);
+  EXPECT_THAT(cache.Get("entry2", now), Pointee(StrEq("test2")));
+  EXPECT_EQ(2U, cache.size());
+
+  // Advance to t=9.
+  now += base::TimeDelta::FromSeconds(4);
+
+  // Verify that the entries added are still retrievable and usable.
+  EXPECT_THAT(cache.Get("entry1", now), Pointee(StrEq("test1")));
+  EXPECT_THAT(cache.Get("entry2", now), Pointee(StrEq("test2")));
+
+  // Advance to t=10; entry1 is now expired.
+  now += base::TimeDelta::FromSeconds(1);
+
+  EXPECT_FALSE(cache.Get("entry1", now));
+  EXPECT_THAT(cache.Get("entry2", now), Pointee(StrEq("test2")));
+
+  // The expired element should no longer be in the cache.
+  EXPECT_EQ(1U, cache.size());
+
+  // Update entry1 so it is no longer expired.
+  cache.Put("entry1", "test1", now, kTTL);
+
+  // Both entries should be retrievable and usable.
+  EXPECT_EQ(2U, cache.size());
+  EXPECT_THAT(cache.Get("entry1", now), Pointee(StrEq("test1")));
+  EXPECT_THAT(cache.Get("entry2", now), Pointee(StrEq("test2")));
+
+  // Advance to t=20; both entries are now expired.
+  now += base::TimeDelta::FromSeconds(10);
+
+  EXPECT_FALSE(cache.Get("entry1", now));
+  EXPECT_FALSE(cache.Get("entry2", now));
+}
+
+TEST(ExpiringCacheTest, Compact) {
+  const base::TimeDelta kTTL = base::TimeDelta::FromSeconds(10);
+
+  Cache cache(kMaxCacheEntries);
+
+  // Start at t=0.
+  base::TimeTicks now;
+  EXPECT_EQ(0U, cache.size());
+
+  // Add five valid entries at t=10.
+  base::TimeTicks t10 = now + kTTL;
+  for (int i = 0; i < 5; ++i) {
+    std::string name = base::StringPrintf("valid%d", i);
+    cache.Put(name, "I'm valid!", t10, kTTL);  // Expire at t=20.
+  }
+  EXPECT_EQ(5U, cache.size());
+
+  // Add three expired entries at t=10.
+  for (int i = 0; i < 3; ++i) {
+    std::string name = base::StringPrintf("expired%d", i);
+    cache.Put(name, "I'm expired.", now - kTTL, kTTL);  // Expire at t=10.
+  }
+  EXPECT_EQ(8U, cache.size());
+
+  // Add two negative (instantly expired) entriies at t=10.
+  for (int i = 0; i < 2; ++i) {
+    std::string name = base::StringPrintf("negative%d", i);
+    cache.Put(name, "I was never valid.", now, base::TimeDelta::FromSeconds(0));
+  }
+  EXPECT_EQ(10U, cache.size());
+
+  EXPECT_TRUE(ContainsKey(cache.entries_, "valid0"));
+  EXPECT_TRUE(ContainsKey(cache.entries_, "valid1"));
+  EXPECT_TRUE(ContainsKey(cache.entries_, "valid2"));
+  EXPECT_TRUE(ContainsKey(cache.entries_, "valid3"));
+  EXPECT_TRUE(ContainsKey(cache.entries_, "valid4"));
+  EXPECT_TRUE(ContainsKey(cache.entries_, "expired0"));
+  EXPECT_TRUE(ContainsKey(cache.entries_, "expired1"));
+  EXPECT_TRUE(ContainsKey(cache.entries_, "expired2"));
+  EXPECT_TRUE(ContainsKey(cache.entries_, "negative0"));
+  EXPECT_TRUE(ContainsKey(cache.entries_, "negative1"));
+
+  // Shrink the new max constraints bound and compact. The "negative" and
+  // "expired" entries should be dropped.
+  cache.max_entries_ = 6;
+  cache.Compact(now);
+  EXPECT_EQ(5U, cache.size());
+
+  EXPECT_TRUE(ContainsKey(cache.entries_, "valid0"));
+  EXPECT_TRUE(ContainsKey(cache.entries_, "valid1"));
+  EXPECT_TRUE(ContainsKey(cache.entries_, "valid2"));
+  EXPECT_TRUE(ContainsKey(cache.entries_, "valid3"));
+  EXPECT_TRUE(ContainsKey(cache.entries_, "valid4"));
+  EXPECT_FALSE(ContainsKey(cache.entries_, "expired0"));
+  EXPECT_FALSE(ContainsKey(cache.entries_, "expired1"));
+  EXPECT_FALSE(ContainsKey(cache.entries_, "expired2"));
+  EXPECT_FALSE(ContainsKey(cache.entries_, "negative0"));
+  EXPECT_FALSE(ContainsKey(cache.entries_, "negative1"));
+
+  // Shrink further -- this time the compact will start dropping valid entries
+  // to make space.
+  cache.max_entries_ = 4;
+  cache.Compact(now);
+  EXPECT_EQ(3U, cache.size());
+}
+
+// Add entries while the cache is at capacity, causing evictions.
+TEST(ExpiringCacheTest, SetWithCompact) {
+  const base::TimeDelta kTTL = base::TimeDelta::FromSeconds(10);
+
+  Cache cache(3);
+
+  // t=10
+  base::TimeTicks now = base::TimeTicks() + kTTL;
+
+  cache.Put("test1", "test1", now, kTTL);
+  cache.Put("test2", "test2", now, kTTL);
+  cache.Put("expired", "expired", now, base::TimeDelta::FromSeconds(0));
+
+  EXPECT_EQ(3U, cache.size());
+
+  // Should all be retrievable except "expired".
+  EXPECT_THAT(cache.Get("test1", now), Pointee(StrEq("test1")));
+  EXPECT_THAT(cache.Get("test2", now), Pointee(StrEq("test2")));
+  EXPECT_FALSE(cache.Get("expired", now));
+
+  // Adding the fourth entry will cause "expired" to be evicted.
+  cache.Put("test3", "test3", now, kTTL);
+  EXPECT_EQ(3U, cache.size());
+
+  EXPECT_FALSE(cache.Get("expired", now));
+  EXPECT_THAT(cache.Get("test1", now), Pointee(StrEq("test1")));
+  EXPECT_THAT(cache.Get("test2", now), Pointee(StrEq("test2")));
+  EXPECT_THAT(cache.Get("test3", now), Pointee(StrEq("test3")));
+
+  // Add two more entries. Something should be evicted, however "test5"
+  // should definitely be in there (since it was last inserted).
+  cache.Put("test4", "test4", now, kTTL);
+  EXPECT_EQ(3U, cache.size());
+  cache.Put("test5", "test5", now, kTTL);
+  EXPECT_EQ(3U, cache.size());
+  EXPECT_THAT(cache.Get("test5", now), Pointee(StrEq("test5")));
+}
+
+TEST(ExpiringCacheTest, Clear) {
+  const base::TimeDelta kTTL = base::TimeDelta::FromSeconds(10);
+
+  Cache cache(kMaxCacheEntries);
+
+  // Start at t=0.
+  base::TimeTicks now;
+  EXPECT_EQ(0U, cache.size());
+
+  // Add three entries.
+  cache.Put("test1", "foo", now, kTTL);
+  cache.Put("test2", "foo", now, kTTL);
+  cache.Put("test3", "foo", now, kTTL);
+  EXPECT_EQ(3U, cache.size());
+
+  cache.Clear();
+
+  EXPECT_EQ(0U, cache.size());
+}
+
+TEST(ExpiringCache, GetTruncatesExpiredEntries) {
+  const base::TimeDelta kTTL = base::TimeDelta::FromSeconds(10);
+
+  Cache cache(kMaxCacheEntries);
+
+  // Start at t=0.
+  base::TimeTicks now;
+  EXPECT_EQ(0U, cache.size());
+
+  // Add three entries at t=0.
+  cache.Put("test1", "foo1", now, kTTL);
+  cache.Put("test2", "foo2", now, kTTL);
+  cache.Put("test3", "foo3", now, kTTL);
+  EXPECT_EQ(3U, cache.size());
+
+  // Ensure the entries were added.
+  EXPECT_THAT(cache.Get("test1", now), Pointee(StrEq("foo1")));
+  EXPECT_THAT(cache.Get("test2", now), Pointee(StrEq("foo2")));
+  EXPECT_THAT(cache.Get("test3", now), Pointee(StrEq("foo3")));
+
+  // Add five entries at t=10.
+  now += kTTL;
+  for (int i = 0; i < 5; ++i) {
+    std::string name = base::StringPrintf("valid%d", i);
+    cache.Put(name, name, now, kTTL);  // Expire at t=20.
+  }
+  EXPECT_EQ(8U, cache.size());
+
+  // Now access two expired entries and ensure the cache size goes down.
+  EXPECT_FALSE(cache.Get("test1", now));
+  EXPECT_FALSE(cache.Get("test2", now));
+  EXPECT_EQ(6U, cache.size());
+
+  // Accessing non-expired entries should return entries and not adjust the
+  // cache size.
+  for (int i = 0; i < 5; ++i) {
+    std::string name = base::StringPrintf("valid%d", i);
+    EXPECT_THAT(cache.Get(name, now), Pointee(StrEq(name)));
+  }
+  EXPECT_EQ(6U, cache.size());
+}
+
+}  // namespace net
diff --git a/net/net.gyp b/net/net.gyp
index 383fbe9..ef5e249 100644
--- a/net/net.gyp
+++ b/net/net.gyp
@@ -106,6 +106,7 @@
         'base/escape.cc',
         'base/escape.h',
         'base/escape_icu.cc',
+        'base/expiring_cache.h',
         'base/ev_root_ca_metadata.cc',
         'base/ev_root_ca_metadata.h',
         'base/file_stream.cc',
@@ -1024,6 +1025,7 @@
         'base/dns_util_unittest.cc',
         'base/dnsrr_resolver_unittest.cc',
         'base/escape_unittest.cc',
+        'base/expiring_cache_unittest.cc',
         'base/file_stream_unittest.cc',
         'base/filter_unittest.cc',
         'base/gzip_filter_unittest.cc',