| 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 35 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 46 // of the string, but it is a safe approximation. | 46 // of the string, but it is a safe approximation. |
| 47 static const int kBMMaxShift = Isolate::kBMMaxShift; | 47 static const int kBMMaxShift = Isolate::kBMMaxShift; |
| 48 | 48 |
| 49 // Reduce alphabet to this size. | 49 // Reduce alphabet to this size. |
| 50 // One of the tables used by Boyer-Moore and Boyer-Moore-Horspool has size | 50 // One of the tables used by Boyer-Moore and Boyer-Moore-Horspool has size |
| 51 // proportional to the input alphabet. We reduce the alphabet size by | 51 // proportional to the input alphabet. We reduce the alphabet size by |
| 52 // equating input characters modulo a smaller alphabet size. This gives | 52 // equating input characters modulo a smaller alphabet size. This gives |
| 53 // a potentially less efficient searching, but is a safe approximation. | 53 // a potentially less efficient searching, but is a safe approximation. |
| 54 // For needles using only characters in the same Unicode 256-code point page, | 54 // For needles using only characters in the same Unicode 256-code point page, |
| 55 // there is no search speed degradation. | 55 // there is no search speed degradation. |
| 56 #ifndef ENABLE_LATIN_1 | |
| 57 static const int kAsciiAlphabetSize = 128; | |
| 58 #else | |
| 59 static const int kAsciiAlphabetSize = 256; | 56 static const int kAsciiAlphabetSize = 256; |
| 60 #endif | |
| 61 static const int kUC16AlphabetSize = Isolate::kUC16AlphabetSize; | 57 static const int kUC16AlphabetSize = Isolate::kUC16AlphabetSize; |
| 62 | 58 |
| 63 // Bad-char shift table stored in the state. It's length is the alphabet size. | 59 // Bad-char shift table stored in the state. It's length is the alphabet size. |
| 64 // For patterns below this length, the skip length of Boyer-Moore is too short | 60 // For patterns below this length, the skip length of Boyer-Moore is too short |
| 65 // to compensate for the algorithmic overhead compared to simple brute force. | 61 // to compensate for the algorithmic overhead compared to simple brute force. |
| 66 static const int kBMMinPatternLength = 7; | 62 static const int kBMMinPatternLength = 7; |
| 67 | 63 |
| 68 static inline bool IsOneByteString(Vector<const uint8_t> string) { | 64 static inline bool IsOneByteString(Vector<const uint8_t> string) { |
| 69 return true; | 65 return true; |
| 70 } | 66 } |
| (...skipping 77 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 148 | 144 |
| 149 static int BoyerMooreSearch(StringSearch<PatternChar, SubjectChar>* search, | 145 static int BoyerMooreSearch(StringSearch<PatternChar, SubjectChar>* search, |
| 150 Vector<const SubjectChar> subject, | 146 Vector<const SubjectChar> subject, |
| 151 int start_index); | 147 int start_index); |
| 152 | 148 |
| 153 void PopulateBoyerMooreHorspoolTable(); | 149 void PopulateBoyerMooreHorspoolTable(); |
| 154 | 150 |
| 155 void PopulateBoyerMooreTable(); | 151 void PopulateBoyerMooreTable(); |
| 156 | 152 |
| 157 static inline bool exceedsOneByte(uint8_t c) { | 153 static inline bool exceedsOneByte(uint8_t c) { |
| 158 #ifdef ENABLE_LATIN_1 | |
| 159 return false; | 154 return false; |
| 160 #else | |
| 161 return c > String::kMaxOneByteCharCodeU; | |
| 162 #endif | |
| 163 } | 155 } |
| 164 | 156 |
| 165 static inline bool exceedsOneByte(uint16_t c) { | 157 static inline bool exceedsOneByte(uint16_t c) { |
| 166 return c > String::kMaxOneByteCharCodeU; | 158 return c > String::kMaxOneByteCharCodeU; |
| 167 } | 159 } |
| 168 | 160 |
| 169 static inline int CharOccurrence(int* bad_char_occurrence, | 161 static inline int CharOccurrence(int* bad_char_occurrence, |
| 170 SubjectChar char_code) { | 162 SubjectChar char_code) { |
| 171 if (sizeof(SubjectChar) == 1) { | 163 if (sizeof(SubjectChar) == 1) { |
| 172 return bad_char_occurrence[static_cast<int>(char_code)]; | 164 return bad_char_occurrence[static_cast<int>(char_code)]; |
| (...skipping 406 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 579 Vector<const SubjectChar> subject, | 571 Vector<const SubjectChar> subject, |
| 580 Vector<const PatternChar> pattern, | 572 Vector<const PatternChar> pattern, |
| 581 int start_index) { | 573 int start_index) { |
| 582 StringSearch<PatternChar, SubjectChar> search(isolate, pattern); | 574 StringSearch<PatternChar, SubjectChar> search(isolate, pattern); |
| 583 return search.Search(subject, start_index); | 575 return search.Search(subject, start_index); |
| 584 } | 576 } |
| 585 | 577 |
| 586 }} // namespace v8::internal | 578 }} // namespace v8::internal |
| 587 | 579 |
| 588 #endif // V8_STRING_SEARCH_H_ | 580 #endif // V8_STRING_SEARCH_H_ |
| OLD | NEW |