SQLite

/*
** 2007 August 27
**
** 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.
**
*************************************************************************
**
** $Id: btmutex.c,v 1.8 2007/12/07 18:55:28 drh Exp $
**
** This file contains code used to implement mutexes on Btree objects.
** This code really belongs in btree.c.  But btree.c is getting too
** big and we want to break it down some.  This packaged seemed like
** a good breakout.
*/
#include "btreeInt.h"

  /* Some basic sanity checking on the Btree.  The list of Btrees
  ** connected by pNext and pPrev should be in sorted order by
  ** Btree.pBt value. All elements of the list should belong to
  ** the same connection. Only shared Btrees are on the list. */
  assert( p->pNext==0 || p->pNext->pBt>p->pBt );
  assert( p->pPrev==0 || p->pPrev->pBt<p->pBt );
  assert( p->pNext==0 || p->pNext->db==p->db );
  assert( p->pPrev==0 || p->pPrev->db==p->db );
  assert( p->sharable || (p->pNext==0 && p->pPrev==0) );

  /* Check for locking consistency */
  assert( !p->locked || p->wantToLock>0 );
  assert( p->sharable || p->wantToLock==0 );

  /* We should already hold a lock on the database connection */
  assert( sqlite3_mutex_held(p->db->mutex) );

  if( !p->sharable ) return;
  p->wantToLock++;
  if( p->locked ) return;

  /* In most cases, we should be able to acquire the lock we
  ** want without having to go throught the ascending lock

  for(i=0; i<pArray->nMutex; i++){
    Btree *p = pArray->aBtree[i];
    /* Some basic sanity checking */
    assert( i==0 || pArray->aBtree[i-1]->pBt<p->pBt );
    assert( !p->locked || p->wantToLock>0 );

    /* We should already hold a lock on the database connection */
    assert( sqlite3_mutex_held(p->db->mutex) );

    p->wantToLock++;
    if( !p->locked && p->sharable ){
      sqlite3_mutex_enter(p->pBt->mutex);
      p->locked = 1;
    }
  }

    Btree *p = pArray->aBtree[i];
    /* Some basic sanity checking */
    assert( i==0 || pArray->aBtree[i-1]->pBt<p->pBt );
    assert( p->locked || !p->sharable );
    assert( p->wantToLock>0 );

    /* We should already hold a lock on the database connection */
    assert( sqlite3_mutex_held(p->db->mutex) );

    p->wantToLock--;
    if( p->wantToLock==0 && p->locked ){
      sqlite3_mutex_leave(p->pBt->mutex);
      p->locked = 0;
    }
  }
}


#endif  /* SQLITE_THREADSAFE && !SQLITE_OMIT_SHARED_CACHE */

