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 template Handle<OrderedHashSet> | |
16532 OrderedHashTable<OrderedHashSet, JSSetIterator, 1>::Rehash( | |
adamk
2014/04/16 22:13:14
This is private, so all calls are almost certainly
| |
16533 Handle<OrderedHashSet> table, int new_capacity); | |
16534 | |
16535 | |
16536 template Handle<OrderedHashMap> | |
16537 OrderedHashTable<OrderedHashMap, JSMapIterator, 2>::Allocate( | |
16538 Isolate* isolate, int capacity, PretenureFlag pretenure); | |
16539 | |
16540 template Handle<OrderedHashMap> | |
16541 OrderedHashTable<OrderedHashMap, JSMapIterator, 2>::EnsureGrowable( | |
16542 Handle<OrderedHashMap> table); | |
16543 | |
16544 template Handle<OrderedHashMap> | |
16545 OrderedHashTable<OrderedHashMap, JSMapIterator, 2>::Shrink( | |
16546 Handle<OrderedHashMap> table); | |
16547 | |
16548 template Handle<OrderedHashMap> | |
16549 OrderedHashTable<OrderedHashMap, JSMapIterator, 2>::Clear( | |
16550 Handle<OrderedHashMap> table); | |
16551 | |
16552 template int | |
16553 OrderedHashTable<OrderedHashMap, JSMapIterator, 2>::FindEntry(Object* key); | |
16554 | |
16555 template int | |
16556 OrderedHashTable<OrderedHashMap, JSMapIterator, 2>::AddEntry(int hash); | |
16557 | |
16558 template void | |
16559 OrderedHashTable<OrderedHashMap, JSMapIterator, 2>::RemoveEntry(int entry); | |
16560 | |
16561 template Handle<OrderedHashMap> | |
16562 OrderedHashTable<OrderedHashMap, JSMapIterator, 2>::Rehash( | |
16563 Handle<OrderedHashMap> table, int new_capacity); | |
16464 | 16564 |
16465 | 16565 |
16466 bool OrderedHashSet::Contains(Object* key) { | 16566 bool OrderedHashSet::Contains(Object* key) { |
16467 return FindEntry(key) != kNotFound; | 16567 return FindEntry(key) != kNotFound; |
16468 } | 16568 } |
16469 | 16569 |
16470 | 16570 |
16471 Handle<OrderedHashSet> OrderedHashSet::Add(Handle<OrderedHashSet> table, | 16571 Handle<OrderedHashSet> OrderedHashSet::Add(Handle<OrderedHashSet> table, |
16472 Handle<Object> key) { | 16572 Handle<Object> key) { |
16473 if (table->FindEntry(*key) != kNotFound) return table; | 16573 if (table->FindEntry(*key) != kNotFound) return table; |
16474 | 16574 |
16475 table = EnsureGrowable(table); | 16575 table = EnsureGrowable(table); |
16476 | 16576 |
16477 Handle<Object> hash = GetOrCreateHash(key, table->GetIsolate()); | 16577 Handle<Object> hash = GetOrCreateHash(key, table->GetIsolate()); |
16478 int index = table->AddEntry(Smi::cast(*hash)->value()); | 16578 int index = table->AddEntry(Smi::cast(*hash)->value()); |
16479 table->set(index, *key); | 16579 table->set(index, *key); |
16480 return table; | 16580 return table; |
16481 } | 16581 } |
16482 | 16582 |
16483 | 16583 |
16484 Handle<OrderedHashSet> OrderedHashSet::Remove(Handle<OrderedHashSet> table, | 16584 Handle<OrderedHashSet> OrderedHashSet::Remove(Handle<OrderedHashSet> table, |
16485 Handle<Object> key) { | 16585 Handle<Object> key) { |
16486 int entry = table->FindEntry(*key); | 16586 int entry = table->FindEntry(*key); |
16487 if (entry == kNotFound) return table; | 16587 if (entry == kNotFound) return table; |
16488 table->RemoveEntry(entry); | 16588 table->RemoveEntry(entry); |
16489 // TODO(adamk): Don't shrink if we're being iterated over | |
16490 return Shrink(table); | 16589 return Shrink(table); |
16491 } | 16590 } |
16492 | 16591 |
16493 | 16592 |
16494 Object* OrderedHashMap::Lookup(Object* key) { | 16593 Object* OrderedHashMap::Lookup(Object* key) { |
16495 int entry = FindEntry(key); | 16594 int entry = FindEntry(key); |
16496 if (entry == kNotFound) return GetHeap()->the_hole_value(); | 16595 if (entry == kNotFound) return GetHeap()->the_hole_value(); |
16497 return ValueAt(entry); | 16596 return ValueAt(entry); |
16498 } | 16597 } |
16499 | 16598 |
16500 | 16599 |
16501 Handle<OrderedHashMap> OrderedHashMap::Put(Handle<OrderedHashMap> table, | 16600 Handle<OrderedHashMap> OrderedHashMap::Put(Handle<OrderedHashMap> table, |
16502 Handle<Object> key, | 16601 Handle<Object> key, |
16503 Handle<Object> value) { | 16602 Handle<Object> value) { |
16504 int entry = table->FindEntry(*key); | 16603 int entry = table->FindEntry(*key); |
16505 | 16604 |
16506 if (value->IsTheHole()) { | 16605 if (value->IsTheHole()) { |
16507 if (entry == kNotFound) return table; | 16606 if (entry == kNotFound) return table; |
16508 table->RemoveEntry(entry); | 16607 table->RemoveEntry(entry); |
16509 // TODO(adamk): Only shrink if not iterating | |
16510 return Shrink(table); | 16608 return Shrink(table); |
16511 } | 16609 } |
16512 | 16610 |
16513 if (entry != kNotFound) { | 16611 if (entry != kNotFound) { |
16514 table->set(table->EntryToIndex(entry) + kValueOffset, *value); | 16612 table->set(table->EntryToIndex(entry) + kValueOffset, *value); |
16515 return table; | 16613 return table; |
16516 } | 16614 } |
16517 | 16615 |
16518 table = EnsureGrowable(table); | 16616 table = EnsureGrowable(table); |
16519 | 16617 |
16520 Handle<Object> hash = GetOrCreateHash(key, table->GetIsolate()); | 16618 Handle<Object> hash = GetOrCreateHash(key, table->GetIsolate()); |
16521 int index = table->AddEntry(Smi::cast(*hash)->value()); | 16619 int index = table->AddEntry(Smi::cast(*hash)->value()); |
16522 table->set(index, *key); | 16620 table->set(index, *key); |
16523 table->set(index + kValueOffset, *value); | 16621 table->set(index + kValueOffset, *value); |
16524 return table; | 16622 return table; |
16525 } | 16623 } |
16526 | 16624 |
16527 | 16625 |
16626 template<class Derived, class TableType> | |
16627 void OrderedHashTableIterator<Derived, TableType>::EntryRemoved(int index) { | |
16628 int i = this->index()->value(); | |
16629 if (index < i) { | |
16630 set_count(Smi::FromInt(count()->value() - 1)); | |
16631 } | |
16632 if (index == i) { | |
16633 Seek(); | |
16634 } | |
16635 } | |
16636 | |
16637 | |
16638 template<class Derived, class TableType> | |
16639 void OrderedHashTableIterator<Derived, TableType>::Close() { | |
16640 if (Closed()) return; | |
16641 | |
16642 DisallowHeapAllocation no_allocation; | |
16643 | |
16644 Object* undefined = GetHeap()->undefined_value(); | |
16645 TableType* table = TableType::cast(this->table()); | |
16646 Object* previous = previous_iterator(); | |
16647 Object* next = next_iterator(); | |
16648 | |
16649 if (previous == undefined) { | |
16650 ASSERT_EQ(table->iterators(), this); | |
16651 table->set_iterators(next); | |
16652 } else { | |
16653 ASSERT_EQ(Derived::cast(previous)->next_iterator(), this); | |
16654 Derived::cast(previous)->set_next_iterator(next); | |
16655 } | |
16656 | |
16657 if (!next->IsUndefined()) { | |
16658 ASSERT_EQ(Derived::cast(next)->previous_iterator(), this); | |
16659 Derived::cast(next)->set_previous_iterator(previous); | |
16660 } | |
16661 | |
16662 set_previous_iterator(undefined); | |
16663 set_next_iterator(undefined); | |
16664 set_table(undefined); | |
16665 } | |
16666 | |
16667 | |
16668 template<class Derived, class TableType> | |
16669 void OrderedHashTableIterator<Derived, TableType>::Seek() { | |
16670 ASSERT(!Closed()); | |
16671 | |
16672 DisallowHeapAllocation no_allocation; | |
16673 | |
16674 int index = this->index()->value(); | |
16675 | |
16676 TableType* table = TableType::cast(this->table()); | |
16677 int used_capacity = table->UsedCapacity(); | |
16678 | |
16679 while (index < used_capacity && table->KeyAt(index)->IsTheHole()) { | |
16680 index++; | |
16681 } | |
16682 set_index(Smi::FromInt(index)); | |
16683 } | |
16684 | |
16685 | |
16686 template<class Derived, class TableType> | |
16687 void OrderedHashTableIterator<Derived, TableType>::MoveNext() { | |
16688 ASSERT(!Closed()); | |
16689 | |
16690 set_index(Smi::FromInt(index()->value() + 1)); | |
16691 set_count(Smi::FromInt(count()->value() + 1)); | |
16692 Seek(); | |
16693 } | |
16694 | |
16695 | |
16696 template<class Derived, class TableType> | |
16697 Handle<JSObject> OrderedHashTableIterator<Derived, TableType>::Next( | |
16698 Handle<Derived> iterator) { | |
16699 Isolate* isolate = iterator->GetIsolate(); | |
16700 Factory* factory = isolate->factory(); | |
16701 | |
16702 Handle<Object> object(iterator->table(), isolate); | |
16703 | |
16704 if (!object->IsUndefined()) { | |
16705 Handle<TableType> table = Handle<TableType>::cast(object); | |
16706 int index = iterator->index()->value(); | |
16707 if (index < table->UsedCapacity()) { | |
16708 int entry_index = table->EntryToIndex(index); | |
16709 iterator->MoveNext(); | |
16710 Handle<Object> value = Derived::ValueForKind(iterator, entry_index); | |
16711 return factory->NewIteratorResultObject(value, false); | |
16712 } else { | |
16713 iterator->Close(); | |
16714 } | |
16715 } | |
16716 | |
16717 return factory->NewIteratorResultObject(factory->undefined_value(), true); | |
16718 } | |
16719 | |
16720 | |
16721 template<class Derived, class TableType> | |
16722 Handle<Derived> OrderedHashTableIterator<Derived, TableType>::CreateInternal( | |
16723 Handle<Map> map, | |
16724 Handle<TableType> table, | |
16725 int kind) { | |
16726 Isolate* isolate = table->GetIsolate(); | |
16727 | |
16728 Handle<Object> undefined = isolate->factory()->undefined_value(); | |
16729 | |
16730 Handle<Derived> new_iterator = Handle<Derived>::cast( | |
16731 isolate->factory()->NewJSObjectFromMap(map)); | |
16732 new_iterator->set_previous_iterator(*undefined); | |
16733 new_iterator->set_table(*table); | |
16734 new_iterator->set_index(Smi::FromInt(0)); | |
16735 new_iterator->set_count(Smi::FromInt(0)); | |
16736 new_iterator->set_kind(Smi::FromInt(kind)); | |
16737 | |
16738 Handle<Object> old_iterator(table->iterators(), isolate); | |
16739 if (!old_iterator->IsUndefined()) { | |
16740 Handle<Derived>::cast(old_iterator)->set_previous_iterator(*new_iterator); | |
16741 new_iterator->set_next_iterator(*old_iterator); | |
16742 } else { | |
16743 new_iterator->set_next_iterator(*undefined); | |
16744 } | |
16745 | |
16746 table->set_iterators(*new_iterator); | |
16747 | |
16748 return new_iterator; | |
16749 } | |
16750 | |
16751 | |
16752 #define EXPLICIT_INSTANTIATE_ACCESSOR(Derived, TableType, name, type) \ | |
adamk
2014/04/16 22:13:14
These all have definitions in objects-inl.h, right
| |
16753 template type* OrderedHashTableIterator<Derived, TableType>::name(); \ | |
16754 template void OrderedHashTableIterator<Derived, TableType>::set_##name( \ | |
16755 type* value, WriteBarrierMode mode); \ | |
16756 | |
16757 EXPLICIT_INSTANTIATE_ACCESSOR(JSSetIterator, OrderedHashSet, table, Object) | |
16758 EXPLICIT_INSTANTIATE_ACCESSOR(JSSetIterator, OrderedHashSet, index, Smi) | |
16759 EXPLICIT_INSTANTIATE_ACCESSOR(JSSetIterator, OrderedHashSet, count, Smi) | |
16760 EXPLICIT_INSTANTIATE_ACCESSOR(JSSetIterator, OrderedHashSet, kind, Smi) | |
16761 EXPLICIT_INSTANTIATE_ACCESSOR(JSSetIterator, OrderedHashSet, next_iterator, | |
16762 Object) | |
16763 EXPLICIT_INSTANTIATE_ACCESSOR(JSSetIterator, OrderedHashSet, previous_iterator, | |
16764 Object) | |
16765 | |
16766 template void | |
16767 OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::EntryRemoved( | |
16768 int index); | |
16769 | |
16770 template void | |
16771 OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::Close(); | |
16772 | |
16773 template Handle<JSObject> | |
16774 OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::Next( | |
16775 Handle<JSSetIterator> iterator); | |
16776 | |
16777 template Handle<JSSetIterator> | |
16778 OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::CreateInternal( | |
16779 Handle<Map> map, Handle<OrderedHashSet> table, int kind); | |
16780 | |
16781 template void | |
16782 OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::Seek(); | |
16783 | |
16784 template void | |
16785 OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::MoveNext(); | |
adamk
2014/04/16 22:13:14
MoveNext and Seek are private, which makes it unli
| |
16786 | |
16787 | |
16788 EXPLICIT_INSTANTIATE_ACCESSOR(JSMapIterator, OrderedHashMap, table, Object) | |
adamk
2014/04/16 22:13:14
Same down here, I don't think you need the accesso
| |
16789 EXPLICIT_INSTANTIATE_ACCESSOR(JSMapIterator, OrderedHashMap, index, Smi) | |
16790 EXPLICIT_INSTANTIATE_ACCESSOR(JSMapIterator, OrderedHashMap, count, Smi) | |
16791 EXPLICIT_INSTANTIATE_ACCESSOR(JSMapIterator, OrderedHashMap, kind, Smi) | |
16792 EXPLICIT_INSTANTIATE_ACCESSOR(JSMapIterator, OrderedHashMap, next_iterator, | |
16793 Object) | |
16794 EXPLICIT_INSTANTIATE_ACCESSOR(JSMapIterator, OrderedHashMap, previous_iterator, | |
16795 Object) | |
16796 | |
16797 #undef EXPLICIT_INSTANTIATE_ACCESSOR | |
16798 | |
16799 template void | |
16800 OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::EntryRemoved( | |
16801 int index); | |
16802 | |
16803 template void | |
16804 OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::Close(); | |
16805 | |
16806 template Handle<JSObject> | |
16807 OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::Next( | |
16808 Handle<JSMapIterator> iterator); | |
16809 | |
16810 template Handle<JSMapIterator> | |
16811 OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::CreateInternal( | |
16812 Handle<Map> map, Handle<OrderedHashMap> table, int kind); | |
16813 | |
16814 template void | |
16815 OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::Seek(); | |
16816 | |
16817 template void | |
16818 OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::MoveNext(); | |
16819 | |
16820 | |
16821 | |
16822 Handle<Object> JSSetIterator::ValueForKind( | |
16823 Handle<JSSetIterator> iterator, int entry_index) { | |
16824 int kind = iterator->kind()->value(); | |
16825 // Set.prototype only has values and entries. | |
16826 ASSERT(kind == kKindValues || kind == kKindEntries); | |
16827 | |
16828 Isolate* isolate = iterator->GetIsolate(); | |
16829 Factory* factory = isolate->factory(); | |
16830 | |
16831 Handle<OrderedHashSet> table( | |
16832 OrderedHashSet::cast(iterator->table()), isolate); | |
16833 Handle<Object> value = Handle<Object>(table->get(entry_index), isolate); | |
16834 | |
16835 if (kind == kKindEntries) { | |
16836 Handle<FixedArray> array = factory->NewFixedArray(2); | |
16837 array->set(0, *value); | |
16838 array->set(1, *value); | |
16839 return factory->NewJSArrayWithElements(array); | |
16840 } | |
16841 | |
16842 return value; | |
16843 } | |
16844 | |
16845 | |
16846 Handle<Object> JSMapIterator::ValueForKind( | |
16847 Handle<JSMapIterator> iterator, int entry_index) { | |
16848 int kind = iterator->kind()->value(); | |
16849 ASSERT(kind == kKindKeys || kind == kKindValues || kind == kKindEntries); | |
16850 | |
16851 Isolate* isolate = iterator->GetIsolate(); | |
16852 Factory* factory = isolate->factory(); | |
16853 | |
16854 Handle<OrderedHashMap> table( | |
16855 OrderedHashMap::cast(iterator->table()), isolate); | |
16856 | |
16857 switch (kind) { | |
16858 case kKindKeys: | |
16859 return Handle<Object>(table->get(entry_index), isolate); | |
16860 | |
16861 case kKindValues: | |
16862 return Handle<Object>(table->get(entry_index + 1), isolate); | |
16863 | |
16864 case kKindEntries: { | |
16865 Handle<Object> key(table->get(entry_index), isolate); | |
16866 Handle<Object> value(table->get(entry_index + 1), isolate); | |
16867 Handle<FixedArray> array = factory->NewFixedArray(2); | |
16868 array->set(0, *key); | |
16869 array->set(1, *value); | |
16870 return factory->NewJSArrayWithElements(array); | |
16871 } | |
16872 } | |
16873 | |
16874 UNREACHABLE(); | |
16875 return factory->undefined_value(); | |
16876 } | |
16877 | |
16878 | |
16528 DeclaredAccessorDescriptorIterator::DeclaredAccessorDescriptorIterator( | 16879 DeclaredAccessorDescriptorIterator::DeclaredAccessorDescriptorIterator( |
16529 DeclaredAccessorDescriptor* descriptor) | 16880 DeclaredAccessorDescriptor* descriptor) |
16530 : array_(descriptor->serialized_data()->GetDataStartAddress()), | 16881 : array_(descriptor->serialized_data()->GetDataStartAddress()), |
16531 length_(descriptor->serialized_data()->length()), | 16882 length_(descriptor->serialized_data()->length()), |
16532 offset_(0) { | 16883 offset_(0) { |
16533 } | 16884 } |
16534 | 16885 |
16535 | 16886 |
16536 const DeclaredAccessorDescriptorData* | 16887 const DeclaredAccessorDescriptorData* |
16537 DeclaredAccessorDescriptorIterator::Next() { | 16888 DeclaredAccessorDescriptorIterator::Next() { |
(...skipping 573 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
17111 #define ERROR_MESSAGES_TEXTS(C, T) T, | 17462 #define ERROR_MESSAGES_TEXTS(C, T) T, |
17112 static const char* error_messages_[] = { | 17463 static const char* error_messages_[] = { |
17113 ERROR_MESSAGES_LIST(ERROR_MESSAGES_TEXTS) | 17464 ERROR_MESSAGES_LIST(ERROR_MESSAGES_TEXTS) |
17114 }; | 17465 }; |
17115 #undef ERROR_MESSAGES_TEXTS | 17466 #undef ERROR_MESSAGES_TEXTS |
17116 return error_messages_[reason]; | 17467 return error_messages_[reason]; |
17117 } | 17468 } |
17118 | 17469 |
17119 | 17470 |
17120 } } // namespace v8::internal | 17471 } } // namespace v8::internal |
OLD | NEW |