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.366 2007/05/02 16:48:37 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.

  int idx;                  /* Index of the entry in pPage->aCell[] */
  CellInfo info;            /* A parse of the cell we are pointing at */
  u8 wrFlag;                /* True if writable */
  u8 eState;                /* One of the CURSOR_XXX constants (see below) */
  void *pKey;      /* Saved key that was cursor's last known position */
  i64 nKey;        /* Size of pKey, or last integer key */
  int skip;        /* (skip<0) -> Prev() is a no-op. (skip>0) -> Next() is */
#ifndef SQLITE_OMIT_INCRBLOB
  u8 cacheOverflow;         /* True to use aOverflow */
  Pgno *aOverflow;          /* Cache of overflow page locations */
#endif
};

/*
** Potential values for BtCursor.eState.
**
** CURSOR_VALID:
**   Cursor points to a valid entry. getPayload() etc. may be called.

  assert( !pCur->pPage->intKey || !pCur->pKey );

  if( rc==SQLITE_OK ){
    releasePage(pCur->pPage);
    pCur->pPage = 0;
    pCur->eState = CURSOR_REQUIRESEEK;
  }

#ifndef SQLITE_OMIT_INCRBLOB
  /* Delete the cache of overflow page numbers. */
  sqliteFree(pCur->aOverflow);
  pCur->aOverflow = 0;
#endif

  return rc;
}

/*
** Save the positions of all cursors except pExcept open on the table 
** with root-page iRoot. Usually, this is called just before cursor

**
** If the incremental vacuum is finished after this function has run,
** SQLITE_DONE is returned. If it is not finished, but no error occured,
** SQLITE_OK is returned. Otherwise an SQLite error code. 
*/
int sqlite3BtreeIncrVacuum(Btree *p){
  BtShared *pBt = p->pBt;
  BtCursor *pCur;

  assert( pBt->inTransaction==TRANS_WRITE && p->inTrans==TRANS_WRITE );
  if( !pBt->autoVacuum ){
    return SQLITE_DONE;
  }
#ifndef SQLITE_OMIT_INCRBLOB
  for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){
    /* Delete the cache of overflow page numbers. */
    sqliteFree(pCur->aOverflow);
    pCur->aOverflow = 0;
  }
#endif
  return incrVacuumStep(pBt, 0);
}

/*
** This routine is called prior to sqlite3PagerCommit when a transaction
** is commited for an auto-vacuum database.
**
** If SQLITE_OK is returned, then *pnTrunc is set to the number of pages
** the database file should be truncated to during the commit process. 
** i.e. the database has been reorganized so that only the first *pnTrunc
** pages are in use.
*/
static int autoVacuumCommit(BtShared *pBt, Pgno *pnTrunc){
  int rc = SQLITE_OK;
  Pager *pPager = pBt->pPager;
#ifndef NDEBUG
  int nRef = sqlite3PagerRefcount(pPager);
#endif

#ifndef SQLITE_OMIT_INCRBLOB
  BtCursor *pCur;
  for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){
    /* Delete the cache of overflow page numbers. */
    sqliteFree(pCur->aOverflow);
    pCur->aOverflow = 0;
  }
#endif

  assert(pBt->autoVacuum);
  if( !pBt->incrVacuum ){
    Pgno nFin = 0;

    if( pBt->nTrunc==0 ){
      Pgno nFree;

    pBt->pCursor = pCur->pNext;
  }
  if( pCur->pNext ){
    pCur->pNext->pPrev = pCur->pPrev;
  }
  releasePage(pCur->pPage);
  unlockBtreeIfUnused(pBt);
#ifndef SQLITE_OMIT_INCRBLOB
  sqliteFree(pCur->aOverflow);
#endif
  sqliteFree(pCur);
  return SQLITE_OK;
}

