SQLite

/*
** 2001 September 15
**
** The author disclaims copyright to this source code.  In place of
** 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.54 2002/02/19 15:00:07 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;
  }
  *pRes = 0;
  rc = moveToLeftmost(pCur);
  pCur->bSkipNext = 0;
  return rc;
}

/* Move the cursor to the last entry in the table.  Return SQLITE_OK
** on success.  Set *pRes to 0 if the cursor actually points to something
** or set *pRes to 1 if the table is empty and there is no first element.
*/
int sqliteBtreeLast(BtCursor *pCur, int *pRes){
  int rc;
  Pgno pgno;
  if( pCur->pPage==0 ) return SQLITE_ABORT;
  rc = moveToRoot(pCur);
  if( rc ) return rc;
  if( pCur->pPage->nCell==0 ){
    *pRes = 1;
    return SQLITE_OK;
  }
  *pRes = 0;
  while( (pgno = pCur->pPage->u.hdr.rightChild)!=0 ){
    rc = moveToChild(pCur, pgno);
    if( rc ) return rc;
  }
  pCur->idx = pCur->pPage->nCell-1;
  pCur->bSkipNext = 0;
  return rc;
}

/* Move the cursor so that it points to an entry near pKey.
** Return a success code.
**
** If an exact match is not found, then the cursor is always
** left pointing at a leaf page which would hold the entry if it
** were present.  The cursor might point to an entry that comes

**    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.24 2002/02/19 15:00:08 drh Exp $
*/
#ifndef _BTREE_H_
#define _BTREE_H_

typedef struct Btree Btree;
typedef struct BtCursor BtCursor;

int sqliteBtreeCursor(Btree*, int iTable, int wrFlag, BtCursor **ppCur);
int sqliteBtreeMoveto(BtCursor*, const void *pKey, int nKey, int *pRes);
int sqliteBtreeDelete(BtCursor*);
int sqliteBtreeInsert(BtCursor*, const void *pKey, int nKey,
                                 const void *pData, int nData);
int sqliteBtreeFirst(BtCursor*, int *pRes);
int sqliteBtreeLast(BtCursor*, int *pRes);
int sqliteBtreeNext(BtCursor*, int *pRes);
int sqliteBtreeKeySize(BtCursor*, int *pSize);
int sqliteBtreeKey(BtCursor*, int offset, int amt, char *zBuf);
int sqliteBtreeKeyCompare(BtCursor*, const void *pKey, int nKey,
                          int nIgnore, int *pRes);
int sqliteBtreeDataSize(BtCursor*, int *pSize);
int sqliteBtreeData(BtCursor*, int offset, int amt, char *zBuf);

**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains C code routines that are called by the parser
** to handle SELECT statements in SQLite.
**
** $Id: select.c,v 1.62 2002/02/19 15:00:08 drh Exp $
*/
#include "sqliteInt.h"

/*
** Allocate a new Select structure and return a pointer to that
** structure.
*/

      selectOpName(p->op), " do not have the same number of result columns", 0);
    pParse->nErr++;
    return 1;
  }
  pParse->nTab = base;
  return 0;
}

