← Back to branch summary

~ubuntu-branches/ubuntu/maverick/python3.1/maverick

« back to all changes in this revision

Viewing changes to Objects/stringlib/fastsearch.h

  • Committer: Bazaar Package Importer
  • Author(s): Matthias Klose
  • Date: 2009-03-23 00:01:27 UTC
  • Revision ID: james.westby@ubuntu.com-20090323000127-5fstfxju4ufrhthq
Tags: upstream-3.1~a1+20090322
Import upstream version 3.1~a1+20090322

Show diffs side-by-side

added added

removed removed

Lines of Context:
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.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
 
 
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
*/