/ Check-in [dbd0125c]
Login

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

Overview
Comment:Remove dead code from btree.c. Ticket #2050. (CVS 3500)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:dbd0125c62457681689db48e1f0a752767855773
User & Date: drh 2006-11-01 12:08:41
Context
2006-11-01
12:20
Modify Makefile.in to install sqlite3ext.h. (CVS 3501) check-in: 35c8c478 user: drh tags: trunk
12:08
Remove dead code from btree.c. Ticket #2050. (CVS 3500) check-in: dbd0125c user: drh tags: trunk
2006-10-31
21:27
Change the default temp file prefix to be "sqlite" spelled backwards. Tickets #2049 et al. (CVS 3499) check-in: a19ce5c1 user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/btree.c.

5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
....
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
....
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
....
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
....
2967
2968
2969
2970
2971
2972
2973
2974
2975
2976
2977
2978
2979
2980
2981
....
3105
3106
3107
3108
3109
3110
3111
3112
3113
3114
3115
3116
3117
3118
3119
....
3167
3168
3169
3170
3171
3172
3173
3174
3175
3176
3177
3178
3179
3180
3181
....
3215
3216
3217
3218
3219
3220
3221
3222
3223
3224
3225
3226
3227
3228
3229
3230
3231
3232
....
3248
3249
3250
3251
3252
3253
3254
3255
3256
3257
3258
3259
3260
3261
3262
....
3402
3403
3404
3405
3406
3407
3408
3409
3410
3411
3412
3413
3414
3415
3416
....
4254
4255
4256
4257
4258
4259
4260
4261
4262
4263
4264
4265
4266
4267
4268
....
4994
4995
4996
4997
4998
4999
5000
5001
5002
5003
5004
5005
5006
5007
5008
5009
....
5980
5981
5982
5983
5984
5985
5986
5987
5988
5989
5990
5991
5992
5993
5994
5995
5996
5997
5998
5999
6000
6001
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** $Id: btree.c,v 1.328 2006/08/16 16:42:48 drh Exp $
**
** This file implements a external (disk-based) database using BTrees.
** For a detailed discussion of BTrees, refer to
**
**     Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
**     "Sorting And Searching", pages 473-480. Addison-Wesley
**     Publishing Company, Reading, Massachusetts.
................................................................................
  u8 *pCell;
  pCell = findOverflowCell(pPage, iCell);
  return ptrmapPutOvflPtr(pPage, pCell);
}
#endif


/*
** Do sanity checking on a page.  Throw an exception if anything is
** not right.
**
** This routine is used for internal error checking only.  It is omitted
** from most builds.
*/
#if defined(BTREE_DEBUG) && !defined(NDEBUG) && 0
static void _pageIntegrity(MemPage *pPage){
  int usableSize;
  u8 *data;
  int i, j, idx, c, pc, hdr, nFree;
  int cellOffset;
  int nCell, cellLimit;
  u8 *used;

  used = sqliteMallocRaw( pPage->pBt->pageSize );
  if( used==0 ) return;
  usableSize = pPage->pBt->usableSize;
  assert( pPage->aData==&((unsigned char*)pPage)[-pPage->pBt->pageSize] );
  hdr = pPage->hdrOffset;
  assert( hdr==(pPage->pgno==1 ? 100 : 0) );
  assert( pPage->pgno==sqlite3pager_pagenumber(pPage->aData) );
  c = pPage->aData[hdr];
  if( pPage->isInit ){
    assert( pPage->leaf == ((c & PTF_LEAF)!=0) );
    assert( pPage->zeroData == ((c & PTF_ZERODATA)!=0) );
    assert( pPage->leafData == ((c & PTF_LEAFDATA)!=0) );
    assert( pPage->intKey == ((c & (PTF_INTKEY|PTF_LEAFDATA))!=0) );
    assert( pPage->hasData ==
             !(pPage->zeroData || (!pPage->leaf && pPage->leafData)) );
    assert( pPage->cellOffset==pPage->hdrOffset+12-4*pPage->leaf );
    assert( pPage->nCell = get2byte(&pPage->aData[hdr+3]) );
  }
  data = pPage->aData;
  memset(used, 0, usableSize);
  for(i=0; i<hdr+10-pPage->leaf*4; i++) used[i] = 1;
  nFree = 0;
  pc = get2byte(&data[hdr+1]);
  while( pc ){
    int size;
    assert( pc>0 && pc<usableSize-4 );
    size = get2byte(&data[pc+2]);
    assert( pc+size<=usableSize );
    nFree += size;
    for(i=pc; i<pc+size; i++){
      assert( used[i]==0 );
      used[i] = 1;
    }
    pc = get2byte(&data[pc]);
  }
  idx = 0;
  nCell = get2byte(&data[hdr+3]);
  cellLimit = get2byte(&data[hdr+5]);
  assert( pPage->isInit==0 
         || pPage->nFree==nFree+data[hdr+7]+cellLimit-(cellOffset+2*nCell) );
  cellOffset = pPage->cellOffset;
  for(i=0; i<nCell; i++){
    int size;
    pc = get2byte(&data[cellOffset+2*i]);
    assert( pc>0 && pc<usableSize-4 );
    size = cellSize(pPage, &data[pc]);
    assert( pc+size<=usableSize );
    for(j=pc; j<pc+size; j++){
      assert( used[j]==0 );
      used[j] = 1;
    }
  }
  for(i=cellOffset+2*nCell; i<cellimit; i++){
    assert( used[i]==0 );
    used[i] = 1;
  }
  nFree = 0;
  for(i=0; i<usableSize; i++){
    assert( used[i]<=1 );
    if( used[i]==0 ) nFree++;
  }
  assert( nFree==data[hdr+7] );
  sqliteFree(used);
}
#define pageIntegrity(X) _pageIntegrity(X)
#else
# define pageIntegrity(X)
#endif

