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