/* 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/. */

#ifndef builtin_OrderedHashTableObject_h
#define builtin_OrderedHashTableObject_h

/*
 * [SMDOC] OrderedHashTableObject (JS Map/Set implementation)
 *
 * This file defines js::OrderedHashMapObject (js::MapObject base class) and
 * js::OrderedHashSetObject (js::SetObject base class).
 *
 * It also defines two templates, js::OrderedHashMapImpl and
 * js::OrderedHashSetImpl, that operate on these objects and implement the
 * ordered hash table algorithm. These templates are defined separately from
 * the JS object types because it lets us switch between different template
 * instantiations to enable or disable GC barriers.
 *
 * The implemented hash table algorithm is different from HashMap and HashSet in
 * MFBT:
 *
 *   - JS Map/Set iterators must visit entries in insertion order. The hashing
 *     is a pure performance optimization and does not affect iteration order.
 *
 *   - Iterator objects must remain valid even when entries are added, removed,
 *     or the table is resized.
 *
 * Implementation
 * ==============
 * The hash table contains two arrays: an array of data entries that stores all
 * entries (in insertion/enumeration order) and a separate array of hash buckets
 * that provides O(1) lookup performance instead of O(n).
 *
 * As an optimization, we allocate a single buffer that stores both of these
 * arrays (and the HashCodeScrambler). We allocate this buffer when the first
 * entry is added to the table.
 *
 * The capacity of the data array is based on the number of hash buckets and the
 * FillFactor constant (currently 8.0/3.0).
 *
 * For example, consider the following JS code:
 *
 *   var m = new Map();
 *   m.set(1, "a");
 *   m.set(2, "b");
 *   m.set(3, "c");
 *   m.set(4, "d");
 *   m.delete(2);
 *
 * After this, the Map object might look like this:
 *
 *   HashTableSlot
 *     |    +---------+---------+
 *     +--> | Data #3 | Data #2 |
 *          +-----+---+-----+---+
 *                |         |
 *                +---------|----------------------------+
 *                          +----------------+           |
 *                                           |           |
 *   DataSlot                                v           v
 *     |    +------------+------------+------------+------------+------------+
 *     |    | Data #0    | Data #1    | Data #2    | Data #3    | Data #4    |
 *     +--> | key: 1     | key: $empty| key: 3     | key: 4     | <free>     |
 *          | value: "a" | value: #   | value: "c" | value: "d" |            |
 *          | chain: null| chain: null| chain: #0  | chain: #1  |            |
 *          +------------+------------+------+-----+------+-----+------------+
 *                 ^            ^            |            |
 *                 |            |            |            |
 *                 |            +------------|------------+
 *                 +-------------------------+
 *
 *   LiveCountSlot = 3    (number of entries in the table)
 *   DataCapacitySlot = 5 (total capacity of the data array)
 *   DataLengthSlot = 4   (number of entries used, including deleted items)
 *   HashShiftSlot = 31   (2 hash buckets; see hashShiftToNumHashBuckets)
 *
 * In this case we have only two hash buckets and each bucket contains two Data
 * entries. Entries in the same bucket form a linked list using the |chain|
 * field. This implements separate chaining for hash collisions.
 *
 * When an entry is deleted from the table, we set its key to the
 * MagicValue(JS_HASH_KEY_EMPTY) tombstone Value, shown as $empty in this
 * diagram. Deleted entries are removed when the table is resized or compacted.
 *
 * Iterators
 * =========
 * Each hash table has a doubly linked list of iterators for it. This is used to
 * update active iterators when we remove an entry, when we compact the table,
 * or when we clear the table. See TableIteratorObject and IterOps.
 *
 * HashCodeScrambler
 * =================
 * Each table has a HashCodeScrambler, used to avoid revealing JSObject*
 * addresses. See bug 1312001 and HashValue in MapObject.cpp
 *
 * Nursery GC Optimizations
 * ========================
 * Each table has a list of keys allocated in the nursery that's traced by the
 * OrderedHashTableRef store buffer entry. This avoids tracing all non-nursery
 * entries during a nursery GC.
 *
 * Similarly, each table has a separate list of nursery-allocated iterators.
 * This list is cleared at the start of a nursery GC and rebuilt when iterators
 * are promoted. See Nursery::clearMapAndSetNurseryIterators.
 */

#include "mozilla/HashFunctions.h"
#include "mozilla/Likely.h"
#include "mozilla/Maybe.h"

#include <memory>
#include <tuple>
#include <utility>

#include "builtin/SelfHostingDefines.h"
#include "gc/Barrier.h"
#include "gc/Zone.h"
#include "js/GCPolicyAPI.h"
#include "js/HashTable.h"
#include "vm/JSContext.h"
#include "vm/Realm.h"

class JSTracer;

namespace js {

class MapIteratorObject;
class SetIteratorObject;

namespace detail {

template <class T, class Ops>
class OrderedHashTableImpl;

// Base class for OrderedHashMapObject and OrderedHashSetObject.
class OrderedHashTableObject : public NativeObject {
  // Use a friend class to avoid exposing these slot definitions directly to
  // MapObject and SetObject.
  template <class T, class Ops>
  friend class OrderedHashTableImpl;

  enum Slots {
    HashTableSlot,
    DataSlot,
    DataLengthSlot,
    DataCapacitySlot,
    LiveCountSlot,
    HashShiftSlot,
    TenuredIteratorsSlot,
    NurseryIteratorsSlot,
    HashCodeScramblerSlot,
    SlotCount
  };

  inline void* allocateCellBuffer(JSContext* cx, size_t numBytes);
  inline void freeCellBuffer(JSContext* cx, void* data, size_t numBytes);

 public:
  static constexpr size_t offsetOfDataLength() {
    return getFixedSlotOffset(DataLengthSlot);
  }
  static constexpr size_t offsetOfData() {
    return getFixedSlotOffset(DataSlot);
  }
  static constexpr size_t offsetOfHashTable() {
    return getFixedSlotOffset(HashTableSlot);
  }
  static constexpr size_t offsetOfHashShift() {
    return getFixedSlotOffset(HashShiftSlot);
  }
  static constexpr size_t offsetOfLiveCount() {
    return getFixedSlotOffset(LiveCountSlot);
  }
  static constexpr size_t offsetOfHashCodeScrambler() {
    return getFixedSlotOffset(HashCodeScramblerSlot);
  }
};

}  // namespace detail

// Base class for MapIteratorObject and SetIteratorObject.
//
// Iterators remain valid for the lifetime of the OrderedHashTableObject, even
// if entries are added or removed or if the table is resized. Hash table
// objects have a doubly linked list of all active iterator objects and this
// lets us update the iterators when needed.
//
// An "active" iterator object has a target object and must be part of its
// linked list of iterators. When the iterator is finished, the target slot is
// cleared and the iterator is removed from the linked list.
//
// Note: the iterator list stores pointers to iterators as PrivateValue instead
// of ObjectValue because we want these links to be weak pointers: an iterator
// must not keep all other iterators alive.
class TableIteratorObject : public NativeObject {
  template <class T, class Ops>
  friend class detail::OrderedHashTableImpl;

