** 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.235 2005/01/16 08:00:01 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.
................................................................................
  u8 *apDiv[NB];               /* Divider cells in pParent */
  int cntNew[NB+2];            /* Index in aCell[] of cell after i-th page */
  int szNew[NB+2];             /* Combined size of cells place on i-th page */
  u8 **apCell;                 /* All cells begin balanced */
  int *szCell;                 /* Local size of all cells in apCell[] */
  u8 *aCopy[NB];               /* Space for holding data of apCopy[] */
  u8 *aSpace;                  /* Space to hold copies of dividers cells */
#ifndef SQLITE_OMIT_VACUUM
  u8 *aFrom = 0;
#endif

  /* 
  ** Find the parent page.
  */
  assert( pPage->isInit );
................................................................................
  MemPage *pChild;             /* The only child page of pPage */
  Pgno pgnoChild;              /* Page number for pChild */
  int rc = SQLITE_OK;          /* Return code from subprocedures */
  Btree *pBt;                  /* The main BTree structure */
  int mxCellPerPage;           /* Maximum number of cells per page */
  u8 **apCell;                 /* All cells from pages being balanced */
  int *szCell;                 /* Local size of all cells */
  int i;

  assert( pPage->pParent==0 );
  assert( pPage->nCell==0 );
  pBt = pPage->pBt;
  mxCellPerPage = MX_CELL(pBt);
  apCell = sqliteMallocRaw( mxCellPerPage*(sizeof(u8*)+sizeof(int)) );
  if( apCell==0 ) return SQLITE_NOMEM;
................................................................................
  if( pChild->nOverflow ){
    pChild->nFree = 0;
  }
  assert( pChild->nCell==pPage->nCell );
  zeroPage(pPage, pChild->aData[0] & ~PTF_LEAF);
  put4byte(&pPage->aData[pPage->hdrOffset+8], pgnoChild);
  TRACE(("BALANCE: copy root %d into %d\n", pPage->pgno, pChild->pgno));

  if( pBt->autoVacuum ){
    int i;
    rc = ptrmapPut(pBt, pChild->pgno, PTRMAP_BTREE, pPage->pgno);
    if( rc ) return rc;
    for(i=0; i<pChild->nCell; i++){
      rc = ptrmapPutOvfl(pChild, i);
      if( rc!=SQLITE_OK ){
        return rc;
      }
    }
  }

  rc = balance_nonroot(pChild);
  releasePage(pChild);
  return rc;
}

/*
** Decide if the page pPage needs to be balanced.  If balancing is

** 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.236 2005/01/16 09:06:34 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.
................................................................................
  u8 *apDiv[NB];               /* Divider cells in pParent */
  int cntNew[NB+2];            /* Index in aCell[] of cell after i-th page */
  int szNew[NB+2];             /* Combined size of cells place on i-th page */
  u8 **apCell;                 /* All cells begin balanced */
  int *szCell;                 /* Local size of all cells in apCell[] */
  u8 *aCopy[NB];               /* Space for holding data of apCopy[] */
  u8 *aSpace;                  /* Space to hold copies of dividers cells */
#ifndef SQLITE_OMIT_AUTOVACUUM
  u8 *aFrom = 0;
#endif

  /* 
  ** Find the parent page.
  */
  assert( pPage->isInit );
................................................................................
  MemPage *pChild;             /* The only child page of pPage */
  Pgno pgnoChild;              /* Page number for pChild */
  int rc = SQLITE_OK;          /* Return code from subprocedures */
  Btree *pBt;                  /* The main BTree structure */
  int mxCellPerPage;           /* Maximum number of cells per page */
  u8 **apCell;                 /* All cells from pages being balanced */
  int *szCell;                 /* Local size of all cells */


  assert( pPage->pParent==0 );
  assert( pPage->nCell==0 );
  pBt = pPage->pBt;
  mxCellPerPage = MX_CELL(pBt);
  apCell = sqliteMallocRaw( mxCellPerPage*(sizeof(u8*)+sizeof(int)) );
  if( apCell==0 ) return SQLITE_NOMEM;
................................................................................
  if( pChild->nOverflow ){
    pChild->nFree = 0;
  }
  assert( pChild->nCell==pPage->nCell );
  zeroPage(pPage, pChild->aData[0] & ~PTF_LEAF);
  put4byte(&pPage->aData[pPage->hdrOffset+8], pgnoChild);
  TRACE(("BALANCE: copy root %d into %d\n", pPage->pgno, pChild->pgno));
