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 2783 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2794 | 2794 |
2795 void DescriptorArray::SetNumberOfDescriptors(int number_of_descriptors) { | 2795 void DescriptorArray::SetNumberOfDescriptors(int number_of_descriptors) { |
2796 WRITE_FIELD( | 2796 WRITE_FIELD( |
2797 this, kDescriptorLengthOffset, Smi::FromInt(number_of_descriptors)); | 2797 this, kDescriptorLengthOffset, Smi::FromInt(number_of_descriptors)); |
2798 } | 2798 } |
2799 | 2799 |
2800 | 2800 |
2801 // Perform a binary search in a fixed array. Low and high are entry indices. If | 2801 // Perform a binary search in a fixed array. Low and high are entry indices. If |
2802 // there are three entries in this array it should be called with low=0 and | 2802 // there are three entries in this array it should be called with low=0 and |
2803 // high=2. | 2803 // high=2. |
2804 template<SearchMode search_mode, typename T> | 2804 template <SearchMode search_mode, typename T> |
2805 int BinarySearch(T* array, Name* name, int low, int high, int valid_entries) { | 2805 int BinarySearch(T* array, Name* name, int low, int high, int valid_entries, |
| 2806 int* out_insertion_index) { |
| 2807 DCHECK(search_mode == ALL_ENTRIES || out_insertion_index == NULL); |
2806 uint32_t hash = name->Hash(); | 2808 uint32_t hash = name->Hash(); |
2807 int limit = high; | 2809 int limit = high; |
2808 | 2810 |
2809 DCHECK(low <= high); | 2811 DCHECK(low <= high); |
2810 | 2812 |
2811 while (low != high) { | 2813 while (low != high) { |
2812 int mid = (low + high) / 2; | 2814 int mid = (low + high) / 2; |
2813 Name* mid_name = array->GetSortedKey(mid); | 2815 Name* mid_name = array->GetSortedKey(mid); |
2814 uint32_t mid_hash = mid_name->Hash(); | 2816 uint32_t mid_hash = mid_name->Hash(); |
2815 | 2817 |
2816 if (mid_hash >= hash) { | 2818 if (mid_hash >= hash) { |
2817 high = mid; | 2819 high = mid; |
2818 } else { | 2820 } else { |
2819 low = mid + 1; | 2821 low = mid + 1; |
2820 } | 2822 } |
2821 } | 2823 } |
2822 | 2824 |
2823 for (; low <= limit; ++low) { | 2825 for (; low <= limit; ++low) { |
2824 int sort_index = array->GetSortedKeyIndex(low); | 2826 int sort_index = array->GetSortedKeyIndex(low); |
2825 Name* entry = array->GetKey(sort_index); | 2827 Name* entry = array->GetKey(sort_index); |
2826 if (entry->Hash() != hash) break; | 2828 uint32_t current_hash = entry->Hash(); |
| 2829 if (current_hash != hash) { |
| 2830 if (out_insertion_index != NULL) { |
| 2831 *out_insertion_index = sort_index + (current_hash > hash ? 0 : 1); |
| 2832 } |
| 2833 return T::kNotFound; |
| 2834 } |
2827 if (entry->Equals(name)) { | 2835 if (entry->Equals(name)) { |
2828 if (search_mode == ALL_ENTRIES || sort_index < valid_entries) { | 2836 if (search_mode == ALL_ENTRIES || sort_index < valid_entries) { |
2829 return sort_index; | 2837 return sort_index; |
2830 } | 2838 } |
2831 return T::kNotFound; | 2839 return T::kNotFound; |
2832 } | 2840 } |
2833 } | 2841 } |
2834 | 2842 |
| 2843 if (out_insertion_index != NULL) *out_insertion_index = limit + 1; |
2835 return T::kNotFound; | 2844 return T::kNotFound; |
2836 } | 2845 } |
2837 | 2846 |
2838 | 2847 |
2839 // Perform a linear search in this fixed array. len is the number of entry | 2848 // Perform a linear search in this fixed array. len is the number of entry |
2840 // indices that are valid. | 2849 // indices that are valid. |
2841 template<SearchMode search_mode, typename T> | 2850 template <SearchMode search_mode, typename T> |
2842 int LinearSearch(T* array, Name* name, int len, int valid_entries) { | 2851 int LinearSearch(T* array, Name* name, int len, int valid_entries, |
| 2852 int* out_insertion_index) { |
2843 uint32_t hash = name->Hash(); | 2853 uint32_t hash = name->Hash(); |
2844 if (search_mode == ALL_ENTRIES) { | 2854 if (search_mode == ALL_ENTRIES) { |
2845 for (int number = 0; number < len; number++) { | 2855 for (int number = 0; number < len; number++) { |
2846 int sorted_index = array->GetSortedKeyIndex(number); | 2856 int sorted_index = array->GetSortedKeyIndex(number); |
2847 Name* entry = array->GetKey(sorted_index); | 2857 Name* entry = array->GetKey(sorted_index); |
2848 uint32_t current_hash = entry->Hash(); | 2858 uint32_t current_hash = entry->Hash(); |
2849 if (current_hash > hash) break; | 2859 if (current_hash > hash) { |
| 2860 if (out_insertion_index != NULL) *out_insertion_index = sorted_index; |
| 2861 return T::kNotFound; |
| 2862 } |
2850 if (current_hash == hash && entry->Equals(name)) return sorted_index; | 2863 if (current_hash == hash && entry->Equals(name)) return sorted_index; |
2851 } | 2864 } |
| 2865 if (out_insertion_index != NULL) *out_insertion_index = len; |
| 2866 return T::kNotFound; |
2852 } else { | 2867 } else { |
2853 DCHECK(len >= valid_entries); | 2868 DCHECK(len >= valid_entries); |
| 2869 DCHECK_EQ(NULL, out_insertion_index); // Not supported here. |
2854 for (int number = 0; number < valid_entries; number++) { | 2870 for (int number = 0; number < valid_entries; number++) { |
2855 Name* entry = array->GetKey(number); | 2871 Name* entry = array->GetKey(number); |
2856 uint32_t current_hash = entry->Hash(); | 2872 uint32_t current_hash = entry->Hash(); |
2857 if (current_hash == hash && entry->Equals(name)) return number; | 2873 if (current_hash == hash && entry->Equals(name)) return number; |
2858 } | 2874 } |
| 2875 return T::kNotFound; |
2859 } | 2876 } |
2860 return T::kNotFound; | |
2861 } | 2877 } |
2862 | 2878 |
2863 | 2879 |
2864 template<SearchMode search_mode, typename T> | 2880 template <SearchMode search_mode, typename T> |
2865 int Search(T* array, Name* name, int valid_entries) { | 2881 int Search(T* array, Name* name, int valid_entries, int* out_insertion_index) { |
2866 if (search_mode == VALID_ENTRIES) { | 2882 if (search_mode == VALID_ENTRIES) { |
2867 SLOW_DCHECK(array->IsSortedNoDuplicates(valid_entries)); | 2883 SLOW_DCHECK(array->IsSortedNoDuplicates(valid_entries)); |
2868 } else { | 2884 } else { |
2869 SLOW_DCHECK(array->IsSortedNoDuplicates()); | 2885 SLOW_DCHECK(array->IsSortedNoDuplicates()); |
2870 } | 2886 } |
2871 | 2887 |
2872 int nof = array->number_of_entries(); | 2888 int nof = array->number_of_entries(); |
2873 if (nof == 0) return T::kNotFound; | 2889 if (nof == 0) { |
| 2890 if (out_insertion_index != NULL) *out_insertion_index = 0; |
| 2891 return T::kNotFound; |
| 2892 } |
2874 | 2893 |
2875 // Fast case: do linear search for small arrays. | 2894 // Fast case: do linear search for small arrays. |
2876 const int kMaxElementsForLinearSearch = 8; | 2895 const int kMaxElementsForLinearSearch = 8; |
2877 if ((search_mode == ALL_ENTRIES && | 2896 if ((search_mode == ALL_ENTRIES && |
2878 nof <= kMaxElementsForLinearSearch) || | 2897 nof <= kMaxElementsForLinearSearch) || |
2879 (search_mode == VALID_ENTRIES && | 2898 (search_mode == VALID_ENTRIES && |
2880 valid_entries <= (kMaxElementsForLinearSearch * 3))) { | 2899 valid_entries <= (kMaxElementsForLinearSearch * 3))) { |
2881 return LinearSearch<search_mode>(array, name, nof, valid_entries); | 2900 return LinearSearch<search_mode>(array, name, nof, valid_entries, |
| 2901 out_insertion_index); |
2882 } | 2902 } |
2883 | 2903 |
2884 // Slow case: perform binary search. | 2904 // Slow case: perform binary search. |
2885 return BinarySearch<search_mode>(array, name, 0, nof - 1, valid_entries); | 2905 return BinarySearch<search_mode>(array, name, 0, nof - 1, valid_entries, |
| 2906 out_insertion_index); |
2886 } | 2907 } |
2887 | 2908 |
2888 | 2909 |
2889 int DescriptorArray::Search(Name* name, int valid_descriptors) { | 2910 int DescriptorArray::Search(Name* name, int valid_descriptors) { |
2890 return internal::Search<VALID_ENTRIES>(this, name, valid_descriptors); | 2911 return internal::Search<VALID_ENTRIES>(this, name, valid_descriptors, NULL); |
2891 } | 2912 } |
2892 | 2913 |
2893 | 2914 |
2894 int DescriptorArray::SearchWithCache(Name* name, Map* map) { | 2915 int DescriptorArray::SearchWithCache(Name* name, Map* map) { |
2895 int number_of_own_descriptors = map->NumberOfOwnDescriptors(); | 2916 int number_of_own_descriptors = map->NumberOfOwnDescriptors(); |
2896 if (number_of_own_descriptors == 0) return kNotFound; | 2917 if (number_of_own_descriptors == 0) return kNotFound; |
2897 | 2918 |
2898 DescriptorLookupCache* cache = GetIsolate()->descriptor_lookup_cache(); | 2919 DescriptorLookupCache* cache = GetIsolate()->descriptor_lookup_cache(); |
2899 int number = cache->Lookup(map, name); | 2920 int number = cache->Lookup(map, name); |
2900 | 2921 |
(...skipping 4394 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
7295 #undef READ_SHORT_FIELD | 7316 #undef READ_SHORT_FIELD |
7296 #undef WRITE_SHORT_FIELD | 7317 #undef WRITE_SHORT_FIELD |
7297 #undef READ_BYTE_FIELD | 7318 #undef READ_BYTE_FIELD |
7298 #undef WRITE_BYTE_FIELD | 7319 #undef WRITE_BYTE_FIELD |
7299 #undef NOBARRIER_READ_BYTE_FIELD | 7320 #undef NOBARRIER_READ_BYTE_FIELD |
7300 #undef NOBARRIER_WRITE_BYTE_FIELD | 7321 #undef NOBARRIER_WRITE_BYTE_FIELD |
7301 | 7322 |
7302 } } // namespace v8::internal | 7323 } } // namespace v8::internal |
7303 | 7324 |
7304 #endif // V8_OBJECTS_INL_H_ | 7325 #endif // V8_OBJECTS_INL_H_ |
OLD | NEW |