random.o resolve.o rowset.o rtree.o select.o status.o \
         tokenize.o trigger.o \
         update.o util.o varint.o \
         vdbeapi.o vdbeaux.o vdbecodec.o vdbecursor.o \
         vdbemem.o vdbetrace.o \
         walker.o where.o utf.o

LIBOBJ += bt_unix.o bt_pager.o bt_main.o 

# All of the source code files.
#
SRC = \
  $(TOP)/src/alter.c \
  $(TOP)/src/analyze.c \
  $(TOP)/src/attach.c \

         random.o resolve.o rowset.o rtree.o select.o status.o \
         tokenize.o trigger.o \
         update.o util.o varint.o \
         vdbeapi.o vdbeaux.o vdbecodec.o vdbecursor.o \
         vdbemem.o vdbetrace.o \
         walker.o where.o utf.o

LIBOBJ += bt_unix.o bt_pager.o bt_main.o bt_varint.o kvbt.o

# All of the source code files.
#
SRC = \
  $(TOP)/src/alter.c \
  $(TOP)/src/analyze.c \
  $(TOP)/src/attach.c \

**   SQLITE4_OK:
**   SQLITE4_NOTFOUND:
**   SQLITE4_INEXACT:
**   other:
*/
int sqlite4BtCsrSeek(bt_cursor *pCsr, const void *pK, int nK, int eSeek);




int sqlite4BtCsrFirst(bt_cursor *pCsr);
int sqlite4BtCsrLast(bt_cursor *pCsr);

int sqlite4BtCsrNext(bt_cursor *pCsr);
int sqlite4BtCsrPrev(bt_cursor *pCsr);

int sqlite4BtCsrValid(bt_cursor *pCsr);

**   SQLITE4_OK:
**   SQLITE4_NOTFOUND:
**   SQLITE4_INEXACT:
**   other:
*/
int sqlite4BtCsrSeek(bt_cursor *pCsr, const void *pK, int nK, int eSeek);

/*
** TODO: Are these actually even required for SQLite4 KV stores?
*/
int sqlite4BtCsrFirst(bt_cursor *pCsr);
int sqlite4BtCsrLast(bt_cursor *pCsr);

int sqlite4BtCsrNext(bt_cursor *pCsr);
int sqlite4BtCsrPrev(bt_cursor *pCsr);

int sqlite4BtCsrValid(bt_cursor *pCsr);

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

#include "bt.h"

typedef sqlite4_int64 i64;

typedef unsigned int u32;

typedef unsigned char u8;

/*************************************************************************
** Interface to bt_pager.c functionality.
*/
typedef struct BtPage BtPage;
typedef struct BtPager BtPager;
................................................................................
int sqlite4BtPagerRevert(BtPager*, int iLevel);
int sqlite4BtPagerRollback(BtPager*, int iLevel);
int sqlite4BtPagerTransactionLevel(BtPager*);

/*
** Query for the database page size. Requires an open read transaction.
*/
int sqlite4BtPagerPagesize(BtPager*, int *pnByte);

/* 
** Query for the root page number. Requires an open read transaction.
*/
int sqlite4BtPagerRootpgno(BtPager*, u32 *piRoot);

/*
** Read, write and trim existing database pages.
*/
int sqlite4BtPageGet(BtPager*, u32 pgno, BtPage **ppPage);
int sqlite4BtPageWrite(BtPage*);
int sqlite4BtPageTrim(BtPage*);
................................................................................
/* Find the default VFS */
bt_env *sqlite4BtEnvDefault(void);

/*
** End of file system interface.
*************************************************************************/

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

#include "bt.h"

typedef sqlite4_int64 i64;
typedef sqlite4_uint64 u64;
typedef unsigned int u32;
typedef unsigned short u16;
typedef unsigned char u8;

/*************************************************************************
** Interface to bt_pager.c functionality.
*/
typedef struct BtPage BtPage;
typedef struct BtPager BtPager;
................................................................................
int sqlite4BtPagerRevert(BtPager*, int iLevel);
int sqlite4BtPagerRollback(BtPager*, int iLevel);
int sqlite4BtPagerTransactionLevel(BtPager*);

/*
** Query for the database page size. Requires an open read transaction.
*/
int sqlite4BtPagerPagesize(BtPager*);

/* 
** Query for the root page number. Requires an open read transaction.
*/
u32 sqlite4BtPagerRootpgno(BtPager*);

/*
** Read, write and trim existing database pages.
*/
int sqlite4BtPageGet(BtPager*, u32 pgno, BtPage **ppPage);
int sqlite4BtPageWrite(BtPage*);
int sqlite4BtPageTrim(BtPage*);
................................................................................
/* Find the default VFS */
bt_env *sqlite4BtEnvDefault(void);

/*
** End of file system interface.
*************************************************************************/

/*************************************************************************
** Interface to bt_varint.c functionality.
**
** All this is just copied from SQLite4 proper. It is a bit ridiculous.
*/
int sqlite4BtVarintPut32(u8 *, int);
int sqlite4BtVarintGet32(u8 *, int *);
int sqlite4BtVarintPut64(u8 *aData, i64 iVal);
int sqlite4BtVarintGet64(const u8 *aData, i64 *piVal);
int sqlite4BtVarintLen32(int);
int sqlite4BtVarintSize(u8 c);
/*
** End of bt_varint.c interface.
*************************************************************************/

#ifdef NDEBUG
# define btErrorBkpt(x) x
#else
int btErrorBkpt(int rc);
#endif

**    May you share freely, never taking more than you give.
**
*************************************************************************
**
*/

#include "btInt.h"











struct bt_db {
  sqlite4_env *pEnv;              /* SQLite environment */
  BtPager *pPager;                /* Underlying page-based database */
};

struct bt_cursor {
  bt_db *pDb;                     /* Database that owns this cursor */

  int nPg;                        /* Number of valid entries in apPage[] */
  int iCell;                      /* Current cell in apPage[nPg] */
  BtPage *apPage[32];             /* All pages from root to current leaf */
};

























