SQLite

/*
** 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.234 2005/01/15 12:45:51 danielk1977 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.

#endif
static int cellSizePtr(MemPage *pPage, u8 *pCell){
  CellInfo info;
  parseCellPtr(pPage, pCell, &info);
  return info.nSize;
}


/*

** If pCell, part of pPage, contains a pointer to an overflow page,
** return the overflow page number. Otherwise return 0.
*/
static Pgno ovflPagePtr(MemPage *pPage, u8 *pCell){



  CellInfo info;
  parseCellPtr(pPage, pCell, &info);
  if( (info.nData+(pPage->intKey?0:info.nKey))>info.nLocal ){
    return get4byte(&pCell[info.iOverflow]);

  }

  return 0;
}



/*
** Do sanity checking on a page.  Throw an exception if anything is
** not right.
**
** This routine is used for internal error checking only.  It is omitted
** from most builds.

  int rc;
  MemPage *pNew;
  Pgno pgnoNew;
  u8 *pCell;
  int szCell;
  CellInfo info;
  Btree *pBt = pPage->pBt;

  u8 parentCell[64];              /* How big should this be? */
  int parentIdx = pParent->nCell;
  int parentSize;


  /* Allocate a new page. Insert the overflow cell from pPage
  ** into it. Then remove the overflow cell from pPage.
  */
  rc = allocatePage(pBt, &pNew, &pgnoNew, 0, 0);
  if( rc!=SQLITE_OK ){
    return rc;
  }
  pCell = pPage->aOvfl[0].pCell;
  szCell = cellSizePtr(pPage, pCell);
  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. Then balance() the parent
  ** page, in case it is now overfull.
  */
  assert( pPage->nCell>0 );
  parseCellPtr(pPage, findCell(pPage, pPage->nCell-1), &info);
  rc = fillInCell(pParent, parentCell, 0, info.nKey, 0, 0, &parentSize);
  if( rc!=SQLITE_OK ){
    return SQLITE_OK;
  }
  assert( parentSize<64 );
  rc = insertCell(pParent, parentIdx, parentCell, parentSize, 0, 4);
  if( rc!=SQLITE_OK ){
    return SQLITE_OK;
  }
  put4byte(findOverflowCell(pParent,parentIdx), pPage->pgno);
  put4byte(&pParent->aData[pParent->hdrOffset+8], pgnoNew);

  pNew->pParent = pParent;


  sqlite3pager_ref(pParent->aData);

  if( pBt->autoVacuum ){
    rc = ptrmapPut(pBt, pgnoNew, PTRMAP_BTREE, pParent->pgno);
    if( rc!=SQLITE_OK ){
      return rc;
    }
    pCell = findCell(pNew, 0);
    parseCellPtr(pNew, pCell, &info);
    if( info.nData>info.nLocal ){
      Pgno pgnoOvfl = get4byte(&pCell[info.iOverflow]);
      rc = ptrmapPut(pBt, pgnoOvfl, PTRMAP_OVERFLOW1, pgnoNew);
      if( rc!=SQLITE_OK ){
        return rc;
      }
    }

  }



  releasePage(pNew);
  return balance(pParent, 0);
}

/*
** The ISAUTOVACUUM macro is used within balance_nonroot() to determine
** if the database supports auto-vacuum or not. Because it is used

    ** that point to the siblings that were rearranged. These can be: left
    ** children of cells, the right-child of the page, or overflow pages
    ** pointed to by cells.
    */
    if( pBt->autoVacuum ){
      for(k=j; k<cntNew[i]; k++){
        if( aFrom[k]==0xFF || apCopy[aFrom[k]]->pgno!=pNew->pgno ){
          Pgno ovfl = ovflPagePtr(pNew, findCell(pNew, k-j));
          if( ovfl ){
            rc = ptrmapPut(pBt, ovfl, PTRMAP_OVERFLOW1, pNew->pgno);
            if( rc!=SQLITE_OK ){
              goto balance_cleanup;
            }
          }
        }
      }
    }
#endif

    j = cntNew[i];

      put4byte(findOverflowCell(pParent,nxDiv), pNew->pgno);
#ifndef SQLITE_OMIT_AUTOVACUUM
      /* If this is an auto-vacuum database, and not a leaf-data tree,
      ** then update the pointer map with an entry for the overflow page
      ** that the cell just inserted points to (if any).
      */
      if( pBt->autoVacuum && !leafData ){
        Pgno ovfl = ovflPagePtr(pParent, findOverflowCell(pParent, nxDiv));
        if( ovfl ){
          rc = ptrmapPut(pBt, ovfl, PTRMAP_OVERFLOW1, pParent->pgno);
          if( rc!=SQLITE_OK ){
            goto balance_cleanup;
          }
        }
      }
#endif
      j++;
      nxDiv++;
    }
  }

              pChild->pgno, pPage->pgno));
    }
    rc = reparentChildPages(pPage);
    assert( pPage->nOverflow==0 );
#ifndef SQLITE_OMIT_AUTOVACUUM
    if( pBt->autoVacuum ){
      for(i=0; i<pPage->nCell; i++){ 
        Pgno ovfl = ovflPagePtr(pPage, findCell(pPage, i));
        if( ovfl ){
          rc = ptrmapPut(pBt, ovfl, PTRMAP_OVERFLOW1, pPage->pgno);
          if( rc!=SQLITE_OK ){
            goto end_shallow_balance;
          } 
        }
      }
    }
#endif
    if( rc!=SQLITE_OK ) goto end_shallow_balance;
    releasePage(pChild);
  }

  put4byte(&pPage->aData[pPage->hdrOffset+8], pgnoChild);
  TRACE(("BALANCE: copy root %d into %d\n", pPage->pgno, pChild->pgno));
  if( pBt->autoVacuum ){
    int i;
    rc = ptrmapPut(pBt, pChild->pgno, PTRMAP_BTREE, pPage->pgno);
    if( rc ) return rc;
    for(i=0; i<pChild->nCell; i++){
      Pgno pgno = ovflPagePtr(pChild, findOverflowCell(pChild, i));
      if( pgno ){ 
        rc = ptrmapPut(pBt, pgno, PTRMAP_OVERFLOW1, pChild->pgno);
        if( rc ) return rc;
      }
    }
  }
  rc = balance_nonroot(pChild);
  releasePage(pChild);
  return rc;
}