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