btree.c.svn-base
上传用户:sunhongbo
上传日期:2022-01-25
资源大小:3010k
文件大小:220k
源码类别:

数据库系统

开发平台:

C/C++

  1. /*
  2. ** 2004 April 6
  3. **
  4. ** The author disclaims copyright to this source code.  In place of
  5. ** a legal notice, here is a blessing:
  6. **
  7. **    May you do good and not evil.
  8. **    May you find forgiveness for yourself and forgive others.
  9. **    May you share freely, never taking more than you give.
  10. **
  11. *************************************************************************
  12. ** $Id: btree.c,v 1.451 2008/04/03 21:46:57 drh Exp $
  13. **
  14. ** This file implements a external (disk-based) database using BTrees.
  15. ** See the header comment on "btreeInt.h" for additional information.
  16. ** Including a description of file format and an overview of operation.
  17. */
  18. #include "btreeInt.h"
  19. /*
  20. ** The header string that appears at the beginning of every
  21. ** SQLite database.
  22. */
  23. static const char zMagicHeader[] = SQLITE_FILE_HEADER;
  24. /*
  25. ** Set this global variable to 1 to enable tracing using the TRACE
  26. ** macro.
  27. */
  28. #if SQLITE_TEST
  29. int sqlite3BtreeTrace=0;  /* True to enable tracing */
  30. #endif
  31. #ifndef SQLITE_OMIT_SHARED_CACHE
  32. /*
  33. ** A flag to indicate whether or not shared cache is enabled.  Also,
  34. ** a list of BtShared objects that are eligible for participation
  35. ** in shared cache.  The variables have file scope during normal builds,
  36. ** but the test harness needs to access these variables so we make them
  37. ** global for test builds.
  38. */
  39. #ifdef SQLITE_TEST
  40. BtShared *sqlite3SharedCacheList = 0;
  41. int sqlite3SharedCacheEnabled = 0;
  42. #else
  43. static BtShared *sqlite3SharedCacheList = 0;
  44. static int sqlite3SharedCacheEnabled = 0;
  45. #endif
  46. #endif /* SQLITE_OMIT_SHARED_CACHE */
  47. #ifndef SQLITE_OMIT_SHARED_CACHE
  48. /*
  49. ** Enable or disable the shared pager and schema features.
  50. **
  51. ** This routine has no effect on existing database connections.
  52. ** The shared cache setting effects only future calls to
  53. ** sqlite3_open(), sqlite3_open16(), or sqlite3_open_v2().
  54. */
  55. int sqlite3_enable_shared_cache(int enable){
  56.   sqlite3SharedCacheEnabled = enable;
  57.   return SQLITE_OK;
  58. }
  59. #endif
  60. /*
  61. ** Forward declaration
  62. */
  63. static int checkReadLocks(Btree*,Pgno,BtCursor*);
  64. #ifdef SQLITE_OMIT_SHARED_CACHE
  65.   /*
  66.   ** The functions queryTableLock(), lockTable() and unlockAllTables()
  67.   ** manipulate entries in the BtShared.pLock linked list used to store
  68.   ** shared-cache table level locks. If the library is compiled with the
  69.   ** shared-cache feature disabled, then there is only ever one user
  70.   ** of each BtShared structure and so this locking is not necessary. 
  71.   ** So define the lock related functions as no-ops.
  72.   */
  73.   #define queryTableLock(a,b,c) SQLITE_OK
  74.   #define lockTable(a,b,c) SQLITE_OK
  75.   #define unlockAllTables(a)
  76. #endif
  77. #ifndef SQLITE_OMIT_SHARED_CACHE
  78. /*
  79. ** Query to see if btree handle p may obtain a lock of type eLock 
  80. ** (READ_LOCK or WRITE_LOCK) on the table with root-page iTab. Return
  81. ** SQLITE_OK if the lock may be obtained (by calling lockTable()), or
  82. ** SQLITE_LOCKED if not.
  83. */
  84. static int queryTableLock(Btree *p, Pgno iTab, u8 eLock){
  85.   BtShared *pBt = p->pBt;
  86.   BtLock *pIter;
  87.   assert( sqlite3BtreeHoldsMutex(p) );
  88.   
  89.   /* This is a no-op if the shared-cache is not enabled */
  90.   if( !p->sharable ){
  91.     return SQLITE_OK;
  92.   }
  93.   /* If some other connection is holding an exclusive lock, the
  94.   ** requested lock may not be obtained.
  95.   */
  96.   if( pBt->pExclusive && pBt->pExclusive!=p ){
  97.     return SQLITE_LOCKED;
  98.   }
  99.   /* This (along with lockTable()) is where the ReadUncommitted flag is
  100.   ** dealt with. If the caller is querying for a read-lock and the flag is
  101.   ** set, it is unconditionally granted - even if there are write-locks
  102.   ** on the table. If a write-lock is requested, the ReadUncommitted flag
  103.   ** is not considered.
  104.   **
  105.   ** In function lockTable(), if a read-lock is demanded and the 
  106.   ** ReadUncommitted flag is set, no entry is added to the locks list 
  107.   ** (BtShared.pLock).
  108.   **
  109.   ** To summarize: If the ReadUncommitted flag is set, then read cursors do
  110.   ** not create or respect table locks. The locking procedure for a 
  111.   ** write-cursor does not change.
  112.   */
  113.   if( 
  114.     !p->db || 
  115.     0==(p->db->flags&SQLITE_ReadUncommitted) || 
  116.     eLock==WRITE_LOCK ||
  117.     iTab==MASTER_ROOT
  118.   ){
  119.     for(pIter=pBt->pLock; pIter; pIter=pIter->pNext){
  120.       if( pIter->pBtree!=p && pIter->iTable==iTab && 
  121.           (pIter->eLock!=eLock || eLock!=READ_LOCK) ){
  122.         return SQLITE_LOCKED;
  123.       }
  124.     }
  125.   }
  126.   return SQLITE_OK;
  127. }
  128. #endif /* !SQLITE_OMIT_SHARED_CACHE */
  129. #ifndef SQLITE_OMIT_SHARED_CACHE
  130. /*
  131. ** Add a lock on the table with root-page iTable to the shared-btree used
  132. ** by Btree handle p. Parameter eLock must be either READ_LOCK or 
  133. ** WRITE_LOCK.
  134. **
  135. ** SQLITE_OK is returned if the lock is added successfully. SQLITE_BUSY and
  136. ** SQLITE_NOMEM may also be returned.
  137. */
  138. static int lockTable(Btree *p, Pgno iTable, u8 eLock){
  139.   BtShared *pBt = p->pBt;
  140.   BtLock *pLock = 0;
  141.   BtLock *pIter;
  142.   assert( sqlite3BtreeHoldsMutex(p) );
  143.   /* This is a no-op if the shared-cache is not enabled */
  144.   if( !p->sharable ){
  145.     return SQLITE_OK;
  146.   }
  147.   assert( SQLITE_OK==queryTableLock(p, iTable, eLock) );
  148.   /* If the read-uncommitted flag is set and a read-lock is requested,
  149.   ** return early without adding an entry to the BtShared.pLock list. See
  150.   ** comment in function queryTableLock() for more info on handling 
  151.   ** the ReadUncommitted flag.
  152.   */
  153.   if( 
  154.     (p->db) && 
  155.     (p->db->flags&SQLITE_ReadUncommitted) && 
  156.     (eLock==READ_LOCK) &&
  157.     iTable!=MASTER_ROOT
  158.   ){
  159.     return SQLITE_OK;
  160.   }
  161.   /* First search the list for an existing lock on this table. */
  162.   for(pIter=pBt->pLock; pIter; pIter=pIter->pNext){
  163.     if( pIter->iTable==iTable && pIter->pBtree==p ){
  164.       pLock = pIter;
  165.       break;
  166.     }
  167.   }
  168.   /* If the above search did not find a BtLock struct associating Btree p
  169.   ** with table iTable, allocate one and link it into the list.
  170.   */
  171.   if( !pLock ){
  172.     pLock = (BtLock *)sqlite3MallocZero(sizeof(BtLock));
  173.     if( !pLock ){
  174.       return SQLITE_NOMEM;
  175.     }
  176.     pLock->iTable = iTable;
  177.     pLock->pBtree = p;
  178.     pLock->pNext = pBt->pLock;
  179.     pBt->pLock = pLock;
  180.   }
  181.   /* Set the BtLock.eLock variable to the maximum of the current lock
  182.   ** and the requested lock. This means if a write-lock was already held
  183.   ** and a read-lock requested, we don't incorrectly downgrade the lock.
  184.   */
  185.   assert( WRITE_LOCK>READ_LOCK );
  186.   if( eLock>pLock->eLock ){
  187.     pLock->eLock = eLock;
  188.   }
  189.   return SQLITE_OK;
  190. }
  191. #endif /* !SQLITE_OMIT_SHARED_CACHE */
  192. #ifndef SQLITE_OMIT_SHARED_CACHE
  193. /*
  194. ** Release all the table locks (locks obtained via calls to the lockTable()
  195. ** procedure) held by Btree handle p.
  196. */
  197. static void unlockAllTables(Btree *p){
  198.   BtShared *pBt = p->pBt;
  199.   BtLock **ppIter = &pBt->pLock;
  200.   assert( sqlite3BtreeHoldsMutex(p) );
  201.   assert( p->sharable || 0==*ppIter );
  202.   while( *ppIter ){
  203.     BtLock *pLock = *ppIter;
  204.     assert( pBt->pExclusive==0 || pBt->pExclusive==pLock->pBtree );
  205.     if( pLock->pBtree==p ){
  206.       *ppIter = pLock->pNext;
  207.       sqlite3_free(pLock);
  208.     }else{
  209.       ppIter = &pLock->pNext;
  210.     }
  211.   }
  212.   if( pBt->pExclusive==p ){
  213.     pBt->pExclusive = 0;
  214.   }
  215. }
  216. #endif /* SQLITE_OMIT_SHARED_CACHE */
  217. static void releasePage(MemPage *pPage);  /* Forward reference */
  218. /*
  219. ** Verify that the cursor holds a mutex on the BtShared
  220. */
  221. #ifndef NDEBUG
  222. static int cursorHoldsMutex(BtCursor *p){
  223.   return sqlite3_mutex_held(p->pBt->mutex);
  224. }
  225. #endif
  226. #ifndef SQLITE_OMIT_INCRBLOB
  227. /*
  228. ** Invalidate the overflow page-list cache for cursor pCur, if any.
  229. */
  230. static void invalidateOverflowCache(BtCursor *pCur){
  231.   assert( cursorHoldsMutex(pCur) );
  232.   sqlite3_free(pCur->aOverflow);
  233.   pCur->aOverflow = 0;
  234. }
  235. /*
  236. ** Invalidate the overflow page-list cache for all cursors opened
  237. ** on the shared btree structure pBt.
  238. */
  239. static void invalidateAllOverflowCache(BtShared *pBt){
  240.   BtCursor *p;
  241.   assert( sqlite3_mutex_held(pBt->mutex) );
  242.   for(p=pBt->pCursor; p; p=p->pNext){
  243.     invalidateOverflowCache(p);
  244.   }
  245. }
  246. #else
  247.   #define invalidateOverflowCache(x)
  248.   #define invalidateAllOverflowCache(x)
  249. #endif
  250. /*
  251. ** Save the current cursor position in the variables BtCursor.nKey 
  252. ** and BtCursor.pKey. The cursor's state is set to CURSOR_REQUIRESEEK.
  253. */
  254. static int saveCursorPosition(BtCursor *pCur){
  255.   int rc;
  256.   assert( CURSOR_VALID==pCur->eState );
  257.   assert( 0==pCur->pKey );
  258.   assert( cursorHoldsMutex(pCur) );
  259.   rc = sqlite3BtreeKeySize(pCur, &pCur->nKey);
  260.   /* If this is an intKey table, then the above call to BtreeKeySize()
  261.   ** stores the integer key in pCur->nKey. In this case this value is
  262.   ** all that is required. Otherwise, if pCur is not open on an intKey
  263.   ** table, then malloc space for and store the pCur->nKey bytes of key 
  264.   ** data.
  265.   */
  266.   if( rc==SQLITE_OK && 0==pCur->pPage->intKey){
  267.     void *pKey = sqlite3_malloc(pCur->nKey);
  268.     if( pKey ){
  269.       rc = sqlite3BtreeKey(pCur, 0, pCur->nKey, pKey);
  270.       if( rc==SQLITE_OK ){
  271.         pCur->pKey = pKey;
  272.       }else{
  273.         sqlite3_free(pKey);
  274.       }
  275.     }else{
  276.       rc = SQLITE_NOMEM;
  277.     }
  278.   }
  279.   assert( !pCur->pPage->intKey || !pCur->pKey );
  280.   if( rc==SQLITE_OK ){
  281.     releasePage(pCur->pPage);
  282.     pCur->pPage = 0;
  283.     pCur->eState = CURSOR_REQUIRESEEK;
  284.   }
  285.   invalidateOverflowCache(pCur);
  286.   return rc;
  287. }
  288. /*
  289. ** Save the positions of all cursors except pExcept open on the table 
  290. ** with root-page iRoot. Usually, this is called just before cursor
  291. ** pExcept is used to modify the table (BtreeDelete() or BtreeInsert()).
  292. */
  293. static int saveAllCursors(BtShared *pBt, Pgno iRoot, BtCursor *pExcept){
  294.   BtCursor *p;
  295.   assert( sqlite3_mutex_held(pBt->mutex) );
  296.   assert( pExcept==0 || pExcept->pBt==pBt );
  297.   for(p=pBt->pCursor; p; p=p->pNext){
  298.     if( p!=pExcept && (0==iRoot || p->pgnoRoot==iRoot) && 
  299.         p->eState==CURSOR_VALID ){
  300.       int rc = saveCursorPosition(p);
  301.       if( SQLITE_OK!=rc ){
  302.         return rc;
  303.       }
  304.     }
  305.   }
  306.   return SQLITE_OK;
  307. }
  308. /*
  309. ** Clear the current cursor position.
  310. */
  311. static void clearCursorPosition(BtCursor *pCur){
  312.   assert( cursorHoldsMutex(pCur) );
  313.   sqlite3_free(pCur->pKey);
  314.   pCur->pKey = 0;
  315.   pCur->eState = CURSOR_INVALID;
  316. }
  317. /*
  318. ** Restore the cursor to the position it was in (or as close to as possible)
  319. ** when saveCursorPosition() was called. Note that this call deletes the 
  320. ** saved position info stored by saveCursorPosition(), so there can be
  321. ** at most one effective restoreOrClearCursorPosition() call after each 
  322. ** saveCursorPosition().
  323. **
  324. ** If the second argument argument - doSeek - is false, then instead of 
  325. ** returning the cursor to its saved position, any saved position is deleted
  326. ** and the cursor state set to CURSOR_INVALID.
  327. */
  328. int sqlite3BtreeRestoreOrClearCursorPosition(BtCursor *pCur){
  329.   int rc;
  330.   assert( cursorHoldsMutex(pCur) );
  331.   assert( pCur->eState>=CURSOR_REQUIRESEEK );
  332.   if( pCur->eState==CURSOR_FAULT ){
  333.     return pCur->skip;
  334.   }
  335. #ifndef SQLITE_OMIT_INCRBLOB
  336.   if( pCur->isIncrblobHandle ){
  337.     return SQLITE_ABORT;
  338.   }
  339. #endif
  340.   pCur->eState = CURSOR_INVALID;
  341.   rc = sqlite3BtreeMoveto(pCur, pCur->pKey, 0, pCur->nKey, 0, &pCur->skip);
  342.   if( rc==SQLITE_OK ){
  343.     sqlite3_free(pCur->pKey);
  344.     pCur->pKey = 0;
  345.     assert( pCur->eState==CURSOR_VALID || pCur->eState==CURSOR_INVALID );
  346.   }
  347.   return rc;
  348. }
  349. #define restoreOrClearCursorPosition(p) 
  350.   (p->eState>=CURSOR_REQUIRESEEK ? 
  351.          sqlite3BtreeRestoreOrClearCursorPosition(p) : 
  352.          SQLITE_OK)
  353. #ifndef SQLITE_OMIT_AUTOVACUUM
  354. /*
  355. ** Given a page number of a regular database page, return the page
  356. ** number for the pointer-map page that contains the entry for the
  357. ** input page number.
  358. */
  359. static Pgno ptrmapPageno(BtShared *pBt, Pgno pgno){
  360.   int nPagesPerMapPage, iPtrMap, ret;
  361.   assert( sqlite3_mutex_held(pBt->mutex) );
  362.   nPagesPerMapPage = (pBt->usableSize/5)+1;
  363.   iPtrMap = (pgno-2)/nPagesPerMapPage;
  364.   ret = (iPtrMap*nPagesPerMapPage) + 2; 
  365.   if( ret==PENDING_BYTE_PAGE(pBt) ){
  366.     ret++;
  367.   }
  368.   return ret;
  369. }
  370. /*
  371. ** Write an entry into the pointer map.
  372. **
  373. ** This routine updates the pointer map entry for page number 'key'
  374. ** so that it maps to type 'eType' and parent page number 'pgno'.
  375. ** An error code is returned if something goes wrong, otherwise SQLITE_OK.
  376. */
  377. static int ptrmapPut(BtShared *pBt, Pgno key, u8 eType, Pgno parent){
  378.   DbPage *pDbPage;  /* The pointer map page */
  379.   u8 *pPtrmap;      /* The pointer map data */
  380.   Pgno iPtrmap;     /* The pointer map page number */
  381.   int offset;       /* Offset in pointer map page */
  382.   int rc;
  383.   assert( sqlite3_mutex_held(pBt->mutex) );
  384.   /* The master-journal page number must never be used as a pointer map page */
  385.   assert( 0==PTRMAP_ISPAGE(pBt, PENDING_BYTE_PAGE(pBt)) );
  386.   assert( pBt->autoVacuum );
  387.   if( key==0 ){
  388.     return SQLITE_CORRUPT_BKPT;
  389.   }
  390.   iPtrmap = PTRMAP_PAGENO(pBt, key);
  391.   rc = sqlite3PagerGet(pBt->pPager, iPtrmap, &pDbPage);
  392.   if( rc!=SQLITE_OK ){
  393.     return rc;
  394.   }
  395.   offset = PTRMAP_PTROFFSET(pBt, key);
  396.   pPtrmap = (u8 *)sqlite3PagerGetData(pDbPage);
  397.   if( eType!=pPtrmap[offset] || get4byte(&pPtrmap[offset+1])!=parent ){
  398.     TRACE(("PTRMAP_UPDATE: %d->(%d,%d)n", key, eType, parent));
  399.     rc = sqlite3PagerWrite(pDbPage);
  400.     if( rc==SQLITE_OK ){
  401.       pPtrmap[offset] = eType;
  402.       put4byte(&pPtrmap[offset+1], parent);
  403.     }
  404.   }
  405.   sqlite3PagerUnref(pDbPage);
  406.   return rc;
  407. }
  408. /*
  409. ** Read an entry from the pointer map.
  410. **
  411. ** This routine retrieves the pointer map entry for page 'key', writing
  412. ** the type and parent page number to *pEType and *pPgno respectively.
  413. ** An error code is returned if something goes wrong, otherwise SQLITE_OK.
  414. */
  415. static int ptrmapGet(BtShared *pBt, Pgno key, u8 *pEType, Pgno *pPgno){
  416.   DbPage *pDbPage;   /* The pointer map page */
  417.   int iPtrmap;       /* Pointer map page index */
  418.   u8 *pPtrmap;       /* Pointer map page data */
  419.   int offset;        /* Offset of entry in pointer map */
  420.   int rc;
  421.   assert( sqlite3_mutex_held(pBt->mutex) );
  422.   iPtrmap = PTRMAP_PAGENO(pBt, key);
  423.   rc = sqlite3PagerGet(pBt->pPager, iPtrmap, &pDbPage);
  424.   if( rc!=0 ){
  425.     return rc;
  426.   }
  427.   pPtrmap = (u8 *)sqlite3PagerGetData(pDbPage);
  428.   offset = PTRMAP_PTROFFSET(pBt, key);
  429.   assert( pEType!=0 );
  430.   *pEType = pPtrmap[offset];
  431.   if( pPgno ) *pPgno = get4byte(&pPtrmap[offset+1]);
  432.   sqlite3PagerUnref(pDbPage);
  433.   if( *pEType<1 || *pEType>5 ) return SQLITE_CORRUPT_BKPT;
  434.   return SQLITE_OK;
  435. }
  436. #endif /* SQLITE_OMIT_AUTOVACUUM */
  437. /*
  438. ** Given a btree page and a cell index (0 means the first cell on
  439. ** the page, 1 means the second cell, and so forth) return a pointer
  440. ** to the cell content.
  441. **
  442. ** This routine works only for pages that do not contain overflow cells.
  443. */
  444. #define findCell(pPage, iCell) 
  445.   ((pPage)->aData + get2byte(&(pPage)->aData[(pPage)->cellOffset+2*(iCell)]))
  446. #ifdef SQLITE_TEST
  447. u8 *sqlite3BtreeFindCell(MemPage *pPage, int iCell){
  448.   assert( iCell>=0 );
  449.   assert( iCell<get2byte(&pPage->aData[pPage->hdrOffset+3]) );
  450.   return findCell(pPage, iCell);
  451. }
  452. #endif
  453. /*
  454. ** This a more complex version of sqlite3BtreeFindCell() that works for
  455. ** pages that do contain overflow cells.  See insert
  456. */
  457. static u8 *findOverflowCell(MemPage *pPage, int iCell){
  458.   int i;
  459.   assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  460.   for(i=pPage->nOverflow-1; i>=0; i--){
  461.     int k;
  462.     struct _OvflCell *pOvfl;
  463.     pOvfl = &pPage->aOvfl[i];
  464.     k = pOvfl->idx;
  465.     if( k<=iCell ){
  466.       if( k==iCell ){
  467.         return pOvfl->pCell;
  468.       }
  469.       iCell--;
  470.     }
  471.   }
  472.   return findCell(pPage, iCell);
  473. }
  474. /*
  475. ** Parse a cell content block and fill in the CellInfo structure.  There
  476. ** are two versions of this function.  sqlite3BtreeParseCell() takes a 
  477. ** cell index as the second argument and sqlite3BtreeParseCellPtr() 
  478. ** takes a pointer to the body of the cell as its second argument.
  479. **
  480. ** Within this file, the parseCell() macro can be called instead of
  481. ** sqlite3BtreeParseCellPtr(). Using some compilers, this will be faster.
  482. */
  483. void sqlite3BtreeParseCellPtr(
  484.   MemPage *pPage,         /* Page containing the cell */
  485.   u8 *pCell,              /* Pointer to the cell text. */
  486.   CellInfo *pInfo         /* Fill in this structure */
  487. ){
  488.   int n;                  /* Number bytes in cell content header */
  489.   u32 nPayload;           /* Number of bytes of cell payload */
  490.   assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  491.   pInfo->pCell = pCell;
  492.   assert( pPage->leaf==0 || pPage->leaf==1 );
  493.   n = pPage->childPtrSize;
  494.   assert( n==4-4*pPage->leaf );
  495.   if( pPage->hasData ){
  496.     n += getVarint32(&pCell[n], &nPayload);
  497.   }else{
  498.     nPayload = 0;
  499.   }
  500.   pInfo->nData = nPayload;
  501.   if( pPage->intKey ){
  502.     n += getVarint(&pCell[n], (u64 *)&pInfo->nKey);
  503.   }else{
  504.     u32 x;
  505.     n += getVarint32(&pCell[n], &x);
  506.     pInfo->nKey = x;
  507.     nPayload += x;
  508.   }
  509.   pInfo->nPayload = nPayload;
  510.   pInfo->nHeader = n;
  511.   if( nPayload<=pPage->maxLocal ){
  512.     /* This is the (easy) common case where the entire payload fits
  513.     ** on the local page.  No overflow is required.
  514.     */
  515.     int nSize;          /* Total size of cell content in bytes */
  516.     pInfo->nLocal = nPayload;
  517.     pInfo->iOverflow = 0;
  518.     nSize = nPayload + n;
  519.     if( nSize<4 ){
  520.       nSize = 4;        /* Minimum cell size is 4 */
  521.     }
  522.     pInfo->nSize = nSize;
  523.   }else{
  524.     /* If the payload will not fit completely on the local page, we have
  525.     ** to decide how much to store locally and how much to spill onto
  526.     ** overflow pages.  The strategy is to minimize the amount of unused
  527.     ** space on overflow pages while keeping the amount of local storage
  528.     ** in between minLocal and maxLocal.
  529.     **
  530.     ** Warning:  changing the way overflow payload is distributed in any
  531.     ** way will result in an incompatible file format.
  532.     */
  533.     int minLocal;  /* Minimum amount of payload held locally */
  534.     int maxLocal;  /* Maximum amount of payload held locally */
  535.     int surplus;   /* Overflow payload available for local storage */
  536.     minLocal = pPage->minLocal;
  537.     maxLocal = pPage->maxLocal;
  538.     surplus = minLocal + (nPayload - minLocal)%(pPage->pBt->usableSize - 4);
  539.     if( surplus <= maxLocal ){
  540.       pInfo->nLocal = surplus;
  541.     }else{
  542.       pInfo->nLocal = minLocal;
  543.     }
  544.     pInfo->iOverflow = pInfo->nLocal + n;
  545.     pInfo->nSize = pInfo->iOverflow + 4;
  546.   }
  547. }
  548. #define parseCell(pPage, iCell, pInfo) 
  549.   sqlite3BtreeParseCellPtr((pPage), findCell((pPage), (iCell)), (pInfo))
  550. void sqlite3BtreeParseCell(
  551.   MemPage *pPage,         /* Page containing the cell */
  552.   int iCell,              /* The cell index.  First cell is 0 */
  553.   CellInfo *pInfo         /* Fill in this structure */
  554. ){
  555.   parseCell(pPage, iCell, pInfo);
  556. }
  557. /*
  558. ** Compute the total number of bytes that a Cell needs in the cell
  559. ** data area of the btree-page.  The return number includes the cell
  560. ** data header and the local payload, but not any overflow page or
  561. ** the space used by the cell pointer.
  562. */
  563. #ifndef NDEBUG
  564. static u16 cellSize(MemPage *pPage, int iCell){
  565.   CellInfo info;
  566.   sqlite3BtreeParseCell(pPage, iCell, &info);
  567.   return info.nSize;
  568. }
  569. #endif
  570. static u16 cellSizePtr(MemPage *pPage, u8 *pCell){
  571.   CellInfo info;
  572.   sqlite3BtreeParseCellPtr(pPage, pCell, &info);
  573.   return info.nSize;
  574. }
  575. #ifndef SQLITE_OMIT_AUTOVACUUM
  576. /*
  577. ** If the cell pCell, part of page pPage contains a pointer
  578. ** to an overflow page, insert an entry into the pointer-map
  579. ** for the overflow page.
  580. */
  581. static int ptrmapPutOvflPtr(MemPage *pPage, u8 *pCell){
  582.   if( pCell ){
  583.     CellInfo info;
  584.     sqlite3BtreeParseCellPtr(pPage, pCell, &info);
  585.     assert( (info.nData+(pPage->intKey?0:info.nKey))==info.nPayload );
  586.     if( (info.nData+(pPage->intKey?0:info.nKey))>info.nLocal ){
  587.       Pgno ovfl = get4byte(&pCell[info.iOverflow]);
  588.       return ptrmapPut(pPage->pBt, ovfl, PTRMAP_OVERFLOW1, pPage->pgno);
  589.     }
  590.   }
  591.   return SQLITE_OK;
  592. }
  593. /*
  594. ** If the cell with index iCell on page pPage contains a pointer
  595. ** to an overflow page, insert an entry into the pointer-map
  596. ** for the overflow page.
  597. */
  598. static int ptrmapPutOvfl(MemPage *pPage, int iCell){
  599.   u8 *pCell;
  600.   assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  601.   pCell = findOverflowCell(pPage, iCell);
  602.   return ptrmapPutOvflPtr(pPage, pCell);
  603. }
  604. #endif
  605. /*
  606. ** Defragment the page given.  All Cells are moved to the
  607. ** end of the page and all free space is collected into one
  608. ** big FreeBlk that occurs in between the header and cell
  609. ** pointer array and the cell content area.
  610. */
  611. static int defragmentPage(MemPage *pPage){
  612.   int i;                     /* Loop counter */
  613.   int pc;                    /* Address of a i-th cell */
  614.   int addr;                  /* Offset of first byte after cell pointer array */
  615.   int hdr;                   /* Offset to the page header */
  616.   int size;                  /* Size of a cell */
  617.   int usableSize;            /* Number of usable bytes on a page */
  618.   int cellOffset;            /* Offset to the cell pointer array */
  619.   int brk;                   /* Offset to the cell content area */
  620.   int nCell;                 /* Number of cells on the page */
  621.   unsigned char *data;       /* The page data */
  622.   unsigned char *temp;       /* Temp area for cell content */
  623.   assert( sqlite3PagerIswriteable(pPage->pDbPage) );
  624.   assert( pPage->pBt!=0 );
  625.   assert( pPage->pBt->usableSize <= SQLITE_MAX_PAGE_SIZE );
  626.   assert( pPage->nOverflow==0 );
  627.   assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  628.   temp = sqlite3PagerTempSpace(pPage->pBt->pPager);
  629.   data = pPage->aData;
  630.   hdr = pPage->hdrOffset;
  631.   cellOffset = pPage->cellOffset;
  632.   nCell = pPage->nCell;
  633.   assert( nCell==get2byte(&data[hdr+3]) );
  634.   usableSize = pPage->pBt->usableSize;
  635.   brk = get2byte(&data[hdr+5]);
  636.   memcpy(&temp[brk], &data[brk], usableSize - brk);
  637.   brk = usableSize;
  638.   for(i=0; i<nCell; i++){
  639.     u8 *pAddr;     /* The i-th cell pointer */
  640.     pAddr = &data[cellOffset + i*2];
  641.     pc = get2byte(pAddr);
  642.     assert( pc<pPage->pBt->usableSize );
  643.     size = cellSizePtr(pPage, &temp[pc]);
  644.     brk -= size;
  645.     memcpy(&data[brk], &temp[pc], size);
  646.     put2byte(pAddr, brk);
  647.   }
  648.   assert( brk>=cellOffset+2*nCell );
  649.   put2byte(&data[hdr+5], brk);
  650.   data[hdr+1] = 0;
  651.   data[hdr+2] = 0;
  652.   data[hdr+7] = 0;
  653.   addr = cellOffset+2*nCell;
  654.   memset(&data[addr], 0, brk-addr);
  655.   return SQLITE_OK;
  656. }
  657. /*
  658. ** Allocate nByte bytes of space on a page.
  659. **
  660. ** Return the index into pPage->aData[] of the first byte of
  661. ** the new allocation. Or return 0 if there is not enough free
  662. ** space on the page to satisfy the allocation request.
  663. **
  664. ** If the page contains nBytes of free space but does not contain
  665. ** nBytes of contiguous free space, then this routine automatically
  666. ** calls defragementPage() to consolidate all free space before 
  667. ** allocating the new chunk.
  668. */
  669. static int allocateSpace(MemPage *pPage, int nByte){
  670.   int addr, pc, hdr;
  671.   int size;
  672.   int nFrag;
  673.   int top;
  674.   int nCell;
  675.   int cellOffset;
  676.   unsigned char *data;
  677.   
  678.   data = pPage->aData;
  679.   assert( sqlite3PagerIswriteable(pPage->pDbPage) );
  680.   assert( pPage->pBt );
  681.   assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  682.   if( nByte<4 ) nByte = 4;
  683.   if( pPage->nFree<nByte || pPage->nOverflow>0 ) return 0;
  684.   pPage->nFree -= nByte;
  685.   hdr = pPage->hdrOffset;
  686.   nFrag = data[hdr+7];
  687.   if( nFrag<60 ){
  688.     /* Search the freelist looking for a slot big enough to satisfy the
  689.     ** space request. */
  690.     addr = hdr+1;
  691.     while( (pc = get2byte(&data[addr]))>0 ){
  692.       size = get2byte(&data[pc+2]);
  693.       if( size>=nByte ){
  694.         if( size<nByte+4 ){
  695.           memcpy(&data[addr], &data[pc], 2);
  696.           data[hdr+7] = nFrag + size - nByte;
  697.           return pc;
  698.         }else{
  699.           put2byte(&data[pc+2], size-nByte);
  700.           return pc + size - nByte;
  701.         }
  702.       }
  703.       addr = pc;
  704.     }
  705.   }
  706.   /* Allocate memory from the gap in between the cell pointer array
  707.   ** and the cell content area.
  708.   */
  709.   top = get2byte(&data[hdr+5]);
  710.   nCell = get2byte(&data[hdr+3]);
  711.   cellOffset = pPage->cellOffset;
  712.   if( nFrag>=60 || cellOffset + 2*nCell > top - nByte ){
  713.     if( defragmentPage(pPage) ) return 0;
  714.     top = get2byte(&data[hdr+5]);
  715.   }
  716.   top -= nByte;
  717.   assert( cellOffset + 2*nCell <= top );
  718.   put2byte(&data[hdr+5], top);
  719.   return top;
  720. }
  721. /*
  722. ** Return a section of the pPage->aData to the freelist.
  723. ** The first byte of the new free block is pPage->aDisk[start]
  724. ** and the size of the block is "size" bytes.
  725. **
  726. ** Most of the effort here is involved in coalesing adjacent
  727. ** free blocks into a single big free block.
  728. */
  729. static void freeSpace(MemPage *pPage, int start, int size){
  730.   int addr, pbegin, hdr;
  731.   unsigned char *data = pPage->aData;
  732.   assert( pPage->pBt!=0 );
  733.   assert( sqlite3PagerIswriteable(pPage->pDbPage) );
  734.   assert( start>=pPage->hdrOffset+6+(pPage->leaf?0:4) );
  735.   assert( (start + size)<=pPage->pBt->usableSize );
  736.   assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  737.   if( size<4 ) size = 4;
  738. #ifdef SQLITE_SECURE_DELETE
  739.   /* Overwrite deleted information with zeros when the SECURE_DELETE 
  740.   ** option is enabled at compile-time */
  741.   memset(&data[start], 0, size);
  742. #endif
  743.   /* Add the space back into the linked list of freeblocks */
  744.   hdr = pPage->hdrOffset;
  745.   addr = hdr + 1;
  746.   while( (pbegin = get2byte(&data[addr]))<start && pbegin>0 ){
  747.     assert( pbegin<=pPage->pBt->usableSize-4 );
  748.     assert( pbegin>addr );
  749.     addr = pbegin;
  750.   }
  751.   assert( pbegin<=pPage->pBt->usableSize-4 );
  752.   assert( pbegin>addr || pbegin==0 );
  753.   put2byte(&data[addr], start);
  754.   put2byte(&data[start], pbegin);
  755.   put2byte(&data[start+2], size);
  756.   pPage->nFree += size;
  757.   /* Coalesce adjacent free blocks */
  758.   addr = pPage->hdrOffset + 1;
  759.   while( (pbegin = get2byte(&data[addr]))>0 ){
  760.     int pnext, psize;
  761.     assert( pbegin>addr );
  762.     assert( pbegin<=pPage->pBt->usableSize-4 );
  763.     pnext = get2byte(&data[pbegin]);
  764.     psize = get2byte(&data[pbegin+2]);
  765.     if( pbegin + psize + 3 >= pnext && pnext>0 ){
  766.       int frag = pnext - (pbegin+psize);
  767.       assert( frag<=data[pPage->hdrOffset+7] );
  768.       data[pPage->hdrOffset+7] -= frag;
  769.       put2byte(&data[pbegin], get2byte(&data[pnext]));
  770.       put2byte(&data[pbegin+2], pnext+get2byte(&data[pnext+2])-pbegin);
  771.     }else{
  772.       addr = pbegin;
  773.     }
  774.   }
  775.   /* If the cell content area begins with a freeblock, remove it. */
  776.   if( data[hdr+1]==data[hdr+5] && data[hdr+2]==data[hdr+6] ){
  777.     int top;
  778.     pbegin = get2byte(&data[hdr+1]);
  779.     memcpy(&data[hdr+1], &data[pbegin], 2);
  780.     top = get2byte(&data[hdr+5]);
  781.     put2byte(&data[hdr+5], top + get2byte(&data[pbegin+2]));
  782.   }
  783. }
  784. /*
  785. ** Decode the flags byte (the first byte of the header) for a page
  786. ** and initialize fields of the MemPage structure accordingly.
  787. */
  788. static void decodeFlags(MemPage *pPage, int flagByte){
  789.   BtShared *pBt;     /* A copy of pPage->pBt */
  790.   assert( pPage->hdrOffset==(pPage->pgno==1 ? 100 : 0) );
  791.   assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  792.   pPage->intKey = (flagByte & (PTF_INTKEY|PTF_LEAFDATA))!=0;
  793.   pPage->zeroData = (flagByte & PTF_ZERODATA)!=0;
  794.   pPage->leaf = (flagByte & PTF_LEAF)!=0;
  795.   pPage->childPtrSize = 4*(pPage->leaf==0);
  796.   pBt = pPage->pBt;
  797.   if( flagByte & PTF_LEAFDATA ){
  798.     pPage->leafData = 1;
  799.     pPage->maxLocal = pBt->maxLeaf;
  800.     pPage->minLocal = pBt->minLeaf;
  801.   }else{
  802.     pPage->leafData = 0;
  803.     pPage->maxLocal = pBt->maxLocal;
  804.     pPage->minLocal = pBt->minLocal;
  805.   }
  806.   pPage->hasData = !(pPage->zeroData || (!pPage->leaf && pPage->leafData));
  807. }
  808. /*
  809. ** Initialize the auxiliary information for a disk block.
  810. **
  811. ** The pParent parameter must be a pointer to the MemPage which
  812. ** is the parent of the page being initialized.  The root of a
  813. ** BTree has no parent and so for that page, pParent==NULL.
  814. **
  815. ** Return SQLITE_OK on success.  If we see that the page does
  816. ** not contain a well-formed database page, then return 
  817. ** SQLITE_CORRUPT.  Note that a return of SQLITE_OK does not
  818. ** guarantee that the page is well-formed.  It only shows that
  819. ** we failed to detect any corruption.
  820. */
  821. int sqlite3BtreeInitPage(
  822.   MemPage *pPage,        /* The page to be initialized */
  823.   MemPage *pParent       /* The parent.  Might be NULL */
  824. ){
  825.   int pc;            /* Address of a freeblock within pPage->aData[] */
  826.   int hdr;           /* Offset to beginning of page header */
  827.   u8 *data;          /* Equal to pPage->aData */
  828.   BtShared *pBt;        /* The main btree structure */
  829.   int usableSize;    /* Amount of usable space on each page */
  830.   int cellOffset;    /* Offset from start of page to first cell pointer */
  831.   int nFree;         /* Number of unused bytes on the page */
  832.   int top;           /* First byte of the cell content area */
  833.   pBt = pPage->pBt;
  834.   assert( pBt!=0 );
  835.   assert( pParent==0 || pParent->pBt==pBt );
  836.   assert( sqlite3_mutex_held(pBt->mutex) );
  837.   assert( pPage->pgno==sqlite3PagerPagenumber(pPage->pDbPage) );
  838.   assert( pPage == sqlite3PagerGetExtra(pPage->pDbPage) );
  839.   assert( pPage->aData == sqlite3PagerGetData(pPage->pDbPage) );
  840.   if( pPage->pParent!=pParent && (pPage->pParent!=0 || pPage->isInit) ){
  841.     /* The parent page should never change unless the file is corrupt */
  842.     return SQLITE_CORRUPT_BKPT;
  843.   }
  844.   if( pPage->isInit ) return SQLITE_OK;
  845.   if( pPage->pParent==0 && pParent!=0 ){
  846.     pPage->pParent = pParent;
  847.     sqlite3PagerRef(pParent->pDbPage);
  848.   }
  849.   hdr = pPage->hdrOffset;
  850.   data = pPage->aData;
  851.   decodeFlags(pPage, data[hdr]);
  852.   pPage->nOverflow = 0;
  853.   pPage->idxShift = 0;
  854.   usableSize = pBt->usableSize;
  855.   pPage->cellOffset = cellOffset = hdr + 12 - 4*pPage->leaf;
  856.   top = get2byte(&data[hdr+5]);
  857.   pPage->nCell = get2byte(&data[hdr+3]);
  858.   if( pPage->nCell>MX_CELL(pBt) ){
  859.     /* To many cells for a single page.  The page must be corrupt */
  860.     return SQLITE_CORRUPT_BKPT;
  861.   }
  862.   if( pPage->nCell==0 && pParent!=0 && pParent->pgno!=1 ){
  863.     /* All pages must have at least one cell, except for root pages */
  864.     return SQLITE_CORRUPT_BKPT;
  865.   }
  866.   /* Compute the total free space on the page */
  867.   pc = get2byte(&data[hdr+1]);
  868.   nFree = data[hdr+7] + top - (cellOffset + 2*pPage->nCell);
  869.   while( pc>0 ){
  870.     int next, size;
  871.     if( pc>usableSize-4 ){
  872.       /* Free block is off the page */
  873.       return SQLITE_CORRUPT_BKPT; 
  874.     }
  875.     next = get2byte(&data[pc]);
  876.     size = get2byte(&data[pc+2]);
  877.     if( next>0 && next<=pc+size+3 ){
  878.       /* Free blocks must be in accending order */
  879.       return SQLITE_CORRUPT_BKPT; 
  880.     }
  881.     nFree += size;
  882.     pc = next;
  883.   }
  884.   pPage->nFree = nFree;
  885.   if( nFree>=usableSize ){
  886.     /* Free space cannot exceed total page size */
  887.     return SQLITE_CORRUPT_BKPT; 
  888.   }
  889.   pPage->isInit = 1;
  890.   return SQLITE_OK;
  891. }
  892. /*
  893. ** Set up a raw page so that it looks like a database page holding
  894. ** no entries.
  895. */
  896. static void zeroPage(MemPage *pPage, int flags){
  897.   unsigned char *data = pPage->aData;
  898.   BtShared *pBt = pPage->pBt;
  899.   int hdr = pPage->hdrOffset;
  900.   int first;
  901.   assert( sqlite3PagerPagenumber(pPage->pDbPage)==pPage->pgno );
  902.   assert( sqlite3PagerGetExtra(pPage->pDbPage) == (void*)pPage );
  903.   assert( sqlite3PagerGetData(pPage->pDbPage) == data );
  904.   assert( sqlite3PagerIswriteable(pPage->pDbPage) );
  905.   assert( sqlite3_mutex_held(pBt->mutex) );
  906.   memset(&data[hdr], 0, pBt->usableSize - hdr);
  907.   data[hdr] = flags;
  908.   first = hdr + 8 + 4*((flags&PTF_LEAF)==0);
  909.   memset(&data[hdr+1], 0, 4);
  910.   data[hdr+7] = 0;
  911.   put2byte(&data[hdr+5], pBt->usableSize);
  912.   pPage->nFree = pBt->usableSize - first;
  913.   decodeFlags(pPage, flags);
  914.   pPage->hdrOffset = hdr;
  915.   pPage->cellOffset = first;
  916.   pPage->nOverflow = 0;
  917.   pPage->idxShift = 0;
  918.   pPage->nCell = 0;
  919.   pPage->isInit = 1;
  920. }
  921. /*
  922. ** Get a page from the pager.  Initialize the MemPage.pBt and
  923. ** MemPage.aData elements if needed.
  924. **
  925. ** If the noContent flag is set, it means that we do not care about
  926. ** the content of the page at this time.  So do not go to the disk
  927. ** to fetch the content.  Just fill in the content with zeros for now.
  928. ** If in the future we call sqlite3PagerWrite() on this page, that
  929. ** means we have started to be concerned about content and the disk
  930. ** read should occur at that point.
  931. */
  932. int sqlite3BtreeGetPage(
  933.   BtShared *pBt,       /* The btree */
  934.   Pgno pgno,           /* Number of the page to fetch */
  935.   MemPage **ppPage,    /* Return the page in this parameter */
  936.   int noContent        /* Do not load page content if true */
  937. ){
  938.   int rc;
  939.   MemPage *pPage;
  940.   DbPage *pDbPage;
  941.   assert( sqlite3_mutex_held(pBt->mutex) );
  942.   rc = sqlite3PagerAcquire(pBt->pPager, pgno, (DbPage**)&pDbPage, noContent);
  943.   if( rc ) return rc;
  944.   pPage = (MemPage *)sqlite3PagerGetExtra(pDbPage);
  945.   pPage->aData = sqlite3PagerGetData(pDbPage);
  946.   pPage->pDbPage = pDbPage;
  947.   pPage->pBt = pBt;
  948.   pPage->pgno = pgno;
  949.   pPage->hdrOffset = pPage->pgno==1 ? 100 : 0;
  950.   *ppPage = pPage;
  951.   return SQLITE_OK;
  952. }
  953. /*
  954. ** Get a page from the pager and initialize it.  This routine
  955. ** is just a convenience wrapper around separate calls to
  956. ** sqlite3BtreeGetPage() and sqlite3BtreeInitPage().
  957. */
  958. static int getAndInitPage(
  959.   BtShared *pBt,          /* The database file */
  960.   Pgno pgno,           /* Number of the page to get */
  961.   MemPage **ppPage,    /* Write the page pointer here */
  962.   MemPage *pParent     /* Parent of the page */
  963. ){
  964.   int rc;
  965.   assert( sqlite3_mutex_held(pBt->mutex) );
  966.   if( pgno==0 ){
  967.     return SQLITE_CORRUPT_BKPT; 
  968.   }
  969.   rc = sqlite3BtreeGetPage(pBt, pgno, ppPage, 0);
  970.   if( rc==SQLITE_OK && (*ppPage)->isInit==0 ){
  971.     rc = sqlite3BtreeInitPage(*ppPage, pParent);
  972.   }
  973.   return rc;
  974. }
  975. /*
  976. ** Release a MemPage.  This should be called once for each prior
  977. ** call to sqlite3BtreeGetPage.
  978. */
  979. static void releasePage(MemPage *pPage){
  980.   if( pPage ){
  981.     assert( pPage->aData );
  982.     assert( pPage->pBt );
  983.     assert( sqlite3PagerGetExtra(pPage->pDbPage) == (void*)pPage );
  984.     assert( sqlite3PagerGetData(pPage->pDbPage)==pPage->aData );
  985.     assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  986.     sqlite3PagerUnref(pPage->pDbPage);
  987.   }
  988. }
  989. /*
  990. ** This routine is called when the reference count for a page
  991. ** reaches zero.  We need to unref the pParent pointer when that
  992. ** happens.
  993. */
  994. static void pageDestructor(DbPage *pData, int pageSize){
  995.   MemPage *pPage;
  996.   assert( (pageSize & 7)==0 );
  997.   pPage = (MemPage *)sqlite3PagerGetExtra(pData);
  998.   assert( pPage->isInit==0 || sqlite3_mutex_held(pPage->pBt->mutex) );
  999.   if( pPage->pParent ){
  1000.     MemPage *pParent = pPage->pParent;
  1001.     assert( pParent->pBt==pPage->pBt );
  1002.     pPage->pParent = 0;
  1003.     releasePage(pParent);
  1004.   }
  1005.   pPage->isInit = 0;
  1006. }
  1007. /*
  1008. ** During a rollback, when the pager reloads information into the cache
  1009. ** so that the cache is restored to its original state at the start of
  1010. ** the transaction, for each page restored this routine is called.
  1011. **
  1012. ** This routine needs to reset the extra data section at the end of the
  1013. ** page to agree with the restored data.
  1014. */
  1015. static void pageReinit(DbPage *pData, int pageSize){
  1016.   MemPage *pPage;
  1017.   assert( (pageSize & 7)==0 );
  1018.   pPage = (MemPage *)sqlite3PagerGetExtra(pData);
  1019.   if( pPage->isInit ){
  1020.     assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  1021.     pPage->isInit = 0;
  1022.     sqlite3BtreeInitPage(pPage, pPage->pParent);
  1023.   }
  1024. }
  1025. /*
  1026. ** Invoke the busy handler for a btree.
  1027. */
  1028. static int sqlite3BtreeInvokeBusyHandler(void *pArg, int n){
  1029.   BtShared *pBt = (BtShared*)pArg;
  1030.   assert( pBt->db );
  1031.   assert( sqlite3_mutex_held(pBt->db->mutex) );
  1032.   return sqlite3InvokeBusyHandler(&pBt->db->busyHandler);
  1033. }
  1034. /*
  1035. ** Open a database file.
  1036. ** 
  1037. ** zFilename is the name of the database file.  If zFilename is NULL
  1038. ** a new database with a random name is created.  This randomly named
  1039. ** database file will be deleted when sqlite3BtreeClose() is called.
  1040. ** If zFilename is ":memory:" then an in-memory database is created
  1041. ** that is automatically destroyed when it is closed.
  1042. */
  1043. int sqlite3BtreeOpen(
  1044.   const char *zFilename,  /* Name of the file containing the BTree database */
  1045.   sqlite3 *db,            /* Associated database handle */
  1046.   Btree **ppBtree,        /* Pointer to new Btree object written here */
  1047.   int flags,              /* Options */
  1048.   int vfsFlags            /* Flags passed through to sqlite3_vfs.xOpen() */
  1049. ){
  1050.   sqlite3_vfs *pVfs;      /* The VFS to use for this btree */
  1051.   BtShared *pBt = 0;      /* Shared part of btree structure */
  1052.   Btree *p;               /* Handle to return */
  1053.   int rc = SQLITE_OK;
  1054.   int nReserve;
  1055.   unsigned char zDbHeader[100];
  1056.   /* Set the variable isMemdb to true for an in-memory database, or 
  1057.   ** false for a file-based database. This symbol is only required if
  1058.   ** either of the shared-data or autovacuum features are compiled 
  1059.   ** into the library.
  1060.   */
  1061. #if !defined(SQLITE_OMIT_SHARED_CACHE) || !defined(SQLITE_OMIT_AUTOVACUUM)
  1062.   #ifdef SQLITE_OMIT_MEMORYDB
  1063.     const int isMemdb = 0;
  1064.   #else
  1065.     const int isMemdb = zFilename && !strcmp(zFilename, ":memory:");
  1066.   #endif
  1067. #endif
  1068.   assert( db!=0 );
  1069.   assert( sqlite3_mutex_held(db->mutex) );
  1070.   pVfs = db->pVfs;
  1071.   p = sqlite3MallocZero(sizeof(Btree));
  1072.   if( !p ){
  1073.     return SQLITE_NOMEM;
  1074.   }
  1075.   p->inTrans = TRANS_NONE;
  1076.   p->db = db;
  1077. #if !defined(SQLITE_OMIT_SHARED_CACHE) && !defined(SQLITE_OMIT_DISKIO)
  1078.   /*
  1079.   ** If this Btree is a candidate for shared cache, try to find an
  1080.   ** existing BtShared object that we can share with
  1081.   */
  1082.   if( (flags & BTREE_PRIVATE)==0
  1083.    && isMemdb==0
  1084.    && (db->flags & SQLITE_Vtab)==0
  1085.    && zFilename && zFilename[0]
  1086.   ){
  1087.     if( sqlite3SharedCacheEnabled ){
  1088.       int nFullPathname = pVfs->mxPathname+1;
  1089.       char *zFullPathname = (char *)sqlite3_malloc(nFullPathname);
  1090.       sqlite3_mutex *mutexShared;
  1091.       p->sharable = 1;
  1092.       if( db ){
  1093.         db->flags |= SQLITE_SharedCache;
  1094.       }
  1095.       if( !zFullPathname ){
  1096.         sqlite3_free(p);
  1097.         return SQLITE_NOMEM;
  1098.       }
  1099.       sqlite3OsFullPathname(pVfs, zFilename, nFullPathname, zFullPathname);
  1100.       mutexShared = sqlite3_mutex_alloc(SQLITE_MUTEX_STATIC_MASTER);
  1101.       sqlite3_mutex_enter(mutexShared);
  1102.       for(pBt=sqlite3SharedCacheList; pBt; pBt=pBt->pNext){
  1103.         assert( pBt->nRef>0 );
  1104.         if( 0==strcmp(zFullPathname, sqlite3PagerFilename(pBt->pPager))
  1105.                  && sqlite3PagerVfs(pBt->pPager)==pVfs ){
  1106.           p->pBt = pBt;
  1107.           pBt->nRef++;
  1108.           break;
  1109.         }
  1110.       }
  1111.       sqlite3_mutex_leave(mutexShared);
  1112.       sqlite3_free(zFullPathname);
  1113.     }
  1114. #ifdef SQLITE_DEBUG
  1115.     else{
  1116.       /* In debug mode, we mark all persistent databases as sharable
  1117.       ** even when they are not.  This exercises the locking code and
  1118.       ** gives more opportunity for asserts(sqlite3_mutex_held())
  1119.       ** statements to find locking problems.
  1120.       */
  1121.       p->sharable = 1;
  1122.     }
  1123. #endif
  1124.   }
  1125. #endif
  1126.   if( pBt==0 ){
  1127.     /*
  1128.     ** The following asserts make sure that structures used by the btree are
  1129.     ** the right size.  This is to guard against size changes that result
  1130.     ** when compiling on a different architecture.
  1131.     */
  1132.     assert( sizeof(i64)==8 || sizeof(i64)==4 );
  1133.     assert( sizeof(u64)==8 || sizeof(u64)==4 );
  1134.     assert( sizeof(u32)==4 );
  1135.     assert( sizeof(u16)==2 );
  1136.     assert( sizeof(Pgno)==4 );
  1137.   
  1138.     pBt = sqlite3MallocZero( sizeof(*pBt) );
  1139.     if( pBt==0 ){
  1140.       rc = SQLITE_NOMEM;
  1141.       goto btree_open_out;
  1142.     }
  1143.     pBt->busyHdr.xFunc = sqlite3BtreeInvokeBusyHandler;
  1144.     pBt->busyHdr.pArg = pBt;
  1145.     rc = sqlite3PagerOpen(pVfs, &pBt->pPager, zFilename,
  1146.                           EXTRA_SIZE, flags, vfsFlags);
  1147.     if( rc==SQLITE_OK ){
  1148.       rc = sqlite3PagerReadFileheader(pBt->pPager,sizeof(zDbHeader),zDbHeader);
  1149.     }
  1150.     if( rc!=SQLITE_OK ){
  1151.       goto btree_open_out;
  1152.     }
  1153.     sqlite3PagerSetBusyhandler(pBt->pPager, &pBt->busyHdr);
  1154.     p->pBt = pBt;
  1155.   
  1156.     sqlite3PagerSetDestructor(pBt->pPager, pageDestructor);
  1157.     sqlite3PagerSetReiniter(pBt->pPager, pageReinit);
  1158.     pBt->pCursor = 0;
  1159.     pBt->pPage1 = 0;
  1160.     pBt->readOnly = sqlite3PagerIsreadonly(pBt->pPager);
  1161.     pBt->pageSize = get2byte(&zDbHeader[16]);
  1162.     if( pBt->pageSize<512 || pBt->pageSize>SQLITE_MAX_PAGE_SIZE
  1163.          || ((pBt->pageSize-1)&pBt->pageSize)!=0 ){
  1164.       pBt->pageSize = 0;
  1165.       sqlite3PagerSetPagesize(pBt->pPager, &pBt->pageSize);
  1166.       pBt->maxEmbedFrac = 64;   /* 25% */
  1167.       pBt->minEmbedFrac = 32;   /* 12.5% */
  1168.       pBt->minLeafFrac = 32;    /* 12.5% */
  1169. #ifndef SQLITE_OMIT_AUTOVACUUM
  1170.       /* If the magic name ":memory:" will create an in-memory database, then
  1171.       ** leave the autoVacuum mode at 0 (do not auto-vacuum), even if
  1172.       ** SQLITE_DEFAULT_AUTOVACUUM is true. On the other hand, if
  1173.       ** SQLITE_OMIT_MEMORYDB has been defined, then ":memory:" is just a
  1174.       ** regular file-name. In this case the auto-vacuum applies as per normal.
  1175.       */
  1176.       if( zFilename && !isMemdb ){
  1177.         pBt->autoVacuum = (SQLITE_DEFAULT_AUTOVACUUM ? 1 : 0);
  1178.         pBt->incrVacuum = (SQLITE_DEFAULT_AUTOVACUUM==2 ? 1 : 0);
  1179.       }
  1180. #endif
  1181.       nReserve = 0;
  1182.     }else{
  1183.       nReserve = zDbHeader[20];
  1184.       pBt->maxEmbedFrac = zDbHeader[21];
  1185.       pBt->minEmbedFrac = zDbHeader[22];
  1186.       pBt->minLeafFrac = zDbHeader[23];
  1187.       pBt->pageSizeFixed = 1;
  1188. #ifndef SQLITE_OMIT_AUTOVACUUM
  1189.       pBt->autoVacuum = (get4byte(&zDbHeader[36 + 4*4])?1:0);
  1190.       pBt->incrVacuum = (get4byte(&zDbHeader[36 + 7*4])?1:0);
  1191. #endif
  1192.     }
  1193.     pBt->usableSize = pBt->pageSize - nReserve;
  1194.     assert( (pBt->pageSize & 7)==0 );  /* 8-byte alignment of pageSize */
  1195.     sqlite3PagerSetPagesize(pBt->pPager, &pBt->pageSize);
  1196.    
  1197. #if !defined(SQLITE_OMIT_SHARED_CACHE) && !defined(SQLITE_OMIT_DISKIO)
  1198.     /* Add the new BtShared object to the linked list sharable BtShareds.
  1199.     */
  1200.     if( p->sharable ){
  1201.       sqlite3_mutex *mutexShared;
  1202.       pBt->nRef = 1;
  1203.       mutexShared = sqlite3_mutex_alloc(SQLITE_MUTEX_STATIC_MASTER);
  1204.       if( SQLITE_THREADSAFE ){
  1205.         pBt->mutex = sqlite3_mutex_alloc(SQLITE_MUTEX_FAST);
  1206.         if( pBt->mutex==0 ){
  1207.           rc = SQLITE_NOMEM;
  1208.           db->mallocFailed = 0;
  1209.           goto btree_open_out;
  1210.         }
  1211.       }
  1212.       sqlite3_mutex_enter(mutexShared);
  1213.       pBt->pNext = sqlite3SharedCacheList;
  1214.       sqlite3SharedCacheList = pBt;
  1215.       sqlite3_mutex_leave(mutexShared);
  1216.     }
  1217. #endif
  1218.   }
  1219. #if !defined(SQLITE_OMIT_SHARED_CACHE) && !defined(SQLITE_OMIT_DISKIO)
  1220.   /* If the new Btree uses a sharable pBtShared, then link the new
  1221.   ** Btree into the list of all sharable Btrees for the same connection.
  1222.   ** The list is kept in ascending order by pBt address.
  1223.   */
  1224.   if( p->sharable ){
  1225.     int i;
  1226.     Btree *pSib;
  1227.     for(i=0; i<db->nDb; i++){
  1228.       if( (pSib = db->aDb[i].pBt)!=0 && pSib->sharable ){
  1229.         while( pSib->pPrev ){ pSib = pSib->pPrev; }
  1230.         if( p->pBt<pSib->pBt ){
  1231.           p->pNext = pSib;
  1232.           p->pPrev = 0;
  1233.           pSib->pPrev = p;
  1234.         }else{
  1235.           while( pSib->pNext && pSib->pNext->pBt<p->pBt ){
  1236.             pSib = pSib->pNext;
  1237.           }
  1238.           p->pNext = pSib->pNext;
  1239.           p->pPrev = pSib;
  1240.           if( p->pNext ){
  1241.             p->pNext->pPrev = p;
  1242.           }
  1243.           pSib->pNext = p;
  1244.         }
  1245.         break;
  1246.       }
  1247.     }
  1248.   }
  1249. #endif
  1250.   *ppBtree = p;
  1251. btree_open_out:
  1252.   if( rc!=SQLITE_OK ){
  1253.     if( pBt && pBt->pPager ){
  1254.       sqlite3PagerClose(pBt->pPager);
  1255.     }
  1256.     sqlite3_free(pBt);
  1257.     sqlite3_free(p);
  1258.     *ppBtree = 0;
  1259.   }
  1260.   return rc;
  1261. }
  1262. /*
  1263. ** Decrement the BtShared.nRef counter.  When it reaches zero,
  1264. ** remove the BtShared structure from the sharing list.  Return
  1265. ** true if the BtShared.nRef counter reaches zero and return
  1266. ** false if it is still positive.
  1267. */
  1268. static int removeFromSharingList(BtShared *pBt){
  1269. #ifndef SQLITE_OMIT_SHARED_CACHE
  1270.   sqlite3_mutex *pMaster;
  1271.   BtShared *pList;
  1272.   int removed = 0;
  1273.   assert( sqlite3_mutex_notheld(pBt->mutex) );
  1274.   pMaster = sqlite3_mutex_alloc(SQLITE_MUTEX_STATIC_MASTER);
  1275.   sqlite3_mutex_enter(pMaster);
  1276.   pBt->nRef--;
  1277.   if( pBt->nRef<=0 ){
  1278.     if( sqlite3SharedCacheList==pBt ){
  1279.       sqlite3SharedCacheList = pBt->pNext;
  1280.     }else{
  1281.       pList = sqlite3SharedCacheList;
  1282.       while( pList && pList->pNext!=pBt ){
  1283.         pList=pList->pNext;
  1284.       }
  1285.       if( pList ){
  1286.         pList->pNext = pBt->pNext;
  1287.       }
  1288.     }
  1289.     if( SQLITE_THREADSAFE ){
  1290.       sqlite3_mutex_free(pBt->mutex);
  1291.     }
  1292.     removed = 1;
  1293.   }
  1294.   sqlite3_mutex_leave(pMaster);
  1295.   return removed;
  1296. #else
  1297.   return 1;
  1298. #endif
  1299. }
  1300. /*
  1301. ** Close an open database and invalidate all cursors.
  1302. */
  1303. int sqlite3BtreeClose(Btree *p){
  1304.   BtShared *pBt = p->pBt;
  1305.   BtCursor *pCur;
  1306.   /* Close all cursors opened via this handle.  */
  1307.   assert( sqlite3_mutex_held(p->db->mutex) );
  1308.   sqlite3BtreeEnter(p);
  1309.   pBt->db = p->db;
  1310.   pCur = pBt->pCursor;
  1311.   while( pCur ){
  1312.     BtCursor *pTmp = pCur;
  1313.     pCur = pCur->pNext;
  1314.     if( pTmp->pBtree==p ){
  1315.       sqlite3BtreeCloseCursor(pTmp);
  1316.     }
  1317.   }
  1318.   /* Rollback any active transaction and free the handle structure.
  1319.   ** The call to sqlite3BtreeRollback() drops any table-locks held by
  1320.   ** this handle.
  1321.   */
  1322.   sqlite3BtreeRollback(p);
  1323.   sqlite3BtreeLeave(p);
  1324.   /* If there are still other outstanding references to the shared-btree
  1325.   ** structure, return now. The remainder of this procedure cleans 
  1326.   ** up the shared-btree.
  1327.   */
  1328.   assert( p->wantToLock==0 && p->locked==0 );
  1329.   if( !p->sharable || removeFromSharingList(pBt) ){
  1330.     /* The pBt is no longer on the sharing list, so we can access
  1331.     ** it without having to hold the mutex.
  1332.     **
  1333.     ** Clean out and delete the BtShared object.
  1334.     */
  1335.     assert( !pBt->pCursor );
  1336.     sqlite3PagerClose(pBt->pPager);
  1337.     if( pBt->xFreeSchema && pBt->pSchema ){
  1338.       pBt->xFreeSchema(pBt->pSchema);
  1339.     }
  1340.     sqlite3_free(pBt->pSchema);
  1341.     sqlite3_free(pBt->pTmpSpace);
  1342.     sqlite3_free(pBt);
  1343.   }
  1344. #ifndef SQLITE_OMIT_SHARED_CACHE
  1345.   assert( p->wantToLock==0 );
  1346.   assert( p->locked==0 );
  1347.   if( p->pPrev ) p->pPrev->pNext = p->pNext;
  1348.   if( p->pNext ) p->pNext->pPrev = p->pPrev;
  1349. #endif
  1350.   sqlite3_free(p);
  1351.   return SQLITE_OK;
  1352. }
  1353. /*
  1354. ** Change the limit on the number of pages allowed in the cache.
  1355. **
  1356. ** The maximum number of cache pages is set to the absolute
  1357. ** value of mxPage.  If mxPage is negative, the pager will
  1358. ** operate asynchronously - it will not stop to do fsync()s
  1359. ** to insure data is written to the disk surface before
  1360. ** continuing.  Transactions still work if synchronous is off,
  1361. ** and the database cannot be corrupted if this program
  1362. ** crashes.  But if the operating system crashes or there is
  1363. ** an abrupt power failure when synchronous is off, the database
  1364. ** could be left in an inconsistent and unrecoverable state.
  1365. ** Synchronous is on by default so database corruption is not
  1366. ** normally a worry.
  1367. */
  1368. int sqlite3BtreeSetCacheSize(Btree *p, int mxPage){
  1369.   BtShared *pBt = p->pBt;
  1370.   assert( sqlite3_mutex_held(p->db->mutex) );
  1371.   sqlite3BtreeEnter(p);
  1372.   sqlite3PagerSetCachesize(pBt->pPager, mxPage);
  1373.   sqlite3BtreeLeave(p);
  1374.   return SQLITE_OK;
  1375. }
  1376. /*
  1377. ** Change the way data is synced to disk in order to increase or decrease
  1378. ** how well the database resists damage due to OS crashes and power
  1379. ** failures.  Level 1 is the same as asynchronous (no syncs() occur and
  1380. ** there is a high probability of damage)  Level 2 is the default.  There
  1381. ** is a very low but non-zero probability of damage.  Level 3 reduces the
  1382. ** probability of damage to near zero but with a write performance reduction.
  1383. */
  1384. #ifndef SQLITE_OMIT_PAGER_PRAGMAS
  1385. int sqlite3BtreeSetSafetyLevel(Btree *p, int level, int fullSync){
  1386.   BtShared *pBt = p->pBt;
  1387.   assert( sqlite3_mutex_held(p->db->mutex) );
  1388.   sqlite3BtreeEnter(p);
  1389.   sqlite3PagerSetSafetyLevel(pBt->pPager, level, fullSync);
  1390.   sqlite3BtreeLeave(p);
  1391.   return SQLITE_OK;
  1392. }
  1393. #endif
  1394. /*
  1395. ** Return TRUE if the given btree is set to safety level 1.  In other
  1396. ** words, return TRUE if no sync() occurs on the disk files.
  1397. */
  1398. int sqlite3BtreeSyncDisabled(Btree *p){
  1399.   BtShared *pBt = p->pBt;
  1400.   int rc;
  1401.   assert( sqlite3_mutex_held(p->db->mutex) );  
  1402.   sqlite3BtreeEnter(p);
  1403.   assert( pBt && pBt->pPager );
  1404.   rc = sqlite3PagerNosync(pBt->pPager);
  1405.   sqlite3BtreeLeave(p);
  1406.   return rc;
  1407. }
  1408. #if !defined(SQLITE_OMIT_PAGER_PRAGMAS) || !defined(SQLITE_OMIT_VACUUM)
  1409. /*
  1410. ** Change the default pages size and the number of reserved bytes per page.
  1411. **
  1412. ** The page size must be a power of 2 between 512 and 65536.  If the page
  1413. ** size supplied does not meet this constraint then the page size is not
  1414. ** changed.
  1415. **
  1416. ** Page sizes are constrained to be a power of two so that the region
  1417. ** of the database file used for locking (beginning at PENDING_BYTE,
  1418. ** the first byte past the 1GB boundary, 0x40000000) needs to occur
  1419. ** at the beginning of a page.
  1420. **
  1421. ** If parameter nReserve is less than zero, then the number of reserved
  1422. ** bytes per page is left unchanged.
  1423. */
  1424. int sqlite3BtreeSetPageSize(Btree *p, int pageSize, int nReserve){
  1425.   int rc = SQLITE_OK;
  1426.   BtShared *pBt = p->pBt;
  1427.   sqlite3BtreeEnter(p);
  1428.   if( pBt->pageSizeFixed ){
  1429.     sqlite3BtreeLeave(p);
  1430.     return SQLITE_READONLY;
  1431.   }
  1432.   if( nReserve<0 ){
  1433.     nReserve = pBt->pageSize - pBt->usableSize;
  1434.   }
  1435.   if( pageSize>=512 && pageSize<=SQLITE_MAX_PAGE_SIZE &&
  1436.         ((pageSize-1)&pageSize)==0 ){
  1437.     assert( (pageSize & 7)==0 );
  1438.     assert( !pBt->pPage1 && !pBt->pCursor );
  1439.     pBt->pageSize = pageSize;
  1440.     sqlite3_free(pBt->pTmpSpace);
  1441.     pBt->pTmpSpace = 0;
  1442.     rc = sqlite3PagerSetPagesize(pBt->pPager, &pBt->pageSize);
  1443.   }
  1444.   pBt->usableSize = pBt->pageSize - nReserve;
  1445.   sqlite3BtreeLeave(p);
  1446.   return rc;
  1447. }
  1448. /*
  1449. ** Return the currently defined page size
  1450. */
  1451. int sqlite3BtreeGetPageSize(Btree *p){
  1452.   return p->pBt->pageSize;
  1453. }
  1454. int sqlite3BtreeGetReserve(Btree *p){
  1455.   int n;
  1456.   sqlite3BtreeEnter(p);
  1457.   n = p->pBt->pageSize - p->pBt->usableSize;
  1458.   sqlite3BtreeLeave(p);
  1459.   return n;
  1460. }
  1461. /*
  1462. ** Set the maximum page count for a database if mxPage is positive.
  1463. ** No changes are made if mxPage is 0 or negative.
  1464. ** Regardless of the value of mxPage, return the maximum page count.
  1465. */
  1466. int sqlite3BtreeMaxPageCount(Btree *p, int mxPage){
  1467.   int n;
  1468.   sqlite3BtreeEnter(p);
  1469.   n = sqlite3PagerMaxPageCount(p->pBt->pPager, mxPage);
  1470.   sqlite3BtreeLeave(p);
  1471.   return n;
  1472. }
  1473. #endif /* !defined(SQLITE_OMIT_PAGER_PRAGMAS) || !defined(SQLITE_OMIT_VACUUM) */
  1474. /*
  1475. ** Change the 'auto-vacuum' property of the database. If the 'autoVacuum'
  1476. ** parameter is non-zero, then auto-vacuum mode is enabled. If zero, it
  1477. ** is disabled. The default value for the auto-vacuum property is 
  1478. ** determined by the SQLITE_DEFAULT_AUTOVACUUM macro.
  1479. */
  1480. int sqlite3BtreeSetAutoVacuum(Btree *p, int autoVacuum){
  1481. #ifdef SQLITE_OMIT_AUTOVACUUM
  1482.   return SQLITE_READONLY;
  1483. #else
  1484.   BtShared *pBt = p->pBt;
  1485.   int rc = SQLITE_OK;
  1486.   int av = (autoVacuum?1:0);
  1487.   sqlite3BtreeEnter(p);
  1488.   if( pBt->pageSizeFixed && av!=pBt->autoVacuum ){
  1489.     rc = SQLITE_READONLY;
  1490.   }else{
  1491.     pBt->autoVacuum = av;
  1492.   }
  1493.   sqlite3BtreeLeave(p);
  1494.   return rc;
  1495. #endif
  1496. }
  1497. /*
  1498. ** Return the value of the 'auto-vacuum' property. If auto-vacuum is 
  1499. ** enabled 1 is returned. Otherwise 0.
  1500. */
  1501. int sqlite3BtreeGetAutoVacuum(Btree *p){
  1502. #ifdef SQLITE_OMIT_AUTOVACUUM
  1503.   return BTREE_AUTOVACUUM_NONE;
  1504. #else
  1505.   int rc;
  1506.   sqlite3BtreeEnter(p);
  1507.   rc = (
  1508.     (!p->pBt->autoVacuum)?BTREE_AUTOVACUUM_NONE:
  1509.     (!p->pBt->incrVacuum)?BTREE_AUTOVACUUM_FULL:
  1510.     BTREE_AUTOVACUUM_INCR
  1511.   );
  1512.   sqlite3BtreeLeave(p);
  1513.   return rc;
  1514. #endif
  1515. }
  1516. /*
  1517. ** Get a reference to pPage1 of the database file.  This will
  1518. ** also acquire a readlock on that file.
  1519. **
  1520. ** SQLITE_OK is returned on success.  If the file is not a
  1521. ** well-formed database file, then SQLITE_CORRUPT is returned.
  1522. ** SQLITE_BUSY is returned if the database is locked.  SQLITE_NOMEM
  1523. ** is returned if we run out of memory. 
  1524. */
  1525. static int lockBtree(BtShared *pBt){
  1526.   int rc;
  1527.   MemPage *pPage1;
  1528.   assert( sqlite3_mutex_held(pBt->mutex) );
  1529.   if( pBt->pPage1 ) return SQLITE_OK;
  1530.   rc = sqlite3BtreeGetPage(pBt, 1, &pPage1, 0);
  1531.   if( rc!=SQLITE_OK ) return rc;
  1532.   /* Do some checking to help insure the file we opened really is
  1533.   ** a valid database file. 
  1534.   */
  1535.   rc = SQLITE_NOTADB;
  1536.   if( sqlite3PagerPagecount(pBt->pPager)>0 ){
  1537.     int pageSize;
  1538.     int usableSize;
  1539.     u8 *page1 = pPage1->aData;
  1540.     if( memcmp(page1, zMagicHeader, 16)!=0 ){
  1541.       goto page1_init_failed;
  1542.     }
  1543.     if( page1[18]>1 ){
  1544.       pBt->readOnly = 1;
  1545.     }
  1546.     if( page1[19]>1 ){
  1547.       goto page1_init_failed;
  1548.     }
  1549.     pageSize = get2byte(&page1[16]);
  1550.     if( ((pageSize-1)&pageSize)!=0 || pageSize<512 ||
  1551.         (SQLITE_MAX_PAGE_SIZE<32768 && pageSize>SQLITE_MAX_PAGE_SIZE)
  1552.     ){
  1553.       goto page1_init_failed;
  1554.     }
  1555.     assert( (pageSize & 7)==0 );
  1556.     usableSize = pageSize - page1[20];
  1557.     if( pageSize!=pBt->pageSize ){
  1558.       /* After reading the first page of the database assuming a page size
  1559.       ** of BtShared.pageSize, we have discovered that the page-size is
  1560.       ** actually pageSize. Unlock the database, leave pBt->pPage1 at
  1561.       ** zero and return SQLITE_OK. The caller will call this function
  1562.       ** again with the correct page-size.
  1563.       */
  1564.       releasePage(pPage1);
  1565.       pBt->usableSize = usableSize;
  1566.       pBt->pageSize = pageSize;
  1567.       sqlite3_free(pBt->pTmpSpace);
  1568.       pBt->pTmpSpace = 0;
  1569.       sqlite3PagerSetPagesize(pBt->pPager, &pBt->pageSize);
  1570.       return SQLITE_OK;
  1571.     }
  1572.     if( usableSize<500 ){
  1573.       goto page1_init_failed;
  1574.     }
  1575.     pBt->pageSize = pageSize;
  1576.     pBt->usableSize = usableSize;
  1577.     pBt->maxEmbedFrac = page1[21];
  1578.     pBt->minEmbedFrac = page1[22];
  1579.     pBt->minLeafFrac = page1[23];
  1580. #ifndef SQLITE_OMIT_AUTOVACUUM
  1581.     pBt->autoVacuum = (get4byte(&page1[36 + 4*4])?1:0);
  1582.     pBt->incrVacuum = (get4byte(&page1[36 + 7*4])?1:0);
  1583. #endif
  1584.   }
  1585.   /* maxLocal is the maximum amount of payload to store locally for
  1586.   ** a cell.  Make sure it is small enough so that at least minFanout
  1587.   ** cells can will fit on one page.  We assume a 10-byte page header.
  1588.   ** Besides the payload, the cell must store:
  1589.   **     2-byte pointer to the cell
  1590.   **     4-byte child pointer
  1591.   **     9-byte nKey value
  1592.   **     4-byte nData value
  1593.   **     4-byte overflow page pointer
  1594.   ** So a cell consists of a 2-byte poiner, a header which is as much as
  1595.   ** 17 bytes long, 0 to N bytes of payload, and an optional 4 byte overflow
  1596.   ** page pointer.
  1597.   */
  1598.   pBt->maxLocal = (pBt->usableSize-12)*pBt->maxEmbedFrac/255 - 23;
  1599.   pBt->minLocal = (pBt->usableSize-12)*pBt->minEmbedFrac/255 - 23;
  1600.   pBt->maxLeaf = pBt->usableSize - 35;
  1601.   pBt->minLeaf = (pBt->usableSize-12)*pBt->minLeafFrac/255 - 23;
  1602.   if( pBt->minLocal>pBt->maxLocal || pBt->maxLocal<0 ){
  1603.     goto page1_init_failed;
  1604.   }
  1605.   assert( pBt->maxLeaf + 23 <= MX_CELL_SIZE(pBt) );
  1606.   pBt->pPage1 = pPage1;
  1607.   return SQLITE_OK;
  1608. page1_init_failed:
  1609.   releasePage(pPage1);
  1610.   pBt->pPage1 = 0;
  1611.   return rc;
  1612. }
  1613. /*
  1614. ** This routine works like lockBtree() except that it also invokes the
  1615. ** busy callback if there is lock contention.
  1616. */
  1617. static int lockBtreeWithRetry(Btree *pRef){
  1618.   int rc = SQLITE_OK;
  1619.   assert( sqlite3BtreeHoldsMutex(pRef) );
  1620.   if( pRef->inTrans==TRANS_NONE ){
  1621.     u8 inTransaction = pRef->pBt->inTransaction;
  1622.     btreeIntegrity(pRef);
  1623.     rc = sqlite3BtreeBeginTrans(pRef, 0);
  1624.     pRef->pBt->inTransaction = inTransaction;
  1625.     pRef->inTrans = TRANS_NONE;
  1626.     if( rc==SQLITE_OK ){
  1627.       pRef->pBt->nTransaction--;
  1628.     }
  1629.     btreeIntegrity(pRef);
  1630.   }
  1631.   return rc;
  1632. }
  1633.        
  1634. /*
  1635. ** If there are no outstanding cursors and we are not in the middle
  1636. ** of a transaction but there is a read lock on the database, then
  1637. ** this routine unrefs the first page of the database file which 
  1638. ** has the effect of releasing the read lock.
  1639. **
  1640. ** If there are any outstanding cursors, this routine is a no-op.
  1641. **
  1642. ** If there is a transaction in progress, this routine is a no-op.
  1643. */
  1644. static void unlockBtreeIfUnused(BtShared *pBt){
  1645.   assert( sqlite3_mutex_held(pBt->mutex) );
  1646.   if( pBt->inTransaction==TRANS_NONE && pBt->pCursor==0 && pBt->pPage1!=0 ){
  1647.     if( sqlite3PagerRefcount(pBt->pPager)>=1 ){
  1648.       assert( pBt->pPage1->aData );
  1649. #if 0
  1650.       if( pBt->pPage1->aData==0 ){
  1651.         MemPage *pPage = pBt->pPage1;
  1652.         pPage->aData = sqlite3PagerGetData(pPage->pDbPage);
  1653.         pPage->pBt = pBt;
  1654.         pPage->pgno = 1;
  1655.       }
  1656. #endif
  1657.       releasePage(pBt->pPage1);
  1658.     }
  1659.     pBt->pPage1 = 0;
  1660.     pBt->inStmt = 0;
  1661.   }
  1662. }
  1663. /*
  1664. ** Create a new database by initializing the first page of the
  1665. ** file.
  1666. */
  1667. static int newDatabase(BtShared *pBt){
  1668.   MemPage *pP1;
  1669.   unsigned char *data;
  1670.   int rc;
  1671.   assert( sqlite3_mutex_held(pBt->mutex) );
  1672.   if( sqlite3PagerPagecount(pBt->pPager)>0 ) return SQLITE_OK;
  1673.   pP1 = pBt->pPage1;
  1674.   assert( pP1!=0 );
  1675.   data = pP1->aData;
  1676.   rc = sqlite3PagerWrite(pP1->pDbPage);
  1677.   if( rc ) return rc;
  1678.   memcpy(data, zMagicHeader, sizeof(zMagicHeader));
  1679.   assert( sizeof(zMagicHeader)==16 );
  1680.   put2byte(&data[16], pBt->pageSize);
  1681.   data[18] = 1;
  1682.   data[19] = 1;
  1683.   data[20] = pBt->pageSize - pBt->usableSize;
  1684.   data[21] = pBt->maxEmbedFrac;
  1685.   data[22] = pBt->minEmbedFrac;
  1686.   data[23] = pBt->minLeafFrac;
  1687.   memset(&data[24], 0, 100-24);
  1688.   zeroPage(pP1, PTF_INTKEY|PTF_LEAF|PTF_LEAFDATA );
  1689.   pBt->pageSizeFixed = 1;
  1690. #ifndef SQLITE_OMIT_AUTOVACUUM
  1691.   assert( pBt->autoVacuum==1 || pBt->autoVacuum==0 );
  1692.   assert( pBt->incrVacuum==1 || pBt->incrVacuum==0 );
  1693.   put4byte(&data[36 + 4*4], pBt->autoVacuum);
  1694.   put4byte(&data[36 + 7*4], pBt->incrVacuum);
  1695. #endif
  1696.   return SQLITE_OK;
  1697. }
  1698. /*
  1699. ** Attempt to start a new transaction. A write-transaction
  1700. ** is started if the second argument is nonzero, otherwise a read-
  1701. ** transaction.  If the second argument is 2 or more and exclusive
  1702. ** transaction is started, meaning that no other process is allowed
  1703. ** to access the database.  A preexisting transaction may not be
  1704. ** upgraded to exclusive by calling this routine a second time - the
  1705. ** exclusivity flag only works for a new transaction.
  1706. **
  1707. ** A write-transaction must be started before attempting any 
  1708. ** changes to the database.  None of the following routines 
  1709. ** will work unless a transaction is started first:
  1710. **
  1711. **      sqlite3BtreeCreateTable()
  1712. **      sqlite3BtreeCreateIndex()
  1713. **      sqlite3BtreeClearTable()
  1714. **      sqlite3BtreeDropTable()
  1715. **      sqlite3BtreeInsert()
  1716. **      sqlite3BtreeDelete()
  1717. **      sqlite3BtreeUpdateMeta()
  1718. **
  1719. ** If an initial attempt to acquire the lock fails because of lock contention
  1720. ** and the database was previously unlocked, then invoke the busy handler
  1721. ** if there is one.  But if there was previously a read-lock, do not
  1722. ** invoke the busy handler - just return SQLITE_BUSY.  SQLITE_BUSY is 
  1723. ** returned when there is already a read-lock in order to avoid a deadlock.
  1724. **
  1725. ** Suppose there are two processes A and B.  A has a read lock and B has
  1726. ** a reserved lock.  B tries to promote to exclusive but is blocked because
  1727. ** of A's read lock.  A tries to promote to reserved but is blocked by B.
  1728. ** One or the other of the two processes must give way or there can be
  1729. ** no progress.  By returning SQLITE_BUSY and not invoking the busy callback
  1730. ** when A already has a read lock, we encourage A to give up and let B
  1731. ** proceed.
  1732. */
  1733. int sqlite3BtreeBeginTrans(Btree *p, int wrflag){
  1734.   BtShared *pBt = p->pBt;
  1735.   int rc = SQLITE_OK;
  1736.   sqlite3BtreeEnter(p);
  1737.   pBt->db = p->db;
  1738.   btreeIntegrity(p);
  1739.   /* If the btree is already in a write-transaction, or it
  1740.   ** is already in a read-transaction and a read-transaction
  1741.   ** is requested, this is a no-op.
  1742.   */
  1743.   if( p->inTrans==TRANS_WRITE || (p->inTrans==TRANS_READ && !wrflag) ){
  1744.     goto trans_begun;
  1745.   }
  1746.   /* Write transactions are not possible on a read-only database */
  1747.   if( pBt->readOnly && wrflag ){
  1748.     rc = SQLITE_READONLY;
  1749.     goto trans_begun;
  1750.   }
  1751.   /* If another database handle has already opened a write transaction 
  1752.   ** on this shared-btree structure and a second write transaction is
  1753.   ** requested, return SQLITE_BUSY.
  1754.   */
  1755.   if( pBt->inTransaction==TRANS_WRITE && wrflag ){
  1756.     rc = SQLITE_BUSY;
  1757.     goto trans_begun;
  1758.   }
  1759. #ifndef SQLITE_OMIT_SHARED_CACHE
  1760.   if( wrflag>1 ){
  1761.     BtLock *pIter;
  1762.     for(pIter=pBt->pLock; pIter; pIter=pIter->pNext){
  1763.       if( pIter->pBtree!=p ){
  1764.         rc = SQLITE_BUSY;
  1765.         goto trans_begun;
  1766.       }
  1767.     }
  1768.   }
  1769. #endif
  1770.   do {
  1771.     while( rc==SQLITE_OK && pBt->pPage1==0 ){
  1772.       rc = lockBtree(pBt);
  1773.     }
  1774.     if( rc==SQLITE_OK && wrflag ){
  1775.       if( pBt->readOnly ){
  1776.         rc = SQLITE_READONLY;
  1777.       }else{
  1778.         rc = sqlite3PagerBegin(pBt->pPage1->pDbPage, wrflag>1);
  1779.         if( rc==SQLITE_OK ){
  1780.           rc = newDatabase(pBt);
  1781.         }
  1782.       }
  1783.     }
  1784.   
  1785.     if( rc==SQLITE_OK ){
  1786.       if( wrflag ) pBt->inStmt = 0;
  1787.     }else{
  1788.       unlockBtreeIfUnused(pBt);
  1789.     }
  1790.   }while( rc==SQLITE_BUSY && pBt->inTransaction==TRANS_NONE &&
  1791.           sqlite3BtreeInvokeBusyHandler(pBt, 0) );
  1792.   if( rc==SQLITE_OK ){
  1793.     if( p->inTrans==TRANS_NONE ){
  1794.       pBt->nTransaction++;
  1795.     }
  1796.     p->inTrans = (wrflag?TRANS_WRITE:TRANS_READ);
  1797.     if( p->inTrans>pBt->inTransaction ){
  1798.       pBt->inTransaction = p->inTrans;
  1799.     }
  1800. #ifndef SQLITE_OMIT_SHARED_CACHE
  1801.     if( wrflag>1 ){
  1802.       assert( !pBt->pExclusive );
  1803.       pBt->pExclusive = p;
  1804.     }
  1805. #endif
  1806.   }
  1807. trans_begun:
  1808.   btreeIntegrity(p);
  1809.   sqlite3BtreeLeave(p);
  1810.   return rc;
  1811. }
  1812. #ifndef SQLITE_OMIT_AUTOVACUUM
  1813. /*
  1814. ** Set the pointer-map entries for all children of page pPage. Also, if
  1815. ** pPage contains cells that point to overflow pages, set the pointer
  1816. ** map entries for the overflow pages as well.
  1817. */
  1818. static int setChildPtrmaps(MemPage *pPage){
  1819.   int i;                             /* Counter variable */
  1820.   int nCell;                         /* Number of cells in page pPage */
  1821.   int rc;                            /* Return code */
  1822.   BtShared *pBt = pPage->pBt;
  1823.   int isInitOrig = pPage->isInit;
  1824.   Pgno pgno = pPage->pgno;
  1825.   assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  1826.   rc = sqlite3BtreeInitPage(pPage, pPage->pParent);
  1827.   if( rc!=SQLITE_OK ){
  1828.     goto set_child_ptrmaps_out;
  1829.   }
  1830.   nCell = pPage->nCell;
  1831.   for(i=0; i<nCell; i++){
  1832.     u8 *pCell = findCell(pPage, i);
  1833.     rc = ptrmapPutOvflPtr(pPage, pCell);
  1834.     if( rc!=SQLITE_OK ){
  1835.       goto set_child_ptrmaps_out;
  1836.     }
  1837.     if( !pPage->leaf ){
  1838.       Pgno childPgno = get4byte(pCell);
  1839.       rc = ptrmapPut(pBt, childPgno, PTRMAP_BTREE, pgno);
  1840.       if( rc!=SQLITE_OK ) goto set_child_ptrmaps_out;
  1841.     }
  1842.   }
  1843.   if( !pPage->leaf ){
  1844.     Pgno childPgno = get4byte(&pPage->aData[pPage->hdrOffset+8]);
  1845.     rc = ptrmapPut(pBt, childPgno, PTRMAP_BTREE, pgno);
  1846.   }
  1847. set_child_ptrmaps_out:
  1848.   pPage->isInit = isInitOrig;
  1849.   return rc;
  1850. }
  1851. /*
  1852. ** Somewhere on pPage, which is guarenteed to be a btree page, not an overflow
  1853. ** page, is a pointer to page iFrom. Modify this pointer so that it points to
  1854. ** iTo. Parameter eType describes the type of pointer to be modified, as 
  1855. ** follows:
  1856. **
  1857. ** PTRMAP_BTREE:     pPage is a btree-page. The pointer points at a child 
  1858. **                   page of pPage.
  1859. **
  1860. ** PTRMAP_OVERFLOW1: pPage is a btree-page. The pointer points at an overflow
  1861. **                   page pointed to by one of the cells on pPage.
  1862. **
  1863. ** PTRMAP_OVERFLOW2: pPage is an overflow-page. The pointer points at the next
  1864. **                   overflow page in the list.
  1865. */
  1866. static int modifyPagePointer(MemPage *pPage, Pgno iFrom, Pgno iTo, u8 eType){
  1867.   assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  1868.   if( eType==PTRMAP_OVERFLOW2 ){
  1869.     /* The pointer is always the first 4 bytes of the page in this case.  */
  1870.     if( get4byte(pPage->aData)!=iFrom ){
  1871.       return SQLITE_CORRUPT_BKPT;
  1872.     }
  1873.     put4byte(pPage->aData, iTo);
  1874.   }else{
  1875.     int isInitOrig = pPage->isInit;
  1876.     int i;
  1877.     int nCell;
  1878.     sqlite3BtreeInitPage(pPage, 0);
  1879.     nCell = pPage->nCell;
  1880.     for(i=0; i<nCell; i++){
  1881.       u8 *pCell = findCell(pPage, i);
  1882.       if( eType==PTRMAP_OVERFLOW1 ){
  1883.         CellInfo info;
  1884.         sqlite3BtreeParseCellPtr(pPage, pCell, &info);
  1885.         if( info.iOverflow ){
  1886.           if( iFrom==get4byte(&pCell[info.iOverflow]) ){
  1887.             put4byte(&pCell[info.iOverflow], iTo);
  1888.             break;
  1889.           }
  1890.         }
  1891.       }else{
  1892.         if( get4byte(pCell)==iFrom ){
  1893.           put4byte(pCell, iTo);
  1894.           break;
  1895.         }
  1896.       }
  1897.     }
  1898.   
  1899.     if( i==nCell ){
  1900.       if( eType!=PTRMAP_BTREE || 
  1901.           get4byte(&pPage->aData[pPage->hdrOffset+8])!=iFrom ){
  1902.         return SQLITE_CORRUPT_BKPT;
  1903.       }
  1904.       put4byte(&pPage->aData[pPage->hdrOffset+8], iTo);
  1905.     }
  1906.     pPage->isInit = isInitOrig;
  1907.   }
  1908.   return SQLITE_OK;
  1909. }
  1910. /*
  1911. ** Move the open database page pDbPage to location iFreePage in the 
  1912. ** database. The pDbPage reference remains valid.
  1913. */
  1914. static int relocatePage(
  1915.   BtShared *pBt,           /* Btree */
  1916.   MemPage *pDbPage,        /* Open page to move */
  1917.   u8 eType,                /* Pointer map 'type' entry for pDbPage */
  1918.   Pgno iPtrPage,           /* Pointer map 'page-no' entry for pDbPage */
  1919.   Pgno iFreePage           /* The location to move pDbPage to */
  1920. ){
  1921.   MemPage *pPtrPage;   /* The page that contains a pointer to pDbPage */
  1922.   Pgno iDbPage = pDbPage->pgno;
  1923.   Pager *pPager = pBt->pPager;
  1924.   int rc;
  1925.   assert( eType==PTRMAP_OVERFLOW2 || eType==PTRMAP_OVERFLOW1 || 
  1926.       eType==PTRMAP_BTREE || eType==PTRMAP_ROOTPAGE );
  1927.   assert( sqlite3_mutex_held(pBt->mutex) );
  1928.   assert( pDbPage->pBt==pBt );
  1929.   /* Move page iDbPage from its current location to page number iFreePage */
  1930.   TRACE(("AUTOVACUUM: Moving %d to free page %d (ptr page %d type %d)n", 
  1931.       iDbPage, iFreePage, iPtrPage, eType));
  1932.   rc = sqlite3PagerMovepage(pPager, pDbPage->pDbPage, iFreePage);
  1933.   if( rc!=SQLITE_OK ){
  1934.     return rc;
  1935.   }
  1936.   pDbPage->pgno = iFreePage;
  1937.   /* If pDbPage was a btree-page, then it may have child pages and/or cells
  1938.   ** that point to overflow pages. The pointer map entries for all these
  1939.   ** pages need to be changed.
  1940.   **
  1941.   ** If pDbPage is an overflow page, then the first 4 bytes may store a
  1942.   ** pointer to a subsequent overflow page. If this is the case, then
  1943.   ** the pointer map needs to be updated for the subsequent overflow page.
  1944.   */
  1945.   if( eType==PTRMAP_BTREE || eType==PTRMAP_ROOTPAGE ){
  1946.     rc = setChildPtrmaps(pDbPage);
  1947.     if( rc!=SQLITE_OK ){
  1948.       return rc;
  1949.     }
  1950.   }else{
  1951.     Pgno nextOvfl = get4byte(pDbPage->aData);
  1952.     if( nextOvfl!=0 ){
  1953.       rc = ptrmapPut(pBt, nextOvfl, PTRMAP_OVERFLOW2, iFreePage);
  1954.       if( rc!=SQLITE_OK ){
  1955.         return rc;
  1956.       }
  1957.     }
  1958.   }
  1959.   /* Fix the database pointer on page iPtrPage that pointed at iDbPage so
  1960.   ** that it points at iFreePage. Also fix the pointer map entry for
  1961.   ** iPtrPage.
  1962.   */
  1963.   if( eType!=PTRMAP_ROOTPAGE ){
  1964.     rc = sqlite3BtreeGetPage(pBt, iPtrPage, &pPtrPage, 0);
  1965.     if( rc!=SQLITE_OK ){
  1966.       return rc;
  1967.     }
  1968.     rc = sqlite3PagerWrite(pPtrPage->pDbPage);
  1969.     if( rc!=SQLITE_OK ){
  1970.       releasePage(pPtrPage);
  1971.       return rc;
  1972.     }
  1973.     rc = modifyPagePointer(pPtrPage, iDbPage, iFreePage, eType);
  1974.     releasePage(pPtrPage);
  1975.     if( rc==SQLITE_OK ){
  1976.       rc = ptrmapPut(pBt, iFreePage, eType, iPtrPage);
  1977.     }
  1978.   }
  1979.   return rc;
  1980. }
  1981. /* Forward declaration required by incrVacuumStep(). */
  1982. static int allocateBtreePage(BtShared *, MemPage **, Pgno *, Pgno, u8);
  1983. /*
  1984. ** Perform a single step of an incremental-vacuum. If successful,
  1985. ** return SQLITE_OK. If there is no work to do (and therefore no
  1986. ** point in calling this function again), return SQLITE_DONE.
  1987. **
  1988. ** More specificly, this function attempts to re-organize the 
  1989. ** database so that the last page of the file currently in use
  1990. ** is no longer in use.
  1991. **
  1992. ** If the nFin parameter is non-zero, the implementation assumes
  1993. ** that the caller will keep calling incrVacuumStep() until
  1994. ** it returns SQLITE_DONE or an error, and that nFin is the
  1995. ** number of pages the database file will contain after this 
  1996. ** process is complete.
  1997. */
  1998. static int incrVacuumStep(BtShared *pBt, Pgno nFin){
  1999.   Pgno iLastPg;             /* Last page in the database */
  2000.   Pgno nFreeList;           /* Number of pages still on the free-list */
  2001.   assert( sqlite3_mutex_held(pBt->mutex) );
  2002.   iLastPg = pBt->nTrunc;
  2003.   if( iLastPg==0 ){
  2004.     iLastPg = sqlite3PagerPagecount(pBt->pPager);
  2005.   }
  2006.   if( !PTRMAP_ISPAGE(pBt, iLastPg) && iLastPg!=PENDING_BYTE_PAGE(pBt) ){
  2007.     int rc;
  2008.     u8 eType;
  2009.     Pgno iPtrPage;
  2010.     nFreeList = get4byte(&pBt->pPage1->aData[36]);
  2011.     if( nFreeList==0 || nFin==iLastPg ){
  2012.       return SQLITE_DONE;
  2013.     }
  2014.     rc = ptrmapGet(pBt, iLastPg, &eType, &iPtrPage);
  2015.     if( rc!=SQLITE_OK ){
  2016.       return rc;
  2017.     }
  2018.     if( eType==PTRMAP_ROOTPAGE ){
  2019.       return SQLITE_CORRUPT_BKPT;
  2020.     }
  2021.     if( eType==PTRMAP_FREEPAGE ){
  2022.       if( nFin==0 ){
  2023.         /* Remove the page from the files free-list. This is not required
  2024.         ** if nFin is non-zero. In that case, the free-list will be
  2025.         ** truncated to zero after this function returns, so it doesn't 
  2026.         ** matter if it still contains some garbage entries.
  2027.         */
  2028.         Pgno iFreePg;
  2029.         MemPage *pFreePg;
  2030.         rc = allocateBtreePage(pBt, &pFreePg, &iFreePg, iLastPg, 1);
  2031.         if( rc!=SQLITE_OK ){
  2032.           return rc;
  2033.         }
  2034.         assert( iFreePg==iLastPg );
  2035.         releasePage(pFreePg);
  2036.       }
  2037.     } else {
  2038.       Pgno iFreePg;             /* Index of free page to move pLastPg to */
  2039.       MemPage *pLastPg;
  2040.       rc = sqlite3BtreeGetPage(pBt, iLastPg, &pLastPg, 0);
  2041.       if( rc!=SQLITE_OK ){
  2042.         return rc;
  2043.       }
  2044.       /* If nFin is zero, this loop runs exactly once and page pLastPg
  2045.       ** is swapped with the first free page pulled off the free list.
  2046.       **
  2047.       ** On the other hand, if nFin is greater than zero, then keep
  2048.       ** looping until a free-page located within the first nFin pages
  2049.       ** of the file is found.
  2050.       */
  2051.       do {
  2052.         MemPage *pFreePg;
  2053.         rc = allocateBtreePage(pBt, &pFreePg, &iFreePg, 0, 0);
  2054.         if( rc!=SQLITE_OK ){
  2055.           releasePage(pLastPg);
  2056.           return rc;
  2057.         }
  2058.         releasePage(pFreePg);
  2059.       }while( nFin!=0 && iFreePg>nFin );
  2060.       assert( iFreePg<iLastPg );
  2061.       
  2062.       rc = sqlite3PagerWrite(pLastPg->pDbPage);
  2063.       if( rc==SQLITE_OK ){
  2064.         rc = relocatePage(pBt, pLastPg, eType, iPtrPage, iFreePg);
  2065.       }
  2066.       releasePage(pLastPg);
  2067.       if( rc!=SQLITE_OK ){
  2068.         return rc;
  2069.       }
  2070.     }
  2071.   }
  2072.   pBt->nTrunc = iLastPg - 1;
  2073.   while( pBt->nTrunc==PENDING_BYTE_PAGE(pBt)||PTRMAP_ISPAGE(pBt, pBt->nTrunc) ){
  2074.     pBt->nTrunc--;
  2075.   }
  2076.   return SQLITE_OK;
  2077. }
  2078. /*
  2079. ** A write-transaction must be opened before calling this function.
  2080. ** It performs a single unit of work towards an incremental vacuum.
  2081. **
  2082. ** If the incremental vacuum is finished after this function has run,
  2083. ** SQLITE_DONE is returned. If it is not finished, but no error occured,
  2084. ** SQLITE_OK is returned. Otherwise an SQLite error code. 
  2085. */
  2086. int sqlite3BtreeIncrVacuum(Btree *p){
  2087.   int rc;
  2088.   BtShared *pBt = p->pBt;
  2089.   sqlite3BtreeEnter(p);
  2090.   pBt->db = p->db;
  2091.   assert( pBt->inTransaction==TRANS_WRITE && p->inTrans==TRANS_WRITE );
  2092.   if( !pBt->autoVacuum ){
  2093.     rc = SQLITE_DONE;
  2094.   }else{
  2095.     invalidateAllOverflowCache(pBt);
  2096.     rc = incrVacuumStep(pBt, 0);
  2097.   }
  2098.   sqlite3BtreeLeave(p);
  2099.   return rc;
  2100. }
  2101. /*
  2102. ** This routine is called prior to sqlite3PagerCommit when a transaction
  2103. ** is commited for an auto-vacuum database.
  2104. **
  2105. ** If SQLITE_OK is returned, then *pnTrunc is set to the number of pages
  2106. ** the database file should be truncated to during the commit process. 
  2107. ** i.e. the database has been reorganized so that only the first *pnTrunc
  2108. ** pages are in use.
  2109. */
  2110. static int autoVacuumCommit(BtShared *pBt, Pgno *pnTrunc){
  2111.   int rc = SQLITE_OK;
  2112.   Pager *pPager = pBt->pPager;
  2113. #ifndef NDEBUG
  2114.   int nRef = sqlite3PagerRefcount(pPager);
  2115. #endif
  2116.   assert( sqlite3_mutex_held(pBt->mutex) );
  2117.   invalidateAllOverflowCache(pBt);
  2118.   assert(pBt->autoVacuum);
  2119.   if( !pBt->incrVacuum ){
  2120.     Pgno nFin = 0;
  2121.     if( pBt->nTrunc==0 ){
  2122.       Pgno nFree;
  2123.       Pgno nPtrmap;
  2124.       const int pgsz = pBt->pageSize;
  2125.       Pgno nOrig = sqlite3PagerPagecount(pBt->pPager);
  2126.       if( PTRMAP_ISPAGE(pBt, nOrig) ){
  2127.         return SQLITE_CORRUPT_BKPT;
  2128.       }
  2129.       if( nOrig==PENDING_BYTE_PAGE(pBt) ){
  2130.         nOrig--;
  2131.       }
  2132.       nFree = get4byte(&pBt->pPage1->aData[36]);
  2133.       nPtrmap = (nFree-nOrig+PTRMAP_PAGENO(pBt, nOrig)+pgsz/5)/(pgsz/5);
  2134.       nFin = nOrig - nFree - nPtrmap;
  2135.       if( nOrig>PENDING_BYTE_PAGE(pBt) && nFin<=PENDING_BYTE_PAGE(pBt) ){
  2136.         nFin--;
  2137.       }
  2138.       while( PTRMAP_ISPAGE(pBt, nFin) || nFin==PENDING_BYTE_PAGE(pBt) ){
  2139.         nFin--;
  2140.       }
  2141.     }
  2142.     while( rc==SQLITE_OK ){
  2143.       rc = incrVacuumStep(pBt, nFin);
  2144.     }
  2145.     if( rc==SQLITE_DONE ){
  2146.       assert(nFin==0 || pBt->nTrunc==0 || nFin<=pBt->nTrunc);
  2147.       rc = SQLITE_OK;
  2148.       if( pBt->nTrunc ){
  2149.         rc = sqlite3PagerWrite(pBt->pPage1->pDbPage);
  2150.         put4byte(&pBt->pPage1->aData[32], 0);
  2151.         put4byte(&pBt->pPage1->aData[36], 0);
  2152.         pBt->nTrunc = nFin;
  2153.       }
  2154.     }
  2155.     if( rc!=SQLITE_OK ){
  2156.       sqlite3PagerRollback(pPager);
  2157.     }
  2158.   }
  2159.   if( rc==SQLITE_OK ){
  2160.     *pnTrunc = pBt->nTrunc;
  2161.     pBt->nTrunc = 0;
  2162.   }
  2163.   assert( nRef==sqlite3PagerRefcount(pPager) );
  2164.   return rc;
  2165. }
  2166. #endif
  2167. /*
  2168. ** This routine does the first phase of a two-phase commit.  This routine
  2169. ** causes a rollback journal to be created (if it does not already exist)
  2170. ** and populated with enough information so that if a power loss occurs
  2171. ** the database can be restored to its original state by playing back
  2172. ** the journal.  Then the contents of the journal are flushed out to
  2173. ** the disk.  After the journal is safely on oxide, the changes to the
  2174. ** database are written into the database file and flushed to oxide.
  2175. ** At the end of this call, the rollback journal still exists on the
  2176. ** disk and we are still holding all locks, so the transaction has not
  2177. ** committed.  See sqlite3BtreeCommit() for the second phase of the
  2178. ** commit process.
  2179. **
  2180. ** This call is a no-op if no write-transaction is currently active on pBt.
  2181. **
  2182. ** Otherwise, sync the database file for the btree pBt. zMaster points to
  2183. ** the name of a master journal file that should be written into the
  2184. ** individual journal file, or is NULL, indicating no master journal file 
  2185. ** (single database transaction).
  2186. **
  2187. ** When this is called, the master journal should already have been
  2188. ** created, populated with this journal pointer and synced to disk.
  2189. **
  2190. ** Once this is routine has returned, the only thing required to commit
  2191. ** the write-transaction for this database file is to delete the journal.
  2192. */
  2193. int sqlite3BtreeCommitPhaseOne(Btree *p, const char *zMaster){
  2194.   int rc = SQLITE_OK;
  2195.   if( p->inTrans==TRANS_WRITE ){
  2196.     BtShared *pBt = p->pBt;
  2197.     Pgno nTrunc = 0;
  2198.     sqlite3BtreeEnter(p);
  2199.     pBt->db = p->db;
  2200. #ifndef SQLITE_OMIT_AUTOVACUUM
  2201.     if( pBt->autoVacuum ){
  2202.       rc = autoVacuumCommit(pBt, &nTrunc); 
  2203.       if( rc!=SQLITE_OK ){
  2204.         sqlite3BtreeLeave(p);
  2205.         return rc;
  2206.       }
  2207.     }
  2208. #endif
  2209.     rc = sqlite3PagerCommitPhaseOne(pBt->pPager, zMaster, nTrunc, 0);
  2210.     sqlite3BtreeLeave(p);
  2211.   }
  2212.   return rc;
  2213. }
  2214. /*
  2215. ** Commit the transaction currently in progress.
  2216. **
  2217. ** This routine implements the second phase of a 2-phase commit.  The
  2218. ** sqlite3BtreeSync() routine does the first phase and should be invoked
  2219. ** prior to calling this routine.  The sqlite3BtreeSync() routine did
  2220. ** all the work of writing information out to disk and flushing the
  2221. ** contents so that they are written onto the disk platter.  All this
  2222. ** routine has to do is delete or truncate the rollback journal
  2223. ** (which causes the transaction to commit) and drop locks.
  2224. **
  2225. ** This will release the write lock on the database file.  If there
  2226. ** are no active cursors, it also releases the read lock.
  2227. */
  2228. int sqlite3BtreeCommitPhaseTwo(Btree *p){
  2229.   BtShared *pBt = p->pBt;
  2230.   sqlite3BtreeEnter(p);
  2231.   pBt->db = p->db;
  2232.   btreeIntegrity(p);
  2233.   /* If the handle has a write-transaction open, commit the shared-btrees 
  2234.   ** transaction and set the shared state to TRANS_READ.
  2235.   */
  2236.   if( p->inTrans==TRANS_WRITE ){
  2237.     int rc;
  2238.     assert( pBt->inTransaction==TRANS_WRITE );
  2239.     assert( pBt->nTransaction>0 );
  2240.     rc = sqlite3PagerCommitPhaseTwo(pBt->pPager);
  2241.     if( rc!=SQLITE_OK ){
  2242.       sqlite3BtreeLeave(p);
  2243.       return rc;
  2244.     }
  2245.     pBt->inTransaction = TRANS_READ;
  2246.     pBt->inStmt = 0;
  2247.   }
  2248.   unlockAllTables(p);
  2249.   /* If the handle has any kind of transaction open, decrement the transaction
  2250.   ** count of the shared btree. If the transaction count reaches 0, set
  2251.   ** the shared state to TRANS_NONE. The unlockBtreeIfUnused() call below
  2252.   ** will unlock the pager.
  2253.   */
  2254.   if( p->inTrans!=TRANS_NONE ){
  2255.     pBt->nTransaction--;
  2256.     if( 0==pBt->nTransaction ){
  2257.       pBt->inTransaction = TRANS_NONE;
  2258.     }
  2259.   }
  2260.   /* Set the handles current transaction state to TRANS_NONE and unlock
  2261.   ** the pager if this call closed the only read or write transaction.
  2262.   */
  2263.   p->inTrans = TRANS_NONE;
  2264.   unlockBtreeIfUnused(pBt);
  2265.   btreeIntegrity(p);
  2266.   sqlite3BtreeLeave(p);
  2267.   return SQLITE_OK;
  2268. }
  2269. /*
  2270. ** Do both phases of a commit.
  2271. */
  2272. int sqlite3BtreeCommit(Btree *p){
  2273.   int rc;
  2274.   sqlite3BtreeEnter(p);
  2275.   rc = sqlite3BtreeCommitPhaseOne(p, 0);
  2276.   if( rc==SQLITE_OK ){
  2277.     rc = sqlite3BtreeCommitPhaseTwo(p);
  2278.   }
  2279.   sqlite3BtreeLeave(p);
  2280.   return rc;
  2281. }
  2282. #ifndef NDEBUG
  2283. /*
  2284. ** Return the number of write-cursors open on this handle. This is for use
  2285. ** in assert() expressions, so it is only compiled if NDEBUG is not
  2286. ** defined.
  2287. **
  2288. ** For the purposes of this routine, a write-cursor is any cursor that
  2289. ** is capable of writing to the databse.  That means the cursor was
  2290. ** originally opened for writing and the cursor has not be disabled
  2291. ** by having its state changed to CURSOR_FAULT.
  2292. */
  2293. static int countWriteCursors(BtShared *pBt){
  2294.   BtCursor *pCur;
  2295.   int r = 0;
  2296.   for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){
  2297.     if( pCur->wrFlag && pCur->eState!=CURSOR_FAULT ) r++; 
  2298.   }
  2299.   return r;
  2300. }
  2301. #endif
  2302. /*
  2303. ** This routine sets the state to CURSOR_FAULT and the error
  2304. ** code to errCode for every cursor on BtShared that pBtree
  2305. ** references.
  2306. **
  2307. ** Every cursor is tripped, including cursors that belong
  2308. ** to other database connections that happen to be sharing
  2309. ** the cache with pBtree.
  2310. **
  2311. ** This routine gets called when a rollback occurs.
  2312. ** All cursors using the same cache must be tripped
  2313. ** to prevent them from trying to use the btree after
  2314. ** the rollback.  The rollback may have deleted tables
  2315. ** or moved root pages, so it is not sufficient to
  2316. ** save the state of the cursor.  The cursor must be
  2317. ** invalidated.
  2318. */
  2319. void sqlite3BtreeTripAllCursors(Btree *pBtree, int errCode){
  2320.   BtCursor *p;
  2321.   sqlite3BtreeEnter(pBtree);
  2322.   for(p=pBtree->pBt->pCursor; p; p=p->pNext){
  2323.     clearCursorPosition(p);
  2324.     p->eState = CURSOR_FAULT;
  2325.     p->skip = errCode;
  2326.   }
  2327.   sqlite3BtreeLeave(pBtree);
  2328. }
  2329. /*
  2330. ** Rollback the transaction in progress.  All cursors will be
  2331. ** invalided by this operation.  Any attempt to use a cursor
  2332. ** that was open at the beginning of this operation will result
  2333. ** in an error.
  2334. **
  2335. ** This will release the write lock on the database file.  If there
  2336. ** are no active cursors, it also releases the read lock.
  2337. */
  2338. int sqlite3BtreeRollback(Btree *p){
  2339.   int rc;
  2340.   BtShared *pBt = p->pBt;
  2341.   MemPage *pPage1;
  2342.   sqlite3BtreeEnter(p);
  2343.   pBt->db = p->db;
  2344.   rc = saveAllCursors(pBt, 0, 0);
  2345. #ifndef SQLITE_OMIT_SHARED_CACHE
  2346.   if( rc!=SQLITE_OK ){
  2347.     /* This is a horrible situation. An IO or malloc() error occured whilst
  2348.     ** trying to save cursor positions. If this is an automatic rollback (as
  2349.     ** the result of a constraint, malloc() failure or IO error) then 
  2350.     ** the cache may be internally inconsistent (not contain valid trees) so
  2351.     ** we cannot simply return the error to the caller. Instead, abort 
  2352.     ** all queries that may be using any of the cursors that failed to save.
  2353.     */
  2354.     sqlite3BtreeTripAllCursors(p, rc);
  2355.   }
  2356. #endif
  2357.   btreeIntegrity(p);
  2358.   unlockAllTables(p);
  2359.   if( p->inTrans==TRANS_WRITE ){
  2360.     int rc2;
  2361. #ifndef SQLITE_OMIT_AUTOVACUUM
  2362.     pBt->nTrunc = 0;
  2363. #endif
  2364.     assert( TRANS_WRITE==pBt->inTransaction );
  2365.     rc2 = sqlite3PagerRollback(pBt->pPager);
  2366.     if( rc2!=SQLITE_OK ){
  2367.       rc = rc2;
  2368.     }
  2369.     /* The rollback may have destroyed the pPage1->aData value.  So
  2370.     ** call sqlite3BtreeGetPage() on page 1 again to make
  2371.     ** sure pPage1->aData is set correctly. */
  2372.     if( sqlite3BtreeGetPage(pBt, 1, &pPage1, 0)==SQLITE_OK ){
  2373.       releasePage(pPage1);
  2374.     }
  2375.     assert( countWriteCursors(pBt)==0 );
  2376.     pBt->inTransaction = TRANS_READ;
  2377.   }
  2378.   if( p->inTrans!=TRANS_NONE ){
  2379.     assert( pBt->nTransaction>0 );
  2380.     pBt->nTransaction--;
  2381.     if( 0==pBt->nTransaction ){
  2382.       pBt->inTransaction = TRANS_NONE;
  2383.     }
  2384.   }
  2385.   p->inTrans = TRANS_NONE;
  2386.   pBt->inStmt = 0;
  2387.   unlockBtreeIfUnused(pBt);
  2388.   btreeIntegrity(p);
  2389.   sqlite3BtreeLeave(p);
  2390.   return rc;
  2391. }
  2392. /*
  2393. ** Start a statement subtransaction.  The subtransaction can
  2394. ** can be rolled back independently of the main transaction.
  2395. ** You must start a transaction before starting a subtransaction.
  2396. ** The subtransaction is ended automatically if the main transaction
  2397. ** commits or rolls back.
  2398. **
  2399. ** Only one subtransaction may be active at a time.  It is an error to try
  2400. ** to start a new subtransaction if another subtransaction is already active.
  2401. **
  2402. ** Statement subtransactions are used around individual SQL statements
  2403. ** that are contained within a BEGIN...COMMIT block.  If a constraint
  2404. ** error occurs within the statement, the effect of that one statement
  2405. ** can be rolled back without having to rollback the entire transaction.
  2406. */
  2407. int sqlite3BtreeBeginStmt(Btree *p){
  2408.   int rc;
  2409.   BtShared *pBt = p->pBt;
  2410.   sqlite3BtreeEnter(p);
  2411.   pBt->db = p->db;
  2412.   if( (p->inTrans!=TRANS_WRITE) || pBt->inStmt ){
  2413.     rc = pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  2414.   }else{
  2415.     assert( pBt->inTransaction==TRANS_WRITE );
  2416.     rc = pBt->readOnly ? SQLITE_OK : sqlite3PagerStmtBegin(pBt->pPager);
  2417.     pBt->inStmt = 1;
  2418.   }
  2419.   sqlite3BtreeLeave(p);
  2420.   return rc;
  2421. }
  2422. /*
  2423. ** Commit the statment subtransaction currently in progress.  If no
  2424. ** subtransaction is active, this is a no-op.
  2425. */
  2426. int sqlite3BtreeCommitStmt(Btree *p){
  2427.   int rc;
  2428.   BtShared *pBt = p->pBt;
  2429.   sqlite3BtreeEnter(p);
  2430.   pBt->db = p->db;
  2431.   if( pBt->inStmt && !pBt->readOnly ){
  2432.     rc = sqlite3PagerStmtCommit(pBt->pPager);
  2433.   }else{
  2434.     rc = SQLITE_OK;
  2435.   }
  2436.   pBt->inStmt = 0;
  2437.   sqlite3BtreeLeave(p);
  2438.   return rc;
  2439. }
  2440. /*
  2441. ** Rollback the active statement subtransaction.  If no subtransaction
  2442. ** is active this routine is a no-op.
  2443. **
  2444. ** All cursors will be invalidated by this operation.  Any attempt
  2445. ** to use a cursor that was open at the beginning of this operation
  2446. ** will result in an error.
  2447. */
  2448. int sqlite3BtreeRollbackStmt(Btree *p){
  2449.   int rc = SQLITE_OK;
  2450.   BtShared *pBt = p->pBt;
  2451.   sqlite3BtreeEnter(p);
  2452.   pBt->db = p->db;
  2453.   if( pBt->inStmt && !pBt->readOnly ){
  2454.     rc = sqlite3PagerStmtRollback(pBt->pPager);
  2455.     assert( countWriteCursors(pBt)==0 );
  2456.     pBt->inStmt = 0;
  2457.   }
  2458.   sqlite3BtreeLeave(p);
  2459.   return rc;
  2460. }
  2461. /*
  2462. ** Create a new cursor for the BTree whose root is on the page
  2463. ** iTable.  The act of acquiring a cursor gets a read lock on 
  2464. ** the database file.
  2465. **
  2466. ** If wrFlag==0, then the cursor can only be used for reading.
  2467. ** If wrFlag==1, then the cursor can be used for reading or for
  2468. ** writing if other conditions for writing are also met.  These
  2469. ** are the conditions that must be met in order for writing to
  2470. ** be allowed:
  2471. **
  2472. ** 1:  The cursor must have been opened with wrFlag==1
  2473. **
  2474. ** 2:  Other database connections that share the same pager cache
  2475. **     but which are not in the READ_UNCOMMITTED state may not have
  2476. **     cursors open with wrFlag==0 on the same table.  Otherwise
  2477. **     the changes made by this write cursor would be visible to
  2478. **     the read cursors in the other database connection.
  2479. **
  2480. ** 3:  The database must be writable (not on read-only media)
  2481. **
  2482. ** 4:  There must be an active transaction.
  2483. **
  2484. ** No checking is done to make sure that page iTable really is the
  2485. ** root page of a b-tree.  If it is not, then the cursor acquired
  2486. ** will not work correctly.
  2487. */
  2488. static int btreeCursor(
  2489.   Btree *p,                              /* The btree */
  2490.   int iTable,                            /* Root page of table to open */
  2491.   int wrFlag,                            /* 1 to write. 0 read-only */
  2492.   struct KeyInfo *pKeyInfo,              /* First arg to comparison function */
  2493.   BtCursor *pCur                         /* Space for new cursor */
  2494. ){
  2495.   int rc;
  2496.   BtShared *pBt = p->pBt;
  2497.   assert( sqlite3BtreeHoldsMutex(p) );
  2498.   if( wrFlag ){
  2499.     if( pBt->readOnly ){
  2500.       return SQLITE_READONLY;
  2501.     }
  2502.     if( checkReadLocks(p, iTable, 0) ){
  2503.       return SQLITE_LOCKED;
  2504.     }
  2505.   }
  2506.   if( pBt->pPage1==0 ){
  2507.     rc = lockBtreeWithRetry(p);
  2508.     if( rc!=SQLITE_OK ){
  2509.       return rc;
  2510.     }
  2511.     if( pBt->readOnly && wrFlag ){
  2512.       return SQLITE_READONLY;
  2513.     }
  2514.   }
  2515.   pCur->pgnoRoot = (Pgno)iTable;
  2516.   if( iTable==1 && sqlite3PagerPagecount(pBt->pPager)==0 ){
  2517.     rc = SQLITE_EMPTY;
  2518.     goto create_cursor_exception;
  2519.   }
  2520.   rc = getAndInitPage(pBt, pCur->pgnoRoot, &pCur->pPage, 0);
  2521.   if( rc!=SQLITE_OK ){
  2522.     goto create_cursor_exception;
  2523.   }
  2524.   /* Now that no other errors can occur, finish filling in the BtCursor
  2525.   ** variables, link the cursor into the BtShared list and set *ppCur (the
  2526.   ** output argument to this function).
  2527.   */
  2528.   pCur->pKeyInfo = pKeyInfo;
  2529.   pCur->pBtree = p;
  2530.   pCur->pBt = pBt;
  2531.   pCur->wrFlag = wrFlag;
  2532.   pCur->pNext = pBt->pCursor;
  2533.   if( pCur->pNext ){
  2534.     pCur->pNext->pPrev = pCur;
  2535.   }
  2536.   pBt->pCursor = pCur;
  2537.   pCur->eState = CURSOR_INVALID;
  2538.   return SQLITE_OK;
  2539. create_cursor_exception:
  2540.   if( pCur ){
  2541.     releasePage(pCur->pPage);
  2542.   }
  2543.   unlockBtreeIfUnused(pBt);
  2544.   return rc;
  2545. }
  2546. int sqlite3BtreeCursor(
  2547.   Btree *p,                                   /* The btree */
  2548.   int iTable,                                 /* Root page of table to open */
  2549.   int wrFlag,                                 /* 1 to write. 0 read-only */
  2550.   struct KeyInfo *pKeyInfo,                   /* First arg to xCompare() */
  2551.   BtCursor *pCur                              /* Write new cursor here */
  2552. ){
  2553.   int rc;
  2554.   sqlite3BtreeEnter(p);
  2555.   p->pBt->db = p->db;
  2556.   rc = btreeCursor(p, iTable, wrFlag, pKeyInfo, pCur);
  2557.   sqlite3BtreeLeave(p);
  2558.   return rc;
  2559. }
  2560. int sqlite3BtreeCursorSize(){
  2561.   return sizeof(BtCursor);
  2562. }
  2563. /*
  2564. ** Close a cursor.  The read lock on the database file is released
  2565. ** when the last cursor is closed.
  2566. */
  2567. int sqlite3BtreeCloseCursor(BtCursor *pCur){
  2568.   Btree *pBtree = pCur->pBtree;
  2569.   if( pBtree ){
  2570.     BtShared *pBt = pCur->pBt;
  2571.     sqlite3BtreeEnter(pBtree);
  2572.     pBt->db = pBtree->db;
  2573.     clearCursorPosition(pCur);
  2574.     if( pCur->pPrev ){
  2575.       pCur->pPrev->pNext = pCur->pNext;
  2576.     }else{
  2577.       pBt->pCursor = pCur->pNext;
  2578.     }
  2579.     if( pCur->pNext ){
  2580.       pCur->pNext->pPrev = pCur->pPrev;
  2581.     }
  2582.     releasePage(pCur->pPage);
  2583.     unlockBtreeIfUnused(pBt);
  2584.     invalidateOverflowCache(pCur);
  2585.     /* sqlite3_free(pCur); */
  2586.     sqlite3BtreeLeave(pBtree);
  2587.   }
  2588.   return SQLITE_OK;
  2589. }
  2590. /*
  2591. ** Make a temporary cursor by filling in the fields of pTempCur.
  2592. ** The temporary cursor is not on the cursor list for the Btree.
  2593. */
  2594. void sqlite3BtreeGetTempCursor(BtCursor *pCur, BtCursor *pTempCur){
  2595.   assert( cursorHoldsMutex(pCur) );
  2596.   memcpy(pTempCur, pCur, sizeof(*pCur));
  2597.   pTempCur->pNext = 0;
  2598.   pTempCur->pPrev = 0;
  2599.   if( pTempCur->pPage ){
  2600.     sqlite3PagerRef(pTempCur->pPage->pDbPage);
  2601.   }
  2602. }
  2603. /*
  2604. ** Delete a temporary cursor such as was made by the CreateTemporaryCursor()
  2605. ** function above.
  2606. */
  2607. void sqlite3BtreeReleaseTempCursor(BtCursor *pCur){
  2608.   assert( cursorHoldsMutex(pCur) );
  2609.   if( pCur->pPage ){
  2610.     sqlite3PagerUnref(pCur->pPage->pDbPage);
  2611.   }
  2612. }
  2613. /*
  2614. ** Make sure the BtCursor* given in the argument has a valid
  2615. ** BtCursor.info structure.  If it is not already valid, call
  2616. ** sqlite3BtreeParseCell() to fill it in.
  2617. **
  2618. ** BtCursor.info is a cache of the information in the current cell.
  2619. ** Using this cache reduces the number of calls to sqlite3BtreeParseCell().
  2620. **
  2621. ** 2007-06-25:  There is a bug in some versions of MSVC that cause the
  2622. ** compiler to crash when getCellInfo() is implemented as a macro.
  2623. ** But there is a measureable speed advantage to using the macro on gcc
  2624. ** (when less compiler optimizations like -Os or -O0 are used and the
  2625. ** compiler is not doing agressive inlining.)  So we use a real function
  2626. ** for MSVC and a macro for everything else.  Ticket #2457.
  2627. */
  2628. #ifndef NDEBUG
  2629.   static void assertCellInfo(BtCursor *pCur){
  2630.     CellInfo info;
  2631.     memset(&info, 0, sizeof(info));
  2632.     sqlite3BtreeParseCell(pCur->pPage, pCur->idx, &info);
  2633.     assert( memcmp(&info, &pCur->info, sizeof(info))==0 );
  2634.   }
  2635. #else
  2636.   #define assertCellInfo(x)
  2637. #endif
  2638. #ifdef _MSC_VER
  2639.   /* Use a real function in MSVC to work around bugs in that compiler. */
  2640.   static void getCellInfo(BtCursor *pCur){
  2641.     if( pCur->info.nSize==0 ){
  2642.       sqlite3BtreeParseCell(pCur->pPage, pCur->idx, &pCur->info);
  2643.       pCur->validNKey = 1;
  2644.     }else{
  2645.       assertCellInfo(pCur);
  2646.     }
  2647.   }
  2648. #else /* if not _MSC_VER */
  2649.   /* Use a macro in all other compilers so that the function is inlined */
  2650. #define getCellInfo(pCur)                                               
  2651.   if( pCur->info.nSize==0 ){                                            
  2652.     sqlite3BtreeParseCell(pCur->pPage, pCur->idx, &pCur->info);         
  2653.     pCur->validNKey = 1;                                                
  2654.   }else{                                                                
  2655.     assertCellInfo(pCur);                                               
  2656.   }
  2657. #endif /* _MSC_VER */
  2658. /*
  2659. ** Set *pSize to the size of the buffer needed to hold the value of
  2660. ** the key for the current entry.  If the cursor is not pointing
  2661. ** to a valid entry, *pSize is set to 0. 
  2662. **
  2663. ** For a table with the INTKEY flag set, this routine returns the key
  2664. ** itself, not the number of bytes in the key.
  2665. */
  2666. int sqlite3BtreeKeySize(BtCursor *pCur, i64 *pSize){
  2667.   int rc;
  2668.   assert( cursorHoldsMutex(pCur) );
  2669.   rc = restoreOrClearCursorPosition(pCur);
  2670.   if( rc==SQLITE_OK ){
  2671.     assert( pCur->eState==CURSOR_INVALID || pCur->eState==CURSOR_VALID );
  2672.     if( pCur->eState==CURSOR_INVALID ){
  2673.       *pSize = 0;
  2674.     }else{
  2675.       getCellInfo(pCur);
  2676.       *pSize = pCur->info.nKey;
  2677.     }
  2678.   }
  2679.   return rc;
  2680. }
  2681. /*
  2682. ** Set *pSize to the number of bytes of data in the entry the
  2683. ** cursor currently points to.  Always return SQLITE_OK.
  2684. ** Failure is not possible.  If the cursor is not currently
  2685. ** pointing to an entry (which can happen, for example, if
  2686. ** the database is empty) then *pSize is set to 0.
  2687. */
  2688. int sqlite3BtreeDataSize(BtCursor *pCur, u32 *pSize){
  2689.   int rc;
  2690.   assert( cursorHoldsMutex(pCur) );
  2691.   rc = restoreOrClearCursorPosition(pCur);
  2692.   if( rc==SQLITE_OK ){
  2693.     assert( pCur->eState==CURSOR_INVALID || pCur->eState==CURSOR_VALID );
  2694.     if( pCur->eState==CURSOR_INVALID ){
  2695.       /* Not pointing at a valid entry - set *pSize to 0. */
  2696.       *pSize = 0;
  2697.     }else{
  2698.       getCellInfo(pCur);
  2699.       *pSize = pCur->info.nData;
  2700.     }
  2701.   }
  2702.   return rc;
  2703. }
  2704. /*
  2705. ** Given the page number of an overflow page in the database (parameter
  2706. ** ovfl), this function finds the page number of the next page in the 
  2707. ** linked list of overflow pages. If possible, it uses the auto-vacuum
  2708. ** pointer-map data instead of reading the content of page ovfl to do so. 
  2709. **
  2710. ** If an error occurs an SQLite error code is returned. Otherwise:
  2711. **
  2712. ** Unless pPgnoNext is NULL, the page number of the next overflow 
  2713. ** page in the linked list is written to *pPgnoNext. If page ovfl
  2714. ** is the last page in its linked list, *pPgnoNext is set to zero. 
  2715. **
  2716. ** If ppPage is not NULL, *ppPage is set to the MemPage* handle
  2717. ** for page ovfl. The underlying pager page may have been requested
  2718. ** with the noContent flag set, so the page data accessable via
  2719. ** this handle may not be trusted.
  2720. */
  2721. static int getOverflowPage(
  2722.   BtShared *pBt, 
  2723.   Pgno ovfl,                   /* Overflow page */
  2724.   MemPage **ppPage,            /* OUT: MemPage handle */
  2725.   Pgno *pPgnoNext              /* OUT: Next overflow page number */
  2726. ){
  2727.   Pgno next = 0;
  2728.   int rc;
  2729.   assert( sqlite3_mutex_held(pBt->mutex) );
  2730.   /* One of these must not be NULL. Otherwise, why call this function? */
  2731.   assert(ppPage || pPgnoNext);
  2732.   /* If pPgnoNext is NULL, then this function is being called to obtain
  2733.   ** a MemPage* reference only. No page-data is required in this case.
  2734.   */
  2735.   if( !pPgnoNext ){
  2736.     return sqlite3BtreeGetPage(pBt, ovfl, ppPage, 1);
  2737.   }
  2738. #ifndef SQLITE_OMIT_AUTOVACUUM
  2739.   /* Try to find the next page in the overflow list using the
  2740.   ** autovacuum pointer-map pages. Guess that the next page in 
  2741.   ** the overflow list is page number (ovfl+1). If that guess turns 
  2742.   ** out to be wrong, fall back to loading the data of page 
  2743.   ** number ovfl to determine the next page number.
  2744.   */
  2745.   if( pBt->autoVacuum ){
  2746.     Pgno pgno;
  2747.     Pgno iGuess = ovfl+1;
  2748.     u8 eType;
  2749.     while( PTRMAP_ISPAGE(pBt, iGuess) || iGuess==PENDING_BYTE_PAGE(pBt) ){
  2750.       iGuess++;
  2751.     }
  2752.     if( iGuess<=sqlite3PagerPagecount(pBt->pPager) ){
  2753.       rc = ptrmapGet(pBt, iGuess, &eType, &pgno);
  2754.       if( rc!=SQLITE_OK ){
  2755.         return rc;
  2756.       }
  2757.       if( eType==PTRMAP_OVERFLOW2 && pgno==ovfl ){
  2758.         next = iGuess;
  2759.       }
  2760.     }
  2761.   }
  2762. #endif
  2763.   if( next==0 || ppPage ){
  2764.     MemPage *pPage = 0;
  2765.     rc = sqlite3BtreeGetPage(pBt, ovfl, &pPage, next!=0);
  2766.     assert(rc==SQLITE_OK || pPage==0);
  2767.     if( next==0 && rc==SQLITE_OK ){
  2768.       next = get4byte(pPage->aData);
  2769.     }
  2770.     if( ppPage ){
  2771.       *ppPage = pPage;
  2772.     }else{
  2773.       releasePage(pPage);
  2774.     }
  2775.   }
  2776.   *pPgnoNext = next;
  2777.   return rc;
  2778. }
  2779. /*
  2780. ** Copy data from a buffer to a page, or from a page to a buffer.
  2781. **
  2782. ** pPayload is a pointer to data stored on database page pDbPage.
  2783. ** If argument eOp is false, then nByte bytes of data are copied
  2784. ** from pPayload to the buffer pointed at by pBuf. If eOp is true,
  2785. ** then sqlite3PagerWrite() is called on pDbPage and nByte bytes
  2786. ** of data are copied from the buffer pBuf to pPayload.
  2787. **
  2788. ** SQLITE_OK is returned on success, otherwise an error code.
  2789. */
  2790. static int copyPayload(
  2791.   void *pPayload,           /* Pointer to page data */
  2792.   void *pBuf,               /* Pointer to buffer */
  2793.   int nByte,                /* Number of bytes to copy */
  2794.   int eOp,                  /* 0 -> copy from page, 1 -> copy to page */
  2795.   DbPage *pDbPage           /* Page containing pPayload */
  2796. ){
  2797.   if( eOp ){
  2798.     /* Copy data from buffer to page (a write operation) */
  2799.     int rc = sqlite3PagerWrite(pDbPage);
  2800.     if( rc!=SQLITE_OK ){
  2801.       return rc;
  2802.     }
  2803.     memcpy(pPayload, pBuf, nByte);
  2804.   }else{
  2805.     /* Copy data from page to buffer (a read operation) */
  2806.     memcpy(pBuf, pPayload, nByte);
  2807.   }
  2808.   return SQLITE_OK;
  2809. }
  2810. /*
  2811. ** This function is used to read or overwrite payload information
  2812. ** for the entry that the pCur cursor is pointing to. If the eOp
  2813. ** parameter is 0, this is a read operation (data copied into
  2814. ** buffer pBuf). If it is non-zero, a write (data copied from
  2815. ** buffer pBuf).
  2816. **
  2817. ** A total of "amt" bytes are read or written beginning at "offset".
  2818. ** Data is read to or from the buffer pBuf.
  2819. **
  2820. ** This routine does not make a distinction between key and data.
  2821. ** It just reads or writes bytes from the payload area.  Data might 
  2822. ** appear on the main page or be scattered out on multiple overflow 
  2823. ** pages.
  2824. **
  2825. ** If the BtCursor.isIncrblobHandle flag is set, and the current
  2826. ** cursor entry uses one or more overflow pages, this function
  2827. ** allocates space for and lazily popluates the overflow page-list 
  2828. ** cache array (BtCursor.aOverflow). Subsequent calls use this
  2829. ** cache to make seeking to the supplied offset more efficient.
  2830. **
  2831. ** Once an overflow page-list cache has been allocated, it may be
  2832. ** invalidated if some other cursor writes to the same table, or if
  2833. ** the cursor is moved to a different row. Additionally, in auto-vacuum
  2834. ** mode, the following events may invalidate an overflow page-list cache.
  2835. **
  2836. **   * An incremental vacuum,
  2837. **   * A commit in auto_vacuum="full" mode,
  2838. **   * Creating a table (may require moving an overflow page).
  2839. */
  2840. static int accessPayload(
  2841.   BtCursor *pCur,      /* Cursor pointing to entry to read from */
  2842.   int offset,          /* Begin reading this far into payload */
  2843.   int amt,             /* Read this many bytes */
  2844.   unsigned char *pBuf, /* Write the bytes into this buffer */ 
  2845.   int skipKey,         /* offset begins at data if this is true */
  2846.   int eOp              /* zero to read. non-zero to write. */
  2847. ){
  2848.   unsigned char *aPayload;
  2849.   int rc = SQLITE_OK;
  2850.   u32 nKey;
  2851.   int iIdx = 0;
  2852.   MemPage *pPage = pCur->pPage;     /* Btree page of current cursor entry */
  2853.   BtShared *pBt;                   /* Btree this cursor belongs to */
  2854.   assert( pPage );
  2855.   assert( pCur->eState==CURSOR_VALID );
  2856.   assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
  2857.   assert( offset>=0 );
  2858.   assert( cursorHoldsMutex(pCur) );
  2859.   getCellInfo(pCur);
  2860.   aPayload = pCur->info.pCell + pCur->info.nHeader;
  2861.   nKey = (pPage->intKey ? 0 : pCur->info.nKey);
  2862.   if( skipKey ){
  2863.     offset += nKey;
  2864.   }
  2865.   if( offset+amt > nKey+pCur->info.nData ){
  2866.     /* Trying to read or write past the end of the data is an error */
  2867.     return SQLITE_ERROR;
  2868.   }
  2869.   /* Check if data must be read/written to/from the btree page itself. */
  2870.   if( offset<pCur->info.nLocal ){
  2871.     int a = amt;
  2872.     if( a+offset>pCur->info.nLocal ){
  2873.       a = pCur->info.nLocal - offset;
  2874.     }
  2875.     rc = copyPayload(&aPayload[offset], pBuf, a, eOp, pPage->pDbPage);
  2876.     offset = 0;
  2877.     pBuf += a;
  2878.     amt -= a;
  2879.   }else{
  2880.     offset -= pCur->info.nLocal;
  2881.   }
  2882.   pBt = pCur->pBt;
  2883.   if( rc==SQLITE_OK && amt>0 ){
  2884.     const int ovflSize = pBt->usableSize - 4;  /* Bytes content per ovfl page */
  2885.     Pgno nextPage;
  2886.     nextPage = get4byte(&aPayload[pCur->info.nLocal]);
  2887. #ifndef SQLITE_OMIT_INCRBLOB
  2888.     /* If the isIncrblobHandle flag is set and the BtCursor.aOverflow[]
  2889.     ** has not been allocated, allocate it now. The array is sized at
  2890.     ** one entry for each overflow page in the overflow chain. The
  2891.     ** page number of the first overflow page is stored in aOverflow[0],
  2892.     ** etc. A value of 0 in the aOverflow[] array means "not yet known"
  2893.     ** (the cache is lazily populated).
  2894.     */
  2895.     if( pCur->isIncrblobHandle && !pCur->aOverflow ){
  2896.       int nOvfl = (pCur->info.nPayload-pCur->info.nLocal+ovflSize-1)/ovflSize;
  2897.       pCur->aOverflow = (Pgno *)sqlite3MallocZero(sizeof(Pgno)*nOvfl);
  2898.       if( nOvfl && !pCur->aOverflow ){
  2899.         rc = SQLITE_NOMEM;
  2900.       }
  2901.     }
  2902.     /* If the overflow page-list cache has been allocated and the
  2903.     ** entry for the first required overflow page is valid, skip
  2904.     ** directly to it.
  2905.     */
  2906.     if( pCur->aOverflow && pCur->aOverflow[offset/ovflSize] ){
  2907.       iIdx = (offset/ovflSize);
  2908.       nextPage = pCur->aOverflow[iIdx];
  2909.       offset = (offset%ovflSize);
  2910.     }
  2911. #endif
  2912.     for( ; rc==SQLITE_OK && amt>0 && nextPage; iIdx++){
  2913. #ifndef SQLITE_OMIT_INCRBLOB
  2914.       /* If required, populate the overflow page-list cache. */
  2915.       if( pCur->aOverflow ){
  2916.         assert(!pCur->aOverflow[iIdx] || pCur->aOverflow[iIdx]==nextPage);
  2917.         pCur->aOverflow[iIdx] = nextPage;
  2918.       }
  2919. #endif
  2920.       if( offset>=ovflSize ){
  2921.         /* The only reason to read this page is to obtain the page
  2922.         ** number for the next page in the overflow chain. The page
  2923.         ** data is not required. So first try to lookup the overflow
  2924.         ** page-list cache, if any, then fall back to the getOverflowPage()
  2925.         ** function.
  2926.         */
  2927. #ifndef SQLITE_OMIT_INCRBLOB
  2928.         if( pCur->aOverflow && pCur->aOverflow[iIdx+1] ){
  2929.           nextPage = pCur->aOverflow[iIdx+1];
  2930.         } else 
  2931. #endif
  2932.           rc = getOverflowPage(pBt, nextPage, 0, &nextPage);
  2933.         offset -= ovflSize;
  2934.       }else{
  2935.         /* Need to read this page properly. It contains some of the
  2936.         ** range of data that is being read (eOp==0) or written (eOp!=0).
  2937.         */
  2938.         DbPage *pDbPage;
  2939.         int a = amt;
  2940.         rc = sqlite3PagerGet(pBt->pPager, nextPage, &pDbPage);
  2941.         if( rc==SQLITE_OK ){
  2942.           aPayload = sqlite3PagerGetData(pDbPage);
  2943.           nextPage = get4byte(aPayload);
  2944.           if( a + offset > ovflSize ){
  2945.             a = ovflSize - offset;
  2946.           }
  2947.           rc = copyPayload(&aPayload[offset+4], pBuf, a, eOp, pDbPage);
  2948.           sqlite3PagerUnref(pDbPage);
  2949.           offset = 0;
  2950.           amt -= a;
  2951.           pBuf += a;
  2952.         }
  2953.       }
  2954.     }
  2955.   }
  2956.   if( rc==SQLITE_OK && amt>0 ){
  2957.     return SQLITE_CORRUPT_BKPT;
  2958.   }
  2959.   return rc;
  2960. }
  2961. /*
  2962. ** Read part of the key associated with cursor pCur.  Exactly
  2963. ** "amt" bytes will be transfered into pBuf[].  The transfer
  2964. ** begins at "offset".
  2965. **
  2966. ** Return SQLITE_OK on success or an error code if anything goes
  2967. ** wrong.  An error is returned if "offset+amt" is larger than
  2968. ** the available payload.
  2969. */
  2970. int sqlite3BtreeKey(BtCursor *pCur, u32 offset, u32 amt, void *pBuf){
  2971.   int rc;
  2972.   assert( cursorHoldsMutex(pCur) );
  2973.   rc = restoreOrClearCursorPosition(pCur);
  2974.   if( rc==SQLITE_OK ){
  2975.     assert( pCur->eState==CURSOR_VALID );
  2976.     assert( pCur->pPage!=0 );
  2977.     if( pCur->pPage->intKey ){
  2978.       return SQLITE_CORRUPT_BKPT;
  2979.     }
  2980.     assert( pCur->pPage->intKey==0 );
  2981.     assert( pCur->idx>=0 && pCur->idx<pCur->pPage->nCell );
  2982.     rc = accessPayload(pCur, offset, amt, (unsigned char*)pBuf, 0, 0);
  2983.   }
  2984.   return rc;
  2985. }
  2986. /*
  2987. ** Read part of the data associated with cursor pCur.  Exactly
  2988. ** "amt" bytes will be transfered into pBuf[].  The transfer
  2989. ** begins at "offset".
  2990. **
  2991. ** Return SQLITE_OK on success or an error code if anything goes
  2992. ** wrong.  An error is returned if "offset+amt" is larger than
  2993. ** the available payload.
  2994. */
  2995. int sqlite3BtreeData(BtCursor *pCur, u32 offset, u32 amt, void *pBuf){
  2996.   int rc;
  2997.   assert( cursorHoldsMutex(pCur) );
  2998.   rc = restoreOrClearCursorPosition(pCur);
  2999.   if( rc==SQLITE_OK ){
  3000.     assert( pCur->eState==CURSOR_VALID );
  3001.     assert( pCur->pPage!=0 );
  3002.     assert( pCur->idx>=0 && pCur->idx<pCur->pPage->nCell );
  3003.     rc = accessPayload(pCur, offset, amt, pBuf, 1, 0);
  3004.   }
  3005.   return rc;
  3006. }
  3007. /*
  3008. ** Return a pointer to payload information from the entry that the 
  3009. ** pCur cursor is pointing to.  The pointer is to the beginning of
  3010. ** the key if skipKey==0 and it points to the beginning of data if
  3011. ** skipKey==1.  The number of bytes of available key/data is written
  3012. ** into *pAmt.  If *pAmt==0, then the value returned will not be
  3013. ** a valid pointer.
  3014. **
  3015. ** This routine is an optimization.  It is common for the entire key
  3016. ** and data to fit on the local page and for there to be no overflow
  3017. ** pages.  When that is so, this routine can be used to access the
  3018. ** key and data without making a copy.  If the key and/or data spills
  3019. ** onto overflow pages, then accessPayload() must be used to reassembly
  3020. ** the key/data and copy it into a preallocated buffer.
  3021. **
  3022. ** The pointer returned by this routine looks directly into the cached
  3023. ** page of the database.  The data might change or move the next time
  3024. ** any btree routine is called.
  3025. */
  3026. static const unsigned char *fetchPayload(
  3027.   BtCursor *pCur,      /* Cursor pointing to entry to read from */
  3028.   int *pAmt,           /* Write the number of available bytes here */
  3029.   int skipKey          /* read beginning at data if this is true */
  3030. ){
  3031.   unsigned char *aPayload;
  3032.   MemPage *pPage;
  3033.   u32 nKey;
  3034.   int nLocal;
  3035.   assert( pCur!=0 && pCur->pPage!=0 );
  3036.   assert( pCur->eState==CURSOR_VALID );
  3037.   assert( cursorHoldsMutex(pCur) );
  3038.   pPage = pCur->pPage;
  3039.   assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
  3040.   getCellInfo(pCur);
  3041.   aPayload = pCur->info.pCell;
  3042.   aPayload += pCur->info.nHeader;
  3043.   if( pPage->intKey ){
  3044.     nKey = 0;
  3045.   }else{
  3046.     nKey = pCur->info.nKey;
  3047.   }
  3048.   if( skipKey ){
  3049.     aPayload += nKey;
  3050.     nLocal = pCur->info.nLocal - nKey;
  3051.   }else{
  3052.     nLocal = pCur->info.nLocal;
  3053.     if( nLocal>nKey ){
  3054.       nLocal = nKey;
  3055.     }
  3056.   }
  3057.   *pAmt = nLocal;
  3058.   return aPayload;
  3059. }
  3060. /*
  3061. ** For the entry that cursor pCur is point to, return as
  3062. ** many bytes of the key or data as are available on the local
  3063. ** b-tree page.  Write the number of available bytes into *pAmt.
  3064. **
  3065. ** The pointer returned is ephemeral.  The key/data may move
  3066. ** or be destroyed on the next call to any Btree routine,
  3067. ** including calls from other threads against the same cache.
  3068. ** Hence, a mutex on the BtShared should be held prior to calling
  3069. ** this routine.
  3070. **
  3071. ** These routines is used to get quick access to key and data
  3072. ** in the common case where no overflow pages are used.
  3073. */
  3074. const void *sqlite3BtreeKeyFetch(BtCursor *pCur, int *pAmt){
  3075.   assert( cursorHoldsMutex(pCur) );
  3076.   if( pCur->eState==CURSOR_VALID ){
  3077.     return (const void*)fetchPayload(pCur, pAmt, 0);
  3078.   }
  3079.   return 0;
  3080. }
  3081. const void *sqlite3BtreeDataFetch(BtCursor *pCur, int *pAmt){
  3082.   assert( cursorHoldsMutex(pCur) );
  3083.   if( pCur->eState==CURSOR_VALID ){
  3084.     return (const void*)fetchPayload(pCur, pAmt, 1);
  3085.   }
  3086.   return 0;
  3087. }
  3088. /*
  3089. ** Move the cursor down to a new child page.  The newPgno argument is the
  3090. ** page number of the child page to move to.
  3091. */
  3092. static int moveToChild(BtCursor *pCur, u32 newPgno){
  3093.   int rc;
  3094.   MemPage *pNewPage;
  3095.   MemPage *pOldPage;
  3096.   BtShared *pBt = pCur->pBt;
  3097.   assert( cursorHoldsMutex(pCur) );
  3098.   assert( pCur->eState==CURSOR_VALID );
  3099.   rc = getAndInitPage(pBt, newPgno, &pNewPage, pCur->pPage);
  3100.   if( rc ) return rc;
  3101.   pNewPage->idxParent = pCur->idx;
  3102.   pOldPage = pCur->pPage;
  3103.   pOldPage->idxShift = 0;
  3104.   releasePage(pOldPage);
  3105.   pCur->pPage = pNewPage;
  3106.   pCur->idx = 0;
  3107.   pCur->info.nSize = 0;
  3108.   pCur->validNKey = 0;
  3109.   if( pNewPage->nCell<1 ){
  3110.     return SQLITE_CORRUPT_BKPT;
  3111.   }
  3112.   return SQLITE_OK;
  3113. }
  3114. /*
  3115. ** Return true if the page is the virtual root of its table.
  3116. **
  3117. ** The virtual root page is the root page for most tables.  But
  3118. ** for the table rooted on page 1, sometime the real root page
  3119. ** is empty except for the right-pointer.  In such cases the
  3120. ** virtual root page is the page that the right-pointer of page
  3121. ** 1 is pointing to.
  3122. */
  3123. int sqlite3BtreeIsRootPage(MemPage *pPage){
  3124.   MemPage *pParent;
  3125.   assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  3126.   pParent = pPage->pParent;
  3127.   if( pParent==0 ) return 1;
  3128.   if( pParent->pgno>1 ) return 0;
  3129.   if( get2byte(&pParent->aData[pParent->hdrOffset+3])==0 ) return 1;
  3130.   return 0;
  3131. }
  3132. /*
  3133. ** Move the cursor up to the parent page.
  3134. **
  3135. ** pCur->idx is set to the cell index that contains the pointer
  3136. ** to the page we are coming from.  If we are coming from the
  3137. ** right-most child page then pCur->idx is set to one more than
  3138. ** the largest cell index.
  3139. */
  3140. void sqlite3BtreeMoveToParent(BtCursor *pCur){
  3141.   MemPage *pParent;
  3142.   MemPage *pPage;
  3143.   int idxParent;
  3144.   assert( cursorHoldsMutex(pCur) );
  3145.   assert( pCur->eState==CURSOR_VALID );
  3146.   pPage = pCur->pPage;
  3147.   assert( pPage!=0 );
  3148.   assert( !sqlite3BtreeIsRootPage(pPage) );
  3149.   pParent = pPage->pParent;
  3150.   assert( pParent!=0 );
  3151.   idxParent = pPage->idxParent;
  3152.   sqlite3PagerRef(pParent->pDbPage);
  3153.   releasePage(pPage);
  3154.   pCur->pPage = pParent;
  3155.   pCur->info.nSize = 0;
  3156.   pCur->validNKey = 0;
  3157.   assert( pParent->idxShift==0 );
  3158.   pCur->idx = idxParent;
  3159. }
  3160. /*
  3161. ** Move the cursor to the root page
  3162. */
  3163. static int moveToRoot(BtCursor *pCur){
  3164.   MemPage *pRoot;
  3165.   int rc = SQLITE_OK;
  3166.   Btree *p = pCur->pBtree;
  3167.   BtShared *pBt = p->pBt;
  3168.   assert( cursorHoldsMutex(pCur) );
  3169.   assert( CURSOR_INVALID < CURSOR_REQUIRESEEK );
  3170.   assert( CURSOR_VALID   < CURSOR_REQUIRESEEK );
  3171.   assert( CURSOR_FAULT   > CURSOR_REQUIRESEEK );
  3172.   if( pCur->eState>=CURSOR_REQUIRESEEK ){
  3173.     if( pCur->eState==CURSOR_FAULT ){
  3174.       return pCur->skip;
  3175.     }
  3176.     clearCursorPosition(pCur);
  3177.   }
  3178.   pRoot = pCur->pPage;
  3179.   if( pRoot && pRoot->pgno==pCur->pgnoRoot ){
  3180.     assert( pRoot->isInit );
  3181.   }else{
  3182.     if( 
  3183.       SQLITE_OK!=(rc = getAndInitPage(pBt, pCur->pgnoRoot, &pRoot, 0))
  3184.     ){
  3185.       pCur->eState = CURSOR_INVALID;
  3186.       return rc;
  3187.     }
  3188.     releasePage(pCur->pPage);
  3189.     pCur->pPage = pRoot;
  3190.   }
  3191.   pCur->idx = 0;
  3192.   pCur->info.nSize = 0;
  3193.   pCur->atLast = 0;
  3194.   pCur->validNKey = 0;
  3195.   if( pRoot->nCell==0 && !pRoot->leaf ){
  3196.     Pgno subpage;
  3197.     assert( pRoot->pgno==1 );
  3198.     subpage = get4byte(&pRoot->aData[pRoot->hdrOffset+8]);
  3199.     assert( subpage>0 );
  3200.     pCur->eState = CURSOR_VALID;
  3201.     rc = moveToChild(pCur, subpage);
  3202.   }
  3203.   pCur->eState = ((pCur->pPage->nCell>0)?CURSOR_VALID:CURSOR_INVALID);
  3204.   return rc;
  3205. }
  3206. /*
  3207. ** Move the cursor down to the left-most leaf entry beneath the
  3208. ** entry to which it is currently pointing.
  3209. **
  3210. ** The left-most leaf is the one with the smallest key - the first
  3211. ** in ascending order.
  3212. */
  3213. static int moveToLeftmost(BtCursor *pCur){
  3214.   Pgno pgno;
  3215.   int rc = SQLITE_OK;
  3216.   MemPage *pPage;
  3217.   assert( cursorHoldsMutex(pCur) );
  3218.   assert( pCur->eState==CURSOR_VALID );
  3219.   while( rc==SQLITE_OK && !(pPage = pCur->pPage)->leaf ){
  3220.     assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
  3221.     pgno = get4byte(findCell(pPage, pCur->idx));
  3222.     rc = moveToChild(pCur, pgno);
  3223.   }
  3224.   return rc;
  3225. }
  3226. /*
  3227. ** Move the cursor down to the right-most leaf entry beneath the
  3228. ** page to which it is currently pointing.  Notice the difference
  3229. ** between moveToLeftmost() and moveToRightmost().  moveToLeftmost()
  3230. ** finds the left-most entry beneath the *entry* whereas moveToRightmost()
  3231. ** finds the right-most entry beneath the *page*.
  3232. **
  3233. ** The right-most entry is the one with the largest key - the last
  3234. ** key in ascending order.
  3235. */
  3236. static int moveToRightmost(BtCursor *pCur){
  3237.   Pgno pgno;
  3238.   int rc = SQLITE_OK;
  3239.   MemPage *pPage;
  3240.   assert( cursorHoldsMutex(pCur) );
  3241.   assert( pCur->eState==CURSOR_VALID );
  3242.   while( rc==SQLITE_OK && !(pPage = pCur->pPage)->leaf ){
  3243.     pgno = get4byte(&pPage->aData[pPage->hdrOffset+8]);
  3244.     pCur->idx = pPage->nCell;
  3245.     rc = moveToChild(pCur, pgno);
  3246.   }
  3247.   if( rc==SQLITE_OK ){
  3248.     pCur->idx = pPage->nCell - 1;
  3249.     pCur->info.nSize = 0;
  3250.     pCur->validNKey = 0;
  3251.   }
  3252.   return SQLITE_OK;
  3253. }
  3254. /* Move the cursor to the first entry in the table.  Return SQLITE_OK
  3255. ** on success.  Set *pRes to 0 if the cursor actually points to something
  3256. ** or set *pRes to 1 if the table is empty.
  3257. */
  3258. int sqlite3BtreeFirst(BtCursor *pCur, int *pRes){
  3259.   int rc;
  3260.   assert( cursorHoldsMutex(pCur) );
  3261.   assert( sqlite3_mutex_held(pCur->pBtree->db->mutex) );
  3262.   rc = moveToRoot(pCur);
  3263.   if( rc==SQLITE_OK ){
  3264.     if( pCur->eState==CURSOR_INVALID ){
  3265.       assert( pCur->pPage->nCell==0 );
  3266.       *pRes = 1;
  3267.       rc = SQLITE_OK;
  3268.     }else{
  3269.       assert( pCur->pPage->nCell>0 );
  3270.       *pRes = 0;
  3271.       rc = moveToLeftmost(pCur);
  3272.     }
  3273.   }
  3274.   return rc;
  3275. }
  3276. /* Move the cursor to the last entry in the table.  Return SQLITE_OK
  3277. ** on success.  Set *pRes to 0 if the cursor actually points to something
  3278. ** or set *pRes to 1 if the table is empty.
  3279. */
  3280. int sqlite3BtreeLast(BtCursor *pCur, int *pRes){
  3281.   int rc;
  3282.  
  3283.   assert( cursorHoldsMutex(pCur) );
  3284.   assert( sqlite3_mutex_held(pCur->pBtree->db->mutex) );
  3285.   rc = moveToRoot(pCur);
  3286.   if( rc==SQLITE_OK ){
  3287.     if( CURSOR_INVALID==pCur->eState ){
  3288.       assert( pCur->pPage->nCell==0 );
  3289.       *pRes = 1;
  3290.     }else{
  3291.       assert( pCur->eState==CURSOR_VALID );
  3292.       *pRes = 0;
  3293.       rc = moveToRightmost(pCur);
  3294.       getCellInfo(pCur);
  3295.       pCur->atLast = rc==SQLITE_OK;
  3296.     }
  3297.   }
  3298.   return rc;
  3299. }
  3300. /* Move the cursor so that it points to an entry near the key 
  3301. ** specified by pKey/nKey/pUnKey. Return a success code.
  3302. **
  3303. ** For INTKEY tables, only the nKey parameter is used.  pKey 
  3304. ** and pUnKey must be NULL.  For index tables, either pUnKey
  3305. ** must point to a key that has already been unpacked, or else
  3306. ** pKey/nKey describes a blob containing the key.
  3307. **
  3308. ** If an exact match is not found, then the cursor is always
  3309. ** left pointing at a leaf page which would hold the entry if it
  3310. ** were present.  The cursor might point to an entry that comes