Multi reader/writer cache/buffer

media/blink/lru_unittests.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 <stdint.h>
+
+#include <list>
+#include <string>
+
+#include "base/logging.h"
+#include "base/strings/stringprintf.h"
+#include "media/blink/lru.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace {
+
+const int kTestSize = 16;
+
+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;
+  }
+
+  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:
+  std::list<int> data_;
+};
+
+class LRUTest : public testing::Test {
+ public:
+  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() {
+    for (int i = 0; i < kTestSize; i++) {
+      EXPECT_EQ(truth_.Contains(i), testee_.Contains(i)) << "i =" << i;
+    }
+    EXPECT_EQ(truth_.Empty(), 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();
+  }
+
+
+ private:
+  SimpleLRU truth_;
+  media::LRU<int> testee_;
+};
+
+}
+
+TEST_F(LRUTest, RandomTest) {
+  for (int j = 0; j < 100; j++) {
+    Clear();
+    for (int i = 0; i < 1000; i++) {
+      int value = rand() % kTestSize;
+      switch (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;
+      }
+    }
+  }
+}