*  Finish fleshing out the db.c file.
      - sqliteDbReadOvfl
      - sqliteDbSpreadLoad
      - sqliteDbSplit
      - sqliteDbNextIndexLevel
      - fix sqliteDbCursorNext to work right after sqliteDbCursorDelete
  *  Compile db.c with -Wall and get no errors.
  *  Make a pass over pg.c and db.c looking for errors.
      - correct handling of I/O errors, malloc failures, etc.
      - page leaks  (not calling sqlitePgUnref)
  *  Write a test interface for db.c.
  *  Compile and link against the db test interface.
  *  Generate tests for the db interface.
  *  Add read/write locks to pg.c
  *  Add an sqliteDbReorganize() function.
  *  Integrate db into vdbe.
  *  Modify code generation to take advantage of the new db interface.
      - Able to delete without disturbing scan order
      - Now keeps a count of number of table entries
         + Special processing for count(*)
         + Better selection of indices on a select
      - Transactions
  *  Modify sqlite_master to store the table number.
  *  Add a cache in DbCursor to speed up the sqliteDbReadOvfl() routine.

Longer term:
  *  Document all the changes and release Sqlite 2.0.
  *  Techniques for optimizing querys by grouping data with similar
     indices.
  *  "OPTIMIZE select" statement to automatically create and/or tune
     indices.
  *  Parse and use constraints.

** Boston, MA  02111-1307, USA.
**
** Author contact information:
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** $Id: db.c,v 1.1 2001/01/20 19:52:49 drh Exp $
*/
#include "sqliteInt.h"
#include "pg.h"

/*
** Everything we need to know about an open database
*/
................................................................................
    rc = sqlitePgGet(pDb->pPgr, pgno, (void**)ppPage);
    if( rc==SQLITE_OK ){
      pDb->aContent[0] = pFree[1];
      *pPgno = pgno;
      return SQLITE_OK;
    }
  }
  if( (rc = sqlitePgAlloc(pDb->pPgr, &pgno))==SQLITE_OK &&
      (rc = sqlitePgGet(pDb->pPgr, pgno, (void**)ppPage))==SQLITE_OK ){
    *pPgno = pgno;
    return SQLITE_OK;
  }
  return rc;
}

................................................................................
  aPage[0] = SWB(BLOCK_MAGIC | BLOCK_FREE);
  aPage[1] = pDb->aContent[0];
  memset(&aPage[2], 0, SQLITE_PAGE_SIZE - 2*sizeof(u32));
  pDb->aContent[0] = SWB(pgno);
  sqlitePgTouch(aPage);
  sqlitePgUnref(aPage);
}































/*
** Open a database.
*/
int sqliteDbOpen(const char *filename, Db **ppDb){
  Db *pDb = 0;
  Pgr *pPgr = 0;
  u32 *aPage1;
  int rc;


  rc = sqlitePgOpen(filename, &pPgr);
  if( rc!=SQLITE_OK ) goto open_err;
  pDb = sqliteMalloc( sizeof(*pDb) );
  if( pDb==0 ){
    rc = SQLITE_NOMEM;
    goto open_err;
  }
  pDb->pPgr = pPgr;
  pDb->pCursor = 0;
  pDb->inTransaction = 0;

  rc = sqlitePgGet(pDb->pPgr, 1, &aPage1);
  if( rc!=0 ) goto open_err;






  pDb->nContent = SWB(aPage1[3]) + 2;
  pDb->nAlloc = 0;
  rc = sqliteDbExpandContent(pDb, pDb->nContent);
  if( rc!=SQLITE_OK ) goto open_err;
  rc = sqliteDbReadOvfl(pDb, 1, aPage1, 0, pDb->nContent*sizeof(u32),
                        pDb->aContent);
  if( rc!=SQLITE_OK ) goto open_err;
................................................................................
  return SQLITE_OK;
}

/*
** Commit changes to the database
*/ 
int sqliteDbCommit(Db *pDb){


  if( !pDb->inTransaction ){
    return SQLITE_OK;
  }


  sqliteDbWriteOvfl(pDb, 1, 0, pDb->nContent*sizeof(u32), pDb->aContent);
  rc = sqlitePgCommit(pDb->pPgr);
  if( rc!=SQLITE_OK ) return rc;
  pDb->inTransaction = 0;
  return SQLITE_OK;
}

