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.74 2002/12/04 13:40:26 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.

  Btree *pBt;               /* The Btree to which this cursor belongs */
  BtCursor *pNext, *pPrev;  /* Forms a linked list of all cursors */
  BtCursor *pShared;        /* Loop of cursors with the same root page */
  Pgno pgnoRoot;            /* The root page of this tree */
  MemPage *pPage;           /* Page that contains the entry */
  int idx;                  /* Index of the entry in pPage->apCell[] */
  u8 wrFlag;                /* True if writable */
  u8 eSkip;                 /* Determines if next step operation is a no-op */
  u8 iMatch;                /* compare result from last sqliteBtreeMoveto() */
};

/*
** Legal values for BtCursor.eSkip.
*/
#define SKIP_NONE     0   /* Always step the cursor */
#define SKIP_NEXT     1   /* The next sqliteBtreeNext() is a no-op */
#define SKIP_PREV     2   /* The next sqliteBtreePrevious() is a no-op */
#define SKIP_INVALID  3   /* Calls to Next() and Previous() are invalid */

/*
** Routines for byte swapping.
*/
u16 swab16(u16 x){
  return ((x & 0xff)<<8) | ((x>>8)&0xff);
}
u32 swab32(u32 x){

  rc = initPage(pBt, pCur->pPage, pCur->pgnoRoot, 0);
  if( rc!=SQLITE_OK ){
    goto create_cursor_exception;
  }
  pCur->pBt = pBt;
  pCur->wrFlag = wrFlag;
  pCur->idx = 0;
  pCur->eSkip = SKIP_INVALID;
  pCur->pNext = pBt->pCursor;
  if( pCur->pNext ){
    pCur->pNext->pPrev = pCur;
  }
  pCur->pPrev = 0;
  pRing = pBt->pCursor;
  while( pRing && pRing->pgnoRoot!=pCur->pgnoRoot ){ pRing = pRing->pNext; }

  while( (pgno = pCur->pPage->apCell[pCur->idx]->h.leftChild)!=0 ){
    rc = moveToChild(pCur, SWAB32(pCur->pBt, pgno));
    if( rc ) return rc;
  }
  return SQLITE_OK;
}

/*
** Move the cursor down to the right-most leaf entry beneath the
** page to which it is currently pointing.  Notice the difference
** between moveToLeftmost() and moveToRightmost().  moveToLeftmost()
** finds the left-most entry beneath the *entry* whereas moveToRightmost()
** finds the right-most entry beneath the *page*.
*/
static int moveToRightmost(BtCursor *pCur){
  Pgno pgno;
  int rc;

  while( (pgno = pCur->pPage->u.hdr.rightChild)!=0 ){
    rc = moveToChild(pCur, SWAB32(pCur->pBt, pgno));
    if( rc ) return rc;
  }
  pCur->idx = pCur->pPage->nCell - 1;
  return SQLITE_OK;
}

