/ Check-in [433ae0d3]
Login

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

Overview
Comment:The btree.c module now passes all the historical regression tests. New tests for new functionality still need to be added. (CVS 1342)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:433ae0d327e5d5b0761e88418ed57fc4cbf4966b
User & Date: drh 2004-05-10 16:18:48
Context
2004-05-10
18:45
The btree.c module passes all tests and is ready for integration. Still need to go back and do coverage testing. (CVS 1343) check-in: 84506b23 user: drh tags: trunk
16:18
The btree.c module now passes all the historical regression tests. New tests for new functionality still need to be added. (CVS 1342) check-in: 433ae0d3 user: drh tags: trunk
12:07
Add flags values to the Mem structure to accomodate BLOBs and to show the representation of strings. (CVS 1341) check-in: 3af283f4 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
...
525
526
527
528
529
530
531

532
533
534
535
536
537
538
539
540
541
542
543

544
545
546
547
548
549
550
....
1128
1129
1130
1131
1132
1133
1134

1135
1136
1137



1138







1139
1140
1141
1142
1143
1144
1145
....
1277
1278
1279
1280
1281
1282
1283




1284
1285
1286
1287
1288
1289
1290
....
2430
2431
2432
2433
2434
2435
2436
2437


2438
2439
2440
2441
2442
2443
2444
2445
2446






2447
2448
2449
2450
2451
2452
2453
2454
2455
2456
2457
2458





2459
2460
2461
2462
2463
2464
2465
2466
....
2615
2616
2617
2618
2619
2620
2621

2622
2623
2624
2625
2626
2627
2628
....
2674
2675
2676
2677
2678
2679
2680
2681
2682
2683
2684
2685
2686
2687
2688
....
2951
2952
2953
2954
2955
2956
2957









2958
2959
2960
2961
2962
2963
2964
2965
2966
2967
2968
2969
2970
2971
2972
2973
2974
2975
2976
2977

2978
2979

2980
2981

2982
2983
2984
2985
2986
2987
2988
2989
2990
....
3129
3130
3131
3132
3133
3134
3135
3136
3137
3138
3139
3140
3141
3142
3143
....
3185
3186
3187
3188
3189
3190
3191
3192
3193
3194
3195
3196
3197
3198
3199
3200
3201
3202
3203
3204
3205
3206
3207
3208

