/ Check-in [fb461b78]
Login

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 | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:fb461b78dfc2501fafa8bce03da5487fdfdff959
User & Date: drh 2008-09-30 17:18:17
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: 59d2e89e 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: fb461b78 user: drh tags: trunk
16:48
Fix a comment in btree.c. No code changes. (CVS 5756) check-in: 0f3c5633 user: danielk1977 tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/btree.c.

     5      5   ** a legal notice, here is a blessing:
     6      6   **
     7      7   **    May you do good and not evil.
     8      8   **    May you find forgiveness for yourself and forgive others.
     9      9   **    May you share freely, never taking more than you give.
    10     10   **
    11     11   *************************************************************************
    12         -** $Id: btree.c,v 1.523 2008/09/30 16:48:11 danielk1977 Exp $
           12  +** $Id: btree.c,v 1.524 2008/09/30 17:18:17 drh Exp $
    13     13   **
    14     14   ** This file implements a external (disk-based) database using BTrees.
    15     15   ** See the header comment on "btreeInt.h" for additional information.
    16     16   ** Including a description of file format and an overview of operation.
    17     17   */
    18     18   #include "btreeInt.h"
    19     19   
................................................................................
    30     30   #if 0
    31     31   int sqlite3BtreeTrace=0;  /* True to enable tracing */
    32     32   # define TRACE(X)  if(sqlite3BtreeTrace){printf X;fflush(stdout);}
    33     33   #else
    34     34   # define TRACE(X)
    35     35   #endif
    36     36   
           37  +/*
           38  +** Sometimes we need a small amount of code such as a variable initialization
           39  +** to setup for a later assert() statement.  We do not want this code to
           40  +** appear when assert() is disabled.  The following macro is therefore
           41  +** used to contain that setup code.  The "VVA" acronym stands for
           42  +** "Verification, Validation, and Accreditation".  In other words, the
           43  +** code within VVA_ONLY() will only run during verification processes.
           44  +*/
           45  +#ifndef NDEBUG
           46  +# define VVA_ONLY(X)  X
           47  +#else
           48  +# define VVA_ONLY(X)
           49  +#endif
           50  +
    37     51   
    38     52   
    39     53   #ifndef SQLITE_OMIT_SHARED_CACHE
    40     54   /*
    41     55   ** A list of BtShared objects that are eligible for participation
    42     56   ** in shared cache.  This variable has file scope during normal builds,
    43     57   ** but the test harness needs to access it so we make it global for 
................................................................................
  2352   2366   ** the database file should be truncated to during the commit process. 
  2353   2367   ** i.e. the database has been reorganized so that only the first *pnTrunc
  2354   2368   ** pages are in use.
  2355   2369   */
  2356   2370   static int autoVacuumCommit(BtShared *pBt, Pgno *pnTrunc){
  2357   2371     int rc = SQLITE_OK;
  2358   2372     Pager *pPager = pBt->pPager;
  2359         -#ifndef NDEBUG
  2360         -  int nRef = sqlite3PagerRefcount(pPager);
  2361         -#endif
         2373  +  VVA_ONLY( int nRef = sqlite3PagerRefcount(pPager) );
  2362   2374   
  2363   2375     assert( sqlite3_mutex_held(pBt->mutex) );
  2364   2376     invalidateAllOverflowCache(pBt);
  2365   2377     assert(pBt->autoVacuum);
  2366   2378     if( !pBt->incrVacuum ){
  2367   2379       Pgno nFin = 0;
  2368   2380   
................................................................................
  4906   4918     u8 *aCopy[NB];         /* Space for holding data of apCopy[] */
  4907   4919     u8 *aSpace1;           /* Space for copies of dividers cells before balance */
  4908   4920     u8 *aSpace2 = 0;       /* Space for overflow dividers cells after balance */
  4909   4921     u8 *aFrom = 0;
  4910   4922   
  4911   4923     pPage = pCur->apPage[pCur->iPage];
  4912   4924     assert( sqlite3_mutex_held(pPage->pBt->mutex) );
         4925  +  VVA_ONLY( pCur->pagesShuffled = 1 );
  4913   4926   
  4914   4927     /* 
  4915   4928     ** Find the parent page.
  4916   4929     */
  4917   4930     assert( pCur->iPage>0 );
  4918   4931     assert( pPage->isInit );
  4919   4932     assert( sqlite3PagerIswriteable(pPage->pDbPage) || pPage->nOverflow==1 );
................................................................................
  5488   5501       ** its child (due to the 100 byte header that occurs at the beginning
  5489   5502       ** of the database fle), so it might not be able to hold all of the 
  5490   5503       ** information currently contained in the child.  If this is the 
  5491   5504       ** case, then do not do the transfer.  Leave page 1 empty except
  5492   5505       ** for the right-pointer to the child page.  The child page becomes
  5493   5506       ** the virtual root of the tree.
  5494   5507       */
         5508  +    VVA_ONLY( pCur->pagesShuffled = 1 );
  5495   5509       pgnoChild = get4byte(&pPage->aData[pPage->hdrOffset+8]);
  5496   5510       assert( pgnoChild>0 );
  5497   5511       assert( pgnoChild<=pagerPagecount(pPage->pBt->pPager) );
  5498   5512       rc = sqlite3BtreeGetPage(pPage->pBt, pgnoChild, &pChild, 0);
  5499   5513       if( rc ) goto end_shallow_balance;
  5500   5514       if( pPage->pgno==1 ){
  5501   5515         rc = sqlite3BtreeInitPage(pChild);
................................................................................
  5562   5576     u8 *cdata;          /* Content of the child page */
  5563   5577     int hdr;            /* Offset to page header in parent */
  5564   5578     int cbrk;           /* Offset to content of first cell in parent */
  5565   5579   
  5566   5580     assert( pCur->iPage==0 );
  5567   5581     assert( pCur->apPage[0]->nOverflow>0 );
  5568   5582   
         5583  +  VVA_ONLY( pCur->pagesShuffled = 1 );
  5569   5584     pPage = pCur->apPage[0];
  5570   5585     pBt = pPage->pBt;
  5571   5586     assert( sqlite3_mutex_held(pBt->mutex) );
  5572   5587     rc = allocateBtreePage(pBt, &pChild, &pgnoChild, pPage->pgno, 0);
  5573   5588     if( rc ) return rc;
  5574   5589     assert( sqlite3PagerIswriteable(pChild->pDbPage) );
  5575   5590     usableSize = pBt->usableSize;
................................................................................
  5810   5825     }
  5811   5826   end_insert:
  5812   5827     return rc;
  5813   5828   }
  5814   5829   
  5815   5830   /*
  5816   5831   ** Delete the entry that the cursor is pointing to.  The cursor
  5817         -** is left pointing at a random location.
         5832  +** is left pointing at a arbitrary location.
  5818   5833   */
  5819   5834   int sqlite3BtreeDelete(BtCursor *pCur){
  5820   5835     MemPage *pPage = pCur->apPage[pCur->iPage];
  5821   5836     int idx;
  5822   5837     unsigned char *pCell;
  5823   5838     int rc;
  5824   5839     Pgno pgnoChild = 0;
................................................................................
  5908   5923         tempCell = pBt->pTmpSpace;
  5909   5924         if( tempCell==0 ){
  5910   5925           rc = SQLITE_NOMEM;
  5911   5926         }
  5912   5927         if( rc==SQLITE_OK ){
  5913   5928           rc = insertCell(pPage, idx, pNext-4, szNext+4, tempCell, 0);
  5914   5929         }
         5930  +
         5931  +
         5932  +      /* The "if" statement in the next code block is critical.  The
         5933  +      ** slightest error in that statement would allow SQLite to operate
         5934  +      ** correctly most of the time but produce very rare failures.  To
         5935  +      ** guard against this, the following macros help to verify that
         5936  +      ** the "if" statement is well tested.
         5937  +      */
         5938  +      testcase( pPage->nOverflow==0 && pPage->nFree<pBt->usableSize*2/3 
         5939  +                 && pLeafPage->nFree+2+szNext > pBt->usableSize*2/3 );
         5940  +      testcase( pPage->nOverflow==0 && pPage->nFree==pBt->usableSize*2/3 
         5941  +                 && pLeafPage->nFree+2+szNext > pBt->usableSize*2/3 );
         5942  +      testcase( pPage->nOverflow==0 && pPage->nFree==pBt->usableSize*2/3+1 
         5943  +                 && pLeafPage->nFree+2+szNext > pBt->usableSize*2/3 );
         5944  +      testcase( pPage->nOverflow>0 && pPage->nFree<=pBt->usableSize*2/3
         5945  +                 && pLeafPage->nFree+2+szNext > pBt->usableSize*2/3 );
         5946  +      testcase( (pPage->nOverflow>0 || (pPage->nFree > pBt->usableSize*2/3))
         5947  +                 && pLeafPage->nFree+2+szNext == pBt->usableSize*2/3 );
         5948  +
  5915   5949   
  5916   5950         if( (pPage->nOverflow>0 || (pPage->nFree > pBt->usableSize*2/3)) &&
  5917   5951             (pLeafPage->nFree+2+szNext > pBt->usableSize*2/3)
  5918   5952         ){
  5919         -        /* This branch is taken if the internal node is now either over or
  5920         -        ** underfull and the leaf node will be underfull after the just cell 
         5953  +        /* This branch is taken if the internal node is now either overflowing
         5954  +        ** or underfull and the leaf node will be underfull after the just cell 
  5921   5955           ** copied to the internal node is deleted from it. This is a special
  5922   5956           ** case because the call to balance() to correct the internal node
  5923   5957           ** may change the tree structure and invalidate the contents of
  5924   5958           ** the leafCur.apPage[] and leafCur.aiIdx[] arrays, which will be
  5925   5959           ** used by the balance() required to correct the underfull leaf
  5926   5960           ** node.
  5927   5961           **
  5928   5962           ** The formula used in the expression above are based on facets of
  5929   5963           ** the SQLite file-format that do not change over time.
  5930   5964           */
         5965  +        testcase( pPage->nFree==pBt->usableSize*2/3+1 );
         5966  +        testcase( pLeafPage->nFree+2+szNext==pBt->usableSize*2/3+1 );
  5931   5967           leafCursorInvalid = 1;
  5932   5968         }        
  5933   5969   
  5934   5970         if( rc==SQLITE_OK ){
  5935   5971           put4byte(findOverflowCell(pPage, idx), pgnoChild);
         5972  +        VVA_ONLY( pCur->pagesShuffled = 0 );
  5936   5973           rc = balance(pCur, 0);
  5937   5974         }
  5938   5975   
  5939   5976         if( rc==SQLITE_OK && leafCursorInvalid ){
  5940   5977           /* The leaf-node is now underfull and so the tree needs to be 
  5941   5978           ** rebalanced. However, the balance() operation on the internal
  5942   5979           ** node above may have modified the structure of the B-Tree and
................................................................................
  5956   5993           ** calls restoreCursorPosition() to point the cursor to the copy
  5957   5994           ** stored on the internal node, then advances to the next entry,
  5958   5995           ** which happens to be the copy of the key on the internal node.
  5959   5996           ** Net effect: leafCur is pointing back to the duplicate cell
  5960   5997           ** that needs to be removed, and the leafCur.apPage[] and
  5961   5998           ** leafCur.aiIdx[] arrays are correct.
  5962   5999           */
  5963         -      #ifndef NDEBUG
  5964         -        Pgno leafPgno = pLeafPage->pgno;
  5965         -      #endif
         6000  +        VVA_ONLY( Pgno leafPgno = pLeafPage->pgno );
  5966   6001           rc = saveCursorPosition(&leafCur);
  5967   6002           if( rc==SQLITE_OK ){
  5968   6003             rc = sqlite3BtreeNext(&leafCur, &notUsed);
  5969   6004           }
  5970   6005           pLeafPage = leafCur.apPage[leafCur.iPage];
  5971   6006           assert( pLeafPage->pgno==leafPgno );
  5972   6007           assert( leafCur.aiIdx[leafCur.iPage]==0 );
  5973   6008         }
  5974   6009   
  5975   6010         if( rc==SQLITE_OK ){
  5976   6011           dropCell(pLeafPage, 0, szNext);
         6012  +        VVA_ONLY( leafCur.pagesShuffled = 0 );
  5977   6013           rc = balance(&leafCur, 0);
         6014  +        assert( leafCursorInvalid || !leafCur.pagesShuffled
         6015  +                                   || !pCur->pagesShuffled );
  5978   6016         }
  5979   6017       }
  5980   6018       sqlite3BtreeReleaseTempCursor(&leafCur);
  5981   6019     }else{
  5982   6020       TRACE(("DELETE: table=%d delete from leaf %d\n",
  5983   6021          pCur->pgnoRoot, pPage->pgno));
  5984   6022       dropCell(pPage, idx, cellSizePtr(pPage, pCell));

Changes to src/btreeInt.h.

     5      5   ** a legal notice, here is a blessing:
     6      6   **
     7      7   **    May you do good and not evil.
     8      8   **    May you find forgiveness for yourself and forgive others.
     9      9   **    May you share freely, never taking more than you give.
    10     10   **
    11     11   *************************************************************************
    12         -** $Id: btreeInt.h,v 1.33 2008/09/29 15:53:26 danielk1977 Exp $
           12  +** $Id: btreeInt.h,v 1.34 2008/09/30 17:18:17 drh Exp $
    13     13   **
    14     14   ** This file implements a external (disk-based) database using BTrees.
    15     15   ** For a detailed discussion of BTrees, refer to
    16     16   **
    17     17   **     Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
    18     18   **     "Sorting And Searching", pages 473-480. Addison-Wesley
    19     19   **     Publishing Company, Reading, Massachusetts.
................................................................................
   450    450     void *pKey;      /* Saved key that was cursor's last known position */
   451    451     i64 nKey;        /* Size of pKey, or last integer key */
   452    452     int skip;        /* (skip<0) -> Prev() is a no-op. (skip>0) -> Next() is */
   453    453   #ifndef SQLITE_OMIT_INCRBLOB
   454    454     u8 isIncrblobHandle;      /* True if this cursor is an incr. io handle */
   455    455     Pgno *aOverflow;          /* Cache of overflow page locations */
   456    456   #endif
   457         -
          457  +#ifndef NDEBUG
          458  +  u8 pagesShuffled;         /* True if Btree pages are rearranged by balance()*/
          459  +#endif
   458    460     i16 iPage;                            /* Index of current page in apPage */
   459    461     MemPage *apPage[BTCURSOR_MAX_DEPTH];  /* Pages from root to current page */
   460    462     u16 aiIdx[BTCURSOR_MAX_DEPTH];        /* Current index in apPage[i] */
   461    463   };
   462    464   
   463    465   /*
   464    466   ** Potential values for BtCursor.eState.