/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: 2007-11-30 23:18:15 UTC
  • mto: This revision was merged to the branch mainline in revision 3072.
  • Revision ID: john@arbash-meinel.com-20071130231815-0r6ce70307kmv28r
Use a Graph.heads() check to determine if the ancestries are compatible.
Whether we should do nothing because source is already ahead,
raise an exception because we have diverged,
or move forward because the new revision is a tip revision.

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,
70
70
 
71
71
 
72
72
struct line {
73
 
    long hash;         /* hash code of the string/object */
 
73
    int hash;          /* hash code of the string */
74
74
    Py_ssize_t next;   /* next line from the same equivalence class */
75
75
    Py_ssize_t equiv;  /* equivalence class */
76
 
    PyObject *data;
 
76
    Py_ssize_t len;
 
77
    const char *data;
77
78
};
78
79
 
79
80
 
150
151
static inline int
151
152
compare_lines(struct line *a, struct line *b)
152
153
{
153
 
    return ((a->hash != b->hash)
154
 
            || PyObject_Compare(a->data, b->data));
 
154
    return ((a->hash != b->hash) || (a->len != b->len) ||
 
155
            memcmp(a->data, b->data, a->len));
155
156
}
156
157
 
157
158
 
189
190
    while (hsize < bsize + 1)
190
191
        hsize *= 2;
191
192
 
192
 
    /* can't be 0 */
193
 
    hashtable = (struct bucket *) guarded_malloc(sizeof(struct bucket) * hsize);
 
193
    hashtable = (struct bucket *)malloc(sizeof(struct bucket) * hsize);
194
194
    if (hashtable == NULL) {
195
195
        PyErr_NoMemory();
196
196
        return 0;
305
305
        apos = SENTINEL;
306
306
        /* loop through all lines in the linked list */
307
307
        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 */
 
308
            /* the index is lower than alo, the the next line */
309
309
            if (i < alo) {
310
310
                h[equiv].a_pos = i;
311
311
                continue;
326
326
        /* check for duplicates of this line in lines_b[blo:bhi] */
327
327
        /* loop through all lines in the linked list */
328
328
        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 */
 
329
            /* the index is lower than blo, the the next line */
330
330
            if (i < blo) {
331
331
                h[equiv].b_pos = i;
332
332
                continue;
467
467
    last_a_pos = alo - 1;
468
468
    last_b_pos = blo - 1;
469
469
 
470
 
    lcs = (struct matching_line *)guarded_malloc(sizeof(struct matching_line) * (bhi - blo));
 
470
    lcs = (struct matching_line *)malloc(sizeof(struct matching_line) * (bhi - blo));
471
471
    if (lcs == NULL)
472
472
        return 0;
473
473
 
542
542
}
543
543
 
544
544
 
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
545
static Py_ssize_t
558
546
load_lines(PyObject *orig, struct line **lines)
559
547
{
560
 
    Py_ssize_t size, i;
 
548
    Py_ssize_t size, i, j;
 
549
    int h;
 
550
    char *p;
561
551
    struct line *line;
562
552
    PyObject *seq, *item;
563
553
 
572
562
        return 0;
573
563
    }
574
564
 
575
 
    /* Allocate a memory block for line data, initialized to 0 */
576
 
    line = *lines = (struct line *)calloc(size, sizeof(struct line));
 
565
    line = *lines = (struct line *)malloc(sizeof(struct line) * size);
577
566
    if (line == NULL) {
578
567
        PyErr_NoMemory();
579
568
        Py_DECREF(seq);
582
571
 
583
572
    for (i = 0; i < size; i++) {
584
573
        item = PySequence_Fast_GET_ITEM(seq, i);
585
 
        Py_INCREF(item);
586
 
        line->data = item;
587
 
        line->hash = PyObject_Hash(item);
588
 
        if (line->hash == (-1)) {
589
 
            /* Propogate the hash exception */
590
 
            size = -1;
591
 
            goto cleanup;
 
574
        if (!PyString_Check(item)){
 
575
            PyErr_Format(PyExc_TypeError,
 
576
                     "sequence item %zd: expected string,"
 
577
                     " %.80s found",
 
578
                     i, item->ob_type->tp_name);
 
579
            Py_DECREF(seq);
 
580
            return -1;
592
581
        }
 
582
        line->len = PyString_GET_SIZE(item);
 
583
        line->data = p = PyString_AS_STRING(item);
 
584
        /* 'djb2' hash. This gives us a nice compromise between fast hash
 
585
            function and a hash with less collisions. The algorithm doesn't
 
586
            use the hash for actual lookups, only for building the table
 
587
            so a better hash function wouldn't bring us much benefit, but
 
588
            would make this loading code slower. */
 
589
        h = 5381;
 
590
        for (j = 0; j < line->len; j++)
 
591
            h = ((h << 5) + h) + *p++;
 
592
        line->hash = h;
593
593
        line->next = SENTINEL;
594
594
        line++;
595
595
    }
596
596
 
597
 
    cleanup:
598
597
    Py_DECREF(seq);
599
 
    if (size == -1) {
600
 
        /* Error -- cleanup unused object references */
601
 
        delete_lines(*lines, i);
602
 
        *lines = NULL;
603
 
    }
604
598
    return size;
605
599
}
606
600
 
627
621
    if (!equate_lines(&hashtable, a, b, asize, bsize))
628
622
        goto error;
629
623
 
630
 
    if (bsize > 0) {
631
 
        matches = (struct matching_line *)guarded_malloc(sizeof(struct matching_line) * bsize);
632
 
        if (matches == NULL)
633
 
            goto error;
 
624
    matches = (struct matching_line *)malloc(sizeof(struct matching_line) * bsize);
 
625
    if (matches == NULL)
 
626
        goto error;
634
627
 
635
 
        backpointers = (Py_ssize_t *)guarded_malloc(sizeof(Py_ssize_t) * bsize * 4);
636
 
        if (backpointers == NULL)
637
 
            goto error;
638
 
    }
 
628
    backpointers = (Py_ssize_t *)malloc(sizeof(Py_ssize_t) * bsize * 4);
 
629
    if (backpointers == NULL)
 
630
        goto error;
639
631
 
640
632
    nmatches = unique_lcs(matches, &hashtable, backpointers, a, b, 0, 0, asize, bsize);
641
633
 
655
647
    free(backpointers);
656
648
    free(matches);
657
649
    free(hashtable.table);
658
 
    delete_lines(b, bsize);
659
 
    delete_lines(a, asize);
 
650
    free(b);
 
651
    free(a);
660
652
    return res;
661
653
 
662
654
error:
663
655
    free(backpointers);
664
656
    free(matches);
665
657
    free(hashtable.table);
666
 
    delete_lines(b, bsize);
667
 
    delete_lines(a, asize);
 
658
    free(b);
 
659
    free(a);
668
660
    return NULL;
669
661
}
670
662
 
701
693
        goto error;
702
694
 
703
695
    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
 
    }
 
696
    matches.matches = (struct matching_block *)malloc(sizeof(struct matching_block) * bsize);
 
697
    if (matches.matches == NULL)
 
698
        goto error;
 
699
 
 
700
    backpointers = (Py_ssize_t *)malloc(sizeof(Py_ssize_t) * bsize * 4);
 
701
    if (backpointers == NULL)
 
702
        goto error;
717
703
 
718
704
    res = recurse_matches(&matches, &hashtable, backpointers,
719
705
                          a, b, alo, blo, ahi, bhi, maxrecursion);
739
725
    free(backpointers);
740
726
    free(matches.matches);
741
727
    free(hashtable.table);
742
 
    delete_lines(b, bsize);
743
 
    delete_lines(a, asize);
 
728
    free(b);
 
729
    free(a);
744
730
    Py_RETURN_NONE;
745
731
 
746
732
error:
747
733
    free(backpointers);
748
734
    free(matches.matches);
749
735
    free(hashtable.table);
750
 
    delete_lines(b, bsize);
751
 
    delete_lines(a, asize);
 
736
    free(b);
 
737
    free(a);
752
738
    return NULL;
753
739
}
754
740
 
