OLD | NEW |
1 // Copyright 2015 the V8 project authors. All rights reserved. | 1 // Copyright 2015 the V8 project authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #ifndef V8_OBJECTS_H_ | 5 #ifndef V8_OBJECTS_H_ |
6 #define V8_OBJECTS_H_ | 6 #define V8_OBJECTS_H_ |
7 | 7 |
8 #include <iosfwd> | 8 #include <iosfwd> |
9 #include <memory> | 9 #include <memory> |
10 | 10 |
(...skipping 3471 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3482 } | 3482 } |
3483 | 3483 |
3484 static const int kNumberOfElementsIndex = 0; | 3484 static const int kNumberOfElementsIndex = 0; |
3485 static const int kNumberOfDeletedElementsIndex = 1; | 3485 static const int kNumberOfDeletedElementsIndex = 1; |
3486 static const int kCapacityIndex = 2; | 3486 static const int kCapacityIndex = 2; |
3487 static const int kPrefixStartIndex = 3; | 3487 static const int kPrefixStartIndex = 3; |
3488 | 3488 |
3489 // Constant used for denoting a absent entry. | 3489 // Constant used for denoting a absent entry. |
3490 static const int kNotFound = -1; | 3490 static const int kNotFound = -1; |
3491 | 3491 |
| 3492 // Minimum capacity for newly created hash tables. |
| 3493 static const int kMinCapacity = 4; |
| 3494 |
3492 protected: | 3495 protected: |
3493 // Update the number of elements in the hash table. | 3496 // Update the number of elements in the hash table. |
3494 inline void SetNumberOfElements(int nof); | 3497 inline void SetNumberOfElements(int nof); |
3495 | 3498 |
3496 // Update the number of deleted elements in the hash table. | 3499 // Update the number of deleted elements in the hash table. |
3497 inline void SetNumberOfDeletedElements(int nod); | 3500 inline void SetNumberOfDeletedElements(int nod); |
3498 | 3501 |
3499 // Returns probe entry. | 3502 // Returns probe entry. |
3500 static uint32_t GetProbe(uint32_t hash, uint32_t number, uint32_t size) { | 3503 static uint32_t GetProbe(uint32_t hash, uint32_t number, uint32_t size) { |
3501 DCHECK(base::bits::IsPowerOfTwo32(size)); | 3504 DCHECK(base::bits::IsPowerOfTwo32(size)); |
(...skipping 57 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3559 | 3562 |
3560 // Returns the key at entry. | 3563 // Returns the key at entry. |
3561 Object* KeyAt(int entry) { return get(EntryToIndex(entry) + kEntryKeyIndex); } | 3564 Object* KeyAt(int entry) { return get(EntryToIndex(entry) + kEntryKeyIndex); } |
3562 | 3565 |
3563 static const int kElementsStartIndex = kPrefixStartIndex + Shape::kPrefixSize; | 3566 static const int kElementsStartIndex = kPrefixStartIndex + Shape::kPrefixSize; |
3564 static const int kEntrySize = Shape::kEntrySize; | 3567 static const int kEntrySize = Shape::kEntrySize; |
3565 STATIC_ASSERT(kEntrySize > 0); | 3568 STATIC_ASSERT(kEntrySize > 0); |
3566 static const int kEntryKeyIndex = 0; | 3569 static const int kEntryKeyIndex = 0; |
3567 static const int kElementsStartOffset = | 3570 static const int kElementsStartOffset = |
3568 kHeaderSize + kElementsStartIndex * kPointerSize; | 3571 kHeaderSize + kElementsStartIndex * kPointerSize; |
3569 static const int kCapacityOffset = | 3572 // Maximal capacity of HashTable. Based on maximal length of underlying |
3570 kHeaderSize + kCapacityIndex * kPointerSize; | 3573 // FixedArray. Staying below kMaxCapacity also ensures that EntryToIndex |
| 3574 // cannot overflow. |
| 3575 static const int kMaxCapacity = |
| 3576 (FixedArray::kMaxLength - kElementsStartIndex) / kEntrySize; |
3571 | 3577 |
3572 // Returns the index for an entry (of the key) | 3578 // Returns the index for an entry (of the key) |
3573 static inline int EntryToIndex(int entry) { | 3579 static inline int EntryToIndex(int entry) { |
3574 return (entry * kEntrySize) + kElementsStartIndex; | 3580 return (entry * kEntrySize) + kElementsStartIndex; |
3575 } | 3581 } |
3576 | 3582 |
3577 protected: | 3583 protected: |
3578 friend class ObjectHashTable; | 3584 friend class ObjectHashTable; |
3579 | 3585 |
3580 // Find the entry at which to insert element with the given key that | 3586 // Find the entry at which to insert element with the given key that |
(...skipping 16 matching lines...) Expand all Loading... |
3597 // Sets the capacity of the hash table. | 3603 // Sets the capacity of the hash table. |
3598 void SetCapacity(int capacity) { | 3604 void SetCapacity(int capacity) { |
3599 // To scale a computed hash code to fit within the hash table, we | 3605 // To scale a computed hash code to fit within the hash table, we |
3600 // use bit-wise AND with a mask, so the capacity must be positive | 3606 // use bit-wise AND with a mask, so the capacity must be positive |
3601 // and non-zero. | 3607 // and non-zero. |
3602 DCHECK(capacity > 0); | 3608 DCHECK(capacity > 0); |
3603 DCHECK(capacity <= kMaxCapacity); | 3609 DCHECK(capacity <= kMaxCapacity); |
3604 set(kCapacityIndex, Smi::FromInt(capacity)); | 3610 set(kCapacityIndex, Smi::FromInt(capacity)); |
3605 } | 3611 } |
3606 | 3612 |
3607 // Maximal capacity of HashTable. Based on maximal length of underlying | |
3608 // FixedArray. Staying below kMaxCapacity also ensures that EntryToIndex | |
3609 // cannot overflow. | |
3610 static const int kMaxCapacity = | |
3611 (FixedArray::kMaxLength - kElementsStartOffset) / kEntrySize; | |
3612 | |
3613 private: | 3613 private: |
3614 // Returns _expected_ if one of entries given by the first _probe_ probes is | 3614 // Returns _expected_ if one of entries given by the first _probe_ probes is |
3615 // equal to _expected_. Otherwise, returns the entry given by the probe | 3615 // equal to _expected_. Otherwise, returns the entry given by the probe |
3616 // number _probe_. | 3616 // number _probe_. |
3617 uint32_t EntryForProbe(Key key, Object* k, int probe, uint32_t expected); | 3617 uint32_t EntryForProbe(Key key, Object* k, int probe, uint32_t expected); |
3618 | 3618 |
3619 void Swap(uint32_t entry1, uint32_t entry2, WriteBarrierMode mode); | 3619 void Swap(uint32_t entry1, uint32_t entry2, WriteBarrierMode mode); |
3620 | 3620 |
3621 // Rehashes this hash-table into the new table. | 3621 // Rehashes this hash-table into the new table. |
3622 void Rehash(Handle<Derived> new_table, Key key); | 3622 void Rehash(Handle<Derived> new_table, Key key); |
(...skipping 208 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3831 MUST_USE_RESULT static Handle<Derived> Add(Handle<Derived> dictionary, | 3831 MUST_USE_RESULT static Handle<Derived> Add(Handle<Derived> dictionary, |
3832 Key key, Handle<Object> value, | 3832 Key key, Handle<Object> value, |
3833 PropertyDetails details, | 3833 PropertyDetails details, |
3834 int* entry_out = nullptr); | 3834 int* entry_out = nullptr); |
3835 | 3835 |
3836 // Returns iteration indices array for the |dictionary|. | 3836 // Returns iteration indices array for the |dictionary|. |
3837 // Values are direct indices in the |HashTable| array. | 3837 // Values are direct indices in the |HashTable| array. |
3838 static Handle<FixedArray> BuildIterationIndicesArray( | 3838 static Handle<FixedArray> BuildIterationIndicesArray( |
3839 Handle<Derived> dictionary); | 3839 Handle<Derived> dictionary); |
3840 | 3840 |
| 3841 static const int kMaxNumberKeyIndex = DerivedHashTable::kPrefixStartIndex; |
| 3842 static const int kNextEnumerationIndexIndex = kMaxNumberKeyIndex + 1; |
| 3843 |
3841 protected: | 3844 protected: |
3842 // Generic at put operation. | 3845 // Generic at put operation. |
3843 MUST_USE_RESULT static Handle<Derived> AtPut( | 3846 MUST_USE_RESULT static Handle<Derived> AtPut( |
3844 Handle<Derived> dictionary, | 3847 Handle<Derived> dictionary, |
3845 Key key, | 3848 Key key, |
3846 Handle<Object> value); | 3849 Handle<Object> value); |
3847 | |
3848 // Add entry to dictionary. Returns entry value. | 3850 // Add entry to dictionary. Returns entry value. |
3849 static int AddEntry(Handle<Derived> dictionary, Key key, Handle<Object> value, | 3851 static int AddEntry(Handle<Derived> dictionary, Key key, Handle<Object> value, |
3850 PropertyDetails details, uint32_t hash); | 3852 PropertyDetails details, uint32_t hash); |
3851 | |
3852 // Generate new enumeration indices to avoid enumeration index overflow. | 3853 // Generate new enumeration indices to avoid enumeration index overflow. |
3853 // Returns iteration indices array for the |dictionary|. | 3854 // Returns iteration indices array for the |dictionary|. |
3854 static Handle<FixedArray> GenerateNewEnumerationIndices( | 3855 static Handle<FixedArray> GenerateNewEnumerationIndices( |
3855 Handle<Derived> dictionary); | 3856 Handle<Derived> dictionary); |
3856 static const int kMaxNumberKeyIndex = DerivedHashTable::kPrefixStartIndex; | |
3857 static const int kNextEnumerationIndexIndex = kMaxNumberKeyIndex + 1; | |
3858 }; | 3857 }; |
3859 | 3858 |
3860 | 3859 |
3861 template <typename Derived, typename Shape> | 3860 template <typename Derived, typename Shape> |
3862 class NameDictionaryBase : public Dictionary<Derived, Shape, Handle<Name> > { | 3861 class NameDictionaryBase : public Dictionary<Derived, Shape, Handle<Name> > { |
3863 typedef Dictionary<Derived, Shape, Handle<Name> > DerivedDictionary; | 3862 typedef Dictionary<Derived, Shape, Handle<Name> > DerivedDictionary; |
3864 | 3863 |
3865 public: | 3864 public: |
3866 // Find entry for key, otherwise return kNotFound. Optimized version of | 3865 // Find entry for key, otherwise return kNotFound. Optimized version of |
3867 // HashTable::FindEntry. | 3866 // HashTable::FindEntry. |
(...skipping 51 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3919 DerivedDictionary; | 3918 DerivedDictionary; |
3920 | 3919 |
3921 public: | 3920 public: |
3922 DECLARE_CAST(NameDictionary) | 3921 DECLARE_CAST(NameDictionary) |
3923 | 3922 |
3924 inline static Handle<FixedArray> DoGenerateNewEnumerationIndices( | 3923 inline static Handle<FixedArray> DoGenerateNewEnumerationIndices( |
3925 Handle<NameDictionary> dictionary); | 3924 Handle<NameDictionary> dictionary); |
3926 | 3925 |
3927 static const int kEntryValueIndex = 1; | 3926 static const int kEntryValueIndex = 1; |
3928 static const int kEntryDetailsIndex = 2; | 3927 static const int kEntryDetailsIndex = 2; |
| 3928 static const int kInitialCapacity = 2; |
3929 }; | 3929 }; |
3930 | 3930 |
3931 | 3931 |
3932 class GlobalDictionaryShape : public NameDictionaryShape { | 3932 class GlobalDictionaryShape : public NameDictionaryShape { |
3933 public: | 3933 public: |
3934 static const int kEntrySize = 2; // Overrides NameDictionaryShape::kEntrySize | 3934 static const int kEntrySize = 2; // Overrides NameDictionaryShape::kEntrySize |
3935 | 3935 |
3936 template <typename Dictionary> | 3936 template <typename Dictionary> |
3937 static inline PropertyDetails DetailsAt(Dictionary* dict, int entry); | 3937 static inline PropertyDetails DetailsAt(Dictionary* dict, int entry); |
3938 | 3938 |
(...skipping 7804 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
11743 } | 11743 } |
11744 return value; | 11744 return value; |
11745 } | 11745 } |
11746 }; | 11746 }; |
11747 | 11747 |
11748 | 11748 |
11749 } // NOLINT, false-positive due to second-order macros. | 11749 } // NOLINT, false-positive due to second-order macros. |
11750 } // NOLINT, false-positive due to second-order macros. | 11750 } // NOLINT, false-positive due to second-order macros. |
11751 | 11751 |
11752 #endif // V8_OBJECTS_H_ | 11752 #endif // V8_OBJECTS_H_ |
OLD | NEW |