/ Check-in [58d7793b]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Fix some code duplication issues on this branch. Add minor optimizations to the new code.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | defrag-opt
Files: files | file ages | folders
SHA1: 58d7793bd5d608ba9fc3a2cd44b9d9512e0332ba
User & Date: dan 2014-10-14 17:27:04
Context
2014-10-22
18:42
Merge latest trunk with this branch. check-in: 854a54c6 user: dan tags: defrag-opt
2014-10-14
17:27
Fix some code duplication issues on this branch. Add minor optimizations to the new code. check-in: 58d7793b user: dan tags: defrag-opt
2014-10-13
18:09
Merge trunk changes into this branch. check-in: d5b7c5a8 user: dan tags: defrag-opt
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/btree.c.

1219
1220
1221
1222
1223
1224
1225



















































1226
1227
1228
1229
1230
1231
1232
....
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
....
5929
5930
5931
5932
5933
5934
5935
5936
5937









5938
5939
5940
5941
5942
5943
5944
5945
5946
5947
5948
5949
5950
5951
5952
5953
5954
5955
5956
5957
5958
5959
5960
5961
5962
5963
5964
5965
5966
5967
5968
5969
5970
5971
5972
5973
5974
5975
5976
5977
5978
5979
5980
5981
5982
5983
5984
....
5988
5989
5990
5991
5992
5993
5994
5995
5996

5997
5998
5999
6000
6001
6002
6003
....
6012
6013
6014
6015
6016
6017
6018
6019
6020
6021
6022
6023
6024
6025
6026
6027
6028
6029
6030
6031
6032
6033
6034
6035
6036
6037
6038
6039
6040
6041
6042
6043
6044
6045
6046
6047
6048
6049
6050
6051
6052
6053
6054
6055
6056
6057
6058
6059
6060
6061
6062
6063
6064
6065


6066
6067
6068
6069
6070
6071
6072
6073
6074
6075
6076
6077
6078
6079
6080
6081









6082
6083
6084
6085
6086
6087
6088
....
6106
6107
6108
6109
6110
6111
6112
6113
6114
6115
6116
6117
6118
6119
6120
....
6202
6203
6204
6205
6206
6207
6208
6209
6210
6211
6212
6213
6214
6215
6216
6217
6218
6219
6220
6221
6222
6223
6224
....
6284
6285
6286
6287
6288
6289
6290
6291

6292
6293
6294
6295
6296
6297
6298
....
6514
6515
6516
6517
6518
6519
6520
6521
6522
6523
6524
6525
6526
6527
6528
6529
....
6883
6884
6885
6886
6887
6888
6889
6890
6891
6892
6893
6894
6895
6896
6897
6898
6899
6900
6901
6902
6903
6904
6905
6906
6907
6908
6909
6910
6911
6912
6913
6914
6915
6916
6917
6918
6919
6920
6921
6922
6923
6924
6925
6926
6927
6928
6929
6930
6931
6932
6933
6934
6935
6936
6937
6938
6939
....
7043
7044
7045
7046
7047
7048
7049
7050
7051
7052
7053
7054
7055
7056
7057
7058
7059
7060
7061
7062
7063
7064
7065
7066
7067
7068
7069
7070
7071
7072
  memset(&data[iCellFirst], 0, cbrk-iCellFirst);
  assert( sqlite3PagerIswriteable(pPage->pDbPage) );
  if( cbrk-iCellFirst!=pPage->nFree ){
    return SQLITE_CORRUPT_BKPT;
  }
  return SQLITE_OK;
}




















































