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 2017 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2028 int idx) { | 2028 int idx) { |
2029 int n = subject.length(); | 2029 int n = subject.length(); |
2030 int m = pattern.length(); | 2030 int m = pattern.length(); |
2031 // Only preprocess at most kBMMaxShift last characters of pattern. | 2031 // Only preprocess at most kBMMaxShift last characters of pattern. |
2032 int start = m < kBMMaxShift ? 0 : m - kBMMaxShift; | 2032 int start = m < kBMMaxShift ? 0 : m - kBMMaxShift; |
2033 | 2033 |
2034 // Build the Good Suffix table and continue searching. | 2034 // Build the Good Suffix table and continue searching. |
2035 BoyerMoorePopulateGoodSuffixTable(pattern, start); | 2035 BoyerMoorePopulateGoodSuffixTable(pattern, start); |
2036 pchar last_char = pattern[m - 1]; | 2036 pchar last_char = pattern[m - 1]; |
2037 // Continue search from i. | 2037 // Continue search from i. |
2038 do { | 2038 while (idx <= n - m) { |
2039 int j = m - 1; | 2039 int j = m - 1; |
2040 schar c; | 2040 schar c; |
2041 while (last_char != (c = subject[idx + j])) { | 2041 while (last_char != (c = subject[idx + j])) { |
2042 int shift = j - CharOccurrence<schar, pchar>(c); | 2042 int shift = j - CharOccurrence<schar, pchar>(c); |
2043 idx += shift; | 2043 idx += shift; |
2044 if (idx > n - m) { | 2044 if (idx > n - m) { |
2045 return -1; | 2045 return -1; |
2046 } | 2046 } |
2047 } | 2047 } |
2048 while (j >= 0 && pattern[j] == (c = subject[idx + j])) j--; | 2048 while (j >= 0 && pattern[j] == (c = subject[idx + j])) j--; |
2049 if (j < 0) { | 2049 if (j < 0) { |
2050 return idx; | 2050 return idx; |
2051 } else if (j < start) { | 2051 } else if (j < start) { |
2052 // we have matched more than our tables allow us to be smart about. | 2052 // we have matched more than our tables allow us to be smart about. |
2053 // Fall back on BMH shift. | 2053 // Fall back on BMH shift. |
2054 idx += m - 1 - CharOccurrence<schar, pchar>(last_char); | 2054 idx += m - 1 - CharOccurrence<schar, pchar>(last_char); |
2055 } else { | 2055 } else { |
2056 int gs_shift = bmgs_buffers.shift(j + 1); // Good suffix shift. | 2056 int gs_shift = bmgs_buffers.shift(j + 1); // Good suffix shift. |
2057 int bc_occ = CharOccurrence<schar, pchar>(c); | 2057 int bc_occ = CharOccurrence<schar, pchar>(c); |
2058 int shift = j - bc_occ; // Bad-char shift. | 2058 int shift = j - bc_occ; // Bad-char shift. |
2059 if (gs_shift > shift) { | 2059 if (gs_shift > shift) { |
2060 shift = gs_shift; | 2060 shift = gs_shift; |
2061 } | 2061 } |
2062 idx += shift; | 2062 idx += shift; |
2063 } | 2063 } |
2064 } while (idx <= n - m); | 2064 } |
2065 | 2065 |
2066 return -1; | 2066 return -1; |
2067 } | 2067 } |
2068 | 2068 |
2069 | 2069 |
2070 template <typename schar> | 2070 template <typename schar> |
2071 static int SingleCharIndexOf(Vector<const schar> string, | 2071 static int SingleCharIndexOf(Vector<const schar> string, |
2072 schar pattern_char, | 2072 schar pattern_char, |
2073 int start_index) { | 2073 int start_index) { |
2074 for (int i = start_index, n = string.length(); i < n; i++) { | 2074 for (int i = start_index, n = string.length(); i < n; i++) { |
(...skipping 4952 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
7027 } else { | 7027 } else { |
7028 // Handle last resort GC and make sure to allow future allocations | 7028 // Handle last resort GC and make sure to allow future allocations |
7029 // to grow the heap without causing GCs (if possible). | 7029 // to grow the heap without causing GCs (if possible). |
7030 Counters::gc_last_resort_from_js.Increment(); | 7030 Counters::gc_last_resort_from_js.Increment(); |
7031 Heap::CollectAllGarbage(); | 7031 Heap::CollectAllGarbage(); |
7032 } | 7032 } |
7033 } | 7033 } |
7034 | 7034 |
7035 | 7035 |
7036 } } // namespace v8::internal | 7036 } } // namespace v8::internal |
OLD | NEW |