← Back to branch summary

~ubuntu-branches/ubuntu/precise/mercurial/precise-updates

« back to all changes in this revision

Viewing changes to mercurial/bdiff.c

  • Committer: Bazaar Package Importer
  • Author(s): Javi Merino
  • Date: 2011-03-06 16:01:58 UTC
  • mto: (28.1.2 sid) (1.1.14)
  • mto: This revision was merged to the branch mainline in revision 32.
  • Revision ID: james.westby@ubuntu.com-20110306160158-y94pzpmtd7b1xgjk
Tags: upstream-1.8
Import upstream version 1.8

Show diffs side-by-side

added added

removed removed

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