** The pager is used to access a database disk file.  It implements
** atomic commit and rollback through the use of a journal file that
** is separate from the database file.  The pager also implements file
** locking to prevent two processes from writing the same database
** file simultaneously, or one process from reading the database while
** another is writing.
**
** @(#) $Id: pager.c,v 1.267 2006/05/03 23:34:06 drh Exp $
*/
#ifndef SQLITE_OMIT_DISKIO
#include "sqliteInt.h"
#include "os.h"
#include "pager.h"
#include <assert.h>
#include <string.h>
................................................................................
*/
#define PGHDR_TO_DATA(P)  ((void*)(&(P)[1]))
#define DATA_TO_PGHDR(D)  (&((PgHdr*)(D))[-1])
#define PGHDR_TO_EXTRA(G,P) ((void*)&((char*)(&(G)[1]))[(P)->pageSize])
#define PGHDR_TO_HIST(P,PGR)  \
            ((PgHistory*)&((char*)(&(P)[1]))[(PGR)->pageSize+(PGR)->nExtra])

/*
** How big to make the hash table used for locating in-memory pages
** by page number. This macro looks a little silly, but is evaluated
** at compile-time, not run-time (at least for gcc this is true).
*/
#define N_PG_HASH (\
  (MAX_PAGES>1024)?2048: \
  (MAX_PAGES>512)?1024: \
  (MAX_PAGES>256)?512: \
  (MAX_PAGES>128)?256: \
  (MAX_PAGES>64)?128:64 \
)

/*
** Hash a page number
*/
#define pager_hash(PN)  ((PN)&(N_PG_HASH-1))

/*
** A open page cache is an instance of the following structure.
**
** Pager.errCode may be set to SQLITE_IOERR, SQLITE_CORRUPT, SQLITE_PROTOCOL
** or SQLITE_FULL. Once one of the first three errors occurs, it persists
** and is returned as the result of every major pager API call.  The
** SQLITE_FULL return code is slightly different. It persists only until the
................................................................................
  int nHit, nMiss, nOvfl;     /* Cache hits, missing, and LRU overflows */
  int nRead,nWrite;           /* Database pages read/written */
#endif
  void (*xDestructor)(void*,int); /* Call this routine when freeing pages */
  void (*xReiniter)(void*,int);   /* Call this routine when reloading pages */
  void *(*xCodec)(void*,void*,Pgno,int); /* Routine for en/decoding data */
  void *pCodecArg;            /* First argument to xCodec() */

  PgHdr *aHash[N_PG_HASH];    /* Hash table to map page number to PgHdr */
#ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
  Pager *pNext;               /* Linked list of pagers in this thread */
#endif
};

/*
** If SQLITE_TEST is defined then increment the variable given in
................................................................................
    cnt++;   /* Something to set a breakpoint on */
  }
# define REFINFO(X)  pager_refinfo(X)
#else
# define REFINFO(X)
#endif




























/*
** Read a 32-bit integer from the given file descriptor.  Store the integer
** that is read in *pRes.  Return SQLITE_OK if everything worked, or an
** error code is something goes wrong.
**
** All values are stored on disk as big-endian.
*/
................................................................................
}

/*
** Find a page in the hash table given its page number.  Return
** a pointer to the page or NULL if not found.
*/
static PgHdr *pager_lookup(Pager *pPager, Pgno pgno){


  PgHdr *p = pPager->aHash[pager_hash(pgno)];
  while( p && p->pgno!=pgno ){
    p = p->pNextHash;
  }
  return p;
}

/*
................................................................................
    pNext = pPg->pNextAll;
    sqliteFree(pPg);
  }
  pPager->pFirst = 0;
  pPager->pFirstSynced = 0;
  pPager->pLast = 0;
  pPager->pAll = 0;

  memset(pPager->aHash, 0, sizeof(pPager->aHash));
  pPager->nPage = 0;

  if( pPager->state>=PAGER_RESERVED ){
    sqlite3pager_rollback(pPager);
  }
  sqlite3OsUnlock(pPager->fd, NO_LOCK);
  pPager->state = PAGER_UNLOCK;
  pPager->dbSize = -1;
  pPager->nRef = 0;
................................................................................
    /* If the page number is zero, then this page is not in any hash chain. */
    return;
  }
  if( pPg->pNextHash ){
    pPg->pNextHash->pPrevHash = pPg->pPrevHash;
  }
  if( pPg->pPrevHash ){
    assert( pPager->aHash[pager_hash(pPg->pgno)]!=pPg );
    pPg->pPrevHash->pNextHash = pPg->pNextHash;
  }else{
    int h = pager_hash(pPg->pgno);
    assert( pPager->aHash[h]==pPg );
    pPager->aHash[h] = pPg->pNextHash;
  }
  if( MEMDB ){
    clearHistory(PGHDR_TO_HIST(pPg, pPager));
  }
  pPg->pgno = 0;
