SQLite4
Check-in [65735e3ca9]
Not logged in

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

Overview
SHA1 Hash:65735e3ca96cae08067a33906bba4edfcf4c31a9
Date: 2013-11-27 18:21:54
User: dan
Comment:Begin adding code for querying the fast-insert tree.
Tags And Properties
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to lsm-test/lsmtest.h

92
93
94
95
96
97
98
99

100
101
102
103
104
105
106
int test_lsm_small_open(const char*, const char*, int bClear, TestDb **ppDb);
int test_lsm_mt2(const char*, const char *zFile, int bClear, TestDb **ppDb);
int test_lsm_mt3(const char*, const char *zFile, int bClear, TestDb **ppDb);

int tdb_lsm_configure(lsm_db *, const char *);

/* Functions in lsmtest_tdb4.c */
int test_bt_open(const char*, const char *zFilename, int bClear, TestDb **ppDb);



/* Functions in testutil.c. */
int  testPrngInit(void);
u32  testPrngValue(u32 iVal);
void testPrngArray(u32 iVal, u32 *aOut, int nOut);
void testPrngString(u32 iVal, char *aOut, int nOut);







|
>







92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
int test_lsm_small_open(const char*, const char*, int bClear, TestDb **ppDb);
int test_lsm_mt2(const char*, const char *zFile, int bClear, TestDb **ppDb);
int test_lsm_mt3(const char*, const char *zFile, int bClear, TestDb **ppDb);

int tdb_lsm_configure(lsm_db *, const char *);

/* Functions in lsmtest_tdb4.c */
int test_bt_open(const char*, const char *zFile, int bClear, TestDb **ppDb);
int test_fbt_open(const char*, const char *zFile, int bClear, TestDb **ppDb);


/* Functions in testutil.c. */
int  testPrngInit(void);
u32  testPrngValue(u32 iVal);
void testPrngArray(u32 iVal, u32 *aOut, int nOut);
void testPrngString(u32 iVal, char *aOut, int nOut);

Changes to lsm-test/lsmtest_tdb.c

706
707
708
709
710
711
712

713
714
715
716
717
718
719
*/
static struct Lib {
  const char *zName;
  const char *zDefaultDb;
  int (*xOpen)(const char *, const char *zFilename, int bClear, TestDb **ppDb);
} aLib[] = {
  { "bt",           "testdb.bt",        test_bt_open },

  { "sqlite3",      "testdb.sqlite",    sql_open },
  { "lsm_small",    "testdb.lsm_small", test_lsm_small_open },
  { "lsm_lomem",    "testdb.lsm_lomem", test_lsm_lomem_open },
#ifdef HAVE_ZLIB
  { "lsm_zip",      "testdb.lsm_zip",   test_lsm_zip_open },
#endif
  { "lsm",          "testdb.lsm",       test_lsm_open },







>







706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
*/
static struct Lib {
  const char *zName;
  const char *zDefaultDb;
  int (*xOpen)(const char *, const char *zFilename, int bClear, TestDb **ppDb);
} aLib[] = {
  { "bt",           "testdb.bt",        test_bt_open },
  { "fbt",          "testdb.fbt",       test_fbt_open },
  { "sqlite3",      "testdb.sqlite",    sql_open },
  { "lsm_small",    "testdb.lsm_small", test_lsm_small_open },
  { "lsm_lomem",    "testdb.lsm_lomem", test_lsm_lomem_open },
#ifdef HAVE_ZLIB
  { "lsm_zip",      "testdb.lsm_zip",   test_lsm_zip_open },
#endif
  { "lsm",          "testdb.lsm",       test_lsm_open },

Changes to lsm-test/lsmtest_tdb4.c

753
754
755
756
757
758
759









760
761
762
763
764
765
766
  if( rc!=SQLITE4_OK && p ){
    bt_close(&p->base);
  }

  *ppDb = &p->base;
  return rc;
}










void tdb_bt_prepare_sync_crash(TestDb *pTestDb, int iSync){
  BtDb *p = (BtDb*)pTestDb;
  assert( pTestDb->pMethods->xClose==bt_close );
  assert( p->bCrash==0 );
  p->nCrashSync = iSync;
}







>
>
>
>
>
>
>
>
>







753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
  if( rc!=SQLITE4_OK && p ){
    bt_close(&p->base);
  }

  *ppDb = &p->base;
  return rc;
}

int test_fbt_open(
  const char *zSpec, 
  const char *zFilename, 
  int bClear, 
  TestDb **ppDb
){
  return test_bt_open("fast=1", zFilename, bClear, ppDb);
}

void tdb_bt_prepare_sync_crash(TestDb *pTestDb, int iSync){
  BtDb *p = (BtDb*)pTestDb;
  assert( pTestDb->pMethods->xClose==bt_close );
  assert( p->bCrash==0 );
  p->nCrashSync = iSync;
}

Changes to src/bt_main.c

24
25
26
27
28
29
30

31
32
33
34
35
36
37
38
39
40
41
42
..
52
53
54
55
56
57
58

59
60
61
62
63
64
65
..
69
70
71
72
73
74
75

76
77








78
79
80
81
82
83
84
..
85
86
87
88
89
90
91
92
93
94


95







96
97
98
99
100
101
102
...
219
220
221
222
223
224
225
226
227
228
229
230
231





232








233
234
235
236
237
238
239
240
241






242
243
244
245

246
247
248
249
250
251
252
...
263
264
265
266
267
268
269












270
271
272

273

274





275
276
277
278
279
280
281
282
283
284
285

286

287
288
289
290
291
292
293
...
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
...
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
...
838
839
840
841
842
843
844



















































































































































































845
846
847
848
849
850
851
....
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
....
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
....
2546
2547
2548
2549
2550
2551
2552
2553
2554
2555


2556
2557
2558
2559
2560
2561
2562
2563
2564




2565
2566
2567
2568
2569
2570
2571
....
2726
2727
2728
2729
2730
2731
2732
2733
2734
2735
2736
2737
2738
2739
2740
2741
2742
2743
2744
2745
2746
2747
2748
2749
2750
2751
2752
2753
2754
2755
2756
....
2770
2771
2772
2773
2774
2775
2776
2777
2778

