Mercurial > hg > mercurial-crew-with-dirclash
comparison mercurial/mdiff.py @ 71:47c9a869adee
Add mdiff.patches to speed up applying thousands of patches to the manifest
author | mpm@selenic.com |
---|---|
date | Sat, 14 May 2005 10:27:14 -0800 |
parents | b3e2ddff0159 |
children | 4a6ab4d80dc4 |
comparison
equal
deleted
inserted
replaced
70:ce080e8eccd7 | 71:47c9a869adee |
---|---|
1 #!/usr/bin/python | 1 #!/usr/bin/python |
2 import difflib, struct | 2 import difflib, struct, mmap |
3 from cStringIO import StringIO | 3 |
4 devzero = file("/dev/zero") | |
4 | 5 |
5 def unidiff(a, ad, b, bd, fn): | 6 def unidiff(a, ad, b, bd, fn): |
6 if not a and not b: return "" | 7 if not a and not b: return "" |
7 a = a.splitlines(1) | 8 a = a.splitlines(1) |
8 b = b.splitlines(1) | 9 b = b.splitlines(1) |
50 s = "".join(b[s:t]) | 51 s = "".join(b[s:t]) |
51 bin.append(struct.pack(">lll", p[m], p[n], len(s)) + s) | 52 bin.append(struct.pack(">lll", p[m], p[n], len(s)) + s) |
52 | 53 |
53 return "".join(bin) | 54 return "".join(bin) |
54 | 55 |
56 # This attempts to apply a series of patches in time proportional to | |
57 # the total size of the patches, rather than patches * len(text). This | |
58 # means rather than shuffling strings around, we shuffle around | |
59 # pointers to fragments with fragment lists. | |
60 # | |
61 # When the fragment lists get too long, we collapse them. To do this | |
62 # efficiently, we do all our operations inside a buffer created by | |
63 # mmap and simply use memmove. This avoids creating a bunch of large | |
64 # temporary string buffers. | |
65 | |
66 def patches(a, bins): | |
67 if not bins: return a | |
68 | |
69 plens = [len(x) for x in bins] | |
70 pl = sum(plens) | |
71 bl = len(a) + pl | |
72 tl = bl + bl + pl # enough for the patches and two working texts | |
73 b1, b2 = 0, bl | |
74 m = mmap.mmap(devzero.fileno(), tl, mmap.MAP_PRIVATE) | |
75 | |
76 # load our original text | |
77 m.write(a) | |
78 frags = [(len(a), b1)] | |
79 | |
80 # copy all the patches into our segment so we can memmove from them | |
81 pos = b2 + bl | |
82 m.seek(pos) | |
83 for p in bins: m.write(p) | |
84 | |
85 def pull(dst, src, l): # pull l bytes from src | |
86 while l: | |
87 f = src.pop(0) | |
88 if f[0] > l: # do we need to split? | |
89 src.insert(0, (f[0] - l, f[1] + l)) | |
90 dst.append((l, f[1])) | |
91 return | |
92 dst.append(f) | |
93 l -= f[0] | |
94 | |
95 def collect(buf, list): | |
96 start = buf | |
97 for l, p in list: | |
98 m.move(buf, p, l) | |
99 buf += l | |
100 return (buf - start, start) | |
101 | |
102 for plen in plens: | |
103 # if our list gets too long, execute it | |
104 if len(frags) > 128: | |
105 b2, b1 = b1, b2 | |
106 frags = [collect(b1, frags)] | |
107 | |
108 new = [] | |
109 end = pos + plen | |
110 last = 0 | |
111 while pos < end: | |
112 p1, p2, l = struct.unpack(">lll", m[pos:pos + 12]) | |
113 pull(new, frags, p1 - last) # what didn't change | |
114 pull([], frags, p2 - p1) # what got deleted | |
115 new.append((l, pos + 12)) # what got added | |
116 pos += l + 12 | |
117 last = p2 | |
118 frags = new + frags # what was left at the end | |
119 | |
120 t = collect(b2, frags) | |
121 | |
122 return m[t[1]:t[1] + t[0]] | |
123 | |
55 def patch(a, bin): | 124 def patch(a, bin): |
56 last = pos = 0 | 125 last = pos = 0 |
57 r = [] | 126 r = [] |
58 | 127 |
59 c = 0 | 128 c = 0 |