xref: /titanic_51/usr/src/lib/libsqlite/test/btree.test (revision c5c4113dfcabb1eed3d4bdf7609de5170027a794)

#pragma ident	"%Z%%M%	%I%	%E% SMI"

# 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: btree.test,v 1.15 2004/02/10 01:54:28 drh Exp $


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

if {[info commands btree_open]!="" && $SQLITE_PAGE_SIZE==1024
     && $SQLITE_USABLE_SIZE==1024} {

# 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}

# The second element of the list returned by btree_pager_stats is the
# number of pages currently checked out.  We'll be checking this value
# frequently during this test script, to make sure the btree library
# is properly releasing the pages it checks out, and thus avoiding
# page leaks.
#
do_test btree-1.1.1 {
  lindex [btree_pager_stats $::b1] 1
} {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.4.1 {
  lindex [btree_pager_stats $::b1] 1
} {1}
do_test btree-1.5 {
  set rc [catch {btree_cursor $::b1 2 1} ::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}
do_test btree-1.12 {
  lindex [btree_pager_stats $::b1] 1
} {0}

# Reopen the database and attempt to read the record that we wrote.
#
do_test btree-2.1 {
  set rc [catch {btree_cursor $::b1 2 1} ::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_test btree-2.7 {
  lindex [btree_pager_stats $::b1] 1
} {2}

# 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.1.1 {
  lindex [btree_pager_stats $::b1] 1
} {2}
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.22.1 {
  lindex [btree_pager_stats $::b1] 1
} {1}
do_test btree-3.23 {
  set rc [catch {btree_commit $::b1} msg]
  lappend rc $msg
} {0 {}}
do_test btree-3.23.1 {
  lindex [btree_pager_stats $::b1] 1
} {0}
do_test btree-3.24 {
  file size test1.bt
} {2048}
do_test btree-3.25 {
  set rc [catch {btree_cursor $::b1 2 1} ::c1]
  if {$rc} {lappend rc $::c1}
  set rc
} {0}
do_test btree-3.25.1 {
  lindex [btree_pager_stats $::b1] 1
} {2}
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
} {}
do_test btree-3.41 {
  lindex [btree_pager_stats $::b1] 1
} {2}


# 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.1.1 {
  lindex [btree_pager_stats $::b1] 1
} {2}
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_commit $::b1
  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}

# Completely close the database and reopen it.  Then check
# the data again.
#
do_test btree-4.6 {
  lindex [btree_pager_stats $::b1] 1
} {2}
do_test btree-4.7 {
  btree_close_cursor $::c1
  lindex [btree_pager_stats $::b1] 1
} {0}
do_test btree-4.8 {
  btree_close $::b1
  set ::b1 [btree_open test1.bt]
  set ::c1 [btree_cursor $::b1 2 1]
  lindex [btree_pager_stats $::b1] 1
} {2}
do_test btree-4.9 {
  set r {}
  btree_first $::c1
  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}

# Try to read and write meta data
#
do_test btree-5.1 {
  btree_get_meta $::b1
} {0 0 0 0 0 0 0 0 0 0}
do_test btree-5.2 {
  set rc [catch {btree_update_meta $::b1 1 2 3 4 5 6 7 8 9 10} msg]
  lappend rc $msg
} {1 SQLITE_ERROR}
do_test btree-5.3 {
  btree_begin_transaction $::b1
  set rc [catch {btree_update_meta $::b1 1 2 3 4 5 6 7 8 9 10} msg]
  lappend rc $msg
} {0 {}}
do_test btree-5.4 {
  btree_get_meta $::b1
} {0 2 3 4 5 6 7 8 9 10}
do_test btree-5.5 {
  btree_close_cursor $::c1
  btree_rollback $::b1
  btree_get_meta $::b1
} {0 0 0 0 0 0 0 0 0 0}
do_test btree-5.6 {
  btree_begin_transaction $::b1
  btree_update_meta $::b1 999 10 20 30 40 50 60 70 80 90
  btree_commit $::b1
  btree_get_meta $::b1
} {0 10 20 30 40 50 60 70 80 90}

proc select_all {cursor} {
  set r {}
  btree_move_to $cursor {}
  while 1 {
    set key [btree_key $cursor]
    if {$key==""} break
    lappend r $key
    lappend r [btree_data $cursor]
    btree_next $cursor
  }
  return $r
}
proc select_keys {cursor} {
  set r {}
  btree_move_to $cursor {}
  while 1 {
    set key [btree_key $cursor]
    if {$key==""} break
    lappend r $key
    btree_next $cursor
  }
  return $r
}

# Try to create a new table in the database file
#
do_test btree-6.1 {
  set rc [catch {btree_create_table $::b1} msg]
  lappend rc $msg
} {1 SQLITE_ERROR}
do_test btree-6.2 {
  btree_begin_transaction $::b1
  set ::t2 [btree_create_table $::b1]
} {3}
do_test btree-6.2.1 {
  lindex [btree_pager_stats $::b1] 1
} {1}
do_test btree-6.2.2 {
  set ::c2 [btree_cursor $::b1 $::t2 1]
  lindex [btree_pager_stats $::b1] 1
} {2}
do_test btree-6.2.3 {
  btree_insert $::c2 ten 10
  btree_key $::c2
} {ten}
do_test btree-6.3 {
  btree_commit $::b1
  set ::c1 [btree_cursor $::b1 2 1]
  lindex [btree_pager_stats $::b1] 1
} {3}
do_test btree-6.3.1 {
  select_all $::c1
} {five 5.00 four 4.00 six 6.00 three 3.00 two 2.00}
#btree_page_dump $::b1 3
do_test btree-6.4 {
  select_all $::c2
} {ten 10}

# Drop the new table, then create it again anew.
#
do_test btree-6.5 {
  btree_begin_transaction $::b1
} {}
do_test btree-6.6 {
  btree_close_cursor $::c2
} {}
do_test btree-6.6.1 {
  lindex [btree_pager_stats $::b1] 1
} {2}
do_test btree-6.7 {
  btree_drop_table $::b1 $::t2
} {}
do_test btree-6.7.1 {
  lindex [btree_get_meta $::b1] 0
} {1}
do_test btree-6.8 {
  set ::t2 [btree_create_table $::b1]
} {3}
do_test btree-6.8.1 {
  lindex [btree_get_meta $::b1] 0
} {0}
do_test btree-6.9 {
  set ::c2 [btree_cursor $::b1 $::t2 1]
  lindex [btree_pager_stats $::b1] 1
} {3}

do_test btree-6.9.1 {
  btree_move_to $::c2 {}
  btree_key $::c2
} {}

# If we drop table 2 it just clears the table.  Table 2 always exists.
#
do_test btree-6.10 {
  btree_close_cursor $::c1
  btree_drop_table $::b1 2
  set ::c1 [btree_cursor $::b1 2 1]
  btree_move_to $::c1 {}
  btree_key $::c1
} {}
do_test btree-6.11 {
  btree_commit $::b1
  select_all $::c1
} {}
do_test btree-6.12 {
  select_all $::c2
} {}
do_test btree-6.13 {
  btree_close_cursor $::c2
  lindex [btree_pager_stats $::b1] 1
} {2}

# Check to see that pages defragment properly.  To do this test we will
#
#   1.  Fill the first page table 2 with data.
#   2.  Delete every other entry of table 2.
#   3.  Insert a single entry that requires more contiguous
#       space than is available.
#
do_test btree-7.1 {
  btree_begin_transaction $::b1
} {}
catch {unset key}
catch {unset data}
do_test btree-7.2 {
  for {set i 0} {$i<36} {incr i} {
    set key [format %03d $i]
    set data "*** $key ***"
    btree_insert $::c1 $key $data
  }
  lrange [btree_cursor_dump $::c1] 4 5
} {8 1}
do_test btree-7.3 {
  btree_move_to $::c1 000
  while {[btree_key $::c1]!=""} {
    btree_delete $::c1
    btree_next $::c1
    btree_next $::c1
  }
  lrange [btree_cursor_dump $::c1] 4 5
} {512 19}
#btree_page_dump $::b1 2
do_test btree-7.4 {
  btree_insert $::c1 018 {*** 018 ***+++}
  btree_key $::c1
} {018}
do_test btree-7.5 {
  lrange [btree_cursor_dump $::c1] 4 5
} {480 1}
#btree_page_dump $::b1 2

# Delete an entry to make a hole of a known size, then immediately recreate
# that entry.  This tests the path into allocateSpace where the hole exactly
# matches the size of the desired space.
#
do_test btree-7.6 {
  btree_move_to $::c1 007
  btree_delete $::c1
  btree_move_to $::c1 011
  btree_delete $::c1
} {}
do_test btree-7.7 {
  lindex [btree_cursor_dump $::c1] 5
} {3}
#btree_page_dump $::b1 2
do_test btree-7.8 {
  btree_insert $::c1 007 {*** 007 ***}
  lindex [btree_cursor_dump $::c1] 5
} {2}
#btree_page_dump $::b1 2

# Make sure the freeSpace() routine properly coaleses adjacent memory blocks
#
do_test btree-7.9 {
  btree_move_to $::c1 013
  btree_delete $::c1
  lrange [btree_cursor_dump $::c1] 4 5
} {536 2}
do_test btree-7.10 {
  btree_move_to $::c1 009
  btree_delete $::c1
  lrange [btree_cursor_dump $::c1] 4 5
} {564 2}
do_test btree-7.11 {
  btree_move_to $::c1 018
  btree_delete $::c1
  lrange [btree_cursor_dump $::c1] 4 5
} {596 2}
do_test btree-7.13 {
  btree_move_to $::c1 033
  btree_delete $::c1
  lrange [btree_cursor_dump $::c1] 4 5
} {624 3}
do_test btree-7.14 {
  btree_move_to $::c1 035
  btree_delete $::c1
  lrange [btree_cursor_dump $::c1] 4 5
} {652 2}
#btree_page_dump $::b1 2
do_test btree-7.15 {
  lindex [btree_pager_stats $::b1] 1
} {2}

# Check to see that data on overflow pages work correctly.
#
do_test btree-8.1 {
  set data "*** This is a very long key "
  while {[string length $data]<256} {append data $data}
  set ::data $data
  btree_insert $::c1 020 $data
} {}
#btree_page_dump $::b1 2
do_test btree-8.1.1 {
  lindex [btree_pager_stats $::b1] 1
} {2}
#btree_pager_ref_dump $::b1
do_test btree-8.2 {
  string length [btree_data $::c1]
} [string length $::data]
do_test btree-8.3 {
  btree_data $::c1
} $::data
do_test btree-8.4 {
  btree_delete $::c1
} {}
do_test btree-8.4.1 {
  lindex [btree_get_meta $::b1] 0
} [expr {int(([string length $::data]-238+1019)/1020)}]
do_test btree-8.5 {
  set data "*** This is an even longer key"
  while {[string length $data]<2000} {append data $data}
  set ::data $data
  btree_insert $::c1 020 $data
} {}
do_test btree-8.6 {
  string length [btree_data $::c1]
} [string length $::data]
do_test btree-8.7 {
  btree_data $::c1
} $::data
do_test btree-8.8 {
  btree_commit $::b1
  btree_data $::c1
} $::data
do_test btree-8.9 {
  btree_close_cursor $::c1
  btree_close $::b1
  set ::b1 [btree_open test1.bt]
  set ::c1 [btree_cursor $::b1 2 1]
  btree_move_to $::c1 020
  btree_data $::c1
} $::data
do_test btree-8.10 {
  btree_begin_transaction $::b1
  btree_delete $::c1
} {}
do_test btree-8.11 {
  lindex [btree_get_meta $::b1] 0
} [expr {int(([string length $::data]-238+1019)/1020)}]

# Now check out keys on overflow pages.
#
do_test btree-8.12 {
  set ::keyprefix "This is a long prefix to a key "
  while {[string length $::keyprefix]<256} {append ::keyprefix $::keyprefix}
  btree_close_cursor $::c1
  btree_drop_table $::b1 2
  lindex [btree_get_meta $::b1] 0
} {4}
do_test btree-8.12.1 {
  set ::c1 [btree_cursor $::b1 2 1]
  btree_insert $::c1 ${::keyprefix}1 1
  btree_data $::c1
} {1}
do_test btree-8.13 {
  btree_key $::c1
} ${keyprefix}1
do_test btree-8.14 {
  btree_insert $::c1 ${::keyprefix}2 2
  btree_insert $::c1 ${::keyprefix}3 3
  btree_key $::c1
} ${keyprefix}3
do_test btree-8.15 {
  btree_move_to $::c1 ${::keyprefix}2
  btree_data $::c1
} {2}
do_test btree-8.16 {
  btree_move_to $::c1 ${::keyprefix}1
  btree_data $::c1
} {1}
do_test btree-8.17 {
  btree_move_to $::c1 ${::keyprefix}3
  btree_data $::c1
} {3}
do_test btree-8.18 {
  lindex [btree_get_meta $::b1] 0
} {1}
do_test btree-8.19 {
  btree_move_to $::c1 ${::keyprefix}2
  btree_key $::c1
} ${::keyprefix}2
#btree_page_dump $::b1 2
do_test btree-8.20 {
  btree_delete $::c1
  btree_next $::c1
  btree_key $::c1
} ${::keyprefix}3
#btree_page_dump $::b1 2
do_test btree-8.21 {
  lindex [btree_get_meta $::b1] 0
} {2}
do_test btree-8.22 {
  lindex [btree_pager_stats $::b1] 1
} {2}
do_test btree-8.23 {
  btree_close_cursor $::c1
  btree_drop_table $::b1 2
  set ::c1 [btree_cursor $::b1 2 1]
  lindex [btree_get_meta $::b1] 0
} {4}
do_test btree-8.24 {
  lindex [btree_pager_stats $::b1] 1
} {2}
#btree_pager_ref_dump $::b1

# Check page splitting logic
#
do_test btree-9.1 {
  for {set i 1} {$i<=19} {incr i} {
    set key [format %03d $i]
    set data "*** $key *** $key *** $key *** $key ***"
    btree_insert $::c1 $key $data
  }
} {}
#btree_tree_dump $::b1 2
#btree_pager_ref_dump $::b1
#set pager_refinfo_enable 1
do_test btree-9.2 {
  btree_insert $::c1 020 {*** 020 *** 020 *** 020 *** 020 ***}
  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 5
#btree_page_dump $::b1 2
#btree_page_dump $::b1 7
#btree_pager_ref_dump $::b1
#set pager_refinfo_enable 0

# The previous "select_keys" command left the cursor pointing at the root
# page.  So there should only be two pages checked out.  2 (the root) and
# page 1.
do_test btree-9.2.1 {
  lindex [btree_pager_stats $::b1] 1
} {2}
for {set i 1} {$i<=20} {incr i} {
  do_test btree-9.3.$i.1 [subst {
    btree_move_to $::c1 [format %03d $i]
    btree_key $::c1
  }] [format %03d $i]
  do_test btree-9.3.$i.2 [subst {
    btree_move_to $::c1 [format %03d $i]
    string range \[btree_data $::c1\] 0 10
  }] "*** [format %03d $i] ***"
}
do_test btree-9.4.1 {
  lindex [btree_pager_stats $::b1] 1
} {3}

# Check the page joining logic.
#
#btree_page_dump $::b1 2
#btree_pager_ref_dump $::b1
do_test btree-9.4.2 {
  btree_move_to $::c1 005
  btree_delete $::c1
} {}
#btree_page_dump $::b1 2
for {set i 1} {$i<=19} {incr i} {
  if {$i==5} continue
  do_test btree-9.5.$i.1 [subst {
    btree_move_to $::c1 [format %03d $i]
    btree_key $::c1
  }] [format %03d $i]
  do_test btree-9.5.$i.2 [subst {
    btree_move_to $::c1 [format %03d $i]
    string range \[btree_data $::c1\] 0 10
  }] "*** [format %03d $i] ***"
}
#btree_pager_ref_dump $::b1
do_test btree-9.6 {
  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 1]
  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_tree_dump $::b1 2
#btree_pager_ref_dump $::b1
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}
  #btree_pager_ref_dump $::b1
  #btree_tree_dump $::b1 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 1]
  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
  set n [btree_key $::c1]
  expr {$n==256||$n==258}
} {1}
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
  set n [btree_key $::c1]
  expr {$n==512||$n==514}
} {1}
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
  set n [btree_key $::c1]
  expr {$n==768||$n==770}
} {1}
#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}
do_test btree-13.1 {
  btree_integrity_check $::b1 2 3
} {}

# 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-15.98 {
  btree_close_cursor $::c1
  lindex [btree_pager_stats $::b1] 1
} {1}
do_test btree-15.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