Line data Source code
1 : // Copyright 2017 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_HASH_TABLE_H_
6 : #define V8_OBJECTS_HASH_TABLE_H_
7 :
8 : #include "src/objects.h"
9 :
10 : // Has to be the last include (doesn't have include guards):
11 : #include "src/objects/object-macros.h"
12 :
13 : namespace v8 {
14 : namespace internal {
15 :
16 : // HashTable is a subclass of FixedArray that implements a hash table
17 : // that uses open addressing and quadratic probing.
18 : //
19 : // In order for the quadratic probing to work, elements that have not
20 : // yet been used and elements that have been deleted are
21 : // distinguished. Probing continues when deleted elements are
22 : // encountered and stops when unused elements are encountered.
23 : //
24 : // - Elements with key == undefined have not been used yet.
25 : // - Elements with key == the_hole have been deleted.
26 : //
27 : // The hash table class is parameterized with a Shape and a Key.
28 : // Shape must be a class with the following interface:
29 : // class ExampleShape {
30 : // public:
31 : // // Tells whether key matches other.
32 : // static bool IsMatch(Key key, Object* other);
33 : // // Returns the hash value for key.
34 : // static uint32_t Hash(Key key);
35 : // // Returns the hash value for object.
36 : // static uint32_t HashForObject(Key key, Object* object);
37 : // // Convert key to an object.
38 : // static inline Handle<Object> AsHandle(Isolate* isolate, Key key);
39 : // // The prefix size indicates number of elements in the beginning
40 : // // of the backing storage.
41 : // static const int kPrefixSize = ..;
42 : // // The Element size indicates number of elements per entry.
43 : // static const int kEntrySize = ..;
44 : // };
45 : // The prefix size indicates an amount of memory in the
46 : // beginning of the backing storage that can be used for non-element
47 : // information by subclasses.
48 :
49 : template <typename Key>
50 : class BaseShape {
51 : public:
52 : static const bool UsesSeed = false;
53 : static uint32_t Hash(Key key) { return 0; }
54 : static uint32_t SeededHash(Key key, uint32_t seed) {
55 : DCHECK(UsesSeed);
56 : return Hash(key);
57 : }
58 : static uint32_t HashForObject(Key key, Object* object) { return 0; }
59 : static uint32_t SeededHashForObject(Key key, uint32_t seed, Object* object) {
60 : DCHECK(UsesSeed);
61 : return HashForObject(key, object);
62 : }
63 : static inline Map* GetMap(Isolate* isolate);
64 : };
65 :
66 : class HashTableBase : public FixedArray {
67 : public:
68 : // Returns the number of elements in the hash table.
69 : inline int NumberOfElements();
70 :
71 : // Returns the number of deleted elements in the hash table.
72 : inline int NumberOfDeletedElements();
73 :
74 : // Returns the capacity of the hash table.
75 : inline int Capacity();
76 :
77 : // ElementAdded should be called whenever an element is added to a
78 : // hash table.
79 : inline void ElementAdded();
80 :
81 : // ElementRemoved should be called whenever an element is removed from
82 : // a hash table.
83 : inline void ElementRemoved();
84 : inline void ElementsRemoved(int n);
85 :
86 : // Computes the required capacity for a table holding the given
87 : // number of elements. May be more than HashTable::kMaxCapacity.
88 : static inline int ComputeCapacity(int at_least_space_for);
89 :
90 : // Tells whether k is a real key. The hole and undefined are not allowed
91 : // as keys and can be used to indicate missing or deleted elements.
92 : inline bool IsKey(Isolate* isolate, Object* k);
93 :
94 : // Compute the probe offset (quadratic probing).
95 : INLINE(static uint32_t GetProbeOffset(uint32_t n)) {
96 5644 : return (n + n * n) >> 1;
97 : }
98 :
99 : static const int kNumberOfElementsIndex = 0;
100 : static const int kNumberOfDeletedElementsIndex = 1;
101 : static const int kCapacityIndex = 2;
102 : static const int kPrefixStartIndex = 3;
103 :
104 : // Constant used for denoting a absent entry.
105 : static const int kNotFound = -1;
106 :
107 : // Minimum capacity for newly created hash tables.
108 : static const int kMinCapacity = 4;
109 :
110 : protected:
111 : // Update the number of elements in the hash table.
112 : inline void SetNumberOfElements(int nof);
113 :
114 : // Update the number of deleted elements in the hash table.
115 : inline void SetNumberOfDeletedElements(int nod);
116 :
117 : // Returns probe entry.
118 : static uint32_t GetProbe(uint32_t hash, uint32_t number, uint32_t size) {
119 : DCHECK(base::bits::IsPowerOfTwo32(size));
120 : return (hash + GetProbeOffset(number)) & (size - 1);
121 : }
122 :
123 : inline static uint32_t FirstProbe(uint32_t hash, uint32_t size) {
124 497720433 : return hash & (size - 1);
125 : }
126 :
127 : inline static uint32_t NextProbe(uint32_t last, uint32_t number,
128 : uint32_t size) {
129 339430613 : return (last + number) & (size - 1);
130 : }
131 : };
132 :
133 : template <typename Derived, typename Shape, typename Key>
134 : class HashTable : public HashTableBase {
135 : public:
136 : typedef Shape ShapeT;
137 :
138 : // Wrapper methods
139 145221511 : inline uint32_t Hash(Key key) {
140 : if (Shape::UsesSeed) {
141 : return Shape::SeededHash(key, GetHeap()->HashSeed());
142 : } else {
143 33151133 : return Shape::Hash(key);
144 : }
145 : }
146 :
147 0 : inline uint32_t HashForObject(Key key, Object* object) {
148 : if (Shape::UsesSeed) {
149 3607223 : return Shape::SeededHashForObject(key, GetHeap()->HashSeed(), object);
150 : } else {
151 1481288 : return Shape::HashForObject(key, object);
152 : }
153 : }
154 :
155 : // Returns a new HashTable object.
156 : MUST_USE_RESULT static Handle<Derived> New(
157 : Isolate* isolate, int at_least_space_for,
158 : MinimumCapacity capacity_option = USE_DEFAULT_MINIMUM_CAPACITY,
159 : PretenureFlag pretenure = NOT_TENURED);
160 :
161 : DECLARE_CAST(HashTable)
162 :
163 : // Garbage collection support.
164 : void IteratePrefix(ObjectVisitor* visitor);
165 : void IterateElements(ObjectVisitor* visitor);
166 :
167 : // Find entry for key otherwise return kNotFound.
168 : inline int FindEntry(Key key);
169 : inline int FindEntry(Isolate* isolate, Key key, int32_t hash);
170 : int FindEntry(Isolate* isolate, Key key);
171 : inline bool Has(Isolate* isolate, Key key);
172 : inline bool Has(Key key);
173 :
174 : // Rehashes the table in-place.
175 : void Rehash(Key key);
176 :
177 : // Returns the key at entry.
178 0 : Object* KeyAt(int entry) { return get(EntryToIndex(entry) + kEntryKeyIndex); }
179 :
180 : static const int kElementsStartIndex = kPrefixStartIndex + Shape::kPrefixSize;
181 : static const int kEntrySize = Shape::kEntrySize;
182 : STATIC_ASSERT(kEntrySize > 0);
183 : static const int kEntryKeyIndex = 0;
184 : static const int kElementsStartOffset =
185 : kHeaderSize + kElementsStartIndex * kPointerSize;
186 : // Maximal capacity of HashTable. Based on maximal length of underlying
187 : // FixedArray. Staying below kMaxCapacity also ensures that EntryToIndex
188 : // cannot overflow.
189 : static const int kMaxCapacity =
190 : (FixedArray::kMaxLength - kElementsStartIndex) / kEntrySize;
191 :
192 : // Returns the index for an entry (of the key)
193 0 : static inline int EntryToIndex(int entry) {
194 1650315022 : return (entry * kEntrySize) + kElementsStartIndex;
195 : }
196 :
197 : protected:
198 : friend class ObjectHashTable;
199 :
200 : MUST_USE_RESULT static Handle<Derived> New(Isolate* isolate, int capacity,
201 : PretenureFlag pretenure);
202 :
203 : // Find the entry at which to insert element with the given key that
204 : // has the given hash value.
205 : uint32_t FindInsertionEntry(uint32_t hash);
206 :
207 : // Attempt to shrink hash table after removal of key.
208 : MUST_USE_RESULT static Handle<Derived> Shrink(Handle<Derived> table, Key key);
209 :
210 : // Ensure enough space for n additional elements.
211 : MUST_USE_RESULT static Handle<Derived> EnsureCapacity(
212 : Handle<Derived> table, int n, Key key,
213 : PretenureFlag pretenure = NOT_TENURED);
214 :
215 : // Returns true if this table has sufficient capacity for adding n elements.
216 : bool HasSufficientCapacityToAdd(int number_of_additional_elements);
217 :
218 : // Sets the capacity of the hash table.
219 0 : void SetCapacity(int capacity) {
220 : // To scale a computed hash code to fit within the hash table, we
221 : // use bit-wise AND with a mask, so the capacity must be positive
222 : // and non-zero.
223 : DCHECK(capacity > 0);
224 : DCHECK(capacity <= kMaxCapacity);
225 : set(kCapacityIndex, Smi::FromInt(capacity));
226 0 : }
227 :
228 : private:
229 : // Returns _expected_ if one of entries given by the first _probe_ probes is
230 : // equal to _expected_. Otherwise, returns the entry given by the probe
231 : // number _probe_.
232 : uint32_t EntryForProbe(Key key, Object* k, int probe, uint32_t expected);
233 :
234 : void Swap(uint32_t entry1, uint32_t entry2, WriteBarrierMode mode);
235 :
236 : // Rehashes this hash-table into the new table.
237 : void Rehash(Handle<Derived> new_table, Key key);
238 : };
239 :
240 : // HashTableKey is an abstract superclass for virtual key behavior.
241 105686262 : class HashTableKey {
242 : public:
243 : // Returns whether the other object matches this key.
244 : virtual bool IsMatch(Object* other) = 0;
245 : // Returns the hash value for this key.
246 : virtual uint32_t Hash() = 0;
247 : // Returns the hash value for object.
248 : virtual uint32_t HashForObject(Object* key) = 0;
249 : // Returns the key object for storing into the hash table.
250 : MUST_USE_RESULT virtual Handle<Object> AsHandle(Isolate* isolate) = 0;
251 : // Required.
252 30357 : virtual ~HashTableKey() {}
253 : };
254 :
255 : class ObjectHashTableShape : public BaseShape<Handle<Object>> {
256 : public:
257 : static inline bool IsMatch(Handle<Object> key, Object* other);
258 : static inline uint32_t Hash(Handle<Object> key);
259 : static inline uint32_t HashForObject(Handle<Object> key, Object* object);
260 : static inline Handle<Object> AsHandle(Isolate* isolate, Handle<Object> key);
261 : static const int kPrefixSize = 0;
262 : static const int kEntrySize = 2;
263 : };
264 :
265 : // ObjectHashTable maps keys that are arbitrary objects to object values by
266 : // using the identity hash of the key for hashing purposes.
267 : class ObjectHashTable
268 : : public HashTable<ObjectHashTable, ObjectHashTableShape, Handle<Object>> {
269 : typedef HashTable<ObjectHashTable, ObjectHashTableShape, Handle<Object>>
270 : DerivedHashTable;
271 :
272 : public:
273 : DECLARE_CAST(ObjectHashTable)
274 :
275 : // Attempt to shrink hash table after removal of key.
276 : MUST_USE_RESULT static inline Handle<ObjectHashTable> Shrink(
277 : Handle<ObjectHashTable> table, Handle<Object> key);
278 :
279 : // Looks up the value associated with the given key. The hole value is
280 : // returned in case the key is not present.
281 : Object* Lookup(Handle<Object> key);
282 : Object* Lookup(Handle<Object> key, int32_t hash);
283 : Object* Lookup(Isolate* isolate, Handle<Object> key, int32_t hash);
284 :
285 : // Returns the value at entry.
286 : Object* ValueAt(int entry);
287 :
288 : // Adds (or overwrites) the value associated with the given key.
289 : static Handle<ObjectHashTable> Put(Handle<ObjectHashTable> table,
290 : Handle<Object> key, Handle<Object> value);
291 : static Handle<ObjectHashTable> Put(Handle<ObjectHashTable> table,
292 : Handle<Object> key, Handle<Object> value,
293 : int32_t hash);
294 :
295 : // Returns an ObjectHashTable (possibly |table|) where |key| has been removed.
296 : static Handle<ObjectHashTable> Remove(Handle<ObjectHashTable> table,
297 : Handle<Object> key, bool* was_present);
298 : static Handle<ObjectHashTable> Remove(Handle<ObjectHashTable> table,
299 : Handle<Object> key, bool* was_present,
300 : int32_t hash);
301 :
302 : protected:
303 : friend class MarkCompactCollector;
304 :
305 : void AddEntry(int entry, Object* key, Object* value);
306 : void RemoveEntry(int entry);
307 :
308 : // Returns the index to the value of an entry.
309 : static inline int EntryToValueIndex(int entry) {
310 27543 : return EntryToIndex(entry) + 1;
311 : }
312 : };
313 :
314 : class ObjectHashSetShape : public ObjectHashTableShape {
315 : public:
316 : static const int kPrefixSize = 0;
317 : static const int kEntrySize = 1;
318 : };
319 :
320 : class ObjectHashSet
321 : : public HashTable<ObjectHashSet, ObjectHashSetShape, Handle<Object>> {
322 : public:
323 : static Handle<ObjectHashSet> Add(Handle<ObjectHashSet> set,
324 : Handle<Object> key);
325 :
326 : inline bool Has(Isolate* isolate, Handle<Object> key, int32_t hash);
327 : inline bool Has(Isolate* isolate, Handle<Object> key);
328 :
329 : DECLARE_CAST(ObjectHashSet)
330 : };
331 :
332 : // OrderedHashTable is a HashTable with Object keys that preserves
333 : // insertion order. There are Map and Set interfaces (OrderedHashMap
334 : // and OrderedHashTable, below). It is meant to be used by JSMap/JSSet.
335 : //
336 : // Only Object* keys are supported, with Object::SameValueZero() used as the
337 : // equality operator and Object::GetHash() for the hash function.
338 : //
339 : // Based on the "Deterministic Hash Table" as described by Jason Orendorff at
340 : // https://wiki.mozilla.org/User:Jorend/Deterministic_hash_tables
341 : // Originally attributed to Tyler Close.
342 : //
343 : // Memory layout:
344 : // [0]: element count
345 : // [1]: deleted element count
346 : // [2]: bucket count
347 : // [3..(3 + NumberOfBuckets() - 1)]: "hash table", where each item is an
348 : // offset into the data table (see below) where the
349 : // first item in this bucket is stored.
350 : // [3 + NumberOfBuckets()..length]: "data table", an array of length
351 : // Capacity() * kEntrySize, where the first entrysize
352 : // items are handled by the derived class and the
353 : // item at kChainOffset is another entry into the
354 : // data table indicating the next entry in this hash
355 : // bucket.
356 : //
357 : // When we transition the table to a new version we obsolete it and reuse parts
358 : // of the memory to store information how to transition an iterator to the new
359 : // table:
360 : //
361 : // Memory layout for obsolete table:
362 : // [0]: bucket count
363 : // [1]: Next newer table
364 : // [2]: Number of removed holes or -1 when the table was cleared.
365 : // [3..(3 + NumberOfRemovedHoles() - 1)]: The indexes of the removed holes.
366 : // [3 + NumberOfRemovedHoles()..length]: Not used
367 : //
368 : template <class Derived, int entrysize>
369 : class OrderedHashTable : public FixedArray {
370 : public:
371 : // Returns an OrderedHashTable with a capacity of at least |capacity|.
372 : static Handle<Derived> Allocate(Isolate* isolate, int capacity,
373 : PretenureFlag pretenure = NOT_TENURED);
374 :
375 : // Returns an OrderedHashTable (possibly |table|) with enough space
376 : // to add at least one new element.
377 : static Handle<Derived> EnsureGrowable(Handle<Derived> table);
378 :
379 : // Returns an OrderedHashTable (possibly |table|) that's shrunken
380 : // if possible.
381 : static Handle<Derived> Shrink(Handle<Derived> table);
382 :
383 : // Returns a new empty OrderedHashTable and records the clearing so that
384 : // existing iterators can be updated.
385 : static Handle<Derived> Clear(Handle<Derived> table);
386 :
387 : // Returns a true if the OrderedHashTable contains the key
388 : static bool HasKey(Handle<Derived> table, Handle<Object> key);
389 :
390 : int NumberOfElements() {
391 : return Smi::cast(get(kNumberOfElementsIndex))->value();
392 : }
393 :
394 : int NumberOfDeletedElements() {
395 : return Smi::cast(get(kNumberOfDeletedElementsIndex))->value();
396 : }
397 :
398 : // Returns the number of contiguous entries in the data table, starting at 0,
399 : // that either are real entries or have been deleted.
400 25642 : int UsedCapacity() { return NumberOfElements() + NumberOfDeletedElements(); }
401 :
402 : int NumberOfBuckets() {
403 : return Smi::cast(get(kNumberOfBucketsIndex))->value();
404 : }
405 :
406 : // Returns an index into |this| for the given entry.
407 : int EntryToIndex(int entry) {
408 217722968 : return kHashTableStartIndex + NumberOfBuckets() + (entry * kEntrySize);
409 : }
410 :
411 235381850 : int HashToBucket(int hash) { return hash & (NumberOfBuckets() - 1); }
412 :
413 156921509 : int HashToEntry(int hash) {
414 : int bucket = HashToBucket(hash);
415 156921509 : Object* entry = this->get(kHashTableStartIndex + bucket);
416 156921509 : return Smi::cast(entry)->value();
417 : }
418 :
419 0 : int KeyToFirstEntry(Isolate* isolate, Object* key) {
420 0 : Object* hash = key->GetHash();
421 : // If the object does not have an identity hash, it was never used as a key
422 0 : if (hash->IsUndefined(isolate)) return kNotFound;
423 0 : return HashToEntry(Smi::cast(hash)->value());
424 : }
425 :
426 50517032 : int NextChainEntry(int entry) {
427 50517032 : Object* next_entry = get(EntryToIndex(entry) + kChainOffset);
428 50517032 : return Smi::cast(next_entry)->value();
429 : }
430 :
431 : // use KeyAt(i)->IsTheHole(isolate) to determine if this is a deleted entry.
432 63426114 : Object* KeyAt(int entry) {
433 : DCHECK_LT(entry, this->UsedCapacity());
434 63426114 : return get(EntryToIndex(entry));
435 : }
436 :
437 : bool IsObsolete() { return !get(kNextTableIndex)->IsSmi(); }
438 :
439 : // The next newer table. This is only valid if the table is obsolete.
440 : Derived* NextTable() { return Derived::cast(get(kNextTableIndex)); }
441 :
442 : // When the table is obsolete we store the indexes of the removed holes.
443 : int RemovedIndexAt(int index) {
444 224 : return Smi::cast(get(kRemovedHolesIndex + index))->value();
445 : }
446 :
447 : static const int kNotFound = -1;
448 : static const int kMinCapacity = 4;
449 :
450 : static const int kNumberOfElementsIndex = 0;
451 : // The next table is stored at the same index as the nof elements.
452 : static const int kNextTableIndex = kNumberOfElementsIndex;
453 : static const int kNumberOfDeletedElementsIndex = kNumberOfElementsIndex + 1;
454 : static const int kNumberOfBucketsIndex = kNumberOfDeletedElementsIndex + 1;
455 : static const int kHashTableStartIndex = kNumberOfBucketsIndex + 1;
456 :
457 : static constexpr const int kNumberOfElementsOffset =
458 : FixedArray::OffsetOfElementAt(kNumberOfElementsIndex);
459 : static constexpr const int kNextTableOffset =
460 : FixedArray::OffsetOfElementAt(kNextTableIndex);
461 : static constexpr const int kNumberOfDeletedElementsOffset =
462 : FixedArray::OffsetOfElementAt(kNumberOfDeletedElementsIndex);
463 : static constexpr const int kNumberOfBucketsOffset =
464 : FixedArray::OffsetOfElementAt(kNumberOfBucketsIndex);
465 : static constexpr const int kHashTableStartOffset =
466 : FixedArray::OffsetOfElementAt(kHashTableStartIndex);
467 :
468 : static const int kEntrySize = entrysize + 1;
469 : static const int kChainOffset = entrysize;
470 :
471 : static const int kLoadFactor = 2;
472 :
473 : // NumberOfDeletedElements is set to kClearedTableSentinel when
474 : // the table is cleared, which allows iterator transitions to
475 : // optimize that case.
476 : static const int kClearedTableSentinel = -1;
477 :
478 : protected:
479 : static Handle<Derived> Rehash(Handle<Derived> table, int new_capacity);
480 :
481 : void SetNumberOfBuckets(int num) {
482 : set(kNumberOfBucketsIndex, Smi::FromInt(num));
483 : }
484 :
485 : void SetNumberOfElements(int num) {
486 : set(kNumberOfElementsIndex, Smi::FromInt(num));
487 : }
488 :
489 : void SetNumberOfDeletedElements(int num) {
490 : set(kNumberOfDeletedElementsIndex, Smi::FromInt(num));
491 : }
492 :
493 : // Returns the number elements that can fit into the allocated buffer.
494 78680772 : int Capacity() { return NumberOfBuckets() * kLoadFactor; }
495 :
496 481614 : void SetNextTable(Derived* next_table) { set(kNextTableIndex, next_table); }
497 :
498 : void SetRemovedIndexAt(int index, int removed_index) {
499 : return set(kRemovedHolesIndex + index, Smi::FromInt(removed_index));
500 : }
501 :
502 : static const int kRemovedHolesIndex = kHashTableStartIndex;
503 :
504 : static const int kMaxCapacity =
505 : (FixedArray::kMaxLength - kHashTableStartIndex) /
506 : (1 + (kEntrySize * kLoadFactor));
507 : };
508 :
509 : class OrderedHashSet : public OrderedHashTable<OrderedHashSet, 1> {
510 : public:
511 : DECLARE_CAST(OrderedHashSet)
512 :
513 : static Handle<OrderedHashSet> Add(Handle<OrderedHashSet> table,
514 : Handle<Object> value);
515 : static Handle<FixedArray> ConvertToKeysArray(Handle<OrderedHashSet> table,
516 : GetKeysConversion convert);
517 : };
518 :
519 : class OrderedHashMap : public OrderedHashTable<OrderedHashMap, 2> {
520 : public:
521 : DECLARE_CAST(OrderedHashMap)
522 :
523 : inline Object* ValueAt(int entry);
524 :
525 : static const int kValueOffset = 1;
526 : };
527 :
528 : template <int entrysize>
529 : class WeakHashTableShape : public BaseShape<Handle<Object>> {
530 : public:
531 : static inline bool IsMatch(Handle<Object> key, Object* other);
532 : static inline uint32_t Hash(Handle<Object> key);
533 : static inline uint32_t HashForObject(Handle<Object> key, Object* object);
534 : static inline Handle<Object> AsHandle(Isolate* isolate, Handle<Object> key);
535 : static const int kPrefixSize = 0;
536 : static const int kEntrySize = entrysize;
537 : };
538 :
539 : // WeakHashTable maps keys that are arbitrary heap objects to heap object
540 : // values. The table wraps the keys in weak cells and store values directly.
541 : // Thus it references keys weakly and values strongly.
542 : class WeakHashTable
543 : : public HashTable<WeakHashTable, WeakHashTableShape<2>, Handle<Object>> {
544 : typedef HashTable<WeakHashTable, WeakHashTableShape<2>, Handle<Object>>
545 : DerivedHashTable;
546 :
547 : public:
548 : DECLARE_CAST(WeakHashTable)
549 :
550 : // Looks up the value associated with the given key. The hole value is
551 : // returned in case the key is not present.
552 : Object* Lookup(Handle<HeapObject> key);
553 :
554 : // Adds (or overwrites) the value associated with the given key. Mapping a
555 : // key to the hole value causes removal of the whole entry.
556 : MUST_USE_RESULT static Handle<WeakHashTable> Put(Handle<WeakHashTable> table,
557 : Handle<HeapObject> key,
558 : Handle<HeapObject> value);
559 :
560 : static Handle<FixedArray> GetValues(Handle<WeakHashTable> table);
561 :
562 : private:
563 : friend class MarkCompactCollector;
564 :
565 : void AddEntry(int entry, Handle<WeakCell> key, Handle<HeapObject> value);
566 :
567 : // Returns the index to the value of an entry.
568 : static inline int EntryToValueIndex(int entry) {
569 2130517 : return EntryToIndex(entry) + 1;
570 : }
571 : };
572 :
573 : // OrderedHashTableIterator is an iterator that iterates over the keys and
574 : // values of an OrderedHashTable.
575 : //
576 : // The iterator has a reference to the underlying OrderedHashTable data,
577 : // [table], as well as the current [index] the iterator is at.
578 : //
579 : // When the OrderedHashTable is rehashed it adds a reference from the old table
580 : // to the new table as well as storing enough data about the changes so that the
581 : // iterator [index] can be adjusted accordingly.
582 : //
583 : // When the [Next] result from the iterator is requested, the iterator checks if
584 : // there is a newer table that it needs to transition to.
585 : template <class Derived, class TableType>
586 : class OrderedHashTableIterator : public JSObject {
587 : public:
588 : // [table]: the backing hash table mapping keys to values.
589 : DECL_ACCESSORS(table, Object)
590 :
591 : // [index]: The index into the data table.
592 : DECL_ACCESSORS(index, Object)
593 :
594 : // [kind]: The kind of iteration this is. One of the [Kind] enum values.
595 : DECL_ACCESSORS(kind, Object)
596 :
597 : #ifdef OBJECT_PRINT
598 : void OrderedHashTableIteratorPrint(std::ostream& os); // NOLINT
599 : #endif
600 :
601 : static const int kTableOffset = JSObject::kHeaderSize;
602 : static const int kIndexOffset = kTableOffset + kPointerSize;
603 : static const int kKindOffset = kIndexOffset + kPointerSize;
604 : static const int kSize = kKindOffset + kPointerSize;
605 :
606 : enum Kind { kKindKeys = 1, kKindValues = 2, kKindEntries = 3 };
607 :
608 : // Whether the iterator has more elements. This needs to be called before
609 : // calling |CurrentKey| and/or |CurrentValue|.
610 : bool HasMore();
611 :
612 : // Move the index forward one.
613 30579 : void MoveNext() { set_index(Smi::FromInt(Smi::cast(index())->value() + 1)); }
614 :
615 : // Populates the array with the next key and value and then moves the iterator
616 : // forward.
617 : // This returns the |kind| or 0 if the iterator is already at the end.
618 : Smi* Next(JSArray* value_array);
619 :
620 : // Returns the current key of the iterator. This should only be called when
621 : // |HasMore| returns true.
622 : inline Object* CurrentKey();
623 :
624 : private:
625 : // Transitions the iterator to the non obsolete backing store. This is a NOP
626 : // if the [table] is not obsolete.
627 : void Transition();
628 :
629 : DISALLOW_IMPLICIT_CONSTRUCTORS(OrderedHashTableIterator);
630 : };
631 :
632 : class JSSetIterator
633 : : public OrderedHashTableIterator<JSSetIterator, OrderedHashSet> {
634 : public:
635 : // Dispatched behavior.
636 : DECLARE_PRINTER(JSSetIterator)
637 : DECLARE_VERIFIER(JSSetIterator)
638 :
639 : DECLARE_CAST(JSSetIterator)
640 :
641 : // Called by |Next| to populate the array. This allows the subclasses to
642 : // populate the array differently.
643 : inline void PopulateValueArray(FixedArray* array);
644 :
645 : private:
646 : DISALLOW_IMPLICIT_CONSTRUCTORS(JSSetIterator);
647 : };
648 :
649 : class JSMapIterator
650 : : public OrderedHashTableIterator<JSMapIterator, OrderedHashMap> {
651 : public:
652 : // Dispatched behavior.
653 : DECLARE_PRINTER(JSMapIterator)
654 : DECLARE_VERIFIER(JSMapIterator)
655 :
656 : DECLARE_CAST(JSMapIterator)
657 :
658 : // Called by |Next| to populate the array. This allows the subclasses to
659 : // populate the array differently.
660 : inline void PopulateValueArray(FixedArray* array);
661 :
662 : private:
663 : // Returns the current value of the iterator. This should only be called when
664 : // |HasMore| returns true.
665 : inline Object* CurrentValue();
666 :
667 : DISALLOW_IMPLICIT_CONSTRUCTORS(JSMapIterator);
668 : };
669 :
670 : } // namespace internal
671 : } // namespace v8
672 :
673 : #include "src/objects/object-macros-undef.h"
674 :
675 : #endif // V8_OBJECTS_HASH_TABLE_H_
|
