/*

** 2004 April 6

**

** The author disclaims copyright to this source code. In place of

** a legal notice, here is a blessing:

**

** 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.

**

*************************************************************************

** This file implements a external (disk-based) database using BTrees.

** See the header comment on "btreeInt.h" for additional information.

** Including a description of file format and an overview of operation.

*/

#include "btreeInt.h"

/*

** The header string that appears at the beginning of every

** SQLite database.

*/

static const char zMagicHeader[] = SQLITE_FILE_HEADER;

/*

** Set this global variable to 1 to enable tracing using the TRACE

** macro.

*/

#if 0

int sqlite3BtreeTrace=1; /* True to enable tracing */

# define TRACE(X) if(sqlite3BtreeTrace){printf X;fflush(stdout);}

#else

# define TRACE(X)

#endif

/*

** Extract a 2-byte big-endian integer from an array of unsigned bytes.

** But if the value is zero, make it 65536.

**

** This routine is used to extract the "offset to cell content area" value

** from the header of a btree page. If the page size is 65536 and the page

** is empty, the offset should be 65536, but the 2-byte value stores zero.

** This routine makes the necessary adjustment to 65536.

*/

#define get2byteNotZero(X) (((((int)get2byte(X))-1)&0xffff)+1)

/*

** Values passed as the 5th argument to allocateBtreePage()

*/

#define BTALLOC_ANY 0 /* Allocate any page */

#define BTALLOC_EXACT 1 /* Allocate exact page if possible */

#define BTALLOC_LE 2 /* Allocate any page <= the parameter */

/*

** Macro IfNotOmitAV(x) returns (x) if SQLITE_OMIT_AUTOVACUUM is not

** defined, or 0 if it is. For example:

**

** bIncrVacuum = IfNotOmitAV(pBtShared->incrVacuum);

*/

#ifndef SQLITE_OMIT_AUTOVACUUM

#define IfNotOmitAV(expr) (expr)

#else

#define IfNotOmitAV(expr) 0

#endif

#ifndef SQLITE_OMIT_SHARED_CACHE

/*

** A list of BtShared objects that are eligible for participation

** in shared cache. This variable has file scope during normal builds,

** but the test harness needs to access it so we make it global for

** test builds.

**

** Access to this variable is protected by SQLITE_MUTEX_STATIC_MASTER.

*/

#ifdef SQLITE_TEST

BtShared *SQLITE_WSD sqlite3SharedCacheList = 0;

#else

static BtShared *SQLITE_WSD sqlite3SharedCacheList = 0;

#endif

#endif /* SQLITE_OMIT_SHARED_CACHE */

#ifndef SQLITE_OMIT_SHARED_CACHE

/*

** Enable or disable the shared pager and schema features.

**

** This routine has no effect on existing database connections.

** The shared cache setting effects only future calls to

** sqlite3_open(), sqlite3_open16(), or sqlite3_open_v2().

*/

int sqlite3_enable_shared_cache(int enable){

sqlite3GlobalConfig.sharedCacheEnabled = enable;

return SQLITE_OK;

}

#endif

#ifdef SQLITE_OMIT_SHARED_CACHE

/*

** The functions querySharedCacheTableLock(), setSharedCacheTableLock(),

** and clearAllSharedCacheTableLocks()

** manipulate entries in the BtShared.pLock linked list used to store

** shared-cache table level locks. If the library is compiled with the

** shared-cache feature disabled, then there is only ever one user

** of each BtShared structure and so this locking is not necessary.

** So define the lock related functions as no-ops.

*/

#define querySharedCacheTableLock(a,b,c) SQLITE_OK

#define setSharedCacheTableLock(a,b,c) SQLITE_OK

#define clearAllSharedCacheTableLocks(a)

#define downgradeAllSharedCacheTableLocks(a)

#define hasSharedCacheTableLock(a,b,c,d) 1

#define hasReadConflicts(a, b) 0

#endif

#ifndef SQLITE_OMIT_SHARED_CACHE

#ifdef SQLITE_DEBUG

/*

**** This function is only used as part of an assert() statement. ***

**

** Check to see if pBtree holds the required locks to read or write to the

** table with root page iRoot. Return 1 if it does and 0 if not.

**

** For example, when writing to a table with root-page iRoot via

** Btree connection pBtree:

**

** assert( hasSharedCacheTableLock(pBtree, iRoot, 0, WRITE_LOCK) );

**

** When writing to an index that resides in a sharable database, the

** caller should have first obtained a lock specifying the root page of

** the corresponding table. This makes things a bit more complicated,

** as this module treats each table as a separate structure. To determine

** the table corresponding to the index being written, this

** function has to search through the database schema.

**

** Instead of a lock on the table/index rooted at page iRoot, the caller may

** hold a write-lock on the schema table (root page 1). This is also

** acceptable.

*/

