Show More
@@ -57,12 +57,10 b' struct pos {' | |||||
57 | int pos, len; |
|
57 | int pos, len; | |
58 | }; |
|
58 | }; | |
59 |
|
59 | |||
|
60 | struct hunk; | |||
60 | struct hunk { |
|
61 | struct hunk { | |
61 | int a1, a2, b1, b2; |
|
62 | int a1, a2, b1, b2; | |
62 | }; |
|
63 | struct hunk *next; | |
63 |
|
||||
64 | struct hunklist { |
|
|||
65 | struct hunk *base, *head; |
|
|||
66 | }; |
|
64 | }; | |
67 |
|
65 | |||
68 | int splitlines(const char *a, int len, struct line **lr) |
|
66 | int splitlines(const char *a, int len, struct line **lr) | |
@@ -223,8 +221,8 b' static int longest_match(struct line *a,' | |||||
223 | return mk + mb; |
|
221 | return mk + mb; | |
224 | } |
|
222 | } | |
225 |
|
223 | |||
226 |
static |
|
224 | static struct hunk *recurse(struct line *a, struct line *b, struct pos *pos, | |
227 |
int a1, int a2, int b1, int b2, struct hunk |
|
225 | int a1, int a2, int b1, int b2, struct hunk *l) | |
228 | { |
|
226 | { | |
229 | int i, j, k; |
|
227 | int i, j, k; | |
230 |
|
228 | |||
@@ -232,51 +230,66 b' static void recurse(struct line *a, stru' | |||||
232 | /* find the longest match in this chunk */ |
|
230 | /* find the longest match in this chunk */ | |
233 | k = longest_match(a, b, pos, a1, a2, b1, b2, &i, &j); |
|
231 | k = longest_match(a, b, pos, a1, a2, b1, b2, &i, &j); | |
234 | if (!k) |
|
232 | if (!k) | |
235 | return; |
|
233 | return l; | |
236 |
|
234 | |||
237 | /* and recurse on the remaining chunks on either side */ |
|
235 | /* and recurse on the remaining chunks on either side */ | |
238 | recurse(a, b, pos, a1, i, b1, j, l); |
|
236 | l = recurse(a, b, pos, a1, i, b1, j, l); | |
239 | l->head->a1 = i; |
|
237 | if (!l) | |
240 | l->head->a2 = i + k; |
|
238 | return NULL; | |
241 | l->head->b1 = j; |
|
239 | ||
242 | l->head->b2 = j + k; |
|
240 | l->next = (struct hunk *)malloc(sizeof(struct hunk)); | |
243 | l->head++; |
|
241 | if (!l->next) | |
244 | /* tail-recursion didn't happen, so doing equivalent iteration */ |
|
242 | return NULL; | |
|
243 | ||||
|
244 | l = l->next; | |||
|
245 | l->a1 = i; | |||
|
246 | l->a2 = i + k; | |||
|
247 | l->b1 = j; | |||
|
248 | l->b2 = j + k; | |||
|
249 | l->next = NULL; | |||
|
250 | ||||
|
251 | /* tail-recursion didn't happen, so do equivalent iteration */ | |||
245 | a1 = i + k; |
|
252 | a1 = i + k; | |
246 | b1 = j + k; |
|
253 | b1 = j + k; | |
247 | } |
|
254 | } | |
248 | } |
|
255 | } | |
249 |
|
256 | |||
250 |
static |
|
257 | static int diff(struct line *a, int an, struct line *b, int bn, | |
|
258 | struct hunk *base) | |||
251 | { |
|
259 | { | |
252 | struct hunklist l; |
|
|||
253 | struct hunk *curr; |
|
260 | struct hunk *curr; | |
254 | struct pos *pos; |
|
261 | struct pos *pos; | |
255 | int t; |
|
262 | int t, count = 0; | |
256 |
|
263 | |||
257 | /* allocate and fill arrays */ |
|
264 | /* allocate and fill arrays */ | |
258 | t = equatelines(a, an, b, bn); |
|
265 | t = equatelines(a, an, b, bn); | |
259 | pos = (struct pos *)calloc(bn ? bn : 1, sizeof(struct pos)); |
|
266 | pos = (struct pos *)calloc(bn ? bn : 1, sizeof(struct pos)); | |
260 | /* we can't have more matches than lines in the shorter file */ |
|
267 | ||
261 | l.head = l.base = (struct hunk *)malloc(sizeof(struct hunk) * |
|
268 | if (pos && t) { | |
262 | ((an<bn ? an:bn) + 1)); |
|
269 | /* generate the matching block list */ | |
|
270 | ||||
|
271 | curr = recurse(a, b, pos, 0, an, 0, bn, base); | |||
|
272 | if (!curr) | |||
|
273 | return -1; | |||
263 |
|
274 | |||
264 | if (pos && l.base && t) { |
|
275 | /* sentinel end hunk */ | |
265 | /* generate the matching block list */ |
|
276 | curr->next = (struct hunk *)malloc(sizeof(struct hunk)); | |
266 | recurse(a, b, pos, 0, an, 0, bn, &l); |
|
277 | if (!curr->next) | |
267 | l.head->a1 = l.head->a2 = an; |
|
278 | return NULL; | |
268 | l.head->b1 = l.head->b2 = bn; |
|
279 | curr = curr->next; | |
269 | l.head++; |
|
280 | curr->a1 = curr->a2 = an; | |
|
281 | curr->b1 = curr->b2 = bn; | |||
|
282 | curr->next = NULL; | |||
270 | } |
|
283 | } | |
271 |
|
284 | |||
272 | free(pos); |
|
285 | free(pos); | |
273 |
|
286 | |||
274 | /* normalize the hunk list, try to push each hunk towards the end */ |
|
287 | /* normalize the hunk list, try to push each hunk towards the end */ | |
275 |
for (curr = |
|
288 | for (curr = base->next; curr; curr = curr->next) { | |
276 |
struct hunk *next = curr |
|
289 | struct hunk *next = curr->next; | |
277 | int shift = 0; |
|
290 | int shift = 0; | |
278 |
|
291 | |||
279 |
if (next |
|
292 | if (!next) | |
280 | break; |
|
293 | break; | |
281 |
|
294 | |||
282 | if (curr->a2 == next->a1) |
|
295 | if (curr->a2 == next->a1) | |
@@ -297,16 +310,26 b' static struct hunklist diff(struct line ' | |||||
297 | next->a1 += shift; |
|
310 | next->a1 += shift; | |
298 | } |
|
311 | } | |
299 |
|
312 | |||
300 | return l; |
|
313 | for (curr = base->next; curr; curr = curr->next) | |
|
314 | count++; | |||
|
315 | return count; | |||
|
316 | } | |||
|
317 | ||||
|
318 | static void freehunks(struct hunk *l) | |||
|
319 | { | |||
|
320 | struct hunk *n; | |||
|
321 | for (; l; l = n) { | |||
|
322 | n = l->next; | |||
|
323 | free(l); | |||
|
324 | } | |||
301 | } |
|
325 | } | |
302 |
|
326 | |||
303 | static PyObject *blocks(PyObject *self, PyObject *args) |
|
327 | static PyObject *blocks(PyObject *self, PyObject *args) | |
304 | { |
|
328 | { | |
305 | PyObject *sa, *sb, *rl = NULL, *m; |
|
329 | PyObject *sa, *sb, *rl = NULL, *m; | |
306 | struct line *a, *b; |
|
330 | struct line *a, *b; | |
307 |
struct hunk |
|
331 | struct hunk l, *h; | |
308 | struct hunk *h; |
|
332 | int an, bn, count, pos = 0; | |
309 | int an, bn, pos = 0; |
|
|||
310 |
|
333 | |||
311 | if (!PyArg_ParseTuple(args, "SS:bdiff", &sa, &sb)) |
|
334 | if (!PyArg_ParseTuple(args, "SS:bdiff", &sa, &sb)) | |
312 | return NULL; |
|
335 | return NULL; | |
@@ -317,12 +340,16 b' static PyObject *blocks(PyObject *self, ' | |||||
317 | if (!a || !b) |
|
340 | if (!a || !b) | |
318 | goto nomem; |
|
341 | goto nomem; | |
319 |
|
342 | |||
320 | l = diff(a, an, b, bn); |
|
343 | l.next = NULL; | |
321 | rl = PyList_New(l.head - l.base); |
|
344 | count = diff(a, an, b, bn, &l); | |
322 | if (!l.head || !rl) |
|
345 | if (count < 0) | |
323 | goto nomem; |
|
346 | goto nomem; | |
324 |
|
347 | |||
325 | for (h = l.base; h != l.head; h++) { |
|
348 | rl = PyList_New(count); | |
|
349 | if (!rl) | |||
|
350 | goto nomem; | |||
|
351 | ||||
|
352 | for (h = l.next; h; h = h->next) { | |||
326 | m = Py_BuildValue("iiii", h->a1, h->a2, h->b1, h->b2); |
|
353 | m = Py_BuildValue("iiii", h->a1, h->a2, h->b1, h->b2); | |
327 | PyList_SetItem(rl, pos, m); |
|
354 | PyList_SetItem(rl, pos, m); | |
328 | pos++; |
|
355 | pos++; | |
@@ -331,7 +358,7 b' static PyObject *blocks(PyObject *self, ' | |||||
331 | nomem: |
|
358 | nomem: | |
332 | free(a); |
|
359 | free(a); | |
333 | free(b); |
|
360 | free(b); | |
334 |
free(l. |
|
361 | freehunks(l.next); | |
335 | return rl ? rl : PyErr_NoMemory(); |
|
362 | return rl ? rl : PyErr_NoMemory(); | |
336 | } |
|
363 | } | |
337 |
|
364 | |||
@@ -340,10 +367,9 b' static PyObject *bdiff(PyObject *self, P' | |||||
340 | char *sa, *sb; |
|
367 | char *sa, *sb; | |
341 | PyObject *result = NULL; |
|
368 | PyObject *result = NULL; | |
342 | struct line *al, *bl; |
|
369 | struct line *al, *bl; | |
343 |
struct hunk |
|
370 | struct hunk l, *h; | |
344 | struct hunk *h; |
|
|||
345 | char encode[12], *rb; |
|
371 | char encode[12], *rb; | |
346 | int an, bn, len = 0, la, lb; |
|
372 | int an, bn, len = 0, la, lb, count; | |
347 |
|
373 | |||
348 | if (!PyArg_ParseTuple(args, "s#s#:bdiff", &sa, &la, &sb, &lb)) |
|
374 | if (!PyArg_ParseTuple(args, "s#s#:bdiff", &sa, &la, &sb, &lb)) | |
349 | return NULL; |
|
375 | return NULL; | |
@@ -353,13 +379,14 b' static PyObject *bdiff(PyObject *self, P' | |||||
353 | if (!al || !bl) |
|
379 | if (!al || !bl) | |
354 | goto nomem; |
|
380 | goto nomem; | |
355 |
|
381 | |||
356 | l = diff(al, an, bl, bn); |
|
382 | l.next = NULL; | |
357 | if (!l.head) |
|
383 | count = diff(al, an, bl, bn, &l); | |
|
384 | if (count < 0) | |||
358 | goto nomem; |
|
385 | goto nomem; | |
359 |
|
386 | |||
360 | /* calculate length of output */ |
|
387 | /* calculate length of output */ | |
361 | la = lb = 0; |
|
388 | la = lb = 0; | |
362 |
for (h = l. |
|
389 | for (h = l.next; h; h = h->next) { | |
363 | if (h->a1 != la || h->b1 != lb) |
|
390 | if (h->a1 != la || h->b1 != lb) | |
364 | len += 12 + bl[h->b1].l - bl[lb].l; |
|
391 | len += 12 + bl[h->b1].l - bl[lb].l; | |
365 | la = h->a2; |
|
392 | la = h->a2; | |
@@ -375,7 +402,7 b' static PyObject *bdiff(PyObject *self, P' | |||||
375 | rb = PyBytes_AsString(result); |
|
402 | rb = PyBytes_AsString(result); | |
376 | la = lb = 0; |
|
403 | la = lb = 0; | |
377 |
|
404 | |||
378 |
for (h = l. |
|
405 | for (h = l.next; h; h = h->next) { | |
379 | if (h->a1 != la || h->b1 != lb) { |
|
406 | if (h->a1 != la || h->b1 != lb) { | |
380 | len = bl[h->b1].l - bl[lb].l; |
|
407 | len = bl[h->b1].l - bl[lb].l; | |
381 | *(uint32_t *)(encode) = htonl(al[la].l - al->l); |
|
408 | *(uint32_t *)(encode) = htonl(al[la].l - al->l); | |
@@ -392,7 +419,7 b' static PyObject *bdiff(PyObject *self, P' | |||||
392 | nomem: |
|
419 | nomem: | |
393 | free(al); |
|
420 | free(al); | |
394 | free(bl); |
|
421 | free(bl); | |
395 |
free(l. |
|
422 | freehunks(l.next); | |
396 | return result ? result : PyErr_NoMemory(); |
|
423 | return result ? result : PyErr_NoMemory(); | |
397 | } |
|
424 | } | |
398 |
|
425 |
General Comments 0
You need to be logged in to leave comments.
Login now