| OLD | NEW |
| 1 // Copyright 2011 the V8 project authors. All rights reserved. | 1 // Copyright 2011 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 #ifndef V8_STRING_SEARCH_H_ | 5 #ifndef V8_STRING_SEARCH_H_ |
| 6 #define V8_STRING_SEARCH_H_ | 6 #define V8_STRING_SEARCH_H_ |
| 7 | 7 |
| 8 namespace v8 { | 8 namespace v8 { |
| 9 namespace internal { | 9 namespace internal { |
| 10 | 10 |
| (...skipping 84 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 95 StringSearch<PatternChar, SubjectChar>*, | 95 StringSearch<PatternChar, SubjectChar>*, |
| 96 Vector<const SubjectChar>, | 96 Vector<const SubjectChar>, |
| 97 int); | 97 int); |
| 98 | 98 |
| 99 static int FailSearch(StringSearch<PatternChar, SubjectChar>*, | 99 static int FailSearch(StringSearch<PatternChar, SubjectChar>*, |
| 100 Vector<const SubjectChar>, | 100 Vector<const SubjectChar>, |
| 101 int) { | 101 int) { |
| 102 return -1; | 102 return -1; |
| 103 } | 103 } |
| 104 | 104 |
| 105 static inline const SubjectChar* SafeMemChr(const SubjectChar* string, |
| 106 PatternChar pattern_char, |
| 107 size_t search_length) { |
| 108 if (search_length == 0) { |
| 109 return NULL; |
| 110 } else { |
| 111 return reinterpret_cast<const SubjectChar*>( |
| 112 memchr(string, pattern_char, search_length)); |
| 113 } |
| 114 } |
| 115 |
| 105 static int SingleCharSearch(StringSearch<PatternChar, SubjectChar>* search, | 116 static int SingleCharSearch(StringSearch<PatternChar, SubjectChar>* search, |
| 106 Vector<const SubjectChar> subject, | 117 Vector<const SubjectChar> subject, |
| 107 int start_index); | 118 int start_index); |
| 108 | 119 |
| 109 static int LinearSearch(StringSearch<PatternChar, SubjectChar>* search, | 120 static int LinearSearch(StringSearch<PatternChar, SubjectChar>* search, |
| 110 Vector<const SubjectChar> subject, | 121 Vector<const SubjectChar> subject, |
| 111 int start_index); | 122 int start_index); |
| 112 | 123 |
| 113 static int InitialSearch(StringSearch<PatternChar, SubjectChar>* search, | 124 static int InitialSearch(StringSearch<PatternChar, SubjectChar>* search, |
| 114 Vector<const SubjectChar> subject, | 125 Vector<const SubjectChar> subject, |
| (...skipping 78 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 193 | 204 |
| 194 template <typename PatternChar, typename SubjectChar> | 205 template <typename PatternChar, typename SubjectChar> |
| 195 int StringSearch<PatternChar, SubjectChar>::SingleCharSearch( | 206 int StringSearch<PatternChar, SubjectChar>::SingleCharSearch( |
| 196 StringSearch<PatternChar, SubjectChar>* search, | 207 StringSearch<PatternChar, SubjectChar>* search, |
| 197 Vector<const SubjectChar> subject, | 208 Vector<const SubjectChar> subject, |
| 198 int index) { | 209 int index) { |
| 199 ASSERT_EQ(1, search->pattern_.length()); | 210 ASSERT_EQ(1, search->pattern_.length()); |
| 200 PatternChar pattern_first_char = search->pattern_[0]; | 211 PatternChar pattern_first_char = search->pattern_[0]; |
| 201 int i = index; | 212 int i = index; |
| 202 if (sizeof(SubjectChar) == 1 && sizeof(PatternChar) == 1) { | 213 if (sizeof(SubjectChar) == 1 && sizeof(PatternChar) == 1) { |
| 203 const SubjectChar* pos = reinterpret_cast<const SubjectChar*>( | 214 const SubjectChar* pos = SafeMemChr(subject.start() + i, pattern_first_char, |
| 204 memchr(subject.start() + i, | 215 subject.length() - i); |
| 205 pattern_first_char, | |
| 206 subject.length() - i)); | |
| 207 if (pos == NULL) return -1; | 216 if (pos == NULL) return -1; |
| 208 return static_cast<int>(pos - subject.start()); | 217 return static_cast<int>(pos - subject.start()); |
| 209 } else { | 218 } else { |
| 210 if (sizeof(PatternChar) > sizeof(SubjectChar)) { | 219 if (sizeof(PatternChar) > sizeof(SubjectChar)) { |
| 211 if (exceedsOneByte(pattern_first_char)) { | 220 if (exceedsOneByte(pattern_first_char)) { |
| 212 return -1; | 221 return -1; |
| 213 } | 222 } |
| 214 } | 223 } |
| 215 SubjectChar search_char = static_cast<SubjectChar>(pattern_first_char); | 224 SubjectChar search_char = static_cast<SubjectChar>(pattern_first_char); |
| 216 int n = subject.length(); | 225 int n = subject.length(); |
| (...skipping 32 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 249 Vector<const SubjectChar> subject, | 258 Vector<const SubjectChar> subject, |
| 250 int index) { | 259 int index) { |
| 251 Vector<const PatternChar> pattern = search->pattern_; | 260 Vector<const PatternChar> pattern = search->pattern_; |
| 252 ASSERT(pattern.length() > 1); | 261 ASSERT(pattern.length() > 1); |
| 253 int pattern_length = pattern.length(); | 262 int pattern_length = pattern.length(); |
| 254 PatternChar pattern_first_char = pattern[0]; | 263 PatternChar pattern_first_char = pattern[0]; |
| 255 int i = index; | 264 int i = index; |
| 256 int n = subject.length() - pattern_length; | 265 int n = subject.length() - pattern_length; |
| 257 while (i <= n) { | 266 while (i <= n) { |
| 258 if (sizeof(SubjectChar) == 1 && sizeof(PatternChar) == 1) { | 267 if (sizeof(SubjectChar) == 1 && sizeof(PatternChar) == 1) { |
| 259 const SubjectChar* pos = reinterpret_cast<const SubjectChar*>( | 268 const SubjectChar* pos = |
| 260 memchr(subject.start() + i, | 269 SafeMemChr(subject.start() + i, pattern_first_char, n - i + 1); |
| 261 pattern_first_char, | |
| 262 n - i + 1)); | |
| 263 if (pos == NULL) return -1; | 270 if (pos == NULL) return -1; |
| 264 i = static_cast<int>(pos - subject.start()) + 1; | 271 i = static_cast<int>(pos - subject.start()) + 1; |
| 265 } else { | 272 } else { |
| 266 if (subject[i++] != pattern_first_char) continue; | 273 if (subject[i++] != pattern_first_char) continue; |
| 267 } | 274 } |
| 268 // Loop extracted to separate function to allow using return to do | 275 // Loop extracted to separate function to allow using return to do |
| 269 // a deeper break. | 276 // a deeper break. |
| 270 if (CharCompare(pattern.start() + 1, | 277 if (CharCompare(pattern.start() + 1, |
| 271 subject.start() + i, | 278 subject.start() + i, |
| 272 pattern_length - 1)) { | 279 pattern_length - 1)) { |
| (...skipping 227 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 500 // algorithm. | 507 // algorithm. |
| 501 int badness = -10 - (pattern_length << 2); | 508 int badness = -10 - (pattern_length << 2); |
| 502 | 509 |
| 503 // We know our pattern is at least 2 characters, we cache the first so | 510 // We know our pattern is at least 2 characters, we cache the first so |
| 504 // the common case of the first character not matching is faster. | 511 // the common case of the first character not matching is faster. |
| 505 PatternChar pattern_first_char = pattern[0]; | 512 PatternChar pattern_first_char = pattern[0]; |
| 506 for (int i = index, n = subject.length() - pattern_length; i <= n; i++) { | 513 for (int i = index, n = subject.length() - pattern_length; i <= n; i++) { |
| 507 badness++; | 514 badness++; |
| 508 if (badness <= 0) { | 515 if (badness <= 0) { |
| 509 if (sizeof(SubjectChar) == 1 && sizeof(PatternChar) == 1) { | 516 if (sizeof(SubjectChar) == 1 && sizeof(PatternChar) == 1) { |
| 510 const SubjectChar* pos = reinterpret_cast<const SubjectChar*>( | 517 const SubjectChar* pos = |
| 511 memchr(subject.start() + i, | 518 SafeMemChr(subject.start() + i, pattern_first_char, n - i + 1); |
| 512 pattern_first_char, | |
| 513 n - i + 1)); | |
| 514 if (pos == NULL) { | 519 if (pos == NULL) { |
| 515 return -1; | 520 return -1; |
| 516 } | 521 } |
| 517 i = static_cast<int>(pos - subject.start()); | 522 i = static_cast<int>(pos - subject.start()); |
| 518 } else { | 523 } else { |
| 519 if (subject[i] != pattern_first_char) continue; | 524 if (subject[i] != pattern_first_char) continue; |
| 520 } | 525 } |
| 521 int j = 1; | 526 int j = 1; |
| 522 do { | 527 do { |
| 523 if (pattern[j] != subject[i + j]) { | 528 if (pattern[j] != subject[i + j]) { |
| (...skipping 24 matching lines...) Expand all Loading... |
| 548 Vector<const SubjectChar> subject, | 553 Vector<const SubjectChar> subject, |
| 549 Vector<const PatternChar> pattern, | 554 Vector<const PatternChar> pattern, |
| 550 int start_index) { | 555 int start_index) { |
| 551 StringSearch<PatternChar, SubjectChar> search(isolate, pattern); | 556 StringSearch<PatternChar, SubjectChar> search(isolate, pattern); |
| 552 return search.Search(subject, start_index); | 557 return search.Search(subject, start_index); |
| 553 } | 558 } |
| 554 | 559 |
| 555 }} // namespace v8::internal | 560 }} // namespace v8::internal |
| 556 | 561 |
| 557 #endif // V8_STRING_SEARCH_H_ | 562 #endif // V8_STRING_SEARCH_H_ |
| OLD | NEW |