** 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.237 2005/01/16 11:07:07 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.
................................................................................
  MemPage *pPage;           /* Page that contains the entry */
  int idx;                  /* Index of the entry in pPage->aCell[] */
  CellInfo info;            /* A parse of the cell we are pointing at */
  u8 wrFlag;                /* True if writable */
  u8 isValid;               /* TRUE if points to a valid entry */
};














/*
** Forward declaration
*/
static int checkReadLocks(Btree*,Pgno,BtCursor*);


/*
** Read or write a two- and four-byte big-endian integer values.
*/
static u32 get2byte(unsigned char *p){
  return (p[0]<<8) | p[1];
}
................................................................................
** this test.
*/
#define PTRMAP_PAGENO(pgsz, pgno) (((pgno-2)/(pgsz/5+1))*(pgsz/5+1)+2)
#define PTRMAP_PTROFFSET(pgsz, pgno) (((pgno-2)%(pgsz/5+1)-1)*5)
#define PTRMAP_ISPAGE(pgsz, pgno) (PTRMAP_PAGENO(pgsz,pgno)==pgno)

/*
** The pointer map is a lookup table that contains an entry for each database


** page in the file except for page 1. In this context 'database page' refers
** to any page that is not part of the pointer map itself.  Each pointer map
** entry consists of a single byte 'type' and a 4 byte page number. The
** PTRMAP_XXX identifiers below are the valid types. The interpretation
** of the page-number depends on the type, as follows:





**
** PTRMAP_ROOTPAGE: The database page is a root-page. The page-number is not
**                  used in this case.
**
** PTRMAP_FREEPAGE: The database page is an unused (free) page. The page-number 
**                  is not used in this case.
**
................................................................................
/*
** Write an entry into the pointer map.
**
** This routine updates the pointer map entry for page number 'key'
** so that it maps to type 'eType' and parent page number 'pgno'.
** An error code is returned if something goes wrong, otherwise SQLITE_OK.
*/
static int ptrmapPut(Btree *pBt, Pgno key, u8 eType, Pgno pgno){
  u8 *pPtrmap;    /* The pointer map page */
  Pgno iPtrmap;   /* The pointer map page number */
  int offset;     /* Offset in pointer map page */
  int rc;

  assert( pBt->autoVacuum );
  assert( key!=0 );
................................................................................
  iPtrmap = PTRMAP_PAGENO(pBt->usableSize, key);
  rc = sqlite3pager_get(pBt->pPager, iPtrmap, (void **)&pPtrmap);
  if( rc!=SQLITE_OK ){
    return rc;
  }
  offset = PTRMAP_PTROFFSET(pBt->usableSize, key);

  if( eType!=pPtrmap[offset] || get4byte(&pPtrmap[offset+1])!=pgno ){

    rc = sqlite3pager_write(pPtrmap);
    if( rc!=0 ){
      return rc;
    }
    pPtrmap[offset] = eType;
    put4byte(&pPtrmap[offset+1], pgno);
  }

  sqlite3pager_unref(pPtrmap);
  return SQLITE_OK;
}

/*
................................................................................
    if( wrflag ) pBt->inStmt = 0;
  }else{
    unlockBtreeIfUnused(pBt);
  }
  return rc;
}

/*
** The TRACE macro will print high-level status information about the
** btree operation when the global variable sqlite3_btree_trace is
** enabled.
*/
#if SQLITE_TEST
# define TRACE(X)   if( sqlite3_btree_trace )\
                        { sqlite3DebugPrintf X; fflush(stdout); }
#else
# define TRACE(X)
#endif
int sqlite3_btree_trace=0;  /* True to enable tracing */

#ifndef SQLITE_OMIT_AUTOVACUUM

/*
** Set the pointer-map entries for all children of page pPage. Also, if
** pPage contains cells that point to overflow pages, set the pointer
** map entries for the overflow pages as well.
*/
................................................................................
*/
#define NN 1             /* Number of neighbors on either side of pPage */
#define NB (NN*2+1)      /* Total pages involved in the balance */

/* Forward reference */
static int balance(MemPage*, int);


/*
** This version of balance() handles the common special case where
** a new entry is being inserted on the extreme right-end of the
** tree, in other words, when the new entry will become the largest
** entry in the tree.
**
** Instead of trying balance the 3 right-most leaf pages, just add
................................................................................

  /* Release the reference to the new page and balance the parent page,
  ** in case the divider cell inserted caused it to become overfull.
  */
  releasePage(pNew);
  return balance(pParent, 0);
}