2779
2780
2781
2782

2783
2784
2785
2786
2787
2788
2789
....
2814
2815
2816
2817
2818
2819
2820

2821
2822
2823
2824
2825
2826
2827
** b-tree pages. 
*/
#define BT_PGFLAGS_INTERNAL 0x01  /* True for non-leaf nodes */

/* #define BT_STDERR_DEBUG 1 */

typedef struct BtCursor BtCursor;


struct bt_db {
  sqlite4_env *pEnv;              /* SQLite environment */
  BtPager *pPager;                /* Underlying page-based database */
  BtCursor *pAllCsr;             /* List of all open cursors */
  int bFastInsertOp;              /* Set by CONTROL_FAST_INSERT_OP */
};

typedef struct BtOvfl BtOvfl;
struct BtOvfl {
  int nKey;
  int nVal;
................................................................................
/* 
** Base class for both cursor types (BtCursor and FiCursor).
*/
struct bt_cursor {
  int eType;                      /* Cursor type */
  void *pExtra;                   /* Extra allocated space */
  bt_db *pDb;                     /* Database this cursor belongs to */

};

/*
** Database b-tree cursor handle.
*/
struct BtCursor {
  bt_cursor base;                 /* Base cursor class */
................................................................................
  int aiCell[BT_MAX_DEPTH];       /* Current cell of each apPage[] entry */
  BtPage *apPage[BT_MAX_DEPTH];   /* All pages from root to current leaf */
  BtOvfl ovfl;                    /* Overflow cache (see above) */

  int bRequireReseek;             /* True if a btCsrReseek() is required */
  int bSkipNext;                  /* True if next CsrNext() is a no-op */
  int bSkipPrev;                  /* True if next CsrPrev() is a no-op */


  BtCursor *pNextCsr;            /* Next cursor opened by same db handle */








};

#ifndef btErrorBkpt
int btErrorBkpt(int rc){
  static int error_cnt = 0;
  error_cnt++;
  return rc;
................................................................................
}
#endif

#if !defined(NDEBUG) 
static void btCheckPageRefs(bt_db *pDb){
  int nActual = 0;                /* Outstanding refs according to pager */
  int nExpect = 0;                /* According to the set of open cursors */
  BtCursor *pCsr;                 /* Iterator variable */

  for(pCsr=pDb->pAllCsr; pCsr; pCsr=pCsr->pNextCsr){


    if( pCsr->nPg>0 ) nExpect += pCsr->nPg;







  }
  nActual = sqlite4BtPagerRefcount(pDb->pPager);
  assert( nActual==nExpect );
}
#else
# define btCheckPageRefs(x) 
#endif
................................................................................
  pCsr->base.pDb = db;
  pCsr->iRoot = iRoot;
  sqlite4_env_config(db->pEnv, SQLITE4_ENVCONFIG_GETMM, &pCsr->ovfl.buf.pMM);
}

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

  assert( sqlite4BtPagerTransactionLevel(db->pPager)>0 );

  if( db->bFastInsertOp ){
    assert( 0 );





  }else{








    BtCursor *pCsr;                /* New cursor object */
    nByte = sizeof(BtCursor) + nExtra;
    pCsr = (BtCursor*)sqlite4_malloc(db->pEnv, nByte);
    *ppCsr = (bt_cursor*)pCsr;
    if( pCsr==0 ){
      rc = btErrorBkpt(SQLITE4_NOMEM);
    }else{
      u32 iRoot = sqlite4BtPagerDbhdr(db->pPager)->iRoot;
      btCsrSetup(db, iRoot, pCsr);






      pCsr->pNextCsr = db->pAllCsr;
      db->pAllCsr = pCsr;
    }
  }


  btCheckPageRefs(db);
  db->bFastInsertOp = 0;
  return rc;
}

static void btCsrReleaseAll(BtCursor *pCsr){
................................................................................
  if( bFreeBuffer ){
    sqlite4_buffer_clear(&pCsr->ovfl.buf);
  }
  pCsr->bSkipNext = 0;
  pCsr->bSkipPrev = 0;
  pCsr->bRequireReseek = 0;
}













int sqlite4BtCsrClose(bt_cursor *pCsr){
  if( pCsr ){

    bt_db *pDb = pCsr->pDb;

    btCheckPageRefs(pDb);





    if( pCsr->eType==CSR_TYPE_BT ){
      /* A regular b-tree cursor */
      BtCursor *p = (BtCursor*)pCsr;
      BtCursor **pp;
      btCsrReset(p, 1);
      for(pp=&pDb->pAllCsr; *pp!=p; pp=&(*pp)->pNextCsr);
      *pp = p->pNextCsr;
      sqlite4_free(pDb->pEnv, p);
    }else{
      /* A fast-insert-tree cursor */
      assert( 0 );

    }

    btCheckPageRefs(pDb);
  }
  return SQLITE4_OK;
}

void *sqlite4BtCsrExtra(bt_cursor *pCsr){
  return pCsr->pExtra;
................................................................................

  if( rc!=SQLITE4_OK && rc!=SQLITE4_INEXACT && eCsrseek!=BT_CSRSEEK_UPDATE ){
    btCsrReset(pCsr, 0);
  }
  return rc;
}