................................................................................
    pTsd->pPager = pPager->pNext;
  }else{
    Pager *pTmp;
    for(pTmp = pTsd->pPager; pTmp->pNext!=pPager; pTmp=pTmp->pNext){}
    pTmp->pNext = pPager->pNext;
  }
#endif

  sqliteFree(pPager);
  return SQLITE_OK;
}

/*
** Return the page number for the given page data.
*/
................................................................................
  }
  if( pPg==0 ){
    /* The requested page is not in the page cache. */
    int h;
    TEST_INCR(pPager->nMiss);
    if( pPager->nPage<pPager->mxPage || pPager->pFirst==0 || MEMDB ){
      /* Create a new page */







      pPg = sqliteMallocRaw( sizeof(*pPg) + pPager->pageSize
                              + sizeof(u32) + pPager->nExtra
                              + MEMDB*sizeof(PgHistory) );
      if( pPg==0 ){
        return SQLITE_NOMEM;
      }
      memset(pPg, 0, sizeof(*pPg));
................................................................................
        }
      }else{
        TEST_INCR(pPager->nRead);
      }
    }

    /* Link the page into the page hash table */
    h = pager_hash(pgno);
    pPg->pNextHash = pPager->aHash[h];
    pPager->aHash[h] = pPg;
    if( pPg->pNextHash ){
      assert( pPg->pNextHash->pPrevHash==0 );
      pPg->pNextHash->pPrevHash = pPg;
    }

................................................................................
      pPg->needSync = 1;
      assert( pPager->needSync );
    }
  }

  /* Change the page number for pPg and insert it into the new hash-chain. */
  pPg->pgno = pgno;
  h = pager_hash(pgno);
  if( pPager->aHash[h] ){
    assert( pPager->aHash[h]->pPrevHash==0 );
    pPager->aHash[h]->pPrevHash = pPg;
  }
  pPg->pNextHash = pPager->aHash[h];
  pPager->aHash[h] = pPg;
  pPg->pPrevHash = 0;

** The pager is used to access a database disk file.  It implements
** atomic commit and rollback through the use of a journal file that
** is separate from the database file.  The pager also implements file
** locking to prevent two processes from writing the same database
** file simultaneously, or one process from reading the database while
** another is writing.
**
** @(#) $Id: pager.c,v 1.268 2006/05/07 17:49:39 drh Exp $
*/
#ifndef SQLITE_OMIT_DISKIO
#include "sqliteInt.h"
#include "os.h"
#include "pager.h"
#include <assert.h>
#include <string.h>
................................................................................
*/
#define PGHDR_TO_DATA(P)  ((void*)(&(P)[1]))
#define DATA_TO_PGHDR(D)  (&((PgHdr*)(D))[-1])
#define PGHDR_TO_EXTRA(G,P) ((void*)&((char*)(&(G)[1]))[(P)->pageSize])
#define PGHDR_TO_HIST(P,PGR)  \
            ((PgHistory*)&((char*)(&(P)[1]))[(PGR)->pageSize+(PGR)->nExtra])



















/*
** A open page cache is an instance of the following structure.
**
** Pager.errCode may be set to SQLITE_IOERR, SQLITE_CORRUPT, SQLITE_PROTOCOL
** or SQLITE_FULL. Once one of the first three errors occurs, it persists
** and is returned as the result of every major pager API call.  The
** SQLITE_FULL return code is slightly different. It persists only until the
................................................................................
  int nHit, nMiss, nOvfl;     /* Cache hits, missing, and LRU overflows */
  int nRead,nWrite;           /* Database pages read/written */
#endif
  void (*xDestructor)(void*,int); /* Call this routine when freeing pages */
  void (*xReiniter)(void*,int);   /* Call this routine when reloading pages */
  void *(*xCodec)(void*,void*,Pgno,int); /* Routine for en/decoding data */
  void *pCodecArg;            /* First argument to xCodec() */
  int nHash;                  /* Size of the pager hash table */
  PgHdr **aHash;              /* Hash table to map page number to PgHdr */
#ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
  Pager *pNext;               /* Linked list of pagers in this thread */
#endif
};

/*
** If SQLITE_TEST is defined then increment the variable given in
................................................................................
    cnt++;   /* Something to set a breakpoint on */
  }
# define REFINFO(X)  pager_refinfo(X)
#else
# define REFINFO(X)
#endif


/*
** Change the size of the pager hash table to N.  N must be a power
** of two.
*/
static void pager_resize_hash_table(Pager *pPager, int N){
  PgHdr **aHash, *pPg;
  assert( N>0 && (N&(N-1))==0 );
  aHash = sqliteMalloc( sizeof(aHash[0])*N );
  if( aHash==0 ){
    /* Failure to rehash is not an error.  It is only a performance hit. */
    return;
  }
  sqliteFree(pPager->aHash);
  pPager->nHash = N;
  pPager->aHash = aHash;
  for(pPg=pPager->pAll; pPg; pPg=pPg->pNextAll){
    int h = pPg->pgno & (N-1);
    pPg->pNextHash = aHash[h];
    if( aHash[h] ){
      aHash[h]->pPrevHash = pPg;
    }
    aHash[h] = pPg;
    pPg->pPrevHash = 0;
  }
}