/*
** Make a temporary cursor by filling in the fields of pTempCur.
** The temporary cursor is not on the cursor list for the Btree.

  unsigned char *aPayload;
  Pgno nextPage;
  int rc;
  MemPage *pPage;
  BtShared *pBt;
  int ovflSize;
  u32 nKey;
  int iIdx = 0;

  assert( pCur!=0 && pCur->pPage!=0 );
  assert( pCur->eState==CURSOR_VALID );
  pBt = pCur->pBtree->pBt;
  pPage = pCur->pPage;
  assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
  getCellInfo(pCur);

    amt -= a;
  }else{
    offset -= pCur->info.nLocal;
  }
  ovflSize = pBt->usableSize - 4;
  if( amt>0 ){
    nextPage = get4byte(&aPayload[pCur->info.nLocal]);
#ifndef SQLITE_OMIT_INCRBLOB
    if( pCur->cacheOverflow && !pCur->aOverflow ){
      int nOvfl = (pCur->info.nPayload-pCur->info.nLocal+ovflSize-1)/ovflSize;
      pCur->aOverflow = (Pgno *)sqliteMalloc(sizeof(Pgno)*nOvfl);
      if( nOvfl && !pCur->aOverflow ){
        return SQLITE_NOMEM;
      }
    }
    if( pCur->aOverflow && pCur->aOverflow[offset/ovflSize] ){
      iIdx = (offset/ovflSize);
      nextPage = pCur->aOverflow[iIdx];
      offset = (offset%ovflSize);
    }
#endif
    for(iIdx++; amt>0 && nextPage; iIdx++){
      if( offset>=ovflSize ){
        /* The only reason to read this page is to obtain the page
        ** number for the next page in the overflow chain. So try
        ** the getOverflowPage() shortcut.
        */
        rc = getOverflowPage(pBt, nextPage, 0, &nextPage);
        if( rc!=SQLITE_OK ){
          return rc;
        }
        offset -= ovflSize;
#ifndef SQLITE_OMIT_INCRBLOB
        if( pCur->aOverflow ){
          assert(nextPage);
          pCur->aOverflow[iIdx] = nextPage;
        }
#endif
      }else{
        /* Need to read this page properly, to obtain data to copy into
        ** the caller's buffer.
        */
        DbPage *pDbPage;
        int a = amt;
        rc = sqlite3PagerGet(pBt->pPager, nextPage, &pDbPage);
        if( rc!=0 ){
          return rc;
        }
        aPayload = sqlite3PagerGetData(pDbPage);
        nextPage = get4byte(aPayload);
        if( a + offset > ovflSize ){
          a = ovflSize - offset;
        }
        memcpy(pBuf, &aPayload[offset+4], a);
        offset = 0;
        amt -= a;
        pBuf += a;
        sqlite3PagerUnref(pDbPage);
#ifndef SQLITE_OMIT_INCRBLOB
        if( pCur->aOverflow && nextPage ){
          pCur->aOverflow[iIdx] = nextPage;
        }
#endif
      }
    }
  }

  if( amt>0 ){
    return SQLITE_CORRUPT_BKPT;
  }

  BtShared *pBt = pCsr->pBtree->pBt;
  int rc;

  u32 iRem = amt;        /* Remaining bytes to write */
  u8 *zRem = (u8 *)z;    /* Pointer to data not yet written */
  u32 iOffset = offset;  /* Offset from traversal point to start of write */

  Pgno iIdx = 0;         /* Index of overflow page in pCsr->aOverflow */
  Pgno iOvfl;            /* Page number for next overflow page */
  int ovflSize;          /* Bytes of data per overflow page. */

  CellInfo *pInfo;

  /* Check some preconditions: 
  **   (a) a write-transaction is open, 

  ** enough for the proposed write operation.
  */
  getCellInfo(pCsr);
  pInfo = &pCsr->info;
  if( pInfo->nData<(offset+amt) ){
    return SQLITE_ERROR;
  }
  ovflSize = pBt->usableSize - 4;

  assert(pCsr->cacheOverflow);
  if( !pCsr->aOverflow ){
    int nOverflow = (pInfo->nPayload - pInfo->nLocal + ovflSize - 1)/ovflSize;
    pCsr->aOverflow = (Pgno *)sqliteMalloc(sizeof(Pgno)*nOverflow);
    if( nOverflow && !pCsr->aOverflow ){
      return SQLITE_NOMEM;
    }
  }

  if( pInfo->nLocal>iOffset ){
    /* In this case data must be written to the b-tree page. */
    int iWrite = pInfo->nLocal - offset;
    if( iWrite>iRem ){
      iWrite = iRem;
    }
    rc = sqlite3PagerWrite(pCsr->pPage->pDbPage);
    if( rc!=SQLITE_OK ){
      return rc;
    }
    memcpy(&pInfo->pCell[iOffset+pInfo->nHeader], zRem, iWrite);

    zRem += iWrite;
    iRem -= iWrite;
  }
  iOffset = ((iOffset<pInfo->nLocal)?0:(iOffset-pInfo->nLocal));


  assert(pInfo->iOverflow>0 || iRem==0);

  if( iRem>0 ){
    if( pCsr->aOverflow[iOffset/ovflSize] ){
      iIdx = iOffset/ovflSize;


      iOvfl = pCsr->aOverflow[iIdx];




      iOffset = iOffset%ovflSize;
    }else{
      iOvfl = get4byte(&pInfo->pCell[pInfo->iOverflow]);
    }
    for(iIdx++; iRem>0; iIdx++){
      if( iOffset>ovflSize ){
        /* The only reason to read this page is to obtain the page
        ** number for the next page in the overflow chain. So try
        ** the getOverflowPage() shortcut.  */
        rc = getOverflowPage(pBt, iOvfl, 0, &iOvfl);
        if( rc!=SQLITE_OK ){
          return rc;
        }
        iOffset -= ovflSize;
        pCsr->aOverflow[iIdx] = iOvfl;
      }else{
        int iWrite = ovflSize - iOffset;
        DbPage *pOvfl;          /* The overflow page. */
        u8 *aData;              /* Page data */
  
        rc = sqlite3PagerGet(pBt->pPager, iOvfl, &pOvfl);
        if( rc!=SQLITE_OK ){
          return rc;
        }
        rc = sqlite3PagerWrite(pOvfl);
        if( rc!=SQLITE_OK ){
          sqlite3PagerUnref(pOvfl);
          return rc;
        }
  
        aData = sqlite3PagerGetData(pOvfl);
        iOvfl = get4byte(aData);
        pCsr->aOverflow[iIdx] = iOvfl;
        if( iWrite>iRem ){
          iWrite = iRem;
        }
        memcpy(&aData[iOffset+4], zRem, iWrite);
        sqlite3PagerUnref(pOvfl);
  
        zRem += iWrite;
        iRem -= iWrite;
        iOffset = ((iOffset<ovflSize)?0:(iOffset-ovflSize));
      }
    }
  }

  return SQLITE_OK;
}

