}
void sqlite3OsShmBarrier(sqlite3_file *id){
  id->pMethods->xShmBarrier(id);
}
int sqlite3OsShmClose(sqlite3_file *id, int deleteFlag){
  return id->pMethods->xShmClose(id, deleteFlag);
}










/*
** The next group of routines are convenience wrappers around the
** VFS methods.
*/
int sqlite3OsOpen(
  sqlite3_vfs *pVfs, 

}
void sqlite3OsShmBarrier(sqlite3_file *id){
  id->pMethods->xShmBarrier(id);
}
int sqlite3OsShmClose(sqlite3_file *id, int deleteFlag){
  return id->pMethods->xShmClose(id, deleteFlag);
}
int sqlite3OsShmPage(
  sqlite3_file *id, 
  int iPage, 
  int pgsz, 
  int isWrite, 
  void volatile **pp
){
  return id->pMethods->xShmPage(id, iPage, pgsz, isWrite, pp);
}

/*
** The next group of routines are convenience wrappers around the
** VFS methods.
*/
int sqlite3OsOpen(
  sqlite3_vfs *pVfs, 

int sqlite3OsShmOpen(sqlite3_file *id);
int sqlite3OsShmSize(sqlite3_file *id, int, int*);
int sqlite3OsShmGet(sqlite3_file *id, int, int*, void volatile**);
int sqlite3OsShmRelease(sqlite3_file *id);
int sqlite3OsShmLock(sqlite3_file *id, int, int, int);
void sqlite3OsShmBarrier(sqlite3_file *id);
int sqlite3OsShmClose(sqlite3_file *id, int);


/* 
** Functions for accessing sqlite3_vfs methods 
*/
int sqlite3OsOpen(sqlite3_vfs *, const char *, sqlite3_file*, int, int *);
int sqlite3OsDelete(sqlite3_vfs *, const char *, int);
int sqlite3OsAccess(sqlite3_vfs *, const char *, int, int *pResOut);

int sqlite3OsShmOpen(sqlite3_file *id);
int sqlite3OsShmSize(sqlite3_file *id, int, int*);
int sqlite3OsShmGet(sqlite3_file *id, int, int*, void volatile**);
int sqlite3OsShmRelease(sqlite3_file *id);
int sqlite3OsShmLock(sqlite3_file *id, int, int, int);
void sqlite3OsShmBarrier(sqlite3_file *id);
int sqlite3OsShmClose(sqlite3_file *id, int);
int sqlite3OsShmPage(sqlite3_file *,int,int,int,void volatile **);

/* 
** Functions for accessing sqlite3_vfs methods 
*/
int sqlite3OsOpen(sqlite3_vfs *, const char *, sqlite3_file*, int, int *);
int sqlite3OsDelete(sqlite3_vfs *, const char *, int);
int sqlite3OsAccess(sqlite3_vfs *, const char *, int, int *pResOut);

*/
struct unixShmNode {
  unixInodeInfo *pInode;     /* unixInodeInfo that owns this SHM node */
  sqlite3_mutex *mutex;      /* Mutex to access this object */
  sqlite3_mutex *mutexBuf;   /* Mutex to access zBuf[] */
  char *zFilename;           /* Name of the mmapped file */
  int h;                     /* Open file descriptor */

  int szMap;                 /* Size of the mapping into memory */
  char *pMMapBuf;            /* Where currently mmapped().  NULL if unmapped */





  int nRef;                  /* Number of unixShm objects pointing to this */
  unixShm *pFirst;           /* All unixShm objects pointing to this */
#ifdef SQLITE_DEBUG
  u8 exclMask;               /* Mask of exclusive locks held */
  u8 sharedMask;             /* Mask of shared locks held */
  u8 nextShmId;              /* Next available unixShm.id value */
#endif
................................................................................
** This is not a VFS shared-memory method; it is a utility function called
** by VFS shared-memory methods.
*/
static void unixShmPurge(unixFile *pFd){
  unixShmNode *p = pFd->pInode->pShmNode;
  assert( unixMutexHeld() );
  if( p && p->nRef==0 ){

    assert( p->pInode==pFd->pInode );
    if( p->mutex ) sqlite3_mutex_free(p->mutex);
    if( p->mutexBuf ) sqlite3_mutex_free(p->mutexBuf);
    if( p->pMMapBuf ) munmap(p->pMMapBuf, p->szMap);




    if( p->h>=0 ) close(p->h);
    p->pInode->pShmNode = 0;
    sqlite3_free(p);
  }
}

/* Forward reference */
................................................................................
static void unixShmBarrier(
  sqlite3_file *fd           /* Database file holding the shared memory */
){
  unixEnterMutex();
  unixLeaveMutex();
}



































































#else
# define unixShmOpen    0
# define unixShmSize    0
# define unixShmGet     0
# define unixShmRelease 0
# define unixShmLock    0
# define unixShmBarrier 0
# define unixShmClose   0

#endif /* #ifndef SQLITE_OMIT_WAL */

/*
** Here ends the implementation of all sqlite3_file methods.
**
********************** End sqlite3_file Methods *******************************
******************************************************************************/
................................................................................
   unixDeviceCharacteristics,  /* xDeviceCapabilities */                     \
   unixShmOpen,                /* xShmOpen */                                \
   unixShmSize,                /* xShmSize */                                \
   unixShmGet,                 /* xShmGet */                                 \
   unixShmRelease,             /* xShmRelease */                             \
   unixShmLock,                /* xShmLock */                                \
   unixShmBarrier,             /* xShmBarrier */                             \
   unixShmClose                /* xShmClose */                               \

};                                                                           \
static const sqlite3_io_methods *FINDER##Impl(const char *z, unixFile *p){   \
  UNUSED_PARAMETER(z); UNUSED_PARAMETER(p);                                  \
  return &METHOD;                                                            \
}                                                                            \
static const sqlite3_io_methods *(*const FINDER)(const char*,unixFile *p)    \
    = FINDER##Impl;

*/
struct unixShmNode {
  unixInodeInfo *pInode;     /* unixInodeInfo that owns this SHM node */
  sqlite3_mutex *mutex;      /* Mutex to access this object */
  sqlite3_mutex *mutexBuf;   /* Mutex to access zBuf[] */
  char *zFilename;           /* Name of the mmapped file */
  int h;                     /* Open file descriptor */

  int szMap;                 /* Size of the mapping into memory */
  char *pMMapBuf;            /* Where currently mmapped().  NULL if unmapped */

  int pgsz;                  /* Size of shared-memory pages */
  int nPage;                 /* Size of array apPage */
  char **apPage;             /* Array of mapped shared-memory pages */

  int nRef;                  /* Number of unixShm objects pointing to this */
  unixShm *pFirst;           /* All unixShm objects pointing to this */
#ifdef SQLITE_DEBUG
  u8 exclMask;               /* Mask of exclusive locks held */
  u8 sharedMask;             /* Mask of shared locks held */
  u8 nextShmId;              /* Next available unixShm.id value */
#endif
................................................................................
** This is not a VFS shared-memory method; it is a utility function called
** by VFS shared-memory methods.
*/
static void unixShmPurge(unixFile *pFd){
  unixShmNode *p = pFd->pInode->pShmNode;
  assert( unixMutexHeld() );
  if( p && p->nRef==0 ){
    int i;
    assert( p->pInode==pFd->pInode );
    if( p->mutex ) sqlite3_mutex_free(p->mutex);
    if( p->mutexBuf ) sqlite3_mutex_free(p->mutexBuf);
    if( p->pMMapBuf ) munmap(p->pMMapBuf, p->szMap);
    for(i=0; i<p->nPage; i++){
      munmap(p->apPage[i], p->pgsz);
    }
    sqlite3_free(p->apPage);
    if( p->h>=0 ) close(p->h);
    p->pInode->pShmNode = 0;
    sqlite3_free(p);
  }
}

/* Forward reference */
................................................................................
static void unixShmBarrier(
  sqlite3_file *fd           /* Database file holding the shared memory */
){
  unixEnterMutex();
  unixLeaveMutex();
}

static int unixShmPage(
  sqlite3_file *fd,               /* Handle open on database file */
  int iPage,                      /* Page to retrieve */
  int pgsz,                       /* Size of pages */
  int isWrite,                    /* True to extend file if necessary */
  void volatile **pp              /* OUT: Mapped memory */
){
  unixFile *pDbFd = (unixFile*)fd;
  unixShm *p = pDbFd->pShm;
  unixShmNode *pShmNode = p->pShmNode;
  int rc = SQLITE_OK;

  assert( p->hasMutexBuf==0 );
  sqlite3_mutex_enter(pShmNode->mutexBuf);
  assert( pgsz==pShmNode->pgsz || pShmNode->nPage==0 );

  if( pShmNode->nPage<=iPage ){
    char **apNew;                 /* New apPage[] array */
    int nByte = (iPage+1)*pgsz;   /* Minimum required file size */
    struct stat sStat;

    pShmNode->pgsz = pgsz;

    /* Make sure the underlying file is large enough (or fail) */
    if( fstat(pShmNode->h, &sStat) ){
      rc = SQLITE_IOERR_SHMSIZE;
      goto shmpage_out;
    }else if( sStat.st_size<nByte ){
      if( !isWrite ) goto shmpage_out;
      if( ftruncate(pShmNode->h, nByte) ){
        rc = SQLITE_IOERR_SHMSIZE;
        goto shmpage_out;
      }  
    }

    apNew = (char**)sqlite3_realloc(pShmNode->apPage, (iPage+1)*sizeof(char *));
    if( !apNew ){
      rc = SQLITE_IOERR_NOMEM;
      goto shmpage_out;
    }
    pShmNode->apPage = apNew;

    while(pShmNode->nPage<=iPage){
      void *pMem = mmap(
          0, pgsz, PROT_READ|PROT_WRITE, MAP_SHARED, pShmNode->h, iPage*pgsz
      );
      if( pMem==MAP_FAILED ){
        assert(0);
        rc = SQLITE_IOERR;
        goto shmpage_out;
      }
      pShmNode->apPage[pShmNode->nPage] = pMem;
      pShmNode->nPage++;
    }
  }

shmpage_out:
  if( pShmNode->nPage>iPage ){
    *pp = pShmNode->apPage[iPage];
  }else{
    *pp = 0;
  }
  sqlite3_mutex_leave(pShmNode->mutexBuf);
  return rc;
}

#else
# define unixShmOpen    0
# define unixShmSize    0
# define unixShmGet     0
# define unixShmRelease 0
# define unixShmLock    0
# define unixShmBarrier 0
# define unixShmClose   0
# define unixShmPage    0
#endif /* #ifndef SQLITE_OMIT_WAL */

/*
** Here ends the implementation of all sqlite3_file methods.
**
********************** End sqlite3_file Methods *******************************
******************************************************************************/
................................................................................
   unixDeviceCharacteristics,  /* xDeviceCapabilities */                     \
   unixShmOpen,                /* xShmOpen */                                \
   unixShmSize,                /* xShmSize */                                \
   unixShmGet,                 /* xShmGet */                                 \
   unixShmRelease,             /* xShmRelease */                             \
   unixShmLock,                /* xShmLock */                                \
   unixShmBarrier,             /* xShmBarrier */                             \
   unixShmClose,               /* xShmClose */                               \
   unixShmPage                 /* xShmPage */                                \
};                                                                           \
static const sqlite3_io_methods *FINDER##Impl(const char *z, unixFile *p){   \
  UNUSED_PARAMETER(z); UNUSED_PARAMETER(p);                                  \
  return &METHOD;                                                            \
}                                                                            \
static const sqlite3_io_methods *(*const FINDER)(const char*,unixFile *p)    \
    = FINDER##Impl;

  int (*xShmOpen)(sqlite3_file*);
  int (*xShmSize)(sqlite3_file*, int reqSize, int *pNewSize);
  int (*xShmGet)(sqlite3_file*, int reqSize, int *pSize, void volatile**);
  int (*xShmRelease)(sqlite3_file*);
  int (*xShmLock)(sqlite3_file*, int offset, int n, int flags);
  void (*xShmBarrier)(sqlite3_file*);
  int (*xShmClose)(sqlite3_file*, int deleteFlag);

  /* Methods above are valid for version 2 */
  /* Additional methods may be added in future releases */
};

/*
** CAPI3REF: Standard File Control Opcodes
**

  int (*xShmOpen)(sqlite3_file*);
  int (*xShmSize)(sqlite3_file*, int reqSize, int *pNewSize);
  int (*xShmGet)(sqlite3_file*, int reqSize, int *pSize, void volatile**);
  int (*xShmRelease)(sqlite3_file*);
  int (*xShmLock)(sqlite3_file*, int offset, int n, int flags);
  void (*xShmBarrier)(sqlite3_file*);
  int (*xShmClose)(sqlite3_file*, int deleteFlag);
  int (*xShmPage)(sqlite3_file*, int iPage, int pgsz, int, void volatile**);
  /* Methods above are valid for version 2 */
  /* Additional methods may be added in future releases */
};

/*
** CAPI3REF: Standard File Control Opcodes
**

static int devsymShmOpen(sqlite3_file*);
static int devsymShmSize(sqlite3_file*,int,int*);
static int devsymShmGet(sqlite3_file*,int,int*,volatile void**);
static int devsymShmRelease(sqlite3_file*);
static int devsymShmLock(sqlite3_file*,int,int,int);
static void devsymShmBarrier(sqlite3_file*);
static int devsymShmClose(sqlite3_file*,int);


/*
** Method declarations for devsym_vfs.
*/
static int devsymOpen(sqlite3_vfs*, const char *, sqlite3_file*, int , int *);
static int devsymDelete(sqlite3_vfs*, const char *zName, int syncDir);
static int devsymAccess(sqlite3_vfs*, const char *zName, int flags, int *);
................................................................................
  devsymDeviceCharacteristics,      /* xDeviceCharacteristics */
  devsymShmOpen,                    /* xShmOpen */
  devsymShmSize,                    /* xShmSize */
  devsymShmGet,                     /* xShmGet */
  devsymShmRelease,                 /* xShmRelease */
  devsymShmLock,                    /* xShmLock */
  devsymShmBarrier,                 /* xShmBarrier */
  devsymShmClose                    /* xShmClose */

};

struct DevsymGlobal {
  sqlite3_vfs *pVfs;
  int iDeviceChar;
  int iSectorSize;
};
................................................................................
  devsym_file *p = (devsym_file *)pFile;
  sqlite3OsShmBarrier(p->pReal);
}
static int devsymShmClose(sqlite3_file *pFile, int delFlag){
  devsym_file *p = (devsym_file *)pFile;
  return sqlite3OsShmClose(p->pReal, delFlag);
}













/*
** Open an devsym file handle.
*/
static int devsymOpen(

static int devsymShmOpen(sqlite3_file*);
static int devsymShmSize(sqlite3_file*,int,int*);
static int devsymShmGet(sqlite3_file*,int,int*,volatile void**);
static int devsymShmRelease(sqlite3_file*);
static int devsymShmLock(sqlite3_file*,int,int,int);
static void devsymShmBarrier(sqlite3_file*);
static int devsymShmClose(sqlite3_file*,int);
static int devsymShmPage(sqlite3_file*,int,int,int, void volatile **);

/*
** Method declarations for devsym_vfs.
*/
static int devsymOpen(sqlite3_vfs*, const char *, sqlite3_file*, int , int *);
static int devsymDelete(sqlite3_vfs*, const char *zName, int syncDir);
static int devsymAccess(sqlite3_vfs*, const char *zName, int flags, int *);
................................................................................
  devsymDeviceCharacteristics,      /* xDeviceCharacteristics */
  devsymShmOpen,                    /* xShmOpen */
  devsymShmSize,                    /* xShmSize */
  devsymShmGet,                     /* xShmGet */
  devsymShmRelease,                 /* xShmRelease */
  devsymShmLock,                    /* xShmLock */
  devsymShmBarrier,                 /* xShmBarrier */
  devsymShmClose,                   /* xShmClose */
  devsymShmPage                     /* xShmPage */
};

struct DevsymGlobal {
  sqlite3_vfs *pVfs;
  int iDeviceChar;
  int iSectorSize;
};
................................................................................
  devsym_file *p = (devsym_file *)pFile;
  sqlite3OsShmBarrier(p->pReal);
}
static int devsymShmClose(sqlite3_file *pFile, int delFlag){
  devsym_file *p = (devsym_file *)pFile;
  return sqlite3OsShmClose(p->pReal, delFlag);
}
static int devsymShmPage(
  sqlite3_file *pFile, 
  int iPage, 
  int pgsz, 
  int isWrite, 
  void volatile **pp
){
  devsym_file *p = (devsym_file *)pFile;
  return sqlite3OsShmPage(p->pReal, iPage, pgsz, isWrite, pp);
}



