/ Check-in [a200e1ea]
Login

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

Overview
Comment:Add the BtCursor.pPage field which is the current page to which the cursor points, for a very small performance gain.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | btree-current-page-cache
Files: files | file ages | folders
SHA1: a200e1eae9a1350ed2aed9bfe70042fec05dd98b
User & Date: drh 2015-04-15 19:13:26
Context
2015-04-15
19:13
Add the BtCursor.pPage field which is the current page to which the cursor points, for a very small performance gain. Leaf check-in: a200e1ea user: drh tags: btree-current-page-cache
17:26
Prevent the fetchPayload() routine from reporting a cell size that extends off the end of the page on a pathologically corrupted database file. check-in: f71053cf user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/btree.c.

583
584
585
586
587
588
589

590
591
592
593
594
595
596
....
3647
3648
3649
3650
3651
3652
3653

3654
3655
3656
3657
3658
3659
3660
....
3861
3862
3863
3864
3865
3866
3867

3868
3869
3870
3871
3872
3873
3874
....
3962
3963
3964
3965
3966
3967
3968

3969
3970
3971
3972
3973
3974
3975
3976
3977
3978
3979

3980
3981
3982
3983
3984
3985
3986
3987
3988
3989
3990

3991
3992
3993
3994
3995
3996
3997
3998
....
4039
4040
4041
4042
4043
4044
4045

4046
4047
4048
4049
4050
4051
4052
4053
....
4193
4194
4195
4196
4197
4198
4199
4200
4201
4202
4203
4204
4205
4206
4207

4208
4209
4210
4211
4212
4213
4214
....
4390
4391
4392
4393
4394
4395
4396
4397


4398
4399
4400
4401
4402
4403
4404
4405
....
4417
4418
4419
4420
4421
4422
4423
4424


4425
4426
4427
4428
4429
4430
4431
4432
....
4448
4449
4450
4451
4452
4453
4454


4455

4456
4457
4458
4459
4460
4461
4462
4463
4464
4465
4466
4467
4468
4469
4470
....
4510
4511
4512
4513
4514
4515
4516
4517
4518
4519
4520
4521
4522
4523
4524
....
4556
4557
4558
4559
4560
4561
4562

4563
4564
4565
4566
4567
4568
4569
4570
4571
4572

4573
4574
4575
4576
4577
4578
4579
....
4621
4622
4623
4624
4625
4626
4627

4628
4629
4630
4631
4632
4633
4634
4635
....
4671
4672
4673
4674
4675
4676
4677
4678
4679
4680
4681
4682
4683
4684
4685
....
4696
4697
4698
4699
4700
4701
4702
4703
4704
4705
4706
4707
4708
4709
4710
....
4719
4720
4721
4722
4723
4724
4725

4726
4727
4728
4729
4730
4731
4732
4733
4734
4735
4736
4737
....
4750
4751
4752
4753
4754
4755
4756

4757
4758
4759
4760
4761
4762
4763
4764
4765
....
4849
4850
4851
4852
4853
4854
4855
4856
4857

4858
4859
4860
4861
4862
4863
4864
4865
4866
4867
4868
4869
4870
4871
4872
4873
4874
4875
....
4984
4985
4986
4987
4988
4989
4990
4991
4992
4993
4994
4995
4996
4997
4998
....
5072
5073
5074
5075
5076
5077
5078
5079
5080
5081
5082
5083
5084
5085
5086
....
5096
5097
5098
5099
5100
5101
5102
5103
5104
5105
5106
5107
5108
5109
5110
....
5120
5121
5122
5123
5124
5125
5126
5127
5128
5129
5130
5131
5132
5133
5134
....
5183
5184
5185
5186
5187
5188
5189

5190
5191
5192
5193
5194
5195
5196
5197
....
5203
5204
5205
5206
5207
5208
5209
5210

5211
5212
5213
5214
5215
5216
5217
....
5222
5223
5224
5225
5226
5227
5228
5229
5230
5231
5232
5233
5234
5235
5236
....
7415
7416
7417
7418
7419
7420
7421
7422

7423
7424
7425
7426
7427
7428
7429
....
7430
7431
7432
7433
7434
7435
7436
7437

7438
7439
7440
7441
7442
7443
7444
....
7509
7510
7511
7512
7513
7514
7515

7516
7517
7518
7519
7520
7521
7522
....
7611
7612
7613
7614
7615
7616
7617

7618
7619
7620
7621
7622
7623
7624
7625
....
7678
7679
7680
7681
7682
7683
7684

7685
7686
7687
7688

7689
7690
7691
7692
7693
7694
7695
....
7707
7708
7709
7710
7711
7712
7713

7714
7715
7716
7717
7718
7719
7720
7721
7722
....
7758
7759
7760
7761
7762
7763
7764
7765
7766
7767
7768
7769
7770
7771
7772
....
7794
7795
7796
7797
7798
7799
7800

7801
7802
7803
7804
7805
7806
7807
....
8298
8299
8300
8301
8302
8303
8304

8305
8306
8307
8308
8309
8310
8311
8312
....
8321
8322
8323
8324
8325
8326
8327
8328
8329
8330

8331
8332
8333
8334
8335
8336
8337
8338
....
9107
9108
9109
9110
9111
9112
9113

9114
9115
9116
9117
9118
9119
9120
static void btreeReleaseAllCursorPages(BtCursor *pCur){
  int i;
  for(i=0; i<=pCur->iPage; i++){
    releasePage(pCur->apPage[i]);
    pCur->apPage[i] = 0;
  }
  pCur->iPage = -1;

}


