SQLite

** Boston, MA  02111-1307, USA.
**
** Author contact information:
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** $Id: btree.c,v 1.14 2001/06/24 20:39:41 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.

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)

/*
** Forward declarations of structures used only in this file.
*/
typedef struct PageOne PageOne;
typedef struct MemPage MemPage;
typedef struct PageHdr PageHdr;

  pPage->u.hdr.firstCell = pc;
  memcpy(newPage, pPage->u.aDisk, pc);
  for(i=0; i<pPage->nCell; i++){
    Cell *pCell = (Cell*)&pPage->apCell[i];

    /* This routine should never be called on an overfull page.  The
    ** following asserts verify that constraint. */
    assert( Addr(pCell) > Addr(pPage) );
    assert( Addr(pCell) < Addr(pPage) + SQLITE_PAGE_SIZE );

    n = cellSize(pCell);
    pCell->h.iNext = i<pPage->nCell-1 ? pc + n : 0;
    memcpy(&newPage[pc], pCell, n);
    pPage->apCell[i] = (Cell*)&pPage->u.aDisk[pc];
    pc += n;
  }

  pPage->nFree = 0;
  idx = pPage->u.hdr.firstFree;
  while( idx!=0 ){
    if( idx>SQLITE_PAGE_SIZE-sizeof(FreeBlk) ) goto page_format_error;
    if( idx<sizeof(PageHdr) ) goto page_format_error;
    pFBlk = (FreeBlk*)&pPage->u.aDisk[idx];
    pPage->nFree += pFBlk->iSize;
    if( pFBlk->iNext>0 && pFBlk->iNext <= idx ) goto page_format_error;
    idx = pFBlk->iNext;
  }
  if( pPage->nCell==0 && pPage->nFree==0 ){
    /* As a special case, an uninitialized root page appears to be
    ** an empty database */
    return SQLITE_OK;
  }

