5 #include "src/objects/ordered-hash-table.h" 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" 15 template <
class Derived,
int entrysize>
16 Handle<Derived> OrderedHashTable<Derived, entrysize>::Allocate(
17 Isolate* isolate,
int capacity, PretenureFlag pretenure) {
23 capacity = base::bits::RoundUpToPowerOfTwo32(Max(kMinCapacity, capacity));
24 if (capacity > kMaxCapacity) {
25 isolate->heap()->FatalProcessOutOfMemory(
"invalid table size");
27 int num_buckets = capacity / kLoadFactor;
28 Handle<FixedArray> backing_store = isolate->factory()->NewFixedArrayWithMap(
29 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));
35 table->SetNumberOfBuckets(num_buckets);
36 table->SetNumberOfElements(0);
37 table->SetNumberOfDeletedElements(0);
41 template <
class Derived,
int entrysize>
42 Handle<Derived> OrderedHashTable<Derived, entrysize>::EnsureGrowable(
43 Isolate* isolate, Handle<Derived> table) {
44 DCHECK(!table->IsObsolete());
46 int nof = table->NumberOfElements();
47 int nod = table->NumberOfDeletedElements();
48 int capacity = table->Capacity();
49 if ((nof + nod) < capacity)
return table;
53 return Rehash(isolate, table,
54 (nod < (capacity >> 1)) ? capacity << 1 : capacity);
57 template <
class Derived,
int entrysize>
58 Handle<Derived> OrderedHashTable<Derived, entrysize>::Shrink(
59 Isolate* isolate, Handle<Derived> table) {
60 DCHECK(!table->IsObsolete());
62 int nof = table->NumberOfElements();
63 int capacity = table->Capacity();
64 if (nof >= (capacity >> 2))
return table;
65 return Rehash(isolate, table, capacity / 2);
68 template <
class Derived,
int entrysize>
69 Handle<Derived> OrderedHashTable<Derived, entrysize>::Clear(
70 Isolate* isolate, Handle<Derived> table) {
71 DCHECK(!table->IsObsolete());
73 Handle<Derived> new_table = Allocate(
74 isolate, kMinCapacity, Heap::InNewSpace(*table) ? NOT_TENURED : TENURED);
76 table->SetNextTable(*new_table);
77 table->SetNumberOfDeletedElements(kClearedTableSentinel);
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 (entrysize == 3 && table->IsOrderedNameDictionary()));
88 DisallowHeapAllocation no_gc;
89 int entry = table->FindEntry(isolate, key);
90 return entry != kNotFound;
93 template <
class Derived,
int entrysize>
94 int OrderedHashTable<Derived, entrysize>::FindEntry(Isolate* isolate,
100 uint32_t hash = ComputeUnseededHash(Smi::ToInt(key));
101 entry = HashToEntry(hash & Smi::kMaxValue);
103 HandleScope scope(isolate);
104 Object* hash = key->GetHash();
106 if (hash->IsUndefined(isolate))
return kNotFound;
107 entry = HashToEntry(Smi::ToInt(hash));
111 while (entry != kNotFound) {
112 Object* candidate_key = KeyAt(entry);
113 if (candidate_key->SameValueZero(key))
break;
114 entry = NextChainEntry(entry);
120 Handle<OrderedHashSet> OrderedHashSet::Add(Isolate* isolate,
121 Handle<OrderedHashSet> table,
122 Handle<Object> key) {
123 int hash = key->GetOrCreateHash(isolate)->value();
124 int entry = table->HashToEntry(hash);
126 while (entry != kNotFound) {
127 Object* candidate_key = table->KeyAt(entry);
129 if (candidate_key->SameValueZero(*key))
return table;
130 entry = table->NextChainEntry(entry);
133 table = OrderedHashSet::EnsureGrowable(isolate, table);
135 int bucket = table->HashToBucket(hash);
136 int previous_entry = table->HashToEntry(hash);
137 int nof = table->NumberOfElements();
139 int new_entry = nof + table->NumberOfDeletedElements();
140 int new_index = table->EntryToIndex(new_entry);
141 table->set(new_index, *key);
142 table->set(new_index + kChainOffset, Smi::FromInt(previous_entry));
144 table->set(kHashTableStartIndex + bucket, Smi::FromInt(new_entry));
145 table->SetNumberOfElements(nof + 1);
149 Handle<FixedArray> OrderedHashSet::ConvertToKeysArray(
150 Isolate* isolate, Handle<OrderedHashSet> table, GetKeysConversion convert) {
151 int length = table->NumberOfElements();
152 int nof_buckets = table->NumberOfBuckets();
154 Handle<FixedArray> result = Handle<FixedArray>::cast(table);
156 result->set_map(ReadOnlyRoots(isolate).fixed_array_map());
157 int const kMaxStringTableEntries =
158 isolate->heap()->MaxNumberToStringCacheSize();
159 for (
int i = 0;
i < length;
i++) {
160 int index = kHashTableStartIndex + nof_buckets + (
i * kEntrySize);
161 Object* key = table->get(index);
162 if (convert == GetKeysConversion::kConvertToString) {
164 if (key->ToArrayIndex(&index_value)) {
166 bool use_cache =
i < kMaxStringTableEntries;
167 key = *isolate->factory()->Uint32ToString(index_value, use_cache);
169 CHECK(key->IsName());
174 return FixedArray::ShrinkOrEmpty(isolate, result, length);
177 HeapObject* OrderedHashSet::GetEmpty(ReadOnlyRoots ro_roots) {
178 return ro_roots.empty_ordered_hash_set();
181 HeapObject* OrderedHashMap::GetEmpty(ReadOnlyRoots ro_roots) {
182 return ro_roots.empty_ordered_hash_map();
185 template <
class Derived,
int entrysize>
186 Handle<Derived> OrderedHashTable<Derived, entrysize>::Rehash(
187 Isolate* isolate, Handle<Derived> table,
int new_capacity) {
188 DCHECK(!table->IsObsolete());
190 Handle<Derived> new_table = Allocate(
191 isolate, new_capacity, Heap::InNewSpace(*table) ? NOT_TENURED : TENURED);
192 int nof = table->NumberOfElements();
193 int nod = table->NumberOfDeletedElements();
194 int new_buckets = new_table->NumberOfBuckets();
196 int removed_holes_index = 0;
198 DisallowHeapAllocation no_gc;
199 for (
int old_entry = 0; old_entry < (nof + nod); ++old_entry) {
200 Object* key = table->KeyAt(old_entry);
201 if (key->IsTheHole(isolate)) {
202 table->SetRemovedIndexAt(removed_holes_index++, old_entry);
206 Object* hash = key->GetHash();
207 int bucket = Smi::ToInt(hash) & (new_buckets - 1);
208 Object* chain_entry = new_table->get(kHashTableStartIndex + bucket);
209 new_table->set(kHashTableStartIndex + bucket, Smi::FromInt(new_entry));
210 int new_index = new_table->EntryToIndex(new_entry);
211 int old_index = table->EntryToIndex(old_entry);
212 for (
int i = 0;
i < entrysize; ++
i) {
213 Object* value = table->get(old_index +
i);
214 new_table->set(new_index +
i, value);
216 new_table->set(new_index + kChainOffset, chain_entry);
220 DCHECK_EQ(nod, removed_holes_index);
222 new_table->SetNumberOfElements(nof);
223 table->SetNextTable(*new_table);
228 template <
class Derived,
int entrysize>
229 bool OrderedHashTable<Derived, entrysize>::Delete(Isolate* isolate,
230 Derived table, Object* key) {
231 DisallowHeapAllocation no_gc;
232 int entry = table->FindEntry(isolate, key);
233 if (entry == kNotFound)
return false;
235 int nof = table->NumberOfElements();
236 int nod = table->NumberOfDeletedElements();
237 int index = table->EntryToIndex(entry);
239 Object* hole = ReadOnlyRoots(isolate).the_hole_value();
240 for (
int i = 0;
i < entrysize; ++
i) {
241 table->set(index +
i, hole);
244 table->SetNumberOfElements(nof - 1);
245 table->SetNumberOfDeletedElements(nod + 1);
250 Object* OrderedHashMap::GetHash(Isolate* isolate, Object* key) {
251 DisallowHeapAllocation no_gc;
253 Object* hash = key->GetHash();
255 if (hash->IsUndefined(isolate))
return Smi::FromInt(-1);
256 DCHECK(hash->IsSmi());
257 DCHECK_GE(Smi::cast(hash)->value(), 0);
261 Handle<OrderedHashMap> OrderedHashMap::Add(Isolate* isolate,
262 Handle<OrderedHashMap> table,
264 Handle<Object> value) {
265 int hash = key->GetOrCreateHash(isolate)->value();
266 int entry = table->HashToEntry(hash);
269 DisallowHeapAllocation no_gc;
270 Object* raw_key = *key;
271 while (entry != kNotFound) {
272 Object* candidate_key = table->KeyAt(entry);
274 if (candidate_key->SameValueZero(raw_key))
return table;
275 entry = table->NextChainEntry(entry);
279 table = OrderedHashMap::EnsureGrowable(isolate, table);
281 int bucket = table->HashToBucket(hash);
282 int previous_entry = table->HashToEntry(hash);
283 int nof = table->NumberOfElements();
285 int new_entry = nof + table->NumberOfDeletedElements();
286 int new_index = table->EntryToIndex(new_entry);
287 table->set(new_index, *key);
288 table->set(new_index + kValueOffset, *value);
289 table->set(new_index + kChainOffset, Smi::FromInt(previous_entry));
291 table->set(kHashTableStartIndex + bucket, Smi::FromInt(new_entry));
292 table->SetNumberOfElements(nof + 1);
296 Handle<OrderedNameDictionary> OrderedNameDictionary::Add(
297 Isolate* isolate, Handle<OrderedNameDictionary> table, Handle<Name> key,
298 Handle<Object> value, PropertyDetails details) {
299 int hash = key->Hash();
304 DisallowHeapAllocation no_gc;
305 int entry = table->HashToEntry(hash);
306 Object* raw_key = *key;
307 while (entry != kNotFound) {
308 Object* candidate_key = table->KeyAt(entry);
311 CHECK(!candidate_key->SameValueZero(raw_key));
313 entry = table->NextChainEntry(entry);
318 table = OrderedNameDictionary::EnsureGrowable(isolate, table);
320 int bucket = table->HashToBucket(hash);
321 int previous_entry = table->HashToEntry(hash);
322 int nof = table->NumberOfElements();
324 int new_entry = nof + table->NumberOfDeletedElements();
325 int new_index = table->EntryToIndex(new_entry);
326 table->set(new_index, *key);
327 table->set(new_index + kValueOffset, *value);
332 table->set(new_index + kPropertyDetailsOffset, details.AsSmi());
334 table->set(new_index + kChainOffset, Smi::FromInt(previous_entry));
336 table->set(kHashTableStartIndex + bucket, Smi::FromInt(new_entry));
337 table->SetNumberOfElements(nof + 1);
342 int OrderedHashTable<OrderedNameDictionary, 3>::FindEntry(Isolate* isolate,
344 DisallowHeapAllocation no_gc;
346 DCHECK(key->IsUniqueName());
347 Name raw_key = Name::cast(key);
349 int entry = HashToEntry(raw_key->Hash());
350 while (entry != kNotFound) {
351 Object* candidate_key = KeyAt(entry);
352 DCHECK(candidate_key->IsTheHole() ||
353 Name::cast(candidate_key)->IsUniqueName());
354 if (candidate_key == raw_key)
return entry;
359 entry = NextChainEntry(entry);
365 template Handle<OrderedHashSet> OrderedHashTable<OrderedHashSet, 1>::Allocate(
366 Isolate* isolate,
int capacity, PretenureFlag pretenure);
368 template Handle<OrderedHashSet>
369 OrderedHashTable<OrderedHashSet, 1>::EnsureGrowable(
370 Isolate* isolate, Handle<OrderedHashSet> table);
372 template Handle<OrderedHashSet> OrderedHashTable<OrderedHashSet, 1>::Shrink(
373 Isolate* isolate, Handle<OrderedHashSet> table);
375 template Handle<OrderedHashSet> OrderedHashTable<OrderedHashSet, 1>::Clear(
376 Isolate* isolate, Handle<OrderedHashSet> table);
378 template bool OrderedHashTable<OrderedHashSet, 1>::HasKey(Isolate* isolate,
379 OrderedHashSet table,
382 template bool OrderedHashTable<OrderedHashSet, 1>::Delete(Isolate* isolate,
383 OrderedHashSet table,
386 template int OrderedHashTable<OrderedHashSet, 1>::FindEntry(Isolate* isolate,
389 template Handle<OrderedHashMap> OrderedHashTable<OrderedHashMap, 2>::Allocate(
390 Isolate* isolate,
int capacity, PretenureFlag pretenure);
392 template Handle<OrderedHashMap>
393 OrderedHashTable<OrderedHashMap, 2>::EnsureGrowable(
394 Isolate* isolate, Handle<OrderedHashMap> table);
396 template Handle<OrderedHashMap> OrderedHashTable<OrderedHashMap, 2>::Shrink(
397 Isolate* isolate, Handle<OrderedHashMap> table);
399 template Handle<OrderedHashMap> OrderedHashTable<OrderedHashMap, 2>::Clear(
400 Isolate* isolate, Handle<OrderedHashMap> table);
402 template bool OrderedHashTable<OrderedHashMap, 2>::HasKey(Isolate* isolate,
403 OrderedHashMap table,
406 template bool OrderedHashTable<OrderedHashMap, 2>::Delete(Isolate* isolate,
407 OrderedHashMap table,
410 template int OrderedHashTable<OrderedHashMap, 2>::FindEntry(Isolate* isolate,
413 template Handle<OrderedNameDictionary>
414 OrderedHashTable<OrderedNameDictionary, 3>::Allocate(Isolate* isolate,
416 PretenureFlag pretenure);
418 template bool OrderedHashTable<OrderedNameDictionary, 3>::HasKey(
419 Isolate* isolate, OrderedNameDictionary table, Object* key);
421 template Handle<OrderedNameDictionary>
422 OrderedHashTable<OrderedNameDictionary, 3>::EnsureGrowable(
423 Isolate* isolate, Handle<OrderedNameDictionary> table);
426 Handle<SmallOrderedHashSet>
427 SmallOrderedHashTable<SmallOrderedHashSet>::Allocate(Isolate* isolate,
429 PretenureFlag pretenure) {
430 return isolate->factory()->NewSmallOrderedHashSet(capacity, pretenure);
434 Handle<SmallOrderedHashMap>
435 SmallOrderedHashTable<SmallOrderedHashMap>::Allocate(Isolate* isolate,
437 PretenureFlag pretenure) {
438 return isolate->factory()->NewSmallOrderedHashMap(capacity, pretenure);
442 Handle<SmallOrderedNameDictionary>
443 SmallOrderedHashTable<SmallOrderedNameDictionary>::Allocate(
444 Isolate* isolate,
int capacity, PretenureFlag pretenure) {
445 return isolate->factory()->NewSmallOrderedNameDictionary(capacity, pretenure);
448 template <
class Derived>
449 void SmallOrderedHashTable<Derived>::Initialize(Isolate* isolate,
451 DisallowHeapAllocation no_gc;
452 int num_buckets = capacity / kLoadFactor;
453 int num_chains = capacity;
455 SetNumberOfBuckets(num_buckets);
456 SetNumberOfElements(0);
457 SetNumberOfDeletedElements(0);
459 Address hashtable_start = GetHashTableStartAddress(capacity);
460 memset(reinterpret_cast<byte*>(hashtable_start), kNotFound,
461 num_buckets + num_chains);
463 if (Heap::InNewSpace(*
this)) {
464 MemsetPointer(RawField(kDataTableStartOffset),
465 ReadOnlyRoots(isolate).the_hole_value(),
466 capacity * Derived::kEntrySize);
468 for (
int i = 0;
i < capacity;
i++) {
469 for (
int j = 0; j < Derived::kEntrySize; j++) {
470 SetDataEntry(
i, j, ReadOnlyRoots(isolate).the_hole_value());
476 for (
int i = 0;
i < num_buckets; ++
i) {
477 DCHECK_EQ(kNotFound, GetFirstEntry(
i));
480 for (
int i = 0;
i < num_chains; ++
i) {
481 DCHECK_EQ(kNotFound, GetNextEntry(
i));
484 for (
int i = 0;
i < capacity; ++
i) {
485 for (
int j = 0; j < Derived::kEntrySize; j++) {
486 DCHECK_EQ(ReadOnlyRoots(isolate).the_hole_value(), GetDataEntry(
i, j));
492 MaybeHandle<SmallOrderedHashSet> SmallOrderedHashSet::Add(
493 Isolate* isolate, Handle<SmallOrderedHashSet> table, Handle<Object> key) {
494 if (table->HasKey(isolate, key))
return table;
496 if (table->UsedCapacity() >= table->Capacity()) {
497 MaybeHandle<SmallOrderedHashSet> new_table =
498 SmallOrderedHashSet::Grow(isolate, table);
499 if (!new_table.ToHandle(&table)) {
500 return MaybeHandle<SmallOrderedHashSet>();
504 int hash = key->GetOrCreateHash(isolate)->value();
505 int nof = table->NumberOfElements();
508 int bucket = table->HashToBucket(hash);
509 int previous_entry = table->HashToFirstEntry(hash);
512 int new_entry = nof + table->NumberOfDeletedElements();
514 table->SetDataEntry(new_entry, SmallOrderedHashSet::kKeyIndex, *key);
515 table->SetFirstEntry(bucket, new_entry);
516 table->SetNextEntry(new_entry, previous_entry);
519 table->SetNumberOfElements(nof + 1);
524 MaybeHandle<SmallOrderedHashMap> SmallOrderedHashMap::Add(
525 Isolate* isolate, Handle<SmallOrderedHashMap> table, Handle<Object> key,
526 Handle<Object> value) {
527 if (table->HasKey(isolate, key))
return table;
529 if (table->UsedCapacity() >= table->Capacity()) {
530 MaybeHandle<SmallOrderedHashMap> new_table =
531 SmallOrderedHashMap::Grow(isolate, table);
532 if (!new_table.ToHandle(&table)) {
533 return MaybeHandle<SmallOrderedHashMap>();
537 int hash = key->GetOrCreateHash(isolate)->value();
538 int nof = table->NumberOfElements();
541 int bucket = table->HashToBucket(hash);
542 int previous_entry = table->HashToFirstEntry(hash);
545 int new_entry = nof + table->NumberOfDeletedElements();
547 table->SetDataEntry(new_entry, SmallOrderedHashMap::kValueIndex, *value);
548 table->SetDataEntry(new_entry, SmallOrderedHashMap::kKeyIndex, *key);
549 table->SetFirstEntry(bucket, new_entry);
550 table->SetNextEntry(new_entry, previous_entry);
553 table->SetNumberOfElements(nof + 1);
558 MaybeHandle<SmallOrderedNameDictionary> SmallOrderedNameDictionary::Add(
559 Isolate* isolate, Handle<SmallOrderedNameDictionary> table,
560 Handle<Name> key, Handle<Object> value, PropertyDetails details) {
561 DCHECK(!table->HasKey(isolate, key));
563 if (table->UsedCapacity() >= table->Capacity()) {
564 MaybeHandle<SmallOrderedNameDictionary> new_table =
565 SmallOrderedNameDictionary::Grow(isolate, table);
566 if (!new_table.ToHandle(&table)) {
567 return MaybeHandle<SmallOrderedNameDictionary>();
571 int hash = key->GetOrCreateHash(isolate)->value();
572 int nof = table->NumberOfElements();
575 int bucket = table->HashToBucket(hash);
576 int previous_entry = table->HashToFirstEntry(hash);
579 int new_entry = nof + table->NumberOfDeletedElements();
581 table->SetDataEntry(new_entry, SmallOrderedNameDictionary::kValueIndex,
583 table->SetDataEntry(new_entry, SmallOrderedNameDictionary::kKeyIndex, *key);
587 table->SetDataEntry(new_entry,
588 SmallOrderedNameDictionary::kPropertyDetailsIndex,
590 table->SetFirstEntry(bucket, new_entry);
591 table->SetNextEntry(new_entry, previous_entry);
594 table->SetNumberOfElements(nof + 1);
599 template <
class Derived>
600 bool SmallOrderedHashTable<Derived>::HasKey(Isolate* isolate,
601 Handle<Object> key) {
602 DisallowHeapAllocation no_gc;
603 return FindEntry(isolate, *key) != kNotFound;
606 template <
class Derived>
607 bool SmallOrderedHashTable<Derived>::Delete(Isolate* isolate, Derived table,
609 DisallowHeapAllocation no_gc;
610 int entry = table->FindEntry(isolate, key);
611 if (entry == kNotFound)
return false;
613 int nof = table->NumberOfElements();
614 int nod = table->NumberOfDeletedElements();
616 Object* hole = ReadOnlyRoots(isolate).the_hole_value();
617 for (
int j = 0; j < Derived::kEntrySize; j++) {
618 table->SetDataEntry(entry, j, hole);
621 table->SetNumberOfElements(nof - 1);
622 table->SetNumberOfDeletedElements(nod + 1);
627 template <
class Derived>
628 Handle<Derived> SmallOrderedHashTable<Derived>::Rehash(Isolate* isolate,
629 Handle<Derived> table,
631 DCHECK_GE(kMaxCapacity, new_capacity);
633 Handle<Derived> new_table = SmallOrderedHashTable<Derived>::Allocate(
634 isolate, new_capacity, Heap::InNewSpace(*table) ? NOT_TENURED : TENURED);
635 int nof = table->NumberOfElements();
636 int nod = table->NumberOfDeletedElements();
640 DisallowHeapAllocation no_gc;
641 for (
int old_entry = 0; old_entry < (nof + nod); ++old_entry) {
642 Object* key = table->KeyAt(old_entry);
643 if (key->IsTheHole(isolate))
continue;
645 int hash = Smi::ToInt(key->GetHash());
646 int bucket = new_table->HashToBucket(hash);
647 int chain = new_table->GetFirstEntry(bucket);
649 new_table->SetFirstEntry(bucket, new_entry);
650 new_table->SetNextEntry(new_entry, chain);
652 for (
int i = 0;
i < Derived::kEntrySize; ++
i) {
653 Object* value = table->GetDataEntry(old_entry,
i);
654 new_table->SetDataEntry(new_entry,
i, value);
660 new_table->SetNumberOfElements(nof);
665 template <
class Derived>
666 MaybeHandle<Derived> SmallOrderedHashTable<Derived>::Grow(
667 Isolate* isolate, Handle<Derived> table) {
668 int capacity = table->Capacity();
669 int new_capacity = capacity;
673 if (table->NumberOfDeletedElements() < (capacity >> 1)) {
674 new_capacity = capacity << 1;
679 if (new_capacity == kGrowthHack) {
680 new_capacity = kMaxCapacity;
684 if (new_capacity > kMaxCapacity) {
685 return MaybeHandle<Derived>();
689 return Rehash(isolate, table, new_capacity);
692 template <
class Derived>
693 int SmallOrderedHashTable<Derived>::FindEntry(Isolate* isolate, Object* key) {
694 DisallowHeapAllocation no_gc;
695 Object* hash = key->GetHash();
697 if (hash->IsUndefined(isolate))
return kNotFound;
698 int entry = HashToFirstEntry(Smi::ToInt(hash));
701 while (entry != kNotFound) {
702 Object* candidate_key = KeyAt(entry);
703 if (candidate_key->SameValueZero(key))
return entry;
704 entry = GetNextEntry(entry);
710 int SmallOrderedHashTable<SmallOrderedNameDictionary>::FindEntry(
711 Isolate* isolate, Object* key) {
712 DisallowHeapAllocation no_gc;
713 DCHECK(key->IsUniqueName());
714 Name raw_key = Name::cast(key);
716 int entry = HashToFirstEntry(raw_key->Hash());
719 while (entry != kNotFound) {
720 Object* candidate_key = KeyAt(entry);
721 if (candidate_key == key)
return entry;
722 entry = GetNextEntry(entry);
728 template bool SmallOrderedHashTable<SmallOrderedHashSet>::HasKey(
729 Isolate* isolate, Handle<Object> key);
730 template Handle<SmallOrderedHashSet>
731 SmallOrderedHashTable<SmallOrderedHashSet>::Rehash(
732 Isolate* isolate, Handle<SmallOrderedHashSet> table,
int new_capacity);
733 template MaybeHandle<SmallOrderedHashSet>
734 SmallOrderedHashTable<SmallOrderedHashSet>::Grow(
735 Isolate* isolate, Handle<SmallOrderedHashSet> table);
736 template void SmallOrderedHashTable<SmallOrderedHashSet>::Initialize(
737 Isolate* isolate,
int capacity);
739 template bool SmallOrderedHashTable<SmallOrderedHashMap>::HasKey(
740 Isolate* isolate, Handle<Object> key);
741 template Handle<SmallOrderedHashMap>
742 SmallOrderedHashTable<SmallOrderedHashMap>::Rehash(
743 Isolate* isolate, Handle<SmallOrderedHashMap> table,
int new_capacity);
744 template MaybeHandle<SmallOrderedHashMap>
745 SmallOrderedHashTable<SmallOrderedHashMap>::Grow(
746 Isolate* isolate, Handle<SmallOrderedHashMap> table);
747 template void SmallOrderedHashTable<SmallOrderedHashMap>::Initialize(
748 Isolate* isolate,
int capacity);
750 template bool SmallOrderedHashTable<SmallOrderedHashMap>::Delete(
751 Isolate* isolate, SmallOrderedHashMap table, Object* key);
752 template bool SmallOrderedHashTable<SmallOrderedHashSet>::Delete(
753 Isolate* isolate, SmallOrderedHashSet table, Object* key);
755 template void SmallOrderedHashTable<SmallOrderedNameDictionary>::Initialize(
756 Isolate* isolate,
int capacity);
757 template bool SmallOrderedHashTable<SmallOrderedNameDictionary>::HasKey(
758 Isolate* isolate, Handle<Object> key);
760 template <
class SmallTable,
class LargeTable>
761 Handle<HeapObject> OrderedHashTableHandler<SmallTable, LargeTable>::Allocate(
762 Isolate* isolate,
int capacity) {
763 if (capacity < SmallTable::kMaxCapacity) {
764 return SmallTable::Allocate(isolate, capacity);
767 return LargeTable::Allocate(isolate, capacity);
770 template Handle<HeapObject>
771 OrderedHashTableHandler<SmallOrderedHashSet, OrderedHashSet>::Allocate(
772 Isolate* isolate,
int capacity);
773 template Handle<HeapObject>
774 OrderedHashTableHandler<SmallOrderedHashMap, OrderedHashMap>::Allocate(
775 Isolate* isolate,
int capacity);
777 template <
class SmallTable,
class LargeTable>
778 bool OrderedHashTableHandler<SmallTable, LargeTable>::Delete(
779 Handle<HeapObject> table, Handle<Object> key) {
780 if (SmallTable::Is(table)) {
781 return SmallTable::Delete(Handle<SmallTable>::cast(table), key);
784 DCHECK(LargeTable::Is(table));
787 return LargeTable::Delete(Handle<LargeTable>::cast(table), key);
790 template <
class SmallTable,
class LargeTable>
791 bool OrderedHashTableHandler<SmallTable, LargeTable>::HasKey(
792 Isolate* isolate, Handle<HeapObject> table, Handle<Object> key) {
793 if (SmallTable::Is(table)) {
794 return Handle<SmallTable>::cast(table)->HasKey(isolate, key);
797 DCHECK(LargeTable::Is(table));
798 return LargeTable::HasKey(isolate, LargeTable::cast(*table), *key);
802 OrderedHashTableHandler<SmallOrderedHashSet, OrderedHashSet>::HasKey(
803 Isolate* isolate, Handle<HeapObject> table, Handle<Object> key);
805 OrderedHashTableHandler<SmallOrderedHashMap, OrderedHashMap>::HasKey(
806 Isolate* isolate, Handle<HeapObject> table, Handle<Object> key);
808 Handle<OrderedHashMap> OrderedHashMapHandler::AdjustRepresentation(
809 Isolate* isolate, Handle<SmallOrderedHashMap> table) {
810 Handle<OrderedHashMap> new_table =
811 OrderedHashMap::Allocate(isolate, OrderedHashTableMinSize);
812 int nof = table->NumberOfElements();
813 int nod = table->NumberOfDeletedElements();
818 for (
int entry = 0; entry < (nof + nod); ++entry) {
819 Handle<Object> key = handle(table->KeyAt(entry), isolate);
820 if (key->IsTheHole(isolate))
continue;
821 Handle<Object> value = handle(
822 table->GetDataEntry(entry, SmallOrderedHashMap::kValueIndex), isolate);
823 new_table = OrderedHashMap::Add(isolate, new_table, key, value);
829 Handle<OrderedHashSet> OrderedHashSetHandler::AdjustRepresentation(
830 Isolate* isolate, Handle<SmallOrderedHashSet> table) {
831 Handle<OrderedHashSet> new_table =
832 OrderedHashSet::Allocate(isolate, OrderedHashTableMinSize);
833 int nof = table->NumberOfElements();
834 int nod = table->NumberOfDeletedElements();
839 for (
int entry = 0; entry < (nof + nod); ++entry) {
840 Handle<Object> key = handle(table->KeyAt(entry), isolate);
841 if (key->IsTheHole(isolate))
continue;
842 new_table = OrderedHashSet::Add(isolate, new_table, key);
848 Handle<HeapObject> OrderedHashMapHandler::Add(Isolate* isolate,
849 Handle<HeapObject> table,
851 Handle<Object> value) {
852 if (table->IsSmallOrderedHashMap()) {
853 Handle<SmallOrderedHashMap> small_map =
854 Handle<SmallOrderedHashMap>::cast(table);
855 MaybeHandle<SmallOrderedHashMap> new_map =
856 SmallOrderedHashMap::Add(isolate, small_map, key, value);
857 if (!new_map.is_null())
return new_map.ToHandleChecked();
861 table = OrderedHashMapHandler::AdjustRepresentation(isolate, small_map);
864 DCHECK(table->IsOrderedHashMap());
865 return OrderedHashMap::Add(isolate, Handle<OrderedHashMap>::cast(table), key,
869 Handle<HeapObject> OrderedHashSetHandler::Add(Isolate* isolate,
870 Handle<HeapObject> table,
871 Handle<Object> key) {
872 if (table->IsSmallOrderedHashSet()) {
873 Handle<SmallOrderedHashSet> small_set =
874 Handle<SmallOrderedHashSet>::cast(table);
875 MaybeHandle<SmallOrderedHashSet> new_set =
876 SmallOrderedHashSet::Add(isolate, small_set, key);
877 if (!new_set.is_null())
return new_set.ToHandleChecked();
881 table = OrderedHashSetHandler::AdjustRepresentation(isolate, small_set);
884 DCHECK(table->IsOrderedHashSet());
885 return OrderedHashSet::Add(isolate, Handle<OrderedHashSet>::cast(table), key);
888 template <
class Derived,
class TableType>
889 void OrderedHashTableIterator<Derived, TableType>::Transition() {
890 DisallowHeapAllocation no_allocation;
891 TableType table = TableType::cast(this->table());
892 if (!table->IsObsolete())
return;
894 int index = Smi::ToInt(this->index());
895 while (table->IsObsolete()) {
896 TableType next_table = table->NextTable();
899 int nod = table->NumberOfDeletedElements();
901 if (nod == TableType::kClearedTableSentinel) {
904 int old_index = index;
905 for (
int i = 0;
i < nod; ++
i) {
906 int removed_index = table->RemovedIndexAt(
i);
907 if (removed_index >= old_index)
break;
917 set_index(Smi::FromInt(index));
920 template <
class Derived,
class TableType>
921 bool OrderedHashTableIterator<Derived, TableType>::HasMore() {
922 DisallowHeapAllocation no_allocation;
923 ReadOnlyRoots ro_roots = GetReadOnlyRoots();
927 TableType table = TableType::cast(this->table());
928 int index = Smi::ToInt(this->index());
929 int used_capacity = table->UsedCapacity();
931 while (index < used_capacity && table->KeyAt(index)->IsTheHole(ro_roots)) {
935 set_index(Smi::FromInt(index));
937 if (index < used_capacity)
return true;
939 set_table(TableType::GetEmpty(ro_roots));
944 OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::HasMore();
947 OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::MoveNext();
950 OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::CurrentKey();
953 OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::Transition();
956 OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::HasMore();
959 OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::MoveNext();
962 OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::CurrentKey();
965 OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::Transition();