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
9namespace {
10
11int cached_item_live_count = 0;
12
13struct 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
35TEST(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
115TEST(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
150TEST(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.
188TEST(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
231TEST(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
255TEST(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