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 13788 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
13799 } | 13799 } |
13800 } | 13800 } |
13801 } | 13801 } |
13802 new_table->SetNumberOfElements(NumberOfElements()); | 13802 new_table->SetNumberOfElements(NumberOfElements()); |
13803 new_table->SetNumberOfDeletedElements(0); | 13803 new_table->SetNumberOfDeletedElements(0); |
13804 return new_table; | 13804 return new_table; |
13805 } | 13805 } |
13806 | 13806 |
13807 | 13807 |
13808 template<typename Shape, typename Key> | 13808 template<typename Shape, typename Key> |
| 13809 uint32_t HashTable<Shape, Key>::EntryForProbe(Key key, |
| 13810 Object* k, |
| 13811 int probe, |
| 13812 uint32_t expected) { |
| 13813 uint32_t hash = HashTable<Shape, Key>::HashForObject(key, k); |
| 13814 uint32_t capacity = Capacity(); |
| 13815 uint32_t entry = FirstProbe(hash, capacity); |
| 13816 for (int i = 1; i < probe; i++) { |
| 13817 if (entry == expected) return expected; |
| 13818 entry = NextProbe(entry, i, capacity); |
| 13819 } |
| 13820 return entry; |
| 13821 } |
| 13822 |
| 13823 |
| 13824 template<typename Shape, typename Key> |
| 13825 void HashTable<Shape, Key>::Swap(uint32_t entry1, |
| 13826 uint32_t entry2, |
| 13827 WriteBarrierMode mode) { |
| 13828 int index1 = EntryToIndex(entry1); |
| 13829 int index2 = EntryToIndex(entry2); |
| 13830 Object* temp[Shape::kEntrySize]; |
| 13831 for (int j = 0; j < Shape::kEntrySize; j++) { |
| 13832 temp[j] = get(index1 + j); |
| 13833 } |
| 13834 for (int j = 0; j < Shape::kEntrySize; j++) { |
| 13835 set(index1 + j, get(index2 + j), mode); |
| 13836 } |
| 13837 for (int j = 0; j < Shape::kEntrySize; j++) { |
| 13838 set(index2 + j, temp[j], mode); |
| 13839 } |
| 13840 } |
| 13841 |
| 13842 |
| 13843 template<typename Shape, typename Key> |
| 13844 void HashTable<Shape, Key>::Rehash(Key key) { |
| 13845 DisallowHeapAllocation no_gc; |
| 13846 WriteBarrierMode mode = GetWriteBarrierMode(no_gc); |
| 13847 uint32_t capacity = Capacity(); |
| 13848 bool done = false; |
| 13849 for (int probe = 1; !done; probe++) { |
| 13850 // All elements at entries given by one of the first _probe_ probes |
| 13851 // are placed correctly. Other elements might need to be moved. |
| 13852 done = true; |
| 13853 for (uint32_t current = 0; current < capacity; current++) { |
| 13854 Object* current_key = get(EntryToIndex(current)); |
| 13855 if (IsKey(current_key)) { |
| 13856 uint32_t target = EntryForProbe(key, current_key, probe, current); |
| 13857 if (current == target) continue; |
| 13858 Object* target_key = get(EntryToIndex(target)); |
| 13859 if (!IsKey(target_key) || |
| 13860 EntryForProbe(key, target_key, probe, target) != target) { |
| 13861 // Put the current element into the correct position. |
| 13862 Swap(current, target, mode); |
| 13863 // The other element will be processed on the next iteration. |
| 13864 current--; |
| 13865 } else { |
| 13866 // The place for the current element is occupied. Leave the element |
| 13867 // for the next probe. |
| 13868 done = false; |
| 13869 } |
| 13870 } |
| 13871 } |
| 13872 } |
| 13873 } |
| 13874 |
| 13875 |
| 13876 template<typename Shape, typename Key> |
13809 MaybeObject* HashTable<Shape, Key>::EnsureCapacity(int n, Key key) { | 13877 MaybeObject* HashTable<Shape, Key>::EnsureCapacity(int n, Key key) { |
13810 int capacity = Capacity(); | 13878 int capacity = Capacity(); |
13811 int nof = NumberOfElements() + n; | 13879 int nof = NumberOfElements() + n; |
13812 int nod = NumberOfDeletedElements(); | 13880 int nod = NumberOfDeletedElements(); |
13813 // Return if: | 13881 // Return if: |
13814 // 50% is still free after adding n elements and | 13882 // 50% is still free after adding n elements and |
13815 // at most 50% of the free elements are deleted elements. | 13883 // at most 50% of the free elements are deleted elements. |
13816 if (nod <= (capacity - nof) >> 1) { | 13884 if (nod <= (capacity - nof) >> 1) { |
13817 int needed_free = nof >> 1; | 13885 int needed_free = nof >> 1; |
13818 if (nof + needed_free <= capacity) return this; | 13886 if (nof + needed_free <= capacity) return this; |
(...skipping 2269 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
16088 #define ERROR_MESSAGES_TEXTS(C, T) T, | 16156 #define ERROR_MESSAGES_TEXTS(C, T) T, |
16089 static const char* error_messages_[] = { | 16157 static const char* error_messages_[] = { |
16090 ERROR_MESSAGES_LIST(ERROR_MESSAGES_TEXTS) | 16158 ERROR_MESSAGES_LIST(ERROR_MESSAGES_TEXTS) |
16091 }; | 16159 }; |
16092 #undef ERROR_MESSAGES_TEXTS | 16160 #undef ERROR_MESSAGES_TEXTS |
16093 return error_messages_[reason]; | 16161 return error_messages_[reason]; |
16094 } | 16162 } |
16095 | 16163 |
16096 | 16164 |
16097 } } // namespace v8::internal | 16165 } } // namespace v8::internal |
OLD | NEW |