/*
** This struct defines the format of database "schedule" pages.
*/
typedef struct BtSchedule BtSchedule;
struct BtSchedule {
  u32 bBusy;                      /* True if page is busy */
  u32 iAge;                       /* Age of input segments */
  u32 iMinLevel;                  /* Minimum level of input segments */
  u32 iMaxLevel;                  /* Maximum level of input segments */
  u32 iOutLevel;                  /* Level at which to write output */
  u32 aBlock[32];                 /* Allocated blocks */

  u32 iNextPg;                    /* Page that contains next input key */
  u32 iNextCell;                  /* Cell that contains next input key */
  u32 iFreeList;                  /* First page of new free-list (if any) */
  u32 aRoot[32];                  /* Root pages for populated blocks */
};





int sqlite4BtMerge(bt_db *db, BtDbHdr *pHdr, u8 *aSched);

/*************************************************************************
** Interface to bt_pager.c functionality.
*/
typedef struct BtPage BtPage;

/*
** This struct defines the format of database "schedule" pages.
*/
typedef struct BtSchedule BtSchedule;
struct BtSchedule {
  u32 eBusy;                      /* One of the BT_SCHEDULE_XXX constants */
  u32 iAge;                       /* Age of input segments */
  u32 iMinLevel;                  /* Minimum level of input segments */
  u32 iMaxLevel;                  /* Maximum level of input segments */
  u32 iOutLevel;                  /* Level at which to write output */
  u32 aBlock[32];                 /* Allocated blocks */

  u32 iNextPg;                    /* Page that contains next input key */
  u32 iNextCell;                  /* Cell that contains next input key */
  u32 iFreeList;                  /* First page of new free-list (if any) */
  u32 aRoot[32];                  /* Root pages for populated blocks */
};

#define BT_SCHEDULE_EMPTY 0
#define BT_SCHEDULE_BUSY  1
#define BT_SCHEDULE_DONE  2

int sqlite4BtMerge(bt_db *db, BtDbHdr *pHdr, u8 *aSched);

/*************************************************************************
** Interface to bt_pager.c functionality.
*/
typedef struct BtPage BtPage;

/*
** TODO: Rearrange things so these are not required!
*/
static int fiLoadSummary(bt_db *, BtCursor *, const u8 **, int *);
static void btReadSummary(const u8 *, int, u16 *, u16 *, u16 *);
static int btCsrData(BtCursor *, int, int, const void **, int *);


/* 
** Meta-table summary key.
*/
static const u8 aSummaryKey[] = {0xFF, 0xFF, 0xFF, 0xFF};

#ifndef btErrorBkpt
................................................................................
#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 = 4;
  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);
