diff options
Diffstat (limited to 'xpcom/tests/gtest/TestSmallArrayLRUCache.cpp')
| -rw-r--r-- | xpcom/tests/gtest/TestSmallArrayLRUCache.cpp | 368 |
1 files changed, 368 insertions, 0 deletions
diff --git a/xpcom/tests/gtest/TestSmallArrayLRUCache.cpp b/xpcom/tests/gtest/TestSmallArrayLRUCache.cpp new file mode 100644 index 0000000000..10e2b71a69 --- /dev/null +++ b/xpcom/tests/gtest/TestSmallArrayLRUCache.cpp @@ -0,0 +1,368 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ +/* vim: set ts=8 sts=2 et sw=2 tw=80: */ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#include "gtest/gtest.h" + +#include "mozilla/SmallArrayLRUCache.h" + +#include <algorithm> +#include <cstring> +#include <utility> + +using Key = unsigned; + +struct Value { + Value() : m(unsigned(-1)) {} + explicit Value(unsigned a) : m(a) {} + + bool operator==(const Value& aOther) const { return m == aOther.m; } + bool operator!=(const Value& aOther) const { return m != aOther.m; } + + unsigned m; +}; + +constexpr static unsigned CacheSize = 8; + +using TestCache = mozilla::SmallArrayLRUCache<Key, Value, CacheSize>; + +// This struct embeds a given object type between two "guard" objects, to check +// if anything is written out of bounds. +template <typename T> +struct Boxed { + constexpr static size_t GuardSize = std::max(sizeof(T), size_t(256)); + + // A Guard is a character array with a pre-set content that can be checked for + // unwanted changes. + struct Guard { + char mGuard[GuardSize]; + explicit Guard(char aValue) { memset(&mGuard, aValue, GuardSize); } + void Check(char aValue) { + for (const char& c : mGuard) { + ASSERT_EQ(c, aValue); + } + } + }; + + Guard mGuardBefore; + T mObject; + Guard mGuardAfter; + + template <typename... Ts> + explicit Boxed(Ts&&... aTs) + : mGuardBefore(0x5a), + mObject(std::forward<Ts>(aTs)...), + mGuardAfter(0xa5) { + Check(); + } + + ~Boxed() { Check(); } + + T& Object() { return mObject; } + const T& Object() const { return mObject; } + + void Check() { + mGuardBefore.Check(0x5a); + mGuardAfter.Check(0xa5); + } +}; + +TEST(SmallArrayLRUCache, FetchOrAdd_KeysFitInCache) +{ + // We're going to add-or-fetch between 1 and CacheSize keys, so they all fit + // in the cache. + for (Key keys = 1; keys <= CacheSize; ++keys) { + Boxed<TestCache> boxedCache; + TestCache& cache = boxedCache.Object(); + for (Key i = 0; i < keys; ++i) { + bool valueFunctionCalled = false; + Value v = cache.FetchOrAdd(i, [&]() { + valueFunctionCalled = true; + return Value{i}; + }); + ASSERT_EQ(v, Value{i}); + ASSERT_TRUE(valueFunctionCalled); + boxedCache.Check(); + } + + // Fetching any key should never call the value function. + for (Key i = 0; i < CacheSize * 3; ++i) { + { + bool valueFunctionCalled = false; + Value v = cache.FetchOrAdd(i % keys, [&]() { + valueFunctionCalled = true; + return Value{i % keys}; + }); + ASSERT_EQ(v, Value{i % keys}); + ASSERT_FALSE(valueFunctionCalled); + boxedCache.Check(); + } + // Fetching the same key again will never call the function value. + { + bool valueFunctionCalled = false; + Value v = cache.FetchOrAdd(i % keys, [&]() { + valueFunctionCalled = true; + return Value{i % keys}; + }); + ASSERT_EQ(v, Value{i % keys}); + ASSERT_FALSE(valueFunctionCalled); + boxedCache.Check(); + } + } + } +} + +TEST(SmallArrayLRUCache, Add_FetchOrAdd_KeysFitInCache) +{ + // We're going to add between 1 and CacheSize keys, so they all fit in the + // cache. + for (Key keys = 1; keys <= CacheSize; ++keys) { + Boxed<TestCache> boxedCache; + TestCache& cache = boxedCache.Object(); + for (Key i = 0; i < keys; ++i) { + cache.Add(i, Value{i}); + boxedCache.Check(); + } + + // Fetching any key should never call the value function. + for (Key i = 0; i < CacheSize * 3; ++i) { + { + bool valueFunctionCalled = false; + Value v = cache.FetchOrAdd(i % keys, [&]() { + valueFunctionCalled = true; + return Value{i % keys}; + }); + ASSERT_EQ(v, Value{i % keys}); + ASSERT_FALSE(valueFunctionCalled); + boxedCache.Check(); + } + // Fetching the same key again will never call the function value. + { + bool valueFunctionCalled = false; + Value v = cache.FetchOrAdd(i % keys, [&]() { + valueFunctionCalled = true; + return Value{i % keys}; + }); + ASSERT_EQ(v, Value{i % keys}); + ASSERT_FALSE(valueFunctionCalled); + boxedCache.Check(); + } + } + } +} + +TEST(SmallArrayLRUCache, FetchOrAdd_KeysDoNotFitInCache) +{ + // We're going to add-or-fetch strictly more than CacheSize keys, so they + // cannot fit in the cache, only the last `CacheSize` ones are kept. + for (Key keys = CacheSize + 1; keys <= CacheSize * 2; ++keys) { + Boxed<TestCache> boxedCache; + TestCache& cache = boxedCache.Object(); + for (Key i = 0; i < keys; ++i) { + bool valueFunctionCalled = false; + Value v = cache.FetchOrAdd(i, [&]() { + valueFunctionCalled = true; + return Value{i}; + }); + ASSERT_EQ(v, Value{i}); + ASSERT_TRUE(valueFunctionCalled); + boxedCache.Check(); + } + + // Fetching keys from 0 should always call the function value: + // - 0 is the oldest key, it must have been pushed out when `CacheSize` + // was added. + // - Once we've fetched 0, it's pushed out the old (smallest) key. + // Etc. + for (Key i = 0; i < CacheSize * 3; ++i) { + { + bool valueFunctionCalled = false; + Value v = cache.FetchOrAdd(i % keys, [&]() { + valueFunctionCalled = true; + return Value{i % keys}; + }); + ASSERT_EQ(v, Value{i % keys}); + ASSERT_TRUE(valueFunctionCalled); + boxedCache.Check(); + } + // Fetching the same key again will never call the function value. + { + bool valueFunctionCalled = false; + Value v = cache.FetchOrAdd(i % keys, [&]() { + valueFunctionCalled = true; + return Value{i % keys}; + }); + ASSERT_EQ(v, Value{i % keys}); + ASSERT_FALSE(valueFunctionCalled); + boxedCache.Check(); + } + } + } +} + +TEST(SmallArrayLRUCache, Add_FetchOrAdd_KeysDoNotFitInCache) +{ + // We're going to add strictly more than CacheSize keys, so they cannot fit in + // the cache, only the last `CacheSize` ones are kept. + for (Key keys = CacheSize + 1; keys <= CacheSize * 2; ++keys) { + Boxed<TestCache> boxedCache; + TestCache& cache = boxedCache.Object(); + for (Key i = 0; i < keys; ++i) { + cache.Add(i, Value{i}); + boxedCache.Check(); + } + + // Fetching keys from 0 should always call the function value: + // - 0 is the oldest key, it must have been pushed out when `CacheSize` + // was added. + // - Once we've fetched 0, it's pushed out the old (smallest) key. + // Etc. + for (Key i = 0; i < CacheSize * 3; ++i) { + { + bool valueFunctionCalled = false; + Value v = cache.FetchOrAdd(i % keys, [&]() { + valueFunctionCalled = true; + return Value{i % keys}; + }); + ASSERT_EQ(v, Value{i % keys}); + ASSERT_TRUE(valueFunctionCalled); + boxedCache.Check(); + } + // Fetching the same key again will never call the function value. + { + bool valueFunctionCalled = false; + Value v = cache.FetchOrAdd(i % keys, [&]() { + valueFunctionCalled = true; + return Value{i % keys}; + }); + ASSERT_EQ(v, Value{i % keys}); + ASSERT_FALSE(valueFunctionCalled); + boxedCache.Check(); + } + } + } +} + +TEST(SmallArrayLRUCache, Clear) +{ + Boxed<TestCache> boxedCache; + TestCache& cache = boxedCache.Object(); + + // First fetch will always call the function value. + { + bool valueFunctionCalled = false; + Value v = cache.FetchOrAdd(42, [&]() { + valueFunctionCalled = true; + return Value{4242}; + }); + ASSERT_EQ(v, Value{4242}); + ASSERT_TRUE(valueFunctionCalled); + boxedCache.Check(); + } + + // Second fetch will never call the function value. + { + bool valueFunctionCalled = false; + Value v = cache.FetchOrAdd(42, [&]() { + valueFunctionCalled = true; + return Value{4242}; + }); + ASSERT_EQ(v, Value{4242}); + ASSERT_FALSE(valueFunctionCalled); + boxedCache.Check(); + } + + cache.Clear(); + + // After Clear(), first fetch will always call the function value. + { + bool valueFunctionCalled = false; + Value v = cache.FetchOrAdd(42, [&]() { + valueFunctionCalled = true; + return Value{4242}; + }); + ASSERT_EQ(v, Value{4242}); + ASSERT_TRUE(valueFunctionCalled); + boxedCache.Check(); + } + + // Next fetch will never call the function value. + { + bool valueFunctionCalled = false; + Value v = cache.FetchOrAdd(42, [&]() { + valueFunctionCalled = true; + return Value{4242}; + }); + ASSERT_EQ(v, Value{4242}); + ASSERT_FALSE(valueFunctionCalled); + boxedCache.Check(); + } +} + +TEST(SmallArrayLRUCache, Shutdown) +{ + Boxed<TestCache> boxedCache; + TestCache& cache = boxedCache.Object(); + + // First fetch will always call the function value. + { + bool valueFunctionCalled = false; + Value v = cache.FetchOrAdd(42, [&]() { + valueFunctionCalled = true; + return Value{4242}; + }); + ASSERT_EQ(v, Value{4242}); + ASSERT_TRUE(valueFunctionCalled); + boxedCache.Check(); + } + + // Second fetch will never call the function value. + { + bool valueFunctionCalled = false; + Value v = cache.FetchOrAdd(42, [&]() { + valueFunctionCalled = true; + return Value{4242}; + }); + ASSERT_EQ(v, Value{4242}); + ASSERT_FALSE(valueFunctionCalled); + boxedCache.Check(); + } + + cache.Shutdown(); + + // After Shutdown(), any fetch will always call the function value. + { + bool valueFunctionCalled = false; + Value v = cache.FetchOrAdd(42, [&]() { + valueFunctionCalled = true; + return Value{4242}; + }); + ASSERT_EQ(v, Value{4242}); + ASSERT_TRUE(valueFunctionCalled); + boxedCache.Check(); + } + { + bool valueFunctionCalled = false; + Value v = cache.FetchOrAdd(42, [&]() { + valueFunctionCalled = true; + return Value{4242}; + }); + ASSERT_EQ(v, Value{4242}); + ASSERT_TRUE(valueFunctionCalled); + boxedCache.Check(); + } + cache.Add(42, Value{4242}); + boxedCache.Check(); + { + bool valueFunctionCalled = false; + Value v = cache.FetchOrAdd(42, [&]() { + valueFunctionCalled = true; + return Value{4242}; + }); + ASSERT_EQ(v, Value{4242}); + ASSERT_TRUE(valueFunctionCalled); + boxedCache.Check(); + } +} |