** 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.506 2008/09/02 00:52:52 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"

................................................................................
** Enable or disable the shared pager and schema features.
**
** This routine has no effect on existing database connections.
** The shared cache setting effects only future calls to
** sqlite3_open(), sqlite3_open16(), or sqlite3_open_v2().
*/
int sqlite3_enable_shared_cache(int enable){
  GLOBAL(int,sqlite3SharedCacheEnabled) = enable;
  return SQLITE_OK;
}
#endif


/*
** Forward declaration

** 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.507 2008/09/02 09:38:07 danielk1977 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"

................................................................................
** Enable or disable the shared pager and schema features.
**
** This routine has no effect on existing database connections.
** The shared cache setting effects only future calls to
** sqlite3_open(), sqlite3_open16(), or sqlite3_open_v2().
*/
int sqlite3_enable_shared_cache(int enable){
  GLOBAL(int, sqlite3SharedCacheEnabled) = enable;
  return SQLITE_OK;
}
#endif


/*
** Forward declaration

**
*************************************************************************
** Main file for the SQLite library.  The routines in this file
** implement the programmer interface to the library.  Routines in
** other files are for internal use by SQLite and should not be
** accessed by users of the library.
**
** $Id: main.c,v 1.495 2008/09/01 18:34:20 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

#ifdef SQLITE_ENABLE_FTS3
# include "fts3.h"
#endif
................................................................................
    FuncDefHash *pHash = &GLOBAL(FuncDefHash, sqlite3GlobalFunctions);
    GLOBAL(int, inProgress) = 1;
    memset(pHash, 0, sizeof(sqlite3GlobalFunctions));
    sqlite3RegisterGlobalFunctions();
    rc = sqlite3_os_init();
    if( rc==SQLITE_OK ){
      rc = sqlite3PcacheInitialize();
      sqlite3PCacheBufferSetup(sqlite3GlobalConfig.pPage, sqlite3GlobalConfig.szPage, 
          sqlite3GlobalConfig.nPage);
    }
    GLOBAL(int, inProgress) = 0;
    sqlite3GlobalConfig.isInit = (rc==SQLITE_OK ? 1 : 0);
  }
  sqlite3_mutex_leave(sqlite3GlobalConfig.pInitMutex);

  /* Go back under the static mutex and clean up the recursive

**
*************************************************************************
** Main file for the SQLite library.  The routines in this file
** implement the programmer interface to the library.  Routines in
** other files are for internal use by SQLite and should not be
** accessed by users of the library.
**
** $Id: main.c,v 1.496 2008/09/02 09:38:07 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

#ifdef SQLITE_ENABLE_FTS3
# include "fts3.h"
#endif
................................................................................
    FuncDefHash *pHash = &GLOBAL(FuncDefHash, sqlite3GlobalFunctions);
    GLOBAL(int, inProgress) = 1;
    memset(pHash, 0, sizeof(sqlite3GlobalFunctions));
    sqlite3RegisterGlobalFunctions();
    rc = sqlite3_os_init();
    if( rc==SQLITE_OK ){
      rc = sqlite3PcacheInitialize();
      sqlite3PCacheBufferSetup( sqlite3GlobalConfig.pPage, 
          sqlite3GlobalConfig.szPage, sqlite3GlobalConfig.nPage);
    }
    GLOBAL(int, inProgress) = 0;
    sqlite3GlobalConfig.isInit = (rc==SQLITE_OK ? 1 : 0);
  }
  sqlite3_mutex_leave(sqlite3GlobalConfig.pInitMutex);

  /* Go back under the static mutex and clean up the recursive

**    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.25 2008/09/01 18:34:20 danielk1977 Exp $
*/
#include "sqliteInt.h"

/*
** A complete page cache is an instance of this structure.
**
** A cache may only be deleted by its owner and while holding the
................................................................................
struct PgFreeslot {
  PgFreeslot *pNext;  /* Next free slot */
};

/*
** Global data for the page cache.
*/
static struct PCacheGlobal {
  int isInit;                         /* True when initialized */
  sqlite3_mutex *mutex;               /* static mutex MUTEX_STATIC_LRU */

  int nMaxPage;                       /* Sum of nMaxPage for purgeable caches */
  int nMinPage;                       /* Sum of nMinPage for purgeable caches */
  int nCurrentPage;                   /* Number of purgeable pages allocated */
  PgHdr *pLruHead, *pLruTail;         /* LRU list of unused clean pgs */
................................................................................

  /* Variables related to SQLITE_CONFIG_PAGECACHE settings. */
  int szSlot;                         /* Size of each free slot */
  void *pStart, *pEnd;                /* Bounds of pagecache malloc range */
  PgFreeslot *pFree;                  /* Free page blocks */
} pcache = {0};








