** 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.690 2009/07/15 18:15:23 drh Exp $
**
** This file implements a external (disk-based) database using BTrees.
** See the header comment on "btreeInt.h" for additional information.
** Including a description of file format and an overview of operation.
*/
#include "btreeInt.h"

................................................................................
  return SQLITE_OK;
}


/*
** Move the open database page pDbPage to location iFreePage in the 
** database. The pDbPage reference remains valid.





*/
static int relocatePage(
  BtShared *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 */
  int isCommit
){
  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 || 

** 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.691 2009/07/16 18:21:18 drh Exp $
**
** This file implements a external (disk-based) database using BTrees.
** See the header comment on "btreeInt.h" for additional information.
** Including a description of file format and an overview of operation.
*/
#include "btreeInt.h"

................................................................................
  return SQLITE_OK;
}


/*
** Move the open database page pDbPage to location iFreePage in the 
** database. The pDbPage reference remains valid.
**
** The isCommit flag indicates that there is no need to remember that
** the journal needs to be sync()ed before database page pDbPage->pgno 
** can be written to. The caller has already promised not to write to that
** page.
*/
static int relocatePage(
  BtShared *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 */
  int isCommit             /* isCommit flag passed to sqlite3PagerMovepage */
){
  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 || 

**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
**
** Memory allocation functions used throughout sqlite.
**
** $Id: malloc.c,v 1.64 2009/06/27 00:48:33 drh Exp $
*/
#include "sqliteInt.h"
#include <stdarg.h>

/*
** This routine runs when the memory allocator sees that the
** total memory allocation is about to exceed the soft heap
................................................................................

  sqlite3_mutex *mutex;         /* Mutex to serialize access */

  /*
  ** The alarm callback and its arguments.  The mem0.mutex lock will
  ** be held while the callback is running.  Recursive calls into
  ** the memory subsystem are allowed, but no new callbacks will be
  ** issued.  The alarmBusy variable is set to prevent recursive
  ** callbacks.
  */
  sqlite3_int64 alarmThreshold;
  void (*alarmCallback)(void*, sqlite3_int64,int);
  void *alarmArg;
  int alarmBusy;

  /*
  ** Pointers to the end of sqlite3GlobalConfig.pScratch and
  ** sqlite3GlobalConfig.pPage to a block of memory that records
  ** which pages are available.
  */
  u32 *aScratchFree;
  u32 *aPageFree;
} mem0 = { 62560955, 0, 0, 0, 0, 0, 0, 0, 0 };

#define mem0 GLOBAL(struct Mem0Global, mem0)

