##// END OF EJS Templates
mpatch: move pull() method to top level...
Augie Fackler -
r28587:76d7cab1 default
parent child Browse files
Show More
@@ -1,119 +1,119 b''
1 1 # mpatch.py - Python implementation of mpatch.c
2 2 #
3 3 # Copyright 2009 Matt Mackall <mpm@selenic.com> and others
4 4 #
5 5 # This software may be used and distributed according to the terms of the
6 6 # GNU General Public License version 2 or any later version.
7 7
8 8 from __future__ import absolute_import
9 9
10 10 import cStringIO
11 11 import struct
12 12
13 13 StringIO = cStringIO.StringIO
14 14
15 15 # This attempts to apply a series of patches in time proportional to
16 16 # the total size of the patches, rather than patches * len(text). This
17 17 # means rather than shuffling strings around, we shuffle around
18 18 # pointers to fragments with fragment lists.
19 19 #
20 20 # When the fragment lists get too long, we collapse them. To do this
21 21 # efficiently, we do all our operations inside a buffer created by
22 22 # mmap and simply use memmove. This avoids creating a bunch of large
23 23 # temporary string buffers.
24 24
25 def _pull(dst, src, l): # pull l bytes from src
26 while l:
27 f = src.pop()
28 if f[0] > l: # do we need to split?
29 src.append((f[0] - l, f[1] + l))
30 dst.append((l, f[1]))
31 return
32 dst.append(f)
33 l -= f[0]
34
25 35 def patches(a, bins):
26 36 if not bins:
27 37 return a
28 38
29 39 plens = [len(x) for x in bins]
30 40 pl = sum(plens)
31 41 bl = len(a) + pl
32 42 tl = bl + bl + pl # enough for the patches and two working texts
33 43 b1, b2 = 0, bl
34 44
35 45 if not tl:
36 46 return a
37 47
38 48 m = StringIO()
39 49 def move(dest, src, count):
40 50 """move count bytes from src to dest
41 51
42 52 The file pointer is left at the end of dest.
43 53 """
44 54 m.seek(src)
45 55 buf = m.read(count)
46 56 m.seek(dest)
47 57 m.write(buf)
48 58
49 59 # load our original text
50 60 m.write(a)
51 61 frags = [(len(a), b1)]
52 62
53 63 # copy all the patches into our segment so we can memmove from them
54 64 pos = b2 + bl
55 65 m.seek(pos)
56 66 for p in bins: m.write(p)
57 67
58 def pull(dst, src, l): # pull l bytes from src
59 while l:
60 f = src.pop()
61 if f[0] > l: # do we need to split?
62 src.append((f[0] - l, f[1] + l))
63 dst.append((l, f[1]))
64 return
65 dst.append(f)
66 l -= f[0]
67
68 68 def collect(buf, list):
69 69 start = buf
70 70 for l, p in reversed(list):
71 71 move(buf, p, l)
72 72 buf += l
73 73 return (buf - start, start)
74 74
75 75 for plen in plens:
76 76 # if our list gets too long, execute it
77 77 if len(frags) > 128:
78 78 b2, b1 = b1, b2
79 79 frags = [collect(b1, frags)]
80 80
81 81 new = []
82 82 end = pos + plen
83 83 last = 0
84 84 while pos < end:
85 85 m.seek(pos)
86 86 p1, p2, l = struct.unpack(">lll", m.read(12))
87 pull(new, frags, p1 - last) # what didn't change
88 pull([], frags, p2 - p1) # what got deleted
87 _pull(new, frags, p1 - last) # what didn't change
88 _pull([], frags, p2 - p1) # what got deleted
89 89 new.append((l, pos + 12)) # what got added
90 90 pos += l + 12
91 91 last = p2
92 92 frags.extend(reversed(new)) # what was left at the end
93 93
94 94 t = collect(b2, frags)
95 95
96 96 m.seek(t[1])
97 97 return m.read(t[0])
98 98
99 99 def patchedsize(orig, delta):
100 100 outlen, last, bin = 0, 0, 0
101 101 binend = len(delta)
102 102 data = 12
103 103
104 104 while data <= binend:
105 105 decode = delta[bin:bin + 12]
106 106 start, end, length = struct.unpack(">lll", decode)
107 107 if start > end:
108 108 break
109 109 bin = data + length
110 110 data = bin + 12
111 111 outlen += start - last
112 112 last = end
113 113 outlen += length
114 114
115 115 if bin != binend:
116 116 raise ValueError("patch cannot be decoded")
117 117
118 118 outlen += orig - last
119 119 return outlen
General Comments 0
You need to be logged in to leave comments. Login now