/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/_patiencediff_c.c

  • Committer: John Arbash Meinel
  • Date: 2008-07-09 21:42:24 UTC
  • mto: This revision was merged to the branch mainline in revision 3543.
  • Revision ID: john@arbash-meinel.com-20080709214224-r75k87r6a01pfc3h
Restore a real weave merge to 'bzr merge --weave'.

To do so efficiently, we only add the simple LCAs to the final weave
object, unless we run into complexities with the merge graph.
This gives the same effective result as adding all the texts,
with the advantage of not having to extract all of them.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_patiencediff_c.c
1
1
/*
2
 
 Copyright (C) 2007, 2010 Canonical Ltd
 
2
 Copyright (C) 2007 Canonical Ltd
3
3
 
4
4
 This program is free software; you can redistribute it and/or modify
5
5
 it under the terms of the GNU General Public License as published by
13
13
 
14
14
 You should have received a copy of the GNU General Public License
15
15
 along with this program; if not, write to the Free Software
16
 
 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 
16
 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
17
17
 
18
18
 Function equate_lines based on bdiff.c from Mercurial.
19
19
   Copyright (C) 2005, 2006 Matt Mackall <mpm@selenic.com>
27
27
#include <string.h>
28
28
#include <Python.h>
29
29
 
30
 
#include "python-compat.h"
 
30
 
 
31
/* http://www.python.org/dev/peps/pep-0353/ */
 
32
#if PY_VERSION_HEX < 0x02050000 && !defined(PY_SSIZE_T_MIN)
 
33
typedef int Py_ssize_t;
 
34
#define PY_SSIZE_T_MAX INT_MAX
 
35
#define PY_SSIZE_T_MIN INT_MIN
 
36
#endif
31
37
 
32
38
 
33
39
#if defined(__GNUC__)
46
52
#define SENTINEL -1
47
53
 
48
54
 
49
 
/* malloc returns NULL on some platforms if you try to allocate nothing,
50
 
 * causing <https://bugs.edge.launchpad.net/bzr/+bug/511267> and
51
 
 * <https://bugs.edge.launchpad.net/bzr/+bug/331095>.  On glibc it passes, but
52
 
 * let's make it fail to aid testing. */
53
 
#define guarded_malloc(x) ( (x) ? malloc(x) : NULL )
54
 
 
55
55
enum {
56
56
    OP_EQUAL = 0,
57
57
    OP_INSERT,
189
189
    while (hsize < bsize + 1)
190
190
        hsize *= 2;
191
191
 
192
 
    /* can't be 0 */
193
 
