** 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.257 2005/05/01 22:52:42 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.
................................................................................
**      *     zero or more pages numbers of leaves
*/
#include "sqliteInt.h"
#include "pager.h"
#include "btree.h"
#include "os.h"
#include <assert.h>







/* The following value is the maximum cell size assuming a maximum page
** size give above.
*/
#define MX_CELL_SIZE(pBt)  (pBt->pageSize-8)

/* The maximum number of cells on a single page of the database.  This
................................................................................

  /*
  ** Allocate space for memory structures
  */
  apCell = sqliteMallocRaw( 
       nMaxCells*sizeof(u8*)                           /* apCell */
     + nMaxCells*sizeof(int)                           /* szCell */
     + sizeof(MemPage)*NB                              /* aCopy */
     + pBt->pageSize*(5+NB)                            /* aSpace */
     + (ISAUTOVACUUM ? nMaxCells : 0)     /* aFrom */
  );
  if( apCell==0 ){
    rc = SQLITE_NOMEM;
    goto balance_cleanup;
  }
  szCell = (int*)&apCell[nMaxCells];
  aCopy[0] = (u8*)&szCell[nMaxCells];

  for(i=1; i<NB; i++){
    aCopy[i] = &aCopy[i-1][pBt->pageSize+sizeof(MemPage)];

  }
  aSpace = &aCopy[NB-1][pBt->pageSize+sizeof(MemPage)];

#ifndef SQLITE_OMIT_AUTOVACUUM
  if( pBt->autoVacuum ){
    aFrom = &aSpace[5*pBt->pageSize];
  }
#endif
  
  /*
................................................................................
  ** Make copies of the content of pPage and its siblings into aOld[].
  ** The rest of this function will use data from the copies rather
  ** that the original pages since the original pages will be in the
  ** process of being overwritten.
  */
  for(i=0; i<nOld; i++){
    MemPage *p = apCopy[i] = (MemPage*)&aCopy[i][pBt->pageSize];
    assert( (((long long unsigned int)p) & 7)==0 );
    p->aData = &((u8*)p)[-pBt->pageSize];
    memcpy(p->aData, apOld[i]->aData, pBt->pageSize + sizeof(MemPage));
    /* The memcpy() above changes the value of p->aData so we have to
    ** set it again. */
    assert( (((long long unsigned int)p) & 7)==0 );
    p->aData = &((u8*)p)[-pBt->pageSize];
  }

  /*
  ** Load pointers to all cells on sibling pages and the divider cells
  ** into the local apCell[] array.  Make copies of the divider cells
  ** into space obtained form aSpace[] and remove the the divider Cells

** 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.258 2005/05/03 12:30:34 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.
................................................................................
**      *     zero or more pages numbers of leaves
*/
#include "sqliteInt.h"
#include "pager.h"
#include "btree.h"
#include "os.h"
#include <assert.h>

/* Round up a number to the next larger multiple of 8.  This is used
** to force 8-byte alignment on 64-bit architectures.
*/
#define ROUND8(x)   ((x+7)&~7)


/* The following value is the maximum cell size assuming a maximum page
** size give above.
*/
#define MX_CELL_SIZE(pBt)  (pBt->pageSize-8)

/* The maximum number of cells on a single page of the database.  This
................................................................................

  /*
  ** Allocate space for memory structures
  */
  apCell = sqliteMallocRaw( 
       nMaxCells*sizeof(u8*)                           /* apCell */
     + nMaxCells*sizeof(int)                           /* szCell */
     + ROUND8(sizeof(MemPage))*NB                      /* aCopy */
     + pBt->pageSize*(5+NB)                            /* aSpace */
     + (ISAUTOVACUUM ? nMaxCells : 0)                  /* aFrom */
  );
  if( apCell==0 ){
    rc = SQLITE_NOMEM;
    goto balance_cleanup;
  }
  szCell = (int*)&apCell[nMaxCells];
  aCopy[0] = (u8*)&szCell[nMaxCells];
  assert( ((aCopy[0] - (u8*)apCell) & 7)==0 ); /* 8-byte alignment required */
  for(i=1; i<NB; i++){
    aCopy[i] = &aCopy[i-1][pBt->pageSize+ROUND8(sizeof(MemPage))];
    assert( ((aCopy[i] - (u8*)apCell) & 7)==0 ); /* 8-byte alignment required */
  }
  aSpace = &aCopy[NB-1][pBt->pageSize+ROUND8(sizeof(MemPage))];
  assert( ((aSpace - (u8*)apCell) & 7)==0 ); /* 8-byte alignment required */
#ifndef SQLITE_OMIT_AUTOVACUUM
  if( pBt->autoVacuum ){
    aFrom = &aSpace[5*pBt->pageSize];
  }
