kc3-lang/gnulib/m4/wcsstr.m4

• Show log

  Commit

• 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.
  

Download

• m4/wcsstr.m4

• # 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
  ])
  

Download