/*
** 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.
**
*************************************************************************
** $Id: btree.c,v 1.432 2007/12/07 18:55:28 drh Exp $
**
** 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"

  ** (BtShared.pLock).
  **
  ** To summarize: If the ReadUncommitted flag is set, then read cursors do
  ** not create or respect table locks. The locking procedure for a 
  ** write-cursor does not change.
  */
  if( 
    !p->db || 
    0==(p->db->flags&SQLITE_ReadUncommitted) || 
    eLock==WRITE_LOCK ||
    iTab==MASTER_ROOT
  ){
    for(pIter=pBt->pLock; pIter; pIter=pIter->pNext){
      if( pIter->pBtree!=p && pIter->iTable==iTab && 
          (pIter->eLock!=eLock || eLock!=READ_LOCK) ){
        return SQLITE_LOCKED;

  /* If the read-uncommitted flag is set and a read-lock is requested,
  ** return early without adding an entry to the BtShared.pLock list. See
  ** comment in function queryTableLock() for more info on handling 
  ** the ReadUncommitted flag.
  */
  if( 
    (p->db) && 
    (p->db->flags&SQLITE_ReadUncommitted) && 
    (eLock==READ_LOCK) &&
    iTable!=MASTER_ROOT
  ){
    return SQLITE_OK;
  }

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

  pPage = (MemPage *)sqlite3PagerGetExtra(pData);
  if( pPage->isInit ){
    assert( sqlite3_mutex_held(pPage->pBt->mutex) );
    pPage->isInit = 0;
    sqlite3BtreeInitPage(pPage, pPage->pParent);
  }
}

/*
** Invoke the busy handler for a btree.
*/
static int sqlite3BtreeInvokeBusyHandler(void *pArg, int n){
  BtShared *pBt = (BtShared*)pArg;
  assert( pBt->db );
  assert( sqlite3_mutex_held(pBt->db->mutex) );
  return sqlite3InvokeBusyHandler(&pBt->db->busyHandler);
}

/*
** Open a database file.
** 
** zFilename is the name of the database file.  If zFilename is NULL
** a new database with a random name is created.  This randomly named
** database file will be deleted when sqlite3BtreeClose() is called.
** If zFilename is ":memory:" then an in-memory database is created
** that is automatically destroyed when it is closed.
*/
int sqlite3BtreeOpen(
  const char *zFilename,  /* Name of the file containing the BTree database */
  sqlite3 *db,            /* Associated database handle */
  Btree **ppBtree,        /* Pointer to new Btree object written here */
  int flags,              /* Options */
  int vfsFlags            /* Flags passed through to sqlite3_vfs.xOpen() */
){
  sqlite3_vfs *pVfs;      /* The VFS to use for this btree */
  BtShared *pBt = 0;      /* Shared part of btree structure */
  Btree *p;               /* Handle to return */

  #ifdef SQLITE_OMIT_MEMORYDB
    const int isMemdb = 0;
  #else
    const int isMemdb = zFilename && !strcmp(zFilename, ":memory:");
  #endif
#endif

  assert( db!=0 );
  assert( sqlite3_mutex_held(db->mutex) );

  pVfs = db->pVfs;
  p = sqlite3MallocZero(sizeof(Btree));
  if( !p ){
    return SQLITE_NOMEM;
  }
  p->inTrans = TRANS_NONE;
  p->db = db;

#if !defined(SQLITE_OMIT_SHARED_CACHE) && !defined(SQLITE_OMIT_DISKIO)
  /*
  ** If this Btree is a candidate for shared cache, try to find an
  ** existing BtShared object that we can share with
  */
  if( (flags & BTREE_PRIVATE)==0
   && isMemdb==0
   && (db->flags & SQLITE_Vtab)==0
   && zFilename && zFilename[0]
  ){
    if( sqlite3SharedCacheEnabled ){
      int nFullPathname = pVfs->mxPathname+1;
      char *zFullPathname = (char *)sqlite3_malloc(nFullPathname);
      sqlite3_mutex *mutexShared;
      p->sharable = 1;
      if( db ){
        db->flags |= SQLITE_SharedCache;
      }
      if( !zFullPathname ){
        sqlite3_free(p);
        return SQLITE_NOMEM;
      }
      sqlite3OsFullPathname(pVfs, zFilename, nFullPathname, zFullPathname);
      mutexShared = sqlite3_mutex_alloc(SQLITE_MUTEX_STATIC_MASTER);

    assert( sizeof(Pgno)==4 );
  
    pBt = sqlite3MallocZero( sizeof(*pBt) );
    if( pBt==0 ){
      rc = SQLITE_NOMEM;
      goto btree_open_out;
    }
    pBt->busyHdr.xFunc = sqlite3BtreeInvokeBusyHandler;
    pBt->busyHdr.pArg = pBt;
    rc = sqlite3PagerOpen(pVfs, &pBt->pPager, zFilename,
                          EXTRA_SIZE, flags, vfsFlags);
    if( rc==SQLITE_OK ){
      rc = sqlite3PagerReadFileheader(pBt->pPager,sizeof(zDbHeader),zDbHeader);
    }
    if( rc!=SQLITE_OK ){
      goto btree_open_out;
    }
    sqlite3PagerSetBusyhandler(pBt->pPager, &pBt->busyHdr);
    p->pBt = pBt;
  
    sqlite3PagerSetDestructor(pBt->pPager, pageDestructor);
    sqlite3PagerSetReiniter(pBt->pPager, pageReinit);
    pBt->pCursor = 0;
    pBt->pPage1 = 0;
    pBt->readOnly = sqlite3PagerIsreadonly(pBt->pPager);

      sqlite3_mutex *mutexShared;
      pBt->nRef = 1;
      mutexShared = sqlite3_mutex_alloc(SQLITE_MUTEX_STATIC_MASTER);
      if( SQLITE_THREADSAFE ){
        pBt->mutex = sqlite3_mutex_alloc(SQLITE_MUTEX_FAST);
        if( pBt->mutex==0 ){
          rc = SQLITE_NOMEM;
          db->mallocFailed = 0;
          goto btree_open_out;
        }
      }
      sqlite3_mutex_enter(mutexShared);
      pBt->pNext = sqlite3SharedCacheList;
      sqlite3SharedCacheList = pBt;
      sqlite3_mutex_leave(mutexShared);
    }
#endif
  }

#if !defined(SQLITE_OMIT_SHARED_CACHE) && !defined(SQLITE_OMIT_DISKIO)
  /* If the new Btree uses a sharable pBtShared, then link the new
  ** Btree into the list of all sharable Btrees for the same connection.
  ** The list is kept in ascending order by pBt address.
  */
  if( p->sharable ){
    int i;
    Btree *pSib;
    for(i=0; i<db->nDb; i++){
      if( (pSib = db->aDb[i].pBt)!=0 && pSib->sharable ){
        while( pSib->pPrev ){ pSib = pSib->pPrev; }
        if( p->pBt<pSib->pBt ){
          p->pNext = pSib;
          p->pPrev = 0;
          pSib->pPrev = p;
        }else{
          while( pSib->pNext && pSib->pNext->pBt<p->pBt ){

** Close an open database and invalidate all cursors.
*/
int sqlite3BtreeClose(Btree *p){
  BtShared *pBt = p->pBt;
  BtCursor *pCur;

  /* Close all cursors opened via this handle.  */
  assert( sqlite3_mutex_held(p->db->mutex) );
  sqlite3BtreeEnter(p);
  pBt->db = p->db;
  pCur = pBt->pCursor;
  while( pCur ){
    BtCursor *pTmp = pCur;
    pCur = pCur->pNext;
    if( pTmp->pBtree==p ){
      sqlite3BtreeCloseCursor(pTmp);
    }

  if( p->pNext ) p->pNext->pPrev = p->pPrev;
#endif

  sqlite3_free(p);
  return SQLITE_OK;
}














/*
** Change the limit on the number of pages allowed in the cache.
**
** The maximum number of cache pages is set to the absolute
** value of mxPage.  If mxPage is negative, the pager will
** operate asynchronously - it will not stop to do fsync()s
** to insure data is written to the disk surface before
** continuing.  Transactions still work if synchronous is off,
** and the database cannot be corrupted if this program
** crashes.  But if the operating system crashes or there is
** an abrupt power failure when synchronous is off, the database
** could be left in an inconsistent and unrecoverable state.
** Synchronous is on by default so database corruption is not
** normally a worry.
*/
int sqlite3BtreeSetCacheSize(Btree *p, int mxPage){
  BtShared *pBt = p->pBt;
  assert( sqlite3_mutex_held(p->db->mutex) );
  sqlite3BtreeEnter(p);
  sqlite3PagerSetCachesize(pBt->pPager, mxPage);
  sqlite3BtreeLeave(p);
  return SQLITE_OK;
}

/*
** Change the way data is synced to disk in order to increase or decrease
** how well the database resists damage due to OS crashes and power
** failures.  Level 1 is the same as asynchronous (no syncs() occur and
** there is a high probability of damage)  Level 2 is the default.  There
** is a very low but non-zero probability of damage.  Level 3 reduces the
** probability of damage to near zero but with a write performance reduction.
*/
#ifndef SQLITE_OMIT_PAGER_PRAGMAS
int sqlite3BtreeSetSafetyLevel(Btree *p, int level, int fullSync){
  BtShared *pBt = p->pBt;
  assert( sqlite3_mutex_held(p->db->mutex) );
  sqlite3BtreeEnter(p);
  sqlite3PagerSetSafetyLevel(pBt->pPager, level, fullSync);
  sqlite3BtreeLeave(p);
  return SQLITE_OK;
}
#endif

/*
** Return TRUE if the given btree is set to safety level 1.  In other
** words, return TRUE if no sync() occurs on the disk files.
*/
int sqlite3BtreeSyncDisabled(Btree *p){
  BtShared *pBt = p->pBt;
  int rc;
  assert( sqlite3_mutex_held(p->db->mutex) );  
  sqlite3BtreeEnter(p);
  assert( pBt && pBt->pPager );
  rc = sqlite3PagerNosync(pBt->pPager);
  sqlite3BtreeLeave(p);
  return rc;
}

** proceed.
*/
int sqlite3BtreeBeginTrans(Btree *p, int wrflag){
  BtShared *pBt = p->pBt;
  int rc = SQLITE_OK;

  sqlite3BtreeEnter(p);
  pBt->db = p->db;
  btreeIntegrity(p);

  /* If the btree is already in a write-transaction, or it
  ** is already in a read-transaction and a read-transaction
  ** is requested, this is a no-op.
  */
  if( p->inTrans==TRANS_WRITE || (p->inTrans==TRANS_READ && !wrflag) ){

  
    if( rc==SQLITE_OK ){
      if( wrflag ) pBt->inStmt = 0;
    }else{
      unlockBtreeIfUnused(pBt);
    }
  }while( rc==SQLITE_BUSY && pBt->inTransaction==TRANS_NONE &&
          sqlite3BtreeInvokeBusyHandler(pBt, 0) );

  if( rc==SQLITE_OK ){
    if( p->inTrans==TRANS_NONE ){
      pBt->nTransaction++;
    }
    p->inTrans = (wrflag?TRANS_WRITE:TRANS_READ);
    if( p->inTrans>pBt->inTransaction ){

** SQLITE_OK is returned. Otherwise an SQLite error code. 
*/
int sqlite3BtreeIncrVacuum(Btree *p){
  int rc;
  BtShared *pBt = p->pBt;

  sqlite3BtreeEnter(p);
  pBt->db = p->db;
  assert( pBt->inTransaction==TRANS_WRITE && p->inTrans==TRANS_WRITE );
  if( !pBt->autoVacuum ){
    rc = SQLITE_DONE;
  }else{
    invalidateAllOverflowCache(pBt);
    rc = incrVacuumStep(pBt, 0);
  }

*/
int sqlite3BtreeCommitPhaseOne(Btree *p, const char *zMaster){
  int rc = SQLITE_OK;
  if( p->inTrans==TRANS_WRITE ){
    BtShared *pBt = p->pBt;
    Pgno nTrunc = 0;
    sqlite3BtreeEnter(p);
    pBt->db = p->db;
#ifndef SQLITE_OMIT_AUTOVACUUM
    if( pBt->autoVacuum ){
      rc = autoVacuumCommit(pBt, &nTrunc); 
      if( rc!=SQLITE_OK ){
        sqlite3BtreeLeave(p);
        return rc;
      }

** This will release the write lock on the database file.  If there
** are no active cursors, it also releases the read lock.
*/
int sqlite3BtreeCommitPhaseTwo(Btree *p){
  BtShared *pBt = p->pBt;

  sqlite3BtreeEnter(p);
  pBt->db = p->db;
  btreeIntegrity(p);

  /* If the handle has a write-transaction open, commit the shared-btrees 
  ** transaction and set the shared state to TRANS_READ.
  */
  if( p->inTrans==TRANS_WRITE ){
    int rc;

*/
int sqlite3BtreeRollback(Btree *p){
  int rc;
  BtShared *pBt = p->pBt;
  MemPage *pPage1;

  sqlite3BtreeEnter(p);
  pBt->db = p->db;
  rc = saveAllCursors(pBt, 0, 0);
#ifndef SQLITE_OMIT_SHARED_CACHE
  if( rc!=SQLITE_OK ){
    /* This is a horrible situation. An IO or malloc() error occured whilst
    ** trying to save cursor positions. If this is an automatic rollback (as
    ** the result of a constraint, malloc() failure or IO error) then 
    ** the cache may be internally inconsistent (not contain valid trees) so

** error occurs within the statement, the effect of that one statement
** can be rolled back without having to rollback the entire transaction.
*/
int sqlite3BtreeBeginStmt(Btree *p){
  int rc;
  BtShared *pBt = p->pBt;
  sqlite3BtreeEnter(p);
  pBt->db = p->db;
  if( (p->inTrans!=TRANS_WRITE) || pBt->inStmt ){
    rc = pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }else{
    assert( pBt->inTransaction==TRANS_WRITE );
    rc = pBt->readOnly ? SQLITE_OK : sqlite3PagerStmtBegin(pBt->pPager);
    pBt->inStmt = 1;
  }
  sqlite3BtreeLeave(p);
  return rc;
}


/*
** Commit the statment subtransaction currently in progress.  If no
** subtransaction is active, this is a no-op.
*/
int sqlite3BtreeCommitStmt(Btree *p){
  int rc;
  BtShared *pBt = p->pBt;
  sqlite3BtreeEnter(p);
  pBt->db = p->db;
  if( pBt->inStmt && !pBt->readOnly ){
    rc = sqlite3PagerStmtCommit(pBt->pPager);
  }else{
    rc = SQLITE_OK;
  }
  pBt->inStmt = 0;
  sqlite3BtreeLeave(p);

** to use a cursor that was open at the beginning of this operation
** will result in an error.
*/
int sqlite3BtreeRollbackStmt(Btree *p){
  int rc = SQLITE_OK;
  BtShared *pBt = p->pBt;
  sqlite3BtreeEnter(p);
  pBt->db = p->db;
  if( pBt->inStmt && !pBt->readOnly ){
    rc = sqlite3PagerStmtRollback(pBt->pPager);
    assert( countWriteCursors(pBt)==0 );
    pBt->inStmt = 0;
  }
  sqlite3BtreeLeave(p);
  return rc;

  int wrFlag,                                 /* 1 to write. 0 read-only */
  int (*xCmp)(void*,int,const void*,int,const void*), /* Key Comparison func */
  void *pArg,                                 /* First arg to xCompare() */
  BtCursor **ppCur                            /* Write new cursor here */
){
  int rc;
  sqlite3BtreeEnter(p);
  p->pBt->db = p->db;
  rc = btreeCursor(p, iTable, wrFlag, xCmp, pArg, ppCur);
  sqlite3BtreeLeave(p);
  return rc;
}


/*
** Close a cursor.  The read lock on the database file is released
** when the last cursor is closed.
*/
int sqlite3BtreeCloseCursor(BtCursor *pCur){
  BtShared *pBt = pCur->pBt;
  Btree *pBtree = pCur->pBtree;

  sqlite3BtreeEnter(pBtree);
  pBt->db = pBtree->db;
  clearCursorPosition(pCur);
  if( pCur->pPrev ){
    pCur->pPrev->pNext = pCur->pNext;
  }else{
    pBt->pCursor = pCur->pNext;
  }
  if( pCur->pNext ){

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

  assert( cursorHoldsMutex(pCur) );
  assert( sqlite3_mutex_held(pCur->pBtree->db->mutex) );
  rc = moveToRoot(pCur);
  if( rc==SQLITE_OK ){
    if( pCur->eState==CURSOR_INVALID ){
      assert( pCur->pPage->nCell==0 );
      *pRes = 1;
      rc = SQLITE_OK;
    }else{

** 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;
 
  assert( cursorHoldsMutex(pCur) );
  assert( sqlite3_mutex_held(pCur->pBtree->db->mutex) );
  rc = moveToRoot(pCur);
  if( rc==SQLITE_OK ){
    if( CURSOR_INVALID==pCur->eState ){
      assert( pCur->pPage->nCell==0 );
      *pRes = 1;
    }else{
      assert( pCur->eState==CURSOR_VALID );

  i64 nKey,              /* Size of pKey.  Or the key for tables */
  int biasRight,         /* If true, bias the search to the high end */
  int *pRes              /* Search result flag */
){
  int rc;

  assert( cursorHoldsMutex(pCur) );
  assert( sqlite3_mutex_held(pCur->pBtree->db->mutex) );
  rc = moveToRoot(pCur);
  if( rc ){
    return rc;
  }
  assert( pCur->pPage );
  assert( pCur->pPage->isInit );
  if( pCur->eState==CURSOR_INVALID ){

  return (CURSOR_VALID!=pCur->eState);
}

/*
** Return the database connection handle for a cursor.
*/
sqlite3 *sqlite3BtreeCursorDb(const BtCursor *pCur){
  assert( sqlite3_mutex_held(pCur->pBtree->db->mutex) );
  return pCur->pBtree->db;
}

/*
** Advance the cursor to the next entry in the database.  If
** successful then set *pRes=0.  If the cursor
** was already pointing to the last entry in the database before
** this routine was called, then set *pRes=1.

** or delete might change the number of cells on a page or delete
** a page entirely and we do not want to leave any cursors 
** pointing to non-existant pages or cells.
*/
static int checkReadLocks(Btree *pBtree, Pgno pgnoRoot, BtCursor *pExclude){
  BtCursor *p;
  BtShared *pBt = pBtree->pBt;
  sqlite3 *db = pBtree->db;
  assert( sqlite3BtreeHoldsMutex(pBtree) );
  for(p=pBt->pCursor; p; p=p->pNext){
    if( p==pExclude ) continue;
    if( p->eState!=CURSOR_VALID ) continue;
    if( p->pgnoRoot!=pgnoRoot ) continue;
    if( p->wrFlag==0 ){
      sqlite3 *dbOther = p->pBtree->db;
      if( dbOther==0 ||
         (dbOther!=db && (dbOther->flags & SQLITE_ReadUncommitted)==0) ){
        return SQLITE_LOCKED;
      }
    }else if( p->pPage->pgno!=p->pgnoRoot ){
      moveToRoot(p);
    }

  sqlite3PagerUnref(pRoot->pDbPage);
  *piTable = (int)pgnoRoot;
  return SQLITE_OK;
}
int sqlite3BtreeCreateTable(Btree *p, int *piTable, int flags){
  int rc;
  sqlite3BtreeEnter(p);
  p->pBt->db = p->db;
  rc = btreeCreateTable(p, piTable, flags);
  sqlite3BtreeLeave(p);
  return rc;
}

/*
** Erase the given database page and all its children.  Return

** read cursors on the table.  Open write cursors are moved to the
** root of the table.
*/
int sqlite3BtreeClearTable(Btree *p, int iTable){
  int rc;
  BtShared *pBt = p->pBt;
  sqlite3BtreeEnter(p);
  pBt->db = p->db;
  if( p->inTrans!=TRANS_WRITE ){
    rc = pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }else if( (rc = checkReadLocks(p, iTable, 0))!=SQLITE_OK ){
    /* nothing to do */
  }else if( SQLITE_OK!=(rc = saveAllCursors(pBt, iTable, 0)) ){
    /* nothing to do */
  }else{

    releasePage(pPage);
  }
  return rc;  
}
int sqlite3BtreeDropTable(Btree *p, int iTable, int *piMoved){
  int rc;
  sqlite3BtreeEnter(p);
  p->pBt->db = p->db;
  rc = btreeDropTable(p, iTable, piMoved);
  sqlite3BtreeLeave(p);
  return rc;
}


/*

int sqlite3BtreeGetMeta(Btree *p, int idx, u32 *pMeta){
  DbPage *pDbPage;
  int rc;
  unsigned char *pP1;
  BtShared *pBt = p->pBt;

  sqlite3BtreeEnter(p);
  pBt->db = p->db;

  /* Reading a meta-data value requires a read-lock on page 1 (and hence
  ** the sqlite_master table. We grab this lock regardless of whether or
  ** not the SQLITE_ReadUncommitted flag is set (the table rooted at page
  ** 1 is treated as a special case by queryTableLock() and lockTable()).
  */
  rc = queryTableLock(p, 1, READ_LOCK);

*/
int sqlite3BtreeUpdateMeta(Btree *p, int idx, u32 iMeta){
  BtShared *pBt = p->pBt;
  unsigned char *pP1;
  int rc;
  assert( idx>=1 && idx<=15 );
  sqlite3BtreeEnter(p);
  pBt->db = p->db;
  if( p->inTrans!=TRANS_WRITE ){
    rc = pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }else{
    assert( pBt->pPage1!=0 );
    pP1 = pBt->pPage1->aData;
    rc = sqlite3PagerWrite(pBt->pPage1->pDbPage);
    if( rc==SQLITE_OK ){

){
  int i;
  int nRef;
  IntegrityCk sCheck;
  BtShared *pBt = p->pBt;

  sqlite3BtreeEnter(p);
  pBt->db = p->db;
  nRef = sqlite3PagerRefcount(pBt->pPager);
  if( lockBtreeWithRetry(p)!=SQLITE_OK ){
    sqlite3BtreeLeave(p);
    return sqlite3StrDup("Unable to acquire a read lock on the database");
  }
  sCheck.pBt = pBt;
  sCheck.pPager = pBt->pPager;

    return 0;
  }
  sCheck.anRef = sqlite3_malloc( (sCheck.nPage+1)*sizeof(sCheck.anRef[0]) );
  if( !sCheck.anRef ){
    unlockBtreeIfUnused(pBt);
    *pnErr = 1;
    sqlite3BtreeLeave(p);
    return sqlite3MPrintf(p->db, "Unable to malloc %d bytes", 
        (sCheck.nPage+1)*sizeof(sCheck.anRef[0]));
  }
  for(i=0; i<=sCheck.nPage; i++){ sCheck.anRef[i] = 0; }
  i = PENDING_BYTE_PAGE(pBt);
  if( i<=sCheck.nPage ){
    sCheck.anRef[i] = 1;
  }

*/
static int btreeCopyFile(Btree *pTo, Btree *pFrom){
  int rc = SQLITE_OK;
  Pgno i, nPage, nToPage, iSkip;

  BtShared *pBtTo = pTo->pBt;
  BtShared *pBtFrom = pFrom->pBt;
  pBtTo->db = pTo->db;
  pBtFrom->db = pFrom->db;
  

  if( pTo->inTrans!=TRANS_WRITE || pFrom->inTrans!=TRANS_WRITE ){
    return SQLITE_ERROR;
  }
  if( pBtTo->pCursor ) return SQLITE_BUSY;
  nToPage = sqlite3PagerPagecount(pBtTo->pPager);
  nPage = sqlite3PagerPagecount(pBtFrom->pPager);

#endif /* SQLITE_OMIT_VACUUM */

/*
** Return non-zero if a transaction is active.
*/
int sqlite3BtreeIsInTrans(Btree *p){
  assert( p==0 || sqlite3_mutex_held(p->db->mutex) );
  return (p && (p->inTrans==TRANS_WRITE));
}

/*
** Return non-zero if a statement transaction is active.
*/
int sqlite3BtreeIsInStmt(Btree *p){
  assert( sqlite3BtreeHoldsMutex(p) );
  return (p->pBt && p->pBt->inStmt);
}

/*
** Return non-zero if a read (or write) transaction is active.
*/
int sqlite3BtreeIsInReadTrans(Btree *p){
  assert( sqlite3_mutex_held(p->db->mutex) );
  return (p && (p->inTrans!=TRANS_NONE));
}

/*
** This function returns a pointer to a blob of memory associated with
** a single shared-btree. The memory is used by client code for it's own
** purposes (for example, to store a high-level schema associated with 

/*
** Return true if another user of the same shared btree as the argument
** handle holds an exclusive lock on the sqlite_master table.
*/
int sqlite3BtreeSchemaLocked(Btree *p){
  int rc;
  assert( sqlite3_mutex_held(p->db->mutex) );
  sqlite3BtreeEnter(p);
  rc = (queryTableLock(p, MASTER_ROOT, READ_LOCK)!=SQLITE_OK);
  sqlite3BtreeLeave(p);
  return rc;
}

** INTKEY table currently pointing at a valid table entry. 
** This function modifies the data stored as part of that entry.
** Only the data content may only be modified, it is not possible
** to change the length of the data stored.
*/
int sqlite3BtreePutData(BtCursor *pCsr, u32 offset, u32 amt, void *z){
  assert( cursorHoldsMutex(pCsr) );
  assert( sqlite3_mutex_held(pCsr->pBtree->db->mutex) );
  assert(pCsr->isIncrblobHandle);
  if( pCsr->eState>=CURSOR_REQUIRESEEK ){
    if( pCsr->eState==CURSOR_FAULT ){
      return pCsr->skip;
    }else{
      return SQLITE_ABORT;
    }

** This function sets a flag only. The actual page location cache
** (stored in BtCursor.aOverflow[]) is allocated and used by function
** accessPayload() (the worker function for sqlite3BtreeData() and
** sqlite3BtreePutData()).
*/
void sqlite3BtreeCacheOverflow(BtCursor *pCur){
  assert( cursorHoldsMutex(pCur) );
  assert( sqlite3_mutex_held(pCur->pBtree->db->mutex) );
  assert(!pCur->isIncrblobHandle);
  assert(!pCur->aOverflow);
  pCur->isIncrblobHandle = 1;
}
#endif

**    May you share freely, never taking more than you give.
**
*************************************************************************
** 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.94 2007/12/07 18:55:28 drh Exp $
*/
#ifndef _BTREE_H_
#define _BTREE_H_

/* TODO: This definition is just included so other modules compile. It
** needs to be revisited.
*/

/* Additional values for the 4th argument of sqlite3BtreeOpen that
** are not associated with PAGER_ values.
*/
#define BTREE_PRIVATE      64  /* Never share with other connections */

int sqlite3BtreeClose(Btree*);

int sqlite3BtreeSetCacheSize(Btree*,int);
int sqlite3BtreeSetSafetyLevel(Btree*,int,int);
int sqlite3BtreeSyncDisabled(Btree*);
int sqlite3BtreeSetPageSize(Btree*,int,int);
int sqlite3BtreeGetPageSize(Btree*);
int sqlite3BtreeMaxPageCount(Btree*,int);
int sqlite3BtreeGetReserve(Btree*);

/*
** 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.
**
*************************************************************************
** $Id: btreeInt.h,v 1.14 2007/12/07 18:55:28 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:
**     "Sorting And Searching", pages 473-480. Addison-Wesley
**     Publishing Company, Reading, Massachusetts.

** All fields in this structure are accessed under sqlite3.mutex.
** The pBt pointer itself may not be changed while there exists cursors 
** in the referenced BtShared that point back to this Btree since those
** cursors have to do go through this Btree to find their BtShared and
** they often do so without holding sqlite3.mutex.
*/
struct Btree {
  sqlite3 *db;       /* The database connection holding this btree */
  BtShared *pBt;     /* Sharable content of this btree */
  u8 inTrans;        /* TRANS_NONE, TRANS_READ or TRANS_WRITE */
  u8 sharable;       /* True if we can share pBt with another db */
  u8 locked;         /* True if db currently has pBt locked */
  int wantToLock;    /* Number of nested calls to sqlite3BtreeEnter() */
  Btree *pNext;      /* List of other sharable Btrees from the same db */
  Btree *pPrev;      /* Back pointer of the same list */
};

/*
** Btree.inTrans may take one of the following values.
**
** If the shared-data extension is enabled, there may be multiple users

** global SQLITE_MUTEX_STATIC_MASTER mutex.  The pPager field
** may not be modified once it is initially set as long as nRef>0.
** The pSchema field may be set once under BtShared.mutex and
** thereafter is unchanged as long as nRef>0.
*/
struct BtShared {
  Pager *pPager;        /* The page cache */
  sqlite3 *db;          /* Database connection currently using this Btree */
  BtCursor *pCursor;    /* A list of all open cursors */
  MemPage *pPage1;      /* First page of the database */
  u8 inStmt;            /* True if we are in a statement subtransaction */
  u8 readOnly;          /* True if the underlying file is readonly */
  u8 maxEmbedFrac;      /* Maximum payload as % of total page size */
  u8 minEmbedFrac;      /* Minimum payload as % of total page size */
  u8 minLeafFrac;       /* Minimum leaf payload as % of total page size */
  u8 pageSizeFixed;     /* True if the page size can no longer be changed */
#ifndef SQLITE_OMIT_AUTOVACUUM
  u8 autoVacuum;        /* True if auto-vacuum is enabled */
  u8 incrVacuum;        /* True if incr-vacuum is enabled */
  Pgno nTrunc;          /* Non-zero if the db will be truncated (incr vacuum) */
#endif
  u16 pageSize;         /* Total number of bytes on a page */
  u16 usableSize;       /* Number of usable bytes on each page */
  int maxLocal;         /* Maximum local payload in non-LEAFDATA tables */
  int minLocal;         /* Minimum local payload in non-LEAFDATA tables */
  int maxLeaf;          /* Maximum local payload in a LEAFDATA table */
  int minLeaf;          /* Minimum local payload in a LEAFDATA table */

  u8 inTransaction;     /* Transaction state */
  int nTransaction;     /* Number of open transactions (read + write) */
  void *pSchema;        /* Pointer to space allocated by sqlite3BtreeSchema() */
  void (*xFreeSchema)(void*);  /* Destructor for BtShared.pSchema */
  sqlite3_mutex *mutex; /* Non-recursive mutex required to access this struct */
  BusyHandler busyHdr;  /* The busy handler for this btree */
#ifndef SQLITE_OMIT_SHARED_CACHE
  int nRef;             /* Number of references to this structure */
  BtShared *pNext;      /* Next on a list of sharable BtShared structs */
  BtLock *pLock;        /* List of locks held on this shared-btree struct */
#endif
};

** b-tree within a database file.
**
** The entry is identified by its MemPage and the index in
** MemPage.aCell[] of the entry.
**
** When a single database file can shared by two more database connections,
** but cursors cannot be shared.  Each cursor is associated with a
** particular database connection identified BtCursor.pBtree.db.
**
** Fields in this structure are accessed under the BtShared.mutex
** found at self->pBt->mutex. 
*/
struct BtCursor {
  Btree *pBtree;            /* The Btree to which this cursor belongs */
  BtShared *pBt;            /* The BtShared this cursor points to */

**
*************************************************************************
** Main file for the SQLite library.  The routines in this file
** implement the programmer interface to the library.  Routines in
** other files are for internal use by SQLite and should not be
** accessed by users of the library.
**
** $Id: main.c,v 1.409 2007/12/07 18:55:28 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

/*
** The version of the library
*/

  }

  if( (vfsFlags & SQLITE_OPEN_MAIN_DB)!=0 && (zFilename==0 || *zFilename==0) ){
    vfsFlags = (vfsFlags & ~SQLITE_OPEN_MAIN_DB) | SQLITE_OPEN_TEMP_DB;
  }
  rc = sqlite3BtreeOpen(zFilename, (sqlite3 *)db, ppBtree, btFlags, vfsFlags);
  if( rc==SQLITE_OK ){

    sqlite3BtreeSetCacheSize(*ppBtree, nCache);
  }
  return rc;
}

/*
** Return UTF-8 encoded English language explanation of the most recent

** The pager is used to access a database disk file.  It implements
** atomic commit and rollback through the use of a journal file that
** is separate from the database file.  The pager also implements file
** locking to prevent two processes from writing the same database
** file simultaneously, or one process from reading the database while
** another is writing.
**
** @(#) $Id: pager.c,v 1.398 2007/12/07 18:55:28 drh Exp $
*/
#ifndef SQLITE_OMIT_DISKIO
#include "sqliteInt.h"
#include <assert.h>
#include <string.h>

/*

** been released, the function returns. The return value is the total number 
** of bytes of memory released.
*/
int sqlite3PagerReleaseMemory(int nReq){
  int nReleased = 0;          /* Bytes of memory released so far */
  sqlite3_mutex *mutex;       /* The MEM2 mutex */
  Pager *pPager;              /* For looping over pagers */
  BusyHandler *savedBusy;     /* Saved copy of the busy handler */
  int rc = SQLITE_OK;

  /* Acquire the memory-management mutex
  */
  mutex = sqlite3_mutex_alloc(SQLITE_MUTEX_STATIC_MEM2);
  sqlite3_mutex_enter(mutex);

    */
    if( !pPg ) break;

    pPager = pPg->pPager;
    assert(!pPg->needSync || pPg==pPager->lru.pFirst);
    assert(pPg->needSync || pPg==pPager->lru.pFirstSynced);
  
    savedBusy = pPager->pBusyHandler;
    pPager->pBusyHandler = 0;
    rc = pager_recycle(pPager, &pRecycled);
    pPager->pBusyHandler = savedBusy;
    assert(pRecycled==pPg || rc!=SQLITE_OK);
    if( rc==SQLITE_OK ){
      /* We've found a page to free. At this point the page has been 
      ** removed from the page hash-table, free-list and synced-list 
      ** (pFirstSynced). It is still in the all pages (pAll) list. 
      ** Remove it from this list before freeing.
      **

/*
** 2001 September 15
**
** 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.
**
*************************************************************************
** Internal interface definitions for SQLite.
**
** @(#) $Id: sqliteInt.h,v 1.624 2007/12/07 18:55:29 drh Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_

/*
** The macro unlikely() is a hint that surrounds a boolean
** expression that is usually false.  Macro likely() surrounds

** builds) or a function call (for debugging).  If it is a function call,
** it allows the operator to set a breakpoint at the spot where database
** corruption is first detected.
*/
#ifdef SQLITE_DEBUG
  int sqlite3Corrupt(void);
# define SQLITE_CORRUPT_BKPT sqlite3Corrupt()
# define DEBUGONLY(X)        X
#else
# define SQLITE_CORRUPT_BKPT SQLITE_CORRUPT
# define DEBUGONLY(X)
#endif

/*
** Internal function prototypes
*/
int sqlite3StrICmp(const char *, const char *);
int sqlite3StrNICmp(const char *, const char *, int);

**    May you share freely, never taking more than you give.
**
*************************************************************************
** 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.88 2007/12/07 18:55:29 drh Exp $
*/
#include "sqliteInt.h"
#include "btreeInt.h"
#include "tcl.h"
#include <stdlib.h>
#include <string.h>

  /* Normally in this file, with a b-tree handle opened using the 
  ** [btree_open] command it is safe to call sqlite3BtreeEnter() directly.
  ** But this function is sometimes called with a btree handle obtained
  ** from an open SQLite connection (using [btree_from_db]). In this case
  ** we need to obtain the mutex for the controlling SQLite handle before
  ** it is safe to call sqlite3BtreeEnter().
  */
  sqlite3_mutex_enter(pBt->db->mutex);

  sqlite3BtreeEnter(pBt);
  a = sqlite3PagerStats(sqlite3BtreePager(pBt));
  for(i=0; i<11; i++){
    static char *zName[] = {
      "ref", "page", "max", "size", "state", "err",
      "hit", "miss", "ovfl", "read", "write"
    };
    char zBuf[100];
    Tcl_AppendElement(interp, zName[i]);
    sqlite3_snprintf(sizeof(zBuf), zBuf,"%d",a[i]);
    Tcl_AppendElement(interp, zBuf);
  }
  sqlite3BtreeLeave(pBt);

  /* Release the mutex on the SQLite handle that controls this b-tree */
  sqlite3_mutex_leave(pBt->db->mutex);
  return TCL_OK;
}

/*
** Usage:   btree_pager_ref_dump ID
**
** Print out all outstanding pages.

    Tcl_AppendResult(interp, "wrong # args: should be \"", argv[0],
       " BT NCACHE\"", 0);
    return TCL_ERROR;
  }
  pBt = sqlite3TextToPtr(argv[1]);
  if( Tcl_GetInt(interp, argv[2], &nCache) ) return TCL_ERROR;

  sqlite3_mutex_enter(pBt->db->mutex);
  sqlite3BtreeEnter(pBt);
  sqlite3BtreeSetCacheSize(pBt, nCache);
  sqlite3BtreeLeave(pBt);
  sqlite3_mutex_leave(pBt->db->mutex);

  return TCL_OK;
}


/*
** Register commands with the TCL interpreter.