1 2#pragma ident "%Z%%M% %I% %E% SMI" 3 4# 2001 September 15 5# 6# The author disclaims copyright to this source code. In place of 7# a legal notice, here is a blessing: 8# 9# May you do good and not evil. 10# May you find forgiveness for yourself and forgive others. 11# May you share freely, never taking more than you give. 12# 13#*********************************************************************** 14# This file implements regression tests for SQLite library. The 15# focus of this script is btree database backend 16# 17# $Id: btree.test,v 1.15 2004/02/10 01:54:28 drh Exp $ 18 19 20set testdir [file dirname $argv0] 21source $testdir/tester.tcl 22 23if {[info commands btree_open]!="" && $SQLITE_PAGE_SIZE==1024 24 && $SQLITE_USABLE_SIZE==1024} { 25 26# Basic functionality. Open and close a database. 27# 28do_test btree-1.1 { 29 file delete -force test1.bt 30 file delete -force test1.bt-journal 31 set rc [catch {btree_open test1.bt} ::b1] 32} {0} 33 34# The second element of the list returned by btree_pager_stats is the 35# number of pages currently checked out. We'll be checking this value 36# frequently during this test script, to make sure the btree library 37# is properly releasing the pages it checks out, and thus avoiding 38# page leaks. 39# 40do_test btree-1.1.1 { 41 lindex [btree_pager_stats $::b1] 1 42} {0} 43do_test btree-1.2 { 44 set rc [catch {btree_open test1.bt} ::b2] 45} {0} 46do_test btree-1.3 { 47 set rc [catch {btree_close $::b2} msg] 48 lappend rc $msg 49} {0 {}} 50 51# Do an insert and verify that the database file grows in size. 52# 53do_test btree-1.4 { 54 set rc [catch {btree_begin_transaction $::b1} msg] 55 lappend rc $msg 56} {0 {}} 57do_test btree-1.4.1 { 58 lindex [btree_pager_stats $::b1] 1 59} {1} 60do_test btree-1.5 { 61 set rc [catch {btree_cursor $::b1 2 1} ::c1] 62 if {$rc} {lappend rc $::c1} 63 set rc 64} {0} 65do_test btree-1.6 { 66 set rc [catch {btree_insert $::c1 one 1.00} msg] 67 lappend rc $msg 68} {0 {}} 69do_test btree-1.7 { 70 btree_key $::c1 71} {one} 72do_test btree-1.8 { 73 btree_data $::c1 74} {1.00} 75do_test btree-1.9 { 76 set rc [catch {btree_close_cursor $::c1} msg] 77 lappend rc $msg 78} {0 {}} 79do_test btree-1.10 { 80 set rc [catch {btree_commit $::b1} msg] 81 lappend rc $msg 82} {0 {}} 83do_test btree-1.11 { 84 file size test1.bt 85} {2048} 86do_test btree-1.12 { 87 lindex [btree_pager_stats $::b1] 1 88} {0} 89 90# Reopen the database and attempt to read the record that we wrote. 91# 92do_test btree-2.1 { 93 set rc [catch {btree_cursor $::b1 2 1} ::c1] 94 if {$rc} {lappend rc $::c1} 95 set rc 96} {0} 97do_test btree-2.2 { 98 btree_move_to $::c1 abc 99} {1} 100do_test btree-2.3 { 101 btree_move_to $::c1 xyz 102} {-1} 103do_test btree-2.4 { 104 btree_move_to $::c1 one 105} {0} 106do_test btree-2.5 { 107 btree_key $::c1 108} {one} 109do_test btree-2.6 { 110 btree_data $::c1 111} {1.00} 112do_test btree-2.7 { 113 lindex [btree_pager_stats $::b1] 1 114} {2} 115 116# Do some additional inserts 117# 118do_test btree-3.1 { 119 btree_begin_transaction $::b1 120 btree_insert $::c1 two 2.00 121 btree_key $::c1 122} {two} 123do_test btree-3.1.1 { 124 lindex [btree_pager_stats $::b1] 1 125} {2} 126do_test btree-3.2 { 127 btree_insert $::c1 three 3.00 128 btree_key $::c1 129} {three} 130do_test btree-3.4 { 131 btree_insert $::c1 four 4.00 132 btree_key $::c1 133} {four} 134do_test btree-3.5 { 135 btree_insert $::c1 five 5.00 136 btree_key $::c1 137} {five} 138do_test btree-3.6 { 139 btree_insert $::c1 six 6.00 140 btree_key $::c1 141} {six} 142#btree_page_dump $::b1 2 143do_test btree-3.7 { 144 set rc [btree_move_to $::c1 {}] 145 expr {$rc>0} 146} {1} 147do_test btree-3.8 { 148 btree_key $::c1 149} {five} 150do_test btree-3.9 { 151 btree_data $::c1 152} {5.00} 153do_test btree-3.10 { 154 btree_next $::c1 155 btree_key $::c1 156} {four} 157do_test btree-3.11 { 158 btree_data $::c1 159} {4.00} 160do_test btree-3.12 { 161 btree_next $::c1 162 btree_key $::c1 163} {one} 164do_test btree-3.13 { 165 btree_data $::c1 166} {1.00} 167do_test btree-3.14 { 168 btree_next $::c1 169 btree_key $::c1 170} {six} 171do_test btree-3.15 { 172 btree_data $::c1 173} {6.00} 174do_test btree-3.16 { 175 btree_next $::c1 176 btree_key $::c1 177} {three} 178do_test btree-3.17 { 179 btree_data $::c1 180} {3.00} 181do_test btree-3.18 { 182 btree_next $::c1 183 btree_key $::c1 184} {two} 185do_test btree-3.19 { 186 btree_data $::c1 187} {2.00} 188do_test btree-3.20 { 189 btree_next $::c1 190 btree_key $::c1 191} {} 192do_test btree-3.21 { 193 btree_data $::c1 194} {} 195 196# Commit the changes, reopen and reread the data 197# 198do_test btree-3.22 { 199 set rc [catch {btree_close_cursor $::c1} msg] 200 lappend rc $msg 201} {0 {}} 202do_test btree-3.22.1 { 203 lindex [btree_pager_stats $::b1] 1 204} {1} 205do_test btree-3.23 { 206 set rc [catch {btree_commit $::b1} msg] 207 lappend rc $msg 208} {0 {}} 209do_test btree-3.23.1 { 210 lindex [btree_pager_stats $::b1] 1 211} {0} 212do_test btree-3.24 { 213 file size test1.bt 214} {2048} 215do_test btree-3.25 { 216 set rc [catch {btree_cursor $::b1 2 1} ::c1] 217 if {$rc} {lappend rc $::c1} 218 set rc 219} {0} 220do_test btree-3.25.1 { 221 lindex [btree_pager_stats $::b1] 1 222} {2} 223do_test btree-3.26 { 224 set rc [btree_move_to $::c1 {}] 225 expr {$rc>0} 226} {1} 227do_test btree-3.27 { 228 btree_key $::c1 229} {five} 230do_test btree-3.28 { 231 btree_data $::c1 232} {5.00} 233do_test btree-3.29 { 234 btree_next $::c1 235 btree_key $::c1 236} {four} 237do_test btree-3.30 { 238 btree_data $::c1 239} {4.00} 240do_test btree-3.31 { 241 btree_next $::c1 242 btree_key $::c1 243} {one} 244do_test btree-3.32 { 245 btree_data $::c1 246} {1.00} 247do_test btree-3.33 { 248 btree_next $::c1 249 btree_key $::c1 250} {six} 251do_test btree-3.34 { 252 btree_data $::c1 253} {6.00} 254do_test btree-3.35 { 255 btree_next $::c1 256 btree_key $::c1 257} {three} 258do_test btree-3.36 { 259 btree_data $::c1 260} {3.00} 261do_test btree-3.37 { 262 btree_next $::c1 263 btree_key $::c1 264} {two} 265do_test btree-3.38 { 266 btree_data $::c1 267} {2.00} 268do_test btree-3.39 { 269 btree_next $::c1 270 btree_key $::c1 271} {} 272do_test btree-3.40 { 273 btree_data $::c1 274} {} 275do_test btree-3.41 { 276 lindex [btree_pager_stats $::b1] 1 277} {2} 278 279 280# Now try a delete 281# 282do_test btree-4.1 { 283 btree_begin_transaction $::b1 284 btree_move_to $::c1 one 285 btree_key $::c1 286} {one} 287do_test btree-4.1.1 { 288 lindex [btree_pager_stats $::b1] 1 289} {2} 290do_test btree-4.2 { 291 btree_delete $::c1 292} {} 293do_test btree-4.3 { 294 btree_key $::c1 295} {six} 296do_test btree-4.4 { 297 btree_next $::c1 298 btree_key $::c1 299} {six} 300do_test btree-4.5 { 301 btree_next $::c1 302 btree_key $::c1 303} {three} 304do_test btree-4.4 { 305 btree_move_to $::c1 {} 306 set r {} 307 while 1 { 308 set key [btree_key $::c1] 309 if {$key==""} break 310 lappend r $key 311 lappend r [btree_data $::c1] 312 btree_next $::c1 313 } 314 set r 315} {five 5.00 four 4.00 six 6.00 three 3.00 two 2.00} 316 317# Commit and make sure the delete is still there. 318# 319do_test btree-4.5 { 320 btree_commit $::b1 321 btree_move_to $::c1 {} 322 set r {} 323 while 1 { 324 set key [btree_key $::c1] 325 if {$key==""} break 326 lappend r $key 327 lappend r [btree_data $::c1] 328 btree_next $::c1 329 } 330 set r 331} {five 5.00 four 4.00 six 6.00 three 3.00 two 2.00} 332 333# Completely close the database and reopen it. Then check 334# the data again. 335# 336do_test btree-4.6 { 337 lindex [btree_pager_stats $::b1] 1 338} {2} 339do_test btree-4.7 { 340 btree_close_cursor $::c1 341 lindex [btree_pager_stats $::b1] 1 342} {0} 343do_test btree-4.8 { 344 btree_close $::b1 345 set ::b1 [btree_open test1.bt] 346 set ::c1 [btree_cursor $::b1 2 1] 347 lindex [btree_pager_stats $::b1] 1 348} {2} 349do_test btree-4.9 { 350 set r {} 351 btree_first $::c1 352 while 1 { 353 set key [btree_key $::c1] 354 if {$key==""} break 355 lappend r $key 356 lappend r [btree_data $::c1] 357 btree_next $::c1 358 } 359 set r 360} {five 5.00 four 4.00 six 6.00 three 3.00 two 2.00} 361 362# Try to read and write meta data 363# 364do_test btree-5.1 { 365 btree_get_meta $::b1 366} {0 0 0 0 0 0 0 0 0 0} 367do_test btree-5.2 { 368 set rc [catch {btree_update_meta $::b1 1 2 3 4 5 6 7 8 9 10} msg] 369 lappend rc $msg 370} {1 SQLITE_ERROR} 371do_test btree-5.3 { 372 btree_begin_transaction $::b1 373 set rc [catch {btree_update_meta $::b1 1 2 3 4 5 6 7 8 9 10} msg] 374 lappend rc $msg 375} {0 {}} 376do_test btree-5.4 { 377 btree_get_meta $::b1 378} {0 2 3 4 5 6 7 8 9 10} 379do_test btree-5.5 { 380 btree_close_cursor $::c1 381 btree_rollback $::b1 382 btree_get_meta $::b1 383} {0 0 0 0 0 0 0 0 0 0} 384do_test btree-5.6 { 385 btree_begin_transaction $::b1 386 btree_update_meta $::b1 999 10 20 30 40 50 60 70 80 90 387 btree_commit $::b1 388 btree_get_meta $::b1 389} {0 10 20 30 40 50 60 70 80 90} 390 391proc select_all {cursor} { 392 set r {} 393 btree_move_to $cursor {} 394 while 1 { 395 set key [btree_key $cursor] 396 if {$key==""} break 397 lappend r $key 398 lappend r [btree_data $cursor] 399 btree_next $cursor 400 } 401 return $r 402} 403proc select_keys {cursor} { 404 set r {} 405 btree_move_to $cursor {} 406 while 1 { 407 set key [btree_key $cursor] 408 if {$key==""} break 409 lappend r $key 410 btree_next $cursor 411 } 412 return $r 413} 414 415# Try to create a new table in the database file 416# 417do_test btree-6.1 { 418 set rc [catch {btree_create_table $::b1} msg] 419 lappend rc $msg 420} {1 SQLITE_ERROR} 421do_test btree-6.2 { 422 btree_begin_transaction $::b1 423 set ::t2 [btree_create_table $::b1] 424} {3} 425do_test btree-6.2.1 { 426 lindex [btree_pager_stats $::b1] 1 427} {1} 428do_test btree-6.2.2 { 429 set ::c2 [btree_cursor $::b1 $::t2 1] 430 lindex [btree_pager_stats $::b1] 1 431} {2} 432do_test btree-6.2.3 { 433 btree_insert $::c2 ten 10 434 btree_key $::c2 435} {ten} 436do_test btree-6.3 { 437 btree_commit $::b1 438 set ::c1 [btree_cursor $::b1 2 1] 439 lindex [btree_pager_stats $::b1] 1 440} {3} 441do_test btree-6.3.1 { 442 select_all $::c1 443} {five 5.00 four 4.00 six 6.00 three 3.00 two 2.00} 444#btree_page_dump $::b1 3 445do_test btree-6.4 { 446 select_all $::c2 447} {ten 10} 448 449# Drop the new table, then create it again anew. 450# 451do_test btree-6.5 { 452 btree_begin_transaction $::b1 453} {} 454do_test btree-6.6 { 455 btree_close_cursor $::c2 456} {} 457do_test btree-6.6.1 { 458 lindex [btree_pager_stats $::b1] 1 459} {2} 460do_test btree-6.7 { 461 btree_drop_table $::b1 $::t2 462} {} 463do_test btree-6.7.1 { 464 lindex [btree_get_meta $::b1] 0 465} {1} 466do_test btree-6.8 { 467 set ::t2 [btree_create_table $::b1] 468} {3} 469do_test btree-6.8.1 { 470 lindex [btree_get_meta $::b1] 0 471} {0} 472do_test btree-6.9 { 473 set ::c2 [btree_cursor $::b1 $::t2 1] 474 lindex [btree_pager_stats $::b1] 1 475} {3} 476 477do_test btree-6.9.1 { 478 btree_move_to $::c2 {} 479 btree_key $::c2 480} {} 481 482# If we drop table 2 it just clears the table. Table 2 always exists. 483# 484do_test btree-6.10 { 485 btree_close_cursor $::c1 486 btree_drop_table $::b1 2 487 set ::c1 [btree_cursor $::b1 2 1] 488 btree_move_to $::c1 {} 489 btree_key $::c1 490} {} 491do_test btree-6.11 { 492 btree_commit $::b1 493 select_all $::c1 494} {} 495do_test btree-6.12 { 496 select_all $::c2 497} {} 498do_test btree-6.13 { 499 btree_close_cursor $::c2 500 lindex [btree_pager_stats $::b1] 1 501} {2} 502 503# Check to see that pages defragment properly. To do this test we will 504# 505# 1. Fill the first page table 2 with data. 506# 2. Delete every other entry of table 2. 507# 3. Insert a single entry that requires more contiguous 508# space than is available. 509# 510do_test btree-7.1 { 511 btree_begin_transaction $::b1 512} {} 513catch {unset key} 514catch {unset data} 515do_test btree-7.2 { 516 for {set i 0} {$i<36} {incr i} { 517 set key [format %03d $i] 518 set data "*** $key ***" 519 btree_insert $::c1 $key $data 520 } 521 lrange [btree_cursor_dump $::c1] 4 5 522} {8 1} 523do_test btree-7.3 { 524 btree_move_to $::c1 000 525 while {[btree_key $::c1]!=""} { 526 btree_delete $::c1 527 btree_next $::c1 528 btree_next $::c1 529 } 530 lrange [btree_cursor_dump $::c1] 4 5 531} {512 19} 532#btree_page_dump $::b1 2 533do_test btree-7.4 { 534 btree_insert $::c1 018 {*** 018 ***+++} 535 btree_key $::c1 536} {018} 537do_test btree-7.5 { 538 lrange [btree_cursor_dump $::c1] 4 5 539} {480 1} 540#btree_page_dump $::b1 2 541 542# Delete an entry to make a hole of a known size, then immediately recreate 543# that entry. This tests the path into allocateSpace where the hole exactly 544# matches the size of the desired space. 545# 546do_test btree-7.6 { 547 btree_move_to $::c1 007 548 btree_delete $::c1 549 btree_move_to $::c1 011 550 btree_delete $::c1 551} {} 552do_test btree-7.7 { 553 lindex [btree_cursor_dump $::c1] 5 554} {3} 555#btree_page_dump $::b1 2 556do_test btree-7.8 { 557 btree_insert $::c1 007 {*** 007 ***} 558 lindex [btree_cursor_dump $::c1] 5 559} {2} 560#btree_page_dump $::b1 2 561 562# Make sure the freeSpace() routine properly coaleses adjacent memory blocks 563# 564do_test btree-7.9 { 565 btree_move_to $::c1 013 566 btree_delete $::c1 567 lrange [btree_cursor_dump $::c1] 4 5 568} {536 2} 569do_test btree-7.10 { 570 btree_move_to $::c1 009 571 btree_delete $::c1 572 lrange [btree_cursor_dump $::c1] 4 5 573} {564 2} 574do_test btree-7.11 { 575 btree_move_to $::c1 018 576 btree_delete $::c1 577 lrange [btree_cursor_dump $::c1] 4 5 578} {596 2} 579do_test btree-7.13 { 580 btree_move_to $::c1 033 581 btree_delete $::c1 582 lrange [btree_cursor_dump $::c1] 4 5 583} {624 3} 584do_test btree-7.14 { 585 btree_move_to $::c1 035 586 btree_delete $::c1 587 lrange [btree_cursor_dump $::c1] 4 5 588} {652 2} 589#btree_page_dump $::b1 2 590do_test btree-7.15 { 591 lindex [btree_pager_stats $::b1] 1 592} {2} 593 594# Check to see that data on overflow pages work correctly. 595# 596do_test btree-8.1 { 597 set data "*** This is a very long key " 598 while {[string length $data]<256} {append data $data} 599 set ::data $data 600 btree_insert $::c1 020 $data 601} {} 602#btree_page_dump $::b1 2 603do_test btree-8.1.1 { 604 lindex [btree_pager_stats $::b1] 1 605} {2} 606#btree_pager_ref_dump $::b1 607do_test btree-8.2 { 608 string length [btree_data $::c1] 609} [string length $::data] 610do_test btree-8.3 { 611 btree_data $::c1 612} $::data 613do_test btree-8.4 { 614 btree_delete $::c1 615} {} 616do_test btree-8.4.1 { 617 lindex [btree_get_meta $::b1] 0 618} [expr {int(([string length $::data]-238+1019)/1020)}] 619do_test btree-8.5 { 620 set data "*** This is an even longer key" 621 while {[string length $data]<2000} {append data $data} 622 set ::data $data 623 btree_insert $::c1 020 $data 624} {} 625do_test btree-8.6 { 626 string length [btree_data $::c1] 627} [string length $::data] 628do_test btree-8.7 { 629 btree_data $::c1 630} $::data 631do_test btree-8.8 { 632 btree_commit $::b1 633 btree_data $::c1 634} $::data 635do_test btree-8.9 { 636 btree_close_cursor $::c1 637 btree_close $::b1 638 set ::b1 [btree_open test1.bt] 639 set ::c1 [btree_cursor $::b1 2 1] 640 btree_move_to $::c1 020 641 btree_data $::c1 642} $::data 643do_test btree-8.10 { 644 btree_begin_transaction $::b1 645 btree_delete $::c1 646} {} 647do_test btree-8.11 { 648 lindex [btree_get_meta $::b1] 0 649} [expr {int(([string length $::data]-238+1019)/1020)}] 650 651# Now check out keys on overflow pages. 652# 653do_test btree-8.12 { 654 set ::keyprefix "This is a long prefix to a key " 655 while {[string length $::keyprefix]<256} {append ::keyprefix $::keyprefix} 656 btree_close_cursor $::c1 657 btree_drop_table $::b1 2 658 lindex [btree_get_meta $::b1] 0 659} {4} 660do_test btree-8.12.1 { 661 set ::c1 [btree_cursor $::b1 2 1] 662 btree_insert $::c1 ${::keyprefix}1 1 663 btree_data $::c1 664} {1} 665do_test btree-8.13 { 666 btree_key $::c1 667} ${keyprefix}1 668do_test btree-8.14 { 669 btree_insert $::c1 ${::keyprefix}2 2 670 btree_insert $::c1 ${::keyprefix}3 3 671 btree_key $::c1 672} ${keyprefix}3 673do_test btree-8.15 { 674 btree_move_to $::c1 ${::keyprefix}2 675 btree_data $::c1 676} {2} 677do_test btree-8.16 { 678 btree_move_to $::c1 ${::keyprefix}1 679 btree_data $::c1 680} {1} 681do_test btree-8.17 { 682 btree_move_to $::c1 ${::keyprefix}3 683 btree_data $::c1 684} {3} 685do_test btree-8.18 { 686 lindex [btree_get_meta $::b1] 0 687} {1} 688do_test btree-8.19 { 689 btree_move_to $::c1 ${::keyprefix}2 690 btree_key $::c1 691} ${::keyprefix}2 692#btree_page_dump $::b1 2 693do_test btree-8.20 { 694 btree_delete $::c1 695 btree_next $::c1 696 btree_key $::c1 697} ${::keyprefix}3 698#btree_page_dump $::b1 2 699do_test btree-8.21 { 700 lindex [btree_get_meta $::b1] 0 701} {2} 702do_test btree-8.22 { 703 lindex [btree_pager_stats $::b1] 1 704} {2} 705do_test btree-8.23 { 706 btree_close_cursor $::c1 707 btree_drop_table $::b1 2 708 set ::c1 [btree_cursor $::b1 2 1] 709 lindex [btree_get_meta $::b1] 0 710} {4} 711do_test btree-8.24 { 712 lindex [btree_pager_stats $::b1] 1 713} {2} 714#btree_pager_ref_dump $::b1 715 716# Check page splitting logic 717# 718do_test btree-9.1 { 719 for {set i 1} {$i<=19} {incr i} { 720 set key [format %03d $i] 721 set data "*** $key *** $key *** $key *** $key ***" 722 btree_insert $::c1 $key $data 723 } 724} {} 725#btree_tree_dump $::b1 2 726#btree_pager_ref_dump $::b1 727#set pager_refinfo_enable 1 728do_test btree-9.2 { 729 btree_insert $::c1 020 {*** 020 *** 020 *** 020 *** 020 ***} 730 select_keys $::c1 731} {001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020} 732#btree_page_dump $::b1 5 733#btree_page_dump $::b1 2 734#btree_page_dump $::b1 7 735#btree_pager_ref_dump $::b1 736#set pager_refinfo_enable 0 737 738# The previous "select_keys" command left the cursor pointing at the root 739# page. So there should only be two pages checked out. 2 (the root) and 740# page 1. 741do_test btree-9.2.1 { 742 lindex [btree_pager_stats $::b1] 1 743} {2} 744for {set i 1} {$i<=20} {incr i} { 745 do_test btree-9.3.$i.1 [subst { 746 btree_move_to $::c1 [format %03d $i] 747 btree_key $::c1 748 }] [format %03d $i] 749 do_test btree-9.3.$i.2 [subst { 750 btree_move_to $::c1 [format %03d $i] 751 string range \[btree_data $::c1\] 0 10 752 }] "*** [format %03d $i] ***" 753} 754do_test btree-9.4.1 { 755 lindex [btree_pager_stats $::b1] 1 756} {3} 757 758# Check the page joining logic. 759# 760#btree_page_dump $::b1 2 761#btree_pager_ref_dump $::b1 762do_test btree-9.4.2 { 763 btree_move_to $::c1 005 764 btree_delete $::c1 765} {} 766#btree_page_dump $::b1 2 767for {set i 1} {$i<=19} {incr i} { 768 if {$i==5} continue 769 do_test btree-9.5.$i.1 [subst { 770 btree_move_to $::c1 [format %03d $i] 771 btree_key $::c1 772 }] [format %03d $i] 773 do_test btree-9.5.$i.2 [subst { 774 btree_move_to $::c1 [format %03d $i] 775 string range \[btree_data $::c1\] 0 10 776 }] "*** [format %03d $i] ***" 777} 778#btree_pager_ref_dump $::b1 779do_test btree-9.6 { 780 btree_close_cursor $::c1 781 lindex [btree_pager_stats $::b1] 1 782} {1} 783do_test btree-9.7 { 784 btree_rollback $::b1 785 lindex [btree_pager_stats $::b1] 1 786} {0} 787 788# Create a tree of depth two. That is, there is a single divider entry 789# on the root pages and two leaf pages. Then delete the divider entry 790# see what happens. 791# 792do_test btree-10.1 { 793 btree_begin_transaction $::b1 794 btree_drop_table $::b1 2 795 lindex [btree_pager_stats $::b1] 1 796} {1} 797do_test btree-10.2 { 798 set ::c1 [btree_cursor $::b1 2 1] 799 lindex [btree_pager_stats $::b1] 1 800} {2} 801do_test btree-10.3 { 802 for {set i 1} {$i<=20} {incr i} { 803 set key [format %03d $i] 804 set data "*** $key *** $key *** $key *** $key ***" 805 btree_insert $::c1 $key $data 806 } 807 select_keys $::c1 808} {001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020} 809#btree_page_dump $::b1 7 810#btree_page_dump $::b1 2 811#btree_page_dump $::b1 6 812do_test btree-10.4 { 813 btree_move_to $::c1 011 814 btree_delete $::c1 815 select_keys $::c1 816} {001 002 003 004 005 006 007 008 009 010 012 013 014 015 016 017 018 019 020} 817#btree_tree_dump $::b1 2 818#btree_pager_ref_dump $::b1 819for {set i 1} {$i<=20} {incr i} { 820 do_test btree-10.5.$i { 821 btree_move_to $::c1 [format %03d $i] 822 lindex [btree_pager_stats $::b1] 1 823 } {2} 824 #btree_pager_ref_dump $::b1 825 #btree_tree_dump $::b1 2 826} 827 828# Create a tree with lots more pages 829# 830catch {unset ::data} 831catch {unset ::key} 832for {set i 21} {$i<=1000} {incr i} { 833 do_test btree-11.1.$i.1 { 834 set key [format %03d $i] 835 set ::data "*** $key *** $key *** $key *** $key ***" 836 btree_insert $::c1 $key $data 837 btree_key $::c1 838 } [format %03d $i] 839 do_test btree-11.1.$i.2 { 840 btree_data $::c1 841 } $::data 842 set ::key [format %03d [expr {$i/2}]] 843 if {$::key=="011"} {set ::key 010} 844 do_test btree-11.1.$i.3 { 845 btree_move_to $::c1 $::key 846 btree_key $::c1 847 } $::key 848} 849catch {unset ::data} 850catch {unset ::key} 851 852# Make sure our reference count is still correct. 853# 854do_test btree-11.2 { 855 btree_close_cursor $::c1 856 lindex [btree_pager_stats $::b1] 1 857} {1} 858do_test btree-11.3 { 859 set ::c1 [btree_cursor $::b1 2 1] 860 lindex [btree_pager_stats $::b1] 1 861} {2} 862#btree_page_dump $::b1 2 863 864# Delete the dividers on the root page 865# 866do_test btree-11.4 { 867 btree_move_to $::c1 257 868 btree_delete $::c1 869 btree_next $::c1 870 btree_key $::c1 871} {258} 872do_test btree-11.4.1 { 873 btree_move_to $::c1 256 874 btree_key $::c1 875} {256} 876do_test btree-11.4.2 { 877 btree_move_to $::c1 258 878 btree_key $::c1 879} {258} 880do_test btree-11.4.3 { 881 btree_move_to $::c1 259 882 btree_key $::c1 883} {259} 884do_test btree-11.4.4 { 885 btree_move_to $::c1 257 886 set n [btree_key $::c1] 887 expr {$n==256||$n==258} 888} {1} 889do_test btree-11.5 { 890 btree_move_to $::c1 513 891 btree_delete $::c1 892 btree_next $::c1 893 btree_key $::c1 894} {514} 895do_test btree-11.5.1 { 896 btree_move_to $::c1 512 897 btree_key $::c1 898} {512} 899do_test btree-11.5.2 { 900 btree_move_to $::c1 514 901 btree_key $::c1 902} {514} 903do_test btree-11.5.3 { 904 btree_move_to $::c1 515 905 btree_key $::c1 906} {515} 907do_test btree-11.5.4 { 908 btree_move_to $::c1 513 909 set n [btree_key $::c1] 910 expr {$n==512||$n==514} 911} {1} 912do_test btree-11.6 { 913 btree_move_to $::c1 769 914 btree_delete $::c1 915 btree_next $::c1 916 btree_key $::c1 917} {770} 918do_test btree-11.6.1 { 919 btree_move_to $::c1 768 920 btree_key $::c1 921} {768} 922do_test btree-11.6.2 { 923 btree_move_to $::c1 771 924 btree_key $::c1 925} {771} 926do_test btree-11.6.3 { 927 btree_move_to $::c1 770 928 btree_key $::c1 929} {770} 930do_test btree-11.6.4 { 931 btree_move_to $::c1 769 932 set n [btree_key $::c1] 933 expr {$n==768||$n==770} 934} {1} 935#btree_page_dump $::b1 2 936#btree_page_dump $::b1 25 937 938# Change the data on an intermediate node such that the node becomes overfull 939# and has to split. We happen to know that intermediate nodes exist on 940# 337, 401 and 465 by the btree_page_dumps above 941# 942catch {unset ::data} 943set ::data {This is going to be a very long data segment} 944append ::data $::data 945append ::data $::data 946do_test btree-12.1 { 947 btree_insert $::c1 337 $::data 948 btree_data $::c1 949} $::data 950do_test btree-12.2 { 951 btree_insert $::c1 401 $::data 952 btree_data $::c1 953} $::data 954do_test btree-12.3 { 955 btree_insert $::c1 465 $::data 956 btree_data $::c1 957} $::data 958do_test btree-12.4 { 959 btree_move_to $::c1 337 960 btree_key $::c1 961} {337} 962do_test btree-12.5 { 963 btree_data $::c1 964} $::data 965do_test btree-12.6 { 966 btree_next $::c1 967 btree_key $::c1 968} {338} 969do_test btree-12.7 { 970 btree_move_to $::c1 464 971 btree_key $::c1 972} {464} 973do_test btree-12.8 { 974 btree_next $::c1 975 btree_data $::c1 976} $::data 977do_test btree-12.9 { 978 btree_next $::c1 979 btree_key $::c1 980} {466} 981do_test btree-12.10 { 982 btree_move_to $::c1 400 983 btree_key $::c1 984} {400} 985do_test btree-12.11 { 986 btree_next $::c1 987 btree_data $::c1 988} $::data 989do_test btree-12.12 { 990 btree_next $::c1 991 btree_key $::c1 992} {402} 993do_test btree-13.1 { 994 btree_integrity_check $::b1 2 3 995} {} 996 997# To Do: 998# 999# 1. Do some deletes from the 3-layer tree 1000# 2. Commit and reopen the database 1001# 3. Read every 15th entry and make sure it works 1002# 4. Implement btree_sanity and put it throughout this script 1003# 1004 1005do_test btree-15.98 { 1006 btree_close_cursor $::c1 1007 lindex [btree_pager_stats $::b1] 1 1008} {1} 1009do_test btree-15.99 { 1010 btree_rollback $::b1 1011 lindex [btree_pager_stats $::b1] 1 1012} {0} 1013btree_pager_ref_dump $::b1 1014 1015do_test btree-99.1 { 1016 btree_close $::b1 1017} {} 1018catch {unset data} 1019catch {unset key} 1020 1021} ;# end if( not mem: and has pager_open command ); 1022 1023finish_test 1024