** 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.197 2004/11/02 14:24:34 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.
................................................................................
**
** PTRMAP_OVERFLOW2: pPage is an overflow-page. The pointer points at the next
**                   overflow page in the list.
*/
static void modifyPagePointer(MemPage *pPage, Pgno iFrom, Pgno iTo, u8 eType){

  if( eType==PTRMAP_OVERFLOW2 ){

    assert( get4byte(pPage->aData)==iFrom );
    put4byte(pPage->aData, iFrom);
  }else{
    int isInitOrig = pPage->isInit;
    int i;
    int nCell;

    initPage(pPage, 0);
    nCell = pPage->nCell;

   /*  assert( !pPage->leaf && eType==PTRMAP_BTREE ); */

    for(i=0; i<nCell; i++){
      u8 *pCell = findCell(pPage, i);
      if( eType==PTRMAP_OVERFLOW1 ){
        CellInfo info;
        parseCellPtr(pPage, pCell, &info);
        if( info.iOverflow ){
          if( iFrom==get4byte(&pCell[info.iOverflow]) ){
................................................................................
      }
      rc = allocatePage(pBt, &pFreeMemPage, &iFreePage, 0);
      if( rc!=SQLITE_OK ) goto autovacuum_out;
      assert( iFreePage<=origDbSize );
    }while( iFreePage>finDbSize );

    /* Move page iDbPage from it's current location to page number iFreePage */
    TRACE(("AUTOVACUUM: Moving %d to free page %d (ptr page %d)\n", 
        iDbPage, iFreePage, iPtrPage));
    releasePage(pFreeMemPage);
    pFreeMemPage = 0;
    rc = sqlite3pager_movepage(pPager, pDbPage, iFreePage);
    if( rc!=SQLITE_OK ) goto autovacuum_out;
    pDbMemPage->pgno = iFreePage;

    /* If pDbPage was a btree-page, then it may have child pages and/or cells
    ** that point to overflow pages. The pointer map entries for all these
    ** pages need to be changed.




    */
    if( eType==PTRMAP_BTREE ){
      rc = setChildPtrmaps(pDbMemPage);
      if( rc!=SQLITE_OK ) goto autovacuum_out;







    }
    releasePage(pDbMemPage);
    pDbMemPage = 0;

    /* Fix the database pointer on page iPtrPage that pointed at iDbPage so
    ** that it points at iFreePage. Also fix the pointer map entry for
    ** iPtrPage.

** 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.198 2004/11/02 14:40:32 danielk1977 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.
................................................................................
**
** PTRMAP_OVERFLOW2: pPage is an overflow-page. The pointer points at the next
**                   overflow page in the list.
*/
static void modifyPagePointer(MemPage *pPage, Pgno iFrom, Pgno iTo, u8 eType){

  if( eType==PTRMAP_OVERFLOW2 ){
    /* The pointer is always the first 4 bytes of the page in this case.  */
    assert( get4byte(pPage->aData)==iFrom );
    put4byte(pPage->aData, iTo);
  }else{
    int isInitOrig = pPage->isInit;
    int i;
    int nCell;

    initPage(pPage, 0);
    nCell = pPage->nCell;



    for(i=0; i<nCell; i++){
      u8 *pCell = findCell(pPage, i);
      if( eType==PTRMAP_OVERFLOW1 ){
        CellInfo info;
        parseCellPtr(pPage, pCell, &info);
        if( info.iOverflow ){
          if( iFrom==get4byte(&pCell[info.iOverflow]) ){
................................................................................
      }
      rc = allocatePage(pBt, &pFreeMemPage, &iFreePage, 0);
      if( rc!=SQLITE_OK ) goto autovacuum_out;
      assert( iFreePage<=origDbSize );
    }while( iFreePage>finDbSize );

    /* Move page iDbPage from it's current location to page number iFreePage */
    TRACE(("AUTOVACUUM: Moving %d to free page %d (ptr page %d type %d)\n", 
        iDbPage, iFreePage, iPtrPage, eType));
    releasePage(pFreeMemPage);
    pFreeMemPage = 0;
    rc = sqlite3pager_movepage(pPager, pDbPage, iFreePage);
    if( rc!=SQLITE_OK ) goto autovacuum_out;
    pDbMemPage->pgno = iFreePage;

    /* If pDbPage was a btree-page, then it may have child pages and/or cells
    ** that point to overflow pages. The pointer map entries for all these
    ** pages need to be changed.
    **
    ** If pDbPage is an overflow page, then the first 4 bytes may store a
    ** pointer to a subsequent overflow page. If this is the case, then
    ** the pointer map needs to be updated for the subsequent overflow page.
    */
    if( eType==PTRMAP_BTREE ){
      rc = setChildPtrmaps(pDbMemPage);
      if( rc!=SQLITE_OK ) goto autovacuum_out;
    }else{
      Pgno nextOvfl = get4byte(pDbPage);
      if( nextOvfl!=0 ){
        assert( nextOvfl<=origDbSize );
        rc = ptrmapPut(pBt, nextOvfl, PTRMAP_OVERFLOW2, iFreePage);
        if( rc!=SQLITE_OK ) goto autovacuum_out;
      }
    }
    releasePage(pDbMemPage);
    pDbMemPage = 0;

    /* Fix the database pointer on page iPtrPage that pointed at iDbPage so
    ** that it points at iFreePage. Also fix the pointer map entry for
    ** iPtrPage.

#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this file is testing the SELECT statement.
#
# $Id: autovacuum.test,v 1.1 2004/11/02 12:56:41 danielk1977 Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl

proc make_str {char len} {
  set str [string repeat $char. $len]
  return [string range $str 0 [expr $len-1]]
................................................................................
proc file_pages {} {
  return [expr [file size test.db] / 1024]
}

do_test autovacuum-1.1 {
  execsql {
    CREATE TABLE av1(a);

  }
} {}

set ENTRY_LEN 1100

set delete_orders [list]
lappend delete_orders {1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20}
lappend delete_orders {20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1} 
lappend delete_orders {8 18 2 4 14 11 13 3 10 7 9 5 12 17 19 15 20 6 16 1}
lappend delete_orders {10 3 11 17 19 20 7 4 13 6 1 14 16 12 9 18 8 15 5 2}

#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this file is testing the SELECT statement.
#
# $Id: autovacuum.test,v 1.2 2004/11/02 14:40:32 danielk1977 Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl

proc make_str {char len} {
  set str [string repeat $char. $len]
  return [string range $str 0 [expr $len-1]]
................................................................................
proc file_pages {} {
  return [expr [file size test.db] / 1024]
}

do_test autovacuum-1.1 {
  execsql {
    CREATE TABLE av1(a);
    -- CREATE INDEX av1_idx ON av1(a);
  }
} {}

set ENTRY_LEN 3000

set delete_orders [list]
lappend delete_orders {1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20}
lappend delete_orders {20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1} 
lappend delete_orders {8 18 2 4 14 11 13 3 10 7 9 5 12 17 19 15 20 6 16 1}
lappend delete_orders {10 3 11 17 19 20 7 4 13 6 1 14 16 12 9 18 8 15 5 2}