/ Hex Artifact Content
Login

Artifact 6e4cb69a9192a8d609c27034ae5f921cf0ecdde1:


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 32 39 20 32 30 30 38  nt.h,v 1.29 2008
0190: 2f 30 37 2f 31 38 20 30 39 3a 33 34 3a 35 37 20  /07/18 09:34:57 
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 69 64 78 53 68 69 66 74 3b 20 20 20 20 20 20   idxShift;      
2fd0: 20 20 20 2f 2a 20 54 72 75 65 20 69 66 20 43 65     /* True if Ce
2fe0: 6c 6c 20 69 6e 64 69 63 65 73 20 68 61 76 65 20  ll indices have 
2ff0: 63 68 61 6e 67 65 64 20 2a 2f 0a 20 20 75 38 20  changed */.  u8 
3000: 6e 4f 76 65 72 66 6c 6f 77 3b 20 20 20 20 20 20  nOverflow;      
3010: 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 6f    /* Number of o
3020: 76 65 72 66 6c 6f 77 20 63 65 6c 6c 20 62 6f 64  verflow cell bod
3030: 69 65 73 20 69 6e 20 61 43 65 6c 6c 5b 5d 20 2a  ies in aCell[] *
3040: 2f 0a 20 20 75 38 20 69 6e 74 4b 65 79 3b 20 20  /.  u8 intKey;  
3050: 20 20 20 20 20 20 20 20 20 2f 2a 20 54 72 75 65           /* True
3060: 20 69 66 20 69 6e 74 6b 65 79 20 66 6c 61 67 20   if intkey flag 
3070: 69 73 20 73 65 74 20 2a 2f 0a 20 20 75 38 20 6c  is set */.  u8 l
3080: 65 61 66 3b 20 20 20 20 20 20 20 20 20 20 20 20  eaf;            
3090: 20 2f 2a 20 54 72 75 65 20 69 66 20 6c 65 61 66   /* True if leaf
30a0: 20 66 6c 61 67 20 69 73 20 73 65 74 20 2a 2f 0a   flag is set */.
30b0: 20 20 75 38 20 68 61 73 44 61 74 61 3b 20 20 20    u8 hasData;   
30c0: 20 20 20 20 20 20 20 2f 2a 20 54 72 75 65 20 69         /* True i
30d0: 66 20 74 68 69 73 20 70 61 67 65 20 73 74 6f 72  f this page stor
30e0: 65 73 20 64 61 74 61 20 2a 2f 0a 20 20 75 38 20  es data */.  u8 
30f0: 68 64 72 4f 66 66 73 65 74 3b 20 20 20 20 20 20  hdrOffset;      
3100: 20 20 2f 2a 20 31 30 30 20 66 6f 72 20 70 61 67    /* 100 for pag
3110: 65 20 31 2e 20 20 30 20 6f 74 68 65 72 77 69 73  e 1.  0 otherwis
3120: 65 20 2a 2f 0a 20 20 75 38 20 63 68 69 6c 64 50  e */.  u8 childP
3130: 74 72 53 69 7a 65 3b 20 20 20 20 20 2f 2a 20 30  trSize;     /* 0
3140: 20 69 66 20 6c 65 61 66 3d 3d 31 2e 20 20 34 20   if leaf==1.  4 
3150: 69 66 20 6c 65 61 66 3d 3d 30 20 2a 2f 0a 20 20  if leaf==0 */.  
3160: 75 31 36 20 6d 61 78 4c 6f 63 61 6c 3b 20 20 20  u16 maxLocal;   
3170: 20 20 20 20 20 2f 2a 20 43 6f 70 79 20 6f 66 20       /* Copy of 
3180: 42 74 53 68 61 72 65 64 2e 6d 61 78 4c 6f 63 61  BtShared.maxLoca
3190: 6c 20 6f 72 20 42 74 53 68 61 72 65 64 2e 6d 61  l or BtShared.ma
31a0: 78 4c 65 61 66 20 2a 2f 0a 20 20 75 31 36 20 6d  xLeaf */.  u16 m
31b0: 69 6e 4c 6f 63 61 6c 3b 20 20 20 20 20 20 20 20  inLocal;        
31c0: 2f 2a 20 43 6f 70 79 20 6f 66 20 42 74 53 68 61  /* Copy of BtSha
31d0: 72 65 64 2e 6d 69 6e 4c 6f 63 61 6c 20 6f 72 20  red.minLocal or 
31e0: 42 74 53 68 61 72 65 64 2e 6d 69 6e 4c 65 61 66  BtShared.minLeaf
31f0: 20 2a 2f 0a 20 20 75 31 36 20 63 65 6c 6c 4f 66   */.  u16 cellOf
3200: 66 73 65 74 3b 20 20 20 20 20 20 2f 2a 20 49 6e  fset;      /* In
3210: 64 65 78 20 69 6e 20 61 44 61 74 61 20 6f 66 20  dex in aData of 
3220: 66 69 72 73 74 20 63 65 6c 6c 20 70 6f 69 6e 74  first cell point
3230: 65 72 20 2a 2f 0a 20 20 75 31 36 20 69 64 78 50  er */.  u16 idxP
3240: 61 72 65 6e 74 3b 20 20 20 20 20 20 20 2f 2a 20  arent;       /* 
3250: 49 6e 64 65 78 20 69 6e 20 70 61 72 65 6e 74 20  Index in parent 
3260: 6f 66 20 74 68 69 73 20 6e 6f 64 65 20 2a 2f 0a  of this node */.
3270: 20 20 75 31 36 20 6e 46 72 65 65 3b 20 20 20 20    u16 nFree;    
3280: 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72         /* Number
3290: 20 6f 66 20 66 72 65 65 20 62 79 74 65 73 20 6f   of free bytes o
32a0: 6e 20 74 68 65 20 70 61 67 65 20 2a 2f 0a 20 20  n the page */.  
32b0: 75 31 36 20 6e 43 65 6c 6c 3b 20 20 20 20 20 20  u16 nCell;      
32c0: 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f       /* Number o
32d0: 66 20 63 65 6c 6c 73 20 6f 6e 20 74 68 69 73 20  f cells on this 
32e0: 70 61 67 65 2c 20 6c 6f 63 61 6c 20 61 6e 64 20  page, local and 
32f0: 6f 76 66 6c 20 2a 2f 0a 20 20 75 31 36 20 6d 61  ovfl */.  u16 ma
3300: 73 6b 50 61 67 65 3b 20 20 20 20 20 20 20 20 2f  skPage;        /
3310: 2a 20 4d 61 73 6b 20 66 6f 72 20 70 61 67 65 20  * Mask for page 
3320: 6f 66 66 73 65 74 20 2a 2f 0a 20 20 73 74 72 75  offset */.  stru
3330: 63 74 20 5f 4f 76 66 6c 43 65 6c 6c 20 7b 20 20  ct _OvflCell {  
3340: 20 2f 2a 20 43 65 6c 6c 73 20 74 68 61 74 20 77   /* Cells that w
3350: 69 6c 6c 20 6e 6f 74 20 66 69 74 20 6f 6e 20 61  ill not fit on a
3360: 44 61 74 61 5b 5d 20 2a 2f 0a 20 20 20 20 75 38  Data[] */.    u8
3370: 20 2a 70 43 65 6c 6c 3b 20 20 20 20 20 20 20 20   *pCell;        
3380: 20 20 2f 2a 20 50 6f 69 6e 74 65 72 73 20 74 6f    /* Pointers to
3390: 20 74 68 65 20 62 6f 64 79 20 6f 66 20 74 68 65   the body of the
33a0: 20 6f 76 65 72 66 6c 6f 77 20 63 65 6c 6c 20 2a   overflow cell *
33b0: 2f 0a 20 20 20 20 75 31 36 20 69 64 78 3b 20 20  /.    u16 idx;  
33c0: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 49 6e 73            /* Ins
33d0: 65 72 74 20 74 68 69 73 20 63 65 6c 6c 20 62 65  ert this cell be
33e0: 66 6f 72 65 20 69 64 78 2d 74 68 20 6e 6f 6e 2d  fore idx-th non-
33f0: 6f 76 65 72 66 6c 6f 77 20 63 65 6c 6c 20 2a 2f  overflow cell */
3400: 0a 20 20 7d 20 61 4f 76 66 6c 5b 35 5d 3b 0a 20  .  } aOvfl[5];. 
3410: 20 42 74 53 68 61 72 65 64 20 2a 70 42 74 3b 20   BtShared *pBt; 
3420: 20 20 20 20 20 20 2f 2a 20 50 6f 69 6e 74 65 72        /* Pointer
3430: 20 74 6f 20 42 74 53 68 61 72 65 64 20 74 68 61   to BtShared tha
3440: 74 20 74 68 69 73 20 70 61 67 65 20 69 73 20 70  t this page is p
3450: 61 72 74 20 6f 66 20 2a 2f 0a 20 20 75 38 20 2a  art of */.  u8 *
3460: 61 44 61 74 61 3b 20 20 20 20 20 20 20 20 20 20  aData;          
3470: 20 2f 2a 20 50 6f 69 6e 74 65 72 20 74 6f 20 64   /* Pointer to d
3480: 69 73 6b 20 69 6d 61 67 65 20 6f 66 20 74 68 65  isk image of the
3490: 20 70 61 67 65 20 64 61 74 61 20 2a 2f 0a 20 20   page data */.  
34a0: 44 62 50 61 67 65 20 2a 70 44 62 50 61 67 65 3b  DbPage *pDbPage;
34b0: 20 20 20 20 20 2f 2a 20 50 61 67 65 72 20 70 61       /* Pager pa
34c0: 67 65 20 68 61 6e 64 6c 65 20 2a 2f 0a 20 20 50  ge handle */.  P
34d0: 67 6e 6f 20 70 67 6e 6f 3b 20 20 20 20 20 20 20  gno pgno;       
34e0: 20 20 20 20 2f 2a 20 50 61 67 65 20 6e 75 6d 62      /* Page numb
34f0: 65 72 20 66 6f 72 20 74 68 69 73 20 70 61 67 65  er for this page
3500: 20 2a 2f 0a 20 20 4d 65 6d 50 61 67 65 20 2a 70   */.  MemPage *p
3510: 50 61 72 65 6e 74 3b 20 20 20 20 2f 2a 20 54 68  Parent;    /* Th
3520: 65 20 70 61 72 65 6e 74 20 6f 66 20 74 68 69 73  e parent of this
3530: 20 70 61 67 65 2e 20 20 4e 55 4c 4c 20 66 6f 72   page.  NULL for
3540: 20 72 6f 6f 74 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a   root */.};../*.
3550: 2a 2a 20 54 68 65 20 69 6e 2d 6d 65 6d 6f 72 79  ** The in-memory
3560: 20 69 6d 61 67 65 20 6f 66 20 61 20 64 69 73 6b   image of a disk
3570: 20 70 61 67 65 20 68 61 73 20 74 68 65 20 61 75   page has the au
3580: 78 69 6c 69 61 72 79 20 69 6e 66 6f 72 6d 61 74  xiliary informat
3590: 69 6f 6e 20 61 70 70 65 6e 64 65 64 0a 2a 2a 20  ion appended.** 
35a0: 74 6f 20 74 68 65 20 65 6e 64 2e 20 20 45 58 54  to the end.  EXT
35b0: 52 41 5f 53 49 5a 45 20 69 73 20 74 68 65 20 6e  RA_SIZE is the n
35c0: 75 6d 62 65 72 20 6f 66 20 62 79 74 65 73 20 6f  umber of bytes o
35d0: 66 20 73 70 61 63 65 20 6e 65 65 64 65 64 20 74  f space needed t
35e0: 6f 20 68 6f 6c 64 0a 2a 2a 20 74 68 61 74 20 65  o hold.** that e
35f0: 78 74 72 61 20 69 6e 66 6f 72 6d 61 74 69 6f 6e  xtra information
3600: 2e 0a 2a 2f 0a 23 64 65 66 69 6e 65 20 45 58 54  ..*/.#define EXT
3610: 52 41 5f 53 49 5a 45 20 73 69 7a 65 6f 66 28 4d  RA_SIZE sizeof(M
3620: 65 6d 50 61 67 65 29 0a 0a 2f 2a 20 41 20 42 74  emPage)../* A Bt
3630: 72 65 65 20 68 61 6e 64 6c 65 0a 2a 2a 0a 2a 2a  ree handle.**.**
3640: 20 41 20 64 61 74 61 62 61 73 65 20 63 6f 6e 6e   A database conn
3650: 65 63 74 69 6f 6e 20 63 6f 6e 74 61 69 6e 73 20  ection contains 
3660: 61 20 70 6f 69 6e 74 65 72 20 74 6f 20 61 6e 20  a pointer to an 
3670: 69 6e 73 74 61 6e 63 65 20 6f 66 0a 2a 2a 20 74  instance of.** t
3680: 68 69 73 20 6f 62 6a 65 63 74 20 66 6f 72 20 65  his object for e
3690: 76 65 72 79 20 64 61 74 61 62 61 73 65 20 66 69  very database fi
36a0: 6c 65 20 74 68 61 74 20 69 74 20 68 61 73 20 6f  le that it has o
36b0: 70 65 6e 2e 20 20 54 68 69 73 20 73 74 72 75 63  pen.  This struc
36c0: 74 75 72 65 0a 2a 2a 20 69 73 20 6f 70 61 71 75  ture.** is opaqu
36d0: 65 20 74 6f 20 74 68 65 20 64 61 74 61 62 61 73  e to the databas
36e0: 65 20 63 6f 6e 6e 65 63 74 69 6f 6e 2e 20 20 54  e connection.  T
36f0: 68 65 20 64 61 74 61 62 61 73 65 20 63 6f 6e 6e  he database conn
3700: 65 63 74 69 6f 6e 20 63 61 6e 6e 6f 74 0a 2a 2a  ection cannot.**
3710: 20 73 65 65 20 74 68 65 20 69 6e 74 65 72 6e 61   see the interna
3720: 6c 73 20 6f 66 20 74 68 69 73 20 73 74 72 75 63  ls of this struc
3730: 74 75 72 65 20 61 6e 64 20 6f 6e 6c 79 20 64 65  ture and only de
3740: 61 6c 73 20 77 69 74 68 20 70 6f 69 6e 74 65 72  als with pointer
3750: 73 20 74 6f 0a 2a 2a 20 74 68 69 73 20 73 74 72  s to.** this str
3760: 75 63 74 75 72 65 2e 0a 2a 2a 0a 2a 2a 20 46 6f  ucture..**.** Fo
3770: 72 20 73 6f 6d 65 20 64 61 74 61 62 61 73 65 20  r some database 
3780: 66 69 6c 65 73 2c 20 74 68 65 20 73 61 6d 65 20  files, the same 
3790: 75 6e 64 65 72 6c 79 69 6e 67 20 64 61 74 61 62  underlying datab
37a0: 61 73 65 20 63 61 63 68 65 20 6d 69 67 68 74 20  ase cache might 
37b0: 62 65 20 0a 2a 2a 20 73 68 61 72 65 64 20 62 65  be .** shared be
37c0: 74 77 65 65 6e 20 6d 75 6c 74 69 70 6c 65 20 63  tween multiple c
37d0: 6f 6e 6e 65 63 74 69 6f 6e 73 2e 20 20 49 6e 20  onnections.  In 
37e0: 74 68 61 74 20 63 61 73 65 2c 20 65 61 63 68 20  that case, each 
37f0: 63 6f 6e 74 65 63 74 69 6f 6e 0a 2a 2a 20 68 61  contection.** ha
3800: 73 20 69 74 20 6f 77 6e 20 70 6f 69 6e 74 65 72  s it own pointer
3810: 20 74 6f 20 74 68 69 73 20 6f 62 6a 65 63 74 2e   to this object.
3820: 20 20 42 75 74 20 65 61 63 68 20 69 6e 73 74 61    But each insta
3830: 6e 63 65 20 6f 66 20 74 68 69 73 20 6f 62 6a 65  nce of this obje
3840: 63 74 0a 2a 2a 20 70 6f 69 6e 74 73 20 74 6f 20  ct.** points to 
3850: 74 68 65 20 73 61 6d 65 20 42 74 53 68 61 72 65  the same BtShare
3860: 64 20 6f 62 6a 65 63 74 2e 20 20 54 68 65 20 64  d object.  The d
3870: 61 74 61 62 61 73 65 20 63 61 63 68 65 20 61 6e  atabase cache an
3880: 64 20 74 68 65 0a 2a 2a 20 73 63 68 65 6d 61 20  d the.** schema 
3890: 61 73 73 6f 63 69 61 74 65 64 20 77 69 74 68 20  associated with 
38a0: 74 68 65 20 64 61 74 61 62 61 73 65 20 66 69 6c  the database fil
38b0: 65 20 61 72 65 20 61 6c 6c 20 63 6f 6e 74 61 69  e are all contai
38c0: 6e 65 64 20 77 69 74 68 69 6e 0a 2a 2a 20 74 68  ned within.** th
38d0: 65 20 42 74 53 68 61 72 65 64 20 6f 62 6a 65 63  e BtShared objec
38e0: 74 2e 0a 2a 2a 0a 2a 2a 20 41 6c 6c 20 66 69 65  t..**.** All fie
38f0: 6c 64 73 20 69 6e 20 74 68 69 73 20 73 74 72 75  lds in this stru
3900: 63 74 75 72 65 20 61 72 65 20 61 63 63 65 73 73  cture are access
3910: 65 64 20 75 6e 64 65 72 20 73 71 6c 69 74 65 33  ed under sqlite3
3920: 2e 6d 75 74 65 78 2e 0a 2a 2a 20 54 68 65 20 70  .mutex..** The p
3930: 42 74 20 70 6f 69 6e 74 65 72 20 69 74 73 65 6c  Bt pointer itsel
3940: 66 20 6d 61 79 20 6e 6f 74 20 62 65 20 63 68 61  f may not be cha
3950: 6e 67 65 64 20 77 68 69 6c 65 20 74 68 65 72 65  nged while there
3960: 20 65 78 69 73 74 73 20 63 75 72 73 6f 72 73 20   exists cursors 
3970: 0a 2a 2a 20 69 6e 20 74 68 65 20 72 65 66 65 72  .** in the refer
3980: 65 6e 63 65 64 20 42 74 53 68 61 72 65 64 20 74  enced BtShared t
3990: 68 61 74 20 70 6f 69 6e 74 20 62 61 63 6b 20 74  hat point back t
39a0: 6f 20 74 68 69 73 20 42 74 72 65 65 20 73 69 6e  o this Btree sin
39b0: 63 65 20 74 68 6f 73 65 0a 2a 2a 20 63 75 72 73  ce those.** curs
39c0: 6f 72 73 20 68 61 76 65 20 74 6f 20 64 6f 20 67  ors have to do g
39d0: 6f 20 74 68 72 6f 75 67 68 20 74 68 69 73 20 42  o through this B
39e0: 74 72 65 65 20 74 6f 20 66 69 6e 64 20 74 68 65  tree to find the
39f0: 69 72 20 42 74 53 68 61 72 65 64 20 61 6e 64 0a  ir BtShared and.
3a00: 2a 2a 20 74 68 65 79 20 6f 66 74 65 6e 20 64 6f  ** they often do
3a10: 20 73 6f 20 77 69 74 68 6f 75 74 20 68 6f 6c 64   so without hold
3a20: 69 6e 67 20 73 71 6c 69 74 65 33 2e 6d 75 74 65  ing sqlite3.mute
3a30: 78 2e 0a 2a 2f 0a 73 74 72 75 63 74 20 42 74 72  x..*/.struct Btr
3a40: 65 65 20 7b 0a 20 20 73 71 6c 69 74 65 33 20 2a  ee {.  sqlite3 *
3a50: 64 62 3b 20 20 20 20 20 20 20 2f 2a 20 54 68 65  db;       /* The
3a60: 20 64 61 74 61 62 61 73 65 20 63 6f 6e 6e 65 63   database connec
3a70: 74 69 6f 6e 20 68 6f 6c 64 69 6e 67 20 74 68 69  tion holding thi
3a80: 73 20 62 74 72 65 65 20 2a 2f 0a 20 20 42 74 53  s btree */.  BtS
3a90: 68 61 72 65 64 20 2a 70 42 74 3b 20 20 20 20 20  hared *pBt;     
3aa0: 2f 2a 20 53 68 61 72 61 62 6c 65 20 63 6f 6e 74  /* Sharable cont
3ab0: 65 6e 74 20 6f 66 20 74 68 69 73 20 62 74 72 65  ent of this btre
3ac0: 65 20 2a 2f 0a 20 20 75 38 20 69 6e 54 72 61 6e  e */.  u8 inTran
3ad0: 73 3b 20 20 20 20 20 20 20 20 2f 2a 20 54 52 41  s;        /* TRA
3ae0: 4e 53 5f 4e 4f 4e 45 2c 20 54 52 41 4e 53 5f 52  NS_NONE, TRANS_R
3af0: 45 41 44 20 6f 72 20 54 52 41 4e 53 5f 57 52 49  EAD or TRANS_WRI
3b00: 54 45 20 2a 2f 0a 20 20 75 38 20 73 68 61 72 61  TE */.  u8 shara
3b10: 62 6c 65 3b 20 20 20 20 20 20 20 2f 2a 20 54 72  ble;       /* Tr
3b20: 75 65 20 69 66 20 77 65 20 63 61 6e 20 73 68 61  ue if we can sha
3b30: 72 65 20 70 42 74 20 77 69 74 68 20 61 6e 6f 74  re pBt with anot
3b40: 68 65 72 20 64 62 20 2a 2f 0a 20 20 75 38 20 6c  her db */.  u8 l
3b50: 6f 63 6b 65 64 3b 20 20 20 20 20 20 20 20 20 2f  ocked;         /
3b60: 2a 20 54 72 75 65 20 69 66 20 64 62 20 63 75 72  * True if db cur
3b70: 72 65 6e 74 6c 79 20 68 61 73 20 70 42 74 20 6c  rently has pBt l
3b80: 6f 63 6b 65 64 20 2a 2f 0a 20 20 69 6e 74 20 77  ocked */.  int w
3b90: 61 6e 74 54 6f 4c 6f 63 6b 3b 20 20 20 20 2f 2a  antToLock;    /*
3ba0: 20 4e 75 6d 62 65 72 20 6f 66 20 6e 65 73 74 65   Number of neste
3bb0: 64 20 63 61 6c 6c 73 20 74 6f 20 73 71 6c 69 74  d calls to sqlit
3bc0: 65 33 42 74 72 65 65 45 6e 74 65 72 28 29 20 2a  e3BtreeEnter() *
3bd0: 2f 0a 20 20 42 74 72 65 65 20 2a 70 4e 65 78 74  /.  Btree *pNext
3be0: 3b 20 20 20 20 20 20 2f 2a 20 4c 69 73 74 20 6f  ;      /* List o
3bf0: 66 20 6f 74 68 65 72 20 73 68 61 72 61 62 6c 65  f other sharable
3c00: 20 42 74 72 65 65 73 20 66 72 6f 6d 20 74 68 65   Btrees from the
3c10: 20 73 61 6d 65 20 64 62 20 2a 2f 0a 20 20 42 74   same db */.  Bt
3c20: 72 65 65 20 2a 70 50 72 65 76 3b 20 20 20 20 20  ree *pPrev;     
3c30: 20 2f 2a 20 42 61 63 6b 20 70 6f 69 6e 74 65 72   /* Back pointer
3c40: 20 6f 66 20 74 68 65 20 73 61 6d 65 20 6c 69 73   of the same lis
3c50: 74 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 42  t */.};../*.** B
3c60: 74 72 65 65 2e 69 6e 54 72 61 6e 73 20 6d 61 79  tree.inTrans may
3c70: 20 74 61 6b 65 20 6f 6e 65 20 6f 66 20 74 68 65   take one of the
3c80: 20 66 6f 6c 6c 6f 77 69 6e 67 20 76 61 6c 75 65   following value
3c90: 73 2e 0a 2a 2a 0a 2a 2a 20 49 66 20 74 68 65 20  s..**.** If the 
3ca0: 73 68 61 72 65 64 2d 64 61 74 61 20 65 78 74 65  shared-data exte
3cb0: 6e 73 69 6f 6e 20 69 73 20 65 6e 61 62 6c 65 64  nsion is enabled
3cc0: 2c 20 74 68 65 72 65 20 6d 61 79 20 62 65 20 6d  , there may be m
3cd0: 75 6c 74 69 70 6c 65 20 75 73 65 72 73 0a 2a 2a  ultiple users.**
3ce0: 20 6f 66 20 74 68 65 20 42 74 72 65 65 20 73 74   of the Btree st
3cf0: 72 75 63 74 75 72 65 2e 20 41 74 20 6d 6f 73 74  ructure. At most
3d00: 20 6f 6e 65 20 6f 66 20 74 68 65 73 65 20 6d 61   one of these ma
3d10: 79 20 6f 70 65 6e 20 61 20 77 72 69 74 65 20 74  y open a write t
3d20: 72 61 6e 73 61 63 74 69 6f 6e 2c 0a 2a 2a 20 62  ransaction,.** b
3d30: 75 74 20 61 6e 79 20 6e 75 6d 62 65 72 20 6d 61  ut any number ma
3d40: 79 20 68 61 76 65 20 61 63 74 69 76 65 20 72 65  y have active re
3d50: 61 64 20 74 72 61 6e 73 61 63 74 69 6f 6e 73 2e  ad transactions.
3d60: 0a 2a 2f 0a 23 64 65 66 69 6e 65 20 54 52 41 4e  .*/.#define TRAN
3d70: 53 5f 4e 4f 4e 45 20 20 30 0a 23 64 65 66 69 6e  S_NONE  0.#defin
3d80: 65 20 54 52 41 4e 53 5f 52 45 41 44 20 20 31 0a  e TRANS_READ  1.
3d90: 23 64 65 66 69 6e 65 20 54 52 41 4e 53 5f 57 52  #define TRANS_WR
3da0: 49 54 45 20 32 0a 0a 2f 2a 0a 2a 2a 20 41 6e 20  ITE 2../*.** An 
3db0: 69 6e 73 74 61 6e 63 65 20 6f 66 20 74 68 69 73  instance of this
3dc0: 20 6f 62 6a 65 63 74 20 72 65 70 72 65 73 65 6e   object represen
3dd0: 74 73 20 61 20 73 69 6e 67 6c 65 20 64 61 74 61  ts a single data
3de0: 62 61 73 65 20 66 69 6c 65 2e 0a 2a 2a 20 0a 2a  base file..** .*
3df0: 2a 20 41 20 73 69 6e 67 6c 65 20 64 61 74 61 62  * A single datab
3e00: 61 73 65 20 66 69 6c 65 20 63 61 6e 20 62 65 20  ase file can be 
3e10: 69 6e 20 75 73 65 20 61 73 20 74 68 65 20 73 61  in use as the sa
3e20: 6d 65 20 74 69 6d 65 20 62 79 20 74 77 6f 0a 2a  me time by two.*
3e30: 2a 20 6f 72 20 6d 6f 72 65 20 64 61 74 61 62 61  * or more databa
3e40: 73 65 20 63 6f 6e 6e 65 63 74 69 6f 6e 73 2e 20  se connections. 
3e50: 20 57 68 65 6e 20 74 77 6f 20 6f 72 20 6d 6f 72   When two or mor
3e60: 65 20 63 6f 6e 6e 65 63 74 69 6f 6e 73 20 61 72  e connections ar
3e70: 65 0a 2a 2a 20 73 68 61 72 69 6e 67 20 74 68 65  e.** sharing the
3e80: 20 73 61 6d 65 20 64 61 74 61 62 61 73 65 20 66   same database f
3e90: 69 6c 65 2c 20 65 61 63 68 20 63 6f 6e 6e 65 63  ile, each connec
3ea0: 74 69 6f 6e 20 68 61 73 20 69 74 20 6f 77 6e 0a  tion has it own.
3eb0: 2a 2a 20 70 72 69 76 61 74 65 20 42 74 72 65 65  ** private Btree
3ec0: 20 6f 62 6a 65 63 74 20 66 6f 72 20 74 68 65 20   object for the 
3ed0: 66 69 6c 65 20 61 6e 64 20 65 61 63 68 20 6f 66  file and each of
3ee0: 20 74 68 6f 73 65 20 42 74 72 65 65 73 20 70 6f   those Btrees po
3ef0: 69 6e 74 73 0a 2a 2a 20 74 6f 20 74 68 69 73 20  ints.** to this 
3f00: 6f 6e 65 20 42 74 53 68 61 72 65 64 20 6f 62 6a  one BtShared obj
3f10: 65 63 74 2e 20 20 42 74 53 68 61 72 65 64 2e 6e  ect.  BtShared.n
3f20: 52 65 66 20 69 73 20 74 68 65 20 6e 75 6d 62 65  Ref is the numbe
3f30: 72 20 6f 66 0a 2a 2a 20 63 6f 6e 6e 65 63 74 69  r of.** connecti
3f40: 6f 6e 73 20 63 75 72 72 65 6e 74 6c 79 20 73 68  ons currently sh
3f50: 61 72 69 6e 67 20 74 68 69 73 20 64 61 74 61 62  aring this datab
3f60: 61 73 65 20 66 69 6c 65 2e 0a 2a 2a 0a 2a 2a 20  ase file..**.** 
3f70: 46 69 65 6c 64 73 20 69 6e 20 74 68 69 73 20 73  Fields in this s
3f80: 74 72 75 63 74 75 72 65 20 61 72 65 20 61 63 63  tructure are acc
3f90: 65 73 73 65 64 20 75 6e 64 65 72 20 74 68 65 20  essed under the 
3fa0: 42 74 53 68 61 72 65 64 2e 6d 75 74 65 78 0a 2a  BtShared.mutex.*
3fb0: 2a 20 6d 75 74 65 78 2c 20 65 78 63 65 70 74 20  * mutex, except 
3fc0: 66 6f 72 20 6e 52 65 66 20 61 6e 64 20 70 4e 65  for nRef and pNe
3fd0: 78 74 20 77 68 69 63 68 20 61 72 65 20 61 63 63  xt which are acc
3fe0: 65 73 73 65 64 20 75 6e 64 65 72 20 74 68 65 0a  essed under the.
3ff0: 2a 2a 20 67 6c 6f 62 61 6c 20 53 51 4c 49 54 45  ** global SQLITE
4000: 5f 4d 55 54 45 58 5f 53 54 41 54 49 43 5f 4d 41  _MUTEX_STATIC_MA
4010: 53 54 45 52 20 6d 75 74 65 78 2e 20 20 54 68 65  STER mutex.  The
4020: 20 70 50 61 67 65 72 20 66 69 65 6c 64 0a 2a 2a   pPager field.**
4030: 20 6d 61 79 20 6e 6f 74 20 62 65 20 6d 6f 64 69   may not be modi
4040: 66 69 65 64 20 6f 6e 63 65 20 69 74 20 69 73 20  fied once it is 
4050: 69 6e 69 74 69 61 6c 6c 79 20 73 65 74 20 61 73  initially set as
4060: 20 6c 6f 6e 67 20 61 73 20 6e 52 65 66 3e 30 2e   long as nRef>0.
4070: 0a 2a 2a 20 54 68 65 20 70 53 63 68 65 6d 61 20  .** The pSchema 
4080: 66 69 65 6c 64 20 6d 61 79 20 62 65 20 73 65 74  field may be set
4090: 20 6f 6e 63 65 20 75 6e 64 65 72 20 42 74 53 68   once under BtSh
40a0: 61 72 65 64 2e 6d 75 74 65 78 20 61 6e 64 0a 2a  ared.mutex and.*
40b0: 2a 20 74 68 65 72 65 61 66 74 65 72 20 69 73 20  * thereafter is 
40c0: 75 6e 63 68 61 6e 67 65 64 20 61 73 20 6c 6f 6e  unchanged as lon
40d0: 67 20 61 73 20 6e 52 65 66 3e 30 2e 0a 2a 2f 0a  g as nRef>0..*/.
40e0: 73 74 72 75 63 74 20 42 74 53 68 61 72 65 64 20  struct BtShared 
40f0: 7b 0a 20 20 50 61 67 65 72 20 2a 70 50 61 67 65  {.  Pager *pPage
4100: 72 3b 20 20 20 20 20 20 20 20 2f 2a 20 54 68 65  r;        /* The
4110: 20 70 61 67 65 20 63 61 63 68 65 20 2a 2f 0a 20   page cache */. 
4120: 20 73 71 6c 69 74 65 33 20 2a 64 62 3b 20 20 20   sqlite3 *db;   
4130: 20 20 20 20 20 20 20 2f 2a 20 44 61 74 61 62 61         /* Databa
4140: 73 65 20 63 6f 6e 6e 65 63 74 69 6f 6e 20 63 75  se connection cu
4150: 72 72 65 6e 74 6c 79 20 75 73 69 6e 67 20 74 68  rrently using th
4160: 69 73 20 42 74 72 65 65 20 2a 2f 0a 20 20 42 74  is Btree */.  Bt
4170: 43 75 72 73 6f 72 20 2a 70 43 75 72 73 6f 72 3b  Cursor *pCursor;
4180: 20 20 20 20 2f 2a 20 41 20 6c 69 73 74 20 6f 66      /* A list of
4190: 20 61 6c 6c 20 6f 70 65 6e 20 63 75 72 73 6f 72   all open cursor
41a0: 73 20 2a 2f 0a 20 20 4d 65 6d 50 61 67 65 20 2a  s */.  MemPage *
41b0: 70 50 61 67 65 31 3b 20 20 20 20 20 20 2f 2a 20  pPage1;      /* 
41c0: 46 69 72 73 74 20 70 61 67 65 20 6f 66 20 74 68  First page of th
41d0: 65 20 64 61 74 61 62 61 73 65 20 2a 2f 0a 20 20  e database */.  
41e0: 75 38 20 69 6e 53 74 6d 74 3b 20 20 20 20 20 20  u8 inStmt;      
41f0: 20 20 20 20 20 20 2f 2a 20 54 72 75 65 20 69 66        /* True if
4200: 20 77 65 20 61 72 65 20 69 6e 20 61 20 73 74 61   we are in a sta
4210: 74 65 6d 65 6e 74 20 73 75 62 74 72 61 6e 73 61  tement subtransa
4220: 63 74 69 6f 6e 20 2a 2f 0a 20 20 75 38 20 72 65  ction */.  u8 re
4230: 61 64 4f 6e 6c 79 3b 20 20 20 20 20 20 20 20 20  adOnly;         
4240: 20 2f 2a 20 54 72 75 65 20 69 66 20 74 68 65 20   /* True if the 
4250: 75 6e 64 65 72 6c 79 69 6e 67 20 66 69 6c 65 20  underlying file 
4260: 69 73 20 72 65 61 64 6f 6e 6c 79 20 2a 2f 0a 20  is readonly */. 
4270: 20 75 38 20 70 61 67 65 53 69 7a 65 46 69 78 65   u8 pageSizeFixe
4280: 64 3b 20 20 20 20 20 2f 2a 20 54 72 75 65 20 69  d;     /* True i
4290: 66 20 74 68 65 20 70 61 67 65 20 73 69 7a 65 20  f the page size 
42a0: 63 61 6e 20 6e 6f 20 6c 6f 6e 67 65 72 20 62 65  can no longer be
42b0: 20 63 68 61 6e 67 65 64 20 2a 2f 0a 23 69 66 6e   changed */.#ifn
42c0: 64 65 66 20 53 51 4c 49 54 45 5f 4f 4d 49 54 5f  def SQLITE_OMIT_
42d0: 41 55 54 4f 56 41 43 55 55 4d 0a 20 20 75 38 20  AUTOVACUUM.  u8 
42e0: 61 75 74 6f 56 61 63 75 75 6d 3b 20 20 20 20 20  autoVacuum;     
42f0: 20 20 20 2f 2a 20 54 72 75 65 20 69 66 20 61 75     /* True if au
4300: 74 6f 2d 76 61 63 75 75 6d 20 69 73 20 65 6e 61  to-vacuum is ena
4310: 62 6c 65 64 20 2a 2f 0a 20 20 75 38 20 69 6e 63  bled */.  u8 inc
4320: 72 56 61 63 75 75 6d 3b 20 20 20 20 20 20 20 20  rVacuum;        
4330: 2f 2a 20 54 72 75 65 20 69 66 20 69 6e 63 72 2d  /* True if incr-
4340: 76 61 63 75 75 6d 20 69 73 20 65 6e 61 62 6c 65  vacuum is enable
4350: 64 20 2a 2f 0a 20 20 50 67 6e 6f 20 6e 54 72 75  d */.  Pgno nTru
4360: 6e 63 3b 20 20 20 20 20 20 20 20 20 20 2f 2a 20  nc;          /* 
4370: 4e 6f 6e 2d 7a 65 72 6f 20 69 66 20 74 68 65 20  Non-zero if the 
4380: 64 62 20 77 69 6c 6c 20 62 65 20 74 72 75 6e 63  db will be trunc
4390: 61 74 65 64 20 28 69 6e 63 72 20 76 61 63 75 75  ated (incr vacuu
43a0: 6d 29 20 2a 2f 0a 23 65 6e 64 69 66 0a 20 20 75  m) */.#endif.  u
43b0: 31 36 20 70 61 67 65 53 69 7a 65 3b 20 20 20 20  16 pageSize;    
43c0: 20 20 20 20 20 2f 2a 20 54 6f 74 61 6c 20 6e 75       /* Total nu
43d0: 6d 62 65 72 20 6f 66 20 62 79 74 65 73 20 6f 6e  mber of bytes on
43e0: 20 61 20 70 61 67 65 20 2a 2f 0a 20 20 75 31 36   a page */.  u16
43f0: 20 75 73 61 62 6c 65 53 69 7a 65 3b 20 20 20 20   usableSize;    
4400: 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20     /* Number of 
4410: 75 73 61 62 6c 65 20 62 79 74 65 73 20 6f 6e 20  usable bytes on 
4420: 65 61 63 68 20 70 61 67 65 20 2a 2f 0a 20 20 69  each page */.  i
4430: 6e 74 20 6d 61 78 4c 6f 63 61 6c 3b 20 20 20 20  nt maxLocal;    
4440: 20 20 20 20 20 2f 2a 20 4d 61 78 69 6d 75 6d 20       /* Maximum 
4450: 6c 6f 63 61 6c 20 70 61 79 6c 6f 61 64 20 69 6e  local payload in
4460: 20 6e 6f 6e 2d 4c 45 41 46 44 41 54 41 20 74 61   non-LEAFDATA ta
4470: 62 6c 65 73 20 2a 2f 0a 20 20 69 6e 74 20 6d 69  bles */.  int mi
4480: 6e 4c 6f 63 61 6c 3b 20 20 20 20 20 20 20 20 20  nLocal;         
4490: 2f 2a 20 4d 69 6e 69 6d 75 6d 20 6c 6f 63 61 6c  /* Minimum local
44a0: 20 70 61 79 6c 6f 61 64 20 69 6e 20 6e 6f 6e 2d   payload in non-
44b0: 4c 45 41 46 44 41 54 41 20 74 61 62 6c 65 73 20  LEAFDATA tables 
44c0: 2a 2f 0a 20 20 69 6e 74 20 6d 61 78 4c 65 61 66  */.  int maxLeaf
44d0: 3b 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4d 61  ;          /* Ma
44e0: 78 69 6d 75 6d 20 6c 6f 63 61 6c 20 70 61 79 6c  ximum local payl
44f0: 6f 61 64 20 69 6e 20 61 20 4c 45 41 46 44 41 54  oad in a LEAFDAT
4500: 41 20 74 61 62 6c 65 20 2a 2f 0a 20 20 69 6e 74  A table */.  int
4510: 20 6d 69 6e 4c 65 61 66 3b 20 20 20 20 20 20 20   minLeaf;       
4520: 20 20 20 2f 2a 20 4d 69 6e 69 6d 75 6d 20 6c 6f     /* Minimum lo
4530: 63 61 6c 20 70 61 79 6c 6f 61 64 20 69 6e 20 61  cal payload in a
4540: 20 4c 45 41 46 44 41 54 41 20 74 61 62 6c 65 20   LEAFDATA table 
4550: 2a 2f 0a 20 20 75 38 20 69 6e 54 72 61 6e 73 61  */.  u8 inTransa
4560: 63 74 69 6f 6e 3b 20 20 20 20 20 2f 2a 20 54 72  ction;     /* Tr
4570: 61 6e 73 61 63 74 69 6f 6e 20 73 74 61 74 65 20  ansaction state 
4580: 2a 2f 0a 20 20 69 6e 74 20 6e 54 72 61 6e 73 61  */.  int nTransa
4590: 63 74 69 6f 6e 3b 20 20 20 20 20 2f 2a 20 4e 75  ction;     /* Nu
45a0: 6d 62 65 72 20 6f 66 20 6f 70 65 6e 20 74 72 61  mber of open tra
45b0: 6e 73 61 63 74 69 6f 6e 73 20 28 72 65 61 64 20  nsactions (read 
45c0: 2b 20 77 72 69 74 65 29 20 2a 2f 0a 20 20 76 6f  + write) */.  vo
45d0: 69 64 20 2a 70 53 63 68 65 6d 61 3b 20 20 20 20  id *pSchema;    
45e0: 20 20 20 20 2f 2a 20 50 6f 69 6e 74 65 72 20 74      /* Pointer t
45f0: 6f 20 73 70 61 63 65 20 61 6c 6c 6f 63 61 74 65  o space allocate
4600: 64 20 62 79 20 73 71 6c 69 74 65 33 42 74 72 65  d by sqlite3Btre
4610: 65 53 63 68 65 6d 61 28 29 20 2a 2f 0a 20 20 76  eSchema() */.  v
4620: 6f 69 64 20 28 2a 78 46 72 65 65 53 63 68 65 6d  oid (*xFreeSchem
4630: 61 29 28 76 6f 69 64 2a 29 3b 20 20 2f 2a 20 44  a)(void*);  /* D
4640: 65 73 74 72 75 63 74 6f 72 20 66 6f 72 20 42 74  estructor for Bt
4650: 53 68 61 72 65 64 2e 70 53 63 68 65 6d 61 20 2a  Shared.pSchema *
4660: 2f 0a 20 20 73 71 6c 69 74 65 33 5f 6d 75 74 65  /.  sqlite3_mute
4670: 78 20 2a 6d 75 74 65 78 3b 20 2f 2a 20 4e 6f 6e  x *mutex; /* Non
4680: 2d 72 65 63 75 72 73 69 76 65 20 6d 75 74 65 78  -recursive mutex
4690: 20 72 65 71 75 69 72 65 64 20 74 6f 20 61 63 63   required to acc
46a0: 65 73 73 20 74 68 69 73 20 73 74 72 75 63 74 20  ess this struct 
46b0: 2a 2f 0a 20 20 42 75 73 79 48 61 6e 64 6c 65 72  */.  BusyHandler
46c0: 20 62 75 73 79 48 64 72 3b 20 20 2f 2a 20 54 68   busyHdr;  /* Th
46d0: 65 20 62 75 73 79 20 68 61 6e 64 6c 65 72 20 66  e busy handler f
46e0: 6f 72 20 74 68 69 73 20 62 74 72 65 65 20 2a 2f  or this btree */
46f0: 0a 23 69 66 6e 64 65 66 20 53 51 4c 49 54 45 5f  .#ifndef SQLITE_
4700: 4f 4d 49 54 5f 53 48 41 52 45 44 5f 43 41 43 48  OMIT_SHARED_CACH
4710: 45 0a 20 20 69 6e 74 20 6e 52 65 66 3b 20 20 20  E.  int nRef;   
4720: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d            /* Num
4730: 62 65 72 20 6f 66 20 72 65 66 65 72 65 6e 63 65  ber of reference
4740: 73 20 74 6f 20 74 68 69 73 20 73 74 72 75 63 74  s to this struct
4750: 75 72 65 20 2a 2f 0a 20 20 42 74 53 68 61 72 65  ure */.  BtShare
4760: 64 20 2a 70 4e 65 78 74 3b 20 20 20 20 20 20 2f  d *pNext;      /
4770: 2a 20 4e 65 78 74 20 6f 6e 20 61 20 6c 69 73 74  * Next on a list
4780: 20 6f 66 20 73 68 61 72 61 62 6c 65 20 42 74 53   of sharable BtS
4790: 68 61 72 65 64 20 73 74 72 75 63 74 73 20 2a 2f  hared structs */
47a0: 0a 20 20 42 74 4c 6f 63 6b 20 2a 70 4c 6f 63 6b  .  BtLock *pLock
47b0: 3b 20 20 20 20 20 20 20 20 2f 2a 20 4c 69 73 74  ;        /* List
47c0: 20 6f 66 20 6c 6f 63 6b 73 20 68 65 6c 64 20 6f   of locks held o
47d0: 6e 20 74 68 69 73 20 73 68 61 72 65 64 2d 62 74  n this shared-bt
47e0: 72 65 65 20 73 74 72 75 63 74 20 2a 2f 0a 20 20  ree struct */.  
47f0: 42 74 72 65 65 20 2a 70 45 78 63 6c 75 73 69 76  Btree *pExclusiv
4800: 65 3b 20 20 20 20 2f 2a 20 42 74 72 65 65 20 77  e;    /* Btree w
4810: 69 74 68 20 61 6e 20 45 58 43 4c 55 53 49 56 45  ith an EXCLUSIVE
4820: 20 6c 6f 63 6b 20 6f 6e 20 74 68 65 20 77 68 6f   lock on the who
4830: 6c 65 20 64 62 20 2a 2f 0a 23 65 6e 64 69 66 0a  le db */.#endif.
4840: 20 20 75 38 20 2a 70 54 6d 70 53 70 61 63 65 3b    u8 *pTmpSpace;
4850: 20 20 20 20 20 20 20 20 2f 2a 20 42 74 53 68 61          /* BtSha
4860: 72 65 64 2e 70 61 67 65 53 69 7a 65 20 62 79 74  red.pageSize byt
4870: 65 73 20 6f 66 20 73 70 61 63 65 20 66 6f 72 20  es of space for 
4880: 74 6d 70 20 75 73 65 20 2a 2f 0a 7d 3b 0a 0a 2f  tmp use */.};../
4890: 2a 0a 2a 2a 20 41 6e 20 69 6e 73 74 61 6e 63 65  *.** An instance
48a0: 20 6f 66 20 74 68 65 20 66 6f 6c 6c 6f 77 69 6e   of the followin
48b0: 67 20 73 74 72 75 63 74 75 72 65 20 69 73 20 75  g structure is u
48c0: 73 65 64 20 74 6f 20 68 6f 6c 64 20 69 6e 66 6f  sed to hold info
48d0: 72 6d 61 74 69 6f 6e 0a 2a 2a 20 61 62 6f 75 74  rmation.** about
48e0: 20 61 20 63 65 6c 6c 2e 20 20 54 68 65 20 70 61   a cell.  The pa
48f0: 72 73 65 43 65 6c 6c 50 74 72 28 29 20 66 75 6e  rseCellPtr() fun
4900: 63 74 69 6f 6e 20 66 69 6c 6c 73 20 69 6e 20 74  ction fills in t
4910: 68 69 73 20 73 74 72 75 63 74 75 72 65 0a 2a 2a  his structure.**
4920: 20 62 61 73 65 64 20 6f 6e 20 69 6e 66 6f 72 6d   based on inform
4930: 61 74 69 6f 6e 20 65 78 74 72 61 63 74 20 66 72  ation extract fr
4940: 6f 6d 20 74 68 65 20 72 61 77 20 64 69 73 6b 20  om the raw disk 
4950: 70 61 67 65 2e 0a 2a 2f 0a 74 79 70 65 64 65 66  page..*/.typedef
4960: 20 73 74 72 75 63 74 20 43 65 6c 6c 49 6e 66 6f   struct CellInfo
4970: 20 43 65 6c 6c 49 6e 66 6f 3b 0a 73 74 72 75 63   CellInfo;.struc
4980: 74 20 43 65 6c 6c 49 6e 66 6f 20 7b 0a 20 20 75  t CellInfo {.  u
4990: 38 20 2a 70 43 65 6c 6c 3b 20 20 20 20 20 2f 2a  8 *pCell;     /*
49a0: 20 50 6f 69 6e 74 65 72 20 74 6f 20 74 68 65 20   Pointer to the 
49b0: 73 74 61 72 74 20 6f 66 20 63 65 6c 6c 20 63 6f  start of cell co
49c0: 6e 74 65 6e 74 20 2a 2f 0a 20 20 69 36 34 20 6e  ntent */.  i64 n
49d0: 4b 65 79 3b 20 20 20 20 20 20 2f 2a 20 54 68 65  Key;      /* The
49e0: 20 6b 65 79 20 66 6f 72 20 49 4e 54 4b 45 59 20   key for INTKEY 
49f0: 74 61 62 6c 65 73 2c 20 6f 72 20 6e 75 6d 62 65  tables, or numbe
4a00: 72 20 6f 66 20 62 79 74 65 73 20 69 6e 20 6b 65  r of bytes in ke
4a10: 79 20 2a 2f 0a 20 20 75 33 32 20 6e 44 61 74 61  y */.  u32 nData
4a20: 3b 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20  ;     /* Number 
4a30: 6f 66 20 62 79 74 65 73 20 6f 66 20 64 61 74 61  of bytes of data
4a40: 20 2a 2f 0a 20 20 75 33 32 20 6e 50 61 79 6c 6f   */.  u32 nPaylo
4a50: 61 64 3b 20 20 2f 2a 20 54 6f 74 61 6c 20 61 6d  ad;  /* Total am
4a60: 6f 75 6e 74 20 6f 66 20 70 61 79 6c 6f 61 64 20  ount of payload 
4a70: 2a 2f 0a 20 20 75 31 36 20 6e 48 65 61 64 65 72  */.  u16 nHeader
4a80: 3b 20 20 20 2f 2a 20 53 69 7a 65 20 6f 66 20 74  ;   /* Size of t
4a90: 68 65 20 63 65 6c 6c 20 63 6f 6e 74 65 6e 74 20  he cell content 
4aa0: 68 65 61 64 65 72 20 69 6e 20 62 79 74 65 73 20  header in bytes 
4ab0: 2a 2f 0a 20 20 75 31 36 20 6e 4c 6f 63 61 6c 3b  */.  u16 nLocal;
4ac0: 20 20 20 20 2f 2a 20 41 6d 6f 75 6e 74 20 6f 66      /* Amount of
4ad0: 20 70 61 79 6c 6f 61 64 20 68 65 6c 64 20 6c 6f   payload held lo
4ae0: 63 61 6c 6c 79 20 2a 2f 0a 20 20 75 31 36 20 69  cally */.  u16 i
4af0: 4f 76 65 72 66 6c 6f 77 3b 20 2f 2a 20 4f 66 66  Overflow; /* Off
4b00: 73 65 74 20 74 6f 20 6f 76 65 72 66 6c 6f 77 20  set to overflow 
4b10: 70 61 67 65 20 6e 75 6d 62 65 72 2e 20 20 5a 65  page number.  Ze
4b20: 72 6f 20 69 66 20 6e 6f 20 6f 76 65 72 66 6c 6f  ro if no overflo
4b30: 77 20 2a 2f 0a 20 20 75 31 36 20 6e 53 69 7a 65  w */.  u16 nSize
4b40: 3b 20 20 20 20 20 2f 2a 20 53 69 7a 65 20 6f 66  ;     /* Size of
4b50: 20 74 68 65 20 63 65 6c 6c 20 63 6f 6e 74 65 6e   the cell conten
4b60: 74 20 6f 6e 20 74 68 65 20 6d 61 69 6e 20 62 2d  t on the main b-
4b70: 74 72 65 65 20 70 61 67 65 20 2a 2f 0a 7d 3b 0a  tree page */.};.
4b80: 0a 2f 2a 0a 2a 2a 20 41 20 63 75 72 73 6f 72 20  ./*.** A cursor 
4b90: 69 73 20 61 20 70 6f 69 6e 74 65 72 20 74 6f 20  is a pointer to 
4ba0: 61 20 70 61 72 74 69 63 75 6c 61 72 20 65 6e 74  a particular ent
4bb0: 72 79 20 77 69 74 68 69 6e 20 61 20 70 61 72 74  ry within a part
4bc0: 69 63 75 6c 61 72 0a 2a 2a 20 62 2d 74 72 65 65  icular.** b-tree
4bd0: 20 77 69 74 68 69 6e 20 61 20 64 61 74 61 62 61   within a databa
4be0: 73 65 20 66 69 6c 65 2e 0a 2a 2a 0a 2a 2a 20 54  se file..**.** T
4bf0: 68 65 20 65 6e 74 72 79 20 69 73 20 69 64 65 6e  he entry is iden
4c00: 74 69 66 69 65 64 20 62 79 20 69 74 73 20 4d 65  tified by its Me
4c10: 6d 50 61 67 65 20 61 6e 64 20 74 68 65 20 69 6e  mPage and the in
4c20: 64 65 78 20 69 6e 0a 2a 2a 20 4d 65 6d 50 61 67  dex in.** MemPag
4c30: 65 2e 61 43 65 6c 6c 5b 5d 20 6f 66 20 74 68 65  e.aCell[] of the
4c40: 20 65 6e 74 72 79 2e 0a 2a 2a 0a 2a 2a 20 57 68   entry..**.** Wh
4c50: 65 6e 20 61 20 73 69 6e 67 6c 65 20 64 61 74 61  en a single data
4c60: 62 61 73 65 20 66 69 6c 65 20 63 61 6e 20 73 68  base file can sh
4c70: 61 72 65 64 20 62 79 20 74 77 6f 20 6d 6f 72 65  ared by two more
4c80: 20 64 61 74 61 62 61 73 65 20 63 6f 6e 6e 65 63   database connec
4c90: 74 69 6f 6e 73 2c 0a 2a 2a 20 62 75 74 20 63 75  tions,.** but cu
4ca0: 72 73 6f 72 73 20 63 61 6e 6e 6f 74 20 62 65 20  rsors cannot be 
4cb0: 73 68 61 72 65 64 2e 20 20 45 61 63 68 20 63 75  shared.  Each cu
4cc0: 72 73 6f 72 20 69 73 20 61 73 73 6f 63 69 61 74  rsor is associat
4cd0: 65 64 20 77 69 74 68 20 61 0a 2a 2a 20 70 61 72  ed with a.** par
4ce0: 74 69 63 75 6c 61 72 20 64 61 74 61 62 61 73 65  ticular database
4cf0: 20 63 6f 6e 6e 65 63 74 69 6f 6e 20 69 64 65 6e   connection iden
4d00: 74 69 66 69 65 64 20 42 74 43 75 72 73 6f 72 2e  tified BtCursor.
4d10: 70 42 74 72 65 65 2e 64 62 2e 0a 2a 2a 0a 2a 2a  pBtree.db..**.**
4d20: 20 46 69 65 6c 64 73 20 69 6e 20 74 68 69 73 20   Fields in this 
4d30: 73 74 72 75 63 74 75 72 65 20 61 72 65 20 61 63  structure are ac
4d40: 63 65 73 73 65 64 20 75 6e 64 65 72 20 74 68 65  cessed under the
4d50: 20 42 74 53 68 61 72 65 64 2e 6d 75 74 65 78 0a   BtShared.mutex.
4d60: 2a 2a 20 66 6f 75 6e 64 20 61 74 20 73 65 6c 66  ** found at self
4d70: 2d 3e 70 42 74 2d 3e 6d 75 74 65 78 2e 20 0a 2a  ->pBt->mutex. .*
4d80: 2f 0a 73 74 72 75 63 74 20 42 74 43 75 72 73 6f  /.struct BtCurso
4d90: 72 20 7b 0a 20 20 42 74 72 65 65 20 2a 70 42 74  r {.  Btree *pBt
4da0: 72 65 65 3b 20 20 20 20 20 20 20 20 20 20 20 20  ree;            
4db0: 2f 2a 20 54 68 65 20 42 74 72 65 65 20 74 6f 20  /* The Btree to 
4dc0: 77 68 69 63 68 20 74 68 69 73 20 63 75 72 73 6f  which this curso
4dd0: 72 20 62 65 6c 6f 6e 67 73 20 2a 2f 0a 20 20 42  r belongs */.  B
4de0: 74 53 68 61 72 65 64 20 2a 70 42 74 3b 20 20 20  tShared *pBt;   
4df0: 20 20 20 20 20 20 20 20 20 2f 2a 20 54 68 65 20           /* The 
4e00: 42 74 53 68 61 72 65 64 20 74 68 69 73 20 63 75  BtShared this cu
4e10: 72 73 6f 72 20 70 6f 69 6e 74 73 20 74 6f 20 2a  rsor points to *
4e20: 2f 0a 20 20 42 74 43 75 72 73 6f 72 20 2a 70 4e  /.  BtCursor *pN
4e30: 65 78 74 2c 20 2a 70 50 72 65 76 3b 20 20 2f 2a  ext, *pPrev;  /*
4e40: 20 46 6f 72 6d 73 20 61 20 6c 69 6e 6b 65 64 20   Forms a linked 
4e50: 6c 69 73 74 20 6f 66 20 61 6c 6c 20 63 75 72 73  list of all curs
4e60: 6f 72 73 20 2a 2f 0a 20 20 73 74 72 75 63 74 20  ors */.  struct 
4e70: 4b 65 79 49 6e 66 6f 20 2a 70 4b 65 79 49 6e 66  KeyInfo *pKeyInf
4e80: 6f 3b 20 2f 2a 20 41 72 67 75 6d 65 6e 74 20 70  o; /* Argument p
4e90: 61 73 73 65 64 20 74 6f 20 63 6f 6d 70 61 72 69  assed to compari
4ea0: 73 6f 6e 20 66 75 6e 63 74 69 6f 6e 20 2a 2f 0a  son function */.
4eb0: 20 20 50 67 6e 6f 20 70 67 6e 6f 52 6f 6f 74 3b    Pgno pgnoRoot;
4ec0: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 54              /* T
4ed0: 68 65 20 72 6f 6f 74 20 70 61 67 65 20 6f 66 20  he root page of 
4ee0: 74 68 69 73 20 74 72 65 65 20 2a 2f 0a 20 20 4d  this tree */.  M
4ef0: 65 6d 50 61 67 65 20 2a 70 50 61 67 65 3b 20 20  emPage *pPage;  
4f00: 20 20 20 20 20 20 20 20 20 2f 2a 20 50 61 67 65           /* Page
4f10: 20 74 68 61 74 20 63 6f 6e 74 61 69 6e 73 20 74   that contains t
4f20: 68 65 20 65 6e 74 72 79 20 2a 2f 0a 20 20 69 6e  he entry */.  in
4f30: 74 20 69 64 78 3b 20 20 20 20 20 20 20 20 20 20  t idx;          
4f40: 20 20 20 20 20 20 20 20 2f 2a 20 49 6e 64 65 78          /* Index
4f50: 20 6f 66 20 74 68 65 20 65 6e 74 72 79 20 69 6e   of the entry in
4f60: 20 70 50 61 67 65 2d 3e 61 43 65 6c 6c 5b 5d 20   pPage->aCell[] 
4f70: 2a 2f 0a 20 20 43 65 6c 6c 49 6e 66 6f 20 69 6e  */.  CellInfo in
4f80: 66 6f 3b 20 20 20 20 20 20 20 20 20 20 20 20 2f  fo;            /
4f90: 2a 20 41 20 70 61 72 73 65 20 6f 66 20 74 68 65  * A parse of the
4fa0: 20 63 65 6c 6c 20 77 65 20 61 72 65 20 70 6f 69   cell we are poi
4fb0: 6e 74 69 6e 67 20 61 74 20 2a 2f 0a 20 20 75 38  nting at */.  u8
4fc0: 20 77 72 46 6c 61 67 3b 20 20 20 20 20 20 20 20   wrFlag;        
4fd0: 20 20 20 20 20 20 20 20 2f 2a 20 54 72 75 65 20          /* True 
4fe0: 69 66 20 77 72 69 74 61 62 6c 65 20 2a 2f 0a 20  if writable */. 
4ff0: 20 75 38 20 61 74 4c 61 73 74 3b 20 20 20 20 20   u8 atLast;     
5000: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 43 75             /* Cu
5010: 72 73 6f 72 20 70 6f 69 6e 74 69 6e 67 20 74 6f  rsor pointing to
5020: 20 74 68 65 20 6c 61 73 74 20 65 6e 74 72 79 20   the last entry 
5030: 2a 2f 0a 20 20 75 38 20 76 61 6c 69 64 4e 4b 65  */.  u8 validNKe
5040: 79 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 2f  y;             /
5050: 2a 20 54 72 75 65 20 69 66 20 69 6e 66 6f 2e 6e  * True if info.n
5060: 4b 65 79 20 69 73 20 76 61 6c 69 64 20 2a 2f 0a  Key is valid */.
5070: 20 20 75 38 20 65 53 74 61 74 65 3b 20 20 20 20    u8 eState;    
5080: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4f              /* O
5090: 6e 65 20 6f 66 20 74 68 65 20 43 55 52 53 4f 52  ne of the CURSOR
50a0: 5f 58 58 58 20 63 6f 6e 73 74 61 6e 74 73 20 28  _XXX constants (
50b0: 73 65 65 20 62 65 6c 6f 77 29 20 2a 2f 0a 20 20  see below) */.  
50c0: 76 6f 69 64 20 2a 70 4b 65 79 3b 20 20 20 20 20  void *pKey;     
50d0: 20 2f 2a 20 53 61 76 65 64 20 6b 65 79 20 74 68   /* Saved key th
50e0: 61 74 20 77 61 73 20 63 75 72 73 6f 72 27 73 20  at was cursor's 
50f0: 6c 61 73 74 20 6b 6e 6f 77 6e 20 70 6f 73 69 74  last known posit
5100: 69 6f 6e 20 2a 2f 0a 20 20 69 36 34 20 6e 4b 65  ion */.  i64 nKe
5110: 79 3b 20 20 20 20 20 20 20 20 2f 2a 20 53 69 7a  y;        /* Siz
5120: 65 20 6f 66 20 70 4b 65 79 2c 20 6f 72 20 6c 61  e of pKey, or la
5130: 73 74 20 69 6e 74 65 67 65 72 20 6b 65 79 20 2a  st integer key *
5140: 2f 0a 20 20 69 6e 74 20 73 6b 69 70 3b 20 20 20  /.  int skip;   
5150: 20 20 20 20 20 2f 2a 20 28 73 6b 69 70 3c 30 29       /* (skip<0)
5160: 20 2d 3e 20 50 72 65 76 28 29 20 69 73 20 61 20   -> Prev() is a 
5170: 6e 6f 2d 6f 70 2e 20 28 73 6b 69 70 3e 30 29 20  no-op. (skip>0) 
5180: 2d 3e 20 4e 65 78 74 28 29 20 69 73 20 2a 2f 0a  -> Next() is */.
5190: 23 69 66 6e 64 65 66 20 53 51 4c 49 54 45 5f 4f  #ifndef SQLITE_O
51a0: 4d 49 54 5f 49 4e 43 52 42 4c 4f 42 0a 20 20 75  MIT_INCRBLOB.  u
51b0: 38 20 69 73 49 6e 63 72 62 6c 6f 62 48 61 6e 64  8 isIncrblobHand
51c0: 6c 65 3b 20 20 20 20 20 20 2f 2a 20 54 72 75 65  le;      /* True
51d0: 20 69 66 20 74 68 69 73 20 63 75 72 73 6f 72 20   if this cursor 
51e0: 69 73 20 61 6e 20 69 6e 63 72 2e 20 69 6f 20 68  is an incr. io h
51f0: 61 6e 64 6c 65 20 2a 2f 0a 20 20 50 67 6e 6f 20  andle */.  Pgno 
5200: 2a 61 4f 76 65 72 66 6c 6f 77 3b 20 20 20 20 20  *aOverflow;     
5210: 20 20 20 20 20 2f 2a 20 43 61 63 68 65 20 6f 66       /* Cache of
5220: 20 6f 76 65 72 66 6c 6f 77 20 70 61 67 65 20 6c   overflow page l
5230: 6f 63 61 74 69 6f 6e 73 20 2a 2f 0a 23 65 6e 64  ocations */.#end
5240: 69 66 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 50 6f 74  if.};../*.** Pot
5250: 65 6e 74 69 61 6c 20 76 61 6c 75 65 73 20 66 6f  ential values fo
5260: 72 20 42 74 43 75 72 73 6f 72 2e 65 53 74 61 74  r BtCursor.eStat
5270: 65 2e 0a 2a 2a 0a 2a 2a 20 43 55 52 53 4f 52 5f  e..**.** CURSOR_
5280: 56 41 4c 49 44 3a 0a 2a 2a 20 20 20 43 75 72 73  VALID:.**   Curs
5290: 6f 72 20 70 6f 69 6e 74 73 20 74 6f 20 61 20 76  or points to a v
52a0: 61 6c 69 64 20 65 6e 74 72 79 2e 20 67 65 74 50  alid entry. getP
52b0: 61 79 6c 6f 61 64 28 29 20 65 74 63 2e 20 6d 61  ayload() etc. ma
52c0: 79 20 62 65 20 63 61 6c 6c 65 64 2e 0a 2a 2a 0a  y be called..**.
52d0: 2a 2a 20 43 55 52 53 4f 52 5f 49 4e 56 41 4c 49  ** CURSOR_INVALI
52e0: 44 3a 0a 2a 2a 20 20 20 43 75 72 73 6f 72 20 64  D:.**   Cursor d
52f0: 6f 65 73 20 6e 6f 74 20 70 6f 69 6e 74 20 74 6f  oes not point to
5300: 20 61 20 76 61 6c 69 64 20 65 6e 74 72 79 2e 20   a valid entry. 
5310: 54 68 69 73 20 63 61 6e 20 68 61 70 70 65 6e 20  This can happen 
5320: 28 66 6f 72 20 65 78 61 6d 70 6c 65 29 20 0a 2a  (for example) .*
5330: 2a 20 20 20 62 65 63 61 75 73 65 20 74 68 65 20  *   because the 
5340: 74 61 62 6c 65 20 69 73 20 65 6d 70 74 79 20 6f  table is empty o
5350: 72 20 62 65 63 61 75 73 65 20 42 74 72 65 65 43  r because BtreeC
5360: 75 72 73 6f 72 46 69 72 73 74 28 29 20 68 61 73  ursorFirst() has
5370: 20 6e 6f 74 20 62 65 65 6e 0a 2a 2a 20 20 20 63   not been.**   c
5380: 61 6c 6c 65 64 2e 0a 2a 2a 0a 2a 2a 20 43 55 52  alled..**.** CUR
5390: 53 4f 52 5f 52 45 51 55 49 52 45 53 45 45 4b 3a  SOR_REQUIRESEEK:
53a0: 0a 2a 2a 20 20 20 54 68 65 20 74 61 62 6c 65 20  .**   The table 
53b0: 74 68 61 74 20 74 68 69 73 20 63 75 72 73 6f 72  that this cursor
53c0: 20 77 61 73 20 6f 70 65 6e 65 64 20 6f 6e 20 73   was opened on s
53d0: 74 69 6c 6c 20 65 78 69 73 74 73 2c 20 62 75 74  till exists, but
53e0: 20 68 61 73 20 62 65 65 6e 20 0a 2a 2a 20 20 20   has been .**   
53f0: 6d 6f 64 69 66 69 65 64 20 73 69 6e 63 65 20 74  modified since t
5400: 68 65 20 63 75 72 73 6f 72 20 77 61 73 20 6c 61  he cursor was la
5410: 73 74 20 75 73 65 64 2e 20 54 68 65 20 63 75 72  st used. The cur
5420: 73 6f 72 20 70 6f 73 69 74 69 6f 6e 20 69 73 20  sor position is 
5430: 73 61 76 65 64 0a 2a 2a 20 20 20 69 6e 20 76 61  saved.**   in va
5440: 72 69 61 62 6c 65 73 20 42 74 43 75 72 73 6f 72  riables BtCursor
5450: 2e 70 4b 65 79 20 61 6e 64 20 42 74 43 75 72 73  .pKey and BtCurs
5460: 6f 72 2e 6e 4b 65 79 2e 20 57 68 65 6e 20 61 20  or.nKey. When a 
5470: 63 75 72 73 6f 72 20 69 73 20 69 6e 20 0a 2a 2a  cursor is in .**
5480: 20 20 20 74 68 69 73 20 73 74 61 74 65 2c 20 72     this state, r
5490: 65 73 74 6f 72 65 43 75 72 73 6f 72 50 6f 73 69  estoreCursorPosi
54a0: 74 69 6f 6e 28 29 20 63 61 6e 20 62 65 20 63 61  tion() can be ca
54b0: 6c 6c 65 64 20 74 6f 20 61 74 74 65 6d 70 74 20  lled to attempt 
54c0: 74 6f 0a 2a 2a 20 20 20 73 65 65 6b 20 74 68 65  to.**   seek the
54d0: 20 63 75 72 73 6f 72 20 74 6f 20 74 68 65 20 73   cursor to the s
54e0: 61 76 65 64 20 70 6f 73 69 74 69 6f 6e 2e 0a 2a  aved position..*
54f0: 2a 0a 2a 2a 20 43 55 52 53 4f 52 5f 46 41 55 4c  *.** CURSOR_FAUL
5500: 54 3a 0a 2a 2a 20 20 20 41 20 75 6e 72 65 63 6f  T:.**   A unreco
5510: 76 65 72 61 62 6c 65 20 65 72 72 6f 72 20 28 61  verable error (a
5520: 6e 20 49 2f 4f 20 65 72 72 6f 72 20 6f 72 20 61  n I/O error or a
5530: 20 6d 61 6c 6c 6f 63 20 66 61 69 6c 75 72 65 29   malloc failure)
5540: 20 68 61 73 20 6f 63 63 75 72 72 65 64 0a 2a 2a   has occurred.**
5550: 20 20 20 6f 6e 20 61 20 64 69 66 66 65 72 65 6e     on a differen
5560: 74 20 63 6f 6e 6e 65 63 74 69 6f 6e 20 74 68 61  t connection tha
5570: 74 20 73 68 61 72 65 73 20 74 68 65 20 42 74 53  t shares the BtS
5580: 68 61 72 65 64 20 63 61 63 68 65 20 77 69 74 68  hared cache with
5590: 20 74 68 69 73 0a 2a 2a 20 20 20 63 75 72 73 6f   this.**   curso
55a0: 72 2e 20 20 54 68 65 20 65 72 72 6f 72 20 68 61  r.  The error ha
55b0: 73 20 6c 65 66 74 20 74 68 65 20 63 61 63 68 65  s left the cache
55c0: 20 69 6e 20 61 6e 20 69 6e 63 6f 6e 73 69 73 74   in an inconsist
55d0: 65 6e 74 20 73 74 61 74 65 2e 0a 2a 2a 20 20 20  ent state..**   
55e0: 44 6f 20 6e 6f 74 68 69 6e 67 20 65 6c 73 65 20  Do nothing else 
55f0: 77 69 74 68 20 74 68 69 73 20 63 75 72 73 6f 72  with this cursor
5600: 2e 20 20 41 6e 79 20 61 74 74 65 6d 70 74 20 74  .  Any attempt t
5610: 6f 20 75 73 65 20 74 68 65 20 63 75 72 73 6f 72  o use the cursor
5620: 0a 2a 2a 20 20 20 73 68 6f 75 6c 64 20 72 65 74  .**   should ret
5630: 75 72 6e 20 74 68 65 20 65 72 72 6f 72 20 63 6f  urn the error co
5640: 64 65 20 73 74 6f 72 65 64 20 69 6e 20 42 74 43  de stored in BtC
5650: 75 72 73 6f 72 2e 73 6b 69 70 0a 2a 2f 0a 23 64  ursor.skip.*/.#d
5660: 65 66 69 6e 65 20 43 55 52 53 4f 52 5f 49 4e 56  efine CURSOR_INV
5670: 41 4c 49 44 20 20 20 20 20 20 20 20 20 20 20 30  ALID           0
5680: 0a 23 64 65 66 69 6e 65 20 43 55 52 53 4f 52 5f  .#define CURSOR_
5690: 56 41 4c 49 44 20 20 20 20 20 20 20 20 20 20 20  VALID           
56a0: 20 20 31 0a 23 64 65 66 69 6e 65 20 43 55 52 53    1.#define CURS
56b0: 4f 52 5f 52 45 51 55 49 52 45 53 45 45 4b 20 20  OR_REQUIRESEEK  
56c0: 20 20 20 20 20 32 0a 23 64 65 66 69 6e 65 20 43       2.#define C
56d0: 55 52 53 4f 52 5f 46 41 55 4c 54 20 20 20 20 20  URSOR_FAULT     
56e0: 20 20 20 20 20 20 20 20 33 0a 0a 2f 2a 20 54 68          3../* Th
56f0: 65 20 64 61 74 61 62 61 73 65 20 70 61 67 65 20  e database page 
5700: 74 68 65 20 50 45 4e 44 49 4e 47 5f 42 59 54 45  the PENDING_BYTE
5710: 20 6f 63 63 75 70 69 65 73 2e 20 54 68 69 73 20   occupies. This 
5720: 70 61 67 65 20 69 73 20 6e 65 76 65 72 20 75 73  page is never us
5730: 65 64 2e 0a 2a 2a 20 54 4f 44 4f 3a 20 54 68 69  ed..** TODO: Thi
5740: 73 20 6d 61 63 72 6f 20 69 73 20 76 65 72 79 20  s macro is very 
5750: 73 69 6d 69 6c 61 72 79 20 74 6f 20 50 41 47 45  similary to PAGE
5760: 52 5f 4d 4a 5f 50 47 4e 4f 28 29 20 69 6e 20 70  R_MJ_PGNO() in p
5770: 61 67 65 72 2e 63 2e 20 54 68 65 79 0a 2a 2a 20  ager.c. They.** 
5780: 73 68 6f 75 6c 64 20 70 6f 73 73 69 62 6c 79 20  should possibly 
5790: 62 65 20 63 6f 6e 73 6f 6c 69 64 61 74 65 64 20  be consolidated 
57a0: 28 70 72 65 73 75 6d 61 62 6c 79 20 69 6e 20 70  (presumably in p
57b0: 61 67 65 72 2e 68 29 2e 0a 2a 2a 0a 2a 2a 20 49  ager.h)..**.** I
57c0: 66 20 64 69 73 6b 20 49 2f 4f 20 69 73 20 6f 6d  f disk I/O is om
57d0: 69 74 74 65 64 20 28 6d 65 61 6e 69 6e 67 20 74  itted (meaning t
57e0: 68 61 74 20 74 68 65 20 64 61 74 61 62 61 73 65  hat the database
57f0: 20 69 73 20 73 74 6f 72 65 64 20 70 75 72 65 6c   is stored purel
5800: 79 0a 2a 2a 20 69 6e 20 6d 65 6d 6f 72 79 29 20  y.** in memory) 
5810: 74 68 65 6e 20 74 68 65 72 65 20 69 73 20 6e 6f  then there is no
5820: 20 70 65 6e 64 69 6e 67 20 62 79 74 65 2e 0a 2a   pending byte..*
5830: 2f 0a 23 69 66 64 65 66 20 53 51 4c 49 54 45 5f  /.#ifdef SQLITE_
5840: 4f 4d 49 54 5f 44 49 53 4b 49 4f 0a 23 20 64 65  OMIT_DISKIO.# de
5850: 66 69 6e 65 20 50 45 4e 44 49 4e 47 5f 42 59 54  fine PENDING_BYT
5860: 45 5f 50 41 47 45 28 70 42 74 29 20 20 30 78 37  E_PAGE(pBt)  0x7
5870: 66 66 66 66 66 66 66 0a 23 65 6c 73 65 0a 23 20  fffffff.#else.# 
5880: 64 65 66 69 6e 65 20 50 45 4e 44 49 4e 47 5f 42  define PENDING_B
5890: 59 54 45 5f 50 41 47 45 28 70 42 74 29 20 28 28  YTE_PAGE(pBt) ((
58a0: 50 45 4e 44 49 4e 47 5f 42 59 54 45 2f 28 70 42  PENDING_BYTE/(pB
58b0: 74 29 2d 3e 70 61 67 65 53 69 7a 65 29 2b 31 29  t)->pageSize)+1)
58c0: 0a 23 65 6e 64 69 66 0a 0a 2f 2a 0a 2a 2a 20 41  .#endif../*.** A
58d0: 20 6c 69 6e 6b 65 64 20 6c 69 73 74 20 6f 66 20   linked list of 
58e0: 74 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 20 73 74  the following st
58f0: 72 75 63 74 75 72 65 73 20 69 73 20 73 74 6f 72  ructures is stor
5900: 65 64 20 61 74 20 42 74 53 68 61 72 65 64 2e 70  ed at BtShared.p
5910: 4c 6f 63 6b 2e 0a 2a 2a 20 4c 6f 63 6b 73 20 61  Lock..** Locks a
5920: 72 65 20 61 64 64 65 64 20 28 6f 72 20 75 70 67  re added (or upg
5930: 72 61 64 65 64 20 66 72 6f 6d 20 52 45 41 44 5f  raded from READ_
5940: 4c 4f 43 4b 20 74 6f 20 57 52 49 54 45 5f 4c 4f  LOCK to WRITE_LO
5950: 43 4b 29 20 77 68 65 6e 20 61 20 63 75 72 73 6f  CK) when a curso
5960: 72 20 0a 2a 2a 20 69 73 20 6f 70 65 6e 65 64 20  r .** is opened 
5970: 6f 6e 20 74 68 65 20 74 61 62 6c 65 20 77 69 74  on the table wit
5980: 68 20 72 6f 6f 74 20 70 61 67 65 20 42 74 53 68  h root page BtSh
5990: 61 72 65 64 2e 69 54 61 62 6c 65 2e 20 4c 6f 63  ared.iTable. Loc
59a0: 6b 73 20 61 72 65 20 72 65 6d 6f 76 65 64 0a 2a  ks are removed.*
59b0: 2a 20 66 72 6f 6d 20 74 68 69 73 20 6c 69 73 74  * from this list
59c0: 20 77 68 65 6e 20 61 20 74 72 61 6e 73 61 63 74   when a transact
59d0: 69 6f 6e 20 69 73 20 63 6f 6d 6d 69 74 74 65 64  ion is committed
59e0: 20 6f 72 20 72 6f 6c 6c 65 64 20 62 61 63 6b 2c   or rolled back,
59f0: 20 6f 72 20 77 68 65 6e 0a 2a 2a 20 61 20 62 74   or when.** a bt
5a00: 72 65 65 20 68 61 6e 64 6c 65 20 69 73 20 63 6c  ree handle is cl
5a10: 6f 73 65 64 2e 0a 2a 2f 0a 73 74 72 75 63 74 20  osed..*/.struct 
5a20: 42 74 4c 6f 63 6b 20 7b 0a 20 20 42 74 72 65 65  BtLock {.  Btree
5a30: 20 2a 70 42 74 72 65 65 3b 20 20 20 20 20 20 20   *pBtree;       
5a40: 20 2f 2a 20 42 74 72 65 65 20 68 61 6e 64 6c 65   /* Btree handle
5a50: 20 68 6f 6c 64 69 6e 67 20 74 68 69 73 20 6c 6f   holding this lo
5a60: 63 6b 20 2a 2f 0a 20 20 50 67 6e 6f 20 69 54 61  ck */.  Pgno iTa
5a70: 62 6c 65 3b 20 20 20 20 20 20 20 20 20 20 2f 2a  ble;          /*
5a80: 20 52 6f 6f 74 20 70 61 67 65 20 6f 66 20 74 61   Root page of ta
5a90: 62 6c 65 20 2a 2f 0a 20 20 75 38 20 65 4c 6f 63  ble */.  u8 eLoc
5aa0: 6b 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 2f  k;             /
5ab0: 2a 20 52 45 41 44 5f 4c 4f 43 4b 20 6f 72 20 57  * READ_LOCK or W
5ac0: 52 49 54 45 5f 4c 4f 43 4b 20 2a 2f 0a 20 20 42  RITE_LOCK */.  B
5ad0: 74 4c 6f 63 6b 20 2a 70 4e 65 78 74 3b 20 20 20  tLock *pNext;   
5ae0: 20 20 20 20 20 2f 2a 20 4e 65 78 74 20 69 6e 20       /* Next in 
5af0: 42 74 53 68 61 72 65 64 2e 70 4c 6f 63 6b 20 6c  BtShared.pLock l
5b00: 69 73 74 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 20 43 61  ist */.};../* Ca
5b10: 6e 64 69 64 61 74 65 20 76 61 6c 75 65 73 20 66  ndidate values f
5b20: 6f 72 20 42 74 4c 6f 63 6b 2e 65 4c 6f 63 6b 20  or BtLock.eLock 
5b30: 2a 2f 0a 23 64 65 66 69 6e 65 20 52 45 41 44 5f  */.#define READ_
5b40: 4c 4f 43 4b 20 20 20 20 20 31 0a 23 64 65 66 69  LOCK     1.#defi
5b50: 6e 65 20 57 52 49 54 45 5f 4c 4f 43 4b 20 20 20  ne WRITE_LOCK   
5b60: 20 32 0a 0a 2f 2a 0a 2a 2a 20 54 68 65 73 65 20   2../*.** These 
5b70: 6d 61 63 72 6f 73 20 64 65 66 69 6e 65 20 74 68  macros define th
5b80: 65 20 6c 6f 63 61 74 69 6f 6e 20 6f 66 20 74 68  e location of th
5b90: 65 20 70 6f 69 6e 74 65 72 2d 6d 61 70 20 65 6e  e pointer-map en
5ba0: 74 72 79 20 66 6f 72 20 61 20 0a 2a 2a 20 64 61  try for a .** da
5bb0: 74 61 62 61 73 65 20 70 61 67 65 2e 20 54 68 65  tabase page. The
5bc0: 20 66 69 72 73 74 20 61 72 67 75 6d 65 6e 74 20   first argument 
5bd0: 74 6f 20 65 61 63 68 20 69 73 20 74 68 65 20 6e  to each is the n
5be0: 75 6d 62 65 72 20 6f 66 20 75 73 61 62 6c 65 0a  umber of usable.
5bf0: 2a 2a 20 62 79 74 65 73 20 6f 6e 20 65 61 63 68  ** bytes on each
5c00: 20 70 61 67 65 20 6f 66 20 74 68 65 20 64 61 74   page of the dat
5c10: 61 62 61 73 65 20 28 6f 66 74 65 6e 20 31 30 32  abase (often 102
5c20: 34 29 2e 20 54 68 65 20 73 65 63 6f 6e 64 20 69  4). The second i
5c30: 73 20 74 68 65 0a 2a 2a 20 70 61 67 65 20 6e 75  s the.** page nu
5c40: 6d 62 65 72 20 74 6f 20 6c 6f 6f 6b 20 75 70 20  mber to look up 
5c50: 69 6e 20 74 68 65 20 70 6f 69 6e 74 65 72 20 6d  in the pointer m
5c60: 61 70 2e 0a 2a 2a 0a 2a 2a 20 50 54 52 4d 41 50  ap..**.** PTRMAP
5c70: 5f 50 41 47 45 4e 4f 20 72 65 74 75 72 6e 73 20  _PAGENO returns 
5c80: 74 68 65 20 64 61 74 61 62 61 73 65 20 70 61 67  the database pag
5c90: 65 20 6e 75 6d 62 65 72 20 6f 66 20 74 68 65 20  e number of the 
5ca0: 70 6f 69 6e 74 65 72 2d 6d 61 70 0a 2a 2a 20 70  pointer-map.** p
5cb0: 61 67 65 20 74 68 61 74 20 73 74 6f 72 65 73 20  age that stores 
5cc0: 74 68 65 20 72 65 71 75 69 72 65 64 20 70 6f 69  the required poi
5cd0: 6e 74 65 72 2e 20 50 54 52 4d 41 50 5f 50 54 52  nter. PTRMAP_PTR
5ce0: 4f 46 46 53 45 54 20 72 65 74 75 72 6e 73 0a 2a  OFFSET returns.*
5cf0: 2a 20 74 68 65 20 6f 66 66 73 65 74 20 6f 66 20  * the offset of 
5d00: 74 68 65 20 72 65 71 75 65 73 74 65 64 20 6d 61  the requested ma
5d10: 70 20 65 6e 74 72 79 2e 0a 2a 2a 0a 2a 2a 20 49  p entry..**.** I
5d20: 66 20 74 68 65 20 70 67 6e 6f 20 61 72 67 75 6d  f the pgno argum
5d30: 65 6e 74 20 70 61 73 73 65 64 20 74 6f 20 50 54  ent passed to PT
5d40: 52 4d 41 50 5f 50 41 47 45 4e 4f 20 69 73 20 61  RMAP_PAGENO is a
5d50: 20 70 6f 69 6e 74 65 72 2d 6d 61 70 20 70 61 67   pointer-map pag
5d60: 65 2c 0a 2a 2a 20 74 68 65 6e 20 70 67 6e 6f 20  e,.** then pgno 
5d70: 69 73 20 72 65 74 75 72 6e 65 64 2e 20 53 6f 20  is returned. So 
5d80: 28 70 67 6e 6f 3d 3d 50 54 52 4d 41 50 5f 50 41  (pgno==PTRMAP_PA
5d90: 47 45 4e 4f 28 70 67 73 7a 2c 20 70 67 6e 6f 29  GENO(pgsz, pgno)
5da0: 29 20 63 61 6e 20 62 65 0a 2a 2a 20 75 73 65 64  ) can be.** used
5db0: 20 74 6f 20 74 65 73 74 20 69 66 20 70 67 6e 6f   to test if pgno
5dc0: 20 69 73 20 61 20 70 6f 69 6e 74 65 72 2d 6d 61   is a pointer-ma
5dd0: 70 20 70 61 67 65 2e 20 50 54 52 4d 41 50 5f 49  p page. PTRMAP_I
5de0: 53 50 41 47 45 20 69 6d 70 6c 65 6d 65 6e 74 73  SPAGE implements
5df0: 0a 2a 2a 20 74 68 69 73 20 74 65 73 74 2e 0a 2a  .** this test..*
5e00: 2f 0a 23 64 65 66 69 6e 65 20 50 54 52 4d 41 50  /.#define PTRMAP
5e10: 5f 50 41 47 45 4e 4f 28 70 42 74 2c 20 70 67 6e  _PAGENO(pBt, pgn
5e20: 6f 29 20 70 74 72 6d 61 70 50 61 67 65 6e 6f 28  o) ptrmapPageno(
5e30: 70 42 74 2c 20 70 67 6e 6f 29 0a 23 64 65 66 69  pBt, pgno).#defi
5e40: 6e 65 20 50 54 52 4d 41 50 5f 50 54 52 4f 46 46  ne PTRMAP_PTROFF
5e50: 53 45 54 28 70 67 70 74 72 6d 61 70 2c 20 70 67  SET(pgptrmap, pg
5e60: 6e 6f 29 20 28 35 2a 28 70 67 6e 6f 2d 70 67 70  no) (5*(pgno-pgp
5e70: 74 72 6d 61 70 2d 31 29 29 0a 23 64 65 66 69 6e  trmap-1)).#defin
5e80: 65 20 50 54 52 4d 41 50 5f 49 53 50 41 47 45 28  e PTRMAP_ISPAGE(
5e90: 70 42 74 2c 20 70 67 6e 6f 29 20 28 50 54 52 4d  pBt, pgno) (PTRM
5ea0: 41 50 5f 50 41 47 45 4e 4f 28 28 70 42 74 29 2c  AP_PAGENO((pBt),
5eb0: 28 70 67 6e 6f 29 29 3d 3d 28 70 67 6e 6f 29 29  (pgno))==(pgno))
5ec0: 0a 0a 2f 2a 0a 2a 2a 20 54 68 65 20 70 6f 69 6e  ../*.** The poin
5ed0: 74 65 72 20 6d 61 70 20 69 73 20 61 20 6c 6f 6f  ter map is a loo
5ee0: 6b 75 70 20 74 61 62 6c 65 20 74 68 61 74 20 69  kup table that i
5ef0: 64 65 6e 74 69 66 69 65 73 20 74 68 65 20 70 61  dentifies the pa
5f00: 72 65 6e 74 20 70 61 67 65 20 66 6f 72 0a 2a 2a  rent page for.**
5f10: 20 65 61 63 68 20 63 68 69 6c 64 20 70 61 67 65   each child page
5f20: 20 69 6e 20 74 68 65 20 64 61 74 61 62 61 73 65   in the database
5f30: 20 66 69 6c 65 2e 20 20 54 68 65 20 70 61 72 65   file.  The pare
5f40: 6e 74 20 70 61 67 65 20 69 73 20 74 68 65 20 70  nt page is the p
5f50: 61 67 65 20 74 68 61 74 0a 2a 2a 20 63 6f 6e 74  age that.** cont
5f60: 61 69 6e 73 20 61 20 70 6f 69 6e 74 65 72 20 74  ains a pointer t
5f70: 6f 20 74 68 65 20 63 68 69 6c 64 2e 20 20 45 76  o the child.  Ev
5f80: 65 72 79 20 70 61 67 65 20 69 6e 20 74 68 65 20  ery page in the 
5f90: 64 61 74 61 62 61 73 65 20 63 6f 6e 74 61 69 6e  database contain
5fa0: 73 0a 2a 2a 20 30 20 6f 72 20 31 20 70 61 72 65  s.** 0 or 1 pare
5fb0: 6e 74 20 70 61 67 65 73 2e 20 20 28 49 6e 20 74  nt pages.  (In t
5fc0: 68 69 73 20 63 6f 6e 74 65 78 74 20 27 64 61 74  his context 'dat
5fd0: 61 62 61 73 65 20 70 61 67 65 27 20 72 65 66 65  abase page' refe
5fe0: 72 73 0a 2a 2a 20 74 6f 20 61 6e 79 20 70 61 67  rs.** to any pag
5ff0: 65 20 74 68 61 74 20 69 73 20 6e 6f 74 20 70 61  e that is not pa
6000: 72 74 20 6f 66 20 74 68 65 20 70 6f 69 6e 74 65  rt of the pointe
6010: 72 20 6d 61 70 20 69 74 73 65 6c 66 2e 29 20 20  r map itself.)  
6020: 45 61 63 68 20 70 6f 69 6e 74 65 72 20 6d 61 70  Each pointer map
6030: 0a 2a 2a 20 65 6e 74 72 79 20 63 6f 6e 73 69 73  .** entry consis
6040: 74 73 20 6f 66 20 61 20 73 69 6e 67 6c 65 20 62  ts of a single b
6050: 79 74 65 20 27 74 79 70 65 27 20 61 6e 64 20 61  yte 'type' and a
6060: 20 34 20 62 79 74 65 20 70 61 72 65 6e 74 20 70   4 byte parent p
6070: 61 67 65 20 6e 75 6d 62 65 72 2e 0a 2a 2a 20 54  age number..** T
6080: 68 65 20 50 54 52 4d 41 50 5f 58 58 58 20 69 64  he PTRMAP_XXX id
6090: 65 6e 74 69 66 69 65 72 73 20 62 65 6c 6f 77 20  entifiers below 
60a0: 61 72 65 20 74 68 65 20 76 61 6c 69 64 20 74 79  are the valid ty
60b0: 70 65 73 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 70  pes..**.** The p
60c0: 75 72 70 6f 73 65 20 6f 66 20 74 68 65 20 70 6f  urpose of the po
60d0: 69 6e 74 65 72 20 6d 61 70 20 69 73 20 74 6f 20  inter map is to 
60e0: 66 61 63 69 6c 69 74 79 20 6d 6f 76 69 6e 67 20  facility moving 
60f0: 70 61 67 65 73 20 66 72 6f 6d 20 6f 6e 65 0a 2a  pages from one.*
6100: 2a 20 70 6f 73 69 74 69 6f 6e 20 69 6e 20 74 68  * position in th
6110: 65 20 66 69 6c 65 20 74 6f 20 61 6e 6f 74 68 65  e file to anothe
6120: 72 20 61 73 20 70 61 72 74 20 6f 66 20 61 75 74  r as part of aut
6130: 6f 76 61 63 75 75 6d 2e 20 20 57 68 65 6e 20 61  ovacuum.  When a
6140: 20 70 61 67 65 0a 2a 2a 20 69 73 20 6d 6f 76 65   page.** is move
6150: 64 2c 20 74 68 65 20 70 6f 69 6e 74 65 72 20 69  d, the pointer i
6160: 6e 20 69 74 73 20 70 61 72 65 6e 74 20 6d 75 73  n its parent mus
6170: 74 20 62 65 20 75 70 64 61 74 65 64 20 74 6f 20  t be updated to 
6180: 70 6f 69 6e 74 20 74 6f 20 74 68 65 0a 2a 2a 20  point to the.** 
6190: 6e 65 77 20 6c 6f 63 61 74 69 6f 6e 2e 20 20 54  new location.  T
61a0: 68 65 20 70 6f 69 6e 74 65 72 20 6d 61 70 20 69  he pointer map i
61b0: 73 20 75 73 65 64 20 74 6f 20 6c 6f 63 61 74 65  s used to locate
61c0: 20 74 68 65 20 70 61 72 65 6e 74 20 70 61 67 65   the parent page
61d0: 20 71 75 69 63 6b 6c 79 2e 0a 2a 2a 0a 2a 2a 20   quickly..**.** 
61e0: 50 54 52 4d 41 50 5f 52 4f 4f 54 50 41 47 45 3a  PTRMAP_ROOTPAGE:
61f0: 20 54 68 65 20 64 61 74 61 62 61 73 65 20 70 61   The database pa
6200: 67 65 20 69 73 20 61 20 72 6f 6f 74 2d 70 61 67  ge is a root-pag
6210: 65 2e 20 54 68 65 20 70 61 67 65 2d 6e 75 6d 62  e. The page-numb
6220: 65 72 20 69 73 20 6e 6f 74 0a 2a 2a 20 20 20 20  er is not.**    
6230: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 75 73                us
6240: 65 64 20 69 6e 20 74 68 69 73 20 63 61 73 65 2e  ed in this case.
6250: 0a 2a 2a 0a 2a 2a 20 50 54 52 4d 41 50 5f 46 52  .**.** PTRMAP_FR
6260: 45 45 50 41 47 45 3a 20 54 68 65 20 64 61 74 61  EEPAGE: The data
6270: 62 61 73 65 20 70 61 67 65 20 69 73 20 61 6e 20  base page is an 
6280: 75 6e 75 73 65 64 20 28 66 72 65 65 29 20 70 61  unused (free) pa
6290: 67 65 2e 20 54 68 65 20 70 61 67 65 2d 6e 75 6d  ge. The page-num
62a0: 62 65 72 20 0a 2a 2a 20 20 20 20 20 20 20 20 20  ber .**         
62b0: 20 20 20 20 20 20 20 20 20 69 73 20 6e 6f 74 20           is not 
62c0: 75 73 65 64 20 69 6e 20 74 68 69 73 20 63 61 73  used in this cas
62d0: 65 2e 0a 2a 2a 0a 2a 2a 20 50 54 52 4d 41 50 5f  e..**.** PTRMAP_
62e0: 4f 56 45 52 46 4c 4f 57 31 3a 20 54 68 65 20 64  OVERFLOW1: The d
62f0: 61 74 61 62 61 73 65 20 70 61 67 65 20 69 73 20  atabase page is 
6300: 74 68 65 20 66 69 72 73 74 20 70 61 67 65 20 69  the first page i
6310: 6e 20 61 20 6c 69 73 74 20 6f 66 20 0a 2a 2a 20  n a list of .** 
6320: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
6330: 20 20 6f 76 65 72 66 6c 6f 77 20 70 61 67 65 73    overflow pages
6340: 2e 20 54 68 65 20 70 61 67 65 20 6e 75 6d 62 65  . The page numbe
6350: 72 20 69 64 65 6e 74 69 66 69 65 73 20 74 68 65  r identifies the
6360: 20 70 61 67 65 20 74 68 61 74 0a 2a 2a 20 20 20   page that.**   
6370: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
6380: 63 6f 6e 74 61 69 6e 73 20 74 68 65 20 63 65 6c  contains the cel
6390: 6c 20 77 69 74 68 20 61 20 70 6f 69 6e 74 65 72  l with a pointer
63a0: 20 74 6f 20 74 68 69 73 20 6f 76 65 72 66 6c 6f   to this overflo
63b0: 77 20 70 61 67 65 2e 0a 2a 2a 0a 2a 2a 20 50 54  w page..**.** PT
63c0: 52 4d 41 50 5f 4f 56 45 52 46 4c 4f 57 32 3a 20  RMAP_OVERFLOW2: 
63d0: 54 68 65 20 64 61 74 61 62 61 73 65 20 70 61 67  The database pag
63e0: 65 20 69 73 20 74 68 65 20 73 65 63 6f 6e 64 20  e is the second 
63f0: 6f 72 20 6c 61 74 65 72 20 70 61 67 65 20 69 6e  or later page in
6400: 20 61 20 6c 69 73 74 20 6f 66 0a 2a 2a 20 20 20   a list of.**   
6410: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
6420: 6f 76 65 72 66 6c 6f 77 20 70 61 67 65 73 2e 20  overflow pages. 
6430: 54 68 65 20 70 61 67 65 2d 6e 75 6d 62 65 72 20  The page-number 
6440: 69 64 65 6e 74 69 66 69 65 73 20 74 68 65 20 70  identifies the p
6450: 72 65 76 69 6f 75 73 0a 2a 2a 20 20 20 20 20 20  revious.**      
6460: 20 20 20 20 20 20 20 20 20 20 20 20 20 70 61 67               pag
6470: 65 20 69 6e 20 74 68 65 20 6f 76 65 72 66 6c 6f  e in the overflo
6480: 77 20 70 61 67 65 20 6c 69 73 74 2e 0a 2a 2a 0a  w page list..**.
6490: 2a 2a 20 50 54 52 4d 41 50 5f 42 54 52 45 45 3a  ** PTRMAP_BTREE:
64a0: 20 54 68 65 20 64 61 74 61 62 61 73 65 20 70 61   The database pa
64b0: 67 65 20 69 73 20 61 20 6e 6f 6e 2d 72 6f 6f 74  ge is a non-root
64c0: 20 62 74 72 65 65 20 70 61 67 65 2e 20 54 68 65   btree page. The
64d0: 20 70 61 67 65 20 6e 75 6d 62 65 72 0a 2a 2a 20   page number.** 
64e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 69 64                id
64f0: 65 6e 74 69 66 69 65 73 20 74 68 65 20 70 61 72  entifies the par
6500: 65 6e 74 20 70 61 67 65 20 69 6e 20 74 68 65 20  ent page in the 
6510: 62 74 72 65 65 2e 0a 2a 2f 0a 23 64 65 66 69 6e  btree..*/.#defin
6520: 65 20 50 54 52 4d 41 50 5f 52 4f 4f 54 50 41 47  e PTRMAP_ROOTPAG
6530: 45 20 31 0a 23 64 65 66 69 6e 65 20 50 54 52 4d  E 1.#define PTRM
6540: 41 50 5f 46 52 45 45 50 41 47 45 20 32 0a 23 64  AP_FREEPAGE 2.#d
6550: 65 66 69 6e 65 20 50 54 52 4d 41 50 5f 4f 56 45  efine PTRMAP_OVE
6560: 52 46 4c 4f 57 31 20 33 0a 23 64 65 66 69 6e 65  RFLOW1 3.#define
6570: 20 50 54 52 4d 41 50 5f 4f 56 45 52 46 4c 4f 57   PTRMAP_OVERFLOW
6580: 32 20 34 0a 23 64 65 66 69 6e 65 20 50 54 52 4d  2 4.#define PTRM
6590: 41 50 5f 42 54 52 45 45 20 35 0a 0a 2f 2a 20 41  AP_BTREE 5../* A
65a0: 20 62 75 6e 63 68 20 6f 66 20 61 73 73 65 72 74   bunch of assert
65b0: 28 29 20 73 74 61 74 65 6d 65 6e 74 73 20 74 6f  () statements to
65c0: 20 63 68 65 63 6b 20 74 68 65 20 74 72 61 6e 73   check the trans
65d0: 61 63 74 69 6f 6e 20 73 74 61 74 65 20 76 61 72  action state var
65e0: 69 61 62 6c 65 73 0a 2a 2a 20 6f 66 20 68 61 6e  iables.** of han
65f0: 64 6c 65 20 70 20 28 74 79 70 65 20 42 74 72 65  dle p (type Btre
6600: 65 2a 29 20 61 72 65 20 69 6e 74 65 72 6e 61 6c  e*) are internal
6610: 6c 79 20 63 6f 6e 73 69 73 74 65 6e 74 2e 0a 2a  ly consistent..*
6620: 2f 0a 23 64 65 66 69 6e 65 20 62 74 72 65 65 49  /.#define btreeI
6630: 6e 74 65 67 72 69 74 79 28 70 29 20 5c 0a 20 20  ntegrity(p) \.  
6640: 61 73 73 65 72 74 28 20 70 2d 3e 70 42 74 2d 3e  assert( p->pBt->
6650: 69 6e 54 72 61 6e 73 61 63 74 69 6f 6e 21 3d 54  inTransaction!=T
6660: 52 41 4e 53 5f 4e 4f 4e 45 20 7c 7c 20 70 2d 3e  RANS_NONE || p->
6670: 70 42 74 2d 3e 6e 54 72 61 6e 73 61 63 74 69 6f  pBt->nTransactio
6680: 6e 3d 3d 30 20 29 3b 20 5c 0a 20 20 61 73 73 65  n==0 ); \.  asse
6690: 72 74 28 20 70 2d 3e 70 42 74 2d 3e 69 6e 54 72  rt( p->pBt->inTr
66a0: 61 6e 73 61 63 74 69 6f 6e 3e 3d 70 2d 3e 69 6e  ansaction>=p->in
66b0: 54 72 61 6e 73 20 29 3b 20 0a 0a 0a 2f 2a 0a 2a  Trans ); .../*.*
66c0: 2a 20 54 68 65 20 49 53 41 55 54 4f 56 41 43 55  * The ISAUTOVACU
66d0: 55 4d 20 6d 61 63 72 6f 20 69 73 20 75 73 65 64  UM macro is used
66e0: 20 77 69 74 68 69 6e 20 62 61 6c 61 6e 63 65 5f   within balance_
66f0: 6e 6f 6e 72 6f 6f 74 28 29 20 74 6f 20 64 65 74  nonroot() to det
6700: 65 72 6d 69 6e 65 0a 2a 2a 20 69 66 20 74 68 65  ermine.** if the
6710: 20 64 61 74 61 62 61 73 65 20 73 75 70 70 6f 72   database suppor
6720: 74 73 20 61 75 74 6f 2d 76 61 63 75 75 6d 20 6f  ts auto-vacuum o
6730: 72 20 6e 6f 74 2e 20 42 65 63 61 75 73 65 20 69  r not. Because i
6740: 74 20 69 73 20 75 73 65 64 0a 2a 2a 20 77 69 74  t is used.** wit
6750: 68 69 6e 20 61 6e 20 65 78 70 72 65 73 73 69 6f  hin an expressio
6760: 6e 20 74 68 61 74 20 69 73 20 61 6e 20 61 72 67  n that is an arg
6770: 75 6d 65 6e 74 20 74 6f 20 61 6e 6f 74 68 65 72  ument to another
6780: 20 6d 61 63 72 6f 20 0a 2a 2a 20 28 73 71 6c 69   macro .** (sqli
6790: 74 65 4d 61 6c 6c 6f 63 52 61 77 29 2c 20 69 74  teMallocRaw), it
67a0: 20 69 73 20 6e 6f 74 20 70 6f 73 73 69 62 6c 65   is not possible
67b0: 20 74 6f 20 75 73 65 20 63 6f 6e 64 69 74 69 6f   to use conditio
67c0: 6e 61 6c 20 63 6f 6d 70 69 6c 61 74 69 6f 6e 2e  nal compilation.
67d0: 0a 2a 2a 20 53 6f 2c 20 74 68 69 73 20 6d 61 63  .** So, this mac
67e0: 72 6f 20 69 73 20 64 65 66 69 6e 65 64 20 69 6e  ro is defined in
67f0: 73 74 65 61 64 2e 0a 2a 2f 0a 23 69 66 6e 64 65  stead..*/.#ifnde
6800: 66 20 53 51 4c 49 54 45 5f 4f 4d 49 54 5f 41 55  f SQLITE_OMIT_AU
6810: 54 4f 56 41 43 55 55 4d 0a 23 64 65 66 69 6e 65  TOVACUUM.#define
6820: 20 49 53 41 55 54 4f 56 41 43 55 55 4d 20 28 70   ISAUTOVACUUM (p
6830: 42 74 2d 3e 61 75 74 6f 56 61 63 75 75 6d 29 0a  Bt->autoVacuum).
6840: 23 65 6c 73 65 0a 23 64 65 66 69 6e 65 20 49 53  #else.#define IS
6850: 41 55 54 4f 56 41 43 55 55 4d 20 30 0a 23 65 6e  AUTOVACUUM 0.#en
6860: 64 69 66 0a 0a 0a 2f 2a 0a 2a 2a 20 54 68 69 73  dif.../*.** This
6870: 20 73 74 72 75 63 74 75 72 65 20 69 73 20 70 61   structure is pa
6880: 73 73 65 64 20 61 72 6f 75 6e 64 20 74 68 72 6f  ssed around thro
6890: 75 67 68 20 61 6c 6c 20 74 68 65 20 73 61 6e 69  ugh all the sani
68a0: 74 79 20 63 68 65 63 6b 69 6e 67 20 72 6f 75 74  ty checking rout
68b0: 69 6e 65 73 0a 2a 2a 20 69 6e 20 6f 72 64 65 72  ines.** in order
68c0: 20 74 6f 20 6b 65 65 70 20 74 72 61 63 6b 20 6f   to keep track o
68d0: 66 20 73 6f 6d 65 20 67 6c 6f 62 61 6c 20 73 74  f some global st
68e0: 61 74 65 20 69 6e 66 6f 72 6d 61 74 69 6f 6e 2e  ate information.
68f0: 0a 2a 2f 0a 74 79 70 65 64 65 66 20 73 74 72 75  .*/.typedef stru
6900: 63 74 20 49 6e 74 65 67 72 69 74 79 43 6b 20 49  ct IntegrityCk I
6910: 6e 74 65 67 72 69 74 79 43 6b 3b 0a 73 74 72 75  ntegrityCk;.stru
6920: 63 74 20 49 6e 74 65 67 72 69 74 79 43 6b 20 7b  ct IntegrityCk {
6930: 0a 20 20 42 74 53 68 61 72 65 64 20 2a 70 42 74  .  BtShared *pBt
6940: 3b 20 20 20 20 2f 2a 20 54 68 65 20 74 72 65 65  ;    /* The tree
6950: 20 62 65 69 6e 67 20 63 68 65 63 6b 65 64 20 6f   being checked o
6960: 75 74 20 2a 2f 0a 20 20 50 61 67 65 72 20 2a 70  ut */.  Pager *p
6970: 50 61 67 65 72 3b 20 20 20 20 2f 2a 20 54 68 65  Pager;    /* The
6980: 20 61 73 73 6f 63 69 61 74 65 64 20 70 61 67 65   associated page
6990: 72 2e 20 20 41 6c 73 6f 20 61 63 63 65 73 73 69  r.  Also accessi
69a0: 62 6c 65 20 62 79 20 70 42 74 2d 3e 70 50 61 67  ble by pBt->pPag
69b0: 65 72 20 2a 2f 0a 20 20 69 6e 74 20 6e 50 61 67  er */.  int nPag
69c0: 65 3b 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d  e;        /* Num
69d0: 62 65 72 20 6f 66 20 70 61 67 65 73 20 69 6e 20  ber of pages in 
69e0: 74 68 65 20 64 61 74 61 62 61 73 65 20 2a 2f 0a  the database */.
69f0: 20 20 69 6e 74 20 2a 61 6e 52 65 66 3b 20 20 20    int *anRef;   
6a00: 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66      /* Number of
6a10: 20 74 69 6d 65 73 20 65 61 63 68 20 70 61 67 65   times each page
6a20: 20 69 73 20 72 65 66 65 72 65 6e 63 65 64 20 2a   is referenced *
6a30: 2f 0a 20 20 69 6e 74 20 6d 78 45 72 72 3b 20 20  /.  int mxErr;  
6a40: 20 20 20 20 20 20 2f 2a 20 53 74 6f 70 20 61 63        /* Stop ac
6a50: 63 75 6d 75 6c 61 74 69 6e 67 20 65 72 72 6f 72  cumulating error
6a60: 73 20 77 68 65 6e 20 74 68 69 73 20 72 65 61 63  s when this reac
6a70: 68 65 73 20 7a 65 72 6f 20 2a 2f 0a 20 20 69 6e  hes zero */.  in
6a80: 74 20 6e 45 72 72 3b 20 20 20 20 20 20 20 20 20  t nErr;         
6a90: 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 6d 65 73  /* Number of mes
6aa0: 73 61 67 65 73 20 77 72 69 74 74 65 6e 20 74 6f  sages written to
6ab0: 20 7a 45 72 72 4d 73 67 20 73 6f 20 66 61 72 20   zErrMsg so far 
6ac0: 2a 2f 0a 20 20 53 74 72 41 63 63 75 6d 20 65 72  */.  StrAccum er
6ad0: 72 4d 73 67 3b 20 20 2f 2a 20 41 63 63 75 6d 75  rMsg;  /* Accumu
6ae0: 6c 61 74 65 20 74 68 65 20 65 72 72 6f 72 20 6d  late the error m
6af0: 65 73 73 61 67 65 20 74 65 78 74 20 68 65 72 65  essage text here
6b00: 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 52 65   */.};../*.** Re
6b10: 61 64 20 6f 72 20 77 72 69 74 65 20 61 20 74 77  ad or write a tw
6b20: 6f 2d 20 61 6e 64 20 66 6f 75 72 2d 62 79 74 65  o- and four-byte
6b30: 20 62 69 67 2d 65 6e 64 69 61 6e 20 69 6e 74 65   big-endian inte
6b40: 67 65 72 20 76 61 6c 75 65 73 2e 0a 2a 2f 0a 23  ger values..*/.#
6b50: 64 65 66 69 6e 65 20 67 65 74 32 62 79 74 65 28  define get2byte(
6b60: 78 29 20 20 20 28 28 78 29 5b 30 5d 3c 3c 38 20  x)   ((x)[0]<<8 
6b70: 7c 20 28 78 29 5b 31 5d 29 0a 23 64 65 66 69 6e  | (x)[1]).#defin
6b80: 65 20 70 75 74 32 62 79 74 65 28 70 2c 76 29 20  e put2byte(p,v) 
6b90: 28 28 70 29 5b 30 5d 20 3d 20 28 76 29 3e 3e 38  ((p)[0] = (v)>>8
6ba0: 2c 20 28 70 29 5b 31 5d 20 3d 20 28 76 29 29 0a  , (p)[1] = (v)).
6bb0: 23 64 65 66 69 6e 65 20 67 65 74 34 62 79 74 65  #define get4byte
6bc0: 20 73 71 6c 69 74 65 33 47 65 74 34 62 79 74 65   sqlite3Get4byte
6bd0: 0a 23 64 65 66 69 6e 65 20 70 75 74 34 62 79 74  .#define put4byt
6be0: 65 20 73 71 6c 69 74 65 33 50 75 74 34 62 79 74  e sqlite3Put4byt
6bf0: 65 0a 0a 2f 2a 0a 2a 2a 20 49 6e 74 65 72 6e 61  e../*.** Interna
6c00: 6c 20 72 6f 75 74 69 6e 65 73 20 74 68 61 74 20  l routines that 
6c10: 73 68 6f 75 6c 64 20 62 65 20 61 63 63 65 73 73  should be access
6c20: 65 64 20 62 79 20 74 68 65 20 62 74 72 65 65 20  ed by the btree 
6c30: 6c 61 79 65 72 20 6f 6e 6c 79 2e 0a 2a 2f 0a 69  layer only..*/.i
6c40: 6e 74 20 73 71 6c 69 74 65 33 42 74 72 65 65 47  nt sqlite3BtreeG
6c50: 65 74 50 61 67 65 28 42 74 53 68 61 72 65 64 2a  etPage(BtShared*
6c60: 2c 20 50 67 6e 6f 2c 20 4d 65 6d 50 61 67 65 2a  , Pgno, MemPage*
6c70: 2a 2c 20 69 6e 74 29 3b 0a 69 6e 74 20 73 71 6c  *, int);.int sql
6c80: 69 74 65 33 42 74 72 65 65 49 6e 69 74 50 61 67  ite3BtreeInitPag
6c90: 65 28 4d 65 6d 50 61 67 65 20 2a 70 50 61 67 65  e(MemPage *pPage
6ca0: 2c 20 4d 65 6d 50 61 67 65 20 2a 70 50 61 72 65  , MemPage *pPare
6cb0: 6e 74 29 3b 0a 76 6f 69 64 20 73 71 6c 69 74 65  nt);.void sqlite
6cc0: 33 42 74 72 65 65 50 61 72 73 65 43 65 6c 6c 50  3BtreeParseCellP
6cd0: 74 72 28 4d 65 6d 50 61 67 65 2a 2c 20 75 38 2a  tr(MemPage*, u8*
6ce0: 2c 20 43 65 6c 6c 49 6e 66 6f 2a 29 3b 0a 76 6f  , CellInfo*);.vo
6cf0: 69 64 20 73 71 6c 69 74 65 33 42 74 72 65 65 50  id sqlite3BtreeP
6d00: 61 72 73 65 43 65 6c 6c 28 4d 65 6d 50 61 67 65  arseCell(MemPage
6d10: 2a 2c 20 69 6e 74 2c 20 43 65 6c 6c 49 6e 66 6f  *, int, CellInfo
6d20: 2a 29 3b 0a 69 6e 74 20 73 71 6c 69 74 65 33 42  *);.int sqlite3B
6d30: 74 72 65 65 52 65 73 74 6f 72 65 43 75 72 73 6f  treeRestoreCurso
6d40: 72 50 6f 73 69 74 69 6f 6e 28 42 74 43 75 72 73  rPosition(BtCurs
6d50: 6f 72 20 2a 70 43 75 72 29 3b 0a 76 6f 69 64 20  or *pCur);.void 
6d60: 73 71 6c 69 74 65 33 42 74 72 65 65 47 65 74 54  sqlite3BtreeGetT
6d70: 65 6d 70 43 75 72 73 6f 72 28 42 74 43 75 72 73  empCursor(BtCurs
6d80: 6f 72 20 2a 70 43 75 72 2c 20 42 74 43 75 72 73  or *pCur, BtCurs
6d90: 6f 72 20 2a 70 54 65 6d 70 43 75 72 29 3b 0a 76  or *pTempCur);.v
6da0: 6f 69 64 20 73 71 6c 69 74 65 33 42 74 72 65 65  oid sqlite3Btree
6db0: 52 65 6c 65 61 73 65 54 65 6d 70 43 75 72 73 6f  ReleaseTempCurso
6dc0: 72 28 42 74 43 75 72 73 6f 72 20 2a 70 43 75 72  r(BtCursor *pCur
6dd0: 29 3b 0a 69 6e 74 20 73 71 6c 69 74 65 33 42 74  );.int sqlite3Bt
6de0: 72 65 65 49 73 52 6f 6f 74 50 61 67 65 28 4d 65  reeIsRootPage(Me
6df0: 6d 50 61 67 65 20 2a 70 50 61 67 65 29 3b 0a 76  mPage *pPage);.v
6e00: 6f 69 64 20 73 71 6c 69 74 65 33 42 74 72 65 65  oid sqlite3Btree
6e10: 4d 6f 76 65 54 6f 50 61 72 65 6e 74 28 42 74 43  MoveToParent(BtC
6e20: 75 72 73 6f 72 20 2a 70 43 75 72 29 3b 0a        ursor *pCur);.