/work/obj-fuzz/dist/include/mozilla/MruCache.h

Source (jump to first uncovered line)
/* -*- 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

Line	Count	Source (jump to first uncovered line)
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		{
28	0	static bool IsNotEmpty(const Value&) { return true; } Unexecuted instantiation: mozilla::detail::EmptyChecker<nsEffectiveTLDService::TLDCacheEntry, false>::IsNotEmpty(nsEffectiveTLDService::TLDCacheEntry const&) Unexecuted instantiation: mozilla::detail::EmptyChecker<int, false>::IsNotEmpty(int const&) Unexecuted instantiation: mozilla::detail::EmptyChecker<StringStruct, false>::IsNotEmpty(StringStruct const&)
29		};
30		// Template specialization for the `IsPtr == true` case.
31		template <typename Value>
32		struct EmptyChecker<Value, true>
33		{
34	0	static bool IsNotEmpty(const Value& aVal) { return aVal != nullptr; } Unexecuted instantiation: mozilla::detail::EmptyChecker<PtrInfo, true>::IsNotEmpty(PtrInfo const&) Unexecuted instantiation: mozilla::detail::EmptyChecker<nsAtom, true>::IsNotEmpty(nsAtom const&) Unexecuted instantiation: mozilla::detail::EmptyChecker<nsContentList, true>::IsNotEmpty(nsContentList const&) Unexecuted instantiation: mozilla::detail::EmptyChecker<mozilla::dom::NodeInfo, true>::IsNotEmpty(mozilla::dom::NodeInfo const&) Unexecuted instantiation: mozilla::detail::EmptyChecker<char const, true>::IsNotEmpty(char const const&) Unexecuted instantiation: mozilla::detail::EmptyChecker<int, true>::IsNotEmpty(int const&)
35		};
36
37		} // namespace detail
38
39		// Provides a most recently used cache that can be used as a layer on top of
40		// a larger container where lookups can be expensive. The default size is 31,
41		// which as a prime number provides a better distrubution of cached entries.
42		//
43		// Users are expected to provide a `Cache` class that defines two required
44		// methods:
45		// - A method for providing the hash of a key:
46		//
47		// static HashNumber Hash(const KeyType& aKey)
48		//
49		// - A method for matching a key to a value, for pointer types the value
50		// is guaranteed not to be null.
51		//
52		// static bool Match(const KeyType& aKey, const ValueType& aVal)
53		//
54		// For example:
55		// class MruExample : public MruCache<void, PtrInfo, MruExample>
56		// {
57		// static HashNumber Hash(const KeyType& aKey)
58		// {
59		// return HashGeneric(aKey);
60		// }
61		// static Match(const KeyType& aKey, const ValueType& aVal)
62		// {
63		// return aVal->mPtr == aKey;
64		// }
65		// };
66		template <class Key, class Value, class Cache, size_t Size=31>
67		class MruCache
68		{
69		// Best distribution is achieved with a prime number. Ideally the closest
70		// to a power of two will be the most efficient use of memory. This
71		// assertion is pretty weak, but should catch the common inclination to
72		// use a power-of-two.
73		static_assert(Size % 2 != 0, "Use a prime number");
74
75		// This is a stronger assertion but significantly limits the values to just
76		// those close to a power-of-two value.
77		//static_assert(Size == 7 \|\| Size == 13 \|\| Size == 31 \|\| Size == 61 \|\|
78		// Size == 127 \|\| Size == 251 \|\| Size == 509 \|\| Size == 1021,
79		// "Use a prime number less than 1024");
80
81		public:
82		using KeyType = Key;
83		using ValueType = Value;
84
85	0	MruCache() = default; Unexecuted instantiation: mozilla::MruCache<void, PtrInfo, CCGraphBuilder::PtrInfoCache, 491ul>::MruCache() Unexecuted instantiation: mozilla::MruCache<nsTSubstring<char>, nsEffectiveTLDService::TLDCacheEntry, nsEffectiveTLDService::TldCache, 31ul>::MruCache() Unexecuted instantiation: mozilla::MruCache<mozilla::dom::NodeInfo::NodeInfoInner, mozilla::dom::NodeInfo, nsNodeInfoManager::NodeInfoCache, 31ul>::MruCache() Unexecuted instantiation: mozilla::MruCache<int, int, IntMap, 31ul>::MruCache() Unexecuted instantiation: mozilla::MruCache<unsigned long, int, UintPtrMap, 31ul>::MruCache() Unexecuted instantiation: mozilla::MruCache<nsTString<char>, StringStruct, StringStructMap, 31ul>::MruCache()
86		MruCache(const MruCache&) = delete;
87		MruCache(const MruCache&&) = delete;
88
89		// Inserts the given value into the cache. Potentially overwrites an
90		// existing entry.
91		template <typename U>
92		void Put(const KeyType& aKey, U&& aVal)
93	0	{
94	0	*RawEntry(aKey) = std::forward<U>(aVal);
95	0	} Unexecuted instantiation: void mozilla::MruCache<int, int, IntMap, 31ul>::Put<int&>(int const&, int&) Unexecuted instantiation: void mozilla::MruCache<unsigned long, int, UintPtrMap, 31ul>::Put<Convertable<int>&>(unsigned long const&, Convertable<int>&) Unexecuted instantiation: void mozilla::MruCache<unsigned long, int, UintPtrMap, 31ul>::Put<int>(unsigned long const&, int&&) Unexecuted instantiation: void mozilla::MruCache<nsTString<char>, StringStruct, StringStructMap, 31ul>::Put<StringStruct>(nsTString<char> const&, StringStruct&&) Unexecuted instantiation: void mozilla::MruCache<int, int, IntMap, 31ul>::Put<int>(int const&, int&&)
96
97		// Removes the given entry if it is in the cache.
98		void Remove(const KeyType& aKey)
99	0	{
100	0	Lookup(aKey).Remove();
101	0	} Unexecuted instantiation: mozilla::MruCache<void, PtrInfo, CCGraphBuilder::PtrInfoCache, 491ul>::Remove(void* const&) Unexecuted instantiation: mozilla::MruCache<nsContentListKey, nsContentList, ContentListCache, 31ul>::Remove(nsContentListKey const&) Unexecuted instantiation: mozilla::MruCache<mozilla::dom::NodeInfo::NodeInfoInner, mozilla::dom::NodeInfo, nsNodeInfoManager::NodeInfoCache, 31ul>::Remove(mozilla::dom::NodeInfo::NodeInfoInner const&) Unexecuted instantiation: mozilla::MruCache<int, int, IntMap, 31ul>::Remove(int const&) Unexecuted instantiation: mozilla::MruCache<unsigned long, int*, UintPtrMap, 31ul>::Remove(unsigned long const&) Unexecuted instantiation: mozilla::MruCache<nsTString<char>, StringStruct, StringStructMap, 31ul>::Remove(nsTString<char> const&)
102
103		// Clears all cached entries and resets them to a default value.
104		void Clear()
105	0	{
106	0	for (ValueType& val : mCache) {
107	0	val = ValueType{};
108	0	}
109	0	} Unexecuted instantiation: mozilla::MruCache<AtomTableKey, nsAtom*, AtomCache, 31ul>::Clear() Unexecuted instantiation: mozilla::MruCache<int, int, IntMap, 31ul>::Clear()
110
111		// Helper that holds an entry that matched a lookup key. Usage:
112		//
113		// auto p = mCache.Lookup(aKey);
114		// if (p) {
115		// return p.Data();
116		// }
117		//
118		// auto foo = new Foo();
119		// mTable.Insert(aKey, foo);
120		// p.Set(foo);
121		// return foo;
122		class Entry
123		{
124		public:
125		Entry(ValueType* aEntry, bool aMatch)
126		: mEntry(aEntry)
127		, mMatch(aMatch)
128	0	{
129	0	MOZ_ASSERT(mEntry);
130	0	} Unexecuted instantiation: mozilla::MruCache<void, PtrInfo, CCGraphBuilder::PtrInfoCache, 491ul>::Entry::Entry(PtrInfo*, bool) Unexecuted instantiation: mozilla::MruCache<AtomTableKey, nsAtom, AtomCache, 31ul>::Entry::Entry(nsAtom*, bool) Unexecuted instantiation: mozilla::MruCache<nsTSubstring<char>, nsEffectiveTLDService::TLDCacheEntry, nsEffectiveTLDService::TldCache, 31ul>::Entry::Entry(nsEffectiveTLDService::TLDCacheEntry, bool) Unexecuted instantiation: mozilla::MruCache<nsContentListKey, nsContentList, ContentListCache, 31ul>::Entry::Entry(nsContentList, bool) Unexecuted instantiation: mozilla::MruCache<mozilla::dom::NodeInfo::NodeInfoInner, mozilla::dom::NodeInfo, nsNodeInfoManager::NodeInfoCache, 31ul>::Entry::Entry(mozilla::dom::NodeInfo*, bool) Unexecuted instantiation: mozilla::MruCache<int, int, IntMap, 31ul>::Entry::Entry(int, bool) Unexecuted instantiation: mozilla::MruCache<unsigned long, int, UintPtrMap, 31ul>::Entry::Entry(int, bool) Unexecuted instantiation: mozilla::MruCache<nsTString<char>, StringStruct, StringStructMap, 31ul>::Entry::Entry(StringStruct, bool)
131
132	0	explicit operator bool() const { return mMatch; } Unexecuted instantiation: mozilla::MruCache<void, PtrInfo, CCGraphBuilder::PtrInfoCache, 491ul>::Entry::operator bool() const Unexecuted instantiation: mozilla::MruCache<AtomTableKey, nsAtom, AtomCache, 31ul>::Entry::operator bool() const Unexecuted instantiation: mozilla::MruCache<nsTSubstring<char>, nsEffectiveTLDService::TLDCacheEntry, nsEffectiveTLDService::TldCache, 31ul>::Entry::operator bool() const Unexecuted instantiation: mozilla::MruCache<nsContentListKey, nsContentList, ContentListCache, 31ul>::Entry::operator bool() const Unexecuted instantiation: mozilla::MruCache<mozilla::dom::NodeInfo::NodeInfoInner, mozilla::dom::NodeInfo, nsNodeInfoManager::NodeInfoCache, 31ul>::Entry::operator bool() const Unexecuted instantiation: mozilla::MruCache<int, int, IntMap, 31ul>::Entry::operator bool() const Unexecuted instantiation: mozilla::MruCache<unsigned long, int, UintPtrMap, 31ul>::Entry::operator bool() const Unexecuted instantiation: mozilla::MruCache<nsTString<char>, StringStruct, StringStructMap, 31ul>::Entry::operator bool() const
133
134		ValueType& Data() const
135	0	{
136	0	MOZ_ASSERT(mMatch);
137	0	return *mEntry;
138	0	} Unexecuted instantiation: mozilla::MruCache<void, PtrInfo, CCGraphBuilder::PtrInfoCache, 491ul>::Entry::Data() const Unexecuted instantiation: mozilla::MruCache<AtomTableKey, nsAtom, AtomCache, 31ul>::Entry::Data() const Unexecuted instantiation: mozilla::MruCache<nsTSubstring<char>, nsEffectiveTLDService::TLDCacheEntry, nsEffectiveTLDService::TldCache, 31ul>::Entry::Data() const Unexecuted instantiation: mozilla::MruCache<nsContentListKey, nsContentList, ContentListCache, 31ul>::Entry::Data() const Unexecuted instantiation: mozilla::MruCache<mozilla::dom::NodeInfo::NodeInfoInner, mozilla::dom::NodeInfo, nsNodeInfoManager::NodeInfoCache, 31ul>::Entry::Data() const Unexecuted instantiation: mozilla::MruCache<int, int, IntMap, 31ul>::Entry::Data() const Unexecuted instantiation: mozilla::MruCache<unsigned long, int, UintPtrMap, 31ul>::Entry::Data() const Unexecuted instantiation: mozilla::MruCache<nsTString<char>, StringStruct, StringStructMap, 31ul>::Entry::Data() const
139
140		template<typename U>
141		void Set(U&& aValue)
142	0	{
143	0	mMatch = true;
144	0	Data() = std::forward<U>(aValue);
145	0	} Unexecuted instantiation: void mozilla::MruCache<void, PtrInfo, CCGraphBuilder::PtrInfoCache, 491ul>::Entry::Set<PtrInfo&>(PtrInfo&) Unexecuted instantiation: void mozilla::MruCache<AtomTableKey, nsAtom, AtomCache, 31ul>::Entry::Set<RefPtr<nsAtom>&>(RefPtr<nsAtom>&) Unexecuted instantiation: void mozilla::MruCache<nsTSubstring<char>, nsEffectiveTLDService::TLDCacheEntry, nsEffectiveTLDService::TldCache, 31ul>::Entry::Set<nsEffectiveTLDService::TLDCacheEntry>(nsEffectiveTLDService::TLDCacheEntry&&) Unexecuted instantiation: void mozilla::MruCache<nsContentListKey, nsContentList, ContentListCache, 31ul>::Entry::Set<RefPtr<nsContentList>&>(RefPtr<nsContentList>&) Unexecuted instantiation: void mozilla::MruCache<mozilla::dom::NodeInfo::NodeInfoInner, mozilla::dom::NodeInfo*, nsNodeInfoManager::NodeInfoCache, 31ul>::Entry::Set<RefPtr<mozilla::dom::NodeInfo>&>(RefPtr<mozilla::dom::NodeInfo>&) Unexecuted instantiation: void mozilla::MruCache<int, int, IntMap, 31ul>::Entry::Set<int>(int&&) Unexecuted instantiation: void mozilla::MruCache<int, int, IntMap, 31ul>::Entry::Set<Convertable<int>&>(Convertable<int>&) Unexecuted instantiation: void mozilla::MruCache<nsTString<char>, StringStruct, StringStructMap, 31ul>::Entry::Set<StringStruct>(StringStruct&&)
146
147		void Remove()
148	0	{
149	0	if (mMatch) {
150	0	Data() = ValueType{};
151	0	mMatch = false;
152	0	}
153	0	} Unexecuted instantiation: mozilla::MruCache<void, PtrInfo, CCGraphBuilder::PtrInfoCache, 491ul>::Entry::Remove() Unexecuted instantiation: mozilla::MruCache<nsContentListKey, nsContentList, ContentListCache, 31ul>::Entry::Remove() Unexecuted instantiation: mozilla::MruCache<mozilla::dom::NodeInfo::NodeInfoInner, mozilla::dom::NodeInfo, nsNodeInfoManager::NodeInfoCache, 31ul>::Entry::Remove() Unexecuted instantiation: mozilla::MruCache<unsigned long, int*, UintPtrMap, 31ul>::Entry::Remove() Unexecuted instantiation: mozilla::MruCache<nsTString<char>, StringStruct, StringStructMap, 31ul>::Entry::Remove() Unexecuted instantiation: mozilla::MruCache<int, int, IntMap, 31ul>::Entry::Remove()
154
155		private:
156		ValueType* mEntry; // Location of the entry in the cache.
157		bool mMatch; // Whether the value matched.
158		};
159
160		// Retrieves an entry from the cache. Can be used to test if an entry is
161		// present, update the entry to a new value, or remove the entry if one was
162		// matched.
163		Entry Lookup(const KeyType& aKey)
164	0	{
165	0	using EmptyChecker = detail::EmptyChecker<ValueType>;
166	0
167	0	auto entry = RawEntry(aKey);
168	0	bool match = EmptyChecker::IsNotEmpty(entry) && Cache::Match(aKey, entry);
169	0	return Entry(entry, match);
170	0	} Unexecuted instantiation: mozilla::MruCache<void, PtrInfo, CCGraphBuilder::PtrInfoCache, 491ul>::Lookup(void* const&) Unexecuted instantiation: mozilla::MruCache<AtomTableKey, nsAtom, AtomCache, 31ul>::Lookup(AtomTableKey const&) Unexecuted instantiation: mozilla::MruCache<nsTSubstring<char>, nsEffectiveTLDService::TLDCacheEntry, nsEffectiveTLDService::TldCache, 31ul>::Lookup(nsTSubstring<char> const&) Unexecuted instantiation: mozilla::MruCache<nsContentListKey, nsContentList, ContentListCache, 31ul>::Lookup(nsContentListKey const&) Unexecuted instantiation: mozilla::MruCache<mozilla::dom::NodeInfo::NodeInfoInner, mozilla::dom::NodeInfo, nsNodeInfoManager::NodeInfoCache, 31ul>::Lookup(mozilla::dom::NodeInfo::NodeInfoInner const&) Unexecuted instantiation: mozilla::MruCache<int, int, IntMap, 31ul>::Lookup(int const&) Unexecuted instantiation: mozilla::MruCache<unsigned long, int, UintPtrMap, 31ul>::Lookup(unsigned long const&) Unexecuted instantiation: mozilla::MruCache<nsTString<char>, StringStruct, StringStructMap, 31ul>::Lookup(nsTString<char> const&)
171
172		private:
173		MOZ_ALWAYS_INLINE ValueType* RawEntry(const KeyType& aKey)
174	0	{
175	0	return &mCache[Cache::Hash(aKey) % Size];
176	0	} Unexecuted instantiation: mozilla::MruCache<void, PtrInfo, CCGraphBuilder::PtrInfoCache, 491ul>::RawEntry(void* const&) Unexecuted instantiation: mozilla::MruCache<AtomTableKey, nsAtom, AtomCache, 31ul>::RawEntry(AtomTableKey const&) Unexecuted instantiation: mozilla::MruCache<nsTSubstring<char>, nsEffectiveTLDService::TLDCacheEntry, nsEffectiveTLDService::TldCache, 31ul>::RawEntry(nsTSubstring<char> const&) Unexecuted instantiation: mozilla::MruCache<nsContentListKey, nsContentList, ContentListCache, 31ul>::RawEntry(nsContentListKey const&) Unexecuted instantiation: mozilla::MruCache<mozilla::dom::NodeInfo::NodeInfoInner, mozilla::dom::NodeInfo, nsNodeInfoManager::NodeInfoCache, 31ul>::RawEntry(mozilla::dom::NodeInfo::NodeInfoInner const&) Unexecuted instantiation: mozilla::MruCache<int, int, IntMap, 31ul>::RawEntry(int const&) Unexecuted instantiation: mozilla::MruCache<unsigned long, int, UintPtrMap, 31ul>::RawEntry(unsigned long const&) Unexecuted instantiation: mozilla::MruCache<nsTString<char>, StringStruct, StringStructMap, 31ul>::RawEntry(nsTString<char> const&)
177
178		ValueType mCache[Size] = {};
179		};
180
181		} // namespace mozilla
182
183		#endif // mozilla_mrucache_h

Coverage Report

Created: 2018-09-25 14:53