SQLite4  Check-in [9e8d7525d8]

static void btCsrSetup(bt_db *db, bt_cursor *pCsr){
  memset(pCsr, 0, sizeof(bt_cursor));
  pCsr->pDb = db;
}

int sqlite4BtCsrOpen(bt_db *db, int nExtra, bt_cursor **ppCsr){
  int rc = SQLITE4_OK;            /* Return Code */
  int nByte;                      /* Total bytes of space to allocate */
  bt_cursor *pCsr;                /* New cursor object */

  nByte = sizeof(bt_cursor) + nExtra;
  *ppCsr = pCsr = (bt_cursor*)sqlite4_malloc(db->pEnv, nByte);
  if( pCsr==0 ){
    rc = btErrorBkpt(SQLITE4_NOMEM);

}

/*
**************************************************************************/

#ifndef NDEBUG
#include <stdio.h>
static void printPage(FILE *f, u32 pgno, u8 *aData, int nData){
  int i;
  int nCell = (int)btCellCount(aData, nData);
  fprintf(f, "Page %d: ", pgno);
  fprintf(f, "nCell=%d ", nCell);
  fprintf(f, "iFree=%d ", (int)btFreeOffset(aData, nData));
  fprintf(f, "flags=%d ", (int)btFlags(aData, nData));
  fprintf(f, "cell-offsets=(");
  for(i=0; i<nCell; i++){
    u8 *ptr = btCellPtrFind(aData, nData, i);
    fprintf(f, "%s%d", i==0?"":" ", (int)btGetU16(ptr));
  }
  fprintf(f, ")\n");
}
#endif


/*
** This function compares the key passed via parameters pK and nK to the
** key stored as part of cell iCell on the database page stored in buffer

          pgno = btGetU32(&aData[1]);
        }else{
          u8 *pCell;
          int nByte;
          pCell = btCellFind(aData, pgsz, 0);
          pCell += sqlite4BtVarintGet32(pCell, &nByte);
          pCell += nByte;
          pgno = btGetU32(pCell);
        }
      }else{
        pgno = 0;

        if( res!=0 ){
          assert( BT_SEEK_LEFAST<0 && BT_SEEK_LE<0 );
          if( eSeek<0 ){

*/
static int btNewBuffer(bt_db *pDb, u8 **paBuf){
  const int pgsz = sqlite4BtPagerPagesize(pDb->pPager);
  u8 *aBuf;

  *paBuf = aBuf = sqlite4_malloc(pDb->pEnv, pgsz);
  if( aBuf==0 ) return btErrorBkpt(SQLITE4_NOMEM);

#ifndef NDEBUG
  /* This stops valgrind from complaining about unitialized bytes when (if)
  ** this buffer is eventually written out to disk.  */
  memset(aBuf, 0x66, pgsz);
#endif

  return SQLITE4_OK;
}

/*
** Discard a page buffer allocated using btNewBuffer.
*/
static void btFreeBuffer(bt_db *pDb, u8 *aBuf){

  const int pgsz = sqlite4BtPagerPagesize(pDb->pPager);
  int rc;

  rc = sqlite4BtPageWrite(pPg);
  if( rc==SQLITE4_OK ){
    u8 *aData = sqlite4BtPageData(pPg);
    int nCell = btCellCount(aData, pgsz);

    if( iChild>=nCell ){
      btPutU32(&aData[1], pgno);
    }else{
      int nKey;
      u8 *pCell = btCellFind(aData, pgsz, iChild);
      pCell += sqlite4BtVarintGet32(pCell, &nKey);
      pCell += nKey;
      btPutU32(pCell, pgno);
    }
  }

  return rc;
}

/* Called recursively by btInsertAndRebalance(). todo: Fix this! */
static int btModifyPage(bt_cursor *, int, int, KeyValue *);

#if 0
/*
** An instance of this structure describes all the cells that will be
** redistributed by a single btRebalance() operation.
*/
struct BtRBIter {
  /* Input parameters */
  int nKV;                        /* Number of KV pairs to add */
  int iKVSib;                     /* Sibling to add KV pairs to */
  int iKVCell;                    /* Cell offset at which to insert KV pairs */
  int nSib;                       /* Number of sibling pages */
  /* Output parameters */
  int iSib;                       /* Sibling page to read cell from (or -ve) */
  int iCell;                      /* Index of cell to read (or -ve) */
};
static void btIterFirst(BtRBIter *p){
  p->iSib = 0;
  p->iCell = 0;
  if( p->iKVSib==0 && p->iKVCell==0 ){
    p->iSib = -1;
  }
}
static void btIterNext(BtRBIter *p){
  p->iCell++;
  /* Just finished the KV pairs */
  if( p->iSib<0 && p->iCell==p->nKV ){
    p->iSib = p->iKVSib;
    p->iCell = p->iKVCell;
  }
  if( p->iSib && p->iCell==p->nKV ){
    p->iSib = p->iKVSib;
    p->iCell = p->iKVCell;
  }
}

static void btIterValid(BtRBIter *p){
  return (p->iSib>=0 || p->iCell>=0);
}
#endif


typedef struct BalanceCtx BalanceCtx;
struct BalanceCtx {
  int pgsz;                       /* Database page size */
  int bLeaf;                      /* True if we are rebalancing leaf data */
  bt_cursor *pCsr;                /* Cursor identifying where to insert pKV */
  KeyValue *pKV;                  /* New KV pair being inserted */
  int nPg;                        /* Number of sibling pages */
  BtPage **apPg;                  /* Array of sibling pages */
  
  int *anOut;                     /* Cell counts for output pages */

  /* Variables used by btBalanceOutput */
  int nOut;                       /* Number of output pages */
  int iOut;                       /* Current output page */
  u8 **apOut;                     /* Buffers to assemble output in */


};

static int btBalanceOutput(
  BalanceCtx *p,                  /* Description of balance operation */
  int iCell,                      /* Cell number in this iteration */
  u8 *pCell, int nByte,           /* Binary cell to copy to output */
  KeyValue *pKV                   /* Key-value cell to write to output */
){
  u8 *aOut;                       /* Buffer for output page */
  int iOff;                       /* Offset of new cell within page */
  int nCell;                      /* Number of cells already on page */

  assert( (pCell==0)!=(pKV==0) );

  /* Scribble the new cell into the output page. */
  aOut = p->apOut[p->iOut];
  iOff = btFreeOffset(aOut, p->pgsz);
  if( iOff==0 ) iOff = (p->bLeaf ? 1 : 5);
  nCell = btCellCount(aOut, p->pgsz);
  btPutU16(btCellPtrFind(aOut, p->pgsz, nCell), iOff);
  if( pCell ){
    memcpy(&aOut[iOff], pCell, nByte);
    iOff += nByte;
  }else{
    iOff += btKVCellWrite(pKV, p->pgsz, &aOut[iOff]);
  }
  btPutU16(&aOut[p->pgsz-2], nCell+1);
  btPutU16(&aOut[p->pgsz-6], iOff);

  if( (iCell+1)==p->anOut[p->iOut] ){
    /* That was the last cell for this page. Fill in the rest of the 
    ** output page footer and so on. Then increment BalanceCtx.iOut so
    ** that the next call writes to the next page.  */ 
    int nFree;                    /* Free space remaining on output page */
    nFree = p->pgsz - iOff - (6 + 2*(nCell+1));
    aOut[0] = (p->bLeaf ? 0 : BT_PGFLAGS_INTERNAL);
    btPutU16(&aOut[p->pgsz-4], nFree);
    p->iOut++;
  }

  return SQLITE4_OK;
}

static int btBalanceVisitCells(
  BalanceCtx *p,
  int (*xVisit)(BalanceCtx*, int, u8*, int, KeyValue*)
){
  const int pgsz = sqlite4BtPagerPagesize(p->pCsr->pDb->pPager);
  int rc = SQLITE4_OK;            /* Return code */
  int iPg;                        /* Current page in apPg[] */
  int iCall = 0;

  BtPage *pIns = p->pCsr->apPage[p->pCsr->nPg-1];
  int iIns = p->pCsr->aiCell[p->pCsr->nPg-1];

  for(iPg=0; iPg<p->nPg && rc==SQLITE4_OK; iPg++){
    BtPage *pPg;                  /* Current page */
    u8 *aData;                    /* Page data */
    int nCell;                    /* Number of cells on page pPg */
    int iCell;                    /* Current cell in pPg */

    pPg = p->apPg[iPg];
    aData = sqlite4BtPageData(pPg);
    nCell = btCellCount(aData, pgsz);

    for(iCell=0; iCell<nCell && rc==SQLITE4_OK; iCell++){
      int nByte;
      u8 *pCell;

      if( pPg==pIns && iCell==iIns ){
        rc = xVisit(p, iCall++, 0, 0, p->pKV);
        if( rc!=SQLITE4_OK ) break;
      }

      pCell = btCellFindSize(aData, pgsz, iCell, &nByte);
      rc = xVisit(p, iCall++, pCell, nByte, 0);
    }

    if( pPg==pIns && iCell==nCell && rc==SQLITE4_OK ){
      rc = xVisit(p, iCall++, 0, 0, p->pKV);
    }
  }

  return rc;
}


int btInsertAndRebalance(bt_cursor *pCsr, KeyValue *pKV){
  bt_db * const pDb = pCsr->pDb; 
  const int pgsz = sqlite4BtPagerPagesize(pDb->pPager);
  const int nSpacePerPage = (pgsz - 1 - 6);

  int nIn = 0;                    /* Number of input pages */
  int iPg;                        /* Used to iterate through pages */
  int iCell;                      /* Used to iterate through cells */

  KeyValue aPCell[5];             /* Cells to push into the parent page */
  BtPage *pPar;                   /* Parent page */
  int iSib;                       /* Index of left-most sibling */

  int nTotal;                     /* Total bytes of content to distribute */
  int rc = SQLITE4_OK;            /* Return code */

  BalanceCtx ctx;


  memset(apOut, 0, sizeof(apOut));
  memset(apPg, 0, sizeof(apPg));
  memset(aPCell, 0, sizeof(aPCell));

  /* Gather the sibling pages from which cells will be redistributed into
  ** the apPg[] array.  */

  }
#endif

  /* Allocate buffers for the output leaves */
  for(iPg=0; iPg<nOut; iPg++){
    rc = btNewBuffer(pDb, &apOut[iPg]);
    if( rc!=SQLITE4_OK ) goto rebalance_out;
    memset(apOut[iPg] + pgsz-6, 0, 6);
  }


  memset(&ctx, 0, sizeof(ctx));
  ctx.pCsr = pCsr;
  ctx.pKV = pKV;
  ctx.nPg = nIn;
  ctx.apPg = apPg;
  ctx.pgsz = pgsz;
  ctx.bLeaf = 1; /* todo */

  ctx.anOut = anOut;
  ctx.nOut = nOut;
  ctx.apOut = apOut;
  rc = btBalanceVisitCells(&ctx, btBalanceOutput);

#if 0
  /* Populate buffers for the output leaves */
  iPgOut = 0;                     /* Index of current output page */
  iPgIn = 0;                      /* Index of current input page */
  iPgInFirst = 0;
  for(iCell=0; iCell<nCell; iCell++){
    int iOff;                     /* Output page offset */
    u8 *aOut;                     /* Output page buffer */

    if( iCell==anOut[iPg] ) iPg++;
    aOut = apOut[iPg];

        aIn = sqlite4BtPageData(apPg[iPgIn]);
      }
      memcpy(&aOut[iOff], btCellFind(aIn, pgsz, iPgCell), anCellSz[iCell]);
      iOff += anCellSz[iCell];
    }
    btPutU16(&aOut[pgsz-6], iOff);
  }
  for(iPg=0; iPg<nOut; iPg++){
    u8 *aData = apOut[iPg];
    btPutU16(&aData[pgsz-2], anOut[iPg] - (iPg==0 ? 0 : anOut[iPg-1]));
  }
