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

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.202 2004/11/03 11:37:08 danielk1977 Exp $
           12  +** $Id: btree.c,v 1.203 2004/11/04 02:57:34 danielk1977 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.
................................................................................
  1422   1422     data[20] = pBt->pageSize - pBt->usableSize;
  1423   1423     data[21] = pBt->maxEmbedFrac;
  1424   1424     data[22] = pBt->minEmbedFrac;
  1425   1425     data[23] = pBt->minLeafFrac;
  1426   1426     memset(&data[24], 0, 100-24);
  1427   1427     zeroPage(pP1, PTF_INTKEY|PTF_LEAF|PTF_LEAFDATA );
  1428   1428     pBt->pageSizeFixed = 1;
         1429  +#ifndef SQLITE_OMIT_AUTOVACUUM
         1430  +  if( pBt->autoVacuum ){
         1431  +    put4byte(&data[36 + 4*4], 1);
         1432  +  }
         1433  +#endif
  1429   1434     return SQLITE_OK;
  1430   1435   }
  1431   1436   
  1432   1437   /*
  1433   1438   ** Attempt to start a new transaction. A write-transaction
  1434   1439   ** is started if the second argument is nonzero, otherwise a read-
  1435   1440   ** transaction.  If the second argument is 2 or more and exclusive
................................................................................
  1602   1607         put4byte(&pPage->aData[pPage->hdrOffset+8], iTo);
  1603   1608       }
  1604   1609   
  1605   1610       pPage->isInit = isInitOrig;
  1606   1611     }
  1607   1612   }
  1608   1613   
         1614  +
         1615  +static int relocatePage(
         1616  +  Btree *pBt, 
         1617  +  MemPage *pDbPage,
         1618  +  u8 eType,
         1619  +  Pgno iPtrPage,
         1620  +  Pgno iFreePage
         1621  +){
         1622  +  MemPage *pPtrPage;   /* The page that contains a pointer to pDbPage */
         1623  +  Pgno iDbPage = pDbPage->pgno;
         1624  +  Pager *pPager = pBt->pPager;
         1625  +  int rc;
         1626  +
         1627  +  assert( eType==PTRMAP_OVERFLOW2 
         1628  +      || eType==PTRMAP_OVERFLOW1 || eType==PTRMAP_BTREE );
         1629  +
         1630  +  /* Move page iDbPage from it's current location to page number iFreePage */
         1631  +  TRACE(("AUTOVACUUM: Moving %d to free page %d (ptr page %d type %d)\n", 
         1632  +      iDbPage, iFreePage, iPtrPage, eType));
         1633  +  rc = sqlite3pager_movepage(pPager, pDbPage->aData, iFreePage);
         1634  +  if( rc!=SQLITE_OK ){
         1635  +    return rc;
         1636  +  }
         1637  +  pDbPage->pgno = iFreePage;
         1638  +
         1639  +  /* If pDbPage was a btree-page, then it may have child pages and/or cells
         1640  +  ** that point to overflow pages. The pointer map entries for all these
         1641  +  ** pages need to be changed.
         1642  +  **
         1643  +  ** If pDbPage is an overflow page, then the first 4 bytes may store a
         1644  +  ** pointer to a subsequent overflow page. If this is the case, then
         1645  +  ** the pointer map needs to be updated for the subsequent overflow page.
         1646  +  */
         1647  +  if( eType==PTRMAP_BTREE ){
         1648  +    rc = setChildPtrmaps(pDbPage);
         1649  +    if( rc!=SQLITE_OK ){
         1650  +      return rc;
         1651  +    }
         1652  +  }else{
         1653  +    Pgno nextOvfl = get4byte(pDbPage->aData);
         1654  +    if( nextOvfl!=0 ){
         1655  +      assert( nextOvfl<=sqlite3pager_pagecount(pPager) );
         1656  +      rc = ptrmapPut(pBt, nextOvfl, PTRMAP_OVERFLOW2, iFreePage);
         1657  +      if( rc!=SQLITE_OK ){
         1658  +        return rc;
         1659  +      }
         1660  +    }
         1661  +  }
         1662  +
         1663  +  /* Fix the database pointer on page iPtrPage that pointed at iDbPage so
         1664  +  ** that it points at iFreePage. Also fix the pointer map entry for
         1665  +  ** iPtrPage.
         1666  +  */
         1667  +  rc = getPage(pBt, iPtrPage, &pPtrPage);
         1668  +  if( rc!=SQLITE_OK ){
         1669  +    return rc;
         1670  +  }
         1671  +  rc = sqlite3pager_write(pPtrPage->aData);
         1672  +  if( rc!=SQLITE_OK ){
         1673  +    releasePage(pPtrPage);
         1674  +    return rc;
         1675  +  }
         1676  +  modifyPagePointer(pPtrPage, iDbPage, iFreePage, eType);
         1677  +  rc = ptrmapPut(pBt, iFreePage, eType, iPtrPage);
         1678  +  releasePage(pPtrPage);
         1679  +  return rc;
         1680  +}
         1681  +
  1609   1682   /* Forward declaration required by autoVacuumCommit(). */
  1610   1683   static int allocatePage(Btree *, MemPage **, Pgno *, Pgno);
  1611   1684   
  1612   1685   /*
  1613   1686   ** This routine is called prior to sqlite3pager_commit when a transaction
  1614   1687   ** is commited for an auto-vacuum database.
  1615   1688   */
