text: // 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/isolate.h"
  #include "src/objects-inl.h"
  #include "src/objects/js-collection-inl.h"
  #include "src/objects/ordered-hash-table-inl.h"
  
  namespace v8 {
  namespace internal {
  
  template <class Derived, int entrysize>
  Handle<Derived> OrderedHashTable<Derived, entrysize>::Allocate(
      Isolate* isolate, int capacity, PretenureFlag pretenure) {
    // 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(Max(kMinCapacity, capacity));
    if (capacity > MaxCapacity()) {
      isolate->heap()->FatalProcessOutOfMemory("invalid table size");
    }
    int num_buckets = capacity / kLoadFactor;
    Handle<FixedArray> backing_store = isolate->factory()->NewFixedArrayWithMap(
        Derived::GetMapRootIndex(),
        HashTableStartIndex() + num_buckets + (capacity * kEntrySize), pretenure);
    Handle<Derived> table = Handle<Derived>::cast(backing_store);
    for (int i = 0; i < num_buckets; ++i) {
      table->set(HashTableStartIndex() + i, Smi::FromInt(kNotFound));
    }
    table->SetNumberOfBuckets(num_buckets);
    table->SetNumberOfElements(0);
    table->SetNumberOfDeletedElements(0);
    return table;
  }
  
  template <class Derived, int entrysize>
  Handle<Derived> OrderedHashTable<Derived, entrysize>::EnsureGrowable(
      Isolate* isolate, Handle<Derived> table) {
    DCHECK(!table->IsObsolete());
  
    int nof = table->NumberOfElements();
    int nod = table->NumberOfDeletedElements();
    int capacity = table->Capacity();
    if ((nof + nod) < capacity) return table;
    // 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.
    return Derived::Rehash(isolate, table,
                           (nod < (capacity >> 1)) ? capacity << 1 : capacity);
  }
  
  template <class Derived, int entrysize>
  Handle<Derived> OrderedHashTable<Derived, entrysize>::Shrink(
      Isolate* isolate, Handle<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);
  }
  
  template <class Derived, int entrysize>
  Handle<Derived> OrderedHashTable<Derived, entrysize>::Clear(
      Isolate* isolate, Handle<Derived> table) {
    DCHECK(!table->IsObsolete());
  
    Handle<Derived> new_table =
        Allocate(isolate, kMinCapacity,
                 Heap::InYoungGeneration(*table) ? NOT_TENURED : TENURED);
  
    table->SetNextTable(*new_table);
    table->SetNumberOfDeletedElements(kClearedTableSentinel);
  
    return new_table;
  }
  
  template <class Derived, int entrysize>
  bool OrderedHashTable<Derived, entrysize>::HasKey(Isolate* isolate,
                                                    Derived table, Object key) {
    DCHECK_IMPLIES(entrysize == 1, table->IsOrderedHashSet());
    DCHECK_IMPLIES(entrysize == 2, table->IsOrderedHashMap());
    DisallowHeapAllocation no_gc;
    int entry = table->FindEntry(isolate, key);
    return entry != kNotFound;
  }
  
  template <class Derived, int entrysize>
  int OrderedHashTable<Derived, entrysize>::FindEntry(Isolate* isolate,
                                                      Object key) {
    int entry;
    // This special cases for Smi, so that we avoid the HandleScope
    // creation below.
    if (key->IsSmi()) {
      uint32_t hash = ComputeUnseededHash(Smi::ToInt(key));
      entry = HashToEntry(hash & Smi::kMaxValue);
    } else {
      HandleScope scope(isolate);
      Object hash = key->GetHash();
      // If the object does not have an identity hash, it was never used as a key
      if (hash->IsUndefined(isolate)) return kNotFound;
      entry = HashToEntry(Smi::ToInt(hash));
    }
  
    // Walk the chain in the bucket to find the key.
    while (entry != kNotFound) {
      Object candidate_key = KeyAt(entry);
      if (candidate_key->SameValueZero(key)) break;
      entry = NextChainEntry(entry);
    }
  
    return entry;
  }
  
  Handle<OrderedHashSet> OrderedHashSet::Add(Isolate* isolate,
                                             Handle<OrderedHashSet> table,
                                             Handle<Object> key) {
    int hash = key->GetOrCreateHash(isolate)->value();
    int entry = table->HashToEntry(hash);
    // Walk the chain of the bucket and try finding the key.
    while (entry != kNotFound) {
      Object candidate_key = table->KeyAt(entry);
      // Do not add if we have the key already
      if (candidate_key->SameValueZero(*key)) return table;
      entry = table->NextChainEntry(entry);
    }
  
    table = OrderedHashSet::EnsureGrowable(isolate, table);
    // Read the existing bucket values.
    int bucket = table->HashToBucket(hash);
    int previous_entry = table->HashToEntry(hash);
    int nof = table->NumberOfElements();
    // Insert a new entry at the end,
    int new_entry = nof + table->NumberOfDeletedElements();
    int new_index = table->EntryToIndex(new_entry);
    table->set(new_index, *key);
    table->set(new_index + kChainOffset, Smi::FromInt(previous_entry));
    // and point the bucket to the new entry.
    table->set(HashTableStartIndex() + bucket, Smi::FromInt(new_entry));
    table->SetNumberOfElements(nof + 1);
    return table;
  }
  
  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 = Handle<FixedArray>::cast(table);
    // From this point on table is no longer a valid OrderedHashSet.
    result->set_map(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);
      Object key = table->get(index);
      if (convert == GetKeysConversion::kConvertToString) {
        uint32_t index_value;
        if (key->ToArrayIndex(&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(key->IsName());
        }
      }
      result->set(i, key);
    }
    return FixedArray::ShrinkOrEmpty(isolate, result, length);
  }
  
  HeapObject OrderedHashSet::GetEmpty(ReadOnlyRoots ro_roots) {
    return ro_roots.empty_ordered_hash_set();
  }
  
  HeapObject OrderedHashMap::GetEmpty(ReadOnlyRoots ro_roots) {
    return ro_roots.empty_ordered_hash_map();
  }
  
  template <class Derived, int entrysize>
  Handle<Derived> OrderedHashTable<Derived, entrysize>::Rehash(
      Isolate* isolate, Handle<Derived> table, int new_capacity) {
    DCHECK(!table->IsObsolete());
  
    Handle<Derived> new_table = Derived::Allocate(
        isolate, new_capacity,
        Heap::InYoungGeneration(*table) ? NOT_TENURED : TENURED);
    int nof = table->NumberOfElements();
    int nod = table->NumberOfDeletedElements();
    int new_buckets = new_table->NumberOfBuckets();
    int new_entry = 0;
    int removed_holes_index = 0;
  
    DisallowHeapAllocation no_gc;
    for (int old_entry = 0; old_entry < (nof + nod); ++old_entry) {
      Object key = table->KeyAt(old_entry);
      if (key->IsTheHole(isolate)) {
        table->SetRemovedIndexAt(removed_holes_index++, old_entry);
        continue;
      }
  
      Object hash = key->GetHash();
      int bucket = Smi::ToInt(hash) & (new_buckets - 1);
      Object chain_entry = new_table->get(HashTableStartIndex() + bucket);
      new_table->set(HashTableStartIndex() + bucket, Smi::FromInt(new_entry));
      int new_index = new_table->EntryToIndex(new_entry);
      int old_index = table->EntryToIndex(old_entry);
      for (int i = 0; i < entrysize; ++i) {
        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(nod, removed_holes_index);
  
    new_table->SetNumberOfElements(nof);
    table->SetNextTable(*new_table);
  
    return new_table;
  }
  
  Handle<OrderedHashSet> OrderedHashSet::Rehash(Isolate* isolate,
                                                Handle<OrderedHashSet> table,
                                                int new_capacity) {
    return OrderedHashTable<OrderedHashSet, 1>::Rehash(isolate, table,
                                                       new_capacity);
  }
  
  Handle<OrderedHashMap> OrderedHashMap::Rehash(Isolate* isolate,
                                                Handle<OrderedHashMap> table,
                                                int new_capacity) {
    return OrderedHashTable<OrderedHashMap, 2>::Rehash(isolate, table,
                                                       new_capacity);
  }
  
  Handle<OrderedNameDictionary> OrderedNameDictionary::Rehash(
      Isolate* isolate, Handle<OrderedNameDictionary> table, int new_capacity) {
    Handle<OrderedNameDictionary> new_table =
        OrderedHashTable<OrderedNameDictionary, 3>::Rehash(isolate, table,
                                                           new_capacity);
    new_table->SetHash(table->Hash());
    return new_table;
  }
  
  template <class Derived, int entrysize>
  bool OrderedHashTable<Derived, entrysize>::Delete(Isolate* isolate,
                                                    Derived table, Object key) {
    DisallowHeapAllocation no_gc;
    int entry = table->FindEntry(isolate, key);
    if (entry == kNotFound) return false;
  
    int nof = table->NumberOfElements();
    int nod = table->NumberOfDeletedElements();
    int index = table->EntryToIndex(entry);
  
    Object hole = ReadOnlyRoots(isolate).the_hole_value();
    for (int i = 0; i < entrysize; ++i) {
      table->set(index + i, hole);
    }
  
    table->SetNumberOfElements(nof - 1);
    table->SetNumberOfDeletedElements(nod + 1);
  
    return true;
  }
  
  Address OrderedHashMap::GetHash(Isolate* isolate, Address raw_key) {
    DisallowHeapAllocation no_gc;
    Object key(raw_key);
    Object hash = key->GetHash();
    // If the object does not have an identity hash, it was never used as a key
    if (hash->IsUndefined(isolate)) return Smi::FromInt(-1).ptr();
    DCHECK(hash->IsSmi());
    DCHECK_GE(Smi::cast(hash)->value(), 0);
    return hash.ptr();
  }
  
  Handle<OrderedHashMap> OrderedHashMap::Add(Isolate* isolate,
                                             Handle<OrderedHashMap> table,
                                             Handle<Object> key,
                                             Handle<Object> value) {
    int hash = key->GetOrCreateHash(isolate)->value();
    int entry = table->HashToEntry(hash);
    // Walk the chain of the bucket and try finding the key.
    {
      DisallowHeapAllocation no_gc;
      Object raw_key = *key;
      while (entry != kNotFound) {
        Object candidate_key = table->KeyAt(entry);
        // Do not add if we have the key already
        if (candidate_key->SameValueZero(raw_key)) return table;
        entry = table->NextChainEntry(entry);
      }
    }
  
    table = OrderedHashMap::EnsureGrowable(isolate, table);
    // Read the existing bucket values.
    int bucket = table->HashToBucket(hash);
    int previous_entry = table->HashToEntry(hash);
    int nof = table->NumberOfElements();
    // Insert a new entry at the end,
    int new_entry = nof + table->NumberOfDeletedElements();
    int new_index = table->EntryToIndex(new_entry);
    table->set(new_index, *key);
    table->set(new_index + kValueOffset, *value);
    table->set(new_index + kChainOffset, Smi::FromInt(previous_entry));
    // and point the bucket to the new entry.
    table->set(HashTableStartIndex() + bucket, Smi::FromInt(new_entry));
    table->SetNumberOfElements(nof + 1);
    return table;
  }
  
  template <>
  int OrderedHashTable<OrderedNameDictionary, 3>::FindEntry(Isolate* isolate,
                                                            Object key) {
    DisallowHeapAllocation no_gc;
  
    DCHECK(key->IsUniqueName());
    Name raw_key = Name::cast(key);
  
    int entry = HashToEntry(raw_key->Hash());
    while (entry != kNotFound) {
      Object candidate_key = KeyAt(entry);
      DCHECK(candidate_key->IsTheHole() ||
             Name::cast(candidate_key)->IsUniqueName());
      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.
      entry = NextChainEntry(entry);
    }
  
    return kNotFound;
  }
  
  Handle<OrderedNameDictionary> OrderedNameDictionary::Add(
      Isolate* isolate, Handle<OrderedNameDictionary> table, Handle<Name> key,
      Handle<Object> value, PropertyDetails details) {
    DCHECK_EQ(kNotFound, table->FindEntry(isolate, *key));
  
    table = OrderedNameDictionary::EnsureGrowable(isolate, table);
    // Read the existing bucket values.
    int hash = key->Hash();
    int bucket = table->HashToBucket(hash);
    int previous_entry = table->HashToEntry(hash);
    int nof = table->NumberOfElements();
    // Insert a new entry at the end,
    int new_entry = nof + table->NumberOfDeletedElements();
    int new_index = table->EntryToIndex(new_entry);
    table->set(new_index, *key);
    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).
    table->set(new_index + kPropertyDetailsOffset, details.AsSmi());
  
    table->set(new_index + kChainOffset, Smi::FromInt(previous_entry));
    // and point the bucket to the new entry.
    table->set(HashTableStartIndex() + bucket, Smi::FromInt(new_entry));
    table->SetNumberOfElements(nof + 1);
    return table;
  }
  
  void OrderedNameDictionary::SetEntry(Isolate* isolate, int entry, Object key,
                                       Object value, PropertyDetails details) {
    DisallowHeapAllocation gc;
    DCHECK_IMPLIES(!key->IsName(), key->IsTheHole(isolate));
    DisallowHeapAllocation 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, int entry) {
    DCHECK_NE(entry, kNotFound);
  
    Object hole = ReadOnlyRoots(isolate).the_hole_value();
    PropertyDetails details = PropertyDetails::Empty();
    table->SetEntry(isolate, entry, hole, hole, details);
  
    int nof = table->NumberOfElements();
    table->SetNumberOfElements(nof - 1);
    int nod = table->NumberOfDeletedElements();
    table->SetNumberOfDeletedElements(nod + 1);
  
    return Shrink(isolate, table);
  }
  
  Handle<OrderedHashSet> OrderedHashSet::Allocate(Isolate* isolate, int capacity,
                                                  PretenureFlag pretenure) {
    return OrderedHashTable<OrderedHashSet, 1>::Allocate(isolate, capacity,
                                                         pretenure);
  }
  
  Handle<OrderedHashMap> OrderedHashMap::Allocate(Isolate* isolate, int capacity,
                                                  PretenureFlag pretenure) {
    return OrderedHashTable<OrderedHashMap, 2>::Allocate(isolate, capacity,
                                                         pretenure);
  }
  
  Handle<OrderedNameDictionary> OrderedNameDictionary::Allocate(
      Isolate* isolate, int capacity, PretenureFlag pretenure) {
    Handle<OrderedNameDictionary> table =
        OrderedHashTable<OrderedNameDictionary, 3>::Allocate(isolate, capacity,
                                                             pretenure);
    table->SetHash(PropertyArray::kNoHashSentinel);
    return table;
  }
  
  template Handle<OrderedHashSet>
  OrderedHashTable<OrderedHashSet, 1>::EnsureGrowable(
      Isolate* isolate, Handle<OrderedHashSet> table);
  
  template Handle<OrderedHashSet> OrderedHashTable<OrderedHashSet, 1>::Shrink(
      Isolate* isolate, Handle<OrderedHashSet> table);
  
  template Handle<OrderedHashSet> OrderedHashTable<OrderedHashSet, 1>::Clear(
      Isolate* isolate, Handle<OrderedHashSet> table);
  
  template bool OrderedHashTable<OrderedHashSet, 1>::HasKey(Isolate* isolate,
                                                            OrderedHashSet table,
                                                            Object key);
  
  template bool OrderedHashTable<OrderedHashSet, 1>::Delete(Isolate* isolate,
                                                            OrderedHashSet table,
                                                            Object key);
  
  template int OrderedHashTable<OrderedHashSet, 1>::FindEntry(Isolate* isolate,
                                                              Object key);
  
  template Handle<OrderedHashMap>
  OrderedHashTable<OrderedHashMap, 2>::EnsureGrowable(
      Isolate* isolate, Handle<OrderedHashMap> table);
  
  template Handle<OrderedHashMap> OrderedHashTable<OrderedHashMap, 2>::Shrink(
      Isolate* isolate, Handle<OrderedHashMap> table);
  
  template Handle<OrderedHashMap> OrderedHashTable<OrderedHashMap, 2>::Clear(
      Isolate* isolate, Handle<OrderedHashMap> table);
  
  template bool OrderedHashTable<OrderedHashMap, 2>::HasKey(Isolate* isolate,
                                                            OrderedHashMap table,
                                                            Object key);
  
  template bool OrderedHashTable<OrderedHashMap, 2>::Delete(Isolate* isolate,
                                                            OrderedHashMap table,
                                                            Object key);
  
  template int OrderedHashTable<OrderedHashMap, 2>::FindEntry(Isolate* isolate,
                                                              Object key);
  
  template Handle<OrderedNameDictionary>
  OrderedHashTable<OrderedNameDictionary, 3>::Shrink(
      Isolate* isolate, Handle<OrderedNameDictionary> table);
  
  template Handle<OrderedNameDictionary>
  OrderedHashTable<OrderedNameDictionary, 3>::EnsureGrowable(
      Isolate* isolate, Handle<OrderedNameDictionary> table);
  
  template <>
  Handle<SmallOrderedHashSet>
  SmallOrderedHashTable<SmallOrderedHashSet>::Allocate(Isolate* isolate,
                                                       int capacity,
                                                       PretenureFlag pretenure) {
    return isolate->factory()->NewSmallOrderedHashSet(capacity, pretenure);
  }
  
  template <>
  Handle<SmallOrderedHashMap>
  SmallOrderedHashTable<SmallOrderedHashMap>::Allocate(Isolate* isolate,
                                                       int capacity,
                                                       PretenureFlag pretenure) {
    return isolate->factory()->NewSmallOrderedHashMap(capacity, pretenure);
  }
  
  template <>
  Handle<SmallOrderedNameDictionary>
  SmallOrderedHashTable<SmallOrderedNameDictionary>::Allocate(
      Isolate* isolate, int capacity, PretenureFlag pretenure) {
    return isolate->factory()->NewSmallOrderedNameDictionary(capacity, pretenure);
  }
  
  template <class Derived>
  void SmallOrderedHashTable<Derived>::Initialize(Isolate* isolate,
                                                  int capacity) {
    DisallowHeapAllocation no_gc;
    int num_buckets = capacity / kLoadFactor;
    int num_chains = capacity;
  
    SetNumberOfBuckets(num_buckets);
    SetNumberOfElements(0);
    SetNumberOfDeletedElements(0);
  
    Address hashtable_start = GetHashTableStartAddress(capacity);
    memset(reinterpret_cast<byte*>(hashtable_start), kNotFound,
           num_buckets + num_chains);
  
    if (Heap::InYoungGeneration(*this)) {
      MemsetTagged(RawField(DataTableStartOffset()),
                   ReadOnlyRoots(isolate).the_hole_value(),
                   capacity * Derived::kEntrySize);
    } else {
      for (int i = 0; i < capacity; i++) {
        for (int j = 0; j < Derived::kEntrySize; j++) {
          SetDataEntry(i, j, ReadOnlyRoots(isolate).the_hole_value());
        }
      }
    }
  
  #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, Handle<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>();
      }
    }
  
    int hash = key->GetOrCreateHash(isolate)->value();
    int nof = table->NumberOfElements();
  
    // Read the existing bucket values.
    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, SmallOrderedHashSet::kKeyIndex, *key);
    table->SetFirstEntry(bucket, new_entry);
    table->SetNextEntry(new_entry, previous_entry);
  
    // and update book keeping.
    table->SetNumberOfElements(nof + 1);
  
    return table;
  }
  
  MaybeHandle<SmallOrderedHashMap> SmallOrderedHashMap::Add(
      Isolate* isolate, Handle<SmallOrderedHashMap> table, Handle<Object> key,
      Handle<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>();
      }
    }
  
    int hash = key->GetOrCreateHash(isolate)->value();
    int nof = table->NumberOfElements();
  
    // Read the existing bucket values.
    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, SmallOrderedHashMap::kValueIndex, *value);
    table->SetDataEntry(new_entry, SmallOrderedHashMap::kKeyIndex, *key);
    table->SetFirstEntry(bucket, new_entry);
    table->SetNextEntry(new_entry, previous_entry);
  
    // and update book keeping.
    table->SetNumberOfElements(nof + 1);
  
    return table;
  }
  
  template <>
  int SmallOrderedHashTable<SmallOrderedNameDictionary>::FindEntry(
      Isolate* isolate, Object key) {
    DisallowHeapAllocation no_gc;
    DCHECK(key->IsUniqueName());
    Name raw_key = Name::cast(key);
  
    int entry = HashToFirstEntry(raw_key->Hash());
  
    // Walk the chain in the bucket to find the key.
    while (entry != kNotFound) {
      Object candidate_key = KeyAt(entry);
      if (candidate_key == key) return entry;
      entry = GetNextEntry(entry);
    }
  
    return kNotFound;
  }
  
  MaybeHandle<SmallOrderedNameDictionary> SmallOrderedNameDictionary::Add(
      Isolate* isolate, Handle<SmallOrderedNameDictionary> table,
      Handle<Name> key, Handle<Object> value, PropertyDetails details) {
    DCHECK_EQ(kNotFound, table->FindEntry(isolate, *key));
  
    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(Isolate* isolate, int entry,
                                            Object key, Object value,
                                            PropertyDetails details) {
    DCHECK_IMPLIES(!key->IsName(), key->IsTheHole(isolate));
    SetDataEntry(entry, SmallOrderedNameDictionary::kValueIndex, value);
    SetDataEntry(entry, SmallOrderedNameDictionary::kKeyIndex, key);
  
    // TODO(gsathya): PropertyDetails should be stored as part of the
    // data table to save more memory.
    SetDataEntry(entry, SmallOrderedNameDictionary::kPropertyDetailsIndex,
                 details.AsSmi());
  }
  
  template <class Derived>
  bool SmallOrderedHashTable<Derived>::HasKey(Isolate* isolate,
                                              Handle<Object> key) {
    DisallowHeapAllocation no_gc;
    return FindEntry(isolate, *key) != kNotFound;
  }
  
  template <class Derived>
  bool SmallOrderedHashTable<Derived>::Delete(Isolate* isolate, Derived table,
                                              Object key) {
    DisallowHeapAllocation no_gc;
    int entry = table->FindEntry(isolate, key);
    if (entry == kNotFound) return false;
  
    int nof = table->NumberOfElements();
    int nod = table->NumberOfDeletedElements();
  
    Object hole = ReadOnlyRoots(isolate).the_hole_value();
    for (int j = 0; j < Derived::kEntrySize; j++) {
      table->SetDataEntry(entry, j, hole);
    }
  
    table->SetNumberOfElements(nof - 1);
    table->SetNumberOfDeletedElements(nod + 1);
  
    return true;
  }
  
  Handle<SmallOrderedNameDictionary> SmallOrderedNameDictionary::DeleteEntry(
      Isolate* isolate, Handle<SmallOrderedNameDictionary> table, int entry) {
    DCHECK_NE(entry, kNotFound);
    {
      DisallowHeapAllocation no_gc;
      Object hole = ReadOnlyRoots(isolate).the_hole_value();
      PropertyDetails details = PropertyDetails::Empty();
      table->SetEntry(isolate, entry, hole, 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,
        Heap::InYoungGeneration(*table) ? NOT_TENURED : TENURED);
    int nof = table->NumberOfElements();
    int nod = table->NumberOfDeletedElements();
    int new_entry = 0;
  
    {
      DisallowHeapAllocation no_gc;
      for (int old_entry = 0; old_entry < (nof + nod); ++old_entry) {
        Object key = table->KeyAt(old_entry);
        if (key->IsTheHole(isolate)) continue;
  
        int hash = Smi::ToInt(key->GetHash());
        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) {
          Object value = table->GetDataEntry(old_entry, i);
          new_table->SetDataEntry(new_entry, i, value);
        }
  
        ++new_entry;
      }
  
      new_table->SetNumberOfElements(nof);
    }
    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>
  int SmallOrderedHashTable<Derived>::FindEntry(Isolate* isolate, Object key) {
    DisallowHeapAllocation no_gc;
    Object hash = key->GetHash();
  
    if (hash->IsUndefined(isolate)) return kNotFound;
    int entry = HashToFirstEntry(Smi::ToInt(hash));
  
    // Walk the chain in the bucket to find the key.
    while (entry != kNotFound) {
      Object candidate_key = KeyAt(entry);
      if (candidate_key->SameValueZero(key)) return entry;
      entry = GetNextEntry(entry);
    }
    return kNotFound;
  }
  
  template bool SmallOrderedHashTable<SmallOrderedHashSet>::HasKey(
      Isolate* isolate, Handle<Object> key);
  template Handle<SmallOrderedHashSet>
  SmallOrderedHashTable<SmallOrderedHashSet>::Rehash(
      Isolate* isolate, Handle<SmallOrderedHashSet> table, int new_capacity);
  template Handle<SmallOrderedHashSet>
  SmallOrderedHashTable<SmallOrderedHashSet>::Shrink(
      Isolate* isolate, Handle<SmallOrderedHashSet> table);
  template MaybeHandle<SmallOrderedHashSet>
  SmallOrderedHashTable<SmallOrderedHashSet>::Grow(
      Isolate* isolate, Handle<SmallOrderedHashSet> table);
  template void SmallOrderedHashTable<SmallOrderedHashSet>::Initialize(
      Isolate* isolate, int capacity);
  
  template bool SmallOrderedHashTable<SmallOrderedHashMap>::HasKey(
      Isolate* isolate, Handle<Object> key);
  template Handle<SmallOrderedHashMap>
  SmallOrderedHashTable<SmallOrderedHashMap>::Rehash(
      Isolate* isolate, Handle<SmallOrderedHashMap> table, int new_capacity);
  template Handle<SmallOrderedHashMap>
  SmallOrderedHashTable<SmallOrderedHashMap>::Shrink(
      Isolate* isolate, Handle<SmallOrderedHashMap> table);
  template MaybeHandle<SmallOrderedHashMap>
  SmallOrderedHashTable<SmallOrderedHashMap>::Grow(
      Isolate* isolate, Handle<SmallOrderedHashMap> table);
  template void SmallOrderedHashTable<SmallOrderedHashMap>::Initialize(
      Isolate* isolate, int capacity);
  
  template bool SmallOrderedHashTable<SmallOrderedHashMap>::Delete(
      Isolate* isolate, SmallOrderedHashMap table, Object key);
  template bool SmallOrderedHashTable<SmallOrderedHashSet>::Delete(
      Isolate* isolate, SmallOrderedHashSet table, Object key);
  
  template void SmallOrderedHashTable<SmallOrderedNameDictionary>::Initialize(
      Isolate* isolate, int capacity);
  template Handle<SmallOrderedNameDictionary>
  SmallOrderedHashTable<SmallOrderedNameDictionary>::Shrink(
      Isolate* isolate, Handle<SmallOrderedNameDictionary> table);
  
  template <class SmallTable, class LargeTable>
  Handle<HeapObject> OrderedHashTableHandler<SmallTable, LargeTable>::Allocate(
      Isolate* isolate, int capacity) {
    if (capacity < SmallTable::kMaxCapacity) {
      return SmallTable::Allocate(isolate, capacity);
    }
  
    return LargeTable::Allocate(isolate, capacity);
  }
  
  template Handle<HeapObject>
  OrderedHashTableHandler<SmallOrderedHashSet, OrderedHashSet>::Allocate(
      Isolate* isolate, int capacity);
  template Handle<HeapObject>
  OrderedHashTableHandler<SmallOrderedHashMap, OrderedHashMap>::Allocate(
      Isolate* isolate, int capacity);
  template Handle<HeapObject>
  OrderedHashTableHandler<SmallOrderedNameDictionary,
                          OrderedNameDictionary>::Allocate(Isolate* isolate,
                                                           int capacity);
  
  template <class SmallTable, class LargeTable>
  bool OrderedHashTableHandler<SmallTable, LargeTable>::Delete(
      Handle<HeapObject> table, Handle<Object> key) {
    if (SmallTable::Is(table)) {
      return SmallTable::Delete(Handle<SmallTable>::cast(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(Handle<LargeTable>::cast(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 Handle<SmallTable>::cast(table)->HasKey(isolate, key);
    }
  
    DCHECK(LargeTable::Is(table));
    return LargeTable::HasKey(isolate, LargeTable::cast(*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);
  
  Handle<OrderedHashMap> OrderedHashMapHandler::AdjustRepresentation(
      Isolate* isolate, Handle<SmallOrderedHashMap> table) {
    Handle<OrderedHashMap> new_table =
        OrderedHashMap::Allocate(isolate, OrderedHashTableMinSize);
    int nof = table->NumberOfElements();
    int nod = table->NumberOfDeletedElements();
  
    // 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 (int entry = 0; entry < (nof + nod); ++entry) {
      Handle<Object> key = handle(table->KeyAt(entry), isolate);
      if (key->IsTheHole(isolate)) continue;
      Handle<Object> value = handle(
          table->GetDataEntry(entry, SmallOrderedHashMap::kValueIndex), isolate);
      new_table = OrderedHashMap::Add(isolate, new_table, key, value);
    }
  
    return new_table;
  }
  
  Handle<OrderedHashSet> OrderedHashSetHandler::AdjustRepresentation(
      Isolate* isolate, Handle<SmallOrderedHashSet> table) {
    Handle<OrderedHashSet> new_table =
        OrderedHashSet::Allocate(isolate, OrderedHashTableMinSize);
    int nof = table->NumberOfElements();
    int nod = table->NumberOfDeletedElements();
  
    // 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 (int entry = 0; entry < (nof + nod); ++entry) {
      Handle<Object> key = handle(table->KeyAt(entry), isolate);
      if (key->IsTheHole(isolate)) continue;
      new_table = OrderedHashSet::Add(isolate, new_table, key);
    }
  
    return new_table;
  }
  
  Handle<OrderedNameDictionary>
  OrderedNameDictionaryHandler::AdjustRepresentation(
      Isolate* isolate, Handle<SmallOrderedNameDictionary> table) {
    Handle<OrderedNameDictionary> new_table =
        OrderedNameDictionary::Allocate(isolate, OrderedHashTableMinSize);
    int nof = table->NumberOfElements();
    int nod = table->NumberOfDeletedElements();
  
    // 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 (int entry = 0; entry < (nof + nod); ++entry) {
      Handle<Name> key(Name::cast(table->KeyAt(entry)), isolate);
      if (key->IsTheHole(isolate)) continue;
      Handle<Object> value(table->ValueAt(entry), isolate);
      PropertyDetails details = table->DetailsAt(entry);
      new_table =
          OrderedNameDictionary::Add(isolate, new_table, key, value, details);
    }
  
    return new_table;
  }
  
  Handle<HeapObject> OrderedHashMapHandler::Add(Isolate* isolate,
                                                Handle<HeapObject> table,
                                                Handle<Object> key,
                                                Handle<Object> value) {
    if (table->IsSmallOrderedHashMap()) {
      Handle<SmallOrderedHashMap> small_map =
          Handle<SmallOrderedHashMap>::cast(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.
      table = OrderedHashMapHandler::AdjustRepresentation(isolate, small_map);
    }
  
    DCHECK(table->IsOrderedHashMap());
    return OrderedHashMap::Add(isolate, Handle<OrderedHashMap>::cast(table), key,
                               value);
  }
  
  Handle<HeapObject> OrderedHashSetHandler::Add(Isolate* isolate,
                                                Handle<HeapObject> table,
                                                Handle<Object> key) {
    if (table->IsSmallOrderedHashSet()) {
      Handle<SmallOrderedHashSet> small_set =
          Handle<SmallOrderedHashSet>::cast(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.
      table = OrderedHashSetHandler::AdjustRepresentation(isolate, small_set);
    }
  
    DCHECK(table->IsOrderedHashSet());
    return OrderedHashSet::Add(isolate, Handle<OrderedHashSet>::cast(table), key);
  }
  
  Handle<HeapObject> OrderedNameDictionaryHandler::Add(Isolate* isolate,
                                                       Handle<HeapObject> table,
                                                       Handle<Name> key,
                                                       Handle<Object> value,
                                                       PropertyDetails details) {
    if (table->IsSmallOrderedNameDictionary()) {
      Handle<SmallOrderedNameDictionary> small_dict =
          Handle<SmallOrderedNameDictionary>::cast(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.
      table =
          OrderedNameDictionaryHandler::AdjustRepresentation(isolate, small_dict);
    }
  
    DCHECK(table->IsOrderedNameDictionary());
    return OrderedNameDictionary::Add(
        isolate, Handle<OrderedNameDictionary>::cast(table), key, value, details);
  }
  
  void OrderedNameDictionaryHandler::SetEntry(Isolate* isolate, HeapObject table,
                                              int entry, Object key, Object value,
                                              PropertyDetails details) {
    DisallowHeapAllocation no_gc;
    if (table->IsSmallOrderedNameDictionary()) {
      return SmallOrderedNameDictionary::cast(table)->SetEntry(
          isolate, entry, key, value, details);
    }
  
    DCHECK(table->IsOrderedNameDictionary());
    return OrderedNameDictionary::cast(table)->SetEntry(isolate, entry, key,
                                                        value, details);
  }
  
  int OrderedNameDictionaryHandler::FindEntry(Isolate* isolate, HeapObject table,
                                              Name key) {
    DisallowHeapAllocation no_gc;
    if (table->IsSmallOrderedNameDictionary()) {
      int entry =
          SmallOrderedNameDictionary::cast(table)->FindEntry(isolate, key);
      return entry == SmallOrderedNameDictionary::kNotFound
                 ? OrderedNameDictionaryHandler::kNotFound
                 : entry;
    }
  
    DCHECK(table->IsOrderedNameDictionary());
    int entry = OrderedNameDictionary::cast(table)->FindEntry(isolate, key);
    return entry == OrderedNameDictionary::kNotFound
               ? OrderedNameDictionaryHandler::kNotFound
               : entry;
  }
  
  Object OrderedNameDictionaryHandler::ValueAt(HeapObject table, int entry) {
    if (table->IsSmallOrderedNameDictionary()) {
      return SmallOrderedNameDictionary::cast(table)->ValueAt(entry);
    }
  
    DCHECK(table->IsOrderedNameDictionary());
    return OrderedNameDictionary::cast(table)->ValueAt(entry);
  }
  
  void OrderedNameDictionaryHandler::ValueAtPut(HeapObject table, int entry,
                                                Object value) {
    if (table->IsSmallOrderedNameDictionary()) {
      return SmallOrderedNameDictionary::cast(table)->ValueAtPut(entry, value);
    }
  
    DCHECK(table->IsOrderedNameDictionary());
    OrderedNameDictionary::cast(table)->ValueAtPut(entry, value);
  }
  
  PropertyDetails OrderedNameDictionaryHandler::DetailsAt(HeapObject table,
                                                          int entry) {
    if (table->IsSmallOrderedNameDictionary()) {
      return SmallOrderedNameDictionary::cast(table)->DetailsAt(entry);
    }
  
    DCHECK(table->IsOrderedNameDictionary());
    return OrderedNameDictionary::cast(table)->DetailsAt(entry);
  }
  
  void OrderedNameDictionaryHandler::DetailsAtPut(HeapObject table, int entry,
                                                  PropertyDetails details) {
    if (table->IsSmallOrderedNameDictionary()) {
      return SmallOrderedNameDictionary::cast(table)->DetailsAtPut(entry,
                                                                   details);
    }
  
    DCHECK(table->IsOrderedNameDictionary());
    OrderedNameDictionary::cast(table)->DetailsAtPut(entry, details);
  }
  
  int OrderedNameDictionaryHandler::Hash(HeapObject table) {
    if (table->IsSmallOrderedNameDictionary()) {
      return SmallOrderedNameDictionary::cast(table)->Hash();
    }
  
    DCHECK(table->IsOrderedNameDictionary());
    return OrderedNameDictionary::cast(table)->Hash();
  }
  
  void OrderedNameDictionaryHandler::SetHash(HeapObject table, int hash) {
    if (table->IsSmallOrderedNameDictionary()) {
      return SmallOrderedNameDictionary::cast(table)->SetHash(hash);
    }
  
    DCHECK(table->IsOrderedNameDictionary());
    OrderedNameDictionary::cast(table)->SetHash(hash);
  }
  
  Name OrderedNameDictionaryHandler::KeyAt(HeapObject table, int entry) {
    if (table->IsSmallOrderedNameDictionary()) {
      return Name::cast(SmallOrderedNameDictionary::cast(table)->KeyAt(entry));
    }
  
    return Name::cast(OrderedNameDictionary::cast(table)->KeyAt(entry));
  }
  
  int OrderedNameDictionaryHandler::NumberOfElements(HeapObject table) {
    if (table->IsSmallOrderedNameDictionary()) {
      return SmallOrderedNameDictionary::cast(table)->NumberOfElements();
    }
  
    return OrderedNameDictionary::cast(table)->NumberOfElements();
  }
  
  int OrderedNameDictionaryHandler::Capacity(HeapObject table) {
    if (table->IsSmallOrderedNameDictionary()) {
      return SmallOrderedNameDictionary::cast(table)->Capacity();
    }
  
    return OrderedNameDictionary::cast(table)->Capacity();
  }
  
  Handle<HeapObject> OrderedNameDictionaryHandler::Shrink(
      Isolate* isolate, Handle<HeapObject> table) {
    if (table->IsSmallOrderedNameDictionary()) {
      Handle<SmallOrderedNameDictionary> small_dict =
          Handle<SmallOrderedNameDictionary>::cast(table);
      return SmallOrderedNameDictionary::Shrink(isolate, small_dict);
    }
  
    Handle<OrderedNameDictionary> large_dict =
        Handle<OrderedNameDictionary>::cast(table);
    return OrderedNameDictionary::Shrink(isolate, large_dict);
  }
  
  Handle<HeapObject> OrderedNameDictionaryHandler::DeleteEntry(
      Isolate* isolate, Handle<HeapObject> table, int entry) {
    DisallowHeapAllocation no_gc;
    if (table->IsSmallOrderedNameDictionary()) {
      Handle<SmallOrderedNameDictionary> small_dict =
          Handle<SmallOrderedNameDictionary>::cast(table);
      return SmallOrderedNameDictionary::DeleteEntry(isolate, small_dict, entry);
    }
  
    Handle<OrderedNameDictionary> large_dict =
        Handle<OrderedNameDictionary>::cast(table);
    return OrderedNameDictionary::DeleteEntry(isolate, large_dict, entry);
  }
  
  template <class Derived, class TableType>
  void OrderedHashTableIterator<Derived, TableType>::Transition() {
    DisallowHeapAllocation no_allocation;
    TableType table = TableType::cast(this->table());
    if (!table->IsObsolete()) return;
  
    int index = Smi::ToInt(this->index());
    while (table->IsObsolete()) {
      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() {
    DisallowHeapAllocation no_allocation;
    ReadOnlyRoots ro_roots = GetReadOnlyRoots();
  
    Transition();
  
    TableType table = TableType::cast(this->table());
    int index = Smi::ToInt(this->index());
    int used_capacity = table->UsedCapacity();
  
    while (index < used_capacity && table->KeyAt(index)->IsTheHole(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 Object
  OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::CurrentKey();
  
  template void
  OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::Transition();
  
  template bool
  OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::HasMore();
  
  template void
  OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::MoveNext();
  
  template Object
  OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::CurrentKey();
  
  template void
  OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::Transition();
  
  }  // namespace internal
  }  // namespace v8
  