2N/A#pragma ident "%Z%%M% %I% %E% SMI"
2N/A# The author disclaims copyright to this source code. In place of
2N/A# a legal notice, here is a blessing:
2N/A# May you do good and not evil.
2N/A# May you find forgiveness for yourself and forgive others.
2N/A# May you share freely, never taking more than you give.
2N/A#***********************************************************************
2N/A# This file implements regression tests for SQLite library. The
2N/A# focus of this script is btree database backend
2N/Aset testdir [file dirname $argv0]
2N/Aif {[info commands btree_open]!=""} {
2N/A# Create a new database file containing no entries. The database should
2N/A# 2 The descriptor table
2N/A# 3 The foreground table
2N/A# 4 The background table
2N/A# 5 The long key table
2N/A# 6 The long data table
2N/A# An explanation for what all these tables are used for is provided below.
2N/A btree_begin_transaction $::b
2N/A btree_create_table $::b
2N/A btree_create_table $::b
2N/A btree_create_table $::b
2N/A btree_create_table $::b
2N/A set ::c2 [btree_cursor $::b 2 1]
2N/A btree_insert $::c2 {one} {1}
2N/A btree_close_cursor $::c2
2N/A btree_integrity_check $::b 2 3 4 5 6
2N/A# This test module works by making lots of pseudo-random changes to a
2N/A# database while simultaneously maintaining an invariant on that database.
2N/A# Periodically, the script does a sanity check on the database and verifies
2N/A# that the invariant is satisfied.
2N/A# The invariant is as follows:
2N/A# 1. The descriptor table always contains 2 enters. An entry keyed by
2N/A# "N" is the number of elements in the foreground and background tables
2N/A# combined. The entry keyed by "L" is the number of digits in the keys
2N/A# for foreground and background tables.
2N/A# 2. The union of the foreground an background tables consists of N entries
2N/A# where each entry an L-digit key. (Actually, some keys can be longer
2N/A# than L characters, but they always start with L digits.) The keys
2N/A# cover all integers between 1 and N. Whenever an entry is added to
2N/A# the foreground it is removed form the background and vice versa.
2N/A# 3. Some entries in the foreground and background tables have keys that
2N/A# begin with an L-digit number but are followed by additional characters.
2N/A# For each such entry there is a corresponding entry in the long key
2N/A# table. The long key table entry has a key which is just the L-digit
2N/A# number and data which is the length of the key in the foreground and
2N/A# 4. The data for both foreground and background entries is usually a
2N/A# short string. But some entries have long data strings. For each
2N/A# such entries there is an entry in the long data type. The key to
2N/A# long data table is an L-digit number. (The extension on long keys
2N/A# is omitted.) The data is the number of charaters in the data of the
2N/A# foreground or background entry.
2N/A# The following function builds a database that satisfies all of the above
2N/Aproc build_db {N L} {
2N/A for {set i 2} {$i<=6} {incr i} {
2N/A catch {btree_close_cursor [set ::c$i]}
2N/A btree_clear_table $::b $i
2N/A set ::c$i [btree_cursor $::b $i 1]
2N/A btree_insert $::c2 N $N
2N/A btree_insert $::c2 L $L
2N/A for {set i 1} {$i<=$N} {incr i} {
2N/A set key [format $format $i]
2N/A btree_insert $::c3 $key $data
2N/A# Given a base key number and a length, construct the full text of the key
2N/Aproc make_payload {keynum L len} {
2N/A set key [format %0${L}d $keynum]
2N/A while {[string length $r]<$len} {
2N/A append r " ($i) $key"
2N/A return [string range $r 0 [expr {$len-1}]]
2N/A# Verify the invariants on the database. Return an empty string on
2N/A# success or an error message if something is amiss.
2N/Aproc check_invariants {} {
2N/A set ck [btree_integrity_check $::b 2 3 4 5 6]
2N/A puts "\n*** SANITY:\n$ck"
2N/A btree_move_to $::c3 {}
2N/A btree_move_to $::c4 {}
2N/A btree_move_to $::c2 N
2N/A set N [btree_data $::c2]
2N/A btree_move_to $::c2 L
2N/A set L [btree_data $::c2]
2N/A set LM1 [expr {$L-1}]
2N/A for {set i 1} {$i<=$N} {incr i} {
2N/A set key [btree_key $::c3]
2N/A if {[scan $key %d k]<1} {set k 0}
2N/A set key [btree_key $::c4]
2N/A if {[scan $key %d k]<1} {set k 0}
2N/A # puts {Page 3:}; btree_page_dump $::b 3
2N/A # puts {Page 4:}; btree_page_dump $::b 4
2N/A return "Key $i is missing from both foreground and background"
2N/A set data [btree_data $::c4]
2N/A set data [btree_data $::c3]
2N/A set skey [string range $key 0 $LM1]
2N/A if {[btree_move_to $::c5 $skey]==0} {
2N/A set keylen [btree_data $::c5]
2N/A if {[string length $key]!=$keylen} {
2N/A return "Key $i is the wrong size.\
2N/A Is \"$key\" but should be \"[make_payload $k $L $keylen]\""
2N/A if {[make_payload $k $L $keylen]!=$key} {
2N/A return "Key $i has an invalid extension"
2N/A if {[btree_move_to $::c6 $skey]==0} {
2N/A set datalen [btree_data $::c6]
2N/A if {[string length $data]!=$datalen} {
2N/A return "Data for $i is the wrong size.\
2N/A Is [string length $data] but should be $datalen"
2N/A if {[make_payload $k $L $datalen]!=$data} {
2N/A return "Entry $i has an incorrect data"
2N/A# Make random changes to the database such that each change preserves
2N/A# the invariants. The number of changes is $n*N where N is the parameter
2N/A# from the descriptor table. Each changes begins with a random key.
2N/A# the entry with that key is put in the foreground table with probability
2N/A# $I and it is put in background with probability (1.0-$I). It gets
2N/A# a long key with probability $K and long data with probability $D.
2N/Aproc random_changes {n I K D} {
2N/A btree_move_to $::c2 N
2N/A set N [btree_data $::c2]
2N/A btree_move_to $::c2 L
2N/A set L [btree_data $::c2]
2N/A set LM1 [expr {$L-1}]
2N/A set total [expr {int($N*$n)}]
2N/A for {set i 0} {$i<$total} {incr i} {
2N/A set k [expr {int(rand()*$N)+1}]
2N/A set insert [expr {rand()<=$I}]
2N/A set longkey [expr {rand()<=$K}]
2N/A set longdata [expr {rand()<=$D}]
2N/A # if {$::chngcnt==251} {btree_tree_dump $::b 3}
2N/A # puts "CHANGE $::chngcnt: $k $insert $longkey $longdata"
2N/A set x [expr {rand()}]
2N/A set keylen [expr {int($x*$x*$x*$x*3000)+10}]
2N/A set key [make_payload $k $L $keylen]
2N/A set x [expr {rand()}]
2N/A set datalen [expr {int($x*$x*$x*$x*3000)+10}]
2N/A set data [make_payload $k $L $datalen]
2N/A set basekey [format $format $k]
2N/A if {[set c [btree_move_to $::c3 $basekey]]==0} {
2N/A if {$c<0} {btree_next $::c3}
2N/A if {[string match $basekey* [btree_key $::c3]]} {
2N/A if {[set c [btree_move_to $::c4 $basekey]]==0} {
2N/A if {$c<0} {btree_next $::c4}
2N/A if {[string match $basekey* [btree_key $::c4]]} {
2N/A if {[scan [btree_key $::c4] %d kx]<1} {set kx -1}
2N/A btree_insert $::c3 $key $data
2N/A btree_insert $::c4 $key $data
2N/A btree_insert $::c5 $basekey $keylen
2N/A } elseif {[btree_move_to $::c5 $basekey]==0} {
2N/A btree_insert $::c6 $basekey $datalen
2N/A } elseif {[btree_move_to $::c6 $basekey]==0} {
2N/A # set ck [btree_integrity_check $::b 2 3 4 5 6]
2N/A # puts "\nSANITY CHECK FAILED!\n$ck"
2N/A # puts "PAGE 3:"; btree_page_dump $::b 3
2N/A # puts "PAGE 4:"; btree_page_dump $::b 4
2N/A# Repeat this test sequence on database of various sizes
2N/A puts "**** N=$N L=$L ****"
2N/A do_test btree2-$testno.1 [subst -nocommands {
2N/A set ::c2 [btree_cursor $::b 2 1]
2N/A set ::c3 [btree_cursor $::b 3 1]
2N/A set ::c4 [btree_cursor $::b 4 1]
2N/A set ::c5 [btree_cursor $::b 5 1]
2N/A set ::c6 [btree_cursor $::b 6 1]
2N/A btree_begin_transaction $::b
2N/A do_test btree2-$testno.2 {
2N/A btree_close_cursor $::c2
2N/A btree_close_cursor $::c3
2N/A btree_close_cursor $::c4
2N/A btree_close_cursor $::c5
2N/A btree_close_cursor $::c6
2N/A do_test btree2-$testno.3 [subst -nocommands {
2N/A btree_begin_transaction $::b
2N/A set ::c2 [btree_cursor $::b 2 1]
2N/A set ::c3 [btree_cursor $::b 3 1]
2N/A set ::c4 [btree_cursor $::b 4 1]
2N/A set ::c5 [btree_cursor $::b 5 1]
2N/A set ::c6 [btree_cursor $::b 6 1]
2N/A do_test btree2-$testno.4 {
2N/A do_test btree2-$testno.5 {
2N/A lindex [btree_pager_stats $::b] 1
2N/A do_test btree2-$testno.6 {
2N/A btree_close_cursor $::c2
2N/A btree_close_cursor $::c3
2N/A btree_close_cursor $::c4
2N/A btree_close_cursor $::c5
2N/A btree_close_cursor $::c6
2N/A lindex [btree_pager_stats $::b] 1
2N/A do_test btree2-$testno.7 {
2N/A # For each database size, run various changes tests.
2N/A set testid btree2-$testno.8.$num2
2N/A set ::c2 [btree_cursor $::b 2 1]
2N/A set ::c3 [btree_cursor $::b 3 1]
2N/A set ::c4 [btree_cursor $::b 4 1]
2N/A set ::c5 [btree_cursor $::b 5 1]
2N/A set ::c6 [btree_cursor $::b 6 1]
2N/A for {set i 2} {$i<=6} {incr i} {
2N/A if {[lindex [btree_cursor_dump [set ::c$i]] 0]!=$i} {incr cnt}
2N/A btree_begin_transaction $::b
2N/A lindex [btree_pager_stats $::b] 1
2N/A do_test $testid.2 [subst {
2N/A random_changes $n $I $K $D
2N/A btree_close_cursor $::c2
2N/A btree_close_cursor $::c3
2N/A btree_close_cursor $::c4
2N/A btree_close_cursor $::c5
2N/A btree_close_cursor $::c6
2N/A btree_begin_transaction $::b
2N/A set ::c2 [btree_cursor $::b 2 1]
2N/A set ::c3 [btree_cursor $::b 3 1]
2N/A set ::c4 [btree_cursor $::b 4 1]
2N/A set ::c5 [btree_cursor $::b 5 1]
2N/A set ::c6 [btree_cursor $::b 6 1]
2N/A do_test $testid.5 [subst {
2N/A random_changes $n $I $K $D
2N/A btree_close_cursor $::c2
2N/A btree_close_cursor $::c3
2N/A btree_close_cursor $::c4
2N/A btree_close_cursor $::c5
2N/A btree_close_cursor $::c6
2N/A lindex [btree_pager_stats $::b] 1
2N/A set ::c2 [btree_cursor $::b 2 1]
2N/A set ::c3 [btree_cursor $::b 3 1]
2N/A set ::c4 [btree_cursor $::b 4 1]
2N/A set ::c5 [btree_cursor $::b 5 1]
2N/A set ::c6 [btree_cursor $::b 6 1]
2N/A do_test $testid.10 {
2N/A btree_close_cursor $::c2
2N/A btree_close_cursor $::c3
2N/A btree_close_cursor $::c4
2N/A btree_close_cursor $::c5
2N/A btree_close_cursor $::c6
2N/A lindex [btree_pager_stats $::b] 1
2N/A do_test $testid.11 {
2N/A# Testing is complete. Shut everything down.
2N/Ado_test btree-999.1 {
2N/A lindex [btree_pager_stats $::b] 1
2N/Ado_test btree-999.2 {
2N/Ado_test btree-999.3 {
2N/A} ;# end if( not mem: and has pager_open command );