/ Check-in [6594f9b4]
Login

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

Overview
Comment:Further work on balance_nonroot().
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | defrag-opt
Files: files | file ages | folders
SHA1: 6594f9b420e2fa642737722ff8521f756ecef227
User & Date: dan 2014-10-13 18:03:27
Context
2014-10-13
18:09
Merge trunk changes into this branch. check-in: d5b7c5a8 user: dan tags: defrag-opt
18:03
Further work on balance_nonroot(). check-in: 6594f9b4 user: dan tags: defrag-opt
2014-10-11
20:00
Attempt to further reduce memcpy() in balance_nonroot(). check-in: fec849dc user: dan tags: defrag-opt
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/btree.c.

6005
6006
6007
6008
6009
6010
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
6089
6090
6091
6092
6093
6094
6095
6096
6097




6098
6099
6100
6101
6102
6103
6104



6105
6106
6107
6108
6109
6110
6111
6112
6113
6114
6115
6116
6117
6118
6119
6120
6121
6122
6123
6124
6125
6126
6127
6128
6129
6130
6131
6132
6133
6134
6135
6136
6137
6138
6139
6140
6141
6142
6143
....
6658
6659
6660
6661
6662
6663
6664
6665
6666
6667
6668
6669
6670
6671
6672
....
6998
6999
7000
7001
7002
7003
7004

7005
7006
7007
7008
7009
7010
7011
    pData -= szCell[i];
    memcpy(pData, pCell, szCell[i]);
    put2byte(pCellptr, (pData - aData));
    pCellptr += 2;
    assert( szCell[i]==cellSizePtr(pPg, pCell) );
  }

  pPg->nFree = (pData - pCellptr);
  pPg->nCell = nCell;
  pPg->nOverflow = 0;

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





































































































static void editPage(
  MemPage *pPg,                   /* Edit this page */
  int iOld,                       /* Index of first cell currently on page */
  int iNew,                       /* Index of new first cell on page */
  int nNew,                       /* Final number of cells on page */
  u8 **apCell,                    /* Array of cells */
  u16 *szCell                     /* Array of cell sizes */
){

  if( 1 ){
    u8 * const aData = pPg->aData;
    const int hdr = pPg->hdrOffset;
    u8 *pBegin = &pPg->aCellIdx[nNew * 2];
    int nFree = pPg->nFree;       /* Free bytes on pPg */
    int nCell = pPg->nCell;       /* Cells stored on pPg */
    u8 *pData;
    u8 *pCellptr;
    int i;
    int iOldEnd = iOld + pPg->nCell + pPg->nOverflow;


#ifdef SQLITE_DEBUG
    u8 *pTmp = sqlite3PagerTempSpace(pPg->pBt->pPager);
    memcpy(pTmp, aData, pPg->pBt->usableSize);
#endif

    /* Remove cells from the start and end of the page */
    if( iOld<iNew ){
      int nShift = 0;
      for(i=iOld; i<iNew; i++){
        if( apCell[i]>aData && apCell[i]<&aData[pPg->pBt->usableSize] ){
          freeSpace(pPg, apCell[i] - aData, szCell[i]);
          nFree += szCell[i] + 2;
          nShift++;
        }
      }
      nCell -= nShift;


      memmove(pPg->aCellIdx, &pPg->aCellIdx[nShift*2], nCell*2);

    }
    for(i=iNew+nNew; i<iOldEnd; i++){
      if( apCell[i]>aData && apCell[i]<&aData[pPg->pBt->usableSize] ){
        freeSpace(pPg, apCell[i] - aData, szCell[i]);
        nFree += szCell[i] + 2;
        nCell--;




      }
    }
    pData = &aData[get2byte(&aData[hdr+5])];
    if( pData<pBegin ) goto editpage_fail;

    /* Add cells to the start of the page */
    if( iNew<iOld ){

      pCellptr = pPg->aCellIdx;
      memmove(&pCellptr[(iOld-iNew)*2], pCellptr, nCell*2);
      for(i=iNew; i<iOld; i++){
        pData -= szCell[i];



        if( pData<pBegin ) goto editpage_fail;
        memcpy(pData, apCell[i], szCell[i]);
        put2byte(pCellptr, (pData - aData));
        pCellptr += 2;
        nFree -= (szCell[i] + 2);
        nCell++;
      }
    }

    /* Add any overflow cells */
    for(i=0; i<pPg->nOverflow; i++){
      int iCell = (iOld + pPg->aiOvfl[i]) - iNew;
      if( iCell>=0 && iCell<nNew ){
        u8 *pCellptr = &pPg->aCellIdx[iCell * 2];
        int sz = szCell[iCell+iNew];
        memmove(&pCellptr[2], pCellptr, (nCell - iCell) * 2);
        pData -= sz;
        if( pData<pBegin ) goto editpage_fail;
        memcpy(pData, apCell[iCell+iNew], sz);
        put2byte(pCellptr, (pData - aData));
        nFree -= (sz + 2);
        nCell++;




      }
    }

    /* Append cells to the end of the page */
    pCellptr = &pPg->aCellIdx[nCell*2];
    for(i=iNew+nCell; i<(iNew+nNew); i++){
      pData -= szCell[i];



      if( pData<pBegin ) goto editpage_fail;
      memcpy(pData, apCell[i], szCell[i]);
      put2byte(pCellptr, (pData - aData));
      pCellptr += 2;
      nFree -= (szCell[i] + 2);
    }

    pPg->nFree = nFree;
    pPg->nCell = nNew;
    pPg->nOverflow = 0;

    put2byte(&aData[hdr+3], pPg->nCell);
    put2byte(&aData[hdr+5], pData - aData);

#ifdef SQLITE_DEBUG
    for(i=0; i<nNew; i++){
      u8 *pCell = apCell[i+iNew];
      int iOff = get2byte(&pPg->aCellIdx[i*2]);
      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]);
}
................................................................................
  ** 
  */
  usableSpace = pBt->usableSize - 12 + leafCorrection;
  for(subtotal=k=i=0; i<nCell; i++){
    assert( i<nMaxCells );
    subtotal += szCell[i] + 2;
    if( subtotal > usableSpace ){
      szNew[k] = subtotal - szCell[i];
      cntNew[k] = i;
      if( leafData ){ i--; }
      subtotal = 0;
      k++;
      if( k>NB+1 ){ rc = SQLITE_CORRUPT_BKPT; goto balance_cleanup; }
    }
  }
