Mercurial > hg > octave-lojdl > gnulib-hg
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. */