Chromium Code Reviews| 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 |