Index: src/btInt.h ================================================================== --- src/btInt.h +++ src/btInt.h @@ -67,10 +67,11 @@ /* ** Read, write and trim existing database pages. */ int sqlite4BtPageGet(BtPager*, u32 pgno, BtPage **ppPage); +int sqlite4BtPageTrimPgno(BtPager*, u32 pgno); int sqlite4BtPageWrite(BtPage*); int sqlite4BtPageTrim(BtPage*); int sqlite4BtPageRelease(BtPage*); void sqlite4BtPageReference(BtPage*); Index: src/bt_main.c ================================================================== --- src/bt_main.c +++ src/bt_main.c @@ -26,12 +26,16 @@ #define BT_PGFLAGS_INTERNAL 0x01 /* True for non-leaf nodes */ #ifndef MIN # define MIN(a,b) (((a)<(b))?(a):(b)) #endif +#ifndef MAX +# define MAX(a,b) (((a)>(b))?(a):(b)) +#endif #define BT_EXPENSIVE_ASSERT 0 +/* #define BT_STDERR_DEBUG 1 */ struct bt_db { sqlite4_env *pEnv; /* SQLite environment */ BtPager *pPager; /* Underlying page-based database */ bt_cursor *pAllCsr; /* List of all open cursors */ @@ -209,10 +213,11 @@ btCsrSetup(db, pCsr); pCsr->pNextCsr = db->pAllCsr; db->pAllCsr = pCsr; } + btCheckPageRefs(db); return rc; } static void btCsrReset(bt_cursor *pCsr, int bFreeBuffer){ int i; @@ -223,15 +228,18 @@ pCsr->nPg = 0; } int sqlite4BtCsrClose(bt_cursor *pCsr){ if( pCsr ){ + bt_db *pDb = pCsr->pDb; bt_cursor **pp; + btCheckPageRefs(pDb); btCsrReset(pCsr, 1); - for(pp=&pCsr->pDb->pAllCsr; *pp!=pCsr; pp=&(*pp)->pNextCsr); + for(pp=&pDb->pAllCsr; *pp!=pCsr; pp=&(*pp)->pNextCsr); *pp = pCsr->pNextCsr; - sqlite4_free(pCsr->pDb->pEnv, pCsr); + sqlite4_free(pDb->pEnv, pCsr); + btCheckPageRefs(pDb); } return SQLITE4_OK; } void *sqlite4BtCsrExtra(bt_cursor *pCsr){ @@ -246,10 +254,11 @@ if( pCsr->nPg>=BT_MAX_DEPTH ){ rc = btErrorBkpt(SQLITE4_CORRUPT); }else{ rc = sqlite4BtPageGet(pCsr->pDb->pPager, pgno, &pCsr->apPage[pCsr->nPg]); if( rc==SQLITE4_OK ){ + assert( pCsr->apPage[pCsr->nPg] ); pCsr->nPg++; } } return rc; } @@ -262,10 +271,11 @@ static int btCsrAscend(bt_cursor *pCsr, int nLvl){ int i; for(i=0; inPg>0 ); i++){ pCsr->nPg--; sqlite4BtPageRelease(pCsr->apPage[pCsr->nPg]); + pCsr->apPage[pCsr->nPg] = 0; } return (pCsr->nPg==0 ? SQLITE4_NOTFOUND : SQLITE4_OK); } /************************************************************************** @@ -379,67 +389,25 @@ #endif /* ** This function compares the key passed via parameters pK and nK to the -** key stored as part of cell iCell on the database page stored in buffer -** aData (size nData bytes). +** key that cursor pCsr currently points to. ** -** If the cell key is C, and the user key K, then this function sets: +** If the cursor key is C, and the user key K, then this function sets: ** ** *piRes = (C - K). ** -** In other workds, *piRes is +ve, zero or -ve if C is respectively larger, +** In other words, *piRes is +ve, zero or -ve if C is respectively larger, ** equal to or smaller than K. */ -#if 0 static int btCellKeyCompare( bt_cursor *pCsr, /* Cursor handle */ - const u8 *aData, int nData, /* Page data (nData is the page size) */ - int iCell, /* Cell to compare key from */ - const u8 *pK, int nK, /* Key to compare to cell key */ + int bLeaf, /* True if cursor currently points to leaf */ + const void *pK, int nK, /* Key to compare against cursor key */ int *piRes /* OUT: Result of comparison */ ){ - BtPage *pLeaf = 0; /* Leaf page reference to release */ - int rc = SQLITE4_OK; - int nCellKey; /* Number of bytes in cell key */ - int res; - u8 *pCell = btCellFind((u8*)aData, nData, iCell); - int nCmp; - int nAscend = 0; - - pCell += sqlite4BtVarintGet32(pCell, &nCellKey); - if( nCellKey==0 ){ - if( (btFlags(aData, nData) & BT_PGFLAGS_INTERNAL)==0 ){ - rc = sqlite4BtCsrKey(pCsr, &pCell, &nCellKey); - }else{ - rc = btOverflowBuffer(pCsr, 0); - if( rc!=SQLITE4_OK ) return rc; - pK = pCsr->ovfl.pBuf; - }else{ - assert( 0 ); - } - } - - nCmp = MIN(nCellKey, nK); - res = memcmp(pCell, pK, nCmp); - if( res==0 ){ - res = nCellKey - nK; - } - - *piRes = res; - return rc; -} -#endif - -static int btCellKeyCompare( - bt_cursor *pCsr, - int bLeaf, - const void *pK, - int nK, - int *piRes -){ const void *pCsrKey; int nCsrKey; int nCmp; int nAscend = 0; int rc = SQLITE4_OK; @@ -453,21 +421,22 @@ u8 *aData = sqlite4BtPageData(pCsr->apPage[pCsr->nPg-1]); u8 *pCell = btCellFind(aData, pgsz, pCsr->aiCell[pCsr->nPg-1]); pCsrKey = pCell + sqlite4BtVarintGet32(pCell, &nCsrKey); if( nCsrKey==0 ){ + int iCell = pCsr->aiCell[pCsr->nPg-1]+1; while( 1 ){ u8 *aData = sqlite4BtPageData(pCsr->apPage[pCsr->nPg-1]); - u32 pgno = btChildPgno(aData, pgsz, pCsr->aiCell[pCsr->nPg-1]); + u32 pgno = btChildPgno(aData, pgsz, iCell); nAscend++; rc = btCsrDescend(pCsr, pgno); if( rc!=SQLITE4_OK ) break; aData = sqlite4BtPageData(pCsr->apPage[pCsr->nPg-1]); - pCsr->aiCell[pCsr->nPg-1] = btCellCount(aData, pgsz); + pCsr->aiCell[pCsr->nPg-1] = 0; if( (btFlags(aData) & BT_PGFLAGS_INTERNAL)==0 ) break; + iCell = 0; } - pCsr->aiCell[pCsr->nPg-1]--; rc = sqlite4BtCsrKey(pCsr, &pCsrKey, &nCsrKey); } } if( rc==SQLITE4_OK ){ @@ -534,16 +503,13 @@ iHi = iTst; } } if( rc!=SQLITE4_OK ) break; assert( iHi==iLo ); + + iHi += (bLeaf==0 && res==0); pCsr->aiCell[pCsr->nPg-1] = iHi; - -#if 0 -printPage(stderr, pgno, aData, pgsz); -#endif - if( bLeaf==0 ){ pgno = btChildPgno(aData, pgsz, iHi); }else{ pgno = 0; @@ -575,11 +541,15 @@ bt_cursor *pCsr, const void *pK, /* Key to seek for */ int nK, /* Size of key pK in bytes */ int eSeek /* Seek mode (a BT_SEEK_XXX constant) */ ){ - return btCsrSeek(pCsr, pK, nK, eSeek, 0); + int rc; + btCheckPageRefs(pCsr->pDb); + rc = btCsrSeek(pCsr, pK, nK, eSeek, 0); + btCheckPageRefs(pCsr->pDb); + return rc; } /* ** This function seeks the cursor as required for either sqlite4BtCsrFirst() ** (if parameter bLast is false) or sqlite4BtCsrLast() (if bLast is true). @@ -1680,10 +1650,64 @@ assert( rc!=SQLITE4_OK || iCall==p->nCell ); return rc; } +/* +** Extract a key-prefix from page pPg, which resides in a database with +** page size pgsz. If parameter bLast is true, the key-prefix is extracted +** from the right-most cell on the page. If bLast is false, the key-prefix +** is extracted from the left-most cell. +** +** A pointer to the key-prefix is returned. Before returning, *pnByte is +** set to the size of the prefix in bytes. +*/ +static u8 *btKeyPrefix(const int pgsz, BtPage *pPg, int bLast, int *pnByte){ + u8 *p; + int n; + u8 *aData; + + aData = sqlite4BtPageData(pPg); + p = btCellFind(aData, pgsz, bLast ? btCellCount(aData, pgsz)-1 : 0); + p += sqlite4BtVarintGet32(p, &n); + if( n==0 ) p += sqlite4BtVarintGet32(p, &n); + + *pnByte = n; + return p; +} + +/* +** Parameters pLeft and pRight point to a pair of adjacent leaf pages in +** a database with page size pgsz. The keys in pRight are larger than those +** in pLeft. This function populates pKV->pK and pKV->nK with a separator +** key that is: +** +** * larger than all keys on pLeft, and +** * smaller than or equal to all keys on pRight. +*/ +static void btPrefixKey( + const int pgsz, BtPage *pLeft, BtPage *pRight, KeyValue *pKV +){ + int nMax; + int nMaxPrefix = pgsz/4; + + u8 *aLeft; int nLeft; + u8 *aRight; int nRight; + u8 *aData; + int i; + + aLeft = btKeyPrefix(pgsz, pLeft, 1, &nLeft); + aRight = btKeyPrefix(pgsz, pRight, 0, &nRight); + + nMax = MIN(nLeft, nMaxPrefix); + for(i=0; ipK = aRight; + pKV->nK = i + 1; + assert( pKV->nK<=nRight ); + } +} int btBalance( bt_cursor *pCsr, /* Cursor pointed to page to rebalance */ int bLeaf, /* True if rebalancing leaf pages */ int nKV, /* Number of entries in apKV[] array */ @@ -1855,20 +1879,13 @@ ** push up into the parent page. This is only required when rebalancing ** b-tree leaves. When internal nodes are balanced, the btBalanceOutput ** loop accumulates the cells destined for the parent page. */ for(iPg=0; iPg<(ctx.nOut-1); iPg++){ ctx.aPCell[iPg].pgno = sqlite4BtPagePgno(ctx.apPg[iPg]); - assert( ctx.aPCell[iPg].nK==0 ); - if( bLeaf ){ -#if 0 - u8 *aData = sqlite4BtPageData(ctx.apPg[iPg]); - u8 *pCell; - pCell = btCellFind(aData, pgsz, btCellCount(aData, pgsz)-1); - pCell += sqlite4BtVarintGet32(pCell, &ctx.aPCell[iPg].nK); - ctx.aPCell[iPg].pK = pCell; -#endif + assert( ctx.aPCell[iPg].nK==0 ); + btPrefixKey(pgsz, ctx.apPg[iPg], ctx.apPg[iPg+1], &ctx.aPCell[iPg]); } } rc = btSetChildPgno( pDb, pPar, iSib+ctx.nIn-1, sqlite4BtPagePgno(ctx.apPg[ctx.nOut-1]) @@ -2180,16 +2197,14 @@ return rc; } int sqlite4BtDelete(bt_cursor *pCsr){ int rc; - btCheckPageRefs(pCsr->pDb); rc = btDeleteFromPage(pCsr, 1); if( rc==SQLITE4_OK ){ rc = btBalanceIfUnderfull(pCsr); } - btCheckPageRefs(pCsr->pDb); return rc; } int sqlite4BtSetCookie(bt_db *db, unsigned int iVal){ return sqlite4BtPagerSetCookie(db->pPager, iVal); Index: src/bt_pager.c ================================================================== --- src/bt_pager.c +++ src/bt_pager.c @@ -499,15 +499,16 @@ pRet = 0; } } } + assert( (pRet!=0)==(rc==SQLITE4_OK) ); if( rc==SQLITE4_OK ){ p->nTotalRef++; pRet->nRef++; - *ppPg = pRet; } + *ppPg = pRet; return rc; } int sqlite4BtPageWrite(BtPage *pPg){ if( (pPg->flags & BT_PAGE_DIRTY)==0 ){ @@ -525,10 +526,17 @@ int sqlite4BtPageTrim(BtPage *pPg){ /* assert( !"todo" ); */ sqlite4BtPageRelease(pPg); return SQLITE4_OK; } + +/* +** Page number pgno is no longer in use. +*/ +int sqlite4BtPageTrimPgno(BtPager *pPager, u32 pgno){ + return SQLITE4_OK; +} int sqlite4BtPageRelease(BtPage *pPg){ if( pPg ){ assert( pPg->nRef>=1 ); pPg->nRef--;