Remove //net (except for Android test stuff) and sdch

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_
-
-#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_