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 "malloca.h"
  29
  30 #define TOLOWER(Ch) (isupper (Ch) ? tolower (Ch) : (Ch))
  31
  32 /* Knuth-Morris-Pratt algorithm.  */
  33 #define CANON_ELEMENT(c) TOLOWER (c)
  34 #include "str-kmp.h"
  35
  36 /* Find the first occurrence of NEEDLE in HAYSTACK, using case-insensitive
  37    comparison.
  38    Note: This function may, in multibyte locales, return success even if
  39    strlen (haystack) < strlen (needle) !  */
  40 char *
  41 strcasestr (const char *haystack, const char *needle)
  42 {
  43   if (*needle != '\0')
  44     {
  45       /* Minimizing the worst-case complexity:
  46          Let n = strlen(haystack), m = strlen(needle).
  47          The naïve algorithm is O(n*m) worst-case.
  48          The Knuth-Morris-Pratt algorithm is O(n) worst-case but it needs a
  49          memory allocation.
  50          To achieve linear complexity and yet amortize the cost of the memory
  51          allocation, we activate the Knuth-Morris-Pratt algorithm only once
  52          the naïve algorithm has already run for some time; more precisely,
  53          when
  54            - the outer loop count is >= 10,
  55            - the average number of comparisons per outer loop is >= 5,
  56            - the total number of comparisons is >= m.
  57          But we try it only once.  If the memory allocation attempt failed,
  58          we don't retry it.  */
  59       bool try_kmp = true;
  60       size_t outer_loop_count = 0;
  61       size_t comparison_count = 0;
  62       size_t last_ccount = 0;                   /* last comparison count */
  63       const char *needle_last_ccount = needle;  /* = needle + last_ccount */
  64
  65       /* Speed up the following searches of needle by caching its first
  66          character.  */
  67       unsigned char b = TOLOWER ((unsigned char) *needle);
  68
  69       needle++;
  70       for (;; haystack++)
  71         {
  72           if (*haystack == '\0')
  73             /* No match.  */
  74             return NULL;
  75
  76           /* See whether it's advisable to use an asymptotically faster
  77              algorithm.  */
  78           if (try_kmp
  79               && outer_loop_count >= 10
  80               && comparison_count >= 5 * outer_loop_count)
  81             {
  82               /* See if needle + comparison_count now reaches the end of
  83                  needle.  */
  84               if (needle_last_ccount != NULL)
  85                 {
  86                   needle_last_ccount +=
  87                     strnlen (needle_last_ccount, comparison_count - last_ccount);
  88                   if (*needle_last_ccount == '\0')
  89                     needle_last_ccount = NULL;
  90                   last_ccount = comparison_count;
  91                 }
  92               if (needle_last_ccount == NULL)
  93                 {
  94                   /* Try the Knuth-Morris-Pratt algorithm.  */
  95                   const char *result;
  96                   bool success =
  97                     knuth_morris_pratt_unibyte (haystack, needle - 1, &result);
  98                   if (success)
  99                     return (char *) result;
 100                   try_kmp = false;
 101                 }
 102             }
 103
 104           outer_loop_count++;
 105           comparison_count++;
 106           if (TOLOWER ((unsigned char) *haystack) == b)
 107             /* The first character matches.  */
 108             {
 109               const char *rhaystack = haystack + 1;
 110               const char *rneedle = needle;
 111
 112               for (;; rhaystack++, rneedle++)
 113                 {
 114                   if (*rneedle == '\0')
 115                     /* Found a match.  */
 116                     return (char *) haystack;
 117                   if (*rhaystack == '\0')
 118                     /* No match.  */
 119                     return NULL;
 120                   comparison_count++;
 121                   if (TOLOWER ((unsigned char) *rhaystack)
 122                       != TOLOWER ((unsigned char) *rneedle))
 123                     /* Nothing in this round.  */
 124                     break;
 125                 }
 126             }
 127         }
 128     }
 129   else
 130     return (char *) haystack;
 131 }