/ Check-in [9a64a4f2]
Login

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

Overview
Comment:Break up the sqlite3BtreeMovetoUnpacked() routine into an eponymous routine and sqlite3BtreeMovetoIntkey(). Each routine specializes in a single kind of btree.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | split-moveto
Files: files | file ages | folders
SHA1:9a64a4f2353576ba742c2ddbf4264d00704066a1
User & Date: drh 2016-11-10 21:19:35
Context
2016-11-10
21:19
Break up the sqlite3BtreeMovetoUnpacked() routine into an eponymous routine and sqlite3BtreeMovetoIntkey(). Each routine specializes in a single kind of btree. Leaf check-in: 9a64a4f2 user: drh tags: split-moveto
20:42
Avoid a few unnecessary calls to sqlite3BtreeMovetoUnpacked(). check-in: eac0e827 user: drh tags: unpacked-IdxInsert
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/btree.c.

773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
....
5071
5072
5073
5074
5075
5076
5077
5078
5079
5080
5081
5082
5083
5084
5085
5086
5087
5088
5089
5090
5091
5092
5093
5094
5095
5096
5097
5098

5099
5100
5101
5102
5103
5104
5105
5106
5107
5108
5109
5110
5111
5112
5113
5114
5115
5116
5117
5118
5119
5120
5121
5122
5123
5124
5125
5126
5127
5128
5129
5130
5131
5132
5133
5134
5135
5136
5137
....
5143
5144
5145
5146
5147
5148
5149
5150
5151
5152
5153
5154
5155
5156
5157
5158
5159
5160
5161
5162
5163
5164
5165
5166
5167
5168
5169
5170
5171
5172
5173
5174
5175
5176
5177
5178
5179
5180
5181
5182
5183
5184
5185
5186
5187
5188
5189
5190
5191
5192
5193
5194
5195
5196
5197
5198
5199
5200
5201
5202
5203
5204
5205
5206
5207
5208
5209
5210
5211
5212
5213
5214
5215
5216
5217
5218
5219
5220
5221
5222
5223
5224
5225
5226
5227
5228
5229
5230
5231
5232
5233
5234
5235
5236
5237
5238
5239
5240
5241
5242
5243
5244
5245
5246
5247
5248
5249
5250
5251
5252
5253
5254
5255
5256
5257
5258
5259
5260
5261
5262
5263
5264
5265
5266
5267
5268
5269
5270
5271
5272
5273
5274
5275


















































































































5276
5277
5278
5279
5280
5281
5282
5283
5284
5285
5286
5287
5288
5289
5290
5291
5292
5293
....
8015
8016
8017
8018
8019
8020
8021
8022
8023
8024
8025
8026
8027
8028
8029
8030
8031
8032
8033
8034
8035
8036
8037
8038
8039
    );
    if( pIdxKey==0 ) return SQLITE_NOMEM_BKPT;
    sqlite3VdbeRecordUnpack(pCur->pKeyInfo, (int)nKey, pKey, pIdxKey);
    if( pIdxKey->nField==0 ){
      sqlite3DbFree(pCur->pKeyInfo->db, pFree);
      return SQLITE_CORRUPT_BKPT;
    }
  }else{
    pIdxKey = 0;
  }
  rc = sqlite3BtreeMovetoUnpacked(pCur, pIdxKey, nKey, bias, pRes);
  if( pFree ){
    sqlite3DbFree(pCur->pKeyInfo->db, pFree);
  }
  return rc;
}

