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 3464 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
3475 // as keys and can be used to indicate missing or deleted elements. | 3475 // as keys and can be used to indicate missing or deleted elements. |
3476 inline bool IsKey(Object* k); | 3476 inline bool IsKey(Object* k); |
3477 inline bool IsKey(Isolate* isolate, Object* k); | 3477 inline bool IsKey(Isolate* isolate, Object* k); |
3478 | 3478 |
3479 // Compute the probe offset (quadratic probing). | 3479 // Compute the probe offset (quadratic probing). |
3480 INLINE(static uint32_t GetProbeOffset(uint32_t n)) { | 3480 INLINE(static uint32_t GetProbeOffset(uint32_t n)) { |
3481 return (n + n * n) >> 1; | 3481 return (n + n * n) >> 1; |
3482 } | 3482 } |
3483 | 3483 |
3484 static const int kNumberOfElementsIndex = 0; | 3484 static const int kNumberOfElementsIndex = 0; |
3485 static const int kNumberOfElementsOffset = kHeaderSize; | |
Igor Sheludko
2016/10/21 07:48:27
I think it is better to use OffsetOfElementAt() to
Camillo Bruni
2016/10/21 13:37:15
done.
| |
3485 static const int kNumberOfDeletedElementsIndex = 1; | 3486 static const int kNumberOfDeletedElementsIndex = 1; |
3487 static const int kNumberOfDeletedElementsOffset = | |
3488 kNumberOfElementsOffset + kPointerSize; | |
3486 static const int kCapacityIndex = 2; | 3489 static const int kCapacityIndex = 2; |
3490 static const int kCapacityOffset = | |
3491 kNumberOfDeletedElementsOffset + kPointerSize; | |
3487 static const int kPrefixStartIndex = 3; | 3492 static const int kPrefixStartIndex = 3; |
3493 static const int kPrefixStartOffset = kCapacityOffset + kPointerSize; | |
3488 | 3494 |
3489 // Constant used for denoting a absent entry. | 3495 // Constant used for denoting a absent entry. |
3490 static const int kNotFound = -1; | 3496 static const int kNotFound = -1; |
3491 | 3497 |
3492 protected: | 3498 protected: |
3493 // Update the number of elements in the hash table. | 3499 // Update the number of elements in the hash table. |
3494 inline void SetNumberOfElements(int nof); | 3500 inline void SetNumberOfElements(int nof); |
3495 | 3501 |
3496 // Update the number of deleted elements in the hash table. | 3502 // Update the number of deleted elements in the hash table. |
3497 inline void SetNumberOfDeletedElements(int nod); | 3503 inline void SetNumberOfDeletedElements(int nod); |
(...skipping 61 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
3559 | 3565 |
3560 // Returns the key at entry. | 3566 // Returns the key at entry. |
3561 Object* KeyAt(int entry) { return get(EntryToIndex(entry) + kEntryKeyIndex); } | 3567 Object* KeyAt(int entry) { return get(EntryToIndex(entry) + kEntryKeyIndex); } |
3562 | 3568 |
3563 static const int kElementsStartIndex = kPrefixStartIndex + Shape::kPrefixSize; | 3569 static const int kElementsStartIndex = kPrefixStartIndex + Shape::kPrefixSize; |
3564 static const int kEntrySize = Shape::kEntrySize; | 3570 static const int kEntrySize = Shape::kEntrySize; |
3565 STATIC_ASSERT(kEntrySize > 0); | 3571 STATIC_ASSERT(kEntrySize > 0); |
3566 static const int kEntryKeyIndex = 0; | 3572 static const int kEntryKeyIndex = 0; |
3567 static const int kElementsStartOffset = | 3573 static const int kElementsStartOffset = |
3568 kHeaderSize + kElementsStartIndex * kPointerSize; | 3574 kHeaderSize + kElementsStartIndex * kPointerSize; |
3569 static const int kCapacityOffset = | 3575 // Maximal capacity of HashTable. Based on maximal length of underlying |
3570 kHeaderSize + kCapacityIndex * kPointerSize; | 3576 // FixedArray. Staying below kMaxCapacity also ensures that EntryToIndex |
3577 // cannot overflow. | |
3578 static const int kMaxCapacity = | |
3579 (FixedArray::kMaxLength - kElementsStartIndex) / kEntrySize; | |
3571 | 3580 |
3572 // Returns the index for an entry (of the key) | 3581 // Returns the index for an entry (of the key) |
3573 static inline int EntryToIndex(int entry) { | 3582 static inline int EntryToIndex(int entry) { |
3574 return (entry * kEntrySize) + kElementsStartIndex; | 3583 return (entry * kEntrySize) + kElementsStartIndex; |
3575 } | 3584 } |
3576 | 3585 |
3577 protected: | 3586 protected: |
3578 friend class ObjectHashTable; | 3587 friend class ObjectHashTable; |
3579 | 3588 |
3580 // Find the entry at which to insert element with the given key that | 3589 // 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. | 3606 // Sets the capacity of the hash table. |
3598 void SetCapacity(int capacity) { | 3607 void SetCapacity(int capacity) { |
3599 // To scale a computed hash code to fit within the hash table, we | 3608 // 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 | 3609 // use bit-wise AND with a mask, so the capacity must be positive |
3601 // and non-zero. | 3610 // and non-zero. |
3602 DCHECK(capacity > 0); | 3611 DCHECK(capacity > 0); |
3603 DCHECK(capacity <= kMaxCapacity); | 3612 DCHECK(capacity <= kMaxCapacity); |
3604 set(kCapacityIndex, Smi::FromInt(capacity)); | 3613 set(kCapacityIndex, Smi::FromInt(capacity)); |
3605 } | 3614 } |
3606 | 3615 |
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: | 3616 private: |
3614 // Returns _expected_ if one of entries given by the first _probe_ probes is | 3617 // 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 | 3618 // equal to _expected_. Otherwise, returns the entry given by the probe |
3616 // number _probe_. | 3619 // number _probe_. |
3617 uint32_t EntryForProbe(Key key, Object* k, int probe, uint32_t expected); | 3620 uint32_t EntryForProbe(Key key, Object* k, int probe, uint32_t expected); |
3618 | 3621 |
3619 void Swap(uint32_t entry1, uint32_t entry2, WriteBarrierMode mode); | 3622 void Swap(uint32_t entry1, uint32_t entry2, WriteBarrierMode mode); |
3620 | 3623 |
3621 // Rehashes this hash-table into the new table. | 3624 // Rehashes this hash-table into the new table. |
3622 void Rehash(Handle<Derived> new_table, Key key); | 3625 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, | 3834 MUST_USE_RESULT static Handle<Derived> Add(Handle<Derived> dictionary, |
3832 Key key, Handle<Object> value, | 3835 Key key, Handle<Object> value, |
3833 PropertyDetails details, | 3836 PropertyDetails details, |
3834 int* entry_out = nullptr); | 3837 int* entry_out = nullptr); |
3835 | 3838 |
3836 // Returns iteration indices array for the |dictionary|. | 3839 // Returns iteration indices array for the |dictionary|. |
3837 // Values are direct indices in the |HashTable| array. | 3840 // Values are direct indices in the |HashTable| array. |
3838 static Handle<FixedArray> BuildIterationIndicesArray( | 3841 static Handle<FixedArray> BuildIterationIndicesArray( |
3839 Handle<Derived> dictionary); | 3842 Handle<Derived> dictionary); |
3840 | 3843 |
3844 // Generate new enumeration indices to avoid enumeration index overflow. | |
3845 // Returns iteration indices array for the |dictionary|. | |
3846 static Handle<FixedArray> GenerateNewEnumerationIndices( | |
3847 Handle<Derived> dictionary); | |
3848 static const int kMaxNumberKeyIndex = DerivedHashTable::kPrefixStartIndex; | |
3849 static const int kMaxNumberKeyOffset = DerivedHashTable::kPrefixStartOffset; | |
Igor Sheludko
2016/10/21 07:48:27
Same here.
Camillo Bruni
2016/10/21 13:37:15
done.
| |
3850 static const int kNextEnumerationIndexIndex = kMaxNumberKeyIndex + 1; | |
3851 static const int kNextEnumerationIndexOffset = | |
3852 kMaxNumberKeyOffset + kPointerSize; | |
3853 | |
3841 protected: | 3854 protected: |
3842 // Generic at put operation. | 3855 // Generic at put operation. |
3843 MUST_USE_RESULT static Handle<Derived> AtPut( | 3856 MUST_USE_RESULT static Handle<Derived> AtPut( |
3844 Handle<Derived> dictionary, | 3857 Handle<Derived> dictionary, |
3845 Key key, | 3858 Key key, |
3846 Handle<Object> value); | 3859 Handle<Object> value); |
3847 | 3860 |
3848 // Add entry to dictionary. Returns entry value. | 3861 // Add entry to dictionary. Returns entry value. |
3849 static int AddEntry(Handle<Derived> dictionary, Key key, Handle<Object> value, | 3862 static int AddEntry(Handle<Derived> dictionary, Key key, Handle<Object> value, |
3850 PropertyDetails details, uint32_t hash); | 3863 PropertyDetails details, uint32_t hash); |
3851 | |
3852 // Generate new enumeration indices to avoid enumeration index overflow. | |
3853 // Returns iteration indices array for the |dictionary|. | |
3854 static Handle<FixedArray> GenerateNewEnumerationIndices( | |
3855 Handle<Derived> dictionary); | |
3856 static const int kMaxNumberKeyIndex = DerivedHashTable::kPrefixStartIndex; | |
3857 static const int kNextEnumerationIndexIndex = kMaxNumberKeyIndex + 1; | |
3858 }; | 3864 }; |
3859 | 3865 |
3860 | 3866 |
3861 template <typename Derived, typename Shape> | 3867 template <typename Derived, typename Shape> |
3862 class NameDictionaryBase : public Dictionary<Derived, Shape, Handle<Name> > { | 3868 class NameDictionaryBase : public Dictionary<Derived, Shape, Handle<Name> > { |
3863 typedef Dictionary<Derived, Shape, Handle<Name> > DerivedDictionary; | 3869 typedef Dictionary<Derived, Shape, Handle<Name> > DerivedDictionary; |
3864 | 3870 |
3865 public: | 3871 public: |
3866 // Find entry for key, otherwise return kNotFound. Optimized version of | 3872 // Find entry for key, otherwise return kNotFound. Optimized version of |
3867 // HashTable::FindEntry. | 3873 // HashTable::FindEntry. |
(...skipping 51 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
3919 DerivedDictionary; | 3925 DerivedDictionary; |
3920 | 3926 |
3921 public: | 3927 public: |
3922 DECLARE_CAST(NameDictionary) | 3928 DECLARE_CAST(NameDictionary) |
3923 | 3929 |
3924 inline static Handle<FixedArray> DoGenerateNewEnumerationIndices( | 3930 inline static Handle<FixedArray> DoGenerateNewEnumerationIndices( |
3925 Handle<NameDictionary> dictionary); | 3931 Handle<NameDictionary> dictionary); |
3926 | 3932 |
3927 static const int kEntryValueIndex = 1; | 3933 static const int kEntryValueIndex = 1; |
3928 static const int kEntryDetailsIndex = 2; | 3934 static const int kEntryDetailsIndex = 2; |
3935 static const int kInitialCapacity = 2; | |
3929 }; | 3936 }; |
3930 | 3937 |
3931 | 3938 |
3932 class GlobalDictionaryShape : public NameDictionaryShape { | 3939 class GlobalDictionaryShape : public NameDictionaryShape { |
3933 public: | 3940 public: |
3934 static const int kEntrySize = 2; // Overrides NameDictionaryShape::kEntrySize | 3941 static const int kEntrySize = 2; // Overrides NameDictionaryShape::kEntrySize |
3935 | 3942 |
3936 template <typename Dictionary> | 3943 template <typename Dictionary> |
3937 static inline PropertyDetails DetailsAt(Dictionary* dict, int entry); | 3944 static inline PropertyDetails DetailsAt(Dictionary* dict, int entry); |
3938 | 3945 |
(...skipping 7791 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
11730 } | 11737 } |
11731 return value; | 11738 return value; |
11732 } | 11739 } |
11733 }; | 11740 }; |
11734 | 11741 |
11735 | 11742 |
11736 } // NOLINT, false-positive due to second-order macros. | 11743 } // NOLINT, false-positive due to second-order macros. |
11737 } // NOLINT, false-positive due to second-order macros. | 11744 } // NOLINT, false-positive due to second-order macros. |
11738 | 11745 |
11739 #endif // V8_OBJECTS_H_ | 11746 #endif // V8_OBJECTS_H_ |
OLD | NEW |