LCOV - code coverage report
Current view: top level - src/objects - ordered-hash-table.h (source / functions) Hit Total Coverage
Test: app.info Lines: 62 63 98.4 %
Date: 2019-03-21 Functions: 41 43 95.3 %

          Line data    Source code
       1             : // Copyright 2018 the V8 project authors. All rights reserved.
       2             : // Use of this source code is governed by a BSD-style license that can be
       3             : // found in the LICENSE file.
       4             : 
       5             : #ifndef V8_OBJECTS_ORDERED_HASH_TABLE_H_
       6             : #define V8_OBJECTS_ORDERED_HASH_TABLE_H_
       7             : 
       8             : #include "src/globals.h"
       9             : #include "src/objects/fixed-array.h"
      10             : #include "src/objects/js-objects.h"
      11             : #include "src/objects/smi.h"
      12             : #include "src/roots.h"
      13             : 
      14             : // Has to be the last include (doesn't have include guards):
      15             : #include "src/objects/object-macros.h"
      16             : 
      17             : namespace v8 {
      18             : namespace internal {
      19             : 
      20             : // OrderedHashTable is a HashTable with Object keys that preserves
      21             : // insertion order. There are Map and Set interfaces (OrderedHashMap
      22             : // and OrderedHashTable, below). It is meant to be used by JSMap/JSSet.
      23             : //
      24             : // Only Object keys are supported, with Object::SameValueZero() used as the
      25             : // equality operator and Object::GetHash() for the hash function.
      26             : //
      27             : // Based on the "Deterministic Hash Table" as described by Jason Orendorff at
      28             : // https://wiki.mozilla.org/User:Jorend/Deterministic_hash_tables
      29             : // Originally attributed to Tyler Close.
      30             : //
      31             : // Memory layout:
      32             : //   [0] : Prefix
      33             : //   [kPrefixSize]: element count
      34             : //   [kPrefixSize + 1]: deleted element count
      35             : //   [kPrefixSize + 2]: bucket count
      36             : //   [kPrefixSize + 3..(3 + NumberOfBuckets() - 1)]: "hash table",
      37             : //                            where each item is an offset into the
      38             : //                            data table (see below) where the first
      39             : //                            item in this bucket is stored.
      40             : //   [kPrefixSize + 3 + NumberOfBuckets()..length]: "data table", an
      41             : //                            array of length Capacity() * kEntrySize,
      42             : //                            where the first entrysize items are
      43             : //                            handled by the derived class and the
      44             : //                            item at kChainOffset is another entry
      45             : //                            into the data table indicating the next
      46             : //                            entry in this hash bucket.
      47             : //
      48             : // When we transition the table to a new version we obsolete it and reuse parts
      49             : // of the memory to store information how to transition an iterator to the new
      50             : // table:
      51             : //
      52             : // Memory layout for obsolete table:
      53             : //   [0] : Prefix
      54             : //   [kPrefixSize + 0]: bucket count
      55             : //   [kPrefixSize + 1]: Next newer table
      56             : //   [kPrefixSize + 2]: Number of removed holes or -1 when the table was
      57             : //                      cleared.
      58             : //   [kPrefixSize + 3..(3 + NumberOfRemovedHoles() - 1)]: The indexes
      59             : //                      of the removed holes.
      60             : //   [kPrefixSize + 3 + NumberOfRemovedHoles()..length]: Not used
      61             : template <class Derived, int entrysize>
      62             : class OrderedHashTable : public FixedArray {
      63             :  public:
      64             :   // Returns an OrderedHashTable (possibly |table|) with enough space
      65             :   // to add at least one new element.
      66             :   static Handle<Derived> EnsureGrowable(Isolate* isolate,
      67             :                                         Handle<Derived> table);
      68             : 
      69             :   // Returns an OrderedHashTable (possibly |table|) that's shrunken
      70             :   // if possible.
      71             :   static Handle<Derived> Shrink(Isolate* isolate, Handle<Derived> table);
      72             : 
      73             :   // Returns a new empty OrderedHashTable and records the clearing so that
      74             :   // existing iterators can be updated.
      75             :   static Handle<Derived> Clear(Isolate* isolate, Handle<Derived> table);
      76             : 
      77             :   // Returns true if the OrderedHashTable contains the key
      78             :   static bool HasKey(Isolate* isolate, Derived table, Object key);
      79             : 
      80             :   // Returns a true value if the OrderedHashTable contains the key and
      81             :   // the key has been deleted. This does not shrink the table.
      82             :   static bool Delete(Isolate* isolate, Derived table, Object key);
      83             : 
      84             :   int FindEntry(Isolate* isolate, Object key);
      85             : 
      86             :   int NumberOfElements() const {
      87             :     return Smi::ToInt(get(NumberOfElementsIndex()));
      88             :   }
      89             : 
      90             :   int NumberOfDeletedElements() const {
      91             :     return Smi::ToInt(get(NumberOfDeletedElementsIndex()));
      92             :   }
      93             : 
      94             :   // Returns the number of contiguous entries in the data table, starting at 0,
      95             :   // that either are real entries or have been deleted.
      96        1369 :   int UsedCapacity() const {
      97        1369 :     return NumberOfElements() + NumberOfDeletedElements();
      98             :   }
      99             : 
     100             :   int NumberOfBuckets() const {
     101             :     return Smi::ToInt(get(NumberOfBucketsIndex()));
     102             :   }
     103             : 
     104             :   // Returns an index into |this| for the given entry.
     105             :   int EntryToIndex(int entry) {
     106   134010200 :     return HashTableStartIndex() + NumberOfBuckets() + (entry * kEntrySize);
     107             :   }
     108             : 
     109    39050561 :   int HashToBucket(int hash) { return hash & (NumberOfBuckets() - 1); }
     110             : 
     111    28988077 :   int HashToEntry(int hash) {
     112             :     int bucket = HashToBucket(hash);
     113    28988077 :     Object entry = this->get(HashTableStartIndex() + bucket);
     114    28988077 :     return Smi::ToInt(entry);
     115             :   }
     116             : 
     117    22299439 :   int NextChainEntry(int entry) {
     118    22299439 :     Object next_entry = get(EntryToIndex(entry) + kChainOffset);
     119    22299439 :     return Smi::ToInt(next_entry);
     120             :   }
     121             : 
     122             :   // use KeyAt(i)->IsTheHole(isolate) to determine if this is a deleted entry.
     123    53839204 :   Object KeyAt(int entry) {
     124             :     DCHECK_LT(entry, this->UsedCapacity());
     125    53839197 :     return get(EntryToIndex(entry));
     126             :   }
     127             : 
     128             :   bool IsObsolete() { return !get(NextTableIndex())->IsSmi(); }
     129             : 
     130             :   // The next newer table. This is only valid if the table is obsolete.
     131             :   Derived NextTable() { return Derived::cast(get(NextTableIndex())); }
     132             : 
     133             :   // When the table is obsolete we store the indexes of the removed holes.
     134             :   int RemovedIndexAt(int index) {
     135          15 :     return Smi::ToInt(get(RemovedHolesIndex() + index));
     136             :   }
     137             : 
     138             :   // The extra +1 is for linking the bucket chains together.
     139             :   static const int kEntrySize = entrysize + 1;
     140             :   static const int kChainOffset = entrysize;
     141             : 
     142             :   static const int kNotFound = -1;
     143             :   static const int kMinCapacity = 4;
     144             : 
     145             :   static constexpr int PrefixIndex() { return 0; }
     146             : 
     147       12152 :   static constexpr int NumberOfElementsIndex() { return Derived::kPrefixSize; }
     148             : 
     149             :   // The next table is stored at the same index as the nof elements.
     150         672 :   static constexpr int NextTableIndex() { return NumberOfElementsIndex(); }
     151             : 
     152       10136 :   static constexpr int NumberOfDeletedElementsIndex() {
     153       10136 :     return NumberOfElementsIndex() + 1;
     154             :   }
     155             : 
     156        9184 :   static constexpr int NumberOfBucketsIndex() {
     157        9184 :     return NumberOfDeletedElementsIndex() + 1;
     158             :   }
     159             : 
     160        6720 :   static constexpr int HashTableStartIndex() {
     161        6720 :     return NumberOfBucketsIndex() + 1;
     162             :   }
     163             : 
     164          56 :   static constexpr int RemovedHolesIndex() { return HashTableStartIndex(); }
     165             : 
     166        1232 :   static constexpr int NumberOfElementsOffset() {
     167        1232 :     return FixedArray::OffsetOfElementAt(NumberOfElementsIndex());
     168             :   }
     169             : 
     170         672 :   static constexpr int NextTableOffset() {
     171         672 :     return FixedArray::OffsetOfElementAt(NextTableIndex());
     172             :   }
     173             : 
     174         840 :   static constexpr int NumberOfDeletedElementsOffset() {
     175         840 :     return FixedArray::OffsetOfElementAt(NumberOfDeletedElementsIndex());
     176             :   }
     177             : 
     178         336 :   static constexpr int NumberOfBucketsOffset() {
     179         336 :     return FixedArray::OffsetOfElementAt(NumberOfBucketsIndex());
     180             :   }
     181             : 
     182             :   static constexpr int HashTableStartOffset() {
     183             :     return FixedArray::OffsetOfElementAt(HashTableStartIndex());
     184             :   }
     185             : 
     186             :   static const int kLoadFactor = 2;
     187             : 
     188             :   // NumberOfDeletedElements is set to kClearedTableSentinel when
     189             :   // the table is cleared, which allows iterator transitions to
     190             :   // optimize that case.
     191             :   static const int kClearedTableSentinel = -1;
     192             :   static constexpr int MaxCapacity() {
     193             :     return (FixedArray::kMaxLength - HashTableStartIndex()) /
     194             :            (1 + (kEntrySize * kLoadFactor));
     195             :   }
     196             : 
     197             :  protected:
     198             :   // Returns an OrderedHashTable with a capacity of at least |capacity|.
     199             :   static Handle<Derived> Allocate(
     200             :       Isolate* isolate, int capacity,
     201             :       AllocationType allocation = AllocationType::kYoung);
     202             :   static Handle<Derived> Rehash(Isolate* isolate, Handle<Derived> table,
     203             :                                 int new_capacity);
     204             : 
     205             :   void SetNumberOfBuckets(int num) {
     206             :     set(NumberOfBucketsIndex(), Smi::FromInt(num));
     207             :   }
     208             : 
     209             :   void SetNumberOfElements(int num) {
     210             :     set(NumberOfElementsIndex(), Smi::FromInt(num));
     211             :   }
     212             : 
     213             :   void SetNumberOfDeletedElements(int num) {
     214             :     set(NumberOfDeletedElementsIndex(), Smi::FromInt(num));
     215             :   }
     216             : 
     217             :   // Returns the number elements that can fit into the allocated buffer.
     218    10381825 :   int Capacity() { return NumberOfBuckets() * kLoadFactor; }
     219             : 
     220      514810 :   void SetNextTable(Derived next_table) { set(NextTableIndex(), next_table); }
     221             : 
     222             :   void SetRemovedIndexAt(int index, int removed_index) {
     223             :     return set(RemovedHolesIndex() + index, Smi::FromInt(removed_index));
     224             :   }
     225             : 
     226             :   OBJECT_CONSTRUCTORS(OrderedHashTable, FixedArray);
     227             : 
     228             :  private:
     229             :   friend class OrderedNameDictionaryHandler;
     230             : };
     231             : 
     232             : class OrderedHashSet : public OrderedHashTable<OrderedHashSet, 1> {
     233             :  public:
     234             :   DECL_CAST(OrderedHashSet)
     235             : 
     236             :   static Handle<OrderedHashSet> Add(Isolate* isolate,
     237             :                                     Handle<OrderedHashSet> table,
     238             :                                     Handle<Object> value);
     239             :   static Handle<FixedArray> ConvertToKeysArray(Isolate* isolate,
     240             :                                                Handle<OrderedHashSet> table,
     241             :                                                GetKeysConversion convert);
     242             :   static Handle<OrderedHashSet> Rehash(Isolate* isolate,
     243             :                                        Handle<OrderedHashSet> table,
     244             :                                        int new_capacity);
     245             :   static Handle<OrderedHashSet> Allocate(
     246             :       Isolate* isolate, int capacity,
     247             :       AllocationType allocation = AllocationType::kYoung);
     248             :   static HeapObject GetEmpty(ReadOnlyRoots ro_roots);
     249             :   static inline RootIndex GetMapRootIndex();
     250             :   static inline bool Is(Handle<HeapObject> table);
     251             :   static const int kPrefixSize = 0;
     252             : 
     253             :   OBJECT_CONSTRUCTORS(OrderedHashSet, OrderedHashTable<OrderedHashSet, 1>);
     254             : };
     255             : 
     256             : class OrderedHashMap : public OrderedHashTable<OrderedHashMap, 2> {
     257             :  public:
     258             :   DECL_CAST(OrderedHashMap)
     259             : 
     260             :   // Returns a value if the OrderedHashMap contains the key, otherwise
     261             :   // returns undefined.
     262             :   static Handle<OrderedHashMap> Add(Isolate* isolate,
     263             :                                     Handle<OrderedHashMap> table,
     264             :                                     Handle<Object> key, Handle<Object> value);
     265             : 
     266             :   static Handle<OrderedHashMap> Allocate(
     267             :       Isolate* isolate, int capacity,
     268             :       AllocationType allocation = AllocationType::kYoung);
     269             :   static Handle<OrderedHashMap> Rehash(Isolate* isolate,
     270             :                                        Handle<OrderedHashMap> table,
     271             :                                        int new_capacity);
     272             :   Object ValueAt(int entry);
     273             : 
     274             :   // This takes and returns raw Address values containing tagged Object
     275             :   // pointers because it is called via ExternalReference.
     276             :   static Address GetHash(Isolate* isolate, Address raw_key);
     277             : 
     278             :   static HeapObject GetEmpty(ReadOnlyRoots ro_roots);
     279             :   static inline RootIndex GetMapRootIndex();
     280             :   static inline bool Is(Handle<HeapObject> table);
     281             : 
     282             :   static const int kValueOffset = 1;
     283             :   static const int kPrefixSize = 0;
     284             : 
     285             :   OBJECT_CONSTRUCTORS(OrderedHashMap, OrderedHashTable<OrderedHashMap, 2>);
     286             : };
     287             : 
     288             : // This is similar to the OrderedHashTable, except for the memory
     289             : // layout where we use byte instead of Smi. The max capacity of this
     290             : // is only 254, we transition to an OrderedHashTable beyond that
     291             : // limit.
     292             : //
     293             : // Each bucket and chain value is a byte long. The padding exists so
     294             : // that the DataTable entries start aligned. A bucket or chain value
     295             : // of 255 is used to denote an unknown entry.
     296             : //
     297             : // The prefix size is calculated as the kPrefixSize * kTaggedSize.
     298             : //
     299             : // Memory layout: [ Prefix ] [ Header ]  [ Padding ] [ DataTable ] [ HashTable ]
     300             : // [ Chains ]
     301             : //
     302             : // The index are represented as bytes, on a 64 bit machine with
     303             : // kEntrySize = 1, capacity = 4 and entries = 2:
     304             : //
     305             : // [ 0 ] : Prefix
     306             : //
     307             : // Note: For the sake of brevity, the following start with index 0
     308             : // but, they actually start from kPrefixSize * kTaggedSize to
     309             : // account for the the prefix.
     310             : //
     311             : // [ Header ]  :
     312             : //    [0] : Number of elements
     313             : //    [1] : Number of deleted elements
     314             : //    [2] : Number of buckets
     315             : //
     316             : // [ Padding ] :
     317             : //    [3 .. 7] : Padding
     318             : //
     319             : // [ DataTable ] :
     320             : //    [8  .. 15] : Entry 1
     321             : //    [16 .. 23] : Entry 2
     322             : //    [24 .. 31] : empty
     323             : //    [32 .. 39] : empty
     324             : //
     325             : // [ HashTable ] :
     326             : //    [40] : First chain-link for bucket 1
     327             : //    [41] : empty
     328             : //
     329             : // [ Chains ] :
     330             : //    [42] : Next chain link for bucket 1
     331             : //    [43] : empty
     332             : //    [44] : empty
     333             : //    [45] : empty
     334             : //
     335             : template <class Derived>
     336             : class SmallOrderedHashTable : public HeapObject {
     337             :  public:
     338             :   // Offset points to a relative location in the table
     339             :   typedef int Offset;
     340             : 
     341             :   // ByteIndex points to a index in the table that needs to be
     342             :   // converted to an Offset.
     343             :   typedef int ByteIndex;
     344             : 
     345             :   void Initialize(Isolate* isolate, int capacity);
     346             : 
     347             :   static Handle<Derived> Allocate(
     348             :       Isolate* isolate, int capacity,
     349             :       AllocationType allocation = AllocationType::kYoung);
     350             : 
     351             :   // Returns a true if the OrderedHashTable contains the key
     352             :   bool HasKey(Isolate* isolate, Handle<Object> key);
     353             : 
     354             :   // Returns a true value if the table contains the key and
     355             :   // the key has been deleted. This does not shrink the table.
     356             :   static bool Delete(Isolate* isolate, Derived table, Object key);
     357             : 
     358             :   // Returns an SmallOrderedHashTable (possibly |table|) with enough
     359             :   // space to add at least one new element. Returns empty handle if
     360             :   // we've already reached MaxCapacity.
     361             :   static MaybeHandle<Derived> Grow(Isolate* isolate, Handle<Derived> table);
     362             : 
     363             :   int FindEntry(Isolate* isolate, Object key);
     364             :   static Handle<Derived> Shrink(Isolate* isolate, Handle<Derived> table);
     365             : 
     366             :   // Iterates only fields in the DataTable.
     367             :   class BodyDescriptor;
     368             : 
     369             :   // Returns total size in bytes required for a table of given
     370             :   // capacity.
     371             :   static int SizeFor(int capacity) {
     372             :     DCHECK_GE(capacity, kMinCapacity);
     373             :     DCHECK_LE(capacity, kMaxCapacity);
     374             : 
     375             :     int data_table_size = DataTableSizeFor(capacity);
     376         443 :     int hash_table_size = capacity / kLoadFactor;
     377             :     int chain_table_size = capacity;
     378             :     int total_size = DataTableStartOffset() + data_table_size +
     379         491 :                      hash_table_size + chain_table_size;
     380             : 
     381             :     return RoundUp(total_size, kTaggedSize);
     382             :   }
     383             : 
     384             :   // Returns the number elements that can fit into the allocated table.
     385             :   int Capacity() const {
     386     1676213 :     int capacity = NumberOfBuckets() * kLoadFactor;
     387             :     DCHECK_GE(capacity, kMinCapacity);
     388             :     DCHECK_LE(capacity, kMaxCapacity);
     389             : 
     390             :     return capacity;
     391             :   }
     392             : 
     393             :   // Returns the number elements that are present in the table.
     394             :   int NumberOfElements() const {
     395       24048 :     int nof_elements = getByte(NumberOfElementsOffset(), 0);
     396             :     DCHECK_LE(nof_elements, Capacity());
     397             : 
     398             :     return nof_elements;
     399             :   }
     400             : 
     401             :   int NumberOfDeletedElements() const {
     402       22858 :     int nof_deleted_elements = getByte(NumberOfDeletedElementsOffset(), 0);
     403             :     DCHECK_LE(nof_deleted_elements, Capacity());
     404             : 
     405             :     return nof_deleted_elements;
     406             :   }
     407             : 
     408     2119103 :   int NumberOfBuckets() const { return getByte(NumberOfBucketsOffset(), 0); }
     409             : 
     410             :   V8_INLINE Object KeyAt(int entry) const;
     411             : 
     412             :   DECL_VERIFIER(SmallOrderedHashTable)
     413             : 
     414             :   static const int kMinCapacity = 4;
     415             :   static const byte kNotFound = 0xFF;
     416             : 
     417             :   // We use the value 255 to indicate kNotFound for chain and bucket
     418             :   // values, which means that this value can't be used a valid
     419             :   // index.
     420             :   static const int kMaxCapacity = 254;
     421             :   STATIC_ASSERT(kMaxCapacity < kNotFound);
     422             : 
     423             :   // The load factor is used to derive the number of buckets from
     424             :   // capacity during Allocation. We also depend on this to calaculate
     425             :   // the capacity from number of buckets after allocation. If we
     426             :   // decide to change kLoadFactor to something other than 2, capacity
     427             :   // should be stored as another field of this object.
     428             :   static const int kLoadFactor = 2;
     429             : 
     430             :   // Our growth strategy involves doubling the capacity until we reach
     431             :   // kMaxCapacity, but since the kMaxCapacity is always less than 256,
     432             :   // we will never fully utilize this table. We special case for 256,
     433             :   // by changing the new capacity to be kMaxCapacity in
     434             :   // SmallOrderedHashTable::Grow.
     435             :   static const int kGrowthHack = 256;
     436             : 
     437             :  protected:
     438             :   static Handle<Derived> Rehash(Isolate* isolate, Handle<Derived> table,
     439             :                                 int new_capacity);
     440             : 
     441             :   void SetDataEntry(int entry, int relative_index, Object value);
     442             : 
     443             :   // TODO(gsathya): Calculate all the various possible values for this
     444             :   // at compile time since capacity can only be 4 different values.
     445             :   Offset GetBucketsStartOffset() const {
     446             :     int capacity = Capacity();
     447             :     int data_table_size = DataTableSizeFor(capacity);
     448     1664265 :     return DataTableStartOffset() + data_table_size;
     449             :   }
     450             : 
     451             :   Address GetHashTableStartAddress(int capacity) const {
     452         886 :     return FIELD_ADDR(*this,
     453             :                       DataTableStartOffset() + DataTableSizeFor(capacity));
     454             :   }
     455             : 
     456             :   void SetFirstEntry(int bucket, byte value) {
     457             :     DCHECK_LE(static_cast<unsigned>(bucket), NumberOfBuckets());
     458             :     setByte(GetBucketsStartOffset(), bucket, value);
     459             :   }
     460             : 
     461             :   int GetFirstEntry(int bucket) const {
     462             :     DCHECK_LE(static_cast<unsigned>(bucket), NumberOfBuckets());
     463     1632930 :     return getByte(GetBucketsStartOffset(), bucket);
     464             :   }
     465             : 
     466             :   // TODO(gsathya): Calculate all the various possible values for this
     467             :   // at compile time since capacity can only be 4 different values.
     468             :   Offset GetChainTableOffset() const {
     469             :     int nof_buckets = NumberOfBuckets();
     470      442475 :     int capacity = nof_buckets * kLoadFactor;
     471             :     DCHECK_EQ(Capacity(), capacity);
     472             : 
     473             :     int data_table_size = DataTableSizeFor(capacity);
     474             :     int hash_table_size = nof_buckets;
     475     3160385 :     return DataTableStartOffset() + data_table_size + hash_table_size;
     476             :   }
     477             : 
     478             :   void SetNextEntry(int entry, int next_entry) {
     479             :     DCHECK_LT(static_cast<unsigned>(entry), Capacity());
     480             :     DCHECK_GE(static_cast<unsigned>(next_entry), 0);
     481             :     DCHECK(next_entry <= Capacity() || next_entry == kNotFound);
     482             :     setByte(GetChainTableOffset(), entry, next_entry);
     483             :   }
     484             : 
     485             :   int GetNextEntry(int entry) const {
     486             :     DCHECK_LT(entry, Capacity());
     487     3139380 :     return getByte(GetChainTableOffset(), entry);
     488             :   }
     489             : 
     490             :   V8_INLINE Object GetDataEntry(int entry, int relative_index);
     491             : 
     492     1653935 :   int HashToBucket(int hash) const { return hash & (NumberOfBuckets() - 1); }
     493             : 
     494             :   int HashToFirstEntry(int hash) const {
     495             :     int bucket = HashToBucket(hash);
     496             :     int entry = GetFirstEntry(bucket);
     497             :     DCHECK(entry < Capacity() || entry == kNotFound);
     498             :     return entry;
     499             :   }
     500             : 
     501             :   void SetNumberOfBuckets(int num) { setByte(NumberOfBucketsOffset(), 0, num); }
     502             : 
     503             :   void SetNumberOfElements(int num) {
     504             :     DCHECK_LE(static_cast<unsigned>(num), Capacity());
     505             :     setByte(NumberOfElementsOffset(), 0, num);
     506             :   }
     507             : 
     508             :   void SetNumberOfDeletedElements(int num) {
     509             :     DCHECK_LE(static_cast<unsigned>(num), Capacity());
     510             :     setByte(NumberOfDeletedElementsOffset(), 0, num);
     511             :   }
     512             : 
     513          32 :   static constexpr Offset PrefixOffset() { return kHeaderSize; }
     514             : 
     515          32 :   static constexpr Offset NumberOfElementsOffset() {
     516          32 :     return PrefixOffset() + (Derived::kPrefixSize * kTaggedSize);
     517             :   }
     518             : 
     519          24 :   static constexpr Offset NumberOfDeletedElementsOffset() {
     520          24 :     return NumberOfElementsOffset() + kOneByteSize;
     521             :   }
     522             : 
     523          16 :   static constexpr Offset NumberOfBucketsOffset() {
     524          16 :     return NumberOfDeletedElementsOffset() + kOneByteSize;
     525             :   }
     526             : 
     527           8 :   static constexpr Offset DataTableStartOffset() {
     528           8 :     return RoundUp<kTaggedSize>(NumberOfBucketsOffset());
     529             :   }
     530             : 
     531             :   static constexpr int DataTableSizeFor(int capacity) {
     532     2107674 :     return capacity * Derived::kEntrySize * kTaggedSize;
     533             :   }
     534             : 
     535             :   // This is used for accessing the non |DataTable| part of the
     536             :   // structure.
     537             :   byte getByte(Offset offset, ByteIndex index) const {
     538             :     DCHECK(offset < DataTableStartOffset() ||
     539             :            offset >= GetBucketsStartOffset());
     540     6948994 :     return READ_BYTE_FIELD(*this, offset + (index * kOneByteSize));
     541             :   }
     542             : 
     543             :   void setByte(Offset offset, ByteIndex index, byte value) {
     544             :     DCHECK(offset < DataTableStartOffset() ||
     545             :            offset >= GetBucketsStartOffset());
     546       56589 :     WRITE_BYTE_FIELD(*this, offset + (index * kOneByteSize), value);
     547             :   }
     548             : 
     549        2600 :   Offset GetDataEntryOffset(int entry, int relative_index) const {
     550             :     DCHECK_LT(entry, Capacity());
     551     3700800 :     int offset_in_datatable = entry * Derived::kEntrySize * kTaggedSize;
     552       78640 :     int offset_in_entry = relative_index * kTaggedSize;
     553     3726535 :     return DataTableStartOffset() + offset_in_datatable + offset_in_entry;
     554             :   }
     555             : 
     556             :   int UsedCapacity() const {
     557       10350 :     int used = NumberOfElements() + NumberOfDeletedElements();
     558             :     DCHECK_LE(used, Capacity());
     559             : 
     560             :     return used;
     561             :   }
     562             : 
     563             :  private:
     564             :   friend class OrderedHashMapHandler;
     565             :   friend class OrderedHashSetHandler;
     566             :   friend class OrderedNameDictionaryHandler;
     567             :   friend class CodeStubAssembler;
     568             : 
     569             :   OBJECT_CONSTRUCTORS(SmallOrderedHashTable, HeapObject);
     570             : };
     571             : 
     572             : class SmallOrderedHashSet : public SmallOrderedHashTable<SmallOrderedHashSet> {
     573             :  public:
     574             :   DECL_CAST(SmallOrderedHashSet)
     575             : 
     576             :   DECL_PRINTER(SmallOrderedHashSet)
     577             :   DECL_VERIFIER(SmallOrderedHashSet)
     578             : 
     579             :   static const int kKeyIndex = 0;
     580             :   static const int kEntrySize = 1;
     581             :   static const int kPrefixSize = 0;
     582             : 
     583             :   // Adds |value| to |table|, if the capacity isn't enough, a new
     584             :   // table is created. The original |table| is returned if there is
     585             :   // capacity to store |value| otherwise the new table is returned.
     586             :   static MaybeHandle<SmallOrderedHashSet> Add(Isolate* isolate,
     587             :                                               Handle<SmallOrderedHashSet> table,
     588             :                                               Handle<Object> key);
     589             :   static inline bool Is(Handle<HeapObject> table);
     590             :   static inline RootIndex GetMapRootIndex();
     591             :   static Handle<SmallOrderedHashSet> Rehash(Isolate* isolate,
     592             :                                             Handle<SmallOrderedHashSet> table,
     593             :                                             int new_capacity);
     594             :   OBJECT_CONSTRUCTORS(SmallOrderedHashSet,
     595             :                       SmallOrderedHashTable<SmallOrderedHashSet>);
     596             : };
     597             : 
     598             : class SmallOrderedHashMap : public SmallOrderedHashTable<SmallOrderedHashMap> {
     599             :  public:
     600             :   DECL_CAST(SmallOrderedHashMap)
     601             : 
     602             :   DECL_PRINTER(SmallOrderedHashMap)
     603             :   DECL_VERIFIER(SmallOrderedHashMap)
     604             : 
     605             :   static const int kKeyIndex = 0;
     606             :   static const int kValueIndex = 1;
     607             :   static const int kEntrySize = 2;
     608             :   static const int kPrefixSize = 0;
     609             : 
     610             :   // Adds |value| to |table|, if the capacity isn't enough, a new
     611             :   // table is created. The original |table| is returned if there is
     612             :   // capacity to store |value| otherwise the new table is returned.
     613             :   static MaybeHandle<SmallOrderedHashMap> Add(Isolate* isolate,
     614             :                                               Handle<SmallOrderedHashMap> table,
     615             :                                               Handle<Object> key,
     616             :                                               Handle<Object> value);
     617             :   static inline bool Is(Handle<HeapObject> table);
     618             :   static inline RootIndex GetMapRootIndex();
     619             : 
     620             :   static Handle<SmallOrderedHashMap> Rehash(Isolate* isolate,
     621             :                                             Handle<SmallOrderedHashMap> table,
     622             :                                             int new_capacity);
     623             : 
     624             :   OBJECT_CONSTRUCTORS(SmallOrderedHashMap,
     625             :                       SmallOrderedHashTable<SmallOrderedHashMap>);
     626             : };
     627             : 
     628             : // TODO(gsathya): Rename this to OrderedHashTable, after we rename
     629             : // OrderedHashTable to LargeOrderedHashTable. Also set up a
     630             : // OrderedHashSetBase class as a base class for the two tables and use
     631             : // that instead of a HeapObject here.
     632             : template <class SmallTable, class LargeTable>
     633             : class OrderedHashTableHandler {
     634             :  public:
     635             :   typedef int Entry;
     636             : 
     637             :   static Handle<HeapObject> Allocate(Isolate* isolate, int capacity);
     638             :   static bool Delete(Handle<HeapObject> table, Handle<Object> key);
     639             :   static bool HasKey(Isolate* isolate, Handle<HeapObject> table,
     640             :                      Handle<Object> key);
     641             : 
     642             :   // TODO(gsathya): Move this to OrderedHashTable
     643             :   static const int OrderedHashTableMinSize =
     644             :       SmallOrderedHashTable<SmallTable>::kGrowthHack << 1;
     645             : };
     646             : 
     647             : class OrderedHashMapHandler
     648             :     : public OrderedHashTableHandler<SmallOrderedHashMap, OrderedHashMap> {
     649             :  public:
     650             :   static Handle<HeapObject> Add(Isolate* isolate, Handle<HeapObject> table,
     651             :                                 Handle<Object> key, Handle<Object> value);
     652             :   static Handle<OrderedHashMap> AdjustRepresentation(
     653             :       Isolate* isolate, Handle<SmallOrderedHashMap> table);
     654             : };
     655             : 
     656             : class OrderedHashSetHandler
     657             :     : public OrderedHashTableHandler<SmallOrderedHashSet, OrderedHashSet> {
     658             :  public:
     659             :   static Handle<HeapObject> Add(Isolate* isolate, Handle<HeapObject> table,
     660             :                                 Handle<Object> key);
     661             :   static Handle<OrderedHashSet> AdjustRepresentation(
     662             :       Isolate* isolate, Handle<SmallOrderedHashSet> table);
     663             : };
     664             : 
     665             : class OrderedNameDictionary
     666             :     : public OrderedHashTable<OrderedNameDictionary, 3> {
     667             :  public:
     668             :   DECL_CAST(OrderedNameDictionary)
     669             : 
     670             :   static Handle<OrderedNameDictionary> Add(Isolate* isolate,
     671             :                                            Handle<OrderedNameDictionary> table,
     672             :                                            Handle<Name> key,
     673             :                                            Handle<Object> value,
     674             :                                            PropertyDetails details);
     675             : 
     676             :   void SetEntry(Isolate* isolate, int entry, Object key, Object value,
     677             :                 PropertyDetails details);
     678             : 
     679             :   static Handle<OrderedNameDictionary> DeleteEntry(
     680             :       Isolate* isolate, Handle<OrderedNameDictionary> table, int entry);
     681             : 
     682             :   static Handle<OrderedNameDictionary> Allocate(
     683             :       Isolate* isolate, int capacity,
     684             :       AllocationType allocation = AllocationType::kYoung);
     685             : 
     686             :   static Handle<OrderedNameDictionary> Rehash(
     687             :       Isolate* isolate, Handle<OrderedNameDictionary> table, int new_capacity);
     688             : 
     689             :   // Returns the value for entry.
     690             :   inline Object ValueAt(int entry);
     691             : 
     692             :   // Set the value for entry.
     693             :   inline void ValueAtPut(int entry, Object value);
     694             : 
     695             :   // Returns the property details for the property at entry.
     696             :   inline PropertyDetails DetailsAt(int entry);
     697             : 
     698             :   // Set the details for entry.
     699             :   inline void DetailsAtPut(int entry, PropertyDetails value);
     700             : 
     701             :   inline void SetHash(int hash);
     702             :   inline int Hash();
     703             : 
     704             :   static HeapObject GetEmpty(ReadOnlyRoots ro_roots);
     705             :   static inline RootIndex GetMapRootIndex();
     706             : 
     707             :   static const int kValueOffset = 1;
     708             :   static const int kPropertyDetailsOffset = 2;
     709             :   static const int kPrefixSize = 1;
     710             : 
     711             :   OBJECT_CONSTRUCTORS(OrderedNameDictionary,
     712             :                       OrderedHashTable<OrderedNameDictionary, 3>);
     713             : };
     714             : 
     715             : class OrderedNameDictionaryHandler
     716             :     : public OrderedHashTableHandler<SmallOrderedNameDictionary,
     717             :                                      OrderedNameDictionary> {
     718             :  public:
     719             :   static Handle<HeapObject> Add(Isolate* isolate, Handle<HeapObject> table,
     720             :                                 Handle<Name> key, Handle<Object> value,
     721             :                                 PropertyDetails details);
     722             :   static Handle<HeapObject> Shrink(Isolate* isolate, Handle<HeapObject> table);
     723             : 
     724             :   static Handle<HeapObject> DeleteEntry(Isolate* isolate,
     725             :                                         Handle<HeapObject> table, int entry);
     726             :   static int FindEntry(Isolate* isolate, HeapObject table, Name key);
     727             :   static void SetEntry(Isolate* isolate, HeapObject table, int entry,
     728             :                        Object key, Object value, PropertyDetails details);
     729             : 
     730             :   // Returns the value for entry.
     731             :   static Object ValueAt(HeapObject table, int entry);
     732             : 
     733             :   // Set the value for entry.
     734             :   static void ValueAtPut(HeapObject table, int entry, Object value);
     735             : 
     736             :   // Returns the property details for the property at entry.
     737             :   static PropertyDetails DetailsAt(HeapObject table, int entry);
     738             : 
     739             :   // Set the details for entry.
     740             :   static void DetailsAtPut(HeapObject table, int entry, PropertyDetails value);
     741             : 
     742             :   static Name KeyAt(HeapObject table, int entry);
     743             : 
     744             :   static void SetHash(HeapObject table, int hash);
     745             :   static int Hash(HeapObject table);
     746             : 
     747             :   static int NumberOfElements(HeapObject table);
     748             :   static int Capacity(HeapObject table);
     749             : 
     750             :   static const int kNotFound = -1;
     751             : 
     752             :  protected:
     753             :   static Handle<OrderedNameDictionary> AdjustRepresentation(
     754             :       Isolate* isolate, Handle<SmallOrderedNameDictionary> table);
     755             : };
     756             : 
     757             : class SmallOrderedNameDictionary
     758             :     : public SmallOrderedHashTable<SmallOrderedNameDictionary> {
     759             :  public:
     760             :   DECL_CAST(SmallOrderedNameDictionary)
     761             : 
     762             :   DECL_PRINTER(SmallOrderedNameDictionary)
     763             :   DECL_VERIFIER(SmallOrderedNameDictionary)
     764             : 
     765             :   // Returns the value for entry.
     766             :   inline Object ValueAt(int entry);
     767             : 
     768             :   static Handle<SmallOrderedNameDictionary> Rehash(
     769             :       Isolate* isolate, Handle<SmallOrderedNameDictionary> table,
     770             :       int new_capacity);
     771             : 
     772             :   static Handle<SmallOrderedNameDictionary> DeleteEntry(
     773             :       Isolate* isolate, Handle<SmallOrderedNameDictionary> table, int entry);
     774             : 
     775             :   // Set the value for entry.
     776             :   inline void ValueAtPut(int entry, Object value);
     777             : 
     778             :   // Returns the property details for the property at entry.
     779             :   inline PropertyDetails DetailsAt(int entry);
     780             : 
     781             :   // Set the details for entry.
     782             :   inline void DetailsAtPut(int entry, PropertyDetails value);
     783             : 
     784             :   inline void SetHash(int hash);
     785             :   inline int Hash();
     786             : 
     787             :   static const int kKeyIndex = 0;
     788             :   static const int kValueIndex = 1;
     789             :   static const int kPropertyDetailsIndex = 2;
     790             :   static const int kEntrySize = 3;
     791             :   static const int kPrefixSize = 1;
     792             : 
     793             :   // Adds |value| to |table|, if the capacity isn't enough, a new
     794             :   // table is created. The original |table| is returned if there is
     795             :   // capacity to store |value| otherwise the new table is returned.
     796             :   static MaybeHandle<SmallOrderedNameDictionary> Add(
     797             :       Isolate* isolate, Handle<SmallOrderedNameDictionary> table,
     798             :       Handle<Name> key, Handle<Object> value, PropertyDetails details);
     799             : 
     800             :   void SetEntry(Isolate* isolate, int entry, Object key, Object value,
     801             :                 PropertyDetails details);
     802             : 
     803             :   static inline RootIndex GetMapRootIndex();
     804             : 
     805             :   OBJECT_CONSTRUCTORS(SmallOrderedNameDictionary,
     806             :                       SmallOrderedHashTable<SmallOrderedNameDictionary>);
     807             : };
     808             : 
     809             : class JSCollectionIterator : public JSObject {
     810             :  public:
     811             :   // [table]: the backing hash table mapping keys to values.
     812             :   DECL_ACCESSORS(table, Object)
     813             : 
     814             :   // [index]: The index into the data table.
     815             :   DECL_ACCESSORS(index, Object)
     816             : 
     817             :   void JSCollectionIteratorPrint(std::ostream& os, const char* name);
     818             : 
     819             :   DEFINE_FIELD_OFFSET_CONSTANTS(JSObject::kHeaderSize,
     820             :                                 TORQUE_GENERATED_JSCOLLECTION_ITERATOR_FIELDS)
     821             : 
     822             :   OBJECT_CONSTRUCTORS(JSCollectionIterator, JSObject);
     823             : };
     824             : 
     825             : // OrderedHashTableIterator is an iterator that iterates over the keys and
     826             : // values of an OrderedHashTable.
     827             : //
     828             : // The iterator has a reference to the underlying OrderedHashTable data,
     829             : // [table], as well as the current [index] the iterator is at.
     830             : //
     831             : // When the OrderedHashTable is rehashed it adds a reference from the old table
     832             : // to the new table as well as storing enough data about the changes so that the
     833             : // iterator [index] can be adjusted accordingly.
     834             : //
     835             : // When the [Next] result from the iterator is requested, the iterator checks if
     836             : // there is a newer table that it needs to transition to.
     837             : template <class Derived, class TableType>
     838             : class OrderedHashTableIterator : public JSCollectionIterator {
     839             :  public:
     840             :   // Whether the iterator has more elements. This needs to be called before
     841             :   // calling |CurrentKey| and/or |CurrentValue|.
     842             :   bool HasMore();
     843             : 
     844             :   // Move the index forward one.
     845           0 :   void MoveNext() { set_index(Smi::FromInt(Smi::ToInt(index()) + 1)); }
     846             : 
     847             :   // Returns the current key of the iterator. This should only be called when
     848             :   // |HasMore| returns true.
     849             :   inline Object CurrentKey();
     850             : 
     851             :  private:
     852             :   // Transitions the iterator to the non obsolete backing store. This is a NOP
     853             :   // if the [table] is not obsolete.
     854             :   void Transition();
     855             : 
     856             :   OBJECT_CONSTRUCTORS(OrderedHashTableIterator, JSCollectionIterator);
     857             : };
     858             : 
     859             : }  // namespace internal
     860             : }  // namespace v8
     861             : 
     862             : #include "src/objects/object-macros-undef.h"
     863             : 
     864             : #endif  // V8_OBJECTS_ORDERED_HASH_TABLE_H_

Generated by: LCOV version 1.10