diff options
Diffstat (limited to 'mfbt/MruCache.h')
-rw-r--r-- | mfbt/MruCache.h | 165 |
1 files changed, 165 insertions, 0 deletions
diff --git a/mfbt/MruCache.h b/mfbt/MruCache.h new file mode 100644 index 0000000000..716224a3e0 --- /dev/null +++ b/mfbt/MruCache.h @@ -0,0 +1,165 @@ +/* -*- 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 mozilla_MruCache_h +#define mozilla_MruCache_h + +#include <cstdint> +#include <type_traits> +#include <utility> + +#include "mozilla/Attributes.h" +#include "mozilla/HashFunctions.h" + +namespace mozilla { + +namespace detail { + +// Helper struct for checking if a value is empty. +// +// `IsNotEmpty` will return true if `Value` is not a pointer type or if the +// pointer value is not null. +template <typename Value, bool IsPtr = std::is_pointer<Value>::value> +struct EmptyChecker { + static bool IsNotEmpty(const Value&) { return true; } +}; +// Template specialization for the `IsPtr == true` case. +template <typename Value> +struct EmptyChecker<Value, true> { + static bool IsNotEmpty(const Value& aVal) { return aVal != nullptr; } +}; + +} // namespace detail + +// Provides a most recently used cache that can be used as a layer on top of +// a larger container where lookups can be expensive. The default size is 31, +// which as a prime number provides a better distrubution of cached entries. +// +// Users are expected to provide a `Cache` class that defines two required +// methods: +// - A method for providing the hash of a key: +// +// static HashNumber Hash(const KeyType& aKey) +// +// - A method for matching a key to a value, for pointer types the value +// is guaranteed not to be null. +// +// static bool Match(const KeyType& aKey, const ValueType& aVal) +// +// For example: +// class MruExample : public MruCache<void*, PtrInfo*, MruExample> +// { +// static HashNumber Hash(const KeyType& aKey) +// { +// return HashGeneric(aKey); +// } +// static Match(const KeyType& aKey, const ValueType& aVal) +// { +// return aVal->mPtr == aKey; +// } +// }; +template <class Key, class Value, class Cache, size_t Size = 31> +class MruCache { + // Best distribution is achieved with a prime number. Ideally the closest + // to a power of two will be the most efficient use of memory. This + // assertion is pretty weak, but should catch the common inclination to + // use a power-of-two. + static_assert(Size % 2 != 0, "Use a prime number"); + + // This is a stronger assertion but significantly limits the values to just + // those close to a power-of-two value. + // static_assert(Size == 7 || Size == 13 || Size == 31 || Size == 61 || + // Size == 127 || Size == 251 || Size == 509 || Size == 1021, + // "Use a prime number less than 1024"); + + public: + using KeyType = Key; + using ValueType = Value; + + MruCache() = default; + MruCache(const MruCache&) = delete; + MruCache(const MruCache&&) = delete; + + // Inserts the given value into the cache. Potentially overwrites an + // existing entry. + template <typename U> + void Put(const KeyType& aKey, U&& aVal) { + *RawEntry(aKey) = std::forward<U>(aVal); + } + + // Removes the given entry if it is in the cache. + void Remove(const KeyType& aKey) { Lookup(aKey).Remove(); } + + // Clears all cached entries and resets them to a default value. + void Clear() { + for (ValueType& val : mCache) { + val = ValueType{}; + } + } + + // Helper that holds an entry that matched a lookup key. Usage: + // + // auto p = mCache.Lookup(aKey); + // if (p) { + // return p.Data(); + // } + // + // auto foo = new Foo(); + // p.Set(foo); + // return foo; + class Entry { + public: + Entry(ValueType* aEntry, bool aMatch) : mEntry(aEntry), mMatch(aMatch) { + MOZ_ASSERT(mEntry); + } + + explicit operator bool() const { return mMatch; } + + ValueType& Data() const { + MOZ_ASSERT(mMatch); + return *mEntry; + } + + template <typename U> + void Set(U&& aValue) { + mMatch = true; + Data() = std::forward<U>(aValue); + } + + void Remove() { + if (mMatch) { + Data() = ValueType{}; + mMatch = false; + } + } + + private: + ValueType* mEntry; // Location of the entry in the cache. + bool mMatch; // Whether the value matched. + }; + + // Retrieves an entry from the cache. Can be used to test if an entry is + // present, update the entry to a new value, or remove the entry if one was + // matched. + Entry Lookup(const KeyType& aKey) { + using EmptyChecker = detail::EmptyChecker<ValueType>; + + auto entry = RawEntry(aKey); + bool match = EmptyChecker::IsNotEmpty(*entry) && Cache::Match(aKey, *entry); + return Entry(entry, match); + } + + private: + MOZ_ALWAYS_INLINE ValueType* RawEntry(const KeyType& aKey) { + return &mCache[Cache::Hash(aKey) % Size]; + } + + ValueType mCache[Size] = {}; +}; + +} // namespace mozilla + +#endif // mozilla_mrucache_h |