Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Call balance_shallower() from balance_nonroot() instead of from balance(). This simplifies coverage testing a bit. (CVS 6805) |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
da9893e23caf89090c8b6563cb5f88d7 |
User & Date: | danielk1977 2009-06-23 15:43:40.000 |
Context
2009-06-23
| ||
16:40 | Remove a condition from balance_nonroot() that is always true. (CVS 6806) (check-in: c5dc80e6bd user: danielk1977 tags: trunk) | |
15:43 | Call balance_shallower() from balance_nonroot() instead of from balance(). This simplifies coverage testing a bit. (CVS 6805) (check-in: da9893e23c user: danielk1977 tags: trunk) | |
14:39 | Update the configure script for version 3.6.16 (CVS 6804) (check-in: b614e554f7 user: drh 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.640 2009/06/23 15:43:40 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" |
︙ | ︙ | |||
5334 5335 5336 5337 5338 5339 5340 5341 5342 5343 5344 5345 5346 5347 | assert( n==pPage->pgno && e==PTRMAP_BTREE ); } } return 1; } #endif /* ** This routine redistributes cells on the iParentIdx'th child of pParent ** (hereafter "the page") and up to 2 siblings so that all pages have about the ** same amount of free space. Usually a single sibling on either side of the ** page are used in the balancing, though both siblings might come from one ** side if the page is the first or last child of its parent. If the page | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 5334 5335 5336 5337 5338 5339 5340 5341 5342 5343 5344 5345 5346 5347 5348 5349 5350 5351 5352 5353 5354 5355 5356 5357 5358 5359 5360 5361 5362 5363 5364 5365 5366 5367 5368 5369 5370 5371 5372 5373 5374 5375 5376 5377 5378 5379 5380 5381 5382 5383 5384 5385 5386 5387 5388 5389 5390 5391 5392 5393 5394 5395 5396 5397 5398 5399 5400 5401 5402 5403 5404 5405 5406 5407 5408 5409 5410 5411 5412 5413 5414 5415 5416 5417 5418 5419 5420 5421 5422 5423 5424 5425 5426 5427 5428 5429 5430 5431 5432 5433 5434 5435 5436 5437 | assert( n==pPage->pgno && e==PTRMAP_BTREE ); } } return 1; } #endif /* ** This function is used to copy the contents of the b-tree node stored ** on page pFrom to page pTo. If page pFrom was not a leaf page, then ** the pointer-map entries for each child page are updated so that the ** parent page stored in the pointer map is page pTo. If pFrom contained ** any cells with overflow page pointers, then the corresponding pointer ** map entries are also updated so that the parent page is page pTo. ** ** If pFrom is currently carrying any overflow cells (entries in the ** MemPage.aOvfl[] array), they are not copied to pTo. ** ** Before returning, page pTo is reinitialized using sqlite3BtreeInitPage(). ** ** The performance of this function is not critical. It is only used by ** the balance_shallower() and balance_deeper() procedures, neither of ** which are called often under normal circumstances. */ static int copyNodeContent(MemPage *pFrom, MemPage *pTo){ BtShared * const pBt = pFrom->pBt; u8 * const aFrom = pFrom->aData; u8 * const aTo = pTo->aData; int const iFromHdr = pFrom->hdrOffset; int const iToHdr = ((pTo->pgno==1) ? 100 : 0); int rc = SQLITE_OK; int iData; assert( pFrom->isInit ); assert( pFrom->nFree>=iToHdr ); assert( get2byte(&aFrom[iFromHdr+5])<=pBt->usableSize ); /* Copy the b-tree node content from page pFrom to page pTo. */ iData = get2byte(&aFrom[iFromHdr+5]); memcpy(&aTo[iData], &aFrom[iData], pBt->usableSize-iData); memcpy(&aTo[iToHdr], &aFrom[iFromHdr], pFrom->cellOffset + 2*pFrom->nCell); /* Reinitialize page pTo so that the contents of the MemPage structure ** match the new data. The initialization of pTo "cannot" fail, as the ** data copied from pFrom is known to be valid. */ pTo->isInit = 0; TESTONLY(rc = ) sqlite3BtreeInitPage(pTo); assert( rc==SQLITE_OK ); /* If this is an auto-vacuum database, update the pointer-map entries ** for any b-tree or overflow pages that pTo now contains the pointers to. */ if( ISAUTOVACUUM ){ rc = setChildPtrmaps(pTo); } return rc; } /* ** This routine is called on the root page of a btree when the root ** page contains no cells. This is an opportunity to make the tree ** shallower by one level. */ static int balance_shallower(MemPage *pRoot, MemPage *pChild){ /* The root page is empty but has one child. Transfer the ** information from that one child into the root page if it ** will fit. This reduces the depth of the tree by one. ** ** If the root page is page 1, it has less space available than ** its child (due to the 100 byte header that occurs at the beginning ** of the database fle), so it might not be able to hold all of the ** information currently contained in the child. If this is the ** case, then do not do the transfer. Leave page 1 empty except ** for the right-pointer to the child page. The child page becomes ** the virtual root of the tree. */ int rc = SQLITE_OK; /* Return code */ int const hdr = pRoot->hdrOffset; /* Offset of root page header */ assert( sqlite3_mutex_held(pRoot->pBt->mutex) ); assert( pRoot->nCell==0 ); assert( pChild->pgno==get4byte(&pRoot->aData[pRoot->hdrOffset+8]) ); assert( hdr==0 || pRoot->pgno==1 ); if( pChild->nFree>=hdr ){ if( hdr ){ rc = defragmentPage(pChild); } if( rc==SQLITE_OK ){ rc = copyNodeContent(pChild, pRoot); } if( rc==SQLITE_OK ){ rc = freePage(pChild); } } return rc; } /* ** This routine redistributes cells on the iParentIdx'th child of pParent ** (hereafter "the page") and up to 2 siblings so that all pages have about the ** same amount of free space. Usually a single sibling on either side of the ** page are used in the balancing, though both siblings might come from one ** side if the page is the first or last child of its parent. If the page |
︙ | ︙ | |||
5378 5379 5380 5381 5382 5383 5384 | ** ** If aOvflSpace is set to a null pointer, this function returns ** SQLITE_NOMEM. */ static int balance_nonroot( MemPage *pParent, /* Parent page of siblings being balanced */ int iParentIdx, /* Index of "the page" in pParent */ | | > | 5468 5469 5470 5471 5472 5473 5474 5475 5476 5477 5478 5479 5480 5481 5482 5483 | ** ** If aOvflSpace is set to a null pointer, this function returns ** SQLITE_NOMEM. */ static int balance_nonroot( 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 */ ){ BtShared *pBt; /* The whole database */ int nCell = 0; /* Number of cells in apCell[] */ 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 */ |
︙ | ︙ | |||
5935 5936 5937 5938 5939 5940 5941 5942 5943 5944 5945 5946 5947 5948 5949 5950 5951 5952 5953 5954 | ptrmapCheckPages(&pParent, 1); #endif } assert( pParent->isInit ); TRACE(("BALANCE: finished: old=%d new=%d cells=%d\n", nOld, nNew, nCell)); /* ** Cleanup before returning. */ balance_cleanup: sqlite3ScratchFree(apCell); for(i=0; i<nOld; i++){ releasePage(apOld[i]); } for(i=0; i<nNew; i++){ releasePage(apNew[i]); } | > > > > > > > > > > < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < | 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 | ptrmapCheckPages(&pParent, 1); #endif } assert( pParent->isInit ); TRACE(("BALANCE: finished: old=%d new=%d cells=%d\n", nOld, nNew, nCell)); if( rc==SQLITE_OK && pParent->nCell==0 && isRoot ){ /* The root page of the b-tree now contains no cells. If the root-page ** is not also a leaf page, it will have a single child page. Call ** balance_shallower to attempt to copy the contents of the single ** child-page into the root page (this may not be possible if the ** root page is page 1). */ assert( nNew==1 ); rc = balance_shallower(pParent, apNew[0]); } /* ** Cleanup before returning. */ balance_cleanup: sqlite3ScratchFree(apCell); for(i=0; i<nOld; i++){ releasePage(apOld[i]); } for(i=0; i<nNew; i++){ releasePage(apNew[i]); } return rc; } /* ** This function is called when the root page of a b-tree structure is ** overfull (has one or more overflow pages). |
︙ | ︙ | |||
6122 6123 6124 6125 6126 6127 6128 | /* ** The page that pCur currently points to has just been modified in ** some way. This function figures out if this modification means the ** tree needs to be balanced, and if so calls the appropriate balancing ** routine. Balancing routines are: ** ** balance_quick() | < | 6120 6121 6122 6123 6124 6125 6126 6127 6128 6129 6130 6131 6132 6133 | /* ** The page that pCur currently points to has just been modified in ** some way. This function figures out if this modification means the ** tree needs to be balanced, and if so calls the appropriate balancing ** routine. Balancing routines are: ** ** balance_quick() ** balance_deeper() ** balance_nonroot() ** ** If built with SQLITE_DEBUG, pCur->pagesShuffled is set to true if ** balance_shallower(), balance_deeper() or balance_nonroot() is called. ** If none of these functions are invoked, pCur->pagesShuffled is left ** unmodified. |
︙ | ︙ | |||
6161 6162 6163 6164 6165 6166 6167 | pCur->iPage = 1; pCur->aiIdx[0] = 0; pCur->aiIdx[1] = 0; assert( pCur->apPage[1]->nOverflow ); } VVA_ONLY( pCur->pagesShuffled = 1 ); }else{ | < < < < < < < < < < < < < | 6158 6159 6160 6161 6162 6163 6164 6165 6166 6167 6168 6169 6170 6171 | pCur->iPage = 1; pCur->aiIdx[0] = 0; pCur->aiIdx[1] = 0; assert( pCur->apPage[1]->nOverflow ); } VVA_ONLY( pCur->pagesShuffled = 1 ); }else{ break; } }else if( pPage->nOverflow==0 && pPage->nFree<=nMin ){ break; }else{ MemPage * const pParent = pCur->apPage[iPage-1]; int const iIdx = pCur->aiIdx[iPage-1]; |
︙ | ︙ | |||
6227 6228 6229 6230 6231 6232 6233 | ** different page). Once this subsequent call to balance_nonroot() ** has completed, it is safe to release the pSpace buffer used by ** the previous call, as the overflow cell data will have been ** copied either into the body of a database page or into the new ** pSpace buffer passed to the latter call to balance_nonroot(). */ u8 *pSpace = sqlite3PageMalloc(pCur->pBt->pageSize); | | | 6211 6212 6213 6214 6215 6216 6217 6218 6219 6220 6221 6222 6223 6224 6225 | ** different page). Once this subsequent call to balance_nonroot() ** has completed, it is safe to release the pSpace buffer used by ** the previous call, as the overflow cell data will have been ** copied either into the body of a database page or into the new ** pSpace buffer passed to the latter call to balance_nonroot(). */ u8 *pSpace = sqlite3PageMalloc(pCur->pBt->pageSize); rc = balance_nonroot(pParent, iIdx, pSpace, iPage==1); if( pFree ){ /* If pFree is not NULL, it points to the pSpace buffer used ** by a previous call to balance_nonroot(). Its contents are ** now stored either on real database pages or within the ** new pSpace buffer, so it may be safely freed here. */ sqlite3PageFree(pFree); } |
︙ | ︙ |