 public:
  enum Slots {
    TargetSlot,
    KindSlot,
    IndexSlot,
    CountSlot,
    PrevPtrSlot,
    NextSlot,
    SlotCount
  };
  enum class Kind { Keys, Values, Entries };

  // Slot numbers and Kind values must match constants used in self-hosted code.
  static_assert(TargetSlot == ITERATOR_SLOT_TARGET);
  static_assert(KindSlot == MAP_SET_ITERATOR_SLOT_ITEM_KIND);
  static_assert(int32_t(Kind::Keys) == ITEM_KIND_KEY);
  static_assert(int32_t(Kind::Values) == ITEM_KIND_VALUE);
  static_assert(int32_t(Kind::Entries) == ITEM_KIND_KEY_AND_VALUE);

 private:
  // The index of the current entry within the table's data array.
  uint32_t getIndex() const {
    return getReservedSlot(IndexSlot).toPrivateUint32();
  }
  void setIndex(uint32_t i) {
    MOZ_ASSERT(isActive());
    setReservedSlotPrivateUint32Unbarriered(IndexSlot, i);
  }

  // The number of nonempty entries in the data array to the left of |index|.
  // This is used when the table is resized or compacted.
  uint32_t getCount() const {
    return getReservedSlot(CountSlot).toPrivateUint32();
  }
  void setCount(uint32_t i) {
    MOZ_ASSERT(isActive());
    setReservedSlotPrivateUint32Unbarriered(CountSlot, i);
  }

  // Links in the doubly-linked list of active iterator objects on the
  // OrderedHashTableObject.
  //
  // The PrevPtr slot points to either the previous iterator's NextSlot or to
  // the table's TenuredIteratorsSlot or NurseryIteratorsSlot if this is the
  // first iterator in the list.
  //
  // The Next slot points to the next iterator object, or is nullptr if this is
  // the last iterator in the list.
  //
  // Invariant: *getPrevPtr() == this.
  TableIteratorObject** getPrevPtr() const {
    MOZ_ASSERT(isActive());
    Value v = getReservedSlot(PrevPtrSlot);
    return static_cast<TableIteratorObject**>(v.toPrivate());
  }
  void setPrevPtr(TableIteratorObject** p) {
    MOZ_ASSERT(isActive());
    setReservedSlotPrivateUnbarriered(PrevPtrSlot, p);
  }
  TableIteratorObject* getNext() const {
    MOZ_ASSERT(isActive());
    Value v = getReservedSlot(NextSlot);
    return static_cast<TableIteratorObject*>(v.toPrivate());
  }
  TableIteratorObject** addressOfNext() {
    MOZ_ASSERT(isActive());
    return addressOfFixedSlotPrivatePtr<TableIteratorObject>(NextSlot);
  }
  void setNext(TableIteratorObject* p) {
    MOZ_ASSERT(isActive());
    setReservedSlotPrivateUnbarriered(NextSlot, p);
  }

  void link(TableIteratorObject** listp) {
    MOZ_ASSERT(isActive());
    TableIteratorObject* next = *listp;
    setPrevPtr(listp);
    setNext(next);
    *listp = this;
    if (next) {
      next->setPrevPtr(this->addressOfNext());
    }
  }

  void init(detail::OrderedHashTableObject* target, Kind kind,
            TableIteratorObject** listp) {
    initReservedSlot(TargetSlot, ObjectValue(*target));
    setReservedSlotPrivateUint32Unbarriered(KindSlot, uint32_t(kind));
    setReservedSlotPrivateUint32Unbarriered(IndexSlot, 0);
    setReservedSlotPrivateUint32Unbarriered(CountSlot, 0);
    link(listp);
  }

  void assertActiveIteratorFor(JSObject* target) {
    MOZ_ASSERT(&getReservedSlot(TargetSlot).toObject() == target);
    MOZ_ASSERT(*getPrevPtr() == this);
    MOZ_ASSERT(getNext() != this);
  }

 protected:
  bool isActive() const { return getReservedSlot(TargetSlot).isObject(); }

  void finish() {
    MOZ_ASSERT(isActive());
    unlink();
    // Mark iterator inactive.
    setReservedSlot(TargetSlot, UndefinedValue());
  }
  void unlink() {
    MOZ_ASSERT(isActive());
    TableIteratorObject** prevp = getPrevPtr();
    TableIteratorObject* next = getNext();
    *prevp = next;
    if (next) {
      next->setPrevPtr(prevp);
    }
  }

  // Update list pointers after a compacting GC moved this iterator in memory.
  // Note: this isn't used for nursery iterators because in that case we have to
  // rebuild the list with clearNurseryIterators and relinkNurseryIterator.
  void updateListAfterMove(TableIteratorObject* old) {
    MOZ_ASSERT(!IsInsideNursery(old));
    MOZ_ASSERT(isActive());
    MOZ_ASSERT(old != this);

    TableIteratorObject** prevp = getPrevPtr();
    MOZ_ASSERT(*prevp == old);
    *prevp = this;

    if (TableIteratorObject* next = getNext()) {
      MOZ_ASSERT(next->getPrevPtr() == old->addressOfNext());
      next->setPrevPtr(this->addressOfNext());
    }
  }

  Kind kind() const {
    uint32_t i = getReservedSlot(KindSlot).toPrivateUint32();
    MOZ_ASSERT(i == uint32_t(Kind::Keys) || i == uint32_t(Kind::Values) ||
               i == uint32_t(Kind::Entries));
    return Kind(i);
  }

 public:
  static constexpr size_t offsetOfTarget() {
    return getFixedSlotOffset(TargetSlot);
  }
  static constexpr size_t offsetOfIndex() {
    return getFixedSlotOffset(IndexSlot);
  }
  static constexpr size_t offsetOfCount() {
    return getFixedSlotOffset(CountSlot);
  }
  static constexpr size_t offsetOfPrevPtr() {
    return getFixedSlotOffset(PrevPtrSlot);
  }
  static constexpr size_t offsetOfNext() {
    return getFixedSlotOffset(NextSlot);
  }
};

namespace detail {

/*
 * detail::OrderedHashTableImpl is the underlying code used to implement both
 * OrderedHashMapImpl and OrderedHashSetImpl. Programs should use one of those
 * two templates rather than OrderedHashTableImpl.
 */
template <class T, class Ops>
class MOZ_STACK_CLASS OrderedHashTableImpl {
 public:
  using Key = typename Ops::KeyType;
  using MutableKey = std::remove_const_t<Key>;
  using UnbarrieredKey = typename RemoveBarrier<MutableKey>::Type;
  using Lookup = typename Ops::Lookup;
  using HashCodeScrambler = mozilla::HashCodeScrambler;
  static constexpr size_t SlotCount = OrderedHashTableObject::SlotCount;

  // Note: use alignas(8) to simplify JIT code generation because
  // alignof(JS::Value) can be either 4 or 8 on 32-bit platforms.
  struct alignas(8) Data {
    T element;
    Data* chain;

    Data(const T& e, Data* c) : element(e), chain(c) {}
    Data(T&& e, Data* c) : element(std::move(e)), chain(c) {}
  };

