SQLite

**
** 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.2 2008/11/15 11:22:45 danielk1977 Exp $
*/

#include "sqliteInt.h"

typedef struct PCache1 PCache1;
typedef struct PgHdr1 PgHdr1;
typedef struct PgFreeslot PgFreeslot;

/* Pointers to structures of this type are cast and returned as 
** opaque sqlite3_pcache* handles
*/
struct PCache1 {
  /* Cache configuration parameters. Page size (szPage) and the purgeable
  ** flag (bPurgeable) are set when the cache is created. nMax may be 
  ** modified at any time by a call to the pcache1CacheSize() method.
  ** The global mutex must be held when accessing nMax.
  */
  int szPage;                         /* Size of allocated pages in bytes */
  int bPurgeable;                     /* True if cache is purgeable */
  unsigned int nMin;                  /* Minimum number of pages reserved */
  unsigned int nMax;                  /* Configured "cache_size" value */

  /* Hash table of all pages. The following variables may only be accessed
  ** when the accessor is holding the global mutex (see pcache1EnterMutex() 
  ** and pcache1LeaveMutex()).
  */
  unsigned int nRecyclable;           /* Number of pages in the LRU list */
  unsigned int nPage;                 /* Total number of pages in apHash */
  unsigned int nHash;                 /* Number of slots in apHash[] */
  PgHdr1 **apHash;                    /* Hash table for fast lookup by key */
};

/*
** Each cache entry is represented by an instance of the following 
** structure. A buffer of PgHdr1.pCache->szPage bytes is allocated 
** directly after the structure in memory (see the PGHDR1_TO_PAGE() 

  int nCurrentPage;                   /* Number of purgeable pages allocated */
  PgHdr1 *pLruHead, *pLruTail;        /* LRU list of unpinned pages */

  /* 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 */
} pcache1_g;

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

** This function is used to resize the hash table used by the cache passed
** as the first argument.
**
** The global mutex must be held when this function is called.
*/
static int pcache1ResizeHash(PCache1 *p){
  PgHdr1 **apNew;
  unsigned int nNew;
  unsigned int i;

  assert( sqlite3_mutex_held(pcache1.mutex) );

  nNew = p->nHash*2;
  if( nNew<256 ){
    nNew = 256;

**      then attempt to recycle a page from the LRU list. If it is the right
**      size, return the recycled buffer. Otherwise, free the buffer and
**      proceed to step 5. 
**
**   5. Otherwise, allocate and return a new page buffer.
*/
static void *pcache1Fetch(sqlite3_pcache *p, unsigned int iKey, int createFlag){
  unsigned int nPinned;
  PCache1 *pCache = (PCache1 *)p;
  PgHdr1 *pPage = 0;

  pcache1EnterMutex();
  if( createFlag==1 ) sqlite3BeginBenignMalloc();

  /* Search the hash table for an existing entry. */