aboutsummaryrefslogtreecommitdiff
path: root/gdb/gnulib/str-two-way.h
diff options
context:
space:
mode:
authorPedro Alves <palves@redhat.com>2010-05-23 00:57:01 +0000
committerPedro Alves <palves@redhat.com>2010-05-23 00:57:01 +0000
commitf434ba0309555deb86dc8b6da65ea67d588bda30 (patch)
treee6037837cb9d1eb5424a46c4ce6f9d1d91525eb1 /gdb/gnulib/str-two-way.h
parent528b55c0a00cc561956d2dbf2b035bb751331cc1 (diff)
downloadgdb-f434ba0309555deb86dc8b6da65ea67d588bda30.zip
gdb-f434ba0309555deb86dc8b6da65ea67d588bda30.tar.gz
gdb-f434ba0309555deb86dc8b6da65ea67d588bda30.tar.bz2
gdb/
2010-05-23 Pedro Alves <pedro@codesourcery.com> Update gnulib from latest git. (250b80067c1e1d8faa0c42fb572f721975b929c5) * gnulib/memcmp.c: Removed. * gnulib/memchr.valgrind: New. * gnulib/stddef.in.h: New. * gnulib/Makefile.am: Updated. * gnulib/memchr.c: Updated. * gnulib/memmem.c: Updated. * gnulib/stdint.in.h: Updated. * gnulib/str-two-way.h: Updated. * gnulib/string.in.h: Updated. * gnulib/wchar.in.h: Updated. * gnulib/extra/link-warning.h: Removed. * gnulib/extra/c++defs.h: New. * gnulib/extra/warn-on-use.h: New. * gnulib/extra/arg-nonnull.h: Updated. * gnulib/m4/extensions.m4: Updated. * gnulib/m4/gnulib-cache.m4: Updated. * gnulib/m4/gnulib-common.m4: Updated. * gnulib/m4/gnulib-comp.m4: Updated. * gnulib/m4/gnulib-tool.m4: Updated. * gnulib/m4/include_next.m4: Updated. * gnulib/m4/longlong.m4: Updated. * gnulib/m4/memchr.m4: Updated. * gnulib/m4/memmem.m4: Updated. * gnulib/m4/stdint.m4: Updated. * gnulib/m4/string_h.m4: Updated. * gnulib/m4/memcmp.m4: Removed. * gnulib/m4/onceonly_2_57.m4: Removed. * gnulib/m4/00gnulib.m4: New. * gnulib/m4/mmap-anon.m4: New. * gnulib/m4/multiarch.m4: New. * gnulib/m4/onceonly.m4: New. * gnulib/m4/stddef_h.m4: New. * gnulib/m4/warn-on-use.m4: New. * gnulib/m4/wchar.m4: Removed. * gnulib/m4/wchar_h.m4: New. * gnulib/m4/wchar_t.m4: New. * gnulib/m4/wint_t.m4: New. * aclocal.m4: Regenerate. * config.in: Likewise. * configure: Likewise. * gnulib/Makefile.in: Likewise. gdb/gdbserver/ 2010-05-23 Pedro Alves <pedro@codesourcery.com> * config.h, configure: Regenerate.
Diffstat (limited to 'gdb/gnulib/str-two-way.h')
-rw-r--r--gdb/gnulib/str-two-way.h364
1 files changed, 183 insertions, 181 deletions
diff --git a/gdb/gnulib/str-two-way.h b/gdb/gnulib/str-two-way.h
index d528528..c08f60e 100644
--- a/gdb/gnulib/str-two-way.h
+++ b/gdb/gnulib/str-two-way.h
@@ -21,21 +21,21 @@
<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.
+ 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.
+ 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.
+ 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.
@@ -67,7 +67,9 @@
# define LONG_NEEDLE_THRESHOLD SIZE_MAX
#endif
-#define MAX(a, b) ((a < b) ? (b) : (a))
+#ifndef MAX
+# define MAX(a, b) ((a < b) ? (b) : (a))
+#endif
#ifndef CANON_ELEMENT
# define CANON_ELEMENT(c) c
@@ -101,7 +103,7 @@
periodicity. */
static size_t
critical_factorization (const unsigned char *needle, size_t needle_len,
- size_t *period)
+ size_t *period)
{
/* Index of last byte of left half, or SIZE_MAX. */
size_t max_suffix, max_suffix_rev;
@@ -128,29 +130,29 @@ critical_factorization (const unsigned char *needle, size_t 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;
- }
+ {
+ /* 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;
- }
- }
+ {
+ /* 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;
- }
+ {
+ /* Suffix is larger, start over from current location. */
+ max_suffix = j++;
+ k = p = 1;
+ }
}
*period = p;
@@ -163,29 +165,29 @@ critical_factorization (const unsigned char *needle, size_t 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;
- }
+ {
+ /* 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;
- }
- }
+ {
+ /* 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;
- }
+ {
+ /* 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
@@ -208,7 +210,7 @@ critical_factorization (const unsigned char *needle, size_t needle_len,
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)
+ 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. */
@@ -225,65 +227,65 @@ two_way_short_needle (const unsigned char *haystack, size_t haystack_len,
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. */
+ 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;
- }
- }
+ {
+ /* 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. */
+ 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;
- }
+ {
+ /* 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;
}
@@ -302,7 +304,7 @@ two_way_short_needle (const unsigned char *haystack, size_t haystack_len,
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)
+ 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. */
@@ -329,93 +331,93 @@ two_way_long_needle (const unsigned char *haystack, size_t haystack_len,
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. */
+ 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;
- }
- }
+ {
+ /* 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. */
+ 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;
- }
+ {
+ /* 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;
}