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

/*
** Everything we need to know about an open database
*/
struct Db {
  Pgr *pPgr;            /* The pager for the database */
  DbCursor *pCursor;    /* All open cursors */
  int inTransaction;    /* True if a transaction is in progress */
  int nContents;        /* Number of slots in aContents[] */
  int nAlloc;           /* Space allocated for aContents[] */
  u32 *aContents;       /* Contents table for the database */
};

/*
** The maximum depth of a cursor
*/
#define MX_LEVEL 10

................................................................................
** 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 */
................................................................................
  u32 rootPgno;                 /* Root page of table for this cursor */
  int onEntry;                  /* True if pointing to a table entry */
  int nLevel;                   /* Number of levels of indexing used */
  DbIdxpt aLevel[MX_LEVEL];     /* The index levels */
};

/*
** Used for rebalancing
*/
typedef struct DbEntry DbEntry;




struct DbEntry {
  int nByte;      /* Space needed on leaf to record this entry */
  int pgno;       /* Page on which this entry is currently found */
  int idx;        /* Index slot in part that points to leaf "pgno" */
  u32 *aPage;     /* Pointer to the leaf for this entry */
  u32 *aEntry;    /* Pointer to the actual text of this entry */
  DbEntry *pNext; /* Next entry in a list of them all */
};

typedef struct DbEntrySet DbEntrySet;
struct DbEntrySet {
  u32 *pIndex;         /* The index node above the leaf pages being balanced */
  int nAlloc;          /* Number of slots allocated in aEntry[] */
  int nEntry;          /* Number of slots in aEntry[] actually used */
  DbEntry *pFirst;     /* First entry in hash order */
  DbEntry aEntry[100]; /* Descriptions of actual database entries */
};













/*
** The first word of every page is some combination of these values
** used to indicate its function.
*/
#define BLOCK_MAGIC            0x24e47190

#define BLOCK_INDEX            0x00000001
#define BLOCK_LEAF             0x00000002
#define BLOCK_FREE             0x00000003
#define BLOCK_OVERFLOW         0x00000004
#define BLOCK_CONTENTS         0x00000005
#define BLOCK_MAGIC_MASK       0xfffffff8
#define BLOCK_TYPE_MASK        0x00000007

/*
** Free blocks:
**
**     0.   BLOCK_MAGIC | BLOCK_FREE
**     1.   address of next block on freelist
**
** Leaf blocks:
**
**     0.   BLOCK_MAGIC | BLOCK_LEAF 
**     1.   number of table entries  (only used if a table root block)
**     entries....
**         0.  size of this entry (measured in u32's)
**         1.  hash
**         2.  keysize  (in bytes)
**         3.  datasize (in bytes)
**         4.  payload
**
** Payload area:
**
**     *   up to LOCAL_PAYLOAD bytes of data
**     *   10 page number of direct blocks
**     *   1 indirect block
**     *   1 double-indirect block
**
** Index block:
**
**     0.   BLOCK_MAGIC | BLOCK_INDEX
**     1.   number of table entries  (only used if a table root block)
**     2.   entries in this index block
**     entries...
**         0.  largest hash value for pgno
**         1.  pgno of subblock
**
** Contents block:  (The first page in the file)
**     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 &&
................................................................................
  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.
................................................................................
    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;
................................................................................
  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.
*/
static int sqliteDbExpandContent(Db *pDb, int newSize){
  if( pDb->nAlloc>=newSize ) return SQLITE_OK;
  pDb->nAlloc = newSize;
  pDb->aContent = sqliteRealloc( pDb->aContent, pDb->nAlloc*sizeof(u32));
  if( pDb->aContent==0 ){
    pDb->nContent = 0;
    pDb->nAlloc = 0;
    pDb->inTranaction = 0;
    return SQLITE_NOMEM;
  }
  return SQLITE_OK;
}