int sqlite4BtCsrSeek(
  bt_cursor *pBase, 
  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 rc;
  btCheckPageRefs(pBase->pDb);
  if( pBase->eType==CSR_TYPE_BT ){
    BtCursor *pCsr = (BtCursor*)pBase;
    rc = btCsrSeek(pCsr, pK, nK, eSeek, BT_CSRSEEK_SEEK);
  }else{
    /* fast-insert-tree cursor */
    assert( 0 );
  }
  btCheckPageRefs(pBase->pDb);
  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(BtCursor *pCsr, int bLast){
  const int pgsz = sqlite4BtPagerPagesize(pCsr->base.pDb->pPager);
  int rc = SQLITE4_OK;            /* Return Code */
  u32 pgno;                       /* Page number for next page to load */

  /* Reset the cursor */
  btCsrReset(pCsr, 0);

  /* Figure out the root page number */
  assert( pCsr->iRoot>1 && pCsr->nPg==0 );
  pgno = pCsr->iRoot;

  while( rc==SQLITE4_OK ){
    /* Load page number pgno into the b-tree */
    rc = btCsrDescend(pCsr, pgno);
    if( rc==SQLITE4_OK ){
      int nCell;                  /* Number of cells on this page */
      int nByte;
      u8 *pCell;
      u8 *aData = (u8*)sqlite4BtPageData(pCsr->apPage[pCsr->nPg-1]);

      nCell = btCellCount(aData, pgsz);
      if( nCell==0 ){
        btCsrReset(pCsr, 0);
        return SQLITE4_NOTFOUND;
      }

      /* If the cursor has descended to a leaf break out of the loop. */
      pCsr->aiCell[pCsr->nPg-1] = (bLast ? nCell : 0);
      if( (aData[0] & BT_PGFLAGS_INTERNAL)==0 ) break;
      
      /* Otherwise, set pgno to the left or rightmost child of the page
      ** just loaded, depending on whether the cursor is seeking to the
      ** start or end of the tree.  */
      if( bLast==0 ){
        pCell = btCellFind(aData, pgsz, 0);
        pCell += sqlite4BtVarintGet32(pCell, &nByte);
        pCell += nByte;
        sqlite4BtVarintGet32(pCell, (int *)&pgno);
      }else{
        pgno = btGetU32(&aData[1]);
      }
    }
  }
  if( pCsr->aiCell[pCsr->nPg-1] ) pCsr->aiCell[pCsr->nPg-1]--;
  return rc;
}

/*
** Position cursor pCsr to point to the smallest key in the database.
*/
int sqlite4BtCsrFirst(bt_cursor *pCsr){
  int rc;
  if( pCsr->eType==CSR_TYPE_BT ){
    rc = btCsrEnd((BtCursor*)pCsr, 0);
  }else{
    assert( 0 );
  }
  return rc;
}

/*
** Position cursor pCsr to point to the largest key in the database.
*/
int sqlite4BtCsrLast(bt_cursor *pCsr){
  int rc;
  if( pCsr->eType==CSR_TYPE_BT ){
    rc = btCsrEnd((BtCursor*)pCsr, 1);
  }else{
    assert( 0 );
  }
  return rc;
}

static int btCsrReseek(BtCursor *pCsr){
  int rc = SQLITE4_OK;
  if( pCsr->bRequireReseek ){
    BtOvfl ovfl;
    memcpy(&ovfl, &pCsr->ovfl, sizeof(BtOvfl));

    pCsr->ovfl.buf.n = 0;
................................................................................
      pCsr->ovfl.buf.p = ovfl.buf.p;
    }else{
      sqlite4_buffer_clear(&ovfl.buf);
    }
  }
  return rc;
}


/*
** This function does the work of both sqlite4BtCsrNext() (if parameter
** bNext is true) and Pref() (if bNext is false).
*/
static int btCsrStep(BtCursor *pCsr, int bNext){
  const int pgsz = sqlite4BtPagerPagesize(pCsr->base.pDb->pPager);
................................................................................
      }
    }
  }

  return rc;
}





















































































































































































/*
** Advance to the next entry in the tree.
*/
int sqlite4BtCsrNext(bt_cursor *pCsr){
  int rc;
  if( pCsr->eType==CSR_TYPE_BT ){
................................................................................
      u32 rootpgno = btGetU32(&pOvfl[1 + nDirect*4]);
      rc = btOverflowTrimtree(pgsz, pPager, rootpgno, nDepth);
    }
  }

  return rc;
}

int sqlite4BtCsrKey(bt_cursor *pBase, const void **ppK, int *pnK){
  int rc = SQLITE4_OK;            /* Return code */
  
  if( pBase->eType==CSR_TYPE_BT ){
    BtCursor *pCsr = (BtCursor*)pBase;
    if( pCsr->bRequireReseek ){
      *ppK = (const void*)pCsr->ovfl.buf.p;
      *pnK = pCsr->ovfl.nKey;
    }else{
      const int pgsz = sqlite4BtPagerPagesize(pCsr->base.pDb->pPager);
      u8 *aData;
      u8 *pCell;
      int nK;
      int iCell = pCsr->aiCell[pCsr->nPg-1];

      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 ){
        /* type (c) leaf cell */
        rc = btCsrBuffer(pCsr, 0);
        if( rc==SQLITE4_OK ){
          *ppK = pCsr->ovfl.buf.p;
          *pnK = pCsr->ovfl.nKey;
        }
      }else{
        *ppK = pCell;
        *pnK = nK;
      }
    }

























  }else{













































    assert( 0 );

  }

  return rc;
}

int sqlite4BtCsrData(
  bt_cursor *pBase,               /* Cursor handle */
  int iOffset,                    /* Offset of requested data */
  int nByte,                      /* Bytes requested (or -ve for all avail.) */
  const void **ppV,               /* OUT: Pointer to data buffer */
  int *pnV                        /* OUT: Size of data buffer in bytes */
){
  const int pgsz = sqlite4BtPagerPagesize(pBase->pDb->pPager);
  int rc;
  u8 *aData;
  u8 *pCell;
  int nK = 0;
  int nV = 0;

  if( pBase->eType==CSR_TYPE_BT ){
    BtCursor *pCsr = (BtCursor*)pBase;
    int iCell = pCsr->aiCell[pCsr->nPg-1];

    rc = btCsrReseek(pCsr);
    if( rc==SQLITE4_OK ){
      if( pCsr->bSkipNext || pCsr->bSkipPrev ){
        /* The row has been deleted out from under this cursor. So return
         ** NULL for data.  */
        *ppV = 0;
        *pnV = 0;

      }else{

        aData = (u8*)sqlite4BtPageData(pCsr->apPage[pCsr->nPg-1]);
        pCell = btCellFind(aData, pgsz, iCell);
        pCell += sqlite4BtVarintGet32(pCell, &nK);
        if( nK>0 ){
          pCell += nK;
          pCell += sqlite4BtVarintGet32(pCell, &nV);
        }

        if( nV==0 ){
          rc = btCsrBuffer(pCsr, 1);
          if( rc==SQLITE4_OK ){
            u8 *aBuf = (u8*)pCsr->ovfl.buf.p;
            *ppV = &aBuf[pCsr->ovfl.nKey];
            *pnV = pCsr->ovfl.nVal;
          }
        }else{
          *ppV = pCell;
          *pnV = (nV-1);
        }

#ifndef NDEBUG
        if( rc==SQLITE4_OK ){
          const void *pK; int nK;
          rc = sqlite4BtCsrKey((bt_cursor*)pCsr, &pK, &nK);
          if( rc==SQLITE4_OK ){
            BtLock *pLock = (BtLock*)pCsr->base.pDb->pPager;
            sqlite4BtDebugKV(pLock, "select", (u8*)pK, nK, (u8*)*ppV, *pnV);
          }
        }
#endif
      }
    }
  }else{

    assert( 0 );

  }

  return rc;
}