/*
** Restore the cursor to the position it was in (or as close to as possible)
** when saveCursorPosition() was called. Note that this call deletes the 
................................................................................
**
** For index tables, the pIdxKey->eqSeen field is set to 1 if there
** exists an entry in the table that exactly matches pIdxKey.  
*/
int sqlite3BtreeMovetoUnpacked(
  BtCursor *pCur,          /* The cursor to be moved */
  UnpackedRecord *pIdxKey, /* Unpacked index key */
  i64 intKey,              /* The table key */
  int biasRight,           /* If true, bias the search to the high end */
  int *pRes                /* Write search results here */
){
  int rc;
  RecordCompare xRecordCompare;

  assert( cursorOwnsBtShared(pCur) );
  assert( sqlite3_mutex_held(pCur->pBtree->db->mutex) );
  assert( pRes );
  assert( (pIdxKey==0)==(pCur->pKeyInfo==0) );
  assert( pCur->eState!=CURSOR_VALID || (pIdxKey==0)==(pCur->curIntKey!=0) );

  /* If the cursor is already positioned at the point we are trying
  ** to move to, then just return without doing any work */
  if( pIdxKey==0
   && pCur->eState==CURSOR_VALID && (pCur->curFlags & BTCF_ValidNKey)!=0
  ){
    if( pCur->info.nKey==intKey ){
      *pRes = 0;
      return SQLITE_OK;

    }
    if( (pCur->curFlags & BTCF_AtLast)!=0 && pCur->info.nKey<intKey ){
      *pRes = -1;
      return SQLITE_OK;
    }
  }

  if( pIdxKey ){
    xRecordCompare = sqlite3VdbeFindCompare(pIdxKey);
    pIdxKey->errCode = 0;
    assert( pIdxKey->default_rc==1 
         || pIdxKey->default_rc==0 
         || pIdxKey->default_rc==-1
    );
  }else{
    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==pCur->curIntKey );
  assert( pCur->curIntKey || 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
................................................................................
    assert( pPage->nCell>0 );
    assert( pPage->intKey==(pIdxKey==0) );
    lwr = 0;
    upr = pPage->nCell-1;
    assert( biasRight==0 || biasRight==1 );
    idx = upr>>(1-biasRight); /* idx = biasRight ? upr : (lwr+upr)/2; */
    pCur->aiIdx[pCur->iPage] = (u16)idx;
    if( xRecordCompare==0 ){
      for(;;){
        i64 nCellKey;
        pCell = findCellPastPtr(pPage, idx);
        if( pPage->intKeyLeaf ){
          while( 0x80 <= *(pCell++) ){
            if( pCell>=pPage->aDataEnd ) return SQLITE_CORRUPT_BKPT;
          }
        }
        getVarint(pCell, (u64*)&nCellKey);
        if( nCellKey<intKey ){
          lwr = idx+1;
          if( lwr>upr ){ c = -1; break; }
        }else if( nCellKey>intKey ){
          upr = idx-1;
          if( lwr>upr ){ c = +1; break; }
        }else{
          assert( nCellKey==intKey );
          pCur->curFlags |= BTCF_ValidNKey;
          pCur->info.nKey = nCellKey;
          pCur->aiIdx[pCur->iPage] = (u16)idx;
          if( !pPage->leaf ){
            lwr = idx;
            goto moveto_next_layer;
          }else{
            *pRes = 0;
            rc = SQLITE_OK;
            goto moveto_finish;
          }
        }
        assert( lwr+upr>=0 );
        idx = (lwr+upr)>>1;  /* idx = (lwr+upr)/2; */
      }
    }else{
      for(;;){
        int nCell;  /* Size of the pCell cell in bytes */
        pCell = findCellPastPtr(pPage, idx);

        /* The maximum supported page-size is 65536 bytes. This means that
        ** the maximum number of record bytes stored on an index B-Tree
        ** page is less than 16384 bytes and may be stored as a 2-byte
        ** varint. This information is used to attempt to avoid parsing 
        ** the entire cell by checking for the cases where the record is 
        ** stored entirely within the b-tree page by inspecting the first 
        ** 2 bytes of the cell.
        */
        nCell = pCell[0];
        if( nCell<=pPage->max1bytePayload ){
          /* This branch runs if the record-size field of the cell is a
          ** single byte varint and the record fits entirely on the main
          ** b-tree page.  */
          testcase( pCell+nCell+1==pPage->aDataEnd );
          c = xRecordCompare(nCell, (void*)&pCell[1], pIdxKey);
        }else if( !(pCell[1] & 0x80) 
          && (nCell = ((nCell&0x7f)<<7) + pCell[1])<=pPage->maxLocal
        ){
          /* The record-size field is a 2 byte varint and the record 
          ** fits entirely on the main b-tree page.  */
          testcase( pCell+nCell+2==pPage->aDataEnd );
          c = xRecordCompare(nCell, (void*)&pCell[2], pIdxKey);
        }else{
          /* The record flows over onto one or more overflow pages. In
          ** this case the whole cell needs to be parsed, a buffer allocated
          ** and accessPayload() used to retrieve the record into the
          ** buffer before VdbeRecordCompare() can be called. 
          **
          ** If the record is corrupt, the xRecordCompare routine may read
          ** up to two varints past the end of the buffer. An extra 18 
          ** bytes of padding is allocated at the end of the buffer in
          ** case this happens.  */
          void *pCellKey;
          u8 * const pCellBody = pCell - pPage->childPtrSize;
          pPage->xParseCell(pPage, pCellBody, &pCur->info);
          nCell = (int)pCur->info.nKey;
          testcase( nCell<0 );   /* True if key size is 2^32 or more */
          testcase( nCell==0 );  /* Invalid key size:  0x80 0x80 0x00 */
          testcase( nCell==1 );  /* Invalid key size:  0x80 0x80 0x01 */
          testcase( nCell==2 );  /* Minimum legal index key size */
          if( nCell<2 ){
            rc = SQLITE_CORRUPT_BKPT;
            goto moveto_finish;
          }
          pCellKey = sqlite3Malloc( nCell+18 );
          if( pCellKey==0 ){
            rc = SQLITE_NOMEM_BKPT;
            goto moveto_finish;
          }
          pCur->aiIdx[pCur->iPage] = (u16)idx;
          rc = accessPayload(pCur, 0, nCell, (unsigned char*)pCellKey, 2);
          if( rc ){
            sqlite3_free(pCellKey);
            goto moveto_finish;
          }
          c = xRecordCompare(nCell, pCellKey, pIdxKey);
          sqlite3_free(pCellKey);
        }
        assert( 
            (pIdxKey->errCode!=SQLITE_CORRUPT || c==0)
         && (pIdxKey->errCode!=SQLITE_NOMEM || pCur->pBtree->db->mallocFailed)
        );
        if( c<0 ){
          lwr = idx+1;
        }else if( c>0 ){
          upr = idx-1;
        }else{
          assert( c==0 );
          *pRes = 0;
          rc = SQLITE_OK;
          pCur->aiIdx[pCur->iPage] = (u16)idx;
          if( pIdxKey->errCode ) rc = SQLITE_CORRUPT;
          goto moveto_finish;
        }
        if( lwr>upr ) break;
        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 ){
      chldPg = get4byte(&pPage->aData[pPage->hdrOffset+8]);
    }else{
      chldPg = get4byte(findCell(pPage, lwr));
    }
    pCur->aiIdx[pCur->iPage] = (u16)lwr;
    rc = moveToChild(pCur, chldPg);
    if( rc ) break;
  }
moveto_finish:
  pCur->info.nSize = 0;
  pCur->curFlags &= ~(BTCF_ValidNKey|BTCF_ValidOvfl);
  return rc;
}


/*
................................................................................
    ** btreeMoveto() call */
    if( (pCur->curFlags&BTCF_ValidNKey)!=0 && pX->nKey==pCur->info.nKey ){
      loc = 0;
    }else if( (pCur->curFlags&BTCF_ValidNKey)!=0 && pX->nKey>0
               && pCur->info.nKey==pX->nKey-1 ){
      loc = -1;
    }else if( loc==0 ){
      rc = sqlite3BtreeMovetoUnpacked(pCur, 0, pX->nKey, appendBias, &loc);
      if( rc ) return rc;
    }
  }else if( loc==0 ){
    if( pX->nMem ){
      UnpackedRecord r;
      memset(&r, 0, sizeof(r));
      r.pKeyInfo = pCur->pKeyInfo;
      r.aMem = pX->aMem;
      r.nField = pX->nMem;
      rc = sqlite3BtreeMovetoUnpacked(pCur, &r, 0, appendBias, &loc);
    }else{
      rc = btreeMoveto(pCur, pX->pKey, pX->nKey, appendBias, &loc);
    }
    if( rc ) return rc;
  }
  assert( pCur->eState==CURSOR_VALID || (pCur->eState==CURSOR_INVALID && loc) );








|
|
|
|
<
<







 







<









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












|
|







 







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

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








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









|







 







|









|







773
774
775
776
777
778
779
780
781
782
783


784
785
786
787
788
789
790
....
5069
5070
5071
5072
5073
5074
5075

5076
5077
5078
5079
5080
5081
5082
5083
5084





5085





5086
5087







5088
5089
5090
5091
5092
5093




5094
5095
5096
5097
5098
5099
5100
5101
5102
5103
5104
5105
5106
5107
5108
5109
5110
5111
5112
5113
5114
....
5120
5121
5122
5123
5124
5125
5126

5127

































5128
5129
5130
5131
5132
5133
5134
5135
5136
5137
5138
5139
5140
5141
5142
5143
5144
5145
5146
5147
5148
5149
5150
5151
5152
5153
5154
5155
5156
5157
5158
5159
5160
5161
5162
5163
5164
5165
5166
5167
5168
5169
5170
5171
5172
5173
5174
5175
5176
5177
5178
5179
5180
5181
5182
5183
5184
5185
5186
5187
5188
5189
5190
5191
5192
5193
5194
5195
5196
5197
5198
5199
5200
5201
5202
5203
5204
5205
5206
5207
5208

5209
5210
5211
5212
5213
5214
5215
5216
5217
5218
5219
5220
5221
5222
5223
5224
5225
5226
5227
5228
5229
5230
5231
5232
5233
5234
5235
5236
5237
5238
5239
5240
5241
5242
5243
5244
5245
5246
5247
5248
5249
5250
5251
5252
5253
5254
5255
5256
5257
5258
5259
5260
5261
5262
5263
5264
5265
5266
5267
5268
5269
5270
5271
5272
5273
5274
5275
5276
5277
5278
5279
5280
5281
5282
5283
5284
5285
5286
5287
5288
5289
5290
5291
5292
5293
5294
5295
5296
5297
5298
5299
5300
5301
5302
5303
5304
5305
5306
5307
5308
5309
5310
5311
5312
5313
5314
5315
5316
5317
5318
5319
5320
5321
5322
5323
5324
5325
5326
5327
5328
5329
5330
5331
5332
5333
5334
5335
5336
5337
5338
5339
5340
5341
5342
5343
5344
5345
5346
5347
5348
5349
....
8071
8072
8073
8074
8075
8076
8077
8078
8079
8080
8081
8082
8083
8084
8085
8086
8087
8088
8089
8090
8091
8092
8093
8094
8095
    );
    if( pIdxKey==0 ) return SQLITE_NOMEM_BKPT;
    sqlite3VdbeRecordUnpack(pCur->pKeyInfo, (int)nKey, pKey, pIdxKey);
    if( pIdxKey->nField==0 ){
      sqlite3DbFree(pCur->pKeyInfo->db, pFree);
      return SQLITE_CORRUPT_BKPT;
    }
    rc = sqlite3BtreeMovetoUnpacked(pCur, pIdxKey, bias, pRes);
    if( pFree ) sqlite3DbFree(pCur->pKeyInfo->db, pFree);
  }else{
    rc = sqlite3BtreeMovetoIntkey(pCur, nKey, bias, pRes);


  }
  return rc;
}

