ref: 1ccd0cd04d75840861e26f6c5f6ac73396d43d8a
dir: /sys/src/cmd/python/Objects/stringlib/fastsearch.h/
/* stringlib: fastsearch implementation */ #ifndef STRINGLIB_FASTSEARCH_H #define STRINGLIB_FASTSEARCH_H /* 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 */ /* 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 using this code in other contexts. also, the count mode returns -1 if there cannot possible be a match in the target string, and 0 if it has actually checked for matches, but didn't find any. callers beware! */ #define FAST_COUNT 0 #define FAST_SEARCH 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) { long mask; Py_ssize_t skip, count = 0; Py_ssize_t i, j, mlast, w; w = n - m; if (w < 0) return -1; /* look for special cases */ if (m <= 1) { if (m <= 0) return -1; /* use special case for 1-character strings */ if (mode == FAST_COUNT) { for (i = 0; i < n; i++) if (s[i] == p[0]) count++; return count; } else { for (i = 0; i < n; 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) return i; count++; i = i + mlast; continue; } /* 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; } } if (mode != FAST_COUNT) return -1; return count; } #endif /* Local variables: c-basic-offset: 4 indent-tabs-mode: nil End: */