/*

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

*/

#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

#ifdef SQLITE_DEBUG

/*

** Return and reset the seek counter for a Btree object.

*/

sqlite3_uint64 sqlite3BtreeSeekCount(Btree *pBt){

u64 n = pBt->nSeek;

pBt->nSeek = 0;

return n;

}

#endif

/*

** Implementation of the SQLITE_CORRUPT_PAGE() macro. Takes a single

** (MemPage*) as an argument. The (MemPage*) must not be NULL.

**

** If SQLITE_DEBUG is not defined, then this macro is equivalent to

** SQLITE_CORRUPT_BKPT. Or, if SQLITE_DEBUG is set, then the log message

** normally produced as a side-effect of SQLITE_CORRUPT_BKPT is augmented

** with the page number and filename associated with the (MemPage*).

*/

#ifdef SQLITE_DEBUG

int corruptPageError(int lineno, MemPage *p){

char *zMsg;

sqlite3BeginBenignMalloc();

zMsg = sqlite3_mprintf("database corruption page %u of %s",

p->pgno, sqlite3PagerFilename(p->pBt->pPager, 0)

);

sqlite3EndBenignMalloc();

if( zMsg ){

sqlite3ReportError(SQLITE_CORRUPT, lineno, zMsg);

}

sqlite3_free(zMsg);

return SQLITE_CORRUPT_BKPT;

}

# define SQLITE_CORRUPT_PAGE(pMemPage) corruptPageError(__LINE__, pMemPage)

#else

# define SQLITE_CORRUPT_PAGE(pMemPage) SQLITE_CORRUPT_PGNO(pMemPage->pgno)

#endif

/* Default value for SHARED_LOCK_TRACE macro if shared-cache is disabled

** or if the lock tracking is disabled. This is always the value for

** release builds.

*/

#define SHARED_LOCK_TRACE(X,MSG,TAB,TYPE) /*no-op*/

#ifndef SQLITE_OMIT_SHARED_CACHE

#if 0

/* ^---- Change to 1 and recompile to enable shared-lock tracing

** for debugging purposes.

**

** Print all shared-cache locks on a BtShared. Debugging use only.

*/

static void sharedLockTrace(

BtShared *pBt,

const char *zMsg,

int iRoot,

int eLockType

){

BtLock *pLock;

if( iRoot>0 ){

printf("%s-%p %u%s:", zMsg, pBt, iRoot, eLockType==READ_LOCK?"R":"W");

}else{

printf("%s-%p:", zMsg, pBt);

}

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

printf(" %p/%u%s", pLock->pBtree, pLock->iTable,

pLock->eLock==READ_LOCK ? "R" : "W");

while( pLock->pNext && pLock->pBtree==pLock->pNext->pBtree ){

pLock = pLock->pNext;

printf(",%u%s", pLock->iTable, pLock->eLock==READ_LOCK ? "R" : "W");

}

}

printf("\n");

fflush(stdout);

}

#undef SHARED_LOCK_TRACE

#define SHARED_LOCK_TRACE(X,MSG,TAB,TYPE) sharedLockTrace(X,MSG,TAB,TYPE)

#endif /* Shared-lock tracing */

#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_ReadUncommit))

){

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;

int bSeen = 0;

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

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

if( pIdx->tnum==iRoot ){

if( bSeen ){

/* Two or more indexes share the same root page. There must

** be imposter tables. So just return true. The assert is not

** useful in that case. */

return 1;

}

iTab = pIdx->pTable->tnum;

bSeen = 1;

}

}

}else{

iTab = iRoot;

}

SHARED_LOCK_TRACE(pBtree->pBt,"hasLock",iRoot,eLockType);

/* 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_ReadUncommit)

){

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_ReadUncommit)||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;

SHARED_LOCK_TRACE(pBt,"setLock", iTable, eLock);

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_schema

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

assert( 0==(p->db->flags&SQLITE_ReadUncommit) || 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_BKPT;

}

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 );

SHARED_LOCK_TRACE(pBt, "clearAllLocks", 0, 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;

SHARED_LOCK_TRACE(pBt, "downgradeLocks", 0, 0);

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

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

static void releasePageNotNull(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);

}

/* Verify that the cursor and the BtShared agree about what is the current

** database connetion. This is important in shared-cache mode. If the database

** connection pointers get out-of-sync, it is possible for routines like

** btreeInitPage() to reference an stale connection pointer that references a

** a connection that has already closed. This routine is used inside assert()

** statements only and for the purpose of double-checking that the btree code

** does keep the database connection pointers up-to-date.

*/

static int cursorOwnsBtShared(BtCursor *p){

assert( cursorHoldsMutex(p) );

return (p->pBtree->db==p->pBt->db);

}

#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 */