/*
** The argument points to a buffer containing an overflow array. Return
................................................................................
  nPg = (nContent + pgsz - 1) / pgsz;
  if( nPg<=BT_MAX_DIRECT_OVERFLOW ){
    return 1 + nPg*4;
  }
  return 1 + (BT_MAX_DIRECT_OVERFLOW+1) * 4;
}

static u32 btBlockToRoot(BtDbHdr *pHdr, u32 iBlk){
  assert( iBlk>0 );
  return (iBlk - 1) * (pHdr->blksz / pHdr->pgsz) + 1;
}

/*
** Allocate a non-overflow page.
**
** This function is a simple wrapper around sqlite4BtPageAllocate(),
** except that if the database is currenly in fast-insert mode the
** BtDbHdr.nSubPg counter is incremented.
*/
................................................................................
    rc = btBalance(pCsr, bLeaf, 0, 0);
  }
  return rc;
}

static int btSaveAllCursor(bt_db *pDb, BtCursor *pCsr){
  int rc = SQLITE4_OK;            /* Return code */
  BtCursor *p;                    /* Used to iterate through cursors */

  for(p=pDb->pAllCsr; rc==SQLITE4_OK && p; p=p->pNextCsr){


    if( p->nPg>0 ){
      assert( p->bRequireReseek==0 );
      rc = btCsrBuffer(p, 0);
      if( rc==SQLITE4_OK ){
        assert( p->ovfl.buf.p );
        p->bRequireReseek = 1;
        if( p!=pCsr ) btCsrReleaseAll(p);
      }
    }




  }

  return rc;
}

static int btFastInsertRoot(bt_db *db, BtDbHdr *pHdr, u32 *piRoot);

................................................................................
    rc = btFindNextLevel(db, pHdr, &iLevel);
    if( rc==SQLITE4_OK ){
      rc = btAllocateBlock(db, &iSubBlock);
    }

    if( rc==SQLITE4_OK ){
      u8 aKey[8];
      u8 aVal[8];
      pHdr->iSubBlock = iSubBlock;
      pHdr->nSubPg = 1;           /* Root page is automatically allocated */

      /* The key for the new entry consists of the concatentation of two 
      ** 32-bit big-endian integers - the <age> and <level-no>. The age
      ** of the new segment is 0. The level number is one greater than the
      ** level number of the previous segment.  */
      btPutU32(&aKey[0], 0);
      btPutU32(&aKey[4], ~iLevel);

      btPutU32(&aVal[0], iSubBlock);
      btPutU32(&aVal[4], 1);

      assert( db->bFastInsertOp==1 );
      db->bFastInsertOp = 0;
      rc = btReplaceEntry(db, pHdr->iMRoot, aKey, 8, aVal, 8);
      db->bFastInsertOp = 1;
    }
  }

  if( rc==SQLITE4_OK ){
    *piRoot = btBlockToRoot(pHdr, pHdr->iSubBlock);
  }
................................................................................
  sqlite4BtDebugKV((BtLock*)db->pPager, "replace", (u8*)pK, nK, (u8*)pV, nV);

  /* Save the position of any open cursors */
  rc = btSaveAllCursor(db, 0);
  assert( rc!=SQLITE4_NOTFOUND && rc!=SQLITE4_INEXACT );
  btCheckPageRefs(db);

  /* Seek stack cursor csr to the b-tree page that key pK/nK is/would be
  ** stored on.  */

  if( rc==SQLITE4_OK ){
    BtDbHdr *pHdr = sqlite4BtPagerDbhdr(db->pPager);
    u32 iRoot = 0;
    if( !db->bFastInsertOp ){

      iRoot = pHdr->iRoot;
    }
    if( rc==SQLITE4_OK ){
      rc = btReplaceEntry(db, iRoot, pK, nK, pV, nV);
    }
  }

................................................................................
    }
    if( rc==SQLITE4_OK ){
      rc = btBalanceIfUnderfull(pCsr);
    }

    btCsrReleaseAll(pCsr);
  }else{

    rc = btErrorBkpt(SQLITE4_MISUSE);
  }
  return rc;
}

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







>




|







 







>







 







>

<
>
>
>
>
>
>
>
>







 







|


>
>
|
>
>
>
>
>
>
>







 







|




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

|

<





>
>
>
>
>
>
|
|
|
<
>







 







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



>

>

>
>
>
>
>



<

<
<
<


<
>

>







 







<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<







 







<







 







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







 








|
|
|
<
<
|
|
|
|
|
|
|
|
|

|
|
|
|

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












|
<
<
<
<
<
|

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







 







<
<
<
<
<







 







|


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







 







|











<



|







 







|
|
>

<


>







 







>







24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
..
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
..
71
72
73
74
75
76
77
78
79

80
81
82
83
84
85
86
87
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
...
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267

268
269
270
271
272
273
274
275
276
277
278
279
280
281

282
283
284
285
286
287
288
289
...
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333

334



335
336

337
338
339
340
341
342
343
344
345
346
...
702
703
704
705
706
707
708

































































































709
710
711
712
713
714
715
...
723
724
725
726
727
728
729

