From 4a3872f5902158b6a0d5f9bac02620da63639d90 Mon Sep 17 00:00:00 2001 From: Bruno Haible Date: Sun, 2 Apr 2023 16:07:36 +0200 Subject: [PATCH] unistr/u{16,32}-strstr: Use two-way algorithm (no memory allocation). * lib/wcs-two-way.h: Use UNIT instead of wchar_t. Don't undefine RETURN_TYPE. * lib/wcsstr-impl.h: Move the non-linear implementation away. Use UNIT instead of wchar_t, RETURN_TYPE instead of 'wchar_t *', FUNC instead of wcsstr. (AVAILABLE): Use MEMCHR0 instead of wmemchr. (FUNC): Use STRCHR instead of wcschr. * lib/wcsstr.c: Moved the non-linear implementation to here. (FUNC, UNIT, RETURN_TYPE, MEMCHR0, STRCHR): New macros. * lib/unistr/u16-strstr.c: Don't include malloca.h, str-kmp.h, u-strstr.h. Instead, include wcsstr-impl.h. * lib/unistr/u32-strstr.c: Likewise. * modules/unistr/u16-strstr (Files): Remove u-strstr.h, str-kmp.h. Add wcsstr-impl.h, wcs-two-way.h. (Depends-on): Remove u16-strmbtouc, u16-strlen, u16-strnlen, malloca. Add u16-chr, u16-cmp. * modules/unistr/u32-strstr (Files): Remove u-strstr.h, str-kmp.h. Add wcsstr-impl.h, wcs-two-way.h. (Depends-on): Remove u32-strlen, u32-strnlen, malloca. Add u32-chr, u32-cmp. --- ChangeLog | 24 +++++++++++++ lib/unistr/u16-strstr.c | 18 +++------- lib/unistr/u32-strstr.c | 15 +++----- lib/wcs-two-way.h | 23 ++++++------- lib/wcsstr-impl.h | 72 +++++++-------------------------------- lib/wcsstr.c | 54 ++++++++++++++++++++++++++++- modules/unistr/u16-strstr | 10 +++--- modules/unistr/u32-strstr | 9 +++-- 8 files changed, 119 insertions(+), 106 deletions(-) diff --git a/ChangeLog b/ChangeLog index ddc568db03..f933d1e94d 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,27 @@ +2023-04-02 Bruno Haible + + unistr/u{16,32}-strstr: Use two-way algorithm (no memory allocation). + * lib/wcs-two-way.h: Use UNIT instead of wchar_t. Don't undefine + RETURN_TYPE. + * lib/wcsstr-impl.h: Move the non-linear implementation away. Use UNIT + instead of wchar_t, RETURN_TYPE instead of 'wchar_t *', FUNC instead of + wcsstr. + (AVAILABLE): Use MEMCHR0 instead of wmemchr. + (FUNC): Use STRCHR instead of wcschr. + * lib/wcsstr.c: Moved the non-linear implementation to here. + (FUNC, UNIT, RETURN_TYPE, MEMCHR0, STRCHR): New macros. + * lib/unistr/u16-strstr.c: Don't include malloca.h, str-kmp.h, + u-strstr.h. Instead, include wcsstr-impl.h. + * lib/unistr/u32-strstr.c: Likewise. + * modules/unistr/u16-strstr (Files): Remove u-strstr.h, str-kmp.h. Add + wcsstr-impl.h, wcs-two-way.h. + (Depends-on): Remove u16-strmbtouc, u16-strlen, u16-strnlen, malloca. + Add u16-chr, u16-cmp. + * modules/unistr/u32-strstr (Files): Remove u-strstr.h, str-kmp.h. Add + wcsstr-impl.h, wcs-two-way.h. + (Depends-on): Remove u32-strlen, u32-strnlen, malloca. Add u32-chr, + u32-cmp. + 2023-04-02 Bruno Haible unistr/u*strstr tests: Add more tests. diff --git a/lib/unistr/u16-strstr.c b/lib/unistr/u16-strstr.c index 5a21a1f63d..2be6cd5744 100644 --- a/lib/unistr/u16-strstr.c +++ b/lib/unistr/u16-strstr.c @@ -28,18 +28,10 @@ /* Specification. */ #include "unistr.h" -#include "malloca.h" - -/* FIXME: Maybe walking the string via u16_mblen is a win? */ - #define UNIT uint16_t - -#define CANON_ELEMENT(c) c -#include "str-kmp.h" - #define FUNC u16_strstr -#define U_STRCHR u16_strchr -#define U_STRMBTOUC u16_strmbtouc -#define U_STRLEN u16_strlen -#define U_STRNLEN u16_strnlen -#include "u-strstr.h" +#define RETURN_TYPE uint16_t * +#define MEMCHR0(s, n) u16_chr (s, n, 0) +#define STRCHR u16_strchr +#define CMP_FUNC u16_cmp +#include "wcsstr-impl.h" diff --git a/lib/unistr/u32-strstr.c b/lib/unistr/u32-strstr.c index 261d93afb3..62f04d0cdf 100644 --- a/lib/unistr/u32-strstr.c +++ b/lib/unistr/u32-strstr.c @@ -28,15 +28,10 @@ /* Specification. */ #include "unistr.h" -#include "malloca.h" - #define UNIT uint32_t - -#define CANON_ELEMENT(c) c -#include "str-kmp.h" - #define FUNC u32_strstr -#define U_STRCHR u32_strchr -#define U_STRLEN u32_strlen -#define U_STRNLEN u32_strnlen -#include "u-strstr.h" +#define RETURN_TYPE uint32_t * +#define MEMCHR0(s, n) u32_chr (s, n, 0) +#define STRCHR u32_strchr +#define CMP_FUNC u32_cmp +#include "wcsstr-impl.h" diff --git a/lib/wcs-two-way.h b/lib/wcs-two-way.h index 0879026f2b..b160f90c4a 100644 --- a/lib/wcs-two-way.h +++ b/lib/wcs-two-way.h @@ -18,23 +18,23 @@ /* Before including this file, you need to include and , and define: + UNIT The element type of the needle and haystack. RETURN_TYPE A macro that expands to the return type. AVAILABLE(h, h_l, j, n_l) A macro that returns nonzero if there are at least N_L characters left starting at H[J]. - H is 'wchar_t *', H_L, J, and N_L - are 'size_t'; H_L is an lvalue. For - NUL-terminated searches, H_L can be - modified each iteration to avoid having - to compute the end of H up front. + H is 'UNIT *', H_L, J, and N_L are 'size_t'; + H_L is an lvalue. For NUL-terminated searches, + H_L can be modified each iteration to avoid + having to compute the end of H up front. For case-insensitivity, you may optionally define: CMP_FUNC(p1, p2, l) A macro that returns 0 iff the first L characters of P1 and P2 are equal. CANON_ELEMENT(c) A macro that canonicalizes an element right after it has been fetched from one of the two strings. - The argument is a 'wchar_t'; the result - must be a 'wchar_t' as well. + The argument is a 'UNIT'; the result must be a + 'UNIT' as well. This file undefines the macros documented above, and defines LONG_NEEDLE_THRESHOLD. @@ -88,7 +88,7 @@ suffixes are determined by lexicographic comparison while tracking periodicity. */ static size_t -critical_factorization (const wchar_t *needle, size_t needle_len, +critical_factorization (const UNIT *needle, size_t needle_len, size_t *period) { /* Index of last character of left half, or SIZE_MAX. */ @@ -96,7 +96,7 @@ critical_factorization (const wchar_t *needle, size_t needle_len, size_t j; /* Index into NEEDLE for current candidate suffix. */ size_t k; /* Offset into current period. */ size_t p; /* Intermediate period. */ - wchar_t a, b; /* Current comparison characters. */ + UNIT a, b; /* Current comparison characters. */ /* Special case NEEDLE_LEN of 1 or 2 (all callers already filtered out 0-length needles. */ @@ -215,8 +215,8 @@ critical_factorization (const wchar_t *needle, size_t needle_len, If AVAILABLE modifies HAYSTACK_LEN (as in strstr), then at most 3 * HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching. */ static RETURN_TYPE _GL_ATTRIBUTE_PURE -two_way_short_needle (const wchar_t *haystack, size_t haystack_len, - const wchar_t *needle, size_t needle_len) +two_way_short_needle (const UNIT *haystack, size_t haystack_len, + const UNIT *needle, size_t needle_len) { size_t i; /* Index into current character of NEEDLE. */ size_t j; /* Index into current window of HAYSTACK. */ @@ -300,4 +300,3 @@ two_way_short_needle (const wchar_t *haystack, size_t haystack_len, #undef CANON_ELEMENT #undef CMP_FUNC #undef MAX -#undef RETURN_TYPE diff --git a/lib/wcsstr-impl.h b/lib/wcsstr-impl.h index ccd64672b4..f889c26b11 100644 --- a/lib/wcsstr-impl.h +++ b/lib/wcsstr-impl.h @@ -14,23 +14,18 @@ You should have received a copy of the GNU Lesser General Public License along with this program. If not, see . */ -/* Written by Bruno Haible, 1999, and Eric Blake, 2008. */ +/* Written by Eric Blake, 2008. */ -#if NEED_LINEAR_WCSSTR +#define AVAILABLE(h, h_l, j, n_l) \ + (!MEMCHR0 ((h) + (h_l), (j) + (n_l) - (h_l)) \ + && ((h_l) = (j) + (n_l))) +#include "wcs-two-way.h" -/* Use Two-Way algorithm, worst-case O(n+m). */ - -# define RETURN_TYPE wchar_t * -# define AVAILABLE(h, h_l, j, n_l) \ - (!wmemchr ((h) + (h_l), L'\0', (j) + (n_l) - (h_l)) \ - && ((h_l) = (j) + (n_l))) -# include "wcs-two-way.h" - -wchar_t * -wcsstr (const wchar_t *haystack_start, const wchar_t *needle_start) +RETURN_TYPE +FUNC (const UNIT *haystack_start, const UNIT *needle_start) { - const wchar_t *haystack = haystack_start; - const wchar_t *needle = needle_start; + const UNIT *haystack = haystack_start; + const UNIT *needle = needle_start; size_t needle_len; /* Length of NEEDLE. */ size_t haystack_len; /* Known minimum length of HAYSTACK. */ bool ok = true; /* True if NEEDLE is prefix of HAYSTACK. */ @@ -43,14 +38,14 @@ wcsstr (const wchar_t *haystack_start, const wchar_t *needle_start) if (*needle) return NULL; if (ok) - return (wchar_t *) haystack_start; + return (RETURN_TYPE) haystack_start; - /* Reduce the size of haystack using wcschr, since it has a smaller + /* Reduce the size of haystack using STRCHR, since it has a smaller linear coefficient than the Two-Way algorithm. */ needle_len = needle - needle_start; - haystack = wcschr (haystack_start + 1, *needle_start); + haystack = STRCHR (haystack_start + 1, *needle_start); if (!haystack || __builtin_expect (needle_len == 1, 0)) - return (wchar_t *) haystack; + return (RETURN_TYPE) haystack; needle -= needle_len; haystack_len = (haystack > haystack_start + needle_len ? 1 : needle_len + haystack_start - haystack); @@ -59,44 +54,3 @@ wcsstr (const wchar_t *haystack_start, const wchar_t *needle_start) return two_way_short_needle (haystack, haystack_len, needle, needle_len); } - -#else - -/* Use simple implementation, worst-case O(nm). */ - -wchar_t * -wcsstr (const wchar_t *haystack, const wchar_t *needle) -{ - wchar_t n = needle[0]; - - /* Is needle empty? */ - if (n == (wchar_t)'\0') - return (wchar_t *) haystack; - - /* Is needle nearly empty? */ - if (needle[1] == (wchar_t)'\0') - return wcschr (haystack, n); - - /* Search for needle's first character. */ - for (; *haystack != (wchar_t)'\0'; haystack++) - { - if (*haystack == n) - { - /* Compare with needle's remaining characters. */ - const wchar_t *hptr = haystack + 1; - const wchar_t *nptr = needle + 1; - for (;;) - { - if (*hptr != *nptr) - break; - hptr++; nptr++; - if (*nptr == (wchar_t)'\0') - return (wchar_t *) haystack; - } - } - } - - return NULL; -} - -#endif diff --git a/lib/wcsstr.c b/lib/wcsstr.c index 47a947d02e..6c73f2df5f 100644 --- a/lib/wcsstr.c +++ b/lib/wcsstr.c @@ -15,9 +15,61 @@ You should have received a copy of the GNU Lesser General Public License along with this program. If not, see . */ +/* Written by Bruno Haible, 1999. */ + #include /* Specification. */ #include -#include "wcsstr-impl.h" +#if NEED_LINEAR_WCSSTR + +/* Use Two-Way algorithm, worst-case O(n+m). */ + +# define FUNC wcsstr +# define UNIT wchar_t +# define RETURN_TYPE wchar_t * +# define MEMCHR0(s, n) wmemchr (s, 0, n) +# define STRCHR wcschr +# include "wcsstr-impl.h" + +#else + +/* Use simple implementation, worst-case O(nm). */ + +wchar_t * +wcsstr (const wchar_t *haystack, const wchar_t *needle) +{ + wchar_t n = needle[0]; + + /* Is needle empty? */ + if (n == (wchar_t)'\0') + return (wchar_t *) haystack; + + /* Is needle nearly empty? */ + if (needle[1] == (wchar_t)'\0') + return wcschr (haystack, n); + + /* Search for needle's first character. */ + for (; *haystack != (wchar_t)'\0'; haystack++) + { + if (*haystack == n) + { + /* Compare with needle's remaining characters. */ + const wchar_t *hptr = haystack + 1; + const wchar_t *nptr = needle + 1; + for (;;) + { + if (*hptr != *nptr) + break; + hptr++; nptr++; + if (*nptr == (wchar_t)'\0') + return (wchar_t *) haystack; + } + } + } + + return NULL; +} + +#endif diff --git a/modules/unistr/u16-strstr b/modules/unistr/u16-strstr index 501bee5303..1ad2e4eec3 100644 --- a/modules/unistr/u16-strstr +++ b/modules/unistr/u16-strstr @@ -3,17 +3,15 @@ Substring test for UTF-16 strings. Files: lib/unistr/u16-strstr.c -lib/unistr/u-strstr.h -lib/str-kmp.h +lib/wcsstr-impl.h +lib/wcs-two-way.h Depends-on: unistr/base +unistr/u16-chr unistr/u16-strchr -unistr/u16-strmbtouc -unistr/u16-strlen -unistr/u16-strnlen +unistr/u16-cmp stdbool -malloca configure.ac: gl_LIBUNISTRING_MODULE([0.9.4], [unistr/u16-strstr]) diff --git a/modules/unistr/u32-strstr b/modules/unistr/u32-strstr index 1fb2fcf498..64d95434b1 100644 --- a/modules/unistr/u32-strstr +++ b/modules/unistr/u32-strstr @@ -3,16 +3,15 @@ Substring test for UTF-32 strings. Files: lib/unistr/u32-strstr.c -lib/unistr/u-strstr.h -lib/str-kmp.h +lib/wcsstr-impl.h +lib/wcs-two-way.h Depends-on: unistr/base +unistr/u32-chr unistr/u32-strchr -unistr/u32-strlen -unistr/u32-strnlen +unistr/u32-cmp stdbool -malloca configure.ac: gl_LIBUNISTRING_MODULE([0.9.4], [unistr/u32-strstr]) -- 2.39.5