Mercurial > cpython-lru_cache-weakref

annotate Objects/stringlib/fastsearch.h @ 78069:a8aa77458e12 3.2

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add c_size_t and c_ssize_t to the ctypes summary table.
author Antoine Pitrou <solipsis@pitrou.net>
date Thu, 12 Jul 2012 20:31:50 +0200
parents eb5aa91f0e16
children 8beaa9a37387
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
38453
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
1 /* stringlib: fastsearch implementation */
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
2
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
3 #ifndef STRINGLIB_FASTSEARCH_H
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
4 #define STRINGLIB_FASTSEARCH_H
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
5
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
6 /* fast search/count implementation, based on a mix between boyer-
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
7 moore and horspool, with a few more bells and whistles on the top.
58095
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
8 for some more background, see: http://effbot.org/zone/stringlib.htm */
38453
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
9
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
10 /* note: fastsearch may access s[n], which isn't a problem when using
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
11 Python's ordinary string types, but may cause problems if you're
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
12 using this code in other contexts. also, the count mode returns -1
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
13 if there cannot possible be a match in the target string, and 0 if
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
14 it has actually checked for matches, but didn't find any. callers
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
15 beware! */
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
16
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
17 #define FAST_COUNT 0
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
18 #define FAST_SEARCH 1
58095
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
19 #define FAST_RSEARCH 2
38453
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
20
58298
e5e55ffe9f73 Merged revisions 77469-77470 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58289
diff changeset
21 #if LONG_BIT >= 128
e5e55ffe9f73 Merged revisions 77469-77470 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58289
diff changeset
22 #define STRINGLIB_BLOOM_WIDTH 128
e5e55ffe9f73 Merged revisions 77469-77470 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58289
diff changeset
23 #elif LONG_BIT >= 64
e5e55ffe9f73 Merged revisions 77469-77470 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58289
diff changeset
24 #define STRINGLIB_BLOOM_WIDTH 64
e5e55ffe9f73 Merged revisions 77469-77470 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58289
diff changeset
25 #elif LONG_BIT >= 32
e5e55ffe9f73 Merged revisions 77469-77470 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58289
diff changeset
26 #define STRINGLIB_BLOOM_WIDTH 32
e5e55ffe9f73 Merged revisions 77469-77470 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58289
diff changeset
27 #else
e5e55ffe9f73 Merged revisions 77469-77470 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58289
diff changeset
28 #error "LONG_BIT is smaller than 32"
e5e55ffe9f73 Merged revisions 77469-77470 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58289
diff changeset
29 #endif
e5e55ffe9f73 Merged revisions 77469-77470 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58289
diff changeset
30
e5e55ffe9f73 Merged revisions 77469-77470 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58289
diff changeset
31 #define STRINGLIB_BLOOM_ADD(mask, ch) \
e5e55ffe9f73 Merged revisions 77469-77470 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58289
diff changeset
32 ((mask |= (1UL << ((ch) & (STRINGLIB_BLOOM_WIDTH -1)))))
e5e55ffe9f73 Merged revisions 77469-77470 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58289
diff changeset
33 #define STRINGLIB_BLOOM(mask, ch) \
e5e55ffe9f73 Merged revisions 77469-77470 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58289
diff changeset
34 ((mask & (1UL << ((ch) & (STRINGLIB_BLOOM_WIDTH -1)))))
58289
5ca1948a8fd6 Merged revisions 77461 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58095
diff changeset
35
38453
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
36 Py_LOCAL_INLINE(Py_ssize_t)
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
37 fastsearch(const STRINGLIB_CHAR* s, Py_ssize_t n,
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
38 const STRINGLIB_CHAR* p, Py_ssize_t m,
58289
5ca1948a8fd6 Merged revisions 77461 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58095
diff changeset
39 Py_ssize_t maxcount, int mode)
38453
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
40 {
58298
e5e55ffe9f73 Merged revisions 77469-77470 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58289
diff changeset
41 unsigned long mask;
38453
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
42 Py_ssize_t skip, count = 0;
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
43 Py_ssize_t i, j, mlast, w;
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
44
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
45 w = n - m;
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
46
58289
5ca1948a8fd6 Merged revisions 77461 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58095
diff changeset
47 if (w < 0 || (mode == FAST_COUNT && maxcount == 0))
38453
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
48 return -1;
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
49
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
50 /* look for special cases */
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
51 if (m <= 1) {
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
52 if (m <= 0)
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
53 return -1;
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
54 /* use special case for 1-character strings */
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
55 if (mode == FAST_COUNT) {
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
56 for (i = 0; i < n; i++)
58289
5ca1948a8fd6 Merged revisions 77461 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58095
diff changeset
57 if (s[i] == p[0]) {
38453
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
58 count++;
58289
5ca1948a8fd6 Merged revisions 77461 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58095
diff changeset
59 if (count == maxcount)
5ca1948a8fd6 Merged revisions 77461 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58095
diff changeset
60 return maxcount;
5ca1948a8fd6 Merged revisions 77461 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58095
diff changeset
61 }
38453
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
62 return count;
58095
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
63 } else if (mode == FAST_SEARCH) {
38453
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
64 for (i = 0; i < n; i++)
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
65 if (s[i] == p[0])
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
66 return i;
58095
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
67 } else { /* FAST_RSEARCH */
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
68 for (i = n - 1; i > -1; i--)
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
69 if (s[i] == p[0])
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
70 return i;
38453
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
71 }
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
72 return -1;
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
73 }
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
74
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
75 mlast = m - 1;
58095
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
76 skip = mlast - 1;
58289
5ca1948a8fd6 Merged revisions 77461 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58095
diff changeset
77 mask = 0;
38453
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
78
58095
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
79 if (mode != FAST_RSEARCH) {
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
80
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
81 /* create compressed boyer-moore delta 1 table */
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
82
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
83 /* process pattern[:-1] */
58289
5ca1948a8fd6 Merged revisions 77461 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58095
diff changeset
84 for (i = 0; i < mlast; i++) {
58298
e5e55ffe9f73 Merged revisions 77469-77470 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58289
diff changeset
85 STRINGLIB_BLOOM_ADD(mask, p[i]);
58095
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
86 if (p[i] == p[mlast])
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
87 skip = mlast - i - 1;
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
88 }
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
89 /* process pattern[-1] outside the loop */
58298
e5e55ffe9f73 Merged revisions 77469-77470 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58289
diff changeset
90 STRINGLIB_BLOOM_ADD(mask, p[mlast]);
38453
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
91
58095
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
92 for (i = 0; i <= w; i++) {
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
93 /* note: using mlast in the skip path slows things down on x86 */
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
94 if (s[i+m-1] == p[m-1]) {
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
95 /* candidate match */
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
96 for (j = 0; j < mlast; j++)
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
97 if (s[i+j] != p[j])
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
98 break;
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
99 if (j == mlast) {
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
100 /* got a match! */
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
101 if (mode != FAST_COUNT)
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
102 return i;
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
103 count++;
58289
5ca1948a8fd6 Merged revisions 77461 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58095
diff changeset
104 if (count == maxcount)
5ca1948a8fd6 Merged revisions 77461 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58095
diff changeset
105 return maxcount;
58095
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
106 i = i + mlast;
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
107 continue;
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
108 }
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
109 /* miss: check if next character is part of pattern */
58298
e5e55ffe9f73 Merged revisions 77469-77470 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58289
diff changeset
110 if (!STRINGLIB_BLOOM(mask, s[i+m]))
58095
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
111 i = i + m;
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
112 else
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
113 i = i + skip;
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
114 } else {
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
115 /* skip: check if next character is part of pattern */
58298
e5e55ffe9f73 Merged revisions 77469-77470 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58289
diff changeset
116 if (!STRINGLIB_BLOOM(mask, s[i+m]))
58095
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
117 i = i + m;
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
118 }
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
119 }
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
120 } else { /* FAST_RSEARCH */
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
121
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
122 /* create compressed boyer-moore delta 1 table */
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
123
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
124 /* process pattern[0] outside the loop */
58298
e5e55ffe9f73 Merged revisions 77469-77470 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58289
diff changeset
125 STRINGLIB_BLOOM_ADD(mask, p[0]);
58095
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
126 /* process pattern[:0:-1] */
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
127 for (i = mlast; i > 0; i--) {
58298
e5e55ffe9f73 Merged revisions 77469-77470 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58289
diff changeset
128 STRINGLIB_BLOOM_ADD(mask, p[i]);
58095
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
129 if (p[i] == p[0])
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
130 skip = i - 1;
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
131 }
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
132
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
133 for (i = w; i >= 0; i--) {
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
134 if (s[i] == p[0]) {
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
135 /* candidate match */
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
136 for (j = mlast; j > 0; j--)
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
137 if (s[i+j] != p[j])
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
138 break;
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
139 if (j == 0)
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
140 /* got a match! */
38453
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
141 return i;
58095
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
142 /* miss: check if previous character is part of pattern */
63850
eb5aa91f0e16 Fix #8530: Prevent stringlib fastsearch from reading beyond the front of an array.
Florent Xicluna <florent.xicluna@gmail.com>
parents: 58298
diff changeset
143 if (i > 0 && !STRINGLIB_BLOOM(mask, s[i-1]))
58095
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
144 i = i - m;
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
145 else
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
146 i = i - skip;
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
147 } else {
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
148 /* skip: check if previous character is part of pattern */
63850
eb5aa91f0e16 Fix #8530: Prevent stringlib fastsearch from reading beyond the front of an array.
Florent Xicluna <florent.xicluna@gmail.com>
parents: 58298
diff changeset
149 if (i > 0 && !STRINGLIB_BLOOM(mask, s[i-1]))
58095
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
150 i = i - m;
38453
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
151 }
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
152 }
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
153 }
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
154
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
155 if (mode != FAST_COUNT)
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
156 return -1;
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
157 return count;
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
158 }
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
159
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
160 #endif