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/stringlib */
   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
  20 Py_LOCAL_INLINE(Py_ssize_t)
  21 fastsearch(const STRINGLIB_CHAR* s, Py_ssize_t n,
  22            const STRINGLIB_CHAR* p, Py_ssize_t m,
  23            int mode)
  24 {
  25     long mask;
  26     Py_ssize_t skip, count = 0;
  27     Py_ssize_t i, j, mlast, w;
  28
  29     w = n - m;
  30
  31     if (w < 0)
  32         return -1;
  33
  34     /* look for special cases */
  35     if (m <= 1) {
  36         if (m <= 0)
  37             return -1;
  38         /* use special case for 1-character strings */
  39         if (mode == FAST_COUNT) {
  40             for (i = 0; i < n; i++)
  41                 if (s[i] == p[0])
  42                     count++;
  43             return count;
  44         } else {
  45             for (i = 0; i < n; i++)
  46                 if (s[i] == p[0])
  47                     return i;
  48         }
  49         return -1;
  50     }
  51
  52     mlast = m - 1;
  53
  54     /* create compressed boyer-moore delta 1 table */
  55     skip = mlast - 1;
  56     /* process pattern[:-1] */
  57     for (mask = i = 0; i < mlast; i++) {
  58         mask |= (1 << (p[i] & 0x1F));
  59         if (p[i] == p[mlast])
  60             skip = mlast - i - 1;
  61     }
  62     /* process pattern[-1] outside the loop */
  63     mask |= (1 << (p[mlast] & 0x1F));
  64
  65     for (i = 0; i <= w; i++) {
  66         /* note: using mlast in the skip path slows things down on x86 */
  67         if (s[i+m-1] == p[m-1]) {
  68             /* candidate match */
  69             for (j = 0; j < mlast; j++)
  70                 if (s[i+j] != p[j])
  71                     break;
  72             if (j == mlast) {
  73                 /* got a match! */
  74                 if (mode != FAST_COUNT)
  75                     return i;
  76                 count++;
  77                 i = i + mlast;
  78                 continue;
  79             }
  80             /* miss: check if next character is part of pattern */
  81             if (!(mask & (1 << (s[i+m] & 0x1F))))
  82                 i = i + m;
  83             else
  84                 i = i + skip;
  85         } else {
  86             /* skip: check if next character is part of pattern */
  87             if (!(mask & (1 << (s[i+m] & 0x1F))))
  88                 i = i + m;
  89         }
  90     }
  91
  92     if (mode != FAST_COUNT)
  93         return -1;
  94     return count;
  95 }
  96
  97 #endif
  98
  99 /*
 100 Local variables:
 101 c-basic-offset: 4
 102 indent-tabs-mode: nil
 103 End:
 104 */