Mercurial > cpython-lru_cache-weakref

annotate Objects/stringlib/fastsearch.h @ 79691:05c8928362ee

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Merge __next__ method link fixes with 3.3.
author Ezio Melotti <ezio.melotti@gmail.com>
date Fri, 12 Oct 2012 13:46:37 +0300
parents 99112b851b25
children ad9b5c69b8b6
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 #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
4
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
5 /* 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
6 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
7 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
8
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
9 /* 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
10 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
11 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
12 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
13 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
14 beware! */
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
15
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
16 #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
17 #define FAST_SEARCH 1
58095
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
18 #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
19
58298
e5e55ffe9f73 Merged revisions 77469-77470 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58289
diff changeset
20 #if LONG_BIT >= 128
e5e55ffe9f73 Merged revisions 77469-77470 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58289
diff changeset
21 #define STRINGLIB_BLOOM_WIDTH 128
e5e55ffe9f73 Merged revisions 77469-77470 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58289
diff changeset
22 #elif LONG_BIT >= 64
e5e55ffe9f73 Merged revisions 77469-77470 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58289
diff changeset
23 #define STRINGLIB_BLOOM_WIDTH 64
e5e55ffe9f73 Merged revisions 77469-77470 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58289
diff changeset
24 #elif LONG_BIT >= 32
e5e55ffe9f73 Merged revisions 77469-77470 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58289
diff changeset
25 #define STRINGLIB_BLOOM_WIDTH 32
e5e55ffe9f73 Merged revisions 77469-77470 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58289
diff changeset
26 #else
e5e55ffe9f73 Merged revisions 77469-77470 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58289
diff changeset
27 #error "LONG_BIT is smaller than 32"
e5e55ffe9f73 Merged revisions 77469-77470 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58289
diff changeset
28 #endif
e5e55ffe9f73 Merged revisions 77469-77470 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58289
diff changeset
29
e5e55ffe9f73 Merged revisions 77469-77470 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58289
diff changeset
30 #define STRINGLIB_BLOOM_ADD(mask, ch) \
e5e55ffe9f73 Merged revisions 77469-77470 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58289
diff changeset
31 ((mask |= (1UL << ((ch) & (STRINGLIB_BLOOM_WIDTH -1)))))
e5e55ffe9f73 Merged revisions 77469-77470 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58289
diff changeset
32 #define STRINGLIB_BLOOM(mask, ch) \
e5e55ffe9f73 Merged revisions 77469-77470 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58289
diff changeset
33 ((mask & (1UL << ((ch) & (STRINGLIB_BLOOM_WIDTH -1)))))
58289
5ca1948a8fd6 Merged revisions 77461 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58095
diff changeset
34
72859
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
35
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
36 Py_LOCAL_INLINE(Py_ssize_t)
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
37 STRINGLIB(fastsearch_memchr_1char)(const STRINGLIB_CHAR* s, Py_ssize_t n,
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
38 STRINGLIB_CHAR ch, unsigned char needle,
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
39 Py_ssize_t maxcount, int mode)
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
40 {
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
41 void *candidate;
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
42 const STRINGLIB_CHAR *found;
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
43
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
44 #define DO_MEMCHR(memchr, s, needle, nchars) do { \
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
45 candidate = memchr((const void *) (s), (needle), (nchars) * sizeof(STRINGLIB_CHAR)); \
79065
99112b851b25 Issue #15144: Fix possible integer overflow when handling pointers as integer values, by using Py_uintptr_t instead of size_t.
Antoine Pitrou <solipsis@pitrou.net>
parents: 78386
diff changeset
46 found = (const STRINGLIB_CHAR *) _Py_ALIGN_DOWN(candidate, sizeof(STRINGLIB_CHAR)); \
72859
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
47 } while (0)
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
48
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
49 if (mode == FAST_SEARCH) {
78386
0e95b61af859 Close #15534: Fix a typo in the fast search function of the string library (_s => s)
Victor Stinner <victor.stinner@gmail.com>
parents: 72959
diff changeset
50 const STRINGLIB_CHAR *ptr = s;
72859
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
51 const STRINGLIB_CHAR *e = s + n;
78386
0e95b61af859 Close #15534: Fix a typo in the fast search function of the string library (_s => s)
Victor Stinner <victor.stinner@gmail.com>
parents: 72959
diff changeset
52 while (ptr < e) {
0e95b61af859 Close #15534: Fix a typo in the fast search function of the string library (_s => s)
Victor Stinner <victor.stinner@gmail.com>
parents: 72959
diff changeset
53 DO_MEMCHR(memchr, ptr, needle, e - ptr);
72859
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
54 if (found == NULL)
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
55 return -1;
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
56 if (sizeof(STRINGLIB_CHAR) == 1 || *found == ch)
78386
0e95b61af859 Close #15534: Fix a typo in the fast search function of the string library (_s => s)
Victor Stinner <victor.stinner@gmail.com>
parents: 72959
diff changeset
57 return (found - s);
72859
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
58 /* False positive */
78386
0e95b61af859 Close #15534: Fix a typo in the fast search function of the string library (_s => s)
Victor Stinner <victor.stinner@gmail.com>
parents: 72959
diff changeset
59 ptr = found + 1;
72859
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
60 }
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
61 return -1;
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
62 }
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
63 #ifdef HAVE_MEMRCHR
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
64 /* memrchr() is a GNU extension, available since glibc 2.1.91.
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
65 it doesn't seem as optimized as memchr(), but is still quite
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
66 faster than our hand-written loop in FASTSEARCH below */
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
67 else if (mode == FAST_RSEARCH) {
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
68 while (n > 0) {
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
69 DO_MEMCHR(memrchr, s, needle, n);
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
70 if (found == NULL)
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
71 return -1;
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
72 n = found - s;
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
73 if (sizeof(STRINGLIB_CHAR) == 1 || *found == ch)
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
74 return n;
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
75 /* False positive */
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
76 }
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
77 return -1;
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
78 }
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
79 #endif
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
80 else {
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
81 assert(0); /* Should never get here */
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
82 return 0;
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
83 }
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
84
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
85 #undef DO_MEMCHR
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
86 }
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
87
38453
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
88 Py_LOCAL_INLINE(Py_ssize_t)
72475
8beaa9a37387 Implement PEP 393.
Martin v. Löwis <martin@v.loewis.de>
parents: 63850
diff changeset
89 FASTSEARCH(const STRINGLIB_CHAR* s, Py_ssize_t n,
38453
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
90 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
91 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
92 {
58298
e5e55ffe9f73 Merged revisions 77469-77470 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58289
diff changeset
93 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
94 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
95 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
96
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
97 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
98
58289
5ca1948a8fd6 Merged revisions 77461 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58095
diff changeset
99 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
100 return -1;
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
101
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
102 /* 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
103 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
104 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
105 return -1;
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
106 /* use special case for 1-character strings */
72859
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
107 if (n > 10 && (mode == FAST_SEARCH
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
108 #ifdef HAVE_MEMRCHR
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
109 || mode == FAST_RSEARCH
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
110 #endif
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
111 )) {
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
112 /* use memchr if we can choose a needle without two many likely
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
113 false positives */
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
114 unsigned char needle;
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
115 needle = p[0] & 0xff;
72874
bfd3fcfb02f3 Fix fastsearch for UCS2 and UCS4
Victor Stinner <victor.stinner@haypocalc.com>
parents: 72859
diff changeset
116 #if STRINGLIB_SIZEOF_CHAR > 1
72959
ca00e021322d Fix typo
Antoine Pitrou <solipsis@pitrou.net>
parents: 72911
diff changeset
117 /* If looking for a multiple of 256, we'd have too
72911
701b2e0e6f3f Add a comment explaining this heuristic.
Antoine Pitrou <solipsis@pitrou.net>
parents: 72910
diff changeset
118 many false positives looking for the '\0' byte in UCS2
701b2e0e6f3f Add a comment explaining this heuristic.
Antoine Pitrou <solipsis@pitrou.net>
parents: 72910
diff changeset
119 and UCS4 representations. */
72910
c61137ff5f52 Simplify heuristic for when to use memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72874
diff changeset
120 if (needle != 0)
72874
bfd3fcfb02f3 Fix fastsearch for UCS2 and UCS4
Victor Stinner <victor.stinner@haypocalc.com>
parents: 72859
diff changeset
121 #endif
72859
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
122 return STRINGLIB(fastsearch_memchr_1char)
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
123 (s, n, p[0], needle, maxcount, mode);
af4a89f4f466 Issue #13134: optimize finding single-character strings using memchr
Antoine Pitrou <solipsis@pitrou.net>
parents: 72475
diff changeset
124 }
38453
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
125 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
126 for (i = 0; i < n; i++)
58289
5ca1948a8fd6 Merged revisions 77461 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58095
diff changeset
127 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
128 count++;
58289
5ca1948a8fd6 Merged revisions 77461 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58095
diff changeset
129 if (count == maxcount)
5ca1948a8fd6 Merged revisions 77461 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58095
diff changeset
130 return maxcount;
5ca1948a8fd6 Merged revisions 77461 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58095
diff changeset
131 }
38453
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
132 return count;
58095
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
133 } 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
134 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
135 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
136 return i;
58095
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
137 } else { /* FAST_RSEARCH */
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
138 for (i = n - 1; i > -1; i--)
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
139 if (s[i] == p[0])
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
140 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
141 }
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
142 return -1;
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
143 }
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
144
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
145 mlast = m - 1;
58095
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
146 skip = mlast - 1;
58289
5ca1948a8fd6 Merged revisions 77461 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58095
diff changeset
147 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
148
58095
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
149 if (mode != FAST_RSEARCH) {
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
150
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
151 /* create compressed boyer-moore delta 1 table */
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
152
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
153 /* process pattern[:-1] */
58289
5ca1948a8fd6 Merged revisions 77461 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58095
diff changeset
154 for (i = 0; i < mlast; i++) {
58298
e5e55ffe9f73 Merged revisions 77469-77470 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58289
diff changeset
155 STRINGLIB_BLOOM_ADD(mask, p[i]);
58095
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
156 if (p[i] == p[mlast])
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
157 skip = mlast - i - 1;
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
158 }
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
159 /* process pattern[-1] outside the loop */
58298
e5e55ffe9f73 Merged revisions 77469-77470 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58289
diff changeset
160 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
161
58095
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
162 for (i = 0; i <= w; i++) {
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
163 /* 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
164 if (s[i+m-1] == p[m-1]) {
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
165 /* candidate match */
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
166 for (j = 0; j < mlast; j++)
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
167 if (s[i+j] != p[j])
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
168 break;
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
169 if (j == mlast) {
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
170 /* got a match! */
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
171 if (mode != FAST_COUNT)
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
172 return i;
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
173 count++;
58289
5ca1948a8fd6 Merged revisions 77461 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58095
diff changeset
174 if (count == maxcount)
5ca1948a8fd6 Merged revisions 77461 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58095
diff changeset
175 return maxcount;
58095
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
176 i = i + mlast;
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
177 continue;
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
178 }
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
179 /* 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
180 if (!STRINGLIB_BLOOM(mask, s[i+m]))
58095
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
181 i = i + m;
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
182 else
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
183 i = i + skip;
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
184 } else {
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
185 /* 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
186 if (!STRINGLIB_BLOOM(mask, s[i+m]))
58095
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
187 i = i + m;
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
188 }
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
189 }
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
190 } else { /* FAST_RSEARCH */
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
191
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
192 /* create compressed boyer-moore delta 1 table */
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
193
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
194 /* process pattern[0] outside the loop */
58298
e5e55ffe9f73 Merged revisions 77469-77470 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58289
diff changeset
195 STRINGLIB_BLOOM_ADD(mask, p[0]);
58095
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
196 /* process pattern[:0:-1] */
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
197 for (i = mlast; i > 0; i--) {
58298
e5e55ffe9f73 Merged revisions 77469-77470 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 58289
diff changeset
198 STRINGLIB_BLOOM_ADD(mask, p[i]);
58095
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
199 if (p[i] == p[0])
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
200 skip = i - 1;
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
201 }
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
202
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
203 for (i = w; i >= 0; i--) {
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
204 if (s[i] == p[0]) {
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
205 /* candidate match */
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
206 for (j = mlast; j > 0; j--)
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
207 if (s[i+j] != p[j])
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
208 break;
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
209 if (j == 0)
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
210 /* 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
211 return i;
58095
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
212 /* 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
213 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
214 i = i - m;
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
215 else
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
216 i = i - skip;
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
217 } else {
a1035cb4a925 Merged revisions 77241 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 50986
diff changeset
218 /* 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
219 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
220 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
221 }
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
222 }
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
223 }
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
224
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
225 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
226 return -1;
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
227 return count;
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
228 }
29ae5e0fc348 Much-needed merge (using svnmerge.py this time) of trunk changes into p3yk.
Thomas Wouters <thomas@python.org>
parents:
diff changeset
229