/ Check-in [2c912794]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:More BTree tests and a few bug fixes. (CVS 231)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:2c9127943cd5a541613924d2df773c4e8df4c1a6
User & Date: drh 2001-06-28 11:50:22
Context
2001-06-30
21:53
Implemented the sqliteBtreeSanityCheck() test function. (CVS 232) check-in: 42486880 user: drh tags: trunk
2001-06-28
11:50
More BTree tests and a few bug fixes. (CVS 231) check-in: 2c912794 user: drh tags: trunk
01:54
Got a lot of BTree tests working. Still lots more needed. (CVS 230) check-in: 9cfeeb58 user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/btree.c.

    17     17   ** Boston, MA  02111-1307, USA.
    18     18   **
    19     19   ** Author contact information:
    20     20   **   drh@hwaci.com
    21     21   **   http://www.hwaci.com/drh/
    22     22   **
    23     23   *************************************************************************
    24         -** $Id: btree.c,v 1.16 2001/06/28 01:54:48 drh Exp $
           24  +** $Id: btree.c,v 1.17 2001/06/28 11:50:22 drh Exp $
    25     25   **
    26     26   ** This file implements a external (disk-based) database using BTrees.
    27     27   ** For a detailed discussion of BTrees, refer to
    28     28   **
    29     29   **     Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
    30     30   **     "Sorting And Searching", pages 473-480. Addison-Wesley
    31     31   **     Publishing Company, Reading, Massachusetts.
