/ Check-in [aab4b794]
Login

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

Overview
Comment:More speed improvements to btree. (CVS 1384)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: aab4b794b4238bad5c4a6aee7d4443732921127d
User & Date: drh 2004-05-15 00:29:24
Context
2004-05-16
11:15
More changes to support the manifest type model. A few things are currently broken. (CVS 1385) check-in: a4af838f user: danielk1977 tags: trunk
2004-05-15
00:29
More speed improvements to btree. (CVS 1384) check-in: aab4b794 user: drh tags: trunk
2004-05-14
21:59
Allocates VDBE cursors one by one in separate memory so that pointers to cursors can persist through a realloc(). (CVS 1383) check-in: d8bacc16 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
...
705
706
707
708
709
710
711
712

713
714
715
716
717
718
719
...
735
736
737
738
739
740
741

742

743
744
745
746

747
748
749
750
751
752
753
754
755
756
757
758
759
760
761


762
763
764

765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
** 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.139 2004/05/14 21:12:23 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.
................................................................................
static int initPage(
  MemPage *pPage,        /* The page to be initialized */
  MemPage *pParent       /* The parent.  Might be NULL */
){
  int c, pc, i, hdr;
  unsigned char *data;
  int usableSize;
  /* int sumCell = 0;       // Total size of all cells */



  assert( pPage->pBt!=0 );
  assert( pParent==0 || pParent->pBt==pPage->pBt );
  assert( pPage->pgno==sqlite3pager_pagenumber(pPage->aData) );
  assert( pPage->aData == &((unsigned char*)pPage)[-pPage->pBt->pageSize] );
  assert( pPage->pParent==0 || pPage->pParent==pParent );
................................................................................
  pPage->hasData = !(pPage->zeroData || (!pPage->leaf && pPage->leafData));
  pPage->isOverfull = 0;
  pPage->needRelink = 0;
  pPage->idxShift = 0;
  usableSize = pPage->pBt->usableSize;

  /* Initialize the cell count and cell pointers */

  pc = get2byte(&data[hdr+3]);

  while( pc>0 ){
    if( pc>=usableSize ) return SQLITE_CORRUPT;
    if( pPage->nCell>usableSize ) return SQLITE_CORRUPT;
    pPage->nCell++;

    pc = get2byte(&data[pc]);
  }
  if( resizeCellArray(pPage, pPage->nCell) ){
    return SQLITE_NOMEM;
  }
  pc = get2byte(&data[hdr+3]);
  for(i=0; pc>0; i++){
    pPage->aCell[i] = &data[pc];
    /* sumCell += cellSize(pPage, &data[pc]); */
    pc = get2byte(&data[pc]);
  }

  /* Compute the total free space on the page */
  pPage->nFree = data[hdr+5];
  pc = get2byte(&data[hdr+1]);


  while( pc>0 ){
    int next, size;
    if( pc>=usableSize ) return SQLITE_CORRUPT;

    next = get2byte(&data[pc]);
    size = get2byte(&data[pc+2]);
    if( next>0 && next<=pc+size+3 ) return SQLITE_CORRUPT;
    pPage->nFree += size;
    pc = next;
  }
  if( pPage->nFree>=usableSize ) 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 != usableSize ){
    return SQLITE_CORRUPT;
  }
  */

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

/*







|







 







|
>







 







>

>


|
<
>


|


<
<
|
|
<
|
<

<

>
>



>



|


|
<
<
<
<
|
<
<







5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
...
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
...
736
737
738
739
740
741
742
743
744
745
746
747
748

749
750
751
752
753
754


755
756

757

758

759
760
761
762
763
764
765
766
767
768
769
770
771
772




773


774
775
776
777
778
779
780
** 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.140 2004/05/15 00:29:24 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.
................................................................................
static int initPage(
  MemPage *pPage,        /* The page to be initialized */
  MemPage *pParent       /* The parent.  Might be NULL */
){
  int c, pc, i, hdr;
  unsigned char *data;
  int usableSize;
  int nCell, nFree;
  u8 *aCell[MX_PAGE_SIZE/2];


  assert( pPage->pBt!=0 );
  assert( pParent==0 || pParent->pBt==pPage->pBt );
  assert( pPage->pgno==sqlite3pager_pagenumber(pPage->aData) );
  assert( pPage->aData == &((unsigned char*)pPage)[-pPage->pBt->pageSize] );
  assert( pPage->pParent==0 || pPage->pParent==pParent );
................................................................................
  pPage->hasData = !(pPage->zeroData || (!pPage->leaf && pPage->leafData));
  pPage->isOverfull = 0;
  pPage->needRelink = 0;
  pPage->idxShift = 0;
  usableSize = pPage->pBt->usableSize;

  /* Initialize the cell count and cell pointers */
  i = 0;
  pc = get2byte(&data[hdr+3]);
  nCell = 0;
  while( pc>0 ){
    if( pc>=usableSize ) return SQLITE_CORRUPT;
    if( nCell>sizeof(aCell)/sizeof(aCell[0]) ) return SQLITE_CORRUPT;

    aCell[nCell++] = &data[pc];
    pc = get2byte(&data[pc]);
  }
  if( resizeCellArray(pPage, nCell) ){
    return SQLITE_NOMEM;
  }


  pPage->nCell = nCell;
  memcpy(pPage->aCell, aCell, nCell*sizeof(aCell[0]));



  /* Compute the total free space on the page */

  pc = get2byte(&data[hdr+1]);
  nFree = data[hdr+5];
  i = 0;
  while( pc>0 ){
    int next, size;
    if( pc>=usableSize ) return SQLITE_CORRUPT;
    if( i++>MX_PAGE_SIZE ) return SQLITE_CORRUPT;
    next = get2byte(&data[pc]);
    size = get2byte(&data[pc+2]);
    if( next>0 && next<=pc+size+3 ) return SQLITE_CORRUPT;
    nFree += size;
    pc = next;
  }
  pPage->nFree = nFree;




  if( nFree>=usableSize ) return SQLITE_CORRUPT;



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

/*