** Boston, MA  02111-1307, USA.
**
** Author contact information:
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** $Id: btree.c,v 1.16 2001/06/28 01:54: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.
................................................................................
  int idx;                     /* Index of pPage in pParent->apCell[] */
  int nxDiv;                   /* Next divider slot in pParent->apCell[] */
  int rc;                      /* The return code */
  int iCur;                    /* apCell[iCur] is the cell of the cursor */
  int usedPerPage;             /* Memory needed for each page */
  int freePerPage;             /* Average free space per page */
  int totalSize;               /* Total bytes for all cells */

  Pgno pgno;                   /* Page number */
  Cell *apCell[MX_CELL*3+5];   /* All cells from pages being balanceed */
  int szCell[MX_CELL*3+5];     /* Local size of all cells */
  Cell aTemp[2];               /* Temporary holding area for apDiv[] */
  MemPage aOld[3];             /* Temporary copies of pPage and its siblings */

  /* 
................................................................................
    copyPage(pChild, pPage);
    pChild->pParent = pPage;
    sqlitepager_ref(pPage);
    pChild->isOverfull = 1;
    if( pCur ){
      sqlitepager_unref(pCur->pPage);
      pCur->pPage = pChild;


    }
    zeroPage(pPage);
    pPage->u.hdr.rightChild = pgnoChild;
    pParent = pPage;
    pPage = pChild;
  }else{
    rc = sqlitepager_write(pPage);
................................................................................
  /*
  ** Set iCur to be the index in apCell[] of the cell that the cursor
  ** is pointing to.  We will need this later on in order to keep the
  ** cursor pointing at the same cell.
  */
  if( pCur ){
    iCur = pCur->idx;
    for(i=0; idxDiv[i]<idx; i++){
      iCur += apOld[i]->nCell + 1;
    }
    sqlitepager_unref(pCur->pPage);
    pCur->pPage = 0;
  }

  /*
................................................................................
  */
  rc = balance(pBt, pParent, 0);

  /*
  ** Cleanup before returning.
  */
balance_cleanup:



  for(i=0; i<nOld; i++){
    if( apOld[i]!=&aOld[i] ) sqlitepager_unref(apOld[i]);
  }
  for(i=0; i<nNew; i++){
    sqlitepager_unref(apNew[i]);
  }
  if( pCur && pCur->pPage==0 ){
................................................................................
    return SQLITE_ERROR;  /* The cursor is not pointing to anything */
  }
  rc = sqlitepager_write(pPage);
  if( rc ) return rc;
  pCell = pPage->apCell[pCur->idx];
  pgnoChild = pCell->h.leftChild;
  clearCell(pCur->pBt, pCell);
  dropCell(pPage, pCur->idx, cellSize(pCell));
  if( pgnoChild ){
    /*

    ** If the entry we just deleted is not a leaf, then we've left a
    ** hole in an internal page.  We have to fill the hole by moving
    ** in a cell from a leaf.  The next Cell after the one just deleted
    ** is guaranteed to exist and to be a leaf so we can use it.
    */
    BtCursor leafCur;
    Cell *pNext;
    int szNext;
    getTempCursor(pCur, &leafCur);
    rc = sqliteBtreeNext(&leafCur, 0);
    if( rc!=SQLITE_OK ){
      return SQLITE_CORRUPT;
    }

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

    rc = balance(pCur->pBt, pPage, pCur);
    pCur->bSkipNext = 1;
  }
  return rc;
}

/*

** Boston, MA  02111-1307, USA.
**
** Author contact information:
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** $Id: btree.c,v 1.17 2001/06/28 11:50:22 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.
................................................................................
  int idx;                     /* Index of pPage in pParent->apCell[] */
  int nxDiv;                   /* Next divider slot in pParent->apCell[] */
  int rc;                      /* The return code */
  int iCur;                    /* apCell[iCur] is the cell of the cursor */
  int usedPerPage;             /* Memory needed for each page */
  int freePerPage;             /* Average free space per page */
  int totalSize;               /* Total bytes for all cells */
  MemPage *extraUnref = 0;     /* A page that needs to be unref-ed */
  Pgno pgno;                   /* Page number */
  Cell *apCell[MX_CELL*3+5];   /* All cells from pages being balanceed */
  int szCell[MX_CELL*3+5];     /* Local size of all cells */
  Cell aTemp[2];               /* Temporary holding area for apDiv[] */
  MemPage aOld[3];             /* Temporary copies of pPage and its siblings */

  /* 
................................................................................
    copyPage(pChild, pPage);
    pChild->pParent = pPage;
    sqlitepager_ref(pPage);
    pChild->isOverfull = 1;
    if( pCur ){
      sqlitepager_unref(pCur->pPage);
      pCur->pPage = pChild;
    }else{
      extraUnref = pChild;
    }
    zeroPage(pPage);
    pPage->u.hdr.rightChild = pgnoChild;
    pParent = pPage;
    pPage = pChild;
  }else{
    rc = sqlitepager_write(pPage);
................................................................................
  /*
  ** Set iCur to be the index in apCell[] of the cell that the cursor
  ** is pointing to.  We will need this later on in order to keep the
  ** cursor pointing at the same cell.
  */
  if( pCur ){
    iCur = pCur->idx;
    for(i=0; i<nDiv && idxDiv[i]<idx; i++){
      iCur += apOld[i]->nCell + 1;
    }
    sqlitepager_unref(pCur->pPage);
    pCur->pPage = 0;
  }

  /*
................................................................................
  */
  rc = balance(pBt, pParent, 0);

  /*
  ** Cleanup before returning.
  */
