Mercurial > cpython-lru_cache-weakref

annotate Objects/stringlib/fastsearch.h @ 65035:87f4b32905df 2.7

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Cosmetic fix to use print function.
author Hirokazu Yamamoto <ocean-city@m2.ccsnet.ne.jp>
date Fri, 01 Oct 2010 10:48:47 +0000
parents 95117aab9a86
children
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.
58090
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
8 for some more background, see: http://effbot.org/zone/stringlib.htm */
38381
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
58090
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
19 #define FAST_RSEARCH 2
38381
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
20
58297
9225ea677c4b Sanitize bloom filter macros
Antoine Pitrou <solipsis@pitrou.net>
parents: 58296
diff changeset
21 #if LONG_BIT >= 128
9225ea677c4b Sanitize bloom filter macros
Antoine Pitrou <solipsis@pitrou.net>
parents: 58296
diff changeset
22 #define STRINGLIB_BLOOM_WIDTH 128
9225ea677c4b Sanitize bloom filter macros
Antoine Pitrou <solipsis@pitrou.net>
parents: 58296
diff changeset
23 #elif LONG_BIT >= 64
9225ea677c4b Sanitize bloom filter macros
Antoine Pitrou <solipsis@pitrou.net>
parents: 58296
diff changeset
24 #define STRINGLIB_BLOOM_WIDTH 64
9225ea677c4b Sanitize bloom filter macros
Antoine Pitrou <solipsis@pitrou.net>
parents: 58296
diff changeset
25 #elif LONG_BIT >= 32
9225ea677c4b Sanitize bloom filter macros
Antoine Pitrou <solipsis@pitrou.net>
parents: 58296
diff changeset
26 #define STRINGLIB_BLOOM_WIDTH 32
9225ea677c4b Sanitize bloom filter macros
Antoine Pitrou <solipsis@pitrou.net>
parents: 58296
diff changeset
27 #else
9225ea677c4b Sanitize bloom filter macros
Antoine Pitrou <solipsis@pitrou.net>
parents: 58296
diff changeset
28 #error "LONG_BIT is smaller than 32"
9225ea677c4b Sanitize bloom filter macros
Antoine Pitrou <solipsis@pitrou.net>
parents: 58296
diff changeset
29 #endif
9225ea677c4b Sanitize bloom filter macros
Antoine Pitrou <solipsis@pitrou.net>
parents: 58296
diff changeset
30
9225ea677c4b Sanitize bloom filter macros
Antoine Pitrou <solipsis@pitrou.net>
parents: 58296
diff changeset
31 #define STRINGLIB_BLOOM_ADD(mask, ch) \
9225ea677c4b Sanitize bloom filter macros
Antoine Pitrou <solipsis@pitrou.net>
parents: 58296
diff changeset
32 ((mask |= (1UL << ((ch) & (STRINGLIB_BLOOM_WIDTH -1)))))
9225ea677c4b Sanitize bloom filter macros
Antoine Pitrou <solipsis@pitrou.net>
parents: 58296
diff changeset
33 #define STRINGLIB_BLOOM(mask, ch) \
9225ea677c4b Sanitize bloom filter macros
Antoine Pitrou <solipsis@pitrou.net>
parents: 58296
diff changeset
34 ((mask & (1UL << ((ch) & (STRINGLIB_BLOOM_WIDTH -1)))))
58288
66f1d4a4c799 Issue #7622: Improve the split(), rsplit(), splitlines() and replace()
Antoine Pitrou <solipsis@pitrou.net>
parents: 58090
diff changeset
35
38440
5b0753b9d16a needforspeed: replace improvements, changed to Py_LOCAL_INLINE
Fredrik Lundh <fredrik@pythonware.com>
parents: 38390
diff changeset
36 Py_LOCAL_INLINE(Py_ssize_t)
38381
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
37 fastsearch(const STRINGLIB_CHAR* s, Py_ssize_t n,
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
38 const STRINGLIB_CHAR* p, Py_ssize_t m,
58288
66f1d4a4c799 Issue #7622: Improve the split(), rsplit(), splitlines() and replace()
Antoine Pitrou <solipsis@pitrou.net>
parents: 58090
diff changeset
39 Py_ssize_t maxcount, int mode)
38381
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
40 {
58297
9225ea677c4b Sanitize bloom filter macros
Antoine Pitrou <solipsis@pitrou.net>
parents: 58296
diff changeset
41 unsigned long mask;
38381
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
42 Py_ssize_t skip, count = 0;
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
43 Py_ssize_t i, j, mlast, w;
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
44
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
45 w = n - m;
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
46
58288
66f1d4a4c799 Issue #7622: Improve the split(), rsplit(), splitlines() and replace()
Antoine Pitrou <solipsis@pitrou.net>
parents: 58090
diff changeset
47 if (w < 0 || (mode == FAST_COUNT && maxcount == 0))
38381
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
48 return -1;
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
49
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
50 /* look for special cases */
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
51 if (m <= 1) {
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
52 if (m <= 0)
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
53 return -1;
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
54 /* use special case for 1-character strings */
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
55 if (mode == FAST_COUNT) {
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
56 for (i = 0; i < n; i++)
58288
66f1d4a4c799 Issue #7622: Improve the split(), rsplit(), splitlines() and replace()
Antoine Pitrou <solipsis@pitrou.net>
parents: 58090
diff changeset
57 if (s[i] == p[0]) {
38381
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
58 count++;
58288
66f1d4a4c799 Issue #7622: Improve the split(), rsplit(), splitlines() and replace()
Antoine Pitrou <solipsis@pitrou.net>
parents: 58090
diff changeset
59 if (count == maxcount)
66f1d4a4c799 Issue #7622: Improve the split(), rsplit(), splitlines() and replace()
Antoine Pitrou <solipsis@pitrou.net>
parents: 58090
diff changeset
60 return maxcount;
66f1d4a4c799 Issue #7622: Improve the split(), rsplit(), splitlines() and replace()
Antoine Pitrou <solipsis@pitrou.net>
parents: 58090
diff changeset
61 }
38381
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
62 return count;
58090
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
63 } else if (mode == FAST_SEARCH) {
38381
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
64 for (i = 0; i < n; i++)
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
65 if (s[i] == p[0])
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
66 return i;
58090
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
67 } else { /* FAST_RSEARCH */
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
68 for (i = n - 1; i > -1; i--)
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
69 if (s[i] == p[0])
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
70 return i;
38381
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
71 }
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
72 return -1;
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
73 }
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
74
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
75 mlast = m - 1;
58090
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
76 skip = mlast - 1;
58288
66f1d4a4c799 Issue #7622: Improve the split(), rsplit(), splitlines() and replace()
Antoine Pitrou <solipsis@pitrou.net>
parents: 58090
diff changeset
77 mask = 0;
38381
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
78
58090
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
79 if (mode != FAST_RSEARCH) {
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
80
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
81 /* create compressed boyer-moore delta 1 table */
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
82
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
83 /* process pattern[:-1] */
58288
66f1d4a4c799 Issue #7622: Improve the split(), rsplit(), splitlines() and replace()
Antoine Pitrou <solipsis@pitrou.net>
parents: 58090
diff changeset
84 for (i = 0; i < mlast; i++) {
58297
9225ea677c4b Sanitize bloom filter macros
Antoine Pitrou <solipsis@pitrou.net>
parents: 58296
diff changeset
85 STRINGLIB_BLOOM_ADD(mask, p[i]);
58090
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
86 if (p[i] == p[mlast])
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
87 skip = mlast - i - 1;
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
88 }
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
89 /* process pattern[-1] outside the loop */
58297
9225ea677c4b Sanitize bloom filter macros
Antoine Pitrou <solipsis@pitrou.net>
parents: 58296
diff changeset
90 STRINGLIB_BLOOM_ADD(mask, p[mlast]);
38381
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
91
58090
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
92 for (i = 0; i <= w; i++) {
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
93 /* note: using mlast in the skip path slows things down on x86 */
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
94 if (s[i+m-1] == p[m-1]) {
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
95 /* candidate match */
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
96 for (j = 0; j < mlast; j++)
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
97 if (s[i+j] != p[j])
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
98 break;
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
99 if (j == mlast) {
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
100 /* got a match! */
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
101 if (mode != FAST_COUNT)
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
102 return i;
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
103 count++;
58288
66f1d4a4c799 Issue #7622: Improve the split(), rsplit(), splitlines() and replace()
Antoine Pitrou <solipsis@pitrou.net>
parents: 58090
diff changeset
104 if (count == maxcount)
66f1d4a4c799 Issue #7622: Improve the split(), rsplit(), splitlines() and replace()
Antoine Pitrou <solipsis@pitrou.net>
parents: 58090
diff changeset
105 return maxcount;
58090
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
106 i = i + mlast;
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
107 continue;
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
108 }
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
109 /* miss: check if next character is part of pattern */
58297
9225ea677c4b Sanitize bloom filter macros
Antoine Pitrou <solipsis@pitrou.net>
parents: 58296
diff changeset
110 if (!STRINGLIB_BLOOM(mask, s[i+m]))
58090
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
111 i = i + m;
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
112 else
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
113 i = i + skip;
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
114 } else {
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
115 /* skip: check if next character is part of pattern */
58297
9225ea677c4b Sanitize bloom filter macros
Antoine Pitrou <solipsis@pitrou.net>
parents: 58296
diff changeset
116 if (!STRINGLIB_BLOOM(mask, s[i+m]))
58090
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
117 i = i + m;
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
118 }
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
119 }
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
120 } else { /* FAST_RSEARCH */
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
121
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
122 /* create compressed boyer-moore delta 1 table */
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
123
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
124 /* process pattern[0] outside the loop */
58297
9225ea677c4b Sanitize bloom filter macros
Antoine Pitrou <solipsis@pitrou.net>
parents: 58296
diff changeset
125 STRINGLIB_BLOOM_ADD(mask, p[0]);
58090
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
126 /* process pattern[:0:-1] */
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
127 for (i = mlast; i > 0; i--) {
58297
9225ea677c4b Sanitize bloom filter macros
Antoine Pitrou <solipsis@pitrou.net>
parents: 58296
diff changeset
128 STRINGLIB_BLOOM_ADD(mask, p[i]);
58090
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
129 if (p[i] == p[0])
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
130 skip = i - 1;
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
131 }
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
132
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
133 for (i = w; i >= 0; i--) {
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
134 if (s[i] == p[0]) {
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
135 /* candidate match */
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
136 for (j = mlast; j > 0; j--)
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
137 if (s[i+j] != p[j])
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
138 break;
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
139 if (j == 0)
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
140 /* got a match! */
38381
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
141 return i;
58090
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
142 /* miss: check if previous character is part of pattern */
63884
95117aab9a86 Merged revisions 83833,83838-83839,83859,83878 via svnmerge from
Florent Xicluna <florent.xicluna@gmail.com>
parents: 58297
diff changeset
143 if (i > 0 && !STRINGLIB_BLOOM(mask, s[i-1]))
58090
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
144 i = i - m;
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
145 else
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
146 i = i - skip;
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
147 } else {
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
148 /* skip: check if previous character is part of pattern */
63884
95117aab9a86 Merged revisions 83833,83838-83839,83859,83878 via svnmerge from
Florent Xicluna <florent.xicluna@gmail.com>
parents: 58297
diff changeset
149 if (i > 0 && !STRINGLIB_BLOOM(mask, s[i-1]))
58090
ddf61cd775e0 Issue #7462: Implement the stringlib fast search algorithm for the `rfind`,
Antoine Pitrou <solipsis@pitrou.net>
parents: 61705
diff changeset
150 i = i - m;
38381
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
151 }
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
152 }
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
153 }
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
154
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
155 if (mode != FAST_COUNT)
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
156 return -1;
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
157 return count;
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
158 }
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
159
b32f9bb2e077 needforspeed: stringlib refactoring (in progress)
Fredrik Lundh <fredrik@pythonware.com>
parents:
diff changeset
160 #endif