← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_patiencediff_c.c

  • Committer: Ian Clatworthy
  • Date: 2007-11-28 00:18:10 UTC
  • mto: (3054.1.1 ianc-integration)
  • mto: This revision was merged to the branch mainline in revision 3055.
  • Revision ID: ian.clatworthy@internode.on.net-20071128001810-978qqnjpd12u4we2
change Makefile to support tutorials

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.launchpad.net/bzr/+bug/511267> and
51
 
 * <https://bugs.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
 
 */