X-Git-Url: http://erislabs.net/gitweb/?a=blobdiff_plain;f=lib%2Fdiffseq.h;h=add2fedc30a764010ba0fdb23831a292f7a5f680;hb=4fd008794167d43f31b6d2cb565597a14c59d10a;hp=d765ccc1b727c98a6f8b06da07f3f433e3d8fd18;hpb=0023b193116338cebab85590087eaab3f82fde57;p=gnulib.git

diff --git a/lib/diffseq.h b/lib/diffseq.h
index d765ccc1b..add2fedc3 100644
--- a/lib/diffseq.h
+++ b/lib/diffseq.h
@@ -1,12 +1,12 @@
 /* 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
@@ -14,8 +14,7 @@
    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
@@ -50,13 +49,25 @@
      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
@@ -72,8 +83,8 @@
 struct context
 {
   /* Vectors being compared.  */
-  const ELEMENT *xvec;
-  const ELEMENT *yvec;
+  ELEMENT const *xvec;
+  ELEMENT const *yvec;
 
   /* Extra fields.  */
   EXTRA_CONTEXT_FIELDS
@@ -149,8 +160,8 @@ diag (OFFSET xoff, OFFSET xlim, OFFSET yoff, OFFSET ylim, bool find_minimal,
 {
   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. */
@@ -403,9 +414,12 @@ diag (OFFSET xoff, OFFSET xlim, OFFSET yoff, OFFSET ylim, bool find_minimal,
    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)
 {
@@ -431,12 +445,16 @@ compareseq (OFFSET xoff, OFFSET xlim, OFFSET yoff, OFFSET ylim,
     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
@@ -447,9 +465,13 @@ compareseq (OFFSET xoff, OFFSET xlim, OFFSET yoff, OFFSET ylim,
       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
@@ -458,5 +480,6 @@ compareseq (OFFSET xoff, OFFSET xlim, OFFSET yoff, OFFSET ylim,
 #undef EXTRA_CONTEXT_FIELDS
 #undef NOTE_DELETE
 #undef NOTE_INSERT
+#undef EARLY_ABORT
 #undef USE_HEURISTIC
 #undef OFFSET_MAX