/ Check-in [51892d6c]
Login

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

Overview
Comment:Sync all version 3 changes. (CVS 1309)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 51892d6cdc739bb049fdfce8301354312167c181
User & Date: drh 2004-04-29 14:42:46
Context
2004-05-02
21:12
Changes to btree for the new file format are mostly complete. Still need to test and debug. (CVS 1311) check-in: 0eee3b5c user: drh tags: trunk
2004-04-29
14:42
Sync all version 3 changes. (CVS 1309) check-in: 51892d6c user: drh tags: trunk
2004-04-26
14:10
Pager tests working. (CVS 1308) check-in: 910067a2 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
....
1514
1515
1516
1517
1518
1519
1520
















1521
1522
1523
1524
1525
1526
1527
....
1531
1532
1533
1534
1535
1536
1537

1538
1539
1540
1541
1542
1543
1544
....
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589







1590
1591
1592
1593
1594
1595
1596
1597
....
1798
1799
1800
1801
1802
1803
1804
1805
1806
1807
1808
1809
1810
1811
1812
....
1851
1852
1853
1854
1855
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
....
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
** 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.105 2004/04/26 14:10:21 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.
................................................................................
  pCur->pPage = pNewPage;
  pCur->idx = 0;
  if( pNewPage->nCell<1 ){
    return SQLITE_CORRUPT;
  }
  return SQLITE_OK;
}

















/*
** Move the cursor up to the parent page.
**
** pCur->idx is set to the cell index that contains the pointer
** to the page we are coming from.  If we are coming from the
** right-most child page then pCur->idx is set to one more than
................................................................................
  Pgno oldPgno;
  MemPage *pParent;
  MemPage *pPage;
  int idxParent;

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

  pParent = pPage->pParent;
  assert( pParent!=0 );
  idxParent = pPage->idxParent;
  sqlitepager_ref(pParent->aData);
  oldPgno = pPage->pgno;
  releasePage(pPage);
  pCur->pPage = pParent;
................................................................................
** Move the cursor to the root page
*/
static int moveToRoot(BtCursor *pCur){
  MemPage *pRoot;
  int rc;
  Btree *pBt = pCur->pBt;

  rc = sqlitepager_get(pBt->pPager, pCur->pgnoRoot, &pRoot);
  if( rc ) return rc;
  rc = initPage(pRoot, 0);
  if( rc ) return rc;
  releasePage(pCur->pPage);
  pCur->pPage = pRoot;
  pCur->idx = 0;







  return SQLITE_OK;
}