................................................................................
  1620   1693     Pgno origSize;  /* Pages in the database file */
  1621   1694     Pgno finSize;   /* Pages in the database file after truncation */
  1622   1695     int i;            /* Counter variable */
  1623   1696     int rc;           /* Return code */
  1624   1697     u8 eType;
  1625   1698     int pgsz = pBt->pageSize;  /* Page size for this database */
  1626   1699     Pgno iDbPage;              /* The database page to move */
  1627         -  u8 *pDbPage = 0;           /* "" */
  1628   1700     MemPage *pDbMemPage = 0;   /* "" */
  1629   1701     Pgno iPtrPage;             /* The page that contains a pointer to iDbPage */
  1630         -  MemPage *pPtrMemPage = 0;  /* "" */
  1631   1702     Pgno iFreePage;            /* The free-list page to move iDbPage to */
  1632   1703     MemPage *pFreeMemPage = 0; /* "" */
  1633   1704   
  1634   1705   #ifndef NDEBUG
  1635   1706     int nRef = *sqlite3pager_stats(pPager);
  1636   1707   #endif
  1637   1708   
................................................................................
  1681   1752   
  1682   1753       /* If iDbPage is a free or pointer map page, do not swap it. */
  1683   1754       if( eType==PTRMAP_FREEPAGE || PTRMAP_ISPAGE(pgsz, iDbPage) ){
  1684   1755         continue;
  1685   1756       }
  1686   1757       rc = getPage(pBt, iDbPage, &pDbMemPage);
  1687   1758       if( rc!=SQLITE_OK ) goto autovacuum_out;
  1688         -    pDbPage = pDbMemPage->aData;
  1689   1759   
  1690   1760       /* Find the next page in the free-list that is not already at the end 
  1691   1761       ** of the file. A page can be pulled off the free list using the 
  1692   1762       ** allocatePage() routine.
  1693   1763       */
  1694   1764       do{
  1695   1765         if( pFreeMemPage ){
................................................................................
  1696   1766           releasePage(pFreeMemPage);
  1697   1767           pFreeMemPage = 0;
  1698   1768         }
  1699   1769         rc = allocatePage(pBt, &pFreeMemPage, &iFreePage, 0);
  1700   1770         if( rc!=SQLITE_OK ) goto autovacuum_out;
  1701   1771         assert( iFreePage<=origSize );
  1702   1772       }while( iFreePage>finSize );
  1703         -
  1704         -    /* Move page iDbPage from it's current location to page number iFreePage */
  1705         -    TRACE(("AUTOVACUUM: Moving %d to free page %d (ptr page %d type %d)\n", 
  1706         -        iDbPage, iFreePage, iPtrPage, eType));
  1707   1773       releasePage(pFreeMemPage);
  1708   1774       pFreeMemPage = 0;
  1709         -    rc = sqlite3pager_movepage(pPager, pDbPage, iFreePage);
  1710         -    if( rc!=SQLITE_OK ) goto autovacuum_out;
  1711         -    pDbMemPage->pgno = iFreePage;
  1712   1775   
  1713         -    /* If pDbPage was a btree-page, then it may have child pages and/or cells
  1714         -    ** that point to overflow pages. The pointer map entries for all these
  1715         -    ** pages need to be changed.
  1716         -    **
  1717         -    ** If pDbPage is an overflow page, then the first 4 bytes may store a
  1718         -    ** pointer to a subsequent overflow page. If this is the case, then
  1719         -    ** the pointer map needs to be updated for the subsequent overflow page.
  1720         -    */
  1721         -    if( eType==PTRMAP_BTREE ){
  1722         -      rc = setChildPtrmaps(pDbMemPage);
  1723         -      if( rc!=SQLITE_OK ) goto autovacuum_out;
  1724         -    }else{
  1725         -      Pgno nextOvfl = get4byte(pDbPage);
  1726         -      if( nextOvfl!=0 ){
  1727         -        assert( nextOvfl<=origSize );
  1728         -        rc = ptrmapPut(pBt, nextOvfl, PTRMAP_OVERFLOW2, iFreePage);
  1729         -        if( rc!=SQLITE_OK ) goto autovacuum_out;
  1730         -      }
  1731         -    }
         1776  +    rc = relocatePage(pBt, pDbMemPage, eType, iPtrPage, iFreePage);
  1732   1777       releasePage(pDbMemPage);
  1733         -    pDbMemPage = 0;
  1734         -
  1735         -    /* Fix the database pointer on page iPtrPage that pointed at iDbPage so
  1736         -    ** that it points at iFreePage. Also fix the pointer map entry for
  1737         -    ** iPtrPage.
  1738         -    */
  1739         -    rc = getPage(pBt, iPtrPage, &pPtrMemPage);
  1740   1778       if( rc!=SQLITE_OK ) goto autovacuum_out;
  1741         -    rc = sqlite3pager_write(pPtrMemPage->aData);
  1742         -    if( rc!=SQLITE_OK ) goto autovacuum_out;
  1743         -    modifyPagePointer(pPtrMemPage, iDbPage, iFreePage, eType);
  1744         -    rc = ptrmapPut(pBt, iFreePage, eType, iPtrPage);
  1745         -    if( rc!=SQLITE_OK ) goto autovacuum_out;
  1746         -    releasePage(pPtrMemPage);
  1747   1779     }
  1748   1780   
  1749   1781     /* The entire free-list has been swapped to the end of the file. So
  1750   1782     ** truncate the database file to finSize pages and consider the
  1751   1783     ** free-list empty.
  1752   1784     */
  1753   1785     rc = sqlite3pager_write(pBt->pPage1->aData);
