| 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 |