SQLite4
Check-in [51c2c9358d]
Not logged in

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
SHA1 Hash:51c2c9358d98aa13181bb67489abca64d73b6189
Date: 2013-10-07 20:43:15
User: dan
Comment:Further progress on b-tree module.
Tags And Properties
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to main.mk

266
267
268
269
270
271
272

273
274
275
276
277
278
279
  $(TOP)/src/vdbemem.c \
  $(TOP)/src/where.c \
  parse.c \

# Header files used by all library source files.
#
HDR = \

   $(TOP)/src/hash.h \
   $(TOP)/src/hwtime.h \
   keywordhash.h \
   $(TOP)/src/kv.h \
   $(TOP)/src/lsm.h \
   $(TOP)/src/lsmInt.h \
   $(TOP)/src/mutex.h \







>







266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
  $(TOP)/src/vdbemem.c \
  $(TOP)/src/where.c \
  parse.c \

# Header files used by all library source files.
#
HDR = \
   $(TOP)/src/btInt.h \
   $(TOP)/src/hash.h \
   $(TOP)/src/hwtime.h \
   keywordhash.h \
   $(TOP)/src/kv.h \
   $(TOP)/src/lsm.h \
   $(TOP)/src/lsmInt.h \
   $(TOP)/src/mutex.h \

Changes to src/btInt.h

9
10
11
12
13
14
15


16
17
18
19
20
21
22
**    May you share freely, never taking more than you give.
**
*************************************************************************
**
*/

#include "bt.h"



typedef sqlite4_int64 i64;
typedef sqlite4_uint64 u64;
typedef unsigned int u32;
typedef unsigned short u16;
typedef unsigned char u8;








>
>







9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
**    May you share freely, never taking more than you give.
**
*************************************************************************
**
*/

#include "bt.h"

/* #define BT_STDERR_DEBUG 1 */

typedef sqlite4_int64 i64;
typedef sqlite4_uint64 u64;
typedef unsigned int u32;
typedef unsigned short u16;
typedef unsigned char u8;

Changes to src/bt_main.c

287
288
289
290
291
292
293








294












295
296
297
298
299
300
301
...
332
333
334
335
336
337
338
339
340
341
342
343

344
345
346
347
348
349
350
...
384
385
386
387
388
389
390




391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408

409
410

411



412
413
414

415
416
417
418
419
420
421









422
423
424
425
426
427
428
...
558
559
560
561
562
563
564

565
566
567
568
569
570
571
...
765
766
767
768
769
770
771


772
773
774

775
776
777
778
779
780



781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
...
811
812
813
814
815
816
817

818
819
820
821
822
823
















824
825
826
827
828
829
830
...
843
844
845
846
847
848
849

850
851
852
853
854
855
856
...
864
865
866
867
868
869
870
871
872
873
874
875
876




































877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899





900

901
902
903
904
905
906
907
...
911
912
913
914
915
916
917





918
919
920
921
922
923
924
...
928
929
930
931
932
933
934

935
936
937
938
939
940
941
942
943
944
945

946
947
948
949











950



951
952
953
954
955





956
957
958
959
960
961
962
963
964
965

966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983

984
985
986
987
988
989
990
991
992
993
994
995


996
997
998
999
1000
1001
1002
1003
1004
1005

1006
1007
1008
1009






1010
1011
1012

1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029

1030
1031
1032



1033
1034
1035
1036
1037

1038
1039
1040
1041

1042
1043
1044
1045


1046
1047


1048
1049
1050
1051
1052
1053
1054
1055
1056

1057
1058
1059
1060



1061
1062
1063
1064
1065



1066
1067

1068








1069
1070
1071
1072
1073
1074
1075
1076
1077
1078




1079
1080


1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091


1092

1093
1094
1095
1096
1097
1098
1099



1100
1101
1102
1103
1104
1105
1106
1107
1108

1109
1110
1111


1112
1113


1114
1115
1116
1117
1118
1119
1120
1121
1122
1123

1124
1125
1126
1127
1128
1129
1130
....
1181
1182
1183
1184
1185
1186
1187

1188

1189
1190
1191
1192
1193
1194
1195
1196
1197
1198










1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
....
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
....
1306
1307
1308
1309
1310
1311
1312



































1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
....
1340
1341
1342
1343
1344
1345
1346

1347



1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
  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
................................................................................
    }
  }

  *piRes = res;
  return rc;
}

int sqlite4BtCsrSeek(
  bt_cursor *pCsr, 
  const void *pK,                 /* Key to seek for */
  int nK,                         /* Size of key pK in bytes */
  int eSeek                       /* Seek mode (a BT_SEEK_XXX constant) */

){
  const int pgsz = sqlite4BtPagerPagesize(pCsr->pDb->pPager);
  u32 pgno;                       /* Page number for next page to load */
  int rc = SQLITE4_OK;            /* Return Code */

  /* Reset the cursor */
  btCsrReset(pCsr);
................................................................................
          iHi = iTst;
        }
      }
      if( rc!=SQLITE4_OK ) break;
      assert( iHi==iLo );
      pCsr->aiCell[pCsr->nPg-1] = iHi;





      if( aData[0] & BT_PGFLAGS_INTERNAL ){
        if( iHi==nCell ){
          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 ){
            rc = sqlite4BtCsrPrev(pCsr);

            if( rc==SQLITE4_OK ) rc = SQLITE4_INEXACT;
          }else if( eSeek==BT_SEEK_EQ || iHi==nCell ){

            rc = SQLITE4_NOTFOUND;



          }else{
            rc = SQLITE4_INEXACT;
          }

        }
      }
    }
  }

  return rc;
}










/*
** This function seeks the cursor as required for either sqlite4BtCsrFirst()
** (if parameter bLast is false) or sqlite4BtCsrLast() (if bLast is true).
*/
static int btCsrEnd(bt_cursor *pCsr, int bLast){
  const int pgsz = sqlite4BtPagerPagesize(pCsr->pDb->pPager);
................................................................................
  const int pgsz = sqlite4BtPagerPagesize(pCsr->pDb->pPager);
  u8 *aData;
  u8 *pCell;
  int iCell = pCsr->aiCell[pCsr->nPg-1];
  int nK;
  
  aData = (u8*)sqlite4BtPageData(pCsr->apPage[pCsr->nPg-1]);

  pCell = btCellFind(aData, pgsz, iCell);
  pCell += sqlite4BtVarintGet32(pCell, &nK);

  if( nK==0 ){
    assert( 0 );
  }else{
    *ppK = pCell;
................................................................................
  int nKV;                        /* Number of KV pairs */
  KeyValue *apKV;                 /* New KV pairs being inserted */

  /* Populated by btGatherSiblings */
  int nIn;                        /* Number of sibling pages */
  BtPage *apPg[5];                /* Array of sibling pages */



  /* Array populated by btBalanceMeasure */
  int *anCellSz;
  

  int anOut[5];                   /* Cell counts for output pages */

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



};

static int btGatherSiblings(BalanceCtx *p){
  bt_cursor *pCsr = p->pCsr;
  bt_db * const pDb = pCsr->pDb; 
  const int pgsz = sqlite4BtPagerPagesize(pDb->pPager);

  int rc = SQLITE4_OK;
  int nCell;                      /* Number of cells in parent page */
  u8 *aParent;                    /* Buffer of parent page */
  int iChild;                     /* Index of child page */
  int nSib;                       /* Number of siblings */
  int iSib;                       /* Index of left-most sibling page */

  int i;

  aParent = sqlite4BtPageData(pCsr->apPage[pCsr->nPg-2]);
  iChild = pCsr->aiCell[pCsr->nPg-2];
................................................................................
  }else{
    iSib = iChild-1;
  }

  for(i=0; i<nSib && rc==SQLITE4_OK; i++){
    u32 pgno = btChildPgno(aParent, pgsz, iSib+i);
    rc = sqlite4BtPageGet(pDb->pPager, pgno, &p->apPg[i]);

  }
  p->nIn = nSib;

  pCsr->aiCell[pCsr->nPg-2] = iSib;
  return rc;
}

















