[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
glibc strstr is no longer quadratic
From: |
Eric Blake |
Subject: |
glibc strstr is no longer quadratic |
Date: |
Thu, 15 May 2008 06:18:31 -0600 |
User-agent: |
Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.8.1.14) Gecko/20080421 Thunderbird/2.0.0.14 Mnenhy/0.7.5.666 |
-----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
- glibc strstr is no longer quadratic,
Eric Blake <=