#ifndef SQLITE_OMIT_AUTOVACUUM
  if( pBt->autoVacuum ){
    int i;
    rc = ptrmapPut(pBt, pChild->pgno, PTRMAP_BTREE, pPage->pgno);
    if( rc ) return rc;
    for(i=0; i<pChild->nCell; i++){
      rc = ptrmapPutOvfl(pChild, i);
      if( rc!=SQLITE_OK ){
        return rc;
      }
    }
  }
#endif
  rc = balance_nonroot(pChild);
  releasePage(pChild);
  return rc;
}

/*
** Decide if the page pPage needs to be balanced.  If balancing is

#    May you share freely, never taking more than you give.
#
#***********************************************************************
#
# This file runs the tests in the file crash.test with auto-vacuum enabled
# databases.
#
# $Id: autovacuum_crash.test,v 1.1 2004/11/08 09:51:09 danielk1977 Exp $

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








rename finish_test really_finish_test2
proc finish_test {} {}
set ISQUICK 1

rename sqlite3 real_sqlite3
proc sqlite3 {args} {
  set r [eval "real_sqlite3 $args"]

#    May you share freely, never taking more than you give.
#
#***********************************************************************
#
# This file runs the tests in the file crash.test with auto-vacuum enabled
# databases.
#
# $Id: autovacuum_crash.test,v 1.2 2005/01/16 09:06:34 danielk1977 Exp $

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

# If this build of the library does not support auto-vacuum, omit this
# whole file.
ifcapable {!autovacuum} {
  finish_test
  return
}

rename finish_test really_finish_test2
proc finish_test {} {}
set ISQUICK 1

rename sqlite3 real_sqlite3
proc sqlite3 {args} {
  set r [eval "real_sqlite3 $args"]

#    May you share freely, never taking more than you give.
#
#***********************************************************************
#
# This file runs the tests in the file crash.test with auto-vacuum enabled
# databases.
#
# $Id: autovacuum_ioerr.test,v 1.1 2005/01/11 10:25:07 danielk1977 Exp $

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








rename finish_test really_finish_test2
proc finish_test {} {}
set ISQUICK 1

rename sqlite3 real_sqlite3
proc sqlite3 {args} {
  set r [eval "real_sqlite3 $args"]

#    May you share freely, never taking more than you give.
#
#***********************************************************************
#
# This file runs the tests in the file crash.test with auto-vacuum enabled
# databases.
#
# $Id: autovacuum_ioerr.test,v 1.2 2005/01/16 09:06:34 danielk1977 Exp $

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

# If this build of the library does not support auto-vacuum, omit this
# whole file.
ifcapable {!autovacuum} {
  finish_test
  return
}

rename finish_test really_finish_test2
proc finish_test {} {}
set ISQUICK 1

rename sqlite3 real_sqlite3
proc sqlite3 {args} {
  set r [eval "real_sqlite3 $args"]

# This file implements regression tests for SQLite library.  The
# focus of this file is testing for correct handling of I/O errors
# such as writes failing because the disk is full.
# 
# The tests in this file use special facilities that are only
# available in the SQLite test fixture.
#
# $Id: autovacuum_ioerr2.test,v 1.2 2005/01/15 12:45:51 danielk1977 Exp $

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








proc opendb {} {
  catch {file delete -force test.db}
  catch {file delete -force test.db-journal}
  sqlite3 db test.db
  execsql {pragma auto_vacuum = 1}
  execsql {SELECT * FROM sqlite_master}

# This file implements regression tests for SQLite library.  The
# focus of this file is testing for correct handling of I/O errors
# such as writes failing because the disk is full.
# 
# The tests in this file use special facilities that are only
# available in the SQLite test fixture.
#
# $Id: autovacuum_ioerr2.test,v 1.3 2005/01/16 09:06:34 danielk1977 Exp $

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

# If this build of the library does not support auto-vacuum, omit this
# whole file.
ifcapable {!autovacuum} {
  finish_test
  return
}

proc opendb {} {
  catch {file delete -force test.db}
  catch {file delete -force test.db-journal}
  sqlite3 db test.db
  execsql {pragma auto_vacuum = 1}
  execsql {SELECT * FROM sqlite_master}

# module "crashtest" compiled with the special "os_test.c" backend is used.
# The os_test.c simulates the kind of file corruption that can occur
# when writes are happening at the moment of power loss.
# 
# The special crash-test module with its os_test.c backend only works
# on Unix.
#
# $Id: crash.test,v 1.15 2005/01/15 12:45:51 danielk1977 Exp $

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

# set repeats 100
set repeats 10

................................................................................
proc signature {} {
  return [db eval {SELECT count(*), md5sum(a), md5sum(b), md5sum(c) FROM abc}]
}
proc signature2 {} {
  return [db eval {SELECT count(*), md5sum(a), md5sum(b), md5sum(c) FROM abc2}]
}

# This variable is set to 1 if the databases being used support auto-vacuum.
# This is because some of the tests in this file verify file-size, which is
# slightly larger for auto-vacuum databases.
set AUTOVACUUM [db eval {pragma auto_vacuum}]

#--------------------------------------------------------------------------
# Simple crash test:
#
# crash-1.1: Create a database with a table with two rows.
# crash-1.2: Run a 'DELETE FROM abc WHERE a = 1' that crashes during
#            the first journal-sync.
# crash-1.3: Ensure the database is in the same state as after crash-1.1.
................................................................................
    INSERT INTO abc SELECT * FROM abc;
    INSERT INTO abc SELECT * FROM abc;
    INSERT INTO abc SELECT * FROM abc;
  }
} {}
do_test crash-5.2 {
  expr [file size test.db] / 1024
} [expr $AUTOVACUUM ? 11 : 10]
set sig [signature]
do_test crash-5.3 {
# The SQL below is used to expose a bug that existed in
# sqlite3pager_movepage() during development of the auto-vacuum feature. It
# functions as follows:
# 
# 1: Begin a transaction.
................................................................................
  puts -nonewline $f "\00\00\00\00"
  close $f
} {}
do_test crash-7.2 {
  signature
} $sig

# The AUTOVACUUM was changed above.  We have to reset it for
# other scripts that run as part of "fulltest"
#
set AUTOVACUUM $sqlite_options(default_autovacuum)

finish_test

# module "crashtest" compiled with the special "os_test.c" backend is used.
# The os_test.c simulates the kind of file corruption that can occur
# when writes are happening at the moment of power loss.
# 
# The special crash-test module with its os_test.c backend only works
# on Unix.
#
# $Id: crash.test,v 1.16 2005/01/16 09:06:34 danielk1977 Exp $

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

# set repeats 100
set repeats 10

................................................................................
proc signature {} {
  return [db eval {SELECT count(*), md5sum(a), md5sum(b), md5sum(c) FROM abc}]
}
proc signature2 {} {
  return [db eval {SELECT count(*), md5sum(a), md5sum(b), md5sum(c) FROM abc2}]
}






#--------------------------------------------------------------------------
# Simple crash test:
#
# crash-1.1: Create a database with a table with two rows.
# crash-1.2: Run a 'DELETE FROM abc WHERE a = 1' that crashes during
#            the first journal-sync.
# crash-1.3: Ensure the database is in the same state as after crash-1.1.
................................................................................
    INSERT INTO abc SELECT * FROM abc;
    INSERT INTO abc SELECT * FROM abc;
    INSERT INTO abc SELECT * FROM abc;
  }
} {}
do_test crash-5.2 {
  expr [file size test.db] / 1024
} [expr [string match [execsql {pragma auto_vacuum}] 1] ? 11 : 10]
set sig [signature]
do_test crash-5.3 {
# The SQL below is used to expose a bug that existed in
# sqlite3pager_movepage() during development of the auto-vacuum feature. It
# functions as follows:
# 
# 1: Begin a transaction.
................................................................................
  puts -nonewline $f "\00\00\00\00"
  close $f
} {}
do_test crash-7.2 {
  signature
} $sig






finish_test

# This file implements regression tests for SQLite library.  The
# focus of this file is testing for correct handling of I/O errors
# such as writes failing because the disk is full.
# 
# The tests in this file use special facilities that are only
# available in the SQLite test fixture.
#
# $Id: ioerr.test,v 1.13 2005/01/14 13:50:13 danielk1977 Exp $

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

set ::AV [execsql {pragma auto_vacuum}]

# Usage: do_ioerr_test <test number> <options...>
#
# The first argument, <test number>, is an integer used to name the
# tests executed by this proc. Options are as follows:
#
#     -tclprep          TCL script to run to prepare test.
#     -sqlprep          SQL script to run to prepare test.
................................................................................
  SELECT * FROM t1;
  BEGIN TRANSACTION;
  INSERT INTO t1 VALUES(1,2,3);
  INSERT INTO t1 VALUES(4,5,6);
  COMMIT;
  SELECT * FROM t1;
  DELETE FROM t1 WHERE a<100;
} -exclude [expr [execsql {pragma auto_vacuum}] ? 8 : 0]


proc cksum {{db db}} {
  set txt [$db eval {
      SELECT name, type, sql FROM sqlite_master order by name
  }]\n
  foreach tbl [$db eval {
................................................................................
do_ioerr_test 5 -sqlprep {
  ATTACH 'test2.db' AS test2;
} -sqlbody {
  BEGIN;
  CREATE TABLE t1(a,b,c);
  CREATE TABLE test2.t2(a,b,c);
  COMMIT;
} -exclude [expr [execsql {pragma auto_vacuum}] ? 8 : 0]

# Test IO errors when replaying two hot journals from a 2-file 
# transaction. This test only runs on UNIX.
if {$tcl_platform(platform)=="unix" && [file exists ./crashtest]} {
  do_ioerr_test 6 -tclprep {
    set rc [crashsql 2 test2.db-journal {
      ATTACH 'test2.db' as aux;
................................................................................
# } -sqlbody {
#   BEGIN;
#   INSERT INTO abc VALUES(1, 2, 3);
#   COMMIT;
# }

finish_test

# This file implements regression tests for SQLite library.  The
# focus of this file is testing for correct handling of I/O errors
# such as writes failing because the disk is full.
# 
# The tests in this file use special facilities that are only
# available in the SQLite test fixture.
#
# $Id: ioerr.test,v 1.14 2005/01/16 09:06:34 danielk1977 Exp $

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



# Usage: do_ioerr_test <test number> <options...>
#
# The first argument, <test number>, is an integer used to name the
# tests executed by this proc. Options are as follows:
#
#     -tclprep          TCL script to run to prepare test.
#     -sqlprep          SQL script to run to prepare test.
................................................................................
  SELECT * FROM t1;
  BEGIN TRANSACTION;
  INSERT INTO t1 VALUES(1,2,3);
  INSERT INTO t1 VALUES(4,5,6);
  COMMIT;
  SELECT * FROM t1;
  DELETE FROM t1 WHERE a<100;
} -exclude [expr [string match [execsql {pragma auto_vacuum}] 1] ? 8 : 0]


proc cksum {{db db}} {
  set txt [$db eval {
      SELECT name, type, sql FROM sqlite_master order by name
  }]\n
  foreach tbl [$db eval {
................................................................................
do_ioerr_test 5 -sqlprep {
  ATTACH 'test2.db' AS test2;
} -sqlbody {
  BEGIN;
  CREATE TABLE t1(a,b,c);
  CREATE TABLE test2.t2(a,b,c);
  COMMIT;
} -exclude [expr [string match [execsql {pragma auto_vacuum}] 1] ? 8 : 0]

# Test IO errors when replaying two hot journals from a 2-file 
# transaction. This test only runs on UNIX.
if {$tcl_platform(platform)=="unix" && [file exists ./crashtest]} {
  do_ioerr_test 6 -tclprep {
    set rc [crashsql 2 test2.db-journal {
      ATTACH 'test2.db' as aux;
................................................................................
# } -sqlbody {
#   BEGIN;
#   INSERT INTO abc VALUES(1, 2, 3);
#   COMMIT;
# }

finish_test

#
#***********************************************************************
# This file implements regression tests for SQLite library.
#
# This file implements tests for the SQLITE_MISUSE detection logic.
# This test file leaks memory and file descriptors.
#
# $Id: misuse.test,v 1.8 2004/11/14 21:56:31 drh Exp $

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

proc catchsql2 {sql} {
  set r [
    catch {
................................................................................


# Make sure the test logic works
#
do_test misuse-1.1 {
  db close
  catch {file delete -force test2.db}

  set ::DB [sqlite3 db test2.db]
  execsql {
    CREATE TABLE t1(a,b);
    INSERT INTO t1 VALUES(1,2);
  }
  catchsql2 {
    SELECT * FROM t1

#
#***********************************************************************
# This file implements regression tests for SQLite library.
#
# This file implements tests for the SQLITE_MISUSE detection logic.
# This test file leaks memory and file descriptors.
#
# $Id: misuse.test,v 1.9 2005/01/16 09:06:34 danielk1977 Exp $

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

proc catchsql2 {sql} {
  set r [
    catch {
................................................................................


# Make sure the test logic works
#
do_test misuse-1.1 {
  db close
  catch {file delete -force test2.db}
  catch {file delete -force test2.db-journal}
  set ::DB [sqlite3 db test2.db]
  execsql {
    CREATE TABLE t1(a,b);
    INSERT INTO t1 VALUES(1,2);
  }
  catchsql2 {
    SELECT * FROM t1