android: add ThumbnailCache

chrome/browser/android/thumbnail/scoped_ptr_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/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++;
+  }
+}