/*
** Initialize the memory allocation subsystem.
*/
int sqlite3MallocInit(void){
................................................................................
/*
** Trigger the alarm 
*/
static void sqlite3MallocAlarm(int nByte){
  void (*xCallback)(void*,sqlite3_int64,int);
  sqlite3_int64 nowUsed;
  void *pArg;
  if( mem0.alarmCallback==0 || mem0.alarmBusy  ) return;
  mem0.alarmBusy = 1;
  xCallback = mem0.alarmCallback;
  nowUsed = sqlite3StatusValue(SQLITE_STATUS_MEMORY_USED);
  pArg = mem0.alarmArg;

  sqlite3_mutex_leave(mem0.mutex);
  xCallback(pArg, nowUsed, nByte);
  sqlite3_mutex_enter(mem0.mutex);

  mem0.alarmBusy = 0;
}

/*
** Do a memory allocation with statistics and alarms.  Assume the
** lock is already held.
*/
static int mallocWithAlarm(int n, void **pp){

**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
**
** Memory allocation functions used throughout sqlite.
**
** $Id: malloc.c,v 1.65 2009/07/16 18:21:18 drh Exp $
*/
#include "sqliteInt.h"
#include <stdarg.h>

/*
** This routine runs when the memory allocator sees that the
** total memory allocation is about to exceed the soft heap
................................................................................

  sqlite3_mutex *mutex;         /* Mutex to serialize access */

  /*
  ** The alarm callback and its arguments.  The mem0.mutex lock will
  ** be held while the callback is running.  Recursive calls into
  ** the memory subsystem are allowed, but no new callbacks will be
  ** issued.

  */
  sqlite3_int64 alarmThreshold;
  void (*alarmCallback)(void*, sqlite3_int64,int);
  void *alarmArg;


  /*
  ** Pointers to the end of sqlite3GlobalConfig.pScratch and
  ** sqlite3GlobalConfig.pPage to a block of memory that records
  ** which pages are available.
  */
  u32 *aScratchFree;
  u32 *aPageFree;
} mem0 = { 0, 0, 0, 0, 0, 0, 0, 0 };

#define mem0 GLOBAL(struct Mem0Global, mem0)

/*
** Initialize the memory allocation subsystem.
*/
int sqlite3MallocInit(void){
................................................................................
/*
** Trigger the alarm 
*/
static void sqlite3MallocAlarm(int nByte){
  void (*xCallback)(void*,sqlite3_int64,int);
  sqlite3_int64 nowUsed;
  void *pArg;
  if( mem0.alarmCallback==0 ) return;

  xCallback = mem0.alarmCallback;
  nowUsed = sqlite3StatusValue(SQLITE_STATUS_MEMORY_USED);
  pArg = mem0.alarmArg;
  mem0.alarmCallback = 0;
  sqlite3_mutex_leave(mem0.mutex);
  xCallback(pArg, nowUsed, nByte);
  sqlite3_mutex_enter(mem0.mutex);
  mem0.alarmCallback = xCallback;
  mem0.alarmArg = pArg;
}

/*
** Do a memory allocation with statistics and alarms.  Assume the
** lock is already held.
*/
static int mallocWithAlarm(int n, void **pp){

**
*************************************************************************
** This file contains the C functions that implement mutexes.
**
** This file contains code that is common across all mutex implementations.

**
** $Id: mutex.c,v 1.30 2009/02/17 16:29:11 danielk1977 Exp $
*/
#include "sqliteInt.h"

#ifndef SQLITE_MUTEX_OMIT
/*
** Initialize the mutex system.
*/
................................................................................
  int rc = SQLITE_OK;
  if( sqlite3GlobalConfig.bCoreMutex ){
    if( !sqlite3GlobalConfig.mutex.xMutexAlloc ){
      /* If the xMutexAlloc method has not been set, then the user did not
      ** install a mutex implementation via sqlite3_config() prior to 
      ** sqlite3_initialize() being called. This block copies pointers to
      ** the default implementation into the sqlite3GlobalConfig structure.
      **
      ** The danger is that although sqlite3_config() is not a threadsafe
      ** API, sqlite3_initialize() is, and so multiple threads may be
      ** attempting to run this function simultaneously. To guard write
      ** access to the sqlite3GlobalConfig structure, the 'MASTER' static mutex
      ** is obtained before modifying it.
      */
      sqlite3_mutex_methods *p = sqlite3DefaultMutex();
      sqlite3_mutex *pMaster = 0;
  
      rc = p->xMutexInit();
      if( rc==SQLITE_OK ){
        pMaster = p->xMutexAlloc(SQLITE_MUTEX_STATIC_MASTER);
        assert(pMaster);
        p->xMutexEnter(pMaster);
        assert( sqlite3GlobalConfig.mutex.xMutexAlloc==0 
             || sqlite3GlobalConfig.mutex.xMutexAlloc==p->xMutexAlloc
        );
        if( !sqlite3GlobalConfig.mutex.xMutexAlloc ){
          sqlite3GlobalConfig.mutex = *p;
        }
        p->xMutexLeave(pMaster);




      }
    }else{
      rc = sqlite3GlobalConfig.mutex.xMutexInit();
    }
  }

  return rc;
}

/*
** Shutdown the mutex system. This call frees resources allocated by

**
*************************************************************************
** This file contains the C functions that implement mutexes.
**
** This file contains code that is common across all mutex implementations.

**
** $Id: mutex.c,v 1.31 2009/07/16 18:21:18 drh Exp $
*/
#include "sqliteInt.h"

#ifndef SQLITE_MUTEX_OMIT
/*
** Initialize the mutex system.
*/
................................................................................
  int rc = SQLITE_OK;
  if( sqlite3GlobalConfig.bCoreMutex ){
    if( !sqlite3GlobalConfig.mutex.xMutexAlloc ){
      /* If the xMutexAlloc method has not been set, then the user did not
      ** install a mutex implementation via sqlite3_config() prior to 
      ** sqlite3_initialize() being called. This block copies pointers to
      ** the default implementation into the sqlite3GlobalConfig structure.






      */
      sqlite3_mutex_methods *pFrom = sqlite3DefaultMutex();











      sqlite3_mutex_methods *pTo = &sqlite3GlobalConfig.mutex;


      memcpy(pTo, pFrom, offsetof(sqlite3_mutex_methods, xMutexAlloc));
      memcpy(&pTo->xMutexFree, &pFrom->xMutexFree,
             sizeof(*pTo) - offsetof(sqlite3_mutex_methods, xMutexFree));
      pTo->xMutexAlloc = pFrom->xMutexAlloc;
    }

    rc = sqlite3GlobalConfig.mutex.xMutexInit();

  }

  return rc;
}

/*
** Shutdown the mutex system. This call frees resources allocated by

**    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.
**
*************************************************************************
** This file implements that page cache.
**
** @(#) $Id: pcache.c,v 1.44 2009/03/31 01:32:18 drh Exp $
*/
#include "sqliteInt.h"

/*
** A complete page cache is an instance of this structure.
*/
struct PCache {
................................................................................
  return result.pDirty;
}

/*
** Sort the list of pages in accending order by pgno.  Pages are
** connected by pDirty pointers.  The pDirtyPrev pointers are
** corrupted by this sort.





*/
#define N_SORT_BUCKET_ALLOC 25
#define N_SORT_BUCKET       25
#ifdef SQLITE_TEST
  int sqlite3_pager_n_sort_bucket = 0;
  #undef N_SORT_BUCKET
  #define N_SORT_BUCKET \
   (sqlite3_pager_n_sort_bucket?sqlite3_pager_n_sort_bucket:N_SORT_BUCKET_ALLOC)
#endif
static PgHdr *pcacheSortDirtyList(PgHdr *pIn){
  PgHdr *a[N_SORT_BUCKET_ALLOC], *p;
  int i;
  memset(a, 0, sizeof(a));
  while( pIn ){
    p = pIn;
    pIn = p->pDirty;
    p->pDirty = 0;
    for(i=0; i<N_SORT_BUCKET-1; i++){
      if( a[i]==0 ){
        a[i] = p;
        break;
      }else{
        p = pcacheMergeDirtyList(a[i], p);
        a[i] = 0;
      }
    }
    if( i==N_SORT_BUCKET-1 ){
      /* Coverage: To get here, there need to be 2^(N_SORT_BUCKET) 
      ** elements in the input list. This is possible, but impractical.
      ** Testing this line is the point of global variable
      ** sqlite3_pager_n_sort_bucket.
      */
      a[i] = pcacheMergeDirtyList(a[i], p);
    }
  }
  p = a[0];
  for(i=1; i<N_SORT_BUCKET; i++){
    p = pcacheMergeDirtyList(p, a[i]);

**    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.
**
*************************************************************************
** This file implements that page cache.
**
** @(#) $Id: pcache.c,v 1.45 2009/07/16 18:21:18 drh Exp $
*/
#include "sqliteInt.h"

/*
** A complete page cache is an instance of this structure.
*/
struct PCache {
................................................................................
  return result.pDirty;
}

/*
** Sort the list of pages in accending order by pgno.  Pages are
** connected by pDirty pointers.  The pDirtyPrev pointers are
** corrupted by this sort.
**
** Since there cannot be more than 2^31 distinct pages in a database,
** there cannot be more than 31 buckets required by the merge sorter.
** One extra bucket is added to catch overflow in case something
** ever changes to make the previous sentence incorrect.
*/





#define N_SORT_BUCKET  32


static PgHdr *pcacheSortDirtyList(PgHdr *pIn){
  PgHdr *a[N_SORT_BUCKET], *p;
  int i;
  memset(a, 0, sizeof(a));
  while( pIn ){
    p = pIn;
    pIn = p->pDirty;
    p->pDirty = 0;
    for(i=0; ALWAYS(i<N_SORT_BUCKET-1); i++){
      if( a[i]==0 ){
        a[i] = p;
        break;
      }else{
        p = pcacheMergeDirtyList(a[i], p);
        a[i] = 0;
      }
    }
    if( NEVER(i==N_SORT_BUCKET-1) ){
      /* To get here, there need to be 2^(N_SORT_BUCKET) elements in
      ** the input list.  But that is impossible.


      */
      a[i] = pcacheMergeDirtyList(a[i], p);
    }
  }
  p = a[0];
  for(i=1; i<N_SORT_BUCKET; i++){
    p = pcacheMergeDirtyList(p, a[i]);

**
** This file implements the default page cache implementation (the
** sqlite3_pcache interface). It also contains part of the implementation
** of the SQLITE_CONFIG_PAGECACHE and sqlite3_release_memory() features.
** If the default page cache implementation is overriden, then neither of
** these two features are available.
**
** @(#) $Id: pcache1.c,v 1.17 2009/06/09 18:58:53 shane Exp $
*/

#include "sqliteInt.h"

typedef struct PCache1 PCache1;
typedef struct PgHdr1 PgHdr1;
typedef struct PgFreeslot PgFreeslot;
................................................................................
  *pp = pPage->pNext;

  h = iNew%pCache->nHash;
  pPage->iKey = iNew;
  pPage->pNext = pCache->apHash[h];
  pCache->apHash[h] = pPage;








  if( iNew>pCache->iMaxKey ){
    pCache->iMaxKey = iNew;
  }

  pcache1LeaveMutex();
}

/*

**
** This file implements the default page cache implementation (the
** sqlite3_pcache interface). It also contains part of the implementation
** of the SQLITE_CONFIG_PAGECACHE and sqlite3_release_memory() features.
** If the default page cache implementation is overriden, then neither of
** these two features are available.
**
** @(#) $Id: pcache1.c,v 1.18 2009/07/16 18:21:18 drh Exp $
*/

#include "sqliteInt.h"

typedef struct PCache1 PCache1;
typedef struct PgHdr1 PgHdr1;
typedef struct PgFreeslot PgFreeslot;
................................................................................
  *pp = pPage->pNext;

  h = iNew%pCache->nHash;
  pPage->iKey = iNew;
  pPage->pNext = pCache->apHash[h];
  pCache->apHash[h] = pPage;

  /* The xRekey() interface is only used to move pages earlier in the
  ** database file (in order to move all free pages to the end of the
  ** file where they can be truncated off.)  Hence, it is not possible
  ** for the new page number to be greater than the largest previously
  ** fetched page.  But we retain the following test in case xRekey()
  ** begins to be used in different ways in the future.
  */
  if( NEVER(iNew>pCache->iMaxKey) ){
    pCache->iMaxKey = iNew;
  }

  pcache1LeaveMutex();
}

/*

**    May you share freely, never taking more than you give.
**
*************************************************************************
** Code for testing the pager.c module in SQLite.  This code
** is not included in the SQLite library.  It is used for automated
** testing of the SQLite library.
**
** $Id: test2.c,v 1.71 2009/06/18 17:22:39 drh Exp $
*/
#include "sqliteInt.h"
#include "tcl.h"
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

................................................................................
int Sqlitetest2_Init(Tcl_Interp *interp){
  extern int sqlite3_io_error_persist;
  extern int sqlite3_io_error_pending;
  extern int sqlite3_io_error_hit;
  extern int sqlite3_io_error_hardhit;
  extern int sqlite3_diskfull_pending;
  extern int sqlite3_diskfull;
  extern int sqlite3_pager_n_sort_bucket;
  static struct {
    char *zName;
    Tcl_CmdProc *xProc;
  } aCmd[] = {
    { "pager_open",              (Tcl_CmdProc*)pager_open          },
    { "pager_close",             (Tcl_CmdProc*)pager_close         },
    { "pager_commit",            (Tcl_CmdProc*)pager_commit        },
................................................................................
     (char*)&sqlite3_io_error_hardhit, TCL_LINK_INT);
  Tcl_LinkVar(interp, "sqlite_diskfull_pending",
     (char*)&sqlite3_diskfull_pending, TCL_LINK_INT);
  Tcl_LinkVar(interp, "sqlite_diskfull",
     (char*)&sqlite3_diskfull, TCL_LINK_INT);
  Tcl_LinkVar(interp, "sqlite_pending_byte",
     (char*)&sqlite3PendingByte, TCL_LINK_INT | TCL_LINK_READ_ONLY);
  Tcl_LinkVar(interp, "sqlite_pager_n_sort_bucket",
     (char*)&sqlite3_pager_n_sort_bucket, TCL_LINK_INT);
  return TCL_OK;
}

**    May you share freely, never taking more than you give.
**
*************************************************************************
** Code for testing the pager.c module in SQLite.  This code
** is not included in the SQLite library.  It is used for automated
** testing of the SQLite library.
**
** $Id: test2.c,v 1.72 2009/07/16 18:21:18 drh Exp $
*/
#include "sqliteInt.h"
#include "tcl.h"
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

................................................................................
int Sqlitetest2_Init(Tcl_Interp *interp){
  extern int sqlite3_io_error_persist;
  extern int sqlite3_io_error_pending;
  extern int sqlite3_io_error_hit;
  extern int sqlite3_io_error_hardhit;
  extern int sqlite3_diskfull_pending;
  extern int sqlite3_diskfull;

  static struct {
    char *zName;
    Tcl_CmdProc *xProc;
  } aCmd[] = {
    { "pager_open",              (Tcl_CmdProc*)pager_open          },
    { "pager_close",             (Tcl_CmdProc*)pager_close         },
    { "pager_commit",            (Tcl_CmdProc*)pager_commit        },
................................................................................
     (char*)&sqlite3_io_error_hardhit, TCL_LINK_INT);
  Tcl_LinkVar(interp, "sqlite_diskfull_pending",
     (char*)&sqlite3_diskfull_pending, TCL_LINK_INT);
  Tcl_LinkVar(interp, "sqlite_diskfull",
     (char*)&sqlite3_diskfull, TCL_LINK_INT);
  Tcl_LinkVar(interp, "sqlite_pending_byte",
     (char*)&sqlite3PendingByte, TCL_LINK_INT | TCL_LINK_READ_ONLY);


  return TCL_OK;
}

#    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.
#
#***********************************************************************
# This file implements regression tests for SQLite library.
#
# $Id: misc7.test,v 1.28 2009/02/10 05:45:42 danielk1977 Exp $

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

do_test misc7-1-misuse {
  c_misuse_test
} {}
................................................................................

do_test misc7-16.X {
  execsql {
    SELECT count(*) FROM t3;
  }
} {32}

set sqlite_pager_n_sort_bucket 4
do_test misc7-17 {
  execsql {
    PRAGMA integrity_check;
    VACUUM;
    PRAGMA integrity_check;
  }
} {ok ok}
set sqlite_pager_n_sort_bucket 0

#----------------------------------------------------------------------
# Test the situation where a hot-journal is discovered but write-access
# to it is denied. This should return SQLITE_BUSY.
#
# These tests do not work on windows due to restrictions in the
# windows file system.
#

#    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.
#
#***********************************************************************
# This file implements regression tests for SQLite library.
#
# $Id: misc7.test,v 1.29 2009/07/16 18:21:18 drh Exp $

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

do_test misc7-1-misuse {
  c_misuse_test
} {}
................................................................................

do_test misc7-16.X {
  execsql {
    SELECT count(*) FROM t3;
  }
} {32}











#----------------------------------------------------------------------
# Test the situation where a hot-journal is discovered but write-access
# to it is denied. This should return SQLITE_BUSY.
#
# These tests do not work on windows due to restrictions in the
# windows file system.
#