diff options
| author | Dennis Sweeney <36520290+sweeneyde@users.noreply.github.com> | 2022-09-13 18:25:10 (GMT) |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2022-09-13 18:25:10 (GMT) |
| commit | 69d9a080993902b289c1b2c089cc0882b908df4c (patch) | |
| tree | e31ab184af8958d0e38089d79208c98f6828ce1d /Objects | |
| parent | 4995f5f9a07921c5b90066a22285a538551b36d8 (diff) | |
| download | cpython-69d9a080993902b289c1b2c089cc0882b908df4c.zip cpython-69d9a080993902b289c1b2c089cc0882b908df4c.tar.gz cpython-69d9a080993902b289c1b2c089cc0882b908df4c.tar.bz2 | |
gh-94808: improve comments and coverage of fastsearch.h (GH-96760)
Diffstat (limited to 'Objects')
| -rw-r--r-- | Objects/stringlib/fastsearch.h | 7 | ||||
| -rw-r--r-- | Objects/stringlib/stringlib_find_two_way_notes.txt | 4 |
2 files changed, 6 insertions, 5 deletions
diff --git a/Objects/stringlib/fastsearch.h b/Objects/stringlib/fastsearch.h index 2949d00..257b7bd 100644 --- a/Objects/stringlib/fastsearch.h +++ b/Objects/stringlib/fastsearch.h @@ -18,7 +18,8 @@ algorithm, which has worst-case O(n) runtime and best-case O(n/k). Also compute a table of shifts to achieve O(n/k) in more cases, and often (data dependent) deduce larger shifts than pure C&P can - deduce. */ + deduce. See stringlib_find_two_way_notes.txt in this folder for a + detailed explanation. */ #define FAST_COUNT 0 #define FAST_SEARCH 1 @@ -398,7 +399,7 @@ STRINGLIB(_two_way)(const STRINGLIB_CHAR *haystack, Py_ssize_t len_haystack, if (window_last >= haystack_end) { return -1; } - LOG("Horspool skip"); + LOG("Horspool skip\n"); } no_shift: window = window_last - len_needle + 1; @@ -457,7 +458,7 @@ STRINGLIB(_two_way)(const STRINGLIB_CHAR *haystack, Py_ssize_t len_haystack, if (window_last >= haystack_end) { return -1; } - LOG("Horspool skip"); + LOG("Horspool skip\n"); } window = window_last - len_needle + 1; assert((window[len_needle - 1] & TABLE_MASK) == diff --git a/Objects/stringlib/stringlib_find_two_way_notes.txt b/Objects/stringlib/stringlib_find_two_way_notes.txt index afe4543..f97615b 100644 --- a/Objects/stringlib/stringlib_find_two_way_notes.txt +++ b/Objects/stringlib/stringlib_find_two_way_notes.txt @@ -239,7 +239,7 @@ We cut as AA + bAAbAAbA, and then the algorithm runs as follows: ~~ AA != bA at the cut bbbAbbAAbAAbAAbbbAAbAAbAAbAA AAbAAbAAbA - ^^^^X 7-3=4 match, and the 5th misses. + ^^^^X 7-3=4 match, and the 5th misses. bbbAbbAAbAAbAAbbbAAbAAbAAbAA AAbAAbAAbA ~ A != b at the cut @@ -395,7 +395,7 @@ of their proof goes something like this (this is far from complete): needle == (a + w) + (w + b), meaning there's a bad equality w == w, it's impossible for w + b to be bigger than both b and w + w + b, so this can't happen. We thus have all of - the ineuqalities with no question marks. + the inequalities with no question marks. * By maximality, the right part is not a substring of the left part. Thus, we have all of the inequalities involving no left-side question marks. |