mfbt/MruCache.h

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
   3 /* This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 #ifndef mozilla_MruCache_h
   8 #define mozilla_MruCache_h
   9
  10 #include <cstdint>
  11 #include <type_traits>
  12 #include <utility>
  13
  14 #include "mozilla/Attributes.h"
  15 #include "mozilla/HashFunctions.h"
  16
  17 namespace mozilla {
  18
  19 namespace detail {
  20
  21 // Helper struct for checking if a value is empty.
  22 //
  23 // `IsNotEmpty` will return true if `Value` is not a pointer type or if the
  24 // pointer value is not null.
  25 template <typename Value, bool IsPtr = std::is_pointer<Value>::value>
  26 struct EmptyChecker {
  27   static bool IsNotEmpty(const Value&) { return true; }
  28 };
  29 // Template specialization for the `IsPtr == true` case.
  30 template <typename Value>
  31 struct EmptyChecker<Value, true> {
  32   static bool IsNotEmpty(const Value& aVal) { return aVal != nullptr; }
  33 };
  34
  35 }  // namespace detail
  36
  37 // Provides a most recently used cache that can be used as a layer on top of
  38 // a larger container where lookups can be expensive. The default size is 31,
  39 // which as a prime number provides a better distrubution of cached entries.
  40 //
  41 // Users are expected to provide a `Cache` class that defines two required
  42 // methods:
  43 //   - A method for providing the hash of a key:
  44 //
  45 //     static HashNumber Hash(const KeyType& aKey)
  46 //
  47 //   - A method for matching a key to a value, for pointer types the value
  48 //     is guaranteed not to be null.
  49 //
  50 //     static bool Match(const KeyType& aKey, const ValueType& aVal)
  51 //
  52 // For example:
  53 //    class MruExample : public MruCache<void*, PtrInfo*, MruExample>
  54 //    {
  55 //      static HashNumber Hash(const KeyType& aKey)
  56 //      {
  57 //        return HashGeneric(aKey);
  58 //      }
  59 //      static Match(const KeyType& aKey, const ValueType& aVal)
  60 //      {
  61 //        return aVal->mPtr == aKey;
  62 //      }
  63 //    };
  64 template <class Key, class Value, class Cache, size_t Size = 31>
  65 class MruCache {
  66   // Best distribution is achieved with a prime number. Ideally the closest
  67   // to a power of two will be the most efficient use of memory. This
  68   // assertion is pretty weak, but should catch the common inclination to
  69   // use a power-of-two.
  70   static_assert(Size % 2 != 0, "Use a prime number");
  71
  72   // This is a stronger assertion but significantly limits the values to just
  73   // those close to a power-of-two value.
  74   // static_assert(Size == 7 || Size == 13 || Size == 31 || Size == 61 ||
  75   //              Size == 127 || Size == 251 || Size == 509 || Size == 1021,
  76   //              "Use a prime number less than 1024");
  77
  78  public:
  79   using KeyType = Key;
  80   using ValueType = Value;
  81
  82   MruCache() = default;
  83   MruCache(const MruCache&) = delete;
  84   MruCache(const MruCache&&) = delete;
  85
  86   // Inserts the given value into the cache. Potentially overwrites an
  87   // existing entry.
  88   template <typename U>
  89   void Put(const KeyType& aKey, U&& aVal) {
  90     *RawEntry(aKey) = std::forward<U>(aVal);
  91   }
  92
  93   // Removes the given entry if it is in the cache.
  94   void Remove(const KeyType& aKey) { Lookup(aKey).Remove(); }
  95
  96   // Clears all cached entries and resets them to a default value.
  97   void Clear() {
  98     for (ValueType& val : mCache) {
  99       val = ValueType{};
 100     }
 101   }
 102
 103   // Helper that holds an entry that matched a lookup key. Usage:
 104   //
 105   //    auto p = mCache.Lookup(aKey);
 106   //    if (p) {
 107   //      return p.Data();
 108   //    }
 109   //
 110   //    auto foo = new Foo();
 111   //    p.Set(foo);
 112   //    return foo;
 113   class Entry {
 114    public:
 115     Entry(ValueType* aEntry, bool aMatch) : mEntry(aEntry), mMatch(aMatch) {
 116       MOZ_ASSERT(mEntry);
 117     }
 118
 119     explicit operator bool() const { return mMatch; }
 120
 121     ValueType& Data() const {
 122       MOZ_ASSERT(mMatch);
 123       return *mEntry;
 124     }
 125
 126     template <typename U>
 127     void Set(U&& aValue) {
 128       mMatch = true;
 129       Data() = std::forward<U>(aValue);
 130     }
 131
 132     void Remove() {
 133       if (mMatch) {
 134         Data() = ValueType{};
 135         mMatch = false;
 136       }
 137     }
 138
 139    private:
 140     ValueType* mEntry;  // Location of the entry in the cache.
 141     bool mMatch;        // Whether the value matched.
 142   };
 143
 144   // Retrieves an entry from the cache. Can be used to test if an entry is
 145   // present, update the entry to a new value, or remove the entry if one was
 146   // matched.
 147   Entry Lookup(const KeyType& aKey) {
 148     using EmptyChecker = detail::EmptyChecker<ValueType>;
 149
 150     auto entry = RawEntry(aKey);
 151     bool match = EmptyChecker::IsNotEmpty(*entry) && Cache::Match(aKey, *entry);
 152     return Entry(entry, match);
 153   }
 154
 155  private:
 156   MOZ_ALWAYS_INLINE ValueType* RawEntry(const KeyType& aKey) {
 157     return &mCache[Cache::Hash(aKey) % Size];
 158   }
 159
 160   ValueType mCache[Size] = {};
 161 };
 162
 163 }  // namespace mozilla
 164
 165 #endif  // mozilla_mrucache_h