/*
** End of utility interface.
*************************************************************************/

#ifdef NDEBUG
# define sqlite4BtDebugReadPage(a,b,c,d)


# define btErrorBkpt(x) x
#else
void sqlite4BtDebugReadPage(BtLock *pLock, u32 pgno, u8 *aData, int pgsz);


int btErrorBkpt(int rc);
#endif

/*
** End of utility interface.
*************************************************************************/

#ifdef NDEBUG
# define sqlite4BtDebugReadPage(a,b,c,d)
# define sqlite4BtDebugKV(a,b,c,d,e,f)
# define sqlite4BtDebugReadlock(a,b,c)
# define btErrorBkpt(x) x
#else
void sqlite4BtDebugReadPage(BtLock *pLock, u32 pgno, u8 *aData, int pgsz);
void sqlite4BtDebugKV(BtLock*, const char*,u8 *pK, int nK, u8 *pV, int nV);
void sqlite4BtDebugReadlock(BtLock *pLock, u32 iFirst, u32 iLast);
int btErrorBkpt(int rc);
#endif

        rc = btLockLockop(pLock, BT_LOCK_READER0 + i, BT_LOCK_SHARED, 0);
        if( rc==SQLITE4_OK ){
          int iSF = sqlite4BtLogFrameToIdx(aLog, aSlot[i].iFirst);
          int iSL = sqlite4BtLogFrameToIdx(aLog, aSlot[i].iLast);
          if( iSF>iIdxFirst || iSL>iIdxLast || iSF<0 || iSL<0 ){
            btLockLockop(pLock, BT_LOCK_READER0 + i, BT_LOCK_UNLOCK, 0);
            rc = SQLITE4_BUSY;


          }
        }else if( rc==SQLITE4_BUSY && nAttempt>(nMaxRetry/2) ){
          btLockDelay();
        }
      }
    }
  }
................................................................................
  BtLock *pLock,                  /* Lock handle */
  u32 *aLog,                      /* Current log topology */
  BtReadSlot *aSlot,              /* Array of BT_NREADER read slots */
  u32 *piOut,                     /* OUT: Query result */
  int *piDblocked                 /* OUT: True if READER_DB_ONLY is locked */
){
  u32 iOut = 0;
  u32 iIdxOut = 0;
  int bLast = (piDblocked!=0);
  int rc = SQLITE4_OK;
  int i;

  if( piDblocked ){
    rc = btLockLockop(pLock, BT_LOCK_READER_DBONLY, BT_LOCK_EXCL, 0);
    if( rc==SQLITE4_OK ){
................................................................................
        rc = btLockLockop(pLock, BT_LOCK_READER0 + iSlot, BT_LOCK_EXCL, 0);
        if( rc==SQLITE4_OK ){
          aSlot[iSlot].iFirst = 0;
          aSlot[iSlot].iLast = 0;
          btLockLockop(pLock, BT_LOCK_READER0 + iSlot, BT_LOCK_UNLOCK, 0);
        }else if( rc==SQLITE4_BUSY ){
          int iIdx = sqlite4BtLogFrameToIdx(aLog, iVal);
          if( iOut==0 || iIdx<iIdxOut ){
            iIdxOut = iIdx;
            iOut = iVal;
          }
        }else{
          return rc;
        }
      }

        rc = btLockLockop(pLock, BT_LOCK_READER0 + i, BT_LOCK_SHARED, 0);
        if( rc==SQLITE4_OK ){
          int iSF = sqlite4BtLogFrameToIdx(aLog, aSlot[i].iFirst);
          int iSL = sqlite4BtLogFrameToIdx(aLog, aSlot[i].iLast);
          if( iSF>iIdxFirst || iSL>iIdxLast || iSF<0 || iSL<0 ){
            btLockLockop(pLock, BT_LOCK_READER0 + i, BT_LOCK_UNLOCK, 0);
            rc = SQLITE4_BUSY;
          }else{
            sqlite4BtDebugReadlock(pLock, aSlot[i].iFirst, aSlot[i].iLast);
          }
        }else if( rc==SQLITE4_BUSY && nAttempt>(nMaxRetry/2) ){
          btLockDelay();
        }
      }
    }
  }
