← 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: 2007-11-04 18:51:39 UTC
  • mfrom: (2961.1.1 trunk)
  • Revision ID: pqm@pqm.ubuntu.com-20071104185139-kaio3sneodg2kp71
Authentication ring implementation (read-only)

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_patiencediff_c.c
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
 
541
542
}
542
543
 
543
544
 
544
 
static void
545
 
delete_lines(struct line *lines, Py_ssize_t size)
546
 
{
547
 
    struct line *line = lines;
548
 
    while (size-- > 0) {
549
 
        Py_XDECREF(line->data);
550
 
        line++;
551
 
    }
552
 
    free(lines);
553
 
}
554
 
 
555
 
 
556
545
static Py_ssize_t
557
546
load_lines(PyObject *orig, struct line **lines)
558
547
{
559
 
    Py_ssize_t size, i;
 
548
    Py_ssize_t size, i, j;
 
549
    int h;
 
550
    char *p;
560
551
    struct line *line;
561
552
    PyObject *seq, *item;
562
553
 
571
562
        return 0;
572
563
    }
573
564
 
574
 
    /* Allocate a memory block for line data, initialized to 0 */
575
 
    line = *lines = (struct line *)calloc(size, sizeof(struct line));
 
565
    line = *lines = (struct line *)malloc(sizeof(struct line) * size);
576
566
    if (line == NULL) {
577
567
        PyErr_NoMemory();
578
568
        Py_DECREF(seq);
581
571
 
582
572
    for (i = 0; i < size; i++) {
583
573
        item = PySequence_Fast_GET_ITEM(seq, i);
584
 
        Py_INCREF(item);
585
 
        line->data = item;
586
 
        line->hash = PyObject_Hash(item);
587
 
        if (line->hash == (-1)) {
588
 
            /* Propogate the hash exception */
589
 
            size = -1;
590
 
            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;
591
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;
592
593
        line->next = SENTINEL;
593
594
        line++;
594
595
    }
595
596
 
596
 
    cleanup:
597
597
    Py_DECREF(seq);
598
 
    if (size == -1) {
599
 
        /* Error -- cleanup unused object references */
600
 
        delete_lines(*lines, i);
601
 
        *lines = NULL;
602
 
    }
603
598
    return size;
604
599
}
605
600
 
652
647
    free(backpointers);
653
648
    free(matches);
654
649
    free(hashtable.table);
655
 
    delete_lines(b, bsize);
656
 
    delete_lines(a, asize);
 
650
    free(b);
 
651
    free(a);
657
652
    return res;
658
653
 
659
654
error:
660
655
    free(backpointers);
661
656
    free(matches);
662
657
    free(hashtable.table);
663
 
    delete_lines(b, bsize);
664
 
    delete_lines(a, asize);
 
658
    free(b);
 
659
    free(a);
665
660
    return NULL;
666
661
}
667
662
 
730
725
    free(backpointers);
731
726
    free(matches.matches);
732
727
    free(hashtable.table);
733
 
    delete_lines(b, bsize);
734
 
    delete_lines(a, asize);
 
728
    free(b);
 
729
    free(a);
735
730
    Py_RETURN_NONE;
736
731
 
737
732
error:
738
733
    free(backpointers);
739
734
    free(matches.matches);
740
735
    free(hashtable.table);
741
 
    delete_lines(b, bsize);
742
 
    delete_lines(a, asize);
 
736
    free(b);
 
737
    free(a);
743
738
    return NULL;
744
739
}
745
740
 
788
783
{
789
784
    free(self->backpointers);
790
785
    free(self->hashtable.table);
791
 
    delete_lines(self->b, self->bsize);
792
 
    delete_lines(self->a, self->asize);
 
786
    free(self->b);
 
787
    free(self->a);
793
788
    self->ob_type->tp_free((PyObject *)self);
794
789
}
795
790