← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_patiencediff_c.c

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2010-03-11 13:47:06 UTC
  • mfrom: (5051.3.16 use-branch-open)
  • Revision ID: pqm@pqm.ubuntu.com-20100311134706-kaerqhx3lf7xn6rh
(Jelmer) Pass colocated branch names further down the call stack.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_patiencediff_c.c
1
1
/*
2
 
 Copyright (C) 2007 Canonical Ltd
 
2
 Copyright (C) 2007, 2010 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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
16
 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 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
 
 
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
 
30
#include "python-compat.h"
37
31
 
38
32
 
39
33
#if defined(__GNUC__)
52
46
#define SENTINEL -1
53
47
 
54
48
 
 
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
 
    hashtable = (struct bucket *)malloc(sizeof(struct bucket) * hsize);
 
192
    /* can't be 0 */
 
193
    hashtable = (struct bucket *) guarded_malloc(sizeof(struct bucket) * hsize);
193
194
    if (hashtable == NULL) {
194
195
        PyErr_NoMemory();
195
196
        return 0;
304
305
        apos = SENTINEL;
305
306
        /* loop through all lines in the linked list */
306
307
        for (i = h[equiv].a_pos; i != SENTINEL; i = lines_a[i].next) {
307
 
            /* the index is lower than alo, the the next line */
 
308
            /* the index is lower than alo, continue to the next line */
308
309
            if (i < alo) {
309
310
                h[equiv].a_pos = i;
310
311
                continue;
325
326
        /* check for duplicates of this line in lines_b[blo:bhi] */
326
327
        /* loop through all lines in the linked list */
327
328
        for (i = h[equiv].b_pos; i != SENTINEL; i = lines_b[i].next) {
328
 
            /* the index is lower than blo, the the next line */
 
329
            /* the index is lower than blo, continue to the next line */
329
330
            if (i < blo) {
330
331
                h[equiv].b_pos = i;
331
332
                continue;
466
467
    last_a_pos = alo - 1;
467
468
    last_b_pos = blo - 1;
468
469
 
469
 
    lcs = (struct matching_line *)malloc(sizeof(struct matching_line) * (bhi - blo));
 
470
    lcs = (struct matching_line *)guarded_malloc(sizeof(struct matching_line) * (bhi - blo));
470
471
    if (lcs == NULL)
471
472
        return 0;
472
473
 
626
627
    if (!equate_lines(&hashtable, a, b, asize, bsize))
627
628
        goto error;
628
629
 
629
 
    matches = (struct matching_line *)malloc(sizeof(struct matching_line) * bsize);
630
 
    if (matches == NULL)
631
 
        goto error;
 
630
    if (bsize > 0) {
 
631
        matches = (struct matching_line *)guarded_malloc(sizeof(struct matching_line) * bsize);
 
632
        if (matches == NULL)
 
633
            goto error;
632
634
 
633
 
    backpointers = (Py_ssize_t *)malloc(sizeof(Py_ssize_t) * bsize * 4);
634
 
    if (backpointers == NULL)
635
 
        goto error;
 
635
        backpointers = (Py_ssize_t *)guarded_malloc(sizeof(Py_ssize_t) * bsize * 4);
 
636
        if (backpointers == NULL)
 
637
            goto error;
 
638
    }
636
639
 
637
640
    nmatches = unique_lcs(matches, &hashtable, backpointers, a, b, 0, 0, asize, bsize);
638
641
 
698
701
        goto error;
699
702
 
700
703
    matches.count = 0;
701
 
    matches.matches = (struct matching_block *)malloc(sizeof(struct matching_block) * bsize);
702
 
    if (matches.matches == NULL)
703
 
        goto error;
704
 
 
705
 
    backpointers = (Py_ssize_t *)malloc(sizeof(Py_ssize_t) * bsize * 4);
706
 
    if (backpointers == NULL)
707
 
        goto error;
 
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
    }
708
717
 
709
718
    res = recurse_matches(&matches, &hashtable, backpointers,
710
719
                          a, b, alo, blo, ahi, bhi, maxrecursion);
771
780
            return NULL;
772
781
        }
773
782
 
774
 
        self->backpointers = (Py_ssize_t *)malloc(sizeof(Py_ssize_t) * self->bsize * 4);
775
 
        if (self->backpointers == NULL) {
776
 
            Py_DECREF(self);
777
 
            return NULL;
 
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;
778
792
        }
779
793
 
780
794
    }
817
831
    struct matching_blocks matches;
818
832
 
819
833
    matches.count = 0;
820
 
    matches.matches = (struct matching_block *)malloc(sizeof(struct matching_block) * self->bsize);
821
 
    if (matches.matches == NULL)
822
 
        return PyErr_NoMemory();
 
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;
823
841
 
824
842
    res = recurse_matches(&matches, &self->hashtable, self->backpointers,
825
843
                          self->a, self->b, 0, 0,
905
923
    struct matching_blocks matches;
906
924
 
907
925
    matches.count = 0;
908
 
    matches.matches = (struct matching_block *)malloc(sizeof(struct matching_block) * (self->bsize + 1));
 
926
    matches.matches = (struct matching_block *)guarded_malloc(sizeof(struct matching_block) * (self->bsize + 1));
909
927
    if (matches.matches == NULL)
910
928
        return PyErr_NoMemory();
911
929
 
1018
1036
        return NULL;
1019
1037
 
1020
1038
    matches.count = 0;
1021
 
    matches.matches = (struct matching_block *)malloc(sizeof(struct matching_block) * (self->bsize + 1));
 
1039
    matches.matches = (struct matching_block *)guarded_malloc(sizeof(struct matching_block) * (self->bsize + 1));
1022
1040
    if (matches.matches == NULL)
1023
1041
        return PyErr_NoMemory();
1024
1042
 
1036
1054
    matches.count++;
1037
1055
 
1038
1056
    ncodes = 0;
1039
 
    codes = (struct opcode *)malloc(sizeof(struct opcode) * matches.count * 2);
 
1057
    codes = (struct opcode *)guarded_malloc(sizeof(struct opcode) * matches.count * 2);
1040
1058
    if (codes == NULL) {
1041
1059
        free(matches.matches);
1042
1060
        return PyErr_NoMemory();
1257
1275
    PyModule_AddObject(m, "PatienceSequenceMatcher_c",
1258
1276
                       (PyObject *)&PatienceSequenceMatcherType);
1259
1277
}
 
1278
 
 
1279
 
 
1280
/* vim: sw=4 et 
 
1281
 */