/ Check-in [f77f2f48]

 ```952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 .... 6239 6240 6241 6242 6243 6244 6245 6246 6247 6248 6249 6250 6251 6252 .... 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 ``` ```** the page, 1 means the second cell, and so forth) return a pointer ** to the cell content. ** ** This routine works only for pages that do not contain overflow cells. */ #define findCell(P,I) \ ((P)->aData + ((P)->maskPage & get2byte(&(P)->aCellIdx[2*(I)]))) /* ** Sort the overflow cells of a page into index order. ** ** An O(N*N) algorithm is used. But that should not be a problem ** since N is only very rarely more than 1. */ static void btreeSortOverflow(MemPage *p){ int j, k; for(j=0; jnOverflow-1; j++){ for(k=j+1; knOverflow; k++){ if( p->aiOvfl[j]>p->aiOvfl[k] ){ SWAP(u16, p->aiOvfl[j], p->aiOvfl[k]); SWAP(u8*, p->apOvfl[j], p->apOvfl[k]); } } } } /* ** This is common tail processing for btreeParseCellPtr() and ** btreeParseCellPtrIndex() for the case when the cell does not fit entirely ** on a single B-tree page. Make necessary adjustments to the CellInfo ** structure. */ ................................................................................ if( iChild ){ put4byte(pCell, iChild); } j = pPage->nOverflow++; assert( j<(int)(sizeof(pPage->apOvfl)/sizeof(pPage->apOvfl[0])) ); pPage->apOvfl[j] = pCell; pPage->aiOvfl[j] = (u16)i; }else{ int rc = sqlite3PagerWrite(pPage->pDbPage); if( rc!=SQLITE_OK ){ *pRC = rc; return; } assert( sqlite3PagerIswriteable(pPage->pDbPage) ); ................................................................................ leafData = b.pRef->intKeyLeaf; for(i=0; inCell; u8 *aData = pOld->aData; u16 maskPage = pOld->maskPage; u8 *piCell = aData + pOld->cellOffset; /* 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; } /* Load b.apCell[] with pointers to all cells in pOld. Intersperse ** overflow cells in the correct sequence. ** ** This must be done in advance. Once the balance starts, the cell ** offset section of the btree page will be overwritten and we will no ** long be able to find the cells if a pointer to each cell is not saved ** first. */ memset(&b.szCell[b.nCell], 0, sizeof(b.szCell[0])*limit); if( pOld->nOverflow>0 ){ memset(&b.szCell[b.nCell+limit], 0, sizeof(b.szCell[0])*pOld->nOverflow); btreeSortOverflow(pOld); for(j=k=0; knOverflow; k++){ limit = pOld->aiOvfl[k] - k; while( japOvfl[k]; b.nCell++; } limit = pOld->nCell - j; } limit += b.nCell; while( b.nCell > > > > > > > > | > | > > > > > > > > < < | | | | | < | > > | | | ``` ```952 953 954 955 956 957 958 959 960 961 962 963 964 965 .... 6220 6221 6222 6223 6224 6225 6226 6227 6228 6229 6230 6231 6232 6233 6234 6235 6236 6237 6238 6239 6240 6241 .... 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 ``` ```** the page, 1 means the second cell, and so forth) return a pointer ** to the cell content. ** ** This routine works only for pages that do not contain overflow cells. */ #define findCell(P,I) \ ((P)->aData + ((P)->maskPage & get2byte(&(P)->aCellIdx[2*(I)]))) /* ** This is common tail processing for btreeParseCellPtr() and ** btreeParseCellPtrIndex() for the case when the cell does not fit entirely ** on a single B-tree page. Make necessary adjustments to the CellInfo ** structure. */ ................................................................................ if( iChild ){ put4byte(pCell, iChild); } j = pPage->nOverflow++; assert( j<(int)(sizeof(pPage->apOvfl)/sizeof(pPage->apOvfl[0])) ); pPage->apOvfl[j] = pCell; pPage->aiOvfl[j] = (u16)i; /* When multiple overflows occur, they are always sequential and in ** sorted order. This invariants arise because multiple overflows can ** only occur when inserting divider cells into the parent page during ** balancing, and the dividers are adjacent and sorted. */ assert( j==0 || pPage->aiOvfl[j-1]<(u16)i ); /* Overflows in sorted order */ assert( j==0 || i==pPage->aiOvfl[j-1]+1 ); /* Overflows are sequential */ }else{ int rc = sqlite3PagerWrite(pPage->pDbPage); if( rc!=SQLITE_OK ){ *pRC = rc; return; } assert( sqlite3PagerIswriteable(pPage->pDbPage) ); ................................................................................ leafData = b.pRef->intKeyLeaf; for(i=0; inCell; u8 *aData = pOld->aData; u16 maskPage = pOld->maskPage; u8 *piCell = aData + pOld->cellOffset; u8 *piEnd; /* 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; } /* Load b.apCell[] with pointers to all cells in pOld. If pOld ** constains overflow cells, include them in the b.apCell[] array ** in the correct spot. ** ** Note that when there are multiple overflow cells, it is always the ** case that they are sequential and adjacent. This invariant arises ** because multiple overflows can only occurs when inserting divider ** cells into a parent on a prior balance, and divider cells are always ** adjacent and are inserted in order. There is an assert() tagged ** with "NOTE 1" in the overflow cell insertion loop to prove this ** invariant. ** ** This must be done in advance. Once the balance starts, the cell ** offset section of the btree page will be overwritten and we will no ** long be able to find the cells if a pointer to each cell is not saved ** first. */ memset(&b.szCell[b.nCell], 0, sizeof(b.szCell[0])*limit); if( pOld->nOverflow>0 ){ memset(&b.szCell[b.nCell+limit], 0, sizeof(b.szCell[0])*pOld->nOverflow); limit = pOld->aiOvfl[0]; for(j=0; jnOverflow; k++){ assert( k==0 || pOld->aiOvfl[k-1]+1==pOld->aiOvfl[k] );/* NOTE 1 */ b.apCell[b.nCell] = pOld->apOvfl[k]; b.nCell++; } limit = pOld->nCell - pOld->aiOvfl[0]; } piEnd = aData + pOld->cellOffset + 2*pOld->nCell; while( piCell