SQLite

Check-in [aab4b794b4]
Login

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

Overview
Comment:More speed improvements to btree. (CVS 1384)
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: aab4b794b4238bad5c4a6aee7d4443732921127d
User & Date: drh 2004-05-15 00:29:24.000
Context
2004-05-16
11:15
More changes to support the manifest type model. A few things are currently broken. (CVS 1385) (check-in: a4af838f8d user: danielk1977 tags: trunk)
2004-05-15
00:29
More speed improvements to btree. (CVS 1384) (check-in: aab4b794b4 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: d8bacc1680 user: drh 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.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.












|








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.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.
︙︙
705
706
707
708
709
710
711
712

713
714
715
716
717
718
719

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 );








|
>








705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720

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 );
︙︙
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

  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;
}

/*








>

>


|
|


|


|
<
|
<
<
|
<

<

>
>



>



|


<
|
<
<
<
|
<
<








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

  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;
}

/*
︙︙