/*
................................................................................
  }
  i = pCur->nLevel-1;
  idx = pCur->aLevel[i].idx;
  aPage = pCur->aLevel[i].aPage;
  assert( aPage );
  assert( idx>=2 && idx+4<(SQLITE_PAGE_SIZE/sizeof(u32))
  nKey = SWB(aPage[idx+2]);
  if( nKey & 0x80000000 ){  ############### -v
    return sqliteDbReadOvfl(pCur->pDb, SWB(aPage[idx+4]), 0, amt, offset, buf);
  }
  if( nKey==4 ){
    kstart = idx + 1;
  }else{
    kstart = idx + 4;
  }
................................................................................
    available -= nKeyU;
  }else{
    u32 newPgno, *newPage;
    aPage[i+2] = SWB(nKey | 0x80000000);
    rc = sqliteDbAllocPage(pCur->pDb, &newPgno, &newPage);
    if( rc!=SQLITE_OK ) goto write_err;
    aPage[i+4] = SWB(newPgno);

    rc = sqliteDbWriteOvfl(pCur->pDb, newPgno, newPage, nKey, pKey); ########
    if( rc!=SQLITE_OK ) goto write_err;
    j = i + 5;
    available -= 1;
  }
  if( nDataU <= available ){
    aPage[i+3] = SWB(nData);
    memcpy(&aPage[j], pData, nData);
................................................................................
    j += nDataU;
  }else{
    u32 newPgno, *newPage;
    aPage[i+3] = SWB(nData | 0x80000000);
    rc = sqliteDbAllocPage(pCur->pDb, &newPgno, &newPage);
    if( rc!=SQLITE_OK ) goto write_err;
    aPage[j] = SWB(newPgno);

    rc = sqliteDbWriteOvfl(pCur->pDb, newPgno, newPage, nData, pData);
    if( rc!=SQLITE_OK ) goto write_err;
    available -= 1;
    j++;
  }    
  if( j<SQLITE_PAGE_SIZE/sizeof(u32) ){
    aPage[j] = 0;
  }
................................................................................

write_err:
  aPage[i] = 0;
  pCur->onEntry = 0;
  return rc;
}

/*
** The cursor is pointing to a particular entry of an index page
** when this routine is called.  This routine frees everything that
** is on the page that the index entry points to.
*/
static int sqliteDbPruneTree(DbCursor *pCur){
  int i, idx;
  u32 *aPage;
  int from, to, limit, n;
  int rc;

  i = pCur->nLevel-1;
  assert( i>=0 && i<MAX_LEVEL );
  idx = pCur->aLevel[i].idx;
  aPage = pCur->aLevel[i].aPage;
  assert( SWB(aPage[0])==BLOCK_MAGIC|BLOCK_INDEX );
  assert( idx>=3 && idx<SQLITE_PAGE_SIZE/sizeof(u32) );
  n = SWB(aPage[2]);
  assert( n>=2 && n<=SQLITE_PAGE_SIZE/2*sizeof(u32)-2 );
  sqliteDbDropPage(pCur->pDb, SWB(aPage[idx+1]);
  to = idx;
  from = idx+2;
  limit = n*2 + 3;
  while( from<limit ){
    aPage[to++] = aPage[from++];
  }
  n--;
  if( n==1 ){
    u32 oldPgno, *oldPage;
    oldPgno = SWB(aPage[4]);
    rc = sqlitePgGet(pCur->pDb->pPgr, oldPgno, &oldPage);
    if( rc!=SQLITE_OK ){
      return rc;  /* Do something smarter here */
    }
    memcpy(aPage, oldPage, SQLITE_PAGE_SIZE);
    oldPage[0] = SWB(BLOCK_MAGIC|BLOCK_OVERFLOW);
    oldPage[1] = 0;
    sqliteDbDropPage(pCur->pDb, oldPgno);
    sqlitePgUnref(oldPage);
  }else{
    aPage[2] = SWB(n);
  }
  sqlitePgTouch(aPage);
  return SQLITE_OK;
}

/*
** Delete the entry that the cursor points to.
*/
int sqliteDbCursorDelete(DbCursor *pCur){
  int i, idx;
  int from, to;
  int entrySize;
  u32 *aPage;
  if( !pCur->onEntry ) return SQLITE_NOTFOUND;

  /* Delete the entry that the cursor is pointing to.
  */
  i = pCur->nLevel - 1;
................................................................................
  */
  if( to>2 || pCur->nLevel==1 ) return SQLITE_OK;

  /* Collapse the tree into a more compact form.
  */
  sqliteDbResetCursor(pCur, pCur->nLevel-1);

  return sqliteDbPruneTree(pCur);













}

** Boston, MA  02111-1307, USA.
**
** Author contact information:
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** $Id: db.c,v 1.2 2001/01/21 00:58:08 drh Exp $
*/
#include "sqliteInt.h"
#include "pg.h"

/*
** Everything we need to know about an open database
*/
................................................................................
    rc = sqlitePgGet(pDb->pPgr, pgno, (void**)ppPage);
    if( rc==SQLITE_OK ){
      pDb->aContent[0] = pFree[1];
      *pPgno = pgno;
      return SQLITE_OK;
    }
  }
  if( (rc = sqlitePgCount(pDb->pPgr, &pgno))==SQLITE_OK &&
      (rc = sqlitePgGet(pDb->pPgr, pgno, (void**)ppPage))==SQLITE_OK ){
    *pPgno = pgno;
    return SQLITE_OK;
  }
  return rc;
}

