diff options
author | dcposch@dcpos.ch <dcposch@dcpos.ch> | 2016-01-29 00:12:09 +0300 |
---|---|---|
committer | James M Snell <jasnell@gmail.com> | 2016-04-25 18:24:28 +0300 |
commit | 6c1e5ad3aba4d9ca5883855e1d3838ba8f04dfbb (patch) | |
tree | eb9352cb98e5f70fbc4b6f5041abc385e6ad58e1 /src/string_search.h | |
parent | d5922bd7a980e1c79016de8b6d3bf07282b1dbb4 (diff) |
buffer: add Buffer.prototype.lastIndexOf()
* Remove unnecessary templating from SearchString
SearchString used to have separate PatternChar and SubjectChar template type
arguments, apparently to support things like searching for an 8-bit string
inside a 16-bit string or vice versa. However, SearchString is only used from
node_buffer.cc, where PatternChar and SubjectChar are always the same. Since
this is extra complexity that's unused and untested (simplifying to a single
Char template argument still compiles and didn't break any unit tests), I
removed it.
* Use Boyer-Hoore[-Horspool] for both indexOf and lastIndexOf
Add test cases for lastIndexOf. Test the fallback from BMH to
Boyer-Moore, which looks like it was totally untested before.
* Extra bounds checks in node_buffer.cc
* Extra asserts in string_search.h
* Buffer.lastIndexOf: clean up, enforce consistency w/ String.lastIndexOf
* Polyfill memrchr(3) for non-GNU systems
PR-URL: https://github.com/nodejs/node/pull/4846
Reviewed-By: James M Snell <jasnell@gmail.com>
Reviewed-By: Trevor Norris <trev.norris@gmail.com>
Diffstat (limited to 'src/string_search.h')
-rw-r--r-- | src/string_search.h | 366 |
1 files changed, 185 insertions, 181 deletions
diff --git a/src/string_search.h b/src/string_search.h index 2a2790b2cc6..bf246702d7e 100644 --- a/src/string_search.h +++ b/src/string_search.h @@ -21,60 +21,35 @@ T Max(T a, T b) { static const uint32_t kMaxOneByteCharCodeU = 0xff; - -static inline size_t NonOneByteStart(const uint16_t* chars, size_t length) { - const uint16_t* limit = chars + length; - const uint16_t* start = chars; - while (chars < limit) { - if (*chars > kMaxOneByteCharCodeU) - return static_cast<size_t>(chars - start); - ++chars; - } - return static_cast<size_t>(chars - start); -} - - -static inline bool IsOneByte(const uint16_t* chars, size_t length) { - return NonOneByteStart(chars, length) >= length; -} - - template <typename T> class Vector { public: - Vector(T* data, size_t length) : start_(data), length_(length) { + Vector(T* data, size_t length, bool isForward) + : start_(data), length_(length), is_forward_(isForward) { ASSERT(length > 0 && data != nullptr); } - // Returns the length of the vector. + // Returns the start of the memory range. + // For vector v this is NOT necessarily &v[0], see forward(). + const T* start() const { return start_; } + + // Returns the length of the vector, in characters. size_t length() const { return length_; } - T* start() const { return start_; } + // Returns true if the Vector is front-to-back, false if back-to-front. + // In the latter case, v[0] corresponds to the *end* of the memory range. + size_t forward() const { return is_forward_; } // Access individual vector elements - checks bounds in debug mode. T& operator[](size_t index) const { ASSERT(0 <= index && index < length_); - return start_[index]; - } - - const T& at(size_t index) const { return operator[](index); } - - bool operator==(const Vector<T>& other) const { - if (length_ != other.length_) - return false; - if (start_ == other.start_) - return true; - for (size_t i = 0; i < length_; ++i) { - if (start_[i] != other.start_[i]) { - return false; - } - } - return true; + return start_[is_forward_ ? index : (length_ - index - 1)]; } private: T* start_; size_t length_; + bool is_forward_; }; @@ -114,31 +89,17 @@ class StringSearchBase { // Table used temporarily while building the BoyerMoore good suffix // shift table. static int kSuffixTable[kBMMaxShift + 1]; - - static inline bool IsOneByteString(Vector<const uint8_t> string) { - return true; - } - - static inline bool IsOneByteString(Vector<const uint16_t> string) { - return IsOneByte(string.start(), string.length()); - } }; -template <typename PatternChar, typename SubjectChar> +template <typename Char> class StringSearch : private StringSearchBase { public: - explicit StringSearch(Vector<const PatternChar> pattern) + explicit StringSearch(Vector<const Char> pattern) : pattern_(pattern), start_(0) { if (pattern.length() >= kBMMaxShift) { start_ = pattern.length() - kBMMaxShift; } - if (sizeof(PatternChar) > sizeof(SubjectChar)) { - if (!IsOneByteString(pattern_)) { - strategy_ = &FailSearch; - return; - } - } size_t pattern_length = pattern_.length(); CHECK_GT(pattern_length, 0); if (pattern_length < kBMMinPatternLength) { @@ -152,12 +113,12 @@ class StringSearch : private StringSearchBase { strategy_ = &InitialSearch; } - size_t Search(Vector<const SubjectChar> subject, size_t index) { + size_t Search(Vector<const Char> subject, size_t index) { return strategy_(this, subject, index); } static inline int AlphabetSize() { - if (sizeof(PatternChar) == 1) { + if (sizeof(Char) == 1) { // Latin1 needle. return kLatin1AlphabetSize; } else { @@ -165,42 +126,42 @@ class StringSearch : private StringSearchBase { return kUC16AlphabetSize; } - static_assert(sizeof(PatternChar) == sizeof(uint8_t) || - sizeof(PatternChar) == sizeof(uint16_t), - "sizeof(PatternChar) == sizeof(uint16_t) || sizeof(uint8_t)"); + static_assert(sizeof(Char) == sizeof(uint8_t) || + sizeof(Char) == sizeof(uint16_t), + "sizeof(Char) == sizeof(uint16_t) || sizeof(uint8_t)"); } private: typedef size_t (*SearchFunction)( // NOLINT - it's not a cast! - StringSearch<PatternChar, SubjectChar>*, - Vector<const SubjectChar>, + StringSearch<Char>*, + Vector<const Char>, size_t); - static size_t FailSearch(StringSearch<PatternChar, SubjectChar>*, - Vector<const SubjectChar> subject, + static size_t FailSearch(StringSearch<Char>*, + Vector<const Char> subject, size_t) { return subject.length(); } - static size_t SingleCharSearch(StringSearch<PatternChar, SubjectChar>* search, - Vector<const SubjectChar> subject, + static size_t SingleCharSearch(StringSearch<Char>* search, + Vector<const Char> subject, size_t start_index); - static size_t LinearSearch(StringSearch<PatternChar, SubjectChar>* search, - Vector<const SubjectChar> subject, + static size_t LinearSearch(StringSearch<Char>* search, + Vector<const Char> subject, size_t start_index); - static size_t InitialSearch(StringSearch<PatternChar, SubjectChar>* search, - Vector<const SubjectChar> subject, + static size_t InitialSearch(StringSearch<Char>* search, + Vector<const Char> subject, size_t start_index); static size_t BoyerMooreHorspoolSearch( - StringSearch<PatternChar, SubjectChar>* search, - Vector<const SubjectChar> subject, + StringSearch<Char>* search, + Vector<const Char> subject, size_t start_index); - static size_t BoyerMooreSearch(StringSearch<PatternChar, SubjectChar>* search, - Vector<const SubjectChar> subject, + static size_t BoyerMooreSearch(StringSearch<Char>* search, + Vector<const Char> subject, size_t start_index); void PopulateBoyerMooreHorspoolTable(); @@ -214,16 +175,10 @@ class StringSearch : private StringSearchBase { } static inline int CharOccurrence(int* bad_char_occurrence, - SubjectChar char_code) { - if (sizeof(SubjectChar) == 1) { + Char char_code) { + if (sizeof(Char) == 1) { return bad_char_occurrence[static_cast<int>(char_code)]; } - if (sizeof(PatternChar) == 1) { - if (exceedsOneByte(char_code)) { - return -1; - } - return bad_char_occurrence[static_cast<unsigned int>(char_code)]; - } // Both pattern and subject are UC16. Reduce character to equivalence class. int equiv_class = char_code % kUC16AlphabetSize; return bad_char_occurrence[equiv_class]; @@ -250,7 +205,7 @@ class StringSearch : private StringSearchBase { } // The pattern to search for. - Vector<const PatternChar> pattern_; + Vector<const Char> pattern_; // Pointer to implementation of the search. SearchFunction strategy_; // Cache value of Max(0, pattern_length() - kBMMaxShift) @@ -274,111 +229,138 @@ inline uint8_t GetHighestValueByte(uint16_t character) { inline uint8_t GetHighestValueByte(uint8_t character) { return character; } -template <typename PatternChar, typename SubjectChar> -inline size_t FindFirstCharacter(Vector<const PatternChar> pattern, - Vector<const SubjectChar> subject, size_t index) { - const PatternChar pattern_first_char = pattern[0]; +// Searches for a byte value in a memory buffer, back to front. +// Uses memrchr(3) on systems which support it, for speed. +// Falls back to a vanilla for loop on non-GNU systems such as Windows. +inline const void* MemrchrFill(const void* haystack, uint8_t needle, + size_t haystack_len) { +#ifdef _GNU_SOURCE + return memrchr(haystack, needle, haystack_len); +#else + const uint8_t* haystack8 = static_cast<const uint8_t*>(haystack); + for (size_t i = haystack_len - 1; i != static_cast<size_t>(-1); i--) { + if (haystack8[i] == needle) { + return haystack8 + i; + } + } + return nullptr; +#endif +} + + +// Finds the first occurence of *two-byte* character pattern[0] in the string +// `subject`. Does not check that the whole pattern matches. +template <typename Char> +inline size_t FindFirstCharacter(Vector<const Char> pattern, + Vector<const Char> subject, size_t index) { + const Char pattern_first_char = pattern[0]; const size_t max_n = (subject.length() - pattern.length() + 1); + // For speed, search for the more `rare` of the two bytes in pattern[0] + // using memchr / memrchr (which are much faster than a simple for loop). const uint8_t search_byte = GetHighestValueByte(pattern_first_char); - const SubjectChar search_char = static_cast<SubjectChar>(pattern_first_char); size_t pos = index; do { - const SubjectChar* char_pos = reinterpret_cast<const SubjectChar*>( - memchr(subject.start() + pos, search_byte, - (max_n - pos) * sizeof(SubjectChar))); + size_t bytes_to_search; + const void* void_pos; + if (subject.forward()) { + // Assert that bytes_to_search won't overflow + CHECK_LE(pos, max_n); + CHECK_LE(max_n - pos, SIZE_MAX / sizeof(Char)); + bytes_to_search = (max_n - pos) * sizeof(Char); + void_pos = memchr(subject.start() + pos, search_byte, bytes_to_search); + } else { + CHECK_LE(pos, subject.length()); + CHECK_LE(subject.length() - pos, SIZE_MAX / sizeof(Char)); + bytes_to_search = (subject.length() - pos) * sizeof(Char); + void_pos = MemrchrFill(subject.start(), search_byte, bytes_to_search); + } + const Char* char_pos = static_cast<const Char*>(void_pos); if (char_pos == nullptr) return subject.length(); - char_pos = AlignDown(char_pos, sizeof(SubjectChar)); - pos = static_cast<size_t>(char_pos - subject.start()); - if (subject[pos] == search_char) + + // Then, for each match, verify that the full two bytes match pattern[0]. + char_pos = AlignDown(char_pos, sizeof(Char)); + size_t raw_pos = static_cast<size_t>(char_pos - subject.start()); + pos = subject.forward() ? raw_pos : (subject.length() - raw_pos - 1); + if (subject[pos] == pattern_first_char) { + // Match found, hooray. return pos; + } + // Search byte matched, but the other byte of pattern[0] didn't. Keep going. } while (++pos < max_n); return subject.length(); } +// Finds the first occurance of the byte pattern[0] in string `subject`. +// Does not verify that the whole pattern matches. template <> inline size_t FindFirstCharacter(Vector<const uint8_t> pattern, Vector<const uint8_t> subject, size_t index) { const uint8_t pattern_first_char = pattern[0]; + const size_t subj_len = subject.length(); const size_t max_n = (subject.length() - pattern.length() + 1); - const uint8_t* char_pos = reinterpret_cast<const uint8_t*>( - memchr(subject.start() + index, pattern_first_char, max_n - index)); - if (char_pos == nullptr) - return subject.length(); - return static_cast<size_t>(char_pos - subject.start()); + const void* pos; + if (subject.forward()) { + pos = memchr(subject.start() + index, pattern_first_char, max_n - index); + } else { + pos = MemrchrFill(subject.start(), pattern_first_char, subj_len - index); + } + const uint8_t* char_pos = static_cast<const uint8_t*>(pos); + if (char_pos == nullptr) { + return subj_len; + } + + size_t raw_pos = static_cast<size_t>(char_pos - subject.start()); + return subject.forward() ? raw_pos : (subj_len - raw_pos - 1); } //--------------------------------------------------------------------- // Single Character Pattern Search Strategy //--------------------------------------------------------------------- -template <typename PatternChar, typename SubjectChar> -size_t StringSearch<PatternChar, SubjectChar>::SingleCharSearch( - StringSearch<PatternChar, SubjectChar>* search, - Vector<const SubjectChar> subject, +template <typename Char> +size_t StringSearch<Char>::SingleCharSearch( + StringSearch<Char>* search, + Vector<const Char> subject, size_t index) { CHECK_EQ(1, search->pattern_.length()); - PatternChar pattern_first_char = search->pattern_[0]; - - if (sizeof(SubjectChar) == 1 && sizeof(PatternChar) == 1) { - return FindFirstCharacter(search->pattern_, subject, index); - } else { - if (sizeof(PatternChar) > sizeof(SubjectChar)) { - if (exceedsOneByte(pattern_first_char)) { - return -1; - } - } - return FindFirstCharacter(search->pattern_, subject, index); - } + return FindFirstCharacter(search->pattern_, subject, index); } //--------------------------------------------------------------------- // Linear Search Strategy //--------------------------------------------------------------------- -template <typename PatternChar, typename SubjectChar> -inline bool CharCompare(const PatternChar* pattern, - const SubjectChar* subject, - size_t length) { - ASSERT_GT(length, 0); - size_t pos = 0; - do { - if (pattern[pos] != subject[pos]) { - return false; - } - pos++; - } while (pos < length); - return true; -} - // Simple linear search for short patterns. Never bails out. -template <typename PatternChar, typename SubjectChar> -size_t StringSearch<PatternChar, SubjectChar>::LinearSearch( - StringSearch<PatternChar, SubjectChar>* search, - Vector<const SubjectChar> subject, +template <typename Char> +size_t StringSearch<Char>::LinearSearch( + StringSearch<Char>* search, + Vector<const Char> subject, size_t index) { - Vector<const PatternChar> pattern = search->pattern_; + Vector<const Char> pattern = search->pattern_; CHECK_GT(pattern.length(), 1); const size_t pattern_length = pattern.length(); - size_t i = index; const size_t n = subject.length() - pattern_length; - while (i <= n) { + for (size_t i = index; i <= n; i++) { i = FindFirstCharacter(pattern, subject, i); if (i == subject.length()) return subject.length(); ASSERT_LE(i, n); - i++; - // Loop extracted to separate function to allow using return to do - // a deeper break. - if (CharCompare(pattern.start() + 1, subject.start() + i, - pattern_length - 1)) { - return i - 1; + bool matches = true; + for (size_t j = 1; j < pattern_length; j++) { + if (pattern[j] != subject[i + j]) { + matches = false; + break; + } + } + if (matches) { + return i; } } return subject.length(); @@ -388,12 +370,12 @@ size_t StringSearch<PatternChar, SubjectChar>::LinearSearch( // Boyer-Moore string search //--------------------------------------------------------------------- -template <typename PatternChar, typename SubjectChar> -size_t StringSearch<PatternChar, SubjectChar>::BoyerMooreSearch( - StringSearch<PatternChar, SubjectChar>* search, - Vector<const SubjectChar> subject, +template <typename Char> +size_t StringSearch<Char>::BoyerMooreSearch( + StringSearch<Char>* search, + Vector<const Char> subject, size_t start_index) { - Vector<const PatternChar> pattern = search->pattern_; + Vector<const Char> pattern = search->pattern_; const size_t subject_length = subject.length(); const size_t pattern_length = pattern.length(); // Only preprocess at most kBMMaxShift last characters of pattern. @@ -402,7 +384,7 @@ size_t StringSearch<PatternChar, SubjectChar>::BoyerMooreSearch( int* bad_char_occurence = search->bad_char_table(); int* good_suffix_shift = search->good_suffix_shift_table(); - PatternChar last_char = pattern[pattern_length - 1]; + Char last_char = pattern[pattern_length - 1]; size_t index = start_index; // Continue search from i. while (index <= subject_length - pattern_length) { @@ -426,7 +408,7 @@ size_t StringSearch<PatternChar, SubjectChar>::BoyerMooreSearch( // Fall back on BMH shift. index += pattern_length - 1 - CharOccurrence(bad_char_occurence, - static_cast<SubjectChar>(last_char)); + static_cast<Char>(last_char)); } else { int gs_shift = good_suffix_shift[j + 1]; int bc_occ = CharOccurrence(bad_char_occurence, c); @@ -441,10 +423,10 @@ size_t StringSearch<PatternChar, SubjectChar>::BoyerMooreSearch( return subject.length(); } -template <typename PatternChar, typename SubjectChar> -void StringSearch<PatternChar, SubjectChar>::PopulateBoyerMooreTable() { +template <typename Char> +void StringSearch<Char>::PopulateBoyerMooreTable() { const size_t pattern_length = pattern_.length(); - const PatternChar* pattern = pattern_.start(); + Vector<const Char> pattern = pattern_; // Only look at the last kBMMaxShift characters of pattern (from start_ // to pattern_length). const size_t start = start_; @@ -467,12 +449,12 @@ void StringSearch<PatternChar, SubjectChar>::PopulateBoyerMooreTable() { } // Find suffixes. - PatternChar last_char = pattern[pattern_length - 1]; + Char last_char = pattern_[pattern_length - 1]; size_t suffix = pattern_length + 1; { size_t i = pattern_length; while (i > start) { - PatternChar c = pattern[i - 1]; + Char c = pattern[i - 1]; while (suffix <= pattern_length && c != pattern[suffix - 1]) { if (static_cast<size_t>(shift_table[suffix]) == length) { shift_table[suffix] = suffix - i; @@ -511,22 +493,22 @@ void StringSearch<PatternChar, SubjectChar>::PopulateBoyerMooreTable() { // Boyer-Moore-Horspool string search. //--------------------------------------------------------------------- -template <typename PatternChar, typename SubjectChar> -size_t StringSearch<PatternChar, SubjectChar>::BoyerMooreHorspoolSearch( - StringSearch<PatternChar, SubjectChar>* search, - Vector<const SubjectChar> subject, +template <typename Char> +size_t StringSearch<Char>::BoyerMooreHorspoolSearch( + StringSearch<Char>* search, + Vector<const Char> subject, size_t start_index) { - Vector<const PatternChar> pattern = search->pattern_; + Vector<const Char> pattern = search->pattern_; const size_t subject_length = subject.length(); const size_t pattern_length = pattern.length(); int* char_occurrences = search->bad_char_table(); int64_t badness = -pattern_length; // How bad we are doing without a good-suffix table. - PatternChar last_char = pattern[pattern_length - 1]; + Char last_char = pattern[pattern_length - 1]; int last_char_shift = pattern_length - 1 - - CharOccurrence(char_occurrences, static_cast<SubjectChar>(last_char)); + CharOccurrence(char_occurrences, static_cast<Char>(last_char)); // Perform search size_t index = start_index; // No matches found prior to this index. @@ -564,8 +546,8 @@ size_t StringSearch<PatternChar, SubjectChar>::BoyerMooreHorspoolSearch( return subject.length(); } -template <typename PatternChar, typename SubjectChar> -void StringSearch<PatternChar, SubjectChar>::PopulateBoyerMooreHorspoolTable() { +template <typename Char> +void StringSearch<Char>::PopulateBoyerMooreHorspoolTable() { const size_t pattern_length = pattern_.length(); int* bad_char_occurrence = bad_char_table(); @@ -585,8 +567,8 @@ void StringSearch<PatternChar, SubjectChar>::PopulateBoyerMooreHorspoolTable() { } } for (size_t i = start; i < pattern_length - 1; i++) { - PatternChar c = pattern_[i]; - int bucket = (sizeof(PatternChar) == 1) ? c : c % AlphabetSize(); + Char c = pattern_[i]; + int bucket = (sizeof(Char) == 1) ? c : c % AlphabetSize(); bad_char_occurrence[bucket] = i; } } @@ -597,12 +579,12 @@ void StringSearch<PatternChar, SubjectChar>::PopulateBoyerMooreHorspoolTable() { // Simple linear search for short patterns, which bails out if the string // isn't found very early in the subject. Upgrades to BoyerMooreHorspool. -template <typename PatternChar, typename SubjectChar> -size_t StringSearch<PatternChar, SubjectChar>::InitialSearch( - StringSearch<PatternChar, SubjectChar>* search, - Vector<const SubjectChar> subject, +template <typename Char> +size_t StringSearch<Char>::InitialSearch( + StringSearch<Char>* search, + Vector<const Char> subject, size_t index) { - Vector<const PatternChar> pattern = search->pattern_; + Vector<const Char> pattern = search->pattern_; const size_t pattern_length = pattern.length(); // Badness is a count of how much work we have done. When we have // done enough work we decide it's probably worth switching to a better @@ -642,11 +624,11 @@ size_t StringSearch<PatternChar, SubjectChar>::InitialSearch( // If searching multiple times for the same pattern, a search // object should be constructed once and the Search function then called // for each search. -template <typename SubjectChar, typename PatternChar> -size_t SearchString(Vector<const SubjectChar> subject, - Vector<const PatternChar> pattern, +template <typename Char> +size_t SearchString(Vector<const Char> subject, + Vector<const Char> pattern, size_t start_index) { - StringSearch<PatternChar, SubjectChar> search(pattern); + StringSearch<Char> search(pattern); return search.Search(subject, start_index); } } @@ -655,16 +637,38 @@ size_t SearchString(Vector<const SubjectChar> subject, namespace node { using node::stringsearch::Vector; -template <typename SubjectChar, typename PatternChar> -size_t SearchString(const SubjectChar* haystack, +template <typename Char> +size_t SearchString(const Char* haystack, size_t haystack_length, - const PatternChar* needle, + const Char* needle, size_t needle_length, - size_t start_index) { - return node::stringsearch::SearchString( - Vector<const SubjectChar>(haystack, haystack_length), - Vector<const PatternChar>(needle, needle_length), - start_index); + size_t start_index, + bool is_forward) { + // To do a reverse search (lastIndexOf instead of indexOf) without redundant + // code, create two vectors that are reversed views into the input strings. + // For example, v_needle[0] would return the *last* character of the needle. + // So we're searching for the first instance of rev(needle) in rev(haystack) + Vector<const Char> v_needle = Vector<const Char>( + needle, needle_length, is_forward); + Vector<const Char> v_haystack = Vector<const Char>( + haystack, haystack_length, is_forward); + ASSERT(haystack_length >= needle_length); + size_t diff = haystack_length - needle_length; + size_t relative_start_index; + if (is_forward) { + relative_start_index = start_index; + } else if (diff < start_index) { + relative_start_index = 0; + } else { + relative_start_index = diff - start_index; + } + size_t pos = node::stringsearch::SearchString( + v_haystack, v_needle, relative_start_index); + if (pos == haystack_length) { + // not found + return pos; + } + return is_forward ? pos : (haystack_length - needle_length - pos); } } // namespace node |