Line Flow Count Block(s) Source
1 - /*
2 - * Copyright (C) 2010, Google Inc.
3 - * and other copyright owners as documented in JGit's IP log.
4 - *
5 - * This program and the accompanying materials are made available
6 - * under the terms of the Eclipse Distribution License v1.0 which
7 - * accompanies this distribution, is reproduced below, and is
8 - * available at http://www.eclipse.org/org/documents/edl-v10.php
9 - *
10 - * All rights reserved.
11 - *
12 - * Redistribution and use in source and binary forms, with or
13 - * without modification, are permitted provided that the following
14 - * conditions are met:
15 - *
16 - * - Redistributions of source code must retain the above copyright
17 - * notice, this list of conditions and the following disclaimer.
18 - *
19 - * - Redistributions in binary form must reproduce the above
20 - * copyright notice, this list of conditions and the following
21 - * disclaimer in the documentation and/or other materials provided
22 - * with the distribution.
23 - *
24 - * - Neither the name of the Eclipse Foundation, Inc. nor the
25 - * names of its contributors may be used to endorse or promote
26 - * products derived from this software without specific prior
27 - * written permission.
28 - *
29 - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
30 - * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
31 - * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
32 - * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
33 - * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
34 - * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
35 - * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
36 - * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
37 - * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
38 - * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
39 - * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
40 - * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
41 - * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
42 - */
43 -
44 - #include "xinclude.h"
45 - #include "xtypes.h"
46 - #include "xdiff.h"
47 -
48 - #define MAX_PTR UINT_MAX
49 - #define MAX_CNT UINT_MAX
50 -
51 - #define LINE_END(n) (line##n + count##n - 1)
52 - #define LINE_END_PTR(n) (*line##n + *count##n - 1)
53 -
54 - struct histindex {
55 - struct record {
56 - unsigned int ptr, cnt;
57 - struct record *next;
58 - } **records, /* an occurrence */
59 - **line_map; /* map of line to record chain */
60 - chastore_t rcha;
61 - unsigned int *next_ptrs;
62 - unsigned int table_bits,
63 - records_size,
64 - line_map_size;
65 -
66 - unsigned int max_chain_length,
67 - key_shift,
68 - ptr_shift;
69 -
70 - unsigned int cnt,
71 - has_common;
72 -
73 - xdfenv_t *env;
74 - xpparam_t const *xpp;
75 - };
76 -
77 - struct region {
78 - unsigned int begin1, end1;
79 - unsigned int begin2, end2;
80 - };
81 -
82 - #define LINE_MAP(i, a) (i->line_map[(a) - i->ptr_shift])
83 -
84 - #define NEXT_PTR(index, ptr) \
85 - (index->next_ptrs[(ptr) - index->ptr_shift])
86 -
87 - #define CNT(index, ptr) \
88 - ((LINE_MAP(index, ptr))->cnt)
89 -
90 - #define REC(env, s, l) \
91 - (env->xdf##s.recs[l - 1])
92 -
93 ##### 2 static int cmp_recs(xpparam_t const *xpp,
94 - xrecord_t *r1, xrecord_t *r2)
95 - {
96 ##### 2,4 return r1->ha == r2->ha &&
97 ##### 3 xdl_recmatch(r1->ptr, r1->size, r2->ptr, r2->size,
98 ##### 3 xpp->flags);
99 - }
100 -
101 - #define CMP_ENV(xpp, env, s1, l1, s2, l2) \
102 - (cmp_recs(xpp, REC(env, s1, l1), REC(env, s2, l2)))
103 -
104 - #define CMP(i, s1, l1, s2, l2) \
105 - (cmp_recs(i->xpp, REC(i->env, s1, l1), REC(i->env, s2, l2)))
106 -
107 - #define TABLE_HASH(index, side, line) \
108 - XDL_HASHLONG((REC(index->env, side, line))->ha, index->table_bits)
109 -
110 ##### 2 static int scanA(struct histindex *index, unsigned int line1, unsigned int count1)
111 - {
112 - unsigned int ptr;
113 - unsigned int tbl_idx;
114 - unsigned int chain_len;
115 - struct record **rec_chain, *rec;
116 -
117 ##### 2,15,16 for (ptr = LINE_END(1); line1 <= ptr; ptr--) {
118 ##### 3 tbl_idx = TABLE_HASH(index, 1, ptr);
119 ##### 3 rec_chain = index->records + tbl_idx;
120 ##### 3 rec = *rec_chain;
121 -
122 ##### 3 chain_len = 0;
123 ##### 3,8 while (rec) {
124 ##### 4,5 if (CMP(index, 1, rec->ptr, 1, ptr)) {
125 - /*
126 - * ptr is identical to another element. Insert
127 - * it onto the front of the existing element
128 - * chain.
129 - */
130 ##### 6 NEXT_PTR(index, ptr) = rec->ptr;
131 ##### 6 rec->ptr = ptr;
132 - /* cap rec->cnt at MAX_CNT */
133 ##### 6 rec->cnt = XDL_MIN(MAX_CNT, rec->cnt + 1);
134 ##### 6 LINE_MAP(index, ptr) = rec;
135 ##### 6 goto continue_scan;
136 - }
137 -
138 ##### 7 rec = rec->next;
139 ##### 7 chain_len++;
140 - }
141 -
142 ##### 9 if (chain_len == index->max_chain_length)
143 ##### 10 return -1;
144 -
145 - /*
146 - * This is the first time we have ever seen this particular
147 - * element in the sequence. Construct a new chain for it.
148 - */
149 ##### 11,12 if (!(rec = xdl_cha_alloc(&index->rcha)))
150 ##### 13 return -1;
151 ##### 14 rec->ptr = ptr;
152 ##### 14 rec->cnt = 1;
153 ##### 14 rec->next = *rec_chain;
154 ##### 14 *rec_chain = rec;
155 ##### 14 LINE_MAP(index, ptr) = rec;
156 -
157 - continue_scan:
158 - ; /* no op */
159 - }
160 -
161 ##### 17 return 0;
162 - }
163 -
164 ##### 2 static int try_lcs(
165 - struct histindex *index, struct region *lcs, unsigned int b_ptr,
166 - unsigned int line1, unsigned int count1,
167 - unsigned int line2, unsigned int count2)
168 - {
169 ##### 2 unsigned int b_next = b_ptr + 1;
170 ##### 2 struct record *rec = index->records[TABLE_HASH(index, 2, b_ptr)];
171 - unsigned int as, ae, bs, be, np, rc;
172 - int should_break;
173 -
174 ##### 2,40,41 for (; rec; rec = rec->next) {
175 ##### 3 if (rec->cnt > index->cnt) {
176 ##### 4 if (!index->has_common)
177 ##### 5,6 index->has_common = CMP(index, 1, rec->ptr, 2, b_ptr);
178 ##### 7 continue;
179 - }
180 -
181 ##### 8 as = rec->ptr;
182 ##### 8,9 if (!CMP(index, 1, as, 2, b_ptr))
183 ##### 10 continue;
184 -
185 ##### 11 index->has_common = 1;
186 - for (;;) {
187 ##### 12 should_break = 0;
188 ##### 12 np = NEXT_PTR(index, as);
189 ##### 12 bs = b_ptr;
190 ##### 12 ae = as;
191 ##### 12 be = bs;
192 ##### 12 rc = rec->cnt;
193 -
194 ##### 12,15,16 while (line1 < as && line2 < bs
195 ##### 17,18 && CMP(index, 1, as - 1, 2, bs - 1)) {
196 ##### 13 as--;
197 ##### 13 bs--;
198 ##### 13 if (1 < rc)
199 ##### 14 rc = XDL_MIN(rc, CNT(index, as));
200 - }
201 ##### 19,22,23 while (ae < LINE_END(1) && be < LINE_END(2)
202 ##### 24,25 && CMP(index, 1, ae + 1, 2, be + 1)) {
203 ##### 20 ae++;
204 ##### 20 be++;
205 ##### 20 if (1 < rc)
206 ##### 21 rc = XDL_MIN(rc, CNT(index, ae));
207 - }
208 -
209 ##### 26 if (b_next <= be)
210 ##### 27 b_next = be + 1;
211 ##### 28,29 if (lcs->end1 - lcs->begin1 < ae - as || rc < index->cnt) {
212 ##### 30 lcs->begin1 = as;
213 ##### 30 lcs->begin2 = bs;
214 ##### 30 lcs->end1 = ae;
215 ##### 30 lcs->end2 = be;
216 ##### 30 index->cnt = rc;
217 - }
218 -
219 ##### 31 if (np == 0)
220 ##### 32 break;
221 -
222 ##### 33,36 while (np <= ae) {
223 ##### 34 np = NEXT_PTR(index, np);
224 ##### 34 if (np == 0) {
225 ##### 35 should_break = 1;
226 ##### 35 break;
227 - }
228 - }
229 -
230 ##### 37 if (should_break)
231 ##### 38 break;
232 -
233 ##### 39 as = np;
234 ##### 39 }
235 - }
236 ##### 42 return b_next;
237 - }
238 -
239 ##### 2 static int find_lcs(
240 - struct histindex *index, struct region *lcs,
241 - unsigned int line1, unsigned int count1,
242 - unsigned int line2, unsigned int count2)
243 - {
244 - unsigned int b_ptr;
245 -
246 ##### 2,3 if (scanA(index, line1, count1))
247 ##### 4 return -1;
248 -
249 ##### 5 index->cnt = index->max_chain_length + 1;
250 -
251 ##### 5,8 for (b_ptr = line2; b_ptr <= LINE_END(2); )
252 ##### 6,7 b_ptr = try_lcs(index, lcs, b_ptr, line1, count1, line2, count2);
253 -
254 ##### 9 return index->has_common && index->max_chain_length < index->cnt;
255 - }
256 -
257 ##### 2 static int fall_back_to_classic_diff(struct histindex *index,
258 - int line1, int count1, int line2, int count2)
259 - {
260 - xpparam_t xpp;
261 ##### 2 xpp.flags = index->xpp->flags & ~XDF_DIFF_ALGORITHM_MASK;
262 -
263 ##### 2 return xdl_fall_back_diff(index->env, &xpp,
264 - line1, count1, line2, count2);
265 - }
266 -
267 ##### 2 static int histogram_diff(
268 - xpparam_t const *xpp, xdfenv_t *env,
269 - unsigned int line1, unsigned int count1,
270 - unsigned int line2, unsigned int count2)
271 - {
272 - struct histindex index;
273 - struct region lcs;
274 - size_t sz;
275 ##### 2 int result = -1;
276 -
277 ##### 2,3 if (count1 <= 0 && count2 <= 0)
278 ##### 4 return 0;
279 -
280 ##### 5 if (LINE_END(1) >= MAX_PTR)
281 ##### 6 return -1;
282 -
283 ##### 7 if (!count1) {
284 ##### 8,10 while(count2--)
285 ##### 9 env->xdf2.rchg[line2++ - 1] = 1;
286 ##### 11 return 0;
287 ##### 12 } else if (!count2) {
288 ##### 13,15 while(count1--)
289 ##### 14 env->xdf1.rchg[line1++ - 1] = 1;
290 ##### 16 return 0;
291 - }
292 -
293 ##### 17 memset(&index, 0, sizeof(index));
294 -
295 ##### 17 index.env = env;
296 ##### 17 index.xpp = xpp;
297 -
298 ##### 17 index.records = NULL;
299 ##### 17 index.line_map = NULL;
300 - /* in case of early xdl_cha_free() */
301 ##### 17 index.rcha.head = NULL;
302 -
303 ##### 17 index.table_bits = xdl_hashbits(count1);
304 ##### 18 sz = index.records_size = 1 << index.table_bits;
305 ##### 18-24 GIT_ERROR_CHECK_ALLOC_MULTIPLY(&sz, sz, sizeof(struct record *));
306 -
307 ##### 25,26 if (!(index.records = (struct record **) xdl_malloc(sz)))
308 ##### 27 goto cleanup;
309 ##### 28 memset(index.records, 0, sz);
310 -
311 ##### 28 sz = index.line_map_size = count1;
312 ##### 28 sz *= sizeof(struct record *);
313 ##### 28,29 if (!(index.line_map = (struct record **) xdl_malloc(sz)))
314 ##### 30 goto cleanup;
315 ##### 31 memset(index.line_map, 0, sz);
316 -
317 ##### 31 sz = index.line_map_size;
318 ##### 31 sz *= sizeof(unsigned int);
319 ##### 31,32 if (!(index.next_ptrs = (unsigned int *) xdl_malloc(sz)))
320 ##### 33 goto cleanup;
321 ##### 34 memset(index.next_ptrs, 0, sz);
322 -
323 - /* lines / 4 + 1 comes from xprepare.c:xdl_prepare_ctx() */
324 ##### 34,35 if (xdl_cha_init(&index.rcha, sizeof(struct record), count1 / 4 + 1) < 0)
325 ##### 36 goto cleanup;
326 -
327 ##### 37 index.ptr_shift = line1;
328 ##### 37 index.max_chain_length = 64;
329 -
330 ##### 37 memset(&lcs, 0, sizeof(lcs));
331 ##### 37,38 if (find_lcs(&index, &lcs, line1, count1, line2, count2))
332 ##### 39 result = fall_back_to_classic_diff(&index, line1, count1, line2, count2);
333 - else {
334 ##### 40,41 if (lcs.begin1 == 0 && lcs.begin2 == 0) {
335 ##### 42,44 while (count1--)
336 ##### 43 env->xdf1.rchg[line1++ - 1] = 1;
337 ##### 45,47 while (count2--)
338 ##### 46 env->xdf2.rchg[line2++ - 1] = 1;
339 ##### 48 result = 0;
340 - } else {
341 ##### 49,49 result = histogram_diff(xpp, env,
342 ##### 49 line1, lcs.begin1 - line1,
343 ##### 49 line2, lcs.begin2 - line2);
344 ##### 50 if (result)
345 ##### 51 goto cleanup;
346 ##### 52,52,52,52 result = histogram_diff(xpp, env,
347 ##### 52,52 lcs.end1 + 1, LINE_END(1) - lcs.end1,
348 ##### 52,52 lcs.end2 + 1, LINE_END(2) - lcs.end2);
349 ##### 53 if (result)
350 ##### 54 goto cleanup;
351 - }
352 - }
353 -
354 - cleanup:
355 ##### 55 xdl_free(index.records);
356 ##### 56 xdl_free(index.line_map);
357 ##### 57 xdl_free(index.next_ptrs);
358 ##### 58 xdl_cha_free(&index.rcha);
359 -
360 ##### 59 return result;
361 - }
362 -
363 ##### 2 int xdl_do_histogram_diff(mmfile_t *file1, mmfile_t *file2,
364 - xpparam_t const *xpp, xdfenv_t *env)
365 - {
366 ##### 2,3 if (xdl_prepare_env(file1, file2, xpp, env) < 0)
367 ##### 4 return -1;
368 -
369 ##### 5,5,5,5,5,5 return histogram_diff(xpp, env,
370 ##### 5,5,5 env->xdf1.dstart + 1, env->xdf1.dend - env->xdf1.dstart + 1,
371 ##### 5,5,5 env->xdf2.dstart + 1, env->xdf2.dend - env->xdf2.dstart + 1);
372 - }