OLD | NEW |
1 // Copyright 2012 the V8 project authors. All rights reserved. | 1 // Copyright 2012 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 // Review notes: | 5 // Review notes: |
6 // | 6 // |
7 // - The use of macros in these inline functions may seem superfluous | 7 // - The use of macros in these inline functions may seem superfluous |
8 // but it is absolutely needed to make sure gcc generates optimal | 8 // but it is absolutely needed to make sure gcc generates optimal |
9 // code. gcc is not happy when attempting to inline too deep. | 9 // code. gcc is not happy when attempting to inline too deep. |
10 // | 10 // |
(...skipping 2573 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2584 if (out_insertion_index != NULL) *out_insertion_index = limit + 1; | 2584 if (out_insertion_index != NULL) *out_insertion_index = limit + 1; |
2585 return T::kNotFound; | 2585 return T::kNotFound; |
2586 } | 2586 } |
2587 | 2587 |
2588 | 2588 |
2589 // Perform a linear search in this fixed array. len is the number of entry | 2589 // Perform a linear search in this fixed array. len is the number of entry |
2590 // indices that are valid. | 2590 // indices that are valid. |
2591 template <SearchMode search_mode, typename T> | 2591 template <SearchMode search_mode, typename T> |
2592 int LinearSearch(T* array, Name* name, int len, int valid_entries, | 2592 int LinearSearch(T* array, Name* name, int len, int valid_entries, |
2593 int* out_insertion_index) { | 2593 int* out_insertion_index) { |
2594 uint32_t hash = name->Hash(); | |
2595 if (search_mode == ALL_ENTRIES) { | 2594 if (search_mode == ALL_ENTRIES) { |
| 2595 uint32_t hash = name->Hash(); |
2596 for (int number = 0; number < len; number++) { | 2596 for (int number = 0; number < len; number++) { |
2597 int sorted_index = array->GetSortedKeyIndex(number); | 2597 int sorted_index = array->GetSortedKeyIndex(number); |
2598 Name* entry = array->GetKey(sorted_index); | 2598 Name* entry = array->GetKey(sorted_index); |
2599 uint32_t current_hash = entry->Hash(); | 2599 uint32_t current_hash = entry->Hash(); |
2600 if (current_hash > hash) { | 2600 if (current_hash > hash) { |
2601 if (out_insertion_index != NULL) *out_insertion_index = sorted_index; | 2601 if (out_insertion_index != NULL) *out_insertion_index = sorted_index; |
2602 return T::kNotFound; | 2602 return T::kNotFound; |
2603 } | 2603 } |
2604 if (current_hash == hash && entry->Equals(name)) return sorted_index; | 2604 if (current_hash == hash && entry->Equals(name)) return sorted_index; |
2605 } | 2605 } |
2606 if (out_insertion_index != NULL) *out_insertion_index = len; | 2606 if (out_insertion_index != NULL) *out_insertion_index = len; |
2607 return T::kNotFound; | 2607 return T::kNotFound; |
2608 } else { | 2608 } else { |
2609 DCHECK(len >= valid_entries); | 2609 DCHECK(len >= valid_entries); |
2610 DCHECK_NULL(out_insertion_index); // Not supported here. | 2610 DCHECK_NULL(out_insertion_index); // Not supported here. |
2611 for (int number = 0; number < valid_entries; number++) { | 2611 for (int number = 0; number < valid_entries; number++) { |
2612 Name* entry = array->GetKey(number); | 2612 if (array->GetKey(number)->Equals(name)) return number; |
2613 uint32_t current_hash = entry->Hash(); | |
2614 if (current_hash == hash && entry->Equals(name)) return number; | |
2615 } | 2613 } |
2616 return T::kNotFound; | 2614 return T::kNotFound; |
2617 } | 2615 } |
2618 } | 2616 } |
2619 | 2617 |
2620 | 2618 |
2621 template <SearchMode search_mode, typename T> | 2619 template <SearchMode search_mode, typename T> |
2622 int Search(T* array, Name* name, int valid_entries, int* out_insertion_index) { | 2620 int Search(T* array, Name* name, int valid_entries, int* out_insertion_index) { |
2623 if (search_mode == VALID_ENTRIES) { | 2621 if (search_mode == VALID_ENTRIES) { |
2624 SLOW_DCHECK(array->IsSortedNoDuplicates(valid_entries)); | 2622 SLOW_DCHECK(array->IsSortedNoDuplicates(valid_entries)); |
(...skipping 5050 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
7675 #undef WRITE_INT64_FIELD | 7673 #undef WRITE_INT64_FIELD |
7676 #undef READ_BYTE_FIELD | 7674 #undef READ_BYTE_FIELD |
7677 #undef WRITE_BYTE_FIELD | 7675 #undef WRITE_BYTE_FIELD |
7678 #undef NOBARRIER_READ_BYTE_FIELD | 7676 #undef NOBARRIER_READ_BYTE_FIELD |
7679 #undef NOBARRIER_WRITE_BYTE_FIELD | 7677 #undef NOBARRIER_WRITE_BYTE_FIELD |
7680 | 7678 |
7681 } // namespace internal | 7679 } // namespace internal |
7682 } // namespace v8 | 7680 } // namespace v8 |
7683 | 7681 |
7684 #endif // V8_OBJECTS_INL_H_ | 7682 #endif // V8_OBJECTS_INL_H_ |
OLD | NEW |