| OLD | NEW |
| 1 // Copyright 2014 The Chromium Authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
| 3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
| 4 | 4 |
| 5 #include <stddef.h> | 5 #include <stddef.h> |
| 6 | 6 |
| 7 #include <algorithm> | 7 #include <algorithm> |
| 8 #include <vector> | 8 #include <vector> |
| 9 | 9 |
| 10 #include "base/macros.h" | 10 #include "base/macros.h" |
| (...skipping 30 matching lines...) Expand all Loading... |
| 41 typedef testing::Test ScopedPtrExpiringCacheTest; | 41 typedef testing::Test ScopedPtrExpiringCacheTest; |
| 42 typedef ScopedPtrExpiringCache<unsigned int, MockObject> | 42 typedef ScopedPtrExpiringCache<unsigned int, MockObject> |
| 43 TestScopedPtrExpiringCache; | 43 TestScopedPtrExpiringCache; |
| 44 | 44 |
| 45 TEST_F(ScopedPtrExpiringCacheTest, SimplePutAndGet) { | 45 TEST_F(ScopedPtrExpiringCacheTest, SimplePutAndGet) { |
| 46 TestScopedPtrExpiringCache cache(MAX_CACHE_SIZE); | 46 TestScopedPtrExpiringCache cache(MAX_CACHE_SIZE); |
| 47 EXPECT_EQ(MAX_CACHE_SIZE, cache.MaximumCacheSize()); | 47 EXPECT_EQ(MAX_CACHE_SIZE, cache.MaximumCacheSize()); |
| 48 EXPECT_EQ(0u, cache.size()); | 48 EXPECT_EQ(0u, cache.size()); |
| 49 | 49 |
| 50 for (unsigned int i = 0; i < MAX_CACHE_SIZE; i++) { | 50 for (unsigned int i = 0; i < MAX_CACHE_SIZE; i++) { |
| 51 cache.Put(i, MockObject::Create(i).Pass()); | 51 cache.Put(i, MockObject::Create(i)); |
| 52 } | 52 } |
| 53 | 53 |
| 54 EXPECT_EQ(MAX_CACHE_SIZE, cache.size()); | 54 EXPECT_EQ(MAX_CACHE_SIZE, cache.size()); |
| 55 | 55 |
| 56 unsigned int next_key = MAX_CACHE_SIZE; | 56 unsigned int next_key = MAX_CACHE_SIZE; |
| 57 | 57 |
| 58 // One cache entry should have been evicted. | 58 // One cache entry should have been evicted. |
| 59 cache.Put(next_key, MockObject::Create(next_key).Pass()); | 59 cache.Put(next_key, MockObject::Create(next_key)); |
| 60 EXPECT_EQ(MAX_CACHE_SIZE, cache.size()); | 60 EXPECT_EQ(MAX_CACHE_SIZE, cache.size()); |
| 61 | 61 |
| 62 size_t cached_count = 0; | 62 size_t cached_count = 0; |
| 63 for (unsigned int i = 0; i < MAX_CACHE_SIZE + 1; i++) { | 63 for (unsigned int i = 0; i < MAX_CACHE_SIZE + 1; i++) { |
| 64 if (cache.Get(i)) { | 64 if (cache.Get(i)) { |
| 65 EXPECT_EQ(GenerateValue(i), cache.Get(i)->value()); | 65 EXPECT_EQ(GenerateValue(i), cache.Get(i)->value()); |
| 66 cached_count++; | 66 cached_count++; |
| 67 } | 67 } |
| 68 } | 68 } |
| 69 | 69 |
| (...skipping 14 matching lines...) Expand all Loading... |
| 84 EXPECT_EQ(NULL, cache.Get(i)); | 84 EXPECT_EQ(NULL, cache.Get(i)); |
| 85 } | 85 } |
| 86 } | 86 } |
| 87 | 87 |
| 88 // The eviction policy is least-recently-used, where we define used as insertion | 88 // The eviction policy is least-recently-used, where we define used as insertion |
| 89 // into the cache. We test that the first to be evicted is the first entry | 89 // into the cache. We test that the first to be evicted is the first entry |
| 90 // inserted into the cache. | 90 // inserted into the cache. |
| 91 TEST_F(ScopedPtrExpiringCacheTest, EvictedEntry) { | 91 TEST_F(ScopedPtrExpiringCacheTest, EvictedEntry) { |
| 92 TestScopedPtrExpiringCache cache(MAX_CACHE_SIZE); | 92 TestScopedPtrExpiringCache cache(MAX_CACHE_SIZE); |
| 93 for (unsigned int i = 0; i < MAX_CACHE_SIZE; i++) { | 93 for (unsigned int i = 0; i < MAX_CACHE_SIZE; i++) { |
| 94 cache.Put(i, MockObject::Create(i).Pass()); | 94 cache.Put(i, MockObject::Create(i)); |
| 95 } | 95 } |
| 96 | 96 |
| 97 unsigned int next_key = MAX_CACHE_SIZE; | 97 unsigned int next_key = MAX_CACHE_SIZE; |
| 98 cache.Put(next_key, MockObject::Create(next_key).Pass()); | 98 cache.Put(next_key, MockObject::Create(next_key)); |
| 99 EXPECT_EQ(MAX_CACHE_SIZE, cache.size()); | 99 EXPECT_EQ(MAX_CACHE_SIZE, cache.size()); |
| 100 EXPECT_EQ(GenerateValue(next_key), cache.Get(next_key)->value()); | 100 EXPECT_EQ(GenerateValue(next_key), cache.Get(next_key)->value()); |
| 101 | 101 |
| 102 // The first inserted entry should have been evicted. | 102 // The first inserted entry should have been evicted. |
| 103 EXPECT_EQ(NULL, cache.Get(0)); | 103 EXPECT_EQ(NULL, cache.Get(0)); |
| 104 | 104 |
| 105 // The rest of the content should be present. | 105 // The rest of the content should be present. |
| 106 for (unsigned int i = 1; i < MAX_CACHE_SIZE; i++) { | 106 for (unsigned int i = 1; i < MAX_CACHE_SIZE; i++) { |
| 107 EXPECT_TRUE(cache.Get(i) != NULL); | 107 EXPECT_TRUE(cache.Get(i) != NULL); |
| 108 } | 108 } |
| 109 | 109 |
| 110 next_key++; | 110 next_key++; |
| 111 | 111 |
| 112 // The first candidate to be evicted is the head of the iterator. | 112 // The first candidate to be evicted is the head of the iterator. |
| 113 unsigned int head_key = cache.begin()->first; | 113 unsigned int head_key = cache.begin()->first; |
| 114 EXPECT_TRUE(cache.Get(head_key) != NULL); | 114 EXPECT_TRUE(cache.Get(head_key) != NULL); |
| 115 cache.Put(next_key, MockObject::Create(next_key).Pass()); | 115 cache.Put(next_key, MockObject::Create(next_key)); |
| 116 | 116 |
| 117 EXPECT_NE(cache.begin()->first, head_key); | 117 EXPECT_NE(cache.begin()->first, head_key); |
| 118 EXPECT_EQ(NULL, cache.Get(head_key)); | 118 EXPECT_EQ(NULL, cache.Get(head_key)); |
| 119 } | 119 } |
| 120 | 120 |
| 121 TEST_F(ScopedPtrExpiringCacheTest, RetainedEntry) { | 121 TEST_F(ScopedPtrExpiringCacheTest, RetainedEntry) { |
| 122 TestScopedPtrExpiringCache cache(MAX_CACHE_SIZE); | 122 TestScopedPtrExpiringCache cache(MAX_CACHE_SIZE); |
| 123 for (unsigned int i = 0; i < MAX_CACHE_SIZE; i++) { | 123 for (unsigned int i = 0; i < MAX_CACHE_SIZE; i++) { |
| 124 cache.Put(i, MockObject::Create(i).Pass()); | 124 cache.Put(i, MockObject::Create(i)); |
| 125 } | 125 } |
| 126 | 126 |
| 127 // Add (cache size - 1)-entries. | 127 // Add (cache size - 1)-entries. |
| 128 for (unsigned int i = 0; i < MAX_CACHE_SIZE; i++) { | 128 for (unsigned int i = 0; i < MAX_CACHE_SIZE; i++) { |
| 129 EXPECT_TRUE(cache.Get(i) != NULL); | 129 EXPECT_TRUE(cache.Get(i) != NULL); |
| 130 } | 130 } |
| 131 | 131 |
| 132 for (unsigned int i = MAX_CACHE_SIZE; i < 2 * MAX_CACHE_SIZE - 1; i++) { | 132 for (unsigned int i = MAX_CACHE_SIZE; i < 2 * MAX_CACHE_SIZE - 1; i++) { |
| 133 cache.Put(i, MockObject::Create(i).Pass()); | 133 cache.Put(i, MockObject::Create(i)); |
| 134 } | 134 } |
| 135 | 135 |
| 136 EXPECT_EQ(MAX_CACHE_SIZE, cache.size()); | 136 EXPECT_EQ(MAX_CACHE_SIZE, cache.size()); |
| 137 | 137 |
| 138 for (unsigned int i = 0; i < MAX_CACHE_SIZE - 1; i++) { | 138 for (unsigned int i = 0; i < MAX_CACHE_SIZE - 1; i++) { |
| 139 EXPECT_EQ(NULL, cache.Get(i)); | 139 EXPECT_EQ(NULL, cache.Get(i)); |
| 140 } | 140 } |
| 141 | 141 |
| 142 // The only retained entry (from the first round of insertion) is the last to | 142 // The only retained entry (from the first round of insertion) is the last to |
| 143 // be inserted. | 143 // be inserted. |
| 144 EXPECT_TRUE(cache.Get(MAX_CACHE_SIZE - 1) != NULL); | 144 EXPECT_TRUE(cache.Get(MAX_CACHE_SIZE - 1) != NULL); |
| 145 } | 145 } |
| 146 | 146 |
| 147 // Test that the iterator order is the insertion order. The first element of | 147 // Test that the iterator order is the insertion order. The first element of |
| 148 // the iterator is the oldest entry in the cache. | 148 // the iterator is the oldest entry in the cache. |
| 149 TEST_F(ScopedPtrExpiringCacheTest, Iterator) { | 149 TEST_F(ScopedPtrExpiringCacheTest, Iterator) { |
| 150 TestScopedPtrExpiringCache cache(MAX_CACHE_SIZE); | 150 TestScopedPtrExpiringCache cache(MAX_CACHE_SIZE); |
| 151 std::vector<unsigned int> test_keys; | 151 std::vector<unsigned int> test_keys; |
| 152 for (unsigned int i = 0; i < MAX_CACHE_SIZE; i++) { | 152 for (unsigned int i = 0; i < MAX_CACHE_SIZE; i++) { |
| 153 test_keys.push_back(i); | 153 test_keys.push_back(i); |
| 154 } | 154 } |
| 155 std::random_shuffle(test_keys.begin(), test_keys.end()); | 155 std::random_shuffle(test_keys.begin(), test_keys.end()); |
| 156 | 156 |
| 157 for (unsigned int i = 0; i < MAX_CACHE_SIZE; i++) { | 157 for (unsigned int i = 0; i < MAX_CACHE_SIZE; i++) { |
| 158 cache.Put(test_keys[i], MockObject::Create(test_keys[i]).Pass()); | 158 cache.Put(test_keys[i], MockObject::Create(test_keys[i])); |
| 159 } | 159 } |
| 160 | 160 |
| 161 TestScopedPtrExpiringCache::iterator cache_iter = cache.begin(); | 161 TestScopedPtrExpiringCache::iterator cache_iter = cache.begin(); |
| 162 std::vector<unsigned int>::iterator key_iter = test_keys.begin(); | 162 std::vector<unsigned int>::iterator key_iter = test_keys.begin(); |
| 163 while (cache_iter != cache.end() && key_iter != test_keys.end()) { | 163 while (cache_iter != cache.end() && key_iter != test_keys.end()) { |
| 164 EXPECT_EQ(cache_iter->first, *key_iter); | 164 EXPECT_EQ(cache_iter->first, *key_iter); |
| 165 cache_iter++; | 165 cache_iter++; |
| 166 key_iter++; | 166 key_iter++; |
| 167 } | 167 } |
| 168 } | 168 } |
| OLD | NEW |