SQLite

/*
** 2001 September 15
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** $Id: btree.c,v 1.86 2003/04/01 21:16:42 paul Exp $
**
** This file implements a external (disk-based) database using BTrees.
** For a detailed discussion of BTrees, refer to
**
**     Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
**     "Sorting And Searching", pages 473-480. Addison-Wesley
**     Publishing Company, Reading, Massachusetts.

**
** The first page of the file contains a magic string used to verify that
** the file really is a valid BTree database, a pointer to a list of unused
** pages in the file, and some meta information.  The root of the first
** BTree begins on page 2 of the file.  (Pages are numbered beginning with
** 1, not 0.)  Thus a minimum database contains 2 pages.
*/
/* We don't want the btree function macros */
#define SQLITE_NO_BTREE_DEFS

#include "sqliteInt.h"
#include "pager.h"
#include "btree.h"
#include <assert.h>

/* Forward declarations */
static BtOps sqliteBtreeOps;
static BtCursorOps sqliteBtreeCursorOps;

/*
** Macros used for byteswapping.  B is a pointer to the Btree
** structure.  This is needed to access the Btree.needSwab boolean
** in order to tell if byte swapping is needed or not.
** X is an unsigned integer.  SWAB16 byte swaps a 16-bit integer.
** SWAB32 byteswaps a 32-bit integer.
*/

*/
#define EXTRA_SIZE (sizeof(MemPage)-SQLITE_PAGE_SIZE)

/*
** Everything we need to know about an open database
*/
struct Btree {
  BtOps *pOps;          /* Function table */
  Pager *pPager;        /* The page cache */
  BtCursor *pCursor;    /* A list of all open cursors */
  PageOne *page1;       /* First page of the database */
  u8 inTrans;           /* True if a transaction is in progress */
  u8 inCkpt;            /* True if there is a checkpoint on the transaction */
  u8 readOnly;          /* True if the underlying file is readonly */
  u8 needSwab;          /* Need to byte-swapping */
};
typedef Btree Bt;

/*
** A cursor is a pointer to a particular entry in the BTree.
** The entry is identified by its MemPage and the index in
** MemPage.apCell[] of the entry.
*/
struct BtCursor {
  BtCursorOps *pOps;        /* Function table */
  Btree *pBt;               /* The Btree to which this cursor belongs */
  BtCursor *pNext, *pPrev;  /* Forms a linked list of all cursors */
  BtCursor *pShared;        /* Loop of cursors with the same root page */
  Pgno pgnoRoot;            /* The root page of this tree */
  MemPage *pPage;           /* Page that contains the entry */
  int idx;                  /* Index of the entry in pPage->apCell[] */
  u8 wrFlag;                /* True if writable */
  u8 eSkip;                 /* Determines if next step operation is a no-op */
  u8 iMatch;                /* compare result from last sqliteBtreeMoveto() */
};

/*
** Legal values for BtCursor.eSkip.
*/
#define SKIP_NONE     0   /* Always step the cursor */
#define SKIP_NEXT     1   /* The next sqliteBtreeNext() is a no-op */
#define SKIP_PREV     2   /* The next sqliteBtreePrevious() is a no-op */
#define SKIP_INVALID  3   /* Calls to Next() and Previous() are invalid */

/* Forward declarations */
static int sqliteBtreeCloseCursor(BtCursor *pCur);

/*
** Routines for byte swapping.
*/
u16 swab16(u16 x){
  return ((x & 0xff)<<8) | ((x>>8)&0xff);
}
u32 swab32(u32 x){

    *ppBtree = 0;
    return rc;
  }
  sqlitepager_set_destructor(pBt->pPager, pageDestructor);
  pBt->pCursor = 0;
  pBt->page1 = 0;
  pBt->readOnly = sqlitepager_isreadonly(pBt->pPager);
  pBt->pOps = &sqliteBtreeOps;
  *ppBtree = pBt;
  return SQLITE_OK;
}

