git

1
/*
2
 *  LibXDiff by Davide Libenzi ( File Differential Library )
3
 *  Copyright (C) 2003  Davide Libenzi
4
 *
5
 *  This library is free software; you can redistribute it and/or
6
 *  modify it under the terms of the GNU Lesser General Public
7
 *  License as published by the Free Software Foundation; either
8
 *  version 2.1 of the License, or (at your option) any later version.
9
 *
10
 *  This library is distributed in the hope that it will be useful,
11
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
12
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13
 *  Lesser General Public License for more details.
14
 *
15
 *  You should have received a copy of the GNU Lesser General Public
16
 *  License along with this library; if not, see
17
 *  <http://www.gnu.org/licenses/>.
18
 *
19
 *  Davide Libenzi <davidel@xmailserver.org>
20
 *
21
 */
22

23
#include "xinclude.h"
24

25

26
#define XDL_KPDIS_RUN 4
27
#define XDL_MAX_EQLIMIT 1024
28
#define XDL_SIMSCAN_WINDOW 100
29
#define XDL_GUESS_NLINES1 256
30
#define XDL_GUESS_NLINES2 20
31

32

33
typedef struct s_xdlclass {
34
	struct s_xdlclass *next;
35
	unsigned long ha;
36
	char const *line;
37
	long size;
38
	long idx;
39
	long len1, len2;
40
} xdlclass_t;
41

42
typedef struct s_xdlclassifier {
43
	unsigned int hbits;
44
	long hsize;
45
	xdlclass_t **rchash;
46
	chastore_t ncha;
47
	xdlclass_t **rcrecs;
48
	long alloc;
49
	long count;
50
	long flags;
51
} xdlclassifier_t;
52

53

54

55

56
static int xdl_init_classifier(xdlclassifier_t *cf, long size, long flags);
57
static void xdl_free_classifier(xdlclassifier_t *cf);
58
static int xdl_classify_record(unsigned int pass, xdlclassifier_t *cf, xrecord_t **rhash,
59
			       unsigned int hbits, xrecord_t *rec);
60
static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_t const *xpp,
61
			   xdlclassifier_t *cf, xdfile_t *xdf);
62
static void xdl_free_ctx(xdfile_t *xdf);
63
static int xdl_clean_mmatch(char const *dis, long i, long s, long e);
64
static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2);
65
static int xdl_trim_ends(xdfile_t *xdf1, xdfile_t *xdf2);
66
static int xdl_optimize_ctxs(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2);
67

68

69

70

71
static int xdl_init_classifier(xdlclassifier_t *cf, long size, long flags) {
72
	cf->flags = flags;
73

74
	cf->hbits = xdl_hashbits((unsigned int) size);
75
	cf->hsize = 1 << cf->hbits;
76

77
	if (xdl_cha_init(&cf->ncha, sizeof(xdlclass_t), size / 4 + 1) < 0) {
78

79
		return -1;
80
	}
81
	if (!XDL_CALLOC_ARRAY(cf->rchash, cf->hsize)) {
82

83
		xdl_cha_free(&cf->ncha);
84
		return -1;
85
	}
86

87
	cf->alloc = size;
88
	if (!XDL_ALLOC_ARRAY(cf->rcrecs, cf->alloc)) {
89

90
		xdl_free(cf->rchash);
91
		xdl_cha_free(&cf->ncha);
92
		return -1;
93
	}
94

95
	cf->count = 0;
96

97
	return 0;
98
}
99

100

101
static void xdl_free_classifier(xdlclassifier_t *cf) {
102

103
	xdl_free(cf->rcrecs);
104
	xdl_free(cf->rchash);
105
	xdl_cha_free(&cf->ncha);
106
}
107

108

