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

/*
** Everything we need to know about an open database
*/
................................................................................
** this structure.
*/
typedef struct DbIdxpt DbIdxpt;
struct DbIdxpt {
  int pgno;         /* The page number */
  u32 *aPage;       /* The page data */
  int idx;          /* Index into pPage[] */


};

/*
** Everything we need to know about a cursor
*/
struct DbCursor {
  Db *pDb;                      /* The whole database */
................................................................................
**     0.   BLOCK_MAGIC | BLOCK_CONTENTS
**     1.   zero
**     2.   number of bytes of payload
**     3.   freelist
**     4... root pages numbers of tables
*/




#define U32_PER_PAGE  (SQLITE_PAGE_SIZE/sizeof(u32))











#deifne LOCAL_PAYLOAD  (SQLITE_PAGE_SIZE - 18*sizeof(u32))

/*
** Byte swapping code.



*/
#ifdef BIG_ENDIAN
# SWB(x) (x)
#else
# SWB(x) sqliteDbSwapBytes(x)
#endif




static u32 sqliteDbSwapBytes(u32 x){
  unsigned char c, *s, *d;
  s = (unsigned char*)&x;
  d = (unsigned char*)&r;
  d[0] = s[3];
  d[1] = s[2];
  d[2] = s[1];
  d[3] = s[0];
























  return r;
}

#endif



















/*
** Return the number of bytes of payload storage required on the leaf

** node to hold the key and data given.  Overflow pages do not count.
** The argument is the total size of the payload.


*/
static int payloadLocalSize(int nTotal){
  int nLocal, i;
  if( nTotal<0 ) nTotal = 0;
  if( nTotal <= LOCAL_PAYLOAD ){
    /* All the data fits on the leaf page */
    return (nTotal + 3)/4;
  }
  nLocal = LOCAL_PAYLOAD;
  nTotal -= LOCAL_PAYLOAD;
  if( nTotal < 10*SQLITE_PAGE_SIZE ){
    return nLocal + ((nTotal+SQLITE_PAGE_SIZE-1)/SQLITE_PAGE_SIZE)*sizeof(u32);
  }
  nLocal += 10*sizeof(u32);
  nTotal -= 10*SQLITE_PAGE_SIZE;
  if( nTotal < U32_PER_PAGE*SQLITE_PAGE_SIZE ){
    return nLocal + sizeof(u32);
  }
  nLocal += sizeof(u32);
  nTotal -= U32_PER_PAGE*SQLITE_PAGE_SIZE;
  if( nTotal < U32_PER_PAGE*U32_PER_PAGE*SQLITE_PAGE_SIZE ){
    return nLocal + sizeof(u32);
................................................................................
**
** aPage points directly at the beginning of the payload.  No bounds 
** checking is done on offset or amt -- it is assumed that the payload
** area is big enough to accomodate.
*/
static int payloadRead(Db *pDb, u32 *aPage, int offset, int amt, void *pBuf){
  int rc;
  int toread, more;





  assert( offset>=0 && amt>=0 );
  if( offset < LOCAL_PAYLOAD ){
    /* Data stored directly in the leaf block of the BTree */
    if( amt+offset>LOCAL_PAYLOAD ){
      toread = LOCAL_PAYLOAD - offset;
      more = 1;
    }else{
      toread = amt;
      more = 0;
    }
    memcpy(pBuf, &((char*)aPage)[offset], toread);
    if( !more ) return SQLITE_OK;
    pBuf = &((char*)pBuf)[toread];
    offset += toread;
    amt -= toread;
  }
  offset -= LOCAL_PAYLOAD;
  aPage += LOCAL_PAYLOAD/sizeof(aPage[0]);
  while( offset < 10*SQLITE_PAGE_SIZE ){
    /* Data stored in one of 10 direct pages */
    int iDir;
    char *aData;
    iDir = offset/SQLITE_PAGE_SIZE;
    base = offset - iDir*SQLITE_PAGE_SIZE;
    rc = sqlitePgGet(pDb->pPgr, aPage[iDir], &aData);
    if( rc!=SQLITE_OK ) return rc;
    if( amt+base > SQLITE_PAGE_SIZE ){
      toread = SQLITE_PAGE_SIZE - base;
      more = 1;
    }else{
      toread = amt;
      more = 0;
    }
    memcpy(pBuf, &aData[base], toread);
    sqlitePgUnref(aData);
    if( !more ) return SQLITE_OK;
    pBuf = &((char*)pBuf)[toread];
    amt -= toread;
    offset += toread;
  }
  offset -= 10*SQLITE_PAGE_SIZE;
  aPage += 10;
  if( offset < U32_PER_PAGE*SQLITE_PAGE_SIZE ){
    /* Data stored in an indirect page */ 
    u32 *indirPage;
    rc = sqlitePgGet(pDb->pPgr, aPage[0], &indirPage);
    if( rc!=SQLITE_OK ) return rc;
    while( amt>0 && offset < U32_PER_PAGE*SQLITE_PAGE_SIZE ){
      int idx, base;
      char *aData;
      idx = offset/SQLITE_PAGE_SIZE;
      base = offset - idx*SQLITE_PAGE_SIZE;
      rc = sqlitePgGet(pDb->pPgr, indirPage[idx], &aData);
      if( rc!=SQLITE_OK ) break;
      if( amt+base > SQLITE_PAGE_SIZE ){
        toread = SQLITE_PAGE_SIZE - base;
      }else{
        toread = amt;
      }
      memcpy(pBuf, &aData[base], toread);
      sqlitePgUnref(aData);
      pBuf = &((char*)pBuf)[toread];
      amt -= toread;
      offset += toread;
    }
    sqlitePgUnref(indirPage);
    if( rc!=SQLITE_OK ) return rc;

  }
  offset -= U32_PER_PAGE*SQLITE_PAGE_SIZE;
  aPage++;











  if( offset < U32_PER_PAGE*U32_PER_PAGE*SQLITE_PAGE_SIZE ){
    /* Data stored in a double-indirect page */
    u32 *dblIndirPage;
    rc = sqlitePgGet(pDb->pPgr, aPage[0], &dblIndirPage);
    if( rc!=SQLITE_OK ) return rc;
    while( amt>0 && offset < U32_PER_PAGE*U32_PER_PAGE*SQLITE_PAGE_SIZE ){
      int dblidx;
      u32 *indirPage;
      int basis;
      dblidx = offset/(U32_PER_PAGE*SQLITE_PAGE_SIZE);
      rc = sqlitePgGet(pDb->pPgr, dblIndirPage[dblidx], &indirPage);
      if( rc!=SQLITE_OK ) break;
      basis = dblidx*U32_PER_PAGE*SQLITE_PAGE_SIZE;
      while( amt>0 && offset < basis + U32_PER_PAGE*SQLITE_PAGE_SIZE ){
        int idx, base;
        char *aData;
        idx = (offset - basis)/SQLITE_PAGE_SIZE;
        base = (offset - basis) - idx*SQLITE_PAGE_SIZE;
        rc = sqlitePgGet(pDb->pPgr, indirPage[idx], &aData);
        if( rc!=SQLITE_OK ) break;
        if( amt+base > SQLITE_PAGE_SIZE ){
          toread = SQLITE_PAGE_SIZE - base;
        }else{
          toread = amt;
        }
        memcpy(pBuf, &aData[base], toread);
        sqlitePgUnref(aData);
        pBuf = &((char*)pBuf)[toread];
        amt -= toread;
        offset += toread;
      }
      sqlitePgUnref(indirPage);
      if( rc!=SQLITE_OK ) break;
    }
    sqlitePgUnref(dblIndirPage);
    return rc;
  }





  memset(pBuf, 0, amt);
  return SQLITE_OK;
}

/*
** Write data into the payload area.
**
** If pages have already been allocated for the payload, they are
................................................................................
** simply overwritten.  New pages are allocated as necessary to
** fill in gaps.  sqlitePgTouch() is called on all overflow pages,
** but the calling function must invoke sqlitePgTouch() for aPage
** itself.
*/
static int payloadWrite(Db *pDb, u32 *aPage, int offset, int amt, void *pBuf){
  assert( offset>=0 && amt>=0 );



  if( offset < LOCAL_PAYLOAD ){
    if( amt+offset>LOCAL_PAYLOAD ){
      towrite = LOCAL_PAYLOAD - offset;
      more = 1;
    }else{
      towrite = amt;
      more = 0;
    }
    memcpy(&((char*)aPage)[offset], pBuf, towrite);
    if( !more ) return SQLITE_OK;
    pBuf = &((char*)pBuf)[towrite];
    offset += toread;
    amt -= toread;

  }
  offset -= LOCAL_PAYLOAD;
  aPage += LOCAL_PAYLOAD/sizeof(aPage[0]);












  while( offset < 10*SQLITE_PAGE_SIZE ){


























    int iDir;
    char *aData;
    iDir = offset/SQLITE_PAGE_SIZE;





















    base = offset - iDir*SQLITE_PAGE_SIZE;






    if( aPage[iDir] ){
      rc = sqliteGet(pDb->pPgr, aPage[iDir], &aData);
    }else{
      rc = sqliteDbAllocPage(pDb, &aPage[iDir], &aData);
    }
    if( rc!=SQLITE_OK ) return rc;

























    if( amt+base > SQLITE_PAGE_SIZE ){
      towrite = SQLITE_PAGE_SIZE - base;
      more = 1;
    }else{
      towrite = amt;
      more = 0;
    }
    memcpy(&aData[base], pBuf, towrite);

    sqlitePgUnref(aData);
    if( !more ) return SQLITE_OK;
    pBuf = &((char*)pBuf)[towrite];
    amt -= towrite;
    offset += towrite;
  }
  /* TBD.... */


}






/*
** Release any and all overflow pages associated with data starting
** with byte "newSize" up to but not including "oldSize".


*/
static int payloadFree(Db *pDb, u32 *aPage, int newSize, int oldSize){
  int i;






  if( newSize>=oldSize ) return;
  oldSize -= LOCAL_PAYLOAD;
  if( oldSize<=0 ) return SQLITE_OK;
  newSize -= LOCAL_PAYLOAD;
  if( newSize<0 ) newSize = 0;
  aPage += LOCAL_PAYLOAD/sizeof(u32);

*************
  for(i=0; i<10; i++){








    sqliteDbFreePage(pDb, aPage[0], 0);
    amt -= SQLITE_PAGE_SIZE;






    if( amt<=0 ) return SQLITE_OK;
    aPage++;

  }




  rc = sqlitePgGet(pDb->pPgr, aPage[0], &indirPage);
  if( rc!=SQLITE_OK ) return rc;
  for(i=0; i<U32_PER_PAGE; i++){
    if( indirPage[i]==0 ) continue;
    sqliteDbFreePage(pDb, indirPage[i], 0);


  }

  sqliteDbFreePage(pDb, aPage[0], indirPage);



  sqlitePgUnref(indirPage);



  amt -= U32_PER_PAGE*SQLITE_PAGE_SIZE;

  if( amt<=0 ) return SQLITE_OK;
  aPage++;






  rc = sqlitePgGet(pDb->pPgr, aPage[0], &dblIndirPage);
  if( rc!=SQLITE_OK ) return rc;
  for(i=0; i<U32_PER_PAGE; i++){
    if( dblIndirPage[i]==0 ) continue;



    rc = sqlitePgGet(pDb->pPgr, dblIndirPage[i], &indirPage);
    if( rc!=SQLITE_OK ) break;
    for(j=0; j<U32_PER_PAGE; j++){


      if( indirPage[j]==0 ) continue;
      sqliteDbFreePage(pDb, dblIndirPage[i], 0);
    }

    sqliteDbFreePage(pDb, dblIndirPage[i], indirPage);


    sqlitePgUnder(indirPage);

  }


  sqliteDbFreePage(pDb, aPage[0], dblIndirPage);



  sqlitePgUnref(dblIndirPage);



  return SQLITE_OK;    
}

/*
** Allocate space for the content table in the given Db structure.
** return SQLITE_OK on success and SQLITE_NOMEM if it fails.
*/
................................................................................
    pDb->nAlloc = 0;
    pDb->inTranaction = 0;
    return SQLITE_NOMEM;
  }
  return SQLITE_OK;
}

/*
** Allocate a new page.  Return both the page number and a pointer
** to the page data.  The calling function is responsible for unref-ing
** the page when it is no longer needed.
*/
int sqliteDbAllocPage(Db *pDb, u32 *pPgno, u32 **ppPage){
  u32 pgno;
  int rc;

  if( pDb->aContent==0 ) return SQLITE_NOMEM;
  pgno = SWB(pDb->aContent[0]);
  if( pgno!=0 ){
    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;
}

/*
** Return a page to the freelist and dereference the page.
*/
static void sqliteDbFreePage(DB *pDb, u32 pgno, u32 *aPage){
  if( pDb->aContent==0 ) return;
  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 sqliteDbCreateTable(Db *pDb, int *pTblno){
  u32 *pPage;
  u32 pgno;
  int rc;
  int swTblno;
  int i;

  rc = sqliteDbAllocPage(pDb, &pgno, &pPage);
  if( rc!=SQLITE_OK ){
    return rc;
  }
  tblno = -1;
  for(i=2; i<pDb->nContent; i++){
    if( pDb->aContent[i]==0 ){
      tblno = i - 2;
................................................................................
*/
static int sqliteDbDropPage(Db *pDb, u32 pgno){
  u32 *aPage;
  int rc;

  rc = sqlitePgGet(pDb->pPgr, pgno, (void**)&aPage);
  if( rc!=SQLITE_OK ) return rc;
  switch(  SWB(aPage[0]) ){
    case BLOCK_MAGIC | BLOCK_INDEX: {
      int n, i;
      n = SWB(aPage[2]);
      for(i=0; i<n; i++){
        u32 subpgno = SWB(aPage[3+i*2]);
        sqliteDbDropPage(pDb, subpgno);
      }
      sqliteDbFreePage(pDb, pgno, aPage);
      break;
    }
    case BLOCK_MAGIC | BLOCK_LEAF: {
      int i = 1;
      while( i<SQLITE_PAGE_SIZE/sizeof(u32) ){
        int entrySize = SWB(aPage[i]);
        if( entrySize==0 ) break;
        sqliteDbClearEntry(pDb, &aPage[i]);
        i += entrySize;
      }
      sqliteDbFreePage(pDb, pgno, aPage);
      break;
    }
    case BLOCK_MAGIC | BLOCK_OVERFLOW: {
      for(;;){
        u32 nx = SWB(aPage[1]);
        sqliteDbFreePage(pDb, pgno, aPage);
        if( nx==0 ) break;
        pgno = nx;
        sqlitePgUnref(aPage);
        sqlitePgGet(pDb->pPgr, pgno, &aPage);
      }
      break;
    }
    default: {
      /* Do nothing */
      break;
    }
  }
................................................................................

/*
** aEntry points directly at a database entry on a leaf page.
** Free any overflow pages associated with the key or data of
** this entry.
*/
static int sqliteDbClearEntry(Db *pDb, u32 *aEntry){
  int nByte;
  int idx;

  idx = 4;
  nByte = SWB(aEntry[2]);
  if( nByte & 0x80000000 ){
    sqliteDbDropPage(pDb, SWB(aEntry[idx]));
    idx++;
  }else{
    idx += (nByte + 3)/4;
  }
  nByte = SWB(aEntry[3]);
  if( nByte & 0x80000000 ){
    sqliteDbDropPage(pDb, SWB(aEntry[idx]));
  }
  return SQLITE_OK;
}

/*
** Delete the current associate of a cursor and release all the
** pages it holds.  Except, do not release pages at levels less
** than N.
................................................................................
    aPage[i+2] = SWB(nKey);
    memcpy(&aPage[i+4], pKey, nKey);
    j = i + 4 + nKeyU;
    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;
................................................................................
    aPage[i+3] = SWB(nData);
    memcpy(&aPage[j], pData, nData);
    available -= nDataU;
    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++;

** Boston, MA  02111-1307, USA.
**
** Author contact information:
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** $Id: db.c,v 1.4 2001/01/25 01:45:40 drh Exp $
*/
#include "sqliteInt.h"
#include "pg.h"

/*
** Everything we need to know about an open database
*/
................................................................................
** this structure.
*/
typedef struct DbIdxpt DbIdxpt;
struct DbIdxpt {
  int pgno;         /* The page number */
  u32 *aPage;       /* The page data */
  int idx;          /* Index into pPage[] */
  int hashLB;       /* Lower bound on hash at this level */
  int hashUB;       /* Upper bound on hash at this level */
};

/*
** Everything we need to know about a cursor
*/
struct DbCursor {
  Db *pDb;                      /* The whole database */
................................................................................
**     0.   BLOCK_MAGIC | BLOCK_CONTENTS
**     1.   zero
**     2.   number of bytes of payload
**     3.   freelist
**     4... root pages numbers of tables
*/

/*
** The number of u32-sized objects that will fit on one page.
*/
#define U32_PER_PAGE  (SQLITE_PAGE_SIZE/sizeof(u32))

/*
** Number of direct overflow pages per database entry
*/
#define N_DIRECT  10

/*
** The maximum amount of payload that will fit on on the same
** page as a leaf, assuming the leaf contains only a single
** database entry and the entry uses no overflow pages.
*/
#define LOCAL_PAYLOAD  (SQLITE_PAGE_SIZE - (8+N_DIRECT)*sizeof(u32))

/*

** Allocate a new page.  Return both the page number and a pointer
** to the page data.  The calling function is responsible for unref-ing
** the page when it is no longer needed.
*/





int allocPage(Db *pDb, u32 *pPgno, u32 **ppPage){
  u32 pgno;
  int rc;









  if( pDb->aContent==0 ) return SQLITE_NOMEM;

  /* Try to reuse a page from the freelist
  */
  pgno = pDb->aContent[0];
  if( pgno!=0 ){
    rc = sqlitePgGet(pDb->pPgr, pgno, (void**)ppPage);
    if( rc==SQLITE_OK ){
      pDb->aContent[0] = pFree[1];
      *pPgno = pgno;
      memset(*ppPage, 0, SQLITE_PAGE_SIZE);
      return SQLITE_OK;
    }
  }

  /* If the freelist is empty, or we cannot access it,
  ** then allocate a new page from the end of the file.
  */
  if( (rc = sqlitePgCount(pDb->pPgr, &pgno))==SQLITE_OK &&
      (rc = sqlitePgGet(pDb->pPgr, pgno, (void**)ppPage))==SQLITE_OK ){
    *pPgno = pgno;
    memset(*ppPage, 0, SQLITE_PAGE_SIZE);
    return SQLITE_OK;
  }
  return rc;
}


/*
** Return a page to the freelist and dereference the page.
*/
static void freePage(DB *pDb, u32 pgno, u32 *aPage){
  if( pDb->aContent==0 ) return;
  if( pgno==0 ) return
  if( aPage==0 ){
    int rc;
    rc = sqlitePgGet(pDb->pPgr, pgno, &aPage);
    if( rc!=SQLITE_OK ) return;
  }
  aPage[0] = BLOCK_MAGIC | BLOCK_FREE;
  aPage[1] = pDb->aContent[0];
  memset(&aPage[2], 0, SQLITE_PAGE_SIZE - 2*sizeof(u32));
  pDb->aContent[0] = pgno;
  sqlitePgTouch(aPage);
  sqlitePgUnref(aPage);
}

/*
** Return the number of bytes of payload storage required on the leaf
** node to hold the amount of payload specified by the argument.
** Overflow pages do not count, only memory on the leaf page.

**
** Return -1 if nTotal is more than sqlite is able to store.
*/
static int payloadLocalSize(int nTotal){
  int nLocal, i;
  if( nTotal<0 ) nTotal = 0;
  if( nTotal <= LOCAL_PAYLOAD ){
    /* All the data fits on the leaf page */
    return (nTotal + 3)/4;
  }
  nLocal = LOCAL_PAYLOAD;
  nTotal -= LOCAL_PAYLOAD;
  if( nTotal < 10*SQLITE_PAGE_SIZE ){
    return nLocal + ((nTotal+SQLITE_PAGE_SIZE-1)/SQLITE_PAGE_SIZE)*sizeof(u32);
  }
  nLocal += N_DIRECT*sizeof(u32);
  nTotal -= N_DIRECT*SQLITE_PAGE_SIZE;
  if( nTotal < U32_PER_PAGE*SQLITE_PAGE_SIZE ){
    return nLocal + sizeof(u32);
  }
  nLocal += sizeof(u32);
  nTotal -= U32_PER_PAGE*SQLITE_PAGE_SIZE;
  if( nTotal < U32_PER_PAGE*U32_PER_PAGE*SQLITE_PAGE_SIZE ){
    return nLocal + sizeof(u32);
................................................................................
**
** aPage points directly at the beginning of the payload.  No bounds 
** checking is done on offset or amt -- it is assumed that the payload
** area is big enough to accomodate.
*/
static int payloadRead(Db *pDb, u32 *aPage, int offset, int amt, void *pBuf){
  int rc;
  int tomove;
  int i;

  /* First read local data off of the leaf page itself.
  ** This is all that ever happens in 99% of accesses.
  */
  assert( offset>=0 && amt>=0 );
  if( offset < LOCAL_PAYLOAD ){
    /* Data stored directly in the leaf block of the BTree */
    if( amt+offset>LOCAL_PAYLOAD ){
      tomove = LOCAL_PAYLOAD - offset;
    }else{
      tomove = amt;
    }
    memcpy(pBuf, &((char*)aPage)[offset], tomove);
    pBuf = &((char*)pBuf)[tomove];
    offset += tomove;
    amt -= tomove;
    if( amt<=0 ) return SQLITE_OK;
  }
  offset -= LOCAL_PAYLOAD;
  aPage += LOCAL_PAYLOAD/sizeof(aPage[0]);

  /* If not all of the data fits locally, read from the first
  ** ten direct-access overflow pages.
  */
  if( offset < N_DIRECT*SQLITE_PAGE_SIZE ){
    for(i=offset/SQLITE_PAGE_SIZE; i<N_DIRECT && amt>0; i++){
      char *aData;
      base = offset - i*SQLITE_PAGE_SIZE;
      rc = sqlitePgGet(pDb->pPgr, aPage[i], &aData);
      if( rc!=SQLITE_OK ) return rc;
      if( amt+base > SQLITE_PAGE_SIZE ){
        tomove = SQLITE_PAGE_SIZE - base;
      }else{
        tomove = amt;
      }
      memcpy(pBuf, &aData[base], tomove);
      sqlitePgUnref(aData);
      pBuf = &((char*)pBuf)[tomove];
      amt -= tomove;
    }
  }
  offset -= N_DIRECT*SQLITE_PAGE_SIZE;
  aPage += N_DIRECT;

  /* If the first N_DIRECT overflow pages do not contain everything, then
  ** read from an overflow page that is filled with pointer to
  ** U32_PER_PAGE more overflow pages.
  */
  if( offset < U32_PER_PAGE*SQLITE_PAGE_SIZE ){
    u32 *indirPage;
    rc = sqlitePgGet(pDb->pPgr, aPage[0], &indirPage);
    if( rc!=SQLITE_OK ) return rc;
    for(i=offset/SQLITE_PAGE_SIZE; i<U32_PER_PAGE && amt>0; i++){
      int base;
      char *aData;
      base = offset - i*SQLITE_PAGE_SIZE;
      rc = sqlitePgGet(pDb->pPgr, indirPage[idx], &aData);
      if( rc!=SQLITE_OK ) break;
      if( amt+base > SQLITE_PAGE_SIZE ){
        tomove = SQLITE_PAGE_SIZE - base;
      }else{
        tomove = amt;
      }
      memcpy(pBuf, &aData[base], tomove);
      sqlitePgUnref(aData);
      pBuf = &((char*)pBuf)[tomove];
      amt -= tomove;

    }
    sqlitePgUnref(indirPage);
    if( rc!=SQLITE_OK ) return rc;
    if( amt<=0 ) return SQLITE_OK;
  }
  offset -= U32_PER_PAGE*SQLITE_PAGE_SIZE;
  aPage++;

  /* If there is still more data, then read using a double-indirect
  ** overflow.  The overflow page points to U32_PER_PAGE additional
  ** overflow pages, each of which pointer to U32_PER_PAGE more overflow
  ** pages which contain data.
  **
  ** This is hard to test.  To exercise this code, you have to make
  ** a database entry of more than 273336 bytes in side, assuming a
  ** pagesize of 1024 bytes and 10 direct overflow pages.  By the 
  ** time this code runs, you have already used 267 overflow pages.
  */
  if( offset < U32_PER_PAGE*U32_PER_PAGE*SQLITE_PAGE_SIZE ){

    u32 *dblIndirPage;
    rc = sqlitePgGet(pDb->pPgr, aPage[0], &dblIndirPage);
    if( rc!=SQLITE_OK ) return rc;
    i = offset/(U32_PER_PAGE*SQLITE_PAGE_SIZE);
    for(; i<U32_PER_PAGE && amt>0; i++){
      u32 *indirPage;
      int basis;
      int j;
      rc = sqlitePgGet(pDb->pPgr, dblIndirPage[i], &indirPage);
      if( rc!=SQLITE_OK ) break;
      basis = i*U32_PER_PAGE*SQLITE_PAGE_SIZE;
      j = (offset - basis)/SQLITE_PAGE_SIZE;
      for(; j<U32_PER_PAGE && amt>0; j++){
        char *aData;

        base = (offset - basis) - ij*SQLITE_PAGE_SIZE;
        rc = sqlitePgGet(pDb->pPgr, indirPage[j], &aData);
        if( rc!=SQLITE_OK ) break;
        if( amt+base > SQLITE_PAGE_SIZE ){
          tomove = SQLITE_PAGE_SIZE - base;
        }else{
          tomove = amt;
        }
        memcpy(pBuf, &aData[base], tomove);
        sqlitePgUnref(aData);
        pBuf = &((char*)pBuf)[tomove];
        amt -= tomove;

      }
      sqlitePgUnref(indirPage);
      if( rc!=SQLITE_OK ) break;
    }
    sqlitePgUnref(dblIndirPage);

  }

  /* Anything beyond the double-indirect pages, just fill in with
  ** zeros.  You have to write 67382200 bytes to go past the
  ** double-indirect pages, assuming a 1024 byte page size.
  */
  if( amt>0 ) memset(pBuf, 0, amt);
  return SQLITE_OK;
}

/*
** Write data into the payload area.
**
** If pages have already been allocated for the payload, they are
................................................................................
** simply overwritten.  New pages are allocated as necessary to
** fill in gaps.  sqlitePgTouch() is called on all overflow pages,
** but the calling function must invoke sqlitePgTouch() for aPage
** itself.
*/
static int payloadWrite(Db *pDb, u32 *aPage, int offset, int amt, void *pBuf){
  assert( offset>=0 && amt>=0 );

  /* Local data
  */
  if( offset < LOCAL_PAYLOAD ){
    if( amt+offset>LOCAL_PAYLOAD ){
      tomove = LOCAL_PAYLOAD - offset;

    }else{
      tomove = amt;

    }
    memcpy(&((char*)aPage)[offset], pBuf, tomove);

    pBuf = &((char*)pBuf)[tomove];
    offset += tomove;
    amt -= tomove;
    if( amt<=0 ) return SQLITE_OK;
  }
  offset -= LOCAL_PAYLOAD;
  aPage += LOCAL_PAYLOAD/sizeof(aPage[0]);

  /* Direct overflow pages
  */
  if( offset < N_DIRECT*SQLITE_PAGE_SIZE ){
    for(i=offset/SQLITE_PAGE_SIZE; i<N_DIRECT && amt>0; i++){
      base = offset - i*SQLITE_PAGE_SIZE;
      if( aPage[i] ){
        rc = sqlitePgGet(pDb->pPgr, aPage[i], &aData);
      }else{
        rc = allocPage(pDb, &aPage[i], &aData);
      }
      if( rc!=SQLITE_OK ) return rc;
      if( amt+base > SQLITE_PAGE_SIZE ){
        tomove = SQLITE_PAGE_SIZE - base;
      }else{
        tomove = amt;
      }
      memcpy(&aData[base], pBuf, tomove);
      sqlitePgTouch(aData);
      sqlitePgUnref(aData);
      pBuf = &((char*)pBuf)[tomove];
      amt -= tomove;
    }
    if( amt<=0 ) return SQLITE_OK;
  }
  offset -= N_DIRECT*SQLITE_PAGE_SIZE;
  aPage += N_DIRECT;

  /* Indirect overflow pages
  */
  if( offset < U32_PER_PAGE*SQLITE_PAGE_SIZE ){
    u32 *indirPage;
    if( aPage[0] ){
      rc = sqlitePgGet(pDb->pPgr, aPage[0], &indirPage);
    }else{
      rc = allocPage(pDb, &aPage[0], &indirPage);
    }
    if( rc!=SQLITE_OK ) return rc;
    for(i=offset/SQLITE_PAGE_SIZE; i<U32_PER_PAGE && amt>0; i++){
      int base;
      char *aData;
      base = offset - i*SQLITE_PAGE_SIZE;
      if( indirPage[i] ){
        rc = sqlitePgGet(pDb->pPgr, indirPage[i], &aData);
      }else{
        rc = allocPage(pDb, &indirPage[i], &aData);
        sqlitePgTouch(indirPage);
      }
      if( rc!=SQLITE_OK ) break;
      if( amt+base > SQLITE_PAGE_SIZE ){
        tomove = SQLITE_PAGE_SIZE - base;
      }else{
        tomove = amt;
      }
      memcpy(&aData[base], pBuf, tomove);
      sqlitePgUnref(aData);
      pBuf = &((char*)pBuf)[tomove];
      amt -= tomove;
    }
    sqlitePgUnref(indirPage);
    if( rc!=SQLITE_OK ) return rc;
    if( amt<=0 ) return SQLITE_OK;
  }
  offset -= U32_PER_PAGE*SQLITE_PAGE_SIZE;
  aPage++;

  /* Double-indirect overflow pages
  */
  if( offset < U32_PER_PAGE*U32_PER_PAGE*SQLITE_PAGE_SIZE ){
    u32 *dblIndirPage;
    if( aPage[0] ){
      rc = sqlitePgGet(pDb->pPgr, aPage[0], &dblIndirPage);
    }else{
      rc = allocPage(pDb, &aPage[0], &dblIndirPage);
    }
    if( rc!=SQLITE_OK ) return rc;
    i = offset/(U32_PER_PAGE*SQLITE_PAGE_SIZE);
    for(; i<U32_PER_PAGE && amt>0; i++){
      u32 *indirPage;
      int basis;
      int j;
      if( aPage[0] ){
        rc = sqlitePgGet(pDb->pPgr, aPage[0], &dblIndirPage);
      }else{
        rc = allocPage(pDb, &aPage[0], &dblIndirPage);
        sqlitePgTouch(dblIndirPage);
      }
      rc = sqlitePgGet(pDb->pPgr, dblIndirPage[i], &indirPage);
      if( rc!=SQLITE_OK ) break;
      basis = i*U32_PER_PAGE*SQLITE_PAGE_SIZE;
      j = (offset - basis)/SQLITE_PAGE_SIZE;
      for(; j<U32_PER_PAGE && amt>0; j++){
        char *aData;
        base = (offset - basis) - ij*SQLITE_PAGE_SIZE;
        if( indirPage[j] ){
          rc = sqlitePgGet(pDb->pPgr, indirPage[j], &aData);
        }else{
          rc = allocPage(pDb, &indirPage[j], &aData);
          sqlitePgTouch(indirPage);
        }
        if( rc!=SQLITE_OK ) break;
        if( amt+base > SQLITE_PAGE_SIZE ){
          tomove = SQLITE_PAGE_SIZE - base;

        }else{
          tomove = amt;

        }
        memcpy(&aData[base], pBuf, tomove);
        sqlitePgTouch(aData);
        sqlitePgUnref(aData);

        pBuf = &((char*)pBuf)[tomove];
        amt -= tomove;

      }

      sqlitePgUnref(indirPage);
      if( rc!=SQLITE_OK ) break;
    }
    sqlitePgUnref(dblIndirPage);
  }

  return SQLITE_OK;
}

/*
** Release any and all overflow pages associated with data starting

** with byte "newSize".  oldSize is the amount of payload before doing
** the free operation.
*/
static int payloadFree(Db *pDb, u32 *aPage, int newSize, int oldSize){

  int i, j;          /* Loop counters */
  int first, last;   /* Indices of first and last pages to be freed */
  int rc;            /* Return code from sqlitePgGet() */

  /* Skip over the local data.  We do not need to free it.
  */
  if( newSize>=oldSize ) return SQLITE_OK;
  oldSize -= LOCAL_PAYLOAD;
  if( oldSize<=0 ) return SQLITE_OK;
  newSize -= LOCAL_PAYLOAD;

  aPage += LOCAL_PAYLOAD/sizeof(u32);

  /* Compute the indices of the first and last overflow pages to
  ** be freed.
  */
  first = (newSize - 1)/SQLITE_PAGE_SIZE + 1;
  last = (oldSize - 1)/SQLITE_PAGE_SIZE;

  /* Free the direct overflow pages
  */
  if( first < N_DIRECT ){
    for(i=first; i<N_DIRECT && i<=last; i++){
      freePage(pDb, aPage[i], 0);

      aPage[i] = 0;
    }
  }
  aPage += N_DIRECT;
  first -= N_DIRECT;
  last -= N_DIRECT;
  if( last<0 ) return SQLITE_OK;

  if( first<0 ) first = 0;
  
  /* Free indirect overflow pages
  */
  if( first < U32_PER_PAGE ){
    u32 *indirPage;
    rc = sqlitePgGet(pDb->pPgr, aPage[0], &indirPage);
    if( rc!=SQLITE_OK ) return rc;
    for(i=first; i<U32_PER_PAGE && i<=last; i++){

      freePage(pDb, indirPage[i], 0);
      indirPage[i] = 0;
      touch = 1;
    }
    if( first<=0 ){
      freepage(pDb, aPage[0], indirPage);
      aPage[0] = 0;
    }else{
      sqlitePgTouch(indirPage);
      sqlitePgUnref(indirPage);
    }
  }
  aPage++;
  first -= U32_PER_PAGE;
  last -= U32_PER_PAGE;
  if( last<0 ) return SQLITE_OK;

  if( first<0 ) first = 0;

  /* Free double-indirect overflow pages
  */
  if( first < U32_PER_PAGE*U32_PER_PAGE ){
    u32 *dblIndirPage;
    rc = sqlitePgGet(pDb->pPgr, aPage[0], &dblIndirPage);
    if( rc!=SQLITE_OK ) return rc;
    for(i=first/U32_PER_PAGE; i<U32_PER_PAGE; i++){

      u32 *indirPage;
      basis = i*U32_PER_PAGE;
      if( last < basis ) break;
      rc = sqlitePgGet(pDb->pPgr, dblIndirPage[i], &indirPage);
      if( rc!=SQLITE_OK ) return rc;
      for(j=first>basis?first-basis:0 ; j<U32_PER_PAGE; j++){
        if( j + basis > last ) break;
        freePage(pDb, indirPage[j], 0);
        indirPage[j] = 0;

      }
      if( first<=basis ){
        freepage(pDb, dblIndirPage[i], 0);
        dblIndirPage[i] = 0;
      }else{
        sqlitePgTouch(indirPage);
        sqlitePgUnref(indirPage);
      }
    }
    if( first<=0 ){
      freepage(pDb, aPage[0], dblIndirPage);
      aPage[0] = 0;
    }else{
      sqlitePgTouch(dblIndirPage);
      sqlitePgUnref(dblIndirPage);
    }
  }

  return SQLITE_OK;    
}

/*
** Allocate space for the content table in the given Db structure.
** return SQLITE_OK on success and SQLITE_NOMEM if it fails.
*/
................................................................................
    pDb->nAlloc = 0;
    pDb->inTranaction = 0;
    return SQLITE_NOMEM;
  }
  return SQLITE_OK;
}









































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

  rc = allocPage(pDb, &pgno, &pPage);
  if( rc!=SQLITE_OK ){
    return rc;
  }
  tblno = -1;
  for(i=2; i<pDb->nContent; i++){
    if( pDb->aContent[i]==0 ){
      tblno = i - 2;
................................................................................
*/
static int sqliteDbDropPage(Db *pDb, u32 pgno){
  u32 *aPage;
  int rc;

  rc = sqlitePgGet(pDb->pPgr, pgno, (void**)&aPage);
  if( rc!=SQLITE_OK ) return rc;
  switch(  aPage[0] ){
    case BLOCK_MAGIC | BLOCK_INDEX: {
      int n, i;
      n = aPage[2];
      for(i=0; i<n; i++){
        u32 subpgno = aPage[3+i*2];
        sqliteDbDropPage(pDb, subpgno);
      }
      freePage(pDb, pgno, aPage);
      break;
    }
    case BLOCK_MAGIC | BLOCK_LEAF: {
      int i = 1;
      while( i<SQLITE_PAGE_SIZE/sizeof(u32) ){
        int entrySize = SWB(aPage[i]);
        if( entrySize==0 ) break;
        sqliteDbClearEntry(pDb, &aPage[i]);
        i += entrySize;
      }
      freePage(pDb, pgno, aPage);











      break;
    }
    default: {
      /* Do nothing */
      break;
    }
  }
................................................................................

/*
** aEntry points directly at a database entry on a leaf page.
** Free any overflow pages associated with the key or data of
** this entry.
*/
static int sqliteDbClearEntry(Db *pDb, u32 *aEntry){















  return SQLITE_OK;
}

/*
** Delete the current associate of a cursor and release all the
** pages it holds.  Except, do not release pages at levels less
** than N.
................................................................................
    aPage[i+2] = SWB(nKey);
    memcpy(&aPage[i+4], pKey, nKey);
    j = i + 4 + nKeyU;
    available -= nKeyU;
  }else{
    u32 newPgno, *newPage;
    aPage[i+2] = SWB(nKey | 0x80000000);
    rc = allocPage(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;
................................................................................
    aPage[i+3] = SWB(nData);
    memcpy(&aPage[j], pData, nData);
    available -= nDataU;
    j += nDataU;
  }else{
    u32 newPgno, *newPage;
    aPage[i+3] = SWB(nData | 0x80000000);
    rc = allocPage(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++;

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

typedef struct Db Db;
typedef struct DbCursor DbCursor;

int sqliteDbOpen(const char *filename, Db**);
int sqliteDbClose(Db*);
................................................................................
int sqliteDbCursorOpen(Db*, int tblno, DbCursor**);
int sqliteDbCursorClose(DbCursor*);

int sqliteDbCursorFirst(DbCursor*);
int sqliteDbCursorNext(DbCursor*);
int sqliteDbCursorDatasize(DbCursor*);
int sqliteDbCursorKeysize(DbCursor*);
int sqliteDbCursorRead(DbCursor*, int amt, int offset, char *buf);
int sqliteDbCursorReadKey(DbCursor*, int amt, int offset, char *buf);
int sqliteDbCursorMoveTo(DbCursor*, int nKey, void *pKey);
int sqliteDbCursorDelete(DbCursor*);
int sqliteDbCursorInsert(DbCursor*, int nKey, void *pKey, int nData, void *pD);

int sqliteDbReorganize(Db*);

** Boston, MA  02111-1307, USA.
**
** Author contact information:
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** $Id: db.h,v 1.3 2001/01/25 01:45:40 drh Exp $
*/

typedef struct Db Db;
typedef struct DbCursor DbCursor;

int sqliteDbOpen(const char *filename, Db**);
int sqliteDbClose(Db*);
................................................................................
int sqliteDbCursorOpen(Db*, int tblno, DbCursor**);
int sqliteDbCursorClose(DbCursor*);

int sqliteDbCursorFirst(DbCursor*);
int sqliteDbCursorNext(DbCursor*);
int sqliteDbCursorDatasize(DbCursor*);
int sqliteDbCursorKeysize(DbCursor*);
int sqliteDbCursorRead(DbCursor*, int amt, int offset, void *buf);
int sqliteDbCursorReadKey(DbCursor*, int amt, int offset, void *buf);
int sqliteDbCursorFind(DbCursor*, int nKey, const void *pKey, int createSize);
int sqliteDbCursorResize(DbCursor*, int nData);
int sqliteDbCursorWrite(DbCursor*, int amt, int offset, const void *buf);

** 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"
................................................................................
** Look in the journal to see if the given database page is stored
** in the journal.  If it is, return its journal page number.  If
** not, return 0.
*/
static u32 sqlitePgJournalPageNumber(Pgr *p, u32 dbpgno){
  u32 jpgno;
  
  assert( dbpgno>0 );
  jpgno = p->aJHash[dbpgno % J_HASH_SIZE];
  while( jpgno!=0 ){
    int idx_num;     /* Which journal index describes page jpgno */
    int ipgno;       /* Page number for the journal index */
    int idx_slot;    /* Which entry in index idx_num describes jpgno */
    Pghdr *pIdxPg;   /* The index page for jpgno */
    JidxEntry *aIdx; /* The data for the index page */
................................................................................
    pPg->pNxHash->pPvHash = pPg;
  }
  p->aPgHash[h] = pPg;
  pPg->jpgno = sqlitePgJournalPageNumber(p, pgno);
  if( pPg->jpgno!=0 ){
    TRACE(("PG: reading d-page %u content from j-page %u\n", pgno, pPg->jpgno));
    sqlitePgRead(p->fdJournal, PG_TO_DATA(pPg), pPg->jpgno);
  }else{
    TRACE(("PG: reading d-page %u from database\n", pgno));
    sqlitePgRead(p->fdMain, PG_TO_DATA(pPg), pPg->dbpgno);



  }
  pPg->isDirty = 0;
  pPg->nRef = 1;
  p->nRefPg++;
  if( p->nRefPg==1 ){
    /* Acquire a read lock */
  }
................................................................................
  return SQLITE_OK;
}

/*
** Return the number of the first unused page at the end of the
** database file.
*/
int sqlitePgAlloc(Pgr *p, u32 *pPgno){
  *pPgno = p->nDbPg;
  return SQLITE_OK;
}

/*
** Return the page number associated with the given page.
*/
u32 sqlitePgNum(void *pD){
  Pghdr *pPg = DATA_TO_PG(pD);
  return pPg->dbpgno;
}

** Boston, MA  02111-1307, USA.
**
** Author contact information:
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** $Id: pg.c,v 1.4 2001/01/25 01:45:41 drh Exp $
*/
#include <assert.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include "sqliteInt.h"
................................................................................
** Look in the journal to see if the given database page is stored
** in the journal.  If it is, return its journal page number.  If
** not, return 0.
*/
static u32 sqlitePgJournalPageNumber(Pgr *p, u32 dbpgno){
  u32 jpgno;
  
  if( dbpgno==0 ) return 0;
  jpgno = p->aJHash[dbpgno % J_HASH_SIZE];
  while( jpgno!=0 ){
    int idx_num;     /* Which journal index describes page jpgno */
    int ipgno;       /* Page number for the journal index */
    int idx_slot;    /* Which entry in index idx_num describes jpgno */
    Pghdr *pIdxPg;   /* The index page for jpgno */
    JidxEntry *aIdx; /* The data for the index page */
................................................................................
    pPg->pNxHash->pPvHash = pPg;
  }
  p->aPgHash[h] = pPg;
  pPg->jpgno = sqlitePgJournalPageNumber(p, pgno);
  if( pPg->jpgno!=0 ){
    TRACE(("PG: reading d-page %u content from j-page %u\n", pgno, pPg->jpgno));
    sqlitePgRead(p->fdJournal, PG_TO_DATA(pPg), pPg->jpgno);
  }else if( pPg->dbpgno!=0 ){
    TRACE(("PG: reading d-page %u from database\n", pgno));
    sqlitePgRead(p->fdMain, PG_TO_DATA(pPg), pPg->dbpgno);
  }else{
    TRACE(("PG: reading zero page\n");
    memset(PG_TO_DATA(pPg), 0, SQLITE_PAGE_SIZE);
  }
  pPg->isDirty = 0;
  pPg->nRef = 1;
  p->nRefPg++;
  if( p->nRefPg==1 ){
    /* Acquire a read lock */
  }
................................................................................
  return SQLITE_OK;
}

/*
** Return the number of the first unused page at the end of the
** database file.
*/
int sqlitePgCount(Pgr *p, u32 *pPgno){
  *pPgno = p->nDbPg;
  return SQLITE_OK;
}

/*
** Return the page number associated with the given page.
*/
u32 sqlitePgNum(void *pD){
  Pghdr *pPg = DATA_TO_PG(pD);
  return pPg->dbpgno;
}