X-Git-Url: http://erislabs.net/gitweb/?a=blobdiff_plain;f=lib%2Fstrstr.c;h=5bd7cb4658890734141a59c4e4f791f743b52876;hb=103b7cd6e6cc45a5aa570ad8c4d0aa6b0188b602;hp=c41e90349ff7b96be0cbcfdf2194649f551048b3;hpb=e6228399a12e9a92be1801283dd66ab3909ce0c2;p=gnulib.git diff --git a/lib/strstr.c b/lib/strstr.c index c41e90349..5bd7cb465 100644 --- a/lib/strstr.c +++ b/lib/strstr.c @@ -1,122 +1,126 @@ -/* Copyright (C) 1994, 1999 Free Software Foundation, Inc. -This file is part of the GNU C Library. +/* Searching in a string. + Copyright (C) 2005 Free Software Foundation, Inc. + Written by Bruno Haible , 2005. -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 -the Free Software Foundation; either version 2, or (at your option) -any later version. + 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 + the Free Software Foundation; either version 2, or (at your option) + any later version. -This program is distributed in the hope that it will be useful, -but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -GNU General Public License for more details. + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. -You should have received a copy of the GNU General Public License -along with this program; if not, write to the Free 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 */ + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software Foundation, + Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ #if HAVE_CONFIG_H # include #endif -#if defined _LIBC || defined HAVE_STRING_H -# include -#endif -#include - -typedef unsigned chartype; +/* Specification. */ +#include "strstr.h" -#undef strstr +#if HAVE_MBRTOWC +# include "mbuiter.h" +#endif +/* Find the first occurrence of NEEDLE in HAYSTACK. */ char * -strstr (const char *phaystack, const char *pneedle) +strstr (const char *haystack, const char *needle) { - register const unsigned char *haystack, *needle; - register chartype b, c; + /* Be careful not to look at the entire extent of haystack or needle + until needed. This is useful because of these two cases: + - haystack may be very long, and a match of needle found early, + - needle may be very long, and not even a short initial segment of + needle may be found in haystack. */ +#if HAVE_MBRTOWC + if (MB_CUR_MAX > 1) + { + mbui_iterator_t iter_needle; - haystack = (const unsigned char *) phaystack; - needle = (const unsigned char *) pneedle; + mbui_init (iter_needle, needle); + if (mbui_avail (iter_needle)) + { + mbui_iterator_t iter_haystack; - b = *needle; - if (b != '\0') + mbui_init (iter_haystack, haystack); + for (;; mbui_advance (iter_haystack)) + { + if (!mbui_avail (iter_haystack)) + /* No match. */ + return NULL; + + if (mb_equal (mbui_cur (iter_haystack), mbui_cur (iter_needle))) + /* The first character matches. */ + { + mbui_iterator_t rhaystack; + mbui_iterator_t rneedle; + + memcpy (&rhaystack, &iter_haystack, sizeof (mbui_iterator_t)); + mbui_advance (rhaystack); + + mbui_init (rneedle, needle); + if (!mbui_avail (rneedle)) + abort (); + mbui_advance (rneedle); + + for (;; mbui_advance (rhaystack), mbui_advance (rneedle)) + { + if (!mbui_avail (rneedle)) + /* Found a match. */ + return (char *) haystack; + if (!mbui_avail (rhaystack)) + /* No match. */ + return NULL; + if (!mb_equal (mbui_cur (rhaystack), mbui_cur (rneedle))) + /* Nothing in this round. */ + break; + } + } + } + } + else + return (char *) haystack; + } + else +#endif { - haystack--; /* possible ANSI violation */ - do + if (*needle != '\0') { - c = *++haystack; - if (c == '\0') - goto ret0; - } - while (c != b); - - c = *++needle; - if (c == '\0') - goto foundneedle; - ++needle; - goto jin; - - for (;;) - { - register chartype a; - register const unsigned char *rhaystack, *rneedle; + /* Speed up the following searches of needle by caching its first + character. */ + char b = *needle++; - do + for (;; haystack++) { - a = *++haystack; - if (a == '\0') - goto ret0; - if (a == b) - break; - a = *++haystack; - if (a == '\0') - goto ret0; -shloop:; } - while (a != b); - -jin: a = *++haystack; - if (a == '\0') - goto ret0; - - if (a != c) - goto shloop; - - rhaystack = haystack-- + 1; - rneedle = needle; - a = *rneedle; - - if (*rhaystack == a) - do - { - if (a == '\0') - goto foundneedle; - ++rhaystack; - a = *++needle; - if (*rhaystack != a) - break; - if (a == '\0') - goto foundneedle; - ++rhaystack; - a = *++needle; - } - while (*rhaystack == a); - - needle = rneedle; /* took the register-poor approach */ - - if (a == '\0') - break; - } + if (*haystack == '\0') + /* No match. */ + return NULL; + if (*haystack == b) + /* The first character matches. */ + { + const char *rhaystack = haystack + 1; + const char *rneedle = needle; + + for (;; rhaystack++, rneedle++) + { + if (*rneedle == '\0') + /* Found a match. */ + return (char *) haystack; + if (*rhaystack == '\0') + /* No match. */ + return NULL; + if (*rhaystack != *rneedle) + /* Nothing in this round. */ + break; + } + } + } + } + else + return (char *) haystack; } -foundneedle: - return (char*) haystack; -ret0: - return 0; }