Simple LRU class

media/blink/lru_unittest.cc

+// Copyright 2015 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 <list>
+
+#include "base/logging.h"
+#include "media/blink/lru.h"
+#include "media/blink/test_random.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+// Range of integer used in tests below.
+// We keep the integers small to get lots of re-use of integers.
+const int kTestIntRange = 16;
+
+namespace media {
+
+class LRUTest;
+
+class SimpleLRU {
+ public:
+  void Insert(int x) {
+    DCHECK(!Contains(x));
+    data_.push_back(x);
+  }
+
+  void Remove(int x) {
+    for (std::list<int>::iterator i = data_.begin(); i != data_.end(); ++i) {
+      if (*i == x) {
+        data_.erase(i);
+        DCHECK(!Contains(x));
+        return;
+      }
+    }
+    LOG(FATAL) << "Remove non-existing element " << x;
+  }
+
+  void Use(int x) {
+    if (Contains(x))
+      Remove(x);
+    Insert(x);
+  }
+
+  bool Empty() const { return data_.empty(); }
+
+  int Pop() {
+    DCHECK(!Empty());
+    int ret = data_.front();
+    data_.pop_front();
+    return ret;
+  }
+
+  int Peek() {
+    DCHECK(!Empty());
+    return data_.front();
+  }
+
+  bool Contains(int x) const {
+    for (std::list<int>::const_iterator i = data_.begin(); i != data_.end();
+         ++i) {
+      if (*i == x) {
+        return true;
+      }
+    }
+    return false;
+  }
+
+  size_t Size() const { return data_.size(); }
+
+ private:
+  friend class LRUTest;
+  std::list<int> data_;
+};
+
+class LRUTest : public testing::Test {
+ public:
+  LRUTest() : rnd_(42) {}
+
+  void Insert(int x) {
+    truth_.Insert(x);
+    testee_.Insert(x);
+    Compare();
+  }
+
+  void Remove(int x) {
+    truth_.Remove(x);
+    testee_.Remove(x);
+    Compare();
+  }
+
+  void Use(int x) {
+    truth_.Use(x);
+    testee_.Use(x);
+    Compare();
+  }
+
+  int Pop() {
+    int truth_value = truth_.Pop();
+    int testee_value = testee_.Pop();
+    EXPECT_EQ(truth_value, testee_value);
+    Compare();
+    return truth_value;
+  }
+
+  void Compare() {
+    EXPECT_EQ(truth_.Size(), testee_.Size());
+    auto testee_iterator = testee_.lru_.rbegin();
+    for (const auto truth : truth_.data_) {
+      EXPECT_TRUE(testee_iterator != testee_.lru_.rend());
+      EXPECT_EQ(truth, *testee_iterator);
+      ++testee_iterator;
+    }
+    EXPECT_TRUE(testee_iterator == testee_.lru_.rend());
+  }
+
+  bool Empty() const {
+    EXPECT_EQ(truth_.Empty(), testee_.Empty());
+    return truth_.Empty();
+  }
+
+  bool Contains(int i) const {
+    EXPECT_EQ(truth_.Contains(i), testee_.Contains(i));
+    return testee_.Contains(i);
+  }
+
+  void Clear() {
+    while (!Empty())
+      Pop();
+  }
+
+  int Peek() {
+    EXPECT_EQ(truth_.Peek(), testee_.Peek());
+    return testee_.Peek();
+  }
+
+ protected:
+  media::TestRandom rnd_;
+  SimpleLRU truth_;
+  media::LRU<int> testee_;
+};
+
+TEST_F(LRUTest, SimpleTest) {
+  Insert(1);  // 1
+  Insert(2);  // 1 2
+  Insert(3);  // 1 2 3
+  EXPECT_EQ(1, Peek());
+  EXPECT_EQ(1, Pop());  // 2 3
+  EXPECT_EQ(2, Peek());
+  Use(2);  // 3 2
+  EXPECT_EQ(3, Peek());
+  EXPECT_EQ(3, Pop());  // 2
+  EXPECT_EQ(2, Pop());
+  EXPECT_TRUE(Empty());
+}
+
+TEST_F(LRUTest, UseTest) {
+  EXPECT_TRUE(Empty());
+  // Using a value that's not on the LRU adds it.
+  Use(3);  // 3
+  EXPECT_EQ(3, Peek());
+  Use(5);  // 3 5
+  EXPECT_EQ(3, Peek());
+  EXPECT_TRUE(Contains(5));
+  Use(7);  // 3 5 7
+  EXPECT_EQ(3, Peek());
+  EXPECT_TRUE(Contains(7));
+  // Using a value that's alraedy on the LRU moves it to the top.
+  Use(3);  // 5 7 3
+  EXPECT_EQ(5, Peek());
+  EXPECT_TRUE(Contains(5));
+  EXPECT_EQ(5, Pop());  // 7 3
+  EXPECT_FALSE(Contains(5));
+  EXPECT_EQ(7, Peek());
+  EXPECT_TRUE(Contains(7));
+  EXPECT_TRUE(Contains(3));
+  Use(9);  // 7 3 9
+  EXPECT_EQ(7, Peek());
+  // Using the same value again has no effect.
+  Use(9);  // 7 3 9
+  EXPECT_EQ(7, Peek());
+  Use(3);  // 7 9 3
+  EXPECT_EQ(7, Pop());
+  EXPECT_EQ(9, Pop());
+  EXPECT_EQ(3, Pop());
+  EXPECT_TRUE(Empty());
+}
+
+TEST_F(LRUTest, RemoveTest) {
+  Insert(5);  // 5
+  Insert(4);  // 5 4
+  Insert(3);  // 5 4 3
+  Insert(2);  // 5 4 3 2
+  Insert(1);  // 5 4 3 2 1
+  EXPECT_EQ(5, Peek());
+  Remove(5);  // 4 3 2 1
+  EXPECT_EQ(4, Peek());
+  Remove(1);  // 4 3 2
+  EXPECT_EQ(4, Peek());
+  Remove(3);  // 4 2
+  EXPECT_EQ(4, Pop());
+  EXPECT_EQ(2, Pop());
+  EXPECT_TRUE(Empty());
+}
+
+TEST_F(LRUTest, RandomTest) {
+  for (int j = 0; j < 100; j++) {
+    Clear();
+    for (int i = 0; i < 1000; i++) {
+      int value = rnd_.Rand() % kTestIntRange;
+      switch (rnd_.Rand() % 3) {
+        case 0:
+          if (!Empty())
+            Pop();
+          break;
+
+        case 1:
+          Use(value);
+          break;
+
+        case 2:
+          if (Contains(value)) {
+            Remove(value);
+          } else {
+            Insert(value);
+          }
+          break;
+      }
+      if (HasFailure()) {
+        return;
+      }
+    }
+  }
+}
+
+}  // namespace media