summaryrefslogtreecommitdiffstats
path: root/base
diff options
context:
space:
mode:
authoragayev@chromium.org <agayev@chromium.org@0039d316-1c4b-4281-b951-d872f2087c98>2011-04-27 18:37:03 +0000
committeragayev@chromium.org <agayev@chromium.org@0039d316-1c4b-4281-b951-d872f2087c98>2011-04-27 18:37:03 +0000
commitb4ae444bfcf965b735181d9a9198eec26773f2fa (patch)
tree2603be60f19659b8f68dce72ddde08dd4fda0caf /base
parente5d35a6d5fa430bb4e70c08ff13b9b13bf3fd2c7 (diff)
downloadchromium_src-b4ae444bfcf965b735181d9a9198eec26773f2fa.zip
chromium_src-b4ae444bfcf965b735181d9a9198eec26773f2fa.tar.gz
chromium_src-b4ae444bfcf965b735181d9a9198eec26773f2fa.tar.bz2
Moved mru_cache from content/common to base/memory.
BUG=None TEST=None Review URL: http://codereview.chromium.org/6883187 git-svn-id: svn://svn.chromium.org/chrome/trunk/src@83182 0039d316-1c4b-4281-b951-d872f2087c98
Diffstat (limited to 'base')
-rw-r--r--base/base.gyp8
-rw-r--r--base/base.gypi1
-rw-r--r--base/memory/mru_cache.h263
-rw-r--r--base/memory/mru_cache_unittest.cc253
4 files changed, 525 insertions, 0 deletions
diff --git a/base/base.gyp b/base/base.gyp
index d103b45..868e20e 100644
--- a/base/base.gyp
+++ b/base/base.gyp
@@ -139,6 +139,7 @@
'mac/objc_property_releaser_unittest.mm',
'md5_unittest.cc',
'memory/linked_ptr_unittest.cc',
+ 'memory/mru_cache_unittest.cc',
'memory/ref_counted_unittest.cc',
'memory/scoped_native_library_unittest.cc',
'memory/scoped_ptr_unittest.cc',
@@ -242,6 +243,13 @@
],
},
],
+ ['gcc_version==44', {
+ # Avoid gcc 4.4 strict aliasing issues in stl_tree.h when
+ # building mru_cache_unittest.cc.
+ 'cflags': [
+ '-fno-strict-aliasing',
+ ],
+ }],
],
'dependencies': [
'../build/linux/system.gyp:gtk',
diff --git a/base/base.gypi b/base/base.gypi
index 77678eb..fa88b3e 100644
--- a/base/base.gypi
+++ b/base/base.gypi
@@ -131,6 +131,7 @@
'memory/linked_ptr.h',
'memory/memory_debug.cc',
'memory/memory_debug.h',
+ 'memory/mru_cache.h',
'memory/raw_scoped_refptr_mismatch_checker.h',
'memory/ref_counted.cc',
'memory/ref_counted.h',
diff --git a/base/memory/mru_cache.h b/base/memory/mru_cache.h
new file mode 100644
index 0000000..132b324
--- /dev/null
+++ b/base/memory/mru_cache.h
@@ -0,0 +1,263 @@
+// 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_
+#pragma once
+
+#include <list>
+#include <map>
+#include <utility>
+
+#include "base/basictypes.h"
+#include "base/logging.h"
+
+namespace base {
+
+// MRUCacheBase ----------------------------------------------------------------
+
+// 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>
+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 std::map<KeyType, typename PayloadList::iterator> 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_[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 { 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 { 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);
+};
+
+} // namespace base
+
+#endif // BASE_MEMORY_MRU_CACHE_H_
diff --git a/base/memory/mru_cache_unittest.cc b/base/memory/mru_cache_unittest.cc
new file mode 100644
index 0000000..89ca2fa
--- /dev/null
+++ b/base/memory/mru_cache_unittest.cc
@@ -0,0 +1,253 @@
+// 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);
+}