Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Avoid computing cell sizes in balance_nonroot() until they are really needed. This gives an overall 1.7% performance gain for about 1000 extra bytes of code space. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | btree-opt2 |
Files: | files | file ages | folders |
SHA1: |
43844537e8a372953386663f81772029 |
User & Date: | drh 2015-06-23 02:37:30.513 |
Context
2015-06-23
| ||
13:02 | Merge the compound SELECT operator fix from trunk. (check-in: a7be554f4b user: drh tags: btree-opt2) | |
02:37 | Avoid computing cell sizes in balance_nonroot() until they are really needed. This gives an overall 1.7% performance gain for about 1000 extra bytes of code space. (check-in: 43844537e8 user: drh tags: btree-opt2) | |
2015-06-22
| ||
20:02 | Change the way that balance_nonroot() partitions cells between the sibling pages such that a scan of the cell size array is not required. (check-in: 1687287151 user: drh tags: btree-opt2) | |
Changes
Changes to src/btree.c.
︙ | ︙ | |||
6278 6279 6280 6281 6282 6283 6284 6285 6286 6287 6288 6289 6290 6291 | ** the entry for the overflow page into the pointer map. */ 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. ** | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 6278 6279 6280 6281 6282 6283 6284 6285 6286 6287 6288 6289 6290 6291 6292 6293 6294 6295 6296 6297 6298 6299 6300 6301 6302 6303 6304 6305 6306 6307 6308 6309 6310 6311 6312 6313 6314 6315 6316 6317 6318 6319 6320 6321 6322 6323 6324 6325 6326 6327 6328 6329 6330 6331 6332 6333 6334 6335 6336 6337 | ** the entry for the overflow page into the pointer map. */ ptrmapPutOvflPtr(pPage, pCell, pRC); } #endif } } /* ** A CellArray object contains a cache of pointers and sizes for a ** consecutive sequence of cells that might be held multiple pages. */ typedef struct CellArray CellArray; struct CellArray { int nCell; /* Number of cells in apCell[] */ MemPage *pRef; /* Reference page */ u8 **apCell; /* All cells begin balanced */ u16 *szCell; /* Local size of all cells in apCell[] */ }; /* ** Make sure the cell sizes at idx, idx+1, ..., idx+N-1 have been ** computed. */ static void populateCellCache(CellArray *p, int idx, int N){ assert( idx>=0 && idx+N<=p->nCell ); while( N>0 ){ assert( p->apCell[idx]!=0 ); if( p->szCell[idx]==0 ){ p->szCell[idx] = p->pRef->xCellSize(p->pRef, p->apCell[idx]); }else{ assert( CORRUPT_DB || p->szCell[idx]==p->pRef->xCellSize(p->pRef, p->apCell[idx]) ); } idx++; N--; } } /* ** Return the size of the Nth element of the cell array */ static SQLITE_NOINLINE u16 computeCellSize(CellArray *p, int N){ assert( N>=0 && N<p->nCell ); assert( p->szCell[N]==0 ); p->szCell[N] = p->pRef->xCellSize(p->pRef, p->apCell[N]); return p->szCell[N]; } static u16 cachedCellSize(CellArray *p, int N){ assert( N>=0 && N<p->nCell ); if( p->szCell[N] ) return p->szCell[N]; return computeCellSize(p, N); } /* ** 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. ** |
︙ | ︙ | |||
6458 6459 6460 6461 6462 6463 6464 | ** responsibility of the caller to set it correctly. */ static int 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 */ | | < > > | | > | > > | > | > | | | > > | | 6504 6505 6506 6507 6508 6509 6510 6511 6512 6513 6514 6515 6516 6517 6518 6519 6520 6521 6522 6523 6524 6525 6526 6527 6528 6529 6530 6531 6532 6533 6534 6535 6536 6537 6538 6539 6540 6541 6542 6543 6544 6545 6546 6547 6548 6549 6550 6551 6552 6553 6554 6555 6556 6557 6558 6559 6560 6561 6562 6563 6564 6565 6566 6567 6568 6569 6570 6571 6572 6573 6574 6575 6576 6577 6578 6579 6580 6581 6582 6583 6584 6585 6586 6587 6588 6589 6590 6591 6592 6593 6594 6595 6596 6597 6598 6599 6600 6601 6602 6603 6604 6605 6606 6607 6608 6609 6610 6611 6612 6613 6614 6615 | ** responsibility of the caller to set it correctly. */ static int 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 */ CellArray *pCArray /* Array of cells and 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; populateCellCache(pCArray, iOld, iNew-iOld); nShift = pageFreeArray( pPg, iNew-iOld, &pCArray->apCell[iOld], &pCArray->szCell[iOld] ); memmove(pPg->aCellIdx, &pPg->aCellIdx[nShift*2], nCell*2); nCell -= nShift; } if( iNewEnd < iOldEnd ){ populateCellCache(pCArray, iNewEnd, iOldEnd-iNewEnd); nCell -= pageFreeArray( pPg, iOldEnd-iNewEnd, &pCArray->apCell[iNewEnd], &pCArray->szCell[iNewEnd] ); } pData = &aData[get2byteNotZero(&aData[hdr+5])]; if( pData<pBegin ) goto editpage_fail; /* Add cells to the start of the page */ if( iNew<iOld ){ int nAdd = MIN(nNew,iOld-iNew); assert( (iOld-iNew)<nNew || nCell==0 || CORRUPT_DB ); pCellptr = pPg->aCellIdx; memmove(&pCellptr[nAdd*2], pCellptr, nCell*2); populateCellCache(pCArray, iNew, nAdd); if( pageInsertArray( pPg, pBegin, &pData, pCellptr, nAdd, &pCArray->apCell[iNew], &pCArray->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 ){ pCellptr = &pPg->aCellIdx[iCell * 2]; memmove(&pCellptr[2], pCellptr, (nCell - iCell) * 2); nCell++; (void)cachedCellSize(pCArray, iCell + iNew); if( pageInsertArray( pPg, pBegin, &pData, pCellptr, 1, &pCArray->apCell[iCell + iNew], &pCArray->szCell[iCell + iNew] ) ) goto editpage_fail; } } /* Append cells to the end of the page */ pCellptr = &pPg->aCellIdx[nCell*2]; populateCellCache(pCArray, iNew+nCell, nNew-nCell); if( pageInsertArray( pPg, pBegin, &pData, pCellptr, nNew-nCell, &pCArray->apCell[iNew+nCell], &pCArray->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 && !CORRUPT_DB; i++){ u8 *pCell = pCArray->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], pCArray->pRef->xCellSize(pCArray->pRef, pCArray->apCell[i+iNew])) ); } #endif return SQLITE_OK; editpage_fail: /* Unable to edit this page. Rebuild it from scratch instead. */ populateCellCache(pCArray, iNew, nNew); return rebuildPage(pPg, nNew, &pCArray->apCell[iNew], &pCArray->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 ** of the page that participate in the balancing operation. NB is the ** total number of pages that participate, including the target page and |
︙ | ︙ | |||
6824 6825 6826 6827 6828 6829 6830 | MemPage *pParent, /* Parent page of siblings being balanced */ int iParentIdx, /* Index of "the page" in pParent */ u8 *aOvflSpace, /* page-size bytes of space for parent ovfl */ int isRoot, /* True if pParent is a root-page */ int bBulk /* True if this call is part of a bulk load */ ){ BtShared *pBt; /* The whole database */ | < | | < < > > > | 6878 6879 6880 6881 6882 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 | MemPage *pParent, /* Parent page of siblings being balanced */ int iParentIdx, /* Index of "the page" in pParent */ u8 *aOvflSpace, /* page-size bytes of space for parent ovfl */ int isRoot, /* True if pParent is a root-page */ int bBulk /* True if this call is part of a bulk load */ ){ BtShared *pBt; /* The whole database */ int nMaxCells = 0; /* Allocated size of apCell, szCell, aFrom. */ int nNew = 0; /* Number of pages in apNew[] */ int nOld; /* Number of pages in apOld[] */ int i, j, k; /* Loop counters */ int nxDiv; /* Next divider slot in pParent->aCell[] */ int rc = SQLITE_OK; /* The return code */ u16 leafCorrection; /* 4 if pPage is a leaf. 0 if not */ int leafData; /* True if pPage is a leaf of a LEAFDATA tree */ int usableSpace; /* Bytes in pPage beyond the header */ int pageFlags; /* Value of pPage->aData[0] */ int iSpace1 = 0; /* First unused byte of aSpace1[] */ int iOvflSpace = 0; /* First unused byte of aOvflSpace[] */ int szScratch; /* Size of scratch memory requested */ MemPage *apOld[NB]; /* pPage and up to two siblings */ MemPage *apNew[NB+2]; /* pPage and up to NB siblings after balancing */ u8 *pRight; /* Location in parent of right-sibling pointer */ u8 *apDiv[NB-1]; /* Divider cells in pParent */ int cntNew[NB+2]; /* Index in b.paCell[] of cell after i-th page */ int cntOld[NB+2]; /* Old index in b.apCell[] */ int szNew[NB+2]; /* Combined size of cells placed on i-th page */ u8 *aSpace1; /* Space for copies of dividers cells */ Pgno pgno; /* Temp var to store a page number in */ u8 abDone[NB+2]; /* True after i'th new page is populated */ Pgno aPgno[NB+2]; /* Page numbers of new pages before shuffling */ Pgno aPgOrder[NB+2]; /* Copy of aPgno[] used for sorting pages */ u16 aPgFlags[NB+2]; /* flags field of new pages before shuffling */ CellArray b; /* Parsed information on cells being balanced */ memset(abDone, 0, sizeof(abDone)); b.nCell = 0; b.apCell = 0; pBt = pParent->pBt; assert( sqlite3_mutex_held(pBt->mutex) ); assert( sqlite3PagerIswriteable(pParent->pDbPage) ); #if 0 TRACE(("BALANCE: begin page %d child of %d\n", pPage->pgno, pParent->pgno)); #endif |
︙ | ︙ | |||
6963 6964 6965 6966 6967 6968 6969 | ** alignment */ nMaxCells = (nMaxCells + 3)&~3; /* ** Allocate space for memory structures */ szScratch = | | | | | | | | | | > | | > | | < | | | < | | | | | | | | | | | | | | | | | | 7017 7018 7019 7020 7021 7022 7023 7024 7025 7026 7027 7028 7029 7030 7031 7032 7033 7034 7035 7036 7037 7038 7039 7040 7041 7042 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 7073 7074 7075 7076 7077 7078 7079 7080 7081 7082 7083 7084 7085 7086 7087 7088 7089 7090 7091 7092 7093 7094 7095 7096 7097 7098 7099 7100 7101 7102 7103 7104 7105 7106 7107 7108 7109 7110 7111 7112 7113 7114 7115 7116 7117 7118 7119 7120 7121 7122 7123 7124 7125 7126 7127 7128 7129 7130 7131 7132 7133 7134 7135 7136 7137 7138 7139 7140 7141 7142 | ** alignment */ nMaxCells = (nMaxCells + 3)&~3; /* ** Allocate space for memory structures */ szScratch = nMaxCells*sizeof(u8*) /* b.apCell */ + nMaxCells*sizeof(u16) /* b.szCell */ + pBt->pageSize; /* aSpace1 */ /* EVIDENCE-OF: R-28375-38319 SQLite will never request a scratch buffer ** that is more than 6 times the database page size. */ assert( szScratch<=6*(int)pBt->pageSize ); b.apCell = sqlite3ScratchMalloc( szScratch ); if( b.apCell==0 ){ rc = SQLITE_NOMEM; goto balance_cleanup; } b.szCell = (u16*)&b.apCell[nMaxCells]; aSpace1 = (u8*)&b.szCell[nMaxCells]; assert( EIGHT_BYTE_ALIGNMENT(aSpace1) ); /* ** Load pointers to all cells on sibling pages and the divider cells ** into the local b.apCell[] array. Make copies of the divider cells ** into space obtained from aSpace1[]. The divider cells have already ** been removed from pParent. ** ** If the siblings are on leaf pages, then the child pointers of the ** divider cells are stripped from the cells before they are copied ** into aSpace1[]. In this way, all cells in b.apCell[] are without ** child pointers. If siblings are not leaves, then all cell in ** b.apCell[] include child pointers. Either way, all cells in b.apCell[] ** are alike. ** ** leafCorrection: 4 if pPage is a leaf. 0 if pPage is not a leaf. ** leafData: 1 if pPage holds key+data and pParent holds only keys. */ b.pRef = apOld[0]; leafCorrection = b.pRef->leaf*4; leafData = b.pRef->intKeyLeaf; for(i=0; i<nOld; i++){ int limit; MemPage *pOld = apOld[i]; /* Verify that all sibling pages are of the same "type" (table-leaf, ** table-interior, index-leaf, or index-interior). */ if( pOld->aData[0]!=apOld[0]->aData[0] ){ rc = SQLITE_CORRUPT_BKPT; goto balance_cleanup; } limit = pOld->nCell+pOld->nOverflow; memset(&b.szCell[b.nCell], 0, sizeof(b.szCell[0])*limit); if( pOld->nOverflow>0 ){ for(j=0; j<limit; j++){ assert( b.nCell<nMaxCells ); b.apCell[b.nCell] = findOverflowCell(pOld, j); b.nCell++; } }else{ u8 *aData = pOld->aData; u16 maskPage = pOld->maskPage; u16 cellOffset = pOld->cellOffset; for(j=0; j<limit; j++){ assert( b.nCell<nMaxCells ); b.apCell[b.nCell] = findCellv2(aData, maskPage, cellOffset, j); b.nCell++; } } cntOld[i] = b.nCell; if( i<nOld-1 && !leafData){ u16 sz = (u16)szNew[i]; u8 *pTemp; assert( b.nCell<nMaxCells ); b.szCell[b.nCell] = sz; pTemp = &aSpace1[iSpace1]; iSpace1 += sz; assert( sz<=pBt->maxLocal+23 ); assert( iSpace1 <= (int)pBt->pageSize ); memcpy(pTemp, apDiv[i], sz); b.apCell[b.nCell] = pTemp+leafCorrection; assert( leafCorrection==0 || leafCorrection==4 ); b.szCell[b.nCell] = b.szCell[b.nCell] - leafCorrection; if( !pOld->leaf ){ assert( leafCorrection==0 ); assert( pOld->hdrOffset==0 ); /* The right pointer of the child page pOld becomes the left ** pointer of the divider cell */ memcpy(b.apCell[b.nCell], &pOld->aData[8], 4); }else{ assert( leafCorrection==4 ); while( b.szCell[b.nCell]<4 ){ /* Do not allow any cells smaller than 4 bytes. If a smaller cell ** does exist, pad it with 0x00 bytes. */ assert( b.szCell[b.nCell]==3 || CORRUPT_DB ); assert( b.apCell[b.nCell]==&aSpace1[iSpace1-3] || CORRUPT_DB ); aSpace1[iSpace1++] = 0x00; b.szCell[b.nCell]++; } } b.nCell++; } } /* ** Figure out the number of pages needed to hold all b.nCell cells. ** Store this number in "k". Also compute szNew[] which is the total ** size of all cells on the i-th page and cntNew[] which is the index ** in b.apCell[] of the cell that divides page i from page i+1. ** cntNew[k] should equal b.nCell. ** ** Values computed by this block: ** ** k: The total number of sibling pages ** szNew[i]: Spaced used on the i-th sibling page. ** cntNew[i]: Index in b.apCell[] and b.szCell[] for the first cell to ** the right of the i-th sibling page. ** usableSpace: Number of bytes of space available on each sibling. ** */ usableSpace = pBt->usableSize - 12 + leafCorrection; for(i=0; i<nOld; i++){ MemPage *p = apOld[i]; |
︙ | ︙ | |||
7097 7098 7099 7100 7101 7102 7103 | for(i=0; i<k; i++){ int sz; while( szNew[i]>usableSpace ){ if( i+1>=k ){ k = i+2; if( k>NB+2 ){ rc = SQLITE_CORRUPT_BKPT; goto balance_cleanup; } szNew[k-1] = 0; | | | | > > > > | | | > > > > | | 7151 7152 7153 7154 7155 7156 7157 7158 7159 7160 7161 7162 7163 7164 7165 7166 7167 7168 7169 7170 7171 7172 7173 7174 7175 7176 7177 7178 7179 7180 7181 7182 7183 7184 7185 7186 7187 7188 7189 7190 7191 7192 7193 | for(i=0; i<k; i++){ int sz; while( szNew[i]>usableSpace ){ if( i+1>=k ){ k = i+2; if( k>NB+2 ){ rc = SQLITE_CORRUPT_BKPT; goto balance_cleanup; } szNew[k-1] = 0; cntNew[k-1] = b.nCell; } sz = 2 + cachedCellSize(&b, cntNew[i]-1); szNew[i] -= sz; if( !leafData ){ if( cntNew[i]<b.nCell ){ sz = 2 + cachedCellSize(&b, cntNew[i]); }else{ sz = 0; } } szNew[i+1] += sz; cntNew[i]--; } while( cntNew[i]<b.nCell ){ sz = 2 + cachedCellSize(&b, cntNew[i]); if( szNew[i]+sz>usableSpace ) break; szNew[i] += sz; cntNew[i]++; if( !leafData ){ if( cntNew[i]<b.nCell ){ sz = 2 + cachedCellSize(&b, cntNew[i]); }else{ sz = 0; } } szNew[i+1] -= sz; } if( cntNew[i]>=b.nCell ){ k = i+1; }else if( cntNew[i] - (i>0 ? cntNew[i-1] : 0) <= 0 ){ rc = SQLITE_CORRUPT_BKPT; goto balance_cleanup; } } |
︙ | ︙ | |||
7142 7143 7144 7145 7146 7147 7148 | */ for(i=k-1; i>0; i--){ int szRight = szNew[i]; /* Size of sibling on the right */ int szLeft = szNew[i-1]; /* Size of sibling on the left */ int r; /* Index of right-most cell in left sibling */ int d; /* Index of first cell to the left of right sibling */ | > | | | | > > | | < > > | | < < | 7204 7205 7206 7207 7208 7209 7210 7211 7212 7213 7214 7215 7216 7217 7218 7219 7220 7221 7222 7223 7224 7225 7226 7227 7228 7229 7230 7231 7232 7233 7234 7235 | */ for(i=k-1; i>0; i--){ int szRight = szNew[i]; /* Size of sibling on the right */ int szLeft = szNew[i-1]; /* Size of sibling on the left */ int r; /* Index of right-most cell in left sibling */ int d; /* Index of first cell to the left of right sibling */ while(1){ r = cntNew[i-1] - 1; d = r + 1 - leafData; assert( d<nMaxCells ); assert( r<nMaxCells ); (void)cachedCellSize(&b, d); (void)cachedCellSize(&b, r); if( szRight!=0 && (bBulk || szRight+b.szCell[d]+2 > szLeft-(b.szCell[r]+2)) ){ break; } szRight += b.szCell[d] + 2; szLeft -= b.szCell[r] + 2; cntNew[i-1]--; if( cntNew[i-1] <= 0 ){ rc = SQLITE_CORRUPT_BKPT; goto balance_cleanup; } } szNew[i] = szRight; szNew[i-1] = szLeft; } /* Sanity check: For a non-corrupt database file one of the follwing ** must be true: |
︙ | ︙ | |||
7196 7197 7198 7199 7200 7201 7202 | }else{ assert( i>0 ); rc = allocateBtreePage(pBt, &pNew, &pgno, (bBulk ? 1 : pgno), 0); if( rc ) goto balance_cleanup; zeroPage(pNew, pageFlags); apNew[i] = pNew; nNew++; | | | 7260 7261 7262 7263 7264 7265 7266 7267 7268 7269 7270 7271 7272 7273 7274 | }else{ assert( i>0 ); rc = allocateBtreePage(pBt, &pNew, &pgno, (bBulk ? 1 : pgno), 0); if( rc ) goto balance_cleanup; zeroPage(pNew, pageFlags); apNew[i] = pNew; nNew++; cntOld[i] = b.nCell; /* Set the pointer-map entry for the new sibling page. */ if( ISAUTOVACUUM ){ ptrmapPut(pBt, pNew->pgno, PTRMAP_BTREE, pParent->pgno, &rc); if( rc!=SQLITE_OK ){ goto balance_cleanup; } |
︙ | ︙ | |||
7301 7302 7303 7304 7305 7306 7307 | MemPage *pNew = apNew[0]; u8 *aOld = pNew->aData; int cntOldNext = pNew->nCell + pNew->nOverflow; int usableSize = pBt->usableSize; int iNew = 0; int iOld = 0; | | | | 7365 7366 7367 7368 7369 7370 7371 7372 7373 7374 7375 7376 7377 7378 7379 7380 | MemPage *pNew = apNew[0]; u8 *aOld = pNew->aData; int cntOldNext = pNew->nCell + pNew->nOverflow; int usableSize = pBt->usableSize; int iNew = 0; int iOld = 0; for(i=0; i<b.nCell; i++){ u8 *pCell = b.apCell[i]; if( i==cntOldNext ){ MemPage *pOld = (++iOld)<nNew ? apNew[iOld] : apOld[iOld]; cntOldNext += pOld->nCell + pOld->nOverflow + !leafData; aOld = pOld->aData; } if( i==cntNew[iNew] ){ pNew = apNew[++iNew]; |
︙ | ︙ | |||
7328 7329 7330 7331 7332 7333 7334 | || pCell<aOld || pCell>=&aOld[usableSize] ){ if( !leafCorrection ){ ptrmapPut(pBt, get4byte(pCell), PTRMAP_BTREE, pNew->pgno, &rc); if( rc ) goto balance_cleanup; } | | > | | | | | | 7392 7393 7394 7395 7396 7397 7398 7399 7400 7401 7402 7403 7404 7405 7406 7407 7408 7409 7410 7411 7412 7413 7414 7415 7416 7417 7418 7419 7420 7421 7422 7423 7424 7425 7426 7427 7428 7429 7430 7431 7432 7433 7434 7435 7436 7437 7438 7439 7440 7441 7442 7443 7444 7445 7446 7447 7448 7449 7450 7451 7452 7453 7454 | || pCell<aOld || pCell>=&aOld[usableSize] ){ if( !leafCorrection ){ ptrmapPut(pBt, get4byte(pCell), PTRMAP_BTREE, pNew->pgno, &rc); if( rc ) goto balance_cleanup; } if( cachedCellSize(&b,i)>pNew->minLocal ){ ptrmapPutOvflPtr(pNew, pCell, &rc); if( rc ) goto balance_cleanup; } } } } /* Insert new divider cells into pParent. */ for(i=0; i<nNew-1; i++){ u8 *pCell; u8 *pTemp; int sz; MemPage *pNew = apNew[i]; j = cntNew[i]; assert( j<nMaxCells ); assert( b.apCell[j]!=0 ); pCell = b.apCell[j]; sz = b.szCell[j] + leafCorrection; pTemp = &aOvflSpace[iOvflSpace]; if( !pNew->leaf ){ memcpy(&pNew->aData[8], pCell, 4); }else if( leafData ){ /* If the tree is a leaf-data tree, and the siblings are leaves, ** then there is no divider cell in b.apCell[]. Instead, the divider ** cell consists of the integer key for the right-most cell of ** the sibling-page assembled above only. */ CellInfo info; j--; pNew->xParseCell(pNew, b.apCell[j], &info); pCell = pTemp; sz = 4 + putVarint(&pCell[4], info.nKey); pTemp = 0; }else{ pCell -= 4; /* Obscure case for non-leaf-data trees: If the cell at pCell was ** previously stored on a leaf node, and its reported size was 4 ** bytes, then it may actually be smaller than this ** (see btreeParseCellPtr(), 4 bytes is the minimum size of ** any cell). But it is important to pass the correct size to ** insertCell(), so reparse the cell now. ** ** Note that this can never happen in an SQLite data file, as all ** cells are at least 4 bytes. It only happens in b-trees used ** to evaluate "IN (SELECT ...)" and similar clauses. */ if( b.szCell[j]==4 ){ assert(leafCorrection==4); sz = pParent->xCellSize(pParent, pCell); } } iOvflSpace += sz; assert( sz<=pBt->maxLocal+23 ); assert( iOvflSpace <= (int)pBt->pageSize ); |
︙ | ︙ | |||
7433 7434 7435 7436 7437 7438 7439 | ** only after iPg+1 has already been updated. */ assert( cntNew[iPg]>=cntOld[iPg] || abDone[iPg+1] ); if( iPg==0 ){ iNew = iOld = 0; nNewCell = cntNew[0]; }else{ | | | | 7498 7499 7500 7501 7502 7503 7504 7505 7506 7507 7508 7509 7510 7511 7512 7513 7514 7515 7516 7517 | ** only after iPg+1 has already been updated. */ assert( cntNew[iPg]>=cntOld[iPg] || abDone[iPg+1] ); if( iPg==0 ){ iNew = iOld = 0; nNewCell = cntNew[0]; }else{ iOld = iPg<nOld ? (cntOld[iPg-1] + !leafData) : b.nCell; iNew = cntNew[iPg-1] + !leafData; nNewCell = cntNew[iPg] - iNew; } rc = editPage(apNew[iPg], iOld, iNew, nNewCell, &b); if( rc ) goto balance_cleanup; abDone[iPg]++; apNew[iPg]->nFree = usableSpace-szNew[iPg]; assert( apNew[iPg]->nOverflow==0 ); assert( apNew[iPg]->nCell==nNewCell ); } } |
︙ | ︙ | |||
7490 7491 7492 7493 7494 7495 7496 | u32 key = get4byte(&apNew[i]->aData[8]); ptrmapPut(pBt, key, PTRMAP_BTREE, apNew[i]->pgno, &rc); } } assert( pParent->isInit ); TRACE(("BALANCE: finished: old=%d new=%d cells=%d\n", | | | 7555 7556 7557 7558 7559 7560 7561 7562 7563 7564 7565 7566 7567 7568 7569 | u32 key = get4byte(&apNew[i]->aData[8]); ptrmapPut(pBt, key, PTRMAP_BTREE, apNew[i]->pgno, &rc); } } assert( pParent->isInit ); TRACE(("BALANCE: finished: old=%d new=%d cells=%d\n", nOld, nNew, b.nCell)); /* Free any old pages that were not reused as new pages. */ for(i=nNew; i<nOld; i++){ freePage(apOld[i], &rc); } |
︙ | ︙ | |||
7513 7514 7515 7516 7517 7518 7519 | } #endif /* ** Cleanup before returning. */ balance_cleanup: | | | 7578 7579 7580 7581 7582 7583 7584 7585 7586 7587 7588 7589 7590 7591 7592 | } #endif /* ** Cleanup before returning. */ balance_cleanup: sqlite3ScratchFree(b.apCell); for(i=0; i<nOld; i++){ releasePage(apOld[i]); } for(i=0; i<nNew; i++){ releasePage(apNew[i]); } |
︙ | ︙ |