** 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.276 2005/12/21 18:36:46 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.
................................................................................
** assumes a minimum cell size of 3 bytes.  Such small cells will be
** exceedingly rare, but they are possible.
*/
#define MX_CELL(pBt) ((pBt->pageSize-8)/3)

/* Forward declarations */
typedef struct MemPage MemPage;


/*
** This is a magic string that appears at the beginning of every
** SQLite database in order to identify the file as a real database.
**
** You can change this value at compile-time by specifying a
** -DSQLITE_FILE_HEADER="..." on the compiler command-line.  The
................................................................................
  u16 maxLocal;        /* Copy of Btree.maxLocal or Btree.maxLeaf */
  u16 minLocal;        /* Copy of Btree.minLocal or Btree.minLeaf */
  u16 cellOffset;      /* Index in aData of first cell pointer */
  u16 idxParent;       /* Index in parent of this node */
  u16 nFree;           /* Number of free bytes on the page */
  u16 nCell;           /* Number of cells on this page, local and ovfl */
  struct _OvflCell {   /* Cells that will not fit on aData[] */
    u8 *pCell;           /* Pointers to the body of the overflow cell */
    u16 idx;             /* Insert this cell before idx-th non-overflow cell */
  } aOvfl[5];
  struct Btree *pBt;   /* Pointer back to BTree structure */
  u8 *aData;           /* Pointer back to the start of the page */
  Pgno pgno;           /* Page number for this page */
  MemPage *pParent;    /* The parent of this page.  NULL for root */
};

/*
** The in-memory image of a disk page has the auxiliary information appended
** to the end.  EXTRA_SIZE is the number of bytes of space needed to hold
** that extra information.
*/
#define EXTRA_SIZE sizeof(MemPage)




















/*
** Everything we need to know about an open database
*/
struct Btree {
  Pager *pPager;        /* The page cache */
  BtCursor *pCursor;    /* A list of all open cursors */
  MemPage *pPage1;      /* First page of the database */
  u8 inTrans;           /* True if a transaction is in progress */
  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
................................................................................
  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 */
  BusyHandler *pBusyHandler;   /* Callback for when there is lock contention */





};
typedef Btree Bt;

/*
** Btree.inTrans may take one of the following values.
*/
#define TRANS_NONE  0
#define TRANS_READ  1
#define TRANS_WRITE 2

/*
** An instance of the following structure is used to hold information
** about a cell.  The parseCellPtr() function fills in this structure
** based on information extract from the raw disk page.
*/
typedef struct CellInfo CellInfo;
................................................................................

