Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
| Comment: | Save a 78 bytes of code space and a million CPU cycles in speedtest1 by storing the cell index for the leaf page in the BtCursor object in its own field (BtCursor.ix), rather than as an entry in the BtCursor.aiIdx array. |
|---|---|
| Downloads: | Tarball | ZIP archive | SQL archive |
| Timelines: | family | ancestors | descendants | both | trunk |
| Files: | files | file ages | folders |
| SHA3-256: |
2452f0617d1085689264b5f66681788c |
| User & Date: | drh 2017-04-01 00:20:06 |
Context
|
2017-04-01
| ||
| 11:40 | Remove unused fields from the BtCursor object. (check-in: 1c0d82e0 user: drh tags: trunk) | |
| 00:20 | Save a 78 bytes of code space and a million CPU cycles in speedtest1 by storing the cell index for the leaf page in the BtCursor object in its own field (BtCursor.ix), rather than as an entry in the BtCursor.aiIdx array. (check-in: 2452f061 user: drh tags: trunk) | |
|
2017-03-30
| ||
| 17:13 | Declare the Lemon-generated parser object as itself. (Duh) (check-in: c8000e94 user: drh tags: trunk) | |
Changes
Changes to src/btree.c.
4313 4314 4315 4316 4317 4318 4319 4320 4321 4322 4323 4324 4325 4326 4327 4328 4329 4330 4331 4332 4333 4334 4335 4336 4337 .... 4530 4531 4532 4533 4534 4535 4536 4537 4538 4539 4540 4541 4542 4543 4544 .... 4717 4718 4719 4720 4721 4722 4723 4724 4725 4726 4727 4728 4729 4730 4731 .... 4779 4780 4781 4782 4783 4784 4785 4786 4787 4788 4789 4790 4791 4792 4793 .... 4830 4831 4832 4833 4834 4835 4836 4837 4838 4839 4840 4841 4842 4843 4844 4845 .... 4879 4880 4881 4882 4883 4884 4885 4886 4887 4888 4889 4890 4891 4892 .... 4960 4961 4962 4963 4964 4965 4966 4967 4968 4969 4970 4971 4972 4973 4974 .... 4994 4995 4996 4997 4998 4999 5000 5001 5002 5003 5004 5005 5006 5007 5008 5009 .... 5020 5021 5022 5023 5024 5025 5026 5027 5028 5029 5030 5031 5032 5033 5034 5035 5036 5037 5038 .... 5072 5073 5074 5075 5076 5077 5078 5079 5080 5081 5082 5083 5084 5085 5086 .... 5219 5220 5221 5222 5223 5224 5225 5226 5227 5228 5229 5230 5231 5232 5233 .... 5238 5239 5240 5241 5242 5243 5244 5245 5246 5247 5248 5249 5250 5251 5252 .... 5307 5308 5309 5310 5311 5312 5313 5314 5315 5316 5317 5318 5319 5320 5321 .... 5329 5330 5331 5332 5333 5334 5335 5336 5337 5338 5339 5340 5341 5342 5343 5344 5345 5346 5347 5348 5349 5350 5351 5352 5353 5354 5355 5356 5357 5358 5359 5360 5361 5362 5363 5364 5365 5366 5367 .... 5454 5455 5456 5457 5458 5459 5460 5461 5462 5463 5464 5465 5466 5467 5468 .... 5478 5479 5480 5481 5482 5483 5484 5485 5486 5487 5488 5489 5490 5491 5492 .... 5502 5503 5504 5505 5506 5507 5508 5509 5510 5511 5512 5513 5514 5515 5516 5517 .... 5567 5568 5569 5570 5571 5572 5573 5574 5575 5576 5577 5578 5579 5580 5581 5582 5583 5584 5585 5586 5587 5588 5589 5590 5591 5592 5593 5594 5595 5596 5597 .... 5602 5603 5604 5605 5606 5607 5608 5609 5610 5611 5612 5613 5614 5615 5616 5617 5618 5619 5620 5621 .... 7929 7930 7931 7932 7933 7934 7935 7936 7937 7938 7939 7940 7941 7942 7943 7944 .... 8159 8160 8161 8162 8163 8164 8165 8166 8167 8168 8169 8170 8171 8172 8173 .... 8187 8188 8189 8190 8191 8192 8193 8194 8195 8196 8197 8198 8199 8200 8201 .... 8283 8284 8285 8286 8287 8288 8289 8290 8291 8292 8293 8294 8295 8296 8297 8298 8299 8300 8301 8302 .... 8405 8406 8407 8408 8409 8410 8411 8412 8413 8414 8415 8416 8417 8418 8419 .... 8918 8919 8920 8921 8922 8923 8924 8925 8926 8927 8928 8929 8930 8931 8932 8933 8934 8935 8936 8937 8938 8939 8940 8941 |
** Using this cache reduces the number of calls to btreeParseCell().
*/
#ifndef NDEBUG
static void assertCellInfo(BtCursor *pCur){
CellInfo info;
int iPage = pCur->iPage;
memset(&info, 0, sizeof(info));
btreeParseCell(pCur->apPage[iPage], pCur->aiIdx[iPage], &info);
assert( CORRUPT_DB || memcmp(&info, &pCur->info, sizeof(info))==0 );
}
#else
#define assertCellInfo(x)
#endif
static SQLITE_NOINLINE void getCellInfo(BtCursor *pCur){
if( pCur->info.nSize==0 ){
int iPage = pCur->iPage;
pCur->curFlags |= BTCF_ValidNKey;
btreeParseCell(pCur->apPage[iPage],pCur->aiIdx[iPage],&pCur->info);
}else{
assertCellInfo(pCur);
}
}
#ifndef NDEBUG /* The next routine used only within assert() statements */
/*
................................................................................
#ifdef SQLITE_DIRECT_OVERFLOW_READ
unsigned char * const pBufStart = pBuf; /* Start of original out buffer */
#endif
assert( pPage );
assert( eOp==0 || eOp==1 );
assert( pCur->eState==CURSOR_VALID );
assert( pCur->aiIdx[pCur->iPage]<pPage->nCell );
assert( cursorHoldsMutex(pCur) );
getCellInfo(pCur);
aPayload = pCur->info.pPayload;
assert( offset+amt <= pCur->info.nPayload );
assert( aPayload > pPage->aData );
................................................................................
** wrong. An error is returned if "offset+amt" is larger than
** the available payload.
*/
int sqlite3BtreePayload(BtCursor *pCur, u32 offset, u32 amt, void *pBuf){
assert( cursorHoldsMutex(pCur) );
assert( pCur->eState==CURSOR_VALID );
assert( pCur->iPage>=0 && pCur->apPage[pCur->iPage] );
assert( pCur->aiIdx[pCur->iPage]<pCur->apPage[pCur->iPage]->nCell );
return accessPayload(pCur, offset, amt, (unsigned char*)pBuf, 0);
}
/*
** This variant of sqlite3BtreePayload() works even if the cursor has not
** in the CURSOR_VALID state. It is only used by the sqlite3_blob_read()
** interface.
................................................................................
u32 *pAmt /* Write the number of available bytes here */
){
u32 amt;
assert( pCur!=0 && pCur->iPage>=0 && pCur->apPage[pCur->iPage]);
assert( pCur->eState==CURSOR_VALID );
assert( sqlite3_mutex_held(pCur->pBtree->db->mutex) );
assert( cursorOwnsBtShared(pCur) );
assert( pCur->aiIdx[pCur->iPage]<pCur->apPage[pCur->iPage]->nCell );
assert( pCur->info.nSize>0 );
assert( pCur->info.pPayload>pCur->apPage[pCur->iPage]->aData || CORRUPT_DB );
assert( pCur->info.pPayload<pCur->apPage[pCur->iPage]->aDataEnd ||CORRUPT_DB);
amt = (int)(pCur->apPage[pCur->iPage]->aDataEnd - pCur->info.pPayload);
if( pCur->info.nLocal<amt ) amt = pCur->info.nLocal;
*pAmt = amt;
return (void*)pCur->info.pPayload;
................................................................................
assert( pCur->iPage<BTCURSOR_MAX_DEPTH );
assert( pCur->iPage>=0 );
if( pCur->iPage>=(BTCURSOR_MAX_DEPTH-1) ){
return SQLITE_CORRUPT_BKPT;
}
pCur->info.nSize = 0;
pCur->curFlags &= ~(BTCF_ValidNKey|BTCF_ValidOvfl);
pCur->iPage++;
pCur->aiIdx[pCur->iPage] = 0;
return getAndInitPage(pBt, newPgno, &pCur->apPage[pCur->iPage],
pCur, pCur->curPagerFlags);
}
#ifdef SQLITE_DEBUG
/*
** Page pParent is an internal (non-leaf) tree page. This function
................................................................................
pCur->apPage[pCur->iPage-1],
pCur->aiIdx[pCur->iPage-1],
pCur->apPage[pCur->iPage]->pgno
);
testcase( pCur->aiIdx[pCur->iPage-1] > pCur->apPage[pCur->iPage-1]->nCell );
pCur->info.nSize = 0;
pCur->curFlags &= ~(BTCF_ValidNKey|BTCF_ValidOvfl);
releasePageNotNull(pCur->apPage[pCur->iPage--]);
}
/*
** Move the cursor to point to the root page of its b-tree structure.
**
** If the table has a virtual root page, then the cursor is moved to point
................................................................................
** (or the freelist). */
assert( pRoot->intKey==1 || pRoot->intKey==0 );
if( pRoot->isInit==0 || (pCur->pKeyInfo==0)!=pRoot->intKey ){
return SQLITE_CORRUPT_BKPT;
}
skip_init:
pCur->aiIdx[0] = 0;
pCur->info.nSize = 0;
pCur->curFlags &= ~(BTCF_AtLast|BTCF_ValidNKey|BTCF_ValidOvfl);
pRoot = pCur->apPage[0];
if( pRoot->nCell>0 ){
pCur->eState = CURSOR_VALID;
}else if( !pRoot->leaf ){
................................................................................
Pgno pgno;
int rc = SQLITE_OK;
MemPage *pPage;
assert( cursorOwnsBtShared(pCur) );
assert( pCur->eState==CURSOR_VALID );
while( rc==SQLITE_OK && !(pPage = pCur->apPage[pCur->iPage])->leaf ){
assert( pCur->aiIdx[pCur->iPage]<pPage->nCell );
pgno = get4byte(findCell(pPage, pCur->aiIdx[pCur->iPage]));
rc = moveToChild(pCur, pgno);
}
return rc;
}
/*
** Move the cursor down to the right-most leaf entry beneath the
................................................................................
int rc = SQLITE_OK;
MemPage *pPage = 0;
assert( cursorOwnsBtShared(pCur) );
assert( pCur->eState==CURSOR_VALID );
while( !(pPage = pCur->apPage[pCur->iPage])->leaf ){
pgno = get4byte(&pPage->aData[pPage->hdrOffset+8]);
pCur->aiIdx[pCur->iPage] = pPage->nCell;
rc = moveToChild(pCur, pgno);
if( rc ) return rc;
}
pCur->aiIdx[pCur->iPage] = pPage->nCell-1;
assert( pCur->info.nSize==0 );
assert( (pCur->curFlags & BTCF_ValidNKey)==0 );
return SQLITE_OK;
}
/* Move the cursor to the first entry in the table. Return SQLITE_OK
** on success. Set *pRes to 0 if the cursor actually points to something
................................................................................
#ifdef SQLITE_DEBUG
/* This block serves to assert() that the cursor really does point
** to the last entry in the b-tree. */
int ii;
for(ii=0; ii<pCur->iPage; ii++){
assert( pCur->aiIdx[ii]==pCur->apPage[ii]->nCell );
}
assert( pCur->aiIdx[pCur->iPage]==pCur->apPage[pCur->iPage]->nCell-1 );
assert( pCur->apPage[pCur->iPage]->leaf );
#endif
return SQLITE_OK;
}
rc = moveToRoot(pCur);
if( rc==SQLITE_OK ){
................................................................................
** a moveToChild() or moveToRoot() call would have detected corruption. */
assert( pPage->nCell>0 );
assert( pPage->intKey==(pIdxKey==0) );
lwr = 0;
upr = pPage->nCell-1;
assert( biasRight==0 || biasRight==1 );
idx = upr>>(1-biasRight); /* idx = biasRight ? upr : (lwr+upr)/2; */
pCur->aiIdx[pCur->iPage] = (u16)idx;
if( xRecordCompare==0 ){
for(;;){
i64 nCellKey;
pCell = findCellPastPtr(pPage, idx);
if( pPage->intKeyLeaf ){
while( 0x80 <= *(pCell++) ){
if( pCell>=pPage->aDataEnd ) return SQLITE_CORRUPT_BKPT;
................................................................................
lwr = idx+1;
if( lwr>upr ){ c = -1; break; }
}else if( nCellKey>intKey ){
upr = idx-1;
if( lwr>upr ){ c = +1; break; }
}else{
assert( nCellKey==intKey );
pCur->aiIdx[pCur->iPage] = (u16)idx;
if( !pPage->leaf ){
lwr = idx;
goto moveto_next_layer;
}else{
pCur->curFlags |= BTCF_ValidNKey;
pCur->info.nKey = nCellKey;
pCur->info.nSize = 0;
................................................................................
goto moveto_finish;
}
pCellKey = sqlite3Malloc( nCell+18 );
if( pCellKey==0 ){
rc = SQLITE_NOMEM_BKPT;
goto moveto_finish;
}
pCur->aiIdx[pCur->iPage] = (u16)idx;
rc = accessPayload(pCur, 0, nCell, (unsigned char*)pCellKey, 0);
pCur->curFlags &= ~BTCF_ValidOvfl;
if( rc ){
sqlite3_free(pCellKey);
goto moveto_finish;
}
c = xRecordCompare(nCell, pCellKey, pIdxKey);
................................................................................
lwr = idx+1;
}else if( c>0 ){
upr = idx-1;
}else{
assert( c==0 );
*pRes = 0;
rc = SQLITE_OK;
pCur->aiIdx[pCur->iPage] = (u16)idx;
if( pIdxKey->errCode ) rc = SQLITE_CORRUPT;
goto moveto_finish;
}
if( lwr>upr ) break;
assert( lwr+upr>=0 );
idx = (lwr+upr)>>1; /* idx = (lwr+upr)/2 */
}
}
assert( lwr==upr+1 || (pPage->intKey && !pPage->leaf) );
assert( pPage->isInit );
if( pPage->leaf ){
assert( pCur->aiIdx[pCur->iPage]<pCur->apPage[pCur->iPage]->nCell );
pCur->aiIdx[pCur->iPage] = (u16)idx;
*pRes = c;
rc = SQLITE_OK;
goto moveto_finish;
}
moveto_next_layer:
if( lwr>=pPage->nCell ){
chldPg = get4byte(&pPage->aData[pPage->hdrOffset+8]);
}else{
chldPg = get4byte(findCell(pPage, lwr));
}
pCur->aiIdx[pCur->iPage] = (u16)lwr;
rc = moveToChild(pCur, chldPg);
if( rc ) break;
}
moveto_finish:
pCur->info.nSize = 0;
assert( (pCur->curFlags & BTCF_ValidOvfl)==0 );
return rc;
................................................................................
return SQLITE_OK;
}
pCur->skipNext = 0;
}
}
pPage = pCur->apPage[pCur->iPage];
idx = ++pCur->aiIdx[pCur->iPage];
assert( pPage->isInit );
/* If the database file is corrupt, it is possible for the value of idx
** to be invalid here. This can only occur if a second cursor modifies
** the page while cursor pCur is holding a reference to it. Which can
** only happen if the database is corrupt in such a way as to link the
** page into more than one b-tree structure. */
................................................................................
if( pCur->iPage==0 ){
*pRes = 1;
pCur->eState = CURSOR_INVALID;
return SQLITE_OK;
}
moveToParent(pCur);
pPage = pCur->apPage[pCur->iPage];
}while( pCur->aiIdx[pCur->iPage]>=pPage->nCell );
if( pPage->intKey ){
return sqlite3BtreeNext(pCur, pRes);
}else{
return SQLITE_OK;
}
}
if( pPage->leaf ){
................................................................................
assert( *pRes==0 || *pRes==1 );
assert( pCur->skipNext==0 || pCur->eState!=CURSOR_VALID );
pCur->info.nSize = 0;
pCur->curFlags &= ~(BTCF_ValidNKey|BTCF_ValidOvfl);
*pRes = 0;
if( pCur->eState!=CURSOR_VALID ) return btreeNext(pCur, pRes);
pPage = pCur->apPage[pCur->iPage];
if( (++pCur->aiIdx[pCur->iPage])>=pPage->nCell ){
pCur->aiIdx[pCur->iPage]--;
return btreeNext(pCur, pRes);
}
if( pPage->leaf ){
return SQLITE_OK;
}else{
return moveToLeftmost(pCur);
}
................................................................................
pCur->skipNext = 0;
}
}
pPage = pCur->apPage[pCur->iPage];
assert( pPage->isInit );
if( !pPage->leaf ){
int idx = pCur->aiIdx[pCur->iPage];
rc = moveToChild(pCur, get4byte(findCell(pPage, idx)));
if( rc ) return rc;
rc = moveToRightmost(pCur);
}else{
while( pCur->aiIdx[pCur->iPage]==0 ){
if( pCur->iPage==0 ){
pCur->eState = CURSOR_INVALID;
*pRes = 1;
return SQLITE_OK;
}
moveToParent(pCur);
}
assert( pCur->info.nSize==0 );
assert( (pCur->curFlags & (BTCF_ValidOvfl))==0 );
pCur->aiIdx[pCur->iPage]--;
pPage = pCur->apPage[pCur->iPage];
if( pPage->intKey && !pPage->leaf ){
rc = sqlite3BtreePrevious(pCur, pRes);
}else{
rc = SQLITE_OK;
}
}
................................................................................
assert( pRes!=0 );
assert( *pRes==0 || *pRes==1 );
assert( pCur->skipNext==0 || pCur->eState!=CURSOR_VALID );
*pRes = 0;
pCur->curFlags &= ~(BTCF_AtLast|BTCF_ValidOvfl|BTCF_ValidNKey);
pCur->info.nSize = 0;
if( pCur->eState!=CURSOR_VALID
|| pCur->aiIdx[pCur->iPage]==0
|| pCur->apPage[pCur->iPage]->leaf==0
){
return btreePrevious(pCur, pRes);
}
pCur->aiIdx[pCur->iPage]--;
return SQLITE_OK;
}
/*
** Allocate a new page from the database file.
**
** The new page is marked as dirty. (In other words, sqlite3PagerWrite()
................................................................................
** next iteration of the do-loop will balance the child page.
*/
assert( balance_deeper_called==0 );
VVA_ONLY( balance_deeper_called++ );
rc = balance_deeper(pPage, &pCur->apPage[1]);
if( rc==SQLITE_OK ){
pCur->iPage = 1;
pCur->aiIdx[0] = 0;
pCur->aiIdx[1] = 0;
assert( pCur->apPage[1]->nOverflow );
}
}else{
break;
}
}else if( pPage->nOverflow==0 && pPage->nFree<=nMin ){
break;
................................................................................
assert( pPage->isInit );
newCell = pBt->pTmpSpace;
assert( newCell!=0 );
rc = fillInCell(pPage, newCell, pX, &szNew);
if( rc ) goto end_insert;
assert( szNew==pPage->xCellSize(pPage, newCell) );
assert( szNew <= MX_CELL_SIZE(pBt) );
idx = pCur->aiIdx[pCur->iPage];
if( loc==0 ){
CellInfo info;
assert( idx<pPage->nCell );
rc = sqlite3PagerWrite(pPage->pDbPage);
if( rc ){
goto end_insert;
}
................................................................................
memcpy(oldCell, newCell, szNew);
return SQLITE_OK;
}
dropCell(pPage, idx, info.nSize, &rc);
if( rc ) goto end_insert;
}else if( loc<0 && pPage->nCell>0 ){
assert( pPage->leaf );
idx = ++pCur->aiIdx[pCur->iPage];
}else{
assert( pPage->leaf );
}
insertCell(pPage, idx, newCell, szNew, 0, 0, &rc);
assert( pPage->nOverflow==0 || rc==SQLITE_OK );
assert( rc!=SQLITE_OK || pPage->nCell>0 || pPage->nOverflow>0 );
................................................................................
assert( cursorOwnsBtShared(pCur) );
assert( pBt->inTransaction==TRANS_WRITE );
assert( (pBt->btsFlags & BTS_READ_ONLY)==0 );
assert( pCur->curFlags & BTCF_WriteFlag );
assert( hasSharedCacheTableLock(p, pCur->pgnoRoot, pCur->pKeyInfo!=0, 2) );
assert( !hasReadConflicts(p, pCur->pgnoRoot) );
assert( pCur->aiIdx[pCur->iPage]<pCur->apPage[pCur->iPage]->nCell );
assert( pCur->eState==CURSOR_VALID );
assert( (flags & ~(BTREE_SAVEPOSITION | BTREE_AUXDELETE))==0 );
iCellDepth = pCur->iPage;
iCellIdx = pCur->aiIdx[iCellDepth];
pPage = pCur->apPage[iCellDepth];
pCell = findCell(pPage, iCellIdx);
/* If the bPreserve flag is set to true, then the cursor position must
** be preserved following this delete operation. If the current delete
** will cause a b-tree rebalance, then this is done by saving the cursor
** key and leaving the cursor in CURSOR_REQUIRESEEK state before
................................................................................
if( bSkipnext ){
assert( bPreserve && (pCur->iPage==iCellDepth || CORRUPT_DB) );
assert( pPage==pCur->apPage[pCur->iPage] || CORRUPT_DB );
assert( (pPage->nCell>0 || CORRUPT_DB) && iCellIdx<=pPage->nCell );
pCur->eState = CURSOR_SKIPNEXT;
if( iCellIdx>=pPage->nCell ){
pCur->skipNext = -1;
pCur->aiIdx[iCellDepth] = pPage->nCell-1;
}else{
pCur->skipNext = 1;
}
}else{
rc = moveToRoot(pCur);
if( bPreserve ){
pCur->eState = CURSOR_REQUIRESEEK;
................................................................................
do {
if( pCur->iPage==0 ){
/* All pages of the b-tree have been visited. Return successfully. */
*pnEntry = nEntry;
return moveToRoot(pCur);
}
moveToParent(pCur);
}while ( pCur->aiIdx[pCur->iPage]>=pCur->apPage[pCur->iPage]->nCell );
pCur->aiIdx[pCur->iPage]++;
pPage = pCur->apPage[pCur->iPage];
}
/* Descend to the child node of the cell that the cursor currently
** points at. This is the right-child if (iIdx==pPage->nCell).
*/
iIdx = pCur->aiIdx[pCur->iPage];
if( iIdx==pPage->nCell ){
rc = moveToChild(pCur, get4byte(&pPage->aData[pPage->hdrOffset+8]));
}else{
rc = moveToChild(pCur, get4byte(findCell(pPage, iIdx)));
}
}
|
| | | | | | | > | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
4313 4314 4315 4316 4317 4318 4319 4320 4321 4322 4323 4324 4325 4326 4327 4328 4329 4330 4331 4332 4333 4334 4335 4336 4337 .... 4530 4531 4532 4533 4534 4535 4536 4537 4538 4539 4540 4541 4542 4543 4544 .... 4717 4718 4719 4720 4721 4722 4723 4724 4725 4726 4727 4728 4729 4730 4731 .... 4779 4780 4781 4782 4783 4784 4785 4786 4787 4788 4789 4790 4791 4792 4793 .... 4830 4831 4832 4833 4834 4835 4836 4837 4838 4839 4840 4841 4842 4843 4844 4845 .... 4879 4880 4881 4882 4883 4884 4885 4886 4887 4888 4889 4890 4891 4892 4893 .... 4961 4962 4963 4964 4965 4966 4967 4968 4969 4970 4971 4972 4973 4974 4975 .... 4995 4996 4997 4998 4999 5000 5001 5002 5003 5004 5005 5006 5007 5008 5009 5010 .... 5021 5022 5023 5024 5025 5026 5027 5028 5029 5030 5031 5032 5033 5034 5035 5036 5037 5038 5039 .... 5073 5074 5075 5076 5077 5078 5079 5080 5081 5082 5083 5084 5085 5086 5087 .... 5220 5221 5222 5223 5224 5225 5226 5227 5228 5229 5230 5231 5232 5233 5234 .... 5239 5240 5241 5242 5243 5244 5245 5246 5247 5248 5249 5250 5251 5252 5253 .... 5308 5309 5310 5311 5312 5313 5314 5315 5316 5317 5318 5319 5320 5321 5322 .... 5330 5331 5332 5333 5334 5335 5336 5337 5338 5339 5340 5341 5342 5343 5344 5345 5346 5347 5348 5349 5350 5351 5352 5353 5354 5355 5356 5357 5358 5359 5360 5361 5362 5363 5364 5365 5366 5367 5368 .... 5455 5456 5457 5458 5459 5460 5461 5462 5463 5464 5465 5466 5467 5468 5469 .... 5479 5480 5481 5482 5483 5484 5485 5486 5487 5488 5489 5490 5491 5492 5493 .... 5503 5504 5505 5506 5507 5508 5509 5510 5511 5512 5513 5514 5515 5516 5517 5518 .... 5568 5569 5570 5571 5572 5573 5574 5575 5576 5577 5578 5579 5580 5581 5582 5583 5584 5585 5586 5587 5588 5589 5590 5591 5592 5593 5594 5595 5596 5597 5598 .... 5603 5604 5605 5606 5607 5608 5609 5610 5611 5612 5613 5614 5615 5616 5617 5618 5619 5620 5621 5622 .... 7930 7931 7932 7933 7934 7935 7936 7937 7938 7939 7940 7941 7942 7943 7944 7945 .... 8160 8161 8162 8163 8164 8165 8166 8167 8168 8169 8170 8171 8172 8173 8174 .... 8188 8189 8190 8191 8192 8193 8194 8195 8196 8197 8198 8199 8200 8201 8202 .... 8284 8285 8286 8287 8288 8289 8290 8291 8292 8293 8294 8295 8296 8297 8298 8299 8300 8301 8302 8303 .... 8406 8407 8408 8409 8410 8411 8412 8413 8414 8415 8416 8417 8418 8419 8420 .... 8919 8920 8921 8922 8923 8924 8925 8926 8927 8928 8929 8930 8931 8932 8933 8934 8935 8936 8937 8938 8939 8940 8941 8942 |
** Using this cache reduces the number of calls to btreeParseCell().
*/
#ifndef NDEBUG
static void assertCellInfo(BtCursor *pCur){
CellInfo info;
int iPage = pCur->iPage;
memset(&info, 0, sizeof(info));
btreeParseCell(pCur->apPage[iPage], pCur->ix, &info);
assert( CORRUPT_DB || memcmp(&info, &pCur->info, sizeof(info))==0 );
}
#else
#define assertCellInfo(x)
#endif
static SQLITE_NOINLINE void getCellInfo(BtCursor *pCur){
if( pCur->info.nSize==0 ){
int iPage = pCur->iPage;
pCur->curFlags |= BTCF_ValidNKey;
btreeParseCell(pCur->apPage[iPage],pCur->ix,&pCur->info);
}else{
assertCellInfo(pCur);
}
}
#ifndef NDEBUG /* The next routine used only within assert() statements */
/*
................................................................................
#ifdef SQLITE_DIRECT_OVERFLOW_READ
unsigned char * const pBufStart = pBuf; /* Start of original out buffer */
#endif
assert( pPage );
assert( eOp==0 || eOp==1 );
assert( pCur->eState==CURSOR_VALID );
assert( pCur->ix<pPage->nCell );
assert( cursorHoldsMutex(pCur) );
getCellInfo(pCur);
aPayload = pCur->info.pPayload;
assert( offset+amt <= pCur->info.nPayload );
assert( aPayload > pPage->aData );
................................................................................
** wrong. An error is returned if "offset+amt" is larger than
** the available payload.
*/
int sqlite3BtreePayload(BtCursor *pCur, u32 offset, u32 amt, void *pBuf){
assert( cursorHoldsMutex(pCur) );
assert( pCur->eState==CURSOR_VALID );
assert( pCur->iPage>=0 && pCur->apPage[pCur->iPage] );
assert( pCur->ix<pCur->apPage[pCur->iPage]->nCell );
return accessPayload(pCur, offset, amt, (unsigned char*)pBuf, 0);
}
/*
** This variant of sqlite3BtreePayload() works even if the cursor has not
** in the CURSOR_VALID state. It is only used by the sqlite3_blob_read()
** interface.
................................................................................
u32 *pAmt /* Write the number of available bytes here */
){
u32 amt;
assert( pCur!=0 && pCur->iPage>=0 && pCur->apPage[pCur->iPage]);
assert( pCur->eState==CURSOR_VALID );
assert( sqlite3_mutex_held(pCur->pBtree->db->mutex) );
assert( cursorOwnsBtShared(pCur) );
assert( pCur->ix<pCur->apPage[pCur->iPage]->nCell );
assert( pCur->info.nSize>0 );
assert( pCur->info.pPayload>pCur->apPage[pCur->iPage]->aData || CORRUPT_DB );
assert( pCur->info.pPayload<pCur->apPage[pCur->iPage]->aDataEnd ||CORRUPT_DB);
amt = (int)(pCur->apPage[pCur->iPage]->aDataEnd - pCur->info.pPayload);
if( pCur->info.nLocal<amt ) amt = pCur->info.nLocal;
*pAmt = amt;
return (void*)pCur->info.pPayload;
................................................................................
assert( pCur->iPage<BTCURSOR_MAX_DEPTH );
assert( pCur->iPage>=0 );
if( pCur->iPage>=(BTCURSOR_MAX_DEPTH-1) ){
return SQLITE_CORRUPT_BKPT;
}
pCur->info.nSize = 0;
pCur->curFlags &= ~(BTCF_ValidNKey|BTCF_ValidOvfl);
pCur->aiIdx[pCur->iPage++] = pCur->ix;
pCur->ix = 0;
return getAndInitPage(pBt, newPgno, &pCur->apPage[pCur->iPage],
pCur, pCur->curPagerFlags);
}
#ifdef SQLITE_DEBUG
/*
** Page pParent is an internal (non-leaf) tree page. This function
................................................................................
pCur->apPage[pCur->iPage-1],
pCur->aiIdx[pCur->iPage-1],
pCur->apPage[pCur->iPage]->pgno
);
testcase( pCur->aiIdx[pCur->iPage-1] > pCur->apPage[pCur->iPage-1]->nCell );
pCur->info.nSize = 0;
pCur->curFlags &= ~(BTCF_ValidNKey|BTCF_ValidOvfl);
pCur->ix = pCur->aiIdx[pCur->iPage-1];
releasePageNotNull(pCur->apPage[pCur->iPage--]);
}
/*
** Move the cursor to point to the root page of its b-tree structure.
**
** If the table has a virtual root page, then the cursor is moved to point
................................................................................
** (or the freelist). */
assert( pRoot->intKey==1 || pRoot->intKey==0 );
if( pRoot->isInit==0 || (pCur->pKeyInfo==0)!=pRoot->intKey ){
return SQLITE_CORRUPT_BKPT;
}
skip_init:
pCur->ix = 0;
pCur->info.nSize = 0;
pCur->curFlags &= ~(BTCF_AtLast|BTCF_ValidNKey|BTCF_ValidOvfl);
pRoot = pCur->apPage[0];
if( pRoot->nCell>0 ){
pCur->eState = CURSOR_VALID;
}else if( !pRoot->leaf ){
................................................................................
Pgno pgno;
int rc = SQLITE_OK;
MemPage *pPage;
assert( cursorOwnsBtShared(pCur) );
assert( pCur->eState==CURSOR_VALID );
while( rc==SQLITE_OK && !(pPage = pCur->apPage[pCur->iPage])->leaf ){
assert( pCur->ix<pPage->nCell );
pgno = get4byte(findCell(pPage, pCur->ix));
rc = moveToChild(pCur, pgno);
}
return rc;
}
/*
** Move the cursor down to the right-most leaf entry beneath the
................................................................................
int rc = SQLITE_OK;
MemPage *pPage = 0;
assert( cursorOwnsBtShared(pCur) );
assert( pCur->eState==CURSOR_VALID );
while( !(pPage = pCur->apPage[pCur->iPage])->leaf ){
pgno = get4byte(&pPage->aData[pPage->hdrOffset+8]);
pCur->ix = pPage->nCell;
rc = moveToChild(pCur, pgno);
if( rc ) return rc;
}
pCur->ix = pPage->nCell-1;
assert( pCur->info.nSize==0 );
assert( (pCur->curFlags & BTCF_ValidNKey)==0 );
return SQLITE_OK;
}
/* Move the cursor to the first entry in the table. Return SQLITE_OK
** on success. Set *pRes to 0 if the cursor actually points to something
................................................................................
#ifdef SQLITE_DEBUG
/* This block serves to assert() that the cursor really does point
** to the last entry in the b-tree. */
int ii;
for(ii=0; ii<pCur->iPage; ii++){
assert( pCur->aiIdx[ii]==pCur->apPage[ii]->nCell );
}
assert( pCur->ix==pCur->apPage[pCur->iPage]->nCell-1 );
assert( pCur->apPage[pCur->iPage]->leaf );
#endif
return SQLITE_OK;
}
rc = moveToRoot(pCur);
if( rc==SQLITE_OK ){
................................................................................
** a moveToChild() or moveToRoot() call would have detected corruption. */
assert( pPage->nCell>0 );
assert( pPage->intKey==(pIdxKey==0) );
lwr = 0;
upr = pPage->nCell-1;
assert( biasRight==0 || biasRight==1 );
idx = upr>>(1-biasRight); /* idx = biasRight ? upr : (lwr+upr)/2; */
pCur->ix = (u16)idx;
if( xRecordCompare==0 ){
for(;;){
i64 nCellKey;
pCell = findCellPastPtr(pPage, idx);
if( pPage->intKeyLeaf ){
while( 0x80 <= *(pCell++) ){
if( pCell>=pPage->aDataEnd ) return SQLITE_CORRUPT_BKPT;
................................................................................
lwr = idx+1;
if( lwr>upr ){ c = -1; break; }
}else if( nCellKey>intKey ){
upr = idx-1;
if( lwr>upr ){ c = +1; break; }
}else{
assert( nCellKey==intKey );
pCur->ix = (u16)idx;
if( !pPage->leaf ){
lwr = idx;
goto moveto_next_layer;
}else{
pCur->curFlags |= BTCF_ValidNKey;
pCur->info.nKey = nCellKey;
pCur->info.nSize = 0;
................................................................................
goto moveto_finish;
}
pCellKey = sqlite3Malloc( nCell+18 );
if( pCellKey==0 ){
rc = SQLITE_NOMEM_BKPT;
goto moveto_finish;
}
pCur->ix = (u16)idx;
rc = accessPayload(pCur, 0, nCell, (unsigned char*)pCellKey, 0);
pCur->curFlags &= ~BTCF_ValidOvfl;
if( rc ){
sqlite3_free(pCellKey);
goto moveto_finish;
}
c = xRecordCompare(nCell, pCellKey, pIdxKey);
................................................................................
lwr = idx+1;
}else if( c>0 ){
upr = idx-1;
}else{
assert( c==0 );
*pRes = 0;
rc = SQLITE_OK;
pCur->ix = (u16)idx;
if( pIdxKey->errCode ) rc = SQLITE_CORRUPT;
goto moveto_finish;
}
if( lwr>upr ) break;
assert( lwr+upr>=0 );
idx = (lwr+upr)>>1; /* idx = (lwr+upr)/2 */
}
}
assert( lwr==upr+1 || (pPage->intKey && !pPage->leaf) );
assert( pPage->isInit );
if( pPage->leaf ){
assert( pCur->ix<pCur->apPage[pCur->iPage]->nCell );
pCur->ix = (u16)idx;
*pRes = c;
rc = SQLITE_OK;
goto moveto_finish;
}
moveto_next_layer:
if( lwr>=pPage->nCell ){
chldPg = get4byte(&pPage->aData[pPage->hdrOffset+8]);
}else{
chldPg = get4byte(findCell(pPage, lwr));
}
pCur->ix = (u16)lwr;
rc = moveToChild(pCur, chldPg);
if( rc ) break;
}
moveto_finish:
pCur->info.nSize = 0;
assert( (pCur->curFlags & BTCF_ValidOvfl)==0 );
return rc;
................................................................................
return SQLITE_OK;
}
pCur->skipNext = 0;
}
}
pPage = pCur->apPage[pCur->iPage];
idx = ++pCur->ix;
assert( pPage->isInit );
/* If the database file is corrupt, it is possible for the value of idx
** to be invalid here. This can only occur if a second cursor modifies
** the page while cursor pCur is holding a reference to it. Which can
** only happen if the database is corrupt in such a way as to link the
** page into more than one b-tree structure. */
................................................................................
if( pCur->iPage==0 ){
*pRes = 1;
pCur->eState = CURSOR_INVALID;
return SQLITE_OK;
}
moveToParent(pCur);
pPage = pCur->apPage[pCur->iPage];
}while( pCur->ix>=pPage->nCell );
if( pPage->intKey ){
return sqlite3BtreeNext(pCur, pRes);
}else{
return SQLITE_OK;
}
}
if( pPage->leaf ){
................................................................................
assert( *pRes==0 || *pRes==1 );
assert( pCur->skipNext==0 || pCur->eState!=CURSOR_VALID );
pCur->info.nSize = 0;
pCur->curFlags &= ~(BTCF_ValidNKey|BTCF_ValidOvfl);
*pRes = 0;
if( pCur->eState!=CURSOR_VALID ) return btreeNext(pCur, pRes);
pPage = pCur->apPage[pCur->iPage];
if( (++pCur->ix)>=pPage->nCell ){
pCur->ix--;
return btreeNext(pCur, pRes);
}
if( pPage->leaf ){
return SQLITE_OK;
}else{
return moveToLeftmost(pCur);
}
................................................................................
pCur->skipNext = 0;
}
}
pPage = pCur->apPage[pCur->iPage];
assert( pPage->isInit );
if( !pPage->leaf ){
int idx = pCur->ix;
rc = moveToChild(pCur, get4byte(findCell(pPage, idx)));
if( rc ) return rc;
rc = moveToRightmost(pCur);
}else{
while( pCur->ix==0 ){
if( pCur->iPage==0 ){
pCur->eState = CURSOR_INVALID;
*pRes = 1;
return SQLITE_OK;
}
moveToParent(pCur);
}
assert( pCur->info.nSize==0 );
assert( (pCur->curFlags & (BTCF_ValidOvfl))==0 );
pCur->ix--;
pPage = pCur->apPage[pCur->iPage];
if( pPage->intKey && !pPage->leaf ){
rc = sqlite3BtreePrevious(pCur, pRes);
}else{
rc = SQLITE_OK;
}
}
................................................................................
assert( pRes!=0 );
assert( *pRes==0 || *pRes==1 );
assert( pCur->skipNext==0 || pCur->eState!=CURSOR_VALID );
*pRes = 0;
pCur->curFlags &= ~(BTCF_AtLast|BTCF_ValidOvfl|BTCF_ValidNKey);
pCur->info.nSize = 0;
if( pCur->eState!=CURSOR_VALID
|| pCur->ix==0
|| pCur->apPage[pCur->iPage]->leaf==0
){
return btreePrevious(pCur, pRes);
}
pCur->ix--;
return SQLITE_OK;
}
/*
** Allocate a new page from the database file.
**
** The new page is marked as dirty. (In other words, sqlite3PagerWrite()
................................................................................
** next iteration of the do-loop will balance the child page.
*/
assert( balance_deeper_called==0 );
VVA_ONLY( balance_deeper_called++ );
rc = balance_deeper(pPage, &pCur->apPage[1]);
if( rc==SQLITE_OK ){
pCur->iPage = 1;
pCur->ix = 0;
pCur->aiIdx[0] = 0;
assert( pCur->apPage[1]->nOverflow );
}
}else{
break;
}
}else if( pPage->nOverflow==0 && pPage->nFree<=nMin ){
break;
................................................................................
assert( pPage->isInit );
newCell = pBt->pTmpSpace;
assert( newCell!=0 );
rc = fillInCell(pPage, newCell, pX, &szNew);
if( rc ) goto end_insert;
assert( szNew==pPage->xCellSize(pPage, newCell) );
assert( szNew <= MX_CELL_SIZE(pBt) );
idx = pCur->ix;
if( loc==0 ){
CellInfo info;
assert( idx<pPage->nCell );
rc = sqlite3PagerWrite(pPage->pDbPage);
if( rc ){
goto end_insert;
}
................................................................................
memcpy(oldCell, newCell, szNew);
return SQLITE_OK;
}
dropCell(pPage, idx, info.nSize, &rc);
if( rc ) goto end_insert;
}else if( loc<0 && pPage->nCell>0 ){
assert( pPage->leaf );
idx = ++pCur->ix;
}else{
assert( pPage->leaf );
}
insertCell(pPage, idx, newCell, szNew, 0, 0, &rc);
assert( pPage->nOverflow==0 || rc==SQLITE_OK );
assert( rc!=SQLITE_OK || pPage->nCell>0 || pPage->nOverflow>0 );
................................................................................
assert( cursorOwnsBtShared(pCur) );
assert( pBt->inTransaction==TRANS_WRITE );
assert( (pBt->btsFlags & BTS_READ_ONLY)==0 );
assert( pCur->curFlags & BTCF_WriteFlag );
assert( hasSharedCacheTableLock(p, pCur->pgnoRoot, pCur->pKeyInfo!=0, 2) );
assert( !hasReadConflicts(p, pCur->pgnoRoot) );
assert( pCur->ix<pCur->apPage[pCur->iPage]->nCell );
assert( pCur->eState==CURSOR_VALID );
assert( (flags & ~(BTREE_SAVEPOSITION | BTREE_AUXDELETE))==0 );
iCellDepth = pCur->iPage;
iCellIdx = pCur->ix;
pPage = pCur->apPage[iCellDepth];
pCell = findCell(pPage, iCellIdx);
/* If the bPreserve flag is set to true, then the cursor position must
** be preserved following this delete operation. If the current delete
** will cause a b-tree rebalance, then this is done by saving the cursor
** key and leaving the cursor in CURSOR_REQUIRESEEK state before
................................................................................
if( bSkipnext ){
assert( bPreserve && (pCur->iPage==iCellDepth || CORRUPT_DB) );
assert( pPage==pCur->apPage[pCur->iPage] || CORRUPT_DB );
assert( (pPage->nCell>0 || CORRUPT_DB) && iCellIdx<=pPage->nCell );
pCur->eState = CURSOR_SKIPNEXT;
if( iCellIdx>=pPage->nCell ){
pCur->skipNext = -1;
pCur->ix = pPage->nCell-1;
}else{
pCur->skipNext = 1;
}
}else{
rc = moveToRoot(pCur);
if( bPreserve ){
pCur->eState = CURSOR_REQUIRESEEK;
................................................................................
do {
if( pCur->iPage==0 ){
/* All pages of the b-tree have been visited. Return successfully. */
*pnEntry = nEntry;
return moveToRoot(pCur);
}
moveToParent(pCur);
}while ( pCur->ix>=pCur->apPage[pCur->iPage]->nCell );
pCur->ix++;
pPage = pCur->apPage[pCur->iPage];
}
/* Descend to the child node of the cell that the cursor currently
** points at. This is the right-child if (iIdx==pPage->nCell).
*/
iIdx = pCur->ix;
if( iIdx==pPage->nCell ){
rc = moveToChild(pCur, get4byte(&pPage->aData[pPage->hdrOffset+8]));
}else{
rc = moveToChild(pCur, get4byte(findCell(pPage, iIdx)));
}
}
|
Changes to src/btreeInt.h.
513 514 515 516 517 518 519 520 521 522 523 524 525 526 |
u8 eState; /* One of the CURSOR_XXX constants (see below) */ u8 hints; /* As configured by CursorSetHints() */ /* All fields above are zeroed when the cursor is allocated. See ** sqlite3BtreeCursorZero(). Fields that follow must be manually ** initialized. */ i8 iPage; /* Index of current page in apPage */ u8 curIntKey; /* Value of apPage[0]->intKey */ struct KeyInfo *pKeyInfo; /* Argument passed to comparison function */ void *padding1; /* Make object size a multiple of 16 */ u16 aiIdx[BTCURSOR_MAX_DEPTH]; /* Current index in apPage[i] */ MemPage *apPage[BTCURSOR_MAX_DEPTH]; /* Pages from root to current page */ }; /* |
> |
513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 |
u8 eState; /* One of the CURSOR_XXX constants (see below) */
u8 hints; /* As configured by CursorSetHints() */
/* All fields above are zeroed when the cursor is allocated. See
** sqlite3BtreeCursorZero(). Fields that follow must be manually
** initialized. */
i8 iPage; /* Index of current page in apPage */
u8 curIntKey; /* Value of apPage[0]->intKey */
u16 ix; /* Current index for apPage[iPage] */
struct KeyInfo *pKeyInfo; /* Argument passed to comparison function */
void *padding1; /* Make object size a multiple of 16 */
u16 aiIdx[BTCURSOR_MAX_DEPTH]; /* Current index in apPage[i] */
MemPage *apPage[BTCURSOR_MAX_DEPTH]; /* Pages from root to current page */
};
/*
|