/* Move the cursor to the first 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.
*/
int sqliteBtreeFirst(BtCursor *pCur, int *pRes){
  int rc;
  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;
  rc = moveToLeftmost(pCur);
  pCur->eSkip = SKIP_NONE;
  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.
*/
int sqliteBtreeLast(BtCursor *pCur, int *pRes){
  int rc;

  if( pCur->pPage==0 ) return SQLITE_ABORT;
  rc = moveToRoot(pCur);
  if( rc ) return rc;
  assert( pCur->pPage->isInit );
  if( pCur->pPage->nCell==0 ){
    *pRes = 1;
    return SQLITE_OK;
  }
  *pRes = 0;

  rc = moveToRightmost(pCur);



  pCur->eSkip = SKIP_NONE;
  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

**
**     *pRes>0      The cursor is left pointing at an entry that
**                  is larger than pKey.
*/
int sqliteBtreeMoveto(BtCursor *pCur, const void *pKey, int nKey, int *pRes){
  int rc;
  if( pCur->pPage==0 ) return SQLITE_ABORT;
  pCur->eSkip = SKIP_NONE;
  rc = moveToRoot(pCur);
  if( rc ) return rc;
  for(;;){
    int lwr, upr;
    Pgno chldPg;
    MemPage *pPage = pCur->pPage;
    int c = -1;

int sqliteBtreeNext(BtCursor *pCur, int *pRes){
  int rc;
  if( pCur->pPage==0 ){
    if( pRes ) *pRes = 1;
    return SQLITE_ABORT;
  }
  assert( pCur->pPage->isInit );
  assert( pCur->eSkip!=SKIP_INVALID );
  if( pCur->pPage->nCell==0 ){
    if( pRes ) *pRes = 1;
    return SQLITE_OK;
  }
  assert( pCur->idx<pCur->pPage->nCell );
  if( pCur->eSkip==SKIP_NEXT ){
    pCur->eSkip = SKIP_NONE;
    if( pRes ) *pRes = 0;
    return SQLITE_OK;
  }
  pCur->eSkip = SKIP_NONE;
  pCur->idx++;
  if( pCur->idx>=pCur->pPage->nCell ){
    if( pCur->pPage->u.hdr.rightChild ){
      rc = moveToChild(pCur, SWAB32(pCur->pBt, pCur->pPage->u.hdr.rightChild));
      if( rc ) return rc;
      rc = moveToLeftmost(pCur);
      if( rc ) return rc;

    return SQLITE_OK;
  }
  rc = moveToLeftmost(pCur);
  if( rc ) return rc;
  if( pRes ) *pRes = 0;
  return SQLITE_OK;
}

/*
** Step the cursor to the back to the previous entry in the database.  If
** successful and pRes!=NULL then set *pRes=0.  If the cursor
** was already pointing to the first entry in the database before
** this routine was called, then set *pRes=1 if pRes!=NULL.
*/
int sqliteBtreePrevious(BtCursor *pCur, int *pRes){
  int rc;
  Pgno pgno;
  if( pCur->pPage==0 ){
    if( pRes ) *pRes = 1;
    return SQLITE_ABORT;
  }
  assert( pCur->pPage->isInit );
  assert( pCur->eSkip!=SKIP_INVALID );
  if( pCur->pPage->nCell==0 ){
    if( pRes ) *pRes = 1;
    return SQLITE_OK;
  }
  if( pCur->eSkip==SKIP_PREV ){
    pCur->eSkip = SKIP_NONE;
    if( pRes ) *pRes = 0;
    return SQLITE_OK;
  }
  pCur->eSkip = SKIP_NONE;
  assert( pCur->idx>=0 );
  if( (pgno = pCur->pPage->apCell[pCur->idx]->h.leftChild)!=0 ){
    rc = moveToChild(pCur, SWAB32(pCur->pBt, pgno));
    if( rc ) return rc;
    rc = moveToRightmost(pCur);
  }else{
    while( pCur->idx==0 ){
      if( pCur->pPage->pParent==0 ){
        if( pRes ) *pRes = 1;
        return SQLITE_OK;
      }
      rc = moveToParent(pCur);
      if( rc ) return rc;
    }
    pCur->idx--;
    rc = SQLITE_OK;
  }
  if( pRes ) *pRes = 0;
  return rc;
}

/*
** Allocate a new page from the database file.
**
** The new page is marked as dirty.  (In other words, sqlitepager_write()
** has already been called on the new page.)  The new page has also
** been referenced and the calling routine is responsible for calling

  }else{
    assert( pPage->u.hdr.rightChild==0 );  /* Must be a leaf page */
  }
  insertCell(pBt, pPage, pCur->idx, &newCell, szNew);
  rc = balance(pCur->pBt, pPage, pCur);
  /* sqliteBtreePageDump(pCur->pBt, pCur->pgnoRoot, 1); */
  /* fflush(stdout); */
  pCur->eSkip = SKIP_INVALID;
  return rc;
}

/*
** Delete the entry that the cursor is pointing to.
**
** The cursor is left pointing at either the next or the previous
** entry.  If the cursor is left pointing to the next entry, then 
** the pCur->eSkip flag is set to SKIP_NEXT which forces the next call to 
** sqliteBtreeNext() to be a no-op.  That way, you can always call
** sqliteBtreeNext() after a delete and the cursor will be left
** pointing to the first entry after the deleted entry.  Similarly,
** pCur->eSkip is set to SKIP_PREV is the cursor is left pointing to
** the entry prior to the deleted entry so that a subsequent call to
** sqliteBtreePrevious() will always leave the cursor pointing at the
** entry immediately before the one that was deleted.
*/
int sqliteBtreeDelete(BtCursor *pCur){
  MemPage *pPage = pCur->pPage;
  Cell *pCell;
  int rc;
  Pgno pgnoChild;
  Btree *pBt = pCur->pBt;

    dropCell(pBt, pPage, pCur->idx, cellSize(pBt, pCell));
    pNext = leafCur.pPage->apCell[leafCur.idx];
    szNext = cellSize(pBt, pNext);
    pNext->h.leftChild = SWAB32(pBt, pgnoChild);
    insertCell(pBt, pPage, pCur->idx, pNext, szNext);
    rc = balance(pBt, pPage, pCur);
    if( rc ) return rc;
    pCur->eSkip = SKIP_NEXT;
    dropCell(pBt, leafCur.pPage, leafCur.idx, szNext);
    rc = balance(pBt, leafCur.pPage, pCur);
    releaseTempCursor(&leafCur);
  }else{
    dropCell(pBt, pPage, pCur->idx, cellSize(pBt, pCell));
    if( pCur->idx>=pPage->nCell ){
      pCur->idx = pPage->nCell-1;
      if( pCur->idx<0 ){ 
        pCur->idx = 0;
        pCur->eSkip = SKIP_NEXT;
      }else{
        pCur->eSkip = SKIP_PREV;
      }
    }else{
      pCur->eSkip = SKIP_NEXT;
    }
    rc = balance(pBt, pPage, pCur);
  }
  return rc;
}

/*

**    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.26 2002/12/04 13:40:26 drh Exp $
*/
#ifndef _BTREE_H_
#define _BTREE_H_

typedef struct Btree Btree;
typedef struct BtCursor BtCursor;

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 sqliteBtreePrevious(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);
int sqliteBtreeCloseCursor(BtCursor*);

**    May you share freely, never taking more than you give.
**
*************************************************************************
** Code for testing the btree.c module in SQLite.  This code
** is not included in the SQLite library.  It is used for automated
** testing of the SQLite library.
**
** $Id: test3.c,v 1.22 2002/12/04 13:40:26 drh Exp $
*/
#include "sqliteInt.h"
#include "pager.h"
#include "btree.h"
#include "tcl.h"
#include <stdlib.h>
#include <string.h>

  }
  return SQLITE_OK;
}

