1 files changed, 199 insertions, 0 deletions
diff --git a/xpcom/build/SmallArrayLRUCache.h b/xpcom/build/SmallArrayLRUCache.h
new file mode 100644
index 0000000000..e7ac727652
--- /dev/null
+++ b/xpcom/build/SmallArrayLRUCache.h
@@ -0,0 +1,199 @@
+/* -*- 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/. */
+
+#ifndef SmallArrayLRUCache_h
+#define SmallArrayLRUCache_h
+
+#include "mozilla/Mutex.h"
+
+#include <algorithm>
+#include <type_traits>
+#include <utility>
+
+// Uncomment the next line to get shutdown stats about cache usage.
+// #define SMALLARRAYLRUCACHE_STATS
+
+#ifdef SMALLARRAYLRUCACHE_STATS
+#  include <cstdio>
+#endif
+
+namespace mozilla {
+
+// Array-based LRU cache, thread-safe.
+// Optimized for cases where `FetchOrAdd` is used with the same key most
+// recently, and assuming the cost of running the value-builder function is much
+// more expensive than going through the whole list.
+// Note: No time limits on keeping items.
+// TODO: Move to more public place, if this could be used elsewhere; make sure
+// the cost/benefits are highlighted.
+template <typename Key, typename Value, unsigned LRUCapacity>
+class SmallArrayLRUCache {
+ public:
+  static_assert(std::is_default_constructible_v<Key>);
+  static_assert(std::is_trivially_constructible_v<Key>);
+  static_assert(std::is_trivially_copyable_v<Key>);
+  static_assert(std::is_default_constructible_v<Value>);
+  static_assert(LRUCapacity >= 2);
+  static_assert(LRUCapacity <= 1024,
+                "This seems a bit big, is this the right cache for your use?");
+
+  // Reset all stored values to their default, and set cache size to zero.
+  void Clear() {
+    mozilla::OffTheBooksMutexAutoLock lock(mMutex);
+    if (mSize == ShutdownSize) {
+      return;
+    }
+    Clear(lock);
+  }
+
+  // Clear the cache, and then prevent further uses (other functions will do
+  // nothing).
+  void Shutdown() {
+    mozilla::OffTheBooksMutexAutoLock lock(mMutex);
+    if (mSize == ShutdownSize) {
+      return;
+    }
+    Clear(lock);
+    mSize = ShutdownSize;
+  }
+
+  // Add a key-value.
+  template <typename ToValue>
+  void Add(Key aKey, ToValue&& aValue) {
+    mozilla::OffTheBooksMutexAutoLock lock(mMutex);
+
+    if (mSize == ShutdownSize) {
+      return;
+    }
+
+    // Quick add to the front, don't remove possible duplicate handles later in
+    // the list, they will eventually drop off the end.
+    KeyAndValue* const item0 = &mLRUArray[0];
+    mSize = std::min(mSize + 1, LRUCapacity);
+    if (MOZ_LIKELY(mSize != 1)) {
+      // List is not empty.
+      // Make a hole at the start.
+      std::move_backward(item0, item0 + mSize - 1, item0 + mSize);
+    }
+    item0->mKey = aKey;
+    item0->mValue = std::forward<ToValue>(aValue);
+    return;
+  }
+
+  // Look for the value associated with `aKey` in the cache.
+  // If not found, run `aValueFunction()`, add it in the cache before returning.
+  // After shutdown, just run `aValueFunction()`.
+  template <typename ValueFunction>
+  Value FetchOrAdd(Key aKey, ValueFunction&& aValueFunction) {
+    Value value;
+    mozilla::OffTheBooksMutexAutoLock lock(mMutex);
+
+    if (mSize == ShutdownSize) {
+      value = std::forward<ValueFunction>(aValueFunction)();
+      return value;
+    }
+
+    KeyAndValue* const item0 = &mLRUArray[0];
+    if (MOZ_UNLIKELY(mSize == 0)) {
+      // List is empty.
+      value = std::forward<ValueFunction>(aValueFunction)();
+      item0->mKey = aKey;
+      item0->mValue = value;
+      mSize = 1;
+      return value;
+    }
+
+    if (MOZ_LIKELY(item0->mKey == aKey)) {
+      // This is already at the beginning of the list, we're done.
+#ifdef SMALLARRAYLRUCACHE_STATS
+      ++mCacheFoundAt[0];
+#endif  // SMALLARRAYLRUCACHE_STATS
+      value = item0->mValue;
+      return value;
+    }
+
+    for (KeyAndValue* item = item0 + 1; item != item0 + mSize; ++item) {
+      if (item->mKey == aKey) {
+        // Found handle in the middle.
+#ifdef SMALLARRAYLRUCACHE_STATS
+        ++mCacheFoundAt[unsigned(item - item0)];
+#endif  // SMALLARRAYLRUCACHE_STATS
+        value = item->mValue;
+        // Move this item to the start of the list.
+        std::rotate(item0, item, item + 1);
+        return value;
+      }
+    }
+
+    // Handle was not in the list.
+#ifdef SMALLARRAYLRUCACHE_STATS
+    ++mCacheFoundAt[LRUCapacity];
+#endif  // SMALLARRAYLRUCACHE_STATS
+    {
+      // Don't lock while doing the potentially-expensive ValueFunction().
+      // This means that the list could change when we lock again, but
+      // it's okay because we'll want to add the new entry at the beginning
+      // anyway, whatever else is in the list then.
+      // In the worst case, it could be the same handle as another `FetchOrAdd`
+      // in parallel, it just means it will be duplicated, so it's a little bit
+      // less efficient (using the extra space), but not wrong (the next
+      // `FetchOrAdd` will find the first one).
+      mozilla::OffTheBooksMutexAutoUnlock unlock(mMutex);
+      value = std::forward<ValueFunction>(aValueFunction)();
+    }
+    // Make a hole at the start, and put the value there.
+    mSize = std::min(mSize + 1, LRUCapacity);
+    std::move_backward(item0, item0 + mSize - 1, item0 + mSize);
+    item0->mKey = aKey;
+    item0->mValue = value;
+    return value;
+  }
+
+#ifdef SMALLARRAYLRUCACHE_STATS
+  ~SmallArrayLRUCache() {
+    if (mSize != 0 && mSize != ShutdownSize) {
+      fprintf(stderr,
+              "***** SmallArrayLRUCache stats: (position -> hit count)\n");
+      for (unsigned i = 0; i < mSize; ++i) {
+        fprintf(stderr, "***** %3u -> %6u\n", i, mCacheFoundAt[i]);
+      }
+      fprintf(stderr, "***** not found -> %6u\n", mCacheFoundAt[LRUCapacity]);
+    }
+  }
+#endif  // SMALLARRAYLRUCACHE_STATS
+
+ private:
+  void Clear(const mozilla::OffTheBooksMutexAutoLock&) MOZ_REQUIRES(mMutex) {
+    for (KeyAndValue* item = &mLRUArray[0]; item != &mLRUArray[mSize]; ++item) {
+      item->mValue = Value{};
+    }
+    mSize = 0;
+  }
+
+  struct KeyAndValue {
+    Key mKey;
+    Value mValue;
+
+    KeyAndValue() = default;
+    KeyAndValue(KeyAndValue&&) = default;
+    KeyAndValue& operator=(KeyAndValue&&) = default;
+  };
+
+  // Special size value that indicates the cache is in shutdown mode.
+  constexpr static unsigned ShutdownSize = unsigned(-1);
+
+  mozilla::OffTheBooksMutex mMutex{"LRU cache"};
+  unsigned mSize MOZ_GUARDED_BY(mMutex) = 0;
+  KeyAndValue mLRUArray[LRUCapacity] MOZ_GUARDED_BY(mMutex);
+#ifdef SMALLARRAYLRUCACHE_STATS
+  // Hit count for each position in the case. +1 for counting not-found cases.
+  unsigned mCacheFoundAt[LRUCapacity + 1] MOZ_GUARDED_BY(mMutex) = {0u};
+#endif  // SMALLARRAYLRUCACHE_STATS
+};
+
+}  // namespace mozilla
+
+#endif  // SmallArrayLRUCache_h