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