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