| 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 66 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 77 | 77 |
| 78 int Search(Vector<const SubjectChar> subject, int index) { | 78 int Search(Vector<const SubjectChar> subject, int index) { |
| 79 return strategy_(this, subject, index); | 79 return strategy_(this, subject, index); |
| 80 } | 80 } |
| 81 | 81 |
| 82 static inline int AlphabetSize() { | 82 static inline int AlphabetSize() { |
| 83 if (sizeof(PatternChar) == 1) { | 83 if (sizeof(PatternChar) == 1) { |
| 84 // ASCII needle. | 84 // ASCII needle. |
| 85 return kAsciiAlphabetSize; | 85 return kAsciiAlphabetSize; |
| 86 } else { | 86 } else { |
| 87 ASSERT(sizeof(PatternChar) == 2); | 87 DCHECK(sizeof(PatternChar) == 2); |
| 88 // UC16 needle. | 88 // UC16 needle. |
| 89 return kUC16AlphabetSize; | 89 return kUC16AlphabetSize; |
| 90 } | 90 } |
| 91 } | 91 } |
| 92 | 92 |
| 93 private: | 93 private: |
| 94 typedef int (*SearchFunction)( // NOLINT - it's not a cast! | 94 typedef int (*SearchFunction)( // NOLINT - it's not a cast! |
| 95 StringSearch<PatternChar, SubjectChar>*, | 95 StringSearch<PatternChar, SubjectChar>*, |
| 96 Vector<const SubjectChar>, | 96 Vector<const SubjectChar>, |
| 97 int); | 97 int); |
| (...skipping 91 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 189 | 189 |
| 190 //--------------------------------------------------------------------- | 190 //--------------------------------------------------------------------- |
| 191 // Single Character Pattern Search Strategy | 191 // Single Character Pattern Search Strategy |
| 192 //--------------------------------------------------------------------- | 192 //--------------------------------------------------------------------- |
| 193 | 193 |
| 194 template <typename PatternChar, typename SubjectChar> | 194 template <typename PatternChar, typename SubjectChar> |
| 195 int StringSearch<PatternChar, SubjectChar>::SingleCharSearch( | 195 int StringSearch<PatternChar, SubjectChar>::SingleCharSearch( |
| 196 StringSearch<PatternChar, SubjectChar>* search, | 196 StringSearch<PatternChar, SubjectChar>* search, |
| 197 Vector<const SubjectChar> subject, | 197 Vector<const SubjectChar> subject, |
| 198 int index) { | 198 int index) { |
| 199 ASSERT_EQ(1, search->pattern_.length()); | 199 DCHECK_EQ(1, search->pattern_.length()); |
| 200 PatternChar pattern_first_char = search->pattern_[0]; | 200 PatternChar pattern_first_char = search->pattern_[0]; |
| 201 int i = index; | 201 int i = index; |
| 202 if (sizeof(SubjectChar) == 1 && sizeof(PatternChar) == 1) { | 202 if (sizeof(SubjectChar) == 1 && sizeof(PatternChar) == 1) { |
| 203 const SubjectChar* pos = reinterpret_cast<const SubjectChar*>( | 203 const SubjectChar* pos = reinterpret_cast<const SubjectChar*>( |
| 204 memchr(subject.start() + i, | 204 memchr(subject.start() + i, |
| 205 pattern_first_char, | 205 pattern_first_char, |
| 206 subject.length() - i)); | 206 subject.length() - i)); |
| 207 if (pos == NULL) return -1; | 207 if (pos == NULL) return -1; |
| 208 return static_cast<int>(pos - subject.start()); | 208 return static_cast<int>(pos - subject.start()); |
| 209 } else { | 209 } else { |
| (...skipping 13 matching lines...) Expand all Loading... |
| 223 | 223 |
| 224 //--------------------------------------------------------------------- | 224 //--------------------------------------------------------------------- |
| 225 // Linear Search Strategy | 225 // Linear Search Strategy |
| 226 //--------------------------------------------------------------------- | 226 //--------------------------------------------------------------------- |
| 227 | 227 |
| 228 | 228 |
| 229 template <typename PatternChar, typename SubjectChar> | 229 template <typename PatternChar, typename SubjectChar> |
| 230 inline bool CharCompare(const PatternChar* pattern, | 230 inline bool CharCompare(const PatternChar* pattern, |
| 231 const SubjectChar* subject, | 231 const SubjectChar* subject, |
| 232 int length) { | 232 int length) { |
| 233 ASSERT(length > 0); | 233 DCHECK(length > 0); |
| 234 int pos = 0; | 234 int pos = 0; |
| 235 do { | 235 do { |
| 236 if (pattern[pos] != subject[pos]) { | 236 if (pattern[pos] != subject[pos]) { |
| 237 return false; | 237 return false; |
| 238 } | 238 } |
| 239 pos++; | 239 pos++; |
| 240 } while (pos < length); | 240 } while (pos < length); |
| 241 return true; | 241 return true; |
| 242 } | 242 } |
| 243 | 243 |
| 244 | 244 |
| 245 // Simple linear search for short patterns. Never bails out. | 245 // Simple linear search for short patterns. Never bails out. |
| 246 template <typename PatternChar, typename SubjectChar> | 246 template <typename PatternChar, typename SubjectChar> |
| 247 int StringSearch<PatternChar, SubjectChar>::LinearSearch( | 247 int StringSearch<PatternChar, SubjectChar>::LinearSearch( |
| 248 StringSearch<PatternChar, SubjectChar>* search, | 248 StringSearch<PatternChar, SubjectChar>* search, |
| 249 Vector<const SubjectChar> subject, | 249 Vector<const SubjectChar> subject, |
| 250 int index) { | 250 int index) { |
| 251 Vector<const PatternChar> pattern = search->pattern_; | 251 Vector<const PatternChar> pattern = search->pattern_; |
| 252 ASSERT(pattern.length() > 1); | 252 DCHECK(pattern.length() > 1); |
| 253 int pattern_length = pattern.length(); | 253 int pattern_length = pattern.length(); |
| 254 PatternChar pattern_first_char = pattern[0]; | 254 PatternChar pattern_first_char = pattern[0]; |
| 255 int i = index; | 255 int i = index; |
| 256 int n = subject.length() - pattern_length; | 256 int n = subject.length() - pattern_length; |
| 257 while (i <= n) { | 257 while (i <= n) { |
| 258 if (sizeof(SubjectChar) == 1 && sizeof(PatternChar) == 1) { | 258 if (sizeof(SubjectChar) == 1 && sizeof(PatternChar) == 1) { |
| 259 const SubjectChar* pos = reinterpret_cast<const SubjectChar*>( | 259 const SubjectChar* pos = reinterpret_cast<const SubjectChar*>( |
| 260 memchr(subject.start() + i, | 260 memchr(subject.start() + i, |
| 261 pattern_first_char, | 261 pattern_first_char, |
| 262 n - i + 1)); | 262 n - i + 1)); |
| (...skipping 285 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 548 Vector<const SubjectChar> subject, | 548 Vector<const SubjectChar> subject, |
| 549 Vector<const PatternChar> pattern, | 549 Vector<const PatternChar> pattern, |
| 550 int start_index) { | 550 int start_index) { |
| 551 StringSearch<PatternChar, SubjectChar> search(isolate, pattern); | 551 StringSearch<PatternChar, SubjectChar> search(isolate, pattern); |
| 552 return search.Search(subject, start_index); | 552 return search.Search(subject, start_index); |
| 553 } | 553 } |
| 554 | 554 |
| 555 }} // namespace v8::internal | 555 }} // namespace v8::internal |
| 556 | 556 |
| 557 #endif // V8_STRING_SEARCH_H_ | 557 #endif // V8_STRING_SEARCH_H_ |
| OLD | NEW |