/*
** Save the current cursor position in the variables BtCursor.nKey 
** and BtCursor.pKey. The cursor's state is set to CURSOR_REQUIRESEEK.
**
................................................................................
        p->eState = CURSOR_FAULT;
        p->skipNext = errCode;
      }
      for(i=0; i<=p->iPage; i++){
        releasePage(p->apPage[i]);
        p->apPage[i] = 0;
      }

    }
    sqlite3BtreeLeave(pBtree);
  }
  return rc;
}

/*
................................................................................
    iTable = 0;
  }

  /* Now that no other errors can occur, finish filling in the BtCursor
  ** variables and link the cursor into the BtShared list.  */
  pCur->pgnoRoot = (Pgno)iTable;
  pCur->iPage = -1;

  pCur->pKeyInfo = pKeyInfo;
  pCur->pBtree = p;
  pCur->pBt = pBt;
  assert( wrFlag==0 || wrFlag==BTCF_WriteFlag );
  pCur->curFlags = wrFlag;
  pCur->pNext = pBt->pCursor;
  if( pCur->pNext ){
................................................................................
** for MSVC and a macro for everything else.  Ticket #2457.
*/
#ifndef NDEBUG
  static void assertCellInfo(BtCursor *pCur){
    CellInfo info;
    int iPage = pCur->iPage;
    memset(&info, 0, sizeof(info));

    btreeParseCell(pCur->apPage[iPage], pCur->aiIdx[iPage], &info);
    assert( CORRUPT_DB || memcmp(&info, &pCur->info, sizeof(info))==0 );
  }
#else
  #define assertCellInfo(x)
#endif
#ifdef _MSC_VER
  /* Use a real function in MSVC to work around bugs in that compiler. */
  static void getCellInfo(BtCursor *pCur){
    if( pCur->info.nSize==0 ){
      int iPage = pCur->iPage;

      btreeParseCell(pCur->apPage[iPage],pCur->aiIdx[iPage],&pCur->info);
      pCur->curFlags |= BTCF_ValidNKey;
    }else{
      assertCellInfo(pCur);
    }
  }
#else /* if not _MSC_VER */
  /* Use a macro in all other compilers so that the function is inlined */
#define getCellInfo(pCur)                                                      \
  if( pCur->info.nSize==0 ){                                                   \
    int iPage = pCur->iPage;                                                   \

    btreeParseCell(pCur->apPage[iPage],pCur->aiIdx[iPage],&pCur->info);        \
    pCur->curFlags |= BTCF_ValidNKey;                                          \
  }else{                                                                       \
    assertCellInfo(pCur);                                                      \
  }
#endif /* _MSC_VER */

#ifndef NDEBUG  /* The next routine used only within assert() statements */
................................................................................
** to return an integer result code for historical reasons.
*/
int sqlite3BtreeDataSize(BtCursor *pCur, u32 *pSize){
  assert( cursorHoldsMutex(pCur) );
  assert( pCur->eState==CURSOR_VALID );
  assert( pCur->iPage>=0 );
  assert( pCur->iPage<BTCURSOR_MAX_DEPTH );

  assert( pCur->apPage[pCur->iPage]->intKeyLeaf==1 );
  getCellInfo(pCur);
  *pSize = pCur->info.nPayload;
  return SQLITE_OK;
}

/*
** Given the page number of an overflow page in the database (parameter
................................................................................
  u32 amt,             /* Read this many bytes */
  unsigned char *pBuf, /* Write the bytes into this buffer */ 
  int eOp              /* zero to read. non-zero to write. */
){
  unsigned char *aPayload;
  int rc = SQLITE_OK;
  int iIdx = 0;
  MemPage *pPage = pCur->apPage[pCur->iPage]; /* Btree page of current entry */
  BtShared *pBt = pCur->pBt;                  /* Btree this cursor belongs to */
#ifdef SQLITE_DIRECT_OVERFLOW_READ
  unsigned char * const pBufStart = pBuf;
  int bEnd;                                 /* True if reading to end of data */
#endif

  assert( pPage );

  assert( pCur->eState==CURSOR_VALID );
  assert( pCur->aiIdx[pCur->iPage]<pPage->nCell );
  assert( cursorHoldsMutex(pCur) );
  assert( eOp!=2 || offset==0 );    /* Always start from beginning for eOp==2 */

  getCellInfo(pCur);
  aPayload = pCur->info.pPayload;
................................................................................
** Return SQLITE_OK on success or an error code if anything goes
** wrong.  An error is returned if "offset+amt" is larger than
** the available payload.
*/
int sqlite3BtreeKey(BtCursor *pCur, u32 offset, u32 amt, void *pBuf){
  assert( cursorHoldsMutex(pCur) );
  assert( pCur->eState==CURSOR_VALID );
  assert( pCur->iPage>=0 && pCur->apPage[pCur->iPage] );


  assert( pCur->aiIdx[pCur->iPage]<pCur->apPage[pCur->iPage]->nCell );
  return accessPayload(pCur, offset, amt, (unsigned char*)pBuf, 0);
}

/*
** Read part of the data associated with cursor pCur.  Exactly
** "amt" bytes will be transfered into pBuf[].  The transfer
** begins at "offset".
................................................................................
  }
#endif

  assert( cursorHoldsMutex(pCur) );
  rc = restoreCursorPosition(pCur);
  if( rc==SQLITE_OK ){
    assert( pCur->eState==CURSOR_VALID );
    assert( pCur->iPage>=0 && pCur->apPage[pCur->iPage] );


    assert( pCur->aiIdx[pCur->iPage]<pCur->apPage[pCur->iPage]->nCell );
    rc = accessPayload(pCur, offset, amt, pBuf, 0);
  }
  return rc;
}

/*
** Return a pointer to payload information from the entry that the 
................................................................................
** any btree routine is called.
*/
static const void *fetchPayload(
  BtCursor *pCur,      /* Cursor pointing to entry to read from */
  u32 *pAmt            /* Write the number of available bytes here */
){
  u32 amt;


  assert( pCur!=0 && pCur->iPage>=0 && pCur->apPage[pCur->iPage]);

  assert( pCur->eState==CURSOR_VALID );
  assert( sqlite3_mutex_held(pCur->pBtree->db->mutex) );
  assert( cursorHoldsMutex(pCur) );
  assert( pCur->aiIdx[pCur->iPage]<pCur->apPage[pCur->iPage]->nCell );
  assert( pCur->info.nSize>0 );
  assert( pCur->info.pPayload>pCur->apPage[pCur->iPage]->aData || CORRUPT_DB );
  assert( pCur->info.pPayload<pCur->apPage[pCur->iPage]->aDataEnd ||CORRUPT_DB);
  amt = (int)(pCur->apPage[pCur->iPage]->aDataEnd - pCur->info.pPayload);
  if( pCur->info.nLocal<amt ) amt = pCur->info.nLocal;
  *pAmt = amt;
  return (void*)pCur->info.pPayload;
}


/*
................................................................................
  assert( pCur->iPage>=0 );
  if( pCur->iPage>=(BTCURSOR_MAX_DEPTH-1) ){
    return SQLITE_CORRUPT_BKPT;
  }
  rc = getAndInitPage(pBt, newPgno, &pNewPage,
               (pCur->curFlags & BTCF_WriteFlag)==0 ? PAGER_GET_READONLY : 0);
  if( rc ) return rc;
  pCur->apPage[i+1] = pNewPage;
  pCur->aiIdx[i+1] = 0;
  pCur->iPage++;

  pCur->info.nSize = 0;
  pCur->curFlags &= ~(BTCF_ValidNKey|BTCF_ValidOvfl);
  if( pNewPage->nCell<1 || pNewPage->intKey!=pCur->apPage[i]->intKey ){
    return SQLITE_CORRUPT_BKPT;
................................................................................
** right-most child page then pCur->idx is set to one more than
** the largest cell index.
*/
static void moveToParent(BtCursor *pCur){
  assert( cursorHoldsMutex(pCur) );
  assert( pCur->eState==CURSOR_VALID );
  assert( pCur->iPage>0 );

  assert( pCur->apPage[pCur->iPage] );
  assertParentIndex(
    pCur->apPage[pCur->iPage-1], 
    pCur->aiIdx[pCur->iPage-1], 
    pCur->apPage[pCur->iPage]->pgno
  );
  testcase( pCur->aiIdx[pCur->iPage-1] > pCur->apPage[pCur->iPage-1]->nCell );

  releasePage(pCur->apPage[pCur->iPage]);
  pCur->iPage--;

  pCur->info.nSize = 0;
  pCur->curFlags &= ~(BTCF_ValidNKey|BTCF_ValidOvfl);
}

/*
** Move the cursor to point to the root page of its b-tree structure.
**
................................................................................
                 (pCur->curFlags & BTCF_WriteFlag)==0 ? PAGER_GET_READONLY : 0);
    if( rc!=SQLITE_OK ){
      pCur->eState = CURSOR_INVALID;
      return rc;
    }
    pCur->iPage = 0;
  }

  pRoot = pCur->apPage[0];
  assert( pRoot->pgno==pCur->pgnoRoot );

  /* If pCur->pKeyInfo is not NULL, then the caller that opened this cursor
  ** expected to open it on an index b-tree. Otherwise, if pKeyInfo is
  ** NULL, the caller expects a table b-tree. If this is not the case,
  ** return an SQLITE_CORRUPT error. 
  **
................................................................................
static int moveToLeftmost(BtCursor *pCur){
  Pgno pgno;
  int rc = SQLITE_OK;
  MemPage *pPage;

  assert( cursorHoldsMutex(pCur) );
  assert( pCur->eState==CURSOR_VALID );
  while( rc==SQLITE_OK && !(pPage = pCur->apPage[pCur->iPage])->leaf ){
    assert( pCur->aiIdx[pCur->iPage]<pPage->nCell );
    pgno = get4byte(findCell(pPage, pCur->aiIdx[pCur->iPage]));
    rc = moveToChild(pCur, pgno);
  }
  return rc;
}

................................................................................
static int moveToRightmost(BtCursor *pCur){
  Pgno pgno;
  int rc = SQLITE_OK;
  MemPage *pPage = 0;

  assert( cursorHoldsMutex(pCur) );
  assert( pCur->eState==CURSOR_VALID );
  while( !(pPage = pCur->apPage[pCur->iPage])->leaf ){
    pgno = get4byte(&pPage->aData[pPage->hdrOffset+8]);
    pCur->aiIdx[pCur->iPage] = pPage->nCell;
    rc = moveToChild(pCur, pgno);
    if( rc ) return rc;
  }
  pCur->aiIdx[pCur->iPage] = pPage->nCell-1;
  assert( pCur->info.nSize==0 );
................................................................................
int sqlite3BtreeFirst(BtCursor *pCur, int *pRes){
  int rc;

  assert( cursorHoldsMutex(pCur) );
  assert( sqlite3_mutex_held(pCur->pBtree->db->mutex) );
  rc = moveToRoot(pCur);
  if( rc==SQLITE_OK ){

    if( pCur->eState==CURSOR_INVALID ){
      assert( pCur->pgnoRoot==0 || pCur->apPage[pCur->iPage]->nCell==0 );
      *pRes = 1;
    }else{
      assert( pCur->apPage[pCur->iPage]->nCell>0 );
      *pRes = 0;
      rc = moveToLeftmost(pCur);
    }
  }
  return rc;
}

................................................................................
#ifdef SQLITE_DEBUG
    /* This block serves to assert() that the cursor really does point 
    ** to the last entry in the b-tree. */
    int ii;
    for(ii=0; ii<pCur->iPage; ii++){
      assert( pCur->aiIdx[ii]==pCur->apPage[ii]->nCell );
    }

    assert( pCur->aiIdx[pCur->iPage]==pCur->apPage[pCur->iPage]->nCell-1 );
    assert( pCur->apPage[pCur->iPage]->leaf );
#endif
    return SQLITE_OK;
  }

  rc = moveToRoot(pCur);
  if( rc==SQLITE_OK ){
    if( CURSOR_INVALID==pCur->eState ){
................................................................................
    xRecordCompare = 0; /* All keys are integers */
  }

  rc = moveToRoot(pCur);
  if( rc ){
    return rc;
  }
  assert( pCur->pgnoRoot==0 || pCur->apPage[pCur->iPage] );
  assert( pCur->pgnoRoot==0 || pCur->apPage[pCur->iPage]->isInit );

  assert( pCur->eState==CURSOR_INVALID || pCur->apPage[pCur->iPage]->nCell>0 );
  if( pCur->eState==CURSOR_INVALID ){
    *pRes = -1;
    assert( pCur->pgnoRoot==0 || pCur->apPage[pCur->iPage]->nCell==0 );
    return SQLITE_OK;
  }
  assert( pCur->apPage[0]->intKey || pIdxKey );
  for(;;){
    int lwr, upr, idx, c;
    Pgno chldPg;
    MemPage *pPage = pCur->apPage[pCur->iPage];
    u8 *pCell;                          /* Pointer to current cell in pPage */

    /* pPage->nCell must be greater than zero. If this is the root-page
    ** the cursor would have been INVALID above and this for(;;) loop
    ** not run. If this is not the root-page, then the moveToChild() routine
    ** would have already detected db corruption. Similarly, pPage must
    ** be the right kind (index or table) of b-tree page. Otherwise
................................................................................
        assert( lwr+upr>=0 );
        idx = (lwr+upr)>>1;  /* idx = (lwr+upr)/2 */
      }
    }
    assert( lwr==upr+1 || (pPage->intKey && !pPage->leaf) );
    assert( pPage->isInit );
    if( pPage->leaf ){
      assert( pCur->aiIdx[pCur->iPage]<pCur->apPage[pCur->iPage]->nCell );
      pCur->aiIdx[pCur->iPage] = (u16)idx;
      *pRes = c;
      rc = SQLITE_OK;
      goto moveto_finish;
    }
