>From 617a6097466d818e425609eff9ed85039aea25db Mon Sep 17 00:00:00 2001 From: Norihiro Tanaka Date: Wed, 19 Sep 2018 08:35:49 -0700 Subject: [PATCH] dfa: optimization for state merge * lib/dfa.c (merge2): New function. (merge_nfa_state): Use it. --- ChangeLog | 6 ++++++ lib/dfa.c | 18 ++++++++++++++++-- 2 files changed, 22 insertions(+), 2 deletions(-) diff --git a/ChangeLog b/ChangeLog index 181039c1a..b9d7b30d6 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,9 @@ +2018-09-19 Norihiro Tanaka + + dfa: optimization for state merge + * lib/dfa.c (merge2): New function. + (merge_nfa_state): Use it. + 2018-09-18 Jim Meyering dfa: trivial comment fix: s/is/if/ diff --git a/lib/dfa.c b/lib/dfa.c index 13b2a0baf..d04bcbe64 100644 --- a/lib/dfa.c +++ b/lib/dfa.c @@ -2102,6 +2102,21 @@ merge (position_set const *s1, position_set const *s2, position_set *m) 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 @@ merge_nfa_state (struct dfa *d, size_t *queue, ptrdiff_t nqueue, size_t tindex, 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; -- 2.17.1