730
731
732
733
734
735
736
...
793
794
795
796
797
798
799
800
801
802
803
804
805
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
846
847
848
849
850
851
852
853
854
855
856
857
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
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
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
....
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
1301
1302
1303
1304
1305
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
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
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
1398
1399
1400
1401
1402
1403
1404
1405
....
1618
1619
1620
1621
1622
1623
1624





1625
1626
1627
1628
1629
1630
1631
....
2698
2699
2700
2701
2702
2703
2704
2705
2706
2707
2708
2709
2710
2711
2712
2713
2714
2715
2716
2717
2718
2719
2720
2721
2722
2723
2724
2725
2726
2727
2728
2729
....
2884
2885
2886
2887
2888
2889
2890
2891
2892
2893
2894
2895
2896
2897
2898
2899
2900
2901
2902

2903
2904
2905
2906
2907
2908
2909
2910
2911
2912
2913
....
2927
2928
2929
2930
2931
2932
2933
2934
2935
2936
2937

2938
2939
2940
2941
2942
2943
2944
2945
2946
2947
....
2972
2973
2974
2975
2976
2977
2978
2979
2980
2981
2982
2983
2984
2985
2986
** b-tree pages. 
*/
#define BT_PGFLAGS_INTERNAL 0x01  /* True for non-leaf nodes */

/* #define BT_STDERR_DEBUG 1 */

typedef struct BtCursor BtCursor;
typedef struct FiCursor FiCursor;

struct bt_db {
  sqlite4_env *pEnv;              /* SQLite environment */
  BtPager *pPager;                /* Underlying page-based database */
  bt_cursor *pAllCsr;             /* List of all open cursors */
  int bFastInsertOp;              /* Set by CONTROL_FAST_INSERT_OP */
};

typedef struct BtOvfl BtOvfl;
struct BtOvfl {
  int nKey;
  int nVal;
................................................................................
/* 
** Base class for both cursor types (BtCursor and FiCursor).
*/
struct bt_cursor {
  int eType;                      /* Cursor type */
  void *pExtra;                   /* Extra allocated space */
  bt_db *pDb;                     /* Database this cursor belongs to */
  bt_cursor *pNextCsr;            /* Next cursor opened by same db handle */
};

/*
** Database b-tree cursor handle.
*/
struct BtCursor {
  bt_cursor base;                 /* Base cursor class */
................................................................................
  int aiCell[BT_MAX_DEPTH];       /* Current cell of each apPage[] entry */
  BtPage *apPage[BT_MAX_DEPTH];   /* All pages from root to current leaf */
  BtOvfl ovfl;                    /* Overflow cache (see above) */

  int bRequireReseek;             /* True if a btCsrReseek() is required */
  int bSkipNext;                  /* True if next CsrNext() is a no-op */
  int bSkipPrev;                  /* True if next CsrPrev() is a no-op */
};


/*
** Database f-tree cursor handle.
*/
struct FiCursor {
  bt_cursor base;                 /* Base cursor class */
  int iBt;                        /* Current sub-tree (or -1 for EOF) */
  int nBt;                        /* Number of entries in aBt[] array */
  BtCursor *aBt;                  /* Array of sub-tree cursors */
};

#ifndef btErrorBkpt
int btErrorBkpt(int rc){
  static int error_cnt = 0;
  error_cnt++;
  return rc;
................................................................................
}
#endif

#if !defined(NDEBUG) 
static void btCheckPageRefs(bt_db *pDb){
  int nActual = 0;                /* Outstanding refs according to pager */
  int nExpect = 0;                /* According to the set of open cursors */
  bt_cursor *pCsr;                /* Iterator variable */

  for(pCsr=pDb->pAllCsr; pCsr; pCsr=pCsr->pNextCsr){
    if( pCsr->eType==CSR_TYPE_BT ){
      BtCursor *p = (BtCursor*)pCsr;
      if( p->nPg>0 ) nExpect += p->nPg;
    }else{
      FiCursor *p = (FiCursor*)pCsr;
      int i;
      for(i=0; i<p->nBt; i++){
        if( p->aBt[i].nPg>0 ) nExpect += p->aBt[i].nPg;
      }
    }
  }
  nActual = sqlite4BtPagerRefcount(pDb->pPager);
  assert( nActual==nExpect );
}
#else
# define btCheckPageRefs(x) 
#endif
................................................................................
  pCsr->base.pDb = db;
  pCsr->iRoot = iRoot;
  sqlite4_env_config(db->pEnv, SQLITE4_ENVCONFIG_GETMM, &pCsr->ovfl.buf.pMM);
}

int sqlite4BtCsrOpen(bt_db *db, int nExtra, bt_cursor **ppCsr){
  int rc = SQLITE4_OK;            /* Return Code */
  bt_cursor *pRet = 0;

  assert( sqlite4BtPagerTransactionLevel(db->pPager)>0 );

  if( db->bFastInsertOp ){
    int nByte = sizeof(FiCursor) + nExtra;
    FiCursor *pCsr;

    pCsr = (FiCursor*)sqlite4_malloc(db->pEnv, nByte);
    if( pCsr==0 ){
      rc = btErrorBkpt(SQLITE4_NOMEM);
    }else{
      memset(pCsr, 0, nByte);
      pCsr->base.eType = CSR_TYPE_FAST;
      pCsr->base.pExtra = (void*)&pCsr[1];
      pCsr->base.pDb = db;
      pRet = (bt_cursor*)pCsr;
    }

  }else{
    BtCursor *pCsr;                /* New cursor object */
    int nByte = sizeof(BtCursor) + nExtra;
    pCsr = (BtCursor*)sqlite4_malloc(db->pEnv, nByte);

    if( pCsr==0 ){
      rc = btErrorBkpt(SQLITE4_NOMEM);
    }else{
      u32 iRoot = sqlite4BtPagerDbhdr(db->pPager)->iRoot;
      btCsrSetup(db, iRoot, pCsr);
      pRet = (bt_cursor*)pCsr;
    }
  }

  assert( (pRet==0)==(rc!=SQLITE4_OK) );
  if( rc==SQLITE4_OK ){
    pRet->pNextCsr = db->pAllCsr;
    db->pAllCsr = pRet;
  }

  *ppCsr = pRet;

  btCheckPageRefs(db);
  db->bFastInsertOp = 0;
  return rc;
}

