SQLite

Check-in [e7ad68e93b]
Login

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

Overview
Comment:Reduce the stack usage of balance_quick(). (CVS 6715)
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: e7ad68e93b19b59cb16205c4b48fd9d6492dbb02
User & Date: danielk1977 2009-06-04 14:46:08.000
Context
2009-06-04
16:14
If the root page of a btree is empty and is also not a leaf page and the page is not page 1, then report database corruption. (CVS 6716) (check-in: 52b02ca5f3 user: drh tags: trunk)
14:46
Reduce the stack usage of balance_quick(). (CVS 6715) (check-in: e7ad68e93b user: danielk1977 tags: trunk)
02:47
Minor updates to comments in test scripts. (CVS 6714) (check-in: 453ff88f73 user: shane 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.613 2009/06/04 00:11:56 drh 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.614 2009/06/04 14:46:08 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"

1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
        sz = cellSizePtr(pPage, &data[pc]);
        if( pc+sz>usableSize ){
          return SQLITE_CORRUPT_BKPT;
        }
      }
    }  
#endif


    /* Compute the total free space on the page */
    pc = get2byte(&data[hdr+1]);
    nFree = data[hdr+7] + top;
    while( pc>0 ){
      u16 next, size;
      if( pc>usableSize-4 ){







<







1168
1169
1170
1171
1172
1173
1174

1175
1176
1177
1178
1179
1180
1181
        sz = cellSizePtr(pPage, &data[pc]);
        if( pc+sz>usableSize ){
          return SQLITE_CORRUPT_BKPT;
        }
      }
    }  
