blob: 15673daa62f396f60328b579f70cbe4c6582876b [file] [log] [blame]
// Copyright 2018 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include "src/objects/ordered-hash-table.h"
#include "src/execution/isolate.h"
#include "src/heap/heap-inl.h"
#include "src/objects/internal-index.h"
#include "src/objects/js-collection-inl.h"
#include "src/objects/objects-inl.h"
#include "src/objects/ordered-hash-table-inl.h"
#include "src/roots/roots.h"
namespace v8 {
namespace internal {
template <class Derived, int entrysize>
MaybeHandle<Derived> OrderedHashTable<Derived, entrysize>::Allocate(
Isolate* isolate, int capacity, AllocationType allocation) {
// Capacity must be a power of two, since we depend on being able
// to divide and multiple by 2 (kLoadFactor) to derive capacity
// from number of buckets. If we decide to change kLoadFactor
// to something other than 2, capacity should be stored as another
// field of this object.
capacity =
base::bits::RoundUpToPowerOfTwo32(std::max({kInitialCapacity, capacity}));
if (capacity > MaxCapacity()) {
return MaybeHandle<Derived>();
}
int num_buckets = capacity / kLoadFactor;
Handle<FixedArray> backing_store = isolate->factory()->NewFixedArrayWithMap(
Derived::GetMap(ReadOnlyRoots(isolate)),
HashTableStartIndex() + num_buckets + (capacity * kEntrySize),
allocation);
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>
MaybeHandle<Derived> OrderedHashTable<Derived, entrysize>::AllocateEmpty(
Isolate* isolate, AllocationType allocation, RootIndex root_index) {
// This is only supposed to be used to create the canonical empty versions
// of each ordered structure, and should not be used afterwards.
// Requires that the map has already been set up in the roots table.
DCHECK(ReadOnlyRoots(isolate).at(root_index) == kNullAddress);
Handle<FixedArray> backing_store = isolate->factory()->NewFixedArrayWithMap(
Derived::GetMap(ReadOnlyRoots(isolate)), HashTableStartIndex(),
allocation);
Handle<Derived> table = Handle<Derived>::cast(backing_store);
table->SetNumberOfBuckets(0);
table->SetNumberOfElements(0);
table->SetNumberOfDeletedElements(0);
return table;
}
template <class Derived, int entrysize>
MaybeHandle<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;
int new_capacity;
if (capacity == 0) {
// step from empty to minimum proper size
new_capacity = kInitialCapacity;
} else if (nod >= (capacity >> 1)) {
// Don't need to grow if we can simply clear out deleted entries instead.
// Note that we can't compact in place, though, so we always allocate
// a new table.
new_capacity = capacity;
} else {
new_capacity = capacity << 1;
}
return Derived::Rehash(isolate, table, new_capacity);
}
template <class Derived, int entrysize>
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).ToHandleChecked();
}
template <class Derived, int entrysize>
Handle<Derived> OrderedHashTable<Derived, entrysize>::Clear(
Isolate* isolate, Handle<Derived> table) {
DCHECK(!table->IsObsolete());
AllocationType allocation_type = Heap::InYoungGeneration(*table)
? AllocationType::kYoung
: AllocationType::kOld;
Handle<Derived> new_table =
Allocate(isolate, kInitialCapacity, allocation_type).ToHandleChecked();
if (table->NumberOfBuckets() > 0) {
// Don't try to modify the empty canonical table which lives in RO space.
table->SetNextTable(*new_table);
table->SetNumberOfDeletedElements(kClearedTableSentinel);
}
return new_table;
}
template <class Derived, int entrysize>
bool OrderedHashTable<Derived, entrysize>::HasKey(Isolate* isolate,
Derived table, Object key) {
DCHECK_IMPLIES(entrysize == 1, table.IsOrderedHashSet());
DCHECK_IMPLIES(entrysize == 2, table.IsOrderedHashMap());
DisallowHeapAllocation no_gc;
InternalIndex entry = table.FindEntry(isolate, key);
return entry.is_found();
}
template <class Derived, int entrysize>
InternalIndex OrderedHashTable<Derived, entrysize>::FindEntry(Isolate* isolate,
Object key) {
if (NumberOfElements() == 0) {
// This is not just an optimization but also ensures that we do the right
// thing if Capacity() == 0
return InternalIndex::NotFound();
}
int raw_entry;
// This special cases for Smi, so that we avoid the HandleScope
// creation below.
if (key.IsSmi()) {
uint32_t hash = ComputeUnseededHash(Smi::ToInt(key));
raw_entry = HashToEntryRaw(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 InternalIndex::NotFound();
raw_entry = HashToEntryRaw(Smi::ToInt(hash));
}
// Walk the chain in the bucket to find the key.
while (raw_entry != kNotFound) {
Object candidate_key = KeyAt(InternalIndex(raw_entry));
if (candidate_key.SameValueZero(key)) return InternalIndex(raw_entry);
raw_entry = NextChainEntryRaw(raw_entry);
}
return InternalIndex::NotFound();
}
MaybeHandle<OrderedHashSet> OrderedHashSet::Add(Isolate* isolate,
Handle<OrderedHashSet> table,
Handle<Object> key) {
int hash = key->GetOrCreateHash(isolate).value();
if (table->NumberOfElements() > 0) {
int raw_entry = table->HashToEntryRaw(hash);
// Walk the chain of the bucket and try finding the key.
while (raw_entry != kNotFound) {
Object candidate_key = table->KeyAt(InternalIndex(raw_entry));
// Do not add if we have the key already
if (candidate_key.SameValueZero(*key)) return table;
raw_entry = table->NextChainEntryRaw(raw_entry);
}
}
MaybeHandle<OrderedHashSet> table_candidate =
OrderedHashSet::EnsureGrowable(isolate, table);
if (!table_candidate.ToHandle(&table)) {
return table_candidate;
}
// Read the existing bucket values.
int bucket = table->HashToBucket(hash);
int previous_entry = table->HashToEntryRaw(hash);
int nof = table->NumberOfElements();
// Insert a new entry at the end,
int new_entry = nof + table->NumberOfDeletedElements();
int new_index = table->EntryToIndexRaw(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);
uint32_t index_value;
if (convert == GetKeysConversion::kConvertToString) {
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());
}
} else if (convert == GetKeysConversion::kNoNumbers) {
DCHECK(!key.ToArrayIndex(&index_value));
}
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>
MaybeHandle<Derived> OrderedHashTable<Derived, entrysize>::Rehash(
Isolate* isolate, Handle<Derived> table) {
return OrderedHashTable<Derived, entrysize>::Rehash(isolate, table,
table->Capacity());
}
template <class Derived, int entrysize>
MaybeHandle<Derived> OrderedHashTable<Derived, entrysize>::Rehash(
Isolate* isolate, Handle<Derived> table, int new_capacity) {
DCHECK(!table->IsObsolete());
MaybeHandle<Derived> new_table_candidate =
Derived::Allocate(isolate, new_capacity,
Heap::InYoungGeneration(*table) ? AllocationType::kYoung
: AllocationType::kOld);
Handle<Derived> new_table;
if (!new_table_candidate.ToHandle(&new_table)) {
return new_table_candidate;
}
int new_buckets = new_table->NumberOfBuckets();
int new_entry = 0;
int removed_holes_index = 0;
DisallowHeapAllocation no_gc;
for (InternalIndex old_entry : table->IterateEntries()) {
int old_entry_raw = old_entry.as_int();
Object key = table->KeyAt(old_entry);
if (key.IsTheHole(isolate)) {
table->SetRemovedIndexAt(removed_holes_index++, old_entry_raw);
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->EntryToIndexRaw(new_entry);
int old_index = table->EntryToIndexRaw(old_entry_raw);
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(table->NumberOfDeletedElements(), removed_holes_index);
new_table->SetNumberOfElements(table->NumberOfElements());
if (table->NumberOfBuckets() > 0) {
// Don't try to modify the empty canonical table which lives in RO space.
table->SetNextTable(*new_table);
}
return new_table_candidate;
}
MaybeHandle<OrderedHashSet> OrderedHashSet::Rehash(Isolate* isolate,
Handle<OrderedHashSet> table,
int new_capacity) {
return Base::Rehash(isolate, table, new_capacity);
}
MaybeHandle<OrderedHashSet> OrderedHashSet::Rehash(
Isolate* isolate, Handle<OrderedHashSet> table) {
return Base::Rehash(isolate, table);
}
MaybeHandle<OrderedHashMap> OrderedHashMap::Rehash(
Isolate* isolate, Handle<OrderedHashMap> table) {
return Base::Rehash(isolate, table);
}
MaybeHandle<OrderedHashMap> OrderedHashMap::Rehash(Isolate* isolate,
Handle<OrderedHashMap> table,
int new_capacity) {
return Base::Rehash(isolate, table, new_capacity);
}
MaybeHandle<OrderedNameDictionary> OrderedNameDictionary::Rehash(
Isolate* isolate, Handle<OrderedNameDictionary> table, int new_capacity) {
MaybeHandle<OrderedNameDictionary> new_table_candidate =
Base::Rehash(isolate, table, new_capacity);
Handle<OrderedNameDictionary> new_table;
if (new_table_candidate.ToHandle(&new_table)) {
new_table->SetHash(table->Hash());
}
return new_table_candidate;
}
template <class Derived, int entrysize>
bool OrderedHashTable<Derived, entrysize>::Delete(Isolate* isolate,
Derived table, Object key) {
DisallowHeapAllocation no_gc;
InternalIndex entry = table.FindEntry(isolate, key);
if (entry.is_not_found()) return false;
int nof = table.NumberOfElements();
int nod = table.NumberOfDeletedElements();
int index = table.EntryToIndex(entry);
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;
}
// Parameter |roots| only here for compatibility with HashTable<...>::ToKey.
template <class Derived, int entrysize>
bool OrderedHashTable<Derived, entrysize>::ToKey(ReadOnlyRoots roots,
InternalIndex entry,
Object* out_key) {
Object k = KeyAt(entry);
if (!IsKey(roots, k)) return false;
*out_key = k;
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();
}
MaybeHandle<OrderedHashMap> OrderedHashMap::Add(Isolate* isolate,
Handle<OrderedHashMap> table,
Handle<Object> key,
Handle<Object> value) {
int hash = key->GetOrCreateHash(isolate).value();
if (table->NumberOfElements() > 0) {
int raw_entry = table->HashToEntryRaw(hash);
// Walk the chain of the bucket and try finding the key.
{
DisallowHeapAllocation no_gc;
Object raw_key = *key;
while (raw_entry != kNotFound) {
Object candidate_key = table->KeyAt(InternalIndex(raw_entry));
// Do not add if we have the key already
if (candidate_key.SameValueZero(raw_key)) return table;
raw_entry = table->NextChainEntryRaw(raw_entry);
}
}
}
MaybeHandle<OrderedHashMap> table_candidate =
OrderedHashMap::EnsureGrowable(isolate, table);
if (!table_candidate.ToHandle(&table)) {
return table_candidate;
}
// Read the existing bucket values.
int bucket = table->HashToBucket(hash);
int previous_entry = table->HashToEntryRaw(hash);
int nof = table->NumberOfElements();
// Insert a new entry at the end,
int new_entry = nof + table->NumberOfDeletedElements();
int new_index = table->EntryToIndexRaw(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;
}
InternalIndex OrderedNameDictionary::FindEntry(Isolate* isolate, Object key) {
DisallowHeapAllocation no_gc;
DCHECK(key.IsUniqueName());
Name raw_key = Name::cast(key);
if (NumberOfElements() == 0) {
// This is not just an optimization but also ensures that we do the right
// thing if Capacity() == 0
return InternalIndex::NotFound();
}
int raw_entry = HashToEntryRaw(raw_key.Hash());
while (raw_entry != kNotFound) {
InternalIndex entry(raw_entry);
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.
raw_entry = NextChainEntryRaw(raw_entry);
}
return InternalIndex::NotFound();
}
// TODO(emrich): This is almost an identical copy of
// Dictionary<..>::SlowReverseLookup.
// Consolidate both versions elsewhere (e.g., hash-table-utils)?
Object OrderedNameDictionary::SlowReverseLookup(Isolate* isolate,
Object value) {
ReadOnlyRoots roots(isolate);
for (InternalIndex i : IterateEntries()) {
Object k;
if (!ToKey(roots, i, &k)) continue;
Object e = this->ValueAt(i);
if (e == value) return k;
}
return roots.undefined_value();
}
// TODO(emrich): This is almost an identical copy of
// HashTable<..>::NumberOfEnumerableProperties.
// Consolidate both versions elsewhere (e.g., hash-table-utils)?
int OrderedNameDictionary::NumberOfEnumerableProperties() {
ReadOnlyRoots roots = this->GetReadOnlyRoots();
int result = 0;
for (InternalIndex i : this->IterateEntries()) {
Object k;
if (!this->ToKey(roots, i, &k)) continue;
if (k.FilterKey(ENUMERABLE_STRINGS)) continue;
PropertyDetails details = this->DetailsAt(i);
PropertyAttributes attr = details.attributes();
if ((attr & ONLY_ENUMERABLE) == 0) result++;
}
return result;
}
MaybeHandle<OrderedNameDictionary> OrderedNameDictionary::Add(
Isolate* isolate, Handle<OrderedNameDictionary> table, Handle<Name> key,
Handle<Object> value, PropertyDetails details) {
DCHECK(table->FindEntry(isolate, *key).is_not_found());
MaybeHandle<OrderedNameDictionary> table_candidate =
OrderedNameDictionary::EnsureGrowable(isolate, table);
if (!table_candidate.ToHandle(&table)) {
return table_candidate;
}
// Read the existing bucket values.
int hash = key->Hash();
int bucket = table->HashToBucket(hash);
int previous_entry = table->HashToEntryRaw(hash);
int nof = table->NumberOfElements();
// Insert a new entry at the end,
int new_entry = nof + table->NumberOfDeletedElements();
int new_index = table->EntryToIndexRaw(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(InternalIndex entry, Object key,
Object value, PropertyDetails details) {
DisallowHeapAllocation gc;
DCHECK_IMPLIES(!key.IsName(), key.IsTheHole());
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,
InternalIndex entry) {
DCHECK(entry.is_found());
Object hole = ReadOnlyRoots(isolate).the_hole_value();
PropertyDetails details = PropertyDetails::Empty();
table->SetEntry(entry, hole, hole, details);
int nof = table->NumberOfElements();
table->SetNumberOfElements(nof - 1);
int nod = table->NumberOfDeletedElements();
table->SetNumberOfDeletedElements(nod + 1);
return Shrink(isolate, table);
}
MaybeHandle<OrderedHashSet> OrderedHashSet::Allocate(
Isolate* isolate, int capacity, AllocationType allocation) {
return Base::Allocate(isolate, capacity, allocation);
}
MaybeHandle<OrderedHashMap> OrderedHashMap::Allocate(
Isolate* isolate, int capacity, AllocationType allocation) {
return Base::Allocate(isolate, capacity, allocation);
}
MaybeHandle<OrderedNameDictionary> OrderedNameDictionary::Allocate(
Isolate* isolate, int capacity, AllocationType allocation) {
MaybeHandle<OrderedNameDictionary> table_candidate =
Base::Allocate(isolate, capacity, allocation);
Handle<OrderedNameDictionary> table;
if (table_candidate.ToHandle(&table)) {
table->SetHash(PropertyArray::kNoHashSentinel);
}
return table_candidate;
}
MaybeHandle<OrderedHashSet> OrderedHashSet::AllocateEmpty(
Isolate* isolate, AllocationType allocation) {
RootIndex ri = RootIndex::kEmptyOrderedHashSet;
return Base::AllocateEmpty(isolate, allocation, ri);
}
MaybeHandle<OrderedHashMap> OrderedHashMap::AllocateEmpty(
Isolate* isolate, AllocationType allocation) {
RootIndex ri = RootIndex::kEmptyOrderedHashMap;
return Base::AllocateEmpty(isolate, allocation, ri);
}
MaybeHandle<OrderedNameDictionary> OrderedNameDictionary::AllocateEmpty(
Isolate* isolate, AllocationType allocation) {
RootIndex ri = RootIndex::kEmptyOrderedPropertyDictionary;
MaybeHandle<OrderedNameDictionary> table_candidate =
Base::AllocateEmpty(isolate, allocation, ri);
Handle<OrderedNameDictionary> table;
if (table_candidate.ToHandle(&table)) {
table->SetHash(PropertyArray::kNoHashSentinel);
}
return table_candidate;
}
template V8_EXPORT_PRIVATE MaybeHandle<OrderedHashSet>
OrderedHashTable<OrderedHashSet, 1>::EnsureGrowable(
Isolate* isolate, Handle<OrderedHashSet> table);
template V8_EXPORT_PRIVATE Handle<OrderedHashSet>
OrderedHashTable<OrderedHashSet, 1>::Shrink(Isolate* isolate,
Handle<OrderedHashSet> table);
template V8_EXPORT_PRIVATE Handle<OrderedHashSet>
OrderedHashTable<OrderedHashSet, 1>::Clear(Isolate* isolate,
Handle<OrderedHashSet> table);
template V8_EXPORT_PRIVATE bool OrderedHashTable<OrderedHashSet, 1>::HasKey(
Isolate* isolate, OrderedHashSet table, Object key);
template V8_EXPORT_PRIVATE bool OrderedHashTable<OrderedHashSet, 1>::Delete(
Isolate* isolate, OrderedHashSet table, Object key);
template V8_EXPORT_PRIVATE InternalIndex
OrderedHashTable<OrderedHashSet, 1>::FindEntry(Isolate* isolate, Object key);
template V8_EXPORT_PRIVATE MaybeHandle<OrderedHashMap>
OrderedHashTable<OrderedHashMap, 2>::EnsureGrowable(
Isolate* isolate, Handle<OrderedHashMap> table);
template V8_EXPORT_PRIVATE Handle<OrderedHashMap>
OrderedHashTable<OrderedHashMap, 2>::Shrink(Isolate* isolate,
Handle<OrderedHashMap> table);
template V8_EXPORT_PRIVATE Handle<OrderedHashMap>
OrderedHashTable<OrderedHashMap, 2>::Clear(Isolate* isolate,
Handle<OrderedHashMap> table);
template V8_EXPORT_PRIVATE bool OrderedHashTable<OrderedHashMap, 2>::HasKey(
Isolate* isolate, OrderedHashMap table, Object key);
template V8_EXPORT_PRIVATE bool OrderedHashTable<OrderedHashMap, 2>::Delete(
Isolate* isolate, OrderedHashMap table, Object key);
template V8_EXPORT_PRIVATE InternalIndex
OrderedHashTable<OrderedHashMap, 2>::FindEntry(Isolate* isolate, Object key);
template V8_EXPORT_PRIVATE Handle<OrderedNameDictionary>
OrderedHashTable<OrderedNameDictionary, 3>::Shrink(
Isolate* isolate, Handle<OrderedNameDictionary> table);
template MaybeHandle<OrderedNameDictionary>
OrderedHashTable<OrderedNameDictionary, 3>::EnsureGrowable(
Isolate* isolate, Handle<OrderedNameDictionary> table);
template <>
Handle<SmallOrderedHashSet>
SmallOrderedHashTable<SmallOrderedHashSet>::Allocate(
Isolate* isolate, int capacity, AllocationType allocation) {
return isolate->factory()->NewSmallOrderedHashSet(capacity, allocation);
}
template <>
Handle<SmallOrderedHashMap>
SmallOrderedHashTable<SmallOrderedHashMap>::Allocate(
Isolate* isolate, int capacity, AllocationType allocation) {
return isolate->factory()->NewSmallOrderedHashMap(capacity, allocation);
}
template <>
Handle<SmallOrderedNameDictionary>
SmallOrderedHashTable<SmallOrderedNameDictionary>::Allocate(
Isolate* isolate, int capacity, AllocationType allocation) {
return isolate->factory()->NewSmallOrderedNameDictionary(capacity,
allocation);
}
template <class Derived>
void SmallOrderedHashTable<Derived>::Initialize(Isolate* isolate,
int capacity) {
DisallowHeapAllocation no_gc;
int num_buckets = capacity / kLoadFactor;
int num_chains = capacity;
SetNumberOfBuckets(num_buckets);
SetNumberOfElements(0);
SetNumberOfDeletedElements(0);
memset(reinterpret_cast<void*>(field_address(PaddingOffset())), 0,
PaddingSize());
Address hashtable_start = GetHashTableStartAddress(capacity);
memset(reinterpret_cast<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;
}
bool SmallOrderedHashSet::Delete(Isolate* isolate, SmallOrderedHashSet table,
Object key) {
return SmallOrderedHashTable<SmallOrderedHashSet>::Delete(isolate, table,
key);
}
bool SmallOrderedHashSet::HasKey(Isolate* isolate, Handle<Object> key) {
return SmallOrderedHashTable<SmallOrderedHashSet>::HasKey(isolate, key);
}
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;
}
bool SmallOrderedHashMap::Delete(Isolate* isolate, SmallOrderedHashMap table,
Object key) {
return SmallOrderedHashTable<SmallOrderedHashMap>::Delete(isolate, table,
key);
}
bool SmallOrderedHashMap::HasKey(Isolate* isolate, Handle<Object> key) {
return SmallOrderedHashTable<SmallOrderedHashMap>::HasKey(isolate, key);
}
template <>
InternalIndex V8_EXPORT_PRIVATE
SmallOrderedHashTable<SmallOrderedNameDictionary>::FindEntry(Isolate* isolate,
Object key) {
DisallowHeapAllocation no_gc;
DCHECK(key.IsUniqueName());
Name raw_key = Name::cast(key);
int raw_entry = HashToFirstEntry(raw_key.Hash());
// Walk the chain in the bucket to find the key.
while (raw_entry != kNotFound) {
InternalIndex entry(raw_entry);
Object candidate_key = KeyAt(entry);
if (candidate_key == key) return entry;
raw_entry = GetNextEntry(raw_entry);
}
return InternalIndex::NotFound();
}
MaybeHandle<SmallOrderedNameDictionary> SmallOrderedNameDictionary::Add(
Isolate* isolate, Handle<SmallOrderedNameDictionary> table,
Handle<Name> key, Handle<Object> value, PropertyDetails details) {
DCHECK(table->FindEntry(isolate, *key).is_not_found());
if (table->UsedCapacity() >= table->Capacity()) {
MaybeHandle<SmallOrderedNameDictionary> new_table =
SmallOrderedNameDictionary::Grow(isolate, table);
if (!new_table.ToHandle(&table)) {
return MaybeHandle<SmallOrderedNameDictionary>();
}
}
int nof = table->NumberOfElements();
// Read the existing bucket values.
int hash = key->Hash();
int bucket = table->HashToBucket(hash);
int previous_entry = table->HashToFirstEntry(hash);
// Insert a new entry at the end,
int new_entry = nof + table->NumberOfDeletedElements();
table->SetDataEntry(new_entry, SmallOrderedNameDictionary::kValueIndex,
*value);
table->SetDataEntry(new_entry, SmallOrderedNameDictionary::kKeyIndex, *key);
// TODO(gsathya): PropertyDetails should be stored as part of the
// data table to save more memory.
table->SetDataEntry(new_entry,
SmallOrderedNameDictionary::kPropertyDetailsIndex,
details.AsSmi());
table->SetFirstEntry(bucket, new_entry);
table->SetNextEntry(new_entry, previous_entry);
// and update book keeping.
table->SetNumberOfElements(nof + 1);
return table;
}
void SmallOrderedNameDictionary::SetEntry(InternalIndex entry, Object key,
Object value,
PropertyDetails details) {
int raw_entry = entry.as_int();
DCHECK_IMPLIES(!key.IsName(), key.IsTheHole());
SetDataEntry(raw_entry, SmallOrderedNameDictionary::kValueIndex, value);
SetDataEntry(raw_entry, SmallOrderedNameDictionary::kKeyIndex, key);
// TODO(gsathya): PropertyDetails should be stored as part of the
// data table to save more memory.
SetDataEntry(raw_entry, SmallOrderedNameDictionary::kPropertyDetailsIndex,
details.AsSmi());
}
template <class Derived>
bool SmallOrderedHashTable<Derived>::HasKey(Isolate* isolate,
Handle<Object> key) {
DisallowHeapAllocation no_gc;
return FindEntry(isolate, *key).is_found();
}
template <class Derived>
bool SmallOrderedHashTable<Derived>::Delete(Isolate* isolate, Derived table,
Object key) {
DisallowHeapAllocation no_gc;
InternalIndex entry = table.FindEntry(isolate, key);
if (entry.is_not_found()) 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.as_int(), j, hole);
}
table.SetNumberOfElements(nof - 1);
table.SetNumberOfDeletedElements(nod + 1);
return true;
}
Handle<SmallOrderedNameDictionary> SmallOrderedNameDictionary::DeleteEntry(
Isolate* isolate, Handle<SmallOrderedNameDictionary> table,
InternalIndex entry) {
DCHECK(entry.is_found());
{
DisallowHeapAllocation no_gc;
Object hole = ReadOnlyRoots(isolate).the_hole_value();
PropertyDetails details = PropertyDetails::Empty();
table->SetEntry(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) ? AllocationType::kYoung
: AllocationType::kOld);
int new_entry = 0;
{
DisallowHeapAllocation no_gc;
for (InternalIndex old_entry : table->IterateEntries()) {
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.as_int(), i);
new_table->SetDataEntry(new_entry, i, value);
}
++new_entry;
}
new_table->SetNumberOfElements(table->NumberOfElements());
}
return new_table;
}
Handle<SmallOrderedHashSet> SmallOrderedHashSet::Rehash(
Isolate* isolate, Handle<SmallOrderedHashSet> table, int new_capacity) {
return SmallOrderedHashTable<SmallOrderedHashSet>::Rehash(isolate, table,
new_capacity);
}
Handle<SmallOrderedHashMap> SmallOrderedHashMap::Rehash(
Isolate* isolate, Handle<SmallOrderedHashMap> table, int new_capacity) {
return SmallOrderedHashTable<SmallOrderedHashMap>::Rehash(isolate, table,
new_capacity);
}
Handle<SmallOrderedNameDictionary> SmallOrderedNameDictionary::Rehash(
Isolate* isolate, Handle<SmallOrderedNameDictionary> table,
int new_capacity) {
Handle<SmallOrderedNameDictionary> new_table =
SmallOrderedHashTable<SmallOrderedNameDictionary>::Rehash(isolate, table,
new_capacity);
new_table->SetHash(table->Hash());
return new_table;
}
template <class Derived>
Handle<Derived> SmallOrderedHashTable<Derived>::Shrink(Isolate* isolate,
Handle<Derived> table) {
int nof = table->NumberOfElements();
int capacity = table->Capacity();
if (nof >= (capacity >> 2)) return table;
return Derived::Rehash(isolate, table, capacity / 2);
}
template <class Derived>
MaybeHandle<Derived> SmallOrderedHashTable<Derived>::Grow(
Isolate* isolate, Handle<Derived> table) {
int capacity = table->Capacity();
int new_capacity = capacity;
// Don't need to grow if we can simply clear out deleted entries instead.
// TODO(gsathya): Compact in place, instead of allocating a new table.
if (table->NumberOfDeletedElements() < (capacity >> 1)) {
new_capacity = capacity << 1;
// The max capacity of our table is 254. We special case for 256 to
// account for our growth strategy, otherwise we would only fill up
// to 128 entries in our table.
if (new_capacity == kGrowthHack) {
new_capacity = kMaxCapacity;
}
// We need to migrate to a bigger hash table.
if (new_capacity > kMaxCapacity) {
return MaybeHandle<Derived>();
}
}
return Derived::Rehash(isolate, table, new_capacity);
}
template <class Derived>
InternalIndex SmallOrderedHashTable<Derived>::FindEntry(Isolate* isolate,
Object key) {
DisallowHeapAllocation no_gc;
Object hash = key.GetHash();
if (hash.IsUndefined(isolate)) return InternalIndex::NotFound();
int raw_entry = HashToFirstEntry(Smi::ToInt(hash));
// Walk the chain in the bucket to find the key.
while (raw_entry != kNotFound) {
InternalIndex entry(raw_entry);
Object candidate_key = KeyAt(entry);
if (candidate_key.SameValueZero(key)) return entry;
raw_entry = GetNextEntry(raw_entry);
}
return InternalIndex::NotFound();
}
template bool EXPORT_TEMPLATE_DEFINE(V8_EXPORT_PRIVATE)
SmallOrderedHashTable<SmallOrderedHashSet>::HasKey(Isolate* isolate,
Handle<Object> key);
template V8_EXPORT_PRIVATE Handle<SmallOrderedHashSet>
SmallOrderedHashTable<SmallOrderedHashSet>::Rehash(
Isolate* isolate, Handle<SmallOrderedHashSet> table, int new_capacity);
template V8_EXPORT_PRIVATE Handle<SmallOrderedHashSet>
SmallOrderedHashTable<SmallOrderedHashSet>::Shrink(
Isolate* isolate, Handle<SmallOrderedHashSet> table);
template V8_EXPORT_PRIVATE MaybeHandle<SmallOrderedHashSet>
SmallOrderedHashTable<SmallOrderedHashSet>::Grow(
Isolate* isolate, Handle<SmallOrderedHashSet> table);
template V8_EXPORT_PRIVATE void
SmallOrderedHashTable<SmallOrderedHashSet>::Initialize(Isolate* isolate,
int capacity);
template V8_EXPORT_PRIVATE bool
SmallOrderedHashTable<SmallOrderedHashSet>::Delete(Isolate* isolate,
SmallOrderedHashSet table,
Object key);
template EXPORT_TEMPLATE_DEFINE(V8_EXPORT_PRIVATE) bool SmallOrderedHashTable<
SmallOrderedHashMap>::HasKey(Isolate* isolate, Handle<Object> key);
template V8_EXPORT_PRIVATE Handle<SmallOrderedHashMap>
SmallOrderedHashTable<SmallOrderedHashMap>::Rehash(
Isolate* isolate, Handle<SmallOrderedHashMap> table, int new_capacity);
template V8_EXPORT_PRIVATE Handle<SmallOrderedHashMap>
SmallOrderedHashTable<SmallOrderedHashMap>::Shrink(
Isolate* isolate, Handle<SmallOrderedHashMap> table);
template V8_EXPORT_PRIVATE MaybeHandle<SmallOrderedHashMap>
SmallOrderedHashTable<SmallOrderedHashMap>::Grow(
Isolate* isolate, Handle<SmallOrderedHashMap> table);
template V8_EXPORT_PRIVATE void
SmallOrderedHashTable<SmallOrderedHashMap>::Initialize(Isolate* isolate,
int capacity);
template V8_EXPORT_PRIVATE bool
SmallOrderedHashTable<SmallOrderedHashMap>::Delete(Isolate* isolate,
SmallOrderedHashMap table,
Object key);
template V8_EXPORT_PRIVATE void
SmallOrderedHashTable<SmallOrderedNameDictionary>::Initialize(Isolate* isolate,
int capacity);
template V8_EXPORT_PRIVATE Handle<SmallOrderedNameDictionary>
SmallOrderedHashTable<SmallOrderedNameDictionary>::Shrink(
Isolate* isolate, Handle<SmallOrderedNameDictionary> table);
template <class SmallTable, class LargeTable>
MaybeHandle<HeapObject>
OrderedHashTableHandler<SmallTable, LargeTable>::Allocate(Isolate* isolate,
int capacity) {
if (capacity < SmallTable::kMaxCapacity) {
return SmallTable::Allocate(isolate, capacity);
}
return LargeTable::Allocate(isolate, capacity);
}
template V8_EXPORT_PRIVATE MaybeHandle<HeapObject>
OrderedHashTableHandler<SmallOrderedHashSet, OrderedHashSet>::Allocate(
Isolate* isolate, int capacity);
template V8_EXPORT_PRIVATE MaybeHandle<HeapObject>
OrderedHashTableHandler<SmallOrderedHashMap, OrderedHashMap>::Allocate(
Isolate* isolate, int capacity);
template V8_EXPORT_PRIVATE MaybeHandle<HeapObject>
OrderedHashTableHandler<SmallOrderedNameDictionary,
OrderedNameDictionary>::Allocate(Isolate* isolate,
int capacity);
template <class SmallTable, class LargeTable>
bool OrderedHashTableHandler<SmallTable, LargeTable>::Delete(
Isolate* isolate, Handle<HeapObject> table, Handle<Object> key) {
if (SmallTable::Is(table)) {
return SmallTable::Delete(isolate, *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(isolate, *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);
template bool
OrderedHashTableHandler<SmallOrderedHashSet, OrderedHashSet>::Delete(
Isolate* isolate, Handle<HeapObject> table, Handle<Object> key);
template bool
OrderedHashTableHandler<SmallOrderedHashMap, OrderedHashMap>::Delete(
Isolate* isolate, Handle<HeapObject> table, Handle<Object> key);
template bool
OrderedHashTableHandler<SmallOrderedNameDictionary,
OrderedNameDictionary>::Delete(Isolate* isolate,
Handle<HeapObject> table,
Handle<Object> key);
MaybeHandle<OrderedHashMap> OrderedHashMapHandler::AdjustRepresentation(
Isolate* isolate, Handle<SmallOrderedHashMap> table) {
MaybeHandle<OrderedHashMap> new_table_candidate =
OrderedHashMap::Allocate(isolate, OrderedHashTableMinSize);
Handle<OrderedHashMap> new_table;
if (!new_table_candidate.ToHandle(&new_table)) {
return new_table_candidate;
}
// TODO(gsathya): Optimize the lookup to not re calc offsets. Also,
// unhandlify this code as we preallocate the new backing store with
// the proper capacity.
for (InternalIndex entry : table->IterateEntries()) {
Handle<Object> key = handle(table->KeyAt(entry), isolate);
if (key->IsTheHole(isolate)) continue;
Handle<Object> value = handle(
table->GetDataEntry(entry.as_int(), SmallOrderedHashMap::kValueIndex),
isolate);
new_table_candidate = OrderedHashMap::Add(isolate, new_table, key, value);
if (!new_table_candidate.ToHandle(&new_table)) {
return new_table_candidate;
}
}
return new_table_candidate;
}
MaybeHandle<OrderedHashSet> OrderedHashSetHandler::AdjustRepresentation(
Isolate* isolate, Handle<SmallOrderedHashSet> table) {
MaybeHandle<OrderedHashSet> new_table_candidate =
OrderedHashSet::Allocate(isolate, OrderedHashTableMinSize);
Handle<OrderedHashSet> new_table;
if (!new_table_candidate.ToHandle(&new_table)) {
return new_table_candidate;
}
// TODO(gsathya): Optimize the lookup to not re calc offsets. Also,
// unhandlify this code as we preallocate the new backing store with
// the proper capacity.
for (InternalIndex entry : table->IterateEntries()) {
Handle<Object> key = handle(table->KeyAt(entry), isolate);
if (key->IsTheHole(isolate)) continue;
new_table_candidate = OrderedHashSet::Add(isolate, new_table, key);
if (!new_table_candidate.ToHandle(&new_table)) {
return new_table_candidate;
}
}
return new_table_candidate;
}
MaybeHandle<OrderedNameDictionary>
OrderedNameDictionaryHandler::AdjustRepresentation(
Isolate* isolate, Handle<SmallOrderedNameDictionary> table) {
MaybeHandle<OrderedNameDictionary> new_table_candidate =
OrderedNameDictionary::Allocate(isolate, OrderedHashTableMinSize);
Handle<OrderedNameDictionary> new_table;
if (!new_table_candidate.ToHandle(&new_table)) {
return new_table_candidate;
}
// TODO(gsathya): Optimize the lookup to not re calc offsets. Also,
// unhandlify this code as we preallocate the new backing store with
// the proper capacity.
for (InternalIndex entry : table->IterateEntries()) {
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_candidate =
OrderedNameDictionary::Add(isolate, new_table, key, value, details);
if (!new_table_candidate.ToHandle(&new_table)) {
return new_table_candidate;
}
}
return new_table_candidate;
}
MaybeHandle<HeapObject> OrderedHashMapHandler::Add(Isolate* isolate,
Handle<HeapObject> table,
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.
MaybeHandle<OrderedHashMap> table_candidate =
OrderedHashMapHandler::AdjustRepresentation(isolate, small_map);
if (!table_candidate.ToHandle(&table)) {
return table_candidate;
}
}
DCHECK(table->IsOrderedHashMap());
return OrderedHashMap::Add(isolate, Handle<OrderedHashMap>::cast(table), key,
value);
}
MaybeHandle<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.
MaybeHandle<OrderedHashSet> table_candidate =
OrderedHashSetHandler::AdjustRepresentation(isolate, small_set);
if (!table_candidate.ToHandle(&table)) {
return table_candidate;
}
}
DCHECK(table->IsOrderedHashSet());
return OrderedHashSet::Add(isolate, Handle<OrderedHashSet>::cast(table), key);
}
MaybeHandle<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.
MaybeHandle<OrderedNameDictionary> table_candidate =
OrderedNameDictionaryHandler::AdjustRepresentation(isolate, small_dict);
if (!table_candidate.ToHandle(&table)) {
return table_candidate;
}
}
DCHECK(table->IsOrderedNameDictionary());
return OrderedNameDictionary::Add(
isolate, Handle<OrderedNameDictionary>::cast(table), key, value, details);
}
void OrderedNameDictionaryHandler::SetEntry(HeapObject table,
InternalIndex entry, Object key,
Object value,
PropertyDetails details) {
DisallowHeapAllocation no_gc;
if (table.IsSmallOrderedNameDictionary()) {
return SmallOrderedNameDictionary::cast(table).SetEntry(entry, key, value,
details);
}
DCHECK(table.IsOrderedNameDictionary());
return OrderedNameDictionary::cast(table).SetEntry(InternalIndex(entry), key,
value, details);
}
InternalIndex OrderedNameDictionaryHandler::FindEntry(Isolate* isolate,
HeapObject table,
Name key) {
DisallowHeapAllocation no_gc;
if (table.IsSmallOrderedNameDictionary()) {
return SmallOrderedNameDictionary::cast(table).FindEntry(isolate, key);
}
DCHECK(table.IsOrderedNameDictionary());
return OrderedNameDictionary::cast(table).FindEntry(isolate, key);
}
Object OrderedNameDictionaryHandler::ValueAt(HeapObject table,
InternalIndex entry) {
if (table.IsSmallOrderedNameDictionary()) {
return SmallOrderedNameDictionary::cast(table).ValueAt(entry);
}
DCHECK(table.IsOrderedNameDictionary());
return OrderedNameDictionary::cast(table).ValueAt(entry);
}
void OrderedNameDictionaryHandler::ValueAtPut(HeapObject table,
InternalIndex 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,
InternalIndex entry) {
if (table.IsSmallOrderedNameDictionary()) {
return SmallOrderedNameDictionary::cast(table).DetailsAt(entry);
}
DCHECK(table.IsOrderedNameDictionary());
return OrderedNameDictionary::cast(table).DetailsAt(entry);
}
void OrderedNameDictionaryHandler::DetailsAtPut(HeapObject table,
InternalIndex 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,
InternalIndex entry) {
if (table.IsSmallOrderedNameDictionary()) {
return Name::cast(SmallOrderedNameDictionary::cast(table).KeyAt(entry));
}
return Name::cast(
OrderedNameDictionary::cast(table).KeyAt(InternalIndex(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, InternalIndex 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,
InternalIndex(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());
DCHECK_LE(0, 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(InternalIndex(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