lib/c-strstr.c

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