Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Reduce the stack usage of balance_quick(). (CVS 6715) |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
e7ad68e93b19b59cb16205c4b48fd9d6 |
User & Date: | danielk1977 2009-06-04 14:46:08.000 |
Context
2009-06-04
| ||
16:14 | If the root page of a btree is empty and is also not a leaf page and the page is not page 1, then report database corruption. (CVS 6716) (check-in: 52b02ca5f3 user: drh tags: trunk) | |
14:46 | Reduce the stack usage of balance_quick(). (CVS 6715) (check-in: e7ad68e93b user: danielk1977 tags: trunk) | |
02:47 | Minor updates to comments in test scripts. (CVS 6714) (check-in: 453ff88f73 user: shane tags: trunk) | |
Changes
Changes to src/btree.c.
1 2 3 4 5 6 7 8 9 10 11 | /* ** 2004 April 6 ** ** The author disclaims copyright to this source code. In place of ** a legal notice, here is a blessing: ** ** May you do good and not evil. ** May you find forgiveness for yourself and forgive others. ** May you share freely, never taking more than you give. ** ************************************************************************* | | | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | /* ** 2004 April 6 ** ** The author disclaims copyright to this source code. In place of ** a legal notice, here is a blessing: ** ** May you do good and not evil. ** May you find forgiveness for yourself and forgive others. ** May you share freely, never taking more than you give. ** ************************************************************************* ** $Id: btree.c,v 1.614 2009/06/04 14:46:08 danielk1977 Exp $ ** ** This file implements a external (disk-based) database using BTrees. ** See the header comment on "btreeInt.h" for additional information. ** Including a description of file format and an overview of operation. */ #include "btreeInt.h" |
︙ | ︙ | |||
1168 1169 1170 1171 1172 1173 1174 | sz = cellSizePtr(pPage, &data[pc]); if( pc+sz>usableSize ){ return SQLITE_CORRUPT_BKPT; } } } #endif | < | 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 | sz = cellSizePtr(pPage, &data[pc]); if( pc+sz>usableSize ){ return SQLITE_CORRUPT_BKPT; } } } #endif /* Compute the total free space on the page */ pc = get2byte(&data[hdr+1]); nFree = data[hdr+7] + top; while( pc>0 ){ u16 next, size; if( pc>usableSize-4 ){ |
︙ | ︙ | |||
5194 5195 5196 5197 5198 5199 5200 | ** fill up. On average. ** ** pPage is the leaf page which is the right-most page in the tree. ** pParent is its parent. pPage must have a single overflow entry ** which is also the right-most entry on the page. */ static int balance_quick(BtCursor *pCur){ | < < < < < < | < | < | | > > | < < > > > > > > > > > > | | > > | | > | | < | | | | | | < | | > | > | | | | > | 5193 5194 5195 5196 5197 5198 5199 5200 5201 5202 5203 5204 5205 5206 5207 5208 5209 5210 5211 5212 5213 5214 5215 5216 5217 5218 5219 5220 5221 5222 5223 5224 5225 5226 5227 5228 5229 5230 5231 5232 5233 5234 5235 5236 5237 5238 5239 5240 5241 5242 5243 5244 5245 5246 5247 5248 5249 5250 5251 5252 5253 5254 5255 5256 5257 5258 5259 5260 5261 | ** fill up. On average. ** ** pPage is the leaf page which is the right-most page in the tree. ** pParent is its parent. pPage must have a single overflow entry ** which is also the right-most entry on the page. */ static int balance_quick(BtCursor *pCur){ MemPage *const pPage = pCur->apPage[pCur->iPage]; BtShared *const pBt = pCur->pBt; MemPage *pNew = 0; /* Newly allocated page */ int rc; /* Return Code */ Pgno pgnoNew; /* Page number of pNew */ assert( sqlite3_mutex_held(pPage->pBt->mutex) ); assert( pPage->nCell>0 ); /* Allocate a new page. This page will become the right-sibling of pPage */ rc = allocateBtreePage(pBt, &pNew, &pgnoNew, 0, 0); if( rc==SQLITE_OK ){ /* The parentCell buffer is used to store a temporary copy of the divider ** cell that will be inserted into pParent. Such a cell consists of a 4 ** byte page number followed by a variable length integer. In other ** words, at most 13 bytes. Hence the parentCell buffer must be at ** least 13 bytes in size. */ MemPage * const pParent = pCur->apPage[pCur->iPage-1]; u8 parentCell[13]; u8 *pOut = &parentCell[4]; u8 *pCell = pPage->aOvfl[0].pCell; u16 szCell = cellSizePtr(pPage, pCell); u8 *pStop; assert( sqlite3PagerIswriteable(pNew->pDbPage) ); zeroPage(pNew, pPage->aData[0]); assemblePage(pNew, 1, &pCell, &szCell); pPage->nOverflow = 0; /* Create a divider cell to insert into pParent. The divider cell ** consists of a 4-byte page number (the page number of pPage) and ** a variable length key value (which must be the same value as the ** largest key on pPage). ** ** To find the largest key value on pPage, first find the right-most ** cell on pPage. The first two fields of this cell are the ** record-length (a variable length integer at most 32-bits in size) ** and the key value (a variable length integer, may have any value). ** The first of the while(...) loops below skips over the record-length ** field. The second while(...) loop copies the key value from the ** cell on pPage into the parentCell buffer. */ put4byte(parentCell, pPage->pgno); pCell = findCell(pPage, pPage->nCell-1); pStop = &pCell[9]; while( (*(pCell++)&0x80) && pCell<pStop ); pStop = &pCell[9]; while( ((*(pOut++) = *(pCell++))&0x80) && pCell<pStop ); /* Insert the new divider cell into pParent */ insertCell(pParent, pParent->nCell, parentCell, pOut-parentCell, 0, 0); /* Set the right-child pointer of pParent to point to the new page. */ put4byte(&pParent->aData[pParent->hdrOffset+8], pgnoNew); /* 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( ISAUTOVACUUM ){ |
︙ | ︙ | |||
5638 5639 5640 5641 5642 5643 5644 | r = cntNew[i-1] - 1; d = r + 1 - leafData; } szNew[i] = szRight; szNew[i-1] = szLeft; } | | | 5643 5644 5645 5646 5647 5648 5649 5650 5651 5652 5653 5654 5655 5656 5657 | r = cntNew[i-1] - 1; d = r + 1 - leafData; } szNew[i] = szRight; szNew[i-1] = szLeft; } /* Either we found one or more cells (cntnew[0])>0) or pPage is ** a virtual root page. A virtual root page is when the real root ** page is page 1 and we are the only child of that page. */ assert( cntNew[0]>0 || (pParent->pgno==1 && pParent->nCell==0) ); /* ** Allocate k new pages. Reuse old pages where possible. |
︙ | ︙ |