................................................................................
  BtLock *pLock,                  /* Lock handle */
  u32 *aLog,                      /* Current log topology */
  BtReadSlot *aSlot,              /* Array of BT_NREADER read slots */
  u32 *piOut,                     /* OUT: Query result */
  int *piDblocked                 /* OUT: True if READER_DB_ONLY is locked */
){
  u32 iOut = 0;
  int iIdxOut = 0;
  int bLast = (piDblocked!=0);
  int rc = SQLITE4_OK;
  int i;

  if( piDblocked ){
    rc = btLockLockop(pLock, BT_LOCK_READER_DBONLY, BT_LOCK_EXCL, 0);
    if( rc==SQLITE4_OK ){
................................................................................
        rc = btLockLockop(pLock, BT_LOCK_READER0 + iSlot, BT_LOCK_EXCL, 0);
        if( rc==SQLITE4_OK ){
          aSlot[iSlot].iFirst = 0;
          aSlot[iSlot].iLast = 0;
          btLockLockop(pLock, BT_LOCK_READER0 + iSlot, BT_LOCK_UNLOCK, 0);
        }else if( rc==SQLITE4_BUSY ){
          int iIdx = sqlite4BtLogFrameToIdx(aLog, iVal);
          if( iIdx>=0 && (iOut==0 || iIdx<iIdxOut) ){
            iIdxOut = iIdx;
            iOut = iVal;
          }
        }else{
          return rc;
        }
      }

){
  assert( (nByte&0x00000007)==4 && nByte>=8 );
  btLogChecksum(nativeCksum, a, 8, aIn, aOut);
  btLogChecksum(nativeCksum, &a[4], nByte-4, aOut, aOut);
}

#define BT_PAGE_DEBUG 0


static void btDebugTopology(BtLock *pLock, char *zStr, int iSide, u32 *aLog){
#if BT_PAGE_DEBUG
  fprintf(stderr, "%d:%s: (side=%d) %d..%d  %d..%d  %d..%d\n", 
      pLock->iDebugId, zStr, iSide,
      (int)aLog[0], (int)aLog[1], (int)aLog[2], 
      (int)aLog[3], (int)aLog[4], (int)aLog[5]
  );










  fflush(stderr);
#endif
}

#ifndef NDEBUG
static void btDebugCheckSnapshot(BtShmHdr *pHdr){
  u32 *aLog = pHdr->aLog;
  assert( pHdr->iNextFrame!=1 ||
      (aLog[0]==0 && aLog[1]==0 && aLog[2]==0 && aLog[3]==0)
  );
}
#else
#define btDebugCheckSnapshot(x,y)
#endif






















static void btDebugCkptPage(u32 pgno, u8 *aData, int pgsz){
#if BT_PAGE_DEBUG
  static int nCall = 0;
  u32 aCksum[2];
  btLogChecksum(1, aData, pgsz, 0, aCksum);
  fprintf(stderr, "%d: Ckpt page %d (cksum=%08x%08x)\n", nCall++,
      (int)pgno, aCksum[0], aCksum[1]
  );
  fflush(stderr);
#endif
}

static void btDebugLogPage(
    BtLock *pLock, u32 pgno, u32 iFrame, u8 *aData, int pgsz, int bCommit
................................................................................
      nCall++, (int)pgno, aCksum[0], aCksum[1]
  );
  fflush(stderr);
#endif
}
#endif


































static void btDebugLogSearch(BtLock *pLock, u32 pgno, u32 iFrame){
#if BT_PAGE_DEBUG
  static int nCall = 0;
  fprintf(stderr, "%d:%d: Search log for page %d - frame %d\n", pLock->iDebugId,
      nCall++, (int)pgno, (int)iFrame
  );
  fflush(stderr);
#endif
}

static void btDebugSetPgno(
    BtLock *pLock, int iHash, u32 *aPgno, int iFrame, int iZero, u32 pgno
................................................................................
      /* One or more transactions were recovered from the log file. */
      BtShm *pShm = btLogShm(pLog);
      pShm->ckpt.iWalHdr = (iSlot<<2) + pHdr->iCnt;
      pShm->ckpt.iFirstRead = pHdr->iFirstFrame;
      pShm->ckpt.iFirstRecover = pHdr->iFirstFrame;
      rc = btLogRollbackRecovery(pLog, &ctx);
      pLog->snapshot.iNextFrame = ctx.iNextFrame;

    }
  }

  if( rc==SQLITE4_OK && ctx.iLast==0 ){
    /* No transactions were recovered from the log file. */
    BtDbhdr dbhdr;            /* Database header */
    btLogZeroSnapshot(pLog);
................................................................................
** SQLITE4_NOTFOUND.
*/
int btLogRead(BtLog *pLog, u32 pgno, u8 *aData, u32 iSafe){
  const int pgsz = sqlite4BtPagerPagesize((BtPager*)(pLog->pLock));
  int rc = SQLITE4_NOTFOUND;
  u32 iFrame = 0;
  int i;

  int bSeen = (iSafe==0);




  /* Loop through regions (c), (b) and (a) of the log file. In that order. */
  for(i=2; i>=0 && rc==SQLITE4_NOTFOUND; i--){
    u32 iLo = pLog->snapshot.aLog[i*2+0];
    u32 iHi = pLog->snapshot.aLog[i*2+1];
    int iSide;
    int iHash;
    int iHashLast;
................................................................................

    for( ; rc==SQLITE4_NOTFOUND && iHash>=iHashLast; iHash--){
      rc = btLogHashSearch(pLog, iSide, iHash, iHi, pgno, &iFrame);
      if( rc==SQLITE4_OK ){
        if( iFrame<iLo || iFrame>iHi ){
          rc = SQLITE4_NOTFOUND;
        }else{
          if( iSafe>=iLo && iSafe<=iHi ){
            if( iFrame>iSafe ) return SQLITE4_NOTFOUND;
          }else if( bSeen==0 ){
            return SQLITE4_NOTFOUND;
          }
        }
      }
    }
    if( (iSafe>=iLo && iSafe<=iHi) ){
      bSeen = 1;
    }
  }

  btDebugLogSearch(pLog->pLock, pgno, (rc==SQLITE4_OK ? iFrame : 0));

  if( rc==SQLITE4_OK ){
    bt_env *pVfs = pLog->pLock->pVfs;
    i64 iOff;
    assert( rc==SQLITE4_OK );
    iOff = btLogFrameOffset(pLog, pgsz, iFrame);
    rc = pVfs->xRead(pLog->pFd, iOff + sizeof(BtFrameHdr), aData, pgsz);
................................................................................
    }

    if( nAttempt==0 ) rc = SQLITE4_PROTOCOL;
  }

  return rc;
}


















