Re: test-memmem takes waaay too long

[Eric Blake]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

According to Bruno Haible on 1/4/2008 4:38 PM:
| Eric Blake wrote:
|> + * tests/test-memmem.c (main): Use alarm to declare failure if test
|> + is taking too long.
|
| The function alarm() does not exist on mingw. Neither does SIGALRM.

Indeed.  But since mingw also lacks memmem, and we know rpl_memmem never
takes too long, we merely need check for HAVE_DECL_ALARM before using
alarm in the test.

Meanwhile, I'm still working on the Two-Way implementation, but it looks
promising enough at providing a linear algorithm that does not require
malloc that I think we can still provide an async-safe memmem for glibc
without needing an additional module.  Therefore, the second commit turns
on quadratic checking in memmem.m4, so that glibc-based systems once again
pass test-memmem.c.  Here, since mingw lacks memmem, we can blindly use
alarm in the m4 test.

I'm installing these two commits:

- --
Don't work too hard, make some time for fun as well!

Eric Blake             address@hidden
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.5 (Cygwin)
Comment: Public key at home.comcast.net/~ericblake/eblake.gpg
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFHf3Bl84KuGfSFAYARAs4oAJ404slzx64Der7EWuwp1rMkzs4q6gCgjMe3
vueMKzwX1/hWMv5istB3fSw=
=01vH
-----END PGP SIGNATURE-----

>From b25c432e30d9e69a81cfaeab355c4bdd0c20eb80 Mon Sep 17 00:00:00 2001
From: Eric Blake <address@hidden>
Date: Sat, 5 Jan 2008 04:47:05 -0700
Subject: [PATCH] Fix memmem test for mingw.

* modules/memmem-tests (configure.ac): Check for alarm.
* tests/test-memmem.c (main): Avoid alarm on platforms that lack
it.
* doc/functions/memmem.texi: New file.
* doc/gnulib.texi (Function Substitutes): Add memmem.
Reported by Bruno Haible.

Signed-off-by: Eric Blake <address@hidden>
---
 ChangeLog                 |   10 ++++++++++
 doc/functions/memmem.texi |   28 ++++++++++++++++++++++++++++
 doc/gnulib.texi           |    4 +++-
 modules/memmem-tests      |    1 +
 tests/test-memmem.c       |    7 ++++++-
 5 files changed, 48 insertions(+), 2 deletions(-)
 create mode 100644 doc/functions/memmem.texi

diff --git a/ChangeLog b/ChangeLog
index bdf61e2..b4be78e 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,13 @@
+2008-01-05  Eric Blake  <address@hidden>
+
+       Fix memmem test for mingw.
+       * modules/memmem-tests (configure.ac): Check for alarm.
+       * tests/test-memmem.c (main): Avoid alarm on platforms that lack
+       it.
+       * doc/functions/memmem.texi: New file.
+       * doc/gnulib.texi (Function Substitutes): Add memmem.
+       Reported by Bruno Haible.
+
 2008-01-04  Bruno Haible  <address@hidden>
 
        * m4/strcase.m4 (gl_FUNC_STRCASECMP, gl_FUNC_STRNCASECMP):
diff --git a/doc/functions/memmem.texi b/doc/functions/memmem.texi
new file mode 100644
index 0000000..50d73fd
--- /dev/null
+++ b/doc/functions/memmem.texi
@@ -0,0 +1,28 @@
address@hidden memmem
address@hidden @code{memmem}
address@hidden memmem
+
+Unspecified by POSIX, but comparable to @code{strstr}.
+
+Gnulib module: memmem
+
+Portability problems fixed by Gnulib:
address@hidden
address@hidden
+This function fails to return the start of the haystack for an empty
+needle on some platforms:
+Cygwin 1.5.x
+
address@hidden
+This function has quadratic instead of linear complexity on some
+platforms:
+glibc <= 2.6.1
+
address@hidden
+This function is missing on some platforms:
+Mingw, OpenBSD 4.0
address@hidden itemize
+
+Portability problems not fixed by Gnulib:
address@hidden
address@hidden itemize
diff --git a/doc/gnulib.texi b/doc/gnulib.texi
index f46096b..deaf528 100644
--- a/doc/gnulib.texi
+++ b/doc/gnulib.texi
@@ -17,7 +17,8 @@ This manual is for GNU Gnulib (updated @value{UPDATED}),
 which is a library of common routines intended to be shared at the
 source level.
 
