summaryrefslogtreecommitdiffstats
path: root/xpcom/tests/gtest/TestSmallArrayLRUCache.cpp
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--xpcom/tests/gtest/TestSmallArrayLRUCache.cpp368
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();
+ }
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-04 04:27:12 +0000