/*
** The ISAUTOVACUUM macro is used within balance_nonroot() to determine
** if the database supports auto-vacuum or not. Because it is used
** within an expression that is an argument to another macro 
** (sqliteMallocRaw), it is not possible to use conditional compilation.
** So, this macro is defined instead.
................................................................................
  assert( sqlite3pager_iswriteable(pPage->aData) );
  pBt = pPage->pBt;
  pParent = pPage->pParent;
  sqlite3pager_write(pParent->aData);
  assert( pParent );
  TRACE(("BALANCE: begin page %d child of %d\n", pPage->pgno, pParent->pgno));

#ifdef SQLITE_BALANCE_QUICK
  /*
  ** A special case:  If a new entry has just been inserted into a
  ** table (that is, a btree with integer keys and all data at the leaves)
  ** an the new entry is the right-most entry in the tree (it has the
  ** largest key) then use the special balance_quick() routine for
  ** balancing.  balance_quick() is much faster and results in a tighter
  ** packing of data in the common case.

** 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.238 2005/01/16 23:21:00 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.
................................................................................
  MemPage *pPage;           /* Page that contains the entry */
  int idx;                  /* Index of the entry in pPage->aCell[] */
  CellInfo info;            /* A parse of the cell we are pointing at */
  u8 wrFlag;                /* True if writable */
  u8 isValid;               /* TRUE if points to a valid entry */
};

/*
** The TRACE macro will print high-level status information about the
** btree operation when the global variable sqlite3_btree_trace is
** enabled.
*/
#if SQLITE_TEST
# define TRACE(X)   if( sqlite3_btree_trace )\
                        { sqlite3DebugPrintf X; fflush(stdout); }
#else
# define TRACE(X)
#endif
int sqlite3_btree_trace=0;  /* True to enable tracing */

/*
** Forward declaration
*/
static int checkReadLocks(Btree*,Pgno,BtCursor*);


/*
** Read or write a two- and four-byte big-endian integer values.
*/
static u32 get2byte(unsigned char *p){
  return (p[0]<<8) | p[1];
}
................................................................................
** this test.
*/
#define PTRMAP_PAGENO(pgsz, pgno) (((pgno-2)/(pgsz/5+1))*(pgsz/5+1)+2)
#define PTRMAP_PTROFFSET(pgsz, pgno) (((pgno-2)%(pgsz/5+1)-1)*5)
#define PTRMAP_ISPAGE(pgsz, pgno) (PTRMAP_PAGENO(pgsz,pgno)==pgno)

/*
** The pointer map is a lookup table that identifies the parent page for
** each child page in the database file.  The parent page is the page that
** contains a pointer to the child.  Every page in the database contains
** 0 or 1 parent pages.  (In this context 'database page' refers
** to any page that is not part of the pointer map itself.)  Each pointer map
** entry consists of a single byte 'type' and a 4 byte parent page number.
** The PTRMAP_XXX identifiers below are the valid types.

**
** The purpose of the pointer map is to facility moving pages from one
** position in the file to another as part of autovacuum.  When a page
** is moved, the pointer in its parent must be updated to point to the
** new location.  The pointer map is used to locate the parent page quickly.
**
** PTRMAP_ROOTPAGE: The database page is a root-page. The page-number is not
**                  used in this case.
**
** PTRMAP_FREEPAGE: The database page is an unused (free) page. The page-number 
**                  is not used in this case.
**
................................................................................
/*
** Write an entry into the pointer map.
**
** This routine updates the pointer map entry for page number 'key'
** so that it maps to type 'eType' and parent page number 'pgno'.
** An error code is returned if something goes wrong, otherwise SQLITE_OK.
*/
static int ptrmapPut(Btree *pBt, Pgno key, u8 eType, Pgno parent){
  u8 *pPtrmap;    /* The pointer map page */
  Pgno iPtrmap;   /* The pointer map page number */
  int offset;     /* Offset in pointer map page */
  int rc;

  assert( pBt->autoVacuum );
  assert( key!=0 );
................................................................................
  iPtrmap = PTRMAP_PAGENO(pBt->usableSize, key);
  rc = sqlite3pager_get(pBt->pPager, iPtrmap, (void **)&pPtrmap);
  if( rc!=SQLITE_OK ){
    return rc;
  }
  offset = PTRMAP_PTROFFSET(pBt->usableSize, key);

  if( eType!=pPtrmap[offset] || get4byte(&pPtrmap[offset+1])!=parent ){
    TRACE(("PTRMAP_UPDATE: %d->(%d,%d)\n", key, eType, parent));
    rc = sqlite3pager_write(pPtrmap);
    if( rc!=0 ){
      return rc;
    }
    pPtrmap[offset] = eType;
    put4byte(&pPtrmap[offset+1], parent);
  }

  sqlite3pager_unref(pPtrmap);
  return SQLITE_OK;
}

/*
................................................................................
    if( wrflag ) pBt->inStmt = 0;
  }else{
    unlockBtreeIfUnused(pBt);
  }
  return rc;
}














#ifndef SQLITE_OMIT_AUTOVACUUM

/*
** Set the pointer-map entries for all children of page pPage. Also, if
** pPage contains cells that point to overflow pages, set the pointer
** map entries for the overflow pages as well.
*/
................................................................................
*/
#define NN 1             /* Number of neighbors on either side of pPage */
#define NB (NN*2+1)      /* Total pages involved in the balance */

/* Forward reference */
static int balance(MemPage*, int);