/* A bunch of assert() statements to check the transaction state variables
** of handle p (type Btree*) are internally consistent.
*/
#define btreeIntegrity(p) \
  assert( p->inTrans!=TRANS_NONE || p->pBt->nTransaction<p->pBt->nRef ); \
  assert( p->pBt->nTransaction<=p->pBt->nRef ); \
  assert( p->pBt->inTransaction!=TRANS_NONE || p->pBt->nTransaction==0 ); \
................................................................................
  pPage->nFree = nFree;
  if( nFree>=usableSize ){
    /* Free space cannot exceed total page size */
    return SQLITE_CORRUPT_BKPT; 
  }

  pPage->isInit = 1;
  pageIntegrity(pPage);
  return SQLITE_OK;
}

/*
** Set up a raw page so that it looks like a database page holding
** no entries.
*/
................................................................................
  decodeFlags(pPage, flags);
  pPage->hdrOffset = hdr;
  pPage->cellOffset = first;
  pPage->nOverflow = 0;
  pPage->idxShift = 0;
  pPage->nCell = 0;
  pPage->isInit = 1;
  pageIntegrity(pPage);
}

/*
** Get a page from the pager.  Initialize the MemPage.pBt and
** MemPage.aData elements if needed.
*/
static int getPage(BtShared *pBt, Pgno pgno, MemPage **ppPage){
................................................................................
  int ovflSize;
  u32 nKey;

  assert( pCur!=0 && pCur->pPage!=0 );
  assert( pCur->eState==CURSOR_VALID );
  pBt = pCur->pBtree->pBt;
  pPage = pCur->pPage;
  pageIntegrity(pPage);
  assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
  getCellInfo(pCur);
  aPayload = pCur->info.pCell + pCur->info.nHeader;
  if( pPage->intKey ){
    nKey = 0;
  }else{
    nKey = pCur->info.nKey;
................................................................................
  MemPage *pPage;
  u32 nKey;
  int nLocal;

  assert( pCur!=0 && pCur->pPage!=0 );
  assert( pCur->eState==CURSOR_VALID );
  pPage = pCur->pPage;
  pageIntegrity(pPage);
  assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
  getCellInfo(pCur);
  aPayload = pCur->info.pCell;
  aPayload += pCur->info.nHeader;
  if( pPage->intKey ){
    nKey = 0;
  }else{
................................................................................
  MemPage *pNewPage;
  MemPage *pOldPage;
  BtShared *pBt = pCur->pBtree->pBt;

  assert( pCur->eState==CURSOR_VALID );
  rc = getAndInitPage(pBt, newPgno, &pNewPage, pCur->pPage);
  if( rc ) return rc;
  pageIntegrity(pNewPage);
  pNewPage->idxParent = pCur->idx;
  pOldPage = pCur->pPage;
  pOldPage->idxShift = 0;
  releasePage(pOldPage);
  pCur->pPage = pNewPage;
  pCur->idx = 0;
  pCur->info.nSize = 0;
................................................................................
  MemPage *pPage;
  int idxParent;

  assert( pCur->eState==CURSOR_VALID );
  pPage = pCur->pPage;
  assert( pPage!=0 );
  assert( !isRootPage(pPage) );
  pageIntegrity(pPage);
  pParent = pPage->pParent;
  assert( pParent!=0 );
  pageIntegrity(pParent);
  idxParent = pPage->idxParent;
  sqlite3pager_ref(pParent->aData);
  releasePage(pPage);
  pCur->pPage = pParent;
  pCur->info.nSize = 0;
  assert( pParent->idxShift==0 );
  pCur->idx = idxParent;
................................................................................
    if( 
      SQLITE_OK!=(rc = getAndInitPage(pBt, pCur->pgnoRoot, &pRoot, 0))
    ){
      pCur->eState = CURSOR_INVALID;
      return rc;
    }
    releasePage(pCur->pPage);
    pageIntegrity(pRoot);
    pCur->pPage = pRoot;
  }
  pCur->idx = 0;
  pCur->info.nSize = 0;
  if( pRoot->nCell==0 && !pRoot->leaf ){
    Pgno subpage;
    assert( pRoot->pgno==1 );
................................................................................
    MemPage *pPage = pCur->pPage;
    int c = -1;  /* pRes return if table is empty must be -1 */
    lwr = 0;
    upr = pPage->nCell-1;
    if( !pPage->intKey && pKey==0 ){
      return SQLITE_CORRUPT_BKPT;
    }
    pageIntegrity(pPage);
    while( lwr<=upr ){
      void *pCellKey;
      i64 nCellKey;
      pCur->idx = (lwr+upr)/2;
      pCur->info.nSize = 0;
      if( pPage->intKey ){
        u8 *pCell;
................................................................................
    for(j=end-2, ptr=&data[j]; j>ins; j-=2, ptr-=2){
      ptr[0] = ptr[-2];
      ptr[1] = ptr[-1];
    }
    put2byte(&data[ins], idx);
    put2byte(&data[hdr+3], pPage->nCell);
    pPage->idxShift = 1;
    pageIntegrity(pPage);
#ifndef SQLITE_OMIT_AUTOVACUUM
    if( pPage->pBt->autoVacuum ){
      /* The cell may contain a pointer to an overflow page. If so, write
      ** the entry for the overflow page into the pointer map.
      */
      CellInfo info;
      parseCellPtr(pPage, pCell, &info);
................................................................................

  /*
  ** Balance the parent page.  Note that the current page (pPage) might
  ** have been added to the freelist so it might no longer be initialized.
  ** But the parent page will always be initialized.
  */
  assert( pParent->isInit );
  /* assert( pPage->isInit ); // No! pPage might have been added to freelist */
  /* pageIntegrity(pPage);    // No! pPage might have been added to freelist */ 
  rc = balance(pParent, 0);
  
  /*
  ** Cleanup before returning.
  */
balance_cleanup:
  sqliteFree(apCell);
................................................................................
  BtCursor tmpCur;

  int rc = restoreOrClearCursorPosition(pCur, 1);
  if( rc!=SQLITE_OK ){
    return rc;
  }

  pageIntegrity(pPage);
  assert( pPage->isInit );
  getTempCursor(pCur, &tmpCur);
  while( upCnt-- ){
    moveToParent(&tmpCur);
  }
  pPage = tmpCur.pPage;
  pageIntegrity(pPage);
  aResult[0] = sqlite3pager_pagenumber(pPage->aData);
  assert( aResult[0]==pPage->pgno );
  aResult[1] = tmpCur.idx;
  aResult[2] = pPage->nCell;
  if( tmpCur.idx>=0 && tmpCur.idx<pPage->nCell ){
    getCellInfo(&tmpCur);
    aResult[3] = tmpCur.info.nSize;







|







 







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







 







<







 







<







 







<







 







<







 







<







 







<


<







 







<







 







<







 







<







 







<
<







 







<






<







5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
....
1035
1036
1037
1038
1039
1040
1041





















































































1042
1043
1044
1045
1046
1047
1048
....
1341
1342
1343
1344
1345
1346
1347

1348
1349
1350
1351
1352
1353
1354
....
1371
1372
1373
1374
1375
1376
1377

1378
1379
1380
1381
1382
1383
1384
....
2880
2881
2882
2883
2884
2885
2886

2887
2888
2889
2890
2891
2892
2893
....
3017
3018
3019
3020
3021
3022
3023

3024
3025
3026
3027
3028
3029
3030
....
3078
3079
3080
3081
3082
3083
3084

3085
3086
3087
3088
3089
3090
3091
....
3125
3126
3127
3128
3129
3130
3131

3132
3133

3134
3135
3136
3137
3138
3139
3140
....
3156
3157
3158
3159
3160
3161
3162

3163
3164
3165
3166
3167
3168
3169
....
3309
3310
3311
3312
3313
3314
3315

3316
3317
3318
3319
3320
3321
3322
....
4160
4161
4162
4163
4164
4165
4166

4167
4168
4169
4170
4171
4172
4173
....
4899
4900
4901
4902
4903
4904
4905


4906
4907
4908
4909
4910
4911
4912
....
5883
5884
5885
5886
5887
5888
5889

5890
5891
5892
5893
5894
5895

5896
5897
5898
5899
5900
5901
5902
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** $Id: btree.c,v 1.329 2006/11/01 12:08:41 drh Exp $
**
** This file implements a external (disk-based) database using BTrees.
** For a detailed discussion of BTrees, refer to
**
**     Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
**     "Sorting And Searching", pages 473-480. Addison-Wesley
**     Publishing Company, Reading, Massachusetts.
................................................................................
  u8 *pCell;
  pCell = findOverflowCell(pPage, iCell);
  return ptrmapPutOvflPtr(pPage, pCell);
}
#endif























































































/* A bunch of assert() statements to check the transaction state variables
** of handle p (type Btree*) are internally consistent.
*/
#define btreeIntegrity(p) \
  assert( p->inTrans!=TRANS_NONE || p->pBt->nTransaction<p->pBt->nRef ); \
  assert( p->pBt->nTransaction<=p->pBt->nRef ); \
  assert( p->pBt->inTransaction!=TRANS_NONE || p->pBt->nTransaction==0 ); \
................................................................................
  pPage->nFree = nFree;
  if( nFree>=usableSize ){
    /* Free space cannot exceed total page size */
    return SQLITE_CORRUPT_BKPT; 
  }

  pPage->isInit = 1;

  return SQLITE_OK;
}

/*
** Set up a raw page so that it looks like a database page holding
** no entries.
*/
................................................................................
  decodeFlags(pPage, flags);
  pPage->hdrOffset = hdr;
  pPage->cellOffset = first;
  pPage->nOverflow = 0;
  pPage->idxShift = 0;
  pPage->nCell = 0;
  pPage->isInit = 1;

}

/*
** Get a page from the pager.  Initialize the MemPage.pBt and
** MemPage.aData elements if needed.
*/
static int getPage(BtShared *pBt, Pgno pgno, MemPage **ppPage){
................................................................................
  int ovflSize;
  u32 nKey;

  assert( pCur!=0 && pCur->pPage!=0 );
  assert( pCur->eState==CURSOR_VALID );
  pBt = pCur->pBtree->pBt;
  pPage = pCur->pPage;

  assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
  getCellInfo(pCur);
  aPayload = pCur->info.pCell + pCur->info.nHeader;
  if( pPage->intKey ){
    nKey = 0;
  }else{
    nKey = pCur->info.nKey;
................................................................................
  MemPage *pPage;
  u32 nKey;
  int nLocal;

  assert( pCur!=0 && pCur->pPage!=0 );
  assert( pCur->eState==CURSOR_VALID );
  pPage = pCur->pPage;

  assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
  getCellInfo(pCur);
  aPayload = pCur->info.pCell;
  aPayload += pCur->info.nHeader;
  if( pPage->intKey ){
    nKey = 0;
  }else{
................................................................................
  MemPage *pNewPage;
  MemPage *pOldPage;
  BtShared *pBt = pCur->pBtree->pBt;

  assert( pCur->eState==CURSOR_VALID );
  rc = getAndInitPage(pBt, newPgno, &pNewPage, pCur->pPage);
  if( rc ) return rc;

  pNewPage->idxParent = pCur->idx;
  pOldPage = pCur->pPage;
  pOldPage->idxShift = 0;
  releasePage(pOldPage);
  pCur->pPage = pNewPage;
  pCur->idx = 0;
  pCur->info.nSize = 0;
................................................................................
  MemPage *pPage;
  int idxParent;

  assert( pCur->eState==CURSOR_VALID );
  pPage = pCur->pPage;
  assert( pPage!=0 );
  assert( !isRootPage(pPage) );

  pParent = pPage->pParent;
  assert( pParent!=0 );

  idxParent = pPage->idxParent;
  sqlite3pager_ref(pParent->aData);
  releasePage(pPage);
  pCur->pPage = pParent;
  pCur->info.nSize = 0;
  assert( pParent->idxShift==0 );
  pCur->idx = idxParent;
................................................................................
    if( 
      SQLITE_OK!=(rc = getAndInitPage(pBt, pCur->pgnoRoot, &pRoot, 0))
    ){
      pCur->eState = CURSOR_INVALID;
      return rc;
    }
    releasePage(pCur->pPage);

    pCur->pPage = pRoot;
  }
  pCur->idx = 0;
  pCur->info.nSize = 0;
  if( pRoot->nCell==0 && !pRoot->leaf ){
    Pgno subpage;
    assert( pRoot->pgno==1 );
................................................................................
    MemPage *pPage = pCur->pPage;
    int c = -1;  /* pRes return if table is empty must be -1 */
    lwr = 0;
    upr = pPage->nCell-1;
    if( !pPage->intKey && pKey==0 ){
      return SQLITE_CORRUPT_BKPT;
    }

    while( lwr<=upr ){
      void *pCellKey;
      i64 nCellKey;
      pCur->idx = (lwr+upr)/2;
      pCur->info.nSize = 0;
      if( pPage->intKey ){
        u8 *pCell;
................................................................................
    for(j=end-2, ptr=&data[j]; j>ins; j-=2, ptr-=2){
      ptr[0] = ptr[-2];
      ptr[1] = ptr[-1];
    }
    put2byte(&data[ins], idx);
    put2byte(&data[hdr+3], pPage->nCell);
    pPage->idxShift = 1;

#ifndef SQLITE_OMIT_AUTOVACUUM
    if( pPage->pBt->autoVacuum ){
      /* The cell may contain a pointer to an overflow page. If so, write
      ** the entry for the overflow page into the pointer map.
      */
      CellInfo info;
      parseCellPtr(pPage, pCell, &info);
................................................................................

  /*
  ** Balance the parent page.  Note that the current page (pPage) might
  ** have been added to the freelist so it might no longer be initialized.
  ** But the parent page will always be initialized.
  */
  assert( pParent->isInit );


  rc = balance(pParent, 0);
  
  /*
  ** Cleanup before returning.
  */
balance_cleanup:
  sqliteFree(apCell);
................................................................................
  BtCursor tmpCur;

  int rc = restoreOrClearCursorPosition(pCur, 1);
  if( rc!=SQLITE_OK ){
    return rc;
  }


  assert( pPage->isInit );
  getTempCursor(pCur, &tmpCur);
  while( upCnt-- ){
    moveToParent(&tmpCur);
  }
  pPage = tmpCur.pPage;

  aResult[0] = sqlite3pager_pagenumber(pPage->aData);
  assert( aResult[0]==pPage->pgno );
  aResult[1] = tmpCur.idx;
  aResult[2] = pPage->nCell;
  if( tmpCur.idx>=0 && tmpCur.idx<pPage->nCell ){
    getCellInfo(&tmpCur);
    aResult[3] = tmpCur.info.nSize;