Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Micro-optimizations in sqlite3BtreeNext() and sqlite3BtreePrevious(). |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
839c7996eecd5480152c514555b9aa11 |
User & Date: | drh 2014-09-01 13:29:32.250 |
Context
2014-09-01
| ||
13:37 | Attempt to make the xDelete method of the unix VFS more robust on VxWorks. (check-in: b0f6b91f36 user: drh tags: trunk) | |
13:29 | Micro-optimizations in sqlite3BtreeNext() and sqlite3BtreePrevious(). (check-in: 839c7996ee user: drh tags: trunk) | |
01:16 | Fix harmless compiler warnings for MSVC. (check-in: 3ef3246120 user: mistachkin tags: trunk) | |
Changes
Changes to src/btree.c.
︙ | ︙ | |||
4509 4510 4511 4512 4513 4514 4515 | static int moveToRightmost(BtCursor *pCur){ Pgno pgno; int rc = SQLITE_OK; MemPage *pPage = 0; assert( cursorHoldsMutex(pCur) ); assert( pCur->eState==CURSOR_VALID ); | | > < | | | < | | 4509 4510 4511 4512 4513 4514 4515 4516 4517 4518 4519 4520 4521 4522 4523 4524 4525 4526 4527 4528 4529 4530 4531 4532 | 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->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 ** or set *pRes to 1 if the table is empty. */ int sqlite3BtreeFirst(BtCursor *pCur, int *pRes){ |
︙ | ︙ | |||
4838 4839 4840 4841 4842 4843 4844 4845 4846 4847 4848 4849 4850 4851 4852 4853 4854 | } /* ** Advance the cursor to the next entry in the database. If ** successful then set *pRes=0. If the cursor ** was already pointing to the last entry in the database before ** this routine was called, then set *pRes=1. ** ** The calling function will set *pRes to 0 or 1. The initial *pRes value ** will be 1 if the cursor being stepped corresponds to an SQL index and ** if this routine could have been skipped if that SQL index had been ** a unique index. Otherwise the caller will have set *pRes to zero. ** Zero is the common case. The btree implementation is free to use the ** initial *pRes value as a hint to improve performance, but the current ** SQLite btree implementation does not. (Note that the comdb2 btree ** implementation does use this hint, however.) */ | > > > > > > | | | < | < < < < | < < < | < < < | | > > | > > > > > > > > > > > > > > > > > | | < | | > > > > > > | | | > | | | < | < < | < < < | | > > > > > > > > > > > > > > > > | | 4837 4838 4839 4840 4841 4842 4843 4844 4845 4846 4847 4848 4849 4850 4851 4852 4853 4854 4855 4856 4857 4858 4859 4860 4861 4862 4863 4864 4865 4866 4867 4868 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 4897 4898 4899 4900 4901 4902 4903 4904 4905 4906 4907 4908 4909 4910 4911 4912 4913 4914 4915 4916 4917 4918 4919 4920 4921 4922 4923 4924 4925 4926 4927 4928 4929 4930 4931 4932 4933 4934 4935 4936 4937 4938 4939 4940 4941 4942 4943 4944 4945 4946 4947 4948 4949 4950 4951 4952 4953 4954 4955 4956 4957 4958 4959 4960 4961 4962 4963 4964 4965 4966 4967 4968 4969 4970 4971 4972 4973 4974 4975 4976 4977 4978 4979 4980 4981 4982 4983 4984 4985 4986 4987 4988 4989 4990 4991 4992 4993 4994 4995 4996 4997 4998 4999 5000 5001 5002 5003 5004 5005 5006 5007 5008 5009 5010 5011 5012 5013 5014 5015 5016 5017 5018 5019 5020 5021 5022 5023 5024 5025 5026 5027 5028 5029 5030 5031 5032 5033 5034 5035 5036 5037 5038 5039 5040 5041 5042 5043 5044 5045 5046 5047 5048 5049 5050 5051 5052 | } /* ** Advance the cursor to the next entry in the database. If ** successful then set *pRes=0. If the cursor ** was already pointing to the last entry in the database before ** this routine was called, then set *pRes=1. ** ** The main entry point is sqlite3BtreeNext(). That routine is optimized ** for the common case of merely incrementing the cell counter BtCursor.aiIdx ** to the next cell on the current page. The (slower) btreeNext() helper ** routine is called when it is necessary to move to a different page or ** to restore the cursor. ** ** The calling function will set *pRes to 0 or 1. The initial *pRes value ** will be 1 if the cursor being stepped corresponds to an SQL index and ** if this routine could have been skipped if that SQL index had been ** a unique index. Otherwise the caller will have set *pRes to zero. ** Zero is the common case. The btree implementation is free to use the ** initial *pRes value as a hint to improve performance, but the current ** SQLite btree implementation does not. (Note that the comdb2 btree ** implementation does use this hint, however.) */ static SQLITE_NOINLINE int btreeNext(BtCursor *pCur, int *pRes){ int rc; int idx; MemPage *pPage; assert( cursorHoldsMutex(pCur) ); assert( pCur->skipNext==0 || pCur->eState!=CURSOR_VALID ); assert( *pRes==0 ); if( pCur->eState!=CURSOR_VALID ){ assert( (pCur->curFlags & BTCF_ValidOvfl)==0 ); rc = restoreCursorPosition(pCur); if( rc!=SQLITE_OK ){ return rc; } if( CURSOR_INVALID==pCur->eState ){ *pRes = 1; return SQLITE_OK; } if( pCur->skipNext ){ assert( pCur->eState==CURSOR_VALID || pCur->eState==CURSOR_SKIPNEXT ); pCur->eState = CURSOR_VALID; if( pCur->skipNext>0 ){ pCur->skipNext = 0; 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. */ testcase( idx>pPage->nCell ); if( idx>=pPage->nCell ){ if( !pPage->leaf ){ rc = moveToChild(pCur, get4byte(&pPage->aData[pPage->hdrOffset+8])); if( rc ) return rc; return moveToLeftmost(pCur); } do{ 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 ){ return SQLITE_OK; }else{ return moveToLeftmost(pCur); } } int sqlite3BtreeNext(BtCursor *pCur, int *pRes){ MemPage *pPage; assert( cursorHoldsMutex(pCur) ); 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->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); } } /* ** Step the cursor to the back to the previous entry in the database. If ** successful then set *pRes=0. If the cursor ** was already pointing to the first entry in the database before ** this routine was called, then set *pRes=1. ** ** The main entry point is sqlite3BtreePrevious(). That routine is optimized ** for the common case of merely decrementing the cell counter BtCursor.aiIdx ** to the previous cell on the current page. The (slower) btreePrevious() helper ** routine is called when it is necessary to move to a different page or ** to restore the cursor. ** ** The calling function will set *pRes to 0 or 1. The initial *pRes value ** will be 1 if the cursor being stepped corresponds to an SQL index and ** if this routine could have been skipped if that SQL index had been ** a unique index. Otherwise the caller will have set *pRes to zero. ** Zero is the common case. The btree implementation is free to use the ** initial *pRes value as a hint to improve performance, but the current ** SQLite btree implementation does not. (Note that the comdb2 btree ** implementation does use this hint, however.) */ static SQLITE_NOINLINE int btreePrevious(BtCursor *pCur, int *pRes){ int rc; MemPage *pPage; assert( cursorHoldsMutex(pCur) ); assert( pRes!=0 ); assert( *pRes==0 ); assert( pCur->skipNext==0 || pCur->eState!=CURSOR_VALID ); assert( (pCur->curFlags & (BTCF_AtLast|BTCF_ValidOvfl|BTCF_ValidNKey))==0 ); assert( pCur->info.nSize==0 ); if( pCur->eState!=CURSOR_VALID ){ assert( pCur->eState>=CURSOR_REQUIRESEEK ); rc = btreeRestoreCursorPosition(pCur); if( rc!=SQLITE_OK ){ return rc; } if( CURSOR_INVALID==pCur->eState ){ *pRes = 1; return SQLITE_OK; } if( pCur->skipNext ){ assert( pCur->eState==CURSOR_VALID || pCur->eState==CURSOR_SKIPNEXT ); pCur->eState = CURSOR_VALID; if( pCur->skipNext<0 ){ pCur->skipNext = 0; return SQLITE_OK; } 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_ValidNKey|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; } } 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->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() ** has already been called on the new page.) The new page has also |
︙ | ︙ |