#endif

  /* Clobber the old pages with the new buffers */
  for(iPg=0; iPg<nOut; iPg++){

    if( iPg>=nIn ){


      rc = sqlite4BtPageAllocate(pDb->pPager, &apPg[iPg]);
      if( rc!=SQLITE4_OK ) goto rebalance_out;
    }
    btSetBuffer(pDb, apPg[iPg], apOut[iPg]);
    apOut[iPg] = 0;
  }

#ifndef NDEBUG
  {
    int iDbg;
    for(iDbg=0; iDbg<nOut; iDbg++){
      u8 *aData = sqlite4BtPageData(apPg[iDbg]);
      printPage(stderr, sqlite4BtPagePgno(apPg[iDbg]), aData, pgsz);
    }
  }
#endif

  /* The leaves are written. Now gather the keys and page numbers to
  ** push up into the parent page.  */ 
  for(iPg=0; iPg<(nOut-1); iPg++){
    u8 *aData = sqlite4BtPageData(apPg[iPg]);
    u8 *pCell;

    pCell = btCellFind(aData, pgsz, btCellCount(aData, pgsz)-1);
    aPCell[iPg].pgno = sqlite4BtPagePgno(apPg[iPg]);
    pCell += sqlite4BtVarintGet32(pCell, &aPCell[iPg].nK);
    aPCell[iPg].pK = pCell;
  }


  assert( nIn==1 && nOut==2 );
  rc = btSetChildPgno(pDb, pPar, iSib+nIn-1, sqlite4BtPagePgno(apPg[nOut-1]));
  if( rc!=SQLITE4_OK ) goto rebalance_out;

  pCsr->nPg--;
  rc = btModifyPage(pCsr, nIn-1, nOut-1, aPCell);

    pCsr->apPage[1] = pNew;
    pCsr->aiCell[0] = 0;
  }

  return rc;
}

