SQLite

/*
** 2004 April 6
**
** 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.138 2004/05/14 19:08:18 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.

** function above.
*/
static void releaseTempCursor(BtCursor *pCur){
  if( pCur->pPage ){
    sqlite3pager_unref(pCur->pPage->aData);
  }
}


















/*
** Set *pSize to the size of the buffer needed to hold the value of
** the key for the current entry.  If the cursor is not pointing
** to a valid entry, *pSize is set to 0. 
**
** For a table with the INTKEY flag set, this routine returns the key
** itself, not the number of bytes in the key.
*/
int sqlite3BtreeKeySize(BtCursor *pCur, i64 *pSize){
  MemPage *pPage;
  unsigned char *cell;

  if( !pCur->isValid ){
    *pSize = 0;
  }else{

    pPage = pCur->pPage;
    pageIntegrity(pPage);
    assert( pPage!=0 );
    assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
    cell = pPage->aCell[pCur->idx];
    cell += 2;   /* Skip the offset to the next cell */
    if( !pPage->leaf ){
      cell += 4;  /* Skip the child pointer */
    }
    if( pPage->hasData ){
      while( (0x80&*(cell++))!=0 ){}  /* Skip the data size number */
    }
    getVarint(cell, pSize);
  }
  return SQLITE_OK;
}

/*
** Set *pSize to the number of bytes of data in the entry the
** cursor currently points to.  Always return SQLITE_OK.
** Failure is not possible.  If the cursor is not currently
** pointing to an entry (which can happen, for example, if
** the database is empty) then *pSize is set to 0.
*/
int sqlite3BtreeDataSize(BtCursor *pCur, u32 *pSize){
  MemPage *pPage;
  unsigned char *cell;

  if( !pCur->isValid ){
    /* Not pointing at a valid entry - set *pSize to 0. */
    *pSize = 0;
  }else{
    pPage = pCur->pPage;
    assert( pPage!=0 );
    assert( pPage->isInit );
    pageIntegrity(pPage);
    if( !pPage->hasData ){
      *pSize = 0;
    }else{
      assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
      cell = pPage->aCell[pCur->idx];
      cell += 2;   /* Skip the offset to the next cell */
      if( !pPage->leaf ){
        cell += 4;  /* Skip the child pointer */
      }
      getVarint32(cell, pSize);
    }
  }
  return SQLITE_OK;
}

/*
** Read payload information from the entry that the pCur cursor is
** pointing to.  Begin reading the payload at "offset" and read

  assert( pCur!=0 && pCur->pPage!=0 );
  assert( pCur->isValid );
  pBt = pCur->pBt;
  pPage = pCur->pPage;
  pageIntegrity(pPage);
  assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
  aPayload = pPage->aCell[pCur->idx];
  if( !pCur->infoValid ){
    parseCell(pPage, aPayload, &pCur->info);
    pCur->infoValid = 1;
  }else{
#ifndef NDEBUG
    CellInfo info;
    parseCell(pPage, aPayload, &info);
    assert( memcmp(&info, &pCur->info, sizeof(info))==0 );
#endif
  }
  aPayload += pCur->info.nHeader;
  if( pPage->intKey ){
    nKey = 0;
  }else{
    nKey = pCur->info.nKey;
  }
  assert( offset>=0 );

  assert( pCur!=0 && pCur->pPage!=0 );
  assert( pCur->isValid );
  pBt = pCur->pBt;
  pPage = pCur->pPage;
  pageIntegrity(pPage);
  assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
  aPayload = pPage->aCell[pCur->idx];
  if( !pCur->infoValid ){
    parseCell(pPage, aPayload, &pCur->info);
    pCur->infoValid = 1;
  }else{
#ifndef NDEBUG
    CellInfo info;
    parseCell(pPage, aPayload, &info);
    assert( memcmp(&info, &pCur->info, sizeof(info))==0 );
#endif
  }
  aPayload += pCur->info.nHeader;
  if( pPage->intKey ){
    nKey = 0;
  }else{
    nKey = pCur->info.nKey;
  }
  if( skipKey ){

**
** Various scripts scan this source file in order to generate HTML
** documentation, headers files, or other derived files.  The formatting
** of the code in this file is, therefore, important.  See other comments
** in this file for details.  If in doubt, do not deviate from existing
** commenting and indentation practices when changing or adding code.
**
** $Id: vdbe.c,v 1.291 2004/05/14 15:27:29 drh Exp $
*/
#include "sqliteInt.h"
#include "os.h"
#include <ctype.h>
#include "vdbeInt.h"

