src/objects/ordered-hash-table.h

// Copyright 2018 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef V8_OBJECTS_ORDERED_HASH_TABLE_H_
#define V8_OBJECTS_ORDERED_HASH_TABLE_H_

#include "src/base/export-template.h"
#include "src/common/globals.h"
#include "src/objects/fixed-array.h"
#include "src/objects/internal-index.h"
#include "src/objects/js-objects.h"
#include "src/objects/keys.h"
#include "src/objects/smi.h"
#include "src/roots/roots.h"

// Has to be the last include (doesn't have include guards):
#include "src/objects/object-macros.h"

namespace v8 {
namespace internal {

// OrderedHashTable is a HashTable with Object keys that preserves
// insertion order. There are Map and Set interfaces (OrderedHashMap
// and OrderedHashTable, below). It is meant to be used by JSMap/JSSet.
//
// Only Object keys are supported, with Object::SameValueZero() used as the
// equality operator and Object::GetHash() for the hash function.
//
// Based on the "Deterministic Hash Table" as described by Jason Orendorff at
// https://wiki.mozilla.org/User:Jorend/Deterministic_hash_tables
// Originally attributed to Tyler Close.
//
// Memory layout:
//   [0] : Prefix
//   [kPrefixSize]: element count
//   [kPrefixSize + 1]: deleted element count
//   [kPrefixSize + 2]: bucket count
//   [kPrefixSize + 3..(kPrefixSize + 3 + NumberOfBuckets() - 1)]: "hash table",
//                            where each item is an offset into the
//                            data table (see below) where the first
//                            item in this bucket is stored.
//   [kPrefixSize + 3 + NumberOfBuckets()..length]: "data table", an
//                            array of length Capacity() * kEntrySize,
//                            where the first entrysize items are
//                            handled by the derived class and the
//                            item at kChainOffset is another entry
//                            into the data table indicating the next
//                            entry in this hash bucket.
//
// When we transition the table to a new version we obsolete it and reuse parts
// of the memory to store information how to transition an iterator to the new
// table:
//
// Memory layout for obsolete table:
//   [0] : Prefix
//   [kPrefixSize + 0]: Next newer table
//   [kPrefixSize + 1]: deleted element count or kClearedTableSentinel if
//                      the table was cleared
//   [kPrefixSize + 2]: bucket count
//   [kPrefixSize + 3..(kPrefixSize + 3 + NumberOfDeletedElements() - 1)]:
//                      The indexes of the removed holes. This part is only
//                      usable for non-cleared tables, as clearing removes the
//                      deleted elements count.
//   [kPrefixSize + 3 + NumberOfDeletedElements()..length]: Not used
template <class Derived, int entrysize>
class OrderedHashTable : public FixedArray {
 public:
  // Returns an OrderedHashTable (possibly |table|) with enough space
  // to add at least one new element.
  template <typename IsolateT>
  static MaybeHandle<Derived> EnsureGrowable(IsolateT* isolate,
                                             Handle<Derived> table);

  // Returns an OrderedHashTable (possibly |table|) that's shrunken
  // if possible.
  static Handle<Derived> Shrink(Isolate* isolate, Handle<Derived> table);

  // Returns a new empty OrderedHashTable and records the clearing so that
  // existing iterators can be updated.
  static Handle<Derived> Clear(Isolate* isolate, Handle<Derived> table);

  // Returns true if the OrderedHashTable contains the key
  static bool HasKey(Isolate* isolate, Derived table, Object key);

  // Returns whether a potential key |k| returned by KeyAt is a real
  // key (meaning that it is not a hole).
  static inline bool IsKey(ReadOnlyRoots roots, Object k);

  // Returns a true value if the OrderedHashTable contains the key and
  // the key has been deleted. This does not shrink the table.
  static bool Delete(Isolate* isolate, Derived table, Object key);

  InternalIndex FindEntry(Isolate* isolate, Object key);

  int NumberOfElements() const {
    return Smi::ToInt(get(NumberOfElementsIndex()));
  }

  int NumberOfDeletedElements() const {
    return Smi::ToInt(get(NumberOfDeletedElementsIndex()));
  }

  // Returns the number of contiguous entries in the data table, starting at 0,
  // that either are real entries or have been deleted.
  int UsedCapacity() const {
    return NumberOfElements() + NumberOfDeletedElements();
  }

  int Capacity() { return NumberOfBuckets() * kLoadFactor; }

  int NumberOfBuckets() const {
    return Smi::ToInt(get(NumberOfBucketsIndex()));
  }

  InternalIndex::Range IterateEntries() {
    return InternalIndex::Range(UsedCapacity());
  }