/*
** A cursor is a pointer to a particular entry in the BTree.
** The entry is identified by its MemPage and the index in
** MemPage.aCell[] of the entry.
*/
struct BtCursor {
  Btree *pBt;               /* The Btree to which this cursor belongs */
  BtCursor *pNext, *pPrev;  /* Forms a linked list of all cursors */
  int (*xCompare)(void*,int,const void*,int,const void*); /* Key comp func */
  void *pArg;               /* First arg to xCompare() */
  Pgno pgnoRoot;            /* The root page of this tree */
  MemPage *pPage;           /* Page that contains the entry */
  int idx;                  /* Index of the entry in pPage->aCell[] */
  CellInfo info;            /* A parse of the cell we are pointing at */
................................................................................
# define TRACE(X)
#endif
int sqlite3_btree_trace=0;  /* True to enable tracing */

/*
** Forward declaration
*/
static int checkReadLocks(Btree*,Pgno,BtCursor*);

/*
** Read or write a two- and four-byte big-endian integer values.
*/
static u32 get2byte(unsigned char *p){
  return (p[0]<<8) | p[1];
}
................................................................................

/* The database page the PENDING_BYTE occupies. This page is never used.
** TODO: This macro is very similary to PAGER_MJ_PGNO() in pager.c. They
** should possibly be consolidated (presumably in pager.h).
*/
#define PENDING_BYTE_PAGE(pBt) ((PENDING_BYTE/(pBt)->pageSize)+1)





















































































































#ifndef SQLITE_OMIT_AUTOVACUUM
/*
** These macros define the location of the pointer-map entry for a 
** database page. The first argument to each is the number of usable
** bytes on each page of the database (often 1024). The second is the
** page number to look up in the pointer map.
**
................................................................................
/*
** 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'.
** An error code is returned if something goes wrong, otherwise SQLITE_OK.
*/
static int ptrmapPut(Btree *pBt, Pgno key, u8 eType, Pgno parent){
  u8 *pPtrmap;    /* The pointer map page */
  Pgno iPtrmap;   /* The pointer map page number */
  int offset;     /* Offset in pointer map page */
  int rc;

  assert( pBt->autoVacuum );
  if( key==0 ){
................................................................................
/*
** 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(Btree *pBt, Pgno key, u8 *pEType, Pgno *pPgno){
  int iPtrmap;       /* Pointer map page index */
  u8 *pPtrmap;       /* Pointer map page data */
  int offset;        /* Offset of entry in pointer map */
  int rc;

  iPtrmap = PTRMAP_PAGENO(pBt->usableSize, key);
  rc = sqlite3pager_get(pBt->pPager, iPtrmap, (void **)&pPtrmap);
................................................................................
  sqlite3pager_unref(pPtrmap);
  if( *pEType<1 || *pEType>5 ) return SQLITE_CORRUPT_BKPT;
  return SQLITE_OK;
}

#endif /* SQLITE_OMIT_AUTOVACUUM */






















/*
** 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.
*/
................................................................................
  sqliteFree(used);
}
#define pageIntegrity(X) _pageIntegrity(X)
#else
# define pageIntegrity(X)
#endif










/*
** Defragment the page given.  All Cells are moved to the
** end of the page and all free space is collected into one
** big FreeBlk that occurs in between the header and cell
** pointer array and the cell content area.
*/
static int defragmentPage(MemPage *pPage){
................................................................................
}

/*
** Decode the flags byte (the first byte of the header) for a page
** and initialize fields of the MemPage structure accordingly.
*/
static void decodeFlags(MemPage *pPage, int flagByte){
  Btree *pBt;     /* A copy of pPage->pBt */

  assert( pPage->hdrOffset==(pPage->pgno==1 ? 100 : 0) );
  pPage->intKey = (flagByte & (PTF_INTKEY|PTF_LEAFDATA))!=0;
  pPage->zeroData = (flagByte & PTF_ZERODATA)!=0;
  pPage->leaf = (flagByte & PTF_LEAF)!=0;
  pPage->childPtrSize = 4*(pPage->leaf==0);
  pBt = pPage->pBt;
................................................................................
static int initPage(
  MemPage *pPage,        /* The page to be initialized */
  MemPage *pParent       /* The parent.  Might be NULL */
){
  int pc;            /* Address of a freeblock within pPage->aData[] */
  int hdr;           /* Offset to beginning of page header */
  u8 *data;          /* Equal to pPage->aData */
  Btree *pBt;        /* The main btree structure */
  int usableSize;    /* Amount of usable space on each page */
  int cellOffset;    /* Offset from start of page to first cell pointer */
  int nFree;         /* Number of unused bytes on the page */
  int top;           /* First byte of the cell content area */

  pBt = pPage->pBt;
  assert( pBt!=0 );
................................................................................

/*
** Set up a raw page so that it looks like a database page holding
** no entries.
*/
static void zeroPage(MemPage *pPage, int flags){
  unsigned char *data = pPage->aData;
  Btree *pBt = pPage->pBt;
  int hdr = pPage->hdrOffset;
  int first;

  assert( sqlite3pager_pagenumber(data)==pPage->pgno );
  assert( &data[pBt->pageSize] == (unsigned char*)pPage );
  assert( sqlite3pager_iswriteable(data) );
  memset(&data[hdr], 0, pBt->usableSize - hdr);
................................................................................
  pageIntegrity(pPage);
}

/*
** Get a page from the pager.  Initialize the MemPage.pBt and
** MemPage.aData elements if needed.
*/
static int getPage(Btree *pBt, Pgno pgno, MemPage **ppPage){
  int rc;
  unsigned char *aData;
  MemPage *pPage;
  rc = sqlite3pager_get(pBt->pPager, pgno, (void**)&aData);
  if( rc ) return rc;
  pPage = (MemPage*)&aData[pBt->pageSize];
  pPage->aData = aData;
................................................................................

/*
** Get a page from the pager and initialize it.  This routine
** is just a convenience wrapper around separate calls to
** getPage() and initPage().
*/
static int getAndInitPage(
  Btree *pBt,          /* The database file */
  Pgno pgno,           /* Number of the page to get */
  MemPage **ppPage,    /* Write the page pointer here */
  MemPage *pParent     /* Parent of the page */
){
  int rc;
  if( pgno==0 ){
    return SQLITE_CORRUPT_BKPT; 
................................................................................
** 
** 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.
*/
int sqlite3BtreeOpen(
  const char *zFilename,  /* Name of the file containing the BTree database */

  Btree **ppBtree,        /* Pointer to new Btree object written here */
  int flags               /* Options */
){
  Btree *pBt;

  int rc;
  int nReserve;
  unsigned char zDbHeader[100];











































  /*
  ** The following asserts make sure that structures used by the btree are
  ** the right size.  This is to guard against size changes that result
  ** when compiling on a different architecture.
  */
  assert( sizeof(i64)==8 );
................................................................................
  assert( sizeof(u32)==4 );
  assert( sizeof(u16)==2 );
  assert( sizeof(Pgno)==4 );

  pBt = sqliteMalloc( sizeof(*pBt) );
  if( pBt==0 ){
    *ppBtree = 0;

    return SQLITE_NOMEM;
  }
  rc = sqlite3pager_open(&pBt->pPager, zFilename, EXTRA_SIZE, flags);
  if( rc!=SQLITE_OK ){
    if( pBt->pPager ) sqlite3pager_close(pBt->pPager);
    sqliteFree(pBt);

    *ppBtree = 0;
    return rc;
  }


  sqlite3pager_set_destructor(pBt->pPager, pageDestructor);
  sqlite3pager_set_reiniter(pBt->pPager, pageReinit);
  pBt->pCursor = 0;
  pBt->pPage1 = 0;
  pBt->readOnly = sqlite3pager_isreadonly(pBt->pPager);
  sqlite3pager_read_fileheader(pBt->pPager, sizeof(zDbHeader), zDbHeader);
  pBt->pageSize = get2byte(&zDbHeader[16]);
................................................................................
#ifndef SQLITE_OMIT_AUTOVACUUM
    /* If the magic name ":memory:" will create an in-memory database, then
    ** do not set the auto-vacuum flag, even if SQLITE_DEFAULT_AUTOVACUUM
    ** is true. On the other hand, if SQLITE_OMIT_MEMORYDB has been defined,
    ** then ":memory:" is just a regular file-name. Respect the auto-vacuum
    ** default in this case.
    */
#ifndef SQLITE_OMIT_MEMORYDB
    if( zFilename && strcmp(zFilename,":memory:") ){
#else
    if( zFilename ){
#endif
      pBt->autoVacuum = SQLITE_DEFAULT_AUTOVACUUM;
    }
#endif
    nReserve = 0;
  }else{
    nReserve = zDbHeader[20];
    pBt->maxEmbedFrac = zDbHeader[21];
................................................................................
#ifndef SQLITE_OMIT_AUTOVACUUM
    pBt->autoVacuum = (get4byte(&zDbHeader[36 + 4*4])?1:0);
#endif
  }
  pBt->usableSize = pBt->pageSize - nReserve;
  assert( (pBt->pageSize & 7)==0 );  /* 8-byte alignment of pageSize */
  sqlite3pager_set_pagesize(pBt->pPager, pBt->pageSize);









  *ppBtree = pBt;
  return SQLITE_OK;
}

/*
** Close an open database and invalidate all cursors.
*/
int sqlite3BtreeClose(Btree *pBt){








  while( pBt->pCursor ){




    sqlite3BtreeCloseCursor(pBt->pCursor);
  }





























  sqlite3pager_close(pBt->pPager);
  sqliteFree(pBt);
  return SQLITE_OK;
}

/*
** Change the busy handler callback function.
*/
int sqlite3BtreeSetBusyHandler(Btree *pBt, BusyHandler *pHandler){

  pBt->pBusyHandler = pHandler;
  sqlite3pager_set_busyhandler(pBt->pPager, pHandler);
  return SQLITE_OK;
}

/*
** Change the limit on the number of pages allowed in the cache.
................................................................................
** 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 *pBt, int mxPage){

  sqlite3pager_set_cachesize(pBt->pPager, mxPage);
  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 *pBt, int level){

  sqlite3pager_set_safety_level(pBt->pPager, level);
  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 *pBt){

  assert( pBt && pBt->pPager );
  return sqlite3pager_nosync(pBt->pPager);
}

#if !defined(SQLITE_OMIT_PAGER_PRAGMAS) || !defined(SQLITE_OMIT_VACUUM)
/*
** Change the default pages size and the number of reserved bytes per page.
................................................................................
** of the database file used for locking (beginning at PENDING_BYTE,
** the first byte past the 1GB boundary, 0x40000000) needs to occur
** at the beginning of a page.
**
** If parameter nReserve is less than zero, then the number of reserved
** bytes per page is left unchanged.
*/
int sqlite3BtreeSetPageSize(Btree *pBt, int pageSize, int nReserve){

  if( pBt->pageSizeFixed ){
    return SQLITE_READONLY;
  }
  if( nReserve<0 ){
    nReserve = pBt->pageSize - pBt->usableSize;
  }
  if( pageSize>=512 && pageSize<=SQLITE_MAX_PAGE_SIZE &&
        ((pageSize-1)&pageSize)==0 ){
    assert( (pageSize & 7)==0 );

    pBt->pageSize = sqlite3pager_set_pagesize(pBt->pPager, pageSize);
  }
  pBt->usableSize = pBt->pageSize - nReserve;
  return SQLITE_OK;
}

/*
** Return the currently defined page size
*/
int sqlite3BtreeGetPageSize(Btree *pBt){
  return pBt->pageSize;
}
int sqlite3BtreeGetReserve(Btree *pBt){
  return pBt->pageSize - pBt->usableSize;
}
#endif /* !defined(SQLITE_OMIT_PAGER_PRAGMAS) || !defined(SQLITE_OMIT_VACUUM) */

/*
** Change the 'auto-vacuum' property of the database. If the 'autoVacuum'
** parameter is non-zero, then auto-vacuum mode is enabled. If zero, it
** is disabled. The default value for the auto-vacuum property is 
** determined by the SQLITE_DEFAULT_AUTOVACUUM macro.
*/
int sqlite3BtreeSetAutoVacuum(Btree *pBt, int autoVacuum){

#ifdef SQLITE_OMIT_AUTOVACUUM
  return SQLITE_READONLY;
#else
  if( pBt->pageSizeFixed ){
    return SQLITE_READONLY;
  }
  pBt->autoVacuum = (autoVacuum?1:0);
................................................................................
#endif
}

/*
** Return the value of the 'auto-vacuum' property. If auto-vacuum is 
** enabled 1 is returned. Otherwise 0.
*/
int sqlite3BtreeGetAutoVacuum(Btree *pBt){
#ifdef SQLITE_OMIT_AUTOVACUUM
  return 0;
#else
  return pBt->autoVacuum;
#endif
}


/*
** Get a reference to pPage1 of the database file.  This will
** also acquire a readlock on that file.
................................................................................
**
** SQLITE_OK is returned on success.  If the file is not a
** well-formed database file, then SQLITE_CORRUPT is returned.
** SQLITE_BUSY is returned if the database is locked.  SQLITE_NOMEM
** is returned if we run out of memory.  SQLITE_PROTOCOL is returned
** if there is a locking protocol violation.
*/
static int lockBtree(Btree *pBt){
  int rc, pageSize;
  MemPage *pPage1;
  if( pBt->pPage1 ) return SQLITE_OK;
  rc = getPage(pBt, 1, &pPage1);
  if( rc!=SQLITE_OK ) return rc;
  

................................................................................
  return rc;
}

/*
** This routine works like lockBtree() except that it also invokes the
** busy callback if there is lock contention.
*/
static int lockBtreeWithRetry(Btree *pBt){
  int rc = SQLITE_OK;
  if( pBt->inTrans==TRANS_NONE ){


    rc = sqlite3BtreeBeginTrans(pBt, 0);

    pBt->inTrans = TRANS_NONE;




  }
  return rc;
}
       

/*
** If there are no outstanding cursors and we are not in the middle
................................................................................
** this routine unrefs the first page of the database file which 
** has the effect of releasing the read lock.
**
** If there are any outstanding cursors, this routine is a no-op.
**
** If there is a transaction in progress, this routine is a no-op.
*/
static void unlockBtreeIfUnused(Btree *pBt){
  if( pBt->inTrans==TRANS_NONE && pBt->pCursor==0 && pBt->pPage1!=0 ){
    if( pBt->pPage1->aData==0 ){
      MemPage *pPage = pBt->pPage1;
      pPage->aData = &((u8*)pPage)[-pBt->pageSize];
      pPage->pBt = pBt;
      pPage->pgno = 1;
    }
    releasePage(pBt->pPage1);
................................................................................
  }
}

/*
** Create a new database by initializing the first page of the
** file.
*/
static int newDatabase(Btree *pBt){
  MemPage *pP1;
  unsigned char *data;
  int rc;
  if( sqlite3pager_pagecount(pBt->pPager)>0 ) return SQLITE_OK;
  pP1 = pBt->pPage1;
  assert( pP1!=0 );
  data = pP1->aData;
................................................................................
** a reserved lock.  B tries to promote to exclusive but is blocked because
** of A's read lock.  A tries to promote to reserved but is blocked by B.
** One or the other of the two processes must give way or there can be
** no progress.  By returning SQLITE_BUSY and not invoking the busy callback
** when A already has a read lock, we encourage A to give up and let B
** proceed.
*/
int sqlite3BtreeBeginTrans(Btree *pBt, int wrflag){

  int rc = SQLITE_OK;



  /* 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( pBt->inTrans==TRANS_WRITE || (pBt->inTrans==TRANS_READ && !wrflag) ){
    return SQLITE_OK;
  }

  /* Write transactions are not possible on a read-only database */
  if( pBt->readOnly && wrflag ){
    return SQLITE_READONLY;
  }









  do {
    if( pBt->pPage1==0 ){
      rc = lockBtree(pBt);
    }
  
    if( rc==SQLITE_OK && wrflag ){
................................................................................
      rc = sqlite3pager_begin(pBt->pPage1->aData, wrflag>1);
      if( rc==SQLITE_OK ){
        rc = newDatabase(pBt);
      }
    }
  
    if( rc==SQLITE_OK ){
      pBt->inTrans = (wrflag?TRANS_WRITE:TRANS_READ);
      if( wrflag ) pBt->inStmt = 0;
    }else{
      unlockBtreeIfUnused(pBt);
    }
  }while( rc==SQLITE_BUSY && pBt->inTrans==TRANS_NONE &&
          sqlite3InvokeBusyHandler(pBt->pBusyHandler) );












  return rc;
}

#ifndef SQLITE_OMIT_AUTOVACUUM

/*
** Set the pointer-map entries for all children of page pPage. Also, if
................................................................................
** pPage contains cells that point to overflow pages, set the pointer
** map entries for the overflow pages as well.
*/
static int setChildPtrmaps(MemPage *pPage){
  int i;                             /* Counter variable */
  int nCell;                         /* Number of cells in page pPage */
  int rc = SQLITE_OK;                /* Return code */
  Btree *pBt = pPage->pBt;
  int isInitOrig = pPage->isInit;
  Pgno pgno = pPage->pgno;

  initPage(pPage, 0);
  nCell = pPage->nCell;

  for(i=0; i<nCell; i++){
................................................................................


/*
** Move the open database page pDbPage to location iFreePage in the 
** database. The pDbPage reference remains valid.
*/
static int relocatePage(
  Btree *pBt,              /* Btree */
  MemPage *pDbPage,        /* Open page to move */
  u8 eType,                /* Pointer map 'type' entry for pDbPage */
  Pgno iPtrPage,           /* Pointer map 'page-no' entry for pDbPage */
  Pgno iFreePage           /* The location to move pDbPage to */
){
  MemPage *pPtrPage;   /* The page that contains a pointer to pDbPage */
  Pgno iDbPage = pDbPage->pgno;
................................................................................
      rc = ptrmapPut(pBt, iFreePage, eType, iPtrPage);
    }
  }
  return rc;
}

/* Forward declaration required by autoVacuumCommit(). */
static int allocatePage(Btree *, MemPage **, Pgno *, Pgno, u8);

/*
** This routine is called prior to sqlite3pager_commit when a transaction
** is commited for an auto-vacuum database.
*/
static int autoVacuumCommit(Btree *pBt, Pgno *nTrunc){
  Pager *pPager = pBt->pPager;
  Pgno nFreeList;   /* Number of pages remaining on the free-list. */
  int nPtrMap;      /* Number of pointer-map pages deallocated */
  Pgno origSize;  /* Pages in the database file */
  Pgno finSize;   /* Pages in the database file after truncation */
  int rc;           /* Return code */
  u8 eType;
................................................................................

/*
** Commit the transaction currently in progress.
**
** This will release the write lock on the database file.  If there
** are no active cursors, it also releases the read lock.
*/
int sqlite3BtreeCommit(Btree *pBt){
  int rc = SQLITE_OK;








  if( pBt->inTrans==TRANS_WRITE ){


    rc = sqlite3pager_commit(pBt->pPager);


  }
















  pBt->inTrans = TRANS_NONE;
  pBt->inStmt = 0;
  unlockBtreeIfUnused(pBt);


  return rc;
}

#ifndef NDEBUG
/*
** Return the number of write-cursors open on this handle. This is for use
** in assert() expressions, so it is only compiled if NDEBUG is not
** defined.
*/
static int countWriteCursors(Btree *pBt){
  BtCursor *pCur;
  int r = 0;
  for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){
    if( pCur->wrFlag ) r++;
  }
  return r;
}
#endif

#ifdef SQLITE_TEST
/*
** Print debugging information about all cursors to standard output.
*/
void sqlite3BtreeCursorList(Btree *pBt){
  BtCursor *pCur;

  for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){
    MemPage *pPage = pCur->pPage;
    char *zMode = pCur->wrFlag ? "rw" : "ro";
    sqlite3DebugPrintf("CURSOR %p rooted at %4d(%s) currently at %d.%d%s\n",
       pCur, pCur->pgnoRoot, zMode,
       pPage ? pPage->pgno : 0, pCur->idx,
       pCur->isValid ? "" : " eof"
................................................................................
** invalided by this operation.  Any attempt to use a cursor
** that was open at the beginning of this operation will result
** in an error.
**
** This will release the write lock on the database file.  If there
** are no active cursors, it also releases the read lock.
*/
int sqlite3BtreeRollback(Btree *pBt){
  int rc = SQLITE_OK;

  MemPage *pPage1;




  if( pBt->inTrans==TRANS_WRITE ){


    rc = sqlite3pager_rollback(pBt->pPager);
    /* The rollback may have destroyed the pPage1->aData value.  So
    ** call getPage() on page 1 again to make sure pPage1->aData is
    ** set correctly. */
    if( getPage(pBt, 1, &pPage1)==SQLITE_OK ){
      releasePage(pPage1);
    }
    assert( countWriteCursors(pBt)==0 );

  }









  pBt->inTrans = TRANS_NONE;
  pBt->inStmt = 0;
  unlockBtreeIfUnused(pBt);


  return rc;
}

/*
** Start a statement subtransaction.  The subtransaction can
** can be rolled back independently of the main transaction.
** You must start a transaction before starting a subtransaction.
................................................................................
** to start a new subtransaction if another subtransaction is already active.
**
** Statement subtransactions are used around individual SQL statements
** that are contained within a BEGIN...COMMIT block.  If a constraint
** 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 *pBt){
  int rc;

  if( (pBt->inTrans!=TRANS_WRITE) || pBt->inStmt ){
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }

  rc = pBt->readOnly ? SQLITE_OK : sqlite3pager_stmt_begin(pBt->pPager);
  pBt->inStmt = 1;
  return rc;
}


/*
** Commit the statment subtransaction currently in progress.  If no
** subtransaction is active, this is a no-op.
*/
int sqlite3BtreeCommitStmt(Btree *pBt){
  int rc;

  if( pBt->inStmt && !pBt->readOnly ){
    rc = sqlite3pager_stmt_commit(pBt->pPager);
  }else{
    rc = SQLITE_OK;
  }
  pBt->inStmt = 0;
  return rc;
................................................................................
** Rollback the active statement subtransaction.  If no subtransaction
** is active this routine is a no-op.
**
** All cursors will be invalidated by this operation.  Any attempt
** to use a cursor that was open at the beginning of this operation
** will result in an error.
*/
int sqlite3BtreeRollbackStmt(Btree *pBt){
  int rc;

  if( pBt->inStmt==0 || pBt->readOnly ) return SQLITE_OK;
  rc = sqlite3pager_stmt_rollback(pBt->pPager);
  assert( countWriteCursors(pBt)==0 );
  pBt->inStmt = 0;
  return rc;
}

................................................................................
** The comparison function must be logically the same for every cursor
** on a particular table.  Changing the comparison function will result
** in incorrect operations.  If the comparison function is NULL, a
** default comparison function is used.  The comparison function is
** always ignored for INTKEY tables.
*/
int sqlite3BtreeCursor(
  Btree *pBt,                                 /* The btree */
  int iTable,                                 /* Root page of table to open */
  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;
  BtCursor *pCur;


  *ppCur = 0;
  if( wrFlag ){
    if( pBt->readOnly ){
      return SQLITE_READONLY;
    }
    if( checkReadLocks(pBt, iTable, 0) ){
      return SQLITE_LOCKED;
    }
  }








  if( pBt->pPage1==0 ){
    rc = lockBtreeWithRetry(pBt);
    if( rc!=SQLITE_OK ){
      return rc;
    }
  }
  pCur = sqliteMallocRaw( sizeof(*pCur) );
  if( pCur==0 ){
    rc = SQLITE_NOMEM;
................................................................................
    rc = SQLITE_EMPTY;
    goto create_cursor_exception;
  }
  rc = getAndInitPage(pBt, pCur->pgnoRoot, &pCur->pPage, 0);
  if( rc!=SQLITE_OK ){
    goto create_cursor_exception;
  }












  pCur->xCompare = xCmp ? xCmp : dfltCompare;
  pCur->pArg = pArg;
  pCur->pBt = pBt;
  pCur->wrFlag = wrFlag;
  pCur->idx = 0;
  memset(&pCur->info, 0, sizeof(pCur->info));
  pCur->pNext = pBt->pCursor;
  if( pCur->pNext ){
    pCur->pNext->pPrev = pCur;
  }
  pCur->pPrev = 0;
  pBt->pCursor = pCur;
  pCur->isValid = 0;
  *ppCur = pCur;
  return SQLITE_OK;


create_cursor_exception:
  if( pCur ){
    releasePage(pCur->pPage);
    sqliteFree(pCur);
  }
  unlockBtreeIfUnused(pBt);
  return rc;
................................................................................
#endif

/*
** Close a cursor.  The read lock on the database file is released
** when the last cursor is closed.
*/
int sqlite3BtreeCloseCursor(BtCursor *pCur){
  Btree *pBt = pCur->pBt;
  if( pCur->pPrev ){
    pCur->pPrev->pNext = pCur->pNext;
  }else{
    pBt->pCursor = pCur->pNext;
  }
  if( pCur->pNext ){
    pCur->pNext->pPrev = pCur->pPrev;
................................................................................
  unsigned char *pBuf, /* Write the bytes into this buffer */ 
  int skipKey          /* offset begins at data if this is true */
){
  unsigned char *aPayload;
  Pgno nextPage;
  int rc;
  MemPage *pPage;
  Btree *pBt;
  int ovflSize;
  u32 nKey;

  assert( pCur!=0 && pCur->pPage!=0 );
  assert( pCur->isValid );
  pBt = pCur->pBt;
  pPage = pCur->pPage;
  pageIntegrity(pPage);
  assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
  getCellInfo(pCur);
  aPayload = pCur->info.pCell;
  aPayload += pCur->info.nHeader;
  if( pPage->intKey ){
................................................................................
** Move the cursor down to a new child page.  The newPgno argument is the
** page number of the child page to move to.
*/
static int moveToChild(BtCursor *pCur, u32 newPgno){
  int rc;
  MemPage *pNewPage;
  MemPage *pOldPage;
  Btree *pBt = pCur->pBt;

  assert( pCur->isValid );
  rc = getAndInitPage(pBt, newPgno, &pNewPage, pCur->pPage);
  if( rc ) return rc;
  pageIntegrity(pNewPage);
  pNewPage->idxParent = pCur->idx;
  pOldPage = pCur->pPage;
................................................................................

/*
** Move the cursor to the root page
*/
static int moveToRoot(BtCursor *pCur){
  MemPage *pRoot;
  int rc;
  Btree *pBt = pCur->pBt;

  rc = getAndInitPage(pBt, pCur->pgnoRoot, &pRoot, 0);
  if( rc ){
    pCur->isValid = 0;
    return rc;
  }
  releasePage(pCur->pPage);
................................................................................
** which in turn can make database access faster.
**
** If the "exact" parameter is not 0, and the page-number nearby exists 
** anywhere on the free-list, then it is guarenteed to be returned. This
** is only used by auto-vacuum databases when allocating a new table.
*/
static int allocatePage(
  Btree *pBt, 
  MemPage **ppPage, 
  Pgno *pPgno, 
  Pgno nearby,
  u8 exact
){
  MemPage *pPage1;
  int rc;
................................................................................

/*
** Add a page of the database file to the freelist.
**
** sqlite3pager_unref() is NOT called for pPage.
*/
static int freePage(MemPage *pPage){
  Btree *pBt = pPage->pBt;
  MemPage *pPage1 = pBt->pPage1;
  int rc, n, k;

  /* Prepare the page for freeing */
  assert( pPage->pgno>1 );
  pPage->isInit = 0;
  releasePage(pPage->pParent);
................................................................................
  return rc;
}

/*
** Free any overflow pages associated with the given Cell.
*/
static int clearCell(MemPage *pPage, unsigned char *pCell){
  Btree *pBt = pPage->pBt;
  CellInfo info;
  Pgno ovflPgno;
  int rc;

  parseCellPtr(pPage, pCell, &info);
  if( info.iOverflow==0 ){
    return SQLITE_OK;  /* No overflow pages. Return without doing anything */
................................................................................
  const u8 *pSrc;
  int nSrc, n, rc;
  int spaceLeft;
  MemPage *pOvfl = 0;
  MemPage *pToRelease = 0;
  unsigned char *pPrior;
  unsigned char *pPayload;
  Btree *pBt = pPage->pBt;
  Pgno pgnoOvfl = 0;
  int nHeader;
  CellInfo info;

  /* Fill in the header. */
  nHeader = 0;
  if( !pPage->leaf ){
................................................................................
}

/*
** Change the MemPage.pParent pointer on the page whose number is
** given in the second argument so that MemPage.pParent holds the
** pointer in the third argument.
*/
static int reparentPage(Btree *pBt, Pgno pgno, MemPage *pNewParent, int idx){
  MemPage *pThis;
  unsigned char *aData;

  if( pgno==0 ) return SQLITE_OK;
  assert( pBt->pPager!=0 );
  aData = sqlite3pager_lookup(pBt->pPager, pgno);
  if( aData ){
................................................................................
** to make sure that each child knows that pPage is its parent.
**
** This routine gets called after you memcpy() one page into
** another.
*/
static int reparentChildPages(MemPage *pPage){
  int i;
  Btree *pBt = pPage->pBt;
  int rc = SQLITE_OK;

  if( pPage->leaf ) return SQLITE_OK;

  for(i=0; i<pPage->nCell; i++){
    u8 *pCell = findCell(pPage, i);
    if( !pPage->leaf ){
................................................................................
static int balance_quick(MemPage *pPage, MemPage *pParent){
  int rc;
  MemPage *pNew;
  Pgno pgnoNew;
  u8 *pCell;
  int szCell;
  CellInfo info;
  Btree *pBt = pPage->pBt;
  int parentIdx = pParent->nCell;   /* pParent new divider cell index */
  int parentSize;                   /* Size of new divider cell */
  u8 parentCell[64];                /* Space for the new divider cell */

  /* Allocate a new page. Insert the overflow cell from pPage
  ** into it. Then remove the overflow cell from pPage.
  */
................................................................................
**
** If this routine fails for any reason, it might leave the database
** in a corrupted state.  So if this routine fails, the database should
** be rolled back.
*/
static int balance_nonroot(MemPage *pPage){
  MemPage *pParent;            /* The parent of pPage */
  Btree *pBt;                  /* The whole database */
  int nCell = 0;               /* Number of cells in apCell[] */
  int nMaxCells = 0;           /* Allocated size of apCell, szCell, aFrom. */
  int nOld;                    /* Number of pages in apOld[] */
  int nNew;                    /* Number of pages in apNew[] */
  int nDiv;                    /* Number of cells in apDiv[] */
  int i, j, k;                 /* Loop counters */
  int idx;                     /* Index of pPage in pParent->aCell[] */
................................................................................
** page contains no cells.  This is an opportunity to make the tree
** shallower by one level.
*/
static int balance_shallower(MemPage *pPage){
  MemPage *pChild;             /* The only child page of pPage */
  Pgno pgnoChild;              /* Page number for pChild */
  int rc = SQLITE_OK;          /* Return code from subprocedures */
  Btree *pBt;                  /* The main BTree structure */
  int mxCellPerPage;           /* Maximum number of cells per page */
  u8 **apCell;                 /* All cells from pages being balanced */
  int *szCell;                 /* Local size of all cells */

  assert( pPage->pParent==0 );
  assert( pPage->nCell==0 );
  pBt = pPage->pBt;
................................................................................
** child.   Finally, call balance_internal() on the new child
** to cause it to split.
*/
static int balance_deeper(MemPage *pPage){
  int rc;             /* Return value from subprocedures */
  MemPage *pChild;    /* Pointer to a new child page */
  Pgno pgnoChild;     /* Page number of the new child page */
  Btree *pBt;         /* The BTree */
  int usableSize;     /* Total usable size of a page */
  u8 *data;           /* Content of the parent page */
  u8 *cdata;          /* Content of the child page */
  int hdr;            /* Offset to page header in parent */
  int brk;            /* Offset to content of first cell in parent */

  assert( pPage->pParent==0 );
................................................................................
** means a cursor opened with wrFlag==0) this routine also moves
** all cursors other than pExclude so that they are pointing to the 
** first Cell on root page.  This is necessary because an insert 
** 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 *pBt, Pgno pgnoRoot, BtCursor *pExclude){
  BtCursor *p;
  for(p=pBt->pCursor; p; p=p->pNext){
    if( p->pgnoRoot!=pgnoRoot || p==pExclude ) continue;
    if( p->wrFlag==0 ) return SQLITE_LOCKED;
    if( p->pPage->pgno!=p->pgnoRoot ){
      moveToRoot(p);
    }
................................................................................
  const void *pKey, i64 nKey,    /* The key of the new record */
  const void *pData, int nData   /* The data of the new record */
){
  int rc;
  int loc;
  int szNew;
  MemPage *pPage;
  Btree *pBt = pCur->pBt;
  unsigned char *oldCell;
  unsigned char *newCell = 0;

  if( pBt->inTrans!=TRANS_WRITE ){
    /* Must start a transaction before doing an insert */
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }
  assert( !pBt->readOnly );
  if( !pCur->wrFlag ){
    return SQLITE_PERM;   /* Cursor not open for writing */
  }
................................................................................
** is left pointing at a random location.
*/
int sqlite3BtreeDelete(BtCursor *pCur){
  MemPage *pPage = pCur->pPage;
  unsigned char *pCell;
  int rc;
  Pgno pgnoChild = 0;
  Btree *pBt = pCur->pBt;

  assert( pPage->isInit );
  if( pBt->inTrans!=TRANS_WRITE ){
    /* Must start a transaction before doing a delete */
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }
  assert( !pBt->readOnly );
  if( pCur->idx >= pPage->nCell ){
    return SQLITE_ERROR;  /* The cursor is not pointing to anything */
  }
................................................................................
** The type of type is determined by the flags parameter.  Only the
** following values of flags are currently in use.  Other values for
** flags might not work:
**
**     BTREE_INTKEY|BTREE_LEAFDATA     Used for SQL tables with rowid keys
**     BTREE_ZERODATA                  Used for SQL indices
*/
int sqlite3BtreeCreateTable(Btree *pBt, int *piTable, int flags){

  MemPage *pRoot;
  Pgno pgnoRoot;
  int rc;
  if( pBt->inTrans!=TRANS_WRITE ){
    /* Must start a transaction first */
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }
  assert( !pBt->readOnly );

  /* It is illegal to create a table if any cursors are open on the
  ** database. This is because in auto-vacuum mode the backend may
................................................................................
    Pgno pgnoMove;      /* Move a page here to make room for the root-page */
    MemPage *pPageMove; /* The page to move to. */

    /* Read the value of meta[3] from the database to determine where the
    ** root page of the new table should go. meta[3] is the largest root-page
    ** created so far, so the new root-page is (meta[3]+1).
    */
    rc = sqlite3BtreeGetMeta(pBt, 4, &pgnoRoot);
    if( rc!=SQLITE_OK ) return rc;
    pgnoRoot++;

    /* The new root-page may not be allocated on a pointer-map page, or the
    ** PENDING_BYTE page.
    */
    if( pgnoRoot==PTRMAP_PAGENO(pBt->usableSize, pgnoRoot) ||
................................................................................

    /* Update the pointer-map and meta-data with the new root-page number. */
    rc = ptrmapPut(pBt, pgnoRoot, PTRMAP_ROOTPAGE, 0);
    if( rc ){
      releasePage(pRoot);
      return rc;
    }
    rc = sqlite3BtreeUpdateMeta(pBt, 4, pgnoRoot);
    if( rc ){
      releasePage(pRoot);
      return rc;
    }

  }else{
    rc = allocatePage(pBt, &pRoot, &pgnoRoot, 1, 0);
................................................................................
}

/*
** Erase the given database page and all its children.  Return
** the page to the freelist.
*/
static int clearDatabasePage(
  Btree *pBt,           /* The BTree that contains the table */
  Pgno pgno,            /* Page number to clear */
  MemPage *pParent,     /* Parent page.  NULL for the root */
  int freePageFlag      /* Deallocate page if true */
){
  MemPage *pPage = 0;
  int rc;
  unsigned char *pCell;
................................................................................
** the page number of the root of the table.  After this routine returns,
** the root page is empty, but still exists.
**
** This routine will fail with SQLITE_LOCKED if there are any open
** read cursors on the table.  Open write cursors are moved to the
** root of the table.
*/
int sqlite3BtreeClearTable(Btree *pBt, int iTable){
  int rc;
  BtCursor *pCur;

  if( pBt->inTrans!=TRANS_WRITE ){
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }
  for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){
    if( pCur->pgnoRoot==(Pgno)iTable ){
      if( pCur->wrFlag==0 ) return SQLITE_LOCKED;
      moveToRoot(pCur);
    }
................................................................................
** root pages are kept at the beginning of the database file, which
** is necessary for AUTOVACUUM to work right.  *piMoved is set to the 
** page number that used to be the last root page in the file before
** the move.  If no page gets moved, *piMoved is set to 0.
** The last root page is recorded in meta[3] and the value of
** meta[3] is updated by this procedure.
*/
int sqlite3BtreeDropTable(Btree *pBt, int iTable, int *piMoved){
  int rc;
  MemPage *pPage = 0;


  if( pBt->inTrans!=TRANS_WRITE ){
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }

  /* It is illegal to drop a table if any cursors are open on the
  ** database. This is because in auto-vacuum mode the backend may
  ** need to move another root-page to fill a gap left by the deleted
  ** root page. If an open cursor was using this page a problem would 
................................................................................
  */
  if( pBt->pCursor ){
    return SQLITE_LOCKED;
  }

  rc = getPage(pBt, (Pgno)iTable, &pPage);
  if( rc ) return rc;
  rc = sqlite3BtreeClearTable(pBt, iTable);
  if( rc ){
    releasePage(pPage);
    return rc;
  }

  *piMoved = 0;

................................................................................
  if( iTable>1 ){
#ifdef SQLITE_OMIT_AUTOVACUUM
    rc = freePage(pPage);
    releasePage(pPage);
#else
    if( pBt->autoVacuum ){
      Pgno maxRootPgno;
      rc = sqlite3BtreeGetMeta(pBt, 4, &maxRootPgno);
      if( rc!=SQLITE_OK ){
        releasePage(pPage);
        return rc;
      }

      if( iTable==maxRootPgno ){
        /* If the table being dropped is the table with the largest root-page
................................................................................
        maxRootPgno--;
      }
      if( maxRootPgno==PTRMAP_PAGENO(pBt->usableSize, maxRootPgno) ){
        maxRootPgno--;
      }
      assert( maxRootPgno!=PENDING_BYTE_PAGE(pBt) );

      rc = sqlite3BtreeUpdateMeta(pBt, 4, maxRootPgno);
    }else{
      rc = freePage(pPage);
      releasePage(pPage);
    }
#endif
  }else{
    /* If sqlite3BtreeDropTable was called on page 1. */
................................................................................
** through meta[15] are available for use by higher layers.  Meta[0]
** is read-only, the others are read/write.
** 
** The schema layer numbers meta values differently.  At the schema
** layer (and the SetCookie and ReadCookie opcodes) the number of
** free pages is not visible.  So Cookie[0] is the same as Meta[1].
*/
int sqlite3BtreeGetMeta(Btree *pBt, int idx, u32 *pMeta){
  int rc;
  unsigned char *pP1;


  assert( idx>=0 && idx<=15 );
  rc = sqlite3pager_get(pBt->pPager, 1, (void**)&pP1);
  if( rc ) return rc;
  *pMeta = get4byte(&pP1[36 + idx*4]);
  sqlite3pager_unref(pP1);

................................................................................
  return SQLITE_OK;
}

/*
** Write meta-information back into the database.  Meta[0] is
** read-only and may not be written.
*/
int sqlite3BtreeUpdateMeta(Btree *pBt, int idx, u32 iMeta){

  unsigned char *pP1;
  int rc;
  assert( idx>=1 && idx<=15 );
  if( pBt->inTrans!=TRANS_WRITE ){
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }
  assert( pBt->pPage1!=0 );
  pP1 = pBt->pPage1->aData;
  rc = sqlite3pager_write(pP1);
  if( rc ) return rc;
  put4byte(&pP1[36 + idx*4], iMeta);
................................................................................
}

#ifdef SQLITE_DEBUG
/*
** Print a disassembly of the given page on standard output.  This routine
** is used for debugging and testing only.
*/
static int btreePageDump(Btree *pBt, int pgno, int recursive, MemPage *pParent){
  int rc;
  MemPage *pPage;
  int i, j, c;
  int nFree;
  u16 idx;
  int hdr;
  int nCell;
................................................................................
    btreePageDump(pBt, get4byte(&data[hdr+8]), 1, pPage);
  }
  pPage->isInit = isInit;
  sqlite3pager_unref(data);
  fflush(stdout);
  return SQLITE_OK;
}
int sqlite3BtreePageDump(Btree *pBt, int pgno, int recursive){
  return btreePageDump(pBt, pgno, recursive, 0);
}
#endif

#ifdef SQLITE_TEST
/*
** Fill aResult[] with information about the entry and page that the
** cursor is pointing to.
................................................................................
}
#endif

/*
** Return the pager associated with a BTree.  This routine is used for
** testing and debugging only.
*/
Pager *sqlite3BtreePager(Btree *pBt){
  return pBt->pPager;
}

/*
** This structure is passed around through all the sanity checking routines
** in order to keep track of some global state information.
*/
typedef struct IntegrityCk IntegrityCk;
struct IntegrityCk {
  Btree *pBt;    /* The tree being checked out */
  Pager *pPager; /* The associated pager.  Also accessible by pBt->pPager */
  int nPage;     /* Number of pages in the database */
  int *anRef;    /* Number of times each page is referenced */
  char *zErrMsg; /* An error message.  NULL of no errors seen. */
};

#ifndef SQLITE_OMIT_INTEGRITY_CHECK
................................................................................
  int nUpper            /* Number of characters in zUpperBound */
){
  MemPage *pPage;
  int i, rc, depth, d2, pgno, cnt;
  int hdr, cellStart;
  int nCell;
  u8 *data;
  Btree *pBt;
  int usableSize;
  char zContext[100];
  char *hit;

  sprintf(zContext, "Page %d: ", iPage);

  /* Check that the page exists
................................................................................
** a table.  nRoot is the number of entries in aRoot.
**
** If everything checks out, this routine returns NULL.  If something is
** amiss, an error message is written into memory obtained from malloc()
** and a pointer to that error message is returned.  The calling function
** is responsible for freeing the error message when it is done.
*/
char *sqlite3BtreeIntegrityCheck(Btree *pBt, int *aRoot, int nRoot){
  int i;
  int nRef;
  IntegrityCk sCheck;


  nRef = *sqlite3pager_stats(pBt->pPager);
  if( lockBtreeWithRetry(pBt)!=SQLITE_OK ){
    return sqliteStrDup("Unable to acquire a read lock on the database");
  }
  sCheck.pBt = pBt;
  sCheck.pPager = pBt->pPager;
  sCheck.nPage = sqlite3pager_pagecount(sCheck.pPager);
  if( sCheck.nPage==0 ){
    unlockBtreeIfUnused(pBt);
................................................................................
  return sCheck.zErrMsg;
}
#endif /* SQLITE_OMIT_INTEGRITY_CHECK */

/*
** Return the full pathname of the underlying database file.
*/
const char *sqlite3BtreeGetFilename(Btree *pBt){
  assert( pBt->pPager!=0 );
  return sqlite3pager_filename(pBt->pPager);
}

/*
** Return the pathname of the directory that contains the database file.
*/
const char *sqlite3BtreeGetDirname(Btree *pBt){
  assert( pBt->pPager!=0 );
  return sqlite3pager_dirname(pBt->pPager);
}

/*
** Return the pathname of the journal file for this database. The return
** value of this routine is the same regardless of whether the journal file
** has been created or not.
*/
const char *sqlite3BtreeGetJournalname(Btree *pBt){
  assert( pBt->pPager!=0 );
  return sqlite3pager_journalname(pBt->pPager);
}

#ifndef SQLITE_OMIT_VACUUM
/*
** Copy the complete content of pBtFrom into pBtTo.  A transaction
** must be active for both files.
**
** The size of file pBtFrom may be reduced by this operation.
** If anything goes wrong, the transaction on pBtFrom is rolled back.
*/
int sqlite3BtreeCopyFile(Btree *pBtTo, Btree *pBtFrom){
  int rc = SQLITE_OK;
  Pgno i, nPage, nToPage, iSkip;




  if( pBtTo->inTrans!=TRANS_WRITE || pBtFrom->inTrans!=TRANS_WRITE ){
    return SQLITE_ERROR;
  }
  if( pBtTo->pCursor ) return SQLITE_BUSY;
  nToPage = sqlite3pager_pagecount(pBtTo->pPager);
  nPage = sqlite3pager_pagecount(pBtFrom->pPager);
  iSkip = PENDING_BYTE_PAGE(pBtTo);
  for(i=1; rc==SQLITE_OK && i<=nPage; i++){
................................................................................
    sqlite3pager_unref(pPage);
    sqlite3pager_dont_write(pBtTo->pPager, i);
  }
  if( !rc && nPage<nToPage ){
    rc = sqlite3pager_truncate(pBtTo->pPager, nPage);
  }
  if( rc ){
    sqlite3BtreeRollback(pBtTo);
  }
  return rc;  
}
#endif /* SQLITE_OMIT_VACUUM */

/*
** Return non-zero if a transaction is active.
*/
int sqlite3BtreeIsInTrans(Btree *pBt){
  return (pBt && (pBt->inTrans==TRANS_WRITE));
}

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

/*
** This call is a no-op if no write-transaction is currently active on pBt.
**
** Otherwise, sync the database file for the btree pBt. zMaster points to
** the name of a master journal file that should be written into the
................................................................................
**
** When this is called, the master journal should already have been
** created, populated with this journal pointer and synced to disk.
**
** Once this is routine has returned, the only thing required to commit
** the write-transaction for this database file is to delete the journal.
*/
int sqlite3BtreeSync(Btree *pBt, const char *zMaster){
  if( pBt->inTrans==TRANS_WRITE ){

#ifndef SQLITE_OMIT_AUTOVACUUM
    Pgno nTrunc = 0;
    if( pBt->autoVacuum ){
      int rc = autoVacuumCommit(pBt, &nTrunc); 
      if( rc!=SQLITE_OK ) return rc;
    }
    return sqlite3pager_sync(pBt->pPager, zMaster, nTrunc);
#endif
    return sqlite3pager_sync(pBt->pPager, zMaster, 0);
  }
  return SQLITE_OK;
}

** 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.277 2005/12/30 16:28:02 danielk1977 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.
................................................................................
** assumes a minimum cell size of 3 bytes.  Such small cells will be
** exceedingly rare, but they are possible.
*/
#define MX_CELL(pBt) ((pBt->pageSize-8)/3)

/* Forward declarations */
typedef struct MemPage MemPage;
typedef struct BtLock BtLock;

/*
** This is a magic string that appears at the beginning of every
** SQLite database in order to identify the file as a real database.
**
** You can change this value at compile-time by specifying a
** -DSQLITE_FILE_HEADER="..." on the compiler command-line.  The
................................................................................
  u16 maxLocal;        /* Copy of Btree.maxLocal or Btree.maxLeaf */
  u16 minLocal;        /* Copy of Btree.minLocal or Btree.minLeaf */
  u16 cellOffset;      /* Index in aData of first cell pointer */
  u16 idxParent;       /* Index in parent of this node */
  u16 nFree;           /* Number of free bytes on the page */
  u16 nCell;           /* Number of cells on this page, local and ovfl */
  struct _OvflCell {   /* Cells that will not fit on aData[] */
    u8 *pCell;          /* Pointers to the body of the overflow cell */
    u16 idx;            /* Insert this cell before idx-th non-overflow cell */
  } aOvfl[5];
  BtShared *pBt;        /* Pointer back to BTree structure */
  u8 *aData;            /* Pointer back to the start of the page */
  Pgno pgno;            /* Page number for this page */
  MemPage *pParent;     /* The parent of this page.  NULL for root */
};

/*
** The in-memory image of a disk page has the auxiliary information appended
** to the end.  EXTRA_SIZE is the number of bytes of space needed to hold
** that extra information.
*/
#define EXTRA_SIZE sizeof(MemPage)

/* Btree handle */
struct Btree {
  sqlite3 *pSqlite;
  BtShared *pBt;
  u8 inTrans;            /* TRANS_NONE, TRANS_READ or TRANS_WRITE */
};

/*
** Btree.inTrans may take one of the following values.
**
** If the shared-data extension is enabled, there may be multiple users
** of the Btree structure. At most one of these may open a write transaction,
** but any number may have active read transactions. Variable Btree.pDb 
** points to the handle that owns any current write-transaction.
*/
#define TRANS_NONE  0
#define TRANS_READ  1
#define TRANS_WRITE 2

/*
** Everything we need to know about an open database
*/
struct BtShared {
  Pager *pPager;        /* The page cache */
  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
................................................................................
  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 */
  BusyHandler *pBusyHandler;   /* Callback for when there is lock contention */
  u8 inTransaction;     /* Transaction state */
  BtShared *pNext;      /* Next in SqliteTsd.pBtree linked list */
  int nRef;             /* Number of references to this structure */
  int nTransaction;     /* Number of open transactions (read + write) */
  BtLock *pLock;        /* List of locks held on this shared-btree struct */
};









/*
** An instance of the following structure is used to hold information
** about a cell.  The parseCellPtr() function fills in this structure
** based on information extract from the raw disk page.
*/
typedef struct CellInfo CellInfo;
................................................................................

/*
** A cursor is a pointer to a particular entry in the BTree.
** The entry is identified by its MemPage and the index in
** MemPage.aCell[] of the entry.
*/
struct BtCursor {
  Btree *pBtree;            /* The Btree to which this cursor belongs */
  BtCursor *pNext, *pPrev;  /* Forms a linked list of all cursors */
  int (*xCompare)(void*,int,const void*,int,const void*); /* Key comp func */
  void *pArg;               /* First arg to xCompare() */
  Pgno pgnoRoot;            /* The root page of this tree */
  MemPage *pPage;           /* Page that contains the entry */
  int idx;                  /* Index of the entry in pPage->aCell[] */
  CellInfo info;            /* A parse of the cell we are pointing at */
................................................................................
# define TRACE(X)
#endif
int sqlite3_btree_trace=0;  /* True to enable tracing */

/*
** Forward declaration
*/
static int checkReadLocks(BtShared*,Pgno,BtCursor*);

/*
** Read or write a two- and four-byte big-endian integer values.
*/
static u32 get2byte(unsigned char *p){
  return (p[0]<<8) | p[1];
}
................................................................................

/* The database page the PENDING_BYTE occupies. This page is never used.
** TODO: This macro is very similary to PAGER_MJ_PGNO() in pager.c. They
** should possibly be consolidated (presumably in pager.h).
*/
#define PENDING_BYTE_PAGE(pBt) ((PENDING_BYTE/(pBt)->pageSize)+1)

/*
** A linked list of the following structures is stored at BtShared.pLock.
** Locks are added (or upgraded from READ_LOCK to WRITE_LOCK) when a cursor 
** is opened on the table with root page BtShared.iTable. Locks are removed
** from this list when a transaction is committed or rolled back, or when
** a btree handle is closed.
*/
struct BtLock {
  Btree *pBtree;        /* Btree handle holding this lock */
  Pgno iTable;          /* Root page of table */
  u8 eLock;             /* READ_LOCK or WRITE_LOCK */
  BtLock *pNext;        /* Next in BtShared.pLock list */
};

/* Candidate values for BtLock.eLock */
#define READ_LOCK     1
#define WRITE_LOCK    2

#ifdef SQLITE_OMIT_SHARED_CACHE
  /*
  ** The functions queryTableLock(), lockTable() and unlockAllTables()
  ** 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 required. 
  ** So define the three interface functions as no-ops.
  */
  #define queryTableLock(a,b,c) SQLITE_OK
  #define lockTable(a,b,c) SQLITE_OK
  #define unlockAllTables(a,b,c)
#else

/*
** 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 lockTable()), or
** SQLITE_BUSY if not.
*/
static int queryTableLock(Btree *p, Pgno iTab, u8 eLock){
  BtShared *pBt = p->pBt;
  BtLock *pIter;

  for(pIter=pBt->pLock; pIter; pIter=pIter->pNext){
    if( pIter->pBtree!=p && pIter->iTable==iTab && 
        (pIter->eLock!=READ_LOCK || eLock!=READ_LOCK) ){
      return SQLITE_BUSY;
    }
  }
  return SQLITE_OK;
}

/*
** 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.
**
** SQLITE_OK is returned if the lock is added successfully. SQLITE_BUSY and
** SQLITE_NOMEM may also be returned.
*/
static int lockTable(Btree *p, Pgno iTable, u8 eLock){
  BtShared *pBt = p->pBt;
  BtLock *pLock = 0;
  BtLock *pIter;

  assert( SQLITE_OK==queryTableLock(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 *)sqliteMalloc(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 );
  pLock->eLock = MAX(pLock->eLock, eLock);

  return SQLITE_OK;
}

/*
** Release all the table locks (locks obtained via calls to the lockTable()
** procedure) held by Btree handle p.
*/
static void unlockAllTables(Btree *p){
  BtLock **ppIter = &p->pBt->pLock;
  while( *ppIter ){
    BtLock *pLock = *ppIter;
    if( pLock->pBtree==p ){
      *ppIter = pLock->pNext;
      sqliteFree(pLock);
    }else{
      ppIter = &pLock->pNext;
    }
  }
}
#endif /* SQLITE_OMIT_SHARED_CACHE */

#ifndef SQLITE_OMIT_AUTOVACUUM
/*
** These macros define the location of the pointer-map entry for a 
** database page. The first argument to each is the number of usable
** bytes on each page of the database (often 1024). The second is the
** page number to look up in the pointer map.
**
................................................................................
/*
** 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'.
** An error code is returned if something goes wrong, otherwise SQLITE_OK.
*/
static int ptrmapPut(BtShared *pBt, Pgno key, u8 eType, Pgno parent){
  u8 *pPtrmap;    /* The pointer map page */
  Pgno iPtrmap;   /* The pointer map page number */
  int offset;     /* Offset in pointer map page */
  int rc;

  assert( pBt->autoVacuum );
  if( key==0 ){
................................................................................
/*
** 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){
  int iPtrmap;       /* Pointer map page index */
  u8 *pPtrmap;       /* Pointer map page data */
  int offset;        /* Offset of entry in pointer map */
  int rc;

  iPtrmap = PTRMAP_PAGENO(pBt->usableSize, key);
  rc = sqlite3pager_get(pBt->pPager, iPtrmap, (void **)&pPtrmap);
................................................................................
  sqlite3pager_unref(pPtrmap);
  if( *pEType<1 || *pEType>5 ) return SQLITE_CORRUPT_BKPT;
  return SQLITE_OK;
}

#endif /* SQLITE_OMIT_AUTOVACUUM */

/*
** Return a pointer to the Btree structure associated with btree pBt
** and connection handle pSqlite.
*/
#if 0
static Btree *btree_findref(BtShared *pBt, sqlite3 *pSqlite){
#ifndef SQLITE_OMIT_SHARED_DATA
  if( pBt->aRef ){
    int i;
    for(i=0; i<pBt->nRef; i++){
      if( pBt->aRef[i].pSqlite==pSqlite ){
        return &pBt->aRef[i];
      }
    }
    assert(0);
  }
#endif
  return &pBt->ref;
}
#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.
*/
................................................................................
  sqliteFree(used);
}
#define pageIntegrity(X) _pageIntegrity(X)
#else
# define pageIntegrity(X)
#endif

/* A bunch of assert() statements to check the transaction state variables
** of handle p (type Btree*) are internally consistent.
*/
#define btreeIntegrity(p) \
  assert( p->inTrans!=TRANS_NONE || p->pBt->nTransaction<p->pBt->nRef ); \
  assert( p->pBt->nTransaction<=p->pBt->nRef ); \
  assert( p->pBt->inTransaction!=TRANS_NONE || p->pBt->nTransaction==0 ); \
  assert( p->pBt->inTransaction>=p->inTrans ); 

/*
** Defragment the page given.  All Cells are moved to the
** end of the page and all free space is collected into one
** big FreeBlk that occurs in between the header and cell
** pointer array and the cell content area.
*/
static int defragmentPage(MemPage *pPage){
................................................................................
}

/*
** Decode the flags byte (the first byte of the header) for a page
** and initialize fields of the MemPage structure accordingly.
*/
static void decodeFlags(MemPage *pPage, int flagByte){
  BtShared *pBt;     /* A copy of pPage->pBt */

  assert( pPage->hdrOffset==(pPage->pgno==1 ? 100 : 0) );
  pPage->intKey = (flagByte & (PTF_INTKEY|PTF_LEAFDATA))!=0;
  pPage->zeroData = (flagByte & PTF_ZERODATA)!=0;
  pPage->leaf = (flagByte & PTF_LEAF)!=0;
  pPage->childPtrSize = 4*(pPage->leaf==0);
  pBt = pPage->pBt;
................................................................................
static int initPage(
  MemPage *pPage,        /* The page to be initialized */
  MemPage *pParent       /* The parent.  Might be NULL */
){
  int pc;            /* Address of a freeblock within pPage->aData[] */
  int hdr;           /* Offset to beginning of page header */
  u8 *data;          /* Equal to pPage->aData */
  BtShared *pBt;        /* The main btree structure */
  int usableSize;    /* Amount of usable space on each page */
  int cellOffset;    /* Offset from start of page to first cell pointer */
  int nFree;         /* Number of unused bytes on the page */
  int top;           /* First byte of the cell content area */

  pBt = pPage->pBt;
  assert( pBt!=0 );
................................................................................

/*
** Set up a raw page so that it looks like a database page holding
** no entries.
*/
static void zeroPage(MemPage *pPage, int flags){
  unsigned char *data = pPage->aData;
  BtShared *pBt = pPage->pBt;
  int hdr = pPage->hdrOffset;
  int first;

  assert( sqlite3pager_pagenumber(data)==pPage->pgno );
  assert( &data[pBt->pageSize] == (unsigned char*)pPage );
  assert( sqlite3pager_iswriteable(data) );
  memset(&data[hdr], 0, pBt->usableSize - hdr);
................................................................................
  pageIntegrity(pPage);
}

/*
** Get a page from the pager.  Initialize the MemPage.pBt and
** MemPage.aData elements if needed.
*/
static int getPage(BtShared *pBt, Pgno pgno, MemPage **ppPage){
  int rc;
  unsigned char *aData;
  MemPage *pPage;
  rc = sqlite3pager_get(pBt->pPager, pgno, (void**)&aData);
  if( rc ) return rc;
  pPage = (MemPage*)&aData[pBt->pageSize];
  pPage->aData = aData;
................................................................................

/*
** Get a page from the pager and initialize it.  This routine
** is just a convenience wrapper around separate calls to
** getPage() and initPage().
*/
static int getAndInitPage(
  BtShared *pBt,          /* The database file */
  Pgno pgno,           /* Number of the page to get */
  MemPage **ppPage,    /* Write the page pointer here */
  MemPage *pParent     /* Parent of the page */
){
  int rc;
  if( pgno==0 ){
    return SQLITE_CORRUPT_BKPT; 
................................................................................
** 
** 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.
*/
int sqlite3BtreeOpen(
  const char *zFilename,  /* Name of the file containing the BTree database */
  sqlite3 *pSqlite,       /* Associated database handle */
  Btree **ppBtree,        /* Pointer to new Btree object written here */
  int flags               /* Options */
){
  BtShared *pBt;          /* Shared part of btree structure */
  Btree *p;               /* Handle to return */
  int rc;
  int nReserve;
  unsigned char zDbHeader[100];
  SqliteTsd *pTsd = sqlite3Tsd();

  /* Set the variable isMemdb to true for an in-memory database, or 
  ** false for a file-based database. This symbol is only required if
  ** either of the shared-data or autovacuum features are compiled 
  ** into the library.
  */
#if !defined(SQLITE_OMIT_SHARED_CACHE) || !defined(SQLITE_OMIT_AUTOVACUUM)
  #ifdef SQLITE_OMIT_MEMORYDB
  const int isMemdb = !zFilename;
  #else
  const int isMemdb = !zFilename || (strcmp(zFilename, ":memory:")?0:1);
  #endif
#endif

  p = sqliteMalloc(sizeof(Btree));
  if( !p ){
    return SQLITE_NOMEM;
  }
  p->inTrans = TRANS_NONE;
  p->pSqlite = pSqlite;

  /* Try to find an existing Btree structure opened on zFilename. */
#ifndef SQLITE_OMIT_SHARED_CACHE
  if( pTsd->useSharedData && zFilename && !isMemdb ){
    char *zFullPathname = sqlite3Os.xFullPathname(zFilename);
    if( !zFullPathname ){
      sqliteFree(p);
      return SQLITE_NOMEM;
    }
    for(pBt=pTsd->pBtree; pBt; pBt=pBt->pNext){
      if( 0==strcmp(zFullPathname, sqlite3pager_filename(pBt->pPager)) ){
        p->pBt = pBt;
        *ppBtree = p;
        pBt->nRef++;
        sqliteFree(zFullPathname);
        return SQLITE_OK;
      }
    }
    sqliteFree(zFullPathname);
  }
#endif

  /*
  ** The following asserts make sure that structures used by the btree are
  ** the right size.  This is to guard against size changes that result
  ** when compiling on a different architecture.
  */
  assert( sizeof(i64)==8 );
................................................................................
  assert( sizeof(u32)==4 );
  assert( sizeof(u16)==2 );
  assert( sizeof(Pgno)==4 );

  pBt = sqliteMalloc( sizeof(*pBt) );
  if( pBt==0 ){
    *ppBtree = 0;
    sqliteFree(p);
    return SQLITE_NOMEM;
  }
  rc = sqlite3pager_open(&pBt->pPager, zFilename, EXTRA_SIZE, flags);
  if( rc!=SQLITE_OK ){
    if( pBt->pPager ) sqlite3pager_close(pBt->pPager);
    sqliteFree(pBt);
    sqliteFree(p);
    *ppBtree = 0;
    return rc;
  }
  p->pBt = pBt;

  sqlite3pager_set_destructor(pBt->pPager, pageDestructor);
  sqlite3pager_set_reiniter(pBt->pPager, pageReinit);
  pBt->pCursor = 0;
  pBt->pPage1 = 0;
  pBt->readOnly = sqlite3pager_isreadonly(pBt->pPager);
  sqlite3pager_read_fileheader(pBt->pPager, sizeof(zDbHeader), zDbHeader);
  pBt->pageSize = get2byte(&zDbHeader[16]);
................................................................................
#ifndef SQLITE_OMIT_AUTOVACUUM
    /* If the magic name ":memory:" will create an in-memory database, then
    ** do not set the auto-vacuum flag, even if SQLITE_DEFAULT_AUTOVACUUM
    ** is true. On the other hand, if SQLITE_OMIT_MEMORYDB has been defined,
    ** then ":memory:" is just a regular file-name. Respect the auto-vacuum
    ** default in this case.
    */



    if( zFilename && !isMemdb ){

      pBt->autoVacuum = SQLITE_DEFAULT_AUTOVACUUM;
    }
#endif
    nReserve = 0;
  }else{
    nReserve = zDbHeader[20];
    pBt->maxEmbedFrac = zDbHeader[21];
................................................................................
#ifndef SQLITE_OMIT_AUTOVACUUM
    pBt->autoVacuum = (get4byte(&zDbHeader[36 + 4*4])?1:0);
#endif
  }
  pBt->usableSize = pBt->pageSize - nReserve;
  assert( (pBt->pageSize & 7)==0 );  /* 8-byte alignment of pageSize */
  sqlite3pager_set_pagesize(pBt->pPager, pBt->pageSize);

#ifndef SQLITE_OMIT_SHARED_CACHE
  /* Add the new btree to the linked list starting at SqliteTsd.pBtree */
  if( pTsd->useSharedData && zFilename && !isMemdb ){
    pBt->pNext = pTsd->pBtree;
    pTsd->pBtree = pBt;
  }
  pBt->nRef = 1;
#endif
  *ppBtree = p;
  return SQLITE_OK;
}

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

  /* Drop any table-locks */
  unlockAllTables(p);

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

  sqliteFree(p);

#ifndef SQLITE_OMIT_SHARED_CACHE
  /* If there are still other outstanding references to the shared-btree
  ** structure, return now. The remainder of this procedure cleans 
  ** up the shared-btree.
  */
  assert( pBt->nRef>0 );
  pBt->nRef--;
  if( pBt->nRef ){
    return SQLITE_OK;
  }

  /* Remove the shared-btree from the thread wide list */
  if( pTsd->pBtree==pBt ){
    pTsd->pBtree = pBt->pNext;
  }else{
    BtShared *pPrev;
    for(pPrev=pTsd->pBtree; pPrev && pPrev->pNext!=pBt; pPrev=pPrev->pNext);
    if( pPrev ){
      pPrev->pNext = pBt->pNext;
    }
  }
#endif

  /* Close the pager and free the shared-btree structure */
  assert( !pBt->pCursor );
  sqlite3pager_close(pBt->pPager);
  sqliteFree(pBt);
  return SQLITE_OK;
}

/*
** Change the busy handler callback function.
*/
int sqlite3BtreeSetBusyHandler(Btree *p, BusyHandler *pHandler){
  BtShared *pBt = p->pBt;
  pBt->pBusyHandler = pHandler;
  sqlite3pager_set_busyhandler(pBt->pPager, pHandler);
  return SQLITE_OK;
}

/*
** Change the limit on the number of pages allowed in the cache.
................................................................................
** 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;
  sqlite3pager_set_cachesize(pBt->pPager, mxPage);
  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){
  BtShared *pBt = p->pBt;
  sqlite3pager_set_safety_level(pBt->pPager, level);
  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;
  assert( pBt && pBt->pPager );
  return sqlite3pager_nosync(pBt->pPager);
}

#if !defined(SQLITE_OMIT_PAGER_PRAGMAS) || !defined(SQLITE_OMIT_VACUUM)
/*
** Change the default pages size and the number of reserved bytes per page.
................................................................................
** of the database file used for locking (beginning at PENDING_BYTE,
** the first byte past the 1GB boundary, 0x40000000) needs to occur
** at the beginning of a page.
**
** If parameter nReserve is less than zero, then the number of reserved
** bytes per page is left unchanged.
*/
int sqlite3BtreeSetPageSize(Btree *p, int pageSize, int nReserve){
  BtShared *pBt = p->pBt;
  if( pBt->pageSizeFixed ){
    return SQLITE_READONLY;
  }
  if( nReserve<0 ){
    nReserve = pBt->pageSize - pBt->usableSize;
  }
  if( pageSize>=512 && pageSize<=SQLITE_MAX_PAGE_SIZE &&
        ((pageSize-1)&pageSize)==0 ){
    assert( (pageSize & 7)==0 );
    assert( !pBt->pPage1 && !pBt->pCursor );
    pBt->pageSize = sqlite3pager_set_pagesize(pBt->pPager, pageSize);
  }
  pBt->usableSize = pBt->pageSize - nReserve;
  return SQLITE_OK;
}

/*
** Return the currently defined page size
*/
int sqlite3BtreeGetPageSize(Btree *p){
  return p->pBt->pageSize;
}
int sqlite3BtreeGetReserve(Btree *p){
  return p->pBt->pageSize - p->pBt->usableSize;
}
#endif /* !defined(SQLITE_OMIT_PAGER_PRAGMAS) || !defined(SQLITE_OMIT_VACUUM) */

/*
** Change the 'auto-vacuum' property of the database. If the 'autoVacuum'
** parameter is non-zero, then auto-vacuum mode is enabled. If zero, it
** is disabled. The default value for the auto-vacuum property is 
** determined by the SQLITE_DEFAULT_AUTOVACUUM macro.
*/
int sqlite3BtreeSetAutoVacuum(Btree *p, int autoVacuum){
  BtShared *pBt = p->pBt;;
#ifdef SQLITE_OMIT_AUTOVACUUM
  return SQLITE_READONLY;
#else
  if( pBt->pageSizeFixed ){
    return SQLITE_READONLY;
  }
  pBt->autoVacuum = (autoVacuum?1:0);
................................................................................
#endif
}

/*
** Return the value of the 'auto-vacuum' property. If auto-vacuum is 
** enabled 1 is returned. Otherwise 0.
*/
int sqlite3BtreeGetAutoVacuum(Btree *p){
#ifdef SQLITE_OMIT_AUTOVACUUM
  return 0;
#else
  return p->pBt->autoVacuum;
#endif
}


/*
** Get a reference to pPage1 of the database file.  This will
** also acquire a readlock on that file.
................................................................................
**
** SQLITE_OK is returned on success.  If the file is not a
** well-formed database file, then SQLITE_CORRUPT is returned.
** SQLITE_BUSY is returned if the database is locked.  SQLITE_NOMEM
** is returned if we run out of memory.  SQLITE_PROTOCOL is returned
** if there is a locking protocol violation.
*/
static int lockBtree(BtShared *pBt){
  int rc, pageSize;
  MemPage *pPage1;
  if( pBt->pPage1 ) return SQLITE_OK;
  rc = getPage(pBt, 1, &pPage1);
  if( rc!=SQLITE_OK ) return rc;
  

................................................................................
  return rc;
}

/*
** This routine works like lockBtree() except that it also invokes the
** busy callback if there is lock contention.
*/
static int lockBtreeWithRetry(Btree *pRef){
  int rc = SQLITE_OK;
  if( pRef->inTrans==TRANS_NONE ){
    u8 inTransaction = pRef->pBt->inTransaction;
    btreeIntegrity(pRef);
    rc = sqlite3BtreeBeginTrans(pRef, 0);
    pRef->pBt->inTransaction = inTransaction;
    pRef->inTrans = TRANS_NONE;
    if( rc==SQLITE_OK ){
      pRef->pBt->nTransaction--;
    }
    btreeIntegrity(pRef);
  }
  return rc;
}
       

/*
** If there are no outstanding cursors and we are not in the middle
................................................................................
** this routine unrefs the first page of the database file which 
** has the effect of releasing the read lock.
**
** If there are any outstanding cursors, this routine is a no-op.
**
** If there is a transaction in progress, this routine is a no-op.
*/
static void unlockBtreeIfUnused(BtShared *pBt){
  if( pBt->inTransaction==TRANS_NONE && pBt->pCursor==0 && pBt->pPage1!=0 ){
    if( pBt->pPage1->aData==0 ){
      MemPage *pPage = pBt->pPage1;
      pPage->aData = &((u8*)pPage)[-pBt->pageSize];
      pPage->pBt = pBt;
      pPage->pgno = 1;
    }
    releasePage(pBt->pPage1);
................................................................................
  }
}

/*
** Create a new database by initializing the first page of the
** file.
*/
static int newDatabase(BtShared *pBt){
  MemPage *pP1;
  unsigned char *data;
  int rc;
  if( sqlite3pager_pagecount(pBt->pPager)>0 ) return SQLITE_OK;
  pP1 = pBt->pPage1;
  assert( pP1!=0 );
  data = pP1->aData;
................................................................................
** a reserved lock.  B tries to promote to exclusive but is blocked because
** of A's read lock.  A tries to promote to reserved but is blocked by B.
** One or the other of the two processes must give way or there can be
** no progress.  By returning SQLITE_BUSY and not invoking the busy callback
** when A already has a read lock, we encourage A to give up and let B
** proceed.
*/
int sqlite3BtreeBeginTrans(Btree *p, int wrflag){
  BtShared *pBt = p->pBt;
  int rc = SQLITE_OK;

  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) ){
    return SQLITE_OK;
  }

  /* Write transactions are not possible on a read-only database */
  if( pBt->readOnly && wrflag ){
    return SQLITE_READONLY;
  }

  /* If another database handle has already opened a write transaction 
  ** on this shared-btree structure and a second write transaction is
  ** requested, return SQLITE_BUSY.
  */
  if( pBt->inTransaction==TRANS_WRITE && wrflag ){
    return SQLITE_BUSY;
  }

  do {
    if( pBt->pPage1==0 ){
      rc = lockBtree(pBt);
    }
  
    if( rc==SQLITE_OK && wrflag ){
................................................................................
      rc = sqlite3pager_begin(pBt->pPage1->aData, wrflag>1);
      if( rc==SQLITE_OK ){
        rc = newDatabase(pBt);
      }
    }
  
    if( rc==SQLITE_OK ){

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

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

  btreeIntegrity(p);
  return rc;
}

#ifndef SQLITE_OMIT_AUTOVACUUM

/*
** Set the pointer-map entries for all children of page pPage. Also, if
................................................................................
** pPage contains cells that point to overflow pages, set the pointer
** map entries for the overflow pages as well.
*/
static int setChildPtrmaps(MemPage *pPage){
  int i;                             /* Counter variable */
  int nCell;                         /* Number of cells in page pPage */
  int rc = SQLITE_OK;                /* Return code */
  BtShared *pBt = pPage->pBt;
  int isInitOrig = pPage->isInit;
  Pgno pgno = pPage->pgno;

  initPage(pPage, 0);
  nCell = pPage->nCell;

  for(i=0; i<nCell; i++){
................................................................................


/*
** Move the open database page pDbPage to location iFreePage in the 
** database. The pDbPage reference remains valid.
*/
static int relocatePage(
  BtShared *pBt,           /* Btree */
  MemPage *pDbPage,        /* Open page to move */
  u8 eType,                /* Pointer map 'type' entry for pDbPage */
  Pgno iPtrPage,           /* Pointer map 'page-no' entry for pDbPage */
  Pgno iFreePage           /* The location to move pDbPage to */
){
  MemPage *pPtrPage;   /* The page that contains a pointer to pDbPage */
  Pgno iDbPage = pDbPage->pgno;
................................................................................
      rc = ptrmapPut(pBt, iFreePage, eType, iPtrPage);
    }
  }
  return rc;
}

/* Forward declaration required by autoVacuumCommit(). */
static int allocatePage(BtShared *, MemPage **, Pgno *, Pgno, u8);

/*
** This routine is called prior to sqlite3pager_commit when a transaction
** is commited for an auto-vacuum database.
*/
static int autoVacuumCommit(BtShared *pBt, Pgno *nTrunc){
  Pager *pPager = pBt->pPager;
  Pgno nFreeList;   /* Number of pages remaining on the free-list. */
  int nPtrMap;      /* Number of pointer-map pages deallocated */
  Pgno origSize;  /* Pages in the database file */
  Pgno finSize;   /* Pages in the database file after truncation */
  int rc;           /* Return code */
  u8 eType;
................................................................................

/*
** Commit the transaction currently in progress.
**
** This will release the write lock on the database file.  If there
** are no active cursors, it also releases the read lock.
*/
int sqlite3BtreeCommit(Btree *p){
  int rc = SQLITE_OK;
  BtShared *pBt = p->pBt;

  btreeIntegrity(p);
  unlockAllTables(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 ){
    assert( pBt->inTransaction==TRANS_WRITE );
    assert( pBt->nTransaction>0 );
    rc = sqlite3pager_commit(pBt->pPager);
    pBt->inTransaction = TRANS_READ;
    pBt->inStmt = 0;
  }

  /* If the handle has any kind of transaction open, decrement the transaction
  ** count of the shared btree. If the transaction count reaches 0, set
  ** the shared state to TRANS_NONE. The unlockBtreeIfUnused() call below
  ** will unlock the pager.
  */
  if( p->inTrans!=TRANS_NONE ){
    pBt->nTransaction--;
    if( 0==pBt->nTransaction ){
      pBt->inTransaction = TRANS_NONE;
    }
  }

  /* Set the handles current transaction state to TRANS_NONE and unlock
  ** the pager if this call closed the only read or write transaction.
  */
  p->inTrans = TRANS_NONE;

  unlockBtreeIfUnused(pBt);

  btreeIntegrity(p);
  return rc;
}

#ifndef NDEBUG
/*
** Return the number of write-cursors open on this handle. This is for use
** in assert() expressions, so it is only compiled if NDEBUG is not
** defined.
*/
static int countWriteCursors(BtShared *pBt){
  BtCursor *pCur;
  int r = 0;
  for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){
    if( pCur->wrFlag ) r++; 
  }
  return r;
}
#endif

#ifdef SQLITE_TEST
/*
** Print debugging information about all cursors to standard output.
*/
void sqlite3BtreeCursorList(Btree *p){
  BtCursor *pCur;
  BtShared *pBt = p->pBt;
  for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){
    MemPage *pPage = pCur->pPage;
    char *zMode = pCur->wrFlag ? "rw" : "ro";
    sqlite3DebugPrintf("CURSOR %p rooted at %4d(%s) currently at %d.%d%s\n",
       pCur, pCur->pgnoRoot, zMode,
       pPage ? pPage->pgno : 0, pCur->idx,
       pCur->isValid ? "" : " eof"
................................................................................
** invalided by this operation.  Any attempt to use a cursor
** that was open at the beginning of this operation will result
** in an error.
**
** This will release the write lock on the database file.  If there
** are no active cursors, it also releases the read lock.
*/
int sqlite3BtreeRollback(Btree *p){
  int rc = SQLITE_OK;
  BtShared *pBt = p->pBt;
  MemPage *pPage1;

  btreeIntegrity(p);
  unlockAllTables(p);

  if( p->inTrans==TRANS_WRITE ){
    assert( TRANS_WRITE==pBt->inTransaction );

    rc = sqlite3pager_rollback(pBt->pPager);
    /* The rollback may have destroyed the pPage1->aData value.  So
    ** call getPage() on page 1 again to make sure pPage1->aData is
    ** set correctly. */
    if( getPage(pBt, 1, &pPage1)==SQLITE_OK ){
      releasePage(pPage1);
    }
    assert( countWriteCursors(pBt)==0 );
    pBt->inTransaction = TRANS_READ;
  }

  if( p->inTrans!=TRANS_NONE ){
    assert( pBt->nTransaction>0 );
    pBt->nTransaction--;
    if( 0==pBt->nTransaction ){
      pBt->inTransaction = TRANS_NONE;
    }
  }

  p->inTrans = TRANS_NONE;
  pBt->inStmt = 0;
  unlockBtreeIfUnused(pBt);

  btreeIntegrity(p);
  return rc;
}

/*
** Start a statement subtransaction.  The subtransaction can
** can be rolled back independently of the main transaction.
** You must start a transaction before starting a subtransaction.
................................................................................
** to start a new subtransaction if another subtransaction is already active.
**
** Statement subtransactions are used around individual SQL statements
** that are contained within a BEGIN...COMMIT block.  If a constraint
** 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;
  if( (p->inTrans!=TRANS_WRITE) || pBt->inStmt ){
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }
  assert( pBt->inTransaction==TRANS_WRITE );
  rc = pBt->readOnly ? SQLITE_OK : sqlite3pager_stmt_begin(pBt->pPager);
  pBt->inStmt = 1;
  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;
  if( pBt->inStmt && !pBt->readOnly ){
    rc = sqlite3pager_stmt_commit(pBt->pPager);
  }else{
    rc = SQLITE_OK;
  }
  pBt->inStmt = 0;
  return rc;
................................................................................
** Rollback the active statement subtransaction.  If no subtransaction
** is active this routine is a no-op.
**
** All cursors will be invalidated by this operation.  Any attempt
** to use a cursor that was open at the beginning of this operation
** will result in an error.
*/
int sqlite3BtreeRollbackStmt(Btree *p){
  int rc;
  BtShared *pBt = p->pBt;
  if( pBt->inStmt==0 || pBt->readOnly ) return SQLITE_OK;
  rc = sqlite3pager_stmt_rollback(pBt->pPager);
  assert( countWriteCursors(pBt)==0 );
  pBt->inStmt = 0;
  return rc;
}

................................................................................
** The comparison function must be logically the same for every cursor
** on a particular table.  Changing the comparison function will result
** in incorrect operations.  If the comparison function is NULL, a
** default comparison function is used.  The comparison function is
** always ignored for INTKEY tables.
*/
int sqlite3BtreeCursor(
  Btree *p,                                   /* The btree */
  int iTable,                                 /* Root page of table to open */
  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;
  BtCursor *pCur;
  BtShared *pBt = p->pBt;

  *ppCur = 0;
  if( wrFlag ){
    if( pBt->readOnly ){
      return SQLITE_READONLY;
    }
    if( checkReadLocks(pBt, iTable, 0) ){
      return SQLITE_LOCKED;
    }
  }

#ifndef SQLITE_OMIT_SHARED_CACHE
  rc = queryTableLock(p, iTable, wrFlag?WRITE_LOCK:READ_LOCK);
  if( rc!=SQLITE_OK ){
    return rc;
  }
#endif

  if( pBt->pPage1==0 ){
    rc = lockBtreeWithRetry(p);
    if( rc!=SQLITE_OK ){
      return rc;
    }
  }
  pCur = sqliteMallocRaw( sizeof(*pCur) );
  if( pCur==0 ){
    rc = SQLITE_NOMEM;
................................................................................
    rc = SQLITE_EMPTY;
    goto create_cursor_exception;
  }
  rc = getAndInitPage(pBt, pCur->pgnoRoot, &pCur->pPage, 0);
  if( rc!=SQLITE_OK ){
    goto create_cursor_exception;
  }

  /* Obtain the table-lock on the shared-btree. */
  rc = lockTable(p, iTable, wrFlag?WRITE_LOCK:READ_LOCK);
  if( rc!=SQLITE_OK ){
    assert( rc==SQLITE_NOMEM );
    goto create_cursor_exception;
  }

  /* Now that no other errors can occur, finish filling in the BtCursor
  ** variables, link the cursor into the BtShared list and set *ppCur (the
  ** output argument to this function).
  */
  pCur->xCompare = xCmp ? xCmp : dfltCompare;
  pCur->pArg = pArg;
  pCur->pBtree = p;
  pCur->wrFlag = wrFlag;
  pCur->idx = 0;
  memset(&pCur->info, 0, sizeof(pCur->info));
  pCur->pNext = pBt->pCursor;
  if( pCur->pNext ){
    pCur->pNext->pPrev = pCur;
  }
  pCur->pPrev = 0;
  pBt->pCursor = pCur;
  pCur->isValid = 0;
  *ppCur = pCur;


  return SQLITE_OK;
create_cursor_exception:
  if( pCur ){
    releasePage(pCur->pPage);
    sqliteFree(pCur);
  }
  unlockBtreeIfUnused(pBt);
  return rc;
................................................................................
#endif

/*
** 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->pBtree->pBt;
  if( pCur->pPrev ){
    pCur->pPrev->pNext = pCur->pNext;
  }else{
    pBt->pCursor = pCur->pNext;
  }
  if( pCur->pNext ){
    pCur->pNext->pPrev = pCur->pPrev;
................................................................................
  unsigned char *pBuf, /* Write the bytes into this buffer */ 
  int skipKey          /* offset begins at data if this is true */
){
  unsigned char *aPayload;
  Pgno nextPage;
  int rc;
  MemPage *pPage;
  BtShared *pBt;
  int ovflSize;
  u32 nKey;

  assert( pCur!=0 && pCur->pPage!=0 );
  assert( pCur->isValid );
  pBt = pCur->pBtree->pBt;
  pPage = pCur->pPage;
  pageIntegrity(pPage);
  assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
  getCellInfo(pCur);
  aPayload = pCur->info.pCell;
  aPayload += pCur->info.nHeader;
  if( pPage->intKey ){
................................................................................
** Move the cursor down to a new child page.  The newPgno argument is the
** page number of the child page to move to.
*/
static int moveToChild(BtCursor *pCur, u32 newPgno){
  int rc;
  MemPage *pNewPage;
  MemPage *pOldPage;
  BtShared *pBt = pCur->pBtree->pBt;

  assert( pCur->isValid );
  rc = getAndInitPage(pBt, newPgno, &pNewPage, pCur->pPage);
  if( rc ) return rc;
  pageIntegrity(pNewPage);
  pNewPage->idxParent = pCur->idx;
  pOldPage = pCur->pPage;
................................................................................

/*
** Move the cursor to the root page
*/
static int moveToRoot(BtCursor *pCur){
  MemPage *pRoot;
  int rc;
  BtShared *pBt = pCur->pBtree->pBt;

  rc = getAndInitPage(pBt, pCur->pgnoRoot, &pRoot, 0);
  if( rc ){
    pCur->isValid = 0;
    return rc;
  }
  releasePage(pCur->pPage);
................................................................................
** which in turn can make database access faster.
**
** If the "exact" parameter is not 0, and the page-number nearby exists 
** anywhere on the free-list, then it is guarenteed to be returned. This
** is only used by auto-vacuum databases when allocating a new table.
*/
static int allocatePage(
  BtShared *pBt, 
  MemPage **ppPage, 
  Pgno *pPgno, 
  Pgno nearby,
  u8 exact
){
  MemPage *pPage1;
  int rc;
................................................................................

/*
** Add a page of the database file to the freelist.
**
** sqlite3pager_unref() is NOT called for pPage.
*/
static int freePage(MemPage *pPage){
  BtShared *pBt = pPage->pBt;
  MemPage *pPage1 = pBt->pPage1;
  int rc, n, k;

  /* Prepare the page for freeing */
  assert( pPage->pgno>1 );
  pPage->isInit = 0;
  releasePage(pPage->pParent);
................................................................................
  return rc;
}

/*
** Free any overflow pages associated with the given Cell.
*/
static int clearCell(MemPage *pPage, unsigned char *pCell){
  BtShared *pBt = pPage->pBt;
  CellInfo info;
  Pgno ovflPgno;
  int rc;

  parseCellPtr(pPage, pCell, &info);
  if( info.iOverflow==0 ){
    return SQLITE_OK;  /* No overflow pages. Return without doing anything */
................................................................................
  const u8 *pSrc;
  int nSrc, n, rc;
  int spaceLeft;
  MemPage *pOvfl = 0;
  MemPage *pToRelease = 0;
  unsigned char *pPrior;
  unsigned char *pPayload;
  BtShared *pBt = pPage->pBt;
  Pgno pgnoOvfl = 0;
  int nHeader;
  CellInfo info;

  /* Fill in the header. */
  nHeader = 0;
  if( !pPage->leaf ){
................................................................................
}

/*
** Change the MemPage.pParent pointer on the page whose number is
** given in the second argument so that MemPage.pParent holds the
** pointer in the third argument.
*/
static int reparentPage(BtShared *pBt, Pgno pgno, MemPage *pNewParent, int idx){
  MemPage *pThis;
  unsigned char *aData;

  if( pgno==0 ) return SQLITE_OK;
  assert( pBt->pPager!=0 );
  aData = sqlite3pager_lookup(pBt->pPager, pgno);
  if( aData ){
................................................................................
** to make sure that each child knows that pPage is its parent.
**
** This routine gets called after you memcpy() one page into
** another.
*/
static int reparentChildPages(MemPage *pPage){
  int i;
  BtShared *pBt = pPage->pBt;
  int rc = SQLITE_OK;

  if( pPage->leaf ) return SQLITE_OK;

  for(i=0; i<pPage->nCell; i++){
    u8 *pCell = findCell(pPage, i);
    if( !pPage->leaf ){
................................................................................
static int balance_quick(MemPage *pPage, MemPage *pParent){
  int rc;
  MemPage *pNew;
  Pgno pgnoNew;
  u8 *pCell;
  int szCell;
  CellInfo info;
  BtShared *pBt = pPage->pBt;
  int parentIdx = pParent->nCell;   /* pParent new divider cell index */
  int parentSize;                   /* Size of new divider cell */
  u8 parentCell[64];                /* Space for the new divider cell */

  /* Allocate a new page. Insert the overflow cell from pPage
  ** into it. Then remove the overflow cell from pPage.
  */
................................................................................
**
** If this routine fails for any reason, it might leave the database
** in a corrupted state.  So if this routine fails, the database should
** be rolled back.
*/
static int balance_nonroot(MemPage *pPage){
  MemPage *pParent;            /* The parent of pPage */
  BtShared *pBt;                  /* The whole database */
  int nCell = 0;               /* Number of cells in apCell[] */
  int nMaxCells = 0;           /* Allocated size of apCell, szCell, aFrom. */
  int nOld;                    /* Number of pages in apOld[] */
  int nNew;                    /* Number of pages in apNew[] */
  int nDiv;                    /* Number of cells in apDiv[] */
  int i, j, k;                 /* Loop counters */
  int idx;                     /* Index of pPage in pParent->aCell[] */
................................................................................
** page contains no cells.  This is an opportunity to make the tree
** shallower by one level.
*/
static int balance_shallower(MemPage *pPage){
  MemPage *pChild;             /* The only child page of pPage */
  Pgno pgnoChild;              /* Page number for pChild */
  int rc = SQLITE_OK;          /* Return code from subprocedures */
  BtShared *pBt;                  /* The main BTree structure */
  int mxCellPerPage;           /* Maximum number of cells per page */
  u8 **apCell;                 /* All cells from pages being balanced */
  int *szCell;                 /* Local size of all cells */

  assert( pPage->pParent==0 );
  assert( pPage->nCell==0 );
  pBt = pPage->pBt;
................................................................................
** child.   Finally, call balance_internal() on the new child
** to cause it to split.
*/
static int balance_deeper(MemPage *pPage){
  int rc;             /* Return value from subprocedures */
  MemPage *pChild;    /* Pointer to a new child page */
  Pgno pgnoChild;     /* Page number of the new child page */
  BtShared *pBt;         /* The BTree */
  int usableSize;     /* Total usable size of a page */
  u8 *data;           /* Content of the parent page */
  u8 *cdata;          /* Content of the child page */
  int hdr;            /* Offset to page header in parent */
  int brk;            /* Offset to content of first cell in parent */

  assert( pPage->pParent==0 );
................................................................................
** means a cursor opened with wrFlag==0) this routine also moves
** all cursors other than pExclude so that they are pointing to the 
** first Cell on root page.  This is necessary because an insert 
** 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(BtShared *pBt, Pgno pgnoRoot, BtCursor *pExclude){
  BtCursor *p;
  for(p=pBt->pCursor; p; p=p->pNext){
    if( p->pgnoRoot!=pgnoRoot || p==pExclude ) continue;
    if( p->wrFlag==0 ) return SQLITE_LOCKED;
    if( p->pPage->pgno!=p->pgnoRoot ){
      moveToRoot(p);
    }
................................................................................
  const void *pKey, i64 nKey,    /* The key of the new record */
  const void *pData, int nData   /* The data of the new record */
){
  int rc;
  int loc;
  int szNew;
  MemPage *pPage;
  BtShared *pBt = pCur->pBtree->pBt;
  unsigned char *oldCell;
  unsigned char *newCell = 0;

  if( pBt->inTransaction!=TRANS_WRITE ){
    /* Must start a transaction before doing an insert */
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }
  assert( !pBt->readOnly );
  if( !pCur->wrFlag ){
    return SQLITE_PERM;   /* Cursor not open for writing */
  }
................................................................................
** is left pointing at a random location.
*/
int sqlite3BtreeDelete(BtCursor *pCur){
  MemPage *pPage = pCur->pPage;
  unsigned char *pCell;
  int rc;
  Pgno pgnoChild = 0;
  BtShared *pBt = pCur->pBtree->pBt;

  assert( pPage->isInit );
  if( pBt->inTransaction!=TRANS_WRITE ){
    /* Must start a transaction before doing a delete */
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }
  assert( !pBt->readOnly );
  if( pCur->idx >= pPage->nCell ){
    return SQLITE_ERROR;  /* The cursor is not pointing to anything */
  }
................................................................................
** The type of type is determined by the flags parameter.  Only the
** following values of flags are currently in use.  Other values for
** flags might not work:
**
**     BTREE_INTKEY|BTREE_LEAFDATA     Used for SQL tables with rowid keys
**     BTREE_ZERODATA                  Used for SQL indices
*/
int sqlite3BtreeCreateTable(Btree *p, int *piTable, int flags){
  BtShared *pBt = p->pBt;
  MemPage *pRoot;
  Pgno pgnoRoot;
  int rc;
  if( pBt->inTransaction!=TRANS_WRITE ){
    /* Must start a transaction first */
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }
  assert( !pBt->readOnly );

  /* It is illegal to create a table if any cursors are open on the
  ** database. This is because in auto-vacuum mode the backend may
................................................................................
    Pgno pgnoMove;      /* Move a page here to make room for the root-page */
    MemPage *pPageMove; /* The page to move to. */

    /* Read the value of meta[3] from the database to determine where the
    ** root page of the new table should go. meta[3] is the largest root-page
    ** created so far, so the new root-page is (meta[3]+1).
    */
    rc = sqlite3BtreeGetMeta(p, 4, &pgnoRoot);
    if( rc!=SQLITE_OK ) return rc;
    pgnoRoot++;

    /* The new root-page may not be allocated on a pointer-map page, or the
    ** PENDING_BYTE page.
    */
    if( pgnoRoot==PTRMAP_PAGENO(pBt->usableSize, pgnoRoot) ||
................................................................................

    /* Update the pointer-map and meta-data with the new root-page number. */
    rc = ptrmapPut(pBt, pgnoRoot, PTRMAP_ROOTPAGE, 0);
    if( rc ){
      releasePage(pRoot);
      return rc;
    }
    rc = sqlite3BtreeUpdateMeta(p, 4, pgnoRoot);
    if( rc ){
      releasePage(pRoot);
      return rc;
    }

  }else{
    rc = allocatePage(pBt, &pRoot, &pgnoRoot, 1, 0);
................................................................................
}

/*
** Erase the given database page and all its children.  Return
** the page to the freelist.
*/
static int clearDatabasePage(
  BtShared *pBt,           /* The BTree that contains the table */
  Pgno pgno,            /* Page number to clear */
  MemPage *pParent,     /* Parent page.  NULL for the root */
  int freePageFlag      /* Deallocate page if true */
){
  MemPage *pPage = 0;
  int rc;
  unsigned char *pCell;
................................................................................
** the page number of the root of the table.  After this routine returns,
** the root page is empty, but still exists.
**
** This routine will fail with SQLITE_LOCKED if there are any open
** read cursors on the table.  Open write cursors are moved to the
** root of the table.
*/
int sqlite3BtreeClearTable(Btree *p, int iTable){
  int rc;
  BtCursor *pCur;
  BtShared *pBt = p->pBt;
  if( p->inTrans!=TRANS_WRITE ){
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }
  for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){
    if( pCur->pgnoRoot==(Pgno)iTable ){
      if( pCur->wrFlag==0 ) return SQLITE_LOCKED;
      moveToRoot(pCur);
    }
................................................................................
** root pages are kept at the beginning of the database file, which
** is necessary for AUTOVACUUM to work right.  *piMoved is set to the 
** page number that used to be the last root page in the file before
** the move.  If no page gets moved, *piMoved is set to 0.
** The last root page is recorded in meta[3] and the value of
** meta[3] is updated by this procedure.
*/
int sqlite3BtreeDropTable(Btree *p, int iTable, int *piMoved){
  int rc;
  MemPage *pPage = 0;
  BtShared *pBt = p->pBt;

  if( p->inTrans!=TRANS_WRITE ){
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }

  /* It is illegal to drop a table if any cursors are open on the
  ** database. This is because in auto-vacuum mode the backend may
  ** need to move another root-page to fill a gap left by the deleted
  ** root page. If an open cursor was using this page a problem would 
................................................................................
  */
  if( pBt->pCursor ){
    return SQLITE_LOCKED;
  }

  rc = getPage(pBt, (Pgno)iTable, &pPage);
  if( rc ) return rc;
  rc = sqlite3BtreeClearTable(p, iTable);
  if( rc ){
    releasePage(pPage);
    return rc;
  }

  *piMoved = 0;

................................................................................
  if( iTable>1 ){
#ifdef SQLITE_OMIT_AUTOVACUUM
    rc = freePage(pPage);
    releasePage(pPage);
#else
    if( pBt->autoVacuum ){
      Pgno maxRootPgno;
      rc = sqlite3BtreeGetMeta(p, 4, &maxRootPgno);
      if( rc!=SQLITE_OK ){
        releasePage(pPage);
        return rc;
      }

      if( iTable==maxRootPgno ){
        /* If the table being dropped is the table with the largest root-page
................................................................................
        maxRootPgno--;
      }
      if( maxRootPgno==PTRMAP_PAGENO(pBt->usableSize, maxRootPgno) ){
        maxRootPgno--;
      }
      assert( maxRootPgno!=PENDING_BYTE_PAGE(pBt) );

      rc = sqlite3BtreeUpdateMeta(p, 4, maxRootPgno);
    }else{
      rc = freePage(pPage);
      releasePage(pPage);
    }
#endif
  }else{
    /* If sqlite3BtreeDropTable was called on page 1. */
................................................................................
** through meta[15] are available for use by higher layers.  Meta[0]
** is read-only, the others are read/write.
** 
** The schema layer numbers meta values differently.  At the schema
** layer (and the SetCookie and ReadCookie opcodes) the number of
** free pages is not visible.  So Cookie[0] is the same as Meta[1].
*/
int sqlite3BtreeGetMeta(Btree *p, int idx, u32 *pMeta){
  int rc;
  unsigned char *pP1;
  BtShared *pBt = p->pBt;

  assert( idx>=0 && idx<=15 );
  rc = sqlite3pager_get(pBt->pPager, 1, (void**)&pP1);
  if( rc ) return rc;
  *pMeta = get4byte(&pP1[36 + idx*4]);
  sqlite3pager_unref(pP1);

................................................................................
  return SQLITE_OK;
}

/*
** Write meta-information back into the database.  Meta[0] is
** read-only and may not be written.
*/
int sqlite3BtreeUpdateMeta(Btree *p, int idx, u32 iMeta){
  BtShared *pBt = p->pBt;
  unsigned char *pP1;
  int rc;
  assert( idx>=1 && idx<=15 );
  if( p->inTrans!=TRANS_WRITE ){
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }
  assert( pBt->pPage1!=0 );
  pP1 = pBt->pPage1->aData;
  rc = sqlite3pager_write(pP1);
  if( rc ) return rc;
  put4byte(&pP1[36 + idx*4], iMeta);
................................................................................
}

#ifdef SQLITE_DEBUG
/*
** Print a disassembly of the given page on standard output.  This routine
** is used for debugging and testing only.
*/
static int btreePageDump(BtShared *pBt, int pgno, int recursive, MemPage *pParent){
  int rc;
  MemPage *pPage;
  int i, j, c;
  int nFree;
  u16 idx;
  int hdr;
  int nCell;
................................................................................
    btreePageDump(pBt, get4byte(&data[hdr+8]), 1, pPage);
  }
  pPage->isInit = isInit;
  sqlite3pager_unref(data);
  fflush(stdout);
  return SQLITE_OK;
}
int sqlite3BtreePageDump(Btree *p, int pgno, int recursive){
  return btreePageDump(p->pBt, pgno, recursive, 0);
}
#endif

#ifdef SQLITE_TEST
/*
** Fill aResult[] with information about the entry and page that the
** cursor is pointing to.
................................................................................
}
#endif

/*
** Return the pager associated with a BTree.  This routine is used for
** testing and debugging only.
*/
Pager *sqlite3BtreePager(Btree *p){
  return p->pBt->pPager;
}

/*
** This structure is passed around through all the sanity checking routines
** in order to keep track of some global state information.
*/
typedef struct IntegrityCk IntegrityCk;
struct IntegrityCk {
  BtShared *pBt;    /* The tree being checked out */
  Pager *pPager; /* The associated pager.  Also accessible by pBt->pPager */
  int nPage;     /* Number of pages in the database */
  int *anRef;    /* Number of times each page is referenced */
  char *zErrMsg; /* An error message.  NULL of no errors seen. */
};

#ifndef SQLITE_OMIT_INTEGRITY_CHECK
................................................................................
  int nUpper            /* Number of characters in zUpperBound */
){
  MemPage *pPage;
  int i, rc, depth, d2, pgno, cnt;
  int hdr, cellStart;
  int nCell;
  u8 *data;
  BtShared *pBt;
  int usableSize;
  char zContext[100];
  char *hit;

  sprintf(zContext, "Page %d: ", iPage);

  /* Check that the page exists
................................................................................
** a table.  nRoot is the number of entries in aRoot.
**
** If everything checks out, this routine returns NULL.  If something is
** amiss, an error message is written into memory obtained from malloc()
** and a pointer to that error message is returned.  The calling function
** is responsible for freeing the error message when it is done.
*/
char *sqlite3BtreeIntegrityCheck(Btree *p, int *aRoot, int nRoot){
  int i;
  int nRef;
  IntegrityCk sCheck;
  BtShared *pBt = p->pBt;

  nRef = *sqlite3pager_stats(pBt->pPager);
  if( lockBtreeWithRetry(p)!=SQLITE_OK ){
    return sqliteStrDup("Unable to acquire a read lock on the database");
  }
  sCheck.pBt = pBt;
  sCheck.pPager = pBt->pPager;
  sCheck.nPage = sqlite3pager_pagecount(sCheck.pPager);
  if( sCheck.nPage==0 ){
    unlockBtreeIfUnused(pBt);
................................................................................
  return sCheck.zErrMsg;
}
#endif /* SQLITE_OMIT_INTEGRITY_CHECK */

/*
** Return the full pathname of the underlying database file.
*/
const char *sqlite3BtreeGetFilename(Btree *p){
  assert( p->pBt->pPager!=0 );
  return sqlite3pager_filename(p->pBt->pPager);
}

/*
** Return the pathname of the directory that contains the database file.
*/
const char *sqlite3BtreeGetDirname(Btree *p){
  assert( p->pBt->pPager!=0 );
  return sqlite3pager_dirname(p->pBt->pPager);
}

/*
** Return the pathname of the journal file for this database. The return
** value of this routine is the same regardless of whether the journal file
** has been created or not.
*/
const char *sqlite3BtreeGetJournalname(Btree *p){
  assert( p->pBt->pPager!=0 );
  return sqlite3pager_journalname(p->pBt->pPager);
}

#ifndef SQLITE_OMIT_VACUUM
/*
** Copy the complete content of pBtFrom into pBtTo.  A transaction
** must be active for both files.
**
** The size of file pBtFrom may be reduced by this operation.
** If anything goes wrong, the transaction on pBtFrom is rolled back.
*/
int sqlite3BtreeCopyFile(Btree *pTo, Btree *pFrom){
  int rc = SQLITE_OK;
  Pgno i, nPage, nToPage, iSkip;

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

  if( pTo->inTrans!=TRANS_WRITE || pFrom->inTrans!=TRANS_WRITE ){
    return SQLITE_ERROR;
  }
  if( pBtTo->pCursor ) return SQLITE_BUSY;
  nToPage = sqlite3pager_pagecount(pBtTo->pPager);
  nPage = sqlite3pager_pagecount(pBtFrom->pPager);
  iSkip = PENDING_BYTE_PAGE(pBtTo);
  for(i=1; rc==SQLITE_OK && i<=nPage; i++){
................................................................................
    sqlite3pager_unref(pPage);
    sqlite3pager_dont_write(pBtTo->pPager, i);
  }
  if( !rc && nPage<nToPage ){
    rc = sqlite3pager_truncate(pBtTo->pPager, nPage);
  }
  if( rc ){
    sqlite3BtreeRollback(pTo);
  }
  return rc;  
}
#endif /* SQLITE_OMIT_VACUUM */

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

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

/*
** This call is a no-op if no write-transaction is currently active on pBt.
**
** Otherwise, sync the database file for the btree pBt. zMaster points to
** the name of a master journal file that should be written into the
................................................................................
**
** When this is called, the master journal should already have been
** created, populated with this journal pointer and synced to disk.
**
** Once this is routine has returned, the only thing required to commit
** the write-transaction for this database file is to delete the journal.
*/
int sqlite3BtreeSync(Btree *p, const char *zMaster){
  if( p->inTrans==TRANS_WRITE ){
    BtShared *pBt = p->pBt;
#ifndef SQLITE_OMIT_AUTOVACUUM
    Pgno nTrunc = 0;
    if( pBt->autoVacuum ){
      int rc = autoVacuumCommit(pBt, &nTrunc); 
      if( rc!=SQLITE_OK ) return rc;
    }
    return sqlite3pager_sync(pBt->pPager, zMaster, nTrunc);
#endif
    return sqlite3pager_sync(pBt->pPager, zMaster, 0);
  }
  return SQLITE_OK;
}

#ifndef SQLITE_OMIT_SHARED_CACHE
/*
** Enable the shared pager and schema features.
*/
int sqlite3_enable_shared_cache(int enable){
  SqliteTsd *pTsd = sqlite3Tsd();
  if( pTsd->pPager ){
    return SQLITE_MISUSE;
  }
  pTsd->useSharedData = enable;
  return SQLITE_OK;
}
#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.65 2005/12/16 15:24:29 danielk1977 Exp $
*/
#ifndef _BTREE_H_
#define _BTREE_H_

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

/*
** Forward declarations of structure
*/
typedef struct Btree Btree;
typedef struct BtCursor BtCursor;



int sqlite3BtreeOpen(
  const char *zFilename,   /* Name of database file to open */

  Btree **,                /* Return open Btree* here */
  int flags                /* Flags */
);

/* The flags parameter to sqlite3BtreeOpen can be the bitwise or of the
** following values.
**

**    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.66 2005/12/30 16:28:02 danielk1977 Exp $
*/
#ifndef _BTREE_H_
#define _BTREE_H_

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

/*
** Forward declarations of structure
*/
typedef struct Btree Btree;
typedef struct BtCursor BtCursor;
typedef struct BtShared BtShared;


int sqlite3BtreeOpen(
  const char *zFilename,   /* Name of database file to open */
  sqlite3 *db,             /* Associated database connection */
  Btree **,                /* Return open Btree* here */
  int flags                /* Flags */
);

/* The flags parameter to sqlite3BtreeOpen can be the bitwise or of the
** following values.
**

**
*************************************************************************
** 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.312 2005/12/16 15:24:29 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include "os.h"
#include <ctype.h>

/*
** The following constant value is used by the SQLITE_BIGENDIAN and
** SQLITE_LITTLEENDIAN macros.
*/
const int sqlite3one = 1;

#ifndef SQLITE_OMIT_GLOBALRECOVER
/*
** Linked list of all open database handles. This is used by the 
** sqlite3_global_recover() function. Entries are added to the list
** by openDatabase() and removed by sqlite3_close().
*/
static sqlite3 *pDbList = 0;
#endif

/*
** The version of the library
*/
const char rcsid3[] = "@(#) \044Id: SQLite version " SQLITE_VERSION " $";
const char sqlite3_version[] = SQLITE_VERSION;
const char *sqlite3_libversion(void){ return sqlite3_version; }
int sqlite3_libversion_number(void){ return SQLITE_VERSION_NUMBER; }
................................................................................
#endif
#if TEMP_STORE==3
    zFilename = ":memory:";
#endif
#endif /* SQLITE_OMIT_MEMORYDB */
  }

  rc = sqlite3BtreeOpen(zFilename, ppBtree, btree_flags);
  if( rc==SQLITE_OK ){
    sqlite3BtreeSetBusyHandler(*ppBtree, (void*)&db->busyHandler);
    sqlite3BtreeSetCacheSize(*ppBtree, nCache);
  }
  return rc;
}

**
*************************************************************************
** 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.313 2005/12/30 16:28:02 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include "os.h"
#include <ctype.h>

/*
** The following constant value is used by the SQLITE_BIGENDIAN and
** SQLITE_LITTLEENDIAN macros.
*/
const int sqlite3one = 1;










/*
** The version of the library
*/
const char rcsid3[] = "@(#) \044Id: SQLite version " SQLITE_VERSION " $";
const char sqlite3_version[] = SQLITE_VERSION;
const char *sqlite3_libversion(void){ return sqlite3_version; }
int sqlite3_libversion_number(void){ return SQLITE_VERSION_NUMBER; }
................................................................................
#endif
#if TEMP_STORE==3
    zFilename = ":memory:";
#endif
#endif /* SQLITE_OMIT_MEMORYDB */
  }

  rc = sqlite3BtreeOpen(zFilename, db, ppBtree, btree_flags);
  if( rc==SQLITE_OK ){
    sqlite3BtreeSetBusyHandler(*ppBtree, (void*)&db->busyHandler);
    sqlite3BtreeSetCacheSize(*ppBtree, nCache);
  }
  return rc;
}

** 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.228 2005/12/20 09:19:37 danielk1977 Exp $
*/
#ifndef SQLITE_OMIT_DISKIO
#include "sqliteInt.h"
#include "os.h"
#include "pager.h"
#include <assert.h>
#include <string.h>
................................................................................
# define TEST_INCR(x)  x++
#else
# define TEST_INCR(x)
#endif

/*
** These are bits that can be set in Pager.errMask.

























*/
#define PAGER_ERR_FULL     0x01  /* a write() failed */
#define PAGER_ERR_MEM      0x02  /* malloc() failed */
#define PAGER_ERR_LOCK     0x04  /* error in the locking protocol */
#define PAGER_ERR_CORRUPT  0x08  /* database or journal corruption */
#define PAGER_ERR_DISK     0x10  /* general disk I/O error - bad hard drive? */

/*
** Journal files begin with the following magic string.  The data
** was obtained from /dev/random.  It is used only as a sanity check.
**
** Since version 2.8.0, the journal format contains additional sanity
** checking information.  If the power fails while the journal is begin
................................................................................
** return code.
*/
static int pager_errcode(Pager *pPager){
  int rc = SQLITE_OK;
  if( pPager->errMask & PAGER_ERR_LOCK )    rc = SQLITE_PROTOCOL;
  if( pPager->errMask & PAGER_ERR_DISK )    rc = SQLITE_IOERR;
  if( pPager->errMask & PAGER_ERR_FULL )    rc = SQLITE_FULL;
  if( pPager->errMask & PAGER_ERR_MEM )     rc = SQLITE_NOMEM;
  if( pPager->errMask & PAGER_ERR_CORRUPT ) rc = SQLITE_CORRUPT;
  return rc;
}























#ifdef SQLITE_CHECK_PAGES
/*
** Return a 32-bit hash of the page data for pPage.
*/
static u32 pager_pagehash(PgHdr *pPage){
  u32 hash = 0;
................................................................................
** + N bytes: length of master journal name.
** + 4 bytes: N
** + 4 bytes: Master journal name checksum.
** + 8 bytes: aJournalMagic[].
**
** The master journal page checksum is the sum of the bytes in the master
** journal name.



*/
static int writeMasterJournal(Pager *pPager, const char *zMaster){
  int rc;
  int len; 
  int i; 
  u32 cksum = 0; 

................................................................................
  }
  sqlite3OsUnlock(pPager->fd, NO_LOCK);
  pPager->state = PAGER_UNLOCK;
  pPager->dbSize = -1;
  pPager->nRef = 0;
  assert( pPager->journalOpen==0 );
}

/*
** This function is used to reset the pager after a malloc() failure. This
** doesn't work with in-memory databases. If a malloc() fails when an 
** in-memory database is in use it is not possible to recover.
**
** If a transaction or statement transaction is active, it is rolled back.
**
** It is an error to call this function if any pages are in use.
*/
#ifndef SQLITE_OMIT_GLOBALRECOVER
int sqlite3pager_reset(Pager *pPager){
  if( pPager ){
    if( pPager->nRef || MEMDB ){
      return SQLITE_ERROR;
    }
    pPager->errMask &= ~(PAGER_ERR_MEM);
    pager_reset(pPager);
  }
  return SQLITE_OK;
}
#endif


/*
** When this routine is called, the pager has the journal file open and
** a RESERVED or EXCLUSIVE lock on the database.  This routine releases
** the database lock and acquires a SHARED lock in its place.  The journal
** file is deleted and closed.
**
................................................................................
*/
int sqlite3pager_open(
  Pager **ppPager,         /* Return the Pager structure here */
  const char *zFilename,   /* Name of the database file to open */
  int nExtra,              /* Extra bytes append to each in-memory page */
  int flags                /* flags controlling this file */
){
  Pager *pPager;
  char *zFullPathname = 0;
  int nameLen;
  OsFile *fd;
  int rc = SQLITE_OK;
  int i;
  int tempFile = 0;
  int memDb = 0;
  int readOnly = 0;
  int useJournal = (flags & PAGER_OMIT_JOURNAL)==0;
  int noReadlock = (flags & PAGER_NO_READLOCK)!=0;
  char zTemp[SQLITE_TEMPNAME_SIZE];
  SqliteTsd *pTsd = sqlite3Tsd();





  *ppPager = 0;
  memset(&fd, 0, sizeof(fd));
  if( sqlite3Tsd()->mallocFailed ){
    return SQLITE_NOMEM;
  }





  if( zFilename && zFilename[0] ){
#ifndef SQLITE_OMIT_MEMORYDB
    if( strcmp(zFilename,":memory:")==0 ){
      memDb = 1;
      zFullPathname = sqliteStrDup("");
      rc = SQLITE_OK;
    }else
#endif
    {
      zFullPathname = sqlite3Os.xFullPathname(zFilename);
      if( zFullPathname ){
        rc = sqlite3Os.xOpenReadWrite(zFullPathname, &fd, &readOnly);
      }
................................................................................
    rc = sqlite3pager_opentemp(zTemp, &fd);
    zFilename = zTemp;
    zFullPathname = sqlite3Os.xFullPathname(zFilename);
    if( rc==SQLITE_OK ){
      tempFile = 1;
    }
  }
  if( !zFullPathname ){
    sqlite3OsClose(&fd);
    return SQLITE_NOMEM;
  }
  if( rc!=SQLITE_OK ){
    sqlite3OsClose(&fd);




    sqliteFree(zFullPathname);
    return rc;
  }
  nameLen = strlen(zFullPathname);
  pPager = sqliteMalloc( sizeof(*pPager) + nameLen*3 + 30 );



  if( pPager==0 ){




    sqlite3OsClose(&fd);
    sqliteFree(zFullPathname);

    return SQLITE_NOMEM;
  }

  TRACE3("OPEN %d %s\n", FILEHANDLEID(fd), zFullPathname);
  pPager->zFilename = (char*)&pPager[1];
  pPager->zDirectory = &pPager->zFilename[nameLen+1];
  pPager->zJournal = &pPager->zDirectory[nameLen+1];
  strcpy(pPager->zFilename, zFullPathname);
  strcpy(pPager->zDirectory, zFullPathname);

  for(i=nameLen; i>0 && pPager->zDirectory[i-1]!='/'; i--){}
  if( i>0 ) pPager->zDirectory[i-1] = 0;
  strcpy(pPager->zJournal, zFullPathname);
  sqliteFree(zFullPathname);
  strcpy(&pPager->zJournal[nameLen], "-journal");
  pPager->fd = fd;
  pPager->journalOpen = 0;
................................................................................
# define clear_simulated_io_error()
# define disable_simulated_io_errors()
# define enable_simulated_io_errors()
#endif

/*
** Read the first N bytes from the beginning of the file into memory
** that pDest points to.  No error checking is done.






*/
void sqlite3pager_read_fileheader(Pager *pPager, int N, unsigned char *pDest){
  memset(pDest, 0, N);
  if( MEMDB==0 ){
    sqlite3OsSeek(pPager->fd, 0);
    sqlite3OsRead(pPager->fd, pDest, N);
    clear_simulated_io_error();
................................................................................
** Shutdown the page cache.  Free all memory and close all files.
**
** If a transaction was in progress when this routine is called, that
** transaction is rolled back.  All outstanding pages are invalidated
** and their memory is freed.  Any attempt to use a page associated
** with this page cache after this function returns will likely
** result in a coredump.





*/
int sqlite3pager_close(Pager *pPager){
  PgHdr *pPg, *pNext;
#ifndef SQLITE_OMIT_MEMORY_MANAGEMENT
  SqliteTsd *pTsd = sqlite3Tsd();
#endif

................................................................................
  /* Temp files are automatically deleted by the OS
  ** if( pPager->tempFile ){
  **   sqlite3Os.xDelete(pPager->zFilename);
  ** }
  */

#ifndef SQLITE_OMIT_MEMORY_MANAGEMENT



  if( pPager==pTsd->pPager ){
    pTsd->pPager = pPager->pNext;
  }else{
    Pager *pTmp;
    for(pTmp = pTsd->pPager; pTmp->pNext!=pPager; pTmp=pTmp->pNext);
    pTmp->pNext = pPager->pNext;
  }
................................................................................
    return 0;
  }else{
    return 1;
  }
}

/*
** Try to find a page in the cache that can be recycled.



*/
static int pager_recycle(Pager *pPager, int syncOk, PgHdr **ppPg){
  PgHdr *pPg;
  *ppPg = 0;

  /* Find a page to recycle.  Try to locate a page that does not
  ** require us to do an fsync() on the journal.
................................................................................
  ** on the journal file then fsync the journal file.  This is a
  ** very slow operation, so we work hard to avoid it.  But sometimes
  ** it can't be helped.
  */
  if( pPg==0 && pPager->pFirst && syncOk && !MEMDB){
    int rc = syncJournal(pPager);
    if( rc!=0 ){
      sqlite3pager_rollback(pPager);
      return SQLITE_IOERR;
    }
    if( pPager->fullSync ){
      /* If in full-sync mode, write a new journal header into the
      ** journal file. This is done to avoid ever modifying a journal
      ** header that is involved in the rollback of pages that have
      ** already been written to the database (in case the header is
      ** trashed when the nRec field is updated).
      */
      pPager->nRec = 0;
      assert( pPager->journalOff > 0 );
      rc = writeJournalHdr(pPager);
      if( rc!=0 ){
        sqlite3pager_rollback(pPager);
        return SQLITE_IOERR;
      }
    }
    pPg = pPager->pFirst;
  }
  if( pPg==0 ){
    return SQLITE_OK;
  }
................................................................................
  */
  if( pPg->dirty ){
    int rc;
    assert( pPg->needSync==0 );
    pPg->pDirty = 0;
    rc = pager_write_pagelist( pPg );
    if( rc!=SQLITE_OK ){
      sqlite3pager_rollback(pPager);
      return SQLITE_IOERR;
    }
  }
  assert( pPg->dirty==0 );

  /* If the page we are recycling is marked as alwaysRollback, then
  ** set the global alwaysRollback flag, thus disabling the
  ** sqlite_dont_rollback() optimization for the rest of this transaction.
................................................................................
      int rc;

      /* For each pager, try to free as many pages as possible (without 
      ** calling fsync() if this is the first iteration of the outermost 
      ** loop).
      */
      while( SQLITE_OK==(rc = pager_recycle(p, i, &pPg)) && pPg) {
	/* 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.
        **
        ** Todo: Check the Pager.pStmt list to make sure this is Ok. It 
        ** probably is though.
        */
        PgHdr *pTmp;
        assert( pPg );

        if( pPg==p->pAll ){
           p->pAll = pPg->pNextAll;
        }else{
          for( pTmp=p->pAll; pTmp->pNextAll!=pPg; pTmp=pTmp->pNextAll );
          pTmp->pNextAll = pPg->pNextAll;
        }
        nReleased += sqliteAllocSize(pPg);
        sqliteFree(pPg);
      }

      if( rc!=SQLITE_OK ){
        /* Assert that fsync() was enabled and the error was an io-error
        ** or a full database. Nothing else should be able to wrong in 
        ** pager_recycle.
        */
        assert( i && (rc==SQLITE_IOERR || rc==SQLITE_FULL) );

        /* TODO: Figure out what to do about this. The IO-error
        ** belongs to the connection that is executing a transaction. 
        */
        assert(0);
      }
    }
  }
  
  return nReleased;
}
#endif

/*
** Acquire a page.
**
** A read lock on the disk file is obtained when the first page is acquired. 
** This read lock is dropped when the last page is released.
**
................................................................................
  /* If this is the first page accessed, then get a SHARED lock
  ** on the database file.
  */
  if( pPager->nRef==0 && !MEMDB ){
    if( !pPager->noReadlock ){
      rc = pager_wait_on_lock(pPager, SHARED_LOCK);
      if( rc!=SQLITE_OK ){
        return rc;
      }
    }

    /* If a journal file exists, and there is no RESERVED lock on the
    ** database file, then it either needs to be played back or deleted.
    */
    if( hasHotJournal(pPager) ){
................................................................................
       ** second process will get to this point in the code and fail to
       ** obtain it's own EXCLUSIVE lock on the database file.
       */
       rc = sqlite3OsLock(pPager->fd, EXCLUSIVE_LOCK);
       if( rc!=SQLITE_OK ){
         sqlite3OsUnlock(pPager->fd, NO_LOCK);
         pPager->state = PAGER_UNLOCK;
         return rc;
       }
       pPager->state = PAGER_EXCLUSIVE;

       /* Open the journal for reading only.  Return SQLITE_BUSY if
       ** we are unable to open the journal file. 
       **
       ** The journal file does not need to be locked itself.  The
................................................................................
       pPager->journalHdr = 0;

       /* Playback and delete the journal.  Drop the database write
       ** lock and reacquire the read lock.
       */
       rc = pager_playback(pPager);
       if( rc!=SQLITE_OK ){
         return rc;
       }
    }
    pPg = 0;
  }else{
    /* Search for page in cache */
    pPg = pager_lookup(pPager, pgno);
    if( MEMDB && pPager->state==PAGER_UNLOCK ){
................................................................................
    TEST_INCR(pPager->nMiss);
    if( pPager->nPage<pPager->mxPage || pPager->pFirst==0 || MEMDB ){
      /* Create a new page */
      pPg = sqliteMallocRaw( sizeof(*pPg) + pPager->pageSize
                              + sizeof(u32) + pPager->nExtra
                              + MEMDB*sizeof(PgHistory) );
      if( pPg==0 ){
        // pPager->errMask |= PAGER_ERR_MEM;
        return SQLITE_NOMEM;
      }
      memset(pPg, 0, sizeof(*pPg));
      if( MEMDB ){
        memset(PGHDR_TO_HIST(pPg, pPager), 0, sizeof(PgHistory));
      }
      pPg->pPager = pPager;
................................................................................
      if( pPager->nPage>pPager->nMaxPage ){
        assert( pPager->nMaxPage==(pPager->nPage-1) );
        pPager->nMaxPage++;
      }
    }else{
      rc = pager_recycle(pPager, 1, &pPg);
      if( rc!=SQLITE_OK ){
        return rc;
      }
      assert(pPg) ;
    }
    pPg->pgno = pgno;
    if( pPager->aInJournal && (int)pgno<=pPager->origDbSize ){
      sqlite3CheckMemory(pPager->aInJournal, pgno/8);
      assert( pPager->journalOpen );
................................................................................
      TRACE3("FETCH %d page %d\n", PAGERID(pPager), pPg->pgno);
      CODEC(pPager, PGHDR_TO_DATA(pPg), pPg->pgno, 3);
      if( rc!=SQLITE_OK ){
        i64 fileSize;
        if( sqlite3OsFileSize(pPager->fd,&fileSize)!=SQLITE_OK
               || fileSize>=pgno*pPager->pageSize ){
          sqlite3pager_unref(PGHDR_TO_DATA(pPg));
          return rc;
        }else{
          clear_simulated_io_error();
          memset(PGHDR_TO_DATA(pPg), 0, pPager->pageSize);
        }
      }else{
        TEST_INCR(pPager->nRead);
      }

** 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.229 2005/12/30 16:28:02 danielk1977 Exp $
*/
#ifndef SQLITE_OMIT_DISKIO
#include "sqliteInt.h"
#include "os.h"
#include "pager.h"
#include <assert.h>
#include <string.h>
................................................................................
# define TEST_INCR(x)  x++
#else
# define TEST_INCR(x)
#endif

/*
** These are bits that can be set in Pager.errMask.
**
** TODO: Maybe we just want a variable - Pager.errCode. Can we really 
**       have two simultaneous error conditions?
**
** Recovering from an SQLITE_FULL, SQLITE_LOCK, SQLITE_CORRUPT or 
** SQLITE_IOERR error is not a simple matter, particularly if the pager 
** cache is shared between multiple connections.
**
** SQLITE_FULL (PAGER_ERR_FULL):
**     Cleared when the transaction is rolled back.
**
** SQLITE_CORRUPT (PAGER_ERR_CORRUPT):
**     Cannot be cleared. The upper layer must close the current pager 
**     and open a new one on the same file to continue.
**
** SQLITE_PROTOCOL (PAGER_ERR_LOCK):
**     This error only occurs if an internal error occurs or another process 
**     is not following the sqlite locking protocol (i.e. someone is 
**     manipulating the database file using something other than sqlite).
**     This is handled in the same way as database corruption - the error 
**     cannot be cleared except by closing the current pager and opening 
**     a brand new one on the same file.
**
** SQLITE_IOERR (PAGER_ERR_DISK):
**     Cleared when the transaction is rolled back.
*/
#define PAGER_ERR_FULL     0x01  /* a write() failed */

#define PAGER_ERR_LOCK     0x02  /* error in the locking protocol */
#define PAGER_ERR_CORRUPT  0x04  /* database or journal corruption */
#define PAGER_ERR_DISK     0x08  /* general disk I/O error - bad hard drive? */

/*
** Journal files begin with the following magic string.  The data
** was obtained from /dev/random.  It is used only as a sanity check.
**
** Since version 2.8.0, the journal format contains additional sanity
** checking information.  If the power fails while the journal is begin
................................................................................
** return code.
*/
static int pager_errcode(Pager *pPager){
  int rc = SQLITE_OK;
  if( pPager->errMask & PAGER_ERR_LOCK )    rc = SQLITE_PROTOCOL;
  if( pPager->errMask & PAGER_ERR_DISK )    rc = SQLITE_IOERR;
  if( pPager->errMask & PAGER_ERR_FULL )    rc = SQLITE_FULL;

  if( pPager->errMask & PAGER_ERR_CORRUPT ) rc = SQLITE_CORRUPT;
  return rc;
}

/*
** This function should be called when an error occurs within the pager
** code to set the appropriate bits in Pager.errMask.
*/
static int pager_error(Pager *pPager, int rc){
  switch( rc ){
    case SQLITE_PROTOCOL:
      pPager->errMask |= PAGER_ERR_LOCK;
      break;
    case SQLITE_IOERR:
      pPager->errMask |= PAGER_ERR_DISK;
      break;
    case SQLITE_FULL:
      pPager->errMask |= PAGER_ERR_FULL;
      break;
    case SQLITE_CORRUPT:
      pPager->errMask |= PAGER_ERR_CORRUPT;
      break;
  }
  return rc;
}

#ifdef SQLITE_CHECK_PAGES
/*
** Return a 32-bit hash of the page data for pPage.
*/
static u32 pager_pagehash(PgHdr *pPage){
  u32 hash = 0;
................................................................................
** + N bytes: length of master journal name.
** + 4 bytes: N
** + 4 bytes: Master journal name checksum.
** + 8 bytes: aJournalMagic[].
**
** The master journal page checksum is the sum of the bytes in the master
** journal name.
**
** If zMaster is a NULL pointer (occurs for a single database transaction), 
** this call is a no-op.
*/
static int writeMasterJournal(Pager *pPager, const char *zMaster){
  int rc;
  int len; 
  int i; 
  u32 cksum = 0; 

................................................................................
  }
  sqlite3OsUnlock(pPager->fd, NO_LOCK);
  pPager->state = PAGER_UNLOCK;
  pPager->dbSize = -1;
  pPager->nRef = 0;
  assert( pPager->journalOpen==0 );
}
























/*
** When this routine is called, the pager has the journal file open and
** a RESERVED or EXCLUSIVE lock on the database.  This routine releases
** the database lock and acquires a SHARED lock in its place.  The journal
** file is deleted and closed.
**
................................................................................
*/
int sqlite3pager_open(
  Pager **ppPager,         /* Return the Pager structure here */
  const char *zFilename,   /* Name of the database file to open */
  int nExtra,              /* Extra bytes append to each in-memory page */
  int flags                /* flags controlling this file */
){
  Pager *pPager = 0;
  char *zFullPathname = 0;
  int nameLen;
  OsFile *fd;
  int rc = SQLITE_OK;
  int i;
  int tempFile = 0;
  int memDb = 0;
  int readOnly = 0;
  int useJournal = (flags & PAGER_OMIT_JOURNAL)==0;
  int noReadlock = (flags & PAGER_NO_READLOCK)!=0;
  char zTemp[SQLITE_TEMPNAME_SIZE];
  SqliteTsd *pTsd = sqlite3Tsd();

  /* If malloc() has already failed return SQLITE_NOMEM. Before even
  ** testing for this, set *ppPager to NULL so the caller knows the pager
  ** structure was never allocated. 
  */
  *ppPager = 0;

  if( sqlite3Tsd()->mallocFailed ){
    return SQLITE_NOMEM;
  }
  memset(&fd, 0, sizeof(fd));

  /* Open the pager file and set zFullPathname to point at malloc()ed 
  ** memory containing the complete filename (i.e. including the directory).
  */
  if( zFilename && zFilename[0] ){
#ifndef SQLITE_OMIT_MEMORYDB
    if( strcmp(zFilename,":memory:")==0 ){
      memDb = 1;
      zFullPathname = sqliteStrDup("");

    }else
#endif
    {
      zFullPathname = sqlite3Os.xFullPathname(zFilename);
      if( zFullPathname ){
        rc = sqlite3Os.xOpenReadWrite(zFullPathname, &fd, &readOnly);
      }
................................................................................
    rc = sqlite3pager_opentemp(zTemp, &fd);
    zFilename = zTemp;
    zFullPathname = sqlite3Os.xFullPathname(zFilename);
    if( rc==SQLITE_OK ){
      tempFile = 1;
    }
  }






  /* Allocate the Pager structure. As part of the same allocation, allocate
  ** space for the full paths of the file, directory and journal 
  ** (Pager.zFilename, Pager.zDirectory and Pager.zJournal).
  */
  if( zFullPathname ){


    nameLen = strlen(zFullPathname);
    pPager = sqliteMalloc( sizeof(*pPager) + nameLen*3 + 30 );
  }

  /* If an error occured in either of the blocks above, free the memory 
  ** pointed to by zFullPathname, free the Pager structure and close the 
  ** file. Since the pager is not allocated there is no need to set 
  ** any Pager.errMask variables.
  */
  if( !pPager || !zFullPathname || rc!=SQLITE_OK ){
    sqlite3OsClose(&fd);
    sqliteFree(zFullPathname);
    sqliteFree(pPager);
    return ((rc==SQLITE_OK)?SQLITE_NOMEM:rc);
  }

  TRACE3("OPEN %d %s\n", FILEHANDLEID(fd), zFullPathname);
  pPager->zFilename = (char*)&pPager[1];
  pPager->zDirectory = &pPager->zFilename[nameLen+1];
  pPager->zJournal = &pPager->zDirectory[nameLen+1];
  strcpy(pPager->zFilename, zFullPathname);
  strcpy(pPager->zDirectory, zFullPathname);

  for(i=nameLen; i>0 && pPager->zDirectory[i-1]!='/'; i--){}
  if( i>0 ) pPager->zDirectory[i-1] = 0;
  strcpy(pPager->zJournal, zFullPathname);
  sqliteFree(zFullPathname);
  strcpy(&pPager->zJournal[nameLen], "-journal");
  pPager->fd = fd;
  pPager->journalOpen = 0;
................................................................................
# define clear_simulated_io_error()
# define disable_simulated_io_errors()
# define enable_simulated_io_errors()
#endif

/*
** Read the first N bytes from the beginning of the file into memory
** that pDest points to. 
**
** No error checking is done. The rational for this is that this function 
** may be called even if the file does not exist or contain a header. In 
** these cases sqlite3OsRead() will return an error, to which the correct 
** response is to zero the memory at pDest and continue.  A real IO error 
** will presumably recur and be picked up later (Todo: Think about this).
*/
void sqlite3pager_read_fileheader(Pager *pPager, int N, unsigned char *pDest){
  memset(pDest, 0, N);
  if( MEMDB==0 ){
    sqlite3OsSeek(pPager->fd, 0);
    sqlite3OsRead(pPager->fd, pDest, N);
    clear_simulated_io_error();
................................................................................
** Shutdown the page cache.  Free all memory and close all files.
**
** If a transaction was in progress when this routine is called, that
** transaction is rolled back.  All outstanding pages are invalidated
** and their memory is freed.  Any attempt to use a page associated
** with this page cache after this function returns will likely
** result in a coredump.
**
** This function always succeeds. If a transaction is active an attempt
** is made to roll it back. If an error occurs during the rollback 
** a hot journal may be left in the filesystem but no error is returned
** to the caller.
*/
int sqlite3pager_close(Pager *pPager){
  PgHdr *pPg, *pNext;
#ifndef SQLITE_OMIT_MEMORY_MANAGEMENT
  SqliteTsd *pTsd = sqlite3Tsd();
#endif

................................................................................
  /* Temp files are automatically deleted by the OS
  ** if( pPager->tempFile ){
  **   sqlite3Os.xDelete(pPager->zFilename);
  ** }
  */

#ifndef SQLITE_OMIT_MEMORY_MANAGEMENT
  /* Remove the pager from the linked list of pagers starting at 
  ** SqliteTsd.pPager.
  */
  if( pPager==pTsd->pPager ){
    pTsd->pPager = pPager->pNext;
  }else{
    Pager *pTmp;
    for(pTmp = pTsd->pPager; pTmp->pNext!=pPager; pTmp=pTmp->pNext);
    pTmp->pNext = pPager->pNext;
  }
................................................................................
    return 0;
  }else{
    return 1;
  }
}

/*
** Try to find a page in the cache that can be recycled. 
**
** This routine may return SQLITE_IOERR, SQLITE_FULL or SQLITE_OK. It 
** does not set the pPager->errMask variable.
*/
static int pager_recycle(Pager *pPager, int syncOk, PgHdr **ppPg){
  PgHdr *pPg;
  *ppPg = 0;

  /* Find a page to recycle.  Try to locate a page that does not
  ** require us to do an fsync() on the journal.
................................................................................
  ** on the journal file then fsync the journal file.  This is a
  ** very slow operation, so we work hard to avoid it.  But sometimes
  ** it can't be helped.
  */
  if( pPg==0 && pPager->pFirst && syncOk && !MEMDB){
    int rc = syncJournal(pPager);
    if( rc!=0 ){

      return rc;
    }
    if( pPager->fullSync ){
      /* If in full-sync mode, write a new journal header into the
      ** journal file. This is done to avoid ever modifying a journal
      ** header that is involved in the rollback of pages that have
      ** already been written to the database (in case the header is
      ** trashed when the nRec field is updated).
      */
      pPager->nRec = 0;
      assert( pPager->journalOff > 0 );
      rc = writeJournalHdr(pPager);
      if( rc!=0 ){

        return rc;
      }
    }
    pPg = pPager->pFirst;
  }
  if( pPg==0 ){
    return SQLITE_OK;
  }
................................................................................
  */
  if( pPg->dirty ){
    int rc;
    assert( pPg->needSync==0 );
    pPg->pDirty = 0;
    rc = pager_write_pagelist( pPg );
    if( rc!=SQLITE_OK ){

      return rc;
    }
  }
  assert( pPg->dirty==0 );

  /* If the page we are recycling is marked as alwaysRollback, then
  ** set the global alwaysRollback flag, thus disabling the
  ** sqlite_dont_rollback() optimization for the rest of this transaction.
................................................................................
      int rc;

      /* For each pager, try to free as many pages as possible (without 
      ** calling fsync() if this is the first iteration of the outermost 
      ** loop).
      */
      while( SQLITE_OK==(rc = pager_recycle(p, i, &pPg)) && pPg) {
        /* 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.
        **
        ** Todo: Check the Pager.pStmt list to make sure this is Ok. It 
        ** probably is though.
        */
        PgHdr *pTmp;
        assert( pPg );
        page_remove_from_stmt_list(pPg);
        if( pPg==p->pAll ){
           p->pAll = pPg->pNextAll;
        }else{
          for( pTmp=p->pAll; pTmp->pNextAll!=pPg; pTmp=pTmp->pNextAll );
          pTmp->pNextAll = pPg->pNextAll;
        }
        nReleased += sqliteAllocSize(pPg);
        sqliteFree(pPg);
      }

      if( rc!=SQLITE_OK ){
        /* An error occured whilst writing to the database file or 
        ** journal in pager_recycle(). The error is not returned to the 
        ** caller of this function. Instead, set the Pager.errMask variable.
        ** The error will be returned to the user (or users, in the case 
        ** of a shared pager cache) of the pager for which the error occured.
        */
        assert( rc==SQLITE_IOERR || rc==SQLITE_FULL );
        assert( p->state>=PAGER_RESERVED );
        pager_error(p, rc);

      }
    }
  }

  return nReleased;
}
#endif /* SQLITE_OMIT_MEMORY_MANAGEMENT */

/*
** Acquire a page.
**
** A read lock on the disk file is obtained when the first page is acquired. 
** This read lock is dropped when the last page is released.
**
................................................................................
  /* If this is the first page accessed, then get a SHARED lock
  ** on the database file.
  */
  if( pPager->nRef==0 && !MEMDB ){
    if( !pPager->noReadlock ){
      rc = pager_wait_on_lock(pPager, SHARED_LOCK);
      if( rc!=SQLITE_OK ){
        return pager_error(pPager, rc);
      }
    }

    /* If a journal file exists, and there is no RESERVED lock on the
    ** database file, then it either needs to be played back or deleted.
    */
    if( hasHotJournal(pPager) ){
................................................................................
       ** second process will get to this point in the code and fail to
       ** obtain it's own EXCLUSIVE lock on the database file.
       */
       rc = sqlite3OsLock(pPager->fd, EXCLUSIVE_LOCK);
       if( rc!=SQLITE_OK ){
         sqlite3OsUnlock(pPager->fd, NO_LOCK);
         pPager->state = PAGER_UNLOCK;
         return pager_error(pPager, rc);
       }
       pPager->state = PAGER_EXCLUSIVE;

       /* Open the journal for reading only.  Return SQLITE_BUSY if
       ** we are unable to open the journal file. 
       **
       ** The journal file does not need to be locked itself.  The
................................................................................
       pPager->journalHdr = 0;

       /* Playback and delete the journal.  Drop the database write
       ** lock and reacquire the read lock.
       */
       rc = pager_playback(pPager);
       if( rc!=SQLITE_OK ){
         return pager_error(pPager, rc);
       }
    }
    pPg = 0;
  }else{
    /* Search for page in cache */
    pPg = pager_lookup(pPager, pgno);
    if( MEMDB && pPager->state==PAGER_UNLOCK ){
................................................................................
    TEST_INCR(pPager->nMiss);
    if( pPager->nPage<pPager->mxPage || pPager->pFirst==0 || MEMDB ){
      /* Create a new page */
      pPg = sqliteMallocRaw( sizeof(*pPg) + pPager->pageSize
                              + sizeof(u32) + pPager->nExtra
                              + MEMDB*sizeof(PgHistory) );
      if( pPg==0 ){

        return SQLITE_NOMEM;
      }
      memset(pPg, 0, sizeof(*pPg));
      if( MEMDB ){
        memset(PGHDR_TO_HIST(pPg, pPager), 0, sizeof(PgHistory));
      }
      pPg->pPager = pPager;
................................................................................
      if( pPager->nPage>pPager->nMaxPage ){
        assert( pPager->nMaxPage==(pPager->nPage-1) );
        pPager->nMaxPage++;
      }
    }else{
      rc = pager_recycle(pPager, 1, &pPg);
      if( rc!=SQLITE_OK ){
        return pager_error(pPager, rc);
      }
      assert(pPg) ;
    }
    pPg->pgno = pgno;
    if( pPager->aInJournal && (int)pgno<=pPager->origDbSize ){
      sqlite3CheckMemory(pPager->aInJournal, pgno/8);
      assert( pPager->journalOpen );
................................................................................
      TRACE3("FETCH %d page %d\n", PAGERID(pPager), pPg->pgno);
      CODEC(pPager, PGHDR_TO_DATA(pPg), pPg->pgno, 3);
      if( rc!=SQLITE_OK ){
        i64 fileSize;
        if( sqlite3OsFileSize(pPager->fd,&fileSize)!=SQLITE_OK
               || fileSize>=pgno*pPager->pageSize ){
          sqlite3pager_unref(PGHDR_TO_DATA(pPg));
          return pager_error(pPager, rc);
        }else{
          clear_simulated_io_error();
          memset(PGHDR_TO_DATA(pPg), 0, pPager->pageSize);
        }
      }else{
        TEST_INCR(pPager->nRead);
      }

**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This header file defines the interface that the SQLite library
** presents to client programs.
**
** @(#) $Id: sqlite.h.in,v 1.151 2005/12/20 09:19:37 danielk1977 Exp $
*/
#ifndef _SQLITE3_H_
#define _SQLITE3_H_
#include <stdarg.h>     /* Needed for the definition of va_list */

/*
** Make sure we can call this stuff from C++.
................................................................................
** callback is not invoked if a transaction is automatically rolled
** back because the database connection is closed.
*/
void *sqlite3_rollback_hook(sqlite3*, void(*)(void *), void*);

int sqlite3_release_memory(int);









/*
** Undo the hack that converts floating point types to integer for
** builds on processors without floating point support.
*/
#ifdef SQLITE_OMIT_FLOATING_POINT
# undef double
#endif

#ifdef __cplusplus
}  /* End of the 'extern "C"' block */
#endif
#endif

**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This header file defines the interface that the SQLite library
** presents to client programs.
**
** @(#) $Id: sqlite.h.in,v 1.152 2005/12/30 16:28:02 danielk1977 Exp $
*/
#ifndef _SQLITE3_H_
#define _SQLITE3_H_
#include <stdarg.h>     /* Needed for the definition of va_list */

/*
** Make sure we can call this stuff from C++.
................................................................................
** callback is not invoked if a transaction is automatically rolled
** back because the database connection is closed.
*/
void *sqlite3_rollback_hook(sqlite3*, void(*)(void *), void*);

int sqlite3_release_memory(int);

/*
** This function is only available if the library is compiled without
** the SQLITE_OMIT_SHARED_CACHE macro defined. It is used to enable or
** disable (if the argument is true or false, respectively) the 
** "shared pager" feature.
*/
int sqlite3_enable_shared_cache(int);

/*
** Undo the hack that converts floating point types to integer for
** builds on processors without floating point support.
*/
#ifdef SQLITE_OMIT_FLOATING_POINT
# undef double
#endif

#ifdef __cplusplus
}  /* End of the 'extern "C"' block */
#endif
#endif

**    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.445 2005/12/29 23:33:54 drh Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_

/*
** Many people are failing to set -DNDEBUG=1 when compiling SQLite.
** Setting NDEBUG makes the code smaller and run faster.  So the following
................................................................................
  u8 mallocFailed;         /* True after a malloc() has failed */

#ifndef SQLITE_OMIT_MEMORY_MANAGEMENT
  i64 nSoftHeapLimit;      /* -ve for unlimited */
  i64 nAlloc;              /* Number of bytes currently allocated */
  Pager *pPager;           /* Linked list of all pagers in this thread */
#endif






#ifdef SQLITE_MEMDEBUG
  i64 nMaxAlloc;           /* High water mark of SqliteTsd.nAlloc */
  int mallocAllowed;       /* assert() in sqlite3Malloc() if not set */
  int isFail;              /* True if all malloc() calls should fail */
  const char *zFile;       /* Filename to associate debugging info with */
  int iLine;               /* Line number to associate debugging info with */

**    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.446 2005/12/30 16:28:02 danielk1977 Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_

/*
** Many people are failing to set -DNDEBUG=1 when compiling SQLite.
** Setting NDEBUG makes the code smaller and run faster.  So the following
................................................................................
  u8 mallocFailed;         /* True after a malloc() has failed */

#ifndef SQLITE_OMIT_MEMORY_MANAGEMENT
  i64 nSoftHeapLimit;      /* -ve for unlimited */
  i64 nAlloc;              /* Number of bytes currently allocated */
  Pager *pPager;           /* Linked list of all pagers in this thread */
#endif

#ifndef SQLITE_OMIT_SHARED_CACHE
  u8 useSharedData;        /* True if shared pagers and schemas are enabled */
  BtShared *pBtree;
#endif

#ifdef SQLITE_MEMDEBUG
  i64 nMaxAlloc;           /* High water mark of SqliteTsd.nAlloc */
  int mallocAllowed;       /* assert() in sqlite3Malloc() if not set */
  int isFail;              /* True if all malloc() calls should fail */
  const char *zFile;       /* Filename to associate debugging info with */
  int iLine;               /* Line number to associate debugging info with */

**    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.
**
*************************************************************************
** A TCL Interface to SQLite
**
** $Id: tclsqlite.c,v 1.141 2005/12/19 14:18:11 danielk1977 Exp $
*/
#ifndef NO_TCL     /* Omit this whole file if TCL is unavailable */

#include "sqliteInt.h"
#include "hash.h"
#include "tcl.h"
#include <stdlib.h>
................................................................................
    break;
  }

  /*
  **     $db soft_heap_limit N
  **
  ** Set the soft-heap-limit for this thread. Note that the limit is 
  ** per-thread, not per-database. An empty string is returned.
  */
  case DB_SOFT_HEAP_LIMIT: {
#ifndef SQLITE_OMIT_MEMORY_MANAGEMENT
    int n;

    if( objc!=3 ){
      Tcl_WrongNumArgs(interp, 2, objv, "BYTES");
      return TCL_ERROR;
    }
    if( Tcl_GetIntFromObj(interp, objv[2], &n) ){
      return TCL_ERROR;
    }

    sqlite3_soft_heap_limit(n);
    Tcl_ResetResult(interp);
#endif
    break;
  }

  /*
  **     $db release_memory ?N?
  **

**    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.
**
*************************************************************************
** A TCL Interface to SQLite
**
** $Id: tclsqlite.c,v 1.142 2005/12/30 16:28:02 danielk1977 Exp $
*/
#ifndef NO_TCL     /* Omit this whole file if TCL is unavailable */

#include "sqliteInt.h"
#include "hash.h"
#include "tcl.h"
#include <stdlib.h>
................................................................................
    break;
  }

  /*
  **     $db soft_heap_limit N
  **
  ** Set the soft-heap-limit for this thread. Note that the limit is 
  ** per-thread, not per-database. The previous limit is returned.
  */
  case DB_SOFT_HEAP_LIMIT: {
#ifndef SQLITE_OMIT_MEMORY_MANAGEMENT
    int n;
    int ret;
    if( objc!=3 ){
      Tcl_WrongNumArgs(interp, 2, objv, "BYTES");
      return TCL_ERROR;
    }
    if( Tcl_GetIntFromObj(interp, objv[2], &n) ){
      return TCL_ERROR;
    }
    ret = sqlite3Tsd()->nSoftHeapLimit;
    sqlite3_soft_heap_limit(n);
    Tcl_SetObjResult(interp, Tcl_NewIntObj(ret));
#endif
    break;
  }

  /*
  **     $db release_memory ?N?
  **

**    May you share freely, never taking more than you give.
**
*************************************************************************
** Code for testing the printf() interface to SQLite.  This code
** is not included in the SQLite library.  It is used for automated
** testing of the SQLite library.
**
** $Id: test1.c,v 1.177 2005/12/20 09:19:37 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include "tcl.h"
#include "os.h"
#include <stdlib.h>
#include <string.h>

................................................................................
    return TCL_OK;
  }

  return sqlite3OutstandingMallocs(interp);
}
#endif

































/*
** Usage:  sqlite_abort
**
** Shutdown the process immediately.  This is not a clean shutdown.
** This command is used to test the recoverability of a database in
** the event of a program crash.
*/
................................................................................
#endif

#ifdef SQLITE_OMIT_SCHEMA_VERSION_PRAGMAS
  Tcl_SetVar2(interp, "sqlite_options", "schema_version", "0", TCL_GLOBAL_ONLY);
#else
  Tcl_SetVar2(interp, "sqlite_options", "schema_version", "1", TCL_GLOBAL_ONLY);
#endif







#ifdef SQLITE_OMIT_SUBQUERY
  Tcl_SetVar2(interp, "sqlite_options", "subquery", "0", TCL_GLOBAL_ONLY);
#else
  Tcl_SetVar2(interp, "sqlite_options", "subquery", "1", TCL_GLOBAL_ONLY);
#endif

................................................................................
     { "add_test_function",       test_function, 0           },
#endif
#ifdef SQLITE_MEMDEBUG
     { "sqlite_malloc_outstanding", sqlite_malloc_outstanding, 0},
#endif
     { "sqlite3_test_errstr",     test_errstr, 0             },
     { "tcl_variable_type",       tcl_variable_type, 0       },



  };
  static int bitmask_size = sizeof(Bitmask)*8;
  int i;
  extern int sqlite3_os_trace;
  extern int sqlite3_where_trace;
  extern int sqlite3_sync_count, sqlite3_fullsync_count;
  extern int sqlite3_opentemp_count;

**    May you share freely, never taking more than you give.
**
*************************************************************************
** Code for testing the printf() interface to SQLite.  This code
** is not included in the SQLite library.  It is used for automated
** testing of the SQLite library.
**
** $Id: test1.c,v 1.178 2005/12/30 16:28:02 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include "tcl.h"
#include "os.h"
#include <stdlib.h>
#include <string.h>

................................................................................
    return TCL_OK;
  }

  return sqlite3OutstandingMallocs(interp);
}
#endif

/*
** Usage: sqlite3_enable_shared_cache BOOLEAN
**
*/
#ifndef SQLITE_OMIT_SHARED_CACHE
static int test_enable_shared_cache(
  ClientData clientData,
  Tcl_Interp *interp,    /* The TCL interpreter that invoked this command */
  int objc,              /* Number of arguments */
  Tcl_Obj *CONST objv[]  /* Command arguments */
){
  int rc;
  int enable;
  SqliteTsd *pTsd = sqlite3Tsd();
  Tcl_SetObjResult(interp, Tcl_NewBooleanObj(pTsd->useSharedData));

  if( objc!=2 ){
    Tcl_WrongNumArgs(interp, 1, objv, "BOOLEAN");
    return TCL_ERROR;
  }
  if( Tcl_GetBooleanFromObj(interp, objv[1], &enable) ){
    return TCL_ERROR;
  }
  rc = sqlite3_enable_shared_cache(enable);
  if( rc!=SQLITE_OK ){
    Tcl_SetResult(interp, (char *)sqlite3ErrStr(rc), TCL_STATIC);
    return TCL_ERROR;
  }
  return TCL_OK;
}
#endif

/*
** Usage:  sqlite_abort
**
** Shutdown the process immediately.  This is not a clean shutdown.
** This command is used to test the recoverability of a database in
** the event of a program crash.
*/
................................................................................
#endif

#ifdef SQLITE_OMIT_SCHEMA_VERSION_PRAGMAS
  Tcl_SetVar2(interp, "sqlite_options", "schema_version", "0", TCL_GLOBAL_ONLY);
#else
  Tcl_SetVar2(interp, "sqlite_options", "schema_version", "1", TCL_GLOBAL_ONLY);
#endif

#ifdef SQLITE_OMIT_SHARED_CACHE
  Tcl_SetVar2(interp, "sqlite_options", "shared_cache", "0", TCL_GLOBAL_ONLY);
#else
  Tcl_SetVar2(interp, "sqlite_options", "shared_cache", "1", TCL_GLOBAL_ONLY);
#endif

#ifdef SQLITE_OMIT_SUBQUERY
  Tcl_SetVar2(interp, "sqlite_options", "subquery", "0", TCL_GLOBAL_ONLY);
#else
  Tcl_SetVar2(interp, "sqlite_options", "subquery", "1", TCL_GLOBAL_ONLY);
#endif

................................................................................
     { "add_test_function",       test_function, 0           },
#endif
#ifdef SQLITE_MEMDEBUG
     { "sqlite_malloc_outstanding", sqlite_malloc_outstanding, 0},
#endif
     { "sqlite3_test_errstr",     test_errstr, 0             },
     { "tcl_variable_type",       tcl_variable_type, 0       },
#ifndef SQLITE_OMIT_SHARED_CACHE
     { "sqlite3_enable_shared_cache", test_enable_shared_cache, 0},
#endif
  };
  static int bitmask_size = sizeof(Bitmask)*8;
  int i;
  extern int sqlite3_os_trace;
  extern int sqlite3_where_trace;
  extern int sqlite3_sync_count, sqlite3_fullsync_count;
  extern int sqlite3_opentemp_count;

**    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.63 2005/12/09 20:21:59 drh Exp $
*/
#include "sqliteInt.h"
#include "pager.h"
#include "btree.h"
#include "tcl.h"
#include <stdlib.h>
#include <string.h>
................................................................................
  if( argc!=4 ){
    Tcl_AppendResult(interp, "wrong # args: should be \"", argv[0],
       " FILENAME NCACHE FLAGS\"", 0);
    return TCL_ERROR;
  }
  if( Tcl_GetInt(interp, argv[2], &nCache) ) return TCL_ERROR;
  if( Tcl_GetInt(interp, argv[3], &flags) ) return TCL_ERROR;
  rc = sqlite3BtreeOpen(argv[1], &pBt, flags);
  if( rc!=SQLITE_OK ){
    Tcl_AppendResult(interp, errorName(rc), 0);
    return TCL_ERROR;
  }
  sqlite3BtreeSetCacheSize(pBt, nCache);
  sqlite3_snprintf(sizeof(zBuf), zBuf,"%p", pBt);
  Tcl_AppendResult(interp, zBuf, 0);

**    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.64 2005/12/30 16:28:02 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include "pager.h"
#include "btree.h"
#include "tcl.h"
#include <stdlib.h>
#include <string.h>
................................................................................
  if( argc!=4 ){
    Tcl_AppendResult(interp, "wrong # args: should be \"", argv[0],
       " FILENAME NCACHE FLAGS\"", 0);
    return TCL_ERROR;
  }
  if( Tcl_GetInt(interp, argv[2], &nCache) ) return TCL_ERROR;
  if( Tcl_GetInt(interp, argv[3], &flags) ) return TCL_ERROR;
  rc = sqlite3BtreeOpen(argv[1], 0, &pBt, flags);
  if( rc!=SQLITE_OK ){
    Tcl_AppendResult(interp, errorName(rc), 0);
    return TCL_ERROR;
  }
  sqlite3BtreeSetCacheSize(pBt, nCache);
  sqlite3_snprintf(sizeof(zBuf), zBuf,"%p", pBt);
  Tcl_AppendResult(interp, zBuf, 0);

      needXcommit = 1;
      if( i!=1 ) nTrans++;
    }
  }

  /* If there are any write-transactions at all, invoke the commit hook */
  if( needXcommit && db->xCommitCallback ){
    int rc;
    sqlite3SafetyOff(db);
    rc = db->xCommitCallback(db->pCommitArg);
    sqlite3SafetyOn(db);
    if( rc ){
      return SQLITE_CONSTRAINT;
    }
  }

      needXcommit = 1;
      if( i!=1 ) nTrans++;
    }
  }

  /* If there are any write-transactions at all, invoke the commit hook */
  if( needXcommit && db->xCommitCallback ){

    sqlite3SafetyOff(db);
    rc = db->xCommitCallback(db->pCommitArg);
    sqlite3SafetyOn(db);
    if( rc ){
      return SQLITE_CONSTRAINT;
    }
  }

#
#*************************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this script is testing that SQLite can handle a subtle 
# file format change that may be used in the future to implement
# "ALTER TABLE ... ADD COLUMN".
#
# $Id: alter3.test,v 1.6 2005/03/29 03:11:00 danielk1977 Exp $
#

set testdir [file dirname $argv0]

source $testdir/tester.tcl

# If SQLITE_OMIT_ALTERTABLE is defined, omit this file.
................................................................................
# Ticket #1183 - Make sure adding columns to large tables does not cause
# memory corruption (as was the case before this bug was fixed).
do_test alter3-8.1 {
  execsql {
    CREATE TABLE t4(c1);
  }
} {}

do_test alter3-8.2 {
  set cols c1
  for {set i 2} {$i < 100} {incr i} {
    execsql "
      ALTER TABLE t4 ADD c$i
    "
    lappend cols c$i

#
#*************************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this script is testing that SQLite can handle a subtle 
# file format change that may be used in the future to implement
# "ALTER TABLE ... ADD COLUMN".
#
# $Id: alter3.test,v 1.7 2005/12/30 16:28:02 danielk1977 Exp $
#

set testdir [file dirname $argv0]

source $testdir/tester.tcl

# If SQLITE_OMIT_ALTERTABLE is defined, omit this file.
................................................................................
# Ticket #1183 - Make sure adding columns to large tables does not cause
# memory corruption (as was the case before this bug was fixed).
do_test alter3-8.1 {
  execsql {
    CREATE TABLE t4(c1);
  }
} {}
set ::sql ""
do_test alter3-8.2 {
  set cols c1
  for {set i 2} {$i < 100} {incr i} {
    execsql "
      ALTER TABLE t4 ADD c$i
    "
    lappend cols c$i

#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this script is testing the ATTACH and DETACH commands
# and related functionality.
#
# $Id: attach2.test,v 1.33 2005/12/06 17:19:12 danielk1977 Exp $
#

set testdir [file dirname $argv0]
source $testdir/tester.tcl


# Ticket #354
#
# Databases test.db and test2.db contain identical schemas.  Make
# sure we can attach test2.db from test.db.
#
do_test attach2-1.1 {
................................................................................

# A procedure to verify the status of locks on a database.
#
proc lock_status {testnum db expected_result} {
  # If the database was compiled with OMIT_TEMPDB set, then 
  # the lock_status list will not contain an entry for the temp
  # db. But the test code doesn't know this, so it's easiest 
  # to filter it out here.
  ifcapable !tempdb {
    set expected_result [concat \
        [lrange $expected_result 0 1] \
        [lrange $expected_result 4 end] \
    ]
  }
  do_test attach2-$testnum [subst {

#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this script is testing the ATTACH and DETACH commands
# and related functionality.
#
# $Id: attach2.test,v 1.34 2005/12/30 16:28:02 danielk1977 Exp $
#

set testdir [file dirname $argv0]
source $testdir/tester.tcl


# Ticket #354
#
# Databases test.db and test2.db contain identical schemas.  Make
# sure we can attach test2.db from test.db.
#
do_test attach2-1.1 {
................................................................................

# A procedure to verify the status of locks on a database.
#
proc lock_status {testnum db expected_result} {
  # If the database was compiled with OMIT_TEMPDB set, then 
  # the lock_status list will not contain an entry for the temp
  # db. But the test code doesn't know this, so it's easiest 
  # to filter it out of the $expected_result list here.
  ifcapable !tempdb {
    set expected_result [concat \
        [lrange $expected_result 0 1] \
        [lrange $expected_result 4 end] \
    ]
  }
  do_test attach2-$testnum [subst {

#
#    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: malloc5.test,v 1.2 2005/12/20 09:19:38 danielk1977 Exp $

#---------------------------------------------------------------------------
# NOTES ON EXPECTED BEHAVIOUR
#
#---------------------------------------------------------------------------

set testdir [file dirname $argv0]
source $testdir/tester.tcl








do_test malloc5-1.1 {
  # Simplest possible test. Call [db release_memory] when there is exactly
  # one unused page in a single pager cache. This test case set's the 
  # value of the ::pgalloc variable, which is used in subsequent tests.
  #
  # Note: Even though executing this statement on an empty database 
................................................................................
# to ensure that more than 1MB of dynamic memory is used to perform
# the transaction. 
#
# The second test case sets the "soft-heap-limit" to 100,000 bytes (0.1 MB)
# and tests to see that this limit is not exceeded at any point during 
# transaction execution.
#





do_test malloc5-4.1 {
  execsql {BEGIN;}
  execsql {DELETE FROM abc;}
  for {set i 0} {$i < 10000} {incr i} {
    execsql "INSERT INTO abc VALUES($i, $i, '[string repeat X 100]');"
  }
  execsql {COMMIT;}
................................................................................
do_test malloc5-4.3 {
  # Check that the content of table abc is at least roughly as expected.
  execsql {
    SELECT count(*), sum(a), sum(b) FROM abc;
  }
} [list 20000 [expr int(20000.0 * 4999.5)] [expr int(20000.0 * 4999.5)]]

# Unset the soft-heap-limit value.
db soft_heap_limit -1

finish_test

#
#    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 contains test cases focused on the two memory-management APIs, 
# sqlite3_soft_heap_limit() and sqlite3_release_memory().
#
# $Id: malloc5.test,v 1.3 2005/12/30 16:28:02 danielk1977 Exp $

#---------------------------------------------------------------------------
# NOTES ON EXPECTED BEHAVIOUR
#
#---------------------------------------------------------------------------

set testdir [file dirname $argv0]
source $testdir/tester.tcl

# Only run these tests if memory debugging is turned on.
if {[info command sqlite_malloc_stat]==""} {
   puts "Skipping malloc tests: not compiled with -DSQLITE_MEMDEBUG..."
   finish_test
   return
}

do_test malloc5-1.1 {
  # Simplest possible test. Call [db release_memory] when there is exactly
  # one unused page in a single pager cache. This test case set's the 
  # value of the ::pgalloc variable, which is used in subsequent tests.
  #
  # Note: Even though executing this statement on an empty database 
................................................................................
# to ensure that more than 1MB of dynamic memory is used to perform
# the transaction. 
#
# The second test case sets the "soft-heap-limit" to 100,000 bytes (0.1 MB)
# and tests to see that this limit is not exceeded at any point during 
# transaction execution.
#
# Before executing malloc5-4.* we save the value of the current soft heap 
# limit in variable ::soft_limit. The original value is restored after 
# running the tests.
#
set ::soft_limit [db soft_heap_limit -1]
do_test malloc5-4.1 {
  execsql {BEGIN;}
  execsql {DELETE FROM abc;}
  for {set i 0} {$i < 10000} {incr i} {
    execsql "INSERT INTO abc VALUES($i, $i, '[string repeat X 100]');"
  }
  execsql {COMMIT;}
................................................................................
do_test malloc5-4.3 {
  # Check that the content of table abc is at least roughly as expected.
  execsql {
    SELECT count(*), sum(a), sum(b) FROM abc;
  }
} [list 20000 [expr int(20000.0 * 4999.5)] [expr int(20000.0 * 4999.5)]]

# Restore the soft heap limit.
db soft_heap_limit $::soft_limit

finish_test

#    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 runs all tests.
#
# $Id: quick.test,v 1.38 2005/12/15 10:11:32 danielk1977 Exp $



















set testdir [file dirname $argv0]
source $testdir/tester.tcl
rename finish_test really_finish_test
proc finish_test {} {}
set ISQUICK 1

#    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 runs all tests.
#
# $Id: quick.test,v 1.39 2005/12/30 16:28:02 danielk1977 Exp $

proc lshift {lvar} {
  upvar $lvar l
  set ret [lindex $l 0]
  set l [lrange $l 1 end]
  return $ret
}
while {[set arg [lshift argv]] != ""} {
  switch -- $arg {
    -sharedpagercache {
      sqlite3_enable_shared_cache 1
    }
    default {
      set argv [linsert $argv 0 $arg]
      break
    }
  }
}

set testdir [file dirname $argv0]
source $testdir/tester.tcl
rename finish_test really_finish_test
proc finish_test {} {}
set ISQUICK 1

# 2005 December 30
#
# 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 regression tests for SQLite library.  The
# focus of this file is testing the SELECT statement.
#
# $Id: shared.test,v 1.1 2005/12/30 16:28:02 danielk1977 Exp $

set ::enable_shared_cache [sqlite3_enable_shared_cache 1]

set testdir [file dirname $argv0]
source $testdir/tester.tcl
db close

ifcapable !shared_cache {
  finish_test
  return
}

# Test organization:
#
# shared-1.*: Simple test to verify basic sanity of table level locking when
#             two connections share a pager cache.
# shared-2.*: Test that a read transaction can co-exist with a 
#             write-transaction, including a simple test to ensure the 
#             external locking protocol is still working.
#

do_test shared-1.1 {
  # Open a second database on the file test.db. It should use the same pager
  # cache and schema as the original connection. Verify that only 1 file is 
  # opened.
  sqlite3 db2 test.db
  sqlite3 db  test.db
  set ::sqlite_open_file_count
} {1}
do_test shared-1.2 {
  # Add a table and a single row of data via the first connection. 
  # Ensure that the second connection can see them.
  execsql {
    CREATE TABLE abc(a, b, c);
    INSERT INTO abc VALUES(1, 2, 3);
  } db
  execsql {
    SELECT * FROM abc;
  } db2
} {1 2 3}
do_test shared-1.3 {
  # Have the first connection begin a transaction and obtain a read-lock
  # on table abc. This should not prevent the second connection from 
  # querying abc.
  execsql {
    BEGIN;
    SELECT * FROM abc;
  }
  execsql {
    SELECT * FROM abc;
  } db2
} {1 2 3}
do_test shared-1.4 {
  # Try to insert a row into abc via connection 2. This should fail because
  # of the read-lock connection 1 is holding on table abc (obtained in the
  # previous test case).
  catchsql {
    INSERT INTO abc VALUES(4, 5, 6);
  } db2
} {1 {database is locked}}
do_test shared-1.5 {
  # Using connection 2 (the one without the open transaction), create a 
  # new table and add a row to it. This is permitted as the transaction
  # started by connection 1 is currently a read transaction.
  execsql {
    CREATE TABLE def(d, e, f);
    INSERT INTO def VALUES('I', 'II', 'III');
  } db2
} {}
do_test shared-1.6 {
  # Upgrade connection 1's transaction to a write transaction. Insert
  # a row into table def - the table just created by connection 2.
  #
  # Connection 1 is able to see table def, even though it was created 
  # "after" the connection 1 transaction was started. This is because no
  # lock was established on the sqlite_master table.

# Todo: Remove this. Because the implementation does not include
# shared-schemas yet, we need to run some query (that will fail at 
# OP_VerifyCookie) so that connection 1 picks up the schema change
# made via connection 2. Otherwise the sqlite3_prepare("INSERT INTO def...")
# below will fail.
execsql {
  SELECT * FROM sqlite_master;
}

  execsql {
    INSERT INTO def VALUES('IV', 'V', 'VI');
  }
} {}
do_test shared-1.7 {
  # Read from the sqlite_master table with connection 1 (inside the 
  # transaction). Then test that we can no longer create a table 
  # with connection 2. This is because of the read-lock on sqlite_master.
  execsql {
    SELECT * FROM sqlite_master;
  }
  catchsql {
    CREATE TABLE ghi(g, h, i);
  } db2
} {1 {database is locked}}
do_test shared-1.8 {
  # Check that connection 2 can read the sqlite_master table. Then
  # create a table using connection 1 (this should write-lock the 
  # sqlite_master table). Then try to read sqlite_master again using 
  # connection 2 and verify that the write-lock prevents this.
  execsql {
    SELECT * FROM sqlite_master;
  } db2
  execsql {
    CREATE TABLE ghi(g, h, i);
  } 
  catchsql {
    SELECT * FROM sqlite_master;
  } db2
} {1 {database is locked}}
do_test shared-1.9 {
  # Commit the connection 1 transaction.
  execsql {
    COMMIT;
  }
} {}

do_test shared-2.1 {
  # Open connection db3 to the database. Use a different path to the same
  # file so that db3 does *not* share the same pager cache as db and db2
  # (there should be two open file handles).
  sqlite3 db3 ./test.db
  set ::sqlite_open_file_count
} {2}
do_test shared-2.2 {
  # Start read transactions on db and db2 (the shared pager cache). Ensure
  # db3 cannot write to the database.
  execsql {
    BEGIN;
    SELECT * FROM abc;
  }
  execsql {
    BEGIN;
    SELECT * FROM abc;
  } db2
  catchsql {
    INSERT INTO abc VALUES(1, 2, 3);
  } db2
} {1 {database is locked}}
do_test shared-2.3 {
  # Turn db's transaction into a write-transaction. db3 should still be
  # able to read from table def (but will not see the new row). Connection
  # db2 should not be able to read def (because of the write-lock).

# Todo: The failed "INSERT INTO abc ..." statement in the above test
# has started a write-transaction on db2 (should this be so?). This 
# would prevent connection db from starting a write-transaction. So roll the
# db2 transaction back and replace it with a new read transaction.
  execsql {
    ROLLBACK;
    BEGIN;
    SELECT * FROM abc;
  } db2

  execsql {
    INSERT INTO def VALUES('VII', 'VIII', 'IX');
  }
  concat [
    catchsql { SELECT * FROM def; } db3
  ] [
    catchsql { SELECT * FROM def; } db2
  ]
} {0 {I II III IV V VI} 1 {database is locked}}
do_test shared-2.4 {
  # Commit the open transaction on db. db2 still holds a read-transaction.
  # This should prevent db3 from writing to the database, but not from 
  # reading.
  execsql {
    COMMIT;
  }
  concat [
    catchsql { SELECT * FROM def; } db3
  ] [
    catchsql { INSERT INTO def VALUES('X', 'XI', 'XII'); } db3
  ]
} {0 {I II III IV V VI VII VIII IX} 1 {database is locked}}


catch {db close}
catch {db2 close}
catch {db3 close}

finish_test
sqlite3_enable_shared_cache $::enable_shared_cache

#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements some common TCL routines used for regression
# testing the SQLite library
#
# $Id: tester.tcl,v 1.54 2005/12/09 14:39:05 danielk1977 Exp $

# Make sure tclsqlite3 was compiled correctly.  Abort now with an
# error message if not.
#
if {[sqlite3 -tcl-uses-utf]} {
  if {"\u1234"=="u1234"} {
    puts stderr "***** BUILD PROBLEM *****"
................................................................................
# the current thread. A list is returned with one entry for each outstanding
# malloc. Each list entry is itself a list of 5 items, as follows:
#
#     { <number-bytes> <file-name> <line-number> <test-case> <stack-dump> }
#
proc check_for_leaks {} {
  set ret [list]

  foreach alloc [sqlite_malloc_outstanding] {
    foreach {nBytes file iLine userstring backtrace} $alloc {}
    set stack [list]
    set skip 0

    # The first command in this block will probably fail on windows. This
    # means there will be no stack dump available.

    catch {
      set stuff [eval "exec addr2line -e ./testfixture -f $backtrace"]
      foreach {func line} $stuff {
        if {$func != "??" || $line != "??:0"} {
          regexp {.*/(.*)} $line dummy line
          lappend stack "${func}() $line"
        } else {
          if {[lindex $stack end] != "..."} {
            lappend stack "..."

          }
        }
      }

    }

    if {!$skip} {
      lappend ret [list $nBytes $file $iLine $userstring $stack]
    }
  }
  return $ret

#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements some common TCL routines used for regression
# testing the SQLite library
#
# $Id: tester.tcl,v 1.55 2005/12/30 16:28:02 danielk1977 Exp $

# Make sure tclsqlite3 was compiled correctly.  Abort now with an
# error message if not.
#
if {[sqlite3 -tcl-uses-utf]} {
  if {"\u1234"=="u1234"} {
    puts stderr "***** BUILD PROBLEM *****"
................................................................................
# the current thread. A list is returned with one entry for each outstanding
# malloc. Each list entry is itself a list of 5 items, as follows:
#
#     { <number-bytes> <file-name> <line-number> <test-case> <stack-dump> }
#
proc check_for_leaks {} {
  set ret [list]
  set cnt 0
  foreach alloc [sqlite_malloc_outstanding] {
    foreach {nBytes file iLine userstring backtrace} $alloc {}
    set stack [list]
    set skip 0

    # The first command in this block will probably fail on windows. This
    # means there will be no stack dump available.
    if {$cnt < 25} {
      catch {
        set stuff [eval "exec addr2line -e ./testfixture -f $backtrace"]
        foreach {func line} $stuff {
          if {$func != "??" || $line != "??:0"} {
            regexp {.*/(.*)} $line dummy line
            lappend stack "${func}() $line"
          } else {
            if {[lindex $stack end] != "..."} {
              lappend stack "..."
            }
          }
        }
      }
      incr cnt
    }

    if {!$skip} {
      lappend ret [list $nBytes $file $iLine $userstring $stack]
    }
  }
  return $ret

#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this script is database locks.
#
# $Id: trans.test,v 1.26 2005/03/29 03:11:00 danielk1977 Exp $


set testdir [file dirname $argv0]
source $testdir/tester.tcl


# Create several tables to work with.
................................................................................
  }
} {1 2 3}
do_test trans-3.2 {
  catchsql {
    SELECT a FROM two ORDER BY a;
  } altdb
} {0 {1 5 10}}

do_test trans-3.3 {
  catchsql {
    SELECT a FROM one ORDER BY a;
  } altdb
} {0 {1 2 3}}
do_test trans-3.4 {
  catchsql {
................................................................................
  catchsql {
    SELECT a FROM one ORDER BY a;
  } altdb
} {0 {1 2 3}}
do_test trans-3.10 {
  execsql {END TRANSACTION}
} {}

do_test trans-3.11 {
  set v [catch {execsql {
    SELECT a FROM two ORDER BY a;
  } altdb} msg]
  lappend v $msg
} {0 {1 4 5 10}}
do_test trans-3.12 {

#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this script is database locks.
#
# $Id: trans.test,v 1.27 2005/12/30 16:28:02 danielk1977 Exp $


set testdir [file dirname $argv0]
source $testdir/tester.tcl


# Create several tables to work with.
................................................................................
  }
} {1 2 3}
do_test trans-3.2 {
  catchsql {
    SELECT a FROM two ORDER BY a;
  } altdb
} {0 {1 5 10}}

do_test trans-3.3 {
  catchsql {
    SELECT a FROM one ORDER BY a;
  } altdb
} {0 {1 2 3}}
do_test trans-3.4 {
  catchsql {
................................................................................
  catchsql {
    SELECT a FROM one ORDER BY a;
  } altdb
} {0 {1 2 3}}
do_test trans-3.10 {
  execsql {END TRANSACTION}
} {}

do_test trans-3.11 {
  set v [catch {execsql {
    SELECT a FROM two ORDER BY a;
  } altdb} msg]
  lappend v $msg
} {0 {1 4 5 10}}
do_test trans-3.12 {