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