Objects/stringlib/fastsearch.h

   1 /* stringlib: fastsearch implementation */
   2
   3 #ifndef STRINGLIB_FASTSEARCH_H
   4 #define STRINGLIB_FASTSEARCH_H
   5
   6 /* fast search/count implementation, based on a mix between boyer-
   7    moore and horspool, with a few more bells and whistles on the top.
   8    for some more background, see: http://effbot.org/zone/stringlib.htm */
   9
  10 /* note: fastsearch may access s[n], which isn't a problem when using
  11    Python's ordinary string types, but may cause problems if you're
  12    using this code in other contexts.  also, the count mode returns -1
  13    if there cannot possible be a match in the target string, and 0 if
  14    it has actually checked for matches, but didn't find any.  callers
  15    beware! */
  16
  17 #define FAST_COUNT 0
  18 #define FAST_SEARCH 1
  19 #define FAST_RSEARCH 2
  20
  21 #if LONG_BIT >= 128
  22 #define STRINGLIB_BLOOM_WIDTH 128
  23 #elif LONG_BIT >= 64
  24 #define STRINGLIB_BLOOM_WIDTH 64
  25 #elif LONG_BIT >= 32
  26 #define STRINGLIB_BLOOM_WIDTH 32
  27 #else
  28 #error "LONG_BIT is smaller than 32"
  29 #endif
  30
  31 #define STRINGLIB_BLOOM_ADD(mask, ch) \
  32     ((mask |= (1UL << ((ch) & (STRINGLIB_BLOOM_WIDTH -1)))))
  33 #define STRINGLIB_BLOOM(mask, ch)     \
  34     ((mask &  (1UL << ((ch) & (STRINGLIB_BLOOM_WIDTH -1)))))
  35
  36 Py_LOCAL_INLINE(Py_ssize_t)
  37 fastsearch(const STRINGLIB_CHAR* s, Py_ssize_t n,
  38            const STRINGLIB_CHAR* p, Py_ssize_t m,
  39            Py_ssize_t maxcount, int mode)
  40 {
  41     unsigned long mask;
  42     Py_ssize_t skip, count = 0;
  43     Py_ssize_t i, j, mlast, w;
  44
  45     w = n - m;
  46
  47     if (w < 0 || (mode == FAST_COUNT && maxcount == 0))
  48         return -1;
  49
  50     /* look for special cases */
  51     if (m <= 1) {
  52         if (m <= 0)
  53             return -1;
  54         /* use special case for 1-character strings */
  55         if (mode == FAST_COUNT) {
  56             for (i = 0; i < n; i++)
  57                 if (s[i] == p[0]) {
  58                     count++;
  59                     if (count == maxcount)
  60                         return maxcount;
  61                 }
  62             return count;
  63         } else if (mode == FAST_SEARCH) {
  64             for (i = 0; i < n; i++)
  65                 if (s[i] == p[0])
  66                     return i;
  67         } else {    /* FAST_RSEARCH */
  68             for (i = n - 1; i > -1; i--)
  69                 if (s[i] == p[0])
  70                     return i;
  71         }
  72         return -1;
  73     }
  74
  75     mlast = m - 1;
  76     skip = mlast - 1;
  77     mask = 0;
  78
  79     if (mode != FAST_RSEARCH) {
  80
  81         /* create compressed boyer-moore delta 1 table */
  82
  83         /* process pattern[:-1] */
  84         for (i = 0; i < mlast; i++) {
  85             STRINGLIB_BLOOM_ADD(mask, p[i]);
  86             if (p[i] == p[mlast])
  87                 skip = mlast - i - 1;
  88         }
  89         /* process pattern[-1] outside the loop */
  90         STRINGLIB_BLOOM_ADD(mask, p[mlast]);
  91
  92         for (i = 0; i <= w; i++) {
  93             /* note: using mlast in the skip path slows things down on x86 */
  94             if (s[i+m-1] == p[m-1]) {
  95                 /* candidate match */
  96                 for (j = 0; j < mlast; j++)
  97                     if (s[i+j] != p[j])
  98                         break;
  99                 if (j == mlast) {
 100                     /* got a match! */
 101                     if (mode != FAST_COUNT)
 102                         return i;
 103                     count++;
 104                     if (count == maxcount)
 105                         return maxcount;
 106                     i = i + mlast;
 107                     continue;
 108                 }
 109                 /* miss: check if next character is part of pattern */
 110                 if (!STRINGLIB_BLOOM(mask, s[i+m]))
 111                     i = i + m;
 112                 else
 113                     i = i + skip;
 114             } else {
 115                 /* skip: check if next character is part of pattern */
 116                 if (!STRINGLIB_BLOOM(mask, s[i+m]))
 117                     i = i + m;
 118             }
 119         }
 120     } else {    /* FAST_RSEARCH */
 121
 122         /* create compressed boyer-moore delta 1 table */
 123
 124         /* process pattern[0] outside the loop */
 125         STRINGLIB_BLOOM_ADD(mask, p[0]);
 126         /* process pattern[:0:-1] */
 127         for (i = mlast; i > 0; i--) {
 128             STRINGLIB_BLOOM_ADD(mask, p[i]);
 129             if (p[i] == p[0])
 130                 skip = i - 1;
 131         }
 132
 133         for (i = w; i >= 0; i--) {
 134             if (s[i] == p[0]) {
 135                 /* candidate match */
 136                 for (j = mlast; j > 0; j--)
 137                     if (s[i+j] != p[j])
 138                         break;
 139                 if (j == 0)
 140                     /* got a match! */
 141                     return i;
 142                 /* miss: check if previous character is part of pattern */
 143                 if (i > 0 && !STRINGLIB_BLOOM(mask, s[i-1]))
 144                     i = i - m;
 145                 else
 146                     i = i - skip;
 147             } else {
 148                 /* skip: check if previous character is part of pattern */
 149                 if (i > 0 && !STRINGLIB_BLOOM(mask, s[i-1]))
 150                     i = i - m;
 151             }
 152         }
 153     }
 154
 155     if (mode != FAST_COUNT)
 156         return -1;
 157     return count;
 158 }
 159
 160 #endif