static int btSetChildPgno(bt_db *pDb, BtPage *pPg, int iChild, u32 pgno){
  const int pgsz = sqlite4BtPagerPagesize(pDb->pPager);
  int rc;

  rc = sqlite4BtPageWrite(pPg);
  if( rc==SQLITE4_OK ){
................................................................................

  return rc;
}

/* Called recursively by btBalance(). todo: Fix this! */
static int btInsertAndBalance(bt_cursor *, int, KeyValue *);
static int btDeleteFromPage(bt_cursor *, int);


static int btBalanceMeasure(
  BalanceCtx *p,                  /* Description of balance operation */
  int iCell,                      /* Cell number in this iteration */
  u8 *pCell, int nByte,           /* Binary cell */
  KeyValue *pKV                   /* Key-value cell */
){
................................................................................

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 rc = SQLITE4_OK;            /* Return code */
  int iPg;                        /* Current page in apPg[] */
  int iCall = 0;
  int i;                          /* Used to iterate through KV pairs */

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






  for(iPg=0; iPg<p->nIn && 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 */

................................................................................

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

      if( pPg==pIns && iCell==iIns ){
        for(i=0; i<p->nKV; i++){

          rc = xVisit(p, iCall++, 0, 0, &p->apKV[i]);
          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 ){
      for(i=0; i<p->nKV; i++){

        rc = xVisit(p, iCall++, 0, 0, &p->apKV[i]);
      }
    }
  }















  return rc;
}


int btBalance(bt_cursor *pCsr, int nKV, KeyValue *apKV){





  bt_db * const pDb = pCsr->pDb; 
  const int pgsz = sqlite4BtPagerPagesize(pDb->pPager);
  const int nSpacePerPage = (pgsz - 1 - 6);

  int iPg;                        /* Used to iterate through pages */
  int iCell;                      /* Used to iterate through cells */
  int nCell = 0;                  /* Total number of cells to redistribute */
  int *anCellSz;                  /* Array containing size in bytes of 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(&ctx, 0, sizeof(ctx));
  ctx.pCsr = pCsr;
  ctx.nKV = nKV;
  ctx.apKV = apKV;
  ctx.pgsz = pgsz;
  ctx.bLeaf = 1; /* todo */

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

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

  assert( pCsr->nPg>1 );
  rc = btGatherSiblings(&ctx);
  if( rc!=SQLITE4_OK ) goto rebalance_out;
  pPar = pCsr->apPage[pCsr->nPg-2];
  iSib = pCsr->aiCell[pCsr->nPg-2];

  /* Count the number of input cells */
  nCell = 1;
  for(iPg=0; iPg<ctx.nIn; iPg++){
    u8 *aData = sqlite4BtPageData(ctx.apPg[iPg]);
    nCell += btCellCount(aData, pgsz);
  }



  /* Allocate and populate the anCellSz[] array */
  anCellSz = ctx.anCellSz = (int*)sqlite4_malloc(pDb->pEnv, sizeof(int)*nCell);
  if( anCellSz==0 ){
    rc = btErrorBkpt(SQLITE4_NOMEM);
    goto rebalance_out;
  }
  rc = btBalanceVisitCells(&ctx, btBalanceMeasure);

  /* Now figure out the number of output pages. Set ctx.nOut to this value. */

  iCell = 0;
  for(iPg=0; iCell<nCell; iPg++){
    int nByte = 0;                /* Number of bytes of content on page */
    assert( iPg<array_size(ctx.anOut) );






    for(/* noop */; iCell<nCell; iCell++){
      nByte += (anCellSz[iCell] + 2);
      if( nByte>nSpacePerPage ) break;

    }
    ctx.anOut[iPg] = iCell;
  }
  ctx.nOut = iPg;
  assert( ctx.anOut[ctx.nOut-1]==nCell );

  /* Calculate the total size of all cells. */
  nTotal = 0;
  for(iCell=0; iCell<nCell; iCell++) nTotal += (anCellSz[iCell] + 2);

  /* The loop in the previous block populated the anOut[] array in such a
  ** way as to make the (ctx.nOut-1) leftmost pages completely full but 
  ** leave the rightmost page partially empty. This block redistributes 
  ** cells a bit more evenly. This block may reduce one or more of the 
  ** values in the anOut[] array, but will not increase any. No values 
  ** are reduced to values lower than 1.  */
  iCell = nCell;

  for(iPg=(ctx.nOut-2); iPg>=0; iPg--){
    int nByte = 0;                /* Number of bytes of content on page */
    int nGoal = nTotal / (iPg + 2);




    for( ; iCell>0 && ((nByte<nGoal) || iCell>ctx.anOut[iPg]); iCell--){
      int nThis = (anCellSz[iCell-1] + 2);
      if( (nThis + nByte)>nSpacePerPage ) break;
      nByte += nThis;

    }
    assert( iCell<=ctx.anOut[iPg] );
    ctx.anOut[iPg] = iCell;
    nTotal = nByte;

  }

#ifndef NDEBUG
  {


    int iDbg;
    fprintf(stderr, "btBalance(): nIn=%d anIn[] = ", ctx.nIn);


    for(iDbg=0; iDbg<ctx.nIn; iDbg++){
      u8 *aData = sqlite4BtPageData(ctx.apPg[iDbg]);
      fprintf(stderr, "%d ", btCellCount(aData, pgsz));
    }
    fprintf(stderr, " ->  nOut=%d anOut[] = ", ctx.nOut);
    for(iDbg=0; iDbg<ctx.nOut; iDbg++){
      fprintf(stderr, "%d ", ctx.anOut[iDbg]);
    }
    fprintf(stderr, "\n");

  }
#endif

  /* Allocate buffers for the output leaves */



  for(iPg=0; iPg<ctx.nOut; iPg++){
    rc = btNewBuffer(pDb, &ctx.apOut[iPg]);
    if( rc!=SQLITE4_OK ) goto rebalance_out;
    memset(ctx.apOut[iPg] + pgsz-6, 0, 6);
  }






  rc = btBalanceVisitCells(&ctx, btBalanceOutput);









  /* Clobber the old pages with the new buffers */
  for(iPg=0; iPg<ctx.nOut; iPg++){
    if( iPg>=ctx.nIn ){
      rc = sqlite4BtPageAllocate(pDb->pPager, &ctx.apPg[iPg]);
      if( rc!=SQLITE4_OK ) goto rebalance_out;
    }
    btSetBuffer(pDb, ctx.apPg[iPg], ctx.apOut[iPg]);
    ctx.apOut[iPg] = 0;
  }





#ifndef NDEBUG


  {
    int iDbg;
    for(iDbg=0; iDbg<ctx.nOut; iDbg++){
      u8 *aData = sqlite4BtPageData(ctx.apPg[iDbg]);
      printPage(stderr, sqlite4BtPagePgno(ctx.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<(ctx.nOut-1); iPg++){

    u8 *aData = sqlite4BtPageData(ctx.apPg[iPg]);
    u8 *pCell;

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



  }

  rc = btSetChildPgno(
      pDb, pPar, iSib+ctx.nIn-1, sqlite4BtPagePgno(ctx.apPg[ctx.nOut-1])
  );
  if( rc==SQLITE4_OK ){
    pCsr->nPg--;
    rc = btDeleteFromPage(pCsr, ctx.nIn-1);
  }

  if( rc==SQLITE4_OK ){
    rc = btInsertAndBalance(pCsr, ctx.nOut-1, aPCell);
  }



#ifndef NDEBUG


  {
    u8 *aData = sqlite4BtPageData(pPar);
    printPage(stderr, sqlite4BtPagePgno(pPar), aData, pgsz);
  }
#endif

 rebalance_out:
  for(iPg=0; iPg<ctx.nIn; iPg++){
    sqlite4BtPageRelease(ctx.apPg[iPg]);
  }

  return rc;
}

static int btExtendTree(bt_cursor *pCsr){
  bt_db * const pDb = pCsr->pDb;
  const int pgsz = sqlite4BtPagerPagesize(pDb->pPager);
  int rc;                         /* Return code */
................................................................................
  u8 *aData;                      /* Page buffer */
  int nCell;                      /* Number of cells on this page already */
  int nFree;                      /* Contiguous free space on this page */
  int nReq = 0;                   /* Space required for type (a) cells */
  int iCell;                      /* Position to insert new key */
  int iWrite;                     /* Byte offset at which to write new cell */
  int i;

  BtPage *pLeaf;


  /* Bytes of space required on the current page. */
  for(i=0; i<nKV; i++){
    nReq += btKVCellSize(&apKV[i], pgsz) + 2;
  }

  iCell = pCsr->aiCell[pCsr->nPg-1];
  assert( pCsr->nPg>0 );
  pLeaf = pCsr->apPage[pCsr->nPg-1];
  aData = (u8*)sqlite4BtPageData(pLeaf);











  nCell = btCellCount(aData, pgsz);
  assert( iCell<=btCellCount(aData, pgsz) );

  if( nCell==0 ){
    /* If the nCell field is zero, then the rest of the header may 
    ** contain invalid values (zeroes - as it may never have been 
    ** initialized). So set our stack variables to values appropriate
    ** to an empty page explicitly here.  */
    iWrite = ((btFlags(aData, pgsz) & BT_PGFLAGS_INTERNAL) ? 5 : 1);
    nFree = pgsz - iWrite - 6;
  }else{
    if( btFreeContiguous(aData, pgsz)<nReq && btFreeSpace(aData, pgsz)>=nReq ){
      /* Special case - the new entry will not fit on the page at present
      ** but would if the page were defragmented. So defragment it before
      ** continuing.  */
      rc = btDefragmentPage(pCsr->pDb, pLeaf);
................................................................................
    /* The new entry will not fit on the leaf page. Entries will have
    ** to be shuffled between existing leaves and new leaves may need
    ** to be added to make space for it. */
    if( pCsr->nPg==1 ){
      rc = btExtendTree(pCsr);
    }
    if( rc==SQLITE4_OK ){
      rc = btBalance(pCsr, nKV, apKV);
    }
  }

  return rc;
}

static int btDeleteFromPage(bt_cursor *pCsr, int nDel){
................................................................................

    /* Increase total free space */
    btPutU16(&aData[pgsz-4], btFreeSpace(aData, pgsz) + nFreed);
  }
  
  return rc;
}




































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

  btCsrSetup(db, &csr);
  rc = sqlite4BtCsrSeek(&csr, pK, nK, BT_SEEK_GE);
  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
    ** the cursor.  */
    rc = sqlite4BtDelete(&csr);
    if( rc==SQLITE4_OK ){
      rc = sqlite4BtCsrSeek(&csr, pK, nK, BT_SEEK_GE);
    }
  }
  if( rc==SQLITE4_OK ) rc = btErrorBkpt(SQLITE4_CORRUPT);

  if( rc==SQLITE4_NOTFOUND || rc==SQLITE4_INEXACT ){
    /* Insert the new KV pair into the current leaf. */
    KeyValue kv;
................................................................................
    rc = btInsertAndBalance(&csr, 1, &kv);
  }

  return rc;
}

int sqlite4BtDelete(bt_cursor *pCsr){

  return btDeleteFromPage(pCsr, 1);



}

int sqlite4BtSetCookie(bt_db *db, unsigned int iVal){
  return sqlite4BtPagerSetCookie(db->pPager, iVal);
}

int sqlite4BtGetCookie(bt_db *db, unsigned int *piVal){
  return sqlite4BtPagerGetCookie(db->pPager, piVal);
}








>
>
>
>
>
>
>
>
|
>
>
>
>
>
>
>
>
>
>
>
>







 







|



|
>







 







>
>
>
>






|











>
|
|
>
|
>
>
>



>







>
>
>
>
>
>
>
>
>







 







>







 







>
>



>






>
>
>










|







 







>






>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







 







>







 







|





>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
|
<
|
|
|
|
|
|
|
|
|
|
|
|

|
|
|
<
|
|
|
|
>
>
>
>
>
|
>







 







>
>
>
>
>







 







>









|
|
>



|
>
>
>
>
>
>
>
>
>
>
>
|
>
>
>




|
>
>
>
>
>


|



<
<

<
>



<








|

|



>






|
|


|

>
>


|
|





|
>

|
<

>
>
>
>
>
>
|
|
|
>




|
<
<
<
<



|
|
|
|
|
>

<
|
>
>
>

<
<
<
|
>
|
|
|
<
>
|
|
<
|
>
>

|
>
>









>



|
>
>
>





>
>
>
|

>

>
>
>
>
>
>
>
>










>
>
>
>
|
<
>
>










|
>
>

>
|
|

|
|
|
|
>
>
>









>
|
|

>
>
|
<
>
>







|


>







 







>

>










>
>
>
>
>
>
>
>
>
>









|







 







|







 







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>









|






|







 







>
|
>
>
>










287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
...
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
...
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
...
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
...
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
...
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
...
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
...
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978

979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994

995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
....
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
....
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092


1093

1094
1095
1096
1097

1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139

1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155




1156
1157
1158
1159
1160
1161
1162
1163
1164
1165

1166
1167
1168
1169
1170



1171
1172
1173
1174
1175

1176
1177
1178

1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237

1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280

1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
....
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
....
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
....
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
....
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
  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");

  for(i=0; i<nCell; i++){
    int nKey;
    int j;
    u8 *pCell = btCellFind(aData, nData, i);
    fprintf(f, "  Key %d: ", i);
    pCell += sqlite4BtVarintGet32(pCell, &nKey);
    for(j=0; j<nKey; j++){
      fprintf(f, "%02X", (int)pCell[j]);
    }
    if( btFlags(aData, nData) & BT_PGFLAGS_INTERNAL ){
      fprintf(f, "  child=%d ", (int)btGetU32(&pCell[j]));
    }
    fprintf(f, "\n");
  }


}

static int printPgToStderr(BtPage *pPg){
  printPage(stderr, sqlite4BtPagePgno(pPg), sqlite4BtPageData(pPg), 1024);
  return 0;
}
#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
................................................................................
    }
  }

  *piRes = res;
  return rc;
}

