[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: glibc strstr is no longer quadratic
From: |
Bruno Haible |
Subject: |
Re: glibc strstr is no longer quadratic |
Date: |
Thu, 15 May 2008 23:29:23 +0200 |
User-agent: |
KMail/1.5.4 |
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])