Re: glibc strstr is no longer quadratic

[Bruno Haible]

Eric Blake wrote:
> http://sourceware.org/bugzilla/show_bug.cgi?id=5514 was finally closed, so
> the next release of glibc will no longer have a quadratic strstr/memmem.

Congratulations! I'm updating the guesses for cross-compiles.

2008-05-15  Bruno Haible  <address@hidden>

        * m4/memmem.m4 (gl_FUNC_MEMMEM): When cross-compiling, assume a fast
        implementation in glibc >= 2.9.
        * m4/strstr.m4 (gl_FUNC_STRSTR): Likewise.
        * m4/strcasestr.m4 (gl_FUNC_STRCASESTR): Likewise.

*** m4/memmem.m4.orig   2008-05-15 23:26:05.000000000 +0200
--- m4/memmem.m4        2008-05-15 23:16:36.000000000 +0200
***************
*** 1,4 ****
! # memmem.m4 serial 10
  dnl Copyright (C) 2002, 2003, 2004, 2007, 2008 Free Software Foundation, Inc.
  dnl This file is free software; the Free Software Foundation
  dnl gives unlimited permission to copy and/or distribute it,
--- 1,4 ----
! # memmem.m4 serial 11
  dnl Copyright (C) 2002, 2003, 2004, 2007, 2008 Free Software Foundation, Inc.
  dnl This file is free software; the Free Software Foundation
  dnl gives unlimited permission to copy and/or distribute it,
***************
*** 49,57 ****
      /* Check for empty needle behavior.  */
      return !result || !memmem ("a", 1, 0, 0);]])],
        [gl_cv_func_memmem_works=yes], [gl_cv_func_memmem_works=no],
!       [dnl pessimistically assume the worst, since even glibc 2.6.1
!        dnl has quadratic complexity in its memmem
!        gl_cv_func_memmem_works="guessing no"])])
      if test "$gl_cv_func_memmem_works" != yes; then
        REPLACE_MEMMEM=1
        AC_LIBOBJ([memmem])
--- 49,69 ----
      /* Check for empty needle behavior.  */
      return !result || !memmem ("a", 1, 0, 0);]])],
        [gl_cv_func_memmem_works=yes], [gl_cv_func_memmem_works=no],
!       [dnl Only glibc >= 2.9 is known to have a memmem that works in
!        dnl linear time.
!        AC_EGREP_CPP([Lucky GNU user],
!          [
! #include <features.h>
! #ifdef __GNU_LIBRARY__
!  #if (__GLIBC__ == 2 && __GLIBC_MINOR__ >= 9) || (__GLIBC__ > 2)
!   Lucky GNU user
!  #endif
! #endif
!          ],
!          [gl_cv_func_memmem_works=yes],
!          [gl_cv_func_memmem_works="guessing no"])
!       ])
!       ])
      if test "$gl_cv_func_memmem_works" != yes; then
        REPLACE_MEMMEM=1
        AC_LIBOBJ([memmem])
*** m4/strcasestr.m4.orig       2008-05-15 23:26:05.000000000 +0200
--- m4/strcasestr.m4    2008-05-15 23:21:17.000000000 +0200
***************
*** 1,4 ****
! # strcasestr.m4 serial 9
  dnl Copyright (C) 2005, 2007, 2008 Free Software Foundation, Inc.
  dnl This file is free software; the Free Software Foundation
  dnl gives unlimited permission to copy and/or distribute it,
--- 1,4 ----
! # strcasestr.m4 serial 10
  dnl Copyright (C) 2005, 2007, 2008 Free Software Foundation, Inc.
  dnl This file is free software; the Free Software Foundation
  dnl gives unlimited permission to copy and/or distribute it,
***************
*** 48,57 ****
        result = strcasestr (haystack, needle);
        }
      return !result;]])],
!       [gl_cv_func_strcasestr_linear=yes], [gl_cv_func_strcasestr_linear=no],
!       [dnl pessimistically assume the worst, since even glibc 2.6.1
!        dnl has quadratic complexity in its strcasestr
!        gl_cv_func_strcasestr_linear="guessing no"])])
      if test "$gl_cv_func_strcasestr_linear" != yes; then
        REPLACE_STRCASESTR=1
        AC_LIBOBJ([strcasestr])
--- 48,69 ----
        result = strcasestr (haystack, needle);
        }
      return !result;]])],
!       [gl_cv_func_strcasestr_linear=yes], [gl_cv_func_strcasestr_linear=no],
!       [dnl Only glibc >= 2.9 is known to have an strcasestr that works in
!        dnl linear time.
!        AC_EGREP_CPP([Lucky GNU user],
!          [
! #include <features.h>
! #ifdef __GNU_LIBRARY__
!  #if (__GLIBC__ == 2 && __GLIBC_MINOR__ >= 9) || (__GLIBC__ > 2)
!   Lucky GNU user
!  #endif
! #endif
!          ],
!          [gl_cv_func_strcasestr_linear=yes],
!          [gl_cv_func_strcasestr_linear="guessing no"])
!       ])
!       ])
      if test "$gl_cv_func_strcasestr_linear" != yes; then
        REPLACE_STRCASESTR=1
        AC_LIBOBJ([strcasestr])
*** m4/strstr.m4.orig   2008-05-15 23:26:05.000000000 +0200
--- m4/strstr.m4        2008-05-15 23:20:21.000000000 +0200
***************
*** 1,4 ****
! # strstr.m4 serial 2
  dnl Copyright (C) 2008 Free Software Foundation, Inc.
  dnl This file is free software; the Free Software Foundation
  dnl gives unlimited permission to copy and/or distribute it,
--- 1,4 ----
! # strstr.m4 serial 3
  dnl Copyright (C) 2008 Free Software Foundation, Inc.
  dnl This file is free software; the Free Software Foundation
  dnl gives unlimited permission to copy and/or distribute it,
***************
*** 34,42 ****
        }
      return !result;]])],
        [gl_cv_func_strstr_linear=yes], [gl_cv_func_strstr_linear=no],
!       [dnl pessimistically assume the worst, since even glibc 2.6.1
!        dnl has quadratic complexity in its strstr
!        gl_cv_func_strstr_linear="guessing no"])])
    if test "$gl_cv_func_strstr_linear" != yes; then
      REPLACE_STRSTR=1
      AC_LIBOBJ([strstr])
--- 34,54 ----
        }
      return !result;]])],
        [gl_cv_func_strstr_linear=yes], [gl_cv_func_strstr_linear=no],
!       [dnl Only glibc >= 2.9 is known to have an strstr that works in
!        dnl linear time.
!        AC_EGREP_CPP([Lucky GNU user],
!        [
! #include <features.h>
! #ifdef __GNU_LIBRARY__
!  #if (__GLIBC__ == 2 && __GLIBC_MINOR__ >= 9) || (__GLIBC__ > 2)
!   Lucky GNU user
!  #endif
! #endif
!        ],
!        [gl_cv_func_strstr_linear=yes],
!        [gl_cv_func_strstr_linear="guessing no"])
!       ])
!     ])
    if test "$gl_cv_func_strstr_linear" != yes; then
      REPLACE_STRSTR=1
      AC_LIBOBJ([strstr])