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.67 2002/07/08 10:59:51 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.

** has already been called on the new page.)  The new page has also
** been referenced and the calling routine is responsible for calling
** sqlitepager_unref() on the new page when it is done.
**
** SQLITE_OK is returned on success.  Any other return value indicates
** an error.  *ppPage and *pPgno are undefined in the event of an error.
** Do not invoke sqlitepager_unref() on *ppPage if an error is returned.
**
** If the "near" parameter is not 0, then a (feeble) effort is made to 
** locate a page close to the page number "near".  This can be used in an
** attempt to keep related pages close to each other in the database file,
** which in turn can make database access faster.
*/
static int allocatePage(Btree *pBt, MemPage **ppPage, Pgno *pPgno, Pgno near){
  PageOne *pPage1 = pBt->page1;
  int rc;
  if( pPage1->freeList ){
    OverflowPage *pOvfl;
    FreelistInfo *pInfo;

    rc = sqlitepager_write(pPage1);

    }
    pInfo = (FreelistInfo*)pOvfl->aPayload;
    if( pInfo->nFree==0 ){
      *pPgno = pPage1->freeList;
      pPage1->freeList = pOvfl->iNext;
      *ppPage = (MemPage*)pOvfl;
    }else{
      int closest;
      if( pInfo->nFree>1 && near>0 ){
        int i, dist;
        closest = 0;
        dist = pInfo->aFree[0] - near;
        if( dist<0 ) dist = -dist;
        for(i=1; i<pInfo->nFree; i++){
          int d2 = pInfo->aFree[i] - near;
          if( d2<0 ) d2 = -d2;
          if( d2<dist ) closest = i;
        }
      }else{
        closest = 0;
      }
      pInfo->nFree--;
      *pPgno = pInfo->aFree[closest];
      pInfo->aFree[closest] = pInfo->aFree[pInfo->nFree];
      rc = sqlitepager_get(pBt->pPager, *pPgno, (void**)ppPage);
      sqlitepager_unref(pOvfl);
      if( rc==SQLITE_OK ){
        sqlitepager_dont_rollback(*ppPage);
        rc = sqlitepager_write(*ppPage);
      }
    }

  OverflowPage *pOvfl, *pPrior;
  Pgno *pNext;
  int spaceLeft;
  int n, rc;
  int nPayload;
  const char *pPayload;
  char *pSpace;
  Pgno near = 0;

  pCell->h.leftChild = 0;
  pCell->h.nKey = nKey & 0xffff;
  pCell->h.nKeyHi = nKey >> 16;
  pCell->h.nData = nData & 0xffff;
  pCell->h.nDataHi = nData >> 16;
  pCell->h.iNext = 0;

  pNext = &pCell->ovfl;
  pSpace = pCell->aPayload;
  spaceLeft = MX_LOCAL_PAYLOAD;
  pPayload = pKey;
  pKey = 0;
  nPayload = nKey;
  pPrior = 0;
  while( nPayload>0 ){
    if( spaceLeft==0 ){
      rc = allocatePage(pBt, (MemPage**)&pOvfl, pNext, near);
      if( rc ){
        *pNext = 0;
      }else{
        near = *pNext;
      }
      if( pPrior ) sqlitepager_unref(pPrior);
      if( rc ){
        clearCell(pBt, pCell);
        return rc;
      }
      pPrior = pOvfl;

    ** contents of the root into the child.  Then make the root
    ** page an empty page with rightChild pointing to the new
    ** child.  Then fall thru to the code below which will cause
    ** the overfull child page to be split.
    */
    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;
    sqlitepager_ref(pPage);
    pChild->isOverfull = 1;
    if( pCur && pCur->pPage==pPage ){

  for(i=0; i<k; i++){
    if( i<nOld ){
      apNew[i] = apOld[i];
      pgnoNew[i] = pgnoOld[i];
      apOld[i] = 0;
      sqlitepager_write(apNew[i]);
    }else{
      rc = allocatePage(pBt, &apNew[i], &pgnoNew[i], pgnoNew[i-1]);
      if( rc ) goto balance_cleanup;
    }
    nNew++;
    zeroPage(apNew[i]);
    apNew[i]->isInit = 1;
  }

  int rc;
  if( !pBt->inTrans ){
    return SQLITE_ERROR;  /* Must start a transaction first */
  }
  if( pBt->readOnly ){
    return SQLITE_READONLY;
  }
  rc = allocatePage(pBt, &pRoot, &pgnoRoot, 0);
  if( rc ) return rc;
  assert( sqlitepager_iswriteable(pRoot) );
  zeroPage(pRoot);
  sqlitepager_unref(pRoot);
  *piTable = (int)pgnoRoot;
  return SQLITE_OK;
}