![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to diffh.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [MW Coherent from dump] / coherent / d / bin / diff|
Return to diffh.c CVS log | Up to [MW Coherent from dump] / coherent / d / bin / diff |
1.1 root 1: /*
2: * Half-hearted version of diff (doesn't
3: * use the complicated algorithm).
4: * This algorithm works on arbitrary files
5: * but is only intended where changes are
6: * minimal and well-spaced. There is another
7: * algorithm which also takes space but is at
8: * least guaranteed to be linear in time and space (unlike
9: * Least Common Subsequence) and sometimes produces
10: * more realistic results (and sometimes it doesn't)
11: * Consult: "A Technique for Isolating Diffeences between
12: * Files", Paul Heckel, CACM, November 1978.
13: * This shares code with the normal
14: * diff though.
15: */
16:
17: #include "diff.h"
18:
19: #define NPEND 200 /* Default # pending lines */
20: #define NMATCH 2 /* Minimum lines in a row to have a match */
21:
22: /*
23: * Structure for each line
24: * This is referenced by the
25: * structure for each file
26: * below.
27: */
28: typedef struct LINE {
29: unsigned l_num; /* Line number */
30: struct LINE *l_next; /* Pointer for ungetting lines */
31: char l_text[]; /* Data of line */
32: } LINE;
33:
34: /*
35: * Structure of pending lines
36: * and ungot lines stored for
37: * each of the input files.
38: */
39: typedef struct PENDING {
40: FILE *p_fp; /* I/O stream for input */
41: int p_eof; /* Reached EOF on this input */
42: char *p_fn; /* File name */
43: LINE *p_master; /* Master input buffer */
44: LINE *p_work; /* Current working line */
45: LINE *p_ungot; /* Ungot lines */
46: LINE *p_lines[NPEND]; /* Pending lines */
47: } PENDING;
48:
49: PENDING p1, p2;
50:
51: LINE *lcopy();
52:
53: /*
54: * A NOP routine so that diff()
55: * gets invoked.
56: */
57: /* ARGSUSED */
58: diffh(args)
59: char **args;
60: {
61: }
62:
63: /*
64: * The actual code to produce list
65: * of differences by a stupider
66: * (but cheaper) algorithm.
67: */
68: diff(fp1, fp2)
69: FILE *fp1;
70: FILE *fp2;
71: {
72: register int top, bot;
73: register int i;
74:
75: p1.p_master = p1.p_work = (LINE *)alloc(sizeof(LINE) + LSIZE);
76: p2.p_master = p2.p_work = (LINE *)alloc(sizeof(LINE) + LSIZE);
77: p1.p_fp = fp1;
78: p2.p_fp = fp2;
79: p1.p_fn = fn1;
80: p2.p_fn = fn2;
81: while (lget(&p1) | lget(&p2)) {
82: register char *s1, *s2;
83:
84: s1 = p1.p_work->l_text;
85: s2 = p2.p_work->l_text;
86: if (*s1=='\0' && *s2=='\0')
87: continue;
88: if ((*equal)(s1, s2)) {
89: text(s1);
90: continue;
91: }
92: top = 0;
93: lpend(&p1, top);
94: lpend(&p2, top++);
95: do {
96: if (top >= NPEND)
97: cerr("Out of memory, lines %d and %d",
98: p1.p_lines[0]->l_num, p2.p_lines[0]->l_num);
99: /*
100: * Not checked, lget has
101: * to stop going over EOF
102: * by itself.
103: */
104: lget(&p1);
105: lget(&p2);
106: lpend(&p1, top);
107: lpend(&p2, top++);
108: bot = top-NMATCH;
109: for (i=0; i<bot; i++) {
110: if (lsearch(i, bot)) {
111: lunget(&p1, i+NMATCH, top);
112: break;
113: }
114: if (lsearch(bot, i)) {
115: lunget(&p2, i+NMATCH, top);
116: break;
117: }
118: }
119: } while (i>bot || i==bot && !lsearch(i, i));
120: }
121: }
122:
123: /*
124: * Get a line and put it into the current
125: * working position.
126: * Return 0 at EOF.
127: */
128: lget(pp)
129: register PENDING *pp;
130: {
131: if (pp->p_master != pp->p_work)
132: free(pp->p_work);
133: if (pp->p_ungot != NULL) {
134: pp->p_work = pp->p_ungot;
135: pp->p_ungot = pp->p_ungot->l_next;
136: return (1);
137: }
138: pp->p_work = pp->p_master;
139: return (lgets(pp));
140: }
141:
142: /*
143: * Unget pending lines between
144: * `beg' and `end' that are
145: * not already dealt with.
146: */
147: lunget(pp, beg, end)
148: register PENDING *pp;
149: register int beg, end;
150: {
151: while (--end >= beg) {
152: pp->p_lines[end]->l_next = pp->p_ungot;
153: pp->p_ungot = pp->p_lines[end];
154: pp->p_lines[end] = NULL;
155: }
156: }
157:
158: /*
159: * Copy a line to a new (allocated)
160: * line space.
161: */
162: LINE *
163: lcopy(lp)
164: register LINE *lp;
165: {
166: register LINE *rlp;
167: register char *cp;
168:
169: for (cp = lp->l_text; *cp != '\0'; cp++)
170: ;
171: rlp = (LINE *)alloc(cp-lp->l_text+1 + sizeof(LINE));
172: rlp->l_num = lp->l_num;
173: rlp->l_next = NULL;
174: strcpy(rlp->l_text, lp->l_text);
175: return (rlp);
176: }
177:
178: /*
179: * Save line away in a pending line
180: * position, specified by `pos'.
181: */
182: lpend(pp, pos)
183: register PENDING *pp;
184: register int pos;
185: {
186: if (pp->p_lines[pos] != NULL)
187: free(pp->p_lines[pos]);
188: if (pp->p_master != pp->p_work) {
189: pp->p_lines[pos] = pp->p_work;
190: pp->p_work = pp->p_master;
191: } else
192: pp->p_lines[pos] = lcopy(pp->p_work);
193: }
194:
195: /*
196: * Read a string from input (specified
197: * by the PENDING pointer) and throw away
198: * partial lines.
199: */
200: lgets(pp)
201: register PENDING *pp;
202: {
203: register int c;
204: register char *s;
205: register unsigned lim = LSIZE;
206:
207: s = pp->p_master->l_text;
208: if (pp->p_eof) {
209: *s = '\0';
210: return (0);
211: }
212: while (--lim > 0 && (c = getc(pp->p_fp)) != EOF)
213: if ((*s++ = c) == '\n')
214: break;
215: *s = '\0';
216: if (c == EOF) {
217: if (s != pp->p_master->l_text)
218: fprintf(stderr, "diff: partial line omitted from %s\n",
219: pp->p_fn);
220: pp->p_eof++;
221: return (0);
222: }
223: pp->p_master->l_num++;
224: return (1);
225: }
226:
227: /*
228: * Search for a match in the pending lines.
229: * The two parameters are `pos1' and `pos2'
230: * for the position to start searching in
231: * file1 and file2, respectively. The
232: * search looks for at least NMATCH lines.
233: */
234: lsearch(pos1, pos2)
235: int pos1;
236: int pos2;
237: {
238: register LINE **lpp1, **lpp2;
239: register int i;
240: register char *s1, *s2;
241: register int ln11, ln12, ln21, ln22;
242:
243: lpp1 = &p1.p_lines[pos1];
244: lpp2 = &p2.p_lines[pos2];
245: /*
246: * Empty strings are actually
247: * dummies for after EOF.
248: */
249: for (i=0; i<NMATCH; i++) {
250: s1 = lpp1[i]->l_text;
251: s2 = lpp2[i]->l_text;
252: if (*s1!='\0' || *s2!='\0')
253: if (!(*equal)(s1, s2))
254: break;
255: }
256: if (i < NMATCH)
257: return (0);
258: lpp1 = p1.p_lines;
259: lpp2 = p2.p_lines;
260: ln11 = lpp1[0]->l_num;
261: ln12 = lpp1[pos1-1]->l_num;
262: ln21 = lpp2[0]->l_num;
263: ln22 = lpp2[pos2-1]->l_num;
264: if (pos1 == 0)
265: append(ln11, ln21, ln22);
266: else if (pos2 == 0)
267: delete(ln11, ln12, ln21);
268: else
269: change(ln11, ln12, ln21, ln22);
270: for (i = 0; i < pos1; i++)
271: text1(lpp1[i]->l_text);
272: prsep();
273: for (i = 0; i < pos2; i++)
274: text2(lpp2[i]->l_text);
275: prend();
276: for (i=0; i<NMATCH; i++)
277: if (*(s1 = lpp1[i+pos1]->l_text) != '\0')
278: text(s1);
279: return (1);
280: }
281:
282: /*
283: * Allocator that also checks for
284: * an prints a message if out of space.
285: */
286: char *
287: alloc(nb)
288: unsigned nb;
289: {
290: register char *rp;
291:
292: if ((rp = calloc(nb, 1)) == NULL)
293: cerr("out of memory");
294: return (rp);
295: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.