/*
** Analyze the SELECT statement passed in as an argument to see if it
** is a simple min() or max() query.  If it is and this query can be
** satisfied using a single seek to the beginning or end of an index,
** then generate the code for this SELECT return 1.  If this is not a 
** simple min() or max() query, then return 0;
**
** A simply min() or max() query looks like this:
**
**    SELECT min(a) FROM table;
**    SELECT max(a) FROM table;
**
** The query may have only a single table in its FROM argument.  There
** can be no GROUP BY or HAVING or WHERE clauses.  The result set must
** be the min() or max() of a single column of the table.  The column
** in the min() or max() function must be indexed.
**
** The parameters to this routine are the same as for sqliteSelect().
** See the header comment on that routine for additional information.
*/
static int simpleMinMaxQuery(Parse *pParse, Select *p, int eDest, int iParm){
  Expr *pExpr;
  int iCol;
  Table *pTab;
  Index *pIdx;
  int base;
  Vdbe *v;
  int openOp;
  int seekOp;
  int cont;
  ExprList eList;
  struct ExprList_item eListItem;

  /* Check to see if this query is a simple min() or max() query.  Return
  ** zero if it is  not.
  */
  if( p->pGroupBy || p->pHaving || p->pWhere ) return 0;
  if( p->pSrc->nId!=1 ) return 0;
  if( p->pEList->nExpr!=1 ) return 0;
  pExpr = p->pEList->a[0].pExpr;
  if( pExpr->op!=TK_AGG_FUNCTION ) return 0;
  if( pExpr->pList==0 || pExpr->pList->nExpr!=1 ) return 0;
  if( pExpr->iColumn!=FN_Min && pExpr->iColumn!=FN_Max ) return 0;
  seekOp = pExpr->iColumn==FN_Min ? OP_Rewind : OP_Last;
  pExpr = pExpr->pList->a[0].pExpr;
  if( pExpr->op!=TK_COLUMN ) return 0;
  iCol = pExpr->iColumn;
  pTab = p->pSrc->a[0].pTab;

  /* If we get to here, it means the query is of the correct form.
  ** Check to make sure we have an index.
  */
  if( iCol<0 ){
    pIdx = 0;
  }else{
    for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
      assert( pIdx->nColumn>=1 );
      if( pIdx->aiColumn[0]==iCol ) break;
    }
    if( pIdx==0 ) return 0;
  }

  /* Identify column names if we will be using in the callback.  This
  ** step is skipped if the output is going to a table or a memory cell.
  */
  v = sqliteGetVdbe(pParse);
  if( v==0 ) return 0;
  if( eDest==SRT_Callback ){
    generateColumnNames(pParse, p->pSrc, p->pEList);
  }

  /* Begin generating code
  */
  base = pParse->nTab;
  eList.nExpr = 1;
  memset(&eListItem, 0, sizeof(eListItem));
  eList.a = &eListItem;
  eList.a[0].pExpr = pExpr;
  openOp = pTab->isTemp ? OP_OpenAux : OP_Open;
  sqliteVdbeAddOp(v, openOp, base, pTab->tnum);
  if( pIdx==0 ){
    sqliteVdbeAddOp(v, seekOp, base, 0);
  }else{
    sqliteVdbeAddOp(v, openOp, base+1, pIdx->tnum);
    sqliteVdbeAddOp(v, seekOp, base+1, 0);
    sqliteVdbeAddOp(v, OP_IdxRecno, base+1, 0);
    sqliteVdbeAddOp(v, OP_Close, base+1, 0);
    sqliteVdbeAddOp(v, OP_MoveTo, base, 0);
  }
  cont = sqliteVdbeMakeLabel(v);
  selectInnerLoop(pParse, &eList, base, 1, 0, -1, eDest, iParm, cont, cont);
  sqliteVdbeResolveLabel(v, cont);
  sqliteVdbeAddOp(v, OP_Close, base, 0);
  return 1;
}