  // use IsKey to check if this is a deleted entry.
  Object KeyAt(InternalIndex entry) {
    DCHECK_LT(entry.as_int(), this->UsedCapacity());
    return get(EntryToIndex(entry));
  }

  // Similar to KeyAt, but indicates whether the given entry is valid
  // (not deleted one)
  inline bool ToKey(ReadOnlyRoots roots, InternalIndex entry, Object* out_key);

  bool IsObsolete() { return !get(NextTableIndex()).IsSmi(); }

  // The next newer table. This is only valid if the table is obsolete.
  Derived NextTable() { return Derived::cast(get(NextTableIndex())); }

  // When the table is obsolete we store the indexes of the removed holes.
  int RemovedIndexAt(int index) {
    return Smi::ToInt(get(RemovedHolesIndex() + index));
  }

  // The extra +1 is for linking the bucket chains together.
  static const int kEntrySize = entrysize + 1;
  static const int kEntrySizeWithoutChain = entrysize;
  static const int kChainOffset = entrysize;

  static const int kNotFound = -1;
  // The minimum capacity. Note that despite this value, 0 is also a permitted
  // capacity, indicating a table without any storage for elements.
  static const int kInitialCapacity = 4;

  static constexpr int PrefixIndex() { return 0; }

  static constexpr int NumberOfElementsIndex() { return Derived::kPrefixSize; }

  // The next table is stored at the same index as the nof elements.
  static constexpr int NextTableIndex() { return NumberOfElementsIndex(); }

  static constexpr int NumberOfDeletedElementsIndex() {
    return NumberOfElementsIndex() + 1;
  }

  static constexpr int NumberOfBucketsIndex() {
    return NumberOfDeletedElementsIndex() + 1;
  }

  static constexpr int HashTableStartIndex() {
    return NumberOfBucketsIndex() + 1;
  }

  static constexpr int RemovedHolesIndex() { return HashTableStartIndex(); }

  static constexpr int NumberOfElementsOffset() {
    return FixedArray::OffsetOfElementAt(NumberOfElementsIndex());
  }

  static constexpr int NextTableOffset() {
    return FixedArray::OffsetOfElementAt(NextTableIndex());
  }

  static constexpr int NumberOfDeletedElementsOffset() {
    return FixedArray::OffsetOfElementAt(NumberOfDeletedElementsIndex());
  }

  static constexpr int NumberOfBucketsOffset() {
    return FixedArray::OffsetOfElementAt(NumberOfBucketsIndex());
  }

  static constexpr int HashTableStartOffset() {
    return FixedArray::OffsetOfElementAt(HashTableStartIndex());
  }

  static const int kLoadFactor = 2;

  // NumberOfDeletedElements is set to kClearedTableSentinel when
  // the table is cleared, which allows iterator transitions to
  // optimize that case.
  static const int kClearedTableSentinel = -1;
  static constexpr int MaxCapacity() {
    return (FixedArray::kMaxLength - HashTableStartIndex()) /
           (1 + (kEntrySize * kLoadFactor));
  }

 protected:
  // Returns an OrderedHashTable with a capacity of at least |capacity|.
  template <typename IsolateT>
  static MaybeHandle<Derived> Allocate(
      IsolateT* isolate, int capacity,
      AllocationType allocation = AllocationType::kYoung);

  static MaybeHandle<Derived> AllocateEmpty(Isolate* isolate,
                                            AllocationType allocation,
                                            RootIndex root_ndex);

  template <typename IsolateT>
  static MaybeHandle<Derived> Rehash(IsolateT* isolate, Handle<Derived> table);
  template <typename IsolateT>
  static MaybeHandle<Derived> Rehash(IsolateT* isolate, Handle<Derived> table,
                                     int new_capacity);

  int HashToEntryRaw(int hash) {
    int bucket = HashToBucket(hash);
    Object entry = this->get(HashTableStartIndex() + bucket);
    int entry_int = Smi::ToInt(entry);
    DCHECK(entry_int == kNotFound || entry_int >= 0);
    return entry_int;
  }

  int NextChainEntryRaw(int entry) {
    DCHECK_LT(entry, this->UsedCapacity());
    Object next_entry = get(EntryToIndexRaw(entry) + kChainOffset);
    int next_entry_int = Smi::ToInt(next_entry);
    DCHECK(next_entry_int == kNotFound || next_entry_int >= 0);
    return next_entry_int;
  }

  // Returns an index into |this| for the given entry.
  int EntryToIndexRaw(int entry) {
    return HashTableStartIndex() + NumberOfBuckets() + (entry * kEntrySize);
  }

