1 files changed, 801 insertions, 0 deletions
diff --git a/xpcom/glue/PLDHashTable.cpp b/xpcom/glue/PLDHashTable.cpp
new file mode 100644
index 000000000..6152e9000
--- /dev/null
+++ b/xpcom/glue/PLDHashTable.cpp
@@ -0,0 +1,801 @@
+/* -*- 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 "mozilla/HashFunctions.h"
+#include "mozilla/MathAlgorithms.h"
+#include "mozilla/OperatorNewExtensions.h"
+#include "nsAlgorithm.h"
+#include "mozilla/Likely.h"
+#include "mozilla/MemoryReporting.h"
+#include "mozilla/ChaosMode.h"
+
+using namespace mozilla;
+
+#ifdef DEBUG
+
+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 (PLDHashNumber)(ptrdiff_t)aKey >> 2;
+}
+
+/* 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)
+{
+  uint64_t nbytes64 = uint64_t(aCapacity) * uint64_t(aEntrySize);
+  *aNbytes = aCapacity * aEntrySize;
+  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)
+{
+  // 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 kHashBits - log2;
+}
+
+PLDHashTable::PLDHashTable(const PLDHashTableOps* aOps, uint32_t aEntrySize,
+                           uint32_t aLength)
+  : mOps(aOps)
+  , mHashShift(HashShift(aEntrySize, aLength))
+  , mEntrySize(aEntrySize)
+  , mEntryCount(0)
+  , mRemovedCount(0)
+  , mEntryStore()
+#ifdef DEBUG
+  , mChecker()
+#endif
+{
+}
+
+PLDHashTable&
+PLDHashTable::operator=(PLDHashTable&& aOther)
+{
+  if (this == &aOther) {
+    return *this;
+  }
+
+  // Destruct |this|.
+  this->~PLDHashTable();
+
+  // |mOps| and |mEntrySize| are const so we can't assign them. Instead, we
+  // require that they are equal. The justification for this is that 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);
+  MOZ_RELEASE_ASSERT(mEntrySize == aOther.mEntrySize);
+
+  // Move non-const pieces over.
+  mHashShift = Move(aOther.mHashShift);
+  mEntryCount = Move(aOther.mEntryCount);
+  mRemovedCount = Move(aOther.mRemovedCount);
+  mEntryStore = Move(aOther.mEntryStore);
+#ifdef DEBUG
+  mChecker = Move(aOther.mChecker);
+#endif
+
+  // Clear up |aOther| so its destruction will be a no-op.
+  {
+#ifdef DEBUG
+    AutoDestructorOp op(mChecker);
+#endif
+    aOther.mEntryStore.Set(nullptr);
+  }
+
+  return *this;
+}
+
+PLDHashNumber
+PLDHashTable::Hash1(PLDHashNumber aHash0)
+{
+  return aHash0 >> mHashShift;
+}
+
+// Double hashing needs the second hash code to be relatively prime to table
+// size, so we simply make hash2 odd.
+void
+PLDHashTable::Hash2(PLDHashNumber aHash,
+                    uint32_t& aHash2Out, uint32_t& aSizeMaskOut)
+{
+  uint32_t sizeLog2 = kHashBits - mHashShift;
+  aHash2Out = ((aHash << sizeLog2) >> mHashShift) | 1;
+  aSizeMaskOut = (PLDHashNumber(1) << sizeLog2) - 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::MatchEntryKeyhash(PLDHashEntryHdr* aEntry, PLDHashNumber aKeyHash)
+{
+  return (aEntry->mKeyHash & ~kCollisionFlag) == aKeyHash;
+}
+
+// Compute the address of the indexed entry in table.
+PLDHashEntryHdr*
+PLDHashTable::AddressEntry(uint32_t aIndex)
+{
+  return reinterpret_cast<PLDHashEntryHdr*>(
+    mEntryStore.Get() + aIndex * mEntrySize);
+}
+
+PLDHashTable::~PLDHashTable()
+{
+#ifdef DEBUG
+  AutoDestructorOp op(mChecker);
+#endif
+
+  if (!mEntryStore.Get()) {
+    return;
+  }
+
+  // Clear any remaining live entries.
+  char* entryAddr = mEntryStore.Get();
+  char* entryLimit = entryAddr + Capacity() * mEntrySize;
+  while (entryAddr < entryLimit) {
+    PLDHashEntryHdr* entry = (PLDHashEntryHdr*)entryAddr;
+    if (EntryIsLive(entry)) {
+      mOps->clearEntry(this, entry);
+    }
+    entryAddr += mEntrySize;
+  }
+
+  // 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.
+template <PLDHashTable::SearchReason Reason>
+PLDHashEntryHdr* NS_FASTCALL
+PLDHashTable::SearchTable(const void* aKey, PLDHashNumber aKeyHash)
+{
+  MOZ_ASSERT(mEntryStore.Get());
+  NS_ASSERTION(!(aKeyHash & kCollisionFlag),
+               "!(aKeyHash & kCollisionFlag)");
+
+  // Compute the primary hash address.
+  PLDHashNumber hash1 = Hash1(aKeyHash);
+  PLDHashEntryHdr* entry = AddressEntry(hash1);
+
+  // Miss: return space for a new entry.
+  if (EntryIsFree(entry)) {
+    return (Reason == ForAdd) ? entry : nullptr;
+  }
+
+  // Hit: return entry.
+  PLDHashMatchEntry matchEntry = mOps->matchEntry;
+  if (MatchEntryKeyhash(entry, aKeyHash) &&
+      matchEntry(entry, aKey)) {
+    return entry;
+  }
+
+  // Collision: double hash.
+  PLDHashNumber hash2;
+  uint32_t sizeMask;
+  Hash2(aKeyHash, hash2, sizeMask);
+
+  // Save the first removed entry pointer so Add() can recycle it. (Only used
+  // if Reason==ForAdd.)
+  PLDHashEntryHdr* firstRemoved = nullptr;
+
+  for (;;) {
+    if (Reason == ForAdd) {
+      if (MOZ_UNLIKELY(EntryIsRemoved(entry))) {
+        if (!firstRemoved) {
+          firstRemoved = entry;
+        }
+      } else {
+        entry->mKeyHash |= kCollisionFlag;
+      }
+    }
+
+    hash1 -= hash2;
+    hash1 &= sizeMask;
+
+    entry = AddressEntry(hash1);
+    if (EntryIsFree(entry)) {
+      return (Reason == ForAdd) ? (firstRemoved ? firstRemoved : entry)
+                                : nullptr;
+    }
+
+    if (MatchEntryKeyhash(entry, aKeyHash) &&
+        matchEntry(entry, aKey)) {
+      return entry;
+    }
+  }
+
+  // NOTREACHED
+  return nullptr;
+}
+
+// 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 PLDHashEntryHdr*
+PLDHashTable::FindFreeEntry(PLDHashNumber aKeyHash)
+{
+  MOZ_ASSERT(mEntryStore.Get());
+  NS_ASSERTION(!(aKeyHash & kCollisionFlag),
+               "!(aKeyHash & kCollisionFlag)");
+
+  // Compute the primary hash address.
+  PLDHashNumber hash1 = Hash1(aKeyHash);
+  PLDHashEntryHdr* entry = AddressEntry(hash1);
+
+  // Miss: return space for a new entry.
+  if (EntryIsFree(entry)) {
+    return entry;
+  }
+
+  // Collision: double hash.
+  PLDHashNumber hash2;
+  uint32_t sizeMask;
+  Hash2(aKeyHash, hash2, sizeMask);
+
+  for (;;) {
+    NS_ASSERTION(!EntryIsRemoved(entry),
+                 "!EntryIsRemoved(entry)");
+    entry->mKeyHash |= kCollisionFlag;
+
+    hash1 -= hash2;
+    hash1 &= sizeMask;
+
+    entry = AddressEntry(hash1);
+    if (EntryIsFree(entry)) {
+      return entry;
+    }
+  }
+
+  // NOTREACHED
+}
+
+bool
+PLDHashTable::ChangeTable(int32_t aDeltaLog2)
+{
+  MOZ_ASSERT(mEntryStore.Get());
+
+  // Look, but don't touch, until we succeed in getting new entry store.
+  int32_t oldLog2 = kHashBits - 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*)malloc(nbytes);
+  if (!newEntryStore) {
+    return false;
+  }
+
+  // We can't fail from here on, so update table parameters.
+  mHashShift = kHashBits - newLog2;
+  mRemovedCount = 0;
+
+  // Assign the new entry store to table.
+  memset(newEntryStore, 0, nbytes);
+  char* oldEntryStore;
+  char* oldEntryAddr;
+  oldEntryAddr = oldEntryStore = mEntryStore.Get();
+  mEntryStore.Set(newEntryStore);
+  PLDHashMoveEntry moveEntry = mOps->moveEntry;
+
+  // Copy only live entries, leaving removed ones behind.
+  uint32_t oldCapacity = 1u << oldLog2;
+  for (uint32_t i = 0; i < oldCapacity; ++i) {
+    PLDHashEntryHdr* oldEntry = (PLDHashEntryHdr*)oldEntryAddr;
+    if (EntryIsLive(oldEntry)) {
+      oldEntry->mKeyHash &= ~kCollisionFlag;
+      PLDHashEntryHdr* newEntry = FindFreeEntry(oldEntry->mKeyHash);
+      NS_ASSERTION(EntryIsFree(newEntry), "EntryIsFree(newEntry)");
+      moveEntry(this, oldEntry, newEntry);
+      newEntry->mKeyHash = oldEntry->mKeyHash;
+    }
+    oldEntryAddr += mEntrySize;
+  }
+
+  free(oldEntryStore);
+  return true;
+}
+
+MOZ_ALWAYS_INLINE PLDHashNumber
+PLDHashTable::ComputeKeyHash(const void* aKey)
+{
+  MOZ_ASSERT(mEntryStore.Get());
+
+  PLDHashNumber keyHash = mOps->hashKey(aKey);
+  keyHash *= kGoldenRatio;
+
+  // 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)
+{
+#ifdef DEBUG
+  AutoReadOp op(mChecker);
+#endif
+
+  PLDHashEntryHdr* entry = mEntryStore.Get()
+                         ? SearchTable<ForSearchOrRemove>(aKey,
+                                                          ComputeKeyHash(aKey))
+                         : nullptr;
+  return entry;
+}
+
+PLDHashEntryHdr*
+PLDHashTable::Add(const void* aKey, const mozilla::fallible_t&)
+{
+#ifdef DEBUG
+  AutoWriteOp op(mChecker);
+#endif
+
+  // Allocate the entry storage if it hasn't already been allocated.
+  if (!mEntryStore.Get()) {
+    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*)malloc(nbytes));
+    if (!mEntryStore.Get()) {
+      return nullptr;
+    }
+    memset(mEntryStore.Get(), 0, nbytes);
+  }
+
+  // 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;
+    if (mRemovedCount >= capacity >> 2) {
+      deltaLog2 = 0;
+    } else {
+      deltaLog2 = 1;
+    }
+
+    // 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 nullptr;
+    }
+  }
+
+  // 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);
+  PLDHashEntryHdr* entry = SearchTable<ForAdd>(aKey, keyHash);
+  if (!EntryIsLive(entry)) {
+    // Initialize the entry, indicating that it's no longer free.
+    if (EntryIsRemoved(entry)) {
+      mRemovedCount--;
+      keyHash |= kCollisionFlag;
+    }
+    if (mOps->initEntry) {
+      mOps->initEntry(entry, aKey);
+    }
+    entry->mKeyHash = keyHash;
+    mEntryCount++;
+  }
+
+  return entry;
+}
+
+PLDHashEntryHdr*
+PLDHashTable::Add(const void* aKey)
+{
+  PLDHashEntryHdr* entry = Add(aKey, fallible);
+  if (!entry) {
+    if (!mEntryStore.Get()) {
+      // 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 entry;
+}
+
+void
+PLDHashTable::Remove(const void* aKey)
+{
+#ifdef DEBUG
+  AutoWriteOp op(mChecker);
+#endif
+
+  PLDHashEntryHdr* entry = mEntryStore.Get()
+                         ? SearchTable<ForSearchOrRemove>(aKey,
+                                                          ComputeKeyHash(aKey))
+                         : nullptr;
+  if (entry) {
+    RawRemove(entry);
+    ShrinkIfAppropriate();
+  }
+}
+
+void
+PLDHashTable::RemoveEntry(PLDHashEntryHdr* aEntry)
+{
+#ifdef DEBUG
+  AutoWriteOp op(mChecker);
+#endif
+
+  RawRemove(aEntry);
+  ShrinkIfAppropriate();
+}
+
+void
+PLDHashTable::RawRemove(PLDHashEntryHdr* aEntry)
+{
+  // 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.Get());
+
+  MOZ_ASSERT(EntryIsLive(aEntry), "EntryIsLive(aEntry)");
+
+  // Load keyHash first in case clearEntry() goofs it.
+  PLDHashNumber keyHash = aEntry->mKeyHash;
+  mOps->clearEntry(this, aEntry);
+  if (keyHash & kCollisionFlag) {
+    MarkEntryRemoved(aEntry);
+    mRemovedCount++;
+  } else {
+    MarkEntryFree(aEntry);
+  }
+  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 - (kHashBits - mHashShift);
+    MOZ_ASSERT(deltaLog2 <= 0);
+
+    (void) ChangeTable(deltaLog2);
+  }
+}
+
+size_t
+PLDHashTable::ShallowSizeOfExcludingThis(MallocSizeOf aMallocSizeOf) const
+{
+#ifdef DEBUG
+  AutoReadOp op(mChecker);
+#endif
+
+  return aMallocSizeOf(mEntryStore.Get());
+}
+
+size_t
+PLDHashTable::ShallowSizeOfIncludingThis(MallocSizeOf aMallocSizeOf) const
+{
+  return aMallocSizeOf(this) + ShallowSizeOfExcludingThis(aMallocSizeOf);
+}
+
+PLDHashTable::Iterator::Iterator(Iterator&& aOther)
+  : mTable(aOther.mTable)
+  , mStart(aOther.mStart)
+  , mLimit(aOther.mLimit)
+  , mCurrent(aOther.mCurrent)
+  , mNexts(aOther.mNexts)
+  , mNextsLimit(aOther.mNextsLimit)
+  , mHaveRemoved(aOther.mHaveRemoved)
+{
+  // No need to change |mChecker| here.
+  aOther.mTable = nullptr;
+  aOther.mStart = nullptr;
+  aOther.mLimit = nullptr;
+  aOther.mCurrent = nullptr;
+  aOther.mNexts = 0;
+  aOther.mNextsLimit = 0;
+  aOther.mHaveRemoved = false;
+}
+
+PLDHashTable::Iterator::Iterator(PLDHashTable* aTable)
+  : mTable(aTable)
+  , mStart(mTable->mEntryStore.Get())
+  , mLimit(mTable->mEntryStore.Get() + mTable->Capacity() * mTable->mEntrySize)
+  , mCurrent(mTable->mEntryStore.Get())
+  , mNexts(0)
+  , mNextsLimit(mTable->EntryCount())
+  , mHaveRemoved(false)
+{
+#ifdef DEBUG
+  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.
+    mCurrent += ChaosMode::randomUint32LessThan(mTable->Capacity()) *
+                mTable->mEntrySize;
+  }
+
+  // Advance to the first live entry, if there is one.
+  if (!Done()) {
+    while (IsOnNonLiveEntry()) {
+      MoveToNextEntry();
+    }
+  }
+}
+
+PLDHashTable::Iterator::~Iterator()
+{
+  if (mTable) {
+    if (mHaveRemoved) {
+      mTable->ShrinkIfAppropriate();
+    }
+#ifdef DEBUG
+    mTable->mChecker.EndReadOp();
+#endif
+  }
+}
+
+MOZ_ALWAYS_INLINE bool
+PLDHashTable::Iterator::IsOnNonLiveEntry() const
+{
+  MOZ_ASSERT(!Done());
+  return !EntryIsLive(reinterpret_cast<PLDHashEntryHdr*>(mCurrent));
+}
+
+MOZ_ALWAYS_INLINE void
+PLDHashTable::Iterator::MoveToNextEntry()
+{
+  mCurrent += mTable->mEntrySize;
+  if (mCurrent == mLimit) {
+    mCurrent = mStart;  // Wrap-around. Possible due to Chaos Mode.
+  }
+}
+
+void
+PLDHashTable::Iterator::Next()
+{
+  MOZ_ASSERT(!Done());
+
+  mNexts++;
+
+  // Advance to the next live entry, if there is one.
+  if (!Done()) {
+    do {
+      MoveToNextEntry();
+    } while (IsOnNonLiveEntry());
+  }
+}
+
+void
+PLDHashTable::Iterator::Remove()
+{
+  // This cast is needed for the same reason as the one in the destructor.
+  mTable->RawRemove(Get());
+  mHaveRemoved = true;
+}
+
+#ifdef DEBUG
+void
+PLDHashTable::MarkImmutable()
+{
+  mChecker.SetNonWritable();
+}
+#endif