| OLD | NEW |
| 1 // Copyright 2017 the V8 project authors. All rights reserved. | 1 // Copyright 2017 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_HASH_TABLE_H_ | 5 #ifndef V8_OBJECTS_HASH_TABLE_H_ |
| 6 #define V8_OBJECTS_HASH_TABLE_H_ | 6 #define V8_OBJECTS_HASH_TABLE_H_ |
| 7 | 7 |
| 8 #include "src/objects.h" | 8 #include "src/objects.h" |
| 9 | 9 |
| 10 #include "src/base/compiler-specific.h" | 10 #include "src/base/compiler-specific.h" |
| (...skipping 122 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 133 public: | 133 public: |
| 134 typedef Shape ShapeT; | 134 typedef Shape ShapeT; |
| 135 typedef typename Shape::Key Key; | 135 typedef typename Shape::Key Key; |
| 136 | 136 |
| 137 // Returns a new HashTable object. | 137 // Returns a new HashTable object. |
| 138 MUST_USE_RESULT static Handle<Derived> New( | 138 MUST_USE_RESULT static Handle<Derived> New( |
| 139 Isolate* isolate, int at_least_space_for, | 139 Isolate* isolate, int at_least_space_for, |
| 140 PretenureFlag pretenure = NOT_TENURED, | 140 PretenureFlag pretenure = NOT_TENURED, |
| 141 MinimumCapacity capacity_option = USE_DEFAULT_MINIMUM_CAPACITY); | 141 MinimumCapacity capacity_option = USE_DEFAULT_MINIMUM_CAPACITY); |
| 142 | 142 |
| 143 DECLARE_CAST(HashTable) | 143 DECL_CAST(HashTable) |
| 144 | 144 |
| 145 // Garbage collection support. | 145 // Garbage collection support. |
| 146 void IteratePrefix(ObjectVisitor* visitor); | 146 void IteratePrefix(ObjectVisitor* visitor); |
| 147 void IterateElements(ObjectVisitor* visitor); | 147 void IterateElements(ObjectVisitor* visitor); |
| 148 | 148 |
| 149 // Find entry for key otherwise return kNotFound. | 149 // Find entry for key otherwise return kNotFound. |
| 150 inline int FindEntry(Key key); | 150 inline int FindEntry(Key key); |
| 151 inline int FindEntry(Isolate* isolate, Key key, int32_t hash); | 151 inline int FindEntry(Isolate* isolate, Key key, int32_t hash); |
| 152 int FindEntry(Isolate* isolate, Key key); | 152 int FindEntry(Isolate* isolate, Key key); |
| 153 | 153 |
| (...skipping 121 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 275 static const bool kNeedsHoleCheck = false; | 275 static const bool kNeedsHoleCheck = false; |
| 276 }; | 276 }; |
| 277 | 277 |
| 278 // ObjectHashTable maps keys that are arbitrary objects to object values by | 278 // ObjectHashTable maps keys that are arbitrary objects to object values by |
| 279 // using the identity hash of the key for hashing purposes. | 279 // using the identity hash of the key for hashing purposes. |
| 280 class ObjectHashTable | 280 class ObjectHashTable |
| 281 : public HashTable<ObjectHashTable, ObjectHashTableShape> { | 281 : public HashTable<ObjectHashTable, ObjectHashTableShape> { |
| 282 typedef HashTable<ObjectHashTable, ObjectHashTableShape> DerivedHashTable; | 282 typedef HashTable<ObjectHashTable, ObjectHashTableShape> DerivedHashTable; |
| 283 | 283 |
| 284 public: | 284 public: |
| 285 DECLARE_CAST(ObjectHashTable) | 285 DECL_CAST(ObjectHashTable) |
| 286 | 286 |
| 287 // Attempt to shrink hash table after removal of key. | 287 // Attempt to shrink hash table after removal of key. |
| 288 MUST_USE_RESULT static inline Handle<ObjectHashTable> Shrink( | 288 MUST_USE_RESULT static inline Handle<ObjectHashTable> Shrink( |
| 289 Handle<ObjectHashTable> table); | 289 Handle<ObjectHashTable> table); |
| 290 | 290 |
| 291 // Looks up the value associated with the given key. The hole value is | 291 // Looks up the value associated with the given key. The hole value is |
| 292 // returned in case the key is not present. | 292 // returned in case the key is not present. |
| 293 Object* Lookup(Handle<Object> key); | 293 Object* Lookup(Handle<Object> key); |
| 294 Object* Lookup(Handle<Object> key, int32_t hash); | 294 Object* Lookup(Handle<Object> key, int32_t hash); |
| 295 Object* Lookup(Isolate* isolate, Handle<Object> key, int32_t hash); | 295 Object* Lookup(Isolate* isolate, Handle<Object> key, int32_t hash); |
| (...skipping 34 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 330 }; | 330 }; |
| 331 | 331 |
| 332 class ObjectHashSet : public HashTable<ObjectHashSet, ObjectHashSetShape> { | 332 class ObjectHashSet : public HashTable<ObjectHashSet, ObjectHashSetShape> { |
| 333 public: | 333 public: |
| 334 static Handle<ObjectHashSet> Add(Handle<ObjectHashSet> set, | 334 static Handle<ObjectHashSet> Add(Handle<ObjectHashSet> set, |
| 335 Handle<Object> key); | 335 Handle<Object> key); |
| 336 | 336 |
| 337 inline bool Has(Isolate* isolate, Handle<Object> key, int32_t hash); | 337 inline bool Has(Isolate* isolate, Handle<Object> key, int32_t hash); |
| 338 inline bool Has(Isolate* isolate, Handle<Object> key); | 338 inline bool Has(Isolate* isolate, Handle<Object> key); |
| 339 | 339 |
| 340 DECLARE_CAST(ObjectHashSet) | 340 DECL_CAST(ObjectHashSet) |
| 341 }; | 341 }; |
| 342 | 342 |
| 343 // OrderedHashTable is a HashTable with Object keys that preserves | 343 // OrderedHashTable is a HashTable with Object keys that preserves |
| 344 // insertion order. There are Map and Set interfaces (OrderedHashMap | 344 // insertion order. There are Map and Set interfaces (OrderedHashMap |
| 345 // and OrderedHashTable, below). It is meant to be used by JSMap/JSSet. | 345 // and OrderedHashTable, below). It is meant to be used by JSMap/JSSet. |
| 346 // | 346 // |
| 347 // Only Object* keys are supported, with Object::SameValueZero() used as the | 347 // Only Object* keys are supported, with Object::SameValueZero() used as the |
| 348 // equality operator and Object::GetHash() for the hash function. | 348 // equality operator and Object::GetHash() for the hash function. |
| 349 // | 349 // |
| 350 // Based on the "Deterministic Hash Table" as described by Jason Orendorff at | 350 // Based on the "Deterministic Hash Table" as described by Jason Orendorff at |
| (...skipping 185 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 536 | 536 |
| 537 void SetRemovedIndexAt(int index, int removed_index) { | 537 void SetRemovedIndexAt(int index, int removed_index) { |
| 538 return set(kRemovedHolesIndex + index, Smi::FromInt(removed_index)); | 538 return set(kRemovedHolesIndex + index, Smi::FromInt(removed_index)); |
| 539 } | 539 } |
| 540 | 540 |
| 541 static const int kRemovedHolesIndex = kHashTableStartIndex; | 541 static const int kRemovedHolesIndex = kHashTableStartIndex; |
| 542 }; | 542 }; |
| 543 | 543 |
| 544 class OrderedHashSet : public OrderedHashTable<OrderedHashSet, 1> { | 544 class OrderedHashSet : public OrderedHashTable<OrderedHashSet, 1> { |
| 545 public: | 545 public: |
| 546 DECLARE_CAST(OrderedHashSet) | 546 DECL_CAST(OrderedHashSet) |
| 547 | 547 |
| 548 static Handle<OrderedHashSet> Add(Handle<OrderedHashSet> table, | 548 static Handle<OrderedHashSet> Add(Handle<OrderedHashSet> table, |
| 549 Handle<Object> value); | 549 Handle<Object> value); |
| 550 static Handle<FixedArray> ConvertToKeysArray(Handle<OrderedHashSet> table, | 550 static Handle<FixedArray> ConvertToKeysArray(Handle<OrderedHashSet> table, |
| 551 GetKeysConversion convert); | 551 GetKeysConversion convert); |
| 552 }; | 552 }; |
| 553 | 553 |
| 554 class OrderedHashMap : public OrderedHashTable<OrderedHashMap, 2> { | 554 class OrderedHashMap : public OrderedHashTable<OrderedHashMap, 2> { |
| 555 public: | 555 public: |
| 556 DECLARE_CAST(OrderedHashMap) | 556 DECL_CAST(OrderedHashMap) |
| 557 | 557 |
| 558 // Returns a value if the OrderedHashMap contains the key, otherwise | 558 // Returns a value if the OrderedHashMap contains the key, otherwise |
| 559 // returns undefined. | 559 // returns undefined. |
| 560 static Object* Get(Isolate* isolate, OrderedHashMap* table, Object* key); | 560 static Object* Get(Isolate* isolate, OrderedHashMap* table, Object* key); |
| 561 static Handle<OrderedHashMap> Add(Handle<OrderedHashMap> table, | 561 static Handle<OrderedHashMap> Add(Handle<OrderedHashMap> table, |
| 562 Handle<Object> key, Handle<Object> value); | 562 Handle<Object> key, Handle<Object> value); |
| 563 Object* ValueAt(int entry); | 563 Object* ValueAt(int entry); |
| 564 | 564 |
| 565 static const int kValueOffset = 1; | 565 static const int kValueOffset = 1; |
| 566 }; | 566 }; |
| (...skipping 10 matching lines...) Expand all Loading... |
| 577 static const bool kNeedsHoleCheck = false; | 577 static const bool kNeedsHoleCheck = false; |
| 578 }; | 578 }; |
| 579 | 579 |
| 580 // WeakHashTable maps keys that are arbitrary heap objects to heap object | 580 // WeakHashTable maps keys that are arbitrary heap objects to heap object |
| 581 // values. The table wraps the keys in weak cells and store values directly. | 581 // values. The table wraps the keys in weak cells and store values directly. |
| 582 // Thus it references keys weakly and values strongly. | 582 // Thus it references keys weakly and values strongly. |
| 583 class WeakHashTable : public HashTable<WeakHashTable, WeakHashTableShape<2>> { | 583 class WeakHashTable : public HashTable<WeakHashTable, WeakHashTableShape<2>> { |
| 584 typedef HashTable<WeakHashTable, WeakHashTableShape<2>> DerivedHashTable; | 584 typedef HashTable<WeakHashTable, WeakHashTableShape<2>> DerivedHashTable; |
| 585 | 585 |
| 586 public: | 586 public: |
| 587 DECLARE_CAST(WeakHashTable) | 587 DECL_CAST(WeakHashTable) |
| 588 | 588 |
| 589 // Looks up the value associated with the given key. The hole value is | 589 // Looks up the value associated with the given key. The hole value is |
| 590 // returned in case the key is not present. | 590 // returned in case the key is not present. |
| 591 Object* Lookup(Handle<HeapObject> key); | 591 Object* Lookup(Handle<HeapObject> key); |
| 592 | 592 |
| 593 // Adds (or overwrites) the value associated with the given key. Mapping a | 593 // Adds (or overwrites) the value associated with the given key. Mapping a |
| 594 // key to the hole value causes removal of the whole entry. | 594 // key to the hole value causes removal of the whole entry. |
| 595 MUST_USE_RESULT static Handle<WeakHashTable> Put(Handle<WeakHashTable> table, | 595 MUST_USE_RESULT static Handle<WeakHashTable> Put(Handle<WeakHashTable> table, |
| 596 Handle<HeapObject> key, | 596 Handle<HeapObject> key, |
| 597 Handle<HeapObject> value); | 597 Handle<HeapObject> value); |
| (...skipping 159 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 757 static const int kLoadFactor = 2; | 757 static const int kLoadFactor = 2; |
| 758 static const int kBitsPerPointer = kPointerSize * kBitsPerByte; | 758 static const int kBitsPerPointer = kPointerSize * kBitsPerByte; |
| 759 | 759 |
| 760 // Our growth strategy involves doubling the capacity until we reach | 760 // Our growth strategy involves doubling the capacity until we reach |
| 761 // kMaxCapacity, but since the kMaxCapacity is always less than 256, | 761 // kMaxCapacity, but since the kMaxCapacity is always less than 256, |
| 762 // we will never fully utilize this table. We special case for 256, | 762 // we will never fully utilize this table. We special case for 256, |
| 763 // by changing the new capacity to be kMaxCapacity in | 763 // by changing the new capacity to be kMaxCapacity in |
| 764 // SmallOrderedHashTable::Grow. | 764 // SmallOrderedHashTable::Grow. |
| 765 static const int kGrowthHack = 256; | 765 static const int kGrowthHack = 256; |
| 766 | 766 |
| 767 DECLARE_VERIFIER(SmallOrderedHashTable) | 767 DECL_VERIFIER(SmallOrderedHashTable) |
| 768 | 768 |
| 769 protected: | 769 protected: |
| 770 // This is used for accessing the non |DataTable| part of the | 770 // This is used for accessing the non |DataTable| part of the |
| 771 // structure. | 771 // structure. |
| 772 byte get(int index) { | 772 byte get(int index) { |
| 773 return READ_BYTE_FIELD(this, kHeaderSize + (index * kOneByteSize)); | 773 return READ_BYTE_FIELD(this, kHeaderSize + (index * kOneByteSize)); |
| 774 } | 774 } |
| 775 | 775 |
| 776 void set(int index, byte value) { | 776 void set(int index, byte value) { |
| 777 WRITE_BYTE_FIELD(this, kHeaderSize + (index * kOneByteSize), value); | 777 WRITE_BYTE_FIELD(this, kHeaderSize + (index * kOneByteSize), value); |
| 778 } | 778 } |
| 779 | 779 |
| 780 int GetDataEntryOffset(int entry, int relative_index) { | 780 int GetDataEntryOffset(int entry, int relative_index) { |
| 781 int datatable_start = GetDataTableStartOffset(); | 781 int datatable_start = GetDataTableStartOffset(); |
| 782 int offset_in_datatable = entry * Derived::kEntrySize * kPointerSize; | 782 int offset_in_datatable = entry * Derived::kEntrySize * kPointerSize; |
| 783 int offset_in_entry = relative_index * kPointerSize; | 783 int offset_in_entry = relative_index * kPointerSize; |
| 784 return datatable_start + offset_in_datatable + offset_in_entry; | 784 return datatable_start + offset_in_datatable + offset_in_entry; |
| 785 } | 785 } |
| 786 | 786 |
| 787 // Returns the number elements that can fit into the allocated buffer. | 787 // Returns the number elements that can fit into the allocated buffer. |
| 788 int Capacity() { return NumberOfBuckets() * kLoadFactor; } | 788 int Capacity() { return NumberOfBuckets() * kLoadFactor; } |
| 789 | 789 |
| 790 int UsedCapacity() { return NumberOfElements() + NumberOfDeletedElements(); } | 790 int UsedCapacity() { return NumberOfElements() + NumberOfDeletedElements(); } |
| 791 }; | 791 }; |
| 792 | 792 |
| 793 class SmallOrderedHashSet : public SmallOrderedHashTable<SmallOrderedHashSet> { | 793 class SmallOrderedHashSet : public SmallOrderedHashTable<SmallOrderedHashSet> { |
| 794 public: | 794 public: |
| 795 DECLARE_CAST(SmallOrderedHashSet) | 795 DECL_CAST(SmallOrderedHashSet) |
| 796 | 796 |
| 797 DECLARE_PRINTER(SmallOrderedHashSet) | 797 DECL_PRINTER(SmallOrderedHashSet) |
| 798 | 798 |
| 799 static const int kKeyIndex = 0; | 799 static const int kKeyIndex = 0; |
| 800 static const int kEntrySize = 1; | 800 static const int kEntrySize = 1; |
| 801 | 801 |
| 802 // Adds |value| to |table|, if the capacity isn't enough, a new | 802 // Adds |value| to |table|, if the capacity isn't enough, a new |
| 803 // table is created. The original |table| is returned if there is | 803 // table is created. The original |table| is returned if there is |
| 804 // capacity to store |value| otherwise the new table is returned. | 804 // capacity to store |value| otherwise the new table is returned. |
| 805 static Handle<SmallOrderedHashSet> Add(Handle<SmallOrderedHashSet> table, | 805 static Handle<SmallOrderedHashSet> Add(Handle<SmallOrderedHashSet> table, |
| 806 Handle<Object> key); | 806 Handle<Object> key); |
| 807 }; | 807 }; |
| 808 | 808 |
| 809 class SmallOrderedHashMap : public SmallOrderedHashTable<SmallOrderedHashMap> { | 809 class SmallOrderedHashMap : public SmallOrderedHashTable<SmallOrderedHashMap> { |
| 810 public: | 810 public: |
| 811 DECLARE_CAST(SmallOrderedHashMap) | 811 DECL_CAST(SmallOrderedHashMap) |
| 812 | 812 |
| 813 DECLARE_PRINTER(SmallOrderedHashMap) | 813 DECL_PRINTER(SmallOrderedHashMap) |
| 814 | 814 |
| 815 static const int kKeyIndex = 0; | 815 static const int kKeyIndex = 0; |
| 816 static const int kValueIndex = 1; | 816 static const int kValueIndex = 1; |
| 817 static const int kEntrySize = 2; | 817 static const int kEntrySize = 2; |
| 818 | 818 |
| 819 // Adds |value| to |table|, if the capacity isn't enough, a new | 819 // Adds |value| to |table|, if the capacity isn't enough, a new |
| 820 // table is created. The original |table| is returned if there is | 820 // table is created. The original |table| is returned if there is |
| 821 // capacity to store |value| otherwise the new table is returned. | 821 // capacity to store |value| otherwise the new table is returned. |
| 822 static Handle<SmallOrderedHashMap> Add(Handle<SmallOrderedHashMap> table, | 822 static Handle<SmallOrderedHashMap> Add(Handle<SmallOrderedHashMap> table, |
| 823 Handle<Object> key, | 823 Handle<Object> key, |
| (...skipping 56 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 880 // if the [table] is not obsolete. | 880 // if the [table] is not obsolete. |
| 881 void Transition(); | 881 void Transition(); |
| 882 | 882 |
| 883 DISALLOW_IMPLICIT_CONSTRUCTORS(OrderedHashTableIterator); | 883 DISALLOW_IMPLICIT_CONSTRUCTORS(OrderedHashTableIterator); |
| 884 }; | 884 }; |
| 885 | 885 |
| 886 class JSSetIterator | 886 class JSSetIterator |
| 887 : public OrderedHashTableIterator<JSSetIterator, OrderedHashSet> { | 887 : public OrderedHashTableIterator<JSSetIterator, OrderedHashSet> { |
| 888 public: | 888 public: |
| 889 // Dispatched behavior. | 889 // Dispatched behavior. |
| 890 DECLARE_PRINTER(JSSetIterator) | 890 DECL_PRINTER(JSSetIterator) |
| 891 DECLARE_VERIFIER(JSSetIterator) | 891 DECL_VERIFIER(JSSetIterator) |
| 892 | 892 |
| 893 DECLARE_CAST(JSSetIterator) | 893 DECL_CAST(JSSetIterator) |
| 894 | 894 |
| 895 // Called by |Next| to populate the array. This allows the subclasses to | 895 // Called by |Next| to populate the array. This allows the subclasses to |
| 896 // populate the array differently. | 896 // populate the array differently. |
| 897 inline void PopulateValueArray(FixedArray* array); | 897 inline void PopulateValueArray(FixedArray* array); |
| 898 | 898 |
| 899 private: | 899 private: |
| 900 DISALLOW_IMPLICIT_CONSTRUCTORS(JSSetIterator); | 900 DISALLOW_IMPLICIT_CONSTRUCTORS(JSSetIterator); |
| 901 }; | 901 }; |
| 902 | 902 |
| 903 class JSMapIterator | 903 class JSMapIterator |
| 904 : public OrderedHashTableIterator<JSMapIterator, OrderedHashMap> { | 904 : public OrderedHashTableIterator<JSMapIterator, OrderedHashMap> { |
| 905 public: | 905 public: |
| 906 // Dispatched behavior. | 906 // Dispatched behavior. |
| 907 DECLARE_PRINTER(JSMapIterator) | 907 DECL_PRINTER(JSMapIterator) |
| 908 DECLARE_VERIFIER(JSMapIterator) | 908 DECL_VERIFIER(JSMapIterator) |
| 909 | 909 |
| 910 DECLARE_CAST(JSMapIterator) | 910 DECL_CAST(JSMapIterator) |
| 911 | 911 |
| 912 // Called by |Next| to populate the array. This allows the subclasses to | 912 // Called by |Next| to populate the array. This allows the subclasses to |
| 913 // populate the array differently. | 913 // populate the array differently. |
| 914 inline void PopulateValueArray(FixedArray* array); | 914 inline void PopulateValueArray(FixedArray* array); |
| 915 | 915 |
| 916 // Returns the current value of the iterator. This should only be called when | 916 // Returns the current value of the iterator. This should only be called when |
| 917 // |HasMore| returns true. | 917 // |HasMore| returns true. |
| 918 inline Object* CurrentValue(); | 918 inline Object* CurrentValue(); |
| 919 | 919 |
| 920 private: | 920 private: |
| 921 DISALLOW_IMPLICIT_CONSTRUCTORS(JSMapIterator); | 921 DISALLOW_IMPLICIT_CONSTRUCTORS(JSMapIterator); |
| 922 }; | 922 }; |
| 923 | 923 |
| 924 } // namespace internal | 924 } // namespace internal |
| 925 } // namespace v8 | 925 } // namespace v8 |
| 926 | 926 |
| 927 #include "src/objects/object-macros-undef.h" | 927 #include "src/objects/object-macros-undef.h" |
| 928 | 928 |
| 929 #endif // V8_OBJECTS_HASH_TABLE_H_ | 929 #endif // V8_OBJECTS_HASH_TABLE_H_ |
| OLD | NEW |