  int EntryToIndex(InternalIndex entry) {
    return EntryToIndexRaw(entry.as_int());
  }

  int HashToBucket(int hash) { return hash & (NumberOfBuckets() - 1); }

  void SetNumberOfBuckets(int num) {
    set(NumberOfBucketsIndex(), Smi::FromInt(num));
  }

  void SetNumberOfElements(int num) {
    set(NumberOfElementsIndex(), Smi::FromInt(num));
  }

  void SetNumberOfDeletedElements(int num) {
    set(NumberOfDeletedElementsIndex(), Smi::FromInt(num));
  }


  void SetNextTable(Derived next_table) { set(NextTableIndex(), next_table); }

  void SetRemovedIndexAt(int index, int removed_index) {
    return set(RemovedHolesIndex() + index, Smi::FromInt(removed_index));
  }

  OBJECT_CONSTRUCTORS(OrderedHashTable, FixedArray);

 private:
  friend class OrderedNameDictionaryHandler;
};

class V8_EXPORT_PRIVATE OrderedHashSet
    : public OrderedHashTable<OrderedHashSet, 1> {
  using Base = OrderedHashTable<OrderedHashSet, 1>;

 public:
  DECL_CAST(OrderedHashSet)
  DECL_PRINTER(OrderedHashSet)

  static MaybeHandle<OrderedHashSet> Add(Isolate* isolate,
                                         Handle<OrderedHashSet> table,
                                         Handle<Object> value);
  static Handle<FixedArray> ConvertToKeysArray(Isolate* isolate,
                                               Handle<OrderedHashSet> table,
                                               GetKeysConversion convert);
  static MaybeHandle<OrderedHashSet> Rehash(Isolate* isolate,
                                            Handle<OrderedHashSet> table,
                                            int new_capacity);
  static MaybeHandle<OrderedHashSet> Rehash(Isolate* isolate,
                                            Handle<OrderedHashSet> table);
  template <typename IsolateT>
  static MaybeHandle<OrderedHashSet> Allocate(
      IsolateT* isolate, int capacity,
      AllocationType allocation = AllocationType::kYoung);

  static MaybeHandle<OrderedHashSet> AllocateEmpty(
      Isolate* isolate, AllocationType allocation = AllocationType::kReadOnly);

  static HeapObject GetEmpty(ReadOnlyRoots ro_roots);
  static inline Handle<Map> GetMap(ReadOnlyRoots roots);
  static inline bool Is(Handle<HeapObject> table);
  static const int kPrefixSize = 0;

  OBJECT_CONSTRUCTORS(OrderedHashSet, OrderedHashTable<OrderedHashSet, 1>);
};

class V8_EXPORT_PRIVATE OrderedHashMap
    : public OrderedHashTable<OrderedHashMap, 2> {
  using Base = OrderedHashTable<OrderedHashMap, 2>;

 public:
  DECL_CAST(OrderedHashMap)
  DECL_PRINTER(OrderedHashMap)

  // Returns a value if the OrderedHashMap contains the key, otherwise
  // returns undefined.
  static MaybeHandle<OrderedHashMap> Add(Isolate* isolate,
                                         Handle<OrderedHashMap> table,
                                         Handle<Object> key,
                                         Handle<Object> value);

  template <typename IsolateT>
  static MaybeHandle<OrderedHashMap> Allocate(
      IsolateT* isolate, int capacity,
      AllocationType allocation = AllocationType::kYoung);

  static MaybeHandle<OrderedHashMap> AllocateEmpty(
      Isolate* isolate, AllocationType allocation = AllocationType::kReadOnly);

  static MaybeHandle<OrderedHashMap> Rehash(Isolate* isolate,
                                            Handle<OrderedHashMap> table,
                                            int new_capacity);
  static MaybeHandle<OrderedHashMap> Rehash(Isolate* isolate,
                                            Handle<OrderedHashMap> table);

  void SetEntry(InternalIndex entry, Object key, Object value);

  Object ValueAt(InternalIndex entry);

  // This takes and returns raw Address values containing tagged Object
  // pointers because it is called via ExternalReference.
  static Address GetHash(Isolate* isolate, Address raw_key);

  static HeapObject GetEmpty(ReadOnlyRoots ro_roots);
  static inline Handle<Map> GetMap(ReadOnlyRoots roots);
  static inline bool Is(Handle<HeapObject> table);

  static const int kValueOffset = 1;
  static const int kPrefixSize = 0;

  OBJECT_CONSTRUCTORS(OrderedHashMap, OrderedHashTable<OrderedHashMap, 2>);
};

// This is similar to the OrderedHashTable, except for the memory
// layout where we use byte instead of Smi. The max capacity of this
// is only 254, we transition to an OrderedHashTable beyond that
// limit.
//
// Each bucket and chain value is a byte long. The padding exists so
// that the DataTable entries start aligned. A bucket or chain value
// of 255 is used to denote an unknown entry.
//
// The prefix size is calculated as the kPrefixSize * kTaggedSize.
//
// Memory layout: [ Prefix ] [ Header ]  [ Padding ] [ DataTable ] [ HashTable ]
// [ Chains ]
//
// The index are represented as bytes, on a 64 bit machine with
// kEntrySize = 1, capacity = 4 and entries = 2:
//
// [ 0 ] : Prefix
//
// Note: For the sake of brevity, the following start with index 0
// but, they actually start from kPrefixSize * kTaggedSize to
// account for the the prefix.
//
// [ Header ]  :
//    [0] : Number of elements
//    [1] : Number of deleted elements
//    [2] : Number of buckets
//
// [ Padding ] :
//    [3 .. 7] : Padding
//
// [ DataTable ] :
//    [8  .. 15] : Entry 1
//    [16 .. 23] : Entry 2
//    [24 .. 31] : empty
//    [32 .. 39] : empty
//
// [ HashTable ] :
//    [40] : First chain-link for bucket 1
//    [41] : empty
//
// [ Chains ] :
//    [42] : Next chain link for bucket 1
//    [43] : empty
//    [44] : empty
//    [45] : empty
//
template <class Derived>
class SmallOrderedHashTable : public HeapObject {
 public:
  // Offset points to a relative location in the table
  using Offset = int;