/*
** All global variables used by this module (all of which are grouped 
** together in global structure "pcache" above) are protected by the static 
** SQLITE_MUTEX_STATIC_LRU mutex. A pointer to this mutex is stored in
** variable "pcache.mutex".
**
** Some elements of the PCache and PgHdr structures are protected by the 
................................................................................
** marked.
**
** Use the following macros must surround all access (read or write)
** of protected elements.  The mutex is not recursive and may not be
** entered more than once.  The pcacheMutexHeld() macro should only be
** used within an assert() to verify that the mutex is being held.
*/
#define pcacheEnterMutex() sqlite3_mutex_enter(pcache.mutex)
#define pcacheExitMutex()  sqlite3_mutex_leave(pcache.mutex)
#define pcacheMutexHeld()  sqlite3_mutex_held(pcache.mutex)

/*
** Some of the assert() macros in this code are too expensive to run
** even during normal debugging.  Use them only rarely on long-running
** tests.  Enable the expensive asserts using the
** -DSQLITE_ENABLE_EXPENSIVE_ASSERT=1 compile-time option.
*/
................................................................................
  }
}

/*
** Remove a page from the global LRU list
*/
static void pcacheRemoveFromLruList(PgHdr *pPage){
  assert( sqlite3_mutex_held(pcache.mutex) );
  assert( (pPage->flags&PGHDR_DIRTY)==0 );
  if( pPage->pCache->bPurgeable==0 ) return;
  if( pPage->pNextLru ){
    assert( pcache.pLruTail!=pPage );
    pPage->pNextLru->pPrevLru = pPage->pPrevLru;
  }else{
    assert( pcache.pLruTail==pPage );
    pcache.pLruTail = pPage->pPrevLru;
  }
  if( pPage->pPrevLru ){
    assert( pcache.pLruHead!=pPage );
    pPage->pPrevLru->pNextLru = pPage->pNextLru;
  }else{
    assert( pcache.pLruHead==pPage );
    pcache.pLruHead = pPage->pNextLru;
  }
}

/*
** Add a page to the global LRU list.  The page is normally added
** to the front of the list so that it will be the last page recycled.
** However, if the PGHDR_REUSE_UNLIKELY bit is set, the page is added
** to the end of the LRU list so that it will be the next to be recycled.
*/
static void pcacheAddToLruList(PgHdr *pPage){
  assert( sqlite3_mutex_held(pcache.mutex) );
  assert( (pPage->flags&PGHDR_DIRTY)==0 );
  if( pPage->pCache->bPurgeable==0 ) return;
  if( pcache.pLruTail && (pPage->flags & PGHDR_REUSE_UNLIKELY)!=0 ){
    /* If reuse is unlikely.  Put the page at the end of the LRU list
    ** where it will be recycled sooner rather than later. 
    */
    assert( pcache.pLruHead );
    pPage->pNextLru = 0;
    pPage->pPrevLru = pcache.pLruTail;
    pcache.pLruTail->pNextLru = pPage;
    pcache.pLruTail = pPage;
    pPage->flags &= ~PGHDR_REUSE_UNLIKELY;
  }else{
    /* If reuse is possible. the page goes at the beginning of the LRU
    ** list so that it will be the last to be recycled.
    */
    if( pcache.pLruHead ){
      pcache.pLruHead->pPrevLru = pPage;
    }
    pPage->pNextLru = pcache.pLruHead;
    pcache.pLruHead = pPage;
    pPage->pPrevLru = 0;
    if( pcache.pLruTail==0 ){
      pcache.pLruTail = pPage;
    }
  }
}

/*********************************************** Memory Allocation ***********
**
** Initialize the page cache memory pool.
................................................................................
**
** This must be called at start-time when no page cache lines are
** checked out. This function is not threadsafe.
*/
void sqlite3PCacheBufferSetup(void *pBuf, int sz, int n){
  PgFreeslot *p;
  sz &= ~7;
  pcache.szSlot = sz;
  pcache.pStart = pBuf;
  pcache.pFree = 0;
  while( n-- ){
    p = (PgFreeslot*)pBuf;
    p->pNext = pcache.pFree;
    pcache.pFree = p;
    pBuf = (void*)&((char*)pBuf)[sz];
  }
  pcache.pEnd = pBuf;
}

