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.220 2004/11/17 10:22:03 danielk1977 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.

    int nCellCnt = 0;
    int iCell = -1;
    Pgno pgno = pCur->pPage->pgno;

    /* If the cursor is not valid, do not do anything with it. */
    if( !pCur->isValid ) continue;

    /* If the cursor pointed to one of the cells moved around during the
    ** balancing, then set variable iCell to the index of the cell in apCell.
    ** This is used by the block below to figure out where the cell was
    ** moved to, and adjust the cursor appropriately.
    **
    ** If the cursor points to the parent page, but the cell was not involved
    ** in the balance, then declare the cache of the cell-parse invalid, as a
    ** defragmentation may of occured during  the balance. Also, if the index
    ** of the cell is greater than that of the divider cells, then it may
    ** need to be adjusted (in case there are now more or less divider cells
    ** than there were before the balancing).
    */
    for(i=0; iCell<0 && i<nOld; i++){
      if( pgno==apCopy[i]->pgno ){
        iCell = nCellCnt + pCur->idx;
        break;
      }
      nCellCnt += (apCopy[i]->nCell + apCopy[i]->nOverflow) + (leafData?0:1);
    }

    if( pgno==pParent->pgno ){
      assert( !leafData );
      assert( iCell==-1 );
      if( pCur->idx>=nxDiv && pCur->idx<(nxDiv+nOld-1) ){
        for(i=0; i<=(pCur->idx-nxDiv); i++){
          iCell += (apCopy[i]->nCell + apCopy[i]->nOverflow + 1);
        }
      }
      if( pCur->idx>=(nxDiv+nOld-1) ){
        TRACE(("BALANCE: Cursor %p migrates from %d,%d to %d,%d\n", 
            pCur, pgno, pCur->idx, pgno, pCur->idx+(nNew-nOld)));
        pCur->idx += (nNew-nOld);
      }
      pCur->info.nSize = 0;
    }

    /* If iCell is greater than or equal to zero, then pCur points at a
    ** cell that was moved around during the balance. Figure out where
    ** the cell was moved to and adjust pCur to match.
    */
    if( iCell>=0 ){
      int idxNew;
      Pgno pgnoNew;
      int x = 0;

      assert( iCell<nCell );
      while( cntNew[x]<=iCell ) x++;

  usableSize = pBt->usableSize;
  data = pPage->aData;
  hdr = pPage->hdrOffset;
  brk = get2byte(&data[hdr+5]);
  cdata = pChild->aData;
  memcpy(cdata, &data[hdr], pPage->cellOffset+2*pPage->nCell-hdr);
  memcpy(&cdata[brk], &data[brk], usableSize-brk);
  assert( pChild->isInit==0 );
  rc = initPage(pChild, pPage);
  if( rc ) return rc;
  memcpy(pChild->aOvfl, pPage->aOvfl, pPage->nOverflow*sizeof(pPage->aOvfl[0]));
  pChild->nOverflow = pPage->nOverflow;
  if( pChild->nOverflow ){
    pChild->nFree = 0;
  }

      if( rc!=SQLITE_NOMEM ){
        rc = SQLITE_CORRUPT;  /* bkpt-CORRUPT */
      }
      goto delete_out;
    }
    rc = sqlite3pager_write(leafCur.pPage->aData);
    if( rc ) goto delete_out;
    TRACE(("DELETE: table=%d delete internal from %d,%d replace "
        "from leaf %d,%d\n", pCur->pgnoRoot, pPage->pgno, idx, 
        leafCur.pPage->pgno, leafCur.idx));

    /* Drop the cell from the internal page. Make a copy of the cell from
    ** the leaf page into memory obtained from malloc(). Insert it into
    ** the internal page, at the position vacated by the delete. There
    ** are now two copies of the leaf-cell in the tree.
    */
    dropCell(pPage, idx, cellSizePtr(pPage, pCell));

    if( rc!=SQLITE_OK ) goto delete_out;
    put4byte(findOverflowCell(pPage, idx), pgnoChild);
    pPage->idxShift = 0;

    /* If there are any cursors that point to the leaf-cell, move them
    ** so that they point at internal cell. This is easiest done by
    ** calling BtreePrevious().
    **
    ** Also, any cursors that point to the internal page have their
    ** cached parses invalidated, as the insertCell() above may have 
    ** caused a defragmation.
    */
    for(pCur2=pBt->pCursor; pCur2; pCur2 = pCur2->pNext){
      if( pCur2->pPage==leafCur.pPage && pCur2->idx==leafCur.idx ){
        int res;
        int delShiftSave = pCur2->delShift; 
        assert( leafCur.idx==0 );
        pCur2->delShift = 0;
        rc = sqlite3BtreePrevious(pCur2, &res);
        if( rc ) goto delete_out;
        assert( res==0 );
        assert( pCur2->pPage==pPage );
        assert( pCur2->idx==idx );
        pCur2->delShift = delShiftSave;
      }
      if( pCur2->pPage==pPage ){
        pCur2->info.nSize = 0;
      }
    }

    /* Balance the internal page. Free the memory allocated for the 
    ** copy of the leaf cell. Then delete the cell from the leaf page.
    */
    rc = balance(pPage);
    sqliteFree(tempCell);
    if( rc ) goto delete_out;
    dropCell(leafCur.pPage, leafCur.idx, szNext);

    for(pCur2=pBt->pCursor; pCur2; pCur2 = pCur2->pNext){
      if( pCur2->pPage==leafCur.pPage && pCur2->idx>leafCur.idx ){
        TRACE(("DELETE: Cursor %p migrates from %d,%d to %d,%d\n", pCur2, 
            leafCur.pPage->pgno,pCur2->idx,leafCur.pPage->pgno, pCur2->idx-1));
        pCur2->idx--;
        pCur2->info.nSize = 0;
      }
    }

    rc = balance(leafCur.pPage);
    releaseTempCursor(&leafCur);

}

