glibc strstr is no longer quadratic

[Eric Blake]

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

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.
I'm committing this to document the last slow release.

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

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

iEYEARECAAYFAkgsKhcACgkQ84KuGfSFAYDf6ACfRHq9ImkIdATbjPViw5eOyvTs
Vp0An0/4viy91E5tqvAqm1Og6ceKi+UA
=r15n
-----END PGP SIGNATURE-----

>From a37217922a7b85ddaab2d802b275905f6e9310ac Mon Sep 17 00:00:00 2001
From: Eric Blake <address@hidden>
Date: Thu, 15 May 2008 06:16:11 -0600
Subject: [PATCH] Glibc finally accepted the memmem speedup code, bugzilla #5514.

* doc/glibc-functions/memmem.texi (memmem): Mention last broken
glibc version.
* doc/glibc-functions/strcasestr.texi (strcasestr): Likewise.
* doc/posix-functions/strstr.texi (strstr): Likewise.
* lib/str-two-way.h (MAX): Sychronize with glibc.

Signed-off-by: Eric Blake <address@hidden>
---
 ChangeLog                           |    9 +++++++++
 doc/glibc-functions/memmem.texi     |    2 +-
 doc/glibc-functions/strcasestr.texi |    2 +-
 doc/posix-functions/strstr.texi     |    2 +-
 lib/str-two-way.h                   |    4 +++-
 5 files changed, 15 insertions(+), 4 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index 6a2635b..f563409 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,12 @@
+2008-05-15  Eric Blake  <address@hidden>
+
+       Glibc finally accepted the memmem speedup code, bugzilla #5514.
+       * doc/glibc-functions/memmem.texi (memmem): Mention last broken
+       glibc version.
+       * doc/glibc-functions/strcasestr.texi (strcasestr): Likewise.
+       * doc/posix-functions/strstr.texi (strstr): Likewise.
+       * lib/str-two-way.h (MAX): Sychronize with glibc.
+
 2008-05-15  Paolo Bonzini  <address@hidden>
 
        * lib/regcomp.c (optimize_utf8): Add a note on why we test
diff --git a/doc/glibc-functions/memmem.texi b/doc/glibc-functions/memmem.texi
index a9ec7de..c7e3d73 100644
--- a/doc/glibc-functions/memmem.texi
+++ b/doc/glibc-functions/memmem.texi
@@ -24,7 +24,7 @@ glibc <= 2.0, Cygwin 1.5.x.
 @item
 This function has quadratic instead of linear worst-case complexity on some
 platforms:
-glibc 2.6.1, FreeBSD 6.2, NetBSD 3.0, AIX 5.1, Cygwin 1.5.x.
+glibc 2.8, FreeBSD 6.2, NetBSD 3.0, AIX 5.1, Cygwin 1.5.x.
 @end itemize
 
 Portability problems not fixed by Gnulib:
diff --git a/doc/glibc-functions/strcasestr.texi 
b/doc/glibc-functions/strcasestr.texi
index 4df018c..c5d1c65 100644
--- a/doc/glibc-functions/strcasestr.texi
+++ b/doc/glibc-functions/strcasestr.texi
@@ -17,7 +17,7 @@ Portability problems fixed by Gnulib module @code{strcasestr}:
 @item
 This function has quadratic instead of linear worst-case complexity on some
 platforms:
-glibc 2.6.1, FreeBSD 6.2, NetBSD 3.0, OpenBSD 4.0.
+glibc 2.8, FreeBSD 6.2, NetBSD 3.0, OpenBSD 4.0.
 @end itemize
 
 Portability problems not fixed by Gnulib:
diff --git a/doc/posix-functions/strstr.texi b/doc/posix-functions/strstr.texi
index 417a035..796a14f 100644
--- a/doc/posix-functions/strstr.texi
+++ b/doc/posix-functions/strstr.texi
@@ -11,7 +11,7 @@ Portability problems fixed by Gnulib:
 @item
 This function has quadratic instead of linear worst-case complexity on some
 platforms:
-glibc 2.6.1, MacOS X 10.3, FreeBSD 6.2, NetBSD 3.0, OpenBSD 4.0, AIX 5.1, 
HP-UX 11, IRIX 6.5, OSF/1 5.1, Solaris 10, Cygwin 1.5.x, mingw.
+glibc 2.8, MacOS X 10.3, FreeBSD 6.2, NetBSD 3.0, OpenBSD 4.0, AIX 5.1, HP-UX 
11, IRIX 6.5, OSF/1 5.1, Solaris 10, Cygwin 1.5.x, mingw.
 @end itemize
 
 Portability problems not fixed by Gnulib:
diff --git a/lib/str-two-way.h b/lib/str-two-way.h
index d144ac9..b0338a7 100644
--- a/lib/str-two-way.h
+++ b/lib/str-two-way.h
@@ -67,7 +67,9 @@
 # define LONG_NEEDLE_THRESHOLD SIZE_MAX
 #endif
 
-#define MAX(a, b) ((a < b) ? (b) : (a))
+#ifndef MAX
+# define MAX(a, b) ((a < b) ? (b) : (a))
+#endif
 
 #ifndef CANON_ELEMENT
 # define CANON_ELEMENT(c) c
-- 
1.5.5.1