Back to index

lightning-sunbird  0.9+nobinonly
Classes | Defines | Typedefs | Functions | Variables
btree.c File Reference
#include "sqliteInt.h"
#include "pager.h"
#include "btree.h"
#include "os.h"
#include <assert.h>

Go to the source code of this file.

Classes

struct  MemPage
struct  MemPage::_OvflCell
struct  Btree
struct  BtShared
struct  CellInfo
struct  BtCursor
struct  BtLock
struct  IntegrityCk

Defines

#define ROUND8(x)   ((x+7)&~7)
#define MX_CELL_SIZE(pBt)   (pBt->pageSize-8)
#define MX_CELL(pBt)   ((pBt->pageSize-8)/3)
#define SQLITE_FILE_HEADER   "SQLite format 3"
#define PTF_INTKEY   0x01
#define PTF_ZERODATA   0x02
#define PTF_LEAFDATA   0x04
#define PTF_LEAF   0x08
#define EXTRA_SIZE   sizeof(MemPage)
#define TRANS_NONE   0
#define TRANS_READ   1
#define TRANS_WRITE   2
#define CURSOR_INVALID   0
#define CURSOR_VALID   1
#define CURSOR_REQUIRESEEK   2
#define TRACE(X)
#define getVarint   sqlite3GetVarint
#define getVarint32(A, B)   ((*B=*(A))<=0x7f?1:sqlite3GetVarint32(A,B))
#define putVarint   sqlite3PutVarint
#define PENDING_BYTE_PAGE(pBt)   ((PENDING_BYTE/(pBt)->pageSize)+1)
#define READ_LOCK   1
#define WRITE_LOCK   2
#define restoreOrClearCursorPosition(p, x)   (p->eState==CURSOR_REQUIRESEEK?restoreOrClearCursorPositionX(p,x):SQLITE_OK)
#define PTRMAP_PAGENO(pBt, pgno)   ptrmapPageno(pBt, pgno)
#define PTRMAP_PTROFFSET(pBt, pgno)   (5*(pgno-ptrmapPageno(pBt, pgno)-1))
#define PTRMAP_ISPAGE(pBt, pgno)   (PTRMAP_PAGENO((pBt),(pgno))==(pgno))
#define PTRMAP_ROOTPAGE   1
#define PTRMAP_FREEPAGE   2
#define PTRMAP_OVERFLOW1   3
#define PTRMAP_OVERFLOW2   4
#define PTRMAP_BTREE   5
#define pageIntegrity(X)
#define btreeIntegrity(p)
#define NN   1 /* Number of neighbors on either side of pPage */
#define NB   (NN*2+1) /* Total pages involved in the balance */
#define ISAUTOVACUUM   (pBt->autoVacuum)

Typedefs

typedef struct MemPage
typedef struct BtLock
typedef struct CellInfo
typedef struct IntegrityCk

Functions

static int checkReadLocks (BtShared *, Pgno, BtCursor *)
static u32 get2byte (unsigned char *p)
static u32 get4byte (unsigned char *p)
static void put2byte (unsigned char *p, u32 v)
static void put4byte (unsigned char *p, u32 v)
static void releasePage (MemPage *pPage)
static int saveCursorPosition (BtCursor *pCur)
static int saveAllCursors (BtShared *pBt, Pgno iRoot, BtCursor *pExcept)
static int restoreOrClearCursorPositionX (BtCursor *pCur, int doSeek)
static int queryTableLock (Btree *p, Pgno iTab, u8 eLock)
static int lockTable (Btree *p, Pgno iTable, u8 eLock)
static void unlockAllTables (Btree *p)
static Pgno ptrmapPageno (BtShared *pBt, Pgno pgno)
static int ptrmapPut (BtShared *pBt, Pgno key, u8 eType, Pgno parent)
static int ptrmapGet (BtShared *pBt, Pgno key, u8 *pEType, Pgno *pPgno)
static u8findCell (MemPage *pPage, int iCell)
static u8findOverflowCell (MemPage *pPage, int iCell)
static void parseCellPtr (MemPage *pPage, u8 *pCell, CellInfo *pInfo)
static void parseCell (MemPage *pPage, int iCell, CellInfo *pInfo)
static int cellSizePtr (MemPage *pPage, u8 *pCell)
static int ptrmapPutOvflPtr (MemPage *pPage, u8 *pCell)
static int ptrmapPutOvfl (MemPage *pPage, int iCell)
static int defragmentPage (MemPage *pPage)
static int allocateSpace (MemPage *pPage, int nByte)
static void freeSpace (MemPage *pPage, int start, int size)
static void decodeFlags (MemPage *pPage, int flagByte)
static int initPage (MemPage *pPage, MemPage *pParent)
static void zeroPage (MemPage *pPage, int flags)
static int getPage (BtShared *pBt, Pgno pgno, MemPage **ppPage)
static int getAndInitPage (BtShared *pBt, Pgno pgno, MemPage **ppPage, MemPage *pParent)
static void pageDestructor (void *pData, int pageSize)
static void pageReinit (void *pData, int pageSize)
int sqlite3BtreeOpen (const char *zFilename, sqlite3 *pSqlite, Btree **ppBtree, int flags)
int sqlite3BtreeClose (Btree *p)
int sqlite3BtreeSetBusyHandler (Btree *p, BusyHandler *pHandler)
int sqlite3BtreeSetCacheSize (Btree *p, int mxPage)
int sqlite3BtreeSetSafetyLevel (Btree *p, int level, int fullSync)
int sqlite3BtreeSyncDisabled (Btree *p)
int sqlite3BtreeSetPageSize (Btree *p, int pageSize, int nReserve)
int sqlite3BtreeGetPageSize (Btree *p)
int sqlite3BtreeGetReserve (Btree *p)
int sqlite3BtreeSetAutoVacuum (Btree *p, int autoVacuum)
int sqlite3BtreeGetAutoVacuum (Btree *p)
static int lockBtree (BtShared *pBt)
static int lockBtreeWithRetry (Btree *pRef)
static void unlockBtreeIfUnused (BtShared *pBt)
static int newDatabase (BtShared *pBt)
int sqlite3BtreeBeginTrans (Btree *p, int wrflag)
static int setChildPtrmaps (MemPage *pPage)
static int modifyPagePointer (MemPage *pPage, Pgno iFrom, Pgno iTo, u8 eType)
static int relocatePage (BtShared *pBt, MemPage *pDbPage, u8 eType, Pgno iPtrPage, Pgno iFreePage)
static int allocatePage (BtShared *, MemPage **, Pgno *, Pgno, u8)
static int autoVacuumCommit (BtShared *pBt, Pgno *nTrunc)
int sqlite3BtreeCommit (Btree *p)
int sqlite3BtreeRollback (Btree *p)
int sqlite3BtreeBeginStmt (Btree *p)
int sqlite3BtreeCommitStmt (Btree *p)
int sqlite3BtreeRollbackStmt (Btree *p)
static int dfltCompare (void *NotUsed, int n1, const void *p1, int n2, const void *p2)
int sqlite3BtreeCursor (Btree *p, int iTable, int wrFlag, int(*xCmp)(void *, int, const void *, int, const void *), void *pArg, BtCursor **ppCur)
int sqlite3BtreeCloseCursor (BtCursor *pCur)
static void getTempCursor (BtCursor *pCur, BtCursor *pTempCur)
static void releaseTempCursor (BtCursor *pCur)
static void getCellInfo (BtCursor *pCur)
int sqlite3BtreeKeySize (BtCursor *pCur, i64 *pSize)
int sqlite3BtreeDataSize (BtCursor *pCur, u32 *pSize)
static int getPayload (BtCursor *pCur, int offset, int amt, unsigned char *pBuf, int skipKey)
int sqlite3BtreeKey (BtCursor *pCur, u32 offset, u32 amt, void *pBuf)
int sqlite3BtreeData (BtCursor *pCur, u32 offset, u32 amt, void *pBuf)
static const unsigned char * fetchPayload (BtCursor *pCur, int *pAmt, int skipKey)
const voidsqlite3BtreeKeyFetch (BtCursor *pCur, int *pAmt)
const voidsqlite3BtreeDataFetch (BtCursor *pCur, int *pAmt)
static int moveToChild (BtCursor *pCur, u32 newPgno)
static int isRootPage (MemPage *pPage)
static void moveToParent (BtCursor *pCur)
static int moveToRoot (BtCursor *pCur)
static int moveToLeftmost (BtCursor *pCur)
static int moveToRightmost (BtCursor *pCur)
int sqlite3BtreeFirst (BtCursor *pCur, int *pRes)
int sqlite3BtreeLast (BtCursor *pCur, int *pRes)
int sqlite3BtreeMoveto (BtCursor *pCur, const void *pKey, i64 nKey, int *pRes)
int sqlite3BtreeEof (BtCursor *pCur)
int sqlite3BtreeNext (BtCursor *pCur, int *pRes)
int sqlite3BtreePrevious (BtCursor *pCur, int *pRes)
static int freePage (MemPage *pPage)
static int clearCell (MemPage *pPage, unsigned char *pCell)
static int fillInCell (MemPage *pPage, unsigned char *pCell, const void *pKey, i64 nKey, const void *pData, int nData, int *pnSize)
static int reparentPage (BtShared *pBt, Pgno pgno, MemPage *pNewParent, int idx)
static int reparentChildPages (MemPage *pPage)
static void dropCell (MemPage *pPage, int idx, int sz)
static int insertCell (MemPage *pPage, int i, u8 *pCell, int sz, u8 *pTemp, u8 nSkip)
static void assemblePage (MemPage *pPage, int nCell, u8 **apCell, int *aSize)
static int balance (MemPage *, int)
static int balance_quick (MemPage *pPage, MemPage *pParent)
static int balance_nonroot (MemPage *pPage)
static int balance_shallower (MemPage *pPage)
static int balance_deeper (MemPage *pPage)
int sqlite3BtreeInsert (BtCursor *pCur, const void *pKey, i64 nKey, const void *pData, int nData)
int sqlite3BtreeDelete (BtCursor *pCur)
int sqlite3BtreeCreateTable (Btree *p, int *piTable, int flags)
static int clearDatabasePage (BtShared *pBt, Pgno pgno, MemPage *pParent, int freePageFlag)
int sqlite3BtreeClearTable (Btree *p, int iTable)
int sqlite3BtreeDropTable (Btree *p, int iTable, int *piMoved)
int sqlite3BtreeGetMeta (Btree *p, int idx, u32 *pMeta)
int sqlite3BtreeUpdateMeta (Btree *p, int idx, u32 iMeta)
int sqlite3BtreeFlags (BtCursor *pCur)
Pagersqlite3BtreePager (Btree *p)
static void checkAppendMsg (IntegrityCk *pCheck, char *zMsg1, const char *zFormat,...)
static int checkRef (IntegrityCk *pCheck, int iPage, char *zContext)
static void checkPtrmap (IntegrityCk *pCheck, Pgno iChild, u8 eType, Pgno iParent, char *zContext)
static void checkList (IntegrityCk *pCheck, int isFreeList, int iPage, int N, char *zContext)
static int checkTreePage (IntegrityCk *pCheck, int iPage, MemPage *pParent, char *zParentContext)
char * sqlite3BtreeIntegrityCheck (Btree *p, int *aRoot, int nRoot)
const char * sqlite3BtreeGetFilename (Btree *p)
const char * sqlite3BtreeGetDirname (Btree *p)
const char * sqlite3BtreeGetJournalname (Btree *p)
int sqlite3BtreeCopyFile (Btree *pTo, Btree *pFrom)
int sqlite3BtreeIsInTrans (Btree *p)
int sqlite3BtreeIsInStmt (Btree *p)
int sqlite3BtreeSync (Btree *p, const char *zMaster)
voidsqlite3BtreeSchema (Btree *p, int nBytes, void(*xFree)(void *))
int sqlite3BtreeSchemaLocked (Btree *p)
int sqlite3BtreeLockTable (Btree *p, int iTab, u8 isWriteLock)

Variables

static const char zMagicHeader [] = SQLITE_FILE_HEADER
int sqlite3_btree_trace = 0

Class Documentation

struct MemPage

Definition at line 271 of file btree.c.

Collaboration diagram for MemPage:
Class Members
u8 * aData
struct _OvflCell aOvfl
u16 cellOffset
u8 childPtrSize
u8 hasData
u8 hdrOffset
u16 idxParent
u8 idxShift
u8 intKey
u8 isInit
u8 leaf
u8 leafData
u16 maxLocal
u16 minLocal
u16 nCell
u16 nFree
u8 nOverflow
BtShared * pBt
Pgno pgno
MemPage * pParent
u8 zeroData
struct MemPage::_OvflCell

Definition at line 288 of file btree.c.

Class Members
u16 idx
u8 * pCell
struct Btree

Definition at line 306 of file btree.c.

Collaboration diagram for Btree:
Class Members
u8 inTrans
BtShared * pBt
sqlite3 * pSqlite
struct CellInfo

Definition at line 364 of file btree.c.

Collaboration diagram for CellInfo:
Class Members
nsTableCellFrame * cellFrame
PRInt32 colSpan
u16 iOverflow
u32 nData
u16 nHeader
i64 nKey
u16 nLocal
u16 nSize
u8 * pCell
struct BtLock

Definition at line 489 of file btree.c.

Collaboration diagram for BtLock:
Class Members
u8 eLock
Pgno iTable
Btree * pBtree
BtLock * pNext
struct IntegrityCk

Definition at line 6055 of file btree.c.

Collaboration diagram for IntegrityCk:
Class Members
int * anRef
int nPage
BtShared * pBt
Pager * pPager
char * zErrMsg

Define Documentation

Value:
assert( p->inTrans!=TRANS_NONE || p->pBt->nTransaction<p->pBt->nRef ); \
  assert( p->pBt->nTransaction<=p->pBt->nRef ); \
  assert( p->pBt->inTransaction!=TRANS_NONE || p->pBt->nTransaction==0 ); \
  assert( p->pBt->inTransaction>=p->inTrans );

Definition at line 1139 of file btree.c.

Definition at line 417 of file btree.c.

Definition at line 419 of file btree.c.

Definition at line 418 of file btree.c.

#define EXTRA_SIZE   sizeof(MemPage)

Definition at line 303 of file btree.c.

Definition at line 464 of file btree.c.

#define getVarint32 (   A,
  B 
)    ((*B=*(A))<=0x7f?1:sqlite3GetVarint32(A,B))

Definition at line 466 of file btree.c.

#define ISAUTOVACUUM   (pBt->autoVacuum)

Definition at line 4450 of file btree.c.

#define MX_CELL (   pBt)    ((pBt->pageSize-8)/3)

Definition at line 229 of file btree.c.

#define MX_CELL_SIZE (   pBt)    (pBt->pageSize-8)

Definition at line 223 of file btree.c.

#define NB   (NN*2+1) /* Total pages involved in the balance */

Definition at line 4347 of file btree.c.

#define NN   1 /* Number of neighbors on either side of pPage */

Definition at line 4346 of file btree.c.

Definition at line 1133 of file btree.c.

#define PENDING_BYTE_PAGE (   pBt)    ((PENDING_BYTE/(pBt)->pageSize)+1)

Definition at line 479 of file btree.c.

#define PTF_INTKEY   0x01

Definition at line 256 of file btree.c.

#define PTF_LEAF   0x08

Definition at line 259 of file btree.c.

#define PTF_LEAFDATA   0x04

Definition at line 258 of file btree.c.

#define PTF_ZERODATA   0x02

Definition at line 257 of file btree.c.

Definition at line 815 of file btree.c.

Definition at line 812 of file btree.c.

#define PTRMAP_ISPAGE (   pBt,
  pgno 
)    (PTRMAP_PAGENO((pBt),(pgno))==(pgno))

Definition at line 768 of file btree.c.

Definition at line 813 of file btree.c.

Definition at line 814 of file btree.c.

#define PTRMAP_PAGENO (   pBt,
  pgno 
)    ptrmapPageno(pBt, pgno)

Definition at line 766 of file btree.c.

#define PTRMAP_PTROFFSET (   pBt,
  pgno 
)    (5*(pgno-ptrmapPageno(pBt, pgno)-1))

Definition at line 767 of file btree.c.

Definition at line 811 of file btree.c.

Definition at line 467 of file btree.c.

#define READ_LOCK   1

Definition at line 497 of file btree.c.

Definition at line 609 of file btree.c.

#define ROUND8 (   x)    ((x+7)&~7)

Definition at line 217 of file btree.c.

#define SQLITE_FILE_HEADER   "SQLite format 3"

Definition at line 248 of file btree.c.

#define TRACE (   X)

Definition at line 430 of file btree.c.

#define TRANS_NONE   0

Definition at line 320 of file btree.c.

#define TRANS_READ   1

Definition at line 321 of file btree.c.

Definition at line 322 of file btree.c.

#define WRITE_LOCK   2

Definition at line 498 of file btree.c.


Typedef Documentation

typedef struct BtLock

Definition at line 233 of file btree.c.

typedef struct CellInfo

Definition at line 363 of file btree.c.

typedef struct IntegrityCk

Definition at line 6054 of file btree.c.

typedef struct MemPage

Definition at line 232 of file btree.c.


Function Documentation

static int allocatePage ( BtShared pBt,
MemPage **  ppPage,
Pgno pPgno,
Pgno  nearby,
u8  exact 
) [static]