/*
** Print a disassembly of the given page on standard output.  This routine
** is used for debugging and testing only.
*/
#ifdef SQLITE_TEST
static int btreePageDump(Btree *pBt, int pgno, int recursive, MemPage *pParent){
  int rc;
  MemPage *pPage;
  int i, j, c;
  int nFree;
  u16 idx;
  int hdr;
  int nCell;
  int isInit;
  unsigned char *data;
  char range[20];
  unsigned char payload[20];

  rc = getPage(pBt, (Pgno)pgno, &pPage);
  isInit = pPage->isInit;
  if( pPage->isInit==0 ){
    initPage(pPage, pParent);
  }
  if( rc ){
    return rc;
  }
  hdr = pPage->hdrOffset;
  data = pPage->aData;
  c = data[hdr];

  }
  if( idx!=0 ){
    sqlite3DebugPrintf("ERROR: next freeblock index out of range: %d\n", idx);
  }
  if( recursive && !pPage->leaf ){
    for(i=0; i<nCell; i++){
      unsigned char *pCell = findCell(pPage, i);
      btreePageDump(pBt, get4byte(pCell), 1, pPage);
      idx = get2byte(pCell);
    }
    btreePageDump(pBt, get4byte(&data[hdr+8]), 1, pPage);
  }
  pPage->isInit = isInit;
  sqlite3pager_unref(data);
  fflush(stdout);
  return SQLITE_OK;
}
int sqlite3BtreePageDump(Btree *pBt, int pgno, int recursive){
  return btreePageDump(pBt, pgno, recursive, 0);
}
#endif