int sqlite4BtLogSnapshotOpen(BtLog *pLog){
  u32 *aLog = pLog->snapshot.aLog;
  int rc = SQLITE4_NOTFOUND;
  BtShmHdr shmhdr;
  u32 iFirstRead = 0;

................................................................................
      }
    }
    
    if( rc!=SQLITE4_OK ){
      sqlite4BtLockReaderUnlock(pLog->pLock);
    }
  }







  /* If a snapshot was successfully read, adjust it so that the aLog[] 
  ** array specifies that no frames before iFirstRead is ever read from 
  ** the log file.  */
  if( rc==SQLITE4_OK ){
    int iRegion;
    for(iRegion=0; iRegion<3; iRegion++){
      if( aLog[iRegion*2] ){
        if( iFirstRead>=aLog[iRegion*2] && iFirstRead<=aLog[iRegion*2+1] ){
          aLog[iRegion*2] = iFirstRead;
          break;
        }else{
          aLog[iRegion*2] = 0;
          aLog[iRegion*2+1] = 0;
        }
      }
    }
  }

if( rc==SQLITE4_OK ){
  btDebugTopology(
      pLog->pLock, "snapshot", pLog->snapshot.iHashSide, pLog->snapshot.aLog
  );
}

  return rc;
}

int sqlite4BtLogSnapshotClose(BtLog *pLog){
  sqlite4BtLockReaderUnlock(pLog->pLock);
  return SQLITE4_OK;
................................................................................
    ** that it contains a map of all frames that are currently in use
    ** by any reader, or may be used by any future reader or recovery
    ** process.  */
    if( rc==SQLITE4_OK ){
      u32 *aLog = shmhdr.aLog;
      u32 iRecover = pShm->ckpt.iFirstRecover;
      u32 iRead = 0;




      btDebugCheckSnapshot(&pLog->snapshot);

      rc = sqlite4BtLockReaderQuery(pLock, aLog, pShm->aReadlock, &iRead, 0);

      if( rc==SQLITE4_OK ){
        /* Now "trim" the snapshot so that it accesses nothing earlier than
        ** either iRecover or iRead (whichever occurs first in the log). */
................................................................................
              break;
            }else{
              aLog[2*i] = aLog[2*i+1] = 0;
            }
          }
        }
      }



      if( rc==SQLITE4_OK ){
        memcpy(pLog->snapshot.aLog, aLog, sizeof(u32)*6);
      }
      btDebugCheckSnapshot(&pLog->snapshot);
    }
  }
................................................................................
  u32 *aSpace;                    /* Temporary space used by merge-sort */
  int nMax;
  int rc = SQLITE4_OK;
  int iRegion;
  int bLocked;
  u32 iSafe;                      /* Last frame in log it is safe to gather */





  *paPgno = 0;
  *pnPgno = 0;
  *piLastFrame = 0;

  rc = sqlite4BtLockReaderQuery(pLock, aLog, pShm->aReadlock, &iSafe, &bLocked);
  if( rc!=SQLITE4_OK || bLocked ) return rc;








  /* Determine an upper limit on the number of distinct page numbers. This
  ** limit is used to allocate space for the returned array.  */
  nMax = 0;
  for(iRegion=0; iRegion<3; iRegion++){
    if( aLog[iRegion*2] ){
      nMax += 1 + aLog[iRegion*2+1] - aLog[iRegion*2+0];
................................................................................
  nPgno = 0;

  /* Copy the required page numbers into the allocated array */
  for(iRegion=0; iRegion<3; iRegion++){
    u32 iFirst = aLog[iRegion*2];
    u32 iLast = aLog[iRegion*2+1];
    if( iFirst ){
      /* If the last frame that it is safe to gather is part of this 
      ** region, gather no frames that lie beyond it.  */
      if( iSafe>=iFirst && iSafe<=iLast ){
        iLast = iSafe;
      }

      for(i=iFirst; rc==SQLITE4_OK && i<=iLast; i++){
        int iHash = btLogFrameHash(pLog, i);
        u32 *aPage;
        ht_slot *aHash;
        u32 iZero;








        /* It doesn't matter which 'side' of the hash table is requested here,
        ** as only the page-number array, not the aHash[] table, will be used.
        ** And it is the same for both sides. Hence the constant 0 passed as
        ** the second argument to btLogFindHash().  */
        rc = btLogFindHash(pLog, 0, iHash, &aHash, &aPage, &iZero);
        if( rc==SQLITE4_OK ){
          aPgno[nPgno++] = aPage[i-iZero];
        }
      }
      *piLastFrame = iLast;

      /* If the last frame of this region is the last frame that it is
      ** safe to gather, break out of the loop.  */
      if( iLast==iSafe ) break;
    }
  }

  /* Sort the contents of the array in ascending order. This step also 
  ** eliminates any  duplicate page numbers. */
  if( rc==SQLITE4_OK ){
    btLogMergeSort(aPgno, &nPgno, aSpace);
................................................................................
    int nPgno;                    /* Number of entries in aPgno[] */
    int i;                        /* Used to loop through aPgno[] */
    u8 *aBuf;                     /* Buffer to load page data into */
    u32 iFirstRead;               /* First frame not checkpointed */

    rc = btLogSnapshot(pLog, &pLog->snapshot);

    /* Allocate space to load log data into */
    if( rc==SQLITE4_OK ){










      aBuf = sqlite4_malloc(pLock->pEnv, pgsz);
      if( aBuf==0 ) rc = btErrorBkpt(SQLITE4_NOMEM);
    }
    
    /* Figure out the set of page numbers stored in the part of the log 
    ** file being checkpointed. Remove any duplicates and sort them in 
    ** ascending order.  */
    if( rc==SQLITE4_OK ){
      rc = btLogGatherPgno(pLog, &aPgno, &nPgno, &iLast);
    }

    if( rc==SQLITE4_OK ){
      i64 iOff = btLogFrameOffset(pLog, pgsz, iLast);
      rc = btLogReadData(pLog, iOff, (u8*)&fhdr, sizeof(BtFrameHdr));
      iFirstRead = fhdr.iNext;
    }

    /* Copy data from the log file to the database file. */
    for(i=0; rc==SQLITE4_OK && i<nPgno; i++){
      u32 pgno = aPgno[i];
      rc = btLogRead(pLog, pgno, aBuf, iLast);
      if( rc==SQLITE4_OK ){
        i64 iOff = (i64)pgsz * (pgno-1);
        if( pgno==1 ){
          btLogUpdateDbhdr(pLog, aBuf);
        }
        btDebugCkptPage(pgno, aBuf, pgsz);
        rc = pVfs->xWrite(pFd, iOff, aBuf, pgsz);
      }else if( rc==SQLITE4_NOTFOUND ){
        rc = SQLITE4_OK;
      }
    }

    /* Update the first field of the checkpoint-header. This tells readers
    ** that they need not consider anything that in the log before this
    ** point (since the data has already been copied into the database
    ** file).  */
    if( rc==SQLITE4_OK ){

      pShm = btLogShm(pLog);
      pShm->ckpt.iFirstRead = iFirstRead;
      pVfs->xShmBarrier(pLog->pFd);
    }

    /* Write a new header into the log file. This tells any future recovery
    ** where it should start reading the log. Once this new header is synced
    ** to disk, the space cleared by this checkpoint operation can be 
    ** reused.  */
    if( rc==SQLITE4_OK ){
      int iSlot = ((pShm->ckpt.iWalHdr >> 2) + 1) % 2;
      BtWalHdr hdr;

      memset(&hdr, 0, sizeof(BtWalHdr));
      hdr.iMagic = BT_WAL_MAGIC;
      hdr.iVersion = BT_WAL_VERSION;
      hdr.iCnt = (((pShm->ckpt.iWalHdr & 0x03) + 1) % 3);
      hdr.nSector = pLog->snapshot.nSector;
      hdr.nPgsz = pgsz;
      hdr.iFirstFrame = iFirstRead;

      hdr.iSalt1 = fhdr.aCksum[0];
      hdr.iSalt2 = fhdr.aCksum[1];
      rc = btLogWriteHeader(pLog, iSlot, &hdr);
      if( rc==SQLITE4_OK ){
        pShm->ckpt.iWalHdr = (iSlot<<2) + hdr.iCnt;
      }
    }

    /* Update the second field of the checkpoint header. This tells future
    ** writers that it is now safe to recycle pages before this point
    ** (assuming all live readers are cleared).  */
    if( rc==SQLITE4_OK ){
      pShm->ckpt.iFirstRecover = iFirstRead;
      pVfs->xShmBarrier(pLog->pFd);

    }

    /* Free buffers and drop the checkpointer lock */
    sqlite4_free(pLock->pEnv, aBuf);
    sqlite4_free(pLock->pEnv, aPgno);
    sqlite4BtLockCkptUnlock(pLog->pLock);
  }

){
  assert( (nByte&0x00000007)==4 && nByte>=8 );
  btLogChecksum(nativeCksum, a, 8, aIn, aOut);
  btLogChecksum(nativeCksum, &a[4], nByte-4, aOut, aOut);
}

#define BT_PAGE_DEBUG 0
#define BT_VAL_DEBUG  0

static void btDebugTopology(BtLock *pLock, char *zStr, int iSide, u32 *aLog){
#if BT_PAGE_DEBUG
  fprintf(stderr, "%d:%s: (side=%d) %d..%d  %d..%d  %d..%d\n", 
      pLock->iDebugId, zStr, iSide,
      (int)aLog[0], (int)aLog[1], (int)aLog[2], 
      (int)aLog[3], (int)aLog[4], (int)aLog[5]
  );
  fflush(stderr);
#endif
}

void sqlite4BtDebugReadlock(BtLock *pLock, u32 iFirst, u32 iLast){
#if BT_PAGE_DEBUG
  static int nCall = 0;
  fprintf(stderr, "%d:%d: readlock=(%d..%d)\n",
      pLock->iDebugId, nCall++, (int)iFirst, (int)iLast
  );
  fflush(stderr);
#endif
}

#ifndef NDEBUG
static void btDebugCheckSnapshot(BtShmHdr *pHdr){
  u32 *aLog = pHdr->aLog;
  assert( pHdr->iNextFrame!=1 ||
      (aLog[0]==0 && aLog[1]==0 && aLog[2]==0 && aLog[3]==0)
  );
}
#else
#define btDebugCheckSnapshot(x)
#endif

#ifndef NDEBUG
static void btDebugCheckHash(BtLock *pLock){
}
#else
#define btDebugCheckHash(x)
#endif

#ifndef NDEBUG
static void btDebugLogSafepoint(BtLock *pLock, u32 iSafe){
#if BT_PAGE_DEBUG
  static int nCall = 0;
  fprintf(stderr, "%d:%d: checkpoint safepoint=%d\n",
      pLock->iDebugId, nCall++, (int)iSafe
  );
  fflush(stderr);
#endif
}
#else
#define btDebugLogSafepoint(x)
#endif

static void btDebugCkptPage(BtLock *pLock, u32 pgno, u8 *aData, int pgsz){
#if BT_PAGE_DEBUG
  static int nCall = 0;
  u32 aCksum[2];
  btLogChecksum(1, aData, pgsz, 0, aCksum);
  fprintf(stderr, "%d:%d: Ckpt page %d (cksum=%08x%08x)\n", 
      pLock->iDebugId, nCall++, (int)pgno, aCksum[0], aCksum[1]
  );
  fflush(stderr);
#endif
}

static void btDebugLogPage(
    BtLock *pLock, u32 pgno, u32 iFrame, u8 *aData, int pgsz, int bCommit
................................................................................
      nCall++, (int)pgno, aCksum[0], aCksum[1]
  );
  fflush(stderr);
#endif
}
#endif

#ifndef NDEBUG
#include <ctype.h>
static void binToStr(u8 *pIn, int nIn, u8 *pOut, int nOut){
  int i;
  int nCopy = MIN(nIn, (nOut-1));
  for(i=0; i<nCopy; i++){
    if( isprint(pIn[i]) ){
      pOut[i] = pIn[i];
    }else{
      pOut[i] = ".";
    }
  }
  pOut[i] = '\0';
}
void sqlite4BtDebugKV(
    BtLock *pLock, const char *zStr, u8 *pK, int nK, u8 *pV, int nV
){
#if BT_VAL_DEBUG
  u8 aKBuf[40];
  u8 aVBuf[40];
  static int nCall = 0;

  binToStr(pK, nK, aKBuf, sizeof(aKBuf));
  binToStr(pV, nV, aVBuf, sizeof(aVBuf));
  fprintf(stderr, "%d:%d: %s \"%s\" -> \"%s\"\n", 
      pLock->iDebugId, nCall++, zStr, aKBuf, aVBuf
  );

  fflush(stderr);
#endif
}
#endif

static void btDebugLogSearch(BtLock *pLock, u32 pgno, u32 iSafe, u32 iFrame){
#if BT_PAGE_DEBUG
  static int nCall = 0;
  fprintf(stderr, "%d:%d: Search log for page %d (safe=%d) - frame %d\n", 
      pLock->iDebugId, nCall++, (int)pgno, (int)iSafe, (int)iFrame
  );
  fflush(stderr);
#endif
}

static void btDebugSetPgno(
    BtLock *pLock, int iHash, u32 *aPgno, int iFrame, int iZero, u32 pgno
................................................................................
      /* One or more transactions were recovered from the log file. */
      BtShm *pShm = btLogShm(pLog);
      pShm->ckpt.iWalHdr = (iSlot<<2) + pHdr->iCnt;
      pShm->ckpt.iFirstRead = pHdr->iFirstFrame;
      pShm->ckpt.iFirstRecover = pHdr->iFirstFrame;
      rc = btLogRollbackRecovery(pLog, &ctx);
      pLog->snapshot.iNextFrame = ctx.iNextFrame;
      assert( pShm->ckpt.iFirstRead>0 );
    }
  }

  if( rc==SQLITE4_OK && ctx.iLast==0 ){
    /* No transactions were recovered from the log file. */
    BtDbhdr dbhdr;            /* Database header */
    btLogZeroSnapshot(pLog);
................................................................................
** SQLITE4_NOTFOUND.
*/
int btLogRead(BtLog *pLog, u32 pgno, u8 *aData, u32 iSafe){
  const int pgsz = sqlite4BtPagerPagesize((BtPager*)(pLog->pLock));
  int rc = SQLITE4_NOTFOUND;
  u32 iFrame = 0;
  int i;

  int bSeen = (iSafe==0);

  u32 *aLog = pLog->snapshot.aLog;
  int iSafeIdx = sqlite4BtLogFrameToIdx(aLog, iSafe);

  /* Loop through regions (c), (b) and (a) of the log file. In that order. */
  for(i=2; i>=0 && rc==SQLITE4_NOTFOUND; i--){
    u32 iLo = pLog->snapshot.aLog[i*2+0];
    u32 iHi = pLog->snapshot.aLog[i*2+1];
    int iSide;
    int iHash;
    int iHashLast;
................................................................................

    for( ; rc==SQLITE4_NOTFOUND && iHash>=iHashLast; iHash--){
      rc = btLogHashSearch(pLog, iSide, iHash, iHi, pgno, &iFrame);
      if( rc==SQLITE4_OK ){
        if( iFrame<iLo || iFrame>iHi ){
          rc = SQLITE4_NOTFOUND;
        }else{
          assert( sqlite4BtLogFrameToIdx(aLog, iFrame)>=0 );
          if( iSafeIdx>=0 && sqlite4BtLogFrameToIdx(aLog, iFrame)>iSafeIdx ){

            return SQLITE4_NOTFOUND;
          }
        }
      }
    }


  }


  btDebugLogSearch(pLog->pLock, pgno, iSafe, (rc==SQLITE4_OK ? iFrame : 0));

  if( rc==SQLITE4_OK ){
    bt_env *pVfs = pLog->pLock->pVfs;
    i64 iOff;
    assert( rc==SQLITE4_OK );
    iOff = btLogFrameOffset(pLog, pgsz, iFrame);
    rc = pVfs->xRead(pLog->pFd, iOff + sizeof(BtFrameHdr), aData, pgsz);
................................................................................
    }

    if( nAttempt==0 ) rc = SQLITE4_PROTOCOL;
  }

  return rc;
}

static void btLogSnapshotTrim(u32 *aLog, u32 iFirst){
  if( iFirst ){
    int iRegion;
    for(iRegion=0; iRegion<3; iRegion++){
      if( aLog[iRegion*2] ){
        if( iFirst>=aLog[iRegion*2] && iFirst<=aLog[iRegion*2+1] ){
          aLog[iRegion*2] = iFirst;
          break;
        }else{
          aLog[iRegion*2] = 0;
          aLog[iRegion*2+1] = 0;
        }
      }
    }
  }
}

int sqlite4BtLogSnapshotOpen(BtLog *pLog){
  u32 *aLog = pLog->snapshot.aLog;
  int rc = SQLITE4_NOTFOUND;
  BtShmHdr shmhdr;
  u32 iFirstRead = 0;

................................................................................
      }
    }
    
    if( rc!=SQLITE4_OK ){
      sqlite4BtLockReaderUnlock(pLog->pLock);
    }
  }

  if( rc==SQLITE4_OK ){
    btDebugTopology(
        pLog->pLock, "snapshotA", pLog->snapshot.iHashSide, pLog->snapshot.aLog
    );
  }

  /* If a snapshot was successfully read, adjust it so that the aLog[] 
  ** array specifies that no frames before iFirstRead is ever read from 
  ** the log file.  */
  if( rc==SQLITE4_OK ){
    btLogSnapshotTrim(aLog, iFirstRead);








  }




  if( rc==SQLITE4_OK ){
    btDebugTopology(
        pLog->pLock, "snapshotB", pLog->snapshot.iHashSide, pLog->snapshot.aLog
    );
  }

  return rc;
}

int sqlite4BtLogSnapshotClose(BtLog *pLog){
  sqlite4BtLockReaderUnlock(pLog->pLock);
  return SQLITE4_OK;
................................................................................
    ** that it contains a map of all frames that are currently in use
    ** by any reader, or may be used by any future reader or recovery
    ** process.  */
    if( rc==SQLITE4_OK ){
      u32 *aLog = shmhdr.aLog;
      u32 iRecover = pShm->ckpt.iFirstRecover;
      u32 iRead = 0;

      btDebugTopology(pLog->pLock, "snapshotC", shmhdr.iHashSide, aLog);

      assert( shmhdr.iHashSide==pLog->snapshot.iHashSide );
      btDebugCheckSnapshot(&pLog->snapshot);

      rc = sqlite4BtLockReaderQuery(pLock, aLog, pShm->aReadlock, &iRead, 0);

      if( rc==SQLITE4_OK ){
        /* Now "trim" the snapshot so that it accesses nothing earlier than
        ** either iRecover or iRead (whichever occurs first in the log). */
................................................................................
              break;
            }else{
              aLog[2*i] = aLog[2*i+1] = 0;
            }
          }
        }
      }

      btDebugTopology(pLog->pLock, "snapshotD", shmhdr.iHashSide, aLog);

      if( rc==SQLITE4_OK ){
        memcpy(pLog->snapshot.aLog, aLog, sizeof(u32)*6);
      }
      btDebugCheckSnapshot(&pLog->snapshot);
    }
  }