moveto_next_layer:
    if( lwr>=pPage->nCell ){
................................................................................
        pCur->skipNext = 0;
        return SQLITE_OK;
      }
      pCur->skipNext = 0;
    }
  }

  pPage = pCur->apPage[pCur->iPage];
  idx = ++pCur->aiIdx[pCur->iPage];
  assert( pPage->isInit );

  /* If the database file is corrupt, it is possible for the value of idx 
  ** to be invalid here. This can only occur if a second cursor modifies
  ** the page while cursor pCur is holding a reference to it. Which can
  ** only happen if the database is corrupt in such a way as to link the
................................................................................
    do{
      if( pCur->iPage==0 ){
        *pRes = 1;
        pCur->eState = CURSOR_INVALID;
        return SQLITE_OK;
      }
      moveToParent(pCur);
      pPage = pCur->apPage[pCur->iPage];
    }while( pCur->aiIdx[pCur->iPage]>=pPage->nCell );
    if( pPage->intKey ){
      return sqlite3BtreeNext(pCur, pRes);
    }else{
      return SQLITE_OK;
    }
  }
................................................................................
  assert( pRes!=0 );
  assert( *pRes==0 || *pRes==1 );
  assert( pCur->skipNext==0 || pCur->eState!=CURSOR_VALID );
  pCur->info.nSize = 0;
  pCur->curFlags &= ~(BTCF_ValidNKey|BTCF_ValidOvfl);
  *pRes = 0;
  if( pCur->eState!=CURSOR_VALID ) return btreeNext(pCur, pRes);
  pPage = pCur->apPage[pCur->iPage];
  if( (++pCur->aiIdx[pCur->iPage])>=pPage->nCell ){
    pCur->aiIdx[pCur->iPage]--;
    return btreeNext(pCur, pRes);
  }
  if( pPage->leaf ){
    return SQLITE_OK;
  }else{
................................................................................
        pCur->skipNext = 0;
        return SQLITE_OK;
      }
      pCur->skipNext = 0;
    }
  }


  pPage = pCur->apPage[pCur->iPage];
  assert( pPage->isInit );
  if( !pPage->leaf ){
    int idx = pCur->aiIdx[pCur->iPage];
    rc = moveToChild(pCur, get4byte(findCell(pPage, idx)));
    if( rc ) return rc;
    rc = moveToRightmost(pCur);
  }else{
................................................................................
      }
      moveToParent(pCur);
    }
    assert( pCur->info.nSize==0 );
    assert( (pCur->curFlags & (BTCF_ValidNKey|BTCF_ValidOvfl))==0 );

    pCur->aiIdx[pCur->iPage]--;
    pPage = pCur->apPage[pCur->iPage];

    if( pPage->intKey && !pPage->leaf ){
      rc = sqlite3BtreePrevious(pCur, pRes);
    }else{
      rc = SQLITE_OK;
    }
  }
  return rc;
................................................................................
  assert( *pRes==0 || *pRes==1 );
  assert( pCur->skipNext==0 || pCur->eState!=CURSOR_VALID );
  *pRes = 0;
  pCur->curFlags &= ~(BTCF_AtLast|BTCF_ValidOvfl|BTCF_ValidNKey);
  pCur->info.nSize = 0;
  if( pCur->eState!=CURSOR_VALID
   || pCur->aiIdx[pCur->iPage]==0
   || pCur->apPage[pCur->iPage]->leaf==0
  ){
    return btreePrevious(pCur, pRes);
  }
  pCur->aiIdx[pCur->iPage]--;
  return SQLITE_OK;
}

................................................................................
  u8 *pFree = 0;

  TESTONLY( int balance_quick_called = 0 );
  TESTONLY( int balance_deeper_called = 0 );

  do {
    int iPage = pCur->iPage;
    MemPage *pPage = pCur->apPage[iPage];


    if( iPage==0 ){
      if( pPage->nOverflow ){
        /* The root page of the b-tree is overfull. In this case call the
        ** balance_deeper() function to create a new child for the root-page
        ** and copy the current contents of the root-page to it. The
        ** next iteration of the do-loop will balance the child page.
................................................................................
        */ 
        assert( (balance_deeper_called++)==0 );
        rc = balance_deeper(pPage, &pCur->apPage[1]);
        if( rc==SQLITE_OK ){
          pCur->iPage = 1;
          pCur->aiIdx[0] = 0;
          pCur->aiIdx[1] = 0;
          assert( pCur->apPage[1]->nOverflow );

        }
      }else{
        break;
      }
    }else if( pPage->nOverflow==0 && pPage->nFree<=nMin ){
      break;
    }else{
................................................................................

      pPage->nOverflow = 0;

      /* The next iteration of the do-loop balances the parent page. */
      releasePage(pPage);
      pCur->iPage--;
      assert( pCur->iPage>=0 );

    }
  }while( rc==SQLITE_OK );

  if( pFree ){
    sqlite3PageFree(pFree);
  }
  return rc;
