LCOV - code coverage report
Current view: top level - src/objects - ordered-hash-table.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 370 425 87.1 %
Date: 2019-02-19 Functions: 76 96 79.2 %

          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             : #include "src/objects/ordered-hash-table.h"
       6             : 
       7             : #include "src/heap/heap-inl.h"
       8             : #include "src/isolate.h"
       9             : #include "src/objects-inl.h"
      10             : #include "src/objects/js-collection-inl.h"
      11             : #include "src/objects/ordered-hash-table-inl.h"
      12             : 
      13             : namespace v8 {
      14             : namespace internal {
      15             : 
      16             : template <class Derived, int entrysize>
      17      856848 : Handle<Derived> OrderedHashTable<Derived, entrysize>::Allocate(
      18             :     Isolate* isolate, int capacity, PretenureFlag pretenure) {
      19             :   // Capacity must be a power of two, since we depend on being able
      20             :   // to divide and multiple by 2 (kLoadFactor) to derive capacity
      21             :   // from number of buckets. If we decide to change kLoadFactor
      22             :   // to something other than 2, capacity should be stored as another
      23             :   // field of this object.
      24      856848 :   capacity = base::bits::RoundUpToPowerOfTwo32(Max(kMinCapacity, capacity));
      25      856848 :   if (capacity > MaxCapacity()) {
      26           0 :     isolate->heap()->FatalProcessOutOfMemory("invalid table size");
      27             :   }
      28      856848 :   int num_buckets = capacity / kLoadFactor;
      29             :   Handle<FixedArray> backing_store = isolate->factory()->NewFixedArrayWithMap(
      30             :       Derived::GetMapRootIndex(),
      31      856848 :       HashTableStartIndex() + num_buckets + (capacity * kEntrySize), pretenure);
      32      856848 :   Handle<Derived> table = Handle<Derived>::cast(backing_store);
      33    27230114 :   for (int i = 0; i < num_buckets; ++i) {
      34             :     table->set(HashTableStartIndex() + i, Smi::FromInt(kNotFound));
      35             :   }
      36             :   table->SetNumberOfBuckets(num_buckets);
      37             :   table->SetNumberOfElements(0);
      38             :   table->SetNumberOfDeletedElements(0);
      39      856848 :   return table;
      40             : }
      41             : 
      42             : template <class Derived, int entrysize>
      43    10226995 : Handle<Derived> OrderedHashTable<Derived, entrysize>::EnsureGrowable(
      44             :     Isolate* isolate, Handle<Derived> table) {
      45             :   DCHECK(!table->IsObsolete());
      46             : 
      47    10226996 :   int nof = table->NumberOfElements();
      48    10226995 :   int nod = table->NumberOfDeletedElements();
      49    20453993 :   int capacity = table->Capacity();
      50    10226998 :   if ((nof + nod) < capacity) return table;
      51             :   // Don't need to grow if we can simply clear out deleted entries instead.
      52             :   // Note that we can't compact in place, though, so we always allocate
      53             :   // a new table.
      54             :   return Derived::Rehash(isolate, table,
      55      365729 :                          (nod < (capacity >> 1)) ? capacity << 1 : capacity);
      56             : }
      57             : 
      58             : template <class Derived, int entrysize>
      59      162379 : Handle<Derived> OrderedHashTable<Derived, entrysize>::Shrink(
      60             :     Isolate* isolate, Handle<Derived> table) {
      61             :   DCHECK(!table->IsObsolete());
      62             : 
      63      162379 :   int nof = table->NumberOfElements();
      64      324758 :   int capacity = table->Capacity();
      65      162379 :   if (nof >= (capacity >> 2)) return table;
      66          35 :   return Derived::Rehash(isolate, table, capacity / 2);
      67             : }
      68             : 
      69             : template <class Derived, int entrysize>
      70         254 : Handle<Derived> OrderedHashTable<Derived, entrysize>::Clear(
      71             :     Isolate* isolate, Handle<Derived> table) {
      72             :   DCHECK(!table->IsObsolete());
      73             : 
      74             :   Handle<Derived> new_table =
      75             :       Allocate(isolate, kMinCapacity,
      76         254 :                Heap::InYoungGeneration(*table) ? NOT_TENURED : TENURED);
      77             : 
      78         508 :   table->SetNextTable(*new_table);
      79             :   table->SetNumberOfDeletedElements(kClearedTableSentinel);
      80             : 
      81         254 :   return new_table;
      82             : }
      83             : 
      84             : template <class Derived, int entrysize>
      85     4924595 : bool OrderedHashTable<Derived, entrysize>::HasKey(Isolate* isolate,
      86             :                                                   Derived table, Object key) {
      87             :   DCHECK_IMPLIES(entrysize == 1, table->IsOrderedHashSet());
      88             :   DCHECK_IMPLIES(entrysize == 2, table->IsOrderedHashMap());
      89             :   DisallowHeapAllocation no_gc;
      90     4924595 :   int entry = table->FindEntry(isolate, key);
      91     4924595 :   return entry != kNotFound;
      92             : }
      93             : 
      94             : template <class Derived, int entrysize>
      95     4924675 : int OrderedHashTable<Derived, entrysize>::FindEntry(Isolate* isolate,
      96             :                                                     Object key) {
      97             :   int entry;
      98             :   // This special cases for Smi, so that we avoid the HandleScope
      99             :   // creation below.
     100     4924675 :   if (key->IsSmi()) {
     101     4924335 :     uint32_t hash = ComputeUnseededHash(Smi::ToInt(key));
     102     4924335 :     entry = HashToEntry(hash & Smi::kMaxValue);
     103             :   } else {
     104             :     HandleScope scope(isolate);
     105         340 :     Object hash = key->GetHash();
     106             :     // If the object does not have an identity hash, it was never used as a key
     107         340 :     if (hash->IsUndefined(isolate)) return kNotFound;
     108         340 :     entry = HashToEntry(Smi::ToInt(hash));
     109             :   }
     110             : 
     111             :   // Walk the chain in the bucket to find the key.
     112     8718185 :   while (entry != kNotFound) {
     113     8717945 :     Object candidate_key = KeyAt(entry);
     114     8717945 :     if (candidate_key->SameValueZero(key)) break;
     115     3793510 :     entry = NextChainEntry(entry);
     116             :   }
     117             : 
     118     4924675 :   return entry;
     119             : }
     120             : 
     121    10041439 : Handle<OrderedHashSet> OrderedHashSet::Add(Isolate* isolate,
     122             :                                            Handle<OrderedHashSet> table,
     123             :                                            Handle<Object> key) {
     124    20082878 :   int hash = key->GetOrCreateHash(isolate)->value();
     125    10041439 :   int entry = table->HashToEntry(hash);
     126             :   // Walk the chain of the bucket and try finding the key.
     127    33371303 :   while (entry != kNotFound) {
     128    13288959 :     Object candidate_key = table->KeyAt(entry);
     129             :     // Do not add if we have the key already
     130    13288959 :     if (candidate_key->SameValueZero(*key)) return table;
     131    13288425 :     entry = table->NextChainEntry(entry);
     132             :   }
     133             : 
     134    10040905 :   table = OrderedHashSet::EnsureGrowable(isolate, table);
     135             :   // Read the existing bucket values.
     136    20081810 :   int bucket = table->HashToBucket(hash);
     137    10040905 :   int previous_entry = table->HashToEntry(hash);
     138    10040905 :   int nof = table->NumberOfElements();
     139             :   // Insert a new entry at the end,
     140    10040905 :   int new_entry = nof + table->NumberOfDeletedElements();
     141    20081810 :   int new_index = table->EntryToIndex(new_entry);
     142    10040905 :   table->set(new_index, *key);
     143             :   table->set(new_index + kChainOffset, Smi::FromInt(previous_entry));
     144             :   // and point the bucket to the new entry.
     145             :   table->set(HashTableStartIndex() + bucket, Smi::FromInt(new_entry));
     146    10040905 :   table->SetNumberOfElements(nof + 1);
     147    10040905 :   return table;
     148             : }
     149             : 
     150      249093 : Handle<FixedArray> OrderedHashSet::ConvertToKeysArray(
     151             :     Isolate* isolate, Handle<OrderedHashSet> table, GetKeysConversion convert) {
     152      249093 :   int length = table->NumberOfElements();
     153      249093 :   int nof_buckets = table->NumberOfBuckets();
     154             :   // Convert the dictionary to a linear list.
     155      249093 :   Handle<FixedArray> result = Handle<FixedArray>::cast(table);
     156             :   // From this point on table is no longer a valid OrderedHashSet.
     157      249093 :   result->set_map(ReadOnlyRoots(isolate).fixed_array_map());
     158             :   int const kMaxStringTableEntries =
     159      249093 :       isolate->heap()->MaxNumberToStringCacheSize();
     160    10284635 :   for (int i = 0; i < length; i++) {
     161    10035542 :     int index = HashTableStartIndex() + nof_buckets + (i * kEntrySize);
     162    10035542 :     Object key = table->get(index);
     163    10035542 :     if (convert == GetKeysConversion::kConvertToString) {
     164             :       uint32_t index_value;
     165     9942127 :       if (key->ToArrayIndex(&index_value)) {
     166             :         // Avoid trashing the Number2String cache if indices get very large.
     167     3517541 :         bool use_cache = i < kMaxStringTableEntries;
     168     7035082 :         key = *isolate->factory()->Uint32ToString(index_value, use_cache);
     169             :       } else {
     170     6424586 :         CHECK(key->IsName());
     171             :       }
     172             :     }
     173    10035542 :     result->set(i, key);
     174             :   }
     175      249093 :   return FixedArray::ShrinkOrEmpty(isolate, result, length);
     176             : }
     177             : 
     178          20 : HeapObject OrderedHashSet::GetEmpty(ReadOnlyRoots ro_roots) {
     179          20 :   return ro_roots.empty_ordered_hash_set();
     180             : }
     181             : 
     182          50 : HeapObject OrderedHashMap::GetEmpty(ReadOnlyRoots ro_roots) {
     183          50 :   return ro_roots.empty_ordered_hash_map();
     184             : }
     185             : 
     186             : template <class Derived, int entrysize>
     187      527638 : Handle<Derived> OrderedHashTable<Derived, entrysize>::Rehash(
     188             :     Isolate* isolate, Handle<Derived> table, int new_capacity) {
     189             :   DCHECK(!table->IsObsolete());
     190             : 
     191             :   Handle<Derived> new_table = Derived::Allocate(
     192             :       isolate, new_capacity,
     193      527638 :       Heap::InYoungGeneration(*table) ? NOT_TENURED : TENURED);
     194      527638 :   int nof = table->NumberOfElements();
     195      527638 :   int nod = table->NumberOfDeletedElements();
     196      527638 :   int new_buckets = new_table->NumberOfBuckets();
     197             :   int new_entry = 0;
     198             :   int removed_holes_index = 0;
     199             : 
     200             :   DisallowHeapAllocation no_gc;
     201    24663453 :   for (int old_entry = 0; old_entry < (nof + nod); ++old_entry) {
     202    24135815 :     Object key = table->KeyAt(old_entry);
     203    24135813 :     if (key->IsTheHole(isolate)) {
     204      487108 :       table->SetRemovedIndexAt(removed_holes_index++, old_entry);
     205      243554 :       continue;
     206             :     }
     207             : 
     208    23892259 :     Object hash = key->GetHash();
     209    23892259 :     int bucket = Smi::ToInt(hash) & (new_buckets - 1);
     210    47784518 :     Object chain_entry = new_table->get(HashTableStartIndex() + bucket);
     211             :     new_table->set(HashTableStartIndex() + bucket, Smi::FromInt(new_entry));
     212    47784518 :     int new_index = new_table->EntryToIndex(new_entry);
     213    47784518 :     int old_index = table->EntryToIndex(old_entry);
     214    50208552 :     for (int i = 0; i < entrysize; ++i) {
     215    52632579 :       Object value = table->get(old_index + i);
     216    52632579 :       new_table->set(new_index + i, value);
     217             :     }
     218    47784525 :     new_table->set(new_index + kChainOffset, chain_entry);
     219    23892260 :     ++new_entry;
     220             :   }
     221             : 
     222             :   DCHECK_EQ(nod, removed_holes_index);
     223             : 
     224             :   new_table->SetNumberOfElements(nof);
     225     1055276 :   table->SetNextTable(*new_table);
     226             : 
     227      527638 :   return new_table;
     228             : }
     229             : 
     230           0 : Handle<OrderedHashSet> OrderedHashSet::Rehash(Isolate* isolate,
     231             :                                               Handle<OrderedHashSet> table,
     232             :                                               int new_capacity) {
     233             :   return OrderedHashTable<OrderedHashSet, 1>::Rehash(isolate, table,
     234      362677 :                                                      new_capacity);
     235             : }
     236             : 
     237           0 : Handle<OrderedHashMap> OrderedHashMap::Rehash(Isolate* isolate,
     238             :                                               Handle<OrderedHashMap> table,
     239             :                                               int new_capacity) {
     240             :   return OrderedHashTable<OrderedHashMap, 2>::Rehash(isolate, table,
     241      164846 :                                                      new_capacity);
     242             : }
     243             : 
     244         115 : Handle<OrderedNameDictionary> OrderedNameDictionary::Rehash(
     245             :     Isolate* isolate, Handle<OrderedNameDictionary> table, int new_capacity) {
     246             :   Handle<OrderedNameDictionary> new_table =
     247             :       OrderedHashTable<OrderedNameDictionary, 3>::Rehash(isolate, table,
     248         115 :                                                          new_capacity);
     249         230 :   new_table->SetHash(table->Hash());
     250         115 :   return new_table;
     251             : }
     252             : 
     253             : template <class Derived, int entrysize>
     254          80 : bool OrderedHashTable<Derived, entrysize>::Delete(Isolate* isolate,
     255             :                                                   Derived table, Object key) {
     256             :   DisallowHeapAllocation no_gc;
     257          80 :   int entry = table->FindEntry(isolate, key);
     258          80 :   if (entry == kNotFound) return false;
     259             : 
     260          40 :   int nof = table->NumberOfElements();
     261          40 :   int nod = table->NumberOfDeletedElements();
     262             :   int index = table->EntryToIndex(entry);
     263             : 
     264          40 :   Object hole = ReadOnlyRoots(isolate).the_hole_value();
     265         100 :   for (int i = 0; i < entrysize; ++i) {
     266          60 :     table->set(index + i, hole);
     267             :   }
     268             : 
     269          40 :   table->SetNumberOfElements(nof - 1);
     270          40 :   table->SetNumberOfDeletedElements(nod + 1);
     271             : 
     272          40 :   return true;
     273             : }
     274             : 
     275      140214 : Address OrderedHashMap::GetHash(Isolate* isolate, Address raw_key) {
     276             :   DisallowHeapAllocation no_gc;
     277             :   Object key(raw_key);
     278      140214 :   Object hash = key->GetHash();
     279             :   // If the object does not have an identity hash, it was never used as a key
     280      140214 :   if (hash->IsUndefined(isolate)) return Smi::FromInt(-1).ptr();
     281             :   DCHECK(hash->IsSmi());
     282             :   DCHECK_GE(Smi::cast(hash)->value(), 0);
     283      140214 :   return hash.ptr();
     284             : }
     285             : 
     286        5200 : Handle<OrderedHashMap> OrderedHashMap::Add(Isolate* isolate,
     287             :                                            Handle<OrderedHashMap> table,
     288             :                                            Handle<Object> key,
     289             :                                            Handle<Object> value) {
     290       10400 :   int hash = key->GetOrCreateHash(isolate)->value();
     291        5200 :   int entry = table->HashToEntry(hash);
     292             :   // Walk the chain of the bucket and try finding the key.
     293             :   {
     294             :     DisallowHeapAllocation no_gc;
     295        5200 :     Object raw_key = *key;
     296       16785 :     while (entry != kNotFound) {
     297        6405 :       Object candidate_key = table->KeyAt(entry);
     298             :       // Do not add if we have the key already
     299        6405 :       if (candidate_key->SameValueZero(raw_key)) return table;
     300        6385 :       entry = table->NextChainEntry(entry);
     301             :     }
     302             :   }
     303             : 
     304        5180 :   table = OrderedHashMap::EnsureGrowable(isolate, table);
     305             :   // Read the existing bucket values.
     306       10360 :   int bucket = table->HashToBucket(hash);
     307        5180 :   int previous_entry = table->HashToEntry(hash);
     308        5180 :   int nof = table->NumberOfElements();
     309             :   // Insert a new entry at the end,
     310        5180 :   int new_entry = nof + table->NumberOfDeletedElements();
     311       10360 :   int new_index = table->EntryToIndex(new_entry);
     312        5180 :   table->set(new_index, *key);
     313       10360 :   table->set(new_index + kValueOffset, *value);
     314             :   table->set(new_index + kChainOffset, Smi::FromInt(previous_entry));
     315             :   // and point the bucket to the new entry.
     316             :   table->set(HashTableStartIndex() + bucket, Smi::FromInt(new_entry));
     317        5180 :   table->SetNumberOfElements(nof + 1);
     318        5180 :   return table;
     319             : }
     320             : 
     321             : template <>
     322     3948680 : int OrderedHashTable<OrderedNameDictionary, 3>::FindEntry(Isolate* isolate,
     323             :                                                           Object key) {
     324             :   DisallowHeapAllocation no_gc;
     325             : 
     326             :   DCHECK(key->IsUniqueName());
     327     3948680 :   Name raw_key = Name::cast(key);
     328             : 
     329     3948680 :   int entry = HashToEntry(raw_key->Hash());
     330    11871460 :   while (entry != kNotFound) {
     331     6438060 :     Object candidate_key = KeyAt(entry);
     332             :     DCHECK(candidate_key->IsTheHole() ||
     333             :            Name::cast(candidate_key)->IsUniqueName());
     334     6438060 :     if (candidate_key == raw_key) return entry;
     335             : 
     336             :     // TODO(gsathya): This is loading the bucket count from the hash
     337             :     // table for every iteration. This should be peeled out of the
     338             :     // loop.
     339     3974100 :     entry = NextChainEntry(entry);
     340             :   }
     341             : 
     342             :   return kNotFound;
     343             : }
     344             : 
     345       10800 : Handle<OrderedNameDictionary> OrderedNameDictionary::Add(
     346             :     Isolate* isolate, Handle<OrderedNameDictionary> table, Handle<Name> key,
     347             :     Handle<Object> value, PropertyDetails details) {
     348             :   DCHECK_EQ(kNotFound, table->FindEntry(isolate, *key));
     349             : 
     350       10800 :   table = OrderedNameDictionary::EnsureGrowable(isolate, table);
     351             :   // Read the existing bucket values.
     352       10800 :   int hash = key->Hash();
     353       21600 :   int bucket = table->HashToBucket(hash);
     354       10800 :   int previous_entry = table->HashToEntry(hash);
     355       10800 :   int nof = table->NumberOfElements();
     356             :   // Insert a new entry at the end,
     357       10800 :   int new_entry = nof + table->NumberOfDeletedElements();
     358       21600 :   int new_index = table->EntryToIndex(new_entry);
     359       21600 :   table->set(new_index, *key);
     360       21600 :   table->set(new_index + kValueOffset, *value);
     361             : 
     362             :   // TODO(gsathya): Optimize how PropertyDetails are stored in this
     363             :   // dictionary to save memory (by reusing padding?) and performance
     364             :   // (by not doing the Smi conversion).
     365             :   table->set(new_index + kPropertyDetailsOffset, details.AsSmi());
     366             : 
     367             :   table->set(new_index + kChainOffset, Smi::FromInt(previous_entry));
     368             :   // and point the bucket to the new entry.
     369             :   table->set(HashTableStartIndex() + bucket, Smi::FromInt(new_entry));
     370       10800 :   table->SetNumberOfElements(nof + 1);
     371       10800 :   return table;
     372             : }
     373             : 
     374         510 : void OrderedNameDictionary::SetEntry(Isolate* isolate, int entry, Object key,
     375             :                                      Object value, PropertyDetails details) {
     376             :   DisallowHeapAllocation gc;
     377             :   DCHECK_IMPLIES(!key->IsName(), key->IsTheHole(isolate));
     378             :   DisallowHeapAllocation no_gc;
     379         510 :   int index = EntryToIndex(entry);
     380         510 :   this->set(index, key);
     381         510 :   this->set(index + kValueOffset, value);
     382             : 
     383             :   // TODO(gsathya): Optimize how PropertyDetails are stored in this
     384             :   // dictionary to save memory (by reusing padding?) and performance
     385             :   // (by not doing the Smi conversion).
     386             :   this->set(index + kPropertyDetailsOffset, details.AsSmi());
     387         510 : }
     388             : 
     389         505 : Handle<OrderedNameDictionary> OrderedNameDictionary::DeleteEntry(
     390             :     Isolate* isolate, Handle<OrderedNameDictionary> table, int entry) {
     391             :   DCHECK_NE(entry, kNotFound);
     392             : 
     393         505 :   Object hole = ReadOnlyRoots(isolate).the_hole_value();
     394         505 :   PropertyDetails details = PropertyDetails::Empty();
     395         505 :   table->SetEntry(isolate, entry, hole, hole, details);
     396             : 
     397         505 :   int nof = table->NumberOfElements();
     398         505 :   table->SetNumberOfElements(nof - 1);
     399         505 :   int nod = table->NumberOfDeletedElements();
     400         505 :   table->SetNumberOfDeletedElements(nod + 1);
     401             : 
     402         505 :   return Shrink(isolate, table);
     403             : }
     404             : 
     405      328873 : Handle<OrderedHashSet> OrderedHashSet::Allocate(Isolate* isolate, int capacity,
     406             :                                                 PretenureFlag pretenure) {
     407             :   return OrderedHashTable<OrderedHashSet, 1>::Allocate(isolate, capacity,
     408      691555 :                                                        pretenure);
     409             : }
     410             : 
     411          33 : Handle<OrderedHashMap> OrderedHashMap::Allocate(Isolate* isolate, int capacity,
     412             :                                                 PretenureFlag pretenure) {
     413             :   return OrderedHashTable<OrderedHashMap, 2>::Allocate(isolate, capacity,
     414      164884 :                                                        pretenure);
     415             : }
     416             : 
     417         155 : Handle<OrderedNameDictionary> OrderedNameDictionary::Allocate(
     418             :     Isolate* isolate, int capacity, PretenureFlag pretenure) {
     419             :   Handle<OrderedNameDictionary> table =
     420             :       OrderedHashTable<OrderedNameDictionary, 3>::Allocate(isolate, capacity,
     421         155 :                                                            pretenure);
     422             :   table->SetHash(PropertyArray::kNoHashSentinel);
     423         155 :   return table;
     424             : }
     425             : 
     426             : template Handle<OrderedHashSet>
     427             : OrderedHashTable<OrderedHashSet, 1>::EnsureGrowable(
     428             :     Isolate* isolate, Handle<OrderedHashSet> table);
     429             : 
     430             : template Handle<OrderedHashSet> OrderedHashTable<OrderedHashSet, 1>::Shrink(
     431             :     Isolate* isolate, Handle<OrderedHashSet> table);
     432             : 
     433             : template Handle<OrderedHashSet> OrderedHashTable<OrderedHashSet, 1>::Clear(
     434             :     Isolate* isolate, Handle<OrderedHashSet> table);
     435             : 
     436             : template bool OrderedHashTable<OrderedHashSet, 1>::HasKey(Isolate* isolate,
     437             :                                                           OrderedHashSet table,
     438             :                                                           Object key);
     439             : 
     440             : template bool OrderedHashTable<OrderedHashSet, 1>::Delete(Isolate* isolate,
     441             :                                                           OrderedHashSet table,
     442             :                                                           Object key);
     443             : 
     444             : template int OrderedHashTable<OrderedHashSet, 1>::FindEntry(Isolate* isolate,
     445             :                                                             Object key);
     446             : 
     447             : template Handle<OrderedHashMap>
     448             : OrderedHashTable<OrderedHashMap, 2>::EnsureGrowable(
     449             :     Isolate* isolate, Handle<OrderedHashMap> table);
     450             : 
     451             : template Handle<OrderedHashMap> OrderedHashTable<OrderedHashMap, 2>::Shrink(
     452             :     Isolate* isolate, Handle<OrderedHashMap> table);
     453             : 
     454             : template Handle<OrderedHashMap> OrderedHashTable<OrderedHashMap, 2>::Clear(
     455             :     Isolate* isolate, Handle<OrderedHashMap> table);
     456             : 
     457             : template bool OrderedHashTable<OrderedHashMap, 2>::HasKey(Isolate* isolate,
     458             :                                                           OrderedHashMap table,
     459             :                                                           Object key);
     460             : 
     461             : template bool OrderedHashTable<OrderedHashMap, 2>::Delete(Isolate* isolate,
     462             :                                                           OrderedHashMap table,
     463             :                                                           Object key);
     464             : 
     465             : template int OrderedHashTable<OrderedHashMap, 2>::FindEntry(Isolate* isolate,
     466             :                                                             Object key);
     467             : 
     468             : template Handle<OrderedNameDictionary>
     469             : OrderedHashTable<OrderedNameDictionary, 3>::Shrink(
     470             :     Isolate* isolate, Handle<OrderedNameDictionary> table);
     471             : 
     472             : template Handle<OrderedNameDictionary>
     473             : OrderedHashTable<OrderedNameDictionary, 3>::EnsureGrowable(
     474             :     Isolate* isolate, Handle<OrderedNameDictionary> table);
     475             : 
     476             : template <>
     477             : Handle<SmallOrderedHashSet>
     478           0 : SmallOrderedHashTable<SmallOrderedHashSet>::Allocate(Isolate* isolate,
     479             :                                                      int capacity,
     480             :                                                      PretenureFlag pretenure) {
     481          70 :   return isolate->factory()->NewSmallOrderedHashSet(capacity, pretenure);
     482             : }
     483             : 
     484             : template <>
     485             : Handle<SmallOrderedHashMap>
     486           0 : SmallOrderedHashTable<SmallOrderedHashMap>::Allocate(Isolate* isolate,
     487             :                                                      int capacity,
     488             :                                                      PretenureFlag pretenure) {
     489          70 :   return isolate->factory()->NewSmallOrderedHashMap(capacity, pretenure);
     490             : }
     491             : 
     492             : template <>
     493             : Handle<SmallOrderedNameDictionary>
     494           0 : SmallOrderedHashTable<SmallOrderedNameDictionary>::Allocate(
     495             :     Isolate* isolate, int capacity, PretenureFlag pretenure) {
     496         165 :   return isolate->factory()->NewSmallOrderedNameDictionary(capacity, pretenure);
     497             : }
     498             : 
     499             : template <class Derived>
     500         443 : void SmallOrderedHashTable<Derived>::Initialize(Isolate* isolate,
     501             :                                                 int capacity) {
     502             :   DisallowHeapAllocation no_gc;
     503         443 :   int num_buckets = capacity / kLoadFactor;
     504             :   int num_chains = capacity;
     505             : 
     506             :   SetNumberOfBuckets(num_buckets);
     507             :   SetNumberOfElements(0);
     508             :   SetNumberOfDeletedElements(0);
     509             : 
     510             :   Address hashtable_start = GetHashTableStartAddress(capacity);
     511             :   memset(reinterpret_cast<byte*>(hashtable_start), kNotFound,
     512         443 :          num_buckets + num_chains);
     513             : 
     514         443 :   if (Heap::InYoungGeneration(*this)) {
     515             :     MemsetTagged(RawField(DataTableStartOffset()),
     516             :                  ReadOnlyRoots(isolate).the_hole_value(),
     517         443 :                  capacity * Derived::kEntrySize);
     518             :   } else {
     519           0 :     for (int i = 0; i < capacity; i++) {
     520           0 :       for (int j = 0; j < Derived::kEntrySize; j++) {
     521           0 :         SetDataEntry(i, j, ReadOnlyRoots(isolate).the_hole_value());
     522             :       }
     523             :     }
     524             :   }
     525             : 
     526             : #ifdef DEBUG
     527             :   for (int i = 0; i < num_buckets; ++i) {
     528             :     DCHECK_EQ(kNotFound, GetFirstEntry(i));
     529             :   }
     530             : 
     531             :   for (int i = 0; i < num_chains; ++i) {
     532             :     DCHECK_EQ(kNotFound, GetNextEntry(i));
     533             :   }
     534             : 
     535             :   for (int i = 0; i < capacity; ++i) {
     536             :     for (int j = 0; j < Derived::kEntrySize; j++) {
     537             :       DCHECK_EQ(ReadOnlyRoots(isolate).the_hole_value(), GetDataEntry(i, j));
     538             :     }
     539             :   }
     540             : #endif  // DEBUG
     541         443 : }
     542             : 
     543        2635 : MaybeHandle<SmallOrderedHashSet> SmallOrderedHashSet::Add(
     544             :     Isolate* isolate, Handle<SmallOrderedHashSet> table, Handle<Object> key) {
     545        2635 :   if (table->HasKey(isolate, key)) return table;
     546             : 
     547        2605 :   if (table->UsedCapacity() >= table->Capacity()) {
     548             :     MaybeHandle<SmallOrderedHashSet> new_table =
     549          70 :         SmallOrderedHashSet::Grow(isolate, table);
     550          70 :     if (!new_table.ToHandle(&table)) {
     551           5 :       return MaybeHandle<SmallOrderedHashSet>();
     552             :     }
     553             :   }
     554             : 
     555        5200 :   int hash = key->GetOrCreateHash(isolate)->value();
     556             :   int nof = table->NumberOfElements();
     557             : 
     558             :   // Read the existing bucket values.
     559             :   int bucket = table->HashToBucket(hash);
     560             :   int previous_entry = table->HashToFirstEntry(hash);
     561             : 
     562             :   // Insert a new entry at the end,
     563        2600 :   int new_entry = nof + table->NumberOfDeletedElements();
     564             : 
     565        2600 :   table->SetDataEntry(new_entry, SmallOrderedHashSet::kKeyIndex, *key);
     566        2600 :   table->SetFirstEntry(bucket, new_entry);
     567             :   table->SetNextEntry(new_entry, previous_entry);
     568             : 
     569             :   // and update book keeping.
     570        2600 :   table->SetNumberOfElements(nof + 1);
     571             : 
     572        2600 :   return table;
     573             : }
     574             : 
     575        2635 : MaybeHandle<SmallOrderedHashMap> SmallOrderedHashMap::Add(
     576             :     Isolate* isolate, Handle<SmallOrderedHashMap> table, Handle<Object> key,
     577             :     Handle<Object> value) {
     578        2635 :   if (table->HasKey(isolate, key)) return table;
     579             : 
     580        2605 :   if (table->UsedCapacity() >= table->Capacity()) {
     581             :     MaybeHandle<SmallOrderedHashMap> new_table =
     582          70 :         SmallOrderedHashMap::Grow(isolate, table);
     583          70 :     if (!new_table.ToHandle(&table)) {
     584           5 :       return MaybeHandle<SmallOrderedHashMap>();
     585             :     }
     586             :   }
     587             : 
     588        5200 :   int hash = key->GetOrCreateHash(isolate)->value();
     589             :   int nof = table->NumberOfElements();
     590             : 
     591             :   // Read the existing bucket values.
     592             :   int bucket = table->HashToBucket(hash);
     593             :   int previous_entry = table->HashToFirstEntry(hash);
     594             : 
     595             :   // Insert a new entry at the end,
     596        2600 :   int new_entry = nof + table->NumberOfDeletedElements();
     597             : 
     598        2600 :   table->SetDataEntry(new_entry, SmallOrderedHashMap::kValueIndex, *value);
     599        2600 :   table->SetDataEntry(new_entry, SmallOrderedHashMap::kKeyIndex, *key);
     600        2600 :   table->SetFirstEntry(bucket, new_entry);
     601             :   table->SetNextEntry(new_entry, previous_entry);
     602             : 
     603             :   // and update book keeping.
     604        2600 :   table->SetNumberOfElements(nof + 1);
     605             : 
     606        2600 :   return table;
     607             : }
     608             : 
     609             : template <>
     610     1298080 : int SmallOrderedHashTable<SmallOrderedNameDictionary>::FindEntry(
     611             :     Isolate* isolate, Object key) {
     612             :   DisallowHeapAllocation no_gc;
     613             :   DCHECK(key->IsUniqueName());
     614     1298080 :   Name raw_key = Name::cast(key);
     615             : 
     616     1298080 :   int entry = HashToFirstEntry(raw_key->Hash());
     617             : 
     618             :   // Walk the chain in the bucket to find the key.
     619     5270190 :   while (entry != kNotFound) {
     620             :     Object candidate_key = KeyAt(entry);
     621     2836080 :     if (candidate_key == key) return entry;
     622             :     entry = GetNextEntry(entry);
     623             :   }
     624             : 
     625             :   return kNotFound;
     626             : }
     627             : 
     628        5140 : MaybeHandle<SmallOrderedNameDictionary> SmallOrderedNameDictionary::Add(
     629             :     Isolate* isolate, Handle<SmallOrderedNameDictionary> table,
     630             :     Handle<Name> key, Handle<Object> value, PropertyDetails details) {
     631             :   DCHECK_EQ(kNotFound, table->FindEntry(isolate, *key));
     632             : 
     633        5140 :   if (table->UsedCapacity() >= table->Capacity()) {
     634             :     MaybeHandle<SmallOrderedNameDictionary> new_table =
     635         130 :         SmallOrderedNameDictionary::Grow(isolate, table);
     636         130 :     if (!new_table.ToHandle(&table)) {
     637          10 :       return MaybeHandle<SmallOrderedNameDictionary>();
     638             :     }
     639             :   }
     640             : 
     641             :   int nof = table->NumberOfElements();
     642             : 
     643             :   // Read the existing bucket values.
     644        5130 :   int hash = key->Hash();
     645             :   int bucket = table->HashToBucket(hash);
     646             :   int previous_entry = table->HashToFirstEntry(hash);
     647             : 
     648             :   // Insert a new entry at the end,
     649        5130 :   int new_entry = nof + table->NumberOfDeletedElements();
     650             : 
     651       10260 :   table->SetDataEntry(new_entry, SmallOrderedNameDictionary::kValueIndex,
     652        5130 :                       *value);
     653       10260 :   table->SetDataEntry(new_entry, SmallOrderedNameDictionary::kKeyIndex, *key);
     654             : 
     655             :   // TODO(gsathya): PropertyDetails should be stored as part of the
     656             :   // data table to save more memory.
     657       10260 :   table->SetDataEntry(new_entry,
     658             :                       SmallOrderedNameDictionary::kPropertyDetailsIndex,
     659       15390 :                       details.AsSmi());
     660        5130 :   table->SetFirstEntry(bucket, new_entry);
     661             :   table->SetNextEntry(new_entry, previous_entry);
     662             : 
     663             :   // and update book keeping.
     664        5130 :   table->SetNumberOfElements(nof + 1);
     665             : 
     666        5130 :   return table;
     667             : }
     668             : 
     669        1280 : void SmallOrderedNameDictionary::SetEntry(Isolate* isolate, int entry,
     670             :                                           Object key, Object value,
     671             :                                           PropertyDetails details) {
     672             :   DCHECK_IMPLIES(!key->IsName(), key->IsTheHole(isolate));
     673        1280 :   SetDataEntry(entry, SmallOrderedNameDictionary::kValueIndex, value);
     674        1280 :   SetDataEntry(entry, SmallOrderedNameDictionary::kKeyIndex, key);
     675             : 
     676             :   // TODO(gsathya): PropertyDetails should be stored as part of the
     677             :   // data table to save more memory.
     678             :   SetDataEntry(entry, SmallOrderedNameDictionary::kPropertyDetailsIndex,
     679        1280 :                details.AsSmi());
     680        1280 : }
     681             : 
     682             : template <class Derived>
     683      334790 : bool SmallOrderedHashTable<Derived>::HasKey(Isolate* isolate,
     684             :                                             Handle<Object> key) {
     685             :   DisallowHeapAllocation no_gc;
     686      334790 :   return FindEntry(isolate, *key) != kNotFound;
     687             : }
     688             : 
     689             : template <class Derived>
     690          80 : bool SmallOrderedHashTable<Derived>::Delete(Isolate* isolate, Derived table,
     691             :                                             Object key) {
     692             :   DisallowHeapAllocation no_gc;
     693          80 :   int entry = table->FindEntry(isolate, key);
     694          80 :   if (entry == kNotFound) return false;
     695             : 
     696             :   int nof = table->NumberOfElements();
     697             :   int nod = table->NumberOfDeletedElements();
     698             : 
     699          40 :   Object hole = ReadOnlyRoots(isolate).the_hole_value();
     700         100 :   for (int j = 0; j < Derived::kEntrySize; j++) {
     701          60 :     table->SetDataEntry(entry, j, hole);
     702             :   }
     703             : 
     704          40 :   table->SetNumberOfElements(nof - 1);
     705          40 :   table->SetNumberOfDeletedElements(nod + 1);
     706             : 
     707          40 :   return true;
     708             : }
     709             : 
     710        1275 : Handle<SmallOrderedNameDictionary> SmallOrderedNameDictionary::DeleteEntry(
     711             :     Isolate* isolate, Handle<SmallOrderedNameDictionary> table, int entry) {
     712             :   DCHECK_NE(entry, kNotFound);
     713             :   {
     714             :     DisallowHeapAllocation no_gc;
     715        1275 :     Object hole = ReadOnlyRoots(isolate).the_hole_value();
     716        1275 :     PropertyDetails details = PropertyDetails::Empty();
     717        1275 :     table->SetEntry(isolate, entry, hole, hole, details);
     718             : 
     719             :     int nof = table->NumberOfElements();
     720        1275 :     table->SetNumberOfElements(nof - 1);
     721             :     int nod = table->NumberOfDeletedElements();
     722        1275 :     table->SetNumberOfDeletedElements(nod + 1);
     723             :   }
     724        1275 :   return Shrink(isolate, table);
     725             : }
     726             : 
     727             : template <class Derived>
     728         290 : Handle<Derived> SmallOrderedHashTable<Derived>::Rehash(Isolate* isolate,
     729             :                                                        Handle<Derived> table,
     730             :                                                        int new_capacity) {
     731             :   DCHECK_GE(kMaxCapacity, new_capacity);
     732             : 
     733             :   Handle<Derived> new_table = SmallOrderedHashTable<Derived>::Allocate(
     734             :       isolate, new_capacity,
     735         290 :       Heap::InYoungGeneration(*table) ? NOT_TENURED : TENURED);
     736             :   int nof = table->NumberOfElements();
     737             :   int nod = table->NumberOfDeletedElements();
     738             :   int new_entry = 0;
     739             : 
     740             :   {
     741             :     DisallowHeapAllocation no_gc;
     742       12280 :     for (int old_entry = 0; old_entry < (nof + nod); ++old_entry) {
     743       11990 :       Object key = table->KeyAt(old_entry);
     744       13305 :       if (key->IsTheHole(isolate)) continue;
     745             : 
     746       10675 :       int hash = Smi::ToInt(key->GetHash());
     747             :       int bucket = new_table->HashToBucket(hash);
     748             :       int chain = new_table->GetFirstEntry(bucket);
     749             : 
     750       10675 :       new_table->SetFirstEntry(bucket, new_entry);
     751             :       new_table->SetNextEntry(new_entry, chain);
     752             : 
     753       35140 :       for (int i = 0; i < Derived::kEntrySize; ++i) {
     754       24465 :         Object value = table->GetDataEntry(old_entry, i);
     755       24465 :         new_table->SetDataEntry(new_entry, i, value);
     756             :       }
     757             : 
     758       10675 :       ++new_entry;
     759             :     }
     760             : 
     761             :     new_table->SetNumberOfElements(nof);
     762             :   }
     763         290 :   return new_table;
     764             : }
     765             : 
     766           0 : Handle<SmallOrderedHashSet> SmallOrderedHashSet::Rehash(
     767             :     Isolate* isolate, Handle<SmallOrderedHashSet> table, int new_capacity) {
     768             :   return SmallOrderedHashTable<SmallOrderedHashSet>::Rehash(isolate, table,
     769          65 :                                                             new_capacity);
     770             : }
     771             : 
     772           0 : Handle<SmallOrderedHashMap> SmallOrderedHashMap::Rehash(
     773             :     Isolate* isolate, Handle<SmallOrderedHashMap> table, int new_capacity) {
     774             :   return SmallOrderedHashTable<SmallOrderedHashMap>::Rehash(isolate, table,
     775          65 :                                                             new_capacity);
     776             : }
     777             : 
     778         160 : Handle<SmallOrderedNameDictionary> SmallOrderedNameDictionary::Rehash(
     779             :     Isolate* isolate, Handle<SmallOrderedNameDictionary> table,
     780             :     int new_capacity) {
     781             :   Handle<SmallOrderedNameDictionary> new_table =
     782             :       SmallOrderedHashTable<SmallOrderedNameDictionary>::Rehash(isolate, table,
     783         160 :                                                                 new_capacity);
     784             :   new_table->SetHash(table->Hash());
     785         160 :   return new_table;
     786             : }
     787             : 
     788             : template <class Derived>
     789        1275 : Handle<Derived> SmallOrderedHashTable<Derived>::Shrink(Isolate* isolate,
     790             :                                                        Handle<Derived> table) {
     791             :   int nof = table->NumberOfElements();
     792             :   int capacity = table->Capacity();
     793        1275 :   if (nof >= (capacity >> 2)) return table;
     794          40 :   return Derived::Rehash(isolate, table, capacity / 2);
     795             : }
     796             : 
     797             : template <class Derived>
     798         270 : MaybeHandle<Derived> SmallOrderedHashTable<Derived>::Grow(
     799             :     Isolate* isolate, Handle<Derived> table) {
     800             :   int capacity = table->Capacity();
     801             :   int new_capacity = capacity;
     802             : 
     803             :   // Don't need to grow if we can simply clear out deleted entries instead.
     804             :   // TODO(gsathya): Compact in place, instead of allocating a new table.
     805         270 :   if (table->NumberOfDeletedElements() < (capacity >> 1)) {
     806         260 :     new_capacity = capacity << 1;
     807             : 
     808             :     // The max capacity of our table is 254. We special case for 256 to
     809             :     // account for our growth strategy, otherwise we would only fill up
     810             :     // to 128 entries in our table.
     811         260 :     if (new_capacity == kGrowthHack) {
     812             :       new_capacity = kMaxCapacity;
     813             :     }
     814             : 
     815             :     // We need to migrate to a bigger hash table.
     816         260 :     if (new_capacity > kMaxCapacity) {
     817          20 :       return MaybeHandle<Derived>();
     818             :     }
     819             :   }
     820             : 
     821         250 :   return Derived::Rehash(isolate, table, new_capacity);
     822             : }
     823             : 
     824             : template <class Derived>
     825      334870 : int SmallOrderedHashTable<Derived>::FindEntry(Isolate* isolate, Object key) {
     826             :   DisallowHeapAllocation no_gc;
     827      334870 :   Object hash = key->GetHash();
     828             : 
     829      334870 :   if (hash->IsUndefined(isolate)) return kNotFound;
     830      334850 :   int entry = HashToFirstEntry(Smi::ToInt(hash));
     831             : 
     832             :   // Walk the chain in the bucket to find the key.
     833     1091290 :   while (entry != kNotFound) {
     834      750980 :     Object candidate_key = KeyAt(entry);
     835      750980 :     if (candidate_key->SameValueZero(key)) return entry;
     836             :     entry = GetNextEntry(entry);
     837             :   }
     838             :   return kNotFound;
     839             : }
     840             : 
     841             : template bool SmallOrderedHashTable<SmallOrderedHashSet>::HasKey(
     842             :     Isolate* isolate, Handle<Object> key);
     843             : template Handle<SmallOrderedHashSet>
     844             : SmallOrderedHashTable<SmallOrderedHashSet>::Rehash(
     845             :     Isolate* isolate, Handle<SmallOrderedHashSet> table, int new_capacity);
     846             : template Handle<SmallOrderedHashSet>
     847             : SmallOrderedHashTable<SmallOrderedHashSet>::Shrink(
     848             :     Isolate* isolate, Handle<SmallOrderedHashSet> table);
     849             : template MaybeHandle<SmallOrderedHashSet>
     850             : SmallOrderedHashTable<SmallOrderedHashSet>::Grow(
     851             :     Isolate* isolate, Handle<SmallOrderedHashSet> table);
     852             : template void SmallOrderedHashTable<SmallOrderedHashSet>::Initialize(
     853             :     Isolate* isolate, int capacity);
     854             : 
     855             : template bool SmallOrderedHashTable<SmallOrderedHashMap>::HasKey(
     856             :     Isolate* isolate, Handle<Object> key);
     857             : template Handle<SmallOrderedHashMap>
     858             : SmallOrderedHashTable<SmallOrderedHashMap>::Rehash(
     859             :     Isolate* isolate, Handle<SmallOrderedHashMap> table, int new_capacity);
     860             : template Handle<SmallOrderedHashMap>
     861             : SmallOrderedHashTable<SmallOrderedHashMap>::Shrink(
     862             :     Isolate* isolate, Handle<SmallOrderedHashMap> table);
     863             : template MaybeHandle<SmallOrderedHashMap>
     864             : SmallOrderedHashTable<SmallOrderedHashMap>::Grow(
     865             :     Isolate* isolate, Handle<SmallOrderedHashMap> table);
     866             : template void SmallOrderedHashTable<SmallOrderedHashMap>::Initialize(
     867             :     Isolate* isolate, int capacity);
     868             : 
     869             : template bool SmallOrderedHashTable<SmallOrderedHashMap>::Delete(
     870             :     Isolate* isolate, SmallOrderedHashMap table, Object key);
     871             : template bool SmallOrderedHashTable<SmallOrderedHashSet>::Delete(
     872             :     Isolate* isolate, SmallOrderedHashSet table, Object key);
     873             : 
     874             : template void SmallOrderedHashTable<SmallOrderedNameDictionary>::Initialize(
     875             :     Isolate* isolate, int capacity);
     876             : template Handle<SmallOrderedNameDictionary>
     877             : SmallOrderedHashTable<SmallOrderedNameDictionary>::Shrink(
     878             :     Isolate* isolate, Handle<SmallOrderedNameDictionary> table);
     879             : 
     880             : template <class SmallTable, class LargeTable>
     881          15 : Handle<HeapObject> OrderedHashTableHandler<SmallTable, LargeTable>::Allocate(
     882             :     Isolate* isolate, int capacity) {
     883          15 :   if (capacity < SmallTable::kMaxCapacity) {
     884          15 :     return SmallTable::Allocate(isolate, capacity);
     885             :   }
     886             : 
     887           0 :   return LargeTable::Allocate(isolate, capacity);
     888             : }
     889             : 
     890             : template Handle<HeapObject>
     891             : OrderedHashTableHandler<SmallOrderedHashSet, OrderedHashSet>::Allocate(
     892             :     Isolate* isolate, int capacity);
     893             : template Handle<HeapObject>
     894             : OrderedHashTableHandler<SmallOrderedHashMap, OrderedHashMap>::Allocate(
     895             :     Isolate* isolate, int capacity);
     896             : template Handle<HeapObject>
     897             : OrderedHashTableHandler<SmallOrderedNameDictionary,
     898             :                         OrderedNameDictionary>::Allocate(Isolate* isolate,
     899             :                                                          int capacity);
     900             : 
     901             : template <class SmallTable, class LargeTable>
     902             : bool OrderedHashTableHandler<SmallTable, LargeTable>::Delete(
     903             :     Handle<HeapObject> table, Handle<Object> key) {
     904             :   if (SmallTable::Is(table)) {
     905             :     return SmallTable::Delete(Handle<SmallTable>::cast(table), key);
     906             :   }
     907             : 
     908             :   DCHECK(LargeTable::Is(table));
     909             :   // Note: Once we migrate to the a big hash table, we never migrate
     910             :   // down to a smaller hash table.
     911             :   return LargeTable::Delete(Handle<LargeTable>::cast(table), key);
     912             : }
     913             : 
     914             : template <class SmallTable, class LargeTable>
     915     5248030 : bool OrderedHashTableHandler<SmallTable, LargeTable>::HasKey(
     916             :     Isolate* isolate, Handle<HeapObject> table, Handle<Object> key) {
     917     5248030 :   if (SmallTable::Is(table)) {
     918      647760 :     return Handle<SmallTable>::cast(table)->HasKey(isolate, key);
     919             :   }
     920             : 
     921             :   DCHECK(LargeTable::Is(table));
     922     4924150 :   return LargeTable::HasKey(isolate, LargeTable::cast(*table), *key);
     923             : }
     924             : 
     925             : template bool
     926             : OrderedHashTableHandler<SmallOrderedHashSet, OrderedHashSet>::HasKey(
     927             :     Isolate* isolate, Handle<HeapObject> table, Handle<Object> key);
     928             : template bool
     929             : OrderedHashTableHandler<SmallOrderedHashMap, OrderedHashMap>::HasKey(
     930             :     Isolate* isolate, Handle<HeapObject> table, Handle<Object> key);
     931             : 
     932           5 : Handle<OrderedHashMap> OrderedHashMapHandler::AdjustRepresentation(
     933             :     Isolate* isolate, Handle<SmallOrderedHashMap> table) {
     934             :   Handle<OrderedHashMap> new_table =
     935             :       OrderedHashMap::Allocate(isolate, OrderedHashTableMinSize);
     936             :   int nof = table->NumberOfElements();
     937             :   int nod = table->NumberOfDeletedElements();
     938             : 
     939             :   // TODO(gsathya): Optimize the lookup to not re calc offsets. Also,
     940             :   // unhandlify this code as we preallocate the new backing store with
     941             :   // the proper capacity.
     942        1275 :   for (int entry = 0; entry < (nof + nod); ++entry) {
     943             :     Handle<Object> key = handle(table->KeyAt(entry), isolate);
     944        2540 :     if (key->IsTheHole(isolate)) continue;
     945             :     Handle<Object> value = handle(
     946        1270 :         table->GetDataEntry(entry, SmallOrderedHashMap::kValueIndex), isolate);
     947        1270 :     new_table = OrderedHashMap::Add(isolate, new_table, key, value);
     948             :   }
     949             : 
     950           5 :   return new_table;
     951             : }
     952             : 
     953           5 : Handle<OrderedHashSet> OrderedHashSetHandler::AdjustRepresentation(
     954             :     Isolate* isolate, Handle<SmallOrderedHashSet> table) {
     955             :   Handle<OrderedHashSet> new_table =
     956             :       OrderedHashSet::Allocate(isolate, OrderedHashTableMinSize);
     957             :   int nof = table->NumberOfElements();
     958             :   int nod = table->NumberOfDeletedElements();
     959             : 
     960             :   // TODO(gsathya): Optimize the lookup to not re calc offsets. Also,
     961             :   // unhandlify this code as we preallocate the new backing store with
     962             :   // the proper capacity.
     963        1275 :   for (int entry = 0; entry < (nof + nod); ++entry) {
     964             :     Handle<Object> key = handle(table->KeyAt(entry), isolate);
     965        2540 :     if (key->IsTheHole(isolate)) continue;
     966        1270 :     new_table = OrderedHashSet::Add(isolate, new_table, key);
     967             :   }
     968             : 
     969           5 :   return new_table;
     970             : }
     971             : 
     972             : Handle<OrderedNameDictionary>
     973           5 : OrderedNameDictionaryHandler::AdjustRepresentation(
     974             :     Isolate* isolate, Handle<SmallOrderedNameDictionary> table) {
     975             :   Handle<OrderedNameDictionary> new_table =
     976           5 :       OrderedNameDictionary::Allocate(isolate, OrderedHashTableMinSize);
     977             :   int nof = table->NumberOfElements();
     978             :   int nod = table->NumberOfDeletedElements();
     979             : 
     980             :   // TODO(gsathya): Optimize the lookup to not re calc offsets. Also,
     981             :   // unhandlify this code as we preallocate the new backing store with
     982             :   // the proper capacity.
     983        1275 :   for (int entry = 0; entry < (nof + nod); ++entry) {
     984             :     Handle<Name> key(Name::cast(table->KeyAt(entry)), isolate);
     985        2540 :     if (key->IsTheHole(isolate)) continue;
     986             :     Handle<Object> value(table->ValueAt(entry), isolate);
     987        1270 :     PropertyDetails details = table->DetailsAt(entry);
     988             :     new_table =
     989        1270 :         OrderedNameDictionary::Add(isolate, new_table, key, value, details);
     990             :   }
     991             : 
     992           5 :   return new_table;
     993             : }
     994             : 
     995        5130 : Handle<HeapObject> OrderedHashMapHandler::Add(Isolate* isolate,
     996             :                                               Handle<HeapObject> table,
     997             :                                               Handle<Object> key,
     998             :                                               Handle<Object> value) {
     999       10260 :   if (table->IsSmallOrderedHashMap()) {
    1000             :     Handle<SmallOrderedHashMap> small_map =
    1001        1285 :         Handle<SmallOrderedHashMap>::cast(table);
    1002             :     MaybeHandle<SmallOrderedHashMap> new_map =
    1003        1285 :         SmallOrderedHashMap::Add(isolate, small_map, key, value);
    1004        2565 :     if (!new_map.is_null()) return new_map.ToHandleChecked();
    1005             : 
    1006             :     // We couldn't add to the small table, let's migrate to the
    1007             :     // big table.
    1008           5 :     table = OrderedHashMapHandler::AdjustRepresentation(isolate, small_map);
    1009             :   }
    1010             : 
    1011             :   DCHECK(table->IsOrderedHashMap());
    1012             :   return OrderedHashMap::Add(isolate, Handle<OrderedHashMap>::cast(table), key,
    1013        3850 :                              value);
    1014             : }
    1015             : 
    1016        5130 : Handle<HeapObject> OrderedHashSetHandler::Add(Isolate* isolate,
    1017             :                                               Handle<HeapObject> table,
    1018             :                                               Handle<Object> key) {
    1019       10260 :   if (table->IsSmallOrderedHashSet()) {
    1020             :     Handle<SmallOrderedHashSet> small_set =
    1021        1285 :         Handle<SmallOrderedHashSet>::cast(table);
    1022             :     MaybeHandle<SmallOrderedHashSet> new_set =
    1023        1285 :         SmallOrderedHashSet::Add(isolate, small_set, key);
    1024        2565 :     if (!new_set.is_null()) return new_set.ToHandleChecked();
    1025             : 
    1026             :     // We couldn't add to the small table, let's migrate to the
    1027             :     // big table.
    1028           5 :     table = OrderedHashSetHandler::AdjustRepresentation(isolate, small_set);
    1029             :   }
    1030             : 
    1031             :   DCHECK(table->IsOrderedHashSet());
    1032        3850 :   return OrderedHashSet::Add(isolate, Handle<OrderedHashSet>::cast(table), key);
    1033             : }
    1034             : 
    1035        5125 : Handle<HeapObject> OrderedNameDictionaryHandler::Add(Isolate* isolate,
    1036             :                                                      Handle<HeapObject> table,
    1037             :                                                      Handle<Name> key,
    1038             :                                                      Handle<Object> value,
    1039             :                                                      PropertyDetails details) {
    1040       10250 :   if (table->IsSmallOrderedNameDictionary()) {
    1041             :     Handle<SmallOrderedNameDictionary> small_dict =
    1042        1275 :         Handle<SmallOrderedNameDictionary>::cast(table);
    1043             :     MaybeHandle<SmallOrderedNameDictionary> new_dict =
    1044             :         SmallOrderedNameDictionary::Add(isolate, small_dict, key, value,
    1045        1275 :                                         details);
    1046        2545 :     if (!new_dict.is_null()) return new_dict.ToHandleChecked();
    1047             : 
    1048             :     // We couldn't add to the small table, let's migrate to the
    1049             :     // big table.
    1050             :     table =
    1051           5 :         OrderedNameDictionaryHandler::AdjustRepresentation(isolate, small_dict);
    1052             :   }
    1053             : 
    1054             :   DCHECK(table->IsOrderedNameDictionary());
    1055             :   return OrderedNameDictionary::Add(
    1056        3855 :       isolate, Handle<OrderedNameDictionary>::cast(table), key, value, details);
    1057             : }
    1058             : 
    1059           0 : void OrderedNameDictionaryHandler::SetEntry(Isolate* isolate, HeapObject table,
    1060             :                                             int entry, Object key, Object value,
    1061             :                                             PropertyDetails details) {
    1062             :   DisallowHeapAllocation no_gc;
    1063           0 :   if (table->IsSmallOrderedNameDictionary()) {
    1064             :     return SmallOrderedNameDictionary::cast(table)->SetEntry(
    1065           0 :         isolate, entry, key, value, details);
    1066             :   }
    1067             : 
    1068             :   DCHECK(table->IsOrderedNameDictionary());
    1069             :   return OrderedNameDictionary::cast(table)->SetEntry(isolate, entry, key,
    1070           0 :                                                       value, details);
    1071             : }
    1072             : 
    1073     5242885 : int OrderedNameDictionaryHandler::FindEntry(Isolate* isolate, HeapObject table,
    1074             :                                             Name key) {
    1075             :   DisallowHeapAllocation no_gc;
    1076     5242885 :   if (table->IsSmallOrderedNameDictionary()) {
    1077             :     int entry =
    1078     1295365 :         SmallOrderedNameDictionary::cast(table)->FindEntry(isolate, key);
    1079             :     return entry == SmallOrderedNameDictionary::kNotFound
    1080             :                ? OrderedNameDictionaryHandler::kNotFound
    1081     1295365 :                : entry;
    1082             :   }
    1083             : 
    1084             :   DCHECK(table->IsOrderedNameDictionary());
    1085     3947520 :   int entry = OrderedNameDictionary::cast(table)->FindEntry(isolate, key);
    1086             :   return entry == OrderedNameDictionary::kNotFound
    1087             :              ? OrderedNameDictionaryHandler::kNotFound
    1088     3947520 :              : entry;
    1089             : }
    1090             : 
    1091           0 : Object OrderedNameDictionaryHandler::ValueAt(HeapObject table, int entry) {
    1092           0 :   if (table->IsSmallOrderedNameDictionary()) {
    1093             :     return SmallOrderedNameDictionary::cast(table)->ValueAt(entry);
    1094             :   }
    1095             : 
    1096             :   DCHECK(table->IsOrderedNameDictionary());
    1097           0 :   return OrderedNameDictionary::cast(table)->ValueAt(entry);
    1098             : }
    1099             : 
    1100           0 : void OrderedNameDictionaryHandler::ValueAtPut(HeapObject table, int entry,
    1101             :                                               Object value) {
    1102           0 :   if (table->IsSmallOrderedNameDictionary()) {
    1103           0 :     return SmallOrderedNameDictionary::cast(table)->ValueAtPut(entry, value);
    1104             :   }
    1105             : 
    1106             :   DCHECK(table->IsOrderedNameDictionary());
    1107           0 :   OrderedNameDictionary::cast(table)->ValueAtPut(entry, value);
    1108             : }
    1109             : 
    1110           0 : PropertyDetails OrderedNameDictionaryHandler::DetailsAt(HeapObject table,
    1111             :                                                         int entry) {
    1112           0 :   if (table->IsSmallOrderedNameDictionary()) {
    1113           0 :     return SmallOrderedNameDictionary::cast(table)->DetailsAt(entry);
    1114             :   }
    1115             : 
    1116             :   DCHECK(table->IsOrderedNameDictionary());
    1117           0 :   return OrderedNameDictionary::cast(table)->DetailsAt(entry);
    1118             : }
    1119             : 
    1120           0 : void OrderedNameDictionaryHandler::DetailsAtPut(HeapObject table, int entry,
    1121             :                                                 PropertyDetails details) {
    1122           0 :   if (table->IsSmallOrderedNameDictionary()) {
    1123             :     return SmallOrderedNameDictionary::cast(table)->DetailsAtPut(entry,
    1124           0 :                                                                  details);
    1125             :   }
    1126             : 
    1127             :   DCHECK(table->IsOrderedNameDictionary());
    1128           0 :   OrderedNameDictionary::cast(table)->DetailsAtPut(entry, details);
    1129             : }
    1130             : 
    1131           0 : int OrderedNameDictionaryHandler::Hash(HeapObject table) {
    1132           0 :   if (table->IsSmallOrderedNameDictionary()) {
    1133             :     return SmallOrderedNameDictionary::cast(table)->Hash();
    1134             :   }
    1135             : 
    1136             :   DCHECK(table->IsOrderedNameDictionary());
    1137           0 :   return OrderedNameDictionary::cast(table)->Hash();
    1138             : }
    1139             : 
    1140           0 : void OrderedNameDictionaryHandler::SetHash(HeapObject table, int hash) {
    1141           0 :   if (table->IsSmallOrderedNameDictionary()) {
    1142           0 :     return SmallOrderedNameDictionary::cast(table)->SetHash(hash);
    1143             :   }
    1144             : 
    1145             :   DCHECK(table->IsOrderedNameDictionary());
    1146             :   OrderedNameDictionary::cast(table)->SetHash(hash);
    1147             : }
    1148             : 
    1149           0 : Name OrderedNameDictionaryHandler::KeyAt(HeapObject table, int entry) {
    1150           0 :   if (table->IsSmallOrderedNameDictionary()) {
    1151             :     return Name::cast(SmallOrderedNameDictionary::cast(table)->KeyAt(entry));
    1152             :   }
    1153             : 
    1154           0 :   return Name::cast(OrderedNameDictionary::cast(table)->KeyAt(entry));
    1155             : }
    1156             : 
    1157           0 : int OrderedNameDictionaryHandler::NumberOfElements(HeapObject table) {
    1158           0 :   if (table->IsSmallOrderedNameDictionary()) {
    1159             :     return SmallOrderedNameDictionary::cast(table)->NumberOfElements();
    1160             :   }
    1161             : 
    1162           0 :   return OrderedNameDictionary::cast(table)->NumberOfElements();
    1163             : }
    1164             : 
    1165           5 : int OrderedNameDictionaryHandler::Capacity(HeapObject table) {
    1166           5 :   if (table->IsSmallOrderedNameDictionary()) {
    1167             :     return SmallOrderedNameDictionary::cast(table)->Capacity();
    1168             :   }
    1169             : 
    1170          10 :   return OrderedNameDictionary::cast(table)->Capacity();
    1171             : }
    1172             : 
    1173           0 : Handle<HeapObject> OrderedNameDictionaryHandler::Shrink(
    1174             :     Isolate* isolate, Handle<HeapObject> table) {
    1175           0 :   if (table->IsSmallOrderedNameDictionary()) {
    1176             :     Handle<SmallOrderedNameDictionary> small_dict =
    1177           0 :         Handle<SmallOrderedNameDictionary>::cast(table);
    1178           0 :     return SmallOrderedNameDictionary::Shrink(isolate, small_dict);
    1179             :   }
    1180             : 
    1181             :   Handle<OrderedNameDictionary> large_dict =
    1182           0 :       Handle<OrderedNameDictionary>::cast(table);
    1183           0 :   return OrderedNameDictionary::Shrink(isolate, large_dict);
    1184             : }
    1185             : 
    1186           0 : Handle<HeapObject> OrderedNameDictionaryHandler::DeleteEntry(
    1187             :     Isolate* isolate, Handle<HeapObject> table, int entry) {
    1188             :   DisallowHeapAllocation no_gc;
    1189           0 :   if (table->IsSmallOrderedNameDictionary()) {
    1190             :     Handle<SmallOrderedNameDictionary> small_dict =
    1191           0 :         Handle<SmallOrderedNameDictionary>::cast(table);
    1192           0 :     return SmallOrderedNameDictionary::DeleteEntry(isolate, small_dict, entry);
    1193             :   }
    1194             : 
    1195             :   Handle<OrderedNameDictionary> large_dict =
    1196           0 :       Handle<OrderedNameDictionary>::cast(table);
    1197           0 :   return OrderedNameDictionary::DeleteEntry(isolate, large_dict, entry);
    1198             : }
    1199             : 
    1200             : template <class Derived, class TableType>
    1201         458 : void OrderedHashTableIterator<Derived, TableType>::Transition() {
    1202             :   DisallowHeapAllocation no_allocation;
    1203         458 :   TableType table = TableType::cast(this->table());
    1204         901 :   if (!table->IsObsolete()) return;
    1205             : 
    1206          15 :   int index = Smi::ToInt(this->index());
    1207          75 :   while (table->IsObsolete()) {
    1208          45 :     TableType next_table = table->NextTable();
    1209             : 
    1210          45 :     if (index > 0) {
    1211          45 :       int nod = table->NumberOfDeletedElements();
    1212             : 
    1213          45 :       if (nod == TableType::kClearedTableSentinel) {
    1214             :         index = 0;
    1215             :       } else {
    1216             :         int old_index = index;
    1217          15 :         for (int i = 0; i < nod; ++i) {
    1218          15 :           int removed_index = table->RemovedIndexAt(i);
    1219          15 :           if (removed_index >= old_index) break;
    1220          15 :           --index;
    1221             :         }
    1222             :       }
    1223             :     }
    1224             : 
    1225          45 :     table = next_table;
    1226             :   }
    1227             : 
    1228          15 :   set_table(table);
    1229          15 :   set_index(Smi::FromInt(index));
    1230             : }
    1231             : 
    1232             : template <class Derived, class TableType>
    1233         458 : bool OrderedHashTableIterator<Derived, TableType>::HasMore() {
    1234             :   DisallowHeapAllocation no_allocation;
    1235         458 :   ReadOnlyRoots ro_roots = GetReadOnlyRoots();
    1236             : 
    1237         458 :   Transition();
    1238             : 
    1239         458 :   TableType table = TableType::cast(this->table());
    1240         458 :   int index = Smi::ToInt(this->index());
    1241         458 :   int used_capacity = table->UsedCapacity();
    1242             : 
    1243        1384 :   while (index < used_capacity && table->KeyAt(index)->IsTheHole(ro_roots)) {
    1244          40 :     index++;
    1245             :   }
    1246             : 
    1247         458 :   set_index(Smi::FromInt(index));
    1248             : 
    1249         458 :   if (index < used_capacity) return true;
    1250             : 
    1251          70 :   set_table(TableType::GetEmpty(ro_roots));
    1252          70 :   return false;
    1253             : }
    1254             : 
    1255             : template bool
    1256             : OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::HasMore();
    1257             : 
    1258             : template void
    1259             : OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::MoveNext();
    1260             : 
    1261             : template Object
    1262             : OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::CurrentKey();
    1263             : 
    1264             : template void
    1265             : OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::Transition();
    1266             : 
    1267             : template bool
    1268             : OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::HasMore();
    1269             : 
    1270             : template void
    1271             : OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::MoveNext();
    1272             : 
    1273             : template Object
    1274             : OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::CurrentKey();
    1275             : 
    1276             : template void
    1277             : OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::Transition();
    1278             : 
    1279             : }  // namespace internal
    1280      178779 : }  // namespace v8

Generated by: LCOV version 1.10