** 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.199 2004/11/02 18:05:09 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.
................................................................................
  rc = sqlite3pager_truncate(pBt->pPager, finDbSize);
  if( rc!=SQLITE_OK ) goto autovacuum_out;

autovacuum_out:
  /* TODO: A goto autovacuum_out; will fail to call releasePage() on 
  ** outstanding references. Fix.
  */
#ifndef NDEBUG
  if( nRef!=*sqlite3pager_stats(pPager) ){
    sqlite3pager_refdump(pPager);
  }
#endif
  assert( nRef==*sqlite3pager_stats(pPager) );
  if( rc!=SQLITE_OK ){
    sqlite3pager_rollback(pPager);
  }
  return rc;
}
#endif
................................................................................
    ** pointer-map must be updated accordingly.
    **
    ** TODO: This looks like quite an expensive thing to do. Investigate.
    */
    if( pBt->autoVacuum ){
      CellInfo info;
      parseCellPtr(pPage, pCell, &info);
      if( info.iOverflow ){
        Pgno pgnoOvfl = get4byte(&pCell[info.iOverflow]);
        rc = ptrmapPut(pBt, pgnoOvfl, PTRMAP_OVERFLOW1, pPage->pgno);
        if( rc!=SQLITE_OK ) return rc;
      }
    }
#endif
  }
................................................................................
** will not fit, then make a copy of the cell content into pTemp if
** pTemp is not null.  Regardless of pTemp, allocate a new entry
** in pPage->aOvfl[] and make it point to the cell content (either
** in pTemp or the original pCell) and also record its index. 
** Allocating a new entry in pPage->aCell[] implies that 
** pPage->nOverflow is incremented.
*/
static void insertCell(
  MemPage *pPage,   /* Page into which we are copying */
  int i,            /* New cell becomes the i-th cell of the page */
  u8 *pCell,        /* Content of the new cell */
  int sz,           /* Bytes of content in pCell */
  u8 *pTemp         /* Temp storage space for pCell, if needed */
){
  int idx;          /* Where to write new cell content in data[] */
................................................................................
      ptr[1] = ptr[-1];
    }
    put2byte(&data[ins], idx);
    put2byte(&data[hdr+3], pPage->nCell);
    pPage->idxShift = 1;
    pageIntegrity(pPage);
  }
















}

/*
** Add a list of cells to a page.  The page should be initially empty.
** The cells are guaranteed to fit on the page.
*/
static void assemblePage(
................................................................................
        pTemp = 0;
      }else{
        pCell -= 4;
        pTemp = &aSpace[iSpace];
        iSpace += sz;
        assert( iSpace<=pBt->psAligned*5 );
      }
      insertCell(pParent, nxDiv, pCell, sz, pTemp);

      put4byte(findOverflowCell(pParent,nxDiv), pNew->pgno);
      j++;
      nxDiv++;
    }
  }
  assert( j==nCell );
  if( (pageFlags & PTF_LEAF)==0 ){
................................................................................
  }else if( loc<0 && pPage->nCell>0 ){
    assert( pPage->leaf );
    pCur->idx++;
    pCur->info.nSize = 0;
  }else{
    assert( pPage->leaf );
  }
  insertCell(pPage, pCur->idx, newCell, szNew, 0);

  rc = balance(pPage);
  /* sqlite3BtreePageDump(pCur->pBt, pCur->pgnoRoot, 1); */
  /* fflush(stdout); */
  if( rc==SQLITE_OK ){
    moveToRoot(pCur);
  }
end_insert:
................................................................................
       pCur->pgnoRoot, pPage->pgno, leafCur.pPage->pgno));
    dropCell(pPage, pCur->idx, cellSizePtr(pPage, pCell));
    pNext = findCell(leafCur.pPage, leafCur.idx);
    szNext = cellSizePtr(leafCur.pPage, pNext);
    assert( MX_CELL_SIZE(pBt)>=szNext+4 );
    tempCell = sqliteMallocRaw( MX_CELL_SIZE(pBt) );
    if( tempCell==0 ) return SQLITE_NOMEM;
    insertCell(pPage, pCur->idx, pNext-4, szNext+4, tempCell);

    put4byte(findOverflowCell(pPage, pCur->idx), pgnoChild);
    rc = balance(pPage);
    sqliteFree(tempCell);
    if( rc ) return rc;
    dropCell(leafCur.pPage, leafCur.idx, szNext);
    rc = balance(leafCur.pPage);
    releaseTempCursor(&leafCur);

