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 MOZ_MUST_USE.
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"
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. Does
214 // nothing if the map already has sufficient capacity.
215 MOZ_MUST_USE
bool reserve(uint32_t aLen
) { return mImpl
.reserve(aLen
); }
217 // -- Lookups --------------------------------------------------------------
219 // Does the map contain a key/value matching |aLookup|?
220 bool has(const Lookup
& aLookup
) const {
221 return mImpl
.lookup(aLookup
).found();
224 // Return a Ptr indicating whether a key/value matching |aLookup| is
225 // present in the map. E.g.:
227 // using HM = HashMap<int,char>;
229 // if (HM::Ptr p = h.lookup(3)) {
230 // assert(p->key() == 3);
231 // char val = p->value();
234 using Ptr
= typename
Impl::Ptr
;
235 MOZ_ALWAYS_INLINE Ptr
lookup(const Lookup
& aLookup
) const {
236 return mImpl
.lookup(aLookup
);
239 // Like lookup(), but does not assert if two threads call it at the same
240 // time. Only use this method when none of the threads will modify the map.
241 MOZ_ALWAYS_INLINE Ptr
readonlyThreadsafeLookup(const Lookup
& aLookup
) const {
242 return mImpl
.readonlyThreadsafeLookup(aLookup
);
245 // -- Insertions -----------------------------------------------------------
247 // Overwrite existing value with |aValue|, or add it if not present. Returns
249 template <typename KeyInput
, typename ValueInput
>
250 MOZ_MUST_USE
bool put(KeyInput
&& aKey
, ValueInput
&& aValue
) {
251 AddPtr p
= lookupForAdd(aKey
);
253 p
->value() = std::forward
<ValueInput
>(aValue
);
256 return add(p
, std::forward
<KeyInput
>(aKey
),
257 std::forward
<ValueInput
>(aValue
));
260 // Like put(), but slightly faster. Must only be used when the given key is
261 // not already present. (In debug builds, assertions check this.)
262 template <typename KeyInput
, typename ValueInput
>
263 MOZ_MUST_USE
bool putNew(KeyInput
&& aKey
, ValueInput
&& aValue
) {
264 return mImpl
.putNew(aKey
, std::forward
<KeyInput
>(aKey
),
265 std::forward
<ValueInput
>(aValue
));
268 // Like putNew(), but should be only used when the table is known to be big
269 // enough for the insertion, and hashing cannot fail. Typically this is used
270 // to populate an empty map with known-unique keys after reserving space with
273 // using HM = HashMap<int,char>;
275 // if (!h.reserve(3)) {
278 // h.putNewInfallible(1, 'a'); // unique key
279 // h.putNewInfallible(2, 'b'); // unique key
280 // h.putNewInfallible(3, 'c'); // unique key
282 template <typename KeyInput
, typename ValueInput
>
283 void putNewInfallible(KeyInput
&& aKey
, ValueInput
&& aValue
) {
284 mImpl
.putNewInfallible(aKey
, std::forward
<KeyInput
>(aKey
),
285 std::forward
<ValueInput
>(aValue
));
288 // Like |lookup(l)|, but on miss, |p = lookupForAdd(l)| allows efficient
289 // insertion of Key |k| (where |HashPolicy::match(k,l) == true|) using
290 // |add(p,k,v)|. After |add(p,k,v)|, |p| points to the new key/value. E.g.:
292 // using HM = HashMap<int,char>;
294 // HM::AddPtr p = h.lookupForAdd(3);
296 // if (!h.add(p, 3, 'a')) {
300 // assert(p->key() == 3);
301 // char val = p->value();
303 // N.B. The caller must ensure that no mutating hash table operations occur
304 // between a pair of lookupForAdd() and add() calls. To avoid looking up the
305 // key a second time, the caller may use the more efficient relookupOrAdd()
306 // method. This method reuses part of the hashing computation to more
307 // efficiently insert the key if it has not been added. For example, a
308 // mutation-handling version of the previous example:
310 // HM::AddPtr p = h.lookupForAdd(3);
312 // call_that_may_mutate_h();
313 // if (!h.relookupOrAdd(p, 3, 'a')) {
317 // assert(p->key() == 3);
318 // char val = p->value();
320 using AddPtr
= typename
Impl::AddPtr
;
321 MOZ_ALWAYS_INLINE AddPtr
lookupForAdd(const Lookup
& aLookup
) {
322 return mImpl
.lookupForAdd(aLookup
);
325 // Add a key/value. Returns false on OOM.
326 template <typename KeyInput
, typename ValueInput
>
327 MOZ_MUST_USE
bool add(AddPtr
& aPtr
, KeyInput
&& aKey
, ValueInput
&& aValue
) {
328 return mImpl
.add(aPtr
, std::forward
<KeyInput
>(aKey
),
329 std::forward
<ValueInput
>(aValue
));
332 // See the comment above lookupForAdd() for details.
333 template <typename KeyInput
, typename ValueInput
>
334 MOZ_MUST_USE
bool relookupOrAdd(AddPtr
& aPtr
, KeyInput
&& aKey
,
335 ValueInput
&& aValue
) {
336 return mImpl
.relookupOrAdd(aPtr
, aKey
, std::forward
<KeyInput
>(aKey
),
337 std::forward
<ValueInput
>(aValue
));
340 // -- Removal --------------------------------------------------------------
342 // Lookup and remove the key/value matching |aLookup|, if present.
343 void remove(const Lookup
& aLookup
) {
344 if (Ptr p
= lookup(aLookup
)) {
349 // Remove a previously found key/value (assuming aPtr.found()). The map must
350 // not have been mutated in the interim.
351 void remove(Ptr aPtr
) { mImpl
.remove(aPtr
); }
353 // Remove all keys/values without changing the capacity.
354 void clear() { mImpl
.clear(); }
356 // Like clear() followed by compact().
357 void clearAndCompact() { mImpl
.clearAndCompact(); }
359 // -- Rekeying -------------------------------------------------------------
361 // Infallibly rekey one entry, if necessary. Requires that template
362 // parameters Key and HashPolicy::Lookup are the same type.
363 void rekeyIfMoved(const Key
& aOldKey
, const Key
& aNewKey
) {
364 if (aOldKey
!= aNewKey
) {
365 rekeyAs(aOldKey
, aNewKey
, aNewKey
);
369 // Infallibly rekey one entry if present, and return whether that happened.
370 bool rekeyAs(const Lookup
& aOldLookup
, const Lookup
& aNewLookup
,
371 const Key
& aNewKey
) {
372 if (Ptr p
= lookup(aOldLookup
)) {
373 mImpl
.rekeyAndMaybeRehash(p
, aNewLookup
, aNewKey
);
379 // -- Iteration ------------------------------------------------------------
381 // |iter()| returns an Iterator:
383 // HashMap<int, char> h;
384 // for (auto iter = h.iter(); !iter.done(); iter.next()) {
385 // char c = iter.get().value();
388 using Iterator
= typename
Impl::Iterator
;
389 Iterator
iter() const { return mImpl
.iter(); }
391 // |modIter()| returns a ModIterator:
393 // HashMap<int, char> h;
394 // for (auto iter = h.modIter(); !iter.done(); iter.next()) {
395 // if (iter.get().value() == 'l') {
400 // Table resize may occur in ModIterator's destructor.
401 using ModIterator
= typename
Impl::ModIterator
;
402 ModIterator
modIter() { return mImpl
.modIter(); }
404 // These are similar to Iterator/ModIterator/iter(), but use different
406 using Range
= typename
Impl::Range
;
407 using Enum
= typename
Impl::Enum
;
408 Range
all() const { return mImpl
.all(); }
411 //---------------------------------------------------------------------------
413 //---------------------------------------------------------------------------
415 // HashSet is a fast hash-based set of values.
417 // Template parameter requirements:
418 // - T: movable, destructible, assignable.
419 // - HashPolicy: see the "Hash Policy" section below.
420 // - AllocPolicy: see AllocPolicy.h
423 // - HashSet is not reentrant: T/HashPolicy/AllocPolicy members called by
424 // HashSet must not call back into the same HashSet object.
426 template <class T
, class HashPolicy
= DefaultHasher
<T
>,
427 class AllocPolicy
= MallocAllocPolicy
>
429 // -- Implementation details -----------------------------------------------
431 // HashSet is not copyable or assignable.
432 HashSet(const HashSet
& hs
) = delete;
433 HashSet
& operator=(const HashSet
& hs
) = delete;
435 struct SetHashPolicy
: HashPolicy
{
436 using Base
= HashPolicy
;
439 static const KeyType
& getKey(const T
& aT
) { return aT
; }
441 static void setKey(T
& aT
, KeyType
& aKey
) { HashPolicy::rekey(aT
, aKey
); }
444 using Impl
= detail::HashTable
<const T
, SetHashPolicy
, AllocPolicy
>;
447 friend class Impl::Enum
;
450 using Lookup
= typename
HashPolicy::Lookup
;
453 // -- Initialization -------------------------------------------------------
455 explicit HashSet(AllocPolicy aAllocPolicy
= AllocPolicy(),
456 uint32_t aLen
= Impl::sDefaultLen
)
457 : mImpl(std::move(aAllocPolicy
), aLen
) {}
459 explicit HashSet(uint32_t aLen
) : mImpl(AllocPolicy(), aLen
) {}
461 // HashSet is movable.
462 HashSet(HashSet
&& aRhs
) = default;
463 HashSet
& operator=(HashSet
&& aRhs
) = default;
465 // -- Status and sizing ----------------------------------------------------
467 // The set's current generation.
468 Generation
generation() const { return mImpl
.generation(); }
471 bool empty() const { return mImpl
.empty(); }
473 // Number of elements in the set.
474 uint32_t count() const { return mImpl
.count(); }
476 // Number of element slots in the set. Note: resize will happen well before
477 // count() == capacity().
478 uint32_t capacity() const { return mImpl
.capacity(); }
480 // The size of the set's entry storage, in bytes. If the elements contain
481 // pointers to other heap blocks, you must iterate over the set and measure
482 // them separately; hence the "shallow" prefix.
483 size_t shallowSizeOfExcludingThis(MallocSizeOf aMallocSizeOf
) const {
484 return mImpl
.shallowSizeOfExcludingThis(aMallocSizeOf
);
486 size_t shallowSizeOfIncludingThis(MallocSizeOf aMallocSizeOf
) const {
487 return aMallocSizeOf(this) +
488 mImpl
.shallowSizeOfExcludingThis(aMallocSizeOf
);
491 // Attempt to minimize the capacity(). If the table is empty, this will free
492 // the empty storage and upon regrowth it will be given the minimum capacity.
493 void compact() { mImpl
.compact(); }
495 // Attempt to reserve enough space to fit at least |aLen| elements. Does
496 // nothing if the map already has sufficient capacity.
497 MOZ_MUST_USE
bool reserve(uint32_t aLen
) { return mImpl
.reserve(aLen
); }
499 // -- Lookups --------------------------------------------------------------
501 // Does the set contain an element matching |aLookup|?
502 bool has(const Lookup
& aLookup
) const {
503 return mImpl
.lookup(aLookup
).found();
506 // Return a Ptr indicating whether an element matching |aLookup| is present
509 // using HS = HashSet<int>;
511 // if (HS::Ptr p = h.lookup(3)) {
512 // assert(*p == 3); // p acts like a pointer to int
515 using Ptr
= typename
Impl::Ptr
;
516 MOZ_ALWAYS_INLINE Ptr
lookup(const Lookup
& aLookup
) const {
517 return mImpl
.lookup(aLookup
);
520 // Like lookup(), but does not assert if two threads call it at the same
521 // time. Only use this method when none of the threads will modify the set.
522 MOZ_ALWAYS_INLINE Ptr
readonlyThreadsafeLookup(const Lookup
& aLookup
) const {
523 return mImpl
.readonlyThreadsafeLookup(aLookup
);
526 // -- Insertions -----------------------------------------------------------
528 // Add |aU| if it is not present already. Returns false on OOM.
529 template <typename U
>
530 MOZ_MUST_USE
bool put(U
&& aU
) {
531 AddPtr p
= lookupForAdd(aU
);
532 return p
? true : add(p
, std::forward
<U
>(aU
));
535 // Like put(), but slightly faster. Must only be used when the given element
536 // is not already present. (In debug builds, assertions check this.)
537 template <typename U
>
538 MOZ_MUST_USE
bool putNew(U
&& aU
) {
539 return mImpl
.putNew(aU
, std::forward
<U
>(aU
));
542 // Like the other putNew(), but for when |Lookup| is different to |T|.
543 template <typename U
>
544 MOZ_MUST_USE
bool putNew(const Lookup
& aLookup
, U
&& aU
) {
545 return mImpl
.putNew(aLookup
, std::forward
<U
>(aU
));
548 // Like putNew(), but should be only used when the table is known to be big
549 // enough for the insertion, and hashing cannot fail. Typically this is used
550 // to populate an empty set with known-unique elements after reserving space
551 // with reserve(), e.g.
553 // using HS = HashMap<int>;
555 // if (!h.reserve(3)) {
558 // h.putNewInfallible(1); // unique element
559 // h.putNewInfallible(2); // unique element
560 // h.putNewInfallible(3); // unique element
562 template <typename U
>
563 void putNewInfallible(const Lookup
& aLookup
, U
&& aU
) {
564 mImpl
.putNewInfallible(aLookup
, std::forward
<U
>(aU
));
567 // Like |lookup(l)|, but on miss, |p = lookupForAdd(l)| allows efficient
568 // insertion of T value |t| (where |HashPolicy::match(t,l) == true|) using
569 // |add(p,t)|. After |add(p,t)|, |p| points to the new element. E.g.:
571 // using HS = HashSet<int>;
573 // HS::AddPtr p = h.lookupForAdd(3);
575 // if (!h.add(p, 3)) {
579 // assert(*p == 3); // p acts like a pointer to int
581 // N.B. The caller must ensure that no mutating hash table operations occur
582 // between a pair of lookupForAdd() and add() calls. To avoid looking up the
583 // key a second time, the caller may use the more efficient relookupOrAdd()
584 // method. This method reuses part of the hashing computation to more
585 // efficiently insert the key if it has not been added. For example, a
586 // mutation-handling version of the previous example:
588 // HS::AddPtr p = h.lookupForAdd(3);
590 // call_that_may_mutate_h();
591 // if (!h.relookupOrAdd(p, 3, 3)) {
597 // Note that relookupOrAdd(p,l,t) performs Lookup using |l| and adds the
598 // entry |t|, where the caller ensures match(l,t).
599 using AddPtr
= typename
Impl::AddPtr
;
600 MOZ_ALWAYS_INLINE AddPtr
lookupForAdd(const Lookup
& aLookup
) {
601 return mImpl
.lookupForAdd(aLookup
);
604 // Add an element. Returns false on OOM.
605 template <typename U
>
606 MOZ_MUST_USE
bool add(AddPtr
& aPtr
, U
&& aU
) {
607 return mImpl
.add(aPtr
, std::forward
<U
>(aU
));
610 // See the comment above lookupForAdd() for details.
611 template <typename U
>
612 MOZ_MUST_USE
bool relookupOrAdd(AddPtr
& aPtr
, const Lookup
& aLookup
, U
&& aU
) {
613 return mImpl
.relookupOrAdd(aPtr
, aLookup
, std::forward
<U
>(aU
));
616 // -- Removal --------------------------------------------------------------
618 // Lookup and remove the element matching |aLookup|, if present.
619 void remove(const Lookup
& aLookup
) {
620 if (Ptr p
= lookup(aLookup
)) {
625 // Remove a previously found element (assuming aPtr.found()). The set must
626 // not have been mutated in the interim.
627 void remove(Ptr aPtr
) { mImpl
.remove(aPtr
); }
629 // Remove all keys/values without changing the capacity.
630 void clear() { mImpl
.clear(); }
632 // Like clear() followed by compact().
633 void clearAndCompact() { mImpl
.clearAndCompact(); }
635 // -- Rekeying -------------------------------------------------------------
637 // Infallibly rekey one entry, if present. Requires that template parameters
638 // T and HashPolicy::Lookup are the same type.
639 void rekeyIfMoved(const Lookup
& aOldValue
, const T
& aNewValue
) {
640 if (aOldValue
!= aNewValue
) {
641 rekeyAs(aOldValue
, aNewValue
, aNewValue
);
645 // Infallibly rekey one entry if present, and return whether that happened.
646 bool rekeyAs(const Lookup
& aOldLookup
, const Lookup
& aNewLookup
,
647 const T
& aNewValue
) {
648 if (Ptr p
= lookup(aOldLookup
)) {
649 mImpl
.rekeyAndMaybeRehash(p
, aNewLookup
, aNewValue
);
655 // Infallibly replace the current key at |aPtr| with an equivalent key.
656 // Specifically, both HashPolicy::hash and HashPolicy::match must return
657 // identical results for the new and old key when applied against all
658 // possible matching values.
659 void replaceKey(Ptr aPtr
, const T
& aNewValue
) {
660 MOZ_ASSERT(aPtr
.found());
661 MOZ_ASSERT(*aPtr
!= aNewValue
);
662 MOZ_ASSERT(HashPolicy::hash(*aPtr
) == HashPolicy::hash(aNewValue
));
663 MOZ_ASSERT(HashPolicy::match(*aPtr
, aNewValue
));
664 const_cast<T
&>(*aPtr
) = aNewValue
;
667 // -- Iteration ------------------------------------------------------------
669 // |iter()| returns an Iterator:
672 // for (auto iter = h.iter(); !iter.done(); iter.next()) {
673 // int i = iter.get();
676 using Iterator
= typename
Impl::Iterator
;
677 Iterator
iter() const { return mImpl
.iter(); }
679 // |modIter()| returns a ModIterator:
682 // for (auto iter = h.modIter(); !iter.done(); iter.next()) {
683 // if (iter.get() == 42) {
688 // Table resize may occur in ModIterator's destructor.
689 using ModIterator
= typename
Impl::ModIterator
;
690 ModIterator
modIter() { return mImpl
.modIter(); }
692 // These are similar to Iterator/ModIterator/iter(), but use different
694 using Range
= typename
Impl::Range
;
695 using Enum
= typename
Impl::Enum
;
696 Range
all() const { return mImpl
.all(); }
699 //---------------------------------------------------------------------------
701 //---------------------------------------------------------------------------
703 // A hash policy |HP| for a hash table with key-type |Key| must provide:
705 // - a type |HP::Lookup| to use to lookup table entries;
707 // - a static member function |HP::hash| that hashes lookup values:
709 // static mozilla::HashNumber hash(const Lookup&);
711 // - a static member function |HP::match| that tests equality of key and
714 // static bool match(const Key&, const Lookup&);
716 // Normally, Lookup = Key. In general, though, different values and types of
717 // values can be used to lookup and store. If a Lookup value |l| is not equal
718 // to the added Key value |k|, the user must ensure that |HP::match(k,l)| is
721 // mozilla::HashSet<Key, HP>::AddPtr p = h.lookup(l);
723 // assert(HP::match(k, l)); // must hold
727 // A pointer hashing policy that uses HashGeneric() to create good hashes for
728 // pointers. Note that we don't shift out the lowest k bits because we don't
729 // want to assume anything about the alignment of the pointers.
730 template <typename Key
>
731 struct PointerHasher
{
734 static HashNumber
hash(const Lookup
& aLookup
) {
735 size_t word
= reinterpret_cast<size_t>(aLookup
);
736 return HashGeneric(word
);
739 static bool match(const Key
& aKey
, const Lookup
& aLookup
) {
740 return aKey
== aLookup
;
743 static void rekey(Key
& aKey
, const Key
& aNewKey
) { aKey
= aNewKey
; }
746 // The default hash policy, which only works with integers.
748 struct DefaultHasher
{
751 static HashNumber
hash(const Lookup
& aLookup
) {
752 // Just convert the integer to a HashNumber and use that as is. (This
753 // discards the high 32-bits of 64-bit integers!) ScrambleHashCode() is
754 // subsequently called on the value to improve the distribution.
758 static bool match(const Key
& aKey
, const Lookup
& aLookup
) {
759 // Use builtin or overloaded operator==.
760 return aKey
== aLookup
;
763 static void rekey(Key
& aKey
, const Key
& aNewKey
) { aKey
= aNewKey
; }
766 // A DefaultHasher specialization for pointers.
768 struct DefaultHasher
<T
*> : PointerHasher
<T
*> {};
770 // A DefaultHasher specialization for mozilla::UniquePtr.
771 template <class T
, class D
>
772 struct DefaultHasher
<UniquePtr
<T
, D
>> {
773 using Key
= UniquePtr
<T
, D
>;
775 using PtrHasher
= PointerHasher
<T
*>;
777 static HashNumber
hash(const Lookup
& aLookup
) {
778 return PtrHasher::hash(aLookup
.get());
781 static bool match(const Key
& aKey
, const Lookup
& aLookup
) {
782 return PtrHasher::match(aKey
.get(), aLookup
.get());
785 static void rekey(UniquePtr
<T
, D
>& aKey
, UniquePtr
<T
, D
>&& aNewKey
) {
786 aKey
= std::move(aNewKey
);
790 // A DefaultHasher specialization for doubles.
792 struct DefaultHasher
<double> {
796 static HashNumber
hash(const Lookup
& aLookup
) {
797 // Just xor the high bits with the low bits, and then treat the bits of the
798 // result as a uint32_t.
799 static_assert(sizeof(HashNumber
) == 4,
800 "subsequent code assumes a four-byte hash");
801 uint64_t u
= BitwiseCast
<uint64_t>(aLookup
);
802 return HashNumber(u
^ (u
>> 32));
805 static bool match(const Key
& aKey
, const Lookup
& aLookup
) {
806 return BitwiseCast
<uint64_t>(aKey
) == BitwiseCast
<uint64_t>(aLookup
);
810 // A DefaultHasher specialization for floats.
812 struct DefaultHasher
<float> {
816 static HashNumber
hash(const Lookup
& aLookup
) {
817 // Just use the value as if its bits form an integer. ScrambleHashCode() is
818 // subsequently called on the value to improve the distribution.
819 static_assert(sizeof(HashNumber
) == 4,
820 "subsequent code assumes a four-byte hash");
821 return HashNumber(BitwiseCast
<uint32_t>(aLookup
));
824 static bool match(const Key
& aKey
, const Lookup
& aLookup
) {
825 return BitwiseCast
<uint32_t>(aKey
) == BitwiseCast
<uint32_t>(aLookup
);
829 // A hash policy for C strings.
830 struct CStringHasher
{
831 using Key
= const char*;
832 using Lookup
= const char*;
834 static HashNumber
hash(const Lookup
& aLookup
) { return HashString(aLookup
); }
836 static bool match(const Key
& aKey
, const Lookup
& aLookup
) {
837 return strcmp(aKey
, aLookup
) == 0;
841 //---------------------------------------------------------------------------
842 // Fallible Hashing Interface
843 //---------------------------------------------------------------------------
845 // Most of the time generating a hash code is infallible so this class provides
846 // default methods that always succeed. Specialize this class for your own hash
847 // policy to provide fallible hashing.
849 // This is used by MovableCellHasher to handle the fact that generating a unique
850 // ID for cell pointer may fail due to OOM.
851 template <typename HashPolicy
>
852 struct FallibleHashMethods
{
853 // Return true if a hashcode is already available for its argument. Once
854 // this returns true for a specific argument it must continue to do so.
855 template <typename Lookup
>
856 static bool hasHash(Lookup
&& aLookup
) {
860 // Fallible method to ensure a hashcode exists for its argument and create
861 // one if not. Returns false on error, e.g. out of memory.
862 template <typename Lookup
>
863 static bool ensureHash(Lookup
&& aLookup
) {
868 template <typename HashPolicy
, typename Lookup
>
869 static bool HasHash(Lookup
&& aLookup
) {
870 return FallibleHashMethods
<typename
HashPolicy::Base
>::hasHash(
871 std::forward
<Lookup
>(aLookup
));
874 template <typename HashPolicy
, typename Lookup
>
875 static bool EnsureHash(Lookup
&& aLookup
) {
876 return FallibleHashMethods
<typename
HashPolicy::Base
>::ensureHash(
877 std::forward
<Lookup
>(aLookup
));
880 //---------------------------------------------------------------------------
881 // Implementation Details (HashMapEntry, HashTableEntry, HashTable)
882 //---------------------------------------------------------------------------
884 // Both HashMap and HashSet are implemented by a single HashTable that is even
885 // more heavily parameterized than the other two. This leaves HashTable gnarly
886 // and extremely coupled to HashMap and HashSet; thus code should not use
887 // HashTable directly.
889 template <class Key
, class Value
>
894 template <class, class, class>
895 friend class detail::HashTable
;
897 friend class detail::HashTableEntry
;
898 template <class, class, class, class>
899 friend class HashMap
;
902 template <typename KeyInput
, typename ValueInput
>
903 HashMapEntry(KeyInput
&& aKey
, ValueInput
&& aValue
)
904 : key_(std::forward
<KeyInput
>(aKey
)),
905 value_(std::forward
<ValueInput
>(aValue
)) {}
907 HashMapEntry(HashMapEntry
&& aRhs
) = default;
908 HashMapEntry
& operator=(HashMapEntry
&& aRhs
) = default;
911 using ValueType
= Value
;
913 const Key
& key() const { return key_
; }
915 // Use this method with caution! If the key is changed such that its hash
916 // value also changes, the map will be left in an invalid state.
917 Key
& mutableKey() { return key_
; }
919 const Value
& value() const { return value_
; }
920 Value
& value() { return value_
; }
923 HashMapEntry(const HashMapEntry
&) = delete;
924 void operator=(const HashMapEntry
&) = delete;
929 template <class T
, class HashPolicy
, class AllocPolicy
>
932 template <typename T
>
935 template <typename T
>
936 class HashTableEntry
{
938 using NonConstT
= std::remove_const_t
<T
>;
940 // Instead of having a hash table entry store that looks like this:
942 // +--------+--------+--------+--------+
943 // | entry0 | entry1 | .... | entryN |
944 // +--------+--------+--------+--------+
946 // where the entries contained their cached hash code, we're going to lay out
947 // the entry store thusly:
949 // +-------+-------+-------+-------+--------+--------+--------+--------+
950 // | hash0 | hash1 | ... | hashN | entry0 | entry1 | .... | entryN |
951 // +-------+-------+-------+-------+--------+--------+--------+--------+
953 // with all the cached hashes prior to the actual entries themselves.
955 // We do this because implementing the first strategy requires us to make
956 // HashTableEntry look roughly like:
958 // template <typename T>
959 // class HashTableEntry {
960 // HashNumber mKeyHash;
964 // The problem with this setup is that, depending on the layout of `T`, there
965 // may be platform ABI-mandated padding between `mKeyHash` and the first
966 // member of `T`. This ABI-mandated padding is wasted space, and can be
967 // surprisingly common, e.g. when `T` is a single pointer on 64-bit platforms.
968 // In such cases, we're throwing away a quarter of our entry store on padding,
969 // which is undesirable.
971 // The second layout above, namely:
973 // +-------+-------+-------+-------+--------+--------+--------+--------+
974 // | hash0 | hash1 | ... | hashN | entry0 | entry1 | .... | entryN |
975 // +-------+-------+-------+-------+--------+--------+--------+--------+
977 // means there is no wasted space between the hashes themselves, and no wasted
978 // space between the entries themselves. However, we would also like there to
979 // be no gap between the last hash and the first entry. The memory allocator
980 // guarantees the alignment of the start of the hashes. The use of a
981 // power-of-two capacity of at least 4 guarantees that the alignment of the
982 // *end* of the hash array is no less than the alignment of the start.
983 // Finally, the static_asserts here guarantee that the entries themselves
984 // don't need to be any more aligned than the alignment of the entry store
987 // This assertion is safe for 32-bit builds because on both Windows and Linux
988 // (including Android), the minimum alignment for allocations larger than 8
989 // bytes is 8 bytes, and the actual data for entries in our entry store is
990 // guaranteed to have that alignment as well, thanks to the power-of-two
991 // number of cached hash values stored prior to the entry data.
993 // The allocation policy must allocate a table with at least this much
995 static constexpr size_t kMinimumAlignment
= 8;
997 static_assert(alignof(HashNumber
) <= kMinimumAlignment
,
998 "[N*2 hashes, N*2 T values] allocation's alignment must be "
999 "enough to align each hash");
1000 static_assert(alignof(NonConstT
) <= 2 * sizeof(HashNumber
),
1001 "subsequent N*2 T values must not require more than an even "
1002 "number of HashNumbers provides");
1004 static const HashNumber sFreeKey
= 0;
1005 static const HashNumber sRemovedKey
= 1;
1006 static const HashNumber sCollisionBit
= 1;
1008 alignas(NonConstT
) unsigned char mValueData
[sizeof(NonConstT
)];
1011 template <class, class, class>
1012 friend class HashTable
;
1014 friend class EntrySlot
;
1016 // Some versions of GCC treat it as a -Wstrict-aliasing violation (ergo a
1017 // -Werror compile error) to reinterpret_cast<> |mValueData| to |T*|, even
1018 // through |void*|. Placing the latter cast in these separate functions
1019 // breaks the chain such that affected GCC versions no longer warn/error.
1020 void* rawValuePtr() { return mValueData
; }
1022 static bool isLiveHash(HashNumber hash
) { return hash
> sRemovedKey
; }
1024 HashTableEntry(const HashTableEntry
&) = delete;
1025 void operator=(const HashTableEntry
&) = delete;
1027 NonConstT
* valuePtr() { return reinterpret_cast<NonConstT
*>(rawValuePtr()); }
1029 void destroyStoredT() {
1030 NonConstT
* ptr
= valuePtr();
1032 MOZ_MAKE_MEM_UNDEFINED(ptr
, sizeof(*ptr
));
1036 HashTableEntry() = default;
1038 ~HashTableEntry() { MOZ_MAKE_MEM_UNDEFINED(this, sizeof(*this)); }
1040 void destroy() { destroyStoredT(); }
1042 void swap(HashTableEntry
* aOther
, bool aIsLive
) {
1043 // This allows types to use Argument-Dependent-Lookup, and thus use a custom
1044 // std::swap, which is needed by types like JS::Heap and such.
1047 if (this == aOther
) {
1051 swap(*valuePtr(), *aOther
->valuePtr());
1053 *aOther
->valuePtr() = std::move(*valuePtr());
1058 T
& get() { return *valuePtr(); }
1060 NonConstT
& getMutable() { return *valuePtr(); }
1063 // A slot represents a cached hash value and its associated entry stored
1064 // in the hash table. These two things are not stored in contiguous memory.
1067 using NonConstT
= std::remove_const_t
<T
>;
1069 using Entry
= HashTableEntry
<T
>;
1072 HashNumber
* mKeyHash
;
1074 template <class, class, class>
1075 friend class HashTable
;
1077 EntrySlot(Entry
* aEntry
, HashNumber
* aKeyHash
)
1078 : mEntry(aEntry
), mKeyHash(aKeyHash
) {}
1081 static bool isLiveHash(HashNumber hash
) { return hash
> Entry::sRemovedKey
; }
1083 EntrySlot(const EntrySlot
&) = default;
1084 EntrySlot(EntrySlot
&& aOther
) = default;
1086 EntrySlot
& operator=(const EntrySlot
&) = default;
1087 EntrySlot
& operator=(EntrySlot
&&) = default;
1089 bool operator==(const EntrySlot
& aRhs
) const { return mEntry
== aRhs
.mEntry
; }
1091 bool operator<(const EntrySlot
& aRhs
) const { return mEntry
< aRhs
.mEntry
; }
1093 EntrySlot
& operator++() {
1099 void destroy() { mEntry
->destroy(); }
1101 void swap(EntrySlot
& aOther
) {
1102 mEntry
->swap(aOther
.mEntry
, aOther
.isLive());
1103 std::swap(*mKeyHash
, *aOther
.mKeyHash
);
1106 T
& get() const { return mEntry
->get(); }
1108 NonConstT
& getMutable() { return mEntry
->getMutable(); }
1110 bool isFree() const { return *mKeyHash
== Entry::sFreeKey
; }
1113 MOZ_ASSERT(isLive());
1114 *mKeyHash
= Entry::sFreeKey
;
1115 mEntry
->destroyStoredT();
1120 mEntry
->destroyStoredT();
1122 MOZ_MAKE_MEM_UNDEFINED(mEntry
, sizeof(*mEntry
));
1123 *mKeyHash
= Entry::sFreeKey
;
1126 bool isRemoved() const { return *mKeyHash
== Entry::sRemovedKey
; }
1129 MOZ_ASSERT(isLive());
1130 *mKeyHash
= Entry::sRemovedKey
;
1131 mEntry
->destroyStoredT();
1134 bool isLive() const { return isLiveHash(*mKeyHash
); }
1136 void setCollision() {
1137 MOZ_ASSERT(isLive());
1138 *mKeyHash
|= Entry::sCollisionBit
;
1140 void unsetCollision() { *mKeyHash
&= ~Entry::sCollisionBit
; }
1141 bool hasCollision() const { return *mKeyHash
& Entry::sCollisionBit
; }
1142 bool matchHash(HashNumber hn
) {
1143 return (*mKeyHash
& ~Entry::sCollisionBit
) == hn
;
1145 HashNumber
getKeyHash() const { return *mKeyHash
& ~Entry::sCollisionBit
; }
1147 template <typename
... Args
>
1148 void setLive(HashNumber aHashNumber
, Args
&&... aArgs
) {
1149 MOZ_ASSERT(!isLive());
1150 *mKeyHash
= aHashNumber
;
1151 new (KnownNotNull
, mEntry
->valuePtr()) T(std::forward
<Args
>(aArgs
)...);
1152 MOZ_ASSERT(isLive());
1155 Entry
* toEntry() const { return mEntry
; }
1158 template <class T
, class HashPolicy
, class AllocPolicy
>
1159 class HashTable
: private AllocPolicy
{
1160 friend class mozilla::ReentrancyGuard
;
1162 using NonConstT
= std::remove_const_t
<T
>;
1163 using Key
= typename
HashPolicy::KeyType
;
1164 using Lookup
= typename
HashPolicy::Lookup
;
1167 using Entry
= HashTableEntry
<T
>;
1168 using Slot
= EntrySlot
<T
>;
1170 template <typename F
>
1171 static void forEachSlot(char* aTable
, uint32_t aCapacity
, F
&& f
) {
1172 auto hashes
= reinterpret_cast<HashNumber
*>(aTable
);
1173 auto entries
= reinterpret_cast<Entry
*>(&hashes
[aCapacity
]);
1174 Slot
slot(entries
, hashes
);
1175 for (size_t i
= 0; i
< size_t(aCapacity
); ++i
) {
1181 // A nullable pointer to a hash table element. A Ptr |p| can be tested
1182 // either explicitly |if (p.found()) p->...| or using boolean conversion
1183 // |if (p) p->...|. Ptr objects must not be used after any mutating hash
1184 // table operations unless |generation()| is tested.
1186 friend class HashTable
;
1190 const HashTable
* mTable
;
1191 Generation mGeneration
;
1195 Ptr(Slot aSlot
, const HashTable
& aTable
)
1200 mGeneration(aTable
.generation())
1205 // This constructor is used only by AddPtr() within lookupForAdd().
1206 explicit Ptr(const HashTable
& aTable
)
1207 : mSlot(nullptr, nullptr)
1211 mGeneration(aTable
.generation())
1216 bool isValid() const { return !!mSlot
.toEntry(); }
1220 : mSlot(nullptr, nullptr)
1229 bool found() const {
1234 MOZ_ASSERT(mGeneration
== mTable
->generation());
1236 return mSlot
.isLive();
1239 explicit operator bool() const { return found(); }
1241 bool operator==(const Ptr
& aRhs
) const {
1242 MOZ_ASSERT(found() && aRhs
.found());
1243 return mSlot
== aRhs
.mSlot
;
1246 bool operator!=(const Ptr
& aRhs
) const {
1248 MOZ_ASSERT(mGeneration
== mTable
->generation());
1250 return !(*this == aRhs
);
1253 T
& operator*() const {
1255 MOZ_ASSERT(found());
1256 MOZ_ASSERT(mGeneration
== mTable
->generation());
1261 T
* operator->() const {
1263 MOZ_ASSERT(found());
1264 MOZ_ASSERT(mGeneration
== mTable
->generation());
1266 return &mSlot
.get();
1270 // A Ptr that can be used to add a key after a failed lookup.
1271 class AddPtr
: public Ptr
{
1272 friend class HashTable
;
1274 HashNumber mKeyHash
;
1276 uint64_t mMutationCount
;
1279 AddPtr(Slot aSlot
, const HashTable
& aTable
, HashNumber aHashNumber
)
1280 : Ptr(aSlot
, aTable
),
1281 mKeyHash(aHashNumber
)
1284 mMutationCount(aTable
.mMutationCount
)
1289 // This constructor is used when lookupForAdd() is performed on a table
1290 // lacking entry storage; it leaves mSlot null but initializes everything
1292 AddPtr(const HashTable
& aTable
, HashNumber aHashNumber
)
1294 mKeyHash(aHashNumber
)
1297 mMutationCount(aTable
.mMutationCount
)
1300 MOZ_ASSERT(isLive());
1303 bool isLive() const { return isLiveHash(mKeyHash
); }
1306 AddPtr() : mKeyHash(0) {}
1309 // A hash table iterator that (mostly) doesn't allow table modifications.
1310 // As with Ptr/AddPtr, Iterator objects must not be used after any mutating
1311 // hash table operation unless the |generation()| is tested.
1313 void moveToNextLiveEntry() {
1314 while (++mCur
< mEnd
&& !mCur
.isLive()) {
1320 friend class HashTable
;
1322 explicit Iterator(const HashTable
& aTable
)
1323 : mCur(aTable
.slotForIndex(0)),
1324 mEnd(aTable
.slotForIndex(aTable
.capacity()))
1328 mMutationCount(aTable
.mMutationCount
),
1329 mGeneration(aTable
.generation()),
1333 if (!done() && !mCur
.isLive()) {
1334 moveToNextLiveEntry();
1341 const HashTable
& mTable
;
1342 uint64_t mMutationCount
;
1343 Generation mGeneration
;
1349 MOZ_ASSERT(mGeneration
== mTable
.generation());
1350 MOZ_ASSERT(mMutationCount
== mTable
.mMutationCount
);
1351 return mCur
== mEnd
;
1355 MOZ_ASSERT(!done());
1356 MOZ_ASSERT(mValidEntry
);
1357 MOZ_ASSERT(mGeneration
== mTable
.generation());
1358 MOZ_ASSERT(mMutationCount
== mTable
.mMutationCount
);
1363 MOZ_ASSERT(!done());
1364 MOZ_ASSERT(mGeneration
== mTable
.generation());
1365 MOZ_ASSERT(mMutationCount
== mTable
.mMutationCount
);
1366 moveToNextLiveEntry();
1373 // A hash table iterator that permits modification, removal and rekeying.
1374 // Since rehashing when elements were removed during enumeration would be
1375 // bad, it is postponed until the ModIterator is destructed. Since the
1376 // ModIterator's destructor touches the hash table, the user must ensure
1377 // that the hash table is still alive when the destructor runs.
1378 class ModIterator
: public Iterator
{
1379 friend class HashTable
;
1385 // ModIterator is movable but not copyable.
1386 ModIterator(const ModIterator
&) = delete;
1387 void operator=(const ModIterator
&) = delete;
1390 explicit ModIterator(HashTable
& aTable
)
1391 : Iterator(aTable
), mTable(aTable
), mRekeyed(false), mRemoved(false) {}
1394 MOZ_IMPLICIT
ModIterator(ModIterator
&& aOther
)
1396 mTable(aOther
.mTable
),
1397 mRekeyed(aOther
.mRekeyed
),
1398 mRemoved(aOther
.mRemoved
) {
1399 aOther
.mRekeyed
= false;
1400 aOther
.mRemoved
= false;
1403 // Removes the current element from the table, leaving |get()|
1404 // invalid until the next call to |next()|.
1406 mTable
.remove(this->mCur
);
1409 this->mValidEntry
= false;
1410 this->mMutationCount
= mTable
.mMutationCount
;
1414 NonConstT
& getMutable() {
1415 MOZ_ASSERT(!this->done());
1416 MOZ_ASSERT(this->mValidEntry
);
1417 MOZ_ASSERT(this->mGeneration
== this->Iterator::mTable
.generation());
1418 MOZ_ASSERT(this->mMutationCount
== this->Iterator::mTable
.mMutationCount
);
1419 return this->mCur
.getMutable();
1422 // Removes the current element and re-inserts it into the table with
1423 // a new key at the new Lookup position. |get()| is invalid after
1424 // this operation until the next call to |next()|.
1425 void rekey(const Lookup
& l
, const Key
& k
) {
1426 MOZ_ASSERT(&k
!= &HashPolicy::getKey(this->mCur
.get()));
1427 Ptr
p(this->mCur
, mTable
);
1428 mTable
.rekeyWithoutRehash(p
, l
, k
);
1431 this->mValidEntry
= false;
1432 this->mMutationCount
= mTable
.mMutationCount
;
1436 void rekey(const Key
& k
) { rekey(k
, k
); }
1438 // Potentially rehashes the table.
1442 mTable
.infallibleRehashIfOverloaded();
1451 // Range is similar to Iterator, but uses different terminology.
1453 friend class HashTable
;
1458 explicit Range(const HashTable
& table
) : mIter(table
) {}
1461 bool empty() const { return mIter
.done(); }
1463 T
& front() const { return mIter
.get(); }
1465 void popFront() { return mIter
.next(); }
1468 // Enum is similar to ModIterator, but uses different terminology.
1472 // Enum is movable but not copyable.
1473 Enum(const Enum
&) = delete;
1474 void operator=(const Enum
&) = delete;
1477 template <class Map
>
1478 explicit Enum(Map
& map
) : mIter(map
.mImpl
) {}
1480 MOZ_IMPLICIT
Enum(Enum
&& other
) : mIter(std::move(other
.mIter
)) {}
1482 bool empty() const { return mIter
.done(); }
1484 T
& front() const { return mIter
.get(); }
1486 void popFront() { return mIter
.next(); }
1488 void removeFront() { mIter
.remove(); }
1490 NonConstT
& mutableFront() { return mIter
.getMutable(); }
1492 void rekeyFront(const Lookup
& aLookup
, const Key
& aKey
) {
1493 mIter
.rekey(aLookup
, aKey
);
1496 void rekeyFront(const Key
& aKey
) { mIter
.rekey(aKey
); }
1499 // HashTable is movable
1500 HashTable(HashTable
&& aRhs
) : AllocPolicy(std::move(aRhs
)) { moveFrom(aRhs
); }
1501 HashTable
& operator=(HashTable
&& aRhs
) {
1502 MOZ_ASSERT(this != &aRhs
, "self-move assignment is prohibited");
1504 destroyTable(*this, mTable
, capacity());
1506 AllocPolicy::operator=(std::move(aRhs
));
1512 void moveFrom(HashTable
& aRhs
) {
1514 mHashShift
= aRhs
.mHashShift
;
1515 mTable
= aRhs
.mTable
;
1516 mEntryCount
= aRhs
.mEntryCount
;
1517 mRemovedCount
= aRhs
.mRemovedCount
;
1519 mMutationCount
= aRhs
.mMutationCount
;
1520 mEntered
= aRhs
.mEntered
;
1522 aRhs
.mTable
= nullptr;
1523 aRhs
.clearAndCompact();
1526 // HashTable is not copyable or assignable
1527 HashTable(const HashTable
&) = delete;
1528 void operator=(const HashTable
&) = delete;
1530 static const uint32_t CAP_BITS
= 30;
1533 uint64_t mGen
: 56; // entry storage generation number
1534 uint64_t mHashShift
: 8; // multiplicative hash shift
1535 char* mTable
; // entry storage
1536 uint32_t mEntryCount
; // number of entries in mTable
1537 uint32_t mRemovedCount
; // removed entry sentinels in mTable
1540 uint64_t mMutationCount
;
1541 mutable bool mEntered
;
1544 // The default initial capacity is 32 (enough to hold 16 elements), but it
1545 // can be as low as 4.
1546 static const uint32_t sDefaultLen
= 16;
1547 static const uint32_t sMinCapacity
= 4;
1548 // See the comments in HashTableEntry about this value.
1549 static_assert(sMinCapacity
>= 4, "too-small sMinCapacity breaks assumptions");
1550 static const uint32_t sMaxInit
= 1u << (CAP_BITS
- 1);
1551 static const uint32_t sMaxCapacity
= 1u << CAP_BITS
;
1553 // Hash-table alpha is conceptually a fraction, but to avoid floating-point
1554 // math we implement it as a ratio of integers.
1555 static const uint8_t sAlphaDenominator
= 4;
1556 static const uint8_t sMinAlphaNumerator
= 1; // min alpha: 1/4
1557 static const uint8_t sMaxAlphaNumerator
= 3; // max alpha: 3/4
1559 static const HashNumber sFreeKey
= Entry::sFreeKey
;
1560 static const HashNumber sRemovedKey
= Entry::sRemovedKey
;
1561 static const HashNumber sCollisionBit
= Entry::sCollisionBit
;
1563 static uint32_t bestCapacity(uint32_t aLen
) {
1565 (sMaxInit
* sAlphaDenominator
) / sAlphaDenominator
== sMaxInit
,
1566 "multiplication in numerator below could overflow");
1568 sMaxInit
* sAlphaDenominator
<= UINT32_MAX
- sMaxAlphaNumerator
,
1569 "numerator calculation below could potentially overflow");
1571 // Callers should ensure this is true.
1572 MOZ_ASSERT(aLen
<= sMaxInit
);
1574 // Compute the smallest capacity allowing |aLen| elements to be
1575 // inserted without rehashing: ceil(aLen / max-alpha). (Ceiling
1576 // integral division: <http://stackoverflow.com/a/2745086>.)
1577 uint32_t capacity
= (aLen
* sAlphaDenominator
+ sMaxAlphaNumerator
- 1) /
1579 capacity
= (capacity
< sMinCapacity
) ? sMinCapacity
: RoundUpPow2(capacity
);
1581 MOZ_ASSERT(capacity
>= aLen
);
1582 MOZ_ASSERT(capacity
<= sMaxCapacity
);
1587 static uint32_t hashShift(uint32_t aLen
) {
1588 // Reject all lengths whose initial computed capacity would exceed
1589 // sMaxCapacity. Round that maximum aLen down to the nearest power of two
1590 // for speedier code.
1591 if (MOZ_UNLIKELY(aLen
> sMaxInit
)) {
1592 MOZ_CRASH("initial length is too large");
1595 return kHashNumberBits
- mozilla::CeilingLog2(bestCapacity(aLen
));
1598 static bool isLiveHash(HashNumber aHash
) { return Entry::isLiveHash(aHash
); }
1600 static HashNumber
prepareHash(const Lookup
& aLookup
) {
1601 HashNumber keyHash
= ScrambleHashCode(HashPolicy::hash(aLookup
));
1603 // Avoid reserved hash codes.
1604 if (!isLiveHash(keyHash
)) {
1605 keyHash
-= (sRemovedKey
+ 1);
1607 return keyHash
& ~sCollisionBit
;
1610 enum FailureBehavior
{ DontReportFailure
= false, ReportFailure
= true };
1612 // Fake a struct that we're going to alloc. See the comments in
1613 // HashTableEntry about how the table is laid out, and why it's safe.
1615 unsigned char c
[sizeof(HashNumber
) + sizeof(typename
Entry::NonConstT
)];
1618 static char* createTable(AllocPolicy
& aAllocPolicy
, uint32_t aCapacity
,
1619 FailureBehavior aReportFailure
= ReportFailure
) {
1622 ? aAllocPolicy
.template pod_malloc
<FakeSlot
>(aCapacity
)
1623 : aAllocPolicy
.template maybe_pod_malloc
<FakeSlot
>(aCapacity
);
1625 MOZ_ASSERT((reinterpret_cast<uintptr_t>(fake
) % Entry::kMinimumAlignment
) ==
1628 char* table
= reinterpret_cast<char*>(fake
);
1630 forEachSlot(table
, aCapacity
, [&](Slot
& slot
) {
1631 *slot
.mKeyHash
= sFreeKey
;
1632 new (KnownNotNull
, slot
.toEntry()) Entry();
1638 static void destroyTable(AllocPolicy
& aAllocPolicy
, char* aOldTable
,
1639 uint32_t aCapacity
) {
1640 forEachSlot(aOldTable
, aCapacity
, [&](const Slot
& slot
) {
1641 if (slot
.isLive()) {
1642 slot
.toEntry()->destroyStoredT();
1645 freeTable(aAllocPolicy
, aOldTable
, aCapacity
);
1648 static void freeTable(AllocPolicy
& aAllocPolicy
, char* aOldTable
,
1649 uint32_t aCapacity
) {
1650 FakeSlot
* fake
= reinterpret_cast<FakeSlot
*>(aOldTable
);
1651 aAllocPolicy
.free_(fake
, aCapacity
);
1655 HashTable(AllocPolicy aAllocPolicy
, uint32_t aLen
)
1656 : AllocPolicy(std::move(aAllocPolicy
)),
1658 mHashShift(hashShift(aLen
)),
1670 explicit HashTable(AllocPolicy aAllocPolicy
)
1671 : HashTable(aAllocPolicy
, sDefaultLen
) {}
1675 destroyTable(*this, mTable
, capacity());
1680 HashNumber
hash1(HashNumber aHash0
) const { return aHash0
>> mHashShift
; }
1684 HashNumber mSizeMask
;
1687 DoubleHash
hash2(HashNumber aCurKeyHash
) const {
1688 uint32_t sizeLog2
= kHashNumberBits
- mHashShift
;
1689 DoubleHash dh
= {((aCurKeyHash
<< sizeLog2
) >> mHashShift
) | 1,
1690 (HashNumber(1) << sizeLog2
) - 1};
1694 static HashNumber
applyDoubleHash(HashNumber aHash1
,
1695 const DoubleHash
& aDoubleHash
) {
1696 return WrappingSubtract(aHash1
, aDoubleHash
.mHash2
) & aDoubleHash
.mSizeMask
;
1699 static MOZ_ALWAYS_INLINE
bool match(T
& aEntry
, const Lookup
& aLookup
) {
1700 return HashPolicy::match(HashPolicy::getKey(aEntry
), aLookup
);
1703 enum LookupReason
{ ForNonAdd
, ForAdd
};
1705 Slot
slotForIndex(HashNumber aIndex
) const {
1706 auto hashes
= reinterpret_cast<HashNumber
*>(mTable
);
1707 auto entries
= reinterpret_cast<Entry
*>(&hashes
[capacity()]);
1708 return Slot(&entries
[aIndex
], &hashes
[aIndex
]);
1711 // Warning: in order for readonlyThreadsafeLookup() to be safe this
1712 // function must not modify the table in any way when Reason==ForNonAdd.
1713 template <LookupReason Reason
>
1714 MOZ_ALWAYS_INLINE Slot
lookup(const Lookup
& aLookup
,
1715 HashNumber aKeyHash
) const {
1716 MOZ_ASSERT(isLiveHash(aKeyHash
));
1717 MOZ_ASSERT(!(aKeyHash
& sCollisionBit
));
1720 // Compute the primary hash address.
1721 HashNumber h1
= hash1(aKeyHash
);
1722 Slot slot
= slotForIndex(h1
);
1724 // Miss: return space for a new entry.
1725 if (slot
.isFree()) {
1729 // Hit: return entry.
1730 if (slot
.matchHash(aKeyHash
) && match(slot
.get(), aLookup
)) {
1734 // Collision: double hash.
1735 DoubleHash dh
= hash2(aKeyHash
);
1737 // Save the first removed entry pointer so we can recycle later.
1738 Maybe
<Slot
> firstRemoved
;
1741 if (Reason
== ForAdd
&& !firstRemoved
) {
1742 if (MOZ_UNLIKELY(slot
.isRemoved())) {
1743 firstRemoved
.emplace(slot
);
1745 slot
.setCollision();
1749 h1
= applyDoubleHash(h1
, dh
);
1751 slot
= slotForIndex(h1
);
1752 if (slot
.isFree()) {
1753 return firstRemoved
.refOr(slot
);
1756 if (slot
.matchHash(aKeyHash
) && match(slot
.get(), aLookup
)) {
1762 // This is a copy of lookup() hardcoded to the assumptions:
1763 // 1. the lookup is for an add;
1764 // 2. the key, whose |keyHash| has been passed, is not in the table.
1765 Slot
findNonLiveSlot(HashNumber aKeyHash
) {
1766 MOZ_ASSERT(!(aKeyHash
& sCollisionBit
));
1769 // We assume 'aKeyHash' has already been distributed.
1771 // Compute the primary hash address.
1772 HashNumber h1
= hash1(aKeyHash
);
1773 Slot slot
= slotForIndex(h1
);
1775 // Miss: return space for a new entry.
1776 if (!slot
.isLive()) {
1780 // Collision: double hash.
1781 DoubleHash dh
= hash2(aKeyHash
);
1784 slot
.setCollision();
1786 h1
= applyDoubleHash(h1
, dh
);
1788 slot
= slotForIndex(h1
);
1789 if (!slot
.isLive()) {
1795 enum RebuildStatus
{ NotOverloaded
, Rehashed
, RehashFailed
};
1797 RebuildStatus
changeTableSize(
1798 uint32_t newCapacity
, FailureBehavior aReportFailure
= ReportFailure
) {
1799 MOZ_ASSERT(IsPowerOfTwo(newCapacity
));
1800 MOZ_ASSERT(!!mTable
== !!capacity());
1802 // Look, but don't touch, until we succeed in getting new entry store.
1803 char* oldTable
= mTable
;
1804 uint32_t oldCapacity
= capacity();
1805 uint32_t newLog2
= mozilla::CeilingLog2(newCapacity
);
1807 if (MOZ_UNLIKELY(newCapacity
> sMaxCapacity
)) {
1808 if (aReportFailure
) {
1809 this->reportAllocOverflow();
1811 return RehashFailed
;
1814 char* newTable
= createTable(*this, newCapacity
, aReportFailure
);
1816 return RehashFailed
;
1819 // We can't fail from here on, so update table parameters.
1820 mHashShift
= kHashNumberBits
- newLog2
;
1825 // Copy only live entries, leaving removed ones behind.
1826 forEachSlot(oldTable
, oldCapacity
, [&](Slot
& slot
) {
1827 if (slot
.isLive()) {
1828 HashNumber hn
= slot
.getKeyHash();
1829 findNonLiveSlot(hn
).setLive(
1830 hn
, std::move(const_cast<typename
Entry::NonConstT
&>(slot
.get())));
1836 // All entries have been destroyed, no need to destroyTable.
1837 freeTable(*this, oldTable
, oldCapacity
);
1841 RebuildStatus
rehashIfOverloaded(
1842 FailureBehavior aReportFailure
= ReportFailure
) {
1843 static_assert(sMaxCapacity
<= UINT32_MAX
/ sMaxAlphaNumerator
,
1844 "multiplication below could overflow");
1846 // Note: if capacity() is zero, this will always succeed, which is
1848 bool overloaded
= mEntryCount
+ mRemovedCount
>=
1849 capacity() * sMaxAlphaNumerator
/ sAlphaDenominator
;
1852 return NotOverloaded
;
1855 // Succeed if a quarter or more of all entries are removed. Note that this
1856 // always succeeds if capacity() == 0 (i.e. entry storage has not been
1857 // allocated), which is what we want, because it means changeTableSize()
1858 // will allocate the requested capacity rather than doubling it.
1859 bool manyRemoved
= mRemovedCount
>= (capacity() >> 2);
1860 uint32_t newCapacity
= manyRemoved
? rawCapacity() : rawCapacity() * 2;
1861 return changeTableSize(newCapacity
, aReportFailure
);
1864 void infallibleRehashIfOverloaded() {
1865 if (rehashIfOverloaded(DontReportFailure
) == RehashFailed
) {
1866 rehashTableInPlace();
1870 void remove(Slot
& aSlot
) {
1873 if (aSlot
.hasCollision()) {
1885 void shrinkIfUnderloaded() {
1886 static_assert(sMaxCapacity
<= UINT32_MAX
/ sMinAlphaNumerator
,
1887 "multiplication below could overflow");
1889 capacity() > sMinCapacity
&&
1890 mEntryCount
<= capacity() * sMinAlphaNumerator
/ sAlphaDenominator
;
1893 (void)changeTableSize(capacity() / 2, DontReportFailure
);
1897 // This is identical to changeTableSize(currentSize), but without requiring
1898 // a second table. We do this by recycling the collision bits to tell us if
1899 // the element is already inserted or still waiting to be inserted. Since
1900 // already-inserted elements win any conflicts, we get the same table as we
1901 // would have gotten through random insertion order.
1902 void rehashTableInPlace() {
1905 forEachSlot(mTable
, capacity(), [&](Slot
& slot
) { slot
.unsetCollision(); });
1906 for (uint32_t i
= 0; i
< capacity();) {
1907 Slot src
= slotForIndex(i
);
1909 if (!src
.isLive() || src
.hasCollision()) {
1914 HashNumber keyHash
= src
.getKeyHash();
1915 HashNumber h1
= hash1(keyHash
);
1916 DoubleHash dh
= hash2(keyHash
);
1917 Slot tgt
= slotForIndex(h1
);
1919 if (!tgt
.hasCollision()) {
1925 h1
= applyDoubleHash(h1
, dh
);
1926 tgt
= slotForIndex(h1
);
1930 // TODO: this algorithm leaves collision bits on *all* elements, even if
1931 // they are on no collision path. We have the option of setting the
1932 // collision bits correctly on a subsequent pass or skipping the rehash
1933 // unless we are totally filled with tombstones: benchmark to find out
1934 // which approach is best.
1937 // Note: |aLookup| may be a reference to a piece of |u|, so this function
1938 // must take care not to use |aLookup| after moving |u|.
1940 // Prefer to use putNewInfallible; this function does not check
1942 template <typename
... Args
>
1943 void putNewInfallibleInternal(const Lookup
& aLookup
, Args
&&... aArgs
) {
1946 HashNumber keyHash
= prepareHash(aLookup
);
1947 Slot slot
= findNonLiveSlot(keyHash
);
1949 if (slot
.isRemoved()) {
1951 keyHash
|= sCollisionBit
;
1954 slot
.setLive(keyHash
, std::forward
<Args
>(aArgs
)...);
1963 forEachSlot(mTable
, capacity(), [&](Slot
& slot
) { slot
.clear(); });
1971 // Resize the table down to the smallest capacity that doesn't overload the
1972 // table. Since we call shrinkIfUnderloaded() on every remove, you only need
1973 // to call this after a bulk removal of items done without calling remove().
1976 // Free the entry storage.
1977 freeTable(*this, mTable
, capacity());
1979 mHashShift
= hashShift(0); // gives minimum capacity on regrowth
1985 uint32_t bestCapacity
= this->bestCapacity(mEntryCount
);
1986 MOZ_ASSERT(bestCapacity
<= capacity());
1988 if (bestCapacity
< capacity()) {
1989 (void)changeTableSize(bestCapacity
, DontReportFailure
);
1993 void clearAndCompact() {
1998 MOZ_MUST_USE
bool reserve(uint32_t aLen
) {
2003 if (MOZ_UNLIKELY(aLen
> sMaxInit
)) {
2007 uint32_t bestCapacity
= this->bestCapacity(aLen
);
2008 if (bestCapacity
<= capacity()) {
2009 return true; // Capacity is already sufficient.
2012 RebuildStatus status
= changeTableSize(bestCapacity
, ReportFailure
);
2013 MOZ_ASSERT(status
!= NotOverloaded
);
2014 return status
!= RehashFailed
;
2017 Iterator
iter() const { return Iterator(*this); }
2019 ModIterator
modIter() { return ModIterator(*this); }
2021 Range
all() const { return Range(*this); }
2023 bool empty() const { return mEntryCount
== 0; }
2025 uint32_t count() const { return mEntryCount
; }
2027 uint32_t rawCapacity() const { return 1u << (kHashNumberBits
- mHashShift
); }
2029 uint32_t capacity() const { return mTable
? rawCapacity() : 0; }
2031 Generation
generation() const { return Generation(mGen
); }
2033 size_t shallowSizeOfExcludingThis(MallocSizeOf aMallocSizeOf
) const {
2034 return aMallocSizeOf(mTable
);
2037 size_t shallowSizeOfIncludingThis(MallocSizeOf aMallocSizeOf
) const {
2038 return aMallocSizeOf(this) + shallowSizeOfExcludingThis(aMallocSizeOf
);
2041 MOZ_ALWAYS_INLINE Ptr
readonlyThreadsafeLookup(const Lookup
& aLookup
) const {
2042 if (empty() || !HasHash
<HashPolicy
>(aLookup
)) {
2045 HashNumber keyHash
= prepareHash(aLookup
);
2046 return Ptr(lookup
<ForNonAdd
>(aLookup
, keyHash
), *this);
2049 MOZ_ALWAYS_INLINE Ptr
lookup(const Lookup
& aLookup
) const {
2050 ReentrancyGuard
g(*this);
2051 return readonlyThreadsafeLookup(aLookup
);
2054 MOZ_ALWAYS_INLINE AddPtr
lookupForAdd(const Lookup
& aLookup
) {
2055 ReentrancyGuard
g(*this);
2056 if (!EnsureHash
<HashPolicy
>(aLookup
)) {
2060 HashNumber keyHash
= prepareHash(aLookup
);
2063 return AddPtr(*this, keyHash
);
2066 // Directly call the constructor in the return statement to avoid
2067 // excess copying when building with Visual Studio 2017.
2069 return AddPtr(lookup
<ForAdd
>(aLookup
, keyHash
), *this, keyHash
);
2072 template <typename
... Args
>
2073 MOZ_MUST_USE
bool add(AddPtr
& aPtr
, Args
&&... aArgs
) {
2074 ReentrancyGuard
g(*this);
2075 MOZ_ASSERT_IF(aPtr
.isValid(), mTable
);
2076 MOZ_ASSERT_IF(aPtr
.isValid(), aPtr
.mTable
== this);
2077 MOZ_ASSERT(!aPtr
.found());
2078 MOZ_ASSERT(!(aPtr
.mKeyHash
& sCollisionBit
));
2080 // Check for error from ensureHash() here.
2081 if (!aPtr
.isLive()) {
2085 MOZ_ASSERT(aPtr
.mGeneration
== generation());
2087 MOZ_ASSERT(aPtr
.mMutationCount
== mMutationCount
);
2090 if (!aPtr
.isValid()) {
2091 MOZ_ASSERT(!mTable
&& mEntryCount
== 0);
2092 uint32_t newCapacity
= rawCapacity();
2093 RebuildStatus status
= changeTableSize(newCapacity
, ReportFailure
);
2094 MOZ_ASSERT(status
!= NotOverloaded
);
2095 if (status
== RehashFailed
) {
2098 aPtr
.mSlot
= findNonLiveSlot(aPtr
.mKeyHash
);
2100 } else if (aPtr
.mSlot
.isRemoved()) {
2101 // Changing an entry from removed to live does not affect whether we are
2102 // overloaded and can be handled separately.
2103 if (!this->checkSimulatedOOM()) {
2107 aPtr
.mKeyHash
|= sCollisionBit
;
2110 // Preserve the validity of |aPtr.mSlot|.
2111 RebuildStatus status
= rehashIfOverloaded();
2112 if (status
== RehashFailed
) {
2115 if (status
== NotOverloaded
&& !this->checkSimulatedOOM()) {
2118 if (status
== Rehashed
) {
2119 aPtr
.mSlot
= findNonLiveSlot(aPtr
.mKeyHash
);
2123 aPtr
.mSlot
.setLive(aPtr
.mKeyHash
, std::forward
<Args
>(aArgs
)...);
2127 aPtr
.mGeneration
= generation();
2128 aPtr
.mMutationCount
= mMutationCount
;
2133 // Note: |aLookup| may be a reference to a piece of |u|, so this function
2134 // must take care not to use |aLookup| after moving |u|.
2135 template <typename
... Args
>
2136 void putNewInfallible(const Lookup
& aLookup
, Args
&&... aArgs
) {
2137 MOZ_ASSERT(!lookup(aLookup
).found());
2138 ReentrancyGuard
g(*this);
2139 putNewInfallibleInternal(aLookup
, std::forward
<Args
>(aArgs
)...);
2142 // Note: |aLookup| may be alias arguments in |aArgs|, so this function must
2143 // take care not to use |aLookup| after moving |aArgs|.
2144 template <typename
... Args
>
2145 MOZ_MUST_USE
bool putNew(const Lookup
& aLookup
, Args
&&... aArgs
) {
2146 if (!this->checkSimulatedOOM()) {
2149 if (!EnsureHash
<HashPolicy
>(aLookup
)) {
2152 if (rehashIfOverloaded() == RehashFailed
) {
2155 putNewInfallible(aLookup
, std::forward
<Args
>(aArgs
)...);
2159 // Note: |aLookup| may be a reference to a piece of |u|, so this function
2160 // must take care not to use |aLookup| after moving |u|.
2161 template <typename
... Args
>
2162 MOZ_MUST_USE
bool relookupOrAdd(AddPtr
& aPtr
, const Lookup
& aLookup
,
2164 // Check for error from ensureHash() here.
2165 if (!aPtr
.isLive()) {
2169 aPtr
.mGeneration
= generation();
2170 aPtr
.mMutationCount
= mMutationCount
;
2173 ReentrancyGuard
g(*this);
2174 // Check that aLookup has not been destroyed.
2175 MOZ_ASSERT(prepareHash(aLookup
) == aPtr
.mKeyHash
);
2176 aPtr
.mSlot
= lookup
<ForAdd
>(aLookup
, aPtr
.mKeyHash
);
2181 // Clear aPtr so it's invalid; add() will allocate storage and redo the
2183 aPtr
.mSlot
= Slot(nullptr, nullptr);
2185 return add(aPtr
, std::forward
<Args
>(aArgs
)...);
2188 void remove(Ptr aPtr
) {
2190 ReentrancyGuard
g(*this);
2191 MOZ_ASSERT(aPtr
.found());
2192 MOZ_ASSERT(aPtr
.mGeneration
== generation());
2194 shrinkIfUnderloaded();
2197 void rekeyWithoutRehash(Ptr aPtr
, const Lookup
& aLookup
, const Key
& aKey
) {
2199 ReentrancyGuard
g(*this);
2200 MOZ_ASSERT(aPtr
.found());
2201 MOZ_ASSERT(aPtr
.mGeneration
== generation());
2202 typename HashTableEntry
<T
>::NonConstT
t(std::move(*aPtr
));
2203 HashPolicy::setKey(t
, const_cast<Key
&>(aKey
));
2205 putNewInfallibleInternal(aLookup
, std::move(t
));
2208 void rekeyAndMaybeRehash(Ptr aPtr
, const Lookup
& aLookup
, const Key
& aKey
) {
2209 rekeyWithoutRehash(aPtr
, aLookup
, aKey
);
2210 infallibleRehashIfOverloaded();
2214 } // namespace detail
2215 } // namespace mozilla
2217 #endif /* mozilla_HashTable_h */