** Create a new database by initializing the first two pages of the
** file.
*/
static int newDatabase(Btree *pBt){
  MemPage *pRoot;
  PageOne *pP1;
  int rc;
  if( sqlitepager_pagecount(pBt->pPager)>1 ) return SQLITE_OK;
  pP1 = pBt->page1;
  rc = sqlitepager_write(pBt->page1);
  if( rc ) return rc;
  rc = sqlitepager_get(pBt->pPager, 2, (void**)&pRoot);
  if( rc ) return rc;
  rc = sqlitepager_write(pRoot);
  if( rc ){

}

/*
** Remove the last reference to the database file.  This will
** remove the read lock.
*/
static void unlockBtree(Btree *pBt){
  if( pBt->inTrans==0 && pBt->pCursor==0 && pBt->page1!=0 ){
    sqlitepager_unref(pBt->page1);
    pBt->page1 = 0;
    pBt->inTrans = 0;
  }
}

/*
** Commit the transaction currently in progress.  All cursors
** must be closed before this routine is called.
*/
int sqliteBtreeCommit(Btree *pBt){
  int rc;
  if( pBt->pCursor!=0 || pBt->inTrans==0 ) return SQLITE_ERROR;
  rc = sqlitepager_commit(pBt->pPager);
  pBt->inTrans = 0;
  unlockBtree(pBt);
  return rc;
}

/*
** Rollback the transaction in progress.  All cursors must be
** closed before this routine is called.
*/
int sqliteBtreeRollback(Btree *pBt){
  int rc;
  if( pBt->pCursor!=0 ) return SQLITE_ERROR;
  if( pBt->inTrans==0 ) return SQLITE_OK;
  pBt->inTrans = 0;
  rc = sqlitepager_rollback(pBt->pPager);
  unlockBtree(pBt);
  return rc;
}

/*
** Create a new cursor for the BTree whose root is on the page

**
** The result of comparing the key with the entry to which the
** cursor is left pointing is stored in pCur->iMatch.  The same
** value is also written to *pRes if pRes!=NULL.  The meaning of
** this value is as follows:
**
**     *pRes<0      The cursor is left pointing at an entry that
**                  is smaller than pKey.
**
**     *pRes==0     The cursor is left pointing at an entry that
**                  exactly matches pKey.
**
**     *pRes>0      The cursor is left pointing at an entry that
**                  is larger than pKey.
*/
int sqliteBtreeMoveto(BtCursor *pCur, void *pKey, int nKey, int *pRes){
  int rc;
  pCur->bSkipNext = 0;
  rc = moveToRoot(pCur);
  if( rc ) return rc;
  for(;;){
    int lwr, upr;
    Pgno chldPg;
    MemPage *pPage = pCur->pPage;
    int c = -1;

** routine will be called soon after this routine in order to rebuild 
** the linked list.
*/
static void dropCell(MemPage *pPage, int idx, int sz){
  int j;
  assert( idx>=0 && idx<pPage->nCell );
  assert( sz==cellSize(pPage->apCell[idx]) );
  freeSpace(pPage, Addr(pPage->apCell[idx]) - Addr(pPage), sz);
  for(j=idx; j<pPage->nCell-1; j++){
    pPage->apCell[j] = pPage->apCell[j+1];
  }
  pPage->nCell--;
}

/*
** Insert a new cell on pPage at cell index "i".  pCell points to the

** invocations of either insertCell() or dropCell().
*/
static void relinkCellList(MemPage *pPage){
  int i;
  u16 *pIdx;
  pIdx = &pPage->u.hdr.firstCell;
  for(i=0; i<pPage->nCell; i++){
    int idx = Addr(pPage->apCell[i]) - Addr(pPage);
    assert( idx>0 && idx<SQLITE_PAGE_SIZE );
    *pIdx = idx;
    pIdx = &pPage->apCell[i]->h.iNext;
  }
  *pIdx = 0;
}

  int i;
  memcpy(pTo->u.aDisk, pFrom->u.aDisk, SQLITE_PAGE_SIZE);
  pTo->pParent = pFrom->pParent;
  pTo->isInit = 1;
  pTo->nCell = pFrom->nCell;
  pTo->nFree = pFrom->nFree;
  pTo->isOverfull = pFrom->isOverfull;
  to = Addr(pTo);
  from = Addr(pFrom);
  for(i=0; i<pTo->nCell; i++){
    uptr x = Addr(pFrom->apCell[i]);
    if( x>from && x<from+SQLITE_PAGE_SIZE ){
      *((uptr*)&pTo->apCell[i]) = x + to - from;
    }
  }
}

/*

  if( rc ) return rc;
  szNew = cellSize(&newCell);
  if( loc==0 ){
    newCell.h.leftChild = pPage->apCell[pCur->idx]->h.leftChild;
    rc = clearCell(pBt, pPage->apCell[pCur->idx]);
    if( rc ) return rc;
    dropCell(pPage, pCur->idx, cellSize(pPage->apCell[pCur->idx]));
  }else if( loc<0 && pPage->nCell>0 ){
    assert( pPage->u.hdr.rightChild==0 );  /* Must be a leaf page */
    pCur->idx++;
  }else{
    assert( pPage->u.hdr.rightChild==0 );  /* Must be a leaf page */
  }
  insertCell(pPage, pCur->idx, &newCell, szNew);
  rc = balance(pCur->pBt, pPage, pCur);
  return rc;
}

/*
** Delete the entry that the cursor is pointing to.
**

    }
    payload[sz] = 0;
    printf(
      "cell %2d: i=%-10s chld=%-4d nk=%-3d nd=%-3d payload=%s\n",
      i, range, (int)pCell->h.leftChild, pCell->h.nKey, pCell->h.nData,
      pCell->aPayload
    );
    i++;
    idx = pCell->h.iNext;
  }
  if( idx!=0 ){
    printf("ERROR: next cell index out of range: %d\n", idx);
  }
  printf("right_child: %d\n", pPage->u.hdr.rightChild);
  nFree = 0;

*************************************************************************
** This is the implementation of the page cache subsystem.
** 
** The page cache is used to access a database file.  The pager journals
** all writes in order to support rollback.  Locking is used to limit
** access to one or more reader or one writer.
**
** @(#) $Id: pager.c,v 1.11 2001/06/24 20:39:41 drh Exp $
*/
#include "sqliteInt.h"
#include "pager.h"
#include <fcntl.h>
#include <sys/stat.h>
#include <unistd.h>
#include <assert.h>

  pPager->dbSize = -1;
  pPager->nPage = 0;
  pPager->mxPage = mxPage>5 ? mxPage : 10;
  pPager->state = SQLITE_UNLOCK;
  pPager->errMask = 0;
  pPager->pFirst = 0;
  pPager->pLast = 0;
  pPager->nExtra = nExtra;
  memset(pPager->aHash, 0, sizeof(pPager->aHash));
  *ppPager = pPager;
  return SQLITE_OK;
}

