base/containers/mru_cache_unittest.cc

   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 }