/ Hex Artifact Content
Login

Artifact e3b81ec33dc2f89b3e6087436dfe605b870c9080:


0000: 23 20 32 30 30 31 20 53 65 70 74 65 6d 62 65 72  # 2001 September
0010: 20 31 35 0a 23 0a 23 20 54 68 65 20 61 75 74 68   15.#.# The auth
0020: 6f 72 20 64 69 73 63 6c 61 69 6d 73 20 63 6f 70  or disclaims cop
0030: 79 72 69 67 68 74 20 74 6f 20 74 68 69 73 20 73  yright to this s
0040: 6f 75 72 63 65 20 63 6f 64 65 2e 20 20 49 6e 20  ource code.  In 
0050: 70 6c 61 63 65 20 6f 66 0a 23 20 61 20 6c 65 67  place of.# a leg
0060: 61 6c 20 6e 6f 74 69 63 65 2c 20 68 65 72 65 20  al notice, here 
0070: 69 73 20 61 20 62 6c 65 73 73 69 6e 67 3a 0a 23  is a blessing:.#
0080: 0a 23 20 20 20 20 4d 61 79 20 79 6f 75 20 64 6f  .#    May you do
0090: 20 67 6f 6f 64 20 61 6e 64 20 6e 6f 74 20 65 76   good and not ev
00a0: 69 6c 2e 0a 23 20 20 20 20 4d 61 79 20 79 6f 75  il..#    May you
00b0: 20 66 69 6e 64 20 66 6f 72 67 69 76 65 6e 65 73   find forgivenes
00c0: 73 20 66 6f 72 20 79 6f 75 72 73 65 6c 66 20 61  s for yourself a
00d0: 6e 64 20 66 6f 72 67 69 76 65 20 6f 74 68 65 72  nd forgive other
00e0: 73 2e 0a 23 20 20 20 20 4d 61 79 20 79 6f 75 20  s..#    May you 
00f0: 73 68 61 72 65 20 66 72 65 65 6c 79 2c 20 6e 65  share freely, ne
0100: 76 65 72 20 74 61 6b 69 6e 67 20 6d 6f 72 65 20  ver taking more 
0110: 74 68 61 6e 20 79 6f 75 20 67 69 76 65 2e 0a 23  than you give..#
0120: 0a 23 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  .#**************
0130: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0140: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0150: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0160: 2a 2a 2a 2a 2a 2a 2a 2a 2a 0a 23 20 54 68 69 73  *********.# This
0170: 20 66 69 6c 65 20 69 6d 70 6c 65 6d 65 6e 74 73   file implements
0180: 20 72 65 67 72 65 73 73 69 6f 6e 20 74 65 73 74   regression test
0190: 73 20 66 6f 72 20 53 51 4c 69 74 65 20 6c 69 62  s for SQLite lib
01a0: 72 61 72 79 2e 20 20 54 68 65 0a 23 20 66 6f 63  rary.  The.# foc
01b0: 75 73 20 6f 66 20 74 68 69 73 20 73 63 72 69 70  us of this scrip
01c0: 74 20 69 73 20 62 74 72 65 65 20 64 61 74 61 62  t is btree datab
01d0: 61 73 65 20 62 61 63 6b 65 6e 64 0a 23 0a 23 20  ase backend.#.# 
01e0: 24 49 64 3a 20 62 74 72 65 65 32 2e 74 65 73 74  $Id: btree2.test
01f0: 2c 76 20 31 2e 31 30 20 32 30 30 32 2f 30 32 2f  ,v 1.10 2002/02/
0200: 31 39 20 31 33 3a 33 39 3a 32 33 20 64 72 68 20  19 13:39:23 drh 
0210: 45 78 70 20 24 0a 0a 0a 73 65 74 20 74 65 73 74  Exp $...set test
0220: 64 69 72 20 5b 66 69 6c 65 20 64 69 72 6e 61 6d  dir [file dirnam
0230: 65 20 24 61 72 67 76 30 5d 0a 73 6f 75 72 63 65  e $argv0].source
0240: 20 24 74 65 73 74 64 69 72 2f 74 65 73 74 65 72   $testdir/tester
0250: 2e 74 63 6c 0a 0a 69 66 20 7b 5b 69 6e 66 6f 20  .tcl..if {[info 
0260: 63 6f 6d 6d 61 6e 64 73 20 62 74 72 65 65 5f 6f  commands btree_o
0270: 70 65 6e 5d 21 3d 22 22 7d 20 7b 0a 0a 23 20 43  pen]!=""} {..# C
0280: 72 65 61 74 65 20 61 20 6e 65 77 20 64 61 74 61  reate a new data
0290: 62 61 73 65 20 66 69 6c 65 20 63 6f 6e 74 61 69  base file contai
02a0: 6e 69 6e 67 20 6e 6f 20 65 6e 74 72 69 65 73 2e  ning no entries.
02b0: 20 20 54 68 65 20 64 61 74 61 62 61 73 65 20 73    The database s
02c0: 68 6f 75 6c 64 0a 23 20 63 6f 6e 74 61 69 6e 20  hould.# contain 
02d0: 35 20 74 61 62 6c 65 73 3a 0a 23 0a 23 20 20 20  5 tables:.#.#   
02e0: 20 20 32 20 20 20 54 68 65 20 64 65 73 63 72 69    2   The descri
02f0: 70 74 6f 72 20 74 61 62 6c 65 0a 23 20 20 20 20  ptor table.#    
0300: 20 33 20 20 20 54 68 65 20 66 6f 72 65 67 72 6f   3   The foregro
0310: 75 6e 64 20 74 61 62 6c 65 0a 23 20 20 20 20 20  und table.#     
0320: 34 20 20 20 54 68 65 20 62 61 63 6b 67 72 6f 75  4   The backgrou
0330: 6e 64 20 74 61 62 6c 65 0a 23 20 20 20 20 20 35  nd table.#     5
0340: 20 20 20 54 68 65 20 6c 6f 6e 67 20 6b 65 79 20     The long key 
0350: 74 61 62 6c 65 0a 23 20 20 20 20 20 36 20 20 20  table.#     6   
0360: 54 68 65 20 6c 6f 6e 67 20 64 61 74 61 20 74 61  The long data ta
0370: 62 6c 65 0a 23 0a 23 20 41 6e 20 65 78 70 6c 61  ble.#.# An expla
0380: 6e 61 74 69 6f 6e 20 66 6f 72 20 77 68 61 74 20  nation for what 
0390: 61 6c 6c 20 74 68 65 73 65 20 74 61 62 6c 65 73  all these tables
03a0: 20 61 72 65 20 75 73 65 64 20 66 6f 72 20 69 73   are used for is
03b0: 20 70 72 6f 76 69 64 65 64 20 62 65 6c 6f 77 2e   provided below.
03c0: 0a 23 0a 64 6f 5f 74 65 73 74 20 62 74 72 65 65  .#.do_test btree
03d0: 32 2d 31 2e 31 20 7b 0a 20 20 65 78 70 72 20 73  2-1.1 {.  expr s
03e0: 72 61 6e 64 28 31 29 0a 20 20 66 69 6c 65 20 64  rand(1).  file d
03f0: 65 6c 65 74 65 20 2d 66 6f 72 63 65 20 74 65 73  elete -force tes
0400: 74 32 2e 62 74 0a 20 20 66 69 6c 65 20 64 65 6c  t2.bt.  file del
0410: 65 74 65 20 2d 66 6f 72 63 65 20 74 65 73 74 32  ete -force test2
0420: 2e 62 74 2d 6a 6f 75 72 6e 61 6c 0a 20 20 73 65  .bt-journal.  se
0430: 74 20 3a 3a 62 20 5b 62 74 72 65 65 5f 6f 70 65  t ::b [btree_ope
0440: 6e 20 74 65 73 74 32 2e 62 74 5d 0a 20 20 62 74  n test2.bt].  bt
0450: 72 65 65 5f 62 65 67 69 6e 5f 74 72 61 6e 73 61  ree_begin_transa
0460: 63 74 69 6f 6e 20 24 3a 3a 62 0a 20 20 62 74 72  ction $::b.  btr
0470: 65 65 5f 63 72 65 61 74 65 5f 74 61 62 6c 65 20  ee_create_table 
0480: 24 3a 3a 62 0a 7d 20 7b 33 7d 0a 64 6f 5f 74 65  $::b.} {3}.do_te
0490: 73 74 20 62 74 72 65 65 32 2d 31 2e 32 20 7b 0a  st btree2-1.2 {.
04a0: 20 20 62 74 72 65 65 5f 63 72 65 61 74 65 5f 74    btree_create_t
04b0: 61 62 6c 65 20 24 3a 3a 62 0a 7d 20 7b 34 7d 0a  able $::b.} {4}.
04c0: 64 6f 5f 74 65 73 74 20 62 74 72 65 65 32 2d 31  do_test btree2-1
04d0: 2e 33 20 7b 0a 20 20 62 74 72 65 65 5f 63 72 65  .3 {.  btree_cre
04e0: 61 74 65 5f 74 61 62 6c 65 20 24 3a 3a 62 0a 7d  ate_table $::b.}
04f0: 20 7b 35 7d 0a 64 6f 5f 74 65 73 74 20 62 74 72   {5}.do_test btr
0500: 65 65 32 2d 31 2e 34 20 7b 0a 20 20 62 74 72 65  ee2-1.4 {.  btre
0510: 65 5f 63 72 65 61 74 65 5f 74 61 62 6c 65 20 24  e_create_table $
0520: 3a 3a 62 0a 7d 20 7b 36 7d 0a 64 6f 5f 74 65 73  ::b.} {6}.do_tes
0530: 74 20 62 74 72 65 65 32 2d 31 2e 35 20 7b 0a 20  t btree2-1.5 {. 
0540: 20 73 65 74 20 3a 3a 63 32 20 5b 62 74 72 65 65   set ::c2 [btree
0550: 5f 63 75 72 73 6f 72 20 24 3a 3a 62 20 32 20 31  _cursor $::b 2 1
0560: 5d 0a 20 20 62 74 72 65 65 5f 69 6e 73 65 72 74  ].  btree_insert
0570: 20 24 3a 3a 63 32 20 7b 6f 6e 65 7d 20 7b 31 7d   $::c2 {one} {1}
0580: 0a 20 20 62 74 72 65 65 5f 64 65 6c 65 74 65 20  .  btree_delete 
0590: 24 3a 3a 63 32 0a 20 20 62 74 72 65 65 5f 63 6c  $::c2.  btree_cl
05a0: 6f 73 65 5f 63 75 72 73 6f 72 20 24 3a 3a 63 32  ose_cursor $::c2
05b0: 0a 20 20 62 74 72 65 65 5f 63 6f 6d 6d 69 74 20  .  btree_commit 
05c0: 24 3a 3a 62 0a 20 20 62 74 72 65 65 5f 69 6e 74  $::b.  btree_int
05d0: 65 67 72 69 74 79 5f 63 68 65 63 6b 20 24 3a 3a  egrity_check $::
05e0: 62 20 32 20 33 20 34 20 35 20 36 0a 7d 20 7b 7d  b 2 3 4 5 6.} {}
05f0: 0a 0a 23 20 54 68 69 73 20 74 65 73 74 20 6d 6f  ..# This test mo
0600: 64 75 6c 65 20 77 6f 72 6b 73 20 62 79 20 6d 61  dule works by ma
0610: 6b 69 6e 67 20 6c 6f 74 73 20 6f 66 20 70 73 65  king lots of pse
0620: 75 64 6f 2d 72 61 6e 64 6f 6d 20 63 68 61 6e 67  udo-random chang
0630: 65 73 20 74 6f 20 61 0a 23 20 64 61 74 61 62 61  es to a.# databa
0640: 73 65 20 77 68 69 6c 65 20 73 69 6d 75 6c 74 61  se while simulta
0650: 6e 65 6f 75 73 6c 79 20 6d 61 69 6e 74 61 69 6e  neously maintain
0660: 69 6e 67 20 61 6e 20 69 6e 76 61 72 69 61 6e 74  ing an invariant
0670: 20 6f 6e 20 74 68 61 74 20 64 61 74 61 62 61 73   on that databas
0680: 65 2e 0a 23 20 50 65 72 69 6f 64 69 63 61 6c 6c  e..# Periodicall
0690: 79 2c 20 74 68 65 20 73 63 72 69 70 74 20 64 6f  y, the script do
06a0: 65 73 20 61 20 73 61 6e 69 74 79 20 63 68 65 63  es a sanity chec
06b0: 6b 20 6f 6e 20 74 68 65 20 64 61 74 61 62 61 73  k on the databas
06c0: 65 20 61 6e 64 20 76 65 72 69 66 69 65 73 0a 23  e and verifies.#
06d0: 20 74 68 61 74 20 74 68 65 20 69 6e 76 61 72 69   that the invari
06e0: 61 6e 74 20 69 73 20 73 61 74 69 73 66 69 65 64  ant is satisfied
06f0: 2e 0a 23 0a 23 20 54 68 65 20 69 6e 76 61 72 69  ..#.# The invari
0700: 61 6e 74 20 69 73 20 61 73 20 66 6f 6c 6c 6f 77  ant is as follow
0710: 73 3a 0a 23 0a 23 20 20 20 31 2e 20 20 54 68 65  s:.#.#   1.  The
0720: 20 64 65 73 63 72 69 70 74 6f 72 20 74 61 62 6c   descriptor tabl
0730: 65 20 61 6c 77 61 79 73 20 63 6f 6e 74 61 69 6e  e always contain
0740: 73 20 32 20 65 6e 74 65 72 73 2e 20 20 41 6e 20  s 2 enters.  An 
0750: 65 6e 74 72 79 20 6b 65 79 65 64 20 62 79 0a 23  entry keyed by.#
0760: 20 20 20 20 20 20 20 22 4e 22 20 69 73 20 74 68         "N" is th
0770: 65 20 6e 75 6d 62 65 72 20 6f 66 20 65 6c 65 6d  e number of elem
0780: 65 6e 74 73 20 69 6e 20 74 68 65 20 66 6f 72 65  ents in the fore
0790: 67 72 6f 75 6e 64 20 61 6e 64 20 62 61 63 6b 67  ground and backg
07a0: 72 6f 75 6e 64 20 74 61 62 6c 65 73 0a 23 20 20  round tables.#  
07b0: 20 20 20 20 20 63 6f 6d 62 69 6e 65 64 2e 20 20       combined.  
07c0: 54 68 65 20 65 6e 74 72 79 20 6b 65 79 65 64 20  The entry keyed 
07d0: 62 79 20 22 4c 22 20 69 73 20 74 68 65 20 6e 75  by "L" is the nu
07e0: 6d 62 65 72 20 6f 66 20 64 69 67 69 74 73 20 69  mber of digits i
07f0: 6e 20 74 68 65 20 6b 65 79 73 0a 23 20 20 20 20  n the keys.#    
0800: 20 20 20 66 6f 72 20 66 6f 72 65 67 72 6f 75 6e     for foregroun
0810: 64 20 61 6e 64 20 62 61 63 6b 67 72 6f 75 6e 64  d and background
0820: 20 74 61 62 6c 65 73 2e 0a 23 0a 23 20 20 20 32   tables..#.#   2
0830: 2e 20 20 54 68 65 20 75 6e 69 6f 6e 20 6f 66 20  .  The union of 
0840: 74 68 65 20 66 6f 72 65 67 72 6f 75 6e 64 20 61  the foreground a
0850: 6e 20 62 61 63 6b 67 72 6f 75 6e 64 20 74 61 62  n background tab
0860: 6c 65 73 20 63 6f 6e 73 69 73 74 73 20 6f 66 20  les consists of 
0870: 4e 20 65 6e 74 72 69 65 73 0a 23 20 20 20 20 20  N entries.#     
0880: 20 20 77 68 65 72 65 20 65 61 63 68 20 65 6e 74    where each ent
0890: 72 79 20 61 6e 20 4c 2d 64 69 67 69 74 20 6b 65  ry an L-digit ke
08a0: 79 2e 20 20 28 41 63 74 75 61 6c 6c 79 2c 20 73  y.  (Actually, s
08b0: 6f 6d 65 20 6b 65 79 73 20 63 61 6e 20 62 65 20  ome keys can be 
08c0: 6c 6f 6e 67 65 72 20 0a 23 20 20 20 20 20 20 20  longer .#       
08d0: 74 68 61 6e 20 4c 20 63 68 61 72 61 63 74 65 72  than L character
08e0: 73 2c 20 62 75 74 20 74 68 65 79 20 61 6c 77 61  s, but they alwa
08f0: 79 73 20 73 74 61 72 74 20 77 69 74 68 20 4c 20  ys start with L 
0900: 64 69 67 69 74 73 2e 29 20 20 54 68 65 20 6b 65  digits.)  The ke
0910: 79 73 0a 23 20 20 20 20 20 20 20 63 6f 76 65 72  ys.#       cover
0920: 20 61 6c 6c 20 69 6e 74 65 67 65 72 73 20 62 65   all integers be
0930: 74 77 65 65 6e 20 31 20 61 6e 64 20 4e 2e 20 20  tween 1 and N.  
0940: 57 68 65 6e 65 76 65 72 20 61 6e 20 65 6e 74 72  Whenever an entr
0950: 79 20 69 73 20 61 64 64 65 64 20 74 6f 0a 23 20  y is added to.# 
0960: 20 20 20 20 20 20 74 68 65 20 66 6f 72 65 67 72        the foregr
0970: 6f 75 6e 64 20 69 74 20 69 73 20 72 65 6d 6f 76  ound it is remov
0980: 65 64 20 66 6f 72 6d 20 74 68 65 20 62 61 63 6b  ed form the back
0990: 67 72 6f 75 6e 64 20 61 6e 64 20 76 69 63 65 20  ground and vice 
09a0: 76 65 72 73 61 2e 0a 23 0a 23 20 20 20 33 2e 20  versa..#.#   3. 
09b0: 20 53 6f 6d 65 20 65 6e 74 72 69 65 73 20 69 6e   Some entries in
09c0: 20 74 68 65 20 66 6f 72 65 67 72 6f 75 6e 64 20   the foreground 
09d0: 61 6e 64 20 62 61 63 6b 67 72 6f 75 6e 64 20 74  and background t
09e0: 61 62 6c 65 73 20 68 61 76 65 20 6b 65 79 73 20  ables have keys 
09f0: 74 68 61 74 0a 23 20 20 20 20 20 20 20 62 65 67  that.#       beg
0a00: 69 6e 20 77 69 74 68 20 61 6e 20 4c 2d 64 69 67  in with an L-dig
0a10: 69 74 20 6e 75 6d 62 65 72 20 62 75 74 20 61 72  it number but ar
0a20: 65 20 66 6f 6c 6c 6f 77 65 64 20 62 79 20 61 64  e followed by ad
0a30: 64 69 74 69 6f 6e 61 6c 20 63 68 61 72 61 63 74  ditional charact
0a40: 65 72 73 2e 0a 23 20 20 20 20 20 20 20 46 6f 72  ers..#       For
0a50: 20 65 61 63 68 20 73 75 63 68 20 65 6e 74 72 79   each such entry
0a60: 20 74 68 65 72 65 20 69 73 20 61 20 63 6f 72 72   there is a corr
0a70: 65 73 70 6f 6e 64 69 6e 67 20 65 6e 74 72 79 20  esponding entry 
0a80: 69 6e 20 74 68 65 20 6c 6f 6e 67 20 6b 65 79 0a  in the long key.
0a90: 23 20 20 20 20 20 20 20 74 61 62 6c 65 2e 20 20  #       table.  
0aa0: 54 68 65 20 6c 6f 6e 67 20 6b 65 79 20 74 61 62  The long key tab
0ab0: 6c 65 20 65 6e 74 72 79 20 68 61 73 20 61 20 6b  le entry has a k
0ac0: 65 79 20 77 68 69 63 68 20 69 73 20 6a 75 73 74  ey which is just
0ad0: 20 74 68 65 20 4c 2d 64 69 67 69 74 0a 23 20 20   the L-digit.#  
0ae0: 20 20 20 20 20 6e 75 6d 62 65 72 20 61 6e 64 20       number and 
0af0: 64 61 74 61 20 77 68 69 63 68 20 69 73 20 74 68  data which is th
0b00: 65 20 6c 65 6e 67 74 68 20 6f 66 20 74 68 65 20  e length of the 
0b10: 6b 65 79 20 69 6e 20 74 68 65 20 66 6f 72 65 67  key in the foreg
0b20: 72 6f 75 6e 64 20 61 6e 64 0a 23 20 20 20 20 20  round and.#     
0b30: 20 20 62 61 63 6b 67 72 6f 75 6e 64 20 74 61 62    background tab
0b40: 6c 65 73 2e 0a 23 0a 23 20 20 20 34 2e 20 20 54  les..#.#   4.  T
0b50: 68 65 20 64 61 74 61 20 66 6f 72 20 62 6f 74 68  he data for both
0b60: 20 66 6f 72 65 67 72 6f 75 6e 64 20 61 6e 64 20   foreground and 
0b70: 62 61 63 6b 67 72 6f 75 6e 64 20 65 6e 74 72 69  background entri
0b80: 65 73 20 69 73 20 75 73 75 61 6c 6c 79 20 61 0a  es is usually a.
0b90: 23 20 20 20 20 20 20 20 73 68 6f 72 74 20 73 74  #       short st
0ba0: 72 69 6e 67 2e 20 20 42 75 74 20 73 6f 6d 65 20  ring.  But some 
0bb0: 65 6e 74 72 69 65 73 20 68 61 76 65 20 6c 6f 6e  entries have lon
0bc0: 67 20 64 61 74 61 20 73 74 72 69 6e 67 73 2e 20  g data strings. 
0bd0: 20 46 6f 72 20 65 61 63 68 0a 23 20 20 20 20 20   For each.#     
0be0: 20 20 73 75 63 68 20 65 6e 74 72 69 65 73 20 74    such entries t
0bf0: 68 65 72 65 20 69 73 20 61 6e 20 65 6e 74 72 79  here is an entry
0c00: 20 69 6e 20 74 68 65 20 6c 6f 6e 67 20 64 61 74   in the long dat
0c10: 61 20 74 79 70 65 2e 20 20 54 68 65 20 6b 65 79  a type.  The key
0c20: 20 74 6f 0a 23 20 20 20 20 20 20 20 6c 6f 6e 67   to.#       long
0c30: 20 64 61 74 61 20 74 61 62 6c 65 20 69 73 20 61   data table is a
0c40: 6e 20 4c 2d 64 69 67 69 74 20 6e 75 6d 62 65 72  n L-digit number
0c50: 2e 20 20 28 54 68 65 20 65 78 74 65 6e 73 69 6f  .  (The extensio
0c60: 6e 20 6f 6e 20 6c 6f 6e 67 20 6b 65 79 73 0a 23  n on long keys.#
0c70: 20 20 20 20 20 20 20 69 73 20 6f 6d 69 74 74 65         is omitte
0c80: 64 2e 29 20 20 54 68 65 20 64 61 74 61 20 69 73  d.)  The data is
0c90: 20 74 68 65 20 6e 75 6d 62 65 72 20 6f 66 20 63   the number of c
0ca0: 68 61 72 61 74 65 72 73 20 69 6e 20 74 68 65 20  haraters in the 
0cb0: 64 61 74 61 20 6f 66 20 74 68 65 0a 23 20 20 20  data of the.#   
0cc0: 20 20 20 20 66 6f 72 65 67 72 6f 75 6e 64 20 6f      foreground o
0cd0: 72 20 62 61 63 6b 67 72 6f 75 6e 64 20 65 6e 74  r background ent
0ce0: 72 79 2e 0a 23 0a 23 20 54 68 65 20 66 6f 6c 6c  ry..#.# The foll
0cf0: 6f 77 69 6e 67 20 66 75 6e 63 74 69 6f 6e 20 62  owing function b
0d00: 75 69 6c 64 73 20 61 20 64 61 74 61 62 61 73 65  uilds a database
0d10: 20 74 68 61 74 20 73 61 74 69 73 66 69 65 73 20   that satisfies 
0d20: 61 6c 6c 20 6f 66 20 74 68 65 20 61 62 6f 76 65  all of the above
0d30: 0a 23 20 69 6e 76 61 72 69 61 6e 74 73 2e 0a 23  .# invariants..#
0d40: 0a 70 72 6f 63 20 62 75 69 6c 64 5f 64 62 20 7b  .proc build_db {
0d50: 4e 20 4c 7d 20 7b 0a 20 20 66 6f 72 20 7b 73 65  N L} {.  for {se
0d60: 74 20 69 20 32 7d 20 7b 24 69 3c 3d 36 7d 20 7b  t i 2} {$i<=6} {
0d70: 69 6e 63 72 20 69 7d 20 7b 0a 20 20 20 20 63 61  incr i} {.    ca
0d80: 74 63 68 20 7b 62 74 72 65 65 5f 63 6c 6f 73 65  tch {btree_close
0d90: 5f 63 75 72 73 6f 72 20 5b 73 65 74 20 3a 3a 63  _cursor [set ::c
0da0: 24 69 5d 7d 0a 20 20 20 20 62 74 72 65 65 5f 63  $i]}.    btree_c
0db0: 6c 65 61 72 5f 74 61 62 6c 65 20 24 3a 3a 62 20  lear_table $::b 
0dc0: 24 69 0a 20 20 20 20 73 65 74 20 3a 3a 63 24 69  $i.    set ::c$i
0dd0: 20 5b 62 74 72 65 65 5f 63 75 72 73 6f 72 20 24   [btree_cursor $
0de0: 3a 3a 62 20 24 69 20 31 5d 0a 20 20 7d 0a 20 20  ::b $i 1].  }.  
0df0: 62 74 72 65 65 5f 69 6e 73 65 72 74 20 24 3a 3a  btree_insert $::
0e00: 63 32 20 4e 20 24 4e 0a 20 20 62 74 72 65 65 5f  c2 N $N.  btree_
0e10: 69 6e 73 65 72 74 20 24 3a 3a 63 32 20 4c 20 24  insert $::c2 L $
0e20: 4c 0a 20 20 73 65 74 20 66 6f 72 6d 61 74 20 25  L.  set format %
0e30: 30 24 7b 4c 7d 64 0a 20 20 66 6f 72 20 7b 73 65  0${L}d.  for {se
0e40: 74 20 69 20 31 7d 20 7b 24 69 3c 3d 24 4e 7d 20  t i 1} {$i<=$N} 
0e50: 7b 69 6e 63 72 20 69 7d 20 7b 20 0a 20 20 20 20  {incr i} { .    
0e60: 73 65 74 20 6b 65 79 20 5b 66 6f 72 6d 61 74 20  set key [format 
0e70: 24 66 6f 72 6d 61 74 20 24 69 5d 0a 20 20 20 20  $format $i].    
0e80: 73 65 74 20 64 61 74 61 20 24 6b 65 79 0a 20 20  set data $key.  
0e90: 20 20 62 74 72 65 65 5f 69 6e 73 65 72 74 20 24    btree_insert $
0ea0: 3a 3a 63 33 20 24 6b 65 79 20 24 64 61 74 61 0a  ::c3 $key $data.
0eb0: 20 20 7d 0a 7d 0a 0a 23 20 47 69 76 65 6e 20 61    }.}..# Given a
0ec0: 20 62 61 73 65 20 6b 65 79 20 6e 75 6d 62 65 72   base key number
0ed0: 20 61 6e 64 20 61 20 6c 65 6e 67 74 68 2c 20 63   and a length, c
0ee0: 6f 6e 73 74 72 75 63 74 20 74 68 65 20 66 75 6c  onstruct the ful
0ef0: 6c 20 74 65 78 74 20 6f 66 20 74 68 65 20 6b 65  l text of the ke
0f00: 79 0a 23 20 6f 72 20 64 61 74 61 2e 0a 23 0a 70  y.# or data..#.p
0f10: 72 6f 63 20 6d 61 6b 65 5f 70 61 79 6c 6f 61 64  roc make_payload
0f20: 20 7b 6b 65 79 6e 75 6d 20 4c 20 6c 65 6e 7d 20   {keynum L len} 
0f30: 7b 0a 20 20 73 65 74 20 6b 65 79 20 5b 66 6f 72  {.  set key [for
0f40: 6d 61 74 20 25 30 24 7b 4c 7d 64 20 24 6b 65 79  mat %0${L}d $key
0f50: 6e 75 6d 5d 0a 20 20 73 65 74 20 72 20 24 6b 65  num].  set r $ke
0f60: 79 0a 20 20 73 65 74 20 69 20 31 0a 20 20 77 68  y.  set i 1.  wh
0f70: 69 6c 65 20 7b 5b 73 74 72 69 6e 67 20 6c 65 6e  ile {[string len
0f80: 67 74 68 20 24 72 5d 3c 24 6c 65 6e 7d 20 7b 0a  gth $r]<$len} {.
0f90: 20 20 20 20 61 70 70 65 6e 64 20 72 20 22 20 28      append r " (
0fa0: 24 69 29 20 24 6b 65 79 22 0a 20 20 20 20 69 6e  $i) $key".    in
0fb0: 63 72 20 69 0a 20 20 7d 0a 20 20 72 65 74 75 72  cr i.  }.  retur
0fc0: 6e 20 5b 73 74 72 69 6e 67 20 72 61 6e 67 65 20  n [string range 
0fd0: 24 72 20 30 20 5b 65 78 70 72 20 7b 24 6c 65 6e  $r 0 [expr {$len
0fe0: 2d 31 7d 5d 5d 0a 7d 0a 0a 23 20 56 65 72 69 66  -1}]].}..# Verif
0ff0: 79 20 74 68 65 20 69 6e 76 61 72 69 61 6e 74 73  y the invariants
1000: 20 6f 6e 20 74 68 65 20 64 61 74 61 62 61 73 65   on the database
1010: 2e 20 20 52 65 74 75 72 6e 20 61 6e 20 65 6d 70  .  Return an emp
1020: 74 79 20 73 74 72 69 6e 67 20 6f 6e 20 0a 23 20  ty string on .# 
1030: 73 75 63 63 65 73 73 20 6f 72 20 61 6e 20 65 72  success or an er
1040: 72 6f 72 20 6d 65 73 73 61 67 65 20 69 66 20 73  ror message if s
1050: 6f 6d 65 74 68 69 6e 67 20 69 73 20 61 6d 69 73  omething is amis
1060: 73 2e 0a 23 0a 70 72 6f 63 20 63 68 65 63 6b 5f  s..#.proc check_
1070: 69 6e 76 61 72 69 61 6e 74 73 20 7b 7d 20 7b 0a  invariants {} {.
1080: 20 20 73 65 74 20 63 6b 20 5b 62 74 72 65 65 5f    set ck [btree_
1090: 69 6e 74 65 67 72 69 74 79 5f 63 68 65 63 6b 20  integrity_check 
10a0: 24 3a 3a 62 20 32 20 33 20 34 20 35 20 36 5d 0a  $::b 2 3 4 5 6].
10b0: 20 20 69 66 20 7b 24 63 6b 21 3d 22 22 7d 20 7b    if {$ck!=""} {
10c0: 0a 20 20 20 20 70 75 74 73 20 22 5c 6e 2a 2a 2a  .    puts "\n***
10d0: 20 53 41 4e 49 54 59 3a 5c 6e 24 63 6b 22 0a 20   SANITY:\n$ck". 
10e0: 20 20 20 65 78 69 74 0a 20 20 20 20 72 65 74 75     exit.    retu
10f0: 72 6e 20 24 63 6b 0a 20 20 7d 0a 20 20 62 74 72  rn $ck.  }.  btr
1100: 65 65 5f 6d 6f 76 65 5f 74 6f 20 24 3a 3a 63 33  ee_move_to $::c3
1110: 20 7b 7d 0a 20 20 62 74 72 65 65 5f 6d 6f 76 65   {}.  btree_move
1120: 5f 74 6f 20 24 3a 3a 63 34 20 7b 7d 0a 20 20 62  _to $::c4 {}.  b
1130: 74 72 65 65 5f 6d 6f 76 65 5f 74 6f 20 24 3a 3a  tree_move_to $::
1140: 63 32 20 4e 0a 20 20 73 65 74 20 4e 20 5b 62 74  c2 N.  set N [bt
1150: 72 65 65 5f 64 61 74 61 20 24 3a 3a 63 32 5d 0a  ree_data $::c2].
1160: 20 20 62 74 72 65 65 5f 6d 6f 76 65 5f 74 6f 20    btree_move_to 
1170: 24 3a 3a 63 32 20 4c 0a 20 20 73 65 74 20 4c 20  $::c2 L.  set L 
1180: 5b 62 74 72 65 65 5f 64 61 74 61 20 24 3a 3a 63  [btree_data $::c
1190: 32 5d 0a 20 20 73 65 74 20 4c 4d 31 20 5b 65 78  2].  set LM1 [ex
11a0: 70 72 20 7b 24 4c 2d 31 7d 5d 0a 20 20 66 6f 72  pr {$L-1}].  for
11b0: 20 7b 73 65 74 20 69 20 31 7d 20 7b 24 69 3c 3d   {set i 1} {$i<=
11c0: 24 4e 7d 20 7b 69 6e 63 72 20 69 7d 20 7b 0a 20  $N} {incr i} {. 
11d0: 20 20 20 73 65 74 20 6b 65 79 20 5b 62 74 72 65     set key [btre
11e0: 65 5f 6b 65 79 20 24 3a 3a 63 33 5d 0a 20 20 20  e_key $::c3].   
11f0: 20 69 66 20 7b 5b 73 63 61 6e 20 24 6b 65 79 20   if {[scan $key 
1200: 25 64 20 6b 5d 3c 31 7d 20 7b 73 65 74 20 6b 20  %d k]<1} {set k 
1210: 30 7d 0a 20 20 20 20 69 66 20 7b 24 6b 21 3d 24  0}.    if {$k!=$
1220: 69 7d 20 7b 0a 20 20 20 20 20 20 73 65 74 20 6b  i} {.      set k
1230: 65 79 20 5b 62 74 72 65 65 5f 6b 65 79 20 24 3a  ey [btree_key $:
1240: 3a 63 34 5d 0a 20 20 20 20 20 20 69 66 20 7b 5b  :c4].      if {[
1250: 73 63 61 6e 20 24 6b 65 79 20 25 64 20 6b 5d 3c  scan $key %d k]<
1260: 31 7d 20 7b 73 65 74 20 6b 20 30 7d 0a 20 20 20  1} {set k 0}.   
1270: 20 20 20 69 66 20 7b 24 6b 21 3d 24 69 7d 20 7b     if {$k!=$i} {
1280: 0a 20 20 20 20 20 20 20 20 23 20 70 75 74 73 20  .        # puts 
1290: 22 4d 49 53 53 49 4e 47 20 24 69 22 0a 20 20 20  "MISSING $i".   
12a0: 20 20 20 20 20 23 20 70 75 74 73 20 7b 50 61 67       # puts {Pag
12b0: 65 20 33 3a 7d 3b 20 62 74 72 65 65 5f 70 61 67  e 3:}; btree_pag
12c0: 65 5f 64 75 6d 70 20 24 3a 3a 62 20 33 0a 20 20  e_dump $::b 3.  
12d0: 20 20 20 20 20 20 23 20 70 75 74 73 20 7b 50 61        # puts {Pa
12e0: 67 65 20 34 3a 7d 3b 20 62 74 72 65 65 5f 70 61  ge 4:}; btree_pa
12f0: 67 65 5f 64 75 6d 70 20 24 3a 3a 62 20 34 0a 20  ge_dump $::b 4. 
1300: 20 20 20 20 20 20 20 23 20 65 78 69 74 0a 20 20         # exit.  
1310: 20 20 20 20 20 20 72 65 74 75 72 6e 20 22 4b 65        return "Ke
1320: 79 20 24 69 20 69 73 20 6d 69 73 73 69 6e 67 20  y $i is missing 
1330: 66 72 6f 6d 20 62 6f 74 68 20 66 6f 72 65 67 72  from both foregr
1340: 6f 75 6e 64 20 61 6e 64 20 62 61 63 6b 67 72 6f  ound and backgro
1350: 75 6e 64 22 0a 20 20 20 20 20 20 7d 0a 20 20 20  und".      }.   
1360: 20 20 20 73 65 74 20 64 61 74 61 20 5b 62 74 72     set data [btr
1370: 65 65 5f 64 61 74 61 20 24 3a 3a 63 34 5d 0a 20  ee_data $::c4]. 
1380: 20 20 20 20 20 62 74 72 65 65 5f 6e 65 78 74 20       btree_next 
1390: 24 3a 3a 63 34 0a 20 20 20 20 7d 20 65 6c 73 65  $::c4.    } else
13a0: 20 7b 0a 20 20 20 20 20 20 73 65 74 20 64 61 74   {.      set dat
13b0: 61 20 5b 62 74 72 65 65 5f 64 61 74 61 20 24 3a  a [btree_data $:
13c0: 3a 63 33 5d 0a 20 20 20 20 20 20 62 74 72 65 65  :c3].      btree
13d0: 5f 6e 65 78 74 20 24 3a 3a 63 33 0a 20 20 20 20  _next $::c3.    
13e0: 7d 0a 20 20 20 20 73 65 74 20 73 6b 65 79 20 5b  }.    set skey [
13f0: 73 74 72 69 6e 67 20 72 61 6e 67 65 20 24 6b 65  string range $ke
1400: 79 20 30 20 24 4c 4d 31 5d 0a 20 20 20 20 69 66  y 0 $LM1].    if
1410: 20 7b 5b 62 74 72 65 65 5f 6d 6f 76 65 5f 74 6f   {[btree_move_to
1420: 20 24 3a 3a 63 35 20 24 73 6b 65 79 5d 3d 3d 30   $::c5 $skey]==0
1430: 7d 20 7b 0a 20 20 20 20 20 20 73 65 74 20 6b 65  } {.      set ke
1440: 79 6c 65 6e 20 5b 62 74 72 65 65 5f 64 61 74 61  ylen [btree_data
1450: 20 24 3a 3a 63 35 5d 0a 20 20 20 20 7d 20 65 6c   $::c5].    } el
1460: 73 65 20 7b 0a 20 20 20 20 20 20 73 65 74 20 6b  se {.      set k
1470: 65 79 6c 65 6e 20 24 4c 0a 20 20 20 20 7d 0a 20  eylen $L.    }. 
1480: 20 20 20 69 66 20 7b 5b 73 74 72 69 6e 67 20 6c     if {[string l
1490: 65 6e 67 74 68 20 24 6b 65 79 5d 21 3d 24 6b 65  ength $key]!=$ke
14a0: 79 6c 65 6e 7d 20 7b 0a 20 20 20 20 20 20 72 65  ylen} {.      re
14b0: 74 75 72 6e 20 22 4b 65 79 20 24 69 20 69 73 20  turn "Key $i is 
14c0: 74 68 65 20 77 72 6f 6e 67 20 73 69 7a 65 2e 5c  the wrong size.\
14d0: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 49  .              I
14e0: 73 20 5c 22 24 6b 65 79 5c 22 20 62 75 74 20 73  s \"$key\" but s
14f0: 68 6f 75 6c 64 20 62 65 20 5c 22 5b 6d 61 6b 65  hould be \"[make
1500: 5f 70 61 79 6c 6f 61 64 20 24 6b 20 24 4c 20 24  _payload $k $L $
1510: 6b 65 79 6c 65 6e 5d 5c 22 22 0a 20 20 20 20 7d  keylen]\"".    }
1520: 0a 20 20 20 20 69 66 20 7b 5b 6d 61 6b 65 5f 70  .    if {[make_p
1530: 61 79 6c 6f 61 64 20 24 6b 20 24 4c 20 24 6b 65  ayload $k $L $ke
1540: 79 6c 65 6e 5d 21 3d 24 6b 65 79 7d 20 7b 0a 20  ylen]!=$key} {. 
1550: 20 20 20 20 20 72 65 74 75 72 6e 20 22 4b 65 79       return "Key
1560: 20 24 69 20 68 61 73 20 61 6e 20 69 6e 76 61 6c   $i has an inval
1570: 69 64 20 65 78 74 65 6e 73 69 6f 6e 22 0a 20 20  id extension".  
1580: 20 20 7d 0a 20 20 20 20 69 66 20 7b 5b 62 74 72    }.    if {[btr
1590: 65 65 5f 6d 6f 76 65 5f 74 6f 20 24 3a 3a 63 36  ee_move_to $::c6
15a0: 20 24 73 6b 65 79 5d 3d 3d 30 7d 20 7b 0a 20 20   $skey]==0} {.  
15b0: 20 20 20 20 73 65 74 20 64 61 74 61 6c 65 6e 20      set datalen 
15c0: 5b 62 74 72 65 65 5f 64 61 74 61 20 24 3a 3a 63  [btree_data $::c
15d0: 36 5d 0a 20 20 20 20 7d 20 65 6c 73 65 20 7b 0a  6].    } else {.
15e0: 20 20 20 20 20 20 73 65 74 20 64 61 74 61 6c 65        set datale
15f0: 6e 20 24 4c 0a 20 20 20 20 7d 0a 20 20 20 20 69  n $L.    }.    i
1600: 66 20 7b 5b 73 74 72 69 6e 67 20 6c 65 6e 67 74  f {[string lengt
1610: 68 20 24 64 61 74 61 5d 21 3d 24 64 61 74 61 6c  h $data]!=$datal
1620: 65 6e 7d 20 7b 0a 20 20 20 20 20 20 72 65 74 75  en} {.      retu
1630: 72 6e 20 22 44 61 74 61 20 66 6f 72 20 24 69 20  rn "Data for $i 
1640: 69 73 20 74 68 65 20 77 72 6f 6e 67 20 73 69 7a  is the wrong siz
1650: 65 2e 5c 0a 20 20 20 20 20 20 20 20 20 20 20 20  e.\.            
1660: 20 20 49 73 20 5b 73 74 72 69 6e 67 20 6c 65 6e    Is [string len
1670: 67 74 68 20 24 64 61 74 61 5d 20 62 75 74 20 73  gth $data] but s
1680: 68 6f 75 6c 64 20 62 65 20 24 64 61 74 61 6c 65  hould be $datale
1690: 6e 22 0a 20 20 20 20 7d 0a 20 20 20 20 69 66 20  n".    }.    if 
16a0: 7b 5b 6d 61 6b 65 5f 70 61 79 6c 6f 61 64 20 24  {[make_payload $
16b0: 6b 20 24 4c 20 24 64 61 74 61 6c 65 6e 5d 21 3d  k $L $datalen]!=
16c0: 24 64 61 74 61 7d 20 7b 0a 20 20 20 20 20 20 72  $data} {.      r
16d0: 65 74 75 72 6e 20 22 45 6e 74 72 79 20 24 69 20  eturn "Entry $i 
16e0: 68 61 73 20 61 6e 20 69 6e 63 6f 72 72 65 63 74  has an incorrect
16f0: 20 64 61 74 61 22 0a 20 20 20 20 7d 0a 20 20 7d   data".    }.  }
1700: 0a 7d 0a 0a 23 20 4d 61 6b 65 20 72 61 6e 64 6f  .}..# Make rando
1710: 6d 20 63 68 61 6e 67 65 73 20 74 6f 20 74 68 65  m changes to the
1720: 20 64 61 74 61 62 61 73 65 20 73 75 63 68 20 74   database such t
1730: 68 61 74 20 65 61 63 68 20 63 68 61 6e 67 65 20  hat each change 
1740: 70 72 65 73 65 72 76 65 73 0a 23 20 74 68 65 20  preserves.# the 
1750: 69 6e 76 61 72 69 61 6e 74 73 2e 20 20 54 68 65  invariants.  The
1760: 20 6e 75 6d 62 65 72 20 6f 66 20 63 68 61 6e 67   number of chang
1770: 65 73 20 69 73 20 24 6e 2a 4e 20 77 68 65 72 65  es is $n*N where
1780: 20 4e 20 69 73 20 74 68 65 20 70 61 72 61 6d 65   N is the parame
1790: 74 65 72 0a 23 20 66 72 6f 6d 20 74 68 65 20 64  ter.# from the d
17a0: 65 73 63 72 69 70 74 6f 72 20 74 61 62 6c 65 2e  escriptor table.
17b0: 20 20 45 61 63 68 20 63 68 61 6e 67 65 73 20 62    Each changes b
17c0: 65 67 69 6e 73 20 77 69 74 68 20 61 20 72 61 6e  egins with a ran
17d0: 64 6f 6d 20 6b 65 79 2e 0a 23 20 74 68 65 20 65  dom key..# the e
17e0: 6e 74 72 79 20 77 69 74 68 20 74 68 61 74 20 6b  ntry with that k
17f0: 65 79 20 69 73 20 70 75 74 20 69 6e 20 74 68 65  ey is put in the
1800: 20 66 6f 72 65 67 72 6f 75 6e 64 20 74 61 62 6c   foreground tabl
1810: 65 20 77 69 74 68 20 70 72 6f 62 61 62 69 6c 69  e with probabili
1820: 74 79 0a 23 20 24 49 20 61 6e 64 20 69 74 20 69  ty.# $I and it i
1830: 73 20 70 75 74 20 69 6e 20 62 61 63 6b 67 72 6f  s put in backgro
1840: 75 6e 64 20 77 69 74 68 20 70 72 6f 62 61 62 69  und with probabi
1850: 6c 69 74 79 20 28 31 2e 30 2d 24 49 29 2e 20 20  lity (1.0-$I).  
1860: 49 74 20 67 65 74 73 0a 23 20 61 20 6c 6f 6e 67  It gets.# a long
1870: 20 6b 65 79 20 77 69 74 68 20 70 72 6f 62 61 62   key with probab
1880: 69 6c 69 74 79 20 24 4b 20 61 6e 64 20 6c 6f 6e  ility $K and lon
1890: 67 20 64 61 74 61 20 77 69 74 68 20 70 72 6f 62  g data with prob
18a0: 61 62 69 6c 69 74 79 20 24 44 2e 20 20 0a 23 20  ability $D.  .# 
18b0: 0a 73 65 74 20 63 68 6e 67 63 6e 74 20 30 0a 70  .set chngcnt 0.p
18c0: 72 6f 63 20 72 61 6e 64 6f 6d 5f 63 68 61 6e 67  roc random_chang
18d0: 65 73 20 7b 6e 20 49 20 4b 20 44 7d 20 7b 0a 20  es {n I K D} {. 
18e0: 20 62 74 72 65 65 5f 6d 6f 76 65 5f 74 6f 20 24   btree_move_to $
18f0: 3a 3a 63 32 20 4e 0a 20 20 73 65 74 20 4e 20 5b  ::c2 N.  set N [
1900: 62 74 72 65 65 5f 64 61 74 61 20 24 3a 3a 63 32  btree_data $::c2
1910: 5d 0a 20 20 62 74 72 65 65 5f 6d 6f 76 65 5f 74  ].  btree_move_t
1920: 6f 20 24 3a 3a 63 32 20 4c 0a 20 20 73 65 74 20  o $::c2 L.  set 
1930: 4c 20 5b 62 74 72 65 65 5f 64 61 74 61 20 24 3a  L [btree_data $:
1940: 3a 63 32 5d 0a 20 20 73 65 74 20 4c 4d 31 20 5b  :c2].  set LM1 [
1950: 65 78 70 72 20 7b 24 4c 2d 31 7d 5d 0a 20 20 73  expr {$L-1}].  s
1960: 65 74 20 74 6f 74 61 6c 20 5b 65 78 70 72 20 7b  et total [expr {
1970: 69 6e 74 28 24 4e 2a 24 6e 29 7d 5d 0a 20 20 73  int($N*$n)}].  s
1980: 65 74 20 66 6f 72 6d 61 74 20 25 30 24 7b 4c 7d  et format %0${L}
1990: 64 0a 20 20 66 6f 72 20 7b 73 65 74 20 69 20 30  d.  for {set i 0
19a0: 7d 20 7b 24 69 3c 24 74 6f 74 61 6c 7d 20 7b 69  } {$i<$total} {i
19b0: 6e 63 72 20 69 7d 20 7b 0a 20 20 20 20 73 65 74  ncr i} {.    set
19c0: 20 6b 20 5b 65 78 70 72 20 7b 69 6e 74 28 72 61   k [expr {int(ra
19d0: 6e 64 28 29 2a 24 4e 29 2b 31 7d 5d 0a 20 20 20  nd()*$N)+1}].   
19e0: 20 73 65 74 20 69 6e 73 65 72 74 20 5b 65 78 70   set insert [exp
19f0: 72 20 7b 72 61 6e 64 28 29 3c 3d 24 49 7d 5d 0a  r {rand()<=$I}].
1a00: 20 20 20 20 73 65 74 20 6c 6f 6e 67 6b 65 79 20      set longkey 
1a10: 5b 65 78 70 72 20 7b 72 61 6e 64 28 29 3c 3d 24  [expr {rand()<=$
1a20: 4b 7d 5d 0a 20 20 20 20 73 65 74 20 6c 6f 6e 67  K}].    set long
1a30: 64 61 74 61 20 5b 65 78 70 72 20 7b 72 61 6e 64  data [expr {rand
1a40: 28 29 3c 3d 24 44 7d 5d 0a 20 20 20 20 23 20 69  ()<=$D}].    # i
1a50: 6e 63 72 20 3a 3a 63 68 6e 67 63 6e 74 0a 20 20  ncr ::chngcnt.  
1a60: 20 20 23 20 69 66 20 7b 24 3a 3a 63 68 6e 67 63    # if {$::chngc
1a70: 6e 74 3d 3d 32 35 31 7d 20 7b 62 74 72 65 65 5f  nt==251} {btree_
1a80: 74 72 65 65 5f 64 75 6d 70 20 24 3a 3a 62 20 33  tree_dump $::b 3
1a90: 7d 20 0a 20 20 20 20 23 20 70 75 74 73 20 22 43  } .    # puts "C
1aa0: 48 41 4e 47 45 20 24 3a 3a 63 68 6e 67 63 6e 74  HANGE $::chngcnt
1ab0: 3a 20 24 6b 20 24 69 6e 73 65 72 74 20 24 6c 6f  : $k $insert $lo
1ac0: 6e 67 6b 65 79 20 24 6c 6f 6e 67 64 61 74 61 22  ngkey $longdata"
1ad0: 0a 20 20 20 20 69 66 20 7b 24 6c 6f 6e 67 6b 65  .    if {$longke
1ae0: 79 7d 20 7b 0a 20 20 20 20 20 20 73 65 74 20 78  y} {.      set x
1af0: 20 5b 65 78 70 72 20 7b 72 61 6e 64 28 29 7d 5d   [expr {rand()}]
1b00: 0a 20 20 20 20 20 20 73 65 74 20 6b 65 79 6c 65  .      set keyle
1b10: 6e 20 5b 65 78 70 72 20 7b 69 6e 74 28 24 78 2a  n [expr {int($x*
1b20: 24 78 2a 24 78 2a 24 78 2a 33 30 30 30 29 2b 31  $x*$x*$x*3000)+1
1b30: 30 7d 5d 0a 20 20 20 20 7d 20 65 6c 73 65 20 7b  0}].    } else {
1b40: 0a 20 20 20 20 20 20 73 65 74 20 6b 65 79 6c 65  .      set keyle
1b50: 6e 20 24 4c 0a 20 20 20 20 7d 0a 20 20 20 20 73  n $L.    }.    s
1b60: 65 74 20 6b 65 79 20 5b 6d 61 6b 65 5f 70 61 79  et key [make_pay
1b70: 6c 6f 61 64 20 24 6b 20 24 4c 20 24 6b 65 79 6c  load $k $L $keyl
1b80: 65 6e 5d 0a 20 20 20 20 69 66 20 7b 24 6c 6f 6e  en].    if {$lon
1b90: 67 64 61 74 61 7d 20 7b 0a 20 20 20 20 20 20 73  gdata} {.      s
1ba0: 65 74 20 78 20 5b 65 78 70 72 20 7b 72 61 6e 64  et x [expr {rand
1bb0: 28 29 7d 5d 0a 20 20 20 20 20 20 73 65 74 20 64  ()}].      set d
1bc0: 61 74 61 6c 65 6e 20 5b 65 78 70 72 20 7b 69 6e  atalen [expr {in
1bd0: 74 28 24 78 2a 24 78 2a 24 78 2a 24 78 2a 33 30  t($x*$x*$x*$x*30
1be0: 30 30 29 2b 31 30 7d 5d 0a 20 20 20 20 7d 20 65  00)+10}].    } e
1bf0: 6c 73 65 20 7b 0a 20 20 20 20 20 20 73 65 74 20  lse {.      set 
1c00: 64 61 74 61 6c 65 6e 20 24 4c 0a 20 20 20 20 7d  datalen $L.    }
1c10: 0a 20 20 20 20 73 65 74 20 64 61 74 61 20 5b 6d  .    set data [m
1c20: 61 6b 65 5f 70 61 79 6c 6f 61 64 20 24 6b 20 24  ake_payload $k $
1c30: 4c 20 24 64 61 74 61 6c 65 6e 5d 0a 20 20 20 20  L $datalen].    
1c40: 73 65 74 20 62 61 73 65 6b 65 79 20 5b 66 6f 72  set basekey [for
1c50: 6d 61 74 20 24 66 6f 72 6d 61 74 20 24 6b 5d 0a  mat $format $k].
1c60: 20 20 20 20 69 66 20 7b 5b 73 65 74 20 63 20 5b      if {[set c [
1c70: 62 74 72 65 65 5f 6d 6f 76 65 5f 74 6f 20 24 3a  btree_move_to $:
1c80: 3a 63 33 20 24 62 61 73 65 6b 65 79 5d 5d 3d 3d  :c3 $basekey]]==
1c90: 30 7d 20 7b 0a 20 20 20 20 20 20 62 74 72 65 65  0} {.      btree
1ca0: 5f 64 65 6c 65 74 65 20 24 3a 3a 63 33 0a 20 20  _delete $::c3.  
1cb0: 20 20 7d 20 65 6c 73 65 20 7b 0a 20 20 20 20 20    } else {.     
1cc0: 20 69 66 20 7b 24 63 3c 30 7d 20 7b 62 74 72 65   if {$c<0} {btre
1cd0: 65 5f 6e 65 78 74 20 24 3a 3a 63 33 7d 0a 20 20  e_next $::c3}.  
1ce0: 20 20 20 20 69 66 20 7b 5b 73 74 72 69 6e 67 20      if {[string 
1cf0: 6d 61 74 63 68 20 24 62 61 73 65 6b 65 79 2a 20  match $basekey* 
1d00: 5b 62 74 72 65 65 5f 6b 65 79 20 24 3a 3a 63 33  [btree_key $::c3
1d10: 5d 5d 7d 20 7b 0a 20 20 20 20 20 20 20 20 62 74  ]]} {.        bt
1d20: 72 65 65 5f 64 65 6c 65 74 65 20 24 3a 3a 63 33  ree_delete $::c3
1d30: 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 7d 0a 20  .      }.    }. 
1d40: 20 20 20 69 66 20 7b 5b 73 65 74 20 63 20 5b 62     if {[set c [b
1d50: 74 72 65 65 5f 6d 6f 76 65 5f 74 6f 20 24 3a 3a  tree_move_to $::
1d60: 63 34 20 24 62 61 73 65 6b 65 79 5d 5d 3d 3d 30  c4 $basekey]]==0
1d70: 7d 20 7b 0a 20 20 20 20 20 20 62 74 72 65 65 5f  } {.      btree_
1d80: 64 65 6c 65 74 65 20 24 3a 3a 63 34 0a 20 20 20  delete $::c4.   
1d90: 20 7d 20 65 6c 73 65 20 7b 0a 20 20 20 20 20 20   } else {.      
1da0: 69 66 20 7b 24 63 3c 30 7d 20 7b 62 74 72 65 65  if {$c<0} {btree
1db0: 5f 6e 65 78 74 20 24 3a 3a 63 34 7d 0a 20 20 20  _next $::c4}.   
1dc0: 20 20 20 69 66 20 7b 5b 73 74 72 69 6e 67 20 6d     if {[string m
1dd0: 61 74 63 68 20 24 62 61 73 65 6b 65 79 2a 20 5b  atch $basekey* [
1de0: 62 74 72 65 65 5f 6b 65 79 20 24 3a 3a 63 34 5d  btree_key $::c4]
1df0: 5d 7d 20 7b 0a 20 20 20 20 20 20 20 20 62 74 72  ]} {.        btr
1e00: 65 65 5f 64 65 6c 65 74 65 20 24 3a 3a 63 34 0a  ee_delete $::c4.
1e10: 20 20 20 20 20 20 7d 0a 20 20 20 20 7d 0a 20 20        }.    }.  
1e20: 20 20 69 66 20 7b 5b 73 63 61 6e 20 5b 62 74 72    if {[scan [btr
1e30: 65 65 5f 6b 65 79 20 24 3a 3a 63 34 5d 20 25 64  ee_key $::c4] %d
1e40: 20 6b 78 5d 3c 31 7d 20 7b 73 65 74 20 6b 78 20   kx]<1} {set kx 
1e50: 2d 31 7d 0a 20 20 20 20 69 66 20 7b 24 6b 78 3d  -1}.    if {$kx=
1e60: 3d 24 6b 7d 20 7b 0a 20 20 20 20 20 20 62 74 72  =$k} {.      btr
1e70: 65 65 5f 64 65 6c 65 74 65 20 24 3a 3a 63 34 0a  ee_delete $::c4.
1e80: 20 20 20 20 7d 0a 20 20 20 20 69 66 20 7b 24 69      }.    if {$i
1e90: 6e 73 65 72 74 7d 20 7b 0a 20 20 20 20 20 20 62  nsert} {.      b
1ea0: 74 72 65 65 5f 69 6e 73 65 72 74 20 24 3a 3a 63  tree_insert $::c
1eb0: 33 20 24 6b 65 79 20 24 64 61 74 61 0a 20 20 20  3 $key $data.   
1ec0: 20 7d 20 65 6c 73 65 20 7b 0a 20 20 20 20 20 20   } else {.      
1ed0: 62 74 72 65 65 5f 69 6e 73 65 72 74 20 24 3a 3a  btree_insert $::
1ee0: 63 34 20 24 6b 65 79 20 24 64 61 74 61 0a 20 20  c4 $key $data.  
1ef0: 20 20 7d 0a 20 20 20 20 69 66 20 7b 24 6c 6f 6e    }.    if {$lon
1f00: 67 6b 65 79 7d 20 7b 0a 20 20 20 20 20 20 62 74  gkey} {.      bt
1f10: 72 65 65 5f 69 6e 73 65 72 74 20 24 3a 3a 63 35  ree_insert $::c5
1f20: 20 24 62 61 73 65 6b 65 79 20 24 6b 65 79 6c 65   $basekey $keyle
1f30: 6e 0a 20 20 20 20 7d 20 65 6c 73 65 69 66 20 7b  n.    } elseif {
1f40: 5b 62 74 72 65 65 5f 6d 6f 76 65 5f 74 6f 20 24  [btree_move_to $
1f50: 3a 3a 63 35 20 24 62 61 73 65 6b 65 79 5d 3d 3d  ::c5 $basekey]==
1f60: 30 7d 20 7b 0a 20 20 20 20 20 20 62 74 72 65 65  0} {.      btree
1f70: 5f 64 65 6c 65 74 65 20 24 3a 3a 63 35 0a 20 20  _delete $::c5.  
1f80: 20 20 7d 0a 20 20 20 20 69 66 20 7b 24 6c 6f 6e    }.    if {$lon
1f90: 67 64 61 74 61 7d 20 7b 0a 20 20 20 20 20 20 62  gdata} {.      b
1fa0: 74 72 65 65 5f 69 6e 73 65 72 74 20 24 3a 3a 63  tree_insert $::c
1fb0: 36 20 24 62 61 73 65 6b 65 79 20 24 64 61 74 61  6 $basekey $data
1fc0: 6c 65 6e 0a 20 20 20 20 7d 20 65 6c 73 65 69 66  len.    } elseif
1fd0: 20 7b 5b 62 74 72 65 65 5f 6d 6f 76 65 5f 74 6f   {[btree_move_to
1fe0: 20 24 3a 3a 63 36 20 24 62 61 73 65 6b 65 79 5d   $::c6 $basekey]
1ff0: 3d 3d 30 7d 20 7b 0a 20 20 20 20 20 20 62 74 72  ==0} {.      btr
2000: 65 65 5f 64 65 6c 65 74 65 20 24 3a 3a 63 36 0a  ee_delete $::c6.
2010: 20 20 20 20 7d 0a 20 20 20 20 23 20 73 65 74 20      }.    # set 
2020: 63 6b 20 5b 62 74 72 65 65 5f 69 6e 74 65 67 72  ck [btree_integr
2030: 69 74 79 5f 63 68 65 63 6b 20 24 3a 3a 62 20 32  ity_check $::b 2
2040: 20 33 20 34 20 35 20 36 5d 0a 20 20 20 20 23 20   3 4 5 6].    # 
2050: 69 66 20 7b 24 63 6b 21 3d 22 22 7d 20 7b 0a 20  if {$ck!=""} {. 
2060: 20 20 20 23 20 20 20 70 75 74 73 20 22 5c 6e 53     #   puts "\nS
2070: 41 4e 49 54 59 20 43 48 45 43 4b 20 46 41 49 4c  ANITY CHECK FAIL
2080: 45 44 21 5c 6e 24 63 6b 22 0a 20 20 20 20 23 20  ED!\n$ck".    # 
2090: 20 20 65 78 69 74 0a 20 20 20 20 23 20 7d 0a 20    exit.    # }. 
20a0: 20 20 20 23 20 70 75 74 73 20 22 50 41 47 45 20     # puts "PAGE 
20b0: 33 3a 22 3b 20 62 74 72 65 65 5f 70 61 67 65 5f  3:"; btree_page_
20c0: 64 75 6d 70 20 24 3a 3a 62 20 33 0a 20 20 20 20  dump $::b 3.    
20d0: 23 20 70 75 74 73 20 22 50 41 47 45 20 34 3a 22  # puts "PAGE 4:"
20e0: 3b 20 62 74 72 65 65 5f 70 61 67 65 5f 64 75 6d  ; btree_page_dum
20f0: 70 20 24 3a 3a 62 20 34 0a 20 20 7d 0a 7d 0a 0a  p $::b 4.  }.}..
2100: 23 20 52 65 70 65 61 74 20 74 68 69 73 20 74 65  # Repeat this te
2110: 73 74 20 73 65 71 75 65 6e 63 65 20 6f 6e 20 64  st sequence on d
2120: 61 74 61 62 61 73 65 20 6f 66 20 76 61 72 69 6f  atabase of vario
2130: 75 73 20 73 69 7a 65 73 0a 23 0a 73 65 74 20 74  us sizes.#.set t
2140: 65 73 74 6e 6f 20 32 0a 66 6f 72 65 61 63 68 20  estno 2.foreach 
2150: 7b 4e 20 4c 7d 20 7b 0a 20 20 31 30 20 32 0a 20  {N L} {.  10 2. 
2160: 20 35 30 20 32 0a 20 20 32 30 30 20 33 0a 20 20   50 2.  200 3.  
2170: 32 30 30 30 20 35 0a 7d 20 7b 0a 20 20 70 75 74  2000 5.} {.  put
2180: 73 20 22 2a 2a 2a 2a 20 4e 3d 24 4e 20 4c 3d 24  s "**** N=$N L=$
2190: 4c 20 2a 2a 2a 2a 22 0a 20 20 73 65 74 20 68 61  L ****".  set ha
21a0: 73 68 20 5b 6d 64 35 66 69 6c 65 20 74 65 73 74  sh [md5file test
21b0: 32 2e 62 74 5d 0a 20 20 64 6f 5f 74 65 73 74 20  2.bt].  do_test 
21c0: 62 74 72 65 65 32 2d 24 74 65 73 74 6e 6f 2e 31  btree2-$testno.1
21d0: 20 5b 73 75 62 73 74 20 2d 6e 6f 63 6f 6d 6d 61   [subst -nocomma
21e0: 6e 64 73 20 7b 0a 20 20 20 20 73 65 74 20 3a 3a  nds {.    set ::
21f0: 63 32 20 5b 62 74 72 65 65 5f 63 75 72 73 6f 72  c2 [btree_cursor
2200: 20 24 3a 3a 62 20 32 20 31 5d 0a 20 20 20 20 73   $::b 2 1].    s
2210: 65 74 20 3a 3a 63 33 20 5b 62 74 72 65 65 5f 63  et ::c3 [btree_c
2220: 75 72 73 6f 72 20 24 3a 3a 62 20 33 20 31 5d 0a  ursor $::b 3 1].
2230: 20 20 20 20 73 65 74 20 3a 3a 63 34 20 5b 62 74      set ::c4 [bt
2240: 72 65 65 5f 63 75 72 73 6f 72 20 24 3a 3a 62 20  ree_cursor $::b 
2250: 34 20 31 5d 0a 20 20 20 20 73 65 74 20 3a 3a 63  4 1].    set ::c
2260: 35 20 5b 62 74 72 65 65 5f 63 75 72 73 6f 72 20  5 [btree_cursor 
2270: 24 3a 3a 62 20 35 20 31 5d 0a 20 20 20 20 73 65  $::b 5 1].    se
2280: 74 20 3a 3a 63 36 20 5b 62 74 72 65 65 5f 63 75  t ::c6 [btree_cu
2290: 72 73 6f 72 20 24 3a 3a 62 20 36 20 31 5d 0a 20  rsor $::b 6 1]. 
22a0: 20 20 20 62 74 72 65 65 5f 62 65 67 69 6e 5f 74     btree_begin_t
22b0: 72 61 6e 73 61 63 74 69 6f 6e 20 24 3a 3a 62 0a  ransaction $::b.
22c0: 20 20 20 20 62 75 69 6c 64 5f 64 62 20 24 4e 20      build_db $N 
22d0: 24 4c 0a 20 20 20 20 63 68 65 63 6b 5f 69 6e 76  $L.    check_inv
22e0: 61 72 69 61 6e 74 73 0a 20 20 7d 5d 20 7b 7d 0a  ariants.  }] {}.
22f0: 20 20 64 6f 5f 74 65 73 74 20 62 74 72 65 65 32    do_test btree2
2300: 2d 24 74 65 73 74 6e 6f 2e 32 20 7b 0a 20 20 20  -$testno.2 {.   
2310: 20 62 74 72 65 65 5f 63 6c 6f 73 65 5f 63 75 72   btree_close_cur
2320: 73 6f 72 20 24 3a 3a 63 32 0a 20 20 20 20 62 74  sor $::c2.    bt
2330: 72 65 65 5f 63 6c 6f 73 65 5f 63 75 72 73 6f 72  ree_close_cursor
2340: 20 24 3a 3a 63 33 0a 20 20 20 20 62 74 72 65 65   $::c3.    btree
2350: 5f 63 6c 6f 73 65 5f 63 75 72 73 6f 72 20 24 3a  _close_cursor $:
2360: 3a 63 34 0a 20 20 20 20 62 74 72 65 65 5f 63 6c  :c4.    btree_cl
2370: 6f 73 65 5f 63 75 72 73 6f 72 20 24 3a 3a 63 35  ose_cursor $::c5
2380: 0a 20 20 20 20 62 74 72 65 65 5f 63 6c 6f 73 65  .    btree_close
2390: 5f 63 75 72 73 6f 72 20 24 3a 3a 63 36 0a 20 20  _cursor $::c6.  
23a0: 20 20 62 74 72 65 65 5f 72 6f 6c 6c 62 61 63 6b    btree_rollback
23b0: 20 24 3a 3a 62 0a 20 20 20 20 6d 64 35 66 69 6c   $::b.    md5fil
23c0: 65 20 74 65 73 74 32 2e 62 74 0a 20 20 7d 20 24  e test2.bt.  } $
23d0: 68 61 73 68 0a 20 20 64 6f 5f 74 65 73 74 20 62  hash.  do_test b
23e0: 74 72 65 65 32 2d 24 74 65 73 74 6e 6f 2e 33 20  tree2-$testno.3 
23f0: 5b 73 75 62 73 74 20 2d 6e 6f 63 6f 6d 6d 61 6e  [subst -nocomman
2400: 64 73 20 7b 0a 20 20 20 20 62 74 72 65 65 5f 62  ds {.    btree_b
2410: 65 67 69 6e 5f 74 72 61 6e 73 61 63 74 69 6f 6e  egin_transaction
2420: 20 24 3a 3a 62 0a 20 20 20 20 73 65 74 20 3a 3a   $::b.    set ::
2430: 63 32 20 5b 62 74 72 65 65 5f 63 75 72 73 6f 72  c2 [btree_cursor
2440: 20 24 3a 3a 62 20 32 20 31 5d 0a 20 20 20 20 73   $::b 2 1].    s
2450: 65 74 20 3a 3a 63 33 20 5b 62 74 72 65 65 5f 63  et ::c3 [btree_c
2460: 75 72 73 6f 72 20 24 3a 3a 62 20 33 20 31 5d 0a  ursor $::b 3 1].
2470: 20 20 20 20 73 65 74 20 3a 3a 63 34 20 5b 62 74      set ::c4 [bt
2480: 72 65 65 5f 63 75 72 73 6f 72 20 24 3a 3a 62 20  ree_cursor $::b 
2490: 34 20 31 5d 0a 20 20 20 20 73 65 74 20 3a 3a 63  4 1].    set ::c
24a0: 35 20 5b 62 74 72 65 65 5f 63 75 72 73 6f 72 20  5 [btree_cursor 
24b0: 24 3a 3a 62 20 35 20 31 5d 0a 20 20 20 20 73 65  $::b 5 1].    se
24c0: 74 20 3a 3a 63 36 20 5b 62 74 72 65 65 5f 63 75  t ::c6 [btree_cu
24d0: 72 73 6f 72 20 24 3a 3a 62 20 36 20 31 5d 0a 20  rsor $::b 6 1]. 
24e0: 20 20 20 62 75 69 6c 64 5f 64 62 20 24 4e 20 24     build_db $N $
24f0: 4c 0a 20 20 20 20 63 68 65 63 6b 5f 69 6e 76 61  L.    check_inva
2500: 72 69 61 6e 74 73 0a 20 20 7d 5d 20 7b 7d 0a 20  riants.  }] {}. 
2510: 20 64 6f 5f 74 65 73 74 20 62 74 72 65 65 32 2d   do_test btree2-
2520: 24 74 65 73 74 6e 6f 2e 34 20 7b 0a 20 20 20 20  $testno.4 {.    
2530: 62 74 72 65 65 5f 63 6f 6d 6d 69 74 20 24 3a 3a  btree_commit $::
2540: 62 0a 20 20 20 20 63 68 65 63 6b 5f 69 6e 76 61  b.    check_inva
2550: 72 69 61 6e 74 73 0a 20 20 7d 20 7b 7d 0a 20 20  riants.  } {}.  
2560: 64 6f 5f 74 65 73 74 20 62 74 72 65 65 32 2d 24  do_test btree2-$
2570: 74 65 73 74 6e 6f 2e 35 20 20 7b 0a 20 20 20 20  testno.5  {.    
2580: 6c 69 6e 64 65 78 20 5b 62 74 72 65 65 5f 70 61  lindex [btree_pa
2590: 67 65 72 5f 73 74 61 74 73 20 24 3a 3a 62 5d 20  ger_stats $::b] 
25a0: 31 0a 20 20 7d 20 7b 36 7d 0a 20 20 64 6f 5f 74  1.  } {6}.  do_t
25b0: 65 73 74 20 62 74 72 65 65 32 2d 24 74 65 73 74  est btree2-$test
25c0: 6e 6f 2e 36 20 20 7b 0a 20 20 20 20 62 74 72 65  no.6  {.    btre
25d0: 65 5f 63 6c 6f 73 65 5f 63 75 72 73 6f 72 20 24  e_close_cursor $
25e0: 3a 3a 63 32 0a 20 20 20 20 62 74 72 65 65 5f 63  ::c2.    btree_c
25f0: 6c 6f 73 65 5f 63 75 72 73 6f 72 20 24 3a 3a 63  lose_cursor $::c
2600: 33 0a 20 20 20 20 62 74 72 65 65 5f 63 6c 6f 73  3.    btree_clos
2610: 65 5f 63 75 72 73 6f 72 20 24 3a 3a 63 34 0a 20  e_cursor $::c4. 
2620: 20 20 20 62 74 72 65 65 5f 63 6c 6f 73 65 5f 63     btree_close_c
2630: 75 72 73 6f 72 20 24 3a 3a 63 35 0a 20 20 20 20  ursor $::c5.    
2640: 62 74 72 65 65 5f 63 6c 6f 73 65 5f 63 75 72 73  btree_close_curs
2650: 6f 72 20 24 3a 3a 63 36 0a 20 20 20 20 6c 69 6e  or $::c6.    lin
2660: 64 65 78 20 5b 62 74 72 65 65 5f 70 61 67 65 72  dex [btree_pager
2670: 5f 73 74 61 74 73 20 24 3a 3a 62 5d 20 31 0a 20  _stats $::b] 1. 
2680: 20 7d 20 7b 30 7d 0a 20 20 64 6f 5f 74 65 73 74   } {0}.  do_test
2690: 20 62 74 72 65 65 32 2d 24 74 65 73 74 6e 6f 2e   btree2-$testno.
26a0: 37 20 7b 0a 20 20 20 20 62 74 72 65 65 5f 63 6c  7 {.    btree_cl
26b0: 6f 73 65 20 24 3a 3a 62 0a 20 20 7d 20 7b 7d 0a  ose $::b.  } {}.
26c0: 61 66 74 65 72 20 31 30 30 0a 20 20 23 20 46 6f  after 100.  # Fo
26d0: 72 20 65 61 63 68 20 64 61 74 61 62 61 73 65 20  r each database 
26e0: 73 69 7a 65 2c 20 72 75 6e 20 76 61 72 69 6f 75  size, run variou
26f0: 73 20 63 68 61 6e 67 65 73 20 74 65 73 74 73 2e  s changes tests.
2700: 0a 20 20 23 0a 20 20 73 65 74 20 6e 75 6d 32 20  .  #.  set num2 
2710: 31 0a 20 20 66 6f 72 65 61 63 68 20 7b 6e 20 49  1.  foreach {n I
2720: 20 4b 20 44 7d 20 7b 0a 20 20 20 20 30 2e 35 20   K D} {.    0.5 
2730: 30 2e 35 20 30 2e 31 20 30 2e 31 0a 20 20 20 20  0.5 0.1 0.1.    
2740: 31 2e 30 20 30 2e 32 20 30 2e 31 20 30 2e 31 0a  1.0 0.2 0.1 0.1.
2750: 20 20 20 20 31 2e 30 20 30 2e 38 20 30 2e 31 20      1.0 0.8 0.1 
2760: 30 2e 31 0a 20 20 20 20 32 2e 30 20 30 2e 30 20  0.1.    2.0 0.0 
2770: 30 2e 31 20 30 2e 31 0a 20 20 20 20 32 2e 30 20  0.1 0.1.    2.0 
2780: 31 2e 30 20 30 2e 31 20 30 2e 31 0a 20 20 20 20  1.0 0.1 0.1.    
2790: 32 2e 30 20 30 2e 30 20 30 2e 30 20 30 2e 30 0a  2.0 0.0 0.0 0.0.
27a0: 20 20 20 20 32 2e 30 20 31 2e 30 20 30 2e 30 20      2.0 1.0 0.0 
27b0: 30 2e 30 0a 20 20 7d 20 7b 0a 20 20 20 20 73 65  0.0.  } {.    se
27c0: 74 20 74 65 73 74 69 64 20 62 74 72 65 65 32 2d  t testid btree2-
27d0: 24 74 65 73 74 6e 6f 2e 38 2e 24 6e 75 6d 32 0a  $testno.8.$num2.
27e0: 20 20 20 20 73 65 74 20 68 61 73 68 20 5b 6d 64      set hash [md
27f0: 35 66 69 6c 65 20 74 65 73 74 32 2e 62 74 5d 0a  5file test2.bt].
2800: 20 20 20 20 64 6f 5f 74 65 73 74 20 24 74 65 73      do_test $tes
2810: 74 69 64 2e 30 20 7b 0a 20 20 20 20 20 20 73 65  tid.0 {.      se
2820: 74 20 3a 3a 62 20 5b 62 74 72 65 65 5f 6f 70 65  t ::b [btree_ope
2830: 6e 20 74 65 73 74 32 2e 62 74 5d 0a 20 20 20 20  n test2.bt].    
2840: 20 20 73 65 74 20 3a 3a 63 32 20 5b 62 74 72 65    set ::c2 [btre
2850: 65 5f 63 75 72 73 6f 72 20 24 3a 3a 62 20 32 20  e_cursor $::b 2 
2860: 31 5d 0a 20 20 20 20 20 20 73 65 74 20 3a 3a 63  1].      set ::c
2870: 33 20 5b 62 74 72 65 65 5f 63 75 72 73 6f 72 20  3 [btree_cursor 
2880: 24 3a 3a 62 20 33 20 31 5d 0a 20 20 20 20 20 20  $::b 3 1].      
2890: 73 65 74 20 3a 3a 63 34 20 5b 62 74 72 65 65 5f  set ::c4 [btree_
28a0: 63 75 72 73 6f 72 20 24 3a 3a 62 20 34 20 31 5d  cursor $::b 4 1]
28b0: 0a 20 20 20 20 20 20 73 65 74 20 3a 3a 63 35 20  .      set ::c5 
28c0: 5b 62 74 72 65 65 5f 63 75 72 73 6f 72 20 24 3a  [btree_cursor $:
28d0: 3a 62 20 35 20 31 5d 0a 20 20 20 20 20 20 73 65  :b 5 1].      se
28e0: 74 20 3a 3a 63 36 20 5b 62 74 72 65 65 5f 63 75  t ::c6 [btree_cu
28f0: 72 73 6f 72 20 24 3a 3a 62 20 36 20 31 5d 0a 20  rsor $::b 6 1]. 
2900: 20 20 20 20 20 63 68 65 63 6b 5f 69 6e 76 61 72       check_invar
2910: 69 61 6e 74 73 0a 20 20 20 20 7d 20 7b 7d 0a 20  iants.    } {}. 
2920: 20 20 20 73 65 74 20 63 6e 74 20 36 0a 20 20 20     set cnt 6.   
2930: 20 66 6f 72 20 7b 73 65 74 20 69 20 32 7d 20 7b   for {set i 2} {
2940: 24 69 3c 3d 36 7d 20 7b 69 6e 63 72 20 69 7d 20  $i<=6} {incr i} 
2950: 7b 0a 20 20 20 20 20 20 69 66 20 7b 5b 6c 69 6e  {.      if {[lin
2960: 64 65 78 20 5b 62 74 72 65 65 5f 63 75 72 73 6f  dex [btree_curso
2970: 72 5f 64 75 6d 70 20 5b 73 65 74 20 3a 3a 63 24  r_dump [set ::c$
2980: 69 5d 5d 20 30 5d 21 3d 24 69 7d 20 7b 69 6e 63  i]] 0]!=$i} {inc
2990: 72 20 63 6e 74 7d 0a 20 20 20 20 7d 0a 20 20 20  r cnt}.    }.   
29a0: 20 64 6f 5f 74 65 73 74 20 24 74 65 73 74 69 64   do_test $testid
29b0: 2e 31 20 7b 0a 20 20 20 20 20 20 62 74 72 65 65  .1 {.      btree
29c0: 5f 62 65 67 69 6e 5f 74 72 61 6e 73 61 63 74 69  _begin_transacti
29d0: 6f 6e 20 24 3a 3a 62 0a 20 20 20 20 20 20 6c 69  on $::b.      li
29e0: 6e 64 65 78 20 5b 62 74 72 65 65 5f 70 61 67 65  ndex [btree_page
29f0: 72 5f 73 74 61 74 73 20 24 3a 3a 62 5d 20 31 0a  r_stats $::b] 1.
2a00: 20 20 20 20 7d 20 24 63 6e 74 0a 20 20 20 20 23      } $cnt.    #
2a10: 20 65 78 65 63 20 63 70 20 74 65 73 74 32 2e 62   exec cp test2.b
2a20: 74 20 74 65 73 74 32 2e 62 74 2e 62 75 31 0a 20  t test2.bt.bu1. 
2a30: 20 20 20 64 6f 5f 74 65 73 74 20 24 74 65 73 74     do_test $test
2a40: 69 64 2e 32 20 5b 73 75 62 73 74 20 7b 0a 20 20  id.2 [subst {.  
2a50: 20 20 20 20 72 61 6e 64 6f 6d 5f 63 68 61 6e 67      random_chang
2a60: 65 73 20 24 6e 20 24 49 20 24 4b 20 24 44 0a 20  es $n $I $K $D. 
2a70: 20 20 20 7d 5d 20 7b 7d 0a 20 20 20 20 64 6f 5f     }] {}.    do_
2a80: 74 65 73 74 20 24 74 65 73 74 69 64 2e 33 20 7b  test $testid.3 {
2a90: 0a 20 20 20 20 20 20 63 68 65 63 6b 5f 69 6e 76  .      check_inv
2aa0: 61 72 69 61 6e 74 73 0a 20 20 20 20 7d 20 7b 7d  ariants.    } {}
2ab0: 0a 20 20 20 20 64 6f 5f 74 65 73 74 20 24 74 65  .    do_test $te
2ac0: 73 74 69 64 2e 34 20 7b 0a 20 20 20 20 20 20 62  stid.4 {.      b
2ad0: 74 72 65 65 5f 63 6c 6f 73 65 5f 63 75 72 73 6f  tree_close_curso
2ae0: 72 20 24 3a 3a 63 32 0a 20 20 20 20 20 20 62 74  r $::c2.      bt
2af0: 72 65 65 5f 63 6c 6f 73 65 5f 63 75 72 73 6f 72  ree_close_cursor
2b00: 20 24 3a 3a 63 33 0a 20 20 20 20 20 20 62 74 72   $::c3.      btr
2b10: 65 65 5f 63 6c 6f 73 65 5f 63 75 72 73 6f 72 20  ee_close_cursor 
2b20: 24 3a 3a 63 34 0a 20 20 20 20 20 20 62 74 72 65  $::c4.      btre
2b30: 65 5f 63 6c 6f 73 65 5f 63 75 72 73 6f 72 20 24  e_close_cursor $
2b40: 3a 3a 63 35 0a 20 20 20 20 20 20 62 74 72 65 65  ::c5.      btree
2b50: 5f 63 6c 6f 73 65 5f 63 75 72 73 6f 72 20 24 3a  _close_cursor $:
2b60: 3a 63 36 0a 20 20 20 20 20 20 62 74 72 65 65 5f  :c6.      btree_
2b70: 72 6f 6c 6c 62 61 63 6b 20 24 3a 3a 62 0a 20 20  rollback $::b.  
2b80: 20 20 20 20 6d 64 35 66 69 6c 65 20 74 65 73 74      md5file test
2b90: 32 2e 62 74 0a 20 20 20 20 7d 20 24 68 61 73 68  2.bt.    } $hash
2ba0: 0a 20 20 20 20 23 20 65 78 65 63 20 63 70 20 74  .    # exec cp t
2bb0: 65 73 74 32 2e 62 74 20 74 65 73 74 32 2e 62 74  est2.bt test2.bt
2bc0: 2e 62 75 32 0a 20 20 20 20 62 74 72 65 65 5f 62  .bu2.    btree_b
2bd0: 65 67 69 6e 5f 74 72 61 6e 73 61 63 74 69 6f 6e  egin_transaction
2be0: 20 24 3a 3a 62 0a 20 20 20 20 73 65 74 20 3a 3a   $::b.    set ::
2bf0: 63 32 20 5b 62 74 72 65 65 5f 63 75 72 73 6f 72  c2 [btree_cursor
2c00: 20 24 3a 3a 62 20 32 20 31 5d 0a 20 20 20 20 73   $::b 2 1].    s
2c10: 65 74 20 3a 3a 63 33 20 5b 62 74 72 65 65 5f 63  et ::c3 [btree_c
2c20: 75 72 73 6f 72 20 24 3a 3a 62 20 33 20 31 5d 0a  ursor $::b 3 1].
2c30: 20 20 20 20 73 65 74 20 3a 3a 63 34 20 5b 62 74      set ::c4 [bt
2c40: 72 65 65 5f 63 75 72 73 6f 72 20 24 3a 3a 62 20  ree_cursor $::b 
2c50: 34 20 31 5d 0a 20 20 20 20 73 65 74 20 3a 3a 63  4 1].    set ::c
2c60: 35 20 5b 62 74 72 65 65 5f 63 75 72 73 6f 72 20  5 [btree_cursor 
2c70: 24 3a 3a 62 20 35 20 31 5d 0a 20 20 20 20 73 65  $::b 5 1].    se
2c80: 74 20 3a 3a 63 36 20 5b 62 74 72 65 65 5f 63 75  t ::c6 [btree_cu
2c90: 72 73 6f 72 20 24 3a 3a 62 20 36 20 31 5d 0a 20  rsor $::b 6 1]. 
2ca0: 20 20 20 64 6f 5f 74 65 73 74 20 24 74 65 73 74     do_test $test
2cb0: 69 64 2e 35 20 5b 73 75 62 73 74 20 7b 0a 20 20  id.5 [subst {.  
2cc0: 20 20 20 20 72 61 6e 64 6f 6d 5f 63 68 61 6e 67      random_chang
2cd0: 65 73 20 24 6e 20 24 49 20 24 4b 20 24 44 0a 20  es $n $I $K $D. 
2ce0: 20 20 20 7d 5d 20 7b 7d 0a 20 20 20 20 64 6f 5f     }] {}.    do_
2cf0: 74 65 73 74 20 24 74 65 73 74 69 64 2e 36 20 7b  test $testid.6 {
2d00: 0a 20 20 20 20 20 20 63 68 65 63 6b 5f 69 6e 76  .      check_inv
2d10: 61 72 69 61 6e 74 73 0a 20 20 20 20 7d 20 7b 7d  ariants.    } {}
2d20: 0a 20 20 20 20 64 6f 5f 74 65 73 74 20 24 74 65  .    do_test $te
2d30: 73 74 69 64 2e 37 20 7b 0a 20 20 20 20 20 20 62  stid.7 {.      b
2d40: 74 72 65 65 5f 63 6f 6d 6d 69 74 20 24 3a 3a 62  tree_commit $::b
2d50: 0a 20 20 20 20 20 20 63 68 65 63 6b 5f 69 6e 76  .      check_inv
2d60: 61 72 69 61 6e 74 73 0a 20 20 20 20 7d 20 7b 7d  ariants.    } {}
2d70: 0a 20 20 20 20 73 65 74 20 68 61 73 68 20 5b 6d  .    set hash [m
2d80: 64 35 66 69 6c 65 20 74 65 73 74 32 2e 62 74 5d  d5file test2.bt]
2d90: 0a 20 20 20 20 64 6f 5f 74 65 73 74 20 24 74 65  .    do_test $te
2da0: 73 74 69 64 2e 38 20 7b 0a 20 20 20 20 20 20 62  stid.8 {.      b
2db0: 74 72 65 65 5f 63 6c 6f 73 65 5f 63 75 72 73 6f  tree_close_curso
2dc0: 72 20 24 3a 3a 63 32 0a 20 20 20 20 20 20 62 74  r $::c2.      bt
2dd0: 72 65 65 5f 63 6c 6f 73 65 5f 63 75 72 73 6f 72  ree_close_cursor
2de0: 20 24 3a 3a 63 33 0a 20 20 20 20 20 20 62 74 72   $::c3.      btr
2df0: 65 65 5f 63 6c 6f 73 65 5f 63 75 72 73 6f 72 20  ee_close_cursor 
2e00: 24 3a 3a 63 34 0a 20 20 20 20 20 20 62 74 72 65  $::c4.      btre
2e10: 65 5f 63 6c 6f 73 65 5f 63 75 72 73 6f 72 20 24  e_close_cursor $
2e20: 3a 3a 63 35 0a 20 20 20 20 20 20 62 74 72 65 65  ::c5.      btree
2e30: 5f 63 6c 6f 73 65 5f 63 75 72 73 6f 72 20 24 3a  _close_cursor $:
2e40: 3a 63 36 0a 20 20 20 20 20 20 6c 69 6e 64 65 78  :c6.      lindex
2e50: 20 5b 62 74 72 65 65 5f 70 61 67 65 72 5f 73 74   [btree_pager_st
2e60: 61 74 73 20 24 3a 3a 62 5d 20 31 0a 20 20 20 20  ats $::b] 1.    
2e70: 7d 20 7b 30 7d 0a 20 20 20 20 64 6f 5f 74 65 73  } {0}.    do_tes
2e80: 74 20 24 74 65 73 74 69 64 2e 39 20 7b 0a 20 20  t $testid.9 {.  
2e90: 20 20 20 20 62 74 72 65 65 5f 63 6c 6f 73 65 20      btree_close 
2ea0: 24 3a 3a 62 0a 20 20 20 20 20 20 73 65 74 20 3a  $::b.      set :
2eb0: 3a 62 20 5b 62 74 72 65 65 5f 6f 70 65 6e 20 74  :b [btree_open t
2ec0: 65 73 74 32 2e 62 74 5d 0a 20 20 20 20 20 20 73  est2.bt].      s
2ed0: 65 74 20 3a 3a 63 32 20 5b 62 74 72 65 65 5f 63  et ::c2 [btree_c
2ee0: 75 72 73 6f 72 20 24 3a 3a 62 20 32 20 31 5d 0a  ursor $::b 2 1].
2ef0: 20 20 20 20 20 20 73 65 74 20 3a 3a 63 33 20 5b        set ::c3 [
2f00: 62 74 72 65 65 5f 63 75 72 73 6f 72 20 24 3a 3a  btree_cursor $::
2f10: 62 20 33 20 31 5d 0a 20 20 20 20 20 20 73 65 74  b 3 1].      set
2f20: 20 3a 3a 63 34 20 5b 62 74 72 65 65 5f 63 75 72   ::c4 [btree_cur
2f30: 73 6f 72 20 24 3a 3a 62 20 34 20 31 5d 0a 20 20  sor $::b 4 1].  
2f40: 20 20 20 20 73 65 74 20 3a 3a 63 35 20 5b 62 74      set ::c5 [bt
2f50: 72 65 65 5f 63 75 72 73 6f 72 20 24 3a 3a 62 20  ree_cursor $::b 
2f60: 35 20 31 5d 0a 20 20 20 20 20 20 73 65 74 20 3a  5 1].      set :
2f70: 3a 63 36 20 5b 62 74 72 65 65 5f 63 75 72 73 6f  :c6 [btree_curso
2f80: 72 20 24 3a 3a 62 20 36 20 31 5d 0a 20 20 20 20  r $::b 6 1].    
2f90: 20 20 63 68 65 63 6b 5f 69 6e 76 61 72 69 61 6e    check_invarian
2fa0: 74 73 0a 20 20 20 20 7d 20 7b 7d 0a 20 20 20 20  ts.    } {}.    
2fb0: 64 6f 5f 74 65 73 74 20 24 74 65 73 74 69 64 2e  do_test $testid.
2fc0: 31 30 20 7b 0a 20 20 20 20 20 20 62 74 72 65 65  10 {.      btree
2fd0: 5f 63 6c 6f 73 65 5f 63 75 72 73 6f 72 20 24 3a  _close_cursor $:
2fe0: 3a 63 32 0a 20 20 20 20 20 20 62 74 72 65 65 5f  :c2.      btree_
2ff0: 63 6c 6f 73 65 5f 63 75 72 73 6f 72 20 24 3a 3a  close_cursor $::
3000: 63 33 0a 20 20 20 20 20 20 62 74 72 65 65 5f 63  c3.      btree_c
3010: 6c 6f 73 65 5f 63 75 72 73 6f 72 20 24 3a 3a 63  lose_cursor $::c
3020: 34 0a 20 20 20 20 20 20 62 74 72 65 65 5f 63 6c  4.      btree_cl
3030: 6f 73 65 5f 63 75 72 73 6f 72 20 24 3a 3a 63 35  ose_cursor $::c5
3040: 0a 20 20 20 20 20 20 62 74 72 65 65 5f 63 6c 6f  .      btree_clo
3050: 73 65 5f 63 75 72 73 6f 72 20 24 3a 3a 63 36 0a  se_cursor $::c6.
3060: 20 20 20 20 20 20 6c 69 6e 64 65 78 20 5b 62 74        lindex [bt
3070: 72 65 65 5f 70 61 67 65 72 5f 73 74 61 74 73 20  ree_pager_stats 
3080: 24 3a 3a 62 5d 20 31 0a 20 20 20 20 7d 20 7b 30  $::b] 1.    } {0
3090: 7d 0a 20 20 20 20 64 6f 5f 74 65 73 74 20 24 74  }.    do_test $t
30a0: 65 73 74 69 64 2e 31 31 20 7b 0a 20 20 20 20 20  estid.11 {.     
30b0: 20 62 74 72 65 65 5f 63 6c 6f 73 65 20 24 3a 3a   btree_close $::
30c0: 62 0a 20 20 20 20 7d 20 7b 7d 0a 20 20 20 20 69  b.    } {}.    i
30d0: 6e 63 72 20 6e 75 6d 32 0a 20 20 7d 0a 20 20 69  ncr num2.  }.  i
30e0: 6e 63 72 20 74 65 73 74 6e 6f 0a 20 20 73 65 74  ncr testno.  set
30f0: 20 3a 3a 62 20 5b 62 74 72 65 65 5f 6f 70 65 6e   ::b [btree_open
3100: 20 74 65 73 74 32 2e 62 74 5d 0a 7d 20 20 0a 0a   test2.bt].}  ..
3110: 23 20 54 65 73 74 69 6e 67 20 69 73 20 63 6f 6d  # Testing is com
3120: 70 6c 65 74 65 2e 20 20 53 68 75 74 20 65 76 65  plete.  Shut eve
3130: 72 79 74 68 69 6e 67 20 64 6f 77 6e 2e 0a 23 0a  rything down..#.
3140: 64 6f 5f 74 65 73 74 20 62 74 72 65 65 2d 39 39  do_test btree-99
3150: 39 2e 31 20 7b 0a 20 20 6c 69 6e 64 65 78 20 5b  9.1 {.  lindex [
3160: 62 74 72 65 65 5f 70 61 67 65 72 5f 73 74 61 74  btree_pager_stat
3170: 73 20 24 3a 3a 62 5d 20 31 0a 7d 20 7b 30 7d 0a  s $::b] 1.} {0}.
3180: 64 6f 5f 74 65 73 74 20 62 74 72 65 65 2d 39 39  do_test btree-99
3190: 39 2e 32 20 7b 0a 20 20 62 74 72 65 65 5f 63 6c  9.2 {.  btree_cl
31a0: 6f 73 65 20 24 3a 3a 62 0a 7d 20 7b 7d 0a 64 6f  ose $::b.} {}.do
31b0: 5f 74 65 73 74 20 62 74 72 65 65 2d 39 39 39 2e  _test btree-999.
31c0: 33 20 7b 0a 20 20 66 69 6c 65 20 64 65 6c 65 74  3 {.  file delet
31d0: 65 20 2d 66 6f 72 63 65 20 74 65 73 74 32 2e 62  e -force test2.b
31e0: 74 0a 20 20 66 69 6c 65 20 65 78 69 73 74 73 20  t.  file exists 
31f0: 74 65 73 74 32 2e 62 74 2d 6a 6f 75 72 6e 61 6c  test2.bt-journal
3200: 0a 7d 20 7b 30 7d 0a 0a 7d 20 3b 23 20 65 6e 64  .} {0}..} ;# end
3210: 20 69 66 28 20 6e 6f 74 20 6d 65 6d 3a 20 61 6e   if( not mem: an
3220: 64 20 68 61 73 20 70 61 67 65 72 5f 6f 70 65 6e  d has pager_open
3230: 20 63 6f 6d 6d 61 6e 64 20 29 3b 0a 0a 66 69 6e   command );..fin
3240: 69 73 68 5f 74 65 73 74 0a                       ish_test.