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.122 2004/05/10 16:18: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.

**
** Algorithm:  Carve a piece off of the first freeblock that is
** nByte in size or that larger.
*/
static int allocateSpace(MemPage *pPage, int nByte){
  int addr, pc, hdr;
  int size;
  int nFrag;
  unsigned char *data;
#ifndef NDEBUG
  int cnt = 0;
#endif

  data = pPage->aData;
  assert( sqlite3pager_iswriteable(data) );
  assert( pPage->pBt );
  if( nByte<4 ) nByte = 4;
  if( pPage->nFree<nByte || pPage->isOverfull ) return 0;
  hdr = pPage->hdrOffset;
  nFrag = data[hdr+5];
  if( nFrag>=60 || nFrag>pPage->nFree-nByte ){
    defragmentPage(pPage);
  }
  addr = hdr+1;
  pc = get2byte(&data[addr]);
  assert( addr<pc );
  assert( pc<=pPage->pBt->pageSize-4 );
  while( (size = get2byte(&data[pc+2]))<nByte ){

** in an error.
**
** This will release the write lock on the database file.  If there
** are no active cursors, it also releases the read lock.
*/
int sqlite3BtreeRollback(Btree *pBt){
  int rc;
  MemPage *pPage1;
  if( pBt->inTrans==0 ) return SQLITE_OK;
  pBt->inTrans = 0;
  pBt->inStmt = 0;
  if( pBt->readOnly ){
    rc = SQLITE_OK;
  }else{
    rc = sqlite3pager_rollback(pBt->pPager);
    /* The rollback may have destroyed the pPage1->aData value.  So
    ** call getPage() on page 1 again to make sure pPage1->aData is
    ** set correctly. */
    if( getPage(pBt, 1, &pPage1)==SQLITE_OK ){
      releasePage(pPage1);
    }
  }
  invalidateCursors(pBt);
  unlockBtreeIfUnused(pBt);
  return rc;
}

/*
** Set the checkpoint for the current transaction.  The checkpoint serves

  }
  pCur = sqliteMalloc( sizeof(*pCur) );
  if( pCur==0 ){
    rc = SQLITE_NOMEM;
    goto create_cursor_exception;
  }
  pCur->pgnoRoot = (Pgno)iTable;
  if( iTable==1 && sqlite3pager_pagecount(pBt->pPager)==0 ){
    rc = SQLITE_EMPTY;
    goto create_cursor_exception;
  }
  rc = getAndInitPage(pBt, pCur->pgnoRoot, &pCur->pPage, 0);
  if( rc!=SQLITE_OK ){
    goto create_cursor_exception;
  }
  pCur->xCompare = xCmp ? xCmp : dfltCompare;
  pCur->pArg = pArg;
  pCur->pBt = pBt;

}

/*
** Insert a new cell on pPage at cell index "i".  pCell points to the
** content of the cell.
**
** If the cell content will fit on the page, then put it there.  If it
** will not fit and pTemp is not NULL, then make a copy of the content
** into pTemp, set pPage->aCell[i] point to pTemp, and set pPage->isOverfull.
** If the content will not fit and pTemp is NULL, then make pPage->aCell[i]
** point to pCell and set pPage->isOverfull.
**
** Try to maintain the integrity of the linked list of cells.  But if
** the cell being inserted does not fit on the page, this will not be
** possible.  If the linked list is not maintained, then just update
** pPage->aCell[] and set the pPage->needRelink flag so that we will
** know to rebuild the linked list later.
*/
static void insertCell(
  MemPage *pPage,   /* Page into which we are copying */
  int i,            /* Which cell on pPage to insert after */
  u8 *pCell,        /* Text of the new cell to insert */
  int sz,           /* Bytes of data in pCell */
  u8 *pTemp         /* Temp storage space for pCell, if needed */
){
  int idx, j;
  assert( i>=0 && i<=pPage->nCell );
  assert( sz==cellSize(pPage, pCell) );
  assert( sqlite3pager_iswriteable(pPage->aData) );
  idx = pPage->needRelink ? 0 : allocateSpace(pPage, sz);
  resizeCellArray(pPage, pPage->nCell+1);
  for(j=pPage->nCell; j>i; j--){
    pPage->aCell[j] = pPage->aCell[j-1];
  }
  pPage->nCell++;
  if( idx<=0 ){
    pPage->isOverfull = 1;
    if( pTemp ){
      memcpy(pTemp, pCell, sz);
    }else{
      pTemp = pCell;
    }
    pPage->aCell[i] = pTemp;
  }else{
    u8 *data = pPage->aData;
    memcpy(&data[idx], pCell, sz);
    pPage->aCell[i] = &data[idx];
  }
  if( !pPage->isOverfull && !pPage->needRelink ){
    u8 *pPrev;

  Pgno pgnoOld[NB];            /* Page numbers for each page in apOld[] */
  MemPage *apCopy[NB];         /* Private copies of apOld[] pages */
  MemPage *apNew[NB+1];        /* pPage and up to NB siblings after balancing */
  Pgno pgnoNew[NB+1];          /* Page numbers for each page in apNew[] */
  int idxDiv[NB];              /* Indices of divider cells in pParent */
  u8 *apDiv[NB];               /* Divider cells in pParent */
  u8 aTemp[NB][MX_CELL_SIZE];  /* Temporary holding area for apDiv[] */
  u8 aInsBuf[NB][MX_CELL_SIZE];/* Space to hold dividers cells during insert */
  int cntNew[NB+1];            /* Index in aCell[] of cell after i-th page */
  int szNew[NB+1];             /* Combined size of cells place on i-th page */
  u8 *apCell[(MX_CELL+2)*NB];  /* All cells from pages being balanced */
  int szCell[(MX_CELL+2)*NB];  /* Local size of all cells */
  u8 aCopy[NB][MX_PAGE_SIZE+sizeof(MemPage)];  /* Space for apCopy[] */

  /* 

          if( pChild->nFree>=100 ){
            /* The child information will fit on the root page, so do the
            ** copy */
            zeroPage(pPage, pChild->aData[0]);
            resizeCellArray(pPage, pChild->nCell);
            for(i=0; i<pChild->nCell; i++){
              insertCell(pPage, i, pChild->aCell[i], 
                        cellSize(pChild, pChild->aCell[i]), 0);
            }
            freePage(pChild);
            TRACE(("BALANCE: child %d transfer to page 1\n", pChild->pgno));
          }else{
            /* The child has more information that will fit on the root.
            ** The tree is already balanced.  Do nothing. */
            TRACE(("BALANCE: child %d will not fit on page 1\n", pChild->pgno));

      pT = apNew[i];
      pgnoNew[i] = pgnoNew[minI];
      apNew[i] = apNew[minI];
      pgnoNew[minI] = t;
      apNew[minI] = pT;
    }
  }
  TRACE(("BALANCE: old: %d %d %d  new: %d %d %d %d\n",
    pgnoOld[0], 
    nOld>=2 ? pgnoOld[1] : 0,
    nOld>=3 ? pgnoOld[2] : 0,
    pgnoNew[0],
    nNew>=2 ? pgnoNew[1] : 0,
    nNew>=3 ? pgnoNew[2] : 0,
    nNew>=4 ? pgnoNew[3] : 0));


  /*
  ** Evenly distribute the data in apCell[] across the new pages.
  ** Insert divider cells into pParent as necessary.
  */
  j = 0;
  for(i=0; i<nNew; i++){
    MemPage *pNew = apNew[i];
    assert( pNew->pgno==pgnoNew[i] );
    resizeCellArray(pNew, cntNew[i] - j);
    while( j<cntNew[i] ){
      assert( pNew->nFree>=szCell[j] );
      insertCell(pNew, pNew->nCell, apCell[j], szCell[j], 0);
      j++;
    }
    assert( pNew->nCell>0 );
    assert( !pNew->isOverfull );
    relinkCellList(pNew);
    if( i<nNew-1 && j<nCell ){
      u8 *pCell = apCell[j];
      u8 *pTemp;
      if( !pNew->leaf ){
        memcpy(&pNew->aData[6], pCell+2, 4);
        pTemp = 0;
      }else{
        pCell -= 4;
        pTemp = aInsBuf[i];
      }
      insertCell(pParent, nxDiv, pCell, szCell[j]+leafCorrection, pTemp);
      put4byte(&pParent->aCell[nxDiv][2], pNew->pgno);
      j++;
      nxDiv++;
    }
  }
  assert( j==nCell );
  if( (pageFlags & PTF_LEAF)==0 ){

    dropCell(pPage, pCur->idx, szOld);
  }else if( loc<0 && pPage->nCell>0 ){
    assert( pPage->leaf );
    pCur->idx++;
  }else{
    assert( pPage->leaf );
  }
  insertCell(pPage, pCur->idx, newCell, szNew, 0);
  rc = balance(pPage);
  /* sqlite3BtreePageDump(pCur->pBt, pCur->pgnoRoot, 1); */
  /* fflush(stdout); */
  moveToRoot(pCur);
  return rc;
}

    ** next Cell after the one to be deleted is guaranteed to exist and
    ** to be a leaf so we can use it.
    */
    BtCursor leafCur;
    unsigned char *pNext;
    int szNext;
    int notUsed;
    unsigned char tempCell[MX_CELL_SIZE];
    getTempCursor(pCur, &leafCur);
    rc = sqlite3BtreeNext(&leafCur, &notUsed);
    if( rc!=SQLITE_OK ){
      if( rc!=SQLITE_NOMEM ) rc = SQLITE_CORRUPT;
      return rc;
    }
    rc = sqlite3pager_write(leafCur.pPage->aData);
    if( rc ) return rc;
    TRACE(("DELETE: table=%d delete internal from %d replace from leaf %d\n",
       pCur->pgnoRoot, pPage->pgno, leafCur.pPage->pgno));
    dropCell(pPage, pCur->idx, cellSize(pPage, pCell));
    pNext = leafCur.pPage->aCell[leafCur.idx];
    szNext = cellSize(leafCur.pPage, pNext);
    assert( sizeof(tempCell)>=szNext+4 );

    insertCell(pPage, pCur->idx, pNext-4, szNext+4, tempCell);
    put4byte(pPage->aCell[pCur->idx]+2, pgnoChild);
    rc = balance(pPage);
    if( rc ) return rc;

    dropCell(leafCur.pPage, leafCur.idx, szNext);
    rc = balance(leafCur.pPage);
    releaseTempCursor(&leafCur);
  }else{
    TRACE(("DELETE: table=%d delete from leaf %d\n",
       pCur->pgnoRoot, pPage->pgno));
    dropCell(pPage, pCur->idx, cellSize(pPage, pCell));

**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This header file defines the interface that the SQLite library
** presents to client programs.
**
** @(#) $Id: sqlite.h.in,v 1.63 2004/05/10 16:18:48 drh Exp $
*/
#ifndef _SQLITE_H_
#define _SQLITE_H_
#include <stdarg.h>     /* Needed for the definition of va_list */

/*
** Make sure we can call this stuff from C++.

#define SQLITE_INTERNAL     2   /* An internal logic error in SQLite */
#define SQLITE_PERM         3   /* Access permission denied */
#define SQLITE_ABORT        4   /* Callback routine requested an abort */
#define SQLITE_BUSY         5   /* The database file is locked */
#define SQLITE_LOCKED       6   /* A table in the database is locked */
#define SQLITE_NOMEM        7   /* A malloc() failed */
#define SQLITE_READONLY     8   /* Attempt to write a readonly database */
#define SQLITE_INTERRUPT    9   /* Operation terminated by sqlite3_interrupt()*/
#define SQLITE_IOERR       10   /* Some kind of disk I/O error occurred */
#define SQLITE_CORRUPT     11   /* The database disk image is malformed */
#define SQLITE_NOTFOUND    12   /* (Internal Only) Table or record not found */
#define SQLITE_FULL        13   /* Insertion failed because database is full */
#define SQLITE_CANTOPEN    14   /* Unable to open the database file */
#define SQLITE_PROTOCOL    15   /* Database lock protocol error */
#define SQLITE_EMPTY       16   /* Database is empty */
#define SQLITE_SCHEMA      17   /* The database schema changed */
#define SQLITE_TOOBIG      18   /* Too much data for one row of a table */
#define SQLITE_CONSTRAINT  19   /* Abort due to contraint violation */
#define SQLITE_MISMATCH    20   /* Data type mismatch */
#define SQLITE_MISUSE      21   /* Library used incorrectly */
#define SQLITE_NOLFS       22   /* Uses OS features not supported on host */
#define SQLITE_AUTH        23   /* Authorization denied */

#endif

#ifdef __cplusplus
}  /* End of the 'extern "C"' block */
#endif
#endif

**    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.34 2004/05/10 16:18:48 drh Exp $
*/
#include "sqliteInt.h"
#include "pager.h"
#include "btree.h"
#include "tcl.h"
#include <stdlib.h>
#include <string.h>

    case SQLITE_INTERRUPT:  zName = "SQLITE_INTERRUPT";   break;
    case SQLITE_IOERR:      zName = "SQLITE_IOERR";       break;
    case SQLITE_CORRUPT:    zName = "SQLITE_CORRUPT";     break;
    case SQLITE_NOTFOUND:   zName = "SQLITE_NOTFOUND";    break;
    case SQLITE_FULL:       zName = "SQLITE_FULL";        break;
    case SQLITE_CANTOPEN:   zName = "SQLITE_CANTOPEN";    break;
    case SQLITE_PROTOCOL:   zName = "SQLITE_PROTOCOL";    break;
    case SQLITE_EMPTY:      zName = "SQLITE_EMPTY";       break;
    default:                zName = "SQLITE_Unknown";     break;
  }
  return zName;
}

