Fossil SCM

Merge the diff enhancement from trunk.

drh 2021-12-20 17:02 synclog merge
Commit 5bb01585bc8677ab15effd48879c8f9f9268e1284614d2b850ec95b0edd3d398
Parent ce5802534c9635a…
1 file changed +57 -51
~ src/diff.c
M src/diff.c
+57 -51
--- src/diff.c
+++ src/diff.c
@@ -2289,70 +2289,76 @@
22892289
 int iSXb, iSYb, iEXb, iEYb; /* Best match so far */
22902290
 int iSXp, iSYp, iEXp, iEYp; /* Previous match */
22912291
 sqlite3_int64 bestScore; /* Best score so far */
22922292
 sqlite3_int64 score; /* Score for current candidate LCS */
22932293
 int span; /* combined width of the input sequences */
2294
+ int cutoff = 4; /* Max hash chain entries to follow */
2295
+ int nextCutoff = -1; /* Value of cutoff for next iteration */
22942296
22952297
 span = (iE1 - iS1) + (iE2 - iS2);
22962298
 bestScore = -10000;
22972299
 score = 0;
22982300
 iSXb = iSXp = iS1;
22992301
 iEXb = iEXp = iS1;
23002302
 iSYb = iSYp = iS2;
23012303
 iEYb = iEYp = iS2;
23022304
 mid = (iE1 + iS1)/2;