static int btCsrSeek(
  bt_cursor *pCsr, 
  const void *pK,                 /* Key to seek for */
  int nK,                         /* Size of key pK in bytes */
  int eSeek,                      /* Seek mode (a BT_SEEK_XXX constant) */
  int bUpdate
){
  const int pgsz = sqlite4BtPagerPagesize(pCsr->pDb->pPager);
  u32 pgno;                       /* Page number for next page to load */
  int rc = SQLITE4_OK;            /* Return Code */

  /* Reset the cursor */
  btCsrReset(pCsr);
................................................................................
          iHi = iTst;
        }
      }
      if( rc!=SQLITE4_OK ) break;
      assert( iHi==iLo );
      pCsr->aiCell[pCsr->nPg-1] = iHi;

#if 0
printPage(stderr, pgno, aData, pgsz);
#endif

      if( aData[0] & BT_PGFLAGS_INTERNAL ){
        if( iHi==nCell ){
          pgno = btGetU32(&aData[1]);
        }else{
          u8 *pCell;
          int nByte;
          pCell = btCellFind(aData, pgsz, iHi);
          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 ){
            rc = sqlite4BtCsrPrev(pCsr);
          }else if( eSeek==BT_SEEK_EQ ){
            rc = SQLITE4_NOTFOUND;
          }else if( iHi==nCell ){
            if( bUpdate ){
              rc = SQLITE4_NOTFOUND;
            }else{
              rc = sqlite4BtCsrNext(pCsr);
            }
          }else{
            rc = SQLITE4_INEXACT;
          }
          if( rc==SQLITE4_OK ) rc = SQLITE4_INEXACT;
        }
      }
    }
  }

  return rc;
}