/*

  assert( &pTos[1-cnt] >= p->aStack );
  for(i=0; i<cnt && (pTos[1+i-cnt].flags & MEM_Null)==0; i++){}
  if( i>=cnt ) pc = pOp->p2-1;
  if( pOp->p1>0 ) popStack(&pTos, cnt);
  break;
}

/* Opcode: Column3 P1 P2 *
**
** This opcode (not yet in use) is a replacement for the current OP_Column3
** that supports the SQLite3 manifest typing feature.
**
** 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

  Cursor *pC;
  char *zRec;        /* Pointer to record-data from stack or pseudo-table. */
  BtCursor *pCrsr;

  char *zData;       
  int freeZdata = 0; /* zData requires sqliteFree() */

  u64 nFields;       /* number of fields in the record */
  u64 *aTypes;       /* An array of serial types (size nFields) */

  int len;           /* The length of the serialized data for the column */
  int offset;
  int nn;

  assert( i<p->nCursor );
  pTos++;

  /* This block sets the variable payloadSize, and if the data is coming
  ** from the stack or from a pseudo-table zRec. If the data is coming
  ** from a real cursor, then zRec is left as NULL.
  */
  if( i<0 ){
    assert( &pTos[i]>=p->aStack );
    assert( pTos[i].flags & MEM_Str );
    zRec = pTos[i].z;
    payloadSize = pTos[i].n;

  }else if( (pC = &p->aCsr[i])->pCursor!=0 ){
    sqlite3VdbeCursorMoveto(pC);
    zRec = 0;
    pCrsr = pC->pCursor;
    if( pC->nullRow ){
      payloadSize = 0;


    }else if( pC->keyAsData ){
      i64 payloadSize64;
      sqlite3BtreeKeySize(pCrsr, &payloadSize64);
      payloadSize = payloadSize64;
    }else{
      sqlite3BtreeDataSize(pCrsr, &payloadSize);
    }
  }else if( pC->pseudoTable ){
    payloadSize = pC->nData;
    zRec = pC->pData;

    assert( payloadSize==0 || zRec!=0 );
  }else{
    payloadSize = 0;
  }

  /* If payloadSize is 0, then just push a NULL onto the stack. */
  if( payloadSize==0 ){
    pTos->flags = MEM_Null;
    break;
  }

  /* Read the number of fields for the record.
  ** FIX ME: The Cursor object should cache this data and the array of
  ** field types for subsequent OP_Column instructions.
  */


  if( zRec ){
    zData = zRec;
  }else{
    /* We can assume that 9 bytes (maximum length of a varint) fits
    ** on the main page in all cases.
    */


    if( pC->keyAsData ){
      zData = (char *)sqlite3BtreeKeyFetch(pCrsr, 9>payloadSize?payloadSize:9);
    }else{
      zData = (char *)sqlite3BtreeDataFetch(pCrsr, 9>payloadSize?payloadSize:9);
    }
    assert( zData );
  }
  offset = sqlite3GetVarint(zData, &nFields);









  if( !zRec ){
    /* If the record is stored in a table, see if enough of it is on
    ** the main page to use sqlite3BtreeDataFetch() to get the data
    ** containing the nFields serial types (varints). This will almost
    ** always work, but if it doesn't sqliteMalloc() space and use
    ** sqlite3BtreeData().
    **
    ** Estimate the maximum space required by the nFields varints by
    ** assuming the maximum space for each is the length required to store:
    **
    **     (<record length> * 2) + 13
    **
    ** This is the serial-type for a text object as long as the record
    ** itself. In all cases the length required to store this is three
    ** bytes or less. 
    */
    int max_space = sqlite3VarintLen((((u64)payloadSize)<<1)+13)*nFields;
    max_space += offset;
    if( max_space>payloadSize ){
      max_space = payloadSize;
    }

    if( pC->keyAsData ){
      zData = (char *)sqlite3BtreeKeyFetch(pCrsr, max_space);
    }else{
      zData = (char *)sqlite3BtreeDataFetch(pCrsr, max_space);
    }
    if( !zData ){
      /* This code will run very infrequently (e.g. tables with several
      ** hundred columns).
      */
      zData = (char *)sqliteMallocRaw(offset+max_space);
      if( !zData ){
        rc = SQLITE_NOMEM;
        goto abort_due_to_error;
      }
      if( pC->keyAsData ){
        rc = sqlite3BtreeKey(pCrsr, 0, max_space, zData);
      }else{
        rc = sqlite3BtreeData(pCrsr, 0, max_space, zData);
      }
      if( rc!=SQLITE_OK ){
        sqliteFree(zData);
        goto abort_due_to_error;
      }
      freeZdata = 1;
    }
  }

  /* Dynamically allocate space for the aTypes array. and read all
  ** the serial types for the record. At the end of this block variable
  ** offset is set to the offset to the start of Data0 in the record.
  */
  aTypes = (u64 *)sqliteMallocRaw(sizeof(u64)*nFields);
  if( !aTypes ){
    if( freeZdata ){
      sqliteFree(zData);
      freeZdata = 0;
    }
    rc = SQLITE_NOMEM;
    goto abort_due_to_error;
  }
  for(nn=0; nn<nFields; nn++){
    offset += sqlite3GetVarint(&zData[offset], &aTypes[nn]);
  }
 
  if( freeZdata ){
    freeZdata = 0;
    sqliteFree(zData);
  }








  for(nn=0; nn<p2; nn++){
    offset += sqlite3VdbeSerialTypeLen(aTypes[nn]);
  }
  len = sqlite3VdbeSerialTypeLen(aTypes[p2]);

  if( !zRec ){
    /* If the record is stored in a table, see if enough of it
    ** is on the main page to read our column using
    ** sqlite3BtreeDataFetch(). If not sqliteMalloc() space and read data
    ** with sqlite3BtreeData().
    */
    if( pC->keyAsData ){
      zData = (char *)sqlite3BtreeKeyFetch(pCrsr, offset+len);
    }else{
      zData = (char *)sqlite3BtreeDataFetch(pCrsr, offset+len);
    }
    if( !zData && len>0 ){
      zData = (char *)sqliteMallocRaw(len);
      if( !zData ){
        sqliteFree(aTypes);
        rc = SQLITE_NOMEM;
        goto abort_due_to_error;
      }
      if( pC->keyAsData ){
        rc = sqlite3BtreeKey(pCrsr, offset, len, zData);
      }else{
        rc = sqlite3BtreeData(pCrsr, offset, len, zData);
      }
      if( rc!=SQLITE_OK ){
        sqliteFree( aTypes );
        sqliteFree( zData );
        goto abort_due_to_error;
      }
      freeZdata = 1;
      offset = 0;
    }
  }

  /* Deserialize the value directly into the top of the stack */
  sqlite3VdbeSerialGet(&zData[offset], aTypes[p2], pTos);

  sqliteFree(aTypes);
  if( freeZdata ){
    sqliteFree(zData);
  }
  break;
}