/*
** Move the cursor down to the left-most leaf entry beneath the
** entry to which it is currently pointing.
*/
static int moveToLeftmost(BtCursor *pCur){
................................................................................
      rc = moveToChild(pCur, get4byte(&pPage->aData[pPage->hdrOffset+6]);
      if( rc ) return rc;
      rc = moveToLeftmost(pCur);
      *pRes = 0;
      return rc;
    }
    do{
      if( pPage->pParent==0 ){
        *pRes = 1;
        return SQLITE_OK;
      }
      moveToParent(pCur);
      pPage = pCur->pPage;
    }while( pCur->idx>=pPage->nCell );
    *pRes = 0;
................................................................................
  if( !pPage->left ){
    pgno = get4byte(&pPage->aCell[pCur->idx][2]);
    rc = moveToChild(pCur, pgno);
    if( rc ) return rc;
    rc = moveToRightmost(pCur);
  }else{
    while( pCur->idx==0 ){
      if( pPage->pParent==0 ){
        if( pRes ) *pRes = 1;
        return SQLITE_OK;
      }
      moveToParent(pCur);
      pPage = pCur->pPage;
    }
    pCur->idx--;
................................................................................
  */
  pParent = pPage->pParent;
  if( pParent==0 ){
    Pgno pgnoChild;
    MemPage *pChild;
    assert( pPage->isInit );
    if( pPage->nCell==0 ){
      if( pPage->u.hdr.rightChild ){
        /*


        ** The root page is empty.  Copy the one child page
        ** into the root page and return.  This reduces the depth

        ** of the BTree by one.






        */
        pgnoChild = SWAB32(pBt, pPage->u.hdr.rightChild);
        rc = sqlitepager_get(pBt->pPager, pgnoChild, (void**)&pChild);



        if( rc ) return rc;






        memcpy(pPage, pChild, SQLITE_USABLE_SIZE);
        pPage->isInit = 0;
        rc = initPage(pBt, pPage, sqlitepager_pagenumber(pPage), 0);
        assert( rc==SQLITE_OK );
        reparentChildPages(pBt, pPage);
        if( pCur && pCur->pPage==pChild ){
          sqlitepager_unref(pChild);
          pCur->pPage = pPage;
          sqlitepager_ref(pPage);
        }
        freePage(pBt, pChild, pgnoChild);
        sqlitepager_unref(pChild);







|







 







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







 







>







 







|






>
>
>
>
>
>
>
|







 







|







 







|







 







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

<
<
>
>
>

>
>
>
>
>
>
|
|
|
|
|







5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
....
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
....
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
....
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
....
1822
1823
1824
1825
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835
1836
....
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
....
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
** 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.106 2004/04/29 14:42:46 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.
................................................................................
  pCur->pPage = pNewPage;
  pCur->idx = 0;
  if( pNewPage->nCell<1 ){
    return SQLITE_CORRUPT;
  }
  return SQLITE_OK;
}

/*
** Return true if the page is the virtual root of its table.
**
** The virtual root page is the root page for most tables.  But
** for the table rooted on page 1, sometime the real root page
** is empty except for the right-pointer.  In such cases the
** virtual root page is the page that the right-pointer of page
** 1 is pointing to.
*/
static int isRootPage(MemPage *pPage){
  MemPage *pParent = pPage->pParent;
  assert( pParent==0 || pParent->isInit );
  if( pParent || (pParent->pgno==1 && pParent->nCell==0) ) return 1;
  return 0;
}

/*
** Move the cursor up to the parent page.
**
** pCur->idx is set to the cell index that contains the pointer
** to the page we are coming from.  If we are coming from the
** right-most child page then pCur->idx is set to one more than
................................................................................
  Pgno oldPgno;
  MemPage *pParent;
  MemPage *pPage;
  int idxParent;

  pPage = pCur->pPage;
  assert( pPage!=0 );
  assert( !isRootPage(pPage) );
  pParent = pPage->pParent;
  assert( pParent!=0 );
  idxParent = pPage->idxParent;
  sqlitepager_ref(pParent->aData);
  oldPgno = pPage->pgno;
  releasePage(pPage);
  pCur->pPage = pParent;
................................................................................
** Move the cursor to the root page
*/
static int moveToRoot(BtCursor *pCur){
  MemPage *pRoot;
  int rc;
  Btree *pBt = pCur->pBt;

  rc = getPage(pBt, pCur->pgnoRoot, &pRoot);
  if( rc ) return rc;
  rc = initPage(pRoot, 0);
  if( rc ) 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 );
    rc = movetoChild(pCur, subpage);
  }
  return rc;
}

/*
** Move the cursor down to the left-most leaf entry beneath the
** entry to which it is currently pointing.
*/
static int moveToLeftmost(BtCursor *pCur){
................................................................................
      rc = moveToChild(pCur, get4byte(&pPage->aData[pPage->hdrOffset+6]);
      if( rc ) return rc;
      rc = moveToLeftmost(pCur);
      *pRes = 0;
      return rc;
    }
    do{
      if( isRootPage(pPage) ){
        *pRes = 1;
        return SQLITE_OK;
      }
      moveToParent(pCur);
      pPage = pCur->pPage;
    }while( pCur->idx>=pPage->nCell );
    *pRes = 0;
................................................................................
  if( !pPage->left ){
    pgno = get4byte(&pPage->aCell[pCur->idx][2]);
    rc = moveToChild(pCur, pgno);
    if( rc ) return rc;
    rc = moveToRightmost(pCur);
  }else{
    while( pCur->idx==0 ){
      if( isRootPage(pPage) ){
        if( pRes ) *pRes = 1;
        return SQLITE_OK;
      }
      moveToParent(pCur);
      pPage = pCur->pPage;
    }
    pCur->idx--;
................................................................................
  */
  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
        ** the child, so it might not be able to hold all of the information
        ** in the child.  If this is the case, then do not do the transfer.
        ** Leave page 1 empty except for the right-pointer to the child page.
        ** The child page becomes the virtual root of the tree.
        */


        pgnoChild = get4byte(pPage->aData[pPage->hdrOffset+6]);
        assert( pgnoChild>0 && pgnoChild<=sqlit3pager_pagecount(pBt->pPager) );
        rc = getPage(pBt, pgnoChild, &pChild);
        if( rc ) return rc;
        if( pPage->pgno==1 ){
          rc = initPage(pChild);
          if( rc ) return rc;
          if( pChild->nFree>=100 ){
          }
        }else{
          memcpy(pPage, pChild, SQLITE_USABLE_SIZE);
          pPage->isInit = 0;
          rc = initPage(pBt, pPage, sqlitepager_pagenumber(pPage), 0);
          assert( rc==SQLITE_OK );
          reparentChildPages(pBt, pPage);
        if( pCur && pCur->pPage==pChild ){
          sqlitepager_unref(pChild);
          pCur->pPage = pPage;
          sqlitepager_ref(pPage);
        }
        freePage(pBt, pChild, pgnoChild);
        sqlitepager_unref(pChild);