-Copyright @copyright{} 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
+Copyright @copyright{} 2004, 2005, 2006, 2007, 2008 Free Software
+Foundation, Inc.
 
 Permission is granted to copy, distribute and/or modify this document
 under the terms of the GNU Free Documentation License, Version 1.1 or
@@ -1174,6 +1175,7 @@ If you need this particular function, you may write to
 * memchr::
 * memcmp::
 * memcpy::
+* memmem::
 * memmove::
 * memset::
 * mkdir::
diff --git a/modules/memmem-tests b/modules/memmem-tests
index 3d79e47..c9365e9 100644
--- a/modules/memmem-tests
+++ b/modules/memmem-tests
@@ -4,6 +4,7 @@ tests/test-memmem.c
 Depends-on:
 
 configure.ac:
+AC_CHECK_DECLS_ONCE([alarm])
 
 Makefile.am:
 TESTS += test-memmem
diff --git a/tests/test-memmem.c b/tests/test-memmem.c
index df3baef..976f293 100644
--- a/tests/test-memmem.c
+++ b/tests/test-memmem.c
@@ -37,9 +37,14 @@
 int
 main (int argc, char *argv[])
 {
+#if HAVE_DECL_ALARM
   /* Declare failure if test takes too long, by using default abort
-     caused by SIGALRM.  */
+     caused by SIGALRM.  All known platforms that lack alarm also lack
+     memmem, and the replacement memmem is known to not take too
+     long.  */
   alarm (10);
+#endif
+
   {
     const char input[] = "foo";
     const char *result = memmem (input, strlen (input), "", 0);
-- 
1.5.3.5


>From e3adb96fc71c48e1d3e638e7e1afadcd3ac0d840 Mon Sep 17 00:00:00 2001
From: Eric Blake <address@hidden>
Date: Sat, 5 Jan 2008 04:47:24 -0700
Subject: [PATCH] Avoid quadratic system memmem.

* m4/memmem.m4 (gl_FUNC_MEMMEM): Check for quadratic memmem.
Reported by Ralf Wildenhues.

Signed-off-by: Eric Blake <address@hidden>
---
 ChangeLog    |    4 ++++
 m4/memmem.m4 |   29 ++++++++++++++++++++++++-----
 2 files changed, 28 insertions(+), 5 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index b4be78e..bdc357a 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,9 @@
 2008-01-05  Eric Blake  <address@hidden>
 
+       Avoid quadratic system memmem.
+       * m4/memmem.m4 (gl_FUNC_MEMMEM): Check for quadratic memmem.
+       Reported by Ralf Wildenhues.
+
        Fix memmem test for mingw.
        * modules/memmem-tests (configure.ac): Check for alarm.
        * tests/test-memmem.c (main): Avoid alarm on platforms that lack
diff --git a/m4/memmem.m4 b/m4/memmem.m4
index a529af3..9767354 100644
--- a/m4/memmem.m4
+++ b/m4/memmem.m4
@@ -1,5 +1,5 @@
-# memmem.m4 serial 6
-dnl Copyright (C) 2002, 2003, 2004, 2007 Free Software Foundation, Inc.
+# memmem.m4 serial 7
+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,
 dnl with or without modifications, as long as this notice is preserved.
@@ -15,9 +15,28 @@ AC_DEFUN([gl_FUNC_MEMMEM],
   if test $ac_cv_have_decl_memmem = no; then
     HAVE_DECL_MEMMEM=0
   else
-    AC_CACHE_CHECK([whether memmem works], [gl_cv_func_memmem_works],
-      [AC_RUN_IFELSE([AC_LANG_PROGRAM([#include <string.h>],
-         [return !memmem ("a", 1, NULL, 0);])],
+    AC_CACHE_CHECK([whether memmem works in linear time],
+      [gl_cv_func_memmem_works],
+      [AC_RUN_IFELSE([AC_LANG_PROGRAM([
+#include <string.h> /* for memmem */
+#include <stdlib.h> /* for malloc */
+#include <unistd.h> /* for alarm */
+], [[size_t m = 1000000;
+    char *haystack = (char *) malloc (2 * m + 1);
+    char *needle = (char *) malloc (m + 1);
+    void *result = 0;
+    /* Failure to compile this test due to missing alarm is okay,
+       since all such platforms (mingw) also lack memmem.  */
+    alarm (5);
+    if (haystack && needle)
+      {
+       memset (haystack, 'A', 2 * m);
+       haystack[2 * m] = 'B';
+       memset (needle, 'A', m);
+       needle[m] = 'B';
+       result = memmem (haystack, 2 * m + 1, needle, m + 1);
+      }
+    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
-- 
1.5.3.5