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
77 #include "mozilla/AllocPolicy.h"
78 #include "mozilla/Assertions.h"
79 #include "mozilla/Attributes.h"
80 #include "mozilla/Casting.h"
81 #include "mozilla/HashFunctions.h"
82 #include "mozilla/MathAlgorithms.h"
83 #include "mozilla/Maybe.h"
84 #include "mozilla/MemoryChecking.h"
85 #include "mozilla/MemoryReporting.h"
86 #include "mozilla/Move.h"
87 #include "mozilla/Opaque.h"
88 #include "mozilla/OperatorNewExtensions.h"
89 #include "mozilla/PodOperations.h"
90 #include "mozilla/ReentrancyGuard.h"
91 #include "mozilla/TypeTraits.h"
92 #include "mozilla/UniquePtr.h"
99 template <class, class>
104 template <typename T
>
105 class HashTableEntry
;
107 template <class T
, class HashPolicy
, class AllocPolicy
>
110 } // namespace detail
112 // The "generation" of a hash table is an opaque value indicating the state of
113 // modification of the hash table through its lifetime. If the generation of
114 // a hash table compares equal at times T1 and T2, then lookups in the hash
115 // table, pointers to (or into) hash table entries, etc. at time T1 are valid
116 // at time T2. If the generation compares unequal, these computations are all
117 // invalid and must be performed again to be used.
119 // Generations are meaningfully comparable only with respect to a single hash
120 // table. It's always nonsensical to compare the generation of distinct hash
122 using Generation
= Opaque
<uint64_t>;
124 //---------------------------------------------------------------------------
126 //---------------------------------------------------------------------------
128 // HashMap is a fast hash-based map from keys to values.
130 // Template parameter requirements:
131 // - Key/Value: movable, destructible, assignable.
132 // - HashPolicy: see the "Hash Policy" section below.
133 // - AllocPolicy: see AllocPolicy.h.
136 // - HashMap is not reentrant: Key/Value/HashPolicy/AllocPolicy members
137 // called by HashMap must not call back into the same HashMap object.
139 template <class Key
, class Value
, class HashPolicy
= DefaultHasher
<Key
>,
140 class AllocPolicy
= MallocAllocPolicy
>
142 // -- Implementation details -----------------------------------------------
144 // HashMap is not copyable or assignable.
145 HashMap(const HashMap
& hm
) = delete;
146 HashMap
& operator=(const HashMap
& hm
) = delete;
148 using TableEntry
= HashMapEntry
<Key
, Value
>;
150 struct MapHashPolicy
: HashPolicy
{
151 using Base
= HashPolicy
;
154 static const Key
& getKey(TableEntry
& aEntry
) { return aEntry
.key(); }
156 static void setKey(TableEntry
& aEntry
, Key
& aKey
) {
157 HashPolicy::rekey(aEntry
.mutableKey(), aKey
);
161 using Impl
= detail::HashTable
<TableEntry
, MapHashPolicy
, AllocPolicy
>;
164 friend class Impl::Enum
;
167 using Lookup
= typename
HashPolicy::Lookup
;
168 using Entry
= TableEntry
;
170 // -- Initialization -------------------------------------------------------
172 explicit HashMap(AllocPolicy aAllocPolicy
= AllocPolicy(),
173 uint32_t aLen
= Impl::sDefaultLen
)
174 : mImpl(aAllocPolicy
, aLen
) {}
176 explicit HashMap(uint32_t aLen
) : mImpl(AllocPolicy(), aLen
) {}
178 // HashMap is movable.
179 HashMap(HashMap
&& aRhs
) : mImpl(std::move(aRhs
.mImpl
)) {}
180 void operator=(HashMap
&& aRhs
) {
181 MOZ_ASSERT(this != &aRhs
, "self-move assignment is prohibited");
182 mImpl
= std::move(aRhs
.mImpl
);
185 // -- Status and sizing ----------------------------------------------------
187 // The map's current generation.
188 Generation
generation() const { return mImpl
.generation(); }
191 bool empty() const { return mImpl
.empty(); }
193 // Number of keys/values in the map.
194 uint32_t count() const { return mImpl
.count(); }
196 // Number of key/value slots in the map. Note: resize will happen well before
197 // count() == capacity().
198 uint32_t capacity() const { return mImpl
.capacity(); }
200 // The size of the map's entry storage, in bytes. If the keys/values contain
201 // pointers to other heap blocks, you must iterate over the map and measure
202 // them separately; hence the "shallow" prefix.
203 size_t shallowSizeOfExcludingThis(MallocSizeOf aMallocSizeOf
) const {
204 return mImpl
.shallowSizeOfExcludingThis(aMallocSizeOf
);
206 size_t shallowSizeOfIncludingThis(MallocSizeOf aMallocSizeOf
) const {
207 return aMallocSizeOf(this) +
208 mImpl
.shallowSizeOfExcludingThis(aMallocSizeOf
);
211 // Attempt to minimize the capacity(). If the table is empty, this will free
212 // the empty storage and upon regrowth it will be given the minimum capacity.
213 void compact() { mImpl
.compact(); }
215 // Attempt to reserve enough space to fit at least |aLen| elements. Does
216 // nothing if the map already has sufficient capacity.
217 MOZ_MUST_USE
bool reserve(uint32_t aLen
) { return mImpl
.reserve(aLen
); }
219 // -- Lookups --------------------------------------------------------------
221 // Does the map contain a key/value matching |aLookup|?
222 bool has(const Lookup
& aLookup
) const {
223 return mImpl
.lookup(aLookup
).found();
226 // Return a Ptr indicating whether a key/value matching |aLookup| is
227 // present in the map. E.g.:
229 // using HM = HashMap<int,char>;
231 // if (HM::Ptr p = h.lookup(3)) {
232 // assert(p->key() == 3);
233 // char val = p->value();
236 using Ptr
= typename
Impl::Ptr
;
237 MOZ_ALWAYS_INLINE Ptr
lookup(const Lookup
& aLookup
) const {
238 return mImpl
.lookup(aLookup
);
241 // Like lookup(), but does not assert if two threads call it at the same
242 // time. Only use this method when none of the threads will modify the map.
243 MOZ_ALWAYS_INLINE Ptr
readonlyThreadsafeLookup(const Lookup
& aLookup
) const {
244 return mImpl
.readonlyThreadsafeLookup(aLookup
);
247 // -- Insertions -----------------------------------------------------------
249 // Overwrite existing value with |aValue|, or add it if not present. Returns
251 template <typename KeyInput
, typename ValueInput
>
252 MOZ_MUST_USE
bool put(KeyInput
&& aKey
, ValueInput
&& aValue
) {
253 AddPtr p
= lookupForAdd(aKey
);
255 p
->value() = std::forward
<ValueInput
>(aValue
);
258 return add(p
, std::forward
<KeyInput
>(aKey
),
259 std::forward
<ValueInput
>(aValue
));
262 // Like put(), but slightly faster. Must only be used when the given key is
263 // not already present. (In debug builds, assertions check this.)
264 template <typename KeyInput
, typename ValueInput
>
265 MOZ_MUST_USE
bool putNew(KeyInput
&& aKey
, ValueInput
&& aValue
) {
266 return mImpl
.putNew(aKey
, std::forward
<KeyInput
>(aKey
),
267 std::forward
<ValueInput
>(aValue
));
270 // Like putNew(), but should be only used when the table is known to be big
271 // enough for the insertion, and hashing cannot fail. Typically this is used
272 // to populate an empty map with known-unique keys after reserving space with
275 // using HM = HashMap<int,char>;
277 // if (!h.reserve(3)) {
280 // h.putNewInfallible(1, 'a'); // unique key
281 // h.putNewInfallible(2, 'b'); // unique key
282 // h.putNewInfallible(3, 'c'); // unique key
284 template <typename KeyInput
, typename ValueInput
>
285 void putNewInfallible(KeyInput
&& aKey
, ValueInput
&& aValue
) {
286 mImpl
.putNewInfallible(aKey
, std::forward
<KeyInput
>(aKey
),
287 std::forward
<ValueInput
>(aValue
));
290 // Like |lookup(l)|, but on miss, |p = lookupForAdd(l)| allows efficient
291 // insertion of Key |k| (where |HashPolicy::match(k,l) == true|) using
292 // |add(p,k,v)|. After |add(p,k,v)|, |p| points to the new key/value. E.g.:
294 // using HM = HashMap<int,char>;
296 // HM::AddPtr p = h.lookupForAdd(3);
298 // if (!h.add(p, 3, 'a')) {
302 // assert(p->key() == 3);
303 // char val = p->value();
305 // N.B. The caller must ensure that no mutating hash table operations occur
306 // between a pair of lookupForAdd() and add() calls. To avoid looking up the
307 // key a second time, the caller may use the more efficient relookupOrAdd()
308 // method. This method reuses part of the hashing computation to more
309 // efficiently insert the key if it has not been added. For example, a
310 // mutation-handling version of the previous example:
312 // HM::AddPtr p = h.lookupForAdd(3);
314 // call_that_may_mutate_h();
315 // if (!h.relookupOrAdd(p, 3, 'a')) {
319 // assert(p->key() == 3);
320 // char val = p->value();
322 using AddPtr
= typename
Impl::AddPtr
;
323 MOZ_ALWAYS_INLINE AddPtr
lookupForAdd(const Lookup
& aLookup
) {
324 return mImpl
.lookupForAdd(aLookup
);
327 // Add a key/value. Returns false on OOM.
328 template <typename KeyInput
, typename ValueInput
>
329 MOZ_MUST_USE
bool add(AddPtr
& aPtr
, KeyInput
&& aKey
, ValueInput
&& aValue
) {
330 return mImpl
.add(aPtr
, std::forward
<KeyInput
>(aKey
),
331 std::forward
<ValueInput
>(aValue
));
334 // See the comment above lookupForAdd() for details.
335 template <typename KeyInput
, typename ValueInput
>
336 MOZ_MUST_USE
bool relookupOrAdd(AddPtr
& aPtr
, KeyInput
&& aKey
,
337 ValueInput
&& aValue
) {
338 return mImpl
.relookupOrAdd(aPtr
, aKey
, std::forward
<KeyInput
>(aKey
),
339 std::forward
<ValueInput
>(aValue
));
342 // -- Removal --------------------------------------------------------------
344 // Lookup and remove the key/value matching |aLookup|, if present.
345 void remove(const Lookup
& aLookup
) {
346 if (Ptr p
= lookup(aLookup
)) {
351 // Remove a previously found key/value (assuming aPtr.found()). The map must
352 // not have been mutated in the interim.
353 void remove(Ptr aPtr
) { mImpl
.remove(aPtr
); }
355 // Remove all keys/values without changing the capacity.
356 void clear() { mImpl
.clear(); }
358 // Like clear() followed by compact().
359 void clearAndCompact() { mImpl
.clearAndCompact(); }
361 // -- Rekeying -------------------------------------------------------------
363 // Infallibly rekey one entry, if necessary. Requires that template
364 // parameters Key and HashPolicy::Lookup are the same type.
365 void rekeyIfMoved(const Key
& aOldKey
, const Key
& aNewKey
) {
366 if (aOldKey
!= aNewKey
) {
367 rekeyAs(aOldKey
, aNewKey
, aNewKey
);
371 // Infallibly rekey one entry if present, and return whether that happened.
372 bool rekeyAs(const Lookup
& aOldLookup
, const Lookup
& aNewLookup
,
373 const Key
& aNewKey
) {
374 if (Ptr p
= lookup(aOldLookup
)) {
375 mImpl
.rekeyAndMaybeRehash(p
, aNewLookup
, aNewKey
);
381 // -- Iteration ------------------------------------------------------------
383 // |iter()| returns an Iterator:
385 // HashMap<int, char> h;
386 // for (auto iter = h.iter(); !iter.done(); iter.next()) {
387 // char c = iter.get().value();
390 using Iterator
= typename
Impl::Iterator
;
391 Iterator
iter() const { return mImpl
.iter(); }
393 // |modIter()| returns a ModIterator:
395 // HashMap<int, char> h;
396 // for (auto iter = h.modIter(); !iter.done(); iter.next()) {
397 // if (iter.get().value() == 'l') {
402 // Table resize may occur in ModIterator's destructor.
403 using ModIterator
= typename
Impl::ModIterator
;
404 ModIterator
modIter() { return mImpl
.modIter(); }
406 // These are similar to Iterator/ModIterator/iter(), but use different
408 using Range
= typename
Impl::Range
;
409 using Enum
= typename
Impl::Enum
;
410 Range
all() const { return mImpl
.all(); }
413 //---------------------------------------------------------------------------
415 //---------------------------------------------------------------------------
417 // HashSet is a fast hash-based set of values.
419 // Template parameter requirements:
420 // - T: movable, destructible, assignable.
421 // - HashPolicy: see the "Hash Policy" section below.
422 // - AllocPolicy: see AllocPolicy.h
425 // - HashSet is not reentrant: T/HashPolicy/AllocPolicy members called by
426 // HashSet must not call back into the same HashSet object.
428 template <class T
, class HashPolicy
= DefaultHasher
<T
>,
429 class AllocPolicy
= MallocAllocPolicy
>
431 // -- Implementation details -----------------------------------------------
433 // HashSet is not copyable or assignable.
434 HashSet(const HashSet
& hs
) = delete;
435 HashSet
& operator=(const HashSet
& hs
) = delete;
437 struct SetHashPolicy
: HashPolicy
{
438 using Base
= HashPolicy
;
441 static const KeyType
& getKey(const T
& aT
) { return aT
; }
443 static void setKey(T
& aT
, KeyType
& aKey
) { HashPolicy::rekey(aT
, aKey
); }
446 using Impl
= detail::HashTable
<const T
, SetHashPolicy
, AllocPolicy
>;
449 friend class Impl::Enum
;
452 using Lookup
= typename
HashPolicy::Lookup
;
455 // -- Initialization -------------------------------------------------------
457 explicit HashSet(AllocPolicy aAllocPolicy
= AllocPolicy(),
458 uint32_t aLen
= Impl::sDefaultLen
)
459 : mImpl(aAllocPolicy
, aLen
) {}
461 explicit HashSet(uint32_t aLen
) : mImpl(AllocPolicy(), aLen
) {}
463 // HashSet is movable.
464 HashSet(HashSet
&& aRhs
) : mImpl(std::move(aRhs
.mImpl
)) {}
465 void operator=(HashSet
&& aRhs
) {
466 MOZ_ASSERT(this != &aRhs
, "self-move assignment is prohibited");
467 mImpl
= std::move(aRhs
.mImpl
);
470 // -- Status and sizing ----------------------------------------------------
472 // The set's current generation.
473 Generation
generation() const { return mImpl
.generation(); }
476 bool empty() const { return mImpl
.empty(); }
478 // Number of elements in the set.
479 uint32_t count() const { return mImpl
.count(); }
481 // Number of element slots in the set. Note: resize will happen well before
482 // count() == capacity().
483 uint32_t capacity() const { return mImpl
.capacity(); }
485 // The size of the set's entry storage, in bytes. If the elements contain
486 // pointers to other heap blocks, you must iterate over the set and measure
487 // them separately; hence the "shallow" prefix.
488 size_t shallowSizeOfExcludingThis(MallocSizeOf aMallocSizeOf
) const {
489 return mImpl
.shallowSizeOfExcludingThis(aMallocSizeOf
);
491 size_t shallowSizeOfIncludingThis(MallocSizeOf aMallocSizeOf
) const {
492 return aMallocSizeOf(this) +
493 mImpl
.shallowSizeOfExcludingThis(aMallocSizeOf
);
496 // Attempt to minimize the capacity(). If the table is empty, this will free
497 // the empty storage and upon regrowth it will be given the minimum capacity.
498 void compact() { mImpl
.compact(); }
500 // Attempt to reserve enough space to fit at least |aLen| elements. Does
501 // nothing if the map already has sufficient capacity.
502 MOZ_MUST_USE
bool reserve(uint32_t aLen
) { return mImpl
.reserve(aLen
); }
504 // -- Lookups --------------------------------------------------------------
506 // Does the set contain an element matching |aLookup|?
507 bool has(const Lookup
& aLookup
) const {
508 return mImpl
.lookup(aLookup
).found();
511 // Return a Ptr indicating whether an element matching |aLookup| is present
514 // using HS = HashSet<int>;
516 // if (HS::Ptr p = h.lookup(3)) {
517 // assert(*p == 3); // p acts like a pointer to int
520 using Ptr
= typename
Impl::Ptr
;
521 MOZ_ALWAYS_INLINE Ptr
lookup(const Lookup
& aLookup
) const {
522 return mImpl
.lookup(aLookup
);
525 // Like lookup(), but does not assert if two threads call it at the same
526 // time. Only use this method when none of the threads will modify the set.
527 MOZ_ALWAYS_INLINE Ptr
readonlyThreadsafeLookup(const Lookup
& aLookup
) const {
528 return mImpl
.readonlyThreadsafeLookup(aLookup
);
531 // -- Insertions -----------------------------------------------------------
533 // Add |aU| if it is not present already. Returns false on OOM.
534 template <typename U
>
535 MOZ_MUST_USE
bool put(U
&& aU
) {
536 AddPtr p
= lookupForAdd(aU
);
537 return p
? true : add(p
, std::forward
<U
>(aU
));
540 // Like put(), but slightly faster. Must only be used when the given element
541 // is not already present. (In debug builds, assertions check this.)
542 template <typename U
>
543 MOZ_MUST_USE
bool putNew(U
&& aU
) {
544 return mImpl
.putNew(aU
, std::forward
<U
>(aU
));
547 // Like the other putNew(), but for when |Lookup| is different to |T|.
548 template <typename U
>
549 MOZ_MUST_USE
bool putNew(const Lookup
& aLookup
, U
&& aU
) {
550 return mImpl
.putNew(aLookup
, std::forward
<U
>(aU
));
553 // Like putNew(), but should be only used when the table is known to be big
554 // enough for the insertion, and hashing cannot fail. Typically this is used
555 // to populate an empty set with known-unique elements after reserving space
556 // with reserve(), e.g.
558 // using HS = HashMap<int>;
560 // if (!h.reserve(3)) {
563 // h.putNewInfallible(1); // unique element
564 // h.putNewInfallible(2); // unique element
565 // h.putNewInfallible(3); // unique element
567 template <typename U
>
568 void putNewInfallible(const Lookup
& aLookup
, U
&& aU
) {
569 mImpl
.putNewInfallible(aLookup
, std::forward
<U
>(aU
));
572 // Like |lookup(l)|, but on miss, |p = lookupForAdd(l)| allows efficient
573 // insertion of T value |t| (where |HashPolicy::match(t,l) == true|) using
574 // |add(p,t)|. After |add(p,t)|, |p| points to the new element. E.g.:
576 // using HS = HashSet<int>;
578 // HS::AddPtr p = h.lookupForAdd(3);
580 // if (!h.add(p, 3)) {
584 // assert(*p == 3); // p acts like a pointer to int
586 // N.B. The caller must ensure that no mutating hash table operations occur
587 // between a pair of lookupForAdd() and add() calls. To avoid looking up the
588 // key a second time, the caller may use the more efficient relookupOrAdd()
589 // method. This method reuses part of the hashing computation to more
590 // efficiently insert the key if it has not been added. For example, a
591 // mutation-handling version of the previous example:
593 // HS::AddPtr p = h.lookupForAdd(3);
595 // call_that_may_mutate_h();
596 // if (!h.relookupOrAdd(p, 3, 3)) {
602 // Note that relookupOrAdd(p,l,t) performs Lookup using |l| and adds the
603 // entry |t|, where the caller ensures match(l,t).
604 using AddPtr
= typename
Impl::AddPtr
;
605 MOZ_ALWAYS_INLINE AddPtr
lookupForAdd(const Lookup
& aLookup
) {
606 return mImpl
.lookupForAdd(aLookup
);
609 // Add an element. Returns false on OOM.
610 template <typename U
>
611 MOZ_MUST_USE
bool add(AddPtr
& aPtr
, U
&& aU
) {
612 return mImpl
.add(aPtr
, std::forward
<U
>(aU
));
615 // See the comment above lookupForAdd() for details.
616 template <typename U
>
617 MOZ_MUST_USE
bool relookupOrAdd(AddPtr
& aPtr
, const Lookup
& aLookup
, U
&& aU
) {
618 return mImpl
.relookupOrAdd(aPtr
, aLookup
, std::forward
<U
>(aU
));
621 // -- Removal --------------------------------------------------------------
623 // Lookup and remove the element matching |aLookup|, if present.
624 void remove(const Lookup
& aLookup
) {
625 if (Ptr p
= lookup(aLookup
)) {
630 // Remove a previously found element (assuming aPtr.found()). The set must
631 // not have been mutated in the interim.
632 void remove(Ptr aPtr
) { mImpl
.remove(aPtr
); }
634 // Remove all keys/values without changing the capacity.
635 void clear() { mImpl
.clear(); }
637 // Like clear() followed by compact().
638 void clearAndCompact() { mImpl
.clearAndCompact(); }
640 // -- Rekeying -------------------------------------------------------------
642 // Infallibly rekey one entry, if present. Requires that template parameters
643 // T and HashPolicy::Lookup are the same type.
644 void rekeyIfMoved(const Lookup
& aOldValue
, const T
& aNewValue
) {
645 if (aOldValue
!= aNewValue
) {
646 rekeyAs(aOldValue
, aNewValue
, aNewValue
);
650 // Infallibly rekey one entry if present, and return whether that happened.
651 bool rekeyAs(const Lookup
& aOldLookup
, const Lookup
& aNewLookup
,
652 const T
& aNewValue
) {
653 if (Ptr p
= lookup(aOldLookup
)) {
654 mImpl
.rekeyAndMaybeRehash(p
, aNewLookup
, aNewValue
);
660 // Infallibly replace the current key at |aPtr| with an equivalent key.
661 // Specifically, both HashPolicy::hash and HashPolicy::match must return
662 // identical results for the new and old key when applied against all
663 // possible matching values.
664 void replaceKey(Ptr aPtr
, const T
& aNewValue
) {
665 MOZ_ASSERT(aPtr
.found());
666 MOZ_ASSERT(*aPtr
!= aNewValue
);
667 MOZ_ASSERT(HashPolicy::hash(*aPtr
) == HashPolicy::hash(aNewValue
));
668 MOZ_ASSERT(HashPolicy::match(*aPtr
, aNewValue
));
669 const_cast<T
&>(*aPtr
) = aNewValue
;
672 // -- Iteration ------------------------------------------------------------
674 // |iter()| returns an Iterator:
677 // for (auto iter = h.iter(); !iter.done(); iter.next()) {
678 // int i = iter.get();
681 using Iterator
= typename
Impl::Iterator
;
682 Iterator
iter() const { return mImpl
.iter(); }
684 // |modIter()| returns a ModIterator:
687 // for (auto iter = h.modIter(); !iter.done(); iter.next()) {
688 // if (iter.get() == 42) {
693 // Table resize may occur in ModIterator's destructor.
694 using ModIterator
= typename
Impl::ModIterator
;
695 ModIterator
modIter() { return mImpl
.modIter(); }
697 // These are similar to Iterator/ModIterator/iter(), but use different
699 using Range
= typename
Impl::Range
;
700 using Enum
= typename
Impl::Enum
;
701 Range
all() const { return mImpl
.all(); }
704 //---------------------------------------------------------------------------
706 //---------------------------------------------------------------------------
708 // A hash policy |HP| for a hash table with key-type |Key| must provide:
710 // - a type |HP::Lookup| to use to lookup table entries;
712 // - a static member function |HP::hash| that hashes lookup values:
714 // static mozilla::HashNumber hash(const Lookup&);
716 // - a static member function |HP::match| that tests equality of key and
719 // static bool match(const Key&, const Lookup&);
721 // Normally, Lookup = Key. In general, though, different values and types of
722 // values can be used to lookup and store. If a Lookup value |l| is not equal
723 // to the added Key value |k|, the user must ensure that |HP::match(k,l)| is
726 // mozilla::HashSet<Key, HP>::AddPtr p = h.lookup(l);
728 // assert(HP::match(k, l)); // must hold
732 // A pointer hashing policy that uses HashGeneric() to create good hashes for
733 // pointers. Note that we don't shift out the lowest k bits because we don't
734 // want to assume anything about the alignment of the pointers.
735 template <typename Key
>
736 struct PointerHasher
{
739 static HashNumber
hash(const Lookup
& aLookup
) {
740 size_t word
= reinterpret_cast<size_t>(aLookup
);
741 return HashGeneric(word
);
744 static bool match(const Key
& aKey
, const Lookup
& aLookup
) {
745 return aKey
== aLookup
;
748 static void rekey(Key
& aKey
, const Key
& aNewKey
) { aKey
= aNewKey
; }
751 // The default hash policy, which only works with integers.
753 struct DefaultHasher
{
756 static HashNumber
hash(const Lookup
& aLookup
) {
757 // Just convert the integer to a HashNumber and use that as is. (This
758 // discards the high 32-bits of 64-bit integers!) ScrambleHashCode() is
759 // subsequently called on the value to improve the distribution.
763 static bool match(const Key
& aKey
, const Lookup
& aLookup
) {
764 // Use builtin or overloaded operator==.
765 return aKey
== aLookup
;
768 static void rekey(Key
& aKey
, const Key
& aNewKey
) { aKey
= aNewKey
; }
771 // A DefaultHasher specialization for pointers.
773 struct DefaultHasher
<T
*> : PointerHasher
<T
*> {};
775 // A DefaultHasher specialization for mozilla::UniquePtr.
776 template <class T
, class D
>
777 struct DefaultHasher
<UniquePtr
<T
, D
>> {
778 using Key
= UniquePtr
<T
, D
>;
780 using PtrHasher
= PointerHasher
<T
*>;
782 static HashNumber
hash(const Lookup
& aLookup
) {
783 return PtrHasher::hash(aLookup
.get());
786 static bool match(const Key
& aKey
, const Lookup
& aLookup
) {
787 return PtrHasher::match(aKey
.get(), aLookup
.get());
790 static void rekey(UniquePtr
<T
, D
>& aKey
, UniquePtr
<T
, D
>&& aNewKey
) {
791 aKey
= std::move(aNewKey
);
795 // A DefaultHasher specialization for doubles.
797 struct DefaultHasher
<double> {
801 static HashNumber
hash(const Lookup
& aLookup
) {
802 // Just xor the high bits with the low bits, and then treat the bits of the
803 // result as a uint32_t.
804 static_assert(sizeof(HashNumber
) == 4,
805 "subsequent code assumes a four-byte hash");
806 uint64_t u
= BitwiseCast
<uint64_t>(aLookup
);
807 return HashNumber(u
^ (u
>> 32));
810 static bool match(const Key
& aKey
, const Lookup
& aLookup
) {
811 return BitwiseCast
<uint64_t>(aKey
) == BitwiseCast
<uint64_t>(aLookup
);
815 // A DefaultHasher specialization for floats.
817 struct DefaultHasher
<float> {
821 static HashNumber
hash(const Lookup
& aLookup
) {
822 // Just use the value as if its bits form an integer. ScrambleHashCode() is
823 // subsequently called on the value to improve the distribution.
824 static_assert(sizeof(HashNumber
) == 4,
825 "subsequent code assumes a four-byte hash");
826 return HashNumber(BitwiseCast
<uint32_t>(aLookup
));
829 static bool match(const Key
& aKey
, const Lookup
& aLookup
) {
830 return BitwiseCast
<uint32_t>(aKey
) == BitwiseCast
<uint32_t>(aLookup
);
834 // A hash policy for C strings.
835 struct CStringHasher
{
836 using Key
= const char*;
837 using Lookup
= const char*;
839 static HashNumber
hash(const Lookup
& aLookup
) { return HashString(aLookup
); }
841 static bool match(const Key
& aKey
, const Lookup
& aLookup
) {
842 return strcmp(aKey
, aLookup
) == 0;
846 //---------------------------------------------------------------------------
847 // Fallible Hashing Interface
848 //---------------------------------------------------------------------------
850 // Most of the time generating a hash code is infallible so this class provides
851 // default methods that always succeed. Specialize this class for your own hash
852 // policy to provide fallible hashing.
854 // This is used by MovableCellHasher to handle the fact that generating a unique
855 // ID for cell pointer may fail due to OOM.
856 template <typename HashPolicy
>
857 struct FallibleHashMethods
{
858 // Return true if a hashcode is already available for its argument. Once
859 // this returns true for a specific argument it must continue to do so.
860 template <typename Lookup
>
861 static bool hasHash(Lookup
&& aLookup
) {
865 // Fallible method to ensure a hashcode exists for its argument and create
866 // one if not. Returns false on error, e.g. out of memory.
867 template <typename Lookup
>
868 static bool ensureHash(Lookup
&& aLookup
) {
873 template <typename HashPolicy
, typename Lookup
>
874 static bool HasHash(Lookup
&& aLookup
) {
875 return FallibleHashMethods
<typename
HashPolicy::Base
>::hasHash(
876 std::forward
<Lookup
>(aLookup
));
879 template <typename HashPolicy
, typename Lookup
>
880 static bool EnsureHash(Lookup
&& aLookup
) {
881 return FallibleHashMethods
<typename
HashPolicy::Base
>::ensureHash(
882 std::forward
<Lookup
>(aLookup
));
885 //---------------------------------------------------------------------------
886 // Implementation Details (HashMapEntry, HashTableEntry, HashTable)
887 //---------------------------------------------------------------------------
889 // Both HashMap and HashSet are implemented by a single HashTable that is even
890 // more heavily parameterized than the other two. This leaves HashTable gnarly
891 // and extremely coupled to HashMap and HashSet; thus code should not use
892 // HashTable directly.
894 template <class Key
, class Value
>
899 template <class, class, class>
900 friend class detail::HashTable
;
902 friend class detail::HashTableEntry
;
903 template <class, class, class, class>
904 friend class HashMap
;
907 template <typename KeyInput
, typename ValueInput
>
908 HashMapEntry(KeyInput
&& aKey
, ValueInput
&& aValue
)
909 : key_(std::forward
<KeyInput
>(aKey
)),
910 value_(std::forward
<ValueInput
>(aValue
)) {}
912 HashMapEntry(HashMapEntry
&& aRhs
)
913 : key_(std::move(aRhs
.key_
)), value_(std::move(aRhs
.value_
)) {}
915 void operator=(HashMapEntry
&& aRhs
) {
916 key_
= std::move(aRhs
.key_
);
917 value_
= std::move(aRhs
.value_
);
921 using ValueType
= Value
;
923 const Key
& key() const { return key_
; }
925 // Use this method with caution! If the key is changed such that its hash
926 // value also changes, the map will be left in an invalid state.
927 Key
& mutableKey() { return key_
; }
929 const Value
& value() const { return value_
; }
930 Value
& value() { return value_
; }
933 HashMapEntry(const HashMapEntry
&) = delete;
934 void operator=(const HashMapEntry
&) = delete;
937 template <typename K
, typename V
>
938 struct IsPod
<HashMapEntry
<K
, V
>>
939 : IntegralConstant
<bool, IsPod
<K
>::value
&& IsPod
<V
>::value
> {};
943 template <class T
, class HashPolicy
, class AllocPolicy
>
946 template <typename T
>
949 template <typename T
>
950 class HashTableEntry
{
952 using NonConstT
= typename RemoveConst
<T
>::Type
;
954 // Instead of having a hash table entry store that looks like this:
956 // +--------+--------+--------+--------+
957 // | entry0 | entry1 | .... | entryN |
958 // +--------+--------+--------+--------+
960 // where the entries contained their cached hash code, we're going to lay out
961 // the entry store thusly:
963 // +-------+-------+-------+-------+--------+--------+--------+--------+
964 // | hash0 | hash1 | ... | hashN | entry0 | entry1 | .... | entryN |
965 // +-------+-------+-------+-------+--------+--------+--------+--------+
967 // with all the cached hashes prior to the actual entries themselves.
969 // We do this because implementing the first strategy requires us to make
970 // HashTableEntry look roughly like:
972 // template <typename T>
973 // class HashTableEntry {
974 // HashNumber mKeyHash;
978 // The problem with this setup is that, depending on the layout of `T`, there
979 // may be platform ABI-mandated padding between `mKeyHash` and the first
980 // member of `T`. This ABI-mandated padding is wasted space, and can be
981 // surprisingly common, e.g. when `T` is a single pointer on 64-bit platforms.
982 // In such cases, we're throwing away a quarter of our entry store on padding,
983 // which is undesirable.
985 // The second layout above, namely:
987 // +-------+-------+-------+-------+--------+--------+--------+--------+
988 // | hash0 | hash1 | ... | hashN | entry0 | entry1 | .... | entryN |
989 // +-------+-------+-------+-------+--------+--------+--------+--------+
991 // means there is no wasted space between the hashes themselves, and no wasted
992 // space between the entries themselves. However, we would also like there to
993 // be no gap between the last hash and the first entry. The memory allocator
994 // guarantees the alignment of the start of the hashes. The use of a
995 // power-of-two capacity of at least 4 guarantees that the alignment of the
996 // *end* of the hash array is no less than the alignment of the start.
997 // Finally, the static_asserts here guarantee that the entries themselves
998 // don't need to be any more aligned than the alignment of the entry store
1000 #ifdef HAVE_64BIT_BUILD
1001 static_assert(alignof(NonConstT
) <= alignof(void*),
1002 "cannot use over-aligned entries in mozilla::HashTable");
1004 // This assertion is safe for 32-bit builds because on both Windows and Linux
1005 // (including Android), the minimum alignment for allocations larger than 8
1006 // bytes is 8 bytes, and the actual data for entries in our entry store is
1007 // guaranteed to have that alignment as well, thanks to the power-of-two
1008 // number of cached hash values stored prior to the entry data.
1009 static_assert(alignof(NonConstT
) <= 2 * alignof(void*),
1010 "cannot use over-aligned entries in mozilla::HashTable");
1013 static const HashNumber sFreeKey
= 0;
1014 static const HashNumber sRemovedKey
= 1;
1015 static const HashNumber sCollisionBit
= 1;
1017 alignas(NonConstT
) unsigned char mValueData
[sizeof(NonConstT
)];
1020 template <class, class, class>
1021 friend class HashTable
;
1023 friend class EntrySlot
;
1025 // Some versions of GCC treat it as a -Wstrict-aliasing violation (ergo a
1026 // -Werror compile error) to reinterpret_cast<> |mValueData| to |T*|, even
1027 // through |void*|. Placing the latter cast in these separate functions
1028 // breaks the chain such that affected GCC versions no longer warn/error.
1029 void* rawValuePtr() { return mValueData
; }
1031 static bool isLiveHash(HashNumber hash
) { return hash
> sRemovedKey
; }
1033 HashTableEntry(const HashTableEntry
&) = delete;
1034 void operator=(const HashTableEntry
&) = delete;
1036 NonConstT
* valuePtr() { return reinterpret_cast<NonConstT
*>(rawValuePtr()); }
1038 void destroyStoredT() {
1039 NonConstT
* ptr
= valuePtr();
1041 MOZ_MAKE_MEM_UNDEFINED(ptr
, sizeof(*ptr
));
1045 HashTableEntry() = default;
1047 ~HashTableEntry() { MOZ_MAKE_MEM_UNDEFINED(this, sizeof(*this)); }
1049 void destroy() { destroyStoredT(); }
1051 void swap(HashTableEntry
* aOther
, bool aIsLive
) {
1052 if (this == aOther
) {
1056 Swap(*valuePtr(), *aOther
->valuePtr());
1058 *aOther
->valuePtr() = std::move(*valuePtr());
1063 T
& get() { return *valuePtr(); }
1065 NonConstT
& getMutable() { return *valuePtr(); }
1068 // A slot represents a cached hash value and its associated entry stored
1069 // in the hash table. These two things are not stored in contiguous memory.
1072 using NonConstT
= typename RemoveConst
<T
>::Type
;
1074 using Entry
= HashTableEntry
<T
>;
1077 HashNumber
* mKeyHash
;
1079 template <class, class, class>
1080 friend class HashTable
;
1082 EntrySlot(Entry
* aEntry
, HashNumber
* aKeyHash
)
1083 : mEntry(aEntry
), mKeyHash(aKeyHash
) {}
1086 static bool isLiveHash(HashNumber hash
) { return hash
> Entry::sRemovedKey
; }
1088 EntrySlot(const EntrySlot
&) = default;
1089 EntrySlot(EntrySlot
&& aOther
) = default;
1091 EntrySlot
& operator=(const EntrySlot
&) = default;
1092 EntrySlot
& operator=(EntrySlot
&&) = default;
1094 bool operator==(const EntrySlot
& aRhs
) const { return mEntry
== aRhs
.mEntry
; }
1096 bool operator<(const EntrySlot
& aRhs
) const { return mEntry
< aRhs
.mEntry
; }
1098 EntrySlot
& operator++() {
1104 void destroy() { mEntry
->destroy(); }
1106 void swap(EntrySlot
& aOther
) {
1107 mEntry
->swap(aOther
.mEntry
, aOther
.isLive());
1108 Swap(*mKeyHash
, *aOther
.mKeyHash
);
1111 T
& get() const { return mEntry
->get(); }
1113 NonConstT
& getMutable() { return mEntry
->getMutable(); }
1115 bool isFree() const { return *mKeyHash
== Entry::sFreeKey
; }
1118 MOZ_ASSERT(isLive());
1119 *mKeyHash
= Entry::sFreeKey
;
1120 mEntry
->destroyStoredT();
1125 mEntry
->destroyStoredT();
1127 MOZ_MAKE_MEM_UNDEFINED(mEntry
, sizeof(*mEntry
));
1128 *mKeyHash
= Entry::sFreeKey
;
1131 bool isRemoved() const { return *mKeyHash
== Entry::sRemovedKey
; }
1134 MOZ_ASSERT(isLive());
1135 *mKeyHash
= Entry::sRemovedKey
;
1136 mEntry
->destroyStoredT();
1139 bool isLive() const { return isLiveHash(*mKeyHash
); }
1141 void setCollision() {
1142 MOZ_ASSERT(isLive());
1143 *mKeyHash
|= Entry::sCollisionBit
;
1145 void unsetCollision() { *mKeyHash
&= ~Entry::sCollisionBit
; }
1146 bool hasCollision() const { return *mKeyHash
& Entry::sCollisionBit
; }
1147 bool matchHash(HashNumber hn
) {
1148 return (*mKeyHash
& ~Entry::sCollisionBit
) == hn
;
1150 HashNumber
getKeyHash() const { return *mKeyHash
& ~Entry::sCollisionBit
; }
1152 template <typename
... Args
>
1153 void setLive(HashNumber aHashNumber
, Args
&&... aArgs
) {
1154 MOZ_ASSERT(!isLive());
1155 *mKeyHash
= aHashNumber
;
1156 new (KnownNotNull
, mEntry
->valuePtr()) T(std::forward
<Args
>(aArgs
)...);
1157 MOZ_ASSERT(isLive());
1160 Entry
* toEntry() const { return mEntry
; }
1163 template <class T
, class HashPolicy
, class AllocPolicy
>
1164 class HashTable
: private AllocPolicy
{
1165 friend class mozilla::ReentrancyGuard
;
1167 using NonConstT
= typename RemoveConst
<T
>::Type
;
1168 using Key
= typename
HashPolicy::KeyType
;
1169 using Lookup
= typename
HashPolicy::Lookup
;
1172 using Entry
= HashTableEntry
<T
>;
1173 using Slot
= EntrySlot
<T
>;
1175 template <typename F
>
1176 static void forEachSlot(char* aTable
, uint32_t aCapacity
, F
&& f
) {
1177 auto hashes
= reinterpret_cast<HashNumber
*>(aTable
);
1178 auto entries
= reinterpret_cast<Entry
*>(&hashes
[aCapacity
]);
1179 Slot
slot(entries
, hashes
);
1180 for (size_t i
= 0; i
< size_t(aCapacity
); ++i
) {
1186 // A nullable pointer to a hash table element. A Ptr |p| can be tested
1187 // either explicitly |if (p.found()) p->...| or using boolean conversion
1188 // |if (p) p->...|. Ptr objects must not be used after any mutating hash
1189 // table operations unless |generation()| is tested.
1191 friend class HashTable
;
1195 const HashTable
* mTable
;
1196 Generation mGeneration
;
1200 Ptr(Slot aSlot
, const HashTable
& aTable
)
1205 mGeneration(aTable
.generation())
1210 // This constructor is used only by AddPtr() within lookupForAdd().
1211 explicit Ptr(const HashTable
& aTable
)
1212 : mSlot(nullptr, nullptr)
1216 mGeneration(aTable
.generation())
1221 bool isValid() const { return !!mSlot
.toEntry(); }
1225 : mSlot(nullptr, nullptr)
1234 bool found() const {
1239 MOZ_ASSERT(mGeneration
== mTable
->generation());
1241 return mSlot
.isLive();
1244 explicit operator bool() const { return found(); }
1246 bool operator==(const Ptr
& aRhs
) const {
1247 MOZ_ASSERT(found() && aRhs
.found());
1248 return mSlot
== aRhs
.mSlot
;
1251 bool operator!=(const Ptr
& aRhs
) const {
1253 MOZ_ASSERT(mGeneration
== mTable
->generation());
1255 return !(*this == aRhs
);
1258 T
& operator*() const {
1260 MOZ_ASSERT(found());
1261 MOZ_ASSERT(mGeneration
== mTable
->generation());
1266 T
* operator->() const {
1268 MOZ_ASSERT(found());
1269 MOZ_ASSERT(mGeneration
== mTable
->generation());
1271 return &mSlot
.get();
1275 // A Ptr that can be used to add a key after a failed lookup.
1276 class AddPtr
: public Ptr
{
1277 friend class HashTable
;
1279 HashNumber mKeyHash
;
1281 uint64_t mMutationCount
;
1284 AddPtr(Slot aSlot
, const HashTable
& aTable
, HashNumber aHashNumber
)
1285 : Ptr(aSlot
, aTable
),
1286 mKeyHash(aHashNumber
)
1289 mMutationCount(aTable
.mMutationCount
)
1294 // This constructor is used when lookupForAdd() is performed on a table
1295 // lacking entry storage; it leaves mSlot null but initializes everything
1297 AddPtr(const HashTable
& aTable
, HashNumber aHashNumber
)
1299 mKeyHash(aHashNumber
)
1302 mMutationCount(aTable
.mMutationCount
)
1305 MOZ_ASSERT(isLive());
1308 bool isLive() const { return isLiveHash(mKeyHash
); }
1311 AddPtr() : mKeyHash(0) {}
1314 // A hash table iterator that (mostly) doesn't allow table modifications.
1315 // As with Ptr/AddPtr, Iterator objects must not be used after any mutating
1316 // hash table operation unless the |generation()| is tested.
1318 void moveToNextLiveEntry() {
1319 while (++mCur
< mEnd
&& !mCur
.isLive()) {
1325 friend class HashTable
;
1327 explicit Iterator(const HashTable
& aTable
)
1328 : mCur(aTable
.slotForIndex(0)),
1329 mEnd(aTable
.slotForIndex(aTable
.capacity()))
1333 mMutationCount(aTable
.mMutationCount
),
1334 mGeneration(aTable
.generation()),
1338 if (!done() && !mCur
.isLive()) {
1339 moveToNextLiveEntry();
1346 const HashTable
& mTable
;
1347 uint64_t mMutationCount
;
1348 Generation mGeneration
;
1355 MOZ_ASSERT(mGeneration
== mTable
.generation());
1356 MOZ_ASSERT(mMutationCount
== mTable
.mMutationCount
);
1358 return mCur
== mEnd
;
1362 MOZ_ASSERT(!done());
1364 MOZ_ASSERT(mValidEntry
);
1365 MOZ_ASSERT(mGeneration
== mTable
.generation());
1366 MOZ_ASSERT(mMutationCount
== mTable
.mMutationCount
);
1372 MOZ_ASSERT(!done());
1374 MOZ_ASSERT(mGeneration
== mTable
.generation());
1375 MOZ_ASSERT(mMutationCount
== mTable
.mMutationCount
);
1377 moveToNextLiveEntry();
1384 // A hash table iterator that permits modification, removal and rekeying.
1385 // Since rehashing when elements were removed during enumeration would be
1386 // bad, it is postponed until the ModIterator is destructed. Since the
1387 // ModIterator's destructor touches the hash table, the user must ensure
1388 // that the hash table is still alive when the destructor runs.
1389 class ModIterator
: public Iterator
{
1390 friend class HashTable
;
1396 // ModIterator is movable but not copyable.
1397 ModIterator(const ModIterator
&) = delete;
1398 void operator=(const ModIterator
&) = delete;
1401 explicit ModIterator(HashTable
& aTable
)
1402 : Iterator(aTable
), mTable(aTable
), mRekeyed(false), mRemoved(false) {}
1405 MOZ_IMPLICIT
ModIterator(ModIterator
&& aOther
)
1407 mTable(aOther
.mTable
),
1408 mRekeyed(aOther
.mRekeyed
),
1409 mRemoved(aOther
.mRemoved
) {
1410 aOther
.mRekeyed
= false;
1411 aOther
.mRemoved
= false;
1414 // Removes the current element from the table, leaving |get()|
1415 // invalid until the next call to |next()|.
1417 mTable
.remove(this->mCur
);
1420 this->mValidEntry
= false;
1421 this->mMutationCount
= mTable
.mMutationCount
;
1425 NonConstT
& getMutable() {
1426 MOZ_ASSERT(!this->done());
1428 MOZ_ASSERT(this->mValidEntry
);
1429 MOZ_ASSERT(this->mGeneration
== this->Iterator::mTable
.generation());
1430 MOZ_ASSERT(this->mMutationCount
== this->Iterator::mTable
.mMutationCount
);
1432 return this->mCur
.getMutable();
1435 // Removes the current element and re-inserts it into the table with
1436 // a new key at the new Lookup position. |get()| is invalid after
1437 // this operation until the next call to |next()|.
1438 void rekey(const Lookup
& l
, const Key
& k
) {
1439 MOZ_ASSERT(&k
!= &HashPolicy::getKey(this->mCur
.get()));
1440 Ptr
p(this->mCur
, mTable
);
1441 mTable
.rekeyWithoutRehash(p
, l
, k
);
1444 this->mValidEntry
= false;
1445 this->mMutationCount
= mTable
.mMutationCount
;
1449 void rekey(const Key
& k
) { rekey(k
, k
); }
1451 // Potentially rehashes the table.
1455 mTable
.infallibleRehashIfOverloaded();
1464 // Range is similar to Iterator, but uses different terminology.
1466 friend class HashTable
;
1471 explicit Range(const HashTable
& table
) : mIter(table
) {}
1474 bool empty() const { return mIter
.done(); }
1476 T
& front() const { return mIter
.get(); }
1478 void popFront() { return mIter
.next(); }
1481 // Enum is similar to ModIterator, but uses different terminology.
1485 // Enum is movable but not copyable.
1486 Enum(const Enum
&) = delete;
1487 void operator=(const Enum
&) = delete;
1490 template <class Map
>
1491 explicit Enum(Map
& map
) : mIter(map
.mImpl
) {}
1493 MOZ_IMPLICIT
Enum(Enum
&& other
) : mIter(std::move(other
.mIter
)) {}
1495 bool empty() const { return mIter
.done(); }
1497 T
& front() const { return mIter
.get(); }
1499 void popFront() { return mIter
.next(); }
1501 void removeFront() { mIter
.remove(); }
1503 NonConstT
& mutableFront() { return mIter
.getMutable(); }
1505 void rekeyFront(const Lookup
& aLookup
, const Key
& aKey
) {
1506 mIter
.rekey(aLookup
, aKey
);
1509 void rekeyFront(const Key
& aKey
) { mIter
.rekey(aKey
); }
1512 // HashTable is movable
1513 HashTable(HashTable
&& aRhs
) : AllocPolicy(aRhs
) {
1514 PodAssign(this, &aRhs
);
1515 aRhs
.mTable
= nullptr;
1517 void operator=(HashTable
&& aRhs
) {
1518 MOZ_ASSERT(this != &aRhs
, "self-move assignment is prohibited");
1520 destroyTable(*this, mTable
, capacity());
1522 PodAssign(this, &aRhs
);
1523 aRhs
.mTable
= nullptr;
1527 // HashTable is not copyable or assignable
1528 HashTable(const HashTable
&) = delete;
1529 void operator=(const HashTable
&) = delete;
1531 static const uint32_t CAP_BITS
= 30;
1534 uint64_t mGen
: 56; // entry storage generation number
1535 uint64_t mHashShift
: 8; // multiplicative hash shift
1536 char* mTable
; // entry storage
1537 uint32_t mEntryCount
; // number of entries in mTable
1538 uint32_t mRemovedCount
; // removed entry sentinels in mTable
1541 uint64_t mMutationCount
;
1542 mutable bool mEntered
;
1545 // The default initial capacity is 32 (enough to hold 16 elements), but it
1546 // can be as low as 4.
1547 static const uint32_t sDefaultLen
= 16;
1548 static const uint32_t sMinCapacity
= 4;
1549 // See the comments in HashTableEntry about this value.
1550 static_assert(sMinCapacity
>= 4, "too-small sMinCapacity breaks assumptions");
1551 static const uint32_t sMaxInit
= 1u << (CAP_BITS
- 1);
1552 static const uint32_t sMaxCapacity
= 1u << CAP_BITS
;
1554 // Hash-table alpha is conceptually a fraction, but to avoid floating-point
1555 // math we implement it as a ratio of integers.
1556 static const uint8_t sAlphaDenominator
= 4;
1557 static const uint8_t sMinAlphaNumerator
= 1; // min alpha: 1/4
1558 static const uint8_t sMaxAlphaNumerator
= 3; // max alpha: 3/4
1560 static const HashNumber sFreeKey
= Entry::sFreeKey
;
1561 static const HashNumber sRemovedKey
= Entry::sRemovedKey
;
1562 static const HashNumber sCollisionBit
= Entry::sCollisionBit
;
1564 static uint32_t bestCapacity(uint32_t aLen
) {
1566 (sMaxInit
* sAlphaDenominator
) / sAlphaDenominator
== sMaxInit
,
1567 "multiplication in numerator below could overflow");
1569 sMaxInit
* sAlphaDenominator
<= UINT32_MAX
- sMaxAlphaNumerator
,
1570 "numerator calculation below could potentially overflow");
1572 // Callers should ensure this is true.
1573 MOZ_ASSERT(aLen
<= sMaxInit
);
1575 // Compute the smallest capacity allowing |aLen| elements to be
1576 // inserted without rehashing: ceil(aLen / max-alpha). (Ceiling
1577 // integral division: <http://stackoverflow.com/a/2745086>.)
1578 uint32_t capacity
= (aLen
* sAlphaDenominator
+ sMaxAlphaNumerator
- 1) /
1580 capacity
= (capacity
< sMinCapacity
) ? sMinCapacity
: RoundUpPow2(capacity
);
1582 MOZ_ASSERT(capacity
>= aLen
);
1583 MOZ_ASSERT(capacity
<= sMaxCapacity
);
1588 static uint32_t hashShift(uint32_t aLen
) {
1589 // Reject all lengths whose initial computed capacity would exceed
1590 // sMaxCapacity. Round that maximum aLen down to the nearest power of two
1591 // for speedier code.
1592 if (MOZ_UNLIKELY(aLen
> sMaxInit
)) {
1593 MOZ_CRASH("initial length is too large");
1596 return kHashNumberBits
- mozilla::CeilingLog2(bestCapacity(aLen
));
1599 static bool isLiveHash(HashNumber aHash
) { return Entry::isLiveHash(aHash
); }
1601 static HashNumber
prepareHash(const Lookup
& aLookup
) {
1602 HashNumber keyHash
= ScrambleHashCode(HashPolicy::hash(aLookup
));
1604 // Avoid reserved hash codes.
1605 if (!isLiveHash(keyHash
)) {
1606 keyHash
-= (sRemovedKey
+ 1);
1608 return keyHash
& ~sCollisionBit
;
1611 enum FailureBehavior
{ DontReportFailure
= false, ReportFailure
= true };
1613 static char* createTable(AllocPolicy
& aAllocPolicy
, uint32_t aCapacity
,
1614 FailureBehavior aReportFailure
= ReportFailure
) {
1615 // Fake a struct that we're going to alloc. See the comments in
1616 // HashTableEntry about how the table is laid out, and why it's safe.
1618 unsigned char c
[sizeof(HashNumber
) + sizeof(typename
Entry::NonConstT
)];
1623 ? aAllocPolicy
.template pod_malloc
<FakeSlot
>(aCapacity
)
1624 : aAllocPolicy
.template maybe_pod_malloc
<FakeSlot
>(aCapacity
);
1625 char* table
= reinterpret_cast<char*>(fake
);
1627 forEachSlot(table
, aCapacity
, [&](Slot
& slot
) {
1628 *slot
.mKeyHash
= sFreeKey
;
1629 new (KnownNotNull
, slot
.toEntry()) Entry();
1635 static void destroyTable(AllocPolicy
& aAllocPolicy
, char* aOldTable
,
1636 uint32_t aCapacity
) {
1637 forEachSlot(aOldTable
, aCapacity
, [&](const Slot
& slot
) {
1638 if (slot
.isLive()) {
1639 slot
.toEntry()->destroyStoredT();
1642 aAllocPolicy
.free_(aOldTable
, aCapacity
);
1646 HashTable(AllocPolicy aAllocPolicy
, uint32_t aLen
)
1647 : AllocPolicy(aAllocPolicy
),
1649 mHashShift(hashShift(aLen
)),
1661 explicit HashTable(AllocPolicy aAllocPolicy
)
1662 : HashTable(aAllocPolicy
, sDefaultLen
) {}
1666 destroyTable(*this, mTable
, capacity());
1671 HashNumber
hash1(HashNumber aHash0
) const { return aHash0
>> mHashShift
; }
1675 HashNumber mSizeMask
;
1678 DoubleHash
hash2(HashNumber aCurKeyHash
) const {
1679 uint32_t sizeLog2
= kHashNumberBits
- mHashShift
;
1680 DoubleHash dh
= {((aCurKeyHash
<< sizeLog2
) >> mHashShift
) | 1,
1681 (HashNumber(1) << sizeLog2
) - 1};
1685 static HashNumber
applyDoubleHash(HashNumber aHash1
,
1686 const DoubleHash
& aDoubleHash
) {
1687 return (aHash1
- aDoubleHash
.mHash2
) & aDoubleHash
.mSizeMask
;
1690 static MOZ_ALWAYS_INLINE
bool match(T
& aEntry
, const Lookup
& aLookup
) {
1691 return HashPolicy::match(HashPolicy::getKey(aEntry
), aLookup
);
1694 enum LookupReason
{ ForNonAdd
, ForAdd
};
1696 Slot
slotForIndex(HashNumber aIndex
) const {
1697 auto hashes
= reinterpret_cast<HashNumber
*>(mTable
);
1698 auto entries
= reinterpret_cast<Entry
*>(&hashes
[capacity()]);
1699 return Slot(&entries
[aIndex
], &hashes
[aIndex
]);
1702 // Warning: in order for readonlyThreadsafeLookup() to be safe this
1703 // function must not modify the table in any way when Reason==ForNonAdd.
1704 template <LookupReason Reason
>
1705 MOZ_ALWAYS_INLINE Slot
lookup(const Lookup
& aLookup
,
1706 HashNumber aKeyHash
) const {
1707 MOZ_ASSERT(isLiveHash(aKeyHash
));
1708 MOZ_ASSERT(!(aKeyHash
& sCollisionBit
));
1711 // Compute the primary hash address.
1712 HashNumber h1
= hash1(aKeyHash
);
1713 Slot slot
= slotForIndex(h1
);
1715 // Miss: return space for a new entry.
1716 if (slot
.isFree()) {
1720 // Hit: return entry.
1721 if (slot
.matchHash(aKeyHash
) && match(slot
.get(), aLookup
)) {
1725 // Collision: double hash.
1726 DoubleHash dh
= hash2(aKeyHash
);
1728 // Save the first removed entry pointer so we can recycle later.
1729 Maybe
<Slot
> firstRemoved
;
1732 if (Reason
== ForAdd
&& !firstRemoved
) {
1733 if (MOZ_UNLIKELY(slot
.isRemoved())) {
1734 firstRemoved
.emplace(slot
);
1736 slot
.setCollision();
1740 h1
= applyDoubleHash(h1
, dh
);
1742 slot
= slotForIndex(h1
);
1743 if (slot
.isFree()) {
1744 return firstRemoved
.refOr(slot
);
1747 if (slot
.matchHash(aKeyHash
) && match(slot
.get(), aLookup
)) {
1753 // This is a copy of lookup() hardcoded to the assumptions:
1754 // 1. the lookup is for an add;
1755 // 2. the key, whose |keyHash| has been passed, is not in the table.
1756 Slot
findNonLiveSlot(HashNumber aKeyHash
) {
1757 MOZ_ASSERT(!(aKeyHash
& sCollisionBit
));
1760 // We assume 'aKeyHash' has already been distributed.
1762 // Compute the primary hash address.
1763 HashNumber h1
= hash1(aKeyHash
);
1764 Slot slot
= slotForIndex(h1
);
1766 // Miss: return space for a new entry.
1767 if (!slot
.isLive()) {
1771 // Collision: double hash.
1772 DoubleHash dh
= hash2(aKeyHash
);
1775 slot
.setCollision();
1777 h1
= applyDoubleHash(h1
, dh
);
1779 slot
= slotForIndex(h1
);
1780 if (!slot
.isLive()) {
1786 enum RebuildStatus
{ NotOverloaded
, Rehashed
, RehashFailed
};
1788 RebuildStatus
changeTableSize(
1789 uint32_t newCapacity
, FailureBehavior aReportFailure
= ReportFailure
) {
1790 MOZ_ASSERT(IsPowerOfTwo(newCapacity
));
1791 MOZ_ASSERT(!!mTable
== !!capacity());
1793 // Look, but don't touch, until we succeed in getting new entry store.
1794 char* oldTable
= mTable
;
1795 uint32_t oldCapacity
= capacity();
1796 uint32_t newLog2
= mozilla::CeilingLog2(newCapacity
);
1798 if (MOZ_UNLIKELY(newCapacity
> sMaxCapacity
)) {
1799 if (aReportFailure
) {
1800 this->reportAllocOverflow();
1802 return RehashFailed
;
1805 char* newTable
= createTable(*this, newCapacity
, aReportFailure
);
1807 return RehashFailed
;
1810 // We can't fail from here on, so update table parameters.
1811 mHashShift
= kHashNumberBits
- newLog2
;
1816 // Copy only live entries, leaving removed ones behind.
1817 forEachSlot(oldTable
, oldCapacity
, [&](Slot
& slot
) {
1818 if (slot
.isLive()) {
1819 HashNumber hn
= slot
.getKeyHash();
1820 findNonLiveSlot(hn
).setLive(
1821 hn
, std::move(const_cast<typename
Entry::NonConstT
&>(slot
.get())));
1827 // All entries have been destroyed, no need to destroyTable.
1828 this->free_(oldTable
, oldCapacity
);
1832 RebuildStatus
rehashIfOverloaded(
1833 FailureBehavior aReportFailure
= ReportFailure
) {
1834 static_assert(sMaxCapacity
<= UINT32_MAX
/ sMaxAlphaNumerator
,
1835 "multiplication below could overflow");
1837 // Note: if capacity() is zero, this will always succeed, which is
1839 bool overloaded
= mEntryCount
+ mRemovedCount
>=
1840 capacity() * sMaxAlphaNumerator
/ sAlphaDenominator
;
1843 return NotOverloaded
;
1846 // Succeed if a quarter or more of all entries are removed. Note that this
1847 // always succeeds if capacity() == 0 (i.e. entry storage has not been
1848 // allocated), which is what we want, because it means changeTableSize()
1849 // will allocate the requested capacity rather than doubling it.
1850 bool manyRemoved
= mRemovedCount
>= (capacity() >> 2);
1851 uint32_t newCapacity
= manyRemoved
? rawCapacity() : rawCapacity() * 2;
1852 return changeTableSize(newCapacity
, aReportFailure
);
1855 void infallibleRehashIfOverloaded() {
1856 if (rehashIfOverloaded(DontReportFailure
) == RehashFailed
) {
1857 rehashTableInPlace();
1861 void remove(Slot
& aSlot
) {
1864 if (aSlot
.hasCollision()) {
1876 void shrinkIfUnderloaded() {
1877 static_assert(sMaxCapacity
<= UINT32_MAX
/ sMinAlphaNumerator
,
1878 "multiplication below could overflow");
1880 capacity() > sMinCapacity
&&
1881 mEntryCount
<= capacity() * sMinAlphaNumerator
/ sAlphaDenominator
;
1884 (void)changeTableSize(capacity() / 2, DontReportFailure
);
1888 // This is identical to changeTableSize(currentSize), but without requiring
1889 // a second table. We do this by recycling the collision bits to tell us if
1890 // the element is already inserted or still waiting to be inserted. Since
1891 // already-inserted elements win any conflicts, we get the same table as we
1892 // would have gotten through random insertion order.
1893 void rehashTableInPlace() {
1896 forEachSlot(mTable
, capacity(), [&](Slot
& slot
) { slot
.unsetCollision(); });
1897 for (uint32_t i
= 0; i
< capacity();) {
1898 Slot src
= slotForIndex(i
);
1900 if (!src
.isLive() || src
.hasCollision()) {
1905 HashNumber keyHash
= src
.getKeyHash();
1906 HashNumber h1
= hash1(keyHash
);
1907 DoubleHash dh
= hash2(keyHash
);
1908 Slot tgt
= slotForIndex(h1
);
1910 if (!tgt
.hasCollision()) {
1916 h1
= applyDoubleHash(h1
, dh
);
1917 tgt
= slotForIndex(h1
);
1921 // TODO: this algorithm leaves collision bits on *all* elements, even if
1922 // they are on no collision path. We have the option of setting the
1923 // collision bits correctly on a subsequent pass or skipping the rehash
1924 // unless we are totally filled with tombstones: benchmark to find out
1925 // which approach is best.
1928 // Note: |aLookup| may be a reference to a piece of |u|, so this function
1929 // must take care not to use |aLookup| after moving |u|.
1931 // Prefer to use putNewInfallible; this function does not check
1933 template <typename
... Args
>
1934 void putNewInfallibleInternal(const Lookup
& aLookup
, Args
&&... aArgs
) {
1937 HashNumber keyHash
= prepareHash(aLookup
);
1938 Slot slot
= findNonLiveSlot(keyHash
);
1940 if (slot
.isRemoved()) {
1942 keyHash
|= sCollisionBit
;
1945 slot
.setLive(keyHash
, std::forward
<Args
>(aArgs
)...);
1954 forEachSlot(mTable
, capacity(), [&](Slot
& slot
) { slot
.clear(); });
1962 // Resize the table down to the smallest capacity that doesn't overload the
1963 // table. Since we call shrinkIfUnderloaded() on every remove, you only need
1964 // to call this after a bulk removal of items done without calling remove().
1967 // Free the entry storage.
1968 this->free_(mTable
, capacity());
1970 mHashShift
= hashShift(0); // gives minimum capacity on regrowth
1976 uint32_t bestCapacity
= this->bestCapacity(mEntryCount
);
1977 MOZ_ASSERT(bestCapacity
<= capacity());
1979 if (bestCapacity
< capacity()) {
1980 (void)changeTableSize(bestCapacity
, DontReportFailure
);
1984 void clearAndCompact() {
1989 MOZ_MUST_USE
bool reserve(uint32_t aLen
) {
1994 if (MOZ_UNLIKELY(aLen
> sMaxInit
)) {
1998 uint32_t bestCapacity
= this->bestCapacity(aLen
);
1999 if (bestCapacity
<= capacity()) {
2000 return true; // Capacity is already sufficient.
2003 RebuildStatus status
= changeTableSize(bestCapacity
, ReportFailure
);
2004 MOZ_ASSERT(status
!= NotOverloaded
);
2005 return status
!= RehashFailed
;
2008 Iterator
iter() const { return Iterator(*this); }
2010 ModIterator
modIter() { return ModIterator(*this); }
2012 Range
all() const { return Range(*this); }
2014 bool empty() const { return mEntryCount
== 0; }
2016 uint32_t count() const { return mEntryCount
; }
2018 uint32_t rawCapacity() const { return 1u << (kHashNumberBits
- mHashShift
); }
2020 uint32_t capacity() const { return mTable
? rawCapacity() : 0; }
2022 Generation
generation() const { return Generation(mGen
); }
2024 size_t shallowSizeOfExcludingThis(MallocSizeOf aMallocSizeOf
) const {
2025 return aMallocSizeOf(mTable
);
2028 size_t shallowSizeOfIncludingThis(MallocSizeOf aMallocSizeOf
) const {
2029 return aMallocSizeOf(this) + shallowSizeOfExcludingThis(aMallocSizeOf
);
2032 MOZ_ALWAYS_INLINE Ptr
readonlyThreadsafeLookup(const Lookup
& aLookup
) const {
2033 if (!mTable
|| !HasHash
<HashPolicy
>(aLookup
)) {
2036 HashNumber keyHash
= prepareHash(aLookup
);
2037 return Ptr(lookup
<ForNonAdd
>(aLookup
, keyHash
), *this);
2040 MOZ_ALWAYS_INLINE Ptr
lookup(const Lookup
& aLookup
) const {
2041 ReentrancyGuard
g(*this);
2042 return readonlyThreadsafeLookup(aLookup
);
2045 MOZ_ALWAYS_INLINE AddPtr
lookupForAdd(const Lookup
& aLookup
) {
2046 ReentrancyGuard
g(*this);
2047 if (!EnsureHash
<HashPolicy
>(aLookup
)) {
2051 HashNumber keyHash
= prepareHash(aLookup
);
2054 return AddPtr(*this, keyHash
);
2057 // Directly call the constructor in the return statement to avoid
2058 // excess copying when building with Visual Studio 2017.
2060 return AddPtr(lookup
<ForAdd
>(aLookup
, keyHash
), *this, keyHash
);
2063 template <typename
... Args
>
2064 MOZ_MUST_USE
bool add(AddPtr
& aPtr
, Args
&&... aArgs
) {
2065 ReentrancyGuard
g(*this);
2066 MOZ_ASSERT_IF(aPtr
.isValid(), mTable
);
2067 MOZ_ASSERT_IF(aPtr
.isValid(), aPtr
.mTable
== this);
2068 MOZ_ASSERT(!aPtr
.found());
2069 MOZ_ASSERT(!(aPtr
.mKeyHash
& sCollisionBit
));
2071 // Check for error from ensureHash() here.
2072 if (!aPtr
.isLive()) {
2076 MOZ_ASSERT(aPtr
.mGeneration
== generation());
2078 MOZ_ASSERT(aPtr
.mMutationCount
== mMutationCount
);
2081 if (!aPtr
.isValid()) {
2082 MOZ_ASSERT(!mTable
&& mEntryCount
== 0);
2083 uint32_t newCapacity
= rawCapacity();
2084 RebuildStatus status
= changeTableSize(newCapacity
, ReportFailure
);
2085 MOZ_ASSERT(status
!= NotOverloaded
);
2086 if (status
== RehashFailed
) {
2089 aPtr
.mSlot
= findNonLiveSlot(aPtr
.mKeyHash
);
2091 } else if (aPtr
.mSlot
.isRemoved()) {
2092 // Changing an entry from removed to live does not affect whether we are
2093 // overloaded and can be handled separately.
2094 if (!this->checkSimulatedOOM()) {
2098 aPtr
.mKeyHash
|= sCollisionBit
;
2101 // Preserve the validity of |aPtr.mSlot|.
2102 RebuildStatus status
= rehashIfOverloaded();
2103 if (status
== RehashFailed
) {
2106 if (status
== NotOverloaded
&& !this->checkSimulatedOOM()) {
2109 if (status
== Rehashed
) {
2110 aPtr
.mSlot
= findNonLiveSlot(aPtr
.mKeyHash
);
2114 aPtr
.mSlot
.setLive(aPtr
.mKeyHash
, std::forward
<Args
>(aArgs
)...);
2118 aPtr
.mGeneration
= generation();
2119 aPtr
.mMutationCount
= mMutationCount
;
2124 // Note: |aLookup| may be a reference to a piece of |u|, so this function
2125 // must take care not to use |aLookup| after moving |u|.
2126 template <typename
... Args
>
2127 void putNewInfallible(const Lookup
& aLookup
, Args
&&... aArgs
) {
2128 MOZ_ASSERT(!lookup(aLookup
).found());
2129 ReentrancyGuard
g(*this);
2130 putNewInfallibleInternal(aLookup
, std::forward
<Args
>(aArgs
)...);
2133 // Note: |aLookup| may be alias arguments in |aArgs|, so this function must
2134 // take care not to use |aLookup| after moving |aArgs|.
2135 template <typename
... Args
>
2136 MOZ_MUST_USE
bool putNew(const Lookup
& aLookup
, Args
&&... aArgs
) {
2137 if (!this->checkSimulatedOOM()) {
2140 if (!EnsureHash
<HashPolicy
>(aLookup
)) {
2143 if (rehashIfOverloaded() == RehashFailed
) {
2146 putNewInfallible(aLookup
, std::forward
<Args
>(aArgs
)...);
2150 // Note: |aLookup| may be a reference to a piece of |u|, so this function
2151 // must take care not to use |aLookup| after moving |u|.
2152 template <typename
... Args
>
2153 MOZ_MUST_USE
bool relookupOrAdd(AddPtr
& aPtr
, const Lookup
& aLookup
,
2155 // Check for error from ensureHash() here.
2156 if (!aPtr
.isLive()) {
2160 aPtr
.mGeneration
= generation();
2161 aPtr
.mMutationCount
= mMutationCount
;
2164 ReentrancyGuard
g(*this);
2165 // Check that aLookup has not been destroyed.
2166 MOZ_ASSERT(prepareHash(aLookup
) == aPtr
.mKeyHash
);
2167 aPtr
.mSlot
= lookup
<ForAdd
>(aLookup
, aPtr
.mKeyHash
);
2172 // Clear aPtr so it's invalid; add() will allocate storage and redo the
2174 aPtr
.mSlot
= Slot(nullptr, nullptr);
2176 return add(aPtr
, std::forward
<Args
>(aArgs
)...);
2179 void remove(Ptr aPtr
) {
2181 ReentrancyGuard
g(*this);
2182 MOZ_ASSERT(aPtr
.found());
2183 MOZ_ASSERT(aPtr
.mGeneration
== generation());
2185 shrinkIfUnderloaded();
2188 void rekeyWithoutRehash(Ptr aPtr
, const Lookup
& aLookup
, const Key
& aKey
) {
2190 ReentrancyGuard
g(*this);
2191 MOZ_ASSERT(aPtr
.found());
2192 MOZ_ASSERT(aPtr
.mGeneration
== generation());
2193 typename HashTableEntry
<T
>::NonConstT
t(std::move(*aPtr
));
2194 HashPolicy::setKey(t
, const_cast<Key
&>(aKey
));
2196 putNewInfallibleInternal(aLookup
, std::move(t
));
2199 void rekeyAndMaybeRehash(Ptr aPtr
, const Lookup
& aLookup
, const Key
& aKey
) {
2200 rekeyWithoutRehash(aPtr
, aLookup
, aKey
);
2201 infallibleRehashIfOverloaded();
2205 } // namespace detail
2206 } // namespace mozilla
2208 #endif /* mozilla_HashTable_h */