-/* 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
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
/* 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)
/* 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
projects / kopensolaris-gnu / glibc.git / commitdiff