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 14659 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
14670 return entry; | 14670 return entry; |
14671 } | 14671 } |
14672 ASSERT(element->IsTheHole() || !Name::cast(element)->Equals(*key)); | 14672 ASSERT(element->IsTheHole() || !Name::cast(element)->Equals(*key)); |
14673 entry = NextProbe(entry, count++, capacity); | 14673 entry = NextProbe(entry, count++, capacity); |
14674 } | 14674 } |
14675 return kNotFound; | 14675 return kNotFound; |
14676 } | 14676 } |
14677 | 14677 |
14678 | 14678 |
14679 template<typename Derived, typename Shape, typename Key> | 14679 template<typename Derived, typename Shape, typename Key> |
14680 void HashTable<Derived, Shape, Key>::Rehash( | 14680 void HashTable<Derived, Shape, Key>::Rehash(Derived* new_table, Key key) { |
14681 Handle<Derived> new_table, | |
14682 Key key) { | |
14683 ASSERT(NumberOfElements() < new_table->Capacity()); | 14681 ASSERT(NumberOfElements() < new_table->Capacity()); |
14684 | 14682 |
14685 DisallowHeapAllocation no_gc; | 14683 DisallowHeapAllocation no_gc; |
14686 WriteBarrierMode mode = new_table->GetWriteBarrierMode(no_gc); | 14684 WriteBarrierMode mode = new_table->GetWriteBarrierMode(no_gc); |
14687 | 14685 |
14688 // Copy prefix to new array. | 14686 // Copy prefix to new array. |
14689 for (int i = kPrefixStartIndex; | 14687 for (int i = kPrefixStartIndex; |
14690 i < kPrefixStartIndex + Shape::kPrefixSize; | 14688 i < kPrefixStartIndex + Shape::kPrefixSize; |
14691 i++) { | 14689 i++) { |
14692 new_table->set(i, get(i), mode); | 14690 new_table->set(i, get(i), mode); |
(...skipping 81 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
14774 // for the next probe. | 14772 // for the next probe. |
14775 done = false; | 14773 done = false; |
14776 } | 14774 } |
14777 } | 14775 } |
14778 } | 14776 } |
14779 } | 14777 } |
14780 } | 14778 } |
14781 | 14779 |
14782 | 14780 |
14783 template<typename Derived, typename Shape, typename Key> | 14781 template<typename Derived, typename Shape, typename Key> |
| 14782 MaybeObject* HashTable<Derived, Shape, Key>::EnsureCapacity( |
| 14783 int n, |
| 14784 Key key, |
| 14785 PretenureFlag pretenure) { |
| 14786 int capacity = Capacity(); |
| 14787 int nof = NumberOfElements() + n; |
| 14788 int nod = NumberOfDeletedElements(); |
| 14789 // Return if: |
| 14790 // 50% is still free after adding n elements and |
| 14791 // at most 50% of the free elements are deleted elements. |
| 14792 if (nod <= (capacity - nof) >> 1) { |
| 14793 int needed_free = nof >> 1; |
| 14794 if (nof + needed_free <= capacity) return this; |
| 14795 } |
| 14796 |
| 14797 const int kMinCapacityForPretenure = 256; |
| 14798 bool should_pretenure = pretenure == TENURED || |
| 14799 ((capacity > kMinCapacityForPretenure) && !GetHeap()->InNewSpace(this)); |
| 14800 Object* obj; |
| 14801 { MaybeObject* maybe_obj = |
| 14802 Allocate(GetHeap(), |
| 14803 nof * 2, |
| 14804 USE_DEFAULT_MINIMUM_CAPACITY, |
| 14805 should_pretenure ? TENURED : NOT_TENURED); |
| 14806 if (!maybe_obj->ToObject(&obj)) return maybe_obj; |
| 14807 } |
| 14808 |
| 14809 Rehash(Derived::cast(obj), key); |
| 14810 return Derived::cast(obj); |
| 14811 } |
| 14812 |
| 14813 |
| 14814 template<typename Derived, typename Shape, typename Key> |
14784 Handle<Derived> HashTable<Derived, Shape, Key>::EnsureCapacity( | 14815 Handle<Derived> HashTable<Derived, Shape, Key>::EnsureCapacity( |
14785 Handle<Derived> table, | 14816 Handle<Derived> table, |
14786 int n, | 14817 int n, |
14787 Key key, | 14818 Key key, |
14788 PretenureFlag pretenure) { | 14819 PretenureFlag pretenure) { |
14789 Isolate* isolate = table->GetIsolate(); | 14820 Isolate* isolate = table->GetIsolate(); |
14790 int capacity = table->Capacity(); | 14821 CALL_HEAP_FUNCTION( |
14791 int nof = table->NumberOfElements() + n; | |
14792 int nod = table->NumberOfDeletedElements(); | |
14793 // Return if: | |
14794 // 50% is still free after adding n elements and | |
14795 // at most 50% of the free elements are deleted elements. | |
14796 if (nod <= (capacity - nof) >> 1) { | |
14797 int needed_free = nof >> 1; | |
14798 if (nof + needed_free <= capacity) return table; | |
14799 } | |
14800 | |
14801 const int kMinCapacityForPretenure = 256; | |
14802 bool should_pretenure = pretenure == TENURED || | |
14803 ((capacity > kMinCapacityForPretenure) && | |
14804 !isolate->heap()->InNewSpace(*table)); | |
14805 Handle<Derived> new_table = HashTable::New( | |
14806 isolate, | 14822 isolate, |
14807 nof * 2, | 14823 static_cast<HashTable*>(*table)->EnsureCapacity(n, key, pretenure), |
14808 USE_DEFAULT_MINIMUM_CAPACITY, | 14824 Derived); |
14809 should_pretenure ? TENURED : NOT_TENURED); | |
14810 | |
14811 table->Rehash(new_table, key); | |
14812 return new_table; | |
14813 } | 14825 } |
14814 | 14826 |
14815 | 14827 |
14816 template<typename Derived, typename Shape, typename Key> | 14828 template<typename Derived, typename Shape, typename Key> |
14817 Handle<Derived> HashTable<Derived, Shape, Key>::Shrink(Handle<Derived> table, | 14829 Handle<Derived> HashTable<Derived, Shape, Key>::Shrink(Handle<Derived> table, |
14818 Key key) { | 14830 Key key) { |
14819 int capacity = table->Capacity(); | 14831 int capacity = table->Capacity(); |
14820 int nof = table->NumberOfElements(); | 14832 int nof = table->NumberOfElements(); |
14821 | 14833 |
14822 // Shrink to fit the number of elements if only a quarter of the | 14834 // Shrink to fit the number of elements if only a quarter of the |
14823 // capacity is filled with elements. | 14835 // capacity is filled with elements. |
14824 if (nof > (capacity >> 2)) return table; | 14836 if (nof > (capacity >> 2)) return table; |
14825 // Allocate a new dictionary with room for at least the current | 14837 // Allocate a new dictionary with room for at least the current |
14826 // number of elements. The allocation method will make sure that | 14838 // number of elements. The allocation method will make sure that |
14827 // there is extra room in the dictionary for additions. Don't go | 14839 // there is extra room in the dictionary for additions. Don't go |
14828 // lower than room for 16 elements. | 14840 // lower than room for 16 elements. |
14829 int at_least_room_for = nof; | 14841 int at_least_room_for = nof; |
14830 if (at_least_room_for < 16) return table; | 14842 if (at_least_room_for < 16) return table; |
14831 | 14843 |
14832 Isolate* isolate = table->GetIsolate(); | 14844 Isolate* isolate = table->GetIsolate(); |
14833 const int kMinCapacityForPretenure = 256; | 14845 const int kMinCapacityForPretenure = 256; |
14834 bool pretenure = | 14846 bool pretenure = |
14835 (at_least_room_for > kMinCapacityForPretenure) && | 14847 (at_least_room_for > kMinCapacityForPretenure) && |
14836 !isolate->heap()->InNewSpace(*table); | 14848 !isolate->heap()->InNewSpace(*table); |
14837 Handle<Derived> new_table = HashTable::New( | 14849 Handle<Derived> new_table = New( |
14838 isolate, | 14850 isolate, |
14839 at_least_room_for, | 14851 at_least_room_for, |
14840 USE_DEFAULT_MINIMUM_CAPACITY, | 14852 USE_DEFAULT_MINIMUM_CAPACITY, |
14841 pretenure ? TENURED : NOT_TENURED); | 14853 pretenure ? TENURED : NOT_TENURED); |
14842 | 14854 |
14843 table->Rehash(new_table, key); | 14855 table->Rehash(*new_table, key); |
14844 return new_table; | 14856 return new_table; |
14845 } | 14857 } |
14846 | 14858 |
14847 | 14859 |
14848 template<typename Derived, typename Shape, typename Key> | 14860 template<typename Derived, typename Shape, typename Key> |
14849 uint32_t HashTable<Derived, Shape, Key>::FindInsertionEntry(uint32_t hash) { | 14861 uint32_t HashTable<Derived, Shape, Key>::FindInsertionEntry(uint32_t hash) { |
14850 uint32_t capacity = Capacity(); | 14862 uint32_t capacity = Capacity(); |
14851 uint32_t entry = FirstProbe(hash, capacity); | 14863 uint32_t entry = FirstProbe(hash, capacity); |
14852 uint32_t count = 1; | 14864 uint32_t count = 1; |
14853 // EnsureCapacity will guarantee the hash table is never full. | 14865 // EnsureCapacity will guarantee the hash table is never full. |
(...skipping 2489 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
17343 #define ERROR_MESSAGES_TEXTS(C, T) T, | 17355 #define ERROR_MESSAGES_TEXTS(C, T) T, |
17344 static const char* error_messages_[] = { | 17356 static const char* error_messages_[] = { |
17345 ERROR_MESSAGES_LIST(ERROR_MESSAGES_TEXTS) | 17357 ERROR_MESSAGES_LIST(ERROR_MESSAGES_TEXTS) |
17346 }; | 17358 }; |
17347 #undef ERROR_MESSAGES_TEXTS | 17359 #undef ERROR_MESSAGES_TEXTS |
17348 return error_messages_[reason]; | 17360 return error_messages_[reason]; |
17349 } | 17361 } |
17350 | 17362 |
17351 | 17363 |
17352 } } // namespace v8::internal | 17364 } } // namespace v8::internal |
OLD | NEW |