Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Add some testcase() and assert() macros to btree.c to aid with testing recent changes. (CVS 5757) |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
fb461b78dfc2501fafa8bce03da5487f |
User & Date: | drh 2008-09-30 17:18:17.000 |
Context
2008-10-01
| ||
08:43 | Fix a bug in where.c where a non-temp register was being incorrectly deallocated. Ticket #3408. (CVS 5758) (check-in: 59d2e89e21 user: danielk1977 tags: trunk) | |
2008-09-30
| ||
17:18 | Add some testcase() and assert() macros to btree.c to aid with testing recent changes. (CVS 5757) (check-in: fb461b78df user: drh tags: trunk) | |
16:48 | Fix a comment in btree.c. No code changes. (CVS 5756) (check-in: 0f3c56330b user: danielk1977 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.524 2008/09/30 17:18:17 drh 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" |
︙ | ︙ | |||
30 31 32 33 34 35 36 37 38 39 40 41 42 43 | #if 0 int sqlite3BtreeTrace=0; /* True to enable tracing */ # define TRACE(X) if(sqlite3BtreeTrace){printf X;fflush(stdout);} #else # define TRACE(X) #endif #ifndef SQLITE_OMIT_SHARED_CACHE /* ** A list of BtShared objects that are eligible for participation ** in shared cache. This variable has file scope during normal builds, ** but the test harness needs to access it so we make it global for | > > > > > > > > > > > > > > | 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 | #if 0 int sqlite3BtreeTrace=0; /* True to enable tracing */ # define TRACE(X) if(sqlite3BtreeTrace){printf X;fflush(stdout);} #else # define TRACE(X) #endif /* ** Sometimes we need a small amount of code such as a variable initialization ** to setup for a later assert() statement. We do not want this code to ** appear when assert() is disabled. The following macro is therefore ** used to contain that setup code. The "VVA" acronym stands for ** "Verification, Validation, and Accreditation". In other words, the ** code within VVA_ONLY() will only run during verification processes. */ #ifndef NDEBUG # define VVA_ONLY(X) X #else # define VVA_ONLY(X) #endif #ifndef SQLITE_OMIT_SHARED_CACHE /* ** A list of BtShared objects that are eligible for participation ** in shared cache. This variable has file scope during normal builds, ** but the test harness needs to access it so we make it global for |
︙ | ︙ | |||
2352 2353 2354 2355 2356 2357 2358 | ** the database file should be truncated to during the commit process. ** i.e. the database has been reorganized so that only the first *pnTrunc ** pages are in use. */ static int autoVacuumCommit(BtShared *pBt, Pgno *pnTrunc){ int rc = SQLITE_OK; Pager *pPager = pBt->pPager; | < | < | 2366 2367 2368 2369 2370 2371 2372 2373 2374 2375 2376 2377 2378 2379 2380 | ** the database file should be truncated to during the commit process. ** i.e. the database has been reorganized so that only the first *pnTrunc ** pages are in use. */ static int autoVacuumCommit(BtShared *pBt, Pgno *pnTrunc){ int rc = SQLITE_OK; Pager *pPager = pBt->pPager; VVA_ONLY( int nRef = sqlite3PagerRefcount(pPager) ); assert( sqlite3_mutex_held(pBt->mutex) ); invalidateAllOverflowCache(pBt); assert(pBt->autoVacuum); if( !pBt->incrVacuum ){ Pgno nFin = 0; |
︙ | ︙ | |||
4906 4907 4908 4909 4910 4911 4912 4913 4914 4915 4916 4917 4918 4919 | u8 *aCopy[NB]; /* Space for holding data of apCopy[] */ u8 *aSpace1; /* Space for copies of dividers cells before balance */ u8 *aSpace2 = 0; /* Space for overflow dividers cells after balance */ u8 *aFrom = 0; pPage = pCur->apPage[pCur->iPage]; assert( sqlite3_mutex_held(pPage->pBt->mutex) ); /* ** Find the parent page. */ assert( pCur->iPage>0 ); assert( pPage->isInit ); assert( sqlite3PagerIswriteable(pPage->pDbPage) || pPage->nOverflow==1 ); | > | 4918 4919 4920 4921 4922 4923 4924 4925 4926 4927 4928 4929 4930 4931 4932 | u8 *aCopy[NB]; /* Space for holding data of apCopy[] */ u8 *aSpace1; /* Space for copies of dividers cells before balance */ u8 *aSpace2 = 0; /* Space for overflow dividers cells after balance */ u8 *aFrom = 0; pPage = pCur->apPage[pCur->iPage]; assert( sqlite3_mutex_held(pPage->pBt->mutex) ); VVA_ONLY( pCur->pagesShuffled = 1 ); /* ** Find the parent page. */ assert( pCur->iPage>0 ); assert( pPage->isInit ); assert( sqlite3PagerIswriteable(pPage->pDbPage) || pPage->nOverflow==1 ); |
︙ | ︙ | |||
5488 5489 5490 5491 5492 5493 5494 5495 5496 5497 5498 5499 5500 5501 | ** 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. */ pgnoChild = get4byte(&pPage->aData[pPage->hdrOffset+8]); assert( pgnoChild>0 ); assert( pgnoChild<=pagerPagecount(pPage->pBt->pPager) ); rc = sqlite3BtreeGetPage(pPage->pBt, pgnoChild, &pChild, 0); if( rc ) goto end_shallow_balance; if( pPage->pgno==1 ){ rc = sqlite3BtreeInitPage(pChild); | > | 5501 5502 5503 5504 5505 5506 5507 5508 5509 5510 5511 5512 5513 5514 5515 | ** 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. */ VVA_ONLY( pCur->pagesShuffled = 1 ); pgnoChild = get4byte(&pPage->aData[pPage->hdrOffset+8]); assert( pgnoChild>0 ); assert( pgnoChild<=pagerPagecount(pPage->pBt->pPager) ); rc = sqlite3BtreeGetPage(pPage->pBt, pgnoChild, &pChild, 0); if( rc ) goto end_shallow_balance; if( pPage->pgno==1 ){ rc = sqlite3BtreeInitPage(pChild); |
︙ | ︙ | |||
5562 5563 5564 5565 5566 5567 5568 5569 5570 5571 5572 5573 5574 5575 | u8 *cdata; /* Content of the child page */ int hdr; /* Offset to page header in parent */ int cbrk; /* Offset to content of first cell in parent */ assert( pCur->iPage==0 ); assert( pCur->apPage[0]->nOverflow>0 ); pPage = pCur->apPage[0]; pBt = pPage->pBt; assert( sqlite3_mutex_held(pBt->mutex) ); rc = allocateBtreePage(pBt, &pChild, &pgnoChild, pPage->pgno, 0); if( rc ) return rc; assert( sqlite3PagerIswriteable(pChild->pDbPage) ); usableSize = pBt->usableSize; | > | 5576 5577 5578 5579 5580 5581 5582 5583 5584 5585 5586 5587 5588 5589 5590 | u8 *cdata; /* Content of the child page */ int hdr; /* Offset to page header in parent */ int cbrk; /* Offset to content of first cell in parent */ assert( pCur->iPage==0 ); assert( pCur->apPage[0]->nOverflow>0 ); VVA_ONLY( pCur->pagesShuffled = 1 ); pPage = pCur->apPage[0]; pBt = pPage->pBt; assert( sqlite3_mutex_held(pBt->mutex) ); rc = allocateBtreePage(pBt, &pChild, &pgnoChild, pPage->pgno, 0); if( rc ) return rc; assert( sqlite3PagerIswriteable(pChild->pDbPage) ); usableSize = pBt->usableSize; |
︙ | ︙ | |||
5810 5811 5812 5813 5814 5815 5816 | } end_insert: return rc; } /* ** Delete the entry that the cursor is pointing to. The cursor | | | 5825 5826 5827 5828 5829 5830 5831 5832 5833 5834 5835 5836 5837 5838 5839 | } end_insert: return rc; } /* ** Delete the entry that the cursor is pointing to. The cursor ** is left pointing at a arbitrary location. */ int sqlite3BtreeDelete(BtCursor *pCur){ MemPage *pPage = pCur->apPage[pCur->iPage]; int idx; unsigned char *pCell; int rc; Pgno pgnoChild = 0; |
︙ | ︙ | |||
5908 5909 5910 5911 5912 5913 5914 5915 5916 5917 5918 | tempCell = pBt->pTmpSpace; if( tempCell==0 ){ rc = SQLITE_NOMEM; } if( rc==SQLITE_OK ){ rc = insertCell(pPage, idx, pNext-4, szNext+4, tempCell, 0); } if( (pPage->nOverflow>0 || (pPage->nFree > pBt->usableSize*2/3)) && (pLeafPage->nFree+2+szNext > pBt->usableSize*2/3) ){ | > > > > > > > > > > > > > > > > > > > | | > > > | 5923 5924 5925 5926 5927 5928 5929 5930 5931 5932 5933 5934 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 | tempCell = pBt->pTmpSpace; if( tempCell==0 ){ rc = SQLITE_NOMEM; } if( rc==SQLITE_OK ){ rc = insertCell(pPage, idx, pNext-4, szNext+4, tempCell, 0); } /* The "if" statement in the next code block is critical. The ** slightest error in that statement would allow SQLite to operate ** correctly most of the time but produce very rare failures. To ** guard against this, the following macros help to verify that ** the "if" statement is well tested. */ testcase( pPage->nOverflow==0 && pPage->nFree<pBt->usableSize*2/3 && pLeafPage->nFree+2+szNext > pBt->usableSize*2/3 ); testcase( pPage->nOverflow==0 && pPage->nFree==pBt->usableSize*2/3 && pLeafPage->nFree+2+szNext > pBt->usableSize*2/3 ); testcase( pPage->nOverflow==0 && pPage->nFree==pBt->usableSize*2/3+1 && pLeafPage->nFree+2+szNext > pBt->usableSize*2/3 ); testcase( pPage->nOverflow>0 && pPage->nFree<=pBt->usableSize*2/3 && pLeafPage->nFree+2+szNext > pBt->usableSize*2/3 ); testcase( (pPage->nOverflow>0 || (pPage->nFree > pBt->usableSize*2/3)) && pLeafPage->nFree+2+szNext == pBt->usableSize*2/3 ); if( (pPage->nOverflow>0 || (pPage->nFree > pBt->usableSize*2/3)) && (pLeafPage->nFree+2+szNext > pBt->usableSize*2/3) ){ /* This branch is taken if the internal node is now either overflowing ** or underfull and the leaf node will be underfull after the just cell ** copied to the internal node is deleted from it. This is a special ** case because the call to balance() to correct the internal node ** may change the tree structure and invalidate the contents of ** the leafCur.apPage[] and leafCur.aiIdx[] arrays, which will be ** used by the balance() required to correct the underfull leaf ** node. ** ** The formula used in the expression above are based on facets of ** the SQLite file-format that do not change over time. */ testcase( pPage->nFree==pBt->usableSize*2/3+1 ); testcase( pLeafPage->nFree+2+szNext==pBt->usableSize*2/3+1 ); leafCursorInvalid = 1; } if( rc==SQLITE_OK ){ put4byte(findOverflowCell(pPage, idx), pgnoChild); VVA_ONLY( pCur->pagesShuffled = 0 ); rc = balance(pCur, 0); } if( rc==SQLITE_OK && leafCursorInvalid ){ /* The leaf-node is now underfull and so the tree needs to be ** rebalanced. However, the balance() operation on the internal ** node above may have modified the structure of the B-Tree and |
︙ | ︙ | |||
5956 5957 5958 5959 5960 5961 5962 | ** calls restoreCursorPosition() to point the cursor to the copy ** stored on the internal node, then advances to the next entry, ** which happens to be the copy of the key on the internal node. ** Net effect: leafCur is pointing back to the duplicate cell ** that needs to be removed, and the leafCur.apPage[] and ** leafCur.aiIdx[] arrays are correct. */ | < | < > > > | 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 | ** calls restoreCursorPosition() to point the cursor to the copy ** stored on the internal node, then advances to the next entry, ** which happens to be the copy of the key on the internal node. ** Net effect: leafCur is pointing back to the duplicate cell ** that needs to be removed, and the leafCur.apPage[] and ** leafCur.aiIdx[] arrays are correct. */ VVA_ONLY( Pgno leafPgno = pLeafPage->pgno ); rc = saveCursorPosition(&leafCur); if( rc==SQLITE_OK ){ rc = sqlite3BtreeNext(&leafCur, ¬Used); } pLeafPage = leafCur.apPage[leafCur.iPage]; assert( pLeafPage->pgno==leafPgno ); assert( leafCur.aiIdx[leafCur.iPage]==0 ); } if( rc==SQLITE_OK ){ dropCell(pLeafPage, 0, szNext); VVA_ONLY( leafCur.pagesShuffled = 0 ); rc = balance(&leafCur, 0); assert( leafCursorInvalid || !leafCur.pagesShuffled || !pCur->pagesShuffled ); } } sqlite3BtreeReleaseTempCursor(&leafCur); }else{ TRACE(("DELETE: table=%d delete from leaf %d\n", pCur->pgnoRoot, pPage->pgno)); dropCell(pPage, idx, cellSizePtr(pPage, pCell)); |
︙ | ︙ |
Changes to src/btreeInt.h.
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: btreeInt.h,v 1.34 2008/09/30 17:18:17 drh Exp $ ** ** This file implements a external (disk-based) database using BTrees. ** For a detailed discussion of BTrees, refer to ** ** Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3: ** "Sorting And Searching", pages 473-480. Addison-Wesley ** Publishing Company, Reading, Massachusetts. |
︙ | ︙ | |||
450 451 452 453 454 455 456 | void *pKey; /* Saved key that was cursor's last known position */ i64 nKey; /* Size of pKey, or last integer key */ int skip; /* (skip<0) -> Prev() is a no-op. (skip>0) -> Next() is */ #ifndef SQLITE_OMIT_INCRBLOB u8 isIncrblobHandle; /* True if this cursor is an incr. io handle */ Pgno *aOverflow; /* Cache of overflow page locations */ #endif | | > > | 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 | void *pKey; /* Saved key that was cursor's last known position */ i64 nKey; /* Size of pKey, or last integer key */ int skip; /* (skip<0) -> Prev() is a no-op. (skip>0) -> Next() is */ #ifndef SQLITE_OMIT_INCRBLOB u8 isIncrblobHandle; /* True if this cursor is an incr. io handle */ Pgno *aOverflow; /* Cache of overflow page locations */ #endif #ifndef NDEBUG u8 pagesShuffled; /* True if Btree pages are rearranged by balance()*/ #endif i16 iPage; /* Index of current page in apPage */ MemPage *apPage[BTCURSOR_MAX_DEPTH]; /* Pages from root to current page */ u16 aiIdx[BTCURSOR_MAX_DEPTH]; /* Current index in apPage[i] */ }; /* ** Potential values for BtCursor.eState. |
︙ | ︙ |