Mercurial > hg
annotate mercurial/bdiff.c @ 30318:e1d6aa0e4c3a
bdiff: replace hash algorithm
This patch replaces lyhash with the hash algorithm used by diffutils.
The algorithm has its origins in Git commit 2e9d1410, which is all the
way back from 1992. The license header in the code at that revision
in GPL v2.
I have not performed an extensive analysis of the distribution
(and therefore buckets) of hash output. However, `hg perfbdiff`
gives some clear wins. I'd like to think that if it is good enough
for diffutils it is good enough for us?
From the mozilla-unified repository:
$ perfbdiff -m 3041e4d59df2
! wall 0.053271 comb 0.060000 user 0.060000 sys 0.000000 (best of 100)
! wall 0.035827 comb 0.040000 user 0.040000 sys 0.000000 (best of 100)
$ perfbdiff 0e9928989e9c --alldata --count 100
! wall 6.204277 comb 6.200000 user 6.200000 sys 0.000000 (best of 3)
! wall 4.309710 comb 4.300000 user 4.300000 sys 0.000000 (best of 3)
From the hg repo:
$ perfbdiff 35000 --alldata --count 1000
! wall 0.660358 comb 0.660000 user 0.660000 sys 0.000000 (best of 15)
! wall 0.534092 comb 0.530000 user 0.530000 sys 0.000000 (best of 19)
Looking at the generated assembly and statistical profiler output
from the kernel level, I believe there is room to make this function
even faster. Namely, we're still consuming data character by character
instead of at the word level. This translates to more loop iterations
and more instructions.
At this juncture though, the real performance killer is that we're
hashing every line. We should get a significant speedup if we change
the algorithm to find the longest prefix, longest suffix, treat those
as single "lines" and then only do the line splitting and hashing on
the parts that are different. That will require a lot of C code,
however. I'm optimistic this approach could result in a ~2x speedup.
author | Gregory Szorc <gregory.szorc@gmail.com> |
---|---|
date | Sun, 06 Nov 2016 18:51:57 -0800 |
parents | d500ddae7494 |
children | 38ed54888617 |
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 |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
12 #include <stdlib.h> |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
13 #include <string.h> |
5341
458acf92b49e
bdiff: use INT_MAX to avoid some inner loop comparisons
Matt Mackall <mpm@selenic.com>
parents:
5340
diff
changeset
|
14 #include <limits.h> |
867
0cd2ee61b10a
Allow Mercurial to build on HP-UX 11
tksoh@users.sourceforge.net
parents:
839
diff
changeset
|
15 |
29539
666832b9e154
bdiff: use ssize_t in favor of Py_ssize_t in cpython-unaware locations
Maciej Fijalkowski <fijall@gmail.com>
parents:
29444
diff
changeset
|
16 #include "compat.h" |
29444
284d742e5611
internals: move the bitmanipulation routines into its own file
Maciej Fijalkowski <fijall@gmail.com>
parents:
29323
diff
changeset
|
17 #include "bitmanipulation.h" |
29541
9631ff5ebbeb
bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
29540
diff
changeset
|
18 #include "bdiff.h" |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
19 |
30318
e1d6aa0e4c3a
bdiff: replace hash algorithm
Gregory Szorc <gregory.szorc@gmail.com>
parents:
30308
diff
changeset
|
20 /* Hash implementation from diffutils */ |
e1d6aa0e4c3a
bdiff: replace hash algorithm
Gregory Szorc <gregory.szorc@gmail.com>
parents:
30308
diff
changeset
|
21 #define ROL(v, n) ((v) << (n) | (v) >> (sizeof(v) * CHAR_BIT - (n))) |
e1d6aa0e4c3a
bdiff: replace hash algorithm
Gregory Szorc <gregory.szorc@gmail.com>
parents:
30308
diff
changeset
|
22 #define HASH(h, c) ((c) + ROL(h ,7)) |
e1d6aa0e4c3a
bdiff: replace hash algorithm
Gregory Szorc <gregory.szorc@gmail.com>
parents:
30308
diff
changeset
|
23 |
474 | 24 struct pos { |
25 int pos, len; | |
26 }; | |
27 | |
29541
9631ff5ebbeb
bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
29540
diff
changeset
|
28 int bdiff_splitlines(const char *a, ssize_t len, struct bdiff_line **lr) |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
29 { |
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
|
30 unsigned hash; |
13731
5d0cdf4ec338
bdiff.c: use unsigned arithmetic for hash computation
Markus F.X.J. Oberhumer <markus@oberhumer.com>
parents:
13730
diff
changeset
|
31 int i; |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
32 const char *p, *b = a; |
5340
5737845fd974
bdiff: simple splitlines optimization
Christoph Spiel <cspiel@freenet.de>
parents:
5339
diff
changeset
|
33 const char * const plast = a + len - 1; |
29540
4ce1fc91e30a
bdiff: rename functions and structs to be amenable for later exporting
Maciej Fijalkowski <fijall@gmail.com>
parents:
29539
diff
changeset
|
34 struct bdiff_line *l; |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
35 |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
36 /* count the lines */ |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
37 i = 1; /* extra line for sentinel */ |
30308
d500ddae7494
bdiff: don't check border condition in loop
Gregory Szorc <gregory.szorc@gmail.com>
parents:
29541
diff
changeset
|
38 for (p = a; p < plast; p++) |
d500ddae7494
bdiff: don't check border condition in loop
Gregory Szorc <gregory.szorc@gmail.com>
parents:
29541
diff
changeset
|
39 if (*p == '\n') |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
40 i++; |
30308
d500ddae7494
bdiff: don't check border condition in loop
Gregory Szorc <gregory.szorc@gmail.com>
parents:
29541
diff
changeset
|
41 if (p == plast) |
d500ddae7494
bdiff: don't check border condition in loop
Gregory Szorc <gregory.szorc@gmail.com>
parents:
29541
diff
changeset
|
42 i++; |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
43 |
29540
4ce1fc91e30a
bdiff: rename functions and structs to be amenable for later exporting
Maciej Fijalkowski <fijall@gmail.com>
parents:
29539
diff
changeset
|
44 *lr = l = (struct bdiff_line *)malloc(sizeof(struct bdiff_line) * i); |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
45 if (!l) |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
46 return -1; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
47 |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
48 /* 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
|
49 hash = 0; |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
50 for (p = a; p < a + len; p++) { |
30318
e1d6aa0e4c3a
bdiff: replace hash algorithm
Gregory Szorc <gregory.szorc@gmail.com>
parents:
30308
diff
changeset
|
51 hash = HASH(hash, *p); |
5342 | 52 |
5340
5737845fd974
bdiff: simple splitlines optimization
Christoph Spiel <cspiel@freenet.de>
parents:
5339
diff
changeset
|
53 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
|
54 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
|
55 hash = 0; |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
56 l->len = p - b + 1; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
57 l->l = b; |
5341
458acf92b49e
bdiff: use INT_MAX to avoid some inner loop comparisons
Matt Mackall <mpm@selenic.com>
parents:
5340
diff
changeset
|
58 l->n = INT_MAX; |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
59 l++; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
60 b = p + 1; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
61 } |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
62 } |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
63 |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
64 /* 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
|
65 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
|
66 l->len = 0; |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
67 l->l = a + len; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
68 return i - 1; |
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 |
29540
4ce1fc91e30a
bdiff: rename functions and structs to be amenable for later exporting
Maciej Fijalkowski <fijall@gmail.com>
parents:
29539
diff
changeset
|
71 static inline int cmp(struct bdiff_line *a, struct bdiff_line *b) |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
72 { |
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
|
73 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
|
74 } |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
75 |
29540
4ce1fc91e30a
bdiff: rename functions and structs to be amenable for later exporting
Maciej Fijalkowski <fijall@gmail.com>
parents:
29539
diff
changeset
|
76 static int equatelines(struct bdiff_line *a, int an, struct bdiff_line *b, |
4ce1fc91e30a
bdiff: rename functions and structs to be amenable for later exporting
Maciej Fijalkowski <fijall@gmail.com>
parents:
29539
diff
changeset
|
77 int bn) |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
78 { |
5452
82b4ff3abbcd
bdiff: tweaks for large files
Matt Mackall <mpm@selenic.com>
parents:
5342
diff
changeset
|
79 int i, j, buckets = 1, t, scale; |
82b4ff3abbcd
bdiff: tweaks for large files
Matt Mackall <mpm@selenic.com>
parents:
5342
diff
changeset
|
80 struct pos *h = NULL; |
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 /* 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
|
83 while (buckets < bn + 1) |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
84 buckets *= 2; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
85 |
5339
058e93c3d07d
I have spotted the biggest bottleneck in "bdiff.c". Actually it was
Christoph Spiel <cspiel@freenet.de>
parents:
4134
diff
changeset
|
86 /* 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
|
87 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
|
88 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
|
89 if (h) |
82b4ff3abbcd
bdiff: tweaks for large files
Matt Mackall <mpm@selenic.com>
parents:
5342
diff
changeset
|
90 break; |
82b4ff3abbcd
bdiff: tweaks for large files
Matt Mackall <mpm@selenic.com>
parents:
5342
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 |
474 | 93 if (!h) |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
94 return 0; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
95 |
5339
058e93c3d07d
I have spotted the biggest bottleneck in "bdiff.c". Actually it was
Christoph Spiel <cspiel@freenet.de>
parents:
4134
diff
changeset
|
96 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
|
97 |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
98 /* clear the hash table */ |
474 | 99 for (i = 0; i <= buckets; i++) { |
29013
9a8363d23419
bdiff: deal better with duplicate lines
Matt Mackall <mpm@selenic.com>
parents:
29012
diff
changeset
|
100 h[i].pos = -1; |
474 | 101 h[i].len = 0; |
102 } | |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
103 |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
104 /* add lines to the hash table chains */ |
29013
9a8363d23419
bdiff: deal better with duplicate lines
Matt Mackall <mpm@selenic.com>
parents:
29012
diff
changeset
|
105 for (i = 0; i < bn; i++) { |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
106 /* find the equivalence class */ |
29013
9a8363d23419
bdiff: deal better with duplicate lines
Matt Mackall <mpm@selenic.com>
parents:
29012
diff
changeset
|
107 for (j = b[i].hash & buckets; h[j].pos != -1; |
474 | 108 j = (j + 1) & buckets) |
109 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
|
110 break; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
111 |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
112 /* add to the head of the equivalence class */ |
474 | 113 b[i].n = h[j].pos; |
433
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
114 b[i].e = j; |
474 | 115 h[j].pos = i; |
116 h[j].len++; /* keep track of popularity */ | |
400
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 |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
119 /* compute popularity threshold */ |
9534
8e202431d620
bdiff: gradually enable the popularity hack
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
8858
diff
changeset
|
120 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
|
121 |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
122 /* 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
|
123 for (i = 0; i < an; i++) { |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
124 /* find the equivalence class */ |
29013
9a8363d23419
bdiff: deal better with duplicate lines
Matt Mackall <mpm@selenic.com>
parents:
29012
diff
changeset
|
125 for (j = a[i].hash & buckets; h[j].pos != -1; |
474 | 126 j = (j + 1) & buckets) |
127 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
|
128 break; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
129 |
433
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
130 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
|
131 if (h[j].len <= t) |
474 | 132 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
|
133 else |
29013
9a8363d23419
bdiff: deal better with duplicate lines
Matt Mackall <mpm@selenic.com>
parents:
29012
diff
changeset
|
134 a[i].n = -1; /* too popular */ |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
135 } |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
136 |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
137 /* discard hash tables */ |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
138 free(h); |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
139 return 1; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
140 } |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
141 |
29540
4ce1fc91e30a
bdiff: rename functions and structs to be amenable for later exporting
Maciej Fijalkowski <fijall@gmail.com>
parents:
29539
diff
changeset
|
142 static int longest_match(struct bdiff_line *a, struct bdiff_line *b, |
4ce1fc91e30a
bdiff: rename functions and structs to be amenable for later exporting
Maciej Fijalkowski <fijall@gmail.com>
parents:
29539
diff
changeset
|
143 struct pos *pos, |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
144 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
|
145 { |
29323
d29cb5e735e9
bdiff: remove effectively dead code
Matt Mackall <mpm@selenic.com>
parents:
29322
diff
changeset
|
146 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
|
147 |
87d4a6c5567e
bdiff: further restrain potential quadratic performance
Matt Mackall <mpm@selenic.com>
parents:
29014
diff
changeset
|
148 /* 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
|
149 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
|
150 reduce skipping overhead on the b chains. */ |
87d4a6c5567e
bdiff: further restrain potential quadratic performance
Matt Mackall <mpm@selenic.com>
parents:
29014
diff
changeset
|
151 if (a2 - a1 > 30000) |
87d4a6c5567e
bdiff: further restrain potential quadratic performance
Matt Mackall <mpm@selenic.com>
parents:
29014
diff
changeset
|
152 a1 = a2 - 30000; |
87d4a6c5567e
bdiff: further restrain potential quadratic performance
Matt Mackall <mpm@selenic.com>
parents:
29014
diff
changeset
|
153 |
87d4a6c5567e
bdiff: further restrain potential quadratic performance
Matt Mackall <mpm@selenic.com>
parents:
29014
diff
changeset
|
154 half = (a1 + a2) / 2; |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
155 |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
156 for (i = a1; i < a2; i++) { |
29013
9a8363d23419
bdiff: deal better with duplicate lines
Matt Mackall <mpm@selenic.com>
parents:
29012
diff
changeset
|
157 /* 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
|
158 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
|
159 ; |
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 /* 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
|
162 for (; j >= b1; j = b[j].n) { |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
163 /* does this extend an earlier match? */ |
29322
66dbdd3cc2b9
bdiff: extend matches across popular lines
Matt Mackall <mpm@selenic.com>
parents:
29015
diff
changeset
|
164 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
|
165 /* reached an earlier match? */ |
66dbdd3cc2b9
bdiff: extend matches across popular lines
Matt Mackall <mpm@selenic.com>
parents:
29015
diff
changeset
|
166 if (pos[j - k].pos == i - k) { |
66dbdd3cc2b9
bdiff: extend matches across popular lines
Matt Mackall <mpm@selenic.com>
parents:
29015
diff
changeset
|
167 k += pos[j - k].len; |
66dbdd3cc2b9
bdiff: extend matches across popular lines
Matt Mackall <mpm@selenic.com>
parents:
29015
diff
changeset
|
168 break; |
66dbdd3cc2b9
bdiff: extend matches across popular lines
Matt Mackall <mpm@selenic.com>
parents:
29015
diff
changeset
|
169 } |
66dbdd3cc2b9
bdiff: extend matches across popular lines
Matt Mackall <mpm@selenic.com>
parents:
29015
diff
changeset
|
170 /* previous line mismatch? */ |
66dbdd3cc2b9
bdiff: extend matches across popular lines
Matt Mackall <mpm@selenic.com>
parents:
29015
diff
changeset
|
171 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
|
172 break; |
66dbdd3cc2b9
bdiff: extend matches across popular lines
Matt Mackall <mpm@selenic.com>
parents:
29015
diff
changeset
|
173 } |
66dbdd3cc2b9
bdiff: extend matches across popular lines
Matt Mackall <mpm@selenic.com>
parents:
29015
diff
changeset
|
174 |
474 | 175 pos[j].pos = i; |
176 pos[j].len = k; | |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
177 |
29014
f1ca249696ed
bdiff: balance recursion to avoid quadratic behavior (issue4704)
Matt Mackall <mpm@selenic.com>
parents:
29013
diff
changeset
|
178 /* 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
|
179 to the middle to balance recursion */ |
f1ca249696ed
bdiff: balance recursion to avoid quadratic behavior (issue4704)
Matt Mackall <mpm@selenic.com>
parents:
29013
diff
changeset
|
180 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
|
181 mi = i; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
182 mj = j; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
183 mk = k; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
184 } |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
185 } |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
186 } |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
187 |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
188 if (mk) { |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
189 mi = mi - mk + 1; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
190 mj = mj - mk + 1; |
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 |
29323
d29cb5e735e9
bdiff: remove effectively dead code
Matt Mackall <mpm@selenic.com>
parents:
29322
diff
changeset
|
193 /* expand match to include subsequent popular lines */ |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
194 while (mi + mk < a2 && mj + mk < b2 && |
433
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
195 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
|
196 mk++; |
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 *omi = mi; |
d29cb5e735e9
bdiff: remove effectively dead code
Matt Mackall <mpm@selenic.com>
parents:
29322
diff
changeset
|
199 *omj = mj; |
5341
458acf92b49e
bdiff: use INT_MAX to avoid some inner loop comparisons
Matt Mackall <mpm@selenic.com>
parents:
5340
diff
changeset
|
200 |
29323
d29cb5e735e9
bdiff: remove effectively dead code
Matt Mackall <mpm@selenic.com>
parents:
29322
diff
changeset
|
201 return mk; |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
202 } |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
203 |
29540
4ce1fc91e30a
bdiff: rename functions and structs to be amenable for later exporting
Maciej Fijalkowski <fijall@gmail.com>
parents:
29539
diff
changeset
|
204 static struct bdiff_hunk *recurse(struct bdiff_line *a, struct bdiff_line *b, |
4ce1fc91e30a
bdiff: rename functions and structs to be amenable for later exporting
Maciej Fijalkowski <fijall@gmail.com>
parents:
29539
diff
changeset
|
205 struct pos *pos, |
4ce1fc91e30a
bdiff: rename functions and structs to be amenable for later exporting
Maciej Fijalkowski <fijall@gmail.com>
parents:
29539
diff
changeset
|
206 int a1, int a2, int b1, int b2, struct bdiff_hunk *l) |
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 int i, j, k; |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
209 |
10500
e96597c8d0ea
bdiff: do not use recursion / avoid stackoverflow (issue1940)
Alistair Bell <alistair@bellsonline.com>
parents:
10282
diff
changeset
|
210 while (1) { |
e96597c8d0ea
bdiff: do not use recursion / avoid stackoverflow (issue1940)
Alistair Bell <alistair@bellsonline.com>
parents:
10282
diff
changeset
|
211 /* 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
|
212 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
|
213 if (!k) |
13089
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
214 return l; |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
215 |
10500
e96597c8d0ea
bdiff: do not use recursion / avoid stackoverflow (issue1940)
Alistair Bell <alistair@bellsonline.com>
parents:
10282
diff
changeset
|
216 /* and recurse on the remaining chunks on either side */ |
13089
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
217 l = recurse(a, b, pos, a1, i, b1, j, l); |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
218 if (!l) |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
219 return NULL; |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
220 |
29540
4ce1fc91e30a
bdiff: rename functions and structs to be amenable for later exporting
Maciej Fijalkowski <fijall@gmail.com>
parents:
29539
diff
changeset
|
221 l->next = (struct bdiff_hunk *)malloc(sizeof(struct bdiff_hunk)); |
13089
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
222 if (!l->next) |
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 = l->next; |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
226 l->a1 = i; |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
227 l->a2 = i + k; |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
228 l->b1 = j; |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
229 l->b2 = j + k; |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
230 l->next = NULL; |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
231 |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
232 /* 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
|
233 a1 = i + k; |
e96597c8d0ea
bdiff: do not use recursion / avoid stackoverflow (issue1940)
Alistair Bell <alistair@bellsonline.com>
parents:
10282
diff
changeset
|
234 b1 = j + k; |
e96597c8d0ea
bdiff: do not use recursion / avoid stackoverflow (issue1940)
Alistair Bell <alistair@bellsonline.com>
parents:
10282
diff
changeset
|
235 } |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
236 } |
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
237 |
29541
9631ff5ebbeb
bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
29540
diff
changeset
|
238 int bdiff_diff(struct bdiff_line *a, int an, struct bdiff_line *b, |
29540
4ce1fc91e30a
bdiff: rename functions and structs to be amenable for later exporting
Maciej Fijalkowski <fijall@gmail.com>
parents:
29539
diff
changeset
|
239 int bn, struct bdiff_hunk *base) |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
240 { |
29540
4ce1fc91e30a
bdiff: rename functions and structs to be amenable for later exporting
Maciej Fijalkowski <fijall@gmail.com>
parents:
29539
diff
changeset
|
241 struct bdiff_hunk *curr; |
474 | 242 struct pos *pos; |
13089
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
243 int t, count = 0; |
433
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
244 |
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
245 /* allocate and fill arrays */ |
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
246 t = equatelines(a, an, b, bn); |
5571 | 247 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
|
248 |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
249 if (pos && t) { |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
250 /* generate the matching block list */ |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
251 |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
252 curr = recurse(a, b, pos, 0, an, 0, bn, base); |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
253 if (!curr) |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
254 return -1; |
433
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
255 |
13089
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
256 /* sentinel end hunk */ |
29540
4ce1fc91e30a
bdiff: rename functions and structs to be amenable for later exporting
Maciej Fijalkowski <fijall@gmail.com>
parents:
29539
diff
changeset
|
257 curr->next = (struct bdiff_hunk *)malloc(sizeof(struct bdiff_hunk)); |
13089
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
258 if (!curr->next) |
13090
c73745762f33
bdiff: Fix bogus NULL return
Matt Mackall <mpm@selenic.com>
parents:
13089
diff
changeset
|
259 return -1; |
13089
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
260 curr = curr->next; |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
261 curr->a1 = curr->a2 = an; |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
262 curr->b1 = curr->b2 = bn; |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
263 curr->next = NULL; |
433
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
264 } |
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
265 |
474 | 266 free(pos); |
7104
9514cbb6e4f6
bdiff: normalize the diff (issue1295)
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
7036
diff
changeset
|
267 |
7625
930a2be7e875
bdiff: add comment about normalization
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
7189
diff
changeset
|
268 /* 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
|
269 for (curr = base->next; curr; curr = curr->next) { |
29540
4ce1fc91e30a
bdiff: rename functions and structs to be amenable for later exporting
Maciej Fijalkowski <fijall@gmail.com>
parents:
29539
diff
changeset
|
270 struct bdiff_hunk *next = curr->next; |
7104
9514cbb6e4f6
bdiff: normalize the diff (issue1295)
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
7036
diff
changeset
|
271 |
13089
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
272 if (!next) |
7104
9514cbb6e4f6
bdiff: normalize the diff (issue1295)
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
7036
diff
changeset
|
273 break; |
9514cbb6e4f6
bdiff: normalize the diff (issue1295)
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
7036
diff
changeset
|
274 |
29010
e868d8ee7c8f
bdiff: unify duplicate normalize loops
Matt Mackall <mpm@selenic.com>
parents:
19962
diff
changeset
|
275 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
|
276 while (curr->a2 < an && curr->b2 < bn |
29012
4bd67ae7d75a
bdiff: fix latent normalization bug
Matt Mackall <mpm@selenic.com>
parents:
29011
diff
changeset
|
277 && next->a1 < next->a2 |
4bd67ae7d75a
bdiff: fix latent normalization bug
Matt Mackall <mpm@selenic.com>
parents:
29011
diff
changeset
|
278 && next->b1 < next->b2 |
29011
8bcda4c76820
bdiff: fold in shift calculation in normalize
Matt Mackall <mpm@selenic.com>
parents:
29010
diff
changeset
|
279 && !cmp(a + curr->a2, b + curr->b2)) { |
8bcda4c76820
bdiff: fold in shift calculation in normalize
Matt Mackall <mpm@selenic.com>
parents:
29010
diff
changeset
|
280 curr->a2++; |
8bcda4c76820
bdiff: fold in shift calculation in normalize
Matt Mackall <mpm@selenic.com>
parents:
29010
diff
changeset
|
281 next->a1++; |
8bcda4c76820
bdiff: fold in shift calculation in normalize
Matt Mackall <mpm@selenic.com>
parents:
29010
diff
changeset
|
282 curr->b2++; |
8bcda4c76820
bdiff: fold in shift calculation in normalize
Matt Mackall <mpm@selenic.com>
parents:
29010
diff
changeset
|
283 next->b1++; |
8bcda4c76820
bdiff: fold in shift calculation in normalize
Matt Mackall <mpm@selenic.com>
parents:
29010
diff
changeset
|
284 } |
7104
9514cbb6e4f6
bdiff: normalize the diff (issue1295)
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
7036
diff
changeset
|
285 } |
9514cbb6e4f6
bdiff: normalize the diff (issue1295)
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
7036
diff
changeset
|
286 |
13089
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
287 for (curr = base->next; curr; curr = curr->next) |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
288 count++; |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
289 return count; |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
290 } |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
291 |
29541
9631ff5ebbeb
bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
29540
diff
changeset
|
292 void bdiff_freehunks(struct bdiff_hunk *l) |
13089
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
293 { |
29540
4ce1fc91e30a
bdiff: rename functions and structs to be amenable for later exporting
Maciej Fijalkowski <fijall@gmail.com>
parents:
29539
diff
changeset
|
294 struct bdiff_hunk *n; |
13089
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
295 for (; l; l = n) { |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
296 n = l->next; |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
297 free(l); |
faee0ffbc24b
bdiff: dynamically allocate hunks
Matt Mackall <mpm@selenic.com>
parents:
11364
diff
changeset
|
298 } |
433
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
299 } |
79c694462294
Add bdiff.blocks / minor performance tweaks
mpm@selenic.com
parents:
411
diff
changeset
|
300 |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
301 |