ES6 Map/Set iterators/forEach improvements

src/objects.cc

Index: src/objects.cc
diff --git a/src/objects.cc b/src/objects.cc
index f9a52e59c7455d2986ade2ac70296c2dd5db5034..c48cb15c86b1a0192cc6abf779d0568cee7ed9d9 100644
--- a/src/objects.cc
+++ b/src/objects.cc
@@ -16214,7 +16214,8 @@ Handle<Derived> OrderedHashTable<Derived, Iterator, entrysize>::Allocate(
   table->SetNumberOfBuckets(num_buckets);
   table->SetNumberOfElements(0);
   table->SetNumberOfDeletedElements(0);
-  table->set_iterators(isolate->heap()->undefined_value());
+  table->set_next_table(isolate->heap()->undefined_value());
+  table->set_changes(isolate->heap()->undefined_value());
   return table;
 }
 
@@ -16251,16 +16252,8 @@ Handle<Derived> OrderedHashTable<Derived, Iterator, entrysize>::Clear(
                kMinCapacity,
                table->GetHeap()->InNewSpace(*table) ? NOT_TENURED : TENURED);
 
-  new_table->set_iterators(table->iterators());
-  table->set_iterators(table->GetHeap()->undefined_value());
-
-  DisallowHeapAllocation no_allocation;
-  for (Object* object = new_table->iterators();
-       !object->IsUndefined();
-       object = Iterator::cast(object)->next_iterator()) {
-    Iterator::cast(object)->TableCleared();
-    Iterator::cast(object)->set_table(*new_table);
-  }
+  table->set_next_table(*new_table);
+  // changes is kept as undefined for Clear.
 
   return new_table;
 }
@@ -16277,9 +16270,15 @@ Handle<Derived> OrderedHashTable<Derived, Iterator, entrysize>::Rehash(
   int nod = table->NumberOfDeletedElements();
   int new_buckets = new_table->NumberOfBuckets();
   int new_entry = 0;
+  Handle<FixedArray> removed_entries =
+      table->GetIsolate()->factory()->NewFixedArray(nod);
+  int removed_entries_index = 0;
   for (int old_entry = 0; old_entry < (nof + nod); ++old_entry) {
     Object* key = table->KeyAt(old_entry);
-    if (key->IsTheHole()) continue;
+    if (key->IsTheHole()) {
+      removed_entries->set(removed_entries_index++, Smi::FromInt(old_entry));
+      continue;
+    }
     Object* hash = key->GetHash();
     int bucket = Smi::cast(hash)->value() & (new_buckets - 1);
     Object* chain_entry = new_table->get(kHashTableStartIndex + bucket);
@@ -16295,16 +16294,8 @@ Handle<Derived> OrderedHashTable<Derived, Iterator, entrysize>::Rehash(
   }
   new_table->SetNumberOfElements(nof);
 
-  new_table->set_iterators(table->iterators());
-  table->set_iterators(table->GetHeap()->undefined_value());
-
-  DisallowHeapAllocation no_allocation;
-  for (Object* object = new_table->iterators();
-       !object->IsUndefined();
-       object = Iterator::cast(object)->next_iterator()) {
-    Iterator::cast(object)->TableCompacted();
-    Iterator::cast(object)->set_table(*new_table);
-  }
+  table->set_next_table(*new_table);
+  table->set_changes(*removed_entries);
 
   return new_table;
 }
@@ -16349,13 +16340,6 @@ void OrderedHashTable<Derived, Iterator, entrysize>::RemoveEntry(int entry) {
   }
   SetNumberOfElements(NumberOfElements() - 1);
   SetNumberOfDeletedElements(NumberOfDeletedElements() + 1);
-
-  DisallowHeapAllocation no_allocation;
-  for (Object* object = iterators();
-       !object->IsUndefined();
-       object = Iterator::cast(object)->next_iterator()) {
-    Iterator::cast(object)->EntryRemoved(entry);
-  }
 }
 
 
