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/. */
7 //---------------------------------------------------------------------------
9 //---------------------------------------------------------------------------
11 // This file defines HashMap<Key, Value> and HashSet<T>, hash tables that are
12 // fast and have a nice API.
14 // Both hash tables have two optional template parameters.
16 // - HashPolicy. This defines the operations for hashing and matching keys. The
17 // default HashPolicy is appropriate when both of the following two
18 // conditions are true.
20 // - The key type stored in the table (|Key| for |HashMap<Key, Value>|, |T|
21 // for |HashSet<T>|) is an integer, pointer, UniquePtr, float, or double.
23 // - The type used for lookups (|Lookup|) is the same as the key type. This
24 // is usually the case, but not always.
26 // There is also a |CStringHasher| policy for |char*| keys. If your keys
27 // don't match any of the above cases, you must provide your own hash policy;
28 // see the "Hash Policy" section below.
30 // - AllocPolicy. This defines how allocations are done by the table.
32 // - |MallocAllocPolicy| is the default and is usually appropriate; note that
33 // operations (such as insertions) that might cause allocations are
34 // fallible and must be checked for OOM. These checks are enforced by the
35 // use of [[nodiscard]].
37 // - |InfallibleAllocPolicy| is another possibility; it allows the
38 // abovementioned OOM checks to be done with MOZ_ALWAYS_TRUE().
40 // Note that entry storage allocation is lazy, and not done until the first
41 // lookupForAdd(), put(), or putNew() is performed.
43 // See AllocPolicy.h for more details.
45 // Documentation on how to use HashMap and HashSet, including examples, is
46 // present within those classes. Search for "class HashMap" and "class
49 // Both HashMap and HashSet are implemented on top of a third class, HashTable.
50 // You only need to look at HashTable if you want to understand the
53 // How does mozilla::HashTable (this file) compare with PLDHashTable (and its
54 // subclasses, such as nsTHashtable)?
56 // - mozilla::HashTable is a lot faster, largely because it uses templates
57 // throughout *and* inlines everything. PLDHashTable inlines operations much
58 // less aggressively, and also uses "virtual ops" for operations like hashing
59 // and matching entries that require function calls.
61 // - Correspondingly, mozilla::HashTable use is likely to increase executable
62 // size much more than PLDHashTable.
64 // - mozilla::HashTable has a nicer API, with a proper HashSet vs. HashMap
67 // - mozilla::HashTable requires more explicit OOM checking. As mentioned
68 // above, the use of |InfallibleAllocPolicy| can simplify things.
70 // - mozilla::HashTable has a default capacity on creation of 32 and a minimum
71 // capacity of 4. PLDHashTable has a default capacity on creation of 8 and a
72 // minimum capacity of 8.
74 #ifndef mozilla_HashTable_h
75 #define mozilla_HashTable_h
78 #include <type_traits>
80 #include "mozilla/AllocPolicy.h"
81 #include "mozilla/Assertions.h"
82 #include "mozilla/Attributes.h"
83 #include "mozilla/Casting.h"
84 #include "mozilla/HashFunctions.h"
85 #include "mozilla/MathAlgorithms.h"
86 #include "mozilla/Maybe.h"
87 #include "mozilla/MemoryChecking.h"
88 #include "mozilla/MemoryReporting.h"
89 #include "mozilla/Opaque.h"
90 #include "mozilla/OperatorNewExtensions.h"
91 #include "mozilla/ReentrancyGuard.h"
92 #include "mozilla/UniquePtr.h"
93 #include "mozilla/WrappingOperations.h"
97 template <class, class = void>
100 template <class, class>
105 template <typename T
>
106 class HashTableEntry
;
108 template <class T
, class HashPolicy
, class AllocPolicy
>
111 } // namespace detail
113 // The "generation" of a hash table is an opaque value indicating the state of
114 // modification of the hash table through its lifetime. If the generation of
115 // a hash table compares equal at times T1 and T2, then lookups in the hash
116 // table, pointers to (or into) hash table entries, etc. at time T1 are valid
117 // at time T2. If the generation compares unequal, these computations are all
118 // invalid and must be performed again to be used.
120 // Generations are meaningfully comparable only with respect to a single hash
121 // table. It's always nonsensical to compare the generation of distinct hash
123 using Generation
= Opaque
<uint64_t>;
125 //---------------------------------------------------------------------------
127 //---------------------------------------------------------------------------
129 // HashMap is a fast hash-based map from keys to values.
131 // Template parameter requirements:
132 // - Key/Value: movable, destructible, assignable.
133 // - HashPolicy: see the "Hash Policy" section below.
134 // - AllocPolicy: see AllocPolicy.h.
137 // - HashMap is not reentrant: Key/Value/HashPolicy/AllocPolicy members
138 // called by HashMap must not call back into the same HashMap object.
140 template <class Key
, class Value
, class HashPolicy
= DefaultHasher
<Key
>,
141 class AllocPolicy
= MallocAllocPolicy
>
143 // -- Implementation details -----------------------------------------------
145 // HashMap is not copyable or assignable.
146 HashMap(const HashMap
& hm
) = delete;
147 HashMap
& operator=(const HashMap
& hm
) = delete;
149 using TableEntry
= HashMapEntry
<Key
, Value
>;
151 struct MapHashPolicy
: HashPolicy
{
152 using Base
= HashPolicy
;
155 static const Key
& getKey(TableEntry
& aEntry
) { return aEntry
.key(); }
157 static void setKey(TableEntry
& aEntry
, Key
& aKey
) {
158 HashPolicy::rekey(aEntry
.mutableKey(), aKey
);
162 using Impl
= detail::HashTable
<TableEntry
, MapHashPolicy
, AllocPolicy
>;
165 friend class Impl::Enum
;
168 using Lookup
= typename
HashPolicy::Lookup
;
169 using Entry
= TableEntry
;
171 // -- Initialization -------------------------------------------------------
173 explicit HashMap(AllocPolicy aAllocPolicy
= AllocPolicy(),
174 uint32_t aLen
= Impl::sDefaultLen
)
175 : mImpl(std::move(aAllocPolicy
), aLen
) {}
177 explicit HashMap(uint32_t aLen
) : mImpl(AllocPolicy(), aLen
) {}
179 // HashMap is movable.
180 HashMap(HashMap
&& aRhs
) = default;
181 HashMap
& operator=(HashMap
&& aRhs
) = default;
183 // -- Status and sizing ----------------------------------------------------
185 // The map's current generation.
186 Generation
generation() const { return mImpl
.generation(); }
189 bool empty() const { return mImpl
.empty(); }
191 // Number of keys/values in the map.
192 uint32_t count() const { return mImpl
.count(); }
194 // Number of key/value slots in the map. Note: resize will happen well before
195 // count() == capacity().
196 uint32_t capacity() const { return mImpl
.capacity(); }
198 // The size of the map's entry storage, in bytes. If the keys/values contain
199 // pointers to other heap blocks, you must iterate over the map and measure
200 // them separately; hence the "shallow" prefix.
201 size_t shallowSizeOfExcludingThis(MallocSizeOf aMallocSizeOf
) const {
202 return mImpl
.shallowSizeOfExcludingThis(aMallocSizeOf
);
204 size_t shallowSizeOfIncludingThis(MallocSizeOf aMallocSizeOf
) const {
205 return aMallocSizeOf(this) +
206 mImpl
.shallowSizeOfExcludingThis(aMallocSizeOf
);
209 // Attempt to minimize the capacity(). If the table is empty, this will free
210 // the empty storage and upon regrowth it will be given the minimum capacity.
211 void compact() { mImpl
.compact(); }
213 // Attempt to reserve enough space to fit at least |aLen| elements. This is
214 // total capacity, including elements already present. Does nothing if the
215 // map already has sufficient capacity.
216 [[nodiscard
]] bool reserve(uint32_t aLen
) { return mImpl
.reserve(aLen
); }
218 // -- Lookups --------------------------------------------------------------
220 // Does the map contain a key/value matching |aLookup|?
221 bool has(const Lookup
& aLookup
) const {
222 return mImpl
.lookup(aLookup
).found();
225 // Return a Ptr indicating whether a key/value matching |aLookup| is
226 // present in the map. E.g.:
228 // using HM = HashMap<int,char>;
230 // if (HM::Ptr p = h.lookup(3)) {
231 // assert(p->key() == 3);
232 // char val = p->value();
235 using Ptr
= typename
Impl::Ptr
;
236 MOZ_ALWAYS_INLINE Ptr
lookup(const Lookup
& aLookup
) const {
237 return mImpl
.lookup(aLookup
);
240 // Like lookup(), but does not assert if two threads call it at the same
241 // time. Only use this method when none of the threads will modify the map.
242 MOZ_ALWAYS_INLINE Ptr
readonlyThreadsafeLookup(const Lookup
& aLookup
) const {
243 return mImpl
.readonlyThreadsafeLookup(aLookup
);
246 // -- Insertions -----------------------------------------------------------
248 // Overwrite existing value with |aValue|, or add it if not present. Returns
250 template <typename KeyInput
, typename ValueInput
>
251 [[nodiscard
]] bool put(KeyInput
&& aKey
, ValueInput
&& aValue
) {
252 return put(aKey
, std::forward
<KeyInput
>(aKey
),
253 std::forward
<ValueInput
>(aValue
));
256 template <typename KeyInput
, typename ValueInput
>
257 [[nodiscard
]] bool put(const Lookup
& aLookup
, KeyInput
&& aKey
,
258 ValueInput
&& aValue
) {
259 AddPtr p
= lookupForAdd(aLookup
);
261 p
->value() = std::forward
<ValueInput
>(aValue
);
264 return add(p
, std::forward
<KeyInput
>(aKey
),
265 std::forward
<ValueInput
>(aValue
));
268 // Like put(), but slightly faster. Must only be used when the given key is
269 // not already present. (In debug builds, assertions check this.)
270 template <typename KeyInput
, typename ValueInput
>
271 [[nodiscard
]] bool putNew(KeyInput
&& aKey
, ValueInput
&& aValue
) {
272 return mImpl
.putNew(aKey
, std::forward
<KeyInput
>(aKey
),
273 std::forward
<ValueInput
>(aValue
));
276 template <typename KeyInput
, typename ValueInput
>
277 [[nodiscard
]] bool putNew(const Lookup
& aLookup
, KeyInput
&& aKey
,
278 ValueInput
&& aValue
) {
279 return mImpl
.putNew(aLookup
, std::forward
<KeyInput
>(aKey
),
280 std::forward
<ValueInput
>(aValue
));
283 // Like putNew(), but should be only used when the table is known to be big
284 // enough for the insertion, and hashing cannot fail. Typically this is used
285 // to populate an empty map with known-unique keys after reserving space with
288 // using HM = HashMap<int,char>;
290 // if (!h.reserve(3)) {
293 // h.putNewInfallible(1, 'a'); // unique key
294 // h.putNewInfallible(2, 'b'); // unique key
295 // h.putNewInfallible(3, 'c'); // unique key
297 template <typename KeyInput
, typename ValueInput
>
298 void putNewInfallible(KeyInput
&& aKey
, ValueInput
&& aValue
) {
299 mImpl
.putNewInfallible(aKey
, std::forward
<KeyInput
>(aKey
),
300 std::forward
<ValueInput
>(aValue
));
303 // Like |lookup(l)|, but on miss, |p = lookupForAdd(l)| allows efficient
304 // insertion of Key |k| (where |HashPolicy::match(k,l) == true|) using
305 // |add(p,k,v)|. After |add(p,k,v)|, |p| points to the new key/value. E.g.:
307 // using HM = HashMap<int,char>;
309 // HM::AddPtr p = h.lookupForAdd(3);
311 // if (!h.add(p, 3, 'a')) {
315 // assert(p->key() == 3);
316 // char val = p->value();
318 // N.B. The caller must ensure that no mutating hash table operations occur
319 // between a pair of lookupForAdd() and add() calls. To avoid looking up the
320 // key a second time, the caller may use the more efficient relookupOrAdd()
321 // method. This method reuses part of the hashing computation to more
322 // efficiently insert the key if it has not been added. For example, a
323 // mutation-handling version of the previous example:
325 // HM::AddPtr p = h.lookupForAdd(3);
327 // call_that_may_mutate_h();
328 // if (!h.relookupOrAdd(p, 3, 'a')) {
332 // assert(p->key() == 3);
333 // char val = p->value();
335 using AddPtr
= typename
Impl::AddPtr
;
336 MOZ_ALWAYS_INLINE AddPtr
lookupForAdd(const Lookup
& aLookup
) {
337 return mImpl
.lookupForAdd(aLookup
);
340 // Add a key/value. Returns false on OOM.
341 template <typename KeyInput
, typename ValueInput
>
342 [[nodiscard
]] bool add(AddPtr
& aPtr
, KeyInput
&& aKey
, ValueInput
&& aValue
) {
343 return mImpl
.add(aPtr
, std::forward
<KeyInput
>(aKey
),
344 std::forward
<ValueInput
>(aValue
));
347 // See the comment above lookupForAdd() for details.
348 template <typename KeyInput
, typename ValueInput
>
349 [[nodiscard
]] bool relookupOrAdd(AddPtr
& aPtr
, KeyInput
&& aKey
,
350 ValueInput
&& aValue
) {
351 return mImpl
.relookupOrAdd(aPtr
, aKey
, std::forward
<KeyInput
>(aKey
),
352 std::forward
<ValueInput
>(aValue
));
355 // -- Removal --------------------------------------------------------------
357 // Lookup and remove the key/value matching |aLookup|, if present.
358 void remove(const Lookup
& aLookup
) {
359 if (Ptr p
= lookup(aLookup
)) {
364 // Remove a previously found key/value (assuming aPtr.found()). The map must
365 // not have been mutated in the interim.
366 void remove(Ptr aPtr
) { mImpl
.remove(aPtr
); }
368 // Remove all keys/values without changing the capacity.
369 void clear() { mImpl
.clear(); }
371 // Like clear() followed by compact().
372 void clearAndCompact() { mImpl
.clearAndCompact(); }
374 // -- Rekeying -------------------------------------------------------------
376 // Infallibly rekey one entry, if necessary. Requires that template
377 // parameters Key and HashPolicy::Lookup are the same type.
378 void rekeyIfMoved(const Key
& aOldKey
, const Key
& aNewKey
) {
379 if (aOldKey
!= aNewKey
) {
380 rekeyAs(aOldKey
, aNewKey
, aNewKey
);
384 // Infallibly rekey one entry if present, and return whether that happened.
385 bool rekeyAs(const Lookup
& aOldLookup
, const Lookup
& aNewLookup
,
386 const Key
& aNewKey
) {
387 if (Ptr p
= lookup(aOldLookup
)) {
388 mImpl
.rekeyAndMaybeRehash(p
, aNewLookup
, aNewKey
);
394 // -- Iteration ------------------------------------------------------------
396 // |iter()| returns an Iterator:
398 // HashMap<int, char> h;
399 // for (auto iter = h.iter(); !iter.done(); iter.next()) {
400 // char c = iter.get().value();
403 using Iterator
= typename
Impl::Iterator
;
404 Iterator
iter() const { return mImpl
.iter(); }
406 // |modIter()| returns a ModIterator:
408 // HashMap<int, char> h;
409 // for (auto iter = h.modIter(); !iter.done(); iter.next()) {
410 // if (iter.get().value() == 'l') {
415 // Table resize may occur in ModIterator's destructor.
416 using ModIterator
= typename
Impl::ModIterator
;
417 ModIterator
modIter() { return mImpl
.modIter(); }
419 // These are similar to Iterator/ModIterator/iter(), but use different
421 using Range
= typename
Impl::Range
;
422 using Enum
= typename
Impl::Enum
;
423 Range
all() const { return mImpl
.all(); }
426 //---------------------------------------------------------------------------
428 //---------------------------------------------------------------------------
430 // HashSet is a fast hash-based set of values.
432 // Template parameter requirements:
433 // - T: movable, destructible, assignable.
434 // - HashPolicy: see the "Hash Policy" section below.
435 // - AllocPolicy: see AllocPolicy.h
438 // - HashSet is not reentrant: T/HashPolicy/AllocPolicy members called by
439 // HashSet must not call back into the same HashSet object.
441 template <class T
, class HashPolicy
= DefaultHasher
<T
>,
442 class AllocPolicy
= MallocAllocPolicy
>
444 // -- Implementation details -----------------------------------------------
446 // HashSet is not copyable or assignable.
447 HashSet(const HashSet
& hs
) = delete;
448 HashSet
& operator=(const HashSet
& hs
) = delete;
450 struct SetHashPolicy
: HashPolicy
{
451 using Base
= HashPolicy
;
454 static const KeyType
& getKey(const T
& aT
) { return aT
; }
456 static void setKey(T
& aT
, KeyType
& aKey
) { HashPolicy::rekey(aT
, aKey
); }
459 using Impl
= detail::HashTable
<const T
, SetHashPolicy
, AllocPolicy
>;
462 friend class Impl::Enum
;
465 using Lookup
= typename
HashPolicy::Lookup
;
468 // -- Initialization -------------------------------------------------------
470 explicit HashSet(AllocPolicy aAllocPolicy
= AllocPolicy(),
471 uint32_t aLen
= Impl::sDefaultLen
)
472 : mImpl(std::move(aAllocPolicy
), aLen
) {}
474 explicit HashSet(uint32_t aLen
) : mImpl(AllocPolicy(), aLen
) {}
476 // HashSet is movable.
477 HashSet(HashSet
&& aRhs
) = default;
478 HashSet
& operator=(HashSet
&& aRhs
) = default;
480 // -- Status and sizing ----------------------------------------------------
482 // The set's current generation.
483 Generation
generation() const { return mImpl
.generation(); }
486 bool empty() const { return mImpl
.empty(); }
488 // Number of elements in the set.
489 uint32_t count() const { return mImpl
.count(); }
491 // Number of element slots in the set. Note: resize will happen well before
492 // count() == capacity().
493 uint32_t capacity() const { return mImpl
.capacity(); }
495 // The size of the set's entry storage, in bytes. If the elements contain
496 // pointers to other heap blocks, you must iterate over the set and measure
497 // them separately; hence the "shallow" prefix.
498 size_t shallowSizeOfExcludingThis(MallocSizeOf aMallocSizeOf
) const {
499 return mImpl
.shallowSizeOfExcludingThis(aMallocSizeOf
);
501 size_t shallowSizeOfIncludingThis(MallocSizeOf aMallocSizeOf
) const {
502 return aMallocSizeOf(this) +
503 mImpl
.shallowSizeOfExcludingThis(aMallocSizeOf
);
506 // Attempt to minimize the capacity(). If the table is empty, this will free
507 // the empty storage and upon regrowth it will be given the minimum capacity.
508 void compact() { mImpl
.compact(); }
510 // Attempt to reserve enough space to fit at least |aLen| elements. This is
511 // total capacity, including elements already present. Does nothing if the
512 // map already has sufficient capacity.
513 [[nodiscard
]] bool reserve(uint32_t aLen
) { return mImpl
.reserve(aLen
); }
515 // -- Lookups --------------------------------------------------------------
517 // Does the set contain an element matching |aLookup|?
518 bool has(const Lookup
& aLookup
) const {
519 return mImpl
.lookup(aLookup
).found();
522 // Return a Ptr indicating whether an element matching |aLookup| is present
525 // using HS = HashSet<int>;
527 // if (HS::Ptr p = h.lookup(3)) {
528 // assert(*p == 3); // p acts like a pointer to int
531 using Ptr
= typename
Impl::Ptr
;
532 MOZ_ALWAYS_INLINE Ptr
lookup(const Lookup
& aLookup
) const {
533 return mImpl
.lookup(aLookup
);
536 // Like lookup(), but does not assert if two threads call it at the same
537 // time. Only use this method when none of the threads will modify the set.
538 MOZ_ALWAYS_INLINE Ptr
readonlyThreadsafeLookup(const Lookup
& aLookup
) const {
539 return mImpl
.readonlyThreadsafeLookup(aLookup
);
542 // -- Insertions -----------------------------------------------------------
544 // Add |aU| if it is not present already. Returns false on OOM.
545 template <typename U
>
546 [[nodiscard
]] bool put(U
&& aU
) {
547 AddPtr p
= lookupForAdd(aU
);
548 return p
? true : add(p
, std::forward
<U
>(aU
));
551 // Like put(), but slightly faster. Must only be used when the given element
552 // is not already present. (In debug builds, assertions check this.)
553 template <typename U
>
554 [[nodiscard
]] bool putNew(U
&& aU
) {
555 return mImpl
.putNew(aU
, std::forward
<U
>(aU
));
558 // Like the other putNew(), but for when |Lookup| is different to |T|.
559 template <typename U
>
560 [[nodiscard
]] bool putNew(const Lookup
& aLookup
, U
&& aU
) {
561 return mImpl
.putNew(aLookup
, std::forward
<U
>(aU
));
564 // Like putNew(), but should be only used when the table is known to be big
565 // enough for the insertion, and hashing cannot fail. Typically this is used
566 // to populate an empty set with known-unique elements after reserving space
567 // with reserve(), e.g.
569 // using HS = HashMap<int>;
571 // if (!h.reserve(3)) {
574 // h.putNewInfallible(1); // unique element
575 // h.putNewInfallible(2); // unique element
576 // h.putNewInfallible(3); // unique element
578 template <typename U
>
579 void putNewInfallible(const Lookup
& aLookup
, U
&& aU
) {
580 mImpl
.putNewInfallible(aLookup
, std::forward
<U
>(aU
));
583 // Like |lookup(l)|, but on miss, |p = lookupForAdd(l)| allows efficient
584 // insertion of T value |t| (where |HashPolicy::match(t,l) == true|) using
585 // |add(p,t)|. After |add(p,t)|, |p| points to the new element. E.g.:
587 // using HS = HashSet<int>;
589 // HS::AddPtr p = h.lookupForAdd(3);
591 // if (!h.add(p, 3)) {
595 // assert(*p == 3); // p acts like a pointer to int
597 // N.B. The caller must ensure that no mutating hash table operations occur
598 // between a pair of lookupForAdd() and add() calls. To avoid looking up the
599 // key a second time, the caller may use the more efficient relookupOrAdd()
600 // method. This method reuses part of the hashing computation to more
601 // efficiently insert the key if it has not been added. For example, a
602 // mutation-handling version of the previous example:
604 // HS::AddPtr p = h.lookupForAdd(3);
606 // call_that_may_mutate_h();
607 // if (!h.relookupOrAdd(p, 3, 3)) {
613 // Note that relookupOrAdd(p,l,t) performs Lookup using |l| and adds the
614 // entry |t|, where the caller ensures match(l,t).
615 using AddPtr
= typename
Impl::AddPtr
;
616 MOZ_ALWAYS_INLINE AddPtr
lookupForAdd(const Lookup
& aLookup
) {
617 return mImpl
.lookupForAdd(aLookup
);
620 // Add an element. Returns false on OOM.
621 template <typename U
>
622 [[nodiscard
]] bool add(AddPtr
& aPtr
, U
&& aU
) {
623 return mImpl
.add(aPtr
, std::forward
<U
>(aU
));
626 // See the comment above lookupForAdd() for details.
627 template <typename U
>
628 [[nodiscard
]] bool relookupOrAdd(AddPtr
& aPtr
, const Lookup
& aLookup
,
630 return mImpl
.relookupOrAdd(aPtr
, aLookup
, std::forward
<U
>(aU
));
633 // -- Removal --------------------------------------------------------------
635 // Lookup and remove the element matching |aLookup|, if present.
636 void remove(const Lookup
& aLookup
) {
637 if (Ptr p
= lookup(aLookup
)) {
642 // Remove a previously found element (assuming aPtr.found()). The set must
643 // not have been mutated in the interim.
644 void remove(Ptr aPtr
) { mImpl
.remove(aPtr
); }
646 // Remove all keys/values without changing the capacity.
647 void clear() { mImpl
.clear(); }
649 // Like clear() followed by compact().
650 void clearAndCompact() { mImpl
.clearAndCompact(); }
652 // -- Rekeying -------------------------------------------------------------
654 // Infallibly rekey one entry, if present. Requires that template parameters
655 // T and HashPolicy::Lookup are the same type.
656 void rekeyIfMoved(const Lookup
& aOldValue
, const T
& aNewValue
) {
657 if (aOldValue
!= aNewValue
) {
658 rekeyAs(aOldValue
, aNewValue
, aNewValue
);
662 // Infallibly rekey one entry if present, and return whether that happened.
663 bool rekeyAs(const Lookup
& aOldLookup
, const Lookup
& aNewLookup
,
664 const T
& aNewValue
) {
665 if (Ptr p
= lookup(aOldLookup
)) {
666 mImpl
.rekeyAndMaybeRehash(p
, aNewLookup
, aNewValue
);
672 // Infallibly replace the current key at |aPtr| with an equivalent key.
673 // Specifically, both HashPolicy::hash and HashPolicy::match must return
674 // identical results for the new and old key when applied against all
675 // possible matching values.
676 void replaceKey(Ptr aPtr
, const Lookup
& aLookup
, const T
& aNewValue
) {
677 MOZ_ASSERT(aPtr
.found());
678 MOZ_ASSERT(*aPtr
!= aNewValue
);
679 MOZ_ASSERT(HashPolicy::match(*aPtr
, aLookup
));
680 MOZ_ASSERT(HashPolicy::match(aNewValue
, aLookup
));
681 const_cast<T
&>(*aPtr
) = aNewValue
;
682 MOZ_ASSERT(*lookup(aLookup
) == aNewValue
);
684 void replaceKey(Ptr aPtr
, const T
& aNewValue
) {
685 replaceKey(aPtr
, aNewValue
, aNewValue
);
688 // -- Iteration ------------------------------------------------------------
690 // |iter()| returns an Iterator:
693 // for (auto iter = h.iter(); !iter.done(); iter.next()) {
694 // int i = iter.get();
697 using Iterator
= typename
Impl::Iterator
;
698 Iterator
iter() const { return mImpl
.iter(); }
700 // |modIter()| returns a ModIterator:
703 // for (auto iter = h.modIter(); !iter.done(); iter.next()) {
704 // if (iter.get() == 42) {
709 // Table resize may occur in ModIterator's destructor.
710 using ModIterator
= typename
Impl::ModIterator
;
711 ModIterator
modIter() { return mImpl
.modIter(); }
713 // These are similar to Iterator/ModIterator/iter(), but use different
715 using Range
= typename
Impl::Range
;
716 using Enum
= typename
Impl::Enum
;
717 Range
all() const { return mImpl
.all(); }
720 //---------------------------------------------------------------------------
722 //---------------------------------------------------------------------------
724 // A hash policy |HP| for a hash table with key-type |Key| must provide:
726 // - a type |HP::Lookup| to use to lookup table entries;
728 // - a static member function |HP::hash| that hashes lookup values:
730 // static mozilla::HashNumber hash(const Lookup&);
732 // - a static member function |HP::match| that tests equality of key and
735 // static bool match(const Key& aKey, const Lookup& aLookup);
737 // |aKey| and |aLookup| can have different hash numbers, only when a
738 // collision happens with |prepareHash| operation, which is less frequent.
739 // Thus, |HP::match| shouldn't assume the hash equality in the comparison,
740 // even if the hash numbers are almost always same between them.
742 // Normally, Lookup = Key. In general, though, different values and types of
743 // values can be used to lookup and store. If a Lookup value |l| is not equal
744 // to the added Key value |k|, the user must ensure that |HP::match(k,l)| is
747 // mozilla::HashSet<Key, HP>::AddPtr p = h.lookup(l);
749 // assert(HP::match(k, l)); // must hold
753 // A pointer hashing policy that uses HashGeneric() to create good hashes for
754 // pointers. Note that we don't shift out the lowest k bits because we don't
755 // want to assume anything about the alignment of the pointers.
756 template <typename Key
>
757 struct PointerHasher
{
760 static HashNumber
hash(const Lookup
& aLookup
) { return HashGeneric(aLookup
); }
762 static bool match(const Key
& aKey
, const Lookup
& aLookup
) {
763 return aKey
== aLookup
;
766 static void rekey(Key
& aKey
, const Key
& aNewKey
) { aKey
= aNewKey
; }
769 // The default hash policy, which only works with integers.
770 template <class Key
, typename
>
771 struct DefaultHasher
{
774 static HashNumber
hash(const Lookup
& aLookup
) {
775 // Just convert the integer to a HashNumber and use that as is. (This
776 // discards the high 32-bits of 64-bit integers!) ScrambleHashCode() is
777 // subsequently called on the value to improve the distribution.
781 static bool match(const Key
& aKey
, const Lookup
& aLookup
) {
782 // Use builtin or overloaded operator==.
783 return aKey
== aLookup
;
786 static void rekey(Key
& aKey
, const Key
& aNewKey
) { aKey
= aNewKey
; }
789 // A DefaultHasher specialization for enums.
791 struct DefaultHasher
<T
, std::enable_if_t
<std::is_enum_v
<T
>>> {
795 static HashNumber
hash(const Lookup
& aLookup
) { return HashGeneric(aLookup
); }
797 static bool match(const Key
& aKey
, const Lookup
& aLookup
) {
798 // Use builtin or overloaded operator==.
799 return aKey
== static_cast<Key
>(aLookup
);
802 static void rekey(Key
& aKey
, const Key
& aNewKey
) { aKey
= aNewKey
; }
805 // A DefaultHasher specialization for pointers.
807 struct DefaultHasher
<T
*> : PointerHasher
<T
*> {};
809 // A DefaultHasher specialization for mozilla::UniquePtr.
810 template <class T
, class D
>
811 struct DefaultHasher
<UniquePtr
<T
, D
>> {
812 using Key
= UniquePtr
<T
, D
>;
814 using PtrHasher
= PointerHasher
<T
*>;
816 static HashNumber
hash(const Lookup
& aLookup
) {
817 return PtrHasher::hash(aLookup
.get());
820 static bool match(const Key
& aKey
, const Lookup
& aLookup
) {
821 return PtrHasher::match(aKey
.get(), aLookup
.get());
824 static void rekey(UniquePtr
<T
, D
>& aKey
, UniquePtr
<T
, D
>&& aNewKey
) {
825 aKey
= std::move(aNewKey
);
829 // A DefaultHasher specialization for doubles.
831 struct DefaultHasher
<double> {
835 static HashNumber
hash(const Lookup
& aLookup
) {
836 // Just xor the high bits with the low bits, and then treat the bits of the
837 // result as a uint32_t.
838 static_assert(sizeof(HashNumber
) == 4,
839 "subsequent code assumes a four-byte hash");
840 uint64_t u
= BitwiseCast
<uint64_t>(aLookup
);
841 return HashNumber(u
^ (u
>> 32));
844 static bool match(const Key
& aKey
, const Lookup
& aLookup
) {
845 return BitwiseCast
<uint64_t>(aKey
) == BitwiseCast
<uint64_t>(aLookup
);
849 // A DefaultHasher specialization for floats.
851 struct DefaultHasher
<float> {
855 static HashNumber
hash(const Lookup
& aLookup
) {
856 // Just use the value as if its bits form an integer. ScrambleHashCode() is
857 // subsequently called on the value to improve the distribution.
858 static_assert(sizeof(HashNumber
) == 4,
859 "subsequent code assumes a four-byte hash");
860 return HashNumber(BitwiseCast
<uint32_t>(aLookup
));
863 static bool match(const Key
& aKey
, const Lookup
& aLookup
) {
864 return BitwiseCast
<uint32_t>(aKey
) == BitwiseCast
<uint32_t>(aLookup
);
868 // A hash policy for C strings.
869 struct CStringHasher
{
870 using Key
= const char*;
871 using Lookup
= const char*;
873 static HashNumber
hash(const Lookup
& aLookup
) { return HashString(aLookup
); }
875 static bool match(const Key
& aKey
, const Lookup
& aLookup
) {
876 return strcmp(aKey
, aLookup
) == 0;
880 //---------------------------------------------------------------------------
881 // Fallible Hashing Interface
882 //---------------------------------------------------------------------------
884 // Most of the time generating a hash code is infallible, but sometimes it is
885 // necessary to generate hash codes on demand in a way that can fail. Specialize
886 // this class for your own hash policy to provide fallible hashing.
888 // This is used by MovableCellHasher to handle the fact that generating a unique
889 // ID for cell pointer may fail due to OOM.
891 // The default implementations of these methods delegate to the usual HashPolicy
892 // implementation and always succeed.
893 template <typename HashPolicy
>
894 struct FallibleHashMethods
{
895 // Return true if a hashcode is already available for its argument, and
896 // sets |aHashOut|. Once this succeeds for a specific argument it
897 // must continue to do so.
899 // Return false if a hashcode is not already available. This implies that any
900 // lookup must fail, as the hash code would have to have been successfully
901 // created on insertion.
902 template <typename Lookup
>
903 static bool maybeGetHash(Lookup
&& aLookup
, HashNumber
* aHashOut
) {
904 *aHashOut
= HashPolicy::hash(aLookup
);
908 // Fallible method to ensure a hashcode exists for its argument and create one
909 // if not. Sets |aHashOut| to the hashcode and retuns true on success. Returns
910 // false on error, e.g. out of memory.
911 template <typename Lookup
>
912 static bool ensureHash(Lookup
&& aLookup
, HashNumber
* aHashOut
) {
913 *aHashOut
= HashPolicy::hash(aLookup
);
918 template <typename HashPolicy
, typename Lookup
>
919 static bool MaybeGetHash(Lookup
&& aLookup
, HashNumber
* aHashOut
) {
920 return FallibleHashMethods
<typename
HashPolicy::Base
>::maybeGetHash(
921 std::forward
<Lookup
>(aLookup
), aHashOut
);
924 template <typename HashPolicy
, typename Lookup
>
925 static bool EnsureHash(Lookup
&& aLookup
, HashNumber
* aHashOut
) {
926 return FallibleHashMethods
<typename
HashPolicy::Base
>::ensureHash(
927 std::forward
<Lookup
>(aLookup
), aHashOut
);
930 //---------------------------------------------------------------------------
931 // Implementation Details (HashMapEntry, HashTableEntry, HashTable)
932 //---------------------------------------------------------------------------
934 // Both HashMap and HashSet are implemented by a single HashTable that is even
935 // more heavily parameterized than the other two. This leaves HashTable gnarly
936 // and extremely coupled to HashMap and HashSet; thus code should not use
937 // HashTable directly.
939 template <class Key
, class Value
>
944 template <class, class, class>
945 friend class detail::HashTable
;
947 friend class detail::HashTableEntry
;
948 template <class, class, class, class>
949 friend class HashMap
;
952 template <typename KeyInput
, typename ValueInput
>
953 HashMapEntry(KeyInput
&& aKey
, ValueInput
&& aValue
)
954 : key_(std::forward
<KeyInput
>(aKey
)),
955 value_(std::forward
<ValueInput
>(aValue
)) {}
957 HashMapEntry(HashMapEntry
&& aRhs
) = default;
958 HashMapEntry
& operator=(HashMapEntry
&& aRhs
) = default;
961 using ValueType
= Value
;
963 const Key
& key() const { return key_
; }
965 // Use this method with caution! If the key is changed such that its hash
966 // value also changes, the map will be left in an invalid state.
967 Key
& mutableKey() { return key_
; }
969 const Value
& value() const { return value_
; }
970 Value
& value() { return value_
; }
973 HashMapEntry(const HashMapEntry
&) = delete;
974 void operator=(const HashMapEntry
&) = delete;
979 template <class T
, class HashPolicy
, class AllocPolicy
>
982 template <typename T
>
985 template <typename T
>
986 class HashTableEntry
{
988 using NonConstT
= std::remove_const_t
<T
>;
990 // Instead of having a hash table entry store that looks like this:
992 // +--------+--------+--------+--------+
993 // | entry0 | entry1 | .... | entryN |
994 // +--------+--------+--------+--------+
996 // where the entries contained their cached hash code, we're going to lay out
997 // the entry store thusly:
999 // +-------+-------+-------+-------+--------+--------+--------+--------+
1000 // | hash0 | hash1 | ... | hashN | entry0 | entry1 | .... | entryN |
1001 // +-------+-------+-------+-------+--------+--------+--------+--------+
1003 // with all the cached hashes prior to the actual entries themselves.
1005 // We do this because implementing the first strategy requires us to make
1006 // HashTableEntry look roughly like:
1008 // template <typename T>
1009 // class HashTableEntry {
1010 // HashNumber mKeyHash;
1014 // The problem with this setup is that, depending on the layout of `T`, there
1015 // may be platform ABI-mandated padding between `mKeyHash` and the first
1016 // member of `T`. This ABI-mandated padding is wasted space, and can be
1017 // surprisingly common, e.g. when `T` is a single pointer on 64-bit platforms.
1018 // In such cases, we're throwing away a quarter of our entry store on padding,
1019 // which is undesirable.
1021 // The second layout above, namely:
1023 // +-------+-------+-------+-------+--------+--------+--------+--------+
1024 // | hash0 | hash1 | ... | hashN | entry0 | entry1 | .... | entryN |
1025 // +-------+-------+-------+-------+--------+--------+--------+--------+
1027 // means there is no wasted space between the hashes themselves, and no wasted
1028 // space between the entries themselves. However, we would also like there to
1029 // be no gap between the last hash and the first entry. The memory allocator
1030 // guarantees the alignment of the start of the hashes. The use of a
1031 // power-of-two capacity of at least 4 guarantees that the alignment of the
1032 // *end* of the hash array is no less than the alignment of the start.
1033 // Finally, the static_asserts here guarantee that the entries themselves
1034 // don't need to be any more aligned than the alignment of the entry store
1037 // This assertion is safe for 32-bit builds because on both Windows and Linux
1038 // (including Android), the minimum alignment for allocations larger than 8
1039 // bytes is 8 bytes, and the actual data for entries in our entry store is
1040 // guaranteed to have that alignment as well, thanks to the power-of-two
1041 // number of cached hash values stored prior to the entry data.
1043 // The allocation policy must allocate a table with at least this much
1045 static constexpr size_t kMinimumAlignment
= 8;
1047 static_assert(alignof(HashNumber
) <= kMinimumAlignment
,
1048 "[N*2 hashes, N*2 T values] allocation's alignment must be "
1049 "enough to align each hash");
1050 static_assert(alignof(NonConstT
) <= 2 * sizeof(HashNumber
),
1051 "subsequent N*2 T values must not require more than an even "
1052 "number of HashNumbers provides");
1054 static const HashNumber sFreeKey
= 0;
1055 static const HashNumber sRemovedKey
= 1;
1056 static const HashNumber sCollisionBit
= 1;
1058 alignas(NonConstT
) unsigned char mValueData
[sizeof(NonConstT
)];
1061 template <class, class, class>
1062 friend class HashTable
;
1064 friend class EntrySlot
;
1066 // Some versions of GCC treat it as a -Wstrict-aliasing violation (ergo a
1067 // -Werror compile error) to reinterpret_cast<> |mValueData| to |T*|, even
1068 // through |void*|. Placing the latter cast in these separate functions
1069 // breaks the chain such that affected GCC versions no longer warn/error.
1070 void* rawValuePtr() { return mValueData
; }
1072 static bool isLiveHash(HashNumber hash
) { return hash
> sRemovedKey
; }
1074 HashTableEntry(const HashTableEntry
&) = delete;
1075 void operator=(const HashTableEntry
&) = delete;
1077 NonConstT
* valuePtr() { return reinterpret_cast<NonConstT
*>(rawValuePtr()); }
1079 void destroyStoredT() {
1080 NonConstT
* ptr
= valuePtr();
1082 MOZ_MAKE_MEM_UNDEFINED(ptr
, sizeof(*ptr
));
1086 HashTableEntry() = default;
1088 ~HashTableEntry() { MOZ_MAKE_MEM_UNDEFINED(this, sizeof(*this)); }
1090 void destroy() { destroyStoredT(); }
1092 void swap(HashTableEntry
* aOther
, bool aIsLive
) {
1093 // This allows types to use Argument-Dependent-Lookup, and thus use a custom
1094 // std::swap, which is needed by types like JS::Heap and such.
1097 if (this == aOther
) {
1101 swap(*valuePtr(), *aOther
->valuePtr());
1103 *aOther
->valuePtr() = std::move(*valuePtr());
1108 T
& get() { return *valuePtr(); }
1110 NonConstT
& getMutable() { return *valuePtr(); }
1113 // A slot represents a cached hash value and its associated entry stored
1114 // in the hash table. These two things are not stored in contiguous memory.
1117 using NonConstT
= std::remove_const_t
<T
>;
1119 using Entry
= HashTableEntry
<T
>;
1122 HashNumber
* mKeyHash
;
1124 template <class, class, class>
1125 friend class HashTable
;
1127 EntrySlot(Entry
* aEntry
, HashNumber
* aKeyHash
)
1128 : mEntry(aEntry
), mKeyHash(aKeyHash
) {}
1131 static bool isLiveHash(HashNumber hash
) { return hash
> Entry::sRemovedKey
; }
1133 EntrySlot(const EntrySlot
&) = default;
1134 EntrySlot(EntrySlot
&& aOther
) = default;
1136 EntrySlot
& operator=(const EntrySlot
&) = default;
1137 EntrySlot
& operator=(EntrySlot
&&) = default;
1139 bool operator==(const EntrySlot
& aRhs
) const { return mEntry
== aRhs
.mEntry
; }
1141 bool operator<(const EntrySlot
& aRhs
) const { return mEntry
< aRhs
.mEntry
; }
1143 EntrySlot
& operator++() {
1149 void destroy() { mEntry
->destroy(); }
1151 void swap(EntrySlot
& aOther
) {
1152 mEntry
->swap(aOther
.mEntry
, aOther
.isLive());
1153 std::swap(*mKeyHash
, *aOther
.mKeyHash
);
1156 T
& get() const { return mEntry
->get(); }
1158 NonConstT
& getMutable() { return mEntry
->getMutable(); }
1160 bool isFree() const { return *mKeyHash
== Entry::sFreeKey
; }
1163 MOZ_ASSERT(isLive());
1164 *mKeyHash
= Entry::sFreeKey
;
1165 mEntry
->destroyStoredT();
1170 mEntry
->destroyStoredT();
1172 MOZ_MAKE_MEM_UNDEFINED(mEntry
, sizeof(*mEntry
));
1173 *mKeyHash
= Entry::sFreeKey
;
1176 bool isRemoved() const { return *mKeyHash
== Entry::sRemovedKey
; }
1179 MOZ_ASSERT(isLive());
1180 *mKeyHash
= Entry::sRemovedKey
;
1181 mEntry
->destroyStoredT();
1184 bool isLive() const { return isLiveHash(*mKeyHash
); }
1186 void setCollision() {
1187 MOZ_ASSERT(isLive());
1188 *mKeyHash
|= Entry::sCollisionBit
;
1190 void unsetCollision() { *mKeyHash
&= ~Entry::sCollisionBit
; }
1191 bool hasCollision() const { return *mKeyHash
& Entry::sCollisionBit
; }
1192 bool matchHash(HashNumber hn
) {
1193 return (*mKeyHash
& ~Entry::sCollisionBit
) == hn
;
1195 HashNumber
getKeyHash() const { return *mKeyHash
& ~Entry::sCollisionBit
; }
1197 template <typename
... Args
>
1198 void setLive(HashNumber aHashNumber
, Args
&&... aArgs
) {
1199 MOZ_ASSERT(!isLive());
1200 *mKeyHash
= aHashNumber
;
1201 new (KnownNotNull
, mEntry
->valuePtr()) T(std::forward
<Args
>(aArgs
)...);
1202 MOZ_ASSERT(isLive());
1205 Entry
* toEntry() const { return mEntry
; }
1208 template <class T
, class HashPolicy
, class AllocPolicy
>
1209 class HashTable
: private AllocPolicy
{
1210 friend class mozilla::ReentrancyGuard
;
1212 using NonConstT
= std::remove_const_t
<T
>;
1213 using Key
= typename
HashPolicy::KeyType
;
1214 using Lookup
= typename
HashPolicy::Lookup
;
1217 using Entry
= HashTableEntry
<T
>;
1218 using Slot
= EntrySlot
<T
>;
1220 template <typename F
>
1221 static void forEachSlot(char* aTable
, uint32_t aCapacity
, F
&& f
) {
1222 auto hashes
= reinterpret_cast<HashNumber
*>(aTable
);
1223 auto entries
= reinterpret_cast<Entry
*>(&hashes
[aCapacity
]);
1224 Slot
slot(entries
, hashes
);
1225 for (size_t i
= 0; i
< size_t(aCapacity
); ++i
) {
1231 // A nullable pointer to a hash table element. A Ptr |p| can be tested
1232 // either explicitly |if (p.found()) p->...| or using boolean conversion
1233 // |if (p) p->...|. Ptr objects must not be used after any mutating hash
1234 // table operations unless |generation()| is tested.
1236 friend class HashTable
;
1240 const HashTable
* mTable
;
1241 Generation mGeneration
;
1245 Ptr(Slot aSlot
, const HashTable
& aTable
)
1250 mGeneration(aTable
.generation())
1255 // This constructor is used only by AddPtr() within lookupForAdd().
1256 explicit Ptr(const HashTable
& aTable
)
1257 : mSlot(nullptr, nullptr)
1261 mGeneration(aTable
.generation())
1266 bool isValid() const { return !!mSlot
.toEntry(); }
1270 : mSlot(nullptr, nullptr)
1279 bool found() const {
1284 MOZ_ASSERT(mGeneration
== mTable
->generation());
1286 return mSlot
.isLive();
1289 explicit operator bool() const { return found(); }
1291 bool operator==(const Ptr
& aRhs
) const {
1292 MOZ_ASSERT(found() && aRhs
.found());
1293 return mSlot
== aRhs
.mSlot
;
1296 bool operator!=(const Ptr
& aRhs
) const {
1298 MOZ_ASSERT(mGeneration
== mTable
->generation());
1300 return !(*this == aRhs
);
1303 T
& operator*() const {
1305 MOZ_ASSERT(found());
1306 MOZ_ASSERT(mGeneration
== mTable
->generation());
1311 T
* operator->() const {
1313 MOZ_ASSERT(found());
1314 MOZ_ASSERT(mGeneration
== mTable
->generation());
1316 return &mSlot
.get();
1320 // A Ptr that can be used to add a key after a failed lookup.
1321 class AddPtr
: public Ptr
{
1322 friend class HashTable
;
1324 HashNumber mKeyHash
;
1326 uint64_t mMutationCount
;
1329 AddPtr(Slot aSlot
, const HashTable
& aTable
, HashNumber aHashNumber
)
1330 : Ptr(aSlot
, aTable
),
1331 mKeyHash(aHashNumber
)
1334 mMutationCount(aTable
.mMutationCount
)
1339 // This constructor is used when lookupForAdd() is performed on a table
1340 // lacking entry storage; it leaves mSlot null but initializes everything
1342 AddPtr(const HashTable
& aTable
, HashNumber aHashNumber
)
1344 mKeyHash(aHashNumber
)
1347 mMutationCount(aTable
.mMutationCount
)
1350 MOZ_ASSERT(isLive());
1353 bool isLive() const { return isLiveHash(mKeyHash
); }
1356 AddPtr() : mKeyHash(0) {}
1359 // A hash table iterator that (mostly) doesn't allow table modifications.
1360 // As with Ptr/AddPtr, Iterator objects must not be used after any mutating
1361 // hash table operation unless the |generation()| is tested.
1363 void moveToNextLiveEntry() {
1364 while (++mCur
< mEnd
&& !mCur
.isLive()) {
1370 friend class HashTable
;
1372 explicit Iterator(const HashTable
& aTable
)
1373 : mCur(aTable
.slotForIndex(0)),
1374 mEnd(aTable
.slotForIndex(aTable
.capacity()))
1378 mMutationCount(aTable
.mMutationCount
),
1379 mGeneration(aTable
.generation()),
1383 if (!done() && !mCur
.isLive()) {
1384 moveToNextLiveEntry();
1391 const HashTable
& mTable
;
1392 uint64_t mMutationCount
;
1393 Generation mGeneration
;
1399 MOZ_ASSERT(mGeneration
== mTable
.generation());
1400 MOZ_ASSERT(mMutationCount
== mTable
.mMutationCount
);
1401 return mCur
== mEnd
;
1405 MOZ_ASSERT(!done());
1406 MOZ_ASSERT(mValidEntry
);
1407 MOZ_ASSERT(mGeneration
== mTable
.generation());
1408 MOZ_ASSERT(mMutationCount
== mTable
.mMutationCount
);
1413 MOZ_ASSERT(!done());
1414 MOZ_ASSERT(mGeneration
== mTable
.generation());
1415 MOZ_ASSERT(mMutationCount
== mTable
.mMutationCount
);
1416 moveToNextLiveEntry();
1423 // A hash table iterator that permits modification, removal and rekeying.
1424 // Since rehashing when elements were removed during enumeration would be
1425 // bad, it is postponed until the ModIterator is destructed. Since the
1426 // ModIterator's destructor touches the hash table, the user must ensure
1427 // that the hash table is still alive when the destructor runs.
1428 class ModIterator
: public Iterator
{
1429 friend class HashTable
;
1435 // ModIterator is movable but not copyable.
1436 ModIterator(const ModIterator
&) = delete;
1437 void operator=(const ModIterator
&) = delete;
1440 explicit ModIterator(HashTable
& aTable
)
1441 : Iterator(aTable
), mTable(aTable
), mRekeyed(false), mRemoved(false) {}
1444 MOZ_IMPLICIT
ModIterator(ModIterator
&& aOther
)
1446 mTable(aOther
.mTable
),
1447 mRekeyed(aOther
.mRekeyed
),
1448 mRemoved(aOther
.mRemoved
) {
1449 aOther
.mRekeyed
= false;
1450 aOther
.mRemoved
= false;
1453 // Removes the current element from the table, leaving |get()|
1454 // invalid until the next call to |next()|.
1456 mTable
.remove(this->mCur
);
1459 this->mValidEntry
= false;
1460 this->mMutationCount
= mTable
.mMutationCount
;
1464 NonConstT
& getMutable() {
1465 MOZ_ASSERT(!this->done());
1466 MOZ_ASSERT(this->mValidEntry
);
1467 MOZ_ASSERT(this->mGeneration
== this->Iterator::mTable
.generation());
1468 MOZ_ASSERT(this->mMutationCount
== this->Iterator::mTable
.mMutationCount
);
1469 return this->mCur
.getMutable();
1472 // Removes the current element and re-inserts it into the table with
1473 // a new key at the new Lookup position. |get()| is invalid after
1474 // this operation until the next call to |next()|.
1475 void rekey(const Lookup
& l
, const Key
& k
) {
1476 MOZ_ASSERT(&k
!= &HashPolicy::getKey(this->mCur
.get()));
1477 Ptr
p(this->mCur
, mTable
);
1478 mTable
.rekeyWithoutRehash(p
, l
, k
);
1481 this->mValidEntry
= false;
1482 this->mMutationCount
= mTable
.mMutationCount
;
1486 void rekey(const Key
& k
) { rekey(k
, k
); }
1488 // Potentially rehashes the table.
1492 mTable
.infallibleRehashIfOverloaded();
1501 // Range is similar to Iterator, but uses different terminology.
1503 friend class HashTable
;
1508 explicit Range(const HashTable
& table
) : mIter(table
) {}
1511 bool empty() const { return mIter
.done(); }
1513 T
& front() const { return mIter
.get(); }
1515 void popFront() { return mIter
.next(); }
1518 // Enum is similar to ModIterator, but uses different terminology.
1522 // Enum is movable but not copyable.
1523 Enum(const Enum
&) = delete;
1524 void operator=(const Enum
&) = delete;
1527 template <class Map
>
1528 explicit Enum(Map
& map
) : mIter(map
.mImpl
) {}
1530 MOZ_IMPLICIT
Enum(Enum
&& other
) : mIter(std::move(other
.mIter
)) {}
1532 bool empty() const { return mIter
.done(); }
1534 T
& front() const { return mIter
.get(); }
1536 void popFront() { return mIter
.next(); }
1538 void removeFront() { mIter
.remove(); }
1540 NonConstT
& mutableFront() { return mIter
.getMutable(); }
1542 void rekeyFront(const Lookup
& aLookup
, const Key
& aKey
) {
1543 mIter
.rekey(aLookup
, aKey
);
1546 void rekeyFront(const Key
& aKey
) { mIter
.rekey(aKey
); }
1549 // HashTable is movable
1550 HashTable(HashTable
&& aRhs
) : AllocPolicy(std::move(aRhs
)) { moveFrom(aRhs
); }
1551 HashTable
& operator=(HashTable
&& aRhs
) {
1552 MOZ_ASSERT(this != &aRhs
, "self-move assignment is prohibited");
1554 destroyTable(*this, mTable
, capacity());
1556 AllocPolicy::operator=(std::move(aRhs
));
1562 void moveFrom(HashTable
& aRhs
) {
1564 mHashShift
= aRhs
.mHashShift
;
1565 mTable
= aRhs
.mTable
;
1566 mEntryCount
= aRhs
.mEntryCount
;
1567 mRemovedCount
= aRhs
.mRemovedCount
;
1569 mMutationCount
= aRhs
.mMutationCount
;
1570 mEntered
= aRhs
.mEntered
;
1572 aRhs
.mTable
= nullptr;
1573 aRhs
.clearAndCompact();
1576 // HashTable is not copyable or assignable
1577 HashTable(const HashTable
&) = delete;
1578 void operator=(const HashTable
&) = delete;
1580 static const uint32_t CAP_BITS
= 30;
1583 uint64_t mGen
: 56; // entry storage generation number
1584 uint64_t mHashShift
: 8; // multiplicative hash shift
1585 char* mTable
; // entry storage
1586 uint32_t mEntryCount
; // number of entries in mTable
1587 uint32_t mRemovedCount
; // removed entry sentinels in mTable
1590 uint64_t mMutationCount
;
1591 mutable bool mEntered
;
1594 // The default initial capacity is 32 (enough to hold 16 elements), but it
1595 // can be as low as 4.
1596 static const uint32_t sDefaultLen
= 16;
1597 static const uint32_t sMinCapacity
= 4;
1598 // See the comments in HashTableEntry about this value.
1599 static_assert(sMinCapacity
>= 4, "too-small sMinCapacity breaks assumptions");
1600 static const uint32_t sMaxInit
= 1u << (CAP_BITS
- 1);
1601 static const uint32_t sMaxCapacity
= 1u << CAP_BITS
;
1603 // Hash-table alpha is conceptually a fraction, but to avoid floating-point
1604 // math we implement it as a ratio of integers.
1605 static const uint8_t sAlphaDenominator
= 4;
1606 static const uint8_t sMinAlphaNumerator
= 1; // min alpha: 1/4
1607 static const uint8_t sMaxAlphaNumerator
= 3; // max alpha: 3/4
1609 static const HashNumber sFreeKey
= Entry::sFreeKey
;
1610 static const HashNumber sRemovedKey
= Entry::sRemovedKey
;
1611 static const HashNumber sCollisionBit
= Entry::sCollisionBit
;
1613 static uint32_t bestCapacity(uint32_t aLen
) {
1615 (sMaxInit
* sAlphaDenominator
) / sAlphaDenominator
== sMaxInit
,
1616 "multiplication in numerator below could overflow");
1618 sMaxInit
* sAlphaDenominator
<= UINT32_MAX
- sMaxAlphaNumerator
,
1619 "numerator calculation below could potentially overflow");
1621 // Callers should ensure this is true.
1622 MOZ_ASSERT(aLen
<= sMaxInit
);
1624 // Compute the smallest capacity allowing |aLen| elements to be
1625 // inserted without rehashing: ceil(aLen / max-alpha). (Ceiling
1626 // integral division: <http://stackoverflow.com/a/2745086>.)
1627 uint32_t capacity
= (aLen
* sAlphaDenominator
+ sMaxAlphaNumerator
- 1) /
1629 capacity
= (capacity
< sMinCapacity
) ? sMinCapacity
: RoundUpPow2(capacity
);
1631 MOZ_ASSERT(capacity
>= aLen
);
1632 MOZ_ASSERT(capacity
<= sMaxCapacity
);
1637 static uint32_t hashShift(uint32_t aLen
) {
1638 // Reject all lengths whose initial computed capacity would exceed
1639 // sMaxCapacity. Round that maximum aLen down to the nearest power of two
1640 // for speedier code.
1641 if (MOZ_UNLIKELY(aLen
> sMaxInit
)) {
1642 MOZ_CRASH("initial length is too large");
1645 return kHashNumberBits
- mozilla::CeilingLog2(bestCapacity(aLen
));
1648 static bool isLiveHash(HashNumber aHash
) { return Entry::isLiveHash(aHash
); }
1650 static HashNumber
prepareHash(HashNumber aInputHash
) {
1651 HashNumber keyHash
= ScrambleHashCode(aInputHash
);
1653 // Avoid reserved hash codes.
1654 if (!isLiveHash(keyHash
)) {
1655 keyHash
-= (sRemovedKey
+ 1);
1657 return keyHash
& ~sCollisionBit
;
1660 enum FailureBehavior
{ DontReportFailure
= false, ReportFailure
= true };
1662 // Fake a struct that we're going to alloc. See the comments in
1663 // HashTableEntry about how the table is laid out, and why it's safe.
1665 unsigned char c
[sizeof(HashNumber
) + sizeof(typename
Entry::NonConstT
)];
1668 static char* createTable(AllocPolicy
& aAllocPolicy
, uint32_t aCapacity
,
1669 FailureBehavior aReportFailure
= ReportFailure
) {
1672 ? aAllocPolicy
.template pod_malloc
<FakeSlot
>(aCapacity
)
1673 : aAllocPolicy
.template maybe_pod_malloc
<FakeSlot
>(aCapacity
);
1675 MOZ_ASSERT((reinterpret_cast<uintptr_t>(fake
) % Entry::kMinimumAlignment
) ==
1678 char* table
= reinterpret_cast<char*>(fake
);
1680 forEachSlot(table
, aCapacity
, [&](Slot
& slot
) {
1681 *slot
.mKeyHash
= sFreeKey
;
1682 new (KnownNotNull
, slot
.toEntry()) Entry();
1688 static void destroyTable(AllocPolicy
& aAllocPolicy
, char* aOldTable
,
1689 uint32_t aCapacity
) {
1690 forEachSlot(aOldTable
, aCapacity
, [&](const Slot
& slot
) {
1691 if (slot
.isLive()) {
1692 slot
.toEntry()->destroyStoredT();
1695 freeTable(aAllocPolicy
, aOldTable
, aCapacity
);
1698 static void freeTable(AllocPolicy
& aAllocPolicy
, char* aOldTable
,
1699 uint32_t aCapacity
) {
1700 FakeSlot
* fake
= reinterpret_cast<FakeSlot
*>(aOldTable
);
1701 aAllocPolicy
.free_(fake
, aCapacity
);
1705 HashTable(AllocPolicy aAllocPolicy
, uint32_t aLen
)
1706 : AllocPolicy(std::move(aAllocPolicy
)),
1708 mHashShift(hashShift(aLen
)),
1720 explicit HashTable(AllocPolicy aAllocPolicy
)
1721 : HashTable(aAllocPolicy
, sDefaultLen
) {}
1725 destroyTable(*this, mTable
, capacity());
1730 HashNumber
hash1(HashNumber aHash0
) const { return aHash0
>> mHashShift
; }
1734 HashNumber mSizeMask
;
1737 DoubleHash
hash2(HashNumber aCurKeyHash
) const {
1738 uint32_t sizeLog2
= kHashNumberBits
- mHashShift
;
1739 DoubleHash dh
= {((aCurKeyHash
<< sizeLog2
) >> mHashShift
) | 1,
1740 (HashNumber(1) << sizeLog2
) - 1};
1744 static HashNumber
applyDoubleHash(HashNumber aHash1
,
1745 const DoubleHash
& aDoubleHash
) {
1746 return WrappingSubtract(aHash1
, aDoubleHash
.mHash2
) & aDoubleHash
.mSizeMask
;
1749 static MOZ_ALWAYS_INLINE
bool match(T
& aEntry
, const Lookup
& aLookup
) {
1750 return HashPolicy::match(HashPolicy::getKey(aEntry
), aLookup
);
1753 enum LookupReason
{ ForNonAdd
, ForAdd
};
1755 Slot
slotForIndex(HashNumber aIndex
) const {
1756 auto hashes
= reinterpret_cast<HashNumber
*>(mTable
);
1757 auto entries
= reinterpret_cast<Entry
*>(&hashes
[capacity()]);
1758 return Slot(&entries
[aIndex
], &hashes
[aIndex
]);
1761 // Warning: in order for readonlyThreadsafeLookup() to be safe this
1762 // function must not modify the table in any way when Reason==ForNonAdd.
1763 template <LookupReason Reason
>
1764 MOZ_ALWAYS_INLINE Slot
lookup(const Lookup
& aLookup
,
1765 HashNumber aKeyHash
) const {
1766 MOZ_ASSERT(isLiveHash(aKeyHash
));
1767 MOZ_ASSERT(!(aKeyHash
& sCollisionBit
));
1770 // Compute the primary hash address.
1771 HashNumber h1
= hash1(aKeyHash
);
1772 Slot slot
= slotForIndex(h1
);
1774 // Miss: return space for a new entry.
1775 if (slot
.isFree()) {
1779 // Hit: return entry.
1780 if (slot
.matchHash(aKeyHash
) && match(slot
.get(), aLookup
)) {
1784 // Collision: double hash.
1785 DoubleHash dh
= hash2(aKeyHash
);
1787 // Save the first removed entry pointer so we can recycle later.
1788 Maybe
<Slot
> firstRemoved
;
1791 if (Reason
== ForAdd
&& !firstRemoved
) {
1792 if (MOZ_UNLIKELY(slot
.isRemoved())) {
1793 firstRemoved
.emplace(slot
);
1795 slot
.setCollision();
1799 h1
= applyDoubleHash(h1
, dh
);
1801 slot
= slotForIndex(h1
);
1802 if (slot
.isFree()) {
1803 return firstRemoved
.refOr(slot
);
1806 if (slot
.matchHash(aKeyHash
) && match(slot
.get(), aLookup
)) {
1812 // This is a copy of lookup() hardcoded to the assumptions:
1813 // 1. the lookup is for an add;
1814 // 2. the key, whose |keyHash| has been passed, is not in the table.
1815 Slot
findNonLiveSlot(HashNumber aKeyHash
) {
1816 MOZ_ASSERT(!(aKeyHash
& sCollisionBit
));
1819 // We assume 'aKeyHash' has already been distributed.
1821 // Compute the primary hash address.
1822 HashNumber h1
= hash1(aKeyHash
);
1823 Slot slot
= slotForIndex(h1
);
1825 // Miss: return space for a new entry.
1826 if (!slot
.isLive()) {
1830 // Collision: double hash.
1831 DoubleHash dh
= hash2(aKeyHash
);
1834 slot
.setCollision();
1836 h1
= applyDoubleHash(h1
, dh
);
1838 slot
= slotForIndex(h1
);
1839 if (!slot
.isLive()) {
1845 enum RebuildStatus
{ NotOverloaded
, Rehashed
, RehashFailed
};
1847 RebuildStatus
changeTableSize(
1848 uint32_t newCapacity
, FailureBehavior aReportFailure
= ReportFailure
) {
1849 MOZ_ASSERT(IsPowerOfTwo(newCapacity
));
1850 MOZ_ASSERT(!!mTable
== !!capacity());
1852 // Look, but don't touch, until we succeed in getting new entry store.
1853 char* oldTable
= mTable
;
1854 uint32_t oldCapacity
= capacity();
1855 uint32_t newLog2
= mozilla::CeilingLog2(newCapacity
);
1857 if (MOZ_UNLIKELY(newCapacity
> sMaxCapacity
)) {
1858 if (aReportFailure
) {
1859 this->reportAllocOverflow();
1861 return RehashFailed
;
1864 char* newTable
= createTable(*this, newCapacity
, aReportFailure
);
1866 return RehashFailed
;
1869 // We can't fail from here on, so update table parameters.
1870 mHashShift
= kHashNumberBits
- newLog2
;
1875 // Copy only live entries, leaving removed ones behind.
1876 forEachSlot(oldTable
, oldCapacity
, [&](Slot
& slot
) {
1877 if (slot
.isLive()) {
1878 HashNumber hn
= slot
.getKeyHash();
1879 findNonLiveSlot(hn
).setLive(
1880 hn
, std::move(const_cast<typename
Entry::NonConstT
&>(slot
.get())));
1886 // All entries have been destroyed, no need to destroyTable.
1887 freeTable(*this, oldTable
, oldCapacity
);
1891 RebuildStatus
rehashIfOverloaded(
1892 FailureBehavior aReportFailure
= ReportFailure
) {
1893 static_assert(sMaxCapacity
<= UINT32_MAX
/ sMaxAlphaNumerator
,
1894 "multiplication below could overflow");
1896 // Note: if capacity() is zero, this will always succeed, which is
1898 bool overloaded
= mEntryCount
+ mRemovedCount
>=
1899 capacity() * sMaxAlphaNumerator
/ sAlphaDenominator
;
1902 return NotOverloaded
;
1905 // Succeed if a quarter or more of all entries are removed. Note that this
1906 // always succeeds if capacity() == 0 (i.e. entry storage has not been
1907 // allocated), which is what we want, because it means changeTableSize()
1908 // will allocate the requested capacity rather than doubling it.
1909 bool manyRemoved
= mRemovedCount
>= (capacity() >> 2);
1910 uint32_t newCapacity
= manyRemoved
? rawCapacity() : rawCapacity() * 2;
1911 return changeTableSize(newCapacity
, aReportFailure
);
1914 void infallibleRehashIfOverloaded() {
1915 if (rehashIfOverloaded(DontReportFailure
) == RehashFailed
) {
1916 rehashTableInPlace();
1920 void remove(Slot
& aSlot
) {
1923 if (aSlot
.hasCollision()) {
1935 void shrinkIfUnderloaded() {
1936 static_assert(sMaxCapacity
<= UINT32_MAX
/ sMinAlphaNumerator
,
1937 "multiplication below could overflow");
1939 capacity() > sMinCapacity
&&
1940 mEntryCount
<= capacity() * sMinAlphaNumerator
/ sAlphaDenominator
;
1943 (void)changeTableSize(capacity() / 2, DontReportFailure
);
1947 // This is identical to changeTableSize(currentSize), but without requiring
1948 // a second table. We do this by recycling the collision bits to tell us if
1949 // the element is already inserted or still waiting to be inserted. Since
1950 // already-inserted elements win any conflicts, we get the same table as we
1951 // would have gotten through random insertion order.
1952 void rehashTableInPlace() {
1955 forEachSlot(mTable
, capacity(), [&](Slot
& slot
) { slot
.unsetCollision(); });
1956 for (uint32_t i
= 0; i
< capacity();) {
1957 Slot src
= slotForIndex(i
);
1959 if (!src
.isLive() || src
.hasCollision()) {
1964 HashNumber keyHash
= src
.getKeyHash();
1965 HashNumber h1
= hash1(keyHash
);
1966 DoubleHash dh
= hash2(keyHash
);
1967 Slot tgt
= slotForIndex(h1
);
1969 if (!tgt
.hasCollision()) {
1975 h1
= applyDoubleHash(h1
, dh
);
1976 tgt
= slotForIndex(h1
);
1980 // TODO: this algorithm leaves collision bits on *all* elements, even if
1981 // they are on no collision path. We have the option of setting the
1982 // collision bits correctly on a subsequent pass or skipping the rehash
1983 // unless we are totally filled with tombstones: benchmark to find out
1984 // which approach is best.
1987 // Prefer to use putNewInfallible; this function does not check
1989 template <typename
... Args
>
1990 void putNewInfallibleInternal(HashNumber aKeyHash
, Args
&&... aArgs
) {
1993 Slot slot
= findNonLiveSlot(aKeyHash
);
1995 if (slot
.isRemoved()) {
1997 aKeyHash
|= sCollisionBit
;
2000 slot
.setLive(aKeyHash
, std::forward
<Args
>(aArgs
)...);
2009 forEachSlot(mTable
, capacity(), [&](Slot
& slot
) { slot
.clear(); });
2017 // Resize the table down to the smallest capacity that doesn't overload the
2018 // table. Since we call shrinkIfUnderloaded() on every remove, you only need
2019 // to call this after a bulk removal of items done without calling remove().
2022 // Free the entry storage.
2023 freeTable(*this, mTable
, capacity());
2025 mHashShift
= hashShift(0); // gives minimum capacity on regrowth
2031 uint32_t bestCapacity
= this->bestCapacity(mEntryCount
);
2032 MOZ_ASSERT(bestCapacity
<= capacity());
2034 if (bestCapacity
< capacity()) {
2035 (void)changeTableSize(bestCapacity
, DontReportFailure
);
2039 void clearAndCompact() {
2044 [[nodiscard
]] bool reserve(uint32_t aLen
) {
2049 if (MOZ_UNLIKELY(aLen
> sMaxInit
)) {
2050 this->reportAllocOverflow();
2054 uint32_t bestCapacity
= this->bestCapacity(aLen
);
2055 if (bestCapacity
<= capacity()) {
2056 return true; // Capacity is already sufficient.
2059 RebuildStatus status
= changeTableSize(bestCapacity
, ReportFailure
);
2060 MOZ_ASSERT(status
!= NotOverloaded
);
2061 return status
!= RehashFailed
;
2064 Iterator
iter() const { return Iterator(*this); }
2066 ModIterator
modIter() { return ModIterator(*this); }
2068 Range
all() const { return Range(*this); }
2070 bool empty() const { return mEntryCount
== 0; }
2072 uint32_t count() const { return mEntryCount
; }
2074 uint32_t rawCapacity() const { return 1u << (kHashNumberBits
- mHashShift
); }
2076 uint32_t capacity() const { return mTable
? rawCapacity() : 0; }
2078 Generation
generation() const { return Generation(mGen
); }
2080 size_t shallowSizeOfExcludingThis(MallocSizeOf aMallocSizeOf
) const {
2081 return aMallocSizeOf(mTable
);
2084 size_t shallowSizeOfIncludingThis(MallocSizeOf aMallocSizeOf
) const {
2085 return aMallocSizeOf(this) + shallowSizeOfExcludingThis(aMallocSizeOf
);
2088 MOZ_ALWAYS_INLINE Ptr
readonlyThreadsafeLookup(const Lookup
& aLookup
) const {
2093 HashNumber inputHash
;
2094 if (!MaybeGetHash
<HashPolicy
>(aLookup
, &inputHash
)) {
2098 HashNumber keyHash
= prepareHash(inputHash
);
2099 return Ptr(lookup
<ForNonAdd
>(aLookup
, keyHash
), *this);
2102 MOZ_ALWAYS_INLINE Ptr
lookup(const Lookup
& aLookup
) const {
2103 ReentrancyGuard
g(*this);
2104 return readonlyThreadsafeLookup(aLookup
);
2107 MOZ_ALWAYS_INLINE AddPtr
lookupForAdd(const Lookup
& aLookup
) {
2108 ReentrancyGuard
g(*this);
2110 HashNumber inputHash
;
2111 if (!EnsureHash
<HashPolicy
>(aLookup
, &inputHash
)) {
2115 HashNumber keyHash
= prepareHash(inputHash
);
2118 return AddPtr(*this, keyHash
);
2121 // Directly call the constructor in the return statement to avoid
2122 // excess copying when building with Visual Studio 2017.
2124 return AddPtr(lookup
<ForAdd
>(aLookup
, keyHash
), *this, keyHash
);
2127 template <typename
... Args
>
2128 [[nodiscard
]] bool add(AddPtr
& aPtr
, Args
&&... aArgs
) {
2129 ReentrancyGuard
g(*this);
2130 MOZ_ASSERT_IF(aPtr
.isValid(), mTable
);
2131 MOZ_ASSERT_IF(aPtr
.isValid(), aPtr
.mTable
== this);
2132 MOZ_ASSERT(!aPtr
.found());
2133 MOZ_ASSERT(!(aPtr
.mKeyHash
& sCollisionBit
));
2135 // Check for error from ensureHash() here.
2136 if (!aPtr
.isLive()) {
2140 MOZ_ASSERT(aPtr
.mGeneration
== generation());
2142 MOZ_ASSERT(aPtr
.mMutationCount
== mMutationCount
);
2145 if (!aPtr
.isValid()) {
2146 MOZ_ASSERT(!mTable
&& mEntryCount
== 0);
2147 uint32_t newCapacity
= rawCapacity();
2148 RebuildStatus status
= changeTableSize(newCapacity
, ReportFailure
);
2149 MOZ_ASSERT(status
!= NotOverloaded
);
2150 if (status
== RehashFailed
) {
2153 aPtr
.mSlot
= findNonLiveSlot(aPtr
.mKeyHash
);
2155 } else if (aPtr
.mSlot
.isRemoved()) {
2156 // Changing an entry from removed to live does not affect whether we are
2157 // overloaded and can be handled separately.
2158 if (!this->checkSimulatedOOM()) {
2162 aPtr
.mKeyHash
|= sCollisionBit
;
2165 // Preserve the validity of |aPtr.mSlot|.
2166 RebuildStatus status
= rehashIfOverloaded();
2167 if (status
== RehashFailed
) {
2170 if (status
== NotOverloaded
&& !this->checkSimulatedOOM()) {
2173 if (status
== Rehashed
) {
2174 aPtr
.mSlot
= findNonLiveSlot(aPtr
.mKeyHash
);
2178 aPtr
.mSlot
.setLive(aPtr
.mKeyHash
, std::forward
<Args
>(aArgs
)...);
2182 aPtr
.mGeneration
= generation();
2183 aPtr
.mMutationCount
= mMutationCount
;
2188 // Note: |aLookup| may reference pieces of arguments in |aArgs|, so this
2189 // function must take care not to use |aLookup| after moving |aArgs|.
2190 template <typename
... Args
>
2191 void putNewInfallible(const Lookup
& aLookup
, Args
&&... aArgs
) {
2192 MOZ_ASSERT(!lookup(aLookup
).found());
2193 ReentrancyGuard
g(*this);
2194 HashNumber keyHash
= prepareHash(HashPolicy::hash(aLookup
));
2195 putNewInfallibleInternal(keyHash
, std::forward
<Args
>(aArgs
)...);
2198 // Note: |aLookup| may alias arguments in |aArgs|, so this function must take
2199 // care not to use |aLookup| after moving |aArgs|.
2200 template <typename
... Args
>
2201 [[nodiscard
]] bool putNew(const Lookup
& aLookup
, Args
&&... aArgs
) {
2202 MOZ_ASSERT(!lookup(aLookup
).found());
2203 ReentrancyGuard
g(*this);
2204 if (!this->checkSimulatedOOM()) {
2207 HashNumber inputHash
;
2208 if (!EnsureHash
<HashPolicy
>(aLookup
, &inputHash
)) {
2211 HashNumber keyHash
= prepareHash(inputHash
);
2212 if (rehashIfOverloaded() == RehashFailed
) {
2215 putNewInfallibleInternal(keyHash
, std::forward
<Args
>(aArgs
)...);
2219 // Note: |aLookup| may be a reference pieces of arguments in |aArgs|, so this
2220 // function must take care not to use |aLookup| after moving |aArgs|.
2221 template <typename
... Args
>
2222 [[nodiscard
]] bool relookupOrAdd(AddPtr
& aPtr
, const Lookup
& aLookup
,
2224 // Check for error from ensureHash() here.
2225 if (!aPtr
.isLive()) {
2229 aPtr
.mGeneration
= generation();
2230 aPtr
.mMutationCount
= mMutationCount
;
2233 ReentrancyGuard
g(*this);
2234 // Check that aLookup has not been destroyed.
2235 MOZ_ASSERT(prepareHash(HashPolicy::hash(aLookup
)) == aPtr
.mKeyHash
);
2236 aPtr
.mSlot
= lookup
<ForAdd
>(aLookup
, aPtr
.mKeyHash
);
2241 // Clear aPtr so it's invalid; add() will allocate storage and redo the
2243 aPtr
.mSlot
= Slot(nullptr, nullptr);
2245 return add(aPtr
, std::forward
<Args
>(aArgs
)...);
2248 void remove(Ptr aPtr
) {
2250 ReentrancyGuard
g(*this);
2251 MOZ_ASSERT(aPtr
.found());
2252 MOZ_ASSERT(aPtr
.mGeneration
== generation());
2254 shrinkIfUnderloaded();
2257 void rekeyWithoutRehash(Ptr aPtr
, const Lookup
& aLookup
, const Key
& aKey
) {
2259 ReentrancyGuard
g(*this);
2260 MOZ_ASSERT(aPtr
.found());
2261 MOZ_ASSERT(aPtr
.mGeneration
== generation());
2262 typename HashTableEntry
<T
>::NonConstT
t(std::move(*aPtr
));
2263 HashPolicy::setKey(t
, const_cast<Key
&>(aKey
));
2265 HashNumber keyHash
= prepareHash(HashPolicy::hash(aLookup
));
2266 putNewInfallibleInternal(keyHash
, std::move(t
));
2269 void rekeyAndMaybeRehash(Ptr aPtr
, const Lookup
& aLookup
, const Key
& aKey
) {
2270 rekeyWithoutRehash(aPtr
, aLookup
, aKey
);
2271 infallibleRehashIfOverloaded();
2275 } // namespace detail
2276 } // namespace mozilla
2278 #endif /* mozilla_HashTable_h */