/*
** Allocate a new database handle.
*/
int sqlite4BtNew(sqlite4_env *pEnv, int nExtra, bt_db **ppDb){
  bt_db *db = 0;                  /* New database object */
  BtPager *pPager = 0;            /* Pager object for this database */
................................................................................
  rc = sqlite4BtPagerRollback(db->pPager, iLevel);
  return rc;
}

int sqlite4BtTransactionLevel(bt_db *db){
  return sqlite4BtPagerTransactionLevel(db->pPager);
}






int sqlite4BtCsrOpen(bt_db *db, int nExtra, bt_cursor **ppCsr){
  int rc;                         /* Return Code */
  int nByte;                      /* Total bytes of space to allocate */
  bt_cursor *pCsr;                /* New cursor object */

  nByte = sizeof(bt_cursor) + nExtra;
  pCsr = (bt_cursor*)sqlite4_malloc(db->pEnv, nByte);
  if( pCsr==0 ){
    rc = SQLITE4_NOMEM;
  }else{
    memset(pCsr, 0, nByte);
    pCsr->pDb = db;
  }

  return rc;
}

int sqlite4BtCsrClose(bt_cursor *pCsr){
  return SQLITE4_OK;
}

void *sqlite4BtCsrExtra(bt_cursor *pCsr){
  return (void*)&pCsr[1];
}

int sqlite4BtCsrSeek(bt_cursor *pCsr, const void *pK, int nK, int eSeek){
  return SQLITE4_OK;
}

static void btCsrReset(bt_cursor *pCsr){
  int i;
  for(i=0; i<pCsr->nPg; i++){
    sqlite4BtPageRelease(pCsr->apPage[i]);
  }
  pCsr->nPg = 0;














  pCsr->iCell = 0;
}





















/*
** Position cursor pCsr to point to the smallest key in the database.


*/


























































































int sqlite4BtCsrFirst(bt_cursor *pCsr){








  /* Reset the cursor */
  btCsrReset(pCsr);

  /* Load the root page into pCsr->apPage[0] */







  return SQLITE4_OK;






















































}

/*
** Position cursor pCsr to point to the largest key in the database.
*/
int sqlite4BtCsrLast(bt_cursor *pCsr){
  return SQLITE4_OK;
}




int sqlite4BtCsrNext(bt_cursor *pCsr){

  return SQLITE4_OK;
}

int sqlite4BtCsrPrev(bt_cursor *pCsr){

  return SQLITE4_OK;
}

int sqlite4BtCsrValid(bt_cursor *pCsr){

  return 0;
}

int sqlite4BtCsrKey(bt_cursor *pCsr, const void **ppK, int *pnK){





  return SQLITE4_OK;
}

int sqlite4BtCsrData(
  bt_cursor *pCsr,                /* Cursor handle */
  int iOffset,                    /* Offset of requested data */
  int nByte,                      /* Bytes requested (or -ve for all avail.) */
  const void **ppV,               /* OUT: Pointer to data buffer */
  int *pnV                        /* OUT: Size of data buffer in bytes */
){

  return SQLITE4_OK;
}

































































int sqlite4BtReplace(bt_db *db, const void *pK, int nK, const void *pV, int nV){
  return SQLITE4_OK;

}





















int sqlite4BtDelete(bt_cursor *pCsr){

  return SQLITE4_OK;
}

int sqlite4BtSetCookie(bt_db *db, unsigned int iVal){
  return sqlite4BtPagerSetCookie(db->pPager, iVal);
}

int sqlite4BtGetCookie(bt_db *db, unsigned int *piVal){
  return sqlite4BtPagerGetCookie(db->pPager, piVal);
}

**    May you share freely, never taking more than you give.
**
*************************************************************************
**
*/

#include "btInt.h"
#include <string.h>
#include <assert.h>

#define BT_MAX_DEPTH 32           /* Maximum possible depth of tree */

/*
** Values that make up the single byte flags field at the start of
** b-tree pages. 
*/
#define BT_PGFLAGS_INTERNAL 0x01  /* True for non-leaf nodes */

struct bt_db {
  sqlite4_env *pEnv;              /* SQLite environment */
  BtPager *pPager;                /* Underlying page-based database */
};

struct bt_cursor {
  bt_db *pDb;                     /* Database that owns this cursor */

  int nPg;                        /* Number of valid entries in apPage[] */
  int aiCell[BT_MAX_DEPTH];       /* Current cell of each apPage[] entry */
  BtPage *apPage[BT_MAX_DEPTH];   /* All pages from root to current leaf */
};

#ifndef btErrorBkpt
int btErrorBkpt(int rc){
  static int error_cnt = 0;
  error_cnt++;
  return rc;
}
#endif

/*
** Interpret the first 4 bytes of the buffer indicated by the first parameter
** as a 32-bit unsigned big-endian integer.
*/
static u32 btGetU32(const u8 *a){
  return ((u32)a[0] << 24) + ((u32)a[1] << 16) + ((u32)a[2] << 8) + ((u32)a[3]);
}
static u16 btGetU16(const u8 *a){
  return ((u32)a[0] << 8) + (u32)a[1];
}

static void btPutU16(u8 *a, u16 i){
  a[0] = (u8)((i>>8) & 0xFF);
  a[1] = (u8)((i>>0) & 0xFF);
}

/*
** Allocate a new database handle.
*/
int sqlite4BtNew(sqlite4_env *pEnv, int nExtra, bt_db **ppDb){
  bt_db *db = 0;                  /* New database object */
  BtPager *pPager = 0;            /* Pager object for this database */
................................................................................
  rc = sqlite4BtPagerRollback(db->pPager, iLevel);
  return rc;
}

int sqlite4BtTransactionLevel(bt_db *db){
  return sqlite4BtPagerTransactionLevel(db->pPager);
}

static void btCsrSetup(bt_db *db, bt_cursor *pCsr){
  memset(pCsr, 0, sizeof(bt_cursor));
  pCsr->pDb = db;
}

int sqlite4BtCsrOpen(bt_db *db, int nExtra, bt_cursor **ppCsr){
  int rc;                         /* Return Code */
  int nByte;                      /* Total bytes of space to allocate */
  bt_cursor *pCsr;                /* New cursor object */

  nByte = sizeof(bt_cursor) + nExtra;
  *ppCsr = pCsr = (bt_cursor*)sqlite4_malloc(db->pEnv, nByte);
  if( pCsr==0 ){
    rc = btErrorBkpt(SQLITE4_NOMEM);
  }else{
    btCsrSetup(db, pCsr);

  }

  return rc;
}