/*
** Allocate nByte bytes of space from within the B-Tree page passed
** as the first argument. Write into *pIdx the index into pPage->aData[]
** of the first byte of allocated space. Return either SQLITE_OK or
** an error code (usually SQLITE_CORRUPT).
**
................................................................................
  ** array entry offset, and if the freelist is not empty, then search the
  ** freelist looking for a free slot big enough to satisfy the request.
  */
  testcase( gap+2==top );
  testcase( gap+1==top );
  testcase( gap==top );
  if( gap+2<=top && (data[hdr+1] || data[hdr+2]) ){
    int pc, addr;
    for(addr=hdr+1; (pc = get2byte(&data[addr]))>0; addr=pc){
      int size;            /* Size of the free slot */
      if( pc>usableSize-4 || pc<addr+4 ){
        return SQLITE_CORRUPT_BKPT;
      }
      size = get2byte(&data[pc+2]);
      if( size>=nByte ){
        int x = size - nByte;
        testcase( x==4 );
        testcase( x==3 );
        if( x<4 ){
          if( data[hdr+7]>=60 ) goto defragment_page;
          /* Remove the slot from the free-list. Update the number of
          ** fragmented bytes within the page. */
          memcpy(&data[addr], &data[pc], 2);
          data[hdr+7] += (u8)x;
        }else if( size+pc > usableSize ){
          return SQLITE_CORRUPT_BKPT;
        }else{
          /* The slot remains on the free-list. Reduce its size to account
          ** for the portion used by the new allocation. */
          put2byte(&data[pc+2], x);
        }
        *pIdx = pc + x;
        return SQLITE_OK;
      }
    }
  }

  /* The request could not be fulfilled using a freelist slot.  Check
  ** to see if defragmentation is necessary.
  */
  testcase( gap+2+nByte==top );
  if( gap+2+nByte>top ){
defragment_page:
    testcase( pPage->nCell==0 );
    rc = defragmentPage(pPage);
    if( rc ) return rc;
    top = get2byteNotZero(&data[hdr+5]);
    assert( gap+nByte<=top );
  }

................................................................................
      ptrmapPutOvflPtr(pPage, pCell, pRC);
    }
#endif
  }
}

/*
** Add a list of cells to a page.  The page should be initially empty.
** The cells are guaranteed to fit on the page.









*/
static void assemblePage(
  MemPage *pPage,   /* The page to be assembled */
  int nCell,        /* The number of cells to add to this page */
  u8 **apCell,      /* Pointers to cell bodies */
  u16 *aSize        /* Sizes of the cells */
){
  int i;            /* Loop counter */
  u8 *pCellptr;     /* Address of next cell pointer */
  int cellbody;     /* Address of next cell body */
  u8 * const data = pPage->aData;             /* Pointer to data for pPage */
  const int hdr = pPage->hdrOffset;           /* Offset of header on pPage */
  const int nUsable = pPage->pBt->usableSize; /* Usable size of page */

  assert( pPage->nOverflow==0 );
  assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  assert( nCell>=0 && nCell<=(int)MX_CELL(pPage->pBt)
            && (int)MX_CELL(pPage->pBt)<=10921);
  assert( sqlite3PagerIswriteable(pPage->pDbPage) );

  /* Check that the page has just been zeroed by zeroPage() */
  assert( pPage->nCell==0 );
  assert( get2byteNotZero(&data[hdr+5])==nUsable );

  pCellptr = pPage->aCellIdx;
  cellbody = nUsable;
  for(i=0; i<nCell; i++){
    u16 sz = aSize[i];
    cellbody -= sz;
    put2byte(pCellptr, cellbody);
    pCellptr += 2;
    memcpy(&data[cellbody], apCell[i], sz);
  }
  put2byte(&data[hdr+3], nCell);
  put2byte(&data[hdr+5], cellbody);
  pPage->nFree -= (nCell*2 + nUsable - cellbody);
  pPage->nCell = (u16)nCell;
}


