Index: src/btree.c ================================================================== --- src/btree.c +++ src/btree.c @@ -7,11 +7,11 @@ ** May you do good and not evil. ** May you find forgiveness for yourself and forgive others. ** May you share freely, never taking more than you give. ** ************************************************************************* -** $Id: btree.c,v 1.111 2004/05/07 17:57:50 drh Exp $ +** $Id: btree.c,v 1.112 2004/05/07 23:50:57 drh Exp $ ** ** This file implements a external (disk-based) database using BTrees. ** For a detailed discussion of BTrees, refer to ** ** Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3: @@ -264,22 +264,15 @@ void *pArg; /* First arg to xCompare() */ Pgno pgnoRoot; /* The root page of this tree */ MemPage *pPage; /* Page that contains the entry */ int idx; /* Index of the entry in pPage->aCell[] */ u8 wrFlag; /* True if writable */ - u8 eSkip; /* Determines if next step operation is a no-op */ u8 iMatch; /* compare result from last sqlite3BtreeMoveto() */ + u8 isValid; /* TRUE if points to a valid entry */ + u8 status; /* Set to SQLITE_ABORT if cursors is invalidated */ }; -/* -** Legal values for BtCursor.eSkip. -*/ -#define SKIP_NONE 0 /* Always step the cursor */ -#define SKIP_NEXT 1 /* The next sqlite3BtreeNext() is a no-op */ -#define SKIP_PREV 2 /* The next sqlite3BtreePrevious() is a no-op */ -#define SKIP_INVALID 3 /* Calls to Next() and Previous() are invalid */ - /* ** Read or write a two-, four-, and eight-byte big-endian integer values. */ static u32 get2byte(unsigned char *p){ return (p[0]<<8) | p[1]; @@ -403,40 +396,43 @@ addr = 3+hdr; n = 6+hdr; if( !pPage->leaf ){ n += 4; } + memcpy(&newPage[hdr], &oldPage[hdr], n-hdr); start = n; pc = get2byte(&oldPage[addr]); i = 0; while( pc>0 ){ assert( npBt->pageSize ); size = cellSize(pPage, &oldPage[pc]); memcpy(&newPage[n], &oldPage[pc], size); put2byte(&newPage[addr],n); - pPage->aCell[i] = &oldPage[n]; + pPage->aCell[i++] = &oldPage[n]; n += size; addr = pc; pc = get2byte(&oldPage[pc]); } + assert( i==pPage->nCell ); leftover = pPage->pBt->pageSize - n; assert( leftover>=0 ); assert( pPage->nFree==leftover ); if( leftover<4 ){ oldPage[hdr+5] = leftover; leftover = 0; n = pPage->pBt->pageSize; } - memcpy(&oldPage[start], &newPage[start], n-start); + memcpy(&oldPage[hdr], &newPage[hdr], n-hdr); if( leftover==0 ){ - put2byte(&oldPage[hdr+3], 0); + put2byte(&oldPage[hdr+1], 0); }else if( leftover>=4 ){ - put2byte(&oldPage[hdr+3], n); + put2byte(&oldPage[hdr+1], n); put2byte(&oldPage[n], 0); put2byte(&oldPage[n+2], leftover); memset(&oldPage[n+4], 0, leftover-4); } + oldPage[hdr+5] = 0; } /* ** Allocate nByte bytes of space on a page. If nByte is less than ** 4 it is rounded up to 4. @@ -1079,10 +1075,26 @@ pBt->inTrans = 0; pBt->inStmt = 0; unlockBtreeIfUnused(pBt); return rc; } + +/* +** Invalidate all cursors +*/ +static void invalidateCursors(Btree *pBt){ + BtCursor *pCur; + for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){ + MemPage *pPage = pCur->pPage; + if( pPage && !pPage->isInit ){ + releasePage(pPage); + pCur->pPage = 0; + pCur->isValid = 0; + pCur->status = SQLITE_ABORT; + } + } +} /* ** Rollback the transaction in progress. All cursors will be ** invalided by this operation. Any attempt to use a cursor ** that was open at the beginning of this operation will result @@ -1091,22 +1103,15 @@ ** This will release the write lock on the database file. If there ** are no active cursors, it also releases the read lock. */ int sqlite3BtreeRollback(Btree *pBt){ int rc; - BtCursor *pCur; if( pBt->inTrans==0 ) return SQLITE_OK; pBt->inTrans = 0; pBt->inStmt = 0; rc = pBt->readOnly ? SQLITE_OK : sqlite3pager_rollback(pBt->pPager); - for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){ - MemPage *pPage = pCur->pPage; - if( pPage && !pPage->isInit ){ - releasePage(pPage); - pCur->pPage = 0; - } - } + invalidateCursors(pBt); unlockBtreeIfUnused(pBt); return rc; } /* @@ -1153,20 +1158,13 @@ ** to use a cursor that was open at the beginning of this operation ** will result in an error. */ int sqlite3BtreeRollbackStmt(Btree *pBt){ int rc; - BtCursor *pCur; if( pBt->inStmt==0 || pBt->readOnly ) return SQLITE_OK; rc = sqlite3pager_stmt_rollback(pBt->pPager); - for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){ - MemPage *pPage = pCur->pPage; - if( pPage && !pPage->isInit ){ - releasePage(pPage); - pCur->pPage = 0; - } - } + invalidateCursors(pBt); pBt->inStmt = 0; return rc; } /* @@ -1263,11 +1261,10 @@ pCur->xCompare = xCmp ? xCmp : dfltCompare; pCur->pArg = pArg; pCur->pBt = pBt; pCur->wrFlag = wrFlag; pCur->idx = 0; - pCur->eSkip = SKIP_INVALID; pCur->pNext = pBt->pCursor; if( pCur->pNext ){ pCur->pNext->pPrev = pCur; } pCur->pPrev = 0; @@ -1278,10 +1275,12 @@ pRing->pShared = pCur; }else{ pCur->pShared = pCur; } pBt->pCursor = pCur; + pCur->isValid = 0; + pCur->status = SQLITE_OK; *ppCur = pCur; return SQLITE_OK; create_cursor_exception: *ppCur = 0; @@ -1349,17 +1348,19 @@ ** For a table with the INTKEY flag set, this routine returns the key ** itself, not the number of bytes in the key. */ int sqlite3BtreeKeySize(BtCursor *pCur, u64 *pSize){ MemPage *pPage; + unsigned char *cell; - pPage = pCur->pPage; - assert( pPage!=0 ); - if( pCur->idx >= pPage->nCell ){ + if( !pCur->isValid ){ *pSize = 0; }else{ - unsigned char *cell = pPage->aCell[pCur->idx]; + pPage = pCur->pPage; + assert( pPage!=0 ); + assert( pCur->idx>=0 && pCur->idxnCell ); + cell = pPage->aCell[pCur->idx]; cell += 2; /* Skip the offset to the next cell */ if( !pPage->leaf ){ cell += 4; /* Skip the child pointer */ } if( !pPage->zeroData ){ @@ -1392,10 +1393,11 @@ Btree *pBt; u64 nData, nKey; int maxLocal, ovflSize; assert( pCur!=0 && pCur->pPage!=0 ); + assert( pCur->isValid ); pBt = pCur->pBt; pPage = pCur->pPage; assert( pCur->idx>=0 && pCur->idxnCell ); aPayload = pPage->aCell[pCur->idx]; aPayload += 2; /* Skip the next cell index */ @@ -1472,20 +1474,18 @@ ** 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){ - MemPage *pPage; - assert( amt>=0 ); assert( offset>=0 ); + if( pCur->isValid==0 ){ + return pCur->status; + } assert( pCur->pPage!=0 ); - pPage = pCur->pPage; - if( pCur->idx >= pPage->nCell || pPage->intKey ){ - assert( amt==0 ); - return SQLITE_OK; - } + assert( pCur->pPage->intKey==0 ); + assert( pCur->idx>=0 && pCur->idxpPage->nCell ); return getPayload(pCur, offset, amt, (unsigned char*)pBuf, 0); } /* ** Return a pointer to the key of record that cursor pCur @@ -1510,24 +1510,30 @@ unsigned char *aPayload; MemPage *pPage; Btree *pBt; u64 nData, nKey; - assert( pCur!=0 && pCur->pPage!=0 ); + assert( pCur!=0 ); + if( !pCur->isValid ){ + return 0; + } + assert( pCur->pPage!=0 ); + assert( pCur->idx>=0 && pCur->idxpPage->nCell ); pBt = pCur->pBt; pPage = pCur->pPage; assert( pCur->idx>=0 && pCur->idxnCell ); + assert( pPage->intKey==0 ); aPayload = pPage->aCell[pCur->idx]; aPayload += 2; /* Skip the next cell index */ if( !pPage->leaf ){ aPayload += 4; /* Skip the child pointer */ } if( !pPage->zeroData ){ aPayload += getVarint(aPayload, &nData); } aPayload += getVarint(aPayload, &nKey); - if( pPage->intKey || nKey>pBt->maxLocal ){ + if( nKey>pBt->maxLocal ){ return 0; } return aPayload; } @@ -1539,18 +1545,23 @@ ** pointing to an entry (which can happen, for example, if ** the database is empty) then *pSize is set to 0. */ int sqlite3BtreeDataSize(BtCursor *pCur, u32 *pSize){ MemPage *pPage; + unsigned char *cell; + u64 size; + if( !pCur->isValid ){ + return pCur->status ? pCur->status : SQLITE_INTERNAL; + } pPage = pCur->pPage; assert( pPage!=0 ); - if( pCur->idx >= pPage->nCell || pPage->zeroData ){ + assert( pPage->isInit ); + if( pPage->zeroData ){ *pSize = 0; }else{ - unsigned char *cell; - u64 size; + assert( pCur->idx>=0 && pCur->idxnCell ); cell = pPage->aCell[pCur->idx]; cell += 2; /* Skip the offset to the next cell */ if( !pPage->leaf ){ cell += 4; /* Skip the child pointer */ } @@ -1569,19 +1580,17 @@ ** 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 sqlite3BtreeData(BtCursor *pCur, u32 offset, u32 amt, void *pBuf){ - MemPage *pPage; - + if( !pCur->isValid ){ + return pCur->status ? pCur->status : SQLITE_INTERNAL; + } assert( amt>=0 ); assert( offset>=0 ); assert( pCur->pPage!=0 ); - pPage = pCur->pPage; - if( pCur->idx >= pPage->nCell ){ - return 0; - } + assert( pCur->idx>=0 && pCur->idxpPage->nCell ); return getPayload(pCur, offset, amt, pBuf, 1); } /* ** Move the cursor down to a new child page. The newPgno argument is the @@ -1591,10 +1600,11 @@ int rc; MemPage *pNewPage; MemPage *pOldPage; Btree *pBt = pCur->pBt; + assert( pCur->isValid ); rc = getAndInitPage(pBt, newPgno, &pNewPage, pCur->pPage); if( rc ) return rc; pNewPage->idxParent = pCur->idx; pOldPage = pCur->pPage; pOldPage->idxShift = 0; @@ -1635,10 +1645,11 @@ Pgno oldPgno; MemPage *pParent; MemPage *pPage; int idxParent; + assert( pCur->isValid ); pPage = pCur->pPage; assert( pPage!=0 ); assert( !isRootPage(pPage) ); pParent = pPage->pParent; assert( pParent!=0 ); @@ -1684,11 +1695,14 @@ MemPage *pRoot; int rc; Btree *pBt = pCur->pBt; rc = getAndInitPage(pBt, pCur->pgnoRoot, &pRoot, 0); - if( rc ) return rc; + if( rc ){ + pCur->isValid = 0; + return rc; + } releasePage(pCur->pPage); pCur->pPage = pRoot; pCur->idx = 0; if( pRoot->nCell==0 && !pRoot->leaf ){ Pgno subpage; @@ -1695,10 +1709,11 @@ assert( pRoot->pgno==1 ); subpage = get4byte(&pRoot->aData[pRoot->hdrOffset+6]); assert( subpage>0 ); rc = moveToChild(pCur, subpage); } + pCur->isValid = pCur->pPage->nCell>0; return rc; } /* ** Move the cursor down to the left-most leaf entry beneath the @@ -1707,10 +1722,11 @@ static int moveToLeftmost(BtCursor *pCur){ Pgno pgno; int rc; MemPage *pPage; + assert( pCur->isValid ); while( !(pPage = pCur->pPage)->leaf ){ assert( pCur->idx>=0 && pCur->idxnCell ); pgno = get4byte(&pPage->aCell[pCur->idx][2]); rc = moveToChild(pCur, pgno); if( rc ) return rc; @@ -1728,10 +1744,11 @@ static int moveToRightmost(BtCursor *pCur){ Pgno pgno; int rc; MemPage *pPage; + assert( pCur->isValid ); while( !(pPage = pCur->pPage)->leaf ){ pgno = get4byte(&pPage->aData[pPage->hdrOffset+6]); pCur->idx = pPage->nCell; rc = moveToChild(pCur, pgno); if( rc ) return rc; @@ -1744,40 +1761,45 @@ ** 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){ int rc; - if( pCur->pPage==0 ) return SQLITE_ABORT; + if( pCur->status ){ + return pCur->status; + } rc = moveToRoot(pCur); if( rc ) return rc; - if( pCur->pPage->nCell==0 ){ + if( pCur->isValid==0 ){ + assert( pCur->pPage->nCell==0 ); *pRes = 1; return SQLITE_OK; } + assert( pCur->pPage->nCell>0 ); *pRes = 0; rc = moveToLeftmost(pCur); - pCur->eSkip = SKIP_NONE; return rc; } /* Move the cursor to the last 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 sqlite3BtreeLast(BtCursor *pCur, int *pRes){ int rc; - if( pCur->pPage==0 ) return SQLITE_ABORT; + if( pCur->status ){ + return pCur->status; + } rc = moveToRoot(pCur); if( rc ) return rc; - assert( pCur->pPage->isInit ); - if( pCur->pPage->nCell==0 ){ + if( pCur->isValid==0 ){ + assert( pCur->pPage->nCell==0 ); *pRes = 1; return SQLITE_OK; } + assert( pCur->isValid ); *pRes = 0; rc = moveToRightmost(pCur); - pCur->eSkip = SKIP_NONE; return rc; } /* Move the cursor so that it points to an entry near pKey/nKey. ** Return a success code. @@ -1807,14 +1829,22 @@ ** *pRes>0 The cursor is left pointing at an entry that ** is larger than pKey. */ int sqlite3BtreeMoveto(BtCursor *pCur, const void *pKey, u64 nKey, int *pRes){ int rc; - if( pCur->pPage==0 ) return SQLITE_ABORT; - pCur->eSkip = SKIP_NONE; + + if( pCur->status ){ + return pCur->status; + } rc = moveToRoot(pCur); if( rc ) return rc; + assert( pCur->pPage ); + assert( pCur->pPage->isInit ); + if( pCur->isValid==0 ){ + assert( pCur->pPage->nCell==0 ); + return SQLITE_OK; + } for(;;){ int lwr, upr; Pgno chldPg; MemPage *pPage = pCur->pPage; int c = -1; /* pRes return if table is empty must be -1 */ @@ -1863,19 +1893,33 @@ }else{ chldPg = get4byte(&pPage->aCell[lwr][2]); } if( chldPg==0 ){ pCur->iMatch = c; + assert( pCur->idx>=0 && pCur->idxpPage->nCell ); if( pRes ) *pRes = c; return SQLITE_OK; } pCur->idx = lwr; rc = moveToChild(pCur, chldPg); - if( rc ) return rc; + if( rc ){ + return rc; + } } /* NOT REACHED */ } + +/* +** Return TRUE if the cursor is not pointing at an entry of the table. +** +** TRUE will be returned after a call to sqlite3BtreeNext() moves +** past the last entry in the table or sqlite3BtreePrev() moves past +** the first entry. TRUE is also returned if the table is empty. +*/ +int sqlite3BtreeEof(BtCursor *pCur){ + return pCur->isValid==0; +} /* ** 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 @@ -1883,27 +1927,16 @@ */ int sqlite3BtreeNext(BtCursor *pCur, int *pRes){ int rc; MemPage *pPage = pCur->pPage; assert( pRes!=0 ); - if( pPage==0 ){ - *pRes = 1; - return SQLITE_ABORT; - } - assert( pPage->isInit ); - assert( pCur->eSkip!=SKIP_INVALID ); - if( pPage->nCell==0 ){ + if( pCur->isValid==0 ){ *pRes = 1; return SQLITE_OK; } + assert( pPage->isInit ); assert( pCur->idxnCell ); - if( pCur->eSkip==SKIP_NEXT ){ - pCur->eSkip = SKIP_NONE; - *pRes = 0; - return SQLITE_OK; - } - pCur->eSkip = SKIP_NONE; pCur->idx++; if( pCur->idx>=pPage->nCell ){ if( !pPage->leaf ){ rc = moveToChild(pCur, get4byte(&pPage->aData[pPage->hdrOffset+6])); if( rc ) return rc; @@ -1912,10 +1945,11 @@ return rc; } do{ if( isRootPage(pPage) ){ *pRes = 1; + pCur->isValid = 0; return SQLITE_OK; } moveToParent(pCur); pPage = pCur->pPage; }while( pCur->idx>=pPage->nCell ); @@ -1938,37 +1972,27 @@ */ int sqlite3BtreePrevious(BtCursor *pCur, int *pRes){ int rc; Pgno pgno; MemPage *pPage; - pPage = pCur->pPage; - if( pPage==0 ){ - *pRes = 1; - return SQLITE_ABORT; - } - assert( pPage->isInit ); - assert( pCur->eSkip!=SKIP_INVALID ); - if( pPage->nCell==0 ){ + if( pCur->isValid==0 ){ *pRes = 1; return SQLITE_OK; } - if( pCur->eSkip==SKIP_PREV ){ - pCur->eSkip = SKIP_NONE; - *pRes = 0; - return SQLITE_OK; - } - pCur->eSkip = SKIP_NONE; + pPage = pCur->pPage; + assert( pPage->isInit ); assert( pCur->idx>=0 ); if( !pPage->leaf ){ pgno = get4byte(&pPage->aCell[pCur->idx][2]); rc = moveToChild(pCur, pgno); if( rc ) return rc; rc = moveToRightmost(pCur); }else{ while( pCur->idx==0 ){ if( isRootPage(pPage) ){ - if( pRes ) *pRes = 1; + pCur->isValid = 0; + *pRes = 1; return SQLITE_OK; } moveToParent(pCur); pPage = pCur->pPage; } @@ -2922,12 +2946,12 @@ MemPage *pPage; Btree *pBt = pCur->pBt; unsigned char *oldCell; unsigned char newCell[MX_CELL_SIZE]; - if( pCur->pPage==0 ){ - return SQLITE_ABORT; /* A rollback destroyed this cursor */ + if( pCur->status ){ + return pCur->status; /* A rollback destroyed this cursor */ } if( !pBt->inTrans || nKey+nData==0 ){ /* Must start a transaction before doing an insert */ return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR; } @@ -2967,11 +2991,10 @@ insertCell(pPage, pCur->idx, newCell, szNew); rc = balance(pPage); /* sqlite3BtreePageDump(pCur->pBt, pCur->pgnoRoot, 1); */ /* fflush(stdout); */ moveToRoot(pCur); - pCur->eSkip = SKIP_INVALID; return rc; } /* ** Delete the entry that the cursor is pointing to. The cursor @@ -2983,12 +3006,12 @@ int rc; Pgno pgnoChild; Btree *pBt = pCur->pBt; assert( pPage->isInit ); - if( pCur->pPage==0 ){ - return SQLITE_ABORT; /* A rollback destroyed this cursor */ + if( pCur->status ){ + return pCur->status; /* A rollback destroyed this cursor */ } if( !pBt->inTrans ){ /* Must start a transaction before doing a delete */ return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR; } @@ -3274,11 +3297,11 @@ printf("right_child: %d\n", get4byte(&pPage->aData[6])); } nFree = 0; i = 0; idx = get2byte(&pPage->aData[hdrOffset+1]); - while( idx>0 && idx0 && idxpBt->pageSize ){ int sz = get2byte(&pPage->aData[idx+2]); sprintf(range,"%d..%d", idx, idx+sz-1); nFree += sz; printf("freeblock %2d: i=%-10s size=%-4d total=%d\n", i, range, sz, nFree); @@ -3344,11 +3367,11 @@ aResult[6] = 0; } aResult[4] = pPage->nFree; cnt = 0; idx = get2byte(&pPage->aData[pPage->hdrOffset+1]); - while( idx>0 && idx0 && idxpBt->pageSize ){ cnt++; idx = get2byte(&pPage->aData[idx]); } aResult[5] = cnt; aResult[7] = pPage->leaf ? 0 : get4byte(&pPage->aData[pPage->hdrOffset+6]); @@ -3705,11 +3728,11 @@ int rc = SQLITE_OK; Pgno i, nPage, nToPage; if( !pBtTo->inTrans || !pBtFrom->inTrans ) return SQLITE_ERROR; if( pBtTo->pCursor ) return SQLITE_BUSY; - memcpy(pBtTo->pPage1, pBtFrom->pPage1, SQLITE_USABLE_SIZE); + memcpy(pBtTo->pPage1, pBtFrom->pPage1, pBtFrom->pageSize); rc = sqlite3pager_overwrite(pBtTo->pPager, 1, pBtFrom->pPage1); nToPage = sqlite3pager_pagecount(pBtTo->pPager); nPage = sqlite3pager_pagecount(pBtFrom->pPager); for(i=2; rc==SQLITE_OK && i<=nPage; i++){ void *pPage; Index: src/btree.h ================================================================== --- src/btree.h +++ src/btree.h @@ -11,11 +11,11 @@ ************************************************************************* ** This header file defines the interface that the sqlite B-Tree file ** subsystem. See comments in the source code for a detailed description ** of what each interface routine does. ** -** @(#) $Id: btree.h,v 1.38 2004/05/07 13:30:42 drh Exp $ +** @(#) $Id: btree.h,v 1.39 2004/05/07 23:50:57 drh Exp $ */ #ifndef _BTREE_H_ #define _BTREE_H_ /* @@ -70,10 +70,11 @@ int sqlite3BtreeInsert(BtCursor*, const void *pKey, u64 nKey, const void *pData, int nData); int sqlite3BtreeFirst(BtCursor*, int *pRes); int sqlite3BtreeLast(BtCursor*, int *pRes); int sqlite3BtreeNext(BtCursor*, int *pRes); +int sqlite3BtreeEof(BtCursor*); int sqlite3BtreePrevious(BtCursor*, int *pRes); int sqlite3BtreeKeySize(BtCursor*, u64 *pSize); int sqlite3BtreeKey(BtCursor*, u32 offset, u32 amt, void*); void *sqlite3BtreeKeyFetch(BtCursor*); int sqlite3BtreeDataSize(BtCursor*, u32 *pSize); Index: src/test3.c ================================================================== --- src/test3.c +++ src/test3.c @@ -11,11 +11,11 @@ ************************************************************************* ** Code for testing the btree.c module in SQLite. This code ** is not included in the SQLite library. It is used for automated ** testing of the SQLite library. ** -** $Id: test3.c,v 1.27 2004/05/07 17:57:50 drh Exp $ +** $Id: test3.c,v 1.28 2004/05/07 23:50:57 drh Exp $ */ #include "sqliteInt.h" #include "pager.h" #include "btree.h" #include "tcl.h" @@ -807,10 +807,36 @@ } sprintf(zBuf,"%d",res); Tcl_AppendResult(interp, zBuf, 0); return SQLITE_OK; } + +/* +** Usage: btree_eof ID +** +** Return TRUE if the given cursor is not pointing at a valid entry. +** Return FALSE if the cursor does point to a valid entry. +*/ +static int btree_eof( + void *NotUsed, + Tcl_Interp *interp, /* The TCL interpreter that invoked this command */ + int argc, /* Number of arguments */ + const char **argv /* Text of each argument */ +){ + BtCursor *pCur; + char zBuf[50]; + + if( argc!=2 ){ + Tcl_AppendResult(interp, "wrong # args: should be \"", argv[0], + " ID\"", 0); + return TCL_ERROR; + } + if( Tcl_GetInt(interp, argv[1], (int*)&pCur) ) return TCL_ERROR; + sprintf(zBuf, "%d", sqlite3BtreeEof(pCur)); + Tcl_AppendResult(interp, zBuf, 0); + return SQLITE_OK; +} /* ** Usage: btree_keysize ID ** ** Return the number of bytes of key. @@ -1020,10 +1046,11 @@ { "btree_move_to", (Tcl_CmdProc*)btree_move_to }, { "btree_delete", (Tcl_CmdProc*)btree_delete }, { "btree_insert", (Tcl_CmdProc*)btree_insert }, { "btree_next", (Tcl_CmdProc*)btree_next }, { "btree_prev", (Tcl_CmdProc*)btree_prev }, + { "btree_eof", (Tcl_CmdProc*)btree_eof }, { "btree_keysize", (Tcl_CmdProc*)btree_keysize }, { "btree_key", (Tcl_CmdProc*)btree_key }, { "btree_data", (Tcl_CmdProc*)btree_data }, { "btree_payload_size", (Tcl_CmdProc*)btree_payload_size }, { "btree_first", (Tcl_CmdProc*)btree_first }, Index: test/btree.test ================================================================== --- test/btree.test +++ test/btree.test @@ -9,11 +9,11 @@ # #*********************************************************************** # This file implements regression tests for SQLite library. The # focus of this script is btree database backend # -# $Id: btree.test,v 1.16 2004/05/07 17:57:50 drh Exp $ +# $Id: btree.test,v 1.17 2004/05/07 23:50:58 drh Exp $ set testdir [file dirname $argv0] source $testdir/tester.tcl @@ -183,17 +183,21 @@ btree_key $::c1 } {600} do_test btree-3.19 { btree_data $::c1 } {6.00} -do_test btree-3.20 { +do_test btree-3.20.1 { btree_next $::c1 btree_key $::c1 } {0} +do_test btree-3.20.2 { + btree_eof $::c1 +} {1} do_test btree-3.21 { - btree_data $::c1 -} {} + set rc [catch {btree_data $::c1} res] + lappend rc $res +} {1 SQLITE_INTERNAL} # Commit the changes, reopen and reread the data # do_test btree-3.22 { set rc [catch {btree_close_cursor $::c1} msg] @@ -268,12 +272,13 @@ do_test btree-3.39 { btree_next $::c1 btree_key $::c1 } {0} do_test btree-3.40 { - btree_data $::c1 -} {} + set rc [catch {btree_data $::c1} res] + lappend rc $res +} {1 SQLITE_INTERNAL} do_test btree-3.41 { lindex [btree_pager_stats $::b1] 1 } {1} @@ -305,11 +310,11 @@ do_test btree-4.4 { btree_move_to $::c1 0 set r {} while 1 { set key [btree_key $::c1] - if {$key==0} break + if {[btree_eof $::c1]} break lappend r $key lappend r [btree_data $::c1] btree_next $::c1 } set r @@ -321,11 +326,11 @@ btree_commit $::b1 btree_move_to $::c1 0 set r {} while 1 { set key [btree_key $::c1] - if {$key==0} break + if {[btree_eof $::c1]} break lappend r $key lappend r [btree_data $::c1] btree_next $::c1 } set r @@ -350,11 +355,11 @@ do_test btree-4.9 { set r {} btree_first $::c1 while 1 { set key [btree_key $::c1] - if {$key==0} break + if {[btree_eof $::c1]} break lappend r $key lappend r [btree_data $::c1] btree_next $::c1 } set r @@ -394,38 +399,24 @@ btree_get_meta $::b1 } {0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150} proc select_all {cursor} { set r {} - btree_move_to $cursor {} - while 1 { - set key [btree_key $cursor] - if {$key==""} break - lappend r $key - lappend r [btree_data $cursor] - btree_next $cursor - } - return $r -} -proc select_all_intkey {cursor} { - set r {} - btree_move_to $cursor 0 - while 1 { - set key [btree_key $cursor] - if {$key==0} break + btree_first $cursor + while {![btree_eof $cursor]} { + set key [btree_key $cursor] lappend r $key lappend r [btree_data $cursor] btree_next $cursor } return $r } proc select_keys {cursor} { set r {} - btree_move_to $cursor {} - while 1 { + btree_first $cursor + while {![btree_eof $cursor]} { set key [btree_key $cursor] - if {$key==""} break lappend r $key btree_next $cursor } return $r } @@ -447,19 +438,20 @@ set ::c2 [btree_cursor $::b1 $::t2 1] lindex [btree_pager_stats $::b1] 1 } {2} do_test btree-6.2.3 { btree_insert $::c2 ten 10 + btree_move_to $::c2 ten btree_key $::c2 } {ten} do_test btree-6.3 { btree_commit $::b1 set ::c1 [btree_cursor $::b1 1 1] lindex [btree_pager_stats $::b1] 1 } {2} do_test btree-6.3.1 { - select_all_intkey $::c1 + select_all $::c1 } {200 2.00 300 3.00 400 4.00 500 5.00 600 6.00} #btree_page_dump $::b1 3 do_test btree-6.4 { select_all $::c2 } {ten 10} @@ -495,19 +487,19 @@ do_test btree-6.9.1 { btree_move_to $::c2 {} btree_key $::c2 } {} -# If we drop table 2 it just clears the table. Table 2 always exists. +# If we drop table 1 it just clears the table. Table 1 always exists. # do_test btree-6.10 { btree_close_cursor $::c1 - btree_drop_table $::b1 2 - set ::c1 [btree_cursor $::b1 2 1] - btree_move_to $::c1 {} - btree_key $::c1 -} {} + btree_drop_table $::b1 1 + set ::c1 [btree_cursor $::b1 1 1] + btree_first $::c1 + btree_eof $::c1 +} {1} do_test btree-6.11 { btree_commit $::b1 select_all $::c1 } {} do_test btree-6.12 { @@ -514,117 +506,131 @@ select_all $::c2 } {} do_test btree-6.13 { btree_close_cursor $::c2 lindex [btree_pager_stats $::b1] 1 -} {2} +} {1} # Check to see that pages defragment properly. To do this test we will # -# 1. Fill the first page table 2 with data. -# 2. Delete every other entry of table 2. +# 1. Fill the first page of table 1 with data. +# 2. Delete every other entry of table 1. # 3. Insert a single entry that requires more contiguous # space than is available. # do_test btree-7.1 { btree_begin_transaction $::b1 } {} catch {unset key} catch {unset data} do_test btree-7.2 { - for {set i 0} {$i<36} {incr i} { - set key [format %03d $i] - set data "*** $key ***" + # Each record will be 10 bytes in size. + # + 100 bytes of database header + # + 6 bytes of table header + # + 91*10=910 bytes of cells + # Totals 1016 bytes. 8 bytes left over + # Keys are 1000 through 1090. + for {set i 1000} {$i<1091} {incr i} { + set key $i + set data [format %5d $i] btree_insert $::c1 $key $data } lrange [btree_cursor_dump $::c1] 4 5 } {8 1} do_test btree-7.3 { - btree_move_to $::c1 000 - while {[btree_key $::c1]!=""} { + for {set i 1001} {$i<1091} {incr i 2} { + btree_move_to $::c1 $i btree_delete $::c1 - btree_next $::c1 - btree_next $::c1 } + # Freed 45 blocks. Total freespace is 458 + # Keys remaining are even numbers between 1000 and 1090, inclusive lrange [btree_cursor_dump $::c1] 4 5 -} {512 19} +} {458 46} #btree_page_dump $::b1 2 do_test btree-7.4 { - btree_insert $::c1 018 {*** 018 ***+++} + # The largest free block is 10 bytes long. So if we insert + # a record bigger than 10 bytes it should force a defrag + # The record is 20 bytes long. + btree_insert $::c1 2000 {123456789_12345} + btree_move_to $::c1 2000 btree_key $::c1 -} {018} +} {2000} do_test btree-7.5 { lrange [btree_cursor_dump $::c1] 4 5 -} {480 1} +} {438 1} #btree_page_dump $::b1 2 # Delete an entry to make a hole of a known size, then immediately recreate # that entry. This tests the path into allocateSpace where the hole exactly # matches the size of the desired space. # +# Keys are even numbers between 1000 and 1090 and one record of 2000. +# There are 47 keys total. +# do_test btree-7.6 { - btree_move_to $::c1 007 + btree_move_to $::c1 1006 btree_delete $::c1 - btree_move_to $::c1 011 + btree_move_to $::c1 1010 btree_delete $::c1 } {} do_test btree-7.7 { - lindex [btree_cursor_dump $::c1] 5 -} {3} + lrange [btree_cursor_dump $::c1] 4 5 +} {458 3} ;# Create two new holes of 10 bytes each #btree_page_dump $::b1 2 do_test btree-7.8 { - btree_insert $::c1 007 {*** 007 ***} - lindex [btree_cursor_dump $::c1] 5 -} {2} + btree_insert $::c1 1006 { 1006} + lrange [btree_cursor_dump $::c1] 4 5 +} {448 2} ;# Filled in the first hole #btree_page_dump $::b1 2 # Make sure the freeSpace() routine properly coaleses adjacent memory blocks # do_test btree-7.9 { - btree_move_to $::c1 013 - btree_delete $::c1 - lrange [btree_cursor_dump $::c1] 4 5 -} {536 2} -do_test btree-7.10 { - btree_move_to $::c1 009 - btree_delete $::c1 - lrange [btree_cursor_dump $::c1] 4 5 -} {564 2} -do_test btree-7.11 { - btree_move_to $::c1 018 - btree_delete $::c1 - lrange [btree_cursor_dump $::c1] 4 5 -} {596 2} -do_test btree-7.13 { - btree_move_to $::c1 033 - btree_delete $::c1 - lrange [btree_cursor_dump $::c1] 4 5 -} {624 3} -do_test btree-7.14 { - btree_move_to $::c1 035 - btree_delete $::c1 - lrange [btree_cursor_dump $::c1] 4 5 -} {652 2} + btree_move_to $::c1 1012 + btree_delete $::c1 + lrange [btree_cursor_dump $::c1] 4 5 +} {458 2} ;# Coalesce with the whole before +do_test btree-7.10 { + btree_move_to $::c1 1008 + btree_delete $::c1 + lrange [btree_cursor_dump $::c1] 4 5 +} {468 2} ;# Coalesce with whole after +do_test btree-7.11 { + btree_move_to $::c1 1030 + btree_delete $::c1 + lrange [btree_cursor_dump $::c1] 4 5 +} {478 3} ;# Make a new hole +do_test btree-7.13 { + btree_move_to $::c1 1034 + btree_delete $::c1 + lrange [btree_cursor_dump $::c1] 4 5 +} {488 4} ;# Make another hole +do_test btree-7.14 { + btree_move_to $::c1 1032 + btree_delete $::c1 + lrange [btree_cursor_dump $::c1] 4 5 +} {498 3} ;# The freed space should coalesce on both ends #btree_page_dump $::b1 2 do_test btree-7.15 { lindex [btree_pager_stats $::b1] 1 -} {2} +} {1} # Check to see that data on overflow pages work correctly. # do_test btree-8.1 { set data "*** This is a very long key " - while {[string length $data]<256} {append data $data} + while {[string length $data]<1234} {append data $data} set ::data $data - btree_insert $::c1 020 $data + btree_insert $::c1 2020 $data } {} #btree_page_dump $::b1 2 do_test btree-8.1.1 { lindex [btree_pager_stats $::b1] 1 -} {2} +} {1} #btree_pager_ref_dump $::b1 do_test btree-8.2 { + btree_move_to $::c1 2020 string length [btree_data $::c1] } [string length $::data] do_test btree-8.3 { btree_data $::c1 } $::data @@ -636,13 +642,14 @@ } [expr {int(([string length $::data]-238+1019)/1020)}] do_test btree-8.5 { set data "*** This is an even longer key" while {[string length $data]<2000} {append data $data} set ::data $data - btree_insert $::c1 020 $data + btree_insert $::c1 2030 $data } {} do_test btree-8.6 { + btree_move_to 2030 string length [btree_data $::c1] } [string length $::data] do_test btree-8.7 { btree_data $::c1 } $::data @@ -652,21 +659,21 @@ } $::data do_test btree-8.9 { btree_close_cursor $::c1 btree_close $::b1 set ::b1 [btree_open test1.bt 2000 0] - set ::c1 [btree_cursor $::b1 2 1] - btree_move_to $::c1 020 + set ::c1 [btree_cursor $::b1 1 1] + btree_move_to $::c1 2030 btree_data $::c1 } $::data do_test btree-8.10 { btree_begin_transaction $::b1 btree_delete $::c1 } {} do_test btree-8.11 { lindex [btree_get_meta $::b1] 0 -} [expr {int(([string length $::data]-238+1019)/1020)}] +} {} # Now check out keys on overflow pages. # do_test btree-8.12 { set ::keyprefix "This is a long prefix to a key "