/*
** The cursor currently points to a cell on a b-tree page that may or
** may not be a leaf page. This routine modifies the contents of that
** page, balancing the b-tree if necessary. The page is modified as
** follows:
**
**     * nDel entries, starting with the one the cursor points to, are
**       deleted from the page.
**
**     * nKV entries are inserted in their place.
**
** The tree balancing routine is called if this causes the page to
** become either overfull or to contain no entries at all.
*/
static int btModifyPage(
  bt_cursor *pCsr,                /* Cursor identifying page to modify */
  int nDel,                       /* Number of entries to delete from page */
  int nKV,                        /* Number of entries in apKV */
  KeyValue *apKV                  /* New cells to insert into the page */
){
  int rc = SQLITE4_OK;

*************************************************************************
*/

#include "btInt.h"

#include <string.h>
#include <assert.h>
#include <stdio.h>

/* By default pages are 1024 bytes in size. */
#define BT_DEFAULT_PGSZ 1024

typedef struct BtPageHash BtPageHash;
typedef struct BtDbhdr BtDbhdr;

  rc = p->pVfs->xSize(p->pFd, &nByte);
  if( rc==SQLITE4_OK && nByte>0 ){
    rc = p->pVfs->xRead(p->pFd, 0, &p->dbhdr, sizeof(p->dbhdr));
  }else{
    memset(&p->dbhdr, 0, sizeof(p->dbhdr));
    p->dbhdr.pgsz = BT_DEFAULT_PGSZ;
    p->dbhdr.nPg = 2;
  }

  if( rc==SQLITE4_OK ){
    /* If the read transaction was successfully opened, the transaction 
    ** level is now 1.  */
    p->iTransactionLevel = 1;
  }

/*
** Allocate a new database page and return a writable reference to it.
*/
int sqlite4BtPageAllocate(BtPager *p, BtPage **ppPg){
  BtPage *pPg = 0;
  int rc;
  u32 pgno = p->dbhdr.nPg+1;

  rc = sqlite4BtPageGet(p, pgno, &pPg);
  if( rc==SQLITE4_OK ){
    rc = sqlite4BtPageWrite(pPg);
    if( rc!=SQLITE4_OK ){
      sqlite4BtPageRelease(pPg);
      pPg = 0;
    }else{
      p->dbhdr.nPg = pgno;
    }
  }

  fprintf(stderr, "allocated page %d\n", pgno);

  *ppPg = pPg;
  return rc;
}

/*
** Return the current page number of the argument page reference.

/*
** Move a VDBE cursor to the first or to the last element of its table.  The
** first element is sought if iEnd==+1 and the last element if iEnd==-1.
**
** Return SQLITE4_OK on success. Return SQLITE4_NOTFOUND if the table is empty.
** Other error codes are also possible for various kinds of errors.
*/
int sqlite4VdbeSeekEnd(VdbeCursor *pC, int iEnd){
  KVCursor *pCur = pC->pKVCur;
  int rc;
  KVSize nProbe;
  KVByteArray aProbe[16];

}

do_execsql_test 2.2 {
  INSERT INTO t1 VALUES(5, $val);
}

do_execsql_test 2.3 { 
  SELECT a, length(b) FROM t1 
} {1 200  3 200  4 200  5 200}

do_execsql_test 2.4 {
  INSERT INTO t1 VALUES(6, $val);
}

breakpoint
do_execsql_test 2.5 { 
  SELECT a, length(b) FROM t1 
} {1 200  3 200  4 200  5 200  6 200}

finish_test