................................................................................

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

  if( pgno==pHdr->iSRoot ){
    int i;
    BtSchedule s;
    sqlite4BtBufAppendf(pBuf, "(schedule page) ");
    memcpy(&s, aData, sizeof(s));

    sqlite4BtBufAppendf(pBuf, "  bBusy=%d\n", (int)s.bBusy);




    sqlite4BtBufAppendf(pBuf, "  iAge=%d\n", (int)s.iAge);
    sqlite4BtBufAppendf(pBuf, "  iMinLevel=%d\n", (int)s.iMinLevel);
    sqlite4BtBufAppendf(pBuf, "  iMaxLevel=%d\n", (int)s.iMaxLevel);
    sqlite4BtBufAppendf(pBuf, "  iOutLevel=%d\n", (int)s.iOutLevel);
    sqlite4BtBufAppendf(pBuf, "  aBlock=(");
    for(i=0; s.aBlock[i] && i<array_size(s.aBlock); i++){
      sqlite4BtBufAppendf(pBuf, "%s%d", i==0 ? "" : " ", (int)s.aBlock[i]);
................................................................................
        }
      }
      if( pVal ){
        btBufferAppendBlob(pBuf, bAscii, pVal, nVal);
        if( flags & BT_PGFLAGS_METATREE ){
          /* Interpret the meta-tree entry */
          if( nKey==sizeof(aSummaryKey) && 0==memcmp(pKey, aSummaryKey, nKey) ){


            sqlite4BtBufAppendf(pBuf, "  [summary]");








          }else{
            u32 iAge = btGetU32(&pKey[0]);
            u32 iLevel = ~btGetU32(&pKey[4]);
            u32 iBlk = btGetU32(pVal);
            sqlite4BtBufAppendf(pBuf, "  [age=%d level=%d root=%d]", 
                (int)iAge, (int)iLevel, (int)iBlk
                );
          }
        }
      }
      sqlite4BtBufAppendf(pBuf, "\n");
    }

    if( pPager && btFlags(aData) & BT_PGFLAGS_INTERNAL ){
      for(i=0; i<btCellCount(aData, nData); i++){
        BtPage *pChild;
        u8 *aChild;
        u32 child;

        child = btChildPgno(aData, nData, i);
        sqlite4BtPageGet(pPager, child, &pChild);
        aChild = sqlite4BtPageData(pChild);
................................................................................

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

static void btWriteSchedule(u8 *aData, BtSchedule *p, int *pRc){
  if( *pRc==SQLITE4_OK ){
    /* TODO: convert values to big-endian format */

    memcpy(aData, p, sizeof(BtSchedule));


  }
}
static int btReadSchedule(bt_db *db, u8 *aData, BtSchedule *p){
  /* TODO: convert values to big-endian format */

  memcpy(p, aData, sizeof(BtSchedule));


  return SQLITE4_OK;
}

static void btWriteSchedulePage(BtPage *pPg, BtSchedule *p, int *pRc){
  if( *pRc==SQLITE4_OK ){
    int rc = sqlite4BtPageWrite(pPg);
    if( rc==SQLITE4_OK ){
................................................................................
    }
  }

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






































































































































/*
** If possible, schedule a merge operation. 
**
** The merge operation is selected based on the following criteria:
**
**   * The more levels involved in the merge the better, and
................................................................................
  }

  /* 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);

    if( btGetU32(aData) ){


      rc = SQLITE4_NOTFOUND;
    }else{





















      rc = btFindMerge(db, &iAge, &iMin, &iMax, &iOutLvl);
    }
  }

  if( rc==SQLITE4_OK ){
    BtSchedule s;
    memset(&s, 0, sizeof(BtSchedule));

    s.bBusy = 1;
    s.iAge = iAge;
    s.iMaxLevel = iMax;
    s.iMinLevel = iMin;
    s.iOutLevel = iOutLvl;
    rc = btAllocateBlock(db, db->nScheduleAlloc, s.aBlock);

    btWriteSchedulePage(pPg, &s, &rc);
................................................................................
*/
int sqlite4BtMerge(bt_db *db, BtDbHdr *pHdr, u8 *aSched){
  BtSchedule s;                   /* Deserialized schedule object */
  int rc = SQLITE4_OK;            /* Return code */

  /* Set up the input cursor. */
  btReadSchedule(db, aSched, &s);
  if( s.bBusy ){
    FiCursor fcsr;                /* FiCursor used to read input */
    FiWriter writer;              /* FiWriter used to write output */

    rc = fiSetupMergeCsr(db, pHdr, &s, &fcsr);
    fiWriterInit(db, &s, &writer, &rc);

    /* The following loop runs once for each key copied from the input to
................................................................................
      }
    }

    /* Assuming no error has occurred, update the serialized BtSchedule
    ** structure stored in buffer aSched[]. The caller will write this
    ** buffer to the database file as page (pHdr->iSRoot).  */
    if( rc==BT_BLOCKFULL || rc==SQLITE4_NOTFOUND ){














      rc = fiWriterFlushAll(&writer);
      if( rc==SQLITE4_OK ){
        btWriteSchedule(aSched, &s, &rc);
      }
    }

    fiWriterCleanup(&writer);

/*
** TODO: Rearrange things so these are not required!
*/
static int fiLoadSummary(bt_db *, BtCursor *, const u8 **, int *);
static void btReadSummary(const u8 *, int, u16 *, u16 *, u16 *);
static int btCsrData(BtCursor *, int, int, const void **, int *);
static int btReadSchedule(bt_db *, u8 *, BtSchedule *);

/* 
** Meta-table summary key.
*/
static const u8 aSummaryKey[] = {0xFF, 0xFF, 0xFF, 0xFF};

#ifndef btErrorBkpt
................................................................................
#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 = 4;
  static const int SCHEDULE_ALLOC = 1;

  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);
................................................................................

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

  if( 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" :
        s.eBusy==BT_SCHEDULE_BUSY ? "busy" :
        s.eBusy==BT_SCHEDULE_DONE ? "done" : "!ErroR"
    );
    sqlite4BtBufAppendf(pBuf, "  iAge=%d\n", (int)s.iAge);
    sqlite4BtBufAppendf(pBuf, "  iMinLevel=%d\n", (int)s.iMinLevel);
    sqlite4BtBufAppendf(pBuf, "  iMaxLevel=%d\n", (int)s.iMaxLevel);
    sqlite4BtBufAppendf(pBuf, "  iOutLevel=%d\n", (int)s.iOutLevel);
    sqlite4BtBufAppendf(pBuf, "  aBlock=(");
    for(i=0; s.aBlock[i] && i<array_size(s.aBlock); i++){
      sqlite4BtBufAppendf(pBuf, "%s%d", i==0 ? "" : " ", (int)s.aBlock[i]);
................................................................................
        }
      }
      if( pVal ){
        btBufferAppendBlob(pBuf, bAscii, pVal, nVal);
        if( flags & BT_PGFLAGS_METATREE ){
          /* Interpret the meta-tree entry */
          if( nKey==sizeof(aSummaryKey) && 0==memcmp(pKey, aSummaryKey, nKey) ){
            u16 iMin, nLvl, iMerge;
            int j;
            sqlite4BtBufAppendf(pBuf, "  [summary:");
            for(j=0; j<(nVal/6); j++){
              btReadSummary(pVal, j, &iMin, &nLvl, &iMerge);
              sqlite4BtBufAppendf(pBuf, " %d/%d/%d", 
                  (int)iMin, (int)nLvl, (int)iMerge
              );
            }
            sqlite4BtBufAppendf(pBuf, "]");
            
          }else{
            u32 iAge = btGetU32(&pKey[0]);
            u32 iLevel = ~btGetU32(&pKey[4]);
            u32 iBlk = btGetU32(pVal);
            sqlite4BtBufAppendf(pBuf, "  [age=%d level=%d root=%d]", 
                (int)iAge, (int)iLevel, (int)iBlk
            );
          }
        }
      }
      sqlite4BtBufAppendf(pBuf, "\n");
    }

    if( pPager && btFlags(aData) & BT_PGFLAGS_INTERNAL ){
      for(i=0; i<=btCellCount(aData, nData); i++){
        BtPage *pChild;
        u8 *aChild;
        u32 child;

        child = btChildPgno(aData, nData, i);
        sqlite4BtPageGet(pPager, child, &pChild);
        aChild = sqlite4BtPageData(pChild);
................................................................................

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

static void btWriteSchedule(u8 *aData, BtSchedule *p, int *pRc){
  if( *pRc==SQLITE4_OK ){
    u32 *a = (u32*)p;
    int i;
    for(i=0; i<sizeof(BtSchedule)/sizeof(u32); i++){
      btPutU32(&aData[i*4], a[i]);
    }
  }
}
static int btReadSchedule(bt_db *db, u8 *aData, BtSchedule *p){
  u32 *a = (u32*)p;
  int i;
  for(i=0; i<sizeof(BtSchedule)/sizeof(u32); i++){
    a[i] = btGetU32(&aData[i*4]);
  }
  return SQLITE4_OK;
}

static void btWriteSchedulePage(BtPage *pPg, BtSchedule *p, int *pRc){
  if( *pRc==SQLITE4_OK ){
    int rc = sqlite4BtPageWrite(pPg);
    if( rc==SQLITE4_OK ){
................................................................................
    }
  }

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

/*
** The connection passed as the first argument to this function currently
** has a write transaction open. The schedule object passed as the second
** is in BT_SCHEDULE_DONE state. This function updates the meta-tree to
** integrate the results of the completed merge into the main fast-insert
** tree structure.
**
** If successful, SQLITE4_OK is returned. If an error occurs, an SQLite
** error code.
*/ 
static int btIntegrateMerge(bt_db *db, BtSchedule *p){
  BtDbHdr *pHdr = sqlite4BtPagerDbhdr(db->pPager);
  int rc = SQLITE4_OK;
  BtCursor csr;                   /* Cursor for reading various sub-trees */
  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;

  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);
    }
  }

  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 && iRoot==0 ){
      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;
        }
      }
      if( rc==SQLITE4_OK ){
        if( pKey ){
          int res = btKeyCompare(pMKey + 8, nMKey - 8, pKey, nKey);
          if( res<=0 ){
            const void *pData; int nData;
            btCsrData(&mcsr, 0, 4, &pData, &nData);
            iRoot = btGetU32(pData);
          }
        }
        rc = sqlite4BtDelete(&mcsr.base);
      }
    }

    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(aData, iRoot);
        rc = btReplaceEntry(db, pHdr->iMRoot, a, n, aData, sizeof(aData));
      }
    }
  }

  /* Add new entries for the new output level blocks. */
  for(iBlk=0; 
      rc==SQLITE4_OK && iBlk<array_size(p->aRoot) && p->aRoot[iBlk]; 
      iBlk++
  ){
    btCsrReset(&csr, 1);
    btCsrSetup(db, p->aRoot[iBlk], &csr);
    rc = btCsrEnd(&csr, 0);
    if( rc==SQLITE4_OK ){
      rc = btCsrKey(&csr, &pKey, &nKey);
    }
    if( rc==SQLITE4_OK ){
      rc = sqlite4_buffer_resize(&buf, nKey+8);
    }
    if( rc==SQLITE4_OK ){
      u8 aData[4];
      u8 *a = (u8*)buf.p;
      btPutU32(a, p->iAge+1);
      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));
    }
  }

  btCsrReset(&csr, 1);
  rc = fiLoadSummary(db, &csr, &aSum, &nSum);
  if( rc==SQLITE4_OK ){
    u16 iMinLevel = 0;
    u16 nLevel = 0;
    u16 iMergeLevel = 0;
    if( nSum>(6*(p->iAge+1)) ){
      btReadSummary(aSum, p->iAge+1, &iMinLevel, &nLevel, &iMergeLevel);
    }
    if( (iMinLevel+nLevel)>p->iOutLevel ){
      rc = sqlite4_buffer_resize(&buf, MAX(nSum, (p->iOutLevel+1)*6));
      if( rc==SQLITE4_OK ){
        nLevel = p->iOutLevel - iMinLevel + 1;
        memcpy(buf.p, aSum, nSum);
        btWriteSummary((u8*)buf.p, p->iAge+1, iMinLevel, nLevel, iMergeLevel);
        rc = btReplaceEntry(
             db, pHdr->iMRoot, aSummaryKey, sizeof(aSummaryKey), buf.p, buf.n
        );
      }
    }
  }

  btCsrReset(&csr, 1);
  btCsrReset(&mcsr, 1);
  sqlite4_buffer_clear(&buf);
  return rc;
}

