Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(1)

Side by Side Diff: src/objects/hash-table.h

Issue 2961253002: [objects] Rename macros from DECLARE_ to DECL_ for consistency. (Closed)
Patch Set: Created 3 years, 5 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « src/objects/frame-array.h ('k') | src/objects/literal-objects.h » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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
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
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
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
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
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
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
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_
OLDNEW
« no previous file with comments | « src/objects/frame-array.h ('k') | src/objects/literal-objects.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698