diff options
author | Bruno Haible <bruno@clisp.org> | 2007-12-31 11:57:16 +0100 |
---|---|---|
committer | Bruno Haible <bruno@clisp.org> | 2007-12-31 11:57:16 +0100 |
commit | 7855e1e3a12ea5e158d51b9ab7f38006ac5fc028 (patch) | |
tree | 6aa4176a242031cd3949d88f5f613e99c2bbf9aa /lib/c-strstr.c | |
parent | f4637bbf9a6a5f1d3c5390fdab23882c25dfe464 (diff) | |
download | gnulib-7855e1e3a12ea5e158d51b9ab7f38006ac5fc028.tar.gz |
Unify 5 copies of the KMP code.
Diffstat (limited to 'lib/c-strstr.c')
-rw-r--r-- | lib/c-strstr.c | 125 |
1 files changed, 4 insertions, 121 deletions
diff --git a/lib/c-strstr.c b/lib/c-strstr.c index 3652100e62..47226c3d47 100644 --- a/lib/c-strstr.c +++ b/lib/c-strstr.c @@ -26,126 +26,9 @@ #include "malloca.h" -/* Knuth-Morris-Pratt algorithm. - See http://en.wikipedia.org/wiki/Knuth-Morris-Pratt_algorithm - Return a boolean indicating success. */ -static bool -knuth_morris_pratt (const char *haystack, const char *needle, - const char **resultp) -{ - size_t m = strlen (needle); - - /* Allocate the table. */ - size_t *table = (size_t *) nmalloca (m, sizeof (size_t)); - if (table == NULL) - return false; - /* Fill the table. - For 0 < i < m: - 0 < table[i] <= i is defined such that - forall 0 < x < table[i]: needle[x..i-1] != needle[0..i-1-x], - and table[i] is as large as possible with this property. - This implies: - 1) For 0 < i < m: - If table[i] < i, - needle[table[i]..i-1] = needle[0..i-1-table[i]]. - 2) For 0 < i < m: - rhaystack[0..i-1] == needle[0..i-1] - and exists h, i <= h < m: rhaystack[h] != needle[h] - implies - forall 0 <= x < table[i]: rhaystack[x..x+m-1] != needle[0..m-1]. - table[0] remains uninitialized. */ - { - size_t i, j; - - /* i = 1: Nothing to verify for x = 0. */ - table[1] = 1; - j = 0; - - for (i = 2; i < m; i++) - { - /* Here: j = i-1 - table[i-1]. - The inequality needle[x..i-1] != needle[0..i-1-x] is known to hold - for x < table[i-1], by induction. - Furthermore, if j>0: needle[i-1-j..i-2] = needle[0..j-1]. */ - unsigned char b = (unsigned char) needle[i - 1]; - - for (;;) - { - /* Invariants: The inequality needle[x..i-1] != needle[0..i-1-x] - is known to hold for x < i-1-j. - Furthermore, if j>0: needle[i-1-j..i-2] = needle[0..j-1]. */ - if (b == (unsigned char) needle[j]) - { - /* Set table[i] := i-1-j. */ - table[i] = i - ++j; - break; - } - /* The inequality needle[x..i-1] != needle[0..i-1-x] also holds - for x = i-1-j, because - needle[i-1] != needle[j] = needle[i-1-x]. */ - if (j == 0) - { - /* The inequality holds for all possible x. */ - table[i] = i; - break; - } - /* The inequality needle[x..i-1] != needle[0..i-1-x] also holds - for i-1-j < x < i-1-j+table[j], because for these x: - needle[x..i-2] - = needle[x-(i-1-j)..j-1] - != needle[0..j-1-(x-(i-1-j))] (by definition of table[j]) - = needle[0..i-2-x], - hence needle[x..i-1] != needle[0..i-1-x]. - Furthermore - needle[i-1-j+table[j]..i-2] - = needle[table[j]..j-1] - = needle[0..j-1-table[j]] (by definition of table[j]). */ - j = j - table[j]; - } - /* Here: j = i - table[i]. */ - } - } - - /* Search, using the table to accelerate the processing. */ - { - size_t j; - const char *rhaystack; - const char *phaystack; - - *resultp = NULL; - j = 0; - rhaystack = haystack; - phaystack = haystack; - /* Invariant: phaystack = rhaystack + j. */ - while (*phaystack != '\0') - if ((unsigned char) needle[j] == (unsigned char) *phaystack) - { - j++; - phaystack++; - if (j == m) - { - /* The entire needle has been found. */ - *resultp = rhaystack; - break; - } - } - else if (j > 0) - { - /* Found a match of needle[0..j-1], mismatch at needle[j]. */ - rhaystack += table[j]; - j -= table[j]; - } - else - { - /* Found a mismatch at needle[0] already. */ - rhaystack++; - phaystack++; - } - } - - freea (table); - return true; -} +/* Knuth-Morris-Pratt algorithm. */ +#define CANON_ELEMENT(c) c +#include "str-kmp.h" /* Find the first occurrence of NEEDLE in HAYSTACK. */ char * @@ -210,7 +93,7 @@ c_strstr (const char *haystack, const char *needle) /* Try the Knuth-Morris-Pratt algorithm. */ const char *result; bool success = - knuth_morris_pratt (haystack, needle - 1, &result); + knuth_morris_pratt_unibyte (haystack, needle - 1, &result); if (success) return (char *) result; try_kmp = false; |