/* Opcode MakeRecord P1 * P3

      }
      Stringify(pTos);
      sqlite3BtreeMoveto(pC->pCursor, pTos->z, pTos->n, &res);
      pC->incrKey = 0;
      pC->recnoIsValid = 0;
    }
    pC->deferredMoveto = 0;

    pC->incrKey = 0;
    sqlite3_search_count++;
    oc = pOp->opcode;
    if( oc==OP_MoveTo && res<0 ){
      sqlite3BtreeNext(pC->pCursor, &res);
      pC->recnoIsValid = 0;
      if( res && pOp->p2>0 ){

  if( (pC = &p->aCsr[i])->pCursor!=0 ){
    int res, rx;
    assert( pC->intKey==0 );
    Stringify(pTos);
    rx = sqlite3BtreeMoveto(pC->pCursor, pTos->z, pTos->n, &res);
    alreadyExists = rx==SQLITE_OK && res==0;
    pC->deferredMoveto = 0;

  }
  if( pOp->opcode==OP_Found ){
    if( alreadyExists ) pc = pOp->p2 - 1;
  }else{
    if( !alreadyExists ) pc = pOp->p2 - 1;
  }
  if( pOp->opcode!=OP_Distinct ){

    assert( nKey >= 2 );
    len = nKey-2;
    while( zKey[len] && --len );

    /* Search for an entry in P1 where all but the last four bytes match K.
    ** If there is no such entry, jump immediately to P2.
    */
    assert( p->aCsr[i].deferredMoveto==0 );

    rc = sqlite3BtreeMoveto(pCrsr, zKey, len, &res);
    if( rc!=SQLITE_OK ) goto abort_due_to_error;
    if( res<0 ){
      rc = sqlite3BtreeNext(pCrsr, &res);
      if( res ){
        pc = pOp->p2 - 1;
        break;

** operation assumes the key is an integer and NotFound assumes it
** is a string.
**
** See also: Distinct, Found, MoveTo, NotFound, IsUnique
*/
case OP_NotExists: {
  int i = pOp->p1;

  BtCursor *pCrsr;
  assert( pTos>=p->aStack );
  assert( i>=0 && i<p->nCursor );
  if( (pCrsr = p->aCsr[i].pCursor)!=0 ){
    int res, rx;
    u64 iKey;
    assert( pTos->flags & MEM_Int );
    assert( p->aCsr[i].intKey );
    iKey = intToKey(pTos->i);
    rx = sqlite3BtreeMoveto(pCrsr, 0, iKey, &res);
    p->aCsr[i].lastRecno = pTos->i;
    p->aCsr[i].recnoIsValid = res==0;
    p->aCsr[i].nullRow = 0;

    if( rx!=SQLITE_OK || res!=0 ){
      pc = pOp->p2 - 1;
      p->aCsr[i].recnoIsValid = 0;
    }
  }
  Release(pTos);
  pTos--;
  break;
}

      if( rx==SQLITE_OK && res==0 ){
        rc = SQLITE_FULL;
        goto abort_due_to_error;
      }
    }
    pC->recnoIsValid = 0;
    pC->deferredMoveto = 0;

  }
  pTos++;
  pTos->i = v;
  pTos->flags = MEM_Int;
  break;
}

      }
      pC->nullRow = 0;
    }else{
      rc = sqlite3BtreeInsert(pC->pCursor, zKey, nKey, pTos->z, pTos->n);
    }
    pC->recnoIsValid = 0;
    pC->deferredMoveto = 0;

  }
  popStack(&pTos, 2);
  break;
}