balance_cleanup:
  if( extraUnref ){
    sqlitepager_unref(extraUnref);
  }
  for(i=0; i<nOld; i++){
    if( apOld[i]!=&aOld[i] ) sqlitepager_unref(apOld[i]);
  }
  for(i=0; i<nNew; i++){
    sqlitepager_unref(apNew[i]);
  }
  if( pCur && pCur->pPage==0 ){
................................................................................
    return SQLITE_ERROR;  /* The cursor is not pointing to anything */
  }
  rc = sqlitepager_write(pPage);
  if( rc ) return rc;
  pCell = pPage->apCell[pCur->idx];
  pgnoChild = pCell->h.leftChild;
  clearCell(pCur->pBt, pCell);

  if( pgnoChild ){
    /*
    ** If the entry we are about to delete is not a leaf so if we do not
    ** do something we will leave a hole on an internal page.
    ** We have to fill the hole by moving in a cell from a leaf.  The
    ** next Cell after the one to be deleted is guaranteed to exist and
    ** to be a leaf so we can use it.
    */
    BtCursor leafCur;
    Cell *pNext;
    int szNext;
    getTempCursor(pCur, &leafCur);
    rc = sqliteBtreeNext(&leafCur, 0);
    if( rc!=SQLITE_OK ){
      return SQLITE_CORRUPT;
    }
    dropCell(pPage, pCur->idx, cellSize(pCell));
    pNext = leafCur.pPage->apCell[leafCur.idx];
    szNext = cellSize(pNext);
    pNext->h.leftChild = pgnoChild;
    insertCell(pPage, pCur->idx, pNext, szNext);
    rc = balance(pCur->pBt, pPage, pCur);
    if( rc ) return rc;
    pCur->bSkipNext = 1;
    dropCell(leafCur.pPage, leafCur.idx, szNext);
    rc = balance(pCur->pBt, leafCur.pPage, 0);
    releaseTempCursor(&leafCur);
  }else{
    dropCell(pPage, pCur->idx, cellSize(pCell));
    rc = balance(pCur->pBt, pPage, pCur);
    pCur->bSkipNext = 1;
  }
  return rc;
}

