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