Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Changes In Branch btree-current-page-cache Excluding Merge-Ins
This is equivalent to a diff from f71053cf65 to a200e1eae9
2015-04-15
| ||
19:25 | Fix a potential one-byte buffer overread in the command-line shell. (check-in: e018f4bf1f user: drh tags: trunk) | |
19:13 | Add the BtCursor.pPage field which is the current page to which the cursor points, for a very small performance gain. (Leaf check-in: a200e1eae9 user: drh tags: btree-current-page-cache) | |
17:26 | Prevent the fetchPayload() routine from reporting a cell size that extends off the end of the page on a pathologically corrupted database file. (check-in: f71053cf65 user: drh tags: trunk) | |
15:29 | Enhance the showdb utility program so that it can read the last partial page of a truncated database file. (check-in: 61d72e1791 user: drh tags: trunk) | |
Changes to src/btree.c.
︙ | ︙ | |||
583 584 585 586 587 588 589 590 591 592 593 594 595 596 | static void btreeReleaseAllCursorPages(BtCursor *pCur){ int i; for(i=0; i<=pCur->iPage; i++){ releasePage(pCur->apPage[i]); pCur->apPage[i] = 0; } pCur->iPage = -1; } /* ** Save the current cursor position in the variables BtCursor.nKey ** and BtCursor.pKey. The cursor's state is set to CURSOR_REQUIRESEEK. ** | > | 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 | static void btreeReleaseAllCursorPages(BtCursor *pCur){ int i; for(i=0; i<=pCur->iPage; i++){ releasePage(pCur->apPage[i]); pCur->apPage[i] = 0; } pCur->iPage = -1; pCur->pPage = 0; } /* ** Save the current cursor position in the variables BtCursor.nKey ** and BtCursor.pKey. The cursor's state is set to CURSOR_REQUIRESEEK. ** |
︙ | ︙ | |||
3647 3648 3649 3650 3651 3652 3653 3654 3655 3656 3657 3658 3659 3660 | p->eState = CURSOR_FAULT; p->skipNext = errCode; } for(i=0; i<=p->iPage; i++){ releasePage(p->apPage[i]); p->apPage[i] = 0; } } sqlite3BtreeLeave(pBtree); } return rc; } /* | > | 3648 3649 3650 3651 3652 3653 3654 3655 3656 3657 3658 3659 3660 3661 3662 | p->eState = CURSOR_FAULT; p->skipNext = errCode; } for(i=0; i<=p->iPage; i++){ releasePage(p->apPage[i]); p->apPage[i] = 0; } p->pPage = 0; } sqlite3BtreeLeave(pBtree); } return rc; } /* |
︙ | ︙ | |||
3861 3862 3863 3864 3865 3866 3867 3868 3869 3870 3871 3872 3873 3874 | iTable = 0; } /* Now that no other errors can occur, finish filling in the BtCursor ** variables and link the cursor into the BtShared list. */ pCur->pgnoRoot = (Pgno)iTable; pCur->iPage = -1; pCur->pKeyInfo = pKeyInfo; pCur->pBtree = p; pCur->pBt = pBt; assert( wrFlag==0 || wrFlag==BTCF_WriteFlag ); pCur->curFlags = wrFlag; pCur->pNext = pBt->pCursor; if( pCur->pNext ){ | > | 3863 3864 3865 3866 3867 3868 3869 3870 3871 3872 3873 3874 3875 3876 3877 | iTable = 0; } /* Now that no other errors can occur, finish filling in the BtCursor ** variables and link the cursor into the BtShared list. */ pCur->pgnoRoot = (Pgno)iTable; pCur->iPage = -1; pCur->pPage = 0; pCur->pKeyInfo = pKeyInfo; pCur->pBtree = p; pCur->pBt = pBt; assert( wrFlag==0 || wrFlag==BTCF_WriteFlag ); pCur->curFlags = wrFlag; pCur->pNext = pBt->pCursor; if( pCur->pNext ){ |
︙ | ︙ | |||
3962 3963 3964 3965 3966 3967 3968 | ** for MSVC and a macro for everything else. Ticket #2457. */ #ifndef NDEBUG static void assertCellInfo(BtCursor *pCur){ CellInfo info; int iPage = pCur->iPage; memset(&info, 0, sizeof(info)); | > | > | > | | 3965 3966 3967 3968 3969 3970 3971 3972 3973 3974 3975 3976 3977 3978 3979 3980 3981 3982 3983 3984 3985 3986 3987 3988 3989 3990 3991 3992 3993 3994 3995 3996 3997 3998 3999 4000 4001 4002 4003 4004 | ** for MSVC and a macro for everything else. Ticket #2457. */ #ifndef NDEBUG static void assertCellInfo(BtCursor *pCur){ CellInfo info; int iPage = pCur->iPage; memset(&info, 0, sizeof(info)); assert( pCur->pPage==pCur->apPage[iPage] ); btreeParseCell(pCur->pPage, pCur->aiIdx[iPage], &info); assert( CORRUPT_DB || memcmp(&info, &pCur->info, sizeof(info))==0 ); } #else #define assertCellInfo(x) #endif #ifdef _MSC_VER /* Use a real function in MSVC to work around bugs in that compiler. */ static void getCellInfo(BtCursor *pCur){ if( pCur->info.nSize==0 ){ int iPage = pCur->iPage; assert( pCur->pPage==pCur->apPage[iPage] ); btreeParseCell(pCur->pPage,pCur->aiIdx[iPage],&pCur->info); pCur->curFlags |= BTCF_ValidNKey; }else{ assertCellInfo(pCur); } } #else /* if not _MSC_VER */ /* Use a macro in all other compilers so that the function is inlined */ #define getCellInfo(pCur) \ if( pCur->info.nSize==0 ){ \ int iPage = pCur->iPage; \ assert( pCur->pPage==pCur->apPage[iPage] ); \ btreeParseCell(pCur->pPage,pCur->aiIdx[iPage],&pCur->info); \ pCur->curFlags |= BTCF_ValidNKey; \ }else{ \ assertCellInfo(pCur); \ } #endif /* _MSC_VER */ #ifndef NDEBUG /* The next routine used only within assert() statements */ |
︙ | ︙ | |||
4039 4040 4041 4042 4043 4044 4045 | ** to return an integer result code for historical reasons. */ int sqlite3BtreeDataSize(BtCursor *pCur, u32 *pSize){ assert( cursorHoldsMutex(pCur) ); assert( pCur->eState==CURSOR_VALID ); assert( pCur->iPage>=0 ); assert( pCur->iPage<BTCURSOR_MAX_DEPTH ); | > | | 4045 4046 4047 4048 4049 4050 4051 4052 4053 4054 4055 4056 4057 4058 4059 4060 | ** to return an integer result code for historical reasons. */ int sqlite3BtreeDataSize(BtCursor *pCur, u32 *pSize){ assert( cursorHoldsMutex(pCur) ); assert( pCur->eState==CURSOR_VALID ); assert( pCur->iPage>=0 ); assert( pCur->iPage<BTCURSOR_MAX_DEPTH ); assert( pCur->pPage==pCur->apPage[pCur->iPage] ); assert( pCur->pPage->intKeyLeaf==1 ); getCellInfo(pCur); *pSize = pCur->info.nPayload; return SQLITE_OK; } /* ** Given the page number of an overflow page in the database (parameter |
︙ | ︙ | |||
4193 4194 4195 4196 4197 4198 4199 | u32 amt, /* Read this many bytes */ unsigned char *pBuf, /* Write the bytes into this buffer */ int eOp /* zero to read. non-zero to write. */ ){ unsigned char *aPayload; int rc = SQLITE_OK; int iIdx = 0; | | | > | 4200 4201 4202 4203 4204 4205 4206 4207 4208 4209 4210 4211 4212 4213 4214 4215 4216 4217 4218 4219 4220 4221 4222 | u32 amt, /* Read this many bytes */ unsigned char *pBuf, /* Write the bytes into this buffer */ int eOp /* zero to read. non-zero to write. */ ){ unsigned char *aPayload; int rc = SQLITE_OK; int iIdx = 0; MemPage *pPage = pCur->pPage; /* Btree page of current entry */ BtShared *pBt = pCur->pBt; /* Btree this cursor belongs to */ #ifdef SQLITE_DIRECT_OVERFLOW_READ unsigned char * const pBufStart = pBuf; int bEnd; /* True if reading to end of data */ #endif assert( pPage ); assert( pPage==pCur->apPage[pCur->iPage] ); assert( pCur->eState==CURSOR_VALID ); assert( pCur->aiIdx[pCur->iPage]<pPage->nCell ); assert( cursorHoldsMutex(pCur) ); assert( eOp!=2 || offset==0 ); /* Always start from beginning for eOp==2 */ getCellInfo(pCur); aPayload = pCur->info.pPayload; |
︙ | ︙ | |||
4390 4391 4392 4393 4394 4395 4396 | ** Return SQLITE_OK on success or an error code if anything goes ** wrong. An error is returned if "offset+amt" is larger than ** the available payload. */ int sqlite3BtreeKey(BtCursor *pCur, u32 offset, u32 amt, void *pBuf){ assert( cursorHoldsMutex(pCur) ); assert( pCur->eState==CURSOR_VALID ); | | > > | | 4398 4399 4400 4401 4402 4403 4404 4405 4406 4407 4408 4409 4410 4411 4412 4413 4414 4415 | ** Return SQLITE_OK on success or an error code if anything goes ** wrong. An error is returned if "offset+amt" is larger than ** the available payload. */ int sqlite3BtreeKey(BtCursor *pCur, u32 offset, u32 amt, void *pBuf){ assert( cursorHoldsMutex(pCur) ); assert( pCur->eState==CURSOR_VALID ); assert( pCur->iPage>=0 ); assert( pCur->apPage[pCur->iPage]==pCur->pPage ); assert( pCur->pPage!=0 ); assert( pCur->aiIdx[pCur->iPage]<pCur->pPage->nCell ); return accessPayload(pCur, offset, amt, (unsigned char*)pBuf, 0); } /* ** Read part of the data associated with cursor pCur. Exactly ** "amt" bytes will be transfered into pBuf[]. The transfer ** begins at "offset". |
︙ | ︙ | |||
4417 4418 4419 4420 4421 4422 4423 | } #endif assert( cursorHoldsMutex(pCur) ); rc = restoreCursorPosition(pCur); if( rc==SQLITE_OK ){ assert( pCur->eState==CURSOR_VALID ); | | > > | | 4427 4428 4429 4430 4431 4432 4433 4434 4435 4436 4437 4438 4439 4440 4441 4442 4443 4444 | } #endif assert( cursorHoldsMutex(pCur) ); rc = restoreCursorPosition(pCur); if( rc==SQLITE_OK ){ assert( pCur->eState==CURSOR_VALID ); assert( pCur->iPage>=0 ); assert( pCur->apPage[pCur->iPage]==pCur->pPage ); assert( pCur->pPage!=0 ); assert( pCur->aiIdx[pCur->iPage]<pCur->pPage->nCell ); rc = accessPayload(pCur, offset, amt, pBuf, 0); } return rc; } /* ** Return a pointer to payload information from the entry that the |
︙ | ︙ | |||
4448 4449 4450 4451 4452 4453 4454 | ** any btree routine is called. */ static const void *fetchPayload( BtCursor *pCur, /* Cursor pointing to entry to read from */ u32 *pAmt /* Write the number of available bytes here */ ){ u32 amt; | | > > > | | | | | 4460 4461 4462 4463 4464 4465 4466 4467 4468 4469 4470 4471 4472 4473 4474 4475 4476 4477 4478 4479 4480 4481 4482 4483 4484 4485 | ** any btree routine is called. */ static const void *fetchPayload( BtCursor *pCur, /* Cursor pointing to entry to read from */ u32 *pAmt /* Write the number of available bytes here */ ){ u32 amt; assert( pCur!=0 ); assert( pCur->iPage>=0 ); assert( pCur->apPage[pCur->iPage]==pCur->pPage ); assert( pCur->pPage!=0 ); assert( pCur->eState==CURSOR_VALID ); assert( sqlite3_mutex_held(pCur->pBtree->db->mutex) ); assert( cursorHoldsMutex(pCur) ); assert( pCur->aiIdx[pCur->iPage]<pCur->pPage->nCell ); assert( pCur->info.nSize>0 ); assert( pCur->info.pPayload>pCur->pPage->aData || CORRUPT_DB ); assert( pCur->info.pPayload<pCur->pPage->aDataEnd || CORRUPT_DB ); amt = (int)(pCur->pPage->aDataEnd - pCur->info.pPayload); if( pCur->info.nLocal<amt ) amt = pCur->info.nLocal; *pAmt = amt; return (void*)pCur->info.pPayload; } /* |
︙ | ︙ | |||
4510 4511 4512 4513 4514 4515 4516 | assert( pCur->iPage>=0 ); if( pCur->iPage>=(BTCURSOR_MAX_DEPTH-1) ){ return SQLITE_CORRUPT_BKPT; } rc = getAndInitPage(pBt, newPgno, &pNewPage, (pCur->curFlags & BTCF_WriteFlag)==0 ? PAGER_GET_READONLY : 0); if( rc ) return rc; | | | 4525 4526 4527 4528 4529 4530 4531 4532 4533 4534 4535 4536 4537 4538 4539 | assert( pCur->iPage>=0 ); if( pCur->iPage>=(BTCURSOR_MAX_DEPTH-1) ){ return SQLITE_CORRUPT_BKPT; } rc = getAndInitPage(pBt, newPgno, &pNewPage, (pCur->curFlags & BTCF_WriteFlag)==0 ? PAGER_GET_READONLY : 0); if( rc ) return rc; pCur->apPage[i+1] = pCur->pPage = pNewPage; pCur->aiIdx[i+1] = 0; pCur->iPage++; pCur->info.nSize = 0; pCur->curFlags &= ~(BTCF_ValidNKey|BTCF_ValidOvfl); if( pNewPage->nCell<1 || pNewPage->intKey!=pCur->apPage[i]->intKey ){ return SQLITE_CORRUPT_BKPT; |
︙ | ︙ | |||
4556 4557 4558 4559 4560 4561 4562 | ** right-most child page then pCur->idx is set to one more than ** the largest cell index. */ static void moveToParent(BtCursor *pCur){ assert( cursorHoldsMutex(pCur) ); assert( pCur->eState==CURSOR_VALID ); assert( pCur->iPage>0 ); | > | | | > | 4571 4572 4573 4574 4575 4576 4577 4578 4579 4580 4581 4582 4583 4584 4585 4586 4587 4588 4589 4590 4591 4592 4593 4594 4595 4596 | ** right-most child page then pCur->idx is set to one more than ** the largest cell index. */ static void moveToParent(BtCursor *pCur){ assert( cursorHoldsMutex(pCur) ); assert( pCur->eState==CURSOR_VALID ); assert( pCur->iPage>0 ); assert( pCur->pPage==pCur->apPage[pCur->iPage] ); assert( pCur->pPage!=0 ); assertParentIndex( pCur->apPage[pCur->iPage-1], pCur->aiIdx[pCur->iPage-1], pCur->pPage->pgno ); testcase( pCur->aiIdx[pCur->iPage-1] > pCur->apPage[pCur->iPage-1]->nCell ); releasePage(pCur->pPage); pCur->iPage--; pCur->pPage = pCur->apPage[pCur->iPage]; pCur->info.nSize = 0; pCur->curFlags &= ~(BTCF_ValidNKey|BTCF_ValidOvfl); } /* ** Move the cursor to point to the root page of its b-tree structure. ** |
︙ | ︙ | |||
4621 4622 4623 4624 4625 4626 4627 | (pCur->curFlags & BTCF_WriteFlag)==0 ? PAGER_GET_READONLY : 0); if( rc!=SQLITE_OK ){ pCur->eState = CURSOR_INVALID; return rc; } pCur->iPage = 0; } | > | | 4638 4639 4640 4641 4642 4643 4644 4645 4646 4647 4648 4649 4650 4651 4652 4653 | (pCur->curFlags & BTCF_WriteFlag)==0 ? PAGER_GET_READONLY : 0); if( rc!=SQLITE_OK ){ pCur->eState = CURSOR_INVALID; return rc; } pCur->iPage = 0; } assert( pCur->iPage==0 ); pRoot = pCur->pPage = pCur->apPage[0]; assert( pRoot->pgno==pCur->pgnoRoot ); /* If pCur->pKeyInfo is not NULL, then the caller that opened this cursor ** expected to open it on an index b-tree. Otherwise, if pKeyInfo is ** NULL, the caller expects a table b-tree. If this is not the case, ** return an SQLITE_CORRUPT error. ** |
︙ | ︙ | |||
4671 4672 4673 4674 4675 4676 4677 | static int moveToLeftmost(BtCursor *pCur){ Pgno pgno; int rc = SQLITE_OK; MemPage *pPage; assert( cursorHoldsMutex(pCur) ); assert( pCur->eState==CURSOR_VALID ); | | | 4689 4690 4691 4692 4693 4694 4695 4696 4697 4698 4699 4700 4701 4702 4703 | static int moveToLeftmost(BtCursor *pCur){ Pgno pgno; int rc = SQLITE_OK; MemPage *pPage; assert( cursorHoldsMutex(pCur) ); assert( pCur->eState==CURSOR_VALID ); while( rc==SQLITE_OK && !(pPage = pCur->pPage)->leaf ){ assert( pCur->aiIdx[pCur->iPage]<pPage->nCell ); pgno = get4byte(findCell(pPage, pCur->aiIdx[pCur->iPage])); rc = moveToChild(pCur, pgno); } return rc; } |
︙ | ︙ | |||
4696 4697 4698 4699 4700 4701 4702 | static int moveToRightmost(BtCursor *pCur){ Pgno pgno; int rc = SQLITE_OK; MemPage *pPage = 0; assert( cursorHoldsMutex(pCur) ); assert( pCur->eState==CURSOR_VALID ); | | | 4714 4715 4716 4717 4718 4719 4720 4721 4722 4723 4724 4725 4726 4727 4728 | static int moveToRightmost(BtCursor *pCur){ Pgno pgno; int rc = SQLITE_OK; MemPage *pPage = 0; assert( cursorHoldsMutex(pCur) ); assert( pCur->eState==CURSOR_VALID ); while( !(pPage = pCur->pPage)->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 ); |
︙ | ︙ | |||
4719 4720 4721 4722 4723 4724 4725 4726 | int sqlite3BtreeFirst(BtCursor *pCur, int *pRes){ int rc; assert( cursorHoldsMutex(pCur) ); assert( sqlite3_mutex_held(pCur->pBtree->db->mutex) ); rc = moveToRoot(pCur); if( rc==SQLITE_OK ){ if( pCur->eState==CURSOR_INVALID ){ | > | | | 4737 4738 4739 4740 4741 4742 4743 4744 4745 4746 4747 4748 4749 4750 4751 4752 4753 4754 4755 4756 | int sqlite3BtreeFirst(BtCursor *pCur, int *pRes){ int rc; assert( cursorHoldsMutex(pCur) ); assert( sqlite3_mutex_held(pCur->pBtree->db->mutex) ); rc = moveToRoot(pCur); if( rc==SQLITE_OK ){ assert( pCur->pPage==pCur->apPage[pCur->iPage] ); if( pCur->eState==CURSOR_INVALID ){ assert( pCur->pgnoRoot==0 || pCur->pPage->nCell==0 ); *pRes = 1; }else{ assert( pCur->pPage->nCell>0 ); *pRes = 0; rc = moveToLeftmost(pCur); } } return rc; } |
︙ | ︙ | |||
4750 4751 4752 4753 4754 4755 4756 | #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 ); } | > | | | 4769 4770 4771 4772 4773 4774 4775 4776 4777 4778 4779 4780 4781 4782 4783 4784 4785 | #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->pPage==pCur->apPage[pCur->iPage] ); assert( pCur->aiIdx[pCur->iPage]==pCur->pPage->nCell-1 ); assert( pCur->pPage->leaf ); #endif return SQLITE_OK; } rc = moveToRoot(pCur); if( rc==SQLITE_OK ){ if( CURSOR_INVALID==pCur->eState ){ |
︙ | ︙ | |||
4849 4850 4851 4852 4853 4854 4855 | xRecordCompare = 0; /* All keys are integers */ } rc = moveToRoot(pCur); if( rc ){ return rc; } | | | > | | | | | 4869 4870 4871 4872 4873 4874 4875 4876 4877 4878 4879 4880 4881 4882 4883 4884 4885 4886 4887 4888 4889 4890 4891 4892 4893 4894 4895 4896 | xRecordCompare = 0; /* All keys are integers */ } rc = moveToRoot(pCur); if( rc ){ return rc; } assert( pCur->pgnoRoot==0 || pCur->apPage[pCur->iPage]==pCur->pPage ); assert( pCur->pgnoRoot==0 || pCur->pPage!=0 ); assert( pCur->pgnoRoot==0 || pCur->pPage->isInit ); assert( pCur->eState==CURSOR_INVALID || pCur->pPage->nCell>0 ); if( pCur->eState==CURSOR_INVALID ){ *pRes = -1; assert( pCur->pgnoRoot==0 || pCur->pPage->nCell==0 ); return SQLITE_OK; } assert( pCur->pPage->intKey || pIdxKey ); for(;;){ int lwr, upr, idx, c; Pgno chldPg; MemPage *pPage = pCur->pPage; u8 *pCell; /* Pointer to current cell in pPage */ /* pPage->nCell must be greater than zero. If this is the root-page ** the cursor would have been INVALID above and this for(;;) loop ** not run. If this is not the root-page, then the moveToChild() routine ** would have already detected db corruption. Similarly, pPage must ** be the right kind (index or table) of b-tree page. Otherwise |
︙ | ︙ | |||
4984 4985 4986 4987 4988 4989 4990 | 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 ){ | | | 5005 5006 5007 5008 5009 5010 5011 5012 5013 5014 5015 5016 5017 5018 5019 | 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->pPage->nCell ); pCur->aiIdx[pCur->iPage] = (u16)idx; *pRes = c; rc = SQLITE_OK; goto moveto_finish; } moveto_next_layer: if( lwr>=pPage->nCell ){ |
︙ | ︙ | |||
5072 5073 5074 5075 5076 5077 5078 | pCur->skipNext = 0; return SQLITE_OK; } pCur->skipNext = 0; } } | | | 5093 5094 5095 5096 5097 5098 5099 5100 5101 5102 5103 5104 5105 5106 5107 | pCur->skipNext = 0; return SQLITE_OK; } pCur->skipNext = 0; } } pPage = pCur->pPage; 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 |
︙ | ︙ | |||
5096 5097 5098 5099 5100 5101 5102 | do{ if( pCur->iPage==0 ){ *pRes = 1; pCur->eState = CURSOR_INVALID; return SQLITE_OK; } moveToParent(pCur); | | | 5117 5118 5119 5120 5121 5122 5123 5124 5125 5126 5127 5128 5129 5130 5131 | do{ if( pCur->iPage==0 ){ *pRes = 1; pCur->eState = CURSOR_INVALID; return SQLITE_OK; } moveToParent(pCur); pPage = pCur->pPage; }while( pCur->aiIdx[pCur->iPage]>=pPage->nCell ); if( pPage->intKey ){ return sqlite3BtreeNext(pCur, pRes); }else{ return SQLITE_OK; } } |
︙ | ︙ | |||
5120 5121 5122 5123 5124 5125 5126 | assert( pRes!=0 ); 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); | | | 5141 5142 5143 5144 5145 5146 5147 5148 5149 5150 5151 5152 5153 5154 5155 | assert( pRes!=0 ); 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->pPage; if( (++pCur->aiIdx[pCur->iPage])>=pPage->nCell ){ pCur->aiIdx[pCur->iPage]--; return btreeNext(pCur, pRes); } if( pPage->leaf ){ return SQLITE_OK; }else{ |
︙ | ︙ | |||
5183 5184 5185 5186 5187 5188 5189 | pCur->skipNext = 0; return SQLITE_OK; } pCur->skipNext = 0; } } | | > > | | | 5204 5205 5206 5207 5208 5209 5210 5211 5212 5213 5214 5215 5216 5217 5218 5219 5220 5221 5222 5223 5224 5225 5226 5227 5228 5229 5230 5231 5232 5233 5234 5235 5236 5237 5238 5239 5240 5241 5242 5243 5244 5245 5246 5247 5248 5249 5250 5251 5252 5253 5254 5255 5256 5257 5258 5259 | pCur->skipNext = 0; return SQLITE_OK; } pCur->skipNext = 0; } } pPage = pCur->pPage; assert( 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_ValidNKey|BTCF_ValidOvfl))==0 ); pCur->aiIdx[pCur->iPage]--; assert( pCur->apPage[pCur->iPage]==pCur->pPage ); pPage = pCur->pPage; if( pPage->intKey && !pPage->leaf ){ rc = sqlite3BtreePrevious(pCur, pRes); }else{ rc = SQLITE_OK; } } return rc; } int sqlite3BtreePrevious(BtCursor *pCur, int *pRes){ assert( cursorHoldsMutex(pCur) ); 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->pPage->leaf==0 ){ return btreePrevious(pCur, pRes); } pCur->aiIdx[pCur->iPage]--; return SQLITE_OK; } |
︙ | ︙ | |||
7415 7416 7417 7418 7419 7420 7421 | u8 *pFree = 0; TESTONLY( int balance_quick_called = 0 ); TESTONLY( int balance_deeper_called = 0 ); do { int iPage = pCur->iPage; | | > | > | 7438 7439 7440 7441 7442 7443 7444 7445 7446 7447 7448 7449 7450 7451 7452 7453 7454 7455 7456 7457 7458 7459 7460 7461 7462 7463 7464 7465 7466 7467 7468 7469 | u8 *pFree = 0; TESTONLY( int balance_quick_called = 0 ); TESTONLY( int balance_deeper_called = 0 ); do { int iPage = pCur->iPage; MemPage *pPage = pCur->pPage; assert( pPage==pCur->apPage[iPage] ); if( iPage==0 ){ if( pPage->nOverflow ){ /* The root page of the b-tree is overfull. In this case call the ** balance_deeper() function to create a new child for the root-page ** and copy the current contents of the root-page to it. The ** next iteration of the do-loop will balance the child page. */ assert( (balance_deeper_called++)==0 ); rc = balance_deeper(pPage, &pCur->apPage[1]); if( rc==SQLITE_OK ){ pCur->iPage = 1; pCur->aiIdx[0] = 0; pCur->aiIdx[1] = 0; pCur->pPage = pCur->apPage[1]; assert( pCur->pPage->nOverflow ); } }else{ break; } }else if( pPage->nOverflow==0 && pPage->nFree<=nMin ){ break; }else{ |
︙ | ︙ | |||
7509 7510 7511 7512 7513 7514 7515 7516 7517 7518 7519 7520 7521 7522 | pPage->nOverflow = 0; /* The next iteration of the do-loop balances the parent page. */ releasePage(pPage); pCur->iPage--; assert( pCur->iPage>=0 ); } }while( rc==SQLITE_OK ); if( pFree ){ sqlite3PageFree(pFree); } return rc; | > | 7534 7535 7536 7537 7538 7539 7540 7541 7542 7543 7544 7545 7546 7547 7548 | pPage->nOverflow = 0; /* The next iteration of the do-loop balances the parent page. */ releasePage(pPage); pCur->iPage--; assert( pCur->iPage>=0 ); pCur->pPage = pCur->apPage[pCur->iPage]; } }while( rc==SQLITE_OK ); if( pFree ){ sqlite3PageFree(pFree); } return rc; |
︙ | ︙ | |||
7611 7612 7613 7614 7615 7616 7617 | if( !loc ){ rc = btreeMoveto(pCur, pKey, nKey, appendBias, &loc); if( rc ) return rc; } assert( pCur->eState==CURSOR_VALID || (pCur->eState==CURSOR_INVALID && loc) ); | > | | 7637 7638 7639 7640 7641 7642 7643 7644 7645 7646 7647 7648 7649 7650 7651 7652 | if( !loc ){ rc = btreeMoveto(pCur, pKey, nKey, appendBias, &loc); if( rc ) return rc; } assert( pCur->eState==CURSOR_VALID || (pCur->eState==CURSOR_INVALID && loc) ); assert( pCur->pPage==pCur->apPage[pCur->iPage] ); pPage = pCur->pPage; assert( pPage->intKey || nKey>=0 ); assert( pPage->leaf || !pPage->intKey ); TRACE(("INSERT: table=%d nkey=%lld ndata=%d page=%d %s\n", pCur->pgnoRoot, nKey, nData, pPage->pgno, loc==0 ? "overwrite" : "new entry")); assert( pPage->isInit ); |
︙ | ︙ | |||
7678 7679 7680 7681 7682 7683 7684 | pCur->curFlags &= ~(BTCF_ValidNKey); rc = balance(pCur); /* Must make sure nOverflow is reset to zero even if the balance() ** fails. Internal data structure corruption will result otherwise. ** Also, set the cursor state to invalid. This stops saveCursorPosition() ** from trying to save the current position of the cursor. */ | > | | | 7705 7706 7707 7708 7709 7710 7711 7712 7713 7714 7715 7716 7717 7718 7719 7720 7721 7722 7723 | pCur->curFlags &= ~(BTCF_ValidNKey); rc = balance(pCur); /* Must make sure nOverflow is reset to zero even if the balance() ** fails. Internal data structure corruption will result otherwise. ** Also, set the cursor state to invalid. This stops saveCursorPosition() ** from trying to save the current position of the cursor. */ assert( pCur->pPage==pCur->apPage[pCur->iPage] ); pCur->pPage->nOverflow = 0; pCur->eState = CURSOR_INVALID; } assert( pCur->pPage->nOverflow==0 ); end_insert: return rc; } /* ** Delete the entry that the cursor is pointing to. The cursor |
︙ | ︙ | |||
7707 7708 7709 7710 7711 7712 7713 7714 | assert( cursorHoldsMutex(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) ); | > | | 7735 7736 7737 7738 7739 7740 7741 7742 7743 7744 7745 7746 7747 7748 7749 7750 7751 | assert( cursorHoldsMutex(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->pPage==pCur->apPage[pCur->iPage] ); if( NEVER(pCur->aiIdx[pCur->iPage]>=pCur->pPage->nCell) || NEVER(pCur->eState!=CURSOR_VALID) ){ return SQLITE_ERROR; /* Something has gone awry. */ } iCellDepth = pCur->iPage; iCellIdx = pCur->aiIdx[iCellDepth]; |
︙ | ︙ | |||
7758 7759 7760 7761 7762 7763 7764 | /* If the cell deleted was not located on a leaf page, then the cursor ** is currently pointing to the largest entry in the sub-tree headed ** by the child-page of the cell that was just deleted from an internal ** node. The cell from the leaf node needs to be moved to the internal ** node to replace the deleted cell. */ if( !pPage->leaf ){ | | | 7787 7788 7789 7790 7791 7792 7793 7794 7795 7796 7797 7798 7799 7800 7801 | /* If the cell deleted was not located on a leaf page, then the cursor ** is currently pointing to the largest entry in the sub-tree headed ** by the child-page of the cell that was just deleted from an internal ** node. The cell from the leaf node needs to be moved to the internal ** node to replace the deleted cell. */ if( !pPage->leaf ){ MemPage *pLeaf = pCur->pPage; int nCell; Pgno n = pCur->apPage[iCellDepth+1]->pgno; unsigned char *pTmp; pCell = findCell(pLeaf, pLeaf->nCell-1); nCell = cellSizePtr(pLeaf, pCell); assert( MX_CELL_SIZE(pBt) >= nCell ); |
︙ | ︙ | |||
7794 7795 7796 7797 7798 7799 7800 7801 7802 7803 7804 7805 7806 7807 | ** walk the cursor up the tree to the internal node and balance it as ** well. */ rc = balance(pCur); if( rc==SQLITE_OK && pCur->iPage>iCellDepth ){ while( pCur->iPage>iCellDepth ){ releasePage(pCur->apPage[pCur->iPage--]); } rc = balance(pCur); } if( rc==SQLITE_OK ){ moveToRoot(pCur); } return rc; | > | 7823 7824 7825 7826 7827 7828 7829 7830 7831 7832 7833 7834 7835 7836 7837 | ** walk the cursor up the tree to the internal node and balance it as ** well. */ rc = balance(pCur); if( rc==SQLITE_OK && pCur->iPage>iCellDepth ){ while( pCur->iPage>iCellDepth ){ releasePage(pCur->apPage[pCur->iPage--]); } pCur->pPage = pCur->apPage[pCur->iPage]; rc = balance(pCur); } if( rc==SQLITE_OK ){ moveToRoot(pCur); } return rc; |
︙ | ︙ | |||
8298 8299 8300 8301 8302 8303 8304 | int iIdx; /* Index of child node in parent */ MemPage *pPage; /* Current page of the b-tree */ /* If this is a leaf page or the tree is not an int-key tree, then ** this page contains countable entries. Increment the entry counter ** accordingly. */ | > | | 8328 8329 8330 8331 8332 8333 8334 8335 8336 8337 8338 8339 8340 8341 8342 8343 | int iIdx; /* Index of child node in parent */ MemPage *pPage; /* Current page of the b-tree */ /* If this is a leaf page or the tree is not an int-key tree, then ** this page contains countable entries. Increment the entry counter ** accordingly. */ assert( pCur->pPage==pCur->apPage[pCur->iPage] ); pPage = pCur->pPage; if( pPage->leaf || !pPage->intKey ){ nEntry += pPage->nCell; } /* pPage is a leaf node. This loop navigates the cursor so that it ** points to the first interior cell that it points to the parent of ** the next page in the tree that has not yet been visited. The |
︙ | ︙ | |||
8321 8322 8323 8324 8325 8326 8327 | do { if( pCur->iPage==0 ){ /* All pages of the b-tree have been visited. Return successfully. */ *pnEntry = nEntry; return moveToRoot(pCur); } moveToParent(pCur); | | > | | 8352 8353 8354 8355 8356 8357 8358 8359 8360 8361 8362 8363 8364 8365 8366 8367 8368 8369 8370 | 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->pPage->nCell ); pCur->aiIdx[pCur->iPage]++; assert( pCur->pPage==pCur->apPage[pCur->iPage] ); pPage = pCur->pPage; } /* 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 ){ |
︙ | ︙ | |||
9107 9108 9109 9110 9111 9112 9113 9114 9115 9116 9117 9118 9119 9120 | return SQLITE_READONLY; } assert( (pCsr->pBt->btsFlags & BTS_READ_ONLY)==0 && pCsr->pBt->inTransaction==TRANS_WRITE ); assert( hasSharedCacheTableLock(pCsr->pBtree, pCsr->pgnoRoot, 0, 2) ); assert( !hasReadConflicts(pCsr->pBtree, pCsr->pgnoRoot) ); assert( pCsr->apPage[pCsr->iPage]->intKey ); return accessPayload(pCsr, offset, amt, (unsigned char *)z, 1); } /* ** Mark this cursor as an incremental blob cursor. */ | > | 9139 9140 9141 9142 9143 9144 9145 9146 9147 9148 9149 9150 9151 9152 9153 | return SQLITE_READONLY; } assert( (pCsr->pBt->btsFlags & BTS_READ_ONLY)==0 && pCsr->pBt->inTransaction==TRANS_WRITE ); assert( hasSharedCacheTableLock(pCsr->pBtree, pCsr->pgnoRoot, 0, 2) ); assert( !hasReadConflicts(pCsr->pBtree, pCsr->pgnoRoot) ); assert( pCsr->apPage[pCsr->iPage]->intKey ); assert( pCsr->pPage==pCsr->apPage[pCsr->iPage] ); return accessPayload(pCsr, offset, amt, (unsigned char *)z, 1); } /* ** Mark this cursor as an incremental blob cursor. */ |
︙ | ︙ |
Changes to src/btreeInt.h.
︙ | ︙ | |||
514 515 516 517 518 519 520 521 522 523 524 525 526 527 | int skipNext; /* Prev() is noop if negative. Next() is noop if positive. ** Error code if eState==CURSOR_FAULT */ u8 curFlags; /* zero or more BTCF_* flags defined below */ u8 eState; /* One of the CURSOR_XXX constants (see below) */ u8 hints; /* As configured by CursorSetHints() */ i16 iPage; /* Index of current page in apPage */ u16 aiIdx[BTCURSOR_MAX_DEPTH]; /* Current index in apPage[i] */ MemPage *apPage[BTCURSOR_MAX_DEPTH]; /* Pages from root to current page */ }; /* ** Legal values for BtCursor.curFlags */ #define BTCF_WriteFlag 0x01 /* True if a write cursor */ | > | 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 | int skipNext; /* Prev() is noop if negative. Next() is noop if positive. ** Error code if eState==CURSOR_FAULT */ u8 curFlags; /* zero or more BTCF_* flags defined below */ u8 eState; /* One of the CURSOR_XXX constants (see below) */ u8 hints; /* As configured by CursorSetHints() */ i16 iPage; /* Index of current page in apPage */ u16 aiIdx[BTCURSOR_MAX_DEPTH]; /* Current index in apPage[i] */ MemPage *pPage; /* Current page */ MemPage *apPage[BTCURSOR_MAX_DEPTH]; /* Pages from root to current page */ }; /* ** Legal values for BtCursor.curFlags */ #define BTCF_WriteFlag 0x01 /* True if a write cursor */ |
︙ | ︙ |