/* Analyze differences between two vectors.
- Copyright (C) 1988-1989, 1992-1995, 2001-2004, 2006, 2007 Free
+ Copyright (C) 1988-1989, 1992-1995, 2001-2004, 2006-2008 Free
Software Foundation, Inc.
- This program is free software; you can redistribute it and/or modify
+ This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
- the Free Software Foundation; either version 2, or (at your option)
- any later version.
+ the Free Software Foundation; either version 3 of the License, or
+ (at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
- along with this program; if not, write to the Free Software Foundation,
- Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
+ along with this program. If not, see <http://www.gnu.org/licenses/>. */
/* The basic idea is to consider two vectors as similar if, when
EXTRA_CONTEXT_FIELDS Declarations of fields for 'struct context'.
NOTE_DELETE(ctxt, xoff) Record the removal of the object xvec[xoff].
NOTE_INSERT(ctxt, yoff) Record the insertion of the object yvec[yoff].
+ EARLY_ABORT(ctxt) (Optional) A boolean expression that triggers an
+ early abort of the computation.
USE_HEURISTIC (Optional) Define if you want to support the
- heuristic for large vectors. */
+ heuristic for large vectors.
+ Before including this file, you also need to include:
+ #include <limits.h>
+ #include <stdbool.h>
+ #include "minmax.h"
+ */
/* Maximum value of type OFFSET. */
#define OFFSET_MAX \
((((OFFSET)1 << (sizeof (OFFSET) * CHAR_BIT - 2)) - 1) * 2 + 1)
+/* Default to no early abort. */
+#ifndef EARLY_ABORT
+# define EARLY_ABORT(ctxt) false
+#endif
+
/* Use this to suppress gcc's `...may be used before initialized' warnings. */
#ifndef IF_LINT
# ifdef lint
struct context
{
/* Vectors being compared. */
- const ELEMENT *xvec;
- const ELEMENT *yvec;
+ ELEMENT const *xvec;
+ ELEMENT const *yvec;
/* Extra fields. */
EXTRA_CONTEXT_FIELDS
{
OFFSET *const fd = ctxt->fdiag; /* Give the compiler a chance. */
OFFSET *const bd = ctxt->bdiag; /* Additional help for the compiler. */
- const ELEMENT *const xv = ctxt->xvec; /* Still more help for the compiler. */
- const ELEMENT *const yv = ctxt->yvec; /* And more and more . . . */
+ ELEMENT const *const xv = ctxt->xvec; /* Still more help for the compiler. */
+ ELEMENT const *const yv = ctxt->yvec; /* And more and more . . . */
const OFFSET dmin = xoff - ylim; /* Minimum valid diagonal. */
const OFFSET dmax = xlim - yoff; /* Maximum valid diagonal. */
const OFFSET fmid = xoff - yoff; /* Center diagonal of top-down search. */
If FIND_MINIMAL, find a minimal difference no matter how
expensive it is.
- The results are recorded by invoking NOTE_DELETE and NOTE_INSERT. */
+ The results are recorded by invoking NOTE_DELETE and NOTE_INSERT.
-static void
+ Return false if terminated normally, or true if terminated through early
+ abort. */
+
+static bool
compareseq (OFFSET xoff, OFFSET xlim, OFFSET yoff, OFFSET ylim,
bool find_minimal, struct context *ctxt)
{
while (yoff < ylim)
{
NOTE_INSERT (ctxt, yoff);
+ if (EARLY_ABORT (ctxt))
+ return true;
yoff++;
}
else if (yoff == ylim)
while (xoff < xlim)
{
NOTE_DELETE (ctxt, xoff);
+ if (EARLY_ABORT (ctxt))
+ return true;
xoff++;
}
else
diag (xoff, xlim, yoff, ylim, find_minimal, &part, ctxt);
/* Use the partitions to split this problem into subproblems. */
- compareseq (xoff, part.xmid, yoff, part.ymid, part.lo_minimal, ctxt);
- compareseq (part.xmid, xlim, part.ymid, ylim, part.hi_minimal, ctxt);
+ if (compareseq (xoff, part.xmid, yoff, part.ymid, part.lo_minimal, ctxt))
+ return true;
+ if (compareseq (part.xmid, xlim, part.ymid, ylim, part.hi_minimal, ctxt))
+ return true;
}
+
+ return false;
}
#undef ELEMENT
#undef EXTRA_CONTEXT_FIELDS
#undef NOTE_DELETE
#undef NOTE_INSERT
+#undef EARLY_ABORT
#undef USE_HEURISTIC
#undef OFFSET_MAX