Commit 118fa97
deps: update nbytes to 0.1.2
PR-URL: #61270
Reviewed-By: Michaël Zasso <targos@protonmail.com>
Reviewed-By: Aviv Keller <me@aviv.sh>
Reviewed-By: Colin Ihrig <cjihrig@gmail.com>
Reviewed-By: Rafael Gonzaga <rafael.nunu@hotmail.com>1 parent 28fe6ea commit 118fa97
2 files changed
Lines changed: 32 additions & 23 deletions
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
@@ -4,6 +4,7 @@ | |||
| 4 | 4 | #include <cmath> | |
| 5 | 5 | #include <cstddef> | |
| 6 | 6 | #include <cstdint> | |
| 7 | + #include <cstdlib> | ||
| 7 | 8 | #include <cstring> | |
| 8 | 9 | #include <string> | |
| 9 | 10 | ||
@@ -548,7 +549,11 @@ size_t StringSearch<Char>::BoyerMooreSearch(Vector subject, | |||
| 548 | 549 | size_t start = start_; | |
| 549 | 550 | ||
| 550 | 551 | int *bad_char_occurrence = bad_char_shift_table_; | |
| 551 | - int *good_suffix_shift = good_suffix_shift_table_ - start_; | ||
| 552 | + | ||
| 553 | + auto good_suffix_get = [&](size_t idx) -> int { | ||
| 554 | + if (idx < start || idx - start > kBMMaxShift) return 0; | ||
| 555 | + return good_suffix_shift_table_[idx - start]; | ||
| 556 | + }; | ||
| 552 | 557 | ||
| 553 | 558 | Char last_char = pattern_[pattern_length - 1]; | |
| 554 | 559 | size_t index = start_index; | |
@@ -575,7 +580,7 @@ size_t StringSearch<Char>::BoyerMooreSearch(Vector subject, | |||
| 575 | 580 | index += | |
| 576 | 581 | pattern_length - 1 - CharOccurrence(bad_char_occurrence, last_char); | |
| 577 | 582 | } else { | |
| 578 | - int gs_shift = good_suffix_shift[j + 1]; | ||
| 583 | + int gs_shift = good_suffix_get(j + 1); | ||
| 579 | 584 | int bc_occ = CharOccurrence(bad_char_occurrence, c); | |
| 580 | 585 | int shift = j - bc_occ; | |
| 581 | 586 | if (gs_shift > shift) { | |
@@ -591,22 +596,25 @@ size_t StringSearch<Char>::BoyerMooreSearch(Vector subject, | |||
| 591 | 596 | template <typename Char> | |
| 592 | 597 | void StringSearch<Char>::PopulateBoyerMooreTable() { | |
| 593 | 598 | const size_t pattern_length = pattern_.length(); | |
| 594 | - // Only look at the last kBMMaxShift characters of pattern (from start_ | ||
| 595 | - // to pattern_length). | ||
| 596 | 599 | const size_t start = start_; | |
| 597 | 600 | const size_t length = pattern_length - start; | |
| 598 | 601 | ||
| 599 | - // Biased tables so that we can use pattern indices as table indices, | ||
| 600 | - // even if we only cover the part of the pattern from offset start. | ||
| 601 | - int *shift_table = good_suffix_shift_table_ - start_; | ||
| 602 | - int *suffix_table = suffix_table_ - start_; | ||
| 602 | + auto shift_get = [&](size_t idx) -> int & { | ||
| 603 | + if (idx < start) abort(); | ||
| 604 | + return good_suffix_shift_table_[idx - start]; | ||
| 605 | + }; | ||
| 606 | + | ||
| 607 | + auto suffix_get = [&](size_t idx) -> int & { | ||
| 608 | + if (idx < start) abort(); | ||
| 609 | + return suffix_table_[idx - start]; | ||
| 610 | + }; | ||
| 603 | 611 | ||
| 604 | 612 | // Initialize table. | |
| 605 | 613 | for (size_t i = start; i < pattern_length; i++) { | |
| 606 | - shift_table[i] = length; | ||
| 614 | + shift_get(i) = length; | ||
| 607 | 615 | } | |
| 608 | - shift_table[pattern_length] = 1; | ||
| 609 | - suffix_table[pattern_length] = pattern_length + 1; | ||
| 616 | + shift_get(pattern_length) = 1; | ||
| 617 | + suffix_get(pattern_length) = pattern_length + 1; | ||
| 610 | 618 | ||
| 611 | 619 | if (pattern_length <= start) { | |
| 612 | 620 | return; | |
@@ -620,34 +628,35 @@ void StringSearch<Char>::PopulateBoyerMooreTable() { | |||
| 620 | 628 | while (i > start) { | |
| 621 | 629 | Char c = pattern_[i - 1]; | |
| 622 | 630 | while (suffix <= pattern_length && c != pattern_[suffix - 1]) { | |
| 623 | - if (static_cast<size_t>(shift_table[suffix]) == length) { | ||
| 624 | - shift_table[suffix] = suffix - i; | ||
| 631 | + if (static_cast<size_t>(shift_get(suffix)) == length) { | ||
| 632 | + shift_get(suffix) = suffix - i; | ||
| 625 | 633 | } | |
| 626 | - suffix = suffix_table[suffix]; | ||
| 634 | + suffix = suffix_get(suffix); | ||
| 627 | 635 | } | |
| 628 | - suffix_table[--i] = --suffix; | ||
| 636 | + suffix_get(--i) = --suffix; | ||
| 629 | 637 | if (suffix == pattern_length) { | |
| 630 | 638 | // No suffix to extend, so we check against last_char only. | |
| 631 | 639 | while ((i > start) && (pattern_[i - 1] != last_char)) { | |
| 632 | - if (static_cast<size_t>(shift_table[pattern_length]) == length) { | ||
| 633 | - shift_table[pattern_length] = pattern_length - i; | ||
| 640 | + if (static_cast<size_t>(shift_get(pattern_length)) == length) { | ||
| 641 | + shift_get(pattern_length) = pattern_length - i; | ||
| 634 | 642 | } | |
| 635 | - suffix_table[--i] = pattern_length; | ||
| 643 | + suffix_get(--i) = pattern_length; | ||
| 636 | 644 | } | |
| 637 | 645 | if (i > start) { | |
| 638 | - suffix_table[--i] = --suffix; | ||
| 646 | + suffix_get(--i) = --suffix; | ||
| 639 | 647 | } | |
| 640 | 648 | } | |
| 641 | 649 | } | |
| 642 | 650 | } | |
| 651 | + | ||
| 643 | 652 | // Build shift table using suffixes. | |
| 644 | 653 | if (suffix < pattern_length) { | |
| 645 | 654 | for (size_t i = start; i <= pattern_length; i++) { | |
| 646 | - if (static_cast<size_t>(shift_table[i]) == length) { | ||
| 647 | - shift_table[i] = suffix - start; | ||
| 655 | + if (static_cast<size_t>(shift_get(i)) == length) { | ||
| 656 | + shift_get(i) = suffix - start; | ||
| 648 | 657 | } | |
| 649 | 658 | if (i == suffix) { | |
| 650 | - suffix = suffix_table[suffix]; | ||
| 659 | + suffix = suffix_get(suffix); | ||
| 651 | 660 | } | |
| 652 | 661 | } | |
| 653 | 662 | } | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
@@ -205,7 +205,7 @@ void ForceAscii(const char *src, char *dst, size_t len) { | |||
| 205 | 205 | ForceAsciiSlow(src, dst, unalign); | |
| 206 | 206 | src += unalign; | |
| 207 | 207 | dst += unalign; | |
| 208 | - len -= src_unalign; | ||
| 208 | + len -= unalign; | ||
| 209 | 209 | } else { | |
| 210 | 210 | ForceAsciiSlow(src, dst, len); | |
| 211 | 211 | return; | |
0 commit comments