SQLite

** Boston, MA  02111-1307, USA.
**
** Author contact information:
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** $Id: btree.c,v 1.28 2001/09/15 13:15:13 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.

/*
** Primitive data types.  u32 must be 4 bytes and u16 must be 2 bytes.
** The uptr type must be big enough to hold a pointer.
** Change these typedefs when porting to new architectures.
*/
typedef unsigned int uptr;

/* There are already definedin sqliteInt.h...
** typedef unsigned int u32;
** typedef unsigned short int u16;
** typedef unsigned char u8;
*/

/*
** This macro casts a pointer to an integer.  Useful for doing
** pointer arithmetic.
*/
#define Addr(X)  ((uptr)X)

**   http://www.hwaci.com/drh/
**
*************************************************************************
** This header file defines the interface that the sqlite page cache
** subsystem.  The page cache subsystem reads and writes a file a page
** at a time and provides a journal for rollback.
**
** @(#) $Id: pager.h,v 1.10 2001/09/15 13:15:13 drh Exp $
*/

/*
** The size of one page
*/
#define SQLITE_PAGE_SIZE 1024

/*
** Maximum number of pages in one database.  (This is a limitation of
** imposed by 4GB files size limits.)
*/
#define SQLITE_MAX_PAGE 1073741823

/*
** The type used to represent a page number.  The first page in a file
** is called page 1.  0 is used to represent "not a page".
*/
typedef unsigned int Pgno;

/*

**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** This header file defines the interface that the sqlite library
** presents to client programs.
**
** @(#) $Id: sqlite.h.in,v 1.16 2001/09/15 13:15:13 drh Exp $
*/
#ifndef _SQLITE_H_
#define _SQLITE_H_
#include <stdarg.h>     /* Needed for the definition of va_list */

/*
** The version of the SQLite library.

#define SQLITE_CORRUPT   10   /* The database disk image is malformed */
#define SQLITE_NOTFOUND  11   /* Table or record not found */
#define SQLITE_FULL      12   /* Insertion failed because database is full */
#define SQLITE_CANTOPEN  13   /* Unable to open the database file */
#define SQLITE_PROTOCOL  14   /* Database lock protocol error */
#define SQLITE_EMPTY     15   /* Database table is empty */
#define SQLITE_SCHEMA    16   /* The database schema changed */
#define SQLITE_TOOBIG    17   /* Too much data for one row of a table */

/* This function causes any pending database operation to abort and
** return at its earliest opportunity.  This routine is typically
** called in response to a user action such as pressing "Cancel"
** or Ctrl-C where the user wants a long query operation to halt
** immediately.
*/

** Author contact information:
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** Internal interface definitions for SQLite.
**
** @(#) $Id: sqliteInt.h,v 1.49 2001/09/15 13:15:13 drh Exp $
*/
#include "sqlite.h"
#include "vdbe.h"
#include "parse.h"
#include "btree.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

/*
** The maximum number of in-memory pages to use for the main database
** table and for temporary tables.
*/
#define MAX_PAGES   100
#define TEMP_PAGES   25

/*
** Integers of known sizes.  These typedefs much change for architectures
** where the sizes very.
*/
typedef unsigned int u32;             /* 4-byte unsigned integer */
typedef unsigned short int u16;       /* 2-byte unsigned integer */
typedef unsigned char u8;             /* 1-byte unsigned integer */

/*
** If memory allocation problems are found, recompile with
**
**      -DMEMORY_DEBUG=1
**
** to enable some sanity checking on malloc() and free().  To

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

/*
** If malloc() ever fails, this global variable gets set to 1.

    case SQLITE_CORRUPT:    z = "database disk image is malformed";      break;
    case SQLITE_NOTFOUND:   z = "table or record not found";             break;
    case SQLITE_FULL:       z = "database is full";                      break;
    case SQLITE_CANTOPEN:   z = "unable to open database file";          break;
    case SQLITE_PROTOCOL:   z = "database locking protocol failure";     break;
    case SQLITE_EMPTY:      z = "table contains no data";                break;
    case SQLITE_SCHEMA:     z = "database schema has changed";           break;
    case SQLITE_TOOBIG:     z = "too much data for one table row";       break;
    default:                z = "unknown error";                         break;
  }
  return z;
}

** inplicit conversion from one type to the other occurs as necessary.
** 
** Most of the code in this file is taken up by the sqliteVdbeExec()
** function which does the work of interpreting a VDBE program.
** But other routines are also provided to help in building up
** a program instruction by instruction.
**
** $Id: vdbe.c,v 1.68 2001/09/15 13:15:13 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>
#include <unistd.h>

/*
** SQL is translated into a sequence of instructions to be

** Hence, a negative P2 value is a label that has yet to be resolved.
*/
int sqliteVdbeMakeLabel(Vdbe *p){
  int i;
  i = p->nLabel++;
  if( i>=p->nLabelAlloc ){
    p->nLabelAlloc = p->nLabelAlloc*2 + 10;
    p->aLabel = sqliteRealloc( p->aLabel, p->nLabelAlloc*sizeof(p->aLabel[0]));
  }
  if( p->aLabel==0 ){
    p->nLabel = 0;
    p->nLabelAlloc = 0;
    return 0;
  }
  p->aLabel[i] = -1;

}

/* Opcode: MakeRecord P1 * *
**
** Convert the top P1 entries of the stack into a single entry
** suitable for use as a data record in a database table.  To do this
** all entries (except NULLs) are converted to strings and 
** concatenated.  The null-terminators are included on all string
** except for NULL columns which are represented by zero bytes.
** The lowest entry
** on the stack is the first in the concatenation and the top of
** the stack is the last.  After all columns are concatenated, an
** index header is added.  The index header consists of P1 16-bit integers
** which hold the offset of the beginning of each column data from the
** beginning of the completed record including the header.

**
** The OP_Column opcode is used to unpack a record manufactured with
** the opcode.
*/
case OP_MakeRecord: {
  char *zNewRecord;
  int nByte;
  int nField;
  int i, j;
  u16 addr;

  nField = pOp->p1;
  VERIFY( if( p->tos+1<nField ) goto not_enough_stack; )
  nByte = 0;
  for(i=p->tos-nField+1; i<=p->tos; i++){
    if( (aStack[i].flags & STK_Null)==0 ){
      if( Stringify(p, i) ) goto no_mem;
      nByte += aStack[i].n;
    }
  }
  nByte += sizeof(addr)*nField;
  if( nByte>65535 ){
    rc = SQLITE_TOOBIG;
    goto abort_due_to_error;
  }
  zNewRecord = sqliteMalloc( nByte );
  if( zNewRecord==0 ) goto no_mem;
  j = 0;
  addr = sizeof(addr)*nField;
  for(i=p->tos-nField+1; i<=p->tos; i++){
    memcpy(&zNewRecord[j], (char*)&addr, sizeof(addr));
    j += sizeof(addr);
    if( (aStack[i].flags & STK_Null)==0 ){
      addr += aStack[i].n;
    }
  }
  for(i=p->tos-nField+1; i<=p->tos; i++){
    if( (aStack[i].flags & STK_Null)==0 ){
      memcpy(&zNewRecord[j], zStack[i], aStack[i].n);

  char *zNewKey;
  int nByte;
  int nField;
  int i, j;

  nField = pOp->p1;
  VERIFY( if( p->tos+1<nField ) goto not_enough_stack; )
  nByte = sizeof(u32);
  for(i=p->tos-nField+1; i<=p->tos; i++){
    if( aStack[i].flags & STK_Null ){
      nByte++;
    }else{
      if( Stringify(p, i) ) goto no_mem;
      nByte += aStack[i].n;
    }
  }
  zNewKey = sqliteMalloc( nByte );
  if( zNewKey==0 ) goto no_mem;
  j = 0;
  for(i=p->tos-nField+1; i<=p->tos; i++){
    if( (aStack[i].flags & STK_Null)==0 ){
      memcpy(&zNewKey[j], zStack[i], aStack[i].n-1);
      j += aStack[i].n-1;
    }
    if( i<p->tos ) zNewKey[j++] = '\t';
  }
  zNewKey[j++] = 0;
  Integerify(p, p->tos-nField);
  memcpy(&zNewKey[j], &aStack[p->tos-nField].i, sizeof(u32));
  PopStack(p, nField+1);
  VERIFY( NeedStack(p, p->tos+1); )
  p->tos++;
  aStack[p->tos].n = nByte;
  aStack[p->tos].flags = STK_Str|STK_Dyn;
  zStack[p->tos] = zNewKey;
  break;

    p->aCsr[i].keyAsData = pOp->p2;
  }
  break;
}

/* Opcode: Column P1 P2 *
**
** Interpret the data that cursor P1 points to as
** a structure built using the MakeRecord instruction.
** (See the MakeRecord opcode for additional information about
** the format of the data.)
** Push onto the stack the value of the P2-th column contained

** in the data.




**
** If the KeyAsData opcode has previously executed on this cursor,
** then the field might be extracted from the key rather than the
** data.
*/
case OP_Column: {
  int amt, offset, nCol, payloadSize;
  u16 aHdr[10];
  static const int mxHdr = sizeof(aHdr)/sizeof(aHdr[0]);
  int i = pOp->p1;
  int p2 = pOp->p2;
  int tos = p->tos+1;
  BtCursor *pCrsr;
  char *z;

    ** The code is complicated by efforts to minimize the number
    ** of invocations of xRead() since that call can be expensive.
    ** For the common case where P2 is small, xRead() is invoked
    ** twice.  For larger values of P2, it has to be called
    ** three times.
    */
    (*xSize)(pCrsr, &payloadSize);
    if( payloadSize < sizeof(aHdr[0])*(p2+1) ){
      rc = SQLITE_CORRUPT;
      goto abort_due_to_error;
    }
    if( p2+1<mxHdr ){
      (*xRead)(pCrsr, 0, sizeof(aHdr[0])*(p2+2), (char*)aHdr);
      nCol = aHdr[0];
      nCol /= sizeof(aHdr[0]);
      offset = aHdr[p2];
      if( p2 == nCol-1 ){
        amt = payloadSize - offset;
      }else{
        amt = aHdr[p2+1] - offset;
      }
    }else{
      sqliteBtreeData(pCrsr, 0, sizeof(aHdr[0]), (char*)aHdr);
      nCol = aHdr[0]/sizeof(aHdr[0]);
      if( p2 == nCol-1 ){
        (*xRead)(pCrsr, sizeof(aHdr[0])*p2, sizeof(aHdr[0]), (char*)aHdr);
        offset = aHdr[0];
        amt = payloadSize - offset;
      }else{
        (*xRead)(pCrsr, sizeof(aHdr[0])*p2, sizeof(aHdr[0])*2, (char*)aHdr);
        offset = aHdr[0];
        amt = aHdr[1] - offset;
      }
    }
    if( payloadSize < nCol || amt<0 || offset<0 ){
      rc = SQLITE_CORRUPT;
      goto abort_due_to_error;
    }

    /* amt and offset now hold the offset to the start of data and the
    ** amount of data.  Go get the data and put it on the stack.
    */
    if( amt==0 ){
      aStack[tos].flags = STK_Null;
    }else{
      z = sqliteMalloc( amt );
      if( z==0 ) goto no_mem;
      (*xRead)(pCrsr, offset, amt, z);
      aStack[tos].flags = STK_Str | STK_Dyn;

  VERIFY( if( NeedStack(p, p->tos) ) goto no_mem; )
  if( VERIFY( i>=0 && i<p->nCursor && ) (pCrsr = p->aCsr[i].pCursor)!=0 ){
    int v;
    if( p->aCsr[i].recnoIsValid ){
      v = p->aCsr[i].lastRecno;
    }else{
      sqliteBtreeKey(pCrsr, 0, sizeof(u32), (char*)&v);
    }
    aStack[tos].i = v;
    aStack[tos].flags = STK_Int;
  }
  break;
}

      pCrsr->atFirst = 0;
      res = 0;
    }else{
      rx = sqliteBtreeNext(pCur, &res);
      if( rx!=SQLITE_OK ) goto abort_due_to_error;
    }
    sqliteBtreeKeySize(pCur, &size);
    if( res>0 || size!=pCrsr->nKey+sizeof(u32) ||
      sqliteBtreeKey(pCur, 0, pCrsr->nKey, pCrsr->zBuf)!=pCrsr->nKey ||
      strncmp(pCrsr->zKey, pCrsr->zBuf, pCrsr->nKey)!=0
    ){
      pc = pOp->p2 - 1;
      POPSTACK;
    }else{
      int recno;
      sqliteBtreeKey(pCur, pCrsr->nKey, sizeof(u32), (char*)&recno);
      p->aCsr[i].lastRecno = aStack[tos].i = recno;
      p->aCsr[i].recnoIsValid = 1;
      aStack[tos].flags = STK_Int;
    }
  }
  break;
}

case OP_ListWrite: {
  int i = pOp->p1;
  Keylist *pKeylist;
  VERIFY( if( i<0 || i>=p->nList ) goto bad_instruction; )
  VERIFY( if( p->tos<0 ) goto not_enough_stack; )
  pKeylist = p->apList[i];
  if( pKeylist==0 || pKeylist->nUsed>=pKeylist->nKey ){
    pKeylist = sqliteMalloc( sizeof(Keylist)+999*sizeof(pKeylist->aKey[0]) );
    if( pKeylist==0 ) goto no_mem;
    pKeylist->nKey = 1000;
    pKeylist->nRead = 0;
    pKeylist->nUsed = 0;
    pKeylist->pNext = p->apList[i];
    p->apList[i] = pKeylist;
  }

        if( aStack[i].flags & STK_Null ){
          fprintf(p->trace, " NULL");
        }else if( aStack[i].flags & STK_Int ){
          fprintf(p->trace, " i:%d", aStack[i].i);
        }else if( aStack[i].flags & STK_Real ){
          fprintf(p->trace, " r:%g", aStack[i].r);
        }else if( aStack[i].flags & STK_Str ){
          int j, k;
          char zBuf[100];
          zBuf[0] = ' ';
          zBuf[1] = (aStack[i].flags & STK_Dyn)!=0 ? 'z' : 's';
          zBuf[2] = ':';
          k = 3;
          for(j=0; j<15 && j<aStack[i].n; j++){
            int c = zStack[i][j];
            if( c==0 && j==aStack[i].n-1 ) break;
            if( isprint(c) && !isspace(c) ){
              zBuf[k++] = c;
            }else{

              zBuf[k++] = '.';
            }
          }
          zBuf[k++] = 0;
          fprintf(p->trace, "%s", zBuf);
        }else{
          fprintf(p->trace, " ???");
        }
      }
      fprintf(p->trace,"\n");
    }
#endif