Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Further work on balance_nonroot(). |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | defrag-opt |
Files: | files | file ages | folders |
SHA1: |
6594f9b420e2fa642737722ff8521f75 |
User & Date: | dan 2014-10-13 18:03:27.743 |
Context
2014-10-13
| ||
18:09 | Merge trunk changes into this branch. (check-in: d5b7c5a88d user: dan tags: defrag-opt) | |
18:03 | Further work on balance_nonroot(). (check-in: 6594f9b420 user: dan tags: defrag-opt) | |
2014-10-11
| ||
20:00 | Attempt to further reduce memcpy() in balance_nonroot(). (check-in: fec849dcca user: dan tags: defrag-opt) | |
Changes
Changes to src/btree.c.
︙ | ︙ | |||
6005 6006 6007 6008 6009 6010 6011 | pData -= szCell[i]; memcpy(pData, pCell, szCell[i]); put2byte(pCellptr, (pData - aData)); pCellptr += 2; assert( szCell[i]==cellSizePtr(pPg, pCell) ); } | | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > < < | | | < | | | | | > | | | | | < < < | > | < < | < | | < < < | > > | | | | | | > | | < > > | | < < < < | < | | | | | | < | < < < < < | > > > > | | | | > | | | < < < < | < < | | | | | | | | | | | | | | < < | 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 | 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]); } |
︙ | ︙ | |||
6658 6659 6660 6661 6662 6663 6664 | ** */ usableSpace = pBt->usableSize - 12 + leafCorrection; for(subtotal=k=i=0; i<nCell; i++){ assert( i<nMaxCells ); subtotal += szCell[i] + 2; if( subtotal > usableSpace ){ | | | 6738 6739 6740 6741 6742 6743 6744 6745 6746 6747 6748 6749 6750 6751 6752 | ** */ 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; } } } |
︙ | ︙ | |||
6998 6999 7000 7001 7002 7003 7004 7005 7006 7007 7008 7009 7010 7011 | 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 ); | > | 7078 7079 7080 7081 7082 7083 7084 7085 7086 7087 7088 7089 7090 7091 7092 | 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 ); |
︙ | ︙ |