ES6 Map/Set iterators/forEach improvements

src/objects.h

Index: src/objects.h
diff --git a/src/objects.h b/src/objects.h
index d642e1e7da88b4f57bf49f79b485031f771a1ef3..c70e0368c2b9b2b9e3e06b04540a7979026c0985 100644
--- a/src/objects.h
+++ b/src/objects.h
@@ -4153,11 +4153,15 @@ class ObjectHashTable: public HashTable<ObjectHashTable,
 //   [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
+//   [3]: "next table". When the table is rehashed the old table points to the
+//        next newer table. The changes between the two tables are described by
+//        [changes].
+//   [4]: "changes". This contains the information needed to transition an
+//        iterator to the next table.
+//   [5..(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
+//   [5 + 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
@@ -4199,9 +4203,17 @@ class OrderedHashTable: public FixedArray {
     return Smi::cast(get(kNumberOfBucketsIndex))->value();
   }
 
-  Object* iterators() { return get(kIteratorsIndex); }
+  // The next newer table or |undefined| if no newer table exists.
+  Object* next_table() {
+    return get(kNextTableIndex);
+  }
 
-  void set_iterators(Object* value) { set(kIteratorsIndex, value); }
+  // The changes describing how to transition an iterator to the [next_table].
+  // This is an array of the removed holes during a Rehash. In case the table
+  // was cleared, this stays as |undefined|.
+  Object* changes() {
+    return get(kChangesIndex);
+  }
 
   // Returns the index into the data table where the new entry
   // should be placed. The table is assumed to have enough space
@@ -4255,11 +4267,20 @@ class OrderedHashTable: public FixedArray {
     return Smi::cast(get(kHashTableStartIndex + bucket))->value();
   }
 
+  void set_next_table(Object* next_table) {
+    set(kNextTableIndex, next_table);
+  }
+
+  void set_changes(Object* changes) {
+    set(kChangesIndex, changes);
+  }
+
   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 kNextTableIndex = kNumberOfDeletedElementsIndex + 1;
+  static const int kChangesIndex = kNextTableIndex + 1;
+  static const int kHashTableStartIndex = kChangesIndex + 1;
 
   static const int kEntrySize = entrysize + 1;
   static const int kChainOffset = entrysize;
@@ -9956,17 +9977,15 @@ class JSMap: public JSObject {
 // 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:
@@ -9976,29 +9995,17 @@ class OrderedHashTableIterator: public JSObject {
   // [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,
@@ -10006,25 +10013,6 @@ class OrderedHashTableIterator: public JSObject {
     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.
@@ -10035,16 +10023,7 @@ class OrderedHashTableIterator: public JSObject {
       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();
-  }
+  Handle<TableType> TransitionIterator(Handle<TableType> table);

[rossberg, 2014/05/14 12:13:46]

Rename to just Transition (or Sync?).

Also, is this ever going to be called with anything other than this->table()? If
so, we should drop the parameter. Likewise for the result, actually -- just make
this void-to-void and call it in Next before even looking at table().

[arv (Not doing code reviews), 2014/05/14 14:02:39]

The idea was to minimize read and writes but reading and writing the field
should be fast. I'll change it to void-to-void.

[arv (Not doing code reviews), 2014/05/14 14:02:39]

Done.

 
   DISALLOW_IMPLICIT_CONSTRUCTORS(OrderedHashTableIterator);
 };
@@ -10066,7 +10045,9 @@ class JSSetIterator: public OrderedHashTableIterator<JSSetIterator,
   static inline JSSetIterator* cast(Object* obj);
 
   static Handle<Object> ValueForKind(
-      Handle<JSSetIterator> iterator, int entry_index);
+      Handle<JSSetIterator> iterator,
+      int entry_index,
+      Handle<OrderedHashSet> table);
 
  private:
   DISALLOW_IMPLICIT_CONSTRUCTORS(JSSetIterator);
@@ -10089,7 +10070,9 @@ class JSMapIterator: public OrderedHashTableIterator<JSMapIterator,
   static inline JSMapIterator* cast(Object* obj);
 
   static Handle<Object> ValueForKind(
-      Handle<JSMapIterator> iterator, int entry_index);
+      Handle<JSMapIterator> iterator,
+      int entry_index,
+      Handle<OrderedHashMap> table);
 
  private:
   DISALLOW_IMPLICIT_CONSTRUCTORS(JSMapIterator);