SQLite

**
** This routine works only for pages that do not contain overflow cells.
*/
#define findCell(P,I) \
  ((P)->aData + ((P)->maskPage & get2byte(&(P)->aCellIdx[2*(I)])))
#define findCellv2(D,M,O,I) (D+(M&get2byte(D+(O+2*(I)))))


/*

** Sort the overflow cells of a page into index order.
**
** An O(N*N) algorithm is used.  But that should not be a problem
** since N is only very rarely more than 1.
*/
static void btreeSortOverflow(MemPage *p){
  int j, k;

  for(j=0; j<p->nOverflow-1; j++){
    for(k=j+1; k<p->nOverflow; k++){
      if( p->aiOvfl[j]>p->aiOvfl[k] ){
        SWAP(u16, p->aiOvfl[j], p->aiOvfl[k]);

        SWAP(u8*, p->apOvfl[j], p->apOvfl[k]);
      }

    }
  }

}


/*
** This is common tail processing for btreeParseCellPtr() and
** btreeParseCellPtrIndex() for the case when the cell does not fit entirely
** on a single B-tree page.  Make necessary adjustments to the CellInfo
** structure.
*/

  ** leafCorrection:  4 if pPage is a leaf.  0 if pPage is not a leaf.
  **       leafData:  1 if pPage holds key+data and pParent holds only keys.
  */
  b.pRef = apOld[0];
  leafCorrection = b.pRef->leaf*4;
  leafData = b.pRef->intKeyLeaf;
  for(i=0; i<nOld; i++){

    MemPage *pOld = apOld[i];
    int limit = pOld->nCell;
    u8 *aData = pOld->aData;
    u16 maskPage = pOld->maskPage;
    u16 cellOffset = pOld->cellOffset;

    /* Verify that all sibling pages are of the same "type" (table-leaf,
    ** table-interior, index-leaf, or index-interior).
    */
    if( pOld->aData[0]!=apOld[0]->aData[0] ){
      rc = SQLITE_CORRUPT_BKPT;
      goto balance_cleanup;
    }

    /* Load b.apCell[] with pointers to all cells in pOld.  Intersperse
    ** overflow cells in the correct sequence.  
    **
    ** This must be done in advance.  Once the balance starts, the cell
    ** offset section of the btree page will be overwritten and we will no
    ** long be able to find the cells if a pointer to each cell is not saved
    ** first.
    */
    memset(&b.szCell[b.nCell], 0, sizeof(b.szCell[0])*limit);
    j = 0;
    if( pOld->nOverflow>0 ){
      memset(&b.szCell[b.nCell+limit], 0, sizeof(b.szCell[0])*pOld->nOverflow);
      btreeSortOverflow(pOld);
      for(k=0; k<pOld->nOverflow; k++){
        limit = pOld->aiOvfl[k] - k;
        while( j<limit ){
          b.apCell[b.nCell] = findCellv2(aData, maskPage, cellOffset, j);
          b.nCell++;
          j++;
        }
        b.apCell[b.nCell] = pOld->apOvfl[k];
        b.nCell++;
      }

      limit = pOld->nCell;


    }
    while( j<limit ){
      assert( b.nCell<nMaxCells );
      b.apCell[b.nCell] = findCellv2(aData, maskPage, cellOffset, j);
      b.nCell++;
      j++;
    }

    cntOld[i] = b.nCell;
    if( i<nOld-1 && !leafData){
      u16 sz = (u16)szNew[i];
      u8 *pTemp;
      assert( b.nCell<nMaxCells );
      b.szCell[b.nCell] = sz;
      pTemp = &aSpace1[iSpace1];