>From d0d7a45d51609f7a69dbeffbc11c086cfa267bb8 Mon Sep 17 00:00:00 2001 From: =?utf-8?q?P=C3=A1draig=20Brady?= Date: Wed, 23 Jun 2010 00:42:54 +0100 Subject: [PATCH] memmem: rearrange memmem and expand memmem-simple modules Move all functional checks to memmem-simple so that one has a fully functional memmem by using just this module. Restrict the memmem module to performance checks only. Document exactly how the memmem and memmem-simple modules relate to each other. * m4/memmem.m4 (gl_FUNC_MEMMEM_SIMPLE, gl_FUNC_MEMMEM): Move the empty needle check from the memmem module to memmem-simple. Also expand the empty needle check to ensure the correct pointer is returned, not just a non NULL pointer. * doc/glibc-functions/memmem.texi: Rearrange the portability documentation to correlate with the rearranged checks. --- ChangeLog | 14 ++++++++++ doc/glibc-functions/memmem.texi | 13 ++++++--- m4/memmem.m4 | 53 +++++++++++++++++++++++++++++++------- 3 files changed, 66 insertions(+), 14 deletions(-) diff --git a/ChangeLog b/ChangeLog index 182d7b2..ab40f8c 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,17 @@ +2010-06-23 Pádraig Brady + + memmem, memmem-simple: reorganize and expand empty needle check + * m4/memmem.m4 (gl_FUNC_MEMMEM_SIMPLE, gl_FUNC_MEMMEM): Move all + functional checks to memmem-simple so that one has a fully functional + memmem by using just this module. + Restrict the performance only check to the memmem module. + Also expand the empty needle check to ensure the correct + pointer is returned, not just a non NULL pointer. + * doc/glibc-functions/memmem.texi: Rearrange the portability + documentation to correlate with the rearranged checks. + Clarify exactly how the memmem and memmem-simple modules + relate to each other. + 2010-06-22 Eric Blake memmem: slight optimization diff --git a/doc/glibc-functions/memmem.texi b/doc/glibc-functions/memmem.texi index c7e3d73..9515d2e 100644 --- a/doc/glibc-functions/memmem.texi +++ b/doc/glibc-functions/memmem.texi @@ -4,6 +4,10 @@ Gnulib module: memmem or memmem-simple +Both modules implement the same replacement for the @code{memmem} function +with the memmem module providing a replacement on more platforms where +the existing @code{memmem} function has a quadratic worst-case complexity. + Portability problems fixed by either Gnulib module @code{memmem-simple} or @code{memmem}: @itemize @@ -13,18 +17,19 @@ MacOS X 10.3, FreeBSD 5.2.1, OpenBSD 4.0, AIX 4.3.2, HP-UX 11, IRIX 6.5, OSF/1 5 @item This function has reversed arguments on some older platforms: Linux libc 5.0.9 address@hidden itemize - -Portability problems fixed by Gnulib module @code{memmem}: address@hidden @item This function returns incorrect values in some cases, such as when given an empty needle: glibc <= 2.0, Cygwin 1.5.x. address@hidden itemize + +Performance problems fixed by Gnulib module @code{memmem}: address@hidden @item This function has quadratic instead of linear worst-case complexity on some platforms: glibc 2.8, FreeBSD 6.2, NetBSD 3.0, AIX 5.1, Cygwin 1.5.x. +Note for small needles the replacement may be slower. @end itemize Portability problems not fixed by Gnulib: diff --git a/m4/memmem.m4 b/m4/memmem.m4 index c6506ee..7a134c6 100644 --- a/m4/memmem.m4 +++ b/m4/memmem.m4 @@ -1,11 +1,11 @@ -# memmem.m4 serial 14 +# memmem.m4 serial 15 dnl Copyright (C) 2002, 2003, 2004, 2007, 2008, 2009, 2010 Free Software dnl 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 memmem is present. +dnl Check that memmem is present and functional. AC_DEFUN([gl_FUNC_MEMMEM_SIMPLE], [ dnl Persuade glibc to declare memmem(). @@ -16,17 +16,51 @@ AC_DEFUN([gl_FUNC_MEMMEM_SIMPLE], AC_CHECK_DECLS_ONCE([memmem]) if test $ac_cv_have_decl_memmem = no; then HAVE_DECL_MEMMEM=0 + else + AC_CACHE_CHECK([whether memmem handles empty needles], + [gl_cv_func_memmem_works], + [AC_RUN_IFELSE([AC_LANG_PROGRAM([[ +#include /* for memmem */ +]], [[char* haystack="AAA"; + /* Check for empty needle behavior. */ + return !(haystack == memmem (haystack, 3, 0, 0));]])], + [gl_cv_func_memmem_works=yes], [gl_cv_func_memmem_works=no], + [dnl Only glibc >= 2.1 and cygwin >= 1.7.0 are known to have a + dnl memmem that works wrt to empty needles. + AC_EGREP_CPP([Lucky user], + [ +#include +#ifdef __GNU_LIBRARY__ + #if (__GLIBC__ == 2 && __GLIBC_MINOR__ >= 1) || (__GLIBC__ > 2) + Lucky user + #endif +#endif +#ifdef __CYGWIN__ + #include + #if CYGWIN_VERSION_DLL_MAJOR >= 1007 + Lucky 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]) + fi fi gl_PREREQ_MEMMEM ]) # gl_FUNC_MEMMEM_SIMPLE -dnl Additionally, check that memmem is efficient and handles empty needles. +dnl Additionally, check that memmem has linear performance characteristics AC_DEFUN([gl_FUNC_MEMMEM], [ AC_REQUIRE([gl_FUNC_MEMMEM_SIMPLE]) if test $ac_cv_have_decl_memmem = yes; then AC_CACHE_CHECK([whether memmem works in linear time], - [gl_cv_func_memmem_works], + [gl_cv_func_memmem_linear], [AC_RUN_IFELSE([AC_LANG_PROGRAM([[ #include /* for signal */ #include /* for memmem */ @@ -49,9 +83,8 @@ AC_DEFUN([gl_FUNC_MEMMEM], needle[m] = 'B'; result = memmem (haystack, 2 * m + 1, needle, m + 1); } - /* Check for empty needle behavior. */ - return !result || !memmem ("a", 1, 0, 0);]])], - [gl_cv_func_memmem_works=yes], [gl_cv_func_memmem_works=no], + return !result;]])], + [gl_cv_func_memmem_linear=yes], [gl_cv_func_memmem_linear=no], [dnl Only glibc >= 2.9 and cygwin >= 1.7.0 are known to have a dnl memmem that works in linear time. AC_EGREP_CPP([Lucky user], @@ -69,11 +102,11 @@ AC_DEFUN([gl_FUNC_MEMMEM], #endif #endif ], - [gl_cv_func_memmem_works=yes], - [gl_cv_func_memmem_works="guessing no"]) + [gl_cv_func_memmem_linear=yes], + [gl_cv_func_memmem_linear="guessing no"]) ]) ]) - if test "$gl_cv_func_memmem_works" != yes; then + if test "$gl_cv_func_memmem_linear" != yes; then REPLACE_MEMMEM=1 AC_LIBOBJ([memmem]) fi -- 1.6.2.5