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
|