int sqlite4BtCsrClose(bt_cursor *pCsr){
  return SQLITE4_OK;
}

void *sqlite4BtCsrExtra(bt_cursor *pCsr){
  return (void*)&pCsr[1];
}





static void btCsrReset(bt_cursor *pCsr){
  int i;
  for(i=0; i<pCsr->nPg; i++){
    sqlite4BtPageRelease(pCsr->apPage[i]);
  }
  pCsr->nPg = 0;
}

/*
** Set pCsr->apPage[pCsr->nPg] to a reference to database page pgno.
*/
static int btCsrDescend(bt_cursor *pCsr, u32 pgno){
  int rc;
  if( pCsr->nPg>=BT_MAX_DEPTH ){
    rc = btErrorBkpt(SQLITE4_CORRUPT);
  }else{
    rc = sqlite4BtPageGet(pCsr->pDb->pPager, pgno, &pCsr->apPage[pCsr->nPg]);
    if( pCsr->nPg==0 && rc==SQLITE4_OK ){
    }
    if( rc==SQLITE4_OK ){
      pCsr->nPg++;
    }
  }
  return rc;
}

static int btCellCount(const u8 *aData, int nData){
  return (int)btGetU16(&aData[nData-2]);
}

static int btFreeOffset(const u8 *aData, int nData){
  return (int)btGetU16(&aData[nData-4]);
}

static u8 btFlags(const u8 *aData, int nData){
  return aData[0];
}

static u8 *btCellFind(u8 *aData, int nData, int iCell){
  int iOff = btGetU16(&aData[nData - 4 - iCell*2 - 2]);
  return &aData[iOff];
}

/*

** Return a pointer to the big-endian u16 field that contains the 
** pointer to cell iCell.
*/
static u8* btCellPtrFind(u8 *aData, int nData, int iCell){
  return &aData[nData - 4 - iCell*2 - 2];
}


/*
** This function seeks the cursor as required for either sqlite4BtCsrFirst()
** (if parameter bLast is false) or sqlite4BtCsrLast() (if bLast is true).
*/
static int btCsrEnd(bt_cursor *pCsr, int bLast){
  const int pgsz = sqlite4BtPagerPagesize(pCsr->pDb->pPager);
  int rc;                         /* Return Code */
  u32 pgno;                       /* Page number for next page to load */

  /* Reset the cursor */
  btCsrReset(pCsr);

  /* Figure out the root page number */
  assert( pCsr->nPg==0 );
  pgno = sqlite4BtPagerRootpgno(pCsr->pDb->pPager);

  while( rc==SQLITE4_OK ){
    /* Load page number pgno into the b-tree */
    rc = btCsrDescend(pCsr, pgno);
    if( rc==SQLITE4_OK ){
      int nByte;
      u8 *pCell;
      u8 *aData = (u8*)sqlite4BtPageData(pCsr->apPage[pCsr->nPg-1]);

      /* If the cursor has descended to a leaf break out of the loop. */
      pCsr->aiCell[pCsr->nPg-1] = (bLast ? btCellCount(aData, pgsz) : 0);
      if( (aData[0] & BT_PGFLAGS_INTERNAL)==0 ) break;
      
      /* Otherwise, set pgno to the left or rightmost child of the page
      ** just loaded, depending on whether the cursor is seeking to the
      ** start or end of the tree.  */
      if( bLast==0 ){
        pCell = btCellFind(aData, pgsz, 0);
        pCell += sqlite4BtVarintGet32(pCell, &nByte);
        pCell += nByte;
        sqlite4BtVarintGet32(pCell, (int *)&pgno);
      }else{
        pgno = btGetU32(&aData[1]);
      }
    }
  }
  return rc;
}

/*
** This function compares the key passed via parameters pK and nK to the
** key stored as part of cell iCell on the database page stored in buffer
** aData (size nData bytes).
**
** If the cell key is C, and the user key K, then this function sets:
**
**     *piRes = (C - K).
**
** In other workds, *piRes is +ve, zero or -ve if C is respectively larger, 
** equal to or smaller than K.
*/
static int btCellKeyCompare(
  bt_cursor *pCsr,                /* Cursor handle */
  const u8 *aData, int nData,     /* Page data (nData is the page size) */
  int iCell,                      /* Cell to compare key from */
  const u8 *pK, int nK,           /* Key to compare to cell key */
  int *piRes                      /* OUT: Result of comparison */
){
  int rc = SQLITE4_OK;
  u8 *pCell = btCellFind((u8*)aData, nData, iCell);
  int nCellKey;                   /* Number of bytes in cell key */
  int res;

  pCell += sqlite4BtVarintGet32(pCell, &nCellKey);
  if( nCellKey==0 ){
    /* Type (c) cell */
    assert( 0 );
  }else{
    int nCmp = ((nCellKey <= nK) ? nCellKey : nK);
    res = memcmp(pCell, pK, nCmp);
    if( res==0 ){
      res = nCellKey - nK;
    }
  }

  *piRes = res;
  return rc;
}

