/* 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;
+ /* Vectors being compared. */
+ ELEMENT const *xvec;
+ ELEMENT const *yvec;
- /* Extra fields. */
+ /* Extra fields. */
EXTRA_CONTEXT_FIELDS
/* Vector, indexed by diagonal, containing 1 + the X coordinate of the point
furthest along the given diagonal in the forward search of the edit
- matrix. */
+ matrix. */
OFFSET *fdiag;
/* Vector, indexed by diagonal, containing the X coordinate of the point
furthest along the given diagonal in the backward search of the edit
- matrix. */
+ matrix. */
OFFSET *bdiag;
#ifdef USE_HEURISTIC
/* This corresponds to the diff -H flag. With this heuristic, for
vectors with a constant small density of changes, the algorithm is
linear in the vectors size. */
- int heuristic;
+ bool heuristic;
#endif
/* Edit scripts longer than this are too expensive to compute. */
bool hi_minimal;
};
+
/* Find the midpoint of the shortest edit script for a specified portion
of the two vectors.
When the two searches meet, we have found the midpoint of the shortest
edit sequence.
- If FIND_MINIMAL is true, find the minimal edit script regardless
- of expense. Otherwise, if the search is too expensive, use
- heuristics to stop the search and report a suboptimal answer.
+ If FIND_MINIMAL is true, find the minimal edit script regardless of
+ expense. Otherwise, if the search is too expensive, use heuristics to
+ stop the search and report a suboptimal answer.
Set PART->(xmid,ymid) to the midpoint (XMID,YMID). The diagonal number
XMID - YMID equals the number of inserted elements minus the number
static void
diag (OFFSET xoff, OFFSET xlim, OFFSET yoff, OFFSET ylim, bool find_minimal,
- struct partition *part, struct context const *ctxt)
+ struct partition *part, struct context *ctxt)
{
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. */
OFFSET thi = bd[d + 1];
OFFSET x0 = tlo < thi ? tlo : thi - 1;
- for (x = x0, y = x - d;
+ for (x = x0, y = x0 - d;
xoff < x && yoff < y && EQUAL (xv[x - 1], yv[y - 1]);
x--, y--)
continue;
}
}
+
/* Compare in detail contiguous subsequences of the two vectors
which are known, as a whole, to match each other.
If FIND_MINIMAL, find a minimal difference no matter how
expensive it is.
- The results are recorded in the vectors files[N].changed, by storing 1
- in the element for each line that is an insertion or deletion. */
+ 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 const *ctxt)
+ bool find_minimal, struct context *ctxt)
{
ELEMENT const *xv = ctxt->xvec; /* Help the compiler. */
ELEMENT const *yv = ctxt->yvec;
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 EQUAL
#undef OFFSET
-#undef OFFSET_MAX
#undef EXTRA_CONTEXT_FIELDS
#undef NOTE_DELETE
#undef NOTE_INSERT
+#undef EARLY_ABORT
+#undef USE_HEURISTIC
+#undef OFFSET_MAX
projects / gnulib.git / blobdiff