/*
** Usage:   btree_next ID
**
** Move the cursor to the next entry in the table.  Return 0 on success
** or 1 if the cursor was already on the last entry in the table or if
** the table is empty.
*/
static int btree_next(
  void *NotUsed,
  Tcl_Interp *interp,    /* The TCL interpreter that invoked this command */
  int argc,              /* Number of arguments */
  const char **argv      /* Text of each argument */
){

    Tcl_AppendResult(interp, errorName(rc), 0);
    return TCL_ERROR;
  }
  sprintf(zBuf,"%d",res);
  Tcl_AppendResult(interp, zBuf, 0);
  return SQLITE_OK;
}

/*
** Usage:   btree_prev ID
**
** Move the cursor to the previous entry in the table.  Return 0 on
** success and 1 if the cursor was already on the first entry in
** the table or if the table was empty.
*/
static int btree_prev(
  void *NotUsed,
  Tcl_Interp *interp,    /* The TCL interpreter that invoked this command */
  int argc,              /* Number of arguments */
  const char **argv      /* Text of each argument */
){
  BtCursor *pCur;
  int rc;
  int res = 0;
  char zBuf[100];

  if( argc!=2 ){
    Tcl_AppendResult(interp, "wrong # args: should be \"", argv[0],
       " ID\"", 0);
    return TCL_ERROR;
  }
  if( Tcl_GetInt(interp, argv[1], (int*)&pCur) ) return TCL_ERROR;
  rc = sqliteBtreePrevious(pCur, &res);
  if( rc ){
    Tcl_AppendResult(interp, errorName(rc), 0);
    return TCL_ERROR;
  }
  sprintf(zBuf,"%d",res);
  Tcl_AppendResult(interp, zBuf, 0);
  return SQLITE_OK;
}

