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#ifndef V8_OBJECTS_ORDERED_HASH_TABLE_H_
6#define V8_OBJECTS_ORDERED_HASH_TABLE_H_
7
8#include "src/base/export-template.h"
9#include "src/globals.h"
10#include "src/objects/fixed-array.h"
11#include "src/objects/js-objects.h"
12#include "src/objects/smi.h"
13#include "src/roots.h"
14
15// Has to be the last include (doesn't have include guards):
16#include "src/objects/object-macros.h"
17
18namespace v8 {
19namespace internal {
20
21// OrderedHashTable is a HashTable with Object keys that preserves
22// insertion order. There are Map and Set interfaces (OrderedHashMap
23// and OrderedHashTable, below). It is meant to be used by JSMap/JSSet.
24//
25// Only Object keys are supported, with Object::SameValueZero() used as the
26// equality operator and Object::GetHash() for the hash function.
27//
28// Based on the "Deterministic Hash Table" as described by Jason Orendorff at
29// https://wiki.mozilla.org/User:Jorend/Deterministic_hash_tables
30// Originally attributed to Tyler Close.
31//
32// Memory layout:
33// [0] : Prefix
34// [kPrefixSize]: element count
35// [kPrefixSize + 1]: deleted element count
36// [kPrefixSize + 2]: bucket count
37// [kPrefixSize + 3..(3 + NumberOfBuckets() - 1)]: "hash table",
38// where each item is an offset into the
39// data table (see below) where the first
40// item in this bucket is stored.
41// [kPrefixSize + 3 + NumberOfBuckets()..length]: "data table", an
42// array of length Capacity() * kEntrySize,
43// where the first entrysize items are
44// handled by the derived class and the
45// item at kChainOffset is another entry
46// into the data table indicating the next
47// entry in this hash bucket.
48//
49// When we transition the table to a new version we obsolete it and reuse parts
50// of the memory to store information how to transition an iterator to the new
51// table:
52//
53// Memory layout for obsolete table:
54// [0] : Prefix
55// [kPrefixSize + 0]: bucket count
56// [kPrefixSize + 1]: Next newer table
57// [kPrefixSize + 2]: Number of removed holes or -1 when the table was
58// cleared.
59// [kPrefixSize + 3..(3 + NumberOfRemovedHoles() - 1)]: The indexes
60// of the removed holes.
61// [kPrefixSize + 3 + NumberOfRemovedHoles()..length]: Not used
62template <class Derived, int entrysize>
63class OrderedHashTable : public FixedArray {
64 public:
65 // Returns an OrderedHashTable (possibly |table|) with enough space
66 // to add at least one new element.
67 static Handle<Derived> EnsureGrowable(Isolate* isolate,
68 Handle<Derived> table);
69
70 // Returns an OrderedHashTable (possibly |table|) that's shrunken
71 // if possible.
72 static Handle<Derived> Shrink(Isolate* isolate, Handle<Derived> table);
73
74 // Returns a new empty OrderedHashTable and records the clearing so that
75 // existing iterators can be updated.
76 static Handle<Derived> Clear(Isolate* isolate, Handle<Derived> table);
77
78 // Returns true if the OrderedHashTable contains the key
79 static bool HasKey(Isolate* isolate, Derived table, Object key);
80
81 // Returns a true value if the OrderedHashTable contains the key and
82 // the key has been deleted. This does not shrink the table.
83 static bool Delete(Isolate* isolate, Derived table, Object key);
84
85 int FindEntry(Isolate* isolate, Object key);
86
87 int NumberOfElements() const {
88 return Smi::ToInt(get(NumberOfElementsIndex()));
89 }
90
91 int NumberOfDeletedElements() const {
92 return Smi::ToInt(get(NumberOfDeletedElementsIndex()));
93 }
94
95 // Returns the number of contiguous entries in the data table, starting at 0,
96 // that either are real entries or have been deleted.
97 int UsedCapacity() const {
98 return NumberOfElements() + NumberOfDeletedElements();
99 }
100
101 int NumberOfBuckets() const {
102 return Smi::ToInt(get(NumberOfBucketsIndex()));
103 }
104
105 // Returns an index into |this| for the given entry.
106 int EntryToIndex(int entry) {
107 return HashTableStartIndex() + NumberOfBuckets() + (entry * kEntrySize);
108 }
109
110 int HashToBucket(int hash) { return hash & (NumberOfBuckets() - 1); }
111
112 int HashToEntry(int hash) {
113 int bucket = HashToBucket(hash);
114 Object entry = this->get(HashTableStartIndex() + bucket);
115 return Smi::ToInt(entry);
116 }
117
118 int NextChainEntry(int entry) {
119 Object next_entry = get(EntryToIndex(entry) + kChainOffset);
120 return Smi::ToInt(next_entry);
121 }
122
123 // use KeyAt(i)->IsTheHole(isolate) to determine if this is a deleted entry.
124 Object KeyAt(int entry) {
125 DCHECK_LT(entry, this->UsedCapacity());
126 return get(EntryToIndex(entry));
127 }
128
129 bool IsObsolete() { return !get(NextTableIndex())->IsSmi(); }
130
131 // The next newer table. This is only valid if the table is obsolete.
132 Derived NextTable() { return Derived::cast(get(NextTableIndex())); }
133
134 // When the table is obsolete we store the indexes of the removed holes.
135 int RemovedIndexAt(int index) {
136 return Smi::ToInt(get(RemovedHolesIndex() + index));
137 }
138
139 // The extra +1 is for linking the bucket chains together.
140 static const int kEntrySize = entrysize + 1;
141 static const int kChainOffset = entrysize;
142
143 static const int kNotFound = -1;
144 static const int kMinCapacity = 4;
145
146 static constexpr int PrefixIndex() { return 0; }
147
148 static constexpr int NumberOfElementsIndex() { return Derived::kPrefixSize; }
149
150 // The next table is stored at the same index as the nof elements.
151 static constexpr int NextTableIndex() { return NumberOfElementsIndex(); }
152
153 static constexpr int NumberOfDeletedElementsIndex() {
154 return NumberOfElementsIndex() + 1;
155 }
156
157 static constexpr int NumberOfBucketsIndex() {
158 return NumberOfDeletedElementsIndex() + 1;
159 }
160
161 static constexpr int HashTableStartIndex() {
162 return NumberOfBucketsIndex() + 1;
163 }
164
165 static constexpr int RemovedHolesIndex() { return HashTableStartIndex(); }
166
167 static constexpr int NumberOfElementsOffset() {
168 return FixedArray::OffsetOfElementAt(NumberOfElementsIndex());
169 }
170
171 static constexpr int NextTableOffset() {
172 return FixedArray::OffsetOfElementAt(NextTableIndex());
173 }
174
175 static constexpr int NumberOfDeletedElementsOffset() {
176 return FixedArray::OffsetOfElementAt(NumberOfDeletedElementsIndex());
177 }
178
179 static constexpr int NumberOfBucketsOffset() {
180 return FixedArray::OffsetOfElementAt(NumberOfBucketsIndex());
181 }
182
183 static constexpr int HashTableStartOffset() {
184 return FixedArray::OffsetOfElementAt(HashTableStartIndex());
185 }
186
187 static const int kLoadFactor = 2;
188
189 // NumberOfDeletedElements is set to kClearedTableSentinel when
190 // the table is cleared, which allows iterator transitions to
191 // optimize that case.
192 static const int kClearedTableSentinel = -1;
193 static constexpr int MaxCapacity() {
194 return (FixedArray::kMaxLength - HashTableStartIndex()) /
195 (1 + (kEntrySize * kLoadFactor));
196 }
197
198 protected:
199 // Returns an OrderedHashTable with a capacity of at least |capacity|.
200 static Handle<Derived> Allocate(
201 Isolate* isolate, int capacity,
202 AllocationType allocation = AllocationType::kYoung);
203 static Handle<Derived> Rehash(Isolate* isolate, Handle<Derived> table,
204 int new_capacity);
205
206 void SetNumberOfBuckets(int num) {
207 set(NumberOfBucketsIndex(), Smi::FromInt(num));
208 }
209
210 void SetNumberOfElements(int num) {
211 set(NumberOfElementsIndex(), Smi::FromInt(num));
212 }
213
214 void SetNumberOfDeletedElements(int num) {
215 set(NumberOfDeletedElementsIndex(), Smi::FromInt(num));
216 }
217
218 // Returns the number elements that can fit into the allocated buffer.
219 int Capacity() { return NumberOfBuckets() * kLoadFactor; }
220
221 void SetNextTable(Derived next_table) { set(NextTableIndex(), next_table); }
222
223 void SetRemovedIndexAt(int index, int removed_index) {
224 return set(RemovedHolesIndex() + index, Smi::FromInt(removed_index));
225 }
226
227 OBJECT_CONSTRUCTORS(OrderedHashTable, FixedArray);
228
229 private:
230 friend class OrderedNameDictionaryHandler;
231};
232
233class V8_EXPORT_PRIVATE OrderedHashSet
234 : public OrderedHashTable<OrderedHashSet, 1> {
235 public:
236 DECL_CAST(OrderedHashSet)
237
238 static Handle<OrderedHashSet> Add(Isolate* isolate,
239 Handle<OrderedHashSet> table,
240 Handle<Object> value);
241 static Handle<FixedArray> ConvertToKeysArray(Isolate* isolate,
242 Handle<OrderedHashSet> table,
243 GetKeysConversion convert);
244 static Handle<OrderedHashSet> Rehash(Isolate* isolate,
245 Handle<OrderedHashSet> table,
246 int new_capacity);
247 static Handle<OrderedHashSet> Allocate(
248 Isolate* isolate, int capacity,
249 AllocationType allocation = AllocationType::kYoung);
250 static HeapObject GetEmpty(ReadOnlyRoots ro_roots);
251 static inline RootIndex GetMapRootIndex();
252 static inline bool Is(Handle<HeapObject> table);
253 static const int kPrefixSize = 0;
254
255 OBJECT_CONSTRUCTORS(OrderedHashSet, OrderedHashTable<OrderedHashSet, 1>);
256};
257
258class V8_EXPORT_PRIVATE OrderedHashMap
259 : public OrderedHashTable<OrderedHashMap, 2> {
260 public:
261 DECL_CAST(OrderedHashMap)
262
263 // Returns a value if the OrderedHashMap contains the key, otherwise
264 // returns undefined.
265 static Handle<OrderedHashMap> Add(Isolate* isolate,
266 Handle<OrderedHashMap> table,
267 Handle<Object> key, Handle<Object> value);
268
269 static Handle<OrderedHashMap> Allocate(
270 Isolate* isolate, int capacity,
271 AllocationType allocation = AllocationType::kYoung);
272 static Handle<OrderedHashMap> Rehash(Isolate* isolate,
273 Handle<OrderedHashMap> table,
274 int new_capacity);
275 Object ValueAt(int entry);
276
277 // This takes and returns raw Address values containing tagged Object
278 // pointers because it is called via ExternalReference.
279 static Address GetHash(Isolate* isolate, Address raw_key);
280
281 static HeapObject GetEmpty(ReadOnlyRoots ro_roots);
282 static inline RootIndex GetMapRootIndex();
283 static inline bool Is(Handle<HeapObject> table);
284
285 static const int kValueOffset = 1;
286 static const int kPrefixSize = 0;
287
288 OBJECT_CONSTRUCTORS(OrderedHashMap, OrderedHashTable<OrderedHashMap, 2>);
289};
290
291// This is similar to the OrderedHashTable, except for the memory
292// layout where we use byte instead of Smi. The max capacity of this
293// is only 254, we transition to an OrderedHashTable beyond that
294// limit.
295//
296// Each bucket and chain value is a byte long. The padding exists so
297// that the DataTable entries start aligned. A bucket or chain value
298// of 255 is used to denote an unknown entry.
299//
300// The prefix size is calculated as the kPrefixSize * kTaggedSize.
301//
302// Memory layout: [ Prefix ] [ Header ] [ Padding ] [ DataTable ] [ HashTable ]
303// [ Chains ]
304//
305// The index are represented as bytes, on a 64 bit machine with
306// kEntrySize = 1, capacity = 4 and entries = 2:
307//
308// [ 0 ] : Prefix
309//
310// Note: For the sake of brevity, the following start with index 0
311// but, they actually start from kPrefixSize * kTaggedSize to
312// account for the the prefix.
313//
314// [ Header ] :
315// [0] : Number of elements
316// [1] : Number of deleted elements
317// [2] : Number of buckets
318//
319// [ Padding ] :
320// [3 .. 7] : Padding
321//
322// [ DataTable ] :
323// [8 .. 15] : Entry 1
324// [16 .. 23] : Entry 2
325// [24 .. 31] : empty
326// [32 .. 39] : empty
327//
328// [ HashTable ] :
329// [40] : First chain-link for bucket 1
330// [41] : empty
331//
332// [ Chains ] :
333// [42] : Next chain link for bucket 1
334// [43] : empty
335// [44] : empty
336// [45] : empty
337//
338template <class Derived>
339class SmallOrderedHashTable : public HeapObject {
340 public:
341 // Offset points to a relative location in the table
342 using Offset = int;
343
344 // ByteIndex points to a index in the table that needs to be
345 // converted to an Offset.
346 using ByteIndex = int;
347
348 void Initialize(Isolate* isolate, int capacity);
349
350 static Handle<Derived> Allocate(
351 Isolate* isolate, int capacity,
352 AllocationType allocation = AllocationType::kYoung);
353
354 // Returns a true if the OrderedHashTable contains the key
355 bool HasKey(Isolate* isolate, Handle<Object> key);
356
357 // Returns a true value if the table contains the key and
358 // the key has been deleted. This does not shrink the table.
359 static bool Delete(Isolate* isolate, Derived table, Object key);
360
361 // Returns an SmallOrderedHashTable (possibly |table|) with enough
362 // space to add at least one new element. Returns empty handle if
363 // we've already reached MaxCapacity.
364 static MaybeHandle<Derived> Grow(Isolate* isolate, Handle<Derived> table);
365
366 int FindEntry(Isolate* isolate, Object key);
367 static Handle<Derived> Shrink(Isolate* isolate, Handle<Derived> table);
368
369 // Iterates only fields in the DataTable.
370 class BodyDescriptor;
371
372 // Returns total size in bytes required for a table of given
373 // capacity.
374 static int SizeFor(int capacity) {
375 DCHECK_GE(capacity, kMinCapacity);
376 DCHECK_LE(capacity, kMaxCapacity);
377
378 int data_table_size = DataTableSizeFor(capacity);
379 int hash_table_size = capacity / kLoadFactor;
380 int chain_table_size = capacity;
381 int total_size = DataTableStartOffset() + data_table_size +
382 hash_table_size + chain_table_size;
383
384 return RoundUp(total_size, kTaggedSize);
385 }
386
387 // Returns the number elements that can fit into the allocated table.
388 int Capacity() const {
389 int capacity = NumberOfBuckets() * kLoadFactor;
390 DCHECK_GE(capacity, kMinCapacity);
391 DCHECK_LE(capacity, kMaxCapacity);
392
393 return capacity;
394 }
395
396 // Returns the number elements that are present in the table.
397 int NumberOfElements() const {
398 int nof_elements = getByte(NumberOfElementsOffset(), 0);
399 DCHECK_LE(nof_elements, Capacity());
400
401 return nof_elements;
402 }
403
404 int NumberOfDeletedElements() const {
405 int nof_deleted_elements = getByte(NumberOfDeletedElementsOffset(), 0);
406 DCHECK_LE(nof_deleted_elements, Capacity());
407
408 return nof_deleted_elements;
409 }
410
411 int NumberOfBuckets() const { return getByte(NumberOfBucketsOffset(), 0); }
412
413 V8_INLINE Object KeyAt(int entry) const;
414
415 DECL_VERIFIER(SmallOrderedHashTable)
416
417 static const int kMinCapacity = 4;
418 static const byte kNotFound = 0xFF;
419
420 // We use the value 255 to indicate kNotFound for chain and bucket
421 // values, which means that this value can't be used a valid
422 // index.
423 static const int kMaxCapacity = 254;
424 STATIC_ASSERT(kMaxCapacity < kNotFound);
425
426 // The load factor is used to derive the number of buckets from
427 // capacity during Allocation. We also depend on this to calaculate
428 // the capacity from number of buckets after allocation. If we
429 // decide to change kLoadFactor to something other than 2, capacity
430 // should be stored as another field of this object.
431 static const int kLoadFactor = 2;
432
433 // Our growth strategy involves doubling the capacity until we reach
434 // kMaxCapacity, but since the kMaxCapacity is always less than 256,
435 // we will never fully utilize this table. We special case for 256,
436 // by changing the new capacity to be kMaxCapacity in
437 // SmallOrderedHashTable::Grow.
438 static const int kGrowthHack = 256;
439
440 protected:
441 static Handle<Derived> Rehash(Isolate* isolate, Handle<Derived> table,
442 int new_capacity);
443
444 void SetDataEntry(int entry, int relative_index, Object value);
445
446 // TODO(gsathya): Calculate all the various possible values for this
447 // at compile time since capacity can only be 4 different values.
448 Offset GetBucketsStartOffset() const {
449 int capacity = Capacity();
450 int data_table_size = DataTableSizeFor(capacity);
451 return DataTableStartOffset() + data_table_size;
452 }
453
454 Address GetHashTableStartAddress(int capacity) const {
455 return FIELD_ADDR(*this,
456 DataTableStartOffset() + DataTableSizeFor(capacity));
457 }
458
459 void SetFirstEntry(int bucket, byte value) {
460 DCHECK_LE(static_cast<unsigned>(bucket), NumberOfBuckets());
461 setByte(GetBucketsStartOffset(), bucket, value);
462 }
463
464 int GetFirstEntry(int bucket) const {
465 DCHECK_LE(static_cast<unsigned>(bucket), NumberOfBuckets());
466 return getByte(GetBucketsStartOffset(), bucket);
467 }
468
469 // TODO(gsathya): Calculate all the various possible values for this
470 // at compile time since capacity can only be 4 different values.
471 Offset GetChainTableOffset() const {
472 int nof_buckets = NumberOfBuckets();
473 int capacity = nof_buckets * kLoadFactor;
474 DCHECK_EQ(Capacity(), capacity);
475
476 int data_table_size = DataTableSizeFor(capacity);
477 int hash_table_size = nof_buckets;
478 return DataTableStartOffset() + data_table_size + hash_table_size;
479 }
480
481 void SetNextEntry(int entry, int next_entry) {
482 DCHECK_LT(static_cast<unsigned>(entry), Capacity());
483 DCHECK_GE(static_cast<unsigned>(next_entry), 0);
484 DCHECK(next_entry <= Capacity() || next_entry == kNotFound);
485 setByte(GetChainTableOffset(), entry, next_entry);
486 }
487
488 int GetNextEntry(int entry) const {
489 DCHECK_LT(entry, Capacity());
490 return getByte(GetChainTableOffset(), entry);
491 }
492
493 V8_INLINE Object GetDataEntry(int entry, int relative_index);
494
495 int HashToBucket(int hash) const { return hash & (NumberOfBuckets() - 1); }
496
497 int HashToFirstEntry(int hash) const {
498 int bucket = HashToBucket(hash);
499 int entry = GetFirstEntry(bucket);
500 DCHECK(entry < Capacity() || entry == kNotFound);
501 return entry;
502 }
503
504 void SetNumberOfBuckets(int num) { setByte(NumberOfBucketsOffset(), 0, num); }
505
506 void SetNumberOfElements(int num) {
507 DCHECK_LE(static_cast<unsigned>(num), Capacity());
508 setByte(NumberOfElementsOffset(), 0, num);
509 }
510
511 void SetNumberOfDeletedElements(int num) {
512 DCHECK_LE(static_cast<unsigned>(num), Capacity());
513 setByte(NumberOfDeletedElementsOffset(), 0, num);
514 }
515
516 static constexpr Offset PrefixOffset() { return kHeaderSize; }
517
518 static constexpr Offset NumberOfElementsOffset() {
519 return PrefixOffset() + (Derived::kPrefixSize * kTaggedSize);
520 }
521
522 static constexpr Offset NumberOfDeletedElementsOffset() {
523 return NumberOfElementsOffset() + kOneByteSize;
524 }
525
526 static constexpr Offset NumberOfBucketsOffset() {
527 return NumberOfDeletedElementsOffset() + kOneByteSize;
528 }
529
530 static constexpr Offset DataTableStartOffset() {
531 return RoundUp<kTaggedSize>(NumberOfBucketsOffset());
532 }
533
534 static constexpr int DataTableSizeFor(int capacity) {
535 return capacity * Derived::kEntrySize * kTaggedSize;
536 }
537
538 // This is used for accessing the non |DataTable| part of the
539 // structure.
540 byte getByte(Offset offset, ByteIndex index) const {
541 DCHECK(offset < DataTableStartOffset() ||
542 offset >= GetBucketsStartOffset());
543 return READ_BYTE_FIELD(*this, offset + (index * kOneByteSize));
544 }
545
546 void setByte(Offset offset, ByteIndex index, byte value) {
547 DCHECK(offset < DataTableStartOffset() ||
548 offset >= GetBucketsStartOffset());
549 WRITE_BYTE_FIELD(*this, offset + (index * kOneByteSize), value);
550 }
551
552 Offset GetDataEntryOffset(int entry, int relative_index) const {
553 DCHECK_LT(entry, Capacity());
554 int offset_in_datatable = entry * Derived::kEntrySize * kTaggedSize;
555 int offset_in_entry = relative_index * kTaggedSize;
556 return DataTableStartOffset() + offset_in_datatable + offset_in_entry;
557 }
558
559 int UsedCapacity() const {
560 int used = NumberOfElements() + NumberOfDeletedElements();
561 DCHECK_LE(used, Capacity());
562
563 return used;
564 }
565
566 private:
567 friend class OrderedHashMapHandler;
568 friend class OrderedHashSetHandler;
569 friend class OrderedNameDictionaryHandler;
570 friend class CodeStubAssembler;
571
572 OBJECT_CONSTRUCTORS(SmallOrderedHashTable, HeapObject);
573};
574
575class SmallOrderedHashSet : public SmallOrderedHashTable<SmallOrderedHashSet> {
576 public:
577 DECL_CAST(SmallOrderedHashSet)
578
579 DECL_PRINTER(SmallOrderedHashSet)
580 EXPORT_DECL_VERIFIER(SmallOrderedHashSet)
581
582 static const int kKeyIndex = 0;
583 static const int kEntrySize = 1;
584 static const int kPrefixSize = 0;
585
586 // Adds |value| to |table|, if the capacity isn't enough, a new
587 // table is created. The original |table| is returned if there is
588 // capacity to store |value| otherwise the new table is returned.
589 V8_EXPORT_PRIVATE static MaybeHandle<SmallOrderedHashSet> Add(
590 Isolate* isolate, Handle<SmallOrderedHashSet> table, Handle<Object> key);
591 V8_EXPORT_PRIVATE static bool Delete(Isolate* isolate,
592 SmallOrderedHashSet table, Object key);
593 V8_EXPORT_PRIVATE bool HasKey(Isolate* isolate, Handle<Object> key);
594
595 static inline bool Is(Handle<HeapObject> table);
596 static inline RootIndex GetMapRootIndex();
597 static Handle<SmallOrderedHashSet> Rehash(Isolate* isolate,
598 Handle<SmallOrderedHashSet> table,
599 int new_capacity);
600 OBJECT_CONSTRUCTORS(SmallOrderedHashSet,
601 SmallOrderedHashTable<SmallOrderedHashSet>);
602};
603
604STATIC_ASSERT(kSmallOrderedHashSetMinCapacity ==
605 SmallOrderedHashSet::kMinCapacity);
606
607class SmallOrderedHashMap : public SmallOrderedHashTable<SmallOrderedHashMap> {
608 public:
609 DECL_CAST(SmallOrderedHashMap)
610
611 DECL_PRINTER(SmallOrderedHashMap)
612 EXPORT_DECL_VERIFIER(SmallOrderedHashMap)
613
614 static const int kKeyIndex = 0;
615 static const int kValueIndex = 1;
616 static const int kEntrySize = 2;
617 static const int kPrefixSize = 0;
618
619 // Adds |value| to |table|, if the capacity isn't enough, a new
620 // table is created. The original |table| is returned if there is
621 // capacity to store |value| otherwise the new table is returned.
622 V8_EXPORT_PRIVATE static MaybeHandle<SmallOrderedHashMap> Add(
623 Isolate* isolate, Handle<SmallOrderedHashMap> table, Handle<Object> key,
624 Handle<Object> value);
625 V8_EXPORT_PRIVATE static bool Delete(Isolate* isolate,
626 SmallOrderedHashMap table, Object key);
627 V8_EXPORT_PRIVATE bool HasKey(Isolate* isolate, Handle<Object> key);
628 static inline bool Is(Handle<HeapObject> table);
629 static inline RootIndex GetMapRootIndex();
630
631 static Handle<SmallOrderedHashMap> Rehash(Isolate* isolate,
632 Handle<SmallOrderedHashMap> table,
633 int new_capacity);
634
635 OBJECT_CONSTRUCTORS(SmallOrderedHashMap,
636 SmallOrderedHashTable<SmallOrderedHashMap>);
637};
638
639STATIC_ASSERT(kSmallOrderedHashMapMinCapacity ==
640 SmallOrderedHashMap::kMinCapacity);
641
642// TODO(gsathya): Rename this to OrderedHashTable, after we rename
643// OrderedHashTable to LargeOrderedHashTable. Also set up a
644// OrderedHashSetBase class as a base class for the two tables and use
645// that instead of a HeapObject here.
646template <class SmallTable, class LargeTable>
647class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE) OrderedHashTableHandler {
648 public:
649 using Entry = int;
650
651 static Handle<HeapObject> Allocate(Isolate* isolate, int capacity);
652 static bool Delete(Handle<HeapObject> table, Handle<Object> key);
653 static bool HasKey(Isolate* isolate, Handle<HeapObject> table,
654 Handle<Object> key);
655
656 // TODO(gsathya): Move this to OrderedHashTable
657 static const int OrderedHashTableMinSize =
658 SmallOrderedHashTable<SmallTable>::kGrowthHack << 1;
659};
660
661extern template class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE)
662 OrderedHashTableHandler<SmallOrderedHashMap, OrderedHashMap>;
663
664class V8_EXPORT_PRIVATE OrderedHashMapHandler
665 : public OrderedHashTableHandler<SmallOrderedHashMap, OrderedHashMap> {
666 public:
667 static Handle<HeapObject> Add(Isolate* isolate, Handle<HeapObject> table,
668 Handle<Object> key, Handle<Object> value);
669 static Handle<OrderedHashMap> AdjustRepresentation(
670 Isolate* isolate, Handle<SmallOrderedHashMap> table);
671};
672
673extern template class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE)
674 OrderedHashTableHandler<SmallOrderedHashSet, OrderedHashSet>;
675
676class V8_EXPORT_PRIVATE OrderedHashSetHandler
677 : public OrderedHashTableHandler<SmallOrderedHashSet, OrderedHashSet> {
678 public:
679 static Handle<HeapObject> Add(Isolate* isolate, Handle<HeapObject> table,
680 Handle<Object> key);
681 static Handle<OrderedHashSet> AdjustRepresentation(
682 Isolate* isolate, Handle<SmallOrderedHashSet> table);
683};
684
685class OrderedNameDictionary
686 : public OrderedHashTable<OrderedNameDictionary, 3> {
687 public:
688 DECL_CAST(OrderedNameDictionary)
689
690 V8_EXPORT_PRIVATE static Handle<OrderedNameDictionary> Add(
691 Isolate* isolate, Handle<OrderedNameDictionary> table, Handle<Name> key,
692 Handle<Object> value, PropertyDetails details);
693
694 V8_EXPORT_PRIVATE void SetEntry(Isolate* isolate, int entry, Object key,
695 Object value, PropertyDetails details);
696
697 V8_EXPORT_PRIVATE static Handle<OrderedNameDictionary> DeleteEntry(
698 Isolate* isolate, Handle<OrderedNameDictionary> table, int entry);
699
700 static Handle<OrderedNameDictionary> Allocate(
701 Isolate* isolate, int capacity,
702 AllocationType allocation = AllocationType::kYoung);
703
704 static Handle<OrderedNameDictionary> Rehash(
705 Isolate* isolate, Handle<OrderedNameDictionary> table, int new_capacity);
706
707 // Returns the value for entry.
708 inline Object ValueAt(int entry);
709
710 // Set the value for entry.
711 inline void ValueAtPut(int entry, Object value);
712
713 // Returns the property details for the property at entry.
714 inline PropertyDetails DetailsAt(int entry);
715
716 // Set the details for entry.
717 inline void DetailsAtPut(int entry, PropertyDetails value);
718
719 inline void SetHash(int hash);
720 inline int Hash();
721
722 static HeapObject GetEmpty(ReadOnlyRoots ro_roots);
723 static inline RootIndex GetMapRootIndex();
724
725 static const int kValueOffset = 1;
726 static const int kPropertyDetailsOffset = 2;
727 static const int kPrefixSize = 1;
728
729 OBJECT_CONSTRUCTORS(OrderedNameDictionary,
730 OrderedHashTable<OrderedNameDictionary, 3>);
731};
732
733extern template class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE)
734 OrderedHashTableHandler<SmallOrderedNameDictionary, OrderedNameDictionary>;
735
736class V8_EXPORT_PRIVATE OrderedNameDictionaryHandler
737 : public OrderedHashTableHandler<SmallOrderedNameDictionary,
738 OrderedNameDictionary> {
739 public:
740 static Handle<HeapObject> Add(Isolate* isolate, Handle<HeapObject> table,
741 Handle<Name> key, Handle<Object> value,
742 PropertyDetails details);
743 static Handle<HeapObject> Shrink(Isolate* isolate, Handle<HeapObject> table);
744
745 static Handle<HeapObject> DeleteEntry(Isolate* isolate,
746 Handle<HeapObject> table, int entry);
747 static int FindEntry(Isolate* isolate, HeapObject table, Name key);
748 static void SetEntry(Isolate* isolate, HeapObject table, int entry,
749 Object key, Object value, PropertyDetails details);
750
751 // Returns the value for entry.
752 static Object ValueAt(HeapObject table, int entry);
753
754 // Set the value for entry.
755 static void ValueAtPut(HeapObject table, int entry, Object value);
756
757 // Returns the property details for the property at entry.
758 static PropertyDetails DetailsAt(HeapObject table, int entry);
759
760 // Set the details for entry.
761 static void DetailsAtPut(HeapObject table, int entry, PropertyDetails value);
762
763 static Name KeyAt(HeapObject table, int entry);
764
765 static void SetHash(HeapObject table, int hash);
766 static int Hash(HeapObject table);
767
768 static int NumberOfElements(HeapObject table);
769 static int Capacity(HeapObject table);
770
771 static const int kNotFound = -1;
772
773 protected:
774 static Handle<OrderedNameDictionary> AdjustRepresentation(
775 Isolate* isolate, Handle<SmallOrderedNameDictionary> table);
776};
777
778class SmallOrderedNameDictionary
779 : public SmallOrderedHashTable<SmallOrderedNameDictionary> {
780 public:
781 DECL_CAST(SmallOrderedNameDictionary)
782
783 DECL_PRINTER(SmallOrderedNameDictionary)
784 DECL_VERIFIER(SmallOrderedNameDictionary)
785
786 // Returns the value for entry.
787 inline Object ValueAt(int entry);
788
789 static Handle<SmallOrderedNameDictionary> Rehash(
790 Isolate* isolate, Handle<SmallOrderedNameDictionary> table,
791 int new_capacity);
792
793 V8_EXPORT_PRIVATE static Handle<SmallOrderedNameDictionary> DeleteEntry(
794 Isolate* isolate, Handle<SmallOrderedNameDictionary> table, int entry);
795
796 // Set the value for entry.
797 inline void ValueAtPut(int entry, Object value);
798
799 // Returns the property details for the property at entry.
800 inline PropertyDetails DetailsAt(int entry);
801
802 // Set the details for entry.
803 inline void DetailsAtPut(int entry, PropertyDetails value);
804
805 inline void SetHash(int hash);
806 inline int Hash();
807
808 static const int kKeyIndex = 0;
809 static const int kValueIndex = 1;
810 static const int kPropertyDetailsIndex = 2;
811 static const int kEntrySize = 3;
812 static const int kPrefixSize = 1;
813
814 // Adds |value| to |table|, if the capacity isn't enough, a new
815 // table is created. The original |table| is returned if there is
816 // capacity to store |value| otherwise the new table is returned.
817 V8_EXPORT_PRIVATE static MaybeHandle<SmallOrderedNameDictionary> Add(
818 Isolate* isolate, Handle<SmallOrderedNameDictionary> table,
819 Handle<Name> key, Handle<Object> value, PropertyDetails details);
820
821 V8_EXPORT_PRIVATE void SetEntry(Isolate* isolate, int entry, Object key,
822 Object value, PropertyDetails details);
823
824 static inline RootIndex GetMapRootIndex();
825
826 OBJECT_CONSTRUCTORS(SmallOrderedNameDictionary,
827 SmallOrderedHashTable<SmallOrderedNameDictionary>);
828};
829
830} // namespace internal
831} // namespace v8
832
833#include "src/objects/object-macros-undef.h"
834
835#endif // V8_OBJECTS_ORDERED_HASH_TABLE_H_
836