usr/src/lib/libsqlite/test/btree.test

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