ordered-hash-table.cc

Go to the documentation of this file.

// 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.
 
#include "src/objects/ordered-hash-table.h"
 
#include "src/execution/isolate.h"
#include "src/heap/heap-inl.h"
#include "src/objects/internal-index.h"
#include "src/objects/js-collection-inl.h"
#include "src/objects/objects-inl.h"
#include "src/objects/ordered-hash-table-inl.h"
#include "src/roots/roots.h"
 
namespace v8 {
namespace internal {
 
template <class Derived, int entrysize>
MaybeHandle<Derived> OrderedHashTable<Derived, entrysize>::Allocate(
    Isolate* isolate, int capacity, AllocationType allocation) {
  // Capacity must be a power of two, since we depend on being able
  // to divide and multiple by 2 (kLoadFactor) to derive capacity
  // from number of buckets. If we decide to change kLoadFactor
  // to something other than 2, capacity should be stored as another
  // field of this object.
  capacity =
      base::bits::RoundUpToPowerOfTwo32(std::max({kInitialCapacity, capacity}));
  if (capacity > MaxCapacity()) {
    // Throw RangeError with a generic message.
    THROW_NEW_ERROR_RETURN_VALUE(
        isolate,
        NewRangeError(MessageTemplate::kCollectionGrowFailed,
                      isolate->factory()->empty_string()),
        {});
  }
  int num_buckets = capacity / kLoadFactor;
  Handle<FixedArray> backing_store = isolate->factory()->NewFixedArrayWithMap(
      Derived::GetMap(isolate->roots_table()),
      HashTableStartIndex() + num_buckets + (capacity * kEntrySize),
      allocation);
  Handle<Derived> table = Cast<Derived>(backing_store);
  DisallowGarbageCollection no_gc;
  Tagged<Derived> raw_table = *table;
  for (int i = 0; i < num_buckets; ++i) {
    raw_table->set(HashTableStartIndex() + i, Smi::FromInt(kNotFound));
  }
  raw_table->SetNumberOfBuckets(num_buckets);
  raw_table->SetNumberOfElements(0);
  raw_table->SetNumberOfDeletedElements(0);
  return table;
}
 
template <class Derived, int entrysize>
MaybeHandle<Derived> OrderedHashTable<Derived, entrysize>::AllocateEmpty(
    Isolate* isolate, AllocationType allocation, RootIndex root_index) {
  // This is only supposed to be used to create the canonical empty versions
  // of each ordered structure, and should not be used afterwards.
  // Requires that the map has already been set up in the roots table.
  DCHECK(!ReadOnlyRoots(isolate).is_initialized(root_index));
 
  Handle<FixedArray> backing_store = isolate->factory()->NewFixedArrayWithMap(
      Derived::GetMap(isolate->roots_table()), HashTableStartIndex(),
      allocation);
  Handle<Derived> table = Cast<Derived>(backing_store);
  DisallowHandleAllocation no_gc;
  Tagged<Derived> raw_table = *table;
  raw_table->SetNumberOfBuckets(0);
  raw_table->SetNumberOfElements(0);
  raw_table->SetNumberOfDeletedElements(0);
  return table;
}
 
template <class Derived, int entrysize>
template <template <typename> typename HandleType>
  requires(std::is_convertible_v<HandleType<Derived>, DirectHandle<Derived>>)
HandleType<Derived>::MaybeType
OrderedHashTable<Derived, entrysize>::EnsureCapacityForAdding(
    Isolate* isolate, HandleType<Derived> table) {
  DCHECK(!table->IsObsolete());
 
  int nof = table->NumberOfElements();
  int nod = table->NumberOfDeletedElements();
  int capacity = table->Capacity();
  if ((nof + nod) < capacity) return table;
 
  int new_capacity;
  if (capacity == 0) {
    // step from empty to minimum proper size
    new_capacity = kInitialCapacity;
  } else if (nod >= (capacity >> 1)) {
    // Don't need to grow if we can simply clear out deleted entries instead.
    // Note that we can't compact in place, though, so we always allocate
    // a new table.
    new_capacity = capacity;
  } else {
    new_capacity = capacity << 1;
  }
 
  return Derived::Rehash(isolate, table, new_capacity);
}
 
template <class Derived, int entrysize>
template <template <typename> typename HandleType>
  requires(std::is_convertible_v<HandleType<Derived>, DirectHandle<Derived>>)
HandleType<Derived> OrderedHashTable<Derived, entrysize>::Shrink(
    Isolate* isolate, HandleType<Derived> table) {
  DCHECK(!table->IsObsolete());
 
  int nof = table->NumberOfElements();
  int capacity = table->Capacity();
  if (nof >= (capacity >> 2)) return table;
  return Derived::Rehash(isolate, table, capacity / 2).ToHandleChecked();
}
 
template <class Derived, int entrysize>
Handle<Derived> OrderedHashTable<Derived, entrysize>::Clear(
    Isolate* isolate, Handle<Derived> table) {
  DCHECK(!table->IsObsolete());
 
  AllocationType allocation_type = HeapLayout::InYoungGeneration(*table)
                                       ? AllocationType::kYoung
                                       : AllocationType::kOld;
 
  Handle<Derived> new_table =
      Allocate(isolate, kInitialCapacity, allocation_type).ToHandleChecked();
 
  if (table->NumberOfBuckets() > 0) {
    // Don't try to modify the empty canonical table which lives in RO space.
    table->SetNextTable(*new_table);
    table->SetNumberOfDeletedElements(kClearedTableSentinel);
  }
 
  return new_table;
}
 
template <class Derived, int entrysize>
bool OrderedHashTable<Derived, entrysize>::HasKey(Isolate* isolate,
                                                  Tagged<Derived> table,
                                                  Tagged<Object> key) {
  DCHECK_IMPLIES(entrysize == 1, IsOrderedHashSet(table));
  DCHECK_IMPLIES(entrysize == 2, IsOrderedHashMap(table));
  DisallowGarbageCollection no_gc;
  InternalIndex entry = table->FindEntry(isolate, key);
  return entry.is_found();
}
 
template <class Derived, int entrysize>
InternalIndex OrderedHashTable<Derived, entrysize>::FindEntry(
    Isolate* isolate, Tagged<Object> key) {
  if (NumberOfElements() == 0) {
    // This is not just an optimization but also ensures that we do the right
    // thing if Capacity() == 0
    return InternalIndex::NotFound();
  }
 
  int raw_entry;
  // This special cases for Smi, so that we avoid the HandleScope
  // creation below.
  if (IsSmi(key)) {
    uint32_t hash = ComputeUnseededHash(Smi::ToInt(key));
    raw_entry = HashToEntryRaw(hash & Smi::kMaxValue);
  } else {
    HandleScope scope(isolate);
    Tagged<Object> hash = Object::GetHash(key);
    // If the object does not have an identity hash, it was never used as a key
    if (IsUndefined(hash, isolate)) return InternalIndex::NotFound();
    raw_entry = HashToEntryRaw(Smi::ToInt(hash));
  }
 
  // Walk the chain in the bucket to find the key.
  while (raw_entry != kNotFound) {
    Tagged<Object> candidate_key = KeyAt(InternalIndex(raw_entry));
    if (Object::SameValueZero(candidate_key, key))
      return InternalIndex(raw_entry);
    raw_entry = NextChainEntryRaw(raw_entry);
  }
 
  return InternalIndex::NotFound();
}
 
template <template <typename> typename HandleType>
  requires(std::is_convertible_v<HandleType<OrderedHashSet>,
                                 DirectHandle<OrderedHashSet>>)
HandleType<OrderedHashSet>::MaybeType OrderedHashSet::Add(
    Isolate* isolate, HandleType<OrderedHashSet> table,
    DirectHandle<Object> key) {
  int hash;
  {
    DisallowGarbageCollection no_gc;
    Tagged<Object> raw_key = *key;
    Tagged<OrderedHashSet> raw_table = *table;
    hash = Object::GetOrCreateHash(raw_key, isolate).value();
    if (raw_table->NumberOfElements() > 0) {
      int raw_entry = raw_table->HashToEntryRaw(hash);
      // Walk the chain of the bucket and try finding the key.
      while (raw_entry != kNotFound) {
        Tagged<Object> candidate_key =
            raw_table->KeyAt(InternalIndex(raw_entry));
        // Do not add if we have the key already
        if (Object::SameValueZero(candidate_key, raw_key)) return table;
        raw_entry = raw_table->NextChainEntryRaw(raw_entry);
      }
    }
  }
 
  typename HandleType<OrderedHashSet>::MaybeType table_candidate =
      OrderedHashSet::EnsureCapacityForAdding(isolate, table);
  if (!table_candidate.ToHandle(&table)) {
    CHECK(isolate->has_exception());
    return table_candidate;
  }
  DisallowGarbageCollection no_gc;
  Tagged<OrderedHashSet> raw_table = *table;
  // Read the existing bucket values.
  int bucket = raw_table->HashToBucket(hash);
  int previous_entry = raw_table->HashToEntryRaw(hash);
  int nof = raw_table->NumberOfElements();
  // Insert a new entry at the end,
  int new_entry = nof + raw_table->NumberOfDeletedElements();
  int new_index = raw_table->EntryToIndexRaw(new_entry);
  raw_table->set(new_index, *key);
  raw_table->set(new_index + kChainOffset, Smi::FromInt(previous_entry));
  // and point the bucket to the new entry.
  raw_table->set(HashTableStartIndex() + bucket, Smi::FromInt(new_entry));
  raw_table->SetNumberOfElements(nof + 1);
  return table;
}
 
template V8_EXPORT_PRIVATE MaybeIndirectHandle<OrderedHashSet>
OrderedHashSet::Add(Isolate* isolate, IndirectHandle<OrderedHashSet> table,
                    DirectHandle<Object> key);
template V8_EXPORT_PRIVATE MaybeDirectHandle<OrderedHashSet>
OrderedHashSet::Add(Isolate* isolate, DirectHandle<OrderedHashSet> table,
                    DirectHandle<Object> key);
 
Handle<FixedArray> OrderedHashSet::ConvertToKeysArray(
    Isolate* isolate, Handle<OrderedHashSet> table, GetKeysConversion convert) {
  int length = table->NumberOfElements();
  int nof_buckets = table->NumberOfBuckets();
  // Convert the dictionary to a linear list.
  Handle<FixedArray> result = Cast<FixedArray>(table);
  // From this point on table is no longer a valid OrderedHashSet.
  result->set_map(isolate, ReadOnlyRoots(isolate).fixed_array_map());
  int const kMaxStringTableEntries =
      isolate->heap()->MaxNumberToStringCacheSize();
  for (int i = 0; i < length; i++) {
    int index = HashTableStartIndex() + nof_buckets + (i * kEntrySize);
    Tagged<Object> key = table->get(index);
    uint32_t index_value;
    if (convert == GetKeysConversion::kConvertToString) {
      if (Object::ToArrayIndex(key, &index_value)) {
        // Avoid trashing the Number2String cache if indices get very large.
        bool use_cache = i < kMaxStringTableEntries;
        key = *isolate->factory()->Uint32ToString(index_value, use_cache);
      } else {
        CHECK(IsName(key));
      }
    } else if (convert == GetKeysConversion::kNoNumbers) {
      DCHECK(!Object::ToArrayIndex(key, &index_value));
    }
    result->set(i, key);
  }
  return FixedArray::RightTrimOrEmpty(isolate, result, length);
}
 
Tagged<HeapObject> OrderedHashSet::GetEmpty(ReadOnlyRoots ro_roots) {
  return ro_roots.empty_ordered_hash_set();
}
 
Tagged<HeapObject> OrderedHashMap::GetEmpty(ReadOnlyRoots ro_roots) {
  return ro_roots.empty_ordered_hash_map();
}
 
template <class Derived, int entrysize>
template <template <typename> typename HandleType>
  requires(std::is_convertible_v<HandleType<Derived>, DirectHandle<Derived>>)
HandleType<Derived>::MaybeType OrderedHashTable<Derived, entrysize>::Rehash(
    Isolate* isolate, HandleType<Derived> table) {
  return OrderedHashTable<Derived, entrysize>::Rehash(isolate, table,
                                                      table->Capacity());
}
 
template <class Derived, int entrysize>
template <template <typename> typename HandleType>
  requires(std::is_convertible_v<HandleType<Derived>, DirectHandle<Derived>>)
HandleType<Derived>::MaybeType OrderedHashTable<Derived, entrysize>::Rehash(
    Isolate* isolate, HandleType<Derived> table, int new_capacity) {
  DCHECK(!table->IsObsolete());
 
  typename HandleType<Derived>::MaybeType new_table_candidate =
      Derived::Allocate(isolate, new_capacity,
                        HeapLayout::InYoungGeneration(*table)
                            ? AllocationType::kYoung
                            : AllocationType::kOld);
  DirectHandle<Derived> new_table;
  if (!new_table_candidate.ToHandle(&new_table)) {
    return new_table_candidate;
  }
  int new_buckets = new_table->NumberOfBuckets();
  int new_entry = 0;
  int removed_holes_index = 0;
 
  DisallowGarbageCollection no_gc;
 
  for (InternalIndex old_entry : table->IterateEntries()) {
    int old_entry_raw = old_entry.as_int();
    Tagged<Object> key = table->KeyAt(old_entry);
    if (IsHashTableHole(key, isolate)) {
      table->SetRemovedIndexAt(removed_holes_index++, old_entry_raw);
      continue;
    }
 
    Tagged<Object> hash = Object::GetHash(key);
    int bucket = Smi::ToInt(hash) & (new_buckets - 1);
    Tagged<Object> chain_entry = new_table->get(HashTableStartIndex() + bucket);
    new_table->set(HashTableStartIndex() + bucket, Smi::FromInt(new_entry));
    int new_index = new_table->EntryToIndexRaw(new_entry);
    int old_index = table->EntryToIndexRaw(old_entry_raw);
    for (int i = 0; i < entrysize; ++i) {
      Tagged<Object> value = table->get(old_index + i);
      new_table->set(new_index + i, value);
    }
    new_table->set(new_index + kChainOffset, chain_entry);
    ++new_entry;
  }
 
  DCHECK_EQ(table->NumberOfDeletedElements(), removed_holes_index);
 
  new_table->SetNumberOfElements(table->NumberOfElements());
  if (table->NumberOfBuckets() > 0) {
    // Don't try to modify the empty canonical table which lives in RO space.
    table->SetNextTable(*new_table);
  }
 
  return new_table_candidate;
}
 
template <template <typename> typename HandleType>
  requires(std::is_convertible_v<HandleType<OrderedHashSet>,
                                 DirectHandle<OrderedHashSet>>)
HandleType<OrderedHashSet>::MaybeType OrderedHashSet::Rehash(
    Isolate* isolate, HandleType<OrderedHashSet> table) {
  return Base::Rehash(isolate, table);
}
 
template <template <typename> typename HandleType>
  requires(std::is_convertible_v<HandleType<OrderedHashSet>,
                                 DirectHandle<OrderedHashSet>>)
HandleType<OrderedHashSet>::MaybeType OrderedHashSet::Rehash(
    Isolate* isolate, HandleType<OrderedHashSet> table, int new_capacity) {
  return Base::Rehash(isolate, table, new_capacity);
}
 
template V8_EXPORT_PRIVATE MaybeIndirectHandle<OrderedHashSet>
OrderedHashSet::Rehash(Isolate* isolate, IndirectHandle<OrderedHashSet> table);
template V8_EXPORT_PRIVATE MaybeIndirectHandle<OrderedHashSet>
OrderedHashSet::Rehash(Isolate* isolate, IndirectHandle<OrderedHashSet> table,
                       int new_capacity);
template V8_EXPORT_PRIVATE MaybeDirectHandle<OrderedHashSet>
OrderedHashSet::Rehash(Isolate* isolate, DirectHandle<OrderedHashSet> table);
template V8_EXPORT_PRIVATE MaybeDirectHandle<OrderedHashSet>
OrderedHashSet::Rehash(Isolate* isolate, DirectHandle<OrderedHashSet> table,
                       int new_capacity);
 
template <template <typename> typename HandleType>
  requires(std::is_convertible_v<HandleType<OrderedHashMap>,
                                 DirectHandle<OrderedHashMap>>)
HandleType<OrderedHashMap>::MaybeType OrderedHashMap::Rehash(
    Isolate* isolate, HandleType<OrderedHashMap> table) {
  return Base::Rehash(isolate, table);
}
template <template <typename> typename HandleType>
  requires(std::is_convertible_v<HandleType<OrderedHashMap>,
                                 DirectHandle<OrderedHashMap>>)
HandleType<OrderedHashMap>::MaybeType OrderedHashMap::Rehash(
    Isolate* isolate, HandleType<OrderedHashMap> table, int new_capacity) {
  return Base::Rehash(isolate, table, new_capacity);
}
 
template V8_EXPORT_PRIVATE MaybeIndirectHandle<OrderedHashMap>
OrderedHashMap::Rehash(Isolate* isolate, IndirectHandle<OrderedHashMap> table);
template V8_EXPORT_PRIVATE MaybeIndirectHandle<OrderedHashMap>
OrderedHashMap::Rehash(Isolate* isolate, IndirectHandle<OrderedHashMap> table,
                       int new_capacity);
template V8_EXPORT_PRIVATE MaybeDirectHandle<OrderedHashMap>
OrderedHashMap::Rehash(Isolate* isolate, DirectHandle<OrderedHashMap> table);
template V8_EXPORT_PRIVATE MaybeDirectHandle<OrderedHashMap>
OrderedHashMap::Rehash(Isolate* isolate, DirectHandle<OrderedHashMap> table,
                       int new_capacity);
 
template <template <typename> typename HandleType>
  requires(std::is_convertible_v<HandleType<OrderedNameDictionary>,
                                 DirectHandle<OrderedNameDictionary>>)
HandleType<OrderedNameDictionary>::MaybeType OrderedNameDictionary::Rehash(
    Isolate* isolate, HandleType<OrderedNameDictionary> table,
    int new_capacity) {
  typename HandleType<OrderedNameDictionary>::MaybeType new_table_candidate =
      Base::Rehash(isolate, table, new_capacity);
  DirectHandle<OrderedNameDictionary> new_table;
  if (new_table_candidate.ToHandle(&new_table)) {
    new_table->SetHash(table->Hash());
  }
  return new_table_candidate;
}
 
template V8_EXPORT_PRIVATE MaybeIndirectHandle<OrderedNameDictionary>
OrderedNameDictionary::Rehash(Isolate* isolate,
                              IndirectHandle<OrderedNameDictionary> table,
                              int new_capacity);
template V8_EXPORT_PRIVATE MaybeDirectHandle<OrderedNameDictionary>
OrderedNameDictionary::Rehash(Isolate* isolate,
                              DirectHandle<OrderedNameDictionary> table,
                              int new_capacity);
 
template <class Derived, int entrysize>
bool OrderedHashTable<Derived, entrysize>::Delete(Isolate* isolate,
                                                  Tagged<Derived> table,
                                                  Tagged<Object> key) {
  DisallowGarbageCollection no_gc;
  InternalIndex entry = table->FindEntry(isolate, key);
  if (entry.is_not_found()) return false;
 
  int nof = table->NumberOfElements();
  int nod = table->NumberOfDeletedElements();
  int index = table->EntryToIndex(entry);
 
  Tagged<Object> hash_table_hole =
      ReadOnlyRoots(isolate).hash_table_hole_value();
  for (int i = 0; i < entrysize; ++i) {
    table->set(index + i, hash_table_hole);
  }
 
  table->SetNumberOfElements(nof - 1);
  table->SetNumberOfDeletedElements(nod + 1);
 
  return true;
}
 
Address OrderedHashMap::GetHash(Isolate* isolate, Address raw_key) {
  DisallowGarbageCollection no_gc;
  Tagged<Object> key(raw_key);
  Tagged<Object> hash = Object::GetHash(key);
  // If the object does not have an identity hash, it was never used as a key
  if (IsUndefined(hash, isolate)) return Smi::FromInt(-1).ptr();
  DCHECK(IsSmi(hash));
  DCHECK_GE(Cast<Smi>(hash).value(), 0);
  return hash.ptr();
}
 
MaybeHandle<OrderedHashMap> OrderedHashMap::Add(Isolate* isolate,
                                                Handle<OrderedHashMap> table,
                                                DirectHandle<Object> key,
                                                DirectHandle<Object> value) {
  int hash = Object::GetOrCreateHash(*key, isolate).value();
  if (table->NumberOfElements() > 0) {
    int raw_entry = table->HashToEntryRaw(hash);
    // Walk the chain of the bucket and try finding the key.
    {
      DisallowGarbageCollection no_gc;
      Tagged<Object> raw_key = *key;
      while (raw_entry != kNotFound) {
        Tagged<Object> candidate_key = table->KeyAt(InternalIndex(raw_entry));
        // Do not add if we have the key already
        if (Object::SameValueZero(candidate_key, raw_key)) return table;
        raw_entry = table->NextChainEntryRaw(raw_entry);
      }
    }
  }
 
  MaybeHandle<OrderedHashMap> table_candidate =
      OrderedHashMap::EnsureCapacityForAdding(isolate, table);
  if (!table_candidate.ToHandle(&table)) {
    return table_candidate;
  }
  DisallowGarbageCollection no_gc;
  Tagged<OrderedHashMap> raw_table = *table;
  // Read the existing bucket values.
  int bucket = raw_table->HashToBucket(hash);
  int previous_entry = raw_table->HashToEntryRaw(hash);
  int nof = raw_table->NumberOfElements();
  // Insert a new entry at the end,
  int new_entry = nof + raw_table->NumberOfDeletedElements();
  int new_index = raw_table->EntryToIndexRaw(new_entry);
  raw_table->set(new_index, *key);
  raw_table->set(new_index + kValueOffset, *value);
  raw_table->set(new_index + kChainOffset, Smi::FromInt(previous_entry));
  // and point the bucket to the new entry.
  raw_table->set(HashTableStartIndex() + bucket, Smi::FromInt(new_entry));
  raw_table->SetNumberOfElements(nof + 1);
  return table;
}
 
void OrderedHashMap::SetEntry(InternalIndex entry, Tagged<Object> key,
                              Tagged<Object> value) {
  DisallowGarbageCollection no_gc;
  int index = EntryToIndex(entry);
  this->set(index, key);
  this->set(index + kValueOffset, value);
}
 
template <typename IsolateT>
InternalIndex OrderedNameDictionary::FindEntry(IsolateT* isolate,
                                               Tagged<Object> key) {
  DisallowGarbageCollection no_gc;
 
  DCHECK(IsUniqueName(key));
  Tagged<Name> raw_key = Cast<Name>(key);
 
  if (NumberOfElements() == 0) {
    // This is not just an optimization but also ensures that we do the right
    // thing if Capacity() == 0
    return InternalIndex::NotFound();
  }
 
  int raw_entry = HashToEntryRaw(raw_key->hash());
  while (raw_entry != kNotFound) {
    InternalIndex entry(raw_entry);
    Tagged<Object> candidate_key = KeyAt(entry);
    DCHECK(IsHashTableHole(candidate_key) ||
           IsUniqueName(Cast<Name>(candidate_key)));
    if (candidate_key == raw_key) return entry;
 
    // TODO(gsathya): This is loading the bucket count from the hash
    // table for every iteration. This should be peeled out of the
    // loop.
    raw_entry = NextChainEntryRaw(raw_entry);
  }
 
  return InternalIndex::NotFound();
}
 
MaybeHandle<OrderedNameDictionary> OrderedNameDictionary::Add(
    Isolate* isolate, Handle<OrderedNameDictionary> table,
    DirectHandle<Name> key, DirectHandle<Object> value,
    PropertyDetails details) {
  DCHECK(IsUniqueName(*key));
  DCHECK(table->FindEntry(isolate, *key).is_not_found());
 
  MaybeHandle<OrderedNameDictionary> table_candidate =
      OrderedNameDictionary::EnsureCapacityForAdding(isolate, table);
  if (!table_candidate.ToHandle(&table)) {
    return table_candidate;
  }
  DisallowGarbageCollection no_gc;
  Tagged<OrderedNameDictionary> raw_table = *table;
  // Read the existing bucket values.
  int hash = key->hash();
  int bucket = raw_table->HashToBucket(hash);
  int previous_entry = raw_table->HashToEntryRaw(hash);
  int nof = raw_table->NumberOfElements();
  // Insert a new entry at the end,
  int new_entry = nof + raw_table->NumberOfDeletedElements();
  int new_index = raw_table->EntryToIndexRaw(new_entry);
  raw_table->set(new_index, *key);
  raw_table->set(new_index + kValueOffset, *value);
 
  // TODO(gsathya): Optimize how PropertyDetails are stored in this
  // dictionary to save memory (by reusing padding?) and performance
  // (by not doing the Smi conversion).
  raw_table->set(new_index + kPropertyDetailsOffset, details.AsSmi());
 
  raw_table->set(new_index + kChainOffset, Smi::FromInt(previous_entry));
  // and point the bucket to the new entry.
  raw_table->set(HashTableStartIndex() + bucket, Smi::FromInt(new_entry));
  raw_table->SetNumberOfElements(nof + 1);
  return table;
}
 
void OrderedNameDictionary::SetEntry(InternalIndex entry, Tagged<Object> key,
                                     Tagged<Object> value,
                                     PropertyDetails details) {
  DisallowGarbageCollection gc;
  DCHECK_IMPLIES(!IsName(key), IsHashTableHole(key));
  DisallowGarbageCollection no_gc;
  int index = EntryToIndex(entry);
  this->set(index, key);
  this->set(index + kValueOffset, value);
 
  // TODO(gsathya): Optimize how PropertyDetails are stored in this
  // dictionary to save memory (by reusing padding?) and performance
  // (by not doing the Smi conversion).
  this->set(index + kPropertyDetailsOffset, details.AsSmi());
}
 
Handle<OrderedNameDictionary> OrderedNameDictionary::DeleteEntry(
    Isolate* isolate, Handle<OrderedNameDictionary> table,
    InternalIndex entry) {
  DCHECK(entry.is_found());
 
  Tagged<Object> hash_table_hole =
      ReadOnlyRoots(isolate).hash_table_hole_value();
  PropertyDetails details = PropertyDetails::Empty();
  table->SetEntry(entry, hash_table_hole, hash_table_hole, details);
 
  int nof = table->NumberOfElements();
  table->SetNumberOfElements(nof - 1);
  int nod = table->NumberOfDeletedElements();
  table->SetNumberOfDeletedElements(nod + 1);
 
  return Shrink(isolate, table);
}
 
template <typename IsolateT>
MaybeHandle<OrderedHashSet> OrderedHashSet::Allocate(
    IsolateT* isolate, int capacity, AllocationType allocation) {
  return Base::Allocate(isolate, capacity, allocation);
}
 
template <typename IsolateT>
MaybeHandle<OrderedHashMap> OrderedHashMap::Allocate(
    IsolateT* isolate, int capacity, AllocationType allocation) {
  return Base::Allocate(isolate, capacity, allocation);
}
 
MaybeHandle<OrderedNameDictionary> OrderedNameDictionary::Allocate(
    Isolate* isolate, int capacity, AllocationType allocation) {
  MaybeHandle<OrderedNameDictionary> table_candidate =
      Base::Allocate(isolate, capacity, allocation);
  DirectHandle<OrderedNameDictionary> table;
  if (table_candidate.ToHandle(&table)) {
    table->SetHash(PropertyArray::kNoHashSentinel);
  }
  return table_candidate;
}
 
MaybeHandle<OrderedHashSet> OrderedHashSet::AllocateEmpty(
    Isolate* isolate, AllocationType allocation) {
  RootIndex ri = RootIndex::kEmptyOrderedHashSet;
  return Base::AllocateEmpty(isolate, allocation, ri);
}
 
MaybeHandle<OrderedHashMap> OrderedHashMap::AllocateEmpty(
    Isolate* isolate, AllocationType allocation) {
  RootIndex ri = RootIndex::kEmptyOrderedHashMap;
  return Base::AllocateEmpty(isolate, allocation, ri);
}
 
MaybeHandle<OrderedNameDictionary> OrderedNameDictionary::AllocateEmpty(
    Isolate* isolate, AllocationType allocation) {
  RootIndex ri = RootIndex::kEmptyOrderedPropertyDictionary;
  MaybeHandle<OrderedNameDictionary> table_candidate =
      Base::AllocateEmpty(isolate, allocation, ri);
  DirectHandle<OrderedNameDictionary> table;
  if (table_candidate.ToHandle(&table)) {
    table->SetHash(PropertyArray::kNoHashSentinel);
  }
 
  return table_candidate;
}
 
template V8_EXPORT_PRIVATE MaybeHandle<OrderedHashSet> OrderedHashSet::Allocate(
    Isolate* isolate, int capacity, AllocationType allocation);
 
template V8_EXPORT_PRIVATE MaybeHandle<OrderedHashMap> OrderedHashMap::Allocate(
    Isolate* isolate, int capacity, AllocationType allocation);
 
template V8_EXPORT_PRIVATE InternalIndex
OrderedNameDictionary::FindEntry(Isolate* isolate, Tagged<Object> key);
 
template V8_EXPORT_PRIVATE InternalIndex
OrderedNameDictionary::FindEntry(LocalIsolate* isolate, Tagged<Object> key);
 
template <>
Handle<SmallOrderedHashSet>
SmallOrderedHashTable<SmallOrderedHashSet>::Allocate(
    Isolate* isolate, int capacity, AllocationType allocation) {
  return isolate->factory()->NewSmallOrderedHashSet(capacity, allocation);
}
 
template <>
Handle<SmallOrderedHashMap>
SmallOrderedHashTable<SmallOrderedHashMap>::Allocate(
    Isolate* isolate, int capacity, AllocationType allocation) {
  return isolate->factory()->NewSmallOrderedHashMap(capacity, allocation);
}
 
template <>
Handle<SmallOrderedNameDictionary>
SmallOrderedHashTable<SmallOrderedNameDictionary>::Allocate(
    Isolate* isolate, int capacity, AllocationType allocation) {
  return isolate->factory()->NewSmallOrderedNameDictionary(capacity,
                                                           allocation);
}
 
template <class Derived>
void SmallOrderedHashTable<Derived>::Initialize(Isolate* isolate,
                                                int capacity) {
  DisallowGarbageCollection no_gc;
  int num_buckets = capacity / kLoadFactor;
  int num_chains = capacity;
 
  SetNumberOfBuckets(num_buckets);
  SetNumberOfElements(0);
  SetNumberOfDeletedElements(0);
  memset(reinterpret_cast<void*>(field_address(PaddingOffset())), 0,
         PaddingSize());
 
  Address hashtable_start = GetHashTableStartAddress(capacity);
  memset(reinterpret_cast<uint8_t*>(hashtable_start), kNotFound,
         num_buckets + num_chains);
 
  MemsetTagged(RawField(DataTableStartOffset()),
               ReadOnlyRoots(isolate).the_hole_value(),
               capacity * Derived::kEntrySize);
 
#ifdef DEBUG
  for (int i = 0; i < num_buckets; ++i) {
    DCHECK_EQ(kNotFound, GetFirstEntry(i));
  }
 
  for (int i = 0; i < num_chains; ++i) {
    DCHECK_EQ(kNotFound, GetNextEntry(i));
  }
 
  for (int i = 0; i < capacity; ++i) {
    for (int j = 0; j < Derived::kEntrySize; j++) {
      DCHECK_EQ(ReadOnlyRoots(isolate).the_hole_value(), GetDataEntry(i, j));
    }
  }
#endif  // DEBUG
}
 
MaybeHandle<SmallOrderedHashSet> SmallOrderedHashSet::Add(
    Isolate* isolate, Handle<SmallOrderedHashSet> table,
    DirectHandle<Object> key) {
  if (table->HasKey(isolate, key)) return table;
 
  if (table->UsedCapacity() >= table->Capacity()) {
    MaybeHandle<SmallOrderedHashSet> new_table =
        SmallOrderedHashSet::Grow(isolate, table);
    if (!new_table.ToHandle(&table)) {
      return MaybeHandle<SmallOrderedHashSet>();
    }
  }
 
  DisallowGarbageCollection no_gc;
  Tagged<SmallOrderedHashSet> raw_table = *table;
  int hash = Object::GetOrCreateHash(*key, isolate).value();
  int nof = raw_table->NumberOfElements();
 
  // Read the existing bucket values.
  int bucket = raw_table->HashToBucket(hash);
  int previous_entry = raw_table->HashToFirstEntry(hash);
 
  // Insert a new entry at the end,
  int new_entry = nof + raw_table->NumberOfDeletedElements();
 
  raw_table->SetDataEntry(new_entry, SmallOrderedHashSet::kKeyIndex, *key);
  raw_table->SetFirstEntry(bucket, new_entry);
  raw_table->SetNextEntry(new_entry, previous_entry);
 
  // and update book keeping.
  raw_table->SetNumberOfElements(nof + 1);
 
  return table;
}
 
bool SmallOrderedHashSet::Delete(Isolate* isolate,
                                 Tagged<SmallOrderedHashSet> table,
                                 Tagged<Object> key) {
  return SmallOrderedHashTable<SmallOrderedHashSet>::Delete(isolate, table,
                                                            key);
}
 
bool SmallOrderedHashSet::HasKey(Isolate* isolate, DirectHandle<Object> key) {
  return SmallOrderedHashTable<SmallOrderedHashSet>::HasKey(isolate, key);
}
 
MaybeHandle<SmallOrderedHashMap> SmallOrderedHashMap::Add(
    Isolate* isolate, Handle<SmallOrderedHashMap> table,
    DirectHandle<Object> key, DirectHandle<Object> value) {
  if (table->HasKey(isolate, key)) return table;
 
  if (table->UsedCapacity() >= table->Capacity()) {
    MaybeHandle<SmallOrderedHashMap> new_table =
        SmallOrderedHashMap::Grow(isolate, table);
    if (!new_table.ToHandle(&table)) {
      return MaybeHandle<SmallOrderedHashMap>();
    }
  }
  DisallowGarbageCollection no_gc;
  Tagged<SmallOrderedHashMap> raw_table = *table;
  int hash = Object::GetOrCreateHash(*key, isolate).value();
  int nof = raw_table->NumberOfElements();
 
  // Read the existing bucket values.
  int bucket = raw_table->HashToBucket(hash);
  int previous_entry = raw_table->HashToFirstEntry(hash);
 
  // Insert a new entry at the end,
  int new_entry = nof + raw_table->NumberOfDeletedElements();
 
  raw_table->SetDataEntry(new_entry, SmallOrderedHashMap::kValueIndex, *value);
  raw_table->SetDataEntry(new_entry, SmallOrderedHashMap::kKeyIndex, *key);
  raw_table->SetFirstEntry(bucket, new_entry);
  raw_table->SetNextEntry(new_entry, previous_entry);
 
  // and update book keeping.
  raw_table->SetNumberOfElements(nof + 1);
 
  return table;
}
 
bool SmallOrderedHashMap::Delete(Isolate* isolate,
                                 Tagged<SmallOrderedHashMap> table,
                                 Tagged<Object> key) {
  return SmallOrderedHashTable<SmallOrderedHashMap>::Delete(isolate, table,
                                                            key);
}
 
bool SmallOrderedHashMap::HasKey(Isolate* isolate, DirectHandle<Object> key) {
  return SmallOrderedHashTable<SmallOrderedHashMap>::HasKey(isolate, key);
}
 
template <>
InternalIndex V8_EXPORT_PRIVATE
SmallOrderedHashTable<SmallOrderedNameDictionary>::FindEntry(
    Isolate* isolate, Tagged<Object> key) {
  DisallowGarbageCollection no_gc;
  DCHECK(IsUniqueName(key));
  Tagged<Name> raw_key = Cast<Name>(key);
 
  int raw_entry = HashToFirstEntry(raw_key->hash());
 
  // Walk the chain in the bucket to find the key.
  while (raw_entry != kNotFound) {
    InternalIndex entry(raw_entry);
    Tagged<Object> candidate_key = KeyAt(entry);
    if (candidate_key == key) return entry;
    raw_entry = GetNextEntry(raw_entry);
  }
 
  return InternalIndex::NotFound();
}
 
MaybeHandle<SmallOrderedNameDictionary> SmallOrderedNameDictionary::Add(
    Isolate* isolate, Handle<SmallOrderedNameDictionary> table,
    DirectHandle<Name> key, DirectHandle<Object> value,
    PropertyDetails details) {
  DCHECK(IsUniqueName(*key));
  DCHECK(table->FindEntry(isolate, *key).is_not_found());
 
  if (table->UsedCapacity() >= table->Capacity()) {
    MaybeHandle<SmallOrderedNameDictionary> new_table =
        SmallOrderedNameDictionary::Grow(isolate, table);
    if (!new_table.ToHandle(&table)) {
      return MaybeHandle<SmallOrderedNameDictionary>();
    }
  }
 
  int nof = table->NumberOfElements();
 
  // Read the existing bucket values.
  int hash = key->hash();
  int bucket = table->HashToBucket(hash);
  int previous_entry = table->HashToFirstEntry(hash);
 
  // Insert a new entry at the end,
  int new_entry = nof + table->NumberOfDeletedElements();
 
  table->SetDataEntry(new_entry, SmallOrderedNameDictionary::kValueIndex,
                      *value);
  table->SetDataEntry(new_entry, SmallOrderedNameDictionary::kKeyIndex, *key);
 
  // TODO(gsathya): PropertyDetails should be stored as part of the
  // data table to save more memory.
  table->SetDataEntry(new_entry,
                      SmallOrderedNameDictionary::kPropertyDetailsIndex,
                      details.AsSmi());
  table->SetFirstEntry(bucket, new_entry);
  table->SetNextEntry(new_entry, previous_entry);
 
  // and update book keeping.
  table->SetNumberOfElements(nof + 1);
 
  return table;
}
 
void SmallOrderedNameDictionary::SetEntry(InternalIndex entry,
                                          Tagged<Object> key,
                                          Tagged<Object> value,
                                          PropertyDetails details) {
  int raw_entry = entry.as_int();
  DCHECK_IMPLIES(!IsName(key), IsTheHole(key));
  SetDataEntry(raw_entry, SmallOrderedNameDictionary::kValueIndex, value);
  SetDataEntry(raw_entry, SmallOrderedNameDictionary::kKeyIndex, key);
 
  // TODO(gsathya): PropertyDetails should be stored as part of the
  // data table to save more memory.
  SetDataEntry(raw_entry, SmallOrderedNameDictionary::kPropertyDetailsIndex,
               details.AsSmi());
}
 
template <class Derived>
bool SmallOrderedHashTable<Derived>::HasKey(Isolate* isolate,
                                            DirectHandle<Object> key) {
  DisallowGarbageCollection no_gc;
  return FindEntry(isolate, *key).is_found();
}
 
template <class Derived>
bool SmallOrderedHashTable<Derived>::Delete(Isolate* isolate,
                                            Tagged<Derived> table,
                                            Tagged<Object> key) {
  DisallowGarbageCollection no_gc;
  InternalIndex entry = table->FindEntry(isolate, key);
  if (entry.is_not_found()) return false;
 
  int nof = table->NumberOfElements();
  int nod = table->NumberOfDeletedElements();
 
  Tagged<Object> the_hole = ReadOnlyRoots(isolate).the_hole_value();
  for (int j = 0; j < Derived::kEntrySize; j++) {
    table->SetDataEntry(entry.as_int(), j, the_hole);
  }
 
  table->SetNumberOfElements(nof - 1);
  table->SetNumberOfDeletedElements(nod + 1);
 
  return true;
}
 
Handle<SmallOrderedNameDictionary> SmallOrderedNameDictionary::DeleteEntry(
    Isolate* isolate, Handle<SmallOrderedNameDictionary> table,
    InternalIndex entry) {
  DCHECK(entry.is_found());
  {
    DisallowGarbageCollection no_gc;
    Tagged<Object> the_hole = ReadOnlyRoots(isolate).the_hole_value();
    PropertyDetails details = PropertyDetails::Empty();
    table->SetEntry(entry, the_hole, the_hole, details);
 
    int nof = table->NumberOfElements();
    table->SetNumberOfElements(nof - 1);
    int nod = table->NumberOfDeletedElements();
    table->SetNumberOfDeletedElements(nod + 1);
  }
  return Shrink(isolate, table);
}
 
template <class Derived>
Handle<Derived> SmallOrderedHashTable<Derived>::Rehash(Isolate* isolate,
                                                       Handle<Derived> table,
                                                       int new_capacity) {
  DCHECK_GE(kMaxCapacity, new_capacity);
 
  Handle<Derived> new_table = SmallOrderedHashTable<Derived>::Allocate(
      isolate, new_capacity,
      HeapLayout::InYoungGeneration(*table) ? AllocationType::kYoung
                                            : AllocationType::kOld);
  int new_entry = 0;
 
  {
    DisallowGarbageCollection no_gc;
    for (InternalIndex old_entry : table->IterateEntries()) {
      Tagged<Object> key = table->KeyAt(old_entry);
      if (IsTheHole(key, isolate)) continue;
 
      int hash = Smi::ToInt(Object::GetHash(key));
      int bucket = new_table->HashToBucket(hash);
      int chain = new_table->GetFirstEntry(bucket);
 
      new_table->SetFirstEntry(bucket, new_entry);
      new_table->SetNextEntry(new_entry, chain);
 
      for (int i = 0; i < Derived::kEntrySize; ++i) {
        Tagged<Object> value = table->GetDataEntry(old_entry.as_int(), i);
        new_table->SetDataEntry(new_entry, i, value);
      }
 
      ++new_entry;
    }
 
    new_table->SetNumberOfElements(table->NumberOfElements());
  }
  return new_table;
}
 
Handle<SmallOrderedHashSet> SmallOrderedHashSet::Rehash(
    Isolate* isolate, Handle<SmallOrderedHashSet> table, int new_capacity) {
  return SmallOrderedHashTable<SmallOrderedHashSet>::Rehash(isolate, table,
                                                            new_capacity);
}
 
Handle<SmallOrderedHashMap> SmallOrderedHashMap::Rehash(
    Isolate* isolate, Handle<SmallOrderedHashMap> table, int new_capacity) {
  return SmallOrderedHashTable<SmallOrderedHashMap>::Rehash(isolate, table,
                                                            new_capacity);
}
 
Handle<SmallOrderedNameDictionary> SmallOrderedNameDictionary::Rehash(
    Isolate* isolate, Handle<SmallOrderedNameDictionary> table,
    int new_capacity) {
  Handle<SmallOrderedNameDictionary> new_table =
      SmallOrderedHashTable<SmallOrderedNameDictionary>::Rehash(isolate, table,
                                                                new_capacity);
  new_table->SetHash(table->Hash());
  return new_table;
}
 
template <class Derived>
Handle<Derived> SmallOrderedHashTable<Derived>::Shrink(Isolate* isolate,
                                                       Handle<Derived> table) {
  int nof = table->NumberOfElements();
  int capacity = table->Capacity();
  if (nof >= (capacity >> 2)) return table;
  return Derived::Rehash(isolate, table, capacity / 2);
}
 
template <class Derived>
MaybeHandle<Derived> SmallOrderedHashTable<Derived>::Grow(
    Isolate* isolate, Handle<Derived> table) {
  int capacity = table->Capacity();
  int new_capacity = capacity;
 
  // Don't need to grow if we can simply clear out deleted entries instead.
  // TODO(gsathya): Compact in place, instead of allocating a new table.
  if (table->NumberOfDeletedElements() < (capacity >> 1)) {
    new_capacity = capacity << 1;
 
    // The max capacity of our table is 254. We special case for 256 to
    // account for our growth strategy, otherwise we would only fill up
    // to 128 entries in our table.
    if (new_capacity == kGrowthHack) {
      new_capacity = kMaxCapacity;
    }
 
    // We need to migrate to a bigger hash table.
    if (new_capacity > kMaxCapacity) {
      return MaybeHandle<Derived>();
    }
  }
 
  return Derived::Rehash(isolate, table, new_capacity);
}
 
template <class Derived>
InternalIndex SmallOrderedHashTable<Derived>::FindEntry(Isolate* isolate,
                                                        Tagged<Object> key) {
  DisallowGarbageCollection no_gc;
  Tagged<Object> hash = Object::GetHash(key);
 
  if (IsUndefined(hash, isolate)) return InternalIndex::NotFound();
  int raw_entry = HashToFirstEntry(Smi::ToInt(hash));
 
  // Walk the chain in the bucket to find the key.
  while (raw_entry != kNotFound) {
    InternalIndex entry(raw_entry);
    Tagged<Object> candidate_key = KeyAt(entry);
    if (Object::SameValueZero(candidate_key, key)) return entry;
    raw_entry = GetNextEntry(raw_entry);
  }
  return InternalIndex::NotFound();
}
 
template bool V8_EXPORT_PRIVATE
SmallOrderedHashTable<SmallOrderedHashSet>::HasKey(Isolate* isolate,
                                                   DirectHandle<Object> key);
template V8_EXPORT_PRIVATE Handle<SmallOrderedHashSet>
SmallOrderedHashTable<SmallOrderedHashSet>::Rehash(
    Isolate* isolate, Handle<SmallOrderedHashSet> table, int new_capacity);
template V8_EXPORT_PRIVATE Handle<SmallOrderedHashSet>
SmallOrderedHashTable<SmallOrderedHashSet>::Shrink(
    Isolate* isolate, Handle<SmallOrderedHashSet> table);
template V8_EXPORT_PRIVATE MaybeHandle<SmallOrderedHashSet>
SmallOrderedHashTable<SmallOrderedHashSet>::Grow(
    Isolate* isolate, Handle<SmallOrderedHashSet> table);
template V8_EXPORT_PRIVATE void
SmallOrderedHashTable<SmallOrderedHashSet>::Initialize(Isolate* isolate,
                                                       int capacity);
template V8_EXPORT_PRIVATE bool
SmallOrderedHashTable<SmallOrderedHashSet>::Delete(
    Isolate* isolate, Tagged<SmallOrderedHashSet> table, Tagged<Object> key);
 
template V8_EXPORT_PRIVATE bool
SmallOrderedHashTable<SmallOrderedHashMap>::HasKey(Isolate* isolate,
                                                   DirectHandle<Object> key);
template V8_EXPORT_PRIVATE Handle<SmallOrderedHashMap>
SmallOrderedHashTable<SmallOrderedHashMap>::Rehash(
    Isolate* isolate, Handle<SmallOrderedHashMap> table, int new_capacity);
template V8_EXPORT_PRIVATE Handle<SmallOrderedHashMap>
SmallOrderedHashTable<SmallOrderedHashMap>::Shrink(
    Isolate* isolate, Handle<SmallOrderedHashMap> table);
template V8_EXPORT_PRIVATE MaybeHandle<SmallOrderedHashMap>
SmallOrderedHashTable<SmallOrderedHashMap>::Grow(
    Isolate* isolate, Handle<SmallOrderedHashMap> table);
template V8_EXPORT_PRIVATE void
SmallOrderedHashTable<SmallOrderedHashMap>::Initialize(Isolate* isolate,
                                                       int capacity);
 
template V8_EXPORT_PRIVATE bool
SmallOrderedHashTable<SmallOrderedHashMap>::Delete(
    Isolate* isolate, Tagged<SmallOrderedHashMap> table, Tagged<Object> key);
 
template V8_EXPORT_PRIVATE void
SmallOrderedHashTable<SmallOrderedNameDictionary>::Initialize(Isolate* isolate,
                                                              int capacity);
template V8_EXPORT_PRIVATE Handle<SmallOrderedNameDictionary>
SmallOrderedHashTable<SmallOrderedNameDictionary>::Shrink(
    Isolate* isolate, Handle<SmallOrderedNameDictionary> table);
 
template <class SmallTable, class LargeTable>
MaybeHandle<HeapObject>
OrderedHashTableHandler<SmallTable, LargeTable>::Allocate(Isolate* isolate,
                                                          int capacity) {
  if (capacity < SmallTable::kMaxCapacity) {
    return SmallTable::Allocate(isolate, capacity);
  }
 
  return LargeTable::Allocate(isolate, capacity);
}
 
template V8_EXPORT_PRIVATE MaybeHandle<HeapObject>
OrderedHashTableHandler<SmallOrderedHashSet, OrderedHashSet>::Allocate(
    Isolate* isolate, int capacity);
template V8_EXPORT_PRIVATE MaybeHandle<HeapObject>
OrderedHashTableHandler<SmallOrderedHashMap, OrderedHashMap>::Allocate(
    Isolate* isolate, int capacity);
template V8_EXPORT_PRIVATE MaybeHandle<HeapObject>
OrderedHashTableHandler<SmallOrderedNameDictionary,
                        OrderedNameDictionary>::Allocate(Isolate* isolate,
                                                         int capacity);
 
template <class SmallTable, class LargeTable>
bool OrderedHashTableHandler<SmallTable, LargeTable>::Delete(
    Isolate* isolate, Handle<HeapObject> table, DirectHandle<Object> key) {
  if (SmallTable::Is(table)) {
    return SmallTable::Delete(isolate, *Cast<SmallTable>(table), *key);
  }
 
  DCHECK(LargeTable::Is(table));
  // Note: Once we migrate to the a big hash table, we never migrate
  // down to a smaller hash table.
  return LargeTable::Delete(isolate, *Cast<LargeTable>(table), *key);
}
 
template <class SmallTable, class LargeTable>
bool OrderedHashTableHandler<SmallTable, LargeTable>::HasKey(
    Isolate* isolate, Handle<HeapObject> table, Handle<Object> key) {
  if (SmallTable::Is(table)) {
    return Cast<SmallTable>(table)->HasKey(isolate, key);
  }
 
  DCHECK(LargeTable::Is(table));
  return LargeTable::HasKey(isolate, Cast<LargeTable>(*table), *key);
}
 
template bool
OrderedHashTableHandler<SmallOrderedHashSet, OrderedHashSet>::HasKey(
    Isolate* isolate, Handle<HeapObject> table, Handle<Object> key);
template bool
OrderedHashTableHandler<SmallOrderedHashMap, OrderedHashMap>::HasKey(
    Isolate* isolate, Handle<HeapObject> table, Handle<Object> key);
 
template bool
OrderedHashTableHandler<SmallOrderedHashSet, OrderedHashSet>::Delete(
    Isolate* isolate, Handle<HeapObject> table, DirectHandle<Object> key);
template bool
OrderedHashTableHandler<SmallOrderedHashMap, OrderedHashMap>::Delete(
    Isolate* isolate, Handle<HeapObject> table, DirectHandle<Object> key);
template bool OrderedHashTableHandler<
    SmallOrderedNameDictionary,
    OrderedNameDictionary>::Delete(Isolate* isolate, Handle<HeapObject> table,
                                   DirectHandle<Object> key);
 
MaybeHandle<OrderedHashMap> OrderedHashMapHandler::AdjustRepresentation(
    Isolate* isolate, DirectHandle<SmallOrderedHashMap> table) {
  MaybeHandle<OrderedHashMap> new_table_candidate =
      OrderedHashMap::Allocate(isolate, OrderedHashTableMinSize);
  Handle<OrderedHashMap> new_table;
  if (!new_table_candidate.ToHandle(&new_table)) {
    return new_table_candidate;
  }
 
  // TODO(gsathya): Optimize the lookup to not re calc offsets. Also,
  // unhandlify this code as we preallocate the new backing store with
  // the proper capacity.
  for (InternalIndex entry : table->IterateEntries()) {
    DirectHandle<Object> key(table->KeyAt(entry), isolate);
    if (IsTheHole(*key, isolate)) continue;
    DirectHandle<Object> value(
        table->GetDataEntry(entry.as_int(), SmallOrderedHashMap::kValueIndex),
        isolate);
    new_table_candidate = OrderedHashMap::Add(isolate, new_table, key, value);
    if (!new_table_candidate.ToHandle(&new_table)) {
      return new_table_candidate;
    }
  }
 
  return new_table_candidate;
}
 
MaybeHandle<OrderedHashSet> OrderedHashSetHandler::AdjustRepresentation(
    Isolate* isolate, DirectHandle<SmallOrderedHashSet> table) {
  MaybeHandle<OrderedHashSet> new_table_candidate =
      OrderedHashSet::Allocate(isolate, OrderedHashTableMinSize);
  Handle<OrderedHashSet> new_table;
  if (!new_table_candidate.ToHandle(&new_table)) {
    return new_table_candidate;
  }
 
  // TODO(gsathya): Optimize the lookup to not re calc offsets. Also,
  // unhandlify this code as we preallocate the new backing store with
  // the proper capacity.
  for (InternalIndex entry : table->IterateEntries()) {
    DirectHandle<Object> key(table->KeyAt(entry), isolate);
    if (IsTheHole(*key, isolate)) continue;
    new_table_candidate = OrderedHashSet::Add(isolate, new_table, key);
    if (!new_table_candidate.ToHandle(&new_table)) {
      return new_table_candidate;
    }
  }
 
  return new_table_candidate;
}
 
MaybeHandle<OrderedNameDictionary>
OrderedNameDictionaryHandler::AdjustRepresentation(
    Isolate* isolate, DirectHandle<SmallOrderedNameDictionary> table) {
  MaybeHandle<OrderedNameDictionary> new_table_candidate =
      OrderedNameDictionary::Allocate(isolate, OrderedHashTableMinSize);
  Handle<OrderedNameDictionary> new_table;
  if (!new_table_candidate.ToHandle(&new_table)) {
    return new_table_candidate;
  }
 
  // TODO(gsathya): Optimize the lookup to not re calc offsets. Also,
  // unhandlify this code as we preallocate the new backing store with
  // the proper capacity.
  for (InternalIndex entry : table->IterateEntries()) {
    DirectHandle<Name> key(Cast<Name>(table->KeyAt(entry)), isolate);
    if (IsTheHole(*key, isolate)) continue;
    DirectHandle<Object> value(table->ValueAt(entry), isolate);
    PropertyDetails details = table->DetailsAt(entry);
    new_table_candidate =
        OrderedNameDictionary::Add(isolate, new_table, key, value, details);
    if (!new_table_candidate.ToHandle(&new_table)) {
      return new_table_candidate;
    }
  }
 
  return new_table_candidate;
}
 
MaybeHandle<HeapObject> OrderedHashMapHandler::Add(Isolate* isolate,
                                                   Handle<HeapObject> table,
                                                   DirectHandle<Object> key,
                                                   DirectHandle<Object> value) {
  if (IsSmallOrderedHashMap(*table)) {
    Handle<SmallOrderedHashMap> small_map = Cast<SmallOrderedHashMap>(table);
    MaybeHandle<SmallOrderedHashMap> new_map =
        SmallOrderedHashMap::Add(isolate, small_map, key, value);
    if (!new_map.is_null()) return new_map.ToHandleChecked();
 
    // We couldn't add to the small table, let's migrate to the
    // big table.
    MaybeHandle<OrderedHashMap> table_candidate =
        OrderedHashMapHandler::AdjustRepresentation(isolate, small_map);
    if (!table_candidate.ToHandle(&table)) {
      return table_candidate;
    }
  }
 
  DCHECK(IsOrderedHashMap(*table));
  return OrderedHashMap::Add(isolate, Cast<OrderedHashMap>(table), key, value);
}
 
MaybeHandle<HeapObject> OrderedHashSetHandler::Add(Isolate* isolate,
                                                   Handle<HeapObject> table,
                                                   DirectHandle<Object> key) {
  if (IsSmallOrderedHashSet(*table)) {
    Handle<SmallOrderedHashSet> small_set = Cast<SmallOrderedHashSet>(table);
    MaybeHandle<SmallOrderedHashSet> new_set =
        SmallOrderedHashSet::Add(isolate, small_set, key);
    if (!new_set.is_null()) return new_set.ToHandleChecked();
 
    // We couldn't add to the small table, let's migrate to the
    // big table.
    MaybeHandle<OrderedHashSet> table_candidate =
        OrderedHashSetHandler::AdjustRepresentation(isolate, small_set);
    if (!table_candidate.ToHandle(&table)) {
      return table_candidate;
    }
  }
 
  DCHECK(IsOrderedHashSet(*table));
  return OrderedHashSet::Add(isolate, Cast<OrderedHashSet>(table), key);
}
 
MaybeHandle<HeapObject> OrderedNameDictionaryHandler::Add(
    Isolate* isolate, Handle<HeapObject> table, DirectHandle<Name> key,
    DirectHandle<Object> value, PropertyDetails details) {
  if (IsSmallOrderedNameDictionary(*table)) {
    Handle<SmallOrderedNameDictionary> small_dict =
        Cast<SmallOrderedNameDictionary>(table);
    MaybeHandle<SmallOrderedNameDictionary> new_dict =
        SmallOrderedNameDictionary::Add(isolate, small_dict, key, value,
                                        details);
    if (!new_dict.is_null()) return new_dict.ToHandleChecked();
 
    // We couldn't add to the small table, let's migrate to the
    // big table.
    MaybeHandle<OrderedNameDictionary> table_candidate =
        OrderedNameDictionaryHandler::AdjustRepresentation(isolate, small_dict);
    if (!table_candidate.ToHandle(&table)) {
      return table_candidate;
    }
  }
 
  DCHECK(IsOrderedNameDictionary(*table));
  return OrderedNameDictionary::Add(isolate, Cast<OrderedNameDictionary>(table),
                                    key, value, details);
}
 
void OrderedNameDictionaryHandler::SetEntry(Tagged<HeapObject> table,
                                            InternalIndex entry,
                                            Tagged<Object> key,
                                            Tagged<Object> value,
                                            PropertyDetails details) {
  DisallowGarbageCollection no_gc;
  if (IsSmallOrderedNameDictionary(table)) {
    return Cast<SmallOrderedNameDictionary>(table)->SetEntry(entry, key, value,
                                                             details);
  }
 
  DCHECK(IsOrderedNameDictionary(table));
  return Cast<OrderedNameDictionary>(table)->SetEntry(InternalIndex(entry), key,
                                                      value, details);
}
 
InternalIndex OrderedNameDictionaryHandler::FindEntry(Isolate* isolate,
                                                      Tagged<HeapObject> table,
                                                      Tagged<Name> key) {
  DisallowGarbageCollection no_gc;
  if (IsSmallOrderedNameDictionary(table)) {
    return Cast<SmallOrderedNameDictionary>(table)->FindEntry(isolate, key);
  }
 
  DCHECK(IsOrderedNameDictionary(table));
  return Cast<OrderedNameDictionary>(table)->FindEntry(isolate, key);
}
 
Tagged<Object> OrderedNameDictionaryHandler::ValueAt(Tagged<HeapObject> table,
                                                     InternalIndex entry) {
  if (IsSmallOrderedNameDictionary(table)) {
    return Cast<SmallOrderedNameDictionary>(table)->ValueAt(entry);
  }
 
  DCHECK(IsOrderedNameDictionary(table));
  return Cast<OrderedNameDictionary>(table)->ValueAt(entry);
}
 
void OrderedNameDictionaryHandler::ValueAtPut(Tagged<HeapObject> table,
                                              InternalIndex entry,
                                              Tagged<Object> value) {
  if (IsSmallOrderedNameDictionary(table)) {
    return Cast<SmallOrderedNameDictionary>(table)->ValueAtPut(entry, value);
  }
 
  DCHECK(IsOrderedNameDictionary(table));
  Cast<OrderedNameDictionary>(table)->ValueAtPut(entry, value);
}
 
PropertyDetails OrderedNameDictionaryHandler::DetailsAt(
    Tagged<HeapObject> table, InternalIndex entry) {
  if (IsSmallOrderedNameDictionary(table)) {
    return Cast<SmallOrderedNameDictionary>(table)->DetailsAt(entry);
  }
 
  DCHECK(IsOrderedNameDictionary(table));
  return Cast<OrderedNameDictionary>(table)->DetailsAt(entry);
}
 
void OrderedNameDictionaryHandler::DetailsAtPut(Tagged<HeapObject> table,
                                                InternalIndex entry,
                                                PropertyDetails details) {
  if (IsSmallOrderedNameDictionary(table)) {
    return Cast<SmallOrderedNameDictionary>(table)->DetailsAtPut(entry,
                                                                 details);
  }
 
  DCHECK(IsOrderedNameDictionary(table));
  Cast<OrderedNameDictionary>(table)->DetailsAtPut(entry, details);
}
 
int OrderedNameDictionaryHandler::Hash(Tagged<HeapObject> table) {
  if (IsSmallOrderedNameDictionary(table)) {
    return Cast<SmallOrderedNameDictionary>(table)->Hash();
  }
 
  DCHECK(IsOrderedNameDictionary(table));
  return Cast<OrderedNameDictionary>(table)->Hash();
}
 
void OrderedNameDictionaryHandler::SetHash(Tagged<HeapObject> table, int hash) {
  if (IsSmallOrderedNameDictionary(table)) {
    return Cast<SmallOrderedNameDictionary>(table)->SetHash(hash);
  }
 
  DCHECK(IsOrderedNameDictionary(table));
  Cast<OrderedNameDictionary>(table)->SetHash(hash);
}
 
Tagged<Name> OrderedNameDictionaryHandler::KeyAt(Tagged<HeapObject> table,
                                                 InternalIndex entry) {
  if (IsSmallOrderedNameDictionary(table)) {
    return Cast<Name>(Cast<SmallOrderedNameDictionary>(table)->KeyAt(entry));
  }
 
  return Cast<Name>(
      Cast<OrderedNameDictionary>(table)->KeyAt(InternalIndex(entry)));
}
 
int OrderedNameDictionaryHandler::NumberOfElements(Tagged<HeapObject> table) {
  if (IsSmallOrderedNameDictionary(table)) {
    return Cast<SmallOrderedNameDictionary>(table)->NumberOfElements();
  }
 
  return Cast<OrderedNameDictionary>(table)->NumberOfElements();
}
 
int OrderedNameDictionaryHandler::Capacity(Tagged<HeapObject> table) {
  if (IsSmallOrderedNameDictionary(table)) {
    return Cast<SmallOrderedNameDictionary>(table)->Capacity();
  }
 
  return Cast<OrderedNameDictionary>(table)->Capacity();
}
 
DirectHandle<HeapObject> OrderedNameDictionaryHandler::Shrink(
    Isolate* isolate, Handle<HeapObject> table) {
  if (IsSmallOrderedNameDictionary(*table)) {
    Handle<SmallOrderedNameDictionary> small_dict =
        Cast<SmallOrderedNameDictionary>(table);
    return SmallOrderedNameDictionary::Shrink(isolate, small_dict);
  }
 
  Handle<OrderedNameDictionary> large_dict = Cast<OrderedNameDictionary>(table);
  return OrderedNameDictionary::Shrink(isolate, large_dict);
}
 
DirectHandle<HeapObject> OrderedNameDictionaryHandler::DeleteEntry(
    Isolate* isolate, Handle<HeapObject> table, InternalIndex entry) {
  DisallowGarbageCollection no_gc;
  if (IsSmallOrderedNameDictionary(*table)) {
    Handle<SmallOrderedNameDictionary> small_dict =
        Cast<SmallOrderedNameDictionary>(table);
    return SmallOrderedNameDictionary::DeleteEntry(isolate, small_dict, entry);
  }
 
  Handle<OrderedNameDictionary> large_dict = Cast<OrderedNameDictionary>(table);
  return OrderedNameDictionary::DeleteEntry(isolate, large_dict,
                                            InternalIndex(entry));
}
 
template <class Derived, class TableType>
void OrderedHashTableIterator<Derived, TableType>::Transition() {
  DisallowGarbageCollection no_gc;
  Tagged<TableType> table = Cast<TableType>(this->table());
  if (!table->IsObsolete()) return;
 
  int index = Smi::ToInt(this->index());
  DCHECK_LE(0, index);
  while (table->IsObsolete()) {
    Tagged<TableType> next_table = table->NextTable();
 
    if (index > 0) {
      int nod = table->NumberOfDeletedElements();
 
      if (nod == TableType::kClearedTableSentinel) {
        index = 0;
      } else {
        int old_index = index;
        for (int i = 0; i < nod; ++i) {
          int removed_index = table->RemovedIndexAt(i);
          if (removed_index >= old_index) break;
          --index;
        }
      }
    }
 
    table = next_table;
  }
 
  set_table(table);
  set_index(Smi::FromInt(index));
}
 
template <class Derived, class TableType>
bool OrderedHashTableIterator<Derived, TableType>::HasMore() {
  DisallowGarbageCollection no_gc;
  ReadOnlyRoots ro_roots = GetReadOnlyRoots();
 
  Transition();
 
  Tagged<TableType> table = Cast<TableType>(this->table());
  int index = Smi::ToInt(this->index());
  int used_capacity = table->UsedCapacity();
 
  while (index < used_capacity &&
         IsHashTableHole(table->KeyAt(InternalIndex(index)), ro_roots)) {
    index++;
  }
 
  set_index(Smi::FromInt(index));
 
  if (index < used_capacity) return true;
 
  set_table(TableType::GetEmpty(ro_roots));
  return false;
}
 
template bool
OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::HasMore();
 
template void
OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::MoveNext();
 
template Tagged<Object>
OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::CurrentKey();
 
template void
OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::Transition();
 
template bool
OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::HasMore();
 
template void
OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::MoveNext();
 
template Tagged<Object>
OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::CurrentKey();
 
template void
OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::Transition();
 
// Force instantiation of template instances class.
// Keep this at the end of this file
 
#define EXTERN_DEFINE_ORDERED_HASH_TABLE(DERIVED, ENTRY_SIZE)                 \
  template V8_EXPORT_PRIVATE MaybeIndirectHandle<DERIVED>                     \
  OrderedHashTable<DERIVED, ENTRY_SIZE>::EnsureCapacityForAdding(             \
      Isolate* isolate, IndirectHandle<DERIVED> table);                       \
  template V8_EXPORT_PRIVATE MaybeDirectHandle<DERIVED>                       \
  OrderedHashTable<DERIVED, ENTRY_SIZE>::EnsureCapacityForAdding(             \
      Isolate* isolate, DirectHandle<DERIVED> table);                         \
  template V8_EXPORT_PRIVATE IndirectHandle<DERIVED>                          \
  OrderedHashTable<DERIVED, ENTRY_SIZE>::Shrink(                              \
      Isolate* isolate, IndirectHandle<DERIVED> table);                       \
  template V8_EXPORT_PRIVATE DirectHandle<DERIVED>                            \
  OrderedHashTable<DERIVED, ENTRY_SIZE>::Shrink(Isolate* isolate,             \
                                                DirectHandle<DERIVED> table); \
  template V8_EXPORT_PRIVATE Handle<DERIVED>                                  \
  OrderedHashTable<DERIVED, ENTRY_SIZE>::Clear(Isolate* isolate,              \
                                               Handle<DERIVED> table);        \
  template V8_EXPORT_PRIVATE MaybeHandle<DERIVED>                             \
  OrderedHashTable<DERIVED, ENTRY_SIZE>::Allocate(                            \
      Isolate* isolate, int capacity, AllocationType allocation);             \
  template V8_EXPORT_PRIVATE bool                                             \
  OrderedHashTable<DERIVED, ENTRY_SIZE>::HasKey(                              \
      Isolate* isolate, Tagged<DERIVED> table, Tagged<Object> key);           \
  template V8_EXPORT_PRIVATE bool                                             \
  OrderedHashTable<DERIVED, ENTRY_SIZE>::Delete(                              \
      Isolate* isolate, Tagged<DERIVED> table, Tagged<Object> key);           \
  template V8_EXPORT_PRIVATE InternalIndex                                    \
  OrderedHashTable<DERIVED, ENTRY_SIZE>::FindEntry(Isolate* isolate,          \
                                                   Tagged<Object> key);
 
EXTERN_DEFINE_ORDERED_HASH_TABLE(OrderedHashSet, 1)
EXTERN_DEFINE_ORDERED_HASH_TABLE(OrderedHashMap, 2)
EXTERN_DEFINE_ORDERED_HASH_TABLE(OrderedNameDictionary, 3)
 
}  // namespace internal
}  // namespace v8