 private:
  using Slots = OrderedHashTableObject::Slots;
  OrderedHashTableObject* const obj;

  // Whether we have allocated a buffer for this object. This buffer is
  // allocated when adding the first entry and it contains the data array, the
  // hash table buckets and the hash code scrambler.
  bool hasAllocatedBuffer() const {
    MOZ_ASSERT(hasInitializedSlots());
    return obj->getReservedSlot(Slots::DataSlot).toPrivate() != nullptr;
  }

  // Hash table. Has hashBuckets() elements.
  // Note: a single malloc buffer is used for the data and hashTable arrays and
  // the HashCodeScrambler. The pointer in DataSlot points to the start of this
  // buffer.
  Data** getHashTable() const {
    MOZ_ASSERT(hasAllocatedBuffer());
    Value v = obj->getReservedSlot(Slots::HashTableSlot);
    return static_cast<Data**>(v.toPrivate());
  }
  void setHashTable(Data** table) {
    obj->setReservedSlotPrivateUnbarriered(Slots::HashTableSlot, table);
  }

  // Array of Data objects. Elements data[0:dataLength] are constructed and the
  // total capacity is dataCapacity.
  //
  // maybeData returns nullptr if this object doesn't have a buffer yet.
  // getData asserts the object has a buffer.
  Data* maybeData() const {
    Value v = obj->getReservedSlot(Slots::DataSlot);
    return static_cast<Data*>(v.toPrivate());
  }
  Data* getData() const {
    MOZ_ASSERT(hasAllocatedBuffer());
    return maybeData();
  }
  void setData(Data* data) {
    obj->setReservedSlotPrivateUnbarriered(Slots::DataSlot, data);
  }

  // Number of constructed elements in the data array.
  uint32_t getDataLength() const {
    return obj->getReservedSlot(Slots::DataLengthSlot).toPrivateUint32();
  }
  void setDataLength(uint32_t length) {
    obj->setReservedSlotPrivateUint32Unbarriered(Slots::DataLengthSlot, length);
  }

  // Size of data array, in elements.
  uint32_t getDataCapacity() const {
    return obj->getReservedSlot(Slots::DataCapacitySlot).toPrivateUint32();
  }
  void setDataCapacity(uint32_t capacity) {
    obj->setReservedSlotPrivateUint32Unbarriered(Slots::DataCapacitySlot,
                                                 capacity);
  }

  // The number of elements in this table. This is different from dataLength
  // because the data array can contain empty/removed elements.
  uint32_t getLiveCount() const {
    return obj->getReservedSlot(Slots::LiveCountSlot).toPrivateUint32();
  }
  void setLiveCount(uint32_t liveCount) {
    obj->setReservedSlotPrivateUint32Unbarriered(Slots::LiveCountSlot,
                                                 liveCount);
  }

  // Multiplicative hash shift.
  uint32_t getHashShift() const {
    MOZ_ASSERT(hasAllocatedBuffer(),
               "hash shift is meaningless if there's no hash table");
    return obj->getReservedSlot(Slots::HashShiftSlot).toPrivateUint32();
  }
  void setHashShift(uint32_t hashShift) {
    obj->setReservedSlotPrivateUint32Unbarriered(Slots::HashShiftSlot,
                                                 hashShift);
  }

  // List of all active iterators on this table in the tenured heap. Populated
  // when iterators are created.
  TableIteratorObject* getTenuredIterators() const {
    Value v = obj->getReservedSlot(Slots::TenuredIteratorsSlot);
    return static_cast<TableIteratorObject*>(v.toPrivate());
  }
  void setTenuredIterators(TableIteratorObject* iter) {
    obj->setReservedSlotPrivateUnbarriered(Slots::TenuredIteratorsSlot, iter);
  }
  TableIteratorObject** addressOfTenuredIterators() const {
    static constexpr size_t slot = Slots::TenuredIteratorsSlot;
    return obj->addressOfFixedSlotPrivatePtr<TableIteratorObject>(slot);
  }

  // List of all active iterators on this table in the GC nursery.
  // Populated when iterators are created. This is cleared at the start
  // of minor GC and rebuilt when iterators are moved.
  TableIteratorObject* getNurseryIterators() const {
    Value v = obj->getReservedSlot(Slots::NurseryIteratorsSlot);
    return static_cast<TableIteratorObject*>(v.toPrivate());
  }
  void setNurseryIterators(TableIteratorObject* iter) {
    obj->setReservedSlotPrivateUnbarriered(Slots::NurseryIteratorsSlot, iter);
  }
  TableIteratorObject** addressOfNurseryIterators() const {
    static constexpr size_t slot = Slots::NurseryIteratorsSlot;
    return obj->addressOfFixedSlotPrivatePtr<TableIteratorObject>(slot);
  }

  // Returns a pointer to the list of tenured or nursery iterators depending on
  // where |iter| is allocated.
  TableIteratorObject** addressOfIterators(TableIteratorObject* iter) {
    return IsInsideNursery(iter) ? addressOfNurseryIterators()
                                 : addressOfTenuredIterators();
  }

  // Scrambler to not reveal pointer hash codes.
  const HashCodeScrambler* getHashCodeScrambler() const {
    MOZ_ASSERT(hasAllocatedBuffer());
    Value v = obj->getReservedSlot(Slots::HashCodeScramblerSlot);
    return static_cast<const HashCodeScrambler*>(v.toPrivate());
  }
  void setHashCodeScrambler(HashCodeScrambler* hcs) {
    obj->setReservedSlotPrivateUnbarriered(Slots::HashCodeScramblerSlot, hcs);
  }

  static constexpr uint32_t hashShiftToNumHashBuckets(uint32_t hashShift) {
    return 1 << (js::kHashNumberBits - hashShift);
  }
  static constexpr uint32_t numHashBucketsToDataCapacity(
      uint32_t numHashBuckets) {
    return uint32_t(numHashBuckets * FillFactor);
  }

  // Logarithm base 2 of the number of buckets in the hash table initially.
  static constexpr uint32_t InitialBucketsLog2 = 1;
  static constexpr uint32_t InitialBuckets = 1 << InitialBucketsLog2;
  static constexpr uint32_t InitialHashShift =
      js::kHashNumberBits - InitialBucketsLog2;

  // The maximum load factor (mean number of entries per bucket).
  // It is an invariant that
  //     dataCapacity == floor(hashBuckets * FillFactor).
  //
  // The fill factor should be between 2 and 4, and it should be chosen so that
  // the fill factor times sizeof(Data) is close to but <= a power of 2.
  // This fixed fill factor was chosen to make the size of the data
  // array, in bytes, close to a power of two when sizeof(T) is 16.
  static constexpr double FillFactor = 8.0 / 3.0;

  // The minimum permitted value of (liveCount / dataLength).
  // If that ratio drops below this value, we shrink the table.
  static constexpr double MinDataFill = 0.25;

