]> granicus.if.org Git - re2c/commit
libre2c: compare histories in a trie without reconstructing them.
authorUlya Trofimovich <skvadrik@gmail.com>
Mon, 18 Feb 2019 16:42:07 +0000 (16:42 +0000)
committerUlya Trofimovich <skvadrik@gmail.com>
Mon, 18 Feb 2019 16:42:07 +0000 (16:42 +0000)
commit2a7158b401d7e925696fc1b0c8da37a59e364dd4
treea9ef43714290908457c838f3361bee484dc5ecec
parente9799d313a32aab1b8199d2e21f3a28a99871078
libre2c: compare histories in a trie without reconstructing them.

Previously we used to unwing each history, store it as a linear sequence
in a separate buffer, and then iterate buffers from the beginning of
histories to fing the fork point.

This reconstruction step can be avoided, because we can find fork by
tracing both histories together from tail to root, element by element,
until their indices coincide (this is the fork point. Someone called
thos "two-fingers algorithm".
re2c/lib/regexec_nfa_posix.cc