// 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 > kMaxCapacity) {
    isolate->heap()->FatalProcessOutOfMemory("invalid table size");
  }
  int num_buckets = capacity / kLoadFactor;
  Handle<FixedArray> backing_store = isolate->factory()->NewFixedArrayWithMap(
      Derived::GetMapRootIndex(),
      kHashTableStartIndex + num_buckets + (capacity * kEntrySize), pretenure);
  Handle<Derived> table = Handle<Derived>::cast(backing_store);
  for (int i = 0; i < num_buckets; ++i) {
    table->set(kHashTableStartIndex + 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 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 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::InNewSpace(*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((entrysize == 1 && table->IsOrderedHashSet()) ||
         (entrysize == 2 && table->IsOrderedHashMap()) ||
         (entrysize == 3 && table->IsOrderedNameDictionary()));
  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(kHashTableStartIndex + 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 = kHashTableStartIndex + 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 = Allocate(
      isolate, new_capacity, Heap::InNewSpace(*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(kHashTableStartIndex + bucket);
    new_table->set(kHashTableStartIndex + 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;
}

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;
}

Object* OrderedHashMap::GetHash(Isolate* isolate, Object* key) {
  DisallowHeapAllocation no_gc;

  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);
  DCHECK(hash->IsSmi());
  DCHECK_GE(Smi::cast(hash)->value(), 0);
  return hash;
}

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(kHashTableStartIndex + bucket, Smi::FromInt(new_entry));
  table->SetNumberOfElements(nof + 1);
  return table;
}

Handle<OrderedNameDictionary> OrderedNameDictionary::Add(
    Isolate* isolate, Handle<OrderedNameDictionary> table, Handle<Name> key,
    Handle<Object> value, PropertyDetails details) {
  int hash = key->Hash();

#ifdef DEBUG
  // Walk the chain of the bucket and try finding the key.
  {
    DisallowHeapAllocation no_gc;
    int entry = table->HashToEntry(hash);
    Object* raw_key = *key;
    while (entry != kNotFound) {
      Object* candidate_key = table->KeyAt(entry);

      // Key should not exist already!
      CHECK(!candidate_key->SameValueZero(raw_key));

      entry = table->NextChainEntry(entry);
    }
  }
#endif

  table = OrderedNameDictionary::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);

  // 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(kHashTableStartIndex + 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;
}

template Handle<OrderedHashSet> OrderedHashTable<OrderedHashSet, 1>::Allocate(
    Isolate* isolate, int capacity, PretenureFlag pretenure);

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>::Allocate(
    Isolate* isolate, int capacity, PretenureFlag pretenure);

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>::Allocate(Isolate* isolate,
                                                     int capacity,
                                                     PretenureFlag pretenure);

template bool OrderedHashTable<OrderedNameDictionary, 3>::HasKey(
    Isolate* isolate, OrderedNameDictionary table, Object* key);

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::InNewSpace(this)) {
    MemsetPointer(RawField(this, kDataTableStartOffset),
                  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;
}

MaybeHandle<SmallOrderedNameDictionary> SmallOrderedNameDictionary::Add(
    Isolate* isolate, Handle<SmallOrderedNameDictionary> table,
    Handle<Name> key, Handle<Object> value, PropertyDetails details) {
  DCHECK(!table->HasKey(isolate, key));

  if (table->UsedCapacity() >= table->Capacity()) {
    MaybeHandle<SmallOrderedNameDictionary> new_table =
        SmallOrderedNameDictionary::Grow(isolate, table);
    if (!new_table.ToHandle(&table)) {
      return MaybeHandle<SmallOrderedNameDictionary>();
    }
  }

  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, 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;
}

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;
}

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::InNewSpace(*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;
}

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 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 <>
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;
}

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 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 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 bool SmallOrderedHashTable<SmallOrderedNameDictionary>::HasKey(
    Isolate* isolate, Handle<Object> key);

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 <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<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);
}

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