................................................................................
  u32 *aSpace;                    /* Temporary space used by merge-sort */
  int nMax;
  int rc = SQLITE4_OK;
  int iRegion;
  int bLocked;
  u32 iSafe;                      /* Last frame in log it is safe to gather */

  int iSafeIdx = -1;
  int iFirstIdx = -1;
  int iIdx = 0;

  *paPgno = 0;
  *pnPgno = 0;
  *piLastFrame = 0;

  rc = sqlite4BtLockReaderQuery(pLock, aLog, pShm->aReadlock, &iSafe, &bLocked);
  if( rc!=SQLITE4_OK || bLocked ) return rc;
  btDebugLogSafepoint(pLock, iSafe);
  btDebugTopology(
      pLock, "checkpointer", pLog->snapshot.iHashSide, pLog->snapshot.aLog
  );

  iSafeIdx = sqlite4BtLogFrameToIdx(aLog, iSafe);
  iFirstIdx = sqlite4BtLogFrameToIdx(aLog, pShm->ckpt.iFirstRecover);

  /* Determine an upper limit on the number of distinct page numbers. This
  ** limit is used to allocate space for the returned array.  */
  nMax = 0;
  for(iRegion=0; iRegion<3; iRegion++){
    if( aLog[iRegion*2] ){
      nMax += 1 + aLog[iRegion*2+1] - aLog[iRegion*2+0];
................................................................................
  nPgno = 0;

  /* Copy the required page numbers into the allocated array */
  for(iRegion=0; iRegion<3; iRegion++){
    u32 iFirst = aLog[iRegion*2];
    u32 iLast = aLog[iRegion*2+1];
    if( iFirst ){






      for(i=iFirst; rc==SQLITE4_OK && i<=iLast; i++, iIdx++){
        int iHash = btLogFrameHash(pLog, i);
        u32 *aPage;
        ht_slot *aHash;
        u32 iZero;

        if( (iFirstIdx>=0 && iIdx<iFirstIdx) 
         || (iSafeIdx>=0 && iIdx>iSafeIdx) 
        ){
          continue;
        }
        *piLastFrame = i;

        /* It doesn't matter which 'side' of the hash table is requested here,
        ** as only the page-number array, not the aHash[] table, will be used.
        ** And it is the same for both sides. Hence the constant 0 passed as
        ** the second argument to btLogFindHash().  */
        rc = btLogFindHash(pLog, 0, iHash, &aHash, &aPage, &iZero);
        if( rc==SQLITE4_OK ){
          aPgno[nPgno++] = aPage[i-iZero];
        }
      }





    }
  }

  /* Sort the contents of the array in ascending order. This step also 
  ** eliminates any  duplicate page numbers. */
  if( rc==SQLITE4_OK ){
    btLogMergeSort(aPgno, &nPgno, aSpace);
................................................................................
    int nPgno;                    /* Number of entries in aPgno[] */
    int i;                        /* Used to loop through aPgno[] */
    u8 *aBuf;                     /* Buffer to load page data into */
    u32 iFirstRead;               /* First frame not checkpointed */

    rc = btLogSnapshot(pLog, &pLog->snapshot);


    if( rc==SQLITE4_OK ){
      /* Ensure that the checkpoint does not read any frames from the log
      ** that occur earlier than iFirstRecover. This is not just an 
      ** optimization - there is a chance that such frames may be 
      ** overwritten by a writer running concurrently with this checkpoint. */
#if 0
      pShm = btLogShm(pLog);
      btLogSnapshotTrim(pLog->snapshot.aLog, pShm->ckpt.iFirstRecover);
#endif

      /* Allocate space to load log data into */
      aBuf = sqlite4_malloc(pLock->pEnv, pgsz);
      if( aBuf==0 ) rc = btErrorBkpt(SQLITE4_NOMEM);
    }
    
    /* Figure out the set of page numbers stored in the part of the log 
    ** file being checkpointed. Remove any duplicates and sort them in 
    ** ascending order.  */
    if( rc==SQLITE4_OK ){
      rc = btLogGatherPgno(pLog, &aPgno, &nPgno, &iLast);
    }

    if( rc==SQLITE4_OK && nPgno>0 ){
      i64 iOff = btLogFrameOffset(pLog, pgsz, iLast);
      rc = btLogReadData(pLog, iOff, (u8*)&fhdr, sizeof(BtFrameHdr));
      iFirstRead = fhdr.iNext;


      /* Copy data from the log file to the database file. */
      for(i=0; rc==SQLITE4_OK && i<nPgno; i++){
        u32 pgno = aPgno[i];
        rc = btLogRead(pLog, pgno, aBuf, iLast);
        if( rc==SQLITE4_OK ){
          i64 iOff = (i64)pgsz * (pgno-1);
          if( pgno==1 ){
            btLogUpdateDbhdr(pLog, aBuf);
          }
          btDebugCkptPage(pLog->pLock, pgno, aBuf, pgsz);
          rc = pVfs->xWrite(pFd, iOff, aBuf, pgsz);
        }else if( rc==SQLITE4_NOTFOUND ){
          rc = SQLITE4_OK;
        }
      }

      /* Update the first field of the checkpoint-header. This tells readers
      ** that they need not consider anything that in the log before this
      ** point (since the data has already been copied into the database
      ** file).  */
      if( rc==SQLITE4_OK ){
        assert( iFirstRead>0 );
        pShm = btLogShm(pLog);
        pShm->ckpt.iFirstRead = iFirstRead;
        pVfs->xShmBarrier(pLog->pFd);
      }

      /* Write a new header into the log file. This tells any future recovery
      ** where it should start reading the log. Once this new header is synced
      ** to disk, the space cleared by this checkpoint operation can be 
      ** reused.  */
      if( rc==SQLITE4_OK ){
        int iSlot = ((pShm->ckpt.iWalHdr >> 2) + 1) % 2;
        BtWalHdr hdr;

        memset(&hdr, 0, sizeof(BtWalHdr));
        hdr.iMagic = BT_WAL_MAGIC;
        hdr.iVersion = BT_WAL_VERSION;
        hdr.iCnt = (((pShm->ckpt.iWalHdr & 0x03) + 1) % 3);
        hdr.nSector = pLog->snapshot.nSector;
        hdr.nPgsz = pgsz;
        hdr.iFirstFrame = iFirstRead;

        hdr.iSalt1 = fhdr.aCksum[0];
        hdr.iSalt2 = fhdr.aCksum[1];
        rc = btLogWriteHeader(pLog, iSlot, &hdr);
        if( rc==SQLITE4_OK ){
          pShm->ckpt.iWalHdr = (iSlot<<2) + hdr.iCnt;
        }
      }

      /* Update the second field of the checkpoint header. This tells future
      ** writers that it is now safe to recycle pages before this point
      ** (assuming all live readers are cleared).  */
      if( rc==SQLITE4_OK ){
        pShm->ckpt.iFirstRecover = iFirstRead;
        pVfs->xShmBarrier(pLog->pFd);
      }
    }

    /* Free buffers and drop the checkpointer lock */
    sqlite4_free(pLock->pEnv, aBuf);
    sqlite4_free(pLock->pEnv, aPgno);
    sqlite4BtLockCkptUnlock(pLog->pLock);
  }

      *ppV = &pCsr->ovfl.pBuf[pCsr->ovfl.nKey];
      *pnV = pCsr->ovfl.nVal;
    }
  }else{
    *ppV = pCell;
    *pnV = (nV-1);
  }












  return rc;
}

