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 |