Mercurial > gnulib
changeset 39862:f61cd4b41f21
dfa: optimization for state merge
* lib/dfa.c (merge2): New function.
(merge_nfa_state): Use it.
| author | Norihiro Tanaka <noritnk@kcn.ne.jp> |
|---|---|
| date | Wed, 19 Sep 2018 08:35:49 -0700 |
| parents | 5d7b30167723 |
| children | c9d15b629a3a |
| files | ChangeLog lib/dfa.c |
| diffstat | 2 files changed, 22 insertions(+), 2 deletions(-) [+] |
line wrap: on
line diff
--- a/ChangeLog Tue Sep 18 21:26:01 2018 -0700 +++ b/ChangeLog Wed Sep 19 08:35:49 2018 -0700 @@ -1,3 +1,9 @@ +2018-09-19 Norihiro Tanaka <noritnk@kcn.ne.jp> + + dfa: optimization for state merge + * lib/dfa.c (merge2): New function. + (merge_nfa_state): Use it. + 2018-09-18 Jim Meyering <meyering@fb.com> dfa: trivial comment fix: s/is/if/
--- a/lib/dfa.c Tue Sep 18 21:26:01 2018 -0700 +++ b/lib/dfa.c Wed Sep 19 08:35:49 2018 -0700 @@ -2102,6 +2102,21 @@ merge_constrained (s1, s2, -1, m); } +static void +merge2 (position_set *dst, position_set const *src, position_set *m) +{ + if (src->nelem < 4) + { + for (ptrdiff_t i = 0; i < src->nelem; ++i) + insert (src->elems[i], dst); + } + else + { + merge (src, dst, m); + copy (m, dst); + } +} + /* Delete a position from a set. Return the nonzero constraint of the deleted position, or zero if there was no such position. */ static unsigned int @@ -2388,8 +2403,7 @@ if (flags[sindex] & OPT_REPEAT) delete (sindex, &follows[sindex]); - merge (&follows[dindex], &follows[sindex], merged); - copy (merged, &follows[dindex]); + merge2 (&follows[dindex], &follows[sindex], merged); /* Mark it as pruned in future. */ follows[tindex].elems[j].constraint = 0;