On 22/06/10 15:42, Eric Blake wrote:
> On 06/22/2010 08:41 AM, Eric Blake wrote:
>> On 06/22/2010 08:34 AM, Pádraig Brady wrote:
>>> Cool, that's what I expected from the names.
>>> So do we just need to move a docs around a little like:
>>>
>>
>> Yes, that looks like an appropriate patch. Please apply.
>
> I spoke too soon. We would also need to patch m4/memmem.m4 to actually
> perform the empty needle verification in the memmem-simple case.
I also noticed the empty needle verification didn't
check that the correct pointer was returned,
and only checked for !NULL. So I rolled that
fix into the attached reorg.
cheers,
Pádraig.
>From d0d7a45d51609f7a69dbeffbc11c086cfa267bb8 Mon Sep 17 00:00:00 2001
From: =?utf-8?q?P=C3=A1draig=20Brady?= <p...@draigbrady.com>
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 <p...@draigbrady.com>
+
+ 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 <ebl...@redhat.com>
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
-...@end itemize
-
-Portability problems fixed by Gnulib module @code{memmem}:
-...@itemize
@item
This function returns incorrect values in some cases, such as when
given an empty needle:
glibc <= 2.0, Cygwin 1.5.x.
+...@end itemize
+
+Performance problems fixed by Gnulib module @code{memmem}:
+...@itemize
@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 <string.h> 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 <string.h> /* 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 <features.h>
+#ifdef __GNU_LIBRARY__
+ #if (__GLIBC__ == 2 && __GLIBC_MINOR__ >= 1) || (__GLIBC__ > 2)
+ Lucky user
+ #endif
+#endif
+#ifdef __CYGWIN__
+ #include <cygwin/version.h>
+ #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 <signal.h> /* for signal */
#include <string.h> /* 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