int sqlite4BtCsrSeek(
  bt_cursor *pCsr, 
  const void *pK,                 /* Key to seek for */
  int nK,                         /* Size of key pK in bytes */
  int eSeek                       /* Seek mode (a BT_SEEK_XXX constant) */
){
  return btCsrSeek(pCsr, pK, nK, eSeek, 0);
}

/*
** This function seeks the cursor as required for either sqlite4BtCsrFirst()
** (if parameter bLast is false) or sqlite4BtCsrLast() (if bLast is true).
*/
static int btCsrEnd(bt_cursor *pCsr, int bLast){
  const int pgsz = sqlite4BtPagerPagesize(pCsr->pDb->pPager);
................................................................................
  const int pgsz = sqlite4BtPagerPagesize(pCsr->pDb->pPager);
  u8 *aData;
  u8 *pCell;
  int iCell = pCsr->aiCell[pCsr->nPg-1];
  int nK;
  
  aData = (u8*)sqlite4BtPageData(pCsr->apPage[pCsr->nPg-1]);
  assert( btCellCount(aData, pgsz)>iCell );
  pCell = btCellFind(aData, pgsz, iCell);
  pCell += sqlite4BtVarintGet32(pCell, &nK);

  if( nK==0 ){
    assert( 0 );
  }else{
    *ppK = pCell;
................................................................................
  int nKV;                        /* Number of KV pairs */
  KeyValue *apKV;                 /* New KV pairs being inserted */

  /* Populated by btGatherSiblings */
  int nIn;                        /* Number of sibling pages */
  BtPage *apPg[5];                /* Array of sibling pages */

  int nCell;                      /* Number of input cells */

  /* Array populated by btBalanceMeasure */
  int *anCellSz;
  
  /* Populated in btBalance() */
  int anOut[5];                   /* Cell counts for output pages */

  /* Variables used by btBalanceOutput */
  int nOut;                       /* Number of output pages */
  int iOut;                       /* Current output page */
  u8 *apOut[5];                   /* Buffers to assemble output in */
  KeyValue aPCell[5];             /* Cells to push into the parent page */
  u8 *pTmp;                       /* Space for apCell[x].pKey if required */
  int iTmp;                       /* Offset to free space within pTmp */
};

static int btGatherSiblings(BalanceCtx *p){
  bt_cursor *pCsr = p->pCsr;
  bt_db * const pDb = pCsr->pDb; 
  const int pgsz = sqlite4BtPagerPagesize(pDb->pPager);

  int rc = SQLITE4_OK;
  int nCell;                      /* Number of cells in parent page */
  u8 *aParent;                    /* Buffer of parent page */
  int iChild;                     /* Index of child page within parent */
  int nSib;                       /* Number of siblings */
  int iSib;                       /* Index of left-most sibling page */

  int i;

  aParent = sqlite4BtPageData(pCsr->apPage[pCsr->nPg-2]);
  iChild = pCsr->aiCell[pCsr->nPg-2];
................................................................................
  }else{
    iSib = iChild-1;
  }

  for(i=0; i<nSib && rc==SQLITE4_OK; i++){
    u32 pgno = btChildPgno(aParent, pgsz, iSib+i);
    rc = sqlite4BtPageGet(pDb->pPager, pgno, &p->apPg[i]);
    assert( (iSib+i)!=iChild || p->apPg[i]==pCsr->apPage[pCsr->nPg-1] );
  }
  p->nIn = nSib;

  pCsr->aiCell[pCsr->nPg-2] = iSib;
  return rc;
}

