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

  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.
**
................................................................................
  return (iBlk - 1) * (pHdr->blksz / pHdr->pgsz) + 1;
}

/*
** Return true if the cell that the argument cursor currently points to
** is a delete marker.
*/
static int fiCsrIsDelete(BtCursor *pCsr){
  const int pgsz = sqlite4BtPagerPagesize(pCsr->base.pDb->pPager);
  int bRet;                       /* Return value */
  u8 *aData;
  u8 *pCell;
  int n;

  aData = sqlite4BtPageData(pCsr->apPage[pCsr->nPg-1]);
................................................................................
    pCell += n;
    pCell += sqlite4BtVarintGet32(pCell, &n);
    bRet = (n==1);
  }

  return bRet;
}










/*
** Return an integer representing the result of (K1 - K2).
*/
static int btKeyCompare(
  const void *pKey1, int nKey1, 
  const void *pKey2, int nKey2
................................................................................
){
  int rc;

  rc = btCsrStep(&pSub->csr, bNext);
  if( rc==SQLITE4_NOTFOUND ){
    const void *pV;
    int nV;
#if 1



    rc = btCsrKey(&pSub->mcsr, &pV, &nV);
    assert( rc==SQLITE4_OK && memcmp(pV, pSub->aPrefix, 8)==0 );
#endif
    rc = btCsrStep(&pSub->mcsr, bNext);


    if( rc==SQLITE4_OK ){
      rc = btCsrKey(&pSub->mcsr, &pV, &nV);
    }
    if( rc==SQLITE4_OK ){
      if( nV<sizeof(pSub->aPrefix) 
       || memcmp(pSub->aPrefix, pV, sizeof(pSub->aPrefix)) 
      ){
................................................................................
      }
    }

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

................................................................................
static int fiCsrSeek(FiCursor *pCsr, const void *pK, int nK, int eSeek){
  u8 aPrefix[8];
  int rc = SQLITE4_NOTFOUND;      /* Return code */
  bt_db *db = pCsr->base.pDb;     /* Database handle */
  BtDbHdr *pHdr = sqlite4BtPagerDbhdr(db->pPager);

  assert( eSeek==BT_SEEK_LE || eSeek==BT_SEEK_EQ || eSeek==BT_SEEK_GE );

  fiCsrReset(pCsr);

  if( pHdr->iMRoot ){
    FiLevelIter iter;

    /* Initialize the iterator used to skip through database levels */
    rc = fiLevelIterInit(db, &iter);
................................................................................
          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;
              }
            }
            break;
          }
................................................................................
      }
      assert( rc!=SQLITE4_OK || iter.iSub==iter.nSub );

      if( rc==SQLITE4_OK ){
        pCsr->base.flags |= (eSeek==BT_SEEK_GE ? CSR_NEXT_OK : CSR_PREV_OK);
        rc = fiCsrSetCurrent(pCsr);
        if( rc==SQLITE4_OK ){
          BtCursor *pCurrent = &pCsr->aSub[pCsr->iBt].csr;
          if( fiCsrIsDelete(pCurrent) ){
            rc = fiCsrStep(pCsr);
            if( rc==SQLITE4_OK ) rc = SQLITE4_INEXACT;
          }else if( bMatch==0 ){
            rc = (bHit ? SQLITE4_INEXACT : SQLITE4_NOTFOUND);
          }
        }
      }
................................................................................
}

static int fiCsrEnd(FiCursor *pCsr, int bLast){
  bt_db *db = pCsr->base.pDb;
  BtDbHdr *pHdr = sqlite4BtPagerDbhdr(db->pPager);
  FiLevelIter iter;         /* Used to iterate through all f-tree levels */
  int rc;                   /* Return code */



  rc = fiLevelIterInit(db, &iter);
  if( rc==SQLITE4_OK ){
    rc = fiCsrAllocateSubs(db, pCsr, iter.nSub);
  }

  while( rc==SQLITE4_OK && 0==fiLevelIterNext(&iter) ){
................................................................................
  }
  fiLevelIterCleanup(&iter);

  if( rc==SQLITE4_OK ){
    pCsr->base.flags &= ~(CSR_NEXT_OK | CSR_PREV_OK);
    pCsr->base.flags |= (bLast ? CSR_PREV_OK : CSR_NEXT_OK);
    rc = fiCsrSetCurrent(pCsr);
    if( rc==SQLITE4_OK && fiCsrIsDelete(&pCsr->aSub[pCsr->iBt].csr) ){
      rc = fiCsrStep(pCsr);
    }
  }

  return rc;
}

................................................................................
        }
      }
    }

    if( rc==SQLITE4_NOTFOUND && iBestAge>=0 ){
      u8 *aNew;
      int nByte = nSum;
      if( iAge+1>=(nSum/3) ) nByte += 6;

      rc = SQLITE4_OK;
      aNew = (u8*)btMalloc(db, nByte, &rc);
      if( rc==SQLITE4_OK ){
        BtDbHdr *pHdr = sqlite4BtPagerDbhdr(db->pPager);

        /* Create a copy of the summary record */
................................................................................
  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 ){
................................................................................
    }
  }

  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:
................................................................................
      if( rc==SQLITE4_OK ){
        u32 iRoot = sqlite4BtGetU32((const u8*)pVal);
        btCsrSetup(db, iRoot, &pSub->csr);
        rc = btCsrSeek(&pSub->csr, 0, pKey, nKey, BT_SEEK_GE, 0);
        if( rc==SQLITE4_INEXACT ) rc = SQLITE4_OK;
        if( rc==SQLITE4_NOTFOUND ) rc = btErrorBkpt(SQLITE4_CORRUPT);
      }



    }
  }

  if( rc==SQLITE4_OK ){
    rc = fiCsrSetCurrent(pCsr);
  }

................................................................................
  /* 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
    ** the output segments. It terminates either when the input is exhausted
    ** or when all available output blocks are full.  */
    while( rc==SQLITE4_OK ){
      const void *pCell;          /* Cell to copy to output */
................................................................................

      /* Read the current cell from the input and push it to the output. */
      fiCsrCell(&fcsr, &pCell, &nCell);
      rc = fiWriterAdd(&writer, pCell, nCell);
      if( rc==BT_BLOCKFULL ){
        rc = fiWriterFlushAll(&writer);
        fiWriterInit(db, &s, &writer, &rc);
      }
      if( rc==SQLITE4_OK ){
        rc = fiCsrStep(&fcsr);
      }
    }

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

/*
** 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, int crc){
  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];

  if( crc!=SQLITE4_OK ) return;

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

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

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


/*
** This function compares the key passed via parameters pK and nK to the
** key that cursor pCsr currently points to.
**
................................................................................
  return (iBlk - 1) * (pHdr->blksz / pHdr->pgsz) + 1;
}

/*
** Return true if the cell that the argument cursor currently points to
** is a delete marker.
*/
static int btCsrIsDelete(BtCursor *pCsr){
  const int pgsz = sqlite4BtPagerPagesize(pCsr->base.pDb->pPager);
  int bRet;                       /* Return value */
  u8 *aData;
  u8 *pCell;
  int n;

  aData = sqlite4BtPageData(pCsr->apPage[pCsr->nPg-1]);
................................................................................
    pCell += n;
    pCell += sqlite4BtVarintGet32(pCell, &n);
    bRet = (n==1);
  }

  return bRet;
}

static int fiCsrIsDelete(FiCursor *pCsr){
  int res = 0;
  if( (pCsr->base.flags & CSR_VISIT_DEL)==0 ){
    BtCursor *p = &pCsr->aSub[pCsr->iBt].csr;
    res = btCsrIsDelete(p);
  }
  return res;
}

/*
** Return an integer representing the result of (K1 - K2).
*/
static int btKeyCompare(
  const void *pKey1, int nKey1, 
  const void *pKey2, int nKey2
................................................................................
){
  int rc;

  rc = btCsrStep(&pSub->csr, bNext);
  if( rc==SQLITE4_NOTFOUND ){
    const void *pV;
    int nV;


#ifndef NDEBUG
    const void *pTmp; int nTmp;
    rc = btCsrKey(&pSub->mcsr, &pTmp, &nTmp);
    assert( rc==SQLITE4_OK && memcmp(pTmp, pSub->aPrefix, 8)==0 );
#endif


    rc = btCsrStep(&pSub->mcsr, bNext);
    if( rc==SQLITE4_OK ){
      rc = btCsrKey(&pSub->mcsr, &pV, &nV);
    }
    if( rc==SQLITE4_OK ){
      if( nV<sizeof(pSub->aPrefix) 
       || memcmp(pSub->aPrefix, pV, sizeof(pSub->aPrefix)) 
      ){
................................................................................
      }
    }

    /* Figure out a new current bt cursor */
    if( rc==SQLITE4_OK ){
      rc = fiCsrSetCurrent(pCsr);
    }
  }while( rc==SQLITE4_OK && fiCsrIsDelete(pCsr) );

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

  return rc;
}

................................................................................
static int fiCsrSeek(FiCursor *pCsr, const void *pK, int nK, int eSeek){
  u8 aPrefix[8];
  int rc = SQLITE4_NOTFOUND;      /* Return code */
  bt_db *db = pCsr->base.pDb;     /* Database handle */
  BtDbHdr *pHdr = sqlite4BtPagerDbhdr(db->pPager);

  assert( eSeek==BT_SEEK_LE || eSeek==BT_SEEK_EQ || eSeek==BT_SEEK_GE );
  assert( (pCsr->base.flags & CSR_VISIT_DEL)==0 || eSeek==BT_SEEK_GE );
  fiCsrReset(pCsr);

  if( pHdr->iMRoot ){
    FiLevelIter iter;

    /* Initialize the iterator used to skip through database levels */
    rc = fiLevelIterInit(db, &iter);
................................................................................
          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==btCsrIsDelete(&pSub->csr) ){
                pCsr->iBt = 0;
              }else{
                rc = SQLITE4_NOTFOUND;
              }
            }
            break;
          }
