changeset 9623:69d9307c0aa0

Convert strcasestr module to use Two-Way algorithm. * modules/strcasestr-simple: New module, based on the old strcasestr, but with Two-Way rather than KMP. * modules/strcasestr (Depends-on): Change to strcasestr-simple. * lib/string.in.h (rpl_strcasestr): Declare. * m4/strcasestr.m4 (gl_FUNC_STRCASESTR): Check for linear performance. * lib/strcasestr.c (strcasestr): Simplify, and avoid malloc. * modules/string (Makefile.am): Support strcasestr. * m4/string_h.m4 (gl_HEADER_STRING_H_DEFAULTS): Likewise. * modules/strcasestr-tests (Depends-on): Check for alarm. * tests/test-strcasestr.c: Augment test. * lib/str-two-way.h: Clean up stray macro. * NEWS: Document new module. * MODULES.html.sh (string handling): Likewise. * doc/functions/strcasestr.texi: New file. * doc/gnulib.texi (Function Substitutes): New node. Move memmem here, since it is not a POSIX function. Signed-off-by: Eric Blake <ebb9@byu.net>
author Eric Blake <ebb9@byu.net>
date Thu, 10 Jan 2008 22:22:51 -0700
parents 7b32838d1079
children 1e2b5f620c05
files ChangeLog MODULES.html.sh NEWS doc/functions/strcasestr.texi doc/gnulib.texi lib/str-two-way.h lib/strcasestr.c lib/string.in.h m4/strcasestr.m4 m4/string_h.m4 modules/strcasestr modules/strcasestr-simple modules/strcasestr-tests modules/string tests/test-strcasestr.c
diffstat 15 files changed, 239 insertions(+), 119 deletions(-) [+]
line wrap: on
line diff
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,24 @@
+2008-01-14  Eric Blake  <ebb9@byu.net>
+
+	Convert strcasestr module to use Two-Way algorithm.
+	* modules/strcasestr-simple: New module, based on the old
+	strcasestr, but with Two-Way rather than KMP.
+	* modules/strcasestr (Depends-on): Change to strcasestr-simple.
+	* lib/string.in.h (rpl_strcasestr): Declare.
+	* m4/strcasestr.m4 (gl_FUNC_STRCASESTR): Check for linear
+	performance.
+	* lib/strcasestr.c (strcasestr): Simplify, and avoid malloc.
+	* modules/string (Makefile.am): Support strcasestr.
+	* m4/string_h.m4 (gl_HEADER_STRING_H_DEFAULTS): Likewise.
+	* modules/strcasestr-tests (Depends-on): Check for alarm.
+	* tests/test-strcasestr.c: Augment test.
+	* lib/str-two-way.h: Clean up stray macro.
+	* NEWS: Document new module.
+	* MODULES.html.sh (string handling): Likewise.
+	* doc/functions/strcasestr.texi: New file.
+	* doc/gnulib.texi (Function Substitutes): New node.  Move memmem
+	here, since it is not a POSIX function.
+
 2008-01-14  Colin Watson  <cjwatson@debian.org>
             Bruno Haible  <bruno@clisp.org>
 
--- a/MODULES.html.sh
+++ b/MODULES.html.sh
@@ -1664,6 +1664,7 @@
   func_module c-strcaseeq
   func_module c-strcasestr
   func_module strcasestr
+  func_module strcasestr-simple
   func_module strchrnul
   func_module strdup
   func_module streq
--- a/NEWS
+++ b/NEWS
@@ -6,6 +6,12 @@
 
 Date        Modules         Changes
 
+2008-01-14  strcasestr      This module now replaces worst-case inefficient
+                            implementations; clients that use controlled
+                            needles and thus do not care about worst-case
+                            efficiency should use the new strcasestr-simple
+                            module instead for smaller code size.
+
 2008-01-09  alloca-opt      Now defines HAVE_ALLOCA_H only when the system
                             supplies an <alloca.h>.  Gnulib-using code is now
                             expected to include <alloca.h> unconditionally.