#endif


    /* Compute the total free space on the page */
    pc = get2byte(&data[hdr+1]);
    nFree = data[hdr+7] + top;
    while( pc>0 ){
      u16 next, size;
      if( pc>usableSize-4 ){
5194
5195
5196
5197
5198
5199
5200
5201
5202
5203
5204
5205
5206
5207
5208
5209
5210
5211
5212

5213
5214

5215
5216
5217
5218
5219

5220









5221
5222


5223
5224
5225
5226
5227
5228
5229

5230
5231
5232
5233
5234
5235
5236
5237
5238
5239
5240
5241
5242
5243
5244

5245

5246
5247
5248
5249

5250
5251
5252
5253
5254
5255
5256
** fill up.  On average.
**
** pPage is the leaf page which is the right-most page in the tree.
** pParent is its parent.  pPage must have a single overflow entry
** which is also the right-most entry on the page.
*/
static int balance_quick(BtCursor *pCur){
  int rc;
  MemPage *pNew = 0;
  Pgno pgnoNew;
  u8 *pCell;
  u16 szCell;
  CellInfo info;
  MemPage *pPage = pCur->apPage[pCur->iPage];
  MemPage *pParent = pCur->apPage[pCur->iPage-1];
  BtShared *pBt = pPage->pBt;
  int parentIdx = pParent->nCell;   /* pParent new divider cell index */
  int parentSize;                   /* Size of new divider cell */
  u8 parentCell[64];                /* Space for the new divider cell */


  assert( sqlite3_mutex_held(pPage->pBt->mutex) );


  /* Allocate a new page. Insert the overflow cell from pPage
  ** into it. Then remove the overflow cell from pPage.
  */
  rc = allocateBtreePage(pBt, &pNew, &pgnoNew, 0, 0);

  if( rc==SQLITE_OK ){









    pCell = pPage->aOvfl[0].pCell;
    szCell = cellSizePtr(pPage, pCell);


    assert( sqlite3PagerIswriteable(pNew->pDbPage) );
    zeroPage(pNew, pPage->aData[0]);
    assemblePage(pNew, 1, &pCell, &szCell);
    pPage->nOverflow = 0;
  
    /* pPage is currently the right-child of pParent. Change this
    ** so that the right-child is the new page allocated above and

    ** pPage is the next-to-right child. 
    **
    ** Ignore the return value of the call to fillInCell(). fillInCell()
    ** may only return other than SQLITE_OK if it is required to allocate
    ** one or more overflow pages. Since an internal table B-Tree cell 
    ** may never spill over onto an overflow page (it is a maximum of 
    ** 13 bytes in size), it is not neccessary to check the return code.
    **
    ** Similarly, the insertCell() function cannot fail if the page
    ** being inserted into is already writable and the cell does not 
    ** contain an overflow pointer. So ignore this return code too.
    */
    assert( pPage->nCell>0 );
    pCell = findCell(pPage, pPage->nCell-1);
    sqlite3BtreeParseCellPtr(pPage, pCell, &info);

    fillInCell(pParent, parentCell, 0, info.nKey, 0, 0, 0, &parentSize);

    assert( parentSize<64 );
    assert( sqlite3PagerIswriteable(pParent->pDbPage) );
    insertCell(pParent, parentIdx, parentCell, parentSize, 0, 4);
    put4byte(findOverflowCell(pParent,parentIdx), pPage->pgno);

    put4byte(&pParent->aData[pParent->hdrOffset+8], pgnoNew);
  
    /* If this is an auto-vacuum database, update the pointer map
    ** with entries for the new page, and any pointer from the 
    ** cell on the page to an overflow page.
    */
    if( ISAUTOVACUUM ){







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


>

|
<
<

>

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





|
|
>
|

|
<
|
|
|
|
|
|
<

|

|
>
|
>
|
|
|
|
>







5193
5194
5195
5196
5197
5198
5199






5200

5201

5202
5203
5204
5205
5206
5207
5208
5209


5210
5211
5212
5213
5214
5215
5216
5217
5218
5219
5220
5221
5222
5223
5224
5225
5226
5227
5228
5229
5230
5231
5232
5233
5234
5235
5236

5237
5238
5239
5240
5241
5242

5243
5244
5245
5246
5247
5248
5249
5250
5251
5252
5253
5254
5255
5256
5257
5258
5259
5260
5261
** fill up.  On average.
**
** pPage is the leaf page which is the right-most page in the tree.
** pParent is its parent.  pPage must have a single overflow entry
** which is also the right-most entry on the page.
*/
static int balance_quick(BtCursor *pCur){






  MemPage *const pPage = pCur->apPage[pCur->iPage];

  BtShared *const pBt = pCur->pBt;

  MemPage *pNew = 0;                   /* Newly allocated page */
  int rc;                              /* Return Code */
  Pgno pgnoNew;                        /* Page number of pNew */

  assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  assert( pPage->nCell>0 );

  /* Allocate a new page. This page will become the right-sibling of pPage */


  rc = allocateBtreePage(pBt, &pNew, &pgnoNew, 0, 0);

  if( rc==SQLITE_OK ){
    /* The parentCell buffer is used to store a temporary copy of the divider
    ** cell that will be inserted into pParent. Such a cell consists of a 4
    ** byte page number followed by a variable length integer. In other
    ** words, at most 13 bytes. Hence the parentCell buffer must be at
    ** least 13 bytes in size.
    */
    MemPage * const pParent = pCur->apPage[pCur->iPage-1];
    u8 parentCell[13];
    u8 *pOut = &parentCell[4];
    u8 *pCell = pPage->aOvfl[0].pCell;
    u16 szCell = cellSizePtr(pPage, pCell);
    u8 *pStop;

    assert( sqlite3PagerIswriteable(pNew->pDbPage) );
    zeroPage(pNew, pPage->aData[0]);
    assemblePage(pNew, 1, &pCell, &szCell);
    pPage->nOverflow = 0;
  
    /* Create a divider cell to insert into pParent. The divider cell
    ** consists of a 4-byte page number (the page number of pPage) and
    ** a variable length key value (which must be the same value as the
    ** largest key on pPage).
    **
    ** To find the largest key value on pPage, first find the right-most 

    ** cell on pPage. The first two fields of this cell are the 
    ** record-length (a variable length integer at most 32-bits in size)
    ** and the key value (a variable length integer, may have any value).
    ** The first of the while(...) loops below skips over the record-length
    ** field. The second while(...) loop copies the key value from the
    ** cell on pPage into the parentCell buffer.

    */
    put4byte(parentCell, pPage->pgno);
    pCell = findCell(pPage, pPage->nCell-1);
    pStop = &pCell[9];
    while( (*(pCell++)&0x80) && pCell<pStop );
    pStop = &pCell[9];
    while( ((*(pOut++) = *(pCell++))&0x80) && pCell<pStop );

    /* Insert the new divider cell into pParent */
    insertCell(pParent, pParent->nCell, parentCell, pOut-parentCell, 0, 0);

    /* Set the right-child pointer of pParent to point to the new page. */
    put4byte(&pParent->aData[pParent->hdrOffset+8], pgnoNew);
  
    /* If this is an auto-vacuum database, update the pointer map
    ** with entries for the new page, and any pointer from the 
    ** cell on the page to an overflow page.
    */
    if( ISAUTOVACUUM ){
5638
5639
5640
5641
5642
5643
5644
5645
5646
5647
5648
5649
5650
5651
5652
      r = cntNew[i-1] - 1;
      d = r + 1 - leafData;
    }
    szNew[i] = szRight;
    szNew[i-1] = szLeft;
  }

  /* Either we found one or more cells (cntnew[0])>0) or we are the
  ** a virtual root page.  A virtual root page is when the real root
  ** page is page 1 and we are the only child of that page.
  */
  assert( cntNew[0]>0 || (pParent->pgno==1 && pParent->nCell==0) );

  /*
  ** Allocate k new pages.  Reuse old pages where possible.







|







5643
5644
5645
5646
5647
5648
5649
5650
5651
5652
5653
5654
5655
5656
5657
      r = cntNew[i-1] - 1;
      d = r + 1 - leafData;
    }
    szNew[i] = szRight;
    szNew[i-1] = szLeft;
  }

  /* Either we found one or more cells (cntnew[0])>0) or pPage is
  ** a virtual root page.  A virtual root page is when the real root
  ** page is page 1 and we are the only child of that page.
  */
  assert( cntNew[0]>0 || (pParent->pgno==1 && pParent->nCell==0) );

  /*
  ** Allocate k new pages.  Reuse old pages where possible.