/*
** Open an devsym file handle.
*/
static int devsymOpen(

#define TESTVFS_SHMOPEN_MASK    0x00000001
#define TESTVFS_SHMSIZE_MASK    0x00000002
#define TESTVFS_SHMGET_MASK     0x00000004
#define TESTVFS_SHMRELEASE_MASK 0x00000008
#define TESTVFS_SHMLOCK_MASK    0x00000010
#define TESTVFS_SHMBARRIER_MASK 0x00000020
#define TESTVFS_SHMCLOSE_MASK   0x00000040


#define TESTVFS_OPEN_MASK       0x00000080
#define TESTVFS_SYNC_MASK       0x00000100
#define TESTVFS_ALL_MASK        0x000001FF




/*
** A shared-memory buffer. There is one of these objects for each shared
** memory region opened by clients. If two clients open the same file,
** there are two TestvfsFile structures but only one TestvfsBuffer structure.
*/
struct TestvfsBuffer {
  char *zFile;                    /* Associated file name */
  int n;                          /* Size of allocated buffer in bytes */
  u8 *a;                          /* Buffer allocated using ckalloc() */
  TestvfsFile *pFile;             /* List of open handles */
  TestvfsBuffer *pNext;           /* Next in linked list of all buffers */
};


#define PARENTVFS(x) (((Testvfs *)((x)->pAppData))->pParent)

................................................................................
static int tvfsShmOpen(sqlite3_file*);
static int tvfsShmSize(sqlite3_file*, int , int *);
static int tvfsShmGet(sqlite3_file*, int , int *, volatile void **);
static int tvfsShmRelease(sqlite3_file*);
static int tvfsShmLock(sqlite3_file*, int , int, int);
static void tvfsShmBarrier(sqlite3_file*);
static int tvfsShmClose(sqlite3_file*, int);


static sqlite3_io_methods tvfs_io_methods = {
  2,                            /* iVersion */
  tvfsClose,                      /* xClose */
  tvfsRead,                       /* xRead */
  tvfsWrite,                      /* xWrite */
  tvfsTruncate,                   /* xTruncate */
................................................................................
  tvfsDeviceCharacteristics,      /* xDeviceCharacteristics */
  tvfsShmOpen,                    /* xShmOpen */
  tvfsShmSize,                    /* xShmSize */
  tvfsShmGet,                     /* xShmGet */
  tvfsShmRelease,                 /* xShmRelease */
  tvfsShmLock,                    /* xShmLock */
  tvfsShmBarrier,                 /* xShmBarrier */
  tvfsShmClose                    /* xShmClose */

};

static int tvfsResultCode(Testvfs *p, int *pRc){
  struct errcode {
    int eCode;
    const char *zCode;
  } aCode[] = {
................................................................................
/*
** Return the current time as a Julian Day number in *pTimeOut.
*/
static int tvfsCurrentTime(sqlite3_vfs *pVfs, double *pTimeOut){
  return PARENTVFS(pVfs)->xCurrentTime(PARENTVFS(pVfs), pTimeOut);
}

static void tvfsGrowBuffer(TestvfsFile *pFd, int reqSize, int *pNewSize){
  TestvfsBuffer *pBuffer = pFd->pShm;
  if( reqSize>pBuffer->n ){
    pBuffer->a = (u8 *)ckrealloc((char *)pBuffer->a, reqSize);
    memset(&pBuffer->a[pBuffer->n], 0x55, reqSize-pBuffer->n);
    pBuffer->n = reqSize;
  }
  *pNewSize = pBuffer->n;
}

static int tvfsInjectIoerr(Testvfs *p){
  int ret = 0;
  if( p->ioerr ){
    p->iIoerrCnt--;
    if( p->iIoerrCnt==0 || (p->iIoerrCnt<0 && p->ioerr==2) ){
      ret = 1;
      p->nIoerrFail++;
................................................................................
}

static int tvfsShmSize(
  sqlite3_file *pFile,
  int reqSize,
  int *pNewSize
){

  int rc = SQLITE_OK;
  TestvfsFile *pFd = (TestvfsFile *)pFile;
  Testvfs *p = (Testvfs *)(pFd->pVfs->pAppData);

  if( p->pScript && p->mask&TESTVFS_SHMSIZE_MASK ){
    tvfsExecTcl(p, "xShmSize", 
        Tcl_NewStringObj(pFd->pShm->zFile, -1), pFd->pShmId, 0
    );
    tvfsResultCode(p, &rc);
  }
  if( rc==SQLITE_OK && p->mask&TESTVFS_SHMSIZE_MASK && tvfsInjectIoerr(p) ){
    rc = SQLITE_IOERR;
  }
  if( rc==SQLITE_OK ){
    tvfsGrowBuffer(pFd, reqSize, pNewSize);
  }
  return rc;
}

static int tvfsShmGet(
  sqlite3_file *pFile, 
  int reqMapSize, 
  int *pMapSize, 
  volatile void **pp
){

  int rc = SQLITE_OK;
  TestvfsFile *pFd = (TestvfsFile *)pFile;
  Testvfs *p = (Testvfs *)(pFd->pVfs->pAppData);


  if( p->pScript && p->mask&TESTVFS_SHMGET_MASK ){
    tvfsExecTcl(p, "xShmGet", 
        Tcl_NewStringObj(pFd->pShm->zFile, -1), pFd->pShmId, 
        Tcl_NewIntObj(reqMapSize)
    );
    tvfsResultCode(p, &rc);
  }
  if( rc==SQLITE_OK && p->mask&TESTVFS_SHMGET_MASK && tvfsInjectIoerr(p) ){
    rc = SQLITE_IOERR;
  }







  *pMapSize = pFd->pShm->n;
  *pp = pFd->pShm->a;
  return rc;
}

static int tvfsShmRelease(sqlite3_file *pFile){






  int rc = SQLITE_OK;
  TestvfsFile *pFd = (TestvfsFile *)pFile;
  Testvfs *p = (Testvfs *)(pFd->pVfs->pAppData);

  if( p->pScript && p->mask&TESTVFS_SHMRELEASE_MASK ){




    tvfsExecTcl(p, "xShmRelease", 
        Tcl_NewStringObj(pFd->pShm->zFile, -1), pFd->pShmId, 0
    );
    tvfsResultCode(p, &rc);
  }









  return rc;
}


static int tvfsShmLock(
  sqlite3_file *pFile,
  int ofst,
  int n,
  int flags
){
................................................................................
  }

  for(ppFd=&pBuffer->pFile; *ppFd!=pFd; ppFd=&((*ppFd)->pNext));
  assert( (*ppFd)==pFd );
  *ppFd = pFd->pNext;

  if( pBuffer->pFile==0 ){

    TestvfsBuffer **pp;
    for(pp=&p->pBuffer; *pp!=pBuffer; pp=&((*pp)->pNext));
    *pp = (*pp)->pNext;

    ckfree((char *)pBuffer->a);

    ckfree((char *)pBuffer);
  }
  pFd->pShm = 0;

  return rc;
}

................................................................................
  if( Tcl_GetIndexFromObj(interp, objv[1], CMD_strs, "subcommand", 0, &i) ){
    return TCL_ERROR;
  }
  Tcl_ResetResult(interp);

  switch( (enum DB_enum)i ){
    case CMD_SHM: {


      TestvfsBuffer *pBuffer;
      char *zName;
      if( objc!=3 && objc!=4 ){
        Tcl_WrongNumArgs(interp, 2, objv, "FILE ?VALUE?");
        return TCL_ERROR;
      }
      zName = Tcl_GetString(objv[2]);
................................................................................
      if( !pBuffer ){
        Tcl_AppendResult(interp, "no such file: ", zName, 0);
        return TCL_ERROR;
      }
      if( objc==4 ){
        int n;
        u8 *a = Tcl_GetByteArrayFromObj(objv[3], &n);
        pBuffer->a = (u8 *)ckrealloc((char *)pBuffer->a, n);




        pBuffer->n = n;

        memcpy(pBuffer->a, a, n);
      }






      Tcl_SetObjResult(interp, Tcl_NewByteArrayObj(pBuffer->a, pBuffer->n));
      break;
    }

    case CMD_FILTER: {
      static struct VfsMethod {
        char *zName;
        int mask;

#define TESTVFS_SHMOPEN_MASK    0x00000001
#define TESTVFS_SHMSIZE_MASK    0x00000002
#define TESTVFS_SHMGET_MASK     0x00000004
#define TESTVFS_SHMRELEASE_MASK 0x00000008
#define TESTVFS_SHMLOCK_MASK    0x00000010
#define TESTVFS_SHMBARRIER_MASK 0x00000020
#define TESTVFS_SHMCLOSE_MASK   0x00000040
#define TESTVFS_SHMPAGE_MASK    0x00000080

#define TESTVFS_OPEN_MASK       0x00000100
#define TESTVFS_SYNC_MASK       0x00000200
#define TESTVFS_ALL_MASK        0x000003FF


#define TESTVFS_MAX_PAGES 256

/*
** A shared-memory buffer. There is one of these objects for each shared
** memory region opened by clients. If two clients open the same file,
** there are two TestvfsFile structures but only one TestvfsBuffer structure.
*/
struct TestvfsBuffer {
  char *zFile;                    /* Associated file name */
  int pgsz;                       /* Page size */
  u8 *aPage[TESTVFS_MAX_PAGES];   /* Array of ckalloc'd pages */
  TestvfsFile *pFile;             /* List of open handles */
  TestvfsBuffer *pNext;           /* Next in linked list of all buffers */
};


#define PARENTVFS(x) (((Testvfs *)((x)->pAppData))->pParent)

................................................................................
static int tvfsShmOpen(sqlite3_file*);
static int tvfsShmSize(sqlite3_file*, int , int *);
static int tvfsShmGet(sqlite3_file*, int , int *, volatile void **);
static int tvfsShmRelease(sqlite3_file*);
static int tvfsShmLock(sqlite3_file*, int , int, int);
static void tvfsShmBarrier(sqlite3_file*);
static int tvfsShmClose(sqlite3_file*, int);
static int tvfsShmPage(sqlite3_file*,int,int,int, void volatile **);

static sqlite3_io_methods tvfs_io_methods = {
  2,                            /* iVersion */
  tvfsClose,                      /* xClose */
  tvfsRead,                       /* xRead */
  tvfsWrite,                      /* xWrite */
  tvfsTruncate,                   /* xTruncate */
................................................................................
  tvfsDeviceCharacteristics,      /* xDeviceCharacteristics */
  tvfsShmOpen,                    /* xShmOpen */
  tvfsShmSize,                    /* xShmSize */
  tvfsShmGet,                     /* xShmGet */
  tvfsShmRelease,                 /* xShmRelease */
  tvfsShmLock,                    /* xShmLock */
  tvfsShmBarrier,                 /* xShmBarrier */
  tvfsShmClose,                   /* xShmClose */
  tvfsShmPage                     /* xShmPage */
};

static int tvfsResultCode(Testvfs *p, int *pRc){
  struct errcode {
    int eCode;
    const char *zCode;
  } aCode[] = {
................................................................................
/*
** Return the current time as a Julian Day number in *pTimeOut.
*/
static int tvfsCurrentTime(sqlite3_vfs *pVfs, double *pTimeOut){
  return PARENTVFS(pVfs)->xCurrentTime(PARENTVFS(pVfs), pTimeOut);
}











static int tvfsInjectIoerr(Testvfs *p){
  int ret = 0;
  if( p->ioerr ){
    p->iIoerrCnt--;
    if( p->iIoerrCnt==0 || (p->iIoerrCnt<0 && p->ioerr==2) ){
      ret = 1;
      p->nIoerrFail++;
................................................................................
}

static int tvfsShmSize(
  sqlite3_file *pFile,
  int reqSize,
  int *pNewSize
){
  assert(0);
  return SQLITE_OK;


}















static int tvfsShmGet(
  sqlite3_file *pFile, 
  int reqMapSize, 
  int *pMapSize, 
  volatile void **pp
){
  assert(0);
  return SQLITE_OK;


}
static int tvfsShmRelease(sqlite3_file *pFile){
  assert(0);
  return SQLITE_OK;




}



static void tvfsAllocPage(TestvfsBuffer *p, int iPage, int pgsz){
  assert( iPage<TESTVFS_MAX_PAGES );
  if( p->aPage[iPage]==0 ){
    p->aPage[iPage] = ckalloc(pgsz);
    memset(p->aPage[iPage], 0, pgsz);
    p->pgsz = pgsz;
  }



}

static int tvfsShmPage(
  sqlite3_file *pFile,            /* Handle open on database file */
  int iPage,                      /* Page to retrieve */
  int pgsz,                       /* Size of pages */
  int isWrite,                    /* True to extend file if necessary */
  void volatile **pp              /* OUT: Mapped memory */
){
  int rc = SQLITE_OK;
  TestvfsFile *pFd = (TestvfsFile *)pFile;
  Testvfs *p = (Testvfs *)(pFd->pVfs->pAppData);

  if( p->pScript && p->mask&TESTVFS_SHMPAGE_MASK ){
    Tcl_Obj *pArg = Tcl_NewObj();
    Tcl_ListObjAppendElement(p->interp, pArg, Tcl_NewIntObj(iPage));
    Tcl_ListObjAppendElement(p->interp, pArg, Tcl_NewIntObj(pgsz));
    Tcl_ListObjAppendElement(p->interp, pArg, Tcl_NewIntObj(isWrite));
    tvfsExecTcl(p, "xShmPage", 
        Tcl_NewStringObj(pFd->pShm->zFile, -1), pFd->pShmId, pArg
    );
    tvfsResultCode(p, &rc);
  }
  if( rc==SQLITE_OK && p->mask&TESTVFS_SHMPAGE_MASK && tvfsInjectIoerr(p) ){
    rc = SQLITE_IOERR;
  }

  if( rc==SQLITE_OK && isWrite && !pFd->pShm->aPage[iPage] ){
    tvfsAllocPage(pFd->pShm, iPage, pgsz);
  }
  *pp = (void volatile *)pFd->pShm->aPage[iPage];

  return rc;
}


static int tvfsShmLock(
  sqlite3_file *pFile,
  int ofst,
  int n,
  int flags
){
................................................................................
  }

  for(ppFd=&pBuffer->pFile; *ppFd!=pFd; ppFd=&((*ppFd)->pNext));
  assert( (*ppFd)==pFd );
  *ppFd = pFd->pNext;

  if( pBuffer->pFile==0 ){
    int i;
    TestvfsBuffer **pp;
    for(pp=&p->pBuffer; *pp!=pBuffer; pp=&((*pp)->pNext));
    *pp = (*pp)->pNext;
    for(i=0; pBuffer->aPage[i]; i++){
      ckfree((char *)pBuffer->aPage[i]);
    }
    ckfree((char *)pBuffer);
  }
  pFd->pShm = 0;

  return rc;
}

................................................................................
  if( Tcl_GetIndexFromObj(interp, objv[1], CMD_strs, "subcommand", 0, &i) ){
    return TCL_ERROR;
  }
  Tcl_ResetResult(interp);

  switch( (enum DB_enum)i ){
    case CMD_SHM: {
      Tcl_Obj *pObj;
      int i;
      TestvfsBuffer *pBuffer;
      char *zName;
      if( objc!=3 && objc!=4 ){
        Tcl_WrongNumArgs(interp, 2, objv, "FILE ?VALUE?");
        return TCL_ERROR;
      }
      zName = Tcl_GetString(objv[2]);
................................................................................
      if( !pBuffer ){
        Tcl_AppendResult(interp, "no such file: ", zName, 0);
        return TCL_ERROR;
      }
      if( objc==4 ){
        int n;
        u8 *a = Tcl_GetByteArrayFromObj(objv[3], &n);
        assert( pBuffer->pgsz==0 || pBuffer->pgsz==32768 );
        for(i=0; i*32768<n; i++){
          int nByte = 32768;
          tvfsAllocPage(pBuffer, i, 32768);
          if( n-i*32768<32768 ){
            nByte = n;
          }
          memcpy(pBuffer->aPage[i], &a[i*32768], nByte);
        }
      }

      pObj = Tcl_NewObj();
      for(i=0; pBuffer->aPage[i]; i++){
        Tcl_AppendObjToObj(pObj, Tcl_NewByteArrayObj(pBuffer->aPage[i], 32768));
      }
      Tcl_SetObjResult(interp, pObj);
      break;
    }

    case CMD_FILTER: {
      static struct VfsMethod {
        char *zName;
        int mask;

** following object.
*/
struct Wal {
  sqlite3_vfs *pVfs;         /* The VFS used to create pDbFd */
  sqlite3_file *pDbFd;       /* File handle for the database file */
  sqlite3_file *pWalFd;      /* File handle for WAL file */
  u32 iCallback;             /* Value to pass to log callback (or 0) */
  int szWIndex;              /* Size of the wal-index that is mapped in mem */
  volatile u32 *pWiData;     /* Pointer to wal-index content in memory */
  u16 szPage;                /* Database page size */
  i16 readLock;              /* Which read lock is being held.  -1 for none */
  u8 exclusiveMode;          /* Non-zero if connection is in exclusive mode */
  u8 isWIndexOpen;           /* True if ShmOpen() called on pDbFd */
  u8 writeLock;              /* True if in a write transaction */
  u8 ckptLock;               /* True if holding a checkpoint lock */
  WalIndexHdr hdr;           /* Wal-index header for current transaction */
  char *zWalName;            /* Name of WAL file */
  u32 nCkpt;                 /* Checkpoint sequence counter in the wal-header */
#ifdef SQLITE_DEBUG
  u8 lockError;              /* True if a locking error has occurred */
#endif
};

/*





























































** Return a pointer to the WalCkptInfo structure in the wal-index.
*/
static volatile WalCkptInfo *walCkptInfo(Wal *pWal){


  assert( pWal->pWiData!=0 );
  return (volatile WalCkptInfo*)&pWal->pWiData[sizeof(WalIndexHdr)/2];
}


/*
** This structure is used to implement an iterator that loops through
** all frames in the WAL in database page order. Where two or more frames
** correspond to the same database page, the iterator visits only the 
** frame most recently written to the WAL (in other words, the frame with
** the largest index).
................................................................................
**   walIteratorFree() - Free an iterator.
**
** This functionality is used by the checkpoint code (see walCheckpoint()).
*/
struct WalIterator {
  int iPrior;           /* Last result returned from the iterator */
  int nSegment;         /* Size of the aSegment[] array */
  int nFinal;           /* Elements in aSegment[nSegment-1]  */
  struct WalSegment {
    int iNext;              /* Next slot in aIndex[] not previously returned */
    u8 *aIndex;             /* i0, i1, i2... such that aPgno[iN] ascending */
    u32 *aPgno;             /* 256 page numbers.  Pointer to Wal.pWiData */


  } aSegment[1];        /* One for every 256 entries in the WAL */
};

/*
** The argument to this macro must be of type u32. On a little-endian
** architecture, it returns the u32 value that results from interpreting
** the 4 bytes as a big-endian value. On a big-endian architecture, it
** returns the value that would be produced by intepreting the 4 bytes
................................................................................
static void walIndexWriteHdr(Wal *pWal){
  WalIndexHdr *aHdr;

  assert( pWal->writeLock );
  pWal->hdr.isInit = 1;
  walChecksumBytes(1, (u8*)&pWal->hdr, offsetof(WalIndexHdr, aCksum),
                   0, pWal->hdr.aCksum);
  aHdr = (WalIndexHdr*)pWal->pWiData;
  memcpy(&aHdr[1], &pWal->hdr, sizeof(WalIndexHdr));
  sqlite3OsShmBarrier(pWal->pDbFd);
  memcpy(&aHdr[0], &pWal->hdr, sizeof(WalIndexHdr));
}

/*
** This function encodes a single frame header and writes it to a buffer
................................................................................
  ** and the new database size.
  */
  *piPage = pgno;
  *pnTruncate = sqlite3Get4byte(&aFrame[4]);
  return 1;
}

/*
** Define the parameters of the hash tables in the wal-index file. There
** is a hash-table following every HASHTABLE_NPAGE page numbers in the
** wal-index.
**
** Changing any of these constants will alter the wal-index format and
** create incompatibilities.
*/
#define HASHTABLE_NPAGE      4096  /* Must be power of 2 and multiple of 256 */
#define HASHTABLE_DATATYPE   u16
#define HASHTABLE_HASH_1     383                  /* Should be prime */
#define HASHTABLE_NSLOT      (HASHTABLE_NPAGE*2)  /* Must be a power of 2 */
#define HASHTABLE_NBYTE      (sizeof(HASHTABLE_DATATYPE)*HASHTABLE_NSLOT)

#if defined(SQLITE_TEST) && defined(SQLITE_DEBUG)
/*
** Names of locks.  This routine is used to provide debugging output and is not
** a part of an ordinary build.
*/
static const char *walLockName(int lockIdx){
................................................................................
  if( pWal->exclusiveMode ) return;
  (void)sqlite3OsShmLock(pWal->pDbFd, lockIdx, n,
                         SQLITE_SHM_UNLOCK | SQLITE_SHM_EXCLUSIVE);
  WALTRACE(("WAL%p: release EXCLUSIVE-%s cnt=%d\n", pWal,
             walLockName(lockIdx), n));
}

/*
** Return the index in the Wal.pWiData array that corresponds to 
** frame iFrame.
**
** Wal.pWiData is an array of u32 elements that is the wal-index.
** The array begins with a header and is then followed by alternating
** "map" and "hash-table" blocks.  Each "map" block consists of
** HASHTABLE_NPAGE u32 elements which are page numbers corresponding
** to frames in the WAL file.  
**
** This routine returns an index X such that Wal.pWiData[X] is part
** of a "map" block that contains the page number of the iFrame-th
** frame in the WAL file.
*/
static int walIndexEntry(u32 iFrame){
  return (
      (WALINDEX_LOCK_OFFSET+WALINDEX_LOCK_RESERVED)/sizeof(u32)
    + (((iFrame-1)/HASHTABLE_NPAGE) * HASHTABLE_NBYTE)/sizeof(u32)
    + (iFrame-1)
  );
}

/*
** Return the minimum size of the shared-memory, in bytes, that is needed
** to support a wal-index containing frame iFrame.  The value returned
** includes the wal-index header and the complete "block" containing iFrame,
** including the hash table segment that follows the block.
*/
static int walMappingSize(u32 iFrame){
  const int nByte = (sizeof(u32)*HASHTABLE_NPAGE + HASHTABLE_NBYTE) ;
  return ( WALINDEX_LOCK_OFFSET 
         + WALINDEX_LOCK_RESERVED 
         + nByte * ((iFrame + HASHTABLE_NPAGE - 1)/HASHTABLE_NPAGE)
  );
}

/*
** Release our reference to the wal-index memory map, if we are holding
** it.
*/
static void walIndexUnmap(Wal *pWal){
  if( pWal->pWiData ){
    sqlite3OsShmRelease(pWal->pDbFd);
  }
  pWal->pWiData = 0;
  pWal->szWIndex = -1;
}

/*
** Map the wal-index file into memory if it isn't already. 
**
** The reqSize parameter is the requested size of the mapping.  The
** mapping will be at least this big if the underlying storage is
** that big.  But the mapping will never grow larger than the underlying
** storage.  Use the walIndexRemap() to enlarget the storage space.
*/
static int walIndexMap(Wal *pWal, int reqSize){
  int rc = SQLITE_OK;
  if( pWal->pWiData==0 || reqSize>pWal->szWIndex ){
    walIndexUnmap(pWal);
    rc = sqlite3OsShmGet(pWal->pDbFd, reqSize, &pWal->szWIndex,
                             (void volatile**)(char volatile*)&pWal->pWiData);
    if( rc!=SQLITE_OK ){
      walIndexUnmap(pWal);
    }
  }
  return rc;
}

/*
** Enlarge the wal-index to be at least enlargeTo bytes in size and
** Remap the wal-index so that the mapping covers the full size
** of the underlying file.
**
** If enlargeTo is non-negative, then increase the size of the underlying
** storage to be at least as big as enlargeTo before remapping.
*/
static int walIndexRemap(Wal *pWal, int enlargeTo){
  int rc;
  int sz;
  assert( pWal->writeLock );
  rc = sqlite3OsShmSize(pWal->pDbFd, enlargeTo, &sz);
  if( rc==SQLITE_OK && sz>pWal->szWIndex ){
    walIndexUnmap(pWal);
    rc = walIndexMap(pWal, sz);
  }
  assert( pWal->szWIndex>=enlargeTo || rc!=SQLITE_OK );
  return rc;
}

/*
** Compute a hash on a page number.  The resulting hash value must land
** between 0 and (HASHTABLE_NSLOT-1).  The walHashNext() function advances
** the hash to the next value in the event of a collision.
*/
static int walHash(u32 iPage){
  assert( iPage>0 );
................................................................................
  assert( (HASHTABLE_NSLOT & (HASHTABLE_NSLOT-1))==0 );
  return (iPage*HASHTABLE_HASH_1) & (HASHTABLE_NSLOT-1);
}
static int walNextHash(int iPriorHash){
  return (iPriorHash+1)&(HASHTABLE_NSLOT-1);
}


















































/* 
** Find the hash table and (section of the) page number array used to
** store data for WAL frame iFrame.
**
** Set output variable *paHash to point to the start of the hash table
** in the wal-index file. Set *piZero to one less than the frame 
................................................................................
static void walHashFind(
  Wal *pWal,                      /* WAL handle */
  u32 iFrame,                     /* Find the hash table indexing this frame */
  volatile HASHTABLE_DATATYPE **paHash,    /* OUT: Pointer to hash index */
  volatile u32 **paPgno,          /* OUT: Pointer to page number array */
  u32 *piZero                     /* OUT: Frame associated with *paPgno[0] */
){
  u32 iZero;
  volatile u32 *aPgno;
  volatile HASHTABLE_DATATYPE *aHash;

  iZero = ((iFrame-1)/HASHTABLE_NPAGE) * HASHTABLE_NPAGE;
  aPgno = &pWal->pWiData[walIndexEntry(iZero+1)-iZero-1];
  aHash = (HASHTABLE_DATATYPE *)&aPgno[iZero+HASHTABLE_NPAGE+1];

  /* Assert that:
  **
  **   + the mapping is large enough for this hash-table, and
  **
  **   + that aPgno[iZero+1] really is the database page number associated
  **     with the first frame indexed by this hash table.
  */
  assert( (u32*)(&aHash[HASHTABLE_NSLOT])<=&pWal->pWiData[pWal->szWIndex/4] );
  assert( walIndexEntry(iZero+1)==(&aPgno[iZero+1] - pWal->pWiData) );

  *paHash = aHash;
  *paPgno = aPgno;
  *piZero = iZero;
}

/*
** Remove entries from the hash table that point to WAL slots greater
** than pWal->hdr.mxFrame.
**
** This function is called whenever pWal->hdr.mxFrame is decreased due
................................................................................
** actually needed.
*/
static void walCleanupHash(Wal *pWal){
  volatile HASHTABLE_DATATYPE *aHash;  /* Pointer to hash table to clear */
  volatile u32 *aPgno;                 /* Unused return from walHashFind() */
  u32 iZero;                           /* frame == (aHash[x]+iZero) */
  int iLimit = 0;                      /* Zero values greater than this */



  assert( pWal->writeLock );
  testcase( pWal->hdr.mxFrame==HASHTABLE_NPAGE-1 );
  testcase( pWal->hdr.mxFrame==HASHTABLE_NPAGE );
  testcase( pWal->hdr.mxFrame==HASHTABLE_NPAGE+1 );
  if( (pWal->hdr.mxFrame % HASHTABLE_NPAGE)>0 ){
    int nByte;                    /* Number of bytes to zero in aPgno[] */
    int i;                        /* Used to iterate through aHash[] */

    walHashFind(pWal, pWal->hdr.mxFrame+1, &aHash, &aPgno, &iZero);

    iLimit = pWal->hdr.mxFrame - iZero;
    assert( iLimit>0 );
    for(i=0; i<HASHTABLE_NSLOT; i++){
      if( aHash[i]>iLimit ){
        aHash[i] = 0;
      }
    }

    /* Zero the entries in the aPgno array that correspond to frames with
    ** frame numbers greater than pWal->hdr.mxFrame. 
    */
    nByte = sizeof(u32) * (HASHTABLE_NPAGE-iLimit);
    memset((void *)&aPgno[iZero+iLimit+1], 0, nByte);
    assert( &((u8 *)&aPgno[iZero+iLimit+1])[nByte]==(u8 *)aHash );
  }

#ifdef SQLITE_ENABLE_EXPENSIVE_ASSERT
  /* Verify that the every entry in the mapping region is still reachable
  ** via the hash table even after the cleanup.
  */
  if( iLimit ){
................................................................................


/*
** Set an entry in the wal-index that will map database page number
** pPage into WAL frame iFrame.
*/
static int walIndexAppend(Wal *pWal, u32 iFrame, u32 iPage){
  int rc;                         /* Return code */
  int nMapping;                   /* Required mapping size in bytes */
  
  /* Make sure the wal-index is mapped. Enlarge the mapping if required. */
  nMapping = walMappingSize(iFrame);
  rc = walIndexMap(pWal, nMapping);
  while( rc==SQLITE_OK && nMapping>pWal->szWIndex ){
    rc = walIndexRemap(pWal, nMapping);
  }

  /* Assuming the wal-index file was successfully mapped, find the hash 
  ** table and section of of the page number array that pertain to frame 
  ** iFrame of the WAL. Then populate the page number array and the hash 
  ** table entry.
  */
  if( rc==SQLITE_OK ){
................................................................................
    volatile HASHTABLE_DATATYPE *aHash;  /* Hash table */
    int idx;                             /* Value to write to hash-table slot */
    TESTONLY( int nCollide = 0;          /* Number of hash collisions */ )

    walHashFind(pWal, iFrame, &aHash, &aPgno, &iZero);
    idx = iFrame - iZero;
    if( idx==1 ){
      memset((void*)&aPgno[iZero+1], 0, HASHTABLE_NPAGE*sizeof(u32));
      memset((void*)aHash, 0, HASHTABLE_NBYTE);
    }
    assert( idx <= HASHTABLE_NSLOT/2 + 1 );

    if( aPgno[iFrame] ){
      /* If the entry in aPgno[] is already set, then the previous writer
      ** must have exited unexpectedly in the middle of a transaction (after
      ** writing one or more dirty pages to the WAL to free up memory). 
................................................................................
      }
    }

    sqlite3_free(aFrame);
  }

finished:
  if( rc==SQLITE_OK && pWal->hdr.mxFrame==0 ){
    rc = walIndexRemap(pWal, walMappingSize(1));
  }
  if( rc==SQLITE_OK ){
    volatile WalCkptInfo *pInfo;
    int i;
    pWal->hdr.aFrameCksum[0] = aFrameCksum[0];
    pWal->hdr.aFrameCksum[1] = aFrameCksum[1];
    walIndexWriteHdr(pWal);

................................................................................
  if( !pRet ){
    return SQLITE_NOMEM;
  }

  pRet->pVfs = pVfs;
  pRet->pWalFd = (sqlite3_file *)&pRet[1];
  pRet->pDbFd = pDbFd;
  pRet->szWIndex = -1;
  pRet->readLock = -1;
  sqlite3_randomness(8, &pRet->hdr.aSalt);
  pRet->zWalName = zWal = pVfs->szOsFile + (char*)pRet->pWalFd;
  sqlite3_snprintf(nWal, zWal, "%s-wal", zDbName);
  rc = sqlite3OsShmOpen(pDbFd);

  /* Open file handle on the write-ahead log file. */
................................................................................
  WalIterator *p,               /* Iterator */
  u32 *piPage,                  /* OUT: The page number of the next page */
  u32 *piFrame                  /* OUT: Wal frame index of next page */
){
  u32 iMin;                     /* Result pgno must be greater than iMin */
  u32 iRet = 0xFFFFFFFF;        /* 0xffffffff is never a valid page number */
  int i;                        /* For looping through segments */
  int nBlock = p->nFinal;       /* Number of entries in current segment */

  iMin = p->iPrior;
  assert( iMin<0xffffffff );
  for(i=p->nSegment-1; i>=0; i--){
    struct WalSegment *pSegment = &p->aSegment[i];
    while( pSegment->iNext<nBlock ){
      u32 iPg = pSegment->aPgno[pSegment->aIndex[pSegment->iNext]];
      if( iPg>iMin ){
        if( iPg<iRet ){
          iRet = iPg;
          *piFrame = i*256 + 1 + pSegment->aIndex[pSegment->iNext];
        }
        break;
      }
      pSegment->iNext++;
    }
    nBlock = 256;
  }

  *piPage = p->iPrior = iRet;
  return (iRet==0xFFFFFFFF);
}


static void walMergesort8(
  Pgno *aContent,                 /* Pages in wal */
  u8 *aBuffer,                    /* Buffer of at least *pnList items to use */
  u8 *aList,                      /* IN/OUT: List to sort */
  int *pnList                     /* IN/OUT: Number of elements in aList[] */
){
  int nList = *pnList;
  if( nList>1 ){
    int nLeft = nList / 2;        /* Elements in left list */
    int nRight = nList - nLeft;   /* Elements in right list */
    u8 *aLeft = aList;            /* Left list */
    u8 *aRight = &aList[nLeft];   /* Right list */
    int iLeft = 0;                /* Current index in aLeft */
    int iRight = 0;               /* Current index in aright */
    int iOut = 0;                 /* Current index in output buffer */



    /* TODO: Change to non-recursive version. */
    walMergesort8(aContent, aBuffer, aLeft, &nLeft);
    walMergesort8(aContent, aBuffer, aRight, &nRight);

    while( iRight<nRight || iLeft<nLeft ){
      u8 logpage;
      Pgno dbpage;

      if( (iLeft<nLeft) 
       && (iRight>=nRight || aContent[aLeft[iLeft]]<aContent[aRight[iRight]])
      ){
        logpage = aLeft[iLeft++];
      }else{
................................................................................
**
** The calling routine should invoke walIteratorFree() to destroy the
** WalIterator object when it has finished with it.  The caller must
** also unmap the wal-index.  But the wal-index must not be unmapped
** prior to the WalIterator object being destroyed.
*/
static int walIteratorInit(Wal *pWal, WalIterator **pp){
  u32 *aData;           /* Content of the wal-index file */
  WalIterator *p;       /* Return value */
  int nSegment;         /* Number of segments to merge */
  u32 iLast;            /* Last frame in log */
  int nByte;            /* Number of bytes to allocate */
  int i;                /* Iterator variable */
  int nFinal;           /* Number of unindexed entries */
  u8 *aTmp;             /* Temp space used by merge-sort */
  u8 *aSpace;           /* Surplus space on the end of the allocation */

  /* Make sure the wal-index is mapped into local memory */
  assert( pWal->pWiData && pWal->szWIndex>=walMappingSize(pWal->hdr.mxFrame) );

  /* This routine only runs while holding SQLITE_SHM_CHECKPOINT.  No other
  ** thread is able to write to shared memory while this routine is
  ** running (or, indeed, while the WalIterator object exists).  Hence,
  ** we can cast off the volatile qualifacation from shared memory
  */
  assert( pWal->ckptLock );
  aData = (u32*)pWal->pWiData;

  /* Allocate space for the WalIterator object */
  iLast = pWal->hdr.mxFrame;
  nSegment = (iLast >> 8) + 1;
  nFinal = (iLast & 0x000000FF);
  nByte = sizeof(WalIterator) + (nSegment+1)*(sizeof(struct WalSegment)+256);

  p = (WalIterator *)sqlite3_malloc(nByte);
  if( !p ){
    return SQLITE_NOMEM;
  }
  memset(p, 0, nByte);

  /* Initialize the WalIterator object.  Each 256-entry segment is
  ** presorted in order to make iterating through all entries much
  ** faster.
  */
  p->nSegment = nSegment;
  aSpace = (u8 *)&p->aSegment[nSegment];
  aTmp = &aSpace[nSegment*256];
  for(i=0; i<nSegment; i++){

    int j;





    int nIndex = (i==nSegment-1) ? nFinal : 256;
    p->aSegment[i].aPgno = &aData[walIndexEntry(i*256+1)];
    p->aSegment[i].aIndex = aSpace;









    for(j=0; j<nIndex; j++){
      aSpace[j] = j;
    }




    walMergesort8(p->aSegment[i].aPgno, aTmp, aSpace, &nIndex);
    memset(&aSpace[nIndex], aSpace[nIndex-1], 256-nIndex);
    aSpace += 256;
    p->nFinal = nIndex;
  }


  /* Return the fully initializd WalIterator object */
  *pp = p;
  return SQLITE_OK ;
}

/* 
** Free an iterator allocated by walIteratorInit().
*/
................................................................................

  /* Compute in mxSafeFrame the index of the last frame of the WAL that is
  ** safe to write into the database.  Frames beyond mxSafeFrame might
  ** overwrite database pages that are in use by active readers and thus
  ** cannot be backfilled from the WAL.
  */
  mxSafeFrame = pWal->hdr.mxFrame;
  pHdr = (volatile WalIndexHdr*)pWal->pWiData;
  pInfo = (volatile WalCkptInfo*)&pHdr[2];
  assert( pInfo==walCkptInfo(pWal) );
  for(i=1; i<WAL_NREADER; i++){
    u32 y = pInfo->aReadMark[i];
    if( mxSafeFrame>=y ){
      assert( y<=pWal->hdr.mxFrame );
      rc = walLockExclusive(pWal, WAL_READ_LOCK(i), 1);
      if( rc==SQLITE_OK ){
................................................................................
    /* Sync the WAL to disk */
    if( sync_flags ){
      rc = sqlite3OsSync(pWal->pWalFd, sync_flags);
    }

    /* Iterate through the contents of the WAL, copying data to the db file. */
    while( rc==SQLITE_OK && 0==walIteratorNext(pIter, &iDbpage, &iFrame) ){

      if( iFrame<=nBackfill || iFrame>mxSafeFrame ) continue;
      rc = sqlite3OsRead(pWal->pWalFd, zBuf, szPage, 
          walFrameOffset(iFrame, szPage) + WAL_FRAME_HDRSIZE
      );
      if( rc!=SQLITE_OK ) break;
      rc = sqlite3OsWrite(pWal->pDbFd, zBuf, szPage, (iDbpage-1)*szPage);
      if( rc!=SQLITE_OK ) break;
................................................................................
    rc = sqlite3OsLock(pWal->pDbFd, SQLITE_LOCK_EXCLUSIVE);
    if( rc==SQLITE_OK ){
      pWal->exclusiveMode = 1;
      rc = sqlite3WalCheckpoint(pWal, sync_flags, nBuf, zBuf);
      if( rc==SQLITE_OK ){
        isDelete = 1;
      }
      walIndexUnmap(pWal);
    }

    walIndexClose(pWal, isDelete);
    sqlite3OsClose(pWal->pWalFd);
    if( isDelete ){
      sqlite3OsDelete(pWal->pVfs, pWal->zWalName, 0);
    }
    WALTRACE(("WAL%p: closed\n", pWal));

    sqlite3_free(pWal);
  }
  return rc;
}

/*
** Try to read the wal-index header.  Return 0 on success and 1 if
................................................................................
** If the checksum cannot be verified return non-zero. If the header
** is read successfully and the checksum verified, return zero.
*/
int walIndexTryHdr(Wal *pWal, int *pChanged){
  u32 aCksum[2];               /* Checksum on the header content */
  WalIndexHdr h1, h2;          /* Two copies of the header content */
  WalIndexHdr *aHdr;           /* Header in shared memory */


  if( pWal->szWIndex < WALINDEX_HDR_SIZE ){


    /* The wal-index is not large enough to hold the header, then assume
    ** header is invalid. */
    return 1;
  }
  assert( pWal->pWiData );

  /* Read the header. This might happen currently with a write to the
  ** same area of shared memory on a different CPU in a SMP,
  ** meaning it is possible that an inconsistent snapshot is read
  ** from the file. If this happens, return non-zero.
  **
  ** There are two copies of the header at the beginning of the wal-index.
  ** When reading, read [0] first then [1].  Writes are in the reverse order.
  ** Memory barriers are used to prevent the compiler or the hardware from
  ** reordering the reads and writes.
  */
  aHdr = (WalIndexHdr*)pWal->pWiData;
  memcpy(&h1, &aHdr[0], sizeof(h1));
  sqlite3OsShmBarrier(pWal->pDbFd);
  memcpy(&h2, &aHdr[1], sizeof(h2));

  if( memcmp(&h1, &h2, sizeof(h1))!=0 ){
    return 1;   /* Dirty read */
  }  
................................................................................
**
** If the wal-index header is successfully read, return SQLITE_OK. 
** Otherwise an SQLite error code.
*/
static int walIndexReadHdr(Wal *pWal, int *pChanged){
  int rc;                         /* Return code */
  int badHdr;                     /* True if a header read failed */


  assert( pChanged );
  rc = walIndexMap(pWal, walMappingSize(1));

  if( rc!=SQLITE_OK ){
    return rc;
  }

  /* Try once to read the header straight out.  This works most of the
  ** time.
  */
................................................................................
        *pChanged = 1;
      }
      walUnlockExclusive(pWal, WAL_WRITE_LOCK, 1);
      pWal->writeLock = 0;
    }
  }

  /* Make sure the mapping is large enough to cover the entire wal-index */
  if( rc==SQLITE_OK ){
    int szWanted = walMappingSize(pWal->hdr.mxFrame);
    if( pWal->szWIndex<szWanted ){
      rc = walIndexMap(pWal, szWanted);
    }
  }

  return rc;
}

/*
** This is the value that walTryBeginRead returns when it needs to
** be retried.
*/
................................................................................
*/
static int walTryBeginRead(Wal *pWal, int *pChanged, int useWal, int cnt){
  volatile WalIndexHdr *pHdr;     /* Header of the wal-index */
  volatile WalCkptInfo *pInfo;    /* Checkpoint information in wal-index */
  u32 mxReadMark;                 /* Largest aReadMark[] value */
  int mxI;                        /* Index of largest aReadMark[] value */
  int i;                          /* Loop counter */
  int rc;                         /* Return code  */

  assert( pWal->readLock<0 );     /* Not currently locked */

  /* Take steps to avoid spinning forever if there is a protocol error. */
  if( cnt>5 ){
    if( cnt>100 ) return SQLITE_PROTOCOL;
    sqlite3OsSleep(pWal->pVfs, 1);
................................................................................
      if( rc==SQLITE_OK ){
        walUnlockShared(pWal, WAL_RECOVER_LOCK);
        rc = WAL_RETRY;
      }else if( rc==SQLITE_BUSY ){
        rc = SQLITE_BUSY_RECOVERY;
      }
    }
  }else{
    rc = walIndexMap(pWal, walMappingSize(pWal->hdr.mxFrame));
  }
  if( rc!=SQLITE_OK ){
    return rc;
  }

  pHdr = (volatile WalIndexHdr*)pWal->pWiData;
  pInfo = (volatile WalCkptInfo*)&pHdr[2];
  assert( pInfo==walCkptInfo(pWal) );
  if( !useWal && pInfo->nBackfill==pWal->hdr.mxFrame ){
    /* The WAL has been completely backfilled (or it is empty).
    ** and can be safely ignored.
    */
    rc = walLockShared(pWal, WAL_READ_LOCK(0));
    sqlite3OsShmBarrier(pWal->pDbFd);
    if( rc==SQLITE_OK ){
................................................................................
int sqlite3WalBeginReadTransaction(Wal *pWal, int *pChanged){
  int rc;                         /* Return code */
  int cnt = 0;                    /* Number of TryBeginRead attempts */

  do{
    rc = walTryBeginRead(pWal, pChanged, 0, ++cnt);
  }while( rc==WAL_RETRY );
  walIndexUnmap(pWal);
  return rc;
}

/*
** Finish with a read transaction.  All this does is release the
** read-lock.
*/
................................................................................
int sqlite3WalRead(
  Wal *pWal,                      /* WAL handle */
  Pgno pgno,                      /* Database page number to read data for */
  int *pInWal,                    /* OUT: True if data is read from WAL */
  int nOut,                       /* Size of buffer pOut in bytes */
  u8 *pOut                        /* Buffer to write page data to */
){
  int rc;                         /* Return code */
  u32 iRead = 0;                  /* If !=0, WAL frame to return data from */
  u32 iLast = pWal->hdr.mxFrame;  /* Last page in WAL for this reader */
  int iHash;                      /* Used to loop through N hash tables */

  /* This routine is only be called from within a read transaction. */
  assert( pWal->readLock>=0 || pWal->lockError );

................................................................................
  ** return early, as if the WAL were empty.
  */
  if( iLast==0 || pWal->readLock==0 ){
    *pInWal = 0;
    return SQLITE_OK;
  }

  /* Ensure the wal-index is mapped. */
  rc = walIndexMap(pWal, walMappingSize(iLast));
  if( rc!=SQLITE_OK ){
    return rc;
  }

  /* Search the hash table or tables for an entry matching page number
  ** pgno. Each iteration of the following for() loop searches one
  ** hash table (each hash table indexes up to HASHTABLE_NPAGE frames).
  **
  ** This code may run concurrently to the code in walIndexAppend()
  ** that adds entries to the wal-index (and possibly to this hash 
  ** table). This means the value just read from the hash 
................................................................................
  **   (aPgno[iFrame]==pgno): 
  **     This condition filters out normal hash-table collisions.
  **
  **   (iFrame<=iLast): 
  **     This condition filters out entries that were added to the hash
  **     table after the current read-transaction had started.
  */
  for(iHash=iLast; iHash>0 && iRead==0; iHash-=HASHTABLE_NPAGE){
    volatile HASHTABLE_DATATYPE *aHash;  /* Pointer to hash table */
    volatile u32 *aPgno;                 /* Pointer to array of page numbers */
    u32 iZero;                    /* Frame number corresponding to aPgno[0] */
    int iKey;                     /* Hash slot index */
    int mxHash;                   /* upper bound on aHash[] values */

    walHashFind(pWal, iHash, &aHash, &aPgno, &iZero);
    mxHash = iLast - iZero;
    if( mxHash > HASHTABLE_NPAGE )  mxHash = HASHTABLE_NPAGE;
    for(iKey=walHash(pgno); aHash[iKey]; iKey=walNextHash(iKey)){
      u32 iFrame = aHash[iKey] + iZero;
      if( iFrame<=iLast && aPgno[iFrame]==pgno ){
        assert( iFrame>iRead );
        iRead = iFrame;
      }
    }
  }
  assert( iRead==0 || pWal->pWiData[walIndexEntry(iRead)]==pgno );

#ifdef SQLITE_ENABLE_EXPENSIVE_ASSERT
  /* If expensive assert() statements are available, do a linear search
  ** of the wal-index file content. Make sure the results agree with the
  ** result obtained using the hash indexes above.  */
  {
    u32 iRead2 = 0;
    u32 iTest;
    for(iTest=iLast; iTest>0; iTest--){
      if( pWal->pWiData[walIndexEntry(iTest)]==pgno ){
        iRead2 = iTest;
        break;
      }
    }
    assert( iRead==iRead2 );
  }
#endif

  /* If iRead is non-zero, then it is the log frame number that contains the
  ** required page. Read and return data from the log file.
  */
  walIndexUnmap(pWal);
  if( iRead ){
    i64 iOffset = walFrameOffset(iRead, pWal->hdr.szPage) + WAL_FRAME_HDRSIZE;
    *pInWal = 1;
    return sqlite3OsRead(pWal->pWalFd, pOut, nOut, iOffset);
  }

  *pInWal = 0;
................................................................................
** thread to write as doing so would cause a fork.  So this routine
** returns SQLITE_BUSY in that case and no write transaction is started.
**
** There can only be a single writer active at a time.
*/
int sqlite3WalBeginWriteTransaction(Wal *pWal){
  int rc;


  /* Cannot start a write transaction without first holding a read
  ** transaction. */
  assert( pWal->readLock>=0 );

  /* Only one writer allowed at a time.  Get the write lock.  Return
  ** SQLITE_BUSY if unable.
................................................................................
  }
  pWal->writeLock = 1;

  /* If another connection has written to the database file since the
  ** time the read transaction on this connection was started, then
  ** the write is disallowed.
  */
  rc = walIndexMap(pWal, walMappingSize(pWal->hdr.mxFrame));
  if( rc ){
    walUnlockExclusive(pWal, WAL_WRITE_LOCK, 1);
    pWal->writeLock = 0;
    return rc;
  }
  if( memcmp(&pWal->hdr, (void*)pWal->pWiData, sizeof(WalIndexHdr))!=0 ){
    walUnlockExclusive(pWal, WAL_WRITE_LOCK, 1);
    pWal->writeLock = 0;
    rc = SQLITE_BUSY;
  }

  walIndexUnmap(pWal);
  return rc;
}

/*
** End a write transaction.  The commit has already been done.  This
** routine merely releases the lock.
*/
................................................................................
int sqlite3WalUndo(Wal *pWal, int (*xUndo)(void *, Pgno), void *pUndoCtx){
  int rc = SQLITE_OK;
  if( pWal->writeLock ){
    int unused;
    Pgno iMax = pWal->hdr.mxFrame;
    Pgno iFrame;
  
    assert( pWal->pWiData==0 );
    rc = walIndexReadHdr(pWal, &unused);
    if( rc==SQLITE_OK ){
      rc = walIndexMap(pWal, walMappingSize(iMax));
    }
    if( rc==SQLITE_OK ){
      for(iFrame=pWal->hdr.mxFrame+1; 
          ALWAYS(rc==SQLITE_OK) && iFrame<=iMax; 
          iFrame++
      ){
        /* This call cannot fail. Unless the page for which the page number
        ** is passed as the second argument is (a) in the cache and 
................................................................................
        **
        ** If the upper layer is doing a rollback, it is guaranteed that there
        ** are no outstanding references to any page other than page 1. And
        ** page 1 is never written to the log until the transaction is
        ** committed. As a result, the call to xUndo may not fail.
        */
        assert( pWal->writeLock );
        assert( pWal->pWiData[walIndexEntry(iFrame)]!=1 );
        rc = xUndo(pUndoCtx, pWal->pWiData[walIndexEntry(iFrame)]);
      }
      walCleanupHash(pWal);
    }
    walIndexUnmap(pWal);
  }
  return rc;
}

/* 
** Argument aWalData must point to an array of WAL_SAVEPOINT_NDATA u32 
** values. This function populates the array with values required to 
................................................................................
    ** to the start of the log. Update the savepoint values to match.
    */
    aWalData[0] = 0;
    aWalData[3] = pWal->nCkpt;
  }

  if( aWalData[0]<pWal->hdr.mxFrame ){
    rc = walIndexMap(pWal, walMappingSize(pWal->hdr.mxFrame));
    pWal->hdr.mxFrame = aWalData[0];
    pWal->hdr.aFrameCksum[0] = aWalData[1];
    pWal->hdr.aFrameCksum[1] = aWalData[2];
    if( rc==SQLITE_OK ){
      walCleanupHash(pWal);
    }
  }

  walIndexUnmap(pWal);
  return rc;
}

/*
** This function is called just before writing a set of frames to the log
** file (see sqlite3WalFrames()). It checks to see if, instead of appending
** to the current log file, it is possible to overwrite the start of the
................................................................................
** or not pWal->hdr.mxFrame is modified). An SQLite error code is returned
** if some error 
*/
static int walRestartLog(Wal *pWal){
  int rc = SQLITE_OK;
  int cnt;

  if( pWal->readLock==0 
   && SQLITE_OK==(rc = walIndexMap(pWal, walMappingSize(pWal->hdr.mxFrame)))
  ){
    volatile WalCkptInfo *pInfo = walCkptInfo(pWal);
    assert( pInfo->nBackfill==pWal->hdr.mxFrame );
    if( pInfo->nBackfill>0 ){
      rc = walLockExclusive(pWal, WAL_READ_LOCK(1), WAL_NREADER-1);
      if( rc==SQLITE_OK ){
        /* If all readers are using WAL_READ_LOCK(0) (in other words if no
        ** readers are currently using the WAL), then the transactions
................................................................................
    walUnlockShared(pWal, WAL_READ_LOCK(0));
    pWal->readLock = -1;
    cnt = 0;
    do{
      int notUsed;
      rc = walTryBeginRead(pWal, &notUsed, 1, ++cnt);
    }while( rc==WAL_RETRY );

    /* Unmap the wal-index before returning. Otherwise the VFS layer may
    ** hold a mutex for the duration of the IO performed by WalFrames().
    */
    walIndexUnmap(pWal);
  }
  return rc;
}

/* 
** Write a set of frames to the log. The caller must hold the write-lock
** on the log file (obtained using sqlite3WalBeginWriteTransaction()).
................................................................................
  u8 aFrame[WAL_FRAME_HDRSIZE];   /* Buffer to assemble frame-header in */
  PgHdr *p;                       /* Iterator to run through pList with. */
  PgHdr *pLast = 0;               /* Last frame in list */
  int nLast = 0;                  /* Number of extra copies of last page */

  assert( pList );
  assert( pWal->writeLock );
  assert( pWal->pWiData==0 );

#if defined(SQLITE_TEST) && defined(SQLITE_DEBUG)
  { int cnt; for(cnt=0, p=pList; p; p=p->pDirty, cnt++){}
    WALTRACE(("WAL%p: frame write begin. %d frames. mxFrame=%d. %s\n",
              pWal, cnt, pWal->hdr.mxFrame, isCommit ? "Commit" : "Spill"));
  }
#endif

  /* See if it is possible to write these frames into the start of the
  ** log file, instead of appending to it at pWal->hdr.mxFrame.
  */
  if( SQLITE_OK!=(rc = walRestartLog(pWal)) ){
    assert( pWal->pWiData==0 );
    return rc;
  }
  assert( pWal->pWiData==0 && pWal->readLock>0 );

  /* If this is the first frame written into the log, write the WAL
  ** header to the start of the WAL file. See comments at the top of
  ** this source file for a description of the WAL header format.
  */
  iFrame = pWal->hdr.mxFrame;
  if( iFrame==0 ){
................................................................................
      }
      nLast++;
      iOffset += szPage;
    }

    rc = sqlite3OsSync(pWal->pWalFd, sync_flags);
  }
  assert( pWal->pWiData==0 );

  /* Append data to the wal-index. It is not necessary to lock the 
  ** wal-index to do this as the SQLITE_SHM_WRITE lock held on the wal-index
  ** guarantees that there are no other writers, and no data that may
  ** be in use by existing readers is being overwritten.
  */
  iFrame = pWal->hdr.mxFrame;
................................................................................
    /* If this is a commit, update the wal-index header too. */
    if( isCommit ){
      walIndexWriteHdr(pWal);
      pWal->iCallback = iFrame;
    }
  }

  walIndexUnmap(pWal);
  WALTRACE(("WAL%p: frame write %s\n", pWal, rc ? "failed" : "ok"));
  return rc;
}

/* 
** This routine is called to implement sqlite3_wal_checkpoint() and
** related interfaces.
................................................................................
  int sync_flags,                 /* Flags to sync db file with (or 0) */
  int nBuf,                       /* Size of temporary buffer */
  u8 *zBuf                        /* Temporary buffer to use */
){
  int rc;                         /* Return code */
  int isChanged = 0;              /* True if a new wal-index header is loaded */

  assert( pWal->pWiData==0 );
  assert( pWal->ckptLock==0 );

  WALTRACE(("WAL%p: checkpoint begins\n", pWal));
  rc = walLockExclusive(pWal, WAL_CKPT_LOCK, 1);
  if( rc ){
    /* Usually this is SQLITE_BUSY meaning that another thread or process
    ** is already running a checkpoint, or maybe a recovery.  But it might
................................................................................
    ** next time the pager opens a snapshot on this database it knows that
    ** the cache needs to be reset.
    */
    memset(&pWal->hdr, 0, sizeof(WalIndexHdr));
  }

  /* Release the locks. */
  walIndexUnmap(pWal);
  walUnlockExclusive(pWal, WAL_CKPT_LOCK, 1);
  pWal->ckptLock = 0;
  WALTRACE(("WAL%p: checkpoint %s\n", pWal, rc ? "failed" : "ok"));
  return rc;
}

/* Return the value to pass to a sqlite3_wal_hook callback, the

** following object.
*/
struct Wal {
  sqlite3_vfs *pVfs;         /* The VFS used to create pDbFd */
  sqlite3_file *pDbFd;       /* File handle for the database file */
  sqlite3_file *pWalFd;      /* File handle for WAL file */
  u32 iCallback;             /* Value to pass to log callback (or 0) */
  int nWiData;               /* Size of array apWiData */
  volatile u32 **apWiData;   /* Pointer to wal-index content in memory */
  u16 szPage;                /* Database page size */
  i16 readLock;              /* Which read lock is being held.  -1 for none */
  u8 exclusiveMode;          /* Non-zero if connection is in exclusive mode */
  u8 isWIndexOpen;           /* True if ShmOpen() called on pDbFd */
  u8 writeLock;              /* True if in a write transaction */
  u8 ckptLock;               /* True if holding a checkpoint lock */
  WalIndexHdr hdr;           /* Wal-index header for current transaction */
  char *zWalName;            /* Name of WAL file */
  u32 nCkpt;                 /* Checkpoint sequence counter in the wal-header */
#ifdef SQLITE_DEBUG
  u8 lockError;              /* True if a locking error has occurred */
#endif
};

/*
** Define the parameters of the hash tables in the wal-index file. There
** is a hash-table following every HASHTABLE_NPAGE page numbers in the
** wal-index.
**
** Changing any of these constants will alter the wal-index format and
** create incompatibilities.
*/
#define HASHTABLE_NPAGE      4096  /* Must be power of 2 and multiple of 256 */
#define HASHTABLE_DATATYPE   u16
#define HASHTABLE_HASH_1     383                  /* Should be prime */
#define HASHTABLE_NSLOT      (HASHTABLE_NPAGE*2)  /* Must be a power of 2 */
#define HASHTABLE_NBYTE      (sizeof(HASHTABLE_DATATYPE)*HASHTABLE_NSLOT)

/* The block of page numbers associated with the first hash-table in a
** wal-index is smaller than usual. This is so that there is a complete
** hash-table on each aligned 32KB page of the wal-index.
*/
#define HASHTABLE_NPAGE_ONE  (4096 - (WALINDEX_HDR_SIZE/sizeof(u32)))

/* The wal-index is divided into pages of HASHTABLE_PAGESIZE bytes each. */
#define HASHTABLE_PAGESIZE   (HASHTABLE_NBYTE + HASHTABLE_NPAGE*sizeof(u32))

/*
** Obtain a pointer to the iPage'th page of the wal-index. The wal-index
** is broken into pages of HASHTABLE_PAGESIZE bytes. Wal-index pages are
** numbered from zero.
**
** If this call is successful, *ppPage is set to point to the wal-index
** page and SQLITE_OK is returned. If an error (an OOM or VFS error) occurs,
** then an SQLite error code is returned and *ppPage is set to 0.
*/
static int walIndexPage(Wal *pWal, int iPage, volatile u32 **ppPage){
  int rc = SQLITE_OK;

  /* Enlarge the pWal->apWiData[] array if required */
  if( pWal->nWiData<=iPage ){
    int nByte = sizeof(u32 *)*(iPage+1);
    volatile u32 **apNew;
    apNew = (volatile u32 **)sqlite3_realloc(pWal->apWiData, nByte);
    if( !apNew ){
      *ppPage = 0;
      return SQLITE_NOMEM;
    }
    memset(&apNew[pWal->nWiData], 0, sizeof(u32 *)*(iPage+1-pWal->nWiData));
    pWal->apWiData = apNew;
    pWal->nWiData = iPage+1;
  }

  /* Request a pointer to the required page from the VFS */
  if( pWal->apWiData[iPage]==0 ){
    rc = sqlite3OsShmPage(pWal->pDbFd, iPage, HASHTABLE_PAGESIZE, 
        pWal->writeLock, (void volatile **)&pWal->apWiData[iPage]
    );
  }

  *ppPage = pWal->apWiData[iPage];
  assert( iPage==0 || *ppPage || rc!=SQLITE_OK );
  return rc;
}

/*
** Return a pointer to the WalCkptInfo structure in the wal-index.
*/
static volatile WalCkptInfo *walCkptInfo(Wal *pWal){
  volatile u32 *page1 = 0;
  walIndexPage(pWal, 0, &page1);
  assert( page1 );
  return (volatile WalCkptInfo*)&page1[sizeof(WalIndexHdr)/2];
}


/*
** This structure is used to implement an iterator that loops through
** all frames in the WAL in database page order. Where two or more frames
** correspond to the same database page, the iterator visits only the 
** frame most recently written to the WAL (in other words, the frame with
** the largest index).
................................................................................
**   walIteratorFree() - Free an iterator.
**
** This functionality is used by the checkpoint code (see walCheckpoint()).
*/
struct WalIterator {
  int iPrior;           /* Last result returned from the iterator */
  int nSegment;         /* Size of the aSegment[] array */

  struct WalSegment {
    int iNext;                    /* Next slot in aIndex[] not yet returned */
    HASHTABLE_DATATYPE *aIndex;   /* i0, i1, i2... such that aPgno[iN] ascend */
    u32 *aPgno;                   /* Array of page numbers. */
    int nEntry;                   /* Max size of aPgno[] and aIndex[] arrays */
    int iZero;                    /* Frame number associated with aPgno[0] */
  } aSegment[1];        /* One for every 32KB page in the WAL */
};

/*
** The argument to this macro must be of type u32. On a little-endian
** architecture, it returns the u32 value that results from interpreting
** the 4 bytes as a big-endian value. On a big-endian architecture, it
** returns the value that would be produced by intepreting the 4 bytes
................................................................................
static void walIndexWriteHdr(Wal *pWal){
  WalIndexHdr *aHdr;

  assert( pWal->writeLock );
  pWal->hdr.isInit = 1;
  walChecksumBytes(1, (u8*)&pWal->hdr, offsetof(WalIndexHdr, aCksum),
                   0, pWal->hdr.aCksum);
  walIndexPage(pWal, 0, (volatile u32 **)&aHdr);
  memcpy(&aHdr[1], &pWal->hdr, sizeof(WalIndexHdr));
  sqlite3OsShmBarrier(pWal->pDbFd);
  memcpy(&aHdr[0], &pWal->hdr, sizeof(WalIndexHdr));
}

/*
** This function encodes a single frame header and writes it to a buffer
................................................................................
  ** and the new database size.
  */
  *piPage = pgno;
  *pnTruncate = sqlite3Get4byte(&aFrame[4]);
  return 1;
}















#if defined(SQLITE_TEST) && defined(SQLITE_DEBUG)
/*
** Names of locks.  This routine is used to provide debugging output and is not
** a part of an ordinary build.
*/
static const char *walLockName(int lockIdx){
................................................................................
  if( pWal->exclusiveMode ) return;
  (void)sqlite3OsShmLock(pWal->pDbFd, lockIdx, n,
                         SQLITE_SHM_UNLOCK | SQLITE_SHM_EXCLUSIVE);
  WALTRACE(("WAL%p: release EXCLUSIVE-%s cnt=%d\n", pWal,
             walLockName(lockIdx), n));
}



























































































/*
** Compute a hash on a page number.  The resulting hash value must land
** between 0 and (HASHTABLE_NSLOT-1).  The walHashNext() function advances
** the hash to the next value in the event of a collision.
*/
static int walHash(u32 iPage){
  assert( iPage>0 );
................................................................................
  assert( (HASHTABLE_NSLOT & (HASHTABLE_NSLOT-1))==0 );
  return (iPage*HASHTABLE_HASH_1) & (HASHTABLE_NSLOT-1);
}
static int walNextHash(int iPriorHash){
  return (iPriorHash+1)&(HASHTABLE_NSLOT-1);
}

static void walHashGet(
  Wal *pWal,                      /* WAL handle */
  int iHash,                      /* Find the iHash'th table */
  volatile HASHTABLE_DATATYPE **paHash,     /* OUT: Pointer to hash index */
  volatile u32 **paPgno,          /* OUT: Pointer to page number array */
  u32 *piZero                     /* OUT: Frame associated with *paPgno[0] */
){
  u32 iZero;
  volatile u32 *aPgno;
  volatile HASHTABLE_DATATYPE *aHash;

  walIndexPage(pWal, iHash, &aPgno);
  aHash = (volatile HASHTABLE_DATATYPE *)&aPgno[HASHTABLE_NPAGE];

  if( iHash==0 ){
    aPgno = &aPgno[WALINDEX_HDR_SIZE/sizeof(u32)-1];
    iZero = 0;
  }else{
    iZero = HASHTABLE_NPAGE_ONE + (iHash-1)*HASHTABLE_NPAGE;
    aPgno = &aPgno[-1*iZero-1];
  }

  *paPgno = aPgno;
  *paHash = aHash;
  *piZero = iZero;
}

static int walFramePage(u32 iFrame){
  int iHash = (iFrame+HASHTABLE_NPAGE-HASHTABLE_NPAGE_ONE-1) / HASHTABLE_NPAGE;
  assert( (iHash==0 || iFrame>HASHTABLE_NPAGE_ONE)
       && (iHash>=1 || iFrame<=HASHTABLE_NPAGE_ONE)
       && (iHash<=1 || iFrame>(HASHTABLE_NPAGE_ONE+HASHTABLE_NPAGE))
       && (iHash>=2 || iFrame<=HASHTABLE_NPAGE_ONE+HASHTABLE_NPAGE)
       && (iHash<=2 || iFrame>(HASHTABLE_NPAGE_ONE+2*HASHTABLE_NPAGE))
  );
  return iHash;
}

/*
** Return the page number associated with frame iFrame in this WAL.
*/
static u32 walFramePgno(Wal *pWal, u32 iFrame){
  int iHash = walFramePage(iFrame);
  if( iHash==0 ){
    return pWal->apWiData[0][WALINDEX_HDR_SIZE/sizeof(u32) + iFrame - 1];
  }
  return pWal->apWiData[iHash][(iFrame-1-HASHTABLE_NPAGE_ONE)%HASHTABLE_NPAGE];
}

/* 
** Find the hash table and (section of the) page number array used to
** store data for WAL frame iFrame.
**
** Set output variable *paHash to point to the start of the hash table
** in the wal-index file. Set *piZero to one less than the frame 
................................................................................
static void walHashFind(
  Wal *pWal,                      /* WAL handle */
  u32 iFrame,                     /* Find the hash table indexing this frame */
  volatile HASHTABLE_DATATYPE **paHash,    /* OUT: Pointer to hash index */
  volatile u32 **paPgno,          /* OUT: Pointer to page number array */
  u32 *piZero                     /* OUT: Frame associated with *paPgno[0] */
){
  int iHash = walFramePage(iFrame);
  walHashGet(pWal, iHash, paHash, paPgno, piZero);



















}

/*
** Remove entries from the hash table that point to WAL slots greater
** than pWal->hdr.mxFrame.
**
** This function is called whenever pWal->hdr.mxFrame is decreased due
................................................................................
** actually needed.
*/
static void walCleanupHash(Wal *pWal){
  volatile HASHTABLE_DATATYPE *aHash;  /* Pointer to hash table to clear */
  volatile u32 *aPgno;                 /* Unused return from walHashFind() */
  u32 iZero;                           /* frame == (aHash[x]+iZero) */
  int iLimit = 0;                      /* Zero values greater than this */
  int nByte;                           /* Number of bytes to zero in aPgno[] */
  int i;                               /* Used to iterate through aHash[] */

  assert( pWal->writeLock );
  testcase( pWal->hdr.mxFrame==HASHTABLE_NPAGE-1 );
  testcase( pWal->hdr.mxFrame==HASHTABLE_NPAGE );
  testcase( pWal->hdr.mxFrame==HASHTABLE_NPAGE+1 );




  walHashFind(pWal, pWal->hdr.mxFrame+1, &aHash, &aPgno, &iZero);
  if( iZero!=pWal->hdr.mxFrame ){
    iLimit = pWal->hdr.mxFrame - iZero;
    assert( iLimit>0 );
    for(i=0; i<HASHTABLE_NSLOT; i++){
      if( aHash[i]>iLimit ){
        aHash[i] = 0;
      }
    }
  
    /* Zero the entries in the aPgno array that correspond to frames with
    ** frame numbers greater than pWal->hdr.mxFrame. 
    */
    nByte = ((char *)aHash - (char *)&aPgno[pWal->hdr.mxFrame+1]);
    memset((void *)&aPgno[pWal->hdr.mxFrame+1], 0, nByte);

  }

#ifdef SQLITE_ENABLE_EXPENSIVE_ASSERT
  /* Verify that the every entry in the mapping region is still reachable
  ** via the hash table even after the cleanup.
  */
  if( iLimit ){
................................................................................


/*
** Set an entry in the wal-index that will map database page number
** pPage into WAL frame iFrame.
*/
static int walIndexAppend(Wal *pWal, u32 iFrame, u32 iPage){
  int rc = SQLITE_OK;             /* Return code */









  /* Assuming the wal-index file was successfully mapped, find the hash 
  ** table and section of of the page number array that pertain to frame 
  ** iFrame of the WAL. Then populate the page number array and the hash 
  ** table entry.
  */
  if( rc==SQLITE_OK ){
................................................................................
    volatile HASHTABLE_DATATYPE *aHash;  /* Hash table */
    int idx;                             /* Value to write to hash-table slot */
    TESTONLY( int nCollide = 0;          /* Number of hash collisions */ )

    walHashFind(pWal, iFrame, &aHash, &aPgno, &iZero);
    idx = iFrame - iZero;
    if( idx==1 ){
      int nByte = (u8 *)&aHash[HASHTABLE_NSLOT] - (u8 *)&aPgno[1+iZero];
      memset((void*)&aPgno[1+iZero], 0, nByte);
    }
    assert( idx <= HASHTABLE_NSLOT/2 + 1 );

    if( aPgno[iFrame] ){
      /* If the entry in aPgno[] is already set, then the previous writer
      ** must have exited unexpectedly in the middle of a transaction (after
      ** writing one or more dirty pages to the WAL to free up memory). 
................................................................................
      }
    }

    sqlite3_free(aFrame);
  }

finished:



  if( rc==SQLITE_OK ){
    volatile WalCkptInfo *pInfo;
    int i;
    pWal->hdr.aFrameCksum[0] = aFrameCksum[0];
    pWal->hdr.aFrameCksum[1] = aFrameCksum[1];
    walIndexWriteHdr(pWal);

................................................................................
  if( !pRet ){
    return SQLITE_NOMEM;
  }

  pRet->pVfs = pVfs;
  pRet->pWalFd = (sqlite3_file *)&pRet[1];
  pRet->pDbFd = pDbFd;

  pRet->readLock = -1;
  sqlite3_randomness(8, &pRet->hdr.aSalt);
  pRet->zWalName = zWal = pVfs->szOsFile + (char*)pRet->pWalFd;
  sqlite3_snprintf(nWal, zWal, "%s-wal", zDbName);
  rc = sqlite3OsShmOpen(pDbFd);

  /* Open file handle on the write-ahead log file. */
................................................................................
  WalIterator *p,               /* Iterator */
  u32 *piPage,                  /* OUT: The page number of the next page */
  u32 *piFrame                  /* OUT: Wal frame index of next page */
){
  u32 iMin;                     /* Result pgno must be greater than iMin */
  u32 iRet = 0xFFFFFFFF;        /* 0xffffffff is never a valid page number */
  int i;                        /* For looping through segments */


  iMin = p->iPrior;
  assert( iMin<0xffffffff );
  for(i=p->nSegment-1; i>=0; i--){
    struct WalSegment *pSegment = &p->aSegment[i];
    while( pSegment->iNext<pSegment->nEntry ){
      u32 iPg = pSegment->aPgno[pSegment->aIndex[pSegment->iNext]];
      if( iPg>iMin ){
        if( iPg<iRet ){
          iRet = iPg;
          *piFrame = pSegment->iZero + pSegment->aIndex[pSegment->iNext];
        }
        break;
      }
      pSegment->iNext++;
    }

  }

  *piPage = p->iPrior = iRet;
  return (iRet==0xFFFFFFFF);
}


static void walMergesort(
  u32 *aContent,                  /* Pages in wal */
  HASHTABLE_DATATYPE *aBuffer,    /* Buffer of at least *pnList items to use */
  HASHTABLE_DATATYPE *aList,      /* IN/OUT: List to sort */
  int *pnList                     /* IN/OUT: Number of elements in aList[] */
){
  int nList = *pnList;
  if( nList>1 ){
    int nLeft = nList / 2;        /* Elements in left list */
    int nRight = nList - nLeft;   /* Elements in right list */


    int iLeft = 0;                /* Current index in aLeft */
    int iRight = 0;               /* Current index in aright */
    int iOut = 0;                 /* Current index in output buffer */
    HASHTABLE_DATATYPE *aLeft = aList;           /* Left list */
    HASHTABLE_DATATYPE *aRight = &aList[nLeft];  /* Right list */

    /* TODO: Change to non-recursive version. */
    walMergesort(aContent, aBuffer, aLeft, &nLeft);
    walMergesort(aContent, aBuffer, aRight, &nRight);

    while( iRight<nRight || iLeft<nLeft ){
      HASHTABLE_DATATYPE logpage;
      Pgno dbpage;

      if( (iLeft<nLeft) 
       && (iRight>=nRight || aContent[aLeft[iLeft]]<aContent[aRight[iRight]])
      ){
        logpage = aLeft[iLeft++];
      }else{
................................................................................
**
** The calling routine should invoke walIteratorFree() to destroy the
** WalIterator object when it has finished with it.  The caller must
** also unmap the wal-index.  But the wal-index must not be unmapped
** prior to the WalIterator object being destroyed.
*/
static int walIteratorInit(Wal *pWal, WalIterator **pp){

  WalIterator *p;       /* Return value */
  int nSegment;         /* Number of segments to merge */
  u32 iLast;            /* Last frame in log */
  int nByte;            /* Number of bytes to allocate */
  int i;                /* Iterator variable */

  HASHTABLE_DATATYPE *aTmp;       /* Temp space used by merge-sort */
  HASHTABLE_DATATYPE *aSpace;     /* Space at the end of the allocation */




  /* This routine only runs while holding SQLITE_SHM_CHECKPOINT.  No other
  ** thread is able to write to shared memory while this routine is
  ** running (or, indeed, while the WalIterator object exists).  Hence,
  ** we can cast off the volatile qualification from shared memory
  */
  assert( pWal->ckptLock );
  iLast = pWal->hdr.mxFrame;

  /* Allocate space for the WalIterator object */
  nSegment = walFramePage(iLast) + 1;
  nByte = sizeof(WalIterator) 

        + nSegment*(sizeof(struct WalSegment))
        + (nSegment+1)*(HASHTABLE_NPAGE * sizeof(HASHTABLE_DATATYPE));
  p = (WalIterator *)sqlite3_malloc(nByte);
  if( !p ){
    return SQLITE_NOMEM;
  }
  memset(p, 0, nByte);

  /* Allocate space for the WalIterator object */



  p->nSegment = nSegment;
  aSpace = (HASHTABLE_DATATYPE *)&p->aSegment[nSegment];
  aTmp = &aSpace[HASHTABLE_NPAGE*nSegment];
  for(i=0; i<nSegment; i++){
    volatile HASHTABLE_DATATYPE *pDummy;
    int j;
    u32 iZero;
    int nEntry;
    volatile u32 *aPgno;

    walHashGet(pWal, i, &pDummy, &aPgno, &iZero);
    if( i==(nSegment-1) ){


      nEntry = iLast - iZero;
    }else if( i==0 ){
      nEntry = HASHTABLE_NPAGE_ONE;
    }else{
      nEntry = HASHTABLE_NPAGE;
    }
    iZero++;
    aPgno += iZero;

    for(j=0; j<nEntry; j++){
      aSpace[j] = j;
    }
    walMergesort((u32 *)aPgno, aTmp, aSpace, &nEntry);
    p->aSegment[i].iZero = iZero;
    p->aSegment[i].nEntry = nEntry;
    p->aSegment[i].aIndex = aSpace;
    p->aSegment[i].aPgno = (u32 *)aPgno;

    aSpace += HASHTABLE_NPAGE;

  }
  assert( aSpace==aTmp );

  /* Return the fully initialized WalIterator object */
  *pp = p;
  return SQLITE_OK ;
}

/* 
** Free an iterator allocated by walIteratorInit().
*/
................................................................................

  /* Compute in mxSafeFrame the index of the last frame of the WAL that is
  ** safe to write into the database.  Frames beyond mxSafeFrame might
  ** overwrite database pages that are in use by active readers and thus
  ** cannot be backfilled from the WAL.
  */
  mxSafeFrame = pWal->hdr.mxFrame;
  walIndexPage(pWal, 0, (volatile u32 **)&pHdr);
  pInfo = walCkptInfo(pWal);
  assert( pInfo==walCkptInfo(pWal) );
  for(i=1; i<WAL_NREADER; i++){
    u32 y = pInfo->aReadMark[i];
    if( mxSafeFrame>=y ){
      assert( y<=pWal->hdr.mxFrame );
      rc = walLockExclusive(pWal, WAL_READ_LOCK(i), 1);
      if( rc==SQLITE_OK ){
................................................................................
    /* Sync the WAL to disk */
    if( sync_flags ){
      rc = sqlite3OsSync(pWal->pWalFd, sync_flags);
    }

    /* Iterate through the contents of the WAL, copying data to the db file. */
    while( rc==SQLITE_OK && 0==walIteratorNext(pIter, &iDbpage, &iFrame) ){
      assert( walFramePgno(pWal, iFrame)==iDbpage );
      if( iFrame<=nBackfill || iFrame>mxSafeFrame ) continue;
      rc = sqlite3OsRead(pWal->pWalFd, zBuf, szPage, 
          walFrameOffset(iFrame, szPage) + WAL_FRAME_HDRSIZE
      );
      if( rc!=SQLITE_OK ) break;
      rc = sqlite3OsWrite(pWal->pDbFd, zBuf, szPage, (iDbpage-1)*szPage);
      if( rc!=SQLITE_OK ) break;
................................................................................
    rc = sqlite3OsLock(pWal->pDbFd, SQLITE_LOCK_EXCLUSIVE);
    if( rc==SQLITE_OK ){
      pWal->exclusiveMode = 1;
      rc = sqlite3WalCheckpoint(pWal, sync_flags, nBuf, zBuf);
      if( rc==SQLITE_OK ){
        isDelete = 1;
      }

    }

    walIndexClose(pWal, isDelete);
    sqlite3OsClose(pWal->pWalFd);
    if( isDelete ){
      sqlite3OsDelete(pWal->pVfs, pWal->zWalName, 0);
    }
    WALTRACE(("WAL%p: closed\n", pWal));
    sqlite3_free(pWal->apWiData);
    sqlite3_free(pWal);
  }
  return rc;
}

/*
** Try to read the wal-index header.  Return 0 on success and 1 if
................................................................................
** If the checksum cannot be verified return non-zero. If the header
** is read successfully and the checksum verified, return zero.
*/
int walIndexTryHdr(Wal *pWal, int *pChanged){
  u32 aCksum[2];               /* Checksum on the header content */
  WalIndexHdr h1, h2;          /* Two copies of the header content */
  WalIndexHdr *aHdr;           /* Header in shared memory */
  volatile u32 *page1 = 0;


  walIndexPage(pWal, 0, &page1);
  if( !page1 ){
    /* The wal-index is not large enough to hold the header, then assume
    ** header is invalid. */
    return 1;
  }


  /* Read the header. This might happen currently with a write to the
  ** same area of shared memory on a different CPU in a SMP,
  ** meaning it is possible that an inconsistent snapshot is read
  ** from the file. If this happens, return non-zero.
  **
  ** There are two copies of the header at the beginning of the wal-index.
  ** When reading, read [0] first then [1].  Writes are in the reverse order.
  ** Memory barriers are used to prevent the compiler or the hardware from
  ** reordering the reads and writes.
  */
  aHdr = (WalIndexHdr*)page1;
  memcpy(&h1, &aHdr[0], sizeof(h1));
  sqlite3OsShmBarrier(pWal->pDbFd);
  memcpy(&h2, &aHdr[1], sizeof(h2));

  if( memcmp(&h1, &h2, sizeof(h1))!=0 ){
    return 1;   /* Dirty read */
  }  
................................................................................
**
** If the wal-index header is successfully read, return SQLITE_OK. 
** Otherwise an SQLite error code.
*/
static int walIndexReadHdr(Wal *pWal, int *pChanged){
  int rc;                         /* Return code */
  int badHdr;                     /* True if a header read failed */
  volatile u32 *dummy;

  assert( pChanged );

  rc = walIndexPage(pWal, 0, &dummy);
  if( rc!=SQLITE_OK ){
    return rc;
  }

  /* Try once to read the header straight out.  This works most of the
  ** time.
  */
................................................................................
        *pChanged = 1;
      }
      walUnlockExclusive(pWal, WAL_WRITE_LOCK, 1);
      pWal->writeLock = 0;
    }
  }









  return rc;
}

/*
** This is the value that walTryBeginRead returns when it needs to
** be retried.
*/
................................................................................
*/
static int walTryBeginRead(Wal *pWal, int *pChanged, int useWal, int cnt){
  volatile WalIndexHdr *pHdr;     /* Header of the wal-index */
  volatile WalCkptInfo *pInfo;    /* Checkpoint information in wal-index */
  u32 mxReadMark;                 /* Largest aReadMark[] value */
  int mxI;                        /* Index of largest aReadMark[] value */
  int i;                          /* Loop counter */
  int rc = SQLITE_OK;             /* Return code  */

  assert( pWal->readLock<0 );     /* Not currently locked */

  /* Take steps to avoid spinning forever if there is a protocol error. */
  if( cnt>5 ){
    if( cnt>100 ) return SQLITE_PROTOCOL;
    sqlite3OsSleep(pWal->pVfs, 1);
................................................................................
      if( rc==SQLITE_OK ){
        walUnlockShared(pWal, WAL_RECOVER_LOCK);
        rc = WAL_RETRY;
      }else if( rc==SQLITE_BUSY ){
        rc = SQLITE_BUSY_RECOVERY;
      }
    }


  }
  if( rc!=SQLITE_OK ){
    return rc;
  }

  walIndexPage(pWal, 0, (volatile u32 **)&pHdr);
  pInfo = walCkptInfo(pWal);
  assert( pInfo==(volatile WalCkptInfo *)&pHdr[2] );
  if( !useWal && pInfo->nBackfill==pWal->hdr.mxFrame ){
    /* The WAL has been completely backfilled (or it is empty).
    ** and can be safely ignored.
    */
    rc = walLockShared(pWal, WAL_READ_LOCK(0));
    sqlite3OsShmBarrier(pWal->pDbFd);
    if( rc==SQLITE_OK ){
................................................................................
int sqlite3WalBeginReadTransaction(Wal *pWal, int *pChanged){
  int rc;                         /* Return code */
  int cnt = 0;                    /* Number of TryBeginRead attempts */

  do{
    rc = walTryBeginRead(pWal, pChanged, 0, ++cnt);
  }while( rc==WAL_RETRY );

  return rc;
}

/*
** Finish with a read transaction.  All this does is release the
** read-lock.
*/
................................................................................
int sqlite3WalRead(
  Wal *pWal,                      /* WAL handle */
  Pgno pgno,                      /* Database page number to read data for */
  int *pInWal,                    /* OUT: True if data is read from WAL */
  int nOut,                       /* Size of buffer pOut in bytes */
  u8 *pOut                        /* Buffer to write page data to */
){

  u32 iRead = 0;                  /* If !=0, WAL frame to return data from */
  u32 iLast = pWal->hdr.mxFrame;  /* Last page in WAL for this reader */
  int iHash;                      /* Used to loop through N hash tables */

  /* This routine is only be called from within a read transaction. */
  assert( pWal->readLock>=0 || pWal->lockError );

................................................................................
  ** return early, as if the WAL were empty.
  */
  if( iLast==0 || pWal->readLock==0 ){
    *pInWal = 0;
    return SQLITE_OK;
  }







  /* Search the hash table or tables for an entry matching page number
  ** pgno. Each iteration of the following for() loop searches one
  ** hash table (each hash table indexes up to HASHTABLE_NPAGE frames).
  **
  ** This code may run concurrently to the code in walIndexAppend()
  ** that adds entries to the wal-index (and possibly to this hash 
  ** table). This means the value just read from the hash 
................................................................................
  **   (aPgno[iFrame]==pgno): 
  **     This condition filters out normal hash-table collisions.
  **
  **   (iFrame<=iLast): 
  **     This condition filters out entries that were added to the hash
  **     table after the current read-transaction had started.
  */
  for(iHash=walFramePage(iLast); iHash>=0 && iRead==0; iHash--){
    volatile HASHTABLE_DATATYPE *aHash;  /* Pointer to hash table */
    volatile u32 *aPgno;                 /* Pointer to array of page numbers */
    u32 iZero;                    /* Frame number corresponding to aPgno[0] */
    int iKey;                     /* Hash slot index */


    walHashGet(pWal, iHash, &aHash, &aPgno, &iZero);


    for(iKey=walHash(pgno); aHash[iKey]; iKey=walNextHash(iKey)){
      u32 iFrame = aHash[iKey] + iZero;
      if( iFrame<=iLast && aPgno[iFrame]==pgno ){
        assert( iFrame>iRead );
        iRead = iFrame;
      }
    }
  }


#ifdef SQLITE_ENABLE_EXPENSIVE_ASSERT
  /* If expensive assert() statements are available, do a linear search
  ** of the wal-index file content. Make sure the results agree with the
  ** result obtained using the hash indexes above.  */
  {
    u32 iRead2 = 0;
    u32 iTest;
    for(iTest=iLast; iTest>0; iTest--){
      if( walFramePgno(pWal, iTest)==pgno ){
        iRead2 = iTest;
        break;
      }
    }
    assert( iRead==iRead2 );
  }
#endif

  /* If iRead is non-zero, then it is the log frame number that contains the
  ** required page. Read and return data from the log file.
  */

  if( iRead ){
    i64 iOffset = walFrameOffset(iRead, pWal->hdr.szPage) + WAL_FRAME_HDRSIZE;
    *pInWal = 1;
    return sqlite3OsRead(pWal->pWalFd, pOut, nOut, iOffset);
  }

  *pInWal = 0;
................................................................................
** thread to write as doing so would cause a fork.  So this routine
** returns SQLITE_BUSY in that case and no write transaction is started.
**
** There can only be a single writer active at a time.
*/
int sqlite3WalBeginWriteTransaction(Wal *pWal){
  int rc;
  volatile u32 *page1;

  /* Cannot start a write transaction without first holding a read
  ** transaction. */
  assert( pWal->readLock>=0 );

  /* Only one writer allowed at a time.  Get the write lock.  Return
  ** SQLITE_BUSY if unable.
................................................................................
  }
  pWal->writeLock = 1;

  /* If another connection has written to the database file since the
  ** time the read transaction on this connection was started, then
  ** the write is disallowed.
  */
  walIndexPage(pWal, 0, &page1);





  if( memcmp(&pWal->hdr, (void*)page1, sizeof(WalIndexHdr))!=0 ){
    walUnlockExclusive(pWal, WAL_WRITE_LOCK, 1);
    pWal->writeLock = 0;
    rc = SQLITE_BUSY;
  }


  return rc;
}

/*
** End a write transaction.  The commit has already been done.  This
** routine merely releases the lock.
*/
................................................................................
int sqlite3WalUndo(Wal *pWal, int (*xUndo)(void *, Pgno), void *pUndoCtx){
  int rc = SQLITE_OK;
  if( pWal->writeLock ){
    int unused;
    Pgno iMax = pWal->hdr.mxFrame;
    Pgno iFrame;
  

    rc = walIndexReadHdr(pWal, &unused);



    if( rc==SQLITE_OK ){
      for(iFrame=pWal->hdr.mxFrame+1; 
          ALWAYS(rc==SQLITE_OK) && iFrame<=iMax; 
          iFrame++
      ){
        /* This call cannot fail. Unless the page for which the page number
        ** is passed as the second argument is (a) in the cache and 
................................................................................
        **
        ** If the upper layer is doing a rollback, it is guaranteed that there
        ** are no outstanding references to any page other than page 1. And
        ** page 1 is never written to the log until the transaction is
        ** committed. As a result, the call to xUndo may not fail.
        */
        assert( pWal->writeLock );
        assert( walFramePgno(pWal, iFrame)!=1 );
        rc = xUndo(pUndoCtx, walFramePgno(pWal, iFrame));
      }
      walCleanupHash(pWal);
    }

  }
  return rc;
}

/* 
** Argument aWalData must point to an array of WAL_SAVEPOINT_NDATA u32 
** values. This function populates the array with values required to 
................................................................................
    ** to the start of the log. Update the savepoint values to match.
    */
    aWalData[0] = 0;
    aWalData[3] = pWal->nCkpt;
  }

  if( aWalData[0]<pWal->hdr.mxFrame ){

    pWal->hdr.mxFrame = aWalData[0];
    pWal->hdr.aFrameCksum[0] = aWalData[1];
    pWal->hdr.aFrameCksum[1] = aWalData[2];
    if( rc==SQLITE_OK ){
      walCleanupHash(pWal);
    }
  }


  return rc;
}

/*
** This function is called just before writing a set of frames to the log
** file (see sqlite3WalFrames()). It checks to see if, instead of appending
** to the current log file, it is possible to overwrite the start of the
................................................................................
** or not pWal->hdr.mxFrame is modified). An SQLite error code is returned
** if some error 
*/
static int walRestartLog(Wal *pWal){
  int rc = SQLITE_OK;
  int cnt;

  if( pWal->readLock==0 ){


    volatile WalCkptInfo *pInfo = walCkptInfo(pWal);
    assert( pInfo->nBackfill==pWal->hdr.mxFrame );
    if( pInfo->nBackfill>0 ){
      rc = walLockExclusive(pWal, WAL_READ_LOCK(1), WAL_NREADER-1);
      if( rc==SQLITE_OK ){
        /* If all readers are using WAL_READ_LOCK(0) (in other words if no
        ** readers are currently using the WAL), then the transactions
................................................................................
    walUnlockShared(pWal, WAL_READ_LOCK(0));
    pWal->readLock = -1;
    cnt = 0;
    do{
      int notUsed;
      rc = walTryBeginRead(pWal, &notUsed, 1, ++cnt);
    }while( rc==WAL_RETRY );





  }
  return rc;
}

/* 
** Write a set of frames to the log. The caller must hold the write-lock
** on the log file (obtained using sqlite3WalBeginWriteTransaction()).
................................................................................
  u8 aFrame[WAL_FRAME_HDRSIZE];   /* Buffer to assemble frame-header in */
  PgHdr *p;                       /* Iterator to run through pList with. */
  PgHdr *pLast = 0;               /* Last frame in list */
  int nLast = 0;                  /* Number of extra copies of last page */

  assert( pList );
  assert( pWal->writeLock );


#if defined(SQLITE_TEST) && defined(SQLITE_DEBUG)
  { int cnt; for(cnt=0, p=pList; p; p=p->pDirty, cnt++){}
    WALTRACE(("WAL%p: frame write begin. %d frames. mxFrame=%d. %s\n",
              pWal, cnt, pWal->hdr.mxFrame, isCommit ? "Commit" : "Spill"));
  }
#endif

  /* See if it is possible to write these frames into the start of the
  ** log file, instead of appending to it at pWal->hdr.mxFrame.
  */
  if( SQLITE_OK!=(rc = walRestartLog(pWal)) ){

    return rc;
  }


  /* If this is the first frame written into the log, write the WAL
  ** header to the start of the WAL file. See comments at the top of
  ** this source file for a description of the WAL header format.
  */
  iFrame = pWal->hdr.mxFrame;
  if( iFrame==0 ){
................................................................................
      }
      nLast++;
      iOffset += szPage;
    }

    rc = sqlite3OsSync(pWal->pWalFd, sync_flags);
  }


  /* Append data to the wal-index. It is not necessary to lock the 
  ** wal-index to do this as the SQLITE_SHM_WRITE lock held on the wal-index
  ** guarantees that there are no other writers, and no data that may
  ** be in use by existing readers is being overwritten.
  */
  iFrame = pWal->hdr.mxFrame;
................................................................................
    /* If this is a commit, update the wal-index header too. */
    if( isCommit ){
      walIndexWriteHdr(pWal);
      pWal->iCallback = iFrame;
    }
  }


  WALTRACE(("WAL%p: frame write %s\n", pWal, rc ? "failed" : "ok"));
  return rc;
}

/* 
** This routine is called to implement sqlite3_wal_checkpoint() and
** related interfaces.
................................................................................
  int sync_flags,                 /* Flags to sync db file with (or 0) */
  int nBuf,                       /* Size of temporary buffer */
  u8 *zBuf                        /* Temporary buffer to use */
){
  int rc;                         /* Return code */
  int isChanged = 0;              /* True if a new wal-index header is loaded */


  assert( pWal->ckptLock==0 );

  WALTRACE(("WAL%p: checkpoint begins\n", pWal));
  rc = walLockExclusive(pWal, WAL_CKPT_LOCK, 1);
  if( rc ){
    /* Usually this is SQLITE_BUSY meaning that another thread or process
    ** is already running a checkpoint, or maybe a recovery.  But it might
................................................................................
    ** next time the pager opens a snapshot on this database it knows that
    ** the cache needs to be reset.
    */
    memset(&pWal->hdr, 0, sizeof(WalIndexHdr));
  }

  /* Release the locks. */

  walUnlockExclusive(pWal, WAL_CKPT_LOCK, 1);
  pWal->ckptLock = 0;
  WALTRACE(("WAL%p: checkpoint %s\n", pWal, rc ? "failed" : "ok"));
  return rc;
}

/* Return the value to pass to a sqlite3_wal_hook callback, the

#
#***********************************************************************
#
# $Id: permutations.test,v 1.51 2009/07/01 18:09:02 danielk1977 Exp $

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


# Argument processing.
#
#puts "PERM-DEBUG: argv=$argv"
namespace eval ::perm {
  variable testmode [lindex $::argv 0]
  variable testfile [lindex $::argv 1]

#
#***********************************************************************
#
# $Id: permutations.test,v 1.51 2009/07/01 18:09:02 danielk1977 Exp $

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

# Argument processing.
#
#puts "PERM-DEBUG: argv=$argv"
namespace eval ::perm {
  variable testmode [lindex $::argv 0]
  variable testfile [lindex $::argv 1]

#      of the the integer fields (so that the reader ends up with a corrupted
#      header).
#
#   3. Check that the reader recovers the wal-index and reads the correct
#      database content.
#
do_test wal2-1.0 {


  proc tvfs_cb {method args} { return SQLITE_OK }


  testvfs tvfs
  tvfs script tvfs_cb


  sqlite3 db  test.db -vfs tvfs
  sqlite3 db2 test.db -vfs tvfs

  execsql {
    PRAGMA journal_mode = WAL;
    CREATE TABLE t1(a);
................................................................................
        10   13   {13 91}   8             {$RECOVER $READ}
        11   14   {14 105}  9             {$RECOVER $READ}
        12   15   {15 120}  -1            {$READ}
" {

  do_test wal2-1.$tn.1 {
    execsql { INSERT INTO t1 VALUES($iInsert) }

    set ::locks [list]
    set ::cb_done 0

    proc tvfs_cb {method args} {
      if {$::cb_done == 0 && $method == "xShmGet"} {
        set ::cb_done 1
        if {$::wal_index_hdr_mod >= 0} {
          incr_tvfs_hdr [lindex $args 0] $::wal_index_hdr_mod 1
        }
      }
      if {$method == "xShmLock"} { lappend ::locks [lindex $args 2] }
      return SQLITE_OK
    }




    execsql { SELECT count(a), sum(a) FROM t1 } db2
  } $res

  do_test wal2-1.$tn.2 {
    set ::locks
  } $wal_locks
}
................................................................................
  {4 1 lock exclusive} {4 1 unlock exclusive} \
  {4 1 lock shared}    {4 1 unlock shared}    \
]
do_test wal2-2.0 {

  testvfs tvfs
  tvfs script tvfs_cb

  proc tvfs_cb {method args} {
    if {$method == "xShmOpen"} { set ::shm_file [lindex $args 0] }

    return SQLITE_OK
  }

  sqlite3 db  test.db -vfs tvfs
  sqlite3 db2 test.db -vfs tvfs

  execsql {
................................................................................
         4    7   {6 21}   {7 28}    2
         5    8   {7 28}   {8 36}    3
         6    9   {8 36}   {9 45}    4
         7   10   {9 45}   {10 55}   5
         8   11   {10 55}  {11 66}   6
         9   12   {11 66}  {12 78}   7
} {


  do_test wal2-2.$tn.1 {
    set oldhdr [set_tvfs_hdr $::shm_file]
    execsql { INSERT INTO t1 VALUES($iInsert) }
    execsql { SELECT count(a), sum(a) FROM t1 }
  } $res1

  do_test wal2-2.$tn.2 {
    set ::locks [list]
    set ::cb_done 0
    proc tvfs_cb {method args} {
      if {$::cb_done == 0 && $method == "xShmGet"} {
        set ::cb_done 1
        if {$::wal_index_hdr_mod >= 0} {
          incr_tvfs_hdr $::shm_file $::wal_index_hdr_mod 1
        }
      }
      if {$method == "xShmLock"} {
        set lock [lindex $args 2]
        lappend ::locks $lock
        if {$lock == $::WRITER} {
          set_tvfs_hdr $::shm_file $::oldhdr
        }
      }
      return SQLITE_OK
    }




    execsql { SELECT count(a), sum(a) FROM t1 } db2
  } $res0

  do_test wal2-2.$tn.3 {
    set ::locks
  } $LOCKS

  do_test wal2-2.$tn.4 {
    set ::locks [list]
    set ::cb_done 0
    proc tvfs_cb {method args} {
      if {$::cb_done == 0 && $method == "xShmGet"} {
        set ::cb_done 1
        if {$::wal_index_hdr_mod >= 0} {
          incr_tvfs_hdr $::shm_file $::wal_index_hdr_mod 1
        }
      }
      if {$method == "xShmLock"} {
        set lock [lindex $args 2]
        lappend ::locks $lock
      }
      return SQLITE_OK
    }




    execsql { SELECT count(a), sum(a) FROM t1 } db2
  } $res1
}
db close
db2 close
tvfs delete
file delete -force test.db test.db-wal test.db-journal

#      of the the integer fields (so that the reader ends up with a corrupted
#      header).
#
#   3. Check that the reader recovers the wal-index and reads the correct
#      database content.
#
do_test wal2-1.0 {
  proc tvfs_cb {method filename args} { 
    set ::filename $filename
    return SQLITE_OK 
  }

  testvfs tvfs
  tvfs script tvfs_cb
  tvfs filter xShmOpen

  sqlite3 db  test.db -vfs tvfs
  sqlite3 db2 test.db -vfs tvfs

  execsql {
    PRAGMA journal_mode = WAL;
    CREATE TABLE t1(a);
................................................................................
        10   13   {13 91}   8             {$RECOVER $READ}
        11   14   {14 105}  9             {$RECOVER $READ}
        12   15   {15 120}  -1            {$READ}
" {

  do_test wal2-1.$tn.1 {
    execsql { INSERT INTO t1 VALUES($iInsert) }

    set ::locks [list]


    proc tvfs_cb {method args} {






      lappend ::locks [lindex $args 2]
      return SQLITE_OK
    }
    tvfs filter xShmLock
    if {$::wal_index_hdr_mod >= 0} {
      incr_tvfs_hdr $::filename $::wal_index_hdr_mod 1
    }
    execsql { SELECT count(a), sum(a) FROM t1 } db2
  } $res

  do_test wal2-1.$tn.2 {
    set ::locks
  } $wal_locks
}
................................................................................
  {4 1 lock exclusive} {4 1 unlock exclusive} \
  {4 1 lock shared}    {4 1 unlock shared}    \
]
do_test wal2-2.0 {

  testvfs tvfs
  tvfs script tvfs_cb
  tvfs filter xShmOpen
  proc tvfs_cb {method args} {

    set ::filename [lindex $args 0]
    return SQLITE_OK
  }

  sqlite3 db  test.db -vfs tvfs
  sqlite3 db2 test.db -vfs tvfs

  execsql {
................................................................................
         4    7   {6 21}   {7 28}    2
         5    8   {7 28}   {8 36}    3
         6    9   {8 36}   {9 45}    4
         7   10   {9 45}   {10 55}   5
         8   11   {10 55}  {11 66}   6
         9   12   {11 66}  {12 78}   7
} {
  tvfs filter xShmLock

  do_test wal2-2.$tn.1 {
    set oldhdr [set_tvfs_hdr $::filename]
    execsql { INSERT INTO t1 VALUES($iInsert) }
    execsql { SELECT count(a), sum(a) FROM t1 }
  } $res1

  do_test wal2-2.$tn.2 {
    set ::locks [list]

    proc tvfs_cb {method args} {







      set lock [lindex $args 2]
      lappend ::locks $lock
      if {$lock == $::WRITER} {
        set_tvfs_hdr $::filename $::oldhdr

      }
      return SQLITE_OK
    }

    if {$::wal_index_hdr_mod >= 0} {
      incr_tvfs_hdr $::filename $::wal_index_hdr_mod 1
    }
    execsql { SELECT count(a), sum(a) FROM t1 } db2
  } $res0

  do_test wal2-2.$tn.3 {
    set ::locks
  } $LOCKS

  do_test wal2-2.$tn.4 {
    set ::locks [list]

    proc tvfs_cb {method args} {







      set lock [lindex $args 2]
      lappend ::locks $lock

      return SQLITE_OK
    }

    if {$::wal_index_hdr_mod >= 0} {
      incr_tvfs_hdr $::filename $::wal_index_hdr_mod 1
    }
    execsql { SELECT count(a), sum(a) FROM t1 } db2
  } $res1
}
db close
db2 close
tvfs delete
file delete -force test.db test.db-wal test.db-journal

testvfs T -default 1
T script method_callback

proc method_callback {method args} {
  if {$method == "xShmBarrier"} {
    incr ::barrier_count
    if {$::barrier_count == 1} {
      # This code is executed within the xShmBarrier() callback invoked
      # by the client running recovery as part of writing the recovered
      # wal-index header. If a second client attempts to access the 
      # database now, it reads a corrupt (partially written) wal-index
      # header. But it cannot even get that far, as the first client
      # is still holding all the locks (recovery takes an exclusive lock
      # on *all* db locks, preventing access by any other client).

testvfs T -default 1
T script method_callback

proc method_callback {method args} {
  if {$method == "xShmBarrier"} {
    incr ::barrier_count
    if {$::barrier_count == 2} {
      # This code is executed within the xShmBarrier() callback invoked
      # by the client running recovery as part of writing the recovered
      # wal-index header. If a second client attempts to access the 
      # database now, it reads a corrupt (partially written) wal-index
      # header. But it cannot even get that far, as the first client
      # is still holding all the locks (recovery takes an exclusive lock
      # on *all* db locks, preventing access by any other client).