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.328 2006/08/16 16:42:48 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.

  void *pArg;               /* First arg to xCompare() */
  Pgno pgnoRoot;            /* The root page of this tree */
  MemPage *pPage;           /* Page that contains the entry */
  int idx;                  /* Index of the entry in pPage->aCell[] */
  CellInfo info;            /* A parse of the cell we are pointing at */
  u8 wrFlag;                /* True if writable */
  u8 eState;                /* One of the CURSOR_XXX constants (see below) */

  void *pKey;      /* Saved key that was cursor's last known position */
  i64 nKey;        /* Size of pKey, or last integer key */
  int skip;        /* (skip<0) -> Prev() is a no-op. (skip>0) -> Next() is */

};

/*
** Potential values for BtCursor.eState.


**
** CURSOR_VALID:
**   Cursor points to a valid entry. getPayload() etc. may be called.
**
** CURSOR_INVALID:
**   Cursor does not point to a valid entry. This can happen (for example) 
**   because the table is empty or because BtreeCursorFirst() has not been

#else
# define TRACE(X)
#endif

/*
** Forward declaration
*/
static int checkReadLocks(Btree*,Pgno,BtCursor*);

/*
** Read or write a two- and four-byte big-endian integer values.
*/
static u32 get2byte(unsigned char *p){
  return (p[0]<<8) | p[1];
}

  ** shared-cache feature disabled, then there is only ever one user
  ** of each BtShared structure and so this locking is not necessary. 
  ** So define the lock related functions as no-ops.
  */
  #define queryTableLock(a,b,c) SQLITE_OK
  #define lockTable(a,b,c) SQLITE_OK
  #define unlockAllTables(a)



#else
































































































/*
** Query to see if btree handle p may obtain a lock of type eLock 
** (READ_LOCK or WRITE_LOCK) on the table with root-page iTab. Return
** SQLITE_OK if the lock may be obtained (by calling lockTable()), or
** SQLITE_LOCKED if not.
*/

    }else{
      ppIter = &pLock->pNext;
    }
  }
}
#endif /* SQLITE_OMIT_SHARED_CACHE */

static void releasePage(MemPage *pPage);  /* Forward reference */

/*
** Save the current cursor position in the variables BtCursor.nKey 
** and BtCursor.pKey. The cursor's state is set to CURSOR_REQUIRESEEK.
*/
static int saveCursorPosition(BtCursor *pCur){
  int rc;

  assert( CURSOR_VALID==pCur->eState );
  assert( 0==pCur->pKey );

  rc = sqlite3BtreeKeySize(pCur, &pCur->nKey);

  /* If this is an intKey table, then the above call to BtreeKeySize()
  ** stores the integer key in pCur->nKey. In this case this value is
  ** all that is required. Otherwise, if pCur is not open on an intKey
  ** table, then malloc space for and store the pCur->nKey bytes of key 
  ** data.
  */
  if( rc==SQLITE_OK && 0==pCur->pPage->intKey){
    void *pKey = sqliteMalloc(pCur->nKey);
    if( pKey ){
      rc = sqlite3BtreeKey(pCur, 0, pCur->nKey, pKey);
      if( rc==SQLITE_OK ){
        pCur->pKey = pKey;
      }else{
        sqliteFree(pKey);
      }
    }else{
      rc = SQLITE_NOMEM;
    }
  }
  assert( !pCur->pPage->intKey || !pCur->pKey );

  if( rc==SQLITE_OK ){
    releasePage(pCur->pPage);
    pCur->pPage = 0;
    pCur->eState = CURSOR_REQUIRESEEK;
  }

  return rc;
}

/*
** Save the positions of all cursors except pExcept open on the table 
** with root-page iRoot. Usually, this is called just before cursor
** pExcept is used to modify the table (BtreeDelete() or BtreeInsert()).
*/
static int saveAllCursors(BtShared *pBt, Pgno iRoot, BtCursor *pExcept){
  BtCursor *p;
  for(p=pBt->pCursor; p; p=p->pNext){
    if( p!=pExcept && (0==iRoot || p->pgnoRoot==iRoot) && 
        p->eState==CURSOR_VALID ){
      int rc = saveCursorPosition(p);
      if( SQLITE_OK!=rc ){
        return rc;
      }
    }
  }
  return SQLITE_OK;
}