780
766
            return NULL;
781
767
        }
782
768
 
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;
 
769
        self->backpointers = (Py_ssize_t *)malloc(sizeof(Py_ssize_t) * self->bsize * 4);
 
770
        if (self->backpointers == NULL) {
 
771
            Py_DECREF(self);
 
772
            return NULL;
792
773
        }
793
774
 
794
775
    }
802
783
{
803
784
    free(self->backpointers);
804
785
    free(self->hashtable.table);
805
 
    delete_lines(self->b, self->bsize);
806
 
    delete_lines(self->a, self->asize);
 
786
    free(self->b);
 
787
    free(self->a);
807
788
    self->ob_type->tp_free((PyObject *)self);
808
789
}
809
790
 
831
812
    struct matching_blocks matches;
832
813
 
833
814
    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;
 
815
    matches.matches = (struct matching_block *)malloc(sizeof(struct matching_block) * self->bsize);
 
816
    if (matches.matches == NULL)
 
817
        return PyErr_NoMemory();
841
818
 
842
819
    res = recurse_matches(&matches, &self->hashtable, self->backpointers,
843
820
                          self->a, self->b, 0, 0,
923
900
    struct matching_blocks matches;
924
901
 
925
902
    matches.count = 0;
926
 
    matches.matches = (struct matching_block *)guarded_malloc(sizeof(struct matching_block) * (self->bsize + 1));
 
903
    matches.matches = (struct matching_block *)malloc(sizeof(struct matching_block) * (self->bsize + 1));
927
904
    if (matches.matches == NULL)
928
905
        return PyErr_NoMemory();
929
906
 
1036
1013
        return NULL;
1037
1014
 
1038
1015
    matches.count = 0;
1039
 
    matches.matches = (struct matching_block *)guarded_malloc(sizeof(struct matching_block) * (self->bsize + 1));
 
1016
    matches.matches = (struct matching_block *)malloc(sizeof(struct matching_block) * (self->bsize + 1));
1040
1017
    if (matches.matches == NULL)
1041
1018
        return PyErr_NoMemory();
1042
1019
 
1054
1031
    matches.count++;
1055
1032
 
1056
1033
    ncodes = 0;
1057
 
    codes = (struct opcode *)guarded_malloc(sizeof(struct opcode) * matches.count * 2);
 
1034
    codes = (struct opcode *)malloc(sizeof(struct opcode) * matches.count * 2);
1058
1035
    if (codes == NULL) {
1059
1036
        free(matches.matches);
1060
1037
        return PyErr_NoMemory();
1275
1252
    PyModule_AddObject(m, "PatienceSequenceMatcher_c",
1276
1253
                       (PyObject *)&PatienceSequenceMatcherType);
1277
1254
}
1278
 
 
1279
 
 
1280
 
/* vim: sw=4 et 
1281
 
 */