/*
................................................................................
  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] = BLOCK_MAGIC|BLOCK_CONTENT;
    aPage1[2] = sizeof(u32)*10;
    sqlitePgTouch(aPage1);
    sqlitePgCommit(pDb->pPgr);
  }
  pDb->nContent = aPage1[2]/sizeof(u32);
  pDb->nAlloc = 0;
  rc = sqliteDbExpandContent(pDb, pDb->nContent);
  if( rc!=SQLITE_OK ) goto open_err;
  rc = payloadRead(pDb, &aPage1[3], 0, aPage1[2], pDb->aContent);
  sqlitePgUnref(aPage1);
  if( rc!=SQLITE_OK ) goto open_err;
  *ppDb = pDb;
  return SQLITE_OK;

open_err:
  *ppDb = 0;
................................................................................
  u32 *aPage1;
  int rc;
  if( !pDb->inTransaction ){
    return SQLITE_OK;
  }
  rc = sqlitePgGet(pDb->pPgr, 1, &aPage1);
  if( rc!=SQLITE_OK ) return rc;
  aPage1[2] = pDb->nContent*sizeof(u32);
  payloadWrite(pDb, 0, aPage1[2], pDb->aContent);

  sqlitePgUnref(aPage1);
  rc = sqlitePgCommit(pDb->pPgr);
  if( rc!=SQLITE_OK ) return rc;
  pDb->inTransaction = 0;
  return SQLITE_OK;
}

................................................................................
int sqliteDbRollback(Db *pDb){
  u32 *aPage1;
  if( !pDb->inTransaction ) return SQLITE_OK;
  rc = sqlitePgRollback(pDb->pPgr);
  if( rc!=SQLITE_OK ) return rc;
  rc = sqlitePgGet(pDb->pPgr, 1, &aPage1);
  if( rc!=SQLITE_OK ) return rc;
  pDb->nContent = SWB(aPage1[3]) + 2;
  if( sqliteDbExpandContent(pDb, pDb->nContent)!=SQLITE_OK ){

    return SQLITE_NOMEM;
  }
  payloadRead(pDb, &aPage1[3], 0, pDb->nContent*sizeof(u32), pDb->aContent);

  pDb->inTransaction = 0;
  return SQLITE_OK;
}

/*
** Create a new table in the database.  Write the table number
** that is used to open a cursor into that table into *pTblno.
*/
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;
      break;
    }
  }
  if( tblno<0 ){
    tblno = pDb->aContent[1];



  }
  if( tblno+2 >= pDb->nContent ){
    sqliteDbExpandContent(pDb, tblno+2);
  }
  if( pDb->aContent==0 ){
    rc = SQLITE_NOMEM;
  }else{
    pDb->aContent[tblno+2] = pgno;
    pPage[0] = SWB(BLOCK_MAGIC | BLOCK_LEAF);
    memset(&pPage[1], 0, SQLITE_PAGE_SIZE - sizeof(u32));
    sqlitePgTouch(pPage);
  }
  sqlitePgUnref(pPage);
  return rc;
}