static void rebuildPage(
  MemPage *pPg,                   /* Edit this page */
  int nCell,                      /* Final number of cells on page */
  u8 **apCell,                    /* Array of cells */
  u16 *szCell                     /* Array of cell sizes */
){
  const int hdr = pPg->hdrOffset;          /* Offset of header on pPg */
................................................................................
  int i;
  u8 *pCellptr = pPg->aCellIdx;
  u8 *pTmp = sqlite3PagerTempSpace(pPg->pBt->pPager);
  u8 *pData;

  i = get2byte(&aData[hdr+5]);
  memcpy(&pTmp[i], &aData[i], usableSize - i);
  pData = &aData[usableSize];


  for(i=0; i<nCell; i++){
    u8 *pCell = apCell[i];
    if( pCell>aData && pCell<pEnd ){
      pCell = &pTmp[pCell - aData];
    }
    pData -= szCell[i];
    memcpy(pData, pCell, szCell[i]);
................................................................................

  put2byte(&aData[hdr+1], 0);
  put2byte(&aData[hdr+3], pPg->nCell);
  put2byte(&aData[hdr+5], pData - aData);
  aData[hdr+7] = 0x00;
}

static u8 *pageFindSlot(MemPage *pPg, int nByte){
  const int hdr = pPg->hdrOffset;
  u8 * const aData = pPg->aData;
  int iAddr;
  int pc;
  int usableSize = pPg->pBt->usableSize;

  for(iAddr=hdr+1; (pc = get2byte(&aData[iAddr]))>0; iAddr=pc){
    int size;            /* Size of the free slot */
    if( pc>usableSize-4 || pc<iAddr+4 ) return 0;
    size = get2byte(&aData[pc+2]);
    if( size>=nByte ){
      int x = size - nByte;
      testcase( x==4 );
      testcase( x==3 );
      if( x<4 ){
        if( aData[hdr+7]>=60 ) return 0;
        /* Remove the slot from the free-list. Update the number of
         ** fragmented bytes within the page. */
        memcpy(&aData[iAddr], &aData[pc], 2);
        aData[hdr+7] += (u8)x;
      }else if( size+pc > usableSize ){
        return 0;
      }else{
        /* The slot remains on the free-list. Reduce its size to account
         ** for the portion used by the new allocation. */
        put2byte(&aData[pc+2], x);
      }
      return &aData[pc + x];
    }
  }

  return 0;
}

static int pageInsertArray(
  MemPage *pPg,
  u8 *pBegin,
  u8 **ppData, 
  u8 *pCellptr, 
  int nCell,
  u8 **apCell,                    /* Array of cells */
  u16 *szCell                     /* Array of cell sizes */
){
  int i;
  u8 *aData = pPg->aData;
  u8 *pData = *ppData;


  for(i=0; i<nCell; i++){
    int sz = szCell[i];
    u8 *pSlot;
    if( (pSlot = pageFindSlot(pPg, sz))==0 ){
      pData -= sz;
      if( pData<pBegin ) return 1;
      pSlot = pData;
    }
    memcpy(pSlot, apCell[i], sz);
    put2byte(pCellptr, (pSlot - aData));
    pCellptr += 2;
  }
  *ppData = pData;
  return 0;
}










static int pageFreeArray(
  MemPage *pPg,                   /* Page to edit */
  int nCell,                      /* Cells to delete */
  u8 **apCell,                    /* Array of cells */
  u16 *szCell                     /* Array of cell sizes */
){
  u8 * const aData = pPg->aData;
................................................................................
      }
      nRet++;
    }
  }
  if( pFree ) freeSpace(pPg, pFree - aData, szFree);
  return nRet;
}


/*
** The pPg->nFree field is invalid when this function returns. It is the
** responsibility of the caller to set it correctly.
*/
static void editPage(
  MemPage *pPg,                   /* Edit this page */
................................................................................
    if( pCell>=aData && pCell<&aData[pPg->pBt->usableSize] ){
      pCell = &pTmp[pCell - aData];
    }
    assert( 0==memcmp(pCell, &aData[iOff], szCell[i+iNew]) );
  }
#endif

#if 0
printf("EDIT\n");
#endif

  return;
 editpage_fail:
#if 0
  printf("REBUILD\n");
#endif
  /* Unable to edit this page. Rebuild it from scratch instead. */
  rebuildPage(pPg, nNew, &apCell[iNew], &szCell[iNew]);
}