/*
** Argument pCell points to a cell on an internal node. Decode the
** cell into key-value object *pKV. An internal cell always has
** the same format:
**
**     * Number of bytes in the key (nKey) as a varint.
**     * nKey bytes of key data.
**     * A page pointer, stored as a 32-bit big-endian unsigned.
*/
static void btInternalCellToKeyValue(u8 *pCell, KeyValue *pKV){
  pKV->pK = pCell + sqlite4BtVarintGet32(pCell, &pKV->nK);
  pKV->pgno = btGetU32(&((u8*)pKV->pK)[pKV->nK]);
  pKV->pV = 0;
  pKV->nV = 0;
}

static int btSetChildPgno(bt_db *pDb, BtPage *pPg, int iChild, u32 pgno){
  const int pgsz = sqlite4BtPagerPagesize(pDb->pPager);
  int rc;

  rc = sqlite4BtPageWrite(pPg);
  if( rc==SQLITE4_OK ){
................................................................................

  return rc;
}

/* Called recursively by btBalance(). todo: Fix this! */
static int btInsertAndBalance(bt_cursor *, int, KeyValue *);
static int btDeleteFromPage(bt_cursor *, int);
static int btBalanceIfUnderfull(bt_cursor *pCsr);

static int btBalanceMeasure(
  BalanceCtx *p,                  /* Description of balance operation */
  int iCell,                      /* Cell number in this iteration */
  u8 *pCell, int nByte,           /* Binary cell */
  KeyValue *pKV                   /* Key-value cell */
){
................................................................................

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 = p->apOut[p->iOut];   /* Buffer for current output page */
  int iOff;                       /* Offset of new cell within page */
  int nCell;                      /* Number of cells already on page */

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

  if( p->bLeaf==0 && iCell==p->anOut[p->iOut] ){
    /* This cell is destined for the parent page of the siblings being
    ** rebalanced. So instead of writing it to a page buffer it is copied
    ** into the BalanceCtx.aPCell[] array. 
    **
    ** When this cell is eventually written to the parent, the accompanying 
    ** page pointer will be the page number of sibling page p->iOut. This
    ** value will be filled in later. 
    **
    ** The pointer that is currently part of the cell is used as the 
    ** right-child pointer of page p->iOut. This value is written now. */
    int nKey;
    u8 *pKey;
    u8 *pCopy;
    u32 pgno;
    KeyValue *pPKey = &p->aPCell[p->iOut];

    if( pCell ){
      pKey = pCell + sqlite4BtVarintGet32(pCell, &nKey);
      pgno = btGetU32(&pKey[nKey]);
    }else{
      pKey = pKV->pK;
      nKey = pKV->nK;
      pgno = pKV->pgno;
    }

    pCopy = &p->pTmp[p->iTmp];
    p->iTmp += nKey;
    memcpy(pCopy, pKey, nKey);
    pPKey->pK = pCopy;
    pPKey->nK = nKey;

    btPutU32(&aOut[1], pgno);
    p->iOut++;
  }else{

    /* Write the new cell into the output page. */

    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 the flags byte at the start of the 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);

      /* If the siblings are leaf pages, increment BalanceCtx.iOut here.
      ** for internal nodes, it will be incremented by the next call to
      ** this function, after a divider cell is pushed into the parent 
      ** node.  */
      p->iOut += p->bLeaf;
    }
  }

  return SQLITE4_OK;
}

static int btBalanceVisitCells(
  BalanceCtx *p,
................................................................................
  int rc = SQLITE4_OK;            /* Return code */
  int iPg;                        /* Current page in apPg[] */
  int iCall = 0;
  int i;                          /* Used to iterate through KV pairs */

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

  /* Check that page pIns is actually a member of the ctx.apPg[] array. */
#ifndef NDEBUG
  for(i=0; p->apPg[i]!=pIns; i++) assert( i<p->nIn );
#endif

  for(iPg=0; iPg<p->nIn && 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 */

................................................................................

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

      if( pPg==pIns && iCell==iIns ){
        for(i=0; i<p->nKV; i++){
          assert( iCall<p->nCell );
          rc = xVisit(p, iCall++, 0, 0, &p->apKV[i]);
          if( rc!=SQLITE4_OK ) break;
        }
      }

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

    if( pPg==pIns && iIns==nCell ){
      for(i=0; i<p->nKV && rc==SQLITE4_OK; i++){
        assert( iCall<p->nCell );
        rc = xVisit(p, iCall++, 0, 0, &p->apKV[i]);
      }
    }

    /* If the siblings being balanced are not leaves, and the page just
    ** processed was not the right-most sibling, visit a cell from the
    ** parent page.  */
    if( p->bLeaf==0 && iPg<(p->nIn-1) && rc==SQLITE4_OK ){
      int iPar = p->pCsr->nPg-2;
      u8 *aParent = sqlite4BtPageData(p->pCsr->apPage[iPar]);
      u8 *pCell = btCellFind(aParent, pgsz, p->pCsr->aiCell[iPar] + iPg);
      KeyValue kv;
      btInternalCellToKeyValue(pCell, &kv);
      kv.pgno = btGetU32(&aData[1]);
      rc = xVisit(p, iCall++, 0, 0, &kv);
    }
  }

  assert( rc!=SQLITE4_OK || iCall==p->nCell );
  return rc;
}