  // ByteIndex points to a index in the table that needs to be
  // converted to an Offset.
  using ByteIndex = int;

  void Initialize(Isolate* isolate, int capacity);

  static Handle<Derived> Allocate(
      Isolate* isolate, int capacity,
      AllocationType allocation = AllocationType::kYoung);

  // Returns a true if the OrderedHashTable contains the key
  bool HasKey(Isolate* isolate, Handle<Object> key);

  // Returns a true value if the table contains the key and
  // the key has been deleted. This does not shrink the table.
  static bool Delete(Isolate* isolate, Derived table, Object key);

  // Returns an SmallOrderedHashTable (possibly |table|) with enough
  // space to add at least one new element. Returns empty handle if
  // we've already reached MaxCapacity.
  static MaybeHandle<Derived> Grow(Isolate* isolate, Handle<Derived> table);

  InternalIndex FindEntry(Isolate* isolate, Object key);
  static Handle<Derived> Shrink(Isolate* isolate, Handle<Derived> table);

  // Iterates only fields in the DataTable.
  class BodyDescriptor;

  // Returns total size in bytes required for a table of given
  // capacity.
  static int SizeFor(int capacity) {
    DCHECK_GE(capacity, kMinCapacity);
    DCHECK_LE(capacity, kMaxCapacity);

    int data_table_size = DataTableSizeFor(capacity);
    int hash_table_size = capacity / kLoadFactor;
    int chain_table_size = capacity;
    int total_size = DataTableStartOffset() + data_table_size +
                     hash_table_size + chain_table_size;

    return RoundUp(total_size, kTaggedSize);
  }

  // Returns the number elements that can fit into the allocated table.
  int Capacity() const {
    int capacity = NumberOfBuckets() * kLoadFactor;
    DCHECK_GE(capacity, kMinCapacity);
    DCHECK_LE(capacity, kMaxCapacity);

    return capacity;
  }

  // Returns the number elements that are present in the table.
  int NumberOfElements() const {
    int nof_elements = getByte(NumberOfElementsOffset(), 0);
    DCHECK_LE(nof_elements, Capacity());

    return nof_elements;
  }

  int NumberOfDeletedElements() const {
    int nof_deleted_elements = getByte(NumberOfDeletedElementsOffset(), 0);
    DCHECK_LE(nof_deleted_elements, Capacity());

    return nof_deleted_elements;
  }

  int NumberOfBuckets() const { return getByte(NumberOfBucketsOffset(), 0); }

  V8_INLINE Object KeyAt(InternalIndex entry) const;

  InternalIndex::Range IterateEntries() {
    return InternalIndex::Range(UsedCapacity());
  }

  DECL_VERIFIER(SmallOrderedHashTable)

  static const int kMinCapacity = 4;
  static const byte kNotFound = 0xFF;

  // We use the value 255 to indicate kNotFound for chain and bucket
  // values, which means that this value can't be used a valid
  // index.
  static const int kMaxCapacity = 254;
  STATIC_ASSERT(kMaxCapacity < kNotFound);