** 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.200 2004/11/03 03:01:17 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.
................................................................................
  rc = sqlite3pager_truncate(pBt->pPager, finDbSize);
  if( rc!=SQLITE_OK ) goto autovacuum_out;

autovacuum_out:
  /* TODO: A goto autovacuum_out; will fail to call releasePage() on 
  ** outstanding references. Fix.
  */





  assert( nRef==*sqlite3pager_stats(pPager) );
  if( rc!=SQLITE_OK ){
    sqlite3pager_rollback(pPager);
  }
  return rc;
}
#endif
................................................................................
    ** pointer-map must be updated accordingly.
    **
    ** TODO: This looks like quite an expensive thing to do. Investigate.
    */
    if( pBt->autoVacuum ){
      CellInfo info;
      parseCellPtr(pPage, pCell, &info);
      if( (info.nData+(pPage->intKey?0:info.nKey))>info.nLocal ){
        Pgno pgnoOvfl = get4byte(&pCell[info.iOverflow]);
        rc = ptrmapPut(pBt, pgnoOvfl, PTRMAP_OVERFLOW1, pPage->pgno);
        if( rc!=SQLITE_OK ) return rc;
      }
    }
#endif
  }
................................................................................
** will not fit, then make a copy of the cell content into pTemp if
** pTemp is not null.  Regardless of pTemp, allocate a new entry
** in pPage->aOvfl[] and make it point to the cell content (either
** in pTemp or the original pCell) and also record its index. 
** Allocating a new entry in pPage->aCell[] implies that 
** pPage->nOverflow is incremented.
*/
static int insertCell(
  MemPage *pPage,   /* Page into which we are copying */
  int i,            /* New cell becomes the i-th cell of the page */
  u8 *pCell,        /* Content of the new cell */
  int sz,           /* Bytes of content in pCell */
  u8 *pTemp         /* Temp storage space for pCell, if needed */
){
  int idx;          /* Where to write new cell content in data[] */
................................................................................
      ptr[1] = ptr[-1];
    }
    put2byte(&data[ins], idx);
    put2byte(&data[hdr+3], pPage->nCell);
    pPage->idxShift = 1;
    pageIntegrity(pPage);
  }

#ifndef SQLITE_OMIT_AUTOVACUUM
  if( pPage->pBt->autoVacuum ){
    /* The cell may contain a pointer to an overflow page. If so, write
    ** the entry for the overflow page into the pointer map.
    */
    CellInfo info;
    parseCellPtr(pPage, pCell, &info);
    if( (info.nData+(pPage->intKey?0:info.nKey))>info.nLocal ){
      Pgno pgnoOvfl = get4byte(&pCell[info.iOverflow]);
      int rc = ptrmapPut(pPage->pBt, pgnoOvfl, PTRMAP_OVERFLOW1, pPage->pgno);
      if( rc!=SQLITE_OK ) return rc;
    }
  }
#endif
  return SQLITE_OK;
}

/*
** Add a list of cells to a page.  The page should be initially empty.
** The cells are guaranteed to fit on the page.
*/
static void assemblePage(
................................................................................
        pTemp = 0;
      }else{
        pCell -= 4;
        pTemp = &aSpace[iSpace];
        iSpace += sz;
        assert( iSpace<=pBt->psAligned*5 );
      }
      rc = insertCell(pParent, nxDiv, pCell, sz, pTemp);
      if( rc!=SQLITE_OK ) goto balance_cleanup;
      put4byte(findOverflowCell(pParent,nxDiv), pNew->pgno);
      j++;
      nxDiv++;
    }
  }
  assert( j==nCell );
  if( (pageFlags & PTF_LEAF)==0 ){
................................................................................
  }else if( loc<0 && pPage->nCell>0 ){
    assert( pPage->leaf );
    pCur->idx++;
    pCur->info.nSize = 0;
  }else{
    assert( pPage->leaf );
  }
  rc = insertCell(pPage, pCur->idx, newCell, szNew, 0);
  if( rc!=SQLITE_OK ) goto end_insert;
  rc = balance(pPage);
  /* sqlite3BtreePageDump(pCur->pBt, pCur->pgnoRoot, 1); */
  /* fflush(stdout); */
  if( rc==SQLITE_OK ){
    moveToRoot(pCur);
  }
