New implementation.
authordrepper <drepper>
Thu, 15 May 2008 04:39:04 +0000 (04:39 +0000)
committerdrepper <drepper>
Thu, 15 May 2008 04:39:04 +0000 (04:39 +0000)
string/memmem.c
string/strcasestr.c
string/strstr.c

index c404621..3176ab7 100644 (file)
@@ -1,4 +1,4 @@
-/* Copyright (C) 1991,92,93,94,96,97,98,2000,2004 Free Software Foundation, Inc.
+/* Copyright (C) 1991,92,93,94,96,97,98,2000,2004,2008 Free Software Foundation, Inc.
    This file is part of the GNU C Library.
 
    The GNU C Library is free software; you can redistribute it and/or
    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
    02111-1307 USA.  */
 
-#include <stddef.h>
+/* This particular implementation was written by Eric Blake, 2008.  */
+
+#ifndef _LIBC
+# include <config.h>
+#endif
+
+/* Specification of memmem.  */
 #include <string.h>
 
 #ifndef _LIBC
 # define __builtin_expect(expr, val)   (expr)
 #endif
 
+#define RETURN_TYPE void *
+#define AVAILABLE(h, h_l, j, n_l) ((j) <= (h_l) - (n_l))
+#include "str-two-way.h"
+
 #undef memmem
 
-/* Return the first occurrence of NEEDLE in HAYSTACK.  */
+/* Return the first occurrence of NEEDLE in HAYSTACK.  Return HAYSTACK
+   if NEEDLE_LEN is 0, otherwise NULL if NEEDLE is not found in
+   HAYSTACK.  */
 void *
-memmem (haystack, haystack_len, needle, needle_len)
-     const void *haystack;
-     size_t haystack_len;
-     const void *needle;
-     size_t needle_len;
+memmem (const void *haystack_start, size_t haystack_len,
+       const void *needle_start, size_t needle_len)
 {
-  const char *begin;
-  const char *const last_possible
-    = (const char *) haystack + haystack_len - needle_len;
+  /* 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.  */
+  const unsigned char *haystack = (const unsigned char *) haystack_start;
+  const unsigned char *needle = (const unsigned char *) needle_start;
 
   if (needle_len == 0)
     /* The first occurrence of the empty string is deemed to occur at
@@ -47,12 +57,22 @@ memmem (haystack, haystack_len, needle, needle_len)
   if (__builtin_expect (haystack_len < needle_len, 0))
     return NULL;
 
-  for (begin = (const char *) haystack; begin <= last_possible; ++begin)
-    if (begin[0] == ((const char *) needle)[0] &&
-       !memcmp ((const void *) &begin[1],
-                (const void *) ((const char *) needle + 1),
-                needle_len - 1))
-      return (void *) begin;
-
-  return NULL;
+  /* Use optimizations in memchr when possible, to reduce the search
+     size of haystack using a linear algorithm with a smaller
+     coefficient.  However, avoid memchr for long needles, since we
+     can often achieve sublinear performance.  */
+  if (needle_len < LONG_NEEDLE_THRESHOLD)
+    {
+      haystack = memchr (haystack, *needle, haystack_len);
+      if (!haystack || __builtin_expect (needle_len == 1, 0))
+       return (void *) haystack;
+      haystack_len -= haystack - (const unsigned char *) haystack_start;
+      if (haystack_len < needle_len)
+       return NULL;
+      return two_way_short_needle (haystack, haystack_len, needle, needle_len);
+    }
+  else
+    return two_way_long_needle (haystack, haystack_len, needle, needle_len);
 }
+
+#undef LONG_NEEDLE_THRESHOLD
index 1dde43c..9de19aa 100644 (file)
@@ -1,5 +1,5 @@
 /* Return the offset of one string within another.
-   Copyright (C) 1994, 1996-2000, 2004 Free Software Foundation, Inc.
+   Copyright (C) 1994, 1996-2000, 2004, 2008 Free Software Foundation, Inc.
    This file is part of the GNU C Library.
 
    The GNU C Library is free software; you can redistribute it and/or
 # include <config.h>
 #endif
 
+/* Specification.  */
+#include <string.h>
+
 #include <ctype.h>