/*
** Restore the cursor to the position it was in (or as close to as possible)
** when saveCursorPosition() was called. Note that this call deletes the 
................................................................................
**
** For index tables, the pIdxKey->eqSeen field is set to 1 if there
** exists an entry in the table that exactly matches pIdxKey.  
*/
int sqlite3BtreeMovetoUnpacked(
  BtCursor *pCur,          /* The cursor to be moved */
  UnpackedRecord *pIdxKey, /* Unpacked index key */

  int biasRight,           /* If true, bias the search to the high end */
  int *pRes                /* Write search results here */
){
  int rc;
  RecordCompare xRecordCompare;

  assert( cursorOwnsBtShared(pCur) );
  assert( sqlite3_mutex_held(pCur->pBtree->db->mutex) );
  assert( pRes );





  assert( pIdxKey );





  assert( pCur->curIntKey==0 || pCur->eState!=CURSOR_VALID );








  xRecordCompare = sqlite3VdbeFindCompare(pIdxKey);
  pIdxKey->errCode = 0;
  assert( pIdxKey->default_rc==1 
       || pIdxKey->default_rc==0 
       || pIdxKey->default_rc==-1
  );




  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 );
  assert( !pCur->curIntKey );
  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
................................................................................
    assert( pPage->nCell>0 );
    assert( pPage->intKey==(pIdxKey==0) );
    lwr = 0;
    upr = pPage->nCell-1;
    assert( biasRight==0 || biasRight==1 );
    idx = upr>>(1-biasRight); /* idx = biasRight ? upr : (lwr+upr)/2; */
    pCur->aiIdx[pCur->iPage] = (u16)idx;

    for(;;){

































      int nCell;  /* Size of the pCell cell in bytes */
      pCell = findCellPastPtr(pPage, idx);

      /* The maximum supported page-size is 65536 bytes. This means that
      ** the maximum number of record bytes stored on an index B-Tree
      ** page is less than 16384 bytes and may be stored as a 2-byte
      ** varint. This information is used to attempt to avoid parsing 
      ** the entire cell by checking for the cases where the record is 
      ** stored entirely within the b-tree page by inspecting the first 
      ** 2 bytes of the cell.
      */
      nCell = pCell[0];
      if( nCell<=pPage->max1bytePayload ){
        /* This branch runs if the record-size field of the cell is a
        ** single byte varint and the record fits entirely on the main
        ** b-tree page.  */
        testcase( pCell+nCell+1==pPage->aDataEnd );
        c = xRecordCompare(nCell, (void*)&pCell[1], pIdxKey);
      }else if( !(pCell[1] & 0x80) 
        && (nCell = ((nCell&0x7f)<<7) + pCell[1])<=pPage->maxLocal
      ){
        /* The record-size field is a 2 byte varint and the record 
        ** fits entirely on the main b-tree page.  */
        testcase( pCell+nCell+2==pPage->aDataEnd );
        c = xRecordCompare(nCell, (void*)&pCell[2], pIdxKey);
      }else{
        /* The record flows over onto one or more overflow pages. In
        ** this case the whole cell needs to be parsed, a buffer allocated
        ** and accessPayload() used to retrieve the record into the
        ** buffer before VdbeRecordCompare() can be called. 
        **
        ** If the record is corrupt, the xRecordCompare routine may read
        ** up to two varints past the end of the buffer. An extra 18 
        ** bytes of padding is allocated at the end of the buffer in
        ** case this happens.  */
        void *pCellKey;
        u8 * const pCellBody = pCell - pPage->childPtrSize;
        pPage->xParseCell(pPage, pCellBody, &pCur->info);
        nCell = (int)pCur->info.nKey;
        testcase( nCell<0 );   /* True if key size is 2^32 or more */
        testcase( nCell==0 );  /* Invalid key size:  0x80 0x80 0x00 */
        testcase( nCell==1 );  /* Invalid key size:  0x80 0x80 0x01 */
        testcase( nCell==2 );  /* Minimum legal index key size */
        if( nCell<2 ){
          rc = SQLITE_CORRUPT_BKPT;
          goto moveto_finish;
        }
        pCellKey = sqlite3Malloc( nCell+18 );
        if( pCellKey==0 ){
          rc = SQLITE_NOMEM_BKPT;
          goto moveto_finish;
        }
        pCur->aiIdx[pCur->iPage] = (u16)idx;
        rc = accessPayload(pCur, 0, nCell, (unsigned char*)pCellKey, 2);
        if( rc ){
          sqlite3_free(pCellKey);
          goto moveto_finish;
        }
        c = xRecordCompare(nCell, pCellKey, pIdxKey);
        sqlite3_free(pCellKey);
      }
      assert( 
          (pIdxKey->errCode!=SQLITE_CORRUPT || c==0)
       && (pIdxKey->errCode!=SQLITE_NOMEM || pCur->pBtree->db->mallocFailed)
      );
      if( c<0 ){
        lwr = idx+1;
      }else if( c>0 ){
        upr = idx-1;
      }else{
        assert( c==0 );
        *pRes = 0;
        rc = SQLITE_OK;
        pCur->aiIdx[pCur->iPage] = (u16)idx;
        if( pIdxKey->errCode ) rc = SQLITE_CORRUPT;
        goto moveto_finish;
      }
      if( lwr>upr ) break;
      assert( lwr+upr>=0 );
      idx = (lwr+upr)>>1;  /* idx = (lwr+upr)/2 */
    }

    assert( lwr==upr+1 );
    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;
    }
    if( lwr>=pPage->nCell ){
      chldPg = get4byte(&pPage->aData[pPage->hdrOffset+8]);
    }else{
      chldPg = get4byte(findCell(pPage, lwr));
    }
    pCur->aiIdx[pCur->iPage] = (u16)lwr;
    rc = moveToChild(pCur, chldPg);
    if( rc ) break;
  }