new file mode 100644
--- /dev/null
+++ b/doc/functions/strcasestr.texi
@@ -0,0 +1,29 @@
+@node strcasestr
+@section @code{strcasestr}
+@findex strcasestr
+
+Unspecified by POSIX, but comparable to a mix of @code{strstr} and
+@code{strcasecmp}.
+
+Gnulib module: strcasestr or strcasestr-simple
+
+Portability problems fixed by either Gnulib module @code{strcasestr-simple}
+or @code{strcasestr}:
+@itemize
+@item
+This function is missing on some platforms:
+MacOS X 10.3, FreeBSD 5.2.1, OpenBSD 4.0, AIX 4.3.2, HP-UX 11, IRIX
+6.5, OSF/1 5.1, Solaris 10, Cygwin 1.5.x, mingw, Interix 3.5, BeOS.
+@end itemize
+
+Portability problems fixed by Gnulib module @code{strcasestr}:
+@itemize
+@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.
+@end itemize
+
+Portability problems not fixed by Gnulib:
+@itemize
+@end itemize
--- a/doc/gnulib.texi
+++ b/doc/gnulib.texi
@@ -644,7 +644,7 @@
 module providing a substitute for the function.  When the list
 ``Portability problems not fixed by Gnulib'' is empty, such a module is
 not needed: No portability problems are known.  Otherwise, it indicates
-that such a module would be useful but is not available: Noone so far
+that such a module would be useful but is not available: No one so far
 found this function important enough to contribute a substitute for it.
 If you need this particular function, you may write to
 @code{<bug-gnulib at gnu dot org>}.
@@ -1176,7 +1176,6 @@
 * memchr::
 * memcmp::
 * memcpy::
-* memmem::
 * memmove::
 * memset::
 * mkdir::
@@ -2962,6 +2961,31 @@
 @include glibc-headers/sysexits.texi
 @include glibc-headers/ttyent.texi
 
+@node Glibc Function Substitutes
+@chapter Glibc Function Substitutes
+
+This chapter describes which functions and function-like macros
+provided as extensions by at least glibc are also supported by Gnulib,
+which portability pitfalls are fixed by Gnulib, and which (known)
+portability problems are not worked around by Gnulib.
+
+The notation ``Gnulib module: ---'' means that Gnulib does not provide a
+module providing a substitute for the function.  When the list
+``Portability problems not fixed by Gnulib'' is empty, such a module is
+not needed: No portability problems are known.  Otherwise, it indicates
+that such a module would be useful but is not available: No one so far
+found this function important enough to contribute a substitute for it.
+If you need this particular function, you may write to
+@code{<bug-gnulib at gnu dot org>}.
+
+@menu
+* memmem::
+* strcasestr::
+@end menu
+
+@include functions/memmem.texi
+@include functions/strcasestr.texi
+
 @node Particular Modules
 @chapter Particular Modules
 
--- a/lib/str-two-way.h
+++ b/lib/str-two-way.h
@@ -422,5 +422,6 @@
 
 #undef AVAILABLE
 #undef CANON_ELEMENT
+#undef CMP_FUNC
 #undef MAX
 #undef RETURN_TYPE
--- a/lib/strcasestr.c
+++ b/lib/strcasestr.c
@@ -1,5 +1,5 @@
 /* Case-insensitive searching in a string.
-   Copyright (C) 2005-2007 Free Software Foundation, Inc.
+   Copyright (C) 2005-2008 Free Software Foundation, Inc.
    Written by Bruno Haible <bruno@clisp.org>, 2005.
 
    This program is free software; you can redistribute it and/or modify
@@ -23,109 +23,61 @@
 
 #include <ctype.h>
 #include <stdbool.h>
-#include <stddef.h>  /* for NULL, in case a nonstandard string.h lacks it */
-
-#include "malloca.h"
+#include <strings.h>
 
 #define TOLOWER(Ch) (isupper (Ch) ? tolower (Ch) : (Ch))
 
-/* Knuth-Morris-Pratt algorithm.  */
+/* Two-Way algorithm.  */
+#define RETURN_TYPE char *
+#define AVAILABLE(h, h_l, j, n_l)			\
+  (!memchr ((h) + (h_l), '\0', (j) + (n_l) - (h_l))	\
+   && ((h_l) = (j) + (n_l)))
 #define CANON_ELEMENT(c) TOLOWER (c)
-#include "str-kmp.h"
+#define CMP_FUNC(p1, p2, l)				\
+  strncasecmp ((const char *) (p1), (const char *) (p2), l)
+#include "str-two-way.h"
 
-/* Find the first occurrence of NEEDLE in HAYSTACK, using case-insensitive
-   comparison.
-   Note: This function may, in multibyte locales, return success even if
-   strlen (haystack) < strlen (needle) !  */
+/* Find the first occurrence of NEEDLE in HAYSTACK, using
+   case-insensitive comparison.  This function gives unspecified
+   results in multibyte locales.  */
 char *
