diff options
| -rw-r--r-- | usr.bin/diff/diff.1 | 19 | ||||
| -rw-r--r-- | usr.bin/diff/diff.c | 24 | ||||
| -rw-r--r-- | usr.bin/diff/diff.h | 4 | ||||
| -rw-r--r-- | usr.bin/diff/diffreg.c | 47 |
4 files changed, 68 insertions, 26 deletions
diff --git a/usr.bin/diff/diff.1 b/usr.bin/diff/diff.1 index b88f170e43b..877c19c468a 100644 --- a/usr.bin/diff/diff.1 +++ b/usr.bin/diff/diff.1 @@ -1,4 +1,4 @@ -.\" $OpenBSD: diff.1,v 1.18 2003/07/22 01:23:51 millert Exp $ +.\" $OpenBSD: diff.1,v 1.19 2003/07/27 07:39:52 otto Exp $ .\" .\" Copyright (c) 1980, 1990, 1993 .\" The Regents of the University of California. All rights reserved. @@ -37,7 +37,7 @@ .Nd differential file and directory comparator .Sh SYNOPSIS .Nm diff -.Op Fl abilqtTw +.Op Fl abdilqtTw .Oo .Fl c | Fl e | Fl f | .Fl n | Fl u @@ -45,21 +45,21 @@ .Op Fl L Ar label .Ar file1 file2 .Nm diff -.Op Fl abilqtTw +.Op Fl abdilqtTw .Op Fl L Ar label .Fl C Ar number .Ar file1 file2 .Nm diff -.Op Fl abilqtw +.Op Fl abdilqtw .Fl D Ar string .Ar file1 file2 .Nm diff -.Op Fl abilqtTw +.Op Fl abdilqtTw .Op Fl L Ar label .Fl U Ar number .Ar file1 file2 .Nm diff -.Op Fl abilNqtTw +.Op Fl abdilNqtTw .Oo .Fl c | Fl e | Fl f | .Fl n | Fl u @@ -105,7 +105,12 @@ are marked Lines which are changed from one file to the other are marked in both files with .Sq !\ \& . -Changes which lie within 3 lines of each other are grouped together on output. +Changes which lie within 3 lines of each other are grouped together on +output. +.It Fl d +Try very hard to produce a diff as small as possible. This may consume a +lot of processing power and memory when processing large files with +many changes. .It Fl e Produces output in a form suitable as input for the editor utility, .Xr ed 1 , diff --git a/usr.bin/diff/diff.c b/usr.bin/diff/diff.c index b671ec3892e..56b11e3da95 100644 --- a/usr.bin/diff/diff.c +++ b/usr.bin/diff/diff.c @@ -1,4 +1,4 @@ -/* $OpenBSD: diff.c,v 1.34 2003/07/22 16:42:58 millert Exp $ */ +/* $OpenBSD: diff.c,v 1.35 2003/07/27 07:39:52 otto Exp $ */ /* * Copyright (c) 2003 Todd C. Miller <Todd.Miller@courtesan.com> @@ -21,7 +21,7 @@ */ #ifndef lint -static const char rcsid[] = "$OpenBSD: diff.c,v 1.34 2003/07/22 16:42:58 millert Exp $"; +static const char rcsid[] = "$OpenBSD: diff.c,v 1.35 2003/07/27 07:39:52 otto Exp $"; #endif /* not lint */ #include <sys/param.h> @@ -39,19 +39,20 @@ static const char rcsid[] = "$OpenBSD: diff.c,v 1.34 2003/07/22 16:42:58 millert #include "diff.h" -int aflag, bflag, iflag, lflag, Nflag, Pflag, rflag, sflag, tflag, Tflag, - wflag; +int aflag, bflag, dflag, iflag, lflag, Nflag, Pflag, rflag, sflag, tflag, + Tflag, wflag; int format, context, status; char *start, *ifdefname, *diffargs, *label; struct stat stb1, stb2; struct excludes *excludes_list; -#define OPTIONS "abC:cD:efhiL:lnNPqrS:sTtU:uwX:x:" +#define OPTIONS "abC:cdD:efhiL:lnNPqrS:sTtU:uwX:x:" static struct option longopts[] = { { "text", no_argument, 0, 'a' }, { "ignore-space-change", no_argument, 0, 'b' }, { "context", optional_argument, 0, 'C' }, { "ifdef", required_argument, 0, 'D' }, + { "minimal", no_argument, 0, 'd' }, { "ed", no_argument, 0, 'e' }, { "forward-ed", no_argument, 0, 'f' }, { "ignore-case", no_argument, 0, 'i' }, @@ -107,6 +108,9 @@ main(int argc, char **argv) } else context = 3; break; + case 'd': + dflag = 1; + break; case 'D': format = D_IFDEF; ifdefname = optarg; @@ -361,11 +365,11 @@ __dead void usage(void) { (void)fprintf(stderr, - "usage: diff [-bilqtTw] [-c | -e | -f | -n | -u] [-L label] file1 file2\n" - " diff [-bilqtTw] [-L label] -C number file1 file2\n" - " diff [-bilqtw] -D string file1 file2\n" - " diff [-bilqtTw] [-L label] -U number file1 file2\n" - " diff [-bilNPqwtT] [-c | -e | -f | -n | -u ] [-L label] [-r] [-s] [-S name]\n" + "usage: diff [-bdilqtTw] [-c | -e | -f | -n | -u] [-L label] file1 file2\n" + " diff [-bdilqtTw] [-L label] -C number file1 file2\n" + " diff [-bdilqtw] -D string file1 file2\n" + " diff [-bdilqtTw] [-L label] -U number file1 file2\n" + " diff [-bdilNPqwtT] [-c | -e | -f | -n | -u ] [-L label] [-r] [-s] [-S name]\n" " [-X file] [-x pattern] dir1 dir2\n"); exit(2); diff --git a/usr.bin/diff/diff.h b/usr.bin/diff/diff.h index 4ac9d45c62e..fd60b13da2d 100644 --- a/usr.bin/diff/diff.h +++ b/usr.bin/diff/diff.h @@ -1,4 +1,4 @@ -/* $OpenBSD: diff.h,v 1.21 2003/07/22 01:16:01 millert Exp $ */ +/* $OpenBSD: diff.h,v 1.22 2003/07/27 07:39:52 otto Exp $ */ /*- * Copyright (c) 1991, 1993 @@ -68,7 +68,7 @@ struct excludes { struct excludes *next; }; -extern int aflag, bflag, iflag, lflag, Nflag, Pflag, rflag, sflag, +extern int aflag, bflag, dflag, iflag, lflag, Nflag, Pflag, rflag, sflag, tflag, Tflag, wflag; extern int format, context, status, anychange; extern char *start, *ifdefname, *diffargs, *label; diff --git a/usr.bin/diff/diffreg.c b/usr.bin/diff/diffreg.c index 2d71a665583..85f4e45fcdd 100644 --- a/usr.bin/diff/diffreg.c +++ b/usr.bin/diff/diffreg.c @@ -1,4 +1,4 @@ -/* $OpenBSD: diffreg.c,v 1.42 2003/07/23 22:01:36 tedu Exp $ */ +/* $OpenBSD: diffreg.c,v 1.43 2003/07/27 07:39:52 otto Exp $ */ /* * Copyright (C) Caldera International Inc. 2001-2002. @@ -65,7 +65,7 @@ */ #ifndef lint -static const char rcsid[] = "$OpenBSD: diffreg.c,v 1.42 2003/07/23 22:01:36 tedu Exp $"; +static const char rcsid[] = "$OpenBSD: diffreg.c,v 1.43 2003/07/27 07:39:52 otto Exp $"; #endif /* not lint */ #include <sys/param.h> @@ -188,6 +188,7 @@ static int anychange; static long *ixnew; /* will be overlaid on file[1] */ static long *ixold; /* will be overlaid on klist */ static struct cand *clist; /* merely a free storage pot for candidates */ +static int clistlen; /* the length of clist */ static struct line *sfile[2]; /* shortened by pruning common prefix/suffix */ static u_char *chrtran; /* translation table for case-folding */ static struct context_vec *context_vec_start; @@ -213,9 +214,13 @@ static int fetch(long *, int, int, FILE *, int, int); static int newcand(int, int, int); static int search(int *, int, int); static int skipline(FILE *); +static int isqrt(int); static int stone(int *, int, int *, int *); static int readhash(FILE *); static int files_differ(FILE *, FILE *, int); +static __inline int min(int, int); +static __inline int max(int, int); + /* * chrtran points to one of 2 translation tables: cup2low if folding upper to @@ -413,7 +418,8 @@ notsame: class = erealloc(class, (slen[0] + 2) * sizeof(int)); klist = emalloc((slen[0] + 2) * sizeof(int)); - clist = emalloc(sizeof(cand)); + clistlen = 100; + clist = emalloc(clistlen * sizeof(cand)); i = stone(class, slen[0], member, klist); free(member); free(class); @@ -594,11 +600,33 @@ equiv(struct line *a, int n, struct line *b, int m, int *c) c[j] = -1; } +/* Code taken from ping.c */ +static int +isqrt(int n) +{ + int y, x = 1; + + if (n == 0) + return(0); + + do { /* newton was a stinker */ + y = x; + x = n / x; + x += y; + x /= 2; + } while ((x - y) > 1 || (x - y) < -1); + + return (x); +} + static int stone(int *a, int n, int *b, int *c) { int i, k, y, j, l; int oldc, tc, oldl; + u_int loopcount; + + const u_int bound = dflag ? UINT_MAX : max(256, isqrt(n)); k = 0; c[0] = newcand(0, 0, 0); @@ -609,7 +637,9 @@ stone(int *a, int n, int *b, int *c) y = -b[j]; oldl = 0; oldc = c[0]; + loopcount = 0; do { + loopcount++; if (y <= clist[oldc].y) continue; l = search(c, k, y); @@ -627,7 +657,7 @@ stone(int *a, int n, int *b, int *c) k++; break; } - } while ((y = b[++j]) > 0); + } while ((y = b[++j]) > 0 && loopcount < bound); } return (k); } @@ -637,12 +667,15 @@ newcand(int x, int y, int pred) { struct cand *q; - clist = erealloc(clist, ++clen * sizeof(cand)); - q = clist + clen - 1; + if (clen == clistlen) { + clistlen = clistlen * 11 / 10; + clist = erealloc(clist, clistlen * sizeof(cand)); + } + q = clist + clen; q->x = x; q->y = y; q->pred = pred; - return (clen - 1); + return (clen++); } static int |