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 2835 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2846 | 2846 |
2847 void DescriptorArray::SetNumberOfDescriptors(int number_of_descriptors) { | 2847 void DescriptorArray::SetNumberOfDescriptors(int number_of_descriptors) { |
2848 WRITE_FIELD( | 2848 WRITE_FIELD( |
2849 this, kDescriptorLengthOffset, Smi::FromInt(number_of_descriptors)); | 2849 this, kDescriptorLengthOffset, Smi::FromInt(number_of_descriptors)); |
2850 } | 2850 } |
2851 | 2851 |
2852 | 2852 |
2853 // Perform a binary search in a fixed array. Low and high are entry indices. If | 2853 // Perform a binary search in a fixed array. Low and high are entry indices. If |
2854 // there are three entries in this array it should be called with low=0 and | 2854 // there are three entries in this array it should be called with low=0 and |
2855 // high=2. | 2855 // high=2. |
2856 template <SearchMode search_mode, typename T> | 2856 template<SearchMode search_mode, typename T> |
2857 int BinarySearch(T* array, Name* name, int low, int high, int valid_entries, | 2857 int BinarySearch(T* array, Name* name, int low, int high, int valid_entries) { |
2858 int* out_insertion_index) { | |
2859 DCHECK(search_mode == ALL_ENTRIES || out_insertion_index == NULL); | |
2860 uint32_t hash = name->Hash(); | 2858 uint32_t hash = name->Hash(); |
2861 int limit = high; | 2859 int limit = high; |
2862 | 2860 |
2863 DCHECK(low <= high); | 2861 DCHECK(low <= high); |
2864 | 2862 |
2865 while (low != high) { | 2863 while (low != high) { |
2866 int mid = (low + high) / 2; | 2864 int mid = (low + high) / 2; |
2867 Name* mid_name = array->GetSortedKey(mid); | 2865 Name* mid_name = array->GetSortedKey(mid); |
2868 uint32_t mid_hash = mid_name->Hash(); | 2866 uint32_t mid_hash = mid_name->Hash(); |
2869 | 2867 |
2870 if (mid_hash >= hash) { | 2868 if (mid_hash >= hash) { |
2871 high = mid; | 2869 high = mid; |
2872 } else { | 2870 } else { |
2873 low = mid + 1; | 2871 low = mid + 1; |
2874 } | 2872 } |
2875 } | 2873 } |
2876 | 2874 |
2877 for (; low <= limit; ++low) { | 2875 for (; low <= limit; ++low) { |
2878 int sort_index = array->GetSortedKeyIndex(low); | 2876 int sort_index = array->GetSortedKeyIndex(low); |
2879 Name* entry = array->GetKey(sort_index); | 2877 Name* entry = array->GetKey(sort_index); |
2880 uint32_t current_hash = entry->Hash(); | 2878 if (entry->Hash() != hash) break; |
2881 if (current_hash != hash) { | |
2882 if (out_insertion_index != NULL) { | |
2883 *out_insertion_index = sort_index + (current_hash > hash ? 0 : 1); | |
2884 } | |
2885 return T::kNotFound; | |
2886 } | |
2887 if (entry->Equals(name)) { | 2879 if (entry->Equals(name)) { |
2888 if (search_mode == ALL_ENTRIES || sort_index < valid_entries) { | 2880 if (search_mode == ALL_ENTRIES || sort_index < valid_entries) { |
2889 return sort_index; | 2881 return sort_index; |
2890 } | 2882 } |
2891 return T::kNotFound; | 2883 return T::kNotFound; |
2892 } | 2884 } |
2893 } | 2885 } |
2894 | 2886 |
2895 if (out_insertion_index != NULL) *out_insertion_index = limit + 1; | |
2896 return T::kNotFound; | 2887 return T::kNotFound; |
2897 } | 2888 } |
2898 | 2889 |
2899 | 2890 |
2900 // Perform a linear search in this fixed array. len is the number of entry | 2891 // Perform a linear search in this fixed array. len is the number of entry |
2901 // indices that are valid. | 2892 // indices that are valid. |
2902 template <SearchMode search_mode, typename T> | 2893 template<SearchMode search_mode, typename T> |
2903 int LinearSearch(T* array, Name* name, int len, int valid_entries, | 2894 int LinearSearch(T* array, Name* name, int len, int valid_entries) { |
2904 int* out_insertion_index) { | |
2905 uint32_t hash = name->Hash(); | 2895 uint32_t hash = name->Hash(); |
2906 if (search_mode == ALL_ENTRIES) { | 2896 if (search_mode == ALL_ENTRIES) { |
2907 for (int number = 0; number < len; number++) { | 2897 for (int number = 0; number < len; number++) { |
2908 int sorted_index = array->GetSortedKeyIndex(number); | 2898 int sorted_index = array->GetSortedKeyIndex(number); |
2909 Name* entry = array->GetKey(sorted_index); | 2899 Name* entry = array->GetKey(sorted_index); |
2910 uint32_t current_hash = entry->Hash(); | 2900 uint32_t current_hash = entry->Hash(); |
2911 if (current_hash > hash) { | 2901 if (current_hash > hash) break; |
2912 if (out_insertion_index != NULL) *out_insertion_index = sorted_index; | |
2913 return T::kNotFound; | |
2914 } | |
2915 if (current_hash == hash && entry->Equals(name)) return sorted_index; | 2902 if (current_hash == hash && entry->Equals(name)) return sorted_index; |
2916 } | 2903 } |
2917 if (out_insertion_index != NULL) *out_insertion_index = len; | |
2918 return T::kNotFound; | |
2919 } else { | 2904 } else { |
2920 DCHECK(len >= valid_entries); | 2905 DCHECK(len >= valid_entries); |
2921 DCHECK_EQ(NULL, out_insertion_index); // Not supported here. | |
2922 for (int number = 0; number < valid_entries; number++) { | 2906 for (int number = 0; number < valid_entries; number++) { |
2923 Name* entry = array->GetKey(number); | 2907 Name* entry = array->GetKey(number); |
2924 uint32_t current_hash = entry->Hash(); | 2908 uint32_t current_hash = entry->Hash(); |
2925 if (current_hash == hash && entry->Equals(name)) return number; | 2909 if (current_hash == hash && entry->Equals(name)) return number; |
2926 } | 2910 } |
2927 return T::kNotFound; | |
2928 } | 2911 } |
| 2912 return T::kNotFound; |
2929 } | 2913 } |
2930 | 2914 |
2931 | 2915 |
2932 template <SearchMode search_mode, typename T> | 2916 template<SearchMode search_mode, typename T> |
2933 int Search(T* array, Name* name, int valid_entries, int* out_insertion_index) { | 2917 int Search(T* array, Name* name, int valid_entries) { |
2934 if (search_mode == VALID_ENTRIES) { | 2918 if (search_mode == VALID_ENTRIES) { |
2935 SLOW_DCHECK(array->IsSortedNoDuplicates(valid_entries)); | 2919 SLOW_DCHECK(array->IsSortedNoDuplicates(valid_entries)); |
2936 } else { | 2920 } else { |
2937 SLOW_DCHECK(array->IsSortedNoDuplicates()); | 2921 SLOW_DCHECK(array->IsSortedNoDuplicates()); |
2938 } | 2922 } |
2939 | 2923 |
2940 int nof = array->number_of_entries(); | 2924 int nof = array->number_of_entries(); |
2941 if (nof == 0) { | 2925 if (nof == 0) return T::kNotFound; |
2942 if (out_insertion_index != NULL) *out_insertion_index = 0; | |
2943 return T::kNotFound; | |
2944 } | |
2945 | 2926 |
2946 // Fast case: do linear search for small arrays. | 2927 // Fast case: do linear search for small arrays. |
2947 const int kMaxElementsForLinearSearch = 8; | 2928 const int kMaxElementsForLinearSearch = 8; |
2948 if ((search_mode == ALL_ENTRIES && | 2929 if ((search_mode == ALL_ENTRIES && |
2949 nof <= kMaxElementsForLinearSearch) || | 2930 nof <= kMaxElementsForLinearSearch) || |
2950 (search_mode == VALID_ENTRIES && | 2931 (search_mode == VALID_ENTRIES && |
2951 valid_entries <= (kMaxElementsForLinearSearch * 3))) { | 2932 valid_entries <= (kMaxElementsForLinearSearch * 3))) { |
2952 return LinearSearch<search_mode>(array, name, nof, valid_entries, | 2933 return LinearSearch<search_mode>(array, name, nof, valid_entries); |
2953 out_insertion_index); | |
2954 } | 2934 } |
2955 | 2935 |
2956 // Slow case: perform binary search. | 2936 // Slow case: perform binary search. |
2957 return BinarySearch<search_mode>(array, name, 0, nof - 1, valid_entries, | 2937 return BinarySearch<search_mode>(array, name, 0, nof - 1, valid_entries); |
2958 out_insertion_index); | |
2959 } | 2938 } |
2960 | 2939 |
2961 | 2940 |
2962 int DescriptorArray::Search(Name* name, int valid_descriptors) { | 2941 int DescriptorArray::Search(Name* name, int valid_descriptors) { |
2963 return internal::Search<VALID_ENTRIES>(this, name, valid_descriptors, NULL); | 2942 return internal::Search<VALID_ENTRIES>(this, name, valid_descriptors); |
2964 } | 2943 } |
2965 | 2944 |
2966 | 2945 |
2967 int DescriptorArray::SearchWithCache(Name* name, Map* map) { | 2946 int DescriptorArray::SearchWithCache(Name* name, Map* map) { |
2968 int number_of_own_descriptors = map->NumberOfOwnDescriptors(); | 2947 int number_of_own_descriptors = map->NumberOfOwnDescriptors(); |
2969 if (number_of_own_descriptors == 0) return kNotFound; | 2948 if (number_of_own_descriptors == 0) return kNotFound; |
2970 | 2949 |
2971 DescriptorLookupCache* cache = GetIsolate()->descriptor_lookup_cache(); | 2950 DescriptorLookupCache* cache = GetIsolate()->descriptor_lookup_cache(); |
2972 int number = cache->Lookup(map, name); | 2951 int number = cache->Lookup(map, name); |
2973 | 2952 |
(...skipping 4477 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
7451 #undef READ_SHORT_FIELD | 7430 #undef READ_SHORT_FIELD |
7452 #undef WRITE_SHORT_FIELD | 7431 #undef WRITE_SHORT_FIELD |
7453 #undef READ_BYTE_FIELD | 7432 #undef READ_BYTE_FIELD |
7454 #undef WRITE_BYTE_FIELD | 7433 #undef WRITE_BYTE_FIELD |
7455 #undef NOBARRIER_READ_BYTE_FIELD | 7434 #undef NOBARRIER_READ_BYTE_FIELD |
7456 #undef NOBARRIER_WRITE_BYTE_FIELD | 7435 #undef NOBARRIER_WRITE_BYTE_FIELD |
7457 | 7436 |
7458 } } // namespace v8::internal | 7437 } } // namespace v8::internal |
7459 | 7438 |
7460 #endif // V8_OBJECTS_INL_H_ | 7439 #endif // V8_OBJECTS_INL_H_ |
OLD | NEW |