Hash :
9411c5e4
Author :
Date :
2023-03-27T15:41:30
wcsstr: Ensure worst-case linear execution time. * lib/wchar.in.h (wcsstr): Consider REPLACE_WCSSTR. * lib/wcs-two-way.h: New file, based on lib/str-two-way.h. * lib/wcsstr-impl.h: If requested, use the two-way algorithm. New code based on lib/strstr.c. * m4/wcsstr.m4 (gl_FUNC_WCSSTR_SIMPLE): Renamed from gl_FUNC_WCSSTR. (gl_FUNC_WCSSTR): New macro, based on gl_FUNC_STRSTR in m4/strstr.m4. * m4/wchar_h.m4 (gl_WCHAR_H_DEFAULTS): Initialize REPLACE_WCSSTR. * modules/wchar (Makefile.am): Substitute REPLACE_WCSSTR. * modules/wcsstr-simple: New file, based on modules/wcsstr. * modules/wcsstr (Description): Document that this module now provides an efficient implementation. (Files): Add lib/wcs-two-way.h. (Depends-on): Depend on wcsstr-simple and the dependencies of the two-way implementation. (configure.ac): Use AC_LIBOBJ instead of a conditional. Don't invoke gl_WCHAR_MODULE_INDICATOR. (Makefile.am): Don't augment lib_SOURCES. * tests/test-wcsstr.c: New file, based on tests/test-strstr.c. * modules/wcsstr-tests: New file, based on modules/strstr-tests. * doc/posix-functions/wcsstr.texi: Mention the worst-case complexity. Mention the new 'wcsstr-simple' module. * doc/posix-functions/strstr.texi: Fix typo.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73
# wcsstr.m4 serial 3
dnl Copyright (C) 2011-2023 Free Software Foundation, Inc.
dnl This file is free software; the Free Software Foundation
dnl gives unlimited permission to copy and/or distribute it,
dnl with or without modifications, as long as this notice is preserved.
dnl Check that wcsstr exists and works.
AC_DEFUN([gl_FUNC_WCSSTR_SIMPLE],
[
AC_REQUIRE([gl_WCHAR_H_DEFAULTS])
AC_CHECK_FUNCS_ONCE([wcsstr])
if test $ac_cv_func_wcsstr = no; then
HAVE_WCSSTR=0
fi
])
dnl Additionally, check that wcsstr is efficient.
AC_DEFUN([gl_FUNC_WCSSTR],
[
AC_REQUIRE([gl_FUNC_WCSSTR_SIMPLE])
if test $HAVE_WCSSTR = 1; then
AC_CACHE_CHECK([whether wcsstr works in linear time],
[gl_cv_func_wcsstr_linear],
[AC_RUN_IFELSE([AC_LANG_PROGRAM([[
#include <signal.h> /* for signal */
#include <wchar.h> /* for wcsstr */
#include <stdlib.h> /* for malloc */
#include <unistd.h> /* for alarm */
static void quit (int sig) { _exit (sig + 128); }
]], [[
int result = 0;
size_t m = 1000000;
wchar_t *haystack = (wchar_t *) malloc ((2 * m + 2) * sizeof (wchar_t));
wchar_t *needle = (wchar_t *) malloc ((m + 2) * sizeof (wchar_t));
/* Failure to compile this test due to missing alarm is okay,
since all such platforms (mingw) also have quadratic strstr. */
signal (SIGALRM, quit);
alarm (5);
/* Check for quadratic performance. */
if (haystack && needle)
{
size_t i;
for (i = 0; i < 2 * m; i++)
haystack[i] = L'A';
haystack[2 * m] = L'B';
haystack[2 * m + 1] = 0;
for (i = 0; i < m; i++)
needle[i] = L'A';
needle[m] = L'B';
needle[m + 1] = 0;
if (!wcsstr (haystack, needle))
result |= 1;
}
/* Free allocated memory, in case some sanitizer is watching. */
free (haystack);
free (needle);
return result;
]])],
[gl_cv_func_wcsstr_linear=yes], [gl_cv_func_wcsstr_linear=no],
[gl_cv_func_wcsstr_linear="$gl_cross_guess_normal"])
])
case "$gl_cv_func_wcsstr_linear" in
*yes) ;;
*)
REPLACE_WCSSTR=1
;;
esac
fi
if test $HAVE_WCSSTR = 0 || test $REPLACE_WCSSTR = 1; then
AC_DEFINE([NEED_LINEAR_WCSSTR], [1],
[Define to 1 to get a worst-case linear time implementation of wcsstr.])
fi
])