  // Note: a lower hash shift results in a higher capacity.
  static constexpr uint32_t MinHashShift = 8;
  static constexpr uint32_t MaxHashBuckets =
      hashShiftToNumHashBuckets(MinHashShift);  // 16777216
  static constexpr uint32_t MaxDataCapacity =
      numHashBucketsToDataCapacity(MaxHashBuckets);  // 44739242

  template <typename F>
  void forEachIterator(F&& f) {
    TableIteratorObject* next;
    for (TableIteratorObject* iter = getTenuredIterators(); iter; iter = next) {
      next = iter->getNext();
      f(iter);
    }
    for (TableIteratorObject* iter = getNurseryIterators(); iter; iter = next) {
      next = iter->getNext();
      f(iter);
    }
  }

  bool hasInitializedSlots() const {
    return !obj->getReservedSlot(Slots::DataSlot).isUndefined();
  }

  static constexpr size_t calcAllocSize(size_t dataCapacity, size_t buckets) {
    return dataCapacity * sizeof(Data) + sizeof(HashCodeScrambler) +
           buckets * sizeof(Data*);
  }

  // Allocate a single buffer that stores the data array followed by the hash
  // code scrambler and the hash table entries.
  using AllocationResult =
      std::tuple<Data*, Data**, HashCodeScrambler*, size_t>;
  AllocationResult allocateBuffer(JSContext* cx, uint32_t dataCapacity,
                                  uint32_t buckets) {
    MOZ_ASSERT(dataCapacity <= MaxDataCapacity);
    MOZ_ASSERT(buckets <= MaxHashBuckets);

    // Ensure the maximum buffer size doesn't exceed INT32_MAX. Don't change
    // this without auditing the buffer allocation code!
    static_assert(calcAllocSize(MaxDataCapacity, MaxHashBuckets) <= INT32_MAX);

    size_t numBytes = calcAllocSize(dataCapacity, buckets);

    void* buf = obj->allocateCellBuffer(cx, numBytes);
    if (!buf) {
      return {};
    }

    return getBufferParts(buf, numBytes, dataCapacity, buckets);
  }

  static AllocationResult getBufferParts(void* buf, size_t numBytes,
                                         uint32_t dataCapacity,
                                         uint32_t buckets) {
    static_assert(alignof(Data) % alignof(HashCodeScrambler) == 0,
                  "Hash code scrambler must be aligned properly");
    static_assert(alignof(HashCodeScrambler) % alignof(Data*) == 0,
                  "Hash table entries must be aligned properly");

    auto* data = static_cast<Data*>(buf);
    auto* hcs = reinterpret_cast<HashCodeScrambler*>(data + dataCapacity);
    auto** table = reinterpret_cast<Data**>(hcs + 1);

    MOZ_ASSERT(uintptr_t(table + buckets) == uintptr_t(buf) + numBytes);

    return {data, table, hcs, numBytes};
  }

  [[nodiscard]] bool initBuffer(JSContext* cx) {
    MOZ_ASSERT(!hasAllocatedBuffer());
    MOZ_ASSERT(getDataLength() == 0);
    MOZ_ASSERT(getLiveCount() == 0);

    constexpr uint32_t buckets = InitialBuckets;
    constexpr uint32_t capacity = uint32_t(buckets * FillFactor);

    auto [dataAlloc, tableAlloc, hcsAlloc, numBytes] =
        allocateBuffer(cx, capacity, buckets);
    if (!dataAlloc) {
      return false;
    }

    *hcsAlloc = cx->realm()->randomHashCodeScrambler();

    std::uninitialized_fill_n(tableAlloc, buckets, nullptr);

    setHashTable(tableAlloc);
    setData(dataAlloc);
    setDataCapacity(capacity);
    setHashShift(InitialHashShift);
    setHashCodeScrambler(hcsAlloc);
    MOZ_ASSERT(hashBuckets() == buckets);
    return true;
  }

  void updateHashTableForRekey(Data* entry, HashNumber oldHash,
                               HashNumber newHash) {
    uint32_t hashShift = getHashShift();
    oldHash >>= hashShift;
    newHash >>= hashShift;

    if (oldHash == newHash) {
      return;
    }

    // Remove this entry from its old hash chain. (If this crashes reading
    // nullptr, it would mean we did not find this entry on the hash chain where
    // we expected it. That probably means the key's hash code changed since it
    // was inserted, breaking the hash code invariant.)
    Data** hashTable = getHashTable();
    Data** ep = &hashTable[oldHash];
    while (*ep != entry) {
      ep = &(*ep)->chain;
    }
    *ep = entry->chain;

    // Add it to the new hash chain. We could just insert it at the beginning of
    // the chain. Instead, we do a bit of work to preserve the invariant that
    // hash chains always go in reverse insertion order (descending memory
    // order). No code currently depends on this invariant, so it's fine to kill
    // it if needed.
    ep = &hashTable[newHash];
    while (*ep && *ep > entry) {
      ep = &(*ep)->chain;
    }
    entry->chain = *ep;
    *ep = entry;
  }

 public:
  explicit OrderedHashTableImpl(OrderedHashTableObject* obj) : obj(obj) {}

  void initSlots() {
    MOZ_ASSERT(!hasInitializedSlots(), "init must be called at most once");
    setHashTable(nullptr);
    setData(nullptr);
    setDataLength(0);
    setDataCapacity(0);
    setLiveCount(0);
    setHashShift(0);
    setTenuredIterators(nullptr);
    setNurseryIterators(nullptr);
    setHashCodeScrambler(nullptr);
  }

  void maybeMoveBufferOnPromotion(Nursery& nursery) {
    if (!hasAllocatedBuffer()) {
      return;
    }

    Data* oldData = getData();
    uint32_t dataCapacity = getDataCapacity();
    uint32_t buckets = hashBuckets();

    size_t numBytes = calcAllocSize(dataCapacity, buckets);

    void* buf = oldData;
    Nursery::WasBufferMoved result =
        nursery.maybeMoveBufferOnPromotion(&buf, obj, numBytes);
    if (result == Nursery::BufferNotMoved) {
      return;
    }

    // The buffer was moved in memory. Update reserved slots and fix up the
    // |Data*| pointers for the hash table chains.
    // TODO(bug 1931492): consider storing indices instead of pointers to
    // simplify this.

    auto [data, table, hcs, numBytesUnused] =
        getBufferParts(buf, numBytes, dataCapacity, buckets);

    auto entryIndex = [=](const Data* entry) {
      MOZ_ASSERT(entry >= oldData);
      MOZ_ASSERT(size_t(entry - oldData) < dataCapacity);
      return entry - oldData;
    };

    for (uint32_t i = 0, len = getDataLength(); i < len; i++) {
      if (const Data* chain = data[i].chain) {
        data[i].chain = data + entryIndex(chain);
      }
    }
    for (uint32_t i = 0; i < buckets; i++) {
      if (const Data* chain = table[i]) {
        table[i] = data + entryIndex(chain);
      }
    }

    setData(data);
    setHashTable(table);
    setHashCodeScrambler(hcs);
  }

  size_t sizeOfExcludingObject() const {
    MOZ_ASSERT(obj->isTenured());  // Assumes data is not in the nursery.

    size_t size = 0;
    if (hasInitializedSlots() && hasAllocatedBuffer()) {
      // Note: this also includes the HashCodeScrambler and the hashTable array.
      size += gc::GetAllocSize(obj->zone(), getData());
    }
    return size;
  }

