1 files changed, 218 insertions, 0 deletions
diff --git a/chromium/net/base/expiring_cache.h b/chromium/net/base/expiring_cache.h
new file mode 100644
index 00000000000..3fbde6594ff
--- /dev/null
+++ b/chromium/net/base/expiring_cache.h
@@ -0,0 +1,218 @@
+// 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_
+
+#include <map>
+#include <utility>
+
+#include "base/basictypes.h"
+#include "base/gtest_prod_util.h"
+#include "base/time/time.h"
+
+namespace net {
+
+template <typename KeyType,
+          typename ValueType,
+          typename ExpirationType>
+class NoopEvictionHandler {
+ public:
+  void Handle(const KeyType& key,
+              const ValueType& value,
+              const ExpirationType& expiration,
+              const ExpirationType& now,
+              bool onGet) const {
+  }
+};
+
+// 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.
+//  ExpirationType must be CopyConstructible and Assignable.
+//  ExpirationCompare is a function class that takes two arguments of the
+//    type ExpirationType and returns a bool. If |comp| is an instance of
+//    ExpirationCompare, then the expression |comp(current, expiration)| shall
+//    return true iff |current| is still valid within |expiration|.
+//
+// A simple use of this class may use base::TimeTicks, which provides a
+// monotonically increasing clock, for the expiration type. Because it's always
+// increasing, std::less<> can be used, which will simply ensure that |now| is
+// sorted before |expiration|:
+//
+//   ExpiringCache<std::string, std::string, base::TimeTicks,
+//                 std::less<base::TimeTicks> > cache(0);
+//   // Add a value that expires in 5 minutes
+//   cache.Put("key1", "value1", base::TimeTicks::Now(),
+//             base::TimeTicks::Now() + base::TimeDelta::FromMinutes(5));
+//   // Add another value that expires in 10 minutes.
+//   cache.Put("key2", "value2", base::TimeTicks::Now(),
+//             base::TimeTicks::Now() + base::TimeDelta::FromMinutes(10));
+//
+// Alternatively, there may be some more complex expiration criteria, at which
+// point a custom functor may be used:
+//
+//   struct ComplexExpirationFunctor {
+//     bool operator()(const ComplexExpiration& now,
+//                     const ComplexExpiration& expiration) const;
+//   };
+//   ExpiringCache<std::string, std::string, ComplexExpiration,
+//                 ComplexExpirationFunctor> cache(15);
+//   // Add a value that expires once the 'sprocket' has 'cog'-ified.
+//   cache.Put("key1", "value1", ComplexExpiration("sprocket"),
+//             ComplexExpiration("cog"));
+template <typename KeyType,
+          typename ValueType,
+          typename ExpirationType,
+          typename ExpirationCompare,
+          typename EvictionHandler = NoopEvictionHandler<KeyType,
+                                                         ValueType,
+                                                         ExpirationType> >
+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, ExpirationType> Entry;
+  typedef std::map<KeyType, Entry> EntryMap;
+
+ public:
+  typedef KeyType key_type;
+  typedef ValueType value_type;
+  typedef ExpirationType expiration_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 ExpirationType& 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, const ExpirationType& now) {
+    typename EntryMap::iterator it = entries_.find(key);
+    if (it == entries_.end())
+      return NULL;
+
+    // Immediately remove expired entries.
+    if (!expiration_comp_(now, it->second.second)) {
+      Evict(it, now, true);
+      return NULL;
+    }
+
+    return &it->second.first;
+  }
+
+  // Updates or replaces the value associated with |key|.
+  void Put(const KeyType& key,
+           const ValueType& value,
+           const ExpirationType& now,
+           const ExpirationType& expiration) {
+    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);
+  FRIEND_TEST_ALL_PREFIXES(ExpiringCacheTest, CustomFunctor);
+
+  // Prunes entries from the cache to bring it below |max_entries()|.
+  void Compact(const ExpirationType& now) {
+    // Clear out expired entries.
+    typename EntryMap::iterator it;
+    for (it = entries_.begin(); it != entries_.end(); ) {
+      if (!expiration_comp_(now, it->second.second)) {
+        Evict(it++, now, false);
+      } 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_;) {
+      Evict(it++, now, false);
+    }
+  }
+
+  void Evict(typename EntryMap::iterator it,
+             const ExpirationType& now,
+             bool on_get) {
+    eviction_handler_.Handle(it->first, it->second.first, it->second.second,
+                             now, on_get);
+    entries_.erase(it);
+  }
+
+  // Bound on total size of the cache.
+  size_t max_entries_;
+
+  EntryMap entries_;
+  ExpirationCompare expiration_comp_;
+  EvictionHandler eviction_handler_;
+
+  DISALLOW_COPY_AND_ASSIGN(ExpiringCache);
+};
+
+}  // namespace net
+
+#endif  // NET_BASE_EXPIRING_CACHE_H_