@@ -16475,97 +16459,71 @@ Handle<OrderedHashMap> OrderedHashMap::Put(Handle<OrderedHashMap> table,
 
 
 template<class Derived, class TableType>
-void OrderedHashTableIterator<Derived, TableType>::EntryRemoved(int index) {
-  int i = this->index()->value();
-  if (index < i) {
-    set_count(Smi::FromInt(count()->value() - 1));
-  }
-  if (index == i) {
-    Seek();
-  }
-}
-
+Handle<JSObject> OrderedHashTableIterator<Derived, TableType>::Next(
+    Handle<Derived> iterator) {
+  Isolate* isolate = iterator->GetIsolate();
+  Factory* factory = isolate->factory();
 
-template<class Derived, class TableType>
-void OrderedHashTableIterator<Derived, TableType>::Close() {
-  if (Closed()) return;
+  Handle<Object> maybe_table(iterator->table(), isolate);
+  if (!maybe_table->IsUndefined()) {
+    iterator->Transition();
 
-  DisallowHeapAllocation no_allocation;
+    Handle<TableType> table(TableType::cast(iterator->table()), isolate);
+    int index = Smi::cast(iterator->index())->value();
+    int used_capacity = table->UsedCapacity();
 
-  Object* undefined = GetHeap()->undefined_value();
-  TableType* table = TableType::cast(this->table());
-  Object* previous = previous_iterator();
-  Object* next = next_iterator();
+    while (index < used_capacity && table->KeyAt(index)->IsTheHole()) {
+      index++;
+    }
 
-  if (previous == undefined) {
-    ASSERT_EQ(table->iterators(), this);
-    table->set_iterators(next);
-  } else {
-    ASSERT_EQ(Derived::cast(previous)->next_iterator(), this);
-    Derived::cast(previous)->set_next_iterator(next);
-  }
+    if (index < used_capacity) {
+      int entry_index = table->EntryToIndex(index);
+      Handle<Object> value =
+          Derived::ValueForKind(iterator, entry_index);
+      iterator->set_index(Smi::FromInt(index + 1));
+      return factory->NewIteratorResultObject(value, false);
+    }
 
-  if (!next->IsUndefined()) {
-    ASSERT_EQ(Derived::cast(next)->previous_iterator(), this);
-    Derived::cast(next)->set_previous_iterator(previous);
+    iterator->set_table(iterator->GetHeap()->undefined_value());
   }
 
-  set_previous_iterator(undefined);
-  set_next_iterator(undefined);
-  set_table(undefined);
-}
-
-
-template<class Derived, class TableType>
-void OrderedHashTableIterator<Derived, TableType>::Seek() {
-  ASSERT(!Closed());
-
-  DisallowHeapAllocation no_allocation;
-
-  int index = this->index()->value();
-
-  TableType* table = TableType::cast(this->table());
-  int used_capacity = table->UsedCapacity();
-
-  while (index < used_capacity && table->KeyAt(index)->IsTheHole()) {
-    index++;
-  }
-  set_index(Smi::FromInt(index));
-}
-
-
-template<class Derived, class TableType>
-void OrderedHashTableIterator<Derived, TableType>::MoveNext() {
-  ASSERT(!Closed());
-
-  set_index(Smi::FromInt(index()->value() + 1));
-  set_count(Smi::FromInt(count()->value() + 1));
-  Seek();
+  return factory->NewIteratorResultObject(factory->undefined_value(), true);
 }
 
 
 template<class Derived, class TableType>
-Handle<JSObject> OrderedHashTableIterator<Derived, TableType>::Next(
-    Handle<Derived> iterator) {
-  Isolate* isolate = iterator->GetIsolate();
-  Factory* factory = isolate->factory();
-
-  Handle<Object> object(iterator->table(), isolate);
-
-  if (!object->IsUndefined()) {
-    Handle<TableType> table = Handle<TableType>::cast(object);
-    int index = iterator->index()->value();
-    if (index < table->UsedCapacity()) {
-      int entry_index = table->EntryToIndex(index);
-      iterator->MoveNext();
-      Handle<Object> value = Derived::ValueForKind(iterator, entry_index);
-      return factory->NewIteratorResultObject(value, false);
+void OrderedHashTableIterator<Derived, TableType>::Transition() {
+  Isolate* isolate = GetIsolate();
+  Handle<TableType> table(TableType::cast(this->table()), isolate);
+  Handle<Object> maybe_next_table(table->next_table(), isolate);
+  if (maybe_next_table->IsUndefined()) return;
+
+  int index = Smi::cast(this->index())->value();
+  while (!maybe_next_table->IsUndefined()) {
+    Handle<TableType> next_table = Handle<TableType>::cast(maybe_next_table);
+    Handle<Object> maybe_changes(table->changes(), table->GetIsolate());
+
+    // changes is kept as undefined after a Clear.
+    if (maybe_changes->IsUndefined()) {
+      index = 0;
     } else {
-      iterator->Close();
+      Handle<FixedArray> changes = Handle<FixedArray>::cast(maybe_changes);
+      for (int i = 0; i < changes->length(); ++i) {
+        int entry_index = Smi::cast(changes->get(i))->value();
+        if (entry_index < index) {

[rossberg, 2014/05/14 14:27:25]

You can simplify this slightly to

  if (entry_index >= index) break;
  --index;

+          index--;
+        } else {
+          break;
+        }
+      }
     }
+
+    table = next_table;
+    maybe_next_table = Handle<Object>(table->next_table(), isolate);
   }
 
-  return factory->NewIteratorResultObject(factory->undefined_value(), true);
+  set_table(*table);
+  set_index(Smi::FromInt(index));
 }
 
 
@@ -16576,64 +16534,42 @@ Handle<Derived> OrderedHashTableIterator<Derived, TableType>::CreateInternal(
     int kind) {
   Isolate* isolate = table->GetIsolate();
 
-  Handle<Object> undefined = isolate->factory()->undefined_value();
-
   Handle<Derived> new_iterator = Handle<Derived>::cast(
       isolate->factory()->NewJSObjectFromMap(map));
-  new_iterator->set_previous_iterator(*undefined);
   new_iterator->set_table(*table);
   new_iterator->set_index(Smi::FromInt(0));
-  new_iterator->set_count(Smi::FromInt(0));
   new_iterator->set_kind(Smi::FromInt(kind));
-
-  Handle<Object> old_iterator(table->iterators(), isolate);
-  if (!old_iterator->IsUndefined()) {
-    Handle<Derived>::cast(old_iterator)->set_previous_iterator(*new_iterator);
-    new_iterator->set_next_iterator(*old_iterator);
-  } else {
-    new_iterator->set_next_iterator(*undefined);
-  }
-
-  table->set_iterators(*new_iterator);
-
   return new_iterator;
 }
 
 
-template void
-OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::EntryRemoved(
-    int index);
-
-template void
-OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::Close();
-
 template Handle<JSObject>
 OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::Next(
     Handle<JSSetIterator> iterator);
 
+template void
+OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::Transition();
+
 template Handle<JSSetIterator>
 OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::CreateInternal(
-      Handle<Map> map, Handle<OrderedHashSet> table, int kind);
+    Handle<Map> map, Handle<OrderedHashSet> table, int kind);
 
 
-template void
-OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::EntryRemoved(
-    int index);
-
-template void
-OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::Close();
-
 template Handle<JSObject>
 OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::Next(
     Handle<JSMapIterator> iterator);
 
+template void
+OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::Transition();
+
 template Handle<JSMapIterator>
 OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::CreateInternal(
-      Handle<Map> map, Handle<OrderedHashMap> table, int kind);
+    Handle<Map> map, Handle<OrderedHashMap> table, int kind);
 
 
 Handle<Object> JSSetIterator::ValueForKind(
-    Handle<JSSetIterator> iterator, int entry_index) {
+    Handle<JSSetIterator> iterator,
+    int entry_index) {
   int kind = iterator->kind()->value();
   // Set.prototype only has values and entries.
   ASSERT(kind == kKindValues || kind == kKindEntries);
@@ -16657,7 +16593,8 @@ Handle<Object> JSSetIterator::ValueForKind(
 
 
 Handle<Object> JSMapIterator::ValueForKind(
-    Handle<JSMapIterator> iterator, int entry_index) {
+    Handle<JSMapIterator> iterator,
+    int entry_index) {
   int kind = iterator->kind()->value();
   ASSERT(kind == kKindKeys || kind == kKindValues || kind == kKindEntries);