................................................................................
        iOld = iPg<nOld ? (cntOld[iPg-1] + !leafData) : nCell;
        iNew = cntNew[iPg-1] + !leafData;
        nNewCell = cntNew[iPg] - iNew;
      }

      editPage(apNew[iPg], iOld, iNew, nNewCell, apCell, szCell);
      abDone[iPg] = 1;

      assert( apNew[iPg]->nOverflow==0 );
      assert( apNew[iPg]->nCell==nNewCell );
    }
  }
  assert( memcmp(abDone, "\01\01\01\01\01", nNew)==0 );

  assert( nOld>0 );







|









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








<
<
|
|
|
<
|
|
|
|
|
>


|
|


|
|
|
<
<
<
<
<
<
<
<
>
>
|
>
|
<
<
<
<
<
>
>
>
>
|
|
|
|

|
|
>
|
|
<
<
>
>
>
|
<
<
<
<
|
|
|
<
|
|
|
|
|
<
|
<
<
<
<
<
|
>
>
>
>
|
|

|
|
<
<
>
>
>
|
<
<
<
<
|
<
<
|
|

|
|


|
|
|
|
|
|
|
|



|


|
<
<







 







|







 







>







6005
6006
6007
6008
6009
6010
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
6089
6090
6091
6092
6093
6094
6095
6096
6097
6098
6099
6100
6101
6102
6103
6104
6105
6106
6107
6108
6109
6110
6111
6112
6113
6114
6115
6116
6117
6118
6119
6120
6121
6122
6123
6124
6125
6126
6127
6128
6129


6130
6131
6132

6133
6134
6135
6136
6137
6138
6139
6140
6141
6142
6143
6144
6145
6146
6147








6148
6149
6150
6151
6152





6153
6154
6155
6156
6157
6158
6159
6160
6161
6162
6163
6164
6165
6166


6167
6168
6169
6170




6171
6172
6173

6174
6175
6176
6177
6178

6179





6180
6181
6182
6183
6184
6185
6186
6187
6188
6189


6190
6191
6192
6193




6194


6195
6196
6197
6198
6199
6200
6201
6202
6203
6204
6205
6206
6207
6208
6209
6210
6211
6212
6213
6214
6215
6216