109
static int xdl_classify_record(unsigned int pass, xdlclassifier_t *cf, xrecord_t **rhash,
110
			       unsigned int hbits, xrecord_t *rec) {
111
	long hi;
112
	char const *line;
113
	xdlclass_t *rcrec;
114

115
	line = rec->ptr;
116
	hi = (long) XDL_HASHLONG(rec->ha, cf->hbits);
117
	for (rcrec = cf->rchash[hi]; rcrec; rcrec = rcrec->next)
118
		if (rcrec->ha == rec->ha &&
119
				xdl_recmatch(rcrec->line, rcrec->size,
120
					rec->ptr, rec->size, cf->flags))
121
			break;
122

123
	if (!rcrec) {
124
		if (!(rcrec = xdl_cha_alloc(&cf->ncha))) {
125

126
			return -1;
127
		}
128
		rcrec->idx = cf->count++;
129
		if (XDL_ALLOC_GROW(cf->rcrecs, cf->count, cf->alloc))
130
				return -1;
131
		cf->rcrecs[rcrec->idx] = rcrec;
132
		rcrec->line = line;
133
		rcrec->size = rec->size;
134
		rcrec->ha = rec->ha;
135
		rcrec->len1 = rcrec->len2 = 0;
136
		rcrec->next = cf->rchash[hi];
137
		cf->rchash[hi] = rcrec;
138
	}
139

140
	(pass == 1) ? rcrec->len1++ : rcrec->len2++;
141

142
	rec->ha = (unsigned long) rcrec->idx;
143

144
	hi = (long) XDL_HASHLONG(rec->ha, hbits);
145
	rec->next = rhash[hi];
146
	rhash[hi] = rec;
147

148
	return 0;
149
}
150

151

152
static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_t const *xpp,
153
			   xdlclassifier_t *cf, xdfile_t *xdf) {
154
	unsigned int hbits;
155
	long nrec, hsize, bsize;
156
	unsigned long hav;
157
	char const *blk, *cur, *top, *prev;
158
	xrecord_t *crec;
159
	xrecord_t **recs;
160
	xrecord_t **rhash;
161
	unsigned long *ha;
162
	char *rchg;
163
	long *rindex;
164

165
	ha = NULL;
166
	rindex = NULL;
167
	rchg = NULL;
168
	rhash = NULL;
169
	recs = NULL;
170

171
	if (xdl_cha_init(&xdf->rcha, sizeof(xrecord_t), narec / 4 + 1) < 0)
172
		goto abort;
173
	if (!XDL_ALLOC_ARRAY(recs, narec))
174
		goto abort;
175

176
	hbits = xdl_hashbits((unsigned int) narec);
177
	hsize = 1 << hbits;
178
	if (!XDL_CALLOC_ARRAY(rhash, hsize))
179
		goto abort;
180

181
	nrec = 0;
182
	if ((cur = blk = xdl_mmfile_first(mf, &bsize))) {
183
		for (top = blk + bsize; cur < top; ) {
184
			prev = cur;
185
			hav = xdl_hash_record(&cur, top, xpp->flags);
186
			if (XDL_ALLOC_GROW(recs, nrec + 1, narec))
187
				goto abort;
188
			if (!(crec = xdl_cha_alloc(&xdf->rcha)))
189
				goto abort;
190
			crec->ptr = prev;
191
			crec->size = (long) (cur - prev);
192
			crec->ha = hav;
193
			recs[nrec++] = crec;
194
			if (xdl_classify_record(pass, cf, rhash, hbits, crec) < 0)
195
				goto abort;
196
		}
197
	}
198

199
	if (!XDL_CALLOC_ARRAY(rchg, nrec + 2))
200
		goto abort;
201

202
	if ((XDF_DIFF_ALG(xpp->flags) != XDF_PATIENCE_DIFF) &&
203
	    (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF)) {
204
		if (!XDL_ALLOC_ARRAY(rindex, nrec + 1))
205
			goto abort;
206
		if (!XDL_ALLOC_ARRAY(ha, nrec + 1))
207
			goto abort;
208
	}
209

210
	xdf->nrec = nrec;
211
	xdf->recs = recs;
212
	xdf->hbits = hbits;
213
	xdf->rhash = rhash;
214
	xdf->rchg = rchg + 1;
215
	xdf->rindex = rindex;
216
	xdf->nreff = 0;
217
	xdf->ha = ha;
218
	xdf->dstart = 0;
219
	xdf->dend = nrec - 1;
220

221
	return 0;
222

223
abort:
224
	xdl_free(ha);
225
	xdl_free(rindex);
226
	xdl_free(rchg);
227
	xdl_free(rhash);
228
	xdl_free(recs);
229
	xdl_cha_free(&xdf->rcha);
230
	return -1;
231
}
232

233

234
static void xdl_free_ctx(xdfile_t *xdf) {
235

236
	xdl_free(xdf->rhash);
237
	xdl_free(xdf->rindex);
238
	xdl_free(xdf->rchg - 1);
239
	xdl_free(xdf->ha);
240
	xdl_free(xdf->recs);
241
	xdl_cha_free(&xdf->rcha);
242
}
243

244

