lib/c-strcasestr.c

   1 /* c-strcasestr.c -- case insensitive substring search in C locale
   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 3 of the License, or
   8    (at your option) 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, see <http://www.gnu.org/licenses/>.  */
  17
  18 #include <config.h>
  19
  20 /* Specification.  */
  21 #include "c-strcasestr.h"
  22
  23 #include <stdbool.h>
  24 #include <stddef.h>
  25 #include <string.h>
  26
  27 #include "malloca.h"
  28 #include "c-ctype.h"
  29
  30 /* Knuth-Morris-Pratt algorithm.
  31    See http://en.wikipedia.org/wiki/Knuth-Morris-Pratt_algorithm
  32    Return a boolean indicating success.  */
  33 static bool
  34 knuth_morris_pratt (const char *haystack, const char *needle,
  35                     const char **resultp)
  36 {
  37   size_t m = strlen (needle);
  38
  39   /* Allocate the table.  */
  40   size_t *table = (size_t *) nmalloca (m, sizeof (size_t));
  41   if (table == NULL)
  42     return false;
  43   /* Fill the table.
  44      For 0 < i < m:
  45        0 < table[i] <= i is defined such that
  46        forall 0 < x < table[i]: needle[x..i-1] != needle[0..i-1-x],
  47        and table[i] is as large as possible with this property.
  48      This implies:
  49      1) For 0 < i < m:
  50           If table[i] < i,
  51           needle[table[i]..i-1] = needle[0..i-1-table[i]].
  52      2) For 0 < i < m:
  53           rhaystack[0..i-1] == needle[0..i-1]
  54           and exists h, i <= h < m: rhaystack[h] != needle[h]
  55           implies
  56           forall 0 <= x < table[i]: rhaystack[x..x+m-1] != needle[0..m-1].
  57      table[0] remains uninitialized.  */
  58   {
  59     size_t i, j;
  60
  61     /* i = 1: Nothing to verify for x = 0.  */
  62     table[1] = 1;
  63     j = 0;
  64
  65     for (i = 2; i < m; i++)
  66       {
  67         /* Here: j = i-1 - table[i-1].
  68            The inequality needle[x..i-1] != needle[0..i-1-x] is known to hold
  69            for x < table[i-1], by induction.
  70            Furthermore, if j>0: needle[i-1-j..i-2] = needle[0..j-1].  */
  71         unsigned char b = c_tolower ((unsigned char) needle[i - 1]);
  72
  73         for (;;)
  74           {
  75             /* Invariants: The inequality needle[x..i-1] != needle[0..i-1-x]
  76                is known to hold for x < i-1-j.
  77                Furthermore, if j>0: needle[i-1-j..i-2] = needle[0..j-1].  */
  78             if (b == c_tolower ((unsigned char) needle[j]))
  79               {
  80                 /* Set table[i] := i-1-j.  */
  81                 table[i] = i - ++j;
  82                 break;
  83               }
  84             /* The inequality needle[x..i-1] != needle[0..i-1-x] also holds
  85                for x = i-1-j, because
  86                  needle[i-1] != needle[j] = needle[i-1-x].  */
  87             if (j == 0)
  88               {
  89                 /* The inequality holds for all possible x.  */
  90                 table[i] = i;
  91                 break;
  92               }
  93             /* The inequality needle[x..i-1] != needle[0..i-1-x] also holds
  94                for i-1-j < x < i-1-j+table[j], because for these x:
  95                  needle[x..i-2]
  96                  = needle[x-(i-1-j)..j-1]
  97                  != needle[0..j-1-(x-(i-1-j))]  (by definition of table[j])
  98                     = needle[0..i-2-x],
  99                hence needle[x..i-1] != needle[0..i-1-x].
 100                Furthermore
 101                  needle[i-1-j+table[j]..i-2]
 102                  = needle[table[j]..j-1]
 103                  = needle[0..j-1-table[j]]  (by definition of table[j]).  */
 104             j = j - table[j];
 105           }
 106         /* Here: j = i - table[i].  */
 107       }
 108   }
 109
 110   /* Search, using the table to accelerate the processing.  */
 111   {
 112     size_t j;
 113     const char *rhaystack;
 114     const char *phaystack;
 115
 116     *resultp = NULL;
 117     j = 0;
 118     rhaystack = haystack;
 119     phaystack = haystack;
 120     /* Invariant: phaystack = rhaystack + j.  */
 121     while (*phaystack != '\0')
 122       if (c_tolower ((unsigned char) needle[j])
 123           == c_tolower ((unsigned char) *phaystack))
 124         {
 125           j++;
 126           phaystack++;
 127           if (j == m)
 128             {
 129               /* The entire needle has been found.  */
 130               *resultp = rhaystack;
 131               break;
 132             }
 133         }
 134       else if (j > 0)
 135         {
 136           /* Found a match of needle[0..j-1], mismatch at needle[j].  */
 137           rhaystack += table[j];
 138           j -= table[j];
 139         }
 140       else
 141         {
 142           /* Found a mismatch at needle[0] already.  */
 143           rhaystack++;
 144           phaystack++;
 145         }
 146   }
 147
 148   freea (table);
 149   return true;
 150 }
 151
 152 /* Find the first occurrence of NEEDLE in HAYSTACK, using case-insensitive
 153    comparison.
 154    Note: This function may, in multibyte locales, return success even if
 155    strlen (haystack) < strlen (needle) !  */
 156 char *
 157 c_strcasestr (const char *haystack, const char *needle)
 158 {
 159   /* Be careful not to look at the entire extent of haystack or needle
 160      until needed.  This is useful because of these two cases:
 161        - haystack may be very long, and a match of needle found early,
 162        - needle may be very long, and not even a short initial segment of
 163          needle may be found in haystack.  */
 164   if (*needle != '\0')
 165     {
 166       /* Minimizing the worst-case complexity:
 167          Let n = strlen(haystack), m = strlen(needle).
 168          The naïve algorithm is O(n*m) worst-case.
 169          The Knuth-Morris-Pratt algorithm is O(n) worst-case but it needs a
 170          memory allocation.
 171          To achieve linear complexity and yet amortize the cost of the memory
 172          allocation, we activate the Knuth-Morris-Pratt algorithm only once
 173          the naïve algorithm has already run for some time; more precisely,
 174          when
 175            - the outer loop count is >= 10,
 176            - the average number of comparisons per outer loop is >= 5,
 177            - the total number of comparisons is >= m.
 178          But we try it only once.  If the memory allocation attempt failed,
 179          we don't retry it.  */
 180       bool try_kmp = true;
 181       size_t outer_loop_count = 0;
 182       size_t comparison_count = 0;
 183       size_t last_ccount = 0;                   /* last comparison count */
 184       const char *needle_last_ccount = needle;  /* = needle + last_ccount */
 185
 186       /* Speed up the following searches of needle by caching its first
 187          character.  */
 188       unsigned char b = c_tolower ((unsigned char) *needle);
 189
 190       needle++;
 191       for (;; haystack++)
 192         {
 193           if (*haystack == '\0')
 194             /* No match.  */
 195             return NULL;
 196
 197           /* See whether it's advisable to use an asymptotically faster
 198              algorithm.  */
 199           if (try_kmp
 200               && outer_loop_count >= 10
 201               && comparison_count >= 5 * outer_loop_count)
 202             {
 203               /* See if needle + comparison_count now reaches the end of
 204                  needle.  */
 205               if (needle_last_ccount != NULL)
 206                 {
 207                   needle_last_ccount +=
 208                     strnlen (needle_last_ccount, comparison_count - last_ccount);
 209                   if (*needle_last_ccount == '\0')
 210                     needle_last_ccount = NULL;
 211                   last_ccount = comparison_count;
 212                 }
 213               if (needle_last_ccount == NULL)
 214                 {
 215                   /* Try the Knuth-Morris-Pratt algorithm.  */
 216                   const char *result;
 217                   bool success =
 218                     knuth_morris_pratt (haystack, needle - 1, &result);
 219                   if (success)
 220                     return (char *) result;
 221                   try_kmp = false;
 222                 }
 223             }
 224
 225           outer_loop_count++;
 226           comparison_count++;
 227           if (c_tolower ((unsigned char) *haystack) == b)
 228             /* The first character matches.  */
 229             {
 230               const char *rhaystack = haystack + 1;
 231               const char *rneedle = needle;
 232
 233               for (;; rhaystack++, rneedle++)
 234                 {
 235                   if (*rneedle == '\0')
 236                     /* Found a match.  */
 237                     return (char *) haystack;
 238                   if (*rhaystack == '\0')
 239                     /* No match.  */
 240                     return NULL;
 241                   comparison_count++;
 242                   if (c_tolower ((unsigned char) *rhaystack)
 243                       != c_tolower ((unsigned char) *rneedle))
 244                     /* Nothing in this round.  */
 245                     break;
 246                 }
 247             }
 248         }
 249     }
 250   else
 251     return (char *) haystack;
 252 }