/* Opcode: Delete P1 P2 *
**

  Cursor *pC;
  assert( i>=0 && i<p->nCursor );
  pC = &p->aCsr[i];
  if( pC->pCursor!=0 ){
    sqlite3VdbeCursorMoveto(pC);
    rc = sqlite3BtreeDelete(pC->pCursor);
    pC->nextRowidValid = 0;

  }
  if( pOp->p2 & OPFLAG_NCHANGE ) db->nChange++;
  if( pOp->p2 & OPFLAG_CSCHANGE ) db->csChange++;
  break;
}

/* Opcode: SetCounts * * *

  assert( i>=0 && i<p->nCursor );
  pC = &p->aCsr[i];
  if( (pCrsr = pC->pCursor)!=0 ){
    int res;
    rc = sqlite3BtreeLast(pCrsr, &res);
    pC->nullRow = res;
    pC->deferredMoveto = 0;

    if( res && pOp->p2>0 ){
      pc = pOp->p2 - 1;
    }
  }else{
    pC->nullRow = 0;
  }
  break;

  assert( i>=0 && i<p->nCursor );
  pC = &p->aCsr[i];
  if( (pCrsr = pC->pCursor)!=0 ){
    rc = sqlite3BtreeFirst(pCrsr, &res);
    pC->atFirst = res==0;
    pC->deferredMoveto = 0;

  }else{
    res = 1;
  }
  pC->nullRow = res;
  if( res && pOp->p2>0 ){
    pc = pOp->p2 - 1;
  }

    if( pC->nullRow ){
      res = 1;
    }else{
      assert( pC->deferredMoveto==0 );
      rc = pOp->opcode==OP_Next ? sqlite3BtreeNext(pCrsr, &res) :
                                  sqlite3BtreePrevious(pCrsr, &res);
      pC->nullRow = res;

    }
    if( res==0 ){
      pc = pOp->p2 - 1;
      sqlite3_search_count++;
    }
  }else{
    pC->nullRow = 1;

** If P2==1, then the key must be unique.  If the key is not unique,
** the program aborts with a SQLITE_CONSTRAINT error and the database
** is rolled back.  If P3 is not null, then it becomes part of the
** error message returned with the SQLITE_CONSTRAINT.
*/
case OP_IdxPut: {
  int i = pOp->p1;

  BtCursor *pCrsr;
  assert( pTos>=p->aStack );
  assert( i>=0 && i<p->nCursor );
  assert( pTos->flags & MEM_Str );
  if( (pCrsr = p->aCsr[i].pCursor)!=0 ){
    int nKey = pTos->n;
    const char *zKey = pTos->z;
    if( pOp->p2 ){
      int res;
      int len;
      u64 n;
   
      /* 'len' is the length of the key minus the rowid at the end */
      len = nKey-2;
      while( zKey[len] && --len );

      rc = sqlite3BtreeMoveto(pCrsr, zKey, len, &res);
      if( rc!=SQLITE_OK ) goto abort_due_to_error;
      while( res!=0 ){
        int c;
        sqlite3BtreeKeySize(pCrsr, &n);
        if( n==nKey && 
            sqlite3VdbeIdxKeyCompare(&p->aCsr[i], len, zKey, 0, &c)==SQLITE_OK
            && c==0
        ){
          rc = SQLITE_CONSTRAINT;
          if( pOp->p3 && pOp->p3[0] ){
            sqlite3SetString(&p->zErrMsg, pOp->p3, (char*)0);
          }
          goto abort_due_to_error;
        }
        if( res<0 ){
          sqlite3BtreeNext(pCrsr, &res);
          res = +1;
        }else{
          break;
        }
      }
    }
    assert( p->aCsr[i].intKey==0 );
    rc = sqlite3BtreeInsert(pCrsr, zKey, nKey, "", 0);
    assert( p->aCsr[i].deferredMoveto==0 );

  }
  Release(pTos);
  pTos--;
  break;
}

