Revision: 21389
Author: [email protected]
Date: Tue May 20 14:22:05 2014 UTC
Log: ES6 Map/Set iterators/forEach improvements
This changes how Map/Set interacts with its iterators. When the
underlying table is rehashed or cleared, we create a new table (like
before) but we add a reference from the old table to the new table. We
also add an array describing how to transition the iterator from the
old table to the new table.
When Next is called on the iterator it checks if there is a newer table
that it should transition to. If there is, it updates the index based
on the previously recorded changes and finally changes itself to point
at the new table.
With these changes Map/Set no longer keeps the iterators alive. Also,
as before, the iterators keep the underlying table(s) alive but not the
actual Map/Set.
BUG=v8:1793
LOG=Y
[email protected], [email protected]
Review URL: https://codereview.chromium.org/289503002
Patch from Erik Arvidsson <[email protected]>.
http://code.google.com/p/v8/source/detail?r=21389
Deleted:
/branches/bleeding_edge/test/mjsunit/runtime-gen/mapiteratorclose.js
/branches/bleeding_edge/test/mjsunit/runtime-gen/setiteratorclose.js
Modified:
/branches/bleeding_edge/src/collection.js
/branches/bleeding_edge/src/objects-debug.cc
/branches/bleeding_edge/src/objects-inl.h
/branches/bleeding_edge/src/objects-printer.cc
/branches/bleeding_edge/src/objects.cc
/branches/bleeding_edge/src/objects.h
/branches/bleeding_edge/src/runtime.cc
/branches/bleeding_edge/src/runtime.h
/branches/bleeding_edge/test/mjsunit/harmony/collections.js
/branches/bleeding_edge/tools/generate-runtime-tests.py
=======================================
--- /branches/bleeding_edge/test/mjsunit/runtime-gen/mapiteratorclose.js
Thu May 8 13:11:59 2014 UTC
+++ /dev/null
@@ -1,5 +0,0 @@
-// Copyright 2014 the V8 project authors. All rights reserved.
-// AUTO-GENERATED BY tools/generate-runtime-tests.py, DO NOT MODIFY
-// Flags: --allow-natives-syntax --harmony
-var _holder = %MapCreateIterator(new Map(), 3);
-%MapIteratorClose(_holder);
=======================================
--- /branches/bleeding_edge/test/mjsunit/runtime-gen/setiteratorclose.js
Thu May 8 13:11:59 2014 UTC
+++ /dev/null
@@ -1,5 +0,0 @@
-// Copyright 2014 the V8 project authors. All rights reserved.
-// AUTO-GENERATED BY tools/generate-runtime-tests.py, DO NOT MODIFY
-// Flags: --allow-natives-syntax --harmony
-var _holder = %SetCreateIterator(new Set(), 2);
-%SetIteratorClose(_holder);
=======================================
--- /branches/bleeding_edge/src/collection.js Wed May 14 08:51:10 2014 UTC
+++ /branches/bleeding_edge/src/collection.js Tue May 20 14:22:05 2014 UTC
@@ -106,12 +106,8 @@
var iterator = %SetCreateIterator(this, ITERATOR_KIND_VALUES);
var entry;
- try {
- while (!(entry = %SetIteratorNext(iterator)).done) {
- %_CallFunction(receiver, entry.value, entry.value, this, f);
- }
- } finally {
- %SetIteratorClose(iterator);
+ while (!(entry = %SetIteratorNext(iterator)).done) {
+ %_CallFunction(receiver, entry.value, entry.value, this, f);
}
}
@@ -219,12 +215,8 @@
var iterator = %MapCreateIterator(this, ITERATOR_KIND_ENTRIES);
var entry;
- try {
- while (!(entry = %MapIteratorNext(iterator)).done) {
- %_CallFunction(receiver, entry.value[1], entry.value[0], this, f);
- }
- } finally {
- %MapIteratorClose(iterator);
+ while (!(entry = %MapIteratorNext(iterator)).done) {
+ %_CallFunction(receiver, entry.value[1], entry.value[0], this, f);
}
}
=======================================
--- /branches/bleeding_edge/src/objects-debug.cc Fri May 9 16:34:58 2014
UTC
+++ /branches/bleeding_edge/src/objects-debug.cc Tue May 20 14:22:05 2014
UTC
@@ -702,13 +702,7 @@
VerifyHeapPointer(table());
CHECK(table()->IsOrderedHashTable() || table()->IsUndefined());
CHECK(index()->IsSmi());
- CHECK(count()->IsSmi());
CHECK(kind()->IsSmi());
- VerifyHeapPointer(next_iterator());
- CHECK(next_iterator()->IsJSSetIterator() ||
next_iterator()->IsUndefined());
- VerifyHeapPointer(table());
- CHECK(previous_iterator()->IsJSSetIterator()
- || previous_iterator()->IsUndefined());
}
@@ -718,13 +712,7 @@
VerifyHeapPointer(table());
CHECK(table()->IsOrderedHashTable() || table()->IsUndefined());
CHECK(index()->IsSmi());
- CHECK(count()->IsSmi());
CHECK(kind()->IsSmi());
- VerifyHeapPointer(next_iterator());
- CHECK(next_iterator()->IsJSMapIterator() ||
next_iterator()->IsUndefined());
- VerifyHeapPointer(table());
- CHECK(previous_iterator()->IsJSMapIterator()
- || previous_iterator()->IsUndefined());
}
=======================================
--- /branches/bleeding_edge/src/objects-inl.h Mon May 19 16:07:20 2014 UTC
+++ /branches/bleeding_edge/src/objects-inl.h Tue May 20 14:22:05 2014 UTC
@@ -5683,12 +5683,7 @@
ORDERED_HASH_TABLE_ITERATOR_ACCESSORS(table, Object, kTableOffset)
ORDERED_HASH_TABLE_ITERATOR_ACCESSORS(index, Smi, kIndexOffset)
-ORDERED_HASH_TABLE_ITERATOR_ACCESSORS(count, Smi, kCountOffset)
ORDERED_HASH_TABLE_ITERATOR_ACCESSORS(kind, Smi, kKindOffset)
-ORDERED_HASH_TABLE_ITERATOR_ACCESSORS(next_iterator, Object,
- kNextIteratorOffset)
-ORDERED_HASH_TABLE_ITERATOR_ACCESSORS(previous_iterator, Object,
- kPreviousIteratorOffset)
#undef ORDERED_HASH_TABLE_ITERATOR_ACCESSORS
=======================================
--- /branches/bleeding_edge/src/objects-printer.cc Wed Apr 30 12:25:18 2014
UTC
+++ /branches/bleeding_edge/src/objects-printer.cc Tue May 20 14:22:05 2014
UTC
@@ -743,14 +743,8 @@
table()->ShortPrint(out);
PrintF(out, "\n - index = ");
index()->ShortPrint(out);
- PrintF(out, "\n - count = ");
- count()->ShortPrint(out);
PrintF(out, "\n - kind = ");
kind()->ShortPrint(out);
- PrintF(out, "\n - next_iterator = ");
- next_iterator()->ShortPrint(out);
- PrintF(out, "\n - previous_iterator = ");
- previous_iterator()->ShortPrint(out);
PrintF(out, "\n");
}
=======================================
--- /branches/bleeding_edge/src/objects.cc Tue May 20 09:21:45 2014 UTC
+++ /branches/bleeding_edge/src/objects.cc Tue May 20 14:22:05 2014 UTC
@@ -16222,7 +16222,6 @@
table->SetNumberOfBuckets(num_buckets);
table->SetNumberOfElements(0);
table->SetNumberOfDeletedElements(0);
- table->set_iterators(isolate->heap()->undefined_value());
return table;
}
@@ -16230,6 +16229,8 @@
template<class Derived, class Iterator, int entrysize>
Handle<Derived> OrderedHashTable<Derived, Iterator,
entrysize>::EnsureGrowable(
Handle<Derived> table) {
+ ASSERT(!table->IsObsolete());
+
int nof = table->NumberOfElements();
int nod = table->NumberOfDeletedElements();
int capacity = table->Capacity();
@@ -16244,9 +16245,11 @@
template<class Derived, class Iterator, int entrysize>
Handle<Derived> OrderedHashTable<Derived, Iterator, entrysize>::Shrink(
Handle<Derived> table) {
+ ASSERT(!table->IsObsolete());
+
int nof = table->NumberOfElements();
int capacity = table->Capacity();
- if (nof > (capacity >> 2)) return table;
+ if (nof >= (capacity >> 2)) return table;
return Rehash(table, capacity / 2);
}
@@ -16254,21 +16257,15 @@
template<class Derived, class Iterator, int entrysize>
Handle<Derived> OrderedHashTable<Derived, Iterator, entrysize>::Clear(
Handle<Derived> table) {
+ ASSERT(!table->IsObsolete());
+
Handle<Derived> new_table =
Allocate(table->GetIsolate(),
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->SetNextTable(*new_table);
+ table->SetNumberOfDeletedElements(-1);
return new_table;
}
@@ -16277,6 +16274,8 @@
template<class Derived, class Iterator, int entrysize>
Handle<Derived> OrderedHashTable<Derived, Iterator, entrysize>::Rehash(
Handle<Derived> table, int new_capacity) {
+ ASSERT(!table->IsObsolete());
+
Handle<Derived> new_table =
Allocate(table->GetIsolate(),
new_capacity,
@@ -16285,9 +16284,15 @@
int nod = table->NumberOfDeletedElements();
int new_buckets = new_table->NumberOfBuckets();
int new_entry = 0;
+ int removed_holes_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()) {
+ table->SetRemovedIndexAt(removed_holes_index++, old_entry);
+ continue;
+ }
+
Object* hash = key->GetHash();
int bucket = Smi::cast(hash)->value() & (new_buckets - 1);
Object* chain_entry = new_table->get(kHashTableStartIndex + bucket);
@@ -16301,18 +16306,11 @@
new_table->set(new_index + kChainOffset, chain_entry);
++new_entry;
}
- new_table->SetNumberOfElements(nof);
- new_table->set_iterators(table->iterators());
- table->set_iterators(table->GetHeap()->undefined_value());
+ ASSERT_EQ(nod, removed_holes_index);
- 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);
- }
+ new_table->SetNumberOfElements(nof);
+ table->SetNextTable(*new_table);
return new_table;
}
@@ -16321,6 +16319,8 @@
template<class Derived, class Iterator, int entrysize>
int OrderedHashTable<Derived, Iterator, entrysize>::FindEntry(
Handle<Object> key) {
+ ASSERT(!IsObsolete());
+
DisallowHeapAllocation no_gc;
ASSERT(!key->IsTheHole());
Object* hash = key->GetHash();
@@ -16338,6 +16338,8 @@
template<class Derived, class Iterator, int entrysize>
int OrderedHashTable<Derived, Iterator, entrysize>::AddEntry(int hash) {
+ ASSERT(!IsObsolete());
+
int entry = UsedCapacity();
int bucket = HashToBucket(hash);
int index = EntryToIndex(entry);
@@ -16351,19 +16353,14 @@
template<class Derived, class Iterator, int entrysize>
void OrderedHashTable<Derived, Iterator, entrysize>::RemoveEntry(int
entry) {
+ ASSERT(!IsObsolete());
+
int index = EntryToIndex(entry);
for (int i = 0; i < entrysize; ++i) {
set_the_hole(index + i);
}
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);
- }
}
@@ -16483,97 +16480,69 @@
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();
+ Handle<Object> maybe_table(iterator->table(), isolate);
+ if (!maybe_table->IsUndefined()) {
+ iterator->Transition();
-template<class Derived, class TableType>
-void OrderedHashTableIterator<Derived, TableType>::Close() {
- if (Closed()) return;
+ Handle<TableType> table(TableType::cast(iterator->table()), isolate);
+ int index = Smi::cast(iterator->index())->value();
+ int used_capacity = table->UsedCapacity();
- DisallowHeapAllocation no_allocation;
+ while (index < used_capacity && table->KeyAt(index)->IsTheHole()) {
+ index++;
+ }
- Object* undefined = GetHeap()->undefined_value();
- TableType* table = TableType::cast(this->table());
- Object* previous = previous_iterator();
- Object* next = next_iterator();
+ 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 (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);
+ iterator->set_table(iterator->GetHeap()->undefined_value());
}
- if (!next->IsUndefined()) {
- ASSERT_EQ(Derived::cast(next)->previous_iterator(), this);
- Derived::cast(next)->set_previous_iterator(previous);
- }
-
- 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));
+ return factory->NewIteratorResultObject(factory->undefined_value(),
true);
}
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();
-}
-
+void OrderedHashTableIterator<Derived, TableType>::Transition() {
+ Isolate* isolate = GetIsolate();
+ Handle<TableType> table(TableType::cast(this->table()), isolate);
+ if (!table->IsObsolete()) return;
-template<class Derived, class TableType>
-Handle<JSObject> OrderedHashTableIterator<Derived, TableType>::Next(
- Handle<Derived> iterator) {
- Isolate* isolate = iterator->GetIsolate();
- Factory* factory = isolate->factory();
+ int index = Smi::cast(this->index())->value();
+ while (table->IsObsolete()) {
+ Handle<TableType> next_table(table->NextTable(), isolate);
- Handle<Object> object(iterator->table(), isolate);
+ if (index > 0) {
+ int nod = table->NumberOfDeletedElements();
- 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);
- } else {
- iterator->Close();
+ // When we clear the table we set the number of deleted elements to
-1.
+ if (nod == -1) {
+ index = 0;
+ } else {
+ int old_index = index;
+ for (int i = 0; i < nod; ++i) {
+ int removed_index = table->RemovedIndexAt(i);
+ if (removed_index >= old_index) break;
+ --index;
+ }
+ }
}
+
+ table = next_table;
}
- return factory->NewIteratorResultObject(factory->undefined_value(),
true);
+ set_table(*table);
+ set_index(Smi::FromInt(index));
}
@@ -16584,60 +16553,37 @@
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);
-
-
-template void
-OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::EntryRemoved(
- int index);
+ Handle<Map> map, Handle<OrderedHashSet> table, int kind);
-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(
=======================================
--- /branches/bleeding_edge/src/objects.h Mon May 12 15:30:00 2014 UTC
+++ /branches/bleeding_edge/src/objects.h Tue May 20 14:22:05 2014 UTC
@@ -4153,16 +4153,27 @@
// [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:
@@ -4198,10 +4209,6 @@
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
@@ -4219,6 +4226,20 @@
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;
@@ -4254,12 +4275,22 @@
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;
@@ -9956,17 +9987,15 @@
// 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 +10005,17 @@
// [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 +10023,6 @@
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 +10033,9 @@
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);
};
@@ -10066,7 +10057,8 @@
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);
@@ -10089,7 +10081,8 @@
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);
=======================================
--- /branches/bleeding_edge/src/runtime.cc Tue May 20 14:03:38 2014 UTC
+++ /branches/bleeding_edge/src/runtime.cc Tue May 20 14:22:05 2014 UTC
@@ -1598,15 +1598,6 @@
CONVERT_ARG_HANDLE_CHECKED(JSSetIterator, holder, 0);
return *JSSetIterator::Next(holder);
}
-
-
-RUNTIME_FUNCTION(Runtime_SetIteratorClose) {
- HandleScope scope(isolate);
- ASSERT(args.length() == 1);
- CONVERT_ARG_HANDLE_CHECKED(JSSetIterator, holder, 0);
- holder->Close();
- return isolate->heap()->undefined_value();
-}
RUNTIME_FUNCTION(Runtime_MapInitialize) {
@@ -1707,15 +1698,6 @@
CONVERT_ARG_HANDLE_CHECKED(JSMapIterator, holder, 0);
return *JSMapIterator::Next(holder);
}
-
-
-RUNTIME_FUNCTION(Runtime_MapIteratorClose) {
- HandleScope scope(isolate);
- ASSERT(args.length() == 1);
- CONVERT_ARG_HANDLE_CHECKED(JSMapIterator, holder, 0);
- holder->Close();
- return isolate->heap()->undefined_value();
-}
static Handle<JSWeakCollection> WeakCollectionInitialize(
=======================================
--- /branches/bleeding_edge/src/runtime.h Mon May 19 07:57:04 2014 UTC
+++ /branches/bleeding_edge/src/runtime.h Tue May 20 14:22:05 2014 UTC
@@ -276,7 +276,6 @@
F(SetCreateIterator, 2, 1) \
\
F(SetIteratorNext, 1, 1) \
- F(SetIteratorClose, 1, 1) \
\
/* Harmony maps */ \
F(MapInitialize, 1, 1) \
@@ -289,7 +288,6 @@
F(MapCreateIterator, 2, 1) \
\
F(MapIteratorNext, 1, 1) \
- F(MapIteratorClose, 1, 1) \
\
/* Harmony weak maps and sets */ \
F(WeakCollectionInitialize, 1, 1) \
=======================================
--- /branches/bleeding_edge/test/mjsunit/harmony/collections.js Tue May 6
14:48:34 2014 UTC
+++ /branches/bleeding_edge/test/mjsunit/harmony/collections.js Tue May 20
14:22:05 2014 UTC
@@ -852,3 +852,138 @@
});
assertEquals(4950, accumulated);
})();
+
+
+(function TestMapForEachAllRemovedTransition() {
+ var map = new Map;
+ map.set(0, 0);
+
+ var buffer = [];
+ map.forEach(function(v) {
+ buffer.push(v);
+ if (v === 0) {
+ for (var i = 1; i < 4; i++) {
+ map.set(i, i);
+ }
+ }
+
+ if (v === 3) {
+ for (var i = 0; i < 4; i++) {
+ map.delete(i);
+ }
+ for (var i = 4; i < 8; i++) {
+ map.set(i, i);
+ }
+ }
+ });
+
+ assertArrayEquals([0, 1, 2, 3, 4, 5, 6, 7], buffer);
+})();
+
+
+(function TestMapForEachClearTransition() {
+ var map = new Map;
+ map.set(0, 0);
+
+ var i = 0;
+ var buffer = [];
+ map.forEach(function(v) {
+ buffer.push(v);
+ if (++i < 5) {
+ for (var j = 0; j < 5; j++) {
+ map.clear();
+ map.set(i, i);
+ }
+ }
+ });
+
+ assertArrayEquals([0, 1, 2, 3, 4], buffer);
+})();
+
+
+(function TestMapForEachNestedNonTrivialTransition() {
+ var map = new Map;
+ map.set(0, 0);
+ map.set(1, 1);
+ map.set(2, 2);
+ map.set(3, 3);
+ map.delete(0);
+
+ var i = 0;
+ var buffer = [];
+ map.forEach(function(v) {
+ if (++i > 10) return;
+
+ buffer.push(v);
+
+ if (v == 3) {
+ map.delete(1);
+ for (var j = 4; j < 10; j++) {
+ map.set(j, j);
+ }
+ for (var j = 4; j < 10; j += 2) {
+ map.delete(j);
+ }
+ map.delete(2);
+
+ for (var j = 10; j < 20; j++) {
+ map.set(j, j);
+ }
+ for (var j = 10; j < 20; j += 2) {
+ map.delete(j);
+ }
+
+ map.delete(3);
+ }
+ });
+
+ assertArrayEquals([1, 2, 3, 5, 7, 9, 11, 13, 15, 17], buffer);
+})();
+
+
+(function TestMapForEachAllRemovedTransitionNoClear() {
+ var map = new Map;
+ map.set(0, 0);
+
+ var buffer = [];
+ map.forEach(function(v) {
+ buffer.push(v);
+ if (v === 0) {
+ for (var i = 1; i < 8; i++) {
+ map.set(i, i);
+ }
+ }
+
+ if (v === 4) {
+ for (var i = 0; i < 8; i++) {
+ map.delete(i);
+ }
+ }
+ });
+
+ assertArrayEquals([0, 1, 2, 3, 4], buffer);
+})();
+
+
+(function TestMapForEachNoMoreElementsAfterTransition() {
+ var map = new Map;
+ map.set(0, 0);
+
+ var buffer = [];
+ map.forEach(function(v) {
+ buffer.push(v);
+ if (v === 0) {
+ for (var i = 1; i < 16; i++) {
+ map.set(i, i);
+ }
+ }
+
+ if (v === 4) {
+ for (var i = 5; i < 16; i++) {
+ map.delete(i);
+ }
+ }
+ });
+
+ assertArrayEquals([0, 1, 2, 3, 4], buffer);
+})();
=======================================
--- /branches/bleeding_edge/tools/generate-runtime-tests.py Mon May 19
08:19:54 2014 UTC
+++ /branches/bleeding_edge/tools/generate-runtime-tests.py Tue May 20
14:22:05 2014 UTC
@@ -47,8 +47,8 @@
# that the parser doesn't bit-rot. Change the values as needed when you
add,
# remove or change runtime functions, but make sure we don't lose our
ability
# to parse them!
-EXPECTED_FUNCTION_COUNT = 361
-EXPECTED_FUZZABLE_COUNT = 328
+EXPECTED_FUNCTION_COUNT = 359
+EXPECTED_FUZZABLE_COUNT = 326
EXPECTED_CCTEST_COUNT = 6
EXPECTED_UNKNOWN_COUNT = 5
EXPECTED_BUILTINS_COUNT = 824
--
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
---
You received this message because you are subscribed to the Google Groups "v8-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/d/optout.
