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.490 2008/07/19 11:49:07 danielk1977 Exp $
**
** This file implements a external (disk-based) database using BTrees.
** See the header comment on "btreeInt.h" for additional information.
** Including a description of file format and an overview of operation.
*/
#include "btreeInt.h"

  if( pPgno ) *pPgno = get4byte(&pPtrmap[offset+1]);

  sqlite3PagerUnref(pDbPage);
  if( *pEType<1 || *pEType>5 ) return SQLITE_CORRUPT_BKPT;
  return SQLITE_OK;
}

#endif /* SQLITE_OMIT_AUTOVACUUM */





/*
** Given a btree page and a cell index (0 means the first cell on
** the page, 1 means the second cell, and so forth) return a pointer
** to the cell content.
**
** This routine works only for pages that do not contain overflow cells.

  ** always fully overwrite deleted information with zeros.
  */
  rc = sqlite3PagerWrite(pPage->pDbPage);
  if( rc ) return rc;
  memset(pPage->aData, 0, pPage->pBt->pageSize);
#endif

#ifndef SQLITE_OMIT_AUTOVACUUM
  /* If the database supports auto-vacuum, write an entry in the pointer-map
  ** to indicate that the page is free.
  */
  if( pBt->autoVacuum ){
    rc = ptrmapPut(pBt, pPage->pgno, PTRMAP_FREEPAGE, 0);
    if( rc ) return rc;
  }
#endif

  if( n==0 ){
    /* This is the first free page */
    rc = sqlite3PagerWrite(pPage->pDbPage);
    if( rc ) return rc;
    memset(pPage->aData, 0, 8);
    put4byte(&pPage1->aData[32], pPage->pgno);

        sqlite3PagerRef(pNewParent->pDbPage);
      }
      pThis->idxParent = idx;
    }
    sqlite3PagerUnref(pDbPage);
  }

#ifndef SQLITE_OMIT_AUTOVACUUM
  if( pBt->autoVacuum && updatePtrmap ){
    return ptrmapPut(pBt, pgno, PTRMAP_BTREE, pNewParent->pgno);
  }

#ifndef NDEBUG
  /* If the updatePtrmap flag was clear, assert that the entry in the
  ** pointer-map is already correct.
  */
  if( pBt->autoVacuum ){
    u8 eType;
    Pgno ii;
    ptrmapGet(pBt, pgno, &eType, &ii);
    assert( ii==pNewParent->pgno && eType==PTRMAP_BTREE );
  }
#endif

#endif
  return SQLITE_OK;
}



/*
** Change the pParent pointer of all children of pPage to point back

  fillInCell(pParent, parentCell, 0, info.nKey, 0, 0, 0, &parentSize);
  assert( parentSize<64 );
  assert( sqlite3PagerIswriteable(pParent->pDbPage) );
  insertCell(pParent, parentIdx, parentCell, parentSize, 0, 4);
  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 ){
      rc = ptrmapPutOvfl(pNew, 0);
    }
    if( rc!=SQLITE_OK ){
      releasePage(pNew);
      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);
}

  int cntNew[NB+2];            /* Index in aCell[] of cell after i-th page */
  int szNew[NB+2];             /* Combined size of cells place on i-th page */
  u8 **apCell = 0;             /* All cells begin balanced */
  u16 *szCell;                 /* Local size of all cells in apCell[] */
  u8 *aCopy[NB];         /* Space for holding data of apCopy[] */
  u8 *aSpace1;           /* Space for copies of dividers cells before balance */
  u8 *aSpace2 = 0;       /* Space for overflow dividers cells after balance */
#ifndef SQLITE_OMIT_AUTOVACUUM
  u8 *aFrom = 0;
#endif

  assert( sqlite3_mutex_held(pPage->pBt->mutex) );

  /* 
  ** Find the parent page.
  */
  assert( pPage->isInit );

  assert( ((aCopy[0] - (u8*)apCell) & 7)==0 ); /* 8-byte alignment required */
  for(i=1; i<NB; i++){
    aCopy[i] = &aCopy[i-1][pBt->pageSize+ROUND8(sizeof(MemPage))];
    assert( ((aCopy[i] - (u8*)apCell) & 7)==0 ); /* 8-byte alignment required */
  }
  aSpace1 = &aCopy[NB-1][pBt->pageSize+ROUND8(sizeof(MemPage))];
  assert( ((aSpace1 - (u8*)apCell) & 7)==0 ); /* 8-byte alignment required */
