From 14d4ab70a33d06b495ae41bcc8f5d5e8330092f3 Mon Sep 17 00:00:00 2001 From: Bruno Haible Date: Sat, 7 Oct 2006 16:40:41 +0000 Subject: [PATCH] Make the heuristic dependent on USE_HEURISTIC and the variable 'heuristic'. --- lib/analyze.c | 3 +++ lib/diffseq.h | 17 +++++++++++++++-- lib/fstrcmp.c | 24 +++++++++++------------- 3 files changed, 29 insertions(+), 15 deletions(-) diff --git a/lib/analyze.c b/lib/analyze.c index 9a3187ca9e..8ed863da41 100644 --- 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 @@ diff_2_files (struct comparison *cmp) 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; diff --git a/lib/diffseq.h b/lib/diffseq.h index 6a348ea893..1c5a5c280e 100644 --- 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 @@ static OFFSET *fdiag; 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 @@ diag (OFFSET xoff, OFFSET xlim, OFFSET yoff, OFFSET ylim, bool find_minimal, 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 @@ diag (OFFSET xoff, OFFSET xlim, OFFSET yoff, OFFSET ylim, bool find_minimal, 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 @@ diag (OFFSET xoff, OFFSET xlim, OFFSET yoff, OFFSET ylim, bool find_minimal, 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. */ diff --git a/lib/fstrcmp.c b/lib/fstrcmp.c index e9b4d0ee20..2ba6cf4aad 100644 --- a/lib/fstrcmp.c +++ b/lib/fstrcmp.c @@ -97,17 +97,6 @@ struct context } 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 @@ struct context 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 @@ diag (OFFSET xoff, OFFSET xlim, OFFSET yoff, OFFSET ylim, bool find_minimal, 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 @@ diag (OFFSET xoff, OFFSET xlim, OFFSET yoff, OFFSET ylim, bool find_minimal, 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. */ -- 2.39.5