/ Check-in [b8f70d17]
Login

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

Overview
Comment:Implement a B+tree option (all data stored on leaves). (CVS 1365)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:b8f70d17f06531269caa0a127efb2d25ad0f3e1c
User & Date: drh 2004-05-12 19:18:16
Context
2004-05-12
21:11
Fix a problem with B+trees. (CVS 1366) check-in: 64a75c4c user: drh tags: trunk
19:18
Implement a B+tree option (all data stored on leaves). (CVS 1365) check-in: b8f70d17 user: drh tags: trunk
15:15
Btree uses signed integers for the rowid. The intToKey() and keyToInt() macros are now no-ops. (CVS 1364) check-in: fb3c8030 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
...
192
193
194
195
196
197
198

199
200
201
202
203
204
205
206
207
...
212
213
214
215
216
217
218
219


220
221
222
223
224
225
226
...
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
...
398
399
400
401
402
403
404

405


406
407
408
409
410
411
412
...
685
686
687
688
689
690
691
692
693

694

695
696
697
698
699
700
701
...
759
760
761
762
763
764
765
766
767
768



769
770
771
772
773
774
775
....
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
....
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
....
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
....
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
....
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
....
1973
1974
1975
1976
1977
1978
1979



1980
1981
1982

1983
1984
1985
1986
1987
1988
1989
....
2027
2028
2029
2030
2031
2032
2033

2034
2035
2036
2037
2038
2039
2040
....
2053
2054
2055
2056
2057
2058
2059



2060


2061
2062
2063
2064
2065
2066
2067
....
2096
2097
2098
2099
2100
2101
2102



2103

2104
2105
2106
2107
2108
2109
2110
....
2331
2332
2333
2334
2335
2336
2337
2338
2339
2340
2341
2342
2343
2344
2345
2346
2347
2348
2349
2350
2351
....
2683
2684
2685
2686
2687
2688
2689

2690
2691
2692
2693
2694
2695
2696
....
2709
2710
2711
2712
2713
2714
2715
2716
2717
2718
2719
2720
2721
2722
2723
....
2908
2909
2910
2911
2912
2913
2914

2915
2916
2917
2918
2919
2920
2921
2922




2923
2924
2925
2926
2927
2928
2929
2930
2931
2932
2933
2934
2935
2936
2937

2938
2939
2940
2941
2942
2943
2944
....
2950
2951
2952
2953
2954
2955
2956

2957
2958
2959
2960
2961
2962
2963
....
3060
3061
3062
3063
3064
3065
3066
3067
3068



3069
3070
3071









3072
3073
3074
3075
3076
3077
3078
3079
3080
3081
3082
3083
....
3196
3197
3198
3199
3200
3201
3202

3203
3204
3205
3206
3207
3208
3209
....
3280
3281
3282
3283
3284
3285
3286

3287
3288
3289
3290
3291
3292
3293
....
3514
3515
3516
3517
3518
3519
3520
3521
3522

3523

3524
3525
3526
3527
3528
3529
3530
** 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.128 2004/05/12 15:15:47 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.
................................................................................

/*
** Page type flags.  An ORed combination of these flags appear as the
** first byte of every BTree page.
*/
#define PTF_INTKEY    0x01
#define PTF_ZERODATA  0x02

#define PTF_LEAF      0x04
/* Idea for the future:  PTF_LEAFDATA */

/*
** As each page of the file is loaded into memory, an instance of the following
** structure is appended and initialized to zero.  This structure stores
** information about the page that is decoded from the raw file page.
**
** The pParent field points back to the parent page.  This allows us to
................................................................................
struct MemPage {
  u32 notUsed;
  u8 isInit;                     /* True if previously initialized */
  u8 idxShift;                   /* True if Cell indices have changed */
  u8 isOverfull;                 /* Some aCell[] do not fit on page */
  u8 intKey;                     /* True if intkey flag is set */
  u8 leaf;                       /* True if leaf flag is set */
  u8 zeroData;                   /* True if zero data flag is set */


  u8 hdrOffset;                  /* 100 for page 1.  0 otherwise */
  u8 needRelink;                 /* True if need to run relinkCellList() */
  int idxParent;                 /* Index in pParent->aCell[] of this node */
  int nFree;                     /* Number of free bytes on the page */
  int nCell;                     /* Number of entries on this page */
  int nCellAlloc;                /* Number of slots allocated in aCell[] */
  unsigned char **aCell;         /* Pointer to start of each cell */
................................................................................
){
  int n;
  if( pPage->leaf ){
    n = 2;
  }else{
    n = 6;
  }
  if( pPage->zeroData ){
    *pnData = 0;
  }else{
    n += getVarint(&pCell[n], pnData);
  }
  n += getVarint(&pCell[n], (u64*)pnKey);
  *pnHeader = n;
}

/*
** Compute the total number of bytes that a Cell needs on the main
................................................................................
  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->intKey == ((c & PTF_INTKEY)!=0) );


  }
  data = pPage->aData;
  memset(used, 0, pageSize);
  for(i=0; i<hdr+10-pPage->leaf*4; i++) used[i] = 1;
  nFree = 0;
  pc = get2byte(&data[hdr+1]);
  while( pc ){
................................................................................
  }
  if( pPage->isInit ) return SQLITE_OK;
  pPage->nCell = pPage->nCellAlloc = 0;
  assert( pPage->hdrOffset==(pPage->pgno==1 ? 100 : 0) );
  hdr = pPage->hdrOffset;
  data = pPage->aData;
  c = data[hdr];
  pPage->intKey = (c & PTF_INTKEY)!=0;
  pPage->zeroData = (c & PTF_ZERODATA)!=0;

  pPage->leaf = (c & PTF_LEAF)!=0;

  pPage->isOverfull = 0;
  pPage->needRelink = 0;
  pPage->idxShift = 0;
  pageSize = pPage->pBt->pageSize;

  /* Initialize the cell count and cell pointers */
  pc = get2byte(&data[hdr+3]);
