]> Savannah Git Hosting - gnulib.git/commit
dfa: improve worst-case 'replace' performance
authorPaul Eggert <eggert@cs.ucla.edu>
Mon, 19 Dec 2016 01:35:19 +0000 (17:35 -0800)
committerPaul Eggert <eggert@cs.ucla.edu>
Mon, 19 Dec 2016 07:25:48 +0000 (23:25 -0800)
commitb783f1ebd54de36c7459ff1a206e46340e68b727
treea147ca0cb43fe4dd5fd9d12e99b94e1dcc10786f
parentd6df3873c7abc243683d0e8fccbfde4e76f23e53
dfa: improve worst-case 'replace' performance

See my note in Bug#22357#71.
* lib/dfa.c (insert, delete): Rework to avoid duplicate test.
(merge_constrained): New function, which is like
the old 'merge' function, except with a new argument C2.
Simplify the body by avoiding the need for different sections
of code depending on whether one input is exhausted.
(merge): Use the new function.
(delete): Return the constraint of the deleted position,
not the entire position.  Caller changed.
(replace): Change from O(N*(N + log N)) to O(N log N) algorithm.
ChangeLog
lib/dfa.c