int sqlite4BtCsrSeek(
  bt_cursor *pCsr, 
  const void *pK,                 /* Key to seek for */
  int nK,                         /* Size of key pK in bytes */
  int eSeek                       /* Seek mode (a BT_SEEK_XXX constant) */
){
  const int pgsz = sqlite4BtPagerPagesize(pCsr->pDb->pPager);
  u32 pgno;                       /* Page number for next page to load */
  int rc = SQLITE4_OK;            /* Return Code */

  /* Reset the cursor */
  btCsrReset(pCsr);


  /* Figure out the root page number */
  assert( pCsr->nPg==0 );
  pgno = sqlite4BtPagerRootpgno(pCsr->pDb->pPager);

  while( rc==SQLITE4_OK && pgno ){
    /* Load page number pgno into the b-tree */
    rc = btCsrDescend(pCsr, pgno);
    if( rc==SQLITE4_OK ){
      int nCell;                  /* Number of cells on this page */
      int iHi;                    /* pK/nK is <= than cell iHi */
      int iLo;                    /* pK/nK is > than cell (iLo-1) */
      int res;                    /* Result of comparison */
      u8 *aData = (u8*)sqlite4BtPageData(pCsr->apPage[pCsr->nPg-1]);

      iLo = 0;
      iHi = nCell = btCellCount(aData, pgsz);

      while( iHi>iLo ){
        int iTst = (iHi+iLo)/2;   /* Cell to compare to pK/nK */
        rc = btCellKeyCompare(pCsr, aData, pgsz, iTst, pK, nK, &res);
        if( rc!=SQLITE4_OK || res==0 ){
          /* Cell iTst is EQUAL to pK/nK */
          iHi = iLo = iTst;
        }else if( res<0 ){
          /* Cell iTst is SMALLER than pK/nK */
          iLo = iTst+1;
        }else{
          /* Cell iTst is LARGER than pK/nK */
          iHi = iTst;
        }
      }
      assert( rc!=SQLITE4_OK || iHi==iLo );
      pCsr->aiCell[pCsr->nPg-1] = iHi;

      if( aData[0] & BT_PGFLAGS_INTERNAL ){
        if( iHi==nCell ){
          pgno = btGetU32(&aData[1]);
        }else{
          u8 *pCell;
          int nByte;
          pCell = btCellFind(aData, pgsz, 0);
          pCell += sqlite4BtVarintGet32(pCell, &nByte);
          pCell += nByte;
          sqlite4BtVarintGet32(pCell, (int*)&pgno);
        }
      }else{
        pgno = 0;
        if( res!=0 ){
          rc = SQLITE4_INEXACT;
        }
      }
    }
  }

  return rc;
}

/*
** Position cursor pCsr to point to the smallest key in the database.
*/
int sqlite4BtCsrFirst(bt_cursor *pCsr){
  return btCsrEnd(pCsr, 0);
}

/*
** Position cursor pCsr to point to the largest key in the database.
*/
int sqlite4BtCsrLast(bt_cursor *pCsr){
  return btCsrEnd(pCsr, 1);
}

/*
** Advance to the next entry in the tree.
*/
int sqlite4BtCsrNext(bt_cursor *pCsr){
  assert( 0 );
  return SQLITE4_OK;
}

int sqlite4BtCsrPrev(bt_cursor *pCsr){
  assert( 0 );
  return SQLITE4_OK;
}

int sqlite4BtCsrValid(bt_cursor *pCsr){
  assert( 0 );
  return 0;
}

int sqlite4BtCsrKey(bt_cursor *pCsr, const void **ppK, int *pnK){
  const int pgsz = sqlite4BtPagerPagesize(pCsr->pDb->pPager);
  u8 *aData;
  
  aData = (u8*)sqlite4BtPageData(pCsr->apPage[pCsr->nPg-1]);

  return SQLITE4_OK;
}

int sqlite4BtCsrData(
  bt_cursor *pCsr,                /* Cursor handle */
  int iOffset,                    /* Offset of requested data */
  int nByte,                      /* Bytes requested (or -ve for all avail.) */
  const void **ppV,               /* OUT: Pointer to data buffer */
  int *pnV                        /* OUT: Size of data buffer in bytes */
){
  assert( 0 );
  return SQLITE4_OK;
}

static int btInsertIntoLeaf(
  bt_cursor *pCsr, 
  const void *pK, int nK, 
  const void *pV, int nV
){
  int rc = SQLITE4_OK;
  const int pgsz = sqlite4BtPagerPagesize(pCsr->pDb->pPager);
  u8 *aData;                      /* Page buffer */
  int nCell;                      /* Number of cells on this page already */
  int nFree;                      /* Free space on this page in bytes */
  int nReq;                       /* Space required for type (a) cell */
  int iCell;                      /* Position to insert new key */
  int iWrite;                     /* Byte offset at which to write new cell */
  BtPage *pLeaf;

  nReq = sqlite4BtVarintLen32(nK) + nK + sqlite4BtVarintLen32(nV) + nV + 2;

  iCell = pCsr->aiCell[pCsr->nPg-1];
  assert( pCsr->nPg>0 );
  pLeaf = pCsr->apPage[pCsr->nPg-1];
  aData = (u8*)sqlite4BtPageData(pLeaf);

  nCell = btCellCount(aData, pgsz);
  assert( iCell<=btCellCount(aData, pgsz) );

  if( nCell==0 ){
    iWrite = 1;                   /* Right after "flags" byte */
    nFree = pgsz - 1 - 4;         /* Page is free aside from header & footer */
  }else{
    iWrite = btFreeOffset(aData, pgsz);
    nFree = pgsz - btFreeOffset(aData, pgsz) - (2+nCell) * 2;
  }
  if( nFree>=nReq ){
    rc = sqlite4BtPageWrite(pLeaf);
    if( rc==SQLITE4_OK ){
      aData = sqlite4BtPageData(pLeaf);

      /* Increase cell count */
      btPutU16(&aData[pgsz-2], nCell+1);

      /* Update the cell pointer array */
      if( iCell!=nCell ){
        u8 *aFrom = &aData[pgsz-4-iCell*2];
        memmove(aFrom, &aFrom[-2], (nCell-iCell) * 2);
      }
      btPutU16(btCellPtrFind(aData, pgsz, iCell), iWrite);
      
      /* Write the cell itself */
      iWrite += sqlite4BtVarintPut32(&aData[iWrite], nK);
      iWrite += nK;
      iWrite += sqlite4BtVarintPut32(&aData[iWrite], nV);
      iWrite += nV;
      btPutU16(&aData[pgsz-4], iWrite);
    }
  }else{
    assert( 0 );
  }

  return rc;
}