-strcasestr (const char *haystack, const char *needle)
+strcasestr (const char *haystack_start, const char *needle_start)
 {
-  if (*needle != '\0')
-    {
-      /* Minimizing the worst-case complexity:
-	 Let n = strlen(haystack), m = strlen(needle).
-	 The naïve algorithm is O(n*m) worst-case.
-	 The Knuth-Morris-Pratt algorithm is O(n) worst-case but it needs a
-	 memory allocation.
-	 To achieve linear complexity and yet amortize the cost of the memory
-	 allocation, we activate the Knuth-Morris-Pratt algorithm only once
-	 the naïve algorithm has already run for some time; more precisely,
-	 when
-	   - the outer loop count is >= 10,
-	   - the average number of comparisons per outer loop is >= 5,
-	   - the total number of comparisons is >= m.
-	 But we try it only once.  If the memory allocation attempt failed,
-	 we don't retry it.  */
-      bool try_kmp = true;
-      size_t outer_loop_count = 0;
-      size_t comparison_count = 0;
-      size_t last_ccount = 0;			/* last comparison count */
-      const char *needle_last_ccount = needle;	/* = needle + last_ccount */
-
-      /* Speed up the following searches of needle by caching its first
-	 character.  */
-      unsigned char b = TOLOWER ((unsigned char) *needle);
-
-      needle++;
-      for (;; haystack++)
-	{
-	  if (*haystack == '\0')
-	    /* No match.  */
-	    return NULL;
+  const char *haystack = haystack_start;
+  const char *needle = needle_start;
+  size_t needle_len; /* Length of NEEDLE.  */
+  size_t haystack_len; /* Known minimum length of HAYSTACK.  */
+  bool ok = true; /* True if NEEDLE is prefix of HAYSTACK.  */
 
-	  /* See whether it's advisable to use an asymptotically faster
-	     algorithm.  */
-	  if (try_kmp
-	      && outer_loop_count >= 10
-	      && comparison_count >= 5 * outer_loop_count)
-	    {
-	      /* See if needle + comparison_count now reaches the end of
-		 needle.  */
-	      if (needle_last_ccount != NULL)
-		{
-		  needle_last_ccount +=
-		    strnlen (needle_last_ccount, comparison_count - last_ccount);
-		  if (*needle_last_ccount == '\0')
-		    needle_last_ccount = NULL;
-		  last_ccount = comparison_count;
-		}
-	      if (needle_last_ccount == NULL)
-		{
-		  /* Try the Knuth-Morris-Pratt algorithm.  */
-		  const char *result;
-		  bool success =
-		    knuth_morris_pratt_unibyte (haystack, needle - 1, &result);
-		  if (success)
-		    return (char *) result;
-		  try_kmp = false;
-		}
-	    }
+  /* Determine length of NEEDLE, and in the process, make sure
+     HAYSTACK is at least as long (no point processing all of a long
+     NEEDLE if HAYSTACK is too short).  */
+  while (*haystack && *needle)
+    {
+      ok &= (TOLOWER ((unsigned char) *haystack)
+	     == TOLOWER ((unsigned char) *needle));
+      haystack++;
+      needle++;
+    }
+  if (*needle)
+    return NULL;
+  if (ok)
+    return (char *) haystack_start;
+  needle_len = needle - needle_start;
+  haystack = haystack_start + 1;
+  haystack_len = needle_len - 1;
 
-	  outer_loop_count++;
-	  comparison_count++;
-	  if (TOLOWER ((unsigned char) *haystack) == b)
-	    /* The first character matches.  */
-	    {
-	      const char *rhaystack = haystack + 1;
-	      const char *rneedle = needle;
+  /* Perform the search.  Abstract memory is considered to be an array
+     of 'unsigned char' values, not an array of 'char' values.  See
+     ISO C 99 section 6.2.6.1.  */
+  if (needle_len < LONG_NEEDLE_THRESHOLD)
+    return two_way_short_needle ((const unsigned char *) haystack,
+				 haystack_len,
+				 (const unsigned char *) needle_start,
+				 needle_len);
+  return two_way_long_needle ((const unsigned char *) haystack, haystack_len,
+			      (const unsigned char *) needle_start,
+			      needle_len);
+}
 
-	      for (;; rhaystack++, rneedle++)
-		{
-		  if (*rneedle == '\0')
-		    /* Found a match.  */
-		    return (char *) haystack;
-		  if (*rhaystack == '\0')
-		    /* No match.  */
-		    return NULL;
-		  comparison_count++;
-		  if (TOLOWER ((unsigned char) *rhaystack)
-		      != TOLOWER ((unsigned char) *rneedle))
-		    /* Nothing in this round.  */
-		    break;
-		}
-	    }
-	}
-    }
-  else
-    return (char *) haystack;
-}
+#undef LONG_NEEDLE_THRESHOLD
--- a/lib/string.in.h
+++ b/lib/string.in.h
@@ -313,11 +313,15 @@
 
 /* Find the first occurrence of NEEDLE in HAYSTACK, using case-insensitive
    comparison.  */