/*
** Allocate a page cache line.  Look in the page cache memory pool first
** and use an element from it first if available.  If nothing is available
** in the page cache memory pool, go to the general purpose memory allocator.
*/
void *pcacheMalloc(int sz, PCache *pCache){
  assert( sqlite3_mutex_held(pcache.mutex) );
  if( sz<=pcache.szSlot && pcache.pFree ){
    PgFreeslot *p = pcache.pFree;
    pcache.pFree = p->pNext;
    sqlite3StatusSet(SQLITE_STATUS_PAGECACHE_SIZE, sz);
    sqlite3StatusAdd(SQLITE_STATUS_PAGECACHE_USED, 1);
    return (void*)p;
  }else{
    void *p;

    /* Allocate a new buffer using sqlite3Malloc. Before doing so, exit the
................................................................................
  return p;
}

/*
** Release a pager memory allocation
*/
void pcacheFree(void *p){
  assert( sqlite3_mutex_held(pcache.mutex) );
  if( p==0 ) return;
  if( p>=pcache.pStart && p<pcache.pEnd ){
    PgFreeslot *pSlot;
    sqlite3StatusAdd(SQLITE_STATUS_PAGECACHE_USED, -1);
    pSlot = (PgFreeslot*)p;
    pSlot->pNext = pcache.pFree;
    pcache.pFree = pSlot;
  }else{
    int iSize = sqlite3MallocSize(p);
    sqlite3StatusAdd(SQLITE_STATUS_PAGECACHE_OVERFLOW, -iSize);
    sqlite3_free(p);
  }
}
void sqlite3PageFree(void *p){
................................................................................

/*
** Allocate a new page.
*/
static PgHdr *pcachePageAlloc(PCache *pCache){
  PgHdr *p;
  int sz = sizeof(*p) + pCache->szPage + pCache->szExtra;
  assert( sqlite3_mutex_held(pcache.mutex) );
  p = pcacheMalloc(sz, pCache);
  if( p==0 ) return 0;
  memset(p, 0, sizeof(PgHdr));
  p->pData = (void*)&p[1];
  p->pExtra = (void*)&((char*)p->pData)[pCache->szPage];
  if( pCache->bPurgeable ){
    pcache.nCurrentPage++;
  }
  return p;
}

/*
** Deallocate a page
*/
static void pcachePageFree(PgHdr *p){
  assert( sqlite3_mutex_held(pcache.mutex) );
  if( p->pCache->bPurgeable ){
    pcache.nCurrentPage--;
  }
  pcacheFree(p->apSave[0]);
  pcacheFree(p->apSave[1]);
  pcacheFree(p);
}

#ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
/*
** Return the number of bytes that will be returned to the heap when
** the argument is passed to pcachePageFree().
*/
static int pcachePageSize(PgHdr *p){
  assert( sqlite3_mutex_held(pcache.mutex) );
  assert( !pcache.pStart );
  assert( p->apSave[0]==0 );
  assert( p->apSave[1]==0 );
  assert( p && p->pCache );
  return sqlite3MallocSize(p);
}
#endif

................................................................................
** There should be no other references to the page.
**
** A pointer to the recycled page is returned, or NULL if no page is
** eligible for recycling.
*/
static PgHdr *pcacheRecyclePage(){
  PgHdr *p = 0;
  assert( sqlite3_mutex_held(pcache.mutex) );

  if( (p=pcache.pLruTail) ){
    assert( (p->flags&PGHDR_DIRTY)==0 );
    pcacheRemoveFromLruList(p);
    pcacheRemoveFromHash(p);
    pcacheRemoveFromList(&p->pCache->pClean, p);
  }

  return p;
................................................................................
*/
static int pcacheRecycleOrAlloc(PCache *pCache, PgHdr **ppPage){
  PgHdr *p = 0;

  int szPage = pCache->szPage;
  int szExtra = pCache->szExtra;

  assert( pcache.isInit );
  assert( sqlite3_mutex_held(pcache.mutex) );

  *ppPage = 0;

  /* If we have reached the limit for pinned/dirty pages, and there is at
  ** least one dirty page, invoke the xStress callback to cause a page to
  ** become clean.
  */
  expensive_assert( pCache->nPinned==pcachePinnedCount(pCache) );
  expensive_assert( pcacheCheckSynced(pCache) );
  if( pCache->xStress
   && pCache->pDirty
   && pCache->nPinned>=(pcache.nMaxPage+pCache->nMin-pcache.nMinPage)
  ){
    PgHdr *pPg;
    assert(pCache->pDirtyTail);

    for(pPg=pCache->pSynced; 
        pPg && (pPg->nRef || (pPg->flags&PGHDR_NEED_SYNC)); 
        pPg=pPg->pPrev
................................................................................
      if( rc!=SQLITE_OK && rc!=SQLITE_BUSY ){
        return rc;
      }
    }
  }

  /* If the global page limit has been reached, try to recycle a page. */
  if( pCache->bPurgeable && pcache.nCurrentPage>=pcache.nMaxPage ){
    p = pcacheRecyclePage();
  }

  /* If a page has been recycled but it is the wrong size, free it. */
  if( p && (p->pCache->szPage!=szPage || p->pCache->szPage!=szExtra) ){
    pcachePageFree(p);
    p = 0;
................................................................................

/*************************************************** General Interfaces ******
**
** Initialize and shutdown the page cache subsystem. Neither of these 
** functions are threadsafe.
*/
int sqlite3PcacheInitialize(void){
  assert( pcache.isInit==0 );
  memset(&pcache, 0, sizeof(pcache));
  if( sqlite3GlobalConfig.bCoreMutex ){
    /* No need to check the return value of sqlite3_mutex_alloc(). 
    ** Allocating a static mutex cannot fail.
    */
    pcache.mutex = sqlite3_mutex_alloc(SQLITE_MUTEX_STATIC_LRU);
  }
  pcache.isInit = 1;
  return SQLITE_OK;
}
void sqlite3PcacheShutdown(void){
  memset(&pcache, 0, sizeof(pcache));
}

/*
** Return the size in bytes of a PCache object.
*/
int sqlite3PcacheSize(void){ return sizeof(PCache); }

................................................................................
  int szExtra,                 /* Extra space associated with each page */
  int bPurgeable,              /* True if pages are on backing store */
  void (*xDestroy)(PgHdr*),    /* Called to destroy a page */
  int (*xStress)(void*,PgHdr*),/* Call to try to make pages clean */
  void *pStress,               /* Argument to xStress */
  PCache *p                    /* Preallocated space for the PCache */
){
  assert( pcache.isInit );
  memset(p, 0, sizeof(PCache));
  p->szPage = szPage;
  p->szExtra = szExtra;
  p->bPurgeable = bPurgeable;
  p->xDestroy = xDestroy;
  p->xStress = xStress;
  p->pStress = pStress;
  p->nMax = 100;
  p->nMin = 10;

  pcacheEnterMutex();
  if( bPurgeable ){
    pcache.nMaxPage += p->nMax;
    pcache.nMinPage += p->nMin;
  }

  pcacheExitMutex();
}

/*
** Change the page size for PCache object.  This can only happen
................................................................................
  Pgno pgno,            /* Page number to obtain */
  int createFlag,       /* If true, create page if it does not exist already */
  PgHdr **ppPage        /* Write the page here */
){
  int rc = SQLITE_OK;
  PgHdr *pPage = 0;

  assert( pcache.isInit );
  assert( pCache!=0 );
  assert( pgno>0 );
  expensive_assert( pCache->nPinned==pcachePinnedCount(pCache) );

  pcacheEnterMutex();

  /* Search the hash table for the requested page. Exit early if it is found. */
................................................................................
    if( p->pCache->xDestroy ){
      p->pCache->xDestroy(p);
    }
    pCache->nRef--;
    if( (p->flags&PGHDR_DIRTY)==0 ){
      pCache->nPinned--;
      pcacheEnterMutex();
      if( pcache.nCurrentPage>pcache.nMaxPage ){
        pcacheRemoveFromList(&pCache->pClean, p);
        pcacheRemoveFromHash(p);
        pcachePageFree(p);
      }else{
        pcacheAddToLruList(p);
      }
      pcacheExitMutex();
................................................................................
}

/*
** Remove all content from a page cache
*/
void pcacheClear(PCache *pCache){
  PgHdr *p, *pNext;
  assert( sqlite3_mutex_held(pcache.mutex) );
  for(p=pCache->pClean; p; p=pNext){
    pNext = p->pNext;
    pcacheRemoveFromLruList(p);
    pcachePageFree(p);
  }
  for(p=pCache->pDirty; p; p=pNext){
    pNext = p->pNext;
................................................................................

/*
** If there are currently more than pcache.nMaxPage pages allocated, try
** to recycle pages to reduce the number allocated to pcache.nMaxPage.
*/
static void pcacheEnforceMaxPage(){
  PgHdr *p;
  assert( sqlite3_mutex_held(pcache.mutex) );
  while( pcache.nCurrentPage>pcache.nMaxPage && (p = pcacheRecyclePage()) ){
    pcachePageFree(p);
  }
}

/*
** Close a cache.
*/
void sqlite3PcacheClose(PCache *pCache){
  pcacheEnterMutex();

  /* Free all the pages used by this pager and remove them from the LRU list. */
  pcacheClear(pCache);
  if( pCache->bPurgeable ){
    pcache.nMaxPage -= pCache->nMax;
    pcache.nMinPage -= pCache->nMin;
    pcacheEnforceMaxPage();
  }
  sqlite3_free(pCache->apHash);
  pcacheExitMutex();
}

/*
................................................................................
*/
void sqlite3PcacheSetCachesize(PCache *pCache, int mxPage){
  if( mxPage<10 ){
    mxPage = 10;
  }
  if( pCache->bPurgeable ){
    pcacheEnterMutex();
    pcache.nMaxPage -= pCache->nMax;
    pcache.nMaxPage += mxPage;
    pcacheEnforceMaxPage();
    pcacheExitMutex();
  }
  pCache->nMax = mxPage;
}

#ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
................................................................................
**
** nReq is the number of bytes of memory required. Once this much has
** been released, the function returns. The return value is the total number 
** of bytes of memory released.
*/
int sqlite3PcacheReleaseMemory(int nReq){
  int nFree = 0;
  if( pcache.pStart==0 ){
    PgHdr *p;
    pcacheEnterMutex();
    while( (nReq<0 || nFree<nReq) && (p=pcacheRecyclePage()) ){
      nFree += pcachePageSize(p);
      pcachePageFree(p);
    }
    pcacheExitMutex();
................................................................................
  int *pnCurrent,
  int *pnMax,
  int *pnMin,
  int *pnRecyclable
){
  PgHdr *p;
  int nRecyclable = 0;
  for(p=pcache.pLruHead; p; p=p->pNextLru){
    nRecyclable++;
  }

  *pnCurrent = pcache.nCurrentPage;
  *pnMax = pcache.nMaxPage;
  *pnMin = pcache.nMinPage;
  *pnRecyclable = nRecyclable;
}
#endif

**    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.26 2008/09/02 09:38:07 danielk1977 Exp $
*/
#include "sqliteInt.h"

/*
** A complete page cache is an instance of this structure.
**
** A cache may only be deleted by its owner and while holding the
................................................................................
struct PgFreeslot {
  PgFreeslot *pNext;  /* Next free slot */
};

/*
** Global data for the page cache.
*/
static SQLITE_WSD struct PCacheGlobal {
  int isInit;                         /* True when initialized */
  sqlite3_mutex *mutex;               /* static mutex MUTEX_STATIC_LRU */

  int nMaxPage;                       /* Sum of nMaxPage for purgeable caches */
  int nMinPage;                       /* Sum of nMinPage for purgeable caches */
  int nCurrentPage;                   /* Number of purgeable pages allocated */
  PgHdr *pLruHead, *pLruTail;         /* LRU list of unused clean pgs */
................................................................................

  /* Variables related to SQLITE_CONFIG_PAGECACHE settings. */
  int szSlot;                         /* Size of each free slot */
  void *pStart, *pEnd;                /* Bounds of pagecache malloc range */
  PgFreeslot *pFree;                  /* Free page blocks */
} pcache = {0};

/*
** All code in this file should access the global pcache structure via the
** alias "pcache_g". This ensures that the WSD emulation is used when
** compiling for systems that do not support real WSD.
*/
#define pcache_g (GLOBAL(struct PCacheGlobal, pcache))

/*
** All global variables used by this module (all of which are grouped 
** together in global structure "pcache" above) are protected by the static 
** SQLITE_MUTEX_STATIC_LRU mutex. A pointer to this mutex is stored in
** variable "pcache.mutex".
**
** Some elements of the PCache and PgHdr structures are protected by the 
................................................................................
** marked.
**
** Use the following macros must surround all access (read or write)
** of protected elements.  The mutex is not recursive and may not be
** entered more than once.  The pcacheMutexHeld() macro should only be
** used within an assert() to verify that the mutex is being held.
*/
#define pcacheEnterMutex() sqlite3_mutex_enter(pcache_g.mutex)
#define pcacheExitMutex()  sqlite3_mutex_leave(pcache_g.mutex)
#define pcacheMutexHeld()  sqlite3_mutex_held(pcache_g.mutex)

/*
** Some of the assert() macros in this code are too expensive to run
** even during normal debugging.  Use them only rarely on long-running
** tests.  Enable the expensive asserts using the
** -DSQLITE_ENABLE_EXPENSIVE_ASSERT=1 compile-time option.
*/
................................................................................
  }
}

/*
** Remove a page from the global LRU list
*/
static void pcacheRemoveFromLruList(PgHdr *pPage){
  assert( sqlite3_mutex_held(pcache_g.mutex) );
  assert( (pPage->flags&PGHDR_DIRTY)==0 );
  if( pPage->pCache->bPurgeable==0 ) return;
  if( pPage->pNextLru ){
    assert( pcache_g.pLruTail!=pPage );
    pPage->pNextLru->pPrevLru = pPage->pPrevLru;
  }else{
    assert( pcache_g.pLruTail==pPage );
    pcache_g.pLruTail = pPage->pPrevLru;
  }
  if( pPage->pPrevLru ){
    assert( pcache_g.pLruHead!=pPage );
    pPage->pPrevLru->pNextLru = pPage->pNextLru;
  }else{
    assert( pcache_g.pLruHead==pPage );
    pcache_g.pLruHead = pPage->pNextLru;
  }
}

/*
** Add a page to the global LRU list.  The page is normally added
** to the front of the list so that it will be the last page recycled.
** However, if the PGHDR_REUSE_UNLIKELY bit is set, the page is added
** to the end of the LRU list so that it will be the next to be recycled.
*/
static void pcacheAddToLruList(PgHdr *pPage){
  assert( sqlite3_mutex_held(pcache_g.mutex) );
  assert( (pPage->flags&PGHDR_DIRTY)==0 );
  if( pPage->pCache->bPurgeable==0 ) return;
  if( pcache_g.pLruTail && (pPage->flags & PGHDR_REUSE_UNLIKELY)!=0 ){
    /* If reuse is unlikely.  Put the page at the end of the LRU list
    ** where it will be recycled sooner rather than later. 
    */
    assert( pcache_g.pLruHead );
    pPage->pNextLru = 0;
    pPage->pPrevLru = pcache_g.pLruTail;
    pcache_g.pLruTail->pNextLru = pPage;
    pcache_g.pLruTail = pPage;
    pPage->flags &= ~PGHDR_REUSE_UNLIKELY;
  }else{
    /* If reuse is possible. the page goes at the beginning of the LRU
    ** list so that it will be the last to be recycled.
    */
    if( pcache_g.pLruHead ){
      pcache_g.pLruHead->pPrevLru = pPage;
    }
    pPage->pNextLru = pcache_g.pLruHead;
    pcache_g.pLruHead = pPage;
    pPage->pPrevLru = 0;
    if( pcache_g.pLruTail==0 ){
      pcache_g.pLruTail = pPage;
    }
  }
}

/*********************************************** Memory Allocation ***********
**
** Initialize the page cache memory pool.
................................................................................
**
** This must be called at start-time when no page cache lines are
** checked out. This function is not threadsafe.
*/
void sqlite3PCacheBufferSetup(void *pBuf, int sz, int n){
  PgFreeslot *p;
  sz &= ~7;
  pcache_g.szSlot = sz;
  pcache_g.pStart = pBuf;
  pcache_g.pFree = 0;
  while( n-- ){
    p = (PgFreeslot*)pBuf;
    p->pNext = pcache_g.pFree;
    pcache_g.pFree = p;
    pBuf = (void*)&((char*)pBuf)[sz];
  }
  pcache_g.pEnd = pBuf;
}

/*
** Allocate a page cache line.  Look in the page cache memory pool first
** and use an element from it first if available.  If nothing is available
** in the page cache memory pool, go to the general purpose memory allocator.
*/
void *pcacheMalloc(int sz, PCache *pCache){
  assert( sqlite3_mutex_held(pcache_g.mutex) );
  if( sz<=pcache_g.szSlot && pcache_g.pFree ){
    PgFreeslot *p = pcache_g.pFree;
    pcache_g.pFree = p->pNext;
    sqlite3StatusSet(SQLITE_STATUS_PAGECACHE_SIZE, sz);
    sqlite3StatusAdd(SQLITE_STATUS_PAGECACHE_USED, 1);
    return (void*)p;
  }else{
    void *p;

    /* Allocate a new buffer using sqlite3Malloc. Before doing so, exit the
................................................................................
  return p;
}

/*
** Release a pager memory allocation
*/
void pcacheFree(void *p){
  assert( sqlite3_mutex_held(pcache_g.mutex) );
  if( p==0 ) return;
  if( p>=pcache_g.pStart && p<pcache_g.pEnd ){
    PgFreeslot *pSlot;
    sqlite3StatusAdd(SQLITE_STATUS_PAGECACHE_USED, -1);
    pSlot = (PgFreeslot*)p;
    pSlot->pNext = pcache_g.pFree;
    pcache_g.pFree = pSlot;
  }else{
    int iSize = sqlite3MallocSize(p);
    sqlite3StatusAdd(SQLITE_STATUS_PAGECACHE_OVERFLOW, -iSize);
    sqlite3_free(p);
  }
}
void sqlite3PageFree(void *p){
................................................................................

/*
** Allocate a new page.
*/
static PgHdr *pcachePageAlloc(PCache *pCache){
  PgHdr *p;
  int sz = sizeof(*p) + pCache->szPage + pCache->szExtra;
  assert( sqlite3_mutex_held(pcache_g.mutex) );
  p = pcacheMalloc(sz, pCache);
  if( p==0 ) return 0;
  memset(p, 0, sizeof(PgHdr));
  p->pData = (void*)&p[1];
  p->pExtra = (void*)&((char*)p->pData)[pCache->szPage];
  if( pCache->bPurgeable ){
    pcache_g.nCurrentPage++;
  }
  return p;
}

/*
** Deallocate a page
*/
static void pcachePageFree(PgHdr *p){
  assert( sqlite3_mutex_held(pcache_g.mutex) );
  if( p->pCache->bPurgeable ){
    pcache_g.nCurrentPage--;
  }
  pcacheFree(p->apSave[0]);
  pcacheFree(p->apSave[1]);
  pcacheFree(p);
}

#ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
/*
** Return the number of bytes that will be returned to the heap when
** the argument is passed to pcachePageFree().
*/
static int pcachePageSize(PgHdr *p){
  assert( sqlite3_mutex_held(pcache_g.mutex) );
  assert( !pcache_g.pStart );
  assert( p->apSave[0]==0 );
  assert( p->apSave[1]==0 );
  assert( p && p->pCache );
  return sqlite3MallocSize(p);
}
#endif

................................................................................
** There should be no other references to the page.
**
** A pointer to the recycled page is returned, or NULL if no page is
** eligible for recycling.
*/
static PgHdr *pcacheRecyclePage(){
  PgHdr *p = 0;
  assert( sqlite3_mutex_held(pcache_g.mutex) );

  if( (p=pcache_g.pLruTail) ){
    assert( (p->flags&PGHDR_DIRTY)==0 );
    pcacheRemoveFromLruList(p);
    pcacheRemoveFromHash(p);
    pcacheRemoveFromList(&p->pCache->pClean, p);
  }

  return p;
................................................................................
*/
static int pcacheRecycleOrAlloc(PCache *pCache, PgHdr **ppPage){
  PgHdr *p = 0;

  int szPage = pCache->szPage;
  int szExtra = pCache->szExtra;

  assert( pcache_g.isInit );
  assert( sqlite3_mutex_held(pcache_g.mutex) );

  *ppPage = 0;

  /* If we have reached the limit for pinned/dirty pages, and there is at
  ** least one dirty page, invoke the xStress callback to cause a page to
  ** become clean.
  */
  expensive_assert( pCache->nPinned==pcachePinnedCount(pCache) );
  expensive_assert( pcacheCheckSynced(pCache) );
  if( pCache->xStress
   && pCache->pDirty
   && pCache->nPinned>=(pcache_g.nMaxPage+pCache->nMin-pcache_g.nMinPage)
  ){
    PgHdr *pPg;
    assert(pCache->pDirtyTail);

    for(pPg=pCache->pSynced; 
        pPg && (pPg->nRef || (pPg->flags&PGHDR_NEED_SYNC)); 
        pPg=pPg->pPrev
................................................................................
      if( rc!=SQLITE_OK && rc!=SQLITE_BUSY ){
        return rc;
      }
    }
  }

  /* If the global page limit has been reached, try to recycle a page. */
  if( pCache->bPurgeable && pcache_g.nCurrentPage>=pcache_g.nMaxPage ){
    p = pcacheRecyclePage();
  }

  /* If a page has been recycled but it is the wrong size, free it. */
  if( p && (p->pCache->szPage!=szPage || p->pCache->szPage!=szExtra) ){
    pcachePageFree(p);
    p = 0;
................................................................................

/*************************************************** General Interfaces ******
**
** Initialize and shutdown the page cache subsystem. Neither of these 
** functions are threadsafe.
*/
int sqlite3PcacheInitialize(void){
  assert( pcache_g.isInit==0 );
  memset(&pcache_g, 0, sizeof(pcache));
  if( sqlite3GlobalConfig.bCoreMutex ){
    /* No need to check the return value of sqlite3_mutex_alloc(). 
    ** Allocating a static mutex cannot fail.
    */
    pcache_g.mutex = sqlite3_mutex_alloc(SQLITE_MUTEX_STATIC_LRU);
  }
  pcache_g.isInit = 1;
  return SQLITE_OK;
}
void sqlite3PcacheShutdown(void){
  memset(&pcache_g, 0, sizeof(pcache));
}

/*
** Return the size in bytes of a PCache object.
*/
int sqlite3PcacheSize(void){ return sizeof(PCache); }

................................................................................
  int szExtra,                 /* Extra space associated with each page */
  int bPurgeable,              /* True if pages are on backing store */
  void (*xDestroy)(PgHdr*),    /* Called to destroy a page */
  int (*xStress)(void*,PgHdr*),/* Call to try to make pages clean */
  void *pStress,               /* Argument to xStress */
  PCache *p                    /* Preallocated space for the PCache */
){
  assert( pcache_g.isInit );
  memset(p, 0, sizeof(PCache));
  p->szPage = szPage;
  p->szExtra = szExtra;
  p->bPurgeable = bPurgeable;
  p->xDestroy = xDestroy;
  p->xStress = xStress;
  p->pStress = pStress;
  p->nMax = 100;
  p->nMin = 10;

  pcacheEnterMutex();
  if( bPurgeable ){
    pcache_g.nMaxPage += p->nMax;
    pcache_g.nMinPage += p->nMin;
  }

  pcacheExitMutex();
}

/*
** Change the page size for PCache object.  This can only happen
................................................................................
  Pgno pgno,            /* Page number to obtain */
  int createFlag,       /* If true, create page if it does not exist already */
  PgHdr **ppPage        /* Write the page here */
){
  int rc = SQLITE_OK;
  PgHdr *pPage = 0;

  assert( pcache_g.isInit );
  assert( pCache!=0 );
  assert( pgno>0 );
  expensive_assert( pCache->nPinned==pcachePinnedCount(pCache) );

  pcacheEnterMutex();

  /* Search the hash table for the requested page. Exit early if it is found. */
................................................................................
    if( p->pCache->xDestroy ){
      p->pCache->xDestroy(p);
    }
    pCache->nRef--;
    if( (p->flags&PGHDR_DIRTY)==0 ){
      pCache->nPinned--;
      pcacheEnterMutex();
      if( pcache_g.nCurrentPage>pcache_g.nMaxPage ){
        pcacheRemoveFromList(&pCache->pClean, p);
        pcacheRemoveFromHash(p);
        pcachePageFree(p);
      }else{
        pcacheAddToLruList(p);
      }
      pcacheExitMutex();
................................................................................
}

/*
** Remove all content from a page cache
*/
void pcacheClear(PCache *pCache){
  PgHdr *p, *pNext;
  assert( sqlite3_mutex_held(pcache_g.mutex) );
  for(p=pCache->pClean; p; p=pNext){
    pNext = p->pNext;
    pcacheRemoveFromLruList(p);
    pcachePageFree(p);
  }
  for(p=pCache->pDirty; p; p=pNext){
    pNext = p->pNext;
................................................................................

/*
** If there are currently more than pcache.nMaxPage pages allocated, try
** to recycle pages to reduce the number allocated to pcache.nMaxPage.
*/
static void pcacheEnforceMaxPage(){
  PgHdr *p;
  assert( sqlite3_mutex_held(pcache_g.mutex) );
  while( pcache_g.nCurrentPage>pcache_g.nMaxPage && (p = pcacheRecyclePage()) ){
    pcachePageFree(p);
  }
}

/*
** Close a cache.
*/
void sqlite3PcacheClose(PCache *pCache){
  pcacheEnterMutex();

  /* Free all the pages used by this pager and remove them from the LRU list. */
  pcacheClear(pCache);
  if( pCache->bPurgeable ){
    pcache_g.nMaxPage -= pCache->nMax;
    pcache_g.nMinPage -= pCache->nMin;
    pcacheEnforceMaxPage();
  }
  sqlite3_free(pCache->apHash);
  pcacheExitMutex();
}

/*
................................................................................
*/
void sqlite3PcacheSetCachesize(PCache *pCache, int mxPage){
  if( mxPage<10 ){
    mxPage = 10;
  }
  if( pCache->bPurgeable ){
    pcacheEnterMutex();
    pcache_g.nMaxPage -= pCache->nMax;
    pcache_g.nMaxPage += mxPage;
    pcacheEnforceMaxPage();
    pcacheExitMutex();
  }
  pCache->nMax = mxPage;
}

#ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
................................................................................
**
** nReq is the number of bytes of memory required. Once this much has
** been released, the function returns. The return value is the total number 
** of bytes of memory released.
*/
int sqlite3PcacheReleaseMemory(int nReq){
  int nFree = 0;
  if( pcache_g.pStart==0 ){
    PgHdr *p;
    pcacheEnterMutex();
    while( (nReq<0 || nFree<nReq) && (p=pcacheRecyclePage()) ){
      nFree += pcachePageSize(p);
      pcachePageFree(p);
    }
    pcacheExitMutex();
................................................................................
  int *pnCurrent,
  int *pnMax,
  int *pnMin,
  int *pnRecyclable
){
  PgHdr *p;
  int nRecyclable = 0;
  for(p=pcache_g.pLruHead; p; p=p->pNextLru){
    nRecyclable++;
  }

  *pnCurrent = pcache_g.nCurrentPage;
  *pnMax = pcache_g.nMaxPage;
  *pnMin = pcache_g.nMinPage;
  *pnRecyclable = nRecyclable;
}
#endif