/ Hex Artifact Content
Login

Artifact 8d21590c97b6a2c00cce1f78ed5dc5756e835108:


0000: 2f 2a 0a 2a 2a 20 32 30 30 34 20 41 70 72 69 6c  /*.** 2004 April
0010: 20 36 0a 2a 2a 0a 2a 2a 20 54 68 65 20 61 75 74   6.**.** The aut
0020: 68 6f 72 20 64 69 73 63 6c 61 69 6d 73 20 63 6f  hor disclaims co
0030: 70 79 72 69 67 68 74 20 74 6f 20 74 68 69 73 20  pyright to this 
0040: 73 6f 75 72 63 65 20 63 6f 64 65 2e 20 20 49 6e  source code.  In
0050: 20 70 6c 61 63 65 20 6f 66 0a 2a 2a 20 61 20 6c   place of.** a l
0060: 65 67 61 6c 20 6e 6f 74 69 63 65 2c 20 68 65 72  egal notice, her
0070: 65 20 69 73 20 61 20 62 6c 65 73 73 69 6e 67 3a  e is a blessing:
0080: 0a 2a 2a 0a 2a 2a 20 20 20 20 4d 61 79 20 79 6f  .**.**    May yo
0090: 75 20 64 6f 20 67 6f 6f 64 20 61 6e 64 20 6e 6f  u do good and no
00a0: 74 20 65 76 69 6c 2e 0a 2a 2a 20 20 20 20 4d 61  t evil..**    Ma
00b0: 79 20 79 6f 75 20 66 69 6e 64 20 66 6f 72 67 69  y you find forgi
00c0: 76 65 6e 65 73 73 20 66 6f 72 20 79 6f 75 72 73  veness for yours
00d0: 65 6c 66 20 61 6e 64 20 66 6f 72 67 69 76 65 20  elf and forgive 
00e0: 6f 74 68 65 72 73 2e 0a 2a 2a 20 20 20 20 4d 61  others..**    Ma
00f0: 79 20 79 6f 75 20 73 68 61 72 65 20 66 72 65 65  y you share free
0100: 6c 79 2c 20 6e 65 76 65 72 20 74 61 6b 69 6e 67  ly, never taking
0110: 20 6d 6f 72 65 20 74 68 61 6e 20 79 6f 75 20 67   more than you g
0120: 69 76 65 2e 0a 2a 2a 0a 2a 2a 2a 2a 2a 2a 2a 2a  ive..**.********
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 2a 2a 2a 2a 2a 2a 2a  ****************
0170: 2a 0a 2a 2a 20 24 49 64 3a 20 62 74 72 65 65 49  *.** $Id: btreeI
0180: 6e 74 2e 68 2c 76 20 31 2e 33 36 20 32 30 30 38  nt.h,v 1.36 2008
0190: 2f 31 31 2f 31 39 20 31 30 3a 32 32 3a 33 33 20  /11/19 10:22:33 
01a0: 64 61 6e 69 65 6c 6b 31 39 37 37 20 45 78 70 20  danielk1977 Exp 
01b0: 24 0a 2a 2a 0a 2a 2a 20 54 68 69 73 20 66 69 6c  $.**.** This fil
01c0: 65 20 69 6d 70 6c 65 6d 65 6e 74 73 20 61 20 65  e implements a e
01d0: 78 74 65 72 6e 61 6c 20 28 64 69 73 6b 2d 62 61  xternal (disk-ba
01e0: 73 65 64 29 20 64 61 74 61 62 61 73 65 20 75 73  sed) database us
01f0: 69 6e 67 20 42 54 72 65 65 73 2e 0a 2a 2a 20 46  ing BTrees..** F
0200: 6f 72 20 61 20 64 65 74 61 69 6c 65 64 20 64 69  or a detailed di
0210: 73 63 75 73 73 69 6f 6e 20 6f 66 20 42 54 72 65  scussion of BTre
0220: 65 73 2c 20 72 65 66 65 72 20 74 6f 0a 2a 2a 0a  es, refer to.**.
0230: 2a 2a 20 20 20 20 20 44 6f 6e 61 6c 64 20 45 2e  **     Donald E.
0240: 20 4b 6e 75 74 68 2c 20 54 48 45 20 41 52 54 20   Knuth, THE ART 
0250: 4f 46 20 43 4f 4d 50 55 54 45 52 20 50 52 4f 47  OF COMPUTER PROG
0260: 52 41 4d 4d 49 4e 47 2c 20 56 6f 6c 75 6d 65 20  RAMMING, Volume 
0270: 33 3a 0a 2a 2a 20 20 20 20 20 22 53 6f 72 74 69  3:.**     "Sorti
0280: 6e 67 20 41 6e 64 20 53 65 61 72 63 68 69 6e 67  ng And Searching
0290: 22 2c 20 70 61 67 65 73 20 34 37 33 2d 34 38 30  ", pages 473-480
02a0: 2e 20 41 64 64 69 73 6f 6e 2d 57 65 73 6c 65 79  . Addison-Wesley
02b0: 0a 2a 2a 20 20 20 20 20 50 75 62 6c 69 73 68 69  .**     Publishi
02c0: 6e 67 20 43 6f 6d 70 61 6e 79 2c 20 52 65 61 64  ng Company, Read
02d0: 69 6e 67 2c 20 4d 61 73 73 61 63 68 75 73 65 74  ing, Massachuset
02e0: 74 73 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 62 61  ts..**.** The ba
02f0: 73 69 63 20 69 64 65 61 20 69 73 20 74 68 61 74  sic idea is that
0300: 20 65 61 63 68 20 70 61 67 65 20 6f 66 20 74 68   each page of th
0310: 65 20 66 69 6c 65 20 63 6f 6e 74 61 69 6e 73 20  e file contains 
0320: 4e 20 64 61 74 61 62 61 73 65 0a 2a 2a 20 65 6e  N database.** en
0330: 74 72 69 65 73 20 61 6e 64 20 4e 2b 31 20 70 6f  tries and N+1 po
0340: 69 6e 74 65 72 73 20 74 6f 20 73 75 62 70 61 67  inters to subpag
0350: 65 73 2e 0a 2a 2a 0a 2a 2a 20 20 20 2d 2d 2d 2d  es..**.**   ----
0360: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
0370: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
0380: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
0390: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 2a 2a 20  ------------.** 
03a0: 20 20 7c 20 20 50 74 72 28 30 29 20 7c 20 4b 65    |  Ptr(0) | Ke
03b0: 79 28 30 29 20 7c 20 50 74 72 28 31 29 20 7c 20  y(0) | Ptr(1) | 
03c0: 4b 65 79 28 31 29 20 7c 20 2e 2e 2e 20 7c 20 4b  Key(1) | ... | K
03d0: 65 79 28 4e 2d 31 29 20 7c 20 50 74 72 28 4e 29  ey(N-1) | Ptr(N)
03e0: 20 7c 0a 2a 2a 20 20 20 2d 2d 2d 2d 2d 2d 2d 2d   |.**   --------
03f0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
0400: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
0410: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
0420: 2d 2d 2d 2d 2d 2d 2d 2d 0a 2a 2a 0a 2a 2a 20 41  --------.**.** A
0430: 6c 6c 20 6f 66 20 74 68 65 20 6b 65 79 73 20 6f  ll of the keys o
0440: 6e 20 74 68 65 20 70 61 67 65 20 74 68 61 74 20  n the page that 
0450: 50 74 72 28 30 29 20 70 6f 69 6e 74 73 20 74 6f  Ptr(0) points to
0460: 20 68 61 76 65 20 76 61 6c 75 65 73 20 6c 65 73   have values les
0470: 73 0a 2a 2a 20 74 68 61 6e 20 4b 65 79 28 30 29  s.** than Key(0)
0480: 2e 20 20 41 6c 6c 20 6f 66 20 74 68 65 20 6b 65  .  All of the ke
0490: 79 73 20 6f 6e 20 70 61 67 65 20 50 74 72 28 31  ys on page Ptr(1
04a0: 29 20 61 6e 64 20 69 74 73 20 73 75 62 70 61 67  ) and its subpag
04b0: 65 73 20 68 61 76 65 0a 2a 2a 20 76 61 6c 75 65  es have.** value
04c0: 73 20 67 72 65 61 74 65 72 20 74 68 61 6e 20 4b  s greater than K
04d0: 65 79 28 30 29 20 61 6e 64 20 6c 65 73 73 20 74  ey(0) and less t
04e0: 68 61 6e 20 4b 65 79 28 31 29 2e 20 20 41 6c 6c  han Key(1).  All
04f0: 20 6f 66 20 74 68 65 20 6b 65 79 73 0a 2a 2a 20   of the keys.** 
0500: 6f 6e 20 50 74 72 28 4e 29 20 61 6e 64 20 69 74  on Ptr(N) and it
0510: 73 20 73 75 62 70 61 67 65 73 20 68 61 76 65 20  s subpages have 
0520: 76 61 6c 75 65 73 20 67 72 65 61 74 65 72 20 74  values greater t
0530: 68 61 6e 20 4b 65 79 28 4e 2d 31 29 2e 20 20 41  han Key(N-1).  A
0540: 6e 64 0a 2a 2a 20 73 6f 20 66 6f 72 74 68 2e 0a  nd.** so forth..
0550: 2a 2a 0a 2a 2a 20 46 69 6e 64 69 6e 67 20 61 20  **.** Finding a 
0560: 70 61 72 74 69 63 75 6c 61 72 20 6b 65 79 20 72  particular key r
0570: 65 71 75 69 72 65 73 20 72 65 61 64 69 6e 67 20  equires reading 
0580: 4f 28 6c 6f 67 28 4d 29 29 20 70 61 67 65 73 20  O(log(M)) pages 
0590: 66 72 6f 6d 20 74 68 65 20 0a 2a 2a 20 64 69 73  from the .** dis
05a0: 6b 20 77 68 65 72 65 20 4d 20 69 73 20 74 68 65  k where M is the
05b0: 20 6e 75 6d 62 65 72 20 6f 66 20 65 6e 74 72 69   number of entri
05c0: 65 73 20 69 6e 20 74 68 65 20 74 72 65 65 2e 0a  es in the tree..
05d0: 2a 2a 0a 2a 2a 20 49 6e 20 74 68 69 73 20 69 6d  **.** In this im
05e0: 70 6c 65 6d 65 6e 74 61 74 69 6f 6e 2c 20 61 20  plementation, a 
05f0: 73 69 6e 67 6c 65 20 66 69 6c 65 20 63 61 6e 20  single file can 
0600: 68 6f 6c 64 20 6f 6e 65 20 6f 72 20 6d 6f 72 65  hold one or more
0610: 20 73 65 70 61 72 61 74 65 20 0a 2a 2a 20 42 54   separate .** BT
0620: 72 65 65 73 2e 20 20 45 61 63 68 20 42 54 72 65  rees.  Each BTre
0630: 65 20 69 73 20 69 64 65 6e 74 69 66 69 65 64 20  e is identified 
0640: 62 79 20 74 68 65 20 69 6e 64 65 78 20 6f 66 20  by the index of 
0650: 69 74 73 20 72 6f 6f 74 20 70 61 67 65 2e 20 20  its root page.  
0660: 54 68 65 0a 2a 2a 20 6b 65 79 20 61 6e 64 20 64  The.** key and d
0670: 61 74 61 20 66 6f 72 20 61 6e 79 20 65 6e 74 72  ata for any entr
0680: 79 20 61 72 65 20 63 6f 6d 62 69 6e 65 64 20 74  y are combined t
0690: 6f 20 66 6f 72 6d 20 74 68 65 20 22 70 61 79 6c  o form the "payl
06a0: 6f 61 64 22 2e 20 20 41 0a 2a 2a 20 66 69 78 65  oad".  A.** fixe
06b0: 64 20 61 6d 6f 75 6e 74 20 6f 66 20 70 61 79 6c  d amount of payl
06c0: 6f 61 64 20 63 61 6e 20 62 65 20 63 61 72 72 69  oad can be carri
06d0: 65 64 20 64 69 72 65 63 74 6c 79 20 6f 6e 20 74  ed directly on t
06e0: 68 65 20 64 61 74 61 62 61 73 65 0a 2a 2a 20 70  he database.** p
06f0: 61 67 65 2e 20 20 49 66 20 74 68 65 20 70 61 79  age.  If the pay
0700: 6c 6f 61 64 20 69 73 20 6c 61 72 67 65 72 20 74  load is larger t
0710: 68 61 6e 20 74 68 65 20 70 72 65 73 65 74 20 61  han the preset a
0720: 6d 6f 75 6e 74 20 74 68 65 6e 20 73 75 72 70 6c  mount then surpl
0730: 75 73 0a 2a 2a 20 62 79 74 65 73 20 61 72 65 20  us.** bytes are 
0740: 73 74 6f 72 65 64 20 6f 6e 20 6f 76 65 72 66 6c  stored on overfl
0750: 6f 77 20 70 61 67 65 73 2e 20 20 54 68 65 20 70  ow pages.  The p
0760: 61 79 6c 6f 61 64 20 66 6f 72 20 61 6e 20 65 6e  ayload for an en
0770: 74 72 79 0a 2a 2a 20 61 6e 64 20 74 68 65 20 70  try.** and the p
0780: 72 65 63 65 64 69 6e 67 20 70 6f 69 6e 74 65 72  receding pointer
0790: 20 61 72 65 20 63 6f 6d 62 69 6e 65 64 20 74 6f   are combined to
07a0: 20 66 6f 72 6d 20 61 20 22 43 65 6c 6c 22 2e 20   form a "Cell". 
07b0: 20 45 61 63 68 20 0a 2a 2a 20 70 61 67 65 20 68   Each .** page h
07c0: 61 73 20 61 20 73 6d 61 6c 6c 20 68 65 61 64 65  as a small heade
07d0: 72 20 77 68 69 63 68 20 63 6f 6e 74 61 69 6e 73  r which contains
07e0: 20 74 68 65 20 50 74 72 28 4e 29 20 70 6f 69 6e   the Ptr(N) poin
07f0: 74 65 72 20 61 6e 64 20 6f 74 68 65 72 0a 2a 2a  ter and other.**
0800: 20 69 6e 66 6f 72 6d 61 74 69 6f 6e 20 73 75 63   information suc
0810: 68 20 61 73 20 74 68 65 20 73 69 7a 65 20 6f 66  h as the size of
0820: 20 6b 65 79 20 61 6e 64 20 64 61 74 61 2e 0a 2a   key and data..*
0830: 2a 0a 2a 2a 20 46 4f 52 4d 41 54 20 44 45 54 41  *.** FORMAT DETA
0840: 49 4c 53 0a 2a 2a 0a 2a 2a 20 54 68 65 20 66 69  ILS.**.** The fi
0850: 6c 65 20 69 73 20 64 69 76 69 64 65 64 20 69 6e  le is divided in
0860: 74 6f 20 70 61 67 65 73 2e 20 20 54 68 65 20 66  to pages.  The f
0870: 69 72 73 74 20 70 61 67 65 20 69 73 20 63 61 6c  irst page is cal
0880: 6c 65 64 20 70 61 67 65 20 31 2c 0a 2a 2a 20 74  led page 1,.** t
0890: 68 65 20 73 65 63 6f 6e 64 20 69 73 20 70 61 67  he second is pag
08a0: 65 20 32 2c 20 61 6e 64 20 73 6f 20 66 6f 72 74  e 2, and so fort
08b0: 68 2e 20 20 41 20 70 61 67 65 20 6e 75 6d 62 65  h.  A page numbe
08c0: 72 20 6f 66 20 7a 65 72 6f 20 69 6e 64 69 63 61  r of zero indica
08d0: 74 65 73 0a 2a 2a 20 22 6e 6f 20 73 75 63 68 20  tes.** "no such 
08e0: 70 61 67 65 22 2e 20 20 54 68 65 20 70 61 67 65  page".  The page
08f0: 20 73 69 7a 65 20 63 61 6e 20 62 65 20 61 6e 79   size can be any
0900: 74 68 69 6e 67 20 62 65 74 77 65 65 6e 20 35 31  thing between 51
0910: 32 20 61 6e 64 20 36 35 35 33 36 2e 0a 2a 2a 20  2 and 65536..** 
0920: 45 61 63 68 20 70 61 67 65 20 63 61 6e 20 62 65  Each page can be
0930: 20 65 69 74 68 65 72 20 61 20 62 74 72 65 65 20   either a btree 
0940: 70 61 67 65 2c 20 61 20 66 72 65 65 6c 69 73 74  page, a freelist
0950: 20 70 61 67 65 20 6f 72 20 61 6e 20 6f 76 65 72   page or an over
0960: 66 6c 6f 77 0a 2a 2a 20 70 61 67 65 2e 0a 2a 2a  flow.** page..**
0970: 0a 2a 2a 20 54 68 65 20 66 69 72 73 74 20 70 61  .** The first pa
0980: 67 65 20 69 73 20 61 6c 77 61 79 73 20 61 20 62  ge is always a b
0990: 74 72 65 65 20 70 61 67 65 2e 20 20 54 68 65 20  tree page.  The 
09a0: 66 69 72 73 74 20 31 30 30 20 62 79 74 65 73 20  first 100 bytes 
09b0: 6f 66 20 74 68 65 20 66 69 72 73 74 0a 2a 2a 20  of the first.** 
09c0: 70 61 67 65 20 63 6f 6e 74 61 69 6e 20 61 20 73  page contain a s
09d0: 70 65 63 69 61 6c 20 68 65 61 64 65 72 20 28 74  pecial header (t
09e0: 68 65 20 22 66 69 6c 65 20 68 65 61 64 65 72 22  he "file header"
09f0: 29 20 74 68 61 74 20 64 65 73 63 72 69 62 65 73  ) that describes
0a00: 20 74 68 65 20 66 69 6c 65 2e 0a 2a 2a 20 54 68   the file..** Th
0a10: 65 20 66 6f 72 6d 61 74 20 6f 66 20 74 68 65 20  e format of the 
0a20: 66 69 6c 65 20 68 65 61 64 65 72 20 69 73 20 61  file header is a
0a30: 73 20 66 6f 6c 6c 6f 77 73 3a 0a 2a 2a 0a 2a 2a  s follows:.**.**
0a40: 20 20 20 4f 46 46 53 45 54 20 20 20 53 49 5a 45     OFFSET   SIZE
0a50: 20 20 20 20 44 45 53 43 52 49 50 54 49 4f 4e 0a      DESCRIPTION.
0a60: 2a 2a 20 20 20 20 20 20 30 20 20 20 20 20 20 31  **      0      1
0a70: 36 20 20 20 20 20 48 65 61 64 65 72 20 73 74 72  6     Header str
0a80: 69 6e 67 3a 20 22 53 51 4c 69 74 65 20 66 6f 72  ing: "SQLite for
0a90: 6d 61 74 20 33 5c 30 30 30 22 0a 2a 2a 20 20 20  mat 3\000".**   
0aa0: 20 20 31 36 20 20 20 20 20 20 20 32 20 20 20 20    16       2    
0ab0: 20 50 61 67 65 20 73 69 7a 65 20 69 6e 20 62 79   Page size in by
0ac0: 74 65 73 2e 20 20 0a 2a 2a 20 20 20 20 20 31 38  tes.  .**     18
0ad0: 20 20 20 20 20 20 20 31 20 20 20 20 20 46 69 6c         1     Fil
0ae0: 65 20 66 6f 72 6d 61 74 20 77 72 69 74 65 20 76  e format write v
0af0: 65 72 73 69 6f 6e 0a 2a 2a 20 20 20 20 20 31 39  ersion.**     19
0b00: 20 20 20 20 20 20 20 31 20 20 20 20 20 46 69 6c         1     Fil
0b10: 65 20 66 6f 72 6d 61 74 20 72 65 61 64 20 76 65  e format read ve
0b20: 72 73 69 6f 6e 0a 2a 2a 20 20 20 20 20 32 30 20  rsion.**     20 
0b30: 20 20 20 20 20 20 31 20 20 20 20 20 42 79 74 65        1     Byte
0b40: 73 20 6f 66 20 75 6e 75 73 65 64 20 73 70 61 63  s of unused spac
0b50: 65 20 61 74 20 74 68 65 20 65 6e 64 20 6f 66 20  e at the end of 
0b60: 65 61 63 68 20 70 61 67 65 0a 2a 2a 20 20 20 20  each page.**    
0b70: 20 32 31 20 20 20 20 20 20 20 31 20 20 20 20 20   21       1     
0b80: 4d 61 78 20 65 6d 62 65 64 64 65 64 20 70 61 79  Max embedded pay
0b90: 6c 6f 61 64 20 66 72 61 63 74 69 6f 6e 0a 2a 2a  load fraction.**
0ba0: 20 20 20 20 20 32 32 20 20 20 20 20 20 20 31 20       22       1 
0bb0: 20 20 20 20 4d 69 6e 20 65 6d 62 65 64 64 65 64      Min embedded
0bc0: 20 70 61 79 6c 6f 61 64 20 66 72 61 63 74 69 6f   payload fractio
0bd0: 6e 0a 2a 2a 20 20 20 20 20 32 33 20 20 20 20 20  n.**     23     
0be0: 20 20 31 20 20 20 20 20 4d 69 6e 20 6c 65 61 66    1     Min leaf
0bf0: 20 70 61 79 6c 6f 61 64 20 66 72 61 63 74 69 6f   payload fractio
0c00: 6e 0a 2a 2a 20 20 20 20 20 32 34 20 20 20 20 20  n.**     24     
0c10: 20 20 34 20 20 20 20 20 46 69 6c 65 20 63 68 61    4     File cha
0c20: 6e 67 65 20 63 6f 75 6e 74 65 72 0a 2a 2a 20 20  nge counter.**  
0c30: 20 20 20 32 38 20 20 20 20 20 20 20 34 20 20 20     28       4   
0c40: 20 20 52 65 73 65 72 76 65 64 20 66 6f 72 20 66    Reserved for f
0c50: 75 74 75 72 65 20 75 73 65 0a 2a 2a 20 20 20 20  uture use.**    
0c60: 20 33 32 20 20 20 20 20 20 20 34 20 20 20 20 20   32       4     
0c70: 46 69 72 73 74 20 66 72 65 65 6c 69 73 74 20 70  First freelist p
0c80: 61 67 65 0a 2a 2a 20 20 20 20 20 33 36 20 20 20  age.**     36   
0c90: 20 20 20 20 34 20 20 20 20 20 4e 75 6d 62 65 72      4     Number
0ca0: 20 6f 66 20 66 72 65 65 6c 69 73 74 20 70 61 67   of freelist pag
0cb0: 65 73 20 69 6e 20 74 68 65 20 66 69 6c 65 0a 2a  es in the file.*
0cc0: 2a 20 20 20 20 20 34 30 20 20 20 20 20 20 36 30  *     40      60
0cd0: 20 20 20 20 20 31 35 20 34 2d 62 79 74 65 20 6d       15 4-byte m
0ce0: 65 74 61 20 76 61 6c 75 65 73 20 70 61 73 73 65  eta values passe
0cf0: 64 20 74 6f 20 68 69 67 68 65 72 20 6c 61 79 65  d to higher laye
0d00: 72 73 0a 2a 2a 0a 2a 2a 20 41 6c 6c 20 6f 66 20  rs.**.** All of 
0d10: 74 68 65 20 69 6e 74 65 67 65 72 20 76 61 6c 75  the integer valu
0d20: 65 73 20 61 72 65 20 62 69 67 2d 65 6e 64 69 61  es are big-endia
0d30: 6e 20 28 6d 6f 73 74 20 73 69 67 6e 69 66 69 63  n (most signific
0d40: 61 6e 74 20 62 79 74 65 20 66 69 72 73 74 29 2e  ant byte first).
0d50: 0a 2a 2a 0a 2a 2a 20 54 68 65 20 66 69 6c 65 20  .**.** The file 
0d60: 63 68 61 6e 67 65 20 63 6f 75 6e 74 65 72 20 69  change counter i
0d70: 73 20 69 6e 63 72 65 6d 65 6e 74 65 64 20 77 68  s incremented wh
0d80: 65 6e 20 74 68 65 20 64 61 74 61 62 61 73 65 20  en the database 
0d90: 69 73 20 63 68 61 6e 67 65 64 0a 2a 2a 20 54 68  is changed.** Th
0da0: 69 73 20 63 6f 75 6e 74 65 72 20 61 6c 6c 6f 77  is counter allow
0db0: 73 20 6f 74 68 65 72 20 70 72 6f 63 65 73 73 65  s other processe
0dc0: 73 20 74 6f 20 6b 6e 6f 77 20 77 68 65 6e 20 74  s to know when t
0dd0: 68 65 20 66 69 6c 65 20 68 61 73 20 63 68 61 6e  he file has chan
0de0: 67 65 64 0a 2a 2a 20 61 6e 64 20 74 68 75 73 20  ged.** and thus 
0df0: 77 68 65 6e 20 74 68 65 79 20 6e 65 65 64 20 74  when they need t
0e00: 6f 20 66 6c 75 73 68 20 74 68 65 69 72 20 63 61  o flush their ca
0e10: 63 68 65 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 6d  che..**.** The m
0e20: 61 78 20 65 6d 62 65 64 64 65 64 20 70 61 79 6c  ax embedded payl
0e30: 6f 61 64 20 66 72 61 63 74 69 6f 6e 20 69 73 20  oad fraction is 
0e40: 74 68 65 20 61 6d 6f 75 6e 74 20 6f 66 20 74 68  the amount of th
0e50: 65 20 74 6f 74 61 6c 20 75 73 61 62 6c 65 0a 2a  e total usable.*
0e60: 2a 20 73 70 61 63 65 20 69 6e 20 61 20 70 61 67  * space in a pag
0e70: 65 20 74 68 61 74 20 63 61 6e 20 62 65 20 63 6f  e that can be co
0e80: 6e 73 75 6d 65 64 20 62 79 20 61 20 73 69 6e 67  nsumed by a sing
0e90: 6c 65 20 63 65 6c 6c 20 66 6f 72 20 73 74 61 6e  le cell for stan
0ea0: 64 61 72 64 0a 2a 2a 20 42 2d 74 72 65 65 20 28  dard.** B-tree (
0eb0: 6e 6f 6e 2d 4c 45 41 46 44 41 54 41 29 20 74 61  non-LEAFDATA) ta
0ec0: 62 6c 65 73 2e 20 20 41 20 76 61 6c 75 65 20 6f  bles.  A value o
0ed0: 66 20 32 35 35 20 6d 65 61 6e 73 20 31 30 30 25  f 255 means 100%
0ee0: 2e 20 20 54 68 65 20 64 65 66 61 75 6c 74 0a 2a  .  The default.*
0ef0: 2a 20 69 73 20 74 6f 20 6c 69 6d 69 74 20 74 68  * is to limit th
0f00: 65 20 6d 61 78 69 6d 75 6d 20 63 65 6c 6c 20 73  e maximum cell s
0f10: 69 7a 65 20 73 6f 20 74 68 61 74 20 61 74 20 6c  ize so that at l
0f20: 65 61 73 74 20 34 20 63 65 6c 6c 73 20 77 69 6c  east 4 cells wil
0f30: 6c 20 66 69 74 0a 2a 2a 20 6f 6e 20 6f 6e 65 20  l fit.** on one 
0f40: 70 61 67 65 2e 20 20 54 68 75 73 20 74 68 65 20  page.  Thus the 
0f50: 64 65 66 61 75 6c 74 20 6d 61 78 20 65 6d 62 65  default max embe
0f60: 64 64 65 64 20 70 61 79 6c 6f 61 64 20 66 72 61  dded payload fra
0f70: 63 74 69 6f 6e 20 69 73 20 36 34 2e 0a 2a 2a 0a  ction is 64..**.
0f80: 2a 2a 20 49 66 20 74 68 65 20 70 61 79 6c 6f 61  ** If the payloa
0f90: 64 20 66 6f 72 20 61 20 63 65 6c 6c 20 69 73 20  d for a cell is 
0fa0: 6c 61 72 67 65 72 20 74 68 61 6e 20 74 68 65 20  larger than the 
0fb0: 6d 61 78 20 70 61 79 6c 6f 61 64 2c 20 74 68 65  max payload, the
0fc0: 6e 20 65 78 74 72 61 0a 2a 2a 20 70 61 79 6c 6f  n extra.** paylo
0fd0: 61 64 20 69 73 20 73 70 69 6c 6c 65 64 20 74 6f  ad is spilled to
0fe0: 20 6f 76 65 72 66 6c 6f 77 20 70 61 67 65 73 2e   overflow pages.
0ff0: 20 20 4f 6e 63 65 20 61 6e 20 6f 76 65 72 66 6c    Once an overfl
1000: 6f 77 20 70 61 67 65 20 69 73 20 61 6c 6c 6f 63  ow page is alloc
1010: 61 74 65 64 2c 0a 2a 2a 20 61 73 20 6d 61 6e 79  ated,.** as many
1020: 20 62 79 74 65 73 20 61 73 20 70 6f 73 73 69 62   bytes as possib
1030: 6c 65 20 61 72 65 20 6d 6f 76 65 64 20 69 6e 74  le are moved int
1040: 6f 20 74 68 65 20 6f 76 65 72 66 6c 6f 77 20 70  o the overflow p
1050: 61 67 65 73 20 77 69 74 68 6f 75 74 20 6c 65 74  ages without let
1060: 74 69 6e 67 0a 2a 2a 20 74 68 65 20 63 65 6c 6c  ting.** the cell
1070: 20 73 69 7a 65 20 64 72 6f 70 20 62 65 6c 6f 77   size drop below
1080: 20 74 68 65 20 6d 69 6e 20 65 6d 62 65 64 64 65   the min embedde
1090: 64 20 70 61 79 6c 6f 61 64 20 66 72 61 63 74 69  d payload fracti
10a0: 6f 6e 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 6d 69  on..**.** The mi
10b0: 6e 20 6c 65 61 66 20 70 61 79 6c 6f 61 64 20 66  n leaf payload f
10c0: 72 61 63 74 69 6f 6e 20 69 73 20 6c 69 6b 65 20  raction is like 
10d0: 74 68 65 20 6d 69 6e 20 65 6d 62 65 64 64 65 64  the min embedded
10e0: 20 70 61 79 6c 6f 61 64 20 66 72 61 63 74 69 6f   payload fractio
10f0: 6e 0a 2a 2a 20 65 78 63 65 70 74 20 74 68 61 74  n.** except that
1100: 20 69 74 20 61 70 70 6c 69 65 73 20 74 6f 20 6c   it applies to l
1110: 65 61 66 20 6e 6f 64 65 73 20 69 6e 20 61 20 4c  eaf nodes in a L
1120: 45 41 46 44 41 54 41 20 74 72 65 65 2e 20 20 54  EAFDATA tree.  T
1130: 68 65 20 6d 61 78 69 6d 75 6d 0a 2a 2a 20 70 61  he maximum.** pa
1140: 79 6c 6f 61 64 20 66 72 61 63 74 69 6f 6e 20 66  yload fraction f
1150: 6f 72 20 61 20 4c 45 41 46 44 41 54 41 20 74 72  or a LEAFDATA tr
1160: 65 65 20 69 73 20 61 6c 77 61 79 73 20 31 30 30  ee is always 100
1170: 25 20 28 6f 72 20 32 35 35 29 20 61 6e 64 20 69  % (or 255) and i
1180: 74 0a 2a 2a 20 6e 6f 74 20 73 70 65 63 69 66 69  t.** not specifi
1190: 65 64 20 69 6e 20 74 68 65 20 68 65 61 64 65 72  ed in the header
11a0: 2e 0a 2a 2a 0a 2a 2a 20 45 61 63 68 20 62 74 72  ..**.** Each btr
11b0: 65 65 20 70 61 67 65 73 20 69 73 20 64 69 76 69  ee pages is divi
11c0: 64 65 64 20 69 6e 74 6f 20 74 68 72 65 65 20 73  ded into three s
11d0: 65 63 74 69 6f 6e 73 3a 20 20 54 68 65 20 68 65  ections:  The he
11e0: 61 64 65 72 2c 20 74 68 65 0a 2a 2a 20 63 65 6c  ader, the.** cel
11f0: 6c 20 70 6f 69 6e 74 65 72 20 61 72 72 61 79 2c  l pointer array,
1200: 20 61 6e 64 20 74 68 65 20 63 65 6c 6c 20 63 6f   and the cell co
1210: 6e 74 65 6e 74 20 61 72 65 61 2e 20 20 50 61 67  ntent area.  Pag
1220: 65 20 31 20 61 6c 73 6f 20 68 61 73 20 61 20 31  e 1 also has a 1
1230: 30 30 2d 62 79 74 65 0a 2a 2a 20 66 69 6c 65 20  00-byte.** file 
1240: 68 65 61 64 65 72 20 74 68 61 74 20 6f 63 63 75  header that occu
1250: 72 73 20 62 65 66 6f 72 65 20 74 68 65 20 70 61  rs before the pa
1260: 67 65 20 68 65 61 64 65 72 2e 0a 2a 2a 0a 2a 2a  ge header..**.**
1270: 20 20 20 20 20 20 7c 2d 2d 2d 2d 2d 2d 2d 2d 2d        |---------
1280: 2d 2d 2d 2d 2d 2d 2d 7c 0a 2a 2a 20 20 20 20 20  -------|.**     
1290: 20 7c 20 66 69 6c 65 20 68 65 61 64 65 72 20 20   | file header  
12a0: 20 20 7c 20 20 20 31 30 30 20 62 79 74 65 73 2e    |   100 bytes.
12b0: 20 20 50 61 67 65 20 31 20 6f 6e 6c 79 2e 0a 2a    Page 1 only..*
12c0: 2a 20 20 20 20 20 20 7c 2d 2d 2d 2d 2d 2d 2d 2d  *      |--------
12d0: 2d 2d 2d 2d 2d 2d 2d 2d 7c 0a 2a 2a 20 20 20 20  --------|.**    
12e0: 20 20 7c 20 70 61 67 65 20 68 65 61 64 65 72 20    | page header 
12f0: 20 20 20 7c 20 20 20 38 20 62 79 74 65 73 20 66     |   8 bytes f
1300: 6f 72 20 6c 65 61 76 65 73 2e 20 20 31 32 20 62  or leaves.  12 b
1310: 79 74 65 73 20 66 6f 72 20 69 6e 74 65 72 69 6f  ytes for interio
1320: 72 20 6e 6f 64 65 73 0a 2a 2a 20 20 20 20 20 20  r nodes.**      
1330: 7c 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  |---------------
1340: 2d 7c 0a 2a 2a 20 20 20 20 20 20 7c 20 63 65 6c  -|.**      | cel
1350: 6c 20 70 6f 69 6e 74 65 72 20 20 20 7c 20 20 20  l pointer   |   
1360: 7c 20 20 32 20 62 79 74 65 73 20 70 65 72 20 63  |  2 bytes per c
1370: 65 6c 6c 2e 20 20 53 6f 72 74 65 64 20 6f 72 64  ell.  Sorted ord
1380: 65 72 2e 0a 2a 2a 20 20 20 20 20 20 7c 20 61 72  er..**      | ar
1390: 72 61 79 20 20 20 20 20 20 20 20 20 20 7c 20 20  ray          |  
13a0: 20 7c 20 20 47 72 6f 77 73 20 64 6f 77 6e 77 61   |  Grows downwa
13b0: 72 64 0a 2a 2a 20 20 20 20 20 20 7c 20 20 20 20  rd.**      |    
13c0: 20 20 20 20 20 20 20 20 20 20 20 20 7c 20 20 20              |   
13d0: 76 0a 2a 2a 20 20 20 20 20 20 7c 2d 2d 2d 2d 2d  v.**      |-----
13e0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 7c 0a 2a 2a 20  -----------|.** 
13f0: 20 20 20 20 20 7c 20 75 6e 61 6c 6c 6f 63 61 74       | unallocat
1400: 65 64 20 20 20 20 7c 0a 2a 2a 20 20 20 20 20 20  ed    |.**      
1410: 7c 20 73 70 61 63 65 20 20 20 20 20 20 20 20 20  | space         
1420: 20 7c 0a 2a 2a 20 20 20 20 20 20 7c 2d 2d 2d 2d   |.**      |----
1430: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 7c 20 20 20  ------------|   
1440: 5e 20 20 47 72 6f 77 73 20 75 70 77 61 72 64 73  ^  Grows upwards
1450: 0a 2a 2a 20 20 20 20 20 20 7c 20 63 65 6c 6c 20  .**      | cell 
1460: 63 6f 6e 74 65 6e 74 20 20 20 7c 20 20 20 7c 20  content   |   | 
1470: 20 41 72 62 69 74 72 61 72 79 20 6f 72 64 65 72   Arbitrary order
1480: 20 69 6e 74 65 72 73 70 65 72 73 65 64 20 77 69   interspersed wi
1490: 74 68 20 66 72 65 65 62 6c 6f 63 6b 73 2e 0a 2a  th freeblocks..*
14a0: 2a 20 20 20 20 20 20 7c 20 61 72 65 61 20 20 20  *      | area   
14b0: 20 20 20 20 20 20 20 20 7c 20 20 20 7c 20 20 61          |   |  a
14c0: 6e 64 20 66 72 65 65 20 73 70 61 63 65 20 66 72  nd free space fr
14d0: 61 67 6d 65 6e 74 73 2e 0a 2a 2a 20 20 20 20 20  agments..**     
14e0: 20 7c 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d   |--------------
14f0: 2d 2d 7c 0a 2a 2a 0a 2a 2a 20 54 68 65 20 70 61  --|.**.** The pa
1500: 67 65 20 68 65 61 64 65 72 73 20 6c 6f 6f 6b 73  ge headers looks
1510: 20 6c 69 6b 65 20 74 68 69 73 3a 0a 2a 2a 0a 2a   like this:.**.*
1520: 2a 20 20 20 4f 46 46 53 45 54 20 20 20 53 49 5a  *   OFFSET   SIZ
1530: 45 20 20 20 20 20 44 45 53 43 52 49 50 54 49 4f  E     DESCRIPTIO
1540: 4e 0a 2a 2a 20 20 20 20 20 20 30 20 20 20 20 20  N.**      0     
1550: 20 20 31 20 20 20 20 20 20 46 6c 61 67 73 2e 20    1      Flags. 
1560: 31 3a 20 69 6e 74 6b 65 79 2c 20 32 3a 20 7a 65  1: intkey, 2: ze
1570: 72 6f 64 61 74 61 2c 20 34 3a 20 6c 65 61 66 64  rodata, 4: leafd
1580: 61 74 61 2c 20 38 3a 20 6c 65 61 66 0a 2a 2a 20  ata, 8: leaf.** 
1590: 20 20 20 20 20 31 20 20 20 20 20 20 20 32 20 20       1       2  
15a0: 20 20 20 20 62 79 74 65 20 6f 66 66 73 65 74 20      byte offset 
15b0: 74 6f 20 74 68 65 20 66 69 72 73 74 20 66 72 65  to the first fre
15c0: 65 62 6c 6f 63 6b 0a 2a 2a 20 20 20 20 20 20 33  eblock.**      3
15d0: 20 20 20 20 20 20 20 32 20 20 20 20 20 20 6e 75         2      nu
15e0: 6d 62 65 72 20 6f 66 20 63 65 6c 6c 73 20 6f 6e  mber of cells on
15f0: 20 74 68 69 73 20 70 61 67 65 0a 2a 2a 20 20 20   this page.**   
1600: 20 20 20 35 20 20 20 20 20 20 20 32 20 20 20 20     5       2    
1610: 20 20 66 69 72 73 74 20 62 79 74 65 20 6f 66 20    first byte of 
1620: 74 68 65 20 63 65 6c 6c 20 63 6f 6e 74 65 6e 74  the cell content
1630: 20 61 72 65 61 0a 2a 2a 20 20 20 20 20 20 37 20   area.**      7 
1640: 20 20 20 20 20 20 31 20 20 20 20 20 20 6e 75 6d        1      num
1650: 62 65 72 20 6f 66 20 66 72 61 67 6d 65 6e 74 65  ber of fragmente
1660: 64 20 66 72 65 65 20 62 79 74 65 73 0a 2a 2a 20  d free bytes.** 
1670: 20 20 20 20 20 38 20 20 20 20 20 20 20 34 20 20       8       4  
1680: 20 20 20 20 52 69 67 68 74 20 63 68 69 6c 64 20      Right child 
1690: 28 74 68 65 20 50 74 72 28 4e 29 20 76 61 6c 75  (the Ptr(N) valu
16a0: 65 29 2e 20 20 4f 6d 69 74 74 65 64 20 6f 6e 20  e).  Omitted on 
16b0: 6c 65 61 76 65 73 2e 0a 2a 2a 0a 2a 2a 20 54 68  leaves..**.** Th
16c0: 65 20 66 6c 61 67 73 20 64 65 66 69 6e 65 20 74  e flags define t
16d0: 68 65 20 66 6f 72 6d 61 74 20 6f 66 20 74 68 69  he format of thi
16e0: 73 20 62 74 72 65 65 20 70 61 67 65 2e 20 20 54  s btree page.  T
16f0: 68 65 20 6c 65 61 66 20 66 6c 61 67 20 6d 65 61  he leaf flag mea
1700: 6e 73 20 74 68 61 74 0a 2a 2a 20 74 68 69 73 20  ns that.** this 
1710: 70 61 67 65 20 68 61 73 20 6e 6f 20 63 68 69 6c  page has no chil
1720: 64 72 65 6e 2e 20 20 54 68 65 20 7a 65 72 6f 64  dren.  The zerod
1730: 61 74 61 20 66 6c 61 67 20 6d 65 61 6e 73 20 74  ata flag means t
1740: 68 61 74 20 74 68 69 73 20 70 61 67 65 20 63 61  hat this page ca
1750: 72 72 69 65 73 0a 2a 2a 20 6f 6e 6c 79 20 6b 65  rries.** only ke
1760: 79 73 20 61 6e 64 20 6e 6f 20 64 61 74 61 2e 20  ys and no data. 
1770: 20 54 68 65 20 69 6e 74 6b 65 79 20 66 6c 61 67   The intkey flag
1780: 20 6d 65 61 6e 73 20 74 68 61 74 20 74 68 65 20   means that the 
1790: 6b 65 79 20 69 73 20 61 20 69 6e 74 65 67 65 72  key is a integer
17a0: 0a 2a 2a 20 77 68 69 63 68 20 69 73 20 73 74 6f  .** which is sto
17b0: 72 65 64 20 69 6e 20 74 68 65 20 6b 65 79 20 73  red in the key s
17c0: 69 7a 65 20 65 6e 74 72 79 20 6f 66 20 74 68 65  ize entry of the
17d0: 20 63 65 6c 6c 20 68 65 61 64 65 72 20 72 61 74   cell header rat
17e0: 68 65 72 20 74 68 61 6e 20 69 6e 0a 2a 2a 20 74  her than in.** t
17f0: 68 65 20 70 61 79 6c 6f 61 64 20 61 72 65 61 2e  he payload area.
1800: 0a 2a 2a 0a 2a 2a 20 54 68 65 20 63 65 6c 6c 20  .**.** The cell 
1810: 70 6f 69 6e 74 65 72 20 61 72 72 61 79 20 62 65  pointer array be
1820: 67 69 6e 73 20 6f 6e 20 74 68 65 20 66 69 72 73  gins on the firs
1830: 74 20 62 79 74 65 20 61 66 74 65 72 20 74 68 65  t byte after the
1840: 20 70 61 67 65 20 68 65 61 64 65 72 2e 0a 2a 2a   page header..**
1850: 20 54 68 65 20 63 65 6c 6c 20 70 6f 69 6e 74 65   The cell pointe
1860: 72 20 61 72 72 61 79 20 63 6f 6e 74 61 69 6e 73  r array contains
1870: 20 7a 65 72 6f 20 6f 72 20 6d 6f 72 65 20 32 2d   zero or more 2-
1880: 62 79 74 65 20 6e 75 6d 62 65 72 73 20 77 68 69  byte numbers whi
1890: 63 68 20 61 72 65 0a 2a 2a 20 6f 66 66 73 65 74  ch are.** offset
18a0: 73 20 66 72 6f 6d 20 74 68 65 20 62 65 67 69 6e  s from the begin
18b0: 6e 69 6e 67 20 6f 66 20 74 68 65 20 70 61 67 65  ning of the page
18c0: 20 74 6f 20 74 68 65 20 63 65 6c 6c 20 63 6f 6e   to the cell con
18d0: 74 65 6e 74 20 69 6e 20 74 68 65 20 63 65 6c 6c  tent in the cell
18e0: 0a 2a 2a 20 63 6f 6e 74 65 6e 74 20 61 72 65 61  .** content area
18f0: 2e 20 20 54 68 65 20 63 65 6c 6c 20 70 6f 69 6e  .  The cell poin
1900: 74 65 72 73 20 6f 63 63 75 72 20 69 6e 20 73 6f  ters occur in so
1910: 72 74 65 64 20 6f 72 64 65 72 2e 20 20 54 68 65  rted order.  The
1920: 20 73 79 73 74 65 6d 20 73 74 72 69 76 65 73 0a   system strives.
1930: 2a 2a 20 74 6f 20 6b 65 65 70 20 66 72 65 65 20  ** to keep free 
1940: 73 70 61 63 65 20 61 66 74 65 72 20 74 68 65 20  space after the 
1950: 6c 61 73 74 20 63 65 6c 6c 20 70 6f 69 6e 74 65  last cell pointe
1960: 72 20 73 6f 20 74 68 61 74 20 6e 65 77 20 63 65  r so that new ce
1970: 6c 6c 73 20 63 61 6e 0a 2a 2a 20 62 65 20 65 61  lls can.** be ea
1980: 73 69 6c 79 20 61 64 64 65 64 20 77 69 74 68 6f  sily added witho
1990: 75 74 20 68 61 76 69 6e 67 20 74 6f 20 64 65 66  ut having to def
19a0: 72 61 67 6d 65 6e 74 20 74 68 65 20 70 61 67 65  ragment the page
19b0: 2e 0a 2a 2a 0a 2a 2a 20 43 65 6c 6c 20 63 6f 6e  ..**.** Cell con
19c0: 74 65 6e 74 20 69 73 20 73 74 6f 72 65 64 20 61  tent is stored a
19d0: 74 20 74 68 65 20 76 65 72 79 20 65 6e 64 20 6f  t the very end o
19e0: 66 20 74 68 65 20 70 61 67 65 20 61 6e 64 20 67  f the page and g
19f0: 72 6f 77 73 20 74 6f 77 61 72 64 20 74 68 65 0a  rows toward the.
1a00: 2a 2a 20 62 65 67 69 6e 6e 69 6e 67 20 6f 66 20  ** beginning of 
1a10: 74 68 65 20 70 61 67 65 2e 0a 2a 2a 0a 2a 2a 20  the page..**.** 
1a20: 55 6e 75 73 65 64 20 73 70 61 63 65 20 77 69 74  Unused space wit
1a30: 68 69 6e 20 74 68 65 20 63 65 6c 6c 20 63 6f 6e  hin the cell con
1a40: 74 65 6e 74 20 61 72 65 61 20 69 73 20 63 6f 6c  tent area is col
1a50: 6c 65 63 74 65 64 20 69 6e 74 6f 20 61 20 6c 69  lected into a li
1a60: 6e 6b 65 64 20 6c 69 73 74 20 6f 66 0a 2a 2a 20  nked list of.** 
1a70: 66 72 65 65 62 6c 6f 63 6b 73 2e 20 20 45 61 63  freeblocks.  Eac
1a80: 68 20 66 72 65 65 62 6c 6f 63 6b 20 69 73 20 61  h freeblock is a
1a90: 74 20 6c 65 61 73 74 20 34 20 62 79 74 65 73 20  t least 4 bytes 
1aa0: 69 6e 20 73 69 7a 65 2e 20 20 54 68 65 20 62 79  in size.  The by
1ab0: 74 65 20 6f 66 66 73 65 74 0a 2a 2a 20 74 6f 20  te offset.** to 
1ac0: 74 68 65 20 66 69 72 73 74 20 66 72 65 65 62 6c  the first freebl
1ad0: 6f 63 6b 20 69 73 20 67 69 76 65 6e 20 69 6e 20  ock is given in 
1ae0: 74 68 65 20 68 65 61 64 65 72 2e 20 20 46 72 65  the header.  Fre
1af0: 65 62 6c 6f 63 6b 73 20 6f 63 63 75 72 20 69 6e  eblocks occur in
1b00: 0a 2a 2a 20 69 6e 63 72 65 61 73 69 6e 67 20 6f  .** increasing o
1b10: 72 64 65 72 2e 20 20 42 65 63 61 75 73 65 20 61  rder.  Because a
1b20: 20 66 72 65 65 62 6c 6f 63 6b 20 6d 75 73 74 20   freeblock must 
1b30: 62 65 20 61 74 20 6c 65 61 73 74 20 34 20 62 79  be at least 4 by
1b40: 74 65 73 20 69 6e 20 73 69 7a 65 2c 0a 2a 2a 20  tes in size,.** 
1b50: 61 6e 79 20 67 72 6f 75 70 20 6f 66 20 33 20 6f  any group of 3 o
1b60: 72 20 66 65 77 65 72 20 75 6e 75 73 65 64 20 62  r fewer unused b
1b70: 79 74 65 73 20 69 6e 20 74 68 65 20 63 65 6c 6c  ytes in the cell
1b80: 20 63 6f 6e 74 65 6e 74 20 61 72 65 61 20 63 61   content area ca
1b90: 6e 6e 6f 74 0a 2a 2a 20 65 78 69 73 74 20 6f 6e  nnot.** exist on
1ba0: 20 74 68 65 20 66 72 65 65 62 6c 6f 63 6b 20 63   the freeblock c
1bb0: 68 61 69 6e 2e 20 20 41 20 67 72 6f 75 70 20 6f  hain.  A group o
1bc0: 66 20 33 20 6f 72 20 66 65 77 65 72 20 66 72 65  f 3 or fewer fre
1bd0: 65 20 62 79 74 65 73 20 69 73 20 63 61 6c 6c 65  e bytes is calle
1be0: 64 0a 2a 2a 20 61 20 66 72 61 67 6d 65 6e 74 2e  d.** a fragment.
1bf0: 20 20 54 68 65 20 74 6f 74 61 6c 20 6e 75 6d 62    The total numb
1c00: 65 72 20 6f 66 20 62 79 74 65 73 20 69 6e 20 61  er of bytes in a
1c10: 6c 6c 20 66 72 61 67 6d 65 6e 74 73 20 69 73 20  ll fragments is 
1c20: 72 65 63 6f 72 64 65 64 2e 0a 2a 2a 20 69 6e 20  recorded..** in 
1c30: 74 68 65 20 70 61 67 65 20 68 65 61 64 65 72 20  the page header 
1c40: 61 74 20 6f 66 66 73 65 74 20 37 2e 0a 2a 2a 0a  at offset 7..**.
1c50: 2a 2a 20 20 20 20 53 49 5a 45 20 20 20 20 44 45  **    SIZE    DE
1c60: 53 43 52 49 50 54 49 4f 4e 0a 2a 2a 20 20 20 20  SCRIPTION.**    
1c70: 20 20 32 20 20 20 20 20 42 79 74 65 20 6f 66 66    2     Byte off
1c80: 73 65 74 20 6f 66 20 74 68 65 20 6e 65 78 74 20  set of the next 
1c90: 66 72 65 65 62 6c 6f 63 6b 0a 2a 2a 20 20 20 20  freeblock.**    
1ca0: 20 20 32 20 20 20 20 20 42 79 74 65 73 20 69 6e    2     Bytes in
1cb0: 20 74 68 69 73 20 66 72 65 65 62 6c 6f 63 6b 0a   this freeblock.
1cc0: 2a 2a 0a 2a 2a 20 43 65 6c 6c 73 20 61 72 65 20  **.** Cells are 
1cd0: 6f 66 20 76 61 72 69 61 62 6c 65 20 6c 65 6e 67  of variable leng
1ce0: 74 68 2e 20 20 43 65 6c 6c 73 20 61 72 65 20 73  th.  Cells are s
1cf0: 74 6f 72 65 64 20 69 6e 20 74 68 65 20 63 65 6c  tored in the cel
1d00: 6c 20 63 6f 6e 74 65 6e 74 20 61 72 65 61 20 61  l content area a
1d10: 74 0a 2a 2a 20 74 68 65 20 65 6e 64 20 6f 66 20  t.** the end of 
1d20: 74 68 65 20 70 61 67 65 2e 20 20 50 6f 69 6e 74  the page.  Point
1d30: 65 72 73 20 74 6f 20 74 68 65 20 63 65 6c 6c 73  ers to the cells
1d40: 20 61 72 65 20 69 6e 20 74 68 65 20 63 65 6c 6c   are in the cell
1d50: 20 70 6f 69 6e 74 65 72 20 61 72 72 61 79 0a 2a   pointer array.*
1d60: 2a 20 74 68 61 74 20 69 6d 6d 65 64 69 61 74 65  * that immediate
1d70: 6c 79 20 66 6f 6c 6c 6f 77 73 20 74 68 65 20 70  ly follows the p
1d80: 61 67 65 20 68 65 61 64 65 72 2e 20 20 43 65 6c  age header.  Cel
1d90: 6c 73 20 69 73 20 6e 6f 74 20 6e 65 63 65 73 73  ls is not necess
1da0: 61 72 69 6c 79 0a 2a 2a 20 63 6f 6e 74 69 67 75  arily.** contigu
1db0: 6f 75 73 20 6f 72 20 69 6e 20 6f 72 64 65 72 2c  ous or in order,
1dc0: 20 62 75 74 20 63 65 6c 6c 20 70 6f 69 6e 74 65   but cell pointe
1dd0: 72 73 20 61 72 65 20 63 6f 6e 74 69 67 75 6f 75  rs are contiguou
1de0: 73 20 61 6e 64 20 69 6e 20 6f 72 64 65 72 2e 0a  s and in order..
1df0: 2a 2a 0a 2a 2a 20 43 65 6c 6c 20 63 6f 6e 74 65  **.** Cell conte
1e00: 6e 74 20 6d 61 6b 65 73 20 75 73 65 20 6f 66 20  nt makes use of 
1e10: 76 61 72 69 61 62 6c 65 20 6c 65 6e 67 74 68 20  variable length 
1e20: 69 6e 74 65 67 65 72 73 2e 20 20 41 20 76 61 72  integers.  A var
1e30: 69 61 62 6c 65 0a 2a 2a 20 6c 65 6e 67 74 68 20  iable.** length 
1e40: 69 6e 74 65 67 65 72 20 69 73 20 31 20 74 6f 20  integer is 1 to 
1e50: 39 20 62 79 74 65 73 20 77 68 65 72 65 20 74 68  9 bytes where th
1e60: 65 20 6c 6f 77 65 72 20 37 20 62 69 74 73 20 6f  e lower 7 bits o
1e70: 66 20 65 61 63 68 20 0a 2a 2a 20 62 79 74 65 20  f each .** byte 
1e80: 61 72 65 20 75 73 65 64 2e 20 20 54 68 65 20 69  are used.  The i
1e90: 6e 74 65 67 65 72 20 63 6f 6e 73 69 73 74 73 20  nteger consists 
1ea0: 6f 66 20 61 6c 6c 20 62 79 74 65 73 20 74 68 61  of all bytes tha
1eb0: 74 20 68 61 76 65 20 62 69 74 20 38 20 73 65 74  t have bit 8 set
1ec0: 20 61 6e 64 0a 2a 2a 20 74 68 65 20 66 69 72 73   and.** the firs
1ed0: 74 20 62 79 74 65 20 77 69 74 68 20 62 69 74 20  t byte with bit 
1ee0: 38 20 63 6c 65 61 72 2e 20 20 54 68 65 20 6d 6f  8 clear.  The mo
1ef0: 73 74 20 73 69 67 6e 69 66 69 63 61 6e 74 20 62  st significant b
1f00: 79 74 65 20 6f 66 20 74 68 65 20 69 6e 74 65 67  yte of the integ
1f10: 65 72 0a 2a 2a 20 61 70 70 65 61 72 73 20 66 69  er.** appears fi
1f20: 72 73 74 2e 20 20 41 20 76 61 72 69 61 62 6c 65  rst.  A variable
1f30: 2d 6c 65 6e 67 74 68 20 69 6e 74 65 67 65 72 20  -length integer 
1f40: 6d 61 79 20 6e 6f 74 20 62 65 20 6d 6f 72 65 20  may not be more 
1f50: 74 68 61 6e 20 39 20 62 79 74 65 73 20 6c 6f 6e  than 9 bytes lon
1f60: 67 2e 0a 2a 2a 20 41 73 20 61 20 73 70 65 63 69  g..** As a speci
1f70: 61 6c 20 63 61 73 65 2c 20 61 6c 6c 20 38 20 62  al case, all 8 b
1f80: 79 74 65 73 20 6f 66 20 74 68 65 20 39 74 68 20  ytes of the 9th 
1f90: 62 79 74 65 20 61 72 65 20 75 73 65 64 20 61 73  byte are used as
1fa0: 20 64 61 74 61 2e 20 20 54 68 69 73 0a 2a 2a 20   data.  This.** 
1fb0: 61 6c 6c 6f 77 73 20 61 20 36 34 2d 62 69 74 20  allows a 64-bit 
1fc0: 69 6e 74 65 67 65 72 20 74 6f 20 62 65 20 65 6e  integer to be en
1fd0: 63 6f 64 65 64 20 69 6e 20 39 20 62 79 74 65 73  coded in 9 bytes
1fe0: 2e 0a 2a 2a 0a 2a 2a 20 20 20 20 30 78 30 30 20  ..**.**    0x00 
1ff0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2000: 20 20 20 20 20 62 65 63 6f 6d 65 73 20 20 30 78       becomes  0x
2010: 30 30 30 30 30 30 30 30 0a 2a 2a 20 20 20 20 30  00000000.**    0
2020: 78 37 66 20 20 20 20 20 20 20 20 20 20 20 20 20  x7f             
2030: 20 20 20 20 20 20 20 20 20 62 65 63 6f 6d 65 73           becomes
2040: 20 20 30 78 30 30 30 30 30 30 37 66 0a 2a 2a 20    0x0000007f.** 
2050: 20 20 20 30 78 38 31 20 30 78 30 30 20 20 20 20     0x81 0x00    
2060: 20 20 20 20 20 20 20 20 20 20 20 20 20 62 65 63               bec
2070: 6f 6d 65 73 20 20 30 78 30 30 30 30 30 30 38 30  omes  0x00000080
2080: 0a 2a 2a 20 20 20 20 30 78 38 32 20 30 78 30 30  .**    0x82 0x00
2090: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
20a0: 20 62 65 63 6f 6d 65 73 20 20 30 78 30 30 30 30   becomes  0x0000
20b0: 30 31 30 30 0a 2a 2a 20 20 20 20 30 78 38 30 20  0100.**    0x80 
20c0: 30 78 37 66 20 20 20 20 20 20 20 20 20 20 20 20  0x7f            
20d0: 20 20 20 20 20 62 65 63 6f 6d 65 73 20 20 30 78       becomes  0x
20e0: 30 30 30 30 30 30 37 66 0a 2a 2a 20 20 20 20 30  0000007f.**    0
20f0: 78 38 61 20 30 78 39 31 20 30 78 64 31 20 30 78  x8a 0x91 0xd1 0x
2100: 61 63 20 30 78 37 38 20 20 62 65 63 6f 6d 65 73  ac 0x78  becomes
2110: 20 20 30 78 31 32 33 34 35 36 37 38 0a 2a 2a 20    0x12345678.** 
2120: 20 20 20 30 78 38 31 20 30 78 38 31 20 30 78 38     0x81 0x81 0x8
2130: 31 20 30 78 38 31 20 30 78 30 31 20 20 62 65 63  1 0x81 0x01  bec
2140: 6f 6d 65 73 20 20 30 78 31 30 32 30 34 30 38 31  omes  0x10204081
2150: 0a 2a 2a 0a 2a 2a 20 56 61 72 69 61 62 6c 65 20  .**.** Variable 
2160: 6c 65 6e 67 74 68 20 69 6e 74 65 67 65 72 73 20  length integers 
2170: 61 72 65 20 75 73 65 64 20 66 6f 72 20 72 6f 77  are used for row
2180: 69 64 73 20 61 6e 64 20 74 6f 20 68 6f 6c 64 20  ids and to hold 
2190: 74 68 65 20 6e 75 6d 62 65 72 20 6f 66 0a 2a 2a  the number of.**
21a0: 20 62 79 74 65 73 20 6f 66 20 6b 65 79 20 61 6e   bytes of key an
21b0: 64 20 64 61 74 61 20 69 6e 20 61 20 62 74 72 65  d data in a btre
21c0: 65 20 63 65 6c 6c 2e 0a 2a 2a 0a 2a 2a 20 54 68  e cell..**.** Th
21d0: 65 20 63 6f 6e 74 65 6e 74 20 6f 66 20 61 20 63  e content of a c
21e0: 65 6c 6c 20 6c 6f 6f 6b 73 20 6c 69 6b 65 20 74  ell looks like t
21f0: 68 69 73 3a 0a 2a 2a 0a 2a 2a 20 20 20 20 53 49  his:.**.**    SI
2200: 5a 45 20 20 20 20 44 45 53 43 52 49 50 54 49 4f  ZE    DESCRIPTIO
2210: 4e 0a 2a 2a 20 20 20 20 20 20 34 20 20 20 20 20  N.**      4     
2220: 50 61 67 65 20 6e 75 6d 62 65 72 20 6f 66 20 74  Page number of t
2230: 68 65 20 6c 65 66 74 20 63 68 69 6c 64 2e 20 4f  he left child. O
2240: 6d 69 74 74 65 64 20 69 66 20 6c 65 61 66 20 66  mitted if leaf f
2250: 6c 61 67 20 69 73 20 73 65 74 2e 0a 2a 2a 20 20  lag is set..**  
2260: 20 20 20 76 61 72 20 20 20 20 4e 75 6d 62 65 72     var    Number
2270: 20 6f 66 20 62 79 74 65 73 20 6f 66 20 64 61 74   of bytes of dat
2280: 61 2e 20 4f 6d 69 74 74 65 64 20 69 66 20 74 68  a. Omitted if th
2290: 65 20 7a 65 72 6f 64 61 74 61 20 66 6c 61 67 20  e zerodata flag 
22a0: 69 73 20 73 65 74 2e 0a 2a 2a 20 20 20 20 20 76  is set..**     v
22b0: 61 72 20 20 20 20 4e 75 6d 62 65 72 20 6f 66 20  ar    Number of 
22c0: 62 79 74 65 73 20 6f 66 20 6b 65 79 2e 20 4f 72  bytes of key. Or
22d0: 20 74 68 65 20 6b 65 79 20 69 74 73 65 6c 66 20   the key itself 
22e0: 69 66 20 69 6e 74 6b 65 79 20 66 6c 61 67 20 69  if intkey flag i
22f0: 73 20 73 65 74 2e 0a 2a 2a 20 20 20 20 20 20 2a  s set..**      *
2300: 20 20 20 20 20 50 61 79 6c 6f 61 64 0a 2a 2a 20       Payload.** 
2310: 20 20 20 20 20 34 20 20 20 20 20 46 69 72 73 74       4     First
2320: 20 70 61 67 65 20 6f 66 20 74 68 65 20 6f 76 65   page of the ove
2330: 72 66 6c 6f 77 20 63 68 61 69 6e 2e 20 20 4f 6d  rflow chain.  Om
2340: 69 74 74 65 64 20 69 66 20 6e 6f 20 6f 76 65 72  itted if no over
2350: 66 6c 6f 77 0a 2a 2a 0a 2a 2a 20 4f 76 65 72 66  flow.**.** Overf
2360: 6c 6f 77 20 70 61 67 65 73 20 66 6f 72 6d 20 61  low pages form a
2370: 20 6c 69 6e 6b 65 64 20 6c 69 73 74 2e 20 20 45   linked list.  E
2380: 61 63 68 20 70 61 67 65 20 65 78 63 65 70 74 20  ach page except 
2390: 74 68 65 20 6c 61 73 74 20 69 73 20 63 6f 6d 70  the last is comp
23a0: 6c 65 74 65 6c 79 0a 2a 2a 20 66 69 6c 6c 65 64  letely.** filled
23b0: 20 77 69 74 68 20 64 61 74 61 20 28 70 61 67 65   with data (page
23c0: 73 69 7a 65 20 2d 20 34 20 62 79 74 65 73 29 2e  size - 4 bytes).
23d0: 20 20 54 68 65 20 6c 61 73 74 20 70 61 67 65 20    The last page 
23e0: 63 61 6e 20 68 61 76 65 20 61 73 20 6c 69 74 74  can have as litt
23f0: 6c 65 0a 2a 2a 20 61 73 20 31 20 62 79 74 65 20  le.** as 1 byte 
2400: 6f 66 20 64 61 74 61 2e 0a 2a 2a 0a 2a 2a 20 20  of data..**.**  
2410: 20 20 53 49 5a 45 20 20 20 20 44 45 53 43 52 49    SIZE    DESCRI
2420: 50 54 49 4f 4e 0a 2a 2a 20 20 20 20 20 20 34 20  PTION.**      4 
2430: 20 20 20 20 50 61 67 65 20 6e 75 6d 62 65 72 20      Page number 
2440: 6f 66 20 6e 65 78 74 20 6f 76 65 72 66 6c 6f 77  of next overflow
2450: 20 70 61 67 65 0a 2a 2a 20 20 20 20 20 20 2a 20   page.**      * 
2460: 20 20 20 20 44 61 74 61 0a 2a 2a 0a 2a 2a 20 46      Data.**.** F
2470: 72 65 65 6c 69 73 74 20 70 61 67 65 73 20 63 6f  reelist pages co
2480: 6d 65 20 69 6e 20 74 77 6f 20 73 75 62 74 79 70  me in two subtyp
2490: 65 73 3a 20 74 72 75 6e 6b 20 70 61 67 65 73 20  es: trunk pages 
24a0: 61 6e 64 20 6c 65 61 66 20 70 61 67 65 73 2e 20  and leaf pages. 
24b0: 20 54 68 65 0a 2a 2a 20 66 69 6c 65 20 68 65 61   The.** file hea
24c0: 64 65 72 20 70 6f 69 6e 74 73 20 74 6f 20 74 68  der points to th
24d0: 65 20 66 69 72 73 74 20 69 6e 20 61 20 6c 69 6e  e first in a lin
24e0: 6b 65 64 20 6c 69 73 74 20 6f 66 20 74 72 75 6e  ked list of trun
24f0: 6b 20 70 61 67 65 2e 20 20 45 61 63 68 20 74 72  k page.  Each tr
2500: 75 6e 6b 0a 2a 2a 20 70 61 67 65 20 70 6f 69 6e  unk.** page poin
2510: 74 73 20 74 6f 20 6d 75 6c 74 69 70 6c 65 20 6c  ts to multiple l
2520: 65 61 66 20 70 61 67 65 73 2e 20 20 54 68 65 20  eaf pages.  The 
2530: 63 6f 6e 74 65 6e 74 20 6f 66 20 61 20 6c 65 61  content of a lea
2540: 66 20 70 61 67 65 20 69 73 0a 2a 2a 20 75 6e 73  f page is.** uns
2550: 70 65 63 69 66 69 65 64 2e 20 20 41 20 74 72 75  pecified.  A tru
2560: 6e 6b 20 70 61 67 65 20 6c 6f 6f 6b 73 20 6c 69  nk page looks li
2570: 6b 65 20 74 68 69 73 3a 0a 2a 2a 0a 2a 2a 20 20  ke this:.**.**  
2580: 20 20 53 49 5a 45 20 20 20 20 44 45 53 43 52 49    SIZE    DESCRI
2590: 50 54 49 4f 4e 0a 2a 2a 20 20 20 20 20 20 34 20  PTION.**      4 
25a0: 20 20 20 20 50 61 67 65 20 6e 75 6d 62 65 72 20      Page number 
25b0: 6f 66 20 6e 65 78 74 20 74 72 75 6e 6b 20 70 61  of next trunk pa
25c0: 67 65 0a 2a 2a 20 20 20 20 20 20 34 20 20 20 20  ge.**      4    
25d0: 20 4e 75 6d 62 65 72 20 6f 66 20 6c 65 61 66 20   Number of leaf 
25e0: 70 6f 69 6e 74 65 72 73 20 6f 6e 20 74 68 69 73  pointers on this
25f0: 20 70 61 67 65 0a 2a 2a 20 20 20 20 20 20 2a 20   page.**      * 
2600: 20 20 20 20 7a 65 72 6f 20 6f 72 20 6d 6f 72 65      zero or more
2610: 20 70 61 67 65 73 20 6e 75 6d 62 65 72 73 20 6f   pages numbers o
2620: 66 20 6c 65 61 76 65 73 0a 2a 2f 0a 23 69 6e 63  f leaves.*/.#inc
2630: 6c 75 64 65 20 22 73 71 6c 69 74 65 49 6e 74 2e  lude "sqliteInt.
2640: 68 22 0a 23 69 6e 63 6c 75 64 65 20 22 70 61 67  h".#include "pag
2650: 65 72 2e 68 22 0a 23 69 6e 63 6c 75 64 65 20 22  er.h".#include "
2660: 62 74 72 65 65 2e 68 22 0a 23 69 6e 63 6c 75 64  btree.h".#includ
2670: 65 20 22 6f 73 2e 68 22 0a 23 69 6e 63 6c 75 64  e "os.h".#includ
2680: 65 20 3c 61 73 73 65 72 74 2e 68 3e 0a 0a 2f 2a  e <assert.h>../*
2690: 20 52 6f 75 6e 64 20 75 70 20 61 20 6e 75 6d 62   Round up a numb
26a0: 65 72 20 74 6f 20 74 68 65 20 6e 65 78 74 20 6c  er to the next l
26b0: 61 72 67 65 72 20 6d 75 6c 74 69 70 6c 65 20 6f  arger multiple o
26c0: 66 20 38 2e 20 20 54 68 69 73 20 69 73 20 75 73  f 8.  This is us
26d0: 65 64 0a 2a 2a 20 74 6f 20 66 6f 72 63 65 20 38  ed.** to force 8
26e0: 2d 62 79 74 65 20 61 6c 69 67 6e 6d 65 6e 74 20  -byte alignment 
26f0: 6f 6e 20 36 34 2d 62 69 74 20 61 72 63 68 69 74  on 64-bit archit
2700: 65 63 74 75 72 65 73 2e 0a 2a 2f 0a 23 64 65 66  ectures..*/.#def
2710: 69 6e 65 20 52 4f 55 4e 44 38 28 78 29 20 20 20  ine ROUND8(x)   
2720: 28 28 78 2b 37 29 26 7e 37 29 0a 0a 0a 2f 2a 20  ((x+7)&~7).../* 
2730: 54 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 20 76 61  The following va
2740: 6c 75 65 20 69 73 20 74 68 65 20 6d 61 78 69 6d  lue is the maxim
2750: 75 6d 20 63 65 6c 6c 20 73 69 7a 65 20 61 73 73  um cell size ass
2760: 75 6d 69 6e 67 20 61 20 6d 61 78 69 6d 75 6d 20  uming a maximum 
2770: 70 61 67 65 0a 2a 2a 20 73 69 7a 65 20 67 69 76  page.** size giv
2780: 65 20 61 62 6f 76 65 2e 0a 2a 2f 0a 23 64 65 66  e above..*/.#def
2790: 69 6e 65 20 4d 58 5f 43 45 4c 4c 5f 53 49 5a 45  ine MX_CELL_SIZE
27a0: 28 70 42 74 29 20 20 28 70 42 74 2d 3e 70 61 67  (pBt)  (pBt->pag
27b0: 65 53 69 7a 65 2d 38 29 0a 0a 2f 2a 20 54 68 65  eSize-8)../* The
27c0: 20 6d 61 78 69 6d 75 6d 20 6e 75 6d 62 65 72 20   maximum number 
27d0: 6f 66 20 63 65 6c 6c 73 20 6f 6e 20 61 20 73 69  of cells on a si
27e0: 6e 67 6c 65 20 70 61 67 65 20 6f 66 20 74 68 65  ngle page of the
27f0: 20 64 61 74 61 62 61 73 65 2e 20 20 54 68 69 73   database.  This
2800: 0a 2a 2a 20 61 73 73 75 6d 65 73 20 61 20 6d 69  .** assumes a mi
2810: 6e 69 6d 75 6d 20 63 65 6c 6c 20 73 69 7a 65 20  nimum cell size 
2820: 6f 66 20 36 20 62 79 74 65 73 20 20 28 34 20 62  of 6 bytes  (4 b
2830: 79 74 65 73 20 66 6f 72 20 74 68 65 20 63 65 6c  ytes for the cel
2840: 6c 20 69 74 73 65 6c 66 0a 2a 2a 20 70 6c 75 73  l itself.** plus
2850: 20 32 20 62 79 74 65 73 20 66 6f 72 20 74 68 65   2 bytes for the
2860: 20 69 6e 64 65 78 20 74 6f 20 74 68 65 20 63 65   index to the ce
2870: 6c 6c 20 69 6e 20 74 68 65 20 70 61 67 65 20 68  ll in the page h
2880: 65 61 64 65 72 29 2e 20 20 53 75 63 68 0a 2a 2a  eader).  Such.**
2890: 20 73 6d 61 6c 6c 20 63 65 6c 6c 73 20 77 69 6c   small cells wil
28a0: 6c 20 62 65 20 72 61 72 65 2c 20 62 75 74 20 74  l be rare, but t
28b0: 68 65 79 20 61 72 65 20 70 6f 73 73 69 62 6c 65  hey are possible
28c0: 2e 0a 2a 2f 0a 23 64 65 66 69 6e 65 20 4d 58 5f  ..*/.#define MX_
28d0: 43 45 4c 4c 28 70 42 74 29 20 28 28 70 42 74 2d  CELL(pBt) ((pBt-
28e0: 3e 70 61 67 65 53 69 7a 65 2d 38 29 2f 36 29 0a  >pageSize-8)/6).
28f0: 0a 2f 2a 20 46 6f 72 77 61 72 64 20 64 65 63 6c  ./* Forward decl
2900: 61 72 61 74 69 6f 6e 73 20 2a 2f 0a 74 79 70 65  arations */.type
2910: 64 65 66 20 73 74 72 75 63 74 20 4d 65 6d 50 61  def struct MemPa
2920: 67 65 20 4d 65 6d 50 61 67 65 3b 0a 74 79 70 65  ge MemPage;.type
2930: 64 65 66 20 73 74 72 75 63 74 20 42 74 4c 6f 63  def struct BtLoc
2940: 6b 20 42 74 4c 6f 63 6b 3b 0a 0a 2f 2a 0a 2a 2a  k BtLock;../*.**
2950: 20 54 68 69 73 20 69 73 20 61 20 6d 61 67 69 63   This is a magic
2960: 20 73 74 72 69 6e 67 20 74 68 61 74 20 61 70 70   string that app
2970: 65 61 72 73 20 61 74 20 74 68 65 20 62 65 67 69  ears at the begi
2980: 6e 6e 69 6e 67 20 6f 66 20 65 76 65 72 79 0a 2a  nning of every.*
2990: 2a 20 53 51 4c 69 74 65 20 64 61 74 61 62 61 73  * SQLite databas
29a0: 65 20 69 6e 20 6f 72 64 65 72 20 74 6f 20 69 64  e in order to id
29b0: 65 6e 74 69 66 79 20 74 68 65 20 66 69 6c 65 20  entify the file 
29c0: 61 73 20 61 20 72 65 61 6c 20 64 61 74 61 62 61  as a real databa
29d0: 73 65 2e 0a 2a 2a 0a 2a 2a 20 59 6f 75 20 63 61  se..**.** You ca
29e0: 6e 20 63 68 61 6e 67 65 20 74 68 69 73 20 76 61  n change this va
29f0: 6c 75 65 20 61 74 20 63 6f 6d 70 69 6c 65 2d 74  lue at compile-t
2a00: 69 6d 65 20 62 79 20 73 70 65 63 69 66 79 69 6e  ime by specifyin
2a10: 67 20 61 0a 2a 2a 20 2d 44 53 51 4c 49 54 45 5f  g a.** -DSQLITE_
2a20: 46 49 4c 45 5f 48 45 41 44 45 52 3d 22 2e 2e 2e  FILE_HEADER="...
2a30: 22 20 6f 6e 20 74 68 65 20 63 6f 6d 70 69 6c 65  " on the compile
2a40: 72 20 63 6f 6d 6d 61 6e 64 2d 6c 69 6e 65 2e 20  r command-line. 
2a50: 20 54 68 65 0a 2a 2a 20 68 65 61 64 65 72 20 6d   The.** header m
2a60: 75 73 74 20 62 65 20 65 78 61 63 74 6c 79 20 31  ust be exactly 1
2a70: 36 20 62 79 74 65 73 20 69 6e 63 6c 75 64 69 6e  6 bytes includin
2a80: 67 20 74 68 65 20 7a 65 72 6f 2d 74 65 72 6d 69  g the zero-termi
2a90: 6e 61 74 6f 72 20 73 6f 0a 2a 2a 20 74 68 65 20  nator so.** the 
2aa0: 73 74 72 69 6e 67 20 69 74 73 65 6c 66 20 73 68  string itself sh
2ab0: 6f 75 6c 64 20 62 65 20 31 35 20 63 68 61 72 61  ould be 15 chara
2ac0: 63 74 65 72 73 20 6c 6f 6e 67 2e 20 20 49 66 20  cters long.  If 
2ad0: 79 6f 75 20 63 68 61 6e 67 65 0a 2a 2a 20 74 68  you change.** th
2ae0: 65 20 68 65 61 64 65 72 2c 20 74 68 65 6e 20 79  e header, then y
2af0: 6f 75 72 20 63 75 73 74 6f 6d 20 6c 69 62 72 61  our custom libra
2b00: 72 79 20 77 69 6c 6c 20 6e 6f 74 20 62 65 20 61  ry will not be a
2b10: 62 6c 65 20 74 6f 20 72 65 61 64 20 0a 2a 2a 20  ble to read .** 
2b20: 64 61 74 61 62 61 73 65 73 20 67 65 6e 65 72 61  databases genera
2b30: 74 65 64 20 62 79 20 74 68 65 20 73 74 61 6e 64  ted by the stand
2b40: 61 72 64 20 74 6f 6f 6c 73 20 61 6e 64 20 74 68  ard tools and th
2b50: 65 20 73 74 61 6e 64 61 72 64 20 74 6f 6f 6c 73  e standard tools
2b60: 0a 2a 2a 20 77 69 6c 6c 20 6e 6f 74 20 62 65 20  .** will not be 
2b70: 61 62 6c 65 20 74 6f 20 72 65 61 64 20 64 61 74  able to read dat
2b80: 61 62 61 73 65 73 20 63 72 65 61 74 65 64 20 62  abases created b
2b90: 79 20 79 6f 75 72 20 63 75 73 74 6f 6d 20 6c 69  y your custom li
2ba0: 62 72 61 72 79 2e 0a 2a 2f 0a 23 69 66 6e 64 65  brary..*/.#ifnde
2bb0: 66 20 53 51 4c 49 54 45 5f 46 49 4c 45 5f 48 45  f SQLITE_FILE_HE
2bc0: 41 44 45 52 20 2f 2a 20 31 32 33 34 35 36 37 38  ADER /* 12345678
2bd0: 39 20 31 32 33 34 35 36 20 2a 2f 0a 23 20 20 64  9 123456 */.#  d
2be0: 65 66 69 6e 65 20 53 51 4c 49 54 45 5f 46 49 4c  efine SQLITE_FIL
2bf0: 45 5f 48 45 41 44 45 52 20 22 53 51 4c 69 74 65  E_HEADER "SQLite
2c00: 20 66 6f 72 6d 61 74 20 33 22 0a 23 65 6e 64 69   format 3".#endi
2c10: 66 0a 0a 2f 2a 0a 2a 2a 20 50 61 67 65 20 74 79  f../*.** Page ty
2c20: 70 65 20 66 6c 61 67 73 2e 20 20 41 6e 20 4f 52  pe flags.  An OR
2c30: 65 64 20 63 6f 6d 62 69 6e 61 74 69 6f 6e 20 6f  ed combination o
2c40: 66 20 74 68 65 73 65 20 66 6c 61 67 73 20 61 70  f these flags ap
2c50: 70 65 61 72 20 61 73 20 74 68 65 0a 2a 2a 20 66  pear as the.** f
2c60: 69 72 73 74 20 62 79 74 65 20 6f 66 20 6f 6e 2d  irst byte of on-
2c70: 64 69 73 6b 20 69 6d 61 67 65 20 6f 66 20 65 76  disk image of ev
2c80: 65 72 79 20 42 54 72 65 65 20 70 61 67 65 2e 0a  ery BTree page..
2c90: 2a 2f 0a 23 64 65 66 69 6e 65 20 50 54 46 5f 49  */.#define PTF_I
2ca0: 4e 54 4b 45 59 20 20 20 20 30 78 30 31 0a 23 64  NTKEY    0x01.#d
2cb0: 65 66 69 6e 65 20 50 54 46 5f 5a 45 52 4f 44 41  efine PTF_ZERODA
2cc0: 54 41 20 20 30 78 30 32 0a 23 64 65 66 69 6e 65  TA  0x02.#define
2cd0: 20 50 54 46 5f 4c 45 41 46 44 41 54 41 20 20 30   PTF_LEAFDATA  0
2ce0: 78 30 34 0a 23 64 65 66 69 6e 65 20 50 54 46 5f  x04.#define PTF_
2cf0: 4c 45 41 46 20 20 20 20 20 20 30 78 30 38 0a 0a  LEAF      0x08..
2d00: 2f 2a 0a 2a 2a 20 41 73 20 65 61 63 68 20 70 61  /*.** As each pa
2d10: 67 65 20 6f 66 20 74 68 65 20 66 69 6c 65 20 69  ge of the file i
2d20: 73 20 6c 6f 61 64 65 64 20 69 6e 74 6f 20 6d 65  s loaded into me
2d30: 6d 6f 72 79 2c 20 61 6e 20 69 6e 73 74 61 6e 63  mory, an instanc
2d40: 65 20 6f 66 20 74 68 65 20 66 6f 6c 6c 6f 77 69  e of the followi
2d50: 6e 67 0a 2a 2a 20 73 74 72 75 63 74 75 72 65 20  ng.** structure 
2d60: 69 73 20 61 70 70 65 6e 64 65 64 20 61 6e 64 20  is appended and 
2d70: 69 6e 69 74 69 61 6c 69 7a 65 64 20 74 6f 20 7a  initialized to z
2d80: 65 72 6f 2e 20 20 54 68 69 73 20 73 74 72 75 63  ero.  This struc
2d90: 74 75 72 65 20 73 74 6f 72 65 73 0a 2a 2a 20 69  ture stores.** i
2da0: 6e 66 6f 72 6d 61 74 69 6f 6e 20 61 62 6f 75 74  nformation about
2db0: 20 74 68 65 20 70 61 67 65 20 74 68 61 74 20 69   the page that i
2dc0: 73 20 64 65 63 6f 64 65 64 20 66 72 6f 6d 20 74  s decoded from t
2dd0: 68 65 20 72 61 77 20 66 69 6c 65 20 70 61 67 65  he raw file page
2de0: 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 70 50 61 72  ..**.** The pPar
2df0: 65 6e 74 20 66 69 65 6c 64 20 70 6f 69 6e 74 73  ent field points
2e00: 20 62 61 63 6b 20 74 6f 20 74 68 65 20 70 61 72   back to the par
2e10: 65 6e 74 20 70 61 67 65 2e 20 20 54 68 69 73 20  ent page.  This 
2e20: 61 6c 6c 6f 77 73 20 75 73 20 74 6f 0a 2a 2a 20  allows us to.** 
2e30: 77 61 6c 6b 20 75 70 20 74 68 65 20 42 54 72 65  walk up the BTre
2e40: 65 20 66 72 6f 6d 20 61 6e 79 20 6c 65 61 66 20  e from any leaf 
2e50: 74 6f 20 74 68 65 20 72 6f 6f 74 2e 20 20 43 61  to the root.  Ca
2e60: 72 65 20 6d 75 73 74 20 62 65 20 74 61 6b 65 6e  re must be taken
2e70: 20 74 6f 0a 2a 2a 20 75 6e 72 65 66 28 29 20 74   to.** unref() t
2e80: 68 65 20 70 61 72 65 6e 74 20 70 61 67 65 20 70  he parent page p
2e90: 6f 69 6e 74 65 72 20 77 68 65 6e 20 74 68 69 73  ointer when this
2ea0: 20 70 61 67 65 20 69 73 20 6e 6f 20 6c 6f 6e 67   page is no long
2eb0: 65 72 20 72 65 66 65 72 65 6e 63 65 64 2e 0a 2a  er referenced..*
2ec0: 2a 20 54 68 65 20 70 61 67 65 44 65 73 74 72 75  * The pageDestru
2ed0: 63 74 6f 72 28 29 20 72 6f 75 74 69 6e 65 20 68  ctor() routine h
2ee0: 61 6e 64 6c 65 73 20 74 68 61 74 20 63 68 6f 72  andles that chor
2ef0: 65 2e 0a 2a 2a 0a 2a 2a 20 41 63 63 65 73 73 20  e..**.** Access 
2f00: 74 6f 20 61 6c 6c 20 66 69 65 6c 64 73 20 6f 66  to all fields of
2f10: 20 74 68 69 73 20 73 74 72 75 63 74 75 72 65 20   this structure 
2f20: 69 73 20 63 6f 6e 74 72 6f 6c 6c 65 64 20 62 79  is controlled by
2f30: 20 74 68 65 20 6d 75 74 65 78 0a 2a 2a 20 73 74   the mutex.** st
2f40: 6f 72 65 64 20 69 6e 20 4d 65 6d 50 61 67 65 2e  ored in MemPage.
2f50: 70 42 74 2d 3e 6d 75 74 65 78 2e 0a 2a 2f 0a 73  pBt->mutex..*/.s
2f60: 74 72 75 63 74 20 4d 65 6d 50 61 67 65 20 7b 0a  truct MemPage {.
2f70: 20 20 75 38 20 69 73 49 6e 69 74 3b 20 20 20 20    u8 isInit;    
2f80: 20 20 20 20 20 20 20 2f 2a 20 54 72 75 65 20 69         /* True i
2f90: 66 20 70 72 65 76 69 6f 75 73 6c 79 20 69 6e 69  f previously ini
2fa0: 74 69 61 6c 69 7a 65 64 2e 20 4d 55 53 54 20 42  tialized. MUST B
2fb0: 45 20 46 49 52 53 54 21 20 2a 2f 0a 20 20 75 38  E FIRST! */.  u8
2fc0: 20 6e 4f 76 65 72 66 6c 6f 77 3b 20 20 20 20 20   nOverflow;     
2fd0: 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20     /* Number of 
2fe0: 6f 76 65 72 66 6c 6f 77 20 63 65 6c 6c 20 62 6f  overflow cell bo
2ff0: 64 69 65 73 20 69 6e 20 61 43 65 6c 6c 5b 5d 20  dies in aCell[] 
3000: 2a 2f 0a 20 20 75 38 20 69 6e 74 4b 65 79 3b 20  */.  u8 intKey; 
3010: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 54 72 75            /* Tru
3020: 65 20 69 66 20 69 6e 74 6b 65 79 20 66 6c 61 67  e if intkey flag
3030: 20 69 73 20 73 65 74 20 2a 2f 0a 20 20 75 38 20   is set */.  u8 
3040: 6c 65 61 66 3b 20 20 20 20 20 20 20 20 20 20 20  leaf;           
3050: 20 20 2f 2a 20 54 72 75 65 20 69 66 20 6c 65 61    /* True if lea
3060: 66 20 66 6c 61 67 20 69 73 20 73 65 74 20 2a 2f  f flag is set */
3070: 0a 20 20 75 38 20 68 61 73 44 61 74 61 3b 20 20  .  u8 hasData;  
3080: 20 20 20 20 20 20 20 20 2f 2a 20 54 72 75 65 20          /* True 
3090: 69 66 20 74 68 69 73 20 70 61 67 65 20 73 74 6f  if this page sto
30a0: 72 65 73 20 64 61 74 61 20 2a 2f 0a 20 20 75 38  res data */.  u8
30b0: 20 68 64 72 4f 66 66 73 65 74 3b 20 20 20 20 20   hdrOffset;     
30c0: 20 20 20 2f 2a 20 31 30 30 20 66 6f 72 20 70 61     /* 100 for pa
30d0: 67 65 20 31 2e 20 20 30 20 6f 74 68 65 72 77 69  ge 1.  0 otherwi
30e0: 73 65 20 2a 2f 0a 20 20 75 38 20 63 68 69 6c 64  se */.  u8 child
30f0: 50 74 72 53 69 7a 65 3b 20 20 20 20 20 2f 2a 20  PtrSize;     /* 
3100: 30 20 69 66 20 6c 65 61 66 3d 3d 31 2e 20 20 34  0 if leaf==1.  4
3110: 20 69 66 20 6c 65 61 66 3d 3d 30 20 2a 2f 0a 20   if leaf==0 */. 
3120: 20 75 31 36 20 6d 61 78 4c 6f 63 61 6c 3b 20 20   u16 maxLocal;  
3130: 20 20 20 20 20 20 2f 2a 20 43 6f 70 79 20 6f 66        /* Copy of
3140: 20 42 74 53 68 61 72 65 64 2e 6d 61 78 4c 6f 63   BtShared.maxLoc
3150: 61 6c 20 6f 72 20 42 74 53 68 61 72 65 64 2e 6d  al or BtShared.m
3160: 61 78 4c 65 61 66 20 2a 2f 0a 20 20 75 31 36 20  axLeaf */.  u16 
3170: 6d 69 6e 4c 6f 63 61 6c 3b 20 20 20 20 20 20 20  minLocal;       
3180: 20 2f 2a 20 43 6f 70 79 20 6f 66 20 42 74 53 68   /* Copy of BtSh
3190: 61 72 65 64 2e 6d 69 6e 4c 6f 63 61 6c 20 6f 72  ared.minLocal or
31a0: 20 42 74 53 68 61 72 65 64 2e 6d 69 6e 4c 65 61   BtShared.minLea
31b0: 66 20 2a 2f 0a 20 20 75 31 36 20 63 65 6c 6c 4f  f */.  u16 cellO
31c0: 66 66 73 65 74 3b 20 20 20 20 20 20 2f 2a 20 49  ffset;      /* I
31d0: 6e 64 65 78 20 69 6e 20 61 44 61 74 61 20 6f 66  ndex in aData of
31e0: 20 66 69 72 73 74 20 63 65 6c 6c 20 70 6f 69 6e   first cell poin
31f0: 74 65 72 20 2a 2f 0a 20 20 75 31 36 20 6e 46 72  ter */.  u16 nFr
3200: 65 65 3b 20 20 20 20 20 20 20 20 20 20 20 2f 2a  ee;           /*
3210: 20 4e 75 6d 62 65 72 20 6f 66 20 66 72 65 65 20   Number of free 
3220: 62 79 74 65 73 20 6f 6e 20 74 68 65 20 70 61 67  bytes on the pag
3230: 65 20 2a 2f 0a 20 20 75 31 36 20 6e 43 65 6c 6c  e */.  u16 nCell
3240: 3b 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4e  ;           /* N
3250: 75 6d 62 65 72 20 6f 66 20 63 65 6c 6c 73 20 6f  umber of cells o
3260: 6e 20 74 68 69 73 20 70 61 67 65 2c 20 6c 6f 63  n this page, loc
3270: 61 6c 20 61 6e 64 20 6f 76 66 6c 20 2a 2f 0a 20  al and ovfl */. 
3280: 20 75 31 36 20 6d 61 73 6b 50 61 67 65 3b 20 20   u16 maskPage;  
3290: 20 20 20 20 20 20 2f 2a 20 4d 61 73 6b 20 66 6f        /* Mask fo
32a0: 72 20 70 61 67 65 20 6f 66 66 73 65 74 20 2a 2f  r page offset */
32b0: 0a 20 20 73 74 72 75 63 74 20 5f 4f 76 66 6c 43  .  struct _OvflC
32c0: 65 6c 6c 20 7b 20 20 20 2f 2a 20 43 65 6c 6c 73  ell {   /* Cells
32d0: 20 74 68 61 74 20 77 69 6c 6c 20 6e 6f 74 20 66   that will not f
32e0: 69 74 20 6f 6e 20 61 44 61 74 61 5b 5d 20 2a 2f  it on aData[] */
32f0: 0a 20 20 20 20 75 38 20 2a 70 43 65 6c 6c 3b 20  .    u8 *pCell; 
3300: 20 20 20 20 20 20 20 20 20 2f 2a 20 50 6f 69 6e           /* Poin
3310: 74 65 72 73 20 74 6f 20 74 68 65 20 62 6f 64 79  ters to the body
3320: 20 6f 66 20 74 68 65 20 6f 76 65 72 66 6c 6f 77   of the overflow
3330: 20 63 65 6c 6c 20 2a 2f 0a 20 20 20 20 75 31 36   cell */.    u16
3340: 20 69 64 78 3b 20 20 20 20 20 20 20 20 20 20 20   idx;           
3350: 20 2f 2a 20 49 6e 73 65 72 74 20 74 68 69 73 20   /* Insert this 
3360: 63 65 6c 6c 20 62 65 66 6f 72 65 20 69 64 78 2d  cell before idx-
3370: 74 68 20 6e 6f 6e 2d 6f 76 65 72 66 6c 6f 77 20  th non-overflow 
3380: 63 65 6c 6c 20 2a 2f 0a 20 20 7d 20 61 4f 76 66  cell */.  } aOvf
3390: 6c 5b 35 5d 3b 0a 20 20 42 74 53 68 61 72 65 64  l[5];.  BtShared
33a0: 20 2a 70 42 74 3b 20 20 20 20 20 20 20 2f 2a 20   *pBt;       /* 
33b0: 50 6f 69 6e 74 65 72 20 74 6f 20 42 74 53 68 61  Pointer to BtSha
33c0: 72 65 64 20 74 68 61 74 20 74 68 69 73 20 70 61  red that this pa
33d0: 67 65 20 69 73 20 70 61 72 74 20 6f 66 20 2a 2f  ge is part of */
33e0: 0a 20 20 75 38 20 2a 61 44 61 74 61 3b 20 20 20  .  u8 *aData;   
33f0: 20 20 20 20 20 20 20 20 2f 2a 20 50 6f 69 6e 74          /* Point
3400: 65 72 20 74 6f 20 64 69 73 6b 20 69 6d 61 67 65  er to disk image
3410: 20 6f 66 20 74 68 65 20 70 61 67 65 20 64 61 74   of the page dat
3420: 61 20 2a 2f 0a 20 20 44 62 50 61 67 65 20 2a 70  a */.  DbPage *p
3430: 44 62 50 61 67 65 3b 20 20 20 20 20 2f 2a 20 50  DbPage;     /* P
3440: 61 67 65 72 20 70 61 67 65 20 68 61 6e 64 6c 65  ager page handle
3450: 20 2a 2f 0a 20 20 50 67 6e 6f 20 70 67 6e 6f 3b   */.  Pgno pgno;
3460: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 50 61             /* Pa
3470: 67 65 20 6e 75 6d 62 65 72 20 66 6f 72 20 74 68  ge number for th
3480: 69 73 20 70 61 67 65 20 2a 2f 0a 7d 3b 0a 0a 2f  is page */.};../
3490: 2a 0a 2a 2a 20 54 68 65 20 69 6e 2d 6d 65 6d 6f  *.** The in-memo
34a0: 72 79 20 69 6d 61 67 65 20 6f 66 20 61 20 64 69  ry image of a di
34b0: 73 6b 20 70 61 67 65 20 68 61 73 20 74 68 65 20  sk page has the 
34c0: 61 75 78 69 6c 69 61 72 79 20 69 6e 66 6f 72 6d  auxiliary inform
34d0: 61 74 69 6f 6e 20 61 70 70 65 6e 64 65 64 0a 2a  ation appended.*
34e0: 2a 20 74 6f 20 74 68 65 20 65 6e 64 2e 20 20 45  * to the end.  E
34f0: 58 54 52 41 5f 53 49 5a 45 20 69 73 20 74 68 65  XTRA_SIZE is the
3500: 20 6e 75 6d 62 65 72 20 6f 66 20 62 79 74 65 73   number of bytes
3510: 20 6f 66 20 73 70 61 63 65 20 6e 65 65 64 65 64   of space needed
3520: 20 74 6f 20 68 6f 6c 64 0a 2a 2a 20 74 68 61 74   to hold.** that
3530: 20 65 78 74 72 61 20 69 6e 66 6f 72 6d 61 74 69   extra informati
3540: 6f 6e 2e 0a 2a 2f 0a 23 64 65 66 69 6e 65 20 45  on..*/.#define E
3550: 58 54 52 41 5f 53 49 5a 45 20 73 69 7a 65 6f 66  XTRA_SIZE sizeof
3560: 28 4d 65 6d 50 61 67 65 29 0a 0a 2f 2a 20 41 20  (MemPage)../* A 
3570: 42 74 72 65 65 20 68 61 6e 64 6c 65 0a 2a 2a 0a  Btree handle.**.
3580: 2a 2a 20 41 20 64 61 74 61 62 61 73 65 20 63 6f  ** A database co
3590: 6e 6e 65 63 74 69 6f 6e 20 63 6f 6e 74 61 69 6e  nnection contain
35a0: 73 20 61 20 70 6f 69 6e 74 65 72 20 74 6f 20 61  s a pointer to a
35b0: 6e 20 69 6e 73 74 61 6e 63 65 20 6f 66 0a 2a 2a  n instance of.**
35c0: 20 74 68 69 73 20 6f 62 6a 65 63 74 20 66 6f 72   this object for
35d0: 20 65 76 65 72 79 20 64 61 74 61 62 61 73 65 20   every database 
35e0: 66 69 6c 65 20 74 68 61 74 20 69 74 20 68 61 73  file that it has
35f0: 20 6f 70 65 6e 2e 20 20 54 68 69 73 20 73 74 72   open.  This str
3600: 75 63 74 75 72 65 0a 2a 2a 20 69 73 20 6f 70 61  ucture.** is opa
3610: 71 75 65 20 74 6f 20 74 68 65 20 64 61 74 61 62  que to the datab
3620: 61 73 65 20 63 6f 6e 6e 65 63 74 69 6f 6e 2e 20  ase connection. 
3630: 20 54 68 65 20 64 61 74 61 62 61 73 65 20 63 6f   The database co
3640: 6e 6e 65 63 74 69 6f 6e 20 63 61 6e 6e 6f 74 0a  nnection cannot.
3650: 2a 2a 20 73 65 65 20 74 68 65 20 69 6e 74 65 72  ** see the inter
3660: 6e 61 6c 73 20 6f 66 20 74 68 69 73 20 73 74 72  nals of this str
3670: 75 63 74 75 72 65 20 61 6e 64 20 6f 6e 6c 79 20  ucture and only 
3680: 64 65 61 6c 73 20 77 69 74 68 20 70 6f 69 6e 74  deals with point
3690: 65 72 73 20 74 6f 0a 2a 2a 20 74 68 69 73 20 73  ers to.** this s
36a0: 74 72 75 63 74 75 72 65 2e 0a 2a 2a 0a 2a 2a 20  tructure..**.** 
36b0: 46 6f 72 20 73 6f 6d 65 20 64 61 74 61 62 61 73  For some databas
36c0: 65 20 66 69 6c 65 73 2c 20 74 68 65 20 73 61 6d  e files, the sam
36d0: 65 20 75 6e 64 65 72 6c 79 69 6e 67 20 64 61 74  e underlying dat
36e0: 61 62 61 73 65 20 63 61 63 68 65 20 6d 69 67 68  abase cache migh
36f0: 74 20 62 65 20 0a 2a 2a 20 73 68 61 72 65 64 20  t be .** shared 
3700: 62 65 74 77 65 65 6e 20 6d 75 6c 74 69 70 6c 65  between multiple
3710: 20 63 6f 6e 6e 65 63 74 69 6f 6e 73 2e 20 20 49   connections.  I
3720: 6e 20 74 68 61 74 20 63 61 73 65 2c 20 65 61 63  n that case, eac
3730: 68 20 63 6f 6e 74 65 63 74 69 6f 6e 0a 2a 2a 20  h contection.** 
3740: 68 61 73 20 69 74 20 6f 77 6e 20 70 6f 69 6e 74  has it own point
3750: 65 72 20 74 6f 20 74 68 69 73 20 6f 62 6a 65 63  er to this objec
3760: 74 2e 20 20 42 75 74 20 65 61 63 68 20 69 6e 73  t.  But each ins
3770: 74 61 6e 63 65 20 6f 66 20 74 68 69 73 20 6f 62  tance of this ob
3780: 6a 65 63 74 0a 2a 2a 20 70 6f 69 6e 74 73 20 74  ject.** points t
3790: 6f 20 74 68 65 20 73 61 6d 65 20 42 74 53 68 61  o the same BtSha
37a0: 72 65 64 20 6f 62 6a 65 63 74 2e 20 20 54 68 65  red object.  The
37b0: 20 64 61 74 61 62 61 73 65 20 63 61 63 68 65 20   database cache 
37c0: 61 6e 64 20 74 68 65 0a 2a 2a 20 73 63 68 65 6d  and the.** schem
37d0: 61 20 61 73 73 6f 63 69 61 74 65 64 20 77 69 74  a associated wit
37e0: 68 20 74 68 65 20 64 61 74 61 62 61 73 65 20 66  h the database f
37f0: 69 6c 65 20 61 72 65 20 61 6c 6c 20 63 6f 6e 74  ile are all cont
3800: 61 69 6e 65 64 20 77 69 74 68 69 6e 0a 2a 2a 20  ained within.** 
3810: 74 68 65 20 42 74 53 68 61 72 65 64 20 6f 62 6a  the BtShared obj
3820: 65 63 74 2e 0a 2a 2a 0a 2a 2a 20 41 6c 6c 20 66  ect..**.** All f
3830: 69 65 6c 64 73 20 69 6e 20 74 68 69 73 20 73 74  ields in this st
3840: 72 75 63 74 75 72 65 20 61 72 65 20 61 63 63 65  ructure are acce
3850: 73 73 65 64 20 75 6e 64 65 72 20 73 71 6c 69 74  ssed under sqlit
3860: 65 33 2e 6d 75 74 65 78 2e 0a 2a 2a 20 54 68 65  e3.mutex..** The
3870: 20 70 42 74 20 70 6f 69 6e 74 65 72 20 69 74 73   pBt pointer its
3880: 65 6c 66 20 6d 61 79 20 6e 6f 74 20 62 65 20 63  elf may not be c
3890: 68 61 6e 67 65 64 20 77 68 69 6c 65 20 74 68 65  hanged while the
38a0: 72 65 20 65 78 69 73 74 73 20 63 75 72 73 6f 72  re exists cursor
38b0: 73 20 0a 2a 2a 20 69 6e 20 74 68 65 20 72 65 66  s .** in the ref
38c0: 65 72 65 6e 63 65 64 20 42 74 53 68 61 72 65 64  erenced BtShared
38d0: 20 74 68 61 74 20 70 6f 69 6e 74 20 62 61 63 6b   that point back
38e0: 20 74 6f 20 74 68 69 73 20 42 74 72 65 65 20 73   to this Btree s
38f0: 69 6e 63 65 20 74 68 6f 73 65 0a 2a 2a 20 63 75  ince those.** cu
3900: 72 73 6f 72 73 20 68 61 76 65 20 74 6f 20 64 6f  rsors have to do
3910: 20 67 6f 20 74 68 72 6f 75 67 68 20 74 68 69 73   go through this
3920: 20 42 74 72 65 65 20 74 6f 20 66 69 6e 64 20 74   Btree to find t
3930: 68 65 69 72 20 42 74 53 68 61 72 65 64 20 61 6e  heir BtShared an
3940: 64 0a 2a 2a 20 74 68 65 79 20 6f 66 74 65 6e 20  d.** they often 
3950: 64 6f 20 73 6f 20 77 69 74 68 6f 75 74 20 68 6f  do so without ho
3960: 6c 64 69 6e 67 20 73 71 6c 69 74 65 33 2e 6d 75  lding sqlite3.mu
3970: 74 65 78 2e 0a 2a 2f 0a 73 74 72 75 63 74 20 42  tex..*/.struct B
3980: 74 72 65 65 20 7b 0a 20 20 73 71 6c 69 74 65 33  tree {.  sqlite3
3990: 20 2a 64 62 3b 20 20 20 20 20 20 20 2f 2a 20 54   *db;       /* T
39a0: 68 65 20 64 61 74 61 62 61 73 65 20 63 6f 6e 6e  he database conn
39b0: 65 63 74 69 6f 6e 20 68 6f 6c 64 69 6e 67 20 74  ection holding t
39c0: 68 69 73 20 62 74 72 65 65 20 2a 2f 0a 20 20 42  his btree */.  B
39d0: 74 53 68 61 72 65 64 20 2a 70 42 74 3b 20 20 20  tShared *pBt;   
39e0: 20 20 2f 2a 20 53 68 61 72 61 62 6c 65 20 63 6f    /* Sharable co
39f0: 6e 74 65 6e 74 20 6f 66 20 74 68 69 73 20 62 74  ntent of this bt
3a00: 72 65 65 20 2a 2f 0a 20 20 75 38 20 69 6e 54 72  ree */.  u8 inTr
3a10: 61 6e 73 3b 20 20 20 20 20 20 20 20 2f 2a 20 54  ans;        /* T
3a20: 52 41 4e 53 5f 4e 4f 4e 45 2c 20 54 52 41 4e 53  RANS_NONE, TRANS
3a30: 5f 52 45 41 44 20 6f 72 20 54 52 41 4e 53 5f 57  _READ or TRANS_W
3a40: 52 49 54 45 20 2a 2f 0a 20 20 75 38 20 73 68 61  RITE */.  u8 sha
3a50: 72 61 62 6c 65 3b 20 20 20 20 20 20 20 2f 2a 20  rable;       /* 
3a60: 54 72 75 65 20 69 66 20 77 65 20 63 61 6e 20 73  True if we can s
3a70: 68 61 72 65 20 70 42 74 20 77 69 74 68 20 61 6e  hare pBt with an
3a80: 6f 74 68 65 72 20 64 62 20 2a 2f 0a 20 20 75 38  other db */.  u8
3a90: 20 6c 6f 63 6b 65 64 3b 20 20 20 20 20 20 20 20   locked;        
3aa0: 20 2f 2a 20 54 72 75 65 20 69 66 20 64 62 20 63   /* True if db c
3ab0: 75 72 72 65 6e 74 6c 79 20 68 61 73 20 70 42 74  urrently has pBt
3ac0: 20 6c 6f 63 6b 65 64 20 2a 2f 0a 20 20 69 6e 74   locked */.  int
3ad0: 20 77 61 6e 74 54 6f 4c 6f 63 6b 3b 20 20 20 20   wantToLock;    
3ae0: 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 6e 65 73  /* Number of nes
3af0: 74 65 64 20 63 61 6c 6c 73 20 74 6f 20 73 71 6c  ted calls to sql
3b00: 69 74 65 33 42 74 72 65 65 45 6e 74 65 72 28 29  ite3BtreeEnter()
3b10: 20 2a 2f 0a 20 20 42 74 72 65 65 20 2a 70 4e 65   */.  Btree *pNe
3b20: 78 74 3b 20 20 20 20 20 20 2f 2a 20 4c 69 73 74  xt;      /* List
3b30: 20 6f 66 20 6f 74 68 65 72 20 73 68 61 72 61 62   of other sharab
3b40: 6c 65 20 42 74 72 65 65 73 20 66 72 6f 6d 20 74  le Btrees from t
3b50: 68 65 20 73 61 6d 65 20 64 62 20 2a 2f 0a 20 20  he same db */.  
3b60: 42 74 72 65 65 20 2a 70 50 72 65 76 3b 20 20 20  Btree *pPrev;   
3b70: 20 20 20 2f 2a 20 42 61 63 6b 20 70 6f 69 6e 74     /* Back point
3b80: 65 72 20 6f 66 20 74 68 65 20 73 61 6d 65 20 6c  er of the same l
3b90: 69 73 74 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a  ist */.};../*.**
3ba0: 20 42 74 72 65 65 2e 69 6e 54 72 61 6e 73 20 6d   Btree.inTrans m
3bb0: 61 79 20 74 61 6b 65 20 6f 6e 65 20 6f 66 20 74  ay take one of t
3bc0: 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 20 76 61 6c  he following val
3bd0: 75 65 73 2e 0a 2a 2a 0a 2a 2a 20 49 66 20 74 68  ues..**.** If th
3be0: 65 20 73 68 61 72 65 64 2d 64 61 74 61 20 65 78  e shared-data ex
3bf0: 74 65 6e 73 69 6f 6e 20 69 73 20 65 6e 61 62 6c  tension is enabl
3c00: 65 64 2c 20 74 68 65 72 65 20 6d 61 79 20 62 65  ed, there may be
3c10: 20 6d 75 6c 74 69 70 6c 65 20 75 73 65 72 73 0a   multiple users.
3c20: 2a 2a 20 6f 66 20 74 68 65 20 42 74 72 65 65 20  ** of the Btree 
3c30: 73 74 72 75 63 74 75 72 65 2e 20 41 74 20 6d 6f  structure. At mo
3c40: 73 74 20 6f 6e 65 20 6f 66 20 74 68 65 73 65 20  st one of these 
3c50: 6d 61 79 20 6f 70 65 6e 20 61 20 77 72 69 74 65  may open a write
3c60: 20 74 72 61 6e 73 61 63 74 69 6f 6e 2c 0a 2a 2a   transaction,.**
3c70: 20 62 75 74 20 61 6e 79 20 6e 75 6d 62 65 72 20   but any number 
3c80: 6d 61 79 20 68 61 76 65 20 61 63 74 69 76 65 20  may have active 
3c90: 72 65 61 64 20 74 72 61 6e 73 61 63 74 69 6f 6e  read transaction
3ca0: 73 2e 0a 2a 2f 0a 23 64 65 66 69 6e 65 20 54 52  s..*/.#define TR
3cb0: 41 4e 53 5f 4e 4f 4e 45 20 20 30 0a 23 64 65 66  ANS_NONE  0.#def
3cc0: 69 6e 65 20 54 52 41 4e 53 5f 52 45 41 44 20 20  ine TRANS_READ  
3cd0: 31 0a 23 64 65 66 69 6e 65 20 54 52 41 4e 53 5f  1.#define TRANS_
3ce0: 57 52 49 54 45 20 32 0a 0a 2f 2a 0a 2a 2a 20 41  WRITE 2../*.** A
3cf0: 6e 20 69 6e 73 74 61 6e 63 65 20 6f 66 20 74 68  n instance of th
3d00: 69 73 20 6f 62 6a 65 63 74 20 72 65 70 72 65 73  is object repres
3d10: 65 6e 74 73 20 61 20 73 69 6e 67 6c 65 20 64 61  ents a single da
3d20: 74 61 62 61 73 65 20 66 69 6c 65 2e 0a 2a 2a 20  tabase file..** 
3d30: 0a 2a 2a 20 41 20 73 69 6e 67 6c 65 20 64 61 74  .** A single dat
3d40: 61 62 61 73 65 20 66 69 6c 65 20 63 61 6e 20 62  abase file can b
3d50: 65 20 69 6e 20 75 73 65 20 61 73 20 74 68 65 20  e in use as the 
3d60: 73 61 6d 65 20 74 69 6d 65 20 62 79 20 74 77 6f  same time by two
3d70: 0a 2a 2a 20 6f 72 20 6d 6f 72 65 20 64 61 74 61  .** or more data
3d80: 62 61 73 65 20 63 6f 6e 6e 65 63 74 69 6f 6e 73  base connections
3d90: 2e 20 20 57 68 65 6e 20 74 77 6f 20 6f 72 20 6d  .  When two or m
3da0: 6f 72 65 20 63 6f 6e 6e 65 63 74 69 6f 6e 73 20  ore connections 
3db0: 61 72 65 0a 2a 2a 20 73 68 61 72 69 6e 67 20 74  are.** sharing t
3dc0: 68 65 20 73 61 6d 65 20 64 61 74 61 62 61 73 65  he same database
3dd0: 20 66 69 6c 65 2c 20 65 61 63 68 20 63 6f 6e 6e   file, each conn
3de0: 65 63 74 69 6f 6e 20 68 61 73 20 69 74 20 6f 77  ection has it ow
3df0: 6e 0a 2a 2a 20 70 72 69 76 61 74 65 20 42 74 72  n.** private Btr
3e00: 65 65 20 6f 62 6a 65 63 74 20 66 6f 72 20 74 68  ee object for th
3e10: 65 20 66 69 6c 65 20 61 6e 64 20 65 61 63 68 20  e file and each 
3e20: 6f 66 20 74 68 6f 73 65 20 42 74 72 65 65 73 20  of those Btrees 
3e30: 70 6f 69 6e 74 73 0a 2a 2a 20 74 6f 20 74 68 69  points.** to thi
3e40: 73 20 6f 6e 65 20 42 74 53 68 61 72 65 64 20 6f  s one BtShared o
3e50: 62 6a 65 63 74 2e 20 20 42 74 53 68 61 72 65 64  bject.  BtShared
3e60: 2e 6e 52 65 66 20 69 73 20 74 68 65 20 6e 75 6d  .nRef is the num
3e70: 62 65 72 20 6f 66 0a 2a 2a 20 63 6f 6e 6e 65 63  ber of.** connec
3e80: 74 69 6f 6e 73 20 63 75 72 72 65 6e 74 6c 79 20  tions currently 
3e90: 73 68 61 72 69 6e 67 20 74 68 69 73 20 64 61 74  sharing this dat
3ea0: 61 62 61 73 65 20 66 69 6c 65 2e 0a 2a 2a 0a 2a  abase file..**.*
3eb0: 2a 20 46 69 65 6c 64 73 20 69 6e 20 74 68 69 73  * Fields in this
3ec0: 20 73 74 72 75 63 74 75 72 65 20 61 72 65 20 61   structure are a
3ed0: 63 63 65 73 73 65 64 20 75 6e 64 65 72 20 74 68  ccessed under th
3ee0: 65 20 42 74 53 68 61 72 65 64 2e 6d 75 74 65 78  e BtShared.mutex
3ef0: 0a 2a 2a 20 6d 75 74 65 78 2c 20 65 78 63 65 70  .** mutex, excep
3f00: 74 20 66 6f 72 20 6e 52 65 66 20 61 6e 64 20 70  t for nRef and p
3f10: 4e 65 78 74 20 77 68 69 63 68 20 61 72 65 20 61  Next which are a
3f20: 63 63 65 73 73 65 64 20 75 6e 64 65 72 20 74 68  ccessed under th
3f30: 65 0a 2a 2a 20 67 6c 6f 62 61 6c 20 53 51 4c 49  e.** global SQLI
3f40: 54 45 5f 4d 55 54 45 58 5f 53 54 41 54 49 43 5f  TE_MUTEX_STATIC_
3f50: 4d 41 53 54 45 52 20 6d 75 74 65 78 2e 20 20 54  MASTER mutex.  T
3f60: 68 65 20 70 50 61 67 65 72 20 66 69 65 6c 64 0a  he pPager field.
3f70: 2a 2a 20 6d 61 79 20 6e 6f 74 20 62 65 20 6d 6f  ** may not be mo
3f80: 64 69 66 69 65 64 20 6f 6e 63 65 20 69 74 20 69  dified once it i
3f90: 73 20 69 6e 69 74 69 61 6c 6c 79 20 73 65 74 20  s initially set 
3fa0: 61 73 20 6c 6f 6e 67 20 61 73 20 6e 52 65 66 3e  as long as nRef>
3fb0: 30 2e 0a 2a 2a 20 54 68 65 20 70 53 63 68 65 6d  0..** The pSchem
3fc0: 61 20 66 69 65 6c 64 20 6d 61 79 20 62 65 20 73  a field may be s
3fd0: 65 74 20 6f 6e 63 65 20 75 6e 64 65 72 20 42 74  et once under Bt
3fe0: 53 68 61 72 65 64 2e 6d 75 74 65 78 20 61 6e 64  Shared.mutex and
3ff0: 0a 2a 2a 20 74 68 65 72 65 61 66 74 65 72 20 69  .** thereafter i
4000: 73 20 75 6e 63 68 61 6e 67 65 64 20 61 73 20 6c  s unchanged as l
4010: 6f 6e 67 20 61 73 20 6e 52 65 66 3e 30 2e 0a 2a  ong as nRef>0..*
4020: 2f 0a 73 74 72 75 63 74 20 42 74 53 68 61 72 65  /.struct BtShare
4030: 64 20 7b 0a 20 20 50 61 67 65 72 20 2a 70 50 61  d {.  Pager *pPa
4040: 67 65 72 3b 20 20 20 20 20 20 20 20 2f 2a 20 54  ger;        /* T
4050: 68 65 20 70 61 67 65 20 63 61 63 68 65 20 2a 2f  he page cache */
4060: 0a 20 20 73 71 6c 69 74 65 33 20 2a 64 62 3b 20  .  sqlite3 *db; 
4070: 20 20 20 20 20 20 20 20 20 2f 2a 20 44 61 74 61           /* Data
4080: 62 61 73 65 20 63 6f 6e 6e 65 63 74 69 6f 6e 20  base connection 
4090: 63 75 72 72 65 6e 74 6c 79 20 75 73 69 6e 67 20  currently using 
40a0: 74 68 69 73 20 42 74 72 65 65 20 2a 2f 0a 20 20  this Btree */.  
40b0: 42 74 43 75 72 73 6f 72 20 2a 70 43 75 72 73 6f  BtCursor *pCurso
40c0: 72 3b 20 20 20 20 2f 2a 20 41 20 6c 69 73 74 20  r;    /* A list 
40d0: 6f 66 20 61 6c 6c 20 6f 70 65 6e 20 63 75 72 73  of all open curs
40e0: 6f 72 73 20 2a 2f 0a 20 20 4d 65 6d 50 61 67 65  ors */.  MemPage
40f0: 20 2a 70 50 61 67 65 31 3b 20 20 20 20 20 20 2f   *pPage1;      /
4100: 2a 20 46 69 72 73 74 20 70 61 67 65 20 6f 66 20  * First page of 
4110: 74 68 65 20 64 61 74 61 62 61 73 65 20 2a 2f 0a  the database */.
4120: 20 20 75 38 20 69 6e 53 74 6d 74 3b 20 20 20 20    u8 inStmt;    
4130: 20 20 20 20 20 20 20 20 2f 2a 20 54 72 75 65 20          /* True 
4140: 69 66 20 77 65 20 61 72 65 20 69 6e 20 61 20 73  if we are in a s
4150: 74 61 74 65 6d 65 6e 74 20 73 75 62 74 72 61 6e  tatement subtran
4160: 73 61 63 74 69 6f 6e 20 2a 2f 0a 20 20 75 38 20  saction */.  u8 
4170: 72 65 61 64 4f 6e 6c 79 3b 20 20 20 20 20 20 20  readOnly;       
4180: 20 20 20 2f 2a 20 54 72 75 65 20 69 66 20 74 68     /* True if th
4190: 65 20 75 6e 64 65 72 6c 79 69 6e 67 20 66 69 6c  e underlying fil
41a0: 65 20 69 73 20 72 65 61 64 6f 6e 6c 79 20 2a 2f  e is readonly */
41b0: 0a 20 20 75 38 20 70 61 67 65 53 69 7a 65 46 69  .  u8 pageSizeFi
41c0: 78 65 64 3b 20 20 20 20 20 2f 2a 20 54 72 75 65  xed;     /* True
41d0: 20 69 66 20 74 68 65 20 70 61 67 65 20 73 69 7a   if the page siz
41e0: 65 20 63 61 6e 20 6e 6f 20 6c 6f 6e 67 65 72 20  e can no longer 
41f0: 62 65 20 63 68 61 6e 67 65 64 20 2a 2f 0a 23 69  be changed */.#i
4200: 66 6e 64 65 66 20 53 51 4c 49 54 45 5f 4f 4d 49  fndef SQLITE_OMI
4210: 54 5f 41 55 54 4f 56 41 43 55 55 4d 0a 20 20 75  T_AUTOVACUUM.  u
4220: 38 20 61 75 74 6f 56 61 63 75 75 6d 3b 20 20 20  8 autoVacuum;   
4230: 20 20 20 20 20 2f 2a 20 54 72 75 65 20 69 66 20       /* True if 
4240: 61 75 74 6f 2d 76 61 63 75 75 6d 20 69 73 20 65  auto-vacuum is e
4250: 6e 61 62 6c 65 64 20 2a 2f 0a 20 20 75 38 20 69  nabled */.  u8 i
4260: 6e 63 72 56 61 63 75 75 6d 3b 20 20 20 20 20 20  ncrVacuum;      
4270: 20 20 2f 2a 20 54 72 75 65 20 69 66 20 69 6e 63    /* True if inc
4280: 72 2d 76 61 63 75 75 6d 20 69 73 20 65 6e 61 62  r-vacuum is enab
4290: 6c 65 64 20 2a 2f 0a 20 20 50 67 6e 6f 20 6e 54  led */.  Pgno nT
42a0: 72 75 6e 63 3b 20 20 20 20 20 20 20 20 20 20 2f  runc;          /
42b0: 2a 20 4e 6f 6e 2d 7a 65 72 6f 20 69 66 20 74 68  * Non-zero if th
42c0: 65 20 64 62 20 77 69 6c 6c 20 62 65 20 74 72 75  e db will be tru
42d0: 6e 63 61 74 65 64 20 28 69 6e 63 72 20 76 61 63  ncated (incr vac
42e0: 75 75 6d 29 20 2a 2f 0a 23 65 6e 64 69 66 0a 20  uum) */.#endif. 
42f0: 20 75 31 36 20 70 61 67 65 53 69 7a 65 3b 20 20   u16 pageSize;  
4300: 20 20 20 20 20 20 20 2f 2a 20 54 6f 74 61 6c 20         /* Total 
4310: 6e 75 6d 62 65 72 20 6f 66 20 62 79 74 65 73 20  number of bytes 
4320: 6f 6e 20 61 20 70 61 67 65 20 2a 2f 0a 20 20 75  on a page */.  u
4330: 31 36 20 75 73 61 62 6c 65 53 69 7a 65 3b 20 20  16 usableSize;  
4340: 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f       /* Number o
4350: 66 20 75 73 61 62 6c 65 20 62 79 74 65 73 20 6f  f usable bytes o
4360: 6e 20 65 61 63 68 20 70 61 67 65 20 2a 2f 0a 20  n each page */. 
4370: 20 69 6e 74 20 6d 61 78 4c 6f 63 61 6c 3b 20 20   int maxLocal;  
4380: 20 20 20 20 20 20 20 2f 2a 20 4d 61 78 69 6d 75         /* Maximu
4390: 6d 20 6c 6f 63 61 6c 20 70 61 79 6c 6f 61 64 20  m local payload 
43a0: 69 6e 20 6e 6f 6e 2d 4c 45 41 46 44 41 54 41 20  in non-LEAFDATA 
43b0: 74 61 62 6c 65 73 20 2a 2f 0a 20 20 69 6e 74 20  tables */.  int 
43c0: 6d 69 6e 4c 6f 63 61 6c 3b 20 20 20 20 20 20 20  minLocal;       
43d0: 20 20 2f 2a 20 4d 69 6e 69 6d 75 6d 20 6c 6f 63    /* Minimum loc
43e0: 61 6c 20 70 61 79 6c 6f 61 64 20 69 6e 20 6e 6f  al payload in no
43f0: 6e 2d 4c 45 41 46 44 41 54 41 20 74 61 62 6c 65  n-LEAFDATA table
4400: 73 20 2a 2f 0a 20 20 69 6e 74 20 6d 61 78 4c 65  s */.  int maxLe
4410: 61 66 3b 20 20 20 20 20 20 20 20 20 20 2f 2a 20  af;          /* 
4420: 4d 61 78 69 6d 75 6d 20 6c 6f 63 61 6c 20 70 61  Maximum local pa
4430: 79 6c 6f 61 64 20 69 6e 20 61 20 4c 45 41 46 44  yload in a LEAFD
4440: 41 54 41 20 74 61 62 6c 65 20 2a 2f 0a 20 20 69  ATA table */.  i
4450: 6e 74 20 6d 69 6e 4c 65 61 66 3b 20 20 20 20 20  nt minLeaf;     
4460: 20 20 20 20 20 2f 2a 20 4d 69 6e 69 6d 75 6d 20       /* Minimum 
4470: 6c 6f 63 61 6c 20 70 61 79 6c 6f 61 64 20 69 6e  local payload in
4480: 20 61 20 4c 45 41 46 44 41 54 41 20 74 61 62 6c   a LEAFDATA tabl
4490: 65 20 2a 2f 0a 20 20 75 38 20 69 6e 54 72 61 6e  e */.  u8 inTran
44a0: 73 61 63 74 69 6f 6e 3b 20 20 20 20 20 2f 2a 20  saction;     /* 
44b0: 54 72 61 6e 73 61 63 74 69 6f 6e 20 73 74 61 74  Transaction stat
44c0: 65 20 2a 2f 0a 20 20 69 6e 74 20 6e 54 72 61 6e  e */.  int nTran
44d0: 73 61 63 74 69 6f 6e 3b 20 20 20 20 20 2f 2a 20  saction;     /* 
44e0: 4e 75 6d 62 65 72 20 6f 66 20 6f 70 65 6e 20 74  Number of open t
44f0: 72 61 6e 73 61 63 74 69 6f 6e 73 20 28 72 65 61  ransactions (rea
4500: 64 20 2b 20 77 72 69 74 65 29 20 2a 2f 0a 20 20  d + write) */.  
4510: 76 6f 69 64 20 2a 70 53 63 68 65 6d 61 3b 20 20  void *pSchema;  
4520: 20 20 20 20 20 20 2f 2a 20 50 6f 69 6e 74 65 72        /* Pointer
4530: 20 74 6f 20 73 70 61 63 65 20 61 6c 6c 6f 63 61   to space alloca
4540: 74 65 64 20 62 79 20 73 71 6c 69 74 65 33 42 74  ted by sqlite3Bt
4550: 72 65 65 53 63 68 65 6d 61 28 29 20 2a 2f 0a 20  reeSchema() */. 
4560: 20 76 6f 69 64 20 28 2a 78 46 72 65 65 53 63 68   void (*xFreeSch
4570: 65 6d 61 29 28 76 6f 69 64 2a 29 3b 20 20 2f 2a  ema)(void*);  /*
4580: 20 44 65 73 74 72 75 63 74 6f 72 20 66 6f 72 20   Destructor for 
4590: 42 74 53 68 61 72 65 64 2e 70 53 63 68 65 6d 61  BtShared.pSchema
45a0: 20 2a 2f 0a 20 20 73 71 6c 69 74 65 33 5f 6d 75   */.  sqlite3_mu
45b0: 74 65 78 20 2a 6d 75 74 65 78 3b 20 2f 2a 20 4e  tex *mutex; /* N
45c0: 6f 6e 2d 72 65 63 75 72 73 69 76 65 20 6d 75 74  on-recursive mut
45d0: 65 78 20 72 65 71 75 69 72 65 64 20 74 6f 20 61  ex required to a
45e0: 63 63 65 73 73 20 74 68 69 73 20 73 74 72 75 63  ccess this struc
45f0: 74 20 2a 2f 0a 23 69 66 6e 64 65 66 20 53 51 4c  t */.#ifndef SQL
4600: 49 54 45 5f 4f 4d 49 54 5f 53 48 41 52 45 44 5f  ITE_OMIT_SHARED_
4610: 43 41 43 48 45 0a 20 20 69 6e 74 20 6e 52 65 66  CACHE.  int nRef
4620: 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a  ;             /*
4630: 20 4e 75 6d 62 65 72 20 6f 66 20 72 65 66 65 72   Number of refer
4640: 65 6e 63 65 73 20 74 6f 20 74 68 69 73 20 73 74  ences to this st
4650: 72 75 63 74 75 72 65 20 2a 2f 0a 20 20 42 74 53  ructure */.  BtS
4660: 68 61 72 65 64 20 2a 70 4e 65 78 74 3b 20 20 20  hared *pNext;   
4670: 20 20 20 2f 2a 20 4e 65 78 74 20 6f 6e 20 61 20     /* Next on a 
4680: 6c 69 73 74 20 6f 66 20 73 68 61 72 61 62 6c 65  list of sharable
4690: 20 42 74 53 68 61 72 65 64 20 73 74 72 75 63 74   BtShared struct
46a0: 73 20 2a 2f 0a 20 20 42 74 4c 6f 63 6b 20 2a 70  s */.  BtLock *p
46b0: 4c 6f 63 6b 3b 20 20 20 20 20 20 20 20 2f 2a 20  Lock;        /* 
46c0: 4c 69 73 74 20 6f 66 20 6c 6f 63 6b 73 20 68 65  List of locks he
46d0: 6c 64 20 6f 6e 20 74 68 69 73 20 73 68 61 72 65  ld on this share
46e0: 64 2d 62 74 72 65 65 20 73 74 72 75 63 74 20 2a  d-btree struct *
46f0: 2f 0a 20 20 42 74 72 65 65 20 2a 70 45 78 63 6c  /.  Btree *pExcl
4700: 75 73 69 76 65 3b 20 20 20 20 2f 2a 20 42 74 72  usive;    /* Btr
4710: 65 65 20 77 69 74 68 20 61 6e 20 45 58 43 4c 55  ee with an EXCLU
4720: 53 49 56 45 20 6c 6f 63 6b 20 6f 6e 20 74 68 65  SIVE lock on the
4730: 20 77 68 6f 6c 65 20 64 62 20 2a 2f 0a 23 65 6e   whole db */.#en
4740: 64 69 66 0a 20 20 75 38 20 2a 70 54 6d 70 53 70  dif.  u8 *pTmpSp
4750: 61 63 65 3b 20 20 20 20 20 20 20 20 2f 2a 20 42  ace;        /* B
4760: 74 53 68 61 72 65 64 2e 70 61 67 65 53 69 7a 65  tShared.pageSize
4770: 20 62 79 74 65 73 20 6f 66 20 73 70 61 63 65 20   bytes of space 
4780: 66 6f 72 20 74 6d 70 20 75 73 65 20 2a 2f 0a 7d  for tmp use */.}
4790: 3b 0a 0a 2f 2a 0a 2a 2a 20 41 6e 20 69 6e 73 74  ;../*.** An inst
47a0: 61 6e 63 65 20 6f 66 20 74 68 65 20 66 6f 6c 6c  ance of the foll
47b0: 6f 77 69 6e 67 20 73 74 72 75 63 74 75 72 65 20  owing structure 
47c0: 69 73 20 75 73 65 64 20 74 6f 20 68 6f 6c 64 20  is used to hold 
47d0: 69 6e 66 6f 72 6d 61 74 69 6f 6e 0a 2a 2a 20 61  information.** a
47e0: 62 6f 75 74 20 61 20 63 65 6c 6c 2e 20 20 54 68  bout a cell.  Th
47f0: 65 20 70 61 72 73 65 43 65 6c 6c 50 74 72 28 29  e parseCellPtr()
4800: 20 66 75 6e 63 74 69 6f 6e 20 66 69 6c 6c 73 20   function fills 
4810: 69 6e 20 74 68 69 73 20 73 74 72 75 63 74 75 72  in this structur
4820: 65 0a 2a 2a 20 62 61 73 65 64 20 6f 6e 20 69 6e  e.** based on in
4830: 66 6f 72 6d 61 74 69 6f 6e 20 65 78 74 72 61 63  formation extrac
4840: 74 20 66 72 6f 6d 20 74 68 65 20 72 61 77 20 64  t from the raw d
4850: 69 73 6b 20 70 61 67 65 2e 0a 2a 2f 0a 74 79 70  isk page..*/.typ
4860: 65 64 65 66 20 73 74 72 75 63 74 20 43 65 6c 6c  edef struct Cell
4870: 49 6e 66 6f 20 43 65 6c 6c 49 6e 66 6f 3b 0a 73  Info CellInfo;.s
4880: 74 72 75 63 74 20 43 65 6c 6c 49 6e 66 6f 20 7b  truct CellInfo {
4890: 0a 20 20 75 38 20 2a 70 43 65 6c 6c 3b 20 20 20  .  u8 *pCell;   
48a0: 20 20 2f 2a 20 50 6f 69 6e 74 65 72 20 74 6f 20    /* Pointer to 
48b0: 74 68 65 20 73 74 61 72 74 20 6f 66 20 63 65 6c  the start of cel
48c0: 6c 20 63 6f 6e 74 65 6e 74 20 2a 2f 0a 20 20 69  l content */.  i
48d0: 36 34 20 6e 4b 65 79 3b 20 20 20 20 20 20 2f 2a  64 nKey;      /*
48e0: 20 54 68 65 20 6b 65 79 20 66 6f 72 20 49 4e 54   The key for INT
48f0: 4b 45 59 20 74 61 62 6c 65 73 2c 20 6f 72 20 6e  KEY tables, or n
4900: 75 6d 62 65 72 20 6f 66 20 62 79 74 65 73 20 69  umber of bytes i
4910: 6e 20 6b 65 79 20 2a 2f 0a 20 20 75 33 32 20 6e  n key */.  u32 n
4920: 44 61 74 61 3b 20 20 20 20 20 2f 2a 20 4e 75 6d  Data;     /* Num
4930: 62 65 72 20 6f 66 20 62 79 74 65 73 20 6f 66 20  ber of bytes of 
4940: 64 61 74 61 20 2a 2f 0a 20 20 75 33 32 20 6e 50  data */.  u32 nP
4950: 61 79 6c 6f 61 64 3b 20 20 2f 2a 20 54 6f 74 61  ayload;  /* Tota
4960: 6c 20 61 6d 6f 75 6e 74 20 6f 66 20 70 61 79 6c  l amount of payl
4970: 6f 61 64 20 2a 2f 0a 20 20 75 31 36 20 6e 48 65  oad */.  u16 nHe
4980: 61 64 65 72 3b 20 20 20 2f 2a 20 53 69 7a 65 20  ader;   /* Size 
4990: 6f 66 20 74 68 65 20 63 65 6c 6c 20 63 6f 6e 74  of the cell cont
49a0: 65 6e 74 20 68 65 61 64 65 72 20 69 6e 20 62 79  ent header in by
49b0: 74 65 73 20 2a 2f 0a 20 20 75 31 36 20 6e 4c 6f  tes */.  u16 nLo
49c0: 63 61 6c 3b 20 20 20 20 2f 2a 20 41 6d 6f 75 6e  cal;    /* Amoun
49d0: 74 20 6f 66 20 70 61 79 6c 6f 61 64 20 68 65 6c  t of payload hel
49e0: 64 20 6c 6f 63 61 6c 6c 79 20 2a 2f 0a 20 20 75  d locally */.  u
49f0: 31 36 20 69 4f 76 65 72 66 6c 6f 77 3b 20 2f 2a  16 iOverflow; /*
4a00: 20 4f 66 66 73 65 74 20 74 6f 20 6f 76 65 72 66   Offset to overf
4a10: 6c 6f 77 20 70 61 67 65 20 6e 75 6d 62 65 72 2e  low page number.
4a20: 20 20 5a 65 72 6f 20 69 66 20 6e 6f 20 6f 76 65    Zero if no ove
4a30: 72 66 6c 6f 77 20 2a 2f 0a 20 20 75 31 36 20 6e  rflow */.  u16 n
4a40: 53 69 7a 65 3b 20 20 20 20 20 2f 2a 20 53 69 7a  Size;     /* Siz
4a50: 65 20 6f 66 20 74 68 65 20 63 65 6c 6c 20 63 6f  e of the cell co
4a60: 6e 74 65 6e 74 20 6f 6e 20 74 68 65 20 6d 61 69  ntent on the mai
4a70: 6e 20 62 2d 74 72 65 65 20 70 61 67 65 20 2a 2f  n b-tree page */
4a80: 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 4d 61 78 69 6d  .};../*.** Maxim
4a90: 75 6d 20 64 65 70 74 68 20 6f 66 20 61 6e 20 53  um depth of an S
4aa0: 51 4c 69 74 65 20 42 2d 54 72 65 65 20 73 74 72  QLite B-Tree str
4ab0: 75 63 74 75 72 65 2e 20 41 6e 79 20 42 2d 54 72  ucture. Any B-Tr
4ac0: 65 65 20 64 65 65 70 65 72 20 74 68 61 6e 0a 2a  ee deeper than.*
4ad0: 2a 20 74 68 69 73 20 77 69 6c 6c 20 62 65 20 64  * this will be d
4ae0: 65 63 6c 61 72 65 64 20 63 6f 72 72 75 70 74 2e  eclared corrupt.
4af0: 20 54 68 69 73 20 76 61 6c 75 65 20 69 73 20 63   This value is c
4b00: 61 6c 63 75 6c 61 74 65 64 20 62 61 73 65 64 20  alculated based 
4b10: 6f 6e 20 61 0a 2a 2a 20 6d 61 78 69 6d 75 6d 20  on a.** maximum 
4b20: 64 61 74 61 62 61 73 65 20 73 69 7a 65 20 6f 66  database size of
4b30: 20 32 5e 33 31 20 70 61 67 65 73 20 61 20 6d 69   2^31 pages a mi
4b40: 6e 69 6d 75 6d 20 66 61 6e 6f 75 74 20 6f 66 20  nimum fanout of 
4b50: 32 20 66 6f 72 20 61 0a 2a 2a 20 72 6f 6f 74 2d  2 for a.** root-
4b60: 6e 6f 64 65 20 61 6e 64 20 33 20 66 6f 72 20 61  node and 3 for a
4b70: 6c 6c 20 6f 74 68 65 72 20 69 6e 74 65 72 6e 61  ll other interna
4b80: 6c 20 6e 6f 64 65 73 2e 0a 2a 2a 0a 2a 2a 20 49  l nodes..**.** I
4b90: 66 20 61 20 74 72 65 65 20 74 68 61 74 20 61 70  f a tree that ap
4ba0: 70 65 61 72 73 20 74 6f 20 62 65 20 74 61 6c 6c  pears to be tall
4bb0: 65 72 20 74 68 61 6e 20 74 68 69 73 20 69 73 20  er than this is 
4bc0: 65 6e 63 6f 75 6e 74 65 72 65 64 2c 20 69 74 20  encountered, it 
4bd0: 69 73 0a 2a 2a 20 61 73 73 75 6d 65 64 20 74 68  is.** assumed th
4be0: 61 74 20 74 68 65 20 64 61 74 61 62 61 73 65 20  at the database 
4bf0: 69 73 20 63 6f 72 72 75 70 74 2e 0a 2a 2f 0a 23  is corrupt..*/.#
4c00: 64 65 66 69 6e 65 20 42 54 43 55 52 53 4f 52 5f  define BTCURSOR_
4c10: 4d 41 58 5f 44 45 50 54 48 20 32 30 0a 0a 2f 2a  MAX_DEPTH 20../*
4c20: 0a 2a 2a 20 41 20 63 75 72 73 6f 72 20 69 73 20  .** A cursor is 
4c30: 61 20 70 6f 69 6e 74 65 72 20 74 6f 20 61 20 70  a pointer to a p
4c40: 61 72 74 69 63 75 6c 61 72 20 65 6e 74 72 79 20  articular entry 
4c50: 77 69 74 68 69 6e 20 61 20 70 61 72 74 69 63 75  within a particu
4c60: 6c 61 72 0a 2a 2a 20 62 2d 74 72 65 65 20 77 69  lar.** b-tree wi
4c70: 74 68 69 6e 20 61 20 64 61 74 61 62 61 73 65 20  thin a database 
4c80: 66 69 6c 65 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20  file..**.** The 
4c90: 65 6e 74 72 79 20 69 73 20 69 64 65 6e 74 69 66  entry is identif
4ca0: 69 65 64 20 62 79 20 69 74 73 20 4d 65 6d 50 61  ied by its MemPa
4cb0: 67 65 20 61 6e 64 20 74 68 65 20 69 6e 64 65 78  ge and the index
4cc0: 20 69 6e 0a 2a 2a 20 4d 65 6d 50 61 67 65 2e 61   in.** MemPage.a
4cd0: 43 65 6c 6c 5b 5d 20 6f 66 20 74 68 65 20 65 6e  Cell[] of the en
4ce0: 74 72 79 2e 0a 2a 2a 0a 2a 2a 20 57 68 65 6e 20  try..**.** When 
4cf0: 61 20 73 69 6e 67 6c 65 20 64 61 74 61 62 61 73  a single databas
4d00: 65 20 66 69 6c 65 20 63 61 6e 20 73 68 61 72 65  e file can share
4d10: 64 20 62 79 20 74 77 6f 20 6d 6f 72 65 20 64 61  d by two more da
4d20: 74 61 62 61 73 65 20 63 6f 6e 6e 65 63 74 69 6f  tabase connectio
4d30: 6e 73 2c 0a 2a 2a 20 62 75 74 20 63 75 72 73 6f  ns,.** but curso
4d40: 72 73 20 63 61 6e 6e 6f 74 20 62 65 20 73 68 61  rs cannot be sha
4d50: 72 65 64 2e 20 20 45 61 63 68 20 63 75 72 73 6f  red.  Each curso
4d60: 72 20 69 73 20 61 73 73 6f 63 69 61 74 65 64 20  r is associated 
4d70: 77 69 74 68 20 61 0a 2a 2a 20 70 61 72 74 69 63  with a.** partic
4d80: 75 6c 61 72 20 64 61 74 61 62 61 73 65 20 63 6f  ular database co
4d90: 6e 6e 65 63 74 69 6f 6e 20 69 64 65 6e 74 69 66  nnection identif
4da0: 69 65 64 20 42 74 43 75 72 73 6f 72 2e 70 42 74  ied BtCursor.pBt
4db0: 72 65 65 2e 64 62 2e 0a 2a 2a 0a 2a 2a 20 46 69  ree.db..**.** Fi
4dc0: 65 6c 64 73 20 69 6e 20 74 68 69 73 20 73 74 72  elds in this str
4dd0: 75 63 74 75 72 65 20 61 72 65 20 61 63 63 65 73  ucture are acces
4de0: 73 65 64 20 75 6e 64 65 72 20 74 68 65 20 42 74  sed under the Bt
4df0: 53 68 61 72 65 64 2e 6d 75 74 65 78 0a 2a 2a 20  Shared.mutex.** 
4e00: 66 6f 75 6e 64 20 61 74 20 73 65 6c 66 2d 3e 70  found at self->p
4e10: 42 74 2d 3e 6d 75 74 65 78 2e 20 0a 2a 2f 0a 73  Bt->mutex. .*/.s
4e20: 74 72 75 63 74 20 42 74 43 75 72 73 6f 72 20 7b  truct BtCursor {
4e30: 0a 20 20 42 74 72 65 65 20 2a 70 42 74 72 65 65  .  Btree *pBtree
4e40: 3b 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20  ;            /* 
4e50: 54 68 65 20 42 74 72 65 65 20 74 6f 20 77 68 69  The Btree to whi
4e60: 63 68 20 74 68 69 73 20 63 75 72 73 6f 72 20 62  ch this cursor b
4e70: 65 6c 6f 6e 67 73 20 2a 2f 0a 20 20 42 74 53 68  elongs */.  BtSh
4e80: 61 72 65 64 20 2a 70 42 74 3b 20 20 20 20 20 20  ared *pBt;      
4e90: 20 20 20 20 20 20 2f 2a 20 54 68 65 20 42 74 53        /* The BtS
4ea0: 68 61 72 65 64 20 74 68 69 73 20 63 75 72 73 6f  hared this curso
4eb0: 72 20 70 6f 69 6e 74 73 20 74 6f 20 2a 2f 0a 20  r points to */. 
4ec0: 20 42 74 43 75 72 73 6f 72 20 2a 70 4e 65 78 74   BtCursor *pNext
4ed0: 2c 20 2a 70 50 72 65 76 3b 20 20 2f 2a 20 46 6f  , *pPrev;  /* Fo
4ee0: 72 6d 73 20 61 20 6c 69 6e 6b 65 64 20 6c 69 73  rms a linked lis
4ef0: 74 20 6f 66 20 61 6c 6c 20 63 75 72 73 6f 72 73  t of all cursors
4f00: 20 2a 2f 0a 20 20 73 74 72 75 63 74 20 4b 65 79   */.  struct Key
4f10: 49 6e 66 6f 20 2a 70 4b 65 79 49 6e 66 6f 3b 20  Info *pKeyInfo; 
4f20: 2f 2a 20 41 72 67 75 6d 65 6e 74 20 70 61 73 73  /* Argument pass
4f30: 65 64 20 74 6f 20 63 6f 6d 70 61 72 69 73 6f 6e  ed to comparison
4f40: 20 66 75 6e 63 74 69 6f 6e 20 2a 2f 0a 20 20 50   function */.  P
4f50: 67 6e 6f 20 70 67 6e 6f 52 6f 6f 74 3b 20 20 20  gno pgnoRoot;   
4f60: 20 20 20 20 20 20 20 20 20 2f 2a 20 54 68 65 20           /* The 
4f70: 72 6f 6f 74 20 70 61 67 65 20 6f 66 20 74 68 69  root page of thi
4f80: 73 20 74 72 65 65 20 2a 2f 0a 20 20 43 65 6c 6c  s tree */.  Cell
4f90: 49 6e 66 6f 20 69 6e 66 6f 3b 20 20 20 20 20 20  Info info;      
4fa0: 20 20 20 20 20 20 2f 2a 20 41 20 70 61 72 73 65        /* A parse
4fb0: 20 6f 66 20 74 68 65 20 63 65 6c 6c 20 77 65 20   of the cell we 
4fc0: 61 72 65 20 70 6f 69 6e 74 69 6e 67 20 61 74 20  are pointing at 
4fd0: 2a 2f 0a 20 20 75 38 20 77 72 46 6c 61 67 3b 20  */.  u8 wrFlag; 
4fe0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f                 /
4ff0: 2a 20 54 72 75 65 20 69 66 20 77 72 69 74 61 62  * True if writab
5000: 6c 65 20 2a 2f 0a 20 20 75 38 20 61 74 4c 61 73  le */.  u8 atLas
5010: 74 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20  t;              
5020: 20 20 2f 2a 20 43 75 72 73 6f 72 20 70 6f 69 6e    /* Cursor poin
5030: 74 69 6e 67 20 74 6f 20 74 68 65 20 6c 61 73 74  ting to the last
5040: 20 65 6e 74 72 79 20 2a 2f 0a 20 20 75 38 20 76   entry */.  u8 v
5050: 61 6c 69 64 4e 4b 65 79 3b 20 20 20 20 20 20 20  alidNKey;       
5060: 20 20 20 20 20 20 2f 2a 20 54 72 75 65 20 69 66        /* True if
5070: 20 69 6e 66 6f 2e 6e 4b 65 79 20 69 73 20 76 61   info.nKey is va
5080: 6c 69 64 20 2a 2f 0a 20 20 75 38 20 65 53 74 61  lid */.  u8 eSta
5090: 74 65 3b 20 20 20 20 20 20 20 20 20 20 20 20 20  te;             
50a0: 20 20 20 2f 2a 20 4f 6e 65 20 6f 66 20 74 68 65     /* One of the
50b0: 20 43 55 52 53 4f 52 5f 58 58 58 20 63 6f 6e 73   CURSOR_XXX cons
50c0: 74 61 6e 74 73 20 28 73 65 65 20 62 65 6c 6f 77  tants (see below
50d0: 29 20 2a 2f 0a 20 20 76 6f 69 64 20 2a 70 4b 65  ) */.  void *pKe
50e0: 79 3b 20 20 20 20 20 20 2f 2a 20 53 61 76 65 64  y;      /* Saved
50f0: 20 6b 65 79 20 74 68 61 74 20 77 61 73 20 63 75   key that was cu
5100: 72 73 6f 72 27 73 20 6c 61 73 74 20 6b 6e 6f 77  rsor's last know
5110: 6e 20 70 6f 73 69 74 69 6f 6e 20 2a 2f 0a 20 20  n position */.  
5120: 69 36 34 20 6e 4b 65 79 3b 20 20 20 20 20 20 20  i64 nKey;       
5130: 20 2f 2a 20 53 69 7a 65 20 6f 66 20 70 4b 65 79   /* Size of pKey
5140: 2c 20 6f 72 20 6c 61 73 74 20 69 6e 74 65 67 65  , or last intege
5150: 72 20 6b 65 79 20 2a 2f 0a 20 20 69 6e 74 20 73  r key */.  int s
5160: 6b 69 70 3b 20 20 20 20 20 20 20 20 2f 2a 20 28  kip;        /* (
5170: 73 6b 69 70 3c 30 29 20 2d 3e 20 50 72 65 76 28  skip<0) -> Prev(
5180: 29 20 69 73 20 61 20 6e 6f 2d 6f 70 2e 20 28 73  ) is a no-op. (s
5190: 6b 69 70 3e 30 29 20 2d 3e 20 4e 65 78 74 28 29  kip>0) -> Next()
51a0: 20 69 73 20 2a 2f 0a 23 69 66 6e 64 65 66 20 53   is */.#ifndef S
51b0: 51 4c 49 54 45 5f 4f 4d 49 54 5f 49 4e 43 52 42  QLITE_OMIT_INCRB
51c0: 4c 4f 42 0a 20 20 75 38 20 69 73 49 6e 63 72 62  LOB.  u8 isIncrb
51d0: 6c 6f 62 48 61 6e 64 6c 65 3b 20 20 20 20 20 20  lobHandle;      
51e0: 2f 2a 20 54 72 75 65 20 69 66 20 74 68 69 73 20  /* True if this 
51f0: 63 75 72 73 6f 72 20 69 73 20 61 6e 20 69 6e 63  cursor is an inc
5200: 72 2e 20 69 6f 20 68 61 6e 64 6c 65 20 2a 2f 0a  r. io handle */.
5210: 20 20 50 67 6e 6f 20 2a 61 4f 76 65 72 66 6c 6f    Pgno *aOverflo
5220: 77 3b 20 20 20 20 20 20 20 20 20 20 2f 2a 20 43  w;          /* C
5230: 61 63 68 65 20 6f 66 20 6f 76 65 72 66 6c 6f 77  ache of overflow
5240: 20 70 61 67 65 20 6c 6f 63 61 74 69 6f 6e 73 20   page locations 
5250: 2a 2f 0a 23 65 6e 64 69 66 0a 23 69 66 6e 64 65  */.#endif.#ifnde
5260: 66 20 4e 44 45 42 55 47 0a 20 20 75 38 20 70 61  f NDEBUG.  u8 pa
5270: 67 65 73 53 68 75 66 66 6c 65 64 3b 20 20 20 20  gesShuffled;    
5280: 20 20 20 20 20 2f 2a 20 54 72 75 65 20 69 66 20       /* True if 
5290: 42 74 72 65 65 20 70 61 67 65 73 20 61 72 65 20  Btree pages are 
52a0: 72 65 61 72 72 61 6e 67 65 64 20 62 79 20 62 61  rearranged by ba
52b0: 6c 61 6e 63 65 28 29 2a 2f 0a 23 65 6e 64 69 66  lance()*/.#endif
52c0: 0a 20 20 69 31 36 20 69 50 61 67 65 3b 20 20 20  .  i16 iPage;   
52d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
52e0: 20 20 20 20 20 20 20 20 20 2f 2a 20 49 6e 64 65           /* Inde
52f0: 78 20 6f 66 20 63 75 72 72 65 6e 74 20 70 61 67  x of current pag
5300: 65 20 69 6e 20 61 70 50 61 67 65 20 2a 2f 0a 20  e in apPage */. 
5310: 20 4d 65 6d 50 61 67 65 20 2a 61 70 50 61 67 65   MemPage *apPage
5320: 5b 42 54 43 55 52 53 4f 52 5f 4d 41 58 5f 44 45  [BTCURSOR_MAX_DE
5330: 50 54 48 5d 3b 20 20 2f 2a 20 50 61 67 65 73 20  PTH];  /* Pages 
5340: 66 72 6f 6d 20 72 6f 6f 74 20 74 6f 20 63 75 72  from root to cur
5350: 72 65 6e 74 20 70 61 67 65 20 2a 2f 0a 20 20 75  rent page */.  u
5360: 31 36 20 61 69 49 64 78 5b 42 54 43 55 52 53 4f  16 aiIdx[BTCURSO
5370: 52 5f 4d 41 58 5f 44 45 50 54 48 5d 3b 20 20 20  R_MAX_DEPTH];   
5380: 20 20 20 20 20 2f 2a 20 43 75 72 72 65 6e 74 20       /* Current 
5390: 69 6e 64 65 78 20 69 6e 20 61 70 50 61 67 65 5b  index in apPage[
53a0: 69 5d 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20  i] */.};../*.** 
53b0: 50 6f 74 65 6e 74 69 61 6c 20 76 61 6c 75 65 73  Potential values
53c0: 20 66 6f 72 20 42 74 43 75 72 73 6f 72 2e 65 53   for BtCursor.eS
53d0: 74 61 74 65 2e 0a 2a 2a 0a 2a 2a 20 43 55 52 53  tate..**.** CURS
53e0: 4f 52 5f 56 41 4c 49 44 3a 0a 2a 2a 20 20 20 43  OR_VALID:.**   C
53f0: 75 72 73 6f 72 20 70 6f 69 6e 74 73 20 74 6f 20  ursor points to 
5400: 61 20 76 61 6c 69 64 20 65 6e 74 72 79 2e 20 67  a valid entry. g
5410: 65 74 50 61 79 6c 6f 61 64 28 29 20 65 74 63 2e  etPayload() etc.
5420: 20 6d 61 79 20 62 65 20 63 61 6c 6c 65 64 2e 0a   may be called..
5430: 2a 2a 0a 2a 2a 20 43 55 52 53 4f 52 5f 49 4e 56  **.** CURSOR_INV
5440: 41 4c 49 44 3a 0a 2a 2a 20 20 20 43 75 72 73 6f  ALID:.**   Curso
5450: 72 20 64 6f 65 73 20 6e 6f 74 20 70 6f 69 6e 74  r does not point
5460: 20 74 6f 20 61 20 76 61 6c 69 64 20 65 6e 74 72   to a valid entr
5470: 79 2e 20 54 68 69 73 20 63 61 6e 20 68 61 70 70  y. This can happ
5480: 65 6e 20 28 66 6f 72 20 65 78 61 6d 70 6c 65 29  en (for example)
5490: 20 0a 2a 2a 20 20 20 62 65 63 61 75 73 65 20 74   .**   because t
54a0: 68 65 20 74 61 62 6c 65 20 69 73 20 65 6d 70 74  he table is empt
54b0: 79 20 6f 72 20 62 65 63 61 75 73 65 20 42 74 72  y or because Btr
54c0: 65 65 43 75 72 73 6f 72 46 69 72 73 74 28 29 20  eeCursorFirst() 
54d0: 68 61 73 20 6e 6f 74 20 62 65 65 6e 0a 2a 2a 20  has not been.** 
54e0: 20 20 63 61 6c 6c 65 64 2e 0a 2a 2a 0a 2a 2a 20    called..**.** 
54f0: 43 55 52 53 4f 52 5f 52 45 51 55 49 52 45 53 45  CURSOR_REQUIRESE
5500: 45 4b 3a 0a 2a 2a 20 20 20 54 68 65 20 74 61 62  EK:.**   The tab
5510: 6c 65 20 74 68 61 74 20 74 68 69 73 20 63 75 72  le that this cur
5520: 73 6f 72 20 77 61 73 20 6f 70 65 6e 65 64 20 6f  sor was opened o
5530: 6e 20 73 74 69 6c 6c 20 65 78 69 73 74 73 2c 20  n still exists, 
5540: 62 75 74 20 68 61 73 20 62 65 65 6e 20 0a 2a 2a  but has been .**
5550: 20 20 20 6d 6f 64 69 66 69 65 64 20 73 69 6e 63     modified sinc
5560: 65 20 74 68 65 20 63 75 72 73 6f 72 20 77 61 73  e the cursor was
5570: 20 6c 61 73 74 20 75 73 65 64 2e 20 54 68 65 20   last used. The 
5580: 63 75 72 73 6f 72 20 70 6f 73 69 74 69 6f 6e 20  cursor position 
5590: 69 73 20 73 61 76 65 64 0a 2a 2a 20 20 20 69 6e  is saved.**   in
55a0: 20 76 61 72 69 61 62 6c 65 73 20 42 74 43 75 72   variables BtCur
55b0: 73 6f 72 2e 70 4b 65 79 20 61 6e 64 20 42 74 43  sor.pKey and BtC
55c0: 75 72 73 6f 72 2e 6e 4b 65 79 2e 20 57 68 65 6e  ursor.nKey. When
55d0: 20 61 20 63 75 72 73 6f 72 20 69 73 20 69 6e 20   a cursor is in 
55e0: 0a 2a 2a 20 20 20 74 68 69 73 20 73 74 61 74 65  .**   this state
55f0: 2c 20 72 65 73 74 6f 72 65 43 75 72 73 6f 72 50  , restoreCursorP
5600: 6f 73 69 74 69 6f 6e 28 29 20 63 61 6e 20 62 65  osition() can be
5610: 20 63 61 6c 6c 65 64 20 74 6f 20 61 74 74 65 6d   called to attem
5620: 70 74 20 74 6f 0a 2a 2a 20 20 20 73 65 65 6b 20  pt to.**   seek 
5630: 74 68 65 20 63 75 72 73 6f 72 20 74 6f 20 74 68  the cursor to th
5640: 65 20 73 61 76 65 64 20 70 6f 73 69 74 69 6f 6e  e saved position
5650: 2e 0a 2a 2a 0a 2a 2a 20 43 55 52 53 4f 52 5f 46  ..**.** CURSOR_F
5660: 41 55 4c 54 3a 0a 2a 2a 20 20 20 41 20 75 6e 72  AULT:.**   A unr
5670: 65 63 6f 76 65 72 61 62 6c 65 20 65 72 72 6f 72  ecoverable error
5680: 20 28 61 6e 20 49 2f 4f 20 65 72 72 6f 72 20 6f   (an I/O error o
5690: 72 20 61 20 6d 61 6c 6c 6f 63 20 66 61 69 6c 75  r a malloc failu
56a0: 72 65 29 20 68 61 73 20 6f 63 63 75 72 72 65 64  re) has occurred
56b0: 0a 2a 2a 20 20 20 6f 6e 20 61 20 64 69 66 66 65  .**   on a diffe
56c0: 72 65 6e 74 20 63 6f 6e 6e 65 63 74 69 6f 6e 20  rent connection 
56d0: 74 68 61 74 20 73 68 61 72 65 73 20 74 68 65 20  that shares the 
56e0: 42 74 53 68 61 72 65 64 20 63 61 63 68 65 20 77  BtShared cache w
56f0: 69 74 68 20 74 68 69 73 0a 2a 2a 20 20 20 63 75  ith this.**   cu
5700: 72 73 6f 72 2e 20 20 54 68 65 20 65 72 72 6f 72  rsor.  The error
5710: 20 68 61 73 20 6c 65 66 74 20 74 68 65 20 63 61   has left the ca
5720: 63 68 65 20 69 6e 20 61 6e 20 69 6e 63 6f 6e 73  che in an incons
5730: 69 73 74 65 6e 74 20 73 74 61 74 65 2e 0a 2a 2a  istent state..**
5740: 20 20 20 44 6f 20 6e 6f 74 68 69 6e 67 20 65 6c     Do nothing el
5750: 73 65 20 77 69 74 68 20 74 68 69 73 20 63 75 72  se with this cur
5760: 73 6f 72 2e 20 20 41 6e 79 20 61 74 74 65 6d 70  sor.  Any attemp
5770: 74 20 74 6f 20 75 73 65 20 74 68 65 20 63 75 72  t to use the cur
5780: 73 6f 72 0a 2a 2a 20 20 20 73 68 6f 75 6c 64 20  sor.**   should 
5790: 72 65 74 75 72 6e 20 74 68 65 20 65 72 72 6f 72  return the error
57a0: 20 63 6f 64 65 20 73 74 6f 72 65 64 20 69 6e 20   code stored in 
57b0: 42 74 43 75 72 73 6f 72 2e 73 6b 69 70 0a 2a 2f  BtCursor.skip.*/
57c0: 0a 23 64 65 66 69 6e 65 20 43 55 52 53 4f 52 5f  .#define CURSOR_
57d0: 49 4e 56 41 4c 49 44 20 20 20 20 20 20 20 20 20  INVALID         
57e0: 20 20 30 0a 23 64 65 66 69 6e 65 20 43 55 52 53    0.#define CURS
57f0: 4f 52 5f 56 41 4c 49 44 20 20 20 20 20 20 20 20  OR_VALID        
5800: 20 20 20 20 20 31 0a 23 64 65 66 69 6e 65 20 43       1.#define C
5810: 55 52 53 4f 52 5f 52 45 51 55 49 52 45 53 45 45  URSOR_REQUIRESEE
5820: 4b 20 20 20 20 20 20 20 32 0a 23 64 65 66 69 6e  K       2.#defin
5830: 65 20 43 55 52 53 4f 52 5f 46 41 55 4c 54 20 20  e CURSOR_FAULT  
5840: 20 20 20 20 20 20 20 20 20 20 20 33 0a 0a 2f 2a             3../*
5850: 20 54 68 65 20 64 61 74 61 62 61 73 65 20 70 61   The database pa
5860: 67 65 20 74 68 65 20 50 45 4e 44 49 4e 47 5f 42  ge the PENDING_B
5870: 59 54 45 20 6f 63 63 75 70 69 65 73 2e 20 54 68  YTE occupies. Th
5880: 69 73 20 70 61 67 65 20 69 73 20 6e 65 76 65 72  is page is never
5890: 20 75 73 65 64 2e 0a 2a 2a 20 54 4f 44 4f 3a 20   used..** TODO: 
58a0: 54 68 69 73 20 6d 61 63 72 6f 20 69 73 20 76 65  This macro is ve
58b0: 72 79 20 73 69 6d 69 6c 61 72 79 20 74 6f 20 50  ry similary to P
58c0: 41 47 45 52 5f 4d 4a 5f 50 47 4e 4f 28 29 20 69  AGER_MJ_PGNO() i
58d0: 6e 20 70 61 67 65 72 2e 63 2e 20 54 68 65 79 0a  n pager.c. They.
58e0: 2a 2a 20 73 68 6f 75 6c 64 20 70 6f 73 73 69 62  ** should possib
58f0: 6c 79 20 62 65 20 63 6f 6e 73 6f 6c 69 64 61 74  ly be consolidat
5900: 65 64 20 28 70 72 65 73 75 6d 61 62 6c 79 20 69  ed (presumably i
5910: 6e 20 70 61 67 65 72 2e 68 29 2e 0a 2a 2a 0a 2a  n pager.h)..**.*
5920: 2a 20 49 66 20 64 69 73 6b 20 49 2f 4f 20 69 73  * If disk I/O is
5930: 20 6f 6d 69 74 74 65 64 20 28 6d 65 61 6e 69 6e   omitted (meanin
5940: 67 20 74 68 61 74 20 74 68 65 20 64 61 74 61 62  g that the datab
5950: 61 73 65 20 69 73 20 73 74 6f 72 65 64 20 70 75  ase is stored pu
5960: 72 65 6c 79 0a 2a 2a 20 69 6e 20 6d 65 6d 6f 72  rely.** in memor
5970: 79 29 20 74 68 65 6e 20 74 68 65 72 65 20 69 73  y) then there is
5980: 20 6e 6f 20 70 65 6e 64 69 6e 67 20 62 79 74 65   no pending byte
5990: 2e 0a 2a 2f 0a 23 69 66 64 65 66 20 53 51 4c 49  ..*/.#ifdef SQLI
59a0: 54 45 5f 4f 4d 49 54 5f 44 49 53 4b 49 4f 0a 23  TE_OMIT_DISKIO.#
59b0: 20 64 65 66 69 6e 65 20 50 45 4e 44 49 4e 47 5f   define PENDING_
59c0: 42 59 54 45 5f 50 41 47 45 28 70 42 74 29 20 20  BYTE_PAGE(pBt)  
59d0: 30 78 37 66 66 66 66 66 66 66 0a 23 65 6c 73 65  0x7fffffff.#else
59e0: 0a 23 20 64 65 66 69 6e 65 20 50 45 4e 44 49 4e  .# define PENDIN
59f0: 47 5f 42 59 54 45 5f 50 41 47 45 28 70 42 74 29  G_BYTE_PAGE(pBt)
5a00: 20 28 28 50 67 6e 6f 29 28 28 50 45 4e 44 49 4e   ((Pgno)((PENDIN
5a10: 47 5f 42 59 54 45 2f 28 70 42 74 29 2d 3e 70 61  G_BYTE/(pBt)->pa
5a20: 67 65 53 69 7a 65 29 2b 31 29 29 0a 23 65 6e 64  geSize)+1)).#end
5a30: 69 66 0a 0a 2f 2a 0a 2a 2a 20 41 20 6c 69 6e 6b  if../*.** A link
5a40: 65 64 20 6c 69 73 74 20 6f 66 20 74 68 65 20 66  ed list of the f
5a50: 6f 6c 6c 6f 77 69 6e 67 20 73 74 72 75 63 74 75  ollowing structu
5a60: 72 65 73 20 69 73 20 73 74 6f 72 65 64 20 61 74  res is stored at
5a70: 20 42 74 53 68 61 72 65 64 2e 70 4c 6f 63 6b 2e   BtShared.pLock.
5a80: 0a 2a 2a 20 4c 6f 63 6b 73 20 61 72 65 20 61 64  .** Locks are ad
5a90: 64 65 64 20 28 6f 72 20 75 70 67 72 61 64 65 64  ded (or upgraded
5aa0: 20 66 72 6f 6d 20 52 45 41 44 5f 4c 4f 43 4b 20   from READ_LOCK 
5ab0: 74 6f 20 57 52 49 54 45 5f 4c 4f 43 4b 29 20 77  to WRITE_LOCK) w
5ac0: 68 65 6e 20 61 20 63 75 72 73 6f 72 20 0a 2a 2a  hen a cursor .**
5ad0: 20 69 73 20 6f 70 65 6e 65 64 20 6f 6e 20 74 68   is opened on th
5ae0: 65 20 74 61 62 6c 65 20 77 69 74 68 20 72 6f 6f  e table with roo
5af0: 74 20 70 61 67 65 20 42 74 53 68 61 72 65 64 2e  t page BtShared.
5b00: 69 54 61 62 6c 65 2e 20 4c 6f 63 6b 73 20 61 72  iTable. Locks ar
5b10: 65 20 72 65 6d 6f 76 65 64 0a 2a 2a 20 66 72 6f  e removed.** fro
5b20: 6d 20 74 68 69 73 20 6c 69 73 74 20 77 68 65 6e  m this list when
5b30: 20 61 20 74 72 61 6e 73 61 63 74 69 6f 6e 20 69   a transaction i
5b40: 73 20 63 6f 6d 6d 69 74 74 65 64 20 6f 72 20 72  s committed or r
5b50: 6f 6c 6c 65 64 20 62 61 63 6b 2c 20 6f 72 20 77  olled back, or w
5b60: 68 65 6e 0a 2a 2a 20 61 20 62 74 72 65 65 20 68  hen.** a btree h
5b70: 61 6e 64 6c 65 20 69 73 20 63 6c 6f 73 65 64 2e  andle is closed.
5b80: 0a 2a 2f 0a 73 74 72 75 63 74 20 42 74 4c 6f 63  .*/.struct BtLoc
5b90: 6b 20 7b 0a 20 20 42 74 72 65 65 20 2a 70 42 74  k {.  Btree *pBt
5ba0: 72 65 65 3b 20 20 20 20 20 20 20 20 2f 2a 20 42  ree;        /* B
5bb0: 74 72 65 65 20 68 61 6e 64 6c 65 20 68 6f 6c 64  tree handle hold
5bc0: 69 6e 67 20 74 68 69 73 20 6c 6f 63 6b 20 2a 2f  ing this lock */
5bd0: 0a 20 20 50 67 6e 6f 20 69 54 61 62 6c 65 3b 20  .  Pgno iTable; 
5be0: 20 20 20 20 20 20 20 20 20 2f 2a 20 52 6f 6f 74           /* Root
5bf0: 20 70 61 67 65 20 6f 66 20 74 61 62 6c 65 20 2a   page of table *
5c00: 2f 0a 20 20 75 38 20 65 4c 6f 63 6b 3b 20 20 20  /.  u8 eLock;   
5c10: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 52 45 41            /* REA
5c20: 44 5f 4c 4f 43 4b 20 6f 72 20 57 52 49 54 45 5f  D_LOCK or WRITE_
5c30: 4c 4f 43 4b 20 2a 2f 0a 20 20 42 74 4c 6f 63 6b  LOCK */.  BtLock
5c40: 20 2a 70 4e 65 78 74 3b 20 20 20 20 20 20 20 20   *pNext;        
5c50: 2f 2a 20 4e 65 78 74 20 69 6e 20 42 74 53 68 61  /* Next in BtSha
5c60: 72 65 64 2e 70 4c 6f 63 6b 20 6c 69 73 74 20 2a  red.pLock list *
5c70: 2f 0a 7d 3b 0a 0a 2f 2a 20 43 61 6e 64 69 64 61  /.};../* Candida
5c80: 74 65 20 76 61 6c 75 65 73 20 66 6f 72 20 42 74  te values for Bt
5c90: 4c 6f 63 6b 2e 65 4c 6f 63 6b 20 2a 2f 0a 23 64  Lock.eLock */.#d
5ca0: 65 66 69 6e 65 20 52 45 41 44 5f 4c 4f 43 4b 20  efine READ_LOCK 
5cb0: 20 20 20 20 31 0a 23 64 65 66 69 6e 65 20 57 52      1.#define WR
5cc0: 49 54 45 5f 4c 4f 43 4b 20 20 20 20 32 0a 0a 2f  ITE_LOCK    2../
5cd0: 2a 0a 2a 2a 20 54 68 65 73 65 20 6d 61 63 72 6f  *.** These macro
5ce0: 73 20 64 65 66 69 6e 65 20 74 68 65 20 6c 6f 63  s define the loc
5cf0: 61 74 69 6f 6e 20 6f 66 20 74 68 65 20 70 6f 69  ation of the poi
5d00: 6e 74 65 72 2d 6d 61 70 20 65 6e 74 72 79 20 66  nter-map entry f
5d10: 6f 72 20 61 20 0a 2a 2a 20 64 61 74 61 62 61 73  or a .** databas
5d20: 65 20 70 61 67 65 2e 20 54 68 65 20 66 69 72 73  e page. The firs
5d30: 74 20 61 72 67 75 6d 65 6e 74 20 74 6f 20 65 61  t argument to ea
5d40: 63 68 20 69 73 20 74 68 65 20 6e 75 6d 62 65 72  ch is the number
5d50: 20 6f 66 20 75 73 61 62 6c 65 0a 2a 2a 20 62 79   of usable.** by
5d60: 74 65 73 20 6f 6e 20 65 61 63 68 20 70 61 67 65  tes on each page
5d70: 20 6f 66 20 74 68 65 20 64 61 74 61 62 61 73 65   of the database
5d80: 20 28 6f 66 74 65 6e 20 31 30 32 34 29 2e 20 54   (often 1024). T
5d90: 68 65 20 73 65 63 6f 6e 64 20 69 73 20 74 68 65  he second is the
5da0: 0a 2a 2a 20 70 61 67 65 20 6e 75 6d 62 65 72 20  .** page number 
5db0: 74 6f 20 6c 6f 6f 6b 20 75 70 20 69 6e 20 74 68  to look up in th
5dc0: 65 20 70 6f 69 6e 74 65 72 20 6d 61 70 2e 0a 2a  e pointer map..*
5dd0: 2a 0a 2a 2a 20 50 54 52 4d 41 50 5f 50 41 47 45  *.** PTRMAP_PAGE
5de0: 4e 4f 20 72 65 74 75 72 6e 73 20 74 68 65 20 64  NO returns the d
5df0: 61 74 61 62 61 73 65 20 70 61 67 65 20 6e 75 6d  atabase page num
5e00: 62 65 72 20 6f 66 20 74 68 65 20 70 6f 69 6e 74  ber of the point
5e10: 65 72 2d 6d 61 70 0a 2a 2a 20 70 61 67 65 20 74  er-map.** page t
5e20: 68 61 74 20 73 74 6f 72 65 73 20 74 68 65 20 72  hat stores the r
5e30: 65 71 75 69 72 65 64 20 70 6f 69 6e 74 65 72 2e  equired pointer.
5e40: 20 50 54 52 4d 41 50 5f 50 54 52 4f 46 46 53 45   PTRMAP_PTROFFSE
5e50: 54 20 72 65 74 75 72 6e 73 0a 2a 2a 20 74 68 65  T returns.** the
5e60: 20 6f 66 66 73 65 74 20 6f 66 20 74 68 65 20 72   offset of the r
5e70: 65 71 75 65 73 74 65 64 20 6d 61 70 20 65 6e 74  equested map ent
5e80: 72 79 2e 0a 2a 2a 0a 2a 2a 20 49 66 20 74 68 65  ry..**.** If the
5e90: 20 70 67 6e 6f 20 61 72 67 75 6d 65 6e 74 20 70   pgno argument p
5ea0: 61 73 73 65 64 20 74 6f 20 50 54 52 4d 41 50 5f  assed to PTRMAP_
5eb0: 50 41 47 45 4e 4f 20 69 73 20 61 20 70 6f 69 6e  PAGENO is a poin
5ec0: 74 65 72 2d 6d 61 70 20 70 61 67 65 2c 0a 2a 2a  ter-map page,.**
5ed0: 20 74 68 65 6e 20 70 67 6e 6f 20 69 73 20 72 65   then pgno is re
5ee0: 74 75 72 6e 65 64 2e 20 53 6f 20 28 70 67 6e 6f  turned. So (pgno
5ef0: 3d 3d 50 54 52 4d 41 50 5f 50 41 47 45 4e 4f 28  ==PTRMAP_PAGENO(
5f00: 70 67 73 7a 2c 20 70 67 6e 6f 29 29 20 63 61 6e  pgsz, pgno)) can
5f10: 20 62 65 0a 2a 2a 20 75 73 65 64 20 74 6f 20 74   be.** used to t
5f20: 65 73 74 20 69 66 20 70 67 6e 6f 20 69 73 20 61  est if pgno is a
5f30: 20 70 6f 69 6e 74 65 72 2d 6d 61 70 20 70 61 67   pointer-map pag
5f40: 65 2e 20 50 54 52 4d 41 50 5f 49 53 50 41 47 45  e. PTRMAP_ISPAGE
5f50: 20 69 6d 70 6c 65 6d 65 6e 74 73 0a 2a 2a 20 74   implements.** t
5f60: 68 69 73 20 74 65 73 74 2e 0a 2a 2f 0a 23 64 65  his test..*/.#de
5f70: 66 69 6e 65 20 50 54 52 4d 41 50 5f 50 41 47 45  fine PTRMAP_PAGE
5f80: 4e 4f 28 70 42 74 2c 20 70 67 6e 6f 29 20 70 74  NO(pBt, pgno) pt
5f90: 72 6d 61 70 50 61 67 65 6e 6f 28 70 42 74 2c 20  rmapPageno(pBt, 
5fa0: 70 67 6e 6f 29 0a 23 64 65 66 69 6e 65 20 50 54  pgno).#define PT
5fb0: 52 4d 41 50 5f 50 54 52 4f 46 46 53 45 54 28 70  RMAP_PTROFFSET(p
5fc0: 67 70 74 72 6d 61 70 2c 20 70 67 6e 6f 29 20 28  gptrmap, pgno) (
5fd0: 35 2a 28 70 67 6e 6f 2d 70 67 70 74 72 6d 61 70  5*(pgno-pgptrmap
5fe0: 2d 31 29 29 0a 23 64 65 66 69 6e 65 20 50 54 52  -1)).#define PTR
5ff0: 4d 41 50 5f 49 53 50 41 47 45 28 70 42 74 2c 20  MAP_ISPAGE(pBt, 
6000: 70 67 6e 6f 29 20 28 50 54 52 4d 41 50 5f 50 41  pgno) (PTRMAP_PA
6010: 47 45 4e 4f 28 28 70 42 74 29 2c 28 70 67 6e 6f  GENO((pBt),(pgno
6020: 29 29 3d 3d 28 70 67 6e 6f 29 29 0a 0a 2f 2a 0a  ))==(pgno))../*.
6030: 2a 2a 20 54 68 65 20 70 6f 69 6e 74 65 72 20 6d  ** The pointer m
6040: 61 70 20 69 73 20 61 20 6c 6f 6f 6b 75 70 20 74  ap is a lookup t
6050: 61 62 6c 65 20 74 68 61 74 20 69 64 65 6e 74 69  able that identi
6060: 66 69 65 73 20 74 68 65 20 70 61 72 65 6e 74 20  fies the parent 
6070: 70 61 67 65 20 66 6f 72 0a 2a 2a 20 65 61 63 68  page for.** each
6080: 20 63 68 69 6c 64 20 70 61 67 65 20 69 6e 20 74   child page in t
6090: 68 65 20 64 61 74 61 62 61 73 65 20 66 69 6c 65  he database file
60a0: 2e 20 20 54 68 65 20 70 61 72 65 6e 74 20 70 61  .  The parent pa
60b0: 67 65 20 69 73 20 74 68 65 20 70 61 67 65 20 74  ge is the page t
60c0: 68 61 74 0a 2a 2a 20 63 6f 6e 74 61 69 6e 73 20  hat.** contains 
60d0: 61 20 70 6f 69 6e 74 65 72 20 74 6f 20 74 68 65  a pointer to the
60e0: 20 63 68 69 6c 64 2e 20 20 45 76 65 72 79 20 70   child.  Every p
60f0: 61 67 65 20 69 6e 20 74 68 65 20 64 61 74 61 62  age in the datab
6100: 61 73 65 20 63 6f 6e 74 61 69 6e 73 0a 2a 2a 20  ase contains.** 
6110: 30 20 6f 72 20 31 20 70 61 72 65 6e 74 20 70 61  0 or 1 parent pa
6120: 67 65 73 2e 20 20 28 49 6e 20 74 68 69 73 20 63  ges.  (In this c
6130: 6f 6e 74 65 78 74 20 27 64 61 74 61 62 61 73 65  ontext 'database
6140: 20 70 61 67 65 27 20 72 65 66 65 72 73 0a 2a 2a   page' refers.**
6150: 20 74 6f 20 61 6e 79 20 70 61 67 65 20 74 68 61   to any page tha
6160: 74 20 69 73 20 6e 6f 74 20 70 61 72 74 20 6f 66  t is not part of
6170: 20 74 68 65 20 70 6f 69 6e 74 65 72 20 6d 61 70   the pointer map
6180: 20 69 74 73 65 6c 66 2e 29 20 20 45 61 63 68 20   itself.)  Each 
6190: 70 6f 69 6e 74 65 72 20 6d 61 70 0a 2a 2a 20 65  pointer map.** e
61a0: 6e 74 72 79 20 63 6f 6e 73 69 73 74 73 20 6f 66  ntry consists of
61b0: 20 61 20 73 69 6e 67 6c 65 20 62 79 74 65 20 27   a single byte '
61c0: 74 79 70 65 27 20 61 6e 64 20 61 20 34 20 62 79  type' and a 4 by
61d0: 74 65 20 70 61 72 65 6e 74 20 70 61 67 65 20 6e  te parent page n
61e0: 75 6d 62 65 72 2e 0a 2a 2a 20 54 68 65 20 50 54  umber..** The PT
61f0: 52 4d 41 50 5f 58 58 58 20 69 64 65 6e 74 69 66  RMAP_XXX identif
6200: 69 65 72 73 20 62 65 6c 6f 77 20 61 72 65 20 74  iers below are t
6210: 68 65 20 76 61 6c 69 64 20 74 79 70 65 73 2e 0a  he valid types..
6220: 2a 2a 0a 2a 2a 20 54 68 65 20 70 75 72 70 6f 73  **.** The purpos
6230: 65 20 6f 66 20 74 68 65 20 70 6f 69 6e 74 65 72  e of the pointer
6240: 20 6d 61 70 20 69 73 20 74 6f 20 66 61 63 69 6c   map is to facil
6250: 69 74 79 20 6d 6f 76 69 6e 67 20 70 61 67 65 73  ity moving pages
6260: 20 66 72 6f 6d 20 6f 6e 65 0a 2a 2a 20 70 6f 73   from one.** pos
6270: 69 74 69 6f 6e 20 69 6e 20 74 68 65 20 66 69 6c  ition in the fil
6280: 65 20 74 6f 20 61 6e 6f 74 68 65 72 20 61 73 20  e to another as 
6290: 70 61 72 74 20 6f 66 20 61 75 74 6f 76 61 63 75  part of autovacu
62a0: 75 6d 2e 20 20 57 68 65 6e 20 61 20 70 61 67 65  um.  When a page
62b0: 0a 2a 2a 20 69 73 20 6d 6f 76 65 64 2c 20 74 68  .** is moved, th
62c0: 65 20 70 6f 69 6e 74 65 72 20 69 6e 20 69 74 73  e pointer in its
62d0: 20 70 61 72 65 6e 74 20 6d 75 73 74 20 62 65 20   parent must be 
62e0: 75 70 64 61 74 65 64 20 74 6f 20 70 6f 69 6e 74  updated to point
62f0: 20 74 6f 20 74 68 65 0a 2a 2a 20 6e 65 77 20 6c   to the.** new l
6300: 6f 63 61 74 69 6f 6e 2e 20 20 54 68 65 20 70 6f  ocation.  The po
6310: 69 6e 74 65 72 20 6d 61 70 20 69 73 20 75 73 65  inter map is use
6320: 64 20 74 6f 20 6c 6f 63 61 74 65 20 74 68 65 20  d to locate the 
6330: 70 61 72 65 6e 74 20 70 61 67 65 20 71 75 69 63  parent page quic
6340: 6b 6c 79 2e 0a 2a 2a 0a 2a 2a 20 50 54 52 4d 41  kly..**.** PTRMA
6350: 50 5f 52 4f 4f 54 50 41 47 45 3a 20 54 68 65 20  P_ROOTPAGE: The 
6360: 64 61 74 61 62 61 73 65 20 70 61 67 65 20 69 73  database page is
6370: 20 61 20 72 6f 6f 74 2d 70 61 67 65 2e 20 54 68   a root-page. Th
6380: 65 20 70 61 67 65 2d 6e 75 6d 62 65 72 20 69 73  e page-number is
6390: 20 6e 6f 74 0a 2a 2a 20 20 20 20 20 20 20 20 20   not.**         
63a0: 20 20 20 20 20 20 20 20 20 75 73 65 64 20 69 6e           used in
63b0: 20 74 68 69 73 20 63 61 73 65 2e 0a 2a 2a 0a 2a   this case..**.*
63c0: 2a 20 50 54 52 4d 41 50 5f 46 52 45 45 50 41 47  * PTRMAP_FREEPAG
63d0: 45 3a 20 54 68 65 20 64 61 74 61 62 61 73 65 20  E: The database 
63e0: 70 61 67 65 20 69 73 20 61 6e 20 75 6e 75 73 65  page is an unuse
63f0: 64 20 28 66 72 65 65 29 20 70 61 67 65 2e 20 54  d (free) page. T
6400: 68 65 20 70 61 67 65 2d 6e 75 6d 62 65 72 20 0a  he page-number .
6410: 2a 2a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  **              
6420: 20 20 20 20 69 73 20 6e 6f 74 20 75 73 65 64 20      is not used 
6430: 69 6e 20 74 68 69 73 20 63 61 73 65 2e 0a 2a 2a  in this case..**
6440: 0a 2a 2a 20 50 54 52 4d 41 50 5f 4f 56 45 52 46  .** PTRMAP_OVERF
6450: 4c 4f 57 31 3a 20 54 68 65 20 64 61 74 61 62 61  LOW1: The databa
6460: 73 65 20 70 61 67 65 20 69 73 20 74 68 65 20 66  se page is the f
6470: 69 72 73 74 20 70 61 67 65 20 69 6e 20 61 20 6c  irst page in a l
6480: 69 73 74 20 6f 66 20 0a 2a 2a 20 20 20 20 20 20  ist of .**      
6490: 20 20 20 20 20 20 20 20 20 20 20 20 20 6f 76 65               ove
64a0: 72 66 6c 6f 77 20 70 61 67 65 73 2e 20 54 68 65  rflow pages. The
64b0: 20 70 61 67 65 20 6e 75 6d 62 65 72 20 69 64 65   page number ide
64c0: 6e 74 69 66 69 65 73 20 74 68 65 20 70 61 67 65  ntifies the page
64d0: 20 74 68 61 74 0a 2a 2a 20 20 20 20 20 20 20 20   that.**        
64e0: 20 20 20 20 20 20 20 20 20 20 20 63 6f 6e 74 61             conta
64f0: 69 6e 73 20 74 68 65 20 63 65 6c 6c 20 77 69 74  ins the cell wit
6500: 68 20 61 20 70 6f 69 6e 74 65 72 20 74 6f 20 74  h a pointer to t
6510: 68 69 73 20 6f 76 65 72 66 6c 6f 77 20 70 61 67  his overflow pag
6520: 65 2e 0a 2a 2a 0a 2a 2a 20 50 54 52 4d 41 50 5f  e..**.** PTRMAP_
6530: 4f 56 45 52 46 4c 4f 57 32 3a 20 54 68 65 20 64  OVERFLOW2: The d
6540: 61 74 61 62 61 73 65 20 70 61 67 65 20 69 73 20  atabase page is 
6550: 74 68 65 20 73 65 63 6f 6e 64 20 6f 72 20 6c 61  the second or la
6560: 74 65 72 20 70 61 67 65 20 69 6e 20 61 20 6c 69  ter page in a li
6570: 73 74 20 6f 66 0a 2a 2a 20 20 20 20 20 20 20 20  st of.**        
6580: 20 20 20 20 20 20 20 20 20 20 20 6f 76 65 72 66             overf
6590: 6c 6f 77 20 70 61 67 65 73 2e 20 54 68 65 20 70  low pages. The p
65a0: 61 67 65 2d 6e 75 6d 62 65 72 20 69 64 65 6e 74  age-number ident
65b0: 69 66 69 65 73 20 74 68 65 20 70 72 65 76 69 6f  ifies the previo
65c0: 75 73 0a 2a 2a 20 20 20 20 20 20 20 20 20 20 20  us.**           
65d0: 20 20 20 20 20 20 20 20 70 61 67 65 20 69 6e 20          page in 
65e0: 74 68 65 20 6f 76 65 72 66 6c 6f 77 20 70 61 67  the overflow pag
65f0: 65 20 6c 69 73 74 2e 0a 2a 2a 0a 2a 2a 20 50 54  e list..**.** PT
6600: 52 4d 41 50 5f 42 54 52 45 45 3a 20 54 68 65 20  RMAP_BTREE: The 
6610: 64 61 74 61 62 61 73 65 20 70 61 67 65 20 69 73  database page is
6620: 20 61 20 6e 6f 6e 2d 72 6f 6f 74 20 62 74 72 65   a non-root btre
6630: 65 20 70 61 67 65 2e 20 54 68 65 20 70 61 67 65  e page. The page
6640: 20 6e 75 6d 62 65 72 0a 2a 2a 20 20 20 20 20 20   number.**      
6650: 20 20 20 20 20 20 20 20 20 69 64 65 6e 74 69 66           identif
6660: 69 65 73 20 74 68 65 20 70 61 72 65 6e 74 20 70  ies the parent p
6670: 61 67 65 20 69 6e 20 74 68 65 20 62 74 72 65 65  age in the btree
6680: 2e 0a 2a 2f 0a 23 64 65 66 69 6e 65 20 50 54 52  ..*/.#define PTR
6690: 4d 41 50 5f 52 4f 4f 54 50 41 47 45 20 31 0a 23  MAP_ROOTPAGE 1.#
66a0: 64 65 66 69 6e 65 20 50 54 52 4d 41 50 5f 46 52  define PTRMAP_FR
66b0: 45 45 50 41 47 45 20 32 0a 23 64 65 66 69 6e 65  EEPAGE 2.#define
66c0: 20 50 54 52 4d 41 50 5f 4f 56 45 52 46 4c 4f 57   PTRMAP_OVERFLOW
66d0: 31 20 33 0a 23 64 65 66 69 6e 65 20 50 54 52 4d  1 3.#define PTRM
66e0: 41 50 5f 4f 56 45 52 46 4c 4f 57 32 20 34 0a 23  AP_OVERFLOW2 4.#
66f0: 64 65 66 69 6e 65 20 50 54 52 4d 41 50 5f 42 54  define PTRMAP_BT
6700: 52 45 45 20 35 0a 0a 2f 2a 20 41 20 62 75 6e 63  REE 5../* A bunc
6710: 68 20 6f 66 20 61 73 73 65 72 74 28 29 20 73 74  h of assert() st
6720: 61 74 65 6d 65 6e 74 73 20 74 6f 20 63 68 65 63  atements to chec
6730: 6b 20 74 68 65 20 74 72 61 6e 73 61 63 74 69 6f  k the transactio
6740: 6e 20 73 74 61 74 65 20 76 61 72 69 61 62 6c 65  n state variable
6750: 73 0a 2a 2a 20 6f 66 20 68 61 6e 64 6c 65 20 70  s.** of handle p
6760: 20 28 74 79 70 65 20 42 74 72 65 65 2a 29 20 61   (type Btree*) a
6770: 72 65 20 69 6e 74 65 72 6e 61 6c 6c 79 20 63 6f  re internally co
6780: 6e 73 69 73 74 65 6e 74 2e 0a 2a 2f 0a 23 64 65  nsistent..*/.#de
6790: 66 69 6e 65 20 62 74 72 65 65 49 6e 74 65 67 72  fine btreeIntegr
67a0: 69 74 79 28 70 29 20 5c 0a 20 20 61 73 73 65 72  ity(p) \.  asser
67b0: 74 28 20 70 2d 3e 70 42 74 2d 3e 69 6e 54 72 61  t( p->pBt->inTra
67c0: 6e 73 61 63 74 69 6f 6e 21 3d 54 52 41 4e 53 5f  nsaction!=TRANS_
67d0: 4e 4f 4e 45 20 7c 7c 20 70 2d 3e 70 42 74 2d 3e  NONE || p->pBt->
67e0: 6e 54 72 61 6e 73 61 63 74 69 6f 6e 3d 3d 30 20  nTransaction==0 
67f0: 29 3b 20 5c 0a 20 20 61 73 73 65 72 74 28 20 70  ); \.  assert( p
6800: 2d 3e 70 42 74 2d 3e 69 6e 54 72 61 6e 73 61 63  ->pBt->inTransac
6810: 74 69 6f 6e 3e 3d 70 2d 3e 69 6e 54 72 61 6e 73  tion>=p->inTrans
6820: 20 29 3b 20 0a 0a 0a 2f 2a 0a 2a 2a 20 54 68 65   ); .../*.** The
6830: 20 49 53 41 55 54 4f 56 41 43 55 55 4d 20 6d 61   ISAUTOVACUUM ma
6840: 63 72 6f 20 69 73 20 75 73 65 64 20 77 69 74 68  cro is used with
6850: 69 6e 20 62 61 6c 61 6e 63 65 5f 6e 6f 6e 72 6f  in balance_nonro
6860: 6f 74 28 29 20 74 6f 20 64 65 74 65 72 6d 69 6e  ot() to determin
6870: 65 0a 2a 2a 20 69 66 20 74 68 65 20 64 61 74 61  e.** if the data
6880: 62 61 73 65 20 73 75 70 70 6f 72 74 73 20 61 75  base supports au
6890: 74 6f 2d 76 61 63 75 75 6d 20 6f 72 20 6e 6f 74  to-vacuum or not
68a0: 2e 20 42 65 63 61 75 73 65 20 69 74 20 69 73 20  . Because it is 
68b0: 75 73 65 64 0a 2a 2a 20 77 69 74 68 69 6e 20 61  used.** within a
68c0: 6e 20 65 78 70 72 65 73 73 69 6f 6e 20 74 68 61  n expression tha
68d0: 74 20 69 73 20 61 6e 20 61 72 67 75 6d 65 6e 74  t is an argument
68e0: 20 74 6f 20 61 6e 6f 74 68 65 72 20 6d 61 63 72   to another macr
68f0: 6f 20 0a 2a 2a 20 28 73 71 6c 69 74 65 4d 61 6c  o .** (sqliteMal
6900: 6c 6f 63 52 61 77 29 2c 20 69 74 20 69 73 20 6e  locRaw), it is n
6910: 6f 74 20 70 6f 73 73 69 62 6c 65 20 74 6f 20 75  ot possible to u
6920: 73 65 20 63 6f 6e 64 69 74 69 6f 6e 61 6c 20 63  se conditional c
6930: 6f 6d 70 69 6c 61 74 69 6f 6e 2e 0a 2a 2a 20 53  ompilation..** S
6940: 6f 2c 20 74 68 69 73 20 6d 61 63 72 6f 20 69 73  o, this macro is
6950: 20 64 65 66 69 6e 65 64 20 69 6e 73 74 65 61 64   defined instead
6960: 2e 0a 2a 2f 0a 23 69 66 6e 64 65 66 20 53 51 4c  ..*/.#ifndef SQL
6970: 49 54 45 5f 4f 4d 49 54 5f 41 55 54 4f 56 41 43  ITE_OMIT_AUTOVAC
6980: 55 55 4d 0a 23 64 65 66 69 6e 65 20 49 53 41 55  UUM.#define ISAU
6990: 54 4f 56 41 43 55 55 4d 20 28 70 42 74 2d 3e 61  TOVACUUM (pBt->a
69a0: 75 74 6f 56 61 63 75 75 6d 29 0a 23 65 6c 73 65  utoVacuum).#else
69b0: 0a 23 64 65 66 69 6e 65 20 49 53 41 55 54 4f 56  .#define ISAUTOV
69c0: 41 43 55 55 4d 20 30 0a 23 65 6e 64 69 66 0a 0a  ACUUM 0.#endif..
69d0: 0a 2f 2a 0a 2a 2a 20 54 68 69 73 20 73 74 72 75  ./*.** This stru
69e0: 63 74 75 72 65 20 69 73 20 70 61 73 73 65 64 20  cture is passed 
69f0: 61 72 6f 75 6e 64 20 74 68 72 6f 75 67 68 20 61  around through a
6a00: 6c 6c 20 74 68 65 20 73 61 6e 69 74 79 20 63 68  ll the sanity ch
6a10: 65 63 6b 69 6e 67 20 72 6f 75 74 69 6e 65 73 0a  ecking routines.
6a20: 2a 2a 20 69 6e 20 6f 72 64 65 72 20 74 6f 20 6b  ** in order to k
6a30: 65 65 70 20 74 72 61 63 6b 20 6f 66 20 73 6f 6d  eep track of som
6a40: 65 20 67 6c 6f 62 61 6c 20 73 74 61 74 65 20 69  e global state i
6a50: 6e 66 6f 72 6d 61 74 69 6f 6e 2e 0a 2a 2f 0a 74  nformation..*/.t
6a60: 79 70 65 64 65 66 20 73 74 72 75 63 74 20 49 6e  ypedef struct In
6a70: 74 65 67 72 69 74 79 43 6b 20 49 6e 74 65 67 72  tegrityCk Integr
6a80: 69 74 79 43 6b 3b 0a 73 74 72 75 63 74 20 49 6e  ityCk;.struct In
6a90: 74 65 67 72 69 74 79 43 6b 20 7b 0a 20 20 42 74  tegrityCk {.  Bt
6aa0: 53 68 61 72 65 64 20 2a 70 42 74 3b 20 20 20 20  Shared *pBt;    
6ab0: 2f 2a 20 54 68 65 20 74 72 65 65 20 62 65 69 6e  /* The tree bein
6ac0: 67 20 63 68 65 63 6b 65 64 20 6f 75 74 20 2a 2f  g checked out */
6ad0: 0a 20 20 50 61 67 65 72 20 2a 70 50 61 67 65 72  .  Pager *pPager
6ae0: 3b 20 20 20 20 2f 2a 20 54 68 65 20 61 73 73 6f  ;    /* The asso
6af0: 63 69 61 74 65 64 20 70 61 67 65 72 2e 20 20 41  ciated pager.  A
6b00: 6c 73 6f 20 61 63 63 65 73 73 69 62 6c 65 20 62  lso accessible b
6b10: 79 20 70 42 74 2d 3e 70 50 61 67 65 72 20 2a 2f  y pBt->pPager */
6b20: 0a 20 20 50 67 6e 6f 20 6e 50 61 67 65 3b 20 20  .  Pgno nPage;  
6b30: 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f       /* Number o
6b40: 66 20 70 61 67 65 73 20 69 6e 20 74 68 65 20 64  f pages in the d
6b50: 61 74 61 62 61 73 65 20 2a 2f 0a 20 20 69 6e 74  atabase */.  int
6b60: 20 2a 61 6e 52 65 66 3b 20 20 20 20 20 20 20 2f   *anRef;       /
6b70: 2a 20 4e 75 6d 62 65 72 20 6f 66 20 74 69 6d 65  * Number of time
6b80: 73 20 65 61 63 68 20 70 61 67 65 20 69 73 20 72  s each page is r
6b90: 65 66 65 72 65 6e 63 65 64 20 2a 2f 0a 20 20 69  eferenced */.  i
6ba0: 6e 74 20 6d 78 45 72 72 3b 20 20 20 20 20 20 20  nt mxErr;       
6bb0: 20 2f 2a 20 53 74 6f 70 20 61 63 63 75 6d 75 6c   /* Stop accumul
6bc0: 61 74 69 6e 67 20 65 72 72 6f 72 73 20 77 68 65  ating errors whe
6bd0: 6e 20 74 68 69 73 20 72 65 61 63 68 65 73 20 7a  n this reaches z
6be0: 65 72 6f 20 2a 2f 0a 20 20 69 6e 74 20 6e 45 72  ero */.  int nEr
6bf0: 72 3b 20 20 20 20 20 20 20 20 20 2f 2a 20 4e 75  r;         /* Nu
6c00: 6d 62 65 72 20 6f 66 20 6d 65 73 73 61 67 65 73  mber of messages
6c10: 20 77 72 69 74 74 65 6e 20 74 6f 20 7a 45 72 72   written to zErr
6c20: 4d 73 67 20 73 6f 20 66 61 72 20 2a 2f 0a 20 20  Msg so far */.  
6c30: 69 6e 74 20 6d 61 6c 6c 6f 63 46 61 69 6c 65 64  int mallocFailed
6c40: 3b 20 2f 2a 20 41 20 6d 65 6d 6f 72 79 20 61 6c  ; /* A memory al
6c50: 6c 6f 63 61 74 69 6f 6e 20 65 72 72 6f 72 20 68  location error h
6c60: 61 73 20 6f 63 63 75 72 72 65 64 20 2a 2f 0a 20  as occurred */. 
6c70: 20 53 74 72 41 63 63 75 6d 20 65 72 72 4d 73 67   StrAccum errMsg
6c80: 3b 20 20 2f 2a 20 41 63 63 75 6d 75 6c 61 74 65  ;  /* Accumulate
6c90: 20 74 68 65 20 65 72 72 6f 72 20 6d 65 73 73 61   the error messa
6ca0: 67 65 20 74 65 78 74 20 68 65 72 65 20 2a 2f 0a  ge text here */.
6cb0: 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 52 65 61 64 20 6f  };../*.** Read o
6cc0: 72 20 77 72 69 74 65 20 61 20 74 77 6f 2d 20 61  r write a two- a
6cd0: 6e 64 20 66 6f 75 72 2d 62 79 74 65 20 62 69 67  nd four-byte big
6ce0: 2d 65 6e 64 69 61 6e 20 69 6e 74 65 67 65 72 20  -endian integer 
6cf0: 76 61 6c 75 65 73 2e 0a 2a 2f 0a 23 64 65 66 69  values..*/.#defi
6d00: 6e 65 20 67 65 74 32 62 79 74 65 28 78 29 20 20  ne get2byte(x)  
6d10: 20 28 28 78 29 5b 30 5d 3c 3c 38 20 7c 20 28 78   ((x)[0]<<8 | (x
6d20: 29 5b 31 5d 29 0a 23 64 65 66 69 6e 65 20 70 75  )[1]).#define pu
6d30: 74 32 62 79 74 65 28 70 2c 76 29 20 28 28 70 29  t2byte(p,v) ((p)
6d40: 5b 30 5d 20 3d 20 28 76 29 3e 3e 38 2c 20 28 70  [0] = (v)>>8, (p
6d50: 29 5b 31 5d 20 3d 20 28 76 29 29 0a 23 64 65 66  )[1] = (v)).#def
6d60: 69 6e 65 20 67 65 74 34 62 79 74 65 20 73 71 6c  ine get4byte sql
6d70: 69 74 65 33 47 65 74 34 62 79 74 65 0a 23 64 65  ite3Get4byte.#de
6d80: 66 69 6e 65 20 70 75 74 34 62 79 74 65 20 73 71  fine put4byte sq
6d90: 6c 69 74 65 33 50 75 74 34 62 79 74 65 0a 0a 2f  lite3Put4byte../
6da0: 2a 0a 2a 2a 20 49 6e 74 65 72 6e 61 6c 20 72 6f  *.** Internal ro
6db0: 75 74 69 6e 65 73 20 74 68 61 74 20 73 68 6f 75  utines that shou
6dc0: 6c 64 20 62 65 20 61 63 63 65 73 73 65 64 20 62  ld be accessed b
6dd0: 79 20 74 68 65 20 62 74 72 65 65 20 6c 61 79 65  y the btree laye
6de0: 72 20 6f 6e 6c 79 2e 0a 2a 2f 0a 69 6e 74 20 73  r only..*/.int s
6df0: 71 6c 69 74 65 33 42 74 72 65 65 47 65 74 50 61  qlite3BtreeGetPa
6e00: 67 65 28 42 74 53 68 61 72 65 64 2a 2c 20 50 67  ge(BtShared*, Pg
6e10: 6e 6f 2c 20 4d 65 6d 50 61 67 65 2a 2a 2c 20 69  no, MemPage**, i
6e20: 6e 74 29 3b 0a 69 6e 74 20 73 71 6c 69 74 65 33  nt);.int sqlite3
6e30: 42 74 72 65 65 49 6e 69 74 50 61 67 65 28 4d 65  BtreeInitPage(Me
6e40: 6d 50 61 67 65 20 2a 70 50 61 67 65 29 3b 0a 76  mPage *pPage);.v
6e50: 6f 69 64 20 73 71 6c 69 74 65 33 42 74 72 65 65  oid sqlite3Btree
6e60: 50 61 72 73 65 43 65 6c 6c 50 74 72 28 4d 65 6d  ParseCellPtr(Mem
6e70: 50 61 67 65 2a 2c 20 75 38 2a 2c 20 43 65 6c 6c  Page*, u8*, Cell
6e80: 49 6e 66 6f 2a 29 3b 0a 76 6f 69 64 20 73 71 6c  Info*);.void sql
6e90: 69 74 65 33 42 74 72 65 65 50 61 72 73 65 43 65  ite3BtreeParseCe
6ea0: 6c 6c 28 4d 65 6d 50 61 67 65 2a 2c 20 69 6e 74  ll(MemPage*, int
6eb0: 2c 20 43 65 6c 6c 49 6e 66 6f 2a 29 3b 0a 69 6e  , CellInfo*);.in
6ec0: 74 20 73 71 6c 69 74 65 33 42 74 72 65 65 52 65  t sqlite3BtreeRe
6ed0: 73 74 6f 72 65 43 75 72 73 6f 72 50 6f 73 69 74  storeCursorPosit
6ee0: 69 6f 6e 28 42 74 43 75 72 73 6f 72 20 2a 70 43  ion(BtCursor *pC
6ef0: 75 72 29 3b 0a 76 6f 69 64 20 73 71 6c 69 74 65  ur);.void sqlite
6f00: 33 42 74 72 65 65 47 65 74 54 65 6d 70 43 75 72  3BtreeGetTempCur
6f10: 73 6f 72 28 42 74 43 75 72 73 6f 72 20 2a 70 43  sor(BtCursor *pC
6f20: 75 72 2c 20 42 74 43 75 72 73 6f 72 20 2a 70 54  ur, BtCursor *pT
6f30: 65 6d 70 43 75 72 29 3b 0a 76 6f 69 64 20 73 71  empCur);.void sq
6f40: 6c 69 74 65 33 42 74 72 65 65 52 65 6c 65 61 73  lite3BtreeReleas
6f50: 65 54 65 6d 70 43 75 72 73 6f 72 28 42 74 43 75  eTempCursor(BtCu
6f60: 72 73 6f 72 20 2a 70 43 75 72 29 3b 0a 76 6f 69  rsor *pCur);.voi
6f70: 64 20 73 71 6c 69 74 65 33 42 74 72 65 65 4d 6f  d sqlite3BtreeMo
6f80: 76 65 54 6f 50 61 72 65 6e 74 28 42 74 43 75 72  veToParent(BtCur
6f90: 73 6f 72 20 2a 70 43 75 72 29 3b 0a              sor *pCur);.