[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: test-memmem takes waaay too long
From: |
Eric Blake |
Subject: |
Re: test-memmem takes waaay too long |
Date: |
Sat, 05 Jan 2008 04:56:22 -0700 |
User-agent: |
Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.8.1.9) Gecko/20071031 Thunderbird/2.0.0.9 Mnenhy/0.7.5.666 |
-----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