/*
** Restore the cursor to the position it was in (or as close to as possible)
** when saveCursorPosition() was called. Note that this call deletes the 
** saved position info stored by saveCursorPosition(), so there can be
** at most one effective restoreOrClearCursorPosition() call after each 
** saveCursorPosition().
**
** If the second argument argument - doSeek - is false, then instead of 
** returning the cursor to it's saved position, any saved position is deleted
** and the cursor state set to CURSOR_INVALID.
*/
static int restoreOrClearCursorPositionX(BtCursor *pCur, int doSeek){
  int rc = SQLITE_OK;
  assert( pCur->eState==CURSOR_REQUIRESEEK );
  pCur->eState = CURSOR_INVALID;
  if( doSeek ){
    rc = sqlite3BtreeMoveto(pCur, pCur->pKey, pCur->nKey, &pCur->skip);
  }
  if( rc==SQLITE_OK ){
    sqliteFree(pCur->pKey);
    pCur->pKey = 0;
    assert( CURSOR_VALID==pCur->eState || CURSOR_INVALID==pCur->eState );
  }
  return rc;
}

#define restoreOrClearCursorPosition(p,x) \
  (p->eState==CURSOR_REQUIRESEEK?restoreOrClearCursorPositionX(p,x):SQLITE_OK)

#ifndef SQLITE_OMIT_AUTOVACUUM
/*
** These macros define the location of the pointer-map entry for a 
** database page. The first argument to each is the number of usable
** bytes on each page of the database (often 1024). The second is the
** page number to look up in the pointer map.
**

  /* Set the variable isMemdb to true for an in-memory database, or 
  ** false for a file-based database. This symbol is only required if
  ** either of the shared-data or autovacuum features are compiled 
  ** into the library.
  */
#if !defined(SQLITE_OMIT_SHARED_CACHE) || !defined(SQLITE_OMIT_AUTOVACUUM)
  #ifdef SQLITE_OMIT_MEMORYDB
    const int isMemdb = 0;
  #else
    const int isMemdb = zFilename && !strcmp(zFilename, ":memory:");
  #endif
#endif

  p = sqliteMalloc(sizeof(Btree));
  if( !p ){
    return SQLITE_NOMEM;
  }

  BtShared *pBt = p->pBt;

  *ppCur = 0;
  if( wrFlag ){
    if( pBt->readOnly ){
      return SQLITE_READONLY;
    }
    if( checkReadLocks(p, iTable, 0) ){
      return SQLITE_LOCKED;
    }
  }

  if( pBt->pPage1==0 ){
    rc = lockBtreeWithRetry(p);
    if( rc!=SQLITE_OK ){

    }
  }
  return rc;
}

/*
** This routine checks all cursors that point to table pgnoRoot.
** If any of those cursors were opened with wrFlag==0 in a different
** database connection (a database connection that shares the pager
** cache with the current connection) and that other connection 
** is not in the ReadUncommmitted state, then this routine returns 

** SQLITE_LOCKED.
**
** In addition to checking for read-locks (where a read-lock 
** means a cursor opened with wrFlag==0) this routine also moves
** all cursors write cursors so that they are pointing to the 
** first Cell on the root page.  This is necessary because an insert 
** or delete might change the number of cells on a page or delete
** a page entirely and we do not want to leave any cursors 
** pointing to non-existant pages or cells.
*/
static int checkReadLocks(Btree *pBtree, Pgno pgnoRoot, BtCursor *pExclude){
  BtCursor *p;
  BtShared *pBt = pBtree->pBt;
  sqlite3 *db = pBtree->pSqlite;
  for(p=pBt->pCursor; p; p=p->pNext){

    if( p==pExclude ) continue;
    if( p->eState!=CURSOR_VALID ) continue;
    if( p->pgnoRoot!=pgnoRoot ) continue;
    if( p->wrFlag==0 ){
      sqlite3 *dbOther = p->pBtree->pSqlite;
      if( dbOther==0 ||
         (dbOther!=db && (dbOther->flags & SQLITE_ReadUncommitted)==0) ){
        return SQLITE_LOCKED;
      }
    }else if( p->pPage->pgno!=p->pgnoRoot ){
      moveToRoot(p);
    }
  }
  return SQLITE_OK;
}

