blob: afb6c35437898c9c0cf5b6c1499510814514ab93 [file] [log] [blame]
// 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 <stddef.h>
#include <list>
#include "base/logging.h"
#include "media/base/test_random.h"
#include "media/blink/lru.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