/*
** The following parameters determine how many adjacent pages get involved
** in a balancing operation.  NN is the number of neighbors on either side
................................................................................
    u8 *pCell = pPage->apOvfl[0];
    u16 szCell = cellSizePtr(pPage, pCell);
    u8 *pStop;

    assert( sqlite3PagerIswriteable(pNew->pDbPage) );
    assert( pPage->aData[0]==(PTF_INTKEY|PTF_LEAFDATA|PTF_LEAF) );
    zeroPage(pNew, PTF_INTKEY|PTF_LEAFDATA|PTF_LEAF);
    assemblePage(pNew, 1, &pCell, &szCell);


    /* If this is an auto-vacuum database, update the pointer map
    ** with entries for the new page, and any pointer from the 
    ** cell on the page to an overflow page. If either of these
    ** operations fails, the return code is set, but the contents
    ** of the parent page are still manipulated by thh code below.
    ** That is Ok, at this point the parent page is guaranteed to
................................................................................
  int cntOld[NB+2];            /* Old index in aCell[] after i-th page */
  int szNew[NB+2];             /* Combined size of cells place on i-th page */
  u8 **apCell = 0;             /* All cells begin balanced */
  u16 *szCell;                 /* Local size of all cells in apCell[] */
  u8 *aSpace1;                 /* Space for copies of dividers cells */
  Pgno pgno;                   /* Temp var to store a page number in */

  int aShiftLeft[NB+2];
  int aShiftRight[NB+2];
  u8 abDone[NB+2];
  Pgno aPgno[NB+2];
  u16 aPgFlags[NB+2];

  memset(abDone, 0, sizeof(abDone));
  pBt = pParent->pBt;
  assert( sqlite3_mutex_held(pBt->mutex) );
................................................................................
    nNew>=5 ? apNew[4]->pgno : 0, nNew>=5 ? szNew[4] : 0,
    nNew>=5 ? cntNew[4] - cntNew[3] - !leafData : 0
  ));

  assert( sqlite3PagerIswriteable(pParent->pDbPage) );
  put4byte(pRight, apNew[nNew-1]->pgno);

  j = 0;
  for(i=0; i<nNew; i++){
    /* At this point, "j" is the apCell[] index of the first cell currently
    ** stored on page apNew[i]. Or, if apNew[i] was not one of the original 
    ** sibling pages, "j" should be set to nCell. Variable iFirst is set
    ** to the apCell[] index of the first cell that will appear on the
    ** page following this balancing operation.  */
    int iFirst = (i==0 ? 0 : cntNew[i-1] + !leafData);     /* new first cell */

#if 0
    MemPage *pNew = apNew[i];
    int iCell;
    int nCta = 0;
    int nFree;

    printf("REBUILD %d: %d@%d -> %d@%d", apNew[i]->pgno,
          pNew->nCell+pNew->nOverflow, j,
          cntNew[i] - iFirst, iFirst
    );
    for(iCell=iFirst; iCell<cntNew[i]; iCell++){
      if( apCell[iCell]<pNew->aData 
       || apCell[iCell]>=&pNew->aData[pBt->usableSize] 
      ){
        nCta += szCell[iCell];
      }
    }
    nFree = get2byte(&pNew->aData[pNew->hdrOffset+5]);
    nFree -= (pNew->cellOffset + (cntNew[i] - iFirst) * 2);
    printf(" cta=%d free=%d\n", nCta, nFree);
    if( i==(nNew-1) ){
      printf("-----\n");
      fflush(stdout);
    }
#endif

    assert( i<nOld || j==nCell );
    aShiftLeft[i] = j - iFirst;
    j += apNew[i]->nCell + apNew[i]->nOverflow;
    aShiftRight[i] = cntNew[i] - j;
    assert( i!=nOld-1 || j==nCell );
    if( j<nCell ) j += !leafData;
  }

  /* If the sibling pages are not leaves, ensure that the right-child pointer
  ** of the right-most new sibling page is set to the value that was 
  ** originally in the same field of the right-most old sibling page. */
  if( (pageFlags & PTF_LEAF)==0 && nOld!=nNew ){
    MemPage *pOld = (nNew>nOld ? apNew : apOld)[nOld-1];
    memcpy(&apNew[nNew-1]->aData[8], &pOld->aData[8], 4);
  }
