3 # The author disclaims copyright to this source code. In place of
4 # a legal notice, here is a blessing:
6 # May you do good and not evil.
7 # May you find forgiveness for yourself and forgive others.
8 # May you share freely, never taking more than you give.
10 #***********************************************************************
11 # This file implements regression tests for SQLite library. The
12 # focus of this script is btree database backend
14 # $Id: btree2.test,v 1.14 2005/01/11 10:25:07 danielk1977 Exp $
17 set testdir [file dirname $argv0]
18 source $testdir/tester.tcl
20 if {[info commands btree_open]!=""} {
22 # Create a new database file containing no entries. The database should
25 # 2 The descriptor table
26 # 3 The foreground table
27 # 4 The background table
28 # 5 The long key table
29 # 6 The long data table
31 # An explanation for what all these tables are used for is provided below.
35 file delete -force test2.bt
36 file delete -force test2.bt-journal
37 set ::b [btree_open test2.bt 2000 0]
38 btree_begin_transaction $::b
39 btree_create_table $::b 0
42 btree_create_table $::b 0
45 btree_create_table $::b 0
48 btree_create_table $::b 0
51 btree_create_table $::b 0
54 set ::c2 [btree_cursor $::b 2 1]
55 btree_insert $::c2 {one} {1}
56 btree_move_to $::c2 {one}
58 btree_close_cursor $::c2
60 btree_integrity_check $::b 1 2 3 4 5 6
63 # This test module works by making lots of pseudo-random changes to a
64 # database while simultaneously maintaining an invariant on that database.
65 # Periodically, the script does a sanity check on the database and verifies
66 # that the invariant is satisfied.
68 # The invariant is as follows:
70 # 1. The descriptor table always contains 2 enters. An entry keyed by
71 # "N" is the number of elements in the foreground and background tables
72 # combined. The entry keyed by "L" is the number of digits in the keys
73 # for foreground and background tables.
75 # 2. The union of the foreground an background tables consists of N entries
76 # where each entry has an L-digit key. (Actually, some keys can be longer
77 # than L characters, but they always start with L digits.) The keys
78 # cover all integers between 1 and N. Whenever an entry is added to
79 # the foreground it is removed form the background and vice versa.
81 # 3. Some entries in the foreground and background tables have keys that
82 # begin with an L-digit number but are followed by additional characters.
83 # For each such entry there is a corresponding entry in the long key
84 # table. The long key table entry has a key which is just the L-digit
85 # number and data which is the length of the key in the foreground and
88 # 4. The data for both foreground and background entries is usually a
89 # short string. But some entries have long data strings. For each
90 # such entries there is an entry in the long data type. The key to
91 # long data table is an L-digit number. (The extension on long keys
92 # is omitted.) The data is the number of charaters in the data of the
93 # foreground or background entry.
95 # The following function builds a database that satisfies all of the above
99 for {set i 2} {$i<=6} {incr i} {
100 catch {btree_close_cursor [set ::c$i]}
101 btree_clear_table $::b $i
102 set ::c$i [btree_cursor $::b $i 1]
104 btree_insert $::c2 N $N
105 btree_insert $::c2 L $L
107 for {set i 1} {$i<=$N} {incr i} {
108 set key [format $format $i]
110 btree_insert $::c3 $key $data
114 # Given a base key number and a length, construct the full text of the key
117 proc make_payload {keynum L len} {
118 set key [format %0${L}d $keynum]
121 while {[string length $r]<$len} {
122 append r " ($i) $key"
125 return [string range $r 0 [expr {$len-1}]]
128 # Verify the invariants on the database. Return an empty string on
129 # success or an error message if something is amiss.
131 proc check_invariants {} {
132 set ck [btree_integrity_check $::b 1 2 3 4 5 6]
134 puts "\n*** SANITY:\n$ck"
138 btree_move_to $::c3 {}
139 btree_move_to $::c4 {}
140 btree_move_to $::c2 N
141 set N [btree_data $::c2]
142 btree_move_to $::c2 L
143 set L [btree_data $::c2]
144 set LM1 [expr {$L-1}]
145 for {set i 1} {$i<=$N} {incr i} {
147 if {![btree_eof $::c3]} {
148 set key [btree_key $::c3]
150 if {[scan $key %d k]<1} {set k 0}
153 if {![btree_eof $::c4]} {
154 set key [btree_key $::c4]
156 if {[scan $key %d k]<1} {set k 0}
158 return "Key $i is missing from both foreground and background"
160 set data [btree_data $::c4]
163 set data [btree_data $::c3]
166 set skey [string range $key 0 $LM1]
167 if {[btree_move_to $::c5 $skey]==0} {
168 set keylen [btree_data $::c5]
172 if {[string length $key]!=$keylen} {
173 return "Key $i is the wrong size.\
174 Is \"$key\" but should be \"[make_payload $k $L $keylen]\""
176 if {[make_payload $k $L $keylen]!=$key} {
177 return "Key $i has an invalid extension"
179 if {[btree_move_to $::c6 $skey]==0} {
180 set datalen [btree_data $::c6]
184 if {[string length $data]!=$datalen} {
185 return "Data for $i is the wrong size.\
186 Is [string length $data] but should be $datalen"
188 if {[make_payload $k $L $datalen]!=$data} {
189 return "Entry $i has an incorrect data"
194 # Look at all elements in both the foreground and background tables.
195 # Make sure the key is always the same as the prefix of the data.
197 # This routine was used for hunting bugs. It is not a part of standard
200 proc check_data {n key} {
203 foreach c [list $c3 $c4] {
204 btree_first $c ;# move_to $c $key
206 while {![btree_eof $c]} {
207 set key [btree_key $c]
208 set data [btree_data $c]
209 if {[string range $key 0 $n] ne [string range $data 0 $n]} {
210 puts "key=[list $key] data=[list $data] n=$n"
211 puts "cursor info = [btree_cursor_info $c]"
212 btree_page_dump $::b [lindex [btree_cursor_info $c] 0]
220 # Make random changes to the database such that each change preserves
221 # the invariants. The number of changes is $n*N where N is the parameter
222 # from the descriptor table. Each changes begins with a random key.
223 # the entry with that key is put in the foreground table with probability
224 # $I and it is put in background with probability (1.0-$I). It gets
225 # a long key with probability $K and long data with probability $D.
228 proc random_changes {n I K D} {
230 btree_move_to $::c2 N
231 set N [btree_data $::c2]
232 btree_move_to $::c2 L
233 set L [btree_data $::c2]
234 set LM1 [expr {$L-1}]
235 set total [expr {int($N*$n)}]
237 for {set i 0} {$i<$total} {incr i} {
238 set k [expr {int(rand()*$N)+1}]
239 set insert [expr {rand()<=$I}]
240 set longkey [expr {rand()<=$K}]
241 set longdata [expr {rand()<=$D}]
243 set x [expr {rand()}]
244 set keylen [expr {int($x*$x*$x*$x*3000)+10}]
248 set key [make_payload $k $L $keylen]
250 set x [expr {rand()}]
251 set datalen [expr {int($x*$x*$x*$x*3000)+10}]
255 set data [make_payload $k $L $datalen]
256 set basekey [format $format $k]
257 if {[set c [btree_move_to $::c3 $basekey]]==0} {
260 if {$c<0} {btree_next $::c3}
261 if {![btree_eof $::c3]} {
262 if {[string match $basekey* [btree_key $::c3]]} {
267 if {[set c [btree_move_to $::c4 $basekey]]==0} {
270 if {$c<0} {btree_next $::c4}
271 if {![btree_eof $::c4]} {
272 if {[string match $basekey* [btree_key $::c4]]} {
278 if {![btree_eof $::c4]} {
279 if {[scan [btree_key $::c4] %d kx]<1} {set kx -1}
284 # For debugging - change the "0" to "1" to integrity check after
288 puts check----$chngcnt
289 set ck [btree_integrity_check $::b 1 2 3 4 5 6]
291 puts "\nSANITY CHECK FAILED!\n$ck"
296 btree_insert $::c3 $key $data
298 btree_insert $::c4 $key $data
301 btree_insert $::c5 $basekey $keylen
302 } elseif {[btree_move_to $::c5 $basekey]==0} {
306 btree_insert $::c6 $basekey $datalen
307 } elseif {[btree_move_to $::c6 $basekey]==0} {
310 # For debugging - change the "0" to "1" to integrity check after
314 puts check----$chngcnt
315 set ck [btree_integrity_check $::b 1 2 3 4 5 6]
317 puts "\nSANITY CHECK FAILED!\n$ck"
325 # Repeat this test sequence on database of various sizes
334 puts "**** N=$N L=$L ****"
335 set hash [md5file test2.bt]
336 do_test btree2-$testno.1 [subst -nocommands {
337 set ::c2 [btree_cursor $::b 2 1]
338 set ::c3 [btree_cursor $::b 3 1]
339 set ::c4 [btree_cursor $::b 4 1]
340 set ::c5 [btree_cursor $::b 5 1]
341 set ::c6 [btree_cursor $::b 6 1]
342 btree_begin_transaction $::b
346 do_test btree2-$testno.2 {
347 btree_close_cursor $::c2
348 btree_close_cursor $::c3
349 btree_close_cursor $::c4
350 btree_close_cursor $::c5
351 btree_close_cursor $::c6
355 do_test btree2-$testno.3 [subst -nocommands {
356 btree_begin_transaction $::b
357 set ::c2 [btree_cursor $::b 2 1]
358 set ::c3 [btree_cursor $::b 3 1]
359 set ::c4 [btree_cursor $::b 4 1]
360 set ::c5 [btree_cursor $::b 5 1]
361 set ::c6 [btree_cursor $::b 6 1]
365 do_test btree2-$testno.4 {
369 do_test btree2-$testno.5 {
370 lindex [btree_pager_stats $::b] 1
372 do_test btree2-$testno.6 {
373 btree_close_cursor $::c2
374 btree_close_cursor $::c3
375 btree_close_cursor $::c4
376 btree_close_cursor $::c5
377 btree_close_cursor $::c6
378 lindex [btree_pager_stats $::b] 1
380 do_test btree2-$testno.7 {
384 # For each database size, run various changes tests.
396 set testid btree2-$testno.8.$num2
397 set hash [md5file test2.bt]
399 set ::b [btree_open test2.bt 2000 0]
400 set ::c2 [btree_cursor $::b 2 1]
401 set ::c3 [btree_cursor $::b 3 1]
402 set ::c4 [btree_cursor $::b 4 1]
403 set ::c5 [btree_cursor $::b 5 1]
404 set ::c6 [btree_cursor $::b 6 1]
408 for {set i 2} {$i<=6} {incr i} {
409 if {[lindex [btree_cursor_info [set ::c$i]] 0]!=$i} {incr cnt}
412 btree_begin_transaction $::b
413 lindex [btree_pager_stats $::b] 1
415 do_test $testid.2 [subst {
416 random_changes $n $I $K $D
422 btree_close_cursor $::c2
423 btree_close_cursor $::c3
424 btree_close_cursor $::c4
425 btree_close_cursor $::c5
426 btree_close_cursor $::c6
430 btree_begin_transaction $::b
431 set ::c2 [btree_cursor $::b 2 1]
432 set ::c3 [btree_cursor $::b 3 1]
433 set ::c4 [btree_cursor $::b 4 1]
434 set ::c5 [btree_cursor $::b 5 1]
435 set ::c6 [btree_cursor $::b 6 1]
436 do_test $testid.5 [subst {
437 random_changes $n $I $K $D
446 set hash [md5file test2.bt]
448 btree_close_cursor $::c2
449 btree_close_cursor $::c3
450 btree_close_cursor $::c4
451 btree_close_cursor $::c5
452 btree_close_cursor $::c6
453 lindex [btree_pager_stats $::b] 1
457 set ::b [btree_open test2.bt 2000 0]
458 set ::c2 [btree_cursor $::b 2 1]
459 set ::c3 [btree_cursor $::b 3 1]
460 set ::c4 [btree_cursor $::b 4 1]
461 set ::c5 [btree_cursor $::b 5 1]
462 set ::c6 [btree_cursor $::b 6 1]
466 btree_close_cursor $::c2
467 btree_close_cursor $::c3
468 btree_close_cursor $::c4
469 btree_close_cursor $::c5
470 btree_close_cursor $::c6
471 lindex [btree_pager_stats $::b] 1
479 set ::b [btree_open test2.bt 2000 0]
482 # Testing is complete. Shut everything down.
484 do_test btree-999.1 {
485 lindex [btree_pager_stats $::b] 1
487 do_test btree-999.2 {
490 do_test btree-999.3 {
491 file delete -force test2.bt
492 file exists test2.bt-journal
495 } ;# end if( not mem: and has pager_open command );