/*
** Usage:   btree_open FILENAME NCACHE FLAGS

# 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: btree2.test,v 1.13 2004/05/10 16:18:48 drh Exp $


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

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

#
#   1.  The descriptor table always contains 2 enters.  An entry keyed by
#       "N" is the number of elements in the foreground and background tables
#       combined.  The entry keyed by "L" is the number of digits in the keys
#       for foreground and background tables.
#
#   2.  The union of the foreground an background tables consists of N entries
#       where each entry has an L-digit key. (Actually, some keys can be longer 
#       than L characters, but they always start with L digits.)  The keys
#       cover all integers between 1 and N.  Whenever an entry is added to
#       the foreground it is removed form the background and vice versa.
#
#   3.  Some entries in the foreground and background tables have keys that
#       begin with an L-digit number but are followed by additional characters.
#       For each such entry there is a corresponding entry in the long key

  for {set i 1} {$i<=$N} {incr i} {
    set key [btree_key $::c3]
    if {[scan $key %d k]<1} {set k 0}
    if {$k!=$i} {
      set key [btree_key $::c4]
      if {[scan $key %d k]<1} {set k 0}
      if {$k!=$i} {




        return "Key $i is missing from both foreground and background"
      }
      set data [btree_data $::c4]
      btree_next $::c4
    } else {
      set data [btree_data $::c3]
      btree_next $::c3

              Is [string length $data] but should be $datalen"
    }
    if {[make_payload $k $L $datalen]!=$data} {
      return "Entry $i has an incorrect data"
    }
  }
}

# Look at all elements in both the foreground and background tables.
# Make sure the key is always the same as the prefix of the data.
#
# This routine was used for hunting bugs.  It is not a part of standard
# tests.
#
proc check_data {n key} {
  global c3 c4
  incr n -1
  foreach c [list $c3 $c4] {
    btree_first $c  ;# move_to $c $key
    set cnt 0
    while {![btree_eof $c]} {
      set key [btree_key $c]
      set data [btree_data $c]
      if {[string range $key 0 $n] ne [string range $data 0 $n]} {
        puts "key=[list $key] data=[list $data] n=$n"
        puts "cursor info = [btree_cursor_info $c]"
        btree_page_dump $::b [lindex [btree_cursor_info $c] 0]
        exit
      }
      btree_next $c
    }
  }
}

# Make random changes to the database such that each change preserves
# the invariants.  The number of changes is $n*N where N is the parameter
# from the descriptor table.  Each changes begins with a random key.
# the entry with that key is put in the foreground table with probability
# $I and it is put in background with probability (1.0-$I).  It gets
# a long key with probability $K and long data with probability $D.  

      if {$ck!=""} {
         puts "\nSANITY CHECK FAILED!\n$ck"
         exit
       }
    }
  }
}
set btree_trace 0

# Repeat this test sequence on database of various sizes
#
set testno 2
foreach {N L} {
  10 2
  50 2

    } $hash
    btree_begin_transaction $::b
    set ::c2 [btree_cursor $::b 2 1]
    set ::c3 [btree_cursor $::b 3 1]
    set ::c4 [btree_cursor $::b 4 1]
    set ::c5 [btree_cursor $::b 5 1]
    set ::c6 [btree_cursor $::b 6 1]

    do_test $testid.5 [subst {
      random_changes $n $I $K $D
    }] {}
    do_test $testid.6 {
      check_invariants
    } {}
    do_test $testid.7 {