/*

#   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.3 2001/06/28 01:54:50 drh Exp $


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

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

................................................................................
  btree_close_cursor $::c1
  lindex [btree_pager_stats $::b1] 1
} {1}
do_test btree-9.7 {
  btree_rollback $::b1
  lindex [btree_pager_stats $::b1] 1
} {0}



























































































































































































































do_test btree-99.1 {
  btree_close $::b1
} {}
catch {unset data}
catch {unset key}

} ;# 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 btree database backend
#
# $Id: btree.test,v 1.4 2001/06/28 11:50:22 drh Exp $


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

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

................................................................................
  btree_close_cursor $::c1
  lindex [btree_pager_stats $::b1] 1
} {1}
do_test btree-9.7 {
  btree_rollback $::b1
  lindex [btree_pager_stats $::b1] 1
} {0}

# Create a tree of depth two.  That is, there is a single divider entry
# on the root pages and two leaf pages.  Then delete the divider entry
# see what happens.
#
do_test btree-10.1 {
  btree_begin_transaction $::b1
  btree_drop_table $::b1 2
  lindex [btree_pager_stats $::b1] 1
} {1}
do_test btree-10.2 {
  set ::c1 [btree_cursor $::b1 2]
  lindex [btree_pager_stats $::b1] 1
} {2}
do_test btree-10.3 {
  for {set i 1} {$i<=20} {incr i} {
    set key [format %03d $i]
    set data "*** $key *** $key *** $key *** $key ***"
    btree_insert $::c1 $key $data
  }
  select_keys $::c1
} {001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020}
#btree_page_dump $::b1 7
#btree_page_dump $::b1 2
#btree_page_dump $::b1 6
do_test btree-10.4 {
  btree_move_to $::c1 011
  btree_delete $::c1
  select_keys $::c1
} {001 002 003 004 005 006 007 008 009 010 012 013 014 015 016 017 018 019 020}
#btree_page_dump $::b1 2
for {set i 1} {$i<=20} {incr i} {
  do_test btree-10.5.$i {
    btree_move_to $::c1 [format %03d $i]
    lindex [btree_pager_stats $::b1] 1
  } {2}
}

# Create a tree with lots more pages
#
catch {unset ::data}
catch {unset ::key}
for {set i 21} {$i<=1000} {incr i} {
  do_test btree-11.1.$i.1 {
    set key [format %03d $i]
    set ::data "*** $key *** $key *** $key *** $key ***"
    btree_insert $::c1 $key $data
    btree_key $::c1
  } [format %03d $i]
  do_test btree-11.1.$i.2 {
    btree_data $::c1
  } $::data
  set ::key [format %03d [expr {$i/2}]]
  if {$::key=="011"} {set ::key 010}
  do_test btree-11.1.$i.3 {
    btree_move_to $::c1 $::key
    btree_key $::c1
  } $::key
}
catch {unset ::data}
catch {unset ::key}

# Make sure our reference count is still correct.
#
do_test btree-11.2 {
  btree_close_cursor $::c1
  lindex [btree_pager_stats $::b1] 1
} {1}
do_test btree-11.3 {
  set ::c1 [btree_cursor $::b1 2]
  lindex [btree_pager_stats $::b1] 1
} {2}
#btree_page_dump $::b1 2

# Delete the dividers on the root page
#
do_test btree-11.4 {
  btree_move_to $::c1 257
  btree_delete $::c1
  btree_next $::c1
  btree_key $::c1
} {258}
do_test btree-11.4.1 {
  btree_move_to $::c1 256
  btree_key $::c1
} {256}
do_test btree-11.4.2 {
  btree_move_to $::c1 258
  btree_key $::c1
} {258}
do_test btree-11.4.3 {
  btree_move_to $::c1 259
  btree_key $::c1
} {259}
do_test btree-11.4.4 {
  btree_move_to $::c1 257
  btree_key $::c1
} {256}
do_test btree-11.5 {
  btree_move_to $::c1 513
  btree_delete $::c1
  btree_next $::c1
  btree_key $::c1
} {514}
do_test btree-11.5.1 {
  btree_move_to $::c1 512
  btree_key $::c1
} {512}
do_test btree-11.5.2 {
  btree_move_to $::c1 514
  btree_key $::c1
} {514}
do_test btree-11.5.3 {
  btree_move_to $::c1 515
  btree_key $::c1
} {515}
do_test btree-11.5.4 {
  btree_move_to $::c1 513
  btree_key $::c1
} {512}
do_test btree-11.6 {
  btree_move_to $::c1 769
  btree_delete $::c1
  btree_next $::c1
  btree_key $::c1
} {770}
do_test btree-11.6.1 {
  btree_move_to $::c1 768
  btree_key $::c1
} {768}
do_test btree-11.6.2 {
  btree_move_to $::c1 771
  btree_key $::c1
} {771}
do_test btree-11.6.3 {
  btree_move_to $::c1 770
  btree_key $::c1
} {770}
do_test btree-11.6.4 {
  btree_move_to $::c1 769
  btree_key $::c1
} {768}
#btree_page_dump $::b1 2
#btree_page_dump $::b1 25

# Change the data on an intermediate node such that the node becomes overfull
# and has to split.  We happen to know that intermediate nodes exist on
# 337, 401 and 465 by the btree_page_dumps above
#
catch {unset ::data}
set ::data {This is going to be a very long data segment}
append ::data $::data
append ::data $::data
do_test btree-12.1 {
  btree_insert $::c1 337 $::data
  btree_data $::c1
} $::data
do_test btree-12.2 {
  btree_insert $::c1 401 $::data
  btree_data $::c1
} $::data
do_test btree-12.3 {
  btree_insert $::c1 465 $::data
  btree_data $::c1
} $::data
do_test btree-12.4 {
  btree_move_to $::c1 337
  btree_key $::c1
} {337}
do_test btree-12.5 {
  btree_data $::c1
} $::data
do_test btree-12.6 {
  btree_next $::c1
  btree_key $::c1
} {338}
do_test btree-12.7 {
  btree_move_to $::c1 464
  btree_key $::c1
} {464}
do_test btree-12.8 {
  btree_next $::c1
  btree_data $::c1
} $::data
do_test btree-12.9 {
  btree_next $::c1
  btree_key $::c1
} {466}
do_test btree-12.10 {
  btree_move_to $::c1 400
  btree_key $::c1
} {400}
do_test btree-12.11 {
  btree_next $::c1
  btree_data $::c1
} $::data
do_test btree-12.12 {
  btree_next $::c1
  btree_key $::c1
} {402}

# To Do:
#
#   1.  Do some deletes from the 3-layer tree
#   2.  Commit and reopen the database
#   3.  Read every 15th entry and make sure it works
#   4.  Implement btree_sanity and put it throughout this script
#

do_test btree-10.98 {
  btree_close_cursor $::c1
  lindex [btree_pager_stats $::b1] 1
} {1}
do_test btree-10.99 {
  btree_rollback $::b1
  lindex [btree_pager_stats $::b1] 1
} {0}
btree_pager_ref_dump $::b1

do_test btree-99.1 {
  btree_close $::b1
} {}
catch {unset data}
catch {unset key}

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

finish_test