changeset 7434:2ee32ecdec9d

Make the heuristic dependent on USE_HEURISTIC and the variable 'heuristic'.
author Bruno Haible <bruno@clisp.org>
date Sat, 07 Oct 2006 16:40:41 +0000
parents 4266f326be34
children 483a70ceec47
files lib/analyze.c lib/diffseq.h lib/fstrcmp.c
diffstat 3 files changed, 29 insertions(+), 15 deletions(-) [+]
line wrap: on
line diff
--- a/lib/analyze.c
+++ b/lib/analyze.c
@@ -30,6 +30,7 @@
 #define ELEMENT lin
 #define EQUAL(x,y) ((x) == (y))
 #define OFFSET lin
+#define USE_HEURISTIC 1
 #include "diffseq.h"
 
 /* Discard lines from one file that have no matches in the other file.
@@ -562,6 +563,8 @@
       fdiag += cmp->file[1].nondiscarded_lines + 1;
       bdiag += cmp->file[1].nondiscarded_lines + 1;
 
+      heuristic = speed_large_files;
+
       /* Set TOO_EXPENSIVE to be approximate square root of input size,
 	 bounded below by 256.  */
       too_expensive = 1;
--- a/lib/diffseq.h
+++ b/lib/diffseq.h
@@ -44,7 +44,9 @@
                              equality.
      OFFSET                  A signed integer type sufficient to hold the
                              difference between two indices. Usually
-                             something like ssize_t.  */
+                             something like ssize_t.
+     USE_HEURISTIC           (Optional) Define if you want to support the
+                             heuristic for large vectors.  */
 
 /* Maximum value of type OFFSET.  */
 #define OFFSET_MAX \
@@ -63,6 +65,15 @@
    matrix. */
 static 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.  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
+
 /* Edit scripts longer than this are too expensive to compute.  */
 static OFFSET too_expensive;
 
@@ -207,6 +218,7 @@
       if (find_minimal)
 	continue;
 
+#ifdef USE_HEURISTIC
       /* Heuristic: check occasionally for a diagonal that has made
 	 lots of progress compared with the edit distance.
 	 If we have any such, find the one that has made the most
@@ -215,7 +227,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 && speed_large_files)
+      if (c > 200 && big_snake && heuristic)
 	{
 	  OFFSET best = 0;
 
@@ -288,6 +300,7 @@
 	      return;
 	    }
 	}
+#endif /* USE_HEURISTIC */
 
       /* Heuristic: if we've gone well beyond the call of duty,
 	 give up and report halfway between our best results so far.  */
--- a/lib/fstrcmp.c
+++ b/lib/fstrcmp.c
@@ -97,17 +97,6 @@
   }
   string[2];
 
-  #ifdef MINUS_H_FLAG
-
-  /* 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 1 + the X coordinate of the
      point furthest along the given diagonal in the forward search of the
      edit matrix.  */
@@ -118,6 +107,15 @@
      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.  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
+
   /* Edit scripts longer than this are too expensive to compute.  */
   OFFSET too_expensive;
 
@@ -301,7 +299,7 @@
       if (find_minimal)
 	continue;
 
-#ifdef MINUS_H_FLAG
+#ifdef USE_HEURISTIC
       /* Heuristic: check occasionally for a diagonal that has made lots
          of progress compared with the edit distance.  If we have any
          such, find the one that has made the most progress and return
@@ -398,7 +396,7 @@
 	      return 2 * c - 1;
 	    }
 	}
-#endif /* MINUS_H_FLAG */
+#endif /* USE_HEURISTIC */
 
       /* Heuristic: if we've gone well beyond the call of duty, give up
 	 and report halfway between our best results so far.  */