/*
** If possible, schedule a merge operation. 
**
** The merge operation is selected based on the following criteria:
**
**   * The more levels involved in the merge the better, and
................................................................................
  }

  /* 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 555:
      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 = 555;
          btWriteSchedulePage(pPg, &s, &rc);
          rc = SQLITE4_NOTFOUND;
        }
        break;
      }

      default: /* BT_SCHEDULE_EMPTY */
        break;
    }

    if( rc==SQLITE4_OK ){
      rc = btFindMerge(db, &iAge, &iMin, &iMax, &iOutLvl);
    }
  }

  if( rc==SQLITE4_OK ){
    BtSchedule s;
    memset(&s, 0, sizeof(BtSchedule));

    s.eBusy = BT_SCHEDULE_BUSY;
    s.iAge = iAge;
    s.iMaxLevel = iMax;
    s.iMinLevel = iMin;
    s.iOutLevel = iOutLvl;
    rc = btAllocateBlock(db, db->nScheduleAlloc, s.aBlock);

    btWriteSchedulePage(pPg, &s, &rc);
................................................................................
*/
int sqlite4BtMerge(bt_db *db, BtDbHdr *pHdr, u8 *aSched){
  BtSchedule s;                   /* Deserialized schedule object */
  int rc = SQLITE4_OK;            /* Return code */

  /* Set up the input cursor. */
  btReadSchedule(db, aSched, &s);
  if( s.eBusy==BT_SCHEDULE_BUSY ){
    FiCursor fcsr;                /* FiCursor used to read input */
    FiWriter writer;              /* FiWriter used to write output */

    rc = fiSetupMergeCsr(db, pHdr, &s, &fcsr);
    fiWriterInit(db, &s, &writer, &rc);

    /* The following loop runs once for each key copied from the input to
................................................................................
      }
    }

    /* Assuming no error has occurred, update the serialized BtSchedule
    ** structure stored in buffer aSched[]. The caller will write this
    ** buffer to the database file as page (pHdr->iSRoot).  */
    if( rc==BT_BLOCKFULL || rc==SQLITE4_NOTFOUND ){

      if( rc==SQLITE4_NOTFOUND ){
        assert( fcsr.iBt<0 );
        s.iNextPg = 0;
        s.iNextCell = 0;
      }else{
        BtCursor *pCsr = &fcsr.aSub[fcsr.iBt].csr;
        assert( pCsr->nPg>0 );
        s.iNextPg = sqlite4BtPagePgno(pCsr->apPage[pCsr->nPg-1]);
        s.iNextCell = pCsr->aiCell[pCsr->nPg-1];
      }
      s.iFreeList = 0;
      s.eBusy = BT_SCHEDULE_DONE;

      rc = fiWriterFlushAll(&writer);
      if( rc==SQLITE4_OK ){
        btWriteSchedule(aSched, &s, &rc);
      }
    }

    fiWriterCleanup(&writer);