................................................................................
  put2byte(&data[hdr+1], first);
  put2byte(&data[first+2], pBt->pageSize - first);
  sqliteFree(pPage->aCell);
  pPage->aCell = 0;
  pPage->nCell = 0;
  pPage->nCellAlloc = 0;
  pPage->nFree = pBt->pageSize - first;
  pPage->intKey = (flags & PTF_INTKEY)!=0;
  pPage->leaf = (flags & PTF_LEAF)!=0;
  pPage->zeroData = (flags & PTF_ZERODATA)!=0;



  pPage->hdrOffset = hdr;
  pPage->isOverfull = 0;
  pPage->needRelink = 0;
  pPage->idxShift = 0;
  pPage->isInit = 1;
  pageIntegrity(pPage);
}
................................................................................
  if( rc ) return rc;
  memcpy(data, zMagicHeader, sizeof(zMagicHeader));
  assert( sizeof(zMagicHeader)==16 );
  put2byte(&data[16], SQLITE_PAGE_SIZE);
  data[18] = 1;
  data[19] = 1;
  put2byte(&data[22], (SQLITE_PAGE_SIZE-10)/4-12);
  zeroPage(pP1, PTF_INTKEY|PTF_LEAF);
  return SQLITE_OK;
}

/*
** Attempt to start a new transaction.
**
** A transaction must be started before attempting any changes
................................................................................
    assert( pPage!=0 );
    assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
    cell = pPage->aCell[pCur->idx];
    cell += 2;   /* Skip the offset to the next cell */
    if( !pPage->leaf ){
      cell += 4;  /* Skip the child pointer */
    }
    if( !pPage->zeroData ){
      while( (0x80&*(cell++))!=0 ){}  /* Skip the data size number */
    }
    getVarint(cell, pSize);
  }
  return SQLITE_OK;
}

................................................................................
  if( !pCur->isValid ){
    return pCur->status ? pCur->status : SQLITE_INTERNAL;
  }
  pPage = pCur->pPage;
  assert( pPage!=0 );
  assert( pPage->isInit );
  pageIntegrity(pPage);
  if( pPage->zeroData ){
    *pSize = 0;
  }else{
    assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
    cell = pPage->aCell[pCur->idx];
    cell += 2;   /* Skip the offset to the next cell */
    if( !pPage->leaf ){
      cell += 4;  /* Skip the child pointer */
................................................................................
  pageIntegrity(pPage);
  assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
  aPayload = pPage->aCell[pCur->idx];
  aPayload += 2;  /* Skip the next cell index */
  if( !pPage->leaf ){
    aPayload += 4;  /* Skip the child pointer */
  }
  if( pPage->zeroData ){
    nData = 0;
  }else{
    aPayload += getVarint(aPayload, &nData);
  }
  aPayload += getVarint(aPayload, (u64*)&nKey);
  if( pPage->intKey ){
    nKey = 0;
  }
  assert( offset>=0 );
  if( skipKey ){
................................................................................
  pageIntegrity(pPage);
  assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
  aPayload = pPage->aCell[pCur->idx];
  aPayload += 2;  /* Skip the next cell index */
  if( !pPage->leaf ){
    aPayload += 4;  /* Skip the child pointer */
  }
  if( pPage->zeroData ){
    nData = 0;
  }else{
    aPayload += getVarint(aPayload, &nData);
  }
  aPayload += getVarint(aPayload, (u64*)&nKey);
  if( pPage->intKey ){
    nKey = 0;
  }
  maxLocal = pBt->maxLocal;
  if( skipKey ){
................................................................................
        if( pCellKey==0 ) return SQLITE_NOMEM;
        rc = sqlite3BtreeKey(pCur, 0, nCellKey, pCellKey);
        c = pCur->xCompare(pCur->pArg, nCellKey, pCellKey, nKey, pKey);
        sqliteFree(pCellKey);
        if( rc ) return rc;
      }
      if( c==0 ){



        pCur->iMatch = c;
        if( pRes ) *pRes = 0;
        return SQLITE_OK;

      }
      if( c<0 ){
        lwr = pCur->idx+1;
      }else{
        upr = pCur->idx-1;
      }
    }
................................................................................
** successful then set *pRes=0.  If the cursor
** was already pointing to the last entry in the database before
** this routine was called, then set *pRes=1.
*/
int sqlite3BtreeNext(BtCursor *pCur, int *pRes){
  int rc;
  MemPage *pPage = pCur->pPage;

  assert( pRes!=0 );
  if( pCur->isValid==0 ){
    *pRes = 1;
    return SQLITE_OK;
  }
  assert( pPage->isInit );
  assert( pCur->idx<pPage->nCell );
................................................................................
        pCur->isValid = 0;
        return SQLITE_OK;
      }
      moveToParent(pCur);
      pPage = pCur->pPage;
    }while( pCur->idx>=pPage->nCell );
    *pRes = 0;



    return SQLITE_OK;


  }
  *pRes = 0;
  if( pPage->leaf ){
    return SQLITE_OK;
  }
  rc = moveToLeftmost(pCur);
  return rc;
................................................................................
        *pRes = 1;
        return SQLITE_OK;
      }
      moveToParent(pCur);
      pPage = pCur->pPage;
    }
    pCur->idx--;



    rc = SQLITE_OK;

  }
  *pRes = 0;
  return rc;
}

/*
** The TRACE macro will print high-level status information about the
................................................................................
  int nHeader;

  /* Fill in the header. */
  nHeader = 2;
  if( !pPage->leaf ){
    nHeader += 4;
  }
  if( !pPage->zeroData ){
    nHeader += putVarint(&pCell[nHeader], nData);
  }
  nHeader += putVarint(&pCell[nHeader], *(u64*)&nKey);
  
  /* Fill in the payload */
  if( pPage->zeroData ){
    nData = 0;
  }
  nPayload = nData;
  if( pPage->intKey ){
    pSrc = pData;
    nSrc = nData;
    nData = 0;
................................................................................
  int nNew;                    /* Number of pages in apNew[] */
  int nDiv;                    /* Number of cells in apDiv[] */
  int i, j, k;                 /* Loop counters */
  int idx;                     /* Index of pPage in pParent->aCell[] */
  int nxDiv;                   /* Next divider slot in pParent->aCell[] */
  int rc;                      /* The return code */
  int leafCorrection;          /* 4 if pPage is a leaf.  0 if not */

  int usableSpace;             /* Bytes in pPage beyond the header */
  int pageFlags;               /* Value of pPage->aData[0] */
  int subtotal;                /* Subtotal of bytes in cells on one page */
  MemPage *extraUnref = 0;     /* Unref this page if not zero */
  MemPage *apOld[NB];          /* pPage and up to two siblings */
  Pgno pgnoOld[NB];            /* Page numbers for each page in apOld[] */
  MemPage *apCopy[NB];         /* Private copies of apOld[] pages */
................................................................................
  /* 
  ** Return without doing any work if pPage is neither overfull nor
  ** underfull.
  */
  assert( pPage->isInit );
  assert( sqlite3pager_iswriteable(pPage->aData) );
  pBt = pPage->pBt;
  if( !pPage->isOverfull && pPage->nFree<pBt->pageSize/2 && pPage->nCell>=2){
    relinkCellList(pPage);
    return SQLITE_OK;
  }

  /*
  ** Find the parent of the page to be balanced.  If there is no parent,
  ** it means this page is the root page and special rules apply.
................................................................................
  ** into aTemp[].  In this wall, all cells in apCell[] are without
  ** child pointers.  If siblings are not leaves, then all cell in
  ** apCell[] include child pointers.  Either way, all cells in apCell[]
  ** are alike.
  */
  nCell = 0;
  leafCorrection = pPage->leaf*4;

  for(i=0; i<nOld; i++){
    MemPage *pOld = apCopy[i];
    for(j=0; j<pOld->nCell; j++){
      apCell[nCell] = pOld->aCell[j];
      szCell[nCell] = cellSize(pOld, apCell[nCell]);
      nCell++;
    }
    if( i<nOld-1 ){




      szCell[nCell] = cellSize(pParent, apDiv[i]);
      memcpy(aTemp[i], apDiv[i], szCell[nCell]);
      apCell[nCell] = &aTemp[i][leafCorrection];
      dropCell(pParent, nxDiv, szCell[nCell]);
      szCell[nCell] -= leafCorrection;
      assert( get4byte(&aTemp[i][2])==pgnoOld[i] );
      if( !pOld->leaf ){
        assert( leafCorrection==0 );
        /* The right pointer of the child page pOld becomes the left
        ** pointer of the divider cell */
        memcpy(&apCell[nCell][2], &pOld->aData[pOld->hdrOffset+6], 4);
      }else{
        assert( leafCorrection==4 );
      }
      nCell++;

    }
  }

  /*
  ** Figure out the number of pages needed to hold all nCell cells.
  ** Store this number in "k".  Also compute szNew[] which is the total
  ** size of all cells on the i-th page and cntNew[] which is the index
................................................................................
  */
  usableSpace = pBt->pageSize - 10 + leafCorrection;
  for(subtotal=k=i=0; i<nCell; i++){
    subtotal += szCell[i];
    if( subtotal > usableSpace ){
      szNew[k] = subtotal - szCell[i];
      cntNew[k] = i;

      subtotal = 0;
      k++;
    }
  }
  szNew[k] = subtotal;
  cntNew[k] = nCell;
  k++;
................................................................................
      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 ){
................................................................................
  if( checkReadLocks(pCur) ){
    return SQLITE_LOCKED; /* The table pCur points to has a read lock */
  }
  rc = sqlite3BtreeMoveto(pCur, pKey, nKey, &loc);
  if( rc ) return rc;
  pPage = pCur->pPage;
  assert( pPage->intKey || nKey>=0 );

  TRACE(("INSERT: table=%d nkey=%lld ndata=%d page=%d %s\n",
          pCur->pgnoRoot, nKey, nData, pPage->pgno,
          loc==0 ? "overwrite" : "new entry"));
  assert( pPage->isInit );
  rc = sqlite3pager_write(pPage->aData);
  if( rc ) return rc;
  rc = fillInCell(pPage, newCell, pKey, nKey, pData, nData, &szNew);
................................................................................
    ** 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);
................................................................................
  rc = getPage(pBt, (Pgno)pgno, &pPage);
  if( rc ){
    return rc;
  }
  hdr = pPage->hdrOffset;
  data = pPage->aData;
  c = data[hdr];
  pPage->intKey = (c & PTF_INTKEY)!=0;
  pPage->zeroData = (c & PTF_ZERODATA)!=0;

  pPage->leaf = (c & PTF_LEAF)!=0;

  printf("PAGE %d:  flags=0x%02x  frag=%d   parent=%d\n", pgno,
    data[hdr], data[hdr+5], 
    (pPage->isInit && pPage->pParent) ? pPage->pParent->pgno : 0);
  i = 0;
  assert( hdr == (pgno==1 ? 100 : 0) );
  idx = get2byte(&data[hdr+3]);
  while( idx>0 && idx<=pBt->pageSize ){







|







 







>
|
<







 







|
>
>







 







|
|

|







 







>
|
>
>







 







|

>

>







 







|
<

>
>
>







 







|







 







|







 







|







 







|
|

|







 







|
|

|







 







>
>
>
|
|
|
>







 







>







 







>
>
>
|
>
>







 







>
>
>
|
>







 







|





|







 







>







 







|







 







>








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







 







>







 







|

>
>
>



>
>
>
>
>
>
>
>
>




|







 







>







 







>







 







|

>

>







5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
...
192
193
194
195
196
197
198
199
200

201
202
203
204
205
206
207
...
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
...
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
...
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
...
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
...
766
767
768
769
770
771
772
773

774
775
776
777
778
779
780
781
782
783
784
....
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
....
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
....
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
....
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
....
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
....
1982
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
....
2040
2041
2042
2043
2044
2045
2046
2047
2048
2049
2050
2051
2052
2053
2054
....
2067
2068
2069
2070
2071
2072
2073
2074
2075
2076
2077
2078
2079
2080
2081
2082
2083
2084
2085
2086
....
2115
2116
2117
2118
2119
2120
2121
2122
2123
2124
2125
2126
2127
2128
2129
2130
2131
2132
2133
....
2354
2355
2356
2357
2358
2359
2360
2361
2362
2363
2364
2365
2366
2367
2368
2369
2370
2371
2372
2373
2374
....
2706
2707
2708
2709
2710
2711
2712
2713
2714
2715
2716
2717
2718
2719
2720
....
2733
2734
2735
2736
2737
2738
2739
2740
2741
2742
2743
2744
2745
2746
2747
....
2932
2933
2934
2935
2936
2937
2938
2939
2940
2941
2942
2943
2944
2945
2946
2947
2948
2949
2950
2951
2952
2953
2954
2955
2956
2957
2958
2959
2960
2961
2962
2963
2964
2965
2966
2967
2968
2969
2970
2971
2972
2973
2974
....
2980
2981
2982
2983
2984
2985
2986
2987
2988
2989
2990
2991
2992
2993
2994
....
3091
3092
3093
3094
3095
3096
3097
3098
3099
3100
3101
3102
3103
3104
3105
3106
3107
3108
3109
3110
3111
3112
3113
3114
3115
3116
3117
3118
3119
3120
3121
3122
3123
3124
3125
3126
....
3239
3240
3241
3242
3243
3244
3245
3246
3247
3248
3249
3250
3251
3252
3253
....
3324
3325
3326
3327
3328
3329
3330
3331
3332
3333
3334
3335
3336
3337
3338
....
3559
3560
3561
3562
3563
3564
3565
3566
3567
3568
3569
3570
3571
3572
3573
3574
3575
3576
3577
** 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.129 2004/05/12 19:18:16 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.
................................................................................

/*
** Page type flags.  An ORed combination of these flags appear as the
** first byte of every BTree page.
*/
#define PTF_INTKEY    0x01
#define PTF_ZERODATA  0x02
#define PTF_LEAFDATA  0x04
#define PTF_LEAF      0x08


/*
** As each page of the file is loaded into memory, an instance of the following
** structure is appended and initialized to zero.  This structure stores
** information about the page that is decoded from the raw file page.
**
** The pParent field points back to the parent page.  This allows us to
................................................................................
struct MemPage {
  u32 notUsed;
  u8 isInit;                     /* True if previously initialized */
  u8 idxShift;                   /* True if Cell indices have changed */
  u8 isOverfull;                 /* Some aCell[] do not fit on page */
  u8 intKey;                     /* True if intkey flag is set */
  u8 leaf;                       /* True if leaf flag is set */
  u8 zeroData;                   /* True if table stores keys only */
  u8 leafData;                   /* True if tables stores data on leaves only */
  u8 hasData;                    /* True if this page stores data */
  u8 hdrOffset;                  /* 100 for page 1.  0 otherwise */
  u8 needRelink;                 /* True if need to run relinkCellList() */
  int idxParent;                 /* Index in pParent->aCell[] of this node */
  int nFree;                     /* Number of free bytes on the page */
  int nCell;                     /* Number of entries on this page */
  int nCellAlloc;                /* Number of slots allocated in aCell[] */
  unsigned char **aCell;         /* Pointer to start of each cell */
................................................................................
){
  int n;
  if( pPage->leaf ){
    n = 2;
  }else{
    n = 6;
  }
  if( pPage->hasData ){
    n += getVarint(&pCell[n], pnData);
  }else{
    *pnData = 0;
  }
  n += getVarint(&pCell[n], (u64*)pnKey);
  *pnHeader = n;
}

/*
** Compute the total number of bytes that a Cell needs on the main
................................................................................
  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)) );
  }
  data = pPage->aData;
  memset(used, 0, pageSize);
  for(i=0; i<hdr+10-pPage->leaf*4; i++) used[i] = 1;
  nFree = 0;
  pc = get2byte(&data[hdr+1]);
  while( pc ){
................................................................................
  }
  if( pPage->isInit ) return SQLITE_OK;
  pPage->nCell = pPage->nCellAlloc = 0;
  assert( pPage->hdrOffset==(pPage->pgno==1 ? 100 : 0) );
  hdr = pPage->hdrOffset;
  data = pPage->aData;
  c = data[hdr];
  pPage->intKey = (c & (PTF_INTKEY|PTF_LEAFDATA))!=0;
  pPage->zeroData = (c & PTF_ZERODATA)!=0;
  pPage->leafData = (c & PTF_LEAFDATA)!=0;
  pPage->leaf = (c & PTF_LEAF)!=0;
  pPage->hasData = !(pPage->zeroData || (!pPage->leaf && pPage->leafData));
  pPage->isOverfull = 0;
  pPage->needRelink = 0;
  pPage->idxShift = 0;
  pageSize = pPage->pBt->pageSize;

  /* Initialize the cell count and cell pointers */
  pc = get2byte(&data[hdr+3]);
................................................................................
  put2byte(&data[hdr+1], first);
  put2byte(&data[first+2], pBt->pageSize - first);
  sqliteFree(pPage->aCell);
  pPage->aCell = 0;
  pPage->nCell = 0;
  pPage->nCellAlloc = 0;
  pPage->nFree = pBt->pageSize - first;
  pPage->intKey = (flags & (PTF_INTKEY|PTF_LEAFDATA))!=0;

  pPage->zeroData = (flags & PTF_ZERODATA)!=0;
  pPage->leafData = (flags & PTF_LEAFDATA)!=0;
  pPage->leaf = (flags & PTF_LEAF)!=0;
  pPage->hasData = !(pPage->zeroData || (!pPage->leaf && pPage->leafData));
  pPage->hdrOffset = hdr;
  pPage->isOverfull = 0;
  pPage->needRelink = 0;
  pPage->idxShift = 0;
  pPage->isInit = 1;
  pageIntegrity(pPage);
}
................................................................................
  if( rc ) return rc;
  memcpy(data, zMagicHeader, sizeof(zMagicHeader));
  assert( sizeof(zMagicHeader)==16 );
  put2byte(&data[16], SQLITE_PAGE_SIZE);
  data[18] = 1;
  data[19] = 1;
  put2byte(&data[22], (SQLITE_PAGE_SIZE-10)/4-12);
  zeroPage(pP1, PTF_INTKEY|PTF_LEAF );
  return SQLITE_OK;
}

/*
** Attempt to start a new transaction.
**
** A transaction must be started before attempting any changes
................................................................................
    assert( pPage!=0 );
    assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
    cell = pPage->aCell[pCur->idx];
    cell += 2;   /* Skip the offset to the next cell */
    if( !pPage->leaf ){
      cell += 4;  /* Skip the child pointer */
    }
    if( pPage->hasData ){
      while( (0x80&*(cell++))!=0 ){}  /* Skip the data size number */
    }
    getVarint(cell, pSize);
  }
  return SQLITE_OK;
}

................................................................................
  if( !pCur->isValid ){
    return pCur->status ? pCur->status : SQLITE_INTERNAL;
  }
  pPage = pCur->pPage;
  assert( pPage!=0 );
  assert( pPage->isInit );
  pageIntegrity(pPage);
  if( !pPage->hasData ){
    *pSize = 0;
  }else{
    assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
    cell = pPage->aCell[pCur->idx];
    cell += 2;   /* Skip the offset to the next cell */
    if( !pPage->leaf ){
      cell += 4;  /* Skip the child pointer */
................................................................................
  pageIntegrity(pPage);
  assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
  aPayload = pPage->aCell[pCur->idx];
  aPayload += 2;  /* Skip the next cell index */
  if( !pPage->leaf ){
    aPayload += 4;  /* Skip the child pointer */
  }
  if( pPage->hasData ){
    aPayload += getVarint(aPayload, &nData);
  }else{
    nData = 0;
  }
  aPayload += getVarint(aPayload, (u64*)&nKey);
  if( pPage->intKey ){
    nKey = 0;
  }
  assert( offset>=0 );
  if( skipKey ){
................................................................................
  pageIntegrity(pPage);
  assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
  aPayload = pPage->aCell[pCur->idx];
  aPayload += 2;  /* Skip the next cell index */
  if( !pPage->leaf ){
    aPayload += 4;  /* Skip the child pointer */
  }
  if( pPage->hasData ){
    aPayload += getVarint(aPayload, &nData);
  }else{
    nData = 0;
  }
  aPayload += getVarint(aPayload, (u64*)&nKey);
  if( pPage->intKey ){
    nKey = 0;
  }
  maxLocal = pBt->maxLocal;
  if( skipKey ){
................................................................................
        if( pCellKey==0 ) return SQLITE_NOMEM;
        rc = sqlite3BtreeKey(pCur, 0, nCellKey, pCellKey);
        c = pCur->xCompare(pCur->pArg, nCellKey, pCellKey, nKey, pKey);
        sqliteFree(pCellKey);
        if( rc ) return rc;
      }
      if( c==0 ){
        if( pPage->leafData && !pPage->leaf ){
          break;
        }else{
          pCur->iMatch = c;
          if( pRes ) *pRes = 0;
          return SQLITE_OK;
        }
      }
      if( c<0 ){
        lwr = pCur->idx+1;
      }else{
        upr = pCur->idx-1;
      }
    }
................................................................................
** successful then set *pRes=0.  If the cursor
** was already pointing to the last entry in the database before
** this routine was called, then set *pRes=1.
*/
int sqlite3BtreeNext(BtCursor *pCur, int *pRes){
  int rc;
  MemPage *pPage = pCur->pPage;

  assert( pRes!=0 );
  if( pCur->isValid==0 ){
    *pRes = 1;
    return SQLITE_OK;
  }
  assert( pPage->isInit );
  assert( pCur->idx<pPage->nCell );
................................................................................
        pCur->isValid = 0;
        return SQLITE_OK;
      }
      moveToParent(pCur);
      pPage = pCur->pPage;
    }while( pCur->idx>=pPage->nCell );
    *pRes = 0;
    if( pPage->leafData ){
      rc = sqlite3BtreeNext(pCur, pRes);
    }else{
      rc = SQLITE_OK;
    }
    return rc;
  }
  *pRes = 0;
  if( pPage->leaf ){
    return SQLITE_OK;
  }
  rc = moveToLeftmost(pCur);
  return rc;
................................................................................
        *pRes = 1;
        return SQLITE_OK;
      }
      moveToParent(pCur);
      pPage = pCur->pPage;
    }
    pCur->idx--;
    if( pPage->leafData ){
      rc = sqlite3BtreePrevious(pCur, pRes);
    }else{
      rc = SQLITE_OK;
    }
  }
  *pRes = 0;
  return rc;
}

/*
** The TRACE macro will print high-level status information about the
................................................................................
  int nHeader;

  /* Fill in the header. */
  nHeader = 2;
  if( !pPage->leaf ){
    nHeader += 4;
  }
  if( pPage->hasData ){
    nHeader += putVarint(&pCell[nHeader], nData);
  }
  nHeader += putVarint(&pCell[nHeader], *(u64*)&nKey);
  
  /* Fill in the payload */
  if( !pPage->hasData ){
    nData = 0;
  }
  nPayload = nData;
  if( pPage->intKey ){
    pSrc = pData;
    nSrc = nData;
    nData = 0;
................................................................................
  int nNew;                    /* Number of pages in apNew[] */
  int nDiv;                    /* Number of cells in apDiv[] */
  int i, j, k;                 /* Loop counters */
  int idx;                     /* Index of pPage in pParent->aCell[] */
  int nxDiv;                   /* Next divider slot in pParent->aCell[] */
  int rc;                      /* The return code */
  int leafCorrection;          /* 4 if pPage is a leaf.  0 if not */
  int leafData;                /* True if pPage is a leaf of a LEAFDATA tree */
  int usableSpace;             /* Bytes in pPage beyond the header */
  int pageFlags;               /* Value of pPage->aData[0] */
  int subtotal;                /* Subtotal of bytes in cells on one page */
  MemPage *extraUnref = 0;     /* Unref this page if not zero */
  MemPage *apOld[NB];          /* pPage and up to two siblings */
  Pgno pgnoOld[NB];            /* Page numbers for each page in apOld[] */
  MemPage *apCopy[NB];         /* Private copies of apOld[] pages */
................................................................................
  /* 
  ** Return without doing any work if pPage is neither overfull nor
  ** underfull.
  */
  assert( pPage->isInit );
  assert( sqlite3pager_iswriteable(pPage->aData) );
  pBt = pPage->pBt;
  if( !pPage->isOverfull && pPage->nFree<pBt->pageSize*2/3 && pPage->nCell>=2){
    relinkCellList(pPage);
    return SQLITE_OK;
  }

  /*
  ** Find the parent of the page to be balanced.  If there is no parent,
  ** it means this page is the root page and special rules apply.
................................................................................
  ** into aTemp[].  In this wall, all cells in apCell[] are without
  ** child pointers.  If siblings are not leaves, then all cell in
  ** apCell[] include child pointers.  Either way, all cells in apCell[]
  ** are alike.
  */
  nCell = 0;
  leafCorrection = pPage->leaf*4;
  leafData = pPage->leafData && pPage->leaf;
  for(i=0; i<nOld; i++){
    MemPage *pOld = apCopy[i];
    for(j=0; j<pOld->nCell; j++){
      apCell[nCell] = pOld->aCell[j];
      szCell[nCell] = cellSize(pOld, apCell[nCell]);
      nCell++;
    }
    if( i<nOld-1 ){
      if( leafData ){
        int sz = cellSize(pParent, apDiv[i]);
        dropCell(pParent, nxDiv, sz);
      }else{
        szCell[nCell] = cellSize(pParent, apDiv[i]);
        memcpy(aTemp[i], apDiv[i], szCell[nCell]);
        apCell[nCell] = &aTemp[i][leafCorrection];
        dropCell(pParent, nxDiv, szCell[nCell]);
        szCell[nCell] -= leafCorrection;
        assert( get4byte(&aTemp[i][2])==pgnoOld[i] );
        if( !pOld->leaf ){
          assert( leafCorrection==0 );
          /* The right pointer of the child page pOld becomes the left
          ** pointer of the divider cell */
          memcpy(&apCell[nCell][2], &pOld->aData[pOld->hdrOffset+6], 4);
        }else{
          assert( leafCorrection==4 );
        }
        nCell++;
      }
    }
  }

  /*
  ** Figure out the number of pages needed to hold all nCell cells.
  ** Store this number in "k".  Also compute szNew[] which is the total
  ** size of all cells on the i-th page and cntNew[] which is the index
................................................................................
  */
  usableSpace = pBt->pageSize - 10 + leafCorrection;
  for(subtotal=k=i=0; i<nCell; i++){
    subtotal += szCell[i];
    if( subtotal > usableSpace ){
      szNew[k] = subtotal - szCell[i];
      cntNew[k] = i;
      if( leafData ){ i--; }
      subtotal = 0;
      k++;
    }
  }
  szNew[k] = subtotal;
  cntNew[k] = nCell;
  k++;
................................................................................
      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;
      u8 *pTemp;
      int sz;
      pCell = apCell[j];
      sz = szCell[j] + leafCorrection;
      if( !pNew->leaf ){
        memcpy(&pNew->aData[6], pCell+2, 4);
        pTemp = 0;
      }else if( leafData ){
        i64 nKey;
        u64 nData;
        int nHeader;
        j--;
        parseCellHeader(pNew, apCell[j], &nData, &nKey, &nHeader);
        pCell = aInsBuf[i];
        fillInCell(pParent, pCell, 0, nKey, 0, 0, &sz);
        pTemp = 0;
      }else{
        pCell -= 4;
        pTemp = aInsBuf[i];
      }
      insertCell(pParent, nxDiv, pCell, sz, pTemp);
      put4byte(&pParent->aCell[nxDiv][2], pNew->pgno);
      j++;
      nxDiv++;
    }
  }
  assert( j==nCell );
  if( (pageFlags & PTF_LEAF)==0 ){
................................................................................
  if( checkReadLocks(pCur) ){
    return SQLITE_LOCKED; /* The table pCur points to has a read lock */
  }
  rc = sqlite3BtreeMoveto(pCur, pKey, nKey, &loc);
  if( rc ) return rc;
  pPage = pCur->pPage;
  assert( pPage->intKey || nKey>=0 );
  assert( pPage->leaf || !pPage->leafData );
  TRACE(("INSERT: table=%d nkey=%lld ndata=%d page=%d %s\n",
          pCur->pgnoRoot, nKey, nData, pPage->pgno,
          loc==0 ? "overwrite" : "new entry"));
  assert( pPage->isInit );
  rc = sqlite3pager_write(pPage->aData);
  if( rc ) return rc;
  rc = fillInCell(pPage, newCell, pKey, nKey, pData, nData, &szNew);
................................................................................
    ** to be a leaf so we can use it.
    */
    BtCursor leafCur;
    unsigned char *pNext;
    int szNext;
    int notUsed;
    unsigned char tempCell[MX_CELL_SIZE];
    assert( !pPage->leafData );
    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);
................................................................................
  rc = getPage(pBt, (Pgno)pgno, &pPage);
  if( rc ){
    return rc;
  }
  hdr = pPage->hdrOffset;
  data = pPage->aData;
  c = data[hdr];
  pPage->intKey = (c & (PTF_INTKEY|PTF_LEAFDATA))!=0;
  pPage->zeroData = (c & PTF_ZERODATA)!=0;
  pPage->leafData = (c & PTF_LEAFDATA)!=0;
  pPage->leaf = (c & PTF_LEAF)!=0;
  pPage->hasData = !(pPage->zeroData || (!pPage->leaf && pPage->leafData));
  printf("PAGE %d:  flags=0x%02x  frag=%d   parent=%d\n", pgno,
    data[hdr], data[hdr+5], 
    (pPage->isInit && pPage->pParent) ? pPage->pParent->pgno : 0);
  i = 0;
  assert( hdr == (pgno==1 ? 100 : 0) );
  idx = get2byte(&data[hdr+3]);
  while( idx>0 && idx<=pBt->pageSize ){

Changes to src/btree.h.

9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
..
51
52
53
54
55
56
57
58
59

60
61
62
63
64
65
66
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This header file defines the interface that the sqlite B-Tree file
** subsystem.  See comments in the source code for a detailed description
** of what each interface routine does.
**
** @(#) $Id: btree.h,v 1.46 2004/05/12 15:15:47 drh Exp $
*/
#ifndef _BTREE_H_
#define _BTREE_H_

/* TODO: This definition is just included so other modules compile. It
** needs to be revisited.
*/
................................................................................

const char *sqlite3BtreeGetFilename(Btree *);
int sqlite3BtreeCopyFile(Btree *, Btree *);

/* The flags parameter to sqlite3BtreeCreateTable can be the bitwise OR
** of the following flags:
*/
#define BTREE_INTKEY     1      /* Table has only 64-bit integer keys */
#define BTREE_ZERODATA   2      /* Table has keys only - no data */


int sqlite3BtreeDropTable(Btree*, int);
int sqlite3BtreeClearTable(Btree*, int);
int sqlite3BtreeGetMeta(Btree*, int idx, u32 *pValue);
int sqlite3BtreeUpdateMeta(Btree*, int idx, u32 value);

int sqlite3BtreeCursor(







|







 







|
|
>







9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
..
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This header file defines the interface that the sqlite B-Tree file
** subsystem.  See comments in the source code for a detailed description
** of what each interface routine does.
**
** @(#) $Id: btree.h,v 1.47 2004/05/12 19:18:17 drh Exp $
*/
#ifndef _BTREE_H_
#define _BTREE_H_

/* TODO: This definition is just included so other modules compile. It
** needs to be revisited.
*/
................................................................................

const char *sqlite3BtreeGetFilename(Btree *);
int sqlite3BtreeCopyFile(Btree *, Btree *);

/* The flags parameter to sqlite3BtreeCreateTable can be the bitwise OR
** of the following flags:
*/
#define BTREE_INTKEY     1    /* Table has only 64-bit signed integer keys */
#define BTREE_ZERODATA   2    /* Table has keys only - no data */
#define BTREE_LEAFDATA   4    /* Data stored in leaves only.  Implies INTKEY */

int sqlite3BtreeDropTable(Btree*, int);
int sqlite3BtreeClearTable(Btree*, int);
int sqlite3BtreeGetMeta(Btree*, int idx, u32 *pValue);
int sqlite3BtreeUpdateMeta(Btree*, int idx, u32 value);

int sqlite3BtreeCursor(

Changes to test/btree5.test.

7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
...
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
...
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
#    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: btree5.test,v 1.2 2004/05/11 00:58:56 drh Exp $


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

# Attempting to read table 1 of an empty file gives an SQLITE_EMPTY
# error.
................................................................................
    if {[set data [btree_data $c1]] ne "data-for-[btree_key $c1]"} {
      return "wrong data for entry $cnt"
    }
    set n [string length $data]
    set fdata1 [btree_fetch_data $c1 $n]
    set fdata2 [btree_fetch_data $c1 -1]
    if {$fdata1 ne "" && $fdata1 ne $data} {
puts "fdata1=[list $fdata1] data=[list $data]"
      return "DataFetch returned the wrong value with amt=$n"
    }
    if {$fdata1 ne $fdata2} {
      return "DataFetch returned the wrong value when amt=-1"
    }
    if {$n>10} {
      set fdata3 [btree_fetch_data $c1 10]
................................................................................
set c1 [btree_cursor $b1 1 1]
set btree_trace 0

# Do the tests.
#
set cnt 0
for {set i 1} {$i<=100} {incr i} {
  do_test test5-2.$i.1 {
    random_inserts 200
    incr cnt 200
    check_table $cnt
  } {}
  do_test test5-2.$i.2 {
    btree_integrity_check $b1 1
  } {}
  do_test test5-2.$i.3 {
    random_deletes 190
    incr cnt -190
    check_table $cnt
  } {}
  do_test test5-2.$i.4 {
    btree_integrity_check $b1 1
  } {}
}

btree_close_cursor $c1
btree_commit $b1
btree_begin_transaction $b1







|







 







<







 







|




|


|




|







7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
...
119
120
121
122
123
124
125

126
127
128
129
130
131
132
...
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
#    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: btree5.test,v 1.3 2004/05/12 19:18:17 drh Exp $


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

# Attempting to read table 1 of an empty file gives an SQLITE_EMPTY
# error.
................................................................................
    if {[set data [btree_data $c1]] ne "data-for-[btree_key $c1]"} {
      return "wrong data for entry $cnt"
    }
    set n [string length $data]
    set fdata1 [btree_fetch_data $c1 $n]
    set fdata2 [btree_fetch_data $c1 -1]
    if {$fdata1 ne "" && $fdata1 ne $data} {

      return "DataFetch returned the wrong value with amt=$n"
    }
    if {$fdata1 ne $fdata2} {
      return "DataFetch returned the wrong value when amt=-1"
    }
    if {$n>10} {
      set fdata3 [btree_fetch_data $c1 10]
................................................................................
set c1 [btree_cursor $b1 1 1]
set btree_trace 0

# Do the tests.
#
set cnt 0
for {set i 1} {$i<=100} {incr i} {
  do_test btree5-2.$i.1 {
    random_inserts 200
    incr cnt 200
    check_table $cnt
  } {}
  do_test btree5-2.$i.2 {
    btree_integrity_check $b1 1
  } {}
  do_test btree5-2.$i.3 {
    random_deletes 190
    incr cnt -190
    check_table $cnt
  } {}
  do_test btree5-2.$i.4 {
    btree_integrity_check $b1 1
  } {}
}

btree_close_cursor $c1
btree_commit $b1
btree_begin_transaction $b1

Added test/btree6.test.































































































































































































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
# 2004 May 10
#
# The author disclaims copyright to this source code.  In place of
# 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.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this script is btree database backend - specifically
# the B+tree tables.  B+trees store all data on the leaves rather
# that storing data with keys on interior nodes.
#
# $Id: btree6.test,v 1.1 2004/05/12 19:18:17 drh Exp $


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


# Insert many entries into the table that cursor $cur points to.
# The table should be an INTKEY table.
#
# Stagger the inserts.  After the inserts complete, go back and do
# deletes.  Stagger the deletes too.  Repeat this several times.
#

# Do N inserts into table $tab using random keys between 0 and 1000000
#
proc random_inserts {cur N} {
  global inscnt
  while {$N>0} {
    set k [expr {int(rand()*1000000)}]
    if {[btree_move_to $cur $k]==0} {
      continue;  # entry already exists
    }
    incr inscnt
    btree_insert $cur $k data-for-$k
    incr N -1
  }
}
set inscnt 0

# Do N delete from the table that $cur points to.
#
proc random_deletes {cur N} {
  while {$N>0} {
    set k [expr {int(rand()*1000000)}]
    btree_move_to $cur $k
    btree_delete $cur
    incr N -1
  }
}

# Make sure the table that $cur points to has exactly N entries.  
# Make sure the data for each entry agrees with its key.
#
proc check_table {cur N} {
  btree_first $cur
  set cnt 0
  while {![btree_eof $cur]} {
    if {[set data [btree_data $cur]] ne "data-for-[btree_key $cur]"} {
      return "wrong data for entry $cnt"
    }
    set n [string length $data]
    set fdata1 [btree_fetch_data $cur $n]
    set fdata2 [btree_fetch_data $cur -1]
    if {$fdata1 ne "" && $fdata1 ne $data} {
      return "DataFetch returned the wrong value with amt=$n"
    }
    if {$fdata1 ne $fdata2} {
      return "DataFetch returned the wrong value when amt=-1"
    }
    if {$n>10} {
      set fdata3 [btree_fetch_data $cur 10]
      if {$fdata3 ne [string range $data 0 9]} {
        return "DataFetch returned the wrong value when amt=10"
      }
    }
    incr cnt
    btree_next $cur
  }
  if {$cnt!=$N} {
    return "wrong number of entries.  Got $cnt.  Looking for $N"
  }
  return {}
}

# Initialize the database
#
file delete -force test1.bt
file delete -force test1.bt-journal
set b1 [btree_open test1.bt 2000 0]
btree_begin_transaction $b1
set tab [btree_create_table $b1 5]
set cur [btree_cursor $b1 $tab 1]
set btree_trace 0
expr srand(1)

# Do the tests.
#
set cnt 0
for {set i 1} {$i<=100} {incr i} {
  do_test btree6-1.$i.1 {
    random_inserts $cur 200
    incr cnt 200
    check_table $cur $cnt
  } {}
  do_test btree6-1.$i.2 {
    btree_integrity_check $b1 1 $tab
  } {}
  do_test btree6-1.$i.3 {
    random_deletes $cur 190
    incr cnt -190
    check_table $cur $cnt
  } {}
  do_test btree6-1.$i.4 {
    btree_integrity_check $b1 1 $tab
  } {}
}

btree_close_cursor $cur
btree_commit $b1

finish_test