| // 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 |