[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
grep branch, master, updated. v2.25-13-g81ccbaa
|
From: |
Paul Eggert |
|
Subject: |
grep branch, master, updated. v2.25-13-g81ccbaa |
|
Date: |
Thu, 2 Jun 2016 22:26:25 +0000 (UTC) |
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 81ccbaa009d4147840f480991ed74845841a436e (commit)
via 4e9899f18fdda1fe19a26f7e1a3e40e87f8c7f2c (commit)
via 966f6586fbce3081ce6e5e2f9b55301b0ec3d2b4 (commit)
via 022c13e4754d3e79aa551040cd9983682a3382ef (commit)
via a3d42de483a29c1da381f5c3dad87cbbc86a5c70 (commit)
from c7526623f458084cbe947f0e1b43f328481b2ca3 (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=81ccbaa009d4147840f480991ed74845841a436e
commit 81ccbaa009d4147840f480991ed74845841a436e
Author: Paul Eggert <address@hidden>
Date: Thu Jun 2 15:24:38 2016 -0700
grep: simplify -F Aho-Corasick a bit
This removes some tuning that complicates the code without providing
performance benefits that I could measure (GCC 6.1, x86-64).
(acexec_trans): Do not hand-unroll. Unduplicate the code for a
transition step.
* src/kwset.c (struct kwset.kwsexec, bmexec, acexec_trans, acexec)
diff --git a/src/kwset.c b/src/kwset.c
index d14972f..7391990 100644
--- a/src/kwset.c
+++ b/src/kwset.c
@@ -932,110 +932,62 @@ acexec_trans (kwset_t kwset, char const *text, size_t
len,
struct trie * const *next;
struct trie const *trie, *accept;
char const *tp, *left, *lim;
- unsigned char c;
struct tree const *tree;
char const *trans;
/* Initialize register copies and look for easy ways out. */
if (len < kwset->mind)
return SIZE_MAX;
- if (!kwset->trans && kwset->maxd == 1 && kwset->words == 2)
+ trans = kwset->trans;
+ if (!trans && kwset->maxd == 1 && kwset->words == 2)
return memoff2_kwset (text, len, kwset, kwsmatch);
next = kwset->next;
- trans = kwset->trans;
+ trie = kwset->trie;
lim = text + len;
tp = text;
- if (kwset->trie->accepting)
+ if (!trie->accepting)
{
- trie = kwset->trie;
- goto match;
- }
-
- trie = next[U(tr (trans, *tp++))];
+ unsigned char c = tr (trans, *tp++);
- while (true)
- {
- if (tp < lim - 8)
+ while (true)
{
- while (!trie)
+ while (! (trie = next[c]))
{
- trie = next[U(tr (trans, *tp++))];
- if (trie)
- break;
- trie = next[U(tr (trans, *tp++))];
- if (trie)
- break;
- trie = next[U(tr (trans, *tp++))];
- if (trie)
- break;
- trie = next[U(tr (trans, *tp++))];
- if (trie)
- break;
- trie = next[U(tr (trans, *tp++))];
- if (trie)
- break;
- trie = next[U(tr (trans, *tp++))];
- if (trie)
- break;
- trie = next[U(tr (trans, *tp++))];
- if (trie)
- break;
- trie = next[U(tr (trans, *tp++))];
- if (trie)
- break;
- if (tp >= lim - 8)
- break;
- trie = next[U(tr (trans, *tp++))];
+ if (tp >= lim)
+ return SIZE_MAX;
+ c = tr (trans, *tp++);
}
- }
-
- while (!trie)
- {
- if (tp >= lim)
- return SIZE_MAX;
- trie = next[U(tr (trans, *tp++))];
- }
- if (trie->accepting)
- goto match;
- if (tp >= lim)
- return SIZE_MAX;
- c = tr (trans, *tp++);
- tree = trie->links;
-
- while (true)
- {
- if (c == tree->label)
+ while (true)
{
- trie = tree->trie;
if (trie->accepting)
goto match;
if (tp >= lim)
return SIZE_MAX;
c = tr (trans, *tp++);
- tree = trie->links;
- }
- else
- {
- tree = c < tree->label ? tree->llink : tree->rlink;
- if (! tree)
+
+ for (tree = trie->links; c != tree->label; )
{
- trie = trie->fail;
- if (!trie)
- break;
- if (trie->accepting)
+ tree = c < tree->label ? tree->llink : tree->rlink;
+ if (! tree)
{
- --tp;
- goto match;
+ trie = trie->fail;
+ if (!trie)
+ goto next_trie;
+ if (trie->accepting)
+ {
+ --tp;
+ goto match;
+ }
+ tree = trie->links;
}
- tree = trie->links;
}
+ trie = tree->trie;
}
+ next_trie:;
}
-
- trie = next[c];
}
match:
@@ -1051,7 +1003,7 @@ acexec_trans (kwset_t kwset, char const *text, size_t len,
{
struct trie const *accept1;
char const *left1;
- c = tr (trans, *tp++);
+ unsigned char c = tr (trans, *tp++);
tree = trie->links;
while (tree && c != tree->label)
tree = c < tree->label ? tree->llink : tree->rlink;
http://git.savannah.gnu.org/cgit/grep.git/commit/?id=4e9899f18fdda1fe19a26f7e1a3e40e87f8c7f2c
commit 81ccbaa009d4147840f480991ed74845841a436e
Author: Paul Eggert <address@hidden>
Date: Thu Jun 2 15:24:38 2016 -0700
grep: simplify -F Aho-Corasick a bit
This removes some tuning that complicates the code without providing
performance benefits that I could measure (GCC 6.1, x86-64).
(acexec_trans): Do not hand-unroll. Unduplicate the code for a
transition step.
* src/kwset.c (struct kwset.kwsexec, bmexec, acexec_trans, acexec)
diff --git a/src/kwset.c b/src/kwset.c
index d14972f..7391990 100644
--- a/src/kwset.c
+++ b/src/kwset.c
@@ -932,110 +932,62 @@ acexec_trans (kwset_t kwset, char const *text, size_t
len,
struct trie * const *next;
struct trie const *trie, *accept;
char const *tp, *left, *lim;
- unsigned char c;
struct tree const *tree;
char const *trans;
/* Initialize register copies and look for easy ways out. */
if (len < kwset->mind)
return SIZE_MAX;
- if (!kwset->trans && kwset->maxd == 1 && kwset->words == 2)
+ trans = kwset->trans;
+ if (!trans && kwset->maxd == 1 && kwset->words == 2)
return memoff2_kwset (text, len, kwset, kwsmatch);
next = kwset->next;
- trans = kwset->trans;
+ trie = kwset->trie;
lim = text + len;
tp = text;
- if (kwset->trie->accepting)
+ if (!trie->accepting)
{
- trie = kwset->trie;
- goto match;
- }
-
- trie = next[U(tr (trans, *tp++))];
+ unsigned char c = tr (trans, *tp++);
- while (true)
- {
- if (tp < lim - 8)
+ while (true)
{
- while (!trie)
+ while (! (trie = next[c]))
{
- trie = next[U(tr (trans, *tp++))];
- if (trie)
- break;
- trie = next[U(tr (trans, *tp++))];
- if (trie)
- break;
- trie = next[U(tr (trans, *tp++))];
- if (trie)
- break;
- trie = next[U(tr (trans, *tp++))];
- if (trie)
- break;
- trie = next[U(tr (trans, *tp++))];
- if (trie)
- break;
- trie = next[U(tr (trans, *tp++))];
- if (trie)
- break;
- trie = next[U(tr (trans, *tp++))];
- if (trie)
- break;
- trie = next[U(tr (trans, *tp++))];
- if (trie)
- break;
- if (tp >= lim - 8)
- break;
- trie = next[U(tr (trans, *tp++))];
+ if (tp >= lim)
+ return SIZE_MAX;
+ c = tr (trans, *tp++);
}
- }
-
- while (!trie)
- {
- if (tp >= lim)
- return SIZE_MAX;
- trie = next[U(tr (trans, *tp++))];
- }
- if (trie->accepting)
- goto match;
- if (tp >= lim)
- return SIZE_MAX;
- c = tr (trans, *tp++);
- tree = trie->links;
-
- while (true)
- {
- if (c == tree->label)
+ while (true)
{
- trie = tree->trie;
if (trie->accepting)
goto match;
if (tp >= lim)
return SIZE_MAX;
c = tr (trans, *tp++);
- tree = trie->links;
- }
- else
- {
- tree = c < tree->label ? tree->llink : tree->rlink;
- if (! tree)
+
+ for (tree = trie->links; c != tree->label; )
{
- trie = trie->fail;
- if (!trie)
- break;
- if (trie->accepting)
+ tree = c < tree->label ? tree->llink : tree->rlink;
+ if (! tree)
{
- --tp;
- goto match;
+ trie = trie->fail;
+ if (!trie)
+ goto next_trie;
+ if (trie->accepting)
+ {
+ --tp;
+ goto match;
+ }
+ tree = trie->links;
}
- tree = trie->links;
}
+ trie = tree->trie;
}
+ next_trie:;
}
-
- trie = next[c];
}
match:
@@ -1051,7 +1003,7 @@ acexec_trans (kwset_t kwset, char const *text, size_t len,
{
struct trie const *accept1;
char const *left1;
- c = tr (trans, *tp++);
+ unsigned char c = tr (trans, *tp++);
tree = trie->links;
while (tree && c != tree->label)
tree = c < tree->label ? tree->llink : tree->rlink;
http://git.savannah.gnu.org/cgit/grep.git/commit/?id=966f6586fbce3081ce6e5e2f9b55301b0ec3d2b4
commit 81ccbaa009d4147840f480991ed74845841a436e
Author: Paul Eggert <address@hidden>
Date: Thu Jun 2 15:24:38 2016 -0700
grep: simplify -F Aho-Corasick a bit
This removes some tuning that complicates the code without providing
performance benefits that I could measure (GCC 6.1, x86-64).
(acexec_trans): Do not hand-unroll. Unduplicate the code for a
transition step.
* src/kwset.c (struct kwset.kwsexec, bmexec, acexec_trans, acexec)
diff --git a/src/kwset.c b/src/kwset.c
index d14972f..7391990 100644
--- a/src/kwset.c
+++ b/src/kwset.c
@@ -932,110 +932,62 @@ acexec_trans (kwset_t kwset, char const *text, size_t
len,
struct trie * const *next;
struct trie const *trie, *accept;
char const *tp, *left, *lim;
- unsigned char c;
struct tree const *tree;
char const *trans;
/* Initialize register copies and look for easy ways out. */
if (len < kwset->mind)
return SIZE_MAX;
- if (!kwset->trans && kwset->maxd == 1 && kwset->words == 2)
+ trans = kwset->trans;
+ if (!trans && kwset->maxd == 1 && kwset->words == 2)
return memoff2_kwset (text, len, kwset, kwsmatch);
next = kwset->next;
- trans = kwset->trans;
+ trie = kwset->trie;
lim = text + len;
tp = text;
- if (kwset->trie->accepting)
+ if (!trie->accepting)
{
- trie = kwset->trie;
- goto match;
- }
-
- trie = next[U(tr (trans, *tp++))];
+ unsigned char c = tr (trans, *tp++);
- while (true)
- {
- if (tp < lim - 8)
+ while (true)
{
- while (!trie)
+ while (! (trie = next[c]))
{
- trie = next[U(tr (trans, *tp++))];
- if (trie)
- break;
- trie = next[U(tr (trans, *tp++))];
- if (trie)
- break;
- trie = next[U(tr (trans, *tp++))];
- if (trie)
- break;
- trie = next[U(tr (trans, *tp++))];
- if (trie)
- break;
- trie = next[U(tr (trans, *tp++))];
- if (trie)
- break;
- trie = next[U(tr (trans, *tp++))];
- if (trie)
- break;
- trie = next[U(tr (trans, *tp++))];
- if (trie)
- break;
- trie = next[U(tr (trans, *tp++))];
- if (trie)
- break;
- if (tp >= lim - 8)
- break;
- trie = next[U(tr (trans, *tp++))];
+ if (tp >= lim)
+ return SIZE_MAX;
+ c = tr (trans, *tp++);
}
- }
-
- while (!trie)
- {
- if (tp >= lim)
- return SIZE_MAX;
- trie = next[U(tr (trans, *tp++))];
- }
- if (trie->accepting)
- goto match;
- if (tp >= lim)
- return SIZE_MAX;
- c = tr (trans, *tp++);
- tree = trie->links;
-
- while (true)
- {
- if (c == tree->label)
+ while (true)
{
- trie = tree->trie;
if (trie->accepting)
goto match;
if (tp >= lim)
return SIZE_MAX;
c = tr (trans, *tp++);
- tree = trie->links;
- }
- else
- {
- tree = c < tree->label ? tree->llink : tree->rlink;
- if (! tree)
+
+ for (tree = trie->links; c != tree->label; )
{
- trie = trie->fail;
- if (!trie)
- break;
- if (trie->accepting)
+ tree = c < tree->label ? tree->llink : tree->rlink;
+ if (! tree)
{
- --tp;
- goto match;
+ trie = trie->fail;
+ if (!trie)
+ goto next_trie;
+ if (trie->accepting)
+ {
+ --tp;
+ goto match;
+ }
+ tree = trie->links;
}
- tree = trie->links;
}
+ trie = tree->trie;
}
+ next_trie:;
}
-
- trie = next[c];
}
match:
@@ -1051,7 +1003,7 @@ acexec_trans (kwset_t kwset, char const *text, size_t len,
{
struct trie const *accept1;
char const *left1;
- c = tr (trans, *tp++);
+ unsigned char c = tr (trans, *tp++);
tree = trie->links;
while (tree && c != tree->label)
tree = c < tree->label ? tree->llink : tree->rlink;
http://git.savannah.gnu.org/cgit/grep.git/commit/?id=022c13e4754d3e79aa551040cd9983682a3382ef
commit 81ccbaa009d4147840f480991ed74845841a436e
Author: Paul Eggert <address@hidden>
Date: Thu Jun 2 15:24:38 2016 -0700
grep: simplify -F Aho-Corasick a bit
This removes some tuning that complicates the code without providing
performance benefits that I could measure (GCC 6.1, x86-64).
(acexec_trans): Do not hand-unroll. Unduplicate the code for a
transition step.
* src/kwset.c (struct kwset.kwsexec, bmexec, acexec_trans, acexec)
diff --git a/src/kwset.c b/src/kwset.c
index d14972f..7391990 100644
--- a/src/kwset.c
+++ b/src/kwset.c
@@ -932,110 +932,62 @@ acexec_trans (kwset_t kwset, char const *text, size_t
len,
struct trie * const *next;
struct trie const *trie, *accept;
char const *tp, *left, *lim;
- unsigned char c;
struct tree const *tree;
char const *trans;
/* Initialize register copies and look for easy ways out. */
if (len < kwset->mind)
return SIZE_MAX;
- if (!kwset->trans && kwset->maxd == 1 && kwset->words == 2)
+ trans = kwset->trans;
+ if (!trans && kwset->maxd == 1 && kwset->words == 2)
return memoff2_kwset (text, len, kwset, kwsmatch);
next = kwset->next;
- trans = kwset->trans;
+ trie = kwset->trie;
lim = text + len;
tp = text;
- if (kwset->trie->accepting)
+ if (!trie->accepting)
{
- trie = kwset->trie;
- goto match;
- }
-
- trie = next[U(tr (trans, *tp++))];
+ unsigned char c = tr (trans, *tp++);
- while (true)
- {
- if (tp < lim - 8)
+ while (true)
{
- while (!trie)
+ while (! (trie = next[c]))
{
- trie = next[U(tr (trans, *tp++))];
- if (trie)
- break;
- trie = next[U(tr (trans, *tp++))];
- if (trie)
- break;
- trie = next[U(tr (trans, *tp++))];
- if (trie)
- break;
- trie = next[U(tr (trans, *tp++))];
- if (trie)
- break;
- trie = next[U(tr (trans, *tp++))];
- if (trie)
- break;
- trie = next[U(tr (trans, *tp++))];
- if (trie)
- break;
- trie = next[U(tr (trans, *tp++))];
- if (trie)
- break;
- trie = next[U(tr (trans, *tp++))];
- if (trie)
- break;
- if (tp >= lim - 8)
- break;
- trie = next[U(tr (trans, *tp++))];
+ if (tp >= lim)
+ return SIZE_MAX;
+ c = tr (trans, *tp++);
}
- }
-
- while (!trie)
- {
- if (tp >= lim)
- return SIZE_MAX;
- trie = next[U(tr (trans, *tp++))];
- }
- if (trie->accepting)
- goto match;
- if (tp >= lim)
- return SIZE_MAX;
- c = tr (trans, *tp++);
- tree = trie->links;
-
- while (true)
- {
- if (c == tree->label)
+ while (true)
{
- trie = tree->trie;
if (trie->accepting)
goto match;
if (tp >= lim)
return SIZE_MAX;
c = tr (trans, *tp++);
- tree = trie->links;
- }
- else
- {
- tree = c < tree->label ? tree->llink : tree->rlink;
- if (! tree)
+
+ for (tree = trie->links; c != tree->label; )
{
- trie = trie->fail;
- if (!trie)
- break;
- if (trie->accepting)
+ tree = c < tree->label ? tree->llink : tree->rlink;
+ if (! tree)
{
- --tp;
- goto match;
+ trie = trie->fail;
+ if (!trie)
+ goto next_trie;
+ if (trie->accepting)
+ {
+ --tp;
+ goto match;
+ }
+ tree = trie->links;
}
- tree = trie->links;
}
+ trie = tree->trie;
}
+ next_trie:;
}
-
- trie = next[c];
}
match:
@@ -1051,7 +1003,7 @@ acexec_trans (kwset_t kwset, char const *text, size_t len,
{
struct trie const *accept1;
char const *left1;
- c = tr (trans, *tp++);
+ unsigned char c = tr (trans, *tp++);
tree = trie->links;
while (tree && c != tree->label)
tree = c < tree->label ? tree->llink : tree->rlink;
http://git.savannah.gnu.org/cgit/grep.git/commit/?id=a3d42de483a29c1da381f5c3dad87cbbc86a5c70
commit 81ccbaa009d4147840f480991ed74845841a436e
Author: Paul Eggert <address@hidden>
Date: Thu Jun 2 15:24:38 2016 -0700
grep: simplify -F Aho-Corasick a bit
This removes some tuning that complicates the code without providing
performance benefits that I could measure (GCC 6.1, x86-64).
(acexec_trans): Do not hand-unroll. Unduplicate the code for a
transition step.
* src/kwset.c (struct kwset.kwsexec, bmexec, acexec_trans, acexec)
diff --git a/src/kwset.c b/src/kwset.c
index d14972f..7391990 100644
--- a/src/kwset.c
+++ b/src/kwset.c
@@ -932,110 +932,62 @@ acexec_trans (kwset_t kwset, char const *text, size_t
len,
struct trie * const *next;
struct trie const *trie, *accept;
char const *tp, *left, *lim;
- unsigned char c;
struct tree const *tree;
char const *trans;
/* Initialize register copies and look for easy ways out. */
if (len < kwset->mind)
return SIZE_MAX;
- if (!kwset->trans && kwset->maxd == 1 && kwset->words == 2)
+ trans = kwset->trans;
+ if (!trans && kwset->maxd == 1 && kwset->words == 2)
return memoff2_kwset (text, len, kwset, kwsmatch);
next = kwset->next;
- trans = kwset->trans;
+ trie = kwset->trie;
lim = text + len;
tp = text;
- if (kwset->trie->accepting)
+ if (!trie->accepting)
{
- trie = kwset->trie;
- goto match;
- }
-
- trie = next[U(tr (trans, *tp++))];
+ unsigned char c = tr (trans, *tp++);
- while (true)
- {
- if (tp < lim - 8)
+ while (true)
{
- while (!trie)
+ while (! (trie = next[c]))
{
- trie = next[U(tr (trans, *tp++))];
- if (trie)
- break;
- trie = next[U(tr (trans, *tp++))];
- if (trie)
- break;
- trie = next[U(tr (trans, *tp++))];
- if (trie)
- break;
- trie = next[U(tr (trans, *tp++))];
- if (trie)
- break;
- trie = next[U(tr (trans, *tp++))];
- if (trie)
- break;
- trie = next[U(tr (trans, *tp++))];
- if (trie)
- break;
- trie = next[U(tr (trans, *tp++))];
- if (trie)
- break;
- trie = next[U(tr (trans, *tp++))];
- if (trie)
- break;
- if (tp >= lim - 8)
- break;
- trie = next[U(tr (trans, *tp++))];
+ if (tp >= lim)
+ return SIZE_MAX;
+ c = tr (trans, *tp++);
}
- }
-
- while (!trie)
- {
- if (tp >= lim)
- return SIZE_MAX;
- trie = next[U(tr (trans, *tp++))];
- }
- if (trie->accepting)
- goto match;
- if (tp >= lim)
- return SIZE_MAX;
- c = tr (trans, *tp++);
- tree = trie->links;
-
- while (true)
- {
- if (c == tree->label)
+ while (true)
{
- trie = tree->trie;
if (trie->accepting)
goto match;
if (tp >= lim)
return SIZE_MAX;
c = tr (trans, *tp++);
- tree = trie->links;
- }
- else
- {
- tree = c < tree->label ? tree->llink : tree->rlink;
- if (! tree)
+
+ for (tree = trie->links; c != tree->label; )
{
- trie = trie->fail;
- if (!trie)
- break;
- if (trie->accepting)
+ tree = c < tree->label ? tree->llink : tree->rlink;
+ if (! tree)
{
- --tp;
- goto match;
+ trie = trie->fail;
+ if (!trie)
+ goto next_trie;
+ if (trie->accepting)
+ {
+ --tp;
+ goto match;
+ }
+ tree = trie->links;
}
- tree = trie->links;
}
+ trie = tree->trie;
}
+ next_trie:;
}
-
- trie = next[c];
}
match:
@@ -1051,7 +1003,7 @@ acexec_trans (kwset_t kwset, char const *text, size_t len,
{
struct trie const *accept1;
char const *left1;
- c = tr (trans, *tp++);
+ unsigned char c = tr (trans, *tp++);
tree = trie->links;
while (tree && c != tree->label)
tree = c < tree->label ? tree->llink : tree->rlink;
-----------------------------------------------------------------------
Summary of changes:
NEWS | 6 +
src/dfasearch.c | 2 +-
src/kwsearch.c | 18 ++-
src/kwset.c | 421 +++++++++++++++++++++++++++++++++++++++--------------
src/kwset.h | 5 +-
src/searchutils.c | 4 +-
6 files changed, 335 insertions(+), 121 deletions(-)
hooks/post-receive
--
grep
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- grep branch, master, updated. v2.25-13-g81ccbaa,
Paul Eggert <=