chrome/browser/android/thumbnail/scoped_ptr_expiring_cache_unittest.cc

   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 }