diff options
Diffstat (limited to 'lib/str-two-way.h')
| -rw-r--r-- | lib/str-two-way.h | 452 |
1 files changed, 0 insertions, 452 deletions
diff --git a/lib/str-two-way.h b/lib/str-two-way.h deleted file mode 100644 index 44225176..00000000 --- a/lib/str-two-way.h +++ /dev/null @@ -1,452 +0,0 @@ -/* Byte-wise substring search, using the Two-Way algorithm. - Copyright (C) 2008-2015 Free Software Foundation, Inc. - This file is part of the GNU C Library. - Written by Eric Blake <ebb9@byu.net>, 2008. - - This program is free software; you can redistribute it and/or modify - it under the terms of the GNU Lesser General Public License as published by - the Free Software Foundation; either version 2, or (at your option) - any later version. - - This program is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU Lesser General Public License for more details. - - You should have received a copy of the GNU Lesser General Public License along - with this program; if not, see <http://www.gnu.org/licenses/>. */ - -/* Before including this file, you need to include <config.h> and - <string.h>, and define: - RESULT_TYPE A macro that expands to the return type. - AVAILABLE(h, h_l, j, n_l) - A macro that returns nonzero if there are - at least N_L bytes left starting at H[J]. - H is 'unsigned char *', H_L, J, and N_L - are 'size_t'; H_L is an lvalue. For - NUL-terminated searches, H_L can be - modified each iteration to avoid having - to compute the end of H up front. - - For case-insensitivity, you may optionally define: - CMP_FUNC(p1, p2, l) A macro that returns 0 iff the first L - characters of P1 and P2 are equal. - CANON_ELEMENT(c) A macro that canonicalizes an element right after - it has been fetched from one of the two strings. - The argument is an 'unsigned char'; the result - must be an 'unsigned char' as well. - - This file undefines the macros documented above, and defines - LONG_NEEDLE_THRESHOLD. -*/ - -#include <limits.h> -#include <stdint.h> - -/* We use the Two-Way string matching algorithm (also known as - Chrochemore-Perrin), which guarantees linear complexity with - constant space. Additionally, for long needles, we also use a bad - character shift table similar to the Boyer-Moore algorithm to - achieve improved (potentially sub-linear) performance. - - See http://www-igm.univ-mlv.fr/~lecroq/string/node26.html#SECTION00260, - http://en.wikipedia.org/wiki/Boyer-Moore_string_search_algorithm, - http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.34.6641&rep=rep1&type=pdf -*/ - -/* Point at which computing a bad-byte shift table is likely to be - worthwhile. Small needles should not compute a table, since it - adds (1 << CHAR_BIT) + NEEDLE_LEN computations of preparation for a - speedup no greater than a factor of NEEDLE_LEN. The larger the - needle, the better the potential performance gain. On the other - hand, on non-POSIX systems with CHAR_BIT larger than eight, the - memory required for the table is prohibitive. */ -#if CHAR_BIT < 10 -# define LONG_NEEDLE_THRESHOLD 32U -#else -# define LONG_NEEDLE_THRESHOLD SIZE_MAX -#endif - -#ifndef MAX -# define MAX(a, b) ((a < b) ? (b) : (a)) -#endif - -#ifndef CANON_ELEMENT -# define CANON_ELEMENT(c) c -#endif -#ifndef CMP_FUNC -# define CMP_FUNC memcmp -#endif - -/* Perform a critical factorization of NEEDLE, of length NEEDLE_LEN. - Return the index of the first byte in the right half, and set - *PERIOD to the global period of the right half. - - The global period of a string is the smallest index (possibly its - length) at which all remaining bytes in the string are repetitions - of the prefix (the last repetition may be a subset of the prefix). - - When NEEDLE is factored into two halves, a local period is the - length of the smallest word that shares a suffix with the left half - and shares a prefix with the right half. All factorizations of a - non-empty NEEDLE have a local period of at least 1 and no greater - than NEEDLE_LEN. - - A critical factorization has the property that the local period - equals the global period. All strings have at least one critical - factorization with the left half smaller than the global period. - And while some strings have more than one critical factorization, - it is provable that with an ordered alphabet, at least one of the - critical factorizations corresponds to a maximal suffix. - - Given an ordered alphabet, a critical factorization can be computed - in linear time, with 2 * NEEDLE_LEN comparisons, by computing the - shorter of two ordered maximal suffixes. The ordered maximal - suffixes are determined by lexicographic comparison while tracking - periodicity. */ -static size_t -critical_factorization (const unsigned char *needle, size_t needle_len, - size_t *period) -{ - /* Index of last byte of left half, or SIZE_MAX. */ - size_t max_suffix, max_suffix_rev; - size_t j; /* Index into NEEDLE for current candidate suffix. */ - size_t k; /* Offset into current period. */ - size_t p; /* Intermediate period. */ - unsigned char a, b; /* Current comparison bytes. */ - - /* Special case NEEDLE_LEN of 1 or 2 (all callers already filtered - out 0-length needles. */ - if (needle_len < 3) - { - *period = 1; - return needle_len - 1; - } - - /* Invariants: - 0 <= j < NEEDLE_LEN - 1 - -1 <= max_suffix{,_rev} < j (treating SIZE_MAX as if it were signed) - min(max_suffix, max_suffix_rev) < global period of NEEDLE - 1 <= p <= global period of NEEDLE - p == global period of the substring NEEDLE[max_suffix{,_rev}+1...j] - 1 <= k <= p - */ - - /* Perform lexicographic search. */ - max_suffix = SIZE_MAX; - j = 0; - k = p = 1; - while (j + k < needle_len) - { - a = CANON_ELEMENT (needle[j + k]); - b = CANON_ELEMENT (needle[max_suffix + k]); - if (a < b) - { - /* Suffix is smaller, period is entire prefix so far. */ - j += k; - k = 1; - p = j - max_suffix; - } - else if (a == b) - { - /* Advance through repetition of the current period. */ - if (k != p) - ++k; - else - { - j += p; - k = 1; - } - } - else /* b < a */ - { - /* Suffix is larger, start over from current location. */ - max_suffix = j++; - k = p = 1; - } - } - *period = p; - - /* Perform reverse lexicographic search. */ - max_suffix_rev = SIZE_MAX; - j = 0; - k = p = 1; - while (j + k < needle_len) - { - a = CANON_ELEMENT (needle[j + k]); - b = CANON_ELEMENT (needle[max_suffix_rev + k]); - if (b < a) - { - /* Suffix is smaller, period is entire prefix so far. */ - j += k; - k = 1; - p = j - max_suffix_rev; - } - else if (a == b) - { - /* Advance through repetition of the current period. */ - if (k != p) - ++k; - else - { - j += p; - k = 1; - } - } - else /* a < b */ - { - /* Suffix is larger, start over from current location. */ - max_suffix_rev = j++; - k = p = 1; - } - } - - /* Choose the shorter suffix. Return the index of the first byte of - the right half, rather than the last byte of the left half. - - For some examples, 'banana' has two critical factorizations, both - exposed by the two lexicographic extreme suffixes of 'anana' and - 'nana', where both suffixes have a period of 2. On the other - hand, with 'aab' and 'bba', both strings have a single critical - factorization of the last byte, with the suffix having a period - of 1. While the maximal lexicographic suffix of 'aab' is 'b', - the maximal lexicographic suffix of 'bba' is 'ba', which is not a - critical factorization. Conversely, the maximal reverse - lexicographic suffix of 'a' works for 'bba', but not 'ab' for - 'aab'. The shorter suffix of the two will always be a critical - factorization. */ - if (max_suffix_rev + 1 < max_suffix + 1) - return max_suffix + 1; - *period = p; - return max_suffix_rev + 1; -} - -/* Return the first location of non-empty NEEDLE within HAYSTACK, or - NULL. HAYSTACK_LEN is the minimum known length of HAYSTACK. This - method is optimized for NEEDLE_LEN < LONG_NEEDLE_THRESHOLD. - Performance is guaranteed to be linear, with an initialization cost - of 2 * NEEDLE_LEN comparisons. - - If AVAILABLE does not modify HAYSTACK_LEN (as in memmem), then at - most 2 * HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching. - If AVAILABLE modifies HAYSTACK_LEN (as in strstr), then at most 3 * - HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching. */ -static RETURN_TYPE -two_way_short_needle (const unsigned char *haystack, size_t haystack_len, - const unsigned char *needle, size_t needle_len) -{ - size_t i; /* Index into current byte of NEEDLE. */ - size_t j; /* Index into current window of HAYSTACK. */ - size_t period; /* The period of the right half of needle. */ - size_t suffix; /* The index of the right half of needle. */ - - /* Factor the needle into two halves, such that the left half is - smaller than the global period, and the right half is - periodic (with a period as large as NEEDLE_LEN - suffix). */ - suffix = critical_factorization (needle, needle_len, &period); - - /* Perform the search. Each iteration compares the right half - first. */ - if (CMP_FUNC (needle, needle + period, suffix) == 0) - { - /* Entire needle is periodic; a mismatch in the left half can - only advance by the period, so use memory to avoid rescanning - known occurrences of the period in the right half. */ - size_t memory = 0; - j = 0; - while (AVAILABLE (haystack, haystack_len, j, needle_len)) - { - /* Scan for matches in right half. */ - i = MAX (suffix, memory); - while (i < needle_len && (CANON_ELEMENT (needle[i]) - == CANON_ELEMENT (haystack[i + j]))) - ++i; - if (needle_len <= i) - { - /* Scan for matches in left half. */ - i = suffix - 1; - while (memory < i + 1 && (CANON_ELEMENT (needle[i]) - == CANON_ELEMENT (haystack[i + j]))) - --i; - if (i + 1 < memory + 1) - return (RETURN_TYPE) (haystack + j); - /* No match, so remember how many repetitions of period - on the right half were scanned. */ - j += period; - memory = needle_len - period; - } - else - { - j += i - suffix + 1; - memory = 0; - } - } - } - else - { - /* The two halves of needle are distinct; no extra memory is - required, and any mismatch results in a maximal shift. */ - period = MAX (suffix, needle_len - suffix) + 1; - j = 0; - while (AVAILABLE (haystack, haystack_len, j, needle_len)) - { - /* Scan for matches in right half. */ - i = suffix; - while (i < needle_len && (CANON_ELEMENT (needle[i]) - == CANON_ELEMENT (haystack[i + j]))) - ++i; - if (needle_len <= i) - { - /* Scan for matches in left half. */ - i = suffix - 1; - while (i != SIZE_MAX && (CANON_ELEMENT (needle[i]) - == CANON_ELEMENT (haystack[i + j]))) - --i; - if (i == SIZE_MAX) - return (RETURN_TYPE) (haystack + j); - j += period; - } - else - j += i - suffix + 1; - } - } - return NULL; -} - -/* Return the first location of non-empty NEEDLE within HAYSTACK, or - NULL. HAYSTACK_LEN is the minimum known length of HAYSTACK. This - method is optimized for LONG_NEEDLE_THRESHOLD <= NEEDLE_LEN. - Performance is guaranteed to be linear, with an initialization cost - of 3 * NEEDLE_LEN + (1 << CHAR_BIT) operations. - - If AVAILABLE does not modify HAYSTACK_LEN (as in memmem), then at - most 2 * HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching, - and sublinear performance O(HAYSTACK_LEN / NEEDLE_LEN) is possible. - If AVAILABLE modifies HAYSTACK_LEN (as in strstr), then at most 3 * - HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching, and - sublinear performance is not possible. */ -static RETURN_TYPE -two_way_long_needle (const unsigned char *haystack, size_t haystack_len, - const unsigned char *needle, size_t needle_len) -{ - size_t i; /* Index into current byte of NEEDLE. */ - size_t j; /* Index into current window of HAYSTACK. */ - size_t period; /* The period of the right half of needle. */ - size_t suffix; /* The index of the right half of needle. */ - size_t shift_table[1U << CHAR_BIT]; /* See below. */ - - /* Factor the needle into two halves, such that the left half is - smaller than the global period, and the right half is - periodic (with a period as large as NEEDLE_LEN - suffix). */ - suffix = critical_factorization (needle, needle_len, &period); - - /* Populate shift_table. For each possible byte value c, - shift_table[c] is the distance from the last occurrence of c to - the end of NEEDLE, or NEEDLE_LEN if c is absent from the NEEDLE. - shift_table[NEEDLE[NEEDLE_LEN - 1]] contains the only 0. */ - for (i = 0; i < 1U << CHAR_BIT; i++) - shift_table[i] = needle_len; - for (i = 0; i < needle_len; i++) - shift_table[CANON_ELEMENT (needle[i])] = needle_len - i - 1; - - /* Perform the search. Each iteration compares the right half - first. */ - if (CMP_FUNC (needle, needle + period, suffix) == 0) - { - /* Entire needle is periodic; a mismatch in the left half can - only advance by the period, so use memory to avoid rescanning - known occurrences of the period in the right half. */ - size_t memory = 0; - size_t shift; - j = 0; - while (AVAILABLE (haystack, haystack_len, j, needle_len)) - { - /* Check the last byte first; if it does not match, then - shift to the next possible match location. */ - shift = shift_table[CANON_ELEMENT (haystack[j + needle_len - 1])]; - if (0 < shift) - { - if (memory && shift < period) - { - /* Since needle is periodic, but the last period has - a byte out of place, there can be no match until - after the mismatch. */ - shift = needle_len - period; - } - memory = 0; - j += shift; - continue; - } - /* Scan for matches in right half. The last byte has - already been matched, by virtue of the shift table. */ - i = MAX (suffix, memory); - while (i < needle_len - 1 && (CANON_ELEMENT (needle[i]) - == CANON_ELEMENT (haystack[i + j]))) - ++i; - if (needle_len - 1 <= i) - { - /* Scan for matches in left half. */ - i = suffix - 1; - while (memory < i + 1 && (CANON_ELEMENT (needle[i]) - == CANON_ELEMENT (haystack[i + j]))) - --i; - if (i + 1 < memory + 1) - return (RETURN_TYPE) (haystack + j); - /* No match, so remember how many repetitions of period - on the right half were scanned. */ - j += period; - memory = needle_len - period; - } - else - { - j += i - suffix + 1; - memory = 0; - } - } - } - else - { - /* The two halves of needle are distinct; no extra memory is - required, and any mismatch results in a maximal shift. */ - size_t shift; - period = MAX (suffix, needle_len - suffix) + 1; - j = 0; - while (AVAILABLE (haystack, haystack_len, j, needle_len)) - { - /* Check the last byte first; if it does not match, then - shift to the next possible match location. */ - shift = shift_table[CANON_ELEMENT (haystack[j + needle_len - 1])]; - if (0 < shift) - { - j += shift; - continue; - } - /* Scan for matches in right half. The last byte has - already been matched, by virtue of the shift table. */ - i = suffix; - while (i < needle_len - 1 && (CANON_ELEMENT (needle[i]) - == CANON_ELEMENT (haystack[i + j]))) - ++i; - if (needle_len - 1 <= i) - { - /* Scan for matches in left half. */ - i = suffix - 1; - while (i != SIZE_MAX && (CANON_ELEMENT (needle[i]) - == CANON_ELEMENT (haystack[i + j]))) - --i; - if (i == SIZE_MAX) - return (RETURN_TYPE) (haystack + j); - j += period; - } - else - j += i - suffix + 1; - } - } - return NULL; -} - -#undef AVAILABLE -#undef CANON_ELEMENT -#undef CMP_FUNC -#undef MAX -#undef RETURN_TYPE |