/*
** Insert a new key/value pair or replace an existing one.
*/
int sqlite4BtReplace(bt_db *db, const void *pK, int nK, const void *pV, int nV){
  int rc = SQLITE4_OK;
  bt_cursor csr;

  btCsrSetup(db, &csr);
  rc = sqlite4BtCsrSeek(&csr, pK, nK, BT_SEEK_GE);
  if( rc==SQLITE4_OK ){
    /* The cursor currently points to an entry with key pK/nK. This call
    ** should therefore replace that entry. So delete it and then re-seek
    ** the cursor.  */
    rc = sqlite4BtDelete(&csr);
    if( rc==SQLITE4_OK ){
      rc = sqlite4BtCsrSeek(&csr, pK, nK, BT_SEEK_GE);
    }
  }
  if( rc==SQLITE4_OK ) rc = btErrorBkpt(SQLITE4_CORRUPT);

  if( rc==SQLITE4_NOTFOUND || rc==SQLITE4_INEXACT ){
    /* Insert the new KV pair into the current leaf. */
    rc = btInsertIntoLeaf(&csr, pK, nK, pV, nV);
  }

  return rc;
}

int sqlite4BtDelete(bt_cursor *pCsr){
  assert( 0 );
  return SQLITE4_OK;
}

int sqlite4BtSetCookie(bt_db *db, unsigned int iVal){
  return sqlite4BtPagerSetCookie(db->pPager, iVal);
}

int sqlite4BtGetCookie(bt_db *db, unsigned int *piVal){
  return sqlite4BtPagerGetCookie(db->pPager, piVal);
}

#ifndef NDEBUG
static void printPage(u8 *aData, int nData){
  printf("nCell=%d\n", (int)btCellCount(aData, nData));
  printf("iFree=%d\n", (int)btFreeOffset(aData, nData));
  printf("flags=%d\n", (int)btFlags(aData, nData));
}
#endif

  if( p->hash.nEntry>=p->hash.nHash/2 ){
    int i;
    int nNew = (p->hash.nHash ? p->hash.nHash*2 : 256);
    BtPage **aNew;
    BtPage **aOld = p->hash.aHash;

    aNew = (BtPage **)sqlite4_malloc(p->pEnv, nNew*sizeof(BtPage*));
    if( aNew==0 ) return SQLITE4_NOMEM;
    memset(aNew, 0, nNew*sizeof(BtPage*));
    for(i=0; i<p->hash.nHash; i++){
      while( aOld[i] ){
        BtPage *pShift = aOld[i];
        aOld[i] = pShift->pNextHash;
        h = hashkey(nNew, pPg->pgno);
        pShift->pNextHash = aNew[h];
................................................................................
}

/*
** Search the hash table for a page with page number pgno. If found, return
** a pointer to the BtPage object. Otherwise, return NULL.
*/
static BtPage *btHashSearch(BtPager *p, u32 pgno){


  int h = hashkey(p->hash.nHash, pgno);
  BtPage *pRet;
  for(pRet=p->hash.aHash[h]; pRet && pRet->pgno!=pgno; pRet=pRet->pNextHash);

  return pRet;
}

/*
** Remove all entries from the hash-table. And free any allocations made
** by earlier calls to btHashAdd().
*/
................................................................................
*/
int sqlite4BtPagerNew(sqlite4_env *pEnv, int nExtra, BtPager **pp){
  BtPager *p;
  int nByte;

  nByte = sizeof(BtPager) + nExtra;
  p = (BtPager*)sqlite4_malloc(pEnv, nByte);
  if( !p ) return SQLITE4_NOMEM; 
  memset(p, 0, nByte);

  p->pEnv = pEnv;
  p->pVfs = sqlite4BtEnvDefault();
  *pp = p;
  return SQLITE4_OK;
}
................................................................................
  if( rc==SQLITE4_OK && nByte>0 ){
    rc = p->pVfs->xRead(p->pFd, 0, &p->dbhdr, sizeof(p->dbhdr));
  }else{
    memset(&p->dbhdr, 0, sizeof(p->dbhdr));
    p->dbhdr.pgsz = BT_DEFAULT_PGSZ;
  }






  return rc;
}

/*
** Commit the current write transaction to disk.
*/
static int btCommitTransaction(BtPager *p){
................................................................................
    memset(pRet, 0, sizeof(BtPage));
    pRet->aData = aData;
    pRet->pPager = p;
    rc = SQLITE4_OK;
  }else{
    sqlite4_free(p->pEnv, pRet);
    sqlite4_free(p->pEnv, aData);
    rc = SQLITE4_NOMEM;
    pRet = 0;
  }

  *ppPg = pRet;
  return rc;
}

................................................................................
    }
    p->iTransactionLevel = iLevel;
  }
  return rc;
}

int sqlite4BtPagerRollback(BtPager *p, int iLevel){
  int rc;

  assert( p->pFd );
  if( p->iTransactionLevel>=iLevel ){
    assert( iLevel<=1 );          /* TODO: Fix this! */

    rc = btRollbackTransaction(p);

    p->iTransactionLevel = iLevel;
  }

  return rc;
}