/*
** Read a 32-bit integer from the given file descriptor.  Store the integer
** that is read in *pRes.  Return SQLITE_OK if everything worked, or an
** error code is something goes wrong.
**
** All values are stored on disk as big-endian.
*/
................................................................................
}

/*
** Find a page in the hash table given its page number.  Return
** a pointer to the page or NULL if not found.
*/
static PgHdr *pager_lookup(Pager *pPager, Pgno pgno){
  PgHdr *p;
  if( pPager->aHash==0 ) return 0;
  p = pPager->aHash[pgno & (pPager->nHash-1)];
  while( p && p->pgno!=pgno ){
    p = p->pNextHash;
  }
  return p;
}

/*
................................................................................
    pNext = pPg->pNextAll;
    sqliteFree(pPg);
  }
  pPager->pFirst = 0;
  pPager->pFirstSynced = 0;
  pPager->pLast = 0;
  pPager->pAll = 0;
  pPager->nHash = 0;
  sqliteFree(pPager->aHash);
  pPager->nPage = 0;
  pPager->aHash = 0;
  if( pPager->state>=PAGER_RESERVED ){
    sqlite3pager_rollback(pPager);
  }
  sqlite3OsUnlock(pPager->fd, NO_LOCK);
  pPager->state = PAGER_UNLOCK;
  pPager->dbSize = -1;
  pPager->nRef = 0;
................................................................................
    /* If the page number is zero, then this page is not in any hash chain. */
    return;
  }
  if( pPg->pNextHash ){
    pPg->pNextHash->pPrevHash = pPg->pPrevHash;
  }
  if( pPg->pPrevHash ){
    assert( pPager->aHash[pPg->pgno & (pPager->nHash-1)]!=pPg );
    pPg->pPrevHash->pNextHash = pPg->pNextHash;
  }else{
    int h = pPg->pgno & (pPager->nHash-1);
    assert( pPager->aHash[h]==pPg );
    pPager->aHash[h] = pPg->pNextHash;
  }
  if( MEMDB ){
    clearHistory(PGHDR_TO_HIST(pPg, pPager));
  }
  pPg->pgno = 0;
................................................................................
    pTsd->pPager = pPager->pNext;
  }else{
    Pager *pTmp;
    for(pTmp = pTsd->pPager; pTmp->pNext!=pPager; pTmp=pTmp->pNext){}
    pTmp->pNext = pPager->pNext;
  }
#endif
  sqliteFree(pPager->aHash);
  sqliteFree(pPager);
  return SQLITE_OK;
}

/*
** Return the page number for the given page data.
*/
................................................................................
  }
  if( pPg==0 ){
    /* The requested page is not in the page cache. */
    int h;
    TEST_INCR(pPager->nMiss);
    if( pPager->nPage<pPager->mxPage || pPager->pFirst==0 || MEMDB ){
      /* Create a new page */
      if( pPager->nPage>=pPager->nHash ){
        pager_resize_hash_table(pPager,
           pPager->nHash<256 ? 256 : pPager->nHash*2);
        if( pPager->nHash==0 ){
          return SQLITE_NOMEM;
        }
      }
      pPg = sqliteMallocRaw( sizeof(*pPg) + pPager->pageSize
                              + sizeof(u32) + pPager->nExtra
                              + MEMDB*sizeof(PgHistory) );
      if( pPg==0 ){
        return SQLITE_NOMEM;
      }
      memset(pPg, 0, sizeof(*pPg));
................................................................................
        }
      }else{
        TEST_INCR(pPager->nRead);
      }
    }

    /* Link the page into the page hash table */
    h = pgno & (pPager->nHash-1);
    pPg->pNextHash = pPager->aHash[h];
    pPager->aHash[h] = pPg;
    if( pPg->pNextHash ){
      assert( pPg->pNextHash->pPrevHash==0 );
      pPg->pNextHash->pPrevHash = pPg;
    }

................................................................................
      pPg->needSync = 1;
      assert( pPager->needSync );
    }
  }

  /* Change the page number for pPg and insert it into the new hash-chain. */
  pPg->pgno = pgno;
  h = pgno & (pPager->nHash-1);
  if( pPager->aHash[h] ){
    assert( pPager->aHash[h]->pPrevHash==0 );
    pPager->aHash[h]->pPrevHash = pPg;
  }
  pPg->pNextHash = pPager->aHash[h];
  pPager->aHash[h] = pPg;
  pPg->pPrevHash = 0;