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 : #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 :
18 : namespace v8 {
19 : namespace 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
62 : template <class Derived, int entrysize>
63 : class 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 1369 : int UsedCapacity() const {
98 1369 : 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 133276310 : return HashTableStartIndex() + NumberOfBuckets() + (entry * kEntrySize);
108 : }
109 :
110 39057038 : int HashToBucket(int hash) { return hash & (NumberOfBuckets() - 1); }
111 :
112 28992395 : int HashToEntry(int hash) {
113 : int bucket = HashToBucket(hash);
114 28992395 : Object entry = this->get(HashTableStartIndex() + bucket);
115 28992395 : return Smi::ToInt(entry);
116 : }
117 :
118 21928638 : int NextChainEntry(int entry) {
119 21928638 : Object next_entry = get(EntryToIndex(entry) + kChainOffset);
120 21928638 : return Smi::ToInt(next_entry);
121 : }
122 :
123 : // use KeyAt(i)->IsTheHole(isolate) to determine if this is a deleted entry.
124 53470336 : Object KeyAt(int entry) {
125 : DCHECK_LT(entry, this->UsedCapacity());
126 53470336 : 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 15 : 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 10384098 : int Capacity() { return NumberOfBuckets() * kLoadFactor; }
220 :
221 515050 : 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 :
233 : class 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 :
258 : class 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 : //
338 : template <class Derived>
339 : class 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 443 : int hash_table_size = capacity / kLoadFactor;
380 : int chain_table_size = capacity;
381 : int total_size = DataTableStartOffset() + data_table_size +
382 491 : 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 1676213 : 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 24048 : int nof_elements = getByte(NumberOfElementsOffset(), 0);
399 : DCHECK_LE(nof_elements, Capacity());
400 :
401 : return nof_elements;
402 : }
403 :
404 : int NumberOfDeletedElements() const {
405 22858 : int nof_deleted_elements = getByte(NumberOfDeletedElementsOffset(), 0);
406 : DCHECK_LE(nof_deleted_elements, Capacity());
407 :
408 : return nof_deleted_elements;
409 : }
410 :
411 2119253 : 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 1664265 : return DataTableStartOffset() + data_table_size;
452 : }
453 :
454 : Address GetHashTableStartAddress(int capacity) const {
455 886 : 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 1632930 : 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 442625 : 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 3067315 : 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 3046310 : return getByte(GetChainTableOffset(), entry);
491 : }
492 :
493 : V8_INLINE Object GetDataEntry(int entry, int relative_index);
494 :
495 1653935 : 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 2107824 : 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 6856074 : 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 56589 : WRITE_BYTE_FIELD(*this, offset + (index * kOneByteSize), value);
550 : }
551 :
552 2600 : Offset GetDataEntryOffset(int entry, int relative_index) const {
553 : DCHECK_LT(entry, Capacity());
554 3607730 : int offset_in_datatable = entry * Derived::kEntrySize * kTaggedSize;
555 78640 : int offset_in_entry = relative_index * kTaggedSize;
556 3633465 : return DataTableStartOffset() + offset_in_datatable + offset_in_entry;
557 : }
558 :
559 : int UsedCapacity() const {
560 10350 : 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 :
575 : class 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 :
604 : STATIC_ASSERT(kSmallOrderedHashSetMinCapacity ==
605 : SmallOrderedHashSet::kMinCapacity);
606 :
607 : class 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 :
639 : STATIC_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.
646 : template <class SmallTable, class LargeTable>
647 : class 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 :
661 : extern template class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE)
662 : OrderedHashTableHandler<SmallOrderedHashMap, OrderedHashMap>;
663 :
664 : class 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 :
673 : extern template class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE)
674 : OrderedHashTableHandler<SmallOrderedHashSet, OrderedHashSet>;
675 :
676 : class 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 :
685 : class 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 :
733 : extern template class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE)
734 : OrderedHashTableHandler<SmallOrderedNameDictionary, OrderedNameDictionary>;
735 :
736 : class 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 :
778 : class 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_
|