-#if ! @HAVE_STRCASESTR@
+#if @GNULIB_STRCASESTR@
+# if @REPLACE_STRCASESTR@
+#  define strcasestr rpl_strcasestr
+# endif
+# if ! @HAVE_STRCASESTR@ || @REPLACE_STRCASESTR@
 extern char *strcasestr (const char *haystack, const char *needle)
   __attribute__ ((__pure__));
-#endif
-#if defined GNULIB_POSIXCHECK
+# endif
+#elif defined GNULIB_POSIXCHECK
 /* strcasestr() does not work with multibyte strings:
    It is a glibc extension, and glibc implements it only for unibyte
    locales.  */
--- a/m4/strcasestr.m4
+++ b/m4/strcasestr.m4
@@ -1,18 +1,63 @@
-# strcasestr.m4 serial 6
-dnl Copyright (C) 2005, 2007 Free Software Foundation, Inc.
+# strcasestr.m4 serial 7
+dnl Copyright (C) 2005, 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.
 
-AC_DEFUN([gl_FUNC_STRCASESTR],
+dnl Check that strcasestr is present.
+AC_DEFUN([gl_FUNC_STRCASESTR_SIMPLE],
 [
+  dnl Persuade glibc <string.h> to declare strcasestr().
+  AC_REQUIRE([AC_USE_SYSTEM_EXTENSIONS])
+
   AC_REQUIRE([gl_HEADER_STRING_H_DEFAULTS])
-  AC_REPLACE_FUNCS(strcasestr)
+  AC_REPLACE_FUNCS([strcasestr])
   if test $ac_cv_func_strcasestr = no; then
     HAVE_STRCASESTR=0
     gl_PREREQ_STRCASESTR
   fi
-])
+]) # gl_FUNC_STRCASESTR_SIMPLE
+
+dnl Additionally, check that strcasestr is efficient.
+AC_DEFUN([gl_FUNC_STRCASESTR])
+[
+  AC_REQUIRE([gl_FUNC_STRCASESTR_SIMPLE])
+  if test $ac_cv_func_strcasestr = yes; then
+    AC_CACHE_CHECK([whether strcasestr works in linear time],
+      [gl_cv_func_strcasestr_linear],
+      [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 + 2);
+    char *needle = (char *) malloc (m + 2);
+    void *result = 0;
+    /* Failure to compile this test due to missing alarm is okay,
+       since all such platforms (mingw) also lack strcasestr.  */
+    alarm (5);
+    /* Check for quadratic performance.  */
+    if (haystack && needle)
+      {
+	memset (haystack, 'A', 2 * m);
+	haystack[2 * m] = 'B';
+	haystack[2 * m + 1] = 0;
+	memset (needle, 'A', m);
+	needle[m] = 'B';
+	needle[m + 1] = 0;
+	result = strcasestr (haystack, needle);
+      }
+    return !result;]])],
+      [gl_cv_func_strcasestr_linear=yes], [gl_cv_func_strcasestr_linear=no],
+      [dnl pessimistically assume the worst, since even glibc 2.6.1
+       dnl has quadratic complexity in its strcasestr
+       gl_cv_func_strcasestr_linear="guessing no"])])
+    if test "$gl_cv_func_strcasestr_linear" != yes; then
+      REPLACE_STRCASESTR=1
+      AC_LIBOBJ([strcasestr])
+    fi
+  fi
+]) # gl_FUNC_STRCASESTR
 
 # Prerequisites of lib/strcasestr.c.
 AC_DEFUN([gl_PREREQ_STRCASESTR], [
--- a/m4/string_h.m4
+++ b/m4/string_h.m4
@@ -82,5 +82,6 @@
   REPLACE_STRERROR=0;		AC_SUBST([REPLACE_STRERROR])
   REPLACE_STRSIGNAL=0;		AC_SUBST([REPLACE_STRSIGNAL])
   REPLACE_MEMMEM=0;		AC_SUBST([REPLACE_MEMMEM])
+  REPLACE_STRCASESTR=0;		AC_SUBST([REPLACE_STRCASESTR])
   REPLACE_STRSTR=0;		AC_SUBST([REPLACE_STRSTR])
 ])