#endif
  
  /*
................................................................................
  ** Make copies of the content of pPage and its siblings into aOld[].
  ** The rest of this function will use data from the copies rather
  ** that the original pages since the original pages will be in the
  ** process of being overwritten.
  */
  for(i=0; i<nOld; i++){
    MemPage *p = apCopy[i] = (MemPage*)&aCopy[i][pBt->pageSize];

    p->aData = &((u8*)p)[-pBt->pageSize];
    memcpy(p->aData, apOld[i]->aData, pBt->pageSize + sizeof(MemPage));
    /* The memcpy() above changes the value of p->aData so we have to
    ** set it again. */

    p->aData = &((u8*)p)[-pBt->pageSize];
  }

  /*
  ** Load pointers to all cells on sibling pages and the divider cells
  ** into the local apCell[] array.  Make copies of the divider cells
  ** into space obtained form aSpace[] and remove the the divider Cells

**     CREATE INDEX
**     DROP INDEX
**     creating ID lists
**     BEGIN TRANSACTION
**     COMMIT
**     ROLLBACK
**
** $Id: build.c,v 1.318 2005/03/29 03:10:59 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

/*
** This routine is called when a new SQL statement is beginning to
** be parsed.  Initialize the pParse structure as needed.
................................................................................
    sqlite3HashInsert(&db->aDb[p->iDb].idxHash, pOld->zName,
                     strlen(pOld->zName)+1, pOld);
  }
  freeIndex(p);
}

/*
** Unlink the given index from its table, then remove

** the index from the index hash table and free its memory
** structures.

*/
void sqlite3UnlinkAndDeleteIndex(sqlite3 *db, int iDb, const char *zIdxName){
  Index *pIndex;
  int len;

  len = strlen(zIdxName);
  pIndex = sqlite3HashInsert(&db->aDb[iDb].idxHash, zIdxName, len+1, 0);
................................................................................

/*
** Given a token, return a string that consists of the text of that
** token with any quotations removed.  Space to hold the returned string
** is obtained from sqliteMalloc() and must be freed by the calling
** function.
**
** Tokens are really just pointers into the original SQL text and so
** are not \000 terminated and are not persistent.  The returned string
** is \000 terminated and is persistent.
*/
char *sqlite3NameFromToken(Token *pName){
  char *zName;
  if( pName ){
    zName = sqliteStrNDup(pName->z, pName->n);

**     CREATE INDEX
**     DROP INDEX
**     creating ID lists
**     BEGIN TRANSACTION
**     COMMIT
**     ROLLBACK
**
** $Id: build.c,v 1.319 2005/05/03 12:30:34 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

/*
** This routine is called when a new SQL statement is beginning to
** be parsed.  Initialize the pParse structure as needed.
................................................................................
    sqlite3HashInsert(&db->aDb[p->iDb].idxHash, pOld->zName,
                     strlen(pOld->zName)+1, pOld);
  }
  freeIndex(p);
}

/*
** For the index called zIdxName which is found in the database iDb,
** unlike that index from its Table then remove the index from
** the index hash table and free all memory structures associated

** with the index.
*/
void sqlite3UnlinkAndDeleteIndex(sqlite3 *db, int iDb, const char *zIdxName){
  Index *pIndex;
  int len;

  len = strlen(zIdxName);
  pIndex = sqlite3HashInsert(&db->aDb[iDb].idxHash, zIdxName, len+1, 0);
................................................................................

/*
** Given a token, return a string that consists of the text of that
** token with any quotations removed.  Space to hold the returned string
** is obtained from sqliteMalloc() and must be freed by the calling
** function.
**
** Tokens are often just pointers into the original SQL text and so
** are not \000 terminated and are not persistent.  The returned string
** is \000 terminated and is persistent.
*/
char *sqlite3NameFromToken(Token *pName){
  char *zName;
  if( pName ){
    zName = sqliteStrNDup(pName->z, pName->n);

**
*************************************************************************
** Utility functions used throughout sqlite.
**
** This file contains functions for allocating memory, comparing
** strings, and stuff like that.
**
** $Id: util.c,v 1.132 2005/03/18 14:03:15 drh Exp $
*/
#include "sqliteInt.h"
#include <stdarg.h>
#include <ctype.h>

#if SQLITE_MEMDEBUG>2 && defined(__GLIBC__)
#include <execinfo.h>
................................................................................
int sqlite3_iMallocFail;     /* Fail sqliteMalloc() after this many calls */
int sqlite3_iMallocReset = -1; /* When iMallocFail reaches 0, set to this */
#if SQLITE_MEMDEBUG>1
static int memcnt = 0;
#endif

/*
** Number of 32-bit guard words


*/
#define N_GUARD 1

/*
** Allocate new memory and set it to zero.  Return NULL if
** no memory is available.
*/
void *sqlite3Malloc_(int n, int bZero, char *zFile, int line){
  void *p;

**
*************************************************************************
** Utility functions used throughout sqlite.
**
** This file contains functions for allocating memory, comparing
** strings, and stuff like that.
**
** $Id: util.c,v 1.133 2005/05/03 12:30:34 drh Exp $
*/
#include "sqliteInt.h"
#include <stdarg.h>
#include <ctype.h>

#if SQLITE_MEMDEBUG>2 && defined(__GLIBC__)
#include <execinfo.h>
................................................................................
int sqlite3_iMallocFail;     /* Fail sqliteMalloc() after this many calls */
int sqlite3_iMallocReset = -1; /* When iMallocFail reaches 0, set to this */
#if SQLITE_MEMDEBUG>1
static int memcnt = 0;
#endif

/*
** Number of 32-bit guard words.  This should probably be a multiple of
** 2 since on 64-bit machines we want the value returned by sqliteMalloc()
** to be 8-byte aligned.
*/
#define N_GUARD 2

/*
** Allocate new memory and set it to zero.  Return NULL if
** no memory is available.
*/
void *sqlite3Malloc_(int n, int bZero, char *zFile, int line){
  void *p;