SQLite

Check-in [35e8e4dcd2]
Login

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

Overview
Comment:Remove the reparentPage() and reparentChildPages() functions from btree.c. All calls to these functions can now be replaced by a call to setChildPtrmaps(). (CVS 5751)
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 35e8e4dcd24b050b535ae005ca3b25e6a673eb89
User & Date: danielk1977 2008-09-29 16:41:32.000
Context
2008-09-30
00:31
A few minor changes to test scripts so that they work on linux-amd64. (CVS 5752) (check-in: 78d075ff38 user: drh tags: trunk)
2008-09-29
16:41
Remove the reparentPage() and reparentChildPages() functions from btree.c. All calls to these functions can now be replaced by a call to setChildPtrmaps(). (CVS 5751) (check-in: 35e8e4dcd2 user: danielk1977 tags: trunk)
15:53
Remove the MemPage.idxShift variable. It is no longer required. (CVS 5750) (check-in: 7354abd03b user: danielk1977 tags: trunk)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/btree.c.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
** 2004 April 6
**
** 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.
**
*************************************************************************
** $Id: btree.c,v 1.519 2008/09/29 15:53:26 danielk1977 Exp $
**
** This file implements a external (disk-based) database using BTrees.
** See the header comment on "btreeInt.h" for additional information.
** Including a description of file format and an overview of operation.
*/
#include "btreeInt.h"












|







1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
** 2004 April 6
**
** 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.
**
*************************************************************************
** $Id: btree.c,v 1.520 2008/09/29 16:41:32 danielk1977 Exp $
**
** This file implements a external (disk-based) database using BTrees.
** See the header comment on "btreeInt.h" for additional information.
** Including a description of file format and an overview of operation.
*/
#include "btreeInt.h"

2053
2054
2055
2056
2057
2058
2059
2060
2061
2062
2063
2064
2065
2066
2067
    if( rc!=SQLITE_OK ){
      goto set_child_ptrmaps_out;
    }

    if( !pPage->leaf ){
      Pgno childPgno = get4byte(pCell);
      rc = ptrmapPut(pBt, childPgno, PTRMAP_BTREE, pgno);
       if( rc!=SQLITE_OK ) goto set_child_ptrmaps_out;
    }
  }

  if( !pPage->leaf ){
    Pgno childPgno = get4byte(&pPage->aData[pPage->hdrOffset+8]);
    rc = ptrmapPut(pBt, childPgno, PTRMAP_BTREE, pgno);
  }







|







2053
2054
2055
2056
2057
2058
2059
2060
2061
2062
2063
2064
2065
2066
2067
    if( rc!=SQLITE_OK ){
      goto set_child_ptrmaps_out;
    }

    if( !pPage->leaf ){
      Pgno childPgno = get4byte(pCell);
      rc = ptrmapPut(pBt, childPgno, PTRMAP_BTREE, pgno);
      if( rc!=SQLITE_OK ) goto set_child_ptrmaps_out;
    }
  }

  if( !pPage->leaf ){
    Pgno childPgno = get4byte(&pPage->aData[pPage->hdrOffset+8]);
    rc = ptrmapPut(pBt, childPgno, PTRMAP_BTREE, pgno);
  }
4535
4536
4537
4538
4539
4540
4541
4542
4543
4544
4545
4546
4547
4548
4549
4550
4551
4552
4553
4554
4555
4556
4557
4558
4559
4560
4561
4562
4563
4564
4565
4566
4567
4568
4569
4570
4571
4572
4573
4574
4575
4576
4577
4578
4579
4580
4581
4582
4583
4584
4585
4586
4587
4588
4589
4590
4591
4592
4593
4594
4595
4596
4597
4598
4599
4600
4601
4602
4603
4604
4605
4606
4607
4608
4609
4610
4611
4612
4613
4614
4615
4616
4617
4618
4619
4620
4621
4622
      pSrc = pData;
    }
  }
  releasePage(pToRelease);
  return SQLITE_OK;
}