/*
** Set the destructor for this pager.  If not NULL, the destructor is called

# Copyright (c) 1999, 2000 D. Richard Hipp
#
# This program is free software; you can redistribute it and/or
# modify it under the terms of the GNU General Public
# License as published by the Free Software Foundation; either
# version 2 of the License, or (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
# General Public License for more details.
# 
# You should have received a copy of the GNU General Public
# License along with this library; if not, write to the
# Free Software Foundation, Inc., 59 Temple Place - Suite 330,
# Boston, MA  02111-1307, USA.
#
# Author contact information:
#   drh@hwaci.com
#   http://www.hwaci.com/drh/
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this script is btree database backend
#
# $Id: btree.test,v 1.1 2001/06/24 20:39:41 drh Exp $


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

if {$dbprefix!="memory:" && [info commands btree_open]!=""} {

# Basic functionality.  Open and close a database.
#
do_test btree-1.1 {
  file delete -force test1.bt
  file delete -force test1.bt-journal
  set rc [catch {btree_open test1.bt} ::b1]
} {0}
do_test btree-1.2 {
  set rc [catch {btree_open test1.bt} ::b2]
} {0}
do_test btree-1.3 {
  set rc [catch {btree_close $::b2} msg]
  lappend rc $msg
} {0 {}}

# Do an insert and verify that the database file grows in size.
#
do_test btree-1.4 {
  set rc [catch {btree_begin_transaction $::b1} msg]
  lappend rc $msg
} {0 {}}
do_test btree-1.5 {
  set rc [catch {btree_cursor $::b1 2} ::c1]
  if {$rc} {lappend rc $::c1}
  set rc
} {0}
do_test btree-1.6 {
  set rc [catch {btree_insert $::c1 one 1.00} msg]
  lappend rc $msg
} {0 {}}
do_test btree-1.7 {
  btree_key $::c1
} {one}
do_test btree-1.8 {
  btree_data $::c1
} {1.00}
do_test btree-1.9 {
  set rc [catch {btree_close_cursor $::c1} msg]
  lappend rc $msg
} {0 {}}
do_test btree-1.10 {
  set rc [catch {btree_commit $::b1} msg]
  lappend rc $msg
} {0 {}}
do_test btree-1.11 {
  file size test1.bt
} {2048}

# Reopen the database and attempt to read the record that we wrote.
#
do_test btree-2.1 {
  set rc [catch {btree_cursor $::b1 2} ::c1]
  if {$rc} {lappend rc $::c1}
  set rc
} {0}
do_test btree-2.2 {
  btree_move_to $::c1 abc
} {1}
do_test btree-2.3 {
  btree_move_to $::c1 xyz
} {-1}
do_test btree-2.4 {
  btree_move_to $::c1 one
} {0}
do_test btree-2.5 {
  btree_key $::c1
} {one}
do_test btree-2.6 {
  btree_data $::c1
} {1.00}

# Do some additional inserts
#
do_test btree-3.1 {
  btree_begin_transaction $::b1
  btree_insert $::c1 two 2.00
  btree_key $::c1
} {two}
do_test btree-3.2 {
  btree_insert $::c1 three 3.00
  btree_key $::c1
} {three}
do_test btree-3.4 {
  btree_insert $::c1 four 4.00
  btree_key $::c1
} {four}
do_test btree-3.5 {
  btree_insert $::c1 five 5.00
  btree_key $::c1
} {five}
do_test btree-3.6 {
  btree_insert $::c1 six 6.00
  btree_key $::c1
} {six}
#btree_page_dump $::b1 2
do_test btree-3.7 {
  set rc [btree_move_to $::c1 {}]
  expr {$rc>0}
} {1}
do_test btree-3.8 {
  btree_key $::c1
} {five}
do_test btree-3.9 {
  btree_data $::c1
} {5.00}
do_test btree-3.10 {
  btree_next $::c1
  btree_key $::c1
} {four}
do_test btree-3.11 {
  btree_data $::c1
} {4.00}
do_test btree-3.12 {
  btree_next $::c1
  btree_key $::c1
} {one}
do_test btree-3.13 {
  btree_data $::c1
} {1.00}
do_test btree-3.14 {
  btree_next $::c1
  btree_key $::c1
} {six}
do_test btree-3.15 {
  btree_data $::c1
} {6.00}
do_test btree-3.16 {
  btree_next $::c1
  btree_key $::c1
} {three}
do_test btree-3.17 {
  btree_data $::c1
} {3.00}
do_test btree-3.18 {
  btree_next $::c1
  btree_key $::c1
} {two}
do_test btree-3.19 {
  btree_data $::c1
} {2.00}
do_test btree-3.20 {
  btree_next $::c1
  btree_key $::c1
} {}
do_test btree-3.21 {
  btree_data $::c1
} {}

# Commit the changes, reopen and reread the data
#
do_test btree-3.22 {
  set rc [catch {btree_close_cursor $::c1} msg]
  lappend rc $msg
} {0 {}}
do_test btree-3.23 {
  set rc [catch {btree_commit $::b1} msg]
  lappend rc $msg
} {0 {}}
do_test btree-3.24 {
  file size test1.bt
} {2048}
do_test btree-3.25 {
  set rc [catch {btree_cursor $::b1 2} ::c1]
  if {$rc} {lappend rc $::c1}
  set rc
} {0}
do_test btree-3.26 {
  set rc [btree_move_to $::c1 {}]
  expr {$rc>0}
} {1}
do_test btree-3.27 {
  btree_key $::c1
} {five}
do_test btree-3.28 {
  btree_data $::c1
} {5.00}
do_test btree-3.29 {
  btree_next $::c1
  btree_key $::c1
} {four}
do_test btree-3.30 {
  btree_data $::c1
} {4.00}
do_test btree-3.31 {
  btree_next $::c1
  btree_key $::c1
} {one}
do_test btree-3.32 {
  btree_data $::c1
} {1.00}
do_test btree-3.33 {
  btree_next $::c1
  btree_key $::c1
} {six}
do_test btree-3.34 {
  btree_data $::c1
} {6.00}
do_test btree-3.35 {
  btree_next $::c1
  btree_key $::c1
} {three}
do_test btree-3.36 {
  btree_data $::c1
} {3.00}
do_test btree-3.37 {
  btree_next $::c1
  btree_key $::c1
} {two}
do_test btree-3.38 {
  btree_data $::c1
} {2.00}
do_test btree-3.39 {
  btree_next $::c1
  btree_key $::c1
} {}
do_test btree-3.40 {
  btree_data $::c1
} {}

# Now try a delete
#
do_test btree-4.1 {
  btree_begin_transaction $::b1
  btree_move_to $::c1 one
  btree_key $::c1
} {one}
do_test btree-4.2 {
  btree_delete $::c1
} {}
do_test btree-4.3 {
  btree_key $::c1
} {six}
do_test btree-4.4 {
  btree_next $::c1
  btree_key $::c1
} {six}
do_test btree-4.5 {
  btree_next $::c1
  btree_key $::c1
} {three}
do_test btree-4.4 {
  btree_move_to $::c1 {}
  set r {}
  while 1 {
    set key [btree_key $::c1]
    if {$key==""} break
    lappend r $key
    lappend r [btree_data $::c1]
    btree_next $::c1
  }
  set r   
} {five 5.00 four 4.00 six 6.00 three 3.00 two 2.00}

# Commit and make sure the delete is still there.
#
do_test btree-4.5 {
  btree_close_cursor $::c1
  btree_commit $::b1
  set ::c1 [btree_cursor $::b1 2]
  btree_move_to $::c1 {}
  set r {}
  while 1 {
    set key [btree_key $::c1]
    if {$key==""} break
    lappend r $key
    lappend r [btree_data $::c1]
    btree_next $::c1
  }
  set r   
} {five 5.00 four 4.00 six 6.00 three 3.00 two 2.00}




do_test btree-99.1 {
  btree_close $::b1
} {}


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

finish_test

#   drh@hwaci.com
#   http://www.hwaci.com/drh/
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this script is page cache subsystem.
#
# $Id: pager.test,v 1.6 2001/06/24 20:39:41 drh Exp $


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

if {$dbprefix!="memory:" && [info commands pager_open]!=""} {

# Basic sanity check.  Open and close a pager.
#
do_test pager-1.0 {
  catch {file delete -force ptf1.db}
  catch {file delete -force ptf1.db-journal}
  set v [catch {