Move mru_cache to the new containers subdirectory.

Review URL: https://codereview.chromium.org/11361193

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

2 files changed, 0 insertions, 576 deletions

diff --git a/base/memory/mru_cache.h b/base/memory/mru_cache.h
deleted file mode 100644
index 915d2b5..0000000
--- a/base/memory/mru_cache.h
+++ /dev/null
@@ -1,305 +0,0 @@
-// Copyright (c) 2011 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.
-
-// This file contains a template for a Most Recently Used cache that allows
-// constant-time access to items using a key, but easy identification of the
-// least-recently-used items for removal.  Each key can only be associated with
-// one payload item at a time.
-//
-// The key object will be stored twice, so it should support efficient copying.
-//
-// NOTE: While all operations are O(1), this code is written for
-// legibility rather than optimality. If future profiling identifies this as
-// a bottleneck, there is room for smaller values of 1 in the O(1). :]
-
-#ifndef BASE_MEMORY_MRU_CACHE_H_
-#define BASE_MEMORY_MRU_CACHE_H_
-
-#include <list>
-#include <map>
-#include <utility>
-
-#include "base/basictypes.h"
-#include "base/hash_tables.h"
-#include "base/logging.h"
-
-namespace base {
-
-// MRUCacheBase ----------------------------------------------------------------
-
-// This template is used to standardize map type containers that can be used
-// by MRUCacheBase. This level of indirection is necessary because of the way
-// that template template params and default template params interact.
-template <class KeyType, class ValueType>
-struct MRUCacheStandardMap {
-  typedef std::map<KeyType, ValueType> Type;
-};
-
-// Base class for the MRU cache specializations defined below.
-// The deletor will get called on all payloads that are being removed or
-// replaced.
-template <class KeyType, class PayloadType, class DeletorType,
-          template <typename, typename> class MapType = MRUCacheStandardMap>
-class MRUCacheBase {
- public:
-  // The payload of the list. This maintains a copy of the key so we can
-  // efficiently delete things given an element of the list.
-  typedef std::pair<KeyType, PayloadType> value_type;
-
- private:
-  typedef std::list<value_type> PayloadList;
-  typedef typename MapType<KeyType,
-                           typename PayloadList::iterator>::Type KeyIndex;
-
- public:
-  typedef typename PayloadList::size_type size_type;
-
-  typedef typename PayloadList::iterator iterator;
-  typedef typename PayloadList::const_iterator const_iterator;
-  typedef typename PayloadList::reverse_iterator reverse_iterator;
-  typedef typename PayloadList::const_reverse_iterator const_reverse_iterator;
-
-  enum { NO_AUTO_EVICT = 0 };
-
-  // The max_size is the size at which the cache will prune its members to when
-  // a new item is inserted. If the caller wants to manager this itself (for
-  // example, maybe it has special work to do when something is evicted), it
-  // can pass NO_AUTO_EVICT to not restrict the cache size.
-  explicit MRUCacheBase(size_type max_size) : max_size_(max_size) {
-  }
-
-  MRUCacheBase(size_type max_size, const DeletorType& deletor)
-      : max_size_(max_size), deletor_(deletor) {
-  }
-
-  virtual ~MRUCacheBase() {
-    iterator i = begin();
-    while (i != end())
-      i = Erase(i);
-  }
-
-  size_type max_size() const { return max_size_; }
-
-  // Inserts a payload item with the given key. If an existing item has
-  // the same key, it is removed prior to insertion. An iterator indicating the
-  // inserted item will be returned (this will always be the front of the list).
-  //
-  // The payload will be copied. In the case of an OwningMRUCache, this function
-  // will take ownership of the pointer.
-  iterator Put(const KeyType& key, const PayloadType& payload) {
-    // Remove any existing payload with that key.
-    typename KeyIndex::iterator index_iter = index_.find(key);
-    if (index_iter != index_.end()) {
-      // Erase the reference to it. This will call the deletor on the removed
-      // element. The index reference will be replaced in the code below.
-      Erase(index_iter->second);
-    } else if (max_size_ != NO_AUTO_EVICT) {
-      // New item is being inserted which might make it larger than the maximum
-      // size: kick the oldest thing out if necessary.
-      ShrinkToSize(max_size_ - 1);
-    }
-
-    ordering_.push_front(value_type(key, payload));
-    index_.insert(std::make_pair(key, ordering_.begin()));
-    return ordering_.begin();
-  }
-
-  // Retrieves the contents of the given key, or end() if not found. This method
-  // has the side effect of moving the requested item to the front of the
-  // recency list.
-  //
-  // TODO(brettw) We may want a const version of this function in the future.
-  iterator Get(const KeyType& key) {
-    typename KeyIndex::iterator index_iter = index_.find(key);
-    if (index_iter == index_.end())
-      return end();
-    typename PayloadList::iterator iter = index_iter->second;
-
-    // Move the touched item to the front of the recency ordering.
-    ordering_.splice(ordering_.begin(), ordering_, iter);
-    return ordering_.begin();
-  }
-
-  // Retrieves the payload associated with a given key and returns it via
-  // result without affecting the ordering (unlike Get).
-  //
-  // TODO(brettw) We may want a const version of this function in the future.
-  iterator Peek(const KeyType& key) {
-    typename KeyIndex::const_iterator index_iter = index_.find(key);
-    if (index_iter == index_.end())
-      return end();
-    return index_iter->second;
-  }
-
-  // Erases the item referenced by the given iterator. An iterator to the item
-  // following it will be returned. The iterator must be valid.
-  iterator Erase(iterator pos) {
-    deletor_(pos->second);
-    index_.erase(pos->first);
-    return ordering_.erase(pos);
-  }
-
-  // MRUCache entries are often processed in reverse order, so we add this
-  // convenience function (not typically defined by STL containers).
-  reverse_iterator Erase(reverse_iterator pos) {
-    // We have to actually give it the incremented iterator to delete, since
-    // the forward iterator that base() returns is actually one past the item
-    // being iterated over.
-    return reverse_iterator(Erase((++pos).base()));
-  }
-
-  // Shrinks the cache so it only holds |new_size| items. If |new_size| is
-  // bigger or equal to the current number of items, this will do nothing.
-  void ShrinkToSize(size_type new_size) {
-    for (size_type i = size(); i > new_size; i--)
-      Erase(rbegin());
-  }
-
-  // Deletes everything from the cache.
-  void Clear() {
-    for (typename PayloadList::iterator i(ordering_.begin());
-         i != ordering_.end(); ++i)
-      deletor_(i->second);
-    index_.clear();
-    ordering_.clear();
-  }
-
-  // Returns the number of elements in the cache.
-  size_type size() const {
-    // We don't use ordering_.size() for the return value because
-    // (as a linked list) it can be O(n).
-    DCHECK(index_.size() == ordering_.size());
-    return index_.size();
-  }
-
-  // Allows iteration over the list. Forward iteration starts with the most
-  // recent item and works backwards.
-  //
-  // Note that since these iterators are actually iterators over a list, you
-  // can keep them as you insert or delete things (as long as you don't delete
-  // the one you are pointing to) and they will still be valid.
-  iterator begin() { return ordering_.begin(); }
-  const_iterator begin() const { return ordering_.begin(); }
-  iterator end() { return ordering_.end(); }
-  const_iterator end() const { return ordering_.end(); }
-
-  reverse_iterator rbegin() { return ordering_.rbegin(); }
-  const_reverse_iterator rbegin() const { return ordering_.rbegin(); }
-  reverse_iterator rend() { return ordering_.rend(); }
-  const_reverse_iterator rend() const { return ordering_.rend(); }
-
-  bool empty() const { return ordering_.empty(); }
-
- private:
-  PayloadList ordering_;
-  KeyIndex index_;
-
-  size_type max_size_;
-
-  DeletorType deletor_;
-
-  DISALLOW_COPY_AND_ASSIGN(MRUCacheBase);
-};
-
-// MRUCache --------------------------------------------------------------------
-
-// A functor that does nothing. Used by the MRUCache.
-template<class PayloadType>
-class MRUCacheNullDeletor {
- public:
-  void operator()(PayloadType& payload) {
-  }
-};
-
-// A container that does not do anything to free its data. Use this when storing
-// value types (as opposed to pointers) in the list.
-template <class KeyType, class PayloadType>
-class MRUCache : public MRUCacheBase<KeyType,
-                                     PayloadType,
-                                     MRUCacheNullDeletor<PayloadType> > {
- private:
-  typedef MRUCacheBase<KeyType, PayloadType,
-      MRUCacheNullDeletor<PayloadType> > ParentType;
-
- public:
-  // See MRUCacheBase, noting the possibility of using NO_AUTO_EVICT.
-  explicit MRUCache(typename ParentType::size_type max_size)
-      : ParentType(max_size) {
-  }
-  virtual ~MRUCache() {
-  }
-
- private:
-  DISALLOW_COPY_AND_ASSIGN(MRUCache);
-};
-
-// OwningMRUCache --------------------------------------------------------------
-
-template<class PayloadType>
-class MRUCachePointerDeletor {
- public:
-  void operator()(PayloadType& payload) {
-    delete payload;
-  }
-};
-
-// A cache that owns the payload type, which must be a non-const pointer type.
-// The pointers will be deleted when they are removed, replaced, or when the
-// cache is destroyed.
-template <class KeyType, class PayloadType>
-class OwningMRUCache
-    : public MRUCacheBase<KeyType,
-                          PayloadType,
-                          MRUCachePointerDeletor<PayloadType> > {
- private:
-  typedef MRUCacheBase<KeyType, PayloadType,
-      MRUCachePointerDeletor<PayloadType> > ParentType;
-
- public:
-  // See MRUCacheBase, noting the possibility of using NO_AUTO_EVICT.
-  explicit OwningMRUCache(typename ParentType::size_type max_size)
-      : ParentType(max_size) {
-  }
-  virtual ~OwningMRUCache() {
-  }
-
- private:
-  DISALLOW_COPY_AND_ASSIGN(OwningMRUCache);
-};
-
-// HashingMRUCache ------------------------------------------------------------
-
-template <class KeyType, class ValueType>
-struct MRUCacheHashMap {
-  typedef base::hash_map<KeyType, ValueType> Type;
-};
-
-// This class is similar to MRUCache, except that it uses base::hash_map as
-// the map type instead of std::map. Note that your KeyType must be hashable
-// to use this cache.
-template <class KeyType, class PayloadType>
-class HashingMRUCache : public MRUCacheBase<KeyType,
-                                            PayloadType,
-                                            MRUCacheNullDeletor<PayloadType>,
-                                            MRUCacheHashMap> {
- private:
-  typedef MRUCacheBase<KeyType, PayloadType,
-                       MRUCacheNullDeletor<PayloadType>,
-                       MRUCacheHashMap> ParentType;
-
- public:
-  // See MRUCacheBase, noting the possibility of using NO_AUTO_EVICT.
-  explicit HashingMRUCache(typename ParentType::size_type max_size)
-      : ParentType(max_size) {
-  }
-  virtual ~HashingMRUCache() {
-  }
-
- private:
-  DISALLOW_COPY_AND_ASSIGN(HashingMRUCache);
-};
-
-}  // namespace base
-
-#endif  // BASE_MEMORY_MRU_CACHE_H_
diff --git a/base/memory/mru_cache_unittest.cc b/base/memory/mru_cache_unittest.cc
deleted file mode 100644
index 1fe9ce2..0000000
--- a/base/memory/mru_cache_unittest.cc
+++ /dev/null
@@ -1,271 +0,0 @@
-// Copyright (c) 2011 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 "base/basictypes.h"
-#include "base/memory/mru_cache.h"
-#include "testing/gtest/include/gtest/gtest.h"
-
-namespace {
-
-int cached_item_live_count = 0;
-
-struct CachedItem {
-  CachedItem() : value(0) {
-    cached_item_live_count++;
-  }
-
-  explicit CachedItem(int new_value) : value(new_value) {
-    cached_item_live_count++;
-  }
-
-  explicit CachedItem(const CachedItem& other) : value(other.value) {
-    cached_item_live_count++;
-  }
-
-  ~CachedItem() {
-    cached_item_live_count--;
-  }
-
-  int value;
-};
-
-}  // namespace
-
-TEST(MRUCacheTest, Basic) {
-  typedef base::MRUCache<int, CachedItem> Cache;
-  Cache cache(Cache::NO_AUTO_EVICT);
-
-  // Check failure conditions
-  {
-    CachedItem test_item;
-    EXPECT_TRUE(cache.Get(0) == cache.end());
-    EXPECT_TRUE(cache.Peek(0) == cache.end());
-  }
-
-  static const int kItem1Key = 5;
-  CachedItem item1(10);
-  Cache::iterator inserted_item = cache.Put(kItem1Key, item1);
-  EXPECT_EQ(1U, cache.size());
-
-  // Check that item1 was properly inserted.
-  {
-    Cache::iterator found = cache.Get(kItem1Key);
-    EXPECT_TRUE(inserted_item == cache.begin());
-    EXPECT_TRUE(found != cache.end());
-
-    found = cache.Peek(kItem1Key);
-    EXPECT_TRUE(found != cache.end());
-
-    EXPECT_EQ(kItem1Key, found->first);
-    EXPECT_EQ(item1.value, found->second.value);
-  }
-
-  static const int kItem2Key = 7;
-  CachedItem item2(12);
-  cache.Put(kItem2Key, item2);
-  EXPECT_EQ(2U, cache.size());
-
-  // Check that item1 is the oldest since item2 was added afterwards.
-  {
-    Cache::reverse_iterator oldest = cache.rbegin();
-    ASSERT_TRUE(oldest != cache.rend());
-    EXPECT_EQ(kItem1Key, oldest->first);
-    EXPECT_EQ(item1.value, oldest->second.value);
-  }
-
-  // Check that item1 is still accessible by key.
-  {
-    Cache::iterator test_item = cache.Get(kItem1Key);
-    ASSERT_TRUE(test_item != cache.end());
-    EXPECT_EQ(kItem1Key, test_item->first);
-    EXPECT_EQ(item1.value, test_item->second.value);
-  }
-
-  // Check that retrieving item1 pushed item2 to oldest.
-  {
-    Cache::reverse_iterator oldest = cache.rbegin();
-    ASSERT_TRUE(oldest != cache.rend());
-    EXPECT_EQ(kItem2Key, oldest->first);
-    EXPECT_EQ(item2.value, oldest->second.value);
-  }
-
-  // Remove the oldest item and check that item1 is now the only member.
-  {
-    Cache::reverse_iterator next = cache.Erase(cache.rbegin());
-
-    EXPECT_EQ(1U, cache.size());
-
-    EXPECT_TRUE(next == cache.rbegin());
-    EXPECT_EQ(kItem1Key, next->first);
-    EXPECT_EQ(item1.value, next->second.value);
-
-    cache.Erase(cache.begin());
-    EXPECT_EQ(0U, cache.size());
-  }
-
-  // Check that Clear() works properly.
-  cache.Put(kItem1Key, item1);
-  cache.Put(kItem2Key, item2);
-  EXPECT_EQ(2U, cache.size());
-  cache.Clear();
-  EXPECT_EQ(0U, cache.size());
-}
-
-TEST(MRUCacheTest, GetVsPeek) {
-  typedef base::MRUCache<int, CachedItem> Cache;
-  Cache cache(Cache::NO_AUTO_EVICT);
-
-  static const int kItem1Key = 1;
-  CachedItem item1(10);
-  cache.Put(kItem1Key, item1);
-
-  static const int kItem2Key = 2;
-  CachedItem item2(20);
-  cache.Put(kItem2Key, item2);
-
-  // This should do nothing since the size is bigger than the number of items.
-  cache.ShrinkToSize(100);
-
-  // Check that item1 starts out as oldest
-  {
-    Cache::reverse_iterator iter = cache.rbegin();
-    ASSERT_TRUE(iter != cache.rend());
-    EXPECT_EQ(kItem1Key, iter->first);
-    EXPECT_EQ(item1.value, iter->second.value);
-  }
-
-  // Check that Peek doesn't change ordering
-  {
-    Cache::iterator peekiter = cache.Peek(kItem1Key);
-    ASSERT_TRUE(peekiter != cache.end());
-
-    Cache::reverse_iterator iter = cache.rbegin();
-    ASSERT_TRUE(iter != cache.rend());
-    EXPECT_EQ(kItem1Key, iter->first);
-    EXPECT_EQ(item1.value, iter->second.value);
-  }
-}
-
-TEST(MRUCacheTest, KeyReplacement) {
-  typedef base::MRUCache<int, CachedItem> Cache;
-  Cache cache(Cache::NO_AUTO_EVICT);
-
-  static const int kItem1Key = 1;
-  CachedItem item1(10);
-  cache.Put(kItem1Key, item1);
-
-  static const int kItem2Key = 2;
-  CachedItem item2(20);
-  cache.Put(kItem2Key, item2);
-
-  static const int kItem3Key = 3;
-  CachedItem item3(30);
-  cache.Put(kItem3Key, item3);
-
-  static const int kItem4Key = 4;
-  CachedItem item4(40);
-  cache.Put(kItem4Key, item4);
-
-  CachedItem item5(50);
-  cache.Put(kItem3Key, item5);
-
-  EXPECT_EQ(4U, cache.size());
-  for (int i = 0; i < 3; ++i) {
-    Cache::reverse_iterator iter = cache.rbegin();
-    ASSERT_TRUE(iter != cache.rend());
-  }
-
-  // Make it so only the most important element is there.
-  cache.ShrinkToSize(1);
-
-  Cache::iterator iter = cache.begin();
-  EXPECT_EQ(kItem3Key, iter->first);
-  EXPECT_EQ(item5.value, iter->second.value);
-}
-
-// Make sure that the owning version release its pointers properly.
-TEST(MRUCacheTest, Owning) {
-  typedef base::OwningMRUCache<int, CachedItem*> Cache;
-  Cache cache(Cache::NO_AUTO_EVICT);
-
-  int initial_count = cached_item_live_count;
-
-  // First insert and item and then overwrite it.
-  static const int kItem1Key = 1;
-  cache.Put(kItem1Key, new CachedItem(20));
-  cache.Put(kItem1Key, new CachedItem(22));
-
-  // There should still be one item, and one extra live item.
-  Cache::iterator iter = cache.Get(kItem1Key);
-  EXPECT_EQ(1U, cache.size());
-  EXPECT_TRUE(iter != cache.end());
-  EXPECT_EQ(initial_count + 1, cached_item_live_count);
-
-  // Now remove it.
-  cache.Erase(cache.begin());
-  EXPECT_EQ(initial_count, cached_item_live_count);
-
-  // Now try another cache that goes out of scope to make sure its pointers
-  // go away.
-  {
-    Cache cache2(Cache::NO_AUTO_EVICT);
-    cache2.Put(1, new CachedItem(20));
-    cache2.Put(2, new CachedItem(20));
-  }
-
-  // There should be no objects leaked.
-  EXPECT_EQ(initial_count, cached_item_live_count);
-
-  // Check that Clear() also frees things correctly.
-  {
-    Cache cache2(Cache::NO_AUTO_EVICT);
-    cache2.Put(1, new CachedItem(20));
-    cache2.Put(2, new CachedItem(20));
-    EXPECT_EQ(initial_count + 2, cached_item_live_count);
-    cache2.Clear();
-    EXPECT_EQ(initial_count, cached_item_live_count);
-  }
-}
-
-TEST(MRUCacheTest, AutoEvict) {
-  typedef base::OwningMRUCache<int, CachedItem*> Cache;
-  static const Cache::size_type kMaxSize = 3;
-
-  int initial_count = cached_item_live_count;
-
-  {
-    Cache cache(kMaxSize);
-
-    static const int kItem1Key = 1, kItem2Key = 2, kItem3Key = 3, kItem4Key = 4;
-    cache.Put(kItem1Key, new CachedItem(20));
-    cache.Put(kItem2Key, new CachedItem(21));
-    cache.Put(kItem3Key, new CachedItem(22));
-    cache.Put(kItem4Key, new CachedItem(23));
-
-    // The cache should only have kMaxSize items in it even though we inserted
-    // more.
-    EXPECT_EQ(kMaxSize, cache.size());
-  }
-
-  // There should be no objects leaked.
-  EXPECT_EQ(initial_count, cached_item_live_count);
-}
-
-TEST(MRUCacheTest, HashingMRUCache) {
-  // Very simple test to make sure that the hashing cache works correctly.
-  typedef base::HashingMRUCache<std::string, CachedItem> Cache;
-  Cache cache(Cache::NO_AUTO_EVICT);
-
-  CachedItem one(1);
-  cache.Put("First", one);
-
-  CachedItem two(2);
-  cache.Put("Second", two);
-
-  EXPECT_EQ(one.value, cache.Get("First")->second.value);
-  EXPECT_EQ(two.value, cache.Get("Second")->second.value);
-  cache.ShrinkToSize(1);
-  EXPECT_EQ(two.value, cache.Get("Second")->second.value);
-  EXPECT_TRUE(cache.Get("First") == cache.end());
-}