2303
- for(i=iS1; i<iE1; i++){
2304
- int limit = 0;
2305
- j = p->aTo[p->aFrom[i].h % p->nTo].iHash;
2306
- while( j>0
2307
- && (j-1<iS2 || j>=iE2 || p->xDiffer(&p->aFrom[i], &p->aTo[j-1]))
2308
- ){
2309
- if( limit++ > 10 ){
2310
- j = 0;
2311
- break;
2312
- }
2313
- j = p->aTo[j-1].iNext;
2314
- }
2315
- if( j==0 ) continue;
2316
- assert( i>=iSXb && i>=iSXp );
2317
- if( i<iEXb && j>=iSYb && j<iEYb ) continue;
2318
- if( i<iEXp && j>=iSYp && j<iEYp ) continue;
2319
- iSX = i;
2320
- iSY = j-1;
2321
- pA = &p->aFrom[iSX-1];
2322
- pB = &p->aTo[iSY-1];
2323
- n = minInt(iSX-iS1, iSY-iS2);
2324
- for(k=0; k<n && p->xDiffer(pA,pB)==0; k++, pA--, pB--){}
2325
- iSX -= k;
2326
- iSY -= k;
2327
- iEX = i+1;
2328
- iEY = j;
2329
- pA = &p->aFrom[iEX];
2330
- pB = &p->aTo[iEY];
2331
- n = minInt(iE1-iEX, iE2-iEY);
2332
- for(k=0; k<n && p->xDiffer(pA,pB)==0; k++, pA++, pB++){}
2333
- iEX += k;
2334
- iEY += k;
2335
- skew = (iSX-iS1) - (iSY-iS2);
2336
- if( skew<0 ) skew = -skew;
2337
- dist = (iSX+iEX)/2 - mid;
2338
- if( dist<0 ) dist = -dist;
2339
- score = (iEX - iSX)*(sqlite3_int64)span - (skew + dist);
2340
- if( score>bestScore ){
2341
- bestScore = score;
2342
- iSXb = iSX;
2343
- iSYb = iSY;
2344
- iEXb = iEX;
2345
- iEYb = iEY;
2346
- }else if( iEX>iEXp ){
2347
- iSXp = iSX;
2348
- iSYp = iSY;
2349
- iEXp = iEX;
2350
- iEYp = iEY;
2351
- }
2352
- }
2353
- if( iSXb==iEXb && (sqlite3_int64)(iE1-iS1)*(iE2-iS2)<400 ){
2305
+ do{
2306
+ nextCutoff = 0;
2307
+ for(i=iS1; i<iE1; i++){
2308
+ int limit = 0;
2309
+ j = p->aTo[p->aFrom[i].h % p->nTo].iHash;
2310
+ while( j>0
2311
+ && (j-1<iS2 || j>=iE2 || p->xDiffer(&p->aFrom[i], &p->aTo[j-1]))
2312
+ ){
2313
+ if( limit++ > cutoff ){
2314
+ j = 0;
2315
+ nextCutoff = cutoff*4;
2316
+ break;
2317
+ }
2318
+ j = p->aTo[j-1].iNext;
2319
+ }
2320
+ if( j==0 ) continue;
2321
+ assert( i>=iSXb && i>=iSXp );
2322
+ if( i<iEXb && j>=iSYb && j<iEYb ) continue;
2323
+ if( i<iEXp && j>=iSYp && j<iEYp ) continue;
2324
+ iSX = i;
2325
+ iSY = j-1;
2326
+ pA = &p->aFrom[iSX-1];
2327
+ pB = &p->aTo[iSY-1];
2328
+ n = minInt(iSX-iS1, iSY-iS2);
2329
+ for(k=0; k<n && p->xDiffer(pA,pB)==0; k++, pA--, pB--){}
2330
+ iSX -= k;
2331
+ iSY -= k;
2332
+ iEX = i+1;
2333
+ iEY = j;
2334
+ pA = &p->aFrom[iEX];
2335
+ pB = &p->aTo[iEY];
2336
+ n = minInt(iE1-iEX, iE2-iEY);
2337
+ for(k=0; k<n && p->xDiffer(pA,pB)==0; k++, pA++, pB++){}
2338
+ iEX += k;
2339
+ iEY += k;
2340
+ skew = (iSX-iS1) - (iSY-iS2);
2341
+ if( skew<0 ) skew = -skew;
2342
+ dist = (iSX+iEX)/2 - mid;
2343
+ if( dist<0 ) dist = -dist;
2344
+ score = (iEX - iSX)*(sqlite3_int64)span - (skew + dist);
2345
+ if( score>bestScore ){
2346
+ bestScore = score;
2347
+ iSXb = iSX;
2348
+ iSYb = iSY;
2349
+ iEXb = iEX;
2350
+ iEYb = iEY;
2351
+ }else if( iEX>iEXp ){
2352
+ iSXp = iSX;
2353
+ iSYp = iSY;
2354
+ iEXp = iEX;
2355
+ iEYp = iEY;
2356
+ }
2357
+ }
2358
+ }while( iSXb==iEXb && nextCutoff && (cutoff=nextCutoff)<=64 );
2359
+ if( iSXb==iEXb && (sqlite3_int64)(iE1-iS1)*(iE2-iS2)<2500 ){
23542360
 /* If no common sequence is found using the hashing heuristic and
23552361
 ** the input is not too big, use the expensive exact solution */
23562362
 optimalLCS(p, iS1, iE1, iS2, iE2, piSX, piEX, piSY, piEY);
23572363
 }else{
23582364
 *piSX = iSXb;
23592365
--- src/diff.c
+++ src/diff.c
@@ -2289,70 +2289,76 @@
2289 int iSXb, iSYb, iEXb, iEYb; /* Best match so far */
2290 int iSXp, iSYp, iEXp, iEYp; /* Previous match */
2291 sqlite3_int64 bestScore; /* Best score so far */
2292 sqlite3_int64 score; /* Score for current candidate LCS */
2293 int span; /* combined width of the input sequences */
 
 
2294
2295 span = (iE1 - iS1) + (iE2 - iS2);
2296 bestScore = -10000;
2297 score = 0;
2298 iSXb = iSXp = iS1;
2299 iEXb = iEXp = iS1;
2300 iSYb = iSYp = iS2;
2301 iEYb = iEYp = iS2;
2302 mid = (iE1 + iS1)/2;
2303 for(i=iS1; i<iE1; i++){
2304 int limit = 0;
2305 j = p->aTo[p->aFrom[i].h % p->nTo].iHash;
2306 while( j>0
2307 && (j-1<iS2 || j>=iE2 || p->xDiffer(&p->aFrom[i], &p->aTo[j-1]))
2308 ){
2309 if( limit++ > 10 ){
2310 j = 0;
2311 break;
2312 }
2313 j = p->aTo[j-1].iNext;
2314 }
2315 if( j==0 ) continue;
2316 assert( i>=iSXb && i>=iSXp );
2317 if( i<iEXb && j>=iSYb && j<iEYb ) continue;
2318 if( i<iEXp && j>=iSYp && j<iEYp ) continue;
2319 iSX = i;
2320 iSY = j-1;
2321 pA = &p->aFrom[iSX-1];
2322 pB = &p->aTo[iSY-1];
2323 n = minInt(iSX-iS1, iSY-iS2);
2324 for(k=0; k<n && p->xDiffer(pA,pB)==0; k++, pA--, pB--){}
2325 iSX -= k;
2326 iSY -= k;
2327 iEX = i+1;
2328 iEY = j;
2329 pA = &p->aFrom[iEX];
2330 pB = &p->aTo[iEY];
2331 n = minInt(iE1-iEX, iE2-iEY);
2332 for(k=0; k<n && p->xDiffer(pA,pB)==0; k++, pA++, pB++){}
2333 iEX += k;
2334 iEY += k;
2335 skew = (iSX-iS1) - (iSY-iS2);
2336 if( skew<0 ) skew = -skew;
2337 dist = (iSX+iEX)/2 - mid;
2338 if( dist<0 ) dist = -dist;
2339 score = (iEX - iSX)*(sqlite3_int64)span - (skew + dist);
2340 if( score>bestScore ){
2341 bestScore = score;
2342 iSXb = iSX;
2343 iSYb = iSY;
2344 iEXb = iEX;
2345 iEYb = iEY;
2346 }else if( iEX>iEXp ){
2347 iSXp = iSX;
2348 iSYp = iSY;
2349 iEXp = iEX;
2350 iEYp = iEY;
2351 }
2352 }
2353 if( iSXb==iEXb && (sqlite3_int64)(iE1-iS1)*(iE2-iS2)<400 ){
 
 
 
 
2354 /* If no common sequence is found using the hashing heuristic and
2355 ** the input is not too big, use the expensive exact solution */
2356 optimalLCS(p, iS1, iE1, iS2, iE2, piSX, piEX, piSY, piEY);
2357 }else{
2358 *piSX = iSXb;
2359
--- src/diff.c
+++ src/diff.c
@@ -2289,70 +2289,76 @@
2289 int iSXb, iSYb, iEXb, iEYb; /* Best match so far */
2290 int iSXp, iSYp, iEXp, iEYp; /* Previous match */
2291 sqlite3_int64 bestScore; /* Best score so far */
2292 sqlite3_int64 score; /* Score for current candidate LCS */
2293 int span; /* combined width of the input sequences */
2294 int cutoff = 4; /* Max hash chain entries to follow */
2295 int nextCutoff = -1; /* Value of cutoff for next iteration */
2296
2297 span = (iE1 - iS1) + (iE2 - iS2);
2298 bestScore = -10000;
2299 score = 0;
2300 iSXb = iSXp = iS1;
2301 iEXb = iEXp = iS1;
2302 iSYb = iSYp = iS2;
2303 iEYb = iEYp = iS2;
2304 mid = (iE1 + iS1)/2;
2305 do{
2306 nextCutoff = 0;
2307 for(i=iS1; i<iE1; i++){
2308 int limit = 0;
2309 j = p->aTo[p->aFrom[i].h % p->nTo].iHash;
2310 while( j>0
2311 && (j-1<iS2 || j>=iE2 || p->xDiffer(&p->aFrom[i], &p->aTo[j-1]))
2312 ){
2313 if( limit++ > cutoff ){
2314 j = 0;
2315 nextCutoff = cutoff*4;
2316 break;
2317 }
2318 j = p->aTo[j-1].iNext;
2319 }
2320 if( j==0 ) continue;
2321 assert( i>=iSXb && i>=iSXp );
2322 if( i<iEXb && j>=iSYb && j<iEYb ) continue;
2323 if( i<iEXp && j>=iSYp && j<iEYp ) continue;
2324 iSX = i;
2325 iSY = j-1;
2326 pA = &p->aFrom[iSX-1];
2327 pB = &p->aTo[iSY-1];
2328 n = minInt(iSX-iS1, iSY-iS2);
2329 for(k=0; k<n && p->xDiffer(pA,pB)==0; k++, pA--, pB--){}
2330 iSX -= k;
2331 iSY -= k;
2332 iEX = i+1;
2333 iEY = j;
2334 pA = &p->aFrom[iEX];
2335 pB = &p->aTo[iEY];
2336 n = minInt(iE1-iEX, iE2-iEY);
2337 for(k=0; k<n && p->xDiffer(pA,pB)==0; k++, pA++, pB++){}
2338 iEX += k;
2339 iEY += k;
2340 skew = (iSX-iS1) - (iSY-iS2);
2341 if( skew<0 ) skew = -skew;
2342 dist = (iSX+iEX)/2 - mid;
2343 if( dist<0 ) dist = -dist;
2344 score = (iEX - iSX)*(sqlite3_int64)span - (skew + dist);
2345 if( score>bestScore ){
2346 bestScore = score;
2347 iSXb = iSX;
2348 iSYb = iSY;
2349 iEXb = iEX;
2350 iEYb = iEY;
2351 }else if( iEX>iEXp ){
2352 iSXp = iSX;
2353 iSYp = iSY;
2354 iEXp = iEX;
2355 iEYp = iEY;
2356 }
2357 }
2358 }while( iSXb==iEXb && nextCutoff && (cutoff=nextCutoff)<=64 );
2359 if( iSXb==iEXb && (sqlite3_int64)(iE1-iS1)*(iE2-iS2)<2500 ){
2360 /* If no common sequence is found using the hashing heuristic and
2361 ** the input is not too big, use the expensive exact solution */
2362 optimalLCS(p, iS1, iE1, iS2, iE2, piSX, piEX, piSY, piEY);
2363 }else{
2364 *piSX = iSXb;
2365

Keyboard Shortcuts

Open search /
Next entry (timeline) j
Previous entry (timeline) k
Open focused entry Enter
Show this help ?
Toggle theme Top nav button