  // The load factor is used to derive the number of buckets from
  // capacity during Allocation. We also depend on this to calaculate
  // the capacity from number of buckets after allocation. If we
  // decide to change kLoadFactor to something other than 2, capacity
  // should be stored as another field of this object.
  static const int kLoadFactor = 2;

  // Our growth strategy involves doubling the capacity until we reach
  // kMaxCapacity, but since the kMaxCapacity is always less than 256,
  // we will never fully utilize this table. We special case for 256,
  // by changing the new capacity to be kMaxCapacity in
  // SmallOrderedHashTable::Grow.
  static const int kGrowthHack = 256;

 protected:
  static Handle<Derived> Rehash(Isolate* isolate, Handle<Derived> table,
                                int new_capacity);

  void SetDataEntry(int entry, int relative_index, Object value);

  // TODO(gsathya): Calculate all the various possible values for this
  // at compile time since capacity can only be 4 different values.
  Offset GetBucketsStartOffset() const {
    int capacity = Capacity();
    int data_table_size = DataTableSizeFor(capacity);
    return DataTableStartOffset() + data_table_size;
  }

  Address GetHashTableStartAddress(int capacity) const {
    return field_address(DataTableStartOffset() + DataTableSizeFor(capacity));
  }

  void SetFirstEntry(int bucket, byte value) {
    DCHECK_LE(static_cast<unsigned>(bucket), NumberOfBuckets());
    setByte(GetBucketsStartOffset(), bucket, value);
  }

  int GetFirstEntry(int bucket) const {
    DCHECK_LE(static_cast<unsigned>(bucket), NumberOfBuckets());
    return getByte(GetBucketsStartOffset(), bucket);
  }

  // TODO(gsathya): Calculate all the various possible values for this
  // at compile time since capacity can only be 4 different values.
  Offset GetChainTableOffset() const {
    int nof_buckets = NumberOfBuckets();
    int capacity = nof_buckets * kLoadFactor;
    DCHECK_EQ(Capacity(), capacity);

    int data_table_size = DataTableSizeFor(capacity);
    int hash_table_size = nof_buckets;
    return DataTableStartOffset() + data_table_size + hash_table_size;
  }

  void SetNextEntry(int entry, int next_entry) {
    DCHECK_LT(static_cast<unsigned>(entry), Capacity());
    DCHECK_GE(static_cast<unsigned>(next_entry), 0);
    DCHECK(next_entry <= Capacity() || next_entry == kNotFound);
    setByte(GetChainTableOffset(), entry, next_entry);
  }

  int GetNextEntry(int entry) const {
    DCHECK_LT(entry, Capacity());
    return getByte(GetChainTableOffset(), entry);
  }

  V8_INLINE Object GetDataEntry(int entry, int relative_index);

  int HashToBucket(int hash) const { return hash & (NumberOfBuckets() - 1); }

  int HashToFirstEntry(int hash) const {
    int bucket = HashToBucket(hash);
    int entry = GetFirstEntry(bucket);
    DCHECK(entry < Capacity() || entry == kNotFound);
    return entry;
  }

  void SetNumberOfBuckets(int num) { setByte(NumberOfBucketsOffset(), 0, num); }

  void SetNumberOfElements(int num) {
    DCHECK_LE(static_cast<unsigned>(num), Capacity());
    setByte(NumberOfElementsOffset(), 0, num);
  }

  void SetNumberOfDeletedElements(int num) {
    DCHECK_LE(static_cast<unsigned>(num), Capacity());
    setByte(NumberOfDeletedElementsOffset(), 0, num);
  }

  static constexpr Offset PrefixOffset() { return kHeaderSize; }

  static constexpr Offset NumberOfElementsOffset() {
    return PrefixOffset() + (Derived::kPrefixSize * kTaggedSize);
  }

  static constexpr Offset NumberOfDeletedElementsOffset() {
    return NumberOfElementsOffset() + kOneByteSize;
  }

  static constexpr Offset NumberOfBucketsOffset() {
    return NumberOfDeletedElementsOffset() + kOneByteSize;
  }

  static constexpr Offset PaddingOffset() {
    return NumberOfBucketsOffset() + kOneByteSize;
  }

  static constexpr size_t PaddingSize() {
    return RoundUp<kTaggedSize>(PaddingOffset()) - PaddingOffset();
  }

  static constexpr Offset DataTableStartOffset() {
    return PaddingOffset() + PaddingSize();
  }

  static constexpr int DataTableSizeFor(int capacity) {
    return capacity * Derived::kEntrySize * kTaggedSize;
  }

