doc: Update regarding linear string search

[Bruno Haible]

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  <bruno@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: