lib/sh/strstr.c

   1 /* strstr - find a substring within a string */
   2
   3 /* Copyright (C) 1994, 1999 Free Software Foundation, Inc.
   4
   5    This file is part of GNU Bash, the Bourne Again SHell.
   6
   7    Bash is free software: you can redistribute it and/or modify
   8    it under the terms of the GNU General Public License as published by
   9    the Free Software Foundation, either version 3 of the License, or
  10    (at your option) any later version.
  11
  12    Bash is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with Bash.  If not, see <http://www.gnu.org/licenses/>.
  19 */
  20
  21 /*
  22  * My personal strstr() implementation that beats most other algorithms.
  23  * Until someone tells me otherwise, I assume that this is the
  24  * fastest implementation of strstr() in C.
  25  * I deliberately chose not to comment it.  You should have at least
  26  * as much fun trying to understand it, as I had to write it :-).
  27  *
  28  * Stephen R. van den Berg, berg@pool.informatik.rwth-aachen.de */
  29
  30 #if HAVE_CONFIG_H
  31 # include <config.h>
  32 #endif
  33
  34 #if defined _LIBC || defined HAVE_STRING_H
  35 # include <string.h>
  36 #endif
  37 #include <sys/types.h>
  38
  39 typedef unsigned chartype;
  40
  41 #undef strstr
  42
  43 char *
  44 strstr (const char *phaystack, const char *pneedle)
  45 {
  46   register const unsigned char *haystack, *needle;
  47   register chartype b, c;
  48
  49   haystack = (const unsigned char *) phaystack;
  50   needle = (const unsigned char *) pneedle;
  51
  52   b = *needle;
  53   if (b != '\0')
  54     {
  55       haystack--;                               /* possible ANSI violation */
  56       do
  57         {
  58           c = *++haystack;
  59           if (c == '\0')
  60             goto ret0;
  61         }
  62       while (c != b);
  63
  64       c = *++needle;
  65       if (c == '\0')
  66         goto foundneedle;
  67       ++needle;
  68       goto jin;
  69
  70       for (;;)
  71         {
  72           register chartype a;
  73           register const unsigned char *rhaystack, *rneedle;
  74
  75           do
  76             {
  77               a = *++haystack;
  78               if (a == '\0')
  79                 goto ret0;
  80               if (a == b)
  81                 break;
  82               a = *++haystack;
  83               if (a == '\0')
  84                 goto ret0;
  85 shloop:;    }
  86           while (a != b);
  87
  88 jin:      a = *++haystack;
  89           if (a == '\0')
  90             goto ret0;
  91
  92           if (a != c)
  93             goto shloop;
  94
  95           rhaystack = haystack-- + 1;
  96           rneedle = needle;
  97           a = *rneedle;
  98
  99           if (*rhaystack == a)
 100             do
 101               {
 102                 if (a == '\0')
 103                   goto foundneedle;
 104                 ++rhaystack;
 105                 a = *++needle;
 106                 if (*rhaystack != a)
 107                   break;
 108                 if (a == '\0')
 109                   goto foundneedle;
 110                 ++rhaystack;
 111                 a = *++needle;
 112               }
 113             while (*rhaystack == a);
 114
 115           needle = rneedle;                /* took the register-poor approach */
 116
 117           if (a == '\0')
 118             break;
 119         }
 120     }
 121 foundneedle:
 122   return (char*) haystack;
 123 ret0:
 124   return 0;
 125 }