int sqlite4BtPagerRevert(BtPager *p, int iLevel){
................................................................................
int sqlite4BtPagerTransactionLevel(BtPager *p){
  return p->iTransactionLevel;
}

/*
** Query for the database page size. Requires an open read transaction.
*/
int sqlite4BtPagerPagesize(BtPager *p, int *pnByte){
  assert( p->iTransactionLevel>=1 && p->pFd );
  *pnByte = (int)p->dbhdr.pgsz;
  return SQLITE4_OK;
}


/* 
** Query for the root page number. Requires an open read transaction.
*/
int sqlite4BtPagerRootpgno(BtPager *p, u32 *piRoot){
  assert( p->iTransactionLevel>=1 && p->pFd );
  *piRoot = 2;
  return SQLITE4_OK;
}

/*
** Read, write and trim existing database pages.
*/
int sqlite4BtPageGet(BtPager *p, u32 pgno, BtPage **ppPg){
  int rc = SQLITE4_OK;            /* Return code */

  if( p->hash.nEntry>=p->hash.nHash/2 ){
    int i;
    int nNew = (p->hash.nHash ? p->hash.nHash*2 : 256);
    BtPage **aNew;
    BtPage **aOld = p->hash.aHash;

    aNew = (BtPage **)sqlite4_malloc(p->pEnv, nNew*sizeof(BtPage*));
    if( aNew==0 ) return btErrorBkpt(SQLITE4_NOMEM);
    memset(aNew, 0, nNew*sizeof(BtPage*));
    for(i=0; i<p->hash.nHash; i++){
      while( aOld[i] ){
        BtPage *pShift = aOld[i];
        aOld[i] = pShift->pNextHash;
        h = hashkey(nNew, pPg->pgno);
        pShift->pNextHash = aNew[h];
................................................................................
}

/*
** Search the hash table for a page with page number pgno. If found, return
** a pointer to the BtPage object. Otherwise, return NULL.
*/
static BtPage *btHashSearch(BtPager *p, u32 pgno){
  BtPage *pRet = 0;
  if( p->hash.nHash ){
    int h = hashkey(p->hash.nHash, pgno);

    for(pRet=p->hash.aHash[h]; pRet && pRet->pgno!=pgno; pRet=pRet->pNextHash);
  }
  return pRet;
}

/*
** Remove all entries from the hash-table. And free any allocations made
** by earlier calls to btHashAdd().
*/
................................................................................
*/
int sqlite4BtPagerNew(sqlite4_env *pEnv, int nExtra, BtPager **pp){
  BtPager *p;
  int nByte;

  nByte = sizeof(BtPager) + nExtra;
  p = (BtPager*)sqlite4_malloc(pEnv, nByte);
  if( !p ) return btErrorBkpt(SQLITE4_NOMEM); 
  memset(p, 0, nByte);

  p->pEnv = pEnv;
  p->pVfs = sqlite4BtEnvDefault();
  *pp = p;
  return SQLITE4_OK;
}
................................................................................
  if( rc==SQLITE4_OK && nByte>0 ){
    rc = p->pVfs->xRead(p->pFd, 0, &p->dbhdr, sizeof(p->dbhdr));
  }else{
    memset(&p->dbhdr, 0, sizeof(p->dbhdr));
    p->dbhdr.pgsz = BT_DEFAULT_PGSZ;
  }

  if( rc==SQLITE4_OK ){
    /* If the read transaction was successfully opened, the transaction 
    ** level is now 1.  */
    p->iTransactionLevel = 1;
  }
  return rc;
}

/*
** Commit the current write transaction to disk.
*/
static int btCommitTransaction(BtPager *p){
................................................................................
    memset(pRet, 0, sizeof(BtPage));
    pRet->aData = aData;
    pRet->pPager = p;
    rc = SQLITE4_OK;
  }else{
    sqlite4_free(p->pEnv, pRet);
    sqlite4_free(p->pEnv, aData);
    rc = btErrorBkpt(SQLITE4_NOMEM);
    pRet = 0;
  }

  *ppPg = pRet;
  return rc;
}

................................................................................
    }
    p->iTransactionLevel = iLevel;
  }
  return rc;
}

int sqlite4BtPagerRollback(BtPager *p, int iLevel){
  int rc = SQLITE4_OK;

  assert( p->pFd );
  if( p->iTransactionLevel>=iLevel ){
    assert( iLevel<=1 );          /* TODO: Fix this! */
    if( p->iTransactionLevel>=2 ){
      rc = btRollbackTransaction(p);
    }
    p->iTransactionLevel = iLevel;
  }

  return rc;
}

int sqlite4BtPagerRevert(BtPager *p, int iLevel){
................................................................................
int sqlite4BtPagerTransactionLevel(BtPager *p){
  return p->iTransactionLevel;
}

/*
** Query for the database page size. Requires an open read transaction.
*/
int sqlite4BtPagerPagesize(BtPager *p){
  assert( p->iTransactionLevel>=1 && p->pFd );
  return (int)p->dbhdr.pgsz;

}


/* 
** Query for the root page number. Requires an open read transaction.
*/
u32 sqlite4BtPagerRootpgno(BtPager *p){
  assert( p->iTransactionLevel>=1 && p->pFd );

  return 2;
}

/*
** Read, write and trim existing database pages.
*/
int sqlite4BtPageGet(BtPager *p, u32 pgno, BtPage **ppPg){
  int rc = SQLITE4_OK;            /* Return code */

#include "btInt.h"

/* There is no fdatasync() call on Android */
#ifdef __ANDROID__
# define fdatasync(x) fsync(x)
#endif

/*
** The malloc/free functions used for allocations made within this file.
** There are relatively few such allocations.
*/
static void *btMalloc(size_t n){ 
  return malloc(n); 
}
static void btFree(void *p){ 
  free(p); 
}
static void *btRealloc(void *p, size_t n){ 
  return realloc(p, n); 
}
static void *btReallocOrFree(void *p, size_t n){
  void *pNew = realloc(p, n); 
  if( pNew==0 ) free(p);
  return pNew;
}

#ifdef NDEBUG
# define btErrorBkpt(x) x
#else
static int btErrorBkpt(int rc){
  return rc;
}
#endif

/*
** An open file is an instance of the following object
*/
typedef struct PosixFile PosixFile;
struct PosixFile {
  sqlite4_env *pSqlEnv;
  bt_env *pEnv;                   /* The run-time environment */
................................................................................
  int nShm;                       /* Number of entries in array apShm[] */
  void **apShm;                   /* Array of 32K shared memory segments */
};

static char *posixShmFile(PosixFile *p){
  char *zShm;
  int nName = strlen(p->zName);
  zShm = (char*)btMalloc(nName+4+1);
  if( zShm ){
    memcpy(zShm, p->zName, nName);
    memcpy(&zShm[nName], "-shm", 5);
  }
  return zShm;
}

................................................................................
    struct stat sStat;

    /* If the shared-memory file has not been opened, open it now. */
    if( p->shmfd<=0 ){
      char *zShm = posixShmFile(p);
      if( !zShm ) return btErrorBkpt(SQLITE4_NOMEM);
      p->shmfd = open(zShm, O_RDWR|O_CREAT, 0644);
      btFree(zShm);
      if( p->shmfd<0 ){ 
        return btErrorBkpt(SQLITE4_IOERR);
      }
    }

    /* If the shared-memory file is not large enough to contain the 
    ** requested chunk, cause it to grow.  */
................................................................................
    }
    if( sStat.st_size<nReq ){
      if( ftruncate(p->shmfd, nReq) ){
        return btErrorBkpt(SQLITE4_IOERR);
      }
    }

    apNew = (void**)btRealloc(p->apShm, sizeof(void *) * nNew);
    if( !apNew ) return btErrorBkpt(SQLITE4_NOMEM);
    for(i=p->nShm; i<nNew; i++){
      apNew[i] = 0;
    }
    p->apShm = apNew;
    p->nShm = nNew;
  }