moveto_finish:
  pCur->info.nSize = 0;
  pCur->curFlags &= ~(BTCF_ValidNKey|BTCF_ValidOvfl);
  return rc;
}
int sqlite3BtreeMovetoIntkey(
  BtCursor *pCur,          /* The cursor to be moved */
  i64 intKey,              /* The table key */
  int biasRight,           /* If true, bias the search to the high end */
  int *pRes                /* Write search results here */
){
  int rc;

  assert( cursorOwnsBtShared(pCur) );
  assert( sqlite3_mutex_held(pCur->pBtree->db->mutex) );
  assert( pRes );
  assert( pCur->pKeyInfo==0 );
  assert( pCur->curIntKey || pCur->eState!=CURSOR_VALID );

  /* If the cursor is already positioned at the point we are trying
  ** to move to, then just return without doing any work */
  if( pCur->eState==CURSOR_VALID && (pCur->curFlags & BTCF_ValidNKey)!=0 ){
    if( pCur->info.nKey==intKey ){
      *pRes = 0;
      return SQLITE_OK;
    }
    if( (pCur->curFlags & BTCF_AtLast)!=0 && pCur->info.nKey<intKey ){
      *pRes = -1;
      return SQLITE_OK;
    }
  }
  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 );
  assert( pCur->curIntKey );
  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
    ** a moveToChild() or moveToRoot() call would have detected corruption.  */
    assert( pPage->nCell>0 );
    assert( pPage->intKey );
    lwr = 0;
    upr = pPage->nCell-1;
    assert( biasRight==0 || biasRight==1 );
    idx = upr>>(1-biasRight); /* idx = biasRight ? upr : (lwr+upr)/2; */
    pCur->aiIdx[pCur->iPage] = (u16)idx;
    for(;;){
      i64 nCellKey;
      pCell = findCellPastPtr(pPage, idx);
      if( pPage->intKeyLeaf ){
        while( 0x80 <= *(pCell++) ){
          if( pCell>=pPage->aDataEnd ) return SQLITE_CORRUPT_BKPT;
        }
      }
      getVarint(pCell, (u64*)&nCellKey);
      if( nCellKey<intKey ){
        lwr = idx+1;
        if( lwr>upr ){ c = -1; break; }
      }else if( nCellKey>intKey ){
        upr = idx-1;
        if( lwr>upr ){ c = +1; break; }
      }else{
        assert( nCellKey==intKey );
        pCur->curFlags |= BTCF_ValidNKey;
        pCur->info.nKey = nCellKey;
        pCur->aiIdx[pCur->iPage] = (u16)idx;
        if( !pPage->leaf ){
          lwr = idx;
          goto intkey_moveto_next_layer;
        }else{
          *pRes = 0;
          rc = SQLITE_OK;
          goto intkey_moveto_finish;
        }
      }
      assert( lwr+upr>=0 );
      idx = (lwr+upr)>>1;  /* idx = (lwr+upr)/2; */
    }
    assert( lwr==upr+1 || !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 intkey_moveto_finish;
    }