  // This is used for accessing the non |DataTable| part of the
  // structure.
  byte getByte(Offset offset, ByteIndex index) const {
    DCHECK(offset < DataTableStartOffset() ||
           offset >= GetBucketsStartOffset());
    return ReadField<byte>(offset + (index * kOneByteSize));
  }

  void setByte(Offset offset, ByteIndex index, byte value) {
    DCHECK(offset < DataTableStartOffset() ||
           offset >= GetBucketsStartOffset());
    WriteField<byte>(offset + (index * kOneByteSize), value);
  }

  Offset GetDataEntryOffset(int entry, int relative_index) const {
    DCHECK_LT(entry, Capacity());
    int offset_in_datatable = entry * Derived::kEntrySize * kTaggedSize;
    int offset_in_entry = relative_index * kTaggedSize;
    return DataTableStartOffset() + offset_in_datatable + offset_in_entry;
  }

  int UsedCapacity() const {
    int used = NumberOfElements() + NumberOfDeletedElements();
    DCHECK_LE(used, Capacity());

    return used;
  }

 private:
  friend class OrderedHashMapHandler;
  friend class OrderedHashSetHandler;
  friend class OrderedNameDictionaryHandler;
  friend class CodeStubAssembler;

  OBJECT_CONSTRUCTORS(SmallOrderedHashTable, HeapObject);
};

class SmallOrderedHashSet : public SmallOrderedHashTable<SmallOrderedHashSet> {
 public:
  DECL_CAST(SmallOrderedHashSet)

  DECL_PRINTER(SmallOrderedHashSet)
  EXPORT_DECL_VERIFIER(SmallOrderedHashSet)

  static const int kKeyIndex = 0;
  static const int kEntrySize = 1;
  static const int kPrefixSize = 0;

  // Adds |value| to |table|, if the capacity isn't enough, a new
  // table is created. The original |table| is returned if there is
  // capacity to store |value| otherwise the new table is returned.
  V8_EXPORT_PRIVATE static MaybeHandle<SmallOrderedHashSet> Add(
      Isolate* isolate, Handle<SmallOrderedHashSet> table, Handle<Object> key);
  V8_EXPORT_PRIVATE static bool Delete(Isolate* isolate,
                                       SmallOrderedHashSet table, Object key);
  V8_EXPORT_PRIVATE bool HasKey(Isolate* isolate, Handle<Object> key);

  static inline bool Is(Handle<HeapObject> table);
  static inline Handle<Map> GetMap(ReadOnlyRoots roots);
  static Handle<SmallOrderedHashSet> Rehash(Isolate* isolate,
                                            Handle<SmallOrderedHashSet> table,
                                            int new_capacity);
  OBJECT_CONSTRUCTORS(SmallOrderedHashSet,
                      SmallOrderedHashTable<SmallOrderedHashSet>);
};

STATIC_ASSERT(kSmallOrderedHashSetMinCapacity ==
              SmallOrderedHashSet::kMinCapacity);

class SmallOrderedHashMap : public SmallOrderedHashTable<SmallOrderedHashMap> {
 public:
  DECL_CAST(SmallOrderedHashMap)

  DECL_PRINTER(SmallOrderedHashMap)
  EXPORT_DECL_VERIFIER(SmallOrderedHashMap)

  static const int kKeyIndex = 0;
  static const int kValueIndex = 1;
  static const int kEntrySize = 2;
  static const int kPrefixSize = 0;

  // Adds |value| to |table|, if the capacity isn't enough, a new
  // table is created. The original |table| is returned if there is
  // capacity to store |value| otherwise the new table is returned.
  V8_EXPORT_PRIVATE static MaybeHandle<SmallOrderedHashMap> Add(
      Isolate* isolate, Handle<SmallOrderedHashMap> table, Handle<Object> key,
      Handle<Object> value);
  V8_EXPORT_PRIVATE static bool Delete(Isolate* isolate,
                                       SmallOrderedHashMap table, Object key);
  V8_EXPORT_PRIVATE bool HasKey(Isolate* isolate, Handle<Object> key);
  static inline bool Is(Handle<HeapObject> table);
  static inline Handle<Map> GetMap(ReadOnlyRoots roots);

  static Handle<SmallOrderedHashMap> Rehash(Isolate* isolate,
                                            Handle<SmallOrderedHashMap> table,
                                            int new_capacity);

  OBJECT_CONSTRUCTORS(SmallOrderedHashMap,
                      SmallOrderedHashTable<SmallOrderedHashMap>);
};

STATIC_ASSERT(kSmallOrderedHashMapMinCapacity ==
              SmallOrderedHashMap::kMinCapacity);

// TODO(gsathya): Rename this to OrderedHashTable, after we rename
// OrderedHashTable to LargeOrderedHashTable. Also set up a
// OrderedHashSetBase class as a base class for the two tables and use
// that instead of a HeapObject here.
template <class SmallTable, class LargeTable>
class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE) OrderedHashTableHandler {
 public:
  using Entry = int;