static void btCsrReleaseAll(BtCursor *pCsr){
................................................................................
  if( bFreeBuffer ){
    sqlite4_buffer_clear(&pCsr->ovfl.buf);
  }
  pCsr->bSkipNext = 0;
  pCsr->bSkipPrev = 0;
  pCsr->bRequireReseek = 0;
}

static void fiCsrReset(FiCursor *pCsr){
  int i;
  bt_db *db = pCsr->base.pDb;
  for(i=0; i<pCsr->nBt; i++){
    btCsrReset(&pCsr->aBt[i], 1);
  }
  sqlite4_free(db->pEnv, pCsr->aBt);
  pCsr->aBt = 0;
  pCsr->nBt = 0;
  pCsr->iBt = -1;
}

int sqlite4BtCsrClose(bt_cursor *pCsr){
  if( pCsr ){
    bt_cursor **pp;
    bt_db *pDb = pCsr->pDb;

    btCheckPageRefs(pDb);

    /* Remove this cursor from the all-cursors list. */
    for(pp=&pDb->pAllCsr; *pp!=pCsr; pp=&(*pp)->pNextCsr);
    *pp = pCsr->pNextCsr;

    if( pCsr->eType==CSR_TYPE_BT ){
      /* A regular b-tree cursor */
      BtCursor *p = (BtCursor*)pCsr;

      btCsrReset(p, 1);



    }else{
      /* A fast-insert-tree cursor */

      fiCsrReset((FiCursor*)pCsr);
    }
    sqlite4_free(pDb->pEnv, pCsr);
    btCheckPageRefs(pDb);
  }
  return SQLITE4_OK;
}

void *sqlite4BtCsrExtra(bt_cursor *pCsr){
  return pCsr->pExtra;
................................................................................

  if( rc!=SQLITE4_OK && rc!=SQLITE4_INEXACT && eCsrseek!=BT_CSRSEEK_UPDATE ){
    btCsrReset(pCsr, 0);
  }
  return rc;
}


































































































static int btCsrReseek(BtCursor *pCsr){
  int rc = SQLITE4_OK;
  if( pCsr->bRequireReseek ){
    BtOvfl ovfl;
    memcpy(&ovfl, &pCsr->ovfl, sizeof(BtOvfl));

    pCsr->ovfl.buf.n = 0;
................................................................................
      pCsr->ovfl.buf.p = ovfl.buf.p;
    }else{
      sqlite4_buffer_clear(&ovfl.buf);
    }
  }
  return rc;
}


/*
** This function does the work of both sqlite4BtCsrNext() (if parameter
** bNext is true) and Pref() (if bNext is false).
*/
static int btCsrStep(BtCursor *pCsr, int bNext){
  const int pgsz = sqlite4BtPagerPagesize(pCsr->base.pDb->pPager);
................................................................................
      }
    }
  }

  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(BtCursor *pCsr, int bLast){
  const int pgsz = sqlite4BtPagerPagesize(pCsr->base.pDb->pPager);
  int rc = SQLITE4_OK;            /* Return Code */
  u32 pgno;                       /* Page number for next page to load */

  /* Reset the cursor */
  btCsrReset(pCsr, 0);

  /* Figure out the root page number */
  assert( pCsr->iRoot>1 && pCsr->nPg==0 );
  pgno = pCsr->iRoot;

  while( rc==SQLITE4_OK ){
    /* Load page number pgno into the b-tree */
    rc = btCsrDescend(pCsr, pgno);
    if( rc==SQLITE4_OK ){
      int nCell;                  /* Number of cells on this page */
      int nByte;
      u8 *pCell;
      u8 *aData = (u8*)sqlite4BtPageData(pCsr->apPage[pCsr->nPg-1]);

      nCell = btCellCount(aData, pgsz);
      if( nCell==0 ){
        btCsrReset(pCsr, 0);
        return SQLITE4_NOTFOUND;
      }

      /* If the cursor has descended to a leaf break out of the loop. */
      pCsr->aiCell[pCsr->nPg-1] = (bLast ? nCell : 0);
      if( (aData[0] & BT_PGFLAGS_INTERNAL)==0 ) break;
      
      /* Otherwise, set pgno to the left or rightmost child of the page
      ** just loaded, depending on whether the cursor is seeking to the
      ** start or end of the tree.  */
      if( bLast==0 ){
        pCell = btCellFind(aData, pgsz, 0);
        pCell += sqlite4BtVarintGet32(pCell, &nByte);
        pCell += nByte;
        sqlite4BtVarintGet32(pCell, (int *)&pgno);
      }else{
        pgno = btGetU32(&aData[1]);
      }
    }
  }
  if( pCsr->aiCell[pCsr->nPg-1] ) pCsr->aiCell[pCsr->nPg-1]--;
  return rc;
}


static int fiCsrAllocateSubs(bt_db *db, FiCursor *pCsr, int nBt){
  int rc = SQLITE4_OK;            /* Return code */
  BtCursor *aNew;                 /* Allocated array */
  int nByte;                      /* Bytes of space to allocate */

  assert( pCsr->nBt==0 && nBt>0 );
  nByte = sizeof(BtCursor) * nBt;
  aNew = (BtCursor*)sqlite4_malloc(db->pEnv, nByte);
  if( aNew ){
    memset(aNew, 0, nByte);
    pCsr->aBt = aNew;
    pCsr->nBt = nBt;
  }else{
    rc = btErrorBkpt(SQLITE4_NOMEM);
  }

  return rc;
}

static u32 btBlockToRoot(BtDbHdr *pHdr, u32 iBlk){
  assert( iBlk>0 );
  return (iBlk - 1) * (pHdr->blksz / pHdr->pgsz) + 1;
}

