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 {
+ 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;
+  }
+
+ private:
+  friend class LRUTest;
+  std::list<int> data_;
+};
+
+class LRUTest : public testing::Test {
+ public:
+  LRUTest() : rnd_(42) {}

[DaleCurtis, 2015/10/28 23:06:13]

Hmm, I don't understand the point of the random test if you are using a sequence
which always remains the same. Instead shouldn't this be seeded based on
base::RandInt() or something and if any failures occur the seed printed out?

[hubbe, 2015/10/29 17:52:44]

I don't think so. The point is not make each test different, the point is to
stimulate internal state in ways that I might have missed in my other tests.

[DaleCurtis, 2015/10/29 17:59:05]

Seems like varying the test would do that better though? So long as runs can be
reconstructed it seems useful.

[hubbe, 2015/10/29 21:45:05]

I think the usefulness would be cancelled out by creating a potentially flaky
test.

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

That's why I was expecting failures to print the seed used so that any time it
does fail you'll have the values necessary to reconstruct the failure. The
caveat would be we need to ensure all test failures are logged (even those that
automatic retries correct). I think our flakiness dashboard tracks this, but I'm
not positive.

A test which always runs the same path based on a value which is always the same
seems no more random than the arbitrarily set of test cases one might normally
choose to write by hand :) In which case the addition of a "random" number
generator feels like cognitive overhead.

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

The difference is that a hand written tests might try 10 different internal
state combinations, while one with a loop and a random might test 1000 or 10000.

If using a real random seed would actually find additional problems, chances are
that the automatic re-trying of tests would hide those problems anyways.

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