** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** $Id: btree.c,v 1.49 2002/02/03 03:34:08 drh Exp $
**
** This file implements a external (disk-based) database using BTrees.
** For a detailed discussion of BTrees, refer to
**
**     Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
**     "Sorting And Searching", pages 473-480. Addison-Wesley
**     Publishing Company, Reading, Massachusetts.
................................................................................
  return SQLITE_OK;
}

/******************************************************************************
** The complete implementation of the BTree subsystem is above this line.
** All the code the follows is for testing and troubleshooting the BTree
** subsystem.  None of the code that follows is used during normal operation.
** All of the following code is omitted unless the library is compiled with
** the -DSQLITE_TEST=1 compiler option.
******************************************************************************/
#if 1

/*
** Print a disassembly of the given page on standard output.  This routine
** is used for debugging and testing only.
*/
int sqliteBtreePageDump(Btree *pBt, int pgno, int recursive){
  int rc;
................................................................................
      checkAppendMsg(pCheck, zContext, zMsg);
      break;
    }
    iPage = (int)pOvfl->iNext;
    sqlitepager_unref(pOvfl);
  }
}


















/*
** Do various sanity checks on a single page of a tree.  Return
** the tree depth.  Root pages return 0.  Parents of root pages
** return 1, and so forth.
** 
** These checks are done:
................................................................................
*/
static int checkTreePage(
  SanityCheck *pCheck,  /* Context for the sanity check */
  int iPage,            /* Page number of the page to check */
  MemPage *pParent,     /* Parent page */
  char *zParentContext, /* Parent context */
  char *zLowerBound,    /* All keys should be greater than this, if not NULL */

  char *zUpperBound     /* All keys should be less than this, if not NULL */

){
  MemPage *pPage;
  int i, rc, depth, d2, pgno;
  char *zKey1, *zKey2;

  BtCursor cur;
  char zMsg[100];
  char zContext[100];
  char hit[SQLITE_PAGE_SIZE];

  /* Check that the page exists
  */
................................................................................
    sqlitepager_unref(pPage);
    return 0;
  }

  /* Check out all the cells.
  */
  depth = 0;
  zKey1 = zLowerBound ? sqliteStrDup(zLowerBound) : 0;







  cur.pPage = pPage;
  cur.pBt = pCheck->pBt;
  for(i=0; i<pPage->nCell; i++){
    Cell *pCell = pPage->apCell[i];
    int sz;

    /* Check payload overflow pages
    */
    sz = NKEY(pCell->h) + NDATA(pCell->h);

    sprintf(zContext, "On page %d cell %d: ", iPage, i);
    if( sz>MX_LOCAL_PAYLOAD ){
      int nPage = (sz - MX_LOCAL_PAYLOAD + OVERFLOW_SIZE - 1)/OVERFLOW_SIZE;
      checkList(pCheck, pCell->ovfl, nPage, zContext);
    }

    /* Check that keys are in the right order
    */
    cur.idx = i;
    zKey2 = sqliteMalloc( NKEY(pCell->h)+1 );
    getPayload(&cur, 0, NKEY(pCell->h), zKey2);
    if( zKey1 && strcmp(zKey1,zKey2)>0 ){
      checkAppendMsg(pCheck, zContext, "Key is out of order");
    }

    /* Check sanity of left child page.
    */
    pgno = (int)pCell->h.leftChild;
    d2 = checkTreePage(pCheck, pgno, pPage, zContext, zKey1, zKey2);
    if( i>0 && d2!=depth ){
      checkAppendMsg(pCheck, zContext, "Child page depth differs");
    }
    depth = d2;
    sqliteFree(zKey1);
    zKey1 = zKey2;

  }
  pgno = pPage->u.hdr.rightChild;
  sprintf(zContext, "On page %d at right child: ", iPage);
  checkTreePage(pCheck, pgno, pPage, zContext, zKey1, zUpperBound);
  sqliteFree(zKey1);
 
  /* Check for complete coverage of the page
  */
  memset(hit, 0, sizeof(hit));
  memset(hit, 1, sizeof(PageHdr));
  for(i=pPage->u.hdr.firstCell; i>0 && i<SQLITE_PAGE_SIZE; ){
................................................................................
  /* Check the integrity of the freelist
  */
  checkList(&sCheck, pBt->page1->freeList, pBt->page1->nFree,"Main freelist: ");

  /* Check all the tables.
  */
  for(i=0; i<nRoot; i++){
    checkTreePage(&sCheck, aRoot[i], 0, "List of tree roots: ", 0, 0);
  }

  /* Make sure every page in the file is referenced
  */
  for(i=1; i<=sCheck.nPage; i++){
    if( sCheck.anRef[i]==0 ){
      char zBuf[100];
................................................................................

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

#endif /* SQLITE_TEST */

** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** $Id: btree.c,v 1.50 2002/02/03 17:37:36 drh Exp $
**
** This file implements a external (disk-based) database using BTrees.
** For a detailed discussion of BTrees, refer to
**
**     Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
**     "Sorting And Searching", pages 473-480. Addison-Wesley
**     Publishing Company, Reading, Massachusetts.
................................................................................
  return SQLITE_OK;
}

/******************************************************************************
** The complete implementation of the BTree subsystem is above this line.
** All the code the follows is for testing and troubleshooting the BTree
** subsystem.  None of the code that follows is used during normal operation.
** All of the following code is omitted if the library is compiled with
** the -DNDEBUG=1 compiler option.
******************************************************************************/
#ifndef NDEEBUG

/*
** Print a disassembly of the given page on standard output.  This routine
** is used for debugging and testing only.
*/
int sqliteBtreePageDump(Btree *pBt, int pgno, int recursive){
  int rc;
................................................................................
      checkAppendMsg(pCheck, zContext, zMsg);
      break;
    }
    iPage = (int)pOvfl->iNext;
    sqlitepager_unref(pOvfl);
  }
}

