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/containers/mru_cache.h"
6
7 #include <cstddef>
8 #include <memory>
9
10 #include "base/memory/ptr_util.h"
11 #include "base/trace_event/memory_usage_estimator.h"
12 #include "testing/gtest/include/gtest/gtest.h"
13
14 namespace base {
15
16 namespace {
17
18 int cached_item_live_count = 0;
19
20 struct CachedItem {
CachedItembase::__anona0a6db340111::CachedItem21 CachedItem() : value(0) {
22 cached_item_live_count++;
23 }
24
CachedItembase::__anona0a6db340111::CachedItem25 explicit CachedItem(int new_value) : value(new_value) {
26 cached_item_live_count++;
27 }
28
CachedItembase::__anona0a6db340111::CachedItem29 explicit CachedItem(const CachedItem& other) : value(other.value) {
30 cached_item_live_count++;
31 }
32
~CachedItembase::__anona0a6db340111::CachedItem33 ~CachedItem() {
34 cached_item_live_count--;
35 }
36
37 int value;
38 };
39
40 } // namespace
41
TEST(MRUCacheTest,Basic)42 TEST(MRUCacheTest, Basic) {
43 typedef base::MRUCache<int, CachedItem> Cache;
44 Cache cache(Cache::NO_AUTO_EVICT);
45
46 // Check failure conditions
47 {
48 CachedItem test_item;
49 EXPECT_TRUE(cache.Get(0) == cache.end());
50 EXPECT_TRUE(cache.Peek(0) == cache.end());
51 }
52
53 static const int kItem1Key = 5;
54 CachedItem item1(10);
55 Cache::iterator inserted_item = cache.Put(kItem1Key, item1);
56 EXPECT_EQ(1U, cache.size());
57
58 // Check that item1 was properly inserted.
59 {
60 Cache::iterator found = cache.Get(kItem1Key);
61 EXPECT_TRUE(inserted_item == cache.begin());
62 EXPECT_TRUE(found != cache.end());
63
64 found = cache.Peek(kItem1Key);
65 EXPECT_TRUE(found != cache.end());
66
67 EXPECT_EQ(kItem1Key, found->first);
68 EXPECT_EQ(item1.value, found->second.value);
69 }
70
71 static const int kItem2Key = 7;
72 CachedItem item2(12);
73 cache.Put(kItem2Key, item2);
74 EXPECT_EQ(2U, cache.size());
75
76 // Check that item1 is the oldest since item2 was added afterwards.
77 {
78 Cache::reverse_iterator oldest = cache.rbegin();
79 ASSERT_TRUE(oldest != cache.rend());
80 EXPECT_EQ(kItem1Key, oldest->first);
81 EXPECT_EQ(item1.value, oldest->second.value);
82 }
83
84 // Check that item1 is still accessible by key.
85 {
86 Cache::iterator test_item = cache.Get(kItem1Key);
87 ASSERT_TRUE(test_item != cache.end());
88 EXPECT_EQ(kItem1Key, test_item->first);
89 EXPECT_EQ(item1.value, test_item->second.value);
90 }
91
92 // Check that retrieving item1 pushed item2 to oldest.
93 {
94 Cache::reverse_iterator oldest = cache.rbegin();
95 ASSERT_TRUE(oldest != cache.rend());
96 EXPECT_EQ(kItem2Key, oldest->first);
97 EXPECT_EQ(item2.value, oldest->second.value);
98 }
99
100 // Remove the oldest item and check that item1 is now the only member.
101 {
102 Cache::reverse_iterator next = cache.Erase(cache.rbegin());
103
104 EXPECT_EQ(1U, cache.size());
105
106 EXPECT_TRUE(next == cache.rbegin());
107 EXPECT_EQ(kItem1Key, next->first);
108 EXPECT_EQ(item1.value, next->second.value);
109
110 cache.Erase(cache.begin());
111 EXPECT_EQ(0U, cache.size());
112 }
113
114 // Check that Clear() works properly.
115 cache.Put(kItem1Key, item1);
116 cache.Put(kItem2Key, item2);
117 EXPECT_EQ(2U, cache.size());
118 cache.Clear();
119 EXPECT_EQ(0U, cache.size());
120 }
121
TEST(MRUCacheTest,GetVsPeek)122 TEST(MRUCacheTest, GetVsPeek) {
123 typedef base::MRUCache<int, CachedItem> Cache;
124 Cache cache(Cache::NO_AUTO_EVICT);
125
126 static const int kItem1Key = 1;
127 CachedItem item1(10);
128 cache.Put(kItem1Key, item1);
129
130 static const int kItem2Key = 2;
131 CachedItem item2(20);
132 cache.Put(kItem2Key, item2);
133
134 // This should do nothing since the size is bigger than the number of items.
135 cache.ShrinkToSize(100);
136
137 // Check that item1 starts out as oldest
138 {
139 Cache::reverse_iterator iter = cache.rbegin();
140 ASSERT_TRUE(iter != cache.rend());
141 EXPECT_EQ(kItem1Key, iter->first);
142 EXPECT_EQ(item1.value, iter->second.value);
143 }
144
145 // Check that Peek doesn't change ordering
146 {
147 Cache::iterator peekiter = cache.Peek(kItem1Key);
148 ASSERT_TRUE(peekiter != cache.end());
149
150 Cache::reverse_iterator iter = cache.rbegin();
151 ASSERT_TRUE(iter != cache.rend());
152 EXPECT_EQ(kItem1Key, iter->first);
153 EXPECT_EQ(item1.value, iter->second.value);
154 }
155 }
156
TEST(MRUCacheTest,KeyReplacement)157 TEST(MRUCacheTest, KeyReplacement) {
158 typedef base::MRUCache<int, CachedItem> Cache;
159 Cache cache(Cache::NO_AUTO_EVICT);
160
161 static const int kItem1Key = 1;
162 CachedItem item1(10);
163 cache.Put(kItem1Key, item1);
164
165 static const int kItem2Key = 2;
166 CachedItem item2(20);
167 cache.Put(kItem2Key, item2);
168
169 static const int kItem3Key = 3;
170 CachedItem item3(30);
171 cache.Put(kItem3Key, item3);
172
173 static const int kItem4Key = 4;
174 CachedItem item4(40);
175 cache.Put(kItem4Key, item4);
176
177 CachedItem item5(50);
178 cache.Put(kItem3Key, item5);
179
180 EXPECT_EQ(4U, cache.size());
181 for (int i = 0; i < 3; ++i) {
182 Cache::reverse_iterator iter = cache.rbegin();
183 ASSERT_TRUE(iter != cache.rend());
184 }
185
186 // Make it so only the most important element is there.
187 cache.ShrinkToSize(1);
188
189 Cache::iterator iter = cache.begin();
190 EXPECT_EQ(kItem3Key, iter->first);
191 EXPECT_EQ(item5.value, iter->second.value);
192 }
193
194 // Make sure that the owning version release its pointers properly.
TEST(MRUCacheTest,Owning)195 TEST(MRUCacheTest, Owning) {
196 using Cache = base::MRUCache<int, std::unique_ptr<CachedItem>>;
197 Cache cache(Cache::NO_AUTO_EVICT);
198
199 int initial_count = cached_item_live_count;
200
201 // First insert and item and then overwrite it.
202 static const int kItem1Key = 1;
203 cache.Put(kItem1Key, WrapUnique(new CachedItem(20)));
204 cache.Put(kItem1Key, WrapUnique(new CachedItem(22)));
205
206 // There should still be one item, and one extra live item.
207 Cache::iterator iter = cache.Get(kItem1Key);
208 EXPECT_EQ(1U, cache.size());
209 EXPECT_TRUE(iter != cache.end());
210 EXPECT_EQ(initial_count + 1, cached_item_live_count);
211
212 // Now remove it.
213 cache.Erase(cache.begin());
214 EXPECT_EQ(initial_count, cached_item_live_count);
215
216 // Now try another cache that goes out of scope to make sure its pointers
217 // go away.
218 {
219 Cache cache2(Cache::NO_AUTO_EVICT);
220 cache2.Put(1, WrapUnique(new CachedItem(20)));
221 cache2.Put(2, WrapUnique(new CachedItem(20)));
222 }
223
224 // There should be no objects leaked.
225 EXPECT_EQ(initial_count, cached_item_live_count);
226
227 // Check that Clear() also frees things correctly.
228 {
229 Cache cache2(Cache::NO_AUTO_EVICT);
230 cache2.Put(1, WrapUnique(new CachedItem(20)));
231 cache2.Put(2, WrapUnique(new CachedItem(20)));
232 EXPECT_EQ(initial_count + 2, cached_item_live_count);
233 cache2.Clear();
234 EXPECT_EQ(initial_count, cached_item_live_count);
235 }
236 }
237
TEST(MRUCacheTest,AutoEvict)238 TEST(MRUCacheTest, AutoEvict) {
239 using Cache = base::MRUCache<int, std::unique_ptr<CachedItem>>;
240 static const Cache::size_type kMaxSize = 3;
241
242 int initial_count = cached_item_live_count;
243
244 {
245 Cache cache(kMaxSize);
246
247 static const int kItem1Key = 1, kItem2Key = 2, kItem3Key = 3, kItem4Key = 4;
248 cache.Put(kItem1Key, std::make_unique<CachedItem>(20));
249 cache.Put(kItem2Key, std::make_unique<CachedItem>(21));
250 cache.Put(kItem3Key, std::make_unique<CachedItem>(22));
251 cache.Put(kItem4Key, std::make_unique<CachedItem>(23));
252
253 // The cache should only have kMaxSize items in it even though we inserted
254 // more.
255 EXPECT_EQ(kMaxSize, cache.size());
256 }
257
258 // There should be no objects leaked.
259 EXPECT_EQ(initial_count, cached_item_live_count);
260 }
261
TEST(MRUCacheTest,HashingMRUCache)262 TEST(MRUCacheTest, HashingMRUCache) {
263 // Very simple test to make sure that the hashing cache works correctly.
264 typedef base::HashingMRUCache<std::string, CachedItem> Cache;
265 Cache cache(Cache::NO_AUTO_EVICT);
266
267 CachedItem one(1);
268 cache.Put("First", one);
269
270 CachedItem two(2);
271 cache.Put("Second", two);
272
273 EXPECT_EQ(one.value, cache.Get("First")->second.value);
274 EXPECT_EQ(two.value, cache.Get("Second")->second.value);
275 cache.ShrinkToSize(1);
276 EXPECT_EQ(two.value, cache.Get("Second")->second.value);
277 EXPECT_TRUE(cache.Get("First") == cache.end());
278 }
279
TEST(MRUCacheTest,Swap)280 TEST(MRUCacheTest, Swap) {
281 typedef base::MRUCache<int, CachedItem> Cache;
282 Cache cache1(Cache::NO_AUTO_EVICT);
283
284 // Insert two items into cache1.
285 static const int kItem1Key = 1;
286 CachedItem item1(2);
287 Cache::iterator inserted_item = cache1.Put(kItem1Key, item1);
288 EXPECT_EQ(1U, cache1.size());
289
290 static const int kItem2Key = 3;
291 CachedItem item2(4);
292 cache1.Put(kItem2Key, item2);
293 EXPECT_EQ(2U, cache1.size());
294
295 // Verify cache1's elements.
296 {
297 Cache::iterator iter = cache1.begin();
298 ASSERT_TRUE(iter != cache1.end());
299 EXPECT_EQ(kItem2Key, iter->first);
300 EXPECT_EQ(item2.value, iter->second.value);
301
302 ++iter;
303 ASSERT_TRUE(iter != cache1.end());
304 EXPECT_EQ(kItem1Key, iter->first);
305 EXPECT_EQ(item1.value, iter->second.value);
306 }
307
308 // Create another cache2.
309 Cache cache2(Cache::NO_AUTO_EVICT);
310
311 // Insert three items into cache2.
312 static const int kItem3Key = 5;
313 CachedItem item3(6);
314 inserted_item = cache2.Put(kItem3Key, item3);
315 EXPECT_EQ(1U, cache2.size());
316
317 static const int kItem4Key = 7;
318 CachedItem item4(8);
319 cache2.Put(kItem4Key, item4);
320 EXPECT_EQ(2U, cache2.size());
321
322 static const int kItem5Key = 9;
323 CachedItem item5(10);
324 cache2.Put(kItem5Key, item5);
325 EXPECT_EQ(3U, cache2.size());
326
327 // Verify cache2's elements.
328 {
329 Cache::iterator iter = cache2.begin();
330 ASSERT_TRUE(iter != cache2.end());
331 EXPECT_EQ(kItem5Key, iter->first);
332 EXPECT_EQ(item5.value, iter->second.value);
333
334 ++iter;
335 ASSERT_TRUE(iter != cache2.end());
336 EXPECT_EQ(kItem4Key, iter->first);
337 EXPECT_EQ(item4.value, iter->second.value);
338
339 ++iter;
340 ASSERT_TRUE(iter != cache2.end());
341 EXPECT_EQ(kItem3Key, iter->first);
342 EXPECT_EQ(item3.value, iter->second.value);
343 }
344
345 // Swap cache1 and cache2 and verify cache2 has cache1's elements and cache1
346 // has cache2's elements.
347 cache2.Swap(cache1);
348
349 EXPECT_EQ(3U, cache1.size());
350 EXPECT_EQ(2U, cache2.size());
351
352 // Verify cache1's elements.
353 {
354 Cache::iterator iter = cache1.begin();
355 ASSERT_TRUE(iter != cache1.end());
356 EXPECT_EQ(kItem5Key, iter->first);
357 EXPECT_EQ(item5.value, iter->second.value);
358
359 ++iter;
360 ASSERT_TRUE(iter != cache1.end());
361 EXPECT_EQ(kItem4Key, iter->first);
362 EXPECT_EQ(item4.value, iter->second.value);
363
364 ++iter;
365 ASSERT_TRUE(iter != cache1.end());
366 EXPECT_EQ(kItem3Key, iter->first);
367 EXPECT_EQ(item3.value, iter->second.value);
368 }
369
370 // Verify cache2's elements.
371 {
372 Cache::iterator iter = cache2.begin();
373 ASSERT_TRUE(iter != cache2.end());
374 EXPECT_EQ(kItem2Key, iter->first);
375 EXPECT_EQ(item2.value, iter->second.value);
376
377 ++iter;
378 ASSERT_TRUE(iter != cache2.end());
379 EXPECT_EQ(kItem1Key, iter->first);
380 EXPECT_EQ(item1.value, iter->second.value);
381 }
382 }
383
TEST(MRUCacheTest,EstimateMemory)384 TEST(MRUCacheTest, EstimateMemory) {
385 base::MRUCache<std::string, int> cache(10);
386
387 const std::string key(100u, 'a');
388 cache.Put(key, 1);
389
390 EXPECT_GT(trace_event::EstimateMemoryUsage(cache),
391 trace_event::EstimateMemoryUsage(key));
392 }
393
394 } // namespace base
395