static int hasSharedCacheTableLock(

Btree *pBtree, /* Handle that must hold lock */

Pgno iRoot, /* Root page of b-tree */

int isIndex, /* True if iRoot is the root of an index b-tree */

int eLockType /* Required lock type (READ_LOCK or WRITE_LOCK) */

){

Schema *pSchema = (Schema *)pBtree->pBt->pSchema;

Pgno iTab = 0;

BtLock *pLock;

/* If this database is not shareable, or if the client is reading

** and has the read-uncommitted flag set, then no lock is required.

** Return true immediately.

*/

if( (pBtree->sharable==0)

|| (eLockType==READ_LOCK && (pBtree->db->flags & SQLITE_ReadUncommitted))

){

return 1;

}

/* If the client is reading or writing an index and the schema is

** not loaded, then it is too difficult to actually check to see if

** the correct locks are held. So do not bother - just return true.

** This case does not come up very often anyhow.

*/

if( isIndex && (!pSchema || (pSchema->schemaFlags&DB_SchemaLoaded)==0) ){

return 1;

}

/* Figure out the root-page that the lock should be held on. For table

** b-trees, this is just the root page of the b-tree being read or

** written. For index b-trees, it is the root page of the associated

** table. */

if( isIndex ){

HashElem *p;

for(p=sqliteHashFirst(&pSchema->idxHash); p; p=sqliteHashNext(p)){

Index *pIdx = (Index *)sqliteHashData(p);

if( pIdx->tnum==(int)iRoot ){

iTab = pIdx->pTable->tnum;

}

}

}else{

iTab = iRoot;

}

/* Search for the required lock. Either a write-lock on root-page iTab, a

** write-lock on the schema table, or (if the client is reading) a

** read-lock on iTab will suffice. Return 1 if any of these are found. */

for(pLock=pBtree->pBt->pLock; pLock; pLock=pLock->pNext){

if( pLock->pBtree==pBtree

&& (pLock->iTable==iTab || (pLock->eLock==WRITE_LOCK && pLock->iTable==1))

&& pLock->eLock>=eLockType

){

return 1;

}

}

/* Failed to find the required lock. */

return 0;

}

#endif /* SQLITE_DEBUG */

#ifdef SQLITE_DEBUG

/*

**** This function may be used as part of assert() statements only. ****

**

** Return true if it would be illegal for pBtree to write into the

** table or index rooted at iRoot because other shared connections are

** simultaneously reading that same table or index.

**

** It is illegal for pBtree to write if some other Btree object that

** shares the same BtShared object is currently reading or writing

** the iRoot table. Except, if the other Btree object has the

** read-uncommitted flag set, then it is OK for the other object to

** have a read cursor.

**

** For example, before writing to any part of the table or index

** rooted at page iRoot, one should call:

**

** assert( !hasReadConflicts(pBtree, iRoot) );

*/

static int hasReadConflicts(Btree *pBtree, Pgno iRoot){

BtCursor *p;

for(p=pBtree->pBt->pCursor; p; p=p->pNext){

if( p->pgnoRoot==iRoot

&& p->pBtree!=pBtree

&& 0==(p->pBtree->db->flags & SQLITE_ReadUncommitted)

){

return 1;

}

}

return 0;

}

#endif /* #ifdef SQLITE_DEBUG */

/*

** Query to see if Btree handle p may obtain a lock of type eLock

** (READ_LOCK or WRITE_LOCK) on the table with root-page iTab. Return

** SQLITE_OK if the lock may be obtained (by calling

** setSharedCacheTableLock()), or SQLITE_LOCKED if not.

*/