/*
** Generate code for the given SELECT statement.
**
** The results are distributed in various ways depending on the
** value of eDest and iParm.
**

    if( sqliteExprResolveIds(pParse, pTabList, pEList, pHaving) ){
      goto select_end;
    }
    if( sqliteExprCheck(pParse, pHaving, isAgg, 0) ){
      goto select_end;
    }
  }

  /* Check for the special case of a min() or max() function by itself
  ** in the result set.
  */
  if( simpleMinMaxQuery(pParse, p, eDest, iParm) ){
    goto select_end;
  }

  /* Begin generating code.
  */
  v = sqliteGetVdbe(pParse);
  if( v==0 ) goto select_end;

  /* Generate code for all sub-queries in the FROM clause

** 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.119 2002/02/19 15:00:08 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

/*
** The following global variable is incremented every time a cursor
** moves, either by the OP_MoveTo or the OP_Next opcode.  The test

static char *zOpName[] = { 0,
  "Transaction",       "Checkpoint",        "Commit",            "Rollback",
  "ReadCookie",        "SetCookie",         "VerifyCookie",      "Open",
  "OpenTemp",          "OpenWrite",         "OpenAux",           "OpenWrAux",
  "Close",             "MoveTo",            "NewRecno",          "PutIntKey",
  "PutStrKey",         "Distinct",          "Found",             "NotFound",
  "IsUnique",          "NotExists",         "Delete",            "Column",
  "KeyAsData",         "Recno",             "FullKey",           "Last",
  "Rewind",            "Next",              "Destroy",           "Clear",
  "CreateIndex",       "CreateTable",       "IntegrityCk",       "IdxPut",
  "IdxDelete",         "IdxRecno",          "IdxGT",             "IdxGE",
  "MemLoad",           "MemStore",          "ListWrite",         "ListRewind",
  "ListRead",          "ListReset",         "SortPut",           "SortMakeRec",
  "SortMakeKey",       "Sort",              "SortNext",          "SortCallback",
  "SortReset",         "FileOpen",          "FileRead",          "FileColumn",
  "AggReset",          "AggFocus",          "AggIncr",           "AggNext",
  "AggSet",            "AggGet",            "SetInsert",         "SetFound",
  "SetNotFound",       "MakeRecord",        "MakeKey",           "MakeIdxKey",
  "IncrKey",           "Goto",              "If",                "Halt",
  "ColumnCount",       "ColumnName",        "Callback",          "NullCallback",
  "Integer",           "String",            "Pop",               "Dup",
  "Pull",              "Push",              "MustBeInt",         "Add",
  "AddImm",            "Subtract",          "Multiply",          "Divide",
  "Remainder",         "BitAnd",            "BitOr",             "BitNot",
  "ShiftLeft",         "ShiftRight",        "AbsValue",          "Precision",
  "Min",               "Max",               "Like",              "Glob",
  "Eq",                "Ne",                "Lt",                "Le",
  "Gt",                "Ge",                "IsNull",            "NotNull",
  "Negative",          "And",               "Or",                "Not",
  "Concat",            "Noop",              "Strlen",            "Substr",
  "Limit",           
};

/*
** Given the name of an opcode, return its number.  Return 0 if
** there is no match.
**
** This routine is used for testing and debugging.

      sqliteBtreeDataSize(pCrsr, &payloadSize);
      xRead = sqliteBtreeData;
    }

    /* Figure out how many bytes in the column data and where the column
    ** data begins.
    */
    if( payloadSize==0 ){
      aStack[tos].flags = STK_Null;
      p->tos = tos;
      break;
    }else if( payloadSize<256 ){
      idxWidth = 1;
    }else if( payloadSize<65536 ){
      idxWidth = 2;
    }else{
      idxWidth = 3;
    }

    }else{
      z = aStack[tos].z;
      aStack[tos].flags = STK_Str;
    }
    sqliteBtreeKey(pCrsr, 0, amt, z);
    zStack[tos] = z;
    aStack[tos].n = amt;
  }
  break;
}

/* Opcode: Last P1 P2 *
**
** The next use of the Recno or Column or Next instruction for P1 
** will refer to the last entry in the database table or index.
** If the table or index is empty and P2>0, then jump immediately to P2.
** If P2 is 0 or if the table or index is not empty, fall through
** to the following instruction.
*/
case OP_Last: {
  int i = pOp->p1;
  BtCursor *pCrsr;

  if( VERIFY( i>=0 && i<p->nCursor && ) (pCrsr = p->aCsr[i].pCursor)!=0 ){
    int res;
    sqliteBtreeLast(pCrsr, &res);
    p->aCsr[i].atFirst = res==0;
    if( res && pOp->p2>0 ){
      pc = pOp->p2 - 1;
    }
  }
  break;
}

