From da2ecaf3349d564ef0392183d86270eea5cdb439 Mon Sep 17 00:00:00 2001 From: Antoine Pitrou Date: Sat, 2 Jan 2010 21:40:36 +0000 Subject: Merged revisions 77241 via svnmerge from svn+ssh://pythondev@svn.python.org/python/trunk ........ r77241 | antoine.pitrou | 2010-01-02 22:12:58 +0100 (sam., 02 janv. 2010) | 4 lines Issue #7462: Implement the stringlib fast search algorithm for the `rfind`, `rindex`, `rsplit` and `rpartition` methods. Patch by Florent Xicluna. ........ --- Lib/collections.py | 2 + Lib/test/string_tests.py | 24 +++++++++ Misc/NEWS | 3 ++ Objects/bytearrayobject.c | 39 ++++---------- Objects/stringlib/README.txt | 4 -- Objects/stringlib/fastsearch.h | 112 +++++++++++++++++++++++++++------------- Objects/stringlib/find.h | 32 +++++------- Objects/stringlib/partition.h | 12 ++--- Objects/stringlib/stringdefs.h | 1 - Objects/stringlib/unicodedefs.h | 19 ------- 10 files changed, 132 insertions(+), 116 deletions(-) diff --git a/Lib/collections.py b/Lib/collections.py index f255919..3e01054 100644 --- a/Lib/collections.py +++ b/Lib/collections.py @@ -767,6 +767,8 @@ class UserString(Sequence): new = new.data return self.__class__(self.data.replace(old, new, maxsplit)) def rfind(self, sub, start=0, end=_sys.maxsize): + if isinstance(sub, UserString): + sub = sub.data return self.data.rfind(sub, start, end) def rindex(self, sub, start=0, end=_sys.maxsize): return self.data.rindex(sub, start, end) diff --git a/Lib/test/string_tests.py b/Lib/test/string_tests.py index 85e52f3..ea49e38 100644 --- a/Lib/test/string_tests.py +++ b/Lib/test/string_tests.py @@ -216,6 +216,30 @@ class BaseTest(unittest.TestCase): self.checkraises(TypeError, 'hello', 'rfind') self.checkraises(TypeError, 'hello', 'rfind', 42) + # For a variety of combinations, + # verify that str.rfind() matches __contains__ + # and that the found substring is really at that location + charset = ['', 'a', 'b', 'c'] + digits = 5 + base = len(charset) + teststrings = set() + for i in range(base ** digits): + entry = [] + for j in range(digits): + i, m = divmod(i, base) + entry.append(charset[m]) + teststrings.add(''.join(entry)) + teststrings = [self.fixtype(ts) for ts in teststrings] + for i in teststrings: + for j in teststrings: + loc = i.rfind(j) + r1 = (loc != -1) + r2 = j in i + if r1 != r2: + self.assertEqual(r1, r2) + if loc != -1: + self.assertEqual(i[loc:loc+len(j)], j) + def test_index(self): self.checkequal(0, 'abcdefghiabc', 'index', '') self.checkequal(3, 'abcdefghiabc', 'index', 'def') diff --git a/Misc/NEWS b/Misc/NEWS index d564c50..81d01e4 100644 --- a/Misc/NEWS +++ b/Misc/NEWS @@ -12,6 +12,9 @@ What's New in Python 3.2 Alpha 1? Core and Builtins ----------------- +- Issue #7462: Implement the stringlib fast search algorithm for the `rfind`, + `rindex`, `rsplit` and `rpartition` methods. Patch by Florent Xicluna. + - Issue #7604: Deleting an unset slotted attribute did not raise an AttributeError. diff --git a/Objects/bytearrayobject.c b/Objects/bytearrayobject.c index c09ccde..827c47b 100644 --- a/Objects/bytearrayobject.c +++ b/Objects/bytearrayobject.c @@ -1035,7 +1035,6 @@ bytearray_dealloc(PyByteArrayObject *self) /* Methods */ #define STRINGLIB_CHAR char -#define STRINGLIB_CMP memcmp #define STRINGLIB_LEN PyByteArray_GET_SIZE #define STRINGLIB_STR PyByteArray_AS_STRING #define STRINGLIB_NEW PyByteArray_FromStringAndSize @@ -2214,14 +2213,11 @@ If maxsplit is given, at most maxsplit splits are done."); static PyObject * bytearray_split(PyByteArrayObject *self, PyObject *args) { - Py_ssize_t len = PyByteArray_GET_SIZE(self), n, i, j; + Py_ssize_t len = PyByteArray_GET_SIZE(self), n, i, j, pos; Py_ssize_t maxsplit = -1, count = 0; const char *s = PyByteArray_AS_STRING(self), *sub; PyObject *list, *str, *subobj = Py_None; Py_buffer vsub; -#ifdef USE_FAST - Py_ssize_t pos; -#endif if (!PyArg_ParseTuple(args, "|On:split", &subobj, &maxsplit)) return NULL; @@ -2253,7 +2249,6 @@ bytearray_split(PyByteArrayObject *self, PyObject *args) return NULL; } -#ifdef USE_FAST i = j = 0; while (maxsplit-- > 0) { pos = fastsearch(s+i, len-i, sub, n, FAST_SEARCH); @@ -2263,18 +2258,6 @@ bytearray_split(PyByteArrayObject *self, PyObject *args) SPLIT_ADD(s, i, j); i = j + n; } -#else - i = j = 0; - while ((j+n <= len) && (maxsplit-- > 0)) { - for (; j+n <= len; j++) { - if (Py_STRING_MATCH(s, j, sub, n)) { - SPLIT_ADD(s, i, j); - i = j = j + n; - break; - } - } - } -#endif SPLIT_ADD(s, i, len); FIX_PREALLOC_SIZE(list); PyBuffer_Release(&vsub); @@ -2452,7 +2435,7 @@ If maxsplit is given, at most maxsplit splits are done."); static PyObject * bytearray_rsplit(PyByteArrayObject *self, PyObject *args) { - Py_ssize_t len = PyByteArray_GET_SIZE(self), n, i, j; + Py_ssize_t len = PyByteArray_GET_SIZE(self), n, j, pos; Py_ssize_t maxsplit = -1, count = 0; const char *s = PyByteArray_AS_STRING(self), *sub; PyObject *list, *str, *subobj = Py_None; @@ -2489,17 +2472,13 @@ bytearray_rsplit(PyByteArrayObject *self, PyObject *args) } j = len; - i = j - n; - - while ( (i >= 0) && (maxsplit-- > 0) ) { - for (; i>=0; i--) { - if (Py_STRING_MATCH(s, i, sub, n)) { - SPLIT_ADD(s, i + n, j); - j = i; - i -= n; - break; - } - } + + while (maxsplit-- > 0) { + pos = fastsearch(s, j, sub, n, FAST_RSEARCH); + if (pos < 0) + break; + SPLIT_ADD(s, pos + n, j); + j = pos; } SPLIT_ADD(s, 0, j); FIX_PREALLOC_SIZE(list); diff --git a/Objects/stringlib/README.txt b/Objects/stringlib/README.txt index aec3441..c884ec3 100644 --- a/Objects/stringlib/README.txt +++ b/Objects/stringlib/README.txt @@ -15,10 +15,6 @@ STRINGLIB_EMPTY a PyObject representing the empty string -int STRINGLIB_CMP(STRINGLIB_CHAR*, STRINGLIB_CHAR*, Py_ssize_t) - - compares two strings. returns 0 if they match, and non-zero if not. - Py_ssize_t STRINGLIB_LEN(PyObject*) returns the length of the given string object (which must be of the diff --git a/Objects/stringlib/fastsearch.h b/Objects/stringlib/fastsearch.h index 23bccfb..7b9dd47 100644 --- a/Objects/stringlib/fastsearch.h +++ b/Objects/stringlib/fastsearch.h @@ -5,7 +5,7 @@ /* fast search/count implementation, based on a mix between boyer- moore and horspool, with a few more bells and whistles on the top. - for some more background, see: http://effbot.org/stringlib.htm */ + for some more background, see: http://effbot.org/zone/stringlib.htm */ /* note: fastsearch may access s[n], which isn't a problem when using Python's ordinary string types, but may cause problems if you're @@ -16,6 +16,7 @@ #define FAST_COUNT 0 #define FAST_SEARCH 1 +#define FAST_RSEARCH 2 Py_LOCAL_INLINE(Py_ssize_t) fastsearch(const STRINGLIB_CHAR* s, Py_ssize_t n, @@ -41,51 +42,92 @@ fastsearch(const STRINGLIB_CHAR* s, Py_ssize_t n, if (s[i] == p[0]) count++; return count; - } else { + } else if (mode == FAST_SEARCH) { for (i = 0; i < n; i++) if (s[i] == p[0]) return i; + } else { /* FAST_RSEARCH */ + for (i = n - 1; i > -1; i--) + if (s[i] == p[0]) + return i; } return -1; } mlast = m - 1; - - /* create compressed boyer-moore delta 1 table */ skip = mlast - 1; - /* process pattern[:-1] */ - for (mask = i = 0; i < mlast; i++) { - mask |= (1 << (p[i] & 0x1F)); - if (p[i] == p[mlast]) - skip = mlast - i - 1; - } - /* process pattern[-1] outside the loop */ - mask |= (1 << (p[mlast] & 0x1F)); - - for (i = 0; i <= w; i++) { - /* note: using mlast in the skip path slows things down on x86 */ - if (s[i+m-1] == p[m-1]) { - /* candidate match */ - for (j = 0; j < mlast; j++) - if (s[i+j] != p[j]) - break; - if (j == mlast) { - /* got a match! */ - if (mode != FAST_COUNT) + + if (mode != FAST_RSEARCH) { + + /* create compressed boyer-moore delta 1 table */ + + /* process pattern[:-1] */ + for (mask = i = 0; i < mlast; i++) { + mask |= (1 << (p[i] & 0x1F)); + if (p[i] == p[mlast]) + skip = mlast - i - 1; + } + /* process pattern[-1] outside the loop */ + mask |= (1 << (p[mlast] & 0x1F)); + + for (i = 0; i <= w; i++) { + /* note: using mlast in the skip path slows things down on x86 */ + if (s[i+m-1] == p[m-1]) { + /* candidate match */ + for (j = 0; j < mlast; j++) + if (s[i+j] != p[j]) + break; + if (j == mlast) { + /* got a match! */ + if (mode != FAST_COUNT) + return i; + count++; + i = i + mlast; + continue; + } + /* miss: check if next character is part of pattern */ + if (!(mask & (1 << (s[i+m] & 0x1F)))) + i = i + m; + else + i = i + skip; + } else { + /* skip: check if next character is part of pattern */ + if (!(mask & (1 << (s[i+m] & 0x1F)))) + i = i + m; + } + } + } else { /* FAST_RSEARCH */ + + /* create compressed boyer-moore delta 1 table */ + + /* process pattern[0] outside the loop */ + mask = (1 << (p[0] & 0x1F)); + /* process pattern[:0:-1] */ + for (i = mlast; i > 0; i--) { + mask |= (1 << (p[i] & 0x1F)); + if (p[i] == p[0]) + skip = i - 1; + } + + for (i = w; i >= 0; i--) { + if (s[i] == p[0]) { + /* candidate match */ + for (j = mlast; j > 0; j--) + if (s[i+j] != p[j]) + break; + if (j == 0) + /* got a match! */ return i; - count++; - i = i + mlast; - continue; + /* miss: check if previous character is part of pattern */ + if (!(mask & (1 << (s[i-1] & 0x1F)))) + i = i - m; + else + i = i - skip; + } else { + /* skip: check if previous character is part of pattern */ + if (!(mask & (1 << (s[i-1] & 0x1F)))) + i = i - m; } - /* miss: check if next character is part of pattern */ - if (!(mask & (1 << (s[i+m] & 0x1F)))) - i = i + m; - else - i = i + skip; - } else { - /* skip: check if next character is part of pattern */ - if (!(mask & (1 << (s[i+m] & 0x1F)))) - i = i + m; } } diff --git a/Objects/stringlib/find.h b/Objects/stringlib/find.h index bf06530..bf27d6a 100644 --- a/Objects/stringlib/find.h +++ b/Objects/stringlib/find.h @@ -32,20 +32,19 @@ stringlib_rfind(const STRINGLIB_CHAR* str, Py_ssize_t str_len, const STRINGLIB_CHAR* sub, Py_ssize_t sub_len, Py_ssize_t offset) { - /* XXX - create reversefastsearch helper! */ - if (sub_len == 0) { - if (str_len < 0) - return -1; - return str_len + offset; - } else { - Py_ssize_t j, pos = -1; - for (j = str_len - sub_len; j >= 0; --j) - if (STRINGLIB_CMP(str+j, sub, sub_len) == 0) { - pos = j + offset; - break; - } - return pos; - } + Py_ssize_t pos; + + if (str_len < 0) + return -1; + if (sub_len == 0) + return str_len + offset; + + pos = fastsearch(str, str_len, sub, sub_len, FAST_RSEARCH); + + if (pos >= 0) + pos += offset; + + return pos; } Py_LOCAL_INLINE(Py_ssize_t) @@ -64,10 +63,7 @@ stringlib_find_slice(const STRINGLIB_CHAR* str, Py_ssize_t str_len, if (end < 0) end = 0; - return stringlib_find( - str + start, end - start, - sub, sub_len, start - ); + return stringlib_find(str + start, end - start, sub, sub_len, start); } Py_LOCAL_INLINE(Py_ssize_t) diff --git a/Objects/stringlib/partition.h b/Objects/stringlib/partition.h index 105ba31..2f26212 100644 --- a/Objects/stringlib/partition.h +++ b/Objects/stringlib/partition.h @@ -58,7 +58,7 @@ stringlib_rpartition( ) { PyObject* out; - Py_ssize_t pos, j; + Py_ssize_t pos; if (sep_len == 0) { PyErr_SetString(PyExc_ValueError, "empty separator"); @@ -69,20 +69,14 @@ stringlib_rpartition( if (!out) return NULL; - /* XXX - create reversefastsearch helper! */ - pos = -1; - for (j = str_len - sep_len; j >= 0; --j) - if (STRINGLIB_CMP(str+j, sep, sep_len) == 0) { - pos = j; - break; - } + pos = fastsearch(str, str_len, sep, sep_len, FAST_RSEARCH); if (pos < 0) { Py_INCREF(STRINGLIB_EMPTY); PyTuple_SET_ITEM(out, 0, (PyObject*) STRINGLIB_EMPTY); Py_INCREF(STRINGLIB_EMPTY); PyTuple_SET_ITEM(out, 1, (PyObject*) STRINGLIB_EMPTY); - Py_INCREF(str_obj); + Py_INCREF(str_obj); PyTuple_SET_ITEM(out, 2, (PyObject*) str_obj); return out; } diff --git a/Objects/stringlib/stringdefs.h b/Objects/stringlib/stringdefs.h index f85357f..8a650fe 100644 --- a/Objects/stringlib/stringdefs.h +++ b/Objects/stringlib/stringdefs.h @@ -22,7 +22,6 @@ #define STRINGLIB_RESIZE _PyBytes_Resize #define STRINGLIB_CHECK PyBytes_Check #define STRINGLIB_CHECK_EXACT PyBytes_CheckExact -#define STRINGLIB_CMP memcmp #define STRINGLIB_TOSTR PyObject_Str #define STRINGLIB_GROUPING _PyBytes_InsertThousandsGrouping #define STRINGLIB_GROUPING_LOCALE _PyBytes_InsertThousandsGroupingLocale diff --git a/Objects/stringlib/unicodedefs.h b/Objects/stringlib/unicodedefs.h index c23c392..a4d2144 100644 --- a/Objects/stringlib/unicodedefs.h +++ b/Objects/stringlib/unicodedefs.h @@ -35,23 +35,4 @@ #define STRINGLIB_WANT_CONTAINS_OBJ 1 -/* STRINGLIB_CMP was defined as: - -Py_LOCAL_INLINE(int) -STRINGLIB_CMP(const Py_UNICODE* str, const Py_UNICODE* other, Py_ssize_t len) -{ - if (str[0] != other[0]) - return 1; - return memcmp((void*) str, (void*) other, len * sizeof(Py_UNICODE)); -} - -but unfortunately that gives a error if the function isn't used in a file that -includes this file. So, reluctantly convert it to a macro instead. */ - -#define STRINGLIB_CMP(str, other, len) \ - (((str)[0] != (other)[0]) ? \ - 1 : \ - memcmp((void*) (str), (void*) (other), (len) * sizeof(Py_UNICODE))) - - #endif /* !STRINGLIB_UNICODEDEFS_H */ -- cgit v0.12