Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
| Comment: | Optimize the inner loop of the LCS algorithm for the main diff generator. |
|---|---|
| Downloads: | Tarball | ZIP archive |
| Timelines: | family | ancestors | descendants | both | trunk |
| Files: | files | file ages | folders |
| SHA1: |
4ab6071145a7fe02a114661ee94ea006 |
| User & Date: | drh 2012-02-07 18:13:47.499 |
Context
|
2012-02-07
| ||
| 18:58 | Performance optimization for the alignment calculation on side-by-side diffs. Noticably faster. ... (check-in: 87f867018b user: drh tags: trunk) | |
| 18:13 | Optimize the inner loop of the LCS algorithm for the main diff generator. ... (check-in: 4ab6071145 user: drh tags: trunk) | |
| 16:20 | Update the built-in SQLite and SQL command-line shell to the latest code from the SQLite trunk. ... (check-in: 030035345c user: drh tags: trunk) | |
Changes
Changes to src/diff.c.
| ︙ | ︙ | |||
895 896 897 898 899 900 901 902 903 904 905 906 907 908 | } *piSX = iSXb; *piEX = iSXb + mxLength; *piSY = iSYb; *piEY = iSYb + mxLength; } /* ** Compare two blocks of text on lines iS1 through iE1-1 of the aFrom[] ** file and lines iS2 through iE2-1 of the aTo[] file. Locate a sequence ** of lines in these two blocks that are exactly the same. Return ** the bounds of the matching sequence. ** ** If there are two or more possible answers of the same length, the | > > > > > | 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 |
}
*piSX = iSXb;
*piEX = iSXb + mxLength;
*piSY = iSYb;
*piEY = iSYb + mxLength;
}
/*
** Minimum of two values
*/
static int minInt(int a, int b){ return a<b ? a : b; }
/*
** Compare two blocks of text on lines iS1 through iE1-1 of the aFrom[]
** file and lines iS2 through iE2-1 of the aTo[] file. Locate a sequence
** of lines in these two blocks that are exactly the same. Return
** the bounds of the matching sequence.
**
** If there are two or more possible answers of the same length, the
|
| ︙ | ︙ | |||
921 922 923 924 925 926 927 |
DContext *p, /* Two files being compared */
int iS1, int iE1, /* Range of lines in p->aFrom[] */
int iS2, int iE2, /* Range of lines in p->aTo[] */
int *piSX, int *piEX, /* Write p->aFrom[] common segment here */
int *piSY, int *piEY /* Write p->aTo[] common segment here */
){
double bestScore = -1e30; /* Best score seen so far */
| > | > | 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 |
DContext *p, /* Two files being compared */
int iS1, int iE1, /* Range of lines in p->aFrom[] */
int iS2, int iE2, /* Range of lines in p->aTo[] */
int *piSX, int *piEX, /* Write p->aFrom[] common segment here */
int *piSY, int *piEY /* Write p->aTo[] common segment here */
){
double bestScore = -1e30; /* Best score seen so far */
int i, j, k; /* Loop counters */
int n; /* Loop limit */
DLine *pA, *pB; /* Pointers to lines */
int iSX, iSY, iEX, iEY; /* Current match */
double score; /* Current score */
int skew; /* How lopsided is the match */
int dist; /* Distance of match from center */
int mid; /* Center of the span */
int iSXb, iSYb, iEXb, iEYb; /* Best match so far */
int iSXp, iSYp, iEXp, iEYp; /* Previous match */
|
| ︙ | ︙ | |||
954 955 956 957 958 959 960 |
}
if( j==0 ) continue;
assert( i>=iSXb && i>=iSXp );
if( i<iEXb && j>=iSYb && j<iEYb ) continue;
if( i<iEXp && j>=iSYp && j<iEYp ) continue;
iSX = i;
iSY = j-1;
| | > > > | | < | > > > | | < | 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 |
}
if( j==0 ) continue;
assert( i>=iSXb && i>=iSXp );
if( i<iEXb && j>=iSYb && j<iEYb ) continue;
if( i<iEXp && j>=iSYp && j<iEYp ) continue;
iSX = i;
iSY = j-1;
pA = &p->aFrom[iSX-1];
pB = &p->aTo[iSY-1];
n = minInt(iSX-iS1, iSY-iS2);
for(k=0; k<n && same_dline(pA,pB); k++, pA--, pB--){}
iSX -= k;
iSY -= k;
iEX = i+1;
iEY = j;
pA = &p->aFrom[iEX];
pB = &p->aTo[iEY];
n = minInt(iE1-iEX, iE2-iEY);
for(k=0; k<n && same_dline(pA,pB); k++, pA++, pB++){}
iEX += k;
iEY += k;
skew = (iSX-iS1) - (iSY-iS2);
if( skew<0 ) skew = -skew;
dist = (iSX+iEX)/2 - mid;
if( dist<0 ) dist = -dist;
score = (iEX - iSX) - 0.05*skew - 0.05*dist;
if( score>bestScore ){
bestScore = score;
|
| ︙ | ︙ |