/* Opcode: Rewind P1 P2 *
**
** The next use of the Recno or Column or Next instruction for P1 

*************************************************************************
** Header file for the Virtual DataBase Engine (VDBE)
**
** This header defines the interface to the virtual database engine
** or VDBE.  The VDBE implements an abstract machine that runs a
** simple program to access and modify the underlying database.
**
** $Id: vdbe.h,v 1.43 2002/02/19 15:00:08 drh Exp $
*/
#ifndef _SQLITE_VDBE_H_
#define _SQLITE_VDBE_H_
#include <stdio.h>

/*
** A single VDBE is an opaque structure named "Vdbe".  Only routines

#define OP_IsUnique           21
#define OP_NotExists          22
#define OP_Delete             23
#define OP_Column             24
#define OP_KeyAsData          25
#define OP_Recno              26
#define OP_FullKey            27
#define OP_Last               28
#define OP_Rewind             29
#define OP_Next               30

#define OP_Destroy            31
#define OP_Clear              32
#define OP_CreateIndex        33
#define OP_CreateTable        34
#define OP_IntegrityCk        35

#define OP_IdxPut             36
#define OP_IdxDelete          37
#define OP_IdxRecno           38
#define OP_IdxGT              39
#define OP_IdxGE              40

#define OP_MemLoad            41
#define OP_MemStore           42

#define OP_ListWrite          43
#define OP_ListRewind         44
#define OP_ListRead           45
#define OP_ListReset          46

#define OP_SortPut            47
#define OP_SortMakeRec        48
#define OP_SortMakeKey        49
#define OP_Sort               50
#define OP_SortNext           51
#define OP_SortCallback       52
#define OP_SortReset          53

#define OP_FileOpen           54
#define OP_FileRead           55
#define OP_FileColumn         56

#define OP_AggReset           57
#define OP_AggFocus           58
#define OP_AggIncr            59
#define OP_AggNext            60
#define OP_AggSet             61
#define OP_AggGet             62

#define OP_SetInsert          63
#define OP_SetFound           64
#define OP_SetNotFound        65

#define OP_MakeRecord         66
#define OP_MakeKey            67
#define OP_MakeIdxKey         68
#define OP_IncrKey            69

#define OP_Goto               70
#define OP_If                 71
#define OP_Halt               72

#define OP_ColumnCount        73
#define OP_ColumnName         74
#define OP_Callback           75
#define OP_NullCallback       76

#define OP_Integer            77
#define OP_String             78
#define OP_Pop                79
#define OP_Dup                80
#define OP_Pull               81
#define OP_Push               82
#define OP_MustBeInt          83

#define OP_Add                84
#define OP_AddImm             85
#define OP_Subtract           86
#define OP_Multiply           87
#define OP_Divide             88
#define OP_Remainder          89
#define OP_BitAnd             90
#define OP_BitOr              91
#define OP_BitNot             92
#define OP_ShiftLeft          93
#define OP_ShiftRight         94
#define OP_AbsValue           95
#define OP_Precision          96
#define OP_Min                97
#define OP_Max                98
#define OP_Like               99
#define OP_Glob              100
#define OP_Eq                101
#define OP_Ne                102
#define OP_Lt                103
#define OP_Le                104
#define OP_Gt                105
#define OP_Ge                106
#define OP_IsNull            107
#define OP_NotNull           108
#define OP_Negative          109
#define OP_And               110
#define OP_Or                111
#define OP_Not               112
#define OP_Concat            113
#define OP_Noop              114

#define OP_Strlen            115
#define OP_Substr            116

#define OP_Limit             117

#define OP_MAX               117

/*
** Prototypes for the VDBE interface.  See comments on the implementation
** for a description of what each of these routines does.
*/
Vdbe *sqliteVdbeCreate(sqlite*);
void sqliteVdbeCreateCallback(Vdbe*, int*);