ES6 Map/Set iterators/forEach improvements

src/objects.h

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #ifndef V8_OBJECTS_H_
 #define V8_OBJECTS_H_
 
 #include "allocation.h"
 #include "assert-scope.h"
 #include "builtins.h"
@@ skipping 4135 matching lines @@
 // equality operator and Object::GetHash() for the hash function.
 //
 // Based on the "Deterministic Hash Table" as described by Jason Orendorff at
 // https://wiki.mozilla.org/User:Jorend/Deterministic_hash_tables
 // Originally attributed to Tyler Close.
 //
 // Memory layout:
 //   [0]: bucket count
 //   [1]: element count
 //   [2]: deleted element count
-//   [3]: live iterators (doubly-linked list)
-//   [4..(NumberOfBuckets() - 1)]: "hash table", where each item is an offset
-//                                 into the data table (see below) where the
-//                                 first item in this bucket is stored.
-//   [4 + NumberOfBuckets()..length]: "data table", an array of length
+//   [3..(3 + NumberOfBuckets() - 1)]: "hash table", where each item is an
+//                            offset into the data table (see below) where the
+//                            first item in this bucket is stored.
+//   [3 + NumberOfBuckets()..length]: "data table", an array of length
 //                            Capacity() * kEntrySize, where the first entrysize
 //                            items are handled by the derived class and the
 //                            item at kChainOffset is another entry into the
 //                            data table indicating the next entry in this hash
 //                            bucket.
+//
+// When we transition the table to a new version we obsolete it and reuse parts
+// of the memory to store information how to transition an iterator to the new
+// table:
+//
+// Memory layout for obsolete table:
+//   [0]: bucket count
+//   [1]: Next newer table
+//   [2]: Number of removed holes or -1 when the table was cleared.
+//   [3..(3 + NumberOfRemovedHoles() - 1)]: The indexes of the removed holes.
+//   [3 + NumberOfRemovedHoles()..length]: Not used
+//
 template<class Derived, class Iterator, int entrysize>
 class OrderedHashTable: public FixedArray {
  public:
   // Returns an OrderedHashTable with a capacity of at least |capacity|.
   static Handle<Derived> Allocate(
       Isolate* isolate, int capacity, PretenureFlag pretenure = NOT_TENURED);
 
   // Returns an OrderedHashTable (possibly |table|) with enough space
   // to add at least one new element.
   static Handle<Derived> EnsureGrowable(Handle<Derived> table);
@@ skipping 16 matching lines @@
   int NumberOfDeletedElements() {
     return Smi::cast(get(kNumberOfDeletedElementsIndex))->value();
   }
 
   int UsedCapacity() { return NumberOfElements() + NumberOfDeletedElements(); }
 
   int NumberOfBuckets() {
     return Smi::cast(get(kNumberOfBucketsIndex))->value();
   }
 
-  Object* iterators() { return get(kIteratorsIndex); }
-
-  void set_iterators(Object* value) { set(kIteratorsIndex, value); }
-
   // Returns the index into the data table where the new entry
   // should be placed. The table is assumed to have enough space
   // for a new entry.
   int AddEntry(int hash);
 
   // Removes the entry, and puts the_hole in entrysize pointers
   // (leaving the hash table chain intact).
   void RemoveEntry(int entry);
 
   // Returns an index into |this| for the given entry.
   int EntryToIndex(int entry) {
     return kHashTableStartIndex + NumberOfBuckets() + (entry * kEntrySize);
   }
 
   Object* KeyAt(int entry) { return get(EntryToIndex(entry)); }
 
+  bool IsObsolete() {
+    return !get(kNextTableIndex)->IsSmi();
+  }
+
+  // The next newer table. This is only valid if the table is obsolete.
+  Derived* NextTable() {
+    return Derived::cast(get(kNextTableIndex));
+  }
+
+  // When the table is obsolete we store the indexes of the removed holes.
+  int RemovedIndexAt(int index) {
+    return Smi::cast(get(kRemovedHolesIndex + index))->value();
+  }
+
   static const int kNotFound = -1;
   static const int kMinCapacity = 4;
 
  private:
   static Handle<Derived> Rehash(Handle<Derived> table, int new_capacity);
 
   void SetNumberOfBuckets(int num) {
     set(kNumberOfBucketsIndex, Smi::FromInt(num));
   }
 
@@ skipping 16 matching lines @@
 
   int HashToBucket(int hash) {
     return hash & (NumberOfBuckets() - 1);
   }
 
   int HashToEntry(int hash) {
     int bucket = HashToBucket(hash);
     return Smi::cast(get(kHashTableStartIndex + bucket))->value();
   }
 
+  void SetNextTable(Derived* next_table) {
+    set(kNextTableIndex, next_table);
+  }
+
+  void SetRemovedIndexAt(int index, int removed_index) {
+    return set(kRemovedHolesIndex + index, Smi::FromInt(removed_index));
+  }
+
   static const int kNumberOfBucketsIndex = 0;
   static const int kNumberOfElementsIndex = kNumberOfBucketsIndex + 1;
   static const int kNumberOfDeletedElementsIndex = kNumberOfElementsIndex + 1;
-  static const int kIteratorsIndex = kNumberOfDeletedElementsIndex + 1;
-  static const int kHashTableStartIndex = kIteratorsIndex + 1;
+  static const int kHashTableStartIndex = kNumberOfDeletedElementsIndex + 1;
+
+  static const int kNextTableIndex = kNumberOfElementsIndex;
+  static const int kRemovedHolesIndex = kHashTableStartIndex;
 
   static const int kEntrySize = entrysize + 1;
   static const int kChainOffset = entrysize;
 
   static const int kLoadFactor = 2;
   static const int kMaxCapacity =
       (FixedArray::kMaxLength - kHashTableStartIndex)
       / (1 + (kEntrySize * kLoadFactor));
 };
 
