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/isolate.h" 8 #include "src/objects-inl.h" 9 #include "src/objects/js-collection-inl.h" 10 #include "src/objects/ordered-hash-table-inl.h" 11 12 namespace v8 { 13 namespace internal { 14 15 template <class Derived, int entrysize> 16 Handle<Derived> OrderedHashTable<Derived, entrysize>::Allocate( 17 Isolate* isolate, int capacity, PretenureFlag pretenure) { 18 // Capacity must be a power of two, since we depend on being able 19 // to divide and multiple by 2 (kLoadFactor) to derive capacity 20 // from number of buckets. If we decide to change kLoadFactor 21 // to something other than 2, capacity should be stored as another 22 // field of this object. 23 capacity = base::bits::RoundUpToPowerOfTwo32(Max(kMinCapacity, capacity)); 24 if (capacity > kMaxCapacity) { 25 isolate->heap()->FatalProcessOutOfMemory("invalid table size"); 26 } 27 int num_buckets = capacity / kLoadFactor; 28 Handle<FixedArray> backing_store = isolate->factory()->NewFixedArrayWithMap( 29 static_cast<Heap::RootListIndex>(Derived::GetMapRootIndex()), 30 kHashTableStartIndex + num_buckets + (capacity * kEntrySize), pretenure); 31 Handle<Derived> table = Handle<Derived>::cast(backing_store); 32 for (int i = 0; i < num_buckets; ++i) { 33 table->set(kHashTableStartIndex + i, Smi::FromInt(kNotFound)); 34 } 35 table->SetNumberOfBuckets(num_buckets); 36 table->SetNumberOfElements(0); 37 table->SetNumberOfDeletedElements(0); 38 return table; 39 } 40 41 template <class Derived, int entrysize> 42 Handle<Derived> OrderedHashTable<Derived, entrysize>::EnsureGrowable( 43 Isolate* isolate, Handle<Derived> table) { 44 DCHECK(!table->IsObsolete()); 45 46 int nof = table->NumberOfElements(); 47 int nod = table->NumberOfDeletedElements(); 48 int capacity = table->Capacity(); 49 if ((nof + nod) < capacity) return table; 50 // Don't need to grow if we can simply clear out deleted entries instead. 51 // Note that we can't compact in place, though, so we always allocate 52 // a new table. 53 return Rehash(isolate, table, 54 (nod < (capacity >> 1)) ? capacity << 1 : capacity); 55 } 56 57 template <class Derived, int entrysize> 58 Handle<Derived> OrderedHashTable<Derived, entrysize>::Shrink( 59 Isolate* isolate, Handle<Derived> table) { 60 DCHECK(!table->IsObsolete()); 61 62 int nof = table->NumberOfElements(); 63 int capacity = table->Capacity(); 64 if (nof >= (capacity >> 2)) return table; 65 return Rehash(isolate, table, capacity / 2); 66 } 67 68 template <class Derived, int entrysize> 69 Handle<Derived> OrderedHashTable<Derived, entrysize>::Clear( 70 Isolate* isolate, Handle<Derived> table) { 71 DCHECK(!table->IsObsolete()); 72 73 Handle<Derived> new_table = Allocate( 74 isolate, kMinCapacity, Heap::InNewSpace(*table) ? NOT_TENURED : TENURED); 75 76 table->SetNextTable(*new_table); 77 table->SetNumberOfDeletedElements(kClearedTableSentinel); 78 79 return new_table; 80 } 81 82 template <class Derived, int entrysize> 83 bool OrderedHashTable<Derived, entrysize>::HasKey(Isolate* isolate, 84 Derived* table, Object* key) { 85 DCHECK((entrysize == 1 && table->IsOrderedHashSet()) || 86 (entrysize == 2 && table->IsOrderedHashMap())); 87 DisallowHeapAllocation no_gc; 88 int entry = table->FindEntry(isolate, key); 89 return entry != kNotFound; 90 } 91 92 Handle<OrderedHashSet> OrderedHashSet::Add(Isolate* isolate, 93 Handle<OrderedHashSet> table, 94 Handle<Object> key) { 95 int hash = key->GetOrCreateHash(isolate)->value(); 96 int entry = table->HashToEntry(hash); 97 // Walk the chain of the bucket and try finding the key. 98 while (entry != kNotFound) { 99 Object* candidate_key = table->KeyAt(entry); 100 // Do not add if we have the key already 101 if (candidate_key->SameValueZero(*key)) return table; 102 entry = table->NextChainEntry(entry); 103 } 104 105 table = OrderedHashSet::EnsureGrowable(isolate, table); 106 // Read the existing bucket values. 107 int bucket = table->HashToBucket(hash); 108 int previous_entry = table->HashToEntry(hash); 109 int nof = table->NumberOfElements(); 110 // Insert a new entry at the end, 111 int new_entry = nof + table->NumberOfDeletedElements(); 112 int new_index = table->EntryToIndex(new_entry); 113 table->set(new_index, *key); 114 table->set(new_index + kChainOffset, Smi::FromInt(previous_entry)); 115 // and point the bucket to the new entry. 116 table->set(kHashTableStartIndex + bucket, Smi::FromInt(new_entry)); 117 table->SetNumberOfElements(nof + 1); 118 return table; 119 } 120 121 Handle<FixedArray> OrderedHashSet::ConvertToKeysArray( 122 Isolate* isolate, Handle<OrderedHashSet> table, GetKeysConversion convert) { 123 int length = table->NumberOfElements(); 124 int nof_buckets = table->NumberOfBuckets(); 125 // Convert the dictionary to a linear list. 126 Handle<FixedArray> result = Handle<FixedArray>::cast(table); 127 // From this point on table is no longer a valid OrderedHashSet. 128 result->set_map(ReadOnlyRoots(isolate).fixed_array_map()); 129 int const kMaxStringTableEntries = 130 isolate->heap()->MaxNumberToStringCacheSize(); 131 for (int i = 0; i < length; i++) { 132 int index = kHashTableStartIndex + nof_buckets + (i * kEntrySize); 133 Object* key = table->get(index); 134 if (convert == GetKeysConversion::kConvertToString) { 135 uint32_t index_value; 136 if (key->ToArrayIndex(&index_value)) { 137 // Avoid trashing the Number2String cache if indices get very large. 138 bool use_cache = i < kMaxStringTableEntries; 139 key = *isolate->factory()->Uint32ToString(index_value, use_cache); 140 } else { 141 CHECK(key->IsName()); 142 } 143 } 144 result->set(i, key); 145 } 146 return FixedArray::ShrinkOrEmpty(isolate, result, length); 147 } 148 149 HeapObject* OrderedHashSet::GetEmpty(ReadOnlyRoots ro_roots) { 150 return ro_roots.empty_ordered_hash_set(); 151 } 152 153 HeapObject* OrderedHashMap::GetEmpty(ReadOnlyRoots ro_roots) { 154 return ro_roots.empty_ordered_hash_map(); 155 } 156 157 template <class Derived, int entrysize> 158 Handle<Derived> OrderedHashTable<Derived, entrysize>::Rehash( 159 Isolate* isolate, Handle<Derived> table, int new_capacity) { 160 DCHECK(!table->IsObsolete()); 161 162 Handle<Derived> new_table = Allocate( 163 isolate, new_capacity, Heap::InNewSpace(*table) ? NOT_TENURED : TENURED); 164 int nof = table->NumberOfElements(); 165 int nod = table->NumberOfDeletedElements(); 166 int new_buckets = new_table->NumberOfBuckets(); 167 int new_entry = 0; 168 int removed_holes_index = 0; 169 170 DisallowHeapAllocation no_gc; 171 for (int old_entry = 0; old_entry < (nof + nod); ++old_entry) { 172 Object* key = table->KeyAt(old_entry); 173 if (key->IsTheHole(isolate)) { 174 table->SetRemovedIndexAt(removed_holes_index++, old_entry); 175 continue; 176 } 177 178 Object* hash = key->GetHash(); 179 int bucket = Smi::ToInt(hash) & (new_buckets - 1); 180 Object* chain_entry = new_table->get(kHashTableStartIndex + bucket); 181 new_table->set(kHashTableStartIndex + bucket, Smi::FromInt(new_entry)); 182 int new_index = new_table->EntryToIndex(new_entry); 183 int old_index = table->EntryToIndex(old_entry); 184 for (int i = 0; i < entrysize; ++i) { 185 Object* value = table->get(old_index + i); 186 new_table->set(new_index + i, value); 187 } 188 new_table->set(new_index + kChainOffset, chain_entry); 189 ++new_entry; 190 } 191 192 DCHECK_EQ(nod, removed_holes_index); 193 194 new_table->SetNumberOfElements(nof); 195 table->SetNextTable(*new_table); 196 197 return new_table; 198 } 199 200 template <class Derived, int entrysize> 201 bool OrderedHashTable<Derived, entrysize>::Delete(Isolate* isolate, 202 Derived* table, Object* key) { 203 DisallowHeapAllocation no_gc; 204 int entry = table->FindEntry(isolate, key); 205 if (entry == kNotFound) return false; 206 207 int nof = table->NumberOfElements(); 208 int nod = table->NumberOfDeletedElements(); 209 int index = table->EntryToIndex(entry); 210 211 Object* hole = ReadOnlyRoots(isolate).the_hole_value(); 212 for (int i = 0; i < entrysize; ++i) { 213 table->set(index + i, hole); 214 } 215 216 table->SetNumberOfElements(nof - 1); 217 table->SetNumberOfDeletedElements(nod + 1); 218 219 return true; 220 } 221 222 Object* OrderedHashMap::GetHash(Isolate* isolate, Object* key) { 223 DisallowHeapAllocation no_gc; 224 225 Object* hash = key->GetHash(); 226 // If the object does not have an identity hash, it was never used as a key 227 if (hash->IsUndefined(isolate)) return Smi::FromInt(-1); 228 DCHECK(hash->IsSmi()); 229 DCHECK_GE(Smi::cast(hash)->value(), 0); 230 return hash; 231 } 232 233 Handle<OrderedHashMap> OrderedHashMap::Add(Isolate* isolate, 234 Handle<OrderedHashMap> table, 235 Handle<Object> key, 236 Handle<Object> value) { 237 int hash = key->GetOrCreateHash(isolate)->value(); 238 int entry = table->HashToEntry(hash); 239 // Walk the chain of the bucket and try finding the key. 240 { 241 DisallowHeapAllocation no_gc; 242 Object* raw_key = *key; 243 while (entry != kNotFound) { 244 Object* candidate_key = table->KeyAt(entry); 245 // Do not add if we have the key already 246 if (candidate_key->SameValueZero(raw_key)) return table; 247 entry = table->NextChainEntry(entry); 248 } 249 } 250 251 table = OrderedHashMap::EnsureGrowable(isolate, table); 252 // Read the existing bucket values. 253 int bucket = table->HashToBucket(hash); 254 int previous_entry = table->HashToEntry(hash); 255 int nof = table->NumberOfElements(); 256 // Insert a new entry at the end, 257 int new_entry = nof + table->NumberOfDeletedElements(); 258 int new_index = table->EntryToIndex(new_entry); 259 table->set(new_index, *key); 260 table->set(new_index + kValueOffset, *value); 261 table->set(new_index + kChainOffset, Smi::FromInt(previous_entry)); 262 // and point the bucket to the new entry. 263 table->set(kHashTableStartIndex + bucket, Smi::FromInt(new_entry)); 264 table->SetNumberOfElements(nof + 1); 265 return table; 266 } 267 268 template Handle<OrderedHashSet> OrderedHashTable<OrderedHashSet, 1>::Allocate( 269 Isolate* isolate, int capacity, PretenureFlag pretenure); 270 271 template Handle<OrderedHashSet> 272 OrderedHashTable<OrderedHashSet, 1>::EnsureGrowable( 273 Isolate* isolate, Handle<OrderedHashSet> table); 274 275 template Handle<OrderedHashSet> OrderedHashTable<OrderedHashSet, 1>::Shrink( 276 Isolate* isolate, Handle<OrderedHashSet> table); 277 278 template Handle<OrderedHashSet> OrderedHashTable<OrderedHashSet, 1>::Clear( 279 Isolate* isolate, Handle<OrderedHashSet> table); 280 281 template bool OrderedHashTable<OrderedHashSet, 1>::HasKey(Isolate* isolate, 282 OrderedHashSet* table, 283 Object* key); 284 285 template bool OrderedHashTable<OrderedHashSet, 1>::Delete(Isolate* isolate, 286 OrderedHashSet* table, 287 Object* key); 288 289 template Handle<OrderedHashMap> OrderedHashTable<OrderedHashMap, 2>::Allocate( 290 Isolate* isolate, int capacity, PretenureFlag pretenure); 291 292 template Handle<OrderedHashMap> 293 OrderedHashTable<OrderedHashMap, 2>::EnsureGrowable( 294 Isolate* isolate, Handle<OrderedHashMap> table); 295 296 template Handle<OrderedHashMap> OrderedHashTable<OrderedHashMap, 2>::Shrink( 297 Isolate* isolate, Handle<OrderedHashMap> table); 298 299 template Handle<OrderedHashMap> OrderedHashTable<OrderedHashMap, 2>::Clear( 300 Isolate* isolate, Handle<OrderedHashMap> table); 301 302 template bool OrderedHashTable<OrderedHashMap, 2>::HasKey(Isolate* isolate, 303 OrderedHashMap* table, 304 Object* key); 305 306 template bool OrderedHashTable<OrderedHashMap, 2>::Delete(Isolate* isolate, 307 OrderedHashMap* table, 308 Object* key); 309 310 template <> 311 Handle<SmallOrderedHashSet> 312 SmallOrderedHashTable<SmallOrderedHashSet>::Allocate(Isolate* isolate, 313 int capacity, 314 PretenureFlag pretenure) { 315 return isolate->factory()->NewSmallOrderedHashSet(capacity, pretenure); 316 } 317 318 template <> 319 Handle<SmallOrderedHashMap> 320 SmallOrderedHashTable<SmallOrderedHashMap>::Allocate(Isolate* isolate, 321 int capacity, 322 PretenureFlag pretenure) { 323 return isolate->factory()->NewSmallOrderedHashMap(capacity, pretenure); 324 } 325 326 template <class Derived> 327 void SmallOrderedHashTable<Derived>::Initialize(Isolate* isolate, 328 int capacity) { 329 DisallowHeapAllocation no_gc; 330 int num_buckets = capacity / kLoadFactor; 331 int num_chains = capacity; 332 333 SetNumberOfBuckets(num_buckets); 334 SetNumberOfElements(0); 335 SetNumberOfDeletedElements(0); 336 337 Address hashtable_start = GetHashTableStartAddress(capacity); 338 memset(reinterpret_cast<byte*>(hashtable_start), kNotFound, 339 num_buckets + num_chains); 340 341 if (Heap::InNewSpace(this)) { 342 MemsetPointer(RawField(this, kDataTableStartOffset), 343 ReadOnlyRoots(isolate).the_hole_value(), 344 capacity * Derived::kEntrySize); 345 } else { 346 for (int i = 0; i < capacity; i++) { 347 for (int j = 0; j < Derived::kEntrySize; j++) { 348 SetDataEntry(i, j, ReadOnlyRoots(isolate).the_hole_value()); 349 } 350 } 351 } 352 353 #ifdef DEBUG 354 for (int i = 0; i < num_buckets; ++i) { 355 DCHECK_EQ(kNotFound, GetFirstEntry(i)); 356 } 357 358 for (int i = 0; i < num_chains; ++i) { 359 DCHECK_EQ(kNotFound, GetNextEntry(i)); 360 } 361 362 for (int i = 0; i < capacity; ++i) { 363 for (int j = 0; j < Derived::kEntrySize; j++) { 364 DCHECK_EQ(ReadOnlyRoots(isolate).the_hole_value(), GetDataEntry(i, j)); 365 } 366 } 367 #endif // DEBUG 368 } 369 370 MaybeHandle<SmallOrderedHashSet> SmallOrderedHashSet::Add( 371 Isolate* isolate, Handle<SmallOrderedHashSet> table, Handle<Object> key) { 372 if (table->HasKey(isolate, key)) return table; 373 374 if (table->UsedCapacity() >= table->Capacity()) { 375 MaybeHandle<SmallOrderedHashSet> new_table = 376 SmallOrderedHashSet::Grow(isolate, table); 377 if (!new_table.ToHandle(&table)) { 378 return MaybeHandle<SmallOrderedHashSet>(); 379 } 380 } 381 382 int hash = key->GetOrCreateHash(isolate)->value(); 383 int nof = table->NumberOfElements(); 384 385 // Read the existing bucket values. 386 int bucket = table->HashToBucket(hash); 387 int previous_entry = table->HashToFirstEntry(hash); 388 389 // Insert a new entry at the end, 390 int new_entry = nof + table->NumberOfDeletedElements(); 391 392 table->SetDataEntry(new_entry, SmallOrderedHashSet::kKeyIndex, *key); 393 table->SetFirstEntry(bucket, new_entry); 394 table->SetNextEntry(new_entry, previous_entry); 395 396 // and update book keeping. 397 table->SetNumberOfElements(nof + 1); 398 399 return table; 400 } 401 402 MaybeHandle<SmallOrderedHashMap> SmallOrderedHashMap::Add( 403 Isolate* isolate, Handle<SmallOrderedHashMap> table, Handle<Object> key, 404 Handle<Object> value) { 405 if (table->HasKey(isolate, key)) return table; 406 407 if (table->UsedCapacity() >= table->Capacity()) { 408 MaybeHandle<SmallOrderedHashMap> new_table = 409 SmallOrderedHashMap::Grow(isolate, table); 410 if (!new_table.ToHandle(&table)) { 411 return MaybeHandle<SmallOrderedHashMap>(); 412 } 413 } 414 415 int hash = key->GetOrCreateHash(isolate)->value(); 416 int nof = table->NumberOfElements(); 417 418 // Read the existing bucket values. 419 int bucket = table->HashToBucket(hash); 420 int previous_entry = table->HashToFirstEntry(hash); 421 422 // Insert a new entry at the end, 423 int new_entry = nof + table->NumberOfDeletedElements(); 424 425 table->SetDataEntry(new_entry, SmallOrderedHashMap::kValueIndex, *value); 426 table->SetDataEntry(new_entry, SmallOrderedHashMap::kKeyIndex, *key); 427 table->SetFirstEntry(bucket, new_entry); 428 table->SetNextEntry(new_entry, previous_entry); 429 430 // and update book keeping. 431 table->SetNumberOfElements(nof + 1); 432 433 return table; 434 } 435 436 template <class Derived> 437 bool SmallOrderedHashTable<Derived>::HasKey(Isolate* isolate, 438 Handle<Object> key) { 439 DisallowHeapAllocation no_gc; 440 return FindEntry(isolate, *key) != kNotFound; 441 } 442 443 template <class Derived> 444 bool SmallOrderedHashTable<Derived>::Delete(Isolate* isolate, Derived* table, 445 Object* key) { 446 DisallowHeapAllocation no_gc; 447 int entry = table->FindEntry(isolate, key); 448 if (entry == kNotFound) return false; 449 450 int nof = table->NumberOfElements(); 451 int nod = table->NumberOfDeletedElements(); 452 453 Object* hole = ReadOnlyRoots(isolate).the_hole_value(); 454 for (int j = 0; j < Derived::kEntrySize; j++) { 455 table->SetDataEntry(entry, j, hole); 456 } 457 458 table->SetNumberOfElements(nof - 1); 459 table->SetNumberOfDeletedElements(nod + 1); 460 461 return true; 462 } 463 464 template <class Derived> 465 Handle<Derived> SmallOrderedHashTable<Derived>::Rehash(Isolate* isolate, 466 Handle<Derived> table, 467 int new_capacity) { 468 DCHECK_GE(kMaxCapacity, new_capacity); 469 470 Handle<Derived> new_table = SmallOrderedHashTable<Derived>::Allocate( 471 isolate, new_capacity, Heap::InNewSpace(*table) ? NOT_TENURED : TENURED); 472 int nof = table->NumberOfElements(); 473 int nod = table->NumberOfDeletedElements(); 474 int new_entry = 0; 475 476 { 477 DisallowHeapAllocation no_gc; 478 for (int old_entry = 0; old_entry < (nof + nod); ++old_entry) { 479 Object* key = table->KeyAt(old_entry); 480 if (key->IsTheHole(isolate)) continue; 481 482 int hash = Smi::ToInt(key->GetHash()); 483 int bucket = new_table->HashToBucket(hash); 484 int chain = new_table->GetFirstEntry(bucket); 485 486 new_table->SetFirstEntry(bucket, new_entry); 487 new_table->SetNextEntry(new_entry, chain); 488 489 for (int i = 0; i < Derived::kEntrySize; ++i) { 490 Object* value = table->GetDataEntry(old_entry, i); 491 new_table->SetDataEntry(new_entry, i, value); 492 } 493 494 ++new_entry; 495 } 496 497 new_table->SetNumberOfElements(nof); 498 } 499 return new_table; 500 } 501 502 template <class Derived> 503 MaybeHandle<Derived> SmallOrderedHashTable<Derived>::Grow( 504 Isolate* isolate, Handle<Derived> table) { 505 int capacity = table->Capacity(); 506 int new_capacity = capacity; 507 508 // Don't need to grow if we can simply clear out deleted entries instead. 509 // TODO(gsathya): Compact in place, instead of allocating a new table. 510 if (table->NumberOfDeletedElements() < (capacity >> 1)) { 511 new_capacity = capacity << 1; 512 513 // The max capacity of our table is 254. We special case for 256 to 514 // account for our growth strategy, otherwise we would only fill up 515 // to 128 entries in our table. 516 if (new_capacity == kGrowthHack) { 517 new_capacity = kMaxCapacity; 518 } 519 520 // We need to migrate to a bigger hash table. 521 if (new_capacity > kMaxCapacity) { 522 return MaybeHandle<Derived>(); 523 } 524 } 525 526 return Rehash(isolate, table, new_capacity); 527 } 528 529 template bool SmallOrderedHashTable<SmallOrderedHashSet>::HasKey( 530 Isolate* isolate, Handle<Object> key); 531 template Handle<SmallOrderedHashSet> 532 SmallOrderedHashTable<SmallOrderedHashSet>::Rehash( 533 Isolate* isolate, Handle<SmallOrderedHashSet> table, int new_capacity); 534 template MaybeHandle<SmallOrderedHashSet> 535 SmallOrderedHashTable<SmallOrderedHashSet>::Grow( 536 Isolate* isolate, Handle<SmallOrderedHashSet> table); 537 template void SmallOrderedHashTable<SmallOrderedHashSet>::Initialize( 538 Isolate* isolate, int capacity); 539 540 template bool SmallOrderedHashTable<SmallOrderedHashMap>::HasKey( 541 Isolate* isolate, Handle<Object> key); 542 template Handle<SmallOrderedHashMap> 543 SmallOrderedHashTable<SmallOrderedHashMap>::Rehash( 544 Isolate* isolate, Handle<SmallOrderedHashMap> table, int new_capacity); 545 template MaybeHandle<SmallOrderedHashMap> 546 SmallOrderedHashTable<SmallOrderedHashMap>::Grow( 547 Isolate* isolate, Handle<SmallOrderedHashMap> table); 548 template void SmallOrderedHashTable<SmallOrderedHashMap>::Initialize( 549 Isolate* isolate, int capacity); 550 551 template bool SmallOrderedHashTable<SmallOrderedHashMap>::Delete( 552 Isolate* isolate, SmallOrderedHashMap* table, Object* key); 553 template bool SmallOrderedHashTable<SmallOrderedHashSet>::Delete( 554 Isolate* isolate, SmallOrderedHashSet* table, Object* key); 555 556 template <class SmallTable, class LargeTable> 557 Handle<HeapObject> OrderedHashTableHandler<SmallTable, LargeTable>::Allocate( 558 Isolate* isolate, int capacity) { 559 if (capacity < SmallTable::kMaxCapacity) { 560 return SmallTable::Allocate(isolate, capacity); 561 } 562 563 return LargeTable::Allocate(isolate, capacity); 564 } 565 566 template Handle<HeapObject> 567 OrderedHashTableHandler<SmallOrderedHashSet, OrderedHashSet>::Allocate( 568 Isolate* isolate, int capacity); 569 template Handle<HeapObject> 570 OrderedHashTableHandler<SmallOrderedHashMap, OrderedHashMap>::Allocate( 571 Isolate* isolate, int capacity); 572 573 template <class SmallTable, class LargeTable> 574 bool OrderedHashTableHandler<SmallTable, LargeTable>::Delete( 575 Handle<HeapObject> table, Handle<Object> key) { 576 if (SmallTable::Is(table)) { 577 return SmallTable::Delete(Handle<SmallTable>::cast(table), key); 578 } 579 580 DCHECK(LargeTable::Is(table)); 581 // Note: Once we migrate to the a big hash table, we never migrate 582 // down to a smaller hash table. 583 return LargeTable::Delete(Handle<LargeTable>::cast(table), key); 584 } 585 586 template <class SmallTable, class LargeTable> 587 bool OrderedHashTableHandler<SmallTable, LargeTable>::HasKey( 588 Isolate* isolate, Handle<HeapObject> table, Handle<Object> key) { 589 if (SmallTable::Is(table)) { 590 return Handle<SmallTable>::cast(table)->HasKey(isolate, key); 591 } 592 593 DCHECK(LargeTable::Is(table)); 594 return LargeTable::HasKey(isolate, LargeTable::cast(*table), *key); 595 } 596 597 template bool 598 OrderedHashTableHandler<SmallOrderedHashSet, OrderedHashSet>::HasKey( 599 Isolate* isolate, Handle<HeapObject> table, Handle<Object> key); 600 template bool 601 OrderedHashTableHandler<SmallOrderedHashMap, OrderedHashMap>::HasKey( 602 Isolate* isolate, Handle<HeapObject> table, Handle<Object> key); 603 604 Handle<OrderedHashMap> OrderedHashMapHandler::AdjustRepresentation( 605 Isolate* isolate, Handle<SmallOrderedHashMap> table) { 606 Handle<OrderedHashMap> new_table = 607 OrderedHashMap::Allocate(isolate, OrderedHashTableMinSize); 608 int nof = table->NumberOfElements(); 609 int nod = table->NumberOfDeletedElements(); 610 611 // TODO(gsathya): Optimize the lookup to not re calc offsets. Also, 612 // unhandlify this code as we preallocate the new backing store with 613 // the proper capacity. 614 for (int entry = 0; entry < (nof + nod); ++entry) { 615 Handle<Object> key = handle(table->KeyAt(entry), isolate); 616 if (key->IsTheHole(isolate)) continue; 617 Handle<Object> value = handle( 618 table->GetDataEntry(entry, SmallOrderedHashMap::kValueIndex), isolate); 619 new_table = OrderedHashMap::Add(isolate, new_table, key, value); 620 } 621 622 return new_table; 623 } 624 625 Handle<OrderedHashSet> OrderedHashSetHandler::AdjustRepresentation( 626 Isolate* isolate, Handle<SmallOrderedHashSet> table) { 627 Handle<OrderedHashSet> new_table = 628 OrderedHashSet::Allocate(isolate, OrderedHashTableMinSize); 629 int nof = table->NumberOfElements(); 630 int nod = table->NumberOfDeletedElements(); 631 632 // TODO(gsathya): Optimize the lookup to not re calc offsets. Also, 633 // unhandlify this code as we preallocate the new backing store with 634 // the proper capacity. 635 for (int entry = 0; entry < (nof + nod); ++entry) { 636 Handle<Object> key = handle(table->KeyAt(entry), isolate); 637 if (key->IsTheHole(isolate)) continue; 638 new_table = OrderedHashSet::Add(isolate, new_table, key); 639 } 640 641 return new_table; 642 } 643 644 Handle<HeapObject> OrderedHashMapHandler::Add(Isolate* isolate, 645 Handle<HeapObject> table, 646 Handle<Object> key, 647 Handle<Object> value) { 648 if (table->IsSmallOrderedHashMap()) { 649 Handle<SmallOrderedHashMap> small_map = 650 Handle<SmallOrderedHashMap>::cast(table); 651 MaybeHandle<SmallOrderedHashMap> new_map = 652 SmallOrderedHashMap::Add(isolate, small_map, key, value); 653 if (!new_map.is_null()) return new_map.ToHandleChecked(); 654 655 // We couldn't add to the small table, let's migrate to the 656 // big table. 657 table = OrderedHashMapHandler::AdjustRepresentation(isolate, small_map); 658 } 659 660 DCHECK(table->IsOrderedHashMap()); 661 return OrderedHashMap::Add(isolate, Handle<OrderedHashMap>::cast(table), key, 662 value); 663 } 664 665 Handle<HeapObject> OrderedHashSetHandler::Add(Isolate* isolate, 666 Handle<HeapObject> table, 667 Handle<Object> key) { 668 if (table->IsSmallOrderedHashSet()) { 669 Handle<SmallOrderedHashSet> small_set = 670 Handle<SmallOrderedHashSet>::cast(table); 671 MaybeHandle<SmallOrderedHashSet> new_set = 672 SmallOrderedHashSet::Add(isolate, small_set, key); 673 if (!new_set.is_null()) return new_set.ToHandleChecked(); 674 675 // We couldn't add to the small table, let's migrate to the 676 // big table. 677 table = OrderedHashSetHandler::AdjustRepresentation(isolate, small_set); 678 } 679 680 DCHECK(table->IsOrderedHashSet()); 681 return OrderedHashSet::Add(isolate, Handle<OrderedHashSet>::cast(table), key); 682 } 683 684 template <class Derived, class TableType> 685 void OrderedHashTableIterator<Derived, TableType>::Transition() { 686 DisallowHeapAllocation no_allocation; 687 TableType* table = TableType::cast(this->table()); 688 if (!table->IsObsolete()) return; 689 690 int index = Smi::ToInt(this->index()); 691 while (table->IsObsolete()) { 692 TableType* next_table = table->NextTable(); 693 694 if (index > 0) { 695 int nod = table->NumberOfDeletedElements(); 696 697 if (nod == TableType::kClearedTableSentinel) { 698 index = 0; 699 } else { 700 int old_index = index; 701 for (int i = 0; i < nod; ++i) { 702 int removed_index = table->RemovedIndexAt(i); 703 if (removed_index >= old_index) break; 704 --index; 705 } 706 } 707 } 708 709 table = next_table; 710 } 711 712 set_table(table); 713 set_index(Smi::FromInt(index)); 714 } 715 716 template <class Derived, class TableType> 717 bool OrderedHashTableIterator<Derived, TableType>::HasMore() { 718 DisallowHeapAllocation no_allocation; 719 ReadOnlyRoots ro_roots = GetReadOnlyRoots(); 720 721 Transition(); 722 723 TableType* table = TableType::cast(this->table()); 724 int index = Smi::ToInt(this->index()); 725 int used_capacity = table->UsedCapacity(); 726 727 while (index < used_capacity && table->KeyAt(index)->IsTheHole(ro_roots)) { 728 index++; 729 } 730 731 set_index(Smi::FromInt(index)); 732 733 if (index < used_capacity) return true; 734 735 set_table(TableType::GetEmpty(ro_roots)); 736 return false; 737 } 738 739 template bool 740 OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::HasMore(); 741 742 template void 743 OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::MoveNext(); 744 745 template Object* 746 OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::CurrentKey(); 747 748 template void 749 OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::Transition(); 750 751 template bool 752 OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::HasMore(); 753 754 template void 755 OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::MoveNext(); 756 757 template Object* 758 OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::CurrentKey(); 759 760 template void 761 OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::Transition(); 762 763 } // namespace internal 764 } // namespace v8 765