Pgno pgnoRoot, /* The table that might be changing */

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

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

){

BtCursor *p;

assert( pBtree->hasIncrblobCur );

assert( sqlite3BtreeHoldsMutex(pBtree) );

pBtree->hasIncrblobCur = 0;

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

if( (p->curFlags & BTCF_Incrblob)!=0 ){

pBtree->hasIncrblobCur = 1;

if( p->pgnoRoot==pgnoRoot && (isClearTable || p->info.nKey==iRow) ){

p->eState = CURSOR_INVALID;

}

}

}

}

#else

/* Stub function when INCRBLOB is omitted */

#define invalidateIncrblobCursors(w,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_BKPT;

}

}

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) || sqlite3BitvecTestNotNull(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;

if( pCur->iPage>=0 ){

for(i=0; i<pCur->iPage; i++){

releasePageNotNull(pCur->apPage[i]);

}

releasePageNotNull(pCur->pPage);

pCur->iPage = -1;

}

}

/*

** The cursor passed as the only argument must point to a valid entry

** when this function is called (i.e. have eState==CURSOR_VALID). This

** function saves the current cursor key in variables pCur->nKey and

** pCur->pKey. SQLITE_OK is returned if successful or an SQLite error

** code otherwise.

**

** If the cursor is open on an intkey table, then the integer key

** (the rowid) is stored in pCur->nKey and pCur->pKey is left set to

** NULL. If the cursor is open on a non-intkey table, then pCur->pKey is

** set to point to a malloced buffer pCur->nKey bytes in size containing

** the key.

*/

static int saveCursorKey(BtCursor *pCur){

int rc = SQLITE_OK;

assert( CURSOR_VALID==pCur->eState );

assert( 0==pCur->pKey );

assert( cursorHoldsMutex(pCur) );

if( pCur->curIntKey ){

/* Only the rowid is required for a table btree */

pCur->nKey = sqlite3BtreeIntegerKey(pCur);

}else{

/* For an index btree, save the complete key content. It is possible

** that the current key is corrupt. In that case, it is possible that

** the sqlite3VdbeRecordUnpack() function may overread the buffer by

** up to the size of 1 varint plus 1 8-byte value when the cursor

** position is restored. Hence the 17 bytes of padding allocated

** below. */

void *pKey;

pCur->nKey = sqlite3BtreePayloadSize(pCur);

pKey = sqlite3Malloc( ((i64)pCur->nKey) + 9 + 8 );

if( pKey ){

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

if( rc==SQLITE_OK ){

memset(((u8*)pKey)+pCur->nKey, 0, 9+8);

pCur->pKey = pKey;

}else{

sqlite3_free(pKey);

}

}else{

rc = SQLITE_NOMEM_BKPT;

}

}

assert( !pCur->curIntKey || !pCur->pKey );

return rc;

}

/*

** 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 || CURSOR_SKIPNEXT==pCur->eState );

assert( 0==pCur->pKey );

assert( cursorHoldsMutex(pCur) );

if( pCur->curFlags & BTCF_Pinned ){

return SQLITE_CONSTRAINT_PINNED;

}

if( pCur->eState==CURSOR_SKIPNEXT ){

pCur->eState = CURSOR_VALID;

}else{

pCur->skipNext = 0;

}

rc = saveCursorKey(pCur);

if( rc==SQLITE_OK ){

btreeReleaseAllCursorPages(pCur);

pCur->eState = CURSOR_REQUIRESEEK;

}

pCur->curFlags &= ~(BTCF_ValidNKey|BTCF_ValidOvfl|BTCF_AtLast);

return rc;

}

/* Forward reference */

static int SQLITE_NOINLINE saveCursorsOnList(BtCursor*,Pgno,BtCursor*);

/*

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

** the table with root-page iRoot. "Saving the cursor position" means that

** the location in the btree is remembered in such a way that it can be

** moved back to the same spot after the btree has been modified. This

** routine is called just before cursor pExcept is used to modify the

** table, for example in BtreeDelete() or BtreeInsert().

**

** If there are two or more cursors on the same btree, then all such

** cursors should have their BTCF_Multiple flag set. The btreeCursor()

** routine enforces that rule. This routine only needs to be called in

** the uncommon case when pExpect has the BTCF_Multiple flag set.

**

** If pExpect!=NULL and if no other cursors are found on the same root-page,

** then the BTCF_Multiple flag on pExpect is cleared, to avoid another

** pointless call to this routine.

**

** Implementation note: This routine merely checks to see if any cursors

** need to be saved. It calls out to saveCursorsOnList() in the (unusual)

** event that cursors are in need to being saved.

*/

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) ) break;

}

if( p ) return saveCursorsOnList(p, iRoot, pExcept);

if( pExcept ) pExcept->curFlags &= ~BTCF_Multiple;

return SQLITE_OK;

}

/* This helper routine to saveAllCursors does the actual work of saving

** the cursors if and when a cursor is found that actually requires saving.

** The common case is that no cursors need to be saved, so this routine is

** broken out from its caller to avoid unnecessary stack pointer movement.

*/

