Multi reader/writer cache/buffer

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 <string>
+
+#include "base/logging.h"
+#include "base/strings/stringprintf.h"
+#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 {

[DaleCurtis, 2015/10/30 00:24:24]

Typically reimplementation type tests like this are considered a bit overboard.
Since both typically have the same author they can suffer from repeated mistakes
as well.

I've generally found it to be just as effective to compare against known good
results. Especially in cases like this where you're evaluating the correctness
of an algorithm. A few hand picked test cases are generally sufficient.

So long as this doesn't add seconds of test runtime it's fine though, so it's up
to you if you prefer to keep this.

[hubbe, 2015/11/02 22:49:53]

I do tend to go a bit overboard sometimes. :)
This class wouldn't really be needed if it wasn't for the random test, and if
you take a look below, I think you'll see that I use some simple hand-coded
examples as well.

Since I do like my random tests, I prefer to keep this class.

I understand the concern about repeated mistakes though.
I'm hoping that this class is simple enough to make such mistakes obvious to
anybody reading the code...

+ 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());
+    }
+    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_;
+};
+}
+
+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) {
+        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;
+      }
+    }
+  }
+}