diff options
Diffstat (limited to 'usr/src/lib/libsqlite/test/btree2.test')
| -rw-r--r-- | usr/src/lib/libsqlite/test/btree2.test | 449 |
1 files changed, 449 insertions, 0 deletions
diff --git a/usr/src/lib/libsqlite/test/btree2.test b/usr/src/lib/libsqlite/test/btree2.test new file mode 100644 index 0000000000..45c0203a52 --- /dev/null +++ b/usr/src/lib/libsqlite/test/btree2.test @@ -0,0 +1,449 @@ + +#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: btree2.test,v 1.10 2002/02/19 13:39:23 drh Exp $ + + +set testdir [file dirname $argv0] +source $testdir/tester.tcl + +if {[info commands btree_open]!=""} { + +# Create a new database file containing no entries. The database should +# contain 5 tables: +# +# 2 The descriptor table +# 3 The foreground table +# 4 The background table +# 5 The long key table +# 6 The long data table +# +# An explanation for what all these tables are used for is provided below. +# +do_test btree2-1.1 { + expr srand(1) + file delete -force test2.bt + file delete -force test2.bt-journal + set ::b [btree_open test2.bt] + btree_begin_transaction $::b + btree_create_table $::b +} {3} +do_test btree2-1.2 { + btree_create_table $::b +} {4} +do_test btree2-1.3 { + btree_create_table $::b +} {5} +do_test btree2-1.4 { + btree_create_table $::b +} {6} +do_test btree2-1.5 { + set ::c2 [btree_cursor $::b 2 1] + btree_insert $::c2 {one} {1} + btree_delete $::c2 + btree_close_cursor $::c2 + btree_commit $::b + btree_integrity_check $::b 2 3 4 5 6 +} {} + +# This test module works by making lots of pseudo-random changes to a +# database while simultaneously maintaining an invariant on that database. +# Periodically, the script does a sanity check on the database and verifies +# that the invariant is satisfied. +# +# The invariant is as follows: +# +# 1. The descriptor table always contains 2 enters. An entry keyed by +# "N" is the number of elements in the foreground and background tables +# combined. The entry keyed by "L" is the number of digits in the keys +# for foreground and background tables. +# +# 2. The union of the foreground an background tables consists of N entries +# where each entry an L-digit key. (Actually, some keys can be longer +# than L characters, but they always start with L digits.) The keys +# cover all integers between 1 and N. Whenever an entry is added to +# the foreground it is removed form the background and vice versa. +# +# 3. Some entries in the foreground and background tables have keys that +# begin with an L-digit number but are followed by additional characters. +# For each such entry there is a corresponding entry in the long key +# table. The long key table entry has a key which is just the L-digit +# number and data which is the length of the key in the foreground and +# background tables. +# +# 4. The data for both foreground and background entries is usually a +# short string. But some entries have long data strings. For each +# such entries there is an entry in the long data type. The key to +# long data table is an L-digit number. (The extension on long keys +# is omitted.) The data is the number of charaters in the data of the +# foreground or background entry. +# +# The following function builds a database that satisfies all of the above +# invariants. +# +proc build_db {N L} { + for {set i 2} {$i<=6} {incr i} { + catch {btree_close_cursor [set ::c$i]} + btree_clear_table $::b $i + set ::c$i [btree_cursor $::b $i 1] + } + btree_insert $::c2 N $N + btree_insert $::c2 L $L + set format %0${L}d + for {set i 1} {$i<=$N} {incr i} { + set key [format $format $i] + set data $key + btree_insert $::c3 $key $data + } +} + +# Given a base key number and a length, construct the full text of the key +# or data. +# +proc make_payload {keynum L len} { + set key [format %0${L}d $keynum] + set r $key + set i 1 + while {[string length $r]<$len} { + append r " ($i) $key" + incr i + } + return [string range $r 0 [expr {$len-1}]] +} + +# Verify the invariants on the database. Return an empty string on +# success or an error message if something is amiss. +# +proc check_invariants {} { + set ck [btree_integrity_check $::b 2 3 4 5 6] + if {$ck!=""} { + puts "\n*** SANITY:\n$ck" + exit + return $ck + } + btree_move_to $::c3 {} + btree_move_to $::c4 {} + btree_move_to $::c2 N + set N [btree_data $::c2] + btree_move_to $::c2 L + set L [btree_data $::c2] + set LM1 [expr {$L-1}] + for {set i 1} {$i<=$N} {incr i} { + set key [btree_key $::c3] + if {[scan $key %d k]<1} {set k 0} + if {$k!=$i} { + set key [btree_key $::c4] + if {[scan $key %d k]<1} {set k 0} + if {$k!=$i} { + # puts "MISSING $i" + # puts {Page 3:}; btree_page_dump $::b 3 + # puts {Page 4:}; btree_page_dump $::b 4 + # exit + return "Key $i is missing from both foreground and background" + } + set data [btree_data $::c4] + btree_next $::c4 + } else { + set data [btree_data $::c3] + btree_next $::c3 + } + set skey [string range $key 0 $LM1] + if {[btree_move_to $::c5 $skey]==0} { + set keylen [btree_data $::c5] + } else { + set keylen $L + } + if {[string length $key]!=$keylen} { + return "Key $i is the wrong size.\ + Is \"$key\" but should be \"[make_payload $k $L $keylen]\"" + } + if {[make_payload $k $L $keylen]!=$key} { + return "Key $i has an invalid extension" + } + if {[btree_move_to $::c6 $skey]==0} { + set datalen [btree_data $::c6] + } else { + set datalen $L + } + if {[string length $data]!=$datalen} { + return "Data for $i is the wrong size.\ + Is [string length $data] but should be $datalen" + } + if {[make_payload $k $L $datalen]!=$data} { + return "Entry $i has an incorrect data" + } + } +} + +# Make random changes to the database such that each change preserves +# the invariants. The number of changes is $n*N where N is the parameter +# from the descriptor table. Each changes begins with a random key. +# the entry with that key is put in the foreground table with probability +# $I and it is put in background with probability (1.0-$I). It gets +# a long key with probability $K and long data with probability $D. +# +set chngcnt 0 +proc random_changes {n I K D} { + btree_move_to $::c2 N + set N [btree_data $::c2] + btree_move_to $::c2 L + set L [btree_data $::c2] + set LM1 [expr {$L-1}] + set total [expr {int($N*$n)}] + set format %0${L}d + for {set i 0} {$i<$total} {incr i} { + set k [expr {int(rand()*$N)+1}] + set insert [expr {rand()<=$I}] + set longkey [expr {rand()<=$K}] + set longdata [expr {rand()<=$D}] + # incr ::chngcnt + # if {$::chngcnt==251} {btree_tree_dump $::b 3} + # puts "CHANGE $::chngcnt: $k $insert $longkey $longdata" + if {$longkey} { + set x [expr {rand()}] + set keylen [expr {int($x*$x*$x*$x*3000)+10}] + } else { + set keylen $L + } + set key [make_payload $k $L $keylen] + if {$longdata} { + set x [expr {rand()}] + set datalen [expr {int($x*$x*$x*$x*3000)+10}] + } else { + set datalen $L + } + set data [make_payload $k $L $datalen] + set basekey [format $format $k] + if {[set c [btree_move_to $::c3 $basekey]]==0} { + btree_delete $::c3 + } else { + if {$c<0} {btree_next $::c3} + if {[string match $basekey* [btree_key $::c3]]} { + btree_delete $::c3 + } + } + if {[set c [btree_move_to $::c4 $basekey]]==0} { + btree_delete $::c4 + } else { + if {$c<0} {btree_next $::c4} + if {[string match $basekey* [btree_key $::c4]]} { + btree_delete $::c4 + } + } + if {[scan [btree_key $::c4] %d kx]<1} {set kx -1} + if {$kx==$k} { + btree_delete $::c4 + } + if {$insert} { + btree_insert $::c3 $key $data + } else { + btree_insert $::c4 $key $data + } + if {$longkey} { + btree_insert $::c5 $basekey $keylen + } elseif {[btree_move_to $::c5 $basekey]==0} { + btree_delete $::c5 + } + if {$longdata} { + btree_insert $::c6 $basekey $datalen + } elseif {[btree_move_to $::c6 $basekey]==0} { + btree_delete $::c6 + } + # set ck [btree_integrity_check $::b 2 3 4 5 6] + # if {$ck!=""} { + # puts "\nSANITY CHECK FAILED!\n$ck" + # exit + # } + # puts "PAGE 3:"; btree_page_dump $::b 3 + # puts "PAGE 4:"; btree_page_dump $::b 4 + } +} + +# Repeat this test sequence on database of various sizes +# +set testno 2 +foreach {N L} { + 10 2 + 50 2 + 200 3 + 2000 5 +} { + puts "**** N=$N L=$L ****" + set hash [md5file test2.bt] + do_test btree2-$testno.1 [subst -nocommands { + set ::c2 [btree_cursor $::b 2 1] + set ::c3 [btree_cursor $::b 3 1] + set ::c4 [btree_cursor $::b 4 1] + set ::c5 [btree_cursor $::b 5 1] + set ::c6 [btree_cursor $::b 6 1] + btree_begin_transaction $::b + build_db $N $L + check_invariants + }] {} + do_test btree2-$testno.2 { + btree_close_cursor $::c2 + btree_close_cursor $::c3 + btree_close_cursor $::c4 + btree_close_cursor $::c5 + btree_close_cursor $::c6 + btree_rollback $::b + md5file test2.bt + } $hash + do_test btree2-$testno.3 [subst -nocommands { + btree_begin_transaction $::b + set ::c2 [btree_cursor $::b 2 1] + set ::c3 [btree_cursor $::b 3 1] + set ::c4 [btree_cursor $::b 4 1] + set ::c5 [btree_cursor $::b 5 1] + set ::c6 [btree_cursor $::b 6 1] + build_db $N $L + check_invariants + }] {} + do_test btree2-$testno.4 { + btree_commit $::b + check_invariants + } {} + do_test btree2-$testno.5 { + lindex [btree_pager_stats $::b] 1 + } {6} + do_test btree2-$testno.6 { + btree_close_cursor $::c2 + btree_close_cursor $::c3 + btree_close_cursor $::c4 + btree_close_cursor $::c5 + btree_close_cursor $::c6 + lindex [btree_pager_stats $::b] 1 + } {0} + do_test btree2-$testno.7 { + btree_close $::b + } {} +after 100 + # For each database size, run various changes tests. + # + set num2 1 + foreach {n I K D} { + 0.5 0.5 0.1 0.1 + 1.0 0.2 0.1 0.1 + 1.0 0.8 0.1 0.1 + 2.0 0.0 0.1 0.1 + 2.0 1.0 0.1 0.1 + 2.0 0.0 0.0 0.0 + 2.0 1.0 0.0 0.0 + } { + set testid btree2-$testno.8.$num2 + set hash [md5file test2.bt] + do_test $testid.0 { + set ::b [btree_open test2.bt] + set ::c2 [btree_cursor $::b 2 1] + set ::c3 [btree_cursor $::b 3 1] + set ::c4 [btree_cursor $::b 4 1] + set ::c5 [btree_cursor $::b 5 1] + set ::c6 [btree_cursor $::b 6 1] + check_invariants + } {} + set cnt 6 + for {set i 2} {$i<=6} {incr i} { + if {[lindex [btree_cursor_dump [set ::c$i]] 0]!=$i} {incr cnt} + } + do_test $testid.1 { + btree_begin_transaction $::b + lindex [btree_pager_stats $::b] 1 + } $cnt + # exec cp test2.bt test2.bt.bu1 + do_test $testid.2 [subst { + random_changes $n $I $K $D + }] {} + do_test $testid.3 { + check_invariants + } {} + do_test $testid.4 { + btree_close_cursor $::c2 + btree_close_cursor $::c3 + btree_close_cursor $::c4 + btree_close_cursor $::c5 + btree_close_cursor $::c6 + btree_rollback $::b + md5file test2.bt + } $hash + # exec cp test2.bt test2.bt.bu2 + btree_begin_transaction $::b + set ::c2 [btree_cursor $::b 2 1] + set ::c3 [btree_cursor $::b 3 1] + set ::c4 [btree_cursor $::b 4 1] + set ::c5 [btree_cursor $::b 5 1] + set ::c6 [btree_cursor $::b 6 1] + do_test $testid.5 [subst { + random_changes $n $I $K $D + }] {} + do_test $testid.6 { + check_invariants + } {} + do_test $testid.7 { + btree_commit $::b + check_invariants + } {} + set hash [md5file test2.bt] + do_test $testid.8 { + btree_close_cursor $::c2 + btree_close_cursor $::c3 + btree_close_cursor $::c4 + btree_close_cursor $::c5 + btree_close_cursor $::c6 + lindex [btree_pager_stats $::b] 1 + } {0} + do_test $testid.9 { + btree_close $::b + set ::b [btree_open test2.bt] + set ::c2 [btree_cursor $::b 2 1] + set ::c3 [btree_cursor $::b 3 1] + set ::c4 [btree_cursor $::b 4 1] + set ::c5 [btree_cursor $::b 5 1] + set ::c6 [btree_cursor $::b 6 1] + check_invariants + } {} + do_test $testid.10 { + btree_close_cursor $::c2 + btree_close_cursor $::c3 + btree_close_cursor $::c4 + btree_close_cursor $::c5 + btree_close_cursor $::c6 + lindex [btree_pager_stats $::b] 1 + } {0} + do_test $testid.11 { + btree_close $::b + } {} + incr num2 + } + incr testno + set ::b [btree_open test2.bt] +} + +# Testing is complete. Shut everything down. +# +do_test btree-999.1 { + lindex [btree_pager_stats $::b] 1 +} {0} +do_test btree-999.2 { + btree_close $::b +} {} +do_test btree-999.3 { + file delete -force test2.bt + file exists test2.bt-journal +} {0} + +} ;# end if( not mem: and has pager_open command ); + +finish_test |