diff options
author | Michaƫl Zasso <targos@protonmail.com> | 2017-09-12 11:34:59 +0200 |
---|---|---|
committer | Anna Henningsen <anna@addaleax.net> | 2017-09-13 16:15:18 +0200 |
commit | d82e1075dbc2cec2d6598ade10c1f43805f690fd (patch) | |
tree | ccd242b9b491dfc341d1099fe11b0ef528839877 /deps/v8/src/objects/hash-table.h | |
parent | b4b7ac6ae811b2b5a3082468115dfb5a5246fe3f (diff) | |
download | node-new-d82e1075dbc2cec2d6598ade10c1f43805f690fd.tar.gz |
deps: update V8 to 6.1.534.36
PR-URL: https://github.com/nodejs/node/pull/14730
Reviewed-By: Ben Noordhuis <info@bnoordhuis.nl>
Reviewed-By: Ali Ijaz Sheikh <ofrobots@google.com>
Reviewed-By: Colin Ihrig <cjihrig@gmail.com>
Reviewed-By: Matteo Collina <matteo.collina@gmail.com>
Diffstat (limited to 'deps/v8/src/objects/hash-table.h')
-rw-r--r-- | deps/v8/src/objects/hash-table.h | 576 |
1 files changed, 413 insertions, 163 deletions
diff --git a/deps/v8/src/objects/hash-table.h b/deps/v8/src/objects/hash-table.h index 0eac3a2342..90146c8f29 100644 --- a/deps/v8/src/objects/hash-table.h +++ b/deps/v8/src/objects/hash-table.h @@ -27,16 +27,16 @@ namespace internal { // - Elements with key == undefined have not been used yet. // - Elements with key == the_hole have been deleted. // -// The hash table class is parameterized with a Shape and a Key. +// The hash table class is parameterized with a Shape. // Shape must be a class with the following interface: // class ExampleShape { // public: -// // Tells whether key matches other. +// // Tells whether key matches other. // static bool IsMatch(Key key, Object* other); // // Returns the hash value for key. -// static uint32_t Hash(Key key); +// static uint32_t Hash(Isolate* isolate, Key key); // // Returns the hash value for object. -// static uint32_t HashForObject(Key key, Object* object); +// static uint32_t HashForObject(Isolate* isolate, Object* object); // // Convert key to an object. // static inline Handle<Object> AsHandle(Isolate* isolate, Key key); // // The prefix size indicates number of elements in the beginning @@ -44,38 +44,37 @@ namespace internal { // static const int kPrefixSize = ..; // // The Element size indicates number of elements per entry. // static const int kEntrySize = ..; +// // Indicates whether IsMatch can deal with other being the_hole (a +// // deleted entry). +// static const bool kNeedsHoleCheck = ..; // }; // The prefix size indicates an amount of memory in the // beginning of the backing storage that can be used for non-element // information by subclasses. -template <typename Key> +template <typename KeyT> class BaseShape { public: - static const bool UsesSeed = false; - static uint32_t Hash(Key key) { return 0; } - static uint32_t SeededHash(Key key, uint32_t seed) { - DCHECK(UsesSeed); - return Hash(key); - } - static uint32_t HashForObject(Key key, Object* object) { return 0; } - static uint32_t SeededHashForObject(Key key, uint32_t seed, Object* object) { - DCHECK(UsesSeed); - return HashForObject(key, object); - } + typedef KeyT Key; static inline Map* GetMap(Isolate* isolate); + static const bool kNeedsHoleCheck = true; + static Object* Unwrap(Object* key) { return key; } + static bool IsKey(Isolate* isolate, Object* key) { + return IsLive(isolate, key); + } + static inline bool IsLive(Isolate* isolate, Object* key); }; class V8_EXPORT_PRIVATE HashTableBase : public NON_EXPORTED_BASE(FixedArray) { public: // Returns the number of elements in the hash table. - inline int NumberOfElements(); + inline int NumberOfElements() const; // Returns the number of deleted elements in the hash table. - inline int NumberOfDeletedElements(); + inline int NumberOfDeletedElements() const; // Returns the capacity of the hash table. - inline int Capacity(); + inline int Capacity() const; // ElementAdded should be called whenever an element is added to a // hash table. @@ -90,10 +89,6 @@ class V8_EXPORT_PRIVATE HashTableBase : public NON_EXPORTED_BASE(FixedArray) { // number of elements. May be more than HashTable::kMaxCapacity. static inline int ComputeCapacity(int at_least_space_for); - // Tells whether k is a real key. The hole and undefined are not allowed - // as keys and can be used to indicate missing or deleted elements. - inline bool IsKey(Isolate* isolate, Object* k); - // Compute the probe offset (quadratic probing). INLINE(static uint32_t GetProbeOffset(uint32_t n)) { return (n + n * n) >> 1; @@ -119,7 +114,7 @@ class V8_EXPORT_PRIVATE HashTableBase : public NON_EXPORTED_BASE(FixedArray) { // Returns probe entry. static uint32_t GetProbe(uint32_t hash, uint32_t number, uint32_t size) { - DCHECK(base::bits::IsPowerOfTwo32(size)); + DCHECK(base::bits::IsPowerOfTwo(size)); return (hash + GetProbeOffset(number)) & (size - 1); } @@ -133,23 +128,19 @@ class V8_EXPORT_PRIVATE HashTableBase : public NON_EXPORTED_BASE(FixedArray) { } }; -template <typename Derived, typename Shape, typename Key> +template <typename Derived, typename Shape> class HashTable : public HashTableBase { public: typedef Shape ShapeT; - - // Wrapper methods. Defined in src/objects/hash-table-inl.h - // to break a cycle with src/heap/heap.h - inline uint32_t Hash(Key key); - inline uint32_t HashForObject(Key key, Object* object); + typedef typename Shape::Key Key; // Returns a new HashTable object. MUST_USE_RESULT static Handle<Derived> New( Isolate* isolate, int at_least_space_for, - MinimumCapacity capacity_option = USE_DEFAULT_MINIMUM_CAPACITY, - PretenureFlag pretenure = NOT_TENURED); + PretenureFlag pretenure = NOT_TENURED, + MinimumCapacity capacity_option = USE_DEFAULT_MINIMUM_CAPACITY); - DECLARE_CAST(HashTable) + DECL_CAST(HashTable) // Garbage collection support. void IteratePrefix(ObjectVisitor* visitor); @@ -159,11 +150,22 @@ class HashTable : public HashTableBase { inline int FindEntry(Key key); inline int FindEntry(Isolate* isolate, Key key, int32_t hash); int FindEntry(Isolate* isolate, Key key); - inline bool Has(Isolate* isolate, Key key); - inline bool Has(Key key); // Rehashes the table in-place. - void Rehash(Key key); + void Rehash(); + + // Tells whether k is a real key. The hole and undefined are not allowed + // as keys and can be used to indicate missing or deleted elements. + static bool IsKey(Isolate* isolate, Object* k) { + return Shape::IsKey(isolate, k); + } + + inline bool ToKey(Isolate* isolate, int entry, Object** out_k) { + Object* k = KeyAt(entry); + if (!IsKey(isolate, k)) return false; + *out_k = Shape::Unwrap(k); + return true; + } // Returns the key at entry. Object* KeyAt(int entry) { return get(EntryToIndex(entry) + kEntryKeyIndex); } @@ -188,31 +190,31 @@ class HashTable : public HashTableBase { return (entry * kEntrySize) + kElementsStartIndex; } + // Ensure enough space for n additional elements. + MUST_USE_RESULT static Handle<Derived> EnsureCapacity( + Handle<Derived> table, int n, PretenureFlag pretenure = NOT_TENURED); + + // Returns true if this table has sufficient capacity for adding n elements. + bool HasSufficientCapacityToAdd(int number_of_additional_elements); + protected: friend class ObjectHashTable; - MUST_USE_RESULT static Handle<Derived> New(Isolate* isolate, int capacity, - PretenureFlag pretenure); + MUST_USE_RESULT static Handle<Derived> NewInternal(Isolate* isolate, + int capacity, + PretenureFlag pretenure); // Find the entry at which to insert element with the given key that // has the given hash value. uint32_t FindInsertionEntry(uint32_t hash); // Attempt to shrink hash table after removal of key. - MUST_USE_RESULT static Handle<Derived> Shrink(Handle<Derived> table, Key key); - - // Ensure enough space for n additional elements. - MUST_USE_RESULT static Handle<Derived> EnsureCapacity( - Handle<Derived> table, int n, Key key, - PretenureFlag pretenure = NOT_TENURED); - - // Returns true if this table has sufficient capacity for adding n elements. - bool HasSufficientCapacityToAdd(int number_of_additional_elements); + MUST_USE_RESULT static Handle<Derived> Shrink(Handle<Derived> table); private: // Ensure that kMaxRegularCapacity yields a non-large object dictionary. STATIC_ASSERT(EntryToIndex(kMaxRegularCapacity) < kMaxRegularLength); - STATIC_ASSERT(v8::base::bits::IsPowerOfTwo32(kMaxRegularCapacity)); + STATIC_ASSERT(v8::base::bits::IsPowerOfTwo(kMaxRegularCapacity)); static const int kMaxRegularEntry = kMaxRegularCapacity / kEntrySize; static const int kMaxRegularIndex = EntryToIndex(kMaxRegularEntry); STATIC_ASSERT(OffsetOfElementAt(kMaxRegularIndex) < @@ -231,52 +233,60 @@ class HashTable : public HashTableBase { // Returns _expected_ if one of entries given by the first _probe_ probes is // equal to _expected_. Otherwise, returns the entry given by the probe // number _probe_. - uint32_t EntryForProbe(Key key, Object* k, int probe, uint32_t expected); + uint32_t EntryForProbe(Object* k, int probe, uint32_t expected); void Swap(uint32_t entry1, uint32_t entry2, WriteBarrierMode mode); // Rehashes this hash-table into the new table. - void Rehash(Handle<Derived> new_table, Key key); + void Rehash(Derived* new_table); }; // HashTableKey is an abstract superclass for virtual key behavior. class HashTableKey { public: + explicit HashTableKey(uint32_t hash) : hash_(hash) {} + // Returns whether the other object matches this key. virtual bool IsMatch(Object* other) = 0; // Returns the hash value for this key. - virtual uint32_t Hash() = 0; - // Returns the hash value for object. - virtual uint32_t HashForObject(Object* key) = 0; - // Returns the key object for storing into the hash table. - MUST_USE_RESULT virtual Handle<Object> AsHandle(Isolate* isolate) = 0; // Required. virtual ~HashTableKey() {} + + uint32_t Hash() const { return hash_; } + + protected: + void set_hash(uint32_t hash) { + DCHECK_EQ(0, hash_); + hash_ = hash; + } + + private: + uint32_t hash_ = 0; }; class ObjectHashTableShape : public BaseShape<Handle<Object>> { public: static inline bool IsMatch(Handle<Object> key, Object* other); - static inline uint32_t Hash(Handle<Object> key); - static inline uint32_t HashForObject(Handle<Object> key, Object* object); + static inline uint32_t Hash(Isolate* isolate, Handle<Object> key); + static inline uint32_t HashForObject(Isolate* isolate, Object* object); static inline Handle<Object> AsHandle(Isolate* isolate, Handle<Object> key); static const int kPrefixSize = 0; static const int kEntrySize = 2; + static const bool kNeedsHoleCheck = false; }; // ObjectHashTable maps keys that are arbitrary objects to object values by // using the identity hash of the key for hashing purposes. class ObjectHashTable - : public HashTable<ObjectHashTable, ObjectHashTableShape, Handle<Object>> { - typedef HashTable<ObjectHashTable, ObjectHashTableShape, Handle<Object>> - DerivedHashTable; + : public HashTable<ObjectHashTable, ObjectHashTableShape> { + typedef HashTable<ObjectHashTable, ObjectHashTableShape> DerivedHashTable; public: - DECLARE_CAST(ObjectHashTable) + DECL_CAST(ObjectHashTable) // Attempt to shrink hash table after removal of key. MUST_USE_RESULT static inline Handle<ObjectHashTable> Shrink( - Handle<ObjectHashTable> table, Handle<Object> key); + Handle<ObjectHashTable> table); // Looks up the value associated with the given key. The hole value is // returned in case the key is not present. @@ -319,8 +329,7 @@ class ObjectHashSetShape : public ObjectHashTableShape { static const int kEntrySize = 1; }; -class ObjectHashSet - : public HashTable<ObjectHashSet, ObjectHashSetShape, Handle<Object>> { +class ObjectHashSet : public HashTable<ObjectHashSet, ObjectHashSetShape> { public: static Handle<ObjectHashSet> Add(Handle<ObjectHashSet> set, Handle<Object> key); @@ -328,7 +337,41 @@ class ObjectHashSet inline bool Has(Isolate* isolate, Handle<Object> key, int32_t hash); inline bool Has(Isolate* isolate, Handle<Object> key); - DECLARE_CAST(ObjectHashSet) + DECL_CAST(ObjectHashSet) +}; + +// 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 @@ -368,7 +411,7 @@ class ObjectHashSet // [3 + NumberOfRemovedHoles()..length]: Not used // template <class Derived, int entrysize> -class OrderedHashTable : public FixedArray { +class OrderedHashTable : public OrderedHashTableBase { public: // Returns an OrderedHashTable with a capacity of at least |capacity|. static Handle<Derived> Allocate(Isolate* isolate, int capacity, @@ -386,24 +429,24 @@ class OrderedHashTable : public FixedArray { // existing iterators can be updated. static Handle<Derived> Clear(Handle<Derived> table); - // Returns a true if the OrderedHashTable contains the key - static bool HasKey(Handle<Derived> table, Handle<Object> key); + // Returns true if the OrderedHashTable contains the key + static bool HasKey(Isolate* isolate, Derived* table, Object* key); - int NumberOfElements() { - return Smi::cast(get(kNumberOfElementsIndex))->value(); - } + // 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); + + int NumberOfElements() { return Smi::ToInt(get(kNumberOfElementsIndex)); } int NumberOfDeletedElements() { - return Smi::cast(get(kNumberOfDeletedElementsIndex))->value(); + return Smi::ToInt(get(kNumberOfDeletedElementsIndex)); } // Returns the number of contiguous entries in the data table, starting at 0, // that either are real entries or have been deleted. int UsedCapacity() { return NumberOfElements() + NumberOfDeletedElements(); } - int NumberOfBuckets() { - return Smi::cast(get(kNumberOfBucketsIndex))->value(); - } + int NumberOfBuckets() { return Smi::ToInt(get(kNumberOfBucketsIndex)); } // Returns an index into |this| for the given entry. int EntryToIndex(int entry) { @@ -415,19 +458,38 @@ class OrderedHashTable : public FixedArray { int HashToEntry(int hash) { int bucket = HashToBucket(hash); Object* entry = this->get(kHashTableStartIndex + bucket); - return Smi::cast(entry)->value(); + 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 = ComputeIntegerHash(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::cast(hash)->value()); + 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); - return Smi::cast(next_entry)->value(); + return Smi::ToInt(next_entry); } // use KeyAt(i)->IsTheHole(isolate) to determine if this is a deleted entry. @@ -443,39 +505,15 @@ class OrderedHashTable : public FixedArray { // When the table is obsolete we store the indexes of the removed holes. int RemovedIndexAt(int index) { - return Smi::cast(get(kRemovedHolesIndex + index))->value(); + return Smi::ToInt(get(kRemovedHolesIndex + index)); } - 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 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 kEntrySize = entrysize + 1; static const int kChainOffset = entrysize; - 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 const int kMaxCapacity = + (FixedArray::kMaxLength - kHashTableStartIndex) / + (1 + (kEntrySize * kLoadFactor)); protected: static Handle<Derived> Rehash(Handle<Derived> table, int new_capacity); @@ -500,17 +538,11 @@ class OrderedHashTable : public FixedArray { void SetRemovedIndexAt(int index, int removed_index) { return set(kRemovedHolesIndex + index, Smi::FromInt(removed_index)); } - - static const int kRemovedHolesIndex = kHashTableStartIndex; - - static const int kMaxCapacity = - (FixedArray::kMaxLength - kHashTableStartIndex) / - (1 + (kEntrySize * kLoadFactor)); }; class OrderedHashSet : public OrderedHashTable<OrderedHashSet, 1> { public: - DECLARE_CAST(OrderedHashSet) + DECL_CAST(OrderedHashSet) static Handle<OrderedHashSet> Add(Handle<OrderedHashSet> table, Handle<Object> value); @@ -520,9 +552,15 @@ class OrderedHashSet : public OrderedHashTable<OrderedHashSet, 1> { class OrderedHashMap : public OrderedHashTable<OrderedHashMap, 2> { public: - DECLARE_CAST(OrderedHashMap) + DECL_CAST(OrderedHashMap) + + // Returns a value if the OrderedHashMap contains the key, otherwise + // returns undefined. + static Handle<OrderedHashMap> Add(Handle<OrderedHashMap> table, + Handle<Object> key, Handle<Object> value); + Object* ValueAt(int entry); - inline Object* ValueAt(int entry); + static Object* GetHash(Isolate* isolate, Object* key); static const int kValueOffset = 1; }; @@ -531,23 +569,22 @@ template <int entrysize> class WeakHashTableShape : public BaseShape<Handle<Object>> { public: static inline bool IsMatch(Handle<Object> key, Object* other); - static inline uint32_t Hash(Handle<Object> key); - static inline uint32_t HashForObject(Handle<Object> key, Object* object); + static inline uint32_t Hash(Isolate* isolate, Handle<Object> key); + static inline uint32_t HashForObject(Isolate* isolate, Object* object); static inline Handle<Object> AsHandle(Isolate* isolate, Handle<Object> key); static const int kPrefixSize = 0; static const int kEntrySize = entrysize; + static const bool kNeedsHoleCheck = false; }; // WeakHashTable maps keys that are arbitrary heap objects to heap object // values. The table wraps the keys in weak cells and store values directly. // Thus it references keys weakly and values strongly. -class WeakHashTable - : public HashTable<WeakHashTable, WeakHashTableShape<2>, Handle<Object>> { - typedef HashTable<WeakHashTable, WeakHashTableShape<2>, Handle<Object>> - DerivedHashTable; +class WeakHashTable : public HashTable<WeakHashTable, WeakHashTableShape<2>> { + typedef HashTable<WeakHashTable, WeakHashTableShape<2>> DerivedHashTable; public: - DECLARE_CAST(WeakHashTable) + DECL_CAST(WeakHashTable) // Looks up the value associated with the given key. The hole value is // returned in case the key is not present. @@ -572,20 +609,234 @@ class WeakHashTable } }; -// OrderedHashTableIterator is an iterator that iterates over the keys and -// values of an OrderedHashTable. +// This is similar to the OrderedHashTable, except for the memory +// layout where we use byte instead of Smi. The max capacity of this +// is only 254, we transition to an OrderedHashTable beyond that +// limit. // -// The iterator has a reference to the underlying OrderedHashTable data, -// [table], as well as the current [index] the iterator is at. +// Each bucket and chain value is a byte long. The padding exists so +// that the DataTable entries start aligned. A bucket or chain value +// of 255 is used to denote an unknown entry. // -// When the OrderedHashTable is rehashed it adds a reference from the old table -// to the new table as well as storing enough data about the changes so that the -// iterator [index] can be adjusted accordingly. +// Memory layout: [ Header ] [ HashTable ] [ Chains ] [ Padding ] [ DataTable ] // -// When the [Next] result from the iterator is requested, the iterator checks if -// there is a newer table that it needs to transition to. -template <class Derived, class TableType> -class OrderedHashTableIterator : public JSObject { +// On a 64 bit machine with capacity = 4 and 2 entries, +// +// [ Header ] : +// [0 .. 7] : Number of elements +// [8 .. 15] : Number of deleted elements +// [16 .. 23] : Number of buckets +// +// [ HashTable ] : +// [24 .. 31] : First chain-link for bucket 1 +// [32 .. 40] : First chain-link for bucket 2 +// +// [ Chains ] : +// [40 .. 47] : Next chain link for entry 1 +// [48 .. 55] : Next chain link for entry 2 +// [56 .. 63] : Next chain link for entry 3 +// [64 .. 71] : Next chain link for entry 4 +// +// [ Padding ] : +// [72 .. 127] : Padding +// +// [ DataTable ] : +// [128 .. 128 + kEntrySize - 1] : Entry 1 +// [128 + kEntrySize .. 128 + kEntrySize + kEntrySize - 1] : Entry 2 +// +template <class Derived> +class SmallOrderedHashTable : public HeapObject { + public: + void Initialize(Isolate* isolate, int capacity); + + static Handle<Derived> Allocate(Isolate* isolate, int capacity, + PretenureFlag pretenure = NOT_TENURED); + + // Returns a true if the OrderedHashTable contains the key + bool HasKey(Isolate* isolate, Handle<Object> key); + + // Iterates only fields in the DataTable. + class BodyDescriptor; + + // No weak fields. + typedef BodyDescriptor BodyDescriptorWeak; + + // Returns an SmallOrderedHashTable (possibly |table|) with enough + // space to add at least one new element. + static Handle<Derived> Grow(Handle<Derived> table); + + static Handle<Derived> Rehash(Handle<Derived> table, int new_capacity); + + void SetDataEntry(int entry, int relative_index, Object* value); + + static int GetDataTableStartOffset(int capacity) { + int nof_buckets = capacity / kLoadFactor; + int nof_chain_entries = capacity; + + int padding_index = kBucketsStartOffset + nof_buckets + nof_chain_entries; + int padding_offset = padding_index * kBitsPerByte; + + return ((padding_offset + kPointerSize - 1) / kPointerSize) * kPointerSize; + } + + int GetDataTableStartOffset() const { + return GetDataTableStartOffset(Capacity()); + } + + static int Size(int capacity) { + int data_table_start = GetDataTableStartOffset(capacity); + int data_table_size = capacity * Derived::kEntrySize * kBitsPerPointer; + return data_table_start + data_table_size; + } + + int Size() const { return Size(Capacity()); } + + void SetFirstEntry(int bucket, byte value) { + set(kBucketsStartOffset + bucket, value); + } + + int GetFirstEntry(int bucket) const { + return get(kBucketsStartOffset + bucket); + } + + void SetNextEntry(int entry, int next_entry) { + set(GetChainTableOffset() + entry, next_entry); + } + + int GetNextEntry(int entry) const { + return get(GetChainTableOffset() + entry); + } + + Object* GetDataEntry(int entry, int relative_index) { + int entry_offset = GetDataEntryOffset(entry, relative_index); + return READ_FIELD(this, entry_offset); + } + + Object* KeyAt(int entry) const { + int 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 { + int bucket = HashToBucket(hash); + int entry = GetFirstEntry(bucket); + return entry; + } + + int GetChainTableOffset() const { + return kBucketsStartOffset + NumberOfBuckets(); + } + + void SetNumberOfBuckets(int num) { set(kNumberOfBucketsOffset, num); } + + void SetNumberOfElements(int num) { set(kNumberOfElementsOffset, num); } + + void SetNumberOfDeletedElements(int num) { + set(kNumberOfDeletedElementsOffset, num); + } + + int NumberOfElements() const { return get(kNumberOfElementsOffset); } + + int NumberOfDeletedElements() const { + return get(kNumberOfDeletedElementsOffset); + } + + int NumberOfBuckets() const { return get(kNumberOfBucketsOffset); } + + static const byte kNotFound = 0xFF; + static const int kMinCapacity = 4; + + // We use the value 255 to indicate kNotFound for chain and bucket + // values, which means that this value can't be used a valid + // index. + static const int kMaxCapacity = 254; + STATIC_ASSERT(kMaxCapacity < kNotFound); + + static const int kNumberOfElementsOffset = 0; + static const int kNumberOfDeletedElementsOffset = 1; + static const int kNumberOfBucketsOffset = 2; + static const int kBucketsStartOffset = 3; + + // The load factor is used to derive the number of buckets from + // capacity during Allocation. We also depend on this to calaculate + // the capacity from number of buckets after allocation. If we + // decide to change kLoadFactor to something other than 2, capacity + // should be stored as another field of this object. + static const int kLoadFactor = 2; + static const int kBitsPerPointer = kPointerSize * kBitsPerByte; + + // Our growth strategy involves doubling the capacity until we reach + // kMaxCapacity, but since the kMaxCapacity is always less than 256, + // we will never fully utilize this table. We special case for 256, + // by changing the new capacity to be kMaxCapacity in + // SmallOrderedHashTable::Grow. + static const int kGrowthHack = 256; + + DECL_VERIFIER(SmallOrderedHashTable) + + protected: + // This is used for accessing the non |DataTable| part of the + // structure. + byte get(int index) const { + return READ_BYTE_FIELD(this, kHeaderSize + (index * kOneByteSize)); + } + + void set(int index, byte value) { + WRITE_BYTE_FIELD(this, kHeaderSize + (index * kOneByteSize), value); + } + + int GetDataEntryOffset(int entry, int relative_index) const { + int datatable_start = GetDataTableStartOffset(); + int offset_in_datatable = entry * Derived::kEntrySize * kPointerSize; + int offset_in_entry = relative_index * kPointerSize; + return datatable_start + offset_in_datatable + offset_in_entry; + } + + // Returns the number elements that can fit into the allocated buffer. + int Capacity() const { return NumberOfBuckets() * kLoadFactor; } + + int UsedCapacity() const { + return NumberOfElements() + NumberOfDeletedElements(); + } +}; + +class SmallOrderedHashSet : public SmallOrderedHashTable<SmallOrderedHashSet> { + public: + DECL_CAST(SmallOrderedHashSet) + + DECL_PRINTER(SmallOrderedHashSet) + + static const int kKeyIndex = 0; + static const int kEntrySize = 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 Handle<SmallOrderedHashSet> Add(Handle<SmallOrderedHashSet> table, + Handle<Object> key); +}; + +class SmallOrderedHashMap : public SmallOrderedHashTable<SmallOrderedHashMap> { + public: + DECL_CAST(SmallOrderedHashMap) + + DECL_PRINTER(SmallOrderedHashMap) + + static const int kKeyIndex = 0; + static const int kValueIndex = 1; + static const int kEntrySize = 2; + + // 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 Handle<SmallOrderedHashMap> Add(Handle<SmallOrderedHashMap> table, + Handle<Object> key, + Handle<Object> value); +}; + +class JSCollectionIterator : public JSObject { public: // [table]: the backing hash table mapping keys to values. DECL_ACCESSORS(table, Object) @@ -593,31 +844,38 @@ class OrderedHashTableIterator : public JSObject { // [index]: The index into the data table. DECL_ACCESSORS(index, Object) - // [kind]: The kind of iteration this is. One of the [Kind] enum values. - DECL_ACCESSORS(kind, Object) - -#ifdef OBJECT_PRINT - void OrderedHashTableIteratorPrint(std::ostream& os); // NOLINT -#endif + // Dispatched behavior. + DECL_PRINTER(JSCollectionIterator) static const int kTableOffset = JSObject::kHeaderSize; static const int kIndexOffset = kTableOffset + kPointerSize; - static const int kKindOffset = kIndexOffset + kPointerSize; - static const int kSize = kKindOffset + kPointerSize; + static const int kSize = kIndexOffset + kPointerSize; - enum Kind { kKindKeys = 1, kKindValues = 2, kKindEntries = 3 }; + private: + DISALLOW_IMPLICIT_CONSTRUCTORS(JSCollectionIterator); +}; +// OrderedHashTableIterator is an iterator that iterates over the keys and +// values of an OrderedHashTable. +// +// The iterator has a reference to the underlying OrderedHashTable data, +// [table], as well as the current [index] the iterator is at. +// +// When the OrderedHashTable is rehashed it adds a reference from the old table +// to the new table as well as storing enough data about the changes so that the +// iterator [index] can be adjusted accordingly. +// +// When the [Next] result from the iterator is requested, the iterator checks if +// there is a newer table that it needs to transition to. +template <class Derived, class TableType> +class OrderedHashTableIterator : public JSCollectionIterator { + public: // Whether the iterator has more elements. This needs to be called before // calling |CurrentKey| and/or |CurrentValue|. bool HasMore(); // Move the index forward one. - void MoveNext() { set_index(Smi::FromInt(Smi::cast(index())->value() + 1)); } - - // Populates the array with the next key and value and then moves the iterator - // forward. - // This returns the |kind| or 0 if the iterator is already at the end. - Smi* Next(JSArray* value_array); + void MoveNext() { set_index(Smi::FromInt(Smi::ToInt(index()) + 1)); } // Returns the current key of the iterator. This should only be called when // |HasMore| returns true. @@ -635,14 +893,10 @@ class JSSetIterator : public OrderedHashTableIterator<JSSetIterator, OrderedHashSet> { public: // Dispatched behavior. - DECLARE_PRINTER(JSSetIterator) - DECLARE_VERIFIER(JSSetIterator) - - DECLARE_CAST(JSSetIterator) + DECL_PRINTER(JSSetIterator) + DECL_VERIFIER(JSSetIterator) - // Called by |Next| to populate the array. This allows the subclasses to - // populate the array differently. - inline void PopulateValueArray(FixedArray* array); + DECL_CAST(JSSetIterator) private: DISALLOW_IMPLICIT_CONSTRUCTORS(JSSetIterator); @@ -652,20 +906,16 @@ class JSMapIterator : public OrderedHashTableIterator<JSMapIterator, OrderedHashMap> { public: // Dispatched behavior. - DECLARE_PRINTER(JSMapIterator) - DECLARE_VERIFIER(JSMapIterator) + DECL_PRINTER(JSMapIterator) + DECL_VERIFIER(JSMapIterator) - DECLARE_CAST(JSMapIterator) + DECL_CAST(JSMapIterator) - // Called by |Next| to populate the array. This allows the subclasses to - // populate the array differently. - inline void PopulateValueArray(FixedArray* array); - - private: // Returns the current value of the iterator. This should only be called when // |HasMore| returns true. inline Object* CurrentValue(); + private: DISALLOW_IMPLICIT_CONSTRUCTORS(JSMapIterator); }; |