/*
** Seek a fast-insert cursor.
*/
static int fiCsrSeek(FiCursor *pCsr, const void *pK, int nK, int eSeek){
  int rc = SQLITE4_OK;            /* 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 ){
    if( eSeek==BT_SEEK_EQ ){
      /* A BT_SEEK_EQ is a special case. There is no need to set up a cursor
      ** that can be advanced (in either direction) in this case. All that
      ** is required is to search each level in order for the requested key 
      ** (or a corresponding delete marker). Once a match is found, there
      ** is no need to search any further.  */
      rc = fiCsrAllocateSubs(db, pCsr, 1);

      if( rc==SQLITE4_OK ){
        BtCursor mcsr;            /* Used to iterate through the meta-tree */
        BtCursor *pSub = pCsr->aBt;

        /* Loop through the set of f-tree levels */
        btCsrSetup(db, pHdr->iMRoot, &mcsr);
        for(rc=btCsrEnd(&mcsr, 0); rc==SQLITE4_OK; rc=btCsrStep(&mcsr, 1)){
          const void *pV; int nV; /* Value associated with meta-tree entry */
          u32 iBlk;               /* Block containing sub-tree */

          sqlite4BtCsrData(&mcsr.base, 0, 4, &pV, &nV);
          iBlk = sqlite4BtGetU32((const u8*)pV);
          btCsrReset(pSub, 1);
          btCsrSetup(db, btBlockToRoot(pHdr, iBlk), pSub);
          rc = btCsrSeek(pSub, pK, nK, BT_SEEK_EQ, BT_CSRSEEK_SEEK);
          if( rc!=SQLITE4_NOTFOUND && rc!=SQLITE4_INEXACT ){
            /* 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. */
            if( rc==SQLITE4_OK ) pCsr->iBt = 0;
            break;
          }
        }
        btCsrReset(&mcsr, 1);
      }
    }else{
      /* Deal with this later... */
      assert( 0 );
    }
  }else{
    rc = SQLITE4_NOTFOUND;
  }

  return rc;
}

int sqlite4BtCsrSeek(
  bt_cursor *pBase, 
  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 rc;
  btCheckPageRefs(pBase->pDb);
  if( pBase->eType==CSR_TYPE_BT ){
    BtCursor *pCsr = (BtCursor*)pBase;
    rc = btCsrSeek(pCsr, pK, nK, eSeek, BT_CSRSEEK_SEEK);
  }else{
    rc = fiCsrSeek((FiCursor*)pBase, pK, nK, eSeek);
  }
  btCheckPageRefs(pBase->pDb);
  return rc;
}

/*
** Position cursor pCsr to point to the smallest key in the database.
*/
int sqlite4BtCsrFirst(bt_cursor *pCsr){
  int rc;
  if( pCsr->eType==CSR_TYPE_BT ){
    rc = btCsrEnd((BtCursor*)pCsr, 0);
  }else{
    assert( 0 );
  }
  return rc;
}

/*
** Position cursor pCsr to point to the largest key in the database.
*/
int sqlite4BtCsrLast(bt_cursor *pCsr){
  int rc;
  if( pCsr->eType==CSR_TYPE_BT ){
    rc = btCsrEnd((BtCursor*)pCsr, 1);
  }else{
    assert( 0 );
  }
  return rc;
}


/*
** Advance to the next entry in the tree.
*/
int sqlite4BtCsrNext(bt_cursor *pCsr){
  int rc;
  if( pCsr->eType==CSR_TYPE_BT ){
................................................................................
      u32 rootpgno = btGetU32(&pOvfl[1 + nDirect*4]);
      rc = btOverflowTrimtree(pgsz, pPager, rootpgno, nDepth);
    }
  }

  return rc;
}

static int btCsrKey(BtCursor *pCsr, const void **ppK, int *pnK){
  int rc = SQLITE4_OK;



  if( pCsr->bRequireReseek ){
    *ppK = (const void*)pCsr->ovfl.buf.p;
    *pnK = pCsr->ovfl.nKey;
  }else{
    const int pgsz = sqlite4BtPagerPagesize(pCsr->base.pDb->pPager);
    u8 *aData;
    u8 *pCell;
    int nK;
    int iCell = pCsr->aiCell[pCsr->nPg-1];

    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 ){
      /* type (c) leaf cell */
      rc = btCsrBuffer(pCsr, 0);
      if( rc==SQLITE4_OK ){
        *ppK = pCsr->ovfl.buf.p;
        *pnK = pCsr->ovfl.nKey;
      }
    }else{
      *ppK = pCell;
      *pnK = nK;
    }
  }

  return rc;
}

static int btCsrData(
  BtCursor *pCsr,                 /* Cursor handle */
  int iOffset,                    /* Offset of requested data */
  int nByte,                      /* Bytes requested (or -ve for all avail.) */
  const void **ppV,               /* OUT: Pointer to data buffer */
  int *pnV                        /* OUT: Size of data buffer in bytes */
){
  const int pgsz = sqlite4BtPagerPagesize(pCsr->base.pDb->pPager);
  int rc;
  u8 *aData;
  u8 *pCell;
  int nK = 0;
  int nV = 0;

  rc = btCsrReseek(pCsr);
  if( rc==SQLITE4_OK ){
    if( pCsr->bSkipNext || pCsr->bSkipPrev ){
      /* The row has been deleted out from under this cursor. So return
       ** NULL for data.  */
      *ppV = 0;
      *pnV = 0;
    }else{
      int iCell = pCsr->aiCell[pCsr->nPg-1];

      aData = (u8*)sqlite4BtPageData(pCsr->apPage[pCsr->nPg-1]);
      pCell = btCellFind(aData, pgsz, iCell);
      pCell += sqlite4BtVarintGet32(pCell, &nK);
      if( nK>0 ){
        pCell += nK;
        pCell += sqlite4BtVarintGet32(pCell, &nV);
      }

      if( nV==0 ){
        rc = btCsrBuffer(pCsr, 1);
        if( rc==SQLITE4_OK ){
          u8 *aBuf = (u8*)pCsr->ovfl.buf.p;
          *ppV = &aBuf[pCsr->ovfl.nKey];
          *pnV = pCsr->ovfl.nVal;
        }
      }else{
        *ppV = pCell;
        *pnV = (nV-1);
      }

#ifndef NDEBUG
      if( rc==SQLITE4_OK ){
        const void *pK; int nK;
        rc = sqlite4BtCsrKey((bt_cursor*)pCsr, &pK, &nK);
        if( rc==SQLITE4_OK ){
          BtLock *pLock = (BtLock*)pCsr->base.pDb->pPager;
          sqlite4BtDebugKV(pLock, "select", (u8*)pK, nK, (u8*)*ppV, *pnV);
        }
      }
#endif
    }
  }

  return rc;
}