................................................................................

  if( !loc ){
    rc = btreeMoveto(pCur, pKey, nKey, appendBias, &loc);
    if( rc ) return rc;
  }
  assert( pCur->eState==CURSOR_VALID || (pCur->eState==CURSOR_INVALID && loc) );


  pPage = pCur->apPage[pCur->iPage];
  assert( pPage->intKey || nKey>=0 );
  assert( pPage->leaf || !pPage->intKey );

  TRACE(("INSERT: table=%d nkey=%lld ndata=%d page=%d %s\n",
          pCur->pgnoRoot, nKey, nData, pPage->pgno,
          loc==0 ? "overwrite" : "new entry"));
  assert( pPage->isInit );
................................................................................
    pCur->curFlags &= ~(BTCF_ValidNKey);
    rc = balance(pCur);

    /* Must make sure nOverflow is reset to zero even if the balance()
    ** fails. Internal data structure corruption will result otherwise. 
    ** Also, set the cursor state to invalid. This stops saveCursorPosition()
    ** from trying to save the current position of the cursor.  */

    pCur->apPage[pCur->iPage]->nOverflow = 0;
    pCur->eState = CURSOR_INVALID;
  }
  assert( pCur->apPage[pCur->iPage]->nOverflow==0 );


end_insert:
  return rc;
}

/*
** Delete the entry that the cursor is pointing to.  The cursor
................................................................................

  assert( cursorHoldsMutex(pCur) );
  assert( pBt->inTransaction==TRANS_WRITE );
  assert( (pBt->btsFlags & BTS_READ_ONLY)==0 );
  assert( pCur->curFlags & BTCF_WriteFlag );
  assert( hasSharedCacheTableLock(p, pCur->pgnoRoot, pCur->pKeyInfo!=0, 2) );
  assert( !hasReadConflicts(p, pCur->pgnoRoot) );


  if( NEVER(pCur->aiIdx[pCur->iPage]>=pCur->apPage[pCur->iPage]->nCell) 
   || NEVER(pCur->eState!=CURSOR_VALID)
  ){
    return SQLITE_ERROR;  /* Something has gone awry. */
  }

  iCellDepth = pCur->iPage;
  iCellIdx = pCur->aiIdx[iCellDepth];
................................................................................

  /* If the cell deleted was not located on a leaf page, then the cursor
  ** is currently pointing to the largest entry in the sub-tree headed
  ** by the child-page of the cell that was just deleted from an internal
  ** node. The cell from the leaf node needs to be moved to the internal
  ** node to replace the deleted cell.  */
  if( !pPage->leaf ){
    MemPage *pLeaf = pCur->apPage[pCur->iPage];
    int nCell;
    Pgno n = pCur->apPage[iCellDepth+1]->pgno;
    unsigned char *pTmp;

    pCell = findCell(pLeaf, pLeaf->nCell-1);
    nCell = cellSizePtr(pLeaf, pCell);
    assert( MX_CELL_SIZE(pBt) >= nCell );
................................................................................
  ** walk the cursor up the tree to the internal node and balance it as 
  ** well.  */
  rc = balance(pCur);
  if( rc==SQLITE_OK && pCur->iPage>iCellDepth ){
    while( pCur->iPage>iCellDepth ){
      releasePage(pCur->apPage[pCur->iPage--]);
    }

    rc = balance(pCur);
  }

  if( rc==SQLITE_OK ){
    moveToRoot(pCur);
  }
  return rc;
................................................................................
    int iIdx;                          /* Index of child node in parent */
    MemPage *pPage;                    /* Current page of the b-tree */

    /* If this is a leaf page or the tree is not an int-key tree, then 
    ** this page contains countable entries. Increment the entry counter
    ** accordingly.
    */

    pPage = pCur->apPage[pCur->iPage];
    if( pPage->leaf || !pPage->intKey ){
      nEntry += pPage->nCell;
    }

    /* pPage is a leaf node. This loop navigates the cursor so that it 
    ** points to the first interior cell that it points to the parent of
    ** the next page in the tree that has not yet been visited. The
................................................................................
      do {
        if( pCur->iPage==0 ){
          /* All pages of the b-tree have been visited. Return successfully. */
          *pnEntry = nEntry;
          return moveToRoot(pCur);
        }
        moveToParent(pCur);
      }while ( pCur->aiIdx[pCur->iPage]>=pCur->apPage[pCur->iPage]->nCell );

      pCur->aiIdx[pCur->iPage]++;

      pPage = pCur->apPage[pCur->iPage];
    }

    /* Descend to the child node of the cell that the cursor currently 
    ** points at. This is the right-child if (iIdx==pPage->nCell).
    */
    iIdx = pCur->aiIdx[pCur->iPage];
    if( iIdx==pPage->nCell ){
................................................................................
    return SQLITE_READONLY;
  }
  assert( (pCsr->pBt->btsFlags & BTS_READ_ONLY)==0
              && pCsr->pBt->inTransaction==TRANS_WRITE );
  assert( hasSharedCacheTableLock(pCsr->pBtree, pCsr->pgnoRoot, 0, 2) );
  assert( !hasReadConflicts(pCsr->pBtree, pCsr->pgnoRoot) );
  assert( pCsr->apPage[pCsr->iPage]->intKey );


  return accessPayload(pCsr, offset, amt, (unsigned char *)z, 1);
}

/* 
** Mark this cursor as an incremental blob cursor.
*/







>







 







>







 







>







 







>
|










>
|










>
|







 







>
|







 







|
|






>







 







|
>
>
|







 







|
>
>
|







 







>
>
|
>



|

|
|
|







 







|







 







>
|



|



|

>







 







>
|







 







|







 







|







 







>

|


|







 







>
|
|







 







|
|
>
|


|


|



|







 







|







 







|







 







|







 







|







 







>
|







 







|
>







 







|







 







|
>







 







|
>







 







>







 







>
|







 







>
|


<
>







 







>

|







 







|







 







>







 







>
|







 







|


>
|







 







>







583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
....
3648
3649
3650
3651
3652
3653
3654
3655
3656
3657
3658
3659
3660
3661
3662
....
3863
3864
3865
3866
3867
3868
3869
3870
3871
3872
3873
3874
3875
3876
3877
....
3965
3966
3967
3968
3969
3970
3971
3972
3973
3974
3975
3976
3977
3978
3979
3980
3981
3982
3983
3984
3985
3986
3987
3988
3989
3990
3991
3992
3993
3994
3995
3996
3997
3998
3999
4000
4001
4002
4003
4004
....
4045
4046
4047
4048
4049
4050
4051
4052
4053
4054
4055
4056
4057
4058
4059
4060
....
4200
4201
4202
4203
4204
4205
4206
4207
4208
4209
4210
4211
4212
4213
4214
4215
4216
4217
4218
4219
4220
4221
4222
....
4398
4399
4400
4401
4402
4403
4404
4405
4406
4407
4408
4409
4410
4411
4412
4413
4414
4415
....
4427
4428
4429
4430
4431
4432
4433
4434
4435
4436
4437
4438
4439
4440
4441
4442
4443
4444
....
4460
4461
4462
4463
4464
4465
4466
4467
4468
4469
4470
4471
4472
4473
4474
4475
4476
4477
4478
4479
4480
4481
4482
4483
4484
4485
....
4525
4526
4527
4528
4529
4530
4531
4532
4533
4534
4535
4536
4537
4538
4539
....
4571
4572
4573
4574
4575
4576
4577
4578
4579
4580
4581
4582
4583
4584
4585
4586
4587
4588
4589
4590
4591
4592
4593
4594
4595
4596
....
4638
4639
4640
4641
4642
4643
4644
4645
4646
4647
4648
4649
4650
4651
4652
4653
....
4689
4690
4691
4692
4693
4694
4695
4696
4697
4698
4699
4700
4701
4702
4703
....
4714
4715
4716
4717
4718
4719
4720
4721
4722
4723
4724
4725
4726
4727
4728
....
4737
4738
4739
4740
4741
4742
4743
4744
4745
4746
4747
4748
4749
4750
4751
4752
4753
4754
4755
4756
....
4769
4770
4771
4772
4773
4774
4775
4776
4777
4778
4779
4780
4781
4782
4783
4784
4785
....
4869
4870
4871
4872
4873
4874
4875
4876
4877
4878
4879
4880
4881
4882
4883
4884
4885
4886
4887
4888
4889
4890
4891
4892
4893
4894
4895
4896
....
5005
5006
5007
5008
5009
5010
5011
5012
5013
5014
5015
5016
5017
5018
5019
....
5093
5094
5095
5096
5097
5098
5099
5100
5101
5102
5103
5104
5105
5106
5107
....
5117
5118
5119
5120
5121
5122
5123
5124
5125
5126
5127
5128
5129
5130
5131
....
5141
5142
5143
5144
5145
5146
5147
5148
5149
5150
5151
5152
5153
5154
5155
....
5204
5205
5206
5207
5208
5209
5210
5211
5212
5213
5214
5215
5216
5217
5218
5219
....
5225
5226
5227
5228
5229
5230
5231
5232
5233
5234
5235
5236
5237
5238
5239
5240
....
5245
5246
5247
5248
5249
5250
5251
5252
5253
5254
5255
5256
5257
5258
5259
....
7438
7439
7440
7441
7442
7443
7444
7445
7446
7447
7448
7449
7450
7451
7452
7453
....
7454
7455
7456
7457
7458
7459
7460
7461
7462
7463
7464
7465
7466
7467
7468
7469
....
7534
7535
7536
7537
7538
7539
7540
7541
7542
7543
7544
7545
7546
7547
7548
....
7637
7638
7639
7640
7641
7642
7643
7644
7645
7646
7647
7648
7649
7650
7651
7652
....
7705
7706
7707
7708
7709
7710
7711
7712
7713
7714
7715

7716
7717
7718
7719
7720
7721
7722
7723
....
7735
7736
7737
7738
7739
7740
7741
7742
7743
7744
7745
7746
7747
7748
7749
7750
7751
....
7787
7788
7789
7790
7791
7792
7793
7794
7795
7796
7797
7798
7799
7800
7801
....
7823
7824
7825
7826
7827
7828
7829
7830
7831
7832
7833
7834
7835
7836
7837
....
8328
8329
8330
8331
8332
8333
8334
8335
8336
8337
8338
8339
8340
8341
8342
8343
....
8352
8353
8354
8355
8356
8357
8358
8359
8360
8361
8362
8363
8364
8365
8366
8367
8368
8369
8370
....
9139
9140
9141
9142
9143
9144
9145
9146
9147
9148
9149
9150
9151
9152
9153
static void btreeReleaseAllCursorPages(BtCursor *pCur){
  int i;
  for(i=0; i<=pCur->iPage; i++){
    releasePage(pCur->apPage[i]);
    pCur->apPage[i] = 0;
  }
  pCur->iPage = -1;
  pCur->pPage = 0;
}