static int querySharedCacheTableLock(Btree *p, Pgno iTab, u8 eLock){

BtShared *pBt = p->pBt;

BtLock *pIter;

assert( sqlite3BtreeHoldsMutex(p) );

assert( eLock==READ_LOCK || eLock==WRITE_LOCK );

assert( p->db!=0 );

assert( !(p->db->flags&SQLITE_ReadUncommitted)||eLock==WRITE_LOCK||iTab==1 );

/* If requesting a write-lock, then the Btree must have an open write

** transaction on this file. And, obviously, for this to be so there

** must be an open write transaction on the file itself.

*/

assert( eLock==READ_LOCK || (p==pBt->pWriter && p->inTrans==TRANS_WRITE) );

assert( eLock==READ_LOCK || pBt->inTransaction==TRANS_WRITE );

/* This routine is a no-op if the shared-cache is not enabled */

if( !p->sharable ){

return SQLITE_OK;

}

/* If some other connection is holding an exclusive lock, the

** requested lock may not be obtained.

*/

if( pBt->pWriter!=p && (pBt->btsFlags & BTS_EXCLUSIVE)!=0 ){

sqlite3ConnectionBlocked(p->db, pBt->pWriter->db);

return SQLITE_LOCKED_SHAREDCACHE;

}

for(pIter=pBt->pLock; pIter; pIter=pIter->pNext){

/* The condition (pIter->eLock!=eLock) in the following if(...)

** statement is a simplification of:

**

** (eLock==WRITE_LOCK || pIter->eLock==WRITE_LOCK)

**

** since we know that if eLock==WRITE_LOCK, then no other connection

** may hold a WRITE_LOCK on any table in this file (since there can

** only be a single writer).

*/

assert( pIter->eLock==READ_LOCK || pIter->eLock==WRITE_LOCK );

assert( eLock==READ_LOCK || pIter->pBtree==p || pIter->eLock==READ_LOCK);

if( pIter->pBtree!=p && pIter->iTable==iTab && pIter->eLock!=eLock ){

sqlite3ConnectionBlocked(p->db, pIter->pBtree->db);

if( eLock==WRITE_LOCK ){

assert( p==pBt->pWriter );

pBt->btsFlags |= BTS_PENDING;

}

return SQLITE_LOCKED_SHAREDCACHE;

}

}

return SQLITE_OK;

}

#endif /* !SQLITE_OMIT_SHARED_CACHE */

#ifndef SQLITE_OMIT_SHARED_CACHE

/*

** Add a lock on the table with root-page iTable to the shared-btree used

** by Btree handle p. Parameter eLock must be either READ_LOCK or

** WRITE_LOCK.

**

** This function assumes the following:

**

** (a) The specified Btree object p is connected to a sharable

** database (one with the BtShared.sharable flag set), and

**

** (b) No other Btree objects hold a lock that conflicts

** with the requested lock (i.e. querySharedCacheTableLock() has

** already been called and returned SQLITE_OK).

**

** SQLITE_OK is returned if the lock is added successfully. SQLITE_NOMEM

** is returned if a malloc attempt fails.

*/

static int setSharedCacheTableLock(Btree *p, Pgno iTable, u8 eLock){

BtShared *pBt = p->pBt;

BtLock *pLock = 0;

BtLock *pIter;

assert( sqlite3BtreeHoldsMutex(p) );

assert( eLock==READ_LOCK || eLock==WRITE_LOCK );

assert( p->db!=0 );

/* A connection with the read-uncommitted flag set will never try to

** obtain a read-lock using this function. The only read-lock obtained

** by a connection in read-uncommitted mode is on the sqlite_master

** table, and that lock is obtained in BtreeBeginTrans(). */

assert( 0==(p->db->flags&SQLITE_ReadUncommitted) || eLock==WRITE_LOCK );

/* This function should only be called on a sharable b-tree after it

** has been determined that no other b-tree holds a conflicting lock. */

assert( p->sharable );

assert( SQLITE_OK==querySharedCacheTableLock(p, iTable, eLock) );

/* First search the list for an existing lock on this table. */

for(pIter=pBt->pLock; pIter; pIter=pIter->pNext){

if( pIter->iTable==iTable && pIter->pBtree==p ){

pLock = pIter;

break;

}

}

/* If the above search did not find a BtLock struct associating Btree p

** with table iTable, allocate one and link it into the list.

*/

if( !pLock ){

pLock = (BtLock *)sqlite3MallocZero(sizeof(BtLock));

if( !pLock ){

return SQLITE_NOMEM;

}

pLock->iTable = iTable;

pLock->pBtree = p;

pLock->pNext = pBt->pLock;

pBt->pLock = pLock;

}

/* Set the BtLock.eLock variable to the maximum of the current lock

** and the requested lock. This means if a write-lock was already held

** and a read-lock requested, we don't incorrectly downgrade the lock.

*/

assert( WRITE_LOCK>READ_LOCK );

if( eLock>pLock->eLock ){

pLock->eLock = eLock;

}

return SQLITE_OK;

}

#endif /* !SQLITE_OMIT_SHARED_CACHE */

#ifndef SQLITE_OMIT_SHARED_CACHE

