OLD | NEW |
1 // Copyright 2015 the V8 project authors. All rights reserved. | 1 // Copyright 2015 the V8 project authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "src/objects.h" | 5 #include "src/objects.h" |
6 | 6 |
7 #include <cmath> | 7 #include <cmath> |
8 #include <iomanip> | 8 #include <iomanip> |
9 #include <sstream> | 9 #include <sstream> |
10 | 10 |
(...skipping 16146 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
16157 // internalized string with minimal performance penalty. It gives a chance | 16157 // internalized string with minimal performance penalty. It gives a chance |
16158 // to perform further lookups in code stubs (and significant performance | 16158 // to perform further lookups in code stubs (and significant performance |
16159 // boost a certain style of code). | 16159 // boost a certain style of code). |
16160 | 16160 |
16161 // EnsureCapacity will guarantee the hash table is never full. | 16161 // EnsureCapacity will guarantee the hash table is never full. |
16162 uint32_t capacity = this->Capacity(); | 16162 uint32_t capacity = this->Capacity(); |
16163 uint32_t entry = Derived::FirstProbe(key->Hash(), capacity); | 16163 uint32_t entry = Derived::FirstProbe(key->Hash(), capacity); |
16164 uint32_t count = 1; | 16164 uint32_t count = 1; |
16165 Isolate* isolate = this->GetIsolate(); | 16165 Isolate* isolate = this->GetIsolate(); |
16166 while (true) { | 16166 while (true) { |
16167 int index = Derived::EntryToIndex(entry); | 16167 Object* element = this->KeyAt(entry); |
16168 Object* element = this->get(index); | |
16169 if (element->IsUndefined(isolate)) break; // Empty entry. | 16168 if (element->IsUndefined(isolate)) break; // Empty entry. |
16170 if (*key == element) return entry; | 16169 if (*key == element) return entry; |
16171 DCHECK(element->IsTheHole(isolate) || element->IsUniqueName()); | 16170 DCHECK(element->IsTheHole(isolate) || element->IsUniqueName()); |
16172 entry = Derived::NextProbe(entry, count++, capacity); | 16171 entry = Derived::NextProbe(entry, count++, capacity); |
16173 } | 16172 } |
16174 return Derived::kNotFound; | 16173 return Derived::kNotFound; |
16175 } | 16174 } |
16176 | 16175 |
16177 | 16176 |
16178 template<typename Derived, typename Shape, typename Key> | 16177 template<typename Derived, typename Shape, typename Key> |
(...skipping 75 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
16254 DisallowHeapAllocation no_gc; | 16253 DisallowHeapAllocation no_gc; |
16255 WriteBarrierMode mode = GetWriteBarrierMode(no_gc); | 16254 WriteBarrierMode mode = GetWriteBarrierMode(no_gc); |
16256 Isolate* isolate = GetIsolate(); | 16255 Isolate* isolate = GetIsolate(); |
16257 uint32_t capacity = Capacity(); | 16256 uint32_t capacity = Capacity(); |
16258 bool done = false; | 16257 bool done = false; |
16259 for (int probe = 1; !done; probe++) { | 16258 for (int probe = 1; !done; probe++) { |
16260 // All elements at entries given by one of the first _probe_ probes | 16259 // All elements at entries given by one of the first _probe_ probes |
16261 // are placed correctly. Other elements might need to be moved. | 16260 // are placed correctly. Other elements might need to be moved. |
16262 done = true; | 16261 done = true; |
16263 for (uint32_t current = 0; current < capacity; current++) { | 16262 for (uint32_t current = 0; current < capacity; current++) { |
16264 Object* current_key = get(EntryToIndex(current)); | 16263 Object* current_key = KeyAt(current); |
16265 if (IsKey(isolate, current_key)) { | 16264 if (IsKey(isolate, current_key)) { |
16266 uint32_t target = EntryForProbe(key, current_key, probe, current); | 16265 uint32_t target = EntryForProbe(key, current_key, probe, current); |
16267 if (current == target) continue; | 16266 if (current == target) continue; |
16268 Object* target_key = get(EntryToIndex(target)); | 16267 Object* target_key = KeyAt(target); |
16269 if (!IsKey(target_key) || | 16268 if (!IsKey(target_key) || |
16270 EntryForProbe(key, target_key, probe, target) != target) { | 16269 EntryForProbe(key, target_key, probe, target) != target) { |
16271 // Put the current element into the correct position. | 16270 // Put the current element into the correct position. |
16272 Swap(current, target, mode); | 16271 Swap(current, target, mode); |
16273 // The other element will be processed on the next iteration. | 16272 // The other element will be processed on the next iteration. |
16274 current--; | 16273 current--; |
16275 } else { | 16274 } else { |
16276 // The place for the current element is occupied. Leave the element | 16275 // The place for the current element is occupied. Leave the element |
16277 // for the next probe. | 16276 // for the next probe. |
16278 done = false; | 16277 done = false; |
16279 } | 16278 } |
16280 } | 16279 } |
16281 } | 16280 } |
16282 } | 16281 } |
16283 // Wipe deleted entries. | 16282 // Wipe deleted entries. |
16284 Object* the_hole = isolate->heap()->the_hole_value(); | 16283 Object* the_hole = isolate->heap()->the_hole_value(); |
16285 Object* undefined = isolate->heap()->undefined_value(); | 16284 Object* undefined = isolate->heap()->undefined_value(); |
16286 for (uint32_t current = 0; current < capacity; current++) { | 16285 for (uint32_t current = 0; current < capacity; current++) { |
16287 if (get(EntryToIndex(current)) == the_hole) { | 16286 if (KeyAt(current) == the_hole) { |
16288 set(EntryToIndex(current), undefined); | 16287 set(EntryToIndex(current) + Derived::kEntryKeyIndex, undefined); |
16289 } | 16288 } |
16290 } | 16289 } |
16291 SetNumberOfDeletedElements(0); | 16290 SetNumberOfDeletedElements(0); |
16292 } | 16291 } |
16293 | 16292 |
16294 | 16293 |
16295 template<typename Derived, typename Shape, typename Key> | 16294 template<typename Derived, typename Shape, typename Key> |
16296 Handle<Derived> HashTable<Derived, Shape, Key>::EnsureCapacity( | 16295 Handle<Derived> HashTable<Derived, Shape, Key>::EnsureCapacity( |
16297 Handle<Derived> table, | 16296 Handle<Derived> table, |
16298 int n, | 16297 int n, |
(...skipping 2559 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
18858 if (cell->value() != *new_value) { | 18857 if (cell->value() != *new_value) { |
18859 cell->set_value(*new_value); | 18858 cell->set_value(*new_value); |
18860 Isolate* isolate = cell->GetIsolate(); | 18859 Isolate* isolate = cell->GetIsolate(); |
18861 cell->dependent_code()->DeoptimizeDependentCodeGroup( | 18860 cell->dependent_code()->DeoptimizeDependentCodeGroup( |
18862 isolate, DependentCode::kPropertyCellChangedGroup); | 18861 isolate, DependentCode::kPropertyCellChangedGroup); |
18863 } | 18862 } |
18864 } | 18863 } |
18865 | 18864 |
18866 } // namespace internal | 18865 } // namespace internal |
18867 } // namespace v8 | 18866 } // namespace v8 |
OLD | NEW |