+#include <stdbool.h>
+#include <strings.h>
 
-#if defined _LIBC || defined HAVE_STRING_H
-# include <string.h>
-#endif
+#define TOLOWER(Ch) (isupper (Ch) ? tolower (Ch) : (Ch))
 
-#ifdef _LIBC
-# include <locale/localeinfo.h>
-# define TOLOWER(c) __tolower_l ((unsigned char) c, loc)
-#else
-# define TOLOWER(c) _tolower (c)
-#endif
-
-typedef unsigned chartype;
+/* 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)
+#define CMP_FUNC(p1, p2, l)                            \
+  strncasecmp ((const char *) (p1), (const char *) (p2), l)
+#include "str-two-way.h"
 
 #undef strcasestr
 #undef __strcasestr
 
+/* Find the first occurrence of NEEDLE in HAYSTACK, using
+   case-insensitive comparison.  This function gives unspecified
+   results in multibyte locales.  */
 char *
-__strcasestr (phaystack, pneedle)
-     const char *phaystack;
-     const char *pneedle;
+__strcasestr (const char *haystack_start, const char *needle_start)
 {
-  register const unsigned char *haystack, *needle;
-  register chartype b, c;
-#ifdef _LIBC
-  __locale_t loc = _NL_CURRENT_LOCALE;
-#endif
-
-  haystack = (const unsigned char *) phaystack;
-  needle = (const unsigned char *) pneedle;
-
-  b = TOLOWER (*needle);
-  if (b != '\0')
+  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.  */
+
+  /* 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)
     {
-      haystack--;                              /* possible ANSI violation */
-      do
-       {
-         c = *++haystack;
-         if (c == '\0')
-           goto ret0;
-       }
-      while (TOLOWER (c) != (int) b);
-
-      c = TOLOWER (*++needle);
-      if (c == '\0')
-       goto foundneedle;
-      ++needle;
-      goto jin;
-
-      for (;;)
-        {
-          register chartype a;
-         register const unsigned char *rhaystack, *rneedle;
-
-         do
-           {
-             a = *++haystack;
-             if (a == '\0')
-               goto ret0;
-             if (TOLOWER (a) == (int) b)
-               break;
-             a = *++haystack;
-             if (a == '\0')
-               goto ret0;
-shloop:
-             ;
-           }
-          while (TOLOWER (a) != (int) b);
-
-jin:     a = *++haystack;
-         if (a == '\0')
-           goto ret0;
-
-         if (TOLOWER (a) != (int) c)
-           goto shloop;
-
-         rhaystack = haystack-- + 1;
-         rneedle = needle;
-         a = TOLOWER (*rneedle);
-
-         if (TOLOWER (*rhaystack) == (int) a)
-           do
-             {
-               if (a == '\0')
-                 goto foundneedle;
-               ++rhaystack;
-               a = TOLOWER (*++needle);
-               if (TOLOWER (*rhaystack) != (int) a)
-                 break;
-               if (a == '\0')
-                 goto foundneedle;
-               ++rhaystack;
-               a = TOLOWER (*++needle);
-             }
-           while (TOLOWER (*rhaystack) == (int) a);
-
-         needle = rneedle;             /* took the register-poor approach */
-
-         if (a == '\0')
-           break;
-        }
+      ok &= (TOLOWER ((unsigned char) *haystack)
+            == TOLOWER ((unsigned char) *needle));
+      haystack++;
+      needle++;
     }
-foundneedle:
-  return (char*) haystack;
-ret0:
-  return 0;
+  if (*needle)
+    return NULL;
+  if (ok)
+    return (char *) haystack_start;
+  needle_len = needle - needle_start;
+  haystack = haystack_start + 1;
+  haystack_len = needle_len - 1;
+
+  /* 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);
 }
 
+#undef LONG_NEEDLE_THRESHOLD
+
 weak_alias (__strcasestr, strcasestr)
index fce1f2a..a9dc312 100644 (file)
@@ -1,5 +1,5 @@
 /* Return the offset of one string within another.
-   Copyright (C) 1994,1996,1997,2000,2001,2003 Free Software Foundation, Inc.
+   Copyright (C) 1994,1996,1997,2000,2001,2003,2008 Free Software Foundation, Inc.
    This file is part of the GNU C Library.
 
    The GNU C Library is free software; you can redistribute it and/or
    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
    02111-1307 USA.  */
 
