** 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.228 2005/01/08 15:43:19 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.
................................................................................
    }

    pPage->isInit = isInitOrig;
  }
}






static int relocatePage(
  Btree *pBt, 
  MemPage *pDbPage,
  u8 eType,
  Pgno iPtrPage,


  Pgno iFreePage
){
  MemPage *pPtrPage;   /* The page that contains a pointer to pDbPage */
  Pgno iDbPage = pDbPage->pgno;
  Pager *pPager = pBt->pPager;
  int rc;

  assert( eType==PTRMAP_OVERFLOW2 || eType==PTRMAP_OVERFLOW1 || 
................................................................................
    memset(hit, 1, get2byte(&data[hdr+5]));
    nCell = get2byte(&data[hdr+3]);
    cellStart = hdr + 12 - 4*pPage->leaf;
    for(i=0; i<nCell; i++){
      int pc = get2byte(&data[cellStart+i*2]);
      int size = cellSizePtr(pPage, &data[pc]);
      int j;




      for(j=pc+size-1; j>=pc; j--) hit[j]++;

    }
    for(cnt=0, i=get2byte(&data[hdr+1]); i>0 && i<usableSize && cnt<10000; 
           cnt++){
      int size = get2byte(&data[i+2]);
      int j;




      for(j=i+size-1; j>=i; j--) hit[j]++;

      i = get2byte(&data[i]);
    }
    for(i=cnt=0; i<usableSize; i++){
      if( hit[i]==0 ){
        cnt++;
      }else if( hit[i]>1 ){
        checkAppendMsg(pCheck, 0,

** 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.229 2005/01/10 12:59:52 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.
................................................................................
    }

    pPage->isInit = isInitOrig;
  }
}


/*
** Move the open database page pDbPage to location iFreePage in the 
** database. The pDbPage reference remains valid.
*/
static int relocatePage(
  Btree *pBt,              /* Btree */
  MemPage *pDbPage,        /* Open page to move */


  u8 eType,                /* Pointer map 'type' entry for pDbPage */
  Pgno iPtrPage,           /* Pointer map 'page-no' entry for pDbPage */
  Pgno iFreePage           /* The location to move pDbPage to */
){
  MemPage *pPtrPage;   /* The page that contains a pointer to pDbPage */
  Pgno iDbPage = pDbPage->pgno;
  Pager *pPager = pBt->pPager;
  int rc;

  assert( eType==PTRMAP_OVERFLOW2 || eType==PTRMAP_OVERFLOW1 || 
................................................................................
    memset(hit, 1, get2byte(&data[hdr+5]));
    nCell = get2byte(&data[hdr+3]);
    cellStart = hdr + 12 - 4*pPage->leaf;
    for(i=0; i<nCell; i++){
      int pc = get2byte(&data[cellStart+i*2]);
      int size = cellSizePtr(pPage, &data[pc]);
      int j;
      if( (pc+size-1)>=usableSize || pc<0 ){
        checkAppendMsg(pCheck, 0, 
            "Corruption detected in cell %d on page %d",i,iPage,0);
      }else{
        for(j=pc+size-1; j>=pc; j--) hit[j]++;
      }
    }
    for(cnt=0, i=get2byte(&data[hdr+1]); i>0 && i<usableSize && cnt<10000; 
           cnt++){
      int size = get2byte(&data[i+2]);
      int j;
      if( (i+size-1)>=usableSize || i<0 ){
        checkAppendMsg(pCheck, 0,  
            "Corruption detected in cell %d on page %d",i,iPage,0);
      }else{
        for(j=i+size-1; j>=i; j--) hit[j]++;
      }
      i = get2byte(&data[i]);
    }
    for(i=cnt=0; i<usableSize; i++){
      if( hit[i]==0 ){
        cnt++;
      }else if( hit[i]>1 ){
        checkAppendMsg(pCheck, 0,

**    May you share freely, never taking more than you give.
**
*************************************************************************
** Code for testing the btree.c module in SQLite.  This code
** is not included in the SQLite library.  It is used for automated
** testing of the SQLite library.
**
** $Id: test3.c,v 1.58 2005/01/08 12:42:39 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include "pager.h"
#include "btree.h"
#include "tcl.h"
#include <stdlib.h>
#include <string.h>
................................................................................
    Tcl_AppendResult(interp, zBuf, 0);
    free(zBuf);
  }
  return SQLITE_OK;
}

/*
** Usage:   btree_data ID
**
** Return the data for the entry at which the cursor is pointing.
*/
static int btree_data(
  void *NotUsed,
  Tcl_Interp *interp,    /* The TCL interpreter that invoked this command */
  int argc,              /* Number of arguments */
................................................................................
  const char **argv      /* Text of each argument */
){
  BtCursor *pCur;
  int rc;
  u32 n;
  char *zBuf;

  if( argc!=2 ){
    Tcl_AppendResult(interp, "wrong # args: should be \"", argv[0],
       " ID\"", 0);
    return TCL_ERROR;
  }
  pCur = sqlite3TextToPtr(argv[1]);

  sqlite3BtreeDataSize(pCur, &n);



  zBuf = malloc( n+1 );
  rc = sqlite3BtreeData(pCur, 0, n, zBuf);
  if( rc ){
    Tcl_AppendResult(interp, errorName(rc), 0);
    return TCL_ERROR;
  }
  zBuf[n] = 0;

**    May you share freely, never taking more than you give.
**
*************************************************************************
** Code for testing the btree.c module in SQLite.  This code
** is not included in the SQLite library.  It is used for automated
** testing of the SQLite library.
**
** $Id: test3.c,v 1.59 2005/01/10 12:59:53 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include "pager.h"
#include "btree.h"
#include "tcl.h"
#include <stdlib.h>
#include <string.h>
................................................................................
    Tcl_AppendResult(interp, zBuf, 0);
    free(zBuf);
  }
  return SQLITE_OK;
}

/*
** Usage:   btree_data ID ?N?
**
** Return the data for the entry at which the cursor is pointing.
*/
static int btree_data(
  void *NotUsed,
  Tcl_Interp *interp,    /* The TCL interpreter that invoked this command */
  int argc,              /* Number of arguments */
................................................................................
  const char **argv      /* Text of each argument */
){
  BtCursor *pCur;
  int rc;
  u32 n;
  char *zBuf;

  if( argc!=2 && argc!=3 ){
    Tcl_AppendResult(interp, "wrong # args: should be \"", argv[0],
       " ID\"", 0);
    return TCL_ERROR;
  }
  pCur = sqlite3TextToPtr(argv[1]);
  if( argc==2 ){
    sqlite3BtreeDataSize(pCur, &n);
  }else{
    n = atoi(argv[2]);
  }
  zBuf = malloc( n+1 );
  rc = sqlite3BtreeData(pCur, 0, n, zBuf);
  if( rc ){
    Tcl_AppendResult(interp, errorName(rc), 0);
    return TCL_ERROR;
  }
  zBuf[n] = 0;

**
** Various scripts scan this source file in order to generate HTML
** documentation, headers files, or other derived files.  The formatting
** of the code in this file is, therefore, important.  See other comments
** in this file for details.  If in doubt, do not deviate from existing
** commenting and indentation practices when changing or adding code.
**
** $Id: vdbe.c,v 1.436 2005/01/07 01:56:17 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include "os.h"
#include <ctype.h>
#include "vdbeInt.h"

/*
................................................................................
  if( rc!=SQLITE_OK ){
    goto abort_due_to_error;
  }
  if( zRec ){
    zData = &zRec[aOffset[p2]];
  }else{
    len = sqlite3VdbeSerialTypeLen(aType[p2]);
    sqlite3VdbeMemFromBtree(pCrsr, aOffset[p2], len, pC->keyAsData, &sMem);



    zData = sMem.z;
  }
  sqlite3VdbeSerialGet(zData, aType[p2], pTos);
  pTos->enc = db->enc;

  /* If we dynamically allocated space to hold the data (in the
  ** sqlite3VdbeMemFromBtree() call above) then transfer control of that

**
** Various scripts scan this source file in order to generate HTML
** documentation, headers files, or other derived files.  The formatting
** of the code in this file is, therefore, important.  See other comments
** in this file for details.  If in doubt, do not deviate from existing
** commenting and indentation practices when changing or adding code.
**
** $Id: vdbe.c,v 1.437 2005/01/10 12:59:53 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include "os.h"
#include <ctype.h>
#include "vdbeInt.h"

/*
................................................................................
  if( rc!=SQLITE_OK ){
    goto abort_due_to_error;
  }
  if( zRec ){
    zData = &zRec[aOffset[p2]];
  }else{
    len = sqlite3VdbeSerialTypeLen(aType[p2]);
    rc = sqlite3VdbeMemFromBtree(pCrsr, aOffset[p2], len, pC->keyAsData, &sMem);
    if( rc!=SQLITE_OK ){
      goto abort_due_to_error;
    }
    zData = sMem.z;
  }
  sqlite3VdbeSerialGet(zData, aType[p2], pTos);
  pTos->enc = db->enc;

  /* If we dynamically allocated space to hold the data (in the
  ** sqlite3VdbeMemFromBtree() call above) then transfer control of that

#    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 script is btree database backend
#
# $Id: btree.test,v 1.33 2004/11/10 15:27:38 danielk1977 Exp $


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

ifcapable default_autovacuum {
  finish_test
................................................................................
  lindex [btree_pager_stats $::b1] 1
} {1}
do_test btree-15.99 {
  btree_rollback $::b1
  lindex [btree_pager_stats $::b1] 1
} {0}
btree_pager_ref_dump $::b1


























do_test btree-99.1 {
  btree_close $::b1
} {}
catch {unset data}
catch {unset key}

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 script is btree database backend
#
# $Id: btree.test,v 1.34 2005/01/10 12:59:53 danielk1977 Exp $


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

ifcapable default_autovacuum {
  finish_test
................................................................................
  lindex [btree_pager_stats $::b1] 1
} {1}
do_test btree-15.99 {
  btree_rollback $::b1
  lindex [btree_pager_stats $::b1] 1
} {0}
btree_pager_ref_dump $::b1

# Miscellaneous tests.
#
# btree-16.1 - Check that a statement cannot be started if a transaction is not
#              active.
do_test btree-16.1 {
  catch {btree_begin_statement $::b1} msg
  set msg
} SQLITE_ERROR

do_test btree-16.2 {
  btree_begin_transaction $::b1
  set ::c1 [btree_cursor $::b1 2 1]
  btree_insert $::c1 1 helloworld
  btree_close_cursor $::c1
  btree_commit $::b1
} {}
do_test btree-16.3 {
  set ::c1 [btree_cursor $::b1 2 1]
  btree_first $::c1
} 0
do_test btree-16.4 {
  catch {btree_data $::c1 [expr [btree_payload_size $::c1] + 10]} msg
  set msg
} SQLITE_ERROR

do_test btree-99.1 {
  btree_close $::b1
} {}
catch {unset data}
catch {unset key}

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.7 2005/01/08 02:35:44 danielk1977 Exp $

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



set ::go 1
for {set n 1} {$go} {incr n} {

  # If SQLITE_DEFAULT_AUTOVACUUM is set to true, then a simulated IO error
  # on the 8th IO operation in the SQL script below doesn't report an error.
  #
  # This is because the 8th IO call attempts to read page 2 of the database
  # file when the file on disk is only 1 page. The pager layer detects that
  # this has happened and suppresses the error returned by the OS layer.
  #
  ifcapable default_autovacuum {
    if {$n==8} continue
  } 

  do_test ioerr-1.$n.1 {
    set ::sqlite_io_error_pending 0
    db close
    catch {file delete -force test.db}
................................................................................
  set cksum [string length $txt]-[md5 $txt]
  # puts $cksum-[file size test.db]
  return $cksum
}

set ::go 1
for {set n 1} {$go} {incr n} {

  do_test ioerr-2.$n.1 {
    set ::sqlite_io_error_pending 0
    db close
    catch {file delete -force test.db}
    catch {file delete -force test.db-journal}
    sqlite3 db test.db
    execsql {
................................................................................
      INSERT INTO t1 SELECT a+2, b||'-'||rowid, c||'-'||rowid FROM t1;
      INSERT INTO t1 SELECT a+4, b||'-'||rowid, c||'-'||rowid FROM t1;
      INSERT INTO t1 SELECT a+8, b||'-'||rowid, c||'-'||rowid FROM t1;
      INSERT INTO t1 SELECT a+16, b||'-'||rowid, c||'-'||rowid FROM t1;
      INSERT INTO t1 SELECT a+32, b||'-'||rowid, c||'-'||rowid FROM t1;
      INSERT INTO t1 SELECT a+64, b||'-'||rowid, c||'-'||rowid FROM t1;
      INSERT INTO t1 SELECT a+128, b||'-'||rowid, c||'-'||rowid FROM t1;

      CREATE TABLE t2 AS SELECT * FROM t1;
      CREATE TABLE t3 AS SELECT * FROM t1;
      COMMIT;
      DROP TABLE t2;
    }
    set ::cksum [cksum]
    execsql {

# 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.8 2005/01/10 12:59:53 danielk1977 Exp $

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

set ::AV [execsql {pragma auto_vacuum}]

set ::go 1
for {set n 1} {$go} {incr n} {

  # If SQLITE_DEFAULT_AUTOVACUUM is set to true, then a simulated IO error
  # on the 8th IO operation in the SQL script below doesn't report an error.
  #
  # This is because the 8th IO call attempts to read page 2 of the database
  # file when the file on disk is only 1 page. The pager layer detects that
  # this has happened and suppresses the error returned by the OS layer.
  #
  if {$::AV} {
    if {$n==8} continue
  } 

  do_test ioerr-1.$n.1 {
    set ::sqlite_io_error_pending 0
    db close
    catch {file delete -force test.db}
................................................................................
  set cksum [string length $txt]-[md5 $txt]
  # puts $cksum-[file size test.db]
  return $cksum
}

set ::go 1
for {set n 1} {$go} {incr n} {
  if {$n==24} breakpoint
  do_test ioerr-2.$n.1 {
    set ::sqlite_io_error_pending 0
    db close
    catch {file delete -force test.db}
    catch {file delete -force test.db-journal}
    sqlite3 db test.db
    execsql {
................................................................................
      INSERT INTO t1 SELECT a+2, b||'-'||rowid, c||'-'||rowid FROM t1;
      INSERT INTO t1 SELECT a+4, b||'-'||rowid, c||'-'||rowid FROM t1;
      INSERT INTO t1 SELECT a+8, b||'-'||rowid, c||'-'||rowid FROM t1;
      INSERT INTO t1 SELECT a+16, b||'-'||rowid, c||'-'||rowid FROM t1;
      INSERT INTO t1 SELECT a+32, b||'-'||rowid, c||'-'||rowid FROM t1;
      INSERT INTO t1 SELECT a+64, b||'-'||rowid, c||'-'||rowid FROM t1;
      INSERT INTO t1 SELECT a+128, b||'-'||rowid, c||'-'||rowid FROM t1;
      INSERT INTO t1 VALUES(1, randstr(600,600), randstr(600,600));
      CREATE TABLE t2 AS SELECT * FROM t1;
      CREATE TABLE t3 AS SELECT * FROM t1;
      COMMIT;
      DROP TABLE t2;
    }
    set ::cksum [cksum]
    execsql {