annotate mercurial/mpatch.c @ 766:b444a7e053f1

Get addremove to use new walk code. It is now more verbose than it used to be. If given file names, it prints nothing, as before. But if given patterns or nothing, it prints the names of the files it is operating on, to remove that air of mystery. It also now operates at or below the current directory.
author Bryan O'Sullivan <bos@serpentine.com>
date Fri, 22 Jul 2005 19:45:48 -0800
parents e530637ea060
children 681c5c211b92
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
1 /*
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
2 mpatch.c - efficient binary patching for Mercurial
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
3
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
4 This implements a patch algorithm that's O(m + nlog n) where m is the
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
5 size of the output and n is the number of patches.
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
6
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
7 Given a list of binary patches, it unpacks each into a hunk list,
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
8 then combines the hunk lists with a treewise recursion to form a
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
9 single hunk list. This hunk list is then applied to the original
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
10 text.
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
11
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
12 The text (or binary) fragments are copied directly from their source
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
13 Python objects into a preallocated output string to avoid the
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
14 allocation of intermediate Python objects. Working memory is about 2x
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
15 the total number of hunks.
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
16
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
17 Copyright 2005 Matt Mackall <mpm@selenic.com>
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
18
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
19 This software may be used and distributed according to the terms
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
20 of the GNU General Public License, incorporated herein by reference.
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
21 */
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
22
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
23 #include <Python.h>
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
24 #include <stdlib.h>
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
25 #include <string.h>
410
7c678976df3e Make mpatch.c compilable under the other `OS'
mpm@selenic.com
parents: 384
diff changeset
26 #ifdef _WIN32
551
b460a2fd8bb7 [PATCH] bdiff/mpatch under MSVC
mpm@selenic.com
parents: 510
diff changeset
27 #ifdef _MSC_VER
b460a2fd8bb7 [PATCH] bdiff/mpatch under MSVC
mpm@selenic.com
parents: 510
diff changeset
28 #define inline __inline
b460a2fd8bb7 [PATCH] bdiff/mpatch under MSVC
mpm@selenic.com
parents: 510
diff changeset
29 typedef unsigned long uint32_t;
b460a2fd8bb7 [PATCH] bdiff/mpatch under MSVC
mpm@selenic.com
parents: 510
diff changeset
30 #else
510
7f3fc8fd427e More fiddling with uint32_t includes for extensions
mpm@selenic.com
parents: 495
diff changeset
31 #include <stdint.h>
551
b460a2fd8bb7 [PATCH] bdiff/mpatch under MSVC
mpm@selenic.com
parents: 510
diff changeset
32 #endif
411
9e9f7ab43ce2 Add 'other OS' bits to bdiff.c / style cleanups
mpm@selenic.com
parents: 410
diff changeset
33 static uint32_t ntohl(uint32_t x)
9e9f7ab43ce2 Add 'other OS' bits to bdiff.c / style cleanups
mpm@selenic.com
parents: 410
diff changeset
34 {
9e9f7ab43ce2 Add 'other OS' bits to bdiff.c / style cleanups
mpm@selenic.com
parents: 410
diff changeset
35 return ((x & 0x000000ffUL) << 24) |
9e9f7ab43ce2 Add 'other OS' bits to bdiff.c / style cleanups
mpm@selenic.com
parents: 410
diff changeset
36 ((x & 0x0000ff00UL) << 8) |
9e9f7ab43ce2 Add 'other OS' bits to bdiff.c / style cleanups
mpm@selenic.com
parents: 410
diff changeset
37 ((x & 0x00ff0000UL) >> 8) |
9e9f7ab43ce2 Add 'other OS' bits to bdiff.c / style cleanups
mpm@selenic.com
parents: 410
diff changeset
38 ((x & 0xff000000UL) >> 24);
410
7c678976df3e Make mpatch.c compilable under the other `OS'
mpm@selenic.com
parents: 384
diff changeset
39 }
7c678976df3e Make mpatch.c compilable under the other `OS'
mpm@selenic.com
parents: 384
diff changeset
40 #else
510
7f3fc8fd427e More fiddling with uint32_t includes for extensions
mpm@selenic.com
parents: 495
diff changeset
41 #include <sys/types.h>
597
e530637ea060 [PATCH] use <arpa/inet.h> instead of <netinet/in.h> for ntohl/htonl
mpm@selenic.com
parents: 553
diff changeset
42 #include <arpa/inet.h>
410
7c678976df3e Make mpatch.c compilable under the other `OS'
mpm@selenic.com
parents: 384
diff changeset
43 #endif
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
44
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
45 static char mpatch_doc[] = "Efficient binary patching.";
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
46
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
47 struct frag {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
48 int start, end, len;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
49 char *data;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
50 };
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
51
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
52 struct flist {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
53 struct frag *base, *head, *tail;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
54 };
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
55
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
56 static struct flist *lalloc(int size)
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
57 {
128
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
58 struct flist *a = NULL;
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
59
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
60 a = malloc(sizeof(struct flist));
128
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
61 if (a) {
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
62 a->base = malloc(sizeof(struct frag) * size);
282
97d83e7fbf2f mpatch: properly NULL out return in lalloc
mpm@selenic.com
parents: 128
diff changeset
63 if (!a->base) {
128
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
64 free(a);
282
97d83e7fbf2f mpatch: properly NULL out return in lalloc
mpm@selenic.com
parents: 128
diff changeset
65 a = NULL;
97d83e7fbf2f mpatch: properly NULL out return in lalloc
mpm@selenic.com
parents: 128
diff changeset
66 } else
128
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
67 a->head = a->tail = a->base;
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
68 }
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
69 return a;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
70 }
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
71
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
72 static void lfree(struct flist *a)
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
73 {
128
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
74 if (a) {
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
75 free(a->base);
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
76 free(a);
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
77 }
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
78 }
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
79
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
80 static int lsize(struct flist *a)
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
81 {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
82 return a->tail - a->head;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
83 }
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
84
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
85 /* move hunks in source that are less cut to dest, compensating
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
86 for changes in offset. the last hunk may be split if necessary.
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
87 */
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
88 static int gather(struct flist *dest, struct flist *src, int cut, int offset)
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
89 {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
90 struct frag *d = dest->tail, *s = src->head;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
91 int postend, c, l;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
92
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
93 while (s != src->tail) {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
94 if (s->start + offset >= cut)
82
7ed96baa7caa Gotos are embarrassing.
mpm@selenic.com
parents: 72
diff changeset
95 break; /* we've gone far enough */
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
96
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
97 postend = offset + s->start + s->len;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
98 if (postend <= cut) {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
99 /* save this hunk */
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
100 offset += s->start + s->len - s->end;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
101 *d++ = *s++;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
102 }
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
103 else {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
104 /* break up this hunk */
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
105 c = cut - offset;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
106 if (s->end < c)
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
107 c = s->end;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
108 l = cut - offset - s->start;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
109 if (s->len < l)
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
110 l = s->len;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
111
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
112 offset += s->start + l - c;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
113
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
114 d->start = s->start;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
115 d->end = c;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
116 d->len = l;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
117 d->data = s->data;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
118 d++;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
119 s->start = c;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
120 s->len = s->len - l;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
121 s->data = s->data + l;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
122
82
7ed96baa7caa Gotos are embarrassing.
mpm@selenic.com
parents: 72
diff changeset
123 break;
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
124 }
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
125 }
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
126
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
127 dest->tail = d;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
128 src->head = s;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
129 return offset;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
130 }
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
131
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
132 /* like gather, but with no output list */
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
133 static int discard(struct flist *src, int cut, int offset)
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
134 {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
135 struct frag *s = src->head;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
136 int postend, c, l;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
137
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
138 while (s != src->tail) {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
139 if (s->start + offset >= cut)
82
7ed96baa7caa Gotos are embarrassing.
mpm@selenic.com
parents: 72
diff changeset
140 break;
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
141
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
142 postend = offset + s->start + s->len;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
143 if (postend <= cut) {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
144 offset += s->start + s->len - s->end;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
145 s++;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
146 }
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
147 else {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
148 c = cut - offset;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
149 if (s->end < c)
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
150 c = s->end;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
151 l = cut - offset - s->start;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
152 if (s->len < l)
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
153 l = s->len;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
154
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
155 offset += s->start + l - c;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
156 s->start = c;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
157 s->len = s->len - l;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
158 s->data = s->data + l;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
159
82
7ed96baa7caa Gotos are embarrassing.
mpm@selenic.com
parents: 72
diff changeset
160 break;
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
161 }
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
162 }
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
163
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
164 src->head = s;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
165 return offset;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
166 }
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
167
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
168 /* combine hunk lists a and b, while adjusting b for offset changes in a/
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
169 this deletes a and b and returns the resultant list. */
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
170 static struct flist *combine(struct flist *a, struct flist *b)
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
171 {
128
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
172 struct flist *c = NULL;
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
173 struct frag *bh, *ct;
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
174 int offset = 0, post;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
175
128
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
176 if (a && b)
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
177 c = lalloc((lsize(a) + lsize(b)) * 2);
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
178
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
179 if (c) {
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
180
128
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
181 for (bh = b->head; bh != b->tail; bh++) {
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
182 /* save old hunks */
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
183 offset = gather(c, a, bh->start, offset);
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
184
128
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
185 /* discard replaced hunks */
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
186 post = discard(a, bh->end, offset);
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
187
128
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
188 /* insert new hunk */
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
189 ct = c->tail;
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
190 ct->start = bh->start - offset;
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
191 ct->end = bh->end - post;
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
192 ct->len = bh->len;
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
193 ct->data = bh->data;
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
194 c->tail++;
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
195 offset = post;
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
196 }
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
197
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
198 /* hold on to tail from a */
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
199 memcpy(c->tail, a->head, sizeof(struct frag) * lsize(a));
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
200 c->tail += lsize(a);
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
201 }
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
202
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
203 lfree(a);
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
204 lfree(b);
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
205 return c;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
206 }
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
207
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
208 /* decode a binary patch into a hunk list */
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
209 static struct flist *decode(char *bin, int len)
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
210 {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
211 struct flist *l;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
212 struct frag *lt;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
213 char *end = bin + len;
384
a29decbf7475 mpatch: attempt to handle unpack alignment issues on Solaris
mpm@selenic.com
parents: 282
diff changeset
214 char decode[12]; /* for dealing with alignment issues */
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
215
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
216 /* assume worst case size, we won't have many of these lists */
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
217 l = lalloc(len / 12);
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
218 lt = l->tail;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
219
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
220 while (bin < end) {
384
a29decbf7475 mpatch: attempt to handle unpack alignment issues on Solaris
mpm@selenic.com
parents: 282
diff changeset
221 memcpy(decode, bin, 12);
a29decbf7475 mpatch: attempt to handle unpack alignment issues on Solaris
mpm@selenic.com
parents: 282
diff changeset
222 lt->start = ntohl(*(uint32_t *)decode);
a29decbf7475 mpatch: attempt to handle unpack alignment issues on Solaris
mpm@selenic.com
parents: 282
diff changeset
223 lt->end = ntohl(*(uint32_t *)(decode + 4));
a29decbf7475 mpatch: attempt to handle unpack alignment issues on Solaris
mpm@selenic.com
parents: 282
diff changeset
224 lt->len = ntohl(*(uint32_t *)(decode + 8));
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
225 lt->data = bin + 12;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
226 bin += 12 + lt->len;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
227 lt++;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
228 }
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
229
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
230 l->tail = lt;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
231 return l;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
232 }
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
233
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
234 /* calculate the size of resultant text */
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
235 static int calcsize(int len, struct flist *l)
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
236 {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
237 int outlen = 0, last = 0;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
238 struct frag *f = l->head;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
239
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
240 while (f != l->tail) {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
241 outlen += f->start - last;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
242 last = f->end;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
243 outlen += f->len;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
244 f++;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
245 }
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
246
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
247 outlen += len - last;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
248 return outlen;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
249 }
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
250
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
251 static void apply(char *buf, char *orig, int len, struct flist *l)
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
252 {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
253 struct frag *f = l->head;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
254 int last = 0;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
255 char *p = buf;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
256
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
257 while (f != l->tail) {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
258 memcpy(p, orig + last, f->start - last);
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
259 p += f->start - last;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
260 memcpy(p, f->data, f->len);
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
261 last = f->end;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
262 p += f->len;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
263 f++;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
264 }
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
265 memcpy(p, orig + last, len - last);
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
266 }
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
267
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
268 /* recursively generate a patch of all bins between start and end */
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
269 static struct flist *fold(PyObject *bins, int start, int end)
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
270 {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
271 int len;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
272
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
273 if (start + 1 == end) {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
274 /* trivial case, output a decoded list */
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
275 PyObject *tmp = PyList_GetItem(bins, start);
128
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
276 if (!tmp)
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
277 return NULL;
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
278 return decode(PyString_AsString(tmp), PyString_Size(tmp));
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
279 }
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
280
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
281 /* divide and conquer, memory management is elsewhere */
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
282 len = (end - start) / 2;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
283 return combine(fold(bins, start, start + len),
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
284 fold(bins, start + len, end));
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
285 }
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
286
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
287 static PyObject *
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
288 patches(PyObject *self, PyObject *args)
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
289 {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
290 PyObject *text, *bins, *result;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
291 struct flist *patch;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
292 char *in, *out;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
293 int len, outlen;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
294
128
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
295 if (!PyArg_ParseTuple(args, "SO:mpatch", &text, &bins))
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
296 return NULL;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
297
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
298 len = PyList_Size(bins);
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
299 if (!len) {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
300 /* nothing to do */
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
301 Py_INCREF(text);
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
302 return text;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
303 }
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
304
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
305 patch = fold(bins, 0, len);
128
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
306 if (!patch)
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
307 return PyErr_NoMemory();
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
308
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
309 outlen = calcsize(PyString_Size(text), patch);
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
310 result = PyString_FromStringAndSize(NULL, outlen);
128
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
311 if (result) {
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
312 in = PyString_AsString(text);
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
313 out = PyString_AsString(result);
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
314 apply(out, in, PyString_Size(text), patch);
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
315 }
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
316
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
317 lfree(patch);
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
318 return result;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
319 }
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
320
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
321 static PyMethodDef methods[] = {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
322 {"patches", patches, METH_VARARGS, "apply a series of patches\n"},
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
323 {NULL, NULL}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
324 };
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
325
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
326 PyMODINIT_FUNC
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
327 initmpatch(void)
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
328 {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
329 Py_InitModule3("mpatch", methods, mpatch_doc);
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
330 }
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
331