--- a/modules/strcasestr
+++ b/modules/strcasestr
@@ -1,20 +1,13 @@
 Description:
-strcasestr() function: case-insensitive search for a substring in a string.
+strcasestr() function: efficient case-insensitive search for unibyte substring.
 
 Files:
-lib/strcasestr.c
-lib/str-kmp.h
-m4/strcasestr.m4
 
 Depends-on:
-string
-stdbool
-malloca
-strnlen
+strcasestr-simple
 
 configure.ac:
 gl_FUNC_STRCASESTR
-gl_STRING_MODULE_INDICATOR([strcasestr])
 
 Makefile.am:
 
new file mode 100644
--- /dev/null
+++ b/modules/strcasestr-simple
@@ -0,0 +1,28 @@
+Description:
+strcasestr() function: case-insensitive search for unibyte substring.
+
+Files:
+lib/strcasestr.c
+lib/str-two-way.h
+m4/strcasestr.m4
+
+Depends-on:
+string
+stdbool
+strcase
+
+configure.ac:
+gl_FUNC_STRCASESTR_SIMPLE
+gl_STRING_MODULE_INDICATOR([strcasestr])
+
+Makefile.am:
+
+Include:
+<string.h>
+
+License:
+LGPLv2+
+
+Maintainer:
+Bruno Haible
+
--- a/modules/strcasestr-tests
+++ b/modules/strcasestr-tests
@@ -4,6 +4,7 @@
 Depends-on:
 
 configure.ac:
+AC_CHECK_DECLS_ONCE([alarm])
 
 Makefile.am:
 TESTS += test-strcasestr
--- a/modules/string
+++ b/modules/string
@@ -70,6 +70,7 @@
 	      -e 's|@''HAVE_DECL_STRERROR''@|$(HAVE_DECL_STRERROR)|g' \
 	      -e 's|@''HAVE_DECL_STRSIGNAL''@|$(HAVE_DECL_STRSIGNAL)|g' \
 	      -e 's|@''REPLACE_MEMMEM''@|$(REPLACE_MEMMEM)|g' \
+	      -e 's|@''REPLACE_STRCASESTR''@|$(REPLACE_STRCASESTR)|g' \
 	      -e 's|@''REPLACE_STRSTR''@|$(REPLACE_STRSTR)|g' \
 	      -e 's|@''REPLACE_STRERROR''@|$(REPLACE_STRERROR)|g' \
 	      -e 's|@''REPLACE_STRSIGNAL''@|$(REPLACE_STRSIGNAL)|g' \
--- a/tests/test-strcasestr.c
+++ b/tests/test-strcasestr.c
@@ -1,5 +1,5 @@
 /* Test of case-insensitive searching in a string.
-   Copyright (C) 2007 Free Software Foundation, Inc.
+   Copyright (C) 2007, 2008 Free Software Foundation, Inc.
 
    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
@@ -22,6 +22,7 @@
 
 #include <stdio.h>
 #include <stdlib.h>
+#include <unistd.h>
 
 #define ASSERT(expr) \
   do									     \
@@ -37,6 +38,14 @@
 int
 main ()
 {
+#if HAVE_DECL_ALARM
+  /* Declare failure if test takes too long, by using default abort
+     caused by SIGALRM.  All known platforms that lack alarm also lack
+     memmem, and the replacement memmem is known to not take too
+     long.  */
+  alarm (50);
+#endif
+
   {
     const char input[] = "foo";
     const char *result = strcasestr (input, "");
@@ -61,6 +70,12 @@
     ASSERT (result == NULL);
   }
 
+  {
+    const char input[] = "ABC ABCDAB ABCDABCDABDE";
+    const char *result = strcasestr (input, "ABCDaBCD");
+    ASSERT (result == input + 11);
+  }
+
   /* Check that a very long haystack is handled quickly if the needle is
      short and occurs near the beginning.  */
   {
@@ -110,7 +125,6 @@
   }
 
   /* Check that the asymptotic worst-case complexity is not quadratic.  */
-#if !HAVE_STRCASESTR /* The system's strcasestr() function fails this test.  */
   {
     size_t m = 1000000;
     char *haystack = (char *) malloc (2 * m + 2);
@@ -135,7 +149,6 @@
     if (haystack != NULL)
       free (haystack);
   }
-#endif
 
   return 0;
 }