diff options
Diffstat (limited to 'deps/v8/src/objects/ordered-hash-table.h')
| -rw-r--r-- | deps/v8/src/objects/ordered-hash-table.h | 534 |
1 files changed, 368 insertions, 166 deletions
diff --git a/deps/v8/src/objects/ordered-hash-table.h b/deps/v8/src/objects/ordered-hash-table.h index 6c606efc75..6e938d53b2 100644 --- a/deps/v8/src/objects/ordered-hash-table.h +++ b/deps/v8/src/objects/ordered-hash-table.h @@ -8,6 +8,8 @@ #include "src/globals.h" #include "src/objects/fixed-array.h" #include "src/objects/js-objects.h" +#include "src/objects/smi.h" +#include "src/roots.h" // Has to be the last include (doesn't have include guards): #include "src/objects/object-macros.h" @@ -15,45 +17,11 @@ namespace v8 { namespace internal { -// Non-templatized base class for {OrderedHashTable}s. -// TODO(hash): Unify this with the HashTableBase above. -class OrderedHashTableBase : public FixedArray { - public: - static const int kNotFound = -1; - static const int kMinCapacity = 4; - - static const int kNumberOfElementsIndex = 0; - // The next table is stored at the same index as the nof elements. - static const int kNextTableIndex = kNumberOfElementsIndex; - static const int kNumberOfDeletedElementsIndex = kNumberOfElementsIndex + 1; - static const int kNumberOfBucketsIndex = kNumberOfDeletedElementsIndex + 1; - static const int kHashTableStartIndex = kNumberOfBucketsIndex + 1; - static const int kRemovedHolesIndex = kHashTableStartIndex; - - static constexpr const int kNumberOfElementsOffset = - FixedArray::OffsetOfElementAt(kNumberOfElementsIndex); - static constexpr const int kNextTableOffset = - FixedArray::OffsetOfElementAt(kNextTableIndex); - static constexpr const int kNumberOfDeletedElementsOffset = - FixedArray::OffsetOfElementAt(kNumberOfDeletedElementsIndex); - static constexpr const int kNumberOfBucketsOffset = - FixedArray::OffsetOfElementAt(kNumberOfBucketsIndex); - static constexpr const int kHashTableStartOffset = - FixedArray::OffsetOfElementAt(kHashTableStartIndex); - - static const int kLoadFactor = 2; - - // NumberOfDeletedElements is set to kClearedTableSentinel when - // the table is cleared, which allows iterator transitions to - // optimize that case. - static const int kClearedTableSentinel = -1; -}; - // OrderedHashTable is a HashTable with Object keys that preserves // insertion order. There are Map and Set interfaces (OrderedHashMap // and OrderedHashTable, below). It is meant to be used by JSMap/JSSet. // -// Only Object* keys are supported, with Object::SameValueZero() used as the +// Only Object keys are supported, with Object::SameValueZero() used as the // equality operator and Object::GetHash() for the hash function. // // Based on the "Deterministic Hash Table" as described by Jason Orendorff at @@ -61,37 +29,38 @@ class OrderedHashTableBase : public FixedArray { // Originally attributed to Tyler Close. // // Memory layout: -// [0]: element count -// [1]: deleted element count -// [2]: bucket count -// [3..(3 + NumberOfBuckets() - 1)]: "hash table", where each item is an -// offset into the data table (see below) where the -// first item in this bucket is stored. -// [3 + NumberOfBuckets()..length]: "data table", an array of length -// Capacity() * kEntrySize, where the first entrysize -// items are handled by the derived class and the -// item at kChainOffset is another entry into the -// data table indicating the next entry in this hash -// bucket. +// [0] : Prefix +// [kPrefixSize]: element count +// [kPrefixSize + 1]: deleted element count +// [kPrefixSize + 2]: bucket count +// [kPrefixSize + 3..(3 + NumberOfBuckets() - 1)]: "hash table", +// where each item is an offset into the +// data table (see below) where the first +// item in this bucket is stored. +// [kPrefixSize + 3 + NumberOfBuckets()..length]: "data table", an +// array of length Capacity() * kEntrySize, +// where the first entrysize items are +// handled by the derived class and the +// item at kChainOffset is another entry +// into the data table indicating the next +// entry in this hash bucket. // // When we transition the table to a new version we obsolete it and reuse parts // of the memory to store information how to transition an iterator to the new // table: // // Memory layout for obsolete table: -// [0]: bucket count -// [1]: Next newer table -// [2]: Number of removed holes or -1 when the table was cleared. -// [3..(3 + NumberOfRemovedHoles() - 1)]: The indexes of the removed holes. -// [3 + NumberOfRemovedHoles()..length]: Not used -// +// [0] : Prefix +// [kPrefixSize + 0]: bucket count +// [kPrefixSize + 1]: Next newer table +// [kPrefixSize + 2]: Number of removed holes or -1 when the table was +// cleared. +// [kPrefixSize + 3..(3 + NumberOfRemovedHoles() - 1)]: The indexes +// of the removed holes. +// [kPrefixSize + 3 + NumberOfRemovedHoles()..length]: Not used template <class Derived, int entrysize> -class OrderedHashTable : public OrderedHashTableBase { +class OrderedHashTable : public FixedArray { public: - // Returns an OrderedHashTable with a capacity of at least |capacity|. - static Handle<Derived> Allocate(Isolate* isolate, int capacity, - PretenureFlag pretenure = NOT_TENURED); - // Returns an OrderedHashTable (possibly |table|) with enough space // to add at least one new element. static Handle<Derived> EnsureGrowable(Isolate* isolate, @@ -106,18 +75,20 @@ class OrderedHashTable : public OrderedHashTableBase { static Handle<Derived> Clear(Isolate* isolate, Handle<Derived> table); // Returns true if the OrderedHashTable contains the key - static bool HasKey(Isolate* isolate, Derived* table, Object* key); + static bool HasKey(Isolate* isolate, Derived table, Object key); // Returns a true value if the OrderedHashTable contains the key and // the key has been deleted. This does not shrink the table. - static bool Delete(Isolate* isolate, Derived* table, Object* key); + static bool Delete(Isolate* isolate, Derived table, Object key); + + int FindEntry(Isolate* isolate, Object key); int NumberOfElements() const { - return Smi::ToInt(get(kNumberOfElementsIndex)); + return Smi::ToInt(get(NumberOfElementsIndex())); } int NumberOfDeletedElements() const { - return Smi::ToInt(get(kNumberOfDeletedElementsIndex)); + return Smi::ToInt(get(NumberOfDeletedElementsIndex())); } // Returns the number of contiguous entries in the data table, starting at 0, @@ -126,99 +97,135 @@ class OrderedHashTable : public OrderedHashTableBase { return NumberOfElements() + NumberOfDeletedElements(); } - int NumberOfBuckets() const { return Smi::ToInt(get(kNumberOfBucketsIndex)); } + int NumberOfBuckets() const { + return Smi::ToInt(get(NumberOfBucketsIndex())); + } // Returns an index into |this| for the given entry. int EntryToIndex(int entry) { - return kHashTableStartIndex + NumberOfBuckets() + (entry * kEntrySize); + return HashTableStartIndex() + NumberOfBuckets() + (entry * kEntrySize); } int HashToBucket(int hash) { return hash & (NumberOfBuckets() - 1); } int HashToEntry(int hash) { int bucket = HashToBucket(hash); - Object* entry = this->get(kHashTableStartIndex + bucket); + Object entry = this->get(HashTableStartIndex() + bucket); return Smi::ToInt(entry); } - int KeyToFirstEntry(Isolate* isolate, Object* key) { - // This special cases for Smi, so that we avoid the HandleScope - // creation below. - if (key->IsSmi()) { - uint32_t hash = ComputeUnseededHash(Smi::ToInt(key)); - return HashToEntry(hash & Smi::kMaxValue); - } - 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; - return HashToEntry(Smi::ToInt(hash)); - } - - int FindEntry(Isolate* isolate, Object* key) { - int entry = KeyToFirstEntry(isolate, key); - // 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; - } - int NextChainEntry(int entry) { - Object* next_entry = get(EntryToIndex(entry) + kChainOffset); + Object next_entry = get(EntryToIndex(entry) + kChainOffset); return Smi::ToInt(next_entry); } // use KeyAt(i)->IsTheHole(isolate) to determine if this is a deleted entry. - Object* KeyAt(int entry) { + Object KeyAt(int entry) { DCHECK_LT(entry, this->UsedCapacity()); return get(EntryToIndex(entry)); } - bool IsObsolete() { return !get(kNextTableIndex)->IsSmi(); } + bool IsObsolete() { return !get(NextTableIndex())->IsSmi(); } // The next newer table. This is only valid if the table is obsolete. - Derived* NextTable() { return Derived::cast(get(kNextTableIndex)); } + Derived NextTable() { return Derived::cast(get(NextTableIndex())); } // When the table is obsolete we store the indexes of the removed holes. int RemovedIndexAt(int index) { - return Smi::ToInt(get(kRemovedHolesIndex + index)); + return Smi::ToInt(get(RemovedHolesIndex() + index)); } + // The extra +1 is for linking the bucket chains together. static const int kEntrySize = entrysize + 1; static const int kChainOffset = entrysize; - static const int kMaxCapacity = - (FixedArray::kMaxLength - kHashTableStartIndex) / - (1 + (kEntrySize * kLoadFactor)); + static const int kNotFound = -1; + static const int kMinCapacity = 4; + + static constexpr int PrefixIndex() { return 0; } + + static constexpr int NumberOfElementsIndex() { return Derived::kPrefixSize; } + + // The next table is stored at the same index as the nof elements. + static constexpr int NextTableIndex() { return NumberOfElementsIndex(); } + + static constexpr int NumberOfDeletedElementsIndex() { + return NumberOfElementsIndex() + 1; + } + + static constexpr int NumberOfBucketsIndex() { + return NumberOfDeletedElementsIndex() + 1; + } + + static constexpr int HashTableStartIndex() { + return NumberOfBucketsIndex() + 1; + } + + static constexpr int RemovedHolesIndex() { return HashTableStartIndex(); } + + static constexpr int NumberOfElementsOffset() { + return FixedArray::OffsetOfElementAt(NumberOfElementsIndex()); + } + + static constexpr int NextTableOffset() { + return FixedArray::OffsetOfElementAt(NextTableIndex()); + } + + static constexpr int NumberOfDeletedElementsOffset() { + return FixedArray::OffsetOfElementAt(NumberOfDeletedElementsIndex()); + } + + static constexpr int NumberOfBucketsOffset() { + return FixedArray::OffsetOfElementAt(NumberOfBucketsIndex()); + } + + static constexpr int HashTableStartOffset() { + return FixedArray::OffsetOfElementAt(HashTableStartIndex()); + } + + static const int kLoadFactor = 2; + + // NumberOfDeletedElements is set to kClearedTableSentinel when + // the table is cleared, which allows iterator transitions to + // optimize that case. + static const int kClearedTableSentinel = -1; + static constexpr int MaxCapacity() { + return (FixedArray::kMaxLength - HashTableStartIndex()) / + (1 + (kEntrySize * kLoadFactor)); + } protected: + // Returns an OrderedHashTable with a capacity of at least |capacity|. + static Handle<Derived> Allocate(Isolate* isolate, int capacity, + PretenureFlag pretenure = NOT_TENURED); static Handle<Derived> Rehash(Isolate* isolate, Handle<Derived> table, int new_capacity); void SetNumberOfBuckets(int num) { - set(kNumberOfBucketsIndex, Smi::FromInt(num)); + set(NumberOfBucketsIndex(), Smi::FromInt(num)); } void SetNumberOfElements(int num) { - set(kNumberOfElementsIndex, Smi::FromInt(num)); + set(NumberOfElementsIndex(), Smi::FromInt(num)); } void SetNumberOfDeletedElements(int num) { - set(kNumberOfDeletedElementsIndex, Smi::FromInt(num)); + set(NumberOfDeletedElementsIndex(), Smi::FromInt(num)); } // Returns the number elements that can fit into the allocated buffer. int Capacity() { return NumberOfBuckets() * kLoadFactor; } - void SetNextTable(Derived* next_table) { set(kNextTableIndex, next_table); } + void SetNextTable(Derived next_table) { set(NextTableIndex(), next_table); } void SetRemovedIndexAt(int index, int removed_index) { - return set(kRemovedHolesIndex + index, Smi::FromInt(removed_index)); + return set(RemovedHolesIndex() + index, Smi::FromInt(removed_index)); } + + OBJECT_CONSTRUCTORS(OrderedHashTable, FixedArray) + + private: + friend class OrderedNameDictionaryHandler; }; class OrderedHashSet : public OrderedHashTable<OrderedHashSet, 1> { @@ -231,9 +238,17 @@ class OrderedHashSet : public OrderedHashTable<OrderedHashSet, 1> { static Handle<FixedArray> ConvertToKeysArray(Isolate* isolate, Handle<OrderedHashSet> table, GetKeysConversion convert); - static HeapObject* GetEmpty(ReadOnlyRoots ro_roots); + static Handle<OrderedHashSet> Rehash(Isolate* isolate, + Handle<OrderedHashSet> table, + int new_capacity); + static Handle<OrderedHashSet> Allocate(Isolate* isolate, int capacity, + PretenureFlag pretenure = NOT_TENURED); + static HeapObject GetEmpty(ReadOnlyRoots ro_roots); static inline RootIndex GetMapRootIndex(); static inline bool Is(Handle<HeapObject> table); + static const int kPrefixSize = 0; + + OBJECT_CONSTRUCTORS(OrderedHashSet, OrderedHashTable<OrderedHashSet, 1>) }; class OrderedHashMap : public OrderedHashTable<OrderedHashMap, 2> { @@ -245,15 +260,26 @@ class OrderedHashMap : public OrderedHashTable<OrderedHashMap, 2> { static Handle<OrderedHashMap> Add(Isolate* isolate, Handle<OrderedHashMap> table, Handle<Object> key, Handle<Object> value); - Object* ValueAt(int entry); - static Object* GetHash(Isolate* isolate, Object* key); + static Handle<OrderedHashMap> Allocate(Isolate* isolate, int capacity, + PretenureFlag pretenure = NOT_TENURED); + static Handle<OrderedHashMap> Rehash(Isolate* isolate, + Handle<OrderedHashMap> table, + int new_capacity); + Object ValueAt(int entry); + + // This takes and returns raw Address values containing tagged Object + // pointers because it is called via ExternalReference. + static Address GetHash(Isolate* isolate, Address raw_key); - static HeapObject* GetEmpty(ReadOnlyRoots ro_roots); + static HeapObject GetEmpty(ReadOnlyRoots ro_roots); static inline RootIndex GetMapRootIndex(); static inline bool Is(Handle<HeapObject> table); static const int kValueOffset = 1; + static const int kPrefixSize = 0; + + OBJECT_CONSTRUCTORS(OrderedHashMap, OrderedHashTable<OrderedHashMap, 2>) }; // This is similar to the OrderedHashTable, except for the memory @@ -265,11 +291,20 @@ class OrderedHashMap : public OrderedHashTable<OrderedHashMap, 2> { // that the DataTable entries start aligned. A bucket or chain value // of 255 is used to denote an unknown entry. // -// Memory layout: [ Header ] [ Padding ] [ DataTable ] [ HashTable ] [ Chains ] +// The prefix size is calculated as the kPrefixSize * kTaggedSize. +// +// Memory layout: [ Prefix ] [ Header ] [ Padding ] [ DataTable ] [ HashTable ] +// [ Chains ] // // The index are represented as bytes, on a 64 bit machine with // kEntrySize = 1, capacity = 4 and entries = 2: // +// [ 0 ] : Prefix +// +// Note: For the sake of brevity, the following start with index 0 +// but, they actually start from kPrefixSize * kTaggedSize to +// account for the the prefix. +// // [ Header ] : // [0] : Number of elements // [1] : Number of deleted elements @@ -314,15 +349,15 @@ class SmallOrderedHashTable : public HeapObject { // Returns a true value if the table contains the key and // the key has been deleted. This does not shrink the table. - static bool Delete(Isolate* isolate, Derived* table, Object* key); + static bool Delete(Isolate* isolate, Derived table, Object key); // Returns an SmallOrderedHashTable (possibly |table|) with enough // space to add at least one new element. Returns empty handle if // we've already reached MaxCapacity. static MaybeHandle<Derived> Grow(Isolate* isolate, Handle<Derived> table); - static Handle<Derived> Rehash(Isolate* isolate, Handle<Derived> table, - int new_capacity); + int FindEntry(Isolate* isolate, Object key); + static Handle<Derived> Shrink(Isolate* isolate, Handle<Derived> table); // Iterates only fields in the DataTable. class BodyDescriptor; @@ -336,10 +371,10 @@ class SmallOrderedHashTable : public HeapObject { int data_table_size = DataTableSizeFor(capacity); int hash_table_size = capacity / kLoadFactor; int chain_table_size = capacity; - int total_size = kDataTableStartOffset + data_table_size + hash_table_size + - chain_table_size; + int total_size = DataTableStartOffset() + data_table_size + + hash_table_size + chain_table_size; - return RoundUp(total_size, kPointerSize); + return RoundUp(total_size, kTaggedSize); } // Returns the number elements that can fit into the allocated table. @@ -353,20 +388,26 @@ class SmallOrderedHashTable : public HeapObject { // Returns the number elements that are present in the table. int NumberOfElements() const { - int nof_elements = getByte(kNumberOfElementsOffset, 0); + int nof_elements = getByte(NumberOfElementsOffset(), 0); DCHECK_LE(nof_elements, Capacity()); return nof_elements; } int NumberOfDeletedElements() const { - int nof_deleted_elements = getByte(kNumberOfDeletedElementsOffset, 0); + int nof_deleted_elements = getByte(NumberOfDeletedElementsOffset(), 0); DCHECK_LE(nof_deleted_elements, Capacity()); return nof_deleted_elements; } - int NumberOfBuckets() const { return getByte(kNumberOfBucketsOffset, 0); } + int NumberOfBuckets() const { return getByte(NumberOfBucketsOffset(), 0); } + + Object KeyAt(int entry) const { + DCHECK_LT(entry, Capacity()); + Offset entry_offset = GetDataEntryOffset(entry, Derived::kKeyIndex); + return READ_FIELD(this, entry_offset); + } DECL_VERIFIER(SmallOrderedHashTable) @@ -394,18 +435,22 @@ class SmallOrderedHashTable : public HeapObject { static const int kGrowthHack = 256; protected: - void SetDataEntry(int entry, int relative_index, Object* value); + static Handle<Derived> Rehash(Isolate* isolate, Handle<Derived> table, + int new_capacity); + + void SetDataEntry(int entry, int relative_index, Object value); // TODO(gsathya): Calculate all the various possible values for this // at compile time since capacity can only be 4 different values. Offset GetBucketsStartOffset() const { int capacity = Capacity(); int data_table_size = DataTableSizeFor(capacity); - return kDataTableStartOffset + data_table_size; + return DataTableStartOffset() + data_table_size; } Address GetHashTableStartAddress(int capacity) const { - return FIELD_ADDR(this, kDataTableStartOffset + DataTableSizeFor(capacity)); + return FIELD_ADDR(this, + DataTableStartOffset() + DataTableSizeFor(capacity)); } void SetFirstEntry(int bucket, byte value) { @@ -427,7 +472,7 @@ class SmallOrderedHashTable : public HeapObject { int data_table_size = DataTableSizeFor(capacity); int hash_table_size = nof_buckets; - return kDataTableStartOffset + data_table_size + hash_table_size; + return DataTableStartOffset() + data_table_size + hash_table_size; } void SetNextEntry(int entry, int next_entry) { @@ -442,19 +487,13 @@ class SmallOrderedHashTable : public HeapObject { return getByte(GetChainTableOffset(), entry); } - Object* GetDataEntry(int entry, int relative_index) { + Object GetDataEntry(int entry, int relative_index) { DCHECK_LT(entry, Capacity()); DCHECK_LE(static_cast<unsigned>(relative_index), Derived::kEntrySize); Offset entry_offset = GetDataEntryOffset(entry, relative_index); return READ_FIELD(this, entry_offset); } - Object* KeyAt(int entry) const { - DCHECK_LT(entry, Capacity()); - Offset entry_offset = GetDataEntryOffset(entry, Derived::kKeyIndex); - return READ_FIELD(this, entry_offset); - } - int HashToBucket(int hash) const { return hash & (NumberOfBuckets() - 1); } int HashToFirstEntry(int hash) const { @@ -464,63 +503,59 @@ class SmallOrderedHashTable : public HeapObject { return entry; } - void SetNumberOfBuckets(int num) { setByte(kNumberOfBucketsOffset, 0, num); } + void SetNumberOfBuckets(int num) { setByte(NumberOfBucketsOffset(), 0, num); } void SetNumberOfElements(int num) { DCHECK_LE(static_cast<unsigned>(num), Capacity()); - setByte(kNumberOfElementsOffset, 0, num); + setByte(NumberOfElementsOffset(), 0, num); } void SetNumberOfDeletedElements(int num) { DCHECK_LE(static_cast<unsigned>(num), Capacity()); - setByte(kNumberOfDeletedElementsOffset, 0, num); + setByte(NumberOfDeletedElementsOffset(), 0, num); } - int FindEntry(Isolate* isolate, Object* key) { - DisallowHeapAllocation no_gc; - Object* hash = key->GetHash(); + static constexpr Offset PrefixOffset() { return kHeaderSize; } - if (hash->IsUndefined(isolate)) return kNotFound; - int entry = HashToFirstEntry(Smi::ToInt(hash)); + static constexpr Offset NumberOfElementsOffset() { + return PrefixOffset() + (Derived::kPrefixSize * kTaggedSize); + } - // 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; + static constexpr Offset NumberOfDeletedElementsOffset() { + return NumberOfElementsOffset() + kOneByteSize; } - static const Offset kNumberOfElementsOffset = kHeaderSize; - static const Offset kNumberOfDeletedElementsOffset = - kNumberOfElementsOffset + kOneByteSize; - static const Offset kNumberOfBucketsOffset = - kNumberOfDeletedElementsOffset + kOneByteSize; - static const constexpr Offset kDataTableStartOffset = - RoundUp<kPointerSize>(kNumberOfBucketsOffset); + static constexpr Offset NumberOfBucketsOffset() { + return NumberOfDeletedElementsOffset() + kOneByteSize; + } + + static constexpr Offset DataTableStartOffset() { + return RoundUp<kTaggedSize>(NumberOfBucketsOffset()); + } static constexpr int DataTableSizeFor(int capacity) { - return capacity * Derived::kEntrySize * kPointerSize; + return capacity * Derived::kEntrySize * kTaggedSize; } // This is used for accessing the non |DataTable| part of the // structure. byte getByte(Offset offset, ByteIndex index) const { - DCHECK(offset < kDataTableStartOffset || offset >= GetBucketsStartOffset()); + DCHECK(offset < DataTableStartOffset() || + offset >= GetBucketsStartOffset()); return READ_BYTE_FIELD(this, offset + (index * kOneByteSize)); } void setByte(Offset offset, ByteIndex index, byte value) { - DCHECK(offset < kDataTableStartOffset || offset >= GetBucketsStartOffset()); + DCHECK(offset < DataTableStartOffset() || + offset >= GetBucketsStartOffset()); WRITE_BYTE_FIELD(this, offset + (index * kOneByteSize), value); } Offset GetDataEntryOffset(int entry, int relative_index) const { DCHECK_LT(entry, Capacity()); - int offset_in_datatable = entry * Derived::kEntrySize * kPointerSize; - int offset_in_entry = relative_index * kPointerSize; - return kDataTableStartOffset + offset_in_datatable + offset_in_entry; + int offset_in_datatable = entry * Derived::kEntrySize * kTaggedSize; + int offset_in_entry = relative_index * kTaggedSize; + return DataTableStartOffset() + offset_in_datatable + offset_in_entry; } int UsedCapacity() const { @@ -533,7 +568,10 @@ class SmallOrderedHashTable : public HeapObject { private: friend class OrderedHashMapHandler; friend class OrderedHashSetHandler; + friend class OrderedNameDictionaryHandler; friend class CodeStubAssembler; + + OBJECT_CONSTRUCTORS(SmallOrderedHashTable, HeapObject) }; class SmallOrderedHashSet : public SmallOrderedHashTable<SmallOrderedHashSet> { @@ -541,9 +579,11 @@ class SmallOrderedHashSet : public SmallOrderedHashTable<SmallOrderedHashSet> { DECL_CAST(SmallOrderedHashSet) DECL_PRINTER(SmallOrderedHashSet) + DECL_VERIFIER(SmallOrderedHashSet) static const int kKeyIndex = 0; static const int kEntrySize = 1; + static const int kPrefixSize = 0; // Adds |value| to |table|, if the capacity isn't enough, a new // table is created. The original |table| is returned if there is @@ -553,6 +593,11 @@ class SmallOrderedHashSet : public SmallOrderedHashTable<SmallOrderedHashSet> { Handle<Object> key); static inline bool Is(Handle<HeapObject> table); static inline RootIndex GetMapRootIndex(); + static Handle<SmallOrderedHashSet> Rehash(Isolate* isolate, + Handle<SmallOrderedHashSet> table, + int new_capacity); + OBJECT_CONSTRUCTORS(SmallOrderedHashSet, + SmallOrderedHashTable<SmallOrderedHashSet>) }; class SmallOrderedHashMap : public SmallOrderedHashTable<SmallOrderedHashMap> { @@ -560,10 +605,12 @@ class SmallOrderedHashMap : public SmallOrderedHashTable<SmallOrderedHashMap> { DECL_CAST(SmallOrderedHashMap) DECL_PRINTER(SmallOrderedHashMap) + DECL_VERIFIER(SmallOrderedHashMap) static const int kKeyIndex = 0; static const int kValueIndex = 1; static const int kEntrySize = 2; + static const int kPrefixSize = 0; // Adds |value| to |table|, if the capacity isn't enough, a new // table is created. The original |table| is returned if there is @@ -574,6 +621,13 @@ class SmallOrderedHashMap : public SmallOrderedHashTable<SmallOrderedHashMap> { Handle<Object> value); static inline bool Is(Handle<HeapObject> table); static inline RootIndex GetMapRootIndex(); + + static Handle<SmallOrderedHashMap> Rehash(Isolate* isolate, + Handle<SmallOrderedHashMap> table, + int new_capacity); + + OBJECT_CONSTRUCTORS(SmallOrderedHashMap, + SmallOrderedHashTable<SmallOrderedHashMap>) }; // TODO(gsathya): Rename this to OrderedHashTable, after we rename @@ -613,6 +667,149 @@ class OrderedHashSetHandler Isolate* isolate, Handle<SmallOrderedHashSet> table); }; +class OrderedNameDictionary + : public OrderedHashTable<OrderedNameDictionary, 3> { + public: + DECL_CAST(OrderedNameDictionary) + + static Handle<OrderedNameDictionary> Add(Isolate* isolate, + Handle<OrderedNameDictionary> table, + Handle<Name> key, + Handle<Object> value, + PropertyDetails details); + + void SetEntry(Isolate* isolate, int entry, Object key, Object value, + PropertyDetails details); + + static Handle<OrderedNameDictionary> DeleteEntry( + Isolate* isolate, Handle<OrderedNameDictionary> table, int entry); + + static Handle<OrderedNameDictionary> Allocate( + Isolate* isolate, int capacity, PretenureFlag pretenure = NOT_TENURED); + + static Handle<OrderedNameDictionary> Rehash( + Isolate* isolate, Handle<OrderedNameDictionary> table, int new_capacity); + + // Returns the value for entry. + inline Object ValueAt(int entry); + + // Set the value for entry. + inline void ValueAtPut(int entry, Object value); + + // Returns the property details for the property at entry. + inline PropertyDetails DetailsAt(int entry); + + // Set the details for entry. + inline void DetailsAtPut(int entry, PropertyDetails value); + + inline void SetHash(int hash); + inline int Hash(); + + static HeapObject GetEmpty(ReadOnlyRoots ro_roots); + static inline RootIndex GetMapRootIndex(); + + static const int kValueOffset = 1; + static const int kPropertyDetailsOffset = 2; + static const int kPrefixSize = 1; + + OBJECT_CONSTRUCTORS(OrderedNameDictionary, + OrderedHashTable<OrderedNameDictionary, 3>) +}; + +class OrderedNameDictionaryHandler + : public OrderedHashTableHandler<SmallOrderedNameDictionary, + OrderedNameDictionary> { + public: + static Handle<HeapObject> Add(Isolate* isolate, Handle<HeapObject> table, + Handle<Name> key, Handle<Object> value, + PropertyDetails details); + static Handle<HeapObject> Shrink(Isolate* isolate, Handle<HeapObject> table); + + static Handle<HeapObject> DeleteEntry(Isolate* isolate, + Handle<HeapObject> table, int entry); + static int FindEntry(Isolate* isolate, HeapObject table, Name key); + static void SetEntry(Isolate* isolate, HeapObject table, int entry, + Object key, Object value, PropertyDetails details); + + // Returns the value for entry. + static Object ValueAt(HeapObject table, int entry); + + // Set the value for entry. + static void ValueAtPut(HeapObject table, int entry, Object value); + + // Returns the property details for the property at entry. + static PropertyDetails DetailsAt(HeapObject table, int entry); + + // Set the details for entry. + static void DetailsAtPut(HeapObject table, int entry, PropertyDetails value); + + static Name KeyAt(HeapObject table, int entry); + + static void SetHash(HeapObject table, int hash); + static int Hash(HeapObject table); + + static int NumberOfElements(HeapObject table); + static int Capacity(HeapObject table); + + static const int kNotFound = -1; + + protected: + static Handle<OrderedNameDictionary> AdjustRepresentation( + Isolate* isolate, Handle<SmallOrderedNameDictionary> table); +}; + +class SmallOrderedNameDictionary + : public SmallOrderedHashTable<SmallOrderedNameDictionary> { + public: + DECL_CAST(SmallOrderedNameDictionary) + + DECL_PRINTER(SmallOrderedNameDictionary) + DECL_VERIFIER(SmallOrderedNameDictionary) + + // Returns the value for entry. + inline Object ValueAt(int entry); + + static Handle<SmallOrderedNameDictionary> Rehash( + Isolate* isolate, Handle<SmallOrderedNameDictionary> table, + int new_capacity); + + static Handle<SmallOrderedNameDictionary> DeleteEntry( + Isolate* isolate, Handle<SmallOrderedNameDictionary> table, int entry); + + // Set the value for entry. + inline void ValueAtPut(int entry, Object value); + + // Returns the property details for the property at entry. + inline PropertyDetails DetailsAt(int entry); + + // Set the details for entry. + inline void DetailsAtPut(int entry, PropertyDetails value); + + inline void SetHash(int hash); + inline int Hash(); + + static const int kKeyIndex = 0; + static const int kValueIndex = 1; + static const int kPropertyDetailsIndex = 2; + static const int kEntrySize = 3; + static const int kPrefixSize = 1; + + // Adds |value| to |table|, if the capacity isn't enough, a new + // table is created. The original |table| is returned if there is + // capacity to store |value| otherwise the new table is returned. + static MaybeHandle<SmallOrderedNameDictionary> Add( + Isolate* isolate, Handle<SmallOrderedNameDictionary> table, + Handle<Name> key, Handle<Object> value, PropertyDetails details); + + void SetEntry(Isolate* isolate, int entry, Object key, Object value, + PropertyDetails details); + + static inline RootIndex GetMapRootIndex(); + + OBJECT_CONSTRUCTORS(SmallOrderedNameDictionary, + SmallOrderedHashTable<SmallOrderedNameDictionary>) +}; + class JSCollectionIterator : public JSObject { public: // [table]: the backing hash table mapping keys to values. @@ -621,15 +818,20 @@ class JSCollectionIterator : public JSObject { // [index]: The index into the data table. DECL_ACCESSORS(index, Object) - // Dispatched behavior. - DECL_PRINTER(JSCollectionIterator) + void JSCollectionIteratorPrint(std::ostream& os, const char* name); - static const int kTableOffset = JSObject::kHeaderSize; - static const int kIndexOffset = kTableOffset + kPointerSize; - static const int kSize = kIndexOffset + kPointerSize; +// Layout description. +#define JS_COLLECTION_ITERATOR_FIELDS(V) \ + V(kTableOffset, kTaggedSize) \ + V(kIndexOffset, kTaggedSize) \ + /* Header size. */ \ + V(kSize, 0) - private: - DISALLOW_IMPLICIT_CONSTRUCTORS(JSCollectionIterator); + DEFINE_FIELD_OFFSET_CONSTANTS(JSObject::kHeaderSize, + JS_COLLECTION_ITERATOR_FIELDS) +#undef JS_COLLECTION_ITERATOR_FIELDS + + OBJECT_CONSTRUCTORS(JSCollectionIterator, JSObject); }; // OrderedHashTableIterator is an iterator that iterates over the keys and @@ -656,14 +858,14 @@ class OrderedHashTableIterator : public JSCollectionIterator { // Returns the current key of the iterator. This should only be called when // |HasMore| returns true. - inline Object* CurrentKey(); + inline Object CurrentKey(); private: // Transitions the iterator to the non obsolete backing store. This is a NOP // if the [table] is not obsolete. void Transition(); - DISALLOW_IMPLICIT_CONSTRUCTORS(OrderedHashTableIterator); + OBJECT_CONSTRUCTORS(OrderedHashTableIterator, JSCollectionIterator); }; } // namespace internal |