| // Copyright 2014 The Chromium Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #include <algorithm> |
| #include <vector> |
| |
| #include "base/memory/ref_counted.h" |
| #include "chrome/browser/android/thumbnail/scoped_ptr_expiring_cache.h" |
| #include "testing/gmock/include/gmock/gmock.h" |
| #include "testing/gtest/include/gtest/gtest.h" |
| |
| #define MAX_CACHE_SIZE 5u |
| |
| namespace { |
| |
| unsigned int GenerateValue(unsigned int key) { |
| return (key * key * 127) % 133 + key * 23; |
| } |
| |
| class MockObject { |
| public: |
| static scoped_ptr<MockObject> Create(unsigned int key) { |
| return make_scoped_ptr(new MockObject(key)); |
| } |
| |
| unsigned int value() const { return value_; } |
| |
| private: |
| explicit MockObject(unsigned int key) : value_(GenerateValue(key)) {} |
| unsigned int value_; |
| |
| DISALLOW_COPY_AND_ASSIGN(MockObject); |
| }; |
| |
| } // namespace |
| |
| typedef testing::Test ScopedPtrExpiringCacheTest; |
| typedef ScopedPtrExpiringCache<unsigned int, MockObject> |
| TestScopedPtrExpiringCache; |
| |
| TEST_F(ScopedPtrExpiringCacheTest, SimplePutAndGet) { |
| TestScopedPtrExpiringCache cache(MAX_CACHE_SIZE); |
| EXPECT_EQ(MAX_CACHE_SIZE, cache.MaximumCacheSize()); |
| EXPECT_EQ(0u, cache.size()); |
| |
| for (unsigned int i = 0; i < MAX_CACHE_SIZE; i++) { |
| cache.Put(i, MockObject::Create(i).Pass()); |
| } |
| |
| EXPECT_EQ(MAX_CACHE_SIZE, cache.size()); |
| |
| unsigned int next_key = MAX_CACHE_SIZE; |
| |
| // One cache entry should have been evicted. |
| cache.Put(next_key, MockObject::Create(next_key).Pass()); |
| EXPECT_EQ(MAX_CACHE_SIZE, cache.size()); |
| |
| size_t cached_count = 0; |
| for (unsigned int i = 0; i < MAX_CACHE_SIZE + 1; i++) { |
| if (cache.Get(i)) { |
| EXPECT_EQ(GenerateValue(i), cache.Get(i)->value()); |
| cached_count++; |
| } |
| } |
| |
| EXPECT_EQ(MAX_CACHE_SIZE, cached_count); |
| |
| // Test Get as membership test. |
| cached_count = 0; |
| for (unsigned int i = 0; i < MAX_CACHE_SIZE + 1; i++) { |
| if (cache.Get(i)) |
| cached_count++; |
| } |
| EXPECT_EQ(MAX_CACHE_SIZE, cached_count); |
| |
| cache.Clear(); |
| EXPECT_EQ(0u, cache.size()); |
| |
| for (unsigned int i = 0; i < MAX_CACHE_SIZE + 1; i++) { |
| EXPECT_EQ(NULL, cache.Get(i)); |
| } |
| } |
| |
| // The eviction policy is least-recently-used, where we define used as insertion |
| // into the cache. We test that the first to be evicted is the first entry |
| // inserted into the cache. |
| TEST_F(ScopedPtrExpiringCacheTest, EvictedEntry) { |
| TestScopedPtrExpiringCache cache(MAX_CACHE_SIZE); |
| for (unsigned int i = 0; i < MAX_CACHE_SIZE; i++) { |
| cache.Put(i, MockObject::Create(i).Pass()); |
| } |
| |
| unsigned int next_key = MAX_CACHE_SIZE; |
| cache.Put(next_key, MockObject::Create(next_key).Pass()); |
| EXPECT_EQ(MAX_CACHE_SIZE, cache.size()); |
| EXPECT_EQ(GenerateValue(next_key), cache.Get(next_key)->value()); |
| |
| // The first inserted entry should have been evicted. |
| EXPECT_EQ(NULL, cache.Get(0)); |
| |
| // The rest of the content should be present. |
| for (unsigned int i = 1; i < MAX_CACHE_SIZE; i++) { |
| EXPECT_TRUE(cache.Get(i) != NULL); |
| } |
| |
| next_key++; |
| |
| // The first candidate to be evicted is the head of the iterator. |
| unsigned int head_key = cache.begin()->first; |
| EXPECT_TRUE(cache.Get(head_key) != NULL); |
| cache.Put(next_key, MockObject::Create(next_key).Pass()); |
| |
| EXPECT_NE(cache.begin()->first, head_key); |
| EXPECT_EQ(NULL, cache.Get(head_key)); |
| } |
| |
| TEST_F(ScopedPtrExpiringCacheTest, RetainedEntry) { |
| TestScopedPtrExpiringCache cache(MAX_CACHE_SIZE); |
| for (unsigned int i = 0; i < MAX_CACHE_SIZE; i++) { |
| cache.Put(i, MockObject::Create(i).Pass()); |
| } |
| |
| // Add (cache size - 1)-entries. |
| for (unsigned int i = 0; i < MAX_CACHE_SIZE; i++) { |
| EXPECT_TRUE(cache.Get(i) != NULL); |
| } |
| |
| for (unsigned int i = MAX_CACHE_SIZE; i < 2 * MAX_CACHE_SIZE - 1; i++) { |
| cache.Put(i, MockObject::Create(i).Pass()); |
| } |
| |
| EXPECT_EQ(MAX_CACHE_SIZE, cache.size()); |
| |
| for (unsigned int i = 0; i < MAX_CACHE_SIZE - 1; i++) { |
| EXPECT_EQ(NULL, cache.Get(i)); |
| } |
| |
| // The only retained entry (from the first round of insertion) is the last to |
| // be inserted. |
| EXPECT_TRUE(cache.Get(MAX_CACHE_SIZE - 1) != NULL); |
| } |
| |
| // Test that the iterator order is the insertion order. The first element of |
| // the iterator is the oldest entry in the cache. |
| TEST_F(ScopedPtrExpiringCacheTest, Iterator) { |
| TestScopedPtrExpiringCache cache(MAX_CACHE_SIZE); |
| std::vector<unsigned int> test_keys; |
| for (unsigned int i = 0; i < MAX_CACHE_SIZE; i++) { |
| test_keys.push_back(i); |
| } |
| std::random_shuffle(test_keys.begin(), test_keys.end()); |
| |
| for (unsigned int i = 0; i < MAX_CACHE_SIZE; i++) { |
| cache.Put(test_keys[i], MockObject::Create(test_keys[i]).Pass()); |
| } |
| |
| TestScopedPtrExpiringCache::iterator cache_iter = cache.begin(); |
| std::vector<unsigned int>::iterator key_iter = test_keys.begin(); |
| while (cache_iter != cache.end() && key_iter != test_keys.end()) { |
| EXPECT_EQ(cache_iter->first, *key_iter); |
| cache_iter++; |
| key_iter++; |
| } |
| } |