    hashtable = (struct bucket *) guarded_malloc(sizeof(struct bucket) * hsize);
 
192
    hashtable = (struct bucket *)malloc(sizeof(struct bucket) * hsize);
194
193
    if (hashtable == NULL) {
195
194
        PyErr_NoMemory();
196
195
        return 0;
305
304
        apos = SENTINEL;
306
305
        /* loop through all lines in the linked list */
307
306
        for (i = h[equiv].a_pos; i != SENTINEL; i = lines_a[i].next) {
308
 
            /* the index is lower than alo, continue to the next line */
 
307
            /* the index is lower than alo, the the next line */
309
308
            if (i < alo) {
310
309
                h[equiv].a_pos = i;
311
310
                continue;
326
325
        /* check for duplicates of this line in lines_b[blo:bhi] */
327
326
        /* loop through all lines in the linked list */
328
327
        for (i = h[equiv].b_pos; i != SENTINEL; i = lines_b[i].next) {
329
 
            /* the index is lower than blo, continue to the next line */
 
328
            /* the index is lower than blo, the the next line */
330
329
            if (i < blo) {
331
330
                h[equiv].b_pos = i;
332
331
                continue;
467
466
    last_a_pos = alo - 1;
468
467
    last_b_pos = blo - 1;
469
468
 
470
 
    lcs = (struct matching_line *)guarded_malloc(sizeof(struct matching_line) * (bhi - blo));
 
469
    lcs = (struct matching_line *)malloc(sizeof(struct matching_line) * (bhi - blo));
471
470
    if (lcs == NULL)
472
471
        return 0;
473
472
 
542
541
}
543
542
 
544
543
 
545
 
static void
546
 
delete_lines(struct line *lines, Py_ssize_t size)
547
 
{
548
 
    struct line *line = lines;
549
 
    while (size-- > 0) {
550
 
        Py_XDECREF(line->data);
551
 
        line++;
552
 
    }
553
 
    free(lines);
554
 
}
555
 
 
556
 
 
557
544
static Py_ssize_t
558
545
load_lines(PyObject *orig, struct line **lines)
559
546
{
572
559
        return 0;
573
560
    }
574
561
 
575
 
    /* Allocate a memory block for line data, initialized to 0 */
576
 
    line = *lines = (struct line *)calloc(size, sizeof(struct line));
 
562
    line = *lines = (struct line *)malloc(sizeof(struct line) * size);
577
563
    if (line == NULL) {
578
564
        PyErr_NoMemory();
579
565
        Py_DECREF(seq);
582
568
 
583
569
    for (i = 0; i < size; i++) {
584
570
        item = PySequence_Fast_GET_ITEM(seq, i);
585
 
        Py_INCREF(item);
586
571
        line->data = item;
587
572
        line->hash = PyObject_Hash(item);
588
573
        if (line->hash == (-1)) {
596
581
 
597
582
    cleanup:
598
583
    Py_DECREF(seq);
599
 
    if (size == -1) {
600
 
        /* Error -- cleanup unused object references */
601
 
        delete_lines(*lines, i);
602
 
        *lines = NULL;
603
 
    }
604
584
    return size;
605
585
}
606
586
 
627
607
    if (!equate_lines(&hashtable, a, b, asize, bsize))
628
608
        goto error;
629
609
 
630
 
    if (bsize > 0) {
631
 
        matches = (struct matching_line *)guarded_malloc(sizeof(struct matching_line) * bsize);
632
 
        if (matches == NULL)
633
 
            goto error;
 
610
    matches = (struct matching_line *)malloc(sizeof(struct matching_line) * bsize);
 
611
    if (matches == NULL)
 
612
        goto error;
634
613
 
635
 
        backpointers = (Py_ssize_t *)guarded_malloc(sizeof(Py_ssize_t) * bsize * 4);
636
 
        if (backpointers == NULL)
637
 
            goto error;
638
 
    }
 
614
    backpointers = (Py_ssize_t *)malloc(sizeof(Py_ssize_t) * bsize * 4);
 
615
    if (backpointers == NULL)
 
616
        goto error;
639
617
 
640
618
    nmatches = unique_lcs(matches, &hashtable, backpointers, a, b, 0, 0, asize, bsize);
641
619
 
655
633
    free(backpointers);
656
634
    free(matches);
657
635
    free(hashtable.table);
658
 
    delete_lines(b, bsize);
659
 
    delete_lines(a, asize);
 
636
    free(b);
 
637
    free(a);
660
638
    return res;
661
639
 
662
640
error:
663
641
    free(backpointers);
664
642
    free(matches);
665
643
    free(hashtable.table);
666
 
    delete_lines(b, bsize);
667
 
    delete_lines(a, asize);
 
644
    free(b);
 
645
    free(a);
668
646
    return NULL;
669
647
}
670
648
 
701
679
        goto error;
702
680
 
703
681
    matches.count = 0;
704
 
 
705
 
    if (bsize > 0) {
706
 
        matches.matches = (struct matching_block *)guarded_malloc(sizeof(struct matching_block) * bsize);
707
 
        if (matches.matches == NULL)
708
 
            goto error;
709
 
 
710
 
        backpointers = (Py_ssize_t *)guarded_malloc(sizeof(Py_ssize_t) * bsize * 4);
711
 
        if (backpointers == NULL)
712
 
            goto error;
713
 
    } else {
714
 
        matches.matches = NULL;
715
 
        backpointers = NULL;
716
 
    }
 
682
    matches.matches = (struct matching_block *)malloc(sizeof(struct matching_block) * bsize);
 
683
    if (matches.matches == NULL)
 
684
        goto error;
 
685
 
 
686
    backpointers = (Py_ssize_t *)malloc(sizeof(Py_ssize_t) * bsize * 4);
 
687
    if (backpointers == NULL)
 
688
        goto error;
717
689
 
718
690
    res = recurse_matches(&matches, &hashtable, backpointers,
719
691
                          a, b, alo, blo, ahi, bhi, maxrecursion);
739
711
    free(backpointers);
740
712
    free(matches.matches);
741
713
    free(hashtable.table);
742
 
    delete_lines(b, bsize);
743
 
    delete_lines(a, asize);
 
714
    free(b);
 
715
    free(a);
744
716
    Py_RETURN_NONE;
745
717
 
746
718
error:
747
719
    free(backpointers);
748
720
    free(matches.matches);
749
721
    free(hashtable.table);
750
 
    delete_lines(b, bsize);
751
 
    delete_lines(a, asize);
 
722
    free(b);
 
723
    free(a);
752
724
    return NULL;
753
725
}
754
726
 
780
752
            return NULL;
781
753
        }
782
754
 
783
 
        if (self->bsize > 0) {
784
 
            self->backpointers = (Py_ssize_t *)guarded_malloc(sizeof(Py_ssize_t) * self->bsize * 4);
785
 
            if (self->backpointers == NULL) {
786
 
                Py_DECREF(self);
787
 
                PyErr_NoMemory();
788
 
                return NULL;
789
 
            }
790
 
        } else {
791
 
            self->backpointers = NULL;
 
755
        self->backpointers = (Py_ssize_t *)malloc(sizeof(Py_ssize_t) * self->bsize * 4);
 
756
        if (self->backpointers == NULL) {
 
757
            Py_DECREF(self);
 
758
            return NULL;
792
759
        }
793
760
 
794
761
    }
802
769
{
803
770
    free(self->backpointers);
804
771
    free(self->hashtable.table);
805
 
    delete_lines(self->b, self->bsize);
806
 
    delete_lines(self->a, self->asize);
 
772
    free(self->b);
 
773
    free(self->a);
807
774
    self->ob_type->tp_free((PyObject *)self);
808
775
}
809
776
 
831
798
    struct matching_blocks matches;
832
799
 
833
800
    matches.count = 0;
834
 
    if (self->bsize > 0) {
835
 
        matches.matches = (struct matching_block *)
836
 
            guarded_malloc(sizeof(struct matching_block) * self->bsize);
837
 
        if (matches.matches == NULL)
838
 
            return PyErr_NoMemory();
839
 
    } else
840
 
        matches.matches = NULL;
 
801
    matches.matches = (struct matching_block *)malloc(sizeof(struct matching_block) * self->bsize);
 
802
    if (matches.matches == NULL)
 
803
        return PyErr_NoMemory();
841
804
 
842
805
    res = recurse_matches(&matches, &self->hashtable, self->backpointers,
843
806
                          self->a, self->b, 0, 0,
923
886
    struct matching_blocks matches;
924
887
 
925
888
    matches.count = 0;
926
 
    matches.matches = (struct matching_block *)guarded_malloc(sizeof(struct matching_block) * (self->bsize + 1));
 
889
    matches.matches = (struct matching_block *)malloc(sizeof(struct matching_block) * (self->bsize + 1));
927
890
    if (matches.matches == NULL)
928
891
        return PyErr_NoMemory();
929
892
 
1036
999
        return NULL;
1037
1000
 
1038
1001
    matches.count = 0;
1039
 
    matches.matches = (struct matching_block *)guarded_malloc(sizeof(struct matching_block) * (self->bsize + 1));
 
1002
    matches.matches = (struct matching_block *)malloc(sizeof(struct matching_block) * (self->bsize + 1));
1040
1003
    if (matches.matches == NULL)
1041
1004
        return PyErr_NoMemory();
1042
1005
 
1054
1017
    matches.count++;
1055
1018
 
1056
1019
    ncodes = 0;
1057
 
    codes = (struct opcode *)guarded_malloc(sizeof(struct opcode) * matches.count * 2);
 
1020
    codes = (struct opcode *)malloc(sizeof(struct opcode) * matches.count * 2);
1058
1021
    if (codes == NULL) {
1059
1022
        free(matches.matches);
1060
1023
        return PyErr_NoMemory();
1275
1238
    PyModule_AddObject(m, "PatienceSequenceMatcher_c",
1276
1239
                       (PyObject *)&PatienceSequenceMatcherType);
1277
1240
}
1278
 
 
1279
 
 
1280
 
/* vim: sw=4 et 
1281
 
 */