diff options
Diffstat (limited to 'Objects/stringlib/fastsearch.h')
| -rw-r--r-- | Objects/stringlib/fastsearch.h | 148 |
1 files changed, 102 insertions, 46 deletions
diff --git a/Objects/stringlib/fastsearch.h b/Objects/stringlib/fastsearch.h index 23bccfb..e231c58 100644 --- a/Objects/stringlib/fastsearch.h +++ b/Objects/stringlib/fastsearch.h @@ -5,7 +5,7 @@ /* fast search/count implementation, based on a mix between boyer- moore and horspool, with a few more bells and whistles on the top. - for some more background, see: http://effbot.org/stringlib.htm */ + for some more background, see: http://effbot.org/zone/stringlib.htm */ /* note: fastsearch may access s[n], which isn't a problem when using Python's ordinary string types, but may cause problems if you're @@ -16,19 +16,35 @@ #define FAST_COUNT 0 #define FAST_SEARCH 1 +#define FAST_RSEARCH 2 + +#if LONG_BIT >= 128 +#define STRINGLIB_BLOOM_WIDTH 128 +#elif LONG_BIT >= 64 +#define STRINGLIB_BLOOM_WIDTH 64 +#elif LONG_BIT >= 32 +#define STRINGLIB_BLOOM_WIDTH 32 +#else +#error "LONG_BIT is smaller than 32" +#endif + +#define STRINGLIB_BLOOM_ADD(mask, ch) \ + ((mask |= (1UL << ((ch) & (STRINGLIB_BLOOM_WIDTH -1))))) +#define STRINGLIB_BLOOM(mask, ch) \ + ((mask & (1UL << ((ch) & (STRINGLIB_BLOOM_WIDTH -1))))) Py_LOCAL_INLINE(Py_ssize_t) fastsearch(const STRINGLIB_CHAR* s, Py_ssize_t n, const STRINGLIB_CHAR* p, Py_ssize_t m, - int mode) + Py_ssize_t maxcount, int mode) { - long mask; + unsigned long mask; Py_ssize_t skip, count = 0; Py_ssize_t i, j, mlast, w; w = n - m; - if (w < 0) + if (w < 0 || (mode == FAST_COUNT && maxcount == 0)) return -1; /* look for special cases */ @@ -38,54 +54,101 @@ fastsearch(const STRINGLIB_CHAR* s, Py_ssize_t n, /* use special case for 1-character strings */ if (mode == FAST_COUNT) { for (i = 0; i < n; i++) - if (s[i] == p[0]) + if (s[i] == p[0]) { count++; + if (count == maxcount) + return maxcount; + } return count; - } else { + } else if (mode == FAST_SEARCH) { for (i = 0; i < n; i++) if (s[i] == p[0]) return i; + } else { /* FAST_RSEARCH */ + for (i = n - 1; i > -1; i--) + if (s[i] == p[0]) + return i; } return -1; } mlast = m - 1; - - /* create compressed boyer-moore delta 1 table */ skip = mlast - 1; - /* process pattern[:-1] */ - for (mask = i = 0; i < mlast; i++) { - mask |= (1 << (p[i] & 0x1F)); - if (p[i] == p[mlast]) - skip = mlast - i - 1; - } - /* process pattern[-1] outside the loop */ - mask |= (1 << (p[mlast] & 0x1F)); - - for (i = 0; i <= w; i++) { - /* note: using mlast in the skip path slows things down on x86 */ - if (s[i+m-1] == p[m-1]) { - /* candidate match */ - for (j = 0; j < mlast; j++) - if (s[i+j] != p[j]) - break; - if (j == mlast) { - /* got a match! */ - if (mode != FAST_COUNT) + mask = 0; + + if (mode != FAST_RSEARCH) { + + /* create compressed boyer-moore delta 1 table */ + + /* process pattern[:-1] */ + for (i = 0; i < mlast; i++) { + STRINGLIB_BLOOM_ADD(mask, p[i]); + if (p[i] == p[mlast]) + skip = mlast - i - 1; + } + /* process pattern[-1] outside the loop */ + STRINGLIB_BLOOM_ADD(mask, p[mlast]); + + for (i = 0; i <= w; i++) { + /* note: using mlast in the skip path slows things down on x86 */ + if (s[i+m-1] == p[m-1]) { + /* candidate match */ + for (j = 0; j < mlast; j++) + if (s[i+j] != p[j]) + break; + if (j == mlast) { + /* got a match! */ + if (mode != FAST_COUNT) + return i; + count++; + if (count == maxcount) + return maxcount; + i = i + mlast; + continue; + } + /* miss: check if next character is part of pattern */ + if (!STRINGLIB_BLOOM(mask, s[i+m])) + i = i + m; + else + i = i + skip; + } else { + /* skip: check if next character is part of pattern */ + if (!STRINGLIB_BLOOM(mask, s[i+m])) + i = i + m; + } + } + } else { /* FAST_RSEARCH */ + + /* create compressed boyer-moore delta 1 table */ + + /* process pattern[0] outside the loop */ + STRINGLIB_BLOOM_ADD(mask, p[0]); + /* process pattern[:0:-1] */ + for (i = mlast; i > 0; i--) { + STRINGLIB_BLOOM_ADD(mask, p[i]); + if (p[i] == p[0]) + skip = i - 1; + } + + for (i = w; i >= 0; i--) { + if (s[i] == p[0]) { + /* candidate match */ + for (j = mlast; j > 0; j--) + if (s[i+j] != p[j]) + break; + if (j == 0) + /* got a match! */ return i; - count++; - i = i + mlast; - continue; + /* miss: check if previous character is part of pattern */ + if (i > 0 && !STRINGLIB_BLOOM(mask, s[i-1])) + i = i - m; + else + i = i - skip; + } else { + /* skip: check if previous character is part of pattern */ + if (i > 0 && !STRINGLIB_BLOOM(mask, s[i-1])) + i = i - m; } - /* miss: check if next character is part of pattern */ - if (!(mask & (1 << (s[i+m] & 0x1F)))) - i = i + m; - else - i = i + skip; - } else { - /* skip: check if next character is part of pattern */ - if (!(mask & (1 << (s[i+m] & 0x1F)))) - i = i + m; } } @@ -95,10 +158,3 @@ fastsearch(const STRINGLIB_CHAR* s, Py_ssize_t n, } #endif - -/* -Local variables: -c-basic-offset: 4 -indent-tabs-mode: nil -End: -*/ |