Adding upstream version 124.0.1.upstream/124.0.1

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 807 insertions, 0 deletions

diff --git a/xpcom/ds/PLDHashTable.h b/xpcom/ds/PLDHashTable.h
new file mode 100644
index 0000000000..f1d741791c
--- /dev/null
+++ b/xpcom/ds/PLDHashTable.h
@@ -0,0 +1,807 @@
+/* -*- 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/. */
+
+// See the comment at the top of mfbt/HashTable.h for a comparison between
+// PLDHashTable and mozilla::HashTable.
+
+#ifndef PLDHashTable_h
+#define PLDHashTable_h
+
+#include <utility>
+
+#include "mozilla/Assertions.h"
+#include "mozilla/Atomics.h"
+#include "mozilla/HashFunctions.h"
+#include "mozilla/Maybe.h"
+#include "mozilla/MemoryReporting.h"
+#include "mozilla/fallible.h"
+#include "nscore.h"
+
+using PLDHashNumber = mozilla::HashNumber;
+static const uint32_t kPLDHashNumberBits = mozilla::kHashNumberBits;
+
+#if defined(DEBUG) || defined(FUZZING)
+#  define MOZ_HASH_TABLE_CHECKS_ENABLED 1
+#endif
+
+class PLDHashTable;
+struct PLDHashTableOps;
+
+// Table entry header structure.
+//
+// In order to allow in-line allocation of key and value, we do not declare
+// either here. Instead, the API uses const void *key as a formal parameter.
+// The key need not be stored in the entry; it may be part of the value, but
+// need not be stored at all.
+//
+// Callback types are defined below and grouped into the PLDHashTableOps
+// structure, for single static initialization per hash table sub-type.
+//
+// Each hash table sub-type should make its entry type a subclass of
+// PLDHashEntryHdr. PLDHashEntryHdr is merely a common superclass to present a
+// uniform interface to PLDHashTable clients. The zero-sized base class
+// optimization, employed by all of our supported C++ compilers, will ensure
+// that this abstraction does not make objects needlessly larger.
+struct PLDHashEntryHdr {
+  PLDHashEntryHdr() = default;
+  PLDHashEntryHdr(const PLDHashEntryHdr&) = delete;
+  PLDHashEntryHdr& operator=(const PLDHashEntryHdr&) = delete;
+  PLDHashEntryHdr(PLDHashEntryHdr&&) = default;
+  PLDHashEntryHdr& operator=(PLDHashEntryHdr&&) = default;
+
+ private:
+  friend class PLDHashTable;
+};
+
+#ifdef MOZ_HASH_TABLE_CHECKS_ENABLED
+
+// This class does three kinds of checking:
+//
+// - that calls to one of |mOps| or to an enumerator do not cause re-entry into
+//   the table in an unsafe way;
+//
+// - that multiple threads do not access the table in an unsafe way;
+//
+// - that a table marked as immutable is not modified.
+//
+// "Safe" here means that multiple concurrent read operations are ok, but a
+// write operation (i.e. one that can cause the entry storage to be reallocated
+// or destroyed) cannot safely run concurrently with another read or write
+// operation. This meaning of "safe" is only partial; for example, it does not
+// cover whether a single entry in the table is modified by two separate
+// threads. (Doing such checking would be much harder.)
+//
+// It does this with two variables:
+//
+// - mState, which embodies a tri-stage tagged union with the following
+//   variants:
+//   - Idle
+//   - Read(n), where 'n' is the number of concurrent read operations
+//   - Write
+//
+// - mIsWritable, which indicates if the table is mutable.
+//
+class Checker {
+ public:
+  constexpr Checker() : mState(kIdle), mIsWritable(true) {}
+
+  Checker& operator=(Checker&& aOther) {
+    // Atomic<> doesn't have an |operator=(Atomic<>&&)|.
+    mState = uint32_t(aOther.mState);
+    mIsWritable = bool(aOther.mIsWritable);
+
+    aOther.mState = kIdle;
+    // XXX Shouldn't we set mIsWritable to true here for consistency?
+
+    return *this;
+  }
+
+  static bool IsIdle(uint32_t aState) { return aState == kIdle; }
+  static bool IsRead(uint32_t aState) {
+    return kRead1 <= aState && aState <= kReadMax;
+  }
+  static bool IsRead1(uint32_t aState) { return aState == kRead1; }
+  static bool IsWrite(uint32_t aState) { return aState == kWrite; }
+
+  bool IsIdle() const { return mState == kIdle; }
+
+  bool IsWritable() const { return mIsWritable; }
+
+  void SetNonWritable() { mIsWritable = false; }
+
+  // NOTE: the obvious way to implement these functions is to (a) check
+  // |mState| is reasonable, and then (b) update |mState|. But the lack of
+  // atomicity in such an implementation can cause problems if we get unlucky
+  // thread interleaving between (a) and (b).
+  //
+  // So instead for |mState| we are careful to (a) first get |mState|'s old
+  // value and assign it a new value in single atomic operation, and only then
+  // (b) check the old value was reasonable. This ensures we don't have
+  // interleaving problems.
+  //
+  // For |mIsWritable| we don't need to be as careful because it can only in
+  // transition in one direction (from writable to non-writable).
+
+  void StartReadOp() {
+    uint32_t oldState = mState++;  // this is an atomic increment
+    MOZ_RELEASE_ASSERT(IsIdle(oldState) || IsRead(oldState));
+    MOZ_RELEASE_ASSERT(oldState < kReadMax);  // check for overflow
+  }
+
+  void EndReadOp() {
+    uint32_t oldState = mState--;  // this is an atomic decrement
+    MOZ_RELEASE_ASSERT(IsRead(oldState));
+  }
+
+  void StartWriteOp() {
+    MOZ_RELEASE_ASSERT(IsWritable());
+    uint32_t oldState = mState.exchange(kWrite);
+    MOZ_RELEASE_ASSERT(IsIdle(oldState));
+  }
+
+  void EndWriteOp() {
+    // Check again that the table is writable, in case it was marked as
+    // non-writable just after the IsWritable() assertion in StartWriteOp()
+    // occurred.
+    MOZ_RELEASE_ASSERT(IsWritable());
+    uint32_t oldState = mState.exchange(kIdle);
+    MOZ_RELEASE_ASSERT(IsWrite(oldState));
+  }
+
+  void StartIteratorRemovalOp() {
+    // When doing removals at the end of iteration, we go from Read1 state to
+    // Write and then back.
+    MOZ_RELEASE_ASSERT(IsWritable());
+    uint32_t oldState = mState.exchange(kWrite);
+    MOZ_RELEASE_ASSERT(IsRead1(oldState));
+  }
+
+  void EndIteratorRemovalOp() {
+    // Check again that the table is writable, in case it was marked as
+    // non-writable just after the IsWritable() assertion in
+    // StartIteratorRemovalOp() occurred.
+    MOZ_RELEASE_ASSERT(IsWritable());
+    uint32_t oldState = mState.exchange(kRead1);
+    MOZ_RELEASE_ASSERT(IsWrite(oldState));
+  }
+
+  void StartDestructorOp() {
+    // A destructor op is like a write, but the table doesn't need to be
+    // writable.
+    uint32_t oldState = mState.exchange(kWrite);
+    MOZ_RELEASE_ASSERT(IsIdle(oldState));
+  }
+
+  void EndDestructorOp() {
+    uint32_t oldState = mState.exchange(kIdle);
+    MOZ_RELEASE_ASSERT(IsWrite(oldState));
+  }
+
+ private:
+  // Things of note about the representation of |mState|.
+  // - The values between kRead1..kReadMax represent valid Read(n) values.
+  // - kIdle and kRead1 are deliberately chosen so that incrementing the -
+  //   former gives the latter.
+  // - 9999 concurrent readers should be enough for anybody.
+  static const uint32_t kIdle = 0;
+  static const uint32_t kRead1 = 1;
+  static const uint32_t kReadMax = 9999;
+  static const uint32_t kWrite = 10000;
+
+  mozilla::Atomic<uint32_t, mozilla::SequentiallyConsistent> mState;
+  mozilla::Atomic<bool, mozilla::SequentiallyConsistent> mIsWritable;
+};
+#endif
+
+// A PLDHashTable may be allocated on the stack or within another structure or
+// class. No entry storage is allocated until the first element is added. This
+// means that empty hash tables are cheap, which is good because they are
+// common.
+//
+// There used to be a long, math-heavy comment here about the merits of
+// double hashing vs. chaining; it was removed in bug 1058335. In short, double
+// hashing is more space-efficient unless the element size gets large (in which
+// case you should keep using double hashing but switch to using pointer
+// elements). Also, with double hashing, you can't safely hold an entry pointer
+// and use it after an add or remove operation, unless you sample Generation()
+// before adding or removing, and compare the sample after, dereferencing the
+// entry pointer only if Generation() has not changed.
+class PLDHashTable {
+ private:
+  // A slot represents a cached hash value and its associated entry stored in
+  // the hash table. The hash value and the entry are not stored contiguously.
+  struct Slot {
+    Slot(PLDHashEntryHdr* aEntry, PLDHashNumber* aKeyHash)
+        : mEntry(aEntry), mKeyHash(aKeyHash) {}
+
+    Slot(const Slot&) = default;
+    Slot(Slot&& aOther) = default;
+
+    Slot& operator=(Slot&& aOther) = default;
+
+    bool operator==(const Slot& aOther) const {
+      return mEntry == aOther.mEntry;
+    }
+
+    PLDHashNumber KeyHash() const { return *HashPtr(); }
+    void SetKeyHash(PLDHashNumber aHash) { *HashPtr() = aHash; }
+
+    PLDHashEntryHdr* ToEntry() const { return mEntry; }
+
+    bool IsFree() const { return KeyHash() == 0; }
+    bool IsRemoved() const { return KeyHash() == 1; }
+    bool IsLive() const { return IsLiveHash(KeyHash()); }
+    static bool IsLiveHash(uint32_t aHash) { return aHash >= 2; }
+
+    void MarkFree() { *HashPtr() = 0; }
+    void MarkRemoved() { *HashPtr() = 1; }
+    void MarkColliding() { *HashPtr() |= kCollisionFlag; }
+
+    void Next(uint32_t aEntrySize) {
+      char* p = reinterpret_cast<char*>(mEntry);
+      p += aEntrySize;
+      mEntry = reinterpret_cast<PLDHashEntryHdr*>(p);
+      mKeyHash++;
+    }
+    PLDHashNumber* HashPtr() const { return mKeyHash; }
+
+   private:
+    PLDHashEntryHdr* mEntry;
+    PLDHashNumber* mKeyHash;
+  };
+
+  // This class maintains the invariant that every time the entry store is
+  // changed, the generation is updated.
+  //
+  // The data layout separates the cached hashes of entries and the entries
+  // themselves to save space. We could store the entries thusly:
+  //
+  // +--------+--------+---------+
+  // | entry0 | entry1 | ...     |
+  // +--------+--------+---------+
+  //
+  // where the entries themselves contain the cached hash stored as their
+  // first member. PLDHashTable did this for a long time, with entries looking
+  // like:
+  //
+  // class PLDHashEntryHdr
+  // {
+  //   PLDHashNumber mKeyHash;
+  // };
+  //
+  // class MyEntry : public PLDHashEntryHdr
+  // {
+  //   ...
+  // };
+  //
+  // The problem with this setup is that, depending on the layout of
+  // `MyEntry`, there may be platform ABI-mandated padding between `mKeyHash`
+  // and the first member of `MyEntry`. This ABI-mandated padding is wasted
+  // space, and was surprisingly common, e.g. when MyEntry contained a single
+  // pointer on 64-bit platforms.
+  //
+  // As previously alluded to, the current setup stores things thusly:
+  //
+  // +-------+-------+-------+-------+--------+--------+---------+
+  // | hash0 | hash1 | ..... | hashN | entry0 | entry1 | ...     |
+  // +-------+-------+-------+-------+--------+--------+---------+
+  //
+  // which contains no wasted space between the hashes themselves, and no
+  // wasted space between the entries themselves. malloc is guaranteed to
+  // return blocks of memory with at least word alignment on all of our major
+  // platforms. PLDHashTable mandates that the size of the hash table is
+  // always a power of two, so the alignment of the memory containing the
+  // first entry is always at least the alignment of the entire entry store.
+  // That means the alignment of `entry0` should be its natural alignment.
+  // Entries may have problems if they contain over-aligned members such as
+  // SIMD vector types, but this has not been a problem in practice.
+  //
+  // Note: It would be natural to store the generation within this class, but
+  // we can't do that without bloating sizeof(PLDHashTable) on 64-bit machines.
+  // So instead we store it outside this class, and Set() takes a pointer to it
+  // and ensures it is updated as necessary.
+  class EntryStore {
+   private:
+    char* mEntryStore;
+
+    static char* Entries(char* aStore, uint32_t aCapacity) {
+      return aStore + aCapacity * sizeof(PLDHashNumber);
+    }
+
+    char* Entries(uint32_t aCapacity) const {
+      return Entries(Get(), aCapacity);
+    }
+
+   public:
+    EntryStore() : mEntryStore(nullptr) {}
+
+    ~EntryStore() {
+      free(mEntryStore);
+      mEntryStore = nullptr;
+    }
+
+    char* Get() const { return mEntryStore; }
+    bool IsAllocated() const { return !!mEntryStore; }
+
+    Slot SlotForIndex(uint32_t aIndex, uint32_t aEntrySize,
+                      uint32_t aCapacity) const {
+      char* entries = Entries(aCapacity);
+      auto entry =
+          reinterpret_cast<PLDHashEntryHdr*>(entries + aIndex * aEntrySize);
+      auto hashes = reinterpret_cast<PLDHashNumber*>(Get());
+      return Slot(entry, &hashes[aIndex]);
+    }
+
+    Slot SlotForPLDHashEntry(PLDHashEntryHdr* aEntry, uint32_t aCapacity,
+                             uint32_t aEntrySize) {
+      char* entries = Entries(aCapacity);
+      char* entry = reinterpret_cast<char*>(aEntry);
+      uint32_t entryOffset = entry - entries;
+      uint32_t slotIndex = entryOffset / aEntrySize;
+      return SlotForIndex(slotIndex, aEntrySize, aCapacity);
+    }
+
+    template <typename F>
+    void ForEachSlot(uint32_t aCapacity, uint32_t aEntrySize, F&& aFunc) {
+      ForEachSlot(Get(), aCapacity, aEntrySize, std::move(aFunc));
+    }
+
+    template <typename F>
+    static void ForEachSlot(char* aStore, uint32_t aCapacity,
+                            uint32_t aEntrySize, F&& aFunc) {
+      char* entries = Entries(aStore, aCapacity);
+      Slot slot(reinterpret_cast<PLDHashEntryHdr*>(entries),
+                reinterpret_cast<PLDHashNumber*>(aStore));
+      for (size_t i = 0; i < aCapacity; ++i) {
+        aFunc(slot);
+        slot.Next(aEntrySize);
+      }
+    }
+
+    void Set(char* aEntryStore, uint16_t* aGeneration) {
+      mEntryStore = aEntryStore;
+      *aGeneration += 1;
+    }
+  };
+
+  // These fields are packed carefully. On 32-bit platforms,
+  // sizeof(PLDHashTable) is 20. On 64-bit platforms, sizeof(PLDHashTable) is
+  // 32; 28 bytes of data followed by 4 bytes of padding for alignment.
+  const PLDHashTableOps* const mOps;  // Virtual operations; see below.
+  EntryStore mEntryStore;             // (Lazy) entry storage and generation.
+  uint16_t mGeneration;               // The storage generation.
+  uint8_t mHashShift;                 // Multiplicative hash shift.
+  const uint8_t mEntrySize;           // Number of bytes in an entry.
+  uint32_t mEntryCount;               // Number of entries in table.
+  uint32_t mRemovedCount;             // Removed entry sentinels in table.
+
+#ifdef MOZ_HASH_TABLE_CHECKS_ENABLED
+  mutable Checker mChecker;
+#endif
+
+ public:
+  // Table capacity limit; do not exceed. The max capacity used to be 1<<23 but
+  // that occasionally that wasn't enough. Making it much bigger than 1<<26
+  // probably isn't worthwhile -- tables that big are kind of ridiculous.
+  // Also, the growth operation will (deliberately) fail if |capacity *
+  // mEntrySize| overflows a uint32_t, and mEntrySize is always at least 8
+  // bytes.
+  static const uint32_t kMaxCapacity = ((uint32_t)1 << 26);
+
+  static const uint32_t kMinCapacity = 8;
+
+  // Making this half of kMaxCapacity ensures it'll fit. Nobody should need an
+  // initial length anywhere nearly this large, anyway.
+  static const uint32_t kMaxInitialLength = kMaxCapacity / 2;
+
+  // This gives a default initial capacity of 8.
+  static const uint32_t kDefaultInitialLength = 4;
+
+  // Initialize the table with |aOps| and |aEntrySize|. The table's initial
+  // capacity is chosen such that |aLength| elements can be inserted without
+  // rehashing; if |aLength| is a power-of-two, this capacity will be
+  // |2*length|. However, because entry storage is allocated lazily, this
+  // initial capacity won't be relevant until the first element is added; prior
+  // to that the capacity will be zero.
+  //
+  // This will crash if |aEntrySize| and/or |aLength| are too large.
+  PLDHashTable(const PLDHashTableOps* aOps, uint32_t aEntrySize,
+               uint32_t aLength = kDefaultInitialLength);
+
+  PLDHashTable(PLDHashTable&& aOther)
+      // Initialize fields which are checked by the move assignment operator
+      // and the destructor (which the move assignment operator calls).
+      : mOps(nullptr), mGeneration(0), mEntrySize(0) {
+    *this = std::move(aOther);
+  }
+
+  PLDHashTable& operator=(PLDHashTable&& aOther);
+
+  ~PLDHashTable();
+
+  // This should be used rarely.
+  const PLDHashTableOps* Ops() const { return mOps; }
+
+  // Size in entries (gross, not net of free and removed sentinels) for table.
+  // This can be zero if no elements have been added yet, in which case the
+  // entry storage will not have yet been allocated.
+  uint32_t Capacity() const {
+    return mEntryStore.IsAllocated() ? CapacityFromHashShift() : 0;
+  }
+
+  uint32_t EntrySize() const { return mEntrySize; }
+  uint32_t EntryCount() const { return mEntryCount; }
+  uint32_t Generation() const { return mGeneration; }
+
+  // To search for a |key| in |table|, call:
+  //
+  //   entry = table.Search(key);
+  //
+  // If |entry| is non-null, |key| was found. If |entry| is null, key was not
+  // found.
+  PLDHashEntryHdr* Search(const void* aKey) const;
+
+  // To add an entry identified by |key| to table, call:
+  //
+  //   entry = table.Add(key, mozilla::fallible);
+  //
+  // If |entry| is null upon return, then the table is severely overloaded and
+  // memory can't be allocated for entry storage.
+  //
+  // Otherwise, if the initEntry hook was provided, |entry| will be
+  // initialized.  If the initEntry hook was not provided, the caller
+  // should initialize |entry| as appropriate.
+  PLDHashEntryHdr* Add(const void* aKey, const mozilla::fallible_t&);
+
+  // This is like the other Add() function, but infallible, and so never
+  // returns null.
+  PLDHashEntryHdr* Add(const void* aKey);
+
+  // To remove an entry identified by |key| from table, call:
+  //
+  //   table.Remove(key);
+  //
+  // If |key|'s entry is found, it is cleared (via table->mOps->clearEntry).
+  // The table's capacity may be reduced afterwards.
+  void Remove(const void* aKey);
+
+  // To remove an entry found by a prior search, call:
+  //
+  //   table.RemoveEntry(entry);
+  //
+  // The entry, which must be present and in use, is cleared (via
+  // table->mOps->clearEntry). The table's capacity may be reduced afterwards.
+  void RemoveEntry(PLDHashEntryHdr* aEntry);
+
+  // Remove an entry already accessed via Search() or Add().
+  //
+  // NB: this is a "raw" or low-level method. It does not shrink the table if
+  // it is underloaded. Don't use it unless necessary and you know what you are
+  // doing, and if so, please explain in a comment why it is necessary instead
+  // of RemoveEntry().
+  void RawRemove(PLDHashEntryHdr* aEntry);
+
+  // This function is equivalent to
+  // ClearAndPrepareForLength(kDefaultInitialLength).
+  void Clear();
+
+  // This function clears the table's contents and frees its entry storage,
+  // leaving it in a empty state ready to be used again. Afterwards, when the
+  // first element is added the entry storage that gets allocated will have a
+  // capacity large enough to fit |aLength| elements without rehashing.
+  //
+  // It's conceptually the same as calling the destructor and then re-calling
+  // the constructor with the original |aOps| and |aEntrySize| arguments, and
+  // a new |aLength| argument.
+  void ClearAndPrepareForLength(uint32_t aLength);
+
+  // Measure the size of the table's entry storage. If the entries contain
+  // pointers to other heap blocks, you have to iterate over the table and
+  // measure those separately; hence the "Shallow" prefix.
+  size_t ShallowSizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf) const;
+
+  // Like ShallowSizeOfExcludingThis(), but includes sizeof(*this).
+  size_t ShallowSizeOfIncludingThis(mozilla::MallocSizeOf aMallocSizeOf) const;
+
+  // Mark a table as immutable for the remainder of its lifetime. This
+  // changes the implementation from asserting one set of invariants to
+  // asserting a different set.
+  void MarkImmutable() {
+#ifdef MOZ_HASH_TABLE_CHECKS_ENABLED
+    mChecker.SetNonWritable();
+#endif
+  }
+
+  // If you use PLDHashEntryStub or a subclass of it as your entry struct, and
+  // if your entries move via memcpy and clear via memset(0), you can use these
+  // stub operations.
+  static const PLDHashTableOps* StubOps();
+
+  // The individual stub operations in StubOps().
+  static PLDHashNumber HashVoidPtrKeyStub(const void* aKey);
+  static bool MatchEntryStub(const PLDHashEntryHdr* aEntry, const void* aKey);
+  static void MoveEntryStub(PLDHashTable* aTable, const PLDHashEntryHdr* aFrom,
+                            PLDHashEntryHdr* aTo);
+  static void ClearEntryStub(PLDHashTable* aTable, PLDHashEntryHdr* aEntry);
+
+  // Hash/match operations for tables holding C strings.
+  static PLDHashNumber HashStringKey(const void* aKey);
+  static bool MatchStringKey(const PLDHashEntryHdr* aEntry, const void* aKey);
+
+  class EntryHandle {
+   public:
+    EntryHandle(EntryHandle&& aOther) noexcept;
+#ifdef MOZ_HASH_TABLE_CHECKS_ENABLED
+    ~EntryHandle();
+#endif
+
+    EntryHandle(const EntryHandle&) = delete;
+    EntryHandle& operator=(const EntryHandle&) = delete;
+    EntryHandle& operator=(EntryHandle&& aOther) = delete;
+
+    // Is this slot currently occupied?
+    bool HasEntry() const { return mSlot.IsLive(); }
+
+    explicit operator bool() const { return HasEntry(); }
+
+    // Get the entry stored in this slot. May not be called unless the slot is
+    // currently occupied.
+    PLDHashEntryHdr* Entry() {
+      MOZ_ASSERT(HasEntry());
+      return mSlot.ToEntry();
+    }
+
+    template <class F>
+    void Insert(F&& aInitEntry) {
+      MOZ_ASSERT(!HasEntry());
+      OccupySlot();
+      std::forward<F>(aInitEntry)(Entry());
+    }
+
+    // If the slot is currently vacant, the slot is occupied and `initEntry` is
+    // invoked to initialize the entry. Returns the entry stored in now-occupied
+    // slot.
+    template <class F>
+    PLDHashEntryHdr* OrInsert(F&& aInitEntry) {
+      if (!HasEntry()) {
+        Insert(std::forward<F>(aInitEntry));
+      }
+      return Entry();
+    }
+
+    /** Removes the entry. Note that the table won't shrink on destruction of
+     * the EntryHandle.
+     *
+     * \pre HasEntry()
+     * \post !HasEntry()
+     */
+    void Remove();
+
+    /** Removes the entry, if it exists. Note that the table won't shrink on
+     * destruction of the EntryHandle.
+     *
+     * \post !HasEntry()
+     */
+    void OrRemove();
+
+   private:
+    friend class PLDHashTable;
+
+    EntryHandle(PLDHashTable* aTable, PLDHashNumber aKeyHash, Slot aSlot);
+
+    void OccupySlot();
+
+    PLDHashTable* mTable;
+    PLDHashNumber mKeyHash;
+    Slot mSlot;
+  };
+
+  template <class F>
+  auto WithEntryHandle(const void* aKey, F&& aFunc)
+      -> std::invoke_result_t<F, EntryHandle&&> {
+    return std::forward<F>(aFunc)(MakeEntryHandle(aKey));
+  }
+
+  template <class F>
+  auto WithEntryHandle(const void* aKey, const mozilla::fallible_t& aFallible,
+                       F&& aFunc)
+      -> std::invoke_result_t<F, mozilla::Maybe<EntryHandle>&&> {
+    return std::forward<F>(aFunc)(MakeEntryHandle(aKey, aFallible));
+  }
+
+  // This is an iterator for PLDHashtable. Assertions will detect some, but not
+  // all, mid-iteration table modifications that might invalidate (e.g.
+  // reallocate) the entry storage.
+  //
+  // Any element can be removed during iteration using Remove(). If any
+  // elements are removed, the table may be resized once iteration ends.
+  //
+  // Example usage:
+  //
+  //   for (auto iter = table.Iter(); !iter.Done(); iter.Next()) {
+  //     auto entry = static_cast<FooEntry*>(iter.Get());
+  //     // ... do stuff with |entry| ...
+  //     // ... possibly call iter.Remove() once ...
+  //   }
+  //
+  // or:
+  //
+  //   for (PLDHashTable::Iterator iter(&table); !iter.Done(); iter.Next()) {
+  //     auto entry = static_cast<FooEntry*>(iter.Get());
+  //     // ... do stuff with |entry| ...
+  //     // ... possibly call iter.Remove() once ...
+  //   }
+  //
+  // The latter form is more verbose but is easier to work with when
+  // making subclasses of Iterator.
+  //
+  class Iterator {
+   public:
+    explicit Iterator(PLDHashTable* aTable);
+    struct EndIteratorTag {};
+    Iterator(PLDHashTable* aTable, EndIteratorTag aTag);
+    Iterator(Iterator&& aOther);
+    ~Iterator();
+
+    // Have we finished?
+    bool Done() const { return mNexts == mNextsLimit; }
+
+    // Get the current entry.
+    PLDHashEntryHdr* Get() const {
+      MOZ_ASSERT(!Done());
+      MOZ_ASSERT(mCurrent.IsLive());
+      return mCurrent.ToEntry();
+    }
+
+    // Advance to the next entry.
+    void Next();
+
+    // Remove the current entry. Must only be called once per entry, and Get()
+    // must not be called on that entry afterwards.
+    void Remove();
+
+    bool operator==(const Iterator& aOther) const {
+      MOZ_ASSERT(mTable == aOther.mTable);
+      return mNexts == aOther.mNexts;
+    }
+
+    Iterator Clone() const { return {*this}; }
+
+   protected:
+    PLDHashTable* mTable;  // Main table pointer.
+
+   private:
+    Slot mCurrent;         // Pointer to the current entry.
+    uint32_t mNexts;       // Number of Next() calls.
+    uint32_t mNextsLimit;  // Next() call limit.
+
+    bool mHaveRemoved;   // Have any elements been removed?
+    uint8_t mEntrySize;  // Size of entries.
+
+    bool IsOnNonLiveEntry() const;
+
+    void MoveToNextLiveEntry();
+
+    Iterator() = delete;
+    Iterator(const Iterator&);
+    Iterator& operator=(const Iterator&) = delete;
+    Iterator& operator=(const Iterator&&) = delete;
+  };
+
+  Iterator Iter() { return Iterator(this); }
+
+  // Use this if you need to initialize an Iterator in a const method. If you
+  // use this case, you should not call Remove() on the iterator.
+  Iterator ConstIter() const {
+    return Iterator(const_cast<PLDHashTable*>(this));
+  }
+
+ private:
+  static uint32_t HashShift(uint32_t aEntrySize, uint32_t aLength);
+
+  static const PLDHashNumber kCollisionFlag = 1;
+
+  PLDHashNumber Hash1(PLDHashNumber aHash0) const;
+  void Hash2(PLDHashNumber aHash, uint32_t& aHash2Out,
+             uint32_t& aSizeMaskOut) const;
+
+  static bool MatchSlotKeyhash(Slot& aSlot, const PLDHashNumber aHash);
+  Slot SlotForIndex(uint32_t aIndex) const;
+
+  // We store mHashShift rather than sizeLog2 to optimize the collision-free
+  // case in SearchTable.
+  uint32_t CapacityFromHashShift() const {
+    return ((uint32_t)1 << (kPLDHashNumberBits - mHashShift));
+  }
+
+  PLDHashNumber ComputeKeyHash(const void* aKey) const;
+
+  enum SearchReason { ForSearchOrRemove, ForAdd };
+
+  // Avoid using bare `Success` and `Failure`, as those names are commonly
+  // defined as macros.
+  template <SearchReason Reason, typename PLDSuccess, typename PLDFailure>
+  auto SearchTable(const void* aKey, PLDHashNumber aKeyHash,
+                   PLDSuccess&& aSucess, PLDFailure&& aFailure) const;
+
+  Slot FindFreeSlot(PLDHashNumber aKeyHash) const;
+
+  bool ChangeTable(int aDeltaLog2);
+
+  void RawRemove(Slot& aSlot);
+  void ShrinkIfAppropriate();
+
+  mozilla::Maybe<EntryHandle> MakeEntryHandle(const void* aKey,
+                                              const mozilla::fallible_t&);
+
+  EntryHandle MakeEntryHandle(const void* aKey);
+
+  PLDHashTable(const PLDHashTable& aOther) = delete;
+  PLDHashTable& operator=(const PLDHashTable& aOther) = delete;
+};
+
+// Compute the hash code for a given key to be looked up, added, or removed.
+// A hash code may have any PLDHashNumber value.
+typedef PLDHashNumber (*PLDHashHashKey)(const void* aKey);
+
+// Compare the key identifying aEntry with the provided key parameter. Return
+// true if keys match, false otherwise.
+typedef bool (*PLDHashMatchEntry)(const PLDHashEntryHdr* aEntry,
+                                  const void* aKey);
+
+// Copy the data starting at aFrom to the new entry storage at aTo. Do not add
+// reference counts for any strong references in the entry, however, as this
+// is a "move" operation: the old entry storage at from will be freed without
+// any reference-decrementing callback shortly.
+typedef void (*PLDHashMoveEntry)(PLDHashTable* aTable,
+                                 const PLDHashEntryHdr* aFrom,
+                                 PLDHashEntryHdr* aTo);
+
+// Clear the entry and drop any strong references it holds. This callback is
+// invoked by Remove(), but only if the given key is found in the table.
+typedef void (*PLDHashClearEntry)(PLDHashTable* aTable,
+                                  PLDHashEntryHdr* aEntry);
+
+// Initialize a new entry. This function is called when
+// Add() finds no existing entry for the given key, and must add a new one.
+typedef void (*PLDHashInitEntry)(PLDHashEntryHdr* aEntry, const void* aKey);
+
+// Finally, the "vtable" structure for PLDHashTable. The first four hooks
+// must be provided by implementations; they're called unconditionally by the
+// generic PLDHashTable.cpp code. Hooks after these may be null.
+//
+// Summary of allocation-related hook usage with C++ placement new emphasis:
+//  initEntry           Call placement new using default key-based ctor.
+//  moveEntry           Call placement new using copy ctor, run dtor on old
+//                      entry storage.
+//  clearEntry          Run dtor on entry.
+//
+// Note the reason why initEntry is optional: the default hooks (stubs) clear
+// entry storage. On a successful Add(tbl, key), the returned entry pointer
+// addresses an entry struct whose entry members are still clear (null). Add()
+// callers can test such members to see whether the entry was newly created by
+// the Add() call that just succeeded. If placement new or similar
+// initialization is required, define an |initEntry| hook. Of course, the
+// |clearEntry| hook must zero or null appropriately.
+//
+// XXX assumes 0 is null for pointer types.
+struct PLDHashTableOps {
+  // Mandatory hooks. All implementations must provide these.
+  PLDHashHashKey hashKey;
+  PLDHashMatchEntry matchEntry;
+  PLDHashMoveEntry moveEntry;
+
+  // Optional hooks start here. If null, these are not called.
+  PLDHashClearEntry clearEntry;
+  PLDHashInitEntry initEntry;
+};
+
+// A minimal entry is a subclass of PLDHashEntryHdr and has a void* key pointer.
+struct PLDHashEntryStub : public PLDHashEntryHdr {
+  const void* key;
+};
+
+#endif /* PLDHashTable_h */