1 // Copyright (c) 2011 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #include "base/basictypes.h" 6 #include "base/containers/mru_cache.h" 7 #include "testing/gtest/include/gtest/gtest.h" 8 9 namespace { 10 11 int cached_item_live_count = 0; 12 13 struct CachedItem { 14 CachedItem() : value(0) { 15 cached_item_live_count++; 16 } 17 18 explicit CachedItem(int new_value) : value(new_value) { 19 cached_item_live_count++; 20 } 21 22 explicit CachedItem(const CachedItem& other) : value(other.value) { 23 cached_item_live_count++; 24 } 25 26 ~CachedItem() { 27 cached_item_live_count--; 28 } 29 30 int value; 31 }; 32 33 } // namespace 34 35 TEST(MRUCacheTest, Basic) { 36 typedef base::MRUCache<int, CachedItem> Cache; 37 Cache cache(Cache::NO_AUTO_EVICT); 38 39 // Check failure conditions 40 { 41 CachedItem test_item; 42 EXPECT_TRUE(cache.Get(0) == cache.end()); 43 EXPECT_TRUE(cache.Peek(0) == cache.end()); 44 } 45 46 static const int kItem1Key = 5; 47 CachedItem item1(10); 48 Cache::iterator inserted_item = cache.Put(kItem1Key, item1); 49 EXPECT_EQ(1U, cache.size()); 50 51 // Check that item1 was properly inserted. 52 { 53 Cache::iterator found = cache.Get(kItem1Key); 54 EXPECT_TRUE(inserted_item == cache.begin()); 55 EXPECT_TRUE(found != cache.end()); 56 57 found = cache.Peek(kItem1Key); 58 EXPECT_TRUE(found != cache.end()); 59 60 EXPECT_EQ(kItem1Key, found->first); 61 EXPECT_EQ(item1.value, found->second.value); 62 } 63 64 static const int kItem2Key = 7; 65 CachedItem item2(12); 66 cache.Put(kItem2Key, item2); 67 EXPECT_EQ(2U, cache.size()); 68 69 // Check that item1 is the oldest since item2 was added afterwards. 70 { 71 Cache::reverse_iterator oldest = cache.rbegin(); 72 ASSERT_TRUE(oldest != cache.rend()); 73 EXPECT_EQ(kItem1Key, oldest->first); 74 EXPECT_EQ(item1.value, oldest->second.value); 75 } 76 77 // Check that item1 is still accessible by key. 78 { 79 Cache::iterator test_item = cache.Get(kItem1Key); 80 ASSERT_TRUE(test_item != cache.end()); 81 EXPECT_EQ(kItem1Key, test_item->first); 82 EXPECT_EQ(item1.value, test_item->second.value); 83 } 84 85 // Check that retrieving item1 pushed item2 to oldest. 86 { 87 Cache::reverse_iterator oldest = cache.rbegin(); 88 ASSERT_TRUE(oldest != cache.rend()); 89 EXPECT_EQ(kItem2Key, oldest->first); 90 EXPECT_EQ(item2.value, oldest->second.value); 91 } 92 93 // Remove the oldest item and check that item1 is now the only member. 94 { 95 Cache::reverse_iterator next = cache.Erase(cache.rbegin()); 96 97 EXPECT_EQ(1U, cache.size()); 98 99 EXPECT_TRUE(next == cache.rbegin()); 100 EXPECT_EQ(kItem1Key, next->first); 101 EXPECT_EQ(item1.value, next->second.value); 102 103 cache.Erase(cache.begin()); 104 EXPECT_EQ(0U, cache.size()); 105 } 106 107 // Check that Clear() works properly. 108 cache.Put(kItem1Key, item1); 109 cache.Put(kItem2Key, item2); 110 EXPECT_EQ(2U, cache.size()); 111 cache.Clear(); 112 EXPECT_EQ(0U, cache.size()); 113 } 114 115 TEST(MRUCacheTest, GetVsPeek) { 116 typedef base::MRUCache<int, CachedItem> Cache; 117 Cache cache(Cache::NO_AUTO_EVICT); 118 119 static const int kItem1Key = 1; 120 CachedItem item1(10); 121 cache.Put(kItem1Key, item1); 122 123 static const int kItem2Key = 2; 124 CachedItem item2(20); 125 cache.Put(kItem2Key, item2); 126 127 // This should do nothing since the size is bigger than the number of items. 128 cache.ShrinkToSize(100); 129 130 // Check that item1 starts out as oldest 131 { 132 Cache::reverse_iterator iter = cache.rbegin(); 133 ASSERT_TRUE(iter != cache.rend()); 134 EXPECT_EQ(kItem1Key, iter->first); 135 EXPECT_EQ(item1.value, iter->second.value); 136 } 137 138 // Check that Peek doesn't change ordering 139 { 140 Cache::iterator peekiter = cache.Peek(kItem1Key); 141 ASSERT_TRUE(peekiter != cache.end()); 142 143 Cache::reverse_iterator iter = cache.rbegin(); 144 ASSERT_TRUE(iter != cache.rend()); 145 EXPECT_EQ(kItem1Key, iter->first); 146 EXPECT_EQ(item1.value, iter->second.value); 147 } 148 } 149 150 TEST(MRUCacheTest, KeyReplacement) { 151 typedef base::MRUCache<int, CachedItem> Cache; 152 Cache cache(Cache::NO_AUTO_EVICT); 153 154 static const int kItem1Key = 1; 155 CachedItem item1(10); 156 cache.Put(kItem1Key, item1); 157 158 static const int kItem2Key = 2; 159 CachedItem item2(20); 160 cache.Put(kItem2Key, item2); 161 162 static const int kItem3Key = 3; 163 CachedItem item3(30); 164 cache.Put(kItem3Key, item3); 165 166 static const int kItem4Key = 4; 167 CachedItem item4(40); 168 cache.Put(kItem4Key, item4); 169 170 CachedItem item5(50); 171 cache.Put(kItem3Key, item5); 172 173 EXPECT_EQ(4U, cache.size()); 174 for (int i = 0; i < 3; ++i) { 175 Cache::reverse_iterator iter = cache.rbegin(); 176 ASSERT_TRUE(iter != cache.rend()); 177 } 178 179 // Make it so only the most important element is there. 180 cache.ShrinkToSize(1); 181 182 Cache::iterator iter = cache.begin(); 183 EXPECT_EQ(kItem3Key, iter->first); 184 EXPECT_EQ(item5.value, iter->second.value); 185 } 186 187 // Make sure that the owning version release its pointers properly. 188 TEST(MRUCacheTest, Owning) { 189 typedef base::OwningMRUCache<int, CachedItem*> Cache; 190 Cache cache(Cache::NO_AUTO_EVICT); 191 192 int initial_count = cached_item_live_count; 193 194 // First insert and item and then overwrite it. 195 static const int kItem1Key = 1; 196 cache.Put(kItem1Key, new CachedItem(20)); 197 cache.Put(kItem1Key, new CachedItem(22)); 198 199 // There should still be one item, and one extra live item. 200 Cache::iterator iter = cache.Get(kItem1Key); 201 EXPECT_EQ(1U, cache.size()); 202 EXPECT_TRUE(iter != cache.end()); 203 EXPECT_EQ(initial_count + 1, cached_item_live_count); 204 205 // Now remove it. 206 cache.Erase(cache.begin()); 207 EXPECT_EQ(initial_count, cached_item_live_count); 208 209 // Now try another cache that goes out of scope to make sure its pointers 210 // go away. 211 { 212 Cache cache2(Cache::NO_AUTO_EVICT); 213 cache2.Put(1, new CachedItem(20)); 214 cache2.Put(2, new CachedItem(20)); 215 } 216 217 // There should be no objects leaked. 218 EXPECT_EQ(initial_count, cached_item_live_count); 219 220 // Check that Clear() also frees things correctly. 221 { 222 Cache cache2(Cache::NO_AUTO_EVICT); 223 cache2.Put(1, new CachedItem(20)); 224 cache2.Put(2, new CachedItem(20)); 225 EXPECT_EQ(initial_count + 2, cached_item_live_count); 226 cache2.Clear(); 227 EXPECT_EQ(initial_count, cached_item_live_count); 228 } 229 } 230 231 TEST(MRUCacheTest, AutoEvict) { 232 typedef base::OwningMRUCache<int, CachedItem*> Cache; 233 static const Cache::size_type kMaxSize = 3; 234 235 int initial_count = cached_item_live_count; 236 237 { 238 Cache cache(kMaxSize); 239 240 static const int kItem1Key = 1, kItem2Key = 2, kItem3Key = 3, kItem4Key = 4; 241 cache.Put(kItem1Key, new CachedItem(20)); 242 cache.Put(kItem2Key, new CachedItem(21)); 243 cache.Put(kItem3Key, new CachedItem(22)); 244 cache.Put(kItem4Key, new CachedItem(23)); 245 246 // The cache should only have kMaxSize items in it even though we inserted 247 // more. 248 EXPECT_EQ(kMaxSize, cache.size()); 249 } 250 251 // There should be no objects leaked. 252 EXPECT_EQ(initial_count, cached_item_live_count); 253 } 254 255 TEST(MRUCacheTest, HashingMRUCache) { 256 // Very simple test to make sure that the hashing cache works correctly. 257 typedef base::HashingMRUCache<std::string, CachedItem> Cache; 258 Cache cache(Cache::NO_AUTO_EVICT); 259 260 CachedItem one(1); 261 cache.Put("First", one); 262 263 CachedItem two(2); 264 cache.Put("Second", two); 265 266 EXPECT_EQ(one.value, cache.Get("First")->second.value); 267 EXPECT_EQ(two.value, cache.Get("Second")->second.value); 268 cache.ShrinkToSize(1); 269 EXPECT_EQ(two.value, cache.Get("Second")->second.value); 270 EXPECT_TRUE(cache.Get("First") == cache.end()); 271 } 272
