Mercurial > gnulib

changeset 7436:bea4f38a0f8d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Make multithread-safe.
author Bruno Haible <bruno@clisp.org>
date Sat, 07 Oct 2006 16:52:57 +0000
parents 483a70ceec47
children e70f23471c45
files lib/analyze.c lib/diffseq.h
diffstat 2 files changed, 56 insertions(+), 47 deletions(-) [+]
line wrap: on
line diff
--- a/lib/analyze.c	Sat Oct 07 16:52:38 2006 +0000
+++ b/lib/analyze.c	Sat Oct 07 16:52:57 2006 +0000
@@ -465,7 +465,6 @@
 int
 diff_2_files (struct comparison *cmp)
 {
-  lin diags;
   int f;
   struct change *e, *p;
   struct change *script;
@@ -535,6 +534,10 @@
     }
   else
     {
+      struct context ctxt;
+      lin diags;
+      OFFSET too_expensive;
+
       /* Allocate vectors for the results of comparison:
 	 a flag for each line of each file, saying whether that line
 	 is an insertion or deletion.
@@ -554,31 +557,31 @@
       /* Now do the main comparison algorithm, considering just the
 	 undiscarded lines.  */
 
-      xvec = cmp->file[0].undiscarded;
-      yvec = cmp->file[1].undiscarded;
+      ctxt.xvec = cmp->file[0].undiscarded;
+      ctxt.yvec = cmp->file[1].undiscarded;
       diags = (cmp->file[0].nondiscarded_lines
 	       + cmp->file[1].nondiscarded_lines + 3);
-      fdiag = xmalloc (diags * (2 * sizeof *fdiag));
-      bdiag = fdiag + diags;
-      fdiag += cmp->file[1].nondiscarded_lines + 1;
-      bdiag += cmp->file[1].nondiscarded_lines + 1;
+      ctxt.fdiag = xmalloc (diags * (2 * sizeof *fdiag));
+      ctxt.bdiag = fdiag + diags;
+      ctxt.fdiag += cmp->file[1].nondiscarded_lines + 1;
+      ctxt.bdiag += cmp->file[1].nondiscarded_lines + 1;
 
-      heuristic = speed_large_files;
+      ctxt.heuristic = speed_large_files;
 
       /* Set TOO_EXPENSIVE to be approximate square root of input size,
 	 bounded below by 256.  */
       too_expensive = 1;
       for (;  diags != 0;  diags >>= 2)
 	too_expensive <<= 1;
-      too_expensive = MAX (256, too_expensive);
+      ctxt.too_expensive = MAX (256, too_expensive);
 
       files[0] = cmp->file[0];
       files[1] = cmp->file[1];
 
       compareseq (0, cmp->file[0].nondiscarded_lines,
-		  0, cmp->file[1].nondiscarded_lines, minimal);
+		  0, cmp->file[1].nondiscarded_lines, minimal, &ctxt);
 
-      free (fdiag - (cmp->file[1].nondiscarded_lines + 1));
+      free (ctxt.fdiag - (cmp->file[1].nondiscarded_lines + 1));
 
       /* Modify the results slightly to make them prettier
 	 in cases where that can validly be done.  */
--- a/lib/diffseq.h	Sat Oct 07 16:52:38 2006 +0000
+++ b/lib/diffseq.h	Sat Oct 07 16:52:57 2006 +0000
@@ -52,33 +52,38 @@
 #define OFFSET_MAX \
   ((((OFFSET)1 << (sizeof (OFFSET_MAX) * CHAR_BIT - 2)) - 1) * 2 + 1)
 
-/* Vectors being compared. */
-static const ELEMENT *xvec, *yvec;
+/*
+ * Context of comparison operation.
+ */
+struct context
+{
+  /* Vectors being compared. */
+  const ELEMENT *xvec;
+  const ELEMENT *yvec;
 
-/* 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. */
-static 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. */
-static OFFSET *bdiag;
+  /* 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. */
+  OFFSET *fdiag;
 
-#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.  This is unlikely in typical uses of
-   fstrcmp, and so is usually compiled out.  Besides, there is no
-   interface to set it true.  */
-int heuristic;
-#endif
+  /* Vector, indexed by diagonal, containing the X coordinate of the point
+     furthest along the given diagonal in the backward search of the edit
+     matrix. */
+  OFFSET *bdiag;
 
-/* Edit scripts longer than this are too expensive to compute.  */
-static OFFSET too_expensive;
+  #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;
+  #endif
 
-/* Snakes bigger than this are considered `big'.  */
-#define SNAKE_LIMIT 20
+  /* Edit scripts longer than this are too expensive to compute.  */
+  OFFSET too_expensive;
+
+  /* Snakes bigger than this are considered `big'.  */
+  #define SNAKE_LIMIT 20
+};
 
 struct partition
 {
@@ -119,12 +124,12 @@
 
 static void
 diag (OFFSET xoff, OFFSET xlim, OFFSET yoff, OFFSET ylim, bool find_minimal,
-      struct partition *part)
+      struct partition *part, struct context *ctxt)
 {
-  OFFSET *const fd = fdiag;	/* Give the compiler a chance. */
-  OFFSET *const bd = bdiag;	/* Additional help for the compiler. */
-  const ELEMENT *const xv = xvec;	/* Still more help for the compiler. */
-  const ELEMENT *const yv = yvec;	/* And more and more . . . */
+  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 . . . */
   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. */
@@ -227,7 +232,7 @@
 	 With this heuristic, for vectors with a constant small density
 	 of changes, the algorithm is linear in the vector size.  */
 
-      if (c > 200 && big_snake && heuristic)
+      if (c > 200 && big_snake && ctxt->heuristic)
 	{
 	  OFFSET best = 0;
 
@@ -304,7 +309,7 @@
 
       /* Heuristic: if we've gone well beyond the call of duty,
 	 give up and report halfway between our best results so far.  */
-      if (c >= too_expensive)
+      if (c >= ctxt->too_expensive)
 	{
 	  OFFSET fxybest;
 	  OFFSET bxybest;
@@ -376,10 +381,11 @@
    expensive it is.  */
 
 static void
-compareseq (OFFSET xoff, OFFSET xlim, OFFSET yoff, OFFSET ylim, bool find_minimal)
+compareseq (OFFSET xoff, OFFSET xlim, OFFSET yoff, OFFSET ylim,
+	    bool find_minimal, struct context *ctxt)
 {
-  const ELEMENT *xv = xvec; /* Help the compiler.  */
-  const ELEMENT *yv = yvec;
+  const ELEMENT *xv = ctxt->xvec; /* Help the compiler.  */
+  const ELEMENT *yv = ctxt->yvec;
 
   /* Slide down the bottom initial diagonal. */
   while (xoff < xlim && yoff < ylim && xv[xoff] == yv[yoff])
@@ -406,11 +412,11 @@
       struct partition part IF_LINT (= {0});
 
       /* Find a point of correspondence in the middle of the vectors.  */
-      diag (xoff, xlim, yoff, ylim, find_minimal, &part);
+      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);
-      compareseq (part.xmid, xlim, part.ymid, ylim, part.hi_minimal);
+      compareseq (xoff, part.xmid, yoff, part.ymid, part.lo_minimal, ctxt);
+      compareseq (part.xmid, xlim, part.ymid, ylim, part.hi_minimal, ctxt);
     }
 }