int btBalance(
  bt_cursor *pCsr,                /* Cursor pointed to page to rebalance */
  int bLeaf,                      /* True if rebalancing leaf pages */
  int nKV,                        /* Number of entries in apKV[] array */
  KeyValue *apKV                  /* Extra entries to add while rebalancing */
){
  bt_db * const pDb = pCsr->pDb; 
  const int pgsz = sqlite4BtPagerPagesize(pDb->pPager);
  const int nSpacePerPage = (pgsz - 1 - 6 - (!bLeaf)*4);

  int iPg;                        /* Used to iterate through pages */
  int iCell;                      /* Used to iterate through cells */




  int anByteOut[5];               /* Bytes of content on each output page */
  BtPage *pPar;                   /* Parent page */
  int iSib;                       /* Index of left-most sibling */


  int rc = SQLITE4_OK;            /* Return code */

  BalanceCtx ctx;
  memset(&ctx, 0, sizeof(ctx));
  ctx.pCsr = pCsr;
  ctx.nKV = nKV;
  ctx.apKV = apKV;
  ctx.pgsz = pgsz;
  ctx.bLeaf = bLeaf;

  memset(anByteOut, 0, sizeof(anByteOut));

  /* Gather the sibling pages from which cells will be redistributed into
  ** the ctx.apPg[] array.  */
  assert( bLeaf==0 || bLeaf==1 );
  assert( pCsr->nPg>1 );
  rc = btGatherSiblings(&ctx);
  if( rc!=SQLITE4_OK ) goto rebalance_out;
  pPar = pCsr->apPage[pCsr->nPg-2];
  iSib = pCsr->aiCell[pCsr->nPg-2];

  /* Count the number of input cells. */
  ctx.nCell = nKV;
  for(iPg=0; iPg<ctx.nIn; iPg++){
    u8 *aData = sqlite4BtPageData(ctx.apPg[iPg]);
    ctx.nCell += btCellCount(aData, pgsz);
  }
  if( bLeaf==0 ) ctx.nCell += (ctx.nIn-1);
  assert( ctx.nCell>0 );

  /* Allocate and populate the anCellSz[] array */
  ctx.anCellSz = (int*)sqlite4_malloc(pDb->pEnv, sizeof(int)*ctx.nCell);
  if( ctx.anCellSz==0 ){
    rc = btErrorBkpt(SQLITE4_NOMEM);
    goto rebalance_out;
  }
  rc = btBalanceVisitCells(&ctx, btBalanceMeasure);

  /* Now figure out the number of output pages required. Set ctx.nOut to 
  ** this value. */
  iCell = 0;
  for(iPg=0; iCell<ctx.nCell; iPg++){

    assert( iPg<array_size(ctx.anOut) );
    if( bLeaf==0 && iPg!=0 ){
      /* This cell will be pushed up to the parent node as a divider cell,
      ** not written to any output page.  */
      iCell++;
    }
    assert( anByteOut[iPg]==0 );
    for(/* noop */; iCell<ctx.nCell; iCell++){
      int nByte = (ctx.anCellSz[iCell] + 2);
      if( nByte+anByteOut[iPg]>nSpacePerPage ) break;
      anByteOut[iPg] += nByte;
    }
    ctx.anOut[iPg] = iCell;
  }
  ctx.nOut = iPg;
  assert( ctx.anOut[ctx.nOut-1]==ctx.nCell );





  /* The loop in the previous block populated the anOut[] array in such a
  ** way as to make the (ctx.nOut-1) leftmost pages completely full but 
  ** leave the rightmost page partially empty. Or, if bLeaf==0, perhaps
  ** even completely empty. This block attempts to redistribute cells a bit 
  ** more evenly. 
  */
  iCell = ctx.nCell;
  
  for(iPg=(ctx.nOut-2); iPg>=0; iPg--){

    int iR = iPg+1;
    while( 1 ){
      int nLeft = ctx.anCellSz[ ctx.anOut[iPg]-1 ] + 2;
      int nRight = (bLeaf ? nLeft : (ctx.anCellSz[ ctx.anOut[iPg] ] + 2));




      if( anByteOut[iPg]==nLeft || (anByteOut[iR] + nRight) > anByteOut[iPg] ){
        break;
      }
      ctx.anOut[iPg]--;
      anByteOut[iPg] -= nLeft;

      anByteOut[iR] += nRight;
    }
  }


#ifdef BT_STDERR_DEBUG
  {
    int iDbg;
    fprintf(stderr, 
        "\nbtBalance(): bLeaf=%d nIn=%d anIn[] = ", ctx.bLeaf, ctx.nIn
    );
    for(iDbg=0; iDbg<ctx.nIn; iDbg++){
      u8 *aData = sqlite4BtPageData(ctx.apPg[iDbg]);
      fprintf(stderr, "%d ", btCellCount(aData, pgsz));
    }
    fprintf(stderr, " ->  nOut=%d anOut[] = ", ctx.nOut);
    for(iDbg=0; iDbg<ctx.nOut; iDbg++){
      fprintf(stderr, "%d ", ctx.anOut[iDbg]);
    }
    fprintf(stderr, "\n");
    fflush(stderr);
  }
#endif

  /* Allocate buffers for the output pages. If the pages being balanced
  ** are not leaves, grab one more buffer from the pager layer to use
  ** to temporarily store a copy of the keys destined for the parent
  ** page.  */
  for(iPg=0; iPg<ctx.nOut; iPg++){
    rc = btNewBuffer(pDb, &ctx.apOut[iPg]);
    if( rc!=SQLITE4_OK ) goto rebalance_out;
    memset(ctx.apOut[iPg] + pgsz-6, 0, 6);
  }
  if( bLeaf==0 ){
    rc = btNewBuffer(pDb, &ctx.pTmp);
    if( rc!=SQLITE4_OK ) goto rebalance_out;
  }

  /* Populate the new buffers with the new page images. */
  rc = btBalanceVisitCells(&ctx, btBalanceOutput);
  if( rc!=SQLITE4_OK ) goto rebalance_out;

  if( ctx.bLeaf==0 ){
    /* Set the right-child pointer of the rightmost new sibling to a copy
    ** of the same pointer from the rightmost original sibling.  */
    u8 *aRightSibling = sqlite4BtPageData(ctx.apPg[ctx.nIn-1]);
    memcpy(&(ctx.apOut[ctx.nOut-1])[1], &aRightSibling[1], 4);
  }

  /* Clobber the old pages with the new buffers */
  for(iPg=0; iPg<ctx.nOut; iPg++){
    if( iPg>=ctx.nIn ){
      rc = sqlite4BtPageAllocate(pDb->pPager, &ctx.apPg[iPg]);
      if( rc!=SQLITE4_OK ) goto rebalance_out;
    }
    btSetBuffer(pDb, ctx.apPg[iPg], ctx.apOut[iPg]);
    ctx.apOut[iPg] = 0;
  }
  for(iPg=ctx.nOut; iPg<ctx.nIn; iPg++){
    rc = sqlite4BtPageTrim(ctx.apPg[iPg]);
    ctx.apPg[iPg] = 0;
    if( rc!=SQLITE4_OK ) goto rebalance_out;
  }


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

  /* The leaves are written. Now gather the keys and page numbers to
  ** push up into the parent page. This is only required when rebalancing
  ** b-tree leaves. When internal nodes are balanced, the btBalanceOutput
  ** loop accumulates the cells destined for the parent page.  */
  for(iPg=0; iPg<(ctx.nOut-1); iPg++){
    if( bLeaf ){
      u8 *aData = sqlite4BtPageData(ctx.apPg[iPg]);
      u8 *pCell;

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

  rc = btSetChildPgno(
      pDb, pPar, iSib+ctx.nIn-1, sqlite4BtPagePgno(ctx.apPg[ctx.nOut-1])
  );
  if( rc==SQLITE4_OK ){
    pCsr->nPg--;
    rc = btDeleteFromPage(pCsr, ctx.nIn-1);
  }
  iPg = pCsr->nPg;
  if( rc==SQLITE4_OK && ctx.nOut>1 ){
    rc = btInsertAndBalance(pCsr, ctx.nOut-1, ctx.aPCell);
  }
  if( rc==SQLITE4_OK && iPg==pCsr->nPg ){
    rc = btBalanceIfUnderfull(pCsr);
  }


#ifdef BT_STDERR_DEBUG
  {
    u8 *aData = sqlite4BtPageData(pPar);
    printPage(stderr, sqlite4BtPagePgno(pPar), aData, pgsz);
  }
#endif

 rebalance_out:
  for(iPg=0; iPg<array_size(ctx.apPg); iPg++){
    sqlite4BtPageRelease(ctx.apPg[iPg]);
  }
  btFreeBuffer(pDb, ctx.pTmp);
  return rc;
}

static int btExtendTree(bt_cursor *pCsr){
  bt_db * const pDb = pCsr->pDb;
  const int pgsz = sqlite4BtPagerPagesize(pDb->pPager);
  int rc;                         /* Return code */
................................................................................
  u8 *aData;                      /* Page buffer */
  int nCell;                      /* Number of cells on this page already */
  int nFree;                      /* Contiguous free space on this page */
  int nReq = 0;                   /* Space required for type (a) cells */
  int iCell;                      /* Position to insert new key */
  int iWrite;                     /* Byte offset at which to write new cell */
  int i;
  int bLeaf;                      /* True if inserting into leaf page */
  BtPage *pLeaf;


  /* Bytes of space required on the current page. */
  for(i=0; i<nKV; i++){
    nReq += btKVCellSize(&apKV[i], pgsz) + 2;
  }

  iCell = pCsr->aiCell[pCsr->nPg-1];
  assert( pCsr->nPg>0 );
  pLeaf = pCsr->apPage[pCsr->nPg-1];
  aData = (u8*)sqlite4BtPageData(pLeaf);

  /* Set the bLeaf variable to true if inserting into a leaf page, or
  ** false otherwise. Return SQLITE4_CORRUPT if the page is a leaf but
  ** the KeyValue pairs being inserted are suitable for internal nodes,
  ** or vice-versa.  */
  assert( nKV>0 );
  bLeaf = (apKV[0].pgno==0);
  if( (0==(btFlags(aData, pgsz) & BT_PGFLAGS_INTERNAL))!=bLeaf ){
    return btErrorBkpt(SQLITE4_CORRUPT);
  }

  nCell = btCellCount(aData, pgsz);
  assert( iCell<=btCellCount(aData, pgsz) );

  if( nCell==0 ){
    /* If the nCell field is zero, then the rest of the header may 
    ** contain invalid values (zeroes - as it may never have been 
    ** initialized). So set our stack variables to values appropriate
    ** to an empty page explicitly here.  */
    iWrite = (bLeaf ? 1 : 5);
    nFree = pgsz - iWrite - 6;
  }else{
    if( btFreeContiguous(aData, pgsz)<nReq && btFreeSpace(aData, pgsz)>=nReq ){
      /* Special case - the new entry will not fit on the page at present
      ** but would if the page were defragmented. So defragment it before
      ** continuing.  */
      rc = btDefragmentPage(pCsr->pDb, pLeaf);
................................................................................
    /* The new entry will not fit on the leaf page. Entries will have
    ** to be shuffled between existing leaves and new leaves may need
    ** to be added to make space for it. */
    if( pCsr->nPg==1 ){
      rc = btExtendTree(pCsr);
    }
    if( rc==SQLITE4_OK ){
      rc = btBalance(pCsr, bLeaf, nKV, apKV);
    }
  }

  return rc;
}

static int btDeleteFromPage(bt_cursor *pCsr, int nDel){
................................................................................

    /* Increase total free space */
    btPutU16(&aData[pgsz-4], btFreeSpace(aData, pgsz) + nFreed);
  }
  
  return rc;
}

static int btBalanceIfUnderfull(bt_cursor *pCsr){
  const int pgsz = sqlite4BtPagerPagesize(pCsr->pDb->pPager);
  int rc = SQLITE4_OK;
  int iPg = pCsr->nPg-1;
  BtPage *pPg = pCsr->apPage[iPg];
  u8 *aData = sqlite4BtPageData(pPg);
  int nCell = btCellCount(aData, pgsz);
  int nFree = btFreeSpace(aData, pgsz);
  int bLeaf = (0==(btFlags(aData, pgsz) & BT_PGFLAGS_INTERNAL));

  if( iPg==0 ){
    /* Root page. If it contains no cells at all and is not already
    ** a leaf, shorten the tree by one here by copying the contents 
    ** of the only child into the root. */
    if( nCell==0 && bLeaf==0 ){
      BtPager *pPager = pCsr->pDb->pPager;
      u32 pgno = btChildPgno(aData, pgsz, 0);
      BtPage *pChild;

      rc = sqlite4BtPageWrite(pPg);
      if( rc==SQLITE4_OK ){
        rc = sqlite4BtPageGet(pPager, pgno, &pChild);
      }
      if( rc==SQLITE4_OK ){
        u8 *a = sqlite4BtPageData(pChild);
        memcpy(aData, a, pgsz);
        rc = sqlite4BtPageTrim(pChild);
      }
    }
  }else if( nCell==0 || (nFree<(pgsz/3) && bLeaf==0) ){
    rc = btBalance(pCsr, bLeaf, 0, 0);
  }
  return rc;
}

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

  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
    ** the cursor.  */
    rc = sqlite4BtDelete(&csr);
    if( rc==SQLITE4_OK ){
      rc = btCsrSeek(&csr, pK, nK, BT_SEEK_GE, 1);
    }
  }
  if( rc==SQLITE4_OK ) rc = btErrorBkpt(SQLITE4_CORRUPT);

  if( rc==SQLITE4_NOTFOUND || rc==SQLITE4_INEXACT ){
    /* Insert the new KV pair into the current leaf. */
    KeyValue kv;
................................................................................
    rc = btInsertAndBalance(&csr, 1, &kv);
  }

  return rc;
}