  static MaybeHandle<HeapObject> Allocate(Isolate* isolate, int capacity);
  static bool Delete(Isolate* isolate, Handle<HeapObject> table,
                     Handle<Object> key);
  static bool HasKey(Isolate* isolate, Handle<HeapObject> table,
                     Handle<Object> key);

  // TODO(gsathya): Move this to OrderedHashTable
  static const int OrderedHashTableMinSize =
      SmallOrderedHashTable<SmallTable>::kGrowthHack << 1;
};

extern template class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE)
    OrderedHashTableHandler<SmallOrderedHashMap, OrderedHashMap>;

class V8_EXPORT_PRIVATE OrderedHashMapHandler
    : public OrderedHashTableHandler<SmallOrderedHashMap, OrderedHashMap> {
 public:
  static MaybeHandle<HeapObject> Add(Isolate* isolate, Handle<HeapObject> table,
                                     Handle<Object> key, Handle<Object> value);
  static MaybeHandle<OrderedHashMap> AdjustRepresentation(
      Isolate* isolate, Handle<SmallOrderedHashMap> table);
};

extern template class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE)
    OrderedHashTableHandler<SmallOrderedHashSet, OrderedHashSet>;

class V8_EXPORT_PRIVATE OrderedHashSetHandler
    : public OrderedHashTableHandler<SmallOrderedHashSet, OrderedHashSet> {
 public:
  static MaybeHandle<HeapObject> Add(Isolate* isolate, Handle<HeapObject> table,
                                     Handle<Object> key);
  static MaybeHandle<OrderedHashSet> AdjustRepresentation(
      Isolate* isolate, Handle<SmallOrderedHashSet> table);
};

class V8_EXPORT_PRIVATE OrderedNameDictionary
    : public OrderedHashTable<OrderedNameDictionary, 3> {
  using Base = OrderedHashTable<OrderedNameDictionary, 3>;

 public:
  DECL_CAST(OrderedNameDictionary)
  DECL_PRINTER(OrderedNameDictionary)

  template <typename IsolateT>
  static MaybeHandle<OrderedNameDictionary> Add(
      IsolateT* isolate, Handle<OrderedNameDictionary> table, Handle<Name> key,
      Handle<Object> value, PropertyDetails details);

  void SetEntry(InternalIndex entry, Object key, Object value,
                PropertyDetails details);

  template <typename IsolateT>
  InternalIndex FindEntry(IsolateT* isolate, Object key);

  // This is to make the interfaces of NameDictionary::FindEntry and
  // OrderedNameDictionary::FindEntry compatible.
  // TODO(emrich) clean this up: NameDictionary uses Handle<Object>
  // for FindEntry keys due to its Key typedef, but that's also used
  // for adding, where we do need handles.
  template <typename IsolateT>
  InternalIndex FindEntry(IsolateT* isolate, Handle<Object> key) {
    return FindEntry(isolate, *key);
  }

  static Handle<OrderedNameDictionary> DeleteEntry(
      Isolate* isolate, Handle<OrderedNameDictionary> table,
      InternalIndex entry);

  template <typename IsolateT>
  static MaybeHandle<OrderedNameDictionary> Allocate(
      IsolateT* isolate, int capacity,
      AllocationType allocation = AllocationType::kYoung);

  static MaybeHandle<OrderedNameDictionary> AllocateEmpty(
      Isolate* isolate, AllocationType allocation = AllocationType::kReadOnly);

  template <typename IsolateT>
  static MaybeHandle<OrderedNameDictionary> Rehash(
      IsolateT* isolate, Handle<OrderedNameDictionary> table, int new_capacity);

  // Returns the value for entry.
  inline Object ValueAt(InternalIndex entry);

  // Like KeyAt, but casts to Name
  inline Name NameAt(InternalIndex entry);

  // Set the value for entry.
  inline void ValueAtPut(InternalIndex entry, Object value);

  // Returns the property details for the property at entry.
  inline PropertyDetails DetailsAt(InternalIndex entry);

  // Set the details for entry.
  inline void DetailsAtPut(InternalIndex entry, PropertyDetails value);

  inline void SetHash(int hash);
  inline int Hash();

  static HeapObject GetEmpty(ReadOnlyRoots ro_roots);
  static inline Handle<Map> GetMap(ReadOnlyRoots roots);
  static inline bool Is(Handle<HeapObject> table);

  static const int kValueOffset = 1;
  static const int kPropertyDetailsOffset = 2;
  static const int kPrefixSize = 1;

  static constexpr int HashIndex() { return PrefixIndex(); }

  static const bool kIsOrderedDictionaryType = true;

  OBJECT_CONSTRUCTORS(OrderedNameDictionary,
                      OrderedHashTable<OrderedNameDictionary, 3>);
};

