~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_patiencediff_c.c

• browse files at revision 3677.1.6
• compare with another revision
• download diff
• download tarball
• view history from revision 3677.1.6

• reverse the comparison (3677.1.6 to 6079)
• stop comparing with revision 6079

Show diffs side-by-side

added

removed

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,

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

 

627

626

    if (!equate_lines(&hashtable, a, b, asize, bsize))

628

627

        goto error;

629

628

 

630

 

    if (bsize > 0) {

631

 

        matches = (struct matching_line *)guarded_malloc(sizeof(struct matching_line) * bsize);

632

 

        if (matches == NULL)

633

 

            goto error;

 

629

    matches = (struct matching_line *)malloc(sizeof(struct matching_line) * bsize);

 

630

    if (matches == NULL)

 

631

        goto error;

634

632

 

635

 

        backpointers = (Py_ssize_t *)guarded_malloc(sizeof(Py_ssize_t) * bsize * 4);

636

 

        if (backpointers == NULL)

637

 

            goto error;

638

 

    }

 

633

    backpointers = (Py_ssize_t *)malloc(sizeof(Py_ssize_t) * bsize * 4);

 

634

    if (backpointers == NULL)

 

635

        goto error;

639

636

 

640

637

    nmatches = unique_lcs(matches, &hashtable, backpointers, a, b, 0, 0, asize, bsize);

641

638

 

701

698

        goto error;

702

699

 

703

700

    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

 

    }

 

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;

717

708

 

718

709

    res = recurse_matches(&matches, &hashtable, backpointers,

719

710

                          a, b, alo, blo, ahi, bhi, maxrecursion);

780

771

            return NULL;

781

772

        }

782

773

 

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;

 

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;

792

778

        }

793

779

 

794

780

    }

831

817

    struct matching_blocks matches;

832

818

 

833

819

    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;

 

820

    matches.matches = (struct matching_block *)malloc(sizeof(struct matching_block) * self->bsize);

 

821

    if (matches.matches == NULL)

 

822

        return PyErr_NoMemory();

841

823

 

842

824

    res = recurse_matches(&matches, &self->hashtable, self->backpointers,

843

825

                          self->a, self->b, 0, 0,

923

905

    struct matching_blocks matches;

924

906

 

925

907

    matches.count = 0;

926

 

    matches.matches = (struct matching_block *)guarded_malloc(sizeof(struct matching_block) * (self->bsize + 1));

 

908

    matches.matches = (struct matching_block *)malloc(sizeof(struct matching_block) * (self->bsize + 1));

927

909

    if (matches.matches == NULL)

928

910

        return PyErr_NoMemory();

929

911

 

1036

1018

        return NULL;

1037

1019

 

1038

1020

    matches.count = 0;

1039

 

    matches.matches = (struct matching_block *)guarded_malloc(sizeof(struct matching_block) * (self->bsize + 1));

 

1021

    matches.matches = (struct matching_block *)malloc(sizeof(struct matching_block) * (self->bsize + 1));

1040

1022

    if (matches.matches == NULL)

1041

1023

        return PyErr_NoMemory();

1042

1024

 

1054

1036

    matches.count++;

1055

1037

 

1056

1038

    ncodes = 0;

1057

 

    codes = (struct opcode *)guarded_malloc(sizeof(struct opcode) * matches.count * 2);

 

1039

    codes = (struct opcode *)malloc(sizeof(struct opcode) * matches.count * 2);

1058

1040

    if (codes == NULL) {

1059

1041

        free(matches.matches);

1060

1042

        return PyErr_NoMemory();

1275

1257

    PyModule_AddObject(m, "PatienceSequenceMatcher_c",

1276

1258

                       (PyObject *)&PatienceSequenceMatcherType);

1277

1259

}

1278

 

 

1279

 

 

1280

 

/* vim: sw=4 et 

1281

 

 */

• Older »

Loggerhead is a web-based interface for Breezy
Version: 2.0.1