diff options
| -rw-r--r-- | ChangeLog | 15 | ||||
| -rw-r--r-- | NEWS | 7 | ||||
| -rw-r--r-- | posix/regcomp.c | 48 | ||||
| -rw-r--r-- | posix/regex_internal.c | 6 | ||||
| -rw-r--r-- | string/Makefile | 3 | ||||
| -rw-r--r-- | string/memmem.c | 58 | ||||
| -rw-r--r-- | string/str-two-way.h | 430 | ||||
| -rw-r--r-- | string/strcasestr.c | 152 | ||||
| -rw-r--r-- | string/strstr.c | 142 |
9 files changed, 623 insertions, 238 deletions
@@ -1,3 +1,16 @@ +2008-05-14 Ulrich Drepper <drepper@redhat.com> + + * string/Makefile (distribute): Add str-two-way.h. + +2008-03-29 Eric Blake <ebb9@byu.net> + + Rewrite string searches to O(n) rather than O(n^2). + * string/str-two-way.h: New file. For linear fixed-allocation + string searching. + * string/memmem.c: New implementation. + * string/strstr.c: New implementation. + * string/strcasestr.c: New implementation. + 2008-04-11 Paolo Bonzini <bonzini@gnu.org> * posix/regcomp.c (optimize_utf8): Add a note on why we test @@ -47,7 +60,7 @@ (match_prefix): Don't treat IPv4 loopback address special when converting to v4 mapped addressed. - * sysdeps/posix/getaddrinfo.c (getaddrinfo): Add _res_hconf_init + * sysdeps/posix/getaddrinfo.c (getaddrinfo): Call _res_hconf_init if necessary. * posix/tst-rfc3484.c: Add dummy definition of _res_hconf_init. * posix/tst-rfc3484-2.c: Likewise. @@ -15,6 +15,13 @@ Version 2.9 * getaddrinfo now handles DCCP and UDPlite. Implemented by Ulrich Drepper. + +* New fixed-size conversion macros: htobe16, htole16, be16toh, le16toh, + htobe32, htole32, be32toh, le32toh, htobe64, htole64, be64toh, le64toh. + Implemented by Ulrich Drepper. + +* New implementation of memmem, strstr, and strcasestr which is O(n). + Implemented by Eric Blake. Version 2.8 diff --git a/posix/regcomp.c b/posix/regcomp.c index f4eab3a..8ba7668 100644 --- a/posix/regcomp.c +++ b/posix/regcomp.c @@ -1038,7 +1038,9 @@ optimize_utf8 (re_dfa_t *dfa) case BUF_LAST: break; default: - /* Word anchors etc. cannot be handled. */ + /* Word anchors etc. cannot be handled. It's okay to test + opr.ctx_type since constraints (for all DFA nodes) are + created by ORing one or more opr.ctx_type values. */ return; } break; @@ -1318,6 +1320,8 @@ calc_first (void *extra, bin_tree_t *node) node->node_idx = re_dfa_add_node (dfa, node->token); if (BE (node->node_idx == -1, 0)) return REG_ESPACE; + if (node->token.type == ANCHOR) + dfa->nodes[node->node_idx].constraint = node->token.opr.ctx_type; } return REG_NOERROR; } @@ -1446,22 +1450,17 @@ duplicate_node_closure (re_dfa_t *dfa, int top_org_node, int top_clone_node, destination. */ org_dest = dfa->edests[org_node].elems[0]; re_node_set_empty (dfa->edests + clone_node); - if (dfa->nodes[org_node].type == ANCHOR) + /* If the node is root_node itself, it means the epsilon clsoure + has a loop. Then tie it to the destination of the root_node. */ + if (org_node == root_node && clone_node != org_node) { - /* In case of the node has another constraint, append it. */ - if (org_node == root_node && clone_node != org_node) - { - /* ...but if the node is root_node itself, it means the - epsilon closure have a loop, then tie it to the - destination of the root_node. */ - ret = re_node_set_insert (dfa->edests + clone_node, - org_dest); - if (BE (ret < 0, 0)) - return REG_ESPACE; - break; - } - constraint |= dfa->nodes[org_node].opr.ctx_type; + ret = re_node_set_insert (dfa->edests + clone_node, org_dest); + if (BE (ret < 0, 0)) + return REG_ESPACE; + break; } + /* In case of the node has another constraint, add it. */ + constraint |= dfa->nodes[org_node].constraint; clone_dest = duplicate_node (dfa, org_dest, constraint); if (BE (clone_dest == -1, 0)) return REG_ESPACE; @@ -1479,7 +1478,7 @@ duplicate_node_closure (re_dfa_t *dfa, int top_org_node, int top_clone_node, clone_dest = search_duplicated_node (dfa, org_dest, constraint); if (clone_dest == -1) { - /* There are no such a duplicated node, create a new one. */ + /* There is no such duplicated node, create a new one. */ reg_errcode_t err; clone_dest = duplicate_node (dfa, org_dest, constraint); if (BE (clone_dest == -1, 0)) @@ -1494,7 +1493,7 @@ duplicate_node_closure (re_dfa_t *dfa, int top_org_node, int top_clone_node, } else { - /* There are a duplicated node which satisfy the constraint, + /* There is a duplicated node which satisfies the constraint, use it to avoid infinite loop. */ ret = re_node_set_insert (dfa->edests + clone_node, clone_dest); if (BE (ret < 0, 0)) @@ -1543,8 +1542,7 @@ duplicate_node (re_dfa_t *dfa, int org_idx, unsigned int constraint) if (BE (dup_idx != -1, 1)) { dfa->nodes[dup_idx].constraint = constraint; - if (dfa->nodes[org_idx].type == ANCHOR) - dfa->nodes[dup_idx].constraint |= dfa->nodes[org_idx].opr.ctx_type; + dfa->nodes[dup_idx].constraint |= dfa->nodes[org_idx].constraint; dfa->nodes[dup_idx].duplicated = 1; /* Store the index of the original node. */ @@ -1624,7 +1622,6 @@ static reg_errcode_t calc_eclosure_iter (re_node_set *new_set, re_dfa_t *dfa, int node, int root) { reg_errcode_t err; - unsigned int constraint; int i, incomplete; re_node_set eclosure; incomplete = 0; @@ -1636,15 +1633,14 @@ calc_eclosure_iter (re_node_set *new_set, re_dfa_t *dfa, int node, int root) We reference this value to avoid infinite loop. */ dfa->eclosures[node].nelem = -1; - constraint = ((dfa->nodes[node].type == ANCHOR) - ? dfa->nodes[node].opr.ctx_type : 0); - /* If the current node has constraints, duplicate all nodes. - Since they must inherit the constraints. */ - if (constraint + /* If the current node has constraints, duplicate all nodes + since they must inherit the constraints. */ + if (dfa->nodes[node].constraint && dfa->edests[node].nelem && !dfa->nodes[dfa->edests[node].elems[0]].duplicated) { - err = duplicate_node_closure (dfa, node, node, node, constraint); + err = duplicate_node_closure (dfa, node, node, node, + dfa->nodes[node].constraint); if (BE (err != REG_NOERROR, 0)) return err; } diff --git a/posix/regex_internal.c b/posix/regex_internal.c index 66154e0..01a432e 100644 --- a/posix/regex_internal.c +++ b/posix/regex_internal.c @@ -1665,11 +1665,9 @@ create_cd_newstate (const re_dfa_t *dfa, const re_node_set *nodes, for (i = 0 ; i < nodes->nelem ; i++) { - unsigned int constraint = 0; re_token_t *node = dfa->nodes + nodes->elems[i]; re_token_type_t type = node->type; - if (node->constraint) - constraint = node->constraint; + unsigned int constraint = node->constraint; if (type == CHARACTER && !constraint) continue; @@ -1682,8 +1680,6 @@ create_cd_newstate (const re_dfa_t *dfa, const re_node_set *nodes, newstate->halt = 1; else if (type == OP_BACK_REF) newstate->has_backref = 1; - else if (type == ANCHOR) - constraint = node->opr.ctx_type; if (constraint) { diff --git a/string/Makefile b/string/Makefile index ccdc497..a15ae14 100644 --- a/string/Makefile +++ b/string/Makefile @@ -55,7 +55,8 @@ tests := tester inl-tester noinl-tester testcopy test-ffs \ tst-strtok tst-strxfrm bug-strcoll1 tst-strfry \ bug-strtok1 $(addprefix test-,$(strop-tests)) \ bug-envz1 tst-strxfrm2 tst-endian -distribute := memcopy.h pagecopy.h tst-svc.expect test-string.h +distribute := memcopy.h pagecopy.h tst-svc.expect test-string.h \ + str-two-way.h include ../Rules diff --git a/string/memmem.c b/string/memmem.c index c404621..3176ab7 100644 --- a/string/memmem.c +++ b/string/memmem.c @@ -1,4 +1,4 @@ -/* Copyright (C) 1991,92,93,94,96,97,98,2000,2004 Free Software Foundation, Inc. +/* Copyright (C) 1991,92,93,94,96,97,98,2000,2004,2008 Free Software Foundation, Inc. This file is part of the GNU C Library. The GNU C Library is free software; you can redistribute it and/or @@ -16,26 +16,36 @@ Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA. */ -#include <stddef.h> +/* This particular implementation was written by Eric Blake, 2008. */ + +#ifndef _LIBC +# include <config.h> +#endif + +/* Specification of memmem. */ #include <string.h> #ifndef _LIBC # define __builtin_expect(expr, val) (expr) #endif +#define RETURN_TYPE void * +#define AVAILABLE(h, h_l, j, n_l) ((j) <= (h_l) - (n_l)) +#include "str-two-way.h" + #undef memmem -/* Return the first occurrence of NEEDLE in HAYSTACK. */ +/* Return the first occurrence of NEEDLE in HAYSTACK. Return HAYSTACK + if NEEDLE_LEN is 0, otherwise NULL if NEEDLE is not found in + HAYSTACK. */ void * -memmem (haystack, haystack_len, needle, needle_len) - const void *haystack; - size_t haystack_len; - const void *needle; - size_t needle_len; +memmem (const void *haystack_start, size_t haystack_len, + const void *needle_start, size_t needle_len) { - const char *begin; - const char *const last_possible - = (const char *) haystack + haystack_len - needle_len; + /* Abstract memory is considered to be an array of 'unsigned char' values, + not an array of 'char' values. See ISO C 99 section 6.2.6.1. */ + const unsigned char *haystack = (const unsigned char *) haystack_start; + const unsigned char *needle = (const unsigned char *) needle_start; if (needle_len == 0) /* The first occurrence of the empty string is deemed to occur at @@ -47,12 +57,22 @@ memmem (haystack, haystack_len, needle, needle_len) if (__builtin_expect (haystack_len < needle_len, 0)) return NULL; - for (begin = (const char *) haystack; begin <= last_possible; ++begin) - if (begin[0] == ((const char *) needle)[0] && - !memcmp ((const void *) &begin[1], - (const void *) ((const char *) needle + 1), - needle_len - 1)) - return (void *) begin; - - return NULL; + /* Use optimizations in memchr when possible, to reduce the search + size of haystack using a linear algorithm with a smaller + coefficient. However, avoid memchr for long needles, since we + can often achieve sublinear performance. */ + if (needle_len < LONG_NEEDLE_THRESHOLD) + { + haystack = memchr (haystack, *needle, haystack_len); + if (!haystack || __builtin_expect (needle_len == 1, 0)) + return (void *) haystack; + haystack_len -= haystack - (const unsigned char *) haystack_start; + if (haystack_len < needle_len) + return NULL; + return two_way_short_needle (haystack, haystack_len, needle, needle_len); + } + else + return two_way_long_needle (haystack, haystack_len, needle, needle_len); } + +#undef LONG_NEEDLE_THRESHOLD diff --git a/string/str-two-way.h b/string/str-two-way.h new file mode 100644 index 0000000..87ed8a0 --- /dev/null +++ b/string/str-two-way.h @@ -0,0 +1,430 @@ +/* Byte-wise substring search, using the Two-Way algorithm. + Copyright (C) 2008 Free Software Foundation, Inc. + This file is part of the GNU C Library. + Written by Eric Blake <ebb9@byu.net>, 2008. + + The GNU C Library 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.1 of the License, or (at your option) any later version. + + The GNU C Library 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 the GNU C Library; if not, write to the Free + Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA + 02111-1307 USA. */ + +/* Before including this file, you need to include <string.h> (and + <config.h> before that, if not part of libc), 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, 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 + and http://en.wikipedia.org/wiki/Boyer-Moore_string_search_algorithm +*/ + +/* 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. + + Given an ordered alphabet, a critical factorization can be computed + in linear time, with 2 * NEEDLE_LEN comparisons, by computing the + larger of two ordered maximal suffixes. The ordered maximal + suffixes are determined by lexicographic comparison of + 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. */ + + /* 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 longer suffix. Return the first byte of the right + half, rather than the last byte of the left half. */ + 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 can only advance by the + period, so use memory to avoid rescanning known occurrences + of the period. */ + 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 can only advance by the + period, so use memory to avoid rescanning known occurrences + of the period. */ + 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 diff --git a/string/strcasestr.c b/string/strcasestr.c index 1dde43c..9de19aa 100644 --- a/string/strcasestr.c +++ b/string/strcasestr.c @@ -1,5 +1,5 @@ /* Return the offset of one string within another. - Copyright (C) 1994, 1996-2000, 2004 Free Software Foundation, Inc. + Copyright (C) 1994, 1996-2000, 2004, 2008 Free Software Foundation, Inc. This file is part of the GNU C Library. The GNU C Library is free software; you can redistribute it and/or @@ -30,113 +30,71 @@ # include <config.h> #endif +/* Specification. */ +#include <string.h> + #include <ctype.h> +#include <stdbool.h> +#include <strings.h> -#if defined _LIBC || defined HAVE_STRING_H -# include <string.h> -#endif +#define TOLOWER(Ch) (isupper (Ch) ? tolower (Ch) : (Ch)) -#ifdef _LIBC -# include <locale/localeinfo.h> -# define TOLOWER(c) __tolower_l ((unsigned char) c, loc) -#else -# define TOLOWER(c) _tolower (c) -#endif - -typedef unsigned chartype; +/* Two-Way algorithm. */ +#define RETURN_TYPE char * +#define AVAILABLE(h, h_l, j, n_l) \ + (!memchr ((h) + (h_l), '\0', (j) + (n_l) - (h_l)) \ + && ((h_l) = (j) + (n_l))) +#define CANON_ELEMENT(c) TOLOWER (c) +#define CMP_FUNC(p1, p2, l) \ + strncasecmp ((const char *) (p1), (const char *) (p2), l) +#include "str-two-way.h" #undef strcasestr #undef __strcasestr +/* Find the first occurrence of NEEDLE in HAYSTACK, using + case-insensitive comparison. This function gives unspecified + results in multibyte locales. */ char * -__strcasestr (phaystack, pneedle) - const char *phaystack; - const char *pneedle; +__strcasestr (const char *haystack_start, const char *needle_start) { - register const unsigned char *haystack, *needle; - register chartype b, c; -#ifdef _LIBC - __locale_t loc = _NL_CURRENT_LOCALE; -#endif - - haystack = (const unsigned char *) phaystack; - needle = (const unsigned char *) pneedle; - - b = TOLOWER (*needle); - if (b != '\0') + const char *haystack = haystack_start; + const char *needle = needle_start; + size_t needle_len; /* Length of NEEDLE. */ + size_t haystack_len; /* Known minimum length of HAYSTACK. */ + bool ok = true; /* True if NEEDLE is prefix of HAYSTACK. */ + + /* Determine length of NEEDLE, and in the process, make sure + HAYSTACK is at least as long (no point processing all of a long + NEEDLE if HAYSTACK is too short). */ + while (*haystack && *needle) { - haystack--; /* possible ANSI violation */ - do - { - c = *++haystack; - if (c == '\0') - goto ret0; - } - while (TOLOWER (c) != (int) b); - - c = TOLOWER (*++needle); - if (c == '\0') - goto foundneedle; - ++needle; - goto jin; - - for (;;) - { - register chartype a; - register const unsigned char *rhaystack, *rneedle; - - do - { - a = *++haystack; - if (a == '\0') - goto ret0; - if (TOLOWER (a) == (int) b) - break; - a = *++haystack; - if (a == '\0') - goto ret0; -shloop: - ; - } - while (TOLOWER (a) != (int) b); - -jin: a = *++haystack; - if (a == '\0') - goto ret0; - - if (TOLOWER (a) != (int) c) - goto shloop; - - rhaystack = haystack-- + 1; - rneedle = needle; - a = TOLOWER (*rneedle); - - if (TOLOWER (*rhaystack) == (int) a) - do - { - if (a == '\0') - goto foundneedle; - ++rhaystack; - a = TOLOWER (*++needle); - if (TOLOWER (*rhaystack) != (int) a) - break; - if (a == '\0') - goto foundneedle; - ++rhaystack; - a = TOLOWER (*++needle); - } - while (TOLOWER (*rhaystack) == (int) a); - - needle = rneedle; /* took the register-poor approach */ - - if (a == '\0') - break; - } + ok &= (TOLOWER ((unsigned char) *haystack) + == TOLOWER ((unsigned char) *needle)); + haystack++; + needle++; } -foundneedle: - return (char*) haystack; -ret0: - return 0; + if (*needle) + return NULL; + if (ok) + return (char *) haystack_start; + needle_len = needle - needle_start; + haystack = haystack_start + 1; + haystack_len = needle_len - 1; + + /* Perform the search. Abstract memory is considered to be an array + of 'unsigned char' values, not an array of 'char' values. See + ISO C 99 section 6.2.6.1. */ + if (needle_len < LONG_NEEDLE_THRESHOLD) + return two_way_short_needle ((const unsigned char *) haystack, + haystack_len, + (const unsigned char *) needle_start, + needle_len); + return two_way_long_needle ((const unsigned char *) haystack, haystack_len, + (const unsigned char *) needle_start, + needle_len); } +#undef LONG_NEEDLE_THRESHOLD + weak_alias (__strcasestr, strcasestr) diff --git a/string/strstr.c b/string/strstr.c index fce1f2a..a9dc312 100644 --- a/string/strstr.c +++ b/string/strstr.c @@ -1,5 +1,5 @@ /* Return the offset of one string within another. - Copyright (C) 1994,1996,1997,2000,2001,2003 Free Software Foundation, Inc. + Copyright (C) 1994,1996,1997,2000,2001,2003,2008 Free Software Foundation, Inc. This file is part of the GNU C Library. The GNU C Library is free software; you can redistribute it and/or @@ -17,107 +17,71 @@ Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA. */ -/* - * My personal strstr() implementation that beats most other algorithms. - * Until someone tells me otherwise, I assume that this is the - * fastest implementation of strstr() in C. - * I deliberately chose not to comment it. You should have at least - * as much fun trying to understand it, as I had to write it :-). - * - * Stephen R. van den Berg, berg@pool.informatik.rwth-aachen.de */ +/* This particular implementation was written by Eric Blake, 2008. */ -#if HAVE_CONFIG_H +#ifndef _LIBC # include <config.h> #endif -#if defined _LIBC || defined HAVE_STRING_H -# include <string.h> +/* Specification of strstr. */ +#include <string.h> + +#include <stdbool.h> + +#ifndef _LIBC +# define __builtin_expect(expr, val) (expr) #endif -typedef unsigned chartype; +#define RETURN_TYPE char * +#define AVAILABLE(h, h_l, j, n_l) \ + (!memchr ((h) + (h_l), '\0', (j) + (n_l) - (h_l)) \ + && ((h_l) = (j) + (n_l))) +#include "str-two-way.h" #undef strstr +/* Return the first occurrence of NEEDLE in HAYSTACK. Return HAYSTACK + if NEEDLE is empty, otherwise NULL if NEEDLE is not found in + HAYSTACK. */ char * -strstr (phaystack, pneedle) - const char *phaystack; - const char *pneedle; +strstr (const char *haystack_start, const char *needle_start) { - const unsigned char *haystack, *needle; - chartype b; - const unsigned char *rneedle; - - haystack = (const unsigned char *) phaystack; + const char *haystack = haystack_start; + const char *needle = needle_start; + size_t needle_len; /* Length of NEEDLE. */ + size_t haystack_len; /* Known minimum length of HAYSTACK. */ + bool ok = true; /* True if NEEDLE is prefix of HAYSTACK. */ - if ((b = *(needle = (const unsigned char *) pneedle))) - { - chartype c; - haystack--; /* possible ANSI violation */ + /* Determine length of NEEDLE, and in the process, make sure + HAYSTACK is at least as long (no point processing all of a long + NEEDLE if HAYSTACK is too short). */ + while (*haystack && *needle) + ok &= *haystack++ == *needle++; + if (*needle) + return NULL; + if (ok) + return (char *) haystack_start; - { - chartype a; - do - if (!(a = *++haystack)) - goto ret0; - while (a != b); - } + /* Reduce the size of haystack using strchr, since it has a smaller + linear coefficient than the Two-Way algorithm. */ + needle_len = needle - needle_start; + haystack = strchr (haystack_start + 1, *needle_start); + if (!haystack || __builtin_expect (needle_len == 1, 0)) + return (char *) haystack; + needle -= needle_len; + haystack_len = (haystack > haystack_start + needle_len ? 1 + : needle_len + haystack_start - haystack); - if (!(c = *++needle)) - goto foundneedle; - ++needle; - goto jin; - - for (;;) - { - { - chartype a; - if (0) - jin:{ - if ((a = *++haystack) == c) - goto crest; - } - else - a = *++haystack; - do - { - for (; a != b; a = *++haystack) - { - if (!a) - goto ret0; - if ((a = *++haystack) == b) - break; - if (!a) - goto ret0; - } - } - while ((a = *++haystack) != c); - } - crest: - { - chartype a; - { - const unsigned char *rhaystack; - if (*(rhaystack = haystack-- + 1) == (a = *(rneedle = needle))) - do - { - if (!a) - goto foundneedle; - if (*++rhaystack != (a = *++needle)) - break; - if (!a) - goto foundneedle; - } - while (*++rhaystack == (a = *++needle)); - needle = rneedle; /* took the register-poor aproach */ - } - if (!a) - break; - } - } - } -foundneedle: - return (char *) haystack; -ret0: - return 0; + /* Perform the search. Abstract memory is considered to be an array + of 'unsigned char' values, not an array of 'char' values. See + ISO C 99 section 6.2.6.1. */ + if (needle_len < LONG_NEEDLE_THRESHOLD) + return two_way_short_needle ((const unsigned char *) haystack, + haystack_len, + (const unsigned char *) needle, needle_len); + return two_way_long_needle ((const unsigned char *) haystack, haystack_len, + (const unsigned char *) needle, needle_len); } libc_hidden_builtin_def (strstr) + +#undef LONG_NEEDLE_THRESHOLD |