// 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( static_cast<Heap::RootListIndex>(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())); DisallowHeapAllocation no_gc; int entry = table->FindEntry(isolate, key); return entry != kNotFound; } 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()); 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)) { key = *isolate->factory()->Uint32ToString(index_value); } 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; } 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 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 <> 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 <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; } 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 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 <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