................................................................................
    assert( sqlite3PagerIswriteable(pParent->pDbPage) );
  }

  /* Now update the actual sibling pages. The order in which they are updated
  ** is important, as this code needs to avoid disrupting any page from which
  ** cells may still to be read. In practice, this means:
  **
  **   1) If the aShiftLeft[] entry is less than 0, it is not safe to 
  **      update the page until the page to the left of the current page
  **      (apNew[i-1]) has already been updated.
  **
  **   2) If the aShiftRight[] entry is less than 0, it is not safe to 
  **      update the page until the page to the right of the current page
  **      (apNew[i+1]) has already been updated.
  **
  ** If neither of the above apply, the page is safe to update.
  */
  assert( aShiftRight[nNew-1]>=0 && aShiftLeft[0]==0 );
  for(i=0; i<nNew*2; i++){
    int iPg = (i>=nNew ? i-nNew : nNew-1-i);
    if( abDone[iPg]==0 
     && (aShiftLeft[iPg]>=0 || abDone[iPg-1])
     && (aShiftRight[iPg]>=0 || abDone[iPg+1])
    ){
      int iNew;
      int iOld;
      int nNewCell;

      if( iPg==0 ){
        iNew = iOld = 0;







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







 







|
|
|
<
<
<
<
<
<
<
<
|
<
<
<
<
<
<
<
<
<
<
<
<
|
|
<








<







 







|
|
>
>
>
>
>
>
>
>
>

<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<







 







<

>







 







|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
<
<
<
<
<
<
<
<
<
<






>
>



|












>
>
>
>
>
>
>
>
>







 







<







 







<
<
<
<


<
<
<







 







|
>







 







<
<







 







<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<







 







|
|
|

|
|
|



<



|
|







1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
....
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330








1331












1332
1333

1334
1335
1336
1337
1338
1339
1340
1341

1342
1343
1344
1345
1346
1347
1348
....
5958
5959
5960
5961
5962
5963
5964
5965
5966
5967
5968
5969
5970
5971
5972
5973
5974
5975
5976







































5977
5978
5979
5980
5981
5982
5983
....
5987
5988
5989
5990
5991
5992
5993

5994
5995
5996
5997
5998
5999
6000
6001
6002
....
6011
6012
6013
6014
6015
6016
6017
6018
6019
6020
6021
6022
6023
6024
6025
6026
6027
6028
6029
6030
6031
6032
6033
6034
6035
6036
6037
6038
6039
6040
6041
6042
6043
6044
6045
6046
6047
6048










6049
6050
6051
6052
6053
6054
6055
6056
6057
6058
6059
6060
6061
6062
6063
6064
6065
6066
6067
6068
6069
6070
6071
6072
6073
6074
6075
6076
6077
6078
6079
6080
6081
6082
6083
6084
6085
6086
6087
6088
....
6106
6107
6108
6109
6110
6111
6112

6113
6114
6115
6116
6117
6118
6119
....
6201
6202
6203
6204
6205
6206
6207




6208
6209



6210
6211
6212
6213
6214
6215
6216
....
6276
6277
6278
6279
6280
6281
6282
6283
6284
6285
6286
6287
6288
6289
6290
6291
....
6507
6508
6509
6510
6511
6512
6513


6514
6515
6516
6517
6518
6519
6520
....
6874
6875
6876
6877
6878
6879
6880











































6881
6882
6883
6884
6885
6886
6887
....
6991
6992
6993
6994
6995
6996
6997
6998
6999
7000
7001
7002
7003
7004
7005
7006
7007

7008
7009
7010
7011
7012
7013
7014
7015
7016
7017
7018
7019
  memset(&data[iCellFirst], 0, cbrk-iCellFirst);
  assert( sqlite3PagerIswriteable(pPage->pDbPage) );
  if( cbrk-iCellFirst!=pPage->nFree ){
    return SQLITE_CORRUPT_BKPT;
  }
  return SQLITE_OK;
}

/*
** Search the free-list on page pPg for space to store a cell nByte bytes in
** size. If one can be found, return a pointer to the space and remove it
** from the free-list.
**
** If no suitable space can be found on the free-list, return NULL.
**
** This function may detect corruption within pPg. If it does and argument 
** pRc is non-NULL, then *pRc is set to SQLITE_CORRUPT and NULL is returned.
** Or, if corruption is detected by pRc is NULL, NULL is returned and the
** corruption goes unreported.
*/
static u8 *pageFindSlot(MemPage *pPg, int nByte, int *pRc){
  const int hdr = pPg->hdrOffset;
  u8 * const aData = pPg->aData;
  int iAddr;
  int pc;
  int usableSize = pPg->pBt->usableSize;

  for(iAddr=hdr+1; (pc = get2byte(&aData[iAddr]))>0; iAddr=pc){
    int size;            /* Size of the free slot */
    if( pc>usableSize-4 || pc<iAddr+4 ){
      if( pRc ) *pRc = SQLITE_CORRUPT_BKPT;
      return 0;
    }
    size = get2byte(&aData[pc+2]);
    if( size>=nByte ){
      int x = size - nByte;
      testcase( x==4 );
      testcase( x==3 );
      if( x<4 ){
        if( aData[hdr+7]>=60 ) return 0;
        /* Remove the slot from the free-list. Update the number of
        ** fragmented bytes within the page. */
        memcpy(&aData[iAddr], &aData[pc], 2);
        aData[hdr+7] += (u8)x;
      }else if( size+pc > usableSize ){
        if( pRc ) *pRc = SQLITE_CORRUPT_BKPT;
        return 0;
      }else{
        /* The slot remains on the free-list. Reduce its size to account
         ** for the portion used by the new allocation. */
        put2byte(&aData[pc+2], x);
      }
      return &aData[pc + x];
    }
  }

  return 0;
}

/*
** Allocate nByte bytes of space from within the B-Tree page passed
** as the first argument. Write into *pIdx the index into pPage->aData[]
** of the first byte of allocated space. Return either SQLITE_OK or
** an error code (usually SQLITE_CORRUPT).
**
................................................................................
  ** array entry offset, and if the freelist is not empty, then search the
  ** freelist looking for a free slot big enough to satisfy the request.
  */
  testcase( gap+2==top );
  testcase( gap+1==top );
  testcase( gap==top );
  if( gap+2<=top && (data[hdr+1] || data[hdr+2]) ){
    int rc = SQLITE_OK;
    u8 *pSpace = pageFindSlot(pPage, nByte, &rc);
    if( rc ) return rc;








    if( pSpace ){












      *pIdx = pSpace - data;
      return SQLITE_OK;

    }
  }

  /* The request could not be fulfilled using a freelist slot.  Check
  ** to see if defragmentation is necessary.
  */
  testcase( gap+2+nByte==top );
  if( gap+2+nByte>top ){

    testcase( pPage->nCell==0 );
    rc = defragmentPage(pPage);
    if( rc ) return rc;
    top = get2byteNotZero(&data[hdr+5]);
    assert( gap+nByte<=top );
  }

................................................................................
      ptrmapPutOvflPtr(pPage, pCell, pRC);
    }
#endif
  }
}