int sqlite4BtDelete(bt_cursor *pCsr){
  int rc;
  rc =  btDeleteFromPage(pCsr, 1);
  if( rc==SQLITE4_OK ){
    rc = btBalanceIfUnderfull(pCsr);
  }
}

int sqlite4BtSetCookie(bt_db *db, unsigned int iVal){
  return sqlite4BtPagerSetCookie(db->pPager, iVal);
}

int sqlite4BtGetCookie(bt_db *db, unsigned int *piVal){
  return sqlite4BtPagerGetCookie(db->pPager, piVal);
}

Changes to src/bt_pager.c

107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
...
455
456
457
458
459
460
461




462
463
464
465
466
467
468
...
496
497
498
499
500
501
502




503
504
505
506
507
508

509
510

511
512
513
514
515
516
517
...
532
533
534
535
536
537
538

539

540
541
542
543
544
545
546
    aNew = (BtPage **)sqlite4_malloc(p->pEnv, nNew*sizeof(BtPage*));
    if( aNew==0 ) return btErrorBkpt(SQLITE4_NOMEM);
    memset(aNew, 0, nNew*sizeof(BtPage*));
    for(i=0; i<p->hash.nHash; i++){
      while( aOld[i] ){
        BtPage *pShift = aOld[i];
        aOld[i] = pShift->pNextHash;
        h = hashkey(nNew, pPg->pgno);
        pShift->pNextHash = aNew[h];
        aNew[h] = pShift;
      }
    }
    p->hash.aHash = aNew;
    p->hash.nHash = nNew;
    sqlite4_free(p->pEnv, aOld);
