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 // See the comment at the top of mfbt/HashTable.h for a comparison between
8 // PLDHashTable and mozilla::HashTable.
10 #ifndef PLDHashTable_h
11 #define PLDHashTable_h
15 #include "mozilla/Assertions.h"
16 #include "mozilla/Atomics.h"
17 #include "mozilla/HashFunctions.h"
18 #include "mozilla/Maybe.h"
19 #include "mozilla/MemoryReporting.h"
20 #include "mozilla/fallible.h"
23 using PLDHashNumber
= mozilla::HashNumber
;
24 static const uint32_t kPLDHashNumberBits
= mozilla::kHashNumberBits
;
26 #if defined(DEBUG) || defined(FUZZING)
27 # define MOZ_HASH_TABLE_CHECKS_ENABLED 1
31 struct PLDHashTableOps
;
33 // Table entry header structure.
35 // In order to allow in-line allocation of key and value, we do not declare
36 // either here. Instead, the API uses const void *key as a formal parameter.
37 // The key need not be stored in the entry; it may be part of the value, but
38 // need not be stored at all.
40 // Callback types are defined below and grouped into the PLDHashTableOps
41 // structure, for single static initialization per hash table sub-type.
43 // Each hash table sub-type should make its entry type a subclass of
44 // PLDHashEntryHdr. PLDHashEntryHdr is merely a common superclass to present a
45 // uniform interface to PLDHashTable clients. The zero-sized base class
46 // optimization, employed by all of our supported C++ compilers, will ensure
47 // that this abstraction does not make objects needlessly larger.
48 struct PLDHashEntryHdr
{
49 PLDHashEntryHdr() = default;
50 PLDHashEntryHdr(const PLDHashEntryHdr
&) = delete;
51 PLDHashEntryHdr
& operator=(const PLDHashEntryHdr
&) = delete;
52 PLDHashEntryHdr(PLDHashEntryHdr
&&) = default;
53 PLDHashEntryHdr
& operator=(PLDHashEntryHdr
&&) = default;
56 friend class PLDHashTable
;
59 #ifdef MOZ_HASH_TABLE_CHECKS_ENABLED
61 // This class does three kinds of checking:
63 // - that calls to one of |mOps| or to an enumerator do not cause re-entry into
64 // the table in an unsafe way;
66 // - that multiple threads do not access the table in an unsafe way;
68 // - that a table marked as immutable is not modified.
70 // "Safe" here means that multiple concurrent read operations are ok, but a
71 // write operation (i.e. one that can cause the entry storage to be reallocated
72 // or destroyed) cannot safely run concurrently with another read or write
73 // operation. This meaning of "safe" is only partial; for example, it does not
74 // cover whether a single entry in the table is modified by two separate
75 // threads. (Doing such checking would be much harder.)
77 // It does this with two variables:
79 // - mState, which embodies a tri-stage tagged union with the following
82 // - Read(n), where 'n' is the number of concurrent read operations
85 // - mIsWritable, which indicates if the table is mutable.
89 constexpr Checker() : mState(kIdle
), mIsWritable(true) {}
91 Checker
& operator=(Checker
&& aOther
) {
92 // Atomic<> doesn't have an |operator=(Atomic<>&&)|.
93 mState
= uint32_t(aOther
.mState
);
94 mIsWritable
= bool(aOther
.mIsWritable
);
96 aOther
.mState
= kIdle
;
97 // XXX Shouldn't we set mIsWritable to true here for consistency?
102 static bool IsIdle(uint32_t aState
) { return aState
== kIdle
; }
103 static bool IsRead(uint32_t aState
) {
104 return kRead1
<= aState
&& aState
<= kReadMax
;
106 static bool IsRead1(uint32_t aState
) { return aState
== kRead1
; }
107 static bool IsWrite(uint32_t aState
) { return aState
== kWrite
; }
109 bool IsIdle() const { return mState
== kIdle
; }
111 bool IsWritable() const { return mIsWritable
; }
113 void SetNonWritable() { mIsWritable
= false; }
115 // NOTE: the obvious way to implement these functions is to (a) check
116 // |mState| is reasonable, and then (b) update |mState|. But the lack of
117 // atomicity in such an implementation can cause problems if we get unlucky
118 // thread interleaving between (a) and (b).
120 // So instead for |mState| we are careful to (a) first get |mState|'s old
121 // value and assign it a new value in single atomic operation, and only then
122 // (b) check the old value was reasonable. This ensures we don't have
123 // interleaving problems.
125 // For |mIsWritable| we don't need to be as careful because it can only in
126 // transition in one direction (from writable to non-writable).
129 uint32_t oldState
= mState
++; // this is an atomic increment
130 MOZ_RELEASE_ASSERT(IsIdle(oldState
) || IsRead(oldState
));
131 MOZ_RELEASE_ASSERT(oldState
< kReadMax
); // check for overflow
135 uint32_t oldState
= mState
--; // this is an atomic decrement
136 MOZ_RELEASE_ASSERT(IsRead(oldState
));
139 void StartWriteOp() {
140 MOZ_RELEASE_ASSERT(IsWritable());
141 uint32_t oldState
= mState
.exchange(kWrite
);
142 MOZ_RELEASE_ASSERT(IsIdle(oldState
));
146 // Check again that the table is writable, in case it was marked as
147 // non-writable just after the IsWritable() assertion in StartWriteOp()
149 MOZ_RELEASE_ASSERT(IsWritable());
150 uint32_t oldState
= mState
.exchange(kIdle
);
151 MOZ_RELEASE_ASSERT(IsWrite(oldState
));
154 void StartIteratorRemovalOp() {
155 // When doing removals at the end of iteration, we go from Read1 state to
156 // Write and then back.
157 MOZ_RELEASE_ASSERT(IsWritable());
158 uint32_t oldState
= mState
.exchange(kWrite
);
159 MOZ_RELEASE_ASSERT(IsRead1(oldState
));
162 void EndIteratorRemovalOp() {
163 // Check again that the table is writable, in case it was marked as
164 // non-writable just after the IsWritable() assertion in
165 // StartIteratorRemovalOp() occurred.
166 MOZ_RELEASE_ASSERT(IsWritable());
167 uint32_t oldState
= mState
.exchange(kRead1
);
168 MOZ_RELEASE_ASSERT(IsWrite(oldState
));
171 void StartDestructorOp() {
172 // A destructor op is like a write, but the table doesn't need to be
174 uint32_t oldState
= mState
.exchange(kWrite
);
175 MOZ_RELEASE_ASSERT(IsIdle(oldState
));
178 void EndDestructorOp() {
179 uint32_t oldState
= mState
.exchange(kIdle
);
180 MOZ_RELEASE_ASSERT(IsWrite(oldState
));
184 // Things of note about the representation of |mState|.
185 // - The values between kRead1..kReadMax represent valid Read(n) values.
186 // - kIdle and kRead1 are deliberately chosen so that incrementing the -
187 // former gives the latter.
188 // - 9999 concurrent readers should be enough for anybody.
189 static const uint32_t kIdle
= 0;
190 static const uint32_t kRead1
= 1;
191 static const uint32_t kReadMax
= 9999;
192 static const uint32_t kWrite
= 10000;
194 mozilla::Atomic
<uint32_t, mozilla::SequentiallyConsistent
> mState
;
195 mozilla::Atomic
<bool, mozilla::SequentiallyConsistent
> mIsWritable
;
199 // A PLDHashTable may be allocated on the stack or within another structure or
200 // class. No entry storage is allocated until the first element is added. This
201 // means that empty hash tables are cheap, which is good because they are
204 // There used to be a long, math-heavy comment here about the merits of
205 // double hashing vs. chaining; it was removed in bug 1058335. In short, double
206 // hashing is more space-efficient unless the element size gets large (in which
207 // case you should keep using double hashing but switch to using pointer
208 // elements). Also, with double hashing, you can't safely hold an entry pointer
209 // and use it after an add or remove operation, unless you sample Generation()
210 // before adding or removing, and compare the sample after, dereferencing the
211 // entry pointer only if Generation() has not changed.
214 // A slot represents a cached hash value and its associated entry stored in
215 // the hash table. The hash value and the entry are not stored contiguously.
217 Slot(PLDHashEntryHdr
* aEntry
, PLDHashNumber
* aKeyHash
)
218 : mEntry(aEntry
), mKeyHash(aKeyHash
) {}
220 Slot(const Slot
&) = default;
221 Slot(Slot
&& aOther
) = default;
223 Slot
& operator=(Slot
&& aOther
) = default;
225 bool operator==(const Slot
& aOther
) { return mEntry
== aOther
.mEntry
; }
227 PLDHashNumber
KeyHash() const { return *HashPtr(); }
228 void SetKeyHash(PLDHashNumber aHash
) { *HashPtr() = aHash
; }
230 PLDHashEntryHdr
* ToEntry() const { return mEntry
; }
232 bool IsFree() const { return KeyHash() == 0; }
233 bool IsRemoved() const { return KeyHash() == 1; }
234 bool IsLive() const { return IsLiveHash(KeyHash()); }
235 static bool IsLiveHash(uint32_t aHash
) { return aHash
>= 2; }
237 void MarkFree() { *HashPtr() = 0; }
238 void MarkRemoved() { *HashPtr() = 1; }
239 void MarkColliding() { *HashPtr() |= kCollisionFlag
; }
241 void Next(uint32_t aEntrySize
) {
242 char* p
= reinterpret_cast<char*>(mEntry
);
244 mEntry
= reinterpret_cast<PLDHashEntryHdr
*>(p
);
247 PLDHashNumber
* HashPtr() const { return mKeyHash
; }
250 PLDHashEntryHdr
* mEntry
;
251 PLDHashNumber
* mKeyHash
;
254 // This class maintains the invariant that every time the entry store is
255 // changed, the generation is updated.
257 // The data layout separates the cached hashes of entries and the entries
258 // themselves to save space. We could store the entries thusly:
260 // +--------+--------+---------+
261 // | entry0 | entry1 | ... |
262 // +--------+--------+---------+
264 // where the entries themselves contain the cached hash stored as their
265 // first member. PLDHashTable did this for a long time, with entries looking
268 // class PLDHashEntryHdr
270 // PLDHashNumber mKeyHash;
273 // class MyEntry : public PLDHashEntryHdr
278 // The problem with this setup is that, depending on the layout of
279 // `MyEntry`, there may be platform ABI-mandated padding between `mKeyHash`
280 // and the first member of `MyEntry`. This ABI-mandated padding is wasted
281 // space, and was surprisingly common, e.g. when MyEntry contained a single
282 // pointer on 64-bit platforms.
284 // As previously alluded to, the current setup stores things thusly:
286 // +-------+-------+-------+-------+--------+--------+---------+
287 // | hash0 | hash1 | ..... | hashN | entry0 | entry1 | ... |
288 // +-------+-------+-------+-------+--------+--------+---------+
290 // which contains no wasted space between the hashes themselves, and no
291 // wasted space between the entries themselves. malloc is guaranteed to
292 // return blocks of memory with at least word alignment on all of our major
293 // platforms. PLDHashTable mandates that the size of the hash table is
294 // always a power of two, so the alignment of the memory containing the
295 // first entry is always at least the alignment of the entire entry store.
296 // That means the alignment of `entry0` should be its natural alignment.
297 // Entries may have problems if they contain over-aligned members such as
298 // SIMD vector types, but this has not been a problem in practice.
300 // Note: It would be natural to store the generation within this class, but
301 // we can't do that without bloating sizeof(PLDHashTable) on 64-bit machines.
302 // So instead we store it outside this class, and Set() takes a pointer to it
303 // and ensures it is updated as necessary.
308 static char* Entries(char* aStore
, uint32_t aCapacity
) {
309 return aStore
+ aCapacity
* sizeof(PLDHashNumber
);
312 char* Entries(uint32_t aCapacity
) const {
313 return Entries(Get(), aCapacity
);
317 EntryStore() : mEntryStore(nullptr) {}
321 mEntryStore
= nullptr;
324 char* Get() const { return mEntryStore
; }
325 bool IsAllocated() const { return !!mEntryStore
; }
327 Slot
SlotForIndex(uint32_t aIndex
, uint32_t aEntrySize
,
328 uint32_t aCapacity
) const {
329 char* entries
= Entries(aCapacity
);
331 reinterpret_cast<PLDHashEntryHdr
*>(entries
+ aIndex
* aEntrySize
);
332 auto hashes
= reinterpret_cast<PLDHashNumber
*>(Get());
333 return Slot(entry
, &hashes
[aIndex
]);
336 Slot
SlotForPLDHashEntry(PLDHashEntryHdr
* aEntry
, uint32_t aCapacity
,
337 uint32_t aEntrySize
) {
338 char* entries
= Entries(aCapacity
);
339 char* entry
= reinterpret_cast<char*>(aEntry
);
340 uint32_t entryOffset
= entry
- entries
;
341 uint32_t slotIndex
= entryOffset
/ aEntrySize
;
342 return SlotForIndex(slotIndex
, aEntrySize
, aCapacity
);
345 template <typename F
>
346 void ForEachSlot(uint32_t aCapacity
, uint32_t aEntrySize
, F
&& aFunc
) {
347 ForEachSlot(Get(), aCapacity
, aEntrySize
, std::move(aFunc
));
350 template <typename F
>
351 static void ForEachSlot(char* aStore
, uint32_t aCapacity
,
352 uint32_t aEntrySize
, F
&& aFunc
) {
353 char* entries
= Entries(aStore
, aCapacity
);
354 Slot
slot(reinterpret_cast<PLDHashEntryHdr
*>(entries
),
355 reinterpret_cast<PLDHashNumber
*>(aStore
));
356 for (size_t i
= 0; i
< aCapacity
; ++i
) {
358 slot
.Next(aEntrySize
);
362 void Set(char* aEntryStore
, uint16_t* aGeneration
) {
363 mEntryStore
= aEntryStore
;
368 // These fields are packed carefully. On 32-bit platforms,
369 // sizeof(PLDHashTable) is 20. On 64-bit platforms, sizeof(PLDHashTable) is
370 // 32; 28 bytes of data followed by 4 bytes of padding for alignment.
371 const PLDHashTableOps
* const mOps
; // Virtual operations; see below.
372 EntryStore mEntryStore
; // (Lazy) entry storage and generation.
373 uint16_t mGeneration
; // The storage generation.
374 uint8_t mHashShift
; // Multiplicative hash shift.
375 const uint8_t mEntrySize
; // Number of bytes in an entry.
376 uint32_t mEntryCount
; // Number of entries in table.
377 uint32_t mRemovedCount
; // Removed entry sentinels in table.
379 #ifdef MOZ_HASH_TABLE_CHECKS_ENABLED
380 mutable Checker mChecker
;
384 // Table capacity limit; do not exceed. The max capacity used to be 1<<23 but
385 // that occasionally that wasn't enough. Making it much bigger than 1<<26
386 // probably isn't worthwhile -- tables that big are kind of ridiculous.
387 // Also, the growth operation will (deliberately) fail if |capacity *
388 // mEntrySize| overflows a uint32_t, and mEntrySize is always at least 8
390 static const uint32_t kMaxCapacity
= ((uint32_t)1 << 26);
392 static const uint32_t kMinCapacity
= 8;
394 // Making this half of kMaxCapacity ensures it'll fit. Nobody should need an
395 // initial length anywhere nearly this large, anyway.
396 static const uint32_t kMaxInitialLength
= kMaxCapacity
/ 2;
398 // This gives a default initial capacity of 8.
399 static const uint32_t kDefaultInitialLength
= 4;
401 // Initialize the table with |aOps| and |aEntrySize|. The table's initial
402 // capacity is chosen such that |aLength| elements can be inserted without
403 // rehashing; if |aLength| is a power-of-two, this capacity will be
404 // |2*length|. However, because entry storage is allocated lazily, this
405 // initial capacity won't be relevant until the first element is added; prior
406 // to that the capacity will be zero.
408 // This will crash if |aEntrySize| and/or |aLength| are too large.
409 PLDHashTable(const PLDHashTableOps
* aOps
, uint32_t aEntrySize
,
410 uint32_t aLength
= kDefaultInitialLength
);
412 PLDHashTable(PLDHashTable
&& aOther
)
413 // Initialize fields which are checked by the move assignment operator
414 // and the destructor (which the move assignment operator calls).
415 : mOps(nullptr), mEntryStore(), mGeneration(0), mEntrySize(0) {
416 *this = std::move(aOther
);
419 PLDHashTable
& operator=(PLDHashTable
&& aOther
);
423 // This should be used rarely.
424 const PLDHashTableOps
* Ops() const { return mOps
; }
426 // Size in entries (gross, not net of free and removed sentinels) for table.
427 // This can be zero if no elements have been added yet, in which case the
428 // entry storage will not have yet been allocated.
429 uint32_t Capacity() const {
430 return mEntryStore
.IsAllocated() ? CapacityFromHashShift() : 0;
433 uint32_t EntrySize() const { return mEntrySize
; }
434 uint32_t EntryCount() const { return mEntryCount
; }
435 uint32_t Generation() const { return mGeneration
; }
437 // To search for a |key| in |table|, call:
439 // entry = table.Search(key);
441 // If |entry| is non-null, |key| was found. If |entry| is null, key was not
443 PLDHashEntryHdr
* Search(const void* aKey
) const;
445 // To add an entry identified by |key| to table, call:
447 // entry = table.Add(key, mozilla::fallible);
449 // If |entry| is null upon return, then the table is severely overloaded and
450 // memory can't be allocated for entry storage.
452 // Otherwise, if the initEntry hook was provided, |entry| will be
453 // initialized. If the initEntry hook was not provided, the caller
454 // should initialize |entry| as appropriate.
455 PLDHashEntryHdr
* Add(const void* aKey
, const mozilla::fallible_t
&);
457 // This is like the other Add() function, but infallible, and so never
459 PLDHashEntryHdr
* Add(const void* aKey
);
461 // To remove an entry identified by |key| from table, call:
463 // table.Remove(key);
465 // If |key|'s entry is found, it is cleared (via table->mOps->clearEntry).
466 // The table's capacity may be reduced afterwards.
467 void Remove(const void* aKey
);
469 // To remove an entry found by a prior search, call:
471 // table.RemoveEntry(entry);
473 // The entry, which must be present and in use, is cleared (via
474 // table->mOps->clearEntry). The table's capacity may be reduced afterwards.
475 void RemoveEntry(PLDHashEntryHdr
* aEntry
);
477 // Remove an entry already accessed via Search() or Add().
479 // NB: this is a "raw" or low-level method. It does not shrink the table if
480 // it is underloaded. Don't use it unless necessary and you know what you are
481 // doing, and if so, please explain in a comment why it is necessary instead
483 void RawRemove(PLDHashEntryHdr
* aEntry
);
485 // This function is equivalent to
486 // ClearAndPrepareForLength(kDefaultInitialLength).
489 // This function clears the table's contents and frees its entry storage,
490 // leaving it in a empty state ready to be used again. Afterwards, when the
491 // first element is added the entry storage that gets allocated will have a
492 // capacity large enough to fit |aLength| elements without rehashing.
494 // It's conceptually the same as calling the destructor and then re-calling
495 // the constructor with the original |aOps| and |aEntrySize| arguments, and
496 // a new |aLength| argument.
497 void ClearAndPrepareForLength(uint32_t aLength
);
499 // Measure the size of the table's entry storage. If the entries contain
500 // pointers to other heap blocks, you have to iterate over the table and
501 // measure those separately; hence the "Shallow" prefix.
502 size_t ShallowSizeOfIncludingThis(mozilla::MallocSizeOf aMallocSizeOf
) const;
504 // Like ShallowSizeOfExcludingThis(), but includes sizeof(*this).
505 size_t ShallowSizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf
) const;
507 // Mark a table as immutable for the remainder of its lifetime. This
508 // changes the implementation from asserting one set of invariants to
509 // asserting a different set.
510 void MarkImmutable() {
511 #ifdef MOZ_HASH_TABLE_CHECKS_ENABLED
512 mChecker
.SetNonWritable();
516 // If you use PLDHashEntryStub or a subclass of it as your entry struct, and
517 // if your entries move via memcpy and clear via memset(0), you can use these
519 static const PLDHashTableOps
* StubOps();
521 // The individual stub operations in StubOps().
522 static PLDHashNumber
HashVoidPtrKeyStub(const void* aKey
);
523 static bool MatchEntryStub(const PLDHashEntryHdr
* aEntry
, const void* aKey
);
524 static void MoveEntryStub(PLDHashTable
* aTable
, const PLDHashEntryHdr
* aFrom
,
525 PLDHashEntryHdr
* aTo
);
526 static void ClearEntryStub(PLDHashTable
* aTable
, PLDHashEntryHdr
* aEntry
);
528 // Hash/match operations for tables holding C strings.
529 static PLDHashNumber
HashStringKey(const void* aKey
);
530 static bool MatchStringKey(const PLDHashEntryHdr
* aEntry
, const void* aKey
);
534 EntryHandle(EntryHandle
&& aOther
) noexcept
;
535 #ifdef MOZ_HASH_TABLE_CHECKS_ENABLED
539 EntryHandle(const EntryHandle
&) = delete;
540 EntryHandle
& operator=(const EntryHandle
&) = delete;
541 EntryHandle
& operator=(EntryHandle
&& aOther
) = delete;
543 // Is this slot currently occupied?
544 bool HasEntry() const { return mSlot
.IsLive(); }
546 explicit operator bool() const { return HasEntry(); }
548 // Get the entry stored in this slot. May not be called unless the slot is
549 // currently occupied.
550 PLDHashEntryHdr
* Entry() {
551 MOZ_ASSERT(HasEntry());
552 return mSlot
.ToEntry();
556 void Insert(F
&& aInitEntry
) {
557 MOZ_ASSERT(!HasEntry());
559 std::forward
<F
>(aInitEntry
)(Entry());
562 // If the slot is currently vacant, the slot is occupied and `initEntry` is
563 // invoked to initialize the entry. Returns the entry stored in now-occupied
566 PLDHashEntryHdr
* OrInsert(F
&& aInitEntry
) {
568 Insert(std::forward
<F
>(aInitEntry
));
573 /** Removes the entry. Note that the table won't shrink on destruction of
581 /** Removes the entry, if it exists. Note that the table won't shrink on
582 * destruction of the EntryHandle.
589 friend class PLDHashTable
;
591 EntryHandle(PLDHashTable
* aTable
, PLDHashNumber aKeyHash
, Slot aSlot
);
595 PLDHashTable
* mTable
;
596 PLDHashNumber mKeyHash
;
601 auto WithEntryHandle(const void* aKey
, F
&& aFunc
)
602 -> std::invoke_result_t
<F
, EntryHandle
&&> {
603 return std::forward
<F
>(aFunc
)(MakeEntryHandle(aKey
));
607 auto WithEntryHandle(const void* aKey
, const mozilla::fallible_t
& aFallible
,
609 -> std::invoke_result_t
<F
, mozilla::Maybe
<EntryHandle
>&&> {
610 return std::forward
<F
>(aFunc
)(MakeEntryHandle(aKey
, aFallible
));
613 // This is an iterator for PLDHashtable. Assertions will detect some, but not
614 // all, mid-iteration table modifications that might invalidate (e.g.
615 // reallocate) the entry storage.
617 // Any element can be removed during iteration using Remove(). If any
618 // elements are removed, the table may be resized once iteration ends.
622 // for (auto iter = table.Iter(); !iter.Done(); iter.Next()) {
623 // auto entry = static_cast<FooEntry*>(iter.Get());
624 // // ... do stuff with |entry| ...
625 // // ... possibly call iter.Remove() once ...
630 // for (PLDHashTable::Iterator iter(&table); !iter.Done(); iter.Next()) {
631 // auto entry = static_cast<FooEntry*>(iter.Get());
632 // // ... do stuff with |entry| ...
633 // // ... possibly call iter.Remove() once ...
636 // The latter form is more verbose but is easier to work with when
637 // making subclasses of Iterator.
641 explicit Iterator(PLDHashTable
* aTable
);
642 struct EndIteratorTag
{};
643 Iterator(PLDHashTable
* aTable
, EndIteratorTag aTag
);
644 Iterator(Iterator
&& aOther
);
648 bool Done() const { return mNexts
== mNextsLimit
; }
650 // Get the current entry.
651 PLDHashEntryHdr
* Get() const {
653 MOZ_ASSERT(mCurrent
.IsLive());
654 return mCurrent
.ToEntry();
657 // Advance to the next entry.
660 // Remove the current entry. Must only be called once per entry, and Get()
661 // must not be called on that entry afterwards.
664 bool operator==(const Iterator
& aOther
) const {
665 MOZ_ASSERT(mTable
== aOther
.mTable
);
666 return mNexts
== aOther
.mNexts
;
669 Iterator
Clone() const { return {*this}; }
672 PLDHashTable
* mTable
; // Main table pointer.
675 Slot mCurrent
; // Pointer to the current entry.
676 uint32_t mNexts
; // Number of Next() calls.
677 uint32_t mNextsLimit
; // Next() call limit.
679 bool mHaveRemoved
; // Have any elements been removed?
680 uint8_t mEntrySize
; // Size of entries.
682 bool IsOnNonLiveEntry() const;
684 void MoveToNextLiveEntry();
687 Iterator(const Iterator
&);
688 Iterator
& operator=(const Iterator
&) = delete;
689 Iterator
& operator=(const Iterator
&&) = delete;
692 Iterator
Iter() { return Iterator(this); }
694 // Use this if you need to initialize an Iterator in a const method. If you
695 // use this case, you should not call Remove() on the iterator.
696 Iterator
ConstIter() const {
697 return Iterator(const_cast<PLDHashTable
*>(this));
701 static uint32_t HashShift(uint32_t aEntrySize
, uint32_t aLength
);
703 static const PLDHashNumber kCollisionFlag
= 1;
705 PLDHashNumber
Hash1(PLDHashNumber aHash0
) const;
706 void Hash2(PLDHashNumber aHash
, uint32_t& aHash2Out
,
707 uint32_t& aSizeMaskOut
) const;
709 static bool MatchSlotKeyhash(Slot
& aSlot
, const PLDHashNumber aHash
);
710 Slot
SlotForIndex(uint32_t aIndex
) const;
712 // We store mHashShift rather than sizeLog2 to optimize the collision-free
713 // case in SearchTable.
714 uint32_t CapacityFromHashShift() const {
715 return ((uint32_t)1 << (kPLDHashNumberBits
- mHashShift
));
718 PLDHashNumber
ComputeKeyHash(const void* aKey
) const;
720 enum SearchReason
{ ForSearchOrRemove
, ForAdd
};
722 // Avoid using bare `Success` and `Failure`, as those names are commonly
723 // defined as macros.
724 template <SearchReason Reason
, typename PLDSuccess
, typename PLDFailure
>
725 auto SearchTable(const void* aKey
, PLDHashNumber aKeyHash
,
726 PLDSuccess
&& aSucess
, PLDFailure
&& aFailure
) const;
728 Slot
FindFreeSlot(PLDHashNumber aKeyHash
) const;
730 bool ChangeTable(int aDeltaLog2
);
732 void RawRemove(Slot
& aSlot
);
733 void ShrinkIfAppropriate();
735 mozilla::Maybe
<EntryHandle
> MakeEntryHandle(const void* aKey
,
736 const mozilla::fallible_t
&);
738 EntryHandle
MakeEntryHandle(const void* aKey
);
740 PLDHashTable(const PLDHashTable
& aOther
) = delete;
741 PLDHashTable
& operator=(const PLDHashTable
& aOther
) = delete;
744 // Compute the hash code for a given key to be looked up, added, or removed.
745 // A hash code may have any PLDHashNumber value.
746 typedef PLDHashNumber (*PLDHashHashKey
)(const void* aKey
);
748 // Compare the key identifying aEntry with the provided key parameter. Return
749 // true if keys match, false otherwise.
750 typedef bool (*PLDHashMatchEntry
)(const PLDHashEntryHdr
* aEntry
,
753 // Copy the data starting at aFrom to the new entry storage at aTo. Do not add
754 // reference counts for any strong references in the entry, however, as this
755 // is a "move" operation: the old entry storage at from will be freed without
756 // any reference-decrementing callback shortly.
757 typedef void (*PLDHashMoveEntry
)(PLDHashTable
* aTable
,
758 const PLDHashEntryHdr
* aFrom
,
759 PLDHashEntryHdr
* aTo
);
761 // Clear the entry and drop any strong references it holds. This callback is
762 // invoked by Remove(), but only if the given key is found in the table.
763 typedef void (*PLDHashClearEntry
)(PLDHashTable
* aTable
,
764 PLDHashEntryHdr
* aEntry
);
766 // Initialize a new entry. This function is called when
767 // Add() finds no existing entry for the given key, and must add a new one.
768 typedef void (*PLDHashInitEntry
)(PLDHashEntryHdr
* aEntry
, const void* aKey
);
770 // Finally, the "vtable" structure for PLDHashTable. The first four hooks
771 // must be provided by implementations; they're called unconditionally by the
772 // generic PLDHashTable.cpp code. Hooks after these may be null.
774 // Summary of allocation-related hook usage with C++ placement new emphasis:
775 // initEntry Call placement new using default key-based ctor.
776 // moveEntry Call placement new using copy ctor, run dtor on old
778 // clearEntry Run dtor on entry.
780 // Note the reason why initEntry is optional: the default hooks (stubs) clear
781 // entry storage. On a successful Add(tbl, key), the returned entry pointer
782 // addresses an entry struct whose entry members are still clear (null). Add()
783 // callers can test such members to see whether the entry was newly created by
784 // the Add() call that just succeeded. If placement new or similar
785 // initialization is required, define an |initEntry| hook. Of course, the
786 // |clearEntry| hook must zero or null appropriately.
788 // XXX assumes 0 is null for pointer types.
789 struct PLDHashTableOps
{
790 // Mandatory hooks. All implementations must provide these.
791 PLDHashHashKey hashKey
;
792 PLDHashMatchEntry matchEntry
;
793 PLDHashMoveEntry moveEntry
;
795 // Optional hooks start here. If null, these are not called.
796 PLDHashClearEntry clearEntry
;
797 PLDHashInitEntry initEntry
;
800 // A minimal entry is a subclass of PLDHashEntryHdr and has a void* key pointer.
801 struct PLDHashEntryStub
: public PLDHashEntryHdr
{
805 #endif /* PLDHashTable_h */