  /* Return the number of elements in the table. */
  uint32_t count() const { return getLiveCount(); }

  /* True if any element matches l. */
  bool has(const Lookup& l) const { return lookup(l) != nullptr; }

  /* Return a pointer to the element, if any, that matches l, or nullptr. */
  T* get(const Lookup& l) {
    Data* e = lookup(l);
    return e ? &e->element : nullptr;
  }

  /*
   * If the table already contains an entry that matches |element|,
   * replace that entry with |element|. Otherwise add a new entry.
   *
   * On success, return true, whether there was already a matching element or
   * not. On allocation failure, return false. If this returns false, it
   * means the element was not added to the table.
   */
  template <typename ElementInput>
  [[nodiscard]] bool put(JSContext* cx, ElementInput&& elementInput) {
    T element(std::forward<ElementInput>(elementInput));
    HashNumber h;
    if (hasAllocatedBuffer()) {
      h = prepareHash(Ops::getKey(element));
      if (Data* e = lookup(Ops::getKey(element), h)) {
        e->element = std::move(element);
        return true;
      }
      if (getDataLength() == getDataCapacity() && !rehashOnFull(cx)) {
        return false;
      }
    } else {
      if (!initBuffer(cx)) {
        return false;
      }
      h = prepareHash(Ops::getKey(element));
    }
    auto [entry, chain] = addEntry(h);
    new (entry) Data(std::move(element), chain);
    return true;
  }

  /*
   * If the table already contains an entry that matches |element|,
   * return that entry. Otherwise add a new entry.
   *
   * On success, return a pointer to the element, whether there was already a
   * matching element or not. On allocation failure, return a nullptr. If this
   * returns a nullptr, it means the element was not added to the table.
   */
  template <typename ElementInput>
  [[nodiscard]] T* getOrAdd(JSContext* cx, ElementInput&& element) {
    HashNumber h;
    if (hasAllocatedBuffer()) {
      h = prepareHash(Ops::getKey(element));
      if (Data* e = lookup(Ops::getKey(element), h)) {
        return &e->element;
      }
      if (getDataLength() == getDataCapacity() && !rehashOnFull(cx)) {
        return nullptr;
      }
    } else {
      if (!initBuffer(cx)) {
        return nullptr;
      }
      h = prepareHash(Ops::getKey(element));
    }
    auto [entry, chain] = addEntry(h);
    new (entry) Data(std::forward<ElementInput>(element), chain);
    return &entry->element;
  }

  /*
   * If the table contains an element matching l, remove it and return true.
   * Otherwise return false.
   */
  bool remove(JSContext* cx, const Lookup& l) {
    // Note: This could be optimized so that removing the last entry,
    // data[dataLength - 1], decrements dataLength. LIFO use cases would
    // benefit.

    // If a matching entry exists, empty it.
    Data* e = lookup(l);
    if (e == nullptr) {
      return false;
    }

    MOZ_ASSERT(uint32_t(e - getData()) < getDataCapacity());

    uint32_t liveCount = getLiveCount();
    liveCount--;
    setLiveCount(liveCount);
    Ops::makeEmpty(&e->element);

    // Update active iterators.
    uint32_t pos = e - getData();
    forEachIterator(
        [this, pos](auto* iter) { IterOps::onRemove(obj, iter, pos); });

    // If many entries have been removed, try to shrink the table. Ignore OOM
    // because shrinking the table is an optimization and it's okay for it to
    // fail.
    if (hashBuckets() > InitialBuckets &&
        liveCount < getDataLength() * MinDataFill) {
      if (!rehash(cx, getHashShift() + 1)) {
        cx->recoverFromOutOfMemory();
      }
    }

    return true;
  }

  /*
   * Remove all entries.
   *
   * The effect on active iterators is the same as removing all entries; in
   * particular, those iterators are still active and will see any entries
   * added after a clear().
   */
  void clear(JSContext* cx) {
    if (getDataLength() != 0) {
      destroyData(getData(), getDataLength());
      setDataLength(0);
      setLiveCount(0);

      size_t buckets = hashBuckets();
      std::fill_n(getHashTable(), buckets, nullptr);

      forEachIterator([](auto* iter) { IterOps::onClear(iter); });

      // Try to shrink the table. Ignore OOM because shrinking the table is an
      // optimization and it's okay for it to fail.
      if (buckets > InitialBuckets) {
        if (!rehash(cx, InitialHashShift)) {
          cx->recoverFromOutOfMemory();
        }
      }
    }

    MOZ_ASSERT(getDataLength() == 0);
    MOZ_ASSERT(getLiveCount() == 0);
  }

  class IterOps {
    friend class OrderedHashTableImpl;

    static void init(OrderedHashTableObject* table, TableIteratorObject* iter,
                     TableIteratorObject::Kind kind) {
      auto** listp = OrderedHashTableImpl(table).addressOfIterators(iter);
      iter->init(table, kind, listp);
      seek(table, iter);
    }

    static void seek(OrderedHashTableObject* table, TableIteratorObject* iter) {
      iter->assertActiveIteratorFor(table);
      const Data* data = OrderedHashTableImpl(table).maybeData();
      uint32_t dataLength = OrderedHashTableImpl(table).getDataLength();
      uint32_t i = iter->getIndex();
      while (i < dataLength && Ops::isEmpty(Ops::getKey(data[i].element))) {
        i++;
      }
      iter->setIndex(i);
    }

    // The hash table calls this when an entry is removed.
    // j is the index of the removed entry.
    static void onRemove(OrderedHashTableObject* table,
                         TableIteratorObject* iter, uint32_t j) {
      iter->assertActiveIteratorFor(table);
      uint32_t i = iter->getIndex();
      if (j < i) {
        iter->setCount(iter->getCount() - 1);
      }
      if (j == i) {
        seek(table, iter);
      }
    }

    // The hash table calls this when the table is resized or compacted.
    // Since |count| is the number of nonempty entries to the left of |index|,
    // discarding the empty entries will not affect |count|, and it will make
    // |index| and |count| equal.
    static void onCompact(TableIteratorObject* iter) {
      iter->setIndex(iter->getCount());
    }

    // The hash table calls this when cleared.
    static void onClear(TableIteratorObject* iter) {
      iter->setIndex(0);
      iter->setCount(0);
    }

    // If the iterator reached the end of the data array, we're done: mark the
    // iterator inactive, remove it from the linked list, and return |true|.
    // Else, call |f| for the current entry, advance the iterator to the next
    // entry, and return |false|.
    template <typename F>
    static bool next(OrderedHashTableObject* obj, TableIteratorObject* iter,
                     F&& f) {
      iter->assertActiveIteratorFor(obj);

      OrderedHashTableImpl table(obj);
      uint32_t index = iter->getIndex();

      if (index >= table.getDataLength()) {
        iter->finish();
        return true;
      }

      f(iter->kind(), table.getData()[index].element);

      iter->setCount(iter->getCount() + 1);
      iter->setIndex(index + 1);
      seek(obj, iter);
      return false;
    }
  };