/* Opcode: IdxDelete P1 * *
**
** The top of the stack is an index key built using the MakeIdxKey opcode.
** This opcode removes that entry from the index.
*/
case OP_IdxDelete: {
  int i = pOp->p1;

  BtCursor *pCrsr;
  assert( pTos>=p->aStack );
  assert( pTos->flags & MEM_Str );
  assert( i>=0 && i<p->nCursor );
  if( (pCrsr = p->aCsr[i].pCursor)!=0 ){
    int rx, res;
    rx = sqlite3BtreeMoveto(pCrsr, pTos->z, pTos->n, &res);
    if( rx==SQLITE_OK && res==0 ){
      rc = sqlite3BtreeDelete(pCrsr);
    }
    assert( p->aCsr[i].deferredMoveto==0 );

  }
  Release(pTos);
  pTos--;
  break;
}

/* Opcode: IdxRecno P1 * *

  Bool zeroData;        /* True if table contains keys only - no data */
  Bool incrKey;         /* Searches on the table simulate OP_IncrKey */
  i64 movetoTarget;     /* Argument to the deferred sqlite3BtreeMoveto() */
  Btree *pBt;           /* Separate file holding temporary table */
  int nData;            /* Number of bytes in pData */
  char *pData;          /* Data for a NEW or OLD pseudo-table */
  i64 iKey;             /* Key for the NEW or OLD pseudo-table row */








};
typedef struct Cursor Cursor;

/*
** A sorter builds a list of elements to be sorted.  Each element of
** the list is an instance of the following structure.
*/

  if( pCx->pCursor ){
    sqlite3BtreeCloseCursor(pCx->pCursor);
  }
  if( pCx->pBt ){
    sqlite3BtreeClose(pCx->pBt);
  }
  sqliteFree(pCx->pData);

  memset(pCx, 0, sizeof(Cursor));
}

/*
** Close all cursors
*/
static void closeAllCursors(Vdbe *p){

    p->lastRecno = keyToInt(p->movetoTarget);
    p->recnoIsValid = res==0;
    if( res<0 ){
      sqlite3BtreeNext(p->pCursor, &res);
    }
    sqlite3_search_count++;
    p->deferredMoveto = 0;

  }
  return SQLITE_OK;
}

/*
** FIX ME
**

#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this file is testing the LIMIT ... OFFSET ... clause
#  of SELECT statements.
#
# $Id: limit.test,v 1.11 2004/03/08 13:26:18 drh Exp $

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

# Build some test data
#
set fd [open data1.txt w]

do_test limit-3.1 {
  execsql {
    SELECT z FROM (SELECT y*10+x AS z FROM t1 ORDER BY x LIMIT 10)
    ORDER BY z LIMIT 5;
  }
} {50 51 52 53 54}


do_test limit-4.1 {
  execsql {
    BEGIN;
    CREATE TABLE t3(x);
    INSERT INTO t3 SELECT x FROM t1 ORDER BY x LIMIT 10 OFFSET 1;
    INSERT INTO t3 SELECT x+(SELECT max(x) FROM t3) FROM t3;
    INSERT INTO t3 SELECT x+(SELECT max(x) FROM t3) FROM t3;