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