/*
** Save the current cursor position in the variables BtCursor.nKey 
** and BtCursor.pKey. The cursor's state is set to CURSOR_REQUIRESEEK.
**
................................................................................
        p->eState = CURSOR_FAULT;
        p->skipNext = errCode;
      }
      for(i=0; i<=p->iPage; i++){
        releasePage(p->apPage[i]);
        p->apPage[i] = 0;
      }
      p->pPage = 0;
    }
    sqlite3BtreeLeave(pBtree);
  }
  return rc;
}

/*
................................................................................
    iTable = 0;
  }

  /* Now that no other errors can occur, finish filling in the BtCursor
  ** variables and link the cursor into the BtShared list.  */
  pCur->pgnoRoot = (Pgno)iTable;
  pCur->iPage = -1;
  pCur->pPage = 0;
  pCur->pKeyInfo = pKeyInfo;
  pCur->pBtree = p;
  pCur->pBt = pBt;
  assert( wrFlag==0 || wrFlag==BTCF_WriteFlag );
  pCur->curFlags = wrFlag;
  pCur->pNext = pBt->pCursor;
  if( pCur->pNext ){
................................................................................
** for MSVC and a macro for everything else.  Ticket #2457.
*/
#ifndef NDEBUG
  static void assertCellInfo(BtCursor *pCur){
    CellInfo info;
    int iPage = pCur->iPage;
    memset(&info, 0, sizeof(info));
    assert( pCur->pPage==pCur->apPage[iPage] );
    btreeParseCell(pCur->pPage, pCur->aiIdx[iPage], &info);
    assert( CORRUPT_DB || memcmp(&info, &pCur->info, sizeof(info))==0 );
  }
#else
  #define assertCellInfo(x)
#endif
#ifdef _MSC_VER
  /* Use a real function in MSVC to work around bugs in that compiler. */
  static void getCellInfo(BtCursor *pCur){
    if( pCur->info.nSize==0 ){
      int iPage = pCur->iPage;
      assert( pCur->pPage==pCur->apPage[iPage] );
      btreeParseCell(pCur->pPage,pCur->aiIdx[iPage],&pCur->info);
      pCur->curFlags |= BTCF_ValidNKey;
    }else{
      assertCellInfo(pCur);
    }
  }
#else /* if not _MSC_VER */
  /* Use a macro in all other compilers so that the function is inlined */
#define getCellInfo(pCur)                                                      \
  if( pCur->info.nSize==0 ){                                                   \
    int iPage = pCur->iPage;                                                   \
    assert( pCur->pPage==pCur->apPage[iPage] );                                \
    btreeParseCell(pCur->pPage,pCur->aiIdx[iPage],&pCur->info);                \
    pCur->curFlags |= BTCF_ValidNKey;                                          \
  }else{                                                                       \
    assertCellInfo(pCur);                                                      \
  }
#endif /* _MSC_VER */

#ifndef NDEBUG  /* The next routine used only within assert() statements */
................................................................................
** to return an integer result code for historical reasons.
*/
int sqlite3BtreeDataSize(BtCursor *pCur, u32 *pSize){
  assert( cursorHoldsMutex(pCur) );
  assert( pCur->eState==CURSOR_VALID );
  assert( pCur->iPage>=0 );
  assert( pCur->iPage<BTCURSOR_MAX_DEPTH );
  assert( pCur->pPage==pCur->apPage[pCur->iPage] );
  assert( pCur->pPage->intKeyLeaf==1 );
  getCellInfo(pCur);
  *pSize = pCur->info.nPayload;
  return SQLITE_OK;
}

/*
** Given the page number of an overflow page in the database (parameter
................................................................................
  u32 amt,             /* Read this many bytes */
  unsigned char *pBuf, /* Write the bytes into this buffer */ 
  int eOp              /* zero to read. non-zero to write. */
){
  unsigned char *aPayload;
  int rc = SQLITE_OK;
  int iIdx = 0;
  MemPage *pPage = pCur->pPage;             /* Btree page of current entry */
  BtShared *pBt = pCur->pBt;                /* Btree this cursor belongs to */
#ifdef SQLITE_DIRECT_OVERFLOW_READ
  unsigned char * const pBufStart = pBuf;
  int bEnd;                                 /* True if reading to end of data */
#endif

  assert( pPage );
  assert( pPage==pCur->apPage[pCur->iPage] );
  assert( pCur->eState==CURSOR_VALID );
  assert( pCur->aiIdx[pCur->iPage]<pPage->nCell );
  assert( cursorHoldsMutex(pCur) );
  assert( eOp!=2 || offset==0 );    /* Always start from beginning for eOp==2 */

  getCellInfo(pCur);
  aPayload = pCur->info.pPayload;
................................................................................
** Return SQLITE_OK on success or an error code if anything goes
** wrong.  An error is returned if "offset+amt" is larger than
** the available payload.
*/
int sqlite3BtreeKey(BtCursor *pCur, u32 offset, u32 amt, void *pBuf){
  assert( cursorHoldsMutex(pCur) );
  assert( pCur->eState==CURSOR_VALID );
  assert( pCur->iPage>=0 );
  assert( pCur->apPage[pCur->iPage]==pCur->pPage );
  assert( pCur->pPage!=0 );
  assert( pCur->aiIdx[pCur->iPage]<pCur->pPage->nCell );
  return accessPayload(pCur, offset, amt, (unsigned char*)pBuf, 0);
}

/*
** Read part of the data associated with cursor pCur.  Exactly
** "amt" bytes will be transfered into pBuf[].  The transfer
** begins at "offset".
................................................................................
  }
#endif

  assert( cursorHoldsMutex(pCur) );
  rc = restoreCursorPosition(pCur);
  if( rc==SQLITE_OK ){
    assert( pCur->eState==CURSOR_VALID );
    assert( pCur->iPage>=0 );
    assert( pCur->apPage[pCur->iPage]==pCur->pPage );
    assert( pCur->pPage!=0 );
    assert( pCur->aiIdx[pCur->iPage]<pCur->pPage->nCell );
    rc = accessPayload(pCur, offset, amt, pBuf, 0);
  }
  return rc;
}

/*
** Return a pointer to payload information from the entry that the 
................................................................................
** any btree routine is called.
*/
static const void *fetchPayload(
  BtCursor *pCur,      /* Cursor pointing to entry to read from */
  u32 *pAmt            /* Write the number of available bytes here */
){
  u32 amt;
  assert( pCur!=0 );
  assert( pCur->iPage>=0 );
  assert( pCur->apPage[pCur->iPage]==pCur->pPage );
  assert( pCur->pPage!=0 );
  assert( pCur->eState==CURSOR_VALID );
  assert( sqlite3_mutex_held(pCur->pBtree->db->mutex) );
  assert( cursorHoldsMutex(pCur) );
  assert( pCur->aiIdx[pCur->iPage]<pCur->pPage->nCell );
  assert( pCur->info.nSize>0 );
  assert( pCur->info.pPayload>pCur->pPage->aData || CORRUPT_DB );
  assert( pCur->info.pPayload<pCur->pPage->aDataEnd || CORRUPT_DB );
  amt = (int)(pCur->pPage->aDataEnd - pCur->info.pPayload);
  if( pCur->info.nLocal<amt ) amt = pCur->info.nLocal;
  *pAmt = amt;
  return (void*)pCur->info.pPayload;
}


/*
................................................................................
  assert( pCur->iPage>=0 );
  if( pCur->iPage>=(BTCURSOR_MAX_DEPTH-1) ){
    return SQLITE_CORRUPT_BKPT;
  }
  rc = getAndInitPage(pBt, newPgno, &pNewPage,
               (pCur->curFlags & BTCF_WriteFlag)==0 ? PAGER_GET_READONLY : 0);
  if( rc ) return rc;
  pCur->apPage[i+1] = pCur->pPage = pNewPage;
  pCur->aiIdx[i+1] = 0;
  pCur->iPage++;

  pCur->info.nSize = 0;
  pCur->curFlags &= ~(BTCF_ValidNKey|BTCF_ValidOvfl);
  if( pNewPage->nCell<1 || pNewPage->intKey!=pCur->apPage[i]->intKey ){
    return SQLITE_CORRUPT_BKPT;
................................................................................
** right-most child page then pCur->idx is set to one more than
** the largest cell index.
*/
static void moveToParent(BtCursor *pCur){
  assert( cursorHoldsMutex(pCur) );
  assert( pCur->eState==CURSOR_VALID );
  assert( pCur->iPage>0 );
  assert( pCur->pPage==pCur->apPage[pCur->iPage] );
  assert( pCur->pPage!=0 );
  assertParentIndex(
    pCur->apPage[pCur->iPage-1], 
    pCur->aiIdx[pCur->iPage-1], 
    pCur->pPage->pgno
  );
  testcase( pCur->aiIdx[pCur->iPage-1] > pCur->apPage[pCur->iPage-1]->nCell );

  releasePage(pCur->pPage);
  pCur->iPage--;
  pCur->pPage = pCur->apPage[pCur->iPage];
  pCur->info.nSize = 0;
  pCur->curFlags &= ~(BTCF_ValidNKey|BTCF_ValidOvfl);
}

/*
** Move the cursor to point to the root page of its b-tree structure.
**
................................................................................
                 (pCur->curFlags & BTCF_WriteFlag)==0 ? PAGER_GET_READONLY : 0);
    if( rc!=SQLITE_OK ){
      pCur->eState = CURSOR_INVALID;
      return rc;
    }
    pCur->iPage = 0;
  }
  assert( pCur->iPage==0 );
  pRoot = pCur->pPage = pCur->apPage[0];
  assert( pRoot->pgno==pCur->pgnoRoot );

  /* If pCur->pKeyInfo is not NULL, then the caller that opened this cursor
  ** expected to open it on an index b-tree. Otherwise, if pKeyInfo is
  ** NULL, the caller expects a table b-tree. If this is not the case,
  ** return an SQLITE_CORRUPT error. 
  **
................................................................................
static int moveToLeftmost(BtCursor *pCur){
  Pgno pgno;
  int rc = SQLITE_OK;
  MemPage *pPage;

  assert( cursorHoldsMutex(pCur) );
  assert( pCur->eState==CURSOR_VALID );
  while( rc==SQLITE_OK && !(pPage = pCur->pPage)->leaf ){
    assert( pCur->aiIdx[pCur->iPage]<pPage->nCell );
    pgno = get4byte(findCell(pPage, pCur->aiIdx[pCur->iPage]));
    rc = moveToChild(pCur, pgno);
  }
  return rc;
}

................................................................................
static int moveToRightmost(BtCursor *pCur){
  Pgno pgno;
  int rc = SQLITE_OK;
  MemPage *pPage = 0;

  assert( cursorHoldsMutex(pCur) );
  assert( pCur->eState==CURSOR_VALID );
  while( !(pPage = pCur->pPage)->leaf ){
    pgno = get4byte(&pPage->aData[pPage->hdrOffset+8]);
    pCur->aiIdx[pCur->iPage] = pPage->nCell;
    rc = moveToChild(pCur, pgno);
    if( rc ) return rc;
  }
  pCur->aiIdx[pCur->iPage] = pPage->nCell-1;
  assert( pCur->info.nSize==0 );
................................................................................
int sqlite3BtreeFirst(BtCursor *pCur, int *pRes){
  int rc;

  assert( cursorHoldsMutex(pCur) );
  assert( sqlite3_mutex_held(pCur->pBtree->db->mutex) );
  rc = moveToRoot(pCur);
  if( rc==SQLITE_OK ){
    assert( pCur->pPage==pCur->apPage[pCur->iPage] );
    if( pCur->eState==CURSOR_INVALID ){
      assert( pCur->pgnoRoot==0 || pCur->pPage->nCell==0 );
      *pRes = 1;
    }else{
      assert( pCur->pPage->nCell>0 );
      *pRes = 0;
      rc = moveToLeftmost(pCur);
    }
  }
  return rc;
}

................................................................................
#ifdef SQLITE_DEBUG
    /* This block serves to assert() that the cursor really does point 
    ** to the last entry in the b-tree. */
    int ii;
    for(ii=0; ii<pCur->iPage; ii++){
      assert( pCur->aiIdx[ii]==pCur->apPage[ii]->nCell );
    }
    assert( pCur->pPage==pCur->apPage[pCur->iPage] );
    assert( pCur->aiIdx[pCur->iPage]==pCur->pPage->nCell-1 );
    assert( pCur->pPage->leaf );
#endif
    return SQLITE_OK;
  }

  rc = moveToRoot(pCur);
  if( rc==SQLITE_OK ){
    if( CURSOR_INVALID==pCur->eState ){
................................................................................
    xRecordCompare = 0; /* All keys are integers */
  }

  rc = moveToRoot(pCur);
  if( rc ){
    return rc;
  }
  assert( pCur->pgnoRoot==0 || pCur->apPage[pCur->iPage]==pCur->pPage );
  assert( pCur->pgnoRoot==0 || pCur->pPage!=0 );
  assert( pCur->pgnoRoot==0 || pCur->pPage->isInit );
  assert( pCur->eState==CURSOR_INVALID || pCur->pPage->nCell>0 );
  if( pCur->eState==CURSOR_INVALID ){
    *pRes = -1;
    assert( pCur->pgnoRoot==0 || pCur->pPage->nCell==0 );
    return SQLITE_OK;
  }
  assert( pCur->pPage->intKey || pIdxKey );
  for(;;){
    int lwr, upr, idx, c;
    Pgno chldPg;
    MemPage *pPage = pCur->pPage;
    u8 *pCell;                          /* Pointer to current cell in pPage */

    /* pPage->nCell must be greater than zero. If this is the root-page
    ** the cursor would have been INVALID above and this for(;;) loop
    ** not run. If this is not the root-page, then the moveToChild() routine
    ** would have already detected db corruption. Similarly, pPage must
    ** be the right kind (index or table) of b-tree page. Otherwise
................................................................................
        assert( lwr+upr>=0 );
        idx = (lwr+upr)>>1;  /* idx = (lwr+upr)/2 */
      }
    }
    assert( lwr==upr+1 || (pPage->intKey && !pPage->leaf) );
    assert( pPage->isInit );
    if( pPage->leaf ){
      assert( pCur->aiIdx[pCur->iPage]<pCur->pPage->nCell );
      pCur->aiIdx[pCur->iPage] = (u16)idx;
      *pRes = c;
      rc = SQLITE_OK;
      goto moveto_finish;
    }
