V8 API Reference, 7.2.502.16 (for Deno 0.2.4)
ordered-hash-table.cc
1 // Copyright 2018 the V8 project authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4 
5 #include "src/objects/ordered-hash-table.h"
6 
7 #include "src/isolate.h"
8 #include "src/objects-inl.h"
9 #include "src/objects/js-collection-inl.h"
10 #include "src/objects/ordered-hash-table-inl.h"
11 
12 namespace v8 {
13 namespace internal {
14 
15 template <class Derived, int entrysize>
16 Handle<Derived> OrderedHashTable<Derived, entrysize>::Allocate(
17  Isolate* isolate, int capacity, PretenureFlag pretenure) {
18  // Capacity must be a power of two, since we depend on being able
19  // to divide and multiple by 2 (kLoadFactor) to derive capacity
20  // from number of buckets. If we decide to change kLoadFactor
21  // to something other than 2, capacity should be stored as another
22  // field of this object.
23  capacity = base::bits::RoundUpToPowerOfTwo32(Max(kMinCapacity, capacity));
24  if (capacity > kMaxCapacity) {
25  isolate->heap()->FatalProcessOutOfMemory("invalid table size");
26  }
27  int num_buckets = capacity / kLoadFactor;
28  Handle<FixedArray> backing_store = isolate->factory()->NewFixedArrayWithMap(
29  Derived::GetMapRootIndex(),
30  kHashTableStartIndex + num_buckets + (capacity * kEntrySize), pretenure);
31  Handle<Derived> table = Handle<Derived>::cast(backing_store);
32  for (int i = 0; i < num_buckets; ++i) {
33  table->set(kHashTableStartIndex + i, Smi::FromInt(kNotFound));
34  }
35  table->SetNumberOfBuckets(num_buckets);
36  table->SetNumberOfElements(0);
37  table->SetNumberOfDeletedElements(0);
38  return table;
39 }
40 
41 template <class Derived, int entrysize>
42 Handle<Derived> OrderedHashTable<Derived, entrysize>::EnsureGrowable(
43  Isolate* isolate, Handle<Derived> table) {
44  DCHECK(!table->IsObsolete());
45 
46  int nof = table->NumberOfElements();
47  int nod = table->NumberOfDeletedElements();
48  int capacity = table->Capacity();
49  if ((nof + nod) < capacity) return table;
50  // Don't need to grow if we can simply clear out deleted entries instead.
51  // Note that we can't compact in place, though, so we always allocate
52  // a new table.
53  return Rehash(isolate, table,
54  (nod < (capacity >> 1)) ? capacity << 1 : capacity);
55 }
56 
57 template <class Derived, int entrysize>
58 Handle<Derived> OrderedHashTable<Derived, entrysize>::Shrink(
59  Isolate* isolate, Handle<Derived> table) {
60  DCHECK(!table->IsObsolete());
61 
62  int nof = table->NumberOfElements();
63  int capacity = table->Capacity();
64  if (nof >= (capacity >> 2)) return table;
65  return Rehash(isolate, table, capacity / 2);
66 }
67 
68 template <class Derived, int entrysize>
69 Handle<Derived> OrderedHashTable<Derived, entrysize>::Clear(
70  Isolate* isolate, Handle<Derived> table) {
71  DCHECK(!table->IsObsolete());
72 
73  Handle<Derived> new_table = Allocate(
74  isolate, kMinCapacity, Heap::InNewSpace(*table) ? NOT_TENURED : TENURED);
75 
76  table->SetNextTable(*new_table);
77  table->SetNumberOfDeletedElements(kClearedTableSentinel);
78 
79  return new_table;
80 }
81 
82 template <class Derived, int entrysize>
83 bool OrderedHashTable<Derived, entrysize>::HasKey(Isolate* isolate,
84  Derived table, Object* key) {
85  DCHECK((entrysize == 1 && table->IsOrderedHashSet()) ||
86  (entrysize == 2 && table->IsOrderedHashMap()) ||
87  (entrysize == 3 && table->IsOrderedNameDictionary()));
88  DisallowHeapAllocation no_gc;
89  int entry = table->FindEntry(isolate, key);
90  return entry != kNotFound;
91 }
92 
93 template <class Derived, int entrysize>
94 int OrderedHashTable<Derived, entrysize>::FindEntry(Isolate* isolate,
95  Object* key) {
96  int entry;
97  // This special cases for Smi, so that we avoid the HandleScope
98  // creation below.
99  if (key->IsSmi()) {
100  uint32_t hash = ComputeUnseededHash(Smi::ToInt(key));
101  entry = HashToEntry(hash & Smi::kMaxValue);
102  } else {
103  HandleScope scope(isolate);
104  Object* hash = key->GetHash();
105  // If the object does not have an identity hash, it was never used as a key
106  if (hash->IsUndefined(isolate)) return kNotFound;
107  entry = HashToEntry(Smi::ToInt(hash));
108  }
109 
110  // Walk the chain in the bucket to find the key.
111  while (entry != kNotFound) {
112  Object* candidate_key = KeyAt(entry);
113  if (candidate_key->SameValueZero(key)) break;
114  entry = NextChainEntry(entry);
115  }
116 
117  return entry;
118 }
119 
120 Handle<OrderedHashSet> OrderedHashSet::Add(Isolate* isolate,
121  Handle<OrderedHashSet> table,
122  Handle<Object> key) {
123  int hash = key->GetOrCreateHash(isolate)->value();
124  int entry = table->HashToEntry(hash);
125  // Walk the chain of the bucket and try finding the key.
126  while (entry != kNotFound) {
127  Object* candidate_key = table->KeyAt(entry);
128  // Do not add if we have the key already
129  if (candidate_key->SameValueZero(*key)) return table;
130  entry = table->NextChainEntry(entry);
131  }
132 
133  table = OrderedHashSet::EnsureGrowable(isolate, table);
134  // Read the existing bucket values.
135  int bucket = table->HashToBucket(hash);
136  int previous_entry = table->HashToEntry(hash);
137  int nof = table->NumberOfElements();
138  // Insert a new entry at the end,
139  int new_entry = nof + table->NumberOfDeletedElements();
140  int new_index = table->EntryToIndex(new_entry);
141  table->set(new_index, *key);
142  table->set(new_index + kChainOffset, Smi::FromInt(previous_entry));
143  // and point the bucket to the new entry.
144  table->set(kHashTableStartIndex + bucket, Smi::FromInt(new_entry));
145  table->SetNumberOfElements(nof + 1);
146  return table;
147 }
148 
149 Handle<FixedArray> OrderedHashSet::ConvertToKeysArray(
150  Isolate* isolate, Handle<OrderedHashSet> table, GetKeysConversion convert) {
151  int length = table->NumberOfElements();
152  int nof_buckets = table->NumberOfBuckets();
153  // Convert the dictionary to a linear list.
154  Handle<FixedArray> result = Handle<FixedArray>::cast(table);
155  // From this point on table is no longer a valid OrderedHashSet.
156  result->set_map(ReadOnlyRoots(isolate).fixed_array_map());
157  int const kMaxStringTableEntries =
158  isolate->heap()->MaxNumberToStringCacheSize();
159  for (int i = 0; i < length; i++) {
160  int index = kHashTableStartIndex + nof_buckets + (i * kEntrySize);
161  Object* key = table->get(index);
162  if (convert == GetKeysConversion::kConvertToString) {
163  uint32_t index_value;
164  if (key->ToArrayIndex(&index_value)) {
165  // Avoid trashing the Number2String cache if indices get very large.
166  bool use_cache = i < kMaxStringTableEntries;
167  key = *isolate->factory()->Uint32ToString(index_value, use_cache);
168  } else {
169  CHECK(key->IsName());
170  }
171  }
172  result->set(i, key);
173  }
174  return FixedArray::ShrinkOrEmpty(isolate, result, length);
175 }
176 
177 HeapObject* OrderedHashSet::GetEmpty(ReadOnlyRoots ro_roots) {
178  return ro_roots.empty_ordered_hash_set();
179 }
180 
181 HeapObject* OrderedHashMap::GetEmpty(ReadOnlyRoots ro_roots) {
182  return ro_roots.empty_ordered_hash_map();
183 }
184 
185 template <class Derived, int entrysize>
186 Handle<Derived> OrderedHashTable<Derived, entrysize>::Rehash(
187  Isolate* isolate, Handle<Derived> table, int new_capacity) {
188  DCHECK(!table->IsObsolete());
189 
190  Handle<Derived> new_table = Allocate(
191  isolate, new_capacity, Heap::InNewSpace(*table) ? NOT_TENURED : TENURED);
192  int nof = table->NumberOfElements();
193  int nod = table->NumberOfDeletedElements();
194  int new_buckets = new_table->NumberOfBuckets();
195  int new_entry = 0;
196  int removed_holes_index = 0;
197 
198  DisallowHeapAllocation no_gc;
199  for (int old_entry = 0; old_entry < (nof + nod); ++old_entry) {
200  Object* key = table->KeyAt(old_entry);
201  if (key->IsTheHole(isolate)) {
202  table->SetRemovedIndexAt(removed_holes_index++, old_entry);
203  continue;
204  }
205 
206  Object* hash = key->GetHash();
207  int bucket = Smi::ToInt(hash) & (new_buckets - 1);
208  Object* chain_entry = new_table->get(kHashTableStartIndex + bucket);
209  new_table->set(kHashTableStartIndex + bucket, Smi::FromInt(new_entry));
210  int new_index = new_table->EntryToIndex(new_entry);
211  int old_index = table->EntryToIndex(old_entry);
212  for (int i = 0; i < entrysize; ++i) {
213  Object* value = table->get(old_index + i);
214  new_table->set(new_index + i, value);
215  }
216  new_table->set(new_index + kChainOffset, chain_entry);
217  ++new_entry;
218  }
219 
220  DCHECK_EQ(nod, removed_holes_index);
221 
222  new_table->SetNumberOfElements(nof);
223  table->SetNextTable(*new_table);
224 
225  return new_table;
226 }
227 
228 template <class Derived, int entrysize>
229 bool OrderedHashTable<Derived, entrysize>::Delete(Isolate* isolate,
230  Derived table, Object* key) {
231  DisallowHeapAllocation no_gc;
232  int entry = table->FindEntry(isolate, key);
233  if (entry == kNotFound) return false;
234 
235  int nof = table->NumberOfElements();
236  int nod = table->NumberOfDeletedElements();
237  int index = table->EntryToIndex(entry);
238 
239  Object* hole = ReadOnlyRoots(isolate).the_hole_value();
240  for (int i = 0; i < entrysize; ++i) {
241  table->set(index + i, hole);
242  }
243 
244  table->SetNumberOfElements(nof - 1);
245  table->SetNumberOfDeletedElements(nod + 1);
246 
247  return true;
248 }
249 
250 Object* OrderedHashMap::GetHash(Isolate* isolate, Object* key) {
251  DisallowHeapAllocation no_gc;
252 
253  Object* hash = key->GetHash();
254  // If the object does not have an identity hash, it was never used as a key
255  if (hash->IsUndefined(isolate)) return Smi::FromInt(-1);
256  DCHECK(hash->IsSmi());
257  DCHECK_GE(Smi::cast(hash)->value(), 0);
258  return hash;
259 }
260 
261 Handle<OrderedHashMap> OrderedHashMap::Add(Isolate* isolate,
262  Handle<OrderedHashMap> table,
263  Handle<Object> key,
264  Handle<Object> value) {
265  int hash = key->GetOrCreateHash(isolate)->value();
266  int entry = table->HashToEntry(hash);
267  // Walk the chain of the bucket and try finding the key.
268  {
269  DisallowHeapAllocation no_gc;
270  Object* raw_key = *key;
271  while (entry != kNotFound) {
272  Object* candidate_key = table->KeyAt(entry);
273  // Do not add if we have the key already
274  if (candidate_key->SameValueZero(raw_key)) return table;
275  entry = table->NextChainEntry(entry);
276  }
277  }
278 
279  table = OrderedHashMap::EnsureGrowable(isolate, table);
280  // Read the existing bucket values.
281  int bucket = table->HashToBucket(hash);
282  int previous_entry = table->HashToEntry(hash);
283  int nof = table->NumberOfElements();
284  // Insert a new entry at the end,
285  int new_entry = nof + table->NumberOfDeletedElements();
286  int new_index = table->EntryToIndex(new_entry);
287  table->set(new_index, *key);
288  table->set(new_index + kValueOffset, *value);
289  table->set(new_index + kChainOffset, Smi::FromInt(previous_entry));
290  // and point the bucket to the new entry.
291  table->set(kHashTableStartIndex + bucket, Smi::FromInt(new_entry));
292  table->SetNumberOfElements(nof + 1);
293  return table;
294 }
295 
296 Handle<OrderedNameDictionary> OrderedNameDictionary::Add(
297  Isolate* isolate, Handle<OrderedNameDictionary> table, Handle<Name> key,
298  Handle<Object> value, PropertyDetails details) {
299  int hash = key->Hash();
300 
301 #ifdef DEBUG
302  // Walk the chain of the bucket and try finding the key.
303  {
304  DisallowHeapAllocation no_gc;
305  int entry = table->HashToEntry(hash);
306  Object* raw_key = *key;
307  while (entry != kNotFound) {
308  Object* candidate_key = table->KeyAt(entry);
309 
310  // Key should not exist already!
311  CHECK(!candidate_key->SameValueZero(raw_key));
312 
313  entry = table->NextChainEntry(entry);
314  }
315  }
316 #endif
317 
318  table = OrderedNameDictionary::EnsureGrowable(isolate, table);
319  // Read the existing bucket values.
320  int bucket = table->HashToBucket(hash);
321  int previous_entry = table->HashToEntry(hash);
322  int nof = table->NumberOfElements();
323  // Insert a new entry at the end,
324  int new_entry = nof + table->NumberOfDeletedElements();
325  int new_index = table->EntryToIndex(new_entry);
326  table->set(new_index, *key);
327  table->set(new_index + kValueOffset, *value);
328 
329  // TODO(gsathya): Optimize how PropertyDetails are stored in this
330  // dictionary to save memory (by reusing padding?) and performance
331  // (by not doing the Smi conversion).
332  table->set(new_index + kPropertyDetailsOffset, details.AsSmi());
333 
334  table->set(new_index + kChainOffset, Smi::FromInt(previous_entry));
335  // and point the bucket to the new entry.
336  table->set(kHashTableStartIndex + bucket, Smi::FromInt(new_entry));
337  table->SetNumberOfElements(nof + 1);
338  return table;
339 }
340 
341 template <>
342 int OrderedHashTable<OrderedNameDictionary, 3>::FindEntry(Isolate* isolate,
343  Object* key) {
344  DisallowHeapAllocation no_gc;
345 
346  DCHECK(key->IsUniqueName());
347  Name raw_key = Name::cast(key);
348 
349  int entry = HashToEntry(raw_key->Hash());
350  while (entry != kNotFound) {
351  Object* candidate_key = KeyAt(entry);
352  DCHECK(candidate_key->IsTheHole() ||
353  Name::cast(candidate_key)->IsUniqueName());
354  if (candidate_key == raw_key) return entry;
355 
356  // TODO(gsathya): This is loading the bucket count from the hash
357  // table for every iteration. This should be peeled out of the
358  // loop.
359  entry = NextChainEntry(entry);
360  }
361 
362  return kNotFound;
363 }
364 
365 template Handle<OrderedHashSet> OrderedHashTable<OrderedHashSet, 1>::Allocate(
366  Isolate* isolate, int capacity, PretenureFlag pretenure);
367 
368 template Handle<OrderedHashSet>
369 OrderedHashTable<OrderedHashSet, 1>::EnsureGrowable(
370  Isolate* isolate, Handle<OrderedHashSet> table);
371 
372 template Handle<OrderedHashSet> OrderedHashTable<OrderedHashSet, 1>::Shrink(
373  Isolate* isolate, Handle<OrderedHashSet> table);
374 
375 template Handle<OrderedHashSet> OrderedHashTable<OrderedHashSet, 1>::Clear(
376  Isolate* isolate, Handle<OrderedHashSet> table);
377 
378 template bool OrderedHashTable<OrderedHashSet, 1>::HasKey(Isolate* isolate,
379  OrderedHashSet table,
380  Object* key);
381 
382 template bool OrderedHashTable<OrderedHashSet, 1>::Delete(Isolate* isolate,
383  OrderedHashSet table,
384  Object* key);
385 
386 template int OrderedHashTable<OrderedHashSet, 1>::FindEntry(Isolate* isolate,
387  Object* key);
388 
389 template Handle<OrderedHashMap> OrderedHashTable<OrderedHashMap, 2>::Allocate(
390  Isolate* isolate, int capacity, PretenureFlag pretenure);
391 
392 template Handle<OrderedHashMap>
393 OrderedHashTable<OrderedHashMap, 2>::EnsureGrowable(
394  Isolate* isolate, Handle<OrderedHashMap> table);
395 
396 template Handle<OrderedHashMap> OrderedHashTable<OrderedHashMap, 2>::Shrink(
397  Isolate* isolate, Handle<OrderedHashMap> table);
398 
399 template Handle<OrderedHashMap> OrderedHashTable<OrderedHashMap, 2>::Clear(
400  Isolate* isolate, Handle<OrderedHashMap> table);
401 
402 template bool OrderedHashTable<OrderedHashMap, 2>::HasKey(Isolate* isolate,
403  OrderedHashMap table,
404  Object* key);
405 
406 template bool OrderedHashTable<OrderedHashMap, 2>::Delete(Isolate* isolate,
407  OrderedHashMap table,
408  Object* key);
409 
410 template int OrderedHashTable<OrderedHashMap, 2>::FindEntry(Isolate* isolate,
411  Object* key);
412 
413 template Handle<OrderedNameDictionary>
414 OrderedHashTable<OrderedNameDictionary, 3>::Allocate(Isolate* isolate,
415  int capacity,
416  PretenureFlag pretenure);
417 
418 template bool OrderedHashTable<OrderedNameDictionary, 3>::HasKey(
419  Isolate* isolate, OrderedNameDictionary table, Object* key);
420 
421 template Handle<OrderedNameDictionary>
422 OrderedHashTable<OrderedNameDictionary, 3>::EnsureGrowable(
423  Isolate* isolate, Handle<OrderedNameDictionary> table);
424 
425 template <>
426 Handle<SmallOrderedHashSet>
427 SmallOrderedHashTable<SmallOrderedHashSet>::Allocate(Isolate* isolate,
428  int capacity,
429  PretenureFlag pretenure) {
430  return isolate->factory()->NewSmallOrderedHashSet(capacity, pretenure);
431 }
432 
433 template <>
434 Handle<SmallOrderedHashMap>
435 SmallOrderedHashTable<SmallOrderedHashMap>::Allocate(Isolate* isolate,
436  int capacity,
437  PretenureFlag pretenure) {
438  return isolate->factory()->NewSmallOrderedHashMap(capacity, pretenure);
439 }
440 
441 template <>
442 Handle<SmallOrderedNameDictionary>
443 SmallOrderedHashTable<SmallOrderedNameDictionary>::Allocate(
444  Isolate* isolate, int capacity, PretenureFlag pretenure) {
445  return isolate->factory()->NewSmallOrderedNameDictionary(capacity, pretenure);
446 }
447 
448 template <class Derived>
449 void SmallOrderedHashTable<Derived>::Initialize(Isolate* isolate,
450  int capacity) {
451  DisallowHeapAllocation no_gc;
452  int num_buckets = capacity / kLoadFactor;
453  int num_chains = capacity;
454 
455  SetNumberOfBuckets(num_buckets);
456  SetNumberOfElements(0);
457  SetNumberOfDeletedElements(0);
458 
459  Address hashtable_start = GetHashTableStartAddress(capacity);
460  memset(reinterpret_cast<byte*>(hashtable_start), kNotFound,
461  num_buckets + num_chains);
462 
463  if (Heap::InNewSpace(*this)) {
464  MemsetPointer(RawField(kDataTableStartOffset),
465  ReadOnlyRoots(isolate).the_hole_value(),
466  capacity * Derived::kEntrySize);
467  } else {
468  for (int i = 0; i < capacity; i++) {
469  for (int j = 0; j < Derived::kEntrySize; j++) {
470  SetDataEntry(i, j, ReadOnlyRoots(isolate).the_hole_value());
471  }
472  }
473  }
474 
475 #ifdef DEBUG
476  for (int i = 0; i < num_buckets; ++i) {
477  DCHECK_EQ(kNotFound, GetFirstEntry(i));
478  }
479 
480  for (int i = 0; i < num_chains; ++i) {
481  DCHECK_EQ(kNotFound, GetNextEntry(i));
482  }
483 
484  for (int i = 0; i < capacity; ++i) {
485  for (int j = 0; j < Derived::kEntrySize; j++) {
486  DCHECK_EQ(ReadOnlyRoots(isolate).the_hole_value(), GetDataEntry(i, j));
487  }
488  }
489 #endif // DEBUG
490 }
491 
492 MaybeHandle<SmallOrderedHashSet> SmallOrderedHashSet::Add(
493  Isolate* isolate, Handle<SmallOrderedHashSet> table, Handle<Object> key) {
494  if (table->HasKey(isolate, key)) return table;
495 
496  if (table->UsedCapacity() >= table->Capacity()) {
497  MaybeHandle<SmallOrderedHashSet> new_table =
498  SmallOrderedHashSet::Grow(isolate, table);
499  if (!new_table.ToHandle(&table)) {
500  return MaybeHandle<SmallOrderedHashSet>();
501  }
502  }
503 
504  int hash = key->GetOrCreateHash(isolate)->value();
505  int nof = table->NumberOfElements();
506 
507  // Read the existing bucket values.
508  int bucket = table->HashToBucket(hash);
509  int previous_entry = table->HashToFirstEntry(hash);
510 
511  // Insert a new entry at the end,
512  int new_entry = nof + table->NumberOfDeletedElements();
513 
514  table->SetDataEntry(new_entry, SmallOrderedHashSet::kKeyIndex, *key);
515  table->SetFirstEntry(bucket, new_entry);
516  table->SetNextEntry(new_entry, previous_entry);
517 
518  // and update book keeping.
519  table->SetNumberOfElements(nof + 1);
520 
521  return table;
522 }
523 
524 MaybeHandle<SmallOrderedHashMap> SmallOrderedHashMap::Add(
525  Isolate* isolate, Handle<SmallOrderedHashMap> table, Handle<Object> key,
526  Handle<Object> value) {
527  if (table->HasKey(isolate, key)) return table;
528 
529  if (table->UsedCapacity() >= table->Capacity()) {
530  MaybeHandle<SmallOrderedHashMap> new_table =
531  SmallOrderedHashMap::Grow(isolate, table);
532  if (!new_table.ToHandle(&table)) {
533  return MaybeHandle<SmallOrderedHashMap>();
534  }
535  }
536 
537  int hash = key->GetOrCreateHash(isolate)->value();
538  int nof = table->NumberOfElements();
539 
540  // Read the existing bucket values.
541  int bucket = table->HashToBucket(hash);
542  int previous_entry = table->HashToFirstEntry(hash);
543 
544  // Insert a new entry at the end,
545  int new_entry = nof + table->NumberOfDeletedElements();
546 
547  table->SetDataEntry(new_entry, SmallOrderedHashMap::kValueIndex, *value);
548  table->SetDataEntry(new_entry, SmallOrderedHashMap::kKeyIndex, *key);
549  table->SetFirstEntry(bucket, new_entry);
550  table->SetNextEntry(new_entry, previous_entry);
551 
552  // and update book keeping.
553  table->SetNumberOfElements(nof + 1);
554 
555  return table;
556 }
557 
558 MaybeHandle<SmallOrderedNameDictionary> SmallOrderedNameDictionary::Add(
559  Isolate* isolate, Handle<SmallOrderedNameDictionary> table,
560  Handle<Name> key, Handle<Object> value, PropertyDetails details) {
561  DCHECK(!table->HasKey(isolate, key));
562 
563  if (table->UsedCapacity() >= table->Capacity()) {
564  MaybeHandle<SmallOrderedNameDictionary> new_table =
565  SmallOrderedNameDictionary::Grow(isolate, table);
566  if (!new_table.ToHandle(&table)) {
567  return MaybeHandle<SmallOrderedNameDictionary>();
568  }
569  }
570 
571  int hash = key->GetOrCreateHash(isolate)->value();
572  int nof = table->NumberOfElements();
573 
574  // Read the existing bucket values.
575  int bucket = table->HashToBucket(hash);
576  int previous_entry = table->HashToFirstEntry(hash);
577 
578  // Insert a new entry at the end,
579  int new_entry = nof + table->NumberOfDeletedElements();
580 
581  table->SetDataEntry(new_entry, SmallOrderedNameDictionary::kValueIndex,
582  *value);
583  table->SetDataEntry(new_entry, SmallOrderedNameDictionary::kKeyIndex, *key);
584 
585  // TODO(gsathya): PropertyDetails should be stored as part of the
586  // data table to save more memory.
587  table->SetDataEntry(new_entry,
588  SmallOrderedNameDictionary::kPropertyDetailsIndex,
589  details.AsSmi());
590  table->SetFirstEntry(bucket, new_entry);
591  table->SetNextEntry(new_entry, previous_entry);
592 
593  // and update book keeping.
594  table->SetNumberOfElements(nof + 1);
595 
596  return table;
597 }
598 
599 template <class Derived>
600 bool SmallOrderedHashTable<Derived>::HasKey(Isolate* isolate,
601  Handle<Object> key) {
602  DisallowHeapAllocation no_gc;
603  return FindEntry(isolate, *key) != kNotFound;
604 }
605 
606 template <class Derived>
607 bool SmallOrderedHashTable<Derived>::Delete(Isolate* isolate, Derived table,
608  Object* key) {
609  DisallowHeapAllocation no_gc;
610  int entry = table->FindEntry(isolate, key);
611  if (entry == kNotFound) return false;
612 
613  int nof = table->NumberOfElements();
614  int nod = table->NumberOfDeletedElements();
615 
616  Object* hole = ReadOnlyRoots(isolate).the_hole_value();
617  for (int j = 0; j < Derived::kEntrySize; j++) {
618  table->SetDataEntry(entry, j, hole);
619  }
620 
621  table->SetNumberOfElements(nof - 1);
622  table->SetNumberOfDeletedElements(nod + 1);
623 
624  return true;
625 }
626 
627 template <class Derived>
628 Handle<Derived> SmallOrderedHashTable<Derived>::Rehash(Isolate* isolate,
629  Handle<Derived> table,
630  int new_capacity) {
631  DCHECK_GE(kMaxCapacity, new_capacity);
632 
633  Handle<Derived> new_table = SmallOrderedHashTable<Derived>::Allocate(
634  isolate, new_capacity, Heap::InNewSpace(*table) ? NOT_TENURED : TENURED);
635  int nof = table->NumberOfElements();
636  int nod = table->NumberOfDeletedElements();
637  int new_entry = 0;
638 
639  {
640  DisallowHeapAllocation no_gc;
641  for (int old_entry = 0; old_entry < (nof + nod); ++old_entry) {
642  Object* key = table->KeyAt(old_entry);
643  if (key->IsTheHole(isolate)) continue;
644 
645  int hash = Smi::ToInt(key->GetHash());
646  int bucket = new_table->HashToBucket(hash);
647  int chain = new_table->GetFirstEntry(bucket);
648 
649  new_table->SetFirstEntry(bucket, new_entry);
650  new_table->SetNextEntry(new_entry, chain);
651 
652  for (int i = 0; i < Derived::kEntrySize; ++i) {
653  Object* value = table->GetDataEntry(old_entry, i);
654  new_table->SetDataEntry(new_entry, i, value);
655  }
656 
657  ++new_entry;
658  }
659 
660  new_table->SetNumberOfElements(nof);
661  }
662  return new_table;
663 }
664 
665 template <class Derived>
666 MaybeHandle<Derived> SmallOrderedHashTable<Derived>::Grow(
667  Isolate* isolate, Handle<Derived> table) {
668  int capacity = table->Capacity();
669  int new_capacity = capacity;
670 
671  // Don't need to grow if we can simply clear out deleted entries instead.
672  // TODO(gsathya): Compact in place, instead of allocating a new table.
673  if (table->NumberOfDeletedElements() < (capacity >> 1)) {
674  new_capacity = capacity << 1;
675 
676  // The max capacity of our table is 254. We special case for 256 to
677  // account for our growth strategy, otherwise we would only fill up
678  // to 128 entries in our table.
679  if (new_capacity == kGrowthHack) {
680  new_capacity = kMaxCapacity;
681  }
682 
683  // We need to migrate to a bigger hash table.
684  if (new_capacity > kMaxCapacity) {
685  return MaybeHandle<Derived>();
686  }
687  }
688 
689  return Rehash(isolate, table, new_capacity);
690 }
691 
692 template <class Derived>
693 int SmallOrderedHashTable<Derived>::FindEntry(Isolate* isolate, Object* key) {
694  DisallowHeapAllocation no_gc;
695  Object* hash = key->GetHash();
696 
697  if (hash->IsUndefined(isolate)) return kNotFound;
698  int entry = HashToFirstEntry(Smi::ToInt(hash));
699 
700  // Walk the chain in the bucket to find the key.
701  while (entry != kNotFound) {
702  Object* candidate_key = KeyAt(entry);
703  if (candidate_key->SameValueZero(key)) return entry;
704  entry = GetNextEntry(entry);
705  }
706  return kNotFound;
707 }
708 
709 template <>
710 int SmallOrderedHashTable<SmallOrderedNameDictionary>::FindEntry(
711  Isolate* isolate, Object* key) {
712  DisallowHeapAllocation no_gc;
713  DCHECK(key->IsUniqueName());
714  Name raw_key = Name::cast(key);
715 
716  int entry = HashToFirstEntry(raw_key->Hash());
717 
718  // Walk the chain in the bucket to find the key.
719  while (entry != kNotFound) {
720  Object* candidate_key = KeyAt(entry);
721  if (candidate_key == key) return entry;
722  entry = GetNextEntry(entry);
723  }
724 
725  return kNotFound;
726 }
727 
728 template bool SmallOrderedHashTable<SmallOrderedHashSet>::HasKey(
729  Isolate* isolate, Handle<Object> key);
730 template Handle<SmallOrderedHashSet>
731 SmallOrderedHashTable<SmallOrderedHashSet>::Rehash(
732  Isolate* isolate, Handle<SmallOrderedHashSet> table, int new_capacity);
733 template MaybeHandle<SmallOrderedHashSet>
734 SmallOrderedHashTable<SmallOrderedHashSet>::Grow(
735  Isolate* isolate, Handle<SmallOrderedHashSet> table);
736 template void SmallOrderedHashTable<SmallOrderedHashSet>::Initialize(
737  Isolate* isolate, int capacity);
738 
739 template bool SmallOrderedHashTable<SmallOrderedHashMap>::HasKey(
740  Isolate* isolate, Handle<Object> key);
741 template Handle<SmallOrderedHashMap>
742 SmallOrderedHashTable<SmallOrderedHashMap>::Rehash(
743  Isolate* isolate, Handle<SmallOrderedHashMap> table, int new_capacity);
744 template MaybeHandle<SmallOrderedHashMap>
745 SmallOrderedHashTable<SmallOrderedHashMap>::Grow(
746  Isolate* isolate, Handle<SmallOrderedHashMap> table);
747 template void SmallOrderedHashTable<SmallOrderedHashMap>::Initialize(
748  Isolate* isolate, int capacity);
749 
750 template bool SmallOrderedHashTable<SmallOrderedHashMap>::Delete(
751  Isolate* isolate, SmallOrderedHashMap table, Object* key);
752 template bool SmallOrderedHashTable<SmallOrderedHashSet>::Delete(
753  Isolate* isolate, SmallOrderedHashSet table, Object* key);
754 
755 template void SmallOrderedHashTable<SmallOrderedNameDictionary>::Initialize(
756  Isolate* isolate, int capacity);
757 template bool SmallOrderedHashTable<SmallOrderedNameDictionary>::HasKey(
758  Isolate* isolate, Handle<Object> key);
759 
760 template <class SmallTable, class LargeTable>
761 Handle<HeapObject> OrderedHashTableHandler<SmallTable, LargeTable>::Allocate(
762  Isolate* isolate, int capacity) {
763  if (capacity < SmallTable::kMaxCapacity) {
764  return SmallTable::Allocate(isolate, capacity);
765  }
766 
767  return LargeTable::Allocate(isolate, capacity);
768 }
769 
770 template Handle<HeapObject>
771 OrderedHashTableHandler<SmallOrderedHashSet, OrderedHashSet>::Allocate(
772  Isolate* isolate, int capacity);
773 template Handle<HeapObject>
774 OrderedHashTableHandler<SmallOrderedHashMap, OrderedHashMap>::Allocate(
775  Isolate* isolate, int capacity);
776 
777 template <class SmallTable, class LargeTable>
778 bool OrderedHashTableHandler<SmallTable, LargeTable>::Delete(
779  Handle<HeapObject> table, Handle<Object> key) {
780  if (SmallTable::Is(table)) {
781  return SmallTable::Delete(Handle<SmallTable>::cast(table), key);
782  }
783 
784  DCHECK(LargeTable::Is(table));
785  // Note: Once we migrate to the a big hash table, we never migrate
786  // down to a smaller hash table.
787  return LargeTable::Delete(Handle<LargeTable>::cast(table), key);
788 }
789 
790 template <class SmallTable, class LargeTable>
791 bool OrderedHashTableHandler<SmallTable, LargeTable>::HasKey(
792  Isolate* isolate, Handle<HeapObject> table, Handle<Object> key) {
793  if (SmallTable::Is(table)) {
794  return Handle<SmallTable>::cast(table)->HasKey(isolate, key);
795  }
796 
797  DCHECK(LargeTable::Is(table));
798  return LargeTable::HasKey(isolate, LargeTable::cast(*table), *key);
799 }
800 
801 template bool
802 OrderedHashTableHandler<SmallOrderedHashSet, OrderedHashSet>::HasKey(
803  Isolate* isolate, Handle<HeapObject> table, Handle<Object> key);
804 template bool
805 OrderedHashTableHandler<SmallOrderedHashMap, OrderedHashMap>::HasKey(
806  Isolate* isolate, Handle<HeapObject> table, Handle<Object> key);
807 
808 Handle<OrderedHashMap> OrderedHashMapHandler::AdjustRepresentation(
809  Isolate* isolate, Handle<SmallOrderedHashMap> table) {
810  Handle<OrderedHashMap> new_table =
811  OrderedHashMap::Allocate(isolate, OrderedHashTableMinSize);
812  int nof = table->NumberOfElements();
813  int nod = table->NumberOfDeletedElements();
814 
815  // TODO(gsathya): Optimize the lookup to not re calc offsets. Also,
816  // unhandlify this code as we preallocate the new backing store with
817  // the proper capacity.
818  for (int entry = 0; entry < (nof + nod); ++entry) {
819  Handle<Object> key = handle(table->KeyAt(entry), isolate);
820  if (key->IsTheHole(isolate)) continue;
821  Handle<Object> value = handle(
822  table->GetDataEntry(entry, SmallOrderedHashMap::kValueIndex), isolate);
823  new_table = OrderedHashMap::Add(isolate, new_table, key, value);
824  }
825 
826  return new_table;
827 }
828 
829 Handle<OrderedHashSet> OrderedHashSetHandler::AdjustRepresentation(
830  Isolate* isolate, Handle<SmallOrderedHashSet> table) {
831  Handle<OrderedHashSet> new_table =
832  OrderedHashSet::Allocate(isolate, OrderedHashTableMinSize);
833  int nof = table->NumberOfElements();
834  int nod = table->NumberOfDeletedElements();
835 
836  // TODO(gsathya): Optimize the lookup to not re calc offsets. Also,
837  // unhandlify this code as we preallocate the new backing store with
838  // the proper capacity.
839  for (int entry = 0; entry < (nof + nod); ++entry) {
840  Handle<Object> key = handle(table->KeyAt(entry), isolate);
841  if (key->IsTheHole(isolate)) continue;
842  new_table = OrderedHashSet::Add(isolate, new_table, key);
843  }
844 
845  return new_table;
846 }
847 
848 Handle<HeapObject> OrderedHashMapHandler::Add(Isolate* isolate,
849  Handle<HeapObject> table,
850  Handle<Object> key,
851  Handle<Object> value) {
852  if (table->IsSmallOrderedHashMap()) {
853  Handle<SmallOrderedHashMap> small_map =
854  Handle<SmallOrderedHashMap>::cast(table);
855  MaybeHandle<SmallOrderedHashMap> new_map =
856  SmallOrderedHashMap::Add(isolate, small_map, key, value);
857  if (!new_map.is_null()) return new_map.ToHandleChecked();
858 
859  // We couldn't add to the small table, let's migrate to the
860  // big table.
861  table = OrderedHashMapHandler::AdjustRepresentation(isolate, small_map);
862  }
863 
864  DCHECK(table->IsOrderedHashMap());
865  return OrderedHashMap::Add(isolate, Handle<OrderedHashMap>::cast(table), key,
866  value);
867 }
868 
869 Handle<HeapObject> OrderedHashSetHandler::Add(Isolate* isolate,
870  Handle<HeapObject> table,
871  Handle<Object> key) {
872  if (table->IsSmallOrderedHashSet()) {
873  Handle<SmallOrderedHashSet> small_set =
874  Handle<SmallOrderedHashSet>::cast(table);
875  MaybeHandle<SmallOrderedHashSet> new_set =
876  SmallOrderedHashSet::Add(isolate, small_set, key);
877  if (!new_set.is_null()) return new_set.ToHandleChecked();
878 
879  // We couldn't add to the small table, let's migrate to the
880  // big table.
881  table = OrderedHashSetHandler::AdjustRepresentation(isolate, small_set);
882  }
883 
884  DCHECK(table->IsOrderedHashSet());
885  return OrderedHashSet::Add(isolate, Handle<OrderedHashSet>::cast(table), key);
886 }
887 
888 template <class Derived, class TableType>
889 void OrderedHashTableIterator<Derived, TableType>::Transition() {
890  DisallowHeapAllocation no_allocation;
891  TableType table = TableType::cast(this->table());
892  if (!table->IsObsolete()) return;
893 
894  int index = Smi::ToInt(this->index());
895  while (table->IsObsolete()) {
896  TableType next_table = table->NextTable();
897 
898  if (index > 0) {
899  int nod = table->NumberOfDeletedElements();
900 
901  if (nod == TableType::kClearedTableSentinel) {
902  index = 0;
903  } else {
904  int old_index = index;
905  for (int i = 0; i < nod; ++i) {
906  int removed_index = table->RemovedIndexAt(i);
907  if (removed_index >= old_index) break;
908  --index;
909  }
910  }
911  }
912 
913  table = next_table;
914  }
915 
916  set_table(table);
917  set_index(Smi::FromInt(index));
918 }
919 
920 template <class Derived, class TableType>
921 bool OrderedHashTableIterator<Derived, TableType>::HasMore() {
922  DisallowHeapAllocation no_allocation;
923  ReadOnlyRoots ro_roots = GetReadOnlyRoots();
924 
925  Transition();
926 
927  TableType table = TableType::cast(this->table());
928  int index = Smi::ToInt(this->index());
929  int used_capacity = table->UsedCapacity();
930 
931  while (index < used_capacity && table->KeyAt(index)->IsTheHole(ro_roots)) {
932  index++;
933  }
934 
935  set_index(Smi::FromInt(index));
936 
937  if (index < used_capacity) return true;
938 
939  set_table(TableType::GetEmpty(ro_roots));
940  return false;
941 }
942 
943 template bool
944 OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::HasMore();
945 
946 template void
947 OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::MoveNext();
948 
949 template Object*
950 OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::CurrentKey();
951 
952 template void
953 OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::Transition();
954 
955 template bool
956 OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::HasMore();
957 
958 template void
959 OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::MoveNext();
960 
961 template Object*
962 OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::CurrentKey();
963 
964 template void
965 OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::Transition();
966 
967 } // namespace internal
968 } // namespace v8
Definition: libplatform.h:13