Index: src/btree.c
==================================================================
--- src/btree.c
+++ src/btree.c
@@ -19,11 +19,11 @@
 ** 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 $
+** $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:
@@ -1621,10 +1621,11 @@
   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 */
@@ -1691,10 +1692,12 @@
     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;
@@ -1765,11 +1768,11 @@
   ** 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++){
+    for(i=0; i<nDiv && idxDiv[i]<idx; i++){
       iCur += apOld[i]->nCell + 1;
     }
     sqlitepager_unref(pCur->pPage);
     pCur->pPage = 0;
   }
@@ -1886,10 +1889,13 @@
 
   /*
   ** 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]);
@@ -1973,26 +1979,27 @@
   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.
+    ** 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);
@@ -2000,10 +2007,11 @@
     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;
 }

Index: test/btree.test
==================================================================
--- test/btree.test
+++ test/btree.test
@@ -21,11 +21,11 @@
 #
 #***********************************************************************
 # 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 $
+# $Id: btree.test,v 1.4 2001/06/28 11:50:22 drh Exp $
 
 
 set testdir [file dirname $argv0]
 source $testdir/tester.tcl
 
@@ -788,10 +788,228 @@
 } {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}