................................................................................

/*
** Read, write and trim existing database pages.
*/
int sqlite4BtPageGet(BtPager *p, u32 pgno, BtPage **ppPg){
  int rc = SQLITE4_OK;            /* Return code */
  BtPage *pRet;                   /* Returned page handle */





  /* Search the cache for an existing page. */
  pRet = btHashSearch(p, pgno);

  /* If the page is not in the cache, load it from disk */
  if( pRet==0 ){
    rc = btAllocatePage(p, &pRet);
................................................................................
    pPg->flags |= BT_PAGE_DIRTY;
    pPg->pNextDirty = pPg->pPager->pDirty;
    pPg->pPager->pDirty = pPg;
  }
  return SQLITE4_OK;
}





int sqlite4BtPageTrim(BtPage *pPg){
  assert( !"todo" );
  return SQLITE4_OK;
}

int sqlite4BtPageRelease(BtPage *pPg){

  assert( pPg->nRef>=1 );
  pPg->nRef--;

  return SQLITE4_OK;
}

void sqlite4BtPageReference(BtPage *pPg){
  assert( pPg->nRef>=1 );
  pPg->nRef++;
  return 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.







|







 







>
>
>
>







 







>
>
>
>

|




>
|
|
>







 







>

>







107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
...
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
...
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
...
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
    aNew = (BtPage **)sqlite4_malloc(p->pEnv, nNew*sizeof(BtPage*));
    if( aNew==0 ) return btErrorBkpt(SQLITE4_NOMEM);
    memset(aNew, 0, nNew*sizeof(BtPage*));
    for(i=0; i<p->hash.nHash; i++){
      while( aOld[i] ){
        BtPage *pShift = aOld[i];
        aOld[i] = pShift->pNextHash;
        h = hashkey(nNew, pShift->pgno);
        pShift->pNextHash = aNew[h];
        aNew[h] = pShift;
      }
    }
    p->hash.aHash = aNew;
    p->hash.nHash = nNew;
    sqlite4_free(p->pEnv, aOld);
................................................................................

/*
** Read, write and trim existing database pages.
*/
int sqlite4BtPageGet(BtPager *p, u32 pgno, BtPage **ppPg){
  int rc = SQLITE4_OK;            /* Return code */
  BtPage *pRet;                   /* Returned page handle */

  if( pgno>100000 ){
    return btErrorBkpt(SQLITE4_CORRUPT);
  }

  /* Search the cache for an existing page. */
  pRet = btHashSearch(p, pgno);

  /* If the page is not in the cache, load it from disk */
  if( pRet==0 ){
    rc = btAllocatePage(p, &pRet);
................................................................................
    pPg->flags |= BT_PAGE_DIRTY;
    pPg->pNextDirty = pPg->pPager->pDirty;
    pPg->pPager->pDirty = pPg;
  }
  return SQLITE4_OK;
}

/*
** Decrement the refcount on page pPg. Also, indicate that page pPg is
** no longer in use.
*/
int sqlite4BtPageTrim(BtPage *pPg){
  /* assert( !"todo" ); */
  return SQLITE4_OK;
}

int sqlite4BtPageRelease(BtPage *pPg){
  if( pPg ){
    assert( pPg->nRef>=1 );
    pPg->nRef--;
  }
  return SQLITE4_OK;
}

void sqlite4BtPageReference(BtPage *pPg){
  assert( pPg->nRef>=1 );
  pPg->nRef++;
  return SQLITE4_OK;
................................................................................
      sqlite4BtPageRelease(pPg);
      pPg = 0;
    }else{
      p->dbhdr.nPg = pgno;
    }
  }

#ifdef BT_STDERR_DEBUG
  fprintf(stderr, "allocated page %d\n", pgno);
#endif

  *ppPg = pPg;
  return rc;
}

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

Changes to test/simple3.test

88
89
90
91
92
93
94


95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

113










































114
115
116
}

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

#--------------------------------------------------------------------------


do_test 3.0 {
  catch { db close }
  forcedelete test.db
  sqlite4 db file:test.db?kv=bt
} {}

do_execsql_test 3.1 {
  CREATE TABLE t1(a PRIMARY KEY, b);
}

for {set i 0} {$i < 100} {incr i} {
if {$i==6} breakpoint
  lappend rows $i
  do_execsql_test 3.2.$i {
    INSERT INTO t1 VALUES($i, randomblob(200));
    SELECT a FROM t1 ORDER BY a;
  } $rows
}













































finish_test








>
>











<






>

>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>



88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
}

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

#--------------------------------------------------------------------------
# Insert many rows in sequence.
#
do_test 3.0 {
  catch { db close }
  forcedelete test.db
  sqlite4 db file:test.db?kv=bt
} {}

do_execsql_test 3.1 {
  CREATE TABLE t1(a PRIMARY KEY, b);
}

for {set i 0} {$i < 100} {incr i} {

  lappend rows $i
  do_execsql_test 3.2.$i {
    INSERT INTO t1 VALUES($i, randomblob(200));
    SELECT a FROM t1 ORDER BY a;
  } $rows
}
set nInitial 100

if 1 {
for {set i 0} {$i < 100} {incr i} {
  if {[set_test_counter errors]} break
  do_test 3.3.$i {
    for {set j 0} {$j < 1000} {incr j} {
      set pk [expr 100 + $i*1000 + $j]
      execsql { INSERT INTO t1 VALUES($pk, randomblob(200)) }
    }
    execsql { SELECT count(*) FROM t1 } 
  } [expr ($i+1)*1000 + 100]
}
set nInitial 100100
}

do_test 3.4 {
  for {set i 0} {$i < $nInitial} {incr i} {
    set res [execsql {SELECT count(*) FROM t1 WHERE a = $i}]
    if {$res!="1"} { error "res = $res for i=$i" }
  }
} {}

#--------------------------------------------------------------------------
# Remove many rows in sequence.
#
for {set i 0} {$i < 100} {incr i} {
if {$i == 5} breakpoint
  do_execsql_test 4.1.$i {
    DELETE FROM t1 WHERE a = $i;
    SELECT count(*) FROM t1;
  } [expr $nInitial - 1 - $i]
  if {[set_test_counter errors]} break
}

for {set i 100} {$i < $nInitial} {incr i 1000} {
  if {[set_test_counter errors]} break
  do_test 4.2.$i {
    for {set j 0} {$j < 1000} {incr j} {
      execsql { DELETE FROM t1 WHERE a = ($i + $j) }
    }
    execsql { SELECT count(*) FROM t1 }
  } [expr $nInitial - $i - 1000]
}

finish_test