Simple LRU class

media/blink/lru_unittest.cc

Index: media/blink/lru_unittest.cc
diff --git a/media/blink/lru_unittest.cc b/media/blink/lru_unittest.cc
new file mode 100644
index 0000000000000000000000000000000000000000..82d2a7ce262dd7f7634980a37b18669f29e44d4b
--- /dev/null
+++ b/media/blink/lru_unittest.cc
@@ -0,0 +1,232 @@
+// 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 <string>

[xhwang, 2015/11/10 00:50:01]

what is this for?

[hubbe, 2015/11/10 18:26:15]

I think it was for some code that is now gone.
(removed)

+
+#include "base/logging.h"
+#include "base/strings/stringprintf.h"

[xhwang, 2015/11/10 00:50:01]

what is this for?

[hubbe, 2015/11/10 18:26:15]

I think it was for some code that is now gone.
(removed)

+#include "media/blink/lru.h"
+#include "media/blink/test_random.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace {
+
+const int kTestSize = 16;
+
+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() {
+    media::LRU<int> testee = testee_;
+    EXPECT_EQ(truth_.Size(), testee.Size());
+    for (const auto truth : truth_.data_) {
+      EXPECT_EQ(truth, testee.Pop());
+    }

[xhwang, 2015/11/10 00:50:01]

Why not popping both LRU until empty? Then you don't need the "friend"?

[hubbe, 2015/11/10 18:26:15]

Speed?
The random test below calls this function quite a few times.

[xhwang, 2015/11/10 19:55:13]

Have you actually measured the speed in that case? Just want to make sure we
don't optimize prematurely.

[hubbe, 2015/11/10 21:50:01]

I've done some rough speed tests.
Compare() is a pretty expensive part of the random tests.
Removing the copy here cut the random test speed in almost half though.

+    EXPECT_TRUE(testee.Empty());
+  }
+
+  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_;
+};
+}

[xhwang, 2015/11/10 00:50:01]

nit: // namespace

[hubbe, 2015/11/10 18:26:15]

Done.

+
+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() % kTestSize;
+      switch (rnd_.Rand() % 3) {

[xhwang, 2015/11/10 00:50:01]

value and "operation" could be correlated. Why not use two random number
generator to make this test really random?

[hubbe, 2015/11/10 18:26:15]

If the random number generator is that bad, we should fix it (see test_random.h)

[xhwang, 2015/11/10 19:55:13]

Acknowledged.

+        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;
+      }
+    }
+  }
+}