/*

** Release all the table locks (locks obtained via calls to

** the setSharedCacheTableLock() procedure) held by Btree object p.

**

** This function assumes that Btree p has an open read or write

** transaction. If it does not, then the BTS_PENDING flag

** may be incorrectly cleared.

*/

static void clearAllSharedCacheTableLocks(Btree *p){

BtShared *pBt = p->pBt;

BtLock **ppIter = &pBt->pLock;

assert( sqlite3BtreeHoldsMutex(p) );

assert( p->sharable || 0==*ppIter );

assert( p->inTrans>0 );

while( *ppIter ){

BtLock *pLock = *ppIter;

assert( (pBt->btsFlags & BTS_EXCLUSIVE)==0 || pBt->pWriter==pLock->pBtree );

assert( pLock->pBtree->inTrans>=pLock->eLock );

if( pLock->pBtree==p ){

*ppIter = pLock->pNext;

assert( pLock->iTable!=1 || pLock==&p->lock );

if( pLock->iTable!=1 ){

sqlite3_free(pLock);

}

}else{

ppIter = &pLock->pNext;

}

}

assert( (pBt->btsFlags & BTS_PENDING)==0 || pBt->pWriter );

if( pBt->pWriter==p ){

pBt->pWriter = 0;

pBt->btsFlags &= ~(BTS_EXCLUSIVE|BTS_PENDING);

}else if( pBt->nTransaction==2 ){

/* This function is called when Btree p is concluding its

** transaction. If there currently exists a writer, and p is not

** that writer, then the number of locks held by connections other

** than the writer must be about to drop to zero. In this case

** set the BTS_PENDING flag to 0.

**

** If there is not currently a writer, then BTS_PENDING must

** be zero already. So this next line is harmless in that case.

*/

pBt->btsFlags &= ~BTS_PENDING;

}

}

/*

** This function changes all write-locks held by Btree p into read-locks.

*/

static void downgradeAllSharedCacheTableLocks(Btree *p){

BtShared *pBt = p->pBt;

if( pBt->pWriter==p ){

BtLock *pLock;

pBt->pWriter = 0;

pBt->btsFlags &= ~(BTS_EXCLUSIVE|BTS_PENDING);

for(pLock=pBt->pLock; pLock; pLock=pLock->pNext){

assert( pLock->eLock==READ_LOCK || pLock->pBtree==p );

pLock->eLock = READ_LOCK;

}

}

}

#endif /* SQLITE_OMIT_SHARED_CACHE */

static void releasePage(MemPage *pPage); /* Forward reference */

/*

***** This routine is used inside of assert() only ****

**

** Verify that the cursor holds the mutex on its BtShared

*/

#ifdef SQLITE_DEBUG

static int cursorHoldsMutex(BtCursor *p){

return sqlite3_mutex_held(p->pBt->mutex);

}

#endif

/*

** Invalidate the overflow cache of the cursor passed as the first argument.

** on the shared btree structure pBt.

*/

#define invalidateOverflowCache(pCur) (pCur->curFlags &= ~BTCF_ValidOvfl)

/*

** Invalidate the overflow page-list cache for all cursors opened

** on the shared btree structure pBt.

*/

static void invalidateAllOverflowCache(BtShared *pBt){

BtCursor *p;

assert( sqlite3_mutex_held(pBt->mutex) );

for(p=pBt->pCursor; p; p=p->pNext){

invalidateOverflowCache(p);

}

}

#ifndef SQLITE_OMIT_INCRBLOB

/*

** This function is called before modifying the contents of a table

** to invalidate any incrblob cursors that are open on the

** row or one of the rows being modified.

**

** If argument isClearTable is true, then the entire contents of the

** table is about to be deleted. In this case invalidate all incrblob

** cursors open on any row within the table with root-page pgnoRoot.

**

** Otherwise, if argument isClearTable is false, then the row with

** rowid iRow is being replaced or deleted. In this case invalidate

** only those incrblob cursors open on that specific row.

*/

static void invalidateIncrblobCursors(

Btree *pBtree, /* The database file to check */

i64 iRow, /* The rowid that might be changing */

int isClearTable /* True if all rows are being deleted */

){

BtCursor *p;

BtShared *pBt = pBtree->pBt;

assert( sqlite3BtreeHoldsMutex(pBtree) );

for(p=pBt->pCursor; p; p=p->pNext){

if( (p->curFlags & BTCF_Incrblob)!=0 && (isClearTable || p->info.nKey==iRow) ){

p->eState = CURSOR_INVALID;

}

}

}

#else

/* Stub function when INCRBLOB is omitted */

#define invalidateIncrblobCursors(x,y,z)

