Update or remove references to gettext release.

[gnulib.git] / lib / diffseq.h

diff --git a/lib/diffseq.h b/lib/diffseq.h
index b8e598d..add2fed 100644 (file)
--- a/lib/diffseq.h
+++ b/lib/diffseq.h
@@ -1,12 +1,12 @@
 /* Analyze differences between two vectors.
 
 /* 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.
 
    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
    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
 
    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
    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
 
 
 /* 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].
      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
      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)
 
 
 /* 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
 /* Use this to suppress gcc's `...may be used before initialized' warnings. */
 #ifndef IF_LINT
 # ifdef lint


@@ -71,28 +82,28 @@
  */
 struct context
 {
  */
 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
   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
   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.  */
   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.  */
   #endif
 
   /* Edit scripts longer than this are too expensive to compute.  */


@@ -115,6 +126,7 @@ struct partition
   bool hi_minimal;
 };
 
   bool hi_minimal;
 };
 

+

 /* Find the midpoint of the shortest edit script for a specified portion
    of the two vectors.
 
 /* Find the midpoint of the shortest edit script for a specified portion
    of the two vectors.
 


@@ -123,9 +135,9 @@ struct partition
    When the two searches meet, we have found the midpoint of the shortest
    edit sequence.
 
    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
 
    Set PART->(xmid,ymid) to the midpoint (XMID,YMID).  The diagonal number
    XMID - YMID equals the number of inserted elements minus the number


@@ -144,12 +156,12 @@ struct partition
 
 static void
 diag (OFFSET xoff, OFFSET xlim, OFFSET yoff, OFFSET ylim, bool find_minimal,
 
 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. */
 {
   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. */
   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. */


@@ -220,7 +232,7 @@ diag (OFFSET xoff, OFFSET xlim, OFFSET yoff, OFFSET ylim, bool find_minimal,
          OFFSET thi = bd[d + 1];
          OFFSET x0 = tlo < thi ? tlo : thi - 1;
 
          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;
               xoff < x && yoff < y && EQUAL (xv[x - 1], yv[y - 1]);
               x--, y--)
            continue;


@@ -390,6 +402,7 @@ diag (OFFSET xoff, OFFSET xlim, OFFSET yoff, OFFSET ylim, bool find_minimal,
     }
 }
 
     }
 }
 

+

 /* Compare in detail contiguous subsequences of the two vectors
    which are known, as a whole, to match each other.
 
 /* Compare in detail contiguous subsequences of the two vectors
    which are known, as a whole, to match each other.
 


@@ -401,12 +414,14 @@ 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.
 
    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,
 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;
 {
   ELEMENT const *xv = ctxt->xvec; /* Help the compiler.  */
   ELEMENT const *yv = ctxt->yvec;


@@ -430,12 +445,16 @@ compareseq (OFFSET xoff, OFFSET xlim, OFFSET yoff, OFFSET ylim,
     while (yoff < ylim)
       {
        NOTE_INSERT (ctxt, yoff);
     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);
        yoff++;
       }
   else if (yoff == ylim)
     while (xoff < xlim)
       {
        NOTE_DELETE (ctxt, xoff);

+       if (EARLY_ABORT (ctxt))
+         return true;

        xoff++;
       }
   else
        xoff++;
       }
   else


@@ -446,15 +465,21 @@ 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.  */
       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 ELEMENT
 #undef EQUAL
 #undef OFFSET

-#undef OFFSET_MAX

 #undef EXTRA_CONTEXT_FIELDS
 #undef NOTE_DELETE
 #undef NOTE_INSERT
 #undef EXTRA_CONTEXT_FIELDS
 #undef NOTE_DELETE
 #undef NOTE_INSERT

+#undef EARLY_ABORT
+#undef USE_HEURISTIC
+#undef OFFSET_MAX