/*
** Array apCell[] contains pointers to nCell b-tree page cells. The 
** szCell[] array contains the size in bytes of each cell. This function
** replaces the current contents of page pPg with the contents of the cell
** array.
**
** Some of the cells in apCell[] may currently be stored in pPg. This
** function works around problems caused by this by making a copy of any 
** such cells before overwriting the page data.
**
** The MemPage.nFree field is invalidated by this function. It is the 
** responsibility of the caller to set it correctly.
*/







































static void rebuildPage(
  MemPage *pPg,                   /* Edit this page */
  int nCell,                      /* Final number of cells on page */
  u8 **apCell,                    /* Array of cells */
  u16 *szCell                     /* Array of cell sizes */
){
  const int hdr = pPg->hdrOffset;          /* Offset of header on pPg */
................................................................................
  int i;
  u8 *pCellptr = pPg->aCellIdx;
  u8 *pTmp = sqlite3PagerTempSpace(pPg->pBt->pPager);
  u8 *pData;

  i = get2byte(&aData[hdr+5]);
  memcpy(&pTmp[i], &aData[i], usableSize - i);


  pData = pEnd;
  for(i=0; i<nCell; i++){
    u8 *pCell = apCell[i];
    if( pCell>aData && pCell<pEnd ){
      pCell = &pTmp[pCell - aData];
    }
    pData -= szCell[i];
    memcpy(pData, pCell, szCell[i]);
................................................................................

  put2byte(&aData[hdr+1], 0);
  put2byte(&aData[hdr+3], pPg->nCell);
  put2byte(&aData[hdr+5], pData - aData);
  aData[hdr+7] = 0x00;
}

/*
** Array apCell[] contains nCell pointers to b-tree cells. Array szCell
** contains the size in bytes of each such cell. This function attempts to 
** add the cells stored in the array to page pPg. If it cannot (because 
** the page needs to be defragmented before the cells will fit), non-zero
** is returned. Otherwise, if the cells are added successfully, zero is
** returned.
**
** Argument pCellptr points to the first entry in the cell-pointer array
** (part of page pPg) to populate. After cell apCell[0] is written to the
** page body, a 16-bit offset is written to pCellptr. And so on, for each
** cell in the array. It is the responsibility of the caller to ensure
** that it is safe to overwrite this part of the cell-pointer array.
**
** When this function is called, *ppData points to the start of the 
** content area on page pPg. If the size of the content area is extended,
** *ppData is updated to point to the new start of the content area
** before returning.
**
** Finally, argument pBegin points to the byte immediately following the
** end of the space required by this page for the cell-pointer area (for
** all cells - not just those inserted by the current call). If the content
** area must be extended to before this point in order to accomodate all
** cells in apCell[], then the cells do not fit and non-zero is returned.
*/
static int pageInsertArray(
  MemPage *pPg,                   /* Page to add cells to */
  u8 *pBegin,                     /* End of cell-pointer array */
  u8 **ppData,                    /* IN/OUT: Page content -area pointer */
  u8 *pCellptr,                   /* Pointer to cell-pointer area */
  int nCell,                      /* Number of cells to add to pPg */










  u8 **apCell,                    /* Array of cells */
  u16 *szCell                     /* Array of cell sizes */
){
  int i;
  u8 *aData = pPg->aData;
  u8 *pData = *ppData;
  const int bFreelist = aData[1] || aData[2];
  assert( pPg->hdrOffset==0 );    /* Never called on page 1 */
  for(i=0; i<nCell; i++){
    int sz = szCell[i];
    u8 *pSlot;
    if( bFreelist==0 || (pSlot = pageFindSlot(pPg, sz, 0))==0 ){
      pData -= sz;
      if( pData<pBegin ) return 1;
      pSlot = pData;
    }
    memcpy(pSlot, apCell[i], sz);
    put2byte(pCellptr, (pSlot - aData));
    pCellptr += 2;
  }
  *ppData = pData;
  return 0;
}

/*
** Array apCell[] contains nCell pointers to b-tree cells. Array szCell 
** contains the size in bytes of each such cell. This function adds the
** space associated with each cell in the array that is currently stored 
** within the body of pPg to the pPg free-list. The cell-pointers and other
** fields of the page are not updated.
**
** This function returns the total number of cells added to the free-list.
*/
static int pageFreeArray(
  MemPage *pPg,                   /* Page to edit */
  int nCell,                      /* Cells to delete */
  u8 **apCell,                    /* Array of cells */
  u16 *szCell                     /* Array of cell sizes */
){
  u8 * const aData = pPg->aData;
................................................................................
      }
      nRet++;
    }
  }
  if( pFree ) freeSpace(pPg, pFree - aData, szFree);
  return nRet;
}