#endif /* SQLITE_OMIT_INCRBLOB */

/*

** Set bit pgno of the BtShared.pHasContent bitvec. This is called

** when a page that previously contained data becomes a free-list leaf

** page.

**

** The BtShared.pHasContent bitvec exists to work around an obscure

** bug caused by the interaction of two useful IO optimizations surrounding

** free-list leaf pages:

**

** 1) When all data is deleted from a page and the page becomes

** a free-list leaf page, the page is not written to the database

** (as free-list leaf pages contain no meaningful data). Sometimes

** such a page is not even journalled (as it will not be modified,

** why bother journalling it?).

**

** 2) When a free-list leaf page is reused, its content is not read

** from the database or written to the journal file (why should it

** be, if it is not at all meaningful?).

**

** By themselves, these optimizations work fine and provide a handy

** performance boost to bulk delete or insert operations. However, if

** a page is moved to the free-list and then reused within the same

** transaction, a problem comes up. If the page is not journalled when

** it is moved to the free-list and it is also not journalled when it

** is extracted from the free-list and reused, then the original data

** may be lost. In the event of a rollback, it may not be possible

** to restore the database to its original configuration.

**

** The solution is the BtShared.pHasContent bitvec. Whenever a page is

** moved to become a free-list leaf page, the corresponding bit is

** set in the bitvec. Whenever a leaf page is extracted from the free-list,

** optimization 2 above is omitted if the corresponding bit is already

** set in BtShared.pHasContent. The contents of the bitvec are cleared

** at the end of every transaction.

*/

static int btreeSetHasContent(BtShared *pBt, Pgno pgno){

int rc = SQLITE_OK;

if( !pBt->pHasContent ){

assert( pgno<=pBt->nPage );

pBt->pHasContent = sqlite3BitvecCreate(pBt->nPage);

if( !pBt->pHasContent ){

rc = SQLITE_NOMEM;

}

}

if( rc==SQLITE_OK && pgno<=sqlite3BitvecSize(pBt->pHasContent) ){

rc = sqlite3BitvecSet(pBt->pHasContent, pgno);

}

return rc;

}

/*

** Query the BtShared.pHasContent vector.

**

** This function is called when a free-list leaf page is removed from the

** free-list for reuse. It returns false if it is safe to retrieve the

** page from the pager layer with the 'no-content' flag set. True otherwise.

*/

static int btreeGetHasContent(BtShared *pBt, Pgno pgno){

Bitvec *p = pBt->pHasContent;

return (p && (pgno>sqlite3BitvecSize(p) || sqlite3BitvecTest(p, pgno)));

}

/*

** Clear (destroy) the BtShared.pHasContent bitvec. This should be

** invoked at the conclusion of each write-transaction.

*/

static void btreeClearHasContent(BtShared *pBt){

sqlite3BitvecDestroy(pBt->pHasContent);

pBt->pHasContent = 0;

}

/*

** Release all of the apPage[] pages for a cursor.

*/

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.

**

** The caller must ensure that the cursor is valid (has eState==CURSOR_VALID)

** prior to calling this routine.

*/

static int saveCursorPosition(BtCursor *pCur){

int rc;

assert( CURSOR_VALID==pCur->eState );

assert( 0==pCur->pKey );

assert( cursorHoldsMutex(pCur) );

rc = sqlite3BtreeKeySize(pCur, &pCur->nKey);

assert( rc==SQLITE_OK ); /* KeySize() cannot fail */

/* If this is an intKey table, then the above call to BtreeKeySize()

** stores the integer key in pCur->nKey. In this case this value is

** all that is required. Otherwise, if pCur is not open on an intKey

** table, then malloc space for and store the pCur->nKey bytes of key

** data.

*/

if( 0==pCur->apPage[0]->intKey ){

void *pKey = sqlite3Malloc( (int)pCur->nKey );

if( pKey ){

rc = sqlite3BtreeKey(pCur, 0, (int)pCur->nKey, pKey);

if( rc==SQLITE_OK ){

pCur->pKey = pKey;

}else{

sqlite3_free(pKey);

}

}else{

rc = SQLITE_NOMEM;

}

}

assert( !pCur->apPage[0]->intKey || !pCur->pKey );

if( rc==SQLITE_OK ){

btreeReleaseAllCursorPages(pCur);

pCur->eState = CURSOR_REQUIRESEEK;

}

invalidateOverflowCache(pCur);

return rc;

}

/*

** Save the positions of all cursors (except pExcept) that are open on

** the table with root-page iRoot. Usually, this is called just before cursor

** pExcept is used to modify the table (BtreeDelete() or BtreeInsert()).

*/

