Mercurial > cpython-lru_cache-weakref

annotate Objects/stringlib/fastsearch.h @ 58925:eecf1bef052d 2.6

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Merged revisions 78207 via svnmerge from svn+ssh://pythondev@svn.python.org/python/trunk ........ r78207 | ezio.melotti | 2010-02-17 01:26:09 +0200 (Wed, 17 Feb 2010) | 1 line #7930: fix stripid ........
author Ezio Melotti <ezio.melotti@gmail.com>
date Tue, 16 Feb 2010 23:29:44 +0000
parents 5b0753b9d16a
children f76f81044d40
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
38381
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
1 /* stringlib: fastsearch implementation */
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
2
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
3 #ifndef STRINGLIB_FASTSEARCH_H
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
4 #define STRINGLIB_FASTSEARCH_H
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
5
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
6 /* fast search/count implementation, based on a mix between boyer-
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
7 moore and horspool, with a few more bells and whistles on the top.
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
8 for some more background, see: http://effbot.org/stringlib */
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
9
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
10 /* note: fastsearch may access s[n], which isn't a problem when using
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
11 Python's ordinary string types, but may cause problems if you're
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
12 using this code in other contexts. also, the count mode returns -1
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
13 if there cannot possible be a match in the target string, and 0 if
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
14 it has actually checked for matches, but didn't find any. callers
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
15 beware! */
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
16
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
17 #define FAST_COUNT 0
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
18 #define FAST_SEARCH 1
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
19
38440
5b0753b9d16a needforspeed: replace improvements, changed to Py_LOCAL_INLINE
Fredrik Lundh <fredrik@pythonware.com>
parents: 38390
diff changeset
20 Py_LOCAL_INLINE(Py_ssize_t)
38381
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
21 fastsearch(const STRINGLIB_CHAR* s, Py_ssize_t n,
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
22 const STRINGLIB_CHAR* p, Py_ssize_t m,
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
23 int mode)
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
24 {
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
25 long mask;
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
26 Py_ssize_t skip, count = 0;
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
27 Py_ssize_t i, j, mlast, w;
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
28
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
29 w = n - m;
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
30
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
31 if (w < 0)
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
32 return -1;
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
33
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
34 /* look for special cases */
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
35 if (m <= 1) {
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
36 if (m <= 0)
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
37 return -1;
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
38 /* use special case for 1-character strings */
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
39 if (mode == FAST_COUNT) {
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
40 for (i = 0; i < n; i++)
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
41 if (s[i] == p[0])
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
42 count++;
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
43 return count;
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
44 } else {
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
45 for (i = 0; i < n; i++)
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
46 if (s[i] == p[0])
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
47 return i;
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
48 }
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
49 return -1;
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
50 }
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
51
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
52 mlast = m - 1;
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
53
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
54 /* create compressed boyer-moore delta 1 table */
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
55 skip = mlast - 1;
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
56 /* process pattern[:-1] */
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
57 for (mask = i = 0; i < mlast; i++) {
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
58 mask |= (1 << (p[i] & 0x1F));
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
59 if (p[i] == p[mlast])
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
60 skip = mlast - i - 1;
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
61 }
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
62 /* process pattern[-1] outside the loop */
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
63 mask |= (1 << (p[mlast] & 0x1F));
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
64
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
65 for (i = 0; i <= w; i++) {
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
66 /* note: using mlast in the skip path slows things down on x86 */
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
67 if (s[i+m-1] == p[m-1]) {
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
68 /* candidate match */
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
69 for (j = 0; j < mlast; j++)
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
70 if (s[i+j] != p[j])
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
71 break;
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
72 if (j == mlast) {
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
73 /* got a match! */
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
74 if (mode != FAST_COUNT)
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
75 return i;
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
76 count++;
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
77 i = i + mlast;
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
78 continue;
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
79 }
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
80 /* miss: check if next character is part of pattern */
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
81 if (!(mask & (1 << (s[i+m] & 0x1F))))
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
82 i = i + m;
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
83 else
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
84 i = i + skip;
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
85 } else {
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
86 /* skip: check if next character is part of pattern */
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
87 if (!(mask & (1 << (s[i+m] & 0x1F))))
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
88 i = i + m;
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
89 }
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
90 }
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
91
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
92 if (mode != FAST_COUNT)
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
93 return -1;
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
94 return count;
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
95 }
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
96
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
97 #endif
38390
76807902a2f5 needforspeed: added rpartition implementation
Fredrik Lundh <fredrik@pythonware.com>
parents: 38381
diff changeset
98
76807902a2f5 needforspeed: added rpartition implementation
Fredrik Lundh <fredrik@pythonware.com>
parents: 38381
diff changeset
99 /*
76807902a2f5 needforspeed: added rpartition implementation
Fredrik Lundh <fredrik@pythonware.com>
parents: 38381
diff changeset
100 Local variables:
76807902a2f5 needforspeed: added rpartition implementation
Fredrik Lundh <fredrik@pythonware.com>
parents: 38381
diff changeset
101 c-basic-offset: 4
76807902a2f5 needforspeed: added rpartition implementation
Fredrik Lundh <fredrik@pythonware.com>
parents: 38381
diff changeset
102 indent-tabs-mode: nil
76807902a2f5 needforspeed: added rpartition implementation
Fredrik Lundh <fredrik@pythonware.com>
parents: 38381
diff changeset
103 End:
76807902a2f5 needforspeed: added rpartition implementation
Fredrik Lundh <fredrik@pythonware.com>
parents: 38381
diff changeset
104 */