LCOV - code coverage report
Current view: top level - src/objects - ordered-hash-table.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 328 390 84.1 %
Date: 2019-03-21 Functions: 73 95 76.8 %

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

Generated by: LCOV version 1.10