]> Savannah Git Hosting - gnulib.git/commit
dfa: use backward set in removal of epsilon closure
authorNorihiro Tanaka <noritnk@kcn.ne.jp>
Sun, 13 Sep 2020 01:51:55 +0000 (18:51 -0700)
committerPaul Eggert <eggert@cs.ucla.edu>
Sun, 13 Sep 2020 01:53:36 +0000 (18:53 -0700)
commitda0e8454a8e68035ef4b87dbb9097f85df6ece27
tree004978b5276a5715f557e5a3da71402d520068d1
parentd468be5b5950bc5f2e0a5a4fbaeb0ea6a88c4c9f
dfa: use backward set in removal of epsilon closure

When removing in epsilon closure, the code searched all nodes
sequentially, and this was slow for some cases.  Build a backward
set before search, and only check previous position with the set.
Problem reported in <https://bugs.gnu.org/40634>.
* lib/dfa.c (struct dfa): New member 'epsilon'.
(addtok_mb): Check whether a pattern has epsilon node or not.
(epsclosure): New arg BACKWORD; caller changed.  When removing
epsilon node and reconnecting, check only previous positions.
Treat BEG as if it were character.
(dfaanalyze): Build backward set.
lib/dfa.c