OLD | NEW |
1 // Copyright 2006-2009 the V8 project authors. All rights reserved. | 1 // Copyright 2006-2009 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 2812 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2823 // final result of searching for the patter in the subject. | 2823 // final result of searching for the patter in the subject. |
2824 // If "complete" is set to false, the return value is the index where | 2824 // If "complete" is set to false, the return value is the index where |
2825 // further checking should start, i.e., it's guaranteed that the pattern | 2825 // further checking should start, i.e., it's guaranteed that the pattern |
2826 // does not occur at a position prior to the returned index. | 2826 // does not occur at a position prior to the returned index. |
2827 template <typename pchar, typename schar> | 2827 template <typename pchar, typename schar> |
2828 static int SimpleIndexOf(Vector<const schar> subject, | 2828 static int SimpleIndexOf(Vector<const schar> subject, |
2829 Vector<const pchar> pattern, | 2829 Vector<const pchar> pattern, |
2830 int idx, | 2830 int idx, |
2831 bool* complete) { | 2831 bool* complete) { |
2832 ASSERT(pattern.length() > 1); | 2832 ASSERT(pattern.length() > 1); |
| 2833 int pattern_length = pattern.length(); |
2833 // Badness is a count of how much work we have done. When we have | 2834 // Badness is a count of how much work we have done. When we have |
2834 // done enough work we decide it's probably worth switching to a better | 2835 // done enough work we decide it's probably worth switching to a better |
2835 // algorithm. | 2836 // algorithm. |
2836 int badness = -10 - (pattern.length() << 2); | 2837 int badness = -10 - (pattern_length << 2); |
2837 | 2838 |
2838 // We know our pattern is at least 2 characters, we cache the first so | 2839 // We know our pattern is at least 2 characters, we cache the first so |
2839 // the common case of the first character not matching is faster. | 2840 // the common case of the first character not matching is faster. |
2840 pchar pattern_first_char = pattern[0]; | 2841 pchar pattern_first_char = pattern[0]; |
2841 for (int i = idx, n = subject.length() - pattern.length(); i <= n; i++) { | 2842 for (int i = idx, n = subject.length() - pattern_length; i <= n; i++) { |
2842 badness++; | 2843 badness++; |
2843 if (badness > 0) { | 2844 if (badness > 0) { |
2844 *complete = false; | 2845 *complete = false; |
2845 return i; | 2846 return i; |
2846 } | 2847 } |
2847 if (sizeof(schar) == 1 && sizeof(pchar) == 1) { | 2848 if (sizeof(schar) == 1 && sizeof(pchar) == 1) { |
2848 const schar* pos = reinterpret_cast<const schar*>( | 2849 const schar* pos = reinterpret_cast<const schar*>( |
2849 memchr(subject.start() + i, | 2850 memchr(subject.start() + i, |
2850 pattern_first_char, | 2851 pattern_first_char, |
2851 n - i + 1)); | 2852 n - i + 1)); |
2852 if (pos == NULL) { | 2853 if (pos == NULL) { |
2853 *complete = true; | 2854 *complete = true; |
2854 return -1; | 2855 return -1; |
2855 } | 2856 } |
2856 i = static_cast<int>(pos - subject.start()); | 2857 i = static_cast<int>(pos - subject.start()); |
2857 } else { | 2858 } else { |
2858 if (subject[i] != pattern_first_char) continue; | 2859 if (subject[i] != pattern_first_char) continue; |
2859 } | 2860 } |
2860 int j = 1; | 2861 int j = 1; |
2861 do { | 2862 do { |
2862 if (pattern[j] != subject[i+j]) { | 2863 if (pattern[j] != subject[i+j]) { |
2863 break; | 2864 break; |
2864 } | 2865 } |
2865 j++; | 2866 j++; |
2866 } while (j < pattern.length()); | 2867 } while (j < pattern_length); |
2867 if (j == pattern.length()) { | 2868 if (j == pattern_length) { |
2868 *complete = true; | 2869 *complete = true; |
2869 return i; | 2870 return i; |
2870 } | 2871 } |
2871 badness += j; | 2872 badness += j; |
2872 } | 2873 } |
2873 *complete = true; | 2874 *complete = true; |
2874 return -1; | 2875 return -1; |
2875 } | 2876 } |
2876 | 2877 |
2877 // Simple indexOf that never bails out. For short patterns only. | 2878 // Simple indexOf that never bails out. For short patterns only. |
2878 template <typename pchar, typename schar> | 2879 template <typename pchar, typename schar> |
2879 static int SimpleIndexOf(Vector<const schar> subject, | 2880 static int SimpleIndexOf(Vector<const schar> subject, |
2880 Vector<const pchar> pattern, | 2881 Vector<const pchar> pattern, |
2881 int idx) { | 2882 int idx) { |
| 2883 int pattern_length = pattern.length(); |
2882 pchar pattern_first_char = pattern[0]; | 2884 pchar pattern_first_char = pattern[0]; |
2883 for (int i = idx, n = subject.length() - pattern.length(); i <= n; i++) { | 2885 for (int i = idx, n = subject.length() - pattern_length; i <= n; i++) { |
2884 if (sizeof(schar) == 1 && sizeof(pchar) == 1) { | 2886 if (sizeof(schar) == 1 && sizeof(pchar) == 1) { |
2885 const schar* pos = reinterpret_cast<const schar*>( | 2887 const schar* pos = reinterpret_cast<const schar*>( |
2886 memchr(subject.start() + i, | 2888 memchr(subject.start() + i, |
2887 pattern_first_char, | 2889 pattern_first_char, |
2888 n - i + 1)); | 2890 n - i + 1)); |
2889 if (pos == NULL) return -1; | 2891 if (pos == NULL) return -1; |
2890 i = static_cast<int>(pos - subject.start()); | 2892 i = static_cast<int>(pos - subject.start()); |
2891 } else { | 2893 } else { |
2892 if (subject[i] != pattern_first_char) continue; | 2894 if (subject[i] != pattern_first_char) continue; |
2893 } | 2895 } |
2894 int j = 1; | 2896 int j = 1; |
2895 while (j < pattern.length()) { | 2897 while (j < pattern_length) { |
2896 if (pattern[j] != subject[i+j]) { | 2898 if (pattern[j] != subject[i+j]) { |
2897 break; | 2899 break; |
2898 } | 2900 } |
2899 j++; | 2901 j++; |
2900 } | 2902 } |
2901 if (j == pattern.length()) { | 2903 if (j == pattern_length) { |
2902 return i; | 2904 return i; |
2903 } | 2905 } |
2904 } | 2906 } |
2905 return -1; | 2907 return -1; |
2906 } | 2908 } |
2907 | 2909 |
2908 | 2910 |
2909 // Strategy for searching for a string in another string. | 2911 // Strategy for searching for a string in another string. |
2910 enum StringSearchStrategy { SEARCH_FAIL, SEARCH_SHORT, SEARCH_LONG }; | 2912 enum StringSearchStrategy { SEARCH_FAIL, SEARCH_SHORT, SEARCH_LONG }; |
2911 | 2913 |
(...skipping 123 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3035 uint32_t start_index; | 3037 uint32_t start_index; |
3036 if (!index->ToArrayIndex(&start_index)) return Smi::FromInt(-1); | 3038 if (!index->ToArrayIndex(&start_index)) return Smi::FromInt(-1); |
3037 | 3039 |
3038 RUNTIME_ASSERT(start_index <= static_cast<uint32_t>(sub->length())); | 3040 RUNTIME_ASSERT(start_index <= static_cast<uint32_t>(sub->length())); |
3039 int position = Runtime::StringMatch(sub, pat, start_index); | 3041 int position = Runtime::StringMatch(sub, pat, start_index); |
3040 return Smi::FromInt(position); | 3042 return Smi::FromInt(position); |
3041 } | 3043 } |
3042 | 3044 |
3043 | 3045 |
3044 template <typename schar, typename pchar> | 3046 template <typename schar, typename pchar> |
3045 static int StringMatchBackwards(Vector<const schar> sub, | 3047 static int StringMatchBackwards(Vector<const schar> subject, |
3046 Vector<const pchar> pat, | 3048 Vector<const pchar> pattern, |
3047 int idx) { | 3049 int idx) { |
3048 ASSERT(pat.length() >= 1); | 3050 int pattern_length = pattern.length(); |
3049 ASSERT(idx + pat.length() <= sub.length()); | 3051 ASSERT(pattern_length >= 1); |
| 3052 ASSERT(idx + pattern_length <= subject.length()); |
3050 | 3053 |
3051 if (sizeof(schar) == 1 && sizeof(pchar) > 1) { | 3054 if (sizeof(schar) == 1 && sizeof(pchar) > 1) { |
3052 for (int i = 0; i < pat.length(); i++) { | 3055 for (int i = 0; i < pattern_length; i++) { |
3053 uc16 c = pat[i]; | 3056 uc16 c = pattern[i]; |
3054 if (c > String::kMaxAsciiCharCode) { | 3057 if (c > String::kMaxAsciiCharCode) { |
3055 return -1; | 3058 return -1; |
3056 } | 3059 } |
3057 } | 3060 } |
3058 } | 3061 } |
3059 | 3062 |
3060 pchar pattern_first_char = pat[0]; | 3063 pchar pattern_first_char = pattern[0]; |
3061 for (int i = idx; i >= 0; i--) { | 3064 for (int i = idx; i >= 0; i--) { |
3062 if (sub[i] != pattern_first_char) continue; | 3065 if (subject[i] != pattern_first_char) continue; |
3063 int j = 1; | 3066 int j = 1; |
3064 while (j < pat.length()) { | 3067 while (j < pattern_length) { |
3065 if (pat[j] != sub[i+j]) { | 3068 if (pattern[j] != subject[i+j]) { |
3066 break; | 3069 break; |
3067 } | 3070 } |
3068 j++; | 3071 j++; |
3069 } | 3072 } |
3070 if (j == pat.length()) { | 3073 if (j == pattern_length) { |
3071 return i; | 3074 return i; |
3072 } | 3075 } |
3073 } | 3076 } |
3074 return -1; | 3077 return -1; |
3075 } | 3078 } |
3076 | 3079 |
3077 static Object* Runtime_StringLastIndexOf(Arguments args) { | 3080 static Object* Runtime_StringLastIndexOf(Arguments args) { |
3078 HandleScope scope; // create a new handle scope | 3081 HandleScope scope; // create a new handle scope |
3079 ASSERT(args.length() == 3); | 3082 ASSERT(args.length() == 3); |
3080 | 3083 |
(...skipping 7447 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
10528 } else { | 10531 } else { |
10529 // Handle last resort GC and make sure to allow future allocations | 10532 // Handle last resort GC and make sure to allow future allocations |
10530 // to grow the heap without causing GCs (if possible). | 10533 // to grow the heap without causing GCs (if possible). |
10531 Counters::gc_last_resort_from_js.Increment(); | 10534 Counters::gc_last_resort_from_js.Increment(); |
10532 Heap::CollectAllGarbage(false); | 10535 Heap::CollectAllGarbage(false); |
10533 } | 10536 } |
10534 } | 10537 } |
10535 | 10538 |
10536 | 10539 |
10537 } } // namespace v8::internal | 10540 } } // namespace v8::internal |
OLD | NEW |