Mercurial > hg > mercurial-crew-with-dirclash

comparison mercurial/bdiff.c @ 5365:458acf92b49e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
bdiff: use INT_MAX to avoid some inner loop comparisons
author Matt Mackall <mpm@selenic.com>
date Thu, 27 Sep 2007 23:59:02 -0500
parents 5737845fd974
children d0c48891dd4a
comparison
equal deleted inserted replaced
5364:5737845fd974 5365:458acf92b49e
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)