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&, const Lookup&);
737 // Normally, Lookup = Key. In general, though, different values and types of
738 // values can be used to lookup and store. If a Lookup value |l| is not equal
739 // to the added Key value |k|, the user must ensure that |HP::match(k,l)| is
742 // mozilla::HashSet<Key, HP>::AddPtr p = h.lookup(l);
744 // assert(HP::match(k, l)); // must hold
748 // A pointer hashing policy that uses HashGeneric() to create good hashes for
749 // pointers. Note that we don't shift out the lowest k bits because we don't
750 // want to assume anything about the alignment of the pointers.
751 template <typename Key
>
752 struct PointerHasher
{
755 static HashNumber
hash(const Lookup
& aLookup
) { return HashGeneric(aLookup
); }
757 static bool match(const Key
& aKey
, const Lookup
& aLookup
) {
758 return aKey
== aLookup
;
761 static void rekey(Key
& aKey
, const Key
& aNewKey
) { aKey
= aNewKey
; }
764 // The default hash policy, which only works with integers.
765 template <class Key
, typename
>
766 struct DefaultHasher
{
769 static HashNumber
hash(const Lookup
& aLookup
) {
770 // Just convert the integer to a HashNumber and use that as is. (This
771 // discards the high 32-bits of 64-bit integers!) ScrambleHashCode() is
772 // subsequently called on the value to improve the distribution.
776 static bool match(const Key
& aKey
, const Lookup
& aLookup
) {
777 // Use builtin or overloaded operator==.
778 return aKey
== aLookup
;
781 static void rekey(Key
& aKey
, const Key
& aNewKey
) { aKey
= aNewKey
; }
784 // A DefaultHasher specialization for enums.
786 struct DefaultHasher
<T
, std::enable_if_t
<std::is_enum_v
<T
>>> {
790 static HashNumber
hash(const Lookup
& aLookup
) { return HashGeneric(aLookup
); }
792 static bool match(const Key
& aKey
, const Lookup
& aLookup
) {
793 // Use builtin or overloaded operator==.
794 return aKey
== static_cast<Key
>(aLookup
);
797 static void rekey(Key
& aKey
, const Key
& aNewKey
) { aKey
= aNewKey
; }
800 // A DefaultHasher specialization for pointers.
802 struct DefaultHasher
<T
*> : PointerHasher
<T
*> {};
804 // A DefaultHasher specialization for mozilla::UniquePtr.
805 template <class T
, class D
>
806 struct DefaultHasher
<UniquePtr
<T
, D
>> {
807 using Key
= UniquePtr
<T
, D
>;
809 using PtrHasher
= PointerHasher
<T
*>;
811 static HashNumber
hash(const Lookup
& aLookup
) {
812 return PtrHasher::hash(aLookup
.get());
815 static bool match(const Key
& aKey
, const Lookup
& aLookup
) {
816 return PtrHasher::match(aKey
.get(), aLookup
.get());
819 static void rekey(UniquePtr
<T
, D
>& aKey
, UniquePtr
<T
, D
>&& aNewKey
) {
820 aKey
= std::move(aNewKey
);
824 // A DefaultHasher specialization for doubles.
826 struct DefaultHasher
<double> {
830 static HashNumber
hash(const Lookup
& aLookup
) {
831 // Just xor the high bits with the low bits, and then treat the bits of the
832 // result as a uint32_t.
833 static_assert(sizeof(HashNumber
) == 4,
834 "subsequent code assumes a four-byte hash");
835 uint64_t u
= BitwiseCast
<uint64_t>(aLookup
);
836 return HashNumber(u
^ (u
>> 32));
839 static bool match(const Key
& aKey
, const Lookup
& aLookup
) {
840 return BitwiseCast
<uint64_t>(aKey
) == BitwiseCast
<uint64_t>(aLookup
);
844 // A DefaultHasher specialization for floats.
846 struct DefaultHasher
<float> {
850 static HashNumber
hash(const Lookup
& aLookup
) {
851 // Just use the value as if its bits form an integer. ScrambleHashCode() is
852 // subsequently called on the value to improve the distribution.
853 static_assert(sizeof(HashNumber
) == 4,
854 "subsequent code assumes a four-byte hash");
855 return HashNumber(BitwiseCast
<uint32_t>(aLookup
));
858 static bool match(const Key
& aKey
, const Lookup
& aLookup
) {
859 return BitwiseCast
<uint32_t>(aKey
) == BitwiseCast
<uint32_t>(aLookup
);
863 // A hash policy for C strings.
864 struct CStringHasher
{
865 using Key
= const char*;
866 using Lookup
= const char*;
868 static HashNumber
hash(const Lookup
& aLookup
) { return HashString(aLookup
); }
870 static bool match(const Key
& aKey
, const Lookup
& aLookup
) {
871 return strcmp(aKey
, aLookup
) == 0;
875 //---------------------------------------------------------------------------
876 // Fallible Hashing Interface
877 //---------------------------------------------------------------------------
879 // Most of the time generating a hash code is infallible, but sometimes it is
880 // necessary to generate hash codes on demand in a way that can fail. Specialize
881 // this class for your own hash policy to provide fallible hashing.
883 // This is used by MovableCellHasher to handle the fact that generating a unique
884 // ID for cell pointer may fail due to OOM.
886 // The default implementations of these methods delegate to the usual HashPolicy
887 // implementation and always succeed.
888 template <typename HashPolicy
>
889 struct FallibleHashMethods
{
890 // Return true if a hashcode is already available for its argument, and
891 // sets |aHashOut|. Once this succeeds for a specific argument it
892 // must continue to do so.
894 // Return false if a hashcode is not already available. This implies that any
895 // lookup must fail, as the hash code would have to have been successfully
896 // created on insertion.
897 template <typename Lookup
>
898 static bool maybeGetHash(Lookup
&& aLookup
, HashNumber
* aHashOut
) {
899 *aHashOut
= HashPolicy::hash(aLookup
);
903 // Fallible method to ensure a hashcode exists for its argument and create one
904 // if not. Sets |aHashOut| to the hashcode and retuns true on success. Returns
905 // false on error, e.g. out of memory.
906 template <typename Lookup
>
907 static bool ensureHash(Lookup
&& aLookup
, HashNumber
* aHashOut
) {
908 *aHashOut
= HashPolicy::hash(aLookup
);
913 template <typename HashPolicy
, typename Lookup
>
914 static bool MaybeGetHash(Lookup
&& aLookup
, HashNumber
* aHashOut
) {
915 return FallibleHashMethods
<typename
HashPolicy::Base
>::maybeGetHash(
916 std::forward
<Lookup
>(aLookup
), aHashOut
);
919 template <typename HashPolicy
, typename Lookup
>
920 static bool EnsureHash(Lookup
&& aLookup
, HashNumber
* aHashOut
) {
921 return FallibleHashMethods
<typename
HashPolicy::Base
>::ensureHash(
922 std::forward
<Lookup
>(aLookup
), aHashOut
);
925 //---------------------------------------------------------------------------
926 // Implementation Details (HashMapEntry, HashTableEntry, HashTable)
927 //---------------------------------------------------------------------------
929 // Both HashMap and HashSet are implemented by a single HashTable that is even
930 // more heavily parameterized than the other two. This leaves HashTable gnarly
931 // and extremely coupled to HashMap and HashSet; thus code should not use
932 // HashTable directly.
934 template <class Key
, class Value
>
939 template <class, class, class>
940 friend class detail::HashTable
;
942 friend class detail::HashTableEntry
;
943 template <class, class, class, class>
944 friend class HashMap
;
947 template <typename KeyInput
, typename ValueInput
>
948 HashMapEntry(KeyInput
&& aKey
, ValueInput
&& aValue
)
949 : key_(std::forward
<KeyInput
>(aKey
)),
950 value_(std::forward
<ValueInput
>(aValue
)) {}
952 HashMapEntry(HashMapEntry
&& aRhs
) = default;
953 HashMapEntry
& operator=(HashMapEntry
&& aRhs
) = default;
956 using ValueType
= Value
;
958 const Key
& key() const { return key_
; }
960 // Use this method with caution! If the key is changed such that its hash
961 // value also changes, the map will be left in an invalid state.
962 Key
& mutableKey() { return key_
; }
964 const Value
& value() const { return value_
; }
965 Value
& value() { return value_
; }
968 HashMapEntry(const HashMapEntry
&) = delete;
969 void operator=(const HashMapEntry
&) = delete;
974 template <class T
, class HashPolicy
, class AllocPolicy
>
977 template <typename T
>
980 template <typename T
>
981 class HashTableEntry
{
983 using NonConstT
= std::remove_const_t
<T
>;
985 // Instead of having a hash table entry store that looks like this:
987 // +--------+--------+--------+--------+
988 // | entry0 | entry1 | .... | entryN |
989 // +--------+--------+--------+--------+
991 // where the entries contained their cached hash code, we're going to lay out
992 // the entry store thusly:
994 // +-------+-------+-------+-------+--------+--------+--------+--------+
995 // | hash0 | hash1 | ... | hashN | entry0 | entry1 | .... | entryN |
996 // +-------+-------+-------+-------+--------+--------+--------+--------+
998 // with all the cached hashes prior to the actual entries themselves.
1000 // We do this because implementing the first strategy requires us to make
1001 // HashTableEntry look roughly like:
1003 // template <typename T>
1004 // class HashTableEntry {
1005 // HashNumber mKeyHash;
1009 // The problem with this setup is that, depending on the layout of `T`, there
1010 // may be platform ABI-mandated padding between `mKeyHash` and the first
1011 // member of `T`. This ABI-mandated padding is wasted space, and can be
1012 // surprisingly common, e.g. when `T` is a single pointer on 64-bit platforms.
1013 // In such cases, we're throwing away a quarter of our entry store on padding,
1014 // which is undesirable.
1016 // The second layout above, namely:
1018 // +-------+-------+-------+-------+--------+--------+--------+--------+
1019 // | hash0 | hash1 | ... | hashN | entry0 | entry1 | .... | entryN |
1020 // +-------+-------+-------+-------+--------+--------+--------+--------+
1022 // means there is no wasted space between the hashes themselves, and no wasted
1023 // space between the entries themselves. However, we would also like there to
1024 // be no gap between the last hash and the first entry. The memory allocator
1025 // guarantees the alignment of the start of the hashes. The use of a
1026 // power-of-two capacity of at least 4 guarantees that the alignment of the
1027 // *end* of the hash array is no less than the alignment of the start.
1028 // Finally, the static_asserts here guarantee that the entries themselves
1029 // don't need to be any more aligned than the alignment of the entry store
1032 // This assertion is safe for 32-bit builds because on both Windows and Linux
1033 // (including Android), the minimum alignment for allocations larger than 8
1034 // bytes is 8 bytes, and the actual data for entries in our entry store is
1035 // guaranteed to have that alignment as well, thanks to the power-of-two
1036 // number of cached hash values stored prior to the entry data.
1038 // The allocation policy must allocate a table with at least this much
1040 static constexpr size_t kMinimumAlignment
= 8;
1042 static_assert(alignof(HashNumber
) <= kMinimumAlignment
,
1043 "[N*2 hashes, N*2 T values] allocation's alignment must be "
1044 "enough to align each hash");
1045 static_assert(alignof(NonConstT
) <= 2 * sizeof(HashNumber
),
1046 "subsequent N*2 T values must not require more than an even "
1047 "number of HashNumbers provides");
1049 static const HashNumber sFreeKey
= 0;
1050 static const HashNumber sRemovedKey
= 1;
1051 static const HashNumber sCollisionBit
= 1;
1053 alignas(NonConstT
) unsigned char mValueData
[sizeof(NonConstT
)];
1056 template <class, class, class>
1057 friend class HashTable
;
1059 friend class EntrySlot
;
1061 // Some versions of GCC treat it as a -Wstrict-aliasing violation (ergo a
1062 // -Werror compile error) to reinterpret_cast<> |mValueData| to |T*|, even
1063 // through |void*|. Placing the latter cast in these separate functions
1064 // breaks the chain such that affected GCC versions no longer warn/error.
1065 void* rawValuePtr() { return mValueData
; }
1067 static bool isLiveHash(HashNumber hash
) { return hash
> sRemovedKey
; }
1069 HashTableEntry(const HashTableEntry
&) = delete;
1070 void operator=(const HashTableEntry
&) = delete;
1072 NonConstT
* valuePtr() { return reinterpret_cast<NonConstT
*>(rawValuePtr()); }
1074 void destroyStoredT() {
1075 NonConstT
* ptr
= valuePtr();
1077 MOZ_MAKE_MEM_UNDEFINED(ptr
, sizeof(*ptr
));
1081 HashTableEntry() = default;
1083 ~HashTableEntry() { MOZ_MAKE_MEM_UNDEFINED(this, sizeof(*this)); }
1085 void destroy() { destroyStoredT(); }
1087 void swap(HashTableEntry
* aOther
, bool aIsLive
) {
1088 // This allows types to use Argument-Dependent-Lookup, and thus use a custom
1089 // std::swap, which is needed by types like JS::Heap and such.
1092 if (this == aOther
) {
1096 swap(*valuePtr(), *aOther
->valuePtr());
1098 *aOther
->valuePtr() = std::move(*valuePtr());
1103 T
& get() { return *valuePtr(); }
1105 NonConstT
& getMutable() { return *valuePtr(); }
1108 // A slot represents a cached hash value and its associated entry stored
1109 // in the hash table. These two things are not stored in contiguous memory.
1112 using NonConstT
= std::remove_const_t
<T
>;
1114 using Entry
= HashTableEntry
<T
>;
1117 HashNumber
* mKeyHash
;
1119 template <class, class, class>
1120 friend class HashTable
;
1122 EntrySlot(Entry
* aEntry
, HashNumber
* aKeyHash
)
1123 : mEntry(aEntry
), mKeyHash(aKeyHash
) {}
1126 static bool isLiveHash(HashNumber hash
) { return hash
> Entry::sRemovedKey
; }
1128 EntrySlot(const EntrySlot
&) = default;
1129 EntrySlot(EntrySlot
&& aOther
) = default;
1131 EntrySlot
& operator=(const EntrySlot
&) = default;
1132 EntrySlot
& operator=(EntrySlot
&&) = default;
1134 bool operator==(const EntrySlot
& aRhs
) const { return mEntry
== aRhs
.mEntry
; }
1136 bool operator<(const EntrySlot
& aRhs
) const { return mEntry
< aRhs
.mEntry
; }
1138 EntrySlot
& operator++() {
1144 void destroy() { mEntry
->destroy(); }
1146 void swap(EntrySlot
& aOther
) {
1147 mEntry
->swap(aOther
.mEntry
, aOther
.isLive());
1148 std::swap(*mKeyHash
, *aOther
.mKeyHash
);
1151 T
& get() const { return mEntry
->get(); }
1153 NonConstT
& getMutable() { return mEntry
->getMutable(); }
1155 bool isFree() const { return *mKeyHash
== Entry::sFreeKey
; }
1158 MOZ_ASSERT(isLive());
1159 *mKeyHash
= Entry::sFreeKey
;
1160 mEntry
->destroyStoredT();
1165 mEntry
->destroyStoredT();
1167 MOZ_MAKE_MEM_UNDEFINED(mEntry
, sizeof(*mEntry
));
1168 *mKeyHash
= Entry::sFreeKey
;
1171 bool isRemoved() const { return *mKeyHash
== Entry::sRemovedKey
; }
1174 MOZ_ASSERT(isLive());
1175 *mKeyHash
= Entry::sRemovedKey
;
1176 mEntry
->destroyStoredT();
1179 bool isLive() const { return isLiveHash(*mKeyHash
); }
1181 void setCollision() {
1182 MOZ_ASSERT(isLive());
1183 *mKeyHash
|= Entry::sCollisionBit
;
1185 void unsetCollision() { *mKeyHash
&= ~Entry::sCollisionBit
; }
1186 bool hasCollision() const { return *mKeyHash
& Entry::sCollisionBit
; }
1187 bool matchHash(HashNumber hn
) {
1188 return (*mKeyHash
& ~Entry::sCollisionBit
) == hn
;
1190 HashNumber
getKeyHash() const { return *mKeyHash
& ~Entry::sCollisionBit
; }
1192 template <typename
... Args
>
1193 void setLive(HashNumber aHashNumber
, Args
&&... aArgs
) {
1194 MOZ_ASSERT(!isLive());
1195 *mKeyHash
= aHashNumber
;
1196 new (KnownNotNull
, mEntry
->valuePtr()) T(std::forward
<Args
>(aArgs
)...);
1197 MOZ_ASSERT(isLive());
1200 Entry
* toEntry() const { return mEntry
; }
1203 template <class T
, class HashPolicy
, class AllocPolicy
>
1204 class HashTable
: private AllocPolicy
{
1205 friend class mozilla::ReentrancyGuard
;
1207 using NonConstT
= std::remove_const_t
<T
>;
1208 using Key
= typename
HashPolicy::KeyType
;
1209 using Lookup
= typename
HashPolicy::Lookup
;
1212 using Entry
= HashTableEntry
<T
>;
1213 using Slot
= EntrySlot
<T
>;
1215 template <typename F
>
1216 static void forEachSlot(char* aTable
, uint32_t aCapacity
, F
&& f
) {
1217 auto hashes
= reinterpret_cast<HashNumber
*>(aTable
);
1218 auto entries
= reinterpret_cast<Entry
*>(&hashes
[aCapacity
]);
1219 Slot
slot(entries
, hashes
);
1220 for (size_t i
= 0; i
< size_t(aCapacity
); ++i
) {
1226 // A nullable pointer to a hash table element. A Ptr |p| can be tested
1227 // either explicitly |if (p.found()) p->...| or using boolean conversion
1228 // |if (p) p->...|. Ptr objects must not be used after any mutating hash
1229 // table operations unless |generation()| is tested.
1231 friend class HashTable
;
1235 const HashTable
* mTable
;
1236 Generation mGeneration
;
1240 Ptr(Slot aSlot
, const HashTable
& aTable
)
1245 mGeneration(aTable
.generation())
1250 // This constructor is used only by AddPtr() within lookupForAdd().
1251 explicit Ptr(const HashTable
& aTable
)
1252 : mSlot(nullptr, nullptr)
1256 mGeneration(aTable
.generation())
1261 bool isValid() const { return !!mSlot
.toEntry(); }
1265 : mSlot(nullptr, nullptr)
1274 bool found() const {
1279 MOZ_ASSERT(mGeneration
== mTable
->generation());
1281 return mSlot
.isLive();
1284 explicit operator bool() const { return found(); }
1286 bool operator==(const Ptr
& aRhs
) const {
1287 MOZ_ASSERT(found() && aRhs
.found());
1288 return mSlot
== aRhs
.mSlot
;
1291 bool operator!=(const Ptr
& aRhs
) const {
1293 MOZ_ASSERT(mGeneration
== mTable
->generation());
1295 return !(*this == aRhs
);
1298 T
& operator*() const {
1300 MOZ_ASSERT(found());
1301 MOZ_ASSERT(mGeneration
== mTable
->generation());
1306 T
* operator->() const {
1308 MOZ_ASSERT(found());
1309 MOZ_ASSERT(mGeneration
== mTable
->generation());
1311 return &mSlot
.get();
1315 // A Ptr that can be used to add a key after a failed lookup.
1316 class AddPtr
: public Ptr
{
1317 friend class HashTable
;
1319 HashNumber mKeyHash
;
1321 uint64_t mMutationCount
;
1324 AddPtr(Slot aSlot
, const HashTable
& aTable
, HashNumber aHashNumber
)
1325 : Ptr(aSlot
, aTable
),
1326 mKeyHash(aHashNumber
)
1329 mMutationCount(aTable
.mMutationCount
)
1334 // This constructor is used when lookupForAdd() is performed on a table
1335 // lacking entry storage; it leaves mSlot null but initializes everything
1337 AddPtr(const HashTable
& aTable
, HashNumber aHashNumber
)
1339 mKeyHash(aHashNumber
)
1342 mMutationCount(aTable
.mMutationCount
)
1345 MOZ_ASSERT(isLive());
1348 bool isLive() const { return isLiveHash(mKeyHash
); }
1351 AddPtr() : mKeyHash(0) {}
1354 // A hash table iterator that (mostly) doesn't allow table modifications.
1355 // As with Ptr/AddPtr, Iterator objects must not be used after any mutating
1356 // hash table operation unless the |generation()| is tested.
1358 void moveToNextLiveEntry() {
1359 while (++mCur
< mEnd
&& !mCur
.isLive()) {
1365 friend class HashTable
;
1367 explicit Iterator(const HashTable
& aTable
)
1368 : mCur(aTable
.slotForIndex(0)),
1369 mEnd(aTable
.slotForIndex(aTable
.capacity()))
1373 mMutationCount(aTable
.mMutationCount
),
1374 mGeneration(aTable
.generation()),
1378 if (!done() && !mCur
.isLive()) {
1379 moveToNextLiveEntry();
1386 const HashTable
& mTable
;
1387 uint64_t mMutationCount
;
1388 Generation mGeneration
;
1394 MOZ_ASSERT(mGeneration
== mTable
.generation());
1395 MOZ_ASSERT(mMutationCount
== mTable
.mMutationCount
);
1396 return mCur
== mEnd
;
1400 MOZ_ASSERT(!done());
1401 MOZ_ASSERT(mValidEntry
);
1402 MOZ_ASSERT(mGeneration
== mTable
.generation());
1403 MOZ_ASSERT(mMutationCount
== mTable
.mMutationCount
);
1408 MOZ_ASSERT(!done());
1409 MOZ_ASSERT(mGeneration
== mTable
.generation());
1410 MOZ_ASSERT(mMutationCount
== mTable
.mMutationCount
);
1411 moveToNextLiveEntry();
1418 // A hash table iterator that permits modification, removal and rekeying.
1419 // Since rehashing when elements were removed during enumeration would be
1420 // bad, it is postponed until the ModIterator is destructed. Since the
1421 // ModIterator's destructor touches the hash table, the user must ensure
1422 // that the hash table is still alive when the destructor runs.
1423 class ModIterator
: public Iterator
{
1424 friend class HashTable
;
1430 // ModIterator is movable but not copyable.
1431 ModIterator(const ModIterator
&) = delete;
1432 void operator=(const ModIterator
&) = delete;
1435 explicit ModIterator(HashTable
& aTable
)
1436 : Iterator(aTable
), mTable(aTable
), mRekeyed(false), mRemoved(false) {}
1439 MOZ_IMPLICIT
ModIterator(ModIterator
&& aOther
)
1441 mTable(aOther
.mTable
),
1442 mRekeyed(aOther
.mRekeyed
),
1443 mRemoved(aOther
.mRemoved
) {
1444 aOther
.mRekeyed
= false;
1445 aOther
.mRemoved
= false;
1448 // Removes the current element from the table, leaving |get()|
1449 // invalid until the next call to |next()|.
1451 mTable
.remove(this->mCur
);
1454 this->mValidEntry
= false;
1455 this->mMutationCount
= mTable
.mMutationCount
;
1459 NonConstT
& getMutable() {
1460 MOZ_ASSERT(!this->done());
1461 MOZ_ASSERT(this->mValidEntry
);
1462 MOZ_ASSERT(this->mGeneration
== this->Iterator::mTable
.generation());
1463 MOZ_ASSERT(this->mMutationCount
== this->Iterator::mTable
.mMutationCount
);
1464 return this->mCur
.getMutable();
1467 // Removes the current element and re-inserts it into the table with
1468 // a new key at the new Lookup position. |get()| is invalid after
1469 // this operation until the next call to |next()|.
1470 void rekey(const Lookup
& l
, const Key
& k
) {
1471 MOZ_ASSERT(&k
!= &HashPolicy::getKey(this->mCur
.get()));
1472 Ptr
p(this->mCur
, mTable
);
1473 mTable
.rekeyWithoutRehash(p
, l
, k
);
1476 this->mValidEntry
= false;
1477 this->mMutationCount
= mTable
.mMutationCount
;
1481 void rekey(const Key
& k
) { rekey(k
, k
); }
1483 // Potentially rehashes the table.
1487 mTable
.infallibleRehashIfOverloaded();
1496 // Range is similar to Iterator, but uses different terminology.
1498 friend class HashTable
;
1503 explicit Range(const HashTable
& table
) : mIter(table
) {}
1506 bool empty() const { return mIter
.done(); }
1508 T
& front() const { return mIter
.get(); }
1510 void popFront() { return mIter
.next(); }
1513 // Enum is similar to ModIterator, but uses different terminology.
1517 // Enum is movable but not copyable.
1518 Enum(const Enum
&) = delete;
1519 void operator=(const Enum
&) = delete;
1522 template <class Map
>
1523 explicit Enum(Map
& map
) : mIter(map
.mImpl
) {}
1525 MOZ_IMPLICIT
Enum(Enum
&& other
) : mIter(std::move(other
.mIter
)) {}
1527 bool empty() const { return mIter
.done(); }
1529 T
& front() const { return mIter
.get(); }
1531 void popFront() { return mIter
.next(); }
1533 void removeFront() { mIter
.remove(); }
1535 NonConstT
& mutableFront() { return mIter
.getMutable(); }
1537 void rekeyFront(const Lookup
& aLookup
, const Key
& aKey
) {
1538 mIter
.rekey(aLookup
, aKey
);
1541 void rekeyFront(const Key
& aKey
) { mIter
.rekey(aKey
); }
1544 // HashTable is movable
1545 HashTable(HashTable
&& aRhs
) : AllocPolicy(std::move(aRhs
)) { moveFrom(aRhs
); }
1546 HashTable
& operator=(HashTable
&& aRhs
) {
1547 MOZ_ASSERT(this != &aRhs
, "self-move assignment is prohibited");
1549 destroyTable(*this, mTable
, capacity());
1551 AllocPolicy::operator=(std::move(aRhs
));
1557 void moveFrom(HashTable
& aRhs
) {
1559 mHashShift
= aRhs
.mHashShift
;
1560 mTable
= aRhs
.mTable
;
1561 mEntryCount
= aRhs
.mEntryCount
;
1562 mRemovedCount
= aRhs
.mRemovedCount
;
1564 mMutationCount
= aRhs
.mMutationCount
;
1565 mEntered
= aRhs
.mEntered
;
1567 aRhs
.mTable
= nullptr;
1568 aRhs
.clearAndCompact();
1571 // HashTable is not copyable or assignable
1572 HashTable(const HashTable
&) = delete;
1573 void operator=(const HashTable
&) = delete;
1575 static const uint32_t CAP_BITS
= 30;
1578 uint64_t mGen
: 56; // entry storage generation number
1579 uint64_t mHashShift
: 8; // multiplicative hash shift
1580 char* mTable
; // entry storage
1581 uint32_t mEntryCount
; // number of entries in mTable
1582 uint32_t mRemovedCount
; // removed entry sentinels in mTable
1585 uint64_t mMutationCount
;
1586 mutable bool mEntered
;
1589 // The default initial capacity is 32 (enough to hold 16 elements), but it
1590 // can be as low as 4.
1591 static const uint32_t sDefaultLen
= 16;
1592 static const uint32_t sMinCapacity
= 4;
1593 // See the comments in HashTableEntry about this value.
1594 static_assert(sMinCapacity
>= 4, "too-small sMinCapacity breaks assumptions");
1595 static const uint32_t sMaxInit
= 1u << (CAP_BITS
- 1);
1596 static const uint32_t sMaxCapacity
= 1u << CAP_BITS
;
1598 // Hash-table alpha is conceptually a fraction, but to avoid floating-point
1599 // math we implement it as a ratio of integers.
1600 static const uint8_t sAlphaDenominator
= 4;
1601 static const uint8_t sMinAlphaNumerator
= 1; // min alpha: 1/4
1602 static const uint8_t sMaxAlphaNumerator
= 3; // max alpha: 3/4
1604 static const HashNumber sFreeKey
= Entry::sFreeKey
;
1605 static const HashNumber sRemovedKey
= Entry::sRemovedKey
;
1606 static const HashNumber sCollisionBit
= Entry::sCollisionBit
;
1608 static uint32_t bestCapacity(uint32_t aLen
) {
1610 (sMaxInit
* sAlphaDenominator
) / sAlphaDenominator
== sMaxInit
,
1611 "multiplication in numerator below could overflow");
1613 sMaxInit
* sAlphaDenominator
<= UINT32_MAX
- sMaxAlphaNumerator
,
1614 "numerator calculation below could potentially overflow");
1616 // Callers should ensure this is true.
1617 MOZ_ASSERT(aLen
<= sMaxInit
);
1619 // Compute the smallest capacity allowing |aLen| elements to be
1620 // inserted without rehashing: ceil(aLen / max-alpha). (Ceiling
1621 // integral division: <http://stackoverflow.com/a/2745086>.)
1622 uint32_t capacity
= (aLen
* sAlphaDenominator
+ sMaxAlphaNumerator
- 1) /
1624 capacity
= (capacity
< sMinCapacity
) ? sMinCapacity
: RoundUpPow2(capacity
);
1626 MOZ_ASSERT(capacity
>= aLen
);
1627 MOZ_ASSERT(capacity
<= sMaxCapacity
);
1632 static uint32_t hashShift(uint32_t aLen
) {
1633 // Reject all lengths whose initial computed capacity would exceed
1634 // sMaxCapacity. Round that maximum aLen down to the nearest power of two
1635 // for speedier code.
1636 if (MOZ_UNLIKELY(aLen
> sMaxInit
)) {
1637 MOZ_CRASH("initial length is too large");
1640 return kHashNumberBits
- mozilla::CeilingLog2(bestCapacity(aLen
));
1643 static bool isLiveHash(HashNumber aHash
) { return Entry::isLiveHash(aHash
); }
1645 static HashNumber
prepareHash(HashNumber aInputHash
) {
1646 HashNumber keyHash
= ScrambleHashCode(aInputHash
);
1648 // Avoid reserved hash codes.
1649 if (!isLiveHash(keyHash
)) {
1650 keyHash
-= (sRemovedKey
+ 1);
1652 return keyHash
& ~sCollisionBit
;
1655 enum FailureBehavior
{ DontReportFailure
= false, ReportFailure
= true };
1657 // Fake a struct that we're going to alloc. See the comments in
1658 // HashTableEntry about how the table is laid out, and why it's safe.
1660 unsigned char c
[sizeof(HashNumber
) + sizeof(typename
Entry::NonConstT
)];
1663 static char* createTable(AllocPolicy
& aAllocPolicy
, uint32_t aCapacity
,
1664 FailureBehavior aReportFailure
= ReportFailure
) {
1667 ? aAllocPolicy
.template pod_malloc
<FakeSlot
>(aCapacity
)
1668 : aAllocPolicy
.template maybe_pod_malloc
<FakeSlot
>(aCapacity
);
1670 MOZ_ASSERT((reinterpret_cast<uintptr_t>(fake
) % Entry::kMinimumAlignment
) ==
1673 char* table
= reinterpret_cast<char*>(fake
);
1675 forEachSlot(table
, aCapacity
, [&](Slot
& slot
) {
1676 *slot
.mKeyHash
= sFreeKey
;
1677 new (KnownNotNull
, slot
.toEntry()) Entry();
1683 static void destroyTable(AllocPolicy
& aAllocPolicy
, char* aOldTable
,
1684 uint32_t aCapacity
) {
1685 forEachSlot(aOldTable
, aCapacity
, [&](const Slot
& slot
) {
1686 if (slot
.isLive()) {
1687 slot
.toEntry()->destroyStoredT();
1690 freeTable(aAllocPolicy
, aOldTable
, aCapacity
);
1693 static void freeTable(AllocPolicy
& aAllocPolicy
, char* aOldTable
,
1694 uint32_t aCapacity
) {
1695 FakeSlot
* fake
= reinterpret_cast<FakeSlot
*>(aOldTable
);
1696 aAllocPolicy
.free_(fake
, aCapacity
);
1700 HashTable(AllocPolicy aAllocPolicy
, uint32_t aLen
)
1701 : AllocPolicy(std::move(aAllocPolicy
)),
1703 mHashShift(hashShift(aLen
)),
1715 explicit HashTable(AllocPolicy aAllocPolicy
)
1716 : HashTable(aAllocPolicy
, sDefaultLen
) {}
1720 destroyTable(*this, mTable
, capacity());
1725 HashNumber
hash1(HashNumber aHash0
) const { return aHash0
>> mHashShift
; }
1729 HashNumber mSizeMask
;
1732 DoubleHash
hash2(HashNumber aCurKeyHash
) const {
1733 uint32_t sizeLog2
= kHashNumberBits
- mHashShift
;
1734 DoubleHash dh
= {((aCurKeyHash
<< sizeLog2
) >> mHashShift
) | 1,
1735 (HashNumber(1) << sizeLog2
) - 1};
1739 static HashNumber
applyDoubleHash(HashNumber aHash1
,
1740 const DoubleHash
& aDoubleHash
) {
1741 return WrappingSubtract(aHash1
, aDoubleHash
.mHash2
) & aDoubleHash
.mSizeMask
;
1744 static MOZ_ALWAYS_INLINE
bool match(T
& aEntry
, const Lookup
& aLookup
) {
1745 return HashPolicy::match(HashPolicy::getKey(aEntry
), aLookup
);
1748 enum LookupReason
{ ForNonAdd
, ForAdd
};
1750 Slot
slotForIndex(HashNumber aIndex
) const {
1751 auto hashes
= reinterpret_cast<HashNumber
*>(mTable
);
1752 auto entries
= reinterpret_cast<Entry
*>(&hashes
[capacity()]);
1753 return Slot(&entries
[aIndex
], &hashes
[aIndex
]);
1756 // Warning: in order for readonlyThreadsafeLookup() to be safe this
1757 // function must not modify the table in any way when Reason==ForNonAdd.
1758 template <LookupReason Reason
>
1759 MOZ_ALWAYS_INLINE Slot
lookup(const Lookup
& aLookup
,
1760 HashNumber aKeyHash
) const {
1761 MOZ_ASSERT(isLiveHash(aKeyHash
));
1762 MOZ_ASSERT(!(aKeyHash
& sCollisionBit
));
1765 // Compute the primary hash address.
1766 HashNumber h1
= hash1(aKeyHash
);
1767 Slot slot
= slotForIndex(h1
);
1769 // Miss: return space for a new entry.
1770 if (slot
.isFree()) {
1774 // Hit: return entry.
1775 if (slot
.matchHash(aKeyHash
) && match(slot
.get(), aLookup
)) {
1779 // Collision: double hash.
1780 DoubleHash dh
= hash2(aKeyHash
);
1782 // Save the first removed entry pointer so we can recycle later.
1783 Maybe
<Slot
> firstRemoved
;
1786 if (Reason
== ForAdd
&& !firstRemoved
) {
1787 if (MOZ_UNLIKELY(slot
.isRemoved())) {
1788 firstRemoved
.emplace(slot
);
1790 slot
.setCollision();
1794 h1
= applyDoubleHash(h1
, dh
);
1796 slot
= slotForIndex(h1
);
1797 if (slot
.isFree()) {
1798 return firstRemoved
.refOr(slot
);
1801 if (slot
.matchHash(aKeyHash
) && match(slot
.get(), aLookup
)) {
1807 // This is a copy of lookup() hardcoded to the assumptions:
1808 // 1. the lookup is for an add;
1809 // 2. the key, whose |keyHash| has been passed, is not in the table.
1810 Slot
findNonLiveSlot(HashNumber aKeyHash
) {
1811 MOZ_ASSERT(!(aKeyHash
& sCollisionBit
));
1814 // We assume 'aKeyHash' has already been distributed.
1816 // Compute the primary hash address.
1817 HashNumber h1
= hash1(aKeyHash
);
1818 Slot slot
= slotForIndex(h1
);
1820 // Miss: return space for a new entry.
1821 if (!slot
.isLive()) {
1825 // Collision: double hash.
1826 DoubleHash dh
= hash2(aKeyHash
);
1829 slot
.setCollision();
1831 h1
= applyDoubleHash(h1
, dh
);
1833 slot
= slotForIndex(h1
);
1834 if (!slot
.isLive()) {
1840 enum RebuildStatus
{ NotOverloaded
, Rehashed
, RehashFailed
};
1842 RebuildStatus
changeTableSize(
1843 uint32_t newCapacity
, FailureBehavior aReportFailure
= ReportFailure
) {
1844 MOZ_ASSERT(IsPowerOfTwo(newCapacity
));
1845 MOZ_ASSERT(!!mTable
== !!capacity());
1847 // Look, but don't touch, until we succeed in getting new entry store.
1848 char* oldTable
= mTable
;
1849 uint32_t oldCapacity
= capacity();
1850 uint32_t newLog2
= mozilla::CeilingLog2(newCapacity
);
1852 if (MOZ_UNLIKELY(newCapacity
> sMaxCapacity
)) {
1853 if (aReportFailure
) {
1854 this->reportAllocOverflow();
1856 return RehashFailed
;
1859 char* newTable
= createTable(*this, newCapacity
, aReportFailure
);
1861 return RehashFailed
;
1864 // We can't fail from here on, so update table parameters.
1865 mHashShift
= kHashNumberBits
- newLog2
;
1870 // Copy only live entries, leaving removed ones behind.
1871 forEachSlot(oldTable
, oldCapacity
, [&](Slot
& slot
) {
1872 if (slot
.isLive()) {
1873 HashNumber hn
= slot
.getKeyHash();
1874 findNonLiveSlot(hn
).setLive(
1875 hn
, std::move(const_cast<typename
Entry::NonConstT
&>(slot
.get())));
1881 // All entries have been destroyed, no need to destroyTable.
1882 freeTable(*this, oldTable
, oldCapacity
);
1886 RebuildStatus
rehashIfOverloaded(
1887 FailureBehavior aReportFailure
= ReportFailure
) {
1888 static_assert(sMaxCapacity
<= UINT32_MAX
/ sMaxAlphaNumerator
,
1889 "multiplication below could overflow");
1891 // Note: if capacity() is zero, this will always succeed, which is
1893 bool overloaded
= mEntryCount
+ mRemovedCount
>=
1894 capacity() * sMaxAlphaNumerator
/ sAlphaDenominator
;
1897 return NotOverloaded
;
1900 // Succeed if a quarter or more of all entries are removed. Note that this
1901 // always succeeds if capacity() == 0 (i.e. entry storage has not been
1902 // allocated), which is what we want, because it means changeTableSize()
1903 // will allocate the requested capacity rather than doubling it.
1904 bool manyRemoved
= mRemovedCount
>= (capacity() >> 2);
1905 uint32_t newCapacity
= manyRemoved
? rawCapacity() : rawCapacity() * 2;
1906 return changeTableSize(newCapacity
, aReportFailure
);
1909 void infallibleRehashIfOverloaded() {
1910 if (rehashIfOverloaded(DontReportFailure
) == RehashFailed
) {
1911 rehashTableInPlace();
1915 void remove(Slot
& aSlot
) {
1918 if (aSlot
.hasCollision()) {
1930 void shrinkIfUnderloaded() {
1931 static_assert(sMaxCapacity
<= UINT32_MAX
/ sMinAlphaNumerator
,
1932 "multiplication below could overflow");
1934 capacity() > sMinCapacity
&&
1935 mEntryCount
<= capacity() * sMinAlphaNumerator
/ sAlphaDenominator
;
1938 (void)changeTableSize(capacity() / 2, DontReportFailure
);
1942 // This is identical to changeTableSize(currentSize), but without requiring
1943 // a second table. We do this by recycling the collision bits to tell us if
1944 // the element is already inserted or still waiting to be inserted. Since
1945 // already-inserted elements win any conflicts, we get the same table as we
1946 // would have gotten through random insertion order.
1947 void rehashTableInPlace() {
1950 forEachSlot(mTable
, capacity(), [&](Slot
& slot
) { slot
.unsetCollision(); });
1951 for (uint32_t i
= 0; i
< capacity();) {
1952 Slot src
= slotForIndex(i
);
1954 if (!src
.isLive() || src
.hasCollision()) {
1959 HashNumber keyHash
= src
.getKeyHash();
1960 HashNumber h1
= hash1(keyHash
);
1961 DoubleHash dh
= hash2(keyHash
);
1962 Slot tgt
= slotForIndex(h1
);
1964 if (!tgt
.hasCollision()) {
1970 h1
= applyDoubleHash(h1
, dh
);
1971 tgt
= slotForIndex(h1
);
1975 // TODO: this algorithm leaves collision bits on *all* elements, even if
1976 // they are on no collision path. We have the option of setting the
1977 // collision bits correctly on a subsequent pass or skipping the rehash
1978 // unless we are totally filled with tombstones: benchmark to find out
1979 // which approach is best.
1982 // Prefer to use putNewInfallible; this function does not check
1984 template <typename
... Args
>
1985 void putNewInfallibleInternal(HashNumber aKeyHash
, Args
&&... aArgs
) {
1988 Slot slot
= findNonLiveSlot(aKeyHash
);
1990 if (slot
.isRemoved()) {
1992 aKeyHash
|= sCollisionBit
;
1995 slot
.setLive(aKeyHash
, std::forward
<Args
>(aArgs
)...);
2004 forEachSlot(mTable
, capacity(), [&](Slot
& slot
) { slot
.clear(); });
2012 // Resize the table down to the smallest capacity that doesn't overload the
2013 // table. Since we call shrinkIfUnderloaded() on every remove, you only need
2014 // to call this after a bulk removal of items done without calling remove().
2017 // Free the entry storage.
2018 freeTable(*this, mTable
, capacity());
2020 mHashShift
= hashShift(0); // gives minimum capacity on regrowth
2026 uint32_t bestCapacity
= this->bestCapacity(mEntryCount
);
2027 MOZ_ASSERT(bestCapacity
<= capacity());
2029 if (bestCapacity
< capacity()) {
2030 (void)changeTableSize(bestCapacity
, DontReportFailure
);
2034 void clearAndCompact() {
2039 [[nodiscard
]] bool reserve(uint32_t aLen
) {
2044 if (MOZ_UNLIKELY(aLen
> sMaxInit
)) {
2045 this->reportAllocOverflow();
2049 uint32_t bestCapacity
= this->bestCapacity(aLen
);
2050 if (bestCapacity
<= capacity()) {
2051 return true; // Capacity is already sufficient.
2054 RebuildStatus status
= changeTableSize(bestCapacity
, ReportFailure
);
2055 MOZ_ASSERT(status
!= NotOverloaded
);
2056 return status
!= RehashFailed
;
2059 Iterator
iter() const { return Iterator(*this); }
2061 ModIterator
modIter() { return ModIterator(*this); }
2063 Range
all() const { return Range(*this); }
2065 bool empty() const { return mEntryCount
== 0; }
2067 uint32_t count() const { return mEntryCount
; }
2069 uint32_t rawCapacity() const { return 1u << (kHashNumberBits
- mHashShift
); }
2071 uint32_t capacity() const { return mTable
? rawCapacity() : 0; }
2073 Generation
generation() const { return Generation(mGen
); }
2075 size_t shallowSizeOfExcludingThis(MallocSizeOf aMallocSizeOf
) const {
2076 return aMallocSizeOf(mTable
);
2079 size_t shallowSizeOfIncludingThis(MallocSizeOf aMallocSizeOf
) const {
2080 return aMallocSizeOf(this) + shallowSizeOfExcludingThis(aMallocSizeOf
);
2083 MOZ_ALWAYS_INLINE Ptr
readonlyThreadsafeLookup(const Lookup
& aLookup
) const {
2088 HashNumber inputHash
;
2089 if (!MaybeGetHash
<HashPolicy
>(aLookup
, &inputHash
)) {
2093 HashNumber keyHash
= prepareHash(inputHash
);
2094 return Ptr(lookup
<ForNonAdd
>(aLookup
, keyHash
), *this);
2097 MOZ_ALWAYS_INLINE Ptr
lookup(const Lookup
& aLookup
) const {
2098 ReentrancyGuard
g(*this);
2099 return readonlyThreadsafeLookup(aLookup
);
2102 MOZ_ALWAYS_INLINE AddPtr
lookupForAdd(const Lookup
& aLookup
) {
2103 ReentrancyGuard
g(*this);
2105 HashNumber inputHash
;
2106 if (!EnsureHash
<HashPolicy
>(aLookup
, &inputHash
)) {
2110 HashNumber keyHash
= prepareHash(inputHash
);
2113 return AddPtr(*this, keyHash
);
2116 // Directly call the constructor in the return statement to avoid
2117 // excess copying when building with Visual Studio 2017.
2119 return AddPtr(lookup
<ForAdd
>(aLookup
, keyHash
), *this, keyHash
);
2122 template <typename
... Args
>
2123 [[nodiscard
]] bool add(AddPtr
& aPtr
, Args
&&... aArgs
) {
2124 ReentrancyGuard
g(*this);
2125 MOZ_ASSERT_IF(aPtr
.isValid(), mTable
);
2126 MOZ_ASSERT_IF(aPtr
.isValid(), aPtr
.mTable
== this);
2127 MOZ_ASSERT(!aPtr
.found());
2128 MOZ_ASSERT(!(aPtr
.mKeyHash
& sCollisionBit
));
2130 // Check for error from ensureHash() here.
2131 if (!aPtr
.isLive()) {
2135 MOZ_ASSERT(aPtr
.mGeneration
== generation());
2137 MOZ_ASSERT(aPtr
.mMutationCount
== mMutationCount
);
2140 if (!aPtr
.isValid()) {
2141 MOZ_ASSERT(!mTable
&& mEntryCount
== 0);
2142 uint32_t newCapacity
= rawCapacity();
2143 RebuildStatus status
= changeTableSize(newCapacity
, ReportFailure
);
2144 MOZ_ASSERT(status
!= NotOverloaded
);
2145 if (status
== RehashFailed
) {
2148 aPtr
.mSlot
= findNonLiveSlot(aPtr
.mKeyHash
);
2150 } else if (aPtr
.mSlot
.isRemoved()) {
2151 // Changing an entry from removed to live does not affect whether we are
2152 // overloaded and can be handled separately.
2153 if (!this->checkSimulatedOOM()) {
2157 aPtr
.mKeyHash
|= sCollisionBit
;
2160 // Preserve the validity of |aPtr.mSlot|.
2161 RebuildStatus status
= rehashIfOverloaded();
2162 if (status
== RehashFailed
) {
2165 if (status
== NotOverloaded
&& !this->checkSimulatedOOM()) {
2168 if (status
== Rehashed
) {
2169 aPtr
.mSlot
= findNonLiveSlot(aPtr
.mKeyHash
);
2173 aPtr
.mSlot
.setLive(aPtr
.mKeyHash
, std::forward
<Args
>(aArgs
)...);
2177 aPtr
.mGeneration
= generation();
2178 aPtr
.mMutationCount
= mMutationCount
;
2183 // Note: |aLookup| may reference pieces of arguments in |aArgs|, so this
2184 // function must take care not to use |aLookup| after moving |aArgs|.
2185 template <typename
... Args
>
2186 void putNewInfallible(const Lookup
& aLookup
, Args
&&... aArgs
) {
2187 MOZ_ASSERT(!lookup(aLookup
).found());
2188 ReentrancyGuard
g(*this);
2189 HashNumber keyHash
= prepareHash(HashPolicy::hash(aLookup
));
2190 putNewInfallibleInternal(keyHash
, std::forward
<Args
>(aArgs
)...);
2193 // Note: |aLookup| may alias arguments in |aArgs|, so this function must take
2194 // care not to use |aLookup| after moving |aArgs|.
2195 template <typename
... Args
>
2196 [[nodiscard
]] bool putNew(const Lookup
& aLookup
, Args
&&... aArgs
) {
2197 MOZ_ASSERT(!lookup(aLookup
).found());
2198 ReentrancyGuard
g(*this);
2199 if (!this->checkSimulatedOOM()) {
2202 HashNumber inputHash
;
2203 if (!EnsureHash
<HashPolicy
>(aLookup
, &inputHash
)) {
2206 HashNumber keyHash
= prepareHash(inputHash
);
2207 if (rehashIfOverloaded() == RehashFailed
) {
2210 putNewInfallibleInternal(keyHash
, std::forward
<Args
>(aArgs
)...);
2214 // Note: |aLookup| may be a reference pieces of arguments in |aArgs|, so this
2215 // function must take care not to use |aLookup| after moving |aArgs|.
2216 template <typename
... Args
>
2217 [[nodiscard
]] bool relookupOrAdd(AddPtr
& aPtr
, const Lookup
& aLookup
,
2219 // Check for error from ensureHash() here.
2220 if (!aPtr
.isLive()) {
2224 aPtr
.mGeneration
= generation();
2225 aPtr
.mMutationCount
= mMutationCount
;
2228 ReentrancyGuard
g(*this);
2229 // Check that aLookup has not been destroyed.
2230 MOZ_ASSERT(prepareHash(HashPolicy::hash(aLookup
)) == aPtr
.mKeyHash
);
2231 aPtr
.mSlot
= lookup
<ForAdd
>(aLookup
, aPtr
.mKeyHash
);
2236 // Clear aPtr so it's invalid; add() will allocate storage and redo the
2238 aPtr
.mSlot
= Slot(nullptr, nullptr);
2240 return add(aPtr
, std::forward
<Args
>(aArgs
)...);
2243 void remove(Ptr aPtr
) {
2245 ReentrancyGuard
g(*this);
2246 MOZ_ASSERT(aPtr
.found());
2247 MOZ_ASSERT(aPtr
.mGeneration
== generation());
2249 shrinkIfUnderloaded();
2252 void rekeyWithoutRehash(Ptr aPtr
, const Lookup
& aLookup
, const Key
& aKey
) {
2254 ReentrancyGuard
g(*this);
2255 MOZ_ASSERT(aPtr
.found());
2256 MOZ_ASSERT(aPtr
.mGeneration
== generation());
2257 typename HashTableEntry
<T
>::NonConstT
t(std::move(*aPtr
));
2258 HashPolicy::setKey(t
, const_cast<Key
&>(aKey
));
2260 HashNumber keyHash
= prepareHash(HashPolicy::hash(aLookup
));
2261 putNewInfallibleInternal(keyHash
, std::move(t
));
2264 void rekeyAndMaybeRehash(Ptr aPtr
, const Lookup
& aLookup
, const Key
& aKey
) {
2265 rekeyWithoutRehash(aPtr
, aLookup
, aKey
);
2266 infallibleRehashIfOverloaded();
2270 } // namespace detail
2271 } // namespace mozilla
2273 #endif /* mozilla_HashTable_h */