/ Check-in [e7ad68e9]
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 | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:e7ad68e93b19b59cb16205c4b48fd9d6492dbb02
User & Date: danielk1977 2009-06-04 14:46:08
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: 52b02ca5 user: drh tags: trunk
14:46
Reduce the stack usage of balance_quick(). (CVS 6715) check-in: e7ad68e9 user: danielk1977 tags: trunk
02:47
Minor updates to comments in test scripts. (CVS 6714) check-in: 453ff88f user: shane 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
....
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
....
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
....
5638
5639
5640
5641
5642
5643
5644
5645
5646
5647
5648
5649
5650
5651
5652
** 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"

................................................................................
        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 ){
................................................................................
** 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 ){
................................................................................
      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.







|







 







<







 







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


>

<
<
<
>

>

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





|
|
|
>

<
|
|
|
|
|
|
|
<

<
>

>
|
|
|
<
>
|
|
>
>







 







|







5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
....
1168
1169
1170
1171
1172
1173
1174

1175
1176
1177
1178
1179
1180
1181
....
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
....
5643
5644
5645
5646
5647
5648
5649
5650
5651
5652
5653
5654
5655
5656
5657
** 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"

................................................................................
        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 ){
................................................................................
** 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 ){
................................................................................
      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.