/*
** The pPg->nFree field is invalid when this function returns. It is the
** responsibility of the caller to set it correctly.
*/
static void editPage(
  MemPage *pPg,                   /* Edit this page */
................................................................................
    if( pCell>=aData && pCell<&aData[pPg->pBt->usableSize] ){
      pCell = &pTmp[pCell - aData];
    }
    assert( 0==memcmp(pCell, &aData[iOff], szCell[i+iNew]) );
  }
#endif





  return;
 editpage_fail:



  /* Unable to edit this page. Rebuild it from scratch instead. */
  rebuildPage(pPg, nNew, &apCell[iNew], &szCell[iNew]);
}

/*
** The following parameters determine how many adjacent pages get involved
** in a balancing operation.  NN is the number of neighbors on either side
................................................................................
    u8 *pCell = pPage->apOvfl[0];
    u16 szCell = cellSizePtr(pPage, pCell);
    u8 *pStop;

    assert( sqlite3PagerIswriteable(pNew->pDbPage) );
    assert( pPage->aData[0]==(PTF_INTKEY|PTF_LEAFDATA|PTF_LEAF) );
    zeroPage(pNew, PTF_INTKEY|PTF_LEAFDATA|PTF_LEAF);
    rebuildPage(pNew, 1, &pCell, &szCell);
    pNew->nFree = pBt->usableSize - pNew->cellOffset - 2 - szCell;

    /* If this is an auto-vacuum database, update the pointer map
    ** with entries for the new page, and any pointer from the 
    ** cell on the page to an overflow page. If either of these
    ** operations fails, the return code is set, but the contents
    ** of the parent page are still manipulated by thh code below.
    ** That is Ok, at this point the parent page is guaranteed to
................................................................................
  int cntOld[NB+2];            /* Old index in aCell[] after i-th page */
  int szNew[NB+2];             /* Combined size of cells place on i-th page */
  u8 **apCell = 0;             /* All cells begin balanced */
  u16 *szCell;                 /* Local size of all cells in apCell[] */
  u8 *aSpace1;                 /* Space for copies of dividers cells */
  Pgno pgno;                   /* Temp var to store a page number in */



  u8 abDone[NB+2];
  Pgno aPgno[NB+2];
  u16 aPgFlags[NB+2];

  memset(abDone, 0, sizeof(abDone));
  pBt = pParent->pBt;
  assert( sqlite3_mutex_held(pBt->mutex) );