Definition at line 3660 of file btree.c.

 {
  MemPage *pPage1;
  int rc;
  int n;     /* Number of pages on the freelist */
  int k;     /* Number of leaves on the trunk of the freelist */

  pPage1 = pBt->pPage1;
  n = get4byte(&pPage1->aData[36]);
  if( n>0 ){
    /* There are pages on the freelist.  Reuse one of those pages. */
    MemPage *pTrunk = 0;
    Pgno iTrunk;
    MemPage *pPrevTrunk = 0;
    u8 searchList = 0; /* If the free-list must be searched for 'nearby' */
    
    /* If the 'exact' parameter was true and a query of the pointer-map
    ** shows that the page 'nearby' is somewhere on the free-list, then
    ** the entire-list will be searched for that page.
    */
#ifndef SQLITE_OMIT_AUTOVACUUM
    if( exact ){
      u8 eType;
      assert( nearby>0 );
      assert( pBt->autoVacuum );
      rc = ptrmapGet(pBt, nearby, &eType, 0);
      if( rc ) return rc;
      if( eType==PTRMAP_FREEPAGE ){
        searchList = 1;
      }
      *pPgno = nearby;
    }
#endif

    /* Decrement the free-list count by 1. Set iTrunk to the index of the
    ** first free-list trunk page. iPrevTrunk is initially 1.
    */
    rc = sqlite3pager_write(pPage1->aData);
    if( rc ) return rc;
    put4byte(&pPage1->aData[36], n-1);

    /* The code within this loop is run only once if the 'searchList' variable
    ** is not true. Otherwise, it runs once for each trunk-page on the
    ** free-list until the page 'nearby' is located.
    */
    do {
      pPrevTrunk = pTrunk;
      if( pPrevTrunk ){
        iTrunk = get4byte(&pPrevTrunk->aData[0]);
      }else{
        iTrunk = get4byte(&pPage1->aData[32]);
      }
      rc = getPage(pBt, iTrunk, &pTrunk);
      if( rc ){
        releasePage(pPrevTrunk);
        return rc;
      }

      /* TODO: This should move to after the loop? */
      rc = sqlite3pager_write(pTrunk->aData);
      if( rc ){
        releasePage(pTrunk);
        releasePage(pPrevTrunk);
        return rc;
      }

      k = get4byte(&pTrunk->aData[4]);
      if( k==0 && !searchList ){
        /* The trunk has no leaves and the list is not being searched. 
        ** So extract the trunk page itself and use it as the newly 
        ** allocated page */
        assert( pPrevTrunk==0 );
        *pPgno = iTrunk;
        memcpy(&pPage1->aData[32], &pTrunk->aData[0], 4);
        *ppPage = pTrunk;
        pTrunk = 0;
        TRACE(("ALLOCATE: %d trunk - %d free pages left\n", *pPgno, n-1));
      }else if( k>pBt->usableSize/4 - 8 ){
        /* Value of k is out of range.  Database corruption */
        return SQLITE_CORRUPT_BKPT;
#ifndef SQLITE_OMIT_AUTOVACUUM
      }else if( searchList && nearby==iTrunk ){
        /* The list is being searched and this trunk page is the page
        ** to allocate, regardless of whether it has leaves.
        */
        assert( *pPgno==iTrunk );
        *ppPage = pTrunk;
        searchList = 0;
        if( k==0 ){
          if( !pPrevTrunk ){
            memcpy(&pPage1->aData[32], &pTrunk->aData[0], 4);
          }else{
            memcpy(&pPrevTrunk->aData[0], &pTrunk->aData[0], 4);
          }
        }else{
          /* The trunk page is required by the caller but it contains 
          ** pointers to free-list leaves. The first leaf becomes a trunk
          ** page in this case.
          */
          MemPage *pNewTrunk;
          Pgno iNewTrunk = get4byte(&pTrunk->aData[8]);
          rc = getPage(pBt, iNewTrunk, &pNewTrunk);
          if( rc!=SQLITE_OK ){
            releasePage(pTrunk);
            releasePage(pPrevTrunk);
            return rc;
          }
          rc = sqlite3pager_write(pNewTrunk->aData);
          if( rc!=SQLITE_OK ){
            releasePage(pNewTrunk);
            releasePage(pTrunk);
            releasePage(pPrevTrunk);
            return rc;
          }
          memcpy(&pNewTrunk->aData[0], &pTrunk->aData[0], 4);
          put4byte(&pNewTrunk->aData[4], k-1);
          memcpy(&pNewTrunk->aData[8], &pTrunk->aData[12], (k-1)*4);
          if( !pPrevTrunk ){
            put4byte(&pPage1->aData[32], iNewTrunk);
          }else{
            put4byte(&pPrevTrunk->aData[0], iNewTrunk);
          }
          releasePage(pNewTrunk);
        }
        pTrunk = 0;
        TRACE(("ALLOCATE: %d trunk - %d free pages left\n", *pPgno, n-1));
#endif
      }else{
        /* Extract a leaf from the trunk */
        int closest;
        Pgno iPage;
        unsigned char *aData = pTrunk->aData;
        if( nearby>0 ){
          int i, dist;
          closest = 0;
          dist = get4byte(&aData[8]) - nearby;
          if( dist<0 ) dist = -dist;
          for(i=1; i<k; i++){
            int d2 = get4byte(&aData[8+i*4]) - nearby;
            if( d2<0 ) d2 = -d2;
            if( d2<dist ){
              closest = i;
              dist = d2;
            }
          }
        }else{
          closest = 0;
        }

        iPage = get4byte(&aData[8+closest*4]);
        if( !searchList || iPage==nearby ){
          *pPgno = iPage;
          if( *pPgno>sqlite3pager_pagecount(pBt->pPager) ){
            /* Free page off the end of the file */
            return SQLITE_CORRUPT_BKPT;
          }
          TRACE(("ALLOCATE: %d was leaf %d of %d on trunk %d"
                 ": %d more free pages\n",
                 *pPgno, closest+1, k, pTrunk->pgno, n-1));
          if( closest<k-1 ){
            memcpy(&aData[8+closest*4], &aData[4+k*4], 4);
          }
          put4byte(&aData[4], k-1);
          rc = getPage(pBt, *pPgno, ppPage);
          if( rc==SQLITE_OK ){
            sqlite3pager_dont_rollback((*ppPage)->aData);
            rc = sqlite3pager_write((*ppPage)->aData);
            if( rc!=SQLITE_OK ){
              releasePage(*ppPage);
            }
          }
          searchList = 0;
        }
      }
      releasePage(pPrevTrunk);
    }while( searchList );
    releasePage(pTrunk);
  }else{
    /* There are no pages on the freelist, so create a new page at the
    ** end of the file */
    *pPgno = sqlite3pager_pagecount(pBt->pPager) + 1;

#ifndef SQLITE_OMIT_AUTOVACUUM
    if( pBt->autoVacuum && PTRMAP_ISPAGE(pBt, *pPgno) ){
      /* If *pPgno refers to a pointer-map page, allocate two new pages
      ** at the end of the file instead of one. The first allocated page
      ** becomes a new pointer-map page, the second is used by the caller.
      */
      TRACE(("ALLOCATE: %d from end of file (pointer-map page)\n", *pPgno));
      assert( *pPgno!=PENDING_BYTE_PAGE(pBt) );
      (*pPgno)++;
    }
#endif

    assert( *pPgno!=PENDING_BYTE_PAGE(pBt) );
    rc = getPage(pBt, *pPgno, ppPage);
    if( rc ) return rc;
    rc = sqlite3pager_write((*ppPage)->aData);
    if( rc!=SQLITE_OK ){
      releasePage(*ppPage);
    }
    TRACE(("ALLOCATE: %d from end of file\n", *pPgno));
  }

  assert( *pPgno!=PENDING_BYTE_PAGE(pBt) );
  return rc;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int allocateSpace ( MemPage pPage,
int  nByte 
) [static]

Definition at line 1212 of file btree.c.

                                                   {
  int addr, pc, hdr;
  int size;
  int nFrag;
  int top;
  int nCell;
  int cellOffset;
  unsigned char *data;
  
  data = pPage->aData;
  assert( sqlite3pager_iswriteable(data) );
  assert( pPage->pBt );
  if( nByte<4 ) nByte = 4;
  if( pPage->nFree<nByte || pPage->nOverflow>0 ) return 0;
  pPage->nFree -= nByte;
  hdr = pPage->hdrOffset;

  nFrag = data[hdr+7];
  if( nFrag<60 ){
    /* Search the freelist looking for a slot big enough to satisfy the
    ** space request. */
    addr = hdr+1;
    while( (pc = get2byte(&data[addr]))>0 ){
      size = get2byte(&data[pc+2]);
      if( size>=nByte ){
        if( size<nByte+4 ){
          memcpy(&data[addr], &data[pc], 2);
          data[hdr+7] = nFrag + size - nByte;
          return pc;
        }else{
          put2byte(&data[pc+2], size-nByte);
          return pc + size - nByte;
        }
      }
      addr = pc;
    }
  }

  /* Allocate memory from the gap in between the cell pointer array
  ** and the cell content area.
  */
  top = get2byte(&data[hdr+5]);
  nCell = get2byte(&data[hdr+3]);
  cellOffset = pPage->cellOffset;
  if( nFrag>=60 || cellOffset + 2*nCell > top - nByte ){
    if( defragmentPage(pPage) ) return 0;
    top = get2byte(&data[hdr+5]);
  }
  top -= nByte;
  assert( cellOffset + 2*nCell <= top );
  put2byte(&data[hdr+5], top);
  return top;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void assemblePage ( MemPage pPage,
int  nCell,
u8 **  apCell,
int aSize 
) [static]

Definition at line 4294 of file btree.c.

 {
  int i;            /* Loop counter */
  int totalSize;    /* Total size of all cells */
  int hdr;          /* Index of page header */
  int cellptr;      /* Address of next cell pointer */
  int cellbody;     /* Address of next cell body */
  u8 *data;         /* Data for the page */

  assert( pPage->nOverflow==0 );
  totalSize = 0;
  for(i=0; i<nCell; i++){
    totalSize += aSize[i];
  }
  assert( totalSize+2*nCell<=pPage->nFree );
  assert( pPage->nCell==0 );
  cellptr = pPage->cellOffset;
  data = pPage->aData;
  hdr = pPage->hdrOffset;
  put2byte(&data[hdr+3], nCell);
  if( nCell ){
    cellbody = allocateSpace(pPage, totalSize);
    assert( cellbody>0 );
    assert( pPage->nFree >= 2*nCell );
    pPage->nFree -= 2*nCell;
    for(i=0; i<nCell; i++){
      put2byte(&data[cellptr], cellbody);
      memcpy(&data[cellbody], apCell[i], aSize[i]);
      cellptr += 2;
      cellbody += aSize[i];
    }
    assert( cellbody==pPage->pBt->usableSize );
  }
  pPage->nCell = nCell;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int autoVacuumCommit ( BtShared pBt,
Pgno nTrunc 
) [static]

Definition at line 2354 of file btree.c.

                                                        {
  Pager *pPager = pBt->pPager;
  Pgno nFreeList;            /* Number of pages remaining on the free-list. */
  int nPtrMap;               /* Number of pointer-map pages deallocated */
  Pgno origSize;             /* Pages in the database file */
  Pgno finSize;              /* Pages in the database file after truncation */
  int rc;                    /* Return code */
  u8 eType;
  int pgsz = pBt->pageSize;  /* Page size for this database */
  Pgno iDbPage;              /* The database page to move */
  MemPage *pDbMemPage = 0;   /* "" */
  Pgno iPtrPage;             /* The page that contains a pointer to iDbPage */
  Pgno iFreePage;            /* The free-list page to move iDbPage to */
  MemPage *pFreeMemPage = 0; /* "" */

#ifndef NDEBUG
  int nRef = *sqlite3pager_stats(pPager);
#endif

  assert( pBt->autoVacuum );
  if( PTRMAP_ISPAGE(pBt, sqlite3pager_pagecount(pPager)) ){
    return SQLITE_CORRUPT_BKPT;
  }

  /* Figure out how many free-pages are in the database. If there are no
  ** free pages, then auto-vacuum is a no-op.
  */
  nFreeList = get4byte(&pBt->pPage1->aData[36]);
  if( nFreeList==0 ){
    *nTrunc = 0;
    return SQLITE_OK;
  }

  /* This block figures out how many pages there are in the database
  ** now (variable origSize), and how many there will be after the
  ** truncation (variable finSize).
  **
  ** The final size is the original size, less the number of free pages
  ** in the database, less any pointer-map pages that will no longer
  ** be required, less 1 if the pending-byte page was part of the database
  ** but is not after the truncation.
  **/
  origSize = sqlite3pager_pagecount(pPager);
  if( origSize==PENDING_BYTE_PAGE(pBt) ){
    origSize--;
  }
  nPtrMap = (nFreeList-origSize+PTRMAP_PAGENO(pBt, origSize)+pgsz/5)/(pgsz/5);
  finSize = origSize - nFreeList - nPtrMap;
  if( origSize>PENDING_BYTE_PAGE(pBt) && finSize<=PENDING_BYTE_PAGE(pBt) ){
    finSize--;
  }
  while( PTRMAP_ISPAGE(pBt, finSize) || finSize==PENDING_BYTE_PAGE(pBt) ){
    finSize--;
  }
  TRACE(("AUTOVACUUM: Begin (db size %d->%d)\n", origSize, finSize));

  /* Variable 'finSize' will be the size of the file in pages after
  ** the auto-vacuum has completed (the current file size minus the number
  ** of pages on the free list). Loop through the pages that lie beyond
  ** this mark, and if they are not already on the free list, move them
  ** to a free page earlier in the file (somewhere before finSize).
  */
  for( iDbPage=finSize+1; iDbPage<=origSize; iDbPage++ ){
    /* If iDbPage is a pointer map page, or the pending-byte page, skip it. */
    if( PTRMAP_ISPAGE(pBt, iDbPage) || iDbPage==PENDING_BYTE_PAGE(pBt) ){
      continue;
    }

    rc = ptrmapGet(pBt, iDbPage, &eType, &iPtrPage);
    if( rc!=SQLITE_OK ) goto autovacuum_out;
    if( eType==PTRMAP_ROOTPAGE ){
      rc = SQLITE_CORRUPT_BKPT;
      goto autovacuum_out;
    }

    /* If iDbPage is free, do not swap it.  */
    if( eType==PTRMAP_FREEPAGE ){
      continue;
    }
    rc = getPage(pBt, iDbPage, &pDbMemPage);
    if( rc!=SQLITE_OK ) goto autovacuum_out;

    /* Find the next page in the free-list that is not already at the end 
    ** of the file. A page can be pulled off the free list using the 
    ** allocatePage() routine.
    */
    do{
      if( pFreeMemPage ){
        releasePage(pFreeMemPage);
        pFreeMemPage = 0;
      }
      rc = allocatePage(pBt, &pFreeMemPage, &iFreePage, 0, 0);
      if( rc!=SQLITE_OK ){
        releasePage(pDbMemPage);
        goto autovacuum_out;
      }
      assert( iFreePage<=origSize );
    }while( iFreePage>finSize );
    releasePage(pFreeMemPage);
    pFreeMemPage = 0;

    /* Relocate the page into the body of the file. Note that although the 
    ** page has moved within the database file, the pDbMemPage pointer 
    ** remains valid. This means that this function can run without
    ** invalidating cursors open on the btree. This is important in 
    ** shared-cache mode.
    */
    rc = relocatePage(pBt, pDbMemPage, eType, iPtrPage, iFreePage);
    releasePage(pDbMemPage);
    if( rc!=SQLITE_OK ) goto autovacuum_out;
  }

  /* The entire free-list has been swapped to the end of the file. So
  ** truncate the database file to finSize pages and consider the
  ** free-list empty.
  */
  rc = sqlite3pager_write(pBt->pPage1->aData);
  if( rc!=SQLITE_OK ) goto autovacuum_out;
  put4byte(&pBt->pPage1->aData[32], 0);
  put4byte(&pBt->pPage1->aData[36], 0);
  *nTrunc = finSize;
  assert( finSize!=PENDING_BYTE_PAGE(pBt) );

autovacuum_out:
  assert( nRef==*sqlite3pager_stats(pPager) );
  if( rc!=SQLITE_OK ){
    sqlite3pager_rollback(pPager);
  }
  return rc;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int balance ( MemPage pPage,
int  insert 
) [static]

Definition at line 5198 of file btree.c.

                                              {
  int rc = SQLITE_OK;
  if( pPage->pParent==0 ){
    if( pPage->nOverflow>0 ){
      rc = balance_deeper(pPage);
    }
    if( rc==SQLITE_OK && pPage->nCell==0 ){
      rc = balance_shallower(pPage);
    }
  }else{
    if( pPage->nOverflow>0 || 
        (!insert && pPage->nFree>pPage->pBt->usableSize*2/3) ){
      rc = balance_nonroot(pPage);
    }
  }
  return rc;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int balance_deeper ( MemPage pPage) [static]

Definition at line 5138 of file btree.c.

                                         {
  int rc;             /* Return value from subprocedures */
  MemPage *pChild;    /* Pointer to a new child page */
  Pgno pgnoChild;     /* Page number of the new child page */
  BtShared *pBt;         /* The BTree */
  int usableSize;     /* Total usable size of a page */
  u8 *data;           /* Content of the parent page */
  u8 *cdata;          /* Content of the child page */
  int hdr;            /* Offset to page header in parent */
  int brk;            /* Offset to content of first cell in parent */

  assert( pPage->pParent==0 );
  assert( pPage->nOverflow>0 );
  pBt = pPage->pBt;
  rc = allocatePage(pBt, &pChild, &pgnoChild, pPage->pgno, 0);
  if( rc ) return rc;
  assert( sqlite3pager_iswriteable(pChild->aData) );
  usableSize = pBt->usableSize;
  data = pPage->aData;
  hdr = pPage->hdrOffset;
  brk = get2byte(&data[hdr+5]);
  cdata = pChild->aData;
  memcpy(cdata, &data[hdr], pPage->cellOffset+2*pPage->nCell-hdr);
  memcpy(&cdata[brk], &data[brk], usableSize-brk);
  assert( pChild->isInit==0 );
  rc = initPage(pChild, pPage);
  if( rc ) goto balancedeeper_out;
  memcpy(pChild->aOvfl, pPage->aOvfl, pPage->nOverflow*sizeof(pPage->aOvfl[0]));
  pChild->nOverflow = pPage->nOverflow;
  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 ){
        return rc;
      }
    }
  }
#endif
  rc = balance_nonroot(pChild);

balancedeeper_out:
  releasePage(pChild);
  return rc;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int balance_nonroot ( MemPage pPage) [static]

Definition at line 4484 of file btree.c.

                                          {
  MemPage *pParent;            /* The parent of pPage */
  BtShared *pBt;                  /* The whole database */
  int nCell = 0;               /* Number of cells in apCell[] */
  int nMaxCells = 0;           /* Allocated size of apCell, szCell, aFrom. */
  int nOld;                    /* Number of pages in apOld[] */
  int nNew;                    /* Number of pages in apNew[] */
  int nDiv;                    /* Number of cells in apDiv[] */
  int i, j, k;                 /* Loop counters */
  int idx;                     /* Index of pPage in pParent->aCell[] */
  int nxDiv;                   /* Next divider slot in pParent->aCell[] */
  int rc;                      /* The return code */
  int leafCorrection;          /* 4 if pPage is a leaf.  0 if not */
  int leafData;                /* True if pPage is a leaf of a LEAFDATA tree */
  int usableSpace;             /* Bytes in pPage beyond the header */
  int pageFlags;               /* Value of pPage->aData[0] */
  int subtotal;                /* Subtotal of bytes in cells on one page */
  int iSpace = 0;              /* First unused byte of aSpace[] */
  MemPage *apOld[NB];          /* pPage and up to two siblings */
  Pgno pgnoOld[NB];            /* Page numbers for each page in apOld[] */
  MemPage *apCopy[NB];         /* Private copies of apOld[] pages */
  MemPage *apNew[NB+2];        /* pPage and up to NB siblings after balancing */
  Pgno pgnoNew[NB+2];          /* Page numbers for each page in apNew[] */
  u8 *apDiv[NB];               /* Divider cells in pParent */
  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 */
  int *szCell;                 /* Local size of all cells in apCell[] */
  u8 *aCopy[NB];               /* Space for holding data of apCopy[] */
  u8 *aSpace;                  /* Space to hold copies of dividers cells */
#ifndef SQLITE_OMIT_AUTOVACUUM
  u8 *aFrom = 0;
#endif

  /* 
  ** Find the parent page.
  */
  assert( pPage->isInit );
  assert( sqlite3pager_iswriteable(pPage->aData) );
  pBt = pPage->pBt;
  pParent = pPage->pParent;
  assert( pParent );
  if( SQLITE_OK!=(rc = sqlite3pager_write(pParent->aData)) ){
    return rc;
  }
  TRACE(("BALANCE: begin page %d child of %d\n", pPage->pgno, pParent->pgno));

#ifndef SQLITE_OMIT_QUICKBALANCE
  /*
  ** A special case:  If a new entry has just been inserted into a
  ** table (that is, a btree with integer keys and all data at the leaves)
  ** and the new entry is the right-most entry in the tree (it has the
  ** largest key) then use the special balance_quick() routine for
  ** balancing.  balance_quick() is much faster and results in a tighter
  ** packing of data in the common case.
  */
  if( pPage->leaf &&
      pPage->intKey &&
      pPage->leafData &&
      pPage->nOverflow==1 &&
      pPage->aOvfl[0].idx==pPage->nCell &&
      pPage->pParent->pgno!=1 &&
      get4byte(&pParent->aData[pParent->hdrOffset+8])==pPage->pgno
  ){
    /*
    ** TODO: Check the siblings to the left of pPage. It may be that
    ** they are not full and no new page is required.
    */
    return balance_quick(pPage, pParent);
  }
#endif

  /*
  ** Find the cell in the parent page whose left child points back
  ** to pPage.  The "idx" variable is the index of that cell.  If pPage
  ** is the rightmost child of pParent then set idx to pParent->nCell 
  */
  if( pParent->idxShift ){
    Pgno pgno;
    pgno = pPage->pgno;
    assert( pgno==sqlite3pager_pagenumber(pPage->aData) );
    for(idx=0; idx<pParent->nCell; idx++){
      if( get4byte(findCell(pParent, idx))==pgno ){
        break;
      }
    }
    assert( idx<pParent->nCell
             || get4byte(&pParent->aData[pParent->hdrOffset+8])==pgno );
  }else{
    idx = pPage->idxParent;
  }

  /*
  ** Initialize variables so that it will be safe to jump
  ** directly to balance_cleanup at any moment.
  */
  nOld = nNew = 0;
  sqlite3pager_ref(pParent->aData);

  /*
  ** Find sibling pages to pPage and the cells in pParent that divide
  ** the siblings.  An attempt is made to find NN siblings on either
  ** side of pPage.  More siblings are taken from one side, however, if
  ** pPage there are fewer than NN siblings on the other side.  If pParent
  ** has NB or fewer children then all children of pParent are taken.
  */
  nxDiv = idx - NN;
  if( nxDiv + NB > pParent->nCell ){
    nxDiv = pParent->nCell - NB + 1;
  }
  if( nxDiv<0 ){
    nxDiv = 0;
  }
  nDiv = 0;
  for(i=0, k=nxDiv; i<NB; i++, k++){
    if( k<pParent->nCell ){
      apDiv[i] = findCell(pParent, k);
      nDiv++;
      assert( !pParent->leaf );
      pgnoOld[i] = get4byte(apDiv[i]);
    }else if( k==pParent->nCell ){
      pgnoOld[i] = get4byte(&pParent->aData[pParent->hdrOffset+8]);
    }else{
      break;
    }
    rc = getAndInitPage(pBt, pgnoOld[i], &apOld[i], pParent);
    if( rc ) goto balance_cleanup;
    apOld[i]->idxParent = k;
    apCopy[i] = 0;
    assert( i==nOld );
    nOld++;
    nMaxCells += 1+apOld[i]->nCell+apOld[i]->nOverflow;
  }

  /* Make nMaxCells a multiple of 2 in order to preserve 8-byte
  ** alignment */
  nMaxCells = (nMaxCells + 1)&~1;

  /*
  ** Allocate space for memory structures
  */
  apCell = sqliteMallocRaw( 
       nMaxCells*sizeof(u8*)                           /* apCell */
     + nMaxCells*sizeof(int)                           /* szCell */
     + ROUND8(sizeof(MemPage))*NB                      /* aCopy */
     + pBt->pageSize*(5+NB)                            /* aSpace */
     + (ISAUTOVACUUM ? nMaxCells : 0)                  /* aFrom */
  );
  if( apCell==0 ){
    rc = SQLITE_NOMEM;
    goto balance_cleanup;
  }
  szCell = (int*)&apCell[nMaxCells];
  aCopy[0] = (u8*)&szCell[nMaxCells];
  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 */
  }
  aSpace = &aCopy[NB-1][pBt->pageSize+ROUND8(sizeof(MemPage))];
  assert( ((aSpace - (u8*)apCell) & 7)==0 ); /* 8-byte alignment required */
#ifndef SQLITE_OMIT_AUTOVACUUM
  if( pBt->autoVacuum ){
    aFrom = &aSpace[5*pBt->pageSize];
  }
#endif
  
  /*
  ** Make copies of the content of pPage and its siblings into aOld[].
  ** The rest of this function will use data from the copies rather
  ** that the original pages since the original pages will be in the
  ** process of being overwritten.
  */
  for(i=0; i<nOld; i++){
    MemPage *p = apCopy[i] = (MemPage*)&aCopy[i][pBt->pageSize];
    p->aData = &((u8*)p)[-pBt->pageSize];
    memcpy(p->aData, apOld[i]->aData, pBt->pageSize + sizeof(MemPage));
    /* The memcpy() above changes the value of p->aData so we have to
    ** set it again. */
    p->aData = &((u8*)p)[-pBt->pageSize];
  }

  /*
  ** Load pointers to all cells on sibling pages and the divider cells
  ** into the local apCell[] array.  Make copies of the divider cells
  ** into space obtained form aSpace[] and remove the the divider Cells
  ** from pParent.
  **
  ** If the siblings are on leaf pages, then the child pointers of the
  ** divider cells are stripped from the cells before they are copied
  ** into aSpace[].  In this way, all cells in apCell[] are without
  ** child pointers.  If siblings are not leaves, then all cell in
  ** apCell[] include child pointers.  Either way, all cells in apCell[]
  ** are alike.
  **
  ** 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.
  */
  nCell = 0;
  leafCorrection = pPage->leaf*4;
  leafData = pPage->leafData && pPage->leaf;
  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 ){
      int 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
        ** the divider cells from pParent, but the dividers cells are not
        ** added to apCell[] because they are duplicates of child cells.
        */
        dropCell(pParent, nxDiv, sz);
      }else{
        u8 *pTemp;
        assert( nCell<nMaxCells );
        szCell[nCell] = sz;
        pTemp = &aSpace[iSpace];
        iSpace += sz;
        assert( iSpace<=pBt->pageSize*5 );
        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 */
          memcpy(apCell[nCell], &pOld->aData[pOld->hdrOffset+8], 4);
        }else{
          assert( leafCorrection==4 );
        }
        nCell++;
      }
    }
  }

  /*
  ** Figure out the number of pages needed to hold all nCell cells.
  ** Store this number in "k".  Also compute szNew[] which is the total
  ** size of all cells on the i-th page and cntNew[] which is the index
  ** in apCell[] of the cell that divides page i from page i+1.  
  ** cntNew[k] should equal nCell.
  **
  ** Values computed by this block:
  **
  **           k: The total number of sibling pages
  **    szNew[i]: Spaced used on the i-th sibling page.
  **   cntNew[i]: Index in apCell[] and szCell[] for the first cell to
  **              the right of the i-th sibling page.
  ** usableSpace: Number of bytes of space available on each sibling.
  ** 
  */
  usableSpace = pBt->usableSize - 12 + leafCorrection;
  for(subtotal=k=i=0; i<nCell; i++){
    assert( i<nMaxCells );
    subtotal += szCell[i] + 2;
    if( subtotal > usableSpace ){
      szNew[k] = subtotal - szCell[i];
      cntNew[k] = i;
      if( leafData ){ i--; }
      subtotal = 0;
      k++;
    }
  }
  szNew[k] = subtotal;
  cntNew[k] = nCell;
  k++;

  /*
  ** The packing computed by the previous block is biased toward the siblings
  ** on the left side.  The left siblings are always nearly full, while the
  ** right-most sibling might be nearly empty.  This block of code attempts
  ** to adjust the packing of siblings to get a better balance.
  **
  ** This adjustment is more than an optimization.  The packing above might
  ** be so out of balance as to be illegal.  For example, the right-most
  ** sibling might be completely empty.  This adjustment is not optional.
  */
  for(i=k-1; i>0; i--){
    int szRight = szNew[i];  /* Size of sibling on the right */
    int szLeft = szNew[i-1]; /* Size of sibling on the left */
    int r;              /* Index of right-most cell in left sibling */
    int d;              /* Index of first cell to the left of right sibling */

    r = cntNew[i-1] - 1;
    d = r + 1 - leafData;
    assert( d<nMaxCells );
    assert( r<nMaxCells );
    while( szRight==0 || szRight+szCell[d]+2<=szLeft-(szCell[r]+2) ){
      szRight += szCell[d] + 2;
      szLeft -= szCell[r] + 2;
      cntNew[i-1]--;
      r = cntNew[i-1] - 1;
      d = r + 1 - leafData;
    }
    szNew[i] = szRight;
    szNew[i-1] = szLeft;
  }

  /* Either we found one or more cells (cntnew[0])>0) or we are the
  ** a virtual root page.  A virtual root page is when the real root
  ** page is page 1 and we are the only child of that page.
  */
  assert( cntNew[0]>0 || (pParent->pgno==1 && pParent->nCell==0) );

  /*
  ** Allocate k new pages.  Reuse old pages where possible.
  */
  assert( pPage->pgno>1 );
  pageFlags = pPage->aData[0];
  for(i=0; i<k; i++){
    MemPage *pNew;
    if( i<nOld ){
      pNew = apNew[i] = apOld[i];
      pgnoNew[i] = pgnoOld[i];
      apOld[i] = 0;
      rc = sqlite3pager_write(pNew->aData);
      if( rc ) goto balance_cleanup;
    }else{
      assert( i>0 );
      rc = allocatePage(pBt, &pNew, &pgnoNew[i], pgnoNew[i-1], 0);
      if( rc ) goto balance_cleanup;
      apNew[i] = pNew;
    }
    nNew++;
    zeroPage(pNew, pageFlags);
  }

  /* Free any old pages that were not reused as new pages.
  */
  while( i<nOld ){
    rc = freePage(apOld[i]);
    if( rc ) goto balance_cleanup;
    releasePage(apOld[i]);
    apOld[i] = 0;
    i++;
  }

  /*
  ** Put the new pages in accending order.  This helps to
  ** keep entries in the disk file in order so that a scan
  ** of the table is a linear scan through the file.  That
  ** in turn helps the operating system to deliver pages
  ** from the disk more rapidly.
  **
  ** An O(n^2) insertion sort algorithm is used, but since
  ** n is never more than NB (a small constant), that should
  ** not be a problem.
  **
  ** When NB==3, this one optimization makes the database
  ** about 25% faster for large insertions and deletions.
  */
  for(i=0; i<k-1; i++){
    int minV = pgnoNew[i];
    int minI = i;
    for(j=i+1; j<k; j++){
      if( pgnoNew[j]<(unsigned)minV ){
        minI = j;
        minV = pgnoNew[j];
      }
    }
    if( minI>i ){
      int t;
      MemPage *pT;
      t = pgnoNew[i];
      pT = apNew[i];
      pgnoNew[i] = pgnoNew[minI];
      apNew[i] = apNew[minI];
      pgnoNew[minI] = t;
      apNew[minI] = pT;
    }
  }
  TRACE(("BALANCE: old: %d %d %d  new: %d(%d) %d(%d) %d(%d) %d(%d) %d(%d)\n",
    pgnoOld[0], 
    nOld>=2 ? pgnoOld[1] : 0,
    nOld>=3 ? pgnoOld[2] : 0,
    pgnoNew[0], szNew[0],
    nNew>=2 ? pgnoNew[1] : 0, nNew>=2 ? szNew[1] : 0,
    nNew>=3 ? pgnoNew[2] : 0, nNew>=3 ? szNew[2] : 0,
    nNew>=4 ? pgnoNew[3] : 0, nNew>=4 ? szNew[3] : 0,
    nNew>=5 ? pgnoNew[4] : 0, nNew>=5 ? szNew[4] : 0));

  /*
  ** Evenly distribute the data in apCell[] across the new pages.
  ** Insert divider cells into pParent as necessary.
  */
  j = 0;
  for(i=0; i<nNew; i++){
    /* Assemble the new sibling page. */
    MemPage *pNew = apNew[i];
    assert( j<nMaxCells );
    assert( pNew->pgno==pgnoNew[i] );
    assemblePage(pNew, cntNew[i]-j, &apCell[j], &szCell[j]);
    assert( pNew->nCell>0 || (nNew==1 && cntNew[0]==0) );
    assert( pNew->nOverflow==0 );

#ifndef SQLITE_OMIT_AUTOVACUUM
    /* 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.
    */
    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 ){
            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;
      if( !pNew->leaf ){
        memcpy(&pNew->aData[8], pCell, 4);
        pTemp = 0;
      }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;
        j--;
        parseCellPtr(pNew, apCell[j], &info);
        pCell = &aSpace[iSpace];
        fillInCell(pParent, pCell, 0, info.nKey, 0, 0, &sz);
        iSpace += sz;
        assert( iSpace<=pBt->pageSize*5 );
        pTemp = 0;
      }else{
        pCell -= 4;
        pTemp = &aSpace[iSpace];
        iSpace += sz;
        assert( iSpace<=pBt->pageSize*5 );
      }
      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++;
    }
  }
  assert( j==nCell );
  assert( nOld>0 );
  assert( nNew>0 );
  if( (pageFlags & PTF_LEAF)==0 ){
    memcpy(&apNew[nNew-1]->aData[8], &apCopy[nOld-1]->aData[8], 4);
  }
  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 */
    put4byte(findOverflowCell(pParent, nxDiv), pgnoNew[nNew-1]);
  }

  /*
  ** Reparent children of all cells.
  */
  for(i=0; i<nNew; i++){
    rc = reparentChildPages(apNew[i]);
    if( rc!=SQLITE_OK ) goto balance_cleanup;
  }
  rc = reparentChildPages(pParent);
  if( rc!=SQLITE_OK ) goto balance_cleanup;

  /*
  ** Balance the parent page.  Note that the current page (pPage) might
  ** have been added to the freelist so it might no longer be initialized.
  ** But the parent page will always be initialized.
  */
  assert( pParent->isInit );
  /* assert( pPage->isInit ); // No! pPage might have been added to freelist */
  /* pageIntegrity(pPage);    // No! pPage might have been added to freelist */ 
  rc = balance(pParent, 0);
  
  /*
  ** Cleanup before returning.
  */