/*
** Usage:   btree_first ID
**
** Move the cursor to the first entry in the table.  Return 0 if the
** cursor was left point to something and 1 if the table is empty.
*/
static int btree_first(
  void *NotUsed,
  Tcl_Interp *interp,    /* The TCL interpreter that invoked this command */
  int argc,              /* Number of arguments */
  const char **argv      /* Text of each argument */
){
  BtCursor *pCur;
  int rc;
  int res = 0;
  char zBuf[100];

  if( argc!=2 ){
    Tcl_AppendResult(interp, "wrong # args: should be \"", argv[0],
       " ID\"", 0);
    return TCL_ERROR;
  }
  if( Tcl_GetInt(interp, argv[1], (int*)&pCur) ) return TCL_ERROR;
  rc = sqliteBtreeFirst(pCur, &res);
  if( rc ){
    Tcl_AppendResult(interp, errorName(rc), 0);
    return TCL_ERROR;
  }
  sprintf(zBuf,"%d",res);
  Tcl_AppendResult(interp, zBuf, 0);
  return SQLITE_OK;
}

/*
** Usage:   btree_last ID
**
** Move the cursor to the last entry in the table.  Return 0 if the
** cursor was left point to something and 1 if the table is empty.
*/
static int btree_last(
  void *NotUsed,
  Tcl_Interp *interp,    /* The TCL interpreter that invoked this command */
  int argc,              /* Number of arguments */
  const char **argv      /* Text of each argument */
){
  BtCursor *pCur;
  int rc;
  int res = 0;
  char zBuf[100];

  if( argc!=2 ){
    Tcl_AppendResult(interp, "wrong # args: should be \"", argv[0],
       " ID\"", 0);
    return TCL_ERROR;
  }
  if( Tcl_GetInt(interp, argv[1], (int*)&pCur) ) return TCL_ERROR;
  rc = sqliteBtreeLast(pCur, &res);
  if( rc ){
    Tcl_AppendResult(interp, errorName(rc), 0);
    return TCL_ERROR;
  }
  sprintf(zBuf,"%d",res);
  Tcl_AppendResult(interp, zBuf, 0);
  return SQLITE_OK;

     { "btree_pager_ref_dump",     (Tcl_CmdProc*)btree_pager_ref_dump     },
     { "btree_cursor",             (Tcl_CmdProc*)btree_cursor             },
     { "btree_close_cursor",       (Tcl_CmdProc*)btree_close_cursor       },
     { "btree_move_to",            (Tcl_CmdProc*)btree_move_to            },
     { "btree_delete",             (Tcl_CmdProc*)btree_delete             },
     { "btree_insert",             (Tcl_CmdProc*)btree_insert             },
     { "btree_next",               (Tcl_CmdProc*)btree_next               },
     { "btree_prev",               (Tcl_CmdProc*)btree_prev               },
     { "btree_key",                (Tcl_CmdProc*)btree_key                },
     { "btree_data",               (Tcl_CmdProc*)btree_data               },
     { "btree_payload_size",       (Tcl_CmdProc*)btree_payload_size       },
     { "btree_first",              (Tcl_CmdProc*)btree_first              },
     { "btree_last",               (Tcl_CmdProc*)btree_last               },
     { "btree_cursor_dump",        (Tcl_CmdProc*)btree_cursor_dump        },
     { "btree_integrity_check",    (Tcl_CmdProc*)btree_integrity_check    },
  };
  int i;

  for(i=0; i<sizeof(aCmd)/sizeof(aCmd[0]); i++){
    Tcl_CreateCommand(interp, aCmd[i].zName, aCmd[i].xProc, 0, 0);

# 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 runs all tests.
#
# $Id: all.test,v 1.18 2002/12/04 13:40:27 drh Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl
rename finish_test really_finish_test
proc finish_test {} {memleak_check}

if {[file exists ./sqlite_test_count]} {
  set COUNT [exec cat ./sqlite_test_count]
} else {
  set COUNT 4
}

if {[llength $argv]>0} {
  foreach {name value} $argv {
    switch -- $name {
      -count {
         set COUNT $value
      }
      -quick {
         set ISQUICK $value
      }
      default {
         puts stderr "Unknown option: $name"
         exit
      }
    }
  }
}
set argv {}

# LeakList will hold a list of the number of unfreed mallocs after
# each round of the test.  This number should be constant.  If it
# grows, it may mean there is a memory leak in the library.
#
set LeakList {}

# cursor is suppose to be left pointing at either the previous or
# next entry in that table.  If the cursor is left pointing at the
# next entry, then the next Next operation is ignored.  So the 
# sequence of operations (Delete, Next) should always leave the
# cursor pointing at the first entry past the one that was deleted.
# This test is designed to verify that behavior.
#
# $Id: btree3.test,v 1.2 2002/12/04 13:40:27 drh Exp $


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

if {[info commands btree_open]!=""} {

append data $data
append data $data
for {set k 2} {$k<=10} {incr k} {
  for {set j 1} {$j<=$k} {incr j} {
    set jkey [format %02d $j]
    btree_clear_table $::b1 2
    set ::c1 [btree_cursor $::b1 2 1]
    for {set i 1} {$i<=$k} {incr i} {
      set key [format %02d $i]
      do_test btree3-$k.$j.1.$i {
        btree_insert $::c1 $::key $::data
      } {}
      # btree_tree_dump $::b1 2
    }
    do_test btree3-$k.$j.2 {
      btree_move_to $::c1 $::jkey
      btree_key $::c1
    } $::jkey
    do_test btree3-$k.$j.3 {
      btree_delete $::c1
    } {}
    if {$j<$k} {
      do_test btree3-$k.$j.4 {
        btree_next $::c1
        btree_key $::c1
      } [format %02d [expr $j+1]]
    }
    if {$j>1} {
      do_test btree3-$k.$j.5 {
        btree_prev $::c1
        btree_key $::c1
      } [format %02d [expr $j-1]]
    }
    btree_close_cursor $::c1
  }
}

btree_rollback $::b1    
btree_pager_ref_dump $::b1
btree_close $::b1

} ;# end if( not mem: and has pager_open command );

finish_test

# 2002 December 03
#
# 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
#
# This file focuses on testing the sqliteBtreeNext() and 
# sqliteBtreePrevious() procedures and making sure they are able
# to step through an entire table from either direction.
#
# $Id: btree4.test,v 1.1 2002/12/04 13:40:27 drh Exp $


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

if {[info commands btree_open]!=""} {

# Open a test database.
#
file delete -force test1.bt
file delete -force test1.bt-journal
set b1 [btree_open test1.bt]
btree_begin_transaction $::b1

set data {abcdefghijklmnopqrstuvwxyz0123456789}
append data $data
append data $data
append data $data
append data $data

foreach N {10 100 1000} {
  btree_clear_table $::b1 2
  set ::c1 [btree_cursor $::b1 2 1]
  do_test btree4-$N.1 {
    for {set i 1} {$i<=$N} {incr i} {
      btree_insert $::c1 [format k-%05d $i] $::data-$i
    }
    btree_first $::c1
    btree_key $::c1
  } {k-00001}
  do_test btree4-$N.2 {
    btree_data $::c1
  } $::data-1
  for {set i 2} {$i<=$N} {incr i} {
    do_test btree-$N.3.$i.1 {
      btree_next $::c1
    } 0
    do_test btree-$N.3.$i.2 {
      btree_key $::c1
    } [format k-%05d $i]
    do_test btree-$N.3.$i.3 {
      btree_data $::c1
    } $::data-$i
  }
  do_test btree4-$N.4 {
    btree_next $::c1
  } 1
  do_test btree4-$N.5 {
    btree_last $::c1
  } 0
  do_test btree4-$N.6 {
    btree_key $::c1
  } [format k-%05d $N]
  do_test btree4-$N.7 {
    btree_data $::c1
  } $::data-$N
  for {set i [expr {$N-1}]} {$i>=1} {incr i -1} {
    do_test btree4-$N.8.$i.1 {
      btree_prev $::c1
    } 0
    do_test btree4-$N.8.$i.2 {
      btree_key $::c1
    } [format k-%05d $i]
    do_test btree4-$N.8.$i.3 {
      btree_data $::c1
    } $::data-$i
  }
  do_test btree4-$N.9 {
    btree_prev $::c1
  } 1
  btree_close_cursor $::c1
}

btree_rollback $::b1    
btree_pager_ref_dump $::b1
btree_close $::b1

} ;# end if( not mem: and has pager_open command );

finish_test

  execsql {
    CREATE TABLE t2(
      x INTEGER PRIMARY KEY,
      y TEXT
    );
  }
} {}
do_test fkey1-1.2 {
  execsql {
    CREATE TABLE t3(
      a INTEGER REFERENCES t2,
      b INTEGER REFERENCES t1,
      FOREIGN KEY (a,b) REFERENCES t2(x,y)
    );
  }
} {}
   


finish_test