Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
| Comment: | Simplify the logic in the cell redistribution loop of balance_nonroot(). Enhance and clarify comments and add assert() statements for additional verification of correctness. |
|---|---|
| Downloads: | Tarball | ZIP archive |
| Timelines: | family | ancestors | descendants | both | trunk |
| Files: | files | file ages | folders |
| SHA1: |
a07078b60007e88adea67bec5f0caf91 |
| User & Date: | drh 2014-10-31 14:26:36.417 |
Context
|
2014-10-31
| ||
| 14:46 | Change the command-line shell man-page to use the ".tr" troff directive instead of ".cc" for escaping the initial "." characters in the ".help" output. (check-in: 67f0d469da user: drh tags: trunk) | |
| 14:26 | Simplify the logic in the cell redistribution loop of balance_nonroot(). Enhance and clarify comments and add assert() statements for additional verification of correctness. (check-in: a07078b600 user: drh tags: trunk) | |
| 12:22 | Simplify the math slightly, and reduce by one the number of loop iterations, for the loop in balance_nonroot() that moves cells between pages. (check-in: 2e838db82e user: drh tags: trunk) | |
Changes
Changes to src/btree.c.
| ︙ | ︙ | |||
7022 7023 7024 7025 7026 7027 7028 |
assert( sqlite3PagerIswriteable(pParent->pDbPage) );
}
/* Now update the actual sibling pages. The order in which they are updated
** is important, as this code needs to avoid disrupting any page from which
** cells may still to be read. In practice, this means:
**
| | | | | | | > > > > > > > > < | > | < > > > > > > > > | > > | 7022 7023 7024 7025 7026 7027 7028 7029 7030 7031 7032 7033 7034 7035 7036 7037 7038 7039 7040 7041 7042 7043 7044 7045 7046 7047 7048 7049 7050 7051 7052 7053 7054 7055 7056 7057 7058 7059 7060 7061 7062 7063 7064 7065 7066 7067 7068 7069 7070 7071 7072 7073 7074 7075 7076 7077 7078 7079 7080 7081 7082 7083 7084 7085 7086 7087 7088 7089 7090 |
assert( sqlite3PagerIswriteable(pParent->pDbPage) );
}
/* Now update the actual sibling pages. The order in which they are updated
** is important, as this code needs to avoid disrupting any page from which
** cells may still to be read. In practice, this means:
**
** (1) If cells are moving left (from apNew[iPg] to apNew[iPg-1])
** then it is not safe to update page apNew[iPg] until after
** the left-hand sibling apNew[iPg-1] has been updated.
**
** (2) If cells are moving right (from apNew[iPg] to apNew[iPg+1])
** then it is not safe to update page apNew[iPg] until after
** the right-hand sibling apNew[iPg+1] has been updated.
**
** If neither of the above apply, the page is safe to update.
**
** The iPg value in the following loop starts at nNew-1 goes down
** to 0, then back up to nNew-1 again, thus making two passes over
** the pages. On the initial downward pass, only condition (1) above
** needs to be tested because (2) will always be true from the previous
** step. On the upward pass, both conditions are always true, so the
** upwards pass simply processes pages that were missed on the downward
** pass.
*/
for(i=1-nNew; i<nNew; i++){
int iPg = i<0 ? -i : i;
assert( iPg>=0 && iPg<nNew );
if( abDone[iPg] ) continue; /* Skip pages already processed */
if( i>=0 /* On the upwards pass, or... */
|| cntOld[iPg-1]>=cntNew[iPg-1] /* Condition (1) is true */
){
int iNew;
int iOld;
int nNewCell;
/* Verify condition (1): If cells are moving left, update iPg
** only after iPg-1 has already been updated. */
assert( iPg==0 || cntOld[iPg-1]>=cntNew[iPg-1] || abDone[iPg-1] );
/* Verify condition (2): If cells are moving right, update iPg
** only after iPg+1 has already been updated. */
assert( cntNew[iPg]>=cntOld[iPg] || abDone[iPg+1] );
if( iPg==0 ){
iNew = iOld = 0;
nNewCell = cntNew[0];
}else{
iOld = iPg<nOld ? (cntOld[iPg-1] + !leafData) : nCell;
iNew = cntNew[iPg-1] + !leafData;
nNewCell = cntNew[iPg] - iNew;
}
editPage(apNew[iPg], iOld, iNew, nNewCell, apCell, szCell);
abDone[iPg]++;
apNew[iPg]->nFree = usableSpace-szNew[iPg];
assert( apNew[iPg]->nOverflow==0 );
assert( apNew[iPg]->nCell==nNewCell );
}
}
/* All pages have been processed exactly once */
assert( memcmp(abDone, "\01\01\01\01\01", nNew)==0 );
assert( nOld>0 );
assert( nNew>0 );
if( isRoot && pParent->nCell==0 && pParent->hdrOffset<=apNew[0]->nFree ){
/* The root page of the b-tree now contains no cells. The only sibling
|
| ︙ | ︙ |