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

   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
  20 set testdir [file dirname $argv0]
  21 source $testdir/tester.tcl
  22
  23 if {[info commands btree_open]!="" && $SQLITE_PAGE_SIZE==1024
  24      && $SQLITE_USABLE_SIZE==1024} {
  25
  26 # Basic functionality.  Open and close a database.
  27 #
  28 do_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 #
  40 do_test btree-1.1.1 {
  41   lindex [btree_pager_stats $::b1] 1
  42 } {0}
  43 do_test btree-1.2 {
  44   set rc [catch {btree_open test1.bt} ::b2]
  45 } {0}
  46 do_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 #
  53 do_test btree-1.4 {
  54   set rc [catch {btree_begin_transaction $::b1} msg]
  55   lappend rc $msg
  56 } {0 {}}
  57 do_test btree-1.4.1 {
  58   lindex [btree_pager_stats $::b1] 1
  59 } {1}
  60 do_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}
  65 do_test btree-1.6 {
  66   set rc [catch {btree_insert $::c1 one 1.00} msg]
  67   lappend rc $msg
  68 } {0 {}}
  69 do_test btree-1.7 {
  70   btree_key $::c1
  71 } {one}
  72 do_test btree-1.8 {
  73   btree_data $::c1
  74 } {1.00}
  75 do_test btree-1.9 {
  76   set rc [catch {btree_close_cursor $::c1} msg]
  77   lappend rc $msg
  78 } {0 {}}
  79 do_test btree-1.10 {
  80   set rc [catch {btree_commit $::b1} msg]
  81   lappend rc $msg
  82 } {0 {}}
  83 do_test btree-1.11 {
  84   file size test1.bt
  85 } {2048}
  86 do_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 #
  92 do_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}
  97 do_test btree-2.2 {
  98   btree_move_to $::c1 abc
  99 } {1}
 100 do_test btree-2.3 {
 101   btree_move_to $::c1 xyz
 102 } {-1}
 103 do_test btree-2.4 {
 104   btree_move_to $::c1 one
 105 } {0}
 106 do_test btree-2.5 {
 107   btree_key $::c1
 108 } {one}
 109 do_test btree-2.6 {
 110   btree_data $::c1
 111 } {1.00}
 112 do_test btree-2.7 {
 113   lindex [btree_pager_stats $::b1] 1
 114 } {2}
 115
 116 # Do some additional inserts
 117 #
 118 do_test btree-3.1 {
 119   btree_begin_transaction $::b1
 120   btree_insert $::c1 two 2.00
 121   btree_key $::c1
 122 } {two}
 123 do_test btree-3.1.1 {
 124   lindex [btree_pager_stats $::b1] 1
 125 } {2}
 126 do_test btree-3.2 {
 127   btree_insert $::c1 three 3.00
 128   btree_key $::c1
 129 } {three}
 130 do_test btree-3.4 {
 131   btree_insert $::c1 four 4.00
 132   btree_key $::c1
 133 } {four}
 134 do_test btree-3.5 {
 135   btree_insert $::c1 five 5.00
 136   btree_key $::c1
 137 } {five}
 138 do_test btree-3.6 {
 139   btree_insert $::c1 six 6.00
 140   btree_key $::c1
 141 } {six}
 142 #btree_page_dump $::b1 2
 143 do_test btree-3.7 {
 144   set rc [btree_move_to $::c1 {}]
 145   expr {$rc>0}
 146 } {1}
 147 do_test btree-3.8 {
 148   btree_key $::c1
 149 } {five}
 150 do_test btree-3.9 {
 151   btree_data $::c1
 152 } {5.00}
 153 do_test btree-3.10 {
 154   btree_next $::c1
 155   btree_key $::c1
 156 } {four}
 157 do_test btree-3.11 {
 158   btree_data $::c1
 159 } {4.00}
 160 do_test btree-3.12 {
 161   btree_next $::c1
 162   btree_key $::c1
 163 } {one}
 164 do_test btree-3.13 {
 165   btree_data $::c1
 166 } {1.00}
 167 do_test btree-3.14 {
 168   btree_next $::c1
 169   btree_key $::c1
 170 } {six}
 171 do_test btree-3.15 {
 172   btree_data $::c1
 173 } {6.00}
 174 do_test btree-3.16 {
 175   btree_next $::c1
 176   btree_key $::c1
 177 } {three}
 178 do_test btree-3.17 {
 179   btree_data $::c1
 180 } {3.00}
 181 do_test btree-3.18 {
 182   btree_next $::c1
 183   btree_key $::c1
 184 } {two}
 185 do_test btree-3.19 {
 186   btree_data $::c1
 187 } {2.00}
 188 do_test btree-3.20 {
 189   btree_next $::c1
 190   btree_key $::c1
 191 } {}
 192 do_test btree-3.21 {
 193   btree_data $::c1
 194 } {}
 195
 196 # Commit the changes, reopen and reread the data
 197 #
 198 do_test btree-3.22 {
 199   set rc [catch {btree_close_cursor $::c1} msg]
 200   lappend rc $msg
 201 } {0 {}}
 202 do_test btree-3.22.1 {
 203   lindex [btree_pager_stats $::b1] 1
 204 } {1}
 205 do_test btree-3.23 {
 206   set rc [catch {btree_commit $::b1} msg]
 207   lappend rc $msg
 208 } {0 {}}
 209 do_test btree-3.23.1 {
 210   lindex [btree_pager_stats $::b1] 1
 211 } {0}
 212 do_test btree-3.24 {
 213   file size test1.bt
 214 } {2048}
 215 do_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}
 220 do_test btree-3.25.1 {
 221   lindex [btree_pager_stats $::b1] 1
 222 } {2}
 223 do_test btree-3.26 {
 224   set rc [btree_move_to $::c1 {}]
 225   expr {$rc>0}
 226 } {1}
 227 do_test btree-3.27 {
 228   btree_key $::c1
 229 } {five}
 230 do_test btree-3.28 {
 231   btree_data $::c1
 232 } {5.00}
 233 do_test btree-3.29 {
 234   btree_next $::c1
 235   btree_key $::c1
 236 } {four}
 237 do_test btree-3.30 {
 238   btree_data $::c1
 239 } {4.00}
 240 do_test btree-3.31 {
 241   btree_next $::c1
 242   btree_key $::c1
 243 } {one}
 244 do_test btree-3.32 {
 245   btree_data $::c1
 246 } {1.00}
 247 do_test btree-3.33 {
 248   btree_next $::c1
 249   btree_key $::c1
 250 } {six}
 251 do_test btree-3.34 {
 252   btree_data $::c1
 253 } {6.00}
 254 do_test btree-3.35 {
 255   btree_next $::c1
 256   btree_key $::c1
 257 } {three}
 258 do_test btree-3.36 {
 259   btree_data $::c1
 260 } {3.00}
 261 do_test btree-3.37 {
 262   btree_next $::c1
 263   btree_key $::c1
 264 } {two}
 265 do_test btree-3.38 {
 266   btree_data $::c1
 267 } {2.00}
 268 do_test btree-3.39 {
 269   btree_next $::c1
 270   btree_key $::c1
 271 } {}
 272 do_test btree-3.40 {
 273   btree_data $::c1
 274 } {}
 275 do_test btree-3.41 {
 276   lindex [btree_pager_stats $::b1] 1
 277 } {2}
 278
 279
 280 # Now try a delete
 281 #
 282 do_test btree-4.1 {
 283   btree_begin_transaction $::b1
 284   btree_move_to $::c1 one
 285   btree_key $::c1
 286 } {one}
 287 do_test btree-4.1.1 {
 288   lindex [btree_pager_stats $::b1] 1
 289 } {2}
 290 do_test btree-4.2 {
 291   btree_delete $::c1
 292 } {}
 293 do_test btree-4.3 {
 294   btree_key $::c1
 295 } {six}
 296 do_test btree-4.4 {
 297   btree_next $::c1
 298   btree_key $::c1
 299 } {six}
 300 do_test btree-4.5 {
 301   btree_next $::c1
 302   btree_key $::c1
 303 } {three}
 304 do_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 #
 319 do_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 #
 336 do_test btree-4.6 {
 337   lindex [btree_pager_stats $::b1] 1
 338 } {2}
 339 do_test btree-4.7 {
 340   btree_close_cursor $::c1
 341   lindex [btree_pager_stats $::b1] 1
 342 } {0}
 343 do_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}
 349 do_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 #
 364 do_test btree-5.1 {
 365   btree_get_meta $::b1
 366 } {0 0 0 0 0 0 0 0 0 0}
 367 do_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}
 371 do_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 {}}
 376 do_test btree-5.4 {
 377   btree_get_meta $::b1
 378 } {0 2 3 4 5 6 7 8 9 10}
 379 do_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}
 384 do_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
 391 proc 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 }
 403 proc 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 #
 417 do_test btree-6.1 {
 418   set rc [catch {btree_create_table $::b1} msg]
 419   lappend rc $msg
 420 } {1 SQLITE_ERROR}
 421 do_test btree-6.2 {
 422   btree_begin_transaction $::b1
 423   set ::t2 [btree_create_table $::b1]
 424 } {3}
 425 do_test btree-6.2.1 {
 426   lindex [btree_pager_stats $::b1] 1
 427 } {1}
 428 do_test btree-6.2.2 {
 429   set ::c2 [btree_cursor $::b1 $::t2 1]
 430   lindex [btree_pager_stats $::b1] 1
 431 } {2}
 432 do_test btree-6.2.3 {
 433   btree_insert $::c2 ten 10
 434   btree_key $::c2
 435 } {ten}
 436 do_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}
 441 do_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
 445 do_test btree-6.4 {
 446   select_all $::c2
 447 } {ten 10}
 448
 449 # Drop the new table, then create it again anew.
 450 #
 451 do_test btree-6.5 {
 452   btree_begin_transaction $::b1
 453 } {}
 454 do_test btree-6.6 {
 455   btree_close_cursor $::c2
 456 } {}
 457 do_test btree-6.6.1 {
 458   lindex [btree_pager_stats $::b1] 1
 459 } {2}
 460 do_test btree-6.7 {
 461   btree_drop_table $::b1 $::t2
 462 } {}
 463 do_test btree-6.7.1 {
 464   lindex [btree_get_meta $::b1] 0
 465 } {1}
 466 do_test btree-6.8 {
 467   set ::t2 [btree_create_table $::b1]
 468 } {3}
 469 do_test btree-6.8.1 {
 470   lindex [btree_get_meta $::b1] 0
 471 } {0}
 472 do_test btree-6.9 {
 473   set ::c2 [btree_cursor $::b1 $::t2 1]
 474   lindex [btree_pager_stats $::b1] 1
 475 } {3}
 476
 477 do_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 #
 484 do_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 } {}
 491 do_test btree-6.11 {
 492   btree_commit $::b1
 493   select_all $::c1
 494 } {}
 495 do_test btree-6.12 {
 496   select_all $::c2
 497 } {}
 498 do_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 #
 510 do_test btree-7.1 {
 511   btree_begin_transaction $::b1
 512 } {}
 513 catch {unset key}
 514 catch {unset data}
 515 do_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}
 523 do_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
 533 do_test btree-7.4 {
 534   btree_insert $::c1 018 {*** 018 ***+++}
 535   btree_key $::c1
 536 } {018}
 537 do_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 #
 546 do_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 } {}
 552 do_test btree-7.7 {
 553   lindex [btree_cursor_dump $::c1] 5
 554 } {3}
 555 #btree_page_dump $::b1 2
 556 do_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 #
 564 do_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}
 569 do_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}
 574 do_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}
 579 do_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}
 584 do_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
 590 do_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 #
 596 do_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
 603 do_test btree-8.1.1 {
 604   lindex [btree_pager_stats $::b1] 1
 605 } {2}
 606 #btree_pager_ref_dump $::b1
 607 do_test btree-8.2 {
 608   string length [btree_data $::c1]
 609 } [string length $::data]
 610 do_test btree-8.3 {
 611   btree_data $::c1
 612 } $::data
 613 do_test btree-8.4 {
 614   btree_delete $::c1
 615 } {}
 616 do_test btree-8.4.1 {
 617   lindex [btree_get_meta $::b1] 0
 618 } [expr {int(([string length $::data]-238+1019)/1020)}]
 619 do_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 } {}
 625 do_test btree-8.6 {
 626   string length [btree_data $::c1]
 627 } [string length $::data]
 628 do_test btree-8.7 {
 629   btree_data $::c1
 630 } $::data
 631 do_test btree-8.8 {
 632   btree_commit $::b1
 633   btree_data $::c1
 634 } $::data
 635 do_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
 643 do_test btree-8.10 {
 644   btree_begin_transaction $::b1
 645   btree_delete $::c1
 646 } {}
 647 do_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 #
 653 do_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}
 660 do_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}
 665 do_test btree-8.13 {
 666   btree_key $::c1
 667 } ${keyprefix}1
 668 do_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
 673 do_test btree-8.15 {
 674   btree_move_to $::c1 ${::keyprefix}2
 675   btree_data $::c1
 676 } {2}
 677 do_test btree-8.16 {
 678   btree_move_to $::c1 ${::keyprefix}1
 679   btree_data $::c1
 680 } {1}
 681 do_test btree-8.17 {
 682   btree_move_to $::c1 ${::keyprefix}3
 683   btree_data $::c1
 684 } {3}
 685 do_test btree-8.18 {
 686   lindex [btree_get_meta $::b1] 0
 687 } {1}
 688 do_test btree-8.19 {
 689   btree_move_to $::c1 ${::keyprefix}2
 690   btree_key $::c1
 691 } ${::keyprefix}2
 692 #btree_page_dump $::b1 2
 693 do_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
 699 do_test btree-8.21 {
 700   lindex [btree_get_meta $::b1] 0
 701 } {2}
 702 do_test btree-8.22 {
 703   lindex [btree_pager_stats $::b1] 1
 704 } {2}
 705 do_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}
 711 do_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 #
 718 do_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
 728 do_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.
 741 do_test btree-9.2.1 {
 742   lindex [btree_pager_stats $::b1] 1
 743 } {2}
 744 for {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 }
 754 do_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
 762 do_test btree-9.4.2 {
 763   btree_move_to $::c1 005
 764   btree_delete $::c1
 765 } {}
 766 #btree_page_dump $::b1 2
 767 for {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
 779 do_test btree-9.6 {
 780   btree_close_cursor $::c1
 781   lindex [btree_pager_stats $::b1] 1
 782 } {1}
 783 do_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 #
 792 do_test btree-10.1 {
 793   btree_begin_transaction $::b1
 794   btree_drop_table $::b1 2
 795   lindex [btree_pager_stats $::b1] 1
 796 } {1}
 797 do_test btree-10.2 {
 798   set ::c1 [btree_cursor $::b1 2 1]
 799   lindex [btree_pager_stats $::b1] 1
 800 } {2}
 801 do_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
 812 do_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
 819 for {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 #
 830 catch {unset ::data}
 831 catch {unset ::key}
 832 for {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 }
 849 catch {unset ::data}
 850 catch {unset ::key}
 851
 852 # Make sure our reference count is still correct.
 853 #
 854 do_test btree-11.2 {
 855   btree_close_cursor $::c1
 856   lindex [btree_pager_stats $::b1] 1
 857 } {1}
 858 do_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 #
 866 do_test btree-11.4 {
 867   btree_move_to $::c1 257
 868   btree_delete $::c1
 869   btree_next $::c1
 870   btree_key $::c1
 871 } {258}
 872 do_test btree-11.4.1 {
 873   btree_move_to $::c1 256
 874   btree_key $::c1
 875 } {256}
 876 do_test btree-11.4.2 {
 877   btree_move_to $::c1 258
 878   btree_key $::c1
 879 } {258}
 880 do_test btree-11.4.3 {
 881   btree_move_to $::c1 259
 882   btree_key $::c1
 883 } {259}
 884 do_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}
 889 do_test btree-11.5 {
 890   btree_move_to $::c1 513
 891   btree_delete $::c1
 892   btree_next $::c1
 893   btree_key $::c1
 894 } {514}
 895 do_test btree-11.5.1 {
 896   btree_move_to $::c1 512
 897   btree_key $::c1
 898 } {512}
 899 do_test btree-11.5.2 {
 900   btree_move_to $::c1 514
 901   btree_key $::c1
 902 } {514}
 903 do_test btree-11.5.3 {
 904   btree_move_to $::c1 515
 905   btree_key $::c1
 906 } {515}
 907 do_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}
 912 do_test btree-11.6 {
 913   btree_move_to $::c1 769
 914   btree_delete $::c1
 915   btree_next $::c1
 916   btree_key $::c1
 917 } {770}
 918 do_test btree-11.6.1 {
 919   btree_move_to $::c1 768
 920   btree_key $::c1
 921 } {768}
 922 do_test btree-11.6.2 {
 923   btree_move_to $::c1 771
 924   btree_key $::c1
 925 } {771}
 926 do_test btree-11.6.3 {
 927   btree_move_to $::c1 770
 928   btree_key $::c1
 929 } {770}
 930 do_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 #
 942 catch {unset ::data}
 943 set ::data {This is going to be a very long data segment}
 944 append ::data $::data
 945 append ::data $::data
 946 do_test btree-12.1 {
 947   btree_insert $::c1 337 $::data
 948   btree_data $::c1
 949 } $::data
 950 do_test btree-12.2 {
 951   btree_insert $::c1 401 $::data
 952   btree_data $::c1
 953 } $::data
 954 do_test btree-12.3 {
 955   btree_insert $::c1 465 $::data
 956   btree_data $::c1
 957 } $::data
 958 do_test btree-12.4 {
 959   btree_move_to $::c1 337
 960   btree_key $::c1
 961 } {337}
 962 do_test btree-12.5 {
 963   btree_data $::c1
 964 } $::data
 965 do_test btree-12.6 {
 966   btree_next $::c1
 967   btree_key $::c1
 968 } {338}
 969 do_test btree-12.7 {
 970   btree_move_to $::c1 464
 971   btree_key $::c1
 972 } {464}
 973 do_test btree-12.8 {
 974   btree_next $::c1
 975   btree_data $::c1
 976 } $::data
 977 do_test btree-12.9 {
 978   btree_next $::c1
 979   btree_key $::c1
 980 } {466}
 981 do_test btree-12.10 {
 982   btree_move_to $::c1 400
 983   btree_key $::c1
 984 } {400}
 985 do_test btree-12.11 {
 986   btree_next $::c1
 987   btree_data $::c1
 988 } $::data
 989 do_test btree-12.12 {
 990   btree_next $::c1
 991   btree_key $::c1
 992 } {402}
 993 do_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
1005 do_test btree-15.98 {
1006   btree_close_cursor $::c1
1007   lindex [btree_pager_stats $::b1] 1
1008 } {1}
1009 do_test btree-15.99 {
1010   btree_rollback $::b1
1011   lindex [btree_pager_stats $::b1] 1
1012 } {0}
1013 btree_pager_ref_dump $::b1
1014
1015 do_test btree-99.1 {
1016   btree_close $::b1
1017 } {}
1018 catch {unset data}
1019 catch {unset key}
1020
1021 } ;# end if( not mem: and has pager_open command );
1022
1023 finish_test