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 21347906 : int NumberOfElements() const {
87 21347906 : return Smi::ToInt(get(NumberOfElementsIndex()));
88 : }
89 :
90 20813644 : int NumberOfDeletedElements() const {
91 20813644 : 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 181716534 : int NumberOfBuckets() const {
101 181716534 : return Smi::ToInt(get(NumberOfBucketsIndex()));
102 : }
103 :
104 : // Returns an index into |this| for the given entry.
105 : int EntryToIndex(int entry) {
106 131516467 : return HashTableStartIndex() + NumberOfBuckets() + (entry * kEntrySize);
107 : }
108 :
109 39033764 : int HashToBucket(int hash) { return hash & (NumberOfBuckets() - 1); }
110 :
111 28976879 : int HashToEntry(int hash) {
112 : int bucket = HashToBucket(hash);
113 57953758 : Object entry = this->get(HashTableStartIndex() + bucket);
114 28976879 : return Smi::ToInt(entry);
115 : }
116 :
117 21062420 : int NextChainEntry(int entry) {
118 42124840 : Object next_entry = get(EntryToIndex(entry) + kChainOffset);
119 21062420 : return Smi::ToInt(next_entry);
120 : }
121 :
122 : // use KeyAt(i)->IsTheHole(isolate) to determine if this is a deleted entry.
123 52606644 : Object KeyAt(int entry) {
124 : DCHECK_LT(entry, this->UsedCapacity());
125 52606644 : return get(EntryToIndex(entry));
126 : }
127 :
128 1554 : bool IsObsolete() { return !get(NextTableIndex())->IsSmi(); }
129 :
130 : // The next newer table. This is only valid if the table is obsolete.
131 90 : Derived NextTable() { return Derived::cast(get(NextTableIndex())); }
132 :
133 : // When the table is obsolete we store the indexes of the removed holes.
134 15 : int RemovedIndexAt(int index) {
135 30 : 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(Isolate* isolate, int capacity,
200 : PretenureFlag pretenure = NOT_TENURED);
201 : static Handle<Derived> Rehash(Isolate* isolate, Handle<Derived> table,
202 : int new_capacity);
203 :
204 : void SetNumberOfBuckets(int num) {
205 : set(NumberOfBucketsIndex(), Smi::FromInt(num));
206 : }
207 :
208 : void SetNumberOfElements(int num) {
209 : set(NumberOfElementsIndex(), Smi::FromInt(num));
210 : }
211 :
212 : void SetNumberOfDeletedElements(int num) {
213 : set(NumberOfDeletedElementsIndex(), Smi::FromInt(num));
214 : }
215 :
216 : // Returns the number elements that can fit into the allocated buffer.
217 10389379 : int Capacity() { return NumberOfBuckets() * kLoadFactor; }
218 :
219 527892 : void SetNextTable(Derived next_table) { set(NextTableIndex(), next_table); }
220 :
221 243554 : void SetRemovedIndexAt(int index, int removed_index) {
222 243554 : return set(RemovedHolesIndex() + index, Smi::FromInt(removed_index));
223 : }
224 :
225 : OBJECT_CONSTRUCTORS(OrderedHashTable, FixedArray);
226 :
227 : private:
228 : friend class OrderedNameDictionaryHandler;
229 : };
230 :
231 : class OrderedHashSet : public OrderedHashTable<OrderedHashSet, 1> {
232 : public:
233 : DECL_CAST(OrderedHashSet)
234 :
235 : static Handle<OrderedHashSet> Add(Isolate* isolate,
236 : Handle<OrderedHashSet> table,
237 : Handle<Object> value);
238 : static Handle<FixedArray> ConvertToKeysArray(Isolate* isolate,
239 : Handle<OrderedHashSet> table,
240 : GetKeysConversion convert);
241 : static Handle<OrderedHashSet> Rehash(Isolate* isolate,
242 : Handle<OrderedHashSet> table,
243 : int new_capacity);
244 : static Handle<OrderedHashSet> Allocate(Isolate* isolate, int capacity,
245 : PretenureFlag pretenure = NOT_TENURED);
246 : static HeapObject GetEmpty(ReadOnlyRoots ro_roots);
247 : static inline RootIndex GetMapRootIndex();
248 : static inline bool Is(Handle<HeapObject> table);
249 : static const int kPrefixSize = 0;
250 :
251 : OBJECT_CONSTRUCTORS(OrderedHashSet, OrderedHashTable<OrderedHashSet, 1>);
252 : };
253 :
254 : class OrderedHashMap : public OrderedHashTable<OrderedHashMap, 2> {
255 : public:
256 : DECL_CAST(OrderedHashMap)
257 :
258 : // Returns a value if the OrderedHashMap contains the key, otherwise
259 : // returns undefined.
260 : static Handle<OrderedHashMap> Add(Isolate* isolate,
261 : Handle<OrderedHashMap> table,
262 : Handle<Object> key, Handle<Object> value);
263 :
264 : static Handle<OrderedHashMap> Allocate(Isolate* isolate, int capacity,
265 : PretenureFlag pretenure = NOT_TENURED);
266 : static Handle<OrderedHashMap> Rehash(Isolate* isolate,
267 : Handle<OrderedHashMap> table,
268 : int new_capacity);
269 : Object ValueAt(int entry);
270 :
271 : // This takes and returns raw Address values containing tagged Object
272 : // pointers because it is called via ExternalReference.
273 : static Address GetHash(Isolate* isolate, Address raw_key);
274 :
275 : static HeapObject GetEmpty(ReadOnlyRoots ro_roots);
276 : static inline RootIndex GetMapRootIndex();
277 : static inline bool Is(Handle<HeapObject> table);
278 :
279 : static const int kValueOffset = 1;
280 : static const int kPrefixSize = 0;
281 :
282 : OBJECT_CONSTRUCTORS(OrderedHashMap, OrderedHashTable<OrderedHashMap, 2>);
283 : };
284 :
285 : // This is similar to the OrderedHashTable, except for the memory
286 : // layout where we use byte instead of Smi. The max capacity of this
287 : // is only 254, we transition to an OrderedHashTable beyond that
288 : // limit.
289 : //
290 : // Each bucket and chain value is a byte long. The padding exists so
291 : // that the DataTable entries start aligned. A bucket or chain value
292 : // of 255 is used to denote an unknown entry.
293 : //
294 : // The prefix size is calculated as the kPrefixSize * kTaggedSize.
295 : //
296 : // Memory layout: [ Prefix ] [ Header ] [ Padding ] [ DataTable ] [ HashTable ]
297 : // [ Chains ]
298 : //
299 : // The index are represented as bytes, on a 64 bit machine with
300 : // kEntrySize = 1, capacity = 4 and entries = 2:
301 : //
302 : // [ 0 ] : Prefix
303 : //
304 : // Note: For the sake of brevity, the following start with index 0
305 : // but, they actually start from kPrefixSize * kTaggedSize to
306 : // account for the the prefix.
307 : //
308 : // [ Header ] :
309 : // [0] : Number of elements
310 : // [1] : Number of deleted elements
311 : // [2] : Number of buckets
312 : //
313 : // [ Padding ] :
314 : // [3 .. 7] : Padding
315 : //
316 : // [ DataTable ] :
317 : // [8 .. 15] : Entry 1
318 : // [16 .. 23] : Entry 2
319 : // [24 .. 31] : empty
320 : // [32 .. 39] : empty
321 : //
322 : // [ HashTable ] :
323 : // [40] : First chain-link for bucket 1
324 : // [41] : empty
325 : //
326 : // [ Chains ] :
327 : // [42] : Next chain link for bucket 1
328 : // [43] : empty
329 : // [44] : empty
330 : // [45] : empty
331 : //
332 : template <class Derived>
333 : class SmallOrderedHashTable : public HeapObject {
334 : public:
335 : // Offset points to a relative location in the table
336 : typedef int Offset;
337 :
338 : // ByteIndex points to a index in the table that needs to be
339 : // converted to an Offset.
340 : typedef int ByteIndex;
341 :
342 : void Initialize(Isolate* isolate, int capacity);
343 :
344 : static Handle<Derived> Allocate(Isolate* isolate, int capacity,
345 : PretenureFlag pretenure = NOT_TENURED);
346 :
347 : // Returns a true if the OrderedHashTable contains the key
348 : bool HasKey(Isolate* isolate, Handle<Object> key);
349 :
350 : // Returns a true value if the table contains the key and
351 : // the key has been deleted. This does not shrink the table.
352 : static bool Delete(Isolate* isolate, Derived table, Object key);
353 :
354 : // Returns an SmallOrderedHashTable (possibly |table|) with enough
355 : // space to add at least one new element. Returns empty handle if
356 : // we've already reached MaxCapacity.
357 : static MaybeHandle<Derived> Grow(Isolate* isolate, Handle<Derived> table);
358 :
359 : int FindEntry(Isolate* isolate, Object key);
360 : static Handle<Derived> Shrink(Isolate* isolate, Handle<Derived> table);
361 :
362 : // Iterates only fields in the DataTable.
363 : class BodyDescriptor;
364 :
365 : // Returns total size in bytes required for a table of given
366 : // capacity.
367 : static int SizeFor(int capacity) {
368 : DCHECK_GE(capacity, kMinCapacity);
369 : DCHECK_LE(capacity, kMaxCapacity);
370 :
371 : int data_table_size = DataTableSizeFor(capacity);
372 443 : int hash_table_size = capacity / kLoadFactor;
373 : int chain_table_size = capacity;
374 : int total_size = DataTableStartOffset() + data_table_size +
375 491 : hash_table_size + chain_table_size;
376 :
377 : return RoundUp(total_size, kTaggedSize);
378 : }
379 :
380 : // Returns the number elements that can fit into the allocated table.
381 : int Capacity() const {
382 1686888 : int capacity = NumberOfBuckets() * kLoadFactor;
383 : DCHECK_GE(capacity, kMinCapacity);
384 : DCHECK_LE(capacity, kMaxCapacity);
385 :
386 : return capacity;
387 : }
388 :
389 : // Returns the number elements that are present in the table.
390 : int NumberOfElements() const {
391 23575 : int nof_elements = getByte(NumberOfElementsOffset(), 0);
392 : DCHECK_LE(nof_elements, Capacity());
393 :
394 : return nof_elements;
395 : }
396 :
397 : int NumberOfDeletedElements() const {
398 22570 : int nof_deleted_elements = getByte(NumberOfDeletedElementsOffset(), 0);
399 : DCHECK_LE(nof_deleted_elements, Capacity());
400 :
401 : return nof_deleted_elements;
402 : }
403 :
404 2150536 : int NumberOfBuckets() const { return getByte(NumberOfBucketsOffset(), 0); }
405 :
406 : Object KeyAt(int entry) const {
407 : DCHECK_LT(entry, Capacity());
408 : Offset entry_offset = GetDataEntryOffset(entry, Derived::kKeyIndex);
409 3602865 : return READ_FIELD(*this, entry_offset);
410 : }
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 1674940 : 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 1653935 : 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 442595 : 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 3116625 : 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 21005 : setByte(GetChainTableOffset(), entry, next_entry);
483 : }
484 :
485 : int GetNextEntry(int entry) const {
486 : DCHECK_LT(entry, Capacity());
487 3095620 : return getByte(GetChainTableOffset(), entry);
488 : }
489 :
490 : Object GetDataEntry(int entry, int relative_index) {
491 : DCHECK_LT(entry, Capacity());
492 : DCHECK_LE(static_cast<unsigned>(relative_index), Derived::kEntrySize);
493 : Offset entry_offset = GetDataEntryOffset(entry, relative_index);
494 28335 : return READ_FIELD(*this, entry_offset);
495 : }
496 :
497 1664265 : int HashToBucket(int hash) const { return hash & (NumberOfBuckets() - 1); }
498 :
499 : int HashToFirstEntry(int hash) const {
500 : int bucket = HashToBucket(hash);
501 : int entry = GetFirstEntry(bucket);
502 : DCHECK(entry < Capacity() || entry == kNotFound);
503 : return entry;
504 : }
505 :
506 443 : void SetNumberOfBuckets(int num) { setByte(NumberOfBucketsOffset(), 0, num); }
507 :
508 : void SetNumberOfElements(int num) {
509 : DCHECK_LE(static_cast<unsigned>(num), Capacity());
510 11935 : setByte(NumberOfElementsOffset(), 0, num);
511 : }
512 :
513 : void SetNumberOfDeletedElements(int num) {
514 : DCHECK_LE(static_cast<unsigned>(num), Capacity());
515 1315 : setByte(NumberOfDeletedElementsOffset(), 0, num);
516 : }
517 :
518 32 : static constexpr Offset PrefixOffset() { return kHeaderSize; }
519 :
520 32 : static constexpr Offset NumberOfElementsOffset() {
521 32 : return PrefixOffset() + (Derived::kPrefixSize * kTaggedSize);
522 : }
523 :
524 24 : static constexpr Offset NumberOfDeletedElementsOffset() {
525 24 : return NumberOfElementsOffset() + kOneByteSize;
526 : }
527 :
528 16 : static constexpr Offset NumberOfBucketsOffset() {
529 16 : return NumberOfDeletedElementsOffset() + kOneByteSize;
530 : }
531 :
532 8 : static constexpr Offset DataTableStartOffset() {
533 8 : return RoundUp<kTaggedSize>(NumberOfBucketsOffset());
534 : }
535 :
536 : static constexpr int DataTableSizeFor(int capacity) {
537 2118469 : return capacity * Derived::kEntrySize * kTaggedSize;
538 : }
539 :
540 : // This is used for accessing the non |DataTable| part of the
541 : // structure.
542 : byte getByte(Offset offset, ByteIndex index) const {
543 : DCHECK(offset < DataTableStartOffset() ||
544 : offset >= GetBucketsStartOffset());
545 6947412 : return READ_BYTE_FIELD(*this, offset + (index * kOneByteSize));
546 : }
547 :
548 : void setByte(Offset offset, ByteIndex index, byte value) {
549 : DCHECK(offset < DataTableStartOffset() ||
550 : offset >= GetBucketsStartOffset());
551 56589 : WRITE_BYTE_FIELD(*this, offset + (index * kOneByteSize), value);
552 : }
553 :
554 : Offset GetDataEntryOffset(int entry, int relative_index) const {
555 : DCHECK_LT(entry, Capacity());
556 3655765 : int offset_in_datatable = entry * Derived::kEntrySize * kTaggedSize;
557 76040 : int offset_in_entry = relative_index * kTaggedSize;
558 3682775 : return DataTableStartOffset() + offset_in_datatable + offset_in_entry;
559 : }
560 :
561 : int UsedCapacity() const {
562 10350 : int used = NumberOfElements() + NumberOfDeletedElements();
563 : DCHECK_LE(used, Capacity());
564 :
565 : return used;
566 : }
567 :
568 : private:
569 : friend class OrderedHashMapHandler;
570 : friend class OrderedHashSetHandler;
571 : friend class OrderedNameDictionaryHandler;
572 : friend class CodeStubAssembler;
573 :
574 : OBJECT_CONSTRUCTORS(SmallOrderedHashTable, HeapObject);
575 : };
576 :
577 : class SmallOrderedHashSet : public SmallOrderedHashTable<SmallOrderedHashSet> {
578 : public:
579 : DECL_CAST(SmallOrderedHashSet)
580 :
581 : DECL_PRINTER(SmallOrderedHashSet)
582 : DECL_VERIFIER(SmallOrderedHashSet)
583 :
584 : static const int kKeyIndex = 0;
585 : static const int kEntrySize = 1;
586 : static const int kPrefixSize = 0;
587 :
588 : // Adds |value| to |table|, if the capacity isn't enough, a new
589 : // table is created. The original |table| is returned if there is
590 : // capacity to store |value| otherwise the new table is returned.
591 : static MaybeHandle<SmallOrderedHashSet> Add(Isolate* isolate,
592 : Handle<SmallOrderedHashSet> table,
593 : Handle<Object> key);
594 : static inline bool Is(Handle<HeapObject> table);
595 : static inline RootIndex GetMapRootIndex();
596 : static Handle<SmallOrderedHashSet> Rehash(Isolate* isolate,
597 : Handle<SmallOrderedHashSet> table,
598 : int new_capacity);
599 0 : OBJECT_CONSTRUCTORS(SmallOrderedHashSet,
600 : SmallOrderedHashTable<SmallOrderedHashSet>);
601 : };
602 :
603 : class SmallOrderedHashMap : public SmallOrderedHashTable<SmallOrderedHashMap> {
604 : public:
605 : DECL_CAST(SmallOrderedHashMap)
606 :
607 : DECL_PRINTER(SmallOrderedHashMap)
608 : DECL_VERIFIER(SmallOrderedHashMap)
609 :
610 : static const int kKeyIndex = 0;
611 : static const int kValueIndex = 1;
612 : static const int kEntrySize = 2;
613 : static const int kPrefixSize = 0;
614 :
615 : // Adds |value| to |table|, if the capacity isn't enough, a new
616 : // table is created. The original |table| is returned if there is
617 : // capacity to store |value| otherwise the new table is returned.
618 : static MaybeHandle<SmallOrderedHashMap> Add(Isolate* isolate,
619 : Handle<SmallOrderedHashMap> table,
620 : Handle<Object> key,
621 : Handle<Object> value);
622 : static inline bool Is(Handle<HeapObject> table);
623 : static inline RootIndex GetMapRootIndex();
624 :
625 : static Handle<SmallOrderedHashMap> Rehash(Isolate* isolate,
626 : Handle<SmallOrderedHashMap> table,
627 : int new_capacity);
628 :
629 0 : OBJECT_CONSTRUCTORS(SmallOrderedHashMap,
630 : SmallOrderedHashTable<SmallOrderedHashMap>);
631 : };
632 :
633 : // TODO(gsathya): Rename this to OrderedHashTable, after we rename
634 : // OrderedHashTable to LargeOrderedHashTable. Also set up a
635 : // OrderedHashSetBase class as a base class for the two tables and use
636 : // that instead of a HeapObject here.
637 : template <class SmallTable, class LargeTable>
638 : class OrderedHashTableHandler {
639 : public:
640 : typedef int Entry;
641 :
642 : static Handle<HeapObject> Allocate(Isolate* isolate, int capacity);
643 : static bool Delete(Handle<HeapObject> table, Handle<Object> key);
644 : static bool HasKey(Isolate* isolate, Handle<HeapObject> table,
645 : Handle<Object> key);
646 :
647 : // TODO(gsathya): Move this to OrderedHashTable
648 : static const int OrderedHashTableMinSize =
649 : SmallOrderedHashTable<SmallTable>::kGrowthHack << 1;
650 : };
651 :
652 : class OrderedHashMapHandler
653 : : public OrderedHashTableHandler<SmallOrderedHashMap, OrderedHashMap> {
654 : public:
655 : static Handle<HeapObject> Add(Isolate* isolate, Handle<HeapObject> table,
656 : Handle<Object> key, Handle<Object> value);
657 : static Handle<OrderedHashMap> AdjustRepresentation(
658 : Isolate* isolate, Handle<SmallOrderedHashMap> table);
659 : };
660 :
661 : class OrderedHashSetHandler
662 : : public OrderedHashTableHandler<SmallOrderedHashSet, OrderedHashSet> {
663 : public:
664 : static Handle<HeapObject> Add(Isolate* isolate, Handle<HeapObject> table,
665 : Handle<Object> key);
666 : static Handle<OrderedHashSet> AdjustRepresentation(
667 : Isolate* isolate, Handle<SmallOrderedHashSet> table);
668 : };
669 :
670 : class OrderedNameDictionary
671 : : public OrderedHashTable<OrderedNameDictionary, 3> {
672 : public:
673 : DECL_CAST(OrderedNameDictionary)
674 :
675 : static Handle<OrderedNameDictionary> Add(Isolate* isolate,
676 : Handle<OrderedNameDictionary> table,
677 : Handle<Name> key,
678 : Handle<Object> value,
679 : PropertyDetails details);
680 :
681 : void SetEntry(Isolate* isolate, int entry, Object key, Object value,
682 : PropertyDetails details);
683 :
684 : static Handle<OrderedNameDictionary> DeleteEntry(
685 : Isolate* isolate, Handle<OrderedNameDictionary> table, int entry);
686 :
687 : static Handle<OrderedNameDictionary> Allocate(
688 : Isolate* isolate, int capacity, PretenureFlag pretenure = NOT_TENURED);
689 :
690 : static Handle<OrderedNameDictionary> Rehash(
691 : Isolate* isolate, Handle<OrderedNameDictionary> table, int new_capacity);
692 :
693 : // Returns the value for entry.
694 : inline Object ValueAt(int entry);
695 :
696 : // Set the value for entry.
697 : inline void ValueAtPut(int entry, Object value);
698 :
699 : // Returns the property details for the property at entry.
700 : inline PropertyDetails DetailsAt(int entry);
701 :
702 : // Set the details for entry.
703 : inline void DetailsAtPut(int entry, PropertyDetails value);
704 :
705 : inline void SetHash(int hash);
706 : inline int Hash();
707 :
708 : static HeapObject GetEmpty(ReadOnlyRoots ro_roots);
709 : static inline RootIndex GetMapRootIndex();
710 :
711 : static const int kValueOffset = 1;
712 : static const int kPropertyDetailsOffset = 2;
713 : static const int kPrefixSize = 1;
714 :
715 : OBJECT_CONSTRUCTORS(OrderedNameDictionary,
716 : OrderedHashTable<OrderedNameDictionary, 3>);
717 : };
718 :
719 : class OrderedNameDictionaryHandler
720 : : public OrderedHashTableHandler<SmallOrderedNameDictionary,
721 : OrderedNameDictionary> {
722 : public:
723 : static Handle<HeapObject> Add(Isolate* isolate, Handle<HeapObject> table,
724 : Handle<Name> key, Handle<Object> value,
725 : PropertyDetails details);
726 : static Handle<HeapObject> Shrink(Isolate* isolate, Handle<HeapObject> table);
727 :
728 : static Handle<HeapObject> DeleteEntry(Isolate* isolate,
729 : Handle<HeapObject> table, int entry);
730 : static int FindEntry(Isolate* isolate, HeapObject table, Name key);
731 : static void SetEntry(Isolate* isolate, HeapObject table, int entry,
732 : Object key, Object value, PropertyDetails details);
733 :
734 : // Returns the value for entry.
735 : static Object ValueAt(HeapObject table, int entry);
736 :
737 : // Set the value for entry.
738 : static void ValueAtPut(HeapObject table, int entry, Object value);
739 :
740 : // Returns the property details for the property at entry.
741 : static PropertyDetails DetailsAt(HeapObject table, int entry);
742 :
743 : // Set the details for entry.
744 : static void DetailsAtPut(HeapObject table, int entry, PropertyDetails value);
745 :
746 : static Name KeyAt(HeapObject table, int entry);
747 :
748 : static void SetHash(HeapObject table, int hash);
749 : static int Hash(HeapObject table);
750 :
751 : static int NumberOfElements(HeapObject table);
752 : static int Capacity(HeapObject table);
753 :
754 : static const int kNotFound = -1;
755 :
756 : protected:
757 : static Handle<OrderedNameDictionary> AdjustRepresentation(
758 : Isolate* isolate, Handle<SmallOrderedNameDictionary> table);
759 : };
760 :
761 : class SmallOrderedNameDictionary
762 : : public SmallOrderedHashTable<SmallOrderedNameDictionary> {
763 : public:
764 : DECL_CAST(SmallOrderedNameDictionary)
765 :
766 : DECL_PRINTER(SmallOrderedNameDictionary)
767 : DECL_VERIFIER(SmallOrderedNameDictionary)
768 :
769 : // Returns the value for entry.
770 : inline Object ValueAt(int entry);
771 :
772 : static Handle<SmallOrderedNameDictionary> Rehash(
773 : Isolate* isolate, Handle<SmallOrderedNameDictionary> table,
774 : int new_capacity);
775 :
776 : static Handle<SmallOrderedNameDictionary> DeleteEntry(
777 : Isolate* isolate, Handle<SmallOrderedNameDictionary> table, int entry);
778 :
779 : // Set the value for entry.
780 : inline void ValueAtPut(int entry, Object value);
781 :
782 : // Returns the property details for the property at entry.
783 : inline PropertyDetails DetailsAt(int entry);
784 :
785 : // Set the details for entry.
786 : inline void DetailsAtPut(int entry, PropertyDetails value);
787 :
788 : inline void SetHash(int hash);
789 : inline int Hash();
790 :
791 : static const int kKeyIndex = 0;
792 : static const int kValueIndex = 1;
793 : static const int kPropertyDetailsIndex = 2;
794 : static const int kEntrySize = 3;
795 : static const int kPrefixSize = 1;
796 :
797 : // Adds |value| to |table|, if the capacity isn't enough, a new
798 : // table is created. The original |table| is returned if there is
799 : // capacity to store |value| otherwise the new table is returned.
800 : static MaybeHandle<SmallOrderedNameDictionary> Add(
801 : Isolate* isolate, Handle<SmallOrderedNameDictionary> table,
802 : Handle<Name> key, Handle<Object> value, PropertyDetails details);
803 :
804 : void SetEntry(Isolate* isolate, int entry, Object key, Object value,
805 : PropertyDetails details);
806 :
807 : static inline RootIndex GetMapRootIndex();
808 :
809 0 : OBJECT_CONSTRUCTORS(SmallOrderedNameDictionary,
810 : SmallOrderedHashTable<SmallOrderedNameDictionary>);
811 : };
812 :
813 : class JSCollectionIterator : public JSObject {
814 : public:
815 : // [table]: the backing hash table mapping keys to values.
816 : DECL_ACCESSORS(table, Object)
817 :
818 : // [index]: The index into the data table.
819 : DECL_ACCESSORS(index, Object)
820 :
821 : void JSCollectionIteratorPrint(std::ostream& os, const char* name);
822 :
823 : // Layout description.
824 : #define JS_COLLECTION_ITERATOR_FIELDS(V) \
825 : V(kTableOffset, kTaggedSize) \
826 : V(kIndexOffset, kTaggedSize) \
827 : /* Header size. */ \
828 : V(kSize, 0)
829 :
830 : DEFINE_FIELD_OFFSET_CONSTANTS(JSObject::kHeaderSize,
831 : JS_COLLECTION_ITERATOR_FIELDS)
832 : #undef JS_COLLECTION_ITERATOR_FIELDS
833 :
834 : OBJECT_CONSTRUCTORS(JSCollectionIterator, JSObject);
835 : };
836 :
837 : // OrderedHashTableIterator is an iterator that iterates over the keys and
838 : // values of an OrderedHashTable.
839 : //
840 : // The iterator has a reference to the underlying OrderedHashTable data,
841 : // [table], as well as the current [index] the iterator is at.
842 : //
843 : // When the OrderedHashTable is rehashed it adds a reference from the old table
844 : // to the new table as well as storing enough data about the changes so that the
845 : // iterator [index] can be adjusted accordingly.
846 : //
847 : // When the [Next] result from the iterator is requested, the iterator checks if
848 : // there is a newer table that it needs to transition to.
849 : template <class Derived, class TableType>
850 : class OrderedHashTableIterator : public JSCollectionIterator {
851 : public:
852 : // Whether the iterator has more elements. This needs to be called before
853 : // calling |CurrentKey| and/or |CurrentValue|.
854 : bool HasMore();
855 :
856 : // Move the index forward one.
857 0 : void MoveNext() { set_index(Smi::FromInt(Smi::ToInt(index()) + 1)); }
858 :
859 : // Returns the current key of the iterator. This should only be called when
860 : // |HasMore| returns true.
861 : inline Object CurrentKey();
862 :
863 : private:
864 : // Transitions the iterator to the non obsolete backing store. This is a NOP
865 : // if the [table] is not obsolete.
866 : void Transition();
867 :
868 : OBJECT_CONSTRUCTORS(OrderedHashTableIterator, JSCollectionIterator);
869 : };
870 :
871 : } // namespace internal
872 : } // namespace v8
873 :
874 : #include "src/objects/object-macros-undef.h"
875 :
876 : #endif // V8_OBJECTS_ORDERED_HASH_TABLE_H_
|