moveto_next_layer:
    if( lwr>=pPage->nCell ){
................................................................................
        pCur->skipNext = 0;
        return SQLITE_OK;
      }
      pCur->skipNext = 0;
    }
  }

  pPage = pCur->pPage;
  idx = ++pCur->aiIdx[pCur->iPage];
  assert( pPage->isInit );

  /* If the database file is corrupt, it is possible for the value of idx 
  ** to be invalid here. This can only occur if a second cursor modifies
  ** the page while cursor pCur is holding a reference to it. Which can
  ** only happen if the database is corrupt in such a way as to link the
................................................................................
    do{
      if( pCur->iPage==0 ){
        *pRes = 1;
        pCur->eState = CURSOR_INVALID;
        return SQLITE_OK;
      }
      moveToParent(pCur);
      pPage = pCur->pPage;
    }while( pCur->aiIdx[pCur->iPage]>=pPage->nCell );
    if( pPage->intKey ){
      return sqlite3BtreeNext(pCur, pRes);
    }else{
      return SQLITE_OK;
    }
  }
................................................................................
  assert( pRes!=0 );
  assert( *pRes==0 || *pRes==1 );
  assert( pCur->skipNext==0 || pCur->eState!=CURSOR_VALID );
  pCur->info.nSize = 0;
  pCur->curFlags &= ~(BTCF_ValidNKey|BTCF_ValidOvfl);
  *pRes = 0;
  if( pCur->eState!=CURSOR_VALID ) return btreeNext(pCur, pRes);
  pPage = pCur->pPage;
  if( (++pCur->aiIdx[pCur->iPage])>=pPage->nCell ){
    pCur->aiIdx[pCur->iPage]--;
    return btreeNext(pCur, pRes);
  }
  if( pPage->leaf ){
    return SQLITE_OK;
  }else{
................................................................................
        pCur->skipNext = 0;
        return SQLITE_OK;
      }
      pCur->skipNext = 0;
    }
  }

  pPage = pCur->pPage;
  assert( pPage==pCur->apPage[pCur->iPage] );
  assert( pPage->isInit );
  if( !pPage->leaf ){
    int idx = pCur->aiIdx[pCur->iPage];
    rc = moveToChild(pCur, get4byte(findCell(pPage, idx)));
    if( rc ) return rc;
    rc = moveToRightmost(pCur);
  }else{
................................................................................
      }
      moveToParent(pCur);
    }
    assert( pCur->info.nSize==0 );
    assert( (pCur->curFlags & (BTCF_ValidNKey|BTCF_ValidOvfl))==0 );

    pCur->aiIdx[pCur->iPage]--;
    assert( pCur->apPage[pCur->iPage]==pCur->pPage );
    pPage = pCur->pPage;
    if( pPage->intKey && !pPage->leaf ){
      rc = sqlite3BtreePrevious(pCur, pRes);
    }else{
      rc = SQLITE_OK;
    }
  }
  return rc;
................................................................................
  assert( *pRes==0 || *pRes==1 );
  assert( pCur->skipNext==0 || pCur->eState!=CURSOR_VALID );
  *pRes = 0;
  pCur->curFlags &= ~(BTCF_AtLast|BTCF_ValidOvfl|BTCF_ValidNKey);
  pCur->info.nSize = 0;
  if( pCur->eState!=CURSOR_VALID
   || pCur->aiIdx[pCur->iPage]==0
   || pCur->pPage->leaf==0
  ){
    return btreePrevious(pCur, pRes);
  }
  pCur->aiIdx[pCur->iPage]--;
  return SQLITE_OK;
}

................................................................................
  u8 *pFree = 0;

  TESTONLY( int balance_quick_called = 0 );
  TESTONLY( int balance_deeper_called = 0 );

  do {
    int iPage = pCur->iPage;
    MemPage *pPage = pCur->pPage;
    assert( pPage==pCur->apPage[iPage] );

    if( iPage==0 ){
      if( pPage->nOverflow ){
        /* The root page of the b-tree is overfull. In this case call the
        ** balance_deeper() function to create a new child for the root-page
        ** and copy the current contents of the root-page to it. The
        ** next iteration of the do-loop will balance the child page.
................................................................................
        */ 
        assert( (balance_deeper_called++)==0 );
        rc = balance_deeper(pPage, &pCur->apPage[1]);
        if( rc==SQLITE_OK ){
          pCur->iPage = 1;
          pCur->aiIdx[0] = 0;
          pCur->aiIdx[1] = 0;
          pCur->pPage = pCur->apPage[1];
          assert( pCur->pPage->nOverflow );
        }
      }else{
        break;
      }
    }else if( pPage->nOverflow==0 && pPage->nFree<=nMin ){
      break;
    }else{
................................................................................

      pPage->nOverflow = 0;

      /* The next iteration of the do-loop balances the parent page. */
      releasePage(pPage);
      pCur->iPage--;
      assert( pCur->iPage>=0 );
      pCur->pPage = pCur->apPage[pCur->iPage];
    }
  }while( rc==SQLITE_OK );

  if( pFree ){
    sqlite3PageFree(pFree);
  }
  return rc;