245
int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
246
		    xdfenv_t *xe) {
247
	long enl1, enl2, sample;
248
	xdlclassifier_t cf;
249

250
	memset(&cf, 0, sizeof(cf));
251

252
	/*
253
	 * For histogram diff, we can afford a smaller sample size and
254
	 * thus a poorer estimate of the number of lines, as the hash
255
	 * table (rhash) won't be filled up/grown. The number of lines
256
	 * (nrecs) will be updated correctly anyway by
257
	 * xdl_prepare_ctx().
258
	 */
259
	sample = (XDF_DIFF_ALG(xpp->flags) == XDF_HISTOGRAM_DIFF
260
		  ? XDL_GUESS_NLINES2 : XDL_GUESS_NLINES1);
261

262
	enl1 = xdl_guess_lines(mf1, sample) + 1;
263
	enl2 = xdl_guess_lines(mf2, sample) + 1;
264

265
	if (xdl_init_classifier(&cf, enl1 + enl2 + 1, xpp->flags) < 0)
266
		return -1;
267

268
	if (xdl_prepare_ctx(1, mf1, enl1, xpp, &cf, &xe->xdf1) < 0) {
269

270
		xdl_free_classifier(&cf);
271
		return -1;
272
	}
273
	if (xdl_prepare_ctx(2, mf2, enl2, xpp, &cf, &xe->xdf2) < 0) {
274

275
		xdl_free_ctx(&xe->xdf1);
276
		xdl_free_classifier(&cf);
277
		return -1;
278
	}
279

280
	if ((XDF_DIFF_ALG(xpp->flags) != XDF_PATIENCE_DIFF) &&
281
	    (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF) &&
282
	    xdl_optimize_ctxs(&cf, &xe->xdf1, &xe->xdf2) < 0) {
283

284
		xdl_free_ctx(&xe->xdf2);
285
		xdl_free_ctx(&xe->xdf1);
286
		xdl_free_classifier(&cf);
287
		return -1;
288
	}
289

290
	xdl_free_classifier(&cf);
291

292
	return 0;
293
}
294

295

296
void xdl_free_env(xdfenv_t *xe) {
297

298
	xdl_free_ctx(&xe->xdf2);
299
	xdl_free_ctx(&xe->xdf1);
300
}
301

302

303
static int xdl_clean_mmatch(char const *dis, long i, long s, long e) {
304
	long r, rdis0, rpdis0, rdis1, rpdis1;
305

306
	/*
307
	 * Limits the window the is examined during the similar-lines
308
	 * scan. The loops below stops when dis[i - r] == 1 (line that
309
	 * has no match), but there are corner cases where the loop
310
	 * proceed all the way to the extremities by causing huge
311
	 * performance penalties in case of big files.
312
	 */
313
	if (i - s > XDL_SIMSCAN_WINDOW)
314
		s = i - XDL_SIMSCAN_WINDOW;
315
	if (e - i > XDL_SIMSCAN_WINDOW)
316
		e = i + XDL_SIMSCAN_WINDOW;
317

318
	/*
319
	 * Scans the lines before 'i' to find a run of lines that either
320
	 * have no match (dis[j] == 0) or have multiple matches (dis[j] > 1).
321
	 * Note that we always call this function with dis[i] > 1, so the
322
	 * current line (i) is already a multimatch line.
323
	 */
324
	for (r = 1, rdis0 = 0, rpdis0 = 1; (i - r) >= s; r++) {
325
		if (!dis[i - r])
326
			rdis0++;
327
		else if (dis[i - r] == 2)
328
			rpdis0++;
329
		else
330
			break;
331
	}
332
	/*
333
	 * If the run before the line 'i' found only multimatch lines, we
334
	 * return 0 and hence we don't make the current line (i) discarded.
335
	 * We want to discard multimatch lines only when they appear in the
336
	 * middle of runs with nomatch lines (dis[j] == 0).
337
	 */
338
	if (rdis0 == 0)
339
		return 0;
340
	for (r = 1, rdis1 = 0, rpdis1 = 1; (i + r) <= e; r++) {
341
		if (!dis[i + r])
342
			rdis1++;
343
		else if (dis[i + r] == 2)
344
			rpdis1++;
345
		else
346
			break;
347
	}
348
	/*
349
	 * If the run after the line 'i' found only multimatch lines, we
350
	 * return 0 and hence we don't make the current line (i) discarded.
351
	 */
352
	if (rdis1 == 0)
353
		return 0;
354
	rdis1 += rdis0;
355
	rpdis1 += rpdis0;
356

357
	return rpdis1 * XDL_KPDIS_RUN < (rpdis1 + rdis1);
358
}
359