-/*
- * My personal strstr() implementation that beats most other algorithms.
- * Until someone tells me otherwise, I assume that this is the
- * fastest implementation of strstr() in C.
- * I deliberately chose not to comment it.  You should have at least
- * as much fun trying to understand it, as I had to write it :-).
- *
- * Stephen R. van den Berg, berg@pool.informatik.rwth-aachen.de        */
+/* This particular implementation was written by Eric Blake, 2008.  */
 
-#if HAVE_CONFIG_H
+#ifndef _LIBC
 # include <config.h>
 #endif
 
-#if defined _LIBC || defined HAVE_STRING_H
-# include <string.h>
+/* Specification of strstr.  */
+#include <string.h>
+
+#include <stdbool.h>
+
+#ifndef _LIBC
+# define __builtin_expect(expr, val)   (expr)
 #endif
 
-typedef unsigned chartype;
+#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)))
+#include "str-two-way.h"
 
 #undef strstr
 
+/* Return the first occurrence of NEEDLE in HAYSTACK.  Return HAYSTACK
+   if NEEDLE is empty, otherwise NULL if NEEDLE is not found in
+   HAYSTACK.  */
 char *
-strstr (phaystack, pneedle)
-     const char *phaystack;
-     const char *pneedle;
+strstr (const char *haystack_start, const char *needle_start)
 {
-  const unsigned char *haystack, *needle;
-  chartype b;
-  const unsigned char *rneedle;
-
-  haystack = (const unsigned char *) phaystack;
+  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.  */
 
-  if ((b = *(needle = (const unsigned char *) pneedle)))
-    {
-      chartype c;
-      haystack--;              /* possible ANSI violation */
+  /* 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 &= *haystack++ == *needle++;
+  if (*needle)
+    return NULL;
+  if (ok)
+    return (char *) haystack_start;
 
-      {
-       chartype a;
-       do
-         if (!(a = *++haystack))
-           goto ret0;
-       while (a != b);
-      }
+  /* Reduce the size of haystack using strchr, since it has a smaller
+     linear coefficient than the Two-Way algorithm.  */
+  needle_len = needle - needle_start;
+  haystack = strchr (haystack_start + 1, *needle_start);
+  if (!haystack || __builtin_expect (needle_len == 1, 0))
+    return (char *) haystack;
+  needle -= needle_len;
+  haystack_len = (haystack > haystack_start + needle_len ? 1
+                 : needle_len + haystack_start - haystack);
 
-      if (!(c = *++needle))
-       goto foundneedle;
-      ++needle;
-      goto jin;
-
-      for (;;)
-       {
-         {
-           chartype a;
-           if (0)
-           jin:{
-               if ((a = *++haystack) == c)
-                 goto crest;
-             }
-           else
-             a = *++haystack;
-           do
-             {
-               for (; a != b; a = *++haystack)
-                 {
-                   if (!a)
-                     goto ret0;
-                   if ((a = *++haystack) == b)
-                     break;
-                   if (!a)
-                     goto ret0;
-                 }
-             }
-           while ((a = *++haystack) != c);
-         }
-       crest:
-         {
-           chartype a;
-           {
-             const unsigned char *rhaystack;
-             if (*(rhaystack = haystack-- + 1) == (a = *(rneedle = needle)))
-               do
-                 {
-                   if (!a)
-                     goto foundneedle;
-                   if (*++rhaystack != (a = *++needle))
-                     break;
-                   if (!a)
-                     goto foundneedle;
-                 }
-               while (*++rhaystack == (a = *++needle));
-             needle = rneedle; /* took the register-poor aproach */
-           }
-           if (!a)
-             break;
-         }
-       }
-    }
-foundneedle:
-  return (char *) haystack;
-ret0:
-  return 0;
+  /* 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, needle_len);
+  return two_way_long_needle ((const unsigned char *) haystack, haystack_len,
+                             (const unsigned char *) needle, needle_len);
 }
 libc_hidden_builtin_def (strstr)
+
+#undef LONG_NEEDLE_THRESHOLD