#ifndef SQLITE_OMIT_QUICKBALANCE
/*
** This version of balance() handles the common special case where
** a new entry is being inserted on the extreme right-end of the
** tree, in other words, when the new entry will become the largest
** entry in the tree.
**
** Instead of trying balance the 3 right-most leaf pages, just add
................................................................................

  /* Release the reference to the new page and balance the parent page,
  ** in case the divider cell inserted caused it to become overfull.
  */
  releasePage(pNew);
  return balance(pParent, 0);
}
#endif /* SQLITE_OMIT_QUICKBALANCE */

/*
** The ISAUTOVACUUM macro is used within balance_nonroot() to determine
** if the database supports auto-vacuum or not. Because it is used
** within an expression that is an argument to another macro 
** (sqliteMallocRaw), it is not possible to use conditional compilation.
** So, this macro is defined instead.
................................................................................
  assert( sqlite3pager_iswriteable(pPage->aData) );
  pBt = pPage->pBt;
  pParent = pPage->pParent;
  sqlite3pager_write(pParent->aData);
  assert( pParent );
  TRACE(("BALANCE: begin page %d child of %d\n", pPage->pgno, pParent->pgno));

#ifndef SQLITE_OMIT_QUICKBALANCE
  /*
  ** A special case:  If a new entry has just been inserted into a
  ** table (that is, a btree with integer keys and all data at the leaves)
  ** an the new entry is the right-most entry in the tree (it has the
  ** largest key) then use the special balance_quick() routine for
  ** balancing.  balance_quick() is much faster and results in a tighter
  ** packing of data in the common case.

#
#***********************************************************************
# This file implements regression tests for SQLite library.
#
# This file implements tests to make sure SQLite does not crash or
# segfault if it sees a corrupt database file.
#
# $Id: corrupt.test,v 1.1 2004/08/30 16:52:19 drh Exp $

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

# Construct a large database for testing.
#
do_test corrupt-1.1 {
................................................................................
    CREATE TABLE t2 AS SELECT * FROM t1;
    DELETE FROM t2 WHERE rowid%5!=0;
    COMMIT;
    PRAGMA integrity_check;
  }
} {ok}

# Copy a file 
#
proc copy_file {from to} {
  set f [open $from]
  fconfigure $f -translation binary
  set t [open $to w]
  fconfigure $t -translation binary
  puts -nonewline $t [read $f [file size $from]]
  close $t
  close $f
}

# Setup for the tests.


copy_file test.db test.bu
set fsize [file size test.db]
set junk "abcdefghijklmnopqrstuvwxyz0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
while {[string length $junk]<256} {append junk $junk}
set junk [string range $junk 0 255]





for {set i [expr {1*256}]} {$i<$fsize-256} {incr i 256} {
  set tn [expr {$i/256}]
  db close
  copy_file test.bu test.db
  set fd [open test.db r+]
  fconfigure $fd -translation binary
  seek $fd $i
................................................................................
    catchsql {CREATE TABLE t3 AS SELECT * FROM t1}
    set x {}
  } {}
  do_test corrupt-2.$tn.6 {
    catchsql {DROP TABLE t1}
    set x {}
  } {}
if {$tn==724} btree_breakpoint
  do_test corrupt-2.$tn.7 {
    catchsql {PRAGMA integrity_check}
    set x {}
  } {}
}  

finish_test

#
#***********************************************************************
# This file implements regression tests for SQLite library.
#
# This file implements tests to make sure SQLite does not crash or
# segfault if it sees a corrupt database file.
#
# $Id: corrupt.test,v 1.2 2005/01/16 23:21:00 drh Exp $

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

# Construct a large database for testing.
#
do_test corrupt-1.1 {
................................................................................
    CREATE TABLE t2 AS SELECT * FROM t1;
    DELETE FROM t2 WHERE rowid%5!=0;
    COMMIT;
    PRAGMA integrity_check;
  }
} {ok}

# Copy file $from into $to
#
proc copy_file {from to} {
  set f [open $from]
  fconfigure $f -translation binary
  set t [open $to w]
  fconfigure $t -translation binary
  puts -nonewline $t [read $f [file size $from]]
  close $t
  close $f
}

# Setup for the tests.  Make a backup copy of the good database in test.bu.
# Create a string of garbage data that is 256 bytes long.
#
copy_file test.db test.bu
set fsize [file size test.db]
set junk "abcdefghijklmnopqrstuvwxyz0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
while {[string length $junk]<256} {append junk $junk}
set junk [string range $junk 0 255]

# Go through the database and write garbage data into each 256 segment
# of the file.  Then do various operations on the file to make sure that
# the database engine can recover gracefully from the corruption.
#
for {set i [expr {1*256}]} {$i<$fsize-256} {incr i 256} {
  set tn [expr {$i/256}]
  db close
  copy_file test.bu test.db
  set fd [open test.db r+]
  fconfigure $fd -translation binary
  seek $fd $i
................................................................................
    catchsql {CREATE TABLE t3 AS SELECT * FROM t1}
    set x {}
  } {}
  do_test corrupt-2.$tn.6 {
    catchsql {DROP TABLE t1}
    set x {}
  } {}

  do_test corrupt-2.$tn.7 {
    catchsql {PRAGMA integrity_check}
    set x {}
  } {}
}  

finish_test