Date: Mon, 22 Aug 2011 11:22:13 +0000 (UTC) From: Gabor Kovesdan <gabor@FreeBSD.org> To: src-committers@freebsd.org, svn-src-user@freebsd.org Subject: svn commit: r225077 - user/gabor/tre-integration/contrib/tre/lib Message-ID: <201108221122.p7MBMDLg048533@svn.freebsd.org>
next in thread | raw e-mail | index | archive | help
Author: gabor Date: Mon Aug 22 11:22:13 2011 New Revision: 225077 URL: http://svn.freebsd.org/changeset/base/225077 Log: - Add a general comment Modified: user/gabor/tre-integration/contrib/tre/lib/tre-heuristic.c Modified: user/gabor/tre-integration/contrib/tre/lib/tre-heuristic.c ============================================================================== --- user/gabor/tre-integration/contrib/tre/lib/tre-heuristic.c Mon Aug 22 11:18:47 2011 (r225076) +++ user/gabor/tre-integration/contrib/tre/lib/tre-heuristic.c Mon Aug 22 11:22:13 2011 (r225077) @@ -40,6 +40,21 @@ #include "xmalloc.h" /* + * A full regex implementation requires a finite state automaton + * and using an automaton is always about a trade-off. A DFA is + * fast but complex and requires more memory because of the + * high number of states. NFA is slower but simpler and uses less + * memory. Regular expression matching is an underlying common task + * that is required to be efficient but correctness, clean and + * maintanable code are also requirements. So what we do is using + * an NFA implementation and heuristically locate the possible matches + * with a cheaper algorithm and only apply the heavy one to the + * possibly matching segments. This allows us to benefit from the + * advantages of an NFA implementation reducing the effect of the + * performance impact. + */ + +/* * Parses bracket expression seeking to the end of the enclosed text. * The parameters are the opening (oe) and closing elements (ce). * Can handle nested bracket expressions.
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201108221122.p7MBMDLg048533>