SQLite4  Check-in [885387b919]

}
#define btPutU32(x,y) sqlite4BtPutU32(x,y)

/*
** Allocate a new database handle.
*/
int sqlite4BtNew(sqlite4_env *pEnv, int nExtra, bt_db **ppDb){
  static const int MIN_MERGE = 2;
  static const int SCHEDULE_ALLOC = 4;

  bt_db *db = 0;                  /* New database object */
  BtPager *pPager = 0;            /* Pager object for this database */
  int nReq;                       /* Bytes of space required for bt_db object */
  int rc;                         /* Return code */

  nReq = sizeof(bt_db);

static void btPageToAscii(
  u32 pgno,                       /* Page number */
  int bAscii,                     /* True to print keys and values as ASCII */
  BtPager *pPager,                /* Pager object (or NULL) */
  u8 *aData, int nData,           /* Buffer containing page data */
  sqlite4_buffer *pBuf            /* Output buffer */
){
  BtDbHdr *pHdr = 0;
  int i;
  int nCell = (int)btCellCount(aData, nData);
  u8 flags = btFlags(aData);      /* Page flags */

  sqlite4BtBufAppendf(pBuf, "Page %d: ", pgno);

  if( pPager ) pHdr = sqlite4BtPagerDbhdr(pPager);
  if( pHdr && pgno==pHdr->iSRoot ){
    int i;
    BtSchedule s;
    sqlite4BtBufAppendf(pBuf, "(schedule page) ");
    btReadSchedule(0, aData, &s);

    sqlite4BtBufAppendf(pBuf, "  eBusy=(%s)\n",
        s.eBusy==BT_SCHEDULE_EMPTY ? "empty" :

  return 0;
}

int printPgToStderr(BtPage *pPg){
  printPage(stderr, sqlite4BtPagePgno(pPg), sqlite4BtPageData(pPg), 1024);
  return 0;
}

static void btPrintMetaTree(BtPager *pPager, int bAscii, BtDbHdr *pHdr){
  u8 *aData;
  int nData;
  sqlite4_buffer buf;
  BtPage *pPg = 0;

  sqlite4BtPageGet(pPager, pHdr->iMRoot, &pPg);
  aData = sqlite4BtPageData(pPg);
  nData = pHdr->pgsz;
  sqlite4_buffer_init(&buf, 0);
  btPageToAscii(pHdr->iMRoot, bAscii, pPager, aData, nData, &buf);
  sqlite4_buffer_append(&buf, "", 1);

  fprintf(stderr, "%s", (char*)buf.p);
  sqlite4_buffer_clear(&buf);
  sqlite4BtPageRelease(pPg);
}
#endif

static int btCsrEnd(BtCursor *pCsr, int bLast);
static int btCsrStep(BtCursor *pCsr, int bNext);
static int btCsrKey(BtCursor *pCsr, const void **ppK, int *pnK);

#ifndef NDEBUG
/*
** This function is really just a big assert() statement. It contributes 
** nothing to the operation of the library.
**
** The assert() fails if the summary-record is not consistent with the
** actual contents of the meta-tree.
*/
static void assert_summary_ok(bt_db *db){
  BtDbHdr *pHdr = sqlite4BtPagerDbhdr(db->pPager);
  BtCursor csr;                   /* Cursor used to load summary record */
  BtCursor mcsr;                  /* Cursor used to scan meta-tree */
  const u8 *aSum; int nSum;       /* Current summary record */
  int i;
  int rc;

  struct AgeData {
    int iMinLevel;                /* Smallest level of this age seen */
    int iMaxLevel;                /* Largest level of this age seen */
  } aData[32];

  for(i=0; i<array_size(aData); i++){
    aData[i].iMinLevel = -1;
    aData[i].iMaxLevel = -1;
  }

  rc = fiLoadSummary(db, &csr, &aSum, &nSum);
  assert( rc==SQLITE4_OK );

  btCsrSetup(db, pHdr->iMRoot, &mcsr);
  for(rc=btCsrEnd(&mcsr, 0); rc==SQLITE4_OK; rc=btCsrStep(&mcsr, 1)){
    const u8 *pKey = 0; int nKey = 0;
    u32 iAge;
    u32 iLevel;
    rc = btCsrKey(&mcsr, (const void **)&pKey, &nKey);
    assert( rc==SQLITE4_OK );

    if( nKey==array_size(aSummaryKey) && memcmp(aSummaryKey, pKey, nKey)==0 ){
      break;
    }
    assert( nKey>=8 );

    iAge = btGetU32(&pKey[0]);
    iLevel = ~btGetU32(&pKey[4]);

    if( aData[iAge].iMinLevel<0 || aData[iAge].iMinLevel>iLevel ){
      aData[iAge].iMinLevel = (int)iLevel;
    }
    if( aData[iAge].iMaxLevel<0 || aData[iAge].iMaxLevel<iLevel ){
      aData[iAge].iMaxLevel = (int)iLevel;
    }
  }
  assert( rc==SQLITE4_OK );

  for(i=0; i<array_size(aData); i++){
    u16 iMin = 0; 
    u16 nLevel = 0;
    if( i<(nSum/6) ){
      btReadSummary(aSum, i, &iMin, &nLevel, 0);
    }
    if( aData[i].iMinLevel>=0 ){
      assert( (int)iMin==aData[i].iMinLevel );
      assert( (int)nLevel==(aData[i].iMaxLevel - aData[i].iMinLevel + 1) );
    }else{
      assert( iMin==0 && nLevel==0 );
    }
  }

  btCsrReset(&csr, 1);
  btCsrReset(&mcsr, 1);
}
#else
# define assert_summary_ok(x) 
#endif


/*
** This function compares the key passed via parameters pK and nK to the
** key that cursor pCsr currently points to.
**

** direction.
*/
static int fiCsrStep(FiCursor *pCsr){
  int rc = SQLITE4_OK;
  int bNext = (0!=(pCsr->base.flags & CSR_NEXT_OK));
  const void *pKey; int nKey;     /* Current key that cursor points to */
  int i;

#ifndef NDEBUG
  sqlite4_buffer buf;
  sqlite4_buffer_init(&buf, 0);
  sqlite4BtCsrKey(&pCsr->base, &pKey, &nKey);
  sqlite4_buffer_set(&buf, pKey, nKey);
#endif

  assert( pCsr->base.flags & (CSR_NEXT_OK | CSR_PREV_OK) );
  assert( pCsr->iBt>=0 );

  do{
    /* Load the current key in to pKey/nKey. Then advance all sub-cursors 
    ** that share a key with the current sub-cursor. */

    }

    /* Figure out a new current bt cursor */
    if( rc==SQLITE4_OK ){
      rc = fiCsrSetCurrent(pCsr);
    }
  }while( rc==SQLITE4_OK && fiCsrIsDelete(&pCsr->aSub[pCsr->iBt].csr) );

#ifndef NDEBUG
  if( rc==SQLITE4_OK ){
    sqlite4BtCsrKey(&pCsr->base, &pKey, &nKey);
    assert( btKeyCompare(buf.p, buf.n, pKey, nKey) < 0 );
  }
  sqlite4_buffer_clear(&buf);
#endif

  return rc;
}

typedef struct FiLevelIter FiLevelIter;
struct FiLevelIter {
  /* Used internally */

};

static int fiLevelIterNext(FiLevelIter *p){
  u16 iMin, nLevel;

  p->iSub++;
  p->iLvl--;
  btReadSummary(p->aSum, p->iAge, &iMin, &nLevel, 0);
  while( p->iLvl<(int)iMin ){
    p->iAge++;
    if( p->iAge>=(p->nSum)/6 ) return 1;
    btReadSummary(p->aSum, p->iAge, &iMin, &nLevel, 0);
    p->iLvl = (int)iMin + (int)nLevel - 1;
  }

          btCsrReset(&pSub->csr, 1);
          btCsrSetup(db, iRoot, &pSub->csr);

          rc = btCsrSeek(&pSub->csr, 0, pK, nK, BT_SEEK_EQ, BT_CSRSEEK_SEEK);
          assert( rc!=SQLITE4_INEXACT );
          if( rc!=SQLITE4_NOTFOUND ){
            /* A hit on the requested key or an error has occurred. Either
            ** way, break out of the loop. If this is a hit, set iBt to
            ** zero so that the BtCsrKey() and BtCsrData() routines know
            ** to return data from the first (only) sub-cursor. */
            assert( pCsr->iBt<0 );
            if( rc==SQLITE4_OK ){
              if( 0==fiCsrIsDelete(&pSub->csr) ){
                pCsr->iBt = 0;
              }else{
                rc = SQLITE4_NOTFOUND;
              }

        *piMaxLevel = (u32)(iMin + nLevel - 1);
        *piAge = iBestAge;

        /* Find the output level */
        btReadSummary(aNew, iBestAge+1, &iMin, &nLevel, &iMerge);
        *piOutLevel = iMin + nLevel;

#if 0
        /* Update the summary record for the output segment. */
        btWriteSummary(aNew, iBestAge+1, iMin, nLevel+1, iMerge);

        /* Write the updated summary record back to the db. */
        rc = btReplaceEntry(
             db, pHdr->iMRoot, aSummaryKey, sizeof(aSummaryKey), aNew, nByte
        );
#endif
      }
    }
  }

  btCsrReset(&csr, 1);
  return rc;
}

  BtCursor mcsr;                  /* Cursor for reading the meta-tree */
  const void *pKey = 0;
  const u8 *aSum; int nSum;       /* Summary value */
  int nKey = 0;
  sqlite4_buffer buf;
  u32 iLvl;
  int iBlk;
  
  fprintf(stderr, "BEFORE!\n");
  btPrintMetaTree(db->pPager, 1, pHdr);
  assert_summary_ok(db);

  memset(&csr, 0, sizeof(csr));
  memset(&mcsr, 0, sizeof(mcsr));
  btCsrSetup(db, pHdr->iMRoot, &mcsr);
  sqlite4_buffer_init(&buf, 0);
  
  if( p->iNextPg ){
    btCsrSetup(db, p->iNextPg, &csr);
    rc = btCsrEnd(&csr, 0);
    if( rc==SQLITE4_OK ){
      csr.aiCell[0] = p->iNextCell;
      rc = btCsrKey(&csr, &pKey, &nKey);
    }
  }

  /* The following loop iterates through each of the input levels. Each
  ** level is either removed from the database completely (if the merge
  ** completed) or else modified so that it contains no keys smaller
  ** than (pKey/nKey).  */ 
  for(iLvl=p->iMinLevel; iLvl<=p->iMaxLevel; iLvl++){
    u8 aPrefix[8];
    u32 iRoot = 0;
    btPutU32(&aPrefix[0], p->iAge);
    btPutU32(&aPrefix[4], ~iLvl);

    rc = btCsrSeek(&mcsr, 0, aPrefix, sizeof(aPrefix), BT_SEEK_GE, 0);
    if( rc==SQLITE4_INEXACT ) rc = SQLITE4_OK;
    while( rc==SQLITE4_OK ){
      const u8 *pMKey; int nMKey;
      rc = btCsrKey(&mcsr, (const void **)&pMKey, &nMKey);

      if( rc==SQLITE4_OK ){
        if( nMKey<sizeof(aPrefix) || memcmp(aPrefix, pMKey, sizeof(aPrefix)) ){
          rc = SQLITE4_NOTFOUND;
        }else{
          rc = SQLITE4_OK;
        }
      }
      if( rc==SQLITE4_OK ){
        if( pKey ){
          const void *pData; int nData;
          int res = btKeyCompare(pMKey + 8, nMKey - 8, pKey, nKey);
          if( res>=0 ){

            break;
          }
          btCsrData(&mcsr, 0, 4, &pData, &nData);
          iRoot = btGetU32(pData);

        }
        rc = sqlite4BtDelete(&mcsr.base);
      }

      if( rc==SQLITE4_OK ){
        /* rc = btCsrStep(&mcsr, 1); */
        rc = btCsrSeek(&mcsr, 0, aPrefix, sizeof(aPrefix), BT_SEEK_GE, 0);
        if( rc==SQLITE4_INEXACT ) rc = SQLITE4_OK;
      }
    }

    if( rc==SQLITE4_NOTFOUND ){
      rc = SQLITE4_OK;
    }else if( rc==SQLITE4_OK && iRoot ){
      int n = sizeof(aPrefix) + nKey;
      rc = sqlite4_buffer_resize(&buf, n);
      if( rc==SQLITE4_OK ){
        u8 aData[4];
        u8 *a = (u8*)buf.p;
        memcpy(a, aPrefix, sizeof(aPrefix));
        memcpy(&a[sizeof(aPrefix)], pKey, nKey);

      btPutU32(&a[4], ~p->iOutLevel);
      memcpy(&a[8], pKey, nKey);
      btPutU32(aData, p->aRoot[iBlk]);
      rc = btReplaceEntry(db, pHdr->iMRoot, a, nKey+8, aData, sizeof(aData));
    }
  }

  /* Update the summary record with the outcome of the merge operation.
  */
  if( rc==SQLITE4_OK ){
    btCsrReset(&csr, 1);
    rc = fiLoadSummary(db, &csr, &aSum, &nSum);
  }
  if( rc==SQLITE4_OK ){
    rc = sqlite4_buffer_resize(&buf, MAX(nSum, (p->iAge+1+1)*6));
    if( rc==SQLITE4_OK ){
      u16 iMinLevel = 0;
      u16 nLevel = 0;
      u16 iMergeLevel = 0;

      memcpy(buf.p, aSum, nSum);
      if( nSum>(6*(p->iAge+1)) ){
        btReadSummary(aSum, p->iAge+1, &iMinLevel, &nLevel, &iMergeLevel);
      }
      if( (iMinLevel+nLevel)>=p->iOutLevel ){


        nLevel = p->iOutLevel - iMinLevel + 1;
        btWriteSummary((u8*)buf.p, p->iAge+1, iMinLevel, nLevel, iMergeLevel);
      }

      btReadSummary(aSum, p->iAge, &iMinLevel, &nLevel, &iMergeLevel);
      if( p->iNextPg==0 ){
        u16 nNewLevel = nLevel - (1 + p->iMaxLevel - p->iMinLevel);
        iMinLevel = (nNewLevel==0 ? 0 : p->iMaxLevel+1);
        btWriteSummary((u8*)buf.p, p->iAge, iMinLevel, nNewLevel, 0);
      }else{
        btWriteSummary((u8*)buf.p, p->iAge, iMinLevel, nLevel, p->iMaxLevel);
      }

      rc = btReplaceEntry(
          db, pHdr->iMRoot, aSummaryKey, sizeof(aSummaryKey), buf.p, buf.n
      );

    }
  }

  btCsrReset(&csr, 1);
  btCsrReset(&mcsr, 1);
  sqlite4_buffer_clear(&buf);

#if 1
  if( rc==SQLITE4_OK ){
    btPrintMetaTree(db->pPager, 1, pHdr);
    assert_summary_ok(db);
  }
#endif
  return rc;
}

/*
** If possible, schedule a merge operation. 
**
** The merge operation is selected based on the following criteria:

  /* Check if the schedule page is busy. If so, no new merge may be 
  ** scheduled. If the schedule page is not busy, call btFindMerge() to
  ** figure out which levels should be scheduled for merge.  */
  if( rc==SQLITE4_OK ){
    aData = sqlite4BtPageData(pPg);
    
    switch( btGetU32(aData) ){

      case BT_SCHEDULE_BUSY:
        rc = SQLITE4_NOTFOUND;
        break;

      case BT_SCHEDULE_DONE: {
        BtSchedule s;
        rc = btReadSchedule(db, aData, &s);
        if( rc==SQLITE4_OK ){
          rc = btIntegrateMerge(db, &s);
        }
        if( rc==SQLITE4_OK ){
          s.eBusy = BT_SCHEDULE_EMPTY;
          btWriteSchedulePage(pPg, &s, &rc);

        }
        break;
      }

      default: /* BT_SCHEDULE_EMPTY */
        break;
    }

**
** No page number is assigned at this point.
*/
static int fiWriterAlloc(FiWriter *p, int bLeaf, FiWriterPg *pPg){
  int rc = SQLITE4_OK;

  assert( pPg->bAllocated==0 );
  assert( p->nAlloc<p->nPgPerBlk );

  pPg->bAllocated = 1;
  p->nAlloc++;
  pPg->nCell = 0;

  if( pPg->aBuf==0 ){
    rc = btNewBuffer(p->db, &pPg->aBuf);
  }
  if( rc==SQLITE4_OK ){
    if( bLeaf ){
      pPg->iFree = 1;
      pPg->aBuf[0] = 0x00;
    }else{
      pPg->iFree = 5;
      pPg->aBuf[0] = BT_PGFLAGS_INTERNAL;
    }
    btPutU16(&pPg->aBuf[p->pgsz-2], 0);
  }
  return rc;
}

static int fiWriterPush(FiWriter *p, const u8 *pKey, int nKey){
  int rc = SQLITE4_OK;
  int i;                          /* Iterator variable */

    /* Check if the key will fit on page FiWriter.aHier[iIns]. If so,
    ** break out of the loop. */
    int nFree;
    pPg = &p->aHier[iIns];
    nFree = p->pgsz - (pPg->iFree + 6 + pPg->nCell*2);
    if( nFree>=nByte ) break;
  }

  if( (iIns + (iIns==p->nHier))>=nMaxAlloc ){
    rc = BT_BLOCKFULL;
  }
  if( rc==SQLITE4_OK && iIns==p->nHier ){
    p->nHier = iIns+1;
    rc = fiWriterAlloc(p, 0, &p->aHier[iIns]);
  }





  for(i=0; rc==SQLITE4_OK && i<iIns; i++){
    pPg = &p->aHier[i];
    if( i!=0 ){
      btPutU32(&pPg->aBuf[1], pgno);
    }
    rc = fiWriterFlush(p, pPg, &pgno);
    if( rc==SQLITE4_OK ){