static int saveAllCursors(BtShared *pBt, Pgno iRoot, BtCursor *pExcept){

BtCursor *p;

assert( sqlite3_mutex_held(pBt->mutex) );

assert( pExcept==0 || pExcept->pBt==pBt );

for(p=pBt->pCursor; p; p=p->pNext){

if( p!=pExcept && (0==iRoot || p->pgnoRoot==iRoot) ){

if( p->eState==CURSOR_VALID ){

int rc = saveCursorPosition(p);

if( SQLITE_OK!=rc ){

return rc;

}

}else{

testcase( p->iPage>0 );

btreeReleaseAllCursorPages(p);

}

}

}

return SQLITE_OK;

}

/*

** Clear the current cursor position.

*/

void sqlite3BtreeClearCursor(BtCursor *pCur){

assert( cursorHoldsMutex(pCur) );

sqlite3_free(pCur->pKey);

pCur->pKey = 0;

pCur->eState = CURSOR_INVALID;

}

/*

** In this version of BtreeMoveto, pKey is a packed index record

** such as is generated by the OP_MakeRecord opcode. Unpack the

** record and then call BtreeMovetoUnpacked() to do the work.

*/

static int btreeMoveto(

BtCursor *pCur, /* Cursor open on the btree to be searched */

const void *pKey, /* Packed key if the btree is an index */

i64 nKey, /* Integer key for tables. Size of pKey for indices */

int bias, /* Bias search to the high end */

int *pRes /* Write search results here */

){

int rc; /* Status code */

UnpackedRecord *pIdxKey; /* Unpacked index key */

char aSpace[200]; /* Temp space for pIdxKey - to avoid a malloc */

char *pFree = 0;

if( pKey ){

assert( nKey==(i64)(int)nKey );

pIdxKey = sqlite3VdbeAllocUnpackedRecord(

pCur->pKeyInfo, aSpace, sizeof(aSpace), &pFree

);

if( pIdxKey==0 ) return SQLITE_NOMEM;

sqlite3VdbeRecordUnpack(pCur->pKeyInfo, (int)nKey, pKey, pIdxKey);

if( pIdxKey->nField==0 ){

sqlite3DbFree(pCur->pKeyInfo->db, pFree);

return SQLITE_CORRUPT_BKPT;

}

}else{

pIdxKey = 0;

}

rc = sqlite3BtreeMovetoUnpacked(pCur, pIdxKey, nKey, bias, pRes);

if( pFree ){

sqlite3DbFree(pCur->pKeyInfo->db, pFree);

}

return rc;

}

/*

** Restore the cursor to the position it was in (or as close to as possible)

** when saveCursorPosition() was called. Note that this call deletes the

** saved position info stored by saveCursorPosition(), so there can be

** at most one effective restoreCursorPosition() call after each

** saveCursorPosition().

*/

static int btreeRestoreCursorPosition(BtCursor *pCur){

int rc;

assert( cursorHoldsMutex(pCur) );

assert( pCur->eState>=CURSOR_REQUIRESEEK );

if( pCur->eState==CURSOR_FAULT ){

return pCur->skipNext;

}

pCur->eState = CURSOR_INVALID;

rc = btreeMoveto(pCur, pCur->pKey, pCur->nKey, 0, &pCur->skipNext);

if( rc==SQLITE_OK ){

sqlite3_free(pCur->pKey);

pCur->pKey = 0;

assert( pCur->eState==CURSOR_VALID || pCur->eState==CURSOR_INVALID );

if( pCur->skipNext && pCur->eState==CURSOR_VALID ){

pCur->eState = CURSOR_SKIPNEXT;

}

}

return rc;

}

#define restoreCursorPosition(p) \

(p->eState>=CURSOR_REQUIRESEEK ? \

btreeRestoreCursorPosition(p) : \

SQLITE_OK)

/*

** Determine whether or not a cursor has moved from the position it

** was last placed at. Cursors can move when the row they are pointing

** at is deleted out from under them.

**

** This routine returns an error code if something goes wrong. The

** integer *pHasMoved is set as follows:

**

** 0: The cursor is unchanged

** 1: The cursor is still pointing at the same row, but the pointers

** returned by sqlite3BtreeKeyFetch() or sqlite3BtreeDataFetch()

** might now be invalid because of a balance() or other change to the

** b-tree.

** 2: The cursor is no longer pointing to the row. The row might have

** been deleted out from under the cursor.

*/

