| OLD | NEW |
| 1 // Copyright 2011 the V8 project authors. All rights reserved. | 1 // Copyright 2011 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 296 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 307 int StringSearch<PatternChar, SubjectChar>::BoyerMooreSearch( | 307 int StringSearch<PatternChar, SubjectChar>::BoyerMooreSearch( |
| 308 StringSearch<PatternChar, SubjectChar>* search, | 308 StringSearch<PatternChar, SubjectChar>* search, |
| 309 Vector<const SubjectChar> subject, | 309 Vector<const SubjectChar> subject, |
| 310 int start_index) { | 310 int start_index) { |
| 311 Vector<const PatternChar> pattern = search->pattern_; | 311 Vector<const PatternChar> pattern = search->pattern_; |
| 312 int subject_length = subject.length(); | 312 int subject_length = subject.length(); |
| 313 int pattern_length = pattern.length(); | 313 int pattern_length = pattern.length(); |
| 314 // Only preprocess at most kBMMaxShift last characters of pattern. | 314 // Only preprocess at most kBMMaxShift last characters of pattern. |
| 315 int start = search->start_; | 315 int start = search->start_; |
| 316 | 316 |
| 317 int* bad_char_occurence = search->bad_char_table(); | 317 int* bad_char_occurrence = search->bad_char_table(); |
| 318 int* good_suffix_shift = search->good_suffix_shift_table(); | 318 int* good_suffix_shift = search->good_suffix_shift_table(); |
| 319 | 319 |
| 320 PatternChar last_char = pattern[pattern_length - 1]; | 320 PatternChar last_char = pattern[pattern_length - 1]; |
| 321 int index = start_index; | 321 int index = start_index; |
| 322 // Continue search from i. | 322 // Continue search from i. |
| 323 while (index <= subject_length - pattern_length) { | 323 while (index <= subject_length - pattern_length) { |
| 324 int j = pattern_length - 1; | 324 int j = pattern_length - 1; |
| 325 int c; | 325 int c; |
| 326 while (last_char != (c = subject[index + j])) { | 326 while (last_char != (c = subject[index + j])) { |
| 327 int shift = | 327 int shift = |
| 328 j - CharOccurrence(bad_char_occurence, c); | 328 j - CharOccurrence(bad_char_occurrence, c); |
| 329 index += shift; | 329 index += shift; |
| 330 if (index > subject_length - pattern_length) { | 330 if (index > subject_length - pattern_length) { |
| 331 return -1; | 331 return -1; |
| 332 } | 332 } |
| 333 } | 333 } |
| 334 while (j >= 0 && pattern[j] == (c = subject[index + j])) j--; | 334 while (j >= 0 && pattern[j] == (c = subject[index + j])) j--; |
| 335 if (j < 0) { | 335 if (j < 0) { |
| 336 return index; | 336 return index; |
| 337 } else if (j < start) { | 337 } else if (j < start) { |
| 338 // we have matched more than our tables allow us to be smart about. | 338 // we have matched more than our tables allow us to be smart about. |
| 339 // Fall back on BMH shift. | 339 // Fall back on BMH shift. |
| 340 index += pattern_length - 1 | 340 index += pattern_length - 1 |
| 341 - CharOccurrence(bad_char_occurence, | 341 - CharOccurrence(bad_char_occurrence, |
| 342 static_cast<SubjectChar>(last_char)); | 342 static_cast<SubjectChar>(last_char)); |
| 343 } else { | 343 } else { |
| 344 int gs_shift = good_suffix_shift[j + 1]; | 344 int gs_shift = good_suffix_shift[j + 1]; |
| 345 int bc_occ = | 345 int bc_occ = |
| 346 CharOccurrence(bad_char_occurence, c); | 346 CharOccurrence(bad_char_occurrence, c); |
| 347 int shift = j - bc_occ; | 347 int shift = j - bc_occ; |
| 348 if (gs_shift > shift) { | 348 if (gs_shift > shift) { |
| 349 shift = gs_shift; | 349 shift = gs_shift; |
| 350 } | 350 } |
| 351 index += shift; | 351 index += shift; |
| 352 } | 352 } |
| 353 } | 353 } |
| 354 | 354 |
| 355 return -1; | 355 return -1; |
| 356 } | 356 } |
| (...skipping 214 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 571 Vector<const SubjectChar> subject, | 571 Vector<const SubjectChar> subject, |
| 572 Vector<const PatternChar> pattern, | 572 Vector<const PatternChar> pattern, |
| 573 int start_index) { | 573 int start_index) { |
| 574 StringSearch<PatternChar, SubjectChar> search(isolate, pattern); | 574 StringSearch<PatternChar, SubjectChar> search(isolate, pattern); |
| 575 return search.Search(subject, start_index); | 575 return search.Search(subject, start_index); |
| 576 } | 576 } |
| 577 | 577 |
| 578 }} // namespace v8::internal | 578 }} // namespace v8::internal |
| 579 | 579 |
| 580 #endif // V8_STRING_SEARCH_H_ | 580 #endif // V8_STRING_SEARCH_H_ |
| OLD | NEW |