lib/c-strcasestr.c

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