#ifndef SQLITE_OMIT_AUTOVACUUM
  if( pBt->autoVacuum ){
    aFrom = &aSpace1[pBt->pageSize];
  }
#endif
  aSpace2 = sqlite3PageMalloc(pBt->pageSize);
  if( aSpace2==0 ){
    rc = SQLITE_NOMEM;
    goto balance_cleanup;
  }
  
  /*

  for(i=0; i<nOld; i++){
    MemPage *pOld = apCopy[i];
    int limit = pOld->nCell+pOld->nOverflow;
    for(j=0; j<limit; j++){
      assert( nCell<nMaxCells );
      apCell[nCell] = findOverflowCell(pOld, j);
      szCell[nCell] = cellSizePtr(pOld, apCell[nCell]);
#ifndef SQLITE_OMIT_AUTOVACUUM
      if( pBt->autoVacuum ){
        int a;
        aFrom[nCell] = i;
        for(a=0; a<pOld->nOverflow; a++){
          if( pOld->aOvfl[a].pCell==apCell[nCell] ){
            aFrom[nCell] = 0xFF;
            break;
          }
        }
      }
#endif
      nCell++;
    }
    if( i<nOld-1 ){
      u16 sz = cellSizePtr(pParent, apDiv[i]);
      if( leafData ){
        /* With the LEAFDATA flag, pParent cells hold only INTKEYs that
        ** are duplicates of keys on the child pages.  We need to remove

        szCell[nCell] = sz;
        pTemp = &aSpace1[iSpace1];
        iSpace1 += sz;
        assert( sz<=pBt->pageSize/4 );
        assert( iSpace1<=pBt->pageSize );
        memcpy(pTemp, apDiv[i], sz);
        apCell[nCell] = pTemp+leafCorrection;
#ifndef SQLITE_OMIT_AUTOVACUUM
        if( pBt->autoVacuum ){
          aFrom[nCell] = 0xFF;
        }
#endif
        dropCell(pParent, nxDiv, sz);
        szCell[nCell] -= leafCorrection;
        assert( get4byte(pTemp)==pgnoOld[i] );
        if( !pOld->leaf ){
          assert( leafCorrection==0 );
          /* The right pointer of the child page pOld becomes the left
          ** pointer of the divider cell */

    assert( pNew->nOverflow==0 );

    /* If this is an auto-vacuum database, update the pointer map entries
    ** 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.
    */
#ifndef SQLITE_OMIT_AUTOVACUUM
    if( pBt->autoVacuum ){
      for(k=j; k<cntNew[i]; k++){
        assert( k<nMaxCells );
        if( aFrom[k]==0xFF || apCopy[aFrom[k]]->pgno!=pNew->pgno ){
          rc = ptrmapPutOvfl(pNew, k-j);
          if( rc==SQLITE_OK && leafCorrection==0 ){
            rc = ptrmapPut(pBt, get4byte(apCell[k]), PTRMAP_BTREE, pNew->pgno);
          }
          if( rc!=SQLITE_OK ){
            goto balance_cleanup;
          }
        }
      }
    }