/*
** The argument points to a buffer containing an overflow array. Return
** the size of the overflow array in bytes. 
................................................................................

/*
** Insert a new key/value pair or replace an existing one.
*/
int sqlite4BtReplace(bt_db *db, const void *pK, int nK, const void *pV, int nV){
  int rc = SQLITE4_OK;
  bt_cursor csr;



  btCheckPageRefs(db);
  btCsrSetup(db, &csr);
  rc = btCsrSeek(&csr, pK, nK, BT_SEEK_GE, 1);
  if( rc==SQLITE4_OK ){
    /* The cursor currently points to an entry with key pK/nK. This call
    ** should therefore replace that entry. So delete it and then re-seek

      *ppV = &pCsr->ovfl.pBuf[pCsr->ovfl.nKey];
      *pnV = pCsr->ovfl.nVal;
    }
  }else{
    *ppV = pCell;
    *pnV = (nV-1);
  }

#ifndef NDEBUG
  if( rc==SQLITE4_OK ){
    const void *pK; int nK;
    rc = sqlite4BtCsrKey(pCsr, &pK, &nK);
    if( rc==SQLITE4_OK ){
      BtLock *pLock = (BtLock*)pCsr->pDb->pPager;
      sqlite4BtDebugKV(pLock, "select", (u8*)pK, nK, (u8*)*ppV, *pnV);
    }
  }
#endif

  return rc;
}

/*
** The argument points to a buffer containing an overflow array. Return
** the size of the overflow array in bytes. 
................................................................................

/*
** Insert a new key/value pair or replace an existing one.
*/
int sqlite4BtReplace(bt_db *db, const void *pK, int nK, const void *pV, int nV){
  int rc = SQLITE4_OK;
  bt_cursor csr;

  sqlite4BtDebugKV((BtLock*)db->pPager, "replace", pK, nK, pV, nV);

  btCheckPageRefs(db);
  btCsrSetup(db, &csr);
  rc = btCsrSeek(&csr, pK, nK, BT_SEEK_GE, 1);
  if( rc==SQLITE4_OK ){
    /* The cursor currently points to an entry with key pK/nK. This call
    ** should therefore replace that entry. So delete it and then re-seek