................................................................................
  aPage[0] = SWB(BLOCK_MAGIC | BLOCK_FREE);
  aPage[1] = pDb->aContent[0];
  memset(&aPage[2], 0, SQLITE_PAGE_SIZE - 2*sizeof(u32));
  pDb->aContent[0] = SWB(pgno);
  sqlitePgTouch(aPage);
  sqlitePgUnref(aPage);
}

/*
** Write data into overflow pages.  The first overflow page is
** provided in the second argument.  If additional pages are
** needed, they must be allocated.
*/
static int sqliteDbWriteOvfl(Db *pDb, u32 *aPage, int nData, const void *pData){
  while( nData>0 ){
    int toWrite, rc;
    u32 *nxPage, nxPgno;
    if( nData > SQLITE_PAGE_SIZE - 2*sizeof(u32) ){
      toWrite = SQLITE_PAGE_SIZE - 2*sizeof(u32);
    }else{
      toWrite = nData;
    }
    memcpy(&aPage[2], pData, toWrite);
    nData -= toWrite;
    pData = &((char*)pData)[toWrite];
    if( nData<=0 ) break;
    rc = sqliteDbAllocPage(pDb, &nxPgno, &nxPage);
    if( rc!=SQLITE_OK ) return rc;  /* Be smarter here */
    aPage[1] = SWB(nxPgno);
    nxPage[0] = SWB(BLOCK_MAGIC|BLOCK_OVERFLOW);
    nxPage[1] = 0;
    sqlitePgTouch(aPage);
    sqlitePgUnref(aPage);
    aPage = nxPage;
  }
  return SQLITE_OK;
}

/*
** Open a database.
*/
int sqliteDbOpen(const char *filename, Db **ppDb){
  Db *pDb = 0;
  Pgr *pPgr = 0;
  u32 *aPage1;
  int rc;
  u32 nPage;

  rc = sqlitePgOpen(filename, &pPgr);
  if( rc!=SQLITE_OK ) goto open_err;
  pDb = sqliteMalloc( sizeof(*pDb) );
  if( pDb==0 ){
    rc = SQLITE_NOMEM;
    goto open_err;
  }
  pDb->pPgr = pPgr;
  pDb->pCursor = 0;
  pDb->inTransaction = 0;
  sqlitePgCount(pDb->pPgr, &nPage);
  rc = sqlitePgGet(pDb->pPgr, 1, &aPage1);
  if( rc!=0 ) goto open_err;
  if( nPage==0 ){
    sqlitePgBeginTransaction(pDb->pPgr);
    aPage1[0] = SWB(BLOCK_MAGIC|BLOCK_CONTENT);
    sqlitePgTouch(aPage1);
    sqlitePgCommit(pDb->pPgr);
  }
  pDb->nContent = SWB(aPage1[3]) + 2;
  pDb->nAlloc = 0;
  rc = sqliteDbExpandContent(pDb, pDb->nContent);
  if( rc!=SQLITE_OK ) goto open_err;
  rc = sqliteDbReadOvfl(pDb, 1, aPage1, 0, pDb->nContent*sizeof(u32),
                        pDb->aContent);
  if( rc!=SQLITE_OK ) goto open_err;
................................................................................
  return SQLITE_OK;
}