static int SQLITE_NOINLINE saveCursorsOnList(

BtCursor *p, /* The first cursor that needs saving */

Pgno iRoot, /* Only save cursor with this iRoot. Save all if zero */

BtCursor *pExcept /* Do not save this cursor */

){

do{

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

if( p->eState==CURSOR_VALID || p->eState==CURSOR_SKIPNEXT ){

int rc = saveCursorPosition(p);

if( SQLITE_OK!=rc ){

return rc;

}

}else{

testcase( p->iPage>=0 );

btreeReleaseAllCursorPages(p);

}

}

p = p->pNext;

}while( 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 sqlite3BtreeIndexMoveto() 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 */

if( pKey ){

KeyInfo *pKeyInfo = pCur->pKeyInfo;

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

pIdxKey = sqlite3VdbeAllocUnpackedRecord(pKeyInfo);

if( pIdxKey==0 ) return SQLITE_NOMEM_BKPT;

sqlite3VdbeRecordUnpack((int)nKey, pKey, pIdxKey);

if( pIdxKey->nField==0 || pIdxKey->nField>pKeyInfo->nAllField ){

rc = SQLITE_CORRUPT_BKPT;

}else{

rc = sqlite3BtreeIndexMoveto(pCur, pIdxKey, pRes);

}

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

}else{

pIdxKey = 0;

rc = sqlite3BtreeTableMoveto(pCur, nKey, bias, pRes);

}

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;

int skipNext = 0;

assert( cursorOwnsBtShared(pCur) );

assert( pCur->eState>=CURSOR_REQUIRESEEK );

if( pCur->eState==CURSOR_FAULT ){

return pCur->skipNext;

}

pCur->eState = CURSOR_INVALID;

if( sqlite3FaultSim(410) ){

rc = SQLITE_IOERR;

}else{

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

}

if( rc==SQLITE_OK ){

sqlite3_free(pCur->pKey);

pCur->pKey = 0;

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

if( skipNext ) pCur->skipNext = skipNext;

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 where

** it was last placed, or has been invalidated for any other reason.

** Cursors can move when the row they are pointing at is deleted out

** from under them, for example. Cursor might also move if a btree

** is rebalanced.

**

** Calling this routine with a NULL cursor pointer returns false.

**

** Use the separate sqlite3BtreeCursorRestore() routine to restore a cursor

** back to where it ought to be if this routine returns true.

*/

int sqlite3BtreeCursorHasMoved(BtCursor *pCur){

assert( EIGHT_BYTE_ALIGNMENT(pCur)

|| pCur==sqlite3BtreeFakeValidCursor() );

assert( offsetof(BtCursor, eState)==0 );

assert( sizeof(pCur->eState)==1 );

return CURSOR_VALID != *(u8*)pCur;

}

/*

** Return a pointer to a fake BtCursor object that will always answer

** false to the sqlite3BtreeCursorHasMoved() routine above. The fake

** cursor returned must not be used with any other Btree interface.

*/

BtCursor *sqlite3BtreeFakeValidCursor(void){

static u8 fakeCursor = CURSOR_VALID;

assert( offsetof(BtCursor, eState)==0 );

return (BtCursor*)&fakeCursor;

}

/*

** This routine restores a cursor back to its original position after it

** has been moved by some outside activity (such as a btree rebalance or

** a row having been deleted out from under the cursor).

**

** On success, the *pDifferentRow parameter is false if the cursor is left

** pointing at exactly the same row. *pDifferntRow is the row the cursor

** was pointing to has been deleted, forcing the cursor to point to some

** nearby row.

**

** This routine should only be called for a cursor that just returned

** TRUE from sqlite3BtreeCursorHasMoved().

*/

int sqlite3BtreeCursorRestore(BtCursor *pCur, int *pDifferentRow){

int rc;

assert( pCur!=0 );

assert( pCur->eState!=CURSOR_VALID );

rc = restoreCursorPosition(pCur);

if( rc ){

*pDifferentRow = 1;

return rc;

}

if( pCur->eState!=CURSOR_VALID ){

*pDifferentRow = 1;

}else{

*pDifferentRow = 0;

}

return SQLITE_OK;

}

#ifdef SQLITE_ENABLE_CURSOR_HINTS

/*

** Provide hints to the cursor. The particular hint given (and the type

** and number of the varargs parameters) is determined by the eHintType

** parameter. See the definitions of the BTREE_HINT_* macros for details.

*/

void sqlite3BtreeCursorHint(BtCursor *pCur, int eHintType, ...){

/* Used only by system that substitute their own storage engine */

#ifdef SQLITE_DEBUG

if( ALWAYS(eHintType==BTREE_HINT_RANGE) ){

va_list ap;

Expr *pExpr;