Regarding the run-time complexity of the memmem, strstr, strcasestr, wcsstr
implementations:
- For memmem: It's interesting to see that after glibc and musl, now also
FreeBSD, NetBSD, and OpenBSD have adopted the two-way algorithm
for O(n) behaviour.
- For strcasestr, on the other hand, glibc is still the only platform
that has O(n) behaviour.
- For wcsstr, even glibc does not get it right so far.
Gnulib is helping to push the libcs to better implementations. This can
be seen from this commit message in OpenBSD:
revision 1.7
date: 2017/04/12 16:06:12; author: millert; state: Exp; lines: +179 -43;
commitid: ADPD8k6Rjd9HgPt6;
New strstr() implementation from musl libc by Rich Felker. This
version uses the two-way string matching algorithm and is faster
than the old implementation. With this change, ports that check
for strstr having linear complexity time strstr will no longer
replace the libc strstr with a private version.
OK deraadt@ espie@
2023-03-28 Bruno Haible <br...@clisp.org>
doc: Update regarding linear string search.
* doc/glibc-functions/memmem.texi: Update platforms list.
* doc/posix-functions/strstr.texi: Likewise.
* doc/glibc-functions/strcasestr.texi: Likewise.
diff --git a/doc/glibc-functions/memmem.texi b/doc/glibc-functions/memmem.texi
index ef5b4ffed2..f3bf80611c 100644
--- a/doc/glibc-functions/memmem.texi
+++ b/doc/glibc-functions/memmem.texi
@@ -40,7 +40,7 @@
@item
This function returns incorrect values in some cases, such as when
given an empty needle:
-glibc <= 2.0, Solaris 11.4, Cygwin 1.5.x.
+glibc <= 2.0, macOS 12.5, AIX 7.2, Solaris 11.3, Cygwin 1.5.x.
@end itemize
Performance problems fixed by Gnulib module @code{memmem}:
@@ -48,7 +48,7 @@
@item
This function has quadratic instead of linear worst-case complexity on some
platforms:
-glibc 2.8, FreeBSD 6.2, NetBSD 9.0, AIX 5.1, Solaris 11.4, Cygwin 1.5.x.
+glibc 2.8, macOS 12.5, FreeBSD 11.4, NetBSD 8.2, OpenBSD 6.6, AIX 7.2, Solaris
11.4, Cygwin 1.5.x.
Note for small needles the replacement may be slower.
@end itemize
diff --git a/doc/glibc-functions/strcasestr.texi
b/doc/glibc-functions/strcasestr.texi
index 2860103155..9a7ca477cd 100644
--- a/doc/glibc-functions/strcasestr.texi
+++ b/doc/glibc-functions/strcasestr.texi
@@ -24,8 +24,7 @@
@itemize
@item
This function is missing on some platforms:
-AIX 5.1, HP-UX 11, IRIX 6.5, Solaris 10, Cygwin 1.5.x,
-mingw, MSVC 14.
+AIX 7.2, HP-UX 11, IRIX 6.5, Solaris 10, Cygwin 1.5.x, mingw, MSVC 14.
@item
This function can trigger memchr bugs on some platforms:
glibc 2.10.
@@ -43,7 +42,7 @@
@item
This function has quadratic instead of linear worst-case complexity on some
platforms:
-glibc 2.8, FreeBSD 6.2, NetBSD 9.0, OpenBSD 4.0, Solaris 11.4.
+glibc 2.8, musl libc 1.2.3, macOS 12.5, FreeBSD 13.1, NetBSD 9.0, OpenBSD 7.2,
Solaris 11.4.
@end itemize
Portability problems not fixed by Gnulib:
diff --git a/doc/posix-functions/strstr.texi b/doc/posix-functions/strstr.texi
index 3a36cfdeed..a2f711da9c 100644
--- a/doc/posix-functions/strstr.texi
+++ b/doc/posix-functions/strstr.texi
@@ -26,7 +26,7 @@
@item
This function has quadratic instead of linear worst-case complexity on some
platforms:
-glibc 2.8, macOS 11.1, FreeBSD 6.2, NetBSD 9.0, OpenBSD 4.0, AIX 5.1, HP-UX
11, IRIX 6.5, Solaris 11.4, Cygwin 1.5.x, mingw, MSVC 14.
+glibc 2.8, macOS 12.5, FreeBSD 11.4, NetBSD 9.0, OpenBSD 6.1, AIX 7.2, HP-UX
11, IRIX 6.5, Solaris 11.4, Cygwin 1.5.x, mingw, MSVC 14.
@end itemize
Portability problems not fixed by Gnulib:
