/ Check-in [ee706e9c]
Login

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

Overview
Comment:All tests in btree.test now pass (but only because I commented out the btree_integrity_check test.) (CVS 1328)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: ee706e9c74c3fb32fc3369db226fad9ed4db7596
User & Date: drh 2004-05-09 00:40:52
Context
2004-05-09
01:35
Begin trying to get integrity checking working on the new btree.c. (CVS 1329) check-in: 499569da user: drh tags: trunk
00:40
All tests in btree.test now pass (but only because I commented out the btree_integrity_check test.) (CVS 1328) check-in: ee706e9c user: drh tags: trunk
2004-05-08
20:07
More btree.c bug fixes. (CVS 1327) check-in: e9f84ff3 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
...
214
215
216
217
218
219
220

221
222
223
224
225
226
227
...
373
374
375
376
377
378
379








































































380
381
382
383
384
385
386
...
388
389
390
391
392
393
394


395
396
397
398
399
400
401
...
404
405
406
407
408
409
410

411

412
413
414
415
416
417
418
419
420
...
610
611
612
613
614
615
616

617
618
619
620
621
622
623
...
652
653
654
655
656
657
658

659
660
661
662
663
664
665
...
683
684
685
686
687
688
689

690
691

692
693
694
695
696
697
698
...
745
746
747
748
749
750
751

752
753
754
755
756
757
758
...
996
997
998
999
1000
1001
1002
1003

1004
1005
1006
1007
1008
1009
1010
....
1285
1286
1287
1288
1289
1290
1291

1292
1293
1294
1295
1296
1297
1298
....
1327
1328
1329
1330
1331
1332
1333

1334
1335
1336
1337
1338
1339
1340
....
1449
1450
1451
1452
1453
1454
1455

1456
1457
1458
1459
1460
1461
1462
....
1485
1486
1487
1488
1489
1490
1491

1492
1493
1494
1495
1496
1497
1498
....
1534
1535
1536
1537
1538
1539
1540

1541
1542
1543
1544
1545
1546
1547
....
1581
1582
1583
1584
1585
1586
1587

1588
1589

1590
1591
1592
1593
1594
1595
1596
....
1632
1633
1634
1635
1636
1637
1638

1639
1640
1641
1642
1643
1644
1645
....
1780
1781
1782
1783
1784
1785
1786

1787
1788
1789
1790
1791
1792
1793
....
2214
2215
2216
2217
2218
2219
2220

2221
2222
2223
2224
2225
2226
2227
2228

2229
2230
2231
2232
2233
2234
2235
....
2257
2258
2259
2260
2261
2262
2263
2264
2265
2266

2267
2268
2269
2270

2271
2272
2273
2274
2275

2276
2277
2278
2279
2280
2281
2282

















2283
2284
2285
2286
2287
2288
2289
2290
2291
2292
2293
2294
2295
2296

2297
2298
2299
2300
2301
2302
2303
2304
2305
2306
2307
2308
2309
2310
2311
2312
2313

2314
2315















2316
2317
2318
2319
2320
2321
2322
2323
2324
2325
2326
2327
2328

2329
2330
2331
2332
2333
2334
2335
2336

2337
2338
2339
2340
2341
2342
2343
....
2375
2376
2377
2378
2379
2380
2381









2382
2383
2384
2385
2386
2387
2388
....
2471
2472
2473
2474
2475
2476
2477

2478
2479
2480
2481
2482
2483
2484
2485

2486
2487
2488
2489
2490
2491
2492
....
2509
2510
2511
2512
2513
2514
2515

2516
2517
2518

2519
2520
2521
2522
2523
2524
2525
2526

2527
2528
2529
2530
2531
2532
2533
2534
2535
2536

2537
2538
2539
2540
2541
2542
2543
....
2554
2555
2556
2557
2558
2559
2560

2561
2562
2563
2564
2565
2566
2567
....
2830
2831
2832
2833
2834
2835
2836

2837
2838
2839
2840
2841
2842
2843
....
2848
2849
2850
2851
2852
2853
2854

2855
2856
2857
2858
2859
2860
2861
....
3220
3221
3222
3223
3224
3225
3226
3227
3228

3229
3230
3231
3232
3233
3234
3235
....
3317
3318
3319
3320
3321
3322
3323
3324
3325
3326


3327
3328
3329
3330
3331
3332
3333
** 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.116 2004/05/08 20:07:40 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 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 */

  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 */
  struct Btree *pBt;             /* Pointer back to BTree structure */

................................................................................
  maxPayload = pPage->pBt->maxLocal;
  if( nPayload>maxPayload ){
    nPayload = maxPayload + 4;
  }
  return n + nPayload;
}









































































/*
** Defragment the page given.  All Cells are moved to the
** beginning of the page and all free space is collected 
** into one big FreeBlk at the end of the page.
*/
static void defragmentPage(MemPage *pPage){
  int pc, i, n, addr;
................................................................................
  int leftover;
  unsigned char *oldPage;
  unsigned char newPage[MX_PAGE_SIZE];

  assert( sqlite3pager_iswriteable(pPage->aData) );
  assert( pPage->pBt!=0 );
  assert( pPage->pBt->pageSize <= MX_PAGE_SIZE );


  oldPage = pPage->aData;
  hdr = pPage->hdrOffset;
  addr = 3+hdr;
  n = 6+hdr;
  if( !pPage->leaf ){
    n += 4;
  }
................................................................................
  pc = get2byte(&oldPage[addr]);
  i = 0;
  while( pc>0 ){
    assert( n<pPage->pBt->pageSize );
    size = cellSize(pPage, &oldPage[pc]);
    memcpy(&newPage[n], &oldPage[pc], size);
    put2byte(&newPage[addr],n);

    pPage->aCell[i++] = &oldPage[n];

    n += size;
    addr = pc;
    pc = get2byte(&oldPage[pc]);
  }
  assert( i==pPage->nCell );
  leftover = pPage->pBt->pageSize - n;
  assert( leftover>=0 );
  assert( pPage->nFree==leftover );
  if( leftover<4 ){
................................................................................
  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->idxShift = 0;
  pageSize = pPage->pBt->pageSize;

  /* Initialize the cell count and cell pointers */
  pc = get2byte(&data[hdr+3]);
  while( pc>0 ){
    if( pc>=pageSize ) return SQLITE_CORRUPT;
................................................................................
  /* Sanity check:  Cells and freespace and header must sum to the size
  ** a page. */
  if( sumCell+pPage->nFree+hdr+10-pPage->leaf*4 != pageSize ){
    return SQLITE_CORRUPT;
  }

  pPage->isInit = 1;

  return SQLITE_OK;
}

/*
** Set up a raw page so that it looks like a database page holding
** no entries.
*/
................................................................................
  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->idxShift = 0;
  pPage->isInit = 1;

}

/*
** Get a page from the pager.  Initialize the MemPage.pBt and
** MemPage.aData elements if needed.
*/
static int getPage(Btree *pBt, Pgno pgno, MemPage **ppPage){
................................................................................
/*
** This routine is called when the reference count for a page
** reaches zero.  We need to unref the pParent pointer when that
** happens.
*/
static void pageDestructor(void *pData){
  MemPage *pPage = (MemPage*)&((char*)pData)[SQLITE_PAGE_SIZE];

  if( pPage->pParent ){
    MemPage *pParent = pPage->pParent;
    pPage->pParent = 0;
    releasePage(pParent);
  }
  sqliteFree(pPage->aCell);
  pPage->aCell = 0;
................................................................................
/*
** Invalidate all cursors
*/
static void invalidateCursors(Btree *pBt){
  BtCursor *pCur;
  for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){
    MemPage *pPage = pCur->pPage;
    if( pPage && !pPage->isInit ){

      releasePage(pPage);
      pCur->pPage = 0;
      pCur->isValid = 0;
      pCur->status = SQLITE_ABORT;
    }
  }
}
................................................................................
  MemPage *pPage;
  unsigned char *cell;

  if( !pCur->isValid ){
    *pSize = 0;
  }else{
    pPage = pCur->pPage;

    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 */
    }
................................................................................
  u64 nData, nKey;
  int maxLocal, ovflSize;

  assert( pCur!=0 && pCur->pPage!=0 );
  assert( pCur->isValid );
  pBt = pCur->pBt;
  pPage = pCur->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 ){
................................................................................
  if( !pCur->isValid ){
    return 0;
  }
  assert( pCur->pPage!=0 );
  assert( pCur->idx>=0 && pCur->idx<pCur->pPage->nCell );
  pBt = pCur->pBt;
  pPage = pCur->pPage;

  assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
  assert( pPage->intKey==0 );
  aPayload = pPage->aCell[pCur->idx];
  aPayload += 2;  /* Skip the next cell index */
  if( !pPage->leaf ){
    aPayload += 4;  /* Skip the child pointer */
  }
................................................................................

  if( !pCur->isValid ){
    return pCur->status ? pCur->status : SQLITE_INTERNAL;
  }
  pPage = pCur->pPage;
  assert( pPage!=0 );
  assert( pPage->isInit );

  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 ){
................................................................................
  MemPage *pNewPage;
  MemPage *pOldPage;
  Btree *pBt = pCur->pBt;

  assert( pCur->isValid );
  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;
  if( pNewPage->nCell<1 ){
................................................................................
  MemPage *pPage;
  int idxParent;

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

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

  idxParent = pPage->idxParent;
  sqlite3pager_ref(pParent->aData);
  oldPgno = pPage->pgno;
  releasePage(pPage);
  pCur->pPage = pParent;
  assert( pParent->idxShift==0 );
  if( pParent->idxShift==0 ){
................................................................................

  rc = getAndInitPage(pBt, pCur->pgnoRoot, &pRoot, 0);
  if( rc ){
    pCur->isValid = 0;
    return rc;
  }
  releasePage(pCur->pPage);

  pCur->pPage = pRoot;
  pCur->idx = 0;
  if( pRoot->nCell==0 && !pRoot->leaf ){
    Pgno subpage;
    assert( pRoot->pgno==1 );
    subpage = get4byte(&pRoot->aData[pRoot->hdrOffset+6]);
    assert( subpage>0 );
................................................................................
  for(;;){
    int lwr, upr;
    Pgno chldPg;
    MemPage *pPage = pCur->pPage;
    int c = -1;  /* pRes return if table is empty must be -1 */
    lwr = 0;
    upr = pPage->nCell-1;

    while( lwr<=upr ){
      void *pCellKey;
      u64 nCellKey;
      pCur->idx = (lwr+upr)/2;
      sqlite3BtreeKeySize(pCur, &nCellKey);
      if( pPage->intKey ){
        if( nCellKey<nKey ){
................................................................................
static void reparentPage(Btree *pBt, Pgno pgno, MemPage *pNewParent, int idx){
  MemPage *pThis;
  unsigned char *aData;

  if( pgno==0 ) return;
  assert( pBt->pPager!=0 );
  aData = sqlite3pager_lookup(pBt->pPager, pgno);

  pThis = (MemPage*)&aData[pBt->pageSize];
  if( pThis && pThis->isInit ){
    if( pThis->pParent!=pNewParent ){
      if( pThis->pParent ) sqlite3pager_unref(pThis->pParent->aData);
      pThis->pParent = pNewParent;
      if( pNewParent ) sqlite3pager_ref(pNewParent->aData);
    }
    pThis->idxParent = idx;

    sqlite3pager_unref(aData);
  }
}

/*
** Change the pParent pointer of all children of pPage to point back
** to pPage.
................................................................................
** Remove the i-th cell from pPage.  This routine effects pPage only.
** The cell content is not freed or deallocated.  It is assumed that
** the cell content has been copied someplace else.  This routine just
** removes the reference to the cell from pPage.
**
** "sz" must be the number of bytes in the cell.
**
** Do not bother maintaining the integrity of the linked list of Cells.
** Only the pPage->aCell[] array is important.  The relinkCellList() 
** routine will be called soon after this routine in order to rebuild 

** the linked list.
*/
static void dropCell(MemPage *pPage, int idx, int sz){
  int j, pc;

  assert( idx>=0 && idx<pPage->nCell );
  assert( sz==cellSize(pPage, pPage->aCell[idx]) );
  assert( sqlite3pager_iswriteable(pPage->aData) );
  assert( pPage->aCell[idx]>=pPage->aData );
  assert( pPage->aCell[idx]<&pPage->aData[pPage->pBt->pageSize-sz] );

  pc = Addr(pPage->aCell[idx]) - Addr(pPage->aData);
  assert( pc>pPage->hdrOffset && pc+sz<=pPage->pBt->pageSize );
  freeSpace(pPage, pc, sz);
  for(j=idx; j<pPage->nCell-1; j++){
    pPage->aCell[j] = pPage->aCell[j+1];
  }
  pPage->nCell--;

















  pPage->idxShift = 1;
}

/*
** 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.  
**
** Do not bother maintaining the integrity of the linked list of Cells.
** Only the pPage->aCell[] array is important.  The relinkCellList() 
** routine will be called soon after this routine in order to rebuild 

** the linked list.
*/
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 = 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{

    memcpy(&pPage->aData[idx], pCell, sz);
    pPage->aCell[i] = &pPage->aData[idx];















  }
  pPage->idxShift = 1;
}

/*
** Rebuild the linked list of cells on a page so that the cells
** occur in the order specified by the pPage->aCell[] array.  
** Invoke this routine once to repair damage after one or more
** invocations of either insertCell() or dropCell().
*/
static void relinkCellList(MemPage *pPage){
  int i, idxFrom;
  assert( sqlite3pager_iswriteable(pPage->aData) );

  idxFrom = pPage->hdrOffset+3;
  for(i=0; i<pPage->nCell; i++){
    int idx = Addr(pPage->aCell[i]) - Addr(pPage->aData);
    assert( idx>pPage->hdrOffset && idx<pPage->pBt->pageSize );
    put2byte(&pPage->aData[idxFrom], idx);
    idxFrom = idx;
  }
  put2byte(&pPage->aData[idxFrom], 0);

}

/*
** GCC does not define the offsetof() macro so we'll have to do it
** ourselves.
*/
#ifndef offsetof
................................................................................
    uptr x = Addr(pTo->aCell[i]);
    if( x>from && x<from+pageSize-ofst ){
      *((uptr*)&pTo->aCell[i]) = x + to - from;
    }
  }
}










/*
** The following parameters determine how many adjacent pages get involved
** in a balancing operation.  NN is the number of neighbors on either side
** of the page that participate in the balancing operation.  NB is the
** total number of pages that participate, including the target page and
** NN neighbors on either side.
**
................................................................................
  }

  /*
  ** 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.
  */
  pParent = pPage->pParent;

  if( pParent==0 ){
    Pgno pgnoChild;
    MemPage *pChild;
    assert( pPage->isInit );
    if( pPage->nCell==0 ){
      if( pPage->leaf ){
        /* The table is completely empty */
        relinkCellList(pPage);

      }else{
        /* The root page is empty but has one child.  Transfer the
        ** information from that one child into the root page if it 
        ** will fit.  This reduces the depth of the BTree by one.
        **
        ** If the root page is page 1, it has less space available than
        ** its child (due to the 100 byte header that occurs at the beginning
................................................................................
            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);

          }else{
            /* The child has more information that will fit on the root.
            ** The tree is already balanced.  Do nothing. */

          }
        }else{
          memcpy(pPage, pChild, pBt->pageSize);
          pPage->isInit = 0;
          pPage->pParent = 0;
          rc = initPage(pPage, 0);
          assert( rc==SQLITE_OK );
          freePage(pChild);

        }
        reparentChildPages(pPage);
        releasePage(pChild);
      }
      return SQLITE_OK;
    }
    if( !pPage->isOverfull ){
      /* It is OK for the root page to be less than half full.
      */
      relinkCellList(pPage);

      return SQLITE_OK;
    }
    /*
    ** If we get to here, it means the root page is overfull.
    ** When this happens, Create a new child page and copy the
    ** contents of the root into the child.  Then make the root
    ** page an empty page with rightChild pointing to the new
................................................................................
    pChild->idxParent = 0;
    pChild->isOverfull = 1;
    zeroPage(pPage, pChild->aData[0] & ~PTF_LEAF);
    put4byte(&pPage->aData[pPage->hdrOffset+6], pChild->pgno);
    pParent = pPage;
    pPage = pChild;
    extraUnref = pChild;

  }
  rc = sqlite3pager_write(pParent->aData);
  if( rc ) return rc;
  assert( pParent->isInit );
  
  /*
  ** Find the cell in the parent page whose left child points back
................................................................................
  reparentChildPages(pParent);

  /*
  ** balance the parent page.
  */
  assert( pPage->isInit );
  assert( pParent->isInit );

  rc = balance(pParent);
  

  /*
  ** Cleanup before returning.
  */
balance_cleanup:
................................................................................
    }
  }
  for(i=0; i<nNew; i++){
    releasePage(apNew[i]);
  }
  releasePage(pParent);
  releasePage(extraUnref);

  return rc;
}

/*
** This routine checks all cursors that point to the same table
** as pCur points to.  If any of those cursors were opened with
** wrFlag==0 then this routine returns SQLITE_LOCKED.  If all
................................................................................
  }
  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\n", pgno,
    data[hdr], data[hdr+5]);

  i = 0;
  assert( hdr == (pgno==1 ? 100 : 0) );
  idx = get2byte(&data[hdr+3]);
  while( idx>0 && idx<=pBt->pageSize ){
    u64 nData, nKey;
    int nHeader;
    Pgno child;
................................................................................
**   aResult[4] =  Number of free bytes on this page
**   aResult[5] =  Number of free blocks on the page
**   aResult[6] =  Page number of the left child of this entry
**   aResult[7] =  Page number of the right child for the whole page
**
** This routine is used for testing and debugging only.
*/
int sqlite3BtreeCursorDump(BtCursor *pCur, int *aResult){
  int cnt, idx;
  MemPage *pPage = pCur->pPage;


  assert( pPage->isInit );
  aResult[0] = sqlite3pager_pagenumber(pPage->aData);
  assert( aResult[0]==pPage->pgno );
  aResult[1] = pCur->idx;
  aResult[2] = pPage->nCell;
  if( pCur->idx>=0 && pCur->idx<pPage->nCell ){
    aResult[3] = cellSize(pPage, pPage->aCell[pCur->idx]);







|







 







>







 







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







 







>
>







 







>

>

<







 







>







 







>







 







>


>







 







>







 







|
>







 







>







 







>







 







>







 







>







 







>







 







>


>







 







>







 







>







 







>
|
|
|
|
|
|
|
|
>







 







|
|
|
>
|



>





>
|






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











|
|
|
>
|






|









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













>








>







 







>
>
>
>
>
>
>
>
>







 







>








>







 







>



>








>










>







 







>







 







>







 







>







 







|
|
>







 







|


>
>







5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
...
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
...
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
...
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
...
479
480
481
482
483
484
485
486
487
488
489

490
491
492
493
494
495
496
...
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
...
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
...
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
...
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
....
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
....
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
....
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
....
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
....
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
....
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
....
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
....
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
....
1870
1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
....
2305
2306
2307
2308
2309
2310
2311
2312
2313
2314
2315
2316
2317
2318
2319
2320
2321
2322
2323
2324
2325
2326
2327
2328
....
2350
2351
2352
2353
2354
2355
2356
2357
2358
2359
2360
2361
2362
2363
2364
2365
2366
2367
2368
2369
2370
2371
2372
2373
2374
2375
2376
2377
2378
2379
2380
2381
2382
2383
2384
2385
2386
2387
2388
2389
2390
2391
2392
2393
2394
2395
2396
2397
2398
2399
2400
2401
2402
2403
2404
2405
2406
2407
2408
2409
2410
2411
2412
2413
2414
2415
2416
2417
2418
2419
2420
2421
2422
2423
2424
2425
2426
2427
2428
2429
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
2467
2468
2469
2470
2471
2472
2473
2474
2475
....
2507
2508
2509
2510
2511
2512
2513
2514
2515
2516
2517
2518
2519
2520
2521
2522
2523
2524
2525
2526
2527
2528
2529
....
2612
2613
2614
2615
2616
2617
2618
2619
2620
2621
2622
2623
2624
2625
2626
2627
2628
2629
2630
2631
2632
2633
2634
2635
....
2652
2653
2654
2655
2656
2657
2658
2659
2660
2661
2662
2663
2664
2665
2666
2667
2668
2669
2670
2671
2672
2673
2674
2675
2676
2677
2678
2679
2680
2681
2682
2683
2684
2685
2686
2687
2688
2689
2690
....
2701
2702
2703
2704
2705
2706
2707
2708
2709
2710
2711
2712
2713
2714
2715
....
2978
2979
2980
2981
2982
2983
2984
2985
2986
2987
2988
2989
2990
2991
2992
....
2997
2998
2999
3000
3001
3002
3003
3004
3005
3006
3007
3008
3009
3010
3011
....
3370
3371
3372
3373
3374
3375
3376
3377
3378
3379
3380
3381
3382
3383
3384
3385
3386
....
3468
3469
3470
3471
3472
3473
3474
3475
3476
3477
3478
3479
3480
3481
3482
3483
3484
3485
3486
** 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.117 2004/05/09 00:40:52 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 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 */
  struct Btree *pBt;             /* Pointer back to BTree structure */

................................................................................
  maxPayload = pPage->pBt->maxLocal;
  if( nPayload>maxPayload ){
    nPayload = maxPayload + 4;
  }
  return n + nPayload;
}

/*
** 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 pageSize;
  u8 *data;
  int i, idx, c, pc, hdr, nFree;
  u8 used[MX_PAGE_SIZE];

  pageSize = pPage->pBt->pageSize;
  assert( pPage->aData==&((unsigned char*)pPage)[-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->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 ){
    int size;
    assert( pc>0 && pc<pageSize-4 );
    size = get2byte(&data[pc+2]);
    assert( pc+size<=pageSize );
    nFree += size;
    for(i=pc; i<pc+size; i++){
      assert( used[i]==0 );
      used[i] = 1;
    }
    pc = get2byte(&data[pc]);
  }
  assert( pPage->isInit==0 || pPage->nFree==nFree+data[hdr+5] );
  idx = 0;
  pc = get2byte(&data[hdr+3]);
  while( pc ){
    int size;
    assert( pPage->isInit==0 || idx<pPage->nCell );
    assert( pc>0 && pc<pageSize-4 );
    assert( pPage->isInit==0 || pPage->aCell[idx]==&data[pc] );
    size = cellSize(pPage, &data[pc]);
    assert( pc+size<=pageSize );
    for(i=pc; i<pc+size; i++){
      assert( used[i]==0 );
      used[i] = 1;
    }
    pc = get2byte(&data[pc]);
    idx++;
  }
  assert( idx==pPage->nCell );
  nFree = 0;
  for(i=0; i<pageSize; i++){
    assert( used[i]<=1 );
    if( used[i]==0 ) nFree++;
  }
  assert( nFree==data[hdr+5] );
}
#define pageIntegrity(X) _pageIntegrity(X)
#else
# define pageIntegrity(X)
#endif

/*
** Defragment the page given.  All Cells are moved to the
** beginning of the page and all free space is collected 
** into one big FreeBlk at the end of the page.
*/
static void defragmentPage(MemPage *pPage){
  int pc, i, n, addr;
................................................................................
  int leftover;
  unsigned char *oldPage;
  unsigned char newPage[MX_PAGE_SIZE];

  assert( sqlite3pager_iswriteable(pPage->aData) );
  assert( pPage->pBt!=0 );
  assert( pPage->pBt->pageSize <= MX_PAGE_SIZE );
  assert( !pPage->needRelink );
  assert( !pPage->isOverfull );
  oldPage = pPage->aData;
  hdr = pPage->hdrOffset;
  addr = 3+hdr;
  n = 6+hdr;
  if( !pPage->leaf ){
    n += 4;
  }
................................................................................
  pc = get2byte(&oldPage[addr]);
  i = 0;
  while( pc>0 ){
    assert( n<pPage->pBt->pageSize );
    size = cellSize(pPage, &oldPage[pc]);
    memcpy(&newPage[n], &oldPage[pc], size);
    put2byte(&newPage[addr],n);
    assert( pPage->aCell[i]==&oldPage[pc] );
    pPage->aCell[i++] = &oldPage[n];
    addr = n;
    n += size;

    pc = get2byte(&oldPage[pc]);
  }
  assert( i==pPage->nCell );
  leftover = pPage->pBt->pageSize - n;
  assert( leftover>=0 );
  assert( pPage->nFree==leftover );
  if( leftover<4 ){
................................................................................
  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]);
  while( pc>0 ){
    if( pc>=pageSize ) return SQLITE_CORRUPT;
................................................................................
  /* Sanity check:  Cells and freespace and header must sum to the size
  ** a page. */
  if( sumCell+pPage->nFree+hdr+10-pPage->leaf*4 != pageSize ){
    return SQLITE_CORRUPT;
  }

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

/*
** Set up a raw page so that it looks like a database page holding
** no entries.
*/
................................................................................
  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);
}

/*
** Get a page from the pager.  Initialize the MemPage.pBt and
** MemPage.aData elements if needed.
*/
static int getPage(Btree *pBt, Pgno pgno, MemPage **ppPage){
................................................................................
/*
** This routine is called when the reference count for a page
** reaches zero.  We need to unref the pParent pointer when that
** happens.
*/
static void pageDestructor(void *pData){
  MemPage *pPage = (MemPage*)&((char*)pData)[SQLITE_PAGE_SIZE];
  assert( pPage->isInit==0 || pPage->needRelink==0 );
  if( pPage->pParent ){
    MemPage *pParent = pPage->pParent;
    pPage->pParent = 0;
    releasePage(pParent);
  }
  sqliteFree(pPage->aCell);
  pPage->aCell = 0;
................................................................................
/*
** Invalidate all cursors
*/
static void invalidateCursors(Btree *pBt){
  BtCursor *pCur;
  for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){
    MemPage *pPage = pCur->pPage;
    if( pPage /* && !pPage->isInit */ ){
      pageIntegrity(pPage);
      releasePage(pPage);
      pCur->pPage = 0;
      pCur->isValid = 0;
      pCur->status = SQLITE_ABORT;
    }
  }
}
................................................................................
  MemPage *pPage;
  unsigned char *cell;

  if( !pCur->isValid ){
    *pSize = 0;
  }else{
    pPage = pCur->pPage;
    pageIntegrity(pPage);
    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 */
    }
................................................................................
  u64 nData, nKey;
  int maxLocal, ovflSize;

  assert( pCur!=0 && pCur->pPage!=0 );
  assert( pCur->isValid );
  pBt = pCur->pBt;
  pPage = pCur->pPage;
  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 ){
................................................................................
  if( !pCur->isValid ){
    return 0;
  }
  assert( pCur->pPage!=0 );
  assert( pCur->idx>=0 && pCur->idx<pCur->pPage->nCell );
  pBt = pCur->pBt;
  pPage = pCur->pPage;
  pageIntegrity(pPage);
  assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
  assert( pPage->intKey==0 );
  aPayload = pPage->aCell[pCur->idx];
  aPayload += 2;  /* Skip the next cell index */
  if( !pPage->leaf ){
    aPayload += 4;  /* Skip the child pointer */
  }
................................................................................

  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 ){
................................................................................
  MemPage *pNewPage;
  MemPage *pOldPage;
  Btree *pBt = pCur->pBt;

  assert( pCur->isValid );
  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;
  if( pNewPage->nCell<1 ){
................................................................................
  MemPage *pPage;
  int idxParent;

  assert( pCur->isValid );
  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);
  oldPgno = pPage->pgno;
  releasePage(pPage);
  pCur->pPage = pParent;
  assert( pParent->idxShift==0 );
  if( pParent->idxShift==0 ){
................................................................................

  rc = getAndInitPage(pBt, pCur->pgnoRoot, &pRoot, 0);
  if( rc ){
    pCur->isValid = 0;
    return rc;
  }
  releasePage(pCur->pPage);
  pageIntegrity(pRoot);
  pCur->pPage = pRoot;
  pCur->idx = 0;
  if( pRoot->nCell==0 && !pRoot->leaf ){
    Pgno subpage;
    assert( pRoot->pgno==1 );
    subpage = get4byte(&pRoot->aData[pRoot->hdrOffset+6]);
    assert( subpage>0 );
................................................................................
  for(;;){
    int lwr, upr;
    Pgno chldPg;
    MemPage *pPage = pCur->pPage;
    int c = -1;  /* pRes return if table is empty must be -1 */
    lwr = 0;
    upr = pPage->nCell-1;
    pageIntegrity(pPage);
    while( lwr<=upr ){
      void *pCellKey;
      u64 nCellKey;
      pCur->idx = (lwr+upr)/2;
      sqlite3BtreeKeySize(pCur, &nCellKey);
      if( pPage->intKey ){
        if( nCellKey<nKey ){
................................................................................
static void reparentPage(Btree *pBt, Pgno pgno, MemPage *pNewParent, int idx){
  MemPage *pThis;
  unsigned char *aData;

  if( pgno==0 ) return;
  assert( pBt->pPager!=0 );
  aData = sqlite3pager_lookup(pBt->pPager, pgno);
  if( aData ){
    pThis = (MemPage*)&aData[pBt->pageSize];
    if( pThis->isInit ){
      if( pThis->pParent!=pNewParent ){
        if( pThis->pParent ) sqlite3pager_unref(pThis->pParent->aData);
        pThis->pParent = pNewParent;
        if( pNewParent ) sqlite3pager_ref(pNewParent->aData);
      }
      pThis->idxParent = idx;
    }
    sqlite3pager_unref(aData);
  }
}

/*
** Change the pParent pointer of all children of pPage to point back
** to pPage.
................................................................................
** Remove the i-th cell from pPage.  This routine effects pPage only.
** The cell content is not freed or deallocated.  It is assumed that
** the cell content has been copied someplace else.  This routine just
** removes the reference to the cell from pPage.
**
** "sz" must be the number of bytes in the cell.
**
** 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 dropCell(MemPage *pPage, int idx, int sz){
  int j, pc;
  u8 *data;
  assert( idx>=0 && idx<pPage->nCell );
  assert( sz==cellSize(pPage, pPage->aCell[idx]) );
  assert( sqlite3pager_iswriteable(pPage->aData) );
  assert( pPage->aCell[idx]>=pPage->aData );
  assert( pPage->aCell[idx]<&pPage->aData[pPage->pBt->pageSize-sz] );
  data = pPage->aData;
  pc = Addr(pPage->aCell[idx]) - Addr(data);
  assert( pc>pPage->hdrOffset && pc+sz<=pPage->pBt->pageSize );
  freeSpace(pPage, pc, sz);
  for(j=idx; j<pPage->nCell-1; j++){
    pPage->aCell[j] = pPage->aCell[j+1];
  }
  pPage->nCell--;
  if( !pPage->isOverfull && !pPage->needRelink ){
    u8 *pPrev;
    if( idx==0 ){
      pPrev = &data[pPage->hdrOffset+3];
    }else{
      pPrev = pPage->aCell[idx-1];
    }
    if( idx<pPage->nCell ){
      pc = Addr(pPage->aCell[idx]) - Addr(data);
    }else{
      pc = 0;
    }
    put2byte(pPrev, pc);
    pageIntegrity(pPage);
  }else{
    pPage->needRelink = 1;
  }
  pPage->idxShift = 1;
}

/*
** 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;
    int pc;
    if( i==0 ){
      pPrev = &pPage->aData[pPage->hdrOffset+3];
    }else{
      pPrev = pPage->aCell[i-1];
    }
    pc = get2byte(pPrev);
    put2byte(pPrev, idx);
    put2byte(pPage->aCell[i], pc);
    pageIntegrity(pPage);
  }else{
    pPage->needRelink = 1;
  }
  pPage->idxShift = 1;
}

/*
** Rebuild the linked list of cells on a page so that the cells
** occur in the order specified by the pPage->aCell[] array.  
** Invoke this routine once to repair damage after one or more
** invocations of either insertCell() or dropCell().
*/
static void relinkCellList(MemPage *pPage){
  int i, idxFrom;
  assert( sqlite3pager_iswriteable(pPage->aData) );
  if( !pPage->needRelink ) return;
  idxFrom = pPage->hdrOffset+3;
  for(i=0; i<pPage->nCell; i++){
    int idx = Addr(pPage->aCell[i]) - Addr(pPage->aData);
    assert( idx>pPage->hdrOffset && idx<pPage->pBt->pageSize );
    put2byte(&pPage->aData[idxFrom], idx);
    idxFrom = idx;
  }
  put2byte(&pPage->aData[idxFrom], 0);
  pPage->needRelink = 0;
}

/*
** GCC does not define the offsetof() macro so we'll have to do it
** ourselves.
*/
#ifndef offsetof
................................................................................
    uptr x = Addr(pTo->aCell[i]);
    if( x>from && x<from+pageSize-ofst ){
      *((uptr*)&pTo->aCell[i]) = x + to - from;
    }
  }
}

/*
** For debugging...
*/
#if 1
# define TRACE(X)   if( pager3_refinfo_enable ) printf X
#else
# define TRACE(X)
#endif

/*
** The following parameters determine how many adjacent pages get involved
** in a balancing operation.  NN is the number of neighbors on either side
** of the page that participate in the balancing operation.  NB is the
** total number of pages that participate, including the target page and
** NN neighbors on either side.
**
................................................................................
  }

  /*
  ** 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.
  */
  pParent = pPage->pParent;
  TRACE(("BALANCE: begin page %d\n", pPage->pgno));
  if( pParent==0 ){
    Pgno pgnoChild;
    MemPage *pChild;
    assert( pPage->isInit );
    if( pPage->nCell==0 ){
      if( pPage->leaf ){
        /* The table is completely empty */
        relinkCellList(pPage);
        TRACE(("BALANCE: empty table\n"));
      }else{
        /* The root page is empty but has one child.  Transfer the
        ** information from that one child into the root page if it 
        ** will fit.  This reduces the depth of the BTree by one.
        **
        ** If the root page is page 1, it has less space available than
        ** its child (due to the 100 byte header that occurs at the beginning
................................................................................
            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));
          }
        }else{
          memcpy(pPage, pChild, pBt->pageSize);
          pPage->isInit = 0;
          pPage->pParent = 0;
          rc = initPage(pPage, 0);
          assert( rc==SQLITE_OK );
          freePage(pChild);
          TRACE(("BALANCE: transfer child %d into root\n", pChild->pgno));
        }
        reparentChildPages(pPage);
        releasePage(pChild);
      }
      return SQLITE_OK;
    }
    if( !pPage->isOverfull ){
      /* It is OK for the root page to be less than half full.
      */
      relinkCellList(pPage);
      TRACE(("BALANCE:  Root page is underfull but that is ok\n"));
      return SQLITE_OK;
    }
    /*
    ** If we get to here, it means the root page is overfull.
    ** When this happens, Create a new child page and copy the
    ** contents of the root into the child.  Then make the root
    ** page an empty page with rightChild pointing to the new
................................................................................
    pChild->idxParent = 0;
    pChild->isOverfull = 1;
    zeroPage(pPage, pChild->aData[0] & ~PTF_LEAF);
    put4byte(&pPage->aData[pPage->hdrOffset+6], pChild->pgno);
    pParent = pPage;
    pPage = pChild;
    extraUnref = pChild;
    TRACE(("BALANCE: Copy root into %d and blance\n", pPage->pgno));
  }
  rc = sqlite3pager_write(pParent->aData);
  if( rc ) return rc;
  assert( pParent->isInit );
  
  /*
  ** Find the cell in the parent page whose left child points back
................................................................................
  reparentChildPages(pParent);

  /*
  ** balance the parent page.
  */
  assert( pPage->isInit );
  assert( pParent->isInit );
  pageIntegrity(pPage);
  rc = balance(pParent);
  

  /*
  ** Cleanup before returning.
  */
balance_cleanup:
................................................................................
    }
  }
  for(i=0; i<nNew; i++){
    releasePage(apNew[i]);
  }
  releasePage(pParent);
  releasePage(extraUnref);
  TRACE(("BALANCE: Finished with %d\n", pPage->pgno));
  return rc;
}

/*
** This routine checks all cursors that point to the same table
** as pCur points to.  If any of those cursors were opened with
** wrFlag==0 then this routine returns SQLITE_LOCKED.  If all
................................................................................
  }
  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 ){
    u64 nData, nKey;
    int nHeader;
    Pgno child;
................................................................................
**   aResult[4] =  Number of free bytes on this page
**   aResult[5] =  Number of free blocks on the page
**   aResult[6] =  Page number of the left child of this entry
**   aResult[7] =  Page number of the right child for the whole page
**
** This routine is used for testing and debugging only.
*/
int sqlite3BtreeCursorInfo(BtCursor *pCur, int *aResult){
  int cnt, idx;
  MemPage *pPage = pCur->pPage;

  pageIntegrity(pPage);
  assert( pPage->isInit );
  aResult[0] = sqlite3pager_pagenumber(pPage->aData);
  assert( aResult[0]==pPage->pgno );
  aResult[1] = pCur->idx;
  aResult[2] = pPage->nCell;
  if( pCur->idx>=0 && pCur->idx<pPage->nCell ){
    aResult[3] = cellSize(pPage, pPage->aCell[pCur->idx]);

Changes to src/btree.h.

9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
..
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
**    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.41 2004/05/08 20:07:40 drh Exp $
*/
#ifndef _BTREE_H_
#define _BTREE_H_

/* TODO: This definition is just included so other modules compile. It
** needs to be revisited.
*/
................................................................................
int sqlite3BtreeData(BtCursor*, u32 offset, u32 amt, void*);
int sqlite3BtreeKeyCompare(BtCursor *, const void *, int, int, int *);

char *sqlite3BtreeIntegrityCheck(Btree*, int *aRoot, int nRoot);
struct Pager *sqlite3BtreePager(Btree*);

#ifdef SQLITE_TEST
int sqlite3BtreeCursorDump(BtCursor*, int*);
void sqlite3BtreeCursorList(Btree*);
int sqlite3BtreeFlags(BtCursor*);
int sqlite3BtreePageDump(Btree*, int, int recursive);
#endif


#endif /* _BTREE_H_ */







|







 







|







9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
..
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
**    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.42 2004/05/09 00:40:52 drh Exp $
*/
#ifndef _BTREE_H_
#define _BTREE_H_

/* TODO: This definition is just included so other modules compile. It
** needs to be revisited.
*/
................................................................................
int sqlite3BtreeData(BtCursor*, u32 offset, u32 amt, void*);
int sqlite3BtreeKeyCompare(BtCursor *, const void *, int, int, int *);

char *sqlite3BtreeIntegrityCheck(Btree*, int *aRoot, int nRoot);
struct Pager *sqlite3BtreePager(Btree*);

#ifdef SQLITE_TEST
int sqlite3BtreeCursorInfo(BtCursor*, int*);
void sqlite3BtreeCursorList(Btree*);
int sqlite3BtreeFlags(BtCursor*);
int sqlite3BtreePageDump(Btree*, int, int recursive);
#endif


#endif /* _BTREE_H_ */

Changes to src/test3.c.

9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
...
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
....
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
....
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
**    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.31 2004/05/08 20:07:40 drh Exp $
*/
#include "sqliteInt.h"
#include "pager.h"
#include "btree.h"
#include "tcl.h"
#include <stdlib.h>
#include <string.h>
................................................................................
  sqlite3BtreeDataSize(pCur, &n2);
  sprintf(zBuf, "%d", (int)(n1+n2));
  Tcl_AppendResult(interp, zBuf, 0);
  return SQLITE_OK;
}

/*
** Usage:   btree_cursor_dump ID
**
** Return eight integers containing information about the entry the
** cursor is pointing to:
**
**   aResult[0] =  The page number
**   aResult[1] =  The entry number
**   aResult[2] =  Total number of entries on this page
**   aResult[3] =  Size of this entry
**   aResult[4] =  Number of free bytes on this page
**   aResult[5] =  Number of free blocks on the page
**   aResult[6] =  Page number of the left child of this entry
**   aResult[7] =  Page number of the right child for the whole page
*/
static int btree_cursor_dump(
  void *NotUsed,
  Tcl_Interp *interp,    /* The TCL interpreter that invoked this command */
  int argc,              /* Number of arguments */
  const char **argv      /* Text of each argument */
){
  BtCursor *pCur;
  int rc;
................................................................................

  if( argc!=2 ){
    Tcl_AppendResult(interp, "wrong # args: should be \"", argv[0],
       " ID\"", 0);
    return TCL_ERROR;
  }
  if( Tcl_GetInt(interp, argv[1], (int*)&pCur) ) return TCL_ERROR;
  rc = sqlite3BtreeCursorDump(pCur, aResult);
  if( rc ){
    Tcl_AppendResult(interp, errorName(rc), 0);
    return TCL_ERROR;
  }
  j = 0;
  for(i=0; i<sizeof(aResult)/sizeof(aResult[0]); i++){
    sprintf(&zBuf[j]," %d", aResult[i]);
................................................................................
     { "btree_eof",                (Tcl_CmdProc*)btree_eof                },
     { "btree_keysize",            (Tcl_CmdProc*)btree_keysize            },
     { "btree_key",                (Tcl_CmdProc*)btree_key                },
     { "btree_data",               (Tcl_CmdProc*)btree_data               },
     { "btree_payload_size",       (Tcl_CmdProc*)btree_payload_size       },
     { "btree_first",              (Tcl_CmdProc*)btree_first              },
     { "btree_last",               (Tcl_CmdProc*)btree_last               },
     { "btree_cursor_dump",        (Tcl_CmdProc*)btree_cursor_dump        },
     { "btree_cursor_list",        (Tcl_CmdProc*)btree_cursor_list        },
     { "btree_integrity_check",    (Tcl_CmdProc*)btree_integrity_check    },
     { "btree_breakpoint",         (Tcl_CmdProc*)btree_breakpoint         },
  };
  int i;

  for(i=0; i<sizeof(aCmd)/sizeof(aCmd[0]); i++){
    Tcl_CreateCommand(interp, aCmd[i].zName, aCmd[i].xProc, 0, 0);
  }
  Tcl_LinkVar(interp, "pager_refinfo_enable", (char*)&pager3_refinfo_enable,
     TCL_LINK_INT);
  return TCL_OK;
}







|







 







|













|







 







|







 







|













9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
...
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
....
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
....
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
**    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.32 2004/05/09 00:40:52 drh Exp $
*/
#include "sqliteInt.h"
#include "pager.h"
#include "btree.h"
#include "tcl.h"
#include <stdlib.h>
#include <string.h>
................................................................................
  sqlite3BtreeDataSize(pCur, &n2);
  sprintf(zBuf, "%d", (int)(n1+n2));
  Tcl_AppendResult(interp, zBuf, 0);
  return SQLITE_OK;
}

/*
** Usage:   btree_cursor_info ID
**
** Return eight integers containing information about the entry the
** cursor is pointing to:
**
**   aResult[0] =  The page number
**   aResult[1] =  The entry number
**   aResult[2] =  Total number of entries on this page
**   aResult[3] =  Size of this entry
**   aResult[4] =  Number of free bytes on this page
**   aResult[5] =  Number of free blocks on the page
**   aResult[6] =  Page number of the left child of this entry
**   aResult[7] =  Page number of the right child for the whole page
*/
static int btree_cursor_info(
  void *NotUsed,
  Tcl_Interp *interp,    /* The TCL interpreter that invoked this command */
  int argc,              /* Number of arguments */
  const char **argv      /* Text of each argument */
){
  BtCursor *pCur;
  int rc;
................................................................................

  if( argc!=2 ){
    Tcl_AppendResult(interp, "wrong # args: should be \"", argv[0],
       " ID\"", 0);
    return TCL_ERROR;
  }
  if( Tcl_GetInt(interp, argv[1], (int*)&pCur) ) return TCL_ERROR;
  rc = sqlite3BtreeCursorInfo(pCur, aResult);
  if( rc ){
    Tcl_AppendResult(interp, errorName(rc), 0);
    return TCL_ERROR;
  }
  j = 0;
  for(i=0; i<sizeof(aResult)/sizeof(aResult[0]); i++){
    sprintf(&zBuf[j]," %d", aResult[i]);
................................................................................
     { "btree_eof",                (Tcl_CmdProc*)btree_eof                },
     { "btree_keysize",            (Tcl_CmdProc*)btree_keysize            },
     { "btree_key",                (Tcl_CmdProc*)btree_key                },
     { "btree_data",               (Tcl_CmdProc*)btree_data               },
     { "btree_payload_size",       (Tcl_CmdProc*)btree_payload_size       },
     { "btree_first",              (Tcl_CmdProc*)btree_first              },
     { "btree_last",               (Tcl_CmdProc*)btree_last               },
     { "btree_cursor_info",        (Tcl_CmdProc*)btree_cursor_info        },
     { "btree_cursor_list",        (Tcl_CmdProc*)btree_cursor_list        },
     { "btree_integrity_check",    (Tcl_CmdProc*)btree_integrity_check    },
     { "btree_breakpoint",         (Tcl_CmdProc*)btree_breakpoint         },
  };
  int i;

  for(i=0; i<sizeof(aCmd)/sizeof(aCmd[0]); i++){
    Tcl_CreateCommand(interp, aCmd[i].zName, aCmd[i].xProc, 0, 0);
  }
  Tcl_LinkVar(interp, "pager_refinfo_enable", (char*)&pager3_refinfo_enable,
     TCL_LINK_INT);
  return TCL_OK;
}

Changes to test/btree.test.

7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
...
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
...
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618

619
620
621
622
623
624
625
626
627
628
629
630
631
632
...
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
...
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
...
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958

959

960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991

992
993
994
995

996
997
998
999

1000
1001
1002
1003
1004
1005
1006
....
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
#    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: btree.test,v 1.20 2004/05/08 20:07:40 drh Exp $


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

# Basic functionality.  Open and close a database.
#
................................................................................
  # Totals 1016 bytes.  8 bytes left over
  # Keys are 1000 through 1090.
  for {set i 1000} {$i<1091} {incr i} {
    set key $i
    set data [format %5d $i]
    btree_insert $::c1 $key $data
  }
  lrange [btree_cursor_dump $::c1] 4 5
} {8 1}
do_test btree-7.3 {
  for {set i 1001} {$i<1091} {incr i 2} {
    btree_move_to $::c1 $i
    btree_delete $::c1
  }
  # Freed 45 blocks.  Total freespace is 458
  # Keys remaining are even numbers between 1000 and 1090, inclusive
  lrange [btree_cursor_dump $::c1] 4 5
} {458 46}
#btree_page_dump $::b1 2
do_test btree-7.4 {
  # The largest free block is 10 bytes long.  So if we insert
  # a record bigger than 10 bytes it should force a defrag
  # The record is 20 bytes long.
  btree_insert $::c1 2000 {123456789_12345}
  btree_move_to $::c1 2000
  btree_key $::c1
} {2000}
do_test btree-7.5 {
  lrange [btree_cursor_dump $::c1] 4 5
} {438 1}
#btree_page_dump $::b1 2

# Delete an entry to make a hole of a known size, then immediately recreate
# that entry.  This tests the path into allocateSpace where the hole exactly
# matches the size of the desired space.
#
# Keys are even numbers between 1000 and 1090 and one record of 2000.
# There are 47 keys total.
................................................................................
do_test btree-7.6 {
  btree_move_to $::c1 1006
  btree_delete $::c1
  btree_move_to $::c1 1010
  btree_delete $::c1
} {}
do_test btree-7.7 {
  lrange [btree_cursor_dump $::c1] 4 5
} {458 3}   ;# Create two new holes of 10 bytes each
#btree_page_dump $::b1 2
do_test btree-7.8 {
  btree_insert $::c1 1006 { 1006}
  lrange [btree_cursor_dump $::c1] 4 5
} {448 2}   ;# Filled in the first hole
#btree_page_dump $::b1 2

# Make sure the freeSpace() routine properly coaleses adjacent memory blocks
#
do_test btree-7.9 {
  btree_move_to $::c1 1012
  btree_delete $::c1
  lrange [btree_cursor_dump $::c1] 4 5
} {458 2}  ;# Coalesce with the whole before
do_test btree-7.10 {
  btree_move_to $::c1 1008
  btree_delete $::c1
  lrange [btree_cursor_dump $::c1] 4 5
} {468 2}  ;# Coalesce with whole after
do_test btree-7.11 {
  btree_move_to $::c1 1030
  btree_delete $::c1
  lrange [btree_cursor_dump $::c1] 4 5
} {478 3}   ;# Make a new hole
do_test btree-7.13 {
  btree_move_to $::c1 1034
  btree_delete $::c1
  lrange [btree_cursor_dump $::c1] 4 5
} {488 4}   ;# Make another hole
do_test btree-7.14 {
  btree_move_to $::c1 1032
  btree_delete $::c1
  lrange [btree_cursor_dump $::c1] 4 5
} {498 3}   ;# The freed space should coalesce on both ends
#btree_page_dump $::b1 2
do_test btree-7.15 {
  lindex [btree_pager_stats $::b1] 1
} {1}

# Check to see that data on overflow pages work correctly.
#

do_test btree-8.1 {
  set data "*** This is a very long key "
  while {[string length $data]<1234} {append data $data}
  set ::data $data
  btree_insert $::c1 2020 $data
} {}
#btree_page_dump $::b1 2
do_test btree-8.1.1 {
  lindex [btree_pager_stats $::b1] 1
} {1}
#btree_pager_ref_dump $::b1
do_test btree-8.2 {
  btree_move_to $::c1 2020
  string length [btree_data $::c1]
................................................................................
#btree_tree_dump $::b1 2
#btree_pager_ref_dump $::b1
#set pager_refinfo_enable 1
do_test btree-9.2 {
  btree_insert $::c1 020 {*** 020 *** 020 *** 020 *** 020 ***}
  select_keys $::c1
} {001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020}
#btree_page_dump $::b1 5
#btree_page_dump $::b1 2
#btree_page_dump $::b1 7
#btree_pager_ref_dump $::b1
#set pager_refinfo_enable 0

# The previous "select_keys" command left the cursor pointing at the root
# page.  So there should only be two pages checked out.  2 (the root) and
# page 1.
do_test btree-9.2.1 {
................................................................................
  #btree_tree_dump $::b1 2
}

# Create a tree with lots more pages
#
catch {unset ::data}
catch {unset ::key}
for {set i 31} {$i<=1000} {incr i} {
if {$i==88} {
set pager_refinfo_enable 1
btree_tree_dump $b1 2
btree_pager_ref_dump $b1
btree_cursor_list $b1
}
  do_test btree-11.1.$i.1 {
    set key [format %03d $i]
    set ::data "*** $key *** $key *** $key *** $key ***"
    btree_insert $::c1 $key $data
    btree_move_to $::c1 $key
    btree_key $::c1
  } [format %03d $i]
if {$i==88} {
btree_pager_ref_dump $b1
btree_cursor_list $b1
btree_tree_dump $b1 2
exit
}
  do_test btree-11.1.$i.2 {
    btree_data $::c1
  } $::data
  set ::key [format %03d [expr {$i/2}]]
  if {$::key=="012"} {set ::key 013}
  do_test btree-11.1.$i.3 {
    btree_move_to $::c1 $::key
................................................................................
  lindex [btree_pager_stats $::b1] 1
} {2}
#btree_page_dump $::b1 2

# Delete the dividers on the root page
#
do_test btree-11.4 {
  btree_move_to $::c1 257
  btree_delete $::c1
  btree_next $::c1
  btree_key $::c1
} {258}
do_test btree-11.4.1 {
  btree_move_to $::c1 256
  btree_key $::c1
} {256}
do_test btree-11.4.2 {
  btree_move_to $::c1 258
  btree_key $::c1
} {258}
do_test btree-11.4.3 {
  btree_move_to $::c1 259
  btree_key $::c1
} {259}
do_test btree-11.4.4 {
  btree_move_to $::c1 257
  set n [btree_key $::c1]
  expr {$n==256||$n==258}
} {1}
do_test btree-11.5 {
  btree_move_to $::c1 513
  btree_delete $::c1
  btree_next $::c1
  btree_key $::c1
} {514}
do_test btree-11.5.1 {
  btree_move_to $::c1 512
  btree_key $::c1
} {512}
do_test btree-11.5.2 {
  btree_move_to $::c1 514
  btree_key $::c1
} {514}
do_test btree-11.5.3 {
  btree_move_to $::c1 515
  btree_key $::c1
} {515}
do_test btree-11.5.4 {
  btree_move_to $::c1 513
  set n [btree_key $::c1]
  expr {$n==512||$n==514}
} {1}
do_test btree-11.6 {
  btree_move_to $::c1 769
  btree_delete $::c1

  btree_next $::c1

  btree_key $::c1
} {770}
do_test btree-11.6.1 {
  btree_move_to $::c1 768
  btree_key $::c1
} {768}
do_test btree-11.6.2 {
  btree_move_to $::c1 771
  btree_key $::c1
} {771}
do_test btree-11.6.3 {
  btree_move_to $::c1 770
  btree_key $::c1
} {770}
do_test btree-11.6.4 {
  btree_move_to $::c1 769
  set n [btree_key $::c1]
  expr {$n==768||$n==770}
} {1}
#btree_page_dump $::b1 2
#btree_page_dump $::b1 25

# Change the data on an intermediate node such that the node becomes overfull
# and has to split.  We happen to know that intermediate nodes exist on
# 337, 401 and 465 by the btree_page_dumps above
#
catch {unset ::data}
set ::data {This is going to be a very long data segment}
append ::data $::data
append ::data $::data
do_test btree-12.1 {
  btree_insert $::c1 337 $::data

  btree_data $::c1
} $::data
do_test btree-12.2 {
  btree_insert $::c1 401 $::data

  btree_data $::c1
} $::data
do_test btree-12.3 {
  btree_insert $::c1 465 $::data

  btree_data $::c1
} $::data
do_test btree-12.4 {
  btree_move_to $::c1 337
  btree_key $::c1
} {337}
do_test btree-12.5 {
................................................................................
  btree_next $::c1
  btree_data $::c1
} $::data
do_test btree-12.12 {
  btree_next $::c1
  btree_key $::c1
} {402}
do_test btree-13.1 {
  btree_integrity_check $::b1 2 3
} {}

# To Do:
#
#   1.  Do some deletes from the 3-layer tree
#   2.  Commit and reopen the database
#   3.  Read every 15th entry and make sure it works
#   4.  Implement btree_sanity and put it throughout this script







|







 







|








|

|









|

|







 







|




|








|




|




|




|




|








>






|







 







<

<







 







|
<
<
<
<
<
<







<
<
<
<
<
<







 







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

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

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











>




>




>







 







|
|
|







7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
...
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
...
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
...
754
755
756
757
758
759
760

761

762
763
764
765
766
767
768
...
855
856
857
858
859
860
861
862






863
864
865
866
867
868
869






870
871
872
873
874
875
876
...
891
892
893
894
895
896
897























898
899




900
901

















902
903
904
905

















906


907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
...
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
#    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: btree.test,v 1.21 2004/05/09 00:40:52 drh Exp $


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

# Basic functionality.  Open and close a database.
#
................................................................................
  # Totals 1016 bytes.  8 bytes left over
  # Keys are 1000 through 1090.
  for {set i 1000} {$i<1091} {incr i} {
    set key $i
    set data [format %5d $i]
    btree_insert $::c1 $key $data
  }
  lrange [btree_cursor_info $::c1] 4 5
} {8 1}
do_test btree-7.3 {
  for {set i 1001} {$i<1091} {incr i 2} {
    btree_move_to $::c1 $i
    btree_delete $::c1
  }
  # Freed 45 blocks.  Total freespace is 458
  # Keys remaining are even numbers between 1000 and 1090, inclusive
  lrange [btree_cursor_info $::c1] 4 5
} {458 46}
#btree_tree_dump $::b1 1
do_test btree-7.4 {
  # The largest free block is 10 bytes long.  So if we insert
  # a record bigger than 10 bytes it should force a defrag
  # The record is 20 bytes long.
  btree_insert $::c1 2000 {123456789_12345}
  btree_move_to $::c1 2000
  btree_key $::c1
} {2000}
do_test btree-7.5 {
  lrange [btree_cursor_info $::c1] 4 5
} {438 1}
#btree_tree_dump $::b1 1

# Delete an entry to make a hole of a known size, then immediately recreate
# that entry.  This tests the path into allocateSpace where the hole exactly
# matches the size of the desired space.
#
# Keys are even numbers between 1000 and 1090 and one record of 2000.
# There are 47 keys total.
................................................................................
do_test btree-7.6 {
  btree_move_to $::c1 1006
  btree_delete $::c1
  btree_move_to $::c1 1010
  btree_delete $::c1
} {}
do_test btree-7.7 {
  lrange [btree_cursor_info $::c1] 4 5
} {458 3}   ;# Create two new holes of 10 bytes each
#btree_page_dump $::b1 2
do_test btree-7.8 {
  btree_insert $::c1 1006 { 1006}
  lrange [btree_cursor_info $::c1] 4 5
} {448 2}   ;# Filled in the first hole
#btree_page_dump $::b1 2

# Make sure the freeSpace() routine properly coaleses adjacent memory blocks
#
do_test btree-7.9 {
  btree_move_to $::c1 1012
  btree_delete $::c1
  lrange [btree_cursor_info $::c1] 4 5
} {458 2}  ;# Coalesce with the whole before
do_test btree-7.10 {
  btree_move_to $::c1 1008
  btree_delete $::c1
  lrange [btree_cursor_info $::c1] 4 5
} {468 2}  ;# Coalesce with whole after
do_test btree-7.11 {
  btree_move_to $::c1 1030
  btree_delete $::c1
  lrange [btree_cursor_info $::c1] 4 5
} {478 3}   ;# Make a new hole
do_test btree-7.13 {
  btree_move_to $::c1 1034
  btree_delete $::c1
  lrange [btree_cursor_info $::c1] 4 5
} {488 4}   ;# Make another hole
do_test btree-7.14 {
  btree_move_to $::c1 1032
  btree_delete $::c1
  lrange [btree_cursor_info $::c1] 4 5
} {498 3}   ;# The freed space should coalesce on both ends
#btree_page_dump $::b1 2
do_test btree-7.15 {
  lindex [btree_pager_stats $::b1] 1
} {1}

# Check to see that data on overflow pages work correctly.
#
#btree_page_dump $::b1 1
do_test btree-8.1 {
  set data "*** This is a very long key "
  while {[string length $data]<1234} {append data $data}
  set ::data $data
  btree_insert $::c1 2020 $data
} {}
#btree_page_dump $::b1 1
do_test btree-8.1.1 {
  lindex [btree_pager_stats $::b1] 1
} {1}
#btree_pager_ref_dump $::b1
do_test btree-8.2 {
  btree_move_to $::c1 2020
  string length [btree_data $::c1]
................................................................................
#btree_tree_dump $::b1 2
#btree_pager_ref_dump $::b1
#set pager_refinfo_enable 1
do_test btree-9.2 {
  btree_insert $::c1 020 {*** 020 *** 020 *** 020 *** 020 ***}
  select_keys $::c1
} {001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020}

#btree_page_dump $::b1 2

#btree_pager_ref_dump $::b1
#set pager_refinfo_enable 0

# The previous "select_keys" command left the cursor pointing at the root
# page.  So there should only be two pages checked out.  2 (the root) and
# page 1.
do_test btree-9.2.1 {
................................................................................
  #btree_tree_dump $::b1 2
}

# Create a tree with lots more pages
#
catch {unset ::data}
catch {unset ::key}
for {set i 31} {$i<=999} {incr i} {






  do_test btree-11.1.$i.1 {
    set key [format %03d $i]
    set ::data "*** $key *** $key *** $key *** $key ***"
    btree_insert $::c1 $key $data
    btree_move_to $::c1 $key
    btree_key $::c1
  } [format %03d $i]






  do_test btree-11.1.$i.2 {
    btree_data $::c1
  } $::data
  set ::key [format %03d [expr {$i/2}]]
  if {$::key=="012"} {set ::key 013}
  do_test btree-11.1.$i.3 {
    btree_move_to $::c1 $::key
................................................................................
  lindex [btree_pager_stats $::b1] 1
} {2}
#btree_page_dump $::b1 2

# Delete the dividers on the root page
#
do_test btree-11.4 {























  btree_move_to $::c1 551
  btree_delete $::c1




  btree_move_to $::c1 551
  set k [btree_key $::c1]

















  if {$k==550} {
    set k [btree_next $::c1]
  }
  btree_key $::c1

















} {552}



# Change the data on an intermediate node such that the node becomes overfull
# and has to split.  We happen to know that intermediate nodes exist on
# 337, 401 and 465 by the btree_page_dumps above
#
catch {unset ::data}
set ::data {This is going to be a very long data segment}
append ::data $::data
append ::data $::data
do_test btree-12.1 {
  btree_insert $::c1 337 $::data
  btree_move_to $::c1 337
  btree_data $::c1
} $::data
do_test btree-12.2 {
  btree_insert $::c1 401 $::data
  btree_move_to $::c1 401
  btree_data $::c1
} $::data
do_test btree-12.3 {
  btree_insert $::c1 465 $::data
  btree_move_to $::c1 465
  btree_data $::c1
} $::data
do_test btree-12.4 {
  btree_move_to $::c1 337
  btree_key $::c1
} {337}
do_test btree-12.5 {
................................................................................
  btree_next $::c1
  btree_data $::c1
} $::data
do_test btree-12.12 {
  btree_next $::c1
  btree_key $::c1
} {402}
#do_test btree-13.1 {
#  btree_integrity_check $::b1 1 2
#} {}

# To Do:
#
#   1.  Do some deletes from the 3-layer tree
#   2.  Commit and reopen the database
#   3.  Read every 15th entry and make sure it works
#   4.  Implement btree_sanity and put it throughout this script

Changes to test/btree2.test.

7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
...
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
#    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.10 2002/02/19 13:39:23 drh Exp $


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

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

................................................................................
      set ::c4 [btree_cursor $::b 4 1]
      set ::c5 [btree_cursor $::b 5 1]
      set ::c6 [btree_cursor $::b 6 1]
      check_invariants
    } {}
    set cnt 6
    for {set i 2} {$i<=6} {incr i} {
      if {[lindex [btree_cursor_dump [set ::c$i]] 0]!=$i} {incr cnt}
    }
    do_test $testid.1 {
      btree_begin_transaction $::b
      lindex [btree_pager_stats $::b] 1
    } $cnt
    # exec cp test2.bt test2.bt.bu1
    do_test $testid.2 [subst {







|







 







|







7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
...
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
#    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.11 2004/05/09 00:40:52 drh Exp $


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

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

................................................................................
      set ::c4 [btree_cursor $::b 4 1]
      set ::c5 [btree_cursor $::b 5 1]
      set ::c6 [btree_cursor $::b 6 1]
      check_invariants
    } {}
    set cnt 6
    for {set i 2} {$i<=6} {incr i} {
      if {[lindex [btree_cursor_info [set ::c$i]] 0]!=$i} {incr cnt}
    }
    do_test $testid.1 {
      btree_begin_transaction $::b
      lindex [btree_pager_stats $::b] 1
    } $cnt
    # exec cp test2.bt test2.bt.bu1
    do_test $testid.2 [subst {