/*
** Commit changes to the database
*/ 
int sqliteDbCommit(Db *pDb){
  u32 *aPage;
  int rc;
  if( !pDb->inTransaction ){
    return SQLITE_OK;
  }
  rc = sqlitePgGet(pDb->pPgr, 1, &aPage);
  if( rc!=SQLITE_OK ) return rc;
  sqliteDbWriteOvfl(pDb, aPage, pDb->nContent*sizeof(u32), pDb->aContent);
  rc = sqlitePgCommit(pDb->pPgr);
  if( rc!=SQLITE_OK ) return rc;
  pDb->inTransaction = 0;
  return SQLITE_OK;
}

/*
................................................................................
  }
  i = pCur->nLevel-1;
  idx = pCur->aLevel[i].idx;
  aPage = pCur->aLevel[i].aPage;
  assert( aPage );
  assert( idx>=2 && idx+4<(SQLITE_PAGE_SIZE/sizeof(u32))
  nKey = SWB(aPage[idx+2]);
  if( nKey & 0x80000000 ){
    return sqliteDbReadOvfl(pCur->pDb, SWB(aPage[idx+4]), 0, amt, offset, buf);
  }
  if( nKey==4 ){
    kstart = idx + 1;
  }else{
    kstart = idx + 4;
  }
................................................................................
    available -= nKeyU;
  }else{
    u32 newPgno, *newPage;
    aPage[i+2] = SWB(nKey | 0x80000000);
    rc = sqliteDbAllocPage(pCur->pDb, &newPgno, &newPage);
    if( rc!=SQLITE_OK ) goto write_err;
    aPage[i+4] = SWB(newPgno);
    newPage[0] = SWB(BLOCK_MAGIC | BLOCK_OVERFLOW);
    rc = sqliteDbWriteOvfl(pCur->pDb, newPage, nKey, pKey);
    if( rc!=SQLITE_OK ) goto write_err;
    j = i + 5;
    available -= 1;
  }
  if( nDataU <= available ){
    aPage[i+3] = SWB(nData);
    memcpy(&aPage[j], pData, nData);
................................................................................
    j += nDataU;
  }else{
    u32 newPgno, *newPage;
    aPage[i+3] = SWB(nData | 0x80000000);
    rc = sqliteDbAllocPage(pCur->pDb, &newPgno, &newPage);
    if( rc!=SQLITE_OK ) goto write_err;
    aPage[j] = SWB(newPgno);
    newPage[0] = SWB(BLOCK_MAGIC | BLOCK_OVERFLOW);
    rc = sqliteDbWriteOvfl(pCur->pDb, newPage, nData, pData);
    if( rc!=SQLITE_OK ) goto write_err;
    available -= 1;
    j++;
  }    
  if( j<SQLITE_PAGE_SIZE/sizeof(u32) ){
    aPage[j] = 0;
  }
................................................................................

write_err:
  aPage[i] = 0;
  pCur->onEntry = 0;
  return rc;
}

/*














































** Delete the entry that the cursor points to.
*/
int sqliteDbCursorDelete(DbCursor *pCur){
  int i, idx;
  int from, to, limit, n;
  int entrySize;
  u32 *aPage;
  if( !pCur->onEntry ) return SQLITE_NOTFOUND;

  /* Delete the entry that the cursor is pointing to.
  */
  i = pCur->nLevel - 1;
................................................................................
  */
  if( to>2 || pCur->nLevel==1 ) return SQLITE_OK;

  /* Collapse the tree into a more compact form.
  */
  sqliteDbResetCursor(pCur, pCur->nLevel-1);

  i = pCur->nLevel-1;
  assert( i>=0 && i<MAX_LEVEL );
  idx = pCur->aLevel[i].idx;
  aPage = pCur->aLevel[i].aPage;
  assert( SWB(aPage[0])==BLOCK_MAGIC|BLOCK_INDEX );
  assert( idx>=3 && idx<SQLITE_PAGE_SIZE/sizeof(u32) );
  n = SWB(aPage[2]);
  assert( n>=2 && n<=SQLITE_PAGE_SIZE/2*sizeof(u32)-2 );
  sqliteDbDropPage(pCur->pDb, SWB(aPage[idx+1]);
  to = idx;
  from = idx+2;
  limit = n*2 + 3;
  while( from<limit ){
    aPage[to++] = aPage[from++];
  }
  n--;
  if( n==1 ){
    u32 oldPgno, *oldPage;
    oldPgno = SWB(aPage[4]);
    rc = sqlitePgGet(pCur->pDb->pPgr, oldPgno, &oldPage);
    if( rc!=SQLITE_OK ){
      return rc;  /* Do something smarter here */
    }
    memcpy(aPage, oldPage, SQLITE_PAGE_SIZE);
    oldPage[0] = SWB(BLOCK_MAGIC|BLOCK_OVERFLOW);
    oldPage[1] = 0;
    sqliteDbDropPage(pCur->pDb, oldPgno);
    sqlitePgUnref(oldPage);
  }else{
    aPage[2] = SWB(n);
  }
  sqlitePgTouch(aPage);
  return SQLITE_OK;
}

** Boston, MA  02111-1307, USA.
**
** Author contact information:
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** $Id: pg.c,v 1.2 2001/01/20 19:52:49 drh Exp $
*/
#include <assert.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include "sqliteInt.h"
................................................................................
/*
** Uncomment the following for a debug trace
*/
#if 1
# define TRACE(X)  printf X; fflush(stdout);
#endif  

#ifndef SQLITE_IOERR
# define SQLITE_IOERR SQLITE_ERROR
#endif

/*
** Hash table sizes
*/
#define J_HASH_SIZE  127  /* Size of the journal page hash table */
#define PG_HASH_SIZE 349  /* Size of the database page hash table */

/*

** Boston, MA  02111-1307, USA.
**
** Author contact information:
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** $Id: pg.c,v 1.3 2001/01/21 00:58:08 drh Exp $
*/
#include <assert.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include "sqliteInt.h"
................................................................................
/*
** Uncomment the following for a debug trace
*/
#if 1
# define TRACE(X)  printf X; fflush(stdout);
#endif  





/*
** Hash table sizes
*/
#define J_HASH_SIZE  127  /* Size of the journal page hash table */
#define PG_HASH_SIZE 349  /* Size of the database page hash table */

/*

** Boston, MA  02111-1307, USA.
**
** Author contact information:
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** $Id: pg.h,v 1.2 2001/01/20 19:52:49 drh Exp $
*/

typedef struct Pgr Pgr;
#define SQLITE_PAGE_SIZE 1024


int sqlitePgOpen(const char *filename, Pgr **pp);
................................................................................
int sqlitePgClose(Pgr*);
int sqlitePgBeginTransaction(Pgr*);
int sqlitePgCommit(Pgr*);
int sqlitePgRollback(Pgr*);
int sqlitePgGet(Pgr*, u32 pgno, void **);
int sqlitePgUnref(void*);
int sqlitePgTouch(void*);
int sqlitePgAlloc(Pgr*, u32*);
u32 sqlitePgNum(void*);

** Boston, MA  02111-1307, USA.
**
** Author contact information:
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** $Id: pg.h,v 1.3 2001/01/21 00:58:09 drh Exp $
*/

typedef struct Pgr Pgr;
#define SQLITE_PAGE_SIZE 1024


int sqlitePgOpen(const char *filename, Pgr **pp);
................................................................................
int sqlitePgClose(Pgr*);
int sqlitePgBeginTransaction(Pgr*);
int sqlitePgCommit(Pgr*);
int sqlitePgRollback(Pgr*);
int sqlitePgGet(Pgr*, u32 pgno, void **);
int sqlitePgUnref(void*);
int sqlitePgTouch(void*);
int sqlitePgCount(Pgr*, u32*);
u32 sqlitePgNum(void*);