/*
** Recursively add a page to the free list
*/
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[4+i*2];
        if( subpgno>0 ) sqliteDbDropPage(pDb, subpgno);
      }
      freePage(pDb, pgno, aPage);
      break;
    }
    case BLOCK_MAGIC | BLOCK_LEAF: {
      int i = 2;
      while( i<U32_PER_PAGE ){
        int entrySize = aPage[i];
        if( entrySize==0 ) break;
        payloadFree(pDb, &aPage[i+4], 0, aPage[i+2]+aPage[i+3]);
        i += entrySize;
      }
      freePage(pDb, pgno, aPage);
      break;
    }
    default: {
      /* Do nothing */
................................................................................
*/
static int sqliteDbDropTable(Db *pDb, int tblno){
  DbCursor *pCur;
  u32 pgno;

  /* Find the root page for the table to be dropped.
  */
  if( pDb->aContent==0 ){
    return SQLITE_NOMEM;
  }
  if( tblno<0 || tblno+2>=pDb->nContent || pDb->aContent[tblno+2]==0 ){
    return SQLITE_NOTFOUND;
  }
  pgno = pDb->aContent[tblno+2];
  pDb->aContent[tblno+2] = 0;




  /* Reset any cursors pointing to the table that is about to
  ** be dropped */
  for(pCur=pDb->pCursor; pCur; pCur=pCur->pNext){
    if( pCur->rootPgno==pgno ){
      sqliteDbResetCursor(pCur, 0);
    }
................................................................................
*/
int sqliteDbCursorOpen(Db *pDb, int tblno, DbCursor **ppCur){
  u32 pgno;
  DbCursor *pCur;

  /* Translate the table number into a page number
  */
  if( pDb->aContent==0 ){
    *ppCur = 0;
    return SQLITE_NOMEM;
  }
  if( tblno<0 || tblno+2>=pDb->nContent || pDb->aContent[tblno+2]==0 ){
    *ppCur = 0;
    return SQLITE_NOTFOUND;
  }
  pgno = SWB(pDb->aContent[tblno+2]);
  
  /* Allocate the cursor
  */
  pCur = sqliteMalloc( sizeof(*pCur) );
  pCur->pgno = pgno;
  pCur->pDb = pDb;
  pCur->pNext = pDb->pCursor;
................................................................................
  if( pCur->nLevel > i+1 ){
    sqliteDbResetCursor(pCur, i+1);
  }
  assert( pCur->nLevel==i+1 );
  while( rc < 0 ){
    u32 *aPage = pCur->aLevel[i].aPage;
    assert( aPage!=0 );
    switch( SWB(aPage[0]) ){
      case BLOCK_LEAF | BLOCK_MAGIC: {
        if( aPage[1]!=0 ){
          pCur->aLevel[i].idx = 1;
          pCur->onEntry = 1;
        }else{
          sqliteDbResetCursor(pCur, 1);
        }
        rc = SQLITE_OK;
        break;
      }
      case BLOCK_INDEX | BLOCK_MAGIC: {
        int n = SWB(aPage[2]);
        if( n<2 || n>=((SQLITE_PAGE_SIZE/sizeof(u32))-3)/2 ){
          sqliteDbResetCur(pCur, 1);
          rc = SQLITE_CORRUPT;
          break;
        }
        pCur->nLevel++;
        i++;
        pCur->aLevel[i].pgno = SWB(aPage[4]);
        rc = sqlitePgGet(pCur->pDb->pPgr, pCur->aLevel[i].pgno,
                    &pCur->aLevel[i].aPage);
        if( rc != SQLITE_OK ){
          sqliteDbResetCursor(pCur, 1);
        }else{
          rc = -1;
        }
................................................................................
        sqliteDbResetCursor(pCur, 1);
        rc = SQLITE_CORRUPT;
      }
    }
  }
  return rc;
}



/*
** Move the cursor to the first entry in the table.
*/
int sqliteDbCursorFirst(DbCursor *pCur){
  if( pCur->nLevel==0 ){
    int rc;

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

/*
** Everything we need to know about an open database
*/
struct Db {
  Pgr *pPgr;            /* The pager for the database */
  DbCursor *pCursor;    /* All open cursors */
  int inTransaction;    /* True if a transaction is in progress */
  u32 freeList;         /* List of free blocks */
  int nTable;           /* Number of slots in aContent[] */
  u32 *aTable;          /* Root page numbers for all tables */
};

/*
** The maximum depth of a cursor
*/
#define MX_LEVEL 10

................................................................................
** 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 */
................................................................................
  u32 rootPgno;                 /* Root page of table for this cursor */
  int onEntry;                  /* True if pointing to a table entry */
  int nLevel;                   /* Number of levels of indexing used */
  DbIdxpt aLevel[MX_LEVEL];     /* The index levels */
};

/*
** Data layouts
**
** LEAF:
**    x[0]          Magic number: BLOCK_LEAF
**    x[1]          If root page, total number of entries in this table
**    ...           One or more entries follow the leaf.
**
** Entry:




**    x[N+0]        Number of u32-sized words in this entry
**    x[N+1]        Hash value for this entry

**    x[N+2]        Number of bytes of key in the payload
**    x[N+3]        Number of bytes of data in the payload
**    x{N+4]...     The payload area.
**
** INDEX:
**    x[0]          Magic number: BLOCK_INDEX
**    x[1]          If root page: total number of entries in this table
**    x[2]          Number of slots in this index (Max value of N)

**    x[2*N+3]      Page number containing entries with hash <= x[2*N+4]
**    x[2*N+4]      The maximum hash value for entries on page x[2*N+3].
**
** FREE:
**    x[0]          Magic number: BLOCK_FREE
**    x[1]          Page number of the next free block on the free list
**
** PAGE1:
**    x[0]          Magic number: BLOCK_PAGE1
**    x[1]          First page of the freelist
**    x[2]          Number of tables in this database
**    x[N+3]        Root page for table N

/*
** The first word of every page is some combination of these values
** used to indicate its function.
*/

#define BLOCK_PAGE1            0x24e47191
#define BLOCK_INDEX            0x7ac53b46
#define BLOCK_LEAF             0x60c45eef
#define BLOCK_FREE             0x5b2dda47














































/*
** 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 (in bytes) that will fit on on the same
** page as a leaf.  In other words, the maximum amount of payload
** that does not require any overflow pages.
**
** This size is chosen so that a least 3 entry will fit on every 
** leaf.  That guarantees it will always be possible to add a new
** entry after a page split.
*/

#define LOCAL_PAYLOAD (((U32_PER_PAGE-2)/3 - (6+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.
**
** The page is obtained from the freelist if there is anything there.
** If the freelist is empty, the new page comes from the end of the
** database file.
*/
int allocPage(Db *pDb, u32 *pPgno, u32 **ppPage){
  u32 pgno;
  int rc;

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

  /* Try to reuse a page from the freelist
  */
  if( pDb->freeList==0 ){
    u32 *pPage;
    rc = sqlitePgGet(pDb->pPgr, pDb->freeList, &pPage);
    if( rc==SQLITE_OK ){
      if( pPage[0]==BLOCK_FREE ){
        *pPgno = pDb->freeList;
        *ppPage = aPage;
        pDb->freeList = aPage[1];
        memset(*ppPage, 0, SQLITE_PAGE_SIZE);
        return SQLITE_OK;
      }
      /* This only happens if we have database corruption */
      sqlitePgUnref(pPage);
    }
  }

  /* 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 &&
................................................................................
  return rc;
}

/*
** Return a page to the freelist and dereference the page.
*/
static void freePage(DB *pDb, u32 pgno, u32 *aPage){

  if( pgno==0 ) return
  if( aPage==0 ){
    int rc;
    rc = sqlitePgGet(pDb->pPgr, pgno, &aPage);
    if( rc!=SQLITE_OK ) return;
  }
  assert( sqlitePgNum(aPage)==pgno );
  aPage[0] = BLOCK_FREE;
  aPage[1] = pDb->freeList;
  pDb->freeList = pgno;
  memset(&aPage[2], 0, SQLITE_PAGE_SIZE - 2*sizeof(u32));

  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.
................................................................................
    sqlitePgUnref(dblIndirPage);
  }

  return SQLITE_OK;
}

/*
** Resize the payload area.  If the payload area descreases in size,
** this routine deallocates unused overflow pages.  If the payload
** area increases in size, this routine is a no-op.
*/
static int payloadResize(Db *pDb, u32 *aPage, int oldSize, int newSize){
  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;
................................................................................
  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.
*/
static int sqliteDbExpandTableArray(Db *pDb){
  pDb->aTable = sqliteRealloc( pDb->aTable, pDb->nTable*sizeof(u32));


  if( pDb->aTable==0 ){


    pDb->inTranaction = 0;
    return SQLITE_NOMEM;
  }
  return SQLITE_OK;
}

/*
................................................................................
  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] = BLOCK_PAGE1;

    sqlitePgTouch(aPage1);
    sqlitePgCommit(pDb->pPgr);
  }
  pDb->freeList = aPage[1];
  pDb->nTable = aPage[2];
  rc = sqliteDbExpandTableArray(pDb);
  if( rc!=SQLITE_OK ) goto open_err;
  rc = payloadRead(pDb, &aPage1[3], 0, pDb->nTable*sizeof(u32), pDb->aTable);
  sqlitePgUnref(aPage1);
  if( rc!=SQLITE_OK ) goto open_err;
  *ppDb = pDb;
  return SQLITE_OK;

open_err:
  *ppDb = 0;
................................................................................
  u32 *aPage1;
  int rc;
  if( !pDb->inTransaction ){
    return SQLITE_OK;
  }
  rc = sqlitePgGet(pDb->pPgr, 1, &aPage1);
  if( rc!=SQLITE_OK ) return rc;
  aPage1[1] = pDb->freeList;
  aPage1[2] = pDb->nTable;
  payloadWrite(pDb, &aPage1[3], 0, pDb->nTable*sizeof(u32), pDb->aTable);
  sqlitePgUnref(aPage1);
  rc = sqlitePgCommit(pDb->pPgr);
  if( rc!=SQLITE_OK ) return rc;
  pDb->inTransaction = 0;
  return SQLITE_OK;
}

................................................................................
int sqliteDbRollback(Db *pDb){
  u32 *aPage1;
  if( !pDb->inTransaction ) return SQLITE_OK;
  rc = sqlitePgRollback(pDb->pPgr);
  if( rc!=SQLITE_OK ) return rc;
  rc = sqlitePgGet(pDb->pPgr, 1, &aPage1);
  if( rc!=SQLITE_OK ) return rc;
  pDb->freeList = aPage1[1];
  pDb->nTable = aPage1[2];
  if( sqliteDbExpandTableArray(pDb)!=SQLITE_OK ){
    return SQLITE_NOMEM;
  }
  payloadRead(pDb, &aPage1[3], 0, pDb->nTable*sizeof(u32), pDb->aTable);
  sqlitePgUnref(aPage1);
  pDb->inTransaction = 0;
  return SQLITE_OK;
}

/*
** Create a new table in the database.  Write the table number
** that is used to open a cursor into that table into *pTblno.
*/
int sqliteDbCreateTable(Db *pDb, int *pTblno){
  u32 *aPage;
  u32 pgno;
  int rc;
  int swTblno;
  int i;

  rc = allocPage(pDb, &pgno, &aPage);
  if( rc!=SQLITE_OK ){
    return rc;
  }
  tblno = -1;
  for(i=0; i<pDb->nTable; i++){
    if( pDb->aTable[i]==0 ){
      tblno = i;
      break;
    }
  }
  if( tblno<0 ){
    pDb->nTable++;
    rc = sqliteExpandTableArray(pDb);
    if( rc!=SQLITE_OK ){
      return rc;
    }


  }

  pDb->aTable[tblno] = pgno;
  aPage[0] = BLOCK_LEAF;


  memset(&aPage[1], 0, SQLITE_PAGE_SIZE - sizeof(u32));
  sqlitePgTouch(aPage);

  sqlitePgUnref(aPage);
  return rc;
}

/*
** Recursively add a page to the free list
*/
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_INDEX: {
      int n, i;
      n = aPage[2];
      for(i=0; i<n; i++){
        u32 subpgno = aPage[3 + i*2];
        if( subpgno>0 ) sqliteDbDropPage(pDb, subpgno);
      }
      freePage(pDb, pgno, aPage);
      break;
    }
    case BLOCK_LEAF: {
      int i = 2;
      while( i<U32_PER_PAGE ){
        int entrySize = aPage[i];
        if( entrySize==0 ) break;
        payloadResize(pDb, &aPage[i+4], aPage[i+2]+aPage[i+3], 0);
        i += entrySize;
      }
      freePage(pDb, pgno, aPage);
      break;
    }
    default: {
      /* Do nothing */
................................................................................
*/
static int sqliteDbDropTable(Db *pDb, int tblno){
  DbCursor *pCur;
  u32 pgno;

  /* Find the root page for the table to be dropped.
  */
  if( pDb->aTable==0 ){
    return SQLITE_NOMEM;
  }
  if( tblno<0 || tblno>=pDb->nTable || pDb->aTable[tblno]==0 ){
    return SQLITE_NOTFOUND;
  }
  pgno = pDb->aTable[tblno];
  pDb->aTable[tblno] = 0;
  if( tblno==pDb->nTable-1 ){
    pDb->nTable--;
  }

  /* Reset any cursors pointing to the table that is about to
  ** be dropped */
  for(pCur=pDb->pCursor; pCur; pCur=pCur->pNext){
    if( pCur->rootPgno==pgno ){
      sqliteDbResetCursor(pCur, 0);
    }
................................................................................
*/
int sqliteDbCursorOpen(Db *pDb, int tblno, DbCursor **ppCur){
  u32 pgno;
  DbCursor *pCur;

  /* Translate the table number into a page number
  */
  if( pDb->aTable==0 ){
    *ppCur = 0;
    return SQLITE_NOMEM;
  }
  if( tblno<0 || tblno>=pDb->nContent || pDb->aTable[tblno]==0 ){
    *ppCur = 0;
    return SQLITE_NOTFOUND;
  }
  pgno = pDb->aTable[tblno];
  
  /* Allocate the cursor
  */
  pCur = sqliteMalloc( sizeof(*pCur) );
  pCur->pgno = pgno;
  pCur->pDb = pDb;
  pCur->pNext = pDb->pCursor;
................................................................................
  if( pCur->nLevel > i+1 ){
    sqliteDbResetCursor(pCur, i+1);
  }
  assert( pCur->nLevel==i+1 );
  while( rc < 0 ){
    u32 *aPage = pCur->aLevel[i].aPage;
    assert( aPage!=0 );
    switch( aPage[0] ){
      case BLOCK_LEAF: {
        if( aPage[2]!=0 ){
          pCur->aLevel[i].idx = 2;
          pCur->onEntry = 1;
        }else{
          sqliteDbResetCursor(pCur, 1);
        }
        rc = SQLITE_OK;
        break;
      }
      case BLOCK_INDEX: {
        int n = aPage[2];
        if( n<2 || n>=((U32_PER_PAGE - 3)/2) ){
          sqliteDbResetCur(pCur, 1);
          rc = SQLITE_CORRUPT;
          break;
        }
        pCur->nLevel++;
        i++;
        pCur->aLevel[i].pgno = aPage[3];
        rc = sqlitePgGet(pCur->pDb->pPgr, pCur->aLevel[i].pgno,
                    &pCur->aLevel[i].aPage);
        if( rc != SQLITE_OK ){
          sqliteDbResetCursor(pCur, 1);
        }else{
          rc = -1;
        }
................................................................................
        sqliteDbResetCursor(pCur, 1);
        rc = SQLITE_CORRUPT;
      }
    }
  }
  return rc;
}

################

/*
** Move the cursor to the first entry in the table.
*/
int sqliteDbCursorFirst(DbCursor *pCur){
  if( pCur->nLevel==0 ){
    int rc;

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

typedef struct Db Db;
typedef struct DbCursor DbCursor;

int sqliteDbOpen(const char *filename, Db**);
int sqliteDbClose(Db*);
................................................................................
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 sqliteDbCursorWrite(DbCursor*, int amt, int offset, const void *buf);

int sqliteDbCursorFind(DbCursor*, int nKey, const void *pKey, int createSize);
int sqliteDbCursorResize(DbCursor*, int nData);

** Boston, MA  02111-1307, USA.
**
** Author contact information:
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** $Id: db.h,v 1.5 2001/01/31 13:28:09 drh Exp $
*/

typedef struct Db Db;
typedef struct DbCursor DbCursor;

int sqliteDbOpen(const char *filename, Db**);
int sqliteDbClose(Db*);
................................................................................
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 sqliteDbCursorWrite(DbCursor*, int amt, int offset, const void *buf);

int sqliteDbCursorFind(DbCursor*, int nKey, const void *pKey, int createFlag);
int sqliteDbCursorResize(DbCursor*, int nData);

**
**      +  When compiled using GCC on a SPARC, this version of printf is
**         faster than the library printf for SUN OS 4.1.
**
**      +  All functions are fully reentrant.
**
*/
#include <ctype.h>
#include "sqliteInt.h"

/*
** Undefine COMPATIBILITY to make some slight changes in the way things
** work.  I think the changes are an improvement, but they are not
** backwards compatible.
*/
................................................................................
      width = va_arg(ap,int);
      if( width<0 ){
        flag_leftjustify = 1;
        width = -width;
      }
      c = *++fmt;
    }else{
      while( isdigit(c) ){
        width = width*10 + c - '0';
        c = *++fmt;
      }
    }
    if( width > etBUFSIZE-10 ){
      width = etBUFSIZE-10;
    }
................................................................................
        precision = va_arg(ap,int);
#ifndef etCOMPATIBILITY
        /* This is sensible, but SUN OS 4.1 doesn't do it. */
        if( precision<0 ) precision = -precision;
#endif
        c = *++fmt;
      }else{
        while( isdigit(c) ){
          precision = precision*10 + c - '0';
          c = *++fmt;
        }
      }
      /* Limit the precision to prevent overflowing buf[] during conversion */
      if( precision>etBUFSIZE-40 ) precision = etBUFSIZE-40;
    }else{

**
**      +  When compiled using GCC on a SPARC, this version of printf is
**         faster than the library printf for SUN OS 4.1.
**
**      +  All functions are fully reentrant.
**
*/

#include "sqliteInt.h"

/*
** Undefine COMPATIBILITY to make some slight changes in the way things
** work.  I think the changes are an improvement, but they are not
** backwards compatible.
*/
................................................................................
      width = va_arg(ap,int);
      if( width<0 ){
        flag_leftjustify = 1;
        width = -width;
      }
      c = *++fmt;
    }else{
      while( c>='0' && c<='9' ){
        width = width*10 + c - '0';
        c = *++fmt;
      }
    }
    if( width > etBUFSIZE-10 ){
      width = etBUFSIZE-10;
    }
................................................................................
        precision = va_arg(ap,int);
#ifndef etCOMPATIBILITY
        /* This is sensible, but SUN OS 4.1 doesn't do it. */
        if( precision<0 ) precision = -precision;
#endif
        c = *++fmt;
      }else{
        while( c>='0' && c<='9' ){
          precision = precision*10 + c - '0';
          c = *++fmt;
        }
      }
      /* Limit the precision to prevent overflowing buf[] during conversion */
      if( precision>etBUFSIZE-40 ) precision = etBUFSIZE-40;
    }else{

*************************************************************************
** This file contains code to implement a pseudo-random number
** generator (PRNG) for SQLite.
**
** Random numbers are used by some of the database backends in order
** to generate random integer keys for tables or random filenames.
**
** $Id: random.c,v 1.1 2001/01/13 14:34:07 drh Exp $
*/
#include "sqliteInt.h"



/*
** Get a single 8-bit random value from the RC4 PRNG.
*/
int sqliteRandomByte(void){
  int t;

*************************************************************************
** This file contains code to implement a pseudo-random number
** generator (PRNG) for SQLite.
**
** Random numbers are used by some of the database backends in order
** to generate random integer keys for tables or random filenames.
**
** $Id: random.c,v 1.2 2001/01/31 13:28:09 drh Exp $
*/
#include "sqliteInt.h"

#include <time.h>

/*
** Get a single 8-bit random value from the RC4 PRNG.
*/
int sqliteRandomByte(void){
  int t;

** Author contact information:
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** A TCL Interface to SQLite
**
** $Id: tclsqlite.c,v 1.12 2000/10/19 14:59:27 drh Exp $
*/
#ifndef NO_TCL     /* Omit this whole file if TCL is unavailable */

#include "sqlite.h"
#include <tcl.h>
#include <stdlib.h>
#include <string.h>

/*
** There is one instance of this structure for each SQLite database
** that has been opened by the SQLite TCL interface.
*/

** Author contact information:
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** A TCL Interface to SQLite
**
** $Id: tclsqlite.c,v 1.13 2001/01/31 13:28:09 drh Exp $
*/
#ifndef NO_TCL     /* Omit this whole file if TCL is unavailable */

#include "sqlite.h"
#include "tcl.h"
#include <stdlib.h>
#include <string.h>

/*
** There is one instance of this structure for each SQLite database
** that has been opened by the SQLite TCL interface.
*/

#   drh@hwaci.com
#   http://www.hwaci.com/drh/
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this file is exercising the code in dbbe.c.
#
# $Id: dbbe.test,v 1.4 2000/10/16 22:06:43 drh Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl

# Try to open a database that does not exist.
#
do_test dbbe-1.1 {
  catch {db close}
  file delete -force testdb
  set v [catch {sqlite db testdb 0444} msg]
  lappend v $msg
} {1 {can't find directory "testdb"}}
do_test dbbe-1.2 {
  catch {db close}
  file delete -force testdb
  set v [catch {sqlite db testdb/dummy 0666} msg]
  lappend v $msg
} {1 {can't find or create directory "testdb/dummy"}}

# Try to open a database for writing in a directory that
# doesn't exist but for which the parent directory does
# exist.  This should work!
#
do_test dbbe-1.3 {
  catch {db close}
  file delete -force testdb
  set v [catch {sqlite db testdb 0666} msg]
  lappend v $msg
} {0 {}}

# Try to open a file instead of a directory.
#
do_test dbbe-1.4 {
  catch {db close}
  file delete -force testdb
  set fd [open testdb w]
  puts $fd hi!
  close $fd
  set v [catch {sqlite db testdb 0666} msg]
  lappend v $msg
} {1 {not a directory: "testdb"}}

# Access permission denied on the directory.
#
do_test dbbe-1.5 {
  catch {db close}
  file delete -force testdb
  file mkdir testdb
  file attributes testdb -permissions 0
  set v [catch {sqlite db testdb 0666} msg]
  lappend v $msg
} {1 {access permission denied}}

# Access permission denied on the master file
#
do_test dbbe-1.6 {
  catch {db close}
  file delete -force testdb
  sqlite db testdb 0666
  execsql {CREATE TABLE t1(x int)}
  db close
  file attributes testdb/sqlite_master.tbl -permission 0444
  set v [catch {sqlite db testdb 0666} msg]
  lappend v $msg
} {1 {access permission denied for testdb/sqlite_master.tbl}}
do_test dbbe-1.6b {
  catch {db close}
  file delete -force testdb
  sqlite db testdb 0666
  execsql {CREATE TABLE t1(x int)}
  db close
  file attributes testdb/sqlite_master.tbl -permission 0444
  set v [catch {sqlite db testdb 0444} msg]
  lappend v $msg
} {0 {}}

# Make sure a table can be accessed by either uppercase or lowercase
# names
#
do_test dbbe-2.1 {
  catch {db close}
  file delete -force testdb
  sqlite db testdb 0666
  execsql {
    CREATE TABLE t1(x int);
    INSERT INTO t1 VALUES(1);
  }
  db close
  sqlite db testdb 0444
................................................................................
  lappend r [execsql {SELECT * FROM t1}]
} {1 1}

# Try to change a table after opening the database readonly
#
do_test dbbe-3.1 {
  catch {db close}
  file delete -force testdb
  sqlite db testdb 0666
  execsql {CREATE TABLE t1(x int)}
  db close
  sqlite db testdb 0444
  set v [catch {execsql {INSERT INTO t1 VALUES(1)}} msg]
  lappend v $msg
} {7 {table t1 is readonly}}


finish_test

#   drh@hwaci.com
#   http://www.hwaci.com/drh/
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this file is exercising the code in dbbe.c.
#
# $Id: dbbe.test,v 1.5 2001/01/31 13:28:09 drh Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl

# Try to open a database that does not exist.
#
do_test dbbe-1.1 {
  catch {db close}
  forcedelete testdb
  set v [catch {sqlite db testdb 0444} msg]
  lappend v $msg
} {1 {can't find directory "testdb"}}
do_test dbbe-1.2 {
  catch {db close}
  forcedelete testdb
  set v [catch {sqlite db testdb/dummy 0666} msg]
  lappend v $msg
} {1 {can't find or create directory "testdb/dummy"}}

# Try to open a database for writing in a directory that
# doesn't exist but for which the parent directory does
# exist.  This should work!
#
do_test dbbe-1.3 {
  catch {db close}
  forcedelete testdb
  set v [catch {sqlite db testdb 0666} msg]
  lappend v $msg
} {0 {}}

# Try to open a file instead of a directory.
#
do_test dbbe-1.4 {
  catch {db close}
  forcedelete testdb
  set fd [open testdb w]
  puts $fd hi!
  close $fd
  set v [catch {sqlite db testdb 0666} msg]
  lappend v $msg
} {1 {not a directory: "testdb"}}

# Access permission denied on the directory.
#
do_test dbbe-1.5 {
  catch {db close}
  forcedelete testdb
  file mkdir testdb
  file attributes testdb -permissions 0
  set v [catch {sqlite db testdb 0666} msg]
  lappend v $msg
} {1 {access permission denied}}

# Access permission denied on the master file
#
do_test dbbe-1.6 {
  catch {db close}
  forcedelete testdb
  sqlite db testdb 0666
  execsql {CREATE TABLE t1(x int)}
  db close
  file attributes testdb/sqlite_master.tbl -permission 0444
  set v [catch {sqlite db testdb 0666} msg]
  lappend v $msg
} {1 {access permission denied for testdb/sqlite_master.tbl}}
do_test dbbe-1.6b {
  catch {db close}
  forcedelete testdb
  sqlite db testdb 0666
  execsql {CREATE TABLE t1(x int)}
  db close
  file attributes testdb/sqlite_master.tbl -permission 0444
  set v [catch {sqlite db testdb 0444} msg]
  lappend v $msg
} {0 {}}

# Make sure a table can be accessed by either uppercase or lowercase
# names
#
do_test dbbe-2.1 {
  catch {db close}
  forcedelete testdb
  sqlite db testdb 0666
  execsql {
    CREATE TABLE t1(x int);
    INSERT INTO t1 VALUES(1);
  }
  db close
  sqlite db testdb 0444
................................................................................
  lappend r [execsql {SELECT * FROM t1}]
} {1 1}

# Try to change a table after opening the database readonly
#
do_test dbbe-3.1 {
  catch {db close}
  forcedelete testdb
  sqlite db testdb 0666
  execsql {CREATE TABLE t1(x int)}
  db close
  sqlite db testdb 0444
  set v [catch {execsql {INSERT INTO t1 VALUES(1)}} msg]
  lappend v $msg
} {7 {table t1 is readonly}}


finish_test

#   drh@hwaci.com
#   http://www.hwaci.com/drh/
#
#***********************************************************************
# This file implements some common TCL routines used for regression
# testing the SQLite library
#
# $Id: tester.tcl,v 1.9 2001/01/22 00:31:53 drh Exp $

# Create a test database
#
if {![info exists dbprefix]} {
  if {[info exists env(SQLITE_PREFIX)]} {
    set dbprefix $env(SQLITE_PREFIX):
  } else {
    set dbprefix "gdbm:"
  }
}
switch $dbprefix {
  gdbm: {
   file delete -force testdb


   file mkdir testdb
  }
  memory: {
   # do nothing
  }
}
sqlite db ${dbprefix}testdb
................................................................................
  db eval $sql data {
    foreach f $data(*) {
      lappend result $f $data($f)
    }
  }
  return $result
}

#   drh@hwaci.com
#   http://www.hwaci.com/drh/
#
#***********************************************************************
# This file implements some common TCL routines used for regression
# testing the SQLite library
#
# $Id: tester.tcl,v 1.10 2001/01/31 13:28:09 drh Exp $

# Create a test database
#
if {![info exists dbprefix]} {
  if {[info exists env(SQLITE_PREFIX)]} {
    set dbprefix $env(SQLITE_PREFIX):
  } else {
    set dbprefix "gdbm:"
  }
}
switch $dbprefix {
  gdbm: {
   if {[catch {file delete -force testdb}]} {
     exec rm -rf testdb
   }
   file mkdir testdb
  }
  memory: {
   # do nothing
  }
}
sqlite db ${dbprefix}testdb
................................................................................
  db eval $sql data {
    foreach f $data(*) {
      lappend result $f $data($f)
    }
  }
  return $result
}

# Delete a file or directory
#
proc forcedelete {filename} {
  if {[catch {file delete -force $filename}]} {
    exec rm -rf $filename
  }
}

#
# Run this Tcl script to generate the crosscompile.html file.
#
set rcsid {$Id: crosscompile.tcl,v 1.3 2000/10/11 19:28:53 drh Exp $}

puts {<html>
<head>
  <title>Notes On How To Compile SQLite Using The MinGW Cross-Compiler</title>
</head>
<body bgcolor=white>
<h1 align=center>
................................................................................

<blockquote><pre>
cat &gt;&gt;systems.h &lt;&lt;\END
#ifdef NO_LOCKS
#undef  UNLOCK_FILE
#define UNLOCK_FILE(x)
#undef  READLOCK_FILE
#define READLOCK_FILE(x)
#undef  WRITELOCK_FILE
#define WRITELOCK_FILE(x)
#endif
END
</pre></blockquote>

<p>Then manually build the GDBM library with the extra
"NO_LOCKS" define as follows:</p>
<blockquote><pre>

#
# Run this Tcl script to generate the crosscompile.html file.
#
set rcsid {$Id: crosscompile.tcl,v 1.4 2001/01/31 13:28:09 drh Exp $}

puts {<html>
<head>
  <title>Notes On How To Compile SQLite Using The MinGW Cross-Compiler</title>
</head>
<body bgcolor=white>
<h1 align=center>
................................................................................

<blockquote><pre>
cat &gt;&gt;systems.h &lt;&lt;\END
#ifdef NO_LOCKS
#undef  UNLOCK_FILE
#define UNLOCK_FILE(x)
#undef  READLOCK_FILE
#define READLOCK_FILE(x)  lock_val=0;
#undef  WRITELOCK_FILE
#define WRITELOCK_FILE(x) lock_val=0;
#endif
END
</pre></blockquote>

<p>Then manually build the GDBM library with the extra
"NO_LOCKS" define as follows:</p>
<blockquote><pre>