................................................................................
  4194   4226   **     BTREE_INTKEY|BTREE_LEAFDATA     Used for SQL tables with rowid keys
  4195   4227   **     BTREE_ZERODATA                  Used for SQL indices
  4196   4228   */
  4197   4229   int sqlite3BtreeCreateTable(Btree *pBt, int *piTable, int flags){
  4198   4230     MemPage *pRoot;
  4199   4231     Pgno pgnoRoot;
  4200   4232     int rc;
         4233  +/* TODO: Disallow schema modifications if there are open cursors */
  4201   4234     if( pBt->inTrans!=TRANS_WRITE ){
  4202   4235       /* Must start a transaction first */
  4203   4236       return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  4204   4237     }
  4205   4238     if( pBt->readOnly ){
  4206   4239       return SQLITE_READONLY;
  4207   4240     }
         4241  +#ifdef SQLITE_OMIT_AUTOVACUUM
  4208   4242     rc = allocatePage(pBt, &pRoot, &pgnoRoot, 1);
  4209   4243     if( rc ) return rc;
  4210         -#ifndef SQLITE_OMIT_AUTOVACUUM
  4211         -  /* Note: This is temporary code for use during development of auto-vacuum. 
  4212         -  ** There should be no need for a pointer map entry for root-pages.
  4213         -  */
         4244  +#else
  4214   4245     if( pBt->autoVacuum ){
         4246  +    Pgno pgnoMove;      /* Move a page here to make room for the root-page */
         4247  +    MemPage *pPageMove; /* The page to move to. */
         4248  +
         4249  +    /* Run the auto-vacuum code to ensure the free-list is empty. This is
         4250  +    ** not really necessary, but it avoids complications in dealing with
         4251  +    ** a free-list in the code below.
         4252  +    ** TODO: This may need to be revisited.
         4253  +    */
         4254  +    rc = autoVacuumCommit(pBt);
         4255  +    if( rc!=SQLITE_OK ) return rc;
         4256  +
         4257  +    /* Read the value of meta[3] from the database to determine where the
         4258  +    ** root page of the new table should go. meta[3] is the largest root-page
         4259  +    ** created so far, so the new root-page is (meta[3]+1).
         4260  +    */
         4261  +    rc = sqlite3BtreeGetMeta(pBt, 4, &pgnoRoot);
         4262  +    if( rc!=SQLITE_OK ) return rc;
         4263  +    pgnoRoot++;
         4264  +
         4265  +    /* The new root-page may not be allocated on a pointer-map page. */
         4266  +    if( pgnoRoot==PTRMAP_PAGENO(pBt->pageSize, pgnoRoot) ){
         4267  +      pgnoRoot++;
         4268  +    }
         4269  +    assert( pgnoRoot>=3 );
         4270  +
         4271  +    /* Allocate a page. The page that currently resides at pgnoRoot will
         4272  +    ** be moved to the allocated page (unless the allocated page happens
         4273  +    ** to reside at pgnoRoot).
         4274  +    */
         4275  +    rc = allocatePage(pBt, &pPageMove, &pgnoMove, 0);
         4276  +    if( rc!=SQLITE_OK ){
         4277  +      return rc;
         4278  +    }
         4279  +
         4280  +    if( pgnoMove!=pgnoRoot ){
         4281  +      u8 eType;
         4282  +      Pgno iPtrPage;
         4283  +
         4284  +      releasePage(pPageMove);
         4285  +      rc = getPage(pBt, pgnoRoot, &pRoot);
         4286  +      if( rc!=SQLITE_OK ){
         4287  +        return rc;
         4288  +      }
         4289  +      rc = ptrmapGet(pBt, pgnoRoot, &eType, &iPtrPage);
         4290  +      if( rc!=SQLITE_OK ){
         4291  +        releasePage(pRoot);
         4292  +        return rc;
         4293  +      }
         4294  +      rc = relocatePage(pBt, pRoot, eType, iPtrPage, pgnoMove);
         4295  +      releasePage(pRoot);
         4296  +      if( rc!=SQLITE_OK ){
         4297  +        return rc;
         4298  +      }
         4299  +      rc = getPage(pBt, pgnoRoot, &pRoot);
         4300  +      if( rc!=SQLITE_OK ){
         4301  +        return rc;
         4302  +      }
         4303  +      rc = sqlite3pager_write(pRoot->aData);
         4304  +      if( rc!=SQLITE_OK ){
         4305  +        releasePage(pRoot);
         4306  +        return rc;
         4307  +      }
         4308  +    }else{
         4309  +      pRoot = pPageMove;
         4310  +    } 
         4311  +
  4215   4312       rc = ptrmapPut(pBt, pgnoRoot, PTRMAP_ROOTPAGE, 0);
  4216   4313       if( rc ){
  4217         -      sqlite3pager_unref(pRoot->aData);
         4314  +      releasePage(pRoot);
         4315  +      return rc;
         4316  +    }
         4317  +    rc = sqlite3BtreeUpdateMeta(pBt, 4, pgnoRoot);
         4318  +    if( rc ){
         4319  +      releasePage(pRoot);
  4218   4320         return rc;
  4219   4321       }
         4322  +  }else{
         4323  +    rc = allocatePage(pBt, &pRoot, &pgnoRoot, 1);
         4324  +    if( rc ) return rc;
  4220   4325     }
  4221   4326   #endif
  4222   4327     assert( sqlite3pager_iswriteable(pRoot->aData) );
  4223   4328     zeroPage(pRoot, flags | PTF_LEAF);
  4224   4329     sqlite3pager_unref(pRoot->aData);
  4225   4330     *piTable = (int)pgnoRoot;
  4226   4331     return SQLITE_OK;
................................................................................
  4303   4408   ** This routine will fail with SQLITE_LOCKED if there are any open
  4304   4409   ** cursors on the table.
  4305   4410   */
  4306   4411   int sqlite3BtreeDropTable(Btree *pBt, int iTable){
  4307   4412     int rc;
  4308   4413     MemPage *pPage;
  4309   4414     BtCursor *pCur;
         4415  +/* TODO: Disallow schema modifications if there are open cursors */
  4310   4416     if( pBt->inTrans!=TRANS_WRITE ){
  4311   4417       return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  4312   4418     }
  4313   4419     for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){
  4314   4420       if( pCur->pgnoRoot==(Pgno)iTable ){
  4315   4421         return SQLITE_LOCKED;  /* Cannot drop a table that has a cursor */
  4316   4422       }
................................................................................
  4347   4453     rc = sqlite3pager_get(pBt->pPager, 1, (void**)&pP1);
  4348   4454     if( rc ) return rc;
  4349   4455     *pMeta = get4byte(&pP1[36 + idx*4]);
  4350   4456     sqlite3pager_unref(pP1);
  4351   4457   
  4352   4458     /* The current implementation is unable to handle writes to an autovacuumed
  4353   4459     ** database.  So make such a database readonly. */
         4460  +#ifdef SQLITE_OMIT_AUTOVACUUM
  4354   4461     if( idx==4 && *pMeta>0 ) pBt->readOnly = 1;
         4462  +#endif
  4355   4463   
  4356   4464     return SQLITE_OK;
  4357   4465   }
  4358   4466   
  4359   4467   /*
  4360   4468   ** Write meta-information back into the database.  Meta[0] is
  4361   4469   ** read-only and may not be written.

Changes to test/autovacuum.test.

     7      7   #    May you find forgiveness for yourself and forgive others.
     8      8   #    May you share freely, never taking more than you give.
     9      9   #
    10     10   #***********************************************************************
    11     11   # This file implements regression tests for SQLite library.  The
    12     12   # focus of this file is testing the SELECT statement.
    13     13   #
    14         -# $Id: autovacuum.test,v 1.4 2004/11/03 09:30:55 danielk1977 Exp $
           14  +# $Id: autovacuum.test,v 1.5 2004/11/04 02:57:35 danielk1977 Exp $
    15     15   
    16     16   set testdir [file dirname $argv0]
    17     17   source $testdir/tester.tcl
    18     18   
    19     19   # Return a string $len characters long. The returned string is $char repeated
    20     20   # over and over. For example, [make_str abc 8] returns "abcabcab".
    21     21   proc make_str {char len} {
................................................................................
   107    107     }
   108    108   
   109    109     # All rows have been deleted. Ensure the file has shrunk to 4 pages.
   110    110     do_test autovacuum-1.$tn.3 {
   111    111       file_pages
   112    112     } {4}
   113    113   }
          114  +
          115  +# Tests autovacuum-2.* test that root pages are allocated correctly at
          116  +# the start of the file.
          117  +do_test autovacuum-2.1 {
          118  +  for {set i 0} {$i<5} {incr i} {
          119  +    execsql "
          120  +      INSERT INTO av1 VALUES('[make_str abc 1000]')
          121  +    "
          122  +  }
          123  +  file_pages 
          124  +} {14}
          125  +
          126  +for {set i 5} {$i < 15} {incr i} {
          127  +  set tablename "av$i"
          128  +  
          129  +  do_test autovacuum-2.$i.2 {
          130  +    execsql "
          131  +      CREATE TABLE $tablename (a);
          132  +      SELECT rootpage FROM sqlite_master WHERE name = '$tablename';
          133  +    "
          134  +  } $i
          135  +
          136  +  do_test autovacuum-2.$i.3 {
          137  +    file_pages 
          138  +  } [expr $i+10]
          139  +
          140  +  do_test autovacuum-2.$i.4 {
          141  +    execsql {
          142  +      pragma integrity_check
          143  +    }
          144  +  } {ok}
          145  +}
          146  +
   114    147   
   115    148   finish_test
   116    149