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