Line Flow Count Block(s) Source
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 -
27 -
28 6366 2 long xdl_bogosqrt(long n) {
29 - long i;
30 -
31 - /*
32 - * Classical integer square root approximation using shifts.
33 - */
34 16027 2-4 for (i = 1; n > 0; n >>= 2)
35 9661 3 i <<= 1;
36 -
37 6366 5 return i;
38 - }
39 -
40 -
41 8696 2 int xdl_emit_diffrec(char const *rec, long size, char const *pre, long psize,
42 - xdemitcb_t *ecb) {
43 8696 2 int i = 2;
44 - mmbuffer_t mb[3];
45 -
46 8696 2 mb[0].ptr = (char *) pre;
47 8696 2 mb[0].size = psize;
48 8696 2 mb[1].ptr = (char *) rec;
49 8696 2 mb[1].size = size;
50 8696 2,3 if (size > 0 && rec[size - 1] != '\n') {
51 65 4 mb[2].ptr = (char *) "\n\\ No newline at end of file\n";
52 65 4 mb[2].size = strlen(mb[2].ptr);
53 65 4 i++;
54 - }
55 8696 5,6 if (ecb->outf(ecb->priv, mb, i) < 0) {
56 -
57 ##### 7 return -1;
58 - }
59 -
60 8696 8 return 0;
61 - }
62 -
63 8492 2 void *xdl_mmfile_first(mmfile_t *mmf, long *size)
64 - {
65 8492 2 *size = mmf->size;
66 8492 2 return mmf->ptr;
67 - }
68 -
69 -
70 3845 2 long xdl_mmfile_size(mmfile_t *mmf)
71 - {
72 3845 2 return mmf->size;
73 - }
74 -
75 -
76 6369 2 int xdl_cha_init(chastore_t *cha, long isize, long icount) {
77 -
78 6369 2 cha->head = cha->tail = NULL;
79 6369 2 cha->isize = isize;
80 6369 2 cha->nsize = icount * isize;
81 6369 2 cha->ancur = cha->sncur = NULL;
82 6369 2 cha->scurr = 0;
83 -
84 6369 2 return 0;
85 - }
86 -
87 -
88 6369 2 void xdl_cha_free(chastore_t *cha) {
89 - chanode_t *cur, *tmp;
90 -
91 17645 2,4 for (cur = cha->head; (tmp = cur) != NULL;) {
92 11276 3 cur = cur->next;
93 11276 3 xdl_free(tmp);
94 - }
95 6369 5 }
96 -
97 -
98 190214 2 void *xdl_cha_alloc(chastore_t *cha) {
99 - chanode_t *ancur;
100 - void *data;
101 -
102 190214 2,3 if (!(ancur = cha->ancur) || ancur->icurr == cha->nsize) {
103 11276 4,5 if (!(ancur = (chanode_t *) xdl_malloc(sizeof(chanode_t) + cha->nsize))) {
104 -
105 ##### 6 return NULL;
106 - }
107 11276 7 ancur->icurr = 0;
108 11276 7 ancur->next = NULL;
109 11276 7 if (cha->tail)
110 5308 8 cha->tail->next = ancur;
111 11276 9 if (!cha->head)
112 5968 10 cha->head = ancur;
113 11276 11 cha->tail = ancur;
114 11276 11 cha->ancur = ancur;
115 - }
116 -
117 190214 12 data = (char *) ancur + sizeof(chanode_t) + ancur->icurr;
118 190214 12 ancur->icurr += cha->isize;
119 -
120 190214 12 return data;
121 - }
122 -
123 4246 2 long xdl_guess_lines(mmfile_t *mf, long sample) {
124 4246 2 long nl = 0, size, tsize = 0;
125 - char const *data, *cur, *top;
126 -
127 4246 2,3 if ((cur = data = xdl_mmfile_first(mf, &size)) != NULL) {
128 45910 4,8,9 for (top = data + size; nl < sample && cur < top; ) {
129 41725 5 nl++;
130 41725 5 if (!(cur = memchr(cur, '\n', top - cur)))
131 83 6 cur = top;
132 - else
133 41642 7 cur++;
134 - }
135 4185 10 tsize += (long) (cur - data);
136 - }
137 -
138 4246 11,12 if (nl && tsize)
139 3845 13,14 nl = xdl_mmfile_size(mf) / (tsize / nl);
140 -
141 4246 15 return nl + 1;
142 - }
143 -
144 ##### 2 int xdl_blankline(const char *line, long size, long flags)
145 - {
146 - long i;
147 -
148 ##### 2 if (!(flags & XDF_WHITESPACE_FLAGS))
149 ##### 3 return (size <= 1);
150 -
151 ##### 4-8 for (i = 0; i < size && XDL_ISSPACE(line[i]); i++)
152 - ;
153 -
154 ##### 9 return (i == size);
155 - }
156 -
157 - /*
158 - * Have we eaten everything on the line, except for an optional
159 - * CR at the very end?
160 - */
161 ##### 2 static int ends_with_optional_cr(const char *l, long s, long i)
162 - {
163 ##### 2-5 int complete = s && l[s-1] == '\n';
164 -
165 ##### 6 if (complete)
166 ##### 7 s--;
167 ##### 8 if (s == i)
168 ##### 9 return 1;
169 - /* do not ignore CR at the end of an incomplete line */
170 ##### 10-12 if (complete && s == i + 1 && l[i] == '\r')
171 ##### 13 return 1;
172 ##### 14 return 0;
173 - }
174 -
175 160343 2 int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags)
176 - {
177 - int i1, i2;
178 -
179 160343 2,3 if (s1 == s2 && !memcmp(l1, l2, s1))
180 160079 4 return 1;
181 264 5 if (!(flags & XDF_WHITESPACE_FLAGS))
182 243 6 return 0;
183 -
184 21 7 i1 = 0;
185 21 7 i2 = 0;
186 -
187 - /*
188 - * -w matches everything that matches with -b, and -b in turn
189 - * matches everything that matches with --ignore-space-at-eol,
190 - * which in turn matches everything that matches with --ignore-cr-at-eol.
191 - *
192 - * Each flavor of ignoring needs different logic to skip whitespaces
193 - * while we have both sides to compare.
194 - */
195 21 7 if (flags & XDF_IGNORE_WHITESPACE) {
196 10 8 goto skip_ws;
197 200 21,22 while (i1 < s1 && i2 < s2) {
198 190 9 if (l1[i1++] != l2[i2++])
199 ##### 10 return 0;
200 - skip_ws:
201 259 11,13-15 while (i1 < s1 && XDL_ISSPACE(l1[i1]))
202 59 12 i1++;
203 261 16,18-20 while (i2 < s2 && XDL_ISSPACE(l2[i2]))
204 61 17 i2++;
205 - }
206 11 23 } else if (flags & XDF_IGNORE_WHITESPACE_CHANGE) {
207 64 24,42,43 while (i1 < s1 && i2 < s2) {
208 59 25-28 if (XDL_ISSPACE(l1[i1]) && XDL_ISSPACE(l2[i2])) {
209 - /* Skip matching spaces and try again */
210 28 29,31-33 while (i1 < s1 && XDL_ISSPACE(l1[i1]))
211 14 30 i1++;
212 35 34,36-38 while (i2 < s2 && XDL_ISSPACE(l2[i2]))
213 21 35 i2++;
214 14 39 continue;
215 - }
216 45 40 if (l1[i1++] != l2[i2++])
217 ##### 41 return 0;
218 - }
219 6 44 } else if (flags & XDF_IGNORE_WHITESPACE_AT_EOL) {
220 51 45,47-49 while (i1 < s1 && i2 < s2 && l1[i1] == l2[i2]) {
221 45 46 i1++;
222 45 46 i2++;
223 - }
224 ##### 50 } else if (flags & XDF_IGNORE_CR_AT_EOL) {
225 - /* Find the first difference and see how the line ends */
226 ##### 51,53-55 while (i1 < s1 && i2 < s2 && l1[i1] == l2[i2]) {
227 ##### 52 i1++;
228 ##### 52 i2++;
229 - }
230 ##### 56,57,59-62 return (ends_with_optional_cr(l1, s1, i1) &&
231 ##### 58 ends_with_optional_cr(l2, s2, i2));
232 - }
233 -
234 - /*
235 - * After running out of one side, the remaining side must have
236 - * nothing but whitespace for the lines to match. Note that
237 - * ignore-whitespace-at-eol case may break out of the loop
238 - * while there still are characters remaining on both lines.
239 - */
240 21 63 if (i1 < s1) {
241 16 64,66-68 while (i1 < s1 && XDL_ISSPACE(l1[i1]))
242 10 65 i1++;
243 6 69 if (s1 != i1)
244 ##### 70 return 0;
245 - }
246 21 71 if (i2 < s2) {
247 16 72,74-76 while (i2 < s2 && XDL_ISSPACE(l2[i2]))
248 10 73 i2++;
249 6 77 return (s2 == i2);
250 - }
251 15 78 return 1;
252 - }
253 -
254 368 2 static unsigned long xdl_hash_record_with_whitespace(char const **data,
255 - char const *top, long flags) {
256 368 2 unsigned long ha = 5381;
257 368 2 char const *ptr = *data;
258 368 2 int cr_at_eol_only = (flags & XDF_WHITESPACE_FLAGS) == XDF_IGNORE_CR_AT_EOL;
259 -
260 2044 2,31-33 for (; ptr < top && *ptr != '\n'; ptr++) {
261 1676 3 if (cr_at_eol_only) {
262 - /* do not ignore CR at the end of an incomplete line */
263 ##### 4,5 if (*ptr == '\r' &&
264 ##### 5,6 (ptr + 1 < top && ptr[1] == '\n'))
265 ##### 7 continue;
266 - }
267 1676 8,9 else if (XDL_ISSPACE(*ptr)) {
268 239 10 const char *ptr2 = ptr;
269 - int at_eol;
270 279 10,12-14 while (ptr + 1 < top && XDL_ISSPACE(ptr[1])
271 60 15 && ptr[1] != '\n')
272 40 11 ptr++;
273 239 16-19 at_eol = (top <= ptr + 1 || ptr[1] == '\n');
274 239 20 if (flags & XDF_IGNORE_WHITESPACE)
275 - ; /* already handled */
276 114 21 else if (flags & XDF_IGNORE_WHITESPACE_CHANGE
277 62 22 && !at_eol) {
278 59 23 ha += (ha << 5);
279 59 23 ha ^= (unsigned long) ' ';
280 - }
281 55 24 else if (flags & XDF_IGNORE_WHITESPACE_AT_EOL
282 52 25 && !at_eol) {
283 83 26,28 while (ptr2 != ptr + 1) {
284 42 27 ha += (ha << 5);
285 42 27 ha ^= (unsigned long) *ptr2;
286 42 27 ptr2++;
287 - }
288 - }
289 239 29 continue;
290 - }
291 1437 30 ha += (ha << 5);
292 1437 30 ha ^= (unsigned long) *ptr;
293 - }
294 368 34-36 *data = ptr < top ? ptr + 1: ptr;
295 -
296 368 37 return ha;
297 - }
298 -
299 172286 2 unsigned long xdl_hash_record(char const **data, char const *top, long flags) {
300 172286 2 unsigned long ha = 5381;
301 172286 2 char const *ptr = *data;
302 -
303 172286 2 if (flags & XDF_WHITESPACE_FLAGS)
304 368 3 return xdl_hash_record_with_whitespace(data, top, flags);
305 -
306 1364786 4-7 for (; ptr < top && *ptr != '\n'; ptr++) {
307 1192868 5 ha += (ha << 5);
308 1192868 5 ha ^= (unsigned long) *ptr;
309 - }
310 171918 8-10 *data = ptr < top ? ptr + 1: ptr;
311 -
312 171918 11 return ha;
313 - }
314 -
315 6369 2 unsigned int xdl_hashbits(unsigned int size) {
316 6369 2 unsigned int val = 1, bits = 0;
317 -
318 28700 2-5 for (; val < size && bits < CHAR_BIT * sizeof(unsigned int); val <<= 1, bits++);
319 6369 6 return bits ? bits: 1;
320 - }
321 -
322 -
323 3234 2 int xdl_num_out(char *out, long val) {
324 3234 2 char *ptr, *str = out;
325 - char buf[32];
326 -
327 3234 2 ptr = buf + sizeof(buf) - 1;
328 3234 2 *ptr = '\0';
329 3234 2 if (val < 0) {
330 ##### 3 *--ptr = '-';
331 ##### 3 val = -val;
332 - }
333 6243 4-7 for (; val && ptr > buf; val /= 10)
334 3009 5 *--ptr = "0123456789"[val % 10];
335 3234 8 if (*ptr)
336 5516 9-11 for (; *ptr; ptr++, str++)
337 3009 10 *str = *ptr;
338 - else
339 727 12 *str++ = '0';
340 3234 13 *str = '\0';
341 -
342 3234 13 return str - out;
343 - }
344 -
345 945 2 int xdl_emit_hunk_hdr(long s1, long c1, long s2, long c2,
346 - const char *func, long funclen, xdemitcb_t *ecb) {
347 945 2 int nb = 0;
348 - mmbuffer_t mb;
349 - char buf[128];
350 -
351 945 2 memcpy(buf, "@@ -", 4);
352 945 2 nb += 4;
353 -
354 945 2-5 nb += xdl_num_out(buf + nb, c1 ? s1: s1 - 1);
355 -
356 945 6 if (c1 != 1) {
357 558 7 memcpy(buf + nb, ",", 1);
358 558 7 nb += 1;
359 -
360 558 7,8 nb += xdl_num_out(buf + nb, c1);
361 - }
362 -
363 945 9 memcpy(buf + nb, " +", 2);
364 945 9 nb += 2;
365 -
366 945 9-12 nb += xdl_num_out(buf + nb, c2 ? s2: s2 - 1);
367 -
368 945 13 if (c2 != 1) {
369 786 14 memcpy(buf + nb, ",", 1);
370 786 14 nb += 1;
371 -
372 786 14,15 nb += xdl_num_out(buf + nb, c2);
373 - }
374 -
375 945 16 memcpy(buf + nb, " @@", 3);
376 945 16 nb += 3;
377 945 16,17 if (func && funclen) {
378 176 18 buf[nb++] = ' ';
379 176 18 if (funclen > (long)(sizeof(buf) - nb - 1))
380 ##### 19 funclen = sizeof(buf) - nb - 1;
381 176 20 memcpy(buf + nb, func, funclen);
382 176 20 nb += funclen;
383 - }
384 945 21 buf[nb++] = '\n';
385 -
386 945 21 mb.ptr = buf;
387 945 21 mb.size = nb;
388 945 21,22 if (ecb->outf(ecb->priv, &mb, 1) < 0)
389 ##### 23 return -1;
390 -
391 945 24 return 0;
392 - }
393 -
394 ##### 2 int xdl_fall_back_diff(xdfenv_t *diff_env, xpparam_t const *xpp,
395 - int line1, int count1, int line2, int count2)
396 - {
397 - /*
398 - * This probably does not work outside Git, since
399 - * we have a very simple mmfile structure.
400 - *
401 - * Note: ideally, we would reuse the prepared environment, but
402 - * the libxdiff interface does not (yet) allow for diffing only
403 - * ranges of lines instead of the whole files.
404 - */
405 - mmfile_t subfile1, subfile2;
406 - xdfenv_t env;
407 -
408 ##### 2 subfile1.ptr = (char *)diff_env->xdf1.recs[line1 - 1]->ptr;
409 ##### 2,2,2 subfile1.size = diff_env->xdf1.recs[line1 + count1 - 2]->ptr +
410 ##### 2,2 diff_env->xdf1.recs[line1 + count1 - 2]->size - subfile1.ptr;
411 ##### 2 subfile2.ptr = (char *)diff_env->xdf2.recs[line2 - 1]->ptr;
412 ##### 2,2,2 subfile2.size = diff_env->xdf2.recs[line2 + count2 - 2]->ptr +
413 ##### 2,2 diff_env->xdf2.recs[line2 + count2 - 2]->size - subfile2.ptr;
414 ##### 2,3 if (xdl_do_diff(&subfile1, &subfile2, xpp, &env) < 0)
415 ##### 4 return -1;
416 -
417 ##### 5 memcpy(diff_env->xdf1.rchg + line1 - 1, env.xdf1.rchg, count1);
418 ##### 5 memcpy(diff_env->xdf2.rchg + line2 - 1, env.xdf2.rchg, count2);
419 -
420 ##### 5 xdl_free_env(&env);
421 -
422 ##### 6 return 0;
423 - }