end_insert:
................................................................................
       pCur->pgnoRoot, pPage->pgno, leafCur.pPage->pgno));
    dropCell(pPage, pCur->idx, cellSizePtr(pPage, pCell));
    pNext = findCell(leafCur.pPage, leafCur.idx);
    szNext = cellSizePtr(leafCur.pPage, pNext);
    assert( MX_CELL_SIZE(pBt)>=szNext+4 );
    tempCell = sqliteMallocRaw( MX_CELL_SIZE(pBt) );
    if( tempCell==0 ) return SQLITE_NOMEM;
    rc = insertCell(pPage, pCur->idx, pNext-4, szNext+4, tempCell);
    if( rc!=SQLITE_OK ) return rc;
    put4byte(findOverflowCell(pPage, pCur->idx), pgnoChild);
    rc = balance(pPage);
    sqliteFree(tempCell);
    if( rc ) return rc;
    dropCell(leafCur.pPage, leafCur.idx, szNext);
    rc = balance(leafCur.pPage);
    releaseTempCursor(&leafCur);

#    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}

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 \
        {{19 8 17 15} {16 11 9 14} {18 5 3 1} {13 20 7 2} {6 12 4 10}}


set tn 0
foreach delete_order $delete_orders {
  incr tn

  # Set up the table.
  set ::tbl_data [list]
  foreach i [lsort -integer [eval concat $delete_order]] {
    execsql "INSERT INTO av1 (oid, a) VALUES($i, '[make_str $i $ENTRY_LEN]')"
    lappend ::tbl_data [make_str $i $ENTRY_LEN]
  }

# puts "File has [file_pages] pages"

  do_test autovacuum-1.$tn.1 {
    execsql {
      pragma integrity_check
    }
  } {ok}

  foreach delete $delete_order {
# if {$delete==6} { set btree_trace 1 ; breakpoint }
    do_test autovacuum-1.$tn.($delete).1 {
      execsql "
        DELETE FROM av1 WHERE oid IN ([join $delete ,])
      "
    } {}
set btree_trace 0

    do_test autovacuum-1.$tn.($delete).2 {
      execsql {
        pragma integrity_check
      }
    } {ok}

................................................................................
      set ::tbl_data [lreplace $::tbl_data $idx $idx]
    }
    do_test autovacuum-1.$tn.($delete).3 {
      execsql {
        select a from av1
      }
    } $::tbl_data
# if {$::nErr>0} finish_test
  }

  do_test autovacuum-1.$tn.3 {
    file_pages
  } {3}
}

finish_test

#    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.3 2004/11/03 03:01:17 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}

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 \
        {{19 8 17 15} {16 11 9 14} {18 5 3 1} {13 20 7 2} {6 12 4 10}}


set tn 0
foreach delete_order $delete_orders {
  incr tn

  # Set up the table.
  set ::tbl_data [list]
  foreach i [lsort -integer [eval concat $delete_order]] {
    execsql "INSERT INTO av1 (oid, a) VALUES($i, '[make_str $i $ENTRY_LEN]')"
    lappend ::tbl_data [make_str $i $ENTRY_LEN]
  }



  do_test autovacuum-1.$tn.1 {
    execsql {
      pragma integrity_check
    }
  } {ok}

  foreach delete $delete_order {

    do_test autovacuum-1.$tn.($delete).1 {
      execsql "
        DELETE FROM av1 WHERE oid IN ([join $delete ,])
      "
    } {}


    do_test autovacuum-1.$tn.($delete).2 {
      execsql {
        pragma integrity_check
      }
    } {ok}

................................................................................
      set ::tbl_data [lreplace $::tbl_data $idx $idx]
    }
    do_test autovacuum-1.$tn.($delete).3 {
      execsql {
        select a from av1
      }
    } $::tbl_data

  }

  do_test autovacuum-1.$tn.3 {
    file_pages
  } {4}
}

finish_test