equal
deleted
inserted
replaced
10 */ |
10 */ |
11 |
11 |
12 #include <Python.h> |
12 #include <Python.h> |
13 #include <stdlib.h> |
13 #include <stdlib.h> |
14 #include <string.h> |
14 #include <string.h> |
|
15 #include <limits.h> |
15 |
16 |
16 #if defined __hpux || defined __SUNPRO_C || defined _AIX |
17 #if defined __hpux || defined __SUNPRO_C || defined _AIX |
17 # define inline |
18 # define inline |
18 #endif |
19 #endif |
19 |
20 |
95 } |
96 } |
96 if (*p == '\n' || p == plast) { |
97 if (*p == '\n' || p == plast) { |
97 l->len = p - b + 1; |
98 l->len = p - b + 1; |
98 l->h = h * l->len; |
99 l->h = h * l->len; |
99 l->l = b; |
100 l->l = b; |
100 l->n = -1; |
101 l->n = INT_MAX; |
101 l++; |
102 l++; |
102 b = p + 1; |
103 b = p + 1; |
103 h = 0; |
104 h = 0; |
104 } |
105 } |
105 } |
106 } |
136 |
137 |
137 buckets = buckets * scale - 1; |
138 buckets = buckets * scale - 1; |
138 |
139 |
139 /* clear the hash table */ |
140 /* clear the hash table */ |
140 for (i = 0; i <= buckets; i++) { |
141 for (i = 0; i <= buckets; i++) { |
141 h[i].pos = -1; |
142 h[i].pos = INT_MAX; |
142 h[i].len = 0; |
143 h[i].len = 0; |
143 } |
144 } |
144 |
145 |
145 /* add lines to the hash table chains */ |
146 /* add lines to the hash table chains */ |
146 for (i = bn - 1; i >= 0; i--) { |
147 for (i = bn - 1; i >= 0; i--) { |
147 /* find the equivalence class */ |
148 /* find the equivalence class */ |
148 for (j = b[i].h & buckets; h[j].pos != -1; |
149 for (j = b[i].h & buckets; h[j].pos != INT_MAX; |
149 j = (j + 1) & buckets) |
150 j = (j + 1) & buckets) |
150 if (!cmp(b + i, b + h[j].pos)) |
151 if (!cmp(b + i, b + h[j].pos)) |
151 break; |
152 break; |
152 |
153 |
153 /* add to the head of the equivalence class */ |
154 /* add to the head of the equivalence class */ |
161 t = (bn >= 200) ? bn / 100 : bn + 1; |
162 t = (bn >= 200) ? bn / 100 : bn + 1; |
162 |
163 |
163 /* match items in a to their equivalence class in b */ |
164 /* match items in a to their equivalence class in b */ |
164 for (i = 0; i < an; i++) { |
165 for (i = 0; i < an; i++) { |
165 /* find the equivalence class */ |
166 /* find the equivalence class */ |
166 for (j = a[i].h & buckets; h[j].pos != -1; |
167 for (j = a[i].h & buckets; h[j].pos != INT_MAX; |
167 j = (j + 1) & buckets) |
168 j = (j + 1) & buckets) |
168 if (!cmp(a + i, b + h[j].pos)) |
169 if (!cmp(a + i, b + h[j].pos)) |
169 break; |
170 break; |
170 |
171 |
171 a[i].e = j; /* use equivalence class for quick compare */ |
172 a[i].e = j; /* use equivalence class for quick compare */ |
172 if (h[j].len <= t) |
173 if (h[j].len <= t) |
173 a[i].n = h[j].pos; /* point to head of match list */ |
174 a[i].n = h[j].pos; /* point to head of match list */ |
174 else |
175 else |
175 a[i].n = -1; /* too popular */ |
176 a[i].n = INT_MAX; /* too popular */ |
176 } |
177 } |
177 |
178 |
178 /* discard hash tables */ |
179 /* discard hash tables */ |
179 free(h); |
180 free(h); |
180 return 1; |
181 return 1; |
185 { |
186 { |
186 int mi = a1, mj = b1, mk = 0, mb = 0, i, j, k; |
187 int mi = a1, mj = b1, mk = 0, mb = 0, i, j, k; |
187 |
188 |
188 for (i = a1; i < a2; i++) { |
189 for (i = a1; i < a2; i++) { |
189 /* skip things before the current block */ |
190 /* skip things before the current block */ |
190 for (j = a[i].n; j != -1 && j < b1; j = b[j].n) |
191 for (j = a[i].n; j < b1; j = b[j].n) |
191 ; |
192 ; |
192 |
193 |
193 /* loop through all lines match a[i] in b */ |
194 /* loop through all lines match a[i] in b */ |
194 for (; j != -1 && j < b2; j = b[j].n) { |
195 for (; j < b2; j = b[j].n) { |
195 /* does this extend an earlier match? */ |
196 /* does this extend an earlier match? */ |
196 if (i > a1 && j > b1 && pos[j - 1].pos == i - 1) |
197 if (i > a1 && j > b1 && pos[j - 1].pos == i - 1) |
197 k = pos[j - 1].len + 1; |
198 k = pos[j - 1].len + 1; |
198 else |
199 else |
199 k = 1; |
200 k = 1; |
222 a[mi + mk].e == b[mj + mk].e) |
223 a[mi + mk].e == b[mj + mk].e) |
223 mk++; |
224 mk++; |
224 |
225 |
225 *omi = mi - mb; |
226 *omi = mi - mb; |
226 *omj = mj - mb; |
227 *omj = mj - mb; |
|
228 |
227 return mk + mb; |
229 return mk + mb; |
228 } |
230 } |
229 |
231 |
230 static void recurse(struct line *a, struct line *b, struct pos *pos, |
232 static void recurse(struct line *a, struct line *b, struct pos *pos, |
231 int a1, int a2, int b1, int b2, struct hunklist *l) |
233 int a1, int a2, int b1, int b2, struct hunklist *l) |