360

361
/*
362
 * Try to reduce the problem complexity, discard records that have no
363
 * matches on the other file. Also, lines that have multiple matches
364
 * might be potentially discarded if they happear in a run of discardable.
365
 */
366
static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2) {
367
	long i, nm, nreff, mlim;
368
	xrecord_t **recs;
369
	xdlclass_t *rcrec;
370
	char *dis, *dis1, *dis2;
371

372
	if (!XDL_CALLOC_ARRAY(dis, xdf1->nrec + xdf2->nrec + 2))
373
		return -1;
374
	dis1 = dis;
375
	dis2 = dis1 + xdf1->nrec + 1;
376

377
	if ((mlim = xdl_bogosqrt(xdf1->nrec)) > XDL_MAX_EQLIMIT)
378
		mlim = XDL_MAX_EQLIMIT;
379
	for (i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart]; i <= xdf1->dend; i++, recs++) {
380
		rcrec = cf->rcrecs[(*recs)->ha];
381
		nm = rcrec ? rcrec->len2 : 0;
382
		dis1[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1;
383
	}
384

385
	if ((mlim = xdl_bogosqrt(xdf2->nrec)) > XDL_MAX_EQLIMIT)
386
		mlim = XDL_MAX_EQLIMIT;
387
	for (i = xdf2->dstart, recs = &xdf2->recs[xdf2->dstart]; i <= xdf2->dend; i++, recs++) {
388
		rcrec = cf->rcrecs[(*recs)->ha];
389
		nm = rcrec ? rcrec->len1 : 0;
390
		dis2[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1;
391
	}
392

393
	for (nreff = 0, i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart];
394
	     i <= xdf1->dend; i++, recs++) {
395
		if (dis1[i] == 1 ||
396
		    (dis1[i] == 2 && !xdl_clean_mmatch(dis1, i, xdf1->dstart, xdf1->dend))) {
397
			xdf1->rindex[nreff] = i;
398
			xdf1->ha[nreff] = (*recs)->ha;
399
			nreff++;
400
		} else
401
			xdf1->rchg[i] = 1;
402
	}
403
	xdf1->nreff = nreff;
404

405
	for (nreff = 0, i = xdf2->dstart, recs = &xdf2->recs[xdf2->dstart];
406
	     i <= xdf2->dend; i++, recs++) {
407
		if (dis2[i] == 1 ||
408
		    (dis2[i] == 2 && !xdl_clean_mmatch(dis2, i, xdf2->dstart, xdf2->dend))) {
409
			xdf2->rindex[nreff] = i;
410
			xdf2->ha[nreff] = (*recs)->ha;
411
			nreff++;
412
		} else
413
			xdf2->rchg[i] = 1;
414
	}
415
	xdf2->nreff = nreff;
416

417
	xdl_free(dis);
418

419
	return 0;
420
}
421

422

423
/*
424
 * Early trim initial and terminal matching records.
425
 */
426
static int xdl_trim_ends(xdfile_t *xdf1, xdfile_t *xdf2) {
427
	long i, lim;
428
	xrecord_t **recs1, **recs2;
429

430
	recs1 = xdf1->recs;
431
	recs2 = xdf2->recs;
432
	for (i = 0, lim = XDL_MIN(xdf1->nrec, xdf2->nrec); i < lim;
433
	     i++, recs1++, recs2++)
434
		if ((*recs1)->ha != (*recs2)->ha)
435
			break;
436

437
	xdf1->dstart = xdf2->dstart = i;
438

439
	recs1 = xdf1->recs + xdf1->nrec - 1;
440
	recs2 = xdf2->recs + xdf2->nrec - 1;
441
	for (lim -= i, i = 0; i < lim; i++, recs1--, recs2--)
442
		if ((*recs1)->ha != (*recs2)->ha)
443
			break;
444

445
	xdf1->dend = xdf1->nrec - i - 1;
446
	xdf2->dend = xdf2->nrec - i - 1;
447

448
	return 0;
449
}
450

451

452
static int xdl_optimize_ctxs(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2) {
453

454
	if (xdl_trim_ends(xdf1, xdf2) < 0 ||
455
	    xdl_cleanup_records(cf, xdf1, xdf2) < 0) {
456

457
		return -1;
458
	}
459

460
	return 0;
461
}
462