@@ skipping 5676 matching lines @@
   static const int kSize = kTableOffset + kPointerSize;
 
  private:
   DISALLOW_IMPLICIT_CONSTRUCTORS(JSMap);
 };
 
 
 // OrderedHashTableIterator is an iterator that iterates over the keys and
 // values of an OrderedHashTable.
 //
-// The hash table has a reference to the iterator and the iterators themselves
-// have references to the [next_iterator] and [previous_iterator], thus creating
-// a double linked list.
+// The iterator has a reference to the underlying OrderedHashTable data,
+// [table], as well as the current [index] the iterator is at.
 //
-// When the hash table changes the iterators are called to update their [index]
-// and [count]. The hash table calls [EntryRemoved], [TableCompacted] as well
-// as [TableCleared].
+// When the OrderedHashTable is rehashed it adds a reference from the old table
+// to the new table as well as storing enough data about the changes so that the
+// iterator [index] can be adjusted accordingly.
 //
-// When an iterator is done it closes itself. It removes itself from the double
-// linked list and it sets its [table] to undefined, no longer keeping the
-// [table] alive.
+// When the [Next] result from the iterator is requested, the iterator checks if
+// there is a newer table that it needs to transition to.
 template<class Derived, class TableType>
 class OrderedHashTableIterator: public JSObject {
  public:
   // [table]: the backing hash table mapping keys to values.
   DECL_ACCESSORS(table, Object)
 
   // [index]: The index into the data table.
   DECL_ACCESSORS(index, Smi)
 
-  // [count]: The logical index into the data table, ignoring the holes.
-  DECL_ACCESSORS(count, Smi)
-
   // [kind]: The kind of iteration this is. One of the [Kind] enum values.
   DECL_ACCESSORS(kind, Smi)
 
-  // [next_iterator]: Used as a double linked list for the live iterators.
-  DECL_ACCESSORS(next_iterator, Object)
-
-  // [previous_iterator]: Used as a double linked list for the live iterators.
-  DECL_ACCESSORS(previous_iterator, Object)
-
 #ifdef OBJECT_PRINT
   void OrderedHashTableIteratorPrint(FILE* out);
 #endif
 
   static const int kTableOffset = JSObject::kHeaderSize;
   static const int kIndexOffset = kTableOffset + kPointerSize;
-  static const int kCountOffset = kIndexOffset + kPointerSize;
-  static const int kKindOffset = kCountOffset + kPointerSize;
-  static const int kNextIteratorOffset = kKindOffset + kPointerSize;
-  static const int kPreviousIteratorOffset = kNextIteratorOffset + kPointerSize;
-  static const int kSize = kPreviousIteratorOffset + kPointerSize;
+  static const int kKindOffset = kIndexOffset + kPointerSize;
+  static const int kSize = kKindOffset + kPointerSize;
 
   enum Kind {
     kKindKeys = 1,
     kKindValues = 2,
     kKindEntries = 3
   };
 
-  // Called by the underlying [table] when an entry is removed.
-  void EntryRemoved(int index);
-
-  // Called by the underlying [table] when it is compacted/rehashed.
-  void TableCompacted() {
-    // All holes have been removed so index is now same as count.
-    set_index(count());
-  }
-
-  // Called by the underlying [table] when it is cleared.
-  void TableCleared() {
-    set_index(Smi::FromInt(0));
-    set_count(Smi::FromInt(0));
-  }
-
-  // Removes the iterator from the double linked list and removes its reference
-  // back to the [table].
-  void Close();
-
   // Returns an iterator result object: {value: any, done: boolean} and moves
   // the index to the next valid entry. Closes the iterator if moving past the
   // end.
   static Handle<JSObject> Next(Handle<Derived> iterator);
 
  protected:
   static Handle<Derived> CreateInternal(
       Handle<Map> map, Handle<TableType> table, int kind);
 
  private:
-  // Ensures [index] is not pointing to a hole.
-  void Seek();
-
-  // Moves [index] to next valid entry. Closes the iterator if moving past the
-  // end.
-  void MoveNext();
-
-  bool Closed() {
-    return table()->IsUndefined();
-  }
+  // Transitions the iterator to the non obsolote backing store. This is a NOP
+  // if the [table] is not obsolete.
+  void Transition();
 
   DISALLOW_IMPLICIT_CONSTRUCTORS(OrderedHashTableIterator);
 };
 
 
 class JSSetIterator: public OrderedHashTableIterator<JSSetIterator,
                                                      OrderedHashSet> {
  public:
   // Creates a new iterator associated with [table].
   // [kind] needs to be one of the OrderedHashTableIterator Kind enum values.
   static inline Handle<JSSetIterator> Create(
       Handle<OrderedHashSet> table, int kind);
 
   // Dispatched behavior.
   DECLARE_PRINTER(JSSetIterator)
   DECLARE_VERIFIER(JSSetIterator)
 
   // Casting.
   static inline JSSetIterator* cast(Object* obj);
 
   static Handle<Object> ValueForKind(
-      Handle<JSSetIterator> iterator, int entry_index);
+      Handle<JSSetIterator> iterator,
+      int entry_index);
 
  private:
   DISALLOW_IMPLICIT_CONSTRUCTORS(JSSetIterator);
 };
 
 
 class JSMapIterator: public OrderedHashTableIterator<JSMapIterator,
                                                      OrderedHashMap> {
  public:
   // Creates a new iterator associated with [table].
   // [kind] needs to be one of the OrderedHashTableIterator Kind enum values.
   static inline Handle<JSMapIterator> Create(
       Handle<OrderedHashMap> table, int kind);
 
   // Dispatched behavior.
   DECLARE_PRINTER(JSMapIterator)
   DECLARE_VERIFIER(JSMapIterator)
 
   // Casting.
   static inline JSMapIterator* cast(Object* obj);
 
   static Handle<Object> ValueForKind(
-      Handle<JSMapIterator> iterator, int entry_index);
+      Handle<JSMapIterator> iterator,
+      int entry_index);
 
  private:
   DISALLOW_IMPLICIT_CONSTRUCTORS(JSMapIterator);
 };
 
 
 // Base class for both JSWeakMap and JSWeakSet
 class JSWeakCollection: public JSObject {
  public:
   // [table]: the backing hash table mapping keys to values.
@@ skipping 1014 matching lines @@
     } else {
       value &= ~(1 << bit_position);
     }
     return value;
   }
 };
 
 } }  // namespace v8::internal
 
 #endif  // V8_OBJECTS_H_