/*
** Return negative if zKey1<zKey2.
** Return zero if zKey1==zKey2.
** Return positive if zKey1>zKey2.
*/
static int keyCompare(
  const char *zKey1, int nKey1,
  const char *zKey2, int nKey2
){
  int min = nKey1>nKey2 ? nKey2 : nKey1;
  int c = memcmp(zKey1, zKey2, min);
  if( c==0 ){
    c = nKey1 - nKey2;
  }
  return c;
}

/*
** Do various sanity checks on a single page of a tree.  Return
** the tree depth.  Root pages return 0.  Parents of root pages
** return 1, and so forth.
** 
** These checks are done:
................................................................................
*/
static int checkTreePage(
  SanityCheck *pCheck,  /* Context for the sanity check */
  int iPage,            /* Page number of the page to check */
  MemPage *pParent,     /* Parent page */
  char *zParentContext, /* Parent context */
  char *zLowerBound,    /* All keys should be greater than this, if not NULL */
  int nLower,           /* Number of characters in zLowerBound */
  char *zUpperBound,    /* All keys should be less than this, if not NULL */
  int nUpper            /* Number of characters in zUpperBound */
){
  MemPage *pPage;
  int i, rc, depth, d2, pgno;
  char *zKey1, *zKey2;
  int nKey1, nKey2;
  BtCursor cur;
  char zMsg[100];
  char zContext[100];
  char hit[SQLITE_PAGE_SIZE];

  /* Check that the page exists
  */
................................................................................
    sqlitepager_unref(pPage);
    return 0;
  }

  /* Check out all the cells.
  */
  depth = 0;
  if( zLowerBound ){
    zKey1 = sqliteMalloc( nLower+1 );
    memcpy(zKey1, zLowerBound, nLower);
    zKey1[nLower] = 0;
  }else{
    zKey1 = 0;
  }
  nKey1 = nLower;
  cur.pPage = pPage;
  cur.pBt = pCheck->pBt;
  for(i=0; i<pPage->nCell; i++){
    Cell *pCell = pPage->apCell[i];
    int sz;

    /* Check payload overflow pages
    */
    nKey2 = NKEY(pCell->h);
    sz = nKey2 + NDATA(pCell->h);
    sprintf(zContext, "On page %d cell %d: ", iPage, i);
    if( sz>MX_LOCAL_PAYLOAD ){
      int nPage = (sz - MX_LOCAL_PAYLOAD + OVERFLOW_SIZE - 1)/OVERFLOW_SIZE;
      checkList(pCheck, pCell->ovfl, nPage, zContext);
    }

    /* Check that keys are in the right order
    */
    cur.idx = i;
    zKey2 = sqliteMalloc( nKey2+1 );
    getPayload(&cur, 0, nKey2, zKey2);
    if( zKey1 && keyCompare(zKey1, nKey1, zKey2, nKey2)>=0 ){
      checkAppendMsg(pCheck, zContext, "Key is out of order");
    }

    /* Check sanity of left child page.
    */
    pgno = (int)pCell->h.leftChild;
    d2 = checkTreePage(pCheck, pgno, pPage, zContext, zKey1,nKey1,zKey2,nKey2);
    if( i>0 && d2!=depth ){
      checkAppendMsg(pCheck, zContext, "Child page depth differs");
    }
    depth = d2;
    sqliteFree(zKey1);
    zKey1 = zKey2;
    nKey1 = nKey2;
  }
  pgno = pPage->u.hdr.rightChild;
  sprintf(zContext, "On page %d at right child: ", iPage);
  checkTreePage(pCheck, pgno, pPage, zContext, zKey1,nKey1,zUpperBound,nUpper);
  sqliteFree(zKey1);
 
  /* Check for complete coverage of the page
  */
  memset(hit, 0, sizeof(hit));
  memset(hit, 1, sizeof(PageHdr));
  for(i=pPage->u.hdr.firstCell; i>0 && i<SQLITE_PAGE_SIZE; ){
................................................................................
  /* Check the integrity of the freelist
  */
  checkList(&sCheck, pBt->page1->freeList, pBt->page1->nFree,"Main freelist: ");

  /* Check all the tables.
  */
  for(i=0; i<nRoot; i++){
    checkTreePage(&sCheck, aRoot[i], 0, "List of tree roots: ", 0,0,0,0);
  }

  /* Make sure every page in the file is referenced
  */
  for(i=1; i<=sCheck.nPage; i++){
    if( sCheck.anRef[i]==0 ){
      char zBuf[100];
................................................................................

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

#endif /* !defined(NDEBUG) */

**    May you share freely, never taking more than you give.
**
*************************************************************************
** This header file defines the interface that the sqlite B-Tree file
** subsystem.  See comments in the source code for a detailed description
** of what each interface routine does.
**
** @(#) $Id: btree.h,v 1.20 2002/02/02 18:49:20 drh Exp $
*/
#ifndef _BTREE_H_
#define _BTREE_H_

typedef struct Btree Btree;
typedef struct BtCursor BtCursor;

................................................................................
int sqliteBtreeCloseCursor(BtCursor*);

#define SQLITE_N_BTREE_META 4
int sqliteBtreeGetMeta(Btree*, int*);
int sqliteBtreeUpdateMeta(Btree*, int*);


#ifdef SQLITE_TEST
int sqliteBtreePageDump(Btree*, int, int);
int sqliteBtreeCursorDump(BtCursor*, int*);
struct Pager *sqliteBtreePager(Btree*);
char *sqliteBtreeSanityCheck(Btree*, int*, int);
#endif

#endif /* _BTREE_H_ */

**    May you share freely, never taking more than you give.
**
*************************************************************************
** This header file defines the interface that the sqlite B-Tree file
** subsystem.  See comments in the source code for a detailed description
** of what each interface routine does.
**
** @(#) $Id: btree.h,v 1.21 2002/02/03 17:37:36 drh Exp $
*/
#ifndef _BTREE_H_
#define _BTREE_H_

typedef struct Btree Btree;
typedef struct BtCursor BtCursor;

................................................................................
int sqliteBtreeCloseCursor(BtCursor*);

#define SQLITE_N_BTREE_META 4
int sqliteBtreeGetMeta(Btree*, int*);
int sqliteBtreeUpdateMeta(Btree*, int*);


#ifndef NDEBUG
int sqliteBtreePageDump(Btree*, int, int);
int sqliteBtreeCursorDump(BtCursor*, int*);
struct Pager *sqliteBtreePager(Btree*);
char *sqliteBtreeSanityCheck(Btree*, int*, int);
#endif

#endif /* _BTREE_H_ */

**     COPY
**     VACUUM
**     BEGIN TRANSACTION
**     COMMIT
**     ROLLBACK
**     PRAGMA
**
** $Id: build.c,v 1.73 2002/02/03 03:34:08 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

/*
** This routine is called after a single SQL statement has been
** parsed and we want to execute the VDBE code to implement 
................................................................................
}

/*
** The non-standard VACUUM command is used to clean up the database,
** collapse free space, etc.  It is modelled after the VACUUM command
** in PostgreSQL.
**
** In this implementation, no cleanup occurs.  Instead, the B-tree that
** forms the database is checked for integrity.  This is a no-op unless
** SQLite is compiled with the SQLITE_TEST macro.

*/
void sqliteVacuum(Parse *pParse, Token *pTableName){
#if 1
  static VdbeOp checkDb[] = {
    { OP_SetInsert,   0, 0,        "2"},
    { OP_Open,        0, 2,        0},
    { OP_Rewind,      0, 6,        0},
    { OP_Column,      0, 3,        0},
    { OP_SetInsert,   0, 0,        0},
    { OP_Next,        0, 3,        0},
    { OP_SanityCheck, 0, 0,        0},
    { OP_ColumnCount, 1, 0,        0},
    { OP_ColumnName,  0, 0,        "sanity_check"},
    { OP_Callback,    1, 0,        0},
  };
  static 
  Vdbe *v;
 

  v = sqliteGetVdbe(pParse);
  if( v==0 ) return;
  sqliteVdbeAddOpList(v, ArraySize(checkDb), checkDb);
  return;
#endif
}

/*
** Begin a transaction
*/
void sqliteBeginTransaction(Parse *pParse, int onError){
  sqlite *db;
................................................................................
    if( getBoolean(zRight) ){
      sqliteParserTrace(stdout, "parser: ");
    }else{
      sqliteParserTrace(0, 0);
    }
  }else
#endif





















  {}
  sqliteFree(zLeft);
  sqliteFree(zRight);
}

**     COPY
**     VACUUM
**     BEGIN TRANSACTION
**     COMMIT
**     ROLLBACK
**     PRAGMA
**
** $Id: build.c,v 1.74 2002/02/03 17:37:36 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

/*
** This routine is called after a single SQL statement has been
** parsed and we want to execute the VDBE code to implement 
................................................................................
}

/*
** The non-standard VACUUM command is used to clean up the database,
** collapse free space, etc.  It is modelled after the VACUUM command
** in PostgreSQL.
**
** In version 1.0.x of SQLite, the VACUUM command would call
** gdbm_reorganize() on all the database tables.  But beginning
** with 2.0.0, SQLite no longer uses GDBM so this command has
** become a no-op.
*/
void sqliteVacuum(Parse *pParse, Token *pTableName){

  /* Do nothing */




















}

/*
** Begin a transaction
*/
void sqliteBeginTransaction(Parse *pParse, int onError){
  sqlite *db;
................................................................................
    if( getBoolean(zRight) ){
      sqliteParserTrace(stdout, "parser: ");
    }else{
      sqliteParserTrace(0, 0);
    }
  }else
#endif

#ifndef NDEBUG
  if( sqliteStrICmp(zLeft, "sanity_check")==0 ){
    static VdbeOp checkDb[] = {
      { OP_SetInsert,   0, 0,        "2"},
      { OP_Open,        0, 2,        0},
      { OP_Rewind,      0, 6,        0},
      { OP_Column,      0, 3,        0},
      { OP_SetInsert,   0, 0,        0},
      { OP_Next,        0, 3,        0},
      { OP_SanityCheck, 0, 0,        0},
      { OP_ColumnCount, 1, 0,        0},
      { OP_ColumnName,  0, 0,        "sanity_check"},
      { OP_Callback,    1, 0,        0},
    };
    Vdbe *v = sqliteGetVdbe(pParse);
    if( v==0 ) return;
    sqliteVdbeAddOpList(v, ArraySize(checkDb), checkDb);
  }else
#endif

  {}
  sqliteFree(zLeft);
  sqliteFree(zRight);
}

**
*************************************************************************
** This file contains SQLite's grammar for SQL.  Process this file
** using the lemon parser generator to generate C code that runs
** the parser.  Lemon will also generate a header file containing
** numeric codes for all of the tokens.
**
** @(#) $Id: parse.y,v 1.47 2002/02/03 00:56:10 drh Exp $
*/
%token_prefix TK_
%token_type {Token}
%default_type {Token}
%extra_argument {Parse *pParse}
%syntax_error {
  sqliteSetString(&pParse->zErrMsg,"syntax error",0);
................................................................................
///////////////////////////// The PRAGMA command /////////////////////////////
//
cmd ::= PRAGMA ids(X) EQ ids(Y).         {sqlitePragma(pParse,&X,&Y,0);}
cmd ::= PRAGMA ids(X) EQ ON(Y).          {sqlitePragma(pParse,&X,&Y,0);}
cmd ::= PRAGMA ids(X) EQ plus_num(Y).    {sqlitePragma(pParse,&X,&Y,0);}
cmd ::= PRAGMA ids(X) EQ minus_num(Y).   {sqlitePragma(pParse,&X,&Y,1);}
cmd ::= PRAGMA ids(X) LP ids(Y) RP.      {sqlitePragma(pParse,&X,&Y,0);}

plus_num(A) ::= plus_opt number(X).   {A = X;}
minus_num(A) ::= MINUS number(X).     {A = X;}
number(A) ::= INTEGER(X).  {A = X;}
number(A) ::= FLOAT(X).    {A = X;}
plus_opt ::= PLUS.
plus_opt ::= .

**
*************************************************************************
** This file contains SQLite's grammar for SQL.  Process this file
** using the lemon parser generator to generate C code that runs
** the parser.  Lemon will also generate a header file containing
** numeric codes for all of the tokens.
**
** @(#) $Id: parse.y,v 1.48 2002/02/03 17:37:36 drh Exp $
*/
%token_prefix TK_
%token_type {Token}
%default_type {Token}
%extra_argument {Parse *pParse}
%syntax_error {
  sqliteSetString(&pParse->zErrMsg,"syntax error",0);
................................................................................
///////////////////////////// The PRAGMA command /////////////////////////////
//
cmd ::= PRAGMA ids(X) EQ ids(Y).         {sqlitePragma(pParse,&X,&Y,0);}
cmd ::= PRAGMA ids(X) EQ ON(Y).          {sqlitePragma(pParse,&X,&Y,0);}
cmd ::= PRAGMA ids(X) EQ plus_num(Y).    {sqlitePragma(pParse,&X,&Y,0);}
cmd ::= PRAGMA ids(X) EQ minus_num(Y).   {sqlitePragma(pParse,&X,&Y,1);}
cmd ::= PRAGMA ids(X) LP ids(Y) RP.      {sqlitePragma(pParse,&X,&Y,0);}
cmd ::= PRAGMA(Y) ids(X).                {sqlitePragma(pParse,&X,&Y,0);}
plus_num(A) ::= plus_opt number(X).   {A = X;}
minus_num(A) ::= MINUS number(X).     {A = X;}
number(A) ::= INTEGER(X).  {A = X;}
number(A) ::= FLOAT(X).    {A = X;}
plus_opt ::= PLUS.
plus_opt ::= .