/*
** Change the MemPage.pParent pointer on the page whose number is
** given in the second argument so that MemPage.pParent holds the
** pointer in the third argument.
**
** If the final argument, updatePtrmap, is non-zero and the database
** is an auto-vacuum database, then the pointer-map entry for pgno
** is updated.
*/
static int reparentPage(
  BtShared *pBt,                /* B-Tree structure */
  Pgno pgno,                    /* Page number of child being adopted */
  MemPage *pNewParent,          /* New parent of pgno */
  int idx,                      /* Index of child page pgno in pNewParent */
  int updatePtrmap              /* If true, update pointer-map for pgno */
){
  DbPage *pDbPage;
  if( ISAUTOVACUUM && updatePtrmap ){
    return ptrmapPut(pBt, pgno, PTRMAP_BTREE, pNewParent->pgno);
  }

#ifndef NDEBUG
  /* If the updatePtrmap flag was clear, assert that the entry in the
  ** pointer-map is already correct.
  */
  if( ISAUTOVACUUM ){
    pDbPage = sqlite3PagerLookup(pBt->pPager,PTRMAP_PAGENO(pBt,pgno));
    if( pDbPage ){
      u8 eType;
      Pgno ii;
      int rc = ptrmapGet(pBt, pgno, &eType, &ii);
      assert( rc==SQLITE_OK && ii==pNewParent->pgno && eType==PTRMAP_BTREE );
      sqlite3PagerUnref(pDbPage);
    }
  }
#endif

  return SQLITE_OK;
}



/*
** Change the pParent pointer of all children of pPage to point back
** to pPage.
**
** In other words, for every child of pPage, invoke reparentPage()
** to make sure that each child knows that pPage is its parent.
**
** This routine gets called after you memcpy() one page into
** another.
**
** If updatePtrmap is true, then the pointer-map entries for all child
** pages of pPage are updated.
*/
static int reparentChildPages(MemPage *pPage, int updatePtrmap){
  int rc = SQLITE_OK;
  assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  if( !pPage->leaf ){
    int i;
    BtShared *pBt = pPage->pBt;
    Pgno iRight = get4byte(&pPage->aData[pPage->hdrOffset+8]);

    for(i=0; i<pPage->nCell; i++){
      u8 *pCell = findCell(pPage, i);
      rc = reparentPage(pBt, get4byte(pCell), pPage, i, updatePtrmap);
      if( rc!=SQLITE_OK ) return rc;
    }
    rc = reparentPage(pBt, iRight, pPage, i, updatePtrmap);
  }
  return rc;
}

/*
** 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.







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







4535
4536
4537
4538
4539
4540
4541










































































4542
4543
4544
4545
4546
4547
4548
      pSrc = pData;
    }
  }
  releasePage(pToRelease);
  return SQLITE_OK;
}











































































/*
** 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.
5489
5490
5491
5492
5493
5494
5495
5496
5497
5498
5499
5500
5501
5502
5503
5504
5505
5506
5507
5508
5509
5510
5511
5512
5513
5514
5515
5516
5517
5518
5519
5520
5521
5522
5523
5524
5525
5526
5527
5528
5529
5530
5531
5532
5533
5534
5535
5536
5537
5538
5539
5540
5541
5542
5543
5544
    put4byte(&pParent->aData[pParent->hdrOffset+8], pgnoNew[nNew-1]);
  }else{
    /* Right-most sibling is the left child of the first entry in pParent
    ** past the right-most divider entry */
    put4byte(findOverflowCell(pParent, nxDiv), pgnoNew[nNew-1]);
  }

  /*
  ** At this point we used to call reparentChildPages() to make sure that
  ** the MemPage.pParent and MemPage.idxParent variables are correct for
  ** all children of the pages modified by this balance operation. Even
  ** if this is an auto-vacuum database there is no need to update the
  ** pointer-map entries for child pages - that has already been done
  ** by the block above.
  **
  ** However, this is no longer necessary because the MemPage.pParent and
  ** MemPage.idxParent variables are only assumed to be valid when there
  ** are one or more references to the page (when isInit==PAGE_ISINIT_FULL). 
  ** At this point we can account for all references to the pages
  ** manipulated by this function and deduce that it is not necessary to
  ** update these two variables because:
  **
  **   a) it must have been called, directly or indirectly, from BtreeInsert()
  **      or BtreeDelete(). Both these functions call saveAllCursors(), so
  **      we can be sure that there exactly one write-cursor (and no
  **      read-cursors) open on the b-tree being manipulated. No other
  **      cursor may be holding references to any pages in the b-tree.
  **
  **   b) After this function returns, the one open write-cursor will be
  **      moved to point at the root of the table using moveToRoot(). The
  **      code that does this (see BtreeInsert() and BtreeDelete()) ensures
  **      that the MemPage.pParent variables are not used to find the root
  **      page of the b-tree, it is located using BtCursor.pgnoRoot.
  **
  **   c) the other page references are those held by this function, on
  **      the pages in apNew[] and apOld[]. They are about to be released.
  **
  ** Therefore, no need to call reparentChildPages(). This can be a
  ** significant performance boost.
  */