................................................................................

  if( !loc ){
    rc = btreeMoveto(pCur, pKey, nKey, appendBias, &loc);
    if( rc ) return rc;
  }
  assert( pCur->eState==CURSOR_VALID || (pCur->eState==CURSOR_INVALID && loc) );

  assert( pCur->pPage==pCur->apPage[pCur->iPage] );
  pPage = pCur->pPage;
  assert( pPage->intKey || nKey>=0 );
  assert( pPage->leaf || !pPage->intKey );

  TRACE(("INSERT: table=%d nkey=%lld ndata=%d page=%d %s\n",
          pCur->pgnoRoot, nKey, nData, pPage->pgno,
          loc==0 ? "overwrite" : "new entry"));
  assert( pPage->isInit );
................................................................................
    pCur->curFlags &= ~(BTCF_ValidNKey);
    rc = balance(pCur);

    /* Must make sure nOverflow is reset to zero even if the balance()
    ** fails. Internal data structure corruption will result otherwise. 
    ** Also, set the cursor state to invalid. This stops saveCursorPosition()
    ** from trying to save the current position of the cursor.  */
    assert( pCur->pPage==pCur->apPage[pCur->iPage] );
    pCur->pPage->nOverflow = 0;
    pCur->eState = CURSOR_INVALID;
  }

  assert( pCur->pPage->nOverflow==0 );

end_insert:
  return rc;
}

/*
** Delete the entry that the cursor is pointing to.  The cursor
................................................................................

  assert( cursorHoldsMutex(pCur) );
  assert( pBt->inTransaction==TRANS_WRITE );
  assert( (pBt->btsFlags & BTS_READ_ONLY)==0 );
  assert( pCur->curFlags & BTCF_WriteFlag );
  assert( hasSharedCacheTableLock(p, pCur->pgnoRoot, pCur->pKeyInfo!=0, 2) );
  assert( !hasReadConflicts(p, pCur->pgnoRoot) );
  assert( pCur->pPage==pCur->apPage[pCur->iPage] );

  if( NEVER(pCur->aiIdx[pCur->iPage]>=pCur->pPage->nCell) 
   || NEVER(pCur->eState!=CURSOR_VALID)
  ){
    return SQLITE_ERROR;  /* Something has gone awry. */
  }

  iCellDepth = pCur->iPage;
  iCellIdx = pCur->aiIdx[iCellDepth];
................................................................................

  /* If the cell deleted was not located on a leaf page, then the cursor
  ** is currently pointing to the largest entry in the sub-tree headed
  ** by the child-page of the cell that was just deleted from an internal
  ** node. The cell from the leaf node needs to be moved to the internal
  ** node to replace the deleted cell.  */
  if( !pPage->leaf ){
    MemPage *pLeaf = pCur->pPage;
    int nCell;
    Pgno n = pCur->apPage[iCellDepth+1]->pgno;
    unsigned char *pTmp;

    pCell = findCell(pLeaf, pLeaf->nCell-1);
    nCell = cellSizePtr(pLeaf, pCell);
    assert( MX_CELL_SIZE(pBt) >= nCell );
................................................................................
  ** walk the cursor up the tree to the internal node and balance it as 
  ** well.  */
  rc = balance(pCur);
  if( rc==SQLITE_OK && pCur->iPage>iCellDepth ){
    while( pCur->iPage>iCellDepth ){
      releasePage(pCur->apPage[pCur->iPage--]);
    }
    pCur->pPage = pCur->apPage[pCur->iPage];
    rc = balance(pCur);
  }

  if( rc==SQLITE_OK ){
    moveToRoot(pCur);
  }
  return rc;
................................................................................
    int iIdx;                          /* Index of child node in parent */
    MemPage *pPage;                    /* Current page of the b-tree */

    /* If this is a leaf page or the tree is not an int-key tree, then 
    ** this page contains countable entries. Increment the entry counter
    ** accordingly.
    */
    assert( pCur->pPage==pCur->apPage[pCur->iPage] );
    pPage = pCur->pPage;
    if( pPage->leaf || !pPage->intKey ){
      nEntry += pPage->nCell;
    }

    /* pPage is a leaf node. This loop navigates the cursor so that it 
    ** points to the first interior cell that it points to the parent of
    ** the next page in the tree that has not yet been visited. The
................................................................................
      do {
        if( pCur->iPage==0 ){
          /* All pages of the b-tree have been visited. Return successfully. */
          *pnEntry = nEntry;
          return moveToRoot(pCur);
        }
        moveToParent(pCur);
      }while ( pCur->aiIdx[pCur->iPage]>=pCur->pPage->nCell );

      pCur->aiIdx[pCur->iPage]++;
      assert( pCur->pPage==pCur->apPage[pCur->iPage] );
      pPage = pCur->pPage;
    }

    /* Descend to the child node of the cell that the cursor currently 
    ** points at. This is the right-child if (iIdx==pPage->nCell).
    */
    iIdx = pCur->aiIdx[pCur->iPage];
    if( iIdx==pPage->nCell ){
................................................................................
    return SQLITE_READONLY;
  }
  assert( (pCsr->pBt->btsFlags & BTS_READ_ONLY)==0
              && pCsr->pBt->inTransaction==TRANS_WRITE );
  assert( hasSharedCacheTableLock(pCsr->pBtree, pCsr->pgnoRoot, 0, 2) );
  assert( !hasReadConflicts(pCsr->pBtree, pCsr->pgnoRoot) );
  assert( pCsr->apPage[pCsr->iPage]->intKey );
  assert( pCsr->pPage==pCsr->apPage[pCsr->iPage] );

  return accessPayload(pCsr, offset, amt, (unsigned char *)z, 1);
}

/* 
** Mark this cursor as an incremental blob cursor.
*/

Changes to src/btreeInt.h.

514
515
516
517
518
519
520

521
522
523
524
525
526
527
  int skipNext;    /* Prev() is noop if negative. Next() is noop if positive.
                   ** Error code if eState==CURSOR_FAULT */
  u8 curFlags;              /* zero or more BTCF_* flags defined below */
  u8 eState;                /* One of the CURSOR_XXX constants (see below) */
  u8 hints;                             /* As configured by CursorSetHints() */
  i16 iPage;                            /* Index of current page in apPage */
  u16 aiIdx[BTCURSOR_MAX_DEPTH];        /* Current index in apPage[i] */

  MemPage *apPage[BTCURSOR_MAX_DEPTH];  /* Pages from root to current page */
};

/*
** Legal values for BtCursor.curFlags
*/
#define BTCF_WriteFlag    0x01   /* True if a write cursor */







>







514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
  int skipNext;    /* Prev() is noop if negative. Next() is noop if positive.
                   ** Error code if eState==CURSOR_FAULT */
  u8 curFlags;              /* zero or more BTCF_* flags defined below */
  u8 eState;                /* One of the CURSOR_XXX constants (see below) */
  u8 hints;                             /* As configured by CursorSetHints() */
  i16 iPage;                            /* Index of current page in apPage */
  u16 aiIdx[BTCURSOR_MAX_DEPTH];        /* Current index in apPage[i] */
  MemPage *pPage;                       /* Current page */
  MemPage *apPage[BTCURSOR_MAX_DEPTH];  /* Pages from root to current page */
};

/*
** Legal values for BtCursor.curFlags
*/
#define BTCF_WriteFlag    0x01   /* True if a write cursor */