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 | SQL archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
da9893e23caf89090c8b6563cb5f88d7 |
User & Date: | danielk1977 2009-06-23 15:43:40 |
Context
2009-06-23
| ||
16:40 | Remove a condition from balance_nonroot() that is always true. (CVS 6806) check-in: c5dc80e6 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: da9893e2 user: danielk1977 tags: trunk | |
14:39 | Update the configure script for version 3.6.16 (CVS 6804) check-in: b614e554 user: drh tags: trunk | |
Changes
Changes to src/btree.c.
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 .... 5334 5335 5336 5337 5338 5339 5340 5341 5342 5343 5344 5345 5346 5347 .... 5378 5379 5380 5381 5382 5383 5384 5385 5386 5387 5388 5389 5390 5391 5392 .... 5935 5936 5937 5938 5939 5940 5941 5942 5943 5944 5945 5946 5947 5948 5949 5950 5951 5952 5953 5954 5955 5956 5957 5958 5959 5960 5961 5962 5963 5964 5965 5966 5967 5968 5969 5970 5971 5972 5973 5974 5975 5976 5977 5978 5979 5980 5981 5982 5983 5984 5985 5986 5987 5988 5989 5990 5991 5992 5993 5994 5995 5996 5997 5998 5999 6000 6001 6002 6003 6004 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 .... 6122 6123 6124 6125 6126 6127 6128 6129 6130 6131 6132 6133 6134 6135 6136 .... 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 .... 6227 6228 6229 6230 6231 6232 6233 6234 6235 6236 6237 6238 6239 6240 6241 |
** 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.639 2009/06/23 11:22:29 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" ................................................................................ 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 ................................................................................ ** ** 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 */ ){ 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 */ ................................................................................ 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]); } return rc; } /* ** 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){ /* 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 */ MemPage *pChild; /* Only child of pRoot */ Pgno const pgnoChild = get4byte(&pRoot->aData[pRoot->hdrOffset+8]); assert( pRoot->nCell==0 ); assert( sqlite3_mutex_held(pRoot->pBt->mutex) ); assert( !pRoot->leaf ); assert( pgnoChild>0 ); assert( pgnoChild<=pagerPagecount(pRoot->pBt) ); assert( hdr==0 || pRoot->pgno==1 ); rc = sqlite3BtreeGetPage(pRoot->pBt, pgnoChild, &pChild, 0); if( rc==SQLITE_OK ){ if( pChild->nFree>=hdr ){ if( hdr ){ rc = defragmentPage(pChild); } if( rc==SQLITE_OK ){ rc = copyNodeContent(pChild, pRoot); } if( rc==SQLITE_OK ){ rc = freePage(pChild); } }else{ /* The child has more information that will fit on the root. ** The tree is already balanced. Do nothing. */ TRACE(("BALANCE: child %d will not fit on page 1\n", pChild->pgno)); } releasePage(pChild); } return rc; } /* ** This function is called when the root page of a b-tree structure is ** overfull (has one or more overflow pages). ................................................................................ /* ** 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_shallower() ** 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. ................................................................................ pCur->iPage = 1; pCur->aiIdx[0] = 0; pCur->aiIdx[1] = 0; assert( pCur->apPage[1]->nOverflow ); } VVA_ONLY( pCur->pagesShuffled = 1 ); }else{ /* The root page of the b-tree is now empty. 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). ** ** Whether or not this is possible , the tree is now balanced. ** Therefore is no next iteration of the do-loop. */ if( pPage->nCell==0 && !pPage->leaf ){ rc = balance_shallower(pPage); VVA_ONLY( pCur->pagesShuffled = 1 ); } 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]; ................................................................................ ** 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); 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); } |
| > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | > | > > > > > > > > > > < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < | |
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 .... 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 .... 5468 5469 5470 5471 5472 5473 5474 5475 5476 5477 5478 5479 5480 5481 5482 5483 .... 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 .... 6120 6121 6122 6123 6124 6125 6126 6127 6128 6129 6130 6131 6132 6133 .... 6158 6159 6160 6161 6162 6163 6164 6165 6166 6167 6168 6169 6170 6171 .... 6211 6212 6213 6214 6215 6216 6217 6218 6219 6220 6221 6222 6223 6224 6225 |
** 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" ................................................................................ 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 ................................................................................ ** ** 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 */ ................................................................................ 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). ................................................................................ /* ** 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. ................................................................................ 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]; ................................................................................ ** 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); } |