extern template class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE)
    OrderedHashTableHandler<SmallOrderedNameDictionary, OrderedNameDictionary>;

class V8_EXPORT_PRIVATE OrderedNameDictionaryHandler
    : public OrderedHashTableHandler<SmallOrderedNameDictionary,
                                     OrderedNameDictionary> {
 public:
  static MaybeHandle<HeapObject> Add(Isolate* isolate, Handle<HeapObject> table,
                                     Handle<Name> key, Handle<Object> value,
                                     PropertyDetails details);
  static Handle<HeapObject> Shrink(Isolate* isolate, Handle<HeapObject> table);

  static Handle<HeapObject> DeleteEntry(Isolate* isolate,
                                        Handle<HeapObject> table,
                                        InternalIndex entry);
  static InternalIndex FindEntry(Isolate* isolate, HeapObject table, Name key);
  static void SetEntry(HeapObject table, InternalIndex entry, Object key,
                       Object value, PropertyDetails details);

  // Returns the value for entry.
  static Object ValueAt(HeapObject table, InternalIndex entry);

  // Set the value for entry.
  static void ValueAtPut(HeapObject table, InternalIndex entry, Object value);

  // Returns the property details for the property at entry.
  static PropertyDetails DetailsAt(HeapObject table, InternalIndex entry);

  // Set the details for entry.
  static void DetailsAtPut(HeapObject table, InternalIndex entry,
                           PropertyDetails value);

  static Name KeyAt(HeapObject table, InternalIndex entry);

  static void SetHash(HeapObject table, int hash);
  static int Hash(HeapObject table);

  static int NumberOfElements(HeapObject table);
  static int Capacity(HeapObject table);

 protected:
  static MaybeHandle<OrderedNameDictionary> AdjustRepresentation(
      Isolate* isolate, Handle<SmallOrderedNameDictionary> table);
};

class SmallOrderedNameDictionary
    : public SmallOrderedHashTable<SmallOrderedNameDictionary> {
 public:
  DECL_CAST(SmallOrderedNameDictionary)

  DECL_PRINTER(SmallOrderedNameDictionary)
  DECL_VERIFIER(SmallOrderedNameDictionary)

  // Returns the value for entry.
  inline Object ValueAt(InternalIndex entry);

  static Handle<SmallOrderedNameDictionary> Rehash(
      Isolate* isolate, Handle<SmallOrderedNameDictionary> table,
      int new_capacity);

  V8_EXPORT_PRIVATE static Handle<SmallOrderedNameDictionary> DeleteEntry(
      Isolate* isolate, Handle<SmallOrderedNameDictionary> table,
      InternalIndex entry);

  // Set the value for entry.
  inline void ValueAtPut(InternalIndex entry, Object value);

  // Returns the property details for the property at entry.
  inline PropertyDetails DetailsAt(InternalIndex entry);

  // Set the details for entry.
  inline void DetailsAtPut(InternalIndex entry, PropertyDetails value);

  inline void SetHash(int hash);
  inline int Hash();

  static const int kKeyIndex = 0;
  static const int kValueIndex = 1;
  static const int kPropertyDetailsIndex = 2;
  static const int kEntrySize = 3;
  static const int kPrefixSize = 1;

  // Adds |value| to |table|, if the capacity isn't enough, a new
  // table is created. The original |table| is returned if there is
  // capacity to store |value| otherwise the new table is returned.
  V8_EXPORT_PRIVATE static MaybeHandle<SmallOrderedNameDictionary> Add(
      Isolate* isolate, Handle<SmallOrderedNameDictionary> table,
      Handle<Name> key, Handle<Object> value, PropertyDetails details);

  V8_EXPORT_PRIVATE void SetEntry(InternalIndex entry, Object key, Object value,
                                  PropertyDetails details);

  static inline Handle<Map> GetMap(ReadOnlyRoots roots);
  static inline bool Is(Handle<HeapObject> table);

  OBJECT_CONSTRUCTORS(SmallOrderedNameDictionary,
                      SmallOrderedHashTable<SmallOrderedNameDictionary>);
};

}  // namespace internal
}  // namespace v8

#include "src/objects/object-macros-undef.h"

#endif  // V8_OBJECTS_ORDERED_HASH_TABLE_H_