DXR will be turned off on Tuesday, December 29th. It will redirect to Searchfox.
See the announcement on Discourse.

DXR is a code search and navigation tool aimed at making sense of large projects. It supports full-text and regex searches as well as structural queries.

Line Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166
/* -*- 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();
  //    mTable.Insert(aKey, 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