#endif

    j = cntNew[i];

    /* If the sibling page assembled above was not the right-most sibling,
    ** insert a divider cell into the parent page.
    */
    if( i<nNew-1 && j<nCell ){
      u8 *pCell;
      u8 *pTemp;
      int sz;

      assert( j<nMaxCells );
      pCell = apCell[j];
      sz = szCell[j] + leafCorrection;
      pTemp = &aSpace2[iSpace2];
      if( !pNew->leaf ){
        memcpy(&pNew->aData[8], pCell, 4);
#ifndef SQLITE_OMIT_AUTOVACUUM
        if( pBt->autoVacuum 
         && (aFrom[j]==0xFF || apCopy[aFrom[j]]->pgno!=pNew->pgno)
        ){
          rc = ptrmapPut(pBt, get4byte(pCell), PTRMAP_BTREE, pNew->pgno);
          if( rc!=SQLITE_OK ){
            goto balance_cleanup;
          }
        }
#endif
      }else if( leafData ){
        /* If the tree is a leaf-data tree, and the siblings are leaves, 
        ** then there is no divider cell in apCell[]. Instead, the divider 
        ** cell consists of the integer key for the right-most cell of 
        ** the sibling-page assembled above only.
        */
        CellInfo info;

      }
      iSpace2 += sz;
      assert( sz<=pBt->pageSize/4 );
      assert( iSpace2<=pBt->pageSize );
      rc = insertCell(pParent, nxDiv, pCell, sz, pTemp, 4);
      if( rc!=SQLITE_OK ) goto balance_cleanup;
      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++;
    }

#ifndef SQLITE_OMIT_AUTOVACUUM
    /* Set the pointer-map entry for the new sibling page. */
    if( pBt->autoVacuum ){
      rc = ptrmapPut(pBt, pNew->pgno, PTRMAP_BTREE, pParent->pgno);
      if( rc!=SQLITE_OK ){
        goto balance_cleanup;
      }
    }
#endif
  }
  assert( j==nCell );
  assert( nOld>0 );
  assert( nNew>0 );
  if( (pageFlags & PTF_LEAF)==0 ){
    u8 *zChild = &apCopy[nOld-1]->aData[8];
    memcpy(&apNew[nNew-1]->aData[8], zChild, 4);
#ifndef SQLITE_OMIT_AUTOVACUUM
    if( pBt->autoVacuum ){
      rc = ptrmapPut(pBt, get4byte(zChild), PTRMAP_BTREE, apNew[nNew-1]->pgno);
      if( rc!=SQLITE_OK ){
        goto balance_cleanup;
      }
    }
#endif
  }
  if( nxDiv==pParent->nCell+pParent->nOverflow ){
    /* Right-most sibling is the right-most child of pParent */
    put4byte(&pParent->aData[pParent->hdrOffset+8], pgnoNew[nNew-1]);
  }else{
    /* Right-most sibling is the left child of the first entry in pParent
    ** past the right-most divider entry */

      assert( rc==SQLITE_OK );
      freePage(pChild);
      TRACE(("BALANCE: transfer child %d into root %d\n",
              pChild->pgno, pPage->pgno));
    }
    rc = reparentChildPages(pPage, 1);
    assert( pPage->nOverflow==0 );
#ifndef SQLITE_OMIT_AUTOVACUUM
    if( pBt->autoVacuum ){
      int i;
      for(i=0; i<pPage->nCell; i++){ 
        rc = ptrmapPutOvfl(pPage, i);
        if( rc!=SQLITE_OK ){
          goto end_shallow_balance;
        }
      }
    }
#endif
    releasePage(pChild);
  }
end_shallow_balance:
  sqlite3_free(apCell);
  return rc;
}

  if( pChild->nOverflow ){
    pChild->nFree = 0;
  }
  assert( pChild->nCell==pPage->nCell );
  zeroPage(pPage, pChild->aData[0] & ~PTF_LEAF);
  put4byte(&pPage->aData[pPage->hdrOffset+8], pgnoChild);
  TRACE(("BALANCE: copy root %d into %d\n", pPage->pgno, pChild->pgno));
#ifndef SQLITE_OMIT_AUTOVACUUM
  if( pBt->autoVacuum ){
    int i;
    rc = ptrmapPut(pBt, pChild->pgno, PTRMAP_BTREE, pPage->pgno);
    if( rc ) goto balancedeeper_out;
    for(i=0; i<pChild->nCell; i++){
      rc = ptrmapPutOvfl(pChild, i);
      if( rc!=SQLITE_OK ){
        goto balancedeeper_out;
      }
    }
    rc = reparentChildPages(pChild, 1);
  }
#endif
  if( rc==SQLITE_OK ){
    rc = balance_nonroot(pChild);
  }

balancedeeper_out:
  releasePage(pChild);
  return rc;