/ Hex Artifact Content
Login

Artifact 0a4884e6152d7cae9c741e91b830064c19fd2c05:


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 34 32 20 32 30 30 39  nt.h,v 1.42 2009
0190: 2f 30 32 2f 30 33 20 31 36 3a 35 31 3a 32 35 20  /02/03 16:51:25 
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 0a 2f 2a 20 52 6f 75 6e 64 20 75 70 20  h"../* Round up 
2650: 61 20 6e 75 6d 62 65 72 20 74 6f 20 74 68 65 20  a number to the 
2660: 6e 65 78 74 20 6c 61 72 67 65 72 20 6d 75 6c 74  next larger mult
2670: 69 70 6c 65 20 6f 66 20 38 2e 20 20 54 68 69 73  iple of 8.  This
2680: 20 69 73 20 75 73 65 64 0a 2a 2a 20 74 6f 20 66   is used.** to f
2690: 6f 72 63 65 20 38 2d 62 79 74 65 20 61 6c 69 67  orce 8-byte alig
26a0: 6e 6d 65 6e 74 20 6f 6e 20 36 34 2d 62 69 74 20  nment on 64-bit 
26b0: 61 72 63 68 69 74 65 63 74 75 72 65 73 2e 0a 2a  architectures..*
26c0: 2f 0a 23 64 65 66 69 6e 65 20 52 4f 55 4e 44 38  /.#define ROUND8
26d0: 28 78 29 20 20 20 28 28 78 2b 37 29 26 7e 37 29  (x)   ((x+7)&~7)
26e0: 0a 0a 0a 2f 2a 20 54 68 65 20 66 6f 6c 6c 6f 77  .../* The follow
26f0: 69 6e 67 20 76 61 6c 75 65 20 69 73 20 74 68 65  ing value is the
2700: 20 6d 61 78 69 6d 75 6d 20 63 65 6c 6c 20 73 69   maximum cell si
2710: 7a 65 20 61 73 73 75 6d 69 6e 67 20 61 20 6d 61  ze assuming a ma
2720: 78 69 6d 75 6d 20 70 61 67 65 0a 2a 2a 20 73 69  ximum page.** si
2730: 7a 65 20 67 69 76 65 20 61 62 6f 76 65 2e 0a 2a  ze give above..*
2740: 2f 0a 23 64 65 66 69 6e 65 20 4d 58 5f 43 45 4c  /.#define MX_CEL
2750: 4c 5f 53 49 5a 45 28 70 42 74 29 20 20 28 70 42  L_SIZE(pBt)  (pB
2760: 74 2d 3e 70 61 67 65 53 69 7a 65 2d 38 29 0a 0a  t->pageSize-8)..
2770: 2f 2a 20 54 68 65 20 6d 61 78 69 6d 75 6d 20 6e  /* The maximum n
2780: 75 6d 62 65 72 20 6f 66 20 63 65 6c 6c 73 20 6f  umber of cells o
2790: 6e 20 61 20 73 69 6e 67 6c 65 20 70 61 67 65 20  n a single page 
27a0: 6f 66 20 74 68 65 20 64 61 74 61 62 61 73 65 2e  of the database.
27b0: 20 20 54 68 69 73 0a 2a 2a 20 61 73 73 75 6d 65    This.** assume
27c0: 73 20 61 20 6d 69 6e 69 6d 75 6d 20 63 65 6c 6c  s a minimum cell
27d0: 20 73 69 7a 65 20 6f 66 20 36 20 62 79 74 65 73   size of 6 bytes
27e0: 20 20 28 34 20 62 79 74 65 73 20 66 6f 72 20 74    (4 bytes for t
27f0: 68 65 20 63 65 6c 6c 20 69 74 73 65 6c 66 0a 2a  he cell itself.*
2800: 2a 20 70 6c 75 73 20 32 20 62 79 74 65 73 20 66  * plus 2 bytes f
2810: 6f 72 20 74 68 65 20 69 6e 64 65 78 20 74 6f 20  or the index to 
2820: 74 68 65 20 63 65 6c 6c 20 69 6e 20 74 68 65 20  the cell in the 
2830: 70 61 67 65 20 68 65 61 64 65 72 29 2e 20 20 53  page header).  S
2840: 75 63 68 0a 2a 2a 20 73 6d 61 6c 6c 20 63 65 6c  uch.** small cel
2850: 6c 73 20 77 69 6c 6c 20 62 65 20 72 61 72 65 2c  ls will be rare,
2860: 20 62 75 74 20 74 68 65 79 20 61 72 65 20 70 6f   but they are po
2870: 73 73 69 62 6c 65 2e 0a 2a 2f 0a 23 64 65 66 69  ssible..*/.#defi
2880: 6e 65 20 4d 58 5f 43 45 4c 4c 28 70 42 74 29 20  ne MX_CELL(pBt) 
2890: 28 28 70 42 74 2d 3e 70 61 67 65 53 69 7a 65 2d  ((pBt->pageSize-
28a0: 38 29 2f 36 29 0a 0a 2f 2a 20 46 6f 72 77 61 72  8)/6)../* Forwar
28b0: 64 20 64 65 63 6c 61 72 61 74 69 6f 6e 73 20 2a  d declarations *
28c0: 2f 0a 74 79 70 65 64 65 66 20 73 74 72 75 63 74  /.typedef struct
28d0: 20 4d 65 6d 50 61 67 65 20 4d 65 6d 50 61 67 65   MemPage MemPage
28e0: 3b 0a 74 79 70 65 64 65 66 20 73 74 72 75 63 74  ;.typedef struct
28f0: 20 42 74 4c 6f 63 6b 20 42 74 4c 6f 63 6b 3b 0a   BtLock BtLock;.
2900: 0a 2f 2a 0a 2a 2a 20 54 68 69 73 20 69 73 20 61  ./*.** This is a
2910: 20 6d 61 67 69 63 20 73 74 72 69 6e 67 20 74 68   magic string th
2920: 61 74 20 61 70 70 65 61 72 73 20 61 74 20 74 68  at appears at th
2930: 65 20 62 65 67 69 6e 6e 69 6e 67 20 6f 66 20 65  e beginning of e
2940: 76 65 72 79 0a 2a 2a 20 53 51 4c 69 74 65 20 64  very.** SQLite d
2950: 61 74 61 62 61 73 65 20 69 6e 20 6f 72 64 65 72  atabase in order
2960: 20 74 6f 20 69 64 65 6e 74 69 66 79 20 74 68 65   to identify the
2970: 20 66 69 6c 65 20 61 73 20 61 20 72 65 61 6c 20   file as a real 
2980: 64 61 74 61 62 61 73 65 2e 0a 2a 2a 0a 2a 2a 20  database..**.** 
2990: 59 6f 75 20 63 61 6e 20 63 68 61 6e 67 65 20 74  You can change t
29a0: 68 69 73 20 76 61 6c 75 65 20 61 74 20 63 6f 6d  his value at com
29b0: 70 69 6c 65 2d 74 69 6d 65 20 62 79 20 73 70 65  pile-time by spe
29c0: 63 69 66 79 69 6e 67 20 61 0a 2a 2a 20 2d 44 53  cifying a.** -DS
29d0: 51 4c 49 54 45 5f 46 49 4c 45 5f 48 45 41 44 45  QLITE_FILE_HEADE
29e0: 52 3d 22 2e 2e 2e 22 20 6f 6e 20 74 68 65 20 63  R="..." on the c
29f0: 6f 6d 70 69 6c 65 72 20 63 6f 6d 6d 61 6e 64 2d  ompiler command-
2a00: 6c 69 6e 65 2e 20 20 54 68 65 0a 2a 2a 20 68 65  line.  The.** he
2a10: 61 64 65 72 20 6d 75 73 74 20 62 65 20 65 78 61  ader must be exa
2a20: 63 74 6c 79 20 31 36 20 62 79 74 65 73 20 69 6e  ctly 16 bytes in
2a30: 63 6c 75 64 69 6e 67 20 74 68 65 20 7a 65 72 6f  cluding the zero
2a40: 2d 74 65 72 6d 69 6e 61 74 6f 72 20 73 6f 0a 2a  -terminator so.*
2a50: 2a 20 74 68 65 20 73 74 72 69 6e 67 20 69 74 73  * the string its
2a60: 65 6c 66 20 73 68 6f 75 6c 64 20 62 65 20 31 35  elf should be 15
2a70: 20 63 68 61 72 61 63 74 65 72 73 20 6c 6f 6e 67   characters long
2a80: 2e 20 20 49 66 20 79 6f 75 20 63 68 61 6e 67 65  .  If you change
2a90: 0a 2a 2a 20 74 68 65 20 68 65 61 64 65 72 2c 20  .** the header, 
2aa0: 74 68 65 6e 20 79 6f 75 72 20 63 75 73 74 6f 6d  then your custom
2ab0: 20 6c 69 62 72 61 72 79 20 77 69 6c 6c 20 6e 6f   library will no
2ac0: 74 20 62 65 20 61 62 6c 65 20 74 6f 20 72 65 61  t be able to rea
2ad0: 64 20 0a 2a 2a 20 64 61 74 61 62 61 73 65 73 20  d .** databases 
2ae0: 67 65 6e 65 72 61 74 65 64 20 62 79 20 74 68 65  generated by the
2af0: 20 73 74 61 6e 64 61 72 64 20 74 6f 6f 6c 73 20   standard tools 
2b00: 61 6e 64 20 74 68 65 20 73 74 61 6e 64 61 72 64  and the standard
2b10: 20 74 6f 6f 6c 73 0a 2a 2a 20 77 69 6c 6c 20 6e   tools.** will n
2b20: 6f 74 20 62 65 20 61 62 6c 65 20 74 6f 20 72 65  ot be able to re
2b30: 61 64 20 64 61 74 61 62 61 73 65 73 20 63 72 65  ad databases cre
2b40: 61 74 65 64 20 62 79 20 79 6f 75 72 20 63 75 73  ated by your cus
2b50: 74 6f 6d 20 6c 69 62 72 61 72 79 2e 0a 2a 2f 0a  tom library..*/.
2b60: 23 69 66 6e 64 65 66 20 53 51 4c 49 54 45 5f 46  #ifndef SQLITE_F
2b70: 49 4c 45 5f 48 45 41 44 45 52 20 2f 2a 20 31 32  ILE_HEADER /* 12
2b80: 33 34 35 36 37 38 39 20 31 32 33 34 35 36 20 2a  3456789 123456 *
2b90: 2f 0a 23 20 20 64 65 66 69 6e 65 20 53 51 4c 49  /.#  define SQLI
2ba0: 54 45 5f 46 49 4c 45 5f 48 45 41 44 45 52 20 22  TE_FILE_HEADER "
2bb0: 53 51 4c 69 74 65 20 66 6f 72 6d 61 74 20 33 22  SQLite format 3"
2bc0: 0a 23 65 6e 64 69 66 0a 0a 2f 2a 0a 2a 2a 20 50  .#endif../*.** P
2bd0: 61 67 65 20 74 79 70 65 20 66 6c 61 67 73 2e 20  age type flags. 
2be0: 20 41 6e 20 4f 52 65 64 20 63 6f 6d 62 69 6e 61   An ORed combina
2bf0: 74 69 6f 6e 20 6f 66 20 74 68 65 73 65 20 66 6c  tion of these fl
2c00: 61 67 73 20 61 70 70 65 61 72 20 61 73 20 74 68  ags appear as th
2c10: 65 0a 2a 2a 20 66 69 72 73 74 20 62 79 74 65 20  e.** first byte 
2c20: 6f 66 20 6f 6e 2d 64 69 73 6b 20 69 6d 61 67 65  of on-disk image
2c30: 20 6f 66 20 65 76 65 72 79 20 42 54 72 65 65 20   of every BTree 
2c40: 70 61 67 65 2e 0a 2a 2f 0a 23 64 65 66 69 6e 65  page..*/.#define
2c50: 20 50 54 46 5f 49 4e 54 4b 45 59 20 20 20 20 30   PTF_INTKEY    0
2c60: 78 30 31 0a 23 64 65 66 69 6e 65 20 50 54 46 5f  x01.#define PTF_
2c70: 5a 45 52 4f 44 41 54 41 20 20 30 78 30 32 0a 23  ZERODATA  0x02.#
2c80: 64 65 66 69 6e 65 20 50 54 46 5f 4c 45 41 46 44  define PTF_LEAFD
2c90: 41 54 41 20 20 30 78 30 34 0a 23 64 65 66 69 6e  ATA  0x04.#defin
2ca0: 65 20 50 54 46 5f 4c 45 41 46 20 20 20 20 20 20  e PTF_LEAF      
2cb0: 30 78 30 38 0a 0a 2f 2a 0a 2a 2a 20 41 73 20 65  0x08../*.** As e
2cc0: 61 63 68 20 70 61 67 65 20 6f 66 20 74 68 65 20  ach page of the 
2cd0: 66 69 6c 65 20 69 73 20 6c 6f 61 64 65 64 20 69  file is loaded i
2ce0: 6e 74 6f 20 6d 65 6d 6f 72 79 2c 20 61 6e 20 69  nto memory, an i
2cf0: 6e 73 74 61 6e 63 65 20 6f 66 20 74 68 65 20 66  nstance of the f
2d00: 6f 6c 6c 6f 77 69 6e 67 0a 2a 2a 20 73 74 72 75  ollowing.** stru
2d10: 63 74 75 72 65 20 69 73 20 61 70 70 65 6e 64 65  cture is appende
2d20: 64 20 61 6e 64 20 69 6e 69 74 69 61 6c 69 7a 65  d and initialize
2d30: 64 20 74 6f 20 7a 65 72 6f 2e 20 20 54 68 69 73  d to zero.  This
2d40: 20 73 74 72 75 63 74 75 72 65 20 73 74 6f 72 65   structure store
2d50: 73 0a 2a 2a 20 69 6e 66 6f 72 6d 61 74 69 6f 6e  s.** information
2d60: 20 61 62 6f 75 74 20 74 68 65 20 70 61 67 65 20   about the page 
2d70: 74 68 61 74 20 69 73 20 64 65 63 6f 64 65 64 20  that is decoded 
2d80: 66 72 6f 6d 20 74 68 65 20 72 61 77 20 66 69 6c  from the raw fil
2d90: 65 20 70 61 67 65 2e 0a 2a 2a 0a 2a 2a 20 54 68  e page..**.** Th
2da0: 65 20 70 50 61 72 65 6e 74 20 66 69 65 6c 64 20  e pParent field 
2db0: 70 6f 69 6e 74 73 20 62 61 63 6b 20 74 6f 20 74  points back to t
2dc0: 68 65 20 70 61 72 65 6e 74 20 70 61 67 65 2e 20  he parent page. 
2dd0: 20 54 68 69 73 20 61 6c 6c 6f 77 73 20 75 73 20   This allows us 
2de0: 74 6f 0a 2a 2a 20 77 61 6c 6b 20 75 70 20 74 68  to.** walk up th
2df0: 65 20 42 54 72 65 65 20 66 72 6f 6d 20 61 6e 79  e BTree from any
2e00: 20 6c 65 61 66 20 74 6f 20 74 68 65 20 72 6f 6f   leaf to the roo
2e10: 74 2e 20 20 43 61 72 65 20 6d 75 73 74 20 62 65  t.  Care must be
2e20: 20 74 61 6b 65 6e 20 74 6f 0a 2a 2a 20 75 6e 72   taken to.** unr
2e30: 65 66 28 29 20 74 68 65 20 70 61 72 65 6e 74 20  ef() the parent 
2e40: 70 61 67 65 20 70 6f 69 6e 74 65 72 20 77 68 65  page pointer whe
2e50: 6e 20 74 68 69 73 20 70 61 67 65 20 69 73 20 6e  n this page is n
2e60: 6f 20 6c 6f 6e 67 65 72 20 72 65 66 65 72 65 6e  o longer referen
2e70: 63 65 64 2e 0a 2a 2a 20 54 68 65 20 70 61 67 65  ced..** The page
2e80: 44 65 73 74 72 75 63 74 6f 72 28 29 20 72 6f 75  Destructor() rou
2e90: 74 69 6e 65 20 68 61 6e 64 6c 65 73 20 74 68 61  tine handles tha
2ea0: 74 20 63 68 6f 72 65 2e 0a 2a 2a 0a 2a 2a 20 41  t chore..**.** A
2eb0: 63 63 65 73 73 20 74 6f 20 61 6c 6c 20 66 69 65  ccess to all fie
2ec0: 6c 64 73 20 6f 66 20 74 68 69 73 20 73 74 72 75  lds of this stru
2ed0: 63 74 75 72 65 20 69 73 20 63 6f 6e 74 72 6f 6c  cture is control
2ee0: 6c 65 64 20 62 79 20 74 68 65 20 6d 75 74 65 78  led by the mutex
2ef0: 0a 2a 2a 20 73 74 6f 72 65 64 20 69 6e 20 4d 65  .** stored in Me
2f00: 6d 50 61 67 65 2e 70 42 74 2d 3e 6d 75 74 65 78  mPage.pBt->mutex
2f10: 2e 0a 2a 2f 0a 73 74 72 75 63 74 20 4d 65 6d 50  ..*/.struct MemP
2f20: 61 67 65 20 7b 0a 20 20 75 38 20 69 73 49 6e 69  age {.  u8 isIni
2f30: 74 3b 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20  t;           /* 
2f40: 54 72 75 65 20 69 66 20 70 72 65 76 69 6f 75 73  True if previous
2f50: 6c 79 20 69 6e 69 74 69 61 6c 69 7a 65 64 2e 20  ly initialized. 
2f60: 4d 55 53 54 20 42 45 20 46 49 52 53 54 21 20 2a  MUST BE FIRST! *
2f70: 2f 0a 20 20 75 38 20 6e 4f 76 65 72 66 6c 6f 77  /.  u8 nOverflow
2f80: 3b 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62  ;        /* Numb
2f90: 65 72 20 6f 66 20 6f 76 65 72 66 6c 6f 77 20 63  er of overflow c
2fa0: 65 6c 6c 20 62 6f 64 69 65 73 20 69 6e 20 61 43  ell bodies in aC
2fb0: 65 6c 6c 5b 5d 20 2a 2f 0a 20 20 75 38 20 69 6e  ell[] */.  u8 in
2fc0: 74 4b 65 79 3b 20 20 20 20 20 20 20 20 20 20 20  tKey;           
2fd0: 2f 2a 20 54 72 75 65 20 69 66 20 69 6e 74 6b 65  /* True if intke
2fe0: 79 20 66 6c 61 67 20 69 73 20 73 65 74 20 2a 2f  y flag is set */
2ff0: 0a 20 20 75 38 20 6c 65 61 66 3b 20 20 20 20 20  .  u8 leaf;     
3000: 20 20 20 20 20 20 20 20 2f 2a 20 54 72 75 65 20          /* True 
3010: 69 66 20 6c 65 61 66 20 66 6c 61 67 20 69 73 20  if leaf flag is 
3020: 73 65 74 20 2a 2f 0a 20 20 75 38 20 68 61 73 44  set */.  u8 hasD
3030: 61 74 61 3b 20 20 20 20 20 20 20 20 20 20 2f 2a  ata;          /*
3040: 20 54 72 75 65 20 69 66 20 74 68 69 73 20 70 61   True if this pa
3050: 67 65 20 73 74 6f 72 65 73 20 64 61 74 61 20 2a  ge stores data *
3060: 2f 0a 20 20 75 38 20 68 64 72 4f 66 66 73 65 74  /.  u8 hdrOffset
3070: 3b 20 20 20 20 20 20 20 20 2f 2a 20 31 30 30 20  ;        /* 100 
3080: 66 6f 72 20 70 61 67 65 20 31 2e 20 20 30 20 6f  for page 1.  0 o
3090: 74 68 65 72 77 69 73 65 20 2a 2f 0a 20 20 75 38  therwise */.  u8
30a0: 20 63 68 69 6c 64 50 74 72 53 69 7a 65 3b 20 20   childPtrSize;  
30b0: 20 20 20 2f 2a 20 30 20 69 66 20 6c 65 61 66 3d     /* 0 if leaf=
30c0: 3d 31 2e 20 20 34 20 69 66 20 6c 65 61 66 3d 3d  =1.  4 if leaf==
30d0: 30 20 2a 2f 0a 20 20 75 31 36 20 6d 61 78 4c 6f  0 */.  u16 maxLo
30e0: 63 61 6c 3b 20 20 20 20 20 20 20 20 2f 2a 20 43  cal;        /* C
30f0: 6f 70 79 20 6f 66 20 42 74 53 68 61 72 65 64 2e  opy of BtShared.
3100: 6d 61 78 4c 6f 63 61 6c 20 6f 72 20 42 74 53 68  maxLocal or BtSh
3110: 61 72 65 64 2e 6d 61 78 4c 65 61 66 20 2a 2f 0a  ared.maxLeaf */.
3120: 20 20 75 31 36 20 6d 69 6e 4c 6f 63 61 6c 3b 20    u16 minLocal; 
3130: 20 20 20 20 20 20 20 2f 2a 20 43 6f 70 79 20 6f         /* Copy o
3140: 66 20 42 74 53 68 61 72 65 64 2e 6d 69 6e 4c 6f  f BtShared.minLo
3150: 63 61 6c 20 6f 72 20 42 74 53 68 61 72 65 64 2e  cal or BtShared.
3160: 6d 69 6e 4c 65 61 66 20 2a 2f 0a 20 20 75 31 36  minLeaf */.  u16
3170: 20 63 65 6c 6c 4f 66 66 73 65 74 3b 20 20 20 20   cellOffset;    
3180: 20 20 2f 2a 20 49 6e 64 65 78 20 69 6e 20 61 44    /* Index in aD
3190: 61 74 61 20 6f 66 20 66 69 72 73 74 20 63 65 6c  ata of first cel
31a0: 6c 20 70 6f 69 6e 74 65 72 20 2a 2f 0a 20 20 75  l pointer */.  u
31b0: 31 36 20 6e 46 72 65 65 3b 20 20 20 20 20 20 20  16 nFree;       
31c0: 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66      /* Number of
31d0: 20 66 72 65 65 20 62 79 74 65 73 20 6f 6e 20 74   free bytes on t
31e0: 68 65 20 70 61 67 65 20 2a 2f 0a 20 20 75 31 36  he page */.  u16
31f0: 20 6e 43 65 6c 6c 3b 20 20 20 20 20 20 20 20 20   nCell;         
3200: 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 63    /* Number of c
3210: 65 6c 6c 73 20 6f 6e 20 74 68 69 73 20 70 61 67  ells on this pag
3220: 65 2c 20 6c 6f 63 61 6c 20 61 6e 64 20 6f 76 66  e, local and ovf
3230: 6c 20 2a 2f 0a 20 20 75 31 36 20 6d 61 73 6b 50  l */.  u16 maskP
3240: 61 67 65 3b 20 20 20 20 20 20 20 20 2f 2a 20 4d  age;        /* M
3250: 61 73 6b 20 66 6f 72 20 70 61 67 65 20 6f 66 66  ask for page off
3260: 73 65 74 20 2a 2f 0a 20 20 73 74 72 75 63 74 20  set */.  struct 
3270: 5f 4f 76 66 6c 43 65 6c 6c 20 7b 20 20 20 2f 2a  _OvflCell {   /*
3280: 20 43 65 6c 6c 73 20 74 68 61 74 20 77 69 6c 6c   Cells that will
3290: 20 6e 6f 74 20 66 69 74 20 6f 6e 20 61 44 61 74   not fit on aDat
32a0: 61 5b 5d 20 2a 2f 0a 20 20 20 20 75 38 20 2a 70  a[] */.    u8 *p
32b0: 43 65 6c 6c 3b 20 20 20 20 20 20 20 20 20 20 2f  Cell;          /
32c0: 2a 20 50 6f 69 6e 74 65 72 73 20 74 6f 20 74 68  * Pointers to th
32d0: 65 20 62 6f 64 79 20 6f 66 20 74 68 65 20 6f 76  e body of the ov
32e0: 65 72 66 6c 6f 77 20 63 65 6c 6c 20 2a 2f 0a 20  erflow cell */. 
32f0: 20 20 20 75 31 36 20 69 64 78 3b 20 20 20 20 20     u16 idx;     
3300: 20 20 20 20 20 20 20 2f 2a 20 49 6e 73 65 72 74         /* Insert
3310: 20 74 68 69 73 20 63 65 6c 6c 20 62 65 66 6f 72   this cell befor
3320: 65 20 69 64 78 2d 74 68 20 6e 6f 6e 2d 6f 76 65  e idx-th non-ove
3330: 72 66 6c 6f 77 20 63 65 6c 6c 20 2a 2f 0a 20 20  rflow cell */.  
3340: 7d 20 61 4f 76 66 6c 5b 35 5d 3b 0a 20 20 42 74  } aOvfl[5];.  Bt
3350: 53 68 61 72 65 64 20 2a 70 42 74 3b 20 20 20 20  Shared *pBt;    
3360: 20 20 20 2f 2a 20 50 6f 69 6e 74 65 72 20 74 6f     /* Pointer to
3370: 20 42 74 53 68 61 72 65 64 20 74 68 61 74 20 74   BtShared that t
3380: 68 69 73 20 70 61 67 65 20 69 73 20 70 61 72 74  his page is part
3390: 20 6f 66 20 2a 2f 0a 20 20 75 38 20 2a 61 44 61   of */.  u8 *aDa
33a0: 74 61 3b 20 20 20 20 20 20 20 20 20 20 20 2f 2a  ta;           /*
33b0: 20 50 6f 69 6e 74 65 72 20 74 6f 20 64 69 73 6b   Pointer to disk
33c0: 20 69 6d 61 67 65 20 6f 66 20 74 68 65 20 70 61   image of the pa
33d0: 67 65 20 64 61 74 61 20 2a 2f 0a 20 20 44 62 50  ge data */.  DbP
33e0: 61 67 65 20 2a 70 44 62 50 61 67 65 3b 20 20 20  age *pDbPage;   
33f0: 20 20 2f 2a 20 50 61 67 65 72 20 70 61 67 65 20    /* Pager page 
3400: 68 61 6e 64 6c 65 20 2a 2f 0a 20 20 50 67 6e 6f  handle */.  Pgno
3410: 20 70 67 6e 6f 3b 20 20 20 20 20 20 20 20 20 20   pgno;          
3420: 20 2f 2a 20 50 61 67 65 20 6e 75 6d 62 65 72 20   /* Page number 
3430: 66 6f 72 20 74 68 69 73 20 70 61 67 65 20 2a 2f  for this page */
3440: 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 54 68 65 20 69  .};../*.** The i
3450: 6e 2d 6d 65 6d 6f 72 79 20 69 6d 61 67 65 20 6f  n-memory image o
3460: 66 20 61 20 64 69 73 6b 20 70 61 67 65 20 68 61  f a disk page ha
3470: 73 20 74 68 65 20 61 75 78 69 6c 69 61 72 79 20  s the auxiliary 
3480: 69 6e 66 6f 72 6d 61 74 69 6f 6e 20 61 70 70 65  information appe
3490: 6e 64 65 64 0a 2a 2a 20 74 6f 20 74 68 65 20 65  nded.** to the e
34a0: 6e 64 2e 20 20 45 58 54 52 41 5f 53 49 5a 45 20  nd.  EXTRA_SIZE 
34b0: 69 73 20 74 68 65 20 6e 75 6d 62 65 72 20 6f 66  is the number of
34c0: 20 62 79 74 65 73 20 6f 66 20 73 70 61 63 65 20   bytes of space 
34d0: 6e 65 65 64 65 64 20 74 6f 20 68 6f 6c 64 0a 2a  needed to hold.*
34e0: 2a 20 74 68 61 74 20 65 78 74 72 61 20 69 6e 66  * that extra inf
34f0: 6f 72 6d 61 74 69 6f 6e 2e 0a 2a 2f 0a 23 64 65  ormation..*/.#de
3500: 66 69 6e 65 20 45 58 54 52 41 5f 53 49 5a 45 20  fine EXTRA_SIZE 
3510: 73 69 7a 65 6f 66 28 4d 65 6d 50 61 67 65 29 0a  sizeof(MemPage).
3520: 0a 2f 2a 20 41 20 42 74 72 65 65 20 68 61 6e 64  ./* A Btree hand
3530: 6c 65 0a 2a 2a 0a 2a 2a 20 41 20 64 61 74 61 62  le.**.** A datab
3540: 61 73 65 20 63 6f 6e 6e 65 63 74 69 6f 6e 20 63  ase connection c
3550: 6f 6e 74 61 69 6e 73 20 61 20 70 6f 69 6e 74 65  ontains a pointe
3560: 72 20 74 6f 20 61 6e 20 69 6e 73 74 61 6e 63 65  r to an instance
3570: 20 6f 66 0a 2a 2a 20 74 68 69 73 20 6f 62 6a 65   of.** this obje
3580: 63 74 20 66 6f 72 20 65 76 65 72 79 20 64 61 74  ct for every dat
3590: 61 62 61 73 65 20 66 69 6c 65 20 74 68 61 74 20  abase file that 
35a0: 69 74 20 68 61 73 20 6f 70 65 6e 2e 20 20 54 68  it has open.  Th
35b0: 69 73 20 73 74 72 75 63 74 75 72 65 0a 2a 2a 20  is structure.** 
35c0: 69 73 20 6f 70 61 71 75 65 20 74 6f 20 74 68 65  is opaque to the
35d0: 20 64 61 74 61 62 61 73 65 20 63 6f 6e 6e 65 63   database connec
35e0: 74 69 6f 6e 2e 20 20 54 68 65 20 64 61 74 61 62  tion.  The datab
35f0: 61 73 65 20 63 6f 6e 6e 65 63 74 69 6f 6e 20 63  ase connection c
3600: 61 6e 6e 6f 74 0a 2a 2a 20 73 65 65 20 74 68 65  annot.** see the
3610: 20 69 6e 74 65 72 6e 61 6c 73 20 6f 66 20 74 68   internals of th
3620: 69 73 20 73 74 72 75 63 74 75 72 65 20 61 6e 64  is structure and
3630: 20 6f 6e 6c 79 20 64 65 61 6c 73 20 77 69 74 68   only deals with
3640: 20 70 6f 69 6e 74 65 72 73 20 74 6f 0a 2a 2a 20   pointers to.** 
3650: 74 68 69 73 20 73 74 72 75 63 74 75 72 65 2e 0a  this structure..
3660: 2a 2a 0a 2a 2a 20 46 6f 72 20 73 6f 6d 65 20 64  **.** For some d
3670: 61 74 61 62 61 73 65 20 66 69 6c 65 73 2c 20 74  atabase files, t
3680: 68 65 20 73 61 6d 65 20 75 6e 64 65 72 6c 79 69  he same underlyi
3690: 6e 67 20 64 61 74 61 62 61 73 65 20 63 61 63 68  ng database cach
36a0: 65 20 6d 69 67 68 74 20 62 65 20 0a 2a 2a 20 73  e might be .** s
36b0: 68 61 72 65 64 20 62 65 74 77 65 65 6e 20 6d 75  hared between mu
36c0: 6c 74 69 70 6c 65 20 63 6f 6e 6e 65 63 74 69 6f  ltiple connectio
36d0: 6e 73 2e 20 20 49 6e 20 74 68 61 74 20 63 61 73  ns.  In that cas
36e0: 65 2c 20 65 61 63 68 20 63 6f 6e 74 65 63 74 69  e, each contecti
36f0: 6f 6e 0a 2a 2a 20 68 61 73 20 69 74 20 6f 77 6e  on.** has it own
3700: 20 70 6f 69 6e 74 65 72 20 74 6f 20 74 68 69 73   pointer to this
3710: 20 6f 62 6a 65 63 74 2e 20 20 42 75 74 20 65 61   object.  But ea
3720: 63 68 20 69 6e 73 74 61 6e 63 65 20 6f 66 20 74  ch instance of t
3730: 68 69 73 20 6f 62 6a 65 63 74 0a 2a 2a 20 70 6f  his object.** po
3740: 69 6e 74 73 20 74 6f 20 74 68 65 20 73 61 6d 65  ints to the same
3750: 20 42 74 53 68 61 72 65 64 20 6f 62 6a 65 63 74   BtShared object
3760: 2e 20 20 54 68 65 20 64 61 74 61 62 61 73 65 20  .  The database 
3770: 63 61 63 68 65 20 61 6e 64 20 74 68 65 0a 2a 2a  cache and the.**
3780: 20 73 63 68 65 6d 61 20 61 73 73 6f 63 69 61 74   schema associat
3790: 65 64 20 77 69 74 68 20 74 68 65 20 64 61 74 61  ed with the data
37a0: 62 61 73 65 20 66 69 6c 65 20 61 72 65 20 61 6c  base file are al
37b0: 6c 20 63 6f 6e 74 61 69 6e 65 64 20 77 69 74 68  l contained with
37c0: 69 6e 0a 2a 2a 20 74 68 65 20 42 74 53 68 61 72  in.** the BtShar
37d0: 65 64 20 6f 62 6a 65 63 74 2e 0a 2a 2a 0a 2a 2a  ed object..**.**
37e0: 20 41 6c 6c 20 66 69 65 6c 64 73 20 69 6e 20 74   All fields in t
37f0: 68 69 73 20 73 74 72 75 63 74 75 72 65 20 61 72  his structure ar
3800: 65 20 61 63 63 65 73 73 65 64 20 75 6e 64 65 72  e accessed under
3810: 20 73 71 6c 69 74 65 33 2e 6d 75 74 65 78 2e 0a   sqlite3.mutex..
3820: 2a 2a 20 54 68 65 20 70 42 74 20 70 6f 69 6e 74  ** The pBt point
3830: 65 72 20 69 74 73 65 6c 66 20 6d 61 79 20 6e 6f  er itself may no
3840: 74 20 62 65 20 63 68 61 6e 67 65 64 20 77 68 69  t be changed whi
3850: 6c 65 20 74 68 65 72 65 20 65 78 69 73 74 73 20  le there exists 
3860: 63 75 72 73 6f 72 73 20 0a 2a 2a 20 69 6e 20 74  cursors .** in t
3870: 68 65 20 72 65 66 65 72 65 6e 63 65 64 20 42 74  he referenced Bt
3880: 53 68 61 72 65 64 20 74 68 61 74 20 70 6f 69 6e  Shared that poin
3890: 74 20 62 61 63 6b 20 74 6f 20 74 68 69 73 20 42  t back to this B
38a0: 74 72 65 65 20 73 69 6e 63 65 20 74 68 6f 73 65  tree since those
38b0: 0a 2a 2a 20 63 75 72 73 6f 72 73 20 68 61 76 65  .** cursors have
38c0: 20 74 6f 20 64 6f 20 67 6f 20 74 68 72 6f 75 67   to do go throug
38d0: 68 20 74 68 69 73 20 42 74 72 65 65 20 74 6f 20  h this Btree to 
38e0: 66 69 6e 64 20 74 68 65 69 72 20 42 74 53 68 61  find their BtSha
38f0: 72 65 64 20 61 6e 64 0a 2a 2a 20 74 68 65 79 20  red and.** they 
3900: 6f 66 74 65 6e 20 64 6f 20 73 6f 20 77 69 74 68  often do so with
3910: 6f 75 74 20 68 6f 6c 64 69 6e 67 20 73 71 6c 69  out holding sqli
3920: 74 65 33 2e 6d 75 74 65 78 2e 0a 2a 2f 0a 73 74  te3.mutex..*/.st
3930: 72 75 63 74 20 42 74 72 65 65 20 7b 0a 20 20 73  ruct Btree {.  s
3940: 71 6c 69 74 65 33 20 2a 64 62 3b 20 20 20 20 20  qlite3 *db;     
3950: 20 20 2f 2a 20 54 68 65 20 64 61 74 61 62 61 73    /* The databas
3960: 65 20 63 6f 6e 6e 65 63 74 69 6f 6e 20 68 6f 6c  e connection hol
3970: 64 69 6e 67 20 74 68 69 73 20 62 74 72 65 65 20  ding this btree 
3980: 2a 2f 0a 20 20 42 74 53 68 61 72 65 64 20 2a 70  */.  BtShared *p
3990: 42 74 3b 20 20 20 20 20 2f 2a 20 53 68 61 72 61  Bt;     /* Shara
39a0: 62 6c 65 20 63 6f 6e 74 65 6e 74 20 6f 66 20 74  ble content of t
39b0: 68 69 73 20 62 74 72 65 65 20 2a 2f 0a 20 20 75  his btree */.  u
39c0: 38 20 69 6e 54 72 61 6e 73 3b 20 20 20 20 20 20  8 inTrans;      
39d0: 20 20 2f 2a 20 54 52 41 4e 53 5f 4e 4f 4e 45 2c    /* TRANS_NONE,
39e0: 20 54 52 41 4e 53 5f 52 45 41 44 20 6f 72 20 54   TRANS_READ or T
39f0: 52 41 4e 53 5f 57 52 49 54 45 20 2a 2f 0a 20 20  RANS_WRITE */.  
3a00: 75 38 20 73 68 61 72 61 62 6c 65 3b 20 20 20 20  u8 sharable;    
3a10: 20 20 20 2f 2a 20 54 72 75 65 20 69 66 20 77 65     /* True if we
3a20: 20 63 61 6e 20 73 68 61 72 65 20 70 42 74 20 77   can share pBt w
3a30: 69 74 68 20 61 6e 6f 74 68 65 72 20 64 62 20 2a  ith another db *
3a40: 2f 0a 20 20 75 38 20 6c 6f 63 6b 65 64 3b 20 20  /.  u8 locked;  
3a50: 20 20 20 20 20 20 20 2f 2a 20 54 72 75 65 20 69         /* True i
3a60: 66 20 64 62 20 63 75 72 72 65 6e 74 6c 79 20 68  f db currently h
3a70: 61 73 20 70 42 74 20 6c 6f 63 6b 65 64 20 2a 2f  as pBt locked */
3a80: 0a 20 20 69 6e 74 20 77 61 6e 74 54 6f 4c 6f 63  .  int wantToLoc
3a90: 6b 3b 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20  k;    /* Number 
3aa0: 6f 66 20 6e 65 73 74 65 64 20 63 61 6c 6c 73 20  of nested calls 
3ab0: 74 6f 20 73 71 6c 69 74 65 33 42 74 72 65 65 45  to sqlite3BtreeE
3ac0: 6e 74 65 72 28 29 20 2a 2f 0a 20 20 69 6e 74 20  nter() */.  int 
3ad0: 6e 42 61 63 6b 75 70 3b 20 20 20 20 20 20 20 2f  nBackup;       /
3ae0: 2a 20 4e 75 6d 62 65 72 20 6f 66 20 62 61 63 6b  * Number of back
3af0: 75 70 20 6f 70 65 72 61 74 69 6f 6e 73 20 72 65  up operations re
3b00: 61 64 69 6e 67 20 74 68 69 73 20 62 74 72 65 65  ading this btree
3b10: 20 2a 2f 0a 20 20 42 74 72 65 65 20 2a 70 4e 65   */.  Btree *pNe
3b20: 78 74 3b 20 20 20 20 20 20 2f 2a 20 4c 69 73 74  xt;      /* List
3b30: 20 6f 66 20 6f 74 68 65 72 20 73 68 61 72 61 62   of other sharab
3b40: 6c 65 20 42 74 72 65 65 73 20 66 72 6f 6d 20 74  le Btrees from t
3b50: 68 65 20 73 61 6d 65 20 64 62 20 2a 2f 0a 20 20  he same db */.  
3b60: 42 74 72 65 65 20 2a 70 50 72 65 76 3b 20 20 20  Btree *pPrev;   
3b70: 20 20 20 2f 2a 20 42 61 63 6b 20 70 6f 69 6e 74     /* Back point
3b80: 65 72 20 6f 66 20 74 68 65 20 73 61 6d 65 20 6c  er of the same l
3b90: 69 73 74 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a  ist */.};../*.**
3ba0: 20 42 74 72 65 65 2e 69 6e 54 72 61 6e 73 20 6d   Btree.inTrans m
3bb0: 61 79 20 74 61 6b 65 20 6f 6e 65 20 6f 66 20 74  ay take one of t
3bc0: 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 20 76 61 6c  he following val
3bd0: 75 65 73 2e 0a 2a 2a 0a 2a 2a 20 49 66 20 74 68  ues..**.** If th
3be0: 65 20 73 68 61 72 65 64 2d 64 61 74 61 20 65 78  e shared-data ex
3bf0: 74 65 6e 73 69 6f 6e 20 69 73 20 65 6e 61 62 6c  tension is enabl
3c00: 65 64 2c 20 74 68 65 72 65 20 6d 61 79 20 62 65  ed, there may be
3c10: 20 6d 75 6c 74 69 70 6c 65 20 75 73 65 72 73 0a   multiple users.
3c20: 2a 2a 20 6f 66 20 74 68 65 20 42 74 72 65 65 20  ** of the Btree 
3c30: 73 74 72 75 63 74 75 72 65 2e 20 41 74 20 6d 6f  structure. At mo
3c40: 73 74 20 6f 6e 65 20 6f 66 20 74 68 65 73 65 20  st one of these 
3c50: 6d 61 79 20 6f 70 65 6e 20 61 20 77 72 69 74 65  may open a write
3c60: 20 74 72 61 6e 73 61 63 74 69 6f 6e 2c 0a 2a 2a   transaction,.**
3c70: 20 62 75 74 20 61 6e 79 20 6e 75 6d 62 65 72 20   but any number 
3c80: 6d 61 79 20 68 61 76 65 20 61 63 74 69 76 65 20  may have active 
3c90: 72 65 61 64 20 74 72 61 6e 73 61 63 74 69 6f 6e  read transaction
3ca0: 73 2e 0a 2a 2f 0a 23 64 65 66 69 6e 65 20 54 52  s..*/.#define TR
3cb0: 41 4e 53 5f 4e 4f 4e 45 20 20 30 0a 23 64 65 66  ANS_NONE  0.#def
3cc0: 69 6e 65 20 54 52 41 4e 53 5f 52 45 41 44 20 20  ine TRANS_READ  
3cd0: 31 0a 23 64 65 66 69 6e 65 20 54 52 41 4e 53 5f  1.#define TRANS_
3ce0: 57 52 49 54 45 20 32 0a 0a 2f 2a 0a 2a 2a 20 41  WRITE 2../*.** A
3cf0: 6e 20 69 6e 73 74 61 6e 63 65 20 6f 66 20 74 68  n instance of th
3d00: 69 73 20 6f 62 6a 65 63 74 20 72 65 70 72 65 73  is object repres
3d10: 65 6e 74 73 20 61 20 73 69 6e 67 6c 65 20 64 61  ents a single da
3d20: 74 61 62 61 73 65 20 66 69 6c 65 2e 0a 2a 2a 20  tabase file..** 
3d30: 0a 2a 2a 20 41 20 73 69 6e 67 6c 65 20 64 61 74  .** A single dat
3d40: 61 62 61 73 65 20 66 69 6c 65 20 63 61 6e 20 62  abase file can b
3d50: 65 20 69 6e 20 75 73 65 20 61 73 20 74 68 65 20  e in use as the 
3d60: 73 61 6d 65 20 74 69 6d 65 20 62 79 20 74 77 6f  same time by two
3d70: 0a 2a 2a 20 6f 72 20 6d 6f 72 65 20 64 61 74 61  .** or more data
3d80: 62 61 73 65 20 63 6f 6e 6e 65 63 74 69 6f 6e 73  base connections
3d90: 2e 20 20 57 68 65 6e 20 74 77 6f 20 6f 72 20 6d  .  When two or m
3da0: 6f 72 65 20 63 6f 6e 6e 65 63 74 69 6f 6e 73 20  ore connections 
3db0: 61 72 65 0a 2a 2a 20 73 68 61 72 69 6e 67 20 74  are.** sharing t
3dc0: 68 65 20 73 61 6d 65 20 64 61 74 61 62 61 73 65  he same database
3dd0: 20 66 69 6c 65 2c 20 65 61 63 68 20 63 6f 6e 6e   file, each conn
3de0: 65 63 74 69 6f 6e 20 68 61 73 20 69 74 20 6f 77  ection has it ow
3df0: 6e 0a 2a 2a 20 70 72 69 76 61 74 65 20 42 74 72  n.** private Btr
3e00: 65 65 20 6f 62 6a 65 63 74 20 66 6f 72 20 74 68  ee object for th
3e10: 65 20 66 69 6c 65 20 61 6e 64 20 65 61 63 68 20  e file and each 
3e20: 6f 66 20 74 68 6f 73 65 20 42 74 72 65 65 73 20  of those Btrees 
3e30: 70 6f 69 6e 74 73 0a 2a 2a 20 74 6f 20 74 68 69  points.** to thi
3e40: 73 20 6f 6e 65 20 42 74 53 68 61 72 65 64 20 6f  s one BtShared o
3e50: 62 6a 65 63 74 2e 20 20 42 74 53 68 61 72 65 64  bject.  BtShared
3e60: 2e 6e 52 65 66 20 69 73 20 74 68 65 20 6e 75 6d  .nRef is the num
3e70: 62 65 72 20 6f 66 0a 2a 2a 20 63 6f 6e 6e 65 63  ber of.** connec
3e80: 74 69 6f 6e 73 20 63 75 72 72 65 6e 74 6c 79 20  tions currently 
3e90: 73 68 61 72 69 6e 67 20 74 68 69 73 20 64 61 74  sharing this dat
3ea0: 61 62 61 73 65 20 66 69 6c 65 2e 0a 2a 2a 0a 2a  abase file..**.*
3eb0: 2a 20 46 69 65 6c 64 73 20 69 6e 20 74 68 69 73  * Fields in this
3ec0: 20 73 74 72 75 63 74 75 72 65 20 61 72 65 20 61   structure are a
3ed0: 63 63 65 73 73 65 64 20 75 6e 64 65 72 20 74 68  ccessed under th
3ee0: 65 20 42 74 53 68 61 72 65 64 2e 6d 75 74 65 78  e BtShared.mutex
3ef0: 0a 2a 2a 20 6d 75 74 65 78 2c 20 65 78 63 65 70  .** mutex, excep
3f00: 74 20 66 6f 72 20 6e 52 65 66 20 61 6e 64 20 70  t for nRef and p
3f10: 4e 65 78 74 20 77 68 69 63 68 20 61 72 65 20 61  Next which are a
3f20: 63 63 65 73 73 65 64 20 75 6e 64 65 72 20 74 68  ccessed under th
3f30: 65 0a 2a 2a 20 67 6c 6f 62 61 6c 20 53 51 4c 49  e.** global SQLI
3f40: 54 45 5f 4d 55 54 45 58 5f 53 54 41 54 49 43 5f  TE_MUTEX_STATIC_
3f50: 4d 41 53 54 45 52 20 6d 75 74 65 78 2e 20 20 54  MASTER mutex.  T
3f60: 68 65 20 70 50 61 67 65 72 20 66 69 65 6c 64 0a  he pPager field.
3f70: 2a 2a 20 6d 61 79 20 6e 6f 74 20 62 65 20 6d 6f  ** may not be mo
3f80: 64 69 66 69 65 64 20 6f 6e 63 65 20 69 74 20 69  dified once it i
3f90: 73 20 69 6e 69 74 69 61 6c 6c 79 20 73 65 74 20  s initially set 
3fa0: 61 73 20 6c 6f 6e 67 20 61 73 20 6e 52 65 66 3e  as long as nRef>
3fb0: 30 2e 0a 2a 2a 20 54 68 65 20 70 53 63 68 65 6d  0..** The pSchem
3fc0: 61 20 66 69 65 6c 64 20 6d 61 79 20 62 65 20 73  a field may be s
3fd0: 65 74 20 6f 6e 63 65 20 75 6e 64 65 72 20 42 74  et once under Bt
3fe0: 53 68 61 72 65 64 2e 6d 75 74 65 78 20 61 6e 64  Shared.mutex and
3ff0: 0a 2a 2a 20 74 68 65 72 65 61 66 74 65 72 20 69  .** thereafter i
4000: 73 20 75 6e 63 68 61 6e 67 65 64 20 61 73 20 6c  s unchanged as l
4010: 6f 6e 67 20 61 73 20 6e 52 65 66 3e 30 2e 0a 2a  ong as nRef>0..*
4020: 2f 0a 73 74 72 75 63 74 20 42 74 53 68 61 72 65  /.struct BtShare
4030: 64 20 7b 0a 20 20 50 61 67 65 72 20 2a 70 50 61  d {.  Pager *pPa
4040: 67 65 72 3b 20 20 20 20 20 20 20 20 2f 2a 20 54  ger;        /* T
4050: 68 65 20 70 61 67 65 20 63 61 63 68 65 20 2a 2f  he page cache */
4060: 0a 20 20 73 71 6c 69 74 65 33 20 2a 64 62 3b 20  .  sqlite3 *db; 
4070: 20 20 20 20 20 20 20 20 20 2f 2a 20 44 61 74 61           /* Data
4080: 62 61 73 65 20 63 6f 6e 6e 65 63 74 69 6f 6e 20  base connection 
4090: 63 75 72 72 65 6e 74 6c 79 20 75 73 69 6e 67 20  currently using 
40a0: 74 68 69 73 20 42 74 72 65 65 20 2a 2f 0a 20 20  this Btree */.  
40b0: 42 74 43 75 72 73 6f 72 20 2a 70 43 75 72 73 6f  BtCursor *pCurso
40c0: 72 3b 20 20 20 20 2f 2a 20 41 20 6c 69 73 74 20  r;    /* A list 
40d0: 6f 66 20 61 6c 6c 20 6f 70 65 6e 20 63 75 72 73  of all open curs
40e0: 6f 72 73 20 2a 2f 0a 20 20 4d 65 6d 50 61 67 65  ors */.  MemPage
40f0: 20 2a 70 50 61 67 65 31 3b 20 20 20 20 20 20 2f   *pPage1;      /
4100: 2a 20 46 69 72 73 74 20 70 61 67 65 20 6f 66 20  * First page of 
4110: 74 68 65 20 64 61 74 61 62 61 73 65 20 2a 2f 0a  the database */.
4120: 20 20 75 38 20 69 6e 53 74 6d 74 3b 20 20 20 20    u8 inStmt;    
4130: 20 20 20 20 20 20 20 20 2f 2a 20 54 72 75 65 20          /* True 
4140: 69 66 20 77 65 20 61 72 65 20 69 6e 20 61 20 73  if we are in a s
4150: 74 61 74 65 6d 65 6e 74 20 73 75 62 74 72 61 6e  tatement subtran
4160: 73 61 63 74 69 6f 6e 20 2a 2f 0a 20 20 75 38 20  saction */.  u8 
4170: 72 65 61 64 4f 6e 6c 79 3b 20 20 20 20 20 20 20  readOnly;       
4180: 20 20 20 2f 2a 20 54 72 75 65 20 69 66 20 74 68     /* True if th
4190: 65 20 75 6e 64 65 72 6c 79 69 6e 67 20 66 69 6c  e underlying fil
41a0: 65 20 69 73 20 72 65 61 64 6f 6e 6c 79 20 2a 2f  e is readonly */
41b0: 0a 20 20 75 38 20 70 61 67 65 53 69 7a 65 46 69  .  u8 pageSizeFi
41c0: 78 65 64 3b 20 20 20 20 20 2f 2a 20 54 72 75 65  xed;     /* True
41d0: 20 69 66 20 74 68 65 20 70 61 67 65 20 73 69 7a   if the page siz
41e0: 65 20 63 61 6e 20 6e 6f 20 6c 6f 6e 67 65 72 20  e can no longer 
41f0: 62 65 20 63 68 61 6e 67 65 64 20 2a 2f 0a 23 69  be changed */.#i
4200: 66 6e 64 65 66 20 53 51 4c 49 54 45 5f 4f 4d 49  fndef SQLITE_OMI
4210: 54 5f 41 55 54 4f 56 41 43 55 55 4d 0a 20 20 75  T_AUTOVACUUM.  u
4220: 38 20 61 75 74 6f 56 61 63 75 75 6d 3b 20 20 20  8 autoVacuum;   
4230: 20 20 20 20 20 2f 2a 20 54 72 75 65 20 69 66 20       /* True if 
4240: 61 75 74 6f 2d 76 61 63 75 75 6d 20 69 73 20 65  auto-vacuum is e
4250: 6e 61 62 6c 65 64 20 2a 2f 0a 20 20 75 38 20 69  nabled */.  u8 i
4260: 6e 63 72 56 61 63 75 75 6d 3b 20 20 20 20 20 20  ncrVacuum;      
4270: 20 20 2f 2a 20 54 72 75 65 20 69 66 20 69 6e 63    /* True if inc
4280: 72 2d 76 61 63 75 75 6d 20 69 73 20 65 6e 61 62  r-vacuum is enab
4290: 6c 65 64 20 2a 2f 0a 23 65 6e 64 69 66 0a 20 20  led */.#endif.  
42a0: 75 31 36 20 70 61 67 65 53 69 7a 65 3b 20 20 20  u16 pageSize;   
42b0: 20 20 20 20 20 20 2f 2a 20 54 6f 74 61 6c 20 6e        /* Total n
42c0: 75 6d 62 65 72 20 6f 66 20 62 79 74 65 73 20 6f  umber of bytes o
42d0: 6e 20 61 20 70 61 67 65 20 2a 2f 0a 20 20 75 31  n a page */.  u1
42e0: 36 20 75 73 61 62 6c 65 53 69 7a 65 3b 20 20 20  6 usableSize;   
42f0: 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66      /* Number of
4300: 20 75 73 61 62 6c 65 20 62 79 74 65 73 20 6f 6e   usable bytes on
4310: 20 65 61 63 68 20 70 61 67 65 20 2a 2f 0a 20 20   each page */.  
4320: 75 31 36 20 6d 61 78 4c 6f 63 61 6c 3b 20 20 20  u16 maxLocal;   
4330: 20 20 20 20 20 20 2f 2a 20 4d 61 78 69 6d 75 6d        /* Maximum
4340: 20 6c 6f 63 61 6c 20 70 61 79 6c 6f 61 64 20 69   local payload i
4350: 6e 20 6e 6f 6e 2d 4c 45 41 46 44 41 54 41 20 74  n non-LEAFDATA t
4360: 61 62 6c 65 73 20 2a 2f 0a 20 20 75 31 36 20 6d  ables */.  u16 m
4370: 69 6e 4c 6f 63 61 6c 3b 20 20 20 20 20 20 20 20  inLocal;        
4380: 20 2f 2a 20 4d 69 6e 69 6d 75 6d 20 6c 6f 63 61   /* Minimum loca
4390: 6c 20 70 61 79 6c 6f 61 64 20 69 6e 20 6e 6f 6e  l payload in non
43a0: 2d 4c 45 41 46 44 41 54 41 20 74 61 62 6c 65 73  -LEAFDATA tables
43b0: 20 2a 2f 0a 20 20 75 31 36 20 6d 61 78 4c 65 61   */.  u16 maxLea
43c0: 66 3b 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4d  f;          /* M
43d0: 61 78 69 6d 75 6d 20 6c 6f 63 61 6c 20 70 61 79  aximum local pay
43e0: 6c 6f 61 64 20 69 6e 20 61 20 4c 45 41 46 44 41  load in a LEAFDA
43f0: 54 41 20 74 61 62 6c 65 20 2a 2f 0a 20 20 75 31  TA table */.  u1
4400: 36 20 6d 69 6e 4c 65 61 66 3b 20 20 20 20 20 20  6 minLeaf;      
4410: 20 20 20 20 2f 2a 20 4d 69 6e 69 6d 75 6d 20 6c      /* Minimum l
4420: 6f 63 61 6c 20 70 61 79 6c 6f 61 64 20 69 6e 20  ocal payload in 
4430: 61 20 4c 45 41 46 44 41 54 41 20 74 61 62 6c 65  a LEAFDATA table
4440: 20 2a 2f 0a 20 20 75 38 20 69 6e 54 72 61 6e 73   */.  u8 inTrans
4450: 61 63 74 69 6f 6e 3b 20 20 20 20 20 2f 2a 20 54  action;     /* T
4460: 72 61 6e 73 61 63 74 69 6f 6e 20 73 74 61 74 65  ransaction state
4470: 20 2a 2f 0a 20 20 69 6e 74 20 6e 54 72 61 6e 73   */.  int nTrans
4480: 61 63 74 69 6f 6e 3b 20 20 20 20 20 2f 2a 20 4e  action;     /* N
4490: 75 6d 62 65 72 20 6f 66 20 6f 70 65 6e 20 74 72  umber of open tr
44a0: 61 6e 73 61 63 74 69 6f 6e 73 20 28 72 65 61 64  ansactions (read
44b0: 20 2b 20 77 72 69 74 65 29 20 2a 2f 0a 20 20 76   + write) */.  v
44c0: 6f 69 64 20 2a 70 53 63 68 65 6d 61 3b 20 20 20  oid *pSchema;   
44d0: 20 20 20 20 20 2f 2a 20 50 6f 69 6e 74 65 72 20       /* Pointer 
44e0: 74 6f 20 73 70 61 63 65 20 61 6c 6c 6f 63 61 74  to space allocat
44f0: 65 64 20 62 79 20 73 71 6c 69 74 65 33 42 74 72  ed by sqlite3Btr
4500: 65 65 53 63 68 65 6d 61 28 29 20 2a 2f 0a 20 20  eeSchema() */.  
4510: 76 6f 69 64 20 28 2a 78 46 72 65 65 53 63 68 65  void (*xFreeSche
4520: 6d 61 29 28 76 6f 69 64 2a 29 3b 20 20 2f 2a 20  ma)(void*);  /* 
4530: 44 65 73 74 72 75 63 74 6f 72 20 66 6f 72 20 42  Destructor for B
4540: 74 53 68 61 72 65 64 2e 70 53 63 68 65 6d 61 20  tShared.pSchema 
4550: 2a 2f 0a 20 20 73 71 6c 69 74 65 33 5f 6d 75 74  */.  sqlite3_mut
4560: 65 78 20 2a 6d 75 74 65 78 3b 20 2f 2a 20 4e 6f  ex *mutex; /* No
4570: 6e 2d 72 65 63 75 72 73 69 76 65 20 6d 75 74 65  n-recursive mute
4580: 78 20 72 65 71 75 69 72 65 64 20 74 6f 20 61 63  x required to ac
4590: 63 65 73 73 20 74 68 69 73 20 73 74 72 75 63 74  cess this struct
45a0: 20 2a 2f 0a 20 20 42 69 74 76 65 63 20 2a 70 48   */.  Bitvec *pH
45b0: 61 73 43 6f 6e 74 65 6e 74 3b 20 20 2f 2a 20 53  asContent;  /* S
45c0: 65 74 20 6f 66 20 70 61 67 65 73 20 6d 6f 76 65  et of pages move
45d0: 64 20 74 6f 20 66 72 65 65 2d 6c 69 73 74 20 74  d to free-list t
45e0: 68 69 73 20 74 72 61 6e 73 61 63 74 69 6f 6e 20  his transaction 
45f0: 2a 2f 0a 23 69 66 6e 64 65 66 20 53 51 4c 49 54  */.#ifndef SQLIT
4600: 45 5f 4f 4d 49 54 5f 53 48 41 52 45 44 5f 43 41  E_OMIT_SHARED_CA
4610: 43 48 45 0a 20 20 69 6e 74 20 6e 52 65 66 3b 20  CHE.  int nRef; 
4620: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4e              /* N
4630: 75 6d 62 65 72 20 6f 66 20 72 65 66 65 72 65 6e  umber of referen
4640: 63 65 73 20 74 6f 20 74 68 69 73 20 73 74 72 75  ces to this stru
4650: 63 74 75 72 65 20 2a 2f 0a 20 20 42 74 53 68 61  cture */.  BtSha
4660: 72 65 64 20 2a 70 4e 65 78 74 3b 20 20 20 20 20  red *pNext;     
4670: 20 2f 2a 20 4e 65 78 74 20 6f 6e 20 61 20 6c 69   /* Next on a li
4680: 73 74 20 6f 66 20 73 68 61 72 61 62 6c 65 20 42  st of sharable B
4690: 74 53 68 61 72 65 64 20 73 74 72 75 63 74 73 20  tShared structs 
46a0: 2a 2f 0a 20 20 42 74 4c 6f 63 6b 20 2a 70 4c 6f  */.  BtLock *pLo
46b0: 63 6b 3b 20 20 20 20 20 20 20 20 2f 2a 20 4c 69  ck;        /* Li
46c0: 73 74 20 6f 66 20 6c 6f 63 6b 73 20 68 65 6c 64  st of locks held
46d0: 20 6f 6e 20 74 68 69 73 20 73 68 61 72 65 64 2d   on this shared-
46e0: 62 74 72 65 65 20 73 74 72 75 63 74 20 2a 2f 0a  btree struct */.
46f0: 20 20 42 74 72 65 65 20 2a 70 45 78 63 6c 75 73    Btree *pExclus
4700: 69 76 65 3b 20 20 20 20 2f 2a 20 42 74 72 65 65  ive;    /* Btree
4710: 20 77 69 74 68 20 61 6e 20 45 58 43 4c 55 53 49   with an EXCLUSI
4720: 56 45 20 6c 6f 63 6b 20 6f 6e 20 74 68 65 20 77  VE lock on the w
4730: 68 6f 6c 65 20 64 62 20 2a 2f 0a 23 65 6e 64 69  hole db */.#endi
4740: 66 0a 20 20 75 38 20 2a 70 54 6d 70 53 70 61 63  f.  u8 *pTmpSpac
4750: 65 3b 20 20 20 20 20 20 20 20 2f 2a 20 42 74 53  e;        /* BtS
4760: 68 61 72 65 64 2e 70 61 67 65 53 69 7a 65 20 62  hared.pageSize b
4770: 79 74 65 73 20 6f 66 20 73 70 61 63 65 20 66 6f  ytes of space fo
4780: 72 20 74 6d 70 20 75 73 65 20 2a 2f 0a 7d 3b 0a  r tmp use */.};.
4790: 0a 2f 2a 0a 2a 2a 20 41 6e 20 69 6e 73 74 61 6e  ./*.** An instan
47a0: 63 65 20 6f 66 20 74 68 65 20 66 6f 6c 6c 6f 77  ce of the follow
47b0: 69 6e 67 20 73 74 72 75 63 74 75 72 65 20 69 73  ing structure is
47c0: 20 75 73 65 64 20 74 6f 20 68 6f 6c 64 20 69 6e   used to hold in
47d0: 66 6f 72 6d 61 74 69 6f 6e 0a 2a 2a 20 61 62 6f  formation.** abo
47e0: 75 74 20 61 20 63 65 6c 6c 2e 20 20 54 68 65 20  ut a cell.  The 
47f0: 70 61 72 73 65 43 65 6c 6c 50 74 72 28 29 20 66  parseCellPtr() f
4800: 75 6e 63 74 69 6f 6e 20 66 69 6c 6c 73 20 69 6e  unction fills in
4810: 20 74 68 69 73 20 73 74 72 75 63 74 75 72 65 0a   this structure.
4820: 2a 2a 20 62 61 73 65 64 20 6f 6e 20 69 6e 66 6f  ** based on info
4830: 72 6d 61 74 69 6f 6e 20 65 78 74 72 61 63 74 20  rmation extract 
4840: 66 72 6f 6d 20 74 68 65 20 72 61 77 20 64 69 73  from the raw dis
4850: 6b 20 70 61 67 65 2e 0a 2a 2f 0a 74 79 70 65 64  k page..*/.typed
4860: 65 66 20 73 74 72 75 63 74 20 43 65 6c 6c 49 6e  ef struct CellIn
4870: 66 6f 20 43 65 6c 6c 49 6e 66 6f 3b 0a 73 74 72  fo CellInfo;.str
4880: 75 63 74 20 43 65 6c 6c 49 6e 66 6f 20 7b 0a 20  uct CellInfo {. 
4890: 20 75 38 20 2a 70 43 65 6c 6c 3b 20 20 20 20 20   u8 *pCell;     
48a0: 2f 2a 20 50 6f 69 6e 74 65 72 20 74 6f 20 74 68  /* Pointer to th
48b0: 65 20 73 74 61 72 74 20 6f 66 20 63 65 6c 6c 20  e start of cell 
48c0: 63 6f 6e 74 65 6e 74 20 2a 2f 0a 20 20 69 36 34  content */.  i64
48d0: 20 6e 4b 65 79 3b 20 20 20 20 20 20 2f 2a 20 54   nKey;      /* T
48e0: 68 65 20 6b 65 79 20 66 6f 72 20 49 4e 54 4b 45  he key for INTKE
48f0: 59 20 74 61 62 6c 65 73 2c 20 6f 72 20 6e 75 6d  Y tables, or num
4900: 62 65 72 20 6f 66 20 62 79 74 65 73 20 69 6e 20  ber of bytes in 
4910: 6b 65 79 20 2a 2f 0a 20 20 75 33 32 20 6e 44 61  key */.  u32 nDa
4920: 74 61 3b 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65  ta;     /* Numbe
4930: 72 20 6f 66 20 62 79 74 65 73 20 6f 66 20 64 61  r of bytes of da
4940: 74 61 20 2a 2f 0a 20 20 75 33 32 20 6e 50 61 79  ta */.  u32 nPay
4950: 6c 6f 61 64 3b 20 20 2f 2a 20 54 6f 74 61 6c 20  load;  /* Total 
4960: 61 6d 6f 75 6e 74 20 6f 66 20 70 61 79 6c 6f 61  amount of payloa
4970: 64 20 2a 2f 0a 20 20 75 31 36 20 6e 48 65 61 64  d */.  u16 nHead
4980: 65 72 3b 20 20 20 2f 2a 20 53 69 7a 65 20 6f 66  er;   /* Size of
4990: 20 74 68 65 20 63 65 6c 6c 20 63 6f 6e 74 65 6e   the cell conten
49a0: 74 20 68 65 61 64 65 72 20 69 6e 20 62 79 74 65  t header in byte
49b0: 73 20 2a 2f 0a 20 20 75 31 36 20 6e 4c 6f 63 61  s */.  u16 nLoca
49c0: 6c 3b 20 20 20 20 2f 2a 20 41 6d 6f 75 6e 74 20  l;    /* Amount 
49d0: 6f 66 20 70 61 79 6c 6f 61 64 20 68 65 6c 64 20  of payload held 
49e0: 6c 6f 63 61 6c 6c 79 20 2a 2f 0a 20 20 75 31 36  locally */.  u16
49f0: 20 69 4f 76 65 72 66 6c 6f 77 3b 20 2f 2a 20 4f   iOverflow; /* O
4a00: 66 66 73 65 74 20 74 6f 20 6f 76 65 72 66 6c 6f  ffset to overflo
4a10: 77 20 70 61 67 65 20 6e 75 6d 62 65 72 2e 20 20  w page number.  
4a20: 5a 65 72 6f 20 69 66 20 6e 6f 20 6f 76 65 72 66  Zero if no overf
4a30: 6c 6f 77 20 2a 2f 0a 20 20 75 31 36 20 6e 53 69  low */.  u16 nSi
4a40: 7a 65 3b 20 20 20 20 20 2f 2a 20 53 69 7a 65 20  ze;     /* Size 
4a50: 6f 66 20 74 68 65 20 63 65 6c 6c 20 63 6f 6e 74  of the cell cont
4a60: 65 6e 74 20 6f 6e 20 74 68 65 20 6d 61 69 6e 20  ent on the main 
4a70: 62 2d 74 72 65 65 20 70 61 67 65 20 2a 2f 0a 7d  b-tree page */.}
4a80: 3b 0a 0a 2f 2a 0a 2a 2a 20 4d 61 78 69 6d 75 6d  ;../*.** Maximum
4a90: 20 64 65 70 74 68 20 6f 66 20 61 6e 20 53 51 4c   depth of an SQL
4aa0: 69 74 65 20 42 2d 54 72 65 65 20 73 74 72 75 63  ite B-Tree struc
4ab0: 74 75 72 65 2e 20 41 6e 79 20 42 2d 54 72 65 65  ture. Any B-Tree
4ac0: 20 64 65 65 70 65 72 20 74 68 61 6e 0a 2a 2a 20   deeper than.** 
4ad0: 74 68 69 73 20 77 69 6c 6c 20 62 65 20 64 65 63  this will be dec
4ae0: 6c 61 72 65 64 20 63 6f 72 72 75 70 74 2e 20 54  lared corrupt. T
4af0: 68 69 73 20 76 61 6c 75 65 20 69 73 20 63 61 6c  his value is cal
4b00: 63 75 6c 61 74 65 64 20 62 61 73 65 64 20 6f 6e  culated based on
4b10: 20 61 0a 2a 2a 20 6d 61 78 69 6d 75 6d 20 64 61   a.** maximum da
4b20: 74 61 62 61 73 65 20 73 69 7a 65 20 6f 66 20 32  tabase size of 2
4b30: 5e 33 31 20 70 61 67 65 73 20 61 20 6d 69 6e 69  ^31 pages a mini
4b40: 6d 75 6d 20 66 61 6e 6f 75 74 20 6f 66 20 32 20  mum fanout of 2 
4b50: 66 6f 72 20 61 0a 2a 2a 20 72 6f 6f 74 2d 6e 6f  for a.** root-no
4b60: 64 65 20 61 6e 64 20 33 20 66 6f 72 20 61 6c 6c  de and 3 for all
4b70: 20 6f 74 68 65 72 20 69 6e 74 65 72 6e 61 6c 20   other internal 
4b80: 6e 6f 64 65 73 2e 0a 2a 2a 0a 2a 2a 20 49 66 20  nodes..**.** If 
4b90: 61 20 74 72 65 65 20 74 68 61 74 20 61 70 70 65  a tree that appe
4ba0: 61 72 73 20 74 6f 20 62 65 20 74 61 6c 6c 65 72  ars to be taller
4bb0: 20 74 68 61 6e 20 74 68 69 73 20 69 73 20 65 6e   than this is en
4bc0: 63 6f 75 6e 74 65 72 65 64 2c 20 69 74 20 69 73  countered, it is
4bd0: 0a 2a 2a 20 61 73 73 75 6d 65 64 20 74 68 61 74  .** assumed that
4be0: 20 74 68 65 20 64 61 74 61 62 61 73 65 20 69 73   the database is
4bf0: 20 63 6f 72 72 75 70 74 2e 0a 2a 2f 0a 23 64 65   corrupt..*/.#de
4c00: 66 69 6e 65 20 42 54 43 55 52 53 4f 52 5f 4d 41  fine BTCURSOR_MA
4c10: 58 5f 44 45 50 54 48 20 32 30 0a 0a 2f 2a 0a 2a  X_DEPTH 20../*.*
4c20: 2a 20 41 20 63 75 72 73 6f 72 20 69 73 20 61 20  * A cursor is a 
4c30: 70 6f 69 6e 74 65 72 20 74 6f 20 61 20 70 61 72  pointer to a par
4c40: 74 69 63 75 6c 61 72 20 65 6e 74 72 79 20 77 69  ticular entry wi
4c50: 74 68 69 6e 20 61 20 70 61 72 74 69 63 75 6c 61  thin a particula
4c60: 72 0a 2a 2a 20 62 2d 74 72 65 65 20 77 69 74 68  r.** b-tree with
4c70: 69 6e 20 61 20 64 61 74 61 62 61 73 65 20 66 69  in a database fi
4c80: 6c 65 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 65 6e  le..**.** The en
4c90: 74 72 79 20 69 73 20 69 64 65 6e 74 69 66 69 65  try is identifie
4ca0: 64 20 62 79 20 69 74 73 20 4d 65 6d 50 61 67 65  d by its MemPage
4cb0: 20 61 6e 64 20 74 68 65 20 69 6e 64 65 78 20 69   and the index i
4cc0: 6e 0a 2a 2a 20 4d 65 6d 50 61 67 65 2e 61 43 65  n.** MemPage.aCe
4cd0: 6c 6c 5b 5d 20 6f 66 20 74 68 65 20 65 6e 74 72  ll[] of the entr
4ce0: 79 2e 0a 2a 2a 0a 2a 2a 20 57 68 65 6e 20 61 20  y..**.** When a 
4cf0: 73 69 6e 67 6c 65 20 64 61 74 61 62 61 73 65 20  single database 
4d00: 66 69 6c 65 20 63 61 6e 20 73 68 61 72 65 64 20  file can shared 
4d10: 62 79 20 74 77 6f 20 6d 6f 72 65 20 64 61 74 61  by two more data
4d20: 62 61 73 65 20 63 6f 6e 6e 65 63 74 69 6f 6e 73  base connections
4d30: 2c 0a 2a 2a 20 62 75 74 20 63 75 72 73 6f 72 73  ,.** but cursors
4d40: 20 63 61 6e 6e 6f 74 20 62 65 20 73 68 61 72 65   cannot be share
4d50: 64 2e 20 20 45 61 63 68 20 63 75 72 73 6f 72 20  d.  Each cursor 
4d60: 69 73 20 61 73 73 6f 63 69 61 74 65 64 20 77 69  is associated wi
4d70: 74 68 20 61 0a 2a 2a 20 70 61 72 74 69 63 75 6c  th a.** particul
4d80: 61 72 20 64 61 74 61 62 61 73 65 20 63 6f 6e 6e  ar database conn
4d90: 65 63 74 69 6f 6e 20 69 64 65 6e 74 69 66 69 65  ection identifie
4da0: 64 20 42 74 43 75 72 73 6f 72 2e 70 42 74 72 65  d BtCursor.pBtre
4db0: 65 2e 64 62 2e 0a 2a 2a 0a 2a 2a 20 46 69 65 6c  e.db..**.** Fiel
4dc0: 64 73 20 69 6e 20 74 68 69 73 20 73 74 72 75 63  ds in this struc
4dd0: 74 75 72 65 20 61 72 65 20 61 63 63 65 73 73 65  ture are accesse
4de0: 64 20 75 6e 64 65 72 20 74 68 65 20 42 74 53 68  d under the BtSh
4df0: 61 72 65 64 2e 6d 75 74 65 78 0a 2a 2a 20 66 6f  ared.mutex.** fo
4e00: 75 6e 64 20 61 74 20 73 65 6c 66 2d 3e 70 42 74  und at self->pBt
4e10: 2d 3e 6d 75 74 65 78 2e 20 0a 2a 2f 0a 73 74 72  ->mutex. .*/.str
4e20: 75 63 74 20 42 74 43 75 72 73 6f 72 20 7b 0a 20  uct BtCursor {. 
4e30: 20 42 74 72 65 65 20 2a 70 42 74 72 65 65 3b 20   Btree *pBtree; 
4e40: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 54 68             /* Th
4e50: 65 20 42 74 72 65 65 20 74 6f 20 77 68 69 63 68  e Btree to which
4e60: 20 74 68 69 73 20 63 75 72 73 6f 72 20 62 65 6c   this cursor bel
4e70: 6f 6e 67 73 20 2a 2f 0a 20 20 42 74 53 68 61 72  ongs */.  BtShar
4e80: 65 64 20 2a 70 42 74 3b 20 20 20 20 20 20 20 20  ed *pBt;        
4e90: 20 20 20 20 2f 2a 20 54 68 65 20 42 74 53 68 61      /* The BtSha
4ea0: 72 65 64 20 74 68 69 73 20 63 75 72 73 6f 72 20  red this cursor 
4eb0: 70 6f 69 6e 74 73 20 74 6f 20 2a 2f 0a 20 20 42  points to */.  B
4ec0: 74 43 75 72 73 6f 72 20 2a 70 4e 65 78 74 2c 20  tCursor *pNext, 
4ed0: 2a 70 50 72 65 76 3b 20 20 2f 2a 20 46 6f 72 6d  *pPrev;  /* Form
4ee0: 73 20 61 20 6c 69 6e 6b 65 64 20 6c 69 73 74 20  s a linked list 
4ef0: 6f 66 20 61 6c 6c 20 63 75 72 73 6f 72 73 20 2a  of all cursors *
4f00: 2f 0a 20 20 73 74 72 75 63 74 20 4b 65 79 49 6e  /.  struct KeyIn
4f10: 66 6f 20 2a 70 4b 65 79 49 6e 66 6f 3b 20 2f 2a  fo *pKeyInfo; /*
4f20: 20 41 72 67 75 6d 65 6e 74 20 70 61 73 73 65 64   Argument passed
4f30: 20 74 6f 20 63 6f 6d 70 61 72 69 73 6f 6e 20 66   to comparison f
4f40: 75 6e 63 74 69 6f 6e 20 2a 2f 0a 20 20 50 67 6e  unction */.  Pgn
4f50: 6f 20 70 67 6e 6f 52 6f 6f 74 3b 20 20 20 20 20  o pgnoRoot;     
4f60: 20 20 20 20 20 20 20 2f 2a 20 54 68 65 20 72 6f         /* The ro
4f70: 6f 74 20 70 61 67 65 20 6f 66 20 74 68 69 73 20  ot page of this 
4f80: 74 72 65 65 20 2a 2f 0a 20 20 43 65 6c 6c 49 6e  tree */.  CellIn
4f90: 66 6f 20 69 6e 66 6f 3b 20 20 20 20 20 20 20 20  fo info;        
4fa0: 20 20 20 20 2f 2a 20 41 20 70 61 72 73 65 20 6f      /* A parse o
4fb0: 66 20 74 68 65 20 63 65 6c 6c 20 77 65 20 61 72  f the cell we ar
4fc0: 65 20 70 6f 69 6e 74 69 6e 67 20 61 74 20 2a 2f  e pointing at */
4fd0: 0a 20 20 75 38 20 77 72 46 6c 61 67 3b 20 20 20  .  u8 wrFlag;   
4fe0: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
4ff0: 54 72 75 65 20 69 66 20 77 72 69 74 61 62 6c 65  True if writable
5000: 20 2a 2f 0a 20 20 75 38 20 61 74 4c 61 73 74 3b   */.  u8 atLast;
5010: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
5020: 2f 2a 20 43 75 72 73 6f 72 20 70 6f 69 6e 74 69  /* Cursor pointi
5030: 6e 67 20 74 6f 20 74 68 65 20 6c 61 73 74 20 65  ng to the last e
5040: 6e 74 72 79 20 2a 2f 0a 20 20 75 38 20 76 61 6c  ntry */.  u8 val
5050: 69 64 4e 4b 65 79 3b 20 20 20 20 20 20 20 20 20  idNKey;         
5060: 20 20 20 20 2f 2a 20 54 72 75 65 20 69 66 20 69      /* True if i
5070: 6e 66 6f 2e 6e 4b 65 79 20 69 73 20 76 61 6c 69  nfo.nKey is vali
5080: 64 20 2a 2f 0a 20 20 75 38 20 65 53 74 61 74 65  d */.  u8 eState
5090: 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ;               
50a0: 20 2f 2a 20 4f 6e 65 20 6f 66 20 74 68 65 20 43   /* One of the C
50b0: 55 52 53 4f 52 5f 58 58 58 20 63 6f 6e 73 74 61  URSOR_XXX consta
50c0: 6e 74 73 20 28 73 65 65 20 62 65 6c 6f 77 29 20  nts (see below) 
50d0: 2a 2f 0a 20 20 76 6f 69 64 20 2a 70 4b 65 79 3b  */.  void *pKey;
50e0: 20 20 20 20 20 20 2f 2a 20 53 61 76 65 64 20 6b        /* Saved k
50f0: 65 79 20 74 68 61 74 20 77 61 73 20 63 75 72 73  ey that was curs
5100: 6f 72 27 73 20 6c 61 73 74 20 6b 6e 6f 77 6e 20  or's last known 
5110: 70 6f 73 69 74 69 6f 6e 20 2a 2f 0a 20 20 69 36  position */.  i6
5120: 34 20 6e 4b 65 79 3b 20 20 20 20 20 20 20 20 2f  4 nKey;        /
5130: 2a 20 53 69 7a 65 20 6f 66 20 70 4b 65 79 2c 20  * Size of pKey, 
5140: 6f 72 20 6c 61 73 74 20 69 6e 74 65 67 65 72 20  or last integer 
5150: 6b 65 79 20 2a 2f 0a 20 20 69 6e 74 20 73 6b 69  key */.  int ski
5160: 70 3b 20 20 20 20 20 20 20 20 2f 2a 20 28 73 6b  p;        /* (sk
5170: 69 70 3c 30 29 20 2d 3e 20 50 72 65 76 28 29 20  ip<0) -> Prev() 
5180: 69 73 20 61 20 6e 6f 2d 6f 70 2e 20 28 73 6b 69  is a no-op. (ski
5190: 70 3e 30 29 20 2d 3e 20 4e 65 78 74 28 29 20 69  p>0) -> Next() i
51a0: 73 20 2a 2f 0a 23 69 66 6e 64 65 66 20 53 51 4c  s */.#ifndef SQL
51b0: 49 54 45 5f 4f 4d 49 54 5f 49 4e 43 52 42 4c 4f  ITE_OMIT_INCRBLO
51c0: 42 0a 20 20 75 38 20 69 73 49 6e 63 72 62 6c 6f  B.  u8 isIncrblo
51d0: 62 48 61 6e 64 6c 65 3b 20 20 20 20 20 20 2f 2a  bHandle;      /*
51e0: 20 54 72 75 65 20 69 66 20 74 68 69 73 20 63 75   True if this cu
51f0: 72 73 6f 72 20 69 73 20 61 6e 20 69 6e 63 72 2e  rsor is an incr.
5200: 20 69 6f 20 68 61 6e 64 6c 65 20 2a 2f 0a 20 20   io handle */.  
5210: 50 67 6e 6f 20 2a 61 4f 76 65 72 66 6c 6f 77 3b  Pgno *aOverflow;
5220: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 43 61 63            /* Cac
5230: 68 65 20 6f 66 20 6f 76 65 72 66 6c 6f 77 20 70  he of overflow p
5240: 61 67 65 20 6c 6f 63 61 74 69 6f 6e 73 20 2a 2f  age locations */
5250: 0a 23 65 6e 64 69 66 0a 23 69 66 6e 64 65 66 20  .#endif.#ifndef 
5260: 4e 44 45 42 55 47 0a 20 20 75 38 20 70 61 67 65  NDEBUG.  u8 page
5270: 73 53 68 75 66 66 6c 65 64 3b 20 20 20 20 20 20  sShuffled;      
5280: 20 20 20 2f 2a 20 54 72 75 65 20 69 66 20 42 74     /* True if Bt
5290: 72 65 65 20 70 61 67 65 73 20 61 72 65 20 72 65  ree pages are re
52a0: 61 72 72 61 6e 67 65 64 20 62 79 20 62 61 6c 61  arranged by bala
52b0: 6e 63 65 28 29 2a 2f 0a 23 65 6e 64 69 66 0a 20  nce()*/.#endif. 
52c0: 20 69 31 36 20 69 50 61 67 65 3b 20 20 20 20 20   i16 iPage;     
52d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
52e0: 20 20 20 20 20 20 20 2f 2a 20 49 6e 64 65 78 20         /* Index 
52f0: 6f 66 20 63 75 72 72 65 6e 74 20 70 61 67 65 20  of current page 
5300: 69 6e 20 61 70 50 61 67 65 20 2a 2f 0a 20 20 4d  in apPage */.  M
5310: 65 6d 50 61 67 65 20 2a 61 70 50 61 67 65 5b 42  emPage *apPage[B
5320: 54 43 55 52 53 4f 52 5f 4d 41 58 5f 44 45 50 54  TCURSOR_MAX_DEPT
5330: 48 5d 3b 20 20 2f 2a 20 50 61 67 65 73 20 66 72  H];  /* Pages fr
5340: 6f 6d 20 72 6f 6f 74 20 74 6f 20 63 75 72 72 65  om root to curre
5350: 6e 74 20 70 61 67 65 20 2a 2f 0a 20 20 75 31 36  nt page */.  u16
5360: 20 61 69 49 64 78 5b 42 54 43 55 52 53 4f 52 5f   aiIdx[BTCURSOR_
5370: 4d 41 58 5f 44 45 50 54 48 5d 3b 20 20 20 20 20  MAX_DEPTH];     
5380: 20 20 20 2f 2a 20 43 75 72 72 65 6e 74 20 69 6e     /* Current in
5390: 64 65 78 20 69 6e 20 61 70 50 61 67 65 5b 69 5d  dex in apPage[i]
53a0: 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 50 6f   */.};../*.** Po
53b0: 74 65 6e 74 69 61 6c 20 76 61 6c 75 65 73 20 66  tential values f
53c0: 6f 72 20 42 74 43 75 72 73 6f 72 2e 65 53 74 61  or BtCursor.eSta
53d0: 74 65 2e 0a 2a 2a 0a 2a 2a 20 43 55 52 53 4f 52  te..**.** CURSOR
53e0: 5f 56 41 4c 49 44 3a 0a 2a 2a 20 20 20 43 75 72  _VALID:.**   Cur
53f0: 73 6f 72 20 70 6f 69 6e 74 73 20 74 6f 20 61 20  sor points to a 
5400: 76 61 6c 69 64 20 65 6e 74 72 79 2e 20 67 65 74  valid entry. get
5410: 50 61 79 6c 6f 61 64 28 29 20 65 74 63 2e 20 6d  Payload() etc. m
5420: 61 79 20 62 65 20 63 61 6c 6c 65 64 2e 0a 2a 2a  ay be called..**
5430: 0a 2a 2a 20 43 55 52 53 4f 52 5f 49 4e 56 41 4c  .** CURSOR_INVAL
5440: 49 44 3a 0a 2a 2a 20 20 20 43 75 72 73 6f 72 20  ID:.**   Cursor 
5450: 64 6f 65 73 20 6e 6f 74 20 70 6f 69 6e 74 20 74  does not point t
5460: 6f 20 61 20 76 61 6c 69 64 20 65 6e 74 72 79 2e  o a valid entry.
5470: 20 54 68 69 73 20 63 61 6e 20 68 61 70 70 65 6e   This can happen
5480: 20 28 66 6f 72 20 65 78 61 6d 70 6c 65 29 20 0a   (for example) .
5490: 2a 2a 20 20 20 62 65 63 61 75 73 65 20 74 68 65  **   because the
54a0: 20 74 61 62 6c 65 20 69 73 20 65 6d 70 74 79 20   table is empty 
54b0: 6f 72 20 62 65 63 61 75 73 65 20 42 74 72 65 65  or because Btree
54c0: 43 75 72 73 6f 72 46 69 72 73 74 28 29 20 68 61  CursorFirst() ha
54d0: 73 20 6e 6f 74 20 62 65 65 6e 0a 2a 2a 20 20 20  s not been.**   
54e0: 63 61 6c 6c 65 64 2e 0a 2a 2a 0a 2a 2a 20 43 55  called..**.** CU
54f0: 52 53 4f 52 5f 52 45 51 55 49 52 45 53 45 45 4b  RSOR_REQUIRESEEK
5500: 3a 0a 2a 2a 20 20 20 54 68 65 20 74 61 62 6c 65  :.**   The table
5510: 20 74 68 61 74 20 74 68 69 73 20 63 75 72 73 6f   that this curso
5520: 72 20 77 61 73 20 6f 70 65 6e 65 64 20 6f 6e 20  r was opened on 
5530: 73 74 69 6c 6c 20 65 78 69 73 74 73 2c 20 62 75  still exists, bu
5540: 74 20 68 61 73 20 62 65 65 6e 20 0a 2a 2a 20 20  t has been .**  
5550: 20 6d 6f 64 69 66 69 65 64 20 73 69 6e 63 65 20   modified since 
5560: 74 68 65 20 63 75 72 73 6f 72 20 77 61 73 20 6c  the cursor was l
5570: 61 73 74 20 75 73 65 64 2e 20 54 68 65 20 63 75  ast used. The cu
5580: 72 73 6f 72 20 70 6f 73 69 74 69 6f 6e 20 69 73  rsor position is
5590: 20 73 61 76 65 64 0a 2a 2a 20 20 20 69 6e 20 76   saved.**   in v
55a0: 61 72 69 61 62 6c 65 73 20 42 74 43 75 72 73 6f  ariables BtCurso
55b0: 72 2e 70 4b 65 79 20 61 6e 64 20 42 74 43 75 72  r.pKey and BtCur
55c0: 73 6f 72 2e 6e 4b 65 79 2e 20 57 68 65 6e 20 61  sor.nKey. When a
55d0: 20 63 75 72 73 6f 72 20 69 73 20 69 6e 20 0a 2a   cursor is in .*
55e0: 2a 20 20 20 74 68 69 73 20 73 74 61 74 65 2c 20  *   this state, 
55f0: 72 65 73 74 6f 72 65 43 75 72 73 6f 72 50 6f 73  restoreCursorPos
5600: 69 74 69 6f 6e 28 29 20 63 61 6e 20 62 65 20 63  ition() can be c
5610: 61 6c 6c 65 64 20 74 6f 20 61 74 74 65 6d 70 74  alled to attempt
5620: 20 74 6f 0a 2a 2a 20 20 20 73 65 65 6b 20 74 68   to.**   seek th
5630: 65 20 63 75 72 73 6f 72 20 74 6f 20 74 68 65 20  e cursor to the 
5640: 73 61 76 65 64 20 70 6f 73 69 74 69 6f 6e 2e 0a  saved position..
5650: 2a 2a 0a 2a 2a 20 43 55 52 53 4f 52 5f 46 41 55  **.** CURSOR_FAU
5660: 4c 54 3a 0a 2a 2a 20 20 20 41 20 75 6e 72 65 63  LT:.**   A unrec
5670: 6f 76 65 72 61 62 6c 65 20 65 72 72 6f 72 20 28  overable error (
5680: 61 6e 20 49 2f 4f 20 65 72 72 6f 72 20 6f 72 20  an I/O error or 
5690: 61 20 6d 61 6c 6c 6f 63 20 66 61 69 6c 75 72 65  a malloc failure
56a0: 29 20 68 61 73 20 6f 63 63 75 72 72 65 64 0a 2a  ) has occurred.*
56b0: 2a 20 20 20 6f 6e 20 61 20 64 69 66 66 65 72 65  *   on a differe
56c0: 6e 74 20 63 6f 6e 6e 65 63 74 69 6f 6e 20 74 68  nt connection th
56d0: 61 74 20 73 68 61 72 65 73 20 74 68 65 20 42 74  at shares the Bt
56e0: 53 68 61 72 65 64 20 63 61 63 68 65 20 77 69 74  Shared cache wit
56f0: 68 20 74 68 69 73 0a 2a 2a 20 20 20 63 75 72 73  h this.**   curs
5700: 6f 72 2e 20 20 54 68 65 20 65 72 72 6f 72 20 68  or.  The error h
5710: 61 73 20 6c 65 66 74 20 74 68 65 20 63 61 63 68  as left the cach
5720: 65 20 69 6e 20 61 6e 20 69 6e 63 6f 6e 73 69 73  e in an inconsis
5730: 74 65 6e 74 20 73 74 61 74 65 2e 0a 2a 2a 20 20  tent state..**  
5740: 20 44 6f 20 6e 6f 74 68 69 6e 67 20 65 6c 73 65   Do nothing else
5750: 20 77 69 74 68 20 74 68 69 73 20 63 75 72 73 6f   with this curso
5760: 72 2e 20 20 41 6e 79 20 61 74 74 65 6d 70 74 20  r.  Any attempt 
5770: 74 6f 20 75 73 65 20 74 68 65 20 63 75 72 73 6f  to use the curso
5780: 72 0a 2a 2a 20 20 20 73 68 6f 75 6c 64 20 72 65  r.**   should re
5790: 74 75 72 6e 20 74 68 65 20 65 72 72 6f 72 20 63  turn the error c
57a0: 6f 64 65 20 73 74 6f 72 65 64 20 69 6e 20 42 74  ode stored in Bt
57b0: 43 75 72 73 6f 72 2e 73 6b 69 70 0a 2a 2f 0a 23  Cursor.skip.*/.#
57c0: 64 65 66 69 6e 65 20 43 55 52 53 4f 52 5f 49 4e  define CURSOR_IN
57d0: 56 41 4c 49 44 20 20 20 20 20 20 20 20 20 20 20  VALID           
57e0: 30 0a 23 64 65 66 69 6e 65 20 43 55 52 53 4f 52  0.#define CURSOR
57f0: 5f 56 41 4c 49 44 20 20 20 20 20 20 20 20 20 20  _VALID          
5800: 20 20 20 31 0a 23 64 65 66 69 6e 65 20 43 55 52     1.#define CUR
5810: 53 4f 52 5f 52 45 51 55 49 52 45 53 45 45 4b 20  SOR_REQUIRESEEK 
5820: 20 20 20 20 20 20 32 0a 23 64 65 66 69 6e 65 20        2.#define 
5830: 43 55 52 53 4f 52 5f 46 41 55 4c 54 20 20 20 20  CURSOR_FAULT    
5840: 20 20 20 20 20 20 20 20 20 33 0a 0a 2f 2a 20 0a           3../* .
5850: 2a 2a 20 54 68 65 20 64 61 74 61 62 61 73 65 20  ** The database 
5860: 70 61 67 65 20 74 68 65 20 50 45 4e 44 49 4e 47  page the PENDING
5870: 5f 42 59 54 45 20 6f 63 63 75 70 69 65 73 2e 20  _BYTE occupies. 
5880: 54 68 69 73 20 70 61 67 65 20 69 73 20 6e 65 76  This page is nev
5890: 65 72 20 75 73 65 64 2e 0a 2a 2f 0a 23 20 64 65  er used..*/.# de
58a0: 66 69 6e 65 20 50 45 4e 44 49 4e 47 5f 42 59 54  fine PENDING_BYT
58b0: 45 5f 50 41 47 45 28 70 42 74 29 20 50 41 47 45  E_PAGE(pBt) PAGE
58c0: 52 5f 4d 4a 5f 50 47 4e 4f 28 70 42 74 29 0a 0a  R_MJ_PGNO(pBt)..
58d0: 2f 2a 0a 2a 2a 20 41 20 6c 69 6e 6b 65 64 20 6c  /*.** A linked l
58e0: 69 73 74 20 6f 66 20 74 68 65 20 66 6f 6c 6c 6f  ist of the follo
58f0: 77 69 6e 67 20 73 74 72 75 63 74 75 72 65 73 20  wing structures 
5900: 69 73 20 73 74 6f 72 65 64 20 61 74 20 42 74 53  is stored at BtS
5910: 68 61 72 65 64 2e 70 4c 6f 63 6b 2e 0a 2a 2a 20  hared.pLock..** 
5920: 4c 6f 63 6b 73 20 61 72 65 20 61 64 64 65 64 20  Locks are added 
5930: 28 6f 72 20 75 70 67 72 61 64 65 64 20 66 72 6f  (or upgraded fro
5940: 6d 20 52 45 41 44 5f 4c 4f 43 4b 20 74 6f 20 57  m READ_LOCK to W
5950: 52 49 54 45 5f 4c 4f 43 4b 29 20 77 68 65 6e 20  RITE_LOCK) when 
5960: 61 20 63 75 72 73 6f 72 20 0a 2a 2a 20 69 73 20  a cursor .** is 
5970: 6f 70 65 6e 65 64 20 6f 6e 20 74 68 65 20 74 61  opened on the ta
5980: 62 6c 65 20 77 69 74 68 20 72 6f 6f 74 20 70 61  ble with root pa
5990: 67 65 20 42 74 53 68 61 72 65 64 2e 69 54 61 62  ge BtShared.iTab
59a0: 6c 65 2e 20 4c 6f 63 6b 73 20 61 72 65 20 72 65  le. Locks are re
59b0: 6d 6f 76 65 64 0a 2a 2a 20 66 72 6f 6d 20 74 68  moved.** from th
59c0: 69 73 20 6c 69 73 74 20 77 68 65 6e 20 61 20 74  is list when a t
59d0: 72 61 6e 73 61 63 74 69 6f 6e 20 69 73 20 63 6f  ransaction is co
59e0: 6d 6d 69 74 74 65 64 20 6f 72 20 72 6f 6c 6c 65  mmitted or rolle
59f0: 64 20 62 61 63 6b 2c 20 6f 72 20 77 68 65 6e 0a  d back, or when.
5a00: 2a 2a 20 61 20 62 74 72 65 65 20 68 61 6e 64 6c  ** a btree handl
5a10: 65 20 69 73 20 63 6c 6f 73 65 64 2e 0a 2a 2f 0a  e is closed..*/.
5a20: 73 74 72 75 63 74 20 42 74 4c 6f 63 6b 20 7b 0a  struct BtLock {.
5a30: 20 20 42 74 72 65 65 20 2a 70 42 74 72 65 65 3b    Btree *pBtree;
5a40: 20 20 20 20 20 20 20 20 2f 2a 20 42 74 72 65 65          /* Btree
5a50: 20 68 61 6e 64 6c 65 20 68 6f 6c 64 69 6e 67 20   handle holding 
5a60: 74 68 69 73 20 6c 6f 63 6b 20 2a 2f 0a 20 20 50  this lock */.  P
5a70: 67 6e 6f 20 69 54 61 62 6c 65 3b 20 20 20 20 20  gno iTable;     
5a80: 20 20 20 20 20 2f 2a 20 52 6f 6f 74 20 70 61 67       /* Root pag
5a90: 65 20 6f 66 20 74 61 62 6c 65 20 2a 2f 0a 20 20  e of table */.  
5aa0: 75 38 20 65 4c 6f 63 6b 3b 20 20 20 20 20 20 20  u8 eLock;       
5ab0: 20 20 20 20 20 20 2f 2a 20 52 45 41 44 5f 4c 4f        /* READ_LO
5ac0: 43 4b 20 6f 72 20 57 52 49 54 45 5f 4c 4f 43 4b  CK or WRITE_LOCK
5ad0: 20 2a 2f 0a 20 20 42 74 4c 6f 63 6b 20 2a 70 4e   */.  BtLock *pN
5ae0: 65 78 74 3b 20 20 20 20 20 20 20 20 2f 2a 20 4e  ext;        /* N
5af0: 65 78 74 20 69 6e 20 42 74 53 68 61 72 65 64 2e  ext in BtShared.
5b00: 70 4c 6f 63 6b 20 6c 69 73 74 20 2a 2f 0a 7d 3b  pLock list */.};
5b10: 0a 0a 2f 2a 20 43 61 6e 64 69 64 61 74 65 20 76  ../* Candidate v
5b20: 61 6c 75 65 73 20 66 6f 72 20 42 74 4c 6f 63 6b  alues for BtLock
5b30: 2e 65 4c 6f 63 6b 20 2a 2f 0a 23 64 65 66 69 6e  .eLock */.#defin
5b40: 65 20 52 45 41 44 5f 4c 4f 43 4b 20 20 20 20 20  e READ_LOCK     
5b50: 31 0a 23 64 65 66 69 6e 65 20 57 52 49 54 45 5f  1.#define WRITE_
5b60: 4c 4f 43 4b 20 20 20 20 32 0a 0a 2f 2a 0a 2a 2a  LOCK    2../*.**
5b70: 20 54 68 65 73 65 20 6d 61 63 72 6f 73 20 64 65   These macros de
5b80: 66 69 6e 65 20 74 68 65 20 6c 6f 63 61 74 69 6f  fine the locatio
5b90: 6e 20 6f 66 20 74 68 65 20 70 6f 69 6e 74 65 72  n of the pointer
5ba0: 2d 6d 61 70 20 65 6e 74 72 79 20 66 6f 72 20 61  -map entry for a
5bb0: 20 0a 2a 2a 20 64 61 74 61 62 61 73 65 20 70 61   .** database pa
5bc0: 67 65 2e 20 54 68 65 20 66 69 72 73 74 20 61 72  ge. The first ar
5bd0: 67 75 6d 65 6e 74 20 74 6f 20 65 61 63 68 20 69  gument to each i
5be0: 73 20 74 68 65 20 6e 75 6d 62 65 72 20 6f 66 20  s the number of 
5bf0: 75 73 61 62 6c 65 0a 2a 2a 20 62 79 74 65 73 20  usable.** bytes 
5c00: 6f 6e 20 65 61 63 68 20 70 61 67 65 20 6f 66 20  on each page of 
5c10: 74 68 65 20 64 61 74 61 62 61 73 65 20 28 6f 66  the database (of
5c20: 74 65 6e 20 31 30 32 34 29 2e 20 54 68 65 20 73  ten 1024). The s
5c30: 65 63 6f 6e 64 20 69 73 20 74 68 65 0a 2a 2a 20  econd is the.** 
5c40: 70 61 67 65 20 6e 75 6d 62 65 72 20 74 6f 20 6c  page number to l
5c50: 6f 6f 6b 20 75 70 20 69 6e 20 74 68 65 20 70 6f  ook up in the po
5c60: 69 6e 74 65 72 20 6d 61 70 2e 0a 2a 2a 0a 2a 2a  inter map..**.**
5c70: 20 50 54 52 4d 41 50 5f 50 41 47 45 4e 4f 20 72   PTRMAP_PAGENO r
5c80: 65 74 75 72 6e 73 20 74 68 65 20 64 61 74 61 62  eturns the datab
5c90: 61 73 65 20 70 61 67 65 20 6e 75 6d 62 65 72 20  ase page number 
5ca0: 6f 66 20 74 68 65 20 70 6f 69 6e 74 65 72 2d 6d  of the pointer-m
5cb0: 61 70 0a 2a 2a 20 70 61 67 65 20 74 68 61 74 20  ap.** page that 
5cc0: 73 74 6f 72 65 73 20 74 68 65 20 72 65 71 75 69  stores the requi
5cd0: 72 65 64 20 70 6f 69 6e 74 65 72 2e 20 50 54 52  red pointer. PTR
5ce0: 4d 41 50 5f 50 54 52 4f 46 46 53 45 54 20 72 65  MAP_PTROFFSET re
5cf0: 74 75 72 6e 73 0a 2a 2a 20 74 68 65 20 6f 66 66  turns.** the off
5d00: 73 65 74 20 6f 66 20 74 68 65 20 72 65 71 75 65  set of the reque
5d10: 73 74 65 64 20 6d 61 70 20 65 6e 74 72 79 2e 0a  sted map entry..
5d20: 2a 2a 0a 2a 2a 20 49 66 20 74 68 65 20 70 67 6e  **.** If the pgn
5d30: 6f 20 61 72 67 75 6d 65 6e 74 20 70 61 73 73 65  o argument passe
5d40: 64 20 74 6f 20 50 54 52 4d 41 50 5f 50 41 47 45  d to PTRMAP_PAGE
5d50: 4e 4f 20 69 73 20 61 20 70 6f 69 6e 74 65 72 2d  NO is a pointer-
5d60: 6d 61 70 20 70 61 67 65 2c 0a 2a 2a 20 74 68 65  map page,.** the
5d70: 6e 20 70 67 6e 6f 20 69 73 20 72 65 74 75 72 6e  n pgno is return
5d80: 65 64 2e 20 53 6f 20 28 70 67 6e 6f 3d 3d 50 54  ed. So (pgno==PT
5d90: 52 4d 41 50 5f 50 41 47 45 4e 4f 28 70 67 73 7a  RMAP_PAGENO(pgsz
5da0: 2c 20 70 67 6e 6f 29 29 20 63 61 6e 20 62 65 0a  , pgno)) can be.
5db0: 2a 2a 20 75 73 65 64 20 74 6f 20 74 65 73 74 20  ** used to test 
5dc0: 69 66 20 70 67 6e 6f 20 69 73 20 61 20 70 6f 69  if pgno is a poi
5dd0: 6e 74 65 72 2d 6d 61 70 20 70 61 67 65 2e 20 50  nter-map page. P
5de0: 54 52 4d 41 50 5f 49 53 50 41 47 45 20 69 6d 70  TRMAP_ISPAGE imp
5df0: 6c 65 6d 65 6e 74 73 0a 2a 2a 20 74 68 69 73 20  lements.** this 
5e00: 74 65 73 74 2e 0a 2a 2f 0a 23 64 65 66 69 6e 65  test..*/.#define
5e10: 20 50 54 52 4d 41 50 5f 50 41 47 45 4e 4f 28 70   PTRMAP_PAGENO(p
5e20: 42 74 2c 20 70 67 6e 6f 29 20 70 74 72 6d 61 70  Bt, pgno) ptrmap
5e30: 50 61 67 65 6e 6f 28 70 42 74 2c 20 70 67 6e 6f  Pageno(pBt, pgno
5e40: 29 0a 23 64 65 66 69 6e 65 20 50 54 52 4d 41 50  ).#define PTRMAP
5e50: 5f 50 54 52 4f 46 46 53 45 54 28 70 67 70 74 72  _PTROFFSET(pgptr
5e60: 6d 61 70 2c 20 70 67 6e 6f 29 20 28 35 2a 28 70  map, pgno) (5*(p
5e70: 67 6e 6f 2d 70 67 70 74 72 6d 61 70 2d 31 29 29  gno-pgptrmap-1))
5e80: 0a 23 64 65 66 69 6e 65 20 50 54 52 4d 41 50 5f  .#define PTRMAP_
5e90: 49 53 50 41 47 45 28 70 42 74 2c 20 70 67 6e 6f  ISPAGE(pBt, pgno
5ea0: 29 20 28 50 54 52 4d 41 50 5f 50 41 47 45 4e 4f  ) (PTRMAP_PAGENO
5eb0: 28 28 70 42 74 29 2c 28 70 67 6e 6f 29 29 3d 3d  ((pBt),(pgno))==
5ec0: 28 70 67 6e 6f 29 29 0a 0a 2f 2a 0a 2a 2a 20 54  (pgno))../*.** T
5ed0: 68 65 20 70 6f 69 6e 74 65 72 20 6d 61 70 20 69  he pointer map i
5ee0: 73 20 61 20 6c 6f 6f 6b 75 70 20 74 61 62 6c 65  s a lookup table
5ef0: 20 74 68 61 74 20 69 64 65 6e 74 69 66 69 65 73   that identifies
5f00: 20 74 68 65 20 70 61 72 65 6e 74 20 70 61 67 65   the parent page
5f10: 20 66 6f 72 0a 2a 2a 20 65 61 63 68 20 63 68 69   for.** each chi
5f20: 6c 64 20 70 61 67 65 20 69 6e 20 74 68 65 20 64  ld page in the d
5f30: 61 74 61 62 61 73 65 20 66 69 6c 65 2e 20 20 54  atabase file.  T
5f40: 68 65 20 70 61 72 65 6e 74 20 70 61 67 65 20 69  he parent page i
5f50: 73 20 74 68 65 20 70 61 67 65 20 74 68 61 74 0a  s the page that.
5f60: 2a 2a 20 63 6f 6e 74 61 69 6e 73 20 61 20 70 6f  ** contains a po
5f70: 69 6e 74 65 72 20 74 6f 20 74 68 65 20 63 68 69  inter to the chi
5f80: 6c 64 2e 20 20 45 76 65 72 79 20 70 61 67 65 20  ld.  Every page 
5f90: 69 6e 20 74 68 65 20 64 61 74 61 62 61 73 65 20  in the database 
5fa0: 63 6f 6e 74 61 69 6e 73 0a 2a 2a 20 30 20 6f 72  contains.** 0 or
5fb0: 20 31 20 70 61 72 65 6e 74 20 70 61 67 65 73 2e   1 parent pages.
5fc0: 20 20 28 49 6e 20 74 68 69 73 20 63 6f 6e 74 65    (In this conte
5fd0: 78 74 20 27 64 61 74 61 62 61 73 65 20 70 61 67  xt 'database pag
5fe0: 65 27 20 72 65 66 65 72 73 0a 2a 2a 20 74 6f 20  e' refers.** to 
5ff0: 61 6e 79 20 70 61 67 65 20 74 68 61 74 20 69 73  any page that is
6000: 20 6e 6f 74 20 70 61 72 74 20 6f 66 20 74 68 65   not part of the
6010: 20 70 6f 69 6e 74 65 72 20 6d 61 70 20 69 74 73   pointer map its
6020: 65 6c 66 2e 29 20 20 45 61 63 68 20 70 6f 69 6e  elf.)  Each poin
6030: 74 65 72 20 6d 61 70 0a 2a 2a 20 65 6e 74 72 79  ter map.** entry
6040: 20 63 6f 6e 73 69 73 74 73 20 6f 66 20 61 20 73   consists of a s
6050: 69 6e 67 6c 65 20 62 79 74 65 20 27 74 79 70 65  ingle byte 'type
6060: 27 20 61 6e 64 20 61 20 34 20 62 79 74 65 20 70  ' and a 4 byte p
6070: 61 72 65 6e 74 20 70 61 67 65 20 6e 75 6d 62 65  arent page numbe
6080: 72 2e 0a 2a 2a 20 54 68 65 20 50 54 52 4d 41 50  r..** The PTRMAP
6090: 5f 58 58 58 20 69 64 65 6e 74 69 66 69 65 72 73  _XXX identifiers
60a0: 20 62 65 6c 6f 77 20 61 72 65 20 74 68 65 20 76   below are the v
60b0: 61 6c 69 64 20 74 79 70 65 73 2e 0a 2a 2a 0a 2a  alid types..**.*
60c0: 2a 20 54 68 65 20 70 75 72 70 6f 73 65 20 6f 66  * The purpose of
60d0: 20 74 68 65 20 70 6f 69 6e 74 65 72 20 6d 61 70   the pointer map
60e0: 20 69 73 20 74 6f 20 66 61 63 69 6c 69 74 79 20   is to facility 
60f0: 6d 6f 76 69 6e 67 20 70 61 67 65 73 20 66 72 6f  moving pages fro
6100: 6d 20 6f 6e 65 0a 2a 2a 20 70 6f 73 69 74 69 6f  m one.** positio
6110: 6e 20 69 6e 20 74 68 65 20 66 69 6c 65 20 74 6f  n in the file to
6120: 20 61 6e 6f 74 68 65 72 20 61 73 20 70 61 72 74   another as part
6130: 20 6f 66 20 61 75 74 6f 76 61 63 75 75 6d 2e 20   of autovacuum. 
6140: 20 57 68 65 6e 20 61 20 70 61 67 65 0a 2a 2a 20   When a page.** 
6150: 69 73 20 6d 6f 76 65 64 2c 20 74 68 65 20 70 6f  is moved, the po
6160: 69 6e 74 65 72 20 69 6e 20 69 74 73 20 70 61 72  inter in its par
6170: 65 6e 74 20 6d 75 73 74 20 62 65 20 75 70 64 61  ent must be upda
6180: 74 65 64 20 74 6f 20 70 6f 69 6e 74 20 74 6f 20  ted to point to 
6190: 74 68 65 0a 2a 2a 20 6e 65 77 20 6c 6f 63 61 74  the.** new locat
61a0: 69 6f 6e 2e 20 20 54 68 65 20 70 6f 69 6e 74 65  ion.  The pointe
61b0: 72 20 6d 61 70 20 69 73 20 75 73 65 64 20 74 6f  r map is used to
61c0: 20 6c 6f 63 61 74 65 20 74 68 65 20 70 61 72 65   locate the pare
61d0: 6e 74 20 70 61 67 65 20 71 75 69 63 6b 6c 79 2e  nt page quickly.
61e0: 0a 2a 2a 0a 2a 2a 20 50 54 52 4d 41 50 5f 52 4f  .**.** PTRMAP_RO
61f0: 4f 54 50 41 47 45 3a 20 54 68 65 20 64 61 74 61  OTPAGE: The data
6200: 62 61 73 65 20 70 61 67 65 20 69 73 20 61 20 72  base page is a r
6210: 6f 6f 74 2d 70 61 67 65 2e 20 54 68 65 20 70 61  oot-page. The pa
6220: 67 65 2d 6e 75 6d 62 65 72 20 69 73 20 6e 6f 74  ge-number is not
6230: 0a 2a 2a 20 20 20 20 20 20 20 20 20 20 20 20 20  .**             
6240: 20 20 20 20 20 75 73 65 64 20 69 6e 20 74 68 69       used in thi
6250: 73 20 63 61 73 65 2e 0a 2a 2a 0a 2a 2a 20 50 54  s case..**.** PT
6260: 52 4d 41 50 5f 46 52 45 45 50 41 47 45 3a 20 54  RMAP_FREEPAGE: T
6270: 68 65 20 64 61 74 61 62 61 73 65 20 70 61 67 65  he database page
6280: 20 69 73 20 61 6e 20 75 6e 75 73 65 64 20 28 66   is an unused (f
6290: 72 65 65 29 20 70 61 67 65 2e 20 54 68 65 20 70  ree) page. The p
62a0: 61 67 65 2d 6e 75 6d 62 65 72 20 0a 2a 2a 20 20  age-number .**  
62b0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
62c0: 69 73 20 6e 6f 74 20 75 73 65 64 20 69 6e 20 74  is not used in t
62d0: 68 69 73 20 63 61 73 65 2e 0a 2a 2a 0a 2a 2a 20  his case..**.** 
62e0: 50 54 52 4d 41 50 5f 4f 56 45 52 46 4c 4f 57 31  PTRMAP_OVERFLOW1
62f0: 3a 20 54 68 65 20 64 61 74 61 62 61 73 65 20 70  : The database p
6300: 61 67 65 20 69 73 20 74 68 65 20 66 69 72 73 74  age is the first
6310: 20 70 61 67 65 20 69 6e 20 61 20 6c 69 73 74 20   page in a list 
6320: 6f 66 20 0a 2a 2a 20 20 20 20 20 20 20 20 20 20  of .**          
6330: 20 20 20 20 20 20 20 20 20 6f 76 65 72 66 6c 6f           overflo
6340: 77 20 70 61 67 65 73 2e 20 54 68 65 20 70 61 67  w pages. The pag
6350: 65 20 6e 75 6d 62 65 72 20 69 64 65 6e 74 69 66  e number identif
6360: 69 65 73 20 74 68 65 20 70 61 67 65 20 74 68 61  ies the page tha
6370: 74 0a 2a 2a 20 20 20 20 20 20 20 20 20 20 20 20  t.**            
6380: 20 20 20 20 20 20 20 63 6f 6e 74 61 69 6e 73 20         contains 
6390: 74 68 65 20 63 65 6c 6c 20 77 69 74 68 20 61 20  the cell with a 
63a0: 70 6f 69 6e 74 65 72 20 74 6f 20 74 68 69 73 20  pointer to this 
63b0: 6f 76 65 72 66 6c 6f 77 20 70 61 67 65 2e 0a 2a  overflow page..*
63c0: 2a 0a 2a 2a 20 50 54 52 4d 41 50 5f 4f 56 45 52  *.** PTRMAP_OVER
63d0: 46 4c 4f 57 32 3a 20 54 68 65 20 64 61 74 61 62  FLOW2: The datab
63e0: 61 73 65 20 70 61 67 65 20 69 73 20 74 68 65 20  ase page is the 
63f0: 73 65 63 6f 6e 64 20 6f 72 20 6c 61 74 65 72 20  second or later 
6400: 70 61 67 65 20 69 6e 20 61 20 6c 69 73 74 20 6f  page in a list o
6410: 66 0a 2a 2a 20 20 20 20 20 20 20 20 20 20 20 20  f.**            
6420: 20 20 20 20 20 20 20 6f 76 65 72 66 6c 6f 77 20         overflow 
6430: 70 61 67 65 73 2e 20 54 68 65 20 70 61 67 65 2d  pages. The page-
6440: 6e 75 6d 62 65 72 20 69 64 65 6e 74 69 66 69 65  number identifie
6450: 73 20 74 68 65 20 70 72 65 76 69 6f 75 73 0a 2a  s the previous.*
6460: 2a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  *               
6470: 20 20 20 20 70 61 67 65 20 69 6e 20 74 68 65 20      page in the 
6480: 6f 76 65 72 66 6c 6f 77 20 70 61 67 65 20 6c 69  overflow page li
6490: 73 74 2e 0a 2a 2a 0a 2a 2a 20 50 54 52 4d 41 50  st..**.** PTRMAP
64a0: 5f 42 54 52 45 45 3a 20 54 68 65 20 64 61 74 61  _BTREE: The data
64b0: 62 61 73 65 20 70 61 67 65 20 69 73 20 61 20 6e  base page is a n
64c0: 6f 6e 2d 72 6f 6f 74 20 62 74 72 65 65 20 70 61  on-root btree pa
64d0: 67 65 2e 20 54 68 65 20 70 61 67 65 20 6e 75 6d  ge. The page num
64e0: 62 65 72 0a 2a 2a 20 20 20 20 20 20 20 20 20 20  ber.**          
64f0: 20 20 20 20 20 69 64 65 6e 74 69 66 69 65 73 20       identifies 
6500: 74 68 65 20 70 61 72 65 6e 74 20 70 61 67 65 20  the parent page 
6510: 69 6e 20 74 68 65 20 62 74 72 65 65 2e 0a 2a 2f  in the btree..*/
6520: 0a 23 64 65 66 69 6e 65 20 50 54 52 4d 41 50 5f  .#define PTRMAP_
6530: 52 4f 4f 54 50 41 47 45 20 31 0a 23 64 65 66 69  ROOTPAGE 1.#defi
6540: 6e 65 20 50 54 52 4d 41 50 5f 46 52 45 45 50 41  ne PTRMAP_FREEPA
6550: 47 45 20 32 0a 23 64 65 66 69 6e 65 20 50 54 52  GE 2.#define PTR
6560: 4d 41 50 5f 4f 56 45 52 46 4c 4f 57 31 20 33 0a  MAP_OVERFLOW1 3.
6570: 23 64 65 66 69 6e 65 20 50 54 52 4d 41 50 5f 4f  #define PTRMAP_O
6580: 56 45 52 46 4c 4f 57 32 20 34 0a 23 64 65 66 69  VERFLOW2 4.#defi
6590: 6e 65 20 50 54 52 4d 41 50 5f 42 54 52 45 45 20  ne PTRMAP_BTREE 
65a0: 35 0a 0a 2f 2a 20 41 20 62 75 6e 63 68 20 6f 66  5../* A bunch of
65b0: 20 61 73 73 65 72 74 28 29 20 73 74 61 74 65 6d   assert() statem
65c0: 65 6e 74 73 20 74 6f 20 63 68 65 63 6b 20 74 68  ents to check th
65d0: 65 20 74 72 61 6e 73 61 63 74 69 6f 6e 20 73 74  e transaction st
65e0: 61 74 65 20 76 61 72 69 61 62 6c 65 73 0a 2a 2a  ate variables.**
65f0: 20 6f 66 20 68 61 6e 64 6c 65 20 70 20 28 74 79   of handle p (ty
6600: 70 65 20 42 74 72 65 65 2a 29 20 61 72 65 20 69  pe Btree*) are i
6610: 6e 74 65 72 6e 61 6c 6c 79 20 63 6f 6e 73 69 73  nternally consis
6620: 74 65 6e 74 2e 0a 2a 2f 0a 23 64 65 66 69 6e 65  tent..*/.#define
6630: 20 62 74 72 65 65 49 6e 74 65 67 72 69 74 79 28   btreeIntegrity(
6640: 70 29 20 5c 0a 20 20 61 73 73 65 72 74 28 20 70  p) \.  assert( p
6650: 2d 3e 70 42 74 2d 3e 69 6e 54 72 61 6e 73 61 63  ->pBt->inTransac
6660: 74 69 6f 6e 21 3d 54 52 41 4e 53 5f 4e 4f 4e 45  tion!=TRANS_NONE
6670: 20 7c 7c 20 70 2d 3e 70 42 74 2d 3e 6e 54 72 61   || p->pBt->nTra
6680: 6e 73 61 63 74 69 6f 6e 3d 3d 30 20 29 3b 20 5c  nsaction==0 ); \
6690: 0a 20 20 61 73 73 65 72 74 28 20 70 2d 3e 70 42  .  assert( p->pB
66a0: 74 2d 3e 69 6e 54 72 61 6e 73 61 63 74 69 6f 6e  t->inTransaction
66b0: 3e 3d 70 2d 3e 69 6e 54 72 61 6e 73 20 29 3b 20  >=p->inTrans ); 
66c0: 0a 0a 0a 2f 2a 0a 2a 2a 20 54 68 65 20 49 53 41  .../*.** The ISA
66d0: 55 54 4f 56 41 43 55 55 4d 20 6d 61 63 72 6f 20  UTOVACUUM macro 
66e0: 69 73 20 75 73 65 64 20 77 69 74 68 69 6e 20 62  is used within b
66f0: 61 6c 61 6e 63 65 5f 6e 6f 6e 72 6f 6f 74 28 29  alance_nonroot()
6700: 20 74 6f 20 64 65 74 65 72 6d 69 6e 65 0a 2a 2a   to determine.**
6710: 20 69 66 20 74 68 65 20 64 61 74 61 62 61 73 65   if the database
6720: 20 73 75 70 70 6f 72 74 73 20 61 75 74 6f 2d 76   supports auto-v
6730: 61 63 75 75 6d 20 6f 72 20 6e 6f 74 2e 20 42 65  acuum or not. Be
6740: 63 61 75 73 65 20 69 74 20 69 73 20 75 73 65 64  cause it is used
6750: 0a 2a 2a 20 77 69 74 68 69 6e 20 61 6e 20 65 78  .** within an ex
6760: 70 72 65 73 73 69 6f 6e 20 74 68 61 74 20 69 73  pression that is
6770: 20 61 6e 20 61 72 67 75 6d 65 6e 74 20 74 6f 20   an argument to 
6780: 61 6e 6f 74 68 65 72 20 6d 61 63 72 6f 20 0a 2a  another macro .*
6790: 2a 20 28 73 71 6c 69 74 65 4d 61 6c 6c 6f 63 52  * (sqliteMallocR
67a0: 61 77 29 2c 20 69 74 20 69 73 20 6e 6f 74 20 70  aw), it is not p
67b0: 6f 73 73 69 62 6c 65 20 74 6f 20 75 73 65 20 63  ossible to use c
67c0: 6f 6e 64 69 74 69 6f 6e 61 6c 20 63 6f 6d 70 69  onditional compi
67d0: 6c 61 74 69 6f 6e 2e 0a 2a 2a 20 53 6f 2c 20 74  lation..** So, t
67e0: 68 69 73 20 6d 61 63 72 6f 20 69 73 20 64 65 66  his macro is def
67f0: 69 6e 65 64 20 69 6e 73 74 65 61 64 2e 0a 2a 2f  ined instead..*/
6800: 0a 23 69 66 6e 64 65 66 20 53 51 4c 49 54 45 5f  .#ifndef SQLITE_
6810: 4f 4d 49 54 5f 41 55 54 4f 56 41 43 55 55 4d 0a  OMIT_AUTOVACUUM.
6820: 23 64 65 66 69 6e 65 20 49 53 41 55 54 4f 56 41  #define ISAUTOVA
6830: 43 55 55 4d 20 28 70 42 74 2d 3e 61 75 74 6f 56  CUUM (pBt->autoV
6840: 61 63 75 75 6d 29 0a 23 65 6c 73 65 0a 23 64 65  acuum).#else.#de
6850: 66 69 6e 65 20 49 53 41 55 54 4f 56 41 43 55 55  fine ISAUTOVACUU
6860: 4d 20 30 0a 23 65 6e 64 69 66 0a 0a 0a 2f 2a 0a  M 0.#endif.../*.
6870: 2a 2a 20 54 68 69 73 20 73 74 72 75 63 74 75 72  ** This structur
6880: 65 20 69 73 20 70 61 73 73 65 64 20 61 72 6f 75  e is passed arou
6890: 6e 64 20 74 68 72 6f 75 67 68 20 61 6c 6c 20 74  nd through all t
68a0: 68 65 20 73 61 6e 69 74 79 20 63 68 65 63 6b 69  he sanity checki
68b0: 6e 67 20 72 6f 75 74 69 6e 65 73 0a 2a 2a 20 69  ng routines.** i
68c0: 6e 20 6f 72 64 65 72 20 74 6f 20 6b 65 65 70 20  n order to keep 
68d0: 74 72 61 63 6b 20 6f 66 20 73 6f 6d 65 20 67 6c  track of some gl
68e0: 6f 62 61 6c 20 73 74 61 74 65 20 69 6e 66 6f 72  obal state infor
68f0: 6d 61 74 69 6f 6e 2e 0a 2a 2f 0a 74 79 70 65 64  mation..*/.typed
6900: 65 66 20 73 74 72 75 63 74 20 49 6e 74 65 67 72  ef struct Integr
6910: 69 74 79 43 6b 20 49 6e 74 65 67 72 69 74 79 43  ityCk IntegrityC
6920: 6b 3b 0a 73 74 72 75 63 74 20 49 6e 74 65 67 72  k;.struct Integr
6930: 69 74 79 43 6b 20 7b 0a 20 20 42 74 53 68 61 72  ityCk {.  BtShar
6940: 65 64 20 2a 70 42 74 3b 20 20 20 20 2f 2a 20 54  ed *pBt;    /* T
6950: 68 65 20 74 72 65 65 20 62 65 69 6e 67 20 63 68  he tree being ch
6960: 65 63 6b 65 64 20 6f 75 74 20 2a 2f 0a 20 20 50  ecked out */.  P
6970: 61 67 65 72 20 2a 70 50 61 67 65 72 3b 20 20 20  ager *pPager;   
6980: 20 2f 2a 20 54 68 65 20 61 73 73 6f 63 69 61 74   /* The associat
6990: 65 64 20 70 61 67 65 72 2e 20 20 41 6c 73 6f 20  ed pager.  Also 
69a0: 61 63 63 65 73 73 69 62 6c 65 20 62 79 20 70 42  accessible by pB
69b0: 74 2d 3e 70 50 61 67 65 72 20 2a 2f 0a 20 20 50  t->pPager */.  P
69c0: 67 6e 6f 20 6e 50 61 67 65 3b 20 20 20 20 20 20  gno nPage;      
69d0: 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 70 61   /* Number of pa
69e0: 67 65 73 20 69 6e 20 74 68 65 20 64 61 74 61 62  ges in the datab
69f0: 61 73 65 20 2a 2f 0a 20 20 69 6e 74 20 2a 61 6e  ase */.  int *an
6a00: 52 65 66 3b 20 20 20 20 20 20 20 2f 2a 20 4e 75  Ref;       /* Nu
6a10: 6d 62 65 72 20 6f 66 20 74 69 6d 65 73 20 65 61  mber of times ea
6a20: 63 68 20 70 61 67 65 20 69 73 20 72 65 66 65 72  ch page is refer
6a30: 65 6e 63 65 64 20 2a 2f 0a 20 20 69 6e 74 20 6d  enced */.  int m
6a40: 78 45 72 72 3b 20 20 20 20 20 20 20 20 2f 2a 20  xErr;        /* 
6a50: 53 74 6f 70 20 61 63 63 75 6d 75 6c 61 74 69 6e  Stop accumulatin
6a60: 67 20 65 72 72 6f 72 73 20 77 68 65 6e 20 74 68  g errors when th
6a70: 69 73 20 72 65 61 63 68 65 73 20 7a 65 72 6f 20  is reaches zero 
6a80: 2a 2f 0a 20 20 69 6e 74 20 6e 45 72 72 3b 20 20  */.  int nErr;  
6a90: 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72         /* Number
6aa0: 20 6f 66 20 6d 65 73 73 61 67 65 73 20 77 72 69   of messages wri
6ab0: 74 74 65 6e 20 74 6f 20 7a 45 72 72 4d 73 67 20  tten to zErrMsg 
6ac0: 73 6f 20 66 61 72 20 2a 2f 0a 20 20 69 6e 74 20  so far */.  int 
6ad0: 6d 61 6c 6c 6f 63 46 61 69 6c 65 64 3b 20 2f 2a  mallocFailed; /*
6ae0: 20 41 20 6d 65 6d 6f 72 79 20 61 6c 6c 6f 63 61   A memory alloca
6af0: 74 69 6f 6e 20 65 72 72 6f 72 20 68 61 73 20 6f  tion error has o
6b00: 63 63 75 72 72 65 64 20 2a 2f 0a 20 20 53 74 72  ccurred */.  Str
6b10: 41 63 63 75 6d 20 65 72 72 4d 73 67 3b 20 20 2f  Accum errMsg;  /
6b20: 2a 20 41 63 63 75 6d 75 6c 61 74 65 20 74 68 65  * Accumulate the
6b30: 20 65 72 72 6f 72 20 6d 65 73 73 61 67 65 20 74   error message t
6b40: 65 78 74 20 68 65 72 65 20 2a 2f 0a 7d 3b 0a 0a  ext here */.};..
6b50: 2f 2a 0a 2a 2a 20 52 65 61 64 20 6f 72 20 77 72  /*.** Read or wr
6b60: 69 74 65 20 61 20 74 77 6f 2d 20 61 6e 64 20 66  ite a two- and f
6b70: 6f 75 72 2d 62 79 74 65 20 62 69 67 2d 65 6e 64  our-byte big-end
6b80: 69 61 6e 20 69 6e 74 65 67 65 72 20 76 61 6c 75  ian integer valu
6b90: 65 73 2e 0a 2a 2f 0a 23 64 65 66 69 6e 65 20 67  es..*/.#define g
6ba0: 65 74 32 62 79 74 65 28 78 29 20 20 20 28 28 78  et2byte(x)   ((x
6bb0: 29 5b 30 5d 3c 3c 38 20 7c 20 28 78 29 5b 31 5d  )[0]<<8 | (x)[1]
6bc0: 29 0a 23 64 65 66 69 6e 65 20 70 75 74 32 62 79  ).#define put2by
6bd0: 74 65 28 70 2c 76 29 20 28 28 70 29 5b 30 5d 20  te(p,v) ((p)[0] 
6be0: 3d 20 28 75 38 29 28 28 76 29 3e 3e 38 29 2c 20  = (u8)((v)>>8), 
6bf0: 28 70 29 5b 31 5d 20 3d 20 28 75 38 29 28 76 29  (p)[1] = (u8)(v)
6c00: 29 0a 23 64 65 66 69 6e 65 20 67 65 74 34 62 79  ).#define get4by
6c10: 74 65 20 73 71 6c 69 74 65 33 47 65 74 34 62 79  te sqlite3Get4by
6c20: 74 65 0a 23 64 65 66 69 6e 65 20 70 75 74 34 62  te.#define put4b
6c30: 79 74 65 20 73 71 6c 69 74 65 33 50 75 74 34 62  yte sqlite3Put4b
6c40: 79 74 65 0a 0a 2f 2a 0a 2a 2a 20 49 6e 74 65 72  yte../*.** Inter
6c50: 6e 61 6c 20 72 6f 75 74 69 6e 65 73 20 74 68 61  nal routines tha
6c60: 74 20 73 68 6f 75 6c 64 20 62 65 20 61 63 63 65  t should be acce
6c70: 73 73 65 64 20 62 79 20 74 68 65 20 62 74 72 65  ssed by the btre
6c80: 65 20 6c 61 79 65 72 20 6f 6e 6c 79 2e 0a 2a 2f  e layer only..*/
6c90: 0a 69 6e 74 20 73 71 6c 69 74 65 33 42 74 72 65  .int sqlite3Btre
6ca0: 65 47 65 74 50 61 67 65 28 42 74 53 68 61 72 65  eGetPage(BtShare
6cb0: 64 2a 2c 20 50 67 6e 6f 2c 20 4d 65 6d 50 61 67  d*, Pgno, MemPag
6cc0: 65 2a 2a 2c 20 69 6e 74 29 3b 0a 69 6e 74 20 73  e**, int);.int s
6cd0: 71 6c 69 74 65 33 42 74 72 65 65 49 6e 69 74 50  qlite3BtreeInitP
6ce0: 61 67 65 28 4d 65 6d 50 61 67 65 20 2a 70 50 61  age(MemPage *pPa
6cf0: 67 65 29 3b 0a 76 6f 69 64 20 73 71 6c 69 74 65  ge);.void sqlite
6d00: 33 42 74 72 65 65 50 61 72 73 65 43 65 6c 6c 50  3BtreeParseCellP
6d10: 74 72 28 4d 65 6d 50 61 67 65 2a 2c 20 75 38 2a  tr(MemPage*, u8*
6d20: 2c 20 43 65 6c 6c 49 6e 66 6f 2a 29 3b 0a 76 6f  , CellInfo*);.vo
6d30: 69 64 20 73 71 6c 69 74 65 33 42 74 72 65 65 50  id sqlite3BtreeP
6d40: 61 72 73 65 43 65 6c 6c 28 4d 65 6d 50 61 67 65  arseCell(MemPage
6d50: 2a 2c 20 69 6e 74 2c 20 43 65 6c 6c 49 6e 66 6f  *, int, CellInfo
6d60: 2a 29 3b 0a 69 6e 74 20 73 71 6c 69 74 65 33 42  *);.int sqlite3B
6d70: 74 72 65 65 52 65 73 74 6f 72 65 43 75 72 73 6f  treeRestoreCurso
6d80: 72 50 6f 73 69 74 69 6f 6e 28 42 74 43 75 72 73  rPosition(BtCurs
6d90: 6f 72 20 2a 70 43 75 72 29 3b 0a 76 6f 69 64 20  or *pCur);.void 
6da0: 73 71 6c 69 74 65 33 42 74 72 65 65 47 65 74 54  sqlite3BtreeGetT
6db0: 65 6d 70 43 75 72 73 6f 72 28 42 74 43 75 72 73  empCursor(BtCurs
6dc0: 6f 72 20 2a 70 43 75 72 2c 20 42 74 43 75 72 73  or *pCur, BtCurs
6dd0: 6f 72 20 2a 70 54 65 6d 70 43 75 72 29 3b 0a 76  or *pTempCur);.v
6de0: 6f 69 64 20 73 71 6c 69 74 65 33 42 74 72 65 65  oid sqlite3Btree
6df0: 52 65 6c 65 61 73 65 54 65 6d 70 43 75 72 73 6f  ReleaseTempCurso
6e00: 72 28 42 74 43 75 72 73 6f 72 20 2a 70 43 75 72  r(BtCursor *pCur
6e10: 29 3b 0a 76 6f 69 64 20 73 71 6c 69 74 65 33 42  );.void sqlite3B
6e20: 74 72 65 65 4d 6f 76 65 54 6f 50 61 72 65 6e 74  treeMoveToParent
6e30: 28 42 74 43 75 72 73 6f 72 20 2a 70 43 75 72 29  (BtCursor *pCur)
6e40: 3b 0a                                            ;.