lib/mbscasestr.c

   1 /* Case-insensitive searching in a string.
   2    Copyright (C) 2005-2008 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 <string.h>
  22
  23 #include <ctype.h>
  24 #include <stdbool.h>
  25 #include <stddef.h>  /* for NULL, in case a nonstandard string.h lacks it */
  26
  27 #include "malloca.h"
  28 #if HAVE_MBRTOWC
  29 # include "mbuiter.h"
  30 #endif
  31
  32 #define TOLOWER(Ch) (isupper (Ch) ? tolower (Ch) : (Ch))
  33
  34 /* Knuth-Morris-Pratt algorithm.  */
  35 #define CANON_ELEMENT(c) TOLOWER (c)
  36 #include "str-kmp.h"
  37
  38 #if HAVE_MBRTOWC
  39 /* Knuth-Morris-Pratt algorithm.
  40    See http://en.wikipedia.org/wiki/Knuth-Morris-Pratt_algorithm
  41    Return a boolean indicating success:
  42    Return true and set *RESULTP if the search was completed.
  43    Return false if it was aborted because not enough memory was available.  */
  44 static bool
  45 knuth_morris_pratt_multibyte (const char *haystack, const char *needle,
  46                               const char **resultp)
  47 {
  48   size_t m = mbslen (needle);
  49   mbchar_t *needle_mbchars;
  50   size_t *table;
  51
  52   /* Allocate room for needle_mbchars and the table.  */
  53   char *memory = (char *) nmalloca (m, sizeof (mbchar_t) + sizeof (size_t));
  54   if (memory == NULL)
  55     return false;
  56   needle_mbchars = (mbchar_t *) memory;
  57   table = (size_t *) (memory + m * sizeof (mbchar_t));
  58
  59   /* Fill needle_mbchars.  */
  60   {
  61     mbui_iterator_t iter;
  62     size_t j;
  63
  64     j = 0;
  65     for (mbui_init (iter, needle); mbui_avail (iter); mbui_advance (iter), j++)
  66       {
  67         mb_copy (&needle_mbchars[j], &mbui_cur (iter));
  68         if (needle_mbchars[j].wc_valid)
  69           needle_mbchars[j].wc = towlower (needle_mbchars[j].wc);
  70       }
  71   }
  72
  73   /* Fill the table.
  74      For 0 < i < m:
  75        0 < table[i] <= i is defined such that
  76        forall 0 < x < table[i]: needle[x..i-1] != needle[0..i-1-x],
  77        and table[i] is as large as possible with this property.
  78      This implies:
  79      1) For 0 < i < m:
  80           If table[i] < i,
  81           needle[table[i]..i-1] = needle[0..i-1-table[i]].
  82      2) For 0 < i < m:
  83           rhaystack[0..i-1] == needle[0..i-1]
  84           and exists h, i <= h < m: rhaystack[h] != needle[h]
  85           implies
  86           forall 0 <= x < table[i]: rhaystack[x..x+m-1] != needle[0..m-1].
  87      table[0] remains uninitialized.  */
  88   {
  89     size_t i, j;
  90
  91     /* i = 1: Nothing to verify for x = 0.  */
  92     table[1] = 1;
  93     j = 0;
  94
  95     for (i = 2; i < m; i++)
  96       {
  97         /* Here: j = i-1 - table[i-1].
  98            The inequality needle[x..i-1] != needle[0..i-1-x] is known to hold
  99            for x < table[i-1], by induction.
 100            Furthermore, if j>0: needle[i-1-j..i-2] = needle[0..j-1].  */
 101         mbchar_t *b = &needle_mbchars[i - 1];
 102
 103         for (;;)
 104           {
 105             /* Invariants: The inequality needle[x..i-1] != needle[0..i-1-x]
 106                is known to hold for x < i-1-j.
 107                Furthermore, if j>0: needle[i-1-j..i-2] = needle[0..j-1].  */
 108             if (mb_equal (*b, needle_mbchars[j]))
 109               {
 110                 /* Set table[i] := i-1-j.  */
 111                 table[i] = i - ++j;
 112                 break;
 113               }
 114             /* The inequality needle[x..i-1] != needle[0..i-1-x] also holds
 115                for x = i-1-j, because
 116                  needle[i-1] != needle[j] = needle[i-1-x].  */
 117             if (j == 0)
 118               {
 119                 /* The inequality holds for all possible x.  */
 120                 table[i] = i;
 121                 break;
 122               }
 123             /* The inequality needle[x..i-1] != needle[0..i-1-x] also holds
 124                for i-1-j < x < i-1-j+table[j], because for these x:
 125                  needle[x..i-2]
 126                  = needle[x-(i-1-j)..j-1]
 127                  != needle[0..j-1-(x-(i-1-j))]  (by definition of table[j])
 128                     = needle[0..i-2-x],
 129                hence needle[x..i-1] != needle[0..i-1-x].
 130                Furthermore
 131                  needle[i-1-j+table[j]..i-2]
 132                  = needle[table[j]..j-1]
 133                  = needle[0..j-1-table[j]]  (by definition of table[j]).  */
 134             j = j - table[j];
 135           }
 136         /* Here: j = i - table[i].  */
 137       }
 138   }
 139
 140   /* Search, using the table to accelerate the processing.  */
 141   {
 142     size_t j;
 143     mbui_iterator_t rhaystack;
 144     mbui_iterator_t phaystack;
 145
 146     *resultp = NULL;
 147     j = 0;
 148     mbui_init (rhaystack, haystack);
 149     mbui_init (phaystack, haystack);
 150     /* Invariant: phaystack = rhaystack + j.  */
 151     while (mbui_avail (phaystack))
 152       {
 153         mbchar_t c;
 154
 155         mb_copy (&c, &mbui_cur (phaystack));
 156         if (c.wc_valid)
 157           c.wc = towlower (c.wc);
 158         if (mb_equal (needle_mbchars[j], c))
 159           {
 160             j++;
 161             mbui_advance (phaystack);
 162             if (j == m)
 163               {
 164                 /* The entire needle has been found.  */
 165                 *resultp = mbui_cur_ptr (rhaystack);
 166                 break;
 167               }
 168           }
 169         else if (j > 0)
 170           {
 171             /* Found a match of needle[0..j-1], mismatch at needle[j].  */
 172             size_t count = table[j];
 173             j -= count;
 174             for (; count > 0; count--)
 175               {
 176                 if (!mbui_avail (rhaystack))
 177                   abort ();
 178                 mbui_advance (rhaystack);
 179               }
 180           }
 181         else
 182           {
 183             /* Found a mismatch at needle[0] already.  */
 184             if (!mbui_avail (rhaystack))
 185               abort ();
 186             mbui_advance (rhaystack);
 187             mbui_advance (phaystack);
 188           }
 189       }
 190   }
 191
 192   freea (memory);
 193   return true;
 194 }
 195 #endif
 196
 197 /* Find the first occurrence of the character string NEEDLE in the character
 198    string HAYSTACK, using case-insensitive comparison.
 199    Note: This function may, in multibyte locales, return success even if
 200    strlen (haystack) < strlen (needle) !  */
 201 char *
 202 mbscasestr (const char *haystack, const char *needle)
 203 {
 204   /* Be careful not to look at the entire extent of haystack or needle
 205      until needed.  This is useful because of these two cases:
 206        - haystack may be very long, and a match of needle found early,
 207        - needle may be very long, and not even a short initial segment of
 208          needle may be found in haystack.  */
 209 #if HAVE_MBRTOWC
 210   if (MB_CUR_MAX > 1)
 211     {
 212       mbui_iterator_t iter_needle;
 213
 214       mbui_init (iter_needle, needle);
 215       if (mbui_avail (iter_needle))
 216         {
 217           /* Minimizing the worst-case complexity:
 218              Let n = mbslen(haystack), m = mbslen(needle).
 219              The naïve algorithm is O(n*m) worst-case.
 220              The Knuth-Morris-Pratt algorithm is O(n) worst-case but it needs a
 221              memory allocation.
 222              To achieve linear complexity and yet amortize the cost of the
 223              memory allocation, we activate the Knuth-Morris-Pratt algorithm
 224              only once the naïve algorithm has already run for some time; more
 225              precisely, when
 226                - the outer loop count is >= 10,
 227                - the average number of comparisons per outer loop is >= 5,
 228                - the total number of comparisons is >= m.
 229              But we try it only once.  If the memory allocation attempt failed,
 230              we don't retry it.  */
 231           bool try_kmp = true;
 232           size_t outer_loop_count = 0;
 233           size_t comparison_count = 0;
 234           size_t last_ccount = 0;                  /* last comparison count */
 235           mbui_iterator_t iter_needle_last_ccount; /* = needle + last_ccount */
 236
 237           mbchar_t b;
 238           mbui_iterator_t iter_haystack;
 239
 240           mbui_init (iter_needle_last_ccount, needle);
 241
 242           mb_copy (&b, &mbui_cur (iter_needle));
 243           if (b.wc_valid)
 244             b.wc = towlower (b.wc);
 245
 246           mbui_init (iter_haystack, haystack);
 247           for (;; mbui_advance (iter_haystack))
 248             {
 249               mbchar_t c;
 250
 251               if (!mbui_avail (iter_haystack))
 252                 /* No match.  */
 253                 return NULL;
 254
 255               /* See whether it's advisable to use an asymptotically faster
 256                  algorithm.  */
 257               if (try_kmp
 258                   && outer_loop_count >= 10
 259                   && comparison_count >= 5 * outer_loop_count)
 260                 {
 261                   /* See if needle + comparison_count now reaches the end of
 262                      needle.  */
 263                   size_t count = comparison_count - last_ccount;
 264                   for (;
 265                        count > 0 && mbui_avail (iter_needle_last_ccount);
 266                        count--)
 267                     mbui_advance (iter_needle_last_ccount);
 268                   last_ccount = comparison_count;
 269                   if (!mbui_avail (iter_needle_last_ccount))
 270                     {
 271                       /* Try the Knuth-Morris-Pratt algorithm.  */
 272                       const char *result;
 273                       bool success =
 274                         knuth_morris_pratt_multibyte (haystack, needle,
 275                                                       &result);
 276                       if (success)
 277                         return (char *) result;
 278                       try_kmp = false;
 279                     }
 280                 }
 281
 282               outer_loop_count++;
 283               comparison_count++;
 284               mb_copy (&c, &mbui_cur (iter_haystack));
 285               if (c.wc_valid)
 286                 c.wc = towlower (c.wc);
 287               if (mb_equal (c, b))
 288                 /* The first character matches.  */
 289                 {
 290                   mbui_iterator_t rhaystack;
 291                   mbui_iterator_t rneedle;
 292
 293                   memcpy (&rhaystack, &iter_haystack, sizeof (mbui_iterator_t));
 294                   mbui_advance (rhaystack);
 295
 296                   mbui_init (rneedle, needle);
 297                   if (!mbui_avail (rneedle))
 298                     abort ();
 299                   mbui_advance (rneedle);
 300
 301                   for (;; mbui_advance (rhaystack), mbui_advance (rneedle))
 302                     {
 303                       if (!mbui_avail (rneedle))
 304                         /* Found a match.  */
 305                         return (char *) mbui_cur_ptr (iter_haystack);
 306                       if (!mbui_avail (rhaystack))
 307                         /* No match.  */
 308                         return NULL;
 309                       comparison_count++;
 310                       if (!mb_caseequal (mbui_cur (rhaystack),
 311                                          mbui_cur (rneedle)))
 312                         /* Nothing in this round.  */
 313                         break;
 314                     }
 315                 }
 316             }
 317         }
 318       else
 319         return (char *) haystack;
 320     }
 321   else
 322 #endif
 323     {
 324       if (*needle != '\0')
 325         {
 326           /* Minimizing the worst-case complexity:
 327              Let n = strlen(haystack), m = strlen(needle).
 328              The naïve algorithm is O(n*m) worst-case.
 329              The Knuth-Morris-Pratt algorithm is O(n) worst-case but it needs a
 330              memory allocation.
 331              To achieve linear complexity and yet amortize the cost of the
 332              memory allocation, we activate the Knuth-Morris-Pratt algorithm
 333              only once the naïve algorithm has already run for some time; more
 334              precisely, when
 335                - the outer loop count is >= 10,
 336                - the average number of comparisons per outer loop is >= 5,
 337                - the total number of comparisons is >= m.
 338              But we try it only once.  If the memory allocation attempt failed,
 339              we don't retry it.  */
 340           bool try_kmp = true;
 341           size_t outer_loop_count = 0;
 342           size_t comparison_count = 0;
 343           size_t last_ccount = 0;                  /* last comparison count */
 344           const char *needle_last_ccount = needle; /* = needle + last_ccount */
 345
 346           /* Speed up the following searches of needle by caching its first
 347              character.  */
 348           unsigned char b = TOLOWER ((unsigned char) *needle);
 349
 350           needle++;
 351           for (;; haystack++)
 352             {
 353               if (*haystack == '\0')
 354                 /* No match.  */
 355                 return NULL;
 356
 357               /* See whether it's advisable to use an asymptotically faster
 358                  algorithm.  */
 359               if (try_kmp
 360                   && outer_loop_count >= 10
 361                   && comparison_count >= 5 * outer_loop_count)
 362                 {
 363                   /* See if needle + comparison_count now reaches the end of
 364                      needle.  */
 365                   if (needle_last_ccount != NULL)
 366                     {
 367                       needle_last_ccount +=
 368                         strnlen (needle_last_ccount,
 369                                  comparison_count - last_ccount);
 370                       if (*needle_last_ccount == '\0')
 371                         needle_last_ccount = NULL;
 372                       last_ccount = comparison_count;
 373                     }
 374                   if (needle_last_ccount == NULL)
 375                     {
 376                       /* Try the Knuth-Morris-Pratt algorithm.  */
 377                       const char *result;
 378                       bool success =
 379                         knuth_morris_pratt_unibyte (haystack, needle - 1,
 380                                                     &result);
 381                       if (success)
 382                         return (char *) result;
 383                       try_kmp = false;
 384                     }
 385                 }
 386
 387               outer_loop_count++;
 388               comparison_count++;
 389               if (TOLOWER ((unsigned char) *haystack) == b)
 390                 /* The first character matches.  */
 391                 {
 392                   const char *rhaystack = haystack + 1;
 393                   const char *rneedle = needle;
 394
 395                   for (;; rhaystack++, rneedle++)
 396                     {
 397                       if (*rneedle == '\0')
 398                         /* Found a match.  */
 399                         return (char *) haystack;
 400                       if (*rhaystack == '\0')
 401                         /* No match.  */
 402                         return NULL;
 403                       comparison_count++;
 404                       if (TOLOWER ((unsigned char) *rhaystack)
 405                           != TOLOWER ((unsigned char) *rneedle))
 406                         /* Nothing in this round.  */
 407                         break;
 408                     }
 409                 }
 410             }
 411         }
 412       else
 413         return (char *) haystack;
 414     }
 415 }