| // 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/containers/mru_cache.h" | |
| #include <cstddef> | |
| #include <memory> | |
| #include "base/memory/ptr_util.h" | |
| #include "base/trace_event/memory_usage_estimator.h" | |
| #include "testing/gtest/include/gtest/gtest.h" | |
| namespace base { | |
| 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) { | |
| using Cache = base::MRUCache<int, std::unique_ptr<CachedItem>>; | |
| 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, WrapUnique(new CachedItem(20))); | |
| cache.Put(kItem1Key, WrapUnique(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, WrapUnique(new CachedItem(20))); | |
| cache2.Put(2, WrapUnique(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, WrapUnique(new CachedItem(20))); | |
| cache2.Put(2, WrapUnique(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) { | |
| using Cache = base::MRUCache<int, std::unique_ptr<CachedItem>>; | |
| 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, std::make_unique<CachedItem>(20)); | |
| cache.Put(kItem2Key, std::make_unique<CachedItem>(21)); | |
| cache.Put(kItem3Key, std::make_unique<CachedItem>(22)); | |
| cache.Put(kItem4Key, std::make_unique<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()); | |
| } | |
| TEST(MRUCacheTest, Swap) { | |
| typedef base::MRUCache<int, CachedItem> Cache; | |
| Cache cache1(Cache::NO_AUTO_EVICT); | |
| // Insert two items into cache1. | |
| static const int kItem1Key = 1; | |
| CachedItem item1(2); | |
| Cache::iterator inserted_item = cache1.Put(kItem1Key, item1); | |
| EXPECT_EQ(1U, cache1.size()); | |
| static const int kItem2Key = 3; | |
| CachedItem item2(4); | |
| cache1.Put(kItem2Key, item2); | |
| EXPECT_EQ(2U, cache1.size()); | |
| // Verify cache1's elements. | |
| { | |
| Cache::iterator iter = cache1.begin(); | |
| ASSERT_TRUE(iter != cache1.end()); | |
| EXPECT_EQ(kItem2Key, iter->first); | |
| EXPECT_EQ(item2.value, iter->second.value); | |
| ++iter; | |
| ASSERT_TRUE(iter != cache1.end()); | |
| EXPECT_EQ(kItem1Key, iter->first); | |
| EXPECT_EQ(item1.value, iter->second.value); | |
| } | |
| // Create another cache2. | |
| Cache cache2(Cache::NO_AUTO_EVICT); | |
| // Insert three items into cache2. | |
| static const int kItem3Key = 5; | |
| CachedItem item3(6); | |
| inserted_item = cache2.Put(kItem3Key, item3); | |
| EXPECT_EQ(1U, cache2.size()); | |
| static const int kItem4Key = 7; | |
| CachedItem item4(8); | |
| cache2.Put(kItem4Key, item4); | |
| EXPECT_EQ(2U, cache2.size()); | |
| static const int kItem5Key = 9; | |
| CachedItem item5(10); | |
| cache2.Put(kItem5Key, item5); | |
| EXPECT_EQ(3U, cache2.size()); | |
| // Verify cache2's elements. | |
| { | |
| Cache::iterator iter = cache2.begin(); | |
| ASSERT_TRUE(iter != cache2.end()); | |
| EXPECT_EQ(kItem5Key, iter->first); | |
| EXPECT_EQ(item5.value, iter->second.value); | |
| ++iter; | |
| ASSERT_TRUE(iter != cache2.end()); | |
| EXPECT_EQ(kItem4Key, iter->first); | |
| EXPECT_EQ(item4.value, iter->second.value); | |
| ++iter; | |
| ASSERT_TRUE(iter != cache2.end()); | |
| EXPECT_EQ(kItem3Key, iter->first); | |
| EXPECT_EQ(item3.value, iter->second.value); | |
| } | |
| // Swap cache1 and cache2 and verify cache2 has cache1's elements and cache1 | |
| // has cache2's elements. | |
| cache2.Swap(cache1); | |
| EXPECT_EQ(3U, cache1.size()); | |
| EXPECT_EQ(2U, cache2.size()); | |
| // Verify cache1's elements. | |
| { | |
| Cache::iterator iter = cache1.begin(); | |
| ASSERT_TRUE(iter != cache1.end()); | |
| EXPECT_EQ(kItem5Key, iter->first); | |
| EXPECT_EQ(item5.value, iter->second.value); | |
| ++iter; | |
| ASSERT_TRUE(iter != cache1.end()); | |
| EXPECT_EQ(kItem4Key, iter->first); | |
| EXPECT_EQ(item4.value, iter->second.value); | |
| ++iter; | |
| ASSERT_TRUE(iter != cache1.end()); | |
| EXPECT_EQ(kItem3Key, iter->first); | |
| EXPECT_EQ(item3.value, iter->second.value); | |
| } | |
| // Verify cache2's elements. | |
| { | |
| Cache::iterator iter = cache2.begin(); | |
| ASSERT_TRUE(iter != cache2.end()); | |
| EXPECT_EQ(kItem2Key, iter->first); | |
| EXPECT_EQ(item2.value, iter->second.value); | |
| ++iter; | |
| ASSERT_TRUE(iter != cache2.end()); | |
| EXPECT_EQ(kItem1Key, iter->first); | |
| EXPECT_EQ(item1.value, iter->second.value); | |
| } | |
| } | |
| TEST(MRUCacheTest, EstimateMemory) { | |
| base::MRUCache<std::string, int> cache(10); | |
| const std::string key(100u, 'a'); | |
| cache.Put(key, 1); | |
| EXPECT_GT(trace_event::EstimateMemoryUsage(cache), | |
| trace_event::EstimateMemoryUsage(key)); | |
| } | |
| } // namespace base |