3209
3210
3211
3212
3213
3214
3215
3216
3217
3218
** 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.121 2004/05/10 10:34:34 danielk1977 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.
................................................................................
**
** Algorithm:  Carve a piece off of the first freeblock that is
** nByte in size or that larger.
*/
static int allocateSpace(MemPage *pPage, int nByte){
  int addr, pc, hdr;
  int size;

  unsigned char *data;
#ifndef NDEBUG
  int cnt = 0;
#endif

  data = pPage->aData;
  assert( sqlite3pager_iswriteable(data) );
  assert( pPage->pBt );
  if( nByte<4 ) nByte = 4;
  if( pPage->nFree<nByte || pPage->isOverfull ) return 0;
  hdr = pPage->hdrOffset;
  if( data[hdr+5]>=60 ){

    defragmentPage(pPage);
  }
  addr = hdr+1;
  pc = get2byte(&data[addr]);
  assert( addr<pc );
  assert( pc<=pPage->pBt->pageSize-4 );
  while( (size = get2byte(&data[pc+2]))<nByte ){
................................................................................
** in an error.
**
** This will release the write lock on the database file.  If there
** are no active cursors, it also releases the read lock.
*/
int sqlite3BtreeRollback(Btree *pBt){
  int rc;

  if( pBt->inTrans==0 ) return SQLITE_OK;
  pBt->inTrans = 0;
  pBt->inStmt = 0;



  rc = pBt->readOnly ? SQLITE_OK : sqlite3pager_rollback(pBt->pPager);







  invalidateCursors(pBt);
  unlockBtreeIfUnused(pBt);
  return rc;
}

/*
** Set the checkpoint for the current transaction.  The checkpoint serves
................................................................................
  }
  pCur = sqliteMalloc( sizeof(*pCur) );
  if( pCur==0 ){
    rc = SQLITE_NOMEM;
    goto create_cursor_exception;
  }
  pCur->pgnoRoot = (Pgno)iTable;




  rc = getAndInitPage(pBt, pCur->pgnoRoot, &pCur->pPage, 0);
  if( rc!=SQLITE_OK ){
    goto create_cursor_exception;
  }
  pCur->xCompare = xCmp ? xCmp : dfltCompare;
  pCur->pArg = pArg;
  pCur->pBt = pBt;
................................................................................
}

/*
** Insert a new cell on pPage at cell index "i".  pCell points to the
** content of the cell.
**
** If the cell content will fit on the page, then put it there.  If it
** will not fit, then just make pPage->aCell[i] point to the content


** and set pPage->isOverfull.  
**
** Try to maintain the integrity of the linked list of cells.  But if
** the cell being inserted does not fit on the page, this will not be
** possible.  If the linked list is not maintained, then just update
** pPage->aCell[] and set the pPage->needRelink flag so that we will
** know to rebuild the linked list later.
*/
static void insertCell(MemPage *pPage, int i, unsigned char *pCell, int sz){






  int idx, j;
  assert( i>=0 && i<=pPage->nCell );
  assert( sz==cellSize(pPage, pCell) );
  assert( sqlite3pager_iswriteable(pPage->aData) );
  idx = pPage->needRelink ? 0 : allocateSpace(pPage, sz);
  resizeCellArray(pPage, pPage->nCell+1);
  for(j=pPage->nCell; j>i; j--){
    pPage->aCell[j] = pPage->aCell[j-1];
  }
  pPage->nCell++;
  if( idx<=0 ){
    pPage->isOverfull = 1;





    pPage->aCell[i] = pCell;
  }else{
    u8 *data = pPage->aData;
    memcpy(&data[idx], pCell, sz);
    pPage->aCell[i] = &data[idx];
  }
  if( !pPage->isOverfull && !pPage->needRelink ){
    u8 *pPrev;
................................................................................
  Pgno pgnoOld[NB];            /* Page numbers for each page in apOld[] */
  MemPage *apCopy[NB];         /* Private copies of apOld[] pages */
  MemPage *apNew[NB+1];        /* pPage and up to NB siblings after balancing */
  Pgno pgnoNew[NB+1];          /* Page numbers for each page in apNew[] */
  int idxDiv[NB];              /* Indices of divider cells in pParent */
  u8 *apDiv[NB];               /* Divider cells in pParent */
  u8 aTemp[NB][MX_CELL_SIZE];  /* Temporary holding area for apDiv[] */

  int cntNew[NB+1];            /* Index in aCell[] of cell after i-th page */
  int szNew[NB+1];             /* Combined size of cells place on i-th page */
  u8 *apCell[(MX_CELL+2)*NB];  /* All cells from pages being balanced */
  int szCell[(MX_CELL+2)*NB];  /* Local size of all cells */
  u8 aCopy[NB][MX_PAGE_SIZE+sizeof(MemPage)];  /* Space for apCopy[] */

  /* 
................................................................................
          if( pChild->nFree>=100 ){
            /* The child information will fit on the root page, so do the
            ** copy */
            zeroPage(pPage, pChild->aData[0]);
            resizeCellArray(pPage, pChild->nCell);
            for(i=0; i<pChild->nCell; i++){
              insertCell(pPage, i, pChild->aCell[i], 
                        cellSize(pChild, pChild->aCell[i]));
            }
            freePage(pChild);
            TRACE(("BALANCE: child %d transfer to page 1\n", pChild->pgno));
          }else{
            /* The child has more information that will fit on the root.
            ** The tree is already balanced.  Do nothing. */
            TRACE(("BALANCE: child %d will not fit on page 1\n", pChild->pgno));
................................................................................
      pT = apNew[i];
      pgnoNew[i] = pgnoNew[minI];
      apNew[i] = apNew[minI];
      pgnoNew[minI] = t;
      apNew[minI] = pT;
    }
  }










  /*
  ** Evenly distribute the data in apCell[] across the new pages.
  ** Insert divider cells into pParent as necessary.
  */
  j = 0;
  for(i=0; i<nNew; i++){
    MemPage *pNew = apNew[i];
    assert( pNew->pgno==pgnoNew[i] );
    resizeCellArray(pNew, cntNew[i] - j);
    while( j<cntNew[i] ){
      assert( pNew->nFree>=szCell[j] );
      insertCell(pNew, pNew->nCell, apCell[j], szCell[j]);
      j++;
    }
    assert( pNew->nCell>0 );
    assert( !pNew->isOverfull );
    relinkCellList(pNew);
    if( i<nNew-1 && j<nCell ){
      u8 *pCell = apCell[j];

      if( !pNew->leaf ){
        memcpy(&pNew->aData[6], &apCell[j][2], 4);

      }else{
        pCell -= 4;

      }
      insertCell(pParent, nxDiv, pCell, szCell[j]+leafCorrection);
      put4byte(&pParent->aCell[nxDiv][2], pNew->pgno);
      j++;
      nxDiv++;
    }
  }
  assert( j==nCell );
  if( (pageFlags & PTF_LEAF)==0 ){
................................................................................
    dropCell(pPage, pCur->idx, szOld);
  }else if( loc<0 && pPage->nCell>0 ){
    assert( pPage->leaf );
    pCur->idx++;
  }else{
    assert( pPage->leaf );
  }
  insertCell(pPage, pCur->idx, newCell, szNew);
  rc = balance(pPage);
  /* sqlite3BtreePageDump(pCur->pBt, pCur->pgnoRoot, 1); */
  /* fflush(stdout); */
  moveToRoot(pCur);
  return rc;
}

................................................................................
    ** next Cell after the one to be deleted is guaranteed to exist and
    ** to be a leaf so we can use it.
    */
    BtCursor leafCur;
    unsigned char *pNext;
    int szNext;
    int notUsed;
    unsigned char tempbuf[4];
    getTempCursor(pCur, &leafCur);
    rc = sqlite3BtreeNext(&leafCur, &notUsed);
    if( rc!=SQLITE_OK ){
      if( rc!=SQLITE_NOMEM ) rc = SQLITE_CORRUPT;
      return rc;
    }
    rc = sqlite3pager_write(leafCur.pPage->aData);
    if( rc ) return rc;
    TRACE(("DELETE: table=%d delete internal from %d replace from leaf %d\n",
       pCur->pgnoRoot, pPage->pgno, leafCur.pPage->pgno));
    dropCell(pPage, pCur->idx, cellSize(pPage, pCell));
    pNext = leafCur.pPage->aCell[leafCur.idx];
    szNext = cellSize(leafCur.pPage, pNext);
    memcpy(tempbuf, &pNext[-2], 4);
    put4byte(&pNext[-2], pgnoChild);
    insertCell(pPage, pCur->idx, &pNext[-4], szNext+4);

    rc = balance(pPage);
    if( rc ) return rc;
    memcpy(&pNext[-2], tempbuf, 4);
    dropCell(leafCur.pPage, leafCur.idx, szNext);
    rc = balance(leafCur.pPage);
    releaseTempCursor(&leafCur);
  }else{
    TRACE(("DELETE: table=%d delete from leaf %d\n",
       pCur->pgnoRoot, pPage->pgno));
    dropCell(pPage, pCur->idx, cellSize(pPage, pCell));







|







 







>











|
>







 







>



>
>
>
|
>
>
>
>
>
>
>







 







>
>
>
>







 







|
>
>
|







|
>
>
>
>
>
>












>
>
>
>
>
|







 







>







 







|







 







>
>
>
>
>
>
>
>
>












|







>

|
>


>

|







 







|







 







|













|
<
|
>


<







5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
...
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
....
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
....
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
....
2447
2448
2449
2450
2451
2452
2453
2454
2455
2456
2457
2458
2459
2460
2461
2462
2463
2464
2465
2466
2467
2468
2469
2470
2471
2472
2473
2474
2475
2476
2477
2478
2479
2480
2481
2482
2483
2484
2485
2486
2487
2488
2489
2490
2491
2492
2493
2494
2495
2496
....
2645
2646
2647
2648
2649
2650
2651
2652
2653
2654
2655
2656
2657
2658
2659
....
2705
2706
2707
2708
2709
2710
2711
2712
2713
2714
2715
2716
2717
2718
2719
....
2982
2983
2984
2985
2986
2987
2988
2989
2990
2991
2992
2993
2994
2995
2996
2997
2998
2999
3000
3001
3002
3003
3004
3005
3006
3007
3008
3009
3010
3011
3012
3013
3014
3015
3016
3017
3018
3019
3020
3021
3022
3023
3024
3025
3026
3027
3028
3029
3030
3031
3032
3033
....
3172
3173
3174
3175
3176
3177
3178
3179
3180
3181
3182
3183
3184
3185
3186
....
3228
3229
3230
3231
3232
3233
3234
3235
3236
3237
3238
3239
3240
3241
3242
3243
3244
3245
3246
3247
3248
3249

3250
3251
3252
3253

3254
3255
3256
3257
3258
3259
3260
** 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.122 2004/05/10 16:18: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.
................................................................................
**
** Algorithm:  Carve a piece off of the first freeblock that is
** nByte in size or that larger.
*/
static int allocateSpace(MemPage *pPage, int nByte){
  int addr, pc, hdr;
  int size;
  int nFrag;
  unsigned char *data;
#ifndef NDEBUG
  int cnt = 0;
#endif

  data = pPage->aData;
  assert( sqlite3pager_iswriteable(data) );
  assert( pPage->pBt );
  if( nByte<4 ) nByte = 4;
  if( pPage->nFree<nByte || pPage->isOverfull ) return 0;
  hdr = pPage->hdrOffset;
  nFrag = data[hdr+5];
  if( nFrag>=60 || nFrag>pPage->nFree-nByte ){
    defragmentPage(pPage);
  }
  addr = hdr+1;
  pc = get2byte(&data[addr]);
  assert( addr<pc );
  assert( pc<=pPage->pBt->pageSize-4 );
  while( (size = get2byte(&data[pc+2]))<nByte ){
................................................................................
** in an error.
**
** This will release the write lock on the database file.  If there
** are no active cursors, it also releases the read lock.
*/
int sqlite3BtreeRollback(Btree *pBt){
  int rc;
  MemPage *pPage1;
  if( pBt->inTrans==0 ) return SQLITE_OK;
  pBt->inTrans = 0;
  pBt->inStmt = 0;
  if( pBt->readOnly ){
    rc = SQLITE_OK;
  }else{
    rc = sqlite3pager_rollback(pBt->pPager);
    /* The rollback may have destroyed the pPage1->aData value.  So
    ** call getPage() on page 1 again to make sure pPage1->aData is
    ** set correctly. */
    if( getPage(pBt, 1, &pPage1)==SQLITE_OK ){
      releasePage(pPage1);
    }
  }
  invalidateCursors(pBt);
  unlockBtreeIfUnused(pBt);
  return rc;
}

/*
** Set the checkpoint for the current transaction.  The checkpoint serves
................................................................................
  }
  pCur = sqliteMalloc( sizeof(*pCur) );
  if( pCur==0 ){
    rc = SQLITE_NOMEM;
    goto create_cursor_exception;
  }
  pCur->pgnoRoot = (Pgno)iTable;
  if( iTable==1 && sqlite3pager_pagecount(pBt->pPager)==0 ){
    rc = SQLITE_EMPTY;
    goto create_cursor_exception;
  }
  rc = getAndInitPage(pBt, pCur->pgnoRoot, &pCur->pPage, 0);
  if( rc!=SQLITE_OK ){
    goto create_cursor_exception;
  }
  pCur->xCompare = xCmp ? xCmp : dfltCompare;
  pCur->pArg = pArg;
  pCur->pBt = pBt;
................................................................................
}

/*
** Insert a new cell on pPage at cell index "i".  pCell points to the
** content of the cell.
**
** If the cell content will fit on the page, then put it there.  If it
** will not fit and pTemp is not NULL, then make a copy of the content
** into pTemp, set pPage->aCell[i] point to pTemp, and set pPage->isOverfull.
** If the content will not fit and pTemp is NULL, then make pPage->aCell[i]
** point to pCell and set pPage->isOverfull.
**
** Try to maintain the integrity of the linked list of cells.  But if
** the cell being inserted does not fit on the page, this will not be
** possible.  If the linked list is not maintained, then just update
** pPage->aCell[] and set the pPage->needRelink flag so that we will
** know to rebuild the linked list later.
*/
static void insertCell(
  MemPage *pPage,   /* Page into which we are copying */
  int i,            /* Which cell on pPage to insert after */
  u8 *pCell,        /* Text of the new cell to insert */
  int sz,           /* Bytes of data in pCell */
  u8 *pTemp         /* Temp storage space for pCell, if needed */
){
  int idx, j;
  assert( i>=0 && i<=pPage->nCell );
  assert( sz==cellSize(pPage, pCell) );
  assert( sqlite3pager_iswriteable(pPage->aData) );
  idx = pPage->needRelink ? 0 : allocateSpace(pPage, sz);
  resizeCellArray(pPage, pPage->nCell+1);
  for(j=pPage->nCell; j>i; j--){
    pPage->aCell[j] = pPage->aCell[j-1];
  }
  pPage->nCell++;
  if( idx<=0 ){
    pPage->isOverfull = 1;
    if( pTemp ){
      memcpy(pTemp, pCell, sz);
    }else{
      pTemp = pCell;
    }
    pPage->aCell[i] = pTemp;
  }else{
    u8 *data = pPage->aData;
    memcpy(&data[idx], pCell, sz);
    pPage->aCell[i] = &data[idx];
  }
  if( !pPage->isOverfull && !pPage->needRelink ){
    u8 *pPrev;
................................................................................
  Pgno pgnoOld[NB];            /* Page numbers for each page in apOld[] */
  MemPage *apCopy[NB];         /* Private copies of apOld[] pages */
  MemPage *apNew[NB+1];        /* pPage and up to NB siblings after balancing */
  Pgno pgnoNew[NB+1];          /* Page numbers for each page in apNew[] */
  int idxDiv[NB];              /* Indices of divider cells in pParent */
  u8 *apDiv[NB];               /* Divider cells in pParent */
  u8 aTemp[NB][MX_CELL_SIZE];  /* Temporary holding area for apDiv[] */
  u8 aInsBuf[NB][MX_CELL_SIZE];/* Space to hold dividers cells during insert */
  int cntNew[NB+1];            /* Index in aCell[] of cell after i-th page */
  int szNew[NB+1];             /* Combined size of cells place on i-th page */
  u8 *apCell[(MX_CELL+2)*NB];  /* All cells from pages being balanced */
  int szCell[(MX_CELL+2)*NB];  /* Local size of all cells */
  u8 aCopy[NB][MX_PAGE_SIZE+sizeof(MemPage)];  /* Space for apCopy[] */

  /* 
................................................................................
          if( pChild->nFree>=100 ){
            /* The child information will fit on the root page, so do the
            ** copy */
            zeroPage(pPage, pChild->aData[0]);
            resizeCellArray(pPage, pChild->nCell);
            for(i=0; i<pChild->nCell; i++){
              insertCell(pPage, i, pChild->aCell[i], 
                        cellSize(pChild, pChild->aCell[i]), 0);
            }
            freePage(pChild);
            TRACE(("BALANCE: child %d transfer to page 1\n", pChild->pgno));
          }else{
            /* The child has more information that will fit on the root.
            ** The tree is already balanced.  Do nothing. */
            TRACE(("BALANCE: child %d will not fit on page 1\n", pChild->pgno));
................................................................................
      pT = apNew[i];
      pgnoNew[i] = pgnoNew[minI];
      apNew[i] = apNew[minI];
      pgnoNew[minI] = t;
      apNew[minI] = pT;
    }
  }
  TRACE(("BALANCE: old: %d %d %d  new: %d %d %d %d\n",
    pgnoOld[0], 
    nOld>=2 ? pgnoOld[1] : 0,
    nOld>=3 ? pgnoOld[2] : 0,
    pgnoNew[0],
    nNew>=2 ? pgnoNew[1] : 0,
    nNew>=3 ? pgnoNew[2] : 0,
    nNew>=4 ? pgnoNew[3] : 0));


  /*
  ** Evenly distribute the data in apCell[] across the new pages.
  ** Insert divider cells into pParent as necessary.
  */
  j = 0;
  for(i=0; i<nNew; i++){
    MemPage *pNew = apNew[i];
    assert( pNew->pgno==pgnoNew[i] );
    resizeCellArray(pNew, cntNew[i] - j);
    while( j<cntNew[i] ){
      assert( pNew->nFree>=szCell[j] );
      insertCell(pNew, pNew->nCell, apCell[j], szCell[j], 0);
      j++;
    }
    assert( pNew->nCell>0 );
    assert( !pNew->isOverfull );
    relinkCellList(pNew);
    if( i<nNew-1 && j<nCell ){
      u8 *pCell = apCell[j];
      u8 *pTemp;
      if( !pNew->leaf ){
        memcpy(&pNew->aData[6], pCell+2, 4);
        pTemp = 0;
      }else{
        pCell -= 4;
        pTemp = aInsBuf[i];
      }
      insertCell(pParent, nxDiv, pCell, szCell[j]+leafCorrection, pTemp);
      put4byte(&pParent->aCell[nxDiv][2], pNew->pgno);
      j++;
      nxDiv++;
    }
  }
  assert( j==nCell );
  if( (pageFlags & PTF_LEAF)==0 ){
................................................................................
    dropCell(pPage, pCur->idx, szOld);
  }else if( loc<0 && pPage->nCell>0 ){
    assert( pPage->leaf );
    pCur->idx++;
  }else{
    assert( pPage->leaf );
  }
  insertCell(pPage, pCur->idx, newCell, szNew, 0);
  rc = balance(pPage);
  /* sqlite3BtreePageDump(pCur->pBt, pCur->pgnoRoot, 1); */
  /* fflush(stdout); */
  moveToRoot(pCur);
  return rc;
}

................................................................................
    ** next Cell after the one to be deleted is guaranteed to exist and
    ** to be a leaf so we can use it.
    */
    BtCursor leafCur;
    unsigned char *pNext;
    int szNext;
    int notUsed;
    unsigned char tempCell[MX_CELL_SIZE];
    getTempCursor(pCur, &leafCur);
    rc = sqlite3BtreeNext(&leafCur, &notUsed);
    if( rc!=SQLITE_OK ){
      if( rc!=SQLITE_NOMEM ) rc = SQLITE_CORRUPT;
      return rc;
    }
    rc = sqlite3pager_write(leafCur.pPage->aData);
    if( rc ) return rc;
    TRACE(("DELETE: table=%d delete internal from %d replace from leaf %d\n",
       pCur->pgnoRoot, pPage->pgno, leafCur.pPage->pgno));
    dropCell(pPage, pCur->idx, cellSize(pPage, pCell));
    pNext = leafCur.pPage->aCell[leafCur.idx];
    szNext = cellSize(leafCur.pPage, pNext);
    assert( sizeof(tempCell)>=szNext+4 );

    insertCell(pPage, pCur->idx, pNext-4, szNext+4, tempCell);
    put4byte(pPage->aCell[pCur->idx]+2, pgnoChild);
    rc = balance(pPage);
    if( rc ) return rc;

    dropCell(leafCur.pPage, leafCur.idx, szNext);
    rc = balance(leafCur.pPage);
    releaseTempCursor(&leafCur);
  }else{
    TRACE(("DELETE: table=%d delete from leaf %d\n",
       pCur->pgnoRoot, pPage->pgno));
    dropCell(pPage, pCur->idx, cellSize(pPage, pCell));

Changes to src/sqlite.h.in.

8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
...
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
...
917
918
919
920
921
922
923
924
925
926
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This header file defines the interface that the SQLite library
** presents to client programs.
**
** @(#) $Id: sqlite.h.in,v 1.62 2004/05/10 10:34:52 danielk1977 Exp $
*/
#ifndef _SQLITE_H_
#define _SQLITE_H_
#include <stdarg.h>     /* Needed for the definition of va_list */

/*
** Make sure we can call this stuff from C++.
................................................................................
#define SQLITE_INTERNAL     2   /* An internal logic error in SQLite */
#define SQLITE_PERM         3   /* Access permission denied */
#define SQLITE_ABORT        4   /* Callback routine requested an abort */
#define SQLITE_BUSY         5   /* The database file is locked */
#define SQLITE_LOCKED       6   /* A table in the database is locked */
#define SQLITE_NOMEM        7   /* A malloc() failed */
#define SQLITE_READONLY     8   /* Attempt to write a readonly database */
#define SQLITE_INTERRUPT    9   /* Operation terminated by sqlite3_interrupt() */
#define SQLITE_IOERR       10   /* Some kind of disk I/O error occurred */
#define SQLITE_CORRUPT     11   /* The database disk image is malformed */
#define SQLITE_NOTFOUND    12   /* (Internal Only) Table or record not found */
#define SQLITE_FULL        13   /* Insertion failed because database is full */
#define SQLITE_CANTOPEN    14   /* Unable to open the database file */
#define SQLITE_PROTOCOL    15   /* Database lock protocol error */
#define SQLITE_EMPTY       16   /* (Internal Only) Database table is empty */
#define SQLITE_SCHEMA      17   /* The database schema changed */
#define SQLITE_TOOBIG      18   /* Too much data for one row of a table */
#define SQLITE_CONSTRAINT  19   /* Abort due to contraint violation */
#define SQLITE_MISMATCH    20   /* Data type mismatch */
#define SQLITE_MISUSE      21   /* Library used incorrectly */
#define SQLITE_NOLFS       22   /* Uses OS features not supported on host */
#define SQLITE_AUTH        23   /* Authorization denied */
................................................................................

#endif

#ifdef __cplusplus
}  /* End of the 'extern "C"' block */
#endif
#endif










|







 







|






|







 







<
<
<
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
...
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
...
917
918
919
920
921
922
923



**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This header file defines the interface that the SQLite library
** presents to client programs.
**
** @(#) $Id: sqlite.h.in,v 1.63 2004/05/10 16:18:48 drh Exp $
*/
#ifndef _SQLITE_H_
#define _SQLITE_H_
#include <stdarg.h>     /* Needed for the definition of va_list */

/*
** Make sure we can call this stuff from C++.
................................................................................
#define SQLITE_INTERNAL     2   /* An internal logic error in SQLite */
#define SQLITE_PERM         3   /* Access permission denied */
#define SQLITE_ABORT        4   /* Callback routine requested an abort */
#define SQLITE_BUSY         5   /* The database file is locked */
#define SQLITE_LOCKED       6   /* A table in the database is locked */
#define SQLITE_NOMEM        7   /* A malloc() failed */
#define SQLITE_READONLY     8   /* Attempt to write a readonly database */
#define SQLITE_INTERRUPT    9   /* Operation terminated by sqlite3_interrupt()*/
#define SQLITE_IOERR       10   /* Some kind of disk I/O error occurred */
#define SQLITE_CORRUPT     11   /* The database disk image is malformed */
#define SQLITE_NOTFOUND    12   /* (Internal Only) Table or record not found */
#define SQLITE_FULL        13   /* Insertion failed because database is full */
#define SQLITE_CANTOPEN    14   /* Unable to open the database file */
#define SQLITE_PROTOCOL    15   /* Database lock protocol error */
#define SQLITE_EMPTY       16   /* Database is empty */
#define SQLITE_SCHEMA      17   /* The database schema changed */
#define SQLITE_TOOBIG      18   /* Too much data for one row of a table */
#define SQLITE_CONSTRAINT  19   /* Abort due to contraint violation */
#define SQLITE_MISMATCH    20   /* Data type mismatch */
#define SQLITE_MISUSE      21   /* Library used incorrectly */
#define SQLITE_NOLFS       22   /* Uses OS features not supported on host */
#define SQLITE_AUTH        23   /* Authorization denied */
................................................................................

#endif

#ifdef __cplusplus
}  /* End of the 'extern "C"' block */
#endif
#endif



Changes to src/test3.c.

9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
..
39
40
41
42
43
44
45

46
47
48
49
50
51
52
**    May you share freely, never taking more than you give.
**
*************************************************************************
** Code for testing the btree.c module in SQLite.  This code
** is not included in the SQLite library.  It is used for automated
** testing of the SQLite library.
**
** $Id: test3.c,v 1.33 2004/05/09 20:40:11 drh Exp $
*/
#include "sqliteInt.h"
#include "pager.h"
#include "btree.h"
#include "tcl.h"
#include <stdlib.h>
#include <string.h>
................................................................................
    case SQLITE_INTERRUPT:  zName = "SQLITE_INTERRUPT";   break;
    case SQLITE_IOERR:      zName = "SQLITE_IOERR";       break;
    case SQLITE_CORRUPT:    zName = "SQLITE_CORRUPT";     break;
    case SQLITE_NOTFOUND:   zName = "SQLITE_NOTFOUND";    break;
    case SQLITE_FULL:       zName = "SQLITE_FULL";        break;
    case SQLITE_CANTOPEN:   zName = "SQLITE_CANTOPEN";    break;
    case SQLITE_PROTOCOL:   zName = "SQLITE_PROTOCOL";    break;

    default:                zName = "SQLITE_Unknown";     break;
  }
  return zName;
}

/*
** Usage:   btree_open FILENAME NCACHE FLAGS







|







 







>







9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
..
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
**    May you share freely, never taking more than you give.
**
*************************************************************************
** Code for testing the btree.c module in SQLite.  This code
** is not included in the SQLite library.  It is used for automated
** testing of the SQLite library.
**
** $Id: test3.c,v 1.34 2004/05/10 16:18:48 drh Exp $
*/
#include "sqliteInt.h"
#include "pager.h"
#include "btree.h"
#include "tcl.h"
#include <stdlib.h>
#include <string.h>
................................................................................
    case SQLITE_INTERRUPT:  zName = "SQLITE_INTERRUPT";   break;
    case SQLITE_IOERR:      zName = "SQLITE_IOERR";       break;
    case SQLITE_CORRUPT:    zName = "SQLITE_CORRUPT";     break;
    case SQLITE_NOTFOUND:   zName = "SQLITE_NOTFOUND";    break;
    case SQLITE_FULL:       zName = "SQLITE_FULL";        break;
    case SQLITE_CANTOPEN:   zName = "SQLITE_CANTOPEN";    break;
    case SQLITE_PROTOCOL:   zName = "SQLITE_PROTOCOL";    break;
    case SQLITE_EMPTY:      zName = "SQLITE_EMPTY";       break;
    default:                zName = "SQLITE_Unknown";     break;
  }
  return zName;
}