balance_cleanup:
  sqliteFree(apCell);
  for(i=0; i<nOld; i++){
    releasePage(apOld[i]);
  }
  for(i=0; i<nNew; i++){
    releasePage(apNew[i]);
  }
  releasePage(pParent);
  TRACE(("BALANCE: finished with %d: old=%d new=%d cells=%d\n",
          pPage->pgno, nOld, nNew, nCell));
  return rc;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int balance_quick ( MemPage pPage,
MemPage pParent 
) [static]

Definition at line 4370 of file btree.c.

                                                          {
  int rc;
  MemPage *pNew;
  Pgno pgnoNew;
  u8 *pCell;
  int szCell;
  CellInfo info;
  BtShared *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);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int balance_shallower ( MemPage pPage) [static]

Definition at line 5036 of file btree.c.

                                            {
  MemPage *pChild;             /* The only child page of pPage */
  Pgno pgnoChild;              /* Page number for pChild */
  int rc = SQLITE_OK;          /* Return code from subprocedures */
  BtShared *pBt;                  /* The main BTree structure */
  int mxCellPerPage;           /* Maximum number of cells per page */
  u8 **apCell;                 /* All cells from pages being balanced */
  int *szCell;                 /* Local size of all cells */

  assert( pPage->pParent==0 );
  assert( pPage->nCell==0 );
  pBt = pPage->pBt;
  mxCellPerPage = MX_CELL(pBt);
  apCell = sqliteMallocRaw( mxCellPerPage*(sizeof(u8*)+sizeof(int)) );
  if( apCell==0 ) return SQLITE_NOMEM;
  szCell = (int*)&apCell[mxCellPerPage];
  if( pPage->leaf ){
    /* The table is completely empty */
    TRACE(("BALANCE: empty table %d\n", pPage->pgno));
  }else{
    /* The root page is empty but has one child.  Transfer the
    ** information from that one child into the root page if it 
    ** will fit.  This reduces the depth of the tree by one.
    **
    ** If the root page is page 1, it has less space available than
    ** its child (due to the 100 byte header that occurs at the beginning
    ** of the database fle), so it might not be able to hold all of the 
    ** information currently contained in the child.  If this is the 
    ** case, then do not do the transfer.  Leave page 1 empty except
    ** for the right-pointer to the child page.  The child page becomes
    ** the virtual root of the tree.
    */
    pgnoChild = get4byte(&pPage->aData[pPage->hdrOffset+8]);
    assert( pgnoChild>0 );
    assert( pgnoChild<=sqlite3pager_pagecount(pPage->pBt->pPager) );
    rc = getPage(pPage->pBt, pgnoChild, &pChild);
    if( rc ) goto end_shallow_balance;
    if( pPage->pgno==1 ){
      rc = initPage(pChild, pPage);
      if( rc ) goto end_shallow_balance;
      assert( pChild->nOverflow==0 );
      if( pChild->nFree>=100 ){
        /* The child information will fit on the root page, so do the
        ** copy */
        int i;
        zeroPage(pPage, pChild->aData[0]);
        for(i=0; i<pChild->nCell; i++){
          apCell[i] = findCell(pChild,i);
          szCell[i] = cellSizePtr(pChild, apCell[i]);
        }
        assemblePage(pPage, pChild->nCell, apCell, szCell);
        /* Copy the right-pointer of the child to the parent. */
        put4byte(&pPage->aData[pPage->hdrOffset+8], 
            get4byte(&pChild->aData[pChild->hdrOffset+8]));
        freePage(pChild);
        TRACE(("BALANCE: child %d transfer to page 1\n", pChild->pgno));
      }else{
        /* The child has more information that will fit on the root.
        ** The tree is already balanced.  Do nothing. */
        TRACE(("BALANCE: child %d will not fit on page 1\n", pChild->pgno));
      }
    }else{
      memcpy(pPage->aData, pChild->aData, pPage->pBt->usableSize);
      pPage->isInit = 0;
      pPage->pParent = 0;
      rc = initPage(pPage, 0);
      assert( rc==SQLITE_OK );
      freePage(pChild);
      TRACE(("BALANCE: transfer child %d into root %d\n",
              pChild->pgno, pPage->pgno));
    }
    rc = reparentChildPages(pPage);
    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
    if( rc!=SQLITE_OK ) goto end_shallow_balance;
    releasePage(pChild);
  }
end_shallow_balance:
  sqliteFree(apCell);
  return rc;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int cellSizePtr ( MemPage pPage,
u8 pCell 
) [static]

Definition at line 1015 of file btree.c.

                                                 {
  CellInfo info;
  parseCellPtr(pPage, pCell, &info);
  return info.nSize;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void checkAppendMsg ( IntegrityCk pCheck,
char *  zMsg1,
const char *  zFormat,
  ... 
) [static]

Definition at line 6067 of file btree.c.

 {
  va_list ap;
  char *zMsg2;
  va_start(ap, zFormat);
  zMsg2 = sqlite3VMPrintf(zFormat, ap);
  va_end(ap);
  if( zMsg1==0 ) zMsg1 = "";
  if( pCheck->zErrMsg ){
    char *zOld = pCheck->zErrMsg;
    pCheck->zErrMsg = 0;
    sqlite3SetString(&pCheck->zErrMsg, zOld, "\n", zMsg1, zMsg2, (char*)0);
    sqliteFree(zOld);
  }else{
    sqlite3SetString(&pCheck->zErrMsg, zMsg1, zMsg2, (char*)0);
  }
  sqliteFree(zMsg2);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void checkList ( IntegrityCk pCheck,
int  isFreeList,
int  iPage,
int  N,
char *  zContext 
) [static]

Definition at line 6148 of file btree.c.

 {
  int i;
  int expected = N;
  int iFirst = iPage;
  while( N-- > 0 ){
    unsigned char *pOvfl;
    if( iPage<1 ){
      checkAppendMsg(pCheck, zContext,
         "%d of %d pages missing from overflow list starting at %d",
          N+1, expected, iFirst);
      break;
    }
    if( checkRef(pCheck, iPage, zContext) ) break;
    if( sqlite3pager_get(pCheck->pPager, (Pgno)iPage, (void**)&pOvfl) ){
      checkAppendMsg(pCheck, zContext, "failed to get page %d", iPage);
      break;
    }
    if( isFreeList ){
      int n = get4byte(&pOvfl[4]);
#ifndef SQLITE_OMIT_AUTOVACUUM
      if( pCheck->pBt->autoVacuum ){
        checkPtrmap(pCheck, iPage, PTRMAP_FREEPAGE, 0, zContext);
      }
#endif
      if( n>pCheck->pBt->usableSize/4-8 ){
        checkAppendMsg(pCheck, zContext,
           "freelist leaf count too big on page %d", iPage);
        N--;
      }else{
        for(i=0; i<n; i++){
          Pgno iFreePage = get4byte(&pOvfl[8+i*4]);
#ifndef SQLITE_OMIT_AUTOVACUUM
          if( pCheck->pBt->autoVacuum ){
            checkPtrmap(pCheck, iFreePage, PTRMAP_FREEPAGE, 0, zContext);
          }
#endif
          checkRef(pCheck, iFreePage, zContext);
        }
        N -= n;
      }
    }
#ifndef SQLITE_OMIT_AUTOVACUUM
    else{
      /* If this database supports auto-vacuum and iPage is not the last
      ** page in this overflow list, check that the pointer-map entry for
      ** the following page matches iPage.
      */
      if( pCheck->pBt->autoVacuum && N>0 ){
        i = get4byte(pOvfl);
        checkPtrmap(pCheck, i, PTRMAP_OVERFLOW2, iPage, zContext);
      }
    }
#endif
    iPage = get4byte(pOvfl);
    sqlite3pager_unref(pOvfl);
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void checkPtrmap ( IntegrityCk pCheck,
Pgno  iChild,
u8  eType,
Pgno  iParent,
char *  zContext 
) [static]

Definition at line 6119 of file btree.c.

 {
  int rc;
  u8 ePtrmapType;
  Pgno iPtrmapParent;

  rc = ptrmapGet(pCheck->pBt, iChild, &ePtrmapType, &iPtrmapParent);
  if( rc!=SQLITE_OK ){
    checkAppendMsg(pCheck, zContext, "Failed to read ptrmap key=%d", iChild);
    return;
  }

  if( ePtrmapType!=eType || iPtrmapParent!=iParent ){
    checkAppendMsg(pCheck, zContext, 
      "Bad ptr map entry key=%d expected=(%d,%d) got=(%d,%d)", 
      iChild, eType, iParent, ePtrmapType, iPtrmapParent);
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int checkReadLocks ( BtShared pBt,
Pgno  pgnoRoot,
BtCursor pExclude 
) [static]

Definition at line 5231 of file btree.c.

                                                                           {
  BtCursor *p;
  for(p=pBt->pCursor; p; p=p->pNext){
    u32 flags = (p->pBtree->pSqlite ? p->pBtree->pSqlite->flags : 0);
    if( p->pgnoRoot!=pgnoRoot || p==pExclude ) continue;
    if( p->wrFlag==0 && flags&SQLITE_ReadUncommitted ) continue;
    if( p->wrFlag==0 ) return SQLITE_LOCKED;
    if( p->pPage->pgno!=p->pgnoRoot ){
      moveToRoot(p);
    }
  }
  return SQLITE_OK;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int checkRef ( IntegrityCk pCheck,
int  iPage,
char *  zContext 
) [static]

Definition at line 6100 of file btree.c.

                                                                   {
  if( iPage==0 ) return 1;
  if( iPage>pCheck->nPage || iPage<0 ){
    checkAppendMsg(pCheck, zContext, "invalid page number %d", iPage);
    return 1;
  }
  if( pCheck->anRef[iPage]==1 ){
    checkAppendMsg(pCheck, zContext, "2nd reference to page %d", iPage);
    return 1;
  }
  return  (pCheck->anRef[iPage]++)>1;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int checkTreePage ( IntegrityCk pCheck,
int  iPage,
MemPage pParent,
char *  zParentContext 
) [static]

Definition at line 6232 of file btree.c.

 {
  MemPage *pPage;
  int i, rc, depth, d2, pgno, cnt;
  int hdr, cellStart;
  int nCell;
  u8 *data;
  BtShared *pBt;
  int usableSize;
  char zContext[100];
  char *hit;

  sprintf(zContext, "Page %d: ", iPage);

  /* Check that the page exists
  */
  pBt = pCheck->pBt;
  usableSize = pBt->usableSize;
  if( iPage==0 ) return 0;
  if( checkRef(pCheck, iPage, zParentContext) ) return 0;
  if( (rc = getPage(pBt, (Pgno)iPage, &pPage))!=0 ){
    checkAppendMsg(pCheck, zContext,
       "unable to get the page. error code=%d", rc);
    return 0;
  }
  if( (rc = initPage(pPage, pParent))!=0 ){
    checkAppendMsg(pCheck, zContext, "initPage() returns error code %d", rc);
    releasePage(pPage);
    return 0;
  }

  /* Check out all the cells.
  */
  depth = 0;
  for(i=0; i<pPage->nCell; i++){
    u8 *pCell;
    int sz;
    CellInfo info;

    /* Check payload overflow pages
    */
    sprintf(zContext, "On tree page %d cell %d: ", iPage, i);
    pCell = findCell(pPage,i);
    parseCellPtr(pPage, pCell, &info);
    sz = info.nData;
    if( !pPage->intKey ) sz += info.nKey;
    if( sz>info.nLocal ){
      int nPage = (sz - info.nLocal + usableSize - 5)/(usableSize - 4);
      Pgno pgnoOvfl = get4byte(&pCell[info.iOverflow]);
#ifndef SQLITE_OMIT_AUTOVACUUM
      if( pBt->autoVacuum ){
        checkPtrmap(pCheck, pgnoOvfl, PTRMAP_OVERFLOW1, iPage, zContext);
      }
#endif
      checkList(pCheck, 0, pgnoOvfl, nPage, zContext);
    }

    /* Check sanity of left child page.
    */
    if( !pPage->leaf ){
      pgno = get4byte(pCell);
#ifndef SQLITE_OMIT_AUTOVACUUM
      if( pBt->autoVacuum ){
        checkPtrmap(pCheck, pgno, PTRMAP_BTREE, iPage, zContext);
      }
#endif
      d2 = checkTreePage(pCheck,pgno,pPage,zContext);
      if( i>0 && d2!=depth ){
        checkAppendMsg(pCheck, zContext, "Child page depth differs");
      }
      depth = d2;
    }
  }
  if( !pPage->leaf ){
    pgno = get4byte(&pPage->aData[pPage->hdrOffset+8]);
    sprintf(zContext, "On page %d at right child: ", iPage);
#ifndef SQLITE_OMIT_AUTOVACUUM
    if( pBt->autoVacuum ){
      checkPtrmap(pCheck, pgno, PTRMAP_BTREE, iPage, 0);
    }
#endif
    checkTreePage(pCheck, pgno, pPage, zContext);
  }
 
  /* Check for complete coverage of the page
  */
  data = pPage->aData;
  hdr = pPage->hdrOffset;
  hit = sqliteMalloc( usableSize );
  if( hit ){
    memset(hit, 1, get2byte(&data[hdr+5]));
    nCell = get2byte(&data[hdr+3]);
    cellStart = hdr + 12 - 4*pPage->leaf;
    for(i=0; i<nCell; i++){
      int pc = get2byte(&data[cellStart+i*2]);
      int size = cellSizePtr(pPage, &data[pc]);
      int j;
      if( (pc+size-1)>=usableSize || pc<0 ){
        checkAppendMsg(pCheck, 0, 
            "Corruption detected in cell %d on page %d",i,iPage,0);
      }else{
        for(j=pc+size-1; j>=pc; j--) hit[j]++;
      }
    }
    for(cnt=0, i=get2byte(&data[hdr+1]); i>0 && i<usableSize && cnt<10000; 
           cnt++){
      int size = get2byte(&data[i+2]);
      int j;
      if( (i+size-1)>=usableSize || i<0 ){
        checkAppendMsg(pCheck, 0,  
            "Corruption detected in cell %d on page %d",i,iPage,0);
      }else{
        for(j=i+size-1; j>=i; j--) hit[j]++;
      }
      i = get2byte(&data[i]);
    }
    for(i=cnt=0; i<usableSize; i++){
      if( hit[i]==0 ){
        cnt++;
      }else if( hit[i]>1 ){
        checkAppendMsg(pCheck, 0,
          "Multiple uses for byte %d of page %d", i, iPage);
        break;
      }
    }
    if( cnt!=data[hdr+7] ){
      checkAppendMsg(pCheck, 0, 
          "Fragmented space is %d byte reported as %d on page %d",
          cnt, data[hdr+7], iPage);
    }
  }
  sqliteFree(hit);

  releasePage(pPage);
  return depth+1;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int clearCell ( MemPage pPage,
unsigned char *  pCell 
) [static]

Definition at line 3957 of file btree.c.

                                                          {
  BtShared *pBt = pPage->pBt;
  CellInfo info;
  Pgno ovflPgno;
  int rc;

  parseCellPtr(pPage, pCell, &info);
  if( info.iOverflow==0 ){
    return SQLITE_OK;  /* No overflow pages. Return without doing anything */
  }
  ovflPgno = get4byte(&pCell[info.iOverflow]);
  while( ovflPgno!=0 ){
    MemPage *pOvfl;
    if( ovflPgno>sqlite3pager_pagecount(pBt->pPager) ){
      return SQLITE_CORRUPT_BKPT;
    }
    rc = getPage(pBt, ovflPgno, &pOvfl);
    if( rc ) return rc;
    ovflPgno = get4byte(pOvfl->aData);
    rc = freePage(pOvfl);
    sqlite3pager_unref(pOvfl->aData);
    if( rc ) return rc;
  }
  return SQLITE_OK;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int clearDatabasePage ( BtShared pBt,
Pgno  pgno,
MemPage pParent,
int  freePageFlag 
) [static]

Definition at line 5580 of file btree.c.

 {
  MemPage *pPage = 0;
  int rc;
  unsigned char *pCell;
  int i;

  if( pgno>sqlite3pager_pagecount(pBt->pPager) ){
    return SQLITE_CORRUPT_BKPT;
  }

  rc = getAndInitPage(pBt, pgno, &pPage, pParent);
  if( rc ) goto cleardatabasepage_out;
  rc = sqlite3pager_write(pPage->aData);
  if( rc ) goto cleardatabasepage_out;
  for(i=0; i<pPage->nCell; i++){
    pCell = findCell(pPage, i);
    if( !pPage->leaf ){
      rc = clearDatabasePage(pBt, get4byte(pCell), pPage->pParent, 1);
      if( rc ) goto cleardatabasepage_out;
    }
    rc = clearCell(pPage, pCell);
    if( rc ) goto cleardatabasepage_out;
  }
  if( !pPage->leaf ){
    rc = clearDatabasePage(pBt, get4byte(&pPage->aData[8]), pPage->pParent, 1);
    if( rc ) goto cleardatabasepage_out;
  }
  if( freePageFlag ){
    rc = freePage(pPage);
  }else{
    zeroPage(pPage, pPage->aData[0] | PTF_LEAF);
  }

cleardatabasepage_out:
  releasePage(pPage);
  return rc;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void decodeFlags ( MemPage pPage,
int  flagByte 
) [static]

Definition at line 1338 of file btree.c.

                                                     {
  BtShared *pBt;     /* A copy of pPage->pBt */

  assert( pPage->hdrOffset==(pPage->pgno==1 ? 100 : 0) );
  pPage->intKey = (flagByte & (PTF_INTKEY|PTF_LEAFDATA))!=0;
  pPage->zeroData = (flagByte & PTF_ZERODATA)!=0;
  pPage->leaf = (flagByte & PTF_LEAF)!=0;
  pPage->childPtrSize = 4*(pPage->leaf==0);
  pBt = pPage->pBt;
  if( flagByte & PTF_LEAFDATA ){
    pPage->leafData = 1;
    pPage->maxLocal = pBt->maxLeaf;
    pPage->minLocal = pBt->minLeaf;
  }else{
    pPage->leafData = 0;
    pPage->maxLocal = pBt->maxLocal;
    pPage->minLocal = pBt->minLocal;
  }
  pPage->hasData = !(pPage->zeroData || (!pPage->leaf && pPage->leafData));
}

Here is the caller graph for this function:

static int defragmentPage ( MemPage pPage) [static]

Definition at line 1151 of file btree.c.

                                         {
  int i;                     /* Loop counter */
  int pc;                    /* Address of a i-th cell */
  int addr;                  /* Offset of first byte after cell pointer array */
  int hdr;                   /* Offset to the page header */
  int size;                  /* Size of a cell */
  int usableSize;            /* Number of usable bytes on a page */
  int cellOffset;            /* Offset to the cell pointer array */
  int brk;                   /* Offset to the cell content area */
  int nCell;                 /* Number of cells on the page */
  unsigned char *data;       /* The page data */
  unsigned char *temp;       /* Temp area for cell content */

  assert( sqlite3pager_iswriteable(pPage->aData) );
  assert( pPage->pBt!=0 );
  assert( pPage->pBt->usableSize <= SQLITE_MAX_PAGE_SIZE );
  assert( pPage->nOverflow==0 );
  temp = sqliteMalloc( pPage->pBt->pageSize );
  if( temp==0 ) return SQLITE_NOMEM;
  data = pPage->aData;
  hdr = pPage->hdrOffset;
  cellOffset = pPage->cellOffset;
  nCell = pPage->nCell;
  assert( nCell==get2byte(&data[hdr+3]) );
  usableSize = pPage->pBt->usableSize;
  brk = get2byte(&data[hdr+5]);
  memcpy(&temp[brk], &data[brk], usableSize - brk);
  brk = usableSize;
  for(i=0; i<nCell; i++){
    u8 *pAddr;     /* The i-th cell pointer */
    pAddr = &data[cellOffset + i*2];
    pc = get2byte(pAddr);
    assert( pc<pPage->pBt->usableSize );
    size = cellSizePtr(pPage, &temp[pc]);
    brk -= size;
    memcpy(&data[brk], &temp[pc], size);
    put2byte(pAddr, brk);
  }
  assert( brk>=cellOffset+2*nCell );
  put2byte(&data[hdr+5], brk);
  data[hdr+1] = 0;
  data[hdr+2] = 0;
  data[hdr+7] = 0;
  addr = cellOffset+2*nCell;
  memset(&data[addr], 0, brk-addr);
  sqliteFree(temp);
  return SQLITE_OK;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int dfltCompare ( void NotUsed,
int  n1,
const void p1,
int  n2,
const void p2 
) [static]

Definition at line 2709 of file btree.c.

 {
  int c;
  c = memcmp(p1, p2, n1<n2 ? n1 : n2);
  if( c==0 ){
    c = n1 - n2;
  }
  return c;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void dropCell ( MemPage pPage,
int  idx,
int  sz 
) [static]

Definition at line 4172 of file btree.c.

                                                     {
  int i;          /* Loop counter */
  int pc;         /* Offset to cell content of cell being deleted */
  u8 *data;       /* pPage->aData */
  u8 *ptr;        /* Used to move bytes around within data[] */

  assert( idx>=0 && idx<pPage->nCell );
  assert( sz==cellSize(pPage, idx) );
  assert( sqlite3pager_iswriteable(pPage->aData) );
  data = pPage->aData;
  ptr = &data[pPage->cellOffset + 2*idx];
  pc = get2byte(ptr);
  assert( pc>10 && pc+sz<=pPage->pBt->usableSize );
  freeSpace(pPage, pc, sz);
  for(i=idx+1; i<pPage->nCell; i++, ptr+=2){
    ptr[0] = ptr[2];
    ptr[1] = ptr[3];
  }
  pPage->nCell--;
  put2byte(&data[pPage->hdrOffset+3], pPage->nCell);
  pPage->nFree += 2;
  pPage->idxShift = 1;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static const unsigned char* fetchPayload ( BtCursor pCur,
int pAmt,
int  skipKey 
) [static]

Definition at line 3108 of file btree.c.

 {
  unsigned char *aPayload;
  MemPage *pPage;
  u32 nKey;
  int nLocal;

  assert( pCur!=0 && pCur->pPage!=0 );
  assert( pCur->eState==CURSOR_VALID );
  pPage = pCur->pPage;
  pageIntegrity(pPage);
  assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
  getCellInfo(pCur);
  aPayload = pCur->info.pCell;
  aPayload += pCur->info.nHeader;
  if( pPage->intKey ){
    nKey = 0;
  }else{
    nKey = pCur->info.nKey;
  }
  if( skipKey ){
    aPayload += nKey;
    nLocal = pCur->info.nLocal - nKey;
  }else{
    nLocal = pCur->info.nLocal;
    if( nLocal>nKey ){
      nLocal = nKey;
    }
  }
  *pAmt = nLocal;
  return aPayload;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int fillInCell ( MemPage pPage,
unsigned char *  pCell,
const void pKey,
i64  nKey,
const void pData,
int  nData,
int pnSize 
) [static]

Definition at line 3995 of file btree.c.

 {
  int nPayload;
  const u8 *pSrc;
  int nSrc, n, rc;
  int spaceLeft;
  MemPage *pOvfl = 0;
  MemPage *pToRelease = 0;
  unsigned char *pPrior;
  unsigned char *pPayload;
  BtShared *pBt = pPage->pBt;
  Pgno pgnoOvfl = 0;
  int nHeader;
  CellInfo info;

  /* Fill in the header. */
  nHeader = 0;
  if( !pPage->leaf ){
    nHeader += 4;
  }
  if( pPage->hasData ){
    nHeader += putVarint(&pCell[nHeader], nData);
  }else{
    nData = 0;
  }
  nHeader += putVarint(&pCell[nHeader], *(u64*)&nKey);
  parseCellPtr(pPage, pCell, &info);
  assert( info.nHeader==nHeader );
  assert( info.nKey==nKey );
  assert( info.nData==nData );
  
  /* Fill in the payload */
  nPayload = nData;
  if( pPage->intKey ){
    pSrc = pData;
    nSrc = nData;
    nData = 0;
  }else{
    nPayload += nKey;
    pSrc = pKey;
    nSrc = nKey;
  }
  *pnSize = info.nSize;
  spaceLeft = info.nLocal;
  pPayload = &pCell[nHeader];
  pPrior = &pCell[info.iOverflow];

  while( nPayload>0 ){
    if( spaceLeft==0 ){
#ifndef SQLITE_OMIT_AUTOVACUUM
      Pgno pgnoPtrmap = pgnoOvfl; /* Overflow page pointer-map entry page */
#endif
      rc = allocatePage(pBt, &pOvfl, &pgnoOvfl, pgnoOvfl, 0);
#ifndef SQLITE_OMIT_AUTOVACUUM
      /* If the database supports auto-vacuum, and the second or subsequent
      ** overflow page is being allocated, add an entry to the pointer-map
      ** for that page now. The entry for the first overflow page will be
      ** added later, by the insertCell() routine.
      */
      if( pBt->autoVacuum && pgnoPtrmap!=0 && rc==SQLITE_OK ){
        rc = ptrmapPut(pBt, pgnoOvfl, PTRMAP_OVERFLOW2, pgnoPtrmap);
      }
#endif
      if( rc ){
        releasePage(pToRelease);
        /* clearCell(pPage, pCell); */
        return rc;
      }
      put4byte(pPrior, pgnoOvfl);
      releasePage(pToRelease);
      pToRelease = pOvfl;
      pPrior = pOvfl->aData;
      put4byte(pPrior, 0);
      pPayload = &pOvfl->aData[4];
      spaceLeft = pBt->usableSize - 4;
    }
    n = nPayload;
    if( n>spaceLeft ) n = spaceLeft;
    if( n>nSrc ) n = nSrc;
    assert( pSrc );
    memcpy(pPayload, pSrc, n);
    nPayload -= n;
    pPayload += n;
    pSrc += n;
    nSrc -= n;
    spaceLeft -= n;
    if( nSrc==0 ){
      nSrc = nData;
      pSrc = pData;
    }
  }
  releasePage(pToRelease);
  return SQLITE_OK;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static u8* findCell ( MemPage pPage,
int  iCell 
) [static]

Definition at line 895 of file btree.c.

                                              {
  u8 *data = pPage->aData;
  assert( iCell>=0 );
  assert( iCell<get2byte(&data[pPage->hdrOffset+3]) );
  return data + get2byte(&data[pPage->cellOffset+2*iCell]);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static u8* findOverflowCell ( MemPage pPage,
int  iCell 
) [static]

Definition at line 906 of file btree.c.

                                                      {
  int i;
  for(i=pPage->nOverflow-1; i>=0; i--){
    int k;
    struct _OvflCell *pOvfl;
    pOvfl = &pPage->aOvfl[i];
    k = pOvfl->idx;
    if( k<=iCell ){
      if( k==iCell ){
        return pOvfl->pCell;
      }
      iCell--;
    }
  }
  return findCell(pPage, iCell);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int freePage ( MemPage pPage) [static]

Definition at line 3878 of file btree.c.

                                   {
  BtShared *pBt = pPage->pBt;
  MemPage *pPage1 = pBt->pPage1;
  int rc, n, k;

  /* Prepare the page for freeing */
  assert( pPage->pgno>1 );
  pPage->isInit = 0;
  releasePage(pPage->pParent);
  pPage->pParent = 0;

  /* Increment the free page count on pPage1 */
  rc = sqlite3pager_write(pPage1->aData);
  if( rc ) return rc;
  n = get4byte(&pPage1->aData[36]);
  put4byte(&pPage1->aData[36], n+1);

#ifdef SQLITE_SECURE_DELETE
  /* If the SQLITE_SECURE_DELETE compile-time option is enabled, then
  ** always fully overwrite deleted information with zeros.
  */
  rc = sqlite3pager_write(pPage->aData);
  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 = sqlite3pager_write(pPage->aData);
    if( rc ) return rc;
    memset(pPage->aData, 0, 8);
    put4byte(&pPage1->aData[32], pPage->pgno);
    TRACE(("FREE-PAGE: %d first\n", pPage->pgno));
  }else{
    /* Other free pages already exist.  Retrive the first trunk page
    ** of the freelist and find out how many leaves it has. */
    MemPage *pTrunk;
    rc = getPage(pBt, get4byte(&pPage1->aData[32]), &pTrunk);
    if( rc ) return rc;
    k = get4byte(&pTrunk->aData[4]);
    if( k>=pBt->usableSize/4 - 8 ){
      /* The trunk is full.  Turn the page being freed into a new
      ** trunk page with no leaves. */
      rc = sqlite3pager_write(pPage->aData);
      if( rc ) return rc;
      put4byte(pPage->aData, pTrunk->pgno);
      put4byte(&pPage->aData[4], 0);
      put4byte(&pPage1->aData[32], pPage->pgno);
      TRACE(("FREE-PAGE: %d new trunk page replacing %d\n",
              pPage->pgno, pTrunk->pgno));
    }else{
      /* Add the newly freed page as a leaf on the current trunk */
      rc = sqlite3pager_write(pTrunk->aData);
      if( rc ) return rc;
      put4byte(&pTrunk->aData[4], k+1);
      put4byte(&pTrunk->aData[8+k*4], pPage->pgno);
#ifndef SQLITE_SECURE_DELETE
      sqlite3pager_dont_write(pBt->pPager, pPage->pgno);
#endif
      TRACE(("FREE-PAGE: %d leaf on trunk page %d\n",pPage->pgno,pTrunk->pgno));
    }
    releasePage(pTrunk);
  }
  return rc;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void freeSpace ( MemPage pPage,
int  start,
int  size 
) [static]

Definition at line 1274 of file btree.c.

                                                          {
  int addr, pbegin, hdr;
  unsigned char *data = pPage->aData;

  assert( pPage->pBt!=0 );
  assert( sqlite3pager_iswriteable(data) );
  assert( start>=pPage->hdrOffset+6+(pPage->leaf?0:4) );
  assert( (start + size)<=pPage->pBt->usableSize );
  if( size<4 ) size = 4;

#ifdef SQLITE_SECURE_DELETE
  /* Overwrite deleted information with zeros when the SECURE_DELETE 
  ** option is enabled at compile-time */
  memset(&data[start], 0, size);
#endif

  /* Add the space back into the linked list of freeblocks */
  hdr = pPage->hdrOffset;
  addr = hdr + 1;
  while( (pbegin = get2byte(&data[addr]))<start && pbegin>0 ){
    assert( pbegin<=pPage->pBt->usableSize-4 );
    assert( pbegin>addr );
    addr = pbegin;
  }
  assert( pbegin<=pPage->pBt->usableSize-4 );
  assert( pbegin>addr || pbegin==0 );
  put2byte(&data[addr], start);
  put2byte(&data[start], pbegin);
  put2byte(&data[start+2], size);
  pPage->nFree += size;

  /* Coalesce adjacent free blocks */
  addr = pPage->hdrOffset + 1;
  while( (pbegin = get2byte(&data[addr]))>0 ){
    int pnext, psize;
    assert( pbegin>addr );
    assert( pbegin<=pPage->pBt->usableSize-4 );
    pnext = get2byte(&data[pbegin]);
    psize = get2byte(&data[pbegin+2]);
    if( pbegin + psize + 3 >= pnext && pnext>0 ){
      int frag = pnext - (pbegin+psize);
      assert( frag<=data[pPage->hdrOffset+7] );
      data[pPage->hdrOffset+7] -= frag;
      put2byte(&data[pbegin], get2byte(&data[pnext]));
      put2byte(&data[pbegin+2], pnext+get2byte(&data[pnext+2])-pbegin);
    }else{
      addr = pbegin;
    }
  }

  /* If the cell content area begins with a freeblock, remove it. */
  if( data[hdr+1]==data[hdr+5] && data[hdr+2]==data[hdr+6] ){
    int top;
    pbegin = get2byte(&data[hdr+1]);
    memcpy(&data[hdr+1], &data[pbegin], 2);
    top = get2byte(&data[hdr+5]);
    put2byte(&data[hdr+5], top + get2byte(&data[pbegin+2]));
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static u32 get2byte ( unsigned char *  p) [static]

Definition at line 442 of file btree.c.

                                     {
  return (p[0]<<8) | p[1];
}

Here is the caller graph for this function:

static u32 get4byte ( unsigned char *  p) [static]

Definition at line 445 of file btree.c.

                                     {
  return (p[0]<<24) | (p[1]<<16) | (p[2]<<8) | p[3];
}

Here is the caller graph for this function:

static int getAndInitPage ( BtShared pBt,
Pgno  pgno,
MemPage **  ppPage,
MemPage pParent 
) [static]

Definition at line 1500 of file btree.c.

 {
  int rc;
  if( pgno==0 ){
    return SQLITE_CORRUPT_BKPT; 
  }
  rc = getPage(pBt, pgno, ppPage);
  if( rc==SQLITE_OK && (*ppPage)->isInit==0 ){
    rc = initPage(*ppPage, pParent);
  }
  return rc;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void getCellInfo ( BtCursor pCur) [static]

Definition at line 2898 of file btree.c.

                                       {
  if( pCur->info.nSize==0 ){
    parseCell(pCur->pPage, pCur->idx, &pCur->info);
  }else{
#ifndef NDEBUG
    CellInfo info;
    memset(&info, 0, sizeof(info));
    parseCell(pCur->pPage, pCur->idx, &info);
    assert( memcmp(&info, &pCur->info, sizeof(info))==0 );
#endif
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int getPage ( BtShared pBt,
Pgno  pgno,
MemPage **  ppPage 
) [static]

Definition at line 1480 of file btree.c.

                                                              {
  int rc;
  unsigned char *aData;
  MemPage *pPage;
  rc = sqlite3pager_get(pBt->pPager, pgno, (void**)&aData);
  if( rc ) return rc;
  pPage = (MemPage*)&aData[pBt->pageSize];
  pPage->aData = aData;
  pPage->pBt = pBt;
  pPage->pgno = pgno;
  pPage->hdrOffset = pPage->pgno==1 ? 100 : 0;
  *ppPage = pPage;
  return SQLITE_OK;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int getPayload ( BtCursor pCur,
int  offset,
int  amt,
unsigned char *  pBuf,
int  skipKey 
) [static]

Definition at line 2964 of file btree.c.

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

  assert( pCur!=0 && pCur->pPage!=0 );
  assert( pCur->eState==CURSOR_VALID );
  pBt = pCur->pBtree->pBt;
  pPage = pCur->pPage;
  pageIntegrity(pPage);
  assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
  getCellInfo(pCur);
  aPayload = pCur->info.pCell + pCur->info.nHeader;
  if( pPage->intKey ){
    nKey = 0;
  }else{
    nKey = pCur->info.nKey;
  }
  assert( offset>=0 );
  if( skipKey ){
    offset += nKey;
  }
  if( offset+amt > nKey+pCur->info.nData ){
    return SQLITE_ERROR;
  }
  if( offset<pCur->info.nLocal ){
    int a = amt;
    if( a+offset>pCur->info.nLocal ){
      a = pCur->info.nLocal - offset;
    }
    memcpy(pBuf, &aPayload[offset], a);
    if( a==amt ){
      return SQLITE_OK;
    }
    offset = 0;
    pBuf += a;
    amt -= a;
  }else{
    offset -= pCur->info.nLocal;
  }
  ovflSize = pBt->usableSize - 4;
  if( amt>0 ){
    nextPage = get4byte(&aPayload[pCur->info.nLocal]);
    while( amt>0 && nextPage ){
      rc = sqlite3pager_get(pBt->pPager, nextPage, (void**)&aPayload);
      if( rc!=0 ){
        return rc;
      }
      nextPage = get4byte(aPayload);
      if( offset<ovflSize ){
        int a = amt;
        if( a + offset > ovflSize ){
          a = ovflSize - offset;
        }
        memcpy(pBuf, &aPayload[offset+4], a);
        offset = 0;
        amt -= a;
        pBuf += a;
      }else{
        offset -= ovflSize;
      }
      sqlite3pager_unref(aPayload);
    }
  }

  if( amt>0 ){
    return SQLITE_CORRUPT_BKPT;
  }
  return SQLITE_OK;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void getTempCursor ( BtCursor pCur,
BtCursor pTempCur 
) [static]

Definition at line 2872 of file btree.c.

                                                             {
  memcpy(pTempCur, pCur, sizeof(*pCur));
  pTempCur->pNext = 0;
  pTempCur->pPrev = 0;
  if( pTempCur->pPage ){
    sqlite3pager_ref(pTempCur->pPage->aData);
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int initPage ( MemPage pPage,
MemPage pParent 
) [static]

Definition at line 1372 of file btree.c.

 {
  int pc;            /* Address of a freeblock within pPage->aData[] */
  int hdr;           /* Offset to beginning of page header */
  u8 *data;          /* Equal to pPage->aData */
  BtShared *pBt;        /* The main btree structure */
  int usableSize;    /* Amount of usable space on each page */
  int cellOffset;    /* Offset from start of page to first cell pointer */
  int nFree;         /* Number of unused bytes on the page */
  int top;           /* First byte of the cell content area */

  pBt = pPage->pBt;
  assert( pBt!=0 );
  assert( pParent==0 || pParent->pBt==pBt );
  assert( pPage->pgno==sqlite3pager_pagenumber(pPage->aData) );
  assert( pPage->aData == &((unsigned char*)pPage)[-pBt->pageSize] );
  if( pPage->pParent!=pParent && (pPage->pParent!=0 || pPage->isInit) ){
    /* The parent page should never change unless the file is corrupt */
    return SQLITE_CORRUPT_BKPT;
  }
  if( pPage->isInit ) return SQLITE_OK;
  if( pPage->pParent==0 && pParent!=0 ){
    pPage->pParent = pParent;
    sqlite3pager_ref(pParent->aData);
  }
  hdr = pPage->hdrOffset;
  data = pPage->aData;
  decodeFlags(pPage, data[hdr]);
  pPage->nOverflow = 0;
  pPage->idxShift = 0;
  usableSize = pBt->usableSize;
  pPage->cellOffset = cellOffset = hdr + 12 - 4*pPage->leaf;
  top = get2byte(&data[hdr+5]);
  pPage->nCell = get2byte(&data[hdr+3]);
  if( pPage->nCell>MX_CELL(pBt) ){
    /* To many cells for a single page.  The page must be corrupt */
    return SQLITE_CORRUPT_BKPT;
  }
  if( pPage->nCell==0 && pParent!=0 && pParent->pgno!=1 ){
    /* All pages must have at least one cell, except for root pages */
    return SQLITE_CORRUPT_BKPT;
  }

  /* Compute the total free space on the page */
  pc = get2byte(&data[hdr+1]);
  nFree = data[hdr+7] + top - (cellOffset + 2*pPage->nCell);
  while( pc>0 ){
    int next, size;
    if( pc>usableSize-4 ){
      /* Free block is off the page */
      return SQLITE_CORRUPT_BKPT; 
    }
    next = get2byte(&data[pc]);
    size = get2byte(&data[pc+2]);
    if( next>0 && next<=pc+size+3 ){
      /* Free blocks must be in accending order */
      return SQLITE_CORRUPT_BKPT; 
    }
    nFree += size;
    pc = next;
  }
  pPage->nFree = nFree;
  if( nFree>=usableSize ){
    /* Free space cannot exceed total page size */
    return SQLITE_CORRUPT_BKPT; 
  }

  pPage->isInit = 1;
  pageIntegrity(pPage);
  return SQLITE_OK;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int insertCell ( MemPage pPage,
int  i,
u8 pCell,
int  sz,
u8 pTemp,
u8  nSkip 
) [static]

Definition at line 4213 of file btree.c.

 {
  int idx;          /* Where to write new cell content in data[] */
  int j;            /* Loop counter */
  int top;          /* First byte of content for any cell in data[] */
  int end;          /* First byte past the last cell pointer in data[] */
  int ins;          /* Index in data[] where new cell pointer is inserted */
  int hdr;          /* Offset into data[] of the page header */
  int cellOffset;   /* Address of first cell pointer in data[] */
  u8 *data;         /* The content of the whole page */
  u8 *ptr;          /* Used for moving information around in data[] */

  assert( i>=0 && i<=pPage->nCell+pPage->nOverflow );
  assert( sz==cellSizePtr(pPage, pCell) );
  assert( sqlite3pager_iswriteable(pPage->aData) );
  if( pPage->nOverflow || sz+2>pPage->nFree ){
    if( pTemp ){
      memcpy(pTemp+nSkip, pCell+nSkip, sz-nSkip);
      pCell = pTemp;
    }
    j = pPage->nOverflow++;
    assert( j<sizeof(pPage->aOvfl)/sizeof(pPage->aOvfl[0]) );
    pPage->aOvfl[j].pCell = pCell;
    pPage->aOvfl[j].idx = i;
    pPage->nFree = 0;
  }else{
    data = pPage->aData;
    hdr = pPage->hdrOffset;
    top = get2byte(&data[hdr+5]);
    cellOffset = pPage->cellOffset;
    end = cellOffset + 2*pPage->nCell + 2;
    ins = cellOffset + 2*i;
    if( end > top - sz ){
      int rc = defragmentPage(pPage);
      if( rc!=SQLITE_OK ) return rc;
      top = get2byte(&data[hdr+5]);
      assert( end + sz <= top );
    }
    idx = allocateSpace(pPage, sz);
    assert( idx>0 );
    assert( end <= get2byte(&data[hdr+5]) );
    pPage->nCell++;
    pPage->nFree -= 2;
    memcpy(&data[idx+nSkip], pCell+nSkip, sz-nSkip);
    for(j=end-2, ptr=&data[j]; j>ins; j-=2, ptr-=2){
      ptr[0] = ptr[-2];
      ptr[1] = ptr[-1];
    }
    put2byte(&data[ins], idx);
    put2byte(&data[hdr+3], pPage->nCell);
    pPage->idxShift = 1;
    pageIntegrity(pPage);
#ifndef SQLITE_OMIT_AUTOVACUUM
    if( pPage->pBt->autoVacuum ){
      /* The cell may contain a pointer to an overflow page. If so, write
      ** the entry for the overflow page into the pointer map.
      */
      CellInfo info;
      parseCellPtr(pPage, pCell, &info);
      if( (info.nData+(pPage->intKey?0:info.nKey))>info.nLocal ){
        Pgno pgnoOvfl = get4byte(&pCell[info.iOverflow]);
        int rc = ptrmapPut(pPage->pBt, pgnoOvfl, PTRMAP_OVERFLOW1, pPage->pgno);
        if( rc!=SQLITE_OK ) return rc;
      }
    }
#endif
  }

  return SQLITE_OK;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int isRootPage ( MemPage pPage) [static]

Definition at line 3206 of file btree.c.

                                     {
  MemPage *pParent = pPage->pParent;
  if( pParent==0 ) return 1;
  if( pParent->pgno>1 ) return 0;
  if( get2byte(&pParent->aData[pParent->hdrOffset+3])==0 ) return 1;
  return 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int lockBtree ( BtShared pBt) [static]

Definition at line 1924 of file btree.c.

                                   {
  int rc, pageSize;
  MemPage *pPage1;
  if( pBt->pPage1 ) return SQLITE_OK;
  rc = getPage(pBt, 1, &pPage1);
  if( rc!=SQLITE_OK ) return rc;
  

  /* Do some checking to help insure the file we opened really is
  ** a valid database file. 
  */
  rc = SQLITE_NOTADB;
  if( sqlite3pager_pagecount(pBt->pPager)>0 ){
    u8 *page1 = pPage1->aData;
    if( memcmp(page1, zMagicHeader, 16)!=0 ){
      goto page1_init_failed;
    }
    if( page1[18]>1 || page1[19]>1 ){
      goto page1_init_failed;
    }
    pageSize = get2byte(&page1[16]);
    if( ((pageSize-1)&pageSize)!=0 ){
      goto page1_init_failed;
    }
    assert( (pageSize & 7)==0 );
    pBt->pageSize = pageSize;
    pBt->usableSize = pageSize - page1[20];
    if( pBt->usableSize<500 ){
      goto page1_init_failed;
    }
    pBt->maxEmbedFrac = page1[21];
    pBt->minEmbedFrac = page1[22];
    pBt->minLeafFrac = page1[23];
#ifndef SQLITE_OMIT_AUTOVACUUM
    pBt->autoVacuum = (get4byte(&page1[36 + 4*4])?1:0);
#endif
  }

  /* maxLocal is the maximum amount of payload to store locally for
  ** a cell.  Make sure it is small enough so that at least minFanout
  ** cells can will fit on one page.  We assume a 10-byte page header.
  ** Besides the payload, the cell must store:
  **     2-byte pointer to the cell
  **     4-byte child pointer
  **     9-byte nKey value
  **     4-byte nData value
  **     4-byte overflow page pointer
  ** So a cell consists of a 2-byte poiner, a header which is as much as
  ** 17 bytes long, 0 to N bytes of payload, and an optional 4 byte overflow
  ** page pointer.
  */
  pBt->maxLocal = (pBt->usableSize-12)*pBt->maxEmbedFrac/255 - 23;
  pBt->minLocal = (pBt->usableSize-12)*pBt->minEmbedFrac/255 - 23;
  pBt->maxLeaf = pBt->usableSize - 35;
  pBt->minLeaf = (pBt->usableSize-12)*pBt->minLeafFrac/255 - 23;
  if( pBt->minLocal>pBt->maxLocal || pBt->maxLocal<0 ){
    goto page1_init_failed;
  }
  assert( pBt->maxLeaf + 23 <= MX_CELL_SIZE(pBt) );
  pBt->pPage1 = pPage1;
  return SQLITE_OK;

page1_init_failed:
  releasePage(pPage1);
  pBt->pPage1 = 0;
  return rc;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int lockBtreeWithRetry ( Btree pRef) [static]

Definition at line 1996 of file btree.c.

                                          {
  int rc = SQLITE_OK;
  if( pRef->inTrans==TRANS_NONE ){
    u8 inTransaction = pRef->pBt->inTransaction;
    btreeIntegrity(pRef);
    rc = sqlite3BtreeBeginTrans(pRef, 0);
    pRef->pBt->inTransaction = inTransaction;
    pRef->inTrans = TRANS_NONE;
    if( rc==SQLITE_OK ){
      pRef->pBt->nTransaction--;
    }
    btreeIntegrity(pRef);
  }
  return rc;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int lockTable ( Btree p,
Pgno  iTable,
u8  eLock 
) [static]

Definition at line 665 of file btree.c.

                                                     {
  BtShared *pBt = p->pBt;
  BtLock *pLock = 0;
  BtLock *pIter;

  /* This is a no-op if the shared-cache is not enabled */
  if( 0==sqlite3ThreadDataReadOnly()->useSharedData ){
    return SQLITE_OK;
  }

  assert( SQLITE_OK==queryTableLock(p, iTable, eLock) );

  /* If the read-uncommitted flag is set and a read-lock is requested,
  ** return early without adding an entry to the BtShared.pLock list. See
  ** comment in function queryTableLock() for more info on handling 
  ** the ReadUncommitted flag.
  */
  if( 
    (p->pSqlite) && 
    (p->pSqlite->flags&SQLITE_ReadUncommitted) && 
    (eLock==READ_LOCK) &&
    iTable!=MASTER_ROOT
  ){
    return SQLITE_OK;
  }

  /* First search the list for an existing lock on this table. */
  for(pIter=pBt->pLock; pIter; pIter=pIter->pNext){
    if( pIter->iTable==iTable && pIter->pBtree==p ){
      pLock = pIter;
      break;
    }
  }

  /* If the above search did not find a BtLock struct associating Btree p
  ** with table iTable, allocate one and link it into the list.
  */
  if( !pLock ){
    pLock = (BtLock *)sqliteMalloc(sizeof(BtLock));
    if( !pLock ){
      return SQLITE_NOMEM;
    }
    pLock->iTable = iTable;
    pLock->pBtree = p;
    pLock->pNext = pBt->pLock;
    pBt->pLock = pLock;
  }

  /* Set the BtLock.eLock variable to the maximum of the current lock
  ** and the requested lock. This means if a write-lock was already held
  ** and a read-lock requested, we don't incorrectly downgrade the lock.
  */
  assert( WRITE_LOCK>READ_LOCK );
  if( eLock>pLock->eLock ){
    pLock->eLock = eLock;
  }

  return SQLITE_OK;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int modifyPagePointer ( MemPage pPage,
Pgno  iFrom,
Pgno  iTo,
u8  eType 
) [static]

Definition at line 2225 of file btree.c.

                                                                            {
  if( eType==PTRMAP_OVERFLOW2 ){
    /* The pointer is always the first 4 bytes of the page in this case.  */
    if( get4byte(pPage->aData)!=iFrom ){
      return SQLITE_CORRUPT_BKPT;
    }
    put4byte(pPage->aData, iTo);
  }else{
    int isInitOrig = pPage->isInit;
    int i;
    int nCell;

    initPage(pPage, 0);
    nCell = pPage->nCell;

    for(i=0; i<nCell; i++){
      u8 *pCell = findCell(pPage, i);
      if( eType==PTRMAP_OVERFLOW1 ){
        CellInfo info;
        parseCellPtr(pPage, pCell, &info);
        if( info.iOverflow ){
          if( iFrom==get4byte(&pCell[info.iOverflow]) ){
            put4byte(&pCell[info.iOverflow], iTo);
            break;
          }
        }
      }else{
        if( get4byte(pCell)==iFrom ){
          put4byte(pCell, iTo);
          break;
        }
      }
    }
  
    if( i==nCell ){
      if( eType!=PTRMAP_BTREE || 
          get4byte(&pPage->aData[pPage->hdrOffset+8])!=iFrom ){
        return SQLITE_CORRUPT_BKPT;
      }
      put4byte(&pPage->aData[pPage->hdrOffset+8], iTo);
    }

    pPage->isInit = isInitOrig;
  }
  return SQLITE_OK;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int moveToChild ( BtCursor pCur,
u32  newPgno 
) [static]

Definition at line 3174 of file btree.c.

                                                   {
  int rc;
  MemPage *pNewPage;
  MemPage *pOldPage;
  BtShared *pBt = pCur->pBtree->pBt;

  assert( pCur->eState==CURSOR_VALID );
  rc = getAndInitPage(pBt, newPgno, &pNewPage, pCur->pPage);
  if( rc ) return rc;
  pageIntegrity(pNewPage);
  pNewPage->idxParent = pCur->idx;
  pOldPage = pCur->pPage;
  pOldPage->idxShift = 0;
  releasePage(pOldPage);
  pCur->pPage = pNewPage;
  pCur->idx = 0;
  pCur->info.nSize = 0;
  if( pNewPage->nCell<1 ){
    return SQLITE_CORRUPT_BKPT;
  }
  return SQLITE_OK;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int moveToLeftmost ( BtCursor pCur) [static]

Definition at line 3288 of file btree.c.

                                         {
  Pgno pgno;
  int rc;
  MemPage *pPage;

  assert( pCur->eState==CURSOR_VALID );
  while( !(pPage = pCur->pPage)->leaf ){
    assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
    pgno = get4byte(findCell(pPage, pCur->idx));
    rc = moveToChild(pCur, pgno);
    if( rc ) return rc;
  }
  return SQLITE_OK;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void moveToParent ( BtCursor pCur) [static]

Definition at line 3222 of file btree.c.

                                        {
  MemPage *pParent;
  MemPage *pPage;
  int idxParent;

  assert( pCur->eState==CURSOR_VALID );
  pPage = pCur->pPage;
  assert( pPage!=0 );
  assert( !isRootPage(pPage) );
  pageIntegrity(pPage);
  pParent = pPage->pParent;
  assert( pParent!=0 );
  pageIntegrity(pParent);
  idxParent = pPage->idxParent;
  sqlite3pager_ref(pParent->aData);
  releasePage(pPage);
  pCur->pPage = pParent;
  pCur->info.nSize = 0;
  assert( pParent->idxShift==0 );
  pCur->idx = idxParent;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int moveToRightmost ( BtCursor pCur) [static]

Definition at line 3313 of file btree.c.

                                          {
  Pgno pgno;
  int rc;
  MemPage *pPage;

  assert( pCur->eState==CURSOR_VALID );
  while( !(pPage = pCur->pPage)->leaf ){
    pgno = get4byte(&pPage->aData[pPage->hdrOffset+8]);
    pCur->idx = pPage->nCell;
    rc = moveToChild(pCur, pgno);
    if( rc ) return rc;
  }
  pCur->idx = pPage->nCell - 1;
  pCur->info.nSize = 0;
  return SQLITE_OK;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int moveToRoot ( BtCursor pCur) [static]

Definition at line 3247 of file btree.c.

                                     {
  MemPage *pRoot;
  int rc = SQLITE_OK;
  BtShared *pBt = pCur->pBtree->pBt;

  restoreOrClearCursorPosition(pCur, 0);
  pRoot = pCur->pPage;
  if( pRoot && pRoot->pgno==pCur->pgnoRoot ){
    assert( pRoot->isInit );
  }else{
    if( 
      SQLITE_OK!=(rc = getAndInitPage(pBt, pCur->pgnoRoot, &pRoot, 0))
    ){
      pCur->eState = CURSOR_INVALID;
      return rc;
    }
    releasePage(pCur->pPage);
    pageIntegrity(pRoot);
    pCur->pPage = pRoot;
  }
  pCur->idx = 0;
  pCur->info.nSize = 0;
  if( pRoot->nCell==0 && !pRoot->leaf ){
    Pgno subpage;
    assert( pRoot->pgno==1 );
    subpage = get4byte(&pRoot->aData[pRoot->hdrOffset+8]);
    assert( subpage>0 );
    pCur->eState = CURSOR_VALID;
    rc = moveToChild(pCur, subpage);
  }
  pCur->eState = ((pCur->pPage->nCell>0)?CURSOR_VALID:CURSOR_INVALID);
  return rc;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int newDatabase ( BtShared pBt) [static]

Definition at line 2041 of file btree.c.

                                     {
  MemPage *pP1;
  unsigned char *data;
  int rc;
  if( sqlite3pager_pagecount(pBt->pPager)>0 ) return SQLITE_OK;
  pP1 = pBt->pPage1;
  assert( pP1!=0 );
  data = pP1->aData;
  rc = sqlite3pager_write(data);
  if( rc ) return rc;
  memcpy(data, zMagicHeader, sizeof(zMagicHeader));
  assert( sizeof(zMagicHeader)==16 );
  put2byte(&data[16], pBt->pageSize);
  data[18] = 1;
  data[19] = 1;
  data[20] = pBt->pageSize - pBt->usableSize;
  data[21] = pBt->maxEmbedFrac;
  data[22] = pBt->minEmbedFrac;
  data[23] = pBt->minLeafFrac;
  memset(&data[24], 0, 100-24);
  zeroPage(pP1, PTF_INTKEY|PTF_LEAF|PTF_LEAFDATA );
  pBt->pageSizeFixed = 1;
#ifndef SQLITE_OMIT_AUTOVACUUM
  if( pBt->autoVacuum ){
    put4byte(&data[36 + 4*4], 1);
  }
#endif
  return SQLITE_OK;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void pageDestructor ( void pData,
int  pageSize 
) [static]

Definition at line 1535 of file btree.c.

                                                     {
  MemPage *pPage;
  assert( (pageSize & 7)==0 );
  pPage = (MemPage*)&((char*)pData)[pageSize];
  if( pPage->pParent ){
    MemPage *pParent = pPage->pParent;
    pPage->pParent = 0;
    releasePage(pParent);
  }
  pPage->isInit = 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void pageReinit ( void pData,
int  pageSize 
) [static]

Definition at line 1555 of file btree.c.

                                                 {
  MemPage *pPage;
  assert( (pageSize & 7)==0 );
  pPage = (MemPage*)&((char*)pData)[pageSize];
  if( pPage->isInit ){
    pPage->isInit = 0;
    initPage(pPage, pPage->pParent);
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void parseCell ( MemPage pPage,
int  iCell,
CellInfo pInfo 
) [static]

Definition at line 994 of file btree.c.

 {
  parseCellPtr(pPage, findCell(pPage, iCell), pInfo);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void parseCellPtr ( MemPage pPage,
u8 pCell,
CellInfo pInfo 
) [static]

Definition at line 929 of file btree.c.

 {
  int n;                  /* Number bytes in cell content header */
  u32 nPayload;           /* Number of bytes of cell payload */

  pInfo->pCell = pCell;
  assert( pPage->leaf==0 || pPage->leaf==1 );
  n = pPage->childPtrSize;
  assert( n==4-4*pPage->leaf );
  if( pPage->hasData ){
    n += getVarint32(&pCell[n], &nPayload);
  }else{
    nPayload = 0;
  }
  pInfo->nData = nPayload;
  if( pPage->intKey ){
    n += getVarint(&pCell[n], (u64 *)&pInfo->nKey);
  }else{
    u32 x;
    n += getVarint32(&pCell[n], &x);
    pInfo->nKey = x;
    nPayload += x;
  }
  pInfo->nHeader = n;
  if( nPayload<=pPage->maxLocal ){
    /* This is the (easy) common case where the entire payload fits
    ** on the local page.  No overflow is required.
    */
    int nSize;          /* Total size of cell content in bytes */
    pInfo->nLocal = nPayload;
    pInfo->iOverflow = 0;
    nSize = nPayload + n;
    if( nSize<4 ){
      nSize = 4;        /* Minimum cell size is 4 */
    }
    pInfo->nSize = nSize;
  }else{
    /* If the payload will not fit completely on the local page, we have
    ** to decide how much to store locally and how much to spill onto
    ** overflow pages.  The strategy is to minimize the amount of unused
    ** space on overflow pages while keeping the amount of local storage
    ** in between minLocal and maxLocal.
    **
    ** Warning:  changing the way overflow payload is distributed in any
    ** way will result in an incompatible file format.
    */
    int minLocal;  /* Minimum amount of payload held locally */
    int maxLocal;  /* Maximum amount of payload held locally */
    int surplus;   /* Overflow payload available for local storage */

    minLocal = pPage->minLocal;
    maxLocal = pPage->maxLocal;
    surplus = minLocal + (nPayload - minLocal)%(pPage->pBt->usableSize - 4);
    if( surplus <= maxLocal ){
      pInfo->nLocal = surplus;
    }else{
      pInfo->nLocal = minLocal;
    }
    pInfo->iOverflow = pInfo->nLocal + n;
    pInfo->nSize = pInfo->iOverflow + 4;
  }
}

Here is the caller graph for this function:

static int ptrmapGet ( BtShared pBt,
Pgno  key,
u8 pEType,
Pgno pPgno 
) [static]

Definition at line 864 of file btree.c.

                                                                      {
  int iPtrmap;       /* Pointer map page index */
  u8 *pPtrmap;       /* Pointer map page data */
  int offset;        /* Offset of entry in pointer map */
  int rc;

  iPtrmap = PTRMAP_PAGENO(pBt, key);
  rc = sqlite3pager_get(pBt->pPager, iPtrmap, (void **)&pPtrmap);
  if( rc!=0 ){
    return rc;
  }

  offset = PTRMAP_PTROFFSET(pBt, key);
  assert( pEType!=0 );
  *pEType = pPtrmap[offset];
  if( pPgno ) *pPgno = get4byte(&pPtrmap[offset+1]);

  sqlite3pager_unref(pPtrmap);
  if( *pEType<1 || *pEType>5 ) return SQLITE_CORRUPT_BKPT;
  return SQLITE_OK;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static Pgno ptrmapPageno ( BtShared pBt,
Pgno  pgno 
) [static]

Definition at line 770 of file btree.c.

                                                  {
  int nPagesPerMapPage = (pBt->usableSize/5)+1;
  int iPtrMap = (pgno-2)/nPagesPerMapPage;
  int ret = (iPtrMap*nPagesPerMapPage) + 2; 
  if( ret==PENDING_BYTE_PAGE(pBt) ){
    ret++;
  }
  return ret;
}
static int ptrmapPut ( BtShared pBt,
Pgno  key,
u8  eType,
Pgno  parent 
) [static]

Definition at line 824 of file btree.c.

                                                                    {
  u8 *pPtrmap;    /* The pointer map page */
  Pgno iPtrmap;   /* The pointer map page number */
  int offset;     /* Offset in pointer map page */
  int rc;

  /* The master-journal page number must never be used as a pointer map page */
  assert( 0==PTRMAP_ISPAGE(pBt, PENDING_BYTE_PAGE(pBt)) );

  assert( pBt->autoVacuum );
  if( key==0 ){
    return SQLITE_CORRUPT_BKPT;
  }
  iPtrmap = PTRMAP_PAGENO(pBt, key);
  rc = sqlite3pager_get(pBt->pPager, iPtrmap, (void **)&pPtrmap);
  if( rc!=SQLITE_OK ){
    return rc;
  }
  offset = PTRMAP_PTROFFSET(pBt, key);

  if( eType!=pPtrmap[offset] || get4byte(&pPtrmap[offset+1])!=parent ){
    TRACE(("PTRMAP_UPDATE: %d->(%d,%d)\n", key, eType, parent));
    rc = sqlite3pager_write(pPtrmap);
    if( rc==SQLITE_OK ){
      pPtrmap[offset] = eType;
      put4byte(&pPtrmap[offset+1], parent);
    }
  }

  sqlite3pager_unref(pPtrmap);
  return rc;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int ptrmapPutOvfl ( MemPage pPage,
int  iCell 
) [static]

Definition at line 1043 of file btree.c.

                                                   {
  u8 *pCell;
  pCell = findOverflowCell(pPage, iCell);
  return ptrmapPutOvflPtr(pPage, pCell);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int ptrmapPutOvflPtr ( MemPage pPage,
u8 pCell 
) [static]

Definition at line 1027 of file btree.c.

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

Here is the call graph for this function:

Here is the caller graph for this function:

static void put2byte ( unsigned char *  p,
u32  v 
) [static]

Definition at line 448 of file btree.c.

                                             {
  p[0] = v>>8;
  p[1] = v;
}

Here is the caller graph for this function:

static void put4byte ( unsigned char *  p,
u32  v 
) [static]

Definition at line 452 of file btree.c.

                                             {
  p[0] = v>>24;
  p[1] = v>>16;
  p[2] = v>>8;
  p[3] = v;
}

Here is the caller graph for this function:

static int queryTableLock ( Btree p,
Pgno  iTab,
u8  eLock 
) [static]

Definition at line 618 of file btree.c.

                                                        {
  BtShared *pBt = p->pBt;
  BtLock *pIter;

  /* This is a no-op if the shared-cache is not enabled */
  if( 0==sqlite3ThreadDataReadOnly()->useSharedData ){
    return SQLITE_OK;
  }

  /* This (along with lockTable()) is where the ReadUncommitted flag is
  ** dealt with. If the caller is querying for a read-lock and the flag is
  ** set, it is unconditionally granted - even if there are write-locks
  ** on the table. If a write-lock is requested, the ReadUncommitted flag
  ** is not considered.
  **
  ** In function lockTable(), if a read-lock is demanded and the 
  ** ReadUncommitted flag is set, no entry is added to the locks list 
  ** (BtShared.pLock).
  **
  ** To summarize: If the ReadUncommitted flag is set, then read cursors do
  ** not create or respect table locks. The locking procedure for a 
  ** write-cursor does not change.
  */
  if( 
    !p->pSqlite || 
    0==(p->pSqlite->flags&SQLITE_ReadUncommitted) || 
    eLock==WRITE_LOCK ||
    iTab==MASTER_ROOT
  ){
    for(pIter=pBt->pLock; pIter; pIter=pIter->pNext){
      if( pIter->pBtree!=p && pIter->iTable==iTab && 
          (pIter->eLock!=eLock || eLock!=READ_LOCK) ){
        return SQLITE_LOCKED;
      }
    }
  }
  return SQLITE_OK;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void releasePage ( MemPage pPage) [static]

Definition at line 1521 of file btree.c.

                                       {
  if( pPage ){
    assert( pPage->aData );
    assert( pPage->pBt );
    assert( &pPage->aData[pPage->pBt->pageSize]==(unsigned char*)pPage );
    sqlite3pager_unref(pPage->aData);
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void releaseTempCursor ( BtCursor pCur) [static]

Definition at line 2885 of file btree.c.

                                             {
  if( pCur->pPage ){
    sqlite3pager_unref(pCur->pPage->aData);
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int relocatePage ( BtShared pBt,
MemPage pDbPage,
u8  eType,
Pgno  iPtrPage,
Pgno  iFreePage 
) [static]

Definition at line 2277 of file btree.c.

 {
  MemPage *pPtrPage;   /* The page that contains a pointer to pDbPage */
  Pgno iDbPage = pDbPage->pgno;
  Pager *pPager = pBt->pPager;
  int rc;

  assert( eType==PTRMAP_OVERFLOW2 || eType==PTRMAP_OVERFLOW1 || 
      eType==PTRMAP_BTREE || eType==PTRMAP_ROOTPAGE );

  /* Move page iDbPage from it's current location to page number iFreePage */
  TRACE(("AUTOVACUUM: Moving %d to free page %d (ptr page %d type %d)\n", 
      iDbPage, iFreePage, iPtrPage, eType));
  rc = sqlite3pager_movepage(pPager, pDbPage->aData, iFreePage);
  if( rc!=SQLITE_OK ){
    return rc;
  }
  pDbPage->pgno = iFreePage;

  /* If pDbPage was a btree-page, then it may have child pages and/or cells
  ** that point to overflow pages. The pointer map entries for all these
  ** pages need to be changed.
  **
  ** If pDbPage is an overflow page, then the first 4 bytes may store a
  ** pointer to a subsequent overflow page. If this is the case, then
  ** the pointer map needs to be updated for the subsequent overflow page.
  */
  if( eType==PTRMAP_BTREE || eType==PTRMAP_ROOTPAGE ){
    rc = setChildPtrmaps(pDbPage);
    if( rc!=SQLITE_OK ){
      return rc;
    }
  }else{
    Pgno nextOvfl = get4byte(pDbPage->aData);
    if( nextOvfl!=0 ){
      rc = ptrmapPut(pBt, nextOvfl, PTRMAP_OVERFLOW2, iFreePage);
      if( rc!=SQLITE_OK ){
        return rc;
      }
    }
  }

  /* Fix the database pointer on page iPtrPage that pointed at iDbPage so
  ** that it points at iFreePage. Also fix the pointer map entry for
  ** iPtrPage.
  */
  if( eType!=PTRMAP_ROOTPAGE ){
    rc = getPage(pBt, iPtrPage, &pPtrPage);
    if( rc!=SQLITE_OK ){
      return rc;
    }
    rc = sqlite3pager_write(pPtrPage->aData);
    if( rc!=SQLITE_OK ){
      releasePage(pPtrPage);
      return rc;
    }
    rc = modifyPagePointer(pPtrPage, iDbPage, iFreePage, eType);
    releasePage(pPtrPage);
    if( rc==SQLITE_OK ){
      rc = ptrmapPut(pBt, iFreePage, eType, iPtrPage);
    }
  }
  return rc;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int reparentChildPages ( MemPage pPage) [static]

Definition at line 4142 of file btree.c.

                                             {
  int i;
  BtShared *pBt = pPage->pBt;
  int rc = SQLITE_OK;

  if( pPage->leaf ) return SQLITE_OK;

  for(i=0; i<pPage->nCell; i++){
    u8 *pCell = findCell(pPage, i);
    if( !pPage->leaf ){
      rc = reparentPage(pBt, get4byte(pCell), pPage, i);
      if( rc!=SQLITE_OK ) return rc;
    }
  }
  if( !pPage->leaf ){
    rc = reparentPage(pBt, get4byte(&pPage->aData[pPage->hdrOffset+8]), 
       pPage, i);
    pPage->idxShift = 0;
  }
  return rc;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int reparentPage ( BtShared pBt,
Pgno  pgno,
MemPage pNewParent,
int  idx 
) [static]

Definition at line 4100 of file btree.c.

                                                                               {
  MemPage *pThis;
  unsigned char *aData;

  assert( pNewParent!=0 );
  if( pgno==0 ) return SQLITE_OK;
  assert( pBt->pPager!=0 );
  aData = sqlite3pager_lookup(pBt->pPager, pgno);
  if( aData ){
    pThis = (MemPage*)&aData[pBt->pageSize];
    assert( pThis->aData==aData );
    if( pThis->isInit ){
      if( pThis->pParent!=pNewParent ){
        if( pThis->pParent ) sqlite3pager_unref(pThis->pParent->aData);
        pThis->pParent = pNewParent;
        sqlite3pager_ref(pNewParent->aData);
      }
      pThis->idxParent = idx;
    }
    sqlite3pager_unref(aData);
  }

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

Here is the call graph for this function:

Here is the caller graph for this function:

static int restoreOrClearCursorPositionX ( BtCursor pCur,
int  doSeek 
) [static]

Definition at line 593 of file btree.c.

                                                                    {
  int rc = SQLITE_OK;
  assert( sqlite3ThreadDataReadOnly()->useSharedData );
  assert( pCur->eState==CURSOR_REQUIRESEEK );
  pCur->eState = CURSOR_INVALID;
  if( doSeek ){
    rc = sqlite3BtreeMoveto(pCur, pCur->pKey, pCur->nKey, &pCur->skip);
  }
  if( rc==SQLITE_OK ){
    sqliteFree(pCur->pKey);
    pCur->pKey = 0;
    assert( CURSOR_VALID==pCur->eState || CURSOR_INVALID==pCur->eState );
  }
  return rc;
}

Here is the call graph for this function:

static int saveAllCursors ( BtShared pBt,
Pgno  iRoot,
BtCursor pExcept 
) [static]

Definition at line 566 of file btree.c.

                                                                       {
  BtCursor *p;
  if( sqlite3ThreadDataReadOnly()->useSharedData ){
    for(p=pBt->pCursor; p; p=p->pNext){
      if( p!=pExcept && (0==iRoot || p->pgnoRoot==iRoot) && 
          p->eState==CURSOR_VALID ){
        int rc = saveCursorPosition(p);
        if( SQLITE_OK!=rc ){
          return rc;
        }
      }
    }
  }
  return SQLITE_OK;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int saveCursorPosition ( BtCursor pCur) [static]

Definition at line 523 of file btree.c.

                                             {
  int rc;

  assert( CURSOR_VALID==pCur->eState );
  assert( 0==pCur->pKey );

  rc = sqlite3BtreeKeySize(pCur, &pCur->nKey);

  /* If this is an intKey table, then the above call to BtreeKeySize()
  ** stores the integer key in pCur->nKey. In this case this value is
  ** all that is required. Otherwise, if pCur is not open on an intKey
  ** table, then malloc space for and store the pCur->nKey bytes of key 
  ** data.
  */
  if( rc==SQLITE_OK && 0==pCur->pPage->intKey){
    void *pKey = sqliteMalloc(pCur->nKey);
    if( pKey ){
      rc = sqlite3BtreeKey(pCur, 0, pCur->nKey, pKey);
      if( rc==SQLITE_OK ){
        pCur->pKey = pKey;
      }else{
        sqliteFree(pKey);
      }
    }else{
      rc = SQLITE_NOMEM;
    }
  }
  assert( !pCur->pPage->intKey || !pCur->pKey );

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

  return rc;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int setChildPtrmaps ( MemPage pPage) [static]

Definition at line 2174 of file btree.c.

                                          {
  int i;                             /* Counter variable */
  int nCell;                         /* Number of cells in page pPage */
  int rc = SQLITE_OK;                /* Return code */
  BtShared *pBt = pPage->pBt;
  int isInitOrig = pPage->isInit;
  Pgno pgno = pPage->pgno;

  initPage(pPage, 0);
  nCell = pPage->nCell;

  for(i=0; i<nCell; i++){
    u8 *pCell = findCell(pPage, i);

    rc = ptrmapPutOvflPtr(pPage, pCell);
    if( rc!=SQLITE_OK ){
      goto set_child_ptrmaps_out;
    }

    if( !pPage->leaf ){
      Pgno childPgno = get4byte(pCell);
      rc = ptrmapPut(pBt, childPgno, PTRMAP_BTREE, pgno);
      if( rc!=SQLITE_OK ) goto set_child_ptrmaps_out;
    }
  }

  if( !pPage->leaf ){
    Pgno childPgno = get4byte(&pPage->aData[pPage->hdrOffset+8]);
    rc = ptrmapPut(pBt, childPgno, PTRMAP_BTREE, pgno);
  }

set_child_ptrmaps_out:
  pPage->isInit = isInitOrig;
  return rc;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 2655 of file btree.c.

                                   {
  int rc;
  BtShared *pBt = p->pBt;
  if( (p->inTrans!=TRANS_WRITE) || pBt->inStmt ){
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }
  assert( pBt->inTransaction==TRANS_WRITE );
  rc = pBt->readOnly ? SQLITE_OK : sqlite3pager_stmt_begin(pBt->pPager);
  pBt->inStmt = 1;
  return rc;
}

Here is the call graph for this function:

Here is the caller graph for this function:

int sqlite3BtreeBeginTrans ( Btree p,
int  wrflag 
)

Definition at line 2106 of file btree.c.

                                                {
  BtShared *pBt = p->pBt;
  int rc = SQLITE_OK;

  btreeIntegrity(p);

  /* If the btree is already in a write-transaction, or it
  ** is already in a read-transaction and a read-transaction
  ** is requested, this is a no-op.
  */
  if( p->inTrans==TRANS_WRITE || (p->inTrans==TRANS_READ && !wrflag) ){
    return SQLITE_OK;
  }

  /* Write transactions are not possible on a read-only database */
  if( pBt->readOnly && wrflag ){
    return SQLITE_READONLY;
  }

  /* If another database handle has already opened a write transaction 
  ** on this shared-btree structure and a second write transaction is
  ** requested, return SQLITE_BUSY.
  */
  if( pBt->inTransaction==TRANS_WRITE && wrflag ){
    return SQLITE_BUSY;
  }

  do {
    if( pBt->pPage1==0 ){
      rc = lockBtree(pBt);
    }
  
    if( rc==SQLITE_OK && wrflag ){
      rc = sqlite3pager_begin(pBt->pPage1->aData, wrflag>1);
      if( rc==SQLITE_OK ){
        rc = newDatabase(pBt);
      }
    }
  
    if( rc==SQLITE_OK ){
      if( wrflag ) pBt->inStmt = 0;
    }else{
      unlockBtreeIfUnused(pBt);
    }
  }while( rc==SQLITE_BUSY && pBt->inTransaction==TRANS_NONE &&
          sqlite3InvokeBusyHandler(pBt->pBusyHandler) );

  if( rc==SQLITE_OK ){
    if( p->inTrans==TRANS_NONE ){
      pBt->nTransaction++;
    }
    p->inTrans = (wrflag?TRANS_WRITE:TRANS_READ);
    if( p->inTrans>pBt->inTransaction ){
      pBt->inTransaction = p->inTrans;
    }
  }

  btreeIntegrity(p);
  return rc;
}

Here is the call graph for this function:

Here is the caller graph for this function:

int sqlite3BtreeClearTable ( Btree p,
int  iTable 
)

Definition at line 5632 of file btree.c.

                                                {
  int rc;
  BtCursor *pCur;
  BtShared *pBt = p->pBt;
  sqlite3 *db = p->pSqlite;
  if( p->inTrans!=TRANS_WRITE ){
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }

  /* If this connection is not in read-uncommitted mode and currently has
  ** a read-cursor open on the table being cleared, return SQLITE_LOCKED.
  */
  if( 0==db || 0==(db->flags&SQLITE_ReadUncommitted) ){
    for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){
      if( pCur->pBtree==p && pCur->pgnoRoot==(Pgno)iTable ){
        if( 0==pCur->wrFlag ){
          return SQLITE_LOCKED;
        }
        moveToRoot(pCur);
      }
    }
  }

  /* Save the position of all cursors open on this table */
  if( SQLITE_OK!=(rc = saveAllCursors(pBt, iTable, 0)) ){
    return rc;
  }

  return clearDatabasePage(pBt, (Pgno)iTable, 0, 0);
}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 1715 of file btree.c.

                               {
  BtShared *pBt = p->pBt;
  BtCursor *pCur;

#ifndef SQLITE_OMIT_SHARED_CACHE
  ThreadData *pTsd;
#endif

  /* Close all cursors opened via this handle.  */
  pCur = pBt->pCursor;
  while( pCur ){
    BtCursor *pTmp = pCur;
    pCur = pCur->pNext;
    if( pTmp->pBtree==p ){
      sqlite3BtreeCloseCursor(pTmp);
    }
  }

  /* Rollback any active transaction and free the handle structure.
  ** The call to sqlite3BtreeRollback() drops any table-locks held by
  ** this handle.
  */
  sqlite3BtreeRollback(p);
  sqliteFree(p);

#ifndef SQLITE_OMIT_SHARED_CACHE
  /* If there are still other outstanding references to the shared-btree
  ** structure, return now. The remainder of this procedure cleans 
  ** up the shared-btree.
  */
  assert( pBt->nRef>0 );
  pBt->nRef--;
  if( pBt->nRef ){
    return SQLITE_OK;
  }

  /* Remove the shared-btree from the thread wide list. Call 
  ** ThreadDataReadOnly() and then cast away the const property of the 
  ** pointer to avoid allocating thread data if it is not really required.
  */
  pTsd = (ThreadData *)sqlite3ThreadDataReadOnly();
  if( pTsd->pBtree==pBt ){
    assert( pTsd==sqlite3ThreadData() );
    pTsd->pBtree = pBt->pNext;
  }else{
    BtShared *pPrev;
    for(pPrev=pTsd->pBtree; pPrev && pPrev->pNext!=pBt; pPrev=pPrev->pNext){}
    if( pPrev ){
      assert( pTsd==sqlite3ThreadData() );
      pPrev->pNext = pBt->pNext;
    }
  }
#endif

  /* Close the pager and free the shared-btree structure */
  assert( !pBt->pCursor );
  sqlite3pager_close(pBt->pPager);
  if( pBt->xFreeSchema && pBt->pSchema ){
    pBt->xFreeSchema(pBt->pSchema);
  }
  sqliteFree(pBt->pSchema);
  sqliteFree(pBt);
  return SQLITE_OK;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 2851 of file btree.c.

                                           {
  BtShared *pBt = pCur->pBtree->pBt;
  restoreOrClearCursorPosition(pCur, 0);
  if( pCur->pPrev ){
    pCur->pPrev->pNext = pCur->pNext;
  }else{
    pBt->pCursor = pCur->pNext;
  }
  if( pCur->pNext ){
    pCur->pNext->pPrev = pCur->pPrev;
  }
  releasePage(pCur->pPage);
  unlockBtreeIfUnused(pBt);
  sqliteFree(pCur);
  return SQLITE_OK;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 2492 of file btree.c.

                                {
  BtShared *pBt = p->pBt;

  btreeIntegrity(p);

  /* If the handle has a write-transaction open, commit the shared-btrees 
  ** transaction and set the shared state to TRANS_READ.
  */
  if( p->inTrans==TRANS_WRITE ){
    int rc;
    assert( pBt->inTransaction==TRANS_WRITE );
    assert( pBt->nTransaction>0 );
    rc = sqlite3pager_commit(pBt->pPager);
    if( rc!=SQLITE_OK ){
      return rc;
    }
    pBt->inTransaction = TRANS_READ;
    pBt->inStmt = 0;
  }
  unlockAllTables(p);

  /* If the handle has any kind of transaction open, decrement the transaction
  ** count of the shared btree. If the transaction count reaches 0, set
  ** the shared state to TRANS_NONE. The unlockBtreeIfUnused() call below
  ** will unlock the pager.
  */
  if( p->inTrans!=TRANS_NONE ){
    pBt->nTransaction--;
    if( 0==pBt->nTransaction ){
      pBt->inTransaction = TRANS_NONE;
    }
  }

  /* Set the handles current transaction state to TRANS_NONE and unlock
  ** the pager if this call closed the only read or write transaction.
  */
  p->inTrans = TRANS_NONE;
  unlockBtreeIfUnused(pBt);

  btreeIntegrity(p);
  return SQLITE_OK;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 2672 of file btree.c.

                                    {
  int rc;
  BtShared *pBt = p->pBt;
  if( pBt->inStmt && !pBt->readOnly ){
    rc = sqlite3pager_stmt_commit(pBt->pPager);
  }else{
    rc = SQLITE_OK;
  }
  pBt->inStmt = 0;
  return rc;
}

Here is the call graph for this function:

Here is the caller graph for this function:

int sqlite3BtreeCopyFile ( Btree pTo,
Btree pFrom 
)

Definition at line 6505 of file btree.c.

                                                  {
  int rc = SQLITE_OK;
  Pgno i, nPage, nToPage, iSkip;

  BtShared *pBtTo = pTo->pBt;
  BtShared *pBtFrom = pFrom->pBt;

  if( pTo->inTrans!=TRANS_WRITE || pFrom->inTrans!=TRANS_WRITE ){
    return SQLITE_ERROR;
  }
  if( pBtTo->pCursor ) return SQLITE_BUSY;
  nToPage = sqlite3pager_pagecount(pBtTo->pPager);
  nPage = sqlite3pager_pagecount(pBtFrom->pPager);
  iSkip = PENDING_BYTE_PAGE(pBtTo);
  for(i=1; rc==SQLITE_OK && i<=nPage; i++){
    void *pPage;
    if( i==iSkip ) continue;
    rc = sqlite3pager_get(pBtFrom->pPager, i, &pPage);
    if( rc ) break;
    rc = sqlite3pager_overwrite(pBtTo->pPager, i, pPage);
    if( rc ) break;
    sqlite3pager_unref(pPage);
  }
  for(i=nPage+1; rc==SQLITE_OK && i<=nToPage; i++){
    void *pPage;
    if( i==iSkip ) continue;
    rc = sqlite3pager_get(pBtTo->pPager, i, &pPage);
    if( rc ) break;
    rc = sqlite3pager_write(pPage);
    sqlite3pager_unref(pPage);
    sqlite3pager_dont_write(pBtTo->pPager, i);
  }
  if( !rc && nPage<nToPage ){
    rc = sqlite3pager_truncate(pBtTo->pPager, nPage);
  }
  if( rc ){
    sqlite3BtreeRollback(pTo);
  }
  return rc;  
}

Here is the call graph for this function:

Here is the caller graph for this function:

int sqlite3BtreeCreateTable ( Btree p,
int piTable,
int  flags 
)

Definition at line 5459 of file btree.c.

                                                              {
  BtShared *pBt = p->pBt;
  MemPage *pRoot;
  Pgno pgnoRoot;
  int rc;
  if( pBt->inTransaction!=TRANS_WRITE ){
    /* Must start a transaction first */
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }
  assert( !pBt->readOnly );

  /* It is illegal to create a table if any cursors are open on the
  ** database. This is because in auto-vacuum mode the backend may
  ** need to move a database page to make room for the new root-page.
  ** If an open cursor was using the page a problem would occur.
  */
  if( pBt->pCursor ){
    return SQLITE_LOCKED;
  }

#ifdef SQLITE_OMIT_AUTOVACUUM
  rc = allocatePage(pBt, &pRoot, &pgnoRoot, 1, 0);
  if( rc ) return rc;
#else
  if( pBt->autoVacuum ){
    Pgno pgnoMove;      /* Move a page here to make room for the root-page */
    MemPage *pPageMove; /* The page to move to. */

    /* Read the value of meta[3] from the database to determine where the
    ** root page of the new table should go. meta[3] is the largest root-page
    ** created so far, so the new root-page is (meta[3]+1).
    */
    rc = sqlite3BtreeGetMeta(p, 4, &pgnoRoot);
    if( rc!=SQLITE_OK ) return rc;
    pgnoRoot++;

    /* The new root-page may not be allocated on a pointer-map page, or the
    ** PENDING_BYTE page.
    */
    if( pgnoRoot==PTRMAP_PAGENO(pBt, pgnoRoot) ||
        pgnoRoot==PENDING_BYTE_PAGE(pBt) ){
      pgnoRoot++;
    }
    assert( pgnoRoot>=3 );

    /* Allocate a page. The page that currently resides at pgnoRoot will
    ** be moved to the allocated page (unless the allocated page happens
    ** to reside at pgnoRoot).
    */
    rc = allocatePage(pBt, &pPageMove, &pgnoMove, pgnoRoot, 1);
    if( rc!=SQLITE_OK ){
      return rc;
    }

    if( pgnoMove!=pgnoRoot ){
      u8 eType;
      Pgno iPtrPage;

      releasePage(pPageMove);
      rc = getPage(pBt, pgnoRoot, &pRoot);
      if( rc!=SQLITE_OK ){
        return rc;
      }
      rc = ptrmapGet(pBt, pgnoRoot, &eType, &iPtrPage);
      if( rc!=SQLITE_OK || eType==PTRMAP_ROOTPAGE || eType==PTRMAP_FREEPAGE ){
        releasePage(pRoot);
        return rc;
      }
      assert( eType!=PTRMAP_ROOTPAGE );
      assert( eType!=PTRMAP_FREEPAGE );
      rc = sqlite3pager_write(pRoot->aData);
      if( rc!=SQLITE_OK ){
        releasePage(pRoot);
        return rc;
      }
      rc = relocatePage(pBt, pRoot, eType, iPtrPage, pgnoMove);
      releasePage(pRoot);
      if( rc!=SQLITE_OK ){
        return rc;
      }
      rc = getPage(pBt, pgnoRoot, &pRoot);
      if( rc!=SQLITE_OK ){
        return rc;
      }
      rc = sqlite3pager_write(pRoot->aData);
      if( rc!=SQLITE_OK ){
        releasePage(pRoot);
        return rc;
      }
    }else{
      pRoot = pPageMove;
    } 

    /* Update the pointer-map and meta-data with the new root-page number. */
    rc = ptrmapPut(pBt, pgnoRoot, PTRMAP_ROOTPAGE, 0);
    if( rc ){
      releasePage(pRoot);
      return rc;
    }
    rc = sqlite3BtreeUpdateMeta(p, 4, pgnoRoot);
    if( rc ){
      releasePage(pRoot);
      return rc;
    }

  }else{
    rc = allocatePage(pBt, &pRoot, &pgnoRoot, 1, 0);
    if( rc ) return rc;
  }
#endif
  assert( sqlite3pager_iswriteable(pRoot->aData) );
  zeroPage(pRoot, flags | PTF_LEAF);
  sqlite3pager_unref(pRoot->aData);
  *piTable = (int)pgnoRoot;
  return SQLITE_OK;
}

Here is the call graph for this function:

Here is the caller graph for this function:

int sqlite3BtreeCursor ( Btree p,
int  iTable,
int  wrFlag,
int(*)(void *, int, const void *, int, const void *)  xCmp,
void pArg,
BtCursor **  ppCur 
)

Definition at line 2764 of file btree.c.

 {
  int rc;
  BtCursor *pCur;
  BtShared *pBt = p->pBt;

  *ppCur = 0;
  if( wrFlag ){
    if( pBt->readOnly ){
      return SQLITE_READONLY;
    }
    if( checkReadLocks(pBt, iTable, 0) ){
      return SQLITE_LOCKED;
    }
  }

  if( pBt->pPage1==0 ){
    rc = lockBtreeWithRetry(p);
    if( rc!=SQLITE_OK ){
      return rc;
    }
  }
  pCur = sqliteMalloc( sizeof(*pCur) );
  if( pCur==0 ){
    rc = SQLITE_NOMEM;
    goto create_cursor_exception;
  }
  pCur->pgnoRoot = (Pgno)iTable;
  if( iTable==1 && sqlite3pager_pagecount(pBt->pPager)==0 ){
    rc = SQLITE_EMPTY;
    goto create_cursor_exception;
  }
  rc = getAndInitPage(pBt, pCur->pgnoRoot, &pCur->pPage, 0);
  if( rc!=SQLITE_OK ){
    goto create_cursor_exception;
  }

  /* Now that no other errors can occur, finish filling in the BtCursor
  ** variables, link the cursor into the BtShared list and set *ppCur (the
  ** output argument to this function).
  */
  pCur->xCompare = xCmp ? xCmp : dfltCompare;
  pCur->pArg = pArg;
  pCur->pBtree = p;
  pCur->wrFlag = wrFlag;
  pCur->pNext = pBt->pCursor;
  if( pCur->pNext ){
    pCur->pNext->pPrev = pCur;
  }
  pBt->pCursor = pCur;
  pCur->eState = CURSOR_INVALID;
  *ppCur = pCur;

  return SQLITE_OK;
create_cursor_exception:
  if( pCur ){
    releasePage(pCur->pPage);
    sqliteFree(pCur);
  }
  unlockBtreeIfUnused(pBt);
  return rc;
}

Here is the call graph for this function:

Here is the caller graph for this function:

int sqlite3BtreeData ( BtCursor pCur,
u32  offset,
u32  amt,
void pBuf 
)

Definition at line 3078 of file btree.c.

                                                                     {
  int rc = restoreOrClearCursorPosition(pCur, 1);
  if( rc==SQLITE_OK ){
    assert( pCur->eState==CURSOR_VALID );
    assert( pCur->pPage!=0 );
    assert( pCur->idx>=0 && pCur->idx<pCur->pPage->nCell );
    rc = getPayload(pCur, offset, amt, pBuf, 1);
  }
  return rc;
}

Here is the call graph for this function:

Here is the caller graph for this function:

const void* sqlite3BtreeDataFetch ( BtCursor pCur,
int pAmt 
)

Definition at line 3162 of file btree.c.

                                                            {
  if( pCur->eState==CURSOR_VALID ){
    return (const void*)fetchPayload(pCur, pAmt, 1);
  }
  return 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

int sqlite3BtreeDataSize ( BtCursor pCur,
u32 pSize 
)

Definition at line 2940 of file btree.c.

                                                    {
  int rc = restoreOrClearCursorPosition(pCur, 1);
  if( rc==SQLITE_OK ){
    assert( pCur->eState==CURSOR_INVALID || pCur->eState==CURSOR_VALID );
    if( pCur->eState==CURSOR_INVALID ){
      /* Not pointing at a valid entry - set *pSize to 0. */
      *pSize = 0;
    }else{
      getCellInfo(pCur);
      *pSize = pCur->info.nData;
    }
  }
  return rc;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 5338 of file btree.c.

                                      {
  MemPage *pPage = pCur->pPage;
  unsigned char *pCell;
  int rc;
  Pgno pgnoChild = 0;
  BtShared *pBt = pCur->pBtree->pBt;

  assert( pPage->isInit );
  if( pBt->inTransaction!=TRANS_WRITE ){
    /* Must start a transaction before doing a delete */
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }
  assert( !pBt->readOnly );
  if( pCur->idx >= pPage->nCell ){
    return SQLITE_ERROR;  /* The cursor is not pointing to anything */
  }
  if( !pCur->wrFlag ){
    return SQLITE_PERM;   /* Did not open this cursor for writing */
  }
  if( checkReadLocks(pBt, pCur->pgnoRoot, pCur) ){
    return SQLITE_LOCKED; /* The table pCur points to has a read lock */
  }

  /* Restore the current cursor position (a no-op if the cursor is not in 
  ** CURSOR_REQUIRESEEK state) and save the positions of any other cursors 
  ** open on the same table. Then call sqlite3pager_write() on the page
  ** that the entry will be deleted from.
  */
  if( 
    (rc = restoreOrClearCursorPosition(pCur, 1))!=0 ||
    (rc = saveAllCursors(pBt, pCur->pgnoRoot, pCur))!=0 ||
    (rc = sqlite3pager_write(pPage->aData))!=0
  ){
    return rc;
  }

  /* Locate the cell within it's page and leave pCell pointing to the
  ** data. The clearCell() call frees any overflow pages associated with the
  ** cell. The cell itself is still intact.
  */
  pCell = findCell(pPage, pCur->idx);
  if( !pPage->leaf ){
    pgnoChild = get4byte(pCell);
  }
  rc = clearCell(pPage, pCell);
  if( rc ) return rc;

  if( !pPage->leaf ){
    /*
    ** The entry we are about to delete is not a leaf so if we do not
    ** do something we will leave a hole on an internal page.
    ** We have to fill the hole by moving in a cell from a leaf.  The
    ** next Cell after the one to be deleted is guaranteed to exist and
    ** to be a leaf so we can use it.
    */
    BtCursor leafCur;
    unsigned char *pNext;
    int szNext;  /* The compiler warning is wrong: szNext is always 
                 ** initialized before use.  Adding an extra initialization
                 ** to silence the compiler slows down the code. */
    int notUsed;
    unsigned char *tempCell = 0;
    assert( !pPage->leafData );
    getTempCursor(pCur, &leafCur);
    rc = sqlite3BtreeNext(&leafCur, &notUsed);
    if( rc!=SQLITE_OK ){
      if( rc!=SQLITE_NOMEM ){
        rc = SQLITE_CORRUPT_BKPT; 
      }
    }
    if( rc==SQLITE_OK ){
      rc = sqlite3pager_write(leafCur.pPage->aData);
    }
    if( rc==SQLITE_OK ){
      TRACE(("DELETE: table=%d delete internal from %d replace from leaf %d\n",
         pCur->pgnoRoot, pPage->pgno, leafCur.pPage->pgno));
      dropCell(pPage, pCur->idx, cellSizePtr(pPage, pCell));
      pNext = findCell(leafCur.pPage, leafCur.idx);
      szNext = cellSizePtr(leafCur.pPage, pNext);
      assert( MX_CELL_SIZE(pBt)>=szNext+4 );
      tempCell = sqliteMallocRaw( MX_CELL_SIZE(pBt) );
      if( tempCell==0 ){
        rc = SQLITE_NOMEM;
      }
    }
    if( rc==SQLITE_OK ){
      rc = insertCell(pPage, pCur->idx, pNext-4, szNext+4, tempCell, 0);
    }
    if( rc==SQLITE_OK ){
      put4byte(findOverflowCell(pPage, pCur->idx), pgnoChild);
      rc = balance(pPage, 0);
    }
    if( rc==SQLITE_OK ){
      dropCell(leafCur.pPage, leafCur.idx, szNext);
      rc = balance(leafCur.pPage, 0);
    }
    sqliteFree(tempCell);
    releaseTempCursor(&leafCur);
  }else{
    TRACE(("DELETE: table=%d delete from leaf %d\n",
       pCur->pgnoRoot, pPage->pgno));
    dropCell(pPage, pCur->idx, cellSizePtr(pPage, pCell));
    rc = balance(pPage, 0);
  }
  if( rc==SQLITE_OK ){
    moveToRoot(pCur);
  }
  return rc;
}

Here is the call graph for this function:

Here is the caller graph for this function:

int sqlite3BtreeDropTable ( Btree p,
int  iTable,
int piMoved 
)

Definition at line 5683 of file btree.c.

                                                             {
  int rc;
  MemPage *pPage = 0;
  BtShared *pBt = p->pBt;

  if( p->inTrans!=TRANS_WRITE ){
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }

  /* It is illegal to drop a table if any cursors are open on the
  ** database. This is because in auto-vacuum mode the backend may
  ** need to move another root-page to fill a gap left by the deleted
  ** root page. If an open cursor was using this page a problem would 
  ** occur.
  */
  if( pBt->pCursor ){
    return SQLITE_LOCKED;
  }

  rc = getPage(pBt, (Pgno)iTable, &pPage);
  if( rc ) return rc;
  rc = sqlite3BtreeClearTable(p, iTable);
  if( rc ){
    releasePage(pPage);
    return rc;
  }

  *piMoved = 0;

  if( iTable>1 ){
#ifdef SQLITE_OMIT_AUTOVACUUM
    rc = freePage(pPage);
    releasePage(pPage);
#else
    if( pBt->autoVacuum ){
      Pgno maxRootPgno;
      rc = sqlite3BtreeGetMeta(p, 4, &maxRootPgno);
      if( rc!=SQLITE_OK ){
        releasePage(pPage);
        return rc;
      }

      if( iTable==maxRootPgno ){
        /* If the table being dropped is the table with the largest root-page
        ** number in the database, put the root page on the free list. 
        */
        rc = freePage(pPage);
        releasePage(pPage);
        if( rc!=SQLITE_OK ){
          return rc;
        }
      }else{
        /* The table being dropped does not have the largest root-page
        ** number in the database. So move the page that does into the 
        ** gap left by the deleted root-page.
        */
        MemPage *pMove;
        releasePage(pPage);
        rc = getPage(pBt, maxRootPgno, &pMove);
        if( rc!=SQLITE_OK ){
          return rc;
        }
        rc = relocatePage(pBt, pMove, PTRMAP_ROOTPAGE, 0, iTable);
        releasePage(pMove);
        if( rc!=SQLITE_OK ){
          return rc;
        }
        rc = getPage(pBt, maxRootPgno, &pMove);
        if( rc!=SQLITE_OK ){
          return rc;
        }
        rc = freePage(pMove);
        releasePage(pMove);
        if( rc!=SQLITE_OK ){
          return rc;
        }
        *piMoved = maxRootPgno;
      }

      /* Set the new 'max-root-page' value in the database header. This
      ** is the old value less one, less one more if that happens to
      ** be a root-page number, less one again if that is the
      ** PENDING_BYTE_PAGE.
      */
      maxRootPgno--;
      if( maxRootPgno==PENDING_BYTE_PAGE(pBt) ){
        maxRootPgno--;
      }
      if( maxRootPgno==PTRMAP_PAGENO(pBt, maxRootPgno) ){
        maxRootPgno--;
      }
      assert( maxRootPgno!=PENDING_BYTE_PAGE(pBt) );

      rc = sqlite3BtreeUpdateMeta(p, 4, maxRootPgno);
    }else{
      rc = freePage(pPage);
      releasePage(pPage);
    }
#endif
  }else{
    /* If sqlite3BtreeDropTable was called on page 1. */
    zeroPage(pPage, PTF_INTKEY|PTF_LEAF );
    releasePage(pPage);
  }
  return rc;  
}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 3505 of file btree.c.

                                   {
  /* TODO: What if the cursor is in CURSOR_REQUIRESEEK but all table entries
  ** have been deleted? This API will need to change to return an error code
  ** as well as the boolean result value.
  */
  return (CURSOR_VALID!=pCur->eState);
}

Here is the caller graph for this function:

int sqlite3BtreeFirst ( BtCursor pCur,
int pRes 
)

Definition at line 3334 of file btree.c.

                                                {
  int rc;
  rc = moveToRoot(pCur);
  if( rc ) return rc;
  if( pCur->eState==CURSOR_INVALID ){
    assert( pCur->pPage->nCell==0 );
    *pRes = 1;
    return SQLITE_OK;
  }
  assert( pCur->pPage->nCell>0 );
  *pRes = 0;
  rc = moveToLeftmost(pCur);
  return rc;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 5858 of file btree.c.

                                     {
  /* TODO: What about CURSOR_REQUIRESEEK state? Probably need to call
  ** restoreOrClearCursorPosition() here.
  */
  MemPage *pPage = pCur->pPage;
  return pPage ? pPage->aData[pPage->hdrOffset] : 0;
}

Here is the caller graph for this function:

Definition at line 1905 of file btree.c.

                                       {
#ifdef SQLITE_OMIT_AUTOVACUUM
  return 0;
#else
  return p->pBt->autoVacuum;
#endif
}

Here is the caller graph for this function:

Definition at line 6482 of file btree.c.

                                            {
  assert( p->pBt->pPager!=0 );
  return sqlite3pager_dirname(p->pBt->pPager);
}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 6474 of file btree.c.

                                             {
  assert( p->pBt->pPager!=0 );
  return sqlite3pager_filename(p->pBt->pPager);
}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 6492 of file btree.c.