  // Calls |f| for each entry in the table. This function must not mutate the
  // table.
  template <typename F>
  [[nodiscard]] bool forEachEntry(F&& f) const {
    const Data* data = maybeData();
    uint32_t dataLength = getDataLength();
#ifdef DEBUG
    uint32_t liveCount = getLiveCount();
#endif
    for (uint32_t i = 0; i < dataLength; i++) {
      if (!Ops::isEmpty(Ops::getKey(data[i].element))) {
        if (!f(data[i].element)) {
          return false;
        }
      }
    }
    MOZ_ASSERT(maybeData() == data);
    MOZ_ASSERT(getDataLength() == dataLength);
    MOZ_ASSERT(getLiveCount() == liveCount);
    return true;
  }
#ifdef DEBUG
  // Like forEachEntry, but infallible and the function is called at most
  // maxCount times. This is useful for debug assertions.
  template <typename F>
  void forEachEntryUpTo(size_t maxCount, F&& f) const {
    MOZ_ASSERT(maxCount > 0);
    const Data* data = maybeData();
    uint32_t dataLength = getDataLength();
    uint32_t liveCount = getLiveCount();
    size_t count = 0;
    for (uint32_t i = 0; i < dataLength; i++) {
      if (!Ops::isEmpty(Ops::getKey(data[i].element))) {
        f(data[i].element);
        count++;
        if (count == maxCount) {
          break;
        }
      }
    }
    MOZ_ASSERT(maybeData() == data);
    MOZ_ASSERT(getDataLength() == dataLength);
    MOZ_ASSERT(getLiveCount() == liveCount);
  }
#endif

  void trace(JSTracer* trc) {
    Data* data = maybeData();
    if (data) {
      TraceBufferEdge(trc, &data, "OrderedHashTable data");
      if (data != maybeData()) {
        setData(data);
      }
    }

    uint32_t dataLength = getDataLength();
    for (uint32_t i = 0; i < dataLength; i++) {
      if (!Ops::isEmpty(Ops::getKey(data[i].element))) {
        Ops::trace(trc, this, i, data[i].element);
      }
    }
  }

  // For use by the implementation of Ops::trace.
  void traceKey(JSTracer* trc, uint32_t index, const Key& key) {
    MOZ_ASSERT(index < getDataLength());
    UnbarrieredKey newKey = key;
    JS::GCPolicy<UnbarrieredKey>::trace(trc, &newKey,
                                        "OrderedHashTableObject key");
    if (newKey != key) {
      rekey(&getData()[index], newKey);
    }
  }
  template <typename Value>
  void traceValue(JSTracer* trc, Value& value) {
    JS::GCPolicy<Value>::trace(trc, &value, "OrderedHashMapObject value");
  }

  void initIterator(TableIteratorObject* iter,
                    TableIteratorObject::Kind kind) const {
    IterOps::init(obj, iter, kind);
  }
  template <typename F>
  bool iteratorNext(TableIteratorObject* iter, F&& f) const {
    return IterOps::next(obj, iter, f);
  }

  void clearNurseryIterators() {
    if (TableIteratorObject* iter = getNurseryIterators()) {
      iter->setPrevPtr(nullptr);
    }
    setNurseryIterators(nullptr);
  }
  void relinkNurseryIterator(TableIteratorObject* iter) {
    auto** listp = addressOfIterators(iter);
    iter->link(listp);
  }

  void updateIteratorsAfterMove(OrderedHashTableObject* old) {
    if (TableIteratorObject* iter = getTenuredIterators()) {
      MOZ_ASSERT(iter->getPrevPtr() ==
                 OrderedHashTableImpl(old).addressOfTenuredIterators());
      iter->setPrevPtr(addressOfTenuredIterators());
    }
    if (TableIteratorObject* iter = getNurseryIterators()) {
      MOZ_ASSERT(iter->getPrevPtr() ==
                 OrderedHashTableImpl(old).addressOfNurseryIterators());
      iter->setPrevPtr(addressOfNurseryIterators());
    }
  }

  bool hasNurseryIterators() const { return getNurseryIterators(); }

  /*
   * Change the value of the given key.
   *
   * This calls Ops::hash on both the current key and the new key.
   * Ops::hash on the current key must return the same hash code as
   * when the entry was added to the table.
   */
  void rekeyOneEntry(const Key& current, const Key& newKey, const T& element) {
    if (current == newKey) {
      return;
    }

    HashNumber currentHash = prepareHash(current);
    HashNumber newHash = prepareHash(newKey);

    Data* entry = lookup(current, currentHash);
    MOZ_ASSERT(entry);
    entry->element = element;

    updateHashTableForRekey(entry, currentHash, newHash);
  }

  static constexpr size_t offsetOfDataElement() {
    static_assert(offsetof(Data, element) == 0,
                  "TableIteratorLoadEntry and TableIteratorAdvance depend on "
                  "offsetof(Data, element) being 0");
    return offsetof(Data, element);
  }
  static constexpr size_t offsetOfDataChain() { return offsetof(Data, chain); }
  static constexpr size_t sizeofData() { return sizeof(Data); }

#ifdef DEBUG
  mozilla::Maybe<HashNumber> hash(const Lookup& l) const {
    // We can only compute the hash number if we have an allocated buffer
    // because the buffer contains the hash code scrambler.
    if (!hasAllocatedBuffer()) {
      return {};
    }
    return mozilla::Some(prepareHash(l));
  }
#endif

 private:
  HashNumber prepareHash(const Lookup& l) const {
    MOZ_ASSERT(hasAllocatedBuffer(),
               "the hash code scrambler is allocated in the buffer");
    const HashCodeScrambler& hcs = *getHashCodeScrambler();
    return mozilla::ScrambleHashCode(Ops::hash(l, hcs));
  }

  /* The size of the hash table, in elements. Always a power of two. */
  uint32_t hashBuckets() const {
    return hashShiftToNumHashBuckets(getHashShift());
  }

  void destroyData(Data* data, uint32_t length) {
    Data* end = data + length;
    for (Data* p = data; p != end; p++) {
      p->~Data();
    }
  }

  void freeData(JSContext* cx, Data* data, uint32_t length, uint32_t capacity,
                uint32_t hashBuckets) {
    MOZ_ASSERT(data);
    MOZ_ASSERT(capacity > 0);

    destroyData(data, length);

    size_t numBytes = calcAllocSize(capacity, hashBuckets);

    obj->freeCellBuffer(cx, data, numBytes);
  }

  Data* lookup(const Lookup& l, HashNumber h) const {
    MOZ_ASSERT(hasAllocatedBuffer());
    Data** hashTable = getHashTable();
    uint32_t hashShift = getHashShift();
    for (Data* e = hashTable[h >> hashShift]; e; e = e->chain) {
      if (Ops::match(Ops::getKey(e->element), l)) {
        return e;
      }
    }
    return nullptr;
  }