................................................................................
    nNew>=5 ? apNew[4]->pgno : 0, nNew>=5 ? szNew[4] : 0,
    nNew>=5 ? cntNew[4] - cntNew[3] - !leafData : 0
  ));

  assert( sqlite3PagerIswriteable(pParent->pDbPage) );
  put4byte(pRight, apNew[nNew-1]->pgno);












































  /* If the sibling pages are not leaves, ensure that the right-child pointer
  ** of the right-most new sibling page is set to the value that was 
  ** originally in the same field of the right-most old sibling page. */
  if( (pageFlags & PTF_LEAF)==0 && nOld!=nNew ){
    MemPage *pOld = (nNew>nOld ? apNew : apOld)[nOld-1];
    memcpy(&apNew[nNew-1]->aData[8], &pOld->aData[8], 4);
  }
................................................................................
    assert( sqlite3PagerIswriteable(pParent->pDbPage) );
  }

  /* Now update the actual sibling pages. The order in which they are updated
  ** is important, as this code needs to avoid disrupting any page from which
  ** cells may still to be read. In practice, this means:
  **
  **   1) If cells are to be removed from the start of the page and shifted
  **      to the left-hand sibling, it is not safe to update the page until 
  **      the left-hand sibling (apNew[i-1]) has already been updated.
  **
  **   2) If cells are to be removed from the end of the page and shifted
  **      to the right-hand sibling, it is not safe to update the page until 
  **      the right-hand sibling (apNew[i+1]) has already been updated.
  **
  ** If neither of the above apply, the page is safe to update.
  */

  for(i=0; i<nNew*2; i++){
    int iPg = (i>=nNew ? i-nNew : nNew-1-i);
    if( abDone[iPg]==0 
     && (iPg==0 || cntOld[iPg-1]>=cntNew[iPg-1] || abDone[iPg-1])
     && (cntNew[iPg]>=cntOld[iPg] || abDone[iPg+1])
    ){
      int iNew;
      int iOld;
      int nNewCell;

      if( iPg==0 ){
        iNew = iOld = 0;