/*
** Close an open database and invalidate all cursors.
*/
static int sqliteBtreeClose(Btree *pBt){
  while( pBt->pCursor ){
    sqliteBtreeCloseCursor(pBt->pCursor);
  }
  sqlitepager_close(pBt->pPager);
  sqliteFree(pBt);
  return SQLITE_OK;
}

** and the database cannot be corrupted if this program
** crashes.  But if the operating system crashes or there is
** an abrupt power failure when synchronous is off, the database
** could be left in an inconsistent and unrecoverable state.
** Synchronous is on by default so database corruption is not
** normally a worry.
*/
static int sqliteBtreeSetCacheSize(Btree *pBt, int mxPage){
  sqlitepager_set_cachesize(pBt->pPager, mxPage);
  return SQLITE_OK;
}

/*
** Change the way data is synced to disk in order to increase or decrease
** how well the database resists damage due to OS crashes and power
** failures.  Level 1 is the same as asynchronous (no syncs() occur and
** there is a high probability of damage)  Level 2 is the default.  There
** is a very low but non-zero probability of damage.  Level 3 reduces the
** probability of damage to near zero but with a write performance reduction.
*/
static int sqliteBtreeSetSafetyLevel(Btree *pBt, int level){
  sqlitepager_set_safety_level(pBt->pPager, level);
  return SQLITE_OK;
}

