android: add ThumbnailCache

chrome/browser/android/thumbnail/lru_expiring_cache_unittest.cc

+// 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/lru_expiring_cache.h"
+#include "testing/gmock/include/gmock/gmock.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+#define MAX_CACHE_SIZE 5u
+
+namespace {
+
+class MockObject {
+ public:
+  MockObject() : value_(0) {}
+  explicit MockObject(int key) : value_((key * 127) % 13 + 23) {}
+  bool operator==(const MockObject& object) const {
+    return value_ == object.value_;
+  }
+  bool operator!=(const MockObject& object) const { return !(*this == object); }
+
+ private:
+  int value_;
+};
+
+const MockObject kInvalidValue;
+
+}  // namespace
+
+typedef testing::Test ThumbnailCache_LRUExpiringCacheTest;
+typedef LRUExpiringCache<int, MockObject> TestLRUExpiringCache;
+
+TEST_F(ThumbnailCache_LRUExpiringCacheTest, SimplePutAndGet) {
+  TestLRUExpiringCache cache(MAX_CACHE_SIZE);
+  EXPECT_EQ(cache.MaximumCacheSize(), MAX_CACHE_SIZE);
+  EXPECT_EQ(cache.size(), 0u);
+
+  for (unsigned int i = 0; i < MAX_CACHE_SIZE; i++) {
+    cache.Put(i, MockObject(i));
+  }
+
+  EXPECT_EQ(cache.size(), MAX_CACHE_SIZE);
+
+  int next_key = MAX_CACHE_SIZE;
+
+  // One cache entry should have been evicted.
+  cache.Put(next_key, MockObject(next_key));
+  EXPECT_EQ(cache.size(), MAX_CACHE_SIZE);
+
+  size_t cached_count = 0;
+  for (unsigned int i = 0; i < MAX_CACHE_SIZE + 1; i++) {
+    if (cache.Get(i) != kInvalidValue) {
+      EXPECT_EQ(cache.Get(i), MockObject(i));
+      cached_count++;
+    }
+  }
+
+  EXPECT_EQ(cached_count, MAX_CACHE_SIZE);
+
+  // Test Contains()
+  cached_count = 0;
+  for (unsigned int i = 0; i < MAX_CACHE_SIZE + 1; i++) {
+    if (cache.Contains(i))
+      cached_count++;
+  }
+  EXPECT_EQ(cached_count, MAX_CACHE_SIZE);
+
+  cache.Clear();
+  EXPECT_EQ(cache.size(), 0u);
+
+  for (unsigned int i = 0; i < MAX_CACHE_SIZE + 1; i++) {
+    EXPECT_FALSE(cache.Contains(i));
+    EXPECT_EQ(cache.Get(i), kInvalidValue);
+  }
+}
+
+// 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(ThumbnailCache_LRUExpiringCacheTest, EvictedEntry) {
+  TestLRUExpiringCache cache(MAX_CACHE_SIZE);
+  for (unsigned int i = 0; i < MAX_CACHE_SIZE; i++) {
+    cache.Put(i, MockObject(i));
+  }
+
+  int next_key = MAX_CACHE_SIZE;
+  cache.Put(next_key, MockObject(next_key));
+  EXPECT_EQ(cache.size(), MAX_CACHE_SIZE);
+  EXPECT_EQ(cache.Get(next_key), MockObject(next_key));
+
+  // The first inserted entry should have been evicted.
+  EXPECT_FALSE(cache.Contains(0));
+
+  // The rest of the content should be present.
+  for (unsigned int i = 1; i < MAX_CACHE_SIZE; i++) {
+    EXPECT_TRUE(cache.Contains(i));
+  }
+
+  next_key++;
+
+  // The first candidate to be evicted is the head of the iterator.
+  int head_key = cache.begin()->first;
+  EXPECT_TRUE(cache.Contains(head_key));
+  cache.Put(next_key, MockObject(next_key));
+
+  EXPECT_NE(cache.begin()->first, head_key);
+  EXPECT_FALSE(cache.Contains(head_key));
+}
+
+TEST_F(ThumbnailCache_LRUExpiringCacheTest, RetainedEntry) {
+  TestLRUExpiringCache cache(MAX_CACHE_SIZE);
+  for (unsigned int i = 0; i < MAX_CACHE_SIZE; i++) {
+    cache.Put(i, MockObject(i));
+  }
+
+  // Add (cache size - 1)-entries.
+  for (unsigned int i = 0; i < MAX_CACHE_SIZE; i++) {
+    EXPECT_TRUE(cache.Contains(i));
+  }
+
+  for (unsigned int i = MAX_CACHE_SIZE; i < 2 * MAX_CACHE_SIZE - 1; i++) {
+    cache.Put(i, MockObject(i));
+  }
+
+  EXPECT_EQ(cache.size(), MAX_CACHE_SIZE);
+
+  for (unsigned int i = 0; i < MAX_CACHE_SIZE - 1; i++) {
+    EXPECT_FALSE(cache.Contains(i));
+  }
+
+  // The only retained entry (from the first round of insertion) is the last to
+  // be inserted.
+  EXPECT_TRUE(cache.Contains(MAX_CACHE_SIZE - 1));
+}
+
+// Test that the iterator order is the insertion order.  The first element of
+// the iterator is the oldest entry in the cache.
+TEST_F(ThumbnailCache_LRUExpiringCacheTest, Iterator) {
+  TestLRUExpiringCache 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(test_keys[i]));
+  }
+
+  TestLRUExpiringCache::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++;
+  }
+}