** 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;
}

** 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.235 2005/01/16 08:00:01 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;
}

#ifndef SQLITE_OMIT_AUTOVACUUM
/*

** If the cell with index iCell on page pPage contains a pointer
** to an overflow page, insert an entry into the pointer-map
** for the overflow page.
*/

static int ptrmapPutOvfl(MemPage *pPage, int iCell){
  u8 *pCell;
  pCell = findOverflowCell(pPage, iCell);
  if( pCell ){
    CellInfo info;
    parseCellPtr(pPage, pCell, &info);
    if( (info.nData+(pPage->intKey?0:info.nKey))>info.nLocal ){
      Pgno ovfl = get4byte(&pCell[info.iOverflow]);
      return ptrmapPut(pPage->pBt, ovfl, PTRMAP_OVERFLOW1, pPage->pgno);
    }
  }
  return SQLITE_OK;
}
#endif


/*
** 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;


  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 */

  /* 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;

  /* Set the parent of the newly allocated page to pParent. */
  pNew->pParent = pParent;
  sqlite3pager_ref(pParent->aData);

  /* 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. 

  */
  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 rc;
  }
  assert( parentSize<64 );
  rc = insertCell(pParent, parentIdx, parentCell, parentSize, 0, 4);
  if( rc!=SQLITE_OK ){
    return rc;
  }
  put4byte(findOverflowCell(pParent,parentIdx), pPage->pgno);
  put4byte(&pParent->aData[pParent->hdrOffset+8], pgnoNew);

#ifndef SQLITE_OMIT_AUTOVACUUM
  /* 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( pBt->autoVacuum ){
    rc = ptrmapPut(pBt, pgnoNew, PTRMAP_BTREE, pParent->pgno);
    if( rc!=SQLITE_OK ){
      return rc;
    }
    rc = ptrmapPutOvfl(pNew, 0);




    if( rc!=SQLITE_OK ){
      return rc;
    }
  }
#endif


  /* Release the reference to the new page and balance the parent page,
  ** in case the divider cell inserted caused it to become overfull.
  */
  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 ){
          rc = ptrmapPutOvfl(pNew, k-j);


          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 ){
        rc = ptrmapPutOvfl(pParent, nxDiv);


        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++){ 
        rc = ptrmapPutOvfl(pPage, i);


        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++){
      rc = ptrmapPutOvfl(pChild, i);
      if( rc!=SQLITE_OK ){

        return rc;
      }
    }
  }
  rc = balance_nonroot(pChild);
  releasePage(pChild);
  return rc;
}