int sqlite3BtreeCursorHasMoved(BtCursor *pCur, int *pHasMoved){

int rc;

if( pCur->eState==CURSOR_VALID ){

*pHasMoved = 0;

return SQLITE_OK;

}

rc = restoreCursorPosition(pCur);

if( rc ){

*pHasMoved = 2;

return rc;

}

if( pCur->eState!=CURSOR_VALID || NEVER(pCur->skipNext!=0) ){

*pHasMoved = 2;

}else{

*pHasMoved = 1;

}

return SQLITE_OK;

}

#ifndef SQLITE_OMIT_AUTOVACUUM

/*

** Given a page number of a regular database page, return the page

** number for the pointer-map page that contains the entry for the

** input page number.

**

** Return 0 (not a valid page) for pgno==1 since there is

** no pointer map associated with page 1. The integrity_check logic

** requires that ptrmapPageno(*,1)!=1.

*/

static Pgno ptrmapPageno(BtShared *pBt, Pgno pgno){

int nPagesPerMapPage;

Pgno iPtrMap, ret;

assert( sqlite3_mutex_held(pBt->mutex) );

if( pgno<2 ) return 0;

nPagesPerMapPage = (pBt->usableSize/5)+1;

iPtrMap = (pgno-2)/nPagesPerMapPage;

ret = (iPtrMap*nPagesPerMapPage) + 2;

if( ret==PENDING_BYTE_PAGE(pBt) ){

ret++;

}

return ret;

}

/*

** Write an entry into the pointer map.

**

** This routine updates the pointer map entry for page number 'key'

** so that it maps to type 'eType' and parent page number 'pgno'.

**

** If *pRC is initially non-zero (non-SQLITE_OK) then this routine is

** a no-op. If an error occurs, the appropriate error code is written

** into *pRC.

*/

static void ptrmapPut(BtShared *pBt, Pgno key, u8 eType, Pgno parent, int *pRC){

DbPage *pDbPage; /* The pointer map page */

u8 *pPtrmap; /* The pointer map data */

Pgno iPtrmap; /* The pointer map page number */

int offset; /* Offset in pointer map page */

int rc; /* Return code from subfunctions */

if( *pRC ) return;

assert( sqlite3_mutex_held(pBt->mutex) );

/* The master-journal page number must never be used as a pointer map page */

assert( 0==PTRMAP_ISPAGE(pBt, PENDING_BYTE_PAGE(pBt)) );

assert( pBt->autoVacuum );

if( key==0 ){

*pRC = SQLITE_CORRUPT_BKPT;

return;

}

iPtrmap = PTRMAP_PAGENO(pBt, key);

rc = sqlite3PagerGet(pBt->pPager, iPtrmap, &pDbPage);

if( rc!=SQLITE_OK ){

*pRC = rc;

return;

}

offset = PTRMAP_PTROFFSET(iPtrmap, key);

if( offset<0 ){

*pRC = SQLITE_CORRUPT_BKPT;

goto ptrmap_exit;

}

assert( offset <= (int)pBt->usableSize-5 );

pPtrmap = (u8 *)sqlite3PagerGetData(pDbPage);

if( eType!=pPtrmap[offset] || get4byte(&pPtrmap[offset+1])!=parent ){

TRACE(("PTRMAP_UPDATE: %d->(%d,%d)\n", key, eType, parent));

*pRC= rc = sqlite3PagerWrite(pDbPage);

if( rc==SQLITE_OK ){

pPtrmap[offset] = eType;

put4byte(&pPtrmap[offset+1], parent);

}

}

ptrmap_exit:

sqlite3PagerUnref(pDbPage);

}

/*

** Read an entry from the pointer map.

**

** This routine retrieves the pointer map entry for page 'key', writing

** the type and parent page number to *pEType and *pPgno respectively.

** An error code is returned if something goes wrong, otherwise SQLITE_OK.

*/

static int ptrmapGet(BtShared *pBt, Pgno key, u8 *pEType, Pgno *pPgno){

DbPage *pDbPage; /* The pointer map page */

int iPtrmap; /* Pointer map page index */

u8 *pPtrmap; /* Pointer map page data */

int offset; /* Offset of entry in pointer map */

int rc;

assert( sqlite3_mutex_held(pBt->mutex) );

iPtrmap = PTRMAP_PAGENO(pBt, key);

rc = sqlite3PagerGet(pBt->pPager, iPtrmap, &pDbPage);

if( rc!=0 ){

return rc;

}

pPtrmap = (u8 *)sqlite3PagerGetData(pDbPage);

offset = PTRMAP_PTROFFSET(iPtrmap, key);

if( offset<0 ){

sqlite3PagerUnref(pDbPage);

return SQLITE_CORRUPT_BKPT;

}

assert( offset <= (int)pBt->usableSize-5 );

assert( pEType!=0 );

*pEType = pPtrmap[offset];

if( pPgno ) *pPgno = get4byte(&pPtrmap[offset+1]);

sqlite3PagerUnref(pDbPage);

if( *pEType<1 || *pEType>5 ) return SQLITE_CORRUPT_BKPT;

return SQLITE_OK;

}

