Index: src/objects.cc |
diff --git a/src/objects.cc b/src/objects.cc |
index aaa03203ae444987ec954edb1d4e19012e0791c5..dd5abbfd4603d3a9ff22adbfa1eb882566d51f9d 100644 |
--- a/src/objects.cc |
+++ b/src/objects.cc |
@@ -1692,6 +1692,8 @@ void HeapObject::IterateBody(InstanceType type, int object_size, |
case JS_DATA_VIEW_TYPE: |
case JS_SET_TYPE: |
case JS_MAP_TYPE: |
+ case JS_SET_ITERATOR_TYPE: |
+ case JS_MAP_ITERATOR_TYPE: |
case JS_WEAK_MAP_TYPE: |
case JS_WEAK_SET_TYPE: |
case JS_REGEXP_TYPE: |
@@ -15742,15 +15744,14 @@ void WeakHashTable::AddEntry(int entry, Object* key, Object* value) { |
} |
-template<class Derived, int entrysize> |
-Handle<Derived> OrderedHashTable<Derived, entrysize>::Allocate( |
+template<class Derived, class Iterator, int entrysize> |
+Handle<Derived> OrderedHashTable<Derived, Iterator, entrysize>::Allocate( |
Isolate* isolate, int capacity, PretenureFlag pretenure) { |
// Capacity must be a power of two, since we depend on being able |
// to divide and multiple by 2 (kLoadFactor) to derive capacity |
// from number of buckets. If we decide to change kLoadFactor |
// to something other than 2, capacity should be stored as another |
// field of this object. |
- const int kMinCapacity = 4; |
capacity = RoundUpToPowerOf2(Max(kMinCapacity, capacity)); |
if (capacity > kMaxCapacity) { |
v8::internal::Heap::FatalProcessOutOfMemory("invalid table size", true); |
@@ -15767,12 +15768,13 @@ Handle<Derived> OrderedHashTable<Derived, entrysize>::Allocate( |
table->SetNumberOfBuckets(num_buckets); |
table->SetNumberOfElements(0); |
table->SetNumberOfDeletedElements(0); |
+ table->set_iterators(isolate->heap()->undefined_value()); |
return table; |
} |
-template<class Derived, int entrysize> |
-Handle<Derived> OrderedHashTable<Derived, entrysize>::EnsureGrowable( |
+template<class Derived, class Iterator, int entrysize> |
+Handle<Derived> OrderedHashTable<Derived, Iterator, entrysize>::EnsureGrowable( |
Handle<Derived> table) { |
int nof = table->NumberOfElements(); |
int nod = table->NumberOfDeletedElements(); |
@@ -15785,8 +15787,8 @@ Handle<Derived> OrderedHashTable<Derived, entrysize>::EnsureGrowable( |
} |
-template<class Derived, int entrysize> |
-Handle<Derived> OrderedHashTable<Derived, entrysize>::Shrink( |
+template<class Derived, class Iterator, int entrysize> |
+Handle<Derived> OrderedHashTable<Derived, Iterator, entrysize>::Shrink( |
Handle<Derived> table) { |
int nof = table->NumberOfElements(); |
int capacity = table->Capacity(); |
@@ -15795,8 +15797,31 @@ Handle<Derived> OrderedHashTable<Derived, entrysize>::Shrink( |
} |
-template<class Derived, int entrysize> |
-Handle<Derived> OrderedHashTable<Derived, entrysize>::Rehash( |
+template<class Derived, class Iterator, int entrysize> |
+Handle<Derived> OrderedHashTable<Derived, Iterator, entrysize>::Clear( |
+ Handle<Derived> table) { |
+ 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); |
+ } |
+ |
+ return new_table; |
+} |
+ |
+ |
+template<class Derived, class Iterator, int entrysize> |
+Handle<Derived> OrderedHashTable<Derived, Iterator, entrysize>::Rehash( |
Handle<Derived> table, int new_capacity) { |
Handle<Derived> new_table = |
Allocate(table->GetIsolate(), |
@@ -15823,12 +15848,24 @@ Handle<Derived> OrderedHashTable<Derived, entrysize>::Rehash( |
++new_entry; |
} |
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); |
+ } |
+ |
return new_table; |
} |
-template<class Derived, int entrysize> |
-int OrderedHashTable<Derived, entrysize>::FindEntry(Object* key) { |
+template<class Derived, class Iterator, int entrysize> |
+int OrderedHashTable<Derived, Iterator, entrysize>::FindEntry(Object* key) { |
ASSERT(!key->IsTheHole()); |
Object* hash = key->GetHash(); |
if (hash->IsUndefined()) return kNotFound; |
@@ -15843,9 +15880,9 @@ int OrderedHashTable<Derived, entrysize>::FindEntry(Object* key) { |
} |
-template<class Derived, int entrysize> |
-int OrderedHashTable<Derived, entrysize>::AddEntry(int hash) { |
- int entry = NumberOfElements() + NumberOfDeletedElements(); |
+template<class Derived, class Iterator, int entrysize> |
+int OrderedHashTable<Derived, Iterator, entrysize>::AddEntry(int hash) { |
+ int entry = UsedCapacity(); |
int bucket = HashToBucket(hash); |
int index = EntryToIndex(entry); |
Object* chain_entry = get(kHashTableStartIndex + bucket); |
@@ -15856,19 +15893,26 @@ int OrderedHashTable<Derived, entrysize>::AddEntry(int hash) { |
} |
-template<class Derived, int entrysize> |
-void OrderedHashTable<Derived, entrysize>::RemoveEntry(int entry) { |
+template<class Derived, class Iterator, int entrysize> |
+void OrderedHashTable<Derived, Iterator, entrysize>::RemoveEntry(int entry) { |
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); |
+ } |
} |
-template class OrderedHashTable<OrderedHashSet, 1>; |
-template class OrderedHashTable<OrderedHashMap, 2>; |
+template class OrderedHashTable<OrderedHashSet, JSSetIterator, 1>; |
+template class OrderedHashTable<OrderedHashMap, JSMapIterator, 2>; |
bool OrderedHashSet::Contains(Object* key) { |
@@ -15894,7 +15938,6 @@ Handle<OrderedHashSet> OrderedHashSet::Remove(Handle<OrderedHashSet> table, |
int entry = table->FindEntry(*key); |
if (entry == kNotFound) return table; |
table->RemoveEntry(entry); |
- // TODO(adamk): Don't shrink if we're being iterated over |
return Shrink(table); |
} |
@@ -15914,7 +15957,6 @@ Handle<OrderedHashMap> OrderedHashMap::Put(Handle<OrderedHashMap> table, |
if (value->IsTheHole()) { |
if (entry == kNotFound) return table; |
table->RemoveEntry(entry); |
- // TODO(adamk): Only shrink if not iterating |
return Shrink(table); |
} |
@@ -15933,6 +15975,206 @@ 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(); |
+ } |
+} |
+ |
+ |
+template<class Derived, class TableType> |
+void OrderedHashTableIterator<Derived, TableType>::Close() { |
+ if (Closed()) return; |
+ |
+ DisallowHeapAllocation no_allocation; |
+ |
+ Object* undefined = GetHeap()->undefined_value(); |
+ TableType* table = TableType::cast(this->table()); |
+ Object* previous = previous_iterator(); |
+ Object* next = next_iterator(); |
+ |
+ 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 (!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)); |
+} |
+ |
+ |
+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(); |
+} |
+ |
+ |
+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); |
+ } else { |
+ iterator->Close(); |
+ } |
+ } |
+ |
+ return factory->NewIteratorResultObject(factory->undefined_value(), true); |
+} |
+ |
+ |
+template<class Derived, class TableType> |
+Handle<Derived> OrderedHashTableIterator<Derived, TableType>::CreateInternal( |
+ Handle<Map> map, |
+ Handle<TableType> table, |
+ 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 class OrderedHashTableIterator<JSSetIterator, OrderedHashSet>; |
+template class OrderedHashTableIterator<JSMapIterator, OrderedHashMap>; |
+ |
+ |
+Handle<JSSetIterator> JSSetIterator::Create( |
+ Handle<OrderedHashSet> table, int kind) { |
+ return CreateInternal(table->GetIsolate()->set_iterator_map(), table, kind); |
+} |
+ |
+ |
+Handle<Object> JSSetIterator::ValueForKind( |
+ Handle<JSSetIterator> iterator, int entry_index) { |
+ int kind = iterator->kind()->value(); |
+ // Set.prototype only has values and entries. |
+ ASSERT(kind == kKindValues || kind == kKindEntries); |
+ |
+ Isolate* isolate = iterator->GetIsolate(); |
+ Factory* factory = isolate->factory(); |
+ |
+ Handle<OrderedHashSet> table( |
+ OrderedHashSet::cast(iterator->table()), isolate); |
+ Handle<Object> value = Handle<Object>(table->get(entry_index), isolate); |
+ |
+ if (kind == kKindEntries) { |
+ Handle<FixedArray> array = factory->NewFixedArray(2); |
+ array->set(0, *value); |
+ array->set(1, *value); |
+ return factory->NewJSArrayWithElements(array); |
+ } |
+ |
+ return value; |
+} |
+ |
+ |
+Handle<JSMapIterator> JSMapIterator::Create( |
+ Handle<OrderedHashMap> table, |
+ int kind) { |
+ return CreateInternal(table->GetIsolate()->map_iterator_map(), table, kind); |
+} |
+ |
+ |
+Handle<Object> JSMapIterator::ValueForKind( |
+ Handle<JSMapIterator> iterator, int entry_index) { |
+ int kind = iterator->kind()->value(); |
+ ASSERT(kind == kKindKeys || kind == kKindValues || kind == kKindEntries); |
+ |
+ Isolate* isolate = iterator->GetIsolate(); |
+ Factory* factory = isolate->factory(); |
+ |
+ Handle<OrderedHashMap> table( |
+ OrderedHashMap::cast(iterator->table()), isolate); |
+ |
+ switch (kind) { |
+ case kKindKeys: |
+ return Handle<Object>(table->get(entry_index), isolate); |
+ |
+ case kKindValues: |
+ return Handle<Object>(table->get(entry_index + 1), isolate); |
+ |
+ case kKindEntries: { |
+ Handle<Object> key(table->get(entry_index), isolate); |
+ Handle<Object> value(table->get(entry_index + 1), isolate); |
+ Handle<FixedArray> array = factory->NewFixedArray(2); |
+ array->set(0, *key); |
+ array->set(1, *value); |
+ return factory->NewJSArrayWithElements(array); |
+ } |
+ } |
+ |
+ UNREACHABLE(); |
+ return factory->undefined_value(); |
+} |
+ |
+ |
DeclaredAccessorDescriptorIterator::DeclaredAccessorDescriptorIterator( |
DeclaredAccessorDescriptor* descriptor) |
: array_(descriptor->serialized_data()->GetDataStartAddress()), |