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

数据库系统

开发平台:

C/C++

  1. ** before or after the key.
  2. **
  3. ** The result of comparing the key with the entry to which the
  4. ** cursor is written to *pRes if pRes!=NULL.  The meaning of
  5. ** this value is as follows:
  6. **
  7. **     *pRes<0      The cursor is left pointing at an entry that
  8. **                  is smaller than pKey or if the table is empty
  9. **                  and the cursor is therefore left point to nothing.
  10. **
  11. **     *pRes==0     The cursor is left pointing at an entry that
  12. **                  exactly matches pKey.
  13. **
  14. **     *pRes>0      The cursor is left pointing at an entry that
  15. **                  is larger than pKey.
  16. **
  17. */
  18. int sqlite3BtreeMoveto(
  19.   BtCursor *pCur,        /* The cursor to be moved */
  20.   const void *pKey,      /* The key content for indices.  Not used by tables */
  21.   UnpackedRecord *pUnKey,/* Unpacked version of pKey */
  22.   i64 nKey,              /* Size of pKey.  Or the key for tables */
  23.   int biasRight,         /* If true, bias the search to the high end */
  24.   int *pRes              /* Search result flag */
  25. ){
  26.   int rc;
  27.   char aSpace[200];
  28.   assert( cursorHoldsMutex(pCur) );
  29.   assert( sqlite3_mutex_held(pCur->pBtree->db->mutex) );
  30.   /* If the cursor is already positioned at the point we are trying
  31.   ** to move to, then just return without doing any work */
  32.   if( pCur->eState==CURSOR_VALID && pCur->validNKey && pCur->pPage->intKey ){
  33.     if( pCur->info.nKey==nKey ){
  34.       *pRes = 0;
  35.       return SQLITE_OK;
  36.     }
  37.     if( pCur->atLast && pCur->info.nKey<nKey ){
  38.       *pRes = -1;
  39.       return SQLITE_OK;
  40.     }
  41.   }
  42.   rc = moveToRoot(pCur);
  43.   if( rc ){
  44.     return rc;
  45.   }
  46.   assert( pCur->pPage );
  47.   assert( pCur->pPage->isInit );
  48.   if( pCur->eState==CURSOR_INVALID ){
  49.     *pRes = -1;
  50.     assert( pCur->pPage->nCell==0 );
  51.     return SQLITE_OK;
  52.   }
  53.   if( pCur->pPage->intKey ){
  54.     /* We are given an SQL table to search.  The key is the integer
  55.     ** rowid contained in nKey.  pKey and pUnKey should both be NULL */
  56.     assert( pUnKey==0 );
  57.     assert( pKey==0 );
  58.   }else if( pUnKey==0 ){
  59.     /* We are to search an SQL index using a key encoded as a blob.
  60.     ** The blob is found at pKey and is nKey bytes in length.  Unpack
  61.     ** this key so that we can use it. */
  62.     assert( pKey!=0 );
  63.     pUnKey = sqlite3VdbeRecordUnpack(pCur->pKeyInfo, nKey, pKey,
  64.                                    aSpace, sizeof(aSpace));
  65.     if( pUnKey==0 ) return SQLITE_NOMEM;
  66.   }else{
  67.     /* We are to search an SQL index using a key that is already unpacked
  68.     ** and handed to us in pUnKey. */
  69.     assert( pKey==0 );
  70.   }
  71.   for(;;){
  72.     int lwr, upr;
  73.     Pgno chldPg;
  74.     MemPage *pPage = pCur->pPage;
  75.     int c = -1;  /* pRes return if table is empty must be -1 */
  76.     lwr = 0;
  77.     upr = pPage->nCell-1;
  78.     if( !pPage->intKey && pUnKey==0 ){
  79.       rc = SQLITE_CORRUPT_BKPT;
  80.       goto moveto_finish;
  81.     }
  82.     if( biasRight ){
  83.       pCur->idx = upr;
  84.     }else{
  85.       pCur->idx = (upr+lwr)/2;
  86.     }
  87.     if( lwr<=upr ) for(;;){
  88.       void *pCellKey;
  89.       i64 nCellKey;
  90.       pCur->info.nSize = 0;
  91.       pCur->validNKey = 1;
  92.       if( pPage->intKey ){
  93.         u8 *pCell;
  94.         pCell = findCell(pPage, pCur->idx) + pPage->childPtrSize;
  95.         if( pPage->hasData ){
  96.           u32 dummy;
  97.           pCell += getVarint32(pCell, &dummy);
  98.         }
  99.         getVarint(pCell, (u64*)&nCellKey);
  100.         if( nCellKey==nKey ){
  101.           c = 0;
  102.         }else if( nCellKey<nKey ){
  103.           c = -1;
  104.         }else{
  105.           assert( nCellKey>nKey );
  106.           c = +1;
  107.         }
  108.       }else{
  109.         int available;
  110.         pCellKey = (void *)fetchPayload(pCur, &available, 0);
  111.         nCellKey = pCur->info.nKey;
  112.         if( available>=nCellKey ){
  113.           c = sqlite3VdbeRecordCompare(nCellKey, pCellKey, pUnKey);
  114.         }else{
  115.           pCellKey = sqlite3_malloc( nCellKey );
  116.           if( pCellKey==0 ){
  117.             rc = SQLITE_NOMEM;
  118.             goto moveto_finish;
  119.           }
  120.           rc = sqlite3BtreeKey(pCur, 0, nCellKey, (void *)pCellKey);
  121.           c = sqlite3VdbeRecordCompare(nCellKey, pCellKey, pUnKey);
  122.           sqlite3_free(pCellKey);
  123.           if( rc ) goto moveto_finish;
  124.         }
  125.       }
  126.       if( c==0 ){
  127.         pCur->info.nKey = nCellKey;
  128.         if( pPage->leafData && !pPage->leaf ){
  129.           lwr = pCur->idx;
  130.           upr = lwr - 1;
  131.           break;
  132.         }else{
  133.           if( pRes ) *pRes = 0;
  134.           rc = SQLITE_OK;
  135.           goto moveto_finish;
  136.         }
  137.       }
  138.       if( c<0 ){
  139.         lwr = pCur->idx+1;
  140.       }else{
  141.         upr = pCur->idx-1;
  142.       }
  143.       if( lwr>upr ){
  144.         pCur->info.nKey = nCellKey;
  145.         break;
  146.       }
  147.       pCur->idx = (lwr+upr)/2;
  148.     }
  149.     assert( lwr==upr+1 );
  150.     assert( pPage->isInit );
  151.     if( pPage->leaf ){
  152.       chldPg = 0;
  153.     }else if( lwr>=pPage->nCell ){
  154.       chldPg = get4byte(&pPage->aData[pPage->hdrOffset+8]);
  155.     }else{
  156.       chldPg = get4byte(findCell(pPage, lwr));
  157.     }
  158.     if( chldPg==0 ){
  159.       assert( pCur->idx>=0 && pCur->idx<pCur->pPage->nCell );
  160.       if( pRes ) *pRes = c;
  161.       rc = SQLITE_OK;
  162.       goto moveto_finish;
  163.     }
  164.     pCur->idx = lwr;
  165.     pCur->info.nSize = 0;
  166.     pCur->validNKey = 0;
  167.     rc = moveToChild(pCur, chldPg);
  168.     if( rc ) goto moveto_finish;
  169.   }
  170. moveto_finish:
  171.   if( pKey ){
  172.     /* If we created our own unpacked key at the top of this
  173.     ** procedure, then destroy that key before returning. */
  174.     sqlite3VdbeDeleteUnpackedRecord(pUnKey);
  175.   }
  176.   return rc;
  177. }
  178. /*
  179. ** Return TRUE if the cursor is not pointing at an entry of the table.
  180. **
  181. ** TRUE will be returned after a call to sqlite3BtreeNext() moves
  182. ** past the last entry in the table or sqlite3BtreePrev() moves past
  183. ** the first entry.  TRUE is also returned if the table is empty.
  184. */
  185. int sqlite3BtreeEof(BtCursor *pCur){
  186.   /* TODO: What if the cursor is in CURSOR_REQUIRESEEK but all table entries
  187.   ** have been deleted? This API will need to change to return an error code
  188.   ** as well as the boolean result value.
  189.   */
  190.   return (CURSOR_VALID!=pCur->eState);
  191. }
  192. /*
  193. ** Return the database connection handle for a cursor.
  194. */
  195. sqlite3 *sqlite3BtreeCursorDb(const BtCursor *pCur){
  196.   assert( sqlite3_mutex_held(pCur->pBtree->db->mutex) );
  197.   return pCur->pBtree->db;
  198. }
  199. /*
  200. ** Advance the cursor to the next entry in the database.  If
  201. ** successful then set *pRes=0.  If the cursor
  202. ** was already pointing to the last entry in the database before
  203. ** this routine was called, then set *pRes=1.
  204. */
  205. int sqlite3BtreeNext(BtCursor *pCur, int *pRes){
  206.   int rc;
  207.   MemPage *pPage;
  208.   assert( cursorHoldsMutex(pCur) );
  209.   rc = restoreOrClearCursorPosition(pCur);
  210.   if( rc!=SQLITE_OK ){
  211.     return rc;
  212.   }
  213.   assert( pRes!=0 );
  214.   pPage = pCur->pPage;
  215.   if( CURSOR_INVALID==pCur->eState ){
  216.     *pRes = 1;
  217.     return SQLITE_OK;
  218.   }
  219.   if( pCur->skip>0 ){
  220.     pCur->skip = 0;
  221.     *pRes = 0;
  222.     return SQLITE_OK;
  223.   }
  224.   pCur->skip = 0;
  225.   assert( pPage->isInit );
  226.   assert( pCur->idx<pPage->nCell );
  227.   pCur->idx++;
  228.   pCur->info.nSize = 0;
  229.   pCur->validNKey = 0;
  230.   if( pCur->idx>=pPage->nCell ){
  231.     if( !pPage->leaf ){
  232.       rc = moveToChild(pCur, get4byte(&pPage->aData[pPage->hdrOffset+8]));
  233.       if( rc ) return rc;
  234.       rc = moveToLeftmost(pCur);
  235.       *pRes = 0;
  236.       return rc;
  237.     }
  238.     do{
  239.       if( sqlite3BtreeIsRootPage(pPage) ){
  240.         *pRes = 1;
  241.         pCur->eState = CURSOR_INVALID;
  242.         return SQLITE_OK;
  243.       }
  244.       sqlite3BtreeMoveToParent(pCur);
  245.       pPage = pCur->pPage;
  246.     }while( pCur->idx>=pPage->nCell );
  247.     *pRes = 0;
  248.     if( pPage->leafData ){
  249.       rc = sqlite3BtreeNext(pCur, pRes);
  250.     }else{
  251.       rc = SQLITE_OK;
  252.     }
  253.     return rc;
  254.   }
  255.   *pRes = 0;
  256.   if( pPage->leaf ){
  257.     return SQLITE_OK;
  258.   }
  259.   rc = moveToLeftmost(pCur);
  260.   return rc;
  261. }
  262. /*
  263. ** Step the cursor to the back to the previous entry in the database.  If
  264. ** successful then set *pRes=0.  If the cursor
  265. ** was already pointing to the first entry in the database before
  266. ** this routine was called, then set *pRes=1.
  267. */
  268. int sqlite3BtreePrevious(BtCursor *pCur, int *pRes){
  269.   int rc;
  270.   Pgno pgno;
  271.   MemPage *pPage;
  272.   assert( cursorHoldsMutex(pCur) );
  273.   rc = restoreOrClearCursorPosition(pCur);
  274.   if( rc!=SQLITE_OK ){
  275.     return rc;
  276.   }
  277.   pCur->atLast = 0;
  278.   if( CURSOR_INVALID==pCur->eState ){
  279.     *pRes = 1;
  280.     return SQLITE_OK;
  281.   }
  282.   if( pCur->skip<0 ){
  283.     pCur->skip = 0;
  284.     *pRes = 0;
  285.     return SQLITE_OK;
  286.   }
  287.   pCur->skip = 0;
  288.   pPage = pCur->pPage;
  289.   assert( pPage->isInit );
  290.   assert( pCur->idx>=0 );
  291.   if( !pPage->leaf ){
  292.     pgno = get4byte( findCell(pPage, pCur->idx) );
  293.     rc = moveToChild(pCur, pgno);
  294.     if( rc ){
  295.       return rc;
  296.     }
  297.     rc = moveToRightmost(pCur);
  298.   }else{
  299.     while( pCur->idx==0 ){
  300.       if( sqlite3BtreeIsRootPage(pPage) ){
  301.         pCur->eState = CURSOR_INVALID;
  302.         *pRes = 1;
  303.         return SQLITE_OK;
  304.       }
  305.       sqlite3BtreeMoveToParent(pCur);
  306.       pPage = pCur->pPage;
  307.     }
  308.     pCur->idx--;
  309.     pCur->info.nSize = 0;
  310.     pCur->validNKey = 0;
  311.     if( pPage->leafData && !pPage->leaf ){
  312.       rc = sqlite3BtreePrevious(pCur, pRes);
  313.     }else{
  314.       rc = SQLITE_OK;
  315.     }
  316.   }
  317.   *pRes = 0;
  318.   return rc;
  319. }
  320. /*
  321. ** Allocate a new page from the database file.
  322. **
  323. ** The new page is marked as dirty.  (In other words, sqlite3PagerWrite()
  324. ** has already been called on the new page.)  The new page has also
  325. ** been referenced and the calling routine is responsible for calling
  326. ** sqlite3PagerUnref() on the new page when it is done.
  327. **
  328. ** SQLITE_OK is returned on success.  Any other return value indicates
  329. ** an error.  *ppPage and *pPgno are undefined in the event of an error.
  330. ** Do not invoke sqlite3PagerUnref() on *ppPage if an error is returned.
  331. **
  332. ** If the "nearby" parameter is not 0, then a (feeble) effort is made to 
  333. ** locate a page close to the page number "nearby".  This can be used in an
  334. ** attempt to keep related pages close to each other in the database file,
  335. ** which in turn can make database access faster.
  336. **
  337. ** If the "exact" parameter is not 0, and the page-number nearby exists 
  338. ** anywhere on the free-list, then it is guarenteed to be returned. This
  339. ** is only used by auto-vacuum databases when allocating a new table.
  340. */
  341. static int allocateBtreePage(
  342.   BtShared *pBt, 
  343.   MemPage **ppPage, 
  344.   Pgno *pPgno, 
  345.   Pgno nearby,
  346.   u8 exact
  347. ){
  348.   MemPage *pPage1;
  349.   int rc;
  350.   int n;     /* Number of pages on the freelist */
  351.   int k;     /* Number of leaves on the trunk of the freelist */
  352.   MemPage *pTrunk = 0;
  353.   MemPage *pPrevTrunk = 0;
  354.   assert( sqlite3_mutex_held(pBt->mutex) );
  355.   pPage1 = pBt->pPage1;
  356.   n = get4byte(&pPage1->aData[36]);
  357.   if( n>0 ){
  358.     /* There are pages on the freelist.  Reuse one of those pages. */
  359.     Pgno iTrunk;
  360.     u8 searchList = 0; /* If the free-list must be searched for 'nearby' */
  361.     
  362.     /* If the 'exact' parameter was true and a query of the pointer-map
  363.     ** shows that the page 'nearby' is somewhere on the free-list, then
  364.     ** the entire-list will be searched for that page.
  365.     */
  366. #ifndef SQLITE_OMIT_AUTOVACUUM
  367.     if( exact && nearby<=sqlite3PagerPagecount(pBt->pPager) ){
  368.       u8 eType;
  369.       assert( nearby>0 );
  370.       assert( pBt->autoVacuum );
  371.       rc = ptrmapGet(pBt, nearby, &eType, 0);
  372.       if( rc ) return rc;
  373.       if( eType==PTRMAP_FREEPAGE ){
  374.         searchList = 1;
  375.       }
  376.       *pPgno = nearby;
  377.     }
  378. #endif
  379.     /* Decrement the free-list count by 1. Set iTrunk to the index of the
  380.     ** first free-list trunk page. iPrevTrunk is initially 1.
  381.     */
  382.     rc = sqlite3PagerWrite(pPage1->pDbPage);
  383.     if( rc ) return rc;
  384.     put4byte(&pPage1->aData[36], n-1);
  385.     /* The code within this loop is run only once if the 'searchList' variable
  386.     ** is not true. Otherwise, it runs once for each trunk-page on the
  387.     ** free-list until the page 'nearby' is located.
  388.     */
  389.     do {
  390.       pPrevTrunk = pTrunk;
  391.       if( pPrevTrunk ){
  392.         iTrunk = get4byte(&pPrevTrunk->aData[0]);
  393.       }else{
  394.         iTrunk = get4byte(&pPage1->aData[32]);
  395.       }
  396.       rc = sqlite3BtreeGetPage(pBt, iTrunk, &pTrunk, 0);
  397.       if( rc ){
  398.         pTrunk = 0;
  399.         goto end_allocate_page;
  400.       }
  401.       k = get4byte(&pTrunk->aData[4]);
  402.       if( k==0 && !searchList ){
  403.         /* The trunk has no leaves and the list is not being searched. 
  404.         ** So extract the trunk page itself and use it as the newly 
  405.         ** allocated page */
  406.         assert( pPrevTrunk==0 );
  407.         rc = sqlite3PagerWrite(pTrunk->pDbPage);
  408.         if( rc ){
  409.           goto end_allocate_page;
  410.         }
  411.         *pPgno = iTrunk;
  412.         memcpy(&pPage1->aData[32], &pTrunk->aData[0], 4);
  413.         *ppPage = pTrunk;
  414.         pTrunk = 0;
  415.         TRACE(("ALLOCATE: %d trunk - %d free pages leftn", *pPgno, n-1));
  416.       }else if( k>pBt->usableSize/4 - 8 ){
  417.         /* Value of k is out of range.  Database corruption */
  418.         rc = SQLITE_CORRUPT_BKPT;
  419.         goto end_allocate_page;
  420. #ifndef SQLITE_OMIT_AUTOVACUUM
  421.       }else if( searchList && nearby==iTrunk ){
  422.         /* The list is being searched and this trunk page is the page
  423.         ** to allocate, regardless of whether it has leaves.
  424.         */
  425.         assert( *pPgno==iTrunk );
  426.         *ppPage = pTrunk;
  427.         searchList = 0;
  428.         rc = sqlite3PagerWrite(pTrunk->pDbPage);
  429.         if( rc ){
  430.           goto end_allocate_page;
  431.         }
  432.         if( k==0 ){
  433.           if( !pPrevTrunk ){
  434.             memcpy(&pPage1->aData[32], &pTrunk->aData[0], 4);
  435.           }else{
  436.             memcpy(&pPrevTrunk->aData[0], &pTrunk->aData[0], 4);
  437.           }
  438.         }else{
  439.           /* The trunk page is required by the caller but it contains 
  440.           ** pointers to free-list leaves. The first leaf becomes a trunk
  441.           ** page in this case.
  442.           */
  443.           MemPage *pNewTrunk;
  444.           Pgno iNewTrunk = get4byte(&pTrunk->aData[8]);
  445.           rc = sqlite3BtreeGetPage(pBt, iNewTrunk, &pNewTrunk, 0);
  446.           if( rc!=SQLITE_OK ){
  447.             goto end_allocate_page;
  448.           }
  449.           rc = sqlite3PagerWrite(pNewTrunk->pDbPage);
  450.           if( rc!=SQLITE_OK ){
  451.             releasePage(pNewTrunk);
  452.             goto end_allocate_page;
  453.           }
  454.           memcpy(&pNewTrunk->aData[0], &pTrunk->aData[0], 4);
  455.           put4byte(&pNewTrunk->aData[4], k-1);
  456.           memcpy(&pNewTrunk->aData[8], &pTrunk->aData[12], (k-1)*4);
  457.           releasePage(pNewTrunk);
  458.           if( !pPrevTrunk ){
  459.             put4byte(&pPage1->aData[32], iNewTrunk);
  460.           }else{
  461.             rc = sqlite3PagerWrite(pPrevTrunk->pDbPage);
  462.             if( rc ){
  463.               goto end_allocate_page;
  464.             }
  465.             put4byte(&pPrevTrunk->aData[0], iNewTrunk);
  466.           }
  467.         }
  468.         pTrunk = 0;
  469.         TRACE(("ALLOCATE: %d trunk - %d free pages leftn", *pPgno, n-1));
  470. #endif
  471.       }else{
  472.         /* Extract a leaf from the trunk */
  473.         int closest;
  474.         Pgno iPage;
  475.         unsigned char *aData = pTrunk->aData;
  476.         rc = sqlite3PagerWrite(pTrunk->pDbPage);
  477.         if( rc ){
  478.           goto end_allocate_page;
  479.         }
  480.         if( nearby>0 ){
  481.           int i, dist;
  482.           closest = 0;
  483.           dist = get4byte(&aData[8]) - nearby;
  484.           if( dist<0 ) dist = -dist;
  485.           for(i=1; i<k; i++){
  486.             int d2 = get4byte(&aData[8+i*4]) - nearby;
  487.             if( d2<0 ) d2 = -d2;
  488.             if( d2<dist ){
  489.               closest = i;
  490.               dist = d2;
  491.             }
  492.           }
  493.         }else{
  494.           closest = 0;
  495.         }
  496.         iPage = get4byte(&aData[8+closest*4]);
  497.         if( !searchList || iPage==nearby ){
  498.           *pPgno = iPage;
  499.           if( *pPgno>sqlite3PagerPagecount(pBt->pPager) ){
  500.             /* Free page off the end of the file */
  501.             return SQLITE_CORRUPT_BKPT;
  502.           }
  503.           TRACE(("ALLOCATE: %d was leaf %d of %d on trunk %d"
  504.                  ": %d more free pagesn",
  505.                  *pPgno, closest+1, k, pTrunk->pgno, n-1));
  506.           if( closest<k-1 ){
  507.             memcpy(&aData[8+closest*4], &aData[4+k*4], 4);
  508.           }
  509.           put4byte(&aData[4], k-1);
  510.           rc = sqlite3BtreeGetPage(pBt, *pPgno, ppPage, 1);
  511.           if( rc==SQLITE_OK ){
  512.             sqlite3PagerDontRollback((*ppPage)->pDbPage);
  513.             rc = sqlite3PagerWrite((*ppPage)->pDbPage);
  514.             if( rc!=SQLITE_OK ){
  515.               releasePage(*ppPage);
  516.             }
  517.           }
  518.           searchList = 0;
  519.         }
  520.       }
  521.       releasePage(pPrevTrunk);
  522.       pPrevTrunk = 0;
  523.     }while( searchList );
  524.   }else{
  525.     /* There are no pages on the freelist, so create a new page at the
  526.     ** end of the file */
  527.     *pPgno = sqlite3PagerPagecount(pBt->pPager) + 1;
  528. #ifndef SQLITE_OMIT_AUTOVACUUM
  529.     if( pBt->nTrunc ){
  530.       /* An incr-vacuum has already run within this transaction. So the
  531.       ** page to allocate is not from the physical end of the file, but
  532.       ** at pBt->nTrunc. 
  533.       */
  534.       *pPgno = pBt->nTrunc+1;
  535.       if( *pPgno==PENDING_BYTE_PAGE(pBt) ){
  536.         (*pPgno)++;
  537.       }
  538.     }
  539.     if( pBt->autoVacuum && PTRMAP_ISPAGE(pBt, *pPgno) ){
  540.       /* If *pPgno refers to a pointer-map page, allocate two new pages
  541.       ** at the end of the file instead of one. The first allocated page
  542.       ** becomes a new pointer-map page, the second is used by the caller.
  543.       */
  544.       TRACE(("ALLOCATE: %d from end of file (pointer-map page)n", *pPgno));
  545.       assert( *pPgno!=PENDING_BYTE_PAGE(pBt) );
  546.       (*pPgno)++;
  547.       if( *pPgno==PENDING_BYTE_PAGE(pBt) ){ (*pPgno)++; }
  548.     }
  549.     if( pBt->nTrunc ){
  550.       pBt->nTrunc = *pPgno;
  551.     }
  552. #endif
  553.     assert( *pPgno!=PENDING_BYTE_PAGE(pBt) );
  554.     rc = sqlite3BtreeGetPage(pBt, *pPgno, ppPage, 0);
  555.     if( rc ) return rc;
  556.     rc = sqlite3PagerWrite((*ppPage)->pDbPage);
  557.     if( rc!=SQLITE_OK ){
  558.       releasePage(*ppPage);
  559.     }
  560.     TRACE(("ALLOCATE: %d from end of filen", *pPgno));
  561.   }
  562.   assert( *pPgno!=PENDING_BYTE_PAGE(pBt) );
  563. end_allocate_page:
  564.   releasePage(pTrunk);
  565.   releasePage(pPrevTrunk);
  566.   return rc;
  567. }
  568. /*
  569. ** Add a page of the database file to the freelist.
  570. **
  571. ** sqlite3PagerUnref() is NOT called for pPage.
  572. */
  573. static int freePage(MemPage *pPage){
  574.   BtShared *pBt = pPage->pBt;
  575.   MemPage *pPage1 = pBt->pPage1;
  576.   int rc, n, k;
  577.   /* Prepare the page for freeing */
  578.   assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  579.   assert( pPage->pgno>1 );
  580.   pPage->isInit = 0;
  581.   releasePage(pPage->pParent);
  582.   pPage->pParent = 0;
  583.   /* Increment the free page count on pPage1 */
  584.   rc = sqlite3PagerWrite(pPage1->pDbPage);
  585.   if( rc ) return rc;
  586.   n = get4byte(&pPage1->aData[36]);
  587.   put4byte(&pPage1->aData[36], n+1);
  588. #ifdef SQLITE_SECURE_DELETE
  589.   /* If the SQLITE_SECURE_DELETE compile-time option is enabled, then
  590.   ** always fully overwrite deleted information with zeros.
  591.   */
  592.   rc = sqlite3PagerWrite(pPage->pDbPage);
  593.   if( rc ) return rc;
  594.   memset(pPage->aData, 0, pPage->pBt->pageSize);
  595. #endif
  596. #ifndef SQLITE_OMIT_AUTOVACUUM
  597.   /* If the database supports auto-vacuum, write an entry in the pointer-map
  598.   ** to indicate that the page is free.
  599.   */
  600.   if( pBt->autoVacuum ){
  601.     rc = ptrmapPut(pBt, pPage->pgno, PTRMAP_FREEPAGE, 0);
  602.     if( rc ) return rc;
  603.   }
  604. #endif
  605.   if( n==0 ){
  606.     /* This is the first free page */
  607.     rc = sqlite3PagerWrite(pPage->pDbPage);
  608.     if( rc ) return rc;
  609.     memset(pPage->aData, 0, 8);
  610.     put4byte(&pPage1->aData[32], pPage->pgno);
  611.     TRACE(("FREE-PAGE: %d firstn", pPage->pgno));
  612.   }else{
  613.     /* Other free pages already exist.  Retrive the first trunk page
  614.     ** of the freelist and find out how many leaves it has. */
  615.     MemPage *pTrunk;
  616.     rc = sqlite3BtreeGetPage(pBt, get4byte(&pPage1->aData[32]), &pTrunk, 0);
  617.     if( rc ) return rc;
  618.     k = get4byte(&pTrunk->aData[4]);
  619.     if( k>=pBt->usableSize/4 - 8 ){
  620.       /* The trunk is full.  Turn the page being freed into a new
  621.       ** trunk page with no leaves. */
  622.       rc = sqlite3PagerWrite(pPage->pDbPage);
  623.       if( rc==SQLITE_OK ){
  624.         put4byte(pPage->aData, pTrunk->pgno);
  625.         put4byte(&pPage->aData[4], 0);
  626.         put4byte(&pPage1->aData[32], pPage->pgno);
  627.         TRACE(("FREE-PAGE: %d new trunk page replacing %dn",
  628.                 pPage->pgno, pTrunk->pgno));
  629.       }
  630.     }else if( k<0 ){
  631.       rc = SQLITE_CORRUPT;
  632.     }else{
  633.       /* Add the newly freed page as a leaf on the current trunk */
  634.       rc = sqlite3PagerWrite(pTrunk->pDbPage);
  635.       if( rc==SQLITE_OK ){
  636.         put4byte(&pTrunk->aData[4], k+1);
  637.         put4byte(&pTrunk->aData[8+k*4], pPage->pgno);
  638. #ifndef SQLITE_SECURE_DELETE
  639.         sqlite3PagerDontWrite(pPage->pDbPage);
  640. #endif
  641.       }
  642.       TRACE(("FREE-PAGE: %d leaf on trunk page %dn",pPage->pgno,pTrunk->pgno));
  643.     }
  644.     releasePage(pTrunk);
  645.   }
  646.   return rc;
  647. }
  648. /*
  649. ** Free any overflow pages associated with the given Cell.
  650. */
  651. static int clearCell(MemPage *pPage, unsigned char *pCell){
  652.   BtShared *pBt = pPage->pBt;
  653.   CellInfo info;
  654.   Pgno ovflPgno;
  655.   int rc;
  656.   int nOvfl;
  657.   int ovflPageSize;
  658.   assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  659.   sqlite3BtreeParseCellPtr(pPage, pCell, &info);
  660.   if( info.iOverflow==0 ){
  661.     return SQLITE_OK;  /* No overflow pages. Return without doing anything */
  662.   }
  663.   ovflPgno = get4byte(&pCell[info.iOverflow]);
  664.   ovflPageSize = pBt->usableSize - 4;
  665.   nOvfl = (info.nPayload - info.nLocal + ovflPageSize - 1)/ovflPageSize;
  666.   assert( ovflPgno==0 || nOvfl>0 );
  667.   while( nOvfl-- ){
  668.     MemPage *pOvfl;
  669.     if( ovflPgno==0 || ovflPgno>sqlite3PagerPagecount(pBt->pPager) ){
  670.       return SQLITE_CORRUPT_BKPT;
  671.     }
  672.     rc = getOverflowPage(pBt, ovflPgno, &pOvfl, (nOvfl==0)?0:&ovflPgno);
  673.     if( rc ) return rc;
  674.     rc = freePage(pOvfl);
  675.     sqlite3PagerUnref(pOvfl->pDbPage);
  676.     if( rc ) return rc;
  677.   }
  678.   return SQLITE_OK;
  679. }
  680. /*
  681. ** Create the byte sequence used to represent a cell on page pPage
  682. ** and write that byte sequence into pCell[].  Overflow pages are
  683. ** allocated and filled in as necessary.  The calling procedure
  684. ** is responsible for making sure sufficient space has been allocated
  685. ** for pCell[].
  686. **
  687. ** Note that pCell does not necessary need to point to the pPage->aData
  688. ** area.  pCell might point to some temporary storage.  The cell will
  689. ** be constructed in this temporary area then copied into pPage->aData
  690. ** later.
  691. */
  692. static int fillInCell(
  693.   MemPage *pPage,                /* The page that contains the cell */
  694.   unsigned char *pCell,          /* Complete text of the cell */
  695.   const void *pKey, i64 nKey,    /* The key */
  696.   const void *pData,int nData,   /* The data */
  697.   int nZero,                     /* Extra zero bytes to append to pData */
  698.   int *pnSize                    /* Write cell size here */
  699. ){
  700.   int nPayload;
  701.   const u8 *pSrc;
  702.   int nSrc, n, rc;
  703.   int spaceLeft;
  704.   MemPage *pOvfl = 0;
  705.   MemPage *pToRelease = 0;
  706.   unsigned char *pPrior;
  707.   unsigned char *pPayload;
  708.   BtShared *pBt = pPage->pBt;
  709.   Pgno pgnoOvfl = 0;
  710.   int nHeader;
  711.   CellInfo info;
  712.   assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  713.   /* Fill in the header. */
  714.   nHeader = 0;
  715.   if( !pPage->leaf ){
  716.     nHeader += 4;
  717.   }
  718.   if( pPage->hasData ){
  719.     nHeader += putVarint(&pCell[nHeader], nData+nZero);
  720.   }else{
  721.     nData = nZero = 0;
  722.   }
  723.   nHeader += putVarint(&pCell[nHeader], *(u64*)&nKey);
  724.   sqlite3BtreeParseCellPtr(pPage, pCell, &info);
  725.   assert( info.nHeader==nHeader );
  726.   assert( info.nKey==nKey );
  727.   assert( info.nData==nData+nZero );
  728.   
  729.   /* Fill in the payload */
  730.   nPayload = nData + nZero;
  731.   if( pPage->intKey ){
  732.     pSrc = pData;
  733.     nSrc = nData;
  734.     nData = 0;
  735.   }else{
  736.     nPayload += nKey;
  737.     pSrc = pKey;
  738.     nSrc = nKey;
  739.   }
  740.   *pnSize = info.nSize;
  741.   spaceLeft = info.nLocal;
  742.   pPayload = &pCell[nHeader];
  743.   pPrior = &pCell[info.iOverflow];
  744.   while( nPayload>0 ){
  745.     if( spaceLeft==0 ){
  746.       int isExact = 0;
  747. #ifndef SQLITE_OMIT_AUTOVACUUM
  748.       Pgno pgnoPtrmap = pgnoOvfl; /* Overflow page pointer-map entry page */
  749.       if( pBt->autoVacuum ){
  750.         do{
  751.           pgnoOvfl++;
  752.         } while( 
  753.           PTRMAP_ISPAGE(pBt, pgnoOvfl) || pgnoOvfl==PENDING_BYTE_PAGE(pBt) 
  754.         );
  755.         if( pgnoOvfl>1 ){
  756.           /* isExact = 1; */
  757.         }
  758.       }
  759. #endif
  760.       rc = allocateBtreePage(pBt, &pOvfl, &pgnoOvfl, pgnoOvfl, isExact);
  761. #ifndef SQLITE_OMIT_AUTOVACUUM
  762.       /* If the database supports auto-vacuum, and the second or subsequent
  763.       ** overflow page is being allocated, add an entry to the pointer-map
  764.       ** for that page now. 
  765.       **
  766.       ** If this is the first overflow page, then write a partial entry 
  767.       ** to the pointer-map. If we write nothing to this pointer-map slot,
  768.       ** then the optimistic overflow chain processing in clearCell()
  769.       ** may misinterpret the uninitialised values and delete the
  770.       ** wrong pages from the database.
  771.       */
  772.       if( pBt->autoVacuum && rc==SQLITE_OK ){
  773.         u8 eType = (pgnoPtrmap?PTRMAP_OVERFLOW2:PTRMAP_OVERFLOW1);
  774.         rc = ptrmapPut(pBt, pgnoOvfl, eType, pgnoPtrmap);
  775.         if( rc ){
  776.           releasePage(pOvfl);
  777.         }
  778.       }
  779. #endif
  780.       if( rc ){
  781.         releasePage(pToRelease);
  782.         return rc;
  783.       }
  784.       put4byte(pPrior, pgnoOvfl);
  785.       releasePage(pToRelease);
  786.       pToRelease = pOvfl;
  787.       pPrior = pOvfl->aData;
  788.       put4byte(pPrior, 0);
  789.       pPayload = &pOvfl->aData[4];
  790.       spaceLeft = pBt->usableSize - 4;
  791.     }
  792.     n = nPayload;
  793.     if( n>spaceLeft ) n = spaceLeft;
  794.     if( nSrc>0 ){
  795.       if( n>nSrc ) n = nSrc;
  796.       assert( pSrc );
  797.       memcpy(pPayload, pSrc, n);
  798.     }else{
  799.       memset(pPayload, 0, n);
  800.     }
  801.     nPayload -= n;
  802.     pPayload += n;
  803.     pSrc += n;
  804.     nSrc -= n;
  805.     spaceLeft -= n;
  806.     if( nSrc==0 ){
  807.       nSrc = nData;
  808.       pSrc = pData;
  809.     }
  810.   }
  811.   releasePage(pToRelease);
  812.   return SQLITE_OK;
  813. }
  814. /*
  815. ** Change the MemPage.pParent pointer on the page whose number is
  816. ** given in the second argument so that MemPage.pParent holds the
  817. ** pointer in the third argument.
  818. */
  819. static int reparentPage(BtShared *pBt, Pgno pgno, MemPage *pNewParent, int idx){
  820.   MemPage *pThis;
  821.   DbPage *pDbPage;
  822.   assert( sqlite3_mutex_held(pBt->mutex) );
  823.   assert( pNewParent!=0 );
  824.   if( pgno==0 ) return SQLITE_OK;
  825.   assert( pBt->pPager!=0 );
  826.   pDbPage = sqlite3PagerLookup(pBt->pPager, pgno);
  827.   if( pDbPage ){
  828.     pThis = (MemPage *)sqlite3PagerGetExtra(pDbPage);
  829.     if( pThis->isInit ){
  830.       assert( pThis->aData==sqlite3PagerGetData(pDbPage) );
  831.       if( pThis->pParent!=pNewParent ){
  832.         if( pThis->pParent ) sqlite3PagerUnref(pThis->pParent->pDbPage);
  833.         pThis->pParent = pNewParent;
  834.         sqlite3PagerRef(pNewParent->pDbPage);
  835.       }
  836.       pThis->idxParent = idx;
  837.     }
  838.     sqlite3PagerUnref(pDbPage);
  839.   }
  840. #ifndef SQLITE_OMIT_AUTOVACUUM
  841.   if( pBt->autoVacuum ){
  842.     return ptrmapPut(pBt, pgno, PTRMAP_BTREE, pNewParent->pgno);
  843.   }
  844. #endif
  845.   return SQLITE_OK;
  846. }
  847. /*
  848. ** Change the pParent pointer of all children of pPage to point back
  849. ** to pPage.
  850. **
  851. ** In other words, for every child of pPage, invoke reparentPage()
  852. ** to make sure that each child knows that pPage is its parent.
  853. **
  854. ** This routine gets called after you memcpy() one page into
  855. ** another.
  856. */
  857. static int reparentChildPages(MemPage *pPage){
  858.   int i;
  859.   BtShared *pBt = pPage->pBt;
  860.   int rc = SQLITE_OK;
  861.   assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  862.   if( pPage->leaf ) return SQLITE_OK;
  863.   for(i=0; i<pPage->nCell; i++){
  864.     u8 *pCell = findCell(pPage, i);
  865.     rc = reparentPage(pBt, get4byte(pCell), pPage, i);
  866.     if( rc!=SQLITE_OK ) return rc;
  867.   }
  868.   rc = reparentPage(pBt, get4byte(&pPage->aData[pPage->hdrOffset+8]), 
  869.                     pPage, i);
  870.   pPage->idxShift = 0;
  871.   return rc;
  872. }
  873. /*
  874. ** Remove the i-th cell from pPage.  This routine effects pPage only.
  875. ** The cell content is not freed or deallocated.  It is assumed that
  876. ** the cell content has been copied someplace else.  This routine just
  877. ** removes the reference to the cell from pPage.
  878. **
  879. ** "sz" must be the number of bytes in the cell.
  880. */
  881. static void dropCell(MemPage *pPage, int idx, int sz){
  882.   int i;          /* Loop counter */
  883.   int pc;         /* Offset to cell content of cell being deleted */
  884.   u8 *data;       /* pPage->aData */
  885.   u8 *ptr;        /* Used to move bytes around within data[] */
  886.   assert( idx>=0 && idx<pPage->nCell );
  887.   assert( sz==cellSize(pPage, idx) );
  888.   assert( sqlite3PagerIswriteable(pPage->pDbPage) );
  889.   assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  890.   data = pPage->aData;
  891.   ptr = &data[pPage->cellOffset + 2*idx];
  892.   pc = get2byte(ptr);
  893.   assert( pc>10 && pc+sz<=pPage->pBt->usableSize );
  894.   freeSpace(pPage, pc, sz);
  895.   for(i=idx+1; i<pPage->nCell; i++, ptr+=2){
  896.     ptr[0] = ptr[2];
  897.     ptr[1] = ptr[3];
  898.   }
  899.   pPage->nCell--;
  900.   put2byte(&data[pPage->hdrOffset+3], pPage->nCell);
  901.   pPage->nFree += 2;
  902.   pPage->idxShift = 1;
  903. }
  904. /*
  905. ** Insert a new cell on pPage at cell index "i".  pCell points to the
  906. ** content of the cell.
  907. **
  908. ** If the cell content will fit on the page, then put it there.  If it
  909. ** will not fit, then make a copy of the cell content into pTemp if
  910. ** pTemp is not null.  Regardless of pTemp, allocate a new entry
  911. ** in pPage->aOvfl[] and make it point to the cell content (either
  912. ** in pTemp or the original pCell) and also record its index. 
  913. ** Allocating a new entry in pPage->aCell[] implies that 
  914. ** pPage->nOverflow is incremented.
  915. **
  916. ** If nSkip is non-zero, then do not copy the first nSkip bytes of the
  917. ** cell. The caller will overwrite them after this function returns. If
  918. ** nSkip is non-zero, then pCell may not point to an invalid memory location 
  919. ** (but pCell+nSkip is always valid).
  920. */
  921. static int insertCell(
  922.   MemPage *pPage,   /* Page into which we are copying */
  923.   int i,            /* New cell becomes the i-th cell of the page */
  924.   u8 *pCell,        /* Content of the new cell */
  925.   int sz,           /* Bytes of content in pCell */
  926.   u8 *pTemp,        /* Temp storage space for pCell, if needed */
  927.   u8 nSkip          /* Do not write the first nSkip bytes of the cell */
  928. ){
  929.   int idx;          /* Where to write new cell content in data[] */
  930.   int j;            /* Loop counter */
  931.   int top;          /* First byte of content for any cell in data[] */
  932.   int end;          /* First byte past the last cell pointer in data[] */
  933.   int ins;          /* Index in data[] where new cell pointer is inserted */
  934.   int hdr;          /* Offset into data[] of the page header */
  935.   int cellOffset;   /* Address of first cell pointer in data[] */
  936.   u8 *data;         /* The content of the whole page */
  937.   u8 *ptr;          /* Used for moving information around in data[] */
  938.   assert( i>=0 && i<=pPage->nCell+pPage->nOverflow );
  939.   assert( sz==cellSizePtr(pPage, pCell) );
  940.   assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  941.   if( pPage->nOverflow || sz+2>pPage->nFree ){
  942.     if( pTemp ){
  943.       memcpy(pTemp+nSkip, pCell+nSkip, sz-nSkip);
  944.       pCell = pTemp;
  945.     }
  946.     j = pPage->nOverflow++;
  947.     assert( j<sizeof(pPage->aOvfl)/sizeof(pPage->aOvfl[0]) );
  948.     pPage->aOvfl[j].pCell = pCell;
  949.     pPage->aOvfl[j].idx = i;
  950.     pPage->nFree = 0;
  951.   }else{
  952.     int rc = sqlite3PagerWrite(pPage->pDbPage);
  953.     if( rc!=SQLITE_OK ){
  954.       return rc;
  955.     }
  956.     assert( sqlite3PagerIswriteable(pPage->pDbPage) );
  957.     data = pPage->aData;
  958.     hdr = pPage->hdrOffset;
  959.     top = get2byte(&data[hdr+5]);
  960.     cellOffset = pPage->cellOffset;
  961.     end = cellOffset + 2*pPage->nCell + 2;
  962.     ins = cellOffset + 2*i;
  963.     if( end > top - sz ){
  964.       rc = defragmentPage(pPage);
  965.       if( rc!=SQLITE_OK ) return rc;
  966.       top = get2byte(&data[hdr+5]);
  967.       assert( end + sz <= top );
  968.     }
  969.     idx = allocateSpace(pPage, sz);
  970.     assert( idx>0 );
  971.     assert( end <= get2byte(&data[hdr+5]) );
  972.     pPage->nCell++;
  973.     pPage->nFree -= 2;
  974.     memcpy(&data[idx+nSkip], pCell+nSkip, sz-nSkip);
  975.     for(j=end-2, ptr=&data[j]; j>ins; j-=2, ptr-=2){
  976.       ptr[0] = ptr[-2];
  977.       ptr[1] = ptr[-1];
  978.     }
  979.     put2byte(&data[ins], idx);
  980.     put2byte(&data[hdr+3], pPage->nCell);
  981.     pPage->idxShift = 1;
  982. #ifndef SQLITE_OMIT_AUTOVACUUM
  983.     if( pPage->pBt->autoVacuum ){
  984.       /* The cell may contain a pointer to an overflow page. If so, write
  985.       ** the entry for the overflow page into the pointer map.
  986.       */
  987.       CellInfo info;
  988.       sqlite3BtreeParseCellPtr(pPage, pCell, &info);
  989.       assert( (info.nData+(pPage->intKey?0:info.nKey))==info.nPayload );
  990.       if( (info.nData+(pPage->intKey?0:info.nKey))>info.nLocal ){
  991.         Pgno pgnoOvfl = get4byte(&pCell[info.iOverflow]);
  992.         rc = ptrmapPut(pPage->pBt, pgnoOvfl, PTRMAP_OVERFLOW1, pPage->pgno);
  993.         if( rc!=SQLITE_OK ) return rc;
  994.       }
  995.     }
  996. #endif
  997.   }
  998.   return SQLITE_OK;
  999. }
  1000. /*
  1001. ** Add a list of cells to a page.  The page should be initially empty.
  1002. ** The cells are guaranteed to fit on the page.
  1003. */
  1004. static void assemblePage(
  1005.   MemPage *pPage,   /* The page to be assemblied */
  1006.   int nCell,        /* The number of cells to add to this page */
  1007.   u8 **apCell,      /* Pointers to cell bodies */
  1008.   u16 *aSize        /* Sizes of the cells */
  1009. ){
  1010.   int i;            /* Loop counter */
  1011.   int totalSize;    /* Total size of all cells */
  1012.   int hdr;          /* Index of page header */
  1013.   int cellptr;      /* Address of next cell pointer */
  1014.   int cellbody;     /* Address of next cell body */
  1015.   u8 *data;         /* Data for the page */
  1016.   assert( pPage->nOverflow==0 );
  1017.   assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  1018.   totalSize = 0;
  1019.   for(i=0; i<nCell; i++){
  1020.     totalSize += aSize[i];
  1021.   }
  1022.   assert( totalSize+2*nCell<=pPage->nFree );
  1023.   assert( pPage->nCell==0 );
  1024.   cellptr = pPage->cellOffset;
  1025.   data = pPage->aData;
  1026.   hdr = pPage->hdrOffset;
  1027.   put2byte(&data[hdr+3], nCell);
  1028.   if( nCell ){
  1029.     cellbody = allocateSpace(pPage, totalSize);
  1030.     assert( cellbody>0 );
  1031.     assert( pPage->nFree >= 2*nCell );
  1032.     pPage->nFree -= 2*nCell;
  1033.     for(i=0; i<nCell; i++){
  1034.       put2byte(&data[cellptr], cellbody);
  1035.       memcpy(&data[cellbody], apCell[i], aSize[i]);
  1036.       cellptr += 2;
  1037.       cellbody += aSize[i];
  1038.     }
  1039.     assert( cellbody==pPage->pBt->usableSize );
  1040.   }
  1041.   pPage->nCell = nCell;
  1042. }
  1043. /*
  1044. ** The following parameters determine how many adjacent pages get involved
  1045. ** in a balancing operation.  NN is the number of neighbors on either side
  1046. ** of the page that participate in the balancing operation.  NB is the
  1047. ** total number of pages that participate, including the target page and
  1048. ** NN neighbors on either side.
  1049. **
  1050. ** The minimum value of NN is 1 (of course).  Increasing NN above 1
  1051. ** (to 2 or 3) gives a modest improvement in SELECT and DELETE performance
  1052. ** in exchange for a larger degradation in INSERT and UPDATE performance.
  1053. ** The value of NN appears to give the best results overall.
  1054. */
  1055. #define NN 1             /* Number of neighbors on either side of pPage */
  1056. #define NB (NN*2+1)      /* Total pages involved in the balance */
  1057. /* Forward reference */
  1058. static int balance(MemPage*, int);
  1059. #ifndef SQLITE_OMIT_QUICKBALANCE
  1060. /*
  1061. ** This version of balance() handles the common special case where
  1062. ** a new entry is being inserted on the extreme right-end of the
  1063. ** tree, in other words, when the new entry will become the largest
  1064. ** entry in the tree.
  1065. **
  1066. ** Instead of trying balance the 3 right-most leaf pages, just add
  1067. ** a new page to the right-hand side and put the one new entry in
  1068. ** that page.  This leaves the right side of the tree somewhat
  1069. ** unbalanced.  But odds are that we will be inserting new entries
  1070. ** at the end soon afterwards so the nearly empty page will quickly
  1071. ** fill up.  On average.
  1072. **
  1073. ** pPage is the leaf page which is the right-most page in the tree.
  1074. ** pParent is its parent.  pPage must have a single overflow entry
  1075. ** which is also the right-most entry on the page.
  1076. */
  1077. static int balance_quick(MemPage *pPage, MemPage *pParent){
  1078.   int rc;
  1079.   MemPage *pNew;
  1080.   Pgno pgnoNew;
  1081.   u8 *pCell;
  1082.   u16 szCell;
  1083.   CellInfo info;
  1084.   BtShared *pBt = pPage->pBt;
  1085.   int parentIdx = pParent->nCell;   /* pParent new divider cell index */
  1086.   int parentSize;                   /* Size of new divider cell */
  1087.   u8 parentCell[64];                /* Space for the new divider cell */
  1088.   assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  1089.   /* Allocate a new page. Insert the overflow cell from pPage
  1090.   ** into it. Then remove the overflow cell from pPage.
  1091.   */
  1092.   rc = allocateBtreePage(pBt, &pNew, &pgnoNew, 0, 0);
  1093.   if( rc!=SQLITE_OK ){
  1094.     return rc;
  1095.   }
  1096.   pCell = pPage->aOvfl[0].pCell;
  1097.   szCell = cellSizePtr(pPage, pCell);
  1098.   zeroPage(pNew, pPage->aData[0]);
  1099.   assemblePage(pNew, 1, &pCell, &szCell);
  1100.   pPage->nOverflow = 0;
  1101.   /* Set the parent of the newly allocated page to pParent. */
  1102.   pNew->pParent = pParent;
  1103.   sqlite3PagerRef(pParent->pDbPage);
  1104.   /* pPage is currently the right-child of pParent. Change this
  1105.   ** so that the right-child is the new page allocated above and
  1106.   ** pPage is the next-to-right child. 
  1107.   */
  1108.   assert( pPage->nCell>0 );
  1109.   pCell = findCell(pPage, pPage->nCell-1);
  1110.   sqlite3BtreeParseCellPtr(pPage, pCell, &info);
  1111.   rc = fillInCell(pParent, parentCell, 0, info.nKey, 0, 0, 0, &parentSize);
  1112.   if( rc!=SQLITE_OK ){
  1113.     return rc;
  1114.   }
  1115.   assert( parentSize<64 );
  1116.   rc = insertCell(pParent, parentIdx, parentCell, parentSize, 0, 4);
  1117.   if( rc!=SQLITE_OK ){
  1118.     return rc;
  1119.   }
  1120.   put4byte(findOverflowCell(pParent,parentIdx), pPage->pgno);
  1121.   put4byte(&pParent->aData[pParent->hdrOffset+8], pgnoNew);
  1122. #ifndef SQLITE_OMIT_AUTOVACUUM
  1123.   /* If this is an auto-vacuum database, update the pointer map
  1124.   ** with entries for the new page, and any pointer from the 
  1125.   ** cell on the page to an overflow page.
  1126.   */
  1127.   if( pBt->autoVacuum ){
  1128.     rc = ptrmapPut(pBt, pgnoNew, PTRMAP_BTREE, pParent->pgno);
  1129.     if( rc==SQLITE_OK ){
  1130.       rc = ptrmapPutOvfl(pNew, 0);
  1131.     }
  1132.     if( rc!=SQLITE_OK ){
  1133.       releasePage(pNew);
  1134.       return rc;
  1135.     }
  1136.   }
  1137. #endif
  1138.   /* Release the reference to the new page and balance the parent page,
  1139.   ** in case the divider cell inserted caused it to become overfull.
  1140.   */
  1141.   releasePage(pNew);
  1142.   return balance(pParent, 0);
  1143. }
  1144. #endif /* SQLITE_OMIT_QUICKBALANCE */
  1145. /*
  1146. ** This routine redistributes Cells on pPage and up to NN*2 siblings
  1147. ** of pPage so that all pages have about the same amount of free space.
  1148. ** Usually NN siblings on either side of pPage is used in the balancing,
  1149. ** though more siblings might come from one side if pPage is the first
  1150. ** or last child of its parent.  If pPage has fewer than 2*NN siblings
  1151. ** (something which can only happen if pPage is the root page or a 
  1152. ** child of root) then all available siblings participate in the balancing.
  1153. **
  1154. ** The number of siblings of pPage might be increased or decreased by one or
  1155. ** two in an effort to keep pages nearly full but not over full. The root page
  1156. ** is special and is allowed to be nearly empty. If pPage is 
  1157. ** the root page, then the depth of the tree might be increased
  1158. ** or decreased by one, as necessary, to keep the root page from being
  1159. ** overfull or completely empty.
  1160. **
  1161. ** Note that when this routine is called, some of the Cells on pPage
  1162. ** might not actually be stored in pPage->aData[].  This can happen
  1163. ** if the page is overfull.  Part of the job of this routine is to
  1164. ** make sure all Cells for pPage once again fit in pPage->aData[].
  1165. **
  1166. ** In the course of balancing the siblings of pPage, the parent of pPage
  1167. ** might become overfull or underfull.  If that happens, then this routine
  1168. ** is called recursively on the parent.
  1169. **
  1170. ** If this routine fails for any reason, it might leave the database
  1171. ** in a corrupted state.  So if this routine fails, the database should
  1172. ** be rolled back.
  1173. */
  1174. static int balance_nonroot(MemPage *pPage){
  1175.   MemPage *pParent;            /* The parent of pPage */
  1176.   BtShared *pBt;               /* The whole database */
  1177.   int nCell = 0;               /* Number of cells in apCell[] */
  1178.   int nMaxCells = 0;           /* Allocated size of apCell, szCell, aFrom. */
  1179.   int nOld;                    /* Number of pages in apOld[] */
  1180.   int nNew;                    /* Number of pages in apNew[] */
  1181.   int nDiv;                    /* Number of cells in apDiv[] */
  1182.   int i, j, k;                 /* Loop counters */
  1183.   int idx;                     /* Index of pPage in pParent->aCell[] */
  1184.   int nxDiv;                   /* Next divider slot in pParent->aCell[] */
  1185.   int rc;                      /* The return code */
  1186.   int leafCorrection;          /* 4 if pPage is a leaf.  0 if not */
  1187.   int leafData;                /* True if pPage is a leaf of a LEAFDATA tree */
  1188.   int usableSpace;             /* Bytes in pPage beyond the header */
  1189.   int pageFlags;               /* Value of pPage->aData[0] */
  1190.   int subtotal;                /* Subtotal of bytes in cells on one page */
  1191.   int iSpace = 0;              /* First unused byte of aSpace[] */
  1192.   MemPage *apOld[NB];          /* pPage and up to two siblings */
  1193.   Pgno pgnoOld[NB];            /* Page numbers for each page in apOld[] */
  1194.   MemPage *apCopy[NB];         /* Private copies of apOld[] pages */
  1195.   MemPage *apNew[NB+2];        /* pPage and up to NB siblings after balancing */
  1196.   Pgno pgnoNew[NB+2];          /* Page numbers for each page in apNew[] */
  1197.   u8 *apDiv[NB];               /* Divider cells in pParent */
  1198.   int cntNew[NB+2];            /* Index in aCell[] of cell after i-th page */
  1199.   int szNew[NB+2];             /* Combined size of cells place on i-th page */
  1200.   u8 **apCell = 0;             /* All cells begin balanced */
  1201.   u16 *szCell;                 /* Local size of all cells in apCell[] */
  1202.   u8 *aCopy[NB];               /* Space for holding data of apCopy[] */
  1203.   u8 *aSpace;                  /* Space to hold copies of dividers cells */
  1204. #ifndef SQLITE_OMIT_AUTOVACUUM
  1205.   u8 *aFrom = 0;
  1206. #endif
  1207.   assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  1208.   /* 
  1209.   ** Find the parent page.
  1210.   */
  1211.   assert( pPage->isInit );
  1212.   assert( sqlite3PagerIswriteable(pPage->pDbPage) || pPage->nOverflow==1 );
  1213.   pBt = pPage->pBt;
  1214.   pParent = pPage->pParent;
  1215.   assert( pParent );
  1216.   if( SQLITE_OK!=(rc = sqlite3PagerWrite(pParent->pDbPage)) ){
  1217.     return rc;
  1218.   }
  1219.   TRACE(("BALANCE: begin page %d child of %dn", pPage->pgno, pParent->pgno));
  1220. #ifndef SQLITE_OMIT_QUICKBALANCE
  1221.   /*
  1222.   ** A special case:  If a new entry has just been inserted into a
  1223.   ** table (that is, a btree with integer keys and all data at the leaves)
  1224.   ** and the new entry is the right-most entry in the tree (it has the
  1225.   ** largest key) then use the special balance_quick() routine for
  1226.   ** balancing.  balance_quick() is much faster and results in a tighter
  1227.   ** packing of data in the common case.
  1228.   */
  1229.   if( pPage->leaf &&
  1230.       pPage->intKey &&
  1231.       pPage->leafData &&
  1232.       pPage->nOverflow==1 &&
  1233.       pPage->aOvfl[0].idx==pPage->nCell &&
  1234.       pPage->pParent->pgno!=1 &&
  1235.       get4byte(&pParent->aData[pParent->hdrOffset+8])==pPage->pgno
  1236.   ){
  1237.     /*
  1238.     ** TODO: Check the siblings to the left of pPage. It may be that
  1239.     ** they are not full and no new page is required.
  1240.     */
  1241.     return balance_quick(pPage, pParent);
  1242.   }
  1243. #endif
  1244.   if( SQLITE_OK!=(rc = sqlite3PagerWrite(pPage->pDbPage)) ){
  1245.     return rc;
  1246.   }
  1247.   /*
  1248.   ** Find the cell in the parent page whose left child points back
  1249.   ** to pPage.  The "idx" variable is the index of that cell.  If pPage
  1250.   ** is the rightmost child of pParent then set idx to pParent->nCell 
  1251.   */
  1252.   if( pParent->idxShift ){
  1253.     Pgno pgno;
  1254.     pgno = pPage->pgno;
  1255.     assert( pgno==sqlite3PagerPagenumber(pPage->pDbPage) );
  1256.     for(idx=0; idx<pParent->nCell; idx++){
  1257.       if( get4byte(findCell(pParent, idx))==pgno ){
  1258.         break;
  1259.       }
  1260.     }
  1261.     assert( idx<pParent->nCell
  1262.              || get4byte(&pParent->aData[pParent->hdrOffset+8])==pgno );
  1263.   }else{
  1264.     idx = pPage->idxParent;
  1265.   }
  1266.   /*
  1267.   ** Initialize variables so that it will be safe to jump
  1268.   ** directly to balance_cleanup at any moment.
  1269.   */
  1270.   nOld = nNew = 0;
  1271.   sqlite3PagerRef(pParent->pDbPage);
  1272.   /*
  1273.   ** Find sibling pages to pPage and the cells in pParent that divide
  1274.   ** the siblings.  An attempt is made to find NN siblings on either
  1275.   ** side of pPage.  More siblings are taken from one side, however, if
  1276.   ** pPage there are fewer than NN siblings on the other side.  If pParent
  1277.   ** has NB or fewer children then all children of pParent are taken.
  1278.   */
  1279.   nxDiv = idx - NN;
  1280.   if( nxDiv + NB > pParent->nCell ){
  1281.     nxDiv = pParent->nCell - NB + 1;
  1282.   }
  1283.   if( nxDiv<0 ){
  1284.     nxDiv = 0;
  1285.   }
  1286.   nDiv = 0;
  1287.   for(i=0, k=nxDiv; i<NB; i++, k++){
  1288.     if( k<pParent->nCell ){
  1289.       apDiv[i] = findCell(pParent, k);
  1290.       nDiv++;
  1291.       assert( !pParent->leaf );
  1292.       pgnoOld[i] = get4byte(apDiv[i]);
  1293.     }else if( k==pParent->nCell ){
  1294.       pgnoOld[i] = get4byte(&pParent->aData[pParent->hdrOffset+8]);
  1295.     }else{
  1296.       break;
  1297.     }
  1298.     rc = getAndInitPage(pBt, pgnoOld[i], &apOld[i], pParent);
  1299.     if( rc ) goto balance_cleanup;
  1300.     apOld[i]->idxParent = k;
  1301.     apCopy[i] = 0;
  1302.     assert( i==nOld );
  1303.     nOld++;
  1304.     nMaxCells += 1+apOld[i]->nCell+apOld[i]->nOverflow;
  1305.   }
  1306.   /* Make nMaxCells a multiple of 4 in order to preserve 8-byte
  1307.   ** alignment */
  1308.   nMaxCells = (nMaxCells + 3)&~3;
  1309.   /*
  1310.   ** Allocate space for memory structures
  1311.   */
  1312.   apCell = sqlite3_malloc( 
  1313.        nMaxCells*sizeof(u8*)                       /* apCell */
  1314.      + nMaxCells*sizeof(u16)                       /* szCell */
  1315.      + (ROUND8(sizeof(MemPage))+pBt->pageSize)*NB  /* aCopy */
  1316.      + pBt->pageSize*5                             /* aSpace */
  1317.      + (ISAUTOVACUUM ? nMaxCells : 0)              /* aFrom */
  1318.   );
  1319.   if( apCell==0 ){
  1320.     rc = SQLITE_NOMEM;
  1321.     goto balance_cleanup;
  1322.   }
  1323.   szCell = (u16*)&apCell[nMaxCells];
  1324.   aCopy[0] = (u8*)&szCell[nMaxCells];
  1325.   assert( ((aCopy[0] - (u8*)apCell) & 7)==0 ); /* 8-byte alignment required */
  1326.   for(i=1; i<NB; i++){
  1327.     aCopy[i] = &aCopy[i-1][pBt->pageSize+ROUND8(sizeof(MemPage))];
  1328.     assert( ((aCopy[i] - (u8*)apCell) & 7)==0 ); /* 8-byte alignment required */
  1329.   }
  1330.   aSpace = &aCopy[NB-1][pBt->pageSize+ROUND8(sizeof(MemPage))];
  1331.   assert( ((aSpace - (u8*)apCell) & 7)==0 ); /* 8-byte alignment required */
  1332. #ifndef SQLITE_OMIT_AUTOVACUUM
  1333.   if( pBt->autoVacuum ){
  1334.     aFrom = &aSpace[5*pBt->pageSize];
  1335.   }
  1336. #endif
  1337.   
  1338.   /*
  1339.   ** Make copies of the content of pPage and its siblings into aOld[].
  1340.   ** The rest of this function will use data from the copies rather
  1341.   ** that the original pages since the original pages will be in the
  1342.   ** process of being overwritten.
  1343.   */
  1344.   for(i=0; i<nOld; i++){
  1345.     MemPage *p = apCopy[i] = (MemPage*)aCopy[i];
  1346.     memcpy(p, apOld[i], sizeof(MemPage));
  1347.     p->aData = (void*)&p[1];
  1348.     memcpy(p->aData, apOld[i]->aData, pBt->pageSize);
  1349.   }
  1350.   /*
  1351.   ** Load pointers to all cells on sibling pages and the divider cells
  1352.   ** into the local apCell[] array.  Make copies of the divider cells
  1353.   ** into space obtained form aSpace[] and remove the the divider Cells
  1354.   ** from pParent.
  1355.   **
  1356.   ** If the siblings are on leaf pages, then the child pointers of the
  1357.   ** divider cells are stripped from the cells before they are copied
  1358.   ** into aSpace[].  In this way, all cells in apCell[] are without
  1359.   ** child pointers.  If siblings are not leaves, then all cell in
  1360.   ** apCell[] include child pointers.  Either way, all cells in apCell[]
  1361.   ** are alike.
  1362.   **
  1363.   ** leafCorrection:  4 if pPage is a leaf.  0 if pPage is not a leaf.
  1364.   **       leafData:  1 if pPage holds key+data and pParent holds only keys.
  1365.   */
  1366.   nCell = 0;
  1367.   leafCorrection = pPage->leaf*4;
  1368.   leafData = pPage->leafData && pPage->leaf;
  1369.   for(i=0; i<nOld; i++){
  1370.     MemPage *pOld = apCopy[i];
  1371.     int limit = pOld->nCell+pOld->nOverflow;
  1372.     for(j=0; j<limit; j++){
  1373.       assert( nCell<nMaxCells );
  1374.       apCell[nCell] = findOverflowCell(pOld, j);
  1375.       szCell[nCell] = cellSizePtr(pOld, apCell[nCell]);
  1376. #ifndef SQLITE_OMIT_AUTOVACUUM
  1377.       if( pBt->autoVacuum ){
  1378.         int a;
  1379.         aFrom[nCell] = i;
  1380.         for(a=0; a<pOld->nOverflow; a++){
  1381.           if( pOld->aOvfl[a].pCell==apCell[nCell] ){
  1382.             aFrom[nCell] = 0xFF;
  1383.             break;
  1384.           }
  1385.         }
  1386.       }
  1387. #endif
  1388.       nCell++;
  1389.     }
  1390.     if( i<nOld-1 ){
  1391.       u16 sz = cellSizePtr(pParent, apDiv[i]);
  1392.       if( leafData ){
  1393.         /* With the LEAFDATA flag, pParent cells hold only INTKEYs that
  1394.         ** are duplicates of keys on the child pages.  We need to remove
  1395.         ** the divider cells from pParent, but the dividers cells are not
  1396.         ** added to apCell[] because they are duplicates of child cells.
  1397.         */
  1398.         dropCell(pParent, nxDiv, sz);
  1399.       }else{
  1400.         u8 *pTemp;
  1401.         assert( nCell<nMaxCells );
  1402.         szCell[nCell] = sz;
  1403.         pTemp = &aSpace[iSpace];
  1404.         iSpace += sz;
  1405.         assert( iSpace<=pBt->pageSize*5 );
  1406.         memcpy(pTemp, apDiv[i], sz);
  1407.         apCell[nCell] = pTemp+leafCorrection;
  1408. #ifndef SQLITE_OMIT_AUTOVACUUM
  1409.         if( pBt->autoVacuum ){
  1410.           aFrom[nCell] = 0xFF;
  1411.         }
  1412. #endif
  1413.         dropCell(pParent, nxDiv, sz);
  1414.         szCell[nCell] -= leafCorrection;
  1415.         assert( get4byte(pTemp)==pgnoOld[i] );
  1416.         if( !pOld->leaf ){
  1417.           assert( leafCorrection==0 );
  1418.           /* The right pointer of the child page pOld becomes the left
  1419.           ** pointer of the divider cell */
  1420.           memcpy(apCell[nCell], &pOld->aData[pOld->hdrOffset+8], 4);
  1421.         }else{
  1422.           assert( leafCorrection==4 );
  1423.           if( szCell[nCell]<4 ){
  1424.             /* Do not allow any cells smaller than 4 bytes. */
  1425.             szCell[nCell] = 4;
  1426.           }
  1427.         }
  1428.         nCell++;
  1429.       }
  1430.     }
  1431.   }
  1432.   /*
  1433.   ** Figure out the number of pages needed to hold all nCell cells.
  1434.   ** Store this number in "k".  Also compute szNew[] which is the total
  1435.   ** size of all cells on the i-th page and cntNew[] which is the index
  1436.   ** in apCell[] of the cell that divides page i from page i+1.  
  1437.   ** cntNew[k] should equal nCell.
  1438.   **
  1439.   ** Values computed by this block:
  1440.   **
  1441.   **           k: The total number of sibling pages
  1442.   **    szNew[i]: Spaced used on the i-th sibling page.
  1443.   **   cntNew[i]: Index in apCell[] and szCell[] for the first cell to
  1444.   **              the right of the i-th sibling page.
  1445.   ** usableSpace: Number of bytes of space available on each sibling.
  1446.   ** 
  1447.   */
  1448.   usableSpace = pBt->usableSize - 12 + leafCorrection;
  1449.   for(subtotal=k=i=0; i<nCell; i++){
  1450.     assert( i<nMaxCells );
  1451.     subtotal += szCell[i] + 2;
  1452.     if( subtotal > usableSpace ){
  1453.       szNew[k] = subtotal - szCell[i];
  1454.       cntNew[k] = i;
  1455.       if( leafData ){ i--; }
  1456.       subtotal = 0;
  1457.       k++;
  1458.     }
  1459.   }
  1460.   szNew[k] = subtotal;
  1461.   cntNew[k] = nCell;
  1462.   k++;
  1463.   /*
  1464.   ** The packing computed by the previous block is biased toward the siblings
  1465.   ** on the left side.  The left siblings are always nearly full, while the
  1466.   ** right-most sibling might be nearly empty.  This block of code attempts
  1467.   ** to adjust the packing of siblings to get a better balance.
  1468.   **
  1469.   ** This adjustment is more than an optimization.  The packing above might
  1470.   ** be so out of balance as to be illegal.  For example, the right-most
  1471.   ** sibling might be completely empty.  This adjustment is not optional.
  1472.   */
  1473.   for(i=k-1; i>0; i--){
  1474.     int szRight = szNew[i];  /* Size of sibling on the right */
  1475.     int szLeft = szNew[i-1]; /* Size of sibling on the left */
  1476.     int r;              /* Index of right-most cell in left sibling */
  1477.     int d;              /* Index of first cell to the left of right sibling */
  1478.     r = cntNew[i-1] - 1;
  1479.     d = r + 1 - leafData;
  1480.     assert( d<nMaxCells );
  1481.     assert( r<nMaxCells );
  1482.     while( szRight==0 || szRight+szCell[d]+2<=szLeft-(szCell[r]+2) ){
  1483.       szRight += szCell[d] + 2;
  1484.       szLeft -= szCell[r] + 2;
  1485.       cntNew[i-1]--;
  1486.       r = cntNew[i-1] - 1;
  1487.       d = r + 1 - leafData;
  1488.     }
  1489.     szNew[i] = szRight;
  1490.     szNew[i-1] = szLeft;
  1491.   }
  1492.   /* Either we found one or more cells (cntnew[0])>0) or we are the
  1493.   ** a virtual root page.  A virtual root page is when the real root
  1494.   ** page is page 1 and we are the only child of that page.
  1495.   */
  1496.   assert( cntNew[0]>0 || (pParent->pgno==1 && pParent->nCell==0) );
  1497.   /*
  1498.   ** Allocate k new pages.  Reuse old pages where possible.
  1499.   */
  1500.   assert( pPage->pgno>1 );
  1501.   pageFlags = pPage->aData[0];
  1502.   for(i=0; i<k; i++){
  1503.     MemPage *pNew;
  1504.     if( i<nOld ){
  1505.       pNew = apNew[i] = apOld[i];
  1506.       pgnoNew[i] = pgnoOld[i];
  1507.       apOld[i] = 0;
  1508.       rc = sqlite3PagerWrite(pNew->pDbPage);
  1509.       nNew++;
  1510.       if( rc ) goto balance_cleanup;
  1511.     }else{
  1512.       assert( i>0 );
  1513.       rc = allocateBtreePage(pBt, &pNew, &pgnoNew[i], pgnoNew[i-1], 0);
  1514.       if( rc ) goto balance_cleanup;
  1515.       apNew[i] = pNew;
  1516.       nNew++;
  1517.     }
  1518.     zeroPage(pNew, pageFlags);
  1519.   }
  1520.   /* Free any old pages that were not reused as new pages.
  1521.   */
  1522.   while( i<nOld ){
  1523.     rc = freePage(apOld[i]);
  1524.     if( rc ) goto balance_cleanup;
  1525.     releasePage(apOld[i]);
  1526.     apOld[i] = 0;
  1527.     i++;
  1528.   }
  1529.   /*
  1530.   ** Put the new pages in accending order.  This helps to
  1531.   ** keep entries in the disk file in order so that a scan
  1532.   ** of the table is a linear scan through the file.  That
  1533.   ** in turn helps the operating system to deliver pages
  1534.   ** from the disk more rapidly.
  1535.   **
  1536.   ** An O(n^2) insertion sort algorithm is used, but since
  1537.   ** n is never more than NB (a small constant), that should
  1538.   ** not be a problem.
  1539.   **
  1540.   ** When NB==3, this one optimization makes the database
  1541.   ** about 25% faster for large insertions and deletions.
  1542.   */
  1543.   for(i=0; i<k-1; i++){
  1544.     int minV = pgnoNew[i];
  1545.     int minI = i;
  1546.     for(j=i+1; j<k; j++){
  1547.       if( pgnoNew[j]<(unsigned)minV ){
  1548.         minI = j;
  1549.         minV = pgnoNew[j];
  1550.       }
  1551.     }
  1552.     if( minI>i ){
  1553.       int t;
  1554.       MemPage *pT;
  1555.       t = pgnoNew[i];
  1556.       pT = apNew[i];
  1557.       pgnoNew[i] = pgnoNew[minI];
  1558.       apNew[i] = apNew[minI];
  1559.       pgnoNew[minI] = t;
  1560.       apNew[minI] = pT;
  1561.     }
  1562.   }
  1563.   TRACE(("BALANCE: old: %d %d %d  new: %d(%d) %d(%d) %d(%d) %d(%d) %d(%d)n",
  1564.     pgnoOld[0], 
  1565.     nOld>=2 ? pgnoOld[1] : 0,
  1566.     nOld>=3 ? pgnoOld[2] : 0,
  1567.     pgnoNew[0], szNew[0],
  1568.     nNew>=2 ? pgnoNew[1] : 0, nNew>=2 ? szNew[1] : 0,
  1569.     nNew>=3 ? pgnoNew[2] : 0, nNew>=3 ? szNew[2] : 0,
  1570.     nNew>=4 ? pgnoNew[3] : 0, nNew>=4 ? szNew[3] : 0,
  1571.     nNew>=5 ? pgnoNew[4] : 0, nNew>=5 ? szNew[4] : 0));
  1572.   /*
  1573.   ** Evenly distribute the data in apCell[] across the new pages.
  1574.   ** Insert divider cells into pParent as necessary.
  1575.   */
  1576.   j = 0;
  1577.   for(i=0; i<nNew; i++){
  1578.     /* Assemble the new sibling page. */
  1579.     MemPage *pNew = apNew[i];
  1580.     assert( j<nMaxCells );
  1581.     assert( pNew->pgno==pgnoNew[i] );
  1582.     assemblePage(pNew, cntNew[i]-j, &apCell[j], &szCell[j]);
  1583.     assert( pNew->nCell>0 || (nNew==1 && cntNew[0]==0) );
  1584.     assert( pNew->nOverflow==0 );
  1585. #ifndef SQLITE_OMIT_AUTOVACUUM
  1586.     /* If this is an auto-vacuum database, update the pointer map entries
  1587.     ** that point to the siblings that were rearranged. These can be: left
  1588.     ** children of cells, the right-child of the page, or overflow pages
  1589.     ** pointed to by cells.
  1590.     */
  1591.     if( pBt->autoVacuum ){
  1592.       for(k=j; k<cntNew[i]; k++){
  1593.         assert( k<nMaxCells );
  1594.         if( aFrom[k]==0xFF || apCopy[aFrom[k]]->pgno!=pNew->pgno ){
  1595.           rc = ptrmapPutOvfl(pNew, k-j);
  1596.           if( rc!=SQLITE_OK ){
  1597.             goto balance_cleanup;
  1598.           }
  1599.         }
  1600.       }
  1601.     }
  1602. #endif
  1603.     j = cntNew[i];
  1604.     /* If the sibling page assembled above was not the right-most sibling,
  1605.     ** insert a divider cell into the parent page.
  1606.     */
  1607.     if( i<nNew-1 && j<nCell ){
  1608.       u8 *pCell;
  1609.       u8 *pTemp;
  1610.       int sz;
  1611.       assert( j<nMaxCells );
  1612.       pCell = apCell[j];
  1613.       sz = szCell[j] + leafCorrection;
  1614.       if( !pNew->leaf ){
  1615.         memcpy(&pNew->aData[8], pCell, 4);
  1616.         pTemp = 0;
  1617.       }else if( leafData ){
  1618.         /* If the tree is a leaf-data tree, and the siblings are leaves, 
  1619.         ** then there is no divider cell in apCell[]. Instead, the divider 
  1620.         ** cell consists of the integer key for the right-most cell of 
  1621.         ** the sibling-page assembled above only.
  1622.         */
  1623.         CellInfo info;
  1624.         j--;
  1625.         sqlite3BtreeParseCellPtr(pNew, apCell[j], &info);
  1626.         pCell = &aSpace[iSpace];
  1627.         fillInCell(pParent, pCell, 0, info.nKey, 0, 0, 0, &sz);
  1628.         iSpace += sz;
  1629.         assert( iSpace<=pBt->pageSize*5 );
  1630.         pTemp = 0;
  1631.       }else{
  1632.         pCell -= 4;
  1633.         pTemp = &aSpace[iSpace];
  1634.         iSpace += sz;
  1635.         assert( iSpace<=pBt->pageSize*5 );
  1636.         /* Obscure case for non-leaf-data trees: If the cell at pCell was
  1637.         ** previously stored on a leaf node, and its reported size was 4
  1638.         ** bytes, then it may actually be smaller than this 
  1639.         ** (see sqlite3BtreeParseCellPtr(), 4 bytes is the minimum size of
  1640.         ** any cell). But it is important to pass the correct size to 
  1641.         ** insertCell(), so reparse the cell now.
  1642.         **
  1643.         ** Note that this can never happen in an SQLite data file, as all
  1644.         ** cells are at least 4 bytes. It only happens in b-trees used
  1645.         ** to evaluate "IN (SELECT ...)" and similar clauses.
  1646.         */
  1647.         if( szCell[j]==4 ){
  1648.           assert(leafCorrection==4);
  1649.           sz = cellSizePtr(pParent, pCell);
  1650.         }
  1651.       }
  1652.       rc = insertCell(pParent, nxDiv, pCell, sz, pTemp, 4);
  1653.       if( rc!=SQLITE_OK ) goto balance_cleanup;
  1654.       put4byte(findOverflowCell(pParent,nxDiv), pNew->pgno);
  1655. #ifndef SQLITE_OMIT_AUTOVACUUM
  1656.       /* If this is an auto-vacuum database, and not a leaf-data tree,
  1657.       ** then update the pointer map with an entry for the overflow page
  1658.       ** that the cell just inserted points to (if any).
  1659.       */
  1660.       if( pBt->autoVacuum && !leafData ){
  1661.         rc = ptrmapPutOvfl(pParent, nxDiv);
  1662.         if( rc!=SQLITE_OK ){
  1663.           goto balance_cleanup;
  1664.         }
  1665.       }
  1666. #endif
  1667.       j++;
  1668.       nxDiv++;
  1669.     }
  1670.   }
  1671.   assert( j==nCell );
  1672.   assert( nOld>0 );
  1673.   assert( nNew>0 );
  1674.   if( (pageFlags & PTF_LEAF)==0 ){
  1675.     memcpy(&apNew[nNew-1]->aData[8], &apCopy[nOld-1]->aData[8], 4);
  1676.   }
  1677.   if( nxDiv==pParent->nCell+pParent->nOverflow ){
  1678.     /* Right-most sibling is the right-most child of pParent */
  1679.     put4byte(&pParent->aData[pParent->hdrOffset+8], pgnoNew[nNew-1]);
  1680.   }else{
  1681.     /* Right-most sibling is the left child of the first entry in pParent
  1682.     ** past the right-most divider entry */
  1683.     put4byte(findOverflowCell(pParent, nxDiv), pgnoNew[nNew-1]);
  1684.   }
  1685.   /*
  1686.   ** Reparent children of all cells.
  1687.   */
  1688.   for(i=0; i<nNew; i++){
  1689.     rc = reparentChildPages(apNew[i]);
  1690.     if( rc!=SQLITE_OK ) goto balance_cleanup;
  1691.   }
  1692.   rc = reparentChildPages(pParent);
  1693.   if( rc!=SQLITE_OK ) goto balance_cleanup;
  1694.   /*
  1695.   ** Balance the parent page.  Note that the current page (pPage) might
  1696.   ** have been added to the freelist so it might no longer be initialized.
  1697.   ** But the parent page will always be initialized.
  1698.   */
  1699.   assert( pParent->isInit );
  1700.   rc = balance(pParent, 0);
  1701.   
  1702.   /*
  1703.   ** Cleanup before returning.
  1704.   */
  1705. balance_cleanup:
  1706.   sqlite3_free(apCell);
  1707.   for(i=0; i<nOld; i++){
  1708.     releasePage(apOld[i]);
  1709.   }
  1710.   for(i=0; i<nNew; i++){
  1711.     releasePage(apNew[i]);
  1712.   }
  1713.   releasePage(pParent);
  1714.   TRACE(("BALANCE: finished with %d: old=%d new=%d cells=%dn",
  1715.           pPage->pgno, nOld, nNew, nCell));
  1716.   return rc;
  1717. }
  1718. /*
  1719. ** This routine is called for the root page of a btree when the root
  1720. ** page contains no cells.  This is an opportunity to make the tree
  1721. ** shallower by one level.
  1722. */
  1723. static int balance_shallower(MemPage *pPage){
  1724.   MemPage *pChild;             /* The only child page of pPage */
  1725.   Pgno pgnoChild;              /* Page number for pChild */
  1726.   int rc = SQLITE_OK;          /* Return code from subprocedures */
  1727.   BtShared *pBt;                  /* The main BTree structure */
  1728.   int mxCellPerPage;           /* Maximum number of cells per page */
  1729.   u8 **apCell;                 /* All cells from pages being balanced */
  1730.   u16 *szCell;                 /* Local size of all cells */
  1731.   assert( pPage->pParent==0 );
  1732.   assert( pPage->nCell==0 );
  1733.   assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  1734.   pBt = pPage->pBt;
  1735.   mxCellPerPage = MX_CELL(pBt);
  1736.   apCell = sqlite3_malloc( mxCellPerPage*(sizeof(u8*)+sizeof(u16)) );
  1737.   if( apCell==0 ) return SQLITE_NOMEM;
  1738.   szCell = (u16*)&apCell[mxCellPerPage];
  1739.   if( pPage->leaf ){
  1740.     /* The table is completely empty */
  1741.     TRACE(("BALANCE: empty table %dn", pPage->pgno));
  1742.   }else{
  1743.     /* The root page is empty but has one child.  Transfer the
  1744.     ** information from that one child into the root page if it 
  1745.     ** will fit.  This reduces the depth of the tree by one.
  1746.     **
  1747.     ** If the root page is page 1, it has less space available than
  1748.     ** its child (due to the 100 byte header that occurs at the beginning
  1749.     ** of the database fle), so it might not be able to hold all of the 
  1750.     ** information currently contained in the child.  If this is the 
  1751.     ** case, then do not do the transfer.  Leave page 1 empty except
  1752.     ** for the right-pointer to the child page.  The child page becomes
  1753.     ** the virtual root of the tree.
  1754.     */
  1755.     pgnoChild = get4byte(&pPage->aData[pPage->hdrOffset+8]);
  1756.     assert( pgnoChild>0 );
  1757.     assert( pgnoChild<=sqlite3PagerPagecount(pPage->pBt->pPager) );
  1758.     rc = sqlite3BtreeGetPage(pPage->pBt, pgnoChild, &pChild, 0);
  1759.     if( rc ) goto end_shallow_balance;
  1760.     if( pPage->pgno==1 ){
  1761.       rc = sqlite3BtreeInitPage(pChild, pPage);
  1762.       if( rc ) goto end_shallow_balance;
  1763.       assert( pChild->nOverflow==0 );
  1764.       if( pChild->nFree>=100 ){
  1765.         /* The child information will fit on the root page, so do the
  1766.         ** copy */
  1767.         int i;
  1768.         zeroPage(pPage, pChild->aData[0]);
  1769.         for(i=0; i<pChild->nCell; i++){
  1770.           apCell[i] = findCell(pChild,i);
  1771.           szCell[i] = cellSizePtr(pChild, apCell[i]);
  1772.         }
  1773.         assemblePage(pPage, pChild->nCell, apCell, szCell);
  1774.         /* Copy the right-pointer of the child to the parent. */
  1775.         put4byte(&pPage->aData[pPage->hdrOffset+8], 
  1776.             get4byte(&pChild->aData[pChild->hdrOffset+8]));
  1777.         freePage(pChild);
  1778.         TRACE(("BALANCE: child %d transfer to page 1n", pChild->pgno));
  1779.       }else{
  1780.         /* The child has more information that will fit on the root.
  1781.         ** The tree is already balanced.  Do nothing. */
  1782.         TRACE(("BALANCE: child %d will not fit on page 1n", pChild->pgno));
  1783.       }
  1784.     }else{
  1785.       memcpy(pPage->aData, pChild->aData, pPage->pBt->usableSize);
  1786.       pPage->isInit = 0;
  1787.       pPage->pParent = 0;
  1788.       rc = sqlite3BtreeInitPage(pPage, 0);
  1789.       assert( rc==SQLITE_OK );
  1790.       freePage(pChild);
  1791.       TRACE(("BALANCE: transfer child %d into root %dn",
  1792.               pChild->pgno, pPage->pgno));
  1793.     }
  1794.     rc = reparentChildPages(pPage);
  1795.     assert( pPage->nOverflow==0 );
  1796. #ifndef SQLITE_OMIT_AUTOVACUUM
  1797.     if( pBt->autoVacuum ){
  1798.       int i;
  1799.       for(i=0; i<pPage->nCell; i++){ 
  1800.         rc = ptrmapPutOvfl(pPage, i);
  1801.         if( rc!=SQLITE_OK ){
  1802.           goto end_shallow_balance;
  1803.         }
  1804.       }
  1805.     }
  1806. #endif
  1807.     releasePage(pChild);
  1808.   }
  1809. end_shallow_balance:
  1810.   sqlite3_free(apCell);
  1811.   return rc;
  1812. }
  1813. /*
  1814. ** The root page is overfull
  1815. **
  1816. ** When this happens, Create a new child page and copy the
  1817. ** contents of the root into the child.  Then make the root
  1818. ** page an empty page with rightChild pointing to the new
  1819. ** child.   Finally, call balance_internal() on the new child
  1820. ** to cause it to split.
  1821. */
  1822. static int balance_deeper(MemPage *pPage){
  1823.   int rc;             /* Return value from subprocedures */
  1824.   MemPage *pChild;    /* Pointer to a new child page */
  1825.   Pgno pgnoChild;     /* Page number of the new child page */
  1826.   BtShared *pBt;         /* The BTree */
  1827.   int usableSize;     /* Total usable size of a page */
  1828.   u8 *data;           /* Content of the parent page */
  1829.   u8 *cdata;          /* Content of the child page */
  1830.   int hdr;            /* Offset to page header in parent */
  1831.   int brk;            /* Offset to content of first cell in parent */
  1832.   assert( pPage->pParent==0 );
  1833.   assert( pPage->nOverflow>0 );
  1834.   pBt = pPage->pBt;
  1835.   assert( sqlite3_mutex_held(pBt->mutex) );
  1836.   rc = allocateBtreePage(pBt, &pChild, &pgnoChild, pPage->pgno, 0);
  1837.   if( rc ) return rc;
  1838.   assert( sqlite3PagerIswriteable(pChild->pDbPage) );
  1839.   usableSize = pBt->usableSize;
  1840.   data = pPage->aData;
  1841.   hdr = pPage->hdrOffset;
  1842.   brk = get2byte(&data[hdr+5]);
  1843.   cdata = pChild->aData;
  1844.   memcpy(cdata, &data[hdr], pPage->cellOffset+2*pPage->nCell-hdr);
  1845.   memcpy(&cdata[brk], &data[brk], usableSize-brk);
  1846.   assert( pChild->isInit==0 );
  1847.   rc = sqlite3BtreeInitPage(pChild, pPage);
  1848.   if( rc ) goto balancedeeper_out;
  1849.   memcpy(pChild->aOvfl, pPage->aOvfl, pPage->nOverflow*sizeof(pPage->aOvfl[0]));
  1850.   pChild->nOverflow = pPage->nOverflow;
  1851.   if( pChild->nOverflow ){
  1852.     pChild->nFree = 0;
  1853.   }
  1854.   assert( pChild->nCell==pPage->nCell );
  1855.   zeroPage(pPage, pChild->aData[0] & ~PTF_LEAF);
  1856.   put4byte(&pPage->aData[pPage->hdrOffset+8], pgnoChild);
  1857.   TRACE(("BALANCE: copy root %d into %dn", pPage->pgno, pChild->pgno));
  1858. #ifndef SQLITE_OMIT_AUTOVACUUM
  1859.   if( pBt->autoVacuum ){
  1860.     int i;
  1861.     rc = ptrmapPut(pBt, pChild->pgno, PTRMAP_BTREE, pPage->pgno);
  1862.     if( rc ) goto balancedeeper_out;
  1863.     for(i=0; i<pChild->nCell; i++){
  1864.       rc = ptrmapPutOvfl(pChild, i);
  1865.       if( rc!=SQLITE_OK ){
  1866.         return rc;
  1867.       }
  1868.     }
  1869.   }
  1870. #endif
  1871.   rc = balance_nonroot(pChild);
  1872. balancedeeper_out:
  1873.   releasePage(pChild);
  1874.   return rc;
  1875. }
  1876. /*
  1877. ** Decide if the page pPage needs to be balanced.  If balancing is
  1878. ** required, call the appropriate balancing routine.
  1879. */
  1880. static int balance(MemPage *pPage, int insert){
  1881.   int rc = SQLITE_OK;
  1882.   assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  1883.   if( pPage->pParent==0 ){
  1884.     rc = sqlite3PagerWrite(pPage->pDbPage);
  1885.     if( rc==SQLITE_OK && pPage->nOverflow>0 ){
  1886.       rc = balance_deeper(pPage);
  1887.     }
  1888.     if( rc==SQLITE_OK && pPage->nCell==0 ){
  1889.       rc = balance_shallower(pPage);
  1890.     }
  1891.   }else{
  1892.     if( pPage->nOverflow>0 || 
  1893.         (!insert && pPage->nFree>pPage->pBt->usableSize*2/3) ){
  1894.       rc = balance_nonroot(pPage);
  1895.     }
  1896.   }
  1897.   return rc;
  1898. }
  1899. /*
  1900. ** This routine checks all cursors that point to table pgnoRoot.
  1901. ** If any of those cursors were opened with wrFlag==0 in a different
  1902. ** database connection (a database connection that shares the pager
  1903. ** cache with the current connection) and that other connection 
  1904. ** is not in the ReadUncommmitted state, then this routine returns 
  1905. ** SQLITE_LOCKED.
  1906. **
  1907. ** In addition to checking for read-locks (where a read-lock 
  1908. ** means a cursor opened with wrFlag==0) this routine also moves
  1909. ** all write cursors so that they are pointing to the 
  1910. ** first Cell on the root page.  This is necessary because an insert 
  1911. ** or delete might change the number of cells on a page or delete
  1912. ** a page entirely and we do not want to leave any cursors 
  1913. ** pointing to non-existant pages or cells.
  1914. */
  1915. static int checkReadLocks(Btree *pBtree, Pgno pgnoRoot, BtCursor *pExclude){
  1916.   BtCursor *p;
  1917.   BtShared *pBt = pBtree->pBt;
  1918.   sqlite3 *db = pBtree->db;
  1919.   assert( sqlite3BtreeHoldsMutex(pBtree) );
  1920.   for(p=pBt->pCursor; p; p=p->pNext){
  1921.     if( p==pExclude ) continue;
  1922.     if( p->eState!=CURSOR_VALID ) continue;
  1923.     if( p->pgnoRoot!=pgnoRoot ) continue;
  1924.     if( p->wrFlag==0 ){
  1925.       sqlite3 *dbOther = p->pBtree->db;
  1926.       if( dbOther==0 ||
  1927.          (dbOther!=db && (dbOther->flags & SQLITE_ReadUncommitted)==0) ){
  1928.         return SQLITE_LOCKED;
  1929.       }
  1930.     }else if( p->pPage->pgno!=p->pgnoRoot ){
  1931.       moveToRoot(p);
  1932.     }
  1933.   }
  1934.   return SQLITE_OK;
  1935. }
  1936. /*
  1937. ** Make sure pBt->pTmpSpace points to an allocation of 
  1938. ** MX_CELL_SIZE(pBt) bytes.
  1939. */
  1940. static void allocateTempSpace(BtShared *pBt){
  1941.   if( !pBt->pTmpSpace ){
  1942.     pBt->pTmpSpace = sqlite3_malloc(MX_CELL_SIZE(pBt));
  1943.   }
  1944. }
  1945. /*
  1946. ** Insert a new record into the BTree.  The key is given by (pKey,nKey)
  1947. ** and the data is given by (pData,nData).  The cursor is used only to
  1948. ** define what table the record should be inserted into.  The cursor
  1949. ** is left pointing at a random location.
  1950. **
  1951. ** For an INTKEY table, only the nKey value of the key is used.  pKey is
  1952. ** ignored.  For a ZERODATA table, the pData and nData are both ignored.
  1953. */
  1954. int sqlite3BtreeInsert(
  1955.   BtCursor *pCur,                /* Insert data into the table of this cursor */
  1956.   const void *pKey, i64 nKey,    /* The key of the new record */
  1957.   const void *pData, int nData,  /* The data of the new record */
  1958.   int nZero,                     /* Number of extra 0 bytes to append to data */
  1959.   int appendBias                 /* True if this is likely an append */
  1960. ){
  1961.   int rc;
  1962.   int loc;
  1963.   int szNew;
  1964.   MemPage *pPage;
  1965.   Btree *p = pCur->pBtree;
  1966.   BtShared *pBt = p->pBt;
  1967.   unsigned char *oldCell;
  1968.   unsigned char *newCell = 0;
  1969.   assert( cursorHoldsMutex(pCur) );
  1970.   if( pBt->inTransaction!=TRANS_WRITE ){
  1971.     /* Must start a transaction before doing an insert */
  1972.     rc = pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  1973.     return rc;
  1974.   }
  1975.   assert( !pBt->readOnly );
  1976.   if( !pCur->wrFlag ){
  1977.     return SQLITE_PERM;   /* Cursor not open for writing */
  1978.   }
  1979.   if( checkReadLocks(pCur->pBtree, pCur->pgnoRoot, pCur) ){
  1980.     return SQLITE_LOCKED; /* The table pCur points to has a read lock */
  1981.   }
  1982.   if( pCur->eState==CURSOR_FAULT ){
  1983.     return pCur->skip;
  1984.   }
  1985.   /* Save the positions of any other cursors open on this table */
  1986.   clearCursorPosition(pCur);
  1987.   if( 
  1988.     SQLITE_OK!=(rc = saveAllCursors(pBt, pCur->pgnoRoot, pCur)) ||
  1989.     SQLITE_OK!=(rc = sqlite3BtreeMoveto(pCur, pKey, 0, nKey, appendBias, &loc))
  1990.   ){
  1991.     return rc;
  1992.   }
  1993.   pPage = pCur->pPage;
  1994.   assert( pPage->intKey || nKey>=0 );
  1995.   assert( pPage->leaf || !pPage->leafData );
  1996.   TRACE(("INSERT: table=%d nkey=%lld ndata=%d page=%d %sn",
  1997.           pCur->pgnoRoot, nKey, nData, pPage->pgno,
  1998.           loc==0 ? "overwrite" : "new entry"));
  1999.   assert( pPage->isInit );
  2000.   allocateTempSpace(pBt);
  2001.   newCell = pBt->pTmpSpace;
  2002.   if( newCell==0 ) return SQLITE_NOMEM;
  2003.   rc = fillInCell(pPage, newCell, pKey, nKey, pData, nData, nZero, &szNew);
  2004.   if( rc ) goto end_insert;
  2005.   assert( szNew==cellSizePtr(pPage, newCell) );
  2006.   assert( szNew<=MX_CELL_SIZE(pBt) );
  2007.   if( loc==0 && CURSOR_VALID==pCur->eState ){
  2008.     u16 szOld;
  2009.     assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
  2010.     rc = sqlite3PagerWrite(pPage->pDbPage);
  2011.     if( rc ){
  2012.       goto end_insert;
  2013.     }
  2014.     oldCell = findCell(pPage, pCur->idx);
  2015.     if( !pPage->leaf ){
  2016.       memcpy(newCell, oldCell, 4);
  2017.     }
  2018.     szOld = cellSizePtr(pPage, oldCell);
  2019.     rc = clearCell(pPage, oldCell);
  2020.     if( rc ) goto end_insert;
  2021.     dropCell(pPage, pCur->idx, szOld);
  2022.   }else if( loc<0 && pPage->nCell>0 ){
  2023.     assert( pPage->leaf );
  2024.     pCur->idx++;
  2025.     pCur->info.nSize = 0;
  2026.     pCur->validNKey = 0;
  2027.   }else{
  2028.     assert( pPage->leaf );
  2029.   }
  2030.   rc = insertCell(pPage, pCur->idx, newCell, szNew, 0, 0);
  2031.   if( rc!=SQLITE_OK ) goto end_insert;
  2032.   rc = balance(pPage, 1);
  2033.   /* sqlite3BtreePageDump(pCur->pBt, pCur->pgnoRoot, 1); */
  2034.   /* fflush(stdout); */
  2035.   if( rc==SQLITE_OK ){
  2036.     moveToRoot(pCur);
  2037.   }
  2038. end_insert:
  2039.   return rc;
  2040. }
  2041. /*
  2042. ** Delete the entry that the cursor is pointing to.  The cursor
  2043. ** is left pointing at a random location.
  2044. */
  2045. int sqlite3BtreeDelete(BtCursor *pCur){
  2046.   MemPage *pPage = pCur->pPage;
  2047.   unsigned char *pCell;
  2048.   int rc;
  2049.   Pgno pgnoChild = 0;
  2050.   Btree *p = pCur->pBtree;
  2051.   BtShared *pBt = p->pBt;
  2052.   assert( cursorHoldsMutex(pCur) );
  2053.   assert( pPage->isInit );
  2054.   if( pBt->inTransaction!=TRANS_WRITE ){
  2055.     /* Must start a transaction before doing a delete */
  2056.     rc = pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  2057.     return rc;
  2058.   }
  2059.   assert( !pBt->readOnly );
  2060.   if( pCur->eState==CURSOR_FAULT ){
  2061.     return pCur->skip;
  2062.   }
  2063.   if( pCur->idx >= pPage->nCell ){
  2064.     return SQLITE_ERROR;  /* The cursor is not pointing to anything */
  2065.   }
  2066.   if( !pCur->wrFlag ){
  2067.     return SQLITE_PERM;   /* Did not open this cursor for writing */
  2068.   }
  2069.   if( checkReadLocks(pCur->pBtree, pCur->pgnoRoot, pCur) ){
  2070.     return SQLITE_LOCKED; /* The table pCur points to has a read lock */
  2071.   }
  2072.   /* Restore the current cursor position (a no-op if the cursor is not in 
  2073.   ** CURSOR_REQUIRESEEK state) and save the positions of any other cursors 
  2074.   ** open on the same table. Then call sqlite3PagerWrite() on the page
  2075.   ** that the entry will be deleted from.
  2076.   */
  2077.   if( 
  2078.     (rc = restoreOrClearCursorPosition(pCur))!=0 ||
  2079.     (rc = saveAllCursors(pBt, pCur->pgnoRoot, pCur))!=0 ||
  2080.     (rc = sqlite3PagerWrite(pPage->pDbPage))!=0
  2081.   ){
  2082.     return rc;
  2083.   }
  2084.   /* Locate the cell within its page and leave pCell pointing to the
  2085.   ** data. The clearCell() call frees any overflow pages associated with the
  2086.   ** cell. The cell itself is still intact.
  2087.   */
  2088.   pCell = findCell(pPage, pCur->idx);
  2089.   if( !pPage->leaf ){
  2090.     pgnoChild = get4byte(pCell);
  2091.   }
  2092.   rc = clearCell(pPage, pCell);
  2093.   if( rc ){
  2094.     return rc;
  2095.   }
  2096.   if( !pPage->leaf ){
  2097.     /*
  2098.     ** The entry we are about to delete is not a leaf so if we do not
  2099.     ** do something we will leave a hole on an internal page.
  2100.     ** We have to fill the hole by moving in a cell from a leaf.  The
  2101.     ** next Cell after the one to be deleted is guaranteed to exist and
  2102.     ** to be a leaf so we can use it.
  2103.     */
  2104.     BtCursor leafCur;
  2105.     unsigned char *pNext;
  2106.     int notUsed;
  2107.     unsigned char *tempCell = 0;
  2108.     assert( !pPage->leafData );
  2109.     sqlite3BtreeGetTempCursor(pCur, &leafCur);
  2110.     rc = sqlite3BtreeNext(&leafCur, &notUsed);
  2111.     if( rc==SQLITE_OK ){
  2112.       rc = sqlite3PagerWrite(leafCur.pPage->pDbPage);
  2113.     }
  2114.     if( rc==SQLITE_OK ){
  2115.       u16 szNext;
  2116.       TRACE(("DELETE: table=%d delete internal from %d replace from leaf %dn",
  2117.          pCur->pgnoRoot, pPage->pgno, leafCur.pPage->pgno));
  2118.       dropCell(pPage, pCur->idx, cellSizePtr(pPage, pCell));
  2119.       pNext = findCell(leafCur.pPage, leafCur.idx);
  2120.       szNext = cellSizePtr(leafCur.pPage, pNext);
  2121.       assert( MX_CELL_SIZE(pBt)>=szNext+4 );
  2122.       allocateTempSpace(pBt);
  2123.       tempCell = pBt->pTmpSpace;
  2124.       if( tempCell==0 ){
  2125.         rc = SQLITE_NOMEM;
  2126.       }
  2127.       if( rc==SQLITE_OK ){
  2128.         rc = insertCell(pPage, pCur->idx, pNext-4, szNext+4, tempCell, 0);
  2129.       }
  2130.       if( rc==SQLITE_OK ){
  2131.         put4byte(findOverflowCell(pPage, pCur->idx), pgnoChild);
  2132.         rc = balance(pPage, 0);
  2133.       }
  2134.       if( rc==SQLITE_OK ){
  2135.         dropCell(leafCur.pPage, leafCur.idx, szNext);
  2136.         rc = balance(leafCur.pPage, 0);
  2137.       }
  2138.     }
  2139.     sqlite3BtreeReleaseTempCursor(&leafCur);
  2140.   }else{
  2141.     TRACE(("DELETE: table=%d delete from leaf %dn",
  2142.        pCur->pgnoRoot, pPage->pgno));
  2143.     dropCell(pPage, pCur->idx, cellSizePtr(pPage, pCell));
  2144.     rc = balance(pPage, 0);
  2145.   }
  2146.   if( rc==SQLITE_OK ){
  2147.     moveToRoot(pCur);
  2148.   }
  2149.   return rc;
  2150. }
  2151. /*
  2152. ** Create a new BTree table.  Write into *piTable the page
  2153. ** number for the root page of the new table.
  2154. **
  2155. ** The type of type is determined by the flags parameter.  Only the
  2156. ** following values of flags are currently in use.  Other values for
  2157. ** flags might not work:
  2158. **
  2159. **     BTREE_INTKEY|BTREE_LEAFDATA     Used for SQL tables with rowid keys
  2160. **     BTREE_ZERODATA                  Used for SQL indices
  2161. */
  2162. static int btreeCreateTable(Btree *p, int *piTable, int flags){
  2163.   BtShared *pBt = p->pBt;
  2164.   MemPage *pRoot;
  2165.   Pgno pgnoRoot;
  2166.   int rc;
  2167.   assert( sqlite3BtreeHoldsMutex(p) );
  2168.   if( pBt->inTransaction!=TRANS_WRITE ){
  2169.     /* Must start a transaction first */
  2170.     rc = pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  2171.     return rc;
  2172.   }
  2173.   assert( !pBt->readOnly );
  2174. #ifdef SQLITE_OMIT_AUTOVACUUM
  2175.   rc = allocateBtreePage(pBt, &pRoot, &pgnoRoot, 1, 0);
  2176.   if( rc ){
  2177.     return rc;
  2178.   }
  2179. #else
  2180.   if( pBt->autoVacuum ){
  2181.     Pgno pgnoMove;      /* Move a page here to make room for the root-page */
  2182.     MemPage *pPageMove; /* The page to move to. */
  2183.     /* Creating a new table may probably require moving an existing database
  2184.     ** to make room for the new tables root page. In case this page turns
  2185.     ** out to be an overflow page, delete all overflow page-map caches
  2186.     ** held by open cursors.
  2187.     */
  2188.     invalidateAllOverflowCache(pBt);
  2189.     /* Read the value of meta[3] from the database to determine where the
  2190.     ** root page of the new table should go. meta[3] is the largest root-page
  2191.     ** created so far, so the new root-page is (meta[3]+1).
  2192.     */
  2193.     rc = sqlite3BtreeGetMeta(p, 4, &pgnoRoot);
  2194.     if( rc!=SQLITE_OK ){
  2195.       return rc;
  2196.     }
  2197.     pgnoRoot++;
  2198.     /* The new root-page may not be allocated on a pointer-map page, or the
  2199.     ** PENDING_BYTE page.
  2200.     */
  2201.     while( pgnoRoot==PTRMAP_PAGENO(pBt, pgnoRoot) ||
  2202.         pgnoRoot==PENDING_BYTE_PAGE(pBt) ){
  2203.       pgnoRoot++;
  2204.     }
  2205.     assert( pgnoRoot>=3 );
  2206.     /* Allocate a page. The page that currently resides at pgnoRoot will
  2207.     ** be moved to the allocated page (unless the allocated page happens
  2208.     ** to reside at pgnoRoot).
  2209.     */
  2210.     rc = allocateBtreePage(pBt, &pPageMove, &pgnoMove, pgnoRoot, 1);
  2211.     if( rc!=SQLITE_OK ){
  2212.       return rc;
  2213.     }
  2214.     if( pgnoMove!=pgnoRoot ){
  2215.       /* pgnoRoot is the page that will be used for the root-page of
  2216.       ** the new table (assuming an error did not occur). But we were
  2217.       ** allocated pgnoMove. If required (i.e. if it was not allocated
  2218.       ** by extending the file), the current page at position pgnoMove
  2219.       ** is already journaled.
  2220.       */
  2221.       u8 eType;
  2222.       Pgno iPtrPage;
  2223.       releasePage(pPageMove);
  2224.       /* Move the page currently at pgnoRoot to pgnoMove. */
  2225.       rc = sqlite3BtreeGetPage(pBt, pgnoRoot, &pRoot, 0);
  2226.       if( rc!=SQLITE_OK ){
  2227.         return rc;
  2228.       }
  2229.       rc = ptrmapGet(pBt, pgnoRoot, &eType, &iPtrPage);
  2230.       if( rc!=SQLITE_OK || eType==PTRMAP_ROOTPAGE || eType==PTRMAP_FREEPAGE ){
  2231.         releasePage(pRoot);
  2232.         return rc;
  2233.       }
  2234.       assert( eType!=PTRMAP_ROOTPAGE );
  2235.       assert( eType!=PTRMAP_FREEPAGE );
  2236.       rc = sqlite3PagerWrite(pRoot->pDbPage);
  2237.       if( rc!=SQLITE_OK ){
  2238.         releasePage(pRoot);
  2239.         return rc;
  2240.       }
  2241.       rc = relocatePage(pBt, pRoot, eType, iPtrPage, pgnoMove);
  2242.       releasePage(pRoot);
  2243.       /* Obtain the page at pgnoRoot */
  2244.       if( rc!=SQLITE_OK ){
  2245.         return rc;
  2246.       }
  2247.       rc = sqlite3BtreeGetPage(pBt, pgnoRoot, &pRoot, 0);
  2248.       if( rc!=SQLITE_OK ){
  2249.         return rc;
  2250.       }
  2251.       rc = sqlite3PagerWrite(pRoot->pDbPage);
  2252.       if( rc!=SQLITE_OK ){
  2253.         releasePage(pRoot);
  2254.         return rc;
  2255.       }
  2256.     }else{
  2257.       pRoot = pPageMove;
  2258.     } 
  2259.     /* Update the pointer-map and meta-data with the new root-page number. */
  2260.     rc = ptrmapPut(pBt, pgnoRoot, PTRMAP_ROOTPAGE, 0);
  2261.     if( rc ){
  2262.       releasePage(pRoot);
  2263.       return rc;
  2264.     }
  2265.     rc = sqlite3BtreeUpdateMeta(p, 4, pgnoRoot);
  2266.     if( rc ){
  2267.       releasePage(pRoot);
  2268.       return rc;
  2269.     }
  2270.   }else{
  2271.     rc = allocateBtreePage(pBt, &pRoot, &pgnoRoot, 1, 0);
  2272.     if( rc ) return rc;
  2273.   }
  2274. #endif
  2275.   assert( sqlite3PagerIswriteable(pRoot->pDbPage) );
  2276.   zeroPage(pRoot, flags | PTF_LEAF);
  2277.   sqlite3PagerUnref(pRoot->pDbPage);
  2278.   *piTable = (int)pgnoRoot;
  2279.   return SQLITE_OK;
  2280. }
  2281. int sqlite3BtreeCreateTable(Btree *p, int *piTable, int flags){
  2282.   int rc;
  2283.   sqlite3BtreeEnter(p);
  2284.   p->pBt->db = p->db;
  2285.   rc = btreeCreateTable(p, piTable, flags);
  2286.   sqlite3BtreeLeave(p);
  2287.   return rc;
  2288. }
  2289. /*
  2290. ** Erase the given database page and all its children.  Return
  2291. ** the page to the freelist.
  2292. */
  2293. static int clearDatabasePage(
  2294.   BtShared *pBt,           /* The BTree that contains the table */
  2295.   Pgno pgno,            /* Page number to clear */
  2296.   MemPage *pParent,     /* Parent page.  NULL for the root */
  2297.   int freePageFlag      /* Deallocate page if true */
  2298. ){
  2299.   MemPage *pPage = 0;
  2300.   int rc;
  2301.   unsigned char *pCell;
  2302.   int i;
  2303.   assert( sqlite3_mutex_held(pBt->mutex) );
  2304.   if( pgno>sqlite3PagerPagecount(pBt->pPager) ){
  2305.     return SQLITE_CORRUPT_BKPT;
  2306.   }
  2307.   rc = getAndInitPage(pBt, pgno, &pPage, pParent);
  2308.   if( rc ) goto cleardatabasepage_out;
  2309.   for(i=0; i<pPage->nCell; i++){
  2310.     pCell = findCell(pPage, i);
  2311.     if( !pPage->leaf ){
  2312.       rc = clearDatabasePage(pBt, get4byte(pCell), pPage->pParent, 1);
  2313.       if( rc ) goto cleardatabasepage_out;
  2314.     }
  2315.     rc = clearCell(pPage, pCell);
  2316.     if( rc ) goto cleardatabasepage_out;
  2317.   }
  2318.   if( !pPage->leaf ){
  2319.     rc = clearDatabasePage(pBt, get4byte(&pPage->aData[8]), pPage->pParent, 1);
  2320.     if( rc ) goto cleardatabasepage_out;
  2321.   }
  2322.   if( freePageFlag ){
  2323.     rc = freePage(pPage);
  2324.   }else if( (rc = sqlite3PagerWrite(pPage->pDbPage))==0 ){
  2325.     zeroPage(pPage, pPage->aData[0] | PTF_LEAF);
  2326.   }
  2327. cleardatabasepage_out:
  2328.   releasePage(pPage);
  2329.   return rc;
  2330. }
  2331. /*
  2332. ** Delete all information from a single table in the database.  iTable is
  2333. ** the page number of the root of the table.  After this routine returns,
  2334. ** the root page is empty, but still exists.
  2335. **
  2336. ** This routine will fail with SQLITE_LOCKED if there are any open
  2337. ** read cursors on the table.  Open write cursors are moved to the
  2338. ** root of the table.
  2339. */
  2340. int sqlite3BtreeClearTable(Btree *p, int iTable){
  2341.   int rc;
  2342.   BtShared *pBt = p->pBt;
  2343.   sqlite3BtreeEnter(p);
  2344.   pBt->db = p->db;
  2345.   if( p->inTrans!=TRANS_WRITE ){
  2346.     rc = pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  2347.   }else if( (rc = checkReadLocks(p, iTable, 0))!=SQLITE_OK ){
  2348.     /* nothing to do */
  2349.   }else if( SQLITE_OK!=(rc = saveAllCursors(pBt, iTable, 0)) ){
  2350.     /* nothing to do */
  2351.   }else{
  2352.     rc = clearDatabasePage(pBt, (Pgno)iTable, 0, 0);
  2353.   }
  2354.   sqlite3BtreeLeave(p);
  2355.   return rc;
  2356. }
  2357. /*
  2358. ** Erase all information in a table and add the root of the table to
  2359. ** the freelist.  Except, the root of the principle table (the one on
  2360. ** page 1) is never added to the freelist.
  2361. **
  2362. ** This routine will fail with SQLITE_LOCKED if there are any open
  2363. ** cursors on the table.
  2364. **
  2365. ** If AUTOVACUUM is enabled and the page at iTable is not the last
  2366. ** root page in the database file, then the last root page 
  2367. ** in the database file is moved into the slot formerly occupied by
  2368. ** iTable and that last slot formerly occupied by the last root page
  2369. ** is added to the freelist instead of iTable.  In this say, all
  2370. ** root pages are kept at the beginning of the database file, which
  2371. ** is necessary for AUTOVACUUM to work right.  *piMoved is set to the 
  2372. ** page number that used to be the last root page in the file before
  2373. ** the move.  If no page gets moved, *piMoved is set to 0.
  2374. ** The last root page is recorded in meta[3] and the value of
  2375. ** meta[3] is updated by this procedure.
  2376. */
  2377. static int btreeDropTable(Btree *p, int iTable, int *piMoved){
  2378.   int rc;
  2379.   MemPage *pPage = 0;
  2380.   BtShared *pBt = p->pBt;
  2381.   assert( sqlite3BtreeHoldsMutex(p) );
  2382.   if( p->inTrans!=TRANS_WRITE ){
  2383.     return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  2384.   }
  2385.   /* It is illegal to drop a table if any cursors are open on the
  2386.   ** database. This is because in auto-vacuum mode the backend may
  2387.   ** need to move another root-page to fill a gap left by the deleted
  2388.   ** root page. If an open cursor was using this page a problem would 
  2389.   ** occur.
  2390.   */
  2391.   if( pBt->pCursor ){
  2392.     return SQLITE_LOCKED;
  2393.   }
  2394.   rc = sqlite3BtreeGetPage(pBt, (Pgno)iTable, &pPage, 0);
  2395.   if( rc ) return rc;
  2396.   rc = sqlite3BtreeClearTable(p, iTable);
  2397.   if( rc ){
  2398.     releasePage(pPage);
  2399.     return rc;
  2400.   }
  2401.   *piMoved = 0;
  2402.   if( iTable>1 ){
  2403. #ifdef SQLITE_OMIT_AUTOVACUUM
  2404.     rc = freePage(pPage);
  2405.     releasePage(pPage);
  2406. #else
  2407.     if( pBt->autoVacuum ){
  2408.       Pgno maxRootPgno;
  2409.       rc = sqlite3BtreeGetMeta(p, 4, &maxRootPgno);
  2410.       if( rc!=SQLITE_OK ){
  2411.         releasePage(pPage);
  2412.         return rc;
  2413.       }
  2414.       if( iTable==maxRootPgno ){
  2415.         /* If the table being dropped is the table with the largest root-page
  2416.         ** number in the database, put the root page on the free list. 
  2417.         */
  2418.         rc = freePage(pPage);
  2419.         releasePage(pPage);
  2420.         if( rc!=SQLITE_OK ){
  2421.           return rc;
  2422.         }
  2423.       }else{
  2424.         /* The table being dropped does not have the largest root-page
  2425.         ** number in the database. So move the page that does into the 
  2426.         ** gap left by the deleted root-page.
  2427.         */
  2428.         MemPage *pMove;
  2429.         releasePage(pPage);
  2430.         rc = sqlite3BtreeGetPage(pBt, maxRootPgno, &pMove, 0);
  2431.         if( rc!=SQLITE_OK ){
  2432.           return rc;
  2433.         }
  2434.         rc = relocatePage(pBt, pMove, PTRMAP_ROOTPAGE, 0, iTable);
  2435.         releasePage(pMove);
  2436.         if( rc!=SQLITE_OK ){
  2437.           return rc;
  2438.         }
  2439.         rc = sqlite3BtreeGetPage(pBt, maxRootPgno, &pMove, 0);
  2440.         if( rc!=SQLITE_OK ){
  2441.           return rc;
  2442.         }
  2443.         rc = freePage(pMove);
  2444.         releasePage(pMove);
  2445.         if( rc!=SQLITE_OK ){
  2446.           return rc;
  2447.         }
  2448.         *piMoved = maxRootPgno;
  2449.       }
  2450.       /* Set the new 'max-root-page' value in the database header. This
  2451.       ** is the old value less one, less one more if that happens to
  2452.       ** be a root-page number, less one again if that is the
  2453.       ** PENDING_BYTE_PAGE.
  2454.       */
  2455.       maxRootPgno--;
  2456.       if( maxRootPgno==PENDING_BYTE_PAGE(pBt) ){
  2457.         maxRootPgno--;
  2458.       }
  2459.       if( maxRootPgno==PTRMAP_PAGENO(pBt, maxRootPgno) ){
  2460.         maxRootPgno--;
  2461.       }
  2462.       assert( maxRootPgno!=PENDING_BYTE_PAGE(pBt) );
  2463.       rc = sqlite3BtreeUpdateMeta(p, 4, maxRootPgno);
  2464.     }else{
  2465.       rc = freePage(pPage);
  2466.       releasePage(pPage);
  2467.     }
  2468. #endif
  2469.   }else{
  2470.     /* If sqlite3BtreeDropTable was called on page 1. */
  2471.     zeroPage(pPage, PTF_INTKEY|PTF_LEAF );
  2472.     releasePage(pPage);
  2473.   }
  2474.   return rc;  
  2475. }
  2476. int sqlite3BtreeDropTable(Btree *p, int iTable, int *piMoved){
  2477.   int rc;
  2478.   sqlite3BtreeEnter(p);
  2479.   p->pBt->db = p->db;
  2480.   rc = btreeDropTable(p, iTable, piMoved);
  2481.   sqlite3BtreeLeave(p);
  2482.   return rc;
  2483. }
  2484. /*
  2485. ** Read the meta-information out of a database file.  Meta[0]
  2486. ** is the number of free pages currently in the database.  Meta[1]
  2487. ** through meta[15] are available for use by higher layers.  Meta[0]
  2488. ** is read-only, the others are read/write.
  2489. ** 
  2490. ** The schema layer numbers meta values differently.  At the schema
  2491. ** layer (and the SetCookie and ReadCookie opcodes) the number of
  2492. ** free pages is not visible.  So Cookie[0] is the same as Meta[1].
  2493. */
  2494. int sqlite3BtreeGetMeta(Btree *p, int idx, u32 *pMeta){
  2495.   DbPage *pDbPage;
  2496.   int rc;
  2497.   unsigned char *pP1;
  2498.   BtShared *pBt = p->pBt;
  2499.   sqlite3BtreeEnter(p);
  2500.   pBt->db = p->db;
  2501.   /* Reading a meta-data value requires a read-lock on page 1 (and hence
  2502.   ** the sqlite_master table. We grab this lock regardless of whether or
  2503.   ** not the SQLITE_ReadUncommitted flag is set (the table rooted at page
  2504.   ** 1 is treated as a special case by queryTableLock() and lockTable()).
  2505.   */
  2506.   rc = queryTableLock(p, 1, READ_LOCK);
  2507.   if( rc!=SQLITE_OK ){
  2508.     sqlite3BtreeLeave(p);
  2509.     return rc;
  2510.   }
  2511.   assert( idx>=0 && idx<=15 );
  2512.   rc = sqlite3PagerGet(pBt->pPager, 1, &pDbPage);
  2513.   if( rc ){
  2514.     sqlite3BtreeLeave(p);
  2515.     return rc;
  2516.   }
  2517.   pP1 = (unsigned char *)sqlite3PagerGetData(pDbPage);
  2518.   *pMeta = get4byte(&pP1[36 + idx*4]);
  2519.   sqlite3PagerUnref(pDbPage);
  2520.   /* If autovacuumed is disabled in this build but we are trying to 
  2521.   ** access an autovacuumed database, then make the database readonly. 
  2522.   */
  2523. #ifdef SQLITE_OMIT_AUTOVACUUM
  2524.   if( idx==4 && *pMeta>0 ) pBt->readOnly = 1;
  2525. #endif
  2526.   /* Grab the read-lock on page 1. */
  2527.   rc = lockTable(p, 1, READ_LOCK);
  2528.   sqlite3BtreeLeave(p);
  2529.   return rc;
  2530. }
  2531. /*
  2532. ** Write meta-information back into the database.  Meta[0] is
  2533. ** read-only and may not be written.
  2534. */
  2535. int sqlite3BtreeUpdateMeta(Btree *p, int idx, u32 iMeta){
  2536.   BtShared *pBt = p->pBt;
  2537.   unsigned char *pP1;
  2538.   int rc;
  2539.   assert( idx>=1 && idx<=15 );
  2540.   sqlite3BtreeEnter(p);
  2541.   pBt->db = p->db;
  2542.   if( p->inTrans!=TRANS_WRITE ){
  2543.     rc = pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  2544.   }else{
  2545.     assert( pBt->pPage1!=0 );
  2546.     pP1 = pBt->pPage1->aData;
  2547.     rc = sqlite3PagerWrite(pBt->pPage1->pDbPage);
  2548.     if( rc==SQLITE_OK ){
  2549.       put4byte(&pP1[36 + idx*4], iMeta);
  2550. #ifndef SQLITE_OMIT_AUTOVACUUM
  2551.       if( idx==7 ){
  2552.         assert( pBt->autoVacuum || iMeta==0 );
  2553.         assert( iMeta==0 || iMeta==1 );
  2554.         pBt->incrVacuum = iMeta;
  2555.       }
  2556. #endif
  2557.     }
  2558.   }
  2559.   sqlite3BtreeLeave(p);
  2560.   return rc;
  2561. }
  2562. /*
  2563. ** Return the flag byte at the beginning of the page that the cursor
  2564. ** is currently pointing to.
  2565. */
  2566. int sqlite3BtreeFlags(BtCursor *pCur){
  2567.   /* TODO: What about CURSOR_REQUIRESEEK state? Probably need to call
  2568.   ** restoreOrClearCursorPosition() here.
  2569.   */
  2570.   MemPage *pPage;
  2571.   restoreOrClearCursorPosition(pCur);
  2572.   pPage = pCur->pPage;
  2573.   assert( cursorHoldsMutex(pCur) );
  2574.   assert( pPage->pBt==pCur->pBt );
  2575.   return pPage ? pPage->aData[pPage->hdrOffset] : 0;
  2576. }
  2577. /*
  2578. ** Return the pager associated with a BTree.  This routine is used for
  2579. ** testing and debugging only.
  2580. */
  2581. Pager *sqlite3BtreePager(Btree *p){
  2582.   return p->pBt->pPager;
  2583. }
  2584. #ifndef SQLITE_OMIT_INTEGRITY_CHECK
  2585. /*
  2586. ** Append a message to the error message string.
  2587. */
  2588. static void checkAppendMsg(
  2589.   IntegrityCk *pCheck,
  2590.   char *zMsg1,
  2591.   const char *zFormat,
  2592.   ...
  2593. ){
  2594.   va_list ap;
  2595.   char *zMsg2;
  2596.   if( !pCheck->mxErr ) return;
  2597.   pCheck->mxErr--;
  2598.   pCheck->nErr++;
  2599.   va_start(ap, zFormat);
  2600.   zMsg2 = sqlite3VMPrintf(0, zFormat, ap);
  2601.   va_end(ap);
  2602.   if( zMsg1==0 ) zMsg1 = "";
  2603.   if( pCheck->zErrMsg ){
  2604.     char *zOld = pCheck->zErrMsg;
  2605.     pCheck->zErrMsg = 0;
  2606.     sqlite3SetString(&pCheck->zErrMsg, zOld, "n", zMsg1, zMsg2, (char*)0);
  2607.     sqlite3_free(zOld);
  2608.   }else{
  2609.     sqlite3SetString(&pCheck->zErrMsg, zMsg1, zMsg2, (char*)0);
  2610.   }
  2611.   sqlite3_free(zMsg2);
  2612. }
  2613. #endif /* SQLITE_OMIT_INTEGRITY_CHECK */
  2614. #ifndef SQLITE_OMIT_INTEGRITY_CHECK
  2615. /*
  2616. ** Add 1 to the reference count for page iPage.  If this is the second
  2617. ** reference to the page, add an error message to pCheck->zErrMsg.
  2618. ** Return 1 if there are 2 ore more references to the page and 0 if
  2619. ** if this is the first reference to the page.
  2620. **
  2621. ** Also check that the page number is in bounds.
  2622. */
  2623. static int checkRef(IntegrityCk *pCheck, int iPage, char *zContext){
  2624.   if( iPage==0 ) return 1;
  2625.   if( iPage>pCheck->nPage || iPage<0 ){
  2626.     checkAppendMsg(pCheck, zContext, "invalid page number %d", iPage);
  2627.     return 1;
  2628.   }
  2629.   if( pCheck->anRef[iPage]==1 ){
  2630.     checkAppendMsg(pCheck, zContext, "2nd reference to page %d", iPage);
  2631.     return 1;
  2632.   }
  2633.   return  (pCheck->anRef[iPage]++)>1;
  2634. }
  2635. #ifndef SQLITE_OMIT_AUTOVACUUM
  2636. /*
  2637. ** Check that the entry in the pointer-map for page iChild maps to 
  2638. ** page iParent, pointer type ptrType. If not, append an error message
  2639. ** to pCheck.
  2640. */
  2641. static void checkPtrmap(
  2642.   IntegrityCk *pCheck,   /* Integrity check context */
  2643.   Pgno iChild,           /* Child page number */
  2644.   u8 eType,              /* Expected pointer map type */
  2645.   Pgno iParent,          /* Expected pointer map parent page number */
  2646.   char *zContext         /* Context description (used for error msg) */
  2647. ){
  2648.   int rc;
  2649.   u8 ePtrmapType;
  2650.   Pgno iPtrmapParent;
  2651.   rc = ptrmapGet(pCheck->pBt, iChild, &ePtrmapType, &iPtrmapParent);
  2652.   if( rc!=SQLITE_OK ){
  2653.     checkAppendMsg(pCheck, zContext, "Failed to read ptrmap key=%d", iChild);
  2654.     return;
  2655.   }
  2656.   if( ePtrmapType!=eType || iPtrmapParent!=iParent ){
  2657.     checkAppendMsg(pCheck, zContext, 
  2658.       "Bad ptr map entry key=%d expected=(%d,%d) got=(%d,%d)", 
  2659.       iChild, eType, iParent, ePtrmapType, iPtrmapParent);
  2660.   }
  2661. }
  2662. #endif
  2663. /*
  2664. ** Check the integrity of the freelist or of an overflow page list.
  2665. ** Verify that the number of pages on the list is N.
  2666. */
  2667. static void checkList(
  2668.   IntegrityCk *pCheck,  /* Integrity checking context */
  2669.   int isFreeList,       /* True for a freelist.  False for overflow page list */
  2670.   int iPage,            /* Page number for first page in the list */
  2671.   int N,                /* Expected number of pages in the list */
  2672.   char *zContext        /* Context for error messages */
  2673. ){
  2674.   int i;
  2675.   int expected = N;
  2676.   int iFirst = iPage;
  2677.   while( N-- > 0 && pCheck->mxErr ){
  2678.     DbPage *pOvflPage;
  2679.     unsigned char *pOvflData;
  2680.     if( iPage<1 ){
  2681.       checkAppendMsg(pCheck, zContext,
  2682.          "%d of %d pages missing from overflow list starting at %d",
  2683.           N+1, expected, iFirst);
  2684.       break;
  2685.     }
  2686.     if( checkRef(pCheck, iPage, zContext) ) break;
  2687.     if( sqlite3PagerGet(pCheck->pPager, (Pgno)iPage, &pOvflPage) ){
  2688.       checkAppendMsg(pCheck, zContext, "failed to get page %d", iPage);
  2689.       break;
  2690.     }
  2691.     pOvflData = (unsigned char *)sqlite3PagerGetData(pOvflPage);
  2692.     if( isFreeList ){
  2693.       int n = get4byte(&pOvflData[4]);
  2694. #ifndef SQLITE_OMIT_AUTOVACUUM
  2695.       if( pCheck->pBt->autoVacuum ){
  2696.         checkPtrmap(pCheck, iPage, PTRMAP_FREEPAGE, 0, zContext);
  2697.       }
  2698. #endif
  2699.       if( n>pCheck->pBt->usableSize/4-8 ){
  2700.         checkAppendMsg(pCheck, zContext,
  2701.            "freelist leaf count too big on page %d", iPage);
  2702.         N--;
  2703.       }else{
  2704.         for(i=0; i<n; i++){
  2705.           Pgno iFreePage = get4byte(&pOvflData[8+i*4]);
  2706. #ifndef SQLITE_OMIT_AUTOVACUUM
  2707.           if( pCheck->pBt->autoVacuum ){
  2708.             checkPtrmap(pCheck, iFreePage, PTRMAP_FREEPAGE, 0, zContext);
  2709.           }
  2710. #endif
  2711.           checkRef(pCheck, iFreePage, zContext);
  2712.         }
  2713.         N -= n;
  2714.       }
  2715.     }
  2716. #ifndef SQLITE_OMIT_AUTOVACUUM
  2717.     else{
  2718.       /* If this database supports auto-vacuum and iPage is not the last
  2719.       ** page in this overflow list, check that the pointer-map entry for
  2720.       ** the following page matches iPage.
  2721.       */
  2722.       if( pCheck->pBt->autoVacuum && N>0 ){
  2723.         i = get4byte(pOvflData);
  2724.         checkPtrmap(pCheck, i, PTRMAP_OVERFLOW2, iPage, zContext);
  2725.       }
  2726.     }
  2727. #endif
  2728.     iPage = get4byte(pOvflData);
  2729.     sqlite3PagerUnref(pOvflPage);
  2730.   }
  2731. }
  2732. #endif /* SQLITE_OMIT_INTEGRITY_CHECK */
  2733. #ifndef SQLITE_OMIT_INTEGRITY_CHECK
  2734. /*
  2735. ** Do various sanity checks on a single page of a tree.  Return
  2736. ** the tree depth.  Root pages return 0.  Parents of root pages
  2737. ** return 1, and so forth.
  2738. ** 
  2739. ** These checks are done:
  2740. **
  2741. **      1.  Make sure that cells and freeblocks do not overlap
  2742. **          but combine to completely cover the page.
  2743. **  NO  2.  Make sure cell keys are in order.
  2744. **  NO  3.  Make sure no key is less than or equal to zLowerBound.
  2745. **  NO  4.  Make sure no key is greater than or equal to zUpperBound.
  2746. **      5.  Check the integrity of overflow pages.
  2747. **      6.  Recursively call checkTreePage on all children.
  2748. **      7.  Verify that the depth of all children is the same.
  2749. **      8.  Make sure this page is at least 33% full or else it is
  2750. **          the root of the tree.
  2751. */
  2752. static int checkTreePage(
  2753.   IntegrityCk *pCheck,  /* Context for the sanity check */
  2754.   int iPage,            /* Page number of the page to check */
  2755.   MemPage *pParent,     /* Parent page */
  2756.   char *zParentContext  /* Parent context */
  2757. ){
  2758.   MemPage *pPage;
  2759.   int i, rc, depth, d2, pgno, cnt;
  2760.   int hdr, cellStart;
  2761.   int nCell;
  2762.   u8 *data;
  2763.   BtShared *pBt;
  2764.   int usableSize;
  2765.   char zContext[100];
  2766.   char *hit;
  2767.   sqlite3_snprintf(sizeof(zContext), zContext, "Page %d: ", iPage);
  2768.   /* Check that the page exists
  2769.   */
  2770.   pBt = pCheck->pBt;
  2771.   usableSize = pBt->usableSize;
  2772.   if( iPage==0 ) return 0;
  2773.   if( checkRef(pCheck, iPage, zParentContext) ) return 0;
  2774.   if( (rc = sqlite3BtreeGetPage(pBt, (Pgno)iPage, &pPage, 0))!=0 ){
  2775.     checkAppendMsg(pCheck, zContext,
  2776.        "unable to get the page. error code=%d", rc);
  2777.     return 0;
  2778.   }
  2779.   if( (rc = sqlite3BtreeInitPage(pPage, pParent))!=0 ){
  2780.     checkAppendMsg(pCheck, zContext, 
  2781.                    "sqlite3BtreeInitPage() returns error code %d", rc);
  2782.     releasePage(pPage);
  2783.     return 0;
  2784.   }
  2785.   /* Check out all the cells.
  2786.   */
  2787.   depth = 0;
  2788.   for(i=0; i<pPage->nCell && pCheck->mxErr; i++){
  2789.     u8 *pCell;
  2790.     int sz;
  2791.     CellInfo info;
  2792.     /* Check payload overflow pages
  2793.     */
  2794.     sqlite3_snprintf(sizeof(zContext), zContext,
  2795.              "On tree page %d cell %d: ", iPage, i);
  2796.     pCell = findCell(pPage,i);
  2797.     sqlite3BtreeParseCellPtr(pPage, pCell, &info);
  2798.     sz = info.nData;
  2799.     if( !pPage->intKey ) sz += info.nKey;
  2800.     assert( sz==info.nPayload );
  2801.     if( sz>info.nLocal ){
  2802.       int nPage = (sz - info.nLocal + usableSize - 5)/(usableSize - 4);
  2803.       Pgno pgnoOvfl = get4byte(&pCell[info.iOverflow]);
  2804. #ifndef SQLITE_OMIT_AUTOVACUUM
  2805.       if( pBt->autoVacuum ){
  2806.         checkPtrmap(pCheck, pgnoOvfl, PTRMAP_OVERFLOW1, iPage, zContext);
  2807.       }
  2808. #endif
  2809.       checkList(pCheck, 0, pgnoOvfl, nPage, zContext);
  2810.     }
  2811.     /* Check sanity of left child page.
  2812.     */
  2813.     if( !pPage->leaf ){
  2814.       pgno = get4byte(pCell);
  2815. #ifndef SQLITE_OMIT_AUTOVACUUM
  2816.       if( pBt->autoVacuum ){
  2817.         checkPtrmap(pCheck, pgno, PTRMAP_BTREE, iPage, zContext);
  2818.       }
  2819. #endif
  2820.       d2 = checkTreePage(pCheck,pgno,pPage,zContext);
  2821.       if( i>0 && d2!=depth ){
  2822.         checkAppendMsg(pCheck, zContext, "Child page depth differs");
  2823.       }
  2824.       depth = d2;
  2825.     }
  2826.   }
  2827.   if( !pPage->leaf ){
  2828.     pgno = get4byte(&pPage->aData[pPage->hdrOffset+8]);
  2829.     sqlite3_snprintf(sizeof(zContext), zContext, 
  2830.                      "On page %d at right child: ", iPage);
  2831. #ifndef SQLITE_OMIT_AUTOVACUUM
  2832.     if( pBt->autoVacuum ){
  2833.       checkPtrmap(pCheck, pgno, PTRMAP_BTREE, iPage, 0);
  2834.     }
  2835. #endif
  2836.     checkTreePage(pCheck, pgno, pPage, zContext);
  2837.   }
  2838.  
  2839.   /* Check for complete coverage of the page
  2840.   */
  2841.   data = pPage->aData;
  2842.   hdr = pPage->hdrOffset;
  2843.   hit = sqlite3MallocZero( usableSize );
  2844.   if( hit ){
  2845.     memset(hit, 1, get2byte(&data[hdr+5]));
  2846.     nCell = get2byte(&data[hdr+3]);
  2847.     cellStart = hdr + 12 - 4*pPage->leaf;
  2848.     for(i=0; i<nCell; i++){
  2849.       int pc = get2byte(&data[cellStart+i*2]);
  2850.       u16 size = cellSizePtr(pPage, &data[pc]);
  2851.       int j;
  2852.       if( (pc+size-1)>=usableSize || pc<0 ){
  2853.         checkAppendMsg(pCheck, 0, 
  2854.             "Corruption detected in cell %d on page %d",i,iPage,0);
  2855.       }else{
  2856.         for(j=pc+size-1; j>=pc; j--) hit[j]++;
  2857.       }
  2858.     }
  2859.     for(cnt=0, i=get2byte(&data[hdr+1]); i>0 && i<usableSize && cnt<10000; 
  2860.            cnt++){
  2861.       int size = get2byte(&data[i+2]);
  2862.       int j;
  2863.       if( (i+size-1)>=usableSize || i<0 ){
  2864.         checkAppendMsg(pCheck, 0,  
  2865.             "Corruption detected in cell %d on page %d",i,iPage,0);
  2866.       }else{
  2867.         for(j=i+size-1; j>=i; j--) hit[j]++;
  2868.       }
  2869.       i = get2byte(&data[i]);
  2870.     }
  2871.     for(i=cnt=0; i<usableSize; i++){
  2872.       if( hit[i]==0 ){
  2873.         cnt++;
  2874.       }else if( hit[i]>1 ){
  2875.         checkAppendMsg(pCheck, 0,
  2876.           "Multiple uses for byte %d of page %d", i, iPage);
  2877.         break;
  2878.       }
  2879.     }
  2880.     if( cnt!=data[hdr+7] ){
  2881.       checkAppendMsg(pCheck, 0, 
  2882.           "Fragmented space is %d byte reported as %d on page %d",
  2883.           cnt, data[hdr+7], iPage);
  2884.     }
  2885.   }
  2886.   sqlite3_free(hit);
  2887.   releasePage(pPage);
  2888.   return depth+1;
  2889. }
  2890. #endif /* SQLITE_OMIT_INTEGRITY_CHECK */
  2891. #ifndef SQLITE_OMIT_INTEGRITY_CHECK
  2892. /*
  2893. ** This routine does a complete check of the given BTree file.  aRoot[] is
  2894. ** an array of pages numbers were each page number is the root page of
  2895. ** a table.  nRoot is the number of entries in aRoot.
  2896. **
  2897. ** If everything checks out, this routine returns NULL.  If something is
  2898. ** amiss, an error message is written into memory obtained from malloc()
  2899. ** and a pointer to that error message is returned.  The calling function
  2900. ** is responsible for freeing the error message when it is done.
  2901. */
  2902. char *sqlite3BtreeIntegrityCheck(
  2903.   Btree *p,     /* The btree to be checked */
  2904.   int *aRoot,   /* An array of root pages numbers for individual trees */
  2905.   int nRoot,    /* Number of entries in aRoot[] */
  2906.   int mxErr,    /* Stop reporting errors after this many */
  2907.   int *pnErr    /* Write number of errors seen to this variable */
  2908. ){
  2909.   int i;
  2910.   int nRef;
  2911.   IntegrityCk sCheck;
  2912.   BtShared *pBt = p->pBt;
  2913.   sqlite3BtreeEnter(p);
  2914.   pBt->db = p->db;
  2915.   nRef = sqlite3PagerRefcount(pBt->pPager);
  2916.   if( lockBtreeWithRetry(p)!=SQLITE_OK ){
  2917.     sqlite3BtreeLeave(p);
  2918.     return sqlite3StrDup("Unable to acquire a read lock on the database");
  2919.   }
  2920.   sCheck.pBt = pBt;
  2921.   sCheck.pPager = pBt->pPager;
  2922.   sCheck.nPage = sqlite3PagerPagecount(sCheck.pPager);
  2923.   sCheck.mxErr = mxErr;
  2924.   sCheck.nErr = 0;
  2925.   *pnErr = 0;
  2926. #ifndef SQLITE_OMIT_AUTOVACUUM
  2927.   if( pBt->nTrunc!=0 ){
  2928.     sCheck.nPage = pBt->nTrunc;
  2929.   }
  2930. #endif
  2931.   if( sCheck.nPage==0 ){
  2932.     unlockBtreeIfUnused(pBt);
  2933.     sqlite3BtreeLeave(p);
  2934.     return 0;
  2935.   }
  2936.   sCheck.anRef = sqlite3_malloc( (sCheck.nPage+1)*sizeof(sCheck.anRef[0]) );
  2937.   if( !sCheck.anRef ){
  2938.     unlockBtreeIfUnused(pBt);
  2939.     *pnErr = 1;
  2940.     sqlite3BtreeLeave(p);
  2941.     return sqlite3MPrintf(p->db, "Unable to malloc %d bytes", 
  2942.         (sCheck.nPage+1)*sizeof(sCheck.anRef[0]));
  2943.   }
  2944.   for(i=0; i<=sCheck.nPage; i++){ sCheck.anRef[i] = 0; }
  2945.   i = PENDING_BYTE_PAGE(pBt);
  2946.   if( i<=sCheck.nPage ){
  2947.     sCheck.anRef[i] = 1;
  2948.   }
  2949.   sCheck.zErrMsg = 0;
  2950.   /* Check the integrity of the freelist
  2951.   */
  2952.   checkList(&sCheck, 1, get4byte(&pBt->pPage1->aData[32]),
  2953.             get4byte(&pBt->pPage1->aData[36]), "Main freelist: ");
  2954.   /* Check all the tables.
  2955.   */
  2956.   for(i=0; i<nRoot && sCheck.mxErr; i++){
  2957.     if( aRoot[i]==0 ) continue;
  2958. #ifndef SQLITE_OMIT_AUTOVACUUM
  2959.     if( pBt->autoVacuum && aRoot[i]>1 ){
  2960.       checkPtrmap(&sCheck, aRoot[i], PTRMAP_ROOTPAGE, 0, 0);
  2961.     }
  2962. #endif
  2963.     checkTreePage(&sCheck, aRoot[i], 0, "List of tree roots: ");
  2964.   }
  2965.   /* Make sure every page in the file is referenced
  2966.   */
  2967.   for(i=1; i<=sCheck.nPage && sCheck.mxErr; i++){
  2968. #ifdef SQLITE_OMIT_AUTOVACUUM
  2969.     if( sCheck.anRef[i]==0 ){
  2970.       checkAppendMsg(&sCheck, 0, "Page %d is never used", i);
  2971.     }
  2972. #else
  2973.     /* If the database supports auto-vacuum, make sure no tables contain
  2974.     ** references to pointer-map pages.
  2975.     */
  2976.     if( sCheck.anRef[i]==0 && 
  2977.        (PTRMAP_PAGENO(pBt, i)!=i || !pBt->autoVacuum) ){
  2978.       checkAppendMsg(&sCheck, 0, "Page %d is never used", i);
  2979.     }
  2980.     if( sCheck.anRef[i]!=0 && 
  2981.        (PTRMAP_PAGENO(pBt, i)==i && pBt->autoVacuum) ){
  2982.       checkAppendMsg(&sCheck, 0, "Pointer map page %d is referenced", i);
  2983.     }
  2984. #endif
  2985.   }
  2986.   /* Make sure this analysis did not leave any unref() pages
  2987.   */
  2988.   unlockBtreeIfUnused(pBt);
  2989.   if( nRef != sqlite3PagerRefcount(pBt->pPager) ){
  2990.     checkAppendMsg(&sCheck, 0, 
  2991.       "Outstanding page count goes from %d to %d during this analysis",
  2992.       nRef, sqlite3PagerRefcount(pBt->pPager)
  2993.     );
  2994.   }
  2995.   /* Clean  up and report errors.
  2996.   */
  2997.   sqlite3BtreeLeave(p);
  2998.   sqlite3_free(sCheck.anRef);
  2999.   *pnErr = sCheck.nErr;
  3000.   return sCheck.zErrMsg;
  3001. }
  3002. #endif /* SQLITE_OMIT_INTEGRITY_CHECK */
  3003. /*
  3004. ** Return the full pathname of the underlying database file.
  3005. **
  3006. ** The pager filename is invariant as long as the pager is
  3007. ** open so it is safe to access without the BtShared mutex.
  3008. */
  3009. const char *sqlite3BtreeGetFilename(Btree *p){
  3010.   assert( p->pBt->pPager!=0 );
  3011.   return sqlite3PagerFilename(p->pBt->pPager);
  3012. }
  3013. /*
  3014. ** Return the pathname of the directory that contains the database file.
  3015. **
  3016. ** The pager directory name is invariant as long as the pager is
  3017. ** open so it is safe to access without the BtShared mutex.
  3018. */
  3019. const char *sqlite3BtreeGetDirname(Btree *p){
  3020.   assert( p->pBt->pPager!=0 );
  3021.   return sqlite3PagerDirname(p->pBt->pPager);
  3022. }
  3023. /*
  3024. ** Return the pathname of the journal file for this database. The return
  3025. ** value of this routine is the same regardless of whether the journal file
  3026. ** has been created or not.
  3027. **
  3028. ** The pager journal filename is invariant as long as the pager is
  3029. ** open so it is safe to access without the BtShared mutex.
  3030. */
  3031. const char *sqlite3BtreeGetJournalname(Btree *p){
  3032.   assert( p->pBt->pPager!=0 );
  3033.   return sqlite3PagerJournalname(p->pBt->pPager);
  3034. }
  3035. #ifndef SQLITE_OMIT_VACUUM
  3036. /*
  3037. ** Copy the complete content of pBtFrom into pBtTo.  A transaction
  3038. ** must be active for both files.
  3039. **
  3040. ** The size of file pTo may be reduced by this operation.
  3041. ** If anything goes wrong, the transaction on pTo is rolled back. 
  3042. **
  3043. ** If successful, CommitPhaseOne() may be called on pTo before returning. 
  3044. ** The caller should finish committing the transaction on pTo by calling
  3045. ** sqlite3BtreeCommit().
  3046. */
  3047. static int btreeCopyFile(Btree *pTo, Btree *pFrom){
  3048.   int rc = SQLITE_OK;
  3049.   Pgno i;
  3050.   Pgno nFromPage;     /* Number of pages in pFrom */
  3051.   Pgno nToPage;       /* Number of pages in pTo */
  3052.   Pgno nNewPage;      /* Number of pages in pTo after the copy */
  3053.   Pgno iSkip;         /* Pending byte page in pTo */
  3054.   int nToPageSize;    /* Page size of pTo in bytes */
  3055.   int nFromPageSize;  /* Page size of pFrom in bytes */
  3056.   BtShared *pBtTo = pTo->pBt;
  3057.   BtShared *pBtFrom = pFrom->pBt;
  3058.   pBtTo->db = pTo->db;
  3059.   pBtFrom->db = pFrom->db;
  3060.   nToPageSize = pBtTo->pageSize;
  3061.   nFromPageSize = pBtFrom->pageSize;
  3062.   if( pTo->inTrans!=TRANS_WRITE || pFrom->inTrans!=TRANS_WRITE ){
  3063.     return SQLITE_ERROR;
  3064.   }
  3065.   if( pBtTo->pCursor ){
  3066.     return SQLITE_BUSY;
  3067.   }
  3068.   nToPage = sqlite3PagerPagecount(pBtTo->pPager);
  3069.   nFromPage = sqlite3PagerPagecount(pBtFrom->pPager);
  3070.   iSkip = PENDING_BYTE_PAGE(pBtTo);
  3071.   /* Variable nNewPage is the number of pages required to store the
  3072.   ** contents of pFrom using the current page-size of pTo.
  3073.   */
  3074.   nNewPage = ((i64)nFromPage * (i64)nFromPageSize + (i64)nToPageSize - 1) / 
  3075.       (i64)nToPageSize;
  3076.   for(i=1; rc==SQLITE_OK && (i<=nToPage || i<=nNewPage); i++){
  3077.     /* Journal the original page.
  3078.     **
  3079.     ** iSkip is the page number of the locking page (PENDING_BYTE_PAGE)
  3080.     ** in database *pTo (before the copy). This page is never written 
  3081.     ** into the journal file. Unless i==iSkip or the page was not
  3082.     ** present in pTo before the copy operation, journal page i from pTo.
  3083.     */
  3084.     if( i!=iSkip && i<=nToPage ){
  3085.       DbPage *pDbPage;
  3086.       rc = sqlite3PagerGet(pBtTo->pPager, i, &pDbPage);
  3087.       if( rc ){
  3088.         break;
  3089.       }
  3090.       rc = sqlite3PagerWrite(pDbPage);
  3091.       if( rc ){
  3092.         break;
  3093.       }
  3094.       if( i>nFromPage ){
  3095.         /* Yeah.  It seems wierd to call DontWrite() right after Write(). But
  3096.         ** that is because the names of those procedures do not exactly 
  3097.         ** represent what they do.  Write() really means "put this page in the
  3098.         ** rollback journal and mark it as dirty so that it will be written
  3099.         ** to the database file later."  DontWrite() undoes the second part of
  3100.         ** that and prevents the page from being written to the database. The
  3101.         ** page is still on the rollback journal, though.  And that is the 
  3102.         ** whole point of this block: to put pages on the rollback journal. 
  3103.         */
  3104.         sqlite3PagerDontWrite(pDbPage);
  3105.       }
  3106.       sqlite3PagerUnref(pDbPage);
  3107.     }
  3108.     /* Overwrite the data in page i of the target database */
  3109.     if( rc==SQLITE_OK && i!=iSkip && i<=nNewPage ){
  3110.       DbPage *pToPage = 0;
  3111.       sqlite3_int64 iOff;
  3112.       rc = sqlite3PagerGet(pBtTo->pPager, i, &pToPage);
  3113.       if( rc==SQLITE_OK ){
  3114.         rc = sqlite3PagerWrite(pToPage);
  3115.       }
  3116.       for(
  3117.         iOff=(i-1)*nToPageSize; 
  3118.         rc==SQLITE_OK && iOff<i*nToPageSize; 
  3119.         iOff += nFromPageSize
  3120.       ){
  3121.         DbPage *pFromPage = 0;
  3122.         Pgno iFrom = (iOff/nFromPageSize)+1;
  3123.         if( iFrom==PENDING_BYTE_PAGE(pBtFrom) ){
  3124.           continue;
  3125.         }
  3126.         rc = sqlite3PagerGet(pBtFrom->pPager, iFrom, &pFromPage);
  3127.         if( rc==SQLITE_OK ){
  3128.           char *zTo = sqlite3PagerGetData(pToPage);
  3129.           char *zFrom = sqlite3PagerGetData(pFromPage);
  3130.           int nCopy;
  3131.           if( nFromPageSize>=nToPageSize ){
  3132.             zFrom += ((i-1)*nToPageSize - ((iFrom-1)*nFromPageSize));
  3133.             nCopy = nToPageSize;
  3134.           }else{
  3135.             zTo += (((iFrom-1)*nFromPageSize) - (i-1)*nToPageSize);
  3136.             nCopy = nFromPageSize;
  3137.           }
  3138.           memcpy(zTo, zFrom, nCopy);
  3139.   sqlite3PagerUnref(pFromPage);
  3140.         }
  3141.       }
  3142.       if( pToPage ) sqlite3PagerUnref(pToPage);
  3143.     }
  3144.   }
  3145.   /* If things have worked so far, the database file may need to be 
  3146.   ** truncated. The complex part is that it may need to be truncated to
  3147.   ** a size that is not an integer multiple of nToPageSize - the current
  3148.   ** page size used by the pager associated with B-Tree pTo.
  3149.   **
  3150.   ** For example, say the page-size of pTo is 2048 bytes and the original 
  3151.   ** number of pages is 5 (10 KB file). If pFrom has a page size of 1024 
  3152.   ** bytes and 9 pages, then the file needs to be truncated to 9KB.
  3153.   */
  3154.   if( rc==SQLITE_OK ){
  3155.     if( nFromPageSize!=nToPageSize ){
  3156.       sqlite3_file *pFile = sqlite3PagerFile(pBtTo->pPager);
  3157.       i64 iSize = (i64)nFromPageSize * (i64)nFromPage;
  3158.       i64 iNow = (i64)((nToPage>nNewPage)?nToPage:nNewPage) * (i64)nToPageSize; 
  3159.       i64 iPending = ((i64)PENDING_BYTE_PAGE(pBtTo)-1) *(i64)nToPageSize;
  3160.   
  3161.       assert( iSize<=iNow );
  3162.   
  3163.       /* Commit phase one syncs the journal file associated with pTo 
  3164.       ** containing the original data. It does not sync the database file
  3165.       ** itself. After doing this it is safe to use OsTruncate() and other
  3166.       ** file APIs on the database file directly.
  3167.       */
  3168.       pBtTo->db = pTo->db;
  3169.       rc = sqlite3PagerCommitPhaseOne(pBtTo->pPager, 0, 0, 1);
  3170.       if( iSize<iNow && rc==SQLITE_OK ){
  3171.         rc = sqlite3OsTruncate(pFile, iSize);
  3172.       }
  3173.   
  3174.       /* The loop that copied data from database pFrom to pTo did not
  3175.       ** populate the locking page of database pTo. If the page-size of
  3176.       ** pFrom is smaller than that of pTo, this means some data will
  3177.       ** not have been copied. 
  3178.       **
  3179.       ** This block copies the missing data from database pFrom to pTo 
  3180.       ** using file APIs. This is safe because at this point we know that
  3181.       ** all of the original data from pTo has been synced into the 
  3182.       ** journal file. At this point it would be safe to do anything at
  3183.       ** all to the database file except truncate it to zero bytes.
  3184.       */
  3185.       if( rc==SQLITE_OK && nFromPageSize<nToPageSize && iSize>iPending){
  3186.         i64 iOff;
  3187.         for(
  3188.           iOff=iPending; 
  3189.           rc==SQLITE_OK && iOff<(iPending+nToPageSize); 
  3190.           iOff += nFromPageSize
  3191.         ){
  3192.           DbPage *pFromPage = 0;
  3193.           Pgno iFrom = (iOff/nFromPageSize)+1;
  3194.   
  3195.           if( iFrom==PENDING_BYTE_PAGE(pBtFrom) || iFrom>nFromPage ){
  3196.             continue;
  3197.           }
  3198.   
  3199.           rc = sqlite3PagerGet(pBtFrom->pPager, iFrom, &pFromPage);
  3200.           if( rc==SQLITE_OK ){
  3201.             char *zFrom = sqlite3PagerGetData(pFromPage);
  3202.      rc = sqlite3OsWrite(pFile, zFrom, nFromPageSize, iOff);
  3203.             sqlite3PagerUnref(pFromPage);
  3204.           }
  3205.         }
  3206.       }
  3207.   
  3208.       /* Sync the database file */
  3209.       if( rc==SQLITE_OK ){
  3210.         rc = sqlite3PagerSync(pBtTo->pPager);
  3211.       }
  3212.     }else{
  3213.       rc = sqlite3PagerTruncate(pBtTo->pPager, nNewPage);
  3214.     }
  3215.     if( rc==SQLITE_OK ){
  3216.       pBtTo->pageSizeFixed = 0;
  3217.     }
  3218.   }
  3219.   if( rc ){
  3220.     sqlite3BtreeRollback(pTo);
  3221.   }
  3222.   return rc;  
  3223. }
  3224. int sqlite3BtreeCopyFile(Btree *pTo, Btree *pFrom){
  3225.   int rc;
  3226.   sqlite3BtreeEnter(pTo);
  3227.   sqlite3BtreeEnter(pFrom);
  3228.   rc = btreeCopyFile(pTo, pFrom);
  3229.   sqlite3BtreeLeave(pFrom);
  3230.   sqlite3BtreeLeave(pTo);
  3231.   return rc;
  3232. }
  3233. #endif /* SQLITE_OMIT_VACUUM */
  3234. /*
  3235. ** Return non-zero if a transaction is active.
  3236. */
  3237. int sqlite3BtreeIsInTrans(Btree *p){
  3238.   assert( p==0 || sqlite3_mutex_held(p->db->mutex) );
  3239.   return (p && (p->inTrans==TRANS_WRITE));
  3240. }
  3241. /*
  3242. ** Return non-zero if a statement transaction is active.
  3243. */
  3244. int sqlite3BtreeIsInStmt(Btree *p){
  3245.   assert( sqlite3BtreeHoldsMutex(p) );
  3246.   return (p->pBt && p->pBt->inStmt);
  3247. }
  3248. /*
  3249. ** Return non-zero if a read (or write) transaction is active.
  3250. */
  3251. int sqlite3BtreeIsInReadTrans(Btree *p){
  3252.   assert( sqlite3_mutex_held(p->db->mutex) );
  3253.   return (p && (p->inTrans!=TRANS_NONE));
  3254. }
  3255. /*
  3256. ** This function returns a pointer to a blob of memory associated with
  3257. ** a single shared-btree. The memory is used by client code for its own
  3258. ** purposes (for example, to store a high-level schema associated with 
  3259. ** the shared-btree). The btree layer manages reference counting issues.
  3260. **
  3261. ** The first time this is called on a shared-btree, nBytes bytes of memory
  3262. ** are allocated, zeroed, and returned to the caller. For each subsequent 
  3263. ** call the nBytes parameter is ignored and a pointer to the same blob
  3264. ** of memory returned. 
  3265. **
  3266. ** Just before the shared-btree is closed, the function passed as the 
  3267. ** xFree argument when the memory allocation was made is invoked on the 
  3268. ** blob of allocated memory. This function should not call sqlite3_free()
  3269. ** on the memory, the btree layer does that.
  3270. */
  3271. void *sqlite3BtreeSchema(Btree *p, int nBytes, void(*xFree)(void *)){
  3272.   BtShared *pBt = p->pBt;
  3273.   sqlite3BtreeEnter(p);
  3274.   if( !pBt->pSchema ){
  3275.     pBt->pSchema = sqlite3MallocZero(nBytes);
  3276.     pBt->xFreeSchema = xFree;
  3277.   }
  3278.   sqlite3BtreeLeave(p);
  3279.   return pBt->pSchema;
  3280. }
  3281. /*
  3282. ** Return true if another user of the same shared btree as the argument
  3283. ** handle holds an exclusive lock on the sqlite_master table.
  3284. */
  3285. int sqlite3BtreeSchemaLocked(Btree *p){
  3286.   int rc;
  3287.   assert( sqlite3_mutex_held(p->db->mutex) );
  3288.   sqlite3BtreeEnter(p);
  3289.   rc = (queryTableLock(p, MASTER_ROOT, READ_LOCK)!=SQLITE_OK);
  3290.   sqlite3BtreeLeave(p);
  3291.   return rc;
  3292. }
  3293. #ifndef SQLITE_OMIT_SHARED_CACHE
  3294. /*
  3295. ** Obtain a lock on the table whose root page is iTab.  The
  3296. ** lock is a write lock if isWritelock is true or a read lock
  3297. ** if it is false.
  3298. */
  3299. int sqlite3BtreeLockTable(Btree *p, int iTab, u8 isWriteLock){
  3300.   int rc = SQLITE_OK;
  3301.   if( p->sharable ){
  3302.     u8 lockType = READ_LOCK + isWriteLock;
  3303.     assert( READ_LOCK+1==WRITE_LOCK );
  3304.     assert( isWriteLock==0 || isWriteLock==1 );
  3305.     sqlite3BtreeEnter(p);
  3306.     rc = queryTableLock(p, iTab, lockType);
  3307.     if( rc==SQLITE_OK ){
  3308.       rc = lockTable(p, iTab, lockType);
  3309.     }
  3310.     sqlite3BtreeLeave(p);
  3311.   }
  3312.   return rc;
  3313. }
  3314. #endif
  3315. #ifndef SQLITE_OMIT_INCRBLOB
  3316. /*
  3317. ** Argument pCsr must be a cursor opened for writing on an 
  3318. ** INTKEY table currently pointing at a valid table entry. 
  3319. ** This function modifies the data stored as part of that entry.
  3320. ** Only the data content may only be modified, it is not possible
  3321. ** to change the length of the data stored.
  3322. */
  3323. int sqlite3BtreePutData(BtCursor *pCsr, u32 offset, u32 amt, void *z){
  3324.   assert( cursorHoldsMutex(pCsr) );
  3325.   assert( sqlite3_mutex_held(pCsr->pBtree->db->mutex) );
  3326.   assert(pCsr->isIncrblobHandle);
  3327.   if( pCsr->eState>=CURSOR_REQUIRESEEK ){
  3328.     if( pCsr->eState==CURSOR_FAULT ){
  3329.       return pCsr->skip;
  3330.     }else{
  3331.       return SQLITE_ABORT;
  3332.     }
  3333.   }
  3334.   /* Check some preconditions: 
  3335.   **   (a) the cursor is open for writing,
  3336.   **   (b) there is no read-lock on the table being modified and
  3337.   **   (c) the cursor points at a valid row of an intKey table.
  3338.   */
  3339.   if( !pCsr->wrFlag ){
  3340.     return SQLITE_READONLY;
  3341.   }
  3342.   assert( !pCsr->pBt->readOnly 
  3343.           && pCsr->pBt->inTransaction==TRANS_WRITE );
  3344.   if( checkReadLocks(pCsr->pBtree, pCsr->pgnoRoot, pCsr) ){
  3345.     return SQLITE_LOCKED; /* The table pCur points to has a read lock */
  3346.   }
  3347.   if( pCsr->eState==CURSOR_INVALID || !pCsr->pPage->intKey ){
  3348.     return SQLITE_ERROR;
  3349.   }
  3350.   return accessPayload(pCsr, offset, amt, (unsigned char *)z, 0, 1);
  3351. }
  3352. /* 
  3353. ** Set a flag on this cursor to cache the locations of pages from the 
  3354. ** overflow list for the current row. This is used by cursors opened
  3355. ** for incremental blob IO only.
  3356. **
  3357. ** This function sets a flag only. The actual page location cache
  3358. ** (stored in BtCursor.aOverflow[]) is allocated and used by function
  3359. ** accessPayload() (the worker function for sqlite3BtreeData() and
  3360. ** sqlite3BtreePutData()).
  3361. */
  3362. void sqlite3BtreeCacheOverflow(BtCursor *pCur){
  3363.   assert( cursorHoldsMutex(pCur) );
  3364.   assert( sqlite3_mutex_held(pCur->pBtree->db->mutex) );
  3365.   assert(!pCur->isIncrblobHandle);
  3366.   assert(!pCur->aOverflow);
  3367.   pCur->isIncrblobHandle = 1;
  3368. }
  3369. #endif