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 |