6217
6218
6219
6220
6221
6222
6223
....
6738
6739
6740
6741
6742
6743
6744
6745
6746
6747
6748
6749
6750
6751
6752
....
7078
7079
7080
7081
7082
7083
7084
7085
7086
7087
7088
7089
7090
7091
7092
    pData -= szCell[i];
    memcpy(pData, pCell, szCell[i]);
    put2byte(pCellptr, (pData - aData));
    pCellptr += 2;
    assert( szCell[i]==cellSizePtr(pPg, pCell) );
  }

  /* The pPg->nFree field is now set incorrectly. The caller will fix it. */
  pPg->nCell = nCell;
  pPg->nOverflow = 0;

  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;
  u8 * const pEnd = &aData[pPg->pBt->usableSize];
  int nRet = 0;
  int i;
  u8 *pFree = 0;
  int szFree = 0;

  for(i=0; i<nCell; i++){
    u8 *pCell = apCell[i];
    if( pCell>aData && pCell<pEnd ){
      int sz = szCell[i];
      if( pFree!=(pCell + sz) ){
        if( pFree ) freeSpace(pPg, pFree - aData, szFree);
        pFree = pCell;
        szFree = sz;
      }else{
        pFree = pCell;
        szFree += sz;
      }
      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 */
  int iOld,                       /* Index of first cell currently on page */
  int iNew,                       /* Index of new first cell on page */
  int nNew,                       /* Final number of cells on page */
  u8 **apCell,                    /* Array of cells */
  u16 *szCell                     /* Array of cell sizes */
){


  u8 * const aData = pPg->aData;
  const int hdr = pPg->hdrOffset;
  u8 *pBegin = &pPg->aCellIdx[nNew * 2];

  int nCell = pPg->nCell;       /* Cells stored on pPg */
  u8 *pData;
  u8 *pCellptr;
  int i;
  int iOldEnd = iOld + pPg->nCell + pPg->nOverflow;
  int iNewEnd = iNew + nNew;

#ifdef SQLITE_DEBUG
  u8 *pTmp = sqlite3PagerTempSpace(pPg->pBt->pPager);
  memcpy(pTmp, aData, pPg->pBt->usableSize);
#endif

  /* Remove cells from the start and end of the page */
  if( iOld<iNew ){
    int nShift = pageFreeArray(








        pPg, iNew-iOld, &apCell[iOld], &szCell[iOld]
    );
    memmove(pPg->aCellIdx, &pPg->aCellIdx[nShift*2], nCell*2);
    nCell -= nShift;
  }





  if( iNewEnd < iOldEnd ){
    nCell -= pageFreeArray(
        pPg, iOldEnd-iNewEnd, &apCell[iNewEnd], &szCell[iNewEnd]
    );
  }

  pData = &aData[get2byte(&aData[hdr+5])];
  if( pData<pBegin ) goto editpage_fail;

  /* Add cells to the start of the page */
  if( iNew<iOld ){
    int nAdd = iOld-iNew;
    pCellptr = pPg->aCellIdx;
    memmove(&pCellptr[nAdd*2], pCellptr, nCell*2);


    if( pageInsertArray(
          pPg, pBegin, &pData, pCellptr,
          nAdd, &apCell[iNew], &szCell[iNew]
    ) ) goto editpage_fail;




    nCell += nAdd;
  }


  /* Add any overflow cells */
  for(i=0; i<pPg->nOverflow; i++){
    int iCell = (iOld + pPg->aiOvfl[i]) - iNew;
    if( iCell>=0 && iCell<nNew ){
      u8 *pCellptr = &pPg->aCellIdx[iCell * 2];

      memmove(&pCellptr[2], pCellptr, (nCell - iCell) * 2);





      nCell++;
      if( pageInsertArray(
            pPg, pBegin, &pData, pCellptr,
            1, &apCell[iCell + iNew], &szCell[iCell + iNew]
      ) ) goto editpage_fail;
    }
  }

  /* Append cells to the end of the page */
  pCellptr = &pPg->aCellIdx[nCell*2];


  if( pageInsertArray(
        pPg, pBegin, &pData, pCellptr,
        nNew-nCell, &apCell[iNew+nCell], &szCell[iNew+nCell]
  ) ) goto editpage_fail;







  pPg->nCell = nNew;
  pPg->nOverflow = 0;

  put2byte(&aData[hdr+3], pPg->nCell);
  put2byte(&aData[hdr+5], pData - aData);

#ifdef SQLITE_DEBUG
  for(i=0; i<nNew; i++){
    u8 *pCell = apCell[i+iNew];
    int iOff = get2byte(&pPg->aCellIdx[i*2]);
    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]);
}
................................................................................
  ** 
  */
  usableSpace = pBt->usableSize - 12 + leafCorrection;
  for(subtotal=k=i=0; i<nCell; i++){
    assert( i<nMaxCells );
    subtotal += szCell[i] + 2;
    if( subtotal > usableSpace ){
      szNew[k] = subtotal - szCell[i] - 2;
      cntNew[k] = i;
      if( leafData ){ i--; }
      subtotal = 0;
      k++;
      if( k>NB+1 ){ rc = SQLITE_CORRUPT_BKPT; goto balance_cleanup; }
    }
  }
................................................................................
        iOld = iPg<nOld ? (cntOld[iPg-1] + !leafData) : nCell;
        iNew = cntNew[iPg-1] + !leafData;
        nNewCell = cntNew[iPg] - iNew;
      }

      editPage(apNew[iPg], iOld, iNew, nNewCell, apCell, szCell);
      abDone[iPg] = 1;
      apNew[iPg]->nFree = usableSpace-szNew[iPg];
      assert( apNew[iPg]->nOverflow==0 );
      assert( apNew[iPg]->nCell==nNewCell );
    }
  }
  assert( memcmp(abDone, "\01\01\01\01\01", nNew)==0 );

  assert( nOld>0 );