................................................................................
  1619   1619     int idx;                     /* Index of pPage in pParent->apCell[] */
  1620   1620     int nxDiv;                   /* Next divider slot in pParent->apCell[] */
  1621   1621     int rc;                      /* The return code */
  1622   1622     int iCur;                    /* apCell[iCur] is the cell of the cursor */
  1623   1623     int usedPerPage;             /* Memory needed for each page */
  1624   1624     int freePerPage;             /* Average free space per page */
  1625   1625     int totalSize;               /* Total bytes for all cells */
         1626  +  MemPage *extraUnref = 0;     /* A page that needs to be unref-ed */
  1626   1627     Pgno pgno;                   /* Page number */
  1627   1628     Cell *apCell[MX_CELL*3+5];   /* All cells from pages being balanceed */
  1628   1629     int szCell[MX_CELL*3+5];     /* Local size of all cells */
  1629   1630     Cell aTemp[2];               /* Temporary holding area for apDiv[] */
  1630   1631     MemPage aOld[3];             /* Temporary copies of pPage and its siblings */
  1631   1632   
  1632   1633     /* 
................................................................................
  1689   1690       copyPage(pChild, pPage);
  1690   1691       pChild->pParent = pPage;
  1691   1692       sqlitepager_ref(pPage);
  1692   1693       pChild->isOverfull = 1;
  1693   1694       if( pCur ){
  1694   1695         sqlitepager_unref(pCur->pPage);
  1695   1696         pCur->pPage = pChild;
         1697  +    }else{
         1698  +      extraUnref = pChild;
  1696   1699       }
  1697   1700       zeroPage(pPage);
  1698   1701       pPage->u.hdr.rightChild = pgnoChild;
  1699   1702       pParent = pPage;
  1700   1703       pPage = pChild;
  1701   1704     }else{
  1702   1705       rc = sqlitepager_write(pPage);
................................................................................
  1763   1766     /*
  1764   1767     ** Set iCur to be the index in apCell[] of the cell that the cursor
  1765   1768     ** is pointing to.  We will need this later on in order to keep the
  1766   1769     ** cursor pointing at the same cell.
  1767   1770     */
  1768   1771     if( pCur ){
  1769   1772       iCur = pCur->idx;
  1770         -    for(i=0; idxDiv[i]<idx; i++){
         1773  +    for(i=0; i<nDiv && idxDiv[i]<idx; i++){
  1771   1774         iCur += apOld[i]->nCell + 1;
  1772   1775       }
  1773   1776       sqlitepager_unref(pCur->pPage);
  1774   1777       pCur->pPage = 0;
  1775   1778     }
  1776   1779   
  1777   1780     /*
................................................................................
  1884   1887     */
  1885   1888     rc = balance(pBt, pParent, 0);
  1886   1889   
  1887   1890     /*
  1888   1891     ** Cleanup before returning.
  1889   1892     */
  1890   1893   balance_cleanup:
         1894  +  if( extraUnref ){
         1895  +    sqlitepager_unref(extraUnref);
         1896  +  }
  1891   1897     for(i=0; i<nOld; i++){
  1892   1898       if( apOld[i]!=&aOld[i] ) sqlitepager_unref(apOld[i]);
  1893   1899     }
  1894   1900     for(i=0; i<nNew; i++){
  1895   1901       sqlitepager_unref(apNew[i]);
  1896   1902     }
  1897   1903     if( pCur && pCur->pPage==0 ){
................................................................................
  1971   1977       return SQLITE_ERROR;  /* The cursor is not pointing to anything */
  1972   1978     }
  1973   1979     rc = sqlitepager_write(pPage);
  1974   1980     if( rc ) return rc;
  1975   1981     pCell = pPage->apCell[pCur->idx];
  1976   1982     pgnoChild = pCell->h.leftChild;
  1977   1983     clearCell(pCur->pBt, pCell);
  1978         -  dropCell(pPage, pCur->idx, cellSize(pCell));
  1979   1984     if( pgnoChild ){
  1980   1985       /*
  1981         -    ** If the entry we just deleted is not a leaf, then we've left a
  1982         -    ** hole in an internal page.  We have to fill the hole by moving
  1983         -    ** in a cell from a leaf.  The next Cell after the one just deleted
  1984         -    ** is guaranteed to exist and to be a leaf so we can use it.
         1986  +    ** If the entry we are about to delete is not a leaf so if we do not
         1987  +    ** do something we will leave a hole on an internal page.
         1988  +    ** We have to fill the hole by moving in a cell from a leaf.  The
         1989  +    ** next Cell after the one to be deleted is guaranteed to exist and
         1990  +    ** to be a leaf so we can use it.
  1985   1991       */
  1986   1992       BtCursor leafCur;
  1987   1993       Cell *pNext;
  1988   1994       int szNext;
  1989   1995       getTempCursor(pCur, &leafCur);
  1990   1996       rc = sqliteBtreeNext(&leafCur, 0);
  1991   1997       if( rc!=SQLITE_OK ){
  1992   1998         return SQLITE_CORRUPT;
  1993   1999       }
         2000  +    dropCell(pPage, pCur->idx, cellSize(pCell));
  1994   2001       pNext = leafCur.pPage->apCell[leafCur.idx];
  1995   2002       szNext = cellSize(pNext);
  1996   2003       pNext->h.leftChild = pgnoChild;
  1997   2004       insertCell(pPage, pCur->idx, pNext, szNext);
  1998   2005       rc = balance(pCur->pBt, pPage, pCur);
  1999   2006       if( rc ) return rc;
  2000   2007       pCur->bSkipNext = 1;
  2001   2008       dropCell(leafCur.pPage, leafCur.idx, szNext);
  2002   2009       rc = balance(pCur->pBt, leafCur.pPage, 0);
  2003   2010       releaseTempCursor(&leafCur);
  2004   2011     }else{
         2012  +    dropCell(pPage, pCur->idx, cellSize(pCell));
  2005   2013       rc = balance(pCur->pBt, pPage, pCur);
  2006   2014       pCur->bSkipNext = 1;
  2007   2015     }
  2008   2016     return rc;
  2009   2017   }
  2010   2018   
  2011   2019   /*

Changes to test/btree.test.

    19     19   #   drh@hwaci.com
    20     20   #   http://www.hwaci.com/drh/
    21     21   #
    22     22   #***********************************************************************
    23     23   # This file implements regression tests for SQLite library.  The
    24     24   # focus of this script is btree database backend
    25     25   #
    26         -# $Id: btree.test,v 1.3 2001/06/28 01:54:50 drh Exp $
           26  +# $Id: btree.test,v 1.4 2001/06/28 11:50:22 drh Exp $
    27     27   
    28     28   
    29     29   set testdir [file dirname $argv0]
    30     30   source $testdir/tester.tcl
    31     31   
    32     32   if {$dbprefix!="memory:" && [info commands btree_open]!=""} {
    33     33   
................................................................................
   786    786     btree_close_cursor $::c1
   787    787     lindex [btree_pager_stats $::b1] 1
   788    788   } {1}
   789    789   do_test btree-9.7 {
   790    790     btree_rollback $::b1
   791    791     lindex [btree_pager_stats $::b1] 1
   792    792   } {0}
          793  +
          794  +# Create a tree of depth two.  That is, there is a single divider entry
          795  +# on the root pages and two leaf pages.  Then delete the divider entry
          796  +# see what happens.
          797  +#
          798  +do_test btree-10.1 {
          799  +  btree_begin_transaction $::b1
          800  +  btree_drop_table $::b1 2
          801  +  lindex [btree_pager_stats $::b1] 1
          802  +} {1}
          803  +do_test btree-10.2 {
          804  +  set ::c1 [btree_cursor $::b1 2]
          805  +  lindex [btree_pager_stats $::b1] 1
          806  +} {2}
          807  +do_test btree-10.3 {
          808  +  for {set i 1} {$i<=20} {incr i} {
          809  +    set key [format %03d $i]
          810  +    set data "*** $key *** $key *** $key *** $key ***"
          811  +    btree_insert $::c1 $key $data
          812  +  }
          813  +  select_keys $::c1
          814  +} {001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020}
          815  +#btree_page_dump $::b1 7
          816  +#btree_page_dump $::b1 2
          817  +#btree_page_dump $::b1 6
          818  +do_test btree-10.4 {
          819  +  btree_move_to $::c1 011
          820  +  btree_delete $::c1
          821  +  select_keys $::c1
          822  +} {001 002 003 004 005 006 007 008 009 010 012 013 014 015 016 017 018 019 020}
          823  +#btree_page_dump $::b1 2
          824  +for {set i 1} {$i<=20} {incr i} {
          825  +  do_test btree-10.5.$i {
          826  +    btree_move_to $::c1 [format %03d $i]
          827  +    lindex [btree_pager_stats $::b1] 1
          828  +  } {2}
          829  +}
          830  +
          831  +# Create a tree with lots more pages
          832  +#
          833  +catch {unset ::data}
          834  +catch {unset ::key}
          835  +for {set i 21} {$i<=1000} {incr i} {
          836  +  do_test btree-11.1.$i.1 {
          837  +    set key [format %03d $i]
          838  +    set ::data "*** $key *** $key *** $key *** $key ***"
          839  +    btree_insert $::c1 $key $data
          840  +    btree_key $::c1
          841  +  } [format %03d $i]
          842  +  do_test btree-11.1.$i.2 {
          843  +    btree_data $::c1
          844  +  } $::data
          845  +  set ::key [format %03d [expr {$i/2}]]
          846  +  if {$::key=="011"} {set ::key 010}
          847  +  do_test btree-11.1.$i.3 {
          848  +    btree_move_to $::c1 $::key
          849  +    btree_key $::c1
          850  +  } $::key
          851  +}
          852  +catch {unset ::data}
          853  +catch {unset ::key}
          854  +
          855  +# Make sure our reference count is still correct.
          856  +#
          857  +do_test btree-11.2 {
          858  +  btree_close_cursor $::c1
          859  +  lindex [btree_pager_stats $::b1] 1
          860  +} {1}
          861  +do_test btree-11.3 {
          862  +  set ::c1 [btree_cursor $::b1 2]
          863  +  lindex [btree_pager_stats $::b1] 1
          864  +} {2}
          865  +#btree_page_dump $::b1 2
          866  +
          867  +# Delete the dividers on the root page
          868  +#
          869  +do_test btree-11.4 {
          870  +  btree_move_to $::c1 257
          871  +  btree_delete $::c1
          872  +  btree_next $::c1
          873  +  btree_key $::c1
          874  +} {258}
          875  +do_test btree-11.4.1 {
          876  +  btree_move_to $::c1 256
          877  +  btree_key $::c1
          878  +} {256}
          879  +do_test btree-11.4.2 {
          880  +  btree_move_to $::c1 258
          881  +  btree_key $::c1
          882  +} {258}
          883  +do_test btree-11.4.3 {
          884  +  btree_move_to $::c1 259
          885  +  btree_key $::c1
          886  +} {259}
          887  +do_test btree-11.4.4 {
          888  +  btree_move_to $::c1 257
          889  +  btree_key $::c1
          890  +} {256}
          891  +do_test btree-11.5 {
          892  +  btree_move_to $::c1 513
          893  +  btree_delete $::c1
          894  +  btree_next $::c1
          895  +  btree_key $::c1
          896  +} {514}
          897  +do_test btree-11.5.1 {
          898  +  btree_move_to $::c1 512
          899  +  btree_key $::c1
          900  +} {512}
          901  +do_test btree-11.5.2 {
          902  +  btree_move_to $::c1 514
          903  +  btree_key $::c1
          904  +} {514}
          905  +do_test btree-11.5.3 {
          906  +  btree_move_to $::c1 515
          907  +  btree_key $::c1
          908  +} {515}
          909  +do_test btree-11.5.4 {
          910  +  btree_move_to $::c1 513
          911  +  btree_key $::c1
          912  +} {512}
          913  +do_test btree-11.6 {
          914  +  btree_move_to $::c1 769
          915  +  btree_delete $::c1
          916  +  btree_next $::c1
          917  +  btree_key $::c1
          918  +} {770}
          919  +do_test btree-11.6.1 {
          920  +  btree_move_to $::c1 768
          921  +  btree_key $::c1
          922  +} {768}
          923  +do_test btree-11.6.2 {
          924  +  btree_move_to $::c1 771
          925  +  btree_key $::c1
          926  +} {771}
          927  +do_test btree-11.6.3 {
          928  +  btree_move_to $::c1 770
          929  +  btree_key $::c1
          930  +} {770}
          931  +do_test btree-11.6.4 {
          932  +  btree_move_to $::c1 769
          933  +  btree_key $::c1
          934  +} {768}
          935  +#btree_page_dump $::b1 2
          936  +#btree_page_dump $::b1 25
          937  +
          938  +# Change the data on an intermediate node such that the node becomes overfull
          939  +# and has to split.  We happen to know that intermediate nodes exist on
          940  +# 337, 401 and 465 by the btree_page_dumps above
          941  +#
          942  +catch {unset ::data}
          943  +set ::data {This is going to be a very long data segment}
          944  +append ::data $::data
          945  +append ::data $::data
          946  +do_test btree-12.1 {
          947  +  btree_insert $::c1 337 $::data
          948  +  btree_data $::c1
          949  +} $::data
          950  +do_test btree-12.2 {
          951  +  btree_insert $::c1 401 $::data
          952  +  btree_data $::c1
          953  +} $::data
          954  +do_test btree-12.3 {
          955  +  btree_insert $::c1 465 $::data
          956  +  btree_data $::c1
          957  +} $::data
          958  +do_test btree-12.4 {
          959  +  btree_move_to $::c1 337
          960  +  btree_key $::c1
          961  +} {337}
          962  +do_test btree-12.5 {
          963  +  btree_data $::c1
          964  +} $::data
          965  +do_test btree-12.6 {
          966  +  btree_next $::c1
          967  +  btree_key $::c1
          968  +} {338}
          969  +do_test btree-12.7 {
          970  +  btree_move_to $::c1 464
          971  +  btree_key $::c1
          972  +} {464}
          973  +do_test btree-12.8 {
          974  +  btree_next $::c1
          975  +  btree_data $::c1
          976  +} $::data
          977  +do_test btree-12.9 {
          978  +  btree_next $::c1
          979  +  btree_key $::c1
          980  +} {466}
          981  +do_test btree-12.10 {
          982  +  btree_move_to $::c1 400
          983  +  btree_key $::c1
          984  +} {400}
          985  +do_test btree-12.11 {
          986  +  btree_next $::c1
          987  +  btree_data $::c1
          988  +} $::data
          989  +do_test btree-12.12 {
          990  +  btree_next $::c1
          991  +  btree_key $::c1
          992  +} {402}
          993  +
          994  +# To Do:
          995  +#
          996  +#   1.  Do some deletes from the 3-layer tree
          997  +#   2.  Commit and reopen the database
          998  +#   3.  Read every 15th entry and make sure it works
          999  +#   4.  Implement btree_sanity and put it throughout this script
         1000  +#
         1001  +
         1002  +do_test btree-10.98 {
         1003  +  btree_close_cursor $::c1
         1004  +  lindex [btree_pager_stats $::b1] 1
         1005  +} {1}
         1006  +do_test btree-10.99 {
         1007  +  btree_rollback $::b1
         1008  +  lindex [btree_pager_stats $::b1] 1
         1009  +} {0}
         1010  +btree_pager_ref_dump $::b1
   793   1011   
   794   1012   do_test btree-99.1 {
   795   1013     btree_close $::b1
   796   1014   } {}
   797   1015   catch {unset data}
   798   1016   catch {unset key}
   799   1017   
   800   1018   } ;# end if( not mem: and has pager_open command );
   801   1019   
   802   1020   finish_test