/*
** Get a reference to page1 of the database file.  This will
** also acquire a readlock on that file.

**      sqliteBtreeCreateIndex()
**      sqliteBtreeClearTable()
**      sqliteBtreeDropTable()
**      sqliteBtreeInsert()
**      sqliteBtreeDelete()
**      sqliteBtreeUpdateMeta()
*/
static int sqliteBtreeBeginTrans(Btree *pBt){
  int rc;
  if( pBt->inTrans ) return SQLITE_ERROR;
  if( pBt->readOnly ) return SQLITE_READONLY;
  if( pBt->page1==0 ){
    rc = lockBtree(pBt);
    if( rc!=SQLITE_OK ){
      return rc;

/*
** Commit the transaction currently in progress.
**
** This will release the write lock on the database file.  If there
** are no active cursors, it also releases the read lock.
*/
static int sqliteBtreeCommit(Btree *pBt){
  int rc;
  rc = pBt->readOnly ? SQLITE_OK : sqlitepager_commit(pBt->pPager);
  pBt->inTrans = 0;
  pBt->inCkpt = 0;
  unlockBtreeIfUnused(pBt);
  return rc;
}

/*
** Rollback the transaction in progress.  All cursors will be
** invalided by this operation.  Any attempt to use a cursor
** that was open at the beginning of this operation will result
** in an error.
**
** This will release the write lock on the database file.  If there
** are no active cursors, it also releases the read lock.
*/
static int sqliteBtreeRollback(Btree *pBt){
  int rc;
  BtCursor *pCur;
  if( pBt->inTrans==0 ) return SQLITE_OK;
  pBt->inTrans = 0;
  pBt->inCkpt = 0;
  rc = pBt->readOnly ? SQLITE_OK : sqlitepager_rollback(pBt->pPager);
  for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){

** main transaction.  You must start a transaction before starting a
** checkpoint.  The checkpoint is ended automatically if the transaction
** commits or rolls back.
**
** Only one checkpoint may be active at a time.  It is an error to try
** to start a new checkpoint if another checkpoint is already active.
*/
static int sqliteBtreeBeginCkpt(Btree *pBt){
  int rc;
  if( !pBt->inTrans || pBt->inCkpt ){
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }
  rc = pBt->readOnly ? SQLITE_OK : sqlitepager_ckpt_begin(pBt->pPager);
  pBt->inCkpt = 1;
  return rc;
}


/*
** Commit a checkpoint to transaction currently in progress.  If no
** checkpoint is active, this is a no-op.
*/
static int sqliteBtreeCommitCkpt(Btree *pBt){
  int rc;
  if( pBt->inCkpt && !pBt->readOnly ){
    rc = sqlitepager_ckpt_commit(pBt->pPager);
  }else{
    rc = SQLITE_OK;
  }
  pBt->inCkpt = 0;
  return rc;
}

/*
** Rollback the checkpoint to the current transaction.  If there
** is no active checkpoint or transaction, this routine is a no-op.
**
** All cursors will be invalided by this operation.  Any attempt
** to use a cursor that was open at the beginning of this operation
** will result in an error.
*/
static int sqliteBtreeRollbackCkpt(Btree *pBt){
  int rc;
  BtCursor *pCur;
  if( pBt->inCkpt==0 || pBt->readOnly ) return SQLITE_OK;
  rc = sqlitepager_ckpt_rollback(pBt->pPager);
  for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){
    if( pCur->pPage && pCur->pPage->isInit==0 ){
      sqlitepager_unref(pCur->pPage);

** should be opened with wrFlag==1 even if they never really intend
** to write.
** 
** No checking is done to make sure that page iTable really is the
** root page of a b-tree.  If it is not, then the cursor acquired
** will not work correctly.
*/
static int sqliteBtreeCursor(Btree *pBt, int iTable, int wrFlag, BtCursor **ppCur){
  int rc;
  BtCursor *pCur, *pRing;

  if( pBt->page1==0 ){
    rc = lockBtree(pBt);
    if( rc!=SQLITE_OK ){
      *ppCur = 0;

  if( rc!=SQLITE_OK ){
    goto create_cursor_exception;
  }
  rc = initPage(pBt, pCur->pPage, pCur->pgnoRoot, 0);
  if( rc!=SQLITE_OK ){
    goto create_cursor_exception;
  }
  pCur->pOps = &sqliteBtreeCursorOps;
  pCur->pBt = pBt;
  pCur->wrFlag = wrFlag;
  pCur->idx = 0;
  pCur->eSkip = SKIP_INVALID;
  pCur->pNext = pBt->pCursor;
  if( pCur->pNext ){
    pCur->pNext->pPrev = pCur;

  return rc;
}

/*
** Close a cursor.  The read lock on the database file is released
** when the last cursor is closed.
*/
static int sqliteBtreeCloseCursor(BtCursor *pCur){
  Btree *pBt = pCur->pBt;
  if( pCur->pPrev ){
    pCur->pPrev->pNext = pCur->pNext;
  }else{
    pBt->pCursor = pCur->pNext;
  }
  if( pCur->pNext ){

/*
** Set *pSize to the number of bytes of key in the entry the
** cursor currently points to.  Always return SQLITE_OK.
** Failure is not possible.  If the cursor is not currently
** pointing to an entry (which can happen, for example, if
** the database is empty) then *pSize is set to 0.
*/
static int sqliteBtreeKeySize(BtCursor *pCur, int *pSize){
  Cell *pCell;
  MemPage *pPage;

  pPage = pCur->pPage;
  assert( pPage!=0 );
  if( pCur->idx >= pPage->nCell ){
    *pSize = 0;

** Change:  It used to be that the amount returned will be smaller
** than the amount requested if there are not enough bytes in the key
** to satisfy the request.  But now, it must be the case that there
** is enough data available to satisfy the request.  If not, an exception
** is raised.  The change was made in an effort to boost performance
** by eliminating unneeded tests.
*/
static int sqliteBtreeKey(BtCursor *pCur, int offset, int amt, char *zBuf){
  MemPage *pPage;

  assert( amt>=0 );
  assert( offset>=0 );
  assert( pCur->pPage!=0 );
  pPage = pCur->pPage;
  if( pCur->idx >= pPage->nCell ){

/*
** Set *pSize to the number of bytes of data in the entry the
** cursor currently points to.  Always return SQLITE_OK.
** Failure is not possible.  If the cursor is not currently
** pointing to an entry (which can happen, for example, if
** the database is empty) then *pSize is set to 0.
*/
static int sqliteBtreeDataSize(BtCursor *pCur, int *pSize){
  Cell *pCell;
  MemPage *pPage;

  pPage = pCur->pPage;
  assert( pPage!=0 );
  if( pCur->idx >= pPage->nCell ){
    *pSize = 0;

** Read part of the data associated with cursor pCur.  A maximum
** of "amt" bytes will be transfered into zBuf[].  The transfer
** begins at "offset".  The number of bytes actually read is
** returned.  The amount returned will be smaller than the
** amount requested if there are not enough bytes in the data
** to satisfy the request.
*/
static int sqliteBtreeData(BtCursor *pCur, int offset, int amt, char *zBuf){
  Cell *pCell;
  MemPage *pPage;

  assert( amt>=0 );
  assert( offset>=0 );
  assert( pCur->pPage!=0 );
  pPage = pCur->pPage;

**    *pRes>0    This means pCur>pKey
**
** When one key is an exact prefix of the other, the shorter key is
** considered less than the longer one.  In order to be equal the
** keys must be exactly the same length. (The length of the pCur key
** is the actual key length minus nIgnore bytes.)
*/
static int sqliteBtreeKeyCompare(
  BtCursor *pCur,       /* Pointer to entry to compare against */
  const void *pKey,     /* Key to compare against entry that pCur points to */
  int nKey,             /* Number of bytes in pKey */
  int nIgnore,          /* Ignore this many bytes at the end of pCur */
  int *pResult          /* Write the result here */
){
  Pgno nextPage;

  return SQLITE_OK;
}

/* Move the cursor to the first entry in the table.  Return SQLITE_OK
** on success.  Set *pRes to 0 if the cursor actually points to something
** or set *pRes to 1 if the table is empty.
*/
static int sqliteBtreeFirst(BtCursor *pCur, int *pRes){
  int rc;
  if( pCur->pPage==0 ) return SQLITE_ABORT;
  rc = moveToRoot(pCur);
  if( rc ) return rc;
  if( pCur->pPage->nCell==0 ){
    *pRes = 1;
    return SQLITE_OK;
  }
  *pRes = 0;
  rc = moveToLeftmost(pCur);
  pCur->eSkip = SKIP_NONE;
  return rc;
}

/* Move the cursor to the last entry in the table.  Return SQLITE_OK
** on success.  Set *pRes to 0 if the cursor actually points to something
** or set *pRes to 1 if the table is empty.
*/
static int sqliteBtreeLast(BtCursor *pCur, int *pRes){
  int rc;
  if( pCur->pPage==0 ) return SQLITE_ABORT;
  rc = moveToRoot(pCur);
  if( rc ) return rc;
  assert( pCur->pPage->isInit );
  if( pCur->pPage->nCell==0 ){
    *pRes = 1;

**
**     *pRes==0     The cursor is left pointing at an entry that
**                  exactly matches pKey.
**
**     *pRes>0      The cursor is left pointing at an entry that
**                  is larger than pKey.
*/
static int sqliteBtreeMoveto(BtCursor *pCur, const void *pKey, int nKey, int *pRes){
  int rc;
  if( pCur->pPage==0 ) return SQLITE_ABORT;
  pCur->eSkip = SKIP_NONE;
  rc = moveToRoot(pCur);
  if( rc ) return rc;
  for(;;){
    int lwr, upr;

/*
** Advance the cursor to the next entry in the database.  If
** successful then set *pRes=0.  If the cursor
** was already pointing to the last entry in the database before
** this routine was called, then set *pRes=1.
*/
static int sqliteBtreeNext(BtCursor *pCur, int *pRes){
  int rc;
  MemPage *pPage = pCur->pPage;
  assert( pRes!=0 );
  if( pPage==0 ){
    *pRes = 1;
    return SQLITE_ABORT;
  }

/*
** Step the cursor to the back to the previous entry in the database.  If
** successful then set *pRes=0.  If the cursor
** was already pointing to the first entry in the database before
** this routine was called, then set *pRes=1.
*/
static int sqliteBtreePrevious(BtCursor *pCur, int *pRes){
  int rc;
  Pgno pgno;
  MemPage *pPage;
  pPage = pCur->pPage;
  if( pPage==0 ){
    *pRes = 1;
    return SQLITE_ABORT;

/*
** Insert a new record into the BTree.  The key is given by (pKey,nKey)
** and the data is given by (pData,nData).  The cursor is used only to
** define what database the record should be inserted into.  The cursor
** is left pointing at the new record.
*/
static int sqliteBtreeInsert(
  BtCursor *pCur,                /* Insert data into the table of this cursor */
  const void *pKey, int nKey,    /* The key of the new record */
  const void *pData, int nData   /* The data of the new record */
){
  Cell newCell;
  int rc;
  int loc;

** sqliteBtreeNext() after a delete and the cursor will be left
** pointing to the first entry after the deleted entry.  Similarly,
** pCur->eSkip is set to SKIP_PREV is the cursor is left pointing to
** the entry prior to the deleted entry so that a subsequent call to
** sqliteBtreePrevious() will always leave the cursor pointing at the
** entry immediately before the one that was deleted.
*/
static int sqliteBtreeDelete(BtCursor *pCur){
  MemPage *pPage = pCur->pPage;
  Cell *pCell;
  int rc;
  Pgno pgnoChild;
  Btree *pBt = pCur->pBt;

  assert( pPage->isInit );

** number for the root page of the new table.
**
** In the current implementation, BTree tables and BTree indices are the 
** the same.  But in the future, we may change this so that BTree tables
** are restricted to having a 4-byte integer key and arbitrary data and
** BTree indices are restricted to having an arbitrary key and no data.
*/
static int sqliteBtreeCreateTable(Btree *pBt, int *piTable){
  MemPage *pRoot;
  Pgno pgnoRoot;
  int rc;
  if( !pBt->inTrans ){
    /* Must start a transaction first */
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }

** number for the root page of the new index.
**
** In the current implementation, BTree tables and BTree indices are the 
** the same.  But in the future, we may change this so that BTree tables
** are restricted to having a 4-byte integer key and arbitrary data and
** BTree indices are restricted to having an arbitrary key and no data.
*/
static int sqliteBtreeCreateIndex(Btree *pBt, int *piIndex){
  return sqliteBtreeCreateTable(pBt, piIndex);
}

/*
** Erase the given database page and all its children.  Return
** the page to the freelist.
*/

  sqlitepager_unref(pPage);
  return rc;
}

/*
** Delete all information from a single table in the database.
*/
static int sqliteBtreeClearTable(Btree *pBt, int iTable){
  int rc;
  BtCursor *pCur;
  if( !pBt->inTrans ){
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }
  for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){
    if( pCur->pgnoRoot==(Pgno)iTable ){

}

/*
** Erase all information in a table and add the root of the table to
** the freelist.  Except, the root of the principle table (the one on
** page 2) is never added to the freelist.
*/
static int sqliteBtreeDropTable(Btree *pBt, int iTable){
  int rc;
  MemPage *pPage;
  BtCursor *pCur;
  if( !pBt->inTrans ){
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }
  for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){

  return rc;
}
#endif

/*
** Read the meta-information out of a database file.
*/
static int sqliteBtreeGetMeta(Btree *pBt, int *aMeta){
  PageOne *pP1;
  int rc;
  int i;

  rc = sqlitepager_get(pBt->pPager, 1, (void**)&pP1);
  if( rc ) return rc;
  aMeta[0] = SWAB32(pBt, pP1->nFree);
  for(i=0; i<sizeof(pP1->aMeta)/sizeof(pP1->aMeta[0]); i++){
    aMeta[i+1] = SWAB32(pBt, pP1->aMeta[i]);
  }
  sqlitepager_unref(pP1);
  return SQLITE_OK;
}

/*
** Write meta-information back into the database.
*/
static int sqliteBtreeUpdateMeta(Btree *pBt, int *aMeta){
  PageOne *pP1;
  int rc, i;
  if( !pBt->inTrans ){
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }
  pP1 = pBt->page1;
  rc = sqlitepager_write(pP1);

******************************************************************************/

/*
** Print a disassembly of the given page on standard output.  This routine
** is used for debugging and testing only.
*/
#ifdef SQLITE_TEST
static int sqliteBtreePageDump(Btree *pBt, int pgno, int recursive){
  int rc;
  MemPage *pPage;
  int i, j;
  int nFree;
  u16 idx;
  char range[20];
  unsigned char payload[20];

**   aResult[4] =  Number of free bytes on this page
**   aResult[5] =  Number of free blocks on the page
**   aResult[6] =  Page number of the left child of this entry
**   aResult[7] =  Page number of the right child for the whole page
**
** This routine is used for testing and debugging only.
*/
static int sqliteBtreeCursorDump(BtCursor *pCur, int *aResult){
  int cnt, idx;
  MemPage *pPage = pCur->pPage;
  Btree *pBt = pCur->pBt;
  aResult[0] = sqlitepager_pagenumber(pPage);
  aResult[1] = pCur->idx;
  aResult[2] = pPage->nCell;
  if( pCur->idx>=0 && pCur->idx<pPage->nCell ){

#endif

#ifdef SQLITE_TEST
/*
** Return the pager associated with a BTree.  This routine is used for
** testing and debugging only.
*/
static Pager *sqliteBtreePager(Btree *pBt){
  return pBt->pPager;
}
#endif

/*
** This structure is passed around through all the sanity checking routines
** in order to keep track of some global state information.

  }

  /* Clean  up and report errors.
  */
  sqliteFree(sCheck.anRef);
  return sCheck.zErrMsg;
}

static BtOps sqliteBtreeOps = {
    sqliteBtreeClose,
    sqliteBtreeSetCacheSize,
    sqliteBtreeSetSafetyLevel,
    sqliteBtreeBeginTrans,
    sqliteBtreeCommit,
    sqliteBtreeRollback,
    sqliteBtreeBeginCkpt,
    sqliteBtreeCommitCkpt,
    sqliteBtreeRollbackCkpt,
    sqliteBtreeCreateTable,
    sqliteBtreeCreateIndex,
    sqliteBtreeDropTable,
    sqliteBtreeClearTable,
    sqliteBtreeCursor,
    sqliteBtreeGetMeta,
    sqliteBtreeUpdateMeta,
    sqliteBtreeIntegrityCheck,

#ifdef SQLITE_TEST
    sqliteBtreePageDump,
    sqliteBtreePager
#endif
};

static BtCursorOps sqliteBtreeCursorOps = {
    sqliteBtreeMoveto,
    sqliteBtreeDelete,
    sqliteBtreeInsert,
    sqliteBtreeFirst,
    sqliteBtreeLast,
    sqliteBtreeNext,
    sqliteBtreePrevious,
    sqliteBtreeKeySize,
    sqliteBtreeKey,
    sqliteBtreeKeyCompare,
    sqliteBtreeDataSize,
    sqliteBtreeData,
    sqliteBtreeCloseCursor,
#ifdef SQLITE_TEST
    sqliteBtreeCursorDump,
#endif
};

**    May you share freely, never taking more than you give.
**
*************************************************************************
** This header file defines the interface that the sqlite B-Tree file
** subsystem.  See comments in the source code for a detailed description
** of what each interface routine does.
**
** @(#) $Id: btree.h,v 1.29 2003/04/01 21:16:43 paul Exp $
*/
#ifndef _BTREE_H_
#define _BTREE_H_

typedef struct Btree Btree;
typedef struct BtCursor BtCursor;

struct BtOps {
    int (*sqliteBtreeClose)(Btree*);
    int (*sqliteBtreeSetCacheSize)(Btree*, int);
    int (*sqliteBtreeSetSafetyLevel)(Btree*, int);

    int (*sqliteBtreeBeginTrans)(Btree*);
    int (*sqliteBtreeCommit)(Btree*);
    int (*sqliteBtreeRollback)(Btree*);
    int (*sqliteBtreeBeginCkpt)(Btree*);
    int (*sqliteBtreeCommitCkpt)(Btree*);
    int (*sqliteBtreeRollbackCkpt)(Btree*);

    int (*sqliteBtreeCreateTable)(Btree*, int*);
    int (*sqliteBtreeCreateIndex)(Btree*, int*);
    int (*sqliteBtreeDropTable)(Btree*, int);
    int (*sqliteBtreeClearTable)(Btree*, int);

    int (*sqliteBtreeCursor)(Btree*, int iTable, int wrFlag, BtCursor **ppCur);

    int (*sqliteBtreeGetMeta)(Btree*, int*);
    int (*sqliteBtreeUpdateMeta)(Btree*, int*);

    char *(*sqliteBtreeIntegrityCheck)(Btree*, int*, int);

#ifdef SQLITE_TEST
    int (*sqliteBtreePageDump)(Btree*, int, int);
    struct Pager * (*sqliteBtreePager)(Btree*);
#endif
};

typedef struct BtOps BtOps;

struct BtCursorOps {
    int (*sqliteBtreeMoveto)(BtCursor*, const void *pKey, int nKey, int *pRes);
    int (*sqliteBtreeDelete)(BtCursor*);
    int (*sqliteBtreeInsert)(BtCursor*, const void *pKey, int nKey,
                             const void *pData, int nData);
    int (*sqliteBtreeFirst)(BtCursor*, int *pRes);
    int (*sqliteBtreeLast)(BtCursor*, int *pRes);
    int (*sqliteBtreeNext)(BtCursor*, int *pRes);
    int (*sqliteBtreePrevious)(BtCursor*, int *pRes);
    int (*sqliteBtreeKeySize)(BtCursor*, int *pSize);
    int (*sqliteBtreeKey)(BtCursor*, int offset, int amt, char *zBuf);
    int (*sqliteBtreeKeyCompare)(BtCursor*, const void *pKey, int nKey,
                                 int nIgnore, int *pRes);
    int (*sqliteBtreeDataSize)(BtCursor*, int *pSize);
    int (*sqliteBtreeData)(BtCursor*, int offset, int amt, char *zBuf);
    int (*sqliteBtreeCloseCursor)(BtCursor*);
#ifdef SQLITE_TEST
    int (*sqliteBtreeCursorDump)(BtCursor*, int*);
#endif
};
    
typedef struct BtCursorOps BtCursorOps;

#define SQLITE_N_BTREE_META 10

int sqliteBtreeOpen(const char *zFilename, int mode, int nPg, Btree **ppBtree);

#if !defined(SQLITE_NO_BTREE_DEFS)
#define btOps(pBt) (*((BtOps **)(pBt)))
#define btCOps(pCur) (*((BtCursorOps **)(pCur)))

#define sqliteBtreeClose(pBt)\
                (btOps(pBt)->sqliteBtreeClose(pBt))
#define sqliteBtreeSetCacheSize(pBt, sz)\
                (btOps(pBt)->sqliteBtreeSetCacheSize(pBt, sz))
#define sqliteBtreeSetSafetyLevel(pBt, sl)\
                (btOps(pBt)->sqliteBtreeSetSafetyLevel(pBt, sl))
#define sqliteBtreeBeginTrans(pBt)\
                (btOps(pBt)->sqliteBtreeBeginTrans(pBt))
#define sqliteBtreeCommit(pBt)\
                (btOps(pBt)->sqliteBtreeCommit(pBt))
#define sqliteBtreeRollback(pBt)\
                (btOps(pBt)->sqliteBtreeRollback(pBt))
#define sqliteBtreeBeginCkpt(pBt)\
                (btOps(pBt)->sqliteBtreeBeginCkpt(pBt))
#define sqliteBtreeCommitCkpt(pBt)\
                (btOps(pBt)->sqliteBtreeCommitCkpt(pBt))
#define sqliteBtreeRollbackCkpt(pBt)\
                (btOps(pBt)->sqliteBtreeRollbackCkpt(pBt))
#define sqliteBtreeCreateTable(pBt, piTable)\
                (btOps(pBt)->sqliteBtreeCreateTable(pBt, piTable))
#define sqliteBtreeCreateIndex(pBt, piIndex)\
                (btOps(pBt)->sqliteBtreeCreateIndex(pBt, piIndex))
#define sqliteBtreeDropTable(pBt, iTable)\
                (btOps(pBt)->sqliteBtreeDropTable(pBt, iTable))
#define sqliteBtreeClearTable(pBt, iTable)\
                (btOps(pBt)->sqliteBtreeClearTable(pBt, iTable))
#define sqliteBtreeCursor(pBt, iTable, wrFlag, ppCur)\
                (btOps(pBt)->sqliteBtreeCursor(pBt, iTable, wrFlag, ppCur))
#define sqliteBtreeMoveto(pCur, pKey, nKey, pRes)\
                (btCOps(pCur)->sqliteBtreeMoveto(pCur, pKey, nKey, pRes))
#define sqliteBtreeDelete(pCur)\
                (btCOps(pCur)->sqliteBtreeDelete(pCur))
#define sqliteBtreeInsert(pCur, pKey, nKey, pData, nData) \
                (btCOps(pCur)->sqliteBtreeInsert(pCur, pKey, nKey, pData, nData))
#define sqliteBtreeFirst(pCur, pRes)\
                (btCOps(pCur)->sqliteBtreeFirst(pCur, pRes))
#define sqliteBtreeLast(pCur, pRes)\
                (btCOps(pCur)->sqliteBtreeLast(pCur, pRes))
#define sqliteBtreeNext(pCur, pRes)\
                (btCOps(pCur)->sqliteBtreeNext(pCur, pRes))
#define sqliteBtreePrevious(pCur, pRes)\
                (btCOps(pCur)->sqliteBtreePrevious(pCur, pRes))
#define sqliteBtreeKeySize(pCur, pSize)\
                (btCOps(pCur)->sqliteBtreeKeySize(pCur, pSize) )
#define sqliteBtreeKey(pCur, offset, amt, zBuf)\
                (btCOps(pCur)->sqliteBtreeKey(pCur, offset, amt, zBuf))
#define sqliteBtreeKeyCompare(pCur, pKey, nKey, nIgnore, pRes)\
                (btCOps(pCur)->sqliteBtreeKeyCompare(pCur, pKey, nKey, nIgnore, pRes))
#define sqliteBtreeDataSize(pCur, pSize)\
                (btCOps(pCur)->sqliteBtreeDataSize(pCur, pSize))
#define sqliteBtreeData(pCur, offset, amt, zBuf)\
                (btCOps(pCur)->sqliteBtreeData(pCur, offset, amt, zBuf))
#define sqliteBtreeCloseCursor(pCur)\
                (btCOps(pCur)->sqliteBtreeCloseCursor(pCur))
#define sqliteBtreeGetMeta(pBt, aMeta)\
                (btOps(pBt)->sqliteBtreeGetMeta(pBt, aMeta))
#define sqliteBtreeUpdateMeta(pBt, aMeta)\
                (btOps(pBt)->sqliteBtreeUpdateMeta(pBt, aMeta))
#define sqliteBtreeIntegrityCheck(pBt, aRoot, nRoot)\
                (btOps(pBt)->sqliteBtreeIntegrityCheck(pBt, aRoot, nRoot))
#endif

#ifdef SQLITE_TEST
#if !defined(SQLITE_NO_BTREE_DEFS)
#define sqliteBtreePageDump(pBt, pgno, recursive)\
                (btOps(pBt)->sqliteBtreePageDump(pBt, pgno, recursive))
#define sqliteBtreeCursorDump(pCur, aResult)\
                (btCOps(pCur)->sqliteBtreeCursorDump(pCur, aResult))
#define sqliteBtreePager(pBt)\
                (btOps(pBt)->sqliteBtreePager(pBt))
#endif

int btree_native_byte_order;
#endif

#endif /* _BTREE_H_ */