Mercurial > hg-stable
annotate mercurial/bdiff.c @ 29323:d29cb5e735e9 stable
bdiff: remove effectively dead code
Now that we extend matches backwards in the inner loop, the final
adjustment has no effect.
(A similar extension for the forward direction is trickier and has
less benefit.)
author | Matt Mackall <mpm@selenic.com> |
---|---|
date | Thu, 02 Jun 2016 17:11:32 -0500 |
parents | 66dbdd3cc2b9 |
children | 284d742e5611 |
rev | line source |
---|---|
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
1 /* |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
2 bdiff.c - efficient binary diff extension for Mercurial |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
3 |
2859 | 4 Copyright 2005, 2006 Matt Mackall <mpm@selenic.com> |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
5 |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
6 This software may be used and distributed according to the terms of |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
7 the GNU General Public License, incorporated herein by reference. |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
8 |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
9 Based roughly on Python difflib |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
10 */ |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
11 |
16749
eab8ca175262
bdiff: use Py_ssize_t instead of int
Adrian Buehlmann <adrian@cadifra.com>
parents:
16477
diff
changeset
|
12 #define PY_SSIZE_T_CLEAN |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
13 #include <Python.h> |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
14 #include <stdlib.h> |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
15 #include <string.h> |
5341
458acf92b49e
bdiff: use INT_MAX to avoid some inner loop comparisons
Matt Mackall <mpm@selenic.com>
parents:
5340
diff
changeset
|
16 #include <limits.h> |
867
0cd2ee61b10a
Allow Mercurial to build on HP-UX 11
tksoh@users.sourceforge.net
parents:
839
diff
changeset
|
17 |
11364
0044193a1c45
bdiff.c: Added support for py3k.
Renato Cunha <renatoc@gmail.com>
parents:
10500
diff
changeset
|
18 #include "util.h" |
0044193a1c45
bdiff.c: Added support for py3k.
Renato Cunha <renatoc@gmail.com>
parents:
10500
diff
changeset
|
19 |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
20 struct line { |
16749
eab8ca175262
bdiff: use Py_ssize_t instead of int
Adrian Buehlmann <adrian@cadifra.com>
parents:
16477
diff
changeset
|
21 int hash, n, e; |
eab8ca175262
bdiff: use Py_ssize_t instead of int
Adrian Buehlmann <adrian@cadifra.com>
parents:
16477
diff
changeset
|
22 Py_ssize_t len; |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
23 const char *l; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
24 }; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
25 |
474 | 26 struct pos { |
27 int pos, len; | |
28 }; | |
29 | |
13089
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
30 struct hunk; |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
31 struct hunk { |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
32 int a1, a2, b1, b2; |
13089
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
33 struct hunk *next; |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
34 }; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
35 |
16749
eab8ca175262
bdiff: use Py_ssize_t instead of int
Adrian Buehlmann <adrian@cadifra.com>
parents:
16477
diff
changeset
|
36 static int splitlines(const char *a, Py_ssize_t len, struct line **lr) |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
37 { |
13732
afe9269dccec
bdiff.c: rename all variables which hold a hash value to "hash"
Markus F.X.J. Oberhumer <markus@oberhumer.com>
parents:
13731
diff
changeset
|
38 unsigned hash; |
13731
5d0cdf4ec338
bdiff.c: use unsigned arithmetic for hash computation
Markus F.X.J. Oberhumer <markus@oberhumer.com>
parents:
13730
diff
changeset
|
39 int i; |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
40 const char *p, *b = a; |
5340
5737845fd974
bdiff: simple splitlines optimization
Christoph Spiel <cspiel@freenet.de>
parents:
5339
diff
changeset
|
41 const char * const plast = a + len - 1; |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
42 struct line *l; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
43 |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
44 /* count the lines */ |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
45 i = 1; /* extra line for sentinel */ |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
46 for (p = a; p < a + len; p++) |
5340
5737845fd974
bdiff: simple splitlines optimization
Christoph Spiel <cspiel@freenet.de>
parents:
5339
diff
changeset
|
47 if (*p == '\n' || p == plast) |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
48 i++; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
49 |
1978
10606ee61107
do proper typecasting on malloc() and calloc() calls
TK Soh <teekaysoh@yahoo.com>
parents:
1759
diff
changeset
|
50 *lr = l = (struct line *)malloc(sizeof(struct line) * i); |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
51 if (!l) |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
52 return -1; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
53 |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
54 /* build the line array and calculate hashes */ |
13732
afe9269dccec
bdiff.c: rename all variables which hold a hash value to "hash"
Markus F.X.J. Oberhumer <markus@oberhumer.com>
parents:
13731
diff
changeset
|
55 hash = 0; |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
56 for (p = a; p < a + len; p++) { |
5342 | 57 /* Leonid Yuriev's hash */ |
13732
afe9269dccec
bdiff.c: rename all variables which hold a hash value to "hash"
Markus F.X.J. Oberhumer <markus@oberhumer.com>
parents:
13731
diff
changeset
|
58 hash = (hash * 1664525) + (unsigned char)*p + 1013904223; |
5342 | 59 |
5340
5737845fd974
bdiff: simple splitlines optimization
Christoph Spiel <cspiel@freenet.de>
parents:
5339
diff
changeset
|
60 if (*p == '\n' || p == plast) { |
13732
afe9269dccec
bdiff.c: rename all variables which hold a hash value to "hash"
Markus F.X.J. Oberhumer <markus@oberhumer.com>
parents:
13731
diff
changeset
|
61 l->hash = hash; |
afe9269dccec
bdiff.c: rename all variables which hold a hash value to "hash"
Markus F.X.J. Oberhumer <markus@oberhumer.com>
parents:
13731
diff
changeset
|
62 hash = 0; |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
63 l->len = p - b + 1; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
64 l->l = b; |
5341
458acf92b49e
bdiff: use INT_MAX to avoid some inner loop comparisons
Matt Mackall <mpm@selenic.com>
parents:
5340
diff
changeset
|
65 l->n = INT_MAX; |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
66 l++; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
67 b = p + 1; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
68 } |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
69 } |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
70 |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
71 /* set up a sentinel */ |
13732
afe9269dccec
bdiff.c: rename all variables which hold a hash value to "hash"
Markus F.X.J. Oberhumer <markus@oberhumer.com>
parents:
13731
diff
changeset
|
72 l->hash = 0; |
13731
5d0cdf4ec338
bdiff.c: use unsigned arithmetic for hash computation
Markus F.X.J. Oberhumer <markus@oberhumer.com>
parents:
13730
diff
changeset
|
73 l->len = 0; |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
74 l->l = a + len; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
75 return i - 1; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
76 } |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
77 |
13729
4a9c09239ba1
bdiff.c: make all local functions static
Markus F.X.J. Oberhumer <markus@oberhumer.com>
parents:
13302
diff
changeset
|
78 static inline int cmp(struct line *a, struct line *b) |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
79 { |
13732
afe9269dccec
bdiff.c: rename all variables which hold a hash value to "hash"
Markus F.X.J. Oberhumer <markus@oberhumer.com>
parents:
13731
diff
changeset
|
80 return a->hash != b->hash || a->len != b->len || memcmp(a->l, b->l, a->len); |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
81 } |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
82 |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
83 static int equatelines(struct line *a, int an, struct line *b, int bn) |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
84 { |
5452
82b4ff3abbcd
bdiff: tweaks for large files
Matt Mackall <mpm@selenic.com>
parents:
5342
diff
changeset
|
85 int i, j, buckets = 1, t, scale; |
82b4ff3abbcd
bdiff: tweaks for large files
Matt Mackall <mpm@selenic.com>
parents:
5342
diff
changeset
|
86 struct pos *h = NULL; |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
87 |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
88 /* build a hash table of the next highest power of 2 */ |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
89 while (buckets < bn + 1) |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
90 buckets *= 2; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
91 |
5339
058e93c3d07d
I have spotted the biggest bottleneck in "bdiff.c". Actually it was
Christoph Spiel <cspiel@freenet.de>
parents:
4134
diff
changeset
|
92 /* try to allocate a large hash table to avoid collisions */ |
5452
82b4ff3abbcd
bdiff: tweaks for large files
Matt Mackall <mpm@selenic.com>
parents:
5342
diff
changeset
|
93 for (scale = 4; scale; scale /= 2) { |
5339
058e93c3d07d
I have spotted the biggest bottleneck in "bdiff.c". Actually it was
Christoph Spiel <cspiel@freenet.de>
parents:
4134
diff
changeset
|
94 h = (struct pos *)malloc(scale * buckets * sizeof(struct pos)); |
5452
82b4ff3abbcd
bdiff: tweaks for large files
Matt Mackall <mpm@selenic.com>
parents:
5342
diff
changeset
|
95 if (h) |
82b4ff3abbcd
bdiff: tweaks for large files
Matt Mackall <mpm@selenic.com>
parents:
5342
diff
changeset
|
96 break; |
82b4ff3abbcd
bdiff: tweaks for large files
Matt Mackall <mpm@selenic.com>
parents:
5342
diff
changeset
|
97 } |
5339
058e93c3d07d
I have spotted the biggest bottleneck in "bdiff.c". Actually it was
Christoph Spiel <cspiel@freenet.de>
parents:
4134
diff
changeset
|
98 |
474 | 99 if (!h) |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
100 return 0; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
101 |
5339
058e93c3d07d
I have spotted the biggest bottleneck in "bdiff.c". Actually it was
Christoph Spiel <cspiel@freenet.de>
parents:
4134
diff
changeset
|
102 buckets = buckets * scale - 1; |
058e93c3d07d
I have spotted the biggest bottleneck in "bdiff.c". Actually it was
Christoph Spiel <cspiel@freenet.de>
parents:
4134
diff
changeset
|
103 |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
104 /* clear the hash table */ |
474 | 105 for (i = 0; i <= buckets; i++) { |
29013
9a8363d23419
bdiff: deal better with duplicate lines
Matt Mackall <mpm@selenic.com>
parents:
29012
diff
changeset
|
106 h[i].pos = -1; |
474 | 107 h[i].len = 0; |
108 } | |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
109 |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
110 /* add lines to the hash table chains */ |
29013
9a8363d23419
bdiff: deal better with duplicate lines
Matt Mackall <mpm@selenic.com>
parents:
29012
diff
changeset
|
111 for (i = 0; i < bn; i++) { |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
112 /* find the equivalence class */ |
29013
9a8363d23419
bdiff: deal better with duplicate lines
Matt Mackall <mpm@selenic.com>
parents:
29012
diff
changeset
|
113 for (j = b[i].hash & buckets; h[j].pos != -1; |
474 | 114 j = (j + 1) & buckets) |
115 if (!cmp(b + i, b + h[j].pos)) | |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
116 break; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
117 |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
118 /* add to the head of the equivalence class */ |
474 | 119 b[i].n = h[j].pos; |
433
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
120 b[i].e = j; |
474 | 121 h[j].pos = i; |
122 h[j].len++; /* keep track of popularity */ | |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
123 } |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
124 |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
125 /* compute popularity threshold */ |
9534
8e202431d620
bdiff: gradually enable the popularity hack
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
8858
diff
changeset
|
126 t = (bn >= 31000) ? bn / 1000 : 1000000 / (bn + 1); |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
127 |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
128 /* match items in a to their equivalence class in b */ |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
129 for (i = 0; i < an; i++) { |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
130 /* find the equivalence class */ |
29013
9a8363d23419
bdiff: deal better with duplicate lines
Matt Mackall <mpm@selenic.com>
parents:
29012
diff
changeset
|
131 for (j = a[i].hash & buckets; h[j].pos != -1; |
474 | 132 j = (j + 1) & buckets) |
133 if (!cmp(a + i, b + h[j].pos)) | |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
134 break; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
135 |
433
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
136 a[i].e = j; /* use equivalence class for quick compare */ |
1542
8e80eefb3de6
made C src formatting more consistent
twaldmann@thinkmo.de
parents:
1397
diff
changeset
|
137 if (h[j].len <= t) |
474 | 138 a[i].n = h[j].pos; /* point to head of match list */ |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
139 else |
29013
9a8363d23419
bdiff: deal better with duplicate lines
Matt Mackall <mpm@selenic.com>
parents:
29012
diff
changeset
|
140 a[i].n = -1; /* too popular */ |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
141 } |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
142 |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
143 /* discard hash tables */ |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
144 free(h); |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
145 return 1; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
146 } |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
147 |
474 | 148 static int longest_match(struct line *a, struct line *b, struct pos *pos, |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
149 int a1, int a2, int b1, int b2, int *omi, int *omj) |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
150 { |
29323
d29cb5e735e9
bdiff: remove effectively dead code
Matt Mackall <mpm@selenic.com>
parents:
29322
diff
changeset
|
151 int mi = a1, mj = b1, mk = 0, i, j, k, half; |
29015
87d4a6c5567e
bdiff: further restrain potential quadratic performance
Matt Mackall <mpm@selenic.com>
parents:
29014
diff
changeset
|
152 |
87d4a6c5567e
bdiff: further restrain potential quadratic performance
Matt Mackall <mpm@selenic.com>
parents:
29014
diff
changeset
|
153 /* window our search on large regions to better bound |
87d4a6c5567e
bdiff: further restrain potential quadratic performance
Matt Mackall <mpm@selenic.com>
parents:
29014
diff
changeset
|
154 worst-case performance. by choosing a window at the end, we |
87d4a6c5567e
bdiff: further restrain potential quadratic performance
Matt Mackall <mpm@selenic.com>
parents:
29014
diff
changeset
|
155 reduce skipping overhead on the b chains. */ |
87d4a6c5567e
bdiff: further restrain potential quadratic performance
Matt Mackall <mpm@selenic.com>
parents:
29014
diff
changeset
|
156 if (a2 - a1 > 30000) |
87d4a6c5567e
bdiff: further restrain potential quadratic performance
Matt Mackall <mpm@selenic.com>
parents:
29014
diff
changeset
|
157 a1 = a2 - 30000; |
87d4a6c5567e
bdiff: further restrain potential quadratic performance
Matt Mackall <mpm@selenic.com>
parents:
29014
diff
changeset
|
158 |
87d4a6c5567e
bdiff: further restrain potential quadratic performance
Matt Mackall <mpm@selenic.com>
parents:
29014
diff
changeset
|
159 half = (a1 + a2) / 2; |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
160 |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
161 for (i = a1; i < a2; i++) { |
29013
9a8363d23419
bdiff: deal better with duplicate lines
Matt Mackall <mpm@selenic.com>
parents:
29012
diff
changeset
|
162 /* skip all lines in b after the current block */ |
9a8363d23419
bdiff: deal better with duplicate lines
Matt Mackall <mpm@selenic.com>
parents:
29012
diff
changeset
|
163 for (j = a[i].n; j >= b2; j = b[j].n) |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
164 ; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
165 |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
166 /* loop through all lines match a[i] in b */ |
29013
9a8363d23419
bdiff: deal better with duplicate lines
Matt Mackall <mpm@selenic.com>
parents:
29012
diff
changeset
|
167 for (; j >= b1; j = b[j].n) { |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
168 /* does this extend an earlier match? */ |
29322
66dbdd3cc2b9
bdiff: extend matches across popular lines
Matt Mackall <mpm@selenic.com>
parents:
29015
diff
changeset
|
169 for (k = 1; j - k >= b1 && i - k >= a1; k++) { |
66dbdd3cc2b9
bdiff: extend matches across popular lines
Matt Mackall <mpm@selenic.com>
parents:
29015
diff
changeset
|
170 /* reached an earlier match? */ |
66dbdd3cc2b9
bdiff: extend matches across popular lines
Matt Mackall <mpm@selenic.com>
parents:
29015
diff
changeset
|
171 if (pos[j - k].pos == i - k) { |
66dbdd3cc2b9
bdiff: extend matches across popular lines
Matt Mackall <mpm@selenic.com>
parents:
29015
diff
changeset
|
172 k += pos[j - k].len; |
66dbdd3cc2b9
bdiff: extend matches across popular lines
Matt Mackall <mpm@selenic.com>
parents:
29015
diff
changeset
|
173 break; |
66dbdd3cc2b9
bdiff: extend matches across popular lines
Matt Mackall <mpm@selenic.com>
parents:
29015
diff
changeset
|
174 } |
66dbdd3cc2b9
bdiff: extend matches across popular lines
Matt Mackall <mpm@selenic.com>
parents:
29015
diff
changeset
|
175 /* previous line mismatch? */ |
66dbdd3cc2b9
bdiff: extend matches across popular lines
Matt Mackall <mpm@selenic.com>
parents:
29015
diff
changeset
|
176 if (a[i - k].e != b[j - k].e) |
66dbdd3cc2b9
bdiff: extend matches across popular lines
Matt Mackall <mpm@selenic.com>
parents:
29015
diff
changeset
|
177 break; |
66dbdd3cc2b9
bdiff: extend matches across popular lines
Matt Mackall <mpm@selenic.com>
parents:
29015
diff
changeset
|
178 } |
66dbdd3cc2b9
bdiff: extend matches across popular lines
Matt Mackall <mpm@selenic.com>
parents:
29015
diff
changeset
|
179 |
474 | 180 pos[j].pos = i; |
181 pos[j].len = k; | |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
182 |
29014
f1ca249696ed
bdiff: balance recursion to avoid quadratic behavior (issue4704)
Matt Mackall <mpm@selenic.com>
parents:
29013
diff
changeset
|
183 /* best match so far? we prefer matches closer |
f1ca249696ed
bdiff: balance recursion to avoid quadratic behavior (issue4704)
Matt Mackall <mpm@selenic.com>
parents:
29013
diff
changeset
|
184 to the middle to balance recursion */ |
f1ca249696ed
bdiff: balance recursion to avoid quadratic behavior (issue4704)
Matt Mackall <mpm@selenic.com>
parents:
29013
diff
changeset
|
185 if (k > mk || (k == mk && (i <= mi || i < half))) { |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
186 mi = i; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
187 mj = j; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
188 mk = k; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
189 } |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
190 } |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
191 } |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
192 |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
193 if (mk) { |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
194 mi = mi - mk + 1; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
195 mj = mj - mk + 1; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
196 } |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
197 |
29323
d29cb5e735e9
bdiff: remove effectively dead code
Matt Mackall <mpm@selenic.com>
parents:
29322
diff
changeset
|
198 /* expand match to include subsequent popular lines */ |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
199 while (mi + mk < a2 && mj + mk < b2 && |
433
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
200 a[mi + mk].e == b[mj + mk].e) |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
201 mk++; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
202 |
29323
d29cb5e735e9
bdiff: remove effectively dead code
Matt Mackall <mpm@selenic.com>
parents:
29322
diff
changeset
|
203 *omi = mi; |
d29cb5e735e9
bdiff: remove effectively dead code
Matt Mackall <mpm@selenic.com>
parents:
29322
diff
changeset
|
204 *omj = mj; |
5341
458acf92b49e
bdiff: use INT_MAX to avoid some inner loop comparisons
Matt Mackall <mpm@selenic.com>
parents:
5340
diff
changeset
|
205 |
29323
d29cb5e735e9
bdiff: remove effectively dead code
Matt Mackall <mpm@selenic.com>
parents:
29322
diff
changeset
|
206 return mk; |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
207 } |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
208 |
13089
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
209 static struct hunk *recurse(struct line *a, struct line *b, struct pos *pos, |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
210 int a1, int a2, int b1, int b2, struct hunk *l) |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
211 { |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
212 int i, j, k; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
213 |
10500
e96597c8d0ea
bdiff: do not use recursion / avoid stackoverflow (issue1940)
Alistair Bell <alistair@bellsonline.com>
parents:
10282
diff
changeset
|
214 while (1) { |
e96597c8d0ea
bdiff: do not use recursion / avoid stackoverflow (issue1940)
Alistair Bell <alistair@bellsonline.com>
parents:
10282
diff
changeset
|
215 /* find the longest match in this chunk */ |
e96597c8d0ea
bdiff: do not use recursion / avoid stackoverflow (issue1940)
Alistair Bell <alistair@bellsonline.com>
parents:
10282
diff
changeset
|
216 k = longest_match(a, b, pos, a1, a2, b1, b2, &i, &j); |
e96597c8d0ea
bdiff: do not use recursion / avoid stackoverflow (issue1940)
Alistair Bell <alistair@bellsonline.com>
parents:
10282
diff
changeset
|
217 if (!k) |
13089
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
218 return l; |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
219 |
10500
e96597c8d0ea
bdiff: do not use recursion / avoid stackoverflow (issue1940)
Alistair Bell <alistair@bellsonline.com>
parents:
10282
diff
changeset
|
220 /* and recurse on the remaining chunks on either side */ |
13089
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
221 l = recurse(a, b, pos, a1, i, b1, j, l); |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
222 if (!l) |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
223 return NULL; |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
224 |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
225 l->next = (struct hunk *)malloc(sizeof(struct hunk)); |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
226 if (!l->next) |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
227 return NULL; |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
228 |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
229 l = l->next; |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
230 l->a1 = i; |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
231 l->a2 = i + k; |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
232 l->b1 = j; |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
233 l->b2 = j + k; |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
234 l->next = NULL; |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
235 |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
236 /* tail-recursion didn't happen, so do equivalent iteration */ |
10500
e96597c8d0ea
bdiff: do not use recursion / avoid stackoverflow (issue1940)
Alistair Bell <alistair@bellsonline.com>
parents:
10282
diff
changeset
|
237 a1 = i + k; |
e96597c8d0ea
bdiff: do not use recursion / avoid stackoverflow (issue1940)
Alistair Bell <alistair@bellsonline.com>
parents:
10282
diff
changeset
|
238 b1 = j + k; |
e96597c8d0ea
bdiff: do not use recursion / avoid stackoverflow (issue1940)
Alistair Bell <alistair@bellsonline.com>
parents:
10282
diff
changeset
|
239 } |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
240 } |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
241 |
13089
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
242 static int diff(struct line *a, int an, struct line *b, int bn, |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
243 struct hunk *base) |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
244 { |
7104
9514cbb6e4f6
bdiff: normalize the diff (issue1295)
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
7036
diff
changeset
|
245 struct hunk *curr; |
474 | 246 struct pos *pos; |
13089
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
247 int t, count = 0; |
433
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
248 |
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
249 /* allocate and fill arrays */ |
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
250 t = equatelines(a, an, b, bn); |
5571 | 251 pos = (struct pos *)calloc(bn ? bn : 1, sizeof(struct pos)); |
13089
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
252 |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
253 if (pos && t) { |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
254 /* generate the matching block list */ |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
255 |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
256 curr = recurse(a, b, pos, 0, an, 0, bn, base); |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
257 if (!curr) |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
258 return -1; |
433
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
259 |
13089
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
260 /* sentinel end hunk */ |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
261 curr->next = (struct hunk *)malloc(sizeof(struct hunk)); |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
262 if (!curr->next) |
13090
c73745762f33
bdiff: Fix bogus NULL return
Matt Mackall <mpm@selenic.com>
parents:
13089
diff
changeset
|
263 return -1; |
13089
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
264 curr = curr->next; |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
265 curr->a1 = curr->a2 = an; |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
266 curr->b1 = curr->b2 = bn; |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
267 curr->next = NULL; |
433
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
268 } |
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
269 |
474 | 270 free(pos); |
7104
9514cbb6e4f6
bdiff: normalize the diff (issue1295)
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
7036
diff
changeset
|
271 |
7625
930a2be7e875
bdiff: add comment about normalization
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
7189
diff
changeset
|
272 /* normalize the hunk list, try to push each hunk towards the end */ |
13089
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
273 for (curr = base->next; curr; curr = curr->next) { |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
274 struct hunk *next = curr->next; |
7104
9514cbb6e4f6
bdiff: normalize the diff (issue1295)
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
7036
diff
changeset
|
275 |
13089
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
276 if (!next) |
7104
9514cbb6e4f6
bdiff: normalize the diff (issue1295)
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
7036
diff
changeset
|
277 break; |
9514cbb6e4f6
bdiff: normalize the diff (issue1295)
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
7036
diff
changeset
|
278 |
29010
e868d8ee7c8f
bdiff: unify duplicate normalize loops
Matt Mackall <mpm@selenic.com>
parents:
19962
diff
changeset
|
279 if (curr->a2 == next->a1 || curr->b2 == next->b1) |
29011
8bcda4c76820
bdiff: fold in shift calculation in normalize
Matt Mackall <mpm@selenic.com>
parents:
29010
diff
changeset
|
280 while (curr->a2 < an && curr->b2 < bn |
29012
4bd67ae7d75a
bdiff: fix latent normalization bug
Matt Mackall <mpm@selenic.com>
parents:
29011
diff
changeset
|
281 && next->a1 < next->a2 |
4bd67ae7d75a
bdiff: fix latent normalization bug
Matt Mackall <mpm@selenic.com>
parents:
29011
diff
changeset
|
282 && next->b1 < next->b2 |
29011
8bcda4c76820
bdiff: fold in shift calculation in normalize
Matt Mackall <mpm@selenic.com>
parents:
29010
diff
changeset
|
283 && !cmp(a + curr->a2, b + curr->b2)) { |
8bcda4c76820
bdiff: fold in shift calculation in normalize
Matt Mackall <mpm@selenic.com>
parents:
29010
diff
changeset
|
284 curr->a2++; |
8bcda4c76820
bdiff: fold in shift calculation in normalize
Matt Mackall <mpm@selenic.com>
parents:
29010
diff
changeset
|
285 next->a1++; |
8bcda4c76820
bdiff: fold in shift calculation in normalize
Matt Mackall <mpm@selenic.com>
parents:
29010
diff
changeset
|
286 curr->b2++; |
8bcda4c76820
bdiff: fold in shift calculation in normalize
Matt Mackall <mpm@selenic.com>
parents:
29010
diff
changeset
|
287 next->b1++; |
8bcda4c76820
bdiff: fold in shift calculation in normalize
Matt Mackall <mpm@selenic.com>
parents:
29010
diff
changeset
|
288 } |
7104
9514cbb6e4f6
bdiff: normalize the diff (issue1295)
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
7036
diff
changeset
|
289 } |
9514cbb6e4f6
bdiff: normalize the diff (issue1295)
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
7036
diff
changeset
|
290 |
13089
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
291 for (curr = base->next; curr; curr = curr->next) |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
292 count++; |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
293 return count; |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
294 } |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
295 |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
296 static void freehunks(struct hunk *l) |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
297 { |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
298 struct hunk *n; |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
299 for (; l; l = n) { |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
300 n = l->next; |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
301 free(l); |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
302 } |
433
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
303 } |
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
304 |
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
305 static PyObject *blocks(PyObject *self, PyObject *args) |
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
306 { |
435 | 307 PyObject *sa, *sb, *rl = NULL, *m; |
433
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
308 struct line *a, *b; |
13089
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
309 struct hunk l, *h; |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
310 int an, bn, count, pos = 0; |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
311 |
19962
66b21ce60a19
bdiff: avoid a memory error on malloc failure
Matt Mackall <mpm@selenic.com>
parents:
18551
diff
changeset
|
312 l.next = NULL; |
66b21ce60a19
bdiff: avoid a memory error on malloc failure
Matt Mackall <mpm@selenic.com>
parents:
18551
diff
changeset
|
313 |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
314 if (!PyArg_ParseTuple(args, "SS:bdiff", &sa, &sb)) |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
315 return NULL; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
316 |
11364
0044193a1c45
bdiff.c: Added support for py3k.
Renato Cunha <renatoc@gmail.com>
parents:
10500
diff
changeset
|
317 an = splitlines(PyBytes_AsString(sa), PyBytes_Size(sa), &a); |
0044193a1c45
bdiff.c: Added support for py3k.
Renato Cunha <renatoc@gmail.com>
parents:
10500
diff
changeset
|
318 bn = splitlines(PyBytes_AsString(sb), PyBytes_Size(sb), &b); |
0044193a1c45
bdiff.c: Added support for py3k.
Renato Cunha <renatoc@gmail.com>
parents:
10500
diff
changeset
|
319 |
433
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
320 if (!a || !b) |
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
321 goto nomem; |
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
322 |
13089
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
323 count = diff(a, an, b, bn, &l); |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
324 if (count < 0) |
433
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
325 goto nomem; |
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
326 |
13089
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
327 rl = PyList_New(count); |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
328 if (!rl) |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
329 goto nomem; |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
330 |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
331 for (h = l.next; h; h = h->next) { |
433
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
332 m = Py_BuildValue("iiii", h->a1, h->a2, h->b1, h->b2); |
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
333 PyList_SetItem(rl, pos, m); |
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
334 pos++; |
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
335 } |
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
336 |
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
337 nomem: |
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
338 free(a); |
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
339 free(b); |
13089
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
340 freehunks(l.next); |
433
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
341 return rl ? rl : PyErr_NoMemory(); |
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
342 } |
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
343 |
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
344 static PyObject *bdiff(PyObject *self, PyObject *args) |
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
345 { |
15222
73015301db86
bdiff: fix pointer aliasing
Matt Mackall <mpm@selenic.com>
parents:
13732
diff
changeset
|
346 char *sa, *sb, *rb; |
3335
9061613c1593
Teach bdiff to support buffer objects
Brendan Cully <brendan@kublai.com>
parents:
2859
diff
changeset
|
347 PyObject *result = NULL; |
433
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
348 struct line *al, *bl; |
13089
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
349 struct hunk l, *h; |
16749
eab8ca175262
bdiff: use Py_ssize_t instead of int
Adrian Buehlmann <adrian@cadifra.com>
parents:
16477
diff
changeset
|
350 int an, bn, count; |
eab8ca175262
bdiff: use Py_ssize_t instead of int
Adrian Buehlmann <adrian@cadifra.com>
parents:
16477
diff
changeset
|
351 Py_ssize_t len = 0, la, lb; |
16477
70b5e25f1598
bdiff.bdiff: release the GIL before doing expensive diff operations
Augie Fackler <raf@durin42.com>
parents:
16437
diff
changeset
|
352 PyThreadState *_save; |
433
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
353 |
19962
66b21ce60a19
bdiff: avoid a memory error on malloc failure
Matt Mackall <mpm@selenic.com>
parents:
18551
diff
changeset
|
354 l.next = NULL; |
66b21ce60a19
bdiff: avoid a memory error on malloc failure
Matt Mackall <mpm@selenic.com>
parents:
18551
diff
changeset
|
355 |
3369
4bad632913d8
python2.5 PyArg_ParseTuple fix
Alexis S. L. Carvalho <alexis@cecm.usp.br>
parents:
3335
diff
changeset
|
356 if (!PyArg_ParseTuple(args, "s#s#:bdiff", &sa, &la, &sb, &lb)) |
433
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
357 return NULL; |
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
358 |
18551
d6fb7bbec16a
bdiff: simplify overflow checks
Matt Mackall <mpm@selenic.com>
parents:
16750
diff
changeset
|
359 if (la > UINT_MAX || lb > UINT_MAX) { |
d6fb7bbec16a
bdiff: simplify overflow checks
Matt Mackall <mpm@selenic.com>
parents:
16750
diff
changeset
|
360 PyErr_SetString(PyExc_ValueError, "bdiff inputs too large"); |
d6fb7bbec16a
bdiff: simplify overflow checks
Matt Mackall <mpm@selenic.com>
parents:
16750
diff
changeset
|
361 return NULL; |
d6fb7bbec16a
bdiff: simplify overflow checks
Matt Mackall <mpm@selenic.com>
parents:
16750
diff
changeset
|
362 } |
d6fb7bbec16a
bdiff: simplify overflow checks
Matt Mackall <mpm@selenic.com>
parents:
16750
diff
changeset
|
363 |
16477
70b5e25f1598
bdiff.bdiff: release the GIL before doing expensive diff operations
Augie Fackler <raf@durin42.com>
parents:
16437
diff
changeset
|
364 _save = PyEval_SaveThread(); |
3335
9061613c1593
Teach bdiff to support buffer objects
Brendan Cully <brendan@kublai.com>
parents:
2859
diff
changeset
|
365 an = splitlines(sa, la, &al); |
9061613c1593
Teach bdiff to support buffer objects
Brendan Cully <brendan@kublai.com>
parents:
2859
diff
changeset
|
366 bn = splitlines(sb, lb, &bl); |
433
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
367 if (!al || !bl) |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
368 goto nomem; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
369 |
13089
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
370 count = diff(al, an, bl, bn, &l); |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
371 if (count < 0) |
433
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
372 goto nomem; |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
373 |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
374 /* calculate length of output */ |
3335
9061613c1593
Teach bdiff to support buffer objects
Brendan Cully <brendan@kublai.com>
parents:
2859
diff
changeset
|
375 la = lb = 0; |
13089
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
376 for (h = l.next; h; h = h->next) { |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
377 if (h->a1 != la || h->b1 != lb) |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
378 len += 12 + bl[h->b1].l - bl[lb].l; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
379 la = h->a2; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
380 lb = h->b2; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
381 } |
16477
70b5e25f1598
bdiff.bdiff: release the GIL before doing expensive diff operations
Augie Fackler <raf@durin42.com>
parents:
16437
diff
changeset
|
382 PyEval_RestoreThread(_save); |
70b5e25f1598
bdiff.bdiff: release the GIL before doing expensive diff operations
Augie Fackler <raf@durin42.com>
parents:
16437
diff
changeset
|
383 _save = NULL; |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
384 |
11364
0044193a1c45
bdiff.c: Added support for py3k.
Renato Cunha <renatoc@gmail.com>
parents:
10500
diff
changeset
|
385 result = PyBytes_FromStringAndSize(NULL, len); |
0044193a1c45
bdiff.c: Added support for py3k.
Renato Cunha <renatoc@gmail.com>
parents:
10500
diff
changeset
|
386 |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
387 if (!result) |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
388 goto nomem; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
389 |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
390 /* build binary patch */ |
11364
0044193a1c45
bdiff.c: Added support for py3k.
Renato Cunha <renatoc@gmail.com>
parents:
10500
diff
changeset
|
391 rb = PyBytes_AsString(result); |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
392 la = lb = 0; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
393 |
13089
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
394 for (h = l.next; h; h = h->next) { |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
395 if (h->a1 != la || h->b1 != lb) { |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
396 len = bl[h->b1].l - bl[lb].l; |
18551
d6fb7bbec16a
bdiff: simplify overflow checks
Matt Mackall <mpm@selenic.com>
parents:
16750
diff
changeset
|
397 putbe32((uint32_t)(al[la].l - al->l), rb); |
d6fb7bbec16a
bdiff: simplify overflow checks
Matt Mackall <mpm@selenic.com>
parents:
16750
diff
changeset
|
398 putbe32((uint32_t)(al[h->a1].l - al->l), rb + 4); |
d6fb7bbec16a
bdiff: simplify overflow checks
Matt Mackall <mpm@selenic.com>
parents:
16750
diff
changeset
|
399 putbe32((uint32_t)len, rb + 8); |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
400 memcpy(rb + 12, bl[lb].l, len); |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
401 rb += 12 + len; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
402 } |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
403 la = h->a2; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
404 lb = h->b2; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
405 } |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
406 |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
407 nomem: |
16477
70b5e25f1598
bdiff.bdiff: release the GIL before doing expensive diff operations
Augie Fackler <raf@durin42.com>
parents:
16437
diff
changeset
|
408 if (_save) |
70b5e25f1598
bdiff.bdiff: release the GIL before doing expensive diff operations
Augie Fackler <raf@durin42.com>
parents:
16437
diff
changeset
|
409 PyEval_RestoreThread(_save); |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
410 free(al); |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
411 free(bl); |
13089
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
412 freehunks(l.next); |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
413 return result ? result : PyErr_NoMemory(); |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
414 } |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
415 |
15530
eeac5e179243
mdiff: replace wscleanup() regexps with C loops
Patrick Mezard <pmezard@gmail.com>
parents:
15222
diff
changeset
|
416 /* |
eeac5e179243
mdiff: replace wscleanup() regexps with C loops
Patrick Mezard <pmezard@gmail.com>
parents:
15222
diff
changeset
|
417 * If allws != 0, remove all whitespace (' ', \t and \r). Otherwise, |
eeac5e179243
mdiff: replace wscleanup() regexps with C loops
Patrick Mezard <pmezard@gmail.com>
parents:
15222
diff
changeset
|
418 * reduce whitespace sequences to a single space and trim remaining whitespace |
eeac5e179243
mdiff: replace wscleanup() regexps with C loops
Patrick Mezard <pmezard@gmail.com>
parents:
15222
diff
changeset
|
419 * from end of lines. |
eeac5e179243
mdiff: replace wscleanup() regexps with C loops
Patrick Mezard <pmezard@gmail.com>
parents:
15222
diff
changeset
|
420 */ |
eeac5e179243
mdiff: replace wscleanup() regexps with C loops
Patrick Mezard <pmezard@gmail.com>
parents:
15222
diff
changeset
|
421 static PyObject *fixws(PyObject *self, PyObject *args) |
eeac5e179243
mdiff: replace wscleanup() regexps with C loops
Patrick Mezard <pmezard@gmail.com>
parents:
15222
diff
changeset
|
422 { |
eeac5e179243
mdiff: replace wscleanup() regexps with C loops
Patrick Mezard <pmezard@gmail.com>
parents:
15222
diff
changeset
|
423 PyObject *s, *result = NULL; |
eeac5e179243
mdiff: replace wscleanup() regexps with C loops
Patrick Mezard <pmezard@gmail.com>
parents:
15222
diff
changeset
|
424 char allws, c; |
eeac5e179243
mdiff: replace wscleanup() regexps with C loops
Patrick Mezard <pmezard@gmail.com>
parents:
15222
diff
changeset
|
425 const char *r; |
16749
eab8ca175262
bdiff: use Py_ssize_t instead of int
Adrian Buehlmann <adrian@cadifra.com>
parents:
16477
diff
changeset
|
426 Py_ssize_t i, rlen, wlen = 0; |
15530
eeac5e179243
mdiff: replace wscleanup() regexps with C loops
Patrick Mezard <pmezard@gmail.com>
parents:
15222
diff
changeset
|
427 char *w; |
eeac5e179243
mdiff: replace wscleanup() regexps with C loops
Patrick Mezard <pmezard@gmail.com>
parents:
15222
diff
changeset
|
428 |
eeac5e179243
mdiff: replace wscleanup() regexps with C loops
Patrick Mezard <pmezard@gmail.com>
parents:
15222
diff
changeset
|
429 if (!PyArg_ParseTuple(args, "Sb:fixws", &s, &allws)) |
eeac5e179243
mdiff: replace wscleanup() regexps with C loops
Patrick Mezard <pmezard@gmail.com>
parents:
15222
diff
changeset
|
430 return NULL; |
eeac5e179243
mdiff: replace wscleanup() regexps with C loops
Patrick Mezard <pmezard@gmail.com>
parents:
15222
diff
changeset
|
431 r = PyBytes_AsString(s); |
eeac5e179243
mdiff: replace wscleanup() regexps with C loops
Patrick Mezard <pmezard@gmail.com>
parents:
15222
diff
changeset
|
432 rlen = PyBytes_Size(s); |
eeac5e179243
mdiff: replace wscleanup() regexps with C loops
Patrick Mezard <pmezard@gmail.com>
parents:
15222
diff
changeset
|
433 |
16071
8134ec8627e7
bdiff: fix malloc(0) issue in fixws()
Jim Hague <jim.hague@acm.org>
parents:
15530
diff
changeset
|
434 w = (char *)malloc(rlen ? rlen : 1); |
15530
eeac5e179243
mdiff: replace wscleanup() regexps with C loops
Patrick Mezard <pmezard@gmail.com>
parents:
15222
diff
changeset
|
435 if (!w) |
eeac5e179243
mdiff: replace wscleanup() regexps with C loops
Patrick Mezard <pmezard@gmail.com>
parents:
15222
diff
changeset
|
436 goto nomem; |
eeac5e179243
mdiff: replace wscleanup() regexps with C loops
Patrick Mezard <pmezard@gmail.com>
parents:
15222
diff
changeset
|
437 |
eeac5e179243
mdiff: replace wscleanup() regexps with C loops
Patrick Mezard <pmezard@gmail.com>
parents:
15222
diff
changeset
|
438 for (i = 0; i != rlen; i++) { |
eeac5e179243
mdiff: replace wscleanup() regexps with C loops
Patrick Mezard <pmezard@gmail.com>
parents:
15222
diff
changeset
|
439 c = r[i]; |
eeac5e179243
mdiff: replace wscleanup() regexps with C loops
Patrick Mezard <pmezard@gmail.com>
parents:
15222
diff
changeset
|
440 if (c == ' ' || c == '\t' || c == '\r') { |
eeac5e179243
mdiff: replace wscleanup() regexps with C loops
Patrick Mezard <pmezard@gmail.com>
parents:
15222
diff
changeset
|
441 if (!allws && (wlen == 0 || w[wlen - 1] != ' ')) |
eeac5e179243
mdiff: replace wscleanup() regexps with C loops
Patrick Mezard <pmezard@gmail.com>
parents:
15222
diff
changeset
|
442 w[wlen++] = ' '; |
eeac5e179243
mdiff: replace wscleanup() regexps with C loops
Patrick Mezard <pmezard@gmail.com>
parents:
15222
diff
changeset
|
443 } else if (c == '\n' && !allws |
eeac5e179243
mdiff: replace wscleanup() regexps with C loops
Patrick Mezard <pmezard@gmail.com>
parents:
15222
diff
changeset
|
444 && wlen > 0 && w[wlen - 1] == ' ') { |
eeac5e179243
mdiff: replace wscleanup() regexps with C loops
Patrick Mezard <pmezard@gmail.com>
parents:
15222
diff
changeset
|
445 w[wlen - 1] = '\n'; |
eeac5e179243
mdiff: replace wscleanup() regexps with C loops
Patrick Mezard <pmezard@gmail.com>
parents:
15222
diff
changeset
|
446 } else { |
eeac5e179243
mdiff: replace wscleanup() regexps with C loops
Patrick Mezard <pmezard@gmail.com>
parents:
15222
diff
changeset
|
447 w[wlen++] = c; |
eeac5e179243
mdiff: replace wscleanup() regexps with C loops
Patrick Mezard <pmezard@gmail.com>
parents:
15222
diff
changeset
|
448 } |
eeac5e179243
mdiff: replace wscleanup() regexps with C loops
Patrick Mezard <pmezard@gmail.com>
parents:
15222
diff
changeset
|
449 } |
eeac5e179243
mdiff: replace wscleanup() regexps with C loops
Patrick Mezard <pmezard@gmail.com>
parents:
15222
diff
changeset
|
450 |
eeac5e179243
mdiff: replace wscleanup() regexps with C loops
Patrick Mezard <pmezard@gmail.com>
parents:
15222
diff
changeset
|
451 result = PyBytes_FromStringAndSize(w, wlen); |
eeac5e179243
mdiff: replace wscleanup() regexps with C loops
Patrick Mezard <pmezard@gmail.com>
parents:
15222
diff
changeset
|
452 |
eeac5e179243
mdiff: replace wscleanup() regexps with C loops
Patrick Mezard <pmezard@gmail.com>
parents:
15222
diff
changeset
|
453 nomem: |
eeac5e179243
mdiff: replace wscleanup() regexps with C loops
Patrick Mezard <pmezard@gmail.com>
parents:
15222
diff
changeset
|
454 free(w); |
eeac5e179243
mdiff: replace wscleanup() regexps with C loops
Patrick Mezard <pmezard@gmail.com>
parents:
15222
diff
changeset
|
455 return result ? result : PyErr_NoMemory(); |
eeac5e179243
mdiff: replace wscleanup() regexps with C loops
Patrick Mezard <pmezard@gmail.com>
parents:
15222
diff
changeset
|
456 } |
eeac5e179243
mdiff: replace wscleanup() regexps with C loops
Patrick Mezard <pmezard@gmail.com>
parents:
15222
diff
changeset
|
457 |
eeac5e179243
mdiff: replace wscleanup() regexps with C loops
Patrick Mezard <pmezard@gmail.com>
parents:
15222
diff
changeset
|
458 |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
459 static char mdiff_doc[] = "Efficient binary diff."; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
460 |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
461 static PyMethodDef methods[] = { |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
462 {"bdiff", bdiff, METH_VARARGS, "calculate a binary diff\n"}, |
433
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
463 {"blocks", blocks, METH_VARARGS, "find a list of matching lines\n"}, |
15530
eeac5e179243
mdiff: replace wscleanup() regexps with C loops
Patrick Mezard <pmezard@gmail.com>
parents:
15222
diff
changeset
|
464 {"fixws", fixws, METH_VARARGS, "normalize diff whitespaces\n"}, |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
465 {NULL, NULL} |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
466 }; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
467 |
11364
0044193a1c45
bdiff.c: Added support for py3k.
Renato Cunha <renatoc@gmail.com>
parents:
10500
diff
changeset
|
468 #ifdef IS_PY3K |
0044193a1c45
bdiff.c: Added support for py3k.
Renato Cunha <renatoc@gmail.com>
parents:
10500
diff
changeset
|
469 static struct PyModuleDef bdiff_module = { |
0044193a1c45
bdiff.c: Added support for py3k.
Renato Cunha <renatoc@gmail.com>
parents:
10500
diff
changeset
|
470 PyModuleDef_HEAD_INIT, |
0044193a1c45
bdiff.c: Added support for py3k.
Renato Cunha <renatoc@gmail.com>
parents:
10500
diff
changeset
|
471 "bdiff", |
0044193a1c45
bdiff.c: Added support for py3k.
Renato Cunha <renatoc@gmail.com>
parents:
10500
diff
changeset
|
472 mdiff_doc, |
0044193a1c45
bdiff.c: Added support for py3k.
Renato Cunha <renatoc@gmail.com>
parents:
10500
diff
changeset
|
473 -1, |
0044193a1c45
bdiff.c: Added support for py3k.
Renato Cunha <renatoc@gmail.com>
parents:
10500
diff
changeset
|
474 methods |
0044193a1c45
bdiff.c: Added support for py3k.
Renato Cunha <renatoc@gmail.com>
parents:
10500
diff
changeset
|
475 }; |
0044193a1c45
bdiff.c: Added support for py3k.
Renato Cunha <renatoc@gmail.com>
parents:
10500
diff
changeset
|
476 |
0044193a1c45
bdiff.c: Added support for py3k.
Renato Cunha <renatoc@gmail.com>
parents:
10500
diff
changeset
|
477 PyMODINIT_FUNC PyInit_bdiff(void) |
0044193a1c45
bdiff.c: Added support for py3k.
Renato Cunha <renatoc@gmail.com>
parents:
10500
diff
changeset
|
478 { |
0044193a1c45
bdiff.c: Added support for py3k.
Renato Cunha <renatoc@gmail.com>
parents:
10500
diff
changeset
|
479 return PyModule_Create(&bdiff_module); |
0044193a1c45
bdiff.c: Added support for py3k.
Renato Cunha <renatoc@gmail.com>
parents:
10500
diff
changeset
|
480 } |
0044193a1c45
bdiff.c: Added support for py3k.
Renato Cunha <renatoc@gmail.com>
parents:
10500
diff
changeset
|
481 #else |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
482 PyMODINIT_FUNC initbdiff(void) |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
483 { |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
484 Py_InitModule3("bdiff", methods, mdiff_doc); |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
485 } |
11364
0044193a1c45
bdiff.c: Added support for py3k.
Renato Cunha <renatoc@gmail.com>
parents:
10500
diff
changeset
|
486 #endif |
1542
8e80eefb3de6
made C src formatting more consistent
twaldmann@thinkmo.de
parents:
1397
diff
changeset
|
487 |