................................................................................
      }
    }
    close(p->shmfd);
    p->shmfd = 0;
    if( bDelete ){
      char *zShm = posixShmFile(p);
      if( zShm ) unlink(zShm);
      btFree(zShm);
    }
  }
  return SQLITE4_OK;
}


static int btPosixOsClose(bt_file *pFile){
   PosixFile *p = (PosixFile *)pFile;
   btPosixOsShmUnmap(pFile, 0);
   close(p->fd);
   btFree(p->apShm);
   btFree(p);
   return SQLITE4_OK;
}

bt_env *sqlite4BtEnvDefault(void){
  static bt_env posix_env = {
    0,                            /* pVfsCtx */
    btPosixOsFullpath,            /* xFullpath */

#include "btInt.h"

/* There is no fdatasync() call on Android */
#ifdef __ANDROID__
# define fdatasync(x) fsync(x)
#endif




























/*
** An open file is an instance of the following object
*/
typedef struct PosixFile PosixFile;
struct PosixFile {
  sqlite4_env *pSqlEnv;
  bt_env *pEnv;                   /* The run-time environment */
................................................................................
  int nShm;                       /* Number of entries in array apShm[] */
  void **apShm;                   /* Array of 32K shared memory segments */
};

static char *posixShmFile(PosixFile *p){
  char *zShm;
  int nName = strlen(p->zName);
  zShm = (char*)sqlite4_malloc(p->pSqlEnv, nName+4+1);
  if( zShm ){
    memcpy(zShm, p->zName, nName);
    memcpy(&zShm[nName], "-shm", 5);
  }
  return zShm;
}

................................................................................
    struct stat sStat;

    /* If the shared-memory file has not been opened, open it now. */
    if( p->shmfd<=0 ){
      char *zShm = posixShmFile(p);
      if( !zShm ) return btErrorBkpt(SQLITE4_NOMEM);
      p->shmfd = open(zShm, O_RDWR|O_CREAT, 0644);
      sqlite4_free(p->pSqlEnv, zShm);
      if( p->shmfd<0 ){ 
        return btErrorBkpt(SQLITE4_IOERR);
      }
    }

    /* If the shared-memory file is not large enough to contain the 
    ** requested chunk, cause it to grow.  */
................................................................................
    }
    if( sStat.st_size<nReq ){
      if( ftruncate(p->shmfd, nReq) ){
        return btErrorBkpt(SQLITE4_IOERR);
      }
    }

    apNew = (void**)sqlite4_realloc(p->pSqlEnv, p->apShm, sizeof(void*) * nNew);
    if( !apNew ) return btErrorBkpt(SQLITE4_NOMEM);
    for(i=p->nShm; i<nNew; i++){
      apNew[i] = 0;
    }
    p->apShm = apNew;
    p->nShm = nNew;
  }
................................................................................
      }
    }
    close(p->shmfd);
    p->shmfd = 0;
    if( bDelete ){
      char *zShm = posixShmFile(p);
      if( zShm ) unlink(zShm);
      sqlite4_free(p->pSqlEnv, zShm);
    }
  }
  return SQLITE4_OK;
}


static int btPosixOsClose(bt_file *pFile){
   PosixFile *p = (PosixFile *)pFile;
   btPosixOsShmUnmap(pFile, 0);
   close(p->fd);
   sqlite4_free(p->pSqlEnv, p->apShm);
   sqlite4_free(p->pSqlEnv, p);
   return SQLITE4_OK;
}