/*
** Usage:   btree_open FILENAME NCACHE FLAGS

Changes to test/btree2.test.

7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
..
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
...
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
...
184
185
186
187
188
189
190


























191
192
193
194
195
196
197
...
281
282
283
284
285
286
287

288
289
290
291
292
293
294
...
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this script is btree database backend
#
# $Id: btree2.test,v 1.12 2004/05/09 20:40:11 drh Exp $


set testdir [file dirname $argv0]
source $testdir/tester.tcl

if {[info commands btree_open]!=""} {

................................................................................
#
#   1.  The descriptor table always contains 2 enters.  An entry keyed by
#       "N" is the number of elements in the foreground and background tables
#       combined.  The entry keyed by "L" is the number of digits in the keys
#       for foreground and background tables.
#
#   2.  The union of the foreground an background tables consists of N entries
#       where each entry an L-digit key.  (Actually, some keys can be longer 
#       than L characters, but they always start with L digits.)  The keys
#       cover all integers between 1 and N.  Whenever an entry is added to
#       the foreground it is removed form the background and vice versa.
#
#   3.  Some entries in the foreground and background tables have keys that
#       begin with an L-digit number but are followed by additional characters.
#       For each such entry there is a corresponding entry in the long key
................................................................................
  for {set i 1} {$i<=$N} {incr i} {
    set key [btree_key $::c3]
    if {[scan $key %d k]<1} {set k 0}
    if {$k!=$i} {
      set key [btree_key $::c4]
      if {[scan $key %d k]<1} {set k 0}
      if {$k!=$i} {
        # puts "MISSING $i"
        # puts {Page 3:}; btree_page_dump $::b 3
        # puts {Page 4:}; btree_page_dump $::b 4
        # exit
        return "Key $i is missing from both foreground and background"
      }
      set data [btree_data $::c4]
      btree_next $::c4
    } else {
      set data [btree_data $::c3]
      btree_next $::c3
................................................................................
              Is [string length $data] but should be $datalen"
    }
    if {[make_payload $k $L $datalen]!=$data} {
      return "Entry $i has an incorrect data"
    }
  }
}



























# Make random changes to the database such that each change preserves
# the invariants.  The number of changes is $n*N where N is the parameter
# from the descriptor table.  Each changes begins with a random key.
# the entry with that key is put in the foreground table with probability
# $I and it is put in background with probability (1.0-$I).  It gets
# a long key with probability $K and long data with probability $D.  
................................................................................
      if {$ck!=""} {
         puts "\nSANITY CHECK FAILED!\n$ck"
         exit
       }
    }
  }
}


# Repeat this test sequence on database of various sizes
#
set testno 2
foreach {N L} {
  10 2
  50 2
................................................................................
    } $hash
    btree_begin_transaction $::b
    set ::c2 [btree_cursor $::b 2 1]
    set ::c3 [btree_cursor $::b 3 1]
    set ::c4 [btree_cursor $::b 4 1]
    set ::c5 [btree_cursor $::b 5 1]
    set ::c6 [btree_cursor $::b 6 1]
#if {$testid=="btree2-3.8.4"} {set btree_trace 1}
    do_test $testid.5 [subst {
      random_changes $n $I $K $D
    }] {}
    do_test $testid.6 {
      check_invariants
    } {}
    do_test $testid.7 {







|







 







|







 







<
<
<
<







 







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







 







>







 







<







7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
..
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
...
145
146
147
148
149
150
151




152
153
154
155
156
157
158
...
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
...
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
...
416
417
418
419
420
421
422

423
424
425
426
427
428
429
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this script is btree database backend
#
# $Id: btree2.test,v 1.13 2004/05/10 16:18:48 drh Exp $


set testdir [file dirname $argv0]
source $testdir/tester.tcl

if {[info commands btree_open]!=""} {

................................................................................
#
#   1.  The descriptor table always contains 2 enters.  An entry keyed by
#       "N" is the number of elements in the foreground and background tables
#       combined.  The entry keyed by "L" is the number of digits in the keys
#       for foreground and background tables.
#
#   2.  The union of the foreground an background tables consists of N entries
#       where each entry has an L-digit key. (Actually, some keys can be longer 
#       than L characters, but they always start with L digits.)  The keys
#       cover all integers between 1 and N.  Whenever an entry is added to
#       the foreground it is removed form the background and vice versa.
#
#   3.  Some entries in the foreground and background tables have keys that
#       begin with an L-digit number but are followed by additional characters.
#       For each such entry there is a corresponding entry in the long key
................................................................................
  for {set i 1} {$i<=$N} {incr i} {
    set key [btree_key $::c3]
    if {[scan $key %d k]<1} {set k 0}
    if {$k!=$i} {
      set key [btree_key $::c4]
      if {[scan $key %d k]<1} {set k 0}
      if {$k!=$i} {




        return "Key $i is missing from both foreground and background"
      }
      set data [btree_data $::c4]
      btree_next $::c4
    } else {
      set data [btree_data $::c3]
      btree_next $::c3
................................................................................
              Is [string length $data] but should be $datalen"
    }
    if {[make_payload $k $L $datalen]!=$data} {
      return "Entry $i has an incorrect data"
    }
  }
}

# Look at all elements in both the foreground and background tables.
# Make sure the key is always the same as the prefix of the data.
#
# This routine was used for hunting bugs.  It is not a part of standard
# tests.
#
proc check_data {n key} {
  global c3 c4
  incr n -1
  foreach c [list $c3 $c4] {
    btree_first $c  ;# move_to $c $key
    set cnt 0
    while {![btree_eof $c]} {
      set key [btree_key $c]
      set data [btree_data $c]
      if {[string range $key 0 $n] ne [string range $data 0 $n]} {
        puts "key=[list $key] data=[list $data] n=$n"
        puts "cursor info = [btree_cursor_info $c]"
        btree_page_dump $::b [lindex [btree_cursor_info $c] 0]
        exit
      }
      btree_next $c
    }
  }
}

# Make random changes to the database such that each change preserves
# the invariants.  The number of changes is $n*N where N is the parameter
# from the descriptor table.  Each changes begins with a random key.
# the entry with that key is put in the foreground table with probability
# $I and it is put in background with probability (1.0-$I).  It gets
# a long key with probability $K and long data with probability $D.  
................................................................................
      if {$ck!=""} {
         puts "\nSANITY CHECK FAILED!\n$ck"
         exit
       }
    }
  }
}
set btree_trace 0

# Repeat this test sequence on database of various sizes
#
set testno 2
foreach {N L} {
  10 2
  50 2
................................................................................
    } $hash
    btree_begin_transaction $::b
    set ::c2 [btree_cursor $::b 2 1]
    set ::c3 [btree_cursor $::b 3 1]
    set ::c4 [btree_cursor $::b 4 1]
    set ::c5 [btree_cursor $::b 5 1]
    set ::c6 [btree_cursor $::b 6 1]

    do_test $testid.5 [subst {
      random_changes $n $I $K $D
    }] {}
    do_test $testid.6 {
      check_invariants
    } {}
    do_test $testid.7 {