/* 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: 4indent-tabs-mode: nilEnd:*/