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