SQLite

/*
** 2001 September 15
**
** 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.77 2003/01/04 16:48:09 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.

  int rc;                      /* The return code */
  int iCur;                    /* apCell[iCur] is the cell of the cursor */
  MemPage *pOldCurPage;        /* The cursor originally points to this page */
  int subtotal;                /* Subtotal of bytes in cells on one page */
  int cntNew[4];               /* Index in apCell[] of cell after i-th page */
  int szNew[4];                /* Combined size of cells place on i-th page */
  MemPage *extraUnref = 0;     /* A page that needs to be unref-ed */
  Pgno pgno, swabPgno;         /* Page number */
  Cell *apCell[MX_CELL*3+5];   /* All cells from pages being balanceed */
  int szCell[MX_CELL*3+5];     /* Local size of all cells */
  Cell aTemp[2];               /* Temporary holding area for apDiv[] */
  MemPage aOld[3];             /* Temporary copies of pPage and its siblings */

  /* 
  ** Return without doing any work if pPage is neither overfull nor

    rc = sqlitepager_write(pPage);
    if( rc ) return rc;
    rc = allocatePage(pBt, &pChild, &pgnoChild, sqlitepager_pagenumber(pPage));
    if( rc ) return rc;
    assert( sqlitepager_iswriteable(pChild) );
    copyPage(pChild, pPage);
    pChild->pParent = pPage;
    pChild->idxParent = pChild->nCell;
    sqlitepager_ref(pPage);
    pChild->isOverfull = 1;
    if( pCur && pCur->pPage==pPage ){
      sqlitepager_unref(pPage);
      pCur->pPage = pChild;
    }else{
      extraUnref = pChild;

  assert( pParent->isInit );
  
  /*
  ** Find the Cell in the parent page whose h.leftChild points back
  ** to pPage.  The "idx" variable is the index of that cell.  If pPage
  ** is the rightmost child of pParent then set idx to pParent->nCell 
  */
  idx = -1;

  pgno = sqlitepager_pagenumber(pPage);
  swabPgno = SWAB32(pBt, pgno);
  for(i=0; i<pParent->nCell; i++){
    if( pParent->apCell[i]->h.leftChild==swabPgno ){
      idx = i;
      break;
    }
  }
  if( idx<0 && pParent->u.hdr.rightChild==swabPgno ){

    idx = pParent->nCell;
  }
  assert( idx>=0 );
  /* assert( pParent->idxShift || idx==pPage->idxParent ); */

  /*
  ** Initialize variables so that it will be safe to jump
  ** directly to balance_cleanup at any moment.
  */
  nOld = nNew = 0;
  sqlitepager_ref(pParent);