lib/strcasestr.c

   1 /* Case-insensitive searching in a string.
   2    Copyright (C) 2005-2007 Free Software Foundation, Inc.
   3    Written by Bruno Haible <bruno@clisp.org>, 2005.
   4
   5    This program is free software; you can redistribute it and/or modify
   6    it under the terms of the GNU General Public License as published by
   7    the Free Software Foundation; either version 2, or (at your option)
   8    any later version.
   9
  10    This program is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13    GNU General Public License for more details.
  14
  15    You should have received a copy of the GNU General Public License
  16    along with this program; if not, write to the Free Software Foundation,
  17    Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
  18
  19 #include <config.h>
  20
  21 /* Specification.  */
  22 #include <string.h>
  23
  24 #include <ctype.h>
  25 #include <stdbool.h>
  26 #include <stddef.h>  /* for NULL, in case a nonstandard string.h lacks it */
  27
  28 #include "allocsa.h"
  29
  30 #define TOLOWER(Ch) (isupper (Ch) ? tolower (Ch) : (Ch))
  31
  32 /* Knuth-Morris-Pratt algorithm.
  33    See http://en.wikipedia.org/wiki/Knuth-Morris-Pratt_algorithm
  34    Return a boolean indicating success.  */
  35 static bool
  36 knuth_morris_pratt (const char *haystack, const char *needle,
  37                     const char **resultp)
  38 {
  39   size_t m = strlen (needle);
  40
  41   /* Allocate the table.  */
  42   size_t *table = (size_t *) allocsa (m * sizeof (size_t));
  43   if (table == NULL)
  44     return false;
  45   /* Fill the table.
  46      For 0 < i < m:
  47        0 < table[i] <= i is defined such that
  48        rhaystack[0..i-1] == needle[0..i-1] and rhaystack[i] != needle[i]
  49        implies
  50        forall 0 <= x < table[i]: rhaystack[x..x+m-1] != needle[0..m-1],
  51        and table[i] is as large as possible with this property.
  52      table[0] remains uninitialized.  */
  53   {
  54     size_t i, j;
  55
  56     table[1] = 1;
  57     j = 0;
  58     for (i = 2; i < m; i++)
  59       {
  60         unsigned char b = TOLOWER ((unsigned char) needle[i - 1]);
  61
  62         for (;;)
  63           {
  64             if (b == TOLOWER ((unsigned char) needle[j]))
  65               {
  66                 table[i] = i - ++j;
  67                 break;
  68               }
  69             if (j == 0)
  70               {
  71                 table[i] = i;
  72                 break;
  73               }
  74             j = j - table[j];
  75           }
  76       }
  77   }
  78
  79   /* Search, using the table to accelerate the processing.  */
  80   {
  81     size_t j;
  82     const char *rhaystack;
  83     const char *phaystack;
  84
  85     *resultp = NULL;
  86     j = 0;
  87     rhaystack = haystack;
  88     phaystack = haystack;
  89     /* Invariant: phaystack = rhaystack + j.  */
  90     while (*phaystack != '\0')
  91       if (TOLOWER ((unsigned char) needle[j])
  92           == TOLOWER ((unsigned char) *phaystack))
  93         {
  94           j++;
  95           phaystack++;
  96           if (j == m)
  97             {
  98               /* The entire needle has been found.  */
  99               *resultp = rhaystack;
 100               break;
 101             }
 102         }
 103       else if (j > 0)
 104         {
 105           /* Found a match of needle[0..j-1], mismatch at needle[j].  */
 106           rhaystack += table[j];
 107           j -= table[j];
 108         }
 109       else
 110         {
 111           /* Found a mismatch at needle[0] already.  */
 112           rhaystack++;
 113           phaystack++;
 114         }
 115   }
 116
 117   freesa (table);
 118   return true;
 119 }
 120
 121 /* Find the first occurrence of NEEDLE in HAYSTACK, using case-insensitive
 122    comparison.
 123    Note: This function may, in multibyte locales, return success even if
 124    strlen (haystack) < strlen (needle) !  */
 125 char *
 126 strcasestr (const char *haystack, const char *needle)
 127 {
 128   if (*needle != '\0')
 129     {
 130       /* Minimizing the worst-case complexity:
 131          Let n = strlen(haystack), m = strlen(needle).
 132          The naïve algorithm is O(n*m) worst-case.
 133          The Knuth-Morris-Pratt algorithm is O(n) worst-case but it needs a
 134          memory allocation.
 135          To achieve linear complexity and yet amortize the cost of the memory
 136          allocation, we activate the Knuth-Morris-Pratt algorithm only once
 137          the naïve algorithm has already run for some time; more precisely,
 138          when
 139            - the outer loop count is >= 10,
 140            - the average number of comparisons per outer loop is >= 5,
 141            - the total number of comparisons is >= m.
 142          But we try it only once.  If the memory allocation attempt failed,
 143          we don't retry it.  */
 144       bool try_kmp = true;
 145       size_t outer_loop_count = 0;
 146       size_t comparison_count = 0;
 147       size_t last_ccount = 0;                   /* last comparison count */
 148       const char *needle_last_ccount = needle;  /* = needle + last_ccount */
 149
 150       /* Speed up the following searches of needle by caching its first
 151          character.  */
 152       unsigned char b = TOLOWER ((unsigned char) *needle);
 153
 154       needle++;
 155       for (;; haystack++)
 156         {
 157           if (*haystack == '\0')
 158             /* No match.  */
 159             return NULL;
 160
 161           /* See whether it's advisable to use an asymptotically faster
 162              algorithm.  */
 163           if (try_kmp
 164               && outer_loop_count >= 10
 165               && comparison_count >= 5 * outer_loop_count)
 166             {
 167               /* See if needle + comparison_count now reaches the end of
 168                  needle.  */
 169               if (needle_last_ccount != NULL)
 170                 {
 171                   needle_last_ccount +=
 172                     strnlen (needle_last_ccount, comparison_count - last_ccount);
 173                   if (*needle_last_ccount == '\0')
 174                     needle_last_ccount = NULL;
 175                   last_ccount = comparison_count;
 176                 }
 177               if (needle_last_ccount == NULL)
 178                 {
 179                   /* Try the Knuth-Morris-Pratt algorithm.  */
 180                   const char *result;
 181                   bool success =
 182                     knuth_morris_pratt (haystack, needle - 1, &result);
 183                   if (success)
 184                     return (char *) result;
 185                   try_kmp = false;
 186                 }
 187             }
 188
 189           outer_loop_count++;
 190           comparison_count++;
 191           if (TOLOWER ((unsigned char) *haystack) == b)
 192             /* The first character matches.  */
 193             {
 194               const char *rhaystack = haystack + 1;
 195               const char *rneedle = needle;
 196
 197               for (;; rhaystack++, rneedle++)
 198                 {
 199                   if (*rneedle == '\0')
 200                     /* Found a match.  */
 201                     return (char *) haystack;
 202                   if (*rhaystack == '\0')
 203                     /* No match.  */
 204                     return NULL;
 205                   comparison_count++;
 206                   if (TOLOWER ((unsigned char) *rhaystack)
 207                       != TOLOWER ((unsigned char) *rneedle))
 208                     /* Nothing in this round.  */
 209                     break;
 210                 }
 211             }
 212         }
 213     }
 214   else
 215     return (char *) haystack;
 216 }