#ifdef SQLITE_TEST
/*
** Fill aResult[] with information about the entry and page that the
** cursor is pointing to.

#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this script is btree database backend. Specifically,
# this file tests that existing cursors are correctly repositioned 
# when entries are inserted into or deleted from btrees.
#
# $Id: btree8.test,v 1.4 2004/11/17 10:22:04 danielk1977 Exp $

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

# Test organization:
#
# btree-8.1.*: Test cursor persistence when inserting records into tables.
# btree-8.2.*: Test cursor persistence when deleting records from tables.
# btree-8.3.*: Test cursor persistence when inserting records into indices.
# btree-8.4.*: Test cursor persistence when deleting records from indices.
#


# Transform the number $num into a string of length $len by repeating the
# string representation of the number as many times as necessary. Repeats
# are seperated by a '.' character. Eg:
#
# [num_to_string 456 10] -> "456.456.45"
#

# Then, a record is inserted for each key value between 1 and 5000,
# including the values for which a record already exists (overwriting
# the original). After each record is inserted, the existing cursors
# are checked to ensure they still point at the same key-value.
#

# Open the database at the btree level and begin a transaction
do_test btree8-1.0 {
  set ::bt [btree_open test.db 100 0]
  expr 0
} {0}

do_test btree8-1.1 {
  btree_begin_transaction $::bt
  expr 0
} {0}

# For each element in the list $keys, insert an entry into the SQL table
# with the corresponding key value. Check that the cursor used to insert
# the key is left pointing to it after the insert. Then save this cursor

btree_close_cursor $::write_csr
btree_commit $::bt
if {$::nErr>0} { puts $::csr_list }
foreach csr $csr_list {
  btree_close_cursor $csr
}
set csr_list [list]

#------------------------------------------------------------------------
# Tests btree8.5.* also test the types of trees used for SQL indices. 
# This time, 300 entries of 150 bytes each are inserted into the btree (this
# produces a tree of height 3 - root page is the grandparent of the leaves).
# A cursor points at each entry. We check that all cursors retain there
# validity when:
#
# * Each entry is deleted (test cases btree-8.5.1.*)
# * An entry is inserted just after/before each existing key (test 
#   cases btree-8.5.2.*).
#

# Open a cursor on each entry in the tree in B-tree $bt, root-page $tnum.
# Return a list of the cursors.
#
proc open_cursors {bt tnum} {
  set c [btree_cursor $bt $tnum 0]
  set csr_list [list]
  for {btree_first $c} {![btree_eof $c]} {btree_next $c} {
    set c2 [btree_cursor $bt $tnum 0]
    btree_move_to $c2 [btree_key $c]
    lappend csr_list $c2
  }
  btree_close_cursor $c
  return $csr_list
}

# Close all cursors in the list $csr_list.
#
proc close_cursors {csr_list} { 
  foreach c $csr_list {
    btree_close_cursor $c
  }
}

# Check that the key for each cursor in csr_list matches the corresponding
# entry in key_list. If not, raise an exception.
#
proc check_cursors {key_list csr_list} {
  foreach k $key_list c $csr_list {
    if {[string compare $k [btree_key $c]]} {
      error "Csr key '[btree_key $c]' - should be '$k'"
    }
  }
}

# Set up the table used for the btree-8.5.* tests
do_test btree-8.5.0 {
  btree_begin_transaction $::bt
  set c [btree_cursor $::bt $::inum 1]
  for {set i 2} {$i<=600} {incr i 2} { 
    set key [num_to_string $i 150]
    lappend key_list $key
    btree_insert $c $key ""
  }
  btree_close_cursor $c
  btree_commit $::bt
} {}

# Test cases btree-8.5.1.* - Check that cursors survive DELETE operations.
set testnum 0
foreach key [lrange $::key_list 0 0] {
  incr testnum

  btree_begin_transaction $::bt

  # Open the 300 cursors.
  do_test btree-8.5.1.$testnum.1 {
    set ::csr_list [open_cursors $::bt $::inum]
    llength $::csr_list
  } {300}

   # Delete an entry.
   do_test btree-8.5.1.$testnum.2 {
     set c [btree_cursor $::bt $::inum 1]
     btree_move_to $c $::key
     btree_delete $c
     btree_close_cursor $c
   } {}
 
   # Check that all 300 cursors are Ok.
   do_test btree-8.5.1.$testnum.3 {
     catch {
       set e [lsearch $::key_list $::key]
       check_cursors [lreplace $::key_list $e $e ""] $::csr_list
     } msg
     set msg
   } {}

  close_cursors $::csr_list
  btree_rollback $::bt
}

# Test cases btree-8.5.2.* - Check that cursors survive INSERT operations.
set testnum 0
foreach key $::key_list {
  incr testnum

  btree_begin_transaction $::bt

  # Open the 300 cursors.
  do_test btree-8.5.2.$testnum.1 {
    set ::csr_list [open_cursors $::bt $::inum]
    llength $::csr_list
  } {300}

  # Insert new entries, one before the key, and one after.
  do_test btree-8.5.2.$testnum.2 {
    set c [btree_cursor $::bt $::inum 1]
    btree_insert $c "$::key$::key" ""
    btree_insert $c [string range $::key 0 end-1] ""
    btree_close_cursor $c
  } {}

  # Check that all 300 cursors are Ok.
  do_test btree-8.5.2.$testnum.3 {
    catch {
      check_cursors $::key_list $::csr_list
    } msg
    set msg
  } {}

  close_cursors $::csr_list
  btree_rollback $::bt
}

finish_test