int sqlite4BtCsrKey(bt_cursor *pBase, const void **ppK, int *pnK){
  int rc = SQLITE4_OK;            /* Return code */
  
  if( pBase->eType==CSR_TYPE_BT ){
    rc = btCsrKey((BtCursor*)pBase, ppK, pnK);
  }else{
    FiCursor *pCsr = (FiCursor*)pBase;
    assert( pCsr->iBt>=0 );
    rc = btCsrKey(&pCsr->aBt[pCsr->iBt], ppK, pnK);
  }

  return rc;
}

int sqlite4BtCsrData(
  bt_cursor *pBase,               /* Cursor handle */
  int iOffset,                    /* Offset of requested data */
  int nByte,                      /* Bytes requested (or -ve for all avail.) */
  const void **ppV,               /* OUT: Pointer to data buffer */
  int *pnV                        /* OUT: Size of data buffer in bytes */
){
  int rc = SQLITE4_OK;            /* Return code */





  
  if( pBase->eType==CSR_TYPE_BT ){










    rc = btCsrData((BtCursor*)pBase, iOffset, nByte, ppV, pnV);
  }else{


































    FiCursor *pCsr = (FiCursor*)pBase;
    assert( pCsr->iBt>=0 );
    rc = btCsrData(&pCsr->aBt[pCsr->iBt], iOffset, nByte, ppV, pnV);
  }

  return rc;
}

/*
** The argument points to a buffer containing an overflow array. Return
................................................................................
  nPg = (nContent + pgsz - 1) / pgsz;
  if( nPg<=BT_MAX_DIRECT_OVERFLOW ){
    return 1 + nPg*4;
  }
  return 1 + (BT_MAX_DIRECT_OVERFLOW+1) * 4;
}






/*
** Allocate a non-overflow page.
**
** This function is a simple wrapper around sqlite4BtPageAllocate(),
** except that if the database is currenly in fast-insert mode the
** BtDbHdr.nSubPg counter is incremented.
*/
................................................................................
    rc = btBalance(pCsr, bLeaf, 0, 0);
  }
  return rc;
}

static int btSaveAllCursor(bt_db *pDb, BtCursor *pCsr){
  int rc = SQLITE4_OK;            /* Return code */
  bt_cursor *p;                   /* Used to iterate through cursors */

  for(p=pDb->pAllCsr; rc==SQLITE4_OK && p; p=p->pNextCsr){
    if( p->eType==CSR_TYPE_BT ){
      BtCursor *pCsr = (BtCursor*)p;
      if( pCsr->nPg>0 ){
        assert( pCsr->bRequireReseek==0 );
        rc = btCsrBuffer(pCsr, 0);
        if( rc==SQLITE4_OK ){
          assert( pCsr->ovfl.buf.p );
          pCsr->bRequireReseek = 1;
          if( pCsr!=pCsr ) btCsrReleaseAll(pCsr);
        }
      }
    }else{
      /* ?? */
    }

  }

  return rc;
}

static int btFastInsertRoot(bt_db *db, BtDbHdr *pHdr, u32 *piRoot);

................................................................................
    rc = btFindNextLevel(db, pHdr, &iLevel);
    if( rc==SQLITE4_OK ){
      rc = btAllocateBlock(db, &iSubBlock);
    }

    if( rc==SQLITE4_OK ){
      u8 aKey[8];
      u8 aVal[4];
      pHdr->iSubBlock = iSubBlock;
      pHdr->nSubPg = 1;           /* Root page is automatically allocated */

      /* The key for the new entry consists of the concatentation of two 
      ** 32-bit big-endian integers - the <age> and <level-no>. The age
      ** of the new segment is 0. The level number is one greater than the
      ** level number of the previous segment.  */
      btPutU32(&aKey[0], 0);
      btPutU32(&aKey[4], ~iLevel);

      btPutU32(&aVal[0], iSubBlock);


      assert( db->bFastInsertOp==1 );
      db->bFastInsertOp = 0;
      rc = btReplaceEntry(db, pHdr->iMRoot, aKey, 8, aVal, 4);
      db->bFastInsertOp = 1;
    }
  }

  if( rc==SQLITE4_OK ){
    *piRoot = btBlockToRoot(pHdr, pHdr->iSubBlock);
  }
................................................................................
  sqlite4BtDebugKV((BtLock*)db->pPager, "replace", (u8*)pK, nK, (u8*)pV, nV);

  /* Save the position of any open cursors */
  rc = btSaveAllCursor(db, 0);
  assert( rc!=SQLITE4_NOTFOUND && rc!=SQLITE4_INEXACT );
  btCheckPageRefs(db);

  /* Call btReplaceEntry() to update either the main b-tree or the top-level
  ** sub-tree. Pass iRoot=0 to update the sub-tree, or the root page number
  ** of the b-tree to update the b-tree.  */
  if( rc==SQLITE4_OK ){

    u32 iRoot = 0;
    if( !db->bFastInsertOp ){
      BtDbHdr *pHdr = sqlite4BtPagerDbhdr(db->pPager);
      iRoot = pHdr->iRoot;
    }
    if( rc==SQLITE4_OK ){
      rc = btReplaceEntry(db, iRoot, pK, nK, pV, nV);
    }
  }

................................................................................
    }
    if( rc==SQLITE4_OK ){
      rc = btBalanceIfUnderfull(pCsr);
    }

    btCsrReleaseAll(pCsr);
  }else{
    /* Fast-insert cursors do not support BtDelete(). */
    rc = btErrorBkpt(SQLITE4_MISUSE);
  }
  return rc;
}

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