/*

    /* Must start a transaction before doing an insert */
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }
  assert( !pBt->readOnly );
  if( !pCur->wrFlag ){
    return SQLITE_PERM;   /* Cursor not open for writing */
  }
  if( checkReadLocks(pCur->pBtree, pCur->pgnoRoot, pCur) ){
    return SQLITE_LOCKED; /* The table pCur points to has a read lock */
  }

  /* Save the positions of any other cursors open on this table */
  restoreOrClearCursorPosition(pCur, 0);
  if( 
    SQLITE_OK!=(rc = saveAllCursors(pBt, pCur->pgnoRoot, pCur)) ||

  assert( !pBt->readOnly );
  if( pCur->idx >= pPage->nCell ){
    return SQLITE_ERROR;  /* The cursor is not pointing to anything */
  }
  if( !pCur->wrFlag ){
    return SQLITE_PERM;   /* Did not open this cursor for writing */
  }
  if( checkReadLocks(pCur->pBtree, pCur->pgnoRoot, pCur) ){
    return SQLITE_LOCKED; /* The table pCur points to has a read lock */
  }

  /* Restore the current cursor position (a no-op if the cursor is not in 
  ** CURSOR_REQUIRESEEK state) and save the positions of any other cursors 
  ** open on the same table. Then call sqlite3pager_write() on the page
  ** that the entry will be deleted from.

**
** This routine will fail with SQLITE_LOCKED if there are any open
** read cursors on the table.  Open write cursors are moved to the
** root of the table.
*/
int sqlite3BtreeClearTable(Btree *p, int iTable){
  int rc;

  BtShared *pBt = p->pBt;

  if( p->inTrans!=TRANS_WRITE ){
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }
  rc = checkReadLocks(p, iTable, 0);






  if( rc ){
    return rc;




  }

  /* Save the position of all cursors open on this table */
  if( SQLITE_OK!=(rc = saveAllCursors(pBt, iTable, 0)) ){
    return rc;
  }

# 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.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this script is btree database backend
#
# $Id: btree.test,v 1.37 2006/08/16 16:42:48 drh Exp $


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

ifcapable default_autovacuum {
  finish_test

  catch {btree_insert $::c1 101 helloworld} msg
  set msg
} {SQLITE_PERM}
do_test btree-16.10 {
  catch {btree_delete $::c1} msg
  set msg
} {SQLITE_PERM}

# As of 2006-08-16 (version 3.3.7+) a read cursor will no
# longer block a write cursor from the same database
# connectiin.  The following three tests uses to return
# the SQLITE_LOCK error, but no more.
#
do_test btree-16.11 {
  btree_close_cursor $::c1
  set ::c2 [btree_cursor $::b1 2 1]
  set ::c1 [btree_cursor $::b1 2 0]
  catch {btree_insert $::c2 101 helloworld} msg
  set msg
} {}
do_test btree-16.12 {
  btree_first $::c2
  catch {btree_delete $::c2} msg
  set msg
} {}
do_test btree-16.13 {
  catch {btree_clear_table $::b1 2} msg
  set msg
} {}


do_test btree-16.14 {
  btree_close_cursor $::c1
  btree_close_cursor $::c2
  btree_commit $::b1
  catch {btree_clear_table $::b1 2} msg
  set msg
} {SQLITE_ERROR}

# 2003 January 29
#
# 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.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this script testing the callback-free C/C++ API.
#
# $Id: capi2.test,v 1.32 2006/08/16 16:42:48 drh Exp $
#

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

# Return the text values from the current row pointed at by STMT as a list.
proc get_row_values {STMT} {

do_test capi2-6.12 {
  list [sqlite3_step $VM1] \
       [sqlite3_column_count $VM1] \
       [get_row_values $VM1] \
       [get_column_names $VM1]
} {SQLITE_ROW 1 5 {x counter}}

# A read no longer blocks a write in the same connection.
#do_test capi2-6.13 {
#  catchsql {UPDATE t3 SET x=x+1}
#} {1 {database table is locked}}

do_test capi2-6.14 {
  list [sqlite3_step $VM1] \
       [sqlite3_column_count $VM1] \
       [get_row_values $VM1] \
       [get_column_names $VM1]
} {SQLITE_ROW 1 6 {x counter}}
do_test capi2-6.15 {

# 2003 January 29
#
# 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.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this script testing the callback-free C/C++ API.
#
# $Id: capi3.test,v 1.46 2006/08/16 16:42:48 drh Exp $
#

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

# Return the UTF-16 representation of the supplied UTF-8 string $str.
# If $nt is true, append two 0x00 bytes as a nul terminator.

} {0 {}}
do_test capi3-11.21 {
  sqlite3_finalize $STMT
} {SQLITE_OK}

# The following tests - capi3-12.* - check that it's Ok to start a
# transaction while other VMs are active, and that it's Ok to execute
# atomic updates in the same situation 

#
do_test capi3-12.1 {
  set STMT [sqlite3_prepare $DB "SELECT a FROM t2" -1 TAIL]
  sqlite3_step $STMT
} {SQLITE_ROW}
do_test capi3-12.2 {
  catchsql {
    INSERT INTO t1 VALUES(3, NULL);
  }
} {0 {}}

do_test capi3-12.3 {
  catchsql {
    INSERT INTO t2 VALUES(4);
  }
} {0 {}}
do_test capi3-12.4 {
  catchsql {
    BEGIN;
    INSERT INTO t1 VALUES(4, NULL);
  }
} {0 {}}
do_test capi3-12.5 {
  sqlite3_step $STMT
} {SQLITE_ROW}
do_test capi3-12.5.1 {
  sqlite3_step $STMT
} {SQLITE_ROW}
do_test capi3-12.6 {
  sqlite3_step $STMT
} {SQLITE_DONE}
do_test capi3-12.7 {
  sqlite3_finalize $STMT
} {SQLITE_OK}

# index entry was deleted first, before the table entry.  And the index
# delete worked.  Thus an entry was deleted from the index but not from
# the table.
#
# The solution to the problem was to detect that the table is locked
# before the index entry is deleted.
#
# $Id: delete2.test,v 1.7 2006/08/16 16:42:48 drh Exp $
#

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

# Create a table that has an index.
#

#
do_test delete2-1.4 {
  set STMT [sqlite3_prepare $DB {SELECT * FROM q} -1 TAIL]
  sqlite3_step $STMT
} SQLITE_ROW
integrity_check delete2-1.5

# Try to delete a row from the table while a read is in process.
# As of 2006-08-16, this is allowed.  (It used to fail with SQLITE_LOCKED.)
#

do_test delete2-1.6 {
  catchsql {
    DELETE FROM q WHERE rowid=1
  }
} {0 {}}
integrity_check delete2-1.7
do_test delete2-1.8 {
  execsql {
    SELECT * FROM q;
  }
} {goodbye id.2 again id.3}

# Finalize the query, thus clearing the lock on the table.  Then
# retry the delete.  The delete should work this time.
#
do_test delete2-1.9 {
  sqlite3_finalize $STMT
  catchsql {

# 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.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this script is database locks.
#
# $Id: lock.test,v 1.33 2006/08/16 16:42:48 drh Exp $


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

# Create an alternative connection to the database
#

    set x [db eval {SELECT * FROM t2}]
  }
  set x
} {8 9}

# You cannot UPDATE a table from within the callback of a SELECT
# on that same table because the SELECT has the table locked.
#
# 2006-08-16:  Reads no longer block writes within the same
# database connection.
#
#do_test lock-1.18 {
#  db eval {SELECT * FROM t1} qv {
#    set r [catch {db eval {UPDATE t1 SET a=b, b=a}} msg]
#    lappend r $msg

#  }
#  set r
#} {1 {database table is locked}}

# But you can UPDATE a different table from the one that is used in
# the SELECT.
#
do_test lock-1.19 {
  db eval {SELECT * FROM t1} qv {
    set r [catch {db eval {UPDATE t2 SET x=y, y=x}} msg]

#
#***********************************************************************
# This file implements regression tests for SQLite library.
#
# This file implements tests for miscellanous features that were
# left out of other test files.
#
# $Id: misc2.test,v 1.25 2006/08/16 16:42:48 drh Exp $

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

ifcapable {trigger} {
# Test for ticket #360
#

  }
} {1 2}

# Make sure we get an error message (not a segfault) on an attempt to
# update a table from within the callback of a select on that same
# table.
#
# 2006-08-16:  This has changed.  It is now permitted to update
# the table being SELECTed from within the callback of the query.
#
do_test misc2-7.1 {
  db close
  file delete -force test.db
  sqlite3 db test.db
  execsql {
    CREATE TABLE t1(x);
    INSERT INTO t1 VALUES(1);
    INSERT INTO t1 VALUES(2);
    INSERT INTO t1 VALUES(3);
    SELECT * FROM t1;
  }
} {1 2 3}
do_test misc2-7.2 {
  set rc [catch {
    db eval {SELECT rowid FROM t1} {} {
      db eval "DELETE FROM t1 WHERE rowid=$rowid"
    }
  } msg]
  lappend rc $msg
} {0 {}}
do_test misc2-7.3 {
  execsql {SELECT * FROM t1}
} {}
do_test misc2-7.4 {
  execsql {
    DELETE FROM t1;
    INSERT INTO t1 VALUES(1);
    INSERT INTO t1 VALUES(2);
    INSERT INTO t1 VALUES(3);
    INSERT INTO t1 VALUES(4);
  }
  db eval {SELECT rowid, x FROM t1} {
    if {$x & 1} {
      db eval {DELETE FROM t1 WHERE rowid=$rowid}
    }
  }
  execsql {SELECT * FROM t1}
} {2 4}
do_test misc2-7.5 {
  execsql {
    DELETE FROM t1;
    INSERT INTO t1 VALUES(1);
    INSERT INTO t1 VALUES(2);
    INSERT INTO t1 VALUES(3);
    INSERT INTO t1 VALUES(4);
  }
  db eval {SELECT rowid, x FROM t1} {
    if {$x & 1} {

      db eval {DELETE FROM t1 WHERE rowid=$rowid+1}
    }
  }
  execsql {SELECT * FROM t1}
} {1 3}

do_test misc2-7.6 {

  execsql {
    DELETE FROM t1;
    INSERT INTO t1 VALUES(1);
    INSERT INTO t1 VALUES(2);
    INSERT INTO t1 VALUES(3);
    INSERT INTO t1 VALUES(4);
  }

  db eval {SELECT rowid, x FROM t1} {
    if {$x & 1} {
      db eval {DELETE FROM t1}
    }
  }
  execsql {SELECT * FROM t1}
} {}


do_test misc2-7.7 {

  execsql {
    DELETE FROM t1;
    INSERT INTO t1 VALUES(1);
    INSERT INTO t1 VALUES(2);
    INSERT INTO t1 VALUES(3);
    INSERT INTO t1 VALUES(4);
  }
  db eval {SELECT rowid, x FROM t1} {
    if {$x & 1} {
      db eval {UPDATE t1 SET x=x+100 WHERE rowid=$rowid}
    }
  }
  execsql {SELECT * FROM t1}
} {101 2 103 4}
do_test misc2-7.8 {
  execsql {
    DELETE FROM t1;
    INSERT INTO t1 VALUES(1);
  }
  db eval {SELECT rowid, x FROM t1} {

    if {$x<10} {
      db eval {INSERT INTO t1 VALUES($x+1)}
    }
  }
  execsql {SELECT * FROM t1}
} {1 2 3 4 5 6 7 8 9 10}

db close
file delete -force test.db
sqlite3 db test.db

# Ticket #453.  If the SQL ended with "-", the tokenizer was calling that
# an incomplete token, which caused problem.  The solution was to just call