Consider the verification time as well as the expiration time when caching certificate verification…

net/base/expiring_cache.h

 // 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 <functional>
 #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>
+//  ExpirationType must be CopyConstructible and Assignable.
+//  ExpirationCompare is a function class that takes two arguments of the

[cbentzel, 2012/06/18 19:08:28]

This is interesting - given the name of the template argument and the use of
less<> as the default implementation, it looks a lot like a comparator. However,
it is not. Thanks for the detailed comment to clarify this. 

+//    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|.
+template <typename KeyType, typename ValueType,
+          typename ExpirationType = base::TimeTicks,

[wtc, 2012/06/18 22:10:38]

Nit: Ideally this type parameter should be named ExpirationTimeType.
I think it'd be better to abbreviate it as TimeType.
I find ExpirationType a little confusing.

[Ryan Sleevi, 2012/06/19 00:59:28]

Now at least, by virtue of taking ExpirationType + comparison function, there is
no requirement that these be Time based. 

+          typename ExpirationCompare = std::less<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, base::TimeTicks> Entry;
+  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 base::TimeTicks& expiration() const { return it_->second.second; }
+    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) {}
+  // Constructs an ExpiringCache that stores up to |max_entries|, using
+  // |expiration_comp| to check if elements are expired.
+  explicit ExpiringCache(

[cbentzel, 2012/06/18 19:08:28]

You provided good justification for this, but it may be worth getting some
feedback from other more style-conscious folks than myself about whether this is
acceptable. Personally, I'd just choose the two constructor route here as it
does not seem overly onerous to either the writer or reader. If this eventually
leads to a combinatorial explosion of constructors due to multiple default
cases, could reevaluate.

[Ryan Sleevi, 2012/06/19 00:59:28]

Checking the internal style list that led to the Google C++ style guide, the
response from csilvers was

"In general, the same arguments against default arguments for functions applies
to templates as well <snip of justification>. That said, if your template is
STL-like, you can choose to use STL coding conventions for the class itself.
This would have several templates with default arguments, which might include
such things as a hash function, an allocator, etc."

However, while searching the discussions, a reasonable point was raised in that
using Functor objects is preferable over Pointer types, in that it's friendlier
to the inlining phase of the compiler optimizations. Storing a function pointer
is less likely to lead to inlining.

As such, I removed the second constructor (which was needed to handle function
pointer passing), and just let the object instantiate a default functor.

+      size_t max_entries,
+      const ExpirationCompare& expiration_comp = ExpirationCompare())
+      : max_entries_(max_entries),
+        expiration_comp_(expiration_comp) {
+  }
+
   ~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) {
+  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 (!CanUseEntry(it->second, now)) {
+    if (!expiration_comp_(now, it->second.second)) {
       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;
+           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.
@@ skipping 11 matching lines @@
   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) {
+  void Compact(const ExpirationType& now) {
     // Clear out expired entries.
     typename EntryMap::iterator it;
     for (it = entries_.begin(); it != entries_.end(); ) {
-      if (!CanUseEntry(it->second, now)) {
+      if (!expiration_comp_(now, it->second.second)) {
         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_;
+  const ExpirationCompare expiration_comp_;
 
   DISALLOW_COPY_AND_ASSIGN(ExpiringCache);
 };
 
 }  // namespace net
 
 #endif  // NET_BASE_EXPIRING_CACHE_H_