  Data* lookup(const Lookup& l) const {
    // Note: checking |getLiveCount() > 0| is a minor performance optimization
    // but this check is also required for correctness because it implies
    // |hasAllocatedBuffer()|.
    if (getLiveCount() == 0) {
      return nullptr;
    }
    return lookup(l, prepareHash(l));
  }

  std::tuple<Data*, Data*> addEntry(HashNumber hash) {
    uint32_t dataLength = getDataLength();
    MOZ_ASSERT(dataLength < getDataCapacity());

    Data* entry = &getData()[dataLength];
    setDataLength(dataLength + 1);
    setLiveCount(getLiveCount() + 1);

    Data** hashTable = getHashTable();
    hash >>= getHashShift();
    Data* chain = hashTable[hash];
    hashTable[hash] = entry;

    return std::make_tuple(entry, chain);
  }

  /* This is called after rehashing the table. */
  void compacted() {
    // If we had any empty entries, compacting may have moved live entries
    // to the left within the data array. Notify all active iterators of
    // the change.
    forEachIterator([](auto* iter) { IterOps::onCompact(iter); });
  }

  /* Compact the entries in the data array and rehash them. */
  void rehashInPlace() {
    Data** hashTable = getHashTable();
    std::fill_n(hashTable, hashBuckets(), nullptr);

    Data* const data = getData();
    uint32_t hashShift = getHashShift();
    Data* wp = data;
    Data* end = data + getDataLength();
    for (Data* rp = data; rp != end; rp++) {
      if (!Ops::isEmpty(Ops::getKey(rp->element))) {
        HashNumber h = prepareHash(Ops::getKey(rp->element)) >> hashShift;
        if (rp != wp) {
          wp->element = std::move(rp->element);
        }
        wp->chain = hashTable[h];
        hashTable[h] = wp;
        wp++;
      }
    }
    MOZ_ASSERT(wp == data + getLiveCount());

    while (wp != end) {
      wp->~Data();
      wp++;
    }
    setDataLength(getLiveCount());
    compacted();
  }

  [[nodiscard]] bool rehashOnFull(JSContext* cx) {
    MOZ_ASSERT(getDataLength() == getDataCapacity());

    // If the hashTable is more than 1/4 deleted data, simply rehash in
    // place to free up some space. Otherwise, grow the table.
    uint32_t newHashShift = getLiveCount() >= getDataCapacity() * 0.75
                                ? getHashShift() - 1
                                : getHashShift();
    return rehash(cx, newHashShift);
  }

  /*
   * Grow, shrink, or compact both the hash table and data array.
   *
   * On success, this returns true, dataLength == liveCount, and there are no
   * empty elements in data[0:dataLength]. On allocation failure, this
   * leaves everything as it was and returns false.
   */
  [[nodiscard]] bool rehash(JSContext* cx, uint32_t newHashShift) {
    // If the size of the table is not changing, rehash in place to avoid
    // allocating memory.
    if (newHashShift == getHashShift()) {
      rehashInPlace();
      return true;
    }

    if (MOZ_UNLIKELY(newHashShift < MinHashShift)) {
      ReportAllocationOverflow(cx);
      return false;
    }

    uint32_t newHashBuckets = hashShiftToNumHashBuckets(newHashShift);
    uint32_t newCapacity = numHashBucketsToDataCapacity(newHashBuckets);

    auto [newData, newHashTable, newHcs, numBytes] =
        allocateBuffer(cx, newCapacity, newHashBuckets);
    if (!newData) {
      return false;
    }

    *newHcs = *getHashCodeScrambler();

    std::uninitialized_fill_n(newHashTable, newHashBuckets, nullptr);

    Data* const oldData = getData();
    const uint32_t oldDataLength = getDataLength();

    Data* wp = newData;
    Data* end = oldData + oldDataLength;
    for (Data* p = oldData; p != end; p++) {
      if (!Ops::isEmpty(Ops::getKey(p->element))) {
        HashNumber h = prepareHash(Ops::getKey(p->element)) >> newHashShift;
        new (wp) Data(std::move(p->element), newHashTable[h]);
        newHashTable[h] = wp;
        wp++;
      }
    }
    MOZ_ASSERT(wp == newData + getLiveCount());

    freeData(cx, oldData, oldDataLength, getDataCapacity(), hashBuckets());

    setHashTable(newHashTable);
    setData(newData);
    setDataLength(getLiveCount());
    setDataCapacity(newCapacity);
    setHashShift(newHashShift);
    setHashCodeScrambler(newHcs);
    MOZ_ASSERT(hashBuckets() == newHashBuckets);

    compacted();
    return true;
  }

  // Change the key of the front entry.
  //
  // This calls Ops::hash on both the current key and the new key. Ops::hash on
  // the current key must return the same hash code as when the entry was added
  // to the table.
  void rekey(Data* entry, const UnbarrieredKey& k) {
    HashNumber oldHash = prepareHash(Ops::getKey(entry->element));
    HashNumber newHash = prepareHash(k);
    reinterpret_cast<UnbarrieredKey&>(Ops::getKeyRef(entry->element)) = k;
    updateHashTableForRekey(entry, oldHash, newHash);
  }
};

}  // namespace detail

class OrderedHashMapObject : public detail::OrderedHashTableObject {};

template <class Key, class Value, class OrderedHashPolicy>
class MOZ_STACK_CLASS OrderedHashMapImpl {
 public:
  class Entry {
    template <class, class>
    friend class detail::OrderedHashTableImpl;
    void operator=(const Entry& rhs) {
      const_cast<Key&>(key) = rhs.key;
      value = rhs.value;
    }

    void operator=(Entry&& rhs) {
      MOZ_ASSERT(this != &rhs, "self-move assignment is prohibited");
      const_cast<Key&>(key) = std::move(rhs.key);
      value = std::move(rhs.value);
    }

   public:
    Entry() = default;
    explicit Entry(const Key& k) : key(k) {}
    template <typename K, typename V>
    Entry(K&& k, V&& v) : key(std::forward<K>(k)), value(std::forward<V>(v)) {}
    Entry(Entry&& rhs) : key(std::move(rhs.key)), value(std::move(rhs.value)) {}

    const Key key{};
    Value value{};

    static constexpr size_t offsetOfKey() { return offsetof(Entry, key); }
    static constexpr size_t offsetOfValue() { return offsetof(Entry, value); }
  };

 private:
  struct MapOps;
  using Impl = detail::OrderedHashTableImpl<Entry, MapOps>;

  struct MapOps : OrderedHashPolicy {
    using KeyType = Key;
    static void makeEmpty(Entry* e) {
      OrderedHashPolicy::makeEmpty(const_cast<Key*>(&e->key));

      // Clear the value. Destroying it is another possibility, but that
      // would complicate class Entry considerably.
      e->value = Value();
    }
    static const Key& getKey(const Entry& e) { return e.key; }
    static Key& getKeyRef(Entry& e) { return const_cast<Key&>(e.key); }
    static void trace(JSTracer* trc, Impl* table, uint32_t index,
                      Entry& entry) {
      table->traceKey(trc, index, entry.key);
      table->traceValue(trc, entry.value);
    }
  };

  Impl impl;