/* 
** Set a flag on this cursor to cache the locations of pages from the 
** overflow list for the current row.
*/
void sqlite3BtreeCacheOverflow(BtCursor *pCur){
  assert(!pCur->cacheOverflow);
  assert(!pCur->aOverflow);
  pCur->cacheOverflow = 1;
}
#endif

/*
** The following debugging interface has to be in this file (rather
** than in, for example, test1.c) so that it can get access to
** the definition of BtShared.
*/

**    May you share freely, never taking more than you give.
**
*************************************************************************
** This header file defines the interface that the sqlite B-Tree file
** subsystem.  See comments in the source code for a detailed description
** of what each interface routine does.
**
** @(#) $Id: btree.h,v 1.78 2007/05/02 16:48:37 danielk1977 Exp $
*/
#ifndef _BTREE_H_
#define _BTREE_H_

/* TODO: This definition is just included so other modules compile. It
** needs to be revisited.
*/

int sqlite3BtreeDataSize(BtCursor*, u32 *pSize);
int sqlite3BtreeData(BtCursor*, u32 offset, u32 amt, void*);

char *sqlite3BtreeIntegrityCheck(Btree*, int *aRoot, int nRoot, int, int*);
struct Pager *sqlite3BtreePager(Btree*);

int sqlite3BtreePutData(BtCursor*, u32 offset, u32 amt, const void*);
void sqlite3BtreeCacheOverflow(BtCursor *);

#ifdef SQLITE_TEST
int sqlite3BtreeCursorInfo(BtCursor*, int*, int);
void sqlite3BtreeCursorList(Btree*);
#endif

#ifdef SQLITE_DEBUG
int sqlite3BtreePageDump(Btree*, int, int recursive);
#else
#define sqlite3BtreePageDump(X,Y,Z) SQLITE_OK
#endif

#endif /* _BTREE_H_ */

/*
** 2007 May 1
**
** 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: vdbeblob.c,v 1.2 2007/05/02 16:48:37 danielk1977 Exp $
*/

#include "sqliteInt.h"
#include "vdbeInt.h"

#ifndef SQLITE_OMIT_INCRBLOB

    pBlob = (Incrblob *)sqliteMalloc(sizeof(Incrblob));
    if( sqlite3MallocFailed() ){
      sqliteFree(pBlob);
      goto blob_open_out;
    }
    pBlob->flags = flags;
    pBlob->pCsr =  v->apCsr[0]->pCursor;
    sqlite3BtreeCacheOverflow(pBlob->pCsr);
    pBlob->pStmt = (sqlite3_stmt *)v;
    pBlob->iOffset = v->apCsr[0]->aOffset[iCol];
    pBlob->nByte = sqlite3VdbeSerialTypeLen(type);
    *ppBlob = (sqlite3_blob *)pBlob;
    rc = SQLITE_OK;
  }else{
    if( rc==SQLITE_DONE ){