#if 0
  for(i=0; i<nNew; i++){
    rc = reparentChildPages(apNew[i], 0);
    if( rc!=SQLITE_OK ) goto balance_cleanup;
  }
  rc = reparentChildPages(pParent, 0);
  if( rc!=SQLITE_OK ) goto balance_cleanup;
#endif

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







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







5415
5416
5417
5418
5419
5420
5421










































5422
5423
5424
5425
5426
5427
5428
    put4byte(&pParent->aData[pParent->hdrOffset+8], pgnoNew[nNew-1]);
  }else{
    /* Right-most sibling is the left child of the first entry in pParent
    ** past the right-most divider entry */
    put4byte(findOverflowCell(pParent, nxDiv), pgnoNew[nNew-1]);
  }











































  /*
  ** Balance the parent page.  Note that the current page (pPage) might
  ** have been added to the freelist so it might no longer be initialized.
  ** But the parent page will always be initialized.
  */
  assert( pParent->isInit );
  sqlite3ScratchFree(apCell);
5642
5643
5644
5645
5646
5647
5648
5649
5650
5651
5652
5653
5654
5655
5656
5657
5658
5659
5660
5661
5662
5663
5664
5665
      pPage->isInit = 0;
      rc = sqlite3BtreeInitPage(pPage);
      assert( rc==SQLITE_OK );
      freePage(pChild);
      TRACE(("BALANCE: transfer child %d into root %d\n",
              pChild->pgno, pPage->pgno));
    }
    rc = reparentChildPages(pPage, 1);
    assert( pPage->nOverflow==0 );
    if( ISAUTOVACUUM ){
      int i;
      for(i=0; i<pPage->nCell; i++){ 
        rc = ptrmapPutOvfl(pPage, i);
        if( rc!=SQLITE_OK ){
          goto end_shallow_balance;
        }
      }
    }
    releasePage(pChild);
  }
end_shallow_balance:
  sqlite3_free(apCell);
  return rc;
}







<


<
<
|
<
<
<
<







5526
5527
5528
5529
5530
5531
5532

5533
5534


5535




5536
5537
5538
5539
5540
5541
5542
      pPage->isInit = 0;
      rc = sqlite3BtreeInitPage(pPage);
      assert( rc==SQLITE_OK );
      freePage(pChild);
      TRACE(("BALANCE: transfer child %d into root %d\n",
              pChild->pgno, pPage->pgno));
    }

    assert( pPage->nOverflow==0 );
    if( ISAUTOVACUUM ){


      rc = setChildPtrmaps(pPage);




    }
    releasePage(pChild);
  }
end_shallow_balance:
  sqlite3_free(apCell);
  return rc;
}
5712
5713
5714
5715
5716
5717
5718
5719
5720
5721
5722
5723
5724
5725
5726
5727
5728
5729
5730
5731
5732
      pChild->nFree = 0;
    }
    assert( pChild->nCell==pPage->nCell );
    zeroPage(pPage, pChild->aData[0] & ~PTF_LEAF);
    put4byte(&pPage->aData[pPage->hdrOffset+8], pgnoChild);
    TRACE(("BALANCE: copy root %d into %d\n", pPage->pgno, pChild->pgno));
    if( ISAUTOVACUUM ){
      int i;
      rc = ptrmapPut(pBt, pChild->pgno, PTRMAP_BTREE, pPage->pgno);
      for(i=0; rc==SQLITE_OK && i<pChild->nCell; i++){
        rc = ptrmapPutOvfl(pChild, i);
      }
      if( rc==SQLITE_OK ){
        rc = reparentChildPages(pChild, 1);
      }
    }
  }

  if( rc==SQLITE_OK ){
    pCur->iPage++;
    pCur->apPage[1] = pChild;







<

<
<
<

|







5589
5590
5591
5592
5593
5594
5595

5596



5597
5598
5599
5600
5601
5602
5603
5604
5605
      pChild->nFree = 0;
    }
    assert( pChild->nCell==pPage->nCell );
    zeroPage(pPage, pChild->aData[0] & ~PTF_LEAF);
    put4byte(&pPage->aData[pPage->hdrOffset+8], pgnoChild);
    TRACE(("BALANCE: copy root %d into %d\n", pPage->pgno, pChild->pgno));
    if( ISAUTOVACUUM ){

      rc = ptrmapPut(pBt, pChild->pgno, PTRMAP_BTREE, pPage->pgno);



      if( rc==SQLITE_OK ){
        rc = setChildPtrmaps(pChild);
      }
    }
  }

  if( rc==SQLITE_OK ){
    pCur->iPage++;
    pCur->apPage[1] = pChild;