 public:
  using Lookup = typename Impl::Lookup;
  static constexpr size_t SlotCount = Impl::SlotCount;

  explicit OrderedHashMapImpl(OrderedHashMapObject* obj) : impl(obj) {}

  void initSlots() { impl.initSlots(); }
  uint32_t count() const { return impl.count(); }
  bool has(const Lookup& key) const { return impl.has(key); }
  template <typename F>
  [[nodiscard]] bool forEachEntry(F&& f) const {
    return impl.forEachEntry(f);
  }
#ifdef DEBUG
  template <typename F>
  void forEachEntryUpTo(size_t maxCount, F&& f) const {
    impl.forEachEntryUpTo(maxCount, f);
  }
#endif
  Entry* get(const Lookup& key) { return impl.get(key); }
  bool remove(JSContext* cx, const Lookup& key) { return impl.remove(cx, key); }
  void clear(JSContext* cx) { impl.clear(cx); }

  template <typename K, typename V>
  [[nodiscard]] bool put(JSContext* cx, K&& key, V&& value) {
    return impl.put(cx, Entry(std::forward<K>(key), std::forward<V>(value)));
  }

  template <typename K, typename V>
  [[nodiscard]] Entry* getOrAdd(JSContext* cx, K&& key, V&& value) {
    return impl.getOrAdd(cx,
                         Entry(std::forward<K>(key), std::forward<V>(value)));
  }

#ifdef DEBUG
  mozilla::Maybe<HashNumber> hash(const Lookup& key) const {
    return impl.hash(key);
  }
#endif

  template <typename GetNewKey>
  mozilla::Maybe<Key> rekeyOneEntry(Lookup& current, GetNewKey&& getNewKey) {
    // TODO: This is inefficient because we also look up the entry in
    // impl.rekeyOneEntry below.
    const Entry* e = get(current);
    if (!e) {
      return mozilla::Nothing();
    }

    Key newKey = getNewKey(current);
    impl.rekeyOneEntry(current, newKey, Entry(newKey, e->value));
    return mozilla::Some(newKey);
  }

  void initIterator(MapIteratorObject* iter,
                    TableIteratorObject::Kind kind) const {
    impl.initIterator(iter, kind);
  }
  template <typename F>
  bool iteratorNext(MapIteratorObject* iter, F&& f) const {
    return impl.iteratorNext(iter, f);
  }

  void clearNurseryIterators() { impl.clearNurseryIterators(); }
  void relinkNurseryIterator(MapIteratorObject* iter) {
    impl.relinkNurseryIterator(iter);
  }
  void updateIteratorsAfterMove(OrderedHashMapObject* old) {
    impl.updateIteratorsAfterMove(old);
  }
  bool hasNurseryIterators() const { return impl.hasNurseryIterators(); }

  void maybeMoveBufferOnPromotion(Nursery& nursery) {
    return impl.maybeMoveBufferOnPromotion(nursery);
  }

  void trace(JSTracer* trc) { impl.trace(trc); }

  static constexpr size_t offsetOfEntryKey() { return Entry::offsetOfKey(); }
  static constexpr size_t offsetOfImplDataElement() {
    return Impl::offsetOfDataElement();
  }
  static constexpr size_t offsetOfImplDataChain() {
    return Impl::offsetOfDataChain();
  }
  static constexpr size_t sizeofImplData() { return Impl::sizeofData(); }

  size_t sizeOfExcludingObject() const { return impl.sizeOfExcludingObject(); }
};

class OrderedHashSetObject : public detail::OrderedHashTableObject {};

template <class T, class OrderedHashPolicy>
class MOZ_STACK_CLASS OrderedHashSetImpl {
 private:
  struct SetOps;
  using Impl = detail::OrderedHashTableImpl<T, SetOps>;

  struct SetOps : OrderedHashPolicy {
    using KeyType = const T;
    static const T& getKey(const T& v) { return v; }
    static T& getKeyRef(T& e) { return e; }
    static void trace(JSTracer* trc, Impl* table, uint32_t index, T& entry) {
      table->traceKey(trc, index, entry);
    }
  };

  Impl impl;

 public:
  using Lookup = typename Impl::Lookup;
  static constexpr size_t SlotCount = Impl::SlotCount;

  explicit OrderedHashSetImpl(OrderedHashSetObject* obj) : impl(obj) {}

  void initSlots() { impl.initSlots(); }
  uint32_t count() const { return impl.count(); }
  bool has(const Lookup& value) const { return impl.has(value); }
  template <typename F>
  [[nodiscard]] bool forEachEntry(F&& f) const {
    return impl.forEachEntry(f);
  }
#ifdef DEBUG
  template <typename F>
  void forEachEntryUpTo(size_t maxCount, F&& f) const {
    impl.forEachEntryUpTo(maxCount, f);
  }
#endif
  template <typename Input>
  [[nodiscard]] bool put(JSContext* cx, Input&& value) {
    return impl.put(cx, std::forward<Input>(value));
  }
  bool remove(JSContext* cx, const Lookup& value) {
    return impl.remove(cx, value);
  }
  void clear(JSContext* cx) { impl.clear(cx); }

#ifdef DEBUG
  mozilla::Maybe<HashNumber> hash(const Lookup& value) const {
    return impl.hash(value);
  }
#endif

  template <typename GetNewKey>
  mozilla::Maybe<T> rekeyOneEntry(Lookup& current, GetNewKey&& getNewKey) {
    // TODO: This is inefficient because we also look up the entry in
    // impl.rekeyOneEntry below.
    if (!has(current)) {
      return mozilla::Nothing();
    }

    T newKey = getNewKey(current);
    impl.rekeyOneEntry(current, newKey, newKey);
    return mozilla::Some(newKey);
  }

  void initIterator(SetIteratorObject* iter,
                    TableIteratorObject::Kind kind) const {
    impl.initIterator(iter, kind);
  }
  template <typename F>
  bool iteratorNext(SetIteratorObject* iter, F&& f) const {
    return impl.iteratorNext(iter, f);
  }

  void clearNurseryIterators() { impl.clearNurseryIterators(); }
  void relinkNurseryIterator(SetIteratorObject* iter) {
    impl.relinkNurseryIterator(iter);
  }
  void updateIteratorsAfterMove(OrderedHashSetObject* old) {
    impl.updateIteratorsAfterMove(old);
  }
  bool hasNurseryIterators() const { return impl.hasNurseryIterators(); }

  void maybeMoveBufferOnPromotion(Nursery& nursery) {
    return impl.maybeMoveBufferOnPromotion(nursery);
  }

  void trace(JSTracer* trc) { impl.trace(trc); }

  static constexpr size_t offsetOfEntryKey() { return 0; }
  static constexpr size_t offsetOfImplDataElement() {
    return Impl::offsetOfDataElement();
  }
  static constexpr size_t offsetOfImplDataChain() {
    return Impl::offsetOfDataChain();
  }
  static constexpr size_t sizeofImplData() { return Impl::sizeofData(); }

  size_t sizeOfExcludingObject() const { return impl.sizeOfExcludingObject(); }
};

}  // namespace js

#endif /* builtin_OrderedHashTableObject_h */