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

diff --git a/lib/diffseq.h b/lib/diffseq.h
index ad8b8b3a2..add2fedc3 100644
--- a/lib/diffseq.h
+++ b/lib/diffseq.h
@@ -49,6 +49,8 @@
      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.
    Before including this file, you also need to include:
@@ -61,6 +63,11 @@
 #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
@@ -76,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
@@ -153,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. */
@@ -407,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)
 {
@@ -435,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
@@ -451,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
@@ -462,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