mirror of
https://github.com/grumpycoders/pcsx-redux.git
synced 2025-04-02 10:41:54 -04:00
340 lines
9.9 KiB
C++
340 lines
9.9 KiB
C++
/////////////////////////////////////////////////////////////////////////////
|
|
// Copyright (c) Electronic Arts Inc. All rights reserved.
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
|
|
#include "EASTLTest.h"
|
|
#include <EASTL/bonus/lru_cache.h>
|
|
#include <EASTL/unique_ptr.h>
|
|
|
|
namespace TestLruCacheInternal
|
|
{
|
|
struct Foo
|
|
{
|
|
static int count;
|
|
|
|
Foo()
|
|
: a(count++)
|
|
, b(count++)
|
|
{ }
|
|
|
|
Foo(int x, int y) : a(x), b(y) {}
|
|
|
|
int a;
|
|
int b;
|
|
|
|
bool operator==(const Foo &other)
|
|
{
|
|
return this->a == other.a && this->b == other.b;
|
|
}
|
|
};
|
|
|
|
int Foo::count = 0;
|
|
|
|
class FooCreator
|
|
{
|
|
public:
|
|
FooCreator() : mFooCreatedCount(0) {}
|
|
|
|
Foo *Create()
|
|
{
|
|
mFooCreatedCount++;
|
|
return new Foo();
|
|
}
|
|
|
|
void Destroy(Foo *f)
|
|
{
|
|
delete f;
|
|
mFooCreatedCount--;
|
|
}
|
|
|
|
int mFooCreatedCount;
|
|
};
|
|
}
|
|
|
|
|
|
int TestLruCache()
|
|
{
|
|
int nErrorCount = 0;
|
|
|
|
// Test simple situation
|
|
{
|
|
using namespace TestLruCacheInternal;
|
|
|
|
eastl::lru_cache<int, Foo> lruCache(3);
|
|
|
|
// Empty state
|
|
EATEST_VERIFY(lruCache.contains(1) == false);
|
|
EATEST_VERIFY(lruCache.size() == 0);
|
|
EATEST_VERIFY(lruCache.empty() == true);
|
|
EATEST_VERIFY(lruCache.capacity() == 3);
|
|
EATEST_VERIFY(lruCache.at(1).has_value() == false);
|
|
|
|
// Auto create with get call
|
|
EATEST_VERIFY(lruCache[0].a == 0);
|
|
EATEST_VERIFY(lruCache[0].b == 1);
|
|
EATEST_VERIFY(lruCache.contains(1) == false);
|
|
EATEST_VERIFY(lruCache.contains(0) == true);
|
|
EATEST_VERIFY(lruCache.size() == 1);
|
|
EATEST_VERIFY(lruCache.empty() == false);
|
|
EATEST_VERIFY(lruCache.capacity() == 3);
|
|
|
|
// Fill structure up to 2 more entries to fill out, also test at()
|
|
lruCache.insert(1, Foo(2, 3));
|
|
EATEST_VERIFY(lruCache.at(1).value().a == 2);
|
|
EATEST_VERIFY(lruCache.at(1).value().b == 3);
|
|
EATEST_VERIFY(lruCache.contains(0) == true);
|
|
EATEST_VERIFY(lruCache.contains(1) == true);
|
|
EATEST_VERIFY(lruCache.contains(2) == false);
|
|
EATEST_VERIFY(lruCache.contains(3) == false);
|
|
EATEST_VERIFY(lruCache.size() == 2);
|
|
EATEST_VERIFY(lruCache.empty() == false);
|
|
EATEST_VERIFY(lruCache.capacity() == 3);
|
|
|
|
lruCache.insert(2, Foo(4, 5));
|
|
EATEST_VERIFY(lruCache[2].a == 4);
|
|
EATEST_VERIFY(lruCache[2].b == 5);
|
|
EATEST_VERIFY(lruCache.contains(0) == true);
|
|
EATEST_VERIFY(lruCache.contains(1) == true);
|
|
EATEST_VERIFY(lruCache.contains(2) == true);
|
|
EATEST_VERIFY(lruCache.contains(3) == false);
|
|
EATEST_VERIFY(lruCache.size() == 3);
|
|
EATEST_VERIFY(lruCache.empty() == false);
|
|
EATEST_VERIFY(lruCache.capacity() == 3);
|
|
|
|
// Add another entry, at this point 0 is the oldest, so it should be pulled
|
|
lruCache.insert(3, Foo(6, 7));
|
|
EATEST_VERIFY(lruCache[3].a == 6);
|
|
EATEST_VERIFY(lruCache[3].b == 7);
|
|
EATEST_VERIFY(lruCache.contains(0) == false);
|
|
EATEST_VERIFY(lruCache.contains(1) == true);
|
|
EATEST_VERIFY(lruCache.contains(2) == true);
|
|
EATEST_VERIFY(lruCache.contains(3) == true);
|
|
EATEST_VERIFY(lruCache.size() == 3);
|
|
EATEST_VERIFY(lruCache.empty() == false);
|
|
EATEST_VERIFY(lruCache.capacity() == 3);
|
|
|
|
// Touch the now oldest 1 key
|
|
EATEST_VERIFY(lruCache.touch(1) == true);
|
|
|
|
// Add another entry, this will be #4 but since 1 was touched, 2 is now the oldest
|
|
lruCache.insert(4, Foo(8, 9));
|
|
EATEST_VERIFY(lruCache[4].a == 8);
|
|
EATEST_VERIFY(lruCache[4].b == 9);
|
|
EATEST_VERIFY(lruCache.contains(0) == false);
|
|
EATEST_VERIFY(lruCache.contains(1) == true);
|
|
EATEST_VERIFY(lruCache.contains(2) == false);
|
|
EATEST_VERIFY(lruCache.contains(3) == true);
|
|
EATEST_VERIFY(lruCache.contains(4) == true);
|
|
EATEST_VERIFY(lruCache.size() == 3);
|
|
EATEST_VERIFY(lruCache.empty() == false);
|
|
EATEST_VERIFY(lruCache.capacity() == 3);
|
|
|
|
// Test resize down
|
|
EATEST_VERIFY(lruCache.touch(3) == true); // Let's make some key in the middle the most recent
|
|
lruCache.resize(1); // Resize down to 1 entry in the cache
|
|
EATEST_VERIFY(lruCache.contains(0) == false);
|
|
EATEST_VERIFY(lruCache.contains(1) == false);
|
|
EATEST_VERIFY(lruCache.contains(2) == false);
|
|
EATEST_VERIFY(lruCache.contains(3) == true);
|
|
EATEST_VERIFY(lruCache.contains(4) == false);
|
|
EATEST_VERIFY(lruCache.size() == 1);
|
|
EATEST_VERIFY(lruCache.empty() == false);
|
|
EATEST_VERIFY(lruCache.capacity() == 1);
|
|
|
|
// Let's resize up to a size of 5 now
|
|
lruCache.resize(5);
|
|
EATEST_VERIFY(lruCache.contains(0) == false);
|
|
EATEST_VERIFY(lruCache.contains(1) == false);
|
|
EATEST_VERIFY(lruCache.contains(2) == false);
|
|
EATEST_VERIFY(lruCache.contains(3) == true);
|
|
EATEST_VERIFY(lruCache.contains(4) == false);
|
|
EATEST_VERIFY(lruCache.size() == 1);
|
|
EATEST_VERIFY(lruCache.empty() == false);
|
|
EATEST_VERIFY(lruCache.capacity() == 5);
|
|
|
|
// Let's try updating
|
|
lruCache.assign(3, Foo(0, 0));
|
|
EATEST_VERIFY(lruCache[3] == Foo(0, 0));
|
|
EATEST_VERIFY(lruCache.contains(0) == false);
|
|
EATEST_VERIFY(lruCache.contains(1) == false);
|
|
EATEST_VERIFY(lruCache.contains(2) == false);
|
|
EATEST_VERIFY(lruCache.contains(3) == true);
|
|
EATEST_VERIFY(lruCache.contains(4) == false);
|
|
EATEST_VERIFY(lruCache.size() == 1);
|
|
EATEST_VERIFY(lruCache.empty() == false);
|
|
EATEST_VERIFY(lruCache.capacity() == 5);
|
|
|
|
// add or update existing
|
|
lruCache.insert_or_assign(3, Foo(1, 1));
|
|
EATEST_VERIFY(lruCache[3] == Foo(1, 1));
|
|
EATEST_VERIFY(lruCache.contains(0) == false);
|
|
EATEST_VERIFY(lruCache.contains(1) == false);
|
|
EATEST_VERIFY(lruCache.contains(2) == false);
|
|
EATEST_VERIFY(lruCache.contains(3) == true);
|
|
EATEST_VERIFY(lruCache.contains(4) == false);
|
|
EATEST_VERIFY(lruCache.size() == 1);
|
|
EATEST_VERIFY(lruCache.empty() == false);
|
|
EATEST_VERIFY(lruCache.capacity() == 5);
|
|
|
|
// Add or update a new entry
|
|
lruCache.insert_or_assign(25, Foo(2, 2));
|
|
EATEST_VERIFY(lruCache[3] == Foo(1, 1));
|
|
EATEST_VERIFY(lruCache[25] == Foo(2, 2));
|
|
EATEST_VERIFY(lruCache.contains(0) == false);
|
|
EATEST_VERIFY(lruCache.contains(1) == false);
|
|
EATEST_VERIFY(lruCache.contains(2) == false);
|
|
EATEST_VERIFY(lruCache.contains(3) == true);
|
|
EATEST_VERIFY(lruCache.contains(4) == false);
|
|
EATEST_VERIFY(lruCache.contains(25) == true);
|
|
EATEST_VERIFY(lruCache.size() == 2);
|
|
EATEST_VERIFY(lruCache.empty() == false);
|
|
EATEST_VERIFY(lruCache.capacity() == 5);
|
|
|
|
// clear everything
|
|
lruCache.clear();
|
|
EATEST_VERIFY(lruCache.size() == 0);
|
|
EATEST_VERIFY(lruCache.empty() == true);
|
|
EATEST_VERIFY(lruCache.capacity() == 5);
|
|
EATEST_VERIFY(lruCache.contains(3) == false);
|
|
|
|
// test unilateral reset
|
|
lruCache[1] = Foo(1, 2);
|
|
lruCache.reset_lose_memory();
|
|
EATEST_VERIFY(lruCache.size() == 0);
|
|
}
|
|
|
|
// Test more advanced creation / deletion via callbacks
|
|
{
|
|
using namespace TestLruCacheInternal;
|
|
|
|
FooCreator fooCreator;
|
|
|
|
auto createCallback = [&fooCreator](int) { return fooCreator.Create(); };
|
|
auto deleteCallback = [&fooCreator](Foo *f) { fooCreator.Destroy(f); };
|
|
|
|
eastl::lru_cache<int, Foo*> lruCache(3, EASTLAllocatorType("eastl lru_cache"), createCallback, deleteCallback);
|
|
|
|
lruCache[1];
|
|
EATEST_VERIFY(fooCreator.mFooCreatedCount == 1);
|
|
EATEST_VERIFY(lruCache.size() == 1);
|
|
EATEST_VERIFY(lruCache.empty() == false);
|
|
EATEST_VERIFY(lruCache.capacity() == 3);
|
|
EATEST_VERIFY(lruCache.contains(1) == true);
|
|
EATEST_VERIFY(lruCache.contains(2) == false);
|
|
|
|
lruCache[2];
|
|
EATEST_VERIFY(fooCreator.mFooCreatedCount == 2);
|
|
EATEST_VERIFY(lruCache.size() == 2);
|
|
EATEST_VERIFY(lruCache.empty() == false);
|
|
EATEST_VERIFY(lruCache.capacity() == 3);
|
|
EATEST_VERIFY(lruCache.contains(1) == true);
|
|
EATEST_VERIFY(lruCache.contains(2) == true);
|
|
|
|
// Update 2, which should delete the existing entry
|
|
{
|
|
auto f = fooCreator.Create();
|
|
EATEST_VERIFY(fooCreator.mFooCreatedCount == 3);
|
|
f->a = 20;
|
|
f->b = 21;
|
|
lruCache.assign(2, f);
|
|
EATEST_VERIFY(fooCreator.mFooCreatedCount == 2);
|
|
EATEST_VERIFY(lruCache.size() == 2);
|
|
EATEST_VERIFY(lruCache.empty() == false);
|
|
EATEST_VERIFY(lruCache.capacity() == 3);
|
|
EATEST_VERIFY(lruCache.contains(1) == true);
|
|
EATEST_VERIFY(lruCache.contains(2) == true);
|
|
EATEST_VERIFY(lruCache[2]->a == 20);
|
|
EATEST_VERIFY(lruCache[2]->b == 21);
|
|
}
|
|
|
|
lruCache.erase(2);
|
|
EATEST_VERIFY(fooCreator.mFooCreatedCount == 1);
|
|
EATEST_VERIFY(lruCache.size() == 1);
|
|
EATEST_VERIFY(lruCache.empty() == false);
|
|
EATEST_VERIFY(lruCache.capacity() == 3);
|
|
EATEST_VERIFY(lruCache.contains(1) == true);
|
|
EATEST_VERIFY(lruCache.contains(2) == false);
|
|
|
|
lruCache.erase(1);
|
|
EATEST_VERIFY(fooCreator.mFooCreatedCount == 0);
|
|
EATEST_VERIFY(lruCache.size() == 0);
|
|
EATEST_VERIFY(lruCache.empty() == true);
|
|
EATEST_VERIFY(lruCache.capacity() == 3);
|
|
EATEST_VERIFY(lruCache.contains(1) == false);
|
|
EATEST_VERIFY(lruCache.contains(2) == false);
|
|
|
|
// Test insert_or_assign
|
|
{
|
|
auto f = fooCreator.Create();
|
|
f->a = 22;
|
|
f->b = 30;
|
|
EATEST_VERIFY(fooCreator.mFooCreatedCount == 1);
|
|
|
|
lruCache.insert_or_assign(7, f);
|
|
EATEST_VERIFY(lruCache.size() == 1);
|
|
EATEST_VERIFY(lruCache.empty() == false);
|
|
EATEST_VERIFY(lruCache.capacity() == 3);
|
|
EATEST_VERIFY(lruCache.contains(1) == false);
|
|
EATEST_VERIFY(lruCache.contains(2) == false);
|
|
EATEST_VERIFY(lruCache.contains(7) == true);
|
|
EATEST_VERIFY(lruCache.erase(7) == true);
|
|
EATEST_VERIFY(fooCreator.mFooCreatedCount == 0);
|
|
}
|
|
}
|
|
|
|
// Test iteration
|
|
{
|
|
eastl::lru_cache<int, int> lc(5);
|
|
lc.insert_or_assign(0,10);
|
|
lc.insert_or_assign(1,11);
|
|
lc.insert_or_assign(2,12);
|
|
lc.insert_or_assign(3,13);
|
|
lc.insert_or_assign(4,14);
|
|
|
|
{ // test manual for-loop
|
|
int i = 0;
|
|
for (auto b = lc.begin(), e = lc.end(); b != e; b++)
|
|
{
|
|
auto &p = *b;
|
|
VERIFY(i == p.first);
|
|
VERIFY(i + 10 == p.second.first);
|
|
i++;
|
|
}
|
|
}
|
|
|
|
{ // test pairs
|
|
int i = 0;
|
|
for(auto& p : lc)
|
|
{
|
|
VERIFY(i == p.first);
|
|
VERIFY(i + 10 == p.second.first);
|
|
i++;
|
|
}
|
|
}
|
|
|
|
{ // test structured bindings
|
|
int i = 0;
|
|
for(auto& [key, value] : lc)
|
|
{
|
|
VERIFY(i == key);
|
|
VERIFY(i + 10 == value.first);
|
|
i++;
|
|
}
|
|
}
|
|
}
|
|
|
|
// test initializer_list
|
|
{
|
|
eastl::lru_cache<int, int> lc = {{0, 10}, {1, 11}, {2, 12}, {3, 13}, {4, 14}, {5, 15}};
|
|
|
|
int i = 0;
|
|
for(auto& p : lc)
|
|
{
|
|
VERIFY(i == p.first);
|
|
VERIFY(i + 10 == p.second.first);
|
|
i++;
|
|
}
|
|
}
|
|
|
|
return nErrorCount;
|
|
}
|