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