#else /* if defined SQLITE_OMIT_AUTOVACUUM */

#define ptrmapPut(w,x,y,z,rc)

#define ptrmapGet(w,x,y,z) SQLITE_OK

#define ptrmapPutOvflPtr(x, y, rc)

#endif

/*

** Given a btree page and a cell index (0 means the first cell on

** the page, 1 means the second cell, and so forth) return a pointer

** to the cell content.

**

** This routine works only for pages that do not contain overflow cells.

*/

#define findCell(P,I) \

((P)->aData + ((P)->maskPage & get2byte(&(P)->aCellIdx[2*(I)])))

#define findCellv2(D,M,O,I) (D+(M&get2byte(D+(O+2*(I)))))

/*

** This a more complex version of findCell() that works for

** pages that do contain overflow cells.

*/

static u8 *findOverflowCell(MemPage *pPage, int iCell){

int i;

assert( sqlite3_mutex_held(pPage->pBt->mutex) );

for(i=pPage->nOverflow-1; i>=0; i--){

int k;

k = pPage->aiOvfl[i];

if( k<=iCell ){

if( k==iCell ){

return pPage->apOvfl[i];

}

iCell--;

}

}

return findCell(pPage, iCell);

}

/*

** Parse a cell content block and fill in the CellInfo structure. There

** are two versions of this function. btreeParseCell() takes a

** cell index as the second argument and btreeParseCellPtr()

** takes a pointer to the body of the cell as its second argument.

**

** Within this file, the parseCell() macro can be called instead of

** btreeParseCellPtr(). Using some compilers, this will be faster.

*/

static void btreeParseCellPtr(

MemPage *pPage, /* Page containing the cell */

u8 *pCell, /* Pointer to the cell text. */

CellInfo *pInfo /* Fill in this structure */

){

u16 n; /* Number bytes in cell content header */

u32 nPayload; /* Number of bytes of cell payload */

assert( sqlite3_mutex_held(pPage->pBt->mutex) );

pInfo->pCell = pCell;

assert( pPage->leaf==0 || pPage->leaf==1 );

n = pPage->childPtrSize;

assert( n==4-4*pPage->leaf );

if( pPage->intKey ){

if( pPage->hasData ){

assert( n==0 );

n = getVarint32(pCell, nPayload);

}else{

nPayload = 0;

}

n += getVarint(&pCell[n], (u64*)&pInfo->nKey);

pInfo->nData = nPayload;

}else{

pInfo->nData = 0;

n += getVarint32(&pCell[n], nPayload);

pInfo->nKey = nPayload;

}

pInfo->nPayload = nPayload;

pInfo->nHeader = n;

testcase( nPayload==pPage->maxLocal );

testcase( nPayload==pPage->maxLocal+1 );

if( likely(nPayload<=pPage->maxLocal) ){

/* This is the (easy) common case where the entire payload fits

** on the local page. No overflow is required.

*/

if( (pInfo->nSize = (u16)(n+nPayload))<4 ) pInfo->nSize = 4;

pInfo->nLocal = (u16)nPayload;

pInfo->iOverflow = 0;

}else{

/* If the payload will not fit completely on the local page, we have

** to decide how much to store locally and how much to spill onto

** overflow pages. The strategy is to minimize the amount of unused

** space on overflow pages while keeping the amount of local storage

** in between minLocal and maxLocal.

**

** Warning: changing the way overflow payload is distributed in any

** way will result in an incompatible file format.

*/

int minLocal; /* Minimum amount of payload held locally */

int maxLocal; /* Maximum amount of payload held locally */

int surplus; /* Overflow payload available for local storage */

minLocal = pPage->minLocal;

maxLocal = pPage->maxLocal;

surplus = minLocal + (nPayload - minLocal)%(pPage->pBt->usableSize - 4);

testcase( surplus==maxLocal );

testcase( surplus==maxLocal+1 );

if( surplus <= maxLocal ){

pInfo->nLocal = (u16)surplus;

}else{

pInfo->nLocal = (u16)minLocal;

}

pInfo->iOverflow = (u16)(pInfo->nLocal + n);