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
|