intkey_moveto_next_layer:
    if( lwr>=pPage->nCell ){
      chldPg = get4byte(&pPage->aData[pPage->hdrOffset+8]);
    }else{
      chldPg = get4byte(findCell(pPage, lwr));
    }
    pCur->aiIdx[pCur->iPage] = (u16)lwr;
    rc = moveToChild(pCur, chldPg);
    if( rc ) break;
  }
intkey_moveto_finish:
  pCur->info.nSize = 0;
  pCur->curFlags &= ~(BTCF_ValidNKey|BTCF_ValidOvfl);
  return rc;
}


/*
................................................................................
    ** btreeMoveto() call */
    if( (pCur->curFlags&BTCF_ValidNKey)!=0 && pX->nKey==pCur->info.nKey ){
      loc = 0;
    }else if( (pCur->curFlags&BTCF_ValidNKey)!=0 && pX->nKey>0
               && pCur->info.nKey==pX->nKey-1 ){
      loc = -1;
    }else if( loc==0 ){
      rc = sqlite3BtreeMovetoIntkey(pCur, pX->nKey, appendBias, &loc);
      if( rc ) return rc;
    }
  }else if( loc==0 ){
    if( pX->nMem ){
      UnpackedRecord r;
      memset(&r, 0, sizeof(r));
      r.pKeyInfo = pCur->pKeyInfo;
      r.aMem = pX->aMem;
      r.nField = pX->nMem;
      rc = sqlite3BtreeMovetoUnpacked(pCur, &r, appendBias, &loc);
    }else{
      rc = btreeMoveto(pCur, pX->pKey, pX->nKey, appendBias, &loc);
    }
    if( rc ) return rc;
  }
  assert( pCur->eState==CURSOR_VALID || (pCur->eState==CURSOR_INVALID && loc) );

Changes to src/btree.h.

237
238
239
240
241
242
243





244
245
246
247
248
249
250
void sqlite3BtreeCursorHint(BtCursor*, int, ...);
#endif

int sqlite3BtreeCloseCursor(BtCursor*);
int sqlite3BtreeMovetoUnpacked(
  BtCursor*,
  UnpackedRecord *pUnKey,





  i64 intKey,
  int bias,
  int *pRes
);
int sqlite3BtreeCursorHasMoved(BtCursor*);
int sqlite3BtreeCursorRestore(BtCursor*, int*);
int sqlite3BtreeDelete(BtCursor*, u8 flags);







>
>
>
>
>







237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
void sqlite3BtreeCursorHint(BtCursor*, int, ...);
#endif

int sqlite3BtreeCloseCursor(BtCursor*);
int sqlite3BtreeMovetoUnpacked(
  BtCursor*,
  UnpackedRecord *pUnKey,
  int bias,
  int *pRes
);
int sqlite3BtreeMovetoIntkey(
  BtCursor*,
  i64 intKey,
  int bias,
  int *pRes
);
int sqlite3BtreeCursorHasMoved(BtCursor*);
int sqlite3BtreeCursorRestore(BtCursor*, int*);
int sqlite3BtreeDelete(BtCursor*, u8 flags);

Changes to src/vdbe.c.

