1 // Copyright 2014 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 <algorithm> 6 #include <vector> 7 8 #include "base/memory/ref_counted.h" 9 #include "chrome/browser/android/thumbnail/scoped_ptr_expiring_cache.h" 10 #include "testing/gmock/include/gmock/gmock.h" 11 #include "testing/gtest/include/gtest/gtest.h" 12 13 #define MAX_CACHE_SIZE 5u 14 15 namespace { 16 17 unsigned int GenerateValue(unsigned int key) { 18 return (key * key * 127) % 133 + key * 23; 19 } 20 21 class MockObject { 22 public: 23 static scoped_ptr<MockObject> Create(unsigned int key) { 24 return make_scoped_ptr(new MockObject(key)); 25 } 26 27 unsigned int value() const { return value_; } 28 29 private: 30 explicit MockObject(unsigned int key) : value_(GenerateValue(key)) {} 31 unsigned int value_; 32 33 DISALLOW_COPY_AND_ASSIGN(MockObject); 34 }; 35 36 } // namespace 37 38 typedef testing::Test ScopedPtrExpiringCacheTest; 39 typedef ScopedPtrExpiringCache<unsigned int, MockObject> 40 TestScopedPtrExpiringCache; 41 42 TEST_F(ScopedPtrExpiringCacheTest, SimplePutAndGet) { 43 TestScopedPtrExpiringCache cache(MAX_CACHE_SIZE); 44 EXPECT_EQ(MAX_CACHE_SIZE, cache.MaximumCacheSize()); 45 EXPECT_EQ(0u, cache.size()); 46 47 for (unsigned int i = 0; i < MAX_CACHE_SIZE; i++) { 48 cache.Put(i, MockObject::Create(i).Pass()); 49 } 50 51 EXPECT_EQ(MAX_CACHE_SIZE, cache.size()); 52 53 unsigned int next_key = MAX_CACHE_SIZE; 54 55 // One cache entry should have been evicted. 56 cache.Put(next_key, MockObject::Create(next_key).Pass()); 57 EXPECT_EQ(MAX_CACHE_SIZE, cache.size()); 58 59 size_t cached_count = 0; 60 for (unsigned int i = 0; i < MAX_CACHE_SIZE + 1; i++) { 61 if (cache.Get(i)) { 62 EXPECT_EQ(GenerateValue(i), cache.Get(i)->value()); 63 cached_count++; 64 } 65 } 66 67 EXPECT_EQ(MAX_CACHE_SIZE, cached_count); 68 69 // Test Get as membership test. 70 cached_count = 0; 71 for (unsigned int i = 0; i < MAX_CACHE_SIZE + 1; i++) { 72 if (cache.Get(i)) 73 cached_count++; 74 } 75 EXPECT_EQ(MAX_CACHE_SIZE, cached_count); 76 77 cache.Clear(); 78 EXPECT_EQ(0u, cache.size()); 79 80 for (unsigned int i = 0; i < MAX_CACHE_SIZE + 1; i++) { 81 EXPECT_EQ(NULL, cache.Get(i)); 82 } 83 } 84 85 // The eviction policy is least-recently-used, where we define used as insertion 86 // into the cache. We test that the first to be evicted is the first entry 87 // inserted into the cache. 88 TEST_F(ScopedPtrExpiringCacheTest, EvictedEntry) { 89 TestScopedPtrExpiringCache cache(MAX_CACHE_SIZE); 90 for (unsigned int i = 0; i < MAX_CACHE_SIZE; i++) { 91 cache.Put(i, MockObject::Create(i).Pass()); 92 } 93 94 unsigned int next_key = MAX_CACHE_SIZE; 95 cache.Put(next_key, MockObject::Create(next_key).Pass()); 96 EXPECT_EQ(MAX_CACHE_SIZE, cache.size()); 97 EXPECT_EQ(GenerateValue(next_key), cache.Get(next_key)->value()); 98 99 // The first inserted entry should have been evicted. 100 EXPECT_EQ(NULL, cache.Get(0)); 101 102 // The rest of the content should be present. 103 for (unsigned int i = 1; i < MAX_CACHE_SIZE; i++) { 104 EXPECT_TRUE(cache.Get(i) != NULL); 105 } 106 107 next_key++; 108 109 // The first candidate to be evicted is the head of the iterator. 110 unsigned int head_key = cache.begin()->first; 111 EXPECT_TRUE(cache.Get(head_key) != NULL); 112 cache.Put(next_key, MockObject::Create(next_key).Pass()); 113 114 EXPECT_NE(cache.begin()->first, head_key); 115 EXPECT_EQ(NULL, cache.Get(head_key)); 116 } 117 118 TEST_F(ScopedPtrExpiringCacheTest, RetainedEntry) { 119 TestScopedPtrExpiringCache cache(MAX_CACHE_SIZE); 120 for (unsigned int i = 0; i < MAX_CACHE_SIZE; i++) { 121 cache.Put(i, MockObject::Create(i).Pass()); 122 } 123 124 // Add (cache size - 1)-entries. 125 for (unsigned int i = 0; i < MAX_CACHE_SIZE; i++) { 126 EXPECT_TRUE(cache.Get(i) != NULL); 127 } 128 129 for (unsigned int i = MAX_CACHE_SIZE; i < 2 * MAX_CACHE_SIZE - 1; i++) { 130 cache.Put(i, MockObject::Create(i).Pass()); 131 } 132 133 EXPECT_EQ(MAX_CACHE_SIZE, cache.size()); 134 135 for (unsigned int i = 0; i < MAX_CACHE_SIZE - 1; i++) { 136 EXPECT_EQ(NULL, cache.Get(i)); 137 } 138 139 // The only retained entry (from the first round of insertion) is the last to 140 // be inserted. 141 EXPECT_TRUE(cache.Get(MAX_CACHE_SIZE - 1) != NULL); 142 } 143 144 // Test that the iterator order is the insertion order. The first element of 145 // the iterator is the oldest entry in the cache. 146 TEST_F(ScopedPtrExpiringCacheTest, Iterator) { 147 TestScopedPtrExpiringCache cache(MAX_CACHE_SIZE); 148 std::vector<unsigned int> test_keys; 149 for (unsigned int i = 0; i < MAX_CACHE_SIZE; i++) { 150 test_keys.push_back(i); 151 } 152 std::random_shuffle(test_keys.begin(), test_keys.end()); 153 154 for (unsigned int i = 0; i < MAX_CACHE_SIZE; i++) { 155 cache.Put(test_keys[i], MockObject::Create(test_keys[i]).Pass()); 156 } 157 158 TestScopedPtrExpiringCache::iterator cache_iter = cache.begin(); 159 std::vector<unsigned int>::iterator key_iter = test_keys.begin(); 160 while (cache_iter != cache.end() && key_iter != test_keys.end()) { 161 EXPECT_EQ(cache_iter->first, *key_iter); 162 cache_iter++; 163 key_iter++; 164 } 165 } 166
