OLD | NEW |
1 // Copyright 2013 the V8 project authors. All rights reserved. | 1 // Copyright 2013 the V8 project authors. All rights reserved. |
2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
4 // met: | 4 // met: |
5 // | 5 // |
6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
(...skipping 1657 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1668 case JS_GENERATOR_OBJECT_TYPE: | 1668 case JS_GENERATOR_OBJECT_TYPE: |
1669 case JS_MODULE_TYPE: | 1669 case JS_MODULE_TYPE: |
1670 case JS_VALUE_TYPE: | 1670 case JS_VALUE_TYPE: |
1671 case JS_DATE_TYPE: | 1671 case JS_DATE_TYPE: |
1672 case JS_ARRAY_TYPE: | 1672 case JS_ARRAY_TYPE: |
1673 case JS_ARRAY_BUFFER_TYPE: | 1673 case JS_ARRAY_BUFFER_TYPE: |
1674 case JS_TYPED_ARRAY_TYPE: | 1674 case JS_TYPED_ARRAY_TYPE: |
1675 case JS_DATA_VIEW_TYPE: | 1675 case JS_DATA_VIEW_TYPE: |
1676 case JS_SET_TYPE: | 1676 case JS_SET_TYPE: |
1677 case JS_MAP_TYPE: | 1677 case JS_MAP_TYPE: |
| 1678 case JS_SET_ITERATOR_TYPE: |
| 1679 case JS_MAP_ITERATOR_TYPE: |
1678 case JS_WEAK_MAP_TYPE: | 1680 case JS_WEAK_MAP_TYPE: |
1679 case JS_WEAK_SET_TYPE: | 1681 case JS_WEAK_SET_TYPE: |
1680 case JS_REGEXP_TYPE: | 1682 case JS_REGEXP_TYPE: |
1681 case JS_GLOBAL_PROXY_TYPE: | 1683 case JS_GLOBAL_PROXY_TYPE: |
1682 case JS_GLOBAL_OBJECT_TYPE: | 1684 case JS_GLOBAL_OBJECT_TYPE: |
1683 case JS_BUILTINS_OBJECT_TYPE: | 1685 case JS_BUILTINS_OBJECT_TYPE: |
1684 case JS_MESSAGE_OBJECT_TYPE: | 1686 case JS_MESSAGE_OBJECT_TYPE: |
1685 JSObject::BodyDescriptor::IterateBody(this, object_size, v); | 1687 JSObject::BodyDescriptor::IterateBody(this, object_size, v); |
1686 break; | 1688 break; |
1687 case JS_FUNCTION_TYPE: | 1689 case JS_FUNCTION_TYPE: |
(...skipping 14625 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
16313 } | 16315 } |
16314 | 16316 |
16315 | 16317 |
16316 void WeakHashTable::AddEntry(int entry, Object* key, Object* value) { | 16318 void WeakHashTable::AddEntry(int entry, Object* key, Object* value) { |
16317 set(EntryToIndex(entry), key); | 16319 set(EntryToIndex(entry), key); |
16318 set(EntryToValueIndex(entry), value); | 16320 set(EntryToValueIndex(entry), value); |
16319 ElementAdded(); | 16321 ElementAdded(); |
16320 } | 16322 } |
16321 | 16323 |
16322 | 16324 |
16323 template<class Derived, int entrysize> | 16325 template<class Derived, class Iterator, int entrysize> |
16324 Handle<Derived> OrderedHashTable<Derived, entrysize>::Allocate( | 16326 Handle<Derived> OrderedHashTable<Derived, Iterator, entrysize>::Allocate( |
16325 Isolate* isolate, int capacity, PretenureFlag pretenure) { | 16327 Isolate* isolate, int capacity, PretenureFlag pretenure) { |
16326 // Capacity must be a power of two, since we depend on being able | 16328 // Capacity must be a power of two, since we depend on being able |
16327 // to divide and multiple by 2 (kLoadFactor) to derive capacity | 16329 // to divide and multiple by 2 (kLoadFactor) to derive capacity |
16328 // from number of buckets. If we decide to change kLoadFactor | 16330 // from number of buckets. If we decide to change kLoadFactor |
16329 // to something other than 2, capacity should be stored as another | 16331 // to something other than 2, capacity should be stored as another |
16330 // field of this object. | 16332 // field of this object. |
16331 const int kMinCapacity = 4; | |
16332 capacity = RoundUpToPowerOf2(Max(kMinCapacity, capacity)); | 16333 capacity = RoundUpToPowerOf2(Max(kMinCapacity, capacity)); |
16333 if (capacity > kMaxCapacity) { | 16334 if (capacity > kMaxCapacity) { |
16334 v8::internal::Heap::FatalProcessOutOfMemory("invalid table size", true); | 16335 v8::internal::Heap::FatalProcessOutOfMemory("invalid table size", true); |
16335 } | 16336 } |
16336 int num_buckets = capacity / kLoadFactor; | 16337 int num_buckets = capacity / kLoadFactor; |
16337 Handle<FixedArray> backing_store = isolate->factory()->NewFixedArray( | 16338 Handle<FixedArray> backing_store = isolate->factory()->NewFixedArray( |
16338 kHashTableStartIndex + num_buckets + (capacity * kEntrySize), pretenure); | 16339 kHashTableStartIndex + num_buckets + (capacity * kEntrySize), pretenure); |
16339 backing_store->set_map_no_write_barrier( | 16340 backing_store->set_map_no_write_barrier( |
16340 isolate->heap()->ordered_hash_table_map()); | 16341 isolate->heap()->ordered_hash_table_map()); |
16341 Handle<Derived> table = Handle<Derived>::cast(backing_store); | 16342 Handle<Derived> table = Handle<Derived>::cast(backing_store); |
16342 for (int i = 0; i < num_buckets; ++i) { | 16343 for (int i = 0; i < num_buckets; ++i) { |
16343 table->set(kHashTableStartIndex + i, Smi::FromInt(kNotFound)); | 16344 table->set(kHashTableStartIndex + i, Smi::FromInt(kNotFound)); |
16344 } | 16345 } |
16345 table->SetNumberOfBuckets(num_buckets); | 16346 table->SetNumberOfBuckets(num_buckets); |
16346 table->SetNumberOfElements(0); | 16347 table->SetNumberOfElements(0); |
16347 table->SetNumberOfDeletedElements(0); | 16348 table->SetNumberOfDeletedElements(0); |
| 16349 table->set_iterators(isolate->heap()->undefined_value()); |
16348 return table; | 16350 return table; |
16349 } | 16351 } |
16350 | 16352 |
16351 | 16353 |
16352 template<class Derived, int entrysize> | 16354 template<class Derived, class Iterator, int entrysize> |
16353 Handle<Derived> OrderedHashTable<Derived, entrysize>::EnsureGrowable( | 16355 Handle<Derived> OrderedHashTable<Derived, Iterator, entrysize>::EnsureGrowable( |
16354 Handle<Derived> table) { | 16356 Handle<Derived> table) { |
16355 int nof = table->NumberOfElements(); | 16357 int nof = table->NumberOfElements(); |
16356 int nod = table->NumberOfDeletedElements(); | 16358 int nod = table->NumberOfDeletedElements(); |
16357 int capacity = table->Capacity(); | 16359 int capacity = table->Capacity(); |
16358 if ((nof + nod) < capacity) return table; | 16360 if ((nof + nod) < capacity) return table; |
16359 // Don't need to grow if we can simply clear out deleted entries instead. | 16361 // Don't need to grow if we can simply clear out deleted entries instead. |
16360 // Note that we can't compact in place, though, so we always allocate | 16362 // Note that we can't compact in place, though, so we always allocate |
16361 // a new table. | 16363 // a new table. |
16362 return Rehash(table, (nod < (capacity >> 1)) ? capacity << 1 : capacity); | 16364 return Rehash(table, (nod < (capacity >> 1)) ? capacity << 1 : capacity); |
16363 } | 16365 } |
16364 | 16366 |
16365 | 16367 |
16366 template<class Derived, int entrysize> | 16368 template<class Derived, class Iterator, int entrysize> |
16367 Handle<Derived> OrderedHashTable<Derived, entrysize>::Shrink( | 16369 Handle<Derived> OrderedHashTable<Derived, Iterator, entrysize>::Shrink( |
16368 Handle<Derived> table) { | 16370 Handle<Derived> table) { |
16369 int nof = table->NumberOfElements(); | 16371 int nof = table->NumberOfElements(); |
16370 int capacity = table->Capacity(); | 16372 int capacity = table->Capacity(); |
16371 if (nof > (capacity >> 2)) return table; | 16373 if (nof > (capacity >> 2)) return table; |
16372 return Rehash(table, capacity / 2); | 16374 return Rehash(table, capacity / 2); |
16373 } | 16375 } |
16374 | 16376 |
16375 | 16377 |
16376 template<class Derived, int entrysize> | 16378 template<class Derived, class Iterator, int entrysize> |
16377 Handle<Derived> OrderedHashTable<Derived, entrysize>::Rehash( | 16379 Handle<Derived> OrderedHashTable<Derived, Iterator, entrysize>::Clear( |
| 16380 Handle<Derived> table) { |
| 16381 Handle<Derived> new_table = |
| 16382 Allocate(table->GetIsolate(), |
| 16383 kMinCapacity, |
| 16384 table->GetHeap()->InNewSpace(*table) ? NOT_TENURED : TENURED); |
| 16385 |
| 16386 new_table->set_iterators(table->iterators()); |
| 16387 table->set_iterators(table->GetHeap()->undefined_value()); |
| 16388 |
| 16389 DisallowHeapAllocation no_allocation; |
| 16390 for (Object* object = new_table->iterators(); |
| 16391 !object->IsUndefined(); |
| 16392 object = Iterator::cast(object)->next_iterator()) { |
| 16393 Iterator::cast(object)->TableCleared(); |
| 16394 Iterator::cast(object)->set_table(*new_table); |
| 16395 } |
| 16396 |
| 16397 return new_table; |
| 16398 } |
| 16399 |
| 16400 |
| 16401 template<class Derived, class Iterator, int entrysize> |
| 16402 Handle<Derived> OrderedHashTable<Derived, Iterator, entrysize>::Rehash( |
16378 Handle<Derived> table, int new_capacity) { | 16403 Handle<Derived> table, int new_capacity) { |
16379 Handle<Derived> new_table = | 16404 Handle<Derived> new_table = |
16380 Allocate(table->GetIsolate(), | 16405 Allocate(table->GetIsolate(), |
16381 new_capacity, | 16406 new_capacity, |
16382 table->GetHeap()->InNewSpace(*table) ? NOT_TENURED : TENURED); | 16407 table->GetHeap()->InNewSpace(*table) ? NOT_TENURED : TENURED); |
16383 int nof = table->NumberOfElements(); | 16408 int nof = table->NumberOfElements(); |
16384 int nod = table->NumberOfDeletedElements(); | 16409 int nod = table->NumberOfDeletedElements(); |
16385 int new_buckets = new_table->NumberOfBuckets(); | 16410 int new_buckets = new_table->NumberOfBuckets(); |
16386 int new_entry = 0; | 16411 int new_entry = 0; |
16387 for (int old_entry = 0; old_entry < (nof + nod); ++old_entry) { | 16412 for (int old_entry = 0; old_entry < (nof + nod); ++old_entry) { |
16388 Object* key = table->KeyAt(old_entry); | 16413 Object* key = table->KeyAt(old_entry); |
16389 if (key->IsTheHole()) continue; | 16414 if (key->IsTheHole()) continue; |
16390 Object* hash = key->GetHash(); | 16415 Object* hash = key->GetHash(); |
16391 int bucket = Smi::cast(hash)->value() & (new_buckets - 1); | 16416 int bucket = Smi::cast(hash)->value() & (new_buckets - 1); |
16392 Object* chain_entry = new_table->get(kHashTableStartIndex + bucket); | 16417 Object* chain_entry = new_table->get(kHashTableStartIndex + bucket); |
16393 new_table->set(kHashTableStartIndex + bucket, Smi::FromInt(new_entry)); | 16418 new_table->set(kHashTableStartIndex + bucket, Smi::FromInt(new_entry)); |
16394 int new_index = new_table->EntryToIndex(new_entry); | 16419 int new_index = new_table->EntryToIndex(new_entry); |
16395 int old_index = table->EntryToIndex(old_entry); | 16420 int old_index = table->EntryToIndex(old_entry); |
16396 for (int i = 0; i < entrysize; ++i) { | 16421 for (int i = 0; i < entrysize; ++i) { |
16397 Object* value = table->get(old_index + i); | 16422 Object* value = table->get(old_index + i); |
16398 new_table->set(new_index + i, value); | 16423 new_table->set(new_index + i, value); |
16399 } | 16424 } |
16400 new_table->set(new_index + kChainOffset, chain_entry); | 16425 new_table->set(new_index + kChainOffset, chain_entry); |
16401 ++new_entry; | 16426 ++new_entry; |
16402 } | 16427 } |
16403 new_table->SetNumberOfElements(nof); | 16428 new_table->SetNumberOfElements(nof); |
| 16429 |
| 16430 new_table->set_iterators(table->iterators()); |
| 16431 table->set_iterators(table->GetHeap()->undefined_value()); |
| 16432 |
| 16433 DisallowHeapAllocation no_allocation; |
| 16434 for (Object* object = new_table->iterators(); |
| 16435 !object->IsUndefined(); |
| 16436 object = Iterator::cast(object)->next_iterator()) { |
| 16437 Iterator::cast(object)->TableCompacted(); |
| 16438 Iterator::cast(object)->set_table(*new_table); |
| 16439 } |
| 16440 |
16404 return new_table; | 16441 return new_table; |
16405 } | 16442 } |
16406 | 16443 |
16407 | 16444 |
16408 template<class Derived, int entrysize> | 16445 template<class Derived, class Iterator, int entrysize> |
16409 int OrderedHashTable<Derived, entrysize>::FindEntry(Object* key) { | 16446 int OrderedHashTable<Derived, Iterator, entrysize>::FindEntry(Object* key) { |
16410 ASSERT(!key->IsTheHole()); | 16447 ASSERT(!key->IsTheHole()); |
16411 Object* hash = key->GetHash(); | 16448 Object* hash = key->GetHash(); |
16412 if (hash->IsUndefined()) return kNotFound; | 16449 if (hash->IsUndefined()) return kNotFound; |
16413 for (int entry = HashToEntry(Smi::cast(hash)->value()); | 16450 for (int entry = HashToEntry(Smi::cast(hash)->value()); |
16414 entry != kNotFound; | 16451 entry != kNotFound; |
16415 entry = ChainAt(entry)) { | 16452 entry = ChainAt(entry)) { |
16416 Object* candidate = KeyAt(entry); | 16453 Object* candidate = KeyAt(entry); |
16417 if (candidate->SameValue(key)) | 16454 if (candidate->SameValue(key)) |
16418 return entry; | 16455 return entry; |
16419 } | 16456 } |
16420 return kNotFound; | 16457 return kNotFound; |
16421 } | 16458 } |
16422 | 16459 |
16423 | 16460 |
16424 template<class Derived, int entrysize> | 16461 template<class Derived, class Iterator, int entrysize> |
16425 int OrderedHashTable<Derived, entrysize>::AddEntry(int hash) { | 16462 int OrderedHashTable<Derived, Iterator, entrysize>::AddEntry(int hash) { |
16426 int entry = NumberOfElements() + NumberOfDeletedElements(); | 16463 int entry = UsedCapacity(); |
16427 int bucket = HashToBucket(hash); | 16464 int bucket = HashToBucket(hash); |
16428 int index = EntryToIndex(entry); | 16465 int index = EntryToIndex(entry); |
16429 Object* chain_entry = get(kHashTableStartIndex + bucket); | 16466 Object* chain_entry = get(kHashTableStartIndex + bucket); |
16430 set(kHashTableStartIndex + bucket, Smi::FromInt(entry)); | 16467 set(kHashTableStartIndex + bucket, Smi::FromInt(entry)); |
16431 set(index + kChainOffset, chain_entry); | 16468 set(index + kChainOffset, chain_entry); |
16432 SetNumberOfElements(NumberOfElements() + 1); | 16469 SetNumberOfElements(NumberOfElements() + 1); |
16433 return index; | 16470 return index; |
16434 } | 16471 } |
16435 | 16472 |
16436 | 16473 |
16437 template<class Derived, int entrysize> | 16474 template<class Derived, class Iterator, int entrysize> |
16438 void OrderedHashTable<Derived, entrysize>::RemoveEntry(int entry) { | 16475 void OrderedHashTable<Derived, Iterator, entrysize>::RemoveEntry(int entry) { |
16439 int index = EntryToIndex(entry); | 16476 int index = EntryToIndex(entry); |
16440 for (int i = 0; i < entrysize; ++i) { | 16477 for (int i = 0; i < entrysize; ++i) { |
16441 set_the_hole(index + i); | 16478 set_the_hole(index + i); |
16442 } | 16479 } |
16443 SetNumberOfElements(NumberOfElements() - 1); | 16480 SetNumberOfElements(NumberOfElements() - 1); |
16444 SetNumberOfDeletedElements(NumberOfDeletedElements() + 1); | 16481 SetNumberOfDeletedElements(NumberOfDeletedElements() + 1); |
| 16482 |
| 16483 DisallowHeapAllocation no_allocation; |
| 16484 for (Object* object = iterators(); |
| 16485 !object->IsUndefined(); |
| 16486 object = Iterator::cast(object)->next_iterator()) { |
| 16487 Iterator::cast(object)->EntryRemoved(entry); |
| 16488 } |
16445 } | 16489 } |
16446 | 16490 |
16447 | 16491 |
16448 template class OrderedHashTable<OrderedHashSet, 1>; | 16492 template Handle<OrderedHashSet> |
16449 template class OrderedHashTable<OrderedHashMap, 2>; | 16493 OrderedHashTable<OrderedHashSet, JSSetIterator, 1>::Allocate( |
| 16494 Isolate* isolate, int capacity, PretenureFlag pretenure); |
| 16495 |
| 16496 template Handle<OrderedHashSet> |
| 16497 OrderedHashTable<OrderedHashSet, JSSetIterator, 1>::EnsureGrowable( |
| 16498 Handle<OrderedHashSet> table); |
| 16499 |
| 16500 template Handle<OrderedHashSet> |
| 16501 OrderedHashTable<OrderedHashSet, JSSetIterator, 1>::Shrink( |
| 16502 Handle<OrderedHashSet> table); |
| 16503 |
| 16504 template Handle<OrderedHashSet> |
| 16505 OrderedHashTable<OrderedHashSet, JSSetIterator, 1>::Clear( |
| 16506 Handle<OrderedHashSet> table); |
| 16507 |
| 16508 template int |
| 16509 OrderedHashTable<OrderedHashSet, JSSetIterator, 1>::FindEntry(Object* key); |
| 16510 |
| 16511 template int |
| 16512 OrderedHashTable<OrderedHashSet, JSSetIterator, 1>::AddEntry(int hash); |
| 16513 |
| 16514 template void |
| 16515 OrderedHashTable<OrderedHashSet, JSSetIterator, 1>::RemoveEntry(int entry); |
| 16516 |
| 16517 template Handle<OrderedHashSet> |
| 16518 OrderedHashTable<OrderedHashSet, JSSetIterator, 1>::Rehash( |
| 16519 Handle<OrderedHashSet> table, int new_capacity); |
| 16520 |
| 16521 |
| 16522 template Handle<OrderedHashMap> |
| 16523 OrderedHashTable<OrderedHashMap, JSMapIterator, 2>::Allocate( |
| 16524 Isolate* isolate, int capacity, PretenureFlag pretenure); |
| 16525 |
| 16526 template Handle<OrderedHashMap> |
| 16527 OrderedHashTable<OrderedHashMap, JSMapIterator, 2>::EnsureGrowable( |
| 16528 Handle<OrderedHashMap> table); |
| 16529 |
| 16530 template Handle<OrderedHashMap> |
| 16531 OrderedHashTable<OrderedHashMap, JSMapIterator, 2>::Shrink( |
| 16532 Handle<OrderedHashMap> table); |
| 16533 |
| 16534 template Handle<OrderedHashMap> |
| 16535 OrderedHashTable<OrderedHashMap, JSMapIterator, 2>::Clear( |
| 16536 Handle<OrderedHashMap> table); |
| 16537 |
| 16538 template int |
| 16539 OrderedHashTable<OrderedHashMap, JSMapIterator, 2>::FindEntry(Object* key); |
| 16540 |
| 16541 template int |
| 16542 OrderedHashTable<OrderedHashMap, JSMapIterator, 2>::AddEntry(int hash); |
| 16543 |
| 16544 template void |
| 16545 OrderedHashTable<OrderedHashMap, JSMapIterator, 2>::RemoveEntry(int entry); |
| 16546 |
| 16547 template Handle<OrderedHashMap> |
| 16548 OrderedHashTable<OrderedHashMap, JSMapIterator, 2>::Rehash( |
| 16549 Handle<OrderedHashMap> table, int new_capacity); |
16450 | 16550 |
16451 | 16551 |
16452 bool OrderedHashSet::Contains(Object* key) { | 16552 bool OrderedHashSet::Contains(Object* key) { |
16453 return FindEntry(key) != kNotFound; | 16553 return FindEntry(key) != kNotFound; |
16454 } | 16554 } |
16455 | 16555 |
16456 | 16556 |
16457 Handle<OrderedHashSet> OrderedHashSet::Add(Handle<OrderedHashSet> table, | 16557 Handle<OrderedHashSet> OrderedHashSet::Add(Handle<OrderedHashSet> table, |
16458 Handle<Object> key) { | 16558 Handle<Object> key) { |
16459 if (table->FindEntry(*key) != kNotFound) return table; | 16559 if (table->FindEntry(*key) != kNotFound) return table; |
16460 | 16560 |
16461 table = EnsureGrowable(table); | 16561 table = EnsureGrowable(table); |
16462 | 16562 |
16463 Handle<Object> hash = GetOrCreateHash(key, table->GetIsolate()); | 16563 Handle<Object> hash = GetOrCreateHash(key, table->GetIsolate()); |
16464 int index = table->AddEntry(Smi::cast(*hash)->value()); | 16564 int index = table->AddEntry(Smi::cast(*hash)->value()); |
16465 table->set(index, *key); | 16565 table->set(index, *key); |
16466 return table; | 16566 return table; |
16467 } | 16567 } |
16468 | 16568 |
16469 | 16569 |
16470 Handle<OrderedHashSet> OrderedHashSet::Remove(Handle<OrderedHashSet> table, | 16570 Handle<OrderedHashSet> OrderedHashSet::Remove(Handle<OrderedHashSet> table, |
16471 Handle<Object> key) { | 16571 Handle<Object> key) { |
16472 int entry = table->FindEntry(*key); | 16572 int entry = table->FindEntry(*key); |
16473 if (entry == kNotFound) return table; | 16573 if (entry == kNotFound) return table; |
16474 table->RemoveEntry(entry); | 16574 table->RemoveEntry(entry); |
16475 // TODO(adamk): Don't shrink if we're being iterated over | |
16476 return Shrink(table); | 16575 return Shrink(table); |
16477 } | 16576 } |
16478 | 16577 |
16479 | 16578 |
16480 Object* OrderedHashMap::Lookup(Object* key) { | 16579 Object* OrderedHashMap::Lookup(Object* key) { |
16481 int entry = FindEntry(key); | 16580 int entry = FindEntry(key); |
16482 if (entry == kNotFound) return GetHeap()->the_hole_value(); | 16581 if (entry == kNotFound) return GetHeap()->the_hole_value(); |
16483 return ValueAt(entry); | 16582 return ValueAt(entry); |
16484 } | 16583 } |
16485 | 16584 |
16486 | 16585 |
16487 Handle<OrderedHashMap> OrderedHashMap::Put(Handle<OrderedHashMap> table, | 16586 Handle<OrderedHashMap> OrderedHashMap::Put(Handle<OrderedHashMap> table, |
16488 Handle<Object> key, | 16587 Handle<Object> key, |
16489 Handle<Object> value) { | 16588 Handle<Object> value) { |
16490 int entry = table->FindEntry(*key); | 16589 int entry = table->FindEntry(*key); |
16491 | 16590 |
16492 if (value->IsTheHole()) { | 16591 if (value->IsTheHole()) { |
16493 if (entry == kNotFound) return table; | 16592 if (entry == kNotFound) return table; |
16494 table->RemoveEntry(entry); | 16593 table->RemoveEntry(entry); |
16495 // TODO(adamk): Only shrink if not iterating | |
16496 return Shrink(table); | 16594 return Shrink(table); |
16497 } | 16595 } |
16498 | 16596 |
16499 if (entry != kNotFound) { | 16597 if (entry != kNotFound) { |
16500 table->set(table->EntryToIndex(entry) + kValueOffset, *value); | 16598 table->set(table->EntryToIndex(entry) + kValueOffset, *value); |
16501 return table; | 16599 return table; |
16502 } | 16600 } |
16503 | 16601 |
16504 table = EnsureGrowable(table); | 16602 table = EnsureGrowable(table); |
16505 | 16603 |
16506 Handle<Object> hash = GetOrCreateHash(key, table->GetIsolate()); | 16604 Handle<Object> hash = GetOrCreateHash(key, table->GetIsolate()); |
16507 int index = table->AddEntry(Smi::cast(*hash)->value()); | 16605 int index = table->AddEntry(Smi::cast(*hash)->value()); |
16508 table->set(index, *key); | 16606 table->set(index, *key); |
16509 table->set(index + kValueOffset, *value); | 16607 table->set(index + kValueOffset, *value); |
16510 return table; | 16608 return table; |
16511 } | 16609 } |
16512 | 16610 |
16513 | 16611 |
| 16612 template<class Derived, class TableType> |
| 16613 void OrderedHashTableIterator<Derived, TableType>::EntryRemoved(int index) { |
| 16614 int i = this->index()->value(); |
| 16615 if (index < i) { |
| 16616 set_count(Smi::FromInt(count()->value() - 1)); |
| 16617 } |
| 16618 if (index == i) { |
| 16619 Seek(); |
| 16620 } |
| 16621 } |
| 16622 |
| 16623 |
| 16624 template<class Derived, class TableType> |
| 16625 void OrderedHashTableIterator<Derived, TableType>::Close() { |
| 16626 if (Closed()) return; |
| 16627 |
| 16628 DisallowHeapAllocation no_allocation; |
| 16629 |
| 16630 Object* undefined = GetHeap()->undefined_value(); |
| 16631 TableType* table = TableType::cast(this->table()); |
| 16632 Object* previous = previous_iterator(); |
| 16633 Object* next = next_iterator(); |
| 16634 |
| 16635 if (previous == undefined) { |
| 16636 ASSERT_EQ(table->iterators(), this); |
| 16637 table->set_iterators(next); |
| 16638 } else { |
| 16639 ASSERT_EQ(Derived::cast(previous)->next_iterator(), this); |
| 16640 Derived::cast(previous)->set_next_iterator(next); |
| 16641 } |
| 16642 |
| 16643 if (!next->IsUndefined()) { |
| 16644 ASSERT_EQ(Derived::cast(next)->previous_iterator(), this); |
| 16645 Derived::cast(next)->set_previous_iterator(previous); |
| 16646 } |
| 16647 |
| 16648 set_previous_iterator(undefined); |
| 16649 set_next_iterator(undefined); |
| 16650 set_table(undefined); |
| 16651 } |
| 16652 |
| 16653 |
| 16654 template<class Derived, class TableType> |
| 16655 void OrderedHashTableIterator<Derived, TableType>::Seek() { |
| 16656 ASSERT(!Closed()); |
| 16657 |
| 16658 DisallowHeapAllocation no_allocation; |
| 16659 |
| 16660 int index = this->index()->value(); |
| 16661 |
| 16662 TableType* table = TableType::cast(this->table()); |
| 16663 int used_capacity = table->UsedCapacity(); |
| 16664 |
| 16665 while (index < used_capacity && table->KeyAt(index)->IsTheHole()) { |
| 16666 index++; |
| 16667 } |
| 16668 set_index(Smi::FromInt(index)); |
| 16669 } |
| 16670 |
| 16671 |
| 16672 template<class Derived, class TableType> |
| 16673 void OrderedHashTableIterator<Derived, TableType>::MoveNext() { |
| 16674 ASSERT(!Closed()); |
| 16675 |
| 16676 set_index(Smi::FromInt(index()->value() + 1)); |
| 16677 set_count(Smi::FromInt(count()->value() + 1)); |
| 16678 Seek(); |
| 16679 } |
| 16680 |
| 16681 |
| 16682 template<class Derived, class TableType> |
| 16683 Handle<JSObject> OrderedHashTableIterator<Derived, TableType>::Next( |
| 16684 Handle<Derived> iterator) { |
| 16685 Isolate* isolate = iterator->GetIsolate(); |
| 16686 Factory* factory = isolate->factory(); |
| 16687 |
| 16688 Handle<Object> object(iterator->table(), isolate); |
| 16689 |
| 16690 if (!object->IsUndefined()) { |
| 16691 Handle<TableType> table = Handle<TableType>::cast(object); |
| 16692 int index = iterator->index()->value(); |
| 16693 if (index < table->UsedCapacity()) { |
| 16694 int entry_index = table->EntryToIndex(index); |
| 16695 iterator->MoveNext(); |
| 16696 Handle<Object> value = Derived::ValueForKind(iterator, entry_index); |
| 16697 return factory->NewIteratorResultObject(value, false); |
| 16698 } else { |
| 16699 iterator->Close(); |
| 16700 } |
| 16701 } |
| 16702 |
| 16703 return factory->NewIteratorResultObject(factory->undefined_value(), true); |
| 16704 } |
| 16705 |
| 16706 |
| 16707 template<class Derived, class TableType> |
| 16708 Handle<Derived> OrderedHashTableIterator<Derived, TableType>::CreateInternal( |
| 16709 Handle<Map> map, |
| 16710 Handle<TableType> table, |
| 16711 int kind) { |
| 16712 Isolate* isolate = table->GetIsolate(); |
| 16713 |
| 16714 Handle<Object> undefined = isolate->factory()->undefined_value(); |
| 16715 |
| 16716 Handle<Derived> new_iterator = Handle<Derived>::cast( |
| 16717 isolate->factory()->NewJSObjectFromMap(map)); |
| 16718 new_iterator->set_previous_iterator(*undefined); |
| 16719 new_iterator->set_table(*table); |
| 16720 new_iterator->set_index(Smi::FromInt(0)); |
| 16721 new_iterator->set_count(Smi::FromInt(0)); |
| 16722 new_iterator->set_kind(Smi::FromInt(kind)); |
| 16723 |
| 16724 Handle<Object> old_iterator(table->iterators(), isolate); |
| 16725 if (!old_iterator->IsUndefined()) { |
| 16726 Handle<Derived>::cast(old_iterator)->set_previous_iterator(*new_iterator); |
| 16727 new_iterator->set_next_iterator(*old_iterator); |
| 16728 } else { |
| 16729 new_iterator->set_next_iterator(*undefined); |
| 16730 } |
| 16731 |
| 16732 table->set_iterators(*new_iterator); |
| 16733 |
| 16734 return new_iterator; |
| 16735 } |
| 16736 |
| 16737 |
| 16738 // template Handle<JSObject> OrderedHashTableIterator<JSSetIterator, |
| 16739 // OrderedHashSet>::Next(Handle<JSSetIterator> iterator); |
| 16740 // template Handle<JSObject> OrderedHashTableIterator<JSMapIterator, |
| 16741 // OrderedHashMap>::Next(Handle<JSMapIterator> iterator); |
| 16742 |
| 16743 |
| 16744 // template class OrderedHashTableIterator<JSSetIterator, OrderedHashSet>; |
| 16745 // template class OrderedHashTableIterator<JSMapIterator, OrderedHashMap>; |
| 16746 |
| 16747 |
| 16748 #define EXPLICIT_INSTANTIATE_ACCESSOR(Derived, TableType, name, type) \ |
| 16749 template type* OrderedHashTableIterator<Derived, TableType>::name(); \ |
| 16750 template void OrderedHashTableIterator<Derived, TableType>::set_##name( \ |
| 16751 type* value, WriteBarrierMode mode); \ |
| 16752 |
| 16753 EXPLICIT_INSTANTIATE_ACCESSOR(JSSetIterator, OrderedHashSet, table, Object) |
| 16754 EXPLICIT_INSTANTIATE_ACCESSOR(JSSetIterator, OrderedHashSet, index, Smi) |
| 16755 EXPLICIT_INSTANTIATE_ACCESSOR(JSSetIterator, OrderedHashSet, count, Smi) |
| 16756 EXPLICIT_INSTANTIATE_ACCESSOR(JSSetIterator, OrderedHashSet, kind, Smi) |
| 16757 EXPLICIT_INSTANTIATE_ACCESSOR(JSSetIterator, OrderedHashSet, next_iterator, |
| 16758 Object) |
| 16759 EXPLICIT_INSTANTIATE_ACCESSOR(JSSetIterator, OrderedHashSet, previous_iterator, |
| 16760 Object) |
| 16761 |
| 16762 template void |
| 16763 OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::EntryRemoved( |
| 16764 int index); |
| 16765 |
| 16766 template void |
| 16767 OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::Close(); |
| 16768 |
| 16769 template Handle<JSObject> |
| 16770 OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::Next( |
| 16771 Handle<JSSetIterator> iterator); |
| 16772 |
| 16773 template Handle<JSSetIterator> |
| 16774 OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::CreateInternal( |
| 16775 Handle<Map> map, Handle<OrderedHashSet> table, int kind); |
| 16776 |
| 16777 template void |
| 16778 OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::Seek(); |
| 16779 |
| 16780 template void |
| 16781 OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::MoveNext(); |
| 16782 |
| 16783 |
| 16784 EXPLICIT_INSTANTIATE_ACCESSOR(JSMapIterator, OrderedHashMap, table, Object) |
| 16785 EXPLICIT_INSTANTIATE_ACCESSOR(JSMapIterator, OrderedHashMap, index, Smi) |
| 16786 EXPLICIT_INSTANTIATE_ACCESSOR(JSMapIterator, OrderedHashMap, count, Smi) |
| 16787 EXPLICIT_INSTANTIATE_ACCESSOR(JSMapIterator, OrderedHashMap, kind, Smi) |
| 16788 EXPLICIT_INSTANTIATE_ACCESSOR(JSMapIterator, OrderedHashMap, next_iterator, |
| 16789 Object) |
| 16790 EXPLICIT_INSTANTIATE_ACCESSOR(JSMapIterator, OrderedHashMap, previous_iterator, |
| 16791 Object) |
| 16792 |
| 16793 template void |
| 16794 OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::EntryRemoved( |
| 16795 int index); |
| 16796 |
| 16797 template void |
| 16798 OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::Close(); |
| 16799 |
| 16800 template Handle<JSObject> |
| 16801 OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::Next( |
| 16802 Handle<JSMapIterator> iterator); |
| 16803 |
| 16804 template Handle<JSMapIterator> |
| 16805 OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::CreateInternal( |
| 16806 Handle<Map> map, Handle<OrderedHashMap> table, int kind); |
| 16807 |
| 16808 template void |
| 16809 OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::Seek(); |
| 16810 |
| 16811 template void |
| 16812 OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::MoveNext(); |
| 16813 |
| 16814 #undef EXPLICIT_INSTANTIATE_ACCESSOR |
| 16815 |
| 16816 Handle<Object> JSSetIterator::ValueForKind( |
| 16817 Handle<JSSetIterator> iterator, int entry_index) { |
| 16818 int kind = iterator->kind()->value(); |
| 16819 // Set.prototype only has values and entries. |
| 16820 ASSERT(kind == kKindValues || kind == kKindEntries); |
| 16821 |
| 16822 Isolate* isolate = iterator->GetIsolate(); |
| 16823 Factory* factory = isolate->factory(); |
| 16824 |
| 16825 Handle<OrderedHashSet> table( |
| 16826 OrderedHashSet::cast(iterator->table()), isolate); |
| 16827 Handle<Object> value = Handle<Object>(table->get(entry_index), isolate); |
| 16828 |
| 16829 if (kind == kKindEntries) { |
| 16830 Handle<FixedArray> array = factory->NewFixedArray(2); |
| 16831 array->set(0, *value); |
| 16832 array->set(1, *value); |
| 16833 return factory->NewJSArrayWithElements(array); |
| 16834 } |
| 16835 |
| 16836 return value; |
| 16837 } |
| 16838 |
| 16839 |
| 16840 Handle<Object> JSMapIterator::ValueForKind( |
| 16841 Handle<JSMapIterator> iterator, int entry_index) { |
| 16842 int kind = iterator->kind()->value(); |
| 16843 ASSERT(kind == kKindKeys || kind == kKindValues || kind == kKindEntries); |
| 16844 |
| 16845 Isolate* isolate = iterator->GetIsolate(); |
| 16846 Factory* factory = isolate->factory(); |
| 16847 |
| 16848 Handle<OrderedHashMap> table( |
| 16849 OrderedHashMap::cast(iterator->table()), isolate); |
| 16850 |
| 16851 switch (kind) { |
| 16852 case kKindKeys: |
| 16853 return Handle<Object>(table->get(entry_index), isolate); |
| 16854 |
| 16855 case kKindValues: |
| 16856 return Handle<Object>(table->get(entry_index + 1), isolate); |
| 16857 |
| 16858 case kKindEntries: { |
| 16859 Handle<Object> key(table->get(entry_index), isolate); |
| 16860 Handle<Object> value(table->get(entry_index + 1), isolate); |
| 16861 Handle<FixedArray> array = factory->NewFixedArray(2); |
| 16862 array->set(0, *key); |
| 16863 array->set(1, *value); |
| 16864 return factory->NewJSArrayWithElements(array); |
| 16865 } |
| 16866 } |
| 16867 |
| 16868 UNREACHABLE(); |
| 16869 return factory->undefined_value(); |
| 16870 } |
| 16871 |
| 16872 |
16514 DeclaredAccessorDescriptorIterator::DeclaredAccessorDescriptorIterator( | 16873 DeclaredAccessorDescriptorIterator::DeclaredAccessorDescriptorIterator( |
16515 DeclaredAccessorDescriptor* descriptor) | 16874 DeclaredAccessorDescriptor* descriptor) |
16516 : array_(descriptor->serialized_data()->GetDataStartAddress()), | 16875 : array_(descriptor->serialized_data()->GetDataStartAddress()), |
16517 length_(descriptor->serialized_data()->length()), | 16876 length_(descriptor->serialized_data()->length()), |
16518 offset_(0) { | 16877 offset_(0) { |
16519 } | 16878 } |
16520 | 16879 |
16521 | 16880 |
16522 const DeclaredAccessorDescriptorData* | 16881 const DeclaredAccessorDescriptorData* |
16523 DeclaredAccessorDescriptorIterator::Next() { | 16882 DeclaredAccessorDescriptorIterator::Next() { |
(...skipping 573 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
17097 #define ERROR_MESSAGES_TEXTS(C, T) T, | 17456 #define ERROR_MESSAGES_TEXTS(C, T) T, |
17098 static const char* error_messages_[] = { | 17457 static const char* error_messages_[] = { |
17099 ERROR_MESSAGES_LIST(ERROR_MESSAGES_TEXTS) | 17458 ERROR_MESSAGES_LIST(ERROR_MESSAGES_TEXTS) |
17100 }; | 17459 }; |
17101 #undef ERROR_MESSAGES_TEXTS | 17460 #undef ERROR_MESSAGES_TEXTS |
17102 return error_messages_[reason]; | 17461 return error_messages_[reason]; |
17103 } | 17462 } |
17104 | 17463 |
17105 | 17464 |
17106 } } // namespace v8::internal | 17465 } } // namespace v8::internal |
OLD | NEW |