bt_env *sqlite4BtEnvDefault(void){
  static bt_env posix_env = {
    0,                            /* pVfsCtx */
    btPosixOsFullpath,            /* xFullpath */

*/
static KVFactory memFactory = {
   0,
   "temp",
   sqlite4KVStoreOpenMem,
   1
};






KVFactory sqlite4BuiltinFactory = {
   &memFactory,
   "main",
   sqlite4KVStoreOpenLsm,
   1
};

/*
** The following singleton contains the global configuration for

*/
static KVFactory memFactory = {
   0,
   "temp",
   sqlite4KVStoreOpenMem,
   1
};
static KVFactory btFactory = {
   &memFactory,
   "bt",
   sqlite4OpenBtree,
   1
};
KVFactory sqlite4BuiltinFactory = {
   &btFactory,
   "main",
   sqlite4KVStoreOpenLsm,
   1
};

/*
** The following singleton contains the global configuration for

  const char *zStorageName;
  KVFactory *pMkr;
  sqlite4_kvfactory xFactory;

  if( (flags & SQLITE4_KVOPEN_TEMPORARY)!=0 || zUri==0 || zUri[0]==0 ){
    zStorageName = "temp";
  }else{
    zStorageName = sqlite4_uri_parameter(zName, "kv");
    if( zStorageName==0 ){
      if( memcmp(":memory:", zUri, 8)==0 ){
        zStorageName = "temp";
      }else{
        zStorageName = "main";
      }
    }

  const char *zStorageName;
  KVFactory *pMkr;
  sqlite4_kvfactory xFactory;

  if( (flags & SQLITE4_KVOPEN_TEMPORARY)!=0 || zUri==0 || zUri[0]==0 ){
    zStorageName = "temp";
  }else{
    zStorageName = sqlite4_uri_parameter(zUri, "kv");
    if( zStorageName==0 ){
      if( memcmp(":memory:", zUri, 8)==0 ){
        zStorageName = "temp";
      }else{
        zStorageName = "main";
      }
    }

/* Typedefs of datatypes */
typedef struct sqlite4_kvstore KVStore;
typedef struct sqlite4_kv_methods KVStoreMethods;
typedef struct sqlite4_kvcursor KVCursor;
typedef unsigned char KVByteArray;
typedef sqlite4_kvsize KVSize;


int sqlite4KVStoreOpenMem(sqlite4_env*, KVStore**, const char *, unsigned);
int sqlite4KVStoreOpenLsm(sqlite4_env*, KVStore**, const char *, unsigned);
int sqlite4KVStoreOpen(
  sqlite4*,
  const char *zLabel, 
  const char *zUri,
  KVStore**,

/* Typedefs of datatypes */
typedef struct sqlite4_kvstore KVStore;
typedef struct sqlite4_kv_methods KVStoreMethods;
typedef struct sqlite4_kvcursor KVCursor;
typedef unsigned char KVByteArray;
typedef sqlite4_kvsize KVSize;

int sqlite4OpenBtree(sqlite4_env*, KVStore**, const char *, unsigned);
int sqlite4KVStoreOpenMem(sqlite4_env*, KVStore**, const char *, unsigned);
int sqlite4KVStoreOpenLsm(sqlite4_env*, KVStore**, const char *, unsigned);
int sqlite4KVStoreOpen(
  sqlite4*,
  const char *zLabel, 
  const char *zUri,
  KVStore**,

*/
static int btSeek(
  KVCursor *pKVCursor, 
  const KVByteArray *aKey,
  KVSize nKey,
  int dir
){
  int rc;
  KVBtCsr *pCsr = (KVBtCsr *)pKVCursor;

  assert( dir==0 || dir==1 || dir==-1 || dir==-2 );
  assert( BT_SEEK_EQ==0 && BT_SEEK_GE==1 && BT_SEEK_LE==-1 );
  assert( BT_SEEK_LEFAST==-2 );

  return sqlite4BtCsrSeek(pCsr->pCsr, (void *)aKey, nKey, dir);
................................................................................
** Though the entry is "deleted", it still continues to exist as a
** phantom.  Subsequent xNext or xPrev calls will work, as will
** calls to xKey and xData, thought the result from xKey and xData
** are undefined.
*/
static int btDelete(KVCursor *pKVCursor){
  KVBtCsr *pBtcsr = (KVBtCsr *)pKVCursor;
  return sqlite4BtDelete(pBtcsr);
}

/*
** Return the key of the node the cursor is pointing to.
*/
static int btKey(
  KVCursor *pKVCursor,         /* The cursor whose key is desired */
................................................................................
    btGetMeta,                    /* xGetMeta */
    btPutMeta,                    /* xPutMeta */
    btGetMethod                   /* xGetMethod */
  };

  KVBt *pNew = 0;
  bt_db *pDb = 0;


  rc = sqlite4BtNew(ENV, sizeof(KVBt), &pDb);
  if( rc==SQLITE4_OK ){
    pNew = (KVBt*)sqlite4BtExtra(pDb);
    pNew->base.pStoreVfunc = &bt_methods;
    pNew->base.pEnv = pEnv;
    pNew->pDb = pDb;
    rc = sqlite4BtOpen(pDb, zFilename);
  }

*/
static int btSeek(
  KVCursor *pKVCursor, 
  const KVByteArray *aKey,
  KVSize nKey,
  int dir
){

  KVBtCsr *pCsr = (KVBtCsr *)pKVCursor;

  assert( dir==0 || dir==1 || dir==-1 || dir==-2 );
  assert( BT_SEEK_EQ==0 && BT_SEEK_GE==1 && BT_SEEK_LE==-1 );
  assert( BT_SEEK_LEFAST==-2 );

  return sqlite4BtCsrSeek(pCsr->pCsr, (void *)aKey, nKey, dir);
................................................................................
** Though the entry is "deleted", it still continues to exist as a
** phantom.  Subsequent xNext or xPrev calls will work, as will
** calls to xKey and xData, thought the result from xKey and xData
** are undefined.
*/
static int btDelete(KVCursor *pKVCursor){
  KVBtCsr *pBtcsr = (KVBtCsr *)pKVCursor;
  return sqlite4BtDelete(pBtcsr->pCsr);
}

/*
** Return the key of the node the cursor is pointing to.
*/
static int btKey(
  KVCursor *pKVCursor,         /* The cursor whose key is desired */
................................................................................
    btGetMeta,                    /* xGetMeta */
    btPutMeta,                    /* xPutMeta */
    btGetMethod                   /* xGetMethod */
  };

  KVBt *pNew = 0;
  bt_db *pDb = 0;
  int rc;

  rc = sqlite4BtNew(pEnv, sizeof(KVBt), &pDb);
  if( rc==SQLITE4_OK ){
    pNew = (KVBt*)sqlite4BtExtra(pDb);
    pNew->base.pStoreVfunc = &bt_methods;
    pNew->base.pEnv = pEnv;
    pNew->pDb = pDb;
    rc = sqlite4BtOpen(pDb, zFilename);
  }

# 2013 September 24
#
# 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.
#
#***********************************************************************
# The tests in this file were used while developing the SQLite 4 code. 
#
set testdir [file dirname $argv0]
source $testdir/tester.tcl
set testprefix simple3

db close
forcedelete test.db

do_test 1.0 {
  sqlite4 db file:test.db?kv=bt
  db close
} {}

do_test 1.1 { sqlite4 db file:test.db?kv=bt } {}
execsql { PRAGMA trace = 1 }
do_execsql_test 1.2 { CREATE TABLE t1(a, b) } 

finish_test

<p><b>Page Header</b>

<p>Page headers are similar to those in SQLite3: 

<ul>
  <li> 1 byte - flags.
  <li> 2 bytes - Number of cells on this page.
  <li> 2 bytes - Offset of first byte after last cell.
  <li> Internal nodes only: 4 bytes - Page number of rightmost child node.
</ul>

<p><b>Page Footer</b>









<h4 id=cell_formats>2.2.3.8. Cell Formats</h4>

<p><b>B-Tree Nodes</b>

<p>Cell format:

<p><b>Page Header</b>

<p>Page headers are similar to those in SQLite3: 

<ul>
  <li> 1 byte - flags.


  <li> Internal nodes only: 4 bytes - Page number of rightmost child node.
</ul>

<p><b>Page Footer</b>

<p> Starting from the end of the page, the fields in the page footer are:

<ul>
  <li> 2 bytes - Number of cells on this page.
  <li> 2 bytes - Offset of first byte after last cell.
  <li> 2 bytes for each cell - the offset to the start of the cell.
</ul>

<h4 id=cell_formats>2.2.3.8. Cell Formats</h4>

<p><b>B-Tree Nodes</b>

<p>Cell format: