summaryrefslogtreecommitdiffstats
path: root/xpcom/ds/PLDHashTable.cpp
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-19 00:47:55 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-19 00:47:55 +0000
commit26a029d407be480d791972afb5975cf62c9360a6 (patch)
treef435a8308119effd964b339f76abb83a57c29483 /xpcom/ds/PLDHashTable.cpp
parentInitial commit. (diff)
downloadfirefox-26a029d407be480d791972afb5975cf62c9360a6.tar.xz
firefox-26a029d407be480d791972afb5975cf62c9360a6.zip
Adding upstream version 124.0.1.upstream/124.0.1
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'xpcom/ds/PLDHashTable.cpp')
-rw-r--r--xpcom/ds/PLDHashTable.cpp869
1 files changed, 869 insertions, 0 deletions
diff --git a/xpcom/ds/PLDHashTable.cpp b/xpcom/ds/PLDHashTable.cpp
new file mode 100644
index 0000000000..75a512ba7a
--- /dev/null
+++ b/xpcom/ds/PLDHashTable.cpp
@@ -0,0 +1,869 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim: set ts=8 sts=2 et sw=2 tw=80: */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include <new>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include "PLDHashTable.h"
+#include "nsDebug.h"
+#include "mozilla/HashFunctions.h"
+#include "mozilla/MathAlgorithms.h"
+#include "mozilla/OperatorNewExtensions.h"
+#include "mozilla/ScopeExit.h"
+#include "nsAlgorithm.h"
+#include "nsPointerHashKeys.h"
+#include "mozilla/Likely.h"
+#include "mozilla/MemoryReporting.h"
+#include "mozilla/Maybe.h"
+#include "mozilla/ChaosMode.h"
+
+using namespace mozilla;
+
+#ifdef MOZ_HASH_TABLE_CHECKS_ENABLED
+
+class AutoReadOp {
+ Checker& mChk;
+
+ public:
+ explicit AutoReadOp(Checker& aChk) : mChk(aChk) { mChk.StartReadOp(); }
+ ~AutoReadOp() { mChk.EndReadOp(); }
+};
+
+class AutoWriteOp {
+ Checker& mChk;
+
+ public:
+ explicit AutoWriteOp(Checker& aChk) : mChk(aChk) { mChk.StartWriteOp(); }
+ ~AutoWriteOp() { mChk.EndWriteOp(); }
+};
+
+class AutoIteratorRemovalOp {
+ Checker& mChk;
+
+ public:
+ explicit AutoIteratorRemovalOp(Checker& aChk) : mChk(aChk) {
+ mChk.StartIteratorRemovalOp();
+ }
+ ~AutoIteratorRemovalOp() { mChk.EndIteratorRemovalOp(); }
+};
+
+class AutoDestructorOp {
+ Checker& mChk;
+
+ public:
+ explicit AutoDestructorOp(Checker& aChk) : mChk(aChk) {
+ mChk.StartDestructorOp();
+ }
+ ~AutoDestructorOp() { mChk.EndDestructorOp(); }
+};
+
+#endif
+
+/* static */
+PLDHashNumber PLDHashTable::HashStringKey(const void* aKey) {
+ return HashString(static_cast<const char*>(aKey));
+}
+
+/* static */
+PLDHashNumber PLDHashTable::HashVoidPtrKeyStub(const void* aKey) {
+ return nsPtrHashKey<void>::HashKey(aKey);
+}
+
+/* static */
+bool PLDHashTable::MatchEntryStub(const PLDHashEntryHdr* aEntry,
+ const void* aKey) {
+ const PLDHashEntryStub* stub = (const PLDHashEntryStub*)aEntry;
+
+ return stub->key == aKey;
+}
+
+/* static */
+bool PLDHashTable::MatchStringKey(const PLDHashEntryHdr* aEntry,
+ const void* aKey) {
+ const PLDHashEntryStub* stub = (const PLDHashEntryStub*)aEntry;
+
+ // XXX tolerate null keys on account of sloppy Mozilla callers.
+ return stub->key == aKey ||
+ (stub->key && aKey &&
+ strcmp((const char*)stub->key, (const char*)aKey) == 0);
+}
+
+/* static */
+void PLDHashTable::MoveEntryStub(PLDHashTable* aTable,
+ const PLDHashEntryHdr* aFrom,
+ PLDHashEntryHdr* aTo) {
+ memcpy(aTo, aFrom, aTable->mEntrySize);
+}
+
+/* static */
+void PLDHashTable::ClearEntryStub(PLDHashTable* aTable,
+ PLDHashEntryHdr* aEntry) {
+ memset(aEntry, 0, aTable->mEntrySize);
+}
+
+static const PLDHashTableOps gStubOps = {
+ PLDHashTable::HashVoidPtrKeyStub, PLDHashTable::MatchEntryStub,
+ PLDHashTable::MoveEntryStub, PLDHashTable::ClearEntryStub, nullptr};
+
+/* static */ const PLDHashTableOps* PLDHashTable::StubOps() {
+ return &gStubOps;
+}
+
+static bool SizeOfEntryStore(uint32_t aCapacity, uint32_t aEntrySize,
+ uint32_t* aNbytes) {
+ uint32_t slotSize = aEntrySize + sizeof(PLDHashNumber);
+ uint64_t nbytes64 = uint64_t(aCapacity) * uint64_t(slotSize);
+ *aNbytes = aCapacity * slotSize;
+ return uint64_t(*aNbytes) == nbytes64; // returns false on overflow
+}
+
+// Compute max and min load numbers (entry counts). We have a secondary max
+// that allows us to overload a table reasonably if it cannot be grown further
+// (i.e. if ChangeTable() fails). The table slows down drastically if the
+// secondary max is too close to 1, but 0.96875 gives only a slight slowdown
+// while allowing 1.3x more elements.
+static inline uint32_t MaxLoad(uint32_t aCapacity) {
+ return aCapacity - (aCapacity >> 2); // == aCapacity * 0.75
+}
+static inline uint32_t MaxLoadOnGrowthFailure(uint32_t aCapacity) {
+ return aCapacity - (aCapacity >> 5); // == aCapacity * 0.96875
+}
+static inline uint32_t MinLoad(uint32_t aCapacity) {
+ return aCapacity >> 2; // == aCapacity * 0.25
+}
+
+// Compute the minimum capacity (and the Log2 of that capacity) for a table
+// containing |aLength| elements while respecting the following contraints:
+// - table must be at most 75% full;
+// - capacity must be a power of two;
+// - capacity cannot be too small.
+static inline void BestCapacity(uint32_t aLength, uint32_t* aCapacityOut,
+ uint32_t* aLog2CapacityOut) {
+ // Callers should ensure this is true.
+ MOZ_ASSERT(aLength <= PLDHashTable::kMaxInitialLength);
+
+ // Compute the smallest capacity allowing |aLength| elements to be inserted
+ // without rehashing.
+ uint32_t capacity = (aLength * 4 + (3 - 1)) / 3; // == ceil(aLength * 4 / 3)
+ if (capacity < PLDHashTable::kMinCapacity) {
+ capacity = PLDHashTable::kMinCapacity;
+ }
+
+ // Round up capacity to next power-of-two.
+ uint32_t log2 = CeilingLog2(capacity);
+ capacity = 1u << log2;
+ MOZ_ASSERT(capacity <= PLDHashTable::kMaxCapacity);
+
+ *aCapacityOut = capacity;
+ *aLog2CapacityOut = log2;
+}
+
+/* static */ MOZ_ALWAYS_INLINE uint32_t
+PLDHashTable::HashShift(uint32_t aEntrySize, uint32_t aLength) {
+ if (aLength > kMaxInitialLength) {
+ MOZ_CRASH("Initial length is too large");
+ }
+
+ uint32_t capacity, log2;
+ BestCapacity(aLength, &capacity, &log2);
+
+ uint32_t nbytes;
+ if (!SizeOfEntryStore(capacity, aEntrySize, &nbytes)) {
+ MOZ_CRASH("Initial entry store size is too large");
+ }
+
+ // Compute the hashShift value.
+ return kPLDHashNumberBits - log2;
+}
+
+PLDHashTable::PLDHashTable(const PLDHashTableOps* aOps, uint32_t aEntrySize,
+ uint32_t aLength)
+ : mOps(aOps),
+ mGeneration(0),
+ mHashShift(HashShift(aEntrySize, aLength)),
+ mEntrySize(aEntrySize),
+ mEntryCount(0),
+ mRemovedCount(0) {
+ // An entry size greater than 0xff is unlikely, but let's check anyway. If
+ // you hit this, your hashtable would waste lots of space for unused entries
+ // and you should change your hash table's entries to pointers.
+ if (aEntrySize != uint32_t(mEntrySize)) {
+ MOZ_CRASH("Entry size is too large");
+ }
+}
+
+PLDHashTable& PLDHashTable::operator=(PLDHashTable&& aOther) {
+ if (this == &aOther) {
+ return *this;
+ }
+
+ // |mOps| and |mEntrySize| are required to stay the same, they're
+ // conceptually part of the type -- indeed, if PLDHashTable was a templated
+ // type like nsTHashtable, they *would* be part of the type -- so it only
+ // makes sense to assign in cases where they match.
+ MOZ_RELEASE_ASSERT(mOps == aOther.mOps || !mOps);
+ MOZ_RELEASE_ASSERT(mEntrySize == aOther.mEntrySize || !mEntrySize);
+
+ // Reconstruct |this|.
+ const PLDHashTableOps* ops = aOther.mOps;
+ this->~PLDHashTable();
+ new (KnownNotNull, this) PLDHashTable(ops, aOther.mEntrySize, 0);
+
+ // Move non-const pieces over.
+ mHashShift = std::move(aOther.mHashShift);
+ mEntryCount = std::move(aOther.mEntryCount);
+ mRemovedCount = std::move(aOther.mRemovedCount);
+ mEntryStore.Set(aOther.mEntryStore.Get(), &mGeneration);
+#ifdef MOZ_HASH_TABLE_CHECKS_ENABLED
+ mChecker = std::move(aOther.mChecker);
+#endif
+
+ // Clear up |aOther| so its destruction will be a no-op and it reports being
+ // empty.
+ {
+#ifdef MOZ_HASH_TABLE_CHECKS_ENABLED
+ AutoDestructorOp op(mChecker);
+#endif
+ aOther.mEntryCount = 0;
+ aOther.mEntryStore.Set(nullptr, &aOther.mGeneration);
+ }
+
+ return *this;
+}
+
+PLDHashNumber PLDHashTable::Hash1(PLDHashNumber aHash0) const {
+ return aHash0 >> mHashShift;
+}
+
+void PLDHashTable::Hash2(PLDHashNumber aHash0, uint32_t& aHash2Out,
+ uint32_t& aSizeMaskOut) const {
+ uint32_t sizeLog2 = kPLDHashNumberBits - mHashShift;
+ uint32_t sizeMask = (PLDHashNumber(1) << sizeLog2) - 1;
+ aSizeMaskOut = sizeMask;
+
+ // The incoming aHash0 always has the low bit unset (since we leave it
+ // free for the collision flag), and should have reasonably random
+ // data in the other 31 bits. We used the high bits of aHash0 for
+ // Hash1, so we use the low bits here. If the table size is large,
+ // the bits we use may overlap, but that's still more random than
+ // filling with 0s.
+ //
+ // Double hashing needs the second hash code to be relatively prime to table
+ // size, so we simply make hash2 odd.
+ //
+ // This also conveniently covers up the fact that we have the low bit
+ // unset since aHash0 has the low bit unset.
+ aHash2Out = (aHash0 & sizeMask) | 1;
+}
+
+// Reserve mKeyHash 0 for free entries and 1 for removed-entry sentinels. Note
+// that a removed-entry sentinel need be stored only if the removed entry had
+// a colliding entry added after it. Therefore we can use 1 as the collision
+// flag in addition to the removed-entry sentinel value. Multiplicative hash
+// uses the high order bits of mKeyHash, so this least-significant reservation
+// should not hurt the hash function's effectiveness much.
+
+// Match an entry's mKeyHash against an unstored one computed from a key.
+/* static */
+bool PLDHashTable::MatchSlotKeyhash(Slot& aSlot, const PLDHashNumber aKeyHash) {
+ return (aSlot.KeyHash() & ~kCollisionFlag) == aKeyHash;
+}
+
+// Compute the address of the indexed entry in table.
+auto PLDHashTable::SlotForIndex(uint32_t aIndex) const -> Slot {
+ return mEntryStore.SlotForIndex(aIndex, mEntrySize, CapacityFromHashShift());
+}
+
+PLDHashTable::~PLDHashTable() {
+#ifdef MOZ_HASH_TABLE_CHECKS_ENABLED
+ AutoDestructorOp op(mChecker);
+#endif
+
+ if (!mEntryStore.IsAllocated()) {
+ return;
+ }
+
+ // Clear any remaining live entries (if not trivially destructible).
+ if (mOps->clearEntry) {
+ mEntryStore.ForEachSlot(Capacity(), mEntrySize, [&](const Slot& aSlot) {
+ if (aSlot.IsLive()) {
+ mOps->clearEntry(this, aSlot.ToEntry());
+ }
+ });
+ }
+
+ // Entry storage is freed last, by ~EntryStore().
+}
+
+void PLDHashTable::ClearAndPrepareForLength(uint32_t aLength) {
+ // Get these values before the destructor clobbers them.
+ const PLDHashTableOps* ops = mOps;
+ uint32_t entrySize = mEntrySize;
+
+ this->~PLDHashTable();
+ new (KnownNotNull, this) PLDHashTable(ops, entrySize, aLength);
+}
+
+void PLDHashTable::Clear() { ClearAndPrepareForLength(kDefaultInitialLength); }
+
+// If |Reason| is |ForAdd|, the return value is always non-null and it may be
+// a previously-removed entry. If |Reason| is |ForSearchOrRemove|, the return
+// value is null on a miss, and will never be a previously-removed entry on a
+// hit. This distinction is a bit grotty but this function is hot enough that
+// these differences are worthwhile. (It's also hot enough that
+// MOZ_ALWAYS_INLINE makes a significant difference.)
+template <PLDHashTable::SearchReason Reason, typename Success, typename Failure>
+MOZ_ALWAYS_INLINE auto PLDHashTable::SearchTable(const void* aKey,
+ PLDHashNumber aKeyHash,
+ Success&& aSuccess,
+ Failure&& aFailure) const {
+ MOZ_ASSERT(mEntryStore.IsAllocated());
+ NS_ASSERTION(!(aKeyHash & kCollisionFlag), "!(aKeyHash & kCollisionFlag)");
+
+ // Compute the primary hash address.
+ PLDHashNumber hash1 = Hash1(aKeyHash);
+ Slot slot = SlotForIndex(hash1);
+
+ // Miss: return space for a new entry.
+ if (slot.IsFree()) {
+ return (Reason == ForAdd) ? aSuccess(slot) : aFailure();
+ }
+
+ // Hit: return entry.
+ PLDHashMatchEntry matchEntry = mOps->matchEntry;
+ if (MatchSlotKeyhash(slot, aKeyHash)) {
+ PLDHashEntryHdr* e = slot.ToEntry();
+ if (matchEntry(e, aKey)) {
+ return aSuccess(slot);
+ }
+ }
+
+ // Collision: double hash.
+ PLDHashNumber hash2;
+ uint32_t sizeMask;
+ Hash2(aKeyHash, hash2, sizeMask);
+
+ // Save the first removed entry slot so Add() can recycle it. (Only used
+ // if Reason==ForAdd.)
+ Maybe<Slot> firstRemoved;
+
+ for (;;) {
+ if (Reason == ForAdd && !firstRemoved) {
+ if (MOZ_UNLIKELY(slot.IsRemoved())) {
+ firstRemoved.emplace(slot);
+ } else {
+ slot.MarkColliding();
+ }
+ }
+
+ hash1 -= hash2;
+ hash1 &= sizeMask;
+
+ slot = SlotForIndex(hash1);
+ if (slot.IsFree()) {
+ if (Reason != ForAdd) {
+ return aFailure();
+ }
+ return aSuccess(firstRemoved.refOr(slot));
+ }
+
+ if (MatchSlotKeyhash(slot, aKeyHash)) {
+ PLDHashEntryHdr* e = slot.ToEntry();
+ if (matchEntry(e, aKey)) {
+ return aSuccess(slot);
+ }
+ }
+ }
+
+ // NOTREACHED
+ return aFailure();
+}
+
+// This is a copy of SearchTable(), used by ChangeTable(), hardcoded to
+// 1. assume |Reason| is |ForAdd|,
+// 2. assume that |aKey| will never match an existing entry, and
+// 3. assume that no entries have been removed from the current table
+// structure.
+// Avoiding the need for |aKey| means we can avoid needing a way to map entries
+// to keys, which means callers can use complex key types more easily.
+MOZ_ALWAYS_INLINE auto PLDHashTable::FindFreeSlot(PLDHashNumber aKeyHash) const
+ -> Slot {
+ MOZ_ASSERT(mEntryStore.IsAllocated());
+ NS_ASSERTION(!(aKeyHash & kCollisionFlag), "!(aKeyHash & kCollisionFlag)");
+
+ // Compute the primary hash address.
+ PLDHashNumber hash1 = Hash1(aKeyHash);
+ Slot slot = SlotForIndex(hash1);
+
+ // Miss: return space for a new entry.
+ if (slot.IsFree()) {
+ return slot;
+ }
+
+ // Collision: double hash.
+ PLDHashNumber hash2;
+ uint32_t sizeMask;
+ Hash2(aKeyHash, hash2, sizeMask);
+
+ for (;;) {
+ MOZ_ASSERT(!slot.IsRemoved());
+ slot.MarkColliding();
+
+ hash1 -= hash2;
+ hash1 &= sizeMask;
+
+ slot = SlotForIndex(hash1);
+ if (slot.IsFree()) {
+ return slot;
+ }
+ }
+
+ // NOTREACHED
+}
+
+bool PLDHashTable::ChangeTable(int32_t aDeltaLog2) {
+ MOZ_ASSERT(mEntryStore.IsAllocated());
+
+ // Look, but don't touch, until we succeed in getting new entry store.
+ int32_t oldLog2 = kPLDHashNumberBits - mHashShift;
+ int32_t newLog2 = oldLog2 + aDeltaLog2;
+ uint32_t newCapacity = 1u << newLog2;
+ if (newCapacity > kMaxCapacity) {
+ return false;
+ }
+
+ uint32_t nbytes;
+ if (!SizeOfEntryStore(newCapacity, mEntrySize, &nbytes)) {
+ return false; // overflowed
+ }
+
+ char* newEntryStore = (char*)calloc(1, nbytes);
+ if (!newEntryStore) {
+ return false;
+ }
+
+ // We can't fail from here on, so update table parameters.
+ mHashShift = kPLDHashNumberBits - newLog2;
+ mRemovedCount = 0;
+
+ // Assign the new entry store to table.
+ char* oldEntryStore = mEntryStore.Get();
+ mEntryStore.Set(newEntryStore, &mGeneration);
+ PLDHashMoveEntry moveEntry = mOps->moveEntry;
+
+ // Copy only live entries, leaving removed ones behind.
+ uint32_t oldCapacity = 1u << oldLog2;
+ EntryStore::ForEachSlot(
+ oldEntryStore, oldCapacity, mEntrySize, [&](const Slot& slot) {
+ if (slot.IsLive()) {
+ const PLDHashNumber key = slot.KeyHash() & ~kCollisionFlag;
+ Slot newSlot = FindFreeSlot(key);
+ MOZ_ASSERT(newSlot.IsFree());
+ moveEntry(this, slot.ToEntry(), newSlot.ToEntry());
+ newSlot.SetKeyHash(key);
+ }
+ });
+
+ free(oldEntryStore);
+ return true;
+}
+
+MOZ_ALWAYS_INLINE PLDHashNumber
+PLDHashTable::ComputeKeyHash(const void* aKey) const {
+ MOZ_ASSERT(mEntryStore.IsAllocated());
+
+ PLDHashNumber keyHash = mozilla::ScrambleHashCode(mOps->hashKey(aKey));
+
+ // Avoid 0 and 1 hash codes, they indicate free and removed entries.
+ if (keyHash < 2) {
+ keyHash -= 2;
+ }
+ keyHash &= ~kCollisionFlag;
+
+ return keyHash;
+}
+
+PLDHashEntryHdr* PLDHashTable::Search(const void* aKey) const {
+#ifdef MOZ_HASH_TABLE_CHECKS_ENABLED
+ AutoReadOp op(mChecker);
+#endif
+
+ if (!mEntryStore.IsAllocated()) {
+ return nullptr;
+ }
+
+ return SearchTable<ForSearchOrRemove>(
+ aKey, ComputeKeyHash(aKey),
+ [&](Slot& slot) -> PLDHashEntryHdr* { return slot.ToEntry(); },
+ [&]() -> PLDHashEntryHdr* { return nullptr; });
+}
+
+PLDHashEntryHdr* PLDHashTable::Add(const void* aKey,
+ const mozilla::fallible_t& aFallible) {
+ auto maybeEntryHandle = MakeEntryHandle(aKey, aFallible);
+ if (!maybeEntryHandle) {
+ return nullptr;
+ }
+ return maybeEntryHandle->OrInsert([&aKey, this](PLDHashEntryHdr* entry) {
+ if (mOps->initEntry) {
+ mOps->initEntry(entry, aKey);
+ }
+ });
+}
+
+PLDHashEntryHdr* PLDHashTable::Add(const void* aKey) {
+ return MakeEntryHandle(aKey).OrInsert([&aKey, this](PLDHashEntryHdr* entry) {
+ if (mOps->initEntry) {
+ mOps->initEntry(entry, aKey);
+ }
+ });
+}
+
+void PLDHashTable::Remove(const void* aKey) {
+#ifdef MOZ_HASH_TABLE_CHECKS_ENABLED
+ AutoWriteOp op(mChecker);
+#endif
+
+ if (!mEntryStore.IsAllocated()) {
+ return;
+ }
+
+ PLDHashNumber keyHash = ComputeKeyHash(aKey);
+ SearchTable<ForSearchOrRemove>(
+ aKey, keyHash,
+ [&](Slot& slot) {
+ RawRemove(slot);
+ ShrinkIfAppropriate();
+ },
+ [&]() {
+ // Do nothing.
+ });
+}
+
+void PLDHashTable::RemoveEntry(PLDHashEntryHdr* aEntry) {
+#ifdef MOZ_HASH_TABLE_CHECKS_ENABLED
+ AutoWriteOp op(mChecker);
+#endif
+
+ RawRemove(aEntry);
+ ShrinkIfAppropriate();
+}
+
+void PLDHashTable::RawRemove(PLDHashEntryHdr* aEntry) {
+ Slot slot(mEntryStore.SlotForPLDHashEntry(aEntry, Capacity(), mEntrySize));
+ RawRemove(slot);
+}
+
+void PLDHashTable::RawRemove(Slot& aSlot) {
+ // Unfortunately, we can only do weak checking here. That's because
+ // RawRemove() can be called legitimately while an Enumerate() call is
+ // active, which doesn't fit well into how Checker's mState variable works.
+ MOZ_ASSERT(mChecker.IsWritable());
+
+ MOZ_ASSERT(mEntryStore.IsAllocated());
+
+ MOZ_ASSERT(aSlot.IsLive());
+
+ // Load keyHash first in case clearEntry() goofs it.
+ PLDHashNumber keyHash = aSlot.KeyHash();
+ if (mOps->clearEntry) {
+ PLDHashEntryHdr* entry = aSlot.ToEntry();
+ mOps->clearEntry(this, entry);
+ }
+ if (keyHash & kCollisionFlag) {
+ aSlot.MarkRemoved();
+ mRemovedCount++;
+ } else {
+ aSlot.MarkFree();
+ }
+ mEntryCount--;
+}
+
+// Shrink or compress if a quarter or more of all entries are removed, or if the
+// table is underloaded according to the minimum alpha, and is not minimal-size
+// already.
+void PLDHashTable::ShrinkIfAppropriate() {
+ uint32_t capacity = Capacity();
+ if (mRemovedCount >= capacity >> 2 ||
+ (capacity > kMinCapacity && mEntryCount <= MinLoad(capacity))) {
+ uint32_t log2;
+ BestCapacity(mEntryCount, &capacity, &log2);
+
+ int32_t deltaLog2 = log2 - (kPLDHashNumberBits - mHashShift);
+ MOZ_ASSERT(deltaLog2 <= 0);
+
+ (void)ChangeTable(deltaLog2);
+ }
+}
+
+size_t PLDHashTable::ShallowSizeOfExcludingThis(
+ MallocSizeOf aMallocSizeOf) const {
+#ifdef MOZ_HASH_TABLE_CHECKS_ENABLED
+ AutoReadOp op(mChecker);
+#endif
+
+ return aMallocSizeOf(mEntryStore.Get());
+}
+
+size_t PLDHashTable::ShallowSizeOfIncludingThis(
+ MallocSizeOf aMallocSizeOf) const {
+ return aMallocSizeOf(this) + ShallowSizeOfExcludingThis(aMallocSizeOf);
+}
+
+mozilla::Maybe<PLDHashTable::EntryHandle> PLDHashTable::MakeEntryHandle(
+ const void* aKey, const mozilla::fallible_t&) {
+#ifdef MOZ_HASH_TABLE_CHECKS_ENABLED
+ mChecker.StartWriteOp();
+ auto endWriteOp = MakeScopeExit([&] { mChecker.EndWriteOp(); });
+#endif
+
+ // Allocate the entry storage if it hasn't already been allocated.
+ if (!mEntryStore.IsAllocated()) {
+ uint32_t nbytes;
+ // We already checked this in the constructor, so it must still be true.
+ MOZ_RELEASE_ASSERT(
+ SizeOfEntryStore(CapacityFromHashShift(), mEntrySize, &nbytes));
+ mEntryStore.Set((char*)calloc(1, nbytes), &mGeneration);
+ if (!mEntryStore.IsAllocated()) {
+ return Nothing();
+ }
+ }
+
+ // If alpha is >= .75, grow or compress the table. If aKey is already in the
+ // table, we may grow once more than necessary, but only if we are on the
+ // edge of being overloaded.
+ uint32_t capacity = Capacity();
+ if (mEntryCount + mRemovedCount >= MaxLoad(capacity)) {
+ // Compress if a quarter or more of all entries are removed.
+ int deltaLog2 = 1;
+ if (mRemovedCount >= capacity >> 2) {
+ deltaLog2 = 0;
+ }
+
+ // Grow or compress the table. If ChangeTable() fails, allow overloading up
+ // to the secondary max. Once we hit the secondary max, return null.
+ if (!ChangeTable(deltaLog2) &&
+ mEntryCount + mRemovedCount >= MaxLoadOnGrowthFailure(capacity)) {
+ return Nothing();
+ }
+ }
+
+ // Look for entry after possibly growing, so we don't have to add it,
+ // then skip it while growing the table and re-add it after.
+ PLDHashNumber keyHash = ComputeKeyHash(aKey);
+ Slot slot = SearchTable<ForAdd>(
+ aKey, keyHash, [](Slot& found) -> Slot { return found; },
+ []() -> Slot {
+ MOZ_CRASH("Nope");
+ return Slot(nullptr, nullptr);
+ });
+
+ // The `EntryHandle` will handle ending the write op when it is destroyed.
+#ifdef MOZ_HASH_TABLE_CHECKS_ENABLED
+ endWriteOp.release();
+#endif
+
+ return Some(EntryHandle{this, keyHash, slot});
+}
+
+PLDHashTable::EntryHandle PLDHashTable::MakeEntryHandle(const void* aKey) {
+ auto res = MakeEntryHandle(aKey, fallible);
+ if (!res) {
+ if (!mEntryStore.IsAllocated()) {
+ // We OOM'd while allocating the initial entry storage.
+ uint32_t nbytes;
+ (void)SizeOfEntryStore(CapacityFromHashShift(), mEntrySize, &nbytes);
+ NS_ABORT_OOM(nbytes);
+ } else {
+ // We failed to resize the existing entry storage, either due to OOM or
+ // because we exceeded the maximum table capacity or size; report it as
+ // an OOM. The multiplication by 2 gets us the size we tried to allocate,
+ // which is double the current size.
+ NS_ABORT_OOM(2 * EntrySize() * EntryCount());
+ }
+ }
+ return res.extract();
+}
+
+PLDHashTable::EntryHandle::EntryHandle(PLDHashTable* aTable,
+ PLDHashNumber aKeyHash, Slot aSlot)
+ : mTable(aTable), mKeyHash(aKeyHash), mSlot(aSlot) {}
+
+PLDHashTable::EntryHandle::EntryHandle(EntryHandle&& aOther) noexcept
+ : mTable(std::exchange(aOther.mTable, nullptr)),
+ mKeyHash(aOther.mKeyHash),
+ mSlot(aOther.mSlot) {}
+
+#ifdef MOZ_HASH_TABLE_CHECKS_ENABLED
+PLDHashTable::EntryHandle::~EntryHandle() {
+ if (!mTable) {
+ return;
+ }
+
+ mTable->mChecker.EndWriteOp();
+}
+#endif
+
+void PLDHashTable::EntryHandle::Remove() {
+ MOZ_ASSERT(HasEntry());
+
+ mTable->RawRemove(mSlot);
+}
+
+void PLDHashTable::EntryHandle::OrRemove() {
+ if (HasEntry()) {
+ Remove();
+ }
+}
+
+void PLDHashTable::EntryHandle::OccupySlot() {
+ MOZ_ASSERT(!HasEntry());
+
+ PLDHashNumber keyHash = mKeyHash;
+ if (mSlot.IsRemoved()) {
+ mTable->mRemovedCount--;
+ keyHash |= kCollisionFlag;
+ }
+ mSlot.SetKeyHash(keyHash);
+ mTable->mEntryCount++;
+}
+
+PLDHashTable::Iterator::Iterator(Iterator&& aOther)
+ : mTable(aOther.mTable),
+ mCurrent(aOther.mCurrent),
+ mNexts(aOther.mNexts),
+ mNextsLimit(aOther.mNextsLimit),
+ mHaveRemoved(aOther.mHaveRemoved),
+ mEntrySize(aOther.mEntrySize) {
+ // No need to change |mChecker| here.
+ aOther.mTable = nullptr;
+ // We don't really have the concept of a null slot, so leave mCurrent.
+ aOther.mNexts = 0;
+ aOther.mNextsLimit = 0;
+ aOther.mHaveRemoved = false;
+ aOther.mEntrySize = 0;
+}
+
+PLDHashTable::Iterator::Iterator(PLDHashTable* aTable)
+ : mTable(aTable),
+ mCurrent(mTable->mEntryStore.SlotForIndex(0, mTable->mEntrySize,
+ mTable->Capacity())),
+ mNexts(0),
+ mNextsLimit(mTable->EntryCount()),
+ mHaveRemoved(false),
+ mEntrySize(aTable->mEntrySize) {
+#ifdef MOZ_HASH_TABLE_CHECKS_ENABLED
+ mTable->mChecker.StartReadOp();
+#endif
+
+ if (ChaosMode::isActive(ChaosFeature::HashTableIteration) &&
+ mTable->Capacity() > 0) {
+ // Start iterating at a random entry. It would be even more chaotic to
+ // iterate in fully random order, but that's harder.
+ uint32_t capacity = mTable->CapacityFromHashShift();
+ uint32_t i = ChaosMode::randomUint32LessThan(capacity);
+ mCurrent =
+ mTable->mEntryStore.SlotForIndex(i, mTable->mEntrySize, capacity);
+ }
+
+ // Advance to the first live entry, if there is one.
+ if (!Done() && IsOnNonLiveEntry()) {
+ MoveToNextLiveEntry();
+ }
+}
+
+PLDHashTable::Iterator::Iterator(PLDHashTable* aTable, EndIteratorTag aTag)
+ : mTable(aTable),
+ mCurrent(mTable->mEntryStore.SlotForIndex(0, mTable->mEntrySize,
+ mTable->Capacity())),
+ mNexts(mTable->EntryCount()),
+ mNextsLimit(mTable->EntryCount()),
+ mHaveRemoved(false),
+ mEntrySize(aTable->mEntrySize) {
+#ifdef MOZ_HASH_TABLE_CHECKS_ENABLED
+ mTable->mChecker.StartReadOp();
+#endif
+
+ MOZ_ASSERT(Done());
+}
+
+PLDHashTable::Iterator::Iterator(const Iterator& aOther)
+ : mTable(aOther.mTable),
+ mCurrent(aOther.mCurrent),
+ mNexts(aOther.mNexts),
+ mNextsLimit(aOther.mNextsLimit),
+ mHaveRemoved(aOther.mHaveRemoved),
+ mEntrySize(aOther.mEntrySize) {
+ // TODO: Is this necessary?
+ MOZ_ASSERT(!mHaveRemoved);
+
+#ifdef MOZ_HASH_TABLE_CHECKS_ENABLED
+ mTable->mChecker.StartReadOp();
+#endif
+}
+
+PLDHashTable::Iterator::~Iterator() {
+ if (mTable) {
+ if (mHaveRemoved) {
+ mTable->ShrinkIfAppropriate();
+ }
+#ifdef MOZ_HASH_TABLE_CHECKS_ENABLED
+ mTable->mChecker.EndReadOp();
+#endif
+ }
+}
+
+MOZ_ALWAYS_INLINE bool PLDHashTable::Iterator::IsOnNonLiveEntry() const {
+ MOZ_ASSERT(!Done());
+ return !mCurrent.IsLive();
+}
+
+void PLDHashTable::Iterator::Next() {
+ MOZ_ASSERT(!Done());
+
+ mNexts++;
+
+ // Advance to the next live entry, if there is one.
+ if (!Done()) {
+ MoveToNextLiveEntry();
+ }
+}
+
+MOZ_ALWAYS_INLINE void PLDHashTable::Iterator::MoveToNextLiveEntry() {
+ // Chaos mode requires wraparound to cover all possible entries, so we can't
+ // simply move to the next live entry and stop when we hit the end of the
+ // entry store. But we don't want to introduce extra branches into our inner
+ // loop. So we are going to exploit the structure of the entry store in this
+ // method to implement an efficient inner loop.
+ //
+ // The idea is that since we are really only iterating through the stored
+ // hashes and because we know that there are a power-of-two number of
+ // hashes, we can use masking to implement the wraparound for us. This
+ // method does have the downside of needing to recalculate where the
+ // associated entry is once we've found it, but that seems OK.
+
+ // Our current slot and its associated hash.
+ Slot slot = mCurrent;
+ PLDHashNumber* p = slot.HashPtr();
+ const uint32_t capacity = mTable->CapacityFromHashShift();
+ const uint32_t mask = capacity - 1;
+ auto hashes = reinterpret_cast<PLDHashNumber*>(mTable->mEntryStore.Get());
+ uint32_t slotIndex = p - hashes;
+
+ do {
+ slotIndex = (slotIndex + 1) & mask;
+ } while (!Slot::IsLiveHash(hashes[slotIndex]));
+
+ // slotIndex now indicates where a live slot is. Rematerialize the entry
+ // and the slot.
+ mCurrent = mTable->mEntryStore.SlotForIndex(slotIndex, mEntrySize, capacity);
+}
+
+void PLDHashTable::Iterator::Remove() {
+ mTable->RawRemove(mCurrent);
+ mHaveRemoved = true;
+}