[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
grep branch, master, updated. v2.18-115-g10ce910
|
From: |
Paul Eggert |
|
Subject: |
grep branch, master, updated. v2.18-115-g10ce910 |
|
Date: |
Thu, 01 May 2014 01:32:36 +0000 |
This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "grep".
The branch, master has been updated
via 10ce910928c757d1adb790a9c9e5bad7de289bd4 (commit)
via cbc97d923cdf98a3fc3744438097f5fe023cbb44 (commit)
via 74e77131657a127f00e6ddc860968ccb3d2f6e03 (commit)
from d4c8de2f3e4f6dfaf964f04600d4bb37285d5623 (commit)
Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.
- Log -----------------------------------------------------------------
http://git.savannah.gnu.org/cgit/grep.git/commit/?id=10ce910928c757d1adb790a9c9e5bad7de289bd4
commit 10ce910928c757d1adb790a9c9e5bad7de289bd4
Author: Paul Eggert <address@hidden>
Date: Wed Apr 30 00:03:18 2014 -0700
grep: simplify EGexecute further
* src/dfa.c, src/dfa.h (dfasuperset): Arg is now const pointer.
Now pure.
* src/dfasearch.c (EGexecute): Coalesce some duplicate code.
Don't worry about memrchr returning NULL when that's impossible.
diff --git a/src/dfa.c b/src/dfa.c
index 1bc6925..45dcc52 100644
--- a/src/dfa.c
+++ b/src/dfa.c
@@ -3395,10 +3395,8 @@ dfaexec (struct dfa *d, char const *begin, char *end,
return (char *) p;
}
-/* Return superset for D, which searchs through a buffer looking for a
- potential match. */
struct dfa *
-dfasuperset (struct dfa *d)
+dfasuperset (struct dfa const *d)
{
return d->superset;
}
diff --git a/src/dfa.h b/src/dfa.h
index 2de7ba8..e3ab700 100644
--- a/src/dfa.h
+++ b/src/dfa.h
@@ -71,9 +71,11 @@ extern void dfacomp (char const *, size_t, struct dfa *,
int);
extern char *dfaexec (struct dfa *d, char const *begin, char *end,
int newline, size_t *count, int *backref);
-/* Return superset for D, which searchs through a buffer looking for a
- potential match. */
-extern struct dfa *dfasuperset (struct dfa *d);
+/* Return a superset for D. The superset matches everything that D
+ matches, along with some other strings (though the latter should be
+ rare, for efficiency reasons). Return a null pointer if no useful
+ superset is available. */
+extern struct dfa *dfasuperset (struct dfa const *d) _GL_ATTRIBUTE_PURE;
/* Return true if the DFA is likely to be fast. */
extern bool dfaisfast (struct dfa const *) _GL_ATTRIBUTE_PURE;
diff --git a/src/dfasearch.c b/src/dfasearch.c
index 6d3765b..5ad6c9d 100644
--- a/src/dfasearch.c
+++ b/src/dfasearch.c
@@ -227,7 +227,7 @@ EGexecute (char const *buf, size_t size, size_t *match_size,
{
char const *next_beg, *dfa_beg = beg;
size_t count = 0;
- bool narrowed = false;
+ bool exact_kwset_match = false;
/* Try matching with KWset, if it's defined. */
if (kwset)
@@ -241,17 +241,30 @@ EGexecute (char const *buf, size_t size, size_t
*match_size,
goto failure;
match = beg + offset;
prev_beg = beg;
-
- /* Narrow down to the line we've found. */
+
+ /* Narrow down to the line containing the possible match. */
beg = memrchr (buf, eol, match - buf);
beg = beg ? beg + 1 : buf;
dfa_beg = beg;
- if (kwsm.index < kwset_exact_matches)
- {
- end = memchr (match, eol, buflim - match);
- end = end ? end + 1 : buflim;
+ /* Determine the end pointer to give the DFA next. Typically
+ this is after the first newline after MATCH; but if the KWset
+ match is not exact, the DFA is fast, and the offset from
+ PREV_BEG is less than 64 or (MATCH - PREV_BEG), this is the
+ greater of the latter two values; this temporarily prefers
+ the DFA to KWset. */
+ exact_kwset_match = kwsm.index < kwset_exact_matches;
+ end = ((exact_kwset_match || !dfafast
+ || MAX (16, match - beg) < (match - prev_beg) >> 2)
+ ? match
+ : (buflim - prev_beg) >> 2 <= match - beg
+ ? buflim
+ : prev_beg + 4 * (match - beg));
+ end = memchr (end, eol, buflim - end);
+ end = end ? end + 1 : buflim;
+ if (exact_kwset_match)
+ {
if (MB_CUR_MAX == 1)
goto success;
if (mb_start < beg)
@@ -263,69 +276,30 @@ EGexecute (char const *buf, size_t size, size_t
*match_size,
character. Perform the DFA search starting from the
beginning of the next character. */
dfa_beg = mb_start;
- narrowed = true;
- }
- else if (dfafast)
- {
- /* Determine the end pointer to start with DFA. It's
- `match' by default. If the offset from prev_beg is
- lesser than (match - beg) * 4 and/or 64, set it to
- greatest value in them. A larger offset than the
- default means that DFA is preferred to KWset. */
- offset = (match - beg) * 4;
- if (offset < 64)
- offset = 64;
- if (prev_beg + offset > match)
- {
- end = prev_beg + offset;
- if (end < buflim)
- {
- end = memchr (end, eol, buflim - end);
- end = end ? end + 1 : buflim;
- }
- else
- end = buflim;
- }
- else
- {
- end = memchr (match, eol, buflim - match);
- end = end ? end + 1 : buflim;
- narrowed = true;
- }
- }
- else
- {
- end = memchr (match, eol, buflim - match);
- end = end ? end + 1 : buflim;
- narrowed = true;
}
}
/* Try matching with the superset of DFA, if it's defined. */
- if (superset && !(kwset && kwsm.index < kwset_exact_matches))
+ if (superset && !exact_kwset_match)
{
- next_beg = dfaexec (superset, dfa_beg, (char *) end, 1, &count,
NULL);
+ next_beg = dfaexec (superset, dfa_beg, (char *) end, 1,
+ &count, NULL);
/* If there's no match, or if we've matched the sentinel,
we're done. */
if (next_beg == NULL || next_beg == end)
continue;
- if (!narrowed)
+
+ /* Narrow down to the line we've found. */
+ if (count != 0)
{
- /* Narrow down to the line we've found. */
- if (count != 0)
- {
- beg = memrchr (buf, eol, next_beg - buf);
- beg = beg ? beg + 1 : buf;
-
- /* If dfaexec may match in multiple lines, try to
- match in one line. */
- end = beg;
- continue;
- }
- end = memchr (next_beg, eol, buflim - next_beg);
- end = end ? end + 1 : buflim;
- narrowed = true;
+ /* If dfaexec may match in multiple lines, try to
+ match in one line. */
+ end = memrchr (buf, eol, next_beg - buf);
+ end++;
+ continue;
}
+ end = memchr (next_beg, eol, buflim - next_beg);
+ end = end ? end + 1 : buflim;
}
/* Try matching with DFA. */
@@ -335,17 +309,15 @@ EGexecute (char const *buf, size_t size, size_t
*match_size,
we're done. */
if (next_beg == NULL || next_beg == end)
continue;
- if (!narrowed)
+
+ /* Narrow down to the line we've found. */
+ if (count != 0)
{
- /* Narrow down to the line we've found. */
- if (count != 0)
- {
- beg = memrchr (buf, eol, next_beg - buf);
- beg = beg ? beg + 1 : buf;
- }
- end = memchr (next_beg, eol, buflim - next_beg);
- end = end ? end + 1 : buflim;
+ beg = memrchr (buf, eol, next_beg - buf);
+ beg++;
}
+ end = memchr (next_beg, eol, buflim - next_beg);
+ end = end ? end + 1 : buflim;
/* Successful, no backreferences encountered! */
if (!backref)
@@ -364,8 +336,7 @@ EGexecute (char const *buf, size_t size, size_t *match_size,
if (TYPE_MAXIMUM (regoff_t) < end - beg - 1)
xalloc_die ();
- /* If we've made it to this point, this means DFA has seen
- a probable match, and we need to run it through Regex. */
+ /* Run the possible match through Regex. */
best_match = end;
best_len = 0;
for (i = 0; i < pcount; i++)
http://git.savannah.gnu.org/cgit/grep.git/commit/?id=cbc97d923cdf98a3fc3744438097f5fe023cbb44
commit 10ce910928c757d1adb790a9c9e5bad7de289bd4
Author: Paul Eggert <address@hidden>
Date: Wed Apr 30 00:03:18 2014 -0700
grep: simplify EGexecute further
* src/dfa.c, src/dfa.h (dfasuperset): Arg is now const pointer.
Now pure.
* src/dfasearch.c (EGexecute): Coalesce some duplicate code.
Don't worry about memrchr returning NULL when that's impossible.
diff --git a/src/dfa.c b/src/dfa.c
index 1bc6925..45dcc52 100644
--- a/src/dfa.c
+++ b/src/dfa.c
@@ -3395,10 +3395,8 @@ dfaexec (struct dfa *d, char const *begin, char *end,
return (char *) p;
}
-/* Return superset for D, which searchs through a buffer looking for a
- potential match. */
struct dfa *
-dfasuperset (struct dfa *d)
+dfasuperset (struct dfa const *d)
{
return d->superset;
}
diff --git a/src/dfa.h b/src/dfa.h
index 2de7ba8..e3ab700 100644
--- a/src/dfa.h
+++ b/src/dfa.h
@@ -71,9 +71,11 @@ extern void dfacomp (char const *, size_t, struct dfa *,
int);
extern char *dfaexec (struct dfa *d, char const *begin, char *end,
int newline, size_t *count, int *backref);
-/* Return superset for D, which searchs through a buffer looking for a
- potential match. */
-extern struct dfa *dfasuperset (struct dfa *d);
+/* Return a superset for D. The superset matches everything that D
+ matches, along with some other strings (though the latter should be
+ rare, for efficiency reasons). Return a null pointer if no useful
+ superset is available. */
+extern struct dfa *dfasuperset (struct dfa const *d) _GL_ATTRIBUTE_PURE;
/* Return true if the DFA is likely to be fast. */
extern bool dfaisfast (struct dfa const *) _GL_ATTRIBUTE_PURE;
diff --git a/src/dfasearch.c b/src/dfasearch.c
index 6d3765b..5ad6c9d 100644
--- a/src/dfasearch.c
+++ b/src/dfasearch.c
@@ -227,7 +227,7 @@ EGexecute (char const *buf, size_t size, size_t *match_size,
{
char const *next_beg, *dfa_beg = beg;
size_t count = 0;
- bool narrowed = false;
+ bool exact_kwset_match = false;
/* Try matching with KWset, if it's defined. */
if (kwset)
@@ -241,17 +241,30 @@ EGexecute (char const *buf, size_t size, size_t
*match_size,
goto failure;
match = beg + offset;
prev_beg = beg;
-
- /* Narrow down to the line we've found. */
+
+ /* Narrow down to the line containing the possible match. */
beg = memrchr (buf, eol, match - buf);
beg = beg ? beg + 1 : buf;
dfa_beg = beg;
- if (kwsm.index < kwset_exact_matches)
- {
- end = memchr (match, eol, buflim - match);
- end = end ? end + 1 : buflim;
+ /* Determine the end pointer to give the DFA next. Typically
+ this is after the first newline after MATCH; but if the KWset
+ match is not exact, the DFA is fast, and the offset from
+ PREV_BEG is less than 64 or (MATCH - PREV_BEG), this is the
+ greater of the latter two values; this temporarily prefers
+ the DFA to KWset. */
+ exact_kwset_match = kwsm.index < kwset_exact_matches;
+ end = ((exact_kwset_match || !dfafast
+ || MAX (16, match - beg) < (match - prev_beg) >> 2)
+ ? match
+ : (buflim - prev_beg) >> 2 <= match - beg
+ ? buflim
+ : prev_beg + 4 * (match - beg));
+ end = memchr (end, eol, buflim - end);
+ end = end ? end + 1 : buflim;
+ if (exact_kwset_match)
+ {
if (MB_CUR_MAX == 1)
goto success;
if (mb_start < beg)
@@ -263,69 +276,30 @@ EGexecute (char const *buf, size_t size, size_t
*match_size,
character. Perform the DFA search starting from the
beginning of the next character. */
dfa_beg = mb_start;
- narrowed = true;
- }
- else if (dfafast)
- {
- /* Determine the end pointer to start with DFA. It's
- `match' by default. If the offset from prev_beg is
- lesser than (match - beg) * 4 and/or 64, set it to
- greatest value in them. A larger offset than the
- default means that DFA is preferred to KWset. */
- offset = (match - beg) * 4;
- if (offset < 64)
- offset = 64;
- if (prev_beg + offset > match)
- {
- end = prev_beg + offset;
- if (end < buflim)
- {
- end = memchr (end, eol, buflim - end);
- end = end ? end + 1 : buflim;
- }
- else
- end = buflim;
- }
- else
- {
- end = memchr (match, eol, buflim - match);
- end = end ? end + 1 : buflim;
- narrowed = true;
- }
- }
- else
- {
- end = memchr (match, eol, buflim - match);
- end = end ? end + 1 : buflim;
- narrowed = true;
}
}
/* Try matching with the superset of DFA, if it's defined. */
- if (superset && !(kwset && kwsm.index < kwset_exact_matches))
+ if (superset && !exact_kwset_match)
{
- next_beg = dfaexec (superset, dfa_beg, (char *) end, 1, &count,
NULL);
+ next_beg = dfaexec (superset, dfa_beg, (char *) end, 1,
+ &count, NULL);
/* If there's no match, or if we've matched the sentinel,
we're done. */
if (next_beg == NULL || next_beg == end)
continue;
- if (!narrowed)
+
+ /* Narrow down to the line we've found. */
+ if (count != 0)
{
- /* Narrow down to the line we've found. */
- if (count != 0)
- {
- beg = memrchr (buf, eol, next_beg - buf);
- beg = beg ? beg + 1 : buf;
-
- /* If dfaexec may match in multiple lines, try to
- match in one line. */
- end = beg;
- continue;
- }
- end = memchr (next_beg, eol, buflim - next_beg);
- end = end ? end + 1 : buflim;
- narrowed = true;
+ /* If dfaexec may match in multiple lines, try to
+ match in one line. */
+ end = memrchr (buf, eol, next_beg - buf);
+ end++;
+ continue;
}
+ end = memchr (next_beg, eol, buflim - next_beg);
+ end = end ? end + 1 : buflim;
}
/* Try matching with DFA. */
@@ -335,17 +309,15 @@ EGexecute (char const *buf, size_t size, size_t
*match_size,
we're done. */
if (next_beg == NULL || next_beg == end)
continue;
- if (!narrowed)
+
+ /* Narrow down to the line we've found. */
+ if (count != 0)
{
- /* Narrow down to the line we've found. */
- if (count != 0)
- {
- beg = memrchr (buf, eol, next_beg - buf);
- beg = beg ? beg + 1 : buf;
- }
- end = memchr (next_beg, eol, buflim - next_beg);
- end = end ? end + 1 : buflim;
+ beg = memrchr (buf, eol, next_beg - buf);
+ beg++;
}
+ end = memchr (next_beg, eol, buflim - next_beg);
+ end = end ? end + 1 : buflim;
/* Successful, no backreferences encountered! */
if (!backref)
@@ -364,8 +336,7 @@ EGexecute (char const *buf, size_t size, size_t *match_size,
if (TYPE_MAXIMUM (regoff_t) < end - beg - 1)
xalloc_die ();
- /* If we've made it to this point, this means DFA has seen
- a probable match, and we need to run it through Regex. */
+ /* Run the possible match through Regex. */
best_match = end;
best_len = 0;
for (i = 0; i < pcount; i++)
http://git.savannah.gnu.org/cgit/grep.git/commit/?id=74e77131657a127f00e6ddc860968ccb3d2f6e03
commit 10ce910928c757d1adb790a9c9e5bad7de289bd4
Author: Paul Eggert <address@hidden>
Date: Wed Apr 30 00:03:18 2014 -0700
grep: simplify EGexecute further
* src/dfa.c, src/dfa.h (dfasuperset): Arg is now const pointer.
Now pure.
* src/dfasearch.c (EGexecute): Coalesce some duplicate code.
Don't worry about memrchr returning NULL when that's impossible.
diff --git a/src/dfa.c b/src/dfa.c
index 1bc6925..45dcc52 100644
--- a/src/dfa.c
+++ b/src/dfa.c
@@ -3395,10 +3395,8 @@ dfaexec (struct dfa *d, char const *begin, char *end,
return (char *) p;
}
-/* Return superset for D, which searchs through a buffer looking for a
- potential match. */
struct dfa *
-dfasuperset (struct dfa *d)
+dfasuperset (struct dfa const *d)
{
return d->superset;
}
diff --git a/src/dfa.h b/src/dfa.h
index 2de7ba8..e3ab700 100644
--- a/src/dfa.h
+++ b/src/dfa.h
@@ -71,9 +71,11 @@ extern void dfacomp (char const *, size_t, struct dfa *,
int);
extern char *dfaexec (struct dfa *d, char const *begin, char *end,
int newline, size_t *count, int *backref);
-/* Return superset for D, which searchs through a buffer looking for a
- potential match. */
-extern struct dfa *dfasuperset (struct dfa *d);
+/* Return a superset for D. The superset matches everything that D
+ matches, along with some other strings (though the latter should be
+ rare, for efficiency reasons). Return a null pointer if no useful
+ superset is available. */
+extern struct dfa *dfasuperset (struct dfa const *d) _GL_ATTRIBUTE_PURE;
/* Return true if the DFA is likely to be fast. */
extern bool dfaisfast (struct dfa const *) _GL_ATTRIBUTE_PURE;
diff --git a/src/dfasearch.c b/src/dfasearch.c
index 6d3765b..5ad6c9d 100644
--- a/src/dfasearch.c
+++ b/src/dfasearch.c
@@ -227,7 +227,7 @@ EGexecute (char const *buf, size_t size, size_t *match_size,
{
char const *next_beg, *dfa_beg = beg;
size_t count = 0;
- bool narrowed = false;
+ bool exact_kwset_match = false;
/* Try matching with KWset, if it's defined. */
if (kwset)
@@ -241,17 +241,30 @@ EGexecute (char const *buf, size_t size, size_t
*match_size,
goto failure;
match = beg + offset;
prev_beg = beg;
-
- /* Narrow down to the line we've found. */
+
+ /* Narrow down to the line containing the possible match. */
beg = memrchr (buf, eol, match - buf);
beg = beg ? beg + 1 : buf;
dfa_beg = beg;
- if (kwsm.index < kwset_exact_matches)
- {
- end = memchr (match, eol, buflim - match);
- end = end ? end + 1 : buflim;
+ /* Determine the end pointer to give the DFA next. Typically
+ this is after the first newline after MATCH; but if the KWset
+ match is not exact, the DFA is fast, and the offset from
+ PREV_BEG is less than 64 or (MATCH - PREV_BEG), this is the
+ greater of the latter two values; this temporarily prefers
+ the DFA to KWset. */
+ exact_kwset_match = kwsm.index < kwset_exact_matches;
+ end = ((exact_kwset_match || !dfafast
+ || MAX (16, match - beg) < (match - prev_beg) >> 2)
+ ? match
+ : (buflim - prev_beg) >> 2 <= match - beg
+ ? buflim
+ : prev_beg + 4 * (match - beg));
+ end = memchr (end, eol, buflim - end);
+ end = end ? end + 1 : buflim;
+ if (exact_kwset_match)
+ {
if (MB_CUR_MAX == 1)
goto success;
if (mb_start < beg)
@@ -263,69 +276,30 @@ EGexecute (char const *buf, size_t size, size_t
*match_size,
character. Perform the DFA search starting from the
beginning of the next character. */
dfa_beg = mb_start;
- narrowed = true;
- }
- else if (dfafast)
- {
- /* Determine the end pointer to start with DFA. It's
- `match' by default. If the offset from prev_beg is
- lesser than (match - beg) * 4 and/or 64, set it to
- greatest value in them. A larger offset than the
- default means that DFA is preferred to KWset. */
- offset = (match - beg) * 4;
- if (offset < 64)
- offset = 64;
- if (prev_beg + offset > match)
- {
- end = prev_beg + offset;
- if (end < buflim)
- {
- end = memchr (end, eol, buflim - end);
- end = end ? end + 1 : buflim;
- }
- else
- end = buflim;
- }
- else
- {
- end = memchr (match, eol, buflim - match);
- end = end ? end + 1 : buflim;
- narrowed = true;
- }
- }
- else
- {
- end = memchr (match, eol, buflim - match);
- end = end ? end + 1 : buflim;
- narrowed = true;
}
}
/* Try matching with the superset of DFA, if it's defined. */
- if (superset && !(kwset && kwsm.index < kwset_exact_matches))
+ if (superset && !exact_kwset_match)
{
- next_beg = dfaexec (superset, dfa_beg, (char *) end, 1, &count,
NULL);
+ next_beg = dfaexec (superset, dfa_beg, (char *) end, 1,
+ &count, NULL);
/* If there's no match, or if we've matched the sentinel,
we're done. */
if (next_beg == NULL || next_beg == end)
continue;
- if (!narrowed)
+
+ /* Narrow down to the line we've found. */
+ if (count != 0)
{
- /* Narrow down to the line we've found. */
- if (count != 0)
- {
- beg = memrchr (buf, eol, next_beg - buf);
- beg = beg ? beg + 1 : buf;
-
- /* If dfaexec may match in multiple lines, try to
- match in one line. */
- end = beg;
- continue;
- }
- end = memchr (next_beg, eol, buflim - next_beg);
- end = end ? end + 1 : buflim;
- narrowed = true;
+ /* If dfaexec may match in multiple lines, try to
+ match in one line. */
+ end = memrchr (buf, eol, next_beg - buf);
+ end++;
+ continue;
}
+ end = memchr (next_beg, eol, buflim - next_beg);
+ end = end ? end + 1 : buflim;
}
/* Try matching with DFA. */
@@ -335,17 +309,15 @@ EGexecute (char const *buf, size_t size, size_t
*match_size,
we're done. */
if (next_beg == NULL || next_beg == end)
continue;
- if (!narrowed)
+
+ /* Narrow down to the line we've found. */
+ if (count != 0)
{
- /* Narrow down to the line we've found. */
- if (count != 0)
- {
- beg = memrchr (buf, eol, next_beg - buf);
- beg = beg ? beg + 1 : buf;
- }
- end = memchr (next_beg, eol, buflim - next_beg);
- end = end ? end + 1 : buflim;
+ beg = memrchr (buf, eol, next_beg - buf);
+ beg++;
}
+ end = memchr (next_beg, eol, buflim - next_beg);
+ end = end ? end + 1 : buflim;
/* Successful, no backreferences encountered! */
if (!backref)
@@ -364,8 +336,7 @@ EGexecute (char const *buf, size_t size, size_t *match_size,
if (TYPE_MAXIMUM (regoff_t) < end - beg - 1)
xalloc_die ();
- /* If we've made it to this point, this means DFA has seen
- a probable match, and we need to run it through Regex. */
+ /* Run the possible match through Regex. */
best_match = end;
best_len = 0;
for (i = 0; i < pcount; i++)
-----------------------------------------------------------------------
Summary of changes:
src/dfa.c | 26 +++----------
src/dfa.h | 15 ++-----
src/dfasearch.c | 113 ++++++++++++++++++++++++++++++-------------------------
3 files changed, 73 insertions(+), 81 deletions(-)
hooks/post-receive
--
grep
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- grep branch, master, updated. v2.18-115-g10ce910,
Paul Eggert <=