1 /* -*- buffer-read-only: t -*- vi: set ro: */
2 /* DO NOT EDIT! GENERATED AUTOMATICALLY! */
3 /* Substring search in a NUL terminated string of 'char' elements,
4 using the Knuth-Morris-Pratt algorithm.
5 Copyright (C) 2005-2010 Free Software Foundation, Inc.
6 Written by Bruno Haible <bruno@clisp.org>, 2005.
8 This program is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
13 This program is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with this program; if not, write to the Free Software Foundation,
20 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
22 /* Before including this file, you need to define:
23 CANON_ELEMENT(c) A macro that canonicalizes an element right after
24 it has been fetched from one of the two strings.
25 The argument is an 'unsigned char'; the result
26 must be an 'unsigned char' as well. */
28 /* Knuth-Morris-Pratt algorithm.
29 See http://en.wikipedia.org/wiki/Knuth-Morris-Pratt_algorithm
30 Return a boolean indicating success:
31 Return true and set *RESULTP if the search was completed.
32 Return false if it was aborted because not enough memory was available. */
34 knuth_morris_pratt_unibyte (const char *haystack, const char *needle,
37 size_t m = strlen (needle);
39 /* Allocate the table. */
40 size_t *table = (size_t *) nmalloca (m, sizeof (size_t));
45 0 < table[i] <= i is defined such that
46 forall 0 < x < table[i]: needle[x..i-1] != needle[0..i-1-x],
47 and table[i] is as large as possible with this property.
51 needle[table[i]..i-1] = needle[0..i-1-table[i]].
53 rhaystack[0..i-1] == needle[0..i-1]
54 and exists h, i <= h < m: rhaystack[h] != needle[h]
56 forall 0 <= x < table[i]: rhaystack[x..x+m-1] != needle[0..m-1].
57 table[0] remains uninitialized. */
61 /* i = 1: Nothing to verify for x = 0. */
65 for (i = 2; i < m; i++)
67 /* Here: j = i-1 - table[i-1].
68 The inequality needle[x..i-1] != needle[0..i-1-x] is known to hold
69 for x < table[i-1], by induction.
70 Furthermore, if j>0: needle[i-1-j..i-2] = needle[0..j-1]. */
71 unsigned char b = CANON_ELEMENT ((unsigned char) needle[i - 1]);
75 /* Invariants: The inequality needle[x..i-1] != needle[0..i-1-x]
76 is known to hold for x < i-1-j.
77 Furthermore, if j>0: needle[i-1-j..i-2] = needle[0..j-1]. */
78 if (b == CANON_ELEMENT ((unsigned char) needle[j]))
80 /* Set table[i] := i-1-j. */
84 /* The inequality needle[x..i-1] != needle[0..i-1-x] also holds
85 for x = i-1-j, because
86 needle[i-1] != needle[j] = needle[i-1-x]. */
89 /* The inequality holds for all possible x. */
93 /* The inequality needle[x..i-1] != needle[0..i-1-x] also holds
94 for i-1-j < x < i-1-j+table[j], because for these x:
96 = needle[x-(i-1-j)..j-1]
97 != needle[0..j-1-(x-(i-1-j))] (by definition of table[j])
99 hence needle[x..i-1] != needle[0..i-1-x].
101 needle[i-1-j+table[j]..i-2]
102 = needle[table[j]..j-1]
103 = needle[0..j-1-table[j]] (by definition of table[j]). */
106 /* Here: j = i - table[i]. */
110 /* Search, using the table to accelerate the processing. */
113 const char *rhaystack;
114 const char *phaystack;
118 rhaystack = haystack;
119 phaystack = haystack;
120 /* Invariant: phaystack = rhaystack + j. */
121 while (*phaystack != '\0')
122 if (CANON_ELEMENT ((unsigned char) needle[j])
123 == CANON_ELEMENT ((unsigned char) *phaystack))
129 /* The entire needle has been found. */
130 *resultp = rhaystack;
136 /* Found a match of needle[0..j-1], mismatch at needle[j]. */
137 rhaystack += table[j];
142 /* Found a mismatch at needle[0] already. */