3825
3826
3827
3828
3829
3830
3831
3832
3833
3834
3835
3836
3837
3838
3839
....
3869
3870
3871
3872
3873
3874
3875
3876
3877
3878
3879
3880
3881
3882
3883
....
4038
4039
4040
4041
4042
4043
4044
4045
4046
4047
4048
4049
4050
4051
4052
....
4132
4133
4134
4135
4136
4137
4138
4139
4140
4141
4142
4143
4144
4145
4146
....
4286
4287
4288
4289
4290
4291
4292
4293
4294
4295
4296
4297
4298
4299
4300
....
5103
5104
5105
5106
5107
5108
5109
5110
5111
5112
5113
5114
5115
5116
5117
      else if( pIn3->u.r>(double)iKey ){
        assert( OP_SeekLE==(OP_SeekLT+1) );
        assert( OP_SeekGT==(OP_SeekGE+1) );
        assert( (OP_SeekLT & 0x0001)==(OP_SeekGE & 0x0001) );
        if( (oc & 0x0001)==(OP_SeekLT & 0x0001) ) oc++;
      }
    } 
    rc = sqlite3BtreeMovetoUnpacked(pC->uc.pCursor, 0, (u64)iKey, 0, &res);
    pC->movetoTarget = iKey;  /* Used by OP_Delete */
    if( rc!=SQLITE_OK ){
      goto abort_due_to_error;
    }
  }else{
    /* For a cursor with the BTREE_SEEK_EQ hint, only the OP_SeekGE and
    ** OP_SeekLE opcodes are allowed, and these must be immediately followed
................................................................................
    assert( oc!=OP_SeekLT || r.default_rc==+1 );

    r.aMem = &aMem[pOp->p3];
#ifdef SQLITE_DEBUG
    { int i; for(i=0; i<r.nField; i++) assert( memIsValid(&r.aMem[i]) ); }
#endif
    r.eqSeen = 0;
    rc = sqlite3BtreeMovetoUnpacked(pC->uc.pCursor, &r, 0, 0, &res);
    if( rc!=SQLITE_OK ){
      goto abort_due_to_error;
    }
    if( eqOnly && r.eqSeen==0 ){
      assert( res!=0 );
      goto seek_not_found;
    }
................................................................................
    for(ii=0; ii<pIdxKey->nField; ii++){
      if( pIdxKey->aMem[ii].flags & MEM_Null ){
        takeJump = 1;
        break;
      }
    }
  }
  rc = sqlite3BtreeMovetoUnpacked(pC->uc.pCursor, pIdxKey, 0, 0, &res);
  sqlite3DbFree(db, pFree);
  if( rc!=SQLITE_OK ){
    goto abort_due_to_error;
  }
  pC->seekResult = res;
  alreadyExists = (res==0);
  pC->nullRow = 1-alreadyExists;
................................................................................
#endif
  assert( pC->isTable );
  assert( pC->eCurType==CURTYPE_BTREE );
  pCrsr = pC->uc.pCursor;
  assert( pCrsr!=0 );
  res = 0;
  iKey = pIn3->u.i;
  rc = sqlite3BtreeMovetoUnpacked(pCrsr, 0, iKey, 0, &res);
  assert( rc==SQLITE_OK || res==0 );
  pC->movetoTarget = iKey;  /* Used by OP_Delete */
  pC->nullRow = 0;
  pC->cacheStatus = CACHE_STALE;
  pC->deferredMoveto = 0;
  VdbeBranchTaken(res!=0,2);
  pC->seekResult = res;
................................................................................
      ** it finds one that is not previously used. */
      assert( pOp->p3==0 );  /* We cannot be in random rowid mode if this is
                             ** an AUTOINCREMENT table. */
      cnt = 0;
      do{
        sqlite3_randomness(sizeof(v), &v);
        v &= (MAX_ROWID>>1); v++;  /* Ensure that v is greater than zero */
      }while(  ((rc = sqlite3BtreeMovetoUnpacked(pC->uc.pCursor, 0, (u64)v,
                                                 0, &res))==SQLITE_OK)
            && (res==0)
            && (++cnt<100));
      if( rc ) goto abort_due_to_error;
      if( res==0 ){
        rc = SQLITE_FULL;   /* IMP: R-38219-53002 */
        goto abort_due_to_error;
................................................................................
  pCrsr = pC->uc.pCursor;
  assert( pCrsr!=0 );
  assert( pOp->p5==0 );
  r.pKeyInfo = pC->pKeyInfo;
  r.nField = (u16)pOp->p3;
  r.default_rc = 0;
  r.aMem = &aMem[pOp->p2];
  rc = sqlite3BtreeMovetoUnpacked(pCrsr, &r, 0, 0, &res);
  if( rc ) goto abort_due_to_error;
  if( res==0 ){
    rc = sqlite3BtreeDelete(pCrsr, BTREE_AUXDELETE);
    if( rc ) goto abort_due_to_error;
  }
  assert( pC->deferredMoveto==0 );
  pC->cacheStatus = CACHE_STALE;







|







 







|







 







|







 







|







 







|







 







|







3825
3826
3827
3828
3829
3830
3831
3832
3833
3834
3835
3836
3837
3838
3839
....
3869
3870
3871
3872
3873
3874
3875
3876
3877
3878
3879
3880
3881
3882
3883
....
4038
4039
4040
4041
4042
4043
4044
4045
4046
4047
4048
4049
4050
4051
4052
....
4132
4133
4134
4135
4136
4137
4138
4139
4140
4141
4142
4143
4144
4145
4146
....
4286
4287
4288
4289
4290
4291
4292
4293
4294
4295
4296
4297
4298
4299
4300
....
5103
5104
5105
5106
5107
5108
5109
5110
5111
5112
5113
5114
5115
5116
5117
      else if( pIn3->u.r>(double)iKey ){
        assert( OP_SeekLE==(OP_SeekLT+1) );
        assert( OP_SeekGT==(OP_SeekGE+1) );
        assert( (OP_SeekLT & 0x0001)==(OP_SeekGE & 0x0001) );
        if( (oc & 0x0001)==(OP_SeekLT & 0x0001) ) oc++;
      }
    } 
    rc = sqlite3BtreeMovetoIntkey(pC->uc.pCursor, (u64)iKey, 0, &res);
    pC->movetoTarget = iKey;  /* Used by OP_Delete */
    if( rc!=SQLITE_OK ){
      goto abort_due_to_error;
    }
  }else{
    /* For a cursor with the BTREE_SEEK_EQ hint, only the OP_SeekGE and
    ** OP_SeekLE opcodes are allowed, and these must be immediately followed
................................................................................
    assert( oc!=OP_SeekLT || r.default_rc==+1 );

    r.aMem = &aMem[pOp->p3];
#ifdef SQLITE_DEBUG
    { int i; for(i=0; i<r.nField; i++) assert( memIsValid(&r.aMem[i]) ); }
#endif
    r.eqSeen = 0;
    rc = sqlite3BtreeMovetoUnpacked(pC->uc.pCursor, &r, 0, &res);
    if( rc!=SQLITE_OK ){
      goto abort_due_to_error;
    }
    if( eqOnly && r.eqSeen==0 ){
      assert( res!=0 );
      goto seek_not_found;
    }
................................................................................
    for(ii=0; ii<pIdxKey->nField; ii++){
      if( pIdxKey->aMem[ii].flags & MEM_Null ){
        takeJump = 1;
        break;
      }
    }
  }
  rc = sqlite3BtreeMovetoUnpacked(pC->uc.pCursor, pIdxKey, 0, &res);
  sqlite3DbFree(db, pFree);
  if( rc!=SQLITE_OK ){
    goto abort_due_to_error;
  }
  pC->seekResult = res;
  alreadyExists = (res==0);
  pC->nullRow = 1-alreadyExists;
................................................................................
#endif
  assert( pC->isTable );
  assert( pC->eCurType==CURTYPE_BTREE );
  pCrsr = pC->uc.pCursor;
  assert( pCrsr!=0 );
  res = 0;
  iKey = pIn3->u.i;
  rc = sqlite3BtreeMovetoIntkey(pCrsr, iKey, 0, &res);
  assert( rc==SQLITE_OK || res==0 );
  pC->movetoTarget = iKey;  /* Used by OP_Delete */
  pC->nullRow = 0;
  pC->cacheStatus = CACHE_STALE;
  pC->deferredMoveto = 0;
  VdbeBranchTaken(res!=0,2);
  pC->seekResult = res;
................................................................................
      ** it finds one that is not previously used. */
      assert( pOp->p3==0 );  /* We cannot be in random rowid mode if this is
                             ** an AUTOINCREMENT table. */
      cnt = 0;
      do{
        sqlite3_randomness(sizeof(v), &v);
        v &= (MAX_ROWID>>1); v++;  /* Ensure that v is greater than zero */
      }while(  ((rc = sqlite3BtreeMovetoIntkey(pC->uc.pCursor, (u64)v,
                                                 0, &res))==SQLITE_OK)
            && (res==0)
            && (++cnt<100));
      if( rc ) goto abort_due_to_error;
      if( res==0 ){
        rc = SQLITE_FULL;   /* IMP: R-38219-53002 */
        goto abort_due_to_error;
................................................................................
  pCrsr = pC->uc.pCursor;
  assert( pCrsr!=0 );
  assert( pOp->p5==0 );
  r.pKeyInfo = pC->pKeyInfo;
  r.nField = (u16)pOp->p3;
  r.default_rc = 0;
  r.aMem = &aMem[pOp->p2];
  rc = sqlite3BtreeMovetoUnpacked(pCrsr, &r, 0, &res);
  if( rc ) goto abort_due_to_error;
  if( res==0 ){
    rc = sqlite3BtreeDelete(pCrsr, BTREE_AUXDELETE);
    if( rc ) goto abort_due_to_error;
  }
  assert( pC->deferredMoveto==0 );
  pC->cacheStatus = CACHE_STALE;

Changes to src/vdbeaux.c.

3004
3005
3006
3007
3008
3009
3010
3011
3012
3013
3014
3015
3016
3017
3018
  int res, rc;
#ifdef SQLITE_TEST
  extern int sqlite3_search_count;
#endif
  assert( p->deferredMoveto );
  assert( p->isTable );
  assert( p->eCurType==CURTYPE_BTREE );
  rc = sqlite3BtreeMovetoUnpacked(p->uc.pCursor, 0, p->movetoTarget, 0, &res);
  if( rc ) return rc;
  if( res!=0 ) return SQLITE_CORRUPT_BKPT;
#ifdef SQLITE_TEST
  sqlite3_search_count++;
#endif
  p->deferredMoveto = 0;
  p->cacheStatus = CACHE_STALE;







|







3004
3005
3006
3007
3008
3009
3010
3011
3012
3013
3014
3015
3016
3017
3018
  int res, rc;
#ifdef SQLITE_TEST
  extern int sqlite3_search_count;
#endif
  assert( p->deferredMoveto );
  assert( p->isTable );
  assert( p->eCurType==CURTYPE_BTREE );
  rc = sqlite3BtreeMovetoIntkey(p->uc.pCursor, p->movetoTarget, 0, &res);
  if( rc ) return rc;
  if( res!=0 ) return SQLITE_CORRUPT_BKPT;
#ifdef SQLITE_TEST
  sqlite3_search_count++;
#endif
  p->deferredMoveto = 0;
  p->cacheStatus = CACHE_STALE;