................................................................................
      }
      assert( rc!=SQLITE4_OK || iter.iSub==iter.nSub );

      if( rc==SQLITE4_OK ){
        pCsr->base.flags |= (eSeek==BT_SEEK_GE ? CSR_NEXT_OK : CSR_PREV_OK);
        rc = fiCsrSetCurrent(pCsr);
        if( rc==SQLITE4_OK ){

          if( fiCsrIsDelete(pCsr) ){
            rc = fiCsrStep(pCsr);
            if( rc==SQLITE4_OK ) rc = SQLITE4_INEXACT;
          }else if( bMatch==0 ){
            rc = (bHit ? SQLITE4_INEXACT : SQLITE4_NOTFOUND);
          }
        }
      }
................................................................................
}

static int fiCsrEnd(FiCursor *pCsr, int bLast){
  bt_db *db = pCsr->base.pDb;
  BtDbHdr *pHdr = sqlite4BtPagerDbhdr(db->pPager);
  FiLevelIter iter;         /* Used to iterate through all f-tree levels */
  int rc;                   /* Return code */

  assert( (pCsr->base.flags & CSR_VISIT_DEL)==0 );

  rc = fiLevelIterInit(db, &iter);
  if( rc==SQLITE4_OK ){
    rc = fiCsrAllocateSubs(db, pCsr, iter.nSub);
  }

  while( rc==SQLITE4_OK && 0==fiLevelIterNext(&iter) ){
................................................................................
  }
  fiLevelIterCleanup(&iter);

  if( rc==SQLITE4_OK ){
    pCsr->base.flags &= ~(CSR_NEXT_OK | CSR_PREV_OK);
    pCsr->base.flags |= (bLast ? CSR_PREV_OK : CSR_NEXT_OK);
    rc = fiCsrSetCurrent(pCsr);
    if( rc==SQLITE4_OK && btCsrIsDelete(&pCsr->aSub[pCsr->iBt].csr) ){
      rc = fiCsrStep(pCsr);
    }
  }

  return rc;
}

................................................................................
        }
      }
    }

    if( rc==SQLITE4_NOTFOUND && iBestAge>=0 ){
      u8 *aNew;
      int nByte = nSum;
      if( iBestAge+1>=(nSum/6) ) nByte += 6;

      rc = SQLITE4_OK;
      aNew = (u8*)btMalloc(db, nByte, &rc);
      if( rc==SQLITE4_OK ){
        BtDbHdr *pHdr = sqlite4BtPagerDbhdr(db->pPager);

        /* Create a copy of the summary record */
................................................................................
  const void *pKey = 0;
  const u8 *aSum; int nSum;       /* Summary value */
  int nKey = 0;
  sqlite4_buffer buf;
  u32 iLvl;
  int iBlk;
  
#if 0
  fprintf(stderr, "BEFORE!\n");
  btPrintMetaTree(db->pPager, 1, pHdr);
#endif
  assert_summary_ok(db, SQLITE4_OK);

  memset(&csr, 0, sizeof(csr));
  memset(&mcsr, 0, sizeof(mcsr));
  btCsrSetup(db, pHdr->iMRoot, &mcsr);
  sqlite4_buffer_init(&buf, 0);
  
  if( p->iNextPg ){
................................................................................
    }
  }

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

#if 0
  if( rc==SQLITE4_OK ){
    btPrintMetaTree(db->pPager, 1, pHdr);

  }
#endif
  assert_summary_ok(db, SQLITE4_OK);
  return rc;
}

/*
** If possible, schedule a merge operation. 
**
** The merge operation is selected based on the following criteria:
................................................................................
      if( rc==SQLITE4_OK ){
        u32 iRoot = sqlite4BtGetU32((const u8*)pVal);
        btCsrSetup(db, iRoot, &pSub->csr);
        rc = btCsrSeek(&pSub->csr, 0, pKey, nKey, BT_SEEK_GE, 0);
        if( rc==SQLITE4_INEXACT ) rc = SQLITE4_OK;
        if( rc==SQLITE4_NOTFOUND ) rc = btErrorBkpt(SQLITE4_CORRUPT);
      }
    }else if( rc==SQLITE4_NOTFOUND ){
      assert( pSub->csr.nPg==0 );
      rc = SQLITE4_OK;
    }
  }

  if( rc==SQLITE4_OK ){
    rc = fiCsrSetCurrent(pCsr);
  }

................................................................................
  /* 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);
    assert( rc!=SQLITE4_NOTFOUND );
    fiWriterInit(db, &s, &writer, &rc);

    /* The following loop runs once for each key copied from the input to
    ** the output segments. It terminates either when the input is exhausted
    ** or when all available output blocks are full.  */
    while( rc==SQLITE4_OK ){
      const void *pCell;          /* Cell to copy to output */
................................................................................

      /* Read the current cell from the input and push it to the output. */
      fiCsrCell(&fcsr, &pCell, &nCell);
      rc = fiWriterAdd(&writer, pCell, nCell);
      if( rc==BT_BLOCKFULL ){
        rc = fiWriterFlushAll(&writer);
        fiWriterInit(db, &s, &writer, &rc);

      }else if( rc==SQLITE4_OK ){
        rc = fiCsrStep(&fcsr);
      }
    }

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