/ Hex Artifact Content
Login
SQLite training in Houston TX on 2019-11-05 (details)
Part of the 2019 Tcl Conference

Artifact a568bf057aa249eb06fd31358b4393a5ac88c118:


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 35 31 20 32 30 30 39  nt.h,v 1.51 2009
0190: 2f 30 37 2f 30 39 20 30 35 3a 30 37 3a 33 38 20  /07/09 05:07:38 
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 20 20 20 20 34 30 20  rs.**.**     40 
0d10: 20 20 20 20 20 20 34 20 20 20 20 20 53 63 68 65        4     Sche
0d20: 6d 61 20 63 6f 6f 6b 69 65 0a 2a 2a 20 20 20 20  ma cookie.**    
0d30: 20 34 34 20 20 20 20 20 20 20 34 20 20 20 20 20   44       4     
0d40: 46 69 6c 65 20 66 6f 72 6d 61 74 20 6f 66 20 73  File format of s
0d50: 63 68 65 6d 61 20 6c 61 79 65 72 0a 2a 2a 20 20  chema layer.**  
0d60: 20 20 20 34 38 20 20 20 20 20 20 20 34 20 20 20     48       4   
0d70: 20 20 53 69 7a 65 20 6f 66 20 70 61 67 65 20 63    Size of page c
0d80: 61 63 68 65 0a 2a 2a 20 20 20 20 20 35 32 20 20  ache.**     52  
0d90: 20 20 20 20 20 34 20 20 20 20 20 4c 61 72 67 65       4     Large
0da0: 73 74 20 72 6f 6f 74 2d 70 61 67 65 20 28 61 75  st root-page (au
0db0: 74 6f 2f 69 6e 63 72 5f 76 61 63 75 75 6d 29 0a  to/incr_vacuum).
0dc0: 2a 2a 20 20 20 20 20 35 36 20 20 20 20 20 20 20  **     56       
0dd0: 34 20 20 20 20 20 31 3d 55 54 46 2d 38 20 32 3d  4     1=UTF-8 2=
0de0: 55 54 46 31 36 6c 65 20 33 3d 55 54 46 31 36 62  UTF16le 3=UTF16b
0df0: 65 0a 2a 2a 20 20 20 20 20 36 30 20 20 20 20 20  e.**     60     
0e00: 20 20 34 20 20 20 20 20 55 73 65 72 20 76 65 72    4     User ver
0e10: 73 69 6f 6e 0a 2a 2a 20 20 20 20 20 36 34 20 20  sion.**     64  
0e20: 20 20 20 20 20 34 20 20 20 20 20 49 6e 63 72 65       4     Incre
0e30: 6d 65 6e 74 61 6c 20 76 61 63 75 75 6d 20 6d 6f  mental vacuum mo
0e40: 64 65 0a 2a 2a 20 20 20 20 20 36 38 20 20 20 20  de.**     68    
0e50: 20 20 20 34 20 20 20 20 20 75 6e 75 73 65 64 0a     4     unused.
0e60: 2a 2a 20 20 20 20 20 37 32 20 20 20 20 20 20 20  **     72       
0e70: 34 20 20 20 20 20 75 6e 75 73 65 64 0a 2a 2a 20  4     unused.** 
0e80: 20 20 20 20 37 36 20 20 20 20 20 20 20 34 20 20      76       4  
0e90: 20 20 20 75 6e 75 73 65 64 0a 2a 2a 0a 2a 2a 20     unused.**.** 
0ea0: 41 6c 6c 20 6f 66 20 74 68 65 20 69 6e 74 65 67  All of the integ
0eb0: 65 72 20 76 61 6c 75 65 73 20 61 72 65 20 62 69  er values are bi
0ec0: 67 2d 65 6e 64 69 61 6e 20 28 6d 6f 73 74 20 73  g-endian (most s
0ed0: 69 67 6e 69 66 69 63 61 6e 74 20 62 79 74 65 20  ignificant byte 
0ee0: 66 69 72 73 74 29 2e 0a 2a 2a 0a 2a 2a 20 54 68  first)..**.** Th
0ef0: 65 20 66 69 6c 65 20 63 68 61 6e 67 65 20 63 6f  e file change co
0f00: 75 6e 74 65 72 20 69 73 20 69 6e 63 72 65 6d 65  unter is increme
0f10: 6e 74 65 64 20 77 68 65 6e 20 74 68 65 20 64 61  nted when the da
0f20: 74 61 62 61 73 65 20 69 73 20 63 68 61 6e 67 65  tabase is change
0f30: 64 0a 2a 2a 20 54 68 69 73 20 63 6f 75 6e 74 65  d.** This counte
0f40: 72 20 61 6c 6c 6f 77 73 20 6f 74 68 65 72 20 70  r allows other p
0f50: 72 6f 63 65 73 73 65 73 20 74 6f 20 6b 6e 6f 77  rocesses to know
0f60: 20 77 68 65 6e 20 74 68 65 20 66 69 6c 65 20 68   when the file h
0f70: 61 73 20 63 68 61 6e 67 65 64 0a 2a 2a 20 61 6e  as changed.** an
0f80: 64 20 74 68 75 73 20 77 68 65 6e 20 74 68 65 79  d thus when they
0f90: 20 6e 65 65 64 20 74 6f 20 66 6c 75 73 68 20 74   need to flush t
0fa0: 68 65 69 72 20 63 61 63 68 65 2e 0a 2a 2a 0a 2a  heir cache..**.*
0fb0: 2a 20 54 68 65 20 6d 61 78 20 65 6d 62 65 64 64  * The max embedd
0fc0: 65 64 20 70 61 79 6c 6f 61 64 20 66 72 61 63 74  ed payload fract
0fd0: 69 6f 6e 20 69 73 20 74 68 65 20 61 6d 6f 75 6e  ion is the amoun
0fe0: 74 20 6f 66 20 74 68 65 20 74 6f 74 61 6c 20 75  t of the total u
0ff0: 73 61 62 6c 65 0a 2a 2a 20 73 70 61 63 65 20 69  sable.** space i
1000: 6e 20 61 20 70 61 67 65 20 74 68 61 74 20 63 61  n a page that ca
1010: 6e 20 62 65 20 63 6f 6e 73 75 6d 65 64 20 62 79  n be consumed by
1020: 20 61 20 73 69 6e 67 6c 65 20 63 65 6c 6c 20 66   a single cell f
1030: 6f 72 20 73 74 61 6e 64 61 72 64 0a 2a 2a 20 42  or standard.** B
1040: 2d 74 72 65 65 20 28 6e 6f 6e 2d 4c 45 41 46 44  -tree (non-LEAFD
1050: 41 54 41 29 20 74 61 62 6c 65 73 2e 20 20 41 20  ATA) tables.  A 
1060: 76 61 6c 75 65 20 6f 66 20 32 35 35 20 6d 65 61  value of 255 mea
1070: 6e 73 20 31 30 30 25 2e 20 20 54 68 65 20 64 65  ns 100%.  The de
1080: 66 61 75 6c 74 0a 2a 2a 20 69 73 20 74 6f 20 6c  fault.** is to l
1090: 69 6d 69 74 20 74 68 65 20 6d 61 78 69 6d 75 6d  imit the maximum
10a0: 20 63 65 6c 6c 20 73 69 7a 65 20 73 6f 20 74 68   cell size so th
10b0: 61 74 20 61 74 20 6c 65 61 73 74 20 34 20 63 65  at at least 4 ce
10c0: 6c 6c 73 20 77 69 6c 6c 20 66 69 74 0a 2a 2a 20  lls will fit.** 
10d0: 6f 6e 20 6f 6e 65 20 70 61 67 65 2e 20 20 54 68  on one page.  Th
10e0: 75 73 20 74 68 65 20 64 65 66 61 75 6c 74 20 6d  us the default m
10f0: 61 78 20 65 6d 62 65 64 64 65 64 20 70 61 79 6c  ax embedded payl
1100: 6f 61 64 20 66 72 61 63 74 69 6f 6e 20 69 73 20  oad fraction is 
1110: 36 34 2e 0a 2a 2a 0a 2a 2a 20 49 66 20 74 68 65  64..**.** If the
1120: 20 70 61 79 6c 6f 61 64 20 66 6f 72 20 61 20 63   payload for a c
1130: 65 6c 6c 20 69 73 20 6c 61 72 67 65 72 20 74 68  ell is larger th
1140: 61 6e 20 74 68 65 20 6d 61 78 20 70 61 79 6c 6f  an the max paylo
1150: 61 64 2c 20 74 68 65 6e 20 65 78 74 72 61 0a 2a  ad, then extra.*
1160: 2a 20 70 61 79 6c 6f 61 64 20 69 73 20 73 70 69  * payload is spi
1170: 6c 6c 65 64 20 74 6f 20 6f 76 65 72 66 6c 6f 77  lled to overflow
1180: 20 70 61 67 65 73 2e 20 20 4f 6e 63 65 20 61 6e   pages.  Once an
1190: 20 6f 76 65 72 66 6c 6f 77 20 70 61 67 65 20 69   overflow page i
11a0: 73 20 61 6c 6c 6f 63 61 74 65 64 2c 0a 2a 2a 20  s allocated,.** 
11b0: 61 73 20 6d 61 6e 79 20 62 79 74 65 73 20 61 73  as many bytes as
11c0: 20 70 6f 73 73 69 62 6c 65 20 61 72 65 20 6d 6f   possible are mo
11d0: 76 65 64 20 69 6e 74 6f 20 74 68 65 20 6f 76 65  ved into the ove
11e0: 72 66 6c 6f 77 20 70 61 67 65 73 20 77 69 74 68  rflow pages with
11f0: 6f 75 74 20 6c 65 74 74 69 6e 67 0a 2a 2a 20 74  out letting.** t
1200: 68 65 20 63 65 6c 6c 20 73 69 7a 65 20 64 72 6f  he cell size dro
1210: 70 20 62 65 6c 6f 77 20 74 68 65 20 6d 69 6e 20  p below the min 
1220: 65 6d 62 65 64 64 65 64 20 70 61 79 6c 6f 61 64  embedded payload
1230: 20 66 72 61 63 74 69 6f 6e 2e 0a 2a 2a 0a 2a 2a   fraction..**.**
1240: 20 54 68 65 20 6d 69 6e 20 6c 65 61 66 20 70 61   The min leaf pa
1250: 79 6c 6f 61 64 20 66 72 61 63 74 69 6f 6e 20 69  yload fraction i
1260: 73 20 6c 69 6b 65 20 74 68 65 20 6d 69 6e 20 65  s like the min e
1270: 6d 62 65 64 64 65 64 20 70 61 79 6c 6f 61 64 20  mbedded payload 
1280: 66 72 61 63 74 69 6f 6e 0a 2a 2a 20 65 78 63 65  fraction.** exce
1290: 70 74 20 74 68 61 74 20 69 74 20 61 70 70 6c 69  pt that it appli
12a0: 65 73 20 74 6f 20 6c 65 61 66 20 6e 6f 64 65 73  es to leaf nodes
12b0: 20 69 6e 20 61 20 4c 45 41 46 44 41 54 41 20 74   in a LEAFDATA t
12c0: 72 65 65 2e 20 20 54 68 65 20 6d 61 78 69 6d 75  ree.  The maximu
12d0: 6d 0a 2a 2a 20 70 61 79 6c 6f 61 64 20 66 72 61  m.** payload fra
12e0: 63 74 69 6f 6e 20 66 6f 72 20 61 20 4c 45 41 46  ction for a LEAF
12f0: 44 41 54 41 20 74 72 65 65 20 69 73 20 61 6c 77  DATA tree is alw
1300: 61 79 73 20 31 30 30 25 20 28 6f 72 20 32 35 35  ays 100% (or 255
1310: 29 20 61 6e 64 20 69 74 0a 2a 2a 20 6e 6f 74 20  ) and it.** not 
1320: 73 70 65 63 69 66 69 65 64 20 69 6e 20 74 68 65  specified in the
1330: 20 68 65 61 64 65 72 2e 0a 2a 2a 0a 2a 2a 20 45   header..**.** E
1340: 61 63 68 20 62 74 72 65 65 20 70 61 67 65 73 20  ach btree pages 
1350: 69 73 20 64 69 76 69 64 65 64 20 69 6e 74 6f 20  is divided into 
1360: 74 68 72 65 65 20 73 65 63 74 69 6f 6e 73 3a 20  three sections: 
1370: 20 54 68 65 20 68 65 61 64 65 72 2c 20 74 68 65   The header, the
1380: 0a 2a 2a 20 63 65 6c 6c 20 70 6f 69 6e 74 65 72  .** cell pointer
1390: 20 61 72 72 61 79 2c 20 61 6e 64 20 74 68 65 20   array, and the 
13a0: 63 65 6c 6c 20 63 6f 6e 74 65 6e 74 20 61 72 65  cell content are
13b0: 61 2e 20 20 50 61 67 65 20 31 20 61 6c 73 6f 20  a.  Page 1 also 
13c0: 68 61 73 20 61 20 31 30 30 2d 62 79 74 65 0a 2a  has a 100-byte.*
13d0: 2a 20 66 69 6c 65 20 68 65 61 64 65 72 20 74 68  * file header th
13e0: 61 74 20 6f 63 63 75 72 73 20 62 65 66 6f 72 65  at occurs before
13f0: 20 74 68 65 20 70 61 67 65 20 68 65 61 64 65 72   the page header
1400: 2e 0a 2a 2a 0a 2a 2a 20 20 20 20 20 20 7c 2d 2d  ..**.**      |--
1410: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 7c 0a  --------------|.
1420: 2a 2a 20 20 20 20 20 20 7c 20 66 69 6c 65 20 68  **      | file h
1430: 65 61 64 65 72 20 20 20 20 7c 20 20 20 31 30 30  eader    |   100
1440: 20 62 79 74 65 73 2e 20 20 50 61 67 65 20 31 20   bytes.  Page 1 
1450: 6f 6e 6c 79 2e 0a 2a 2a 20 20 20 20 20 20 7c 2d  only..**      |-
1460: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 7c  ---------------|
1470: 0a 2a 2a 20 20 20 20 20 20 7c 20 70 61 67 65 20  .**      | page 
1480: 68 65 61 64 65 72 20 20 20 20 7c 20 20 20 38 20  header    |   8 
1490: 62 79 74 65 73 20 66 6f 72 20 6c 65 61 76 65 73  bytes for leaves
14a0: 2e 20 20 31 32 20 62 79 74 65 73 20 66 6f 72 20  .  12 bytes for 
14b0: 69 6e 74 65 72 69 6f 72 20 6e 6f 64 65 73 0a 2a  interior nodes.*
14c0: 2a 20 20 20 20 20 20 7c 2d 2d 2d 2d 2d 2d 2d 2d  *      |--------
14d0: 2d 2d 2d 2d 2d 2d 2d 2d 7c 0a 2a 2a 20 20 20 20  --------|.**    
14e0: 20 20 7c 20 63 65 6c 6c 20 70 6f 69 6e 74 65 72    | cell pointer
14f0: 20 20 20 7c 20 20 20 7c 20 20 32 20 62 79 74 65     |   |  2 byte
1500: 73 20 70 65 72 20 63 65 6c 6c 2e 20 20 53 6f 72  s per cell.  Sor
1510: 74 65 64 20 6f 72 64 65 72 2e 0a 2a 2a 20 20 20  ted order..**   
1520: 20 20 20 7c 20 61 72 72 61 79 20 20 20 20 20 20     | array      
1530: 20 20 20 20 7c 20 20 20 7c 20 20 47 72 6f 77 73      |   |  Grows
1540: 20 64 6f 77 6e 77 61 72 64 0a 2a 2a 20 20 20 20   downward.**    
1550: 20 20 7c 20 20 20 20 20 20 20 20 20 20 20 20 20    |             
1560: 20 20 20 7c 20 20 20 76 0a 2a 2a 20 20 20 20 20     |   v.**     
1570: 20 7c 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d   |--------------
1580: 2d 2d 7c 0a 2a 2a 20 20 20 20 20 20 7c 20 75 6e  --|.**      | un
1590: 61 6c 6c 6f 63 61 74 65 64 20 20 20 20 7c 0a 2a  allocated    |.*
15a0: 2a 20 20 20 20 20 20 7c 20 73 70 61 63 65 20 20  *      | space  
15b0: 20 20 20 20 20 20 20 20 7c 0a 2a 2a 20 20 20 20          |.**    
15c0: 20 20 7c 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d    |-------------
15d0: 2d 2d 2d 7c 20 20 20 5e 20 20 47 72 6f 77 73 20  ---|   ^  Grows 
15e0: 75 70 77 61 72 64 73 0a 2a 2a 20 20 20 20 20 20  upwards.**      
15f0: 7c 20 63 65 6c 6c 20 63 6f 6e 74 65 6e 74 20 20  | cell content  
1600: 20 7c 20 20 20 7c 20 20 41 72 62 69 74 72 61 72   |   |  Arbitrar
1610: 79 20 6f 72 64 65 72 20 69 6e 74 65 72 73 70 65  y order interspe
1620: 72 73 65 64 20 77 69 74 68 20 66 72 65 65 62 6c  rsed with freebl
1630: 6f 63 6b 73 2e 0a 2a 2a 20 20 20 20 20 20 7c 20  ocks..**      | 
1640: 61 72 65 61 20 20 20 20 20 20 20 20 20 20 20 7c  area           |
1650: 20 20 20 7c 20 20 61 6e 64 20 66 72 65 65 20 73     |  and free s
1660: 70 61 63 65 20 66 72 61 67 6d 65 6e 74 73 2e 0a  pace fragments..
1670: 2a 2a 20 20 20 20 20 20 7c 2d 2d 2d 2d 2d 2d 2d  **      |-------
1680: 2d 2d 2d 2d 2d 2d 2d 2d 2d 7c 0a 2a 2a 0a 2a 2a  ---------|.**.**
1690: 20 54 68 65 20 70 61 67 65 20 68 65 61 64 65 72   The page header
16a0: 73 20 6c 6f 6f 6b 73 20 6c 69 6b 65 20 74 68 69  s looks like thi
16b0: 73 3a 0a 2a 2a 0a 2a 2a 20 20 20 4f 46 46 53 45  s:.**.**   OFFSE
16c0: 54 20 20 20 53 49 5a 45 20 20 20 20 20 44 45 53  T   SIZE     DES
16d0: 43 52 49 50 54 49 4f 4e 0a 2a 2a 20 20 20 20 20  CRIPTION.**     
16e0: 20 30 20 20 20 20 20 20 20 31 20 20 20 20 20 20   0       1      
16f0: 46 6c 61 67 73 2e 20 31 3a 20 69 6e 74 6b 65 79  Flags. 1: intkey
1700: 2c 20 32 3a 20 7a 65 72 6f 64 61 74 61 2c 20 34  , 2: zerodata, 4
1710: 3a 20 6c 65 61 66 64 61 74 61 2c 20 38 3a 20 6c  : leafdata, 8: l
1720: 65 61 66 0a 2a 2a 20 20 20 20 20 20 31 20 20 20  eaf.**      1   
1730: 20 20 20 20 32 20 20 20 20 20 20 62 79 74 65 20      2      byte 
1740: 6f 66 66 73 65 74 20 74 6f 20 74 68 65 20 66 69  offset to the fi
1750: 72 73 74 20 66 72 65 65 62 6c 6f 63 6b 0a 2a 2a  rst freeblock.**
1760: 20 20 20 20 20 20 33 20 20 20 20 20 20 20 32 20        3       2 
1770: 20 20 20 20 20 6e 75 6d 62 65 72 20 6f 66 20 63       number of c
1780: 65 6c 6c 73 20 6f 6e 20 74 68 69 73 20 70 61 67  ells on this pag
1790: 65 0a 2a 2a 20 20 20 20 20 20 35 20 20 20 20 20  e.**      5     
17a0: 20 20 32 20 20 20 20 20 20 66 69 72 73 74 20 62    2      first b
17b0: 79 74 65 20 6f 66 20 74 68 65 20 63 65 6c 6c 20  yte of the cell 
17c0: 63 6f 6e 74 65 6e 74 20 61 72 65 61 0a 2a 2a 20  content area.** 
17d0: 20 20 20 20 20 37 20 20 20 20 20 20 20 31 20 20       7       1  
17e0: 20 20 20 20 6e 75 6d 62 65 72 20 6f 66 20 66 72      number of fr
17f0: 61 67 6d 65 6e 74 65 64 20 66 72 65 65 20 62 79  agmented free by
1800: 74 65 73 0a 2a 2a 20 20 20 20 20 20 38 20 20 20  tes.**      8   
1810: 20 20 20 20 34 20 20 20 20 20 20 52 69 67 68 74      4      Right
1820: 20 63 68 69 6c 64 20 28 74 68 65 20 50 74 72 28   child (the Ptr(
1830: 4e 29 20 76 61 6c 75 65 29 2e 20 20 4f 6d 69 74  N) value).  Omit
1840: 74 65 64 20 6f 6e 20 6c 65 61 76 65 73 2e 0a 2a  ted on leaves..*
1850: 2a 0a 2a 2a 20 54 68 65 20 66 6c 61 67 73 20 64  *.** The flags d
1860: 65 66 69 6e 65 20 74 68 65 20 66 6f 72 6d 61 74  efine the format
1870: 20 6f 66 20 74 68 69 73 20 62 74 72 65 65 20 70   of this btree p
1880: 61 67 65 2e 20 20 54 68 65 20 6c 65 61 66 20 66  age.  The leaf f
1890: 6c 61 67 20 6d 65 61 6e 73 20 74 68 61 74 0a 2a  lag means that.*
18a0: 2a 20 74 68 69 73 20 70 61 67 65 20 68 61 73 20  * this page has 
18b0: 6e 6f 20 63 68 69 6c 64 72 65 6e 2e 20 20 54 68  no children.  Th
18c0: 65 20 7a 65 72 6f 64 61 74 61 20 66 6c 61 67 20  e zerodata flag 
18d0: 6d 65 61 6e 73 20 74 68 61 74 20 74 68 69 73 20  means that this 
18e0: 70 61 67 65 20 63 61 72 72 69 65 73 0a 2a 2a 20  page carries.** 
18f0: 6f 6e 6c 79 20 6b 65 79 73 20 61 6e 64 20 6e 6f  only keys and no
1900: 20 64 61 74 61 2e 20 20 54 68 65 20 69 6e 74 6b   data.  The intk
1910: 65 79 20 66 6c 61 67 20 6d 65 61 6e 73 20 74 68  ey flag means th
1920: 61 74 20 74 68 65 20 6b 65 79 20 69 73 20 61 20  at the key is a 
1930: 69 6e 74 65 67 65 72 0a 2a 2a 20 77 68 69 63 68  integer.** which
1940: 20 69 73 20 73 74 6f 72 65 64 20 69 6e 20 74 68   is stored in th
1950: 65 20 6b 65 79 20 73 69 7a 65 20 65 6e 74 72 79  e key size entry
1960: 20 6f 66 20 74 68 65 20 63 65 6c 6c 20 68 65 61   of the cell hea
1970: 64 65 72 20 72 61 74 68 65 72 20 74 68 61 6e 20  der rather than 
1980: 69 6e 0a 2a 2a 20 74 68 65 20 70 61 79 6c 6f 61  in.** the payloa
1990: 64 20 61 72 65 61 2e 0a 2a 2a 0a 2a 2a 20 54 68  d area..**.** Th
19a0: 65 20 63 65 6c 6c 20 70 6f 69 6e 74 65 72 20 61  e cell pointer a
19b0: 72 72 61 79 20 62 65 67 69 6e 73 20 6f 6e 20 74  rray begins on t
19c0: 68 65 20 66 69 72 73 74 20 62 79 74 65 20 61 66  he first byte af
19d0: 74 65 72 20 74 68 65 20 70 61 67 65 20 68 65 61  ter the page hea
19e0: 64 65 72 2e 0a 2a 2a 20 54 68 65 20 63 65 6c 6c  der..** The cell
19f0: 20 70 6f 69 6e 74 65 72 20 61 72 72 61 79 20 63   pointer array c
1a00: 6f 6e 74 61 69 6e 73 20 7a 65 72 6f 20 6f 72 20  ontains zero or 
1a10: 6d 6f 72 65 20 32 2d 62 79 74 65 20 6e 75 6d 62  more 2-byte numb
1a20: 65 72 73 20 77 68 69 63 68 20 61 72 65 0a 2a 2a  ers which are.**
1a30: 20 6f 66 66 73 65 74 73 20 66 72 6f 6d 20 74 68   offsets from th
1a40: 65 20 62 65 67 69 6e 6e 69 6e 67 20 6f 66 20 74  e beginning of t
1a50: 68 65 20 70 61 67 65 20 74 6f 20 74 68 65 20 63  he page to the c
1a60: 65 6c 6c 20 63 6f 6e 74 65 6e 74 20 69 6e 20 74  ell content in t
1a70: 68 65 20 63 65 6c 6c 0a 2a 2a 20 63 6f 6e 74 65  he cell.** conte
1a80: 6e 74 20 61 72 65 61 2e 20 20 54 68 65 20 63 65  nt area.  The ce
1a90: 6c 6c 20 70 6f 69 6e 74 65 72 73 20 6f 63 63 75  ll pointers occu
1aa0: 72 20 69 6e 20 73 6f 72 74 65 64 20 6f 72 64 65  r in sorted orde
1ab0: 72 2e 20 20 54 68 65 20 73 79 73 74 65 6d 20 73  r.  The system s
1ac0: 74 72 69 76 65 73 0a 2a 2a 20 74 6f 20 6b 65 65  trives.** to kee
1ad0: 70 20 66 72 65 65 20 73 70 61 63 65 20 61 66 74  p free space aft
1ae0: 65 72 20 74 68 65 20 6c 61 73 74 20 63 65 6c 6c  er the last cell
1af0: 20 70 6f 69 6e 74 65 72 20 73 6f 20 74 68 61 74   pointer so that
1b00: 20 6e 65 77 20 63 65 6c 6c 73 20 63 61 6e 0a 2a   new cells can.*
1b10: 2a 20 62 65 20 65 61 73 69 6c 79 20 61 64 64 65  * be easily adde
1b20: 64 20 77 69 74 68 6f 75 74 20 68 61 76 69 6e 67  d without having
1b30: 20 74 6f 20 64 65 66 72 61 67 6d 65 6e 74 20 74   to defragment t
1b40: 68 65 20 70 61 67 65 2e 0a 2a 2a 0a 2a 2a 20 43  he page..**.** C
1b50: 65 6c 6c 20 63 6f 6e 74 65 6e 74 20 69 73 20 73  ell content is s
1b60: 74 6f 72 65 64 20 61 74 20 74 68 65 20 76 65 72  tored at the ver
1b70: 79 20 65 6e 64 20 6f 66 20 74 68 65 20 70 61 67  y end of the pag
1b80: 65 20 61 6e 64 20 67 72 6f 77 73 20 74 6f 77 61  e and grows towa
1b90: 72 64 20 74 68 65 0a 2a 2a 20 62 65 67 69 6e 6e  rd the.** beginn
1ba0: 69 6e 67 20 6f 66 20 74 68 65 20 70 61 67 65 2e  ing of the page.
1bb0: 0a 2a 2a 0a 2a 2a 20 55 6e 75 73 65 64 20 73 70  .**.** Unused sp
1bc0: 61 63 65 20 77 69 74 68 69 6e 20 74 68 65 20 63  ace within the c
1bd0: 65 6c 6c 20 63 6f 6e 74 65 6e 74 20 61 72 65 61  ell content area
1be0: 20 69 73 20 63 6f 6c 6c 65 63 74 65 64 20 69 6e   is collected in
1bf0: 74 6f 20 61 20 6c 69 6e 6b 65 64 20 6c 69 73 74  to a linked list
1c00: 20 6f 66 0a 2a 2a 20 66 72 65 65 62 6c 6f 63 6b   of.** freeblock
1c10: 73 2e 20 20 45 61 63 68 20 66 72 65 65 62 6c 6f  s.  Each freeblo
1c20: 63 6b 20 69 73 20 61 74 20 6c 65 61 73 74 20 34  ck is at least 4
1c30: 20 62 79 74 65 73 20 69 6e 20 73 69 7a 65 2e 20   bytes in size. 
1c40: 20 54 68 65 20 62 79 74 65 20 6f 66 66 73 65 74   The byte offset
1c50: 0a 2a 2a 20 74 6f 20 74 68 65 20 66 69 72 73 74  .** to the first
1c60: 20 66 72 65 65 62 6c 6f 63 6b 20 69 73 20 67 69   freeblock is gi
1c70: 76 65 6e 20 69 6e 20 74 68 65 20 68 65 61 64 65  ven in the heade
1c80: 72 2e 20 20 46 72 65 65 62 6c 6f 63 6b 73 20 6f  r.  Freeblocks o
1c90: 63 63 75 72 20 69 6e 0a 2a 2a 20 69 6e 63 72 65  ccur in.** incre
1ca0: 61 73 69 6e 67 20 6f 72 64 65 72 2e 20 20 42 65  asing order.  Be
1cb0: 63 61 75 73 65 20 61 20 66 72 65 65 62 6c 6f 63  cause a freebloc
1cc0: 6b 20 6d 75 73 74 20 62 65 20 61 74 20 6c 65 61  k must be at lea
1cd0: 73 74 20 34 20 62 79 74 65 73 20 69 6e 20 73 69  st 4 bytes in si
1ce0: 7a 65 2c 0a 2a 2a 20 61 6e 79 20 67 72 6f 75 70  ze,.** any group
1cf0: 20 6f 66 20 33 20 6f 72 20 66 65 77 65 72 20 75   of 3 or fewer u
1d00: 6e 75 73 65 64 20 62 79 74 65 73 20 69 6e 20 74  nused bytes in t
1d10: 68 65 20 63 65 6c 6c 20 63 6f 6e 74 65 6e 74 20  he cell content 
1d20: 61 72 65 61 20 63 61 6e 6e 6f 74 0a 2a 2a 20 65  area cannot.** e
1d30: 78 69 73 74 20 6f 6e 20 74 68 65 20 66 72 65 65  xist on the free
1d40: 62 6c 6f 63 6b 20 63 68 61 69 6e 2e 20 20 41 20  block chain.  A 
1d50: 67 72 6f 75 70 20 6f 66 20 33 20 6f 72 20 66 65  group of 3 or fe
1d60: 77 65 72 20 66 72 65 65 20 62 79 74 65 73 20 69  wer free bytes i
1d70: 73 20 63 61 6c 6c 65 64 0a 2a 2a 20 61 20 66 72  s called.** a fr
1d80: 61 67 6d 65 6e 74 2e 20 20 54 68 65 20 74 6f 74  agment.  The tot
1d90: 61 6c 20 6e 75 6d 62 65 72 20 6f 66 20 62 79 74  al number of byt
1da0: 65 73 20 69 6e 20 61 6c 6c 20 66 72 61 67 6d 65  es in all fragme
1db0: 6e 74 73 20 69 73 20 72 65 63 6f 72 64 65 64 2e  nts is recorded.
1dc0: 0a 2a 2a 20 69 6e 20 74 68 65 20 70 61 67 65 20  .** in the page 
1dd0: 68 65 61 64 65 72 20 61 74 20 6f 66 66 73 65 74  header at offset
1de0: 20 37 2e 0a 2a 2a 0a 2a 2a 20 20 20 20 53 49 5a   7..**.**    SIZ
1df0: 45 20 20 20 20 44 45 53 43 52 49 50 54 49 4f 4e  E    DESCRIPTION
1e00: 0a 2a 2a 20 20 20 20 20 20 32 20 20 20 20 20 42  .**      2     B
1e10: 79 74 65 20 6f 66 66 73 65 74 20 6f 66 20 74 68  yte offset of th
1e20: 65 20 6e 65 78 74 20 66 72 65 65 62 6c 6f 63 6b  e next freeblock
1e30: 0a 2a 2a 20 20 20 20 20 20 32 20 20 20 20 20 42  .**      2     B
1e40: 79 74 65 73 20 69 6e 20 74 68 69 73 20 66 72 65  ytes in this fre
1e50: 65 62 6c 6f 63 6b 0a 2a 2a 0a 2a 2a 20 43 65 6c  eblock.**.** Cel
1e60: 6c 73 20 61 72 65 20 6f 66 20 76 61 72 69 61 62  ls are of variab
1e70: 6c 65 20 6c 65 6e 67 74 68 2e 20 20 43 65 6c 6c  le length.  Cell
1e80: 73 20 61 72 65 20 73 74 6f 72 65 64 20 69 6e 20  s are stored in 
1e90: 74 68 65 20 63 65 6c 6c 20 63 6f 6e 74 65 6e 74  the cell content
1ea0: 20 61 72 65 61 20 61 74 0a 2a 2a 20 74 68 65 20   area at.** the 
1eb0: 65 6e 64 20 6f 66 20 74 68 65 20 70 61 67 65 2e  end of the page.
1ec0: 20 20 50 6f 69 6e 74 65 72 73 20 74 6f 20 74 68    Pointers to th
1ed0: 65 20 63 65 6c 6c 73 20 61 72 65 20 69 6e 20 74  e cells are in t
1ee0: 68 65 20 63 65 6c 6c 20 70 6f 69 6e 74 65 72 20  he cell pointer 
1ef0: 61 72 72 61 79 0a 2a 2a 20 74 68 61 74 20 69 6d  array.** that im
1f00: 6d 65 64 69 61 74 65 6c 79 20 66 6f 6c 6c 6f 77  mediately follow
1f10: 73 20 74 68 65 20 70 61 67 65 20 68 65 61 64 65  s the page heade
1f20: 72 2e 20 20 43 65 6c 6c 73 20 69 73 20 6e 6f 74  r.  Cells is not
1f30: 20 6e 65 63 65 73 73 61 72 69 6c 79 0a 2a 2a 20   necessarily.** 
1f40: 63 6f 6e 74 69 67 75 6f 75 73 20 6f 72 20 69 6e  contiguous or in
1f50: 20 6f 72 64 65 72 2c 20 62 75 74 20 63 65 6c 6c   order, but cell
1f60: 20 70 6f 69 6e 74 65 72 73 20 61 72 65 20 63 6f   pointers are co
1f70: 6e 74 69 67 75 6f 75 73 20 61 6e 64 20 69 6e 20  ntiguous and in 
1f80: 6f 72 64 65 72 2e 0a 2a 2a 0a 2a 2a 20 43 65 6c  order..**.** Cel
1f90: 6c 20 63 6f 6e 74 65 6e 74 20 6d 61 6b 65 73 20  l content makes 
1fa0: 75 73 65 20 6f 66 20 76 61 72 69 61 62 6c 65 20  use of variable 
1fb0: 6c 65 6e 67 74 68 20 69 6e 74 65 67 65 72 73 2e  length integers.
1fc0: 20 20 41 20 76 61 72 69 61 62 6c 65 0a 2a 2a 20    A variable.** 
1fd0: 6c 65 6e 67 74 68 20 69 6e 74 65 67 65 72 20 69  length integer i
1fe0: 73 20 31 20 74 6f 20 39 20 62 79 74 65 73 20 77  s 1 to 9 bytes w
1ff0: 68 65 72 65 20 74 68 65 20 6c 6f 77 65 72 20 37  here the lower 7
2000: 20 62 69 74 73 20 6f 66 20 65 61 63 68 20 0a 2a   bits of each .*
2010: 2a 20 62 79 74 65 20 61 72 65 20 75 73 65 64 2e  * byte are used.
2020: 20 20 54 68 65 20 69 6e 74 65 67 65 72 20 63 6f    The integer co
2030: 6e 73 69 73 74 73 20 6f 66 20 61 6c 6c 20 62 79  nsists of all by
2040: 74 65 73 20 74 68 61 74 20 68 61 76 65 20 62 69  tes that have bi
2050: 74 20 38 20 73 65 74 20 61 6e 64 0a 2a 2a 20 74  t 8 set and.** t
2060: 68 65 20 66 69 72 73 74 20 62 79 74 65 20 77 69  he first byte wi
2070: 74 68 20 62 69 74 20 38 20 63 6c 65 61 72 2e 20  th bit 8 clear. 
2080: 20 54 68 65 20 6d 6f 73 74 20 73 69 67 6e 69 66   The most signif
2090: 69 63 61 6e 74 20 62 79 74 65 20 6f 66 20 74 68  icant byte of th
20a0: 65 20 69 6e 74 65 67 65 72 0a 2a 2a 20 61 70 70  e integer.** app
20b0: 65 61 72 73 20 66 69 72 73 74 2e 20 20 41 20 76  ears first.  A v
20c0: 61 72 69 61 62 6c 65 2d 6c 65 6e 67 74 68 20 69  ariable-length i
20d0: 6e 74 65 67 65 72 20 6d 61 79 20 6e 6f 74 20 62  nteger may not b
20e0: 65 20 6d 6f 72 65 20 74 68 61 6e 20 39 20 62 79  e more than 9 by
20f0: 74 65 73 20 6c 6f 6e 67 2e 0a 2a 2a 20 41 73 20  tes long..** As 
2100: 61 20 73 70 65 63 69 61 6c 20 63 61 73 65 2c 20  a special case, 
2110: 61 6c 6c 20 38 20 62 79 74 65 73 20 6f 66 20 74  all 8 bytes of t
2120: 68 65 20 39 74 68 20 62 79 74 65 20 61 72 65 20  he 9th byte are 
2130: 75 73 65 64 20 61 73 20 64 61 74 61 2e 20 20 54  used as data.  T
2140: 68 69 73 0a 2a 2a 20 61 6c 6c 6f 77 73 20 61 20  his.** allows a 
2150: 36 34 2d 62 69 74 20 69 6e 74 65 67 65 72 20 74  64-bit integer t
2160: 6f 20 62 65 20 65 6e 63 6f 64 65 64 20 69 6e 20  o be encoded in 
2170: 39 20 62 79 74 65 73 2e 0a 2a 2a 0a 2a 2a 20 20  9 bytes..**.**  
2180: 20 20 30 78 30 30 20 20 20 20 20 20 20 20 20 20    0x00          
2190: 20 20 20 20 20 20 20 20 20 20 20 20 62 65 63 6f              beco
21a0: 6d 65 73 20 20 30 78 30 30 30 30 30 30 30 30 0a  mes  0x00000000.
21b0: 2a 2a 20 20 20 20 30 78 37 66 20 20 20 20 20 20  **    0x7f      
21c0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
21d0: 62 65 63 6f 6d 65 73 20 20 30 78 30 30 30 30 30  becomes  0x00000
21e0: 30 37 66 0a 2a 2a 20 20 20 20 30 78 38 31 20 30  07f.**    0x81 0
21f0: 78 30 30 20 20 20 20 20 20 20 20 20 20 20 20 20  x00             
2200: 20 20 20 20 62 65 63 6f 6d 65 73 20 20 30 78 30      becomes  0x0
2210: 30 30 30 30 30 38 30 0a 2a 2a 20 20 20 20 30 78  0000080.**    0x
2220: 38 32 20 30 78 30 30 20 20 20 20 20 20 20 20 20  82 0x00         
2230: 20 20 20 20 20 20 20 20 62 65 63 6f 6d 65 73 20          becomes 
2240: 20 30 78 30 30 30 30 30 31 30 30 0a 2a 2a 20 20   0x00000100.**  
2250: 20 20 30 78 38 30 20 30 78 37 66 20 20 20 20 20    0x80 0x7f     
2260: 20 20 20 20 20 20 20 20 20 20 20 20 62 65 63 6f              beco
2270: 6d 65 73 20 20 30 78 30 30 30 30 30 30 37 66 0a  mes  0x0000007f.
2280: 2a 2a 20 20 20 20 30 78 38 61 20 30 78 39 31 20  **    0x8a 0x91 
2290: 30 78 64 31 20 30 78 61 63 20 30 78 37 38 20 20  0xd1 0xac 0x78  
22a0: 62 65 63 6f 6d 65 73 20 20 30 78 31 32 33 34 35  becomes  0x12345
22b0: 36 37 38 0a 2a 2a 20 20 20 20 30 78 38 31 20 30  678.**    0x81 0
22c0: 78 38 31 20 30 78 38 31 20 30 78 38 31 20 30 78  x81 0x81 0x81 0x
22d0: 30 31 20 20 62 65 63 6f 6d 65 73 20 20 30 78 31  01  becomes  0x1
22e0: 30 32 30 34 30 38 31 0a 2a 2a 0a 2a 2a 20 56 61  0204081.**.** Va
22f0: 72 69 61 62 6c 65 20 6c 65 6e 67 74 68 20 69 6e  riable length in
2300: 74 65 67 65 72 73 20 61 72 65 20 75 73 65 64 20  tegers are used 
2310: 66 6f 72 20 72 6f 77 69 64 73 20 61 6e 64 20 74  for rowids and t
2320: 6f 20 68 6f 6c 64 20 74 68 65 20 6e 75 6d 62 65  o hold the numbe
2330: 72 20 6f 66 0a 2a 2a 20 62 79 74 65 73 20 6f 66  r of.** bytes of
2340: 20 6b 65 79 20 61 6e 64 20 64 61 74 61 20 69 6e   key and data in
2350: 20 61 20 62 74 72 65 65 20 63 65 6c 6c 2e 0a 2a   a btree cell..*
2360: 2a 0a 2a 2a 20 54 68 65 20 63 6f 6e 74 65 6e 74  *.** The content
2370: 20 6f 66 20 61 20 63 65 6c 6c 20 6c 6f 6f 6b 73   of a cell looks
2380: 20 6c 69 6b 65 20 74 68 69 73 3a 0a 2a 2a 0a 2a   like this:.**.*
2390: 2a 20 20 20 20 53 49 5a 45 20 20 20 20 44 45 53  *    SIZE    DES
23a0: 43 52 49 50 54 49 4f 4e 0a 2a 2a 20 20 20 20 20  CRIPTION.**     
23b0: 20 34 20 20 20 20 20 50 61 67 65 20 6e 75 6d 62   4     Page numb
23c0: 65 72 20 6f 66 20 74 68 65 20 6c 65 66 74 20 63  er of the left c
23d0: 68 69 6c 64 2e 20 4f 6d 69 74 74 65 64 20 69 66  hild. Omitted if
23e0: 20 6c 65 61 66 20 66 6c 61 67 20 69 73 20 73 65   leaf flag is se
23f0: 74 2e 0a 2a 2a 20 20 20 20 20 76 61 72 20 20 20  t..**     var   
2400: 20 4e 75 6d 62 65 72 20 6f 66 20 62 79 74 65 73   Number of bytes
2410: 20 6f 66 20 64 61 74 61 2e 20 4f 6d 69 74 74 65   of data. Omitte
2420: 64 20 69 66 20 74 68 65 20 7a 65 72 6f 64 61 74  d if the zerodat
2430: 61 20 66 6c 61 67 20 69 73 20 73 65 74 2e 0a 2a  a flag is set..*
2440: 2a 20 20 20 20 20 76 61 72 20 20 20 20 4e 75 6d  *     var    Num
2450: 62 65 72 20 6f 66 20 62 79 74 65 73 20 6f 66 20  ber of bytes of 
2460: 6b 65 79 2e 20 4f 72 20 74 68 65 20 6b 65 79 20  key. Or the key 
2470: 69 74 73 65 6c 66 20 69 66 20 69 6e 74 6b 65 79  itself if intkey
2480: 20 66 6c 61 67 20 69 73 20 73 65 74 2e 0a 2a 2a   flag is set..**
2490: 20 20 20 20 20 20 2a 20 20 20 20 20 50 61 79 6c        *     Payl
24a0: 6f 61 64 0a 2a 2a 20 20 20 20 20 20 34 20 20 20  oad.**      4   
24b0: 20 20 46 69 72 73 74 20 70 61 67 65 20 6f 66 20    First page of 
24c0: 74 68 65 20 6f 76 65 72 66 6c 6f 77 20 63 68 61  the overflow cha
24d0: 69 6e 2e 20 20 4f 6d 69 74 74 65 64 20 69 66 20  in.  Omitted if 
24e0: 6e 6f 20 6f 76 65 72 66 6c 6f 77 0a 2a 2a 0a 2a  no overflow.**.*
24f0: 2a 20 4f 76 65 72 66 6c 6f 77 20 70 61 67 65 73  * Overflow pages
2500: 20 66 6f 72 6d 20 61 20 6c 69 6e 6b 65 64 20 6c   form a linked l
2510: 69 73 74 2e 20 20 45 61 63 68 20 70 61 67 65 20  ist.  Each page 
2520: 65 78 63 65 70 74 20 74 68 65 20 6c 61 73 74 20  except the last 
2530: 69 73 20 63 6f 6d 70 6c 65 74 65 6c 79 0a 2a 2a  is completely.**
2540: 20 66 69 6c 6c 65 64 20 77 69 74 68 20 64 61 74   filled with dat
2550: 61 20 28 70 61 67 65 73 69 7a 65 20 2d 20 34 20  a (pagesize - 4 
2560: 62 79 74 65 73 29 2e 20 20 54 68 65 20 6c 61 73  bytes).  The las
2570: 74 20 70 61 67 65 20 63 61 6e 20 68 61 76 65 20  t page can have 
2580: 61 73 20 6c 69 74 74 6c 65 0a 2a 2a 20 61 73 20  as little.** as 
2590: 31 20 62 79 74 65 20 6f 66 20 64 61 74 61 2e 0a  1 byte of data..
25a0: 2a 2a 0a 2a 2a 20 20 20 20 53 49 5a 45 20 20 20  **.**    SIZE   
25b0: 20 44 45 53 43 52 49 50 54 49 4f 4e 0a 2a 2a 20   DESCRIPTION.** 
25c0: 20 20 20 20 20 34 20 20 20 20 20 50 61 67 65 20       4     Page 
25d0: 6e 75 6d 62 65 72 20 6f 66 20 6e 65 78 74 20 6f  number of next o
25e0: 76 65 72 66 6c 6f 77 20 70 61 67 65 0a 2a 2a 20  verflow page.** 
25f0: 20 20 20 20 20 2a 20 20 20 20 20 44 61 74 61 0a       *     Data.
2600: 2a 2a 0a 2a 2a 20 46 72 65 65 6c 69 73 74 20 70  **.** Freelist p
2610: 61 67 65 73 20 63 6f 6d 65 20 69 6e 20 74 77 6f  ages come in two
2620: 20 73 75 62 74 79 70 65 73 3a 20 74 72 75 6e 6b   subtypes: trunk
2630: 20 70 61 67 65 73 20 61 6e 64 20 6c 65 61 66 20   pages and leaf 
2640: 70 61 67 65 73 2e 20 20 54 68 65 0a 2a 2a 20 66  pages.  The.** f
2650: 69 6c 65 20 68 65 61 64 65 72 20 70 6f 69 6e 74  ile header point
2660: 73 20 74 6f 20 74 68 65 20 66 69 72 73 74 20 69  s to the first i
2670: 6e 20 61 20 6c 69 6e 6b 65 64 20 6c 69 73 74 20  n a linked list 
2680: 6f 66 20 74 72 75 6e 6b 20 70 61 67 65 2e 20 20  of trunk page.  
2690: 45 61 63 68 20 74 72 75 6e 6b 0a 2a 2a 20 70 61  Each trunk.** pa
26a0: 67 65 20 70 6f 69 6e 74 73 20 74 6f 20 6d 75 6c  ge points to mul
26b0: 74 69 70 6c 65 20 6c 65 61 66 20 70 61 67 65 73  tiple leaf pages
26c0: 2e 20 20 54 68 65 20 63 6f 6e 74 65 6e 74 20 6f  .  The content o
26d0: 66 20 61 20 6c 65 61 66 20 70 61 67 65 20 69 73  f a leaf page is
26e0: 0a 2a 2a 20 75 6e 73 70 65 63 69 66 69 65 64 2e  .** unspecified.
26f0: 20 20 41 20 74 72 75 6e 6b 20 70 61 67 65 20 6c    A trunk page l
2700: 6f 6f 6b 73 20 6c 69 6b 65 20 74 68 69 73 3a 0a  ooks like this:.
2710: 2a 2a 0a 2a 2a 20 20 20 20 53 49 5a 45 20 20 20  **.**    SIZE   
2720: 20 44 45 53 43 52 49 50 54 49 4f 4e 0a 2a 2a 20   DESCRIPTION.** 
2730: 20 20 20 20 20 34 20 20 20 20 20 50 61 67 65 20       4     Page 
2740: 6e 75 6d 62 65 72 20 6f 66 20 6e 65 78 74 20 74  number of next t
2750: 72 75 6e 6b 20 70 61 67 65 0a 2a 2a 20 20 20 20  runk page.**    
2760: 20 20 34 20 20 20 20 20 4e 75 6d 62 65 72 20 6f    4     Number o
2770: 66 20 6c 65 61 66 20 70 6f 69 6e 74 65 72 73 20  f leaf pointers 
2780: 6f 6e 20 74 68 69 73 20 70 61 67 65 0a 2a 2a 20  on this page.** 
2790: 20 20 20 20 20 2a 20 20 20 20 20 7a 65 72 6f 20       *     zero 
27a0: 6f 72 20 6d 6f 72 65 20 70 61 67 65 73 20 6e 75  or more pages nu
27b0: 6d 62 65 72 73 20 6f 66 20 6c 65 61 76 65 73 0a  mbers of leaves.
27c0: 2a 2f 0a 23 69 6e 63 6c 75 64 65 20 22 73 71 6c  */.#include "sql
27d0: 69 74 65 49 6e 74 2e 68 22 0a 0a 0a 2f 2a 20 54  iteInt.h".../* T
27e0: 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 20 76 61 6c  he following val
27f0: 75 65 20 69 73 20 74 68 65 20 6d 61 78 69 6d 75  ue is the maximu
2800: 6d 20 63 65 6c 6c 20 73 69 7a 65 20 61 73 73 75  m cell size assu
2810: 6d 69 6e 67 20 61 20 6d 61 78 69 6d 75 6d 20 70  ming a maximum p
2820: 61 67 65 0a 2a 2a 20 73 69 7a 65 20 67 69 76 65  age.** size give
2830: 20 61 62 6f 76 65 2e 0a 2a 2f 0a 23 64 65 66 69   above..*/.#defi
2840: 6e 65 20 4d 58 5f 43 45 4c 4c 5f 53 49 5a 45 28  ne MX_CELL_SIZE(
2850: 70 42 74 29 20 20 28 70 42 74 2d 3e 70 61 67 65  pBt)  (pBt->page
2860: 53 69 7a 65 2d 38 29 0a 0a 2f 2a 20 54 68 65 20  Size-8)../* The 
2870: 6d 61 78 69 6d 75 6d 20 6e 75 6d 62 65 72 20 6f  maximum number o
2880: 66 20 63 65 6c 6c 73 20 6f 6e 20 61 20 73 69 6e  f cells on a sin
2890: 67 6c 65 20 70 61 67 65 20 6f 66 20 74 68 65 20  gle page of the 
28a0: 64 61 74 61 62 61 73 65 2e 20 20 54 68 69 73 0a  database.  This.
28b0: 2a 2a 20 61 73 73 75 6d 65 73 20 61 20 6d 69 6e  ** assumes a min
28c0: 69 6d 75 6d 20 63 65 6c 6c 20 73 69 7a 65 20 6f  imum cell size o
28d0: 66 20 36 20 62 79 74 65 73 20 20 28 34 20 62 79  f 6 bytes  (4 by
28e0: 74 65 73 20 66 6f 72 20 74 68 65 20 63 65 6c 6c  tes for the cell
28f0: 20 69 74 73 65 6c 66 0a 2a 2a 20 70 6c 75 73 20   itself.** plus 
2900: 32 20 62 79 74 65 73 20 66 6f 72 20 74 68 65 20  2 bytes for the 
2910: 69 6e 64 65 78 20 74 6f 20 74 68 65 20 63 65 6c  index to the cel
2920: 6c 20 69 6e 20 74 68 65 20 70 61 67 65 20 68 65  l in the page he
2930: 61 64 65 72 29 2e 20 20 53 75 63 68 0a 2a 2a 20  ader).  Such.** 
2940: 73 6d 61 6c 6c 20 63 65 6c 6c 73 20 77 69 6c 6c  small cells will
2950: 20 62 65 20 72 61 72 65 2c 20 62 75 74 20 74 68   be rare, but th
2960: 65 79 20 61 72 65 20 70 6f 73 73 69 62 6c 65 2e  ey are possible.
2970: 0a 2a 2f 0a 23 64 65 66 69 6e 65 20 4d 58 5f 43  .*/.#define MX_C
2980: 45 4c 4c 28 70 42 74 29 20 28 28 70 42 74 2d 3e  ELL(pBt) ((pBt->
2990: 70 61 67 65 53 69 7a 65 2d 38 29 2f 36 29 0a 0a  pageSize-8)/6)..
29a0: 2f 2a 20 46 6f 72 77 61 72 64 20 64 65 63 6c 61  /* Forward decla
29b0: 72 61 74 69 6f 6e 73 20 2a 2f 0a 74 79 70 65 64  rations */.typed
29c0: 65 66 20 73 74 72 75 63 74 20 4d 65 6d 50 61 67  ef struct MemPag
29d0: 65 20 4d 65 6d 50 61 67 65 3b 0a 74 79 70 65 64  e MemPage;.typed
29e0: 65 66 20 73 74 72 75 63 74 20 42 74 4c 6f 63 6b  ef struct BtLock
29f0: 20 42 74 4c 6f 63 6b 3b 0a 0a 2f 2a 0a 2a 2a 20   BtLock;../*.** 
2a00: 54 68 69 73 20 69 73 20 61 20 6d 61 67 69 63 20  This is a magic 
2a10: 73 74 72 69 6e 67 20 74 68 61 74 20 61 70 70 65  string that appe
2a20: 61 72 73 20 61 74 20 74 68 65 20 62 65 67 69 6e  ars at the begin
2a30: 6e 69 6e 67 20 6f 66 20 65 76 65 72 79 0a 2a 2a  ning of every.**
2a40: 20 53 51 4c 69 74 65 20 64 61 74 61 62 61 73 65   SQLite database
2a50: 20 69 6e 20 6f 72 64 65 72 20 74 6f 20 69 64 65   in order to ide
2a60: 6e 74 69 66 79 20 74 68 65 20 66 69 6c 65 20 61  ntify the file a
2a70: 73 20 61 20 72 65 61 6c 20 64 61 74 61 62 61 73  s a real databas
2a80: 65 2e 0a 2a 2a 0a 2a 2a 20 59 6f 75 20 63 61 6e  e..**.** You can
2a90: 20 63 68 61 6e 67 65 20 74 68 69 73 20 76 61 6c   change this val
2aa0: 75 65 20 61 74 20 63 6f 6d 70 69 6c 65 2d 74 69  ue at compile-ti
2ab0: 6d 65 20 62 79 20 73 70 65 63 69 66 79 69 6e 67  me by specifying
2ac0: 20 61 0a 2a 2a 20 2d 44 53 51 4c 49 54 45 5f 46   a.** -DSQLITE_F
2ad0: 49 4c 45 5f 48 45 41 44 45 52 3d 22 2e 2e 2e 22  ILE_HEADER="..."
2ae0: 20 6f 6e 20 74 68 65 20 63 6f 6d 70 69 6c 65 72   on the compiler
2af0: 20 63 6f 6d 6d 61 6e 64 2d 6c 69 6e 65 2e 20 20   command-line.  
2b00: 54 68 65 0a 2a 2a 20 68 65 61 64 65 72 20 6d 75  The.** header mu
2b10: 73 74 20 62 65 20 65 78 61 63 74 6c 79 20 31 36  st be exactly 16
2b20: 20 62 79 74 65 73 20 69 6e 63 6c 75 64 69 6e 67   bytes including
2b30: 20 74 68 65 20 7a 65 72 6f 2d 74 65 72 6d 69 6e   the zero-termin
2b40: 61 74 6f 72 20 73 6f 0a 2a 2a 20 74 68 65 20 73  ator so.** the s
2b50: 74 72 69 6e 67 20 69 74 73 65 6c 66 20 73 68 6f  tring itself sho
2b60: 75 6c 64 20 62 65 20 31 35 20 63 68 61 72 61 63  uld be 15 charac
2b70: 74 65 72 73 20 6c 6f 6e 67 2e 20 20 49 66 20 79  ters long.  If y
2b80: 6f 75 20 63 68 61 6e 67 65 0a 2a 2a 20 74 68 65  ou change.** the
2b90: 20 68 65 61 64 65 72 2c 20 74 68 65 6e 20 79 6f   header, then yo
2ba0: 75 72 20 63 75 73 74 6f 6d 20 6c 69 62 72 61 72  ur custom librar
2bb0: 79 20 77 69 6c 6c 20 6e 6f 74 20 62 65 20 61 62  y will not be ab
2bc0: 6c 65 20 74 6f 20 72 65 61 64 20 0a 2a 2a 20 64  le to read .** d
2bd0: 61 74 61 62 61 73 65 73 20 67 65 6e 65 72 61 74  atabases generat
2be0: 65 64 20 62 79 20 74 68 65 20 73 74 61 6e 64 61  ed by the standa
2bf0: 72 64 20 74 6f 6f 6c 73 20 61 6e 64 20 74 68 65  rd tools and the
2c00: 20 73 74 61 6e 64 61 72 64 20 74 6f 6f 6c 73 0a   standard tools.
2c10: 2a 2a 20 77 69 6c 6c 20 6e 6f 74 20 62 65 20 61  ** will not be a
2c20: 62 6c 65 20 74 6f 20 72 65 61 64 20 64 61 74 61  ble to read data
2c30: 62 61 73 65 73 20 63 72 65 61 74 65 64 20 62 79  bases created by
2c40: 20 79 6f 75 72 20 63 75 73 74 6f 6d 20 6c 69 62   your custom lib
2c50: 72 61 72 79 2e 0a 2a 2f 0a 23 69 66 6e 64 65 66  rary..*/.#ifndef
2c60: 20 53 51 4c 49 54 45 5f 46 49 4c 45 5f 48 45 41   SQLITE_FILE_HEA
2c70: 44 45 52 20 2f 2a 20 31 32 33 34 35 36 37 38 39  DER /* 123456789
2c80: 20 31 32 33 34 35 36 20 2a 2f 0a 23 20 20 64 65   123456 */.#  de
2c90: 66 69 6e 65 20 53 51 4c 49 54 45 5f 46 49 4c 45  fine SQLITE_FILE
2ca0: 5f 48 45 41 44 45 52 20 22 53 51 4c 69 74 65 20  _HEADER "SQLite 
2cb0: 66 6f 72 6d 61 74 20 33 22 0a 23 65 6e 64 69 66  format 3".#endif
2cc0: 0a 0a 2f 2a 0a 2a 2a 20 50 61 67 65 20 74 79 70  ../*.** Page typ
2cd0: 65 20 66 6c 61 67 73 2e 20 20 41 6e 20 4f 52 65  e flags.  An ORe
2ce0: 64 20 63 6f 6d 62 69 6e 61 74 69 6f 6e 20 6f 66  d combination of
2cf0: 20 74 68 65 73 65 20 66 6c 61 67 73 20 61 70 70   these flags app
2d00: 65 61 72 20 61 73 20 74 68 65 0a 2a 2a 20 66 69  ear as the.** fi
2d10: 72 73 74 20 62 79 74 65 20 6f 66 20 6f 6e 2d 64  rst byte of on-d
2d20: 69 73 6b 20 69 6d 61 67 65 20 6f 66 20 65 76 65  isk image of eve
2d30: 72 79 20 42 54 72 65 65 20 70 61 67 65 2e 0a 2a  ry BTree page..*
2d40: 2f 0a 23 64 65 66 69 6e 65 20 50 54 46 5f 49 4e  /.#define PTF_IN
2d50: 54 4b 45 59 20 20 20 20 30 78 30 31 0a 23 64 65  TKEY    0x01.#de
2d60: 66 69 6e 65 20 50 54 46 5f 5a 45 52 4f 44 41 54  fine PTF_ZERODAT
2d70: 41 20 20 30 78 30 32 0a 23 64 65 66 69 6e 65 20  A  0x02.#define 
2d80: 50 54 46 5f 4c 45 41 46 44 41 54 41 20 20 30 78  PTF_LEAFDATA  0x
2d90: 30 34 0a 23 64 65 66 69 6e 65 20 50 54 46 5f 4c  04.#define PTF_L
2da0: 45 41 46 20 20 20 20 20 20 30 78 30 38 0a 0a 2f  EAF      0x08../
2db0: 2a 0a 2a 2a 20 41 73 20 65 61 63 68 20 70 61 67  *.** As each pag
2dc0: 65 20 6f 66 20 74 68 65 20 66 69 6c 65 20 69 73  e of the file is
2dd0: 20 6c 6f 61 64 65 64 20 69 6e 74 6f 20 6d 65 6d   loaded into mem
2de0: 6f 72 79 2c 20 61 6e 20 69 6e 73 74 61 6e 63 65  ory, an instance
2df0: 20 6f 66 20 74 68 65 20 66 6f 6c 6c 6f 77 69 6e   of the followin
2e00: 67 0a 2a 2a 20 73 74 72 75 63 74 75 72 65 20 69  g.** structure i
2e10: 73 20 61 70 70 65 6e 64 65 64 20 61 6e 64 20 69  s appended and i
2e20: 6e 69 74 69 61 6c 69 7a 65 64 20 74 6f 20 7a 65  nitialized to ze
2e30: 72 6f 2e 20 20 54 68 69 73 20 73 74 72 75 63 74  ro.  This struct
2e40: 75 72 65 20 73 74 6f 72 65 73 0a 2a 2a 20 69 6e  ure stores.** in
2e50: 66 6f 72 6d 61 74 69 6f 6e 20 61 62 6f 75 74 20  formation about 
2e60: 74 68 65 20 70 61 67 65 20 74 68 61 74 20 69 73  the page that is
2e70: 20 64 65 63 6f 64 65 64 20 66 72 6f 6d 20 74 68   decoded from th
2e80: 65 20 72 61 77 20 66 69 6c 65 20 70 61 67 65 2e  e raw file page.
2e90: 0a 2a 2a 0a 2a 2a 20 54 68 65 20 70 50 61 72 65  .**.** The pPare
2ea0: 6e 74 20 66 69 65 6c 64 20 70 6f 69 6e 74 73 20  nt field points 
2eb0: 62 61 63 6b 20 74 6f 20 74 68 65 20 70 61 72 65  back to the pare
2ec0: 6e 74 20 70 61 67 65 2e 20 20 54 68 69 73 20 61  nt page.  This a
2ed0: 6c 6c 6f 77 73 20 75 73 20 74 6f 0a 2a 2a 20 77  llows us to.** w
2ee0: 61 6c 6b 20 75 70 20 74 68 65 20 42 54 72 65 65  alk up the BTree
2ef0: 20 66 72 6f 6d 20 61 6e 79 20 6c 65 61 66 20 74   from any leaf t
2f00: 6f 20 74 68 65 20 72 6f 6f 74 2e 20 20 43 61 72  o the root.  Car
2f10: 65 20 6d 75 73 74 20 62 65 20 74 61 6b 65 6e 20  e must be taken 
2f20: 74 6f 0a 2a 2a 20 75 6e 72 65 66 28 29 20 74 68  to.** unref() th
2f30: 65 20 70 61 72 65 6e 74 20 70 61 67 65 20 70 6f  e parent page po
2f40: 69 6e 74 65 72 20 77 68 65 6e 20 74 68 69 73 20  inter when this 
2f50: 70 61 67 65 20 69 73 20 6e 6f 20 6c 6f 6e 67 65  page is no longe
2f60: 72 20 72 65 66 65 72 65 6e 63 65 64 2e 0a 2a 2a  r referenced..**
2f70: 20 54 68 65 20 70 61 67 65 44 65 73 74 72 75 63   The pageDestruc
2f80: 74 6f 72 28 29 20 72 6f 75 74 69 6e 65 20 68 61  tor() routine ha
2f90: 6e 64 6c 65 73 20 74 68 61 74 20 63 68 6f 72 65  ndles that chore
2fa0: 2e 0a 2a 2a 0a 2a 2a 20 41 63 63 65 73 73 20 74  ..**.** Access t
2fb0: 6f 20 61 6c 6c 20 66 69 65 6c 64 73 20 6f 66 20  o all fields of 
2fc0: 74 68 69 73 20 73 74 72 75 63 74 75 72 65 20 69  this structure i
2fd0: 73 20 63 6f 6e 74 72 6f 6c 6c 65 64 20 62 79 20  s controlled by 
2fe0: 74 68 65 20 6d 75 74 65 78 0a 2a 2a 20 73 74 6f  the mutex.** sto
2ff0: 72 65 64 20 69 6e 20 4d 65 6d 50 61 67 65 2e 70  red in MemPage.p
3000: 42 74 2d 3e 6d 75 74 65 78 2e 0a 2a 2f 0a 73 74  Bt->mutex..*/.st
3010: 72 75 63 74 20 4d 65 6d 50 61 67 65 20 7b 0a 20  ruct MemPage {. 
3020: 20 75 38 20 69 73 49 6e 69 74 3b 20 20 20 20 20   u8 isInit;     
3030: 20 20 20 20 20 20 2f 2a 20 54 72 75 65 20 69 66        /* True if
3040: 20 70 72 65 76 69 6f 75 73 6c 79 20 69 6e 69 74   previously init
3050: 69 61 6c 69 7a 65 64 2e 20 4d 55 53 54 20 42 45  ialized. MUST BE
3060: 20 46 49 52 53 54 21 20 2a 2f 0a 20 20 75 38 20   FIRST! */.  u8 
3070: 6e 4f 76 65 72 66 6c 6f 77 3b 20 20 20 20 20 20  nOverflow;      
3080: 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 6f    /* Number of o
3090: 76 65 72 66 6c 6f 77 20 63 65 6c 6c 20 62 6f 64  verflow cell bod
30a0: 69 65 73 20 69 6e 20 61 43 65 6c 6c 5b 5d 20 2a  ies in aCell[] *
30b0: 2f 0a 20 20 75 38 20 69 6e 74 4b 65 79 3b 20 20  /.  u8 intKey;  
30c0: 20 20 20 20 20 20 20 20 20 2f 2a 20 54 72 75 65           /* True
30d0: 20 69 66 20 69 6e 74 6b 65 79 20 66 6c 61 67 20   if intkey flag 
30e0: 69 73 20 73 65 74 20 2a 2f 0a 20 20 75 38 20 6c  is set */.  u8 l
30f0: 65 61 66 3b 20 20 20 20 20 20 20 20 20 20 20 20  eaf;            
3100: 20 2f 2a 20 54 72 75 65 20 69 66 20 6c 65 61 66   /* True if leaf
3110: 20 66 6c 61 67 20 69 73 20 73 65 74 20 2a 2f 0a   flag is set */.
3120: 20 20 75 38 20 68 61 73 44 61 74 61 3b 20 20 20    u8 hasData;   
3130: 20 20 20 20 20 20 20 2f 2a 20 54 72 75 65 20 69         /* True i
3140: 66 20 74 68 69 73 20 70 61 67 65 20 73 74 6f 72  f this page stor
3150: 65 73 20 64 61 74 61 20 2a 2f 0a 20 20 75 38 20  es data */.  u8 
3160: 68 64 72 4f 66 66 73 65 74 3b 20 20 20 20 20 20  hdrOffset;      
3170: 20 20 2f 2a 20 31 30 30 20 66 6f 72 20 70 61 67    /* 100 for pag
3180: 65 20 31 2e 20 20 30 20 6f 74 68 65 72 77 69 73  e 1.  0 otherwis
3190: 65 20 2a 2f 0a 20 20 75 38 20 63 68 69 6c 64 50  e */.  u8 childP
31a0: 74 72 53 69 7a 65 3b 20 20 20 20 20 2f 2a 20 30  trSize;     /* 0
31b0: 20 69 66 20 6c 65 61 66 3d 3d 31 2e 20 20 34 20   if leaf==1.  4 
31c0: 69 66 20 6c 65 61 66 3d 3d 30 20 2a 2f 0a 20 20  if leaf==0 */.  
31d0: 75 31 36 20 6d 61 78 4c 6f 63 61 6c 3b 20 20 20  u16 maxLocal;   
31e0: 20 20 20 20 20 2f 2a 20 43 6f 70 79 20 6f 66 20       /* Copy of 
31f0: 42 74 53 68 61 72 65 64 2e 6d 61 78 4c 6f 63 61  BtShared.maxLoca
3200: 6c 20 6f 72 20 42 74 53 68 61 72 65 64 2e 6d 61  l or BtShared.ma
3210: 78 4c 65 61 66 20 2a 2f 0a 20 20 75 31 36 20 6d  xLeaf */.  u16 m
3220: 69 6e 4c 6f 63 61 6c 3b 20 20 20 20 20 20 20 20  inLocal;        
3230: 2f 2a 20 43 6f 70 79 20 6f 66 20 42 74 53 68 61  /* Copy of BtSha
3240: 72 65 64 2e 6d 69 6e 4c 6f 63 61 6c 20 6f 72 20  red.minLocal or 
3250: 42 74 53 68 61 72 65 64 2e 6d 69 6e 4c 65 61 66  BtShared.minLeaf
3260: 20 2a 2f 0a 20 20 75 31 36 20 63 65 6c 6c 4f 66   */.  u16 cellOf
3270: 66 73 65 74 3b 20 20 20 20 20 20 2f 2a 20 49 6e  fset;      /* In
3280: 64 65 78 20 69 6e 20 61 44 61 74 61 20 6f 66 20  dex in aData of 
3290: 66 69 72 73 74 20 63 65 6c 6c 20 70 6f 69 6e 74  first cell point
32a0: 65 72 20 2a 2f 0a 20 20 75 31 36 20 6e 46 72 65  er */.  u16 nFre
32b0: 65 3b 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20  e;           /* 
32c0: 4e 75 6d 62 65 72 20 6f 66 20 66 72 65 65 20 62  Number of free b
32d0: 79 74 65 73 20 6f 6e 20 74 68 65 20 70 61 67 65  ytes on the page
32e0: 20 2a 2f 0a 20 20 75 31 36 20 6e 43 65 6c 6c 3b   */.  u16 nCell;
32f0: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4e 75             /* Nu
3300: 6d 62 65 72 20 6f 66 20 63 65 6c 6c 73 20 6f 6e  mber of cells on
3310: 20 74 68 69 73 20 70 61 67 65 2c 20 6c 6f 63 61   this page, loca
3320: 6c 20 61 6e 64 20 6f 76 66 6c 20 2a 2f 0a 20 20  l and ovfl */.  
3330: 75 31 36 20 6d 61 73 6b 50 61 67 65 3b 20 20 20  u16 maskPage;   
3340: 20 20 20 20 20 2f 2a 20 4d 61 73 6b 20 66 6f 72       /* Mask for
3350: 20 70 61 67 65 20 6f 66 66 73 65 74 20 2a 2f 0a   page offset */.
3360: 20 20 73 74 72 75 63 74 20 5f 4f 76 66 6c 43 65    struct _OvflCe
3370: 6c 6c 20 7b 20 20 20 2f 2a 20 43 65 6c 6c 73 20  ll {   /* Cells 
3380: 74 68 61 74 20 77 69 6c 6c 20 6e 6f 74 20 66 69  that will not fi
3390: 74 20 6f 6e 20 61 44 61 74 61 5b 5d 20 2a 2f 0a  t on aData[] */.
33a0: 20 20 20 20 75 38 20 2a 70 43 65 6c 6c 3b 20 20      u8 *pCell;  
33b0: 20 20 20 20 20 20 20 20 2f 2a 20 50 6f 69 6e 74          /* Point
33c0: 65 72 73 20 74 6f 20 74 68 65 20 62 6f 64 79 20  ers to the body 
33d0: 6f 66 20 74 68 65 20 6f 76 65 72 66 6c 6f 77 20  of the overflow 
33e0: 63 65 6c 6c 20 2a 2f 0a 20 20 20 20 75 31 36 20  cell */.    u16 
33f0: 69 64 78 3b 20 20 20 20 20 20 20 20 20 20 20 20  idx;            
3400: 2f 2a 20 49 6e 73 65 72 74 20 74 68 69 73 20 63  /* Insert this c
3410: 65 6c 6c 20 62 65 66 6f 72 65 20 69 64 78 2d 74  ell before idx-t
3420: 68 20 6e 6f 6e 2d 6f 76 65 72 66 6c 6f 77 20 63  h non-overflow c
3430: 65 6c 6c 20 2a 2f 0a 20 20 7d 20 61 4f 76 66 6c  ell */.  } aOvfl
3440: 5b 35 5d 3b 0a 20 20 42 74 53 68 61 72 65 64 20  [5];.  BtShared 
3450: 2a 70 42 74 3b 20 20 20 20 20 20 20 2f 2a 20 50  *pBt;       /* P
3460: 6f 69 6e 74 65 72 20 74 6f 20 42 74 53 68 61 72  ointer to BtShar
3470: 65 64 20 74 68 61 74 20 74 68 69 73 20 70 61 67  ed that this pag
3480: 65 20 69 73 20 70 61 72 74 20 6f 66 20 2a 2f 0a  e is part of */.
3490: 20 20 75 38 20 2a 61 44 61 74 61 3b 20 20 20 20    u8 *aData;    
34a0: 20 20 20 20 20 20 20 2f 2a 20 50 6f 69 6e 74 65         /* Pointe
34b0: 72 20 74 6f 20 64 69 73 6b 20 69 6d 61 67 65 20  r to disk image 
34c0: 6f 66 20 74 68 65 20 70 61 67 65 20 64 61 74 61  of the page data
34d0: 20 2a 2f 0a 20 20 44 62 50 61 67 65 20 2a 70 44   */.  DbPage *pD
34e0: 62 50 61 67 65 3b 20 20 20 20 20 2f 2a 20 50 61  bPage;     /* Pa
34f0: 67 65 72 20 70 61 67 65 20 68 61 6e 64 6c 65 20  ger page handle 
3500: 2a 2f 0a 20 20 50 67 6e 6f 20 70 67 6e 6f 3b 20  */.  Pgno pgno; 
3510: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 50 61 67            /* Pag
3520: 65 20 6e 75 6d 62 65 72 20 66 6f 72 20 74 68 69  e number for thi
3530: 73 20 70 61 67 65 20 2a 2f 0a 7d 3b 0a 0a 2f 2a  s page */.};../*
3540: 0a 2a 2a 20 54 68 65 20 69 6e 2d 6d 65 6d 6f 72  .** The in-memor
3550: 79 20 69 6d 61 67 65 20 6f 66 20 61 20 64 69 73  y image of a dis
3560: 6b 20 70 61 67 65 20 68 61 73 20 74 68 65 20 61  k page has the a
3570: 75 78 69 6c 69 61 72 79 20 69 6e 66 6f 72 6d 61  uxiliary informa
3580: 74 69 6f 6e 20 61 70 70 65 6e 64 65 64 0a 2a 2a  tion appended.**
3590: 20 74 6f 20 74 68 65 20 65 6e 64 2e 20 20 45 58   to the end.  EX
35a0: 54 52 41 5f 53 49 5a 45 20 69 73 20 74 68 65 20  TRA_SIZE is the 
35b0: 6e 75 6d 62 65 72 20 6f 66 20 62 79 74 65 73 20  number of bytes 
35c0: 6f 66 20 73 70 61 63 65 20 6e 65 65 64 65 64 20  of space needed 
35d0: 74 6f 20 68 6f 6c 64 0a 2a 2a 20 74 68 61 74 20  to hold.** that 
35e0: 65 78 74 72 61 20 69 6e 66 6f 72 6d 61 74 69 6f  extra informatio
35f0: 6e 2e 0a 2a 2f 0a 23 64 65 66 69 6e 65 20 45 58  n..*/.#define EX
3600: 54 52 41 5f 53 49 5a 45 20 73 69 7a 65 6f 66 28  TRA_SIZE sizeof(
3610: 4d 65 6d 50 61 67 65 29 0a 0a 2f 2a 0a 2a 2a 20  MemPage)../*.** 
3620: 41 20 6c 69 6e 6b 65 64 20 6c 69 73 74 20 6f 66  A linked list of
3630: 20 74 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 20 73   the following s
3640: 74 72 75 63 74 75 72 65 73 20 69 73 20 73 74 6f  tructures is sto
3650: 72 65 64 20 61 74 20 42 74 53 68 61 72 65 64 2e  red at BtShared.
3660: 70 4c 6f 63 6b 2e 0a 2a 2a 20 4c 6f 63 6b 73 20  pLock..** Locks 
3670: 61 72 65 20 61 64 64 65 64 20 28 6f 72 20 75 70  are added (or up
3680: 67 72 61 64 65 64 20 66 72 6f 6d 20 52 45 41 44  graded from READ
3690: 5f 4c 4f 43 4b 20 74 6f 20 57 52 49 54 45 5f 4c  _LOCK to WRITE_L
36a0: 4f 43 4b 29 20 77 68 65 6e 20 61 20 63 75 72 73  OCK) when a curs
36b0: 6f 72 20 0a 2a 2a 20 69 73 20 6f 70 65 6e 65 64  or .** is opened
36c0: 20 6f 6e 20 74 68 65 20 74 61 62 6c 65 20 77 69   on the table wi
36d0: 74 68 20 72 6f 6f 74 20 70 61 67 65 20 42 74 53  th root page BtS
36e0: 68 61 72 65 64 2e 69 54 61 62 6c 65 2e 20 4c 6f  hared.iTable. Lo
36f0: 63 6b 73 20 61 72 65 20 72 65 6d 6f 76 65 64 0a  cks are removed.
3700: 2a 2a 20 66 72 6f 6d 20 74 68 69 73 20 6c 69 73  ** from this lis
3710: 74 20 77 68 65 6e 20 61 20 74 72 61 6e 73 61 63  t when a transac
3720: 74 69 6f 6e 20 69 73 20 63 6f 6d 6d 69 74 74 65  tion is committe
3730: 64 20 6f 72 20 72 6f 6c 6c 65 64 20 62 61 63 6b  d or rolled back
3740: 2c 20 6f 72 20 77 68 65 6e 0a 2a 2a 20 61 20 62  , or when.** a b
3750: 74 72 65 65 20 68 61 6e 64 6c 65 20 69 73 20 63  tree handle is c
3760: 6c 6f 73 65 64 2e 0a 2a 2f 0a 73 74 72 75 63 74  losed..*/.struct
3770: 20 42 74 4c 6f 63 6b 20 7b 0a 20 20 42 74 72 65   BtLock {.  Btre
3780: 65 20 2a 70 42 74 72 65 65 3b 20 20 20 20 20 20  e *pBtree;      
3790: 20 20 2f 2a 20 42 74 72 65 65 20 68 61 6e 64 6c    /* Btree handl
37a0: 65 20 68 6f 6c 64 69 6e 67 20 74 68 69 73 20 6c  e holding this l
37b0: 6f 63 6b 20 2a 2f 0a 20 20 50 67 6e 6f 20 69 54  ock */.  Pgno iT
37c0: 61 62 6c 65 3b 20 20 20 20 20 20 20 20 20 20 2f  able;          /
37d0: 2a 20 52 6f 6f 74 20 70 61 67 65 20 6f 66 20 74  * Root page of t
37e0: 61 62 6c 65 20 2a 2f 0a 20 20 75 38 20 65 4c 6f  able */.  u8 eLo
37f0: 63 6b 3b 20 20 20 20 20 20 20 20 20 20 20 20 20  ck;             
3800: 2f 2a 20 52 45 41 44 5f 4c 4f 43 4b 20 6f 72 20  /* READ_LOCK or 
3810: 57 52 49 54 45 5f 4c 4f 43 4b 20 2a 2f 0a 20 20  WRITE_LOCK */.  
3820: 42 74 4c 6f 63 6b 20 2a 70 4e 65 78 74 3b 20 20  BtLock *pNext;  
3830: 20 20 20 20 20 20 2f 2a 20 4e 65 78 74 20 69 6e        /* Next in
3840: 20 42 74 53 68 61 72 65 64 2e 70 4c 6f 63 6b 20   BtShared.pLock 
3850: 6c 69 73 74 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 20 43  list */.};../* C
3860: 61 6e 64 69 64 61 74 65 20 76 61 6c 75 65 73 20  andidate values 
3870: 66 6f 72 20 42 74 4c 6f 63 6b 2e 65 4c 6f 63 6b  for BtLock.eLock
3880: 20 2a 2f 0a 23 64 65 66 69 6e 65 20 52 45 41 44   */.#define READ
3890: 5f 4c 4f 43 4b 20 20 20 20 20 31 0a 23 64 65 66  _LOCK     1.#def
38a0: 69 6e 65 20 57 52 49 54 45 5f 4c 4f 43 4b 20 20  ine WRITE_LOCK  
38b0: 20 20 32 0a 0a 2f 2a 20 41 20 42 74 72 65 65 20    2../* A Btree 
38c0: 68 61 6e 64 6c 65 0a 2a 2a 0a 2a 2a 20 41 20 64  handle.**.** A d
38d0: 61 74 61 62 61 73 65 20 63 6f 6e 6e 65 63 74 69  atabase connecti
38e0: 6f 6e 20 63 6f 6e 74 61 69 6e 73 20 61 20 70 6f  on contains a po
38f0: 69 6e 74 65 72 20 74 6f 20 61 6e 20 69 6e 73 74  inter to an inst
3900: 61 6e 63 65 20 6f 66 0a 2a 2a 20 74 68 69 73 20  ance of.** this 
3910: 6f 62 6a 65 63 74 20 66 6f 72 20 65 76 65 72 79  object for every
3920: 20 64 61 74 61 62 61 73 65 20 66 69 6c 65 20 74   database file t
3930: 68 61 74 20 69 74 20 68 61 73 20 6f 70 65 6e 2e  hat it has open.
3940: 20 20 54 68 69 73 20 73 74 72 75 63 74 75 72 65    This structure
3950: 0a 2a 2a 20 69 73 20 6f 70 61 71 75 65 20 74 6f  .** is opaque to
3960: 20 74 68 65 20 64 61 74 61 62 61 73 65 20 63 6f   the database co
3970: 6e 6e 65 63 74 69 6f 6e 2e 20 20 54 68 65 20 64  nnection.  The d
3980: 61 74 61 62 61 73 65 20 63 6f 6e 6e 65 63 74 69  atabase connecti
3990: 6f 6e 20 63 61 6e 6e 6f 74 0a 2a 2a 20 73 65 65  on cannot.** see
39a0: 20 74 68 65 20 69 6e 74 65 72 6e 61 6c 73 20 6f   the internals o
39b0: 66 20 74 68 69 73 20 73 74 72 75 63 74 75 72 65  f this structure
39c0: 20 61 6e 64 20 6f 6e 6c 79 20 64 65 61 6c 73 20   and only deals 
39d0: 77 69 74 68 20 70 6f 69 6e 74 65 72 73 20 74 6f  with pointers to
39e0: 0a 2a 2a 20 74 68 69 73 20 73 74 72 75 63 74 75  .** this structu
39f0: 72 65 2e 0a 2a 2a 0a 2a 2a 20 46 6f 72 20 73 6f  re..**.** For so
3a00: 6d 65 20 64 61 74 61 62 61 73 65 20 66 69 6c 65  me database file
3a10: 73 2c 20 74 68 65 20 73 61 6d 65 20 75 6e 64 65  s, the same unde
3a20: 72 6c 79 69 6e 67 20 64 61 74 61 62 61 73 65 20  rlying database 
3a30: 63 61 63 68 65 20 6d 69 67 68 74 20 62 65 20 0a  cache might be .
3a40: 2a 2a 20 73 68 61 72 65 64 20 62 65 74 77 65 65  ** shared betwee
3a50: 6e 20 6d 75 6c 74 69 70 6c 65 20 63 6f 6e 6e 65  n multiple conne
3a60: 63 74 69 6f 6e 73 2e 20 20 49 6e 20 74 68 61 74  ctions.  In that
3a70: 20 63 61 73 65 2c 20 65 61 63 68 20 63 6f 6e 74   case, each cont
3a80: 65 63 74 69 6f 6e 0a 2a 2a 20 68 61 73 20 69 74  ection.** has it
3a90: 20 6f 77 6e 20 70 6f 69 6e 74 65 72 20 74 6f 20   own pointer to 
3aa0: 74 68 69 73 20 6f 62 6a 65 63 74 2e 20 20 42 75  this object.  Bu
3ab0: 74 20 65 61 63 68 20 69 6e 73 74 61 6e 63 65 20  t each instance 
3ac0: 6f 66 20 74 68 69 73 20 6f 62 6a 65 63 74 0a 2a  of this object.*
3ad0: 2a 20 70 6f 69 6e 74 73 20 74 6f 20 74 68 65 20  * points to the 
3ae0: 73 61 6d 65 20 42 74 53 68 61 72 65 64 20 6f 62  same BtShared ob
3af0: 6a 65 63 74 2e 20 20 54 68 65 20 64 61 74 61 62  ject.  The datab
3b00: 61 73 65 20 63 61 63 68 65 20 61 6e 64 20 74 68  ase cache and th
3b10: 65 0a 2a 2a 20 73 63 68 65 6d 61 20 61 73 73 6f  e.** schema asso
3b20: 63 69 61 74 65 64 20 77 69 74 68 20 74 68 65 20  ciated with the 
3b30: 64 61 74 61 62 61 73 65 20 66 69 6c 65 20 61 72  database file ar
3b40: 65 20 61 6c 6c 20 63 6f 6e 74 61 69 6e 65 64 20  e all contained 
3b50: 77 69 74 68 69 6e 0a 2a 2a 20 74 68 65 20 42 74  within.** the Bt
3b60: 53 68 61 72 65 64 20 6f 62 6a 65 63 74 2e 0a 2a  Shared object..*
3b70: 2a 0a 2a 2a 20 41 6c 6c 20 66 69 65 6c 64 73 20  *.** All fields 
3b80: 69 6e 20 74 68 69 73 20 73 74 72 75 63 74 75 72  in this structur
3b90: 65 20 61 72 65 20 61 63 63 65 73 73 65 64 20 75  e are accessed u
3ba0: 6e 64 65 72 20 73 71 6c 69 74 65 33 2e 6d 75 74  nder sqlite3.mut
3bb0: 65 78 2e 0a 2a 2a 20 54 68 65 20 70 42 74 20 70  ex..** The pBt p
3bc0: 6f 69 6e 74 65 72 20 69 74 73 65 6c 66 20 6d 61  ointer itself ma
3bd0: 79 20 6e 6f 74 20 62 65 20 63 68 61 6e 67 65 64  y not be changed
3be0: 20 77 68 69 6c 65 20 74 68 65 72 65 20 65 78 69   while there exi
3bf0: 73 74 73 20 63 75 72 73 6f 72 73 20 0a 2a 2a 20  sts cursors .** 
3c00: 69 6e 20 74 68 65 20 72 65 66 65 72 65 6e 63 65  in the reference
3c10: 64 20 42 74 53 68 61 72 65 64 20 74 68 61 74 20  d BtShared that 
3c20: 70 6f 69 6e 74 20 62 61 63 6b 20 74 6f 20 74 68  point back to th
3c30: 69 73 20 42 74 72 65 65 20 73 69 6e 63 65 20 74  is Btree since t
3c40: 68 6f 73 65 0a 2a 2a 20 63 75 72 73 6f 72 73 20  hose.** cursors 
3c50: 68 61 76 65 20 74 6f 20 64 6f 20 67 6f 20 74 68  have to do go th
3c60: 72 6f 75 67 68 20 74 68 69 73 20 42 74 72 65 65  rough this Btree
3c70: 20 74 6f 20 66 69 6e 64 20 74 68 65 69 72 20 42   to find their B
3c80: 74 53 68 61 72 65 64 20 61 6e 64 0a 2a 2a 20 74  tShared and.** t
3c90: 68 65 79 20 6f 66 74 65 6e 20 64 6f 20 73 6f 20  hey often do so 
3ca0: 77 69 74 68 6f 75 74 20 68 6f 6c 64 69 6e 67 20  without holding 
3cb0: 73 71 6c 69 74 65 33 2e 6d 75 74 65 78 2e 0a 2a  sqlite3.mutex..*
3cc0: 2f 0a 73 74 72 75 63 74 20 42 74 72 65 65 20 7b  /.struct Btree {
3cd0: 0a 20 20 73 71 6c 69 74 65 33 20 2a 64 62 3b 20  .  sqlite3 *db; 
3ce0: 20 20 20 20 20 20 2f 2a 20 54 68 65 20 64 61 74        /* The dat
3cf0: 61 62 61 73 65 20 63 6f 6e 6e 65 63 74 69 6f 6e  abase connection
3d00: 20 68 6f 6c 64 69 6e 67 20 74 68 69 73 20 62 74   holding this bt
3d10: 72 65 65 20 2a 2f 0a 20 20 42 74 53 68 61 72 65  ree */.  BtShare
3d20: 64 20 2a 70 42 74 3b 20 20 20 20 20 2f 2a 20 53  d *pBt;     /* S
3d30: 68 61 72 61 62 6c 65 20 63 6f 6e 74 65 6e 74 20  harable content 
3d40: 6f 66 20 74 68 69 73 20 62 74 72 65 65 20 2a 2f  of this btree */
3d50: 0a 20 20 75 38 20 69 6e 54 72 61 6e 73 3b 20 20  .  u8 inTrans;  
3d60: 20 20 20 20 20 20 2f 2a 20 54 52 41 4e 53 5f 4e        /* TRANS_N
3d70: 4f 4e 45 2c 20 54 52 41 4e 53 5f 52 45 41 44 20  ONE, TRANS_READ 
3d80: 6f 72 20 54 52 41 4e 53 5f 57 52 49 54 45 20 2a  or TRANS_WRITE *
3d90: 2f 0a 20 20 75 38 20 73 68 61 72 61 62 6c 65 3b  /.  u8 sharable;
3da0: 20 20 20 20 20 20 20 2f 2a 20 54 72 75 65 20 69         /* True i
3db0: 66 20 77 65 20 63 61 6e 20 73 68 61 72 65 20 70  f we can share p
3dc0: 42 74 20 77 69 74 68 20 61 6e 6f 74 68 65 72 20  Bt with another 
3dd0: 64 62 20 2a 2f 0a 20 20 75 38 20 6c 6f 63 6b 65  db */.  u8 locke
3de0: 64 3b 20 20 20 20 20 20 20 20 20 2f 2a 20 54 72  d;         /* Tr
3df0: 75 65 20 69 66 20 64 62 20 63 75 72 72 65 6e 74  ue if db current
3e00: 6c 79 20 68 61 73 20 70 42 74 20 6c 6f 63 6b 65  ly has pBt locke
3e10: 64 20 2a 2f 0a 20 20 69 6e 74 20 77 61 6e 74 54  d */.  int wantT
3e20: 6f 4c 6f 63 6b 3b 20 20 20 20 2f 2a 20 4e 75 6d  oLock;    /* Num
3e30: 62 65 72 20 6f 66 20 6e 65 73 74 65 64 20 63 61  ber of nested ca
3e40: 6c 6c 73 20 74 6f 20 73 71 6c 69 74 65 33 42 74  lls to sqlite3Bt
3e50: 72 65 65 45 6e 74 65 72 28 29 20 2a 2f 0a 20 20  reeEnter() */.  
3e60: 69 6e 74 20 6e 42 61 63 6b 75 70 3b 20 20 20 20  int nBackup;    
3e70: 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20     /* Number of 
3e80: 62 61 63 6b 75 70 20 6f 70 65 72 61 74 69 6f 6e  backup operation
3e90: 73 20 72 65 61 64 69 6e 67 20 74 68 69 73 20 62  s reading this b
3ea0: 74 72 65 65 20 2a 2f 0a 20 20 42 74 72 65 65 20  tree */.  Btree 
3eb0: 2a 70 4e 65 78 74 3b 20 20 20 20 20 20 2f 2a 20  *pNext;      /* 
3ec0: 4c 69 73 74 20 6f 66 20 6f 74 68 65 72 20 73 68  List of other sh
3ed0: 61 72 61 62 6c 65 20 42 74 72 65 65 73 20 66 72  arable Btrees fr
3ee0: 6f 6d 20 74 68 65 20 73 61 6d 65 20 64 62 20 2a  om the same db *
3ef0: 2f 0a 20 20 42 74 72 65 65 20 2a 70 50 72 65 76  /.  Btree *pPrev
3f00: 3b 20 20 20 20 20 20 2f 2a 20 42 61 63 6b 20 70  ;      /* Back p
3f10: 6f 69 6e 74 65 72 20 6f 66 20 74 68 65 20 73 61  ointer of the sa
3f20: 6d 65 20 6c 69 73 74 20 2a 2f 0a 23 69 66 6e 64  me list */.#ifnd
3f30: 65 66 20 53 51 4c 49 54 45 5f 4f 4d 49 54 5f 53  ef SQLITE_OMIT_S
3f40: 48 41 52 45 44 5f 43 41 43 48 45 0a 20 20 42 74  HARED_CACHE.  Bt
3f50: 4c 6f 63 6b 20 6c 6f 63 6b 3b 20 20 20 20 20 20  Lock lock;      
3f60: 20 2f 2a 20 4f 62 6a 65 63 74 20 75 73 65 64 20   /* Object used 
3f70: 74 6f 20 6c 6f 63 6b 20 70 61 67 65 20 31 20 2a  to lock page 1 *
3f80: 2f 0a 23 65 6e 64 69 66 0a 7d 3b 0a 0a 2f 2a 0a  /.#endif.};../*.
3f90: 2a 2a 20 42 74 72 65 65 2e 69 6e 54 72 61 6e 73  ** Btree.inTrans
3fa0: 20 6d 61 79 20 74 61 6b 65 20 6f 6e 65 20 6f 66   may take one of
3fb0: 20 74 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 20 76   the following v
3fc0: 61 6c 75 65 73 2e 0a 2a 2a 0a 2a 2a 20 49 66 20  alues..**.** If 
3fd0: 74 68 65 20 73 68 61 72 65 64 2d 64 61 74 61 20  the shared-data 
3fe0: 65 78 74 65 6e 73 69 6f 6e 20 69 73 20 65 6e 61  extension is ena
3ff0: 62 6c 65 64 2c 20 74 68 65 72 65 20 6d 61 79 20  bled, there may 
4000: 62 65 20 6d 75 6c 74 69 70 6c 65 20 75 73 65 72  be multiple user
4010: 73 0a 2a 2a 20 6f 66 20 74 68 65 20 42 74 72 65  s.** of the Btre
4020: 65 20 73 74 72 75 63 74 75 72 65 2e 20 41 74 20  e structure. At 
4030: 6d 6f 73 74 20 6f 6e 65 20 6f 66 20 74 68 65 73  most one of thes
4040: 65 20 6d 61 79 20 6f 70 65 6e 20 61 20 77 72 69  e may open a wri
4050: 74 65 20 74 72 61 6e 73 61 63 74 69 6f 6e 2c 0a  te transaction,.
4060: 2a 2a 20 62 75 74 20 61 6e 79 20 6e 75 6d 62 65  ** but any numbe
4070: 72 20 6d 61 79 20 68 61 76 65 20 61 63 74 69 76  r may have activ
4080: 65 20 72 65 61 64 20 74 72 61 6e 73 61 63 74 69  e read transacti
4090: 6f 6e 73 2e 0a 2a 2f 0a 23 64 65 66 69 6e 65 20  ons..*/.#define 
40a0: 54 52 41 4e 53 5f 4e 4f 4e 45 20 20 30 0a 23 64  TRANS_NONE  0.#d
40b0: 65 66 69 6e 65 20 54 52 41 4e 53 5f 52 45 41 44  efine TRANS_READ
40c0: 20 20 31 0a 23 64 65 66 69 6e 65 20 54 52 41 4e    1.#define TRAN
40d0: 53 5f 57 52 49 54 45 20 32 0a 0a 2f 2a 0a 2a 2a  S_WRITE 2../*.**
40e0: 20 41 6e 20 69 6e 73 74 61 6e 63 65 20 6f 66 20   An instance of 
40f0: 74 68 69 73 20 6f 62 6a 65 63 74 20 72 65 70 72  this object repr
4100: 65 73 65 6e 74 73 20 61 20 73 69 6e 67 6c 65 20  esents a single 
4110: 64 61 74 61 62 61 73 65 20 66 69 6c 65 2e 0a 2a  database file..*
4120: 2a 20 0a 2a 2a 20 41 20 73 69 6e 67 6c 65 20 64  * .** A single d
4130: 61 74 61 62 61 73 65 20 66 69 6c 65 20 63 61 6e  atabase file can
4140: 20 62 65 20 69 6e 20 75 73 65 20 61 73 20 74 68   be in use as th
4150: 65 20 73 61 6d 65 20 74 69 6d 65 20 62 79 20 74  e same time by t
4160: 77 6f 0a 2a 2a 20 6f 72 20 6d 6f 72 65 20 64 61  wo.** or more da
4170: 74 61 62 61 73 65 20 63 6f 6e 6e 65 63 74 69 6f  tabase connectio
4180: 6e 73 2e 20 20 57 68 65 6e 20 74 77 6f 20 6f 72  ns.  When two or
4190: 20 6d 6f 72 65 20 63 6f 6e 6e 65 63 74 69 6f 6e   more connection
41a0: 73 20 61 72 65 0a 2a 2a 20 73 68 61 72 69 6e 67  s are.** sharing
41b0: 20 74 68 65 20 73 61 6d 65 20 64 61 74 61 62 61   the same databa
41c0: 73 65 20 66 69 6c 65 2c 20 65 61 63 68 20 63 6f  se file, each co
41d0: 6e 6e 65 63 74 69 6f 6e 20 68 61 73 20 69 74 20  nnection has it 
41e0: 6f 77 6e 0a 2a 2a 20 70 72 69 76 61 74 65 20 42  own.** private B
41f0: 74 72 65 65 20 6f 62 6a 65 63 74 20 66 6f 72 20  tree object for 
4200: 74 68 65 20 66 69 6c 65 20 61 6e 64 20 65 61 63  the file and eac
4210: 68 20 6f 66 20 74 68 6f 73 65 20 42 74 72 65 65  h of those Btree
4220: 73 20 70 6f 69 6e 74 73 0a 2a 2a 20 74 6f 20 74  s points.** to t
4230: 68 69 73 20 6f 6e 65 20 42 74 53 68 61 72 65 64  his one BtShared
4240: 20 6f 62 6a 65 63 74 2e 20 20 42 74 53 68 61 72   object.  BtShar
4250: 65 64 2e 6e 52 65 66 20 69 73 20 74 68 65 20 6e  ed.nRef is the n
4260: 75 6d 62 65 72 20 6f 66 0a 2a 2a 20 63 6f 6e 6e  umber of.** conn
4270: 65 63 74 69 6f 6e 73 20 63 75 72 72 65 6e 74 6c  ections currentl
4280: 79 20 73 68 61 72 69 6e 67 20 74 68 69 73 20 64  y sharing this d
4290: 61 74 61 62 61 73 65 20 66 69 6c 65 2e 0a 2a 2a  atabase file..**
42a0: 0a 2a 2a 20 46 69 65 6c 64 73 20 69 6e 20 74 68  .** Fields in th
42b0: 69 73 20 73 74 72 75 63 74 75 72 65 20 61 72 65  is structure are
42c0: 20 61 63 63 65 73 73 65 64 20 75 6e 64 65 72 20   accessed under 
42d0: 74 68 65 20 42 74 53 68 61 72 65 64 2e 6d 75 74  the BtShared.mut
42e0: 65 78 0a 2a 2a 20 6d 75 74 65 78 2c 20 65 78 63  ex.** mutex, exc
42f0: 65 70 74 20 66 6f 72 20 6e 52 65 66 20 61 6e 64  ept for nRef and
4300: 20 70 4e 65 78 74 20 77 68 69 63 68 20 61 72 65   pNext which are
4310: 20 61 63 63 65 73 73 65 64 20 75 6e 64 65 72 20   accessed under 
4320: 74 68 65 0a 2a 2a 20 67 6c 6f 62 61 6c 20 53 51  the.** global SQ
4330: 4c 49 54 45 5f 4d 55 54 45 58 5f 53 54 41 54 49  LITE_MUTEX_STATI
4340: 43 5f 4d 41 53 54 45 52 20 6d 75 74 65 78 2e 20  C_MASTER mutex. 
4350: 20 54 68 65 20 70 50 61 67 65 72 20 66 69 65 6c   The pPager fiel
4360: 64 0a 2a 2a 20 6d 61 79 20 6e 6f 74 20 62 65 20  d.** may not be 
4370: 6d 6f 64 69 66 69 65 64 20 6f 6e 63 65 20 69 74  modified once it
4380: 20 69 73 20 69 6e 69 74 69 61 6c 6c 79 20 73 65   is initially se
4390: 74 20 61 73 20 6c 6f 6e 67 20 61 73 20 6e 52 65  t as long as nRe
43a0: 66 3e 30 2e 0a 2a 2a 20 54 68 65 20 70 53 63 68  f>0..** The pSch
43b0: 65 6d 61 20 66 69 65 6c 64 20 6d 61 79 20 62 65  ema field may be
43c0: 20 73 65 74 20 6f 6e 63 65 20 75 6e 64 65 72 20   set once under 
43d0: 42 74 53 68 61 72 65 64 2e 6d 75 74 65 78 20 61  BtShared.mutex a
43e0: 6e 64 0a 2a 2a 20 74 68 65 72 65 61 66 74 65 72  nd.** thereafter
43f0: 20 69 73 20 75 6e 63 68 61 6e 67 65 64 20 61 73   is unchanged as
4400: 20 6c 6f 6e 67 20 61 73 20 6e 52 65 66 3e 30 2e   long as nRef>0.
4410: 0a 2a 2a 0a 2a 2a 20 69 73 50 65 6e 64 69 6e 67  .**.** isPending
4420: 3a 0a 2a 2a 0a 2a 2a 20 20 20 49 66 20 61 20 42  :.**.**   If a B
4430: 74 53 68 61 72 65 64 20 63 6c 69 65 6e 74 20 66  tShared client f
4440: 61 69 6c 73 20 74 6f 20 6f 62 74 61 69 6e 20 61  ails to obtain a
4450: 20 77 72 69 74 65 2d 6c 6f 63 6b 20 6f 6e 20 61   write-lock on a
4460: 20 64 61 74 61 62 61 73 65 0a 2a 2a 20 20 20 74   database.**   t
4470: 61 62 6c 65 20 28 62 65 63 61 75 73 65 20 74 68  able (because th
4480: 65 72 65 20 65 78 69 73 74 73 20 6f 6e 65 20 6f  ere exists one o
4490: 72 20 6d 6f 72 65 20 72 65 61 64 2d 6c 6f 63 6b  r more read-lock
44a0: 73 20 6f 6e 20 74 68 65 20 74 61 62 6c 65 29 2c  s on the table),
44b0: 0a 2a 2a 20 20 20 74 68 65 20 73 68 61 72 65 64  .**   the shared
44c0: 2d 63 61 63 68 65 20 65 6e 74 65 72 73 20 27 70  -cache enters 'p
44d0: 65 6e 64 69 6e 67 2d 6c 6f 63 6b 27 20 73 74 61  ending-lock' sta
44e0: 74 65 20 61 6e 64 20 69 73 50 65 6e 64 69 6e 67  te and isPending
44f0: 20 69 73 0a 2a 2a 20 20 20 73 65 74 20 74 6f 20   is.**   set to 
4500: 74 72 75 65 2e 0a 2a 2a 0a 2a 2a 20 20 20 54 68  true..**.**   Th
4510: 65 20 73 68 61 72 65 64 2d 63 61 63 68 65 20 6c  e shared-cache l
4520: 65 61 76 65 73 20 74 68 65 20 27 70 65 6e 64 69  eaves the 'pendi
4530: 6e 67 20 6c 6f 63 6b 27 20 73 74 61 74 65 20 77  ng lock' state w
4540: 68 65 6e 20 65 69 74 68 65 72 20 6f 66 0a 2a 2a  hen either of.**
4550: 20 20 20 74 68 65 20 66 6f 6c 6c 6f 77 69 6e 67     the following
4560: 20 6f 63 63 75 72 3a 0a 2a 2a 0a 2a 2a 20 20 20   occur:.**.**   
4570: 20 20 31 29 20 54 68 65 20 63 75 72 72 65 6e 74    1) The current
4580: 20 77 72 69 74 65 72 20 28 42 74 53 68 61 72 65   writer (BtShare
4590: 64 2e 70 57 72 69 74 65 72 29 20 63 6f 6e 63 6c  d.pWriter) concl
45a0: 75 64 65 73 20 69 74 73 20 74 72 61 6e 73 61 63  udes its transac
45b0: 74 69 6f 6e 2c 20 4f 52 0a 2a 2a 20 20 20 20 20  tion, OR.**     
45c0: 32 29 20 54 68 65 20 6e 75 6d 62 65 72 20 6f 66  2) The number of
45d0: 20 6c 6f 63 6b 73 20 68 65 6c 64 20 62 79 20 6f   locks held by o
45e0: 74 68 65 72 20 63 6f 6e 6e 65 63 74 69 6f 6e 73  ther connections
45f0: 20 64 72 6f 70 73 20 74 6f 20 7a 65 72 6f 2e 0a   drops to zero..
4600: 2a 2a 0a 2a 2a 20 20 20 77 68 69 6c 65 20 69 6e  **.**   while in
4610: 20 74 68 65 20 27 70 65 6e 64 69 6e 67 2d 6c 6f   the 'pending-lo
4620: 63 6b 27 20 73 74 61 74 65 2c 20 6e 6f 20 63 6f  ck' state, no co
4630: 6e 6e 65 63 74 69 6f 6e 20 6d 61 79 20 73 74 61  nnection may sta
4640: 72 74 20 61 20 6e 65 77 0a 2a 2a 20 20 20 74 72  rt a new.**   tr
4650: 61 6e 73 61 63 74 69 6f 6e 2e 0a 2a 2a 0a 2a 2a  ansaction..**.**
4660: 20 20 20 54 68 69 73 20 66 65 61 74 75 72 65 20     This feature 
4670: 69 73 20 69 6e 63 6c 75 64 65 64 20 74 6f 20 68  is included to h
4680: 65 6c 70 20 70 72 65 76 65 6e 74 20 77 72 69 74  elp prevent writ
4690: 65 72 2d 73 74 61 72 76 61 74 69 6f 6e 2e 0a 2a  er-starvation..*
46a0: 2f 0a 73 74 72 75 63 74 20 42 74 53 68 61 72 65  /.struct BtShare
46b0: 64 20 7b 0a 20 20 50 61 67 65 72 20 2a 70 50 61  d {.  Pager *pPa
46c0: 67 65 72 3b 20 20 20 20 20 20 20 20 2f 2a 20 54  ger;        /* T
46d0: 68 65 20 70 61 67 65 20 63 61 63 68 65 20 2a 2f  he page cache */
46e0: 0a 20 20 73 71 6c 69 74 65 33 20 2a 64 62 3b 20  .  sqlite3 *db; 
46f0: 20 20 20 20 20 20 20 20 20 2f 2a 20 44 61 74 61           /* Data
4700: 62 61 73 65 20 63 6f 6e 6e 65 63 74 69 6f 6e 20  base connection 
4710: 63 75 72 72 65 6e 74 6c 79 20 75 73 69 6e 67 20  currently using 
4720: 74 68 69 73 20 42 74 72 65 65 20 2a 2f 0a 20 20  this Btree */.  
4730: 42 74 43 75 72 73 6f 72 20 2a 70 43 75 72 73 6f  BtCursor *pCurso
4740: 72 3b 20 20 20 20 2f 2a 20 41 20 6c 69 73 74 20  r;    /* A list 
4750: 6f 66 20 61 6c 6c 20 6f 70 65 6e 20 63 75 72 73  of all open curs
4760: 6f 72 73 20 2a 2f 0a 20 20 4d 65 6d 50 61 67 65  ors */.  MemPage
4770: 20 2a 70 50 61 67 65 31 3b 20 20 20 20 20 20 2f   *pPage1;      /
4780: 2a 20 46 69 72 73 74 20 70 61 67 65 20 6f 66 20  * First page of 
4790: 74 68 65 20 64 61 74 61 62 61 73 65 20 2a 2f 0a  the database */.
47a0: 20 20 75 38 20 72 65 61 64 4f 6e 6c 79 3b 20 20    u8 readOnly;  
47b0: 20 20 20 20 20 20 20 20 2f 2a 20 54 72 75 65 20          /* True 
47c0: 69 66 20 74 68 65 20 75 6e 64 65 72 6c 79 69 6e  if the underlyin
47d0: 67 20 66 69 6c 65 20 69 73 20 72 65 61 64 6f 6e  g file is readon
47e0: 6c 79 20 2a 2f 0a 20 20 75 38 20 70 61 67 65 53  ly */.  u8 pageS
47f0: 69 7a 65 46 69 78 65 64 3b 20 20 20 20 20 2f 2a  izeFixed;     /*
4800: 20 54 72 75 65 20 69 66 20 74 68 65 20 70 61 67   True if the pag
4810: 65 20 73 69 7a 65 20 63 61 6e 20 6e 6f 20 6c 6f  e size can no lo
4820: 6e 67 65 72 20 62 65 20 63 68 61 6e 67 65 64 20  nger be changed 
4830: 2a 2f 0a 23 69 66 6e 64 65 66 20 53 51 4c 49 54  */.#ifndef SQLIT
4840: 45 5f 4f 4d 49 54 5f 41 55 54 4f 56 41 43 55 55  E_OMIT_AUTOVACUU
4850: 4d 0a 20 20 75 38 20 61 75 74 6f 56 61 63 75 75  M.  u8 autoVacuu
4860: 6d 3b 20 20 20 20 20 20 20 20 2f 2a 20 54 72 75  m;        /* Tru
4870: 65 20 69 66 20 61 75 74 6f 2d 76 61 63 75 75 6d  e if auto-vacuum
4880: 20 69 73 20 65 6e 61 62 6c 65 64 20 2a 2f 0a 20   is enabled */. 
4890: 20 75 38 20 69 6e 63 72 56 61 63 75 75 6d 3b 20   u8 incrVacuum; 
48a0: 20 20 20 20 20 20 20 2f 2a 20 54 72 75 65 20 69         /* True i
48b0: 66 20 69 6e 63 72 2d 76 61 63 75 75 6d 20 69 73  f incr-vacuum is
48c0: 20 65 6e 61 62 6c 65 64 20 2a 2f 0a 23 65 6e 64   enabled */.#end
48d0: 69 66 0a 20 20 75 31 36 20 70 61 67 65 53 69 7a  if.  u16 pageSiz
48e0: 65 3b 20 20 20 20 20 20 20 20 20 2f 2a 20 54 6f  e;         /* To
48f0: 74 61 6c 20 6e 75 6d 62 65 72 20 6f 66 20 62 79  tal number of by
4900: 74 65 73 20 6f 6e 20 61 20 70 61 67 65 20 2a 2f  tes on a page */
4910: 0a 20 20 75 31 36 20 75 73 61 62 6c 65 53 69 7a  .  u16 usableSiz
4920: 65 3b 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62  e;       /* Numb
4930: 65 72 20 6f 66 20 75 73 61 62 6c 65 20 62 79 74  er of usable byt
4940: 65 73 20 6f 6e 20 65 61 63 68 20 70 61 67 65 20  es on each page 
4950: 2a 2f 0a 20 20 75 31 36 20 6d 61 78 4c 6f 63 61  */.  u16 maxLoca
4960: 6c 3b 20 20 20 20 20 20 20 20 20 2f 2a 20 4d 61  l;         /* Ma
4970: 78 69 6d 75 6d 20 6c 6f 63 61 6c 20 70 61 79 6c  ximum local payl
4980: 6f 61 64 20 69 6e 20 6e 6f 6e 2d 4c 45 41 46 44  oad in non-LEAFD
4990: 41 54 41 20 74 61 62 6c 65 73 20 2a 2f 0a 20 20  ATA tables */.  
49a0: 75 31 36 20 6d 69 6e 4c 6f 63 61 6c 3b 20 20 20  u16 minLocal;   
49b0: 20 20 20 20 20 20 2f 2a 20 4d 69 6e 69 6d 75 6d        /* Minimum
49c0: 20 6c 6f 63 61 6c 20 70 61 79 6c 6f 61 64 20 69   local payload i
49d0: 6e 20 6e 6f 6e 2d 4c 45 41 46 44 41 54 41 20 74  n non-LEAFDATA t
49e0: 61 62 6c 65 73 20 2a 2f 0a 20 20 75 31 36 20 6d  ables */.  u16 m
49f0: 61 78 4c 65 61 66 3b 20 20 20 20 20 20 20 20 20  axLeaf;         
4a00: 20 2f 2a 20 4d 61 78 69 6d 75 6d 20 6c 6f 63 61   /* Maximum loca
4a10: 6c 20 70 61 79 6c 6f 61 64 20 69 6e 20 61 20 4c  l payload in a L
4a20: 45 41 46 44 41 54 41 20 74 61 62 6c 65 20 2a 2f  EAFDATA table */
4a30: 0a 20 20 75 31 36 20 6d 69 6e 4c 65 61 66 3b 20  .  u16 minLeaf; 
4a40: 20 20 20 20 20 20 20 20 20 2f 2a 20 4d 69 6e 69           /* Mini
4a50: 6d 75 6d 20 6c 6f 63 61 6c 20 70 61 79 6c 6f 61  mum local payloa
4a60: 64 20 69 6e 20 61 20 4c 45 41 46 44 41 54 41 20  d in a LEAFDATA 
4a70: 74 61 62 6c 65 20 2a 2f 0a 20 20 75 38 20 69 6e  table */.  u8 in
4a80: 54 72 61 6e 73 61 63 74 69 6f 6e 3b 20 20 20 20  Transaction;    
4a90: 20 2f 2a 20 54 72 61 6e 73 61 63 74 69 6f 6e 20   /* Transaction 
4aa0: 73 74 61 74 65 20 2a 2f 0a 20 20 69 6e 74 20 6e  state */.  int n
4ab0: 54 72 61 6e 73 61 63 74 69 6f 6e 3b 20 20 20 20  Transaction;    
4ac0: 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 6f 70   /* Number of op
4ad0: 65 6e 20 74 72 61 6e 73 61 63 74 69 6f 6e 73 20  en transactions 
4ae0: 28 72 65 61 64 20 2b 20 77 72 69 74 65 29 20 2a  (read + write) *
4af0: 2f 0a 20 20 76 6f 69 64 20 2a 70 53 63 68 65 6d  /.  void *pSchem
4b00: 61 3b 20 20 20 20 20 20 20 20 2f 2a 20 50 6f 69  a;        /* Poi
4b10: 6e 74 65 72 20 74 6f 20 73 70 61 63 65 20 61 6c  nter to space al
4b20: 6c 6f 63 61 74 65 64 20 62 79 20 73 71 6c 69 74  located by sqlit
4b30: 65 33 42 74 72 65 65 53 63 68 65 6d 61 28 29 20  e3BtreeSchema() 
4b40: 2a 2f 0a 20 20 76 6f 69 64 20 28 2a 78 46 72 65  */.  void (*xFre
4b50: 65 53 63 68 65 6d 61 29 28 76 6f 69 64 2a 29 3b  eSchema)(void*);
4b60: 20 20 2f 2a 20 44 65 73 74 72 75 63 74 6f 72 20    /* Destructor 
4b70: 66 6f 72 20 42 74 53 68 61 72 65 64 2e 70 53 63  for BtShared.pSc
4b80: 68 65 6d 61 20 2a 2f 0a 20 20 73 71 6c 69 74 65  hema */.  sqlite
4b90: 33 5f 6d 75 74 65 78 20 2a 6d 75 74 65 78 3b 20  3_mutex *mutex; 
4ba0: 2f 2a 20 4e 6f 6e 2d 72 65 63 75 72 73 69 76 65  /* Non-recursive
4bb0: 20 6d 75 74 65 78 20 72 65 71 75 69 72 65 64 20   mutex required 
4bc0: 74 6f 20 61 63 63 65 73 73 20 74 68 69 73 20 73  to access this s
4bd0: 74 72 75 63 74 20 2a 2f 0a 20 20 42 69 74 76 65  truct */.  Bitve
4be0: 63 20 2a 70 48 61 73 43 6f 6e 74 65 6e 74 3b 20  c *pHasContent; 
4bf0: 20 2f 2a 20 53 65 74 20 6f 66 20 70 61 67 65 73   /* Set of pages
4c00: 20 6d 6f 76 65 64 20 74 6f 20 66 72 65 65 2d 6c   moved to free-l
4c10: 69 73 74 20 74 68 69 73 20 74 72 61 6e 73 61 63  ist this transac
4c20: 74 69 6f 6e 20 2a 2f 0a 23 69 66 6e 64 65 66 20  tion */.#ifndef 
4c30: 53 51 4c 49 54 45 5f 4f 4d 49 54 5f 53 48 41 52  SQLITE_OMIT_SHAR
4c40: 45 44 5f 43 41 43 48 45 0a 20 20 69 6e 74 20 6e  ED_CACHE.  int n
4c50: 52 65 66 3b 20 20 20 20 20 20 20 20 20 20 20 20  Ref;            
4c60: 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 72 65   /* Number of re
4c70: 66 65 72 65 6e 63 65 73 20 74 6f 20 74 68 69 73  ferences to this
4c80: 20 73 74 72 75 63 74 75 72 65 20 2a 2f 0a 20 20   structure */.  
4c90: 42 74 53 68 61 72 65 64 20 2a 70 4e 65 78 74 3b  BtShared *pNext;
4ca0: 20 20 20 20 20 20 2f 2a 20 4e 65 78 74 20 6f 6e        /* Next on
4cb0: 20 61 20 6c 69 73 74 20 6f 66 20 73 68 61 72 61   a list of shara
4cc0: 62 6c 65 20 42 74 53 68 61 72 65 64 20 73 74 72  ble BtShared str
4cd0: 75 63 74 73 20 2a 2f 0a 20 20 42 74 4c 6f 63 6b  ucts */.  BtLock
4ce0: 20 2a 70 4c 6f 63 6b 3b 20 20 20 20 20 20 20 20   *pLock;        
4cf0: 2f 2a 20 4c 69 73 74 20 6f 66 20 6c 6f 63 6b 73  /* List of locks
4d00: 20 68 65 6c 64 20 6f 6e 20 74 68 69 73 20 73 68   held on this sh
4d10: 61 72 65 64 2d 62 74 72 65 65 20 73 74 72 75 63  ared-btree struc
4d20: 74 20 2a 2f 0a 20 20 42 74 72 65 65 20 2a 70 57  t */.  Btree *pW
4d30: 72 69 74 65 72 3b 20 20 20 20 20 20 20 2f 2a 20  riter;       /* 
4d40: 42 74 72 65 65 20 77 69 74 68 20 63 75 72 72 65  Btree with curre
4d50: 6e 74 6c 79 20 6f 70 65 6e 20 77 72 69 74 65 20  ntly open write 
4d60: 74 72 61 6e 73 61 63 74 69 6f 6e 20 2a 2f 0a 20  transaction */. 
4d70: 20 75 38 20 69 73 45 78 63 6c 75 73 69 76 65 3b   u8 isExclusive;
4d80: 20 20 20 20 20 20 20 2f 2a 20 54 72 75 65 20 69         /* True i
4d90: 66 20 70 57 72 69 74 65 72 20 68 61 73 20 61 6e  f pWriter has an
4da0: 20 45 58 43 4c 55 53 49 56 45 20 6c 6f 63 6b 20   EXCLUSIVE lock 
4db0: 6f 6e 20 74 68 65 20 64 62 20 2a 2f 0a 20 20 75  on the db */.  u
4dc0: 38 20 69 73 50 65 6e 64 69 6e 67 3b 20 20 20 20  8 isPending;    
4dd0: 20 20 20 20 20 2f 2a 20 49 66 20 77 61 69 74 69       /* If waiti
4de0: 6e 67 20 66 6f 72 20 72 65 61 64 2d 6c 6f 63 6b  ng for read-lock
4df0: 73 20 74 6f 20 63 6c 65 61 72 20 2a 2f 0a 23 65  s to clear */.#e
4e00: 6e 64 69 66 0a 20 20 75 38 20 2a 70 54 6d 70 53  ndif.  u8 *pTmpS
4e10: 70 61 63 65 3b 20 20 20 20 20 20 20 20 2f 2a 20  pace;        /* 
4e20: 42 74 53 68 61 72 65 64 2e 70 61 67 65 53 69 7a  BtShared.pageSiz
4e30: 65 20 62 79 74 65 73 20 6f 66 20 73 70 61 63 65  e bytes of space
4e40: 20 66 6f 72 20 74 6d 70 20 75 73 65 20 2a 2f 0a   for tmp use */.
4e50: 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 41 6e 20 69 6e 73  };../*.** An ins
4e60: 74 61 6e 63 65 20 6f 66 20 74 68 65 20 66 6f 6c  tance of the fol
4e70: 6c 6f 77 69 6e 67 20 73 74 72 75 63 74 75 72 65  lowing structure
4e80: 20 69 73 20 75 73 65 64 20 74 6f 20 68 6f 6c 64   is used to hold
4e90: 20 69 6e 66 6f 72 6d 61 74 69 6f 6e 0a 2a 2a 20   information.** 
4ea0: 61 62 6f 75 74 20 61 20 63 65 6c 6c 2e 20 20 54  about a cell.  T
4eb0: 68 65 20 70 61 72 73 65 43 65 6c 6c 50 74 72 28  he parseCellPtr(
4ec0: 29 20 66 75 6e 63 74 69 6f 6e 20 66 69 6c 6c 73  ) function fills
4ed0: 20 69 6e 20 74 68 69 73 20 73 74 72 75 63 74 75   in this structu
4ee0: 72 65 0a 2a 2a 20 62 61 73 65 64 20 6f 6e 20 69  re.** based on i
4ef0: 6e 66 6f 72 6d 61 74 69 6f 6e 20 65 78 74 72 61  nformation extra
4f00: 63 74 20 66 72 6f 6d 20 74 68 65 20 72 61 77 20  ct from the raw 
4f10: 64 69 73 6b 20 70 61 67 65 2e 0a 2a 2f 0a 74 79  disk page..*/.ty
4f20: 70 65 64 65 66 20 73 74 72 75 63 74 20 43 65 6c  pedef struct Cel
4f30: 6c 49 6e 66 6f 20 43 65 6c 6c 49 6e 66 6f 3b 0a  lInfo CellInfo;.
4f40: 73 74 72 75 63 74 20 43 65 6c 6c 49 6e 66 6f 20  struct CellInfo 
4f50: 7b 0a 20 20 75 38 20 2a 70 43 65 6c 6c 3b 20 20  {.  u8 *pCell;  
4f60: 20 20 20 2f 2a 20 50 6f 69 6e 74 65 72 20 74 6f     /* Pointer to
4f70: 20 74 68 65 20 73 74 61 72 74 20 6f 66 20 63 65   the start of ce
4f80: 6c 6c 20 63 6f 6e 74 65 6e 74 20 2a 2f 0a 20 20  ll content */.  
4f90: 69 36 34 20 6e 4b 65 79 3b 20 20 20 20 20 20 2f  i64 nKey;      /
4fa0: 2a 20 54 68 65 20 6b 65 79 20 66 6f 72 20 49 4e  * The key for IN
4fb0: 54 4b 45 59 20 74 61 62 6c 65 73 2c 20 6f 72 20  TKEY tables, or 
4fc0: 6e 75 6d 62 65 72 20 6f 66 20 62 79 74 65 73 20  number of bytes 
4fd0: 69 6e 20 6b 65 79 20 2a 2f 0a 20 20 75 33 32 20  in key */.  u32 
4fe0: 6e 44 61 74 61 3b 20 20 20 20 20 2f 2a 20 4e 75  nData;     /* Nu
4ff0: 6d 62 65 72 20 6f 66 20 62 79 74 65 73 20 6f 66  mber of bytes of
5000: 20 64 61 74 61 20 2a 2f 0a 20 20 75 33 32 20 6e   data */.  u32 n
5010: 50 61 79 6c 6f 61 64 3b 20 20 2f 2a 20 54 6f 74  Payload;  /* Tot
5020: 61 6c 20 61 6d 6f 75 6e 74 20 6f 66 20 70 61 79  al amount of pay
5030: 6c 6f 61 64 20 2a 2f 0a 20 20 75 31 36 20 6e 48  load */.  u16 nH
5040: 65 61 64 65 72 3b 20 20 20 2f 2a 20 53 69 7a 65  eader;   /* Size
5050: 20 6f 66 20 74 68 65 20 63 65 6c 6c 20 63 6f 6e   of the cell con
5060: 74 65 6e 74 20 68 65 61 64 65 72 20 69 6e 20 62  tent header in b
5070: 79 74 65 73 20 2a 2f 0a 20 20 75 31 36 20 6e 4c  ytes */.  u16 nL
5080: 6f 63 61 6c 3b 20 20 20 20 2f 2a 20 41 6d 6f 75  ocal;    /* Amou
5090: 6e 74 20 6f 66 20 70 61 79 6c 6f 61 64 20 68 65  nt of payload he
50a0: 6c 64 20 6c 6f 63 61 6c 6c 79 20 2a 2f 0a 20 20  ld locally */.  
50b0: 75 31 36 20 69 4f 76 65 72 66 6c 6f 77 3b 20 2f  u16 iOverflow; /
50c0: 2a 20 4f 66 66 73 65 74 20 74 6f 20 6f 76 65 72  * Offset to over
50d0: 66 6c 6f 77 20 70 61 67 65 20 6e 75 6d 62 65 72  flow page number
50e0: 2e 20 20 5a 65 72 6f 20 69 66 20 6e 6f 20 6f 76  .  Zero if no ov
50f0: 65 72 66 6c 6f 77 20 2a 2f 0a 20 20 75 31 36 20  erflow */.  u16 
5100: 6e 53 69 7a 65 3b 20 20 20 20 20 2f 2a 20 53 69  nSize;     /* Si
5110: 7a 65 20 6f 66 20 74 68 65 20 63 65 6c 6c 20 63  ze of the cell c
5120: 6f 6e 74 65 6e 74 20 6f 6e 20 74 68 65 20 6d 61  ontent on the ma
5130: 69 6e 20 62 2d 74 72 65 65 20 70 61 67 65 20 2a  in b-tree page *
5140: 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 4d 61 78 69  /.};../*.** Maxi
5150: 6d 75 6d 20 64 65 70 74 68 20 6f 66 20 61 6e 20  mum depth of an 
5160: 53 51 4c 69 74 65 20 42 2d 54 72 65 65 20 73 74  SQLite B-Tree st
5170: 72 75 63 74 75 72 65 2e 20 41 6e 79 20 42 2d 54  ructure. Any B-T
5180: 72 65 65 20 64 65 65 70 65 72 20 74 68 61 6e 0a  ree deeper than.
5190: 2a 2a 20 74 68 69 73 20 77 69 6c 6c 20 62 65 20  ** this will be 
51a0: 64 65 63 6c 61 72 65 64 20 63 6f 72 72 75 70 74  declared corrupt
51b0: 2e 20 54 68 69 73 20 76 61 6c 75 65 20 69 73 20  . This value is 
51c0: 63 61 6c 63 75 6c 61 74 65 64 20 62 61 73 65 64  calculated based
51d0: 20 6f 6e 20 61 0a 2a 2a 20 6d 61 78 69 6d 75 6d   on a.** maximum
51e0: 20 64 61 74 61 62 61 73 65 20 73 69 7a 65 20 6f   database size o
51f0: 66 20 32 5e 33 31 20 70 61 67 65 73 20 61 20 6d  f 2^31 pages a m
5200: 69 6e 69 6d 75 6d 20 66 61 6e 6f 75 74 20 6f 66  inimum fanout of
5210: 20 32 20 66 6f 72 20 61 0a 2a 2a 20 72 6f 6f 74   2 for a.** root
5220: 2d 6e 6f 64 65 20 61 6e 64 20 33 20 66 6f 72 20  -node and 3 for 
5230: 61 6c 6c 20 6f 74 68 65 72 20 69 6e 74 65 72 6e  all other intern
5240: 61 6c 20 6e 6f 64 65 73 2e 0a 2a 2a 0a 2a 2a 20  al nodes..**.** 
5250: 49 66 20 61 20 74 72 65 65 20 74 68 61 74 20 61  If a tree that a
5260: 70 70 65 61 72 73 20 74 6f 20 62 65 20 74 61 6c  ppears to be tal
5270: 6c 65 72 20 74 68 61 6e 20 74 68 69 73 20 69 73  ler than this is
5280: 20 65 6e 63 6f 75 6e 74 65 72 65 64 2c 20 69 74   encountered, it
5290: 20 69 73 0a 2a 2a 20 61 73 73 75 6d 65 64 20 74   is.** assumed t
52a0: 68 61 74 20 74 68 65 20 64 61 74 61 62 61 73 65  hat the database
52b0: 20 69 73 20 63 6f 72 72 75 70 74 2e 0a 2a 2f 0a   is corrupt..*/.
52c0: 23 64 65 66 69 6e 65 20 42 54 43 55 52 53 4f 52  #define BTCURSOR
52d0: 5f 4d 41 58 5f 44 45 50 54 48 20 32 30 0a 0a 2f  _MAX_DEPTH 20../
52e0: 2a 0a 2a 2a 20 41 20 63 75 72 73 6f 72 20 69 73  *.** A cursor is
52f0: 20 61 20 70 6f 69 6e 74 65 72 20 74 6f 20 61 20   a pointer to a 
5300: 70 61 72 74 69 63 75 6c 61 72 20 65 6e 74 72 79  particular entry
5310: 20 77 69 74 68 69 6e 20 61 20 70 61 72 74 69 63   within a partic
5320: 75 6c 61 72 0a 2a 2a 20 62 2d 74 72 65 65 20 77  ular.** b-tree w
5330: 69 74 68 69 6e 20 61 20 64 61 74 61 62 61 73 65  ithin a database
5340: 20 66 69 6c 65 2e 0a 2a 2a 0a 2a 2a 20 54 68 65   file..**.** The
5350: 20 65 6e 74 72 79 20 69 73 20 69 64 65 6e 74 69   entry is identi
5360: 66 69 65 64 20 62 79 20 69 74 73 20 4d 65 6d 50  fied by its MemP
5370: 61 67 65 20 61 6e 64 20 74 68 65 20 69 6e 64 65  age and the inde
5380: 78 20 69 6e 0a 2a 2a 20 4d 65 6d 50 61 67 65 2e  x in.** MemPage.
5390: 61 43 65 6c 6c 5b 5d 20 6f 66 20 74 68 65 20 65  aCell[] of the e
53a0: 6e 74 72 79 2e 0a 2a 2a 0a 2a 2a 20 57 68 65 6e  ntry..**.** When
53b0: 20 61 20 73 69 6e 67 6c 65 20 64 61 74 61 62 61   a single databa
53c0: 73 65 20 66 69 6c 65 20 63 61 6e 20 73 68 61 72  se file can shar
53d0: 65 64 20 62 79 20 74 77 6f 20 6d 6f 72 65 20 64  ed by two more d
53e0: 61 74 61 62 61 73 65 20 63 6f 6e 6e 65 63 74 69  atabase connecti
53f0: 6f 6e 73 2c 0a 2a 2a 20 62 75 74 20 63 75 72 73  ons,.** but curs
5400: 6f 72 73 20 63 61 6e 6e 6f 74 20 62 65 20 73 68  ors cannot be sh
5410: 61 72 65 64 2e 20 20 45 61 63 68 20 63 75 72 73  ared.  Each curs
5420: 6f 72 20 69 73 20 61 73 73 6f 63 69 61 74 65 64  or is associated
5430: 20 77 69 74 68 20 61 0a 2a 2a 20 70 61 72 74 69   with a.** parti
5440: 63 75 6c 61 72 20 64 61 74 61 62 61 73 65 20 63  cular database c
5450: 6f 6e 6e 65 63 74 69 6f 6e 20 69 64 65 6e 74 69  onnection identi
5460: 66 69 65 64 20 42 74 43 75 72 73 6f 72 2e 70 42  fied BtCursor.pB
5470: 74 72 65 65 2e 64 62 2e 0a 2a 2a 0a 2a 2a 20 46  tree.db..**.** F
5480: 69 65 6c 64 73 20 69 6e 20 74 68 69 73 20 73 74  ields in this st
5490: 72 75 63 74 75 72 65 20 61 72 65 20 61 63 63 65  ructure are acce
54a0: 73 73 65 64 20 75 6e 64 65 72 20 74 68 65 20 42  ssed under the B
54b0: 74 53 68 61 72 65 64 2e 6d 75 74 65 78 0a 2a 2a  tShared.mutex.**
54c0: 20 66 6f 75 6e 64 20 61 74 20 73 65 6c 66 2d 3e   found at self->
54d0: 70 42 74 2d 3e 6d 75 74 65 78 2e 20 0a 2a 2f 0a  pBt->mutex. .*/.
54e0: 73 74 72 75 63 74 20 42 74 43 75 72 73 6f 72 20  struct BtCursor 
54f0: 7b 0a 20 20 42 74 72 65 65 20 2a 70 42 74 72 65  {.  Btree *pBtre
5500: 65 3b 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a  e;            /*
5510: 20 54 68 65 20 42 74 72 65 65 20 74 6f 20 77 68   The Btree to wh
5520: 69 63 68 20 74 68 69 73 20 63 75 72 73 6f 72 20  ich this cursor 
5530: 62 65 6c 6f 6e 67 73 20 2a 2f 0a 20 20 42 74 53  belongs */.  BtS
5540: 68 61 72 65 64 20 2a 70 42 74 3b 20 20 20 20 20  hared *pBt;     
5550: 20 20 20 20 20 20 20 2f 2a 20 54 68 65 20 42 74         /* The Bt
5560: 53 68 61 72 65 64 20 74 68 69 73 20 63 75 72 73  Shared this curs
5570: 6f 72 20 70 6f 69 6e 74 73 20 74 6f 20 2a 2f 0a  or points to */.
5580: 20 20 42 74 43 75 72 73 6f 72 20 2a 70 4e 65 78    BtCursor *pNex
5590: 74 2c 20 2a 70 50 72 65 76 3b 20 20 2f 2a 20 46  t, *pPrev;  /* F
55a0: 6f 72 6d 73 20 61 20 6c 69 6e 6b 65 64 20 6c 69  orms a linked li
55b0: 73 74 20 6f 66 20 61 6c 6c 20 63 75 72 73 6f 72  st of all cursor
55c0: 73 20 2a 2f 0a 20 20 73 74 72 75 63 74 20 4b 65  s */.  struct Ke
55d0: 79 49 6e 66 6f 20 2a 70 4b 65 79 49 6e 66 6f 3b  yInfo *pKeyInfo;
55e0: 20 2f 2a 20 41 72 67 75 6d 65 6e 74 20 70 61 73   /* Argument pas
55f0: 73 65 64 20 74 6f 20 63 6f 6d 70 61 72 69 73 6f  sed to compariso
5600: 6e 20 66 75 6e 63 74 69 6f 6e 20 2a 2f 0a 20 20  n function */.  
5610: 50 67 6e 6f 20 70 67 6e 6f 52 6f 6f 74 3b 20 20  Pgno pgnoRoot;  
5620: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 54 68 65            /* The
5630: 20 72 6f 6f 74 20 70 61 67 65 20 6f 66 20 74 68   root page of th
5640: 69 73 20 74 72 65 65 20 2a 2f 0a 20 20 73 71 6c  is tree */.  sql
5650: 69 74 65 33 5f 69 6e 74 36 34 20 63 61 63 68 65  ite3_int64 cache
5660: 64 52 6f 77 69 64 3b 20 2f 2a 20 4e 65 78 74 20  dRowid; /* Next 
5670: 72 6f 77 69 64 20 63 61 63 68 65 2e 20 20 30 20  rowid cache.  0 
5680: 6d 65 61 6e 73 20 6e 6f 74 20 76 61 6c 69 64 20  means not valid 
5690: 2a 2f 0a 20 20 43 65 6c 6c 49 6e 66 6f 20 69 6e  */.  CellInfo in
56a0: 66 6f 3b 20 20 20 20 20 20 20 20 20 20 20 20 2f  fo;            /
56b0: 2a 20 41 20 70 61 72 73 65 20 6f 66 20 74 68 65  * A parse of the
56c0: 20 63 65 6c 6c 20 77 65 20 61 72 65 20 70 6f 69   cell we are poi
56d0: 6e 74 69 6e 67 20 61 74 20 2a 2f 0a 20 20 75 38  nting at */.  u8
56e0: 20 77 72 46 6c 61 67 3b 20 20 20 20 20 20 20 20   wrFlag;        
56f0: 20 20 20 20 20 20 20 20 2f 2a 20 54 72 75 65 20          /* True 
5700: 69 66 20 77 72 69 74 61 62 6c 65 20 2a 2f 0a 20  if writable */. 
5710: 20 75 38 20 61 74 4c 61 73 74 3b 20 20 20 20 20   u8 atLast;     
5720: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 43 75             /* Cu
5730: 72 73 6f 72 20 70 6f 69 6e 74 69 6e 67 20 74 6f  rsor pointing to
5740: 20 74 68 65 20 6c 61 73 74 20 65 6e 74 72 79 20   the last entry 
5750: 2a 2f 0a 20 20 75 38 20 76 61 6c 69 64 4e 4b 65  */.  u8 validNKe
5760: 79 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 2f  y;             /
5770: 2a 20 54 72 75 65 20 69 66 20 69 6e 66 6f 2e 6e  * True if info.n
5780: 4b 65 79 20 69 73 20 76 61 6c 69 64 20 2a 2f 0a  Key is valid */.
5790: 20 20 75 38 20 65 53 74 61 74 65 3b 20 20 20 20    u8 eState;    
57a0: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4f              /* O
57b0: 6e 65 20 6f 66 20 74 68 65 20 43 55 52 53 4f 52  ne of the CURSOR
57c0: 5f 58 58 58 20 63 6f 6e 73 74 61 6e 74 73 20 28  _XXX constants (
57d0: 73 65 65 20 62 65 6c 6f 77 29 20 2a 2f 0a 20 20  see below) */.  
57e0: 76 6f 69 64 20 2a 70 4b 65 79 3b 20 20 20 20 20  void *pKey;     
57f0: 20 2f 2a 20 53 61 76 65 64 20 6b 65 79 20 74 68   /* Saved key th
5800: 61 74 20 77 61 73 20 63 75 72 73 6f 72 27 73 20  at was cursor's 
5810: 6c 61 73 74 20 6b 6e 6f 77 6e 20 70 6f 73 69 74  last known posit
5820: 69 6f 6e 20 2a 2f 0a 20 20 69 36 34 20 6e 4b 65  ion */.  i64 nKe
5830: 79 3b 20 20 20 20 20 20 20 20 2f 2a 20 53 69 7a  y;        /* Siz
5840: 65 20 6f 66 20 70 4b 65 79 2c 20 6f 72 20 6c 61  e of pKey, or la
5850: 73 74 20 69 6e 74 65 67 65 72 20 6b 65 79 20 2a  st integer key *
5860: 2f 0a 20 20 69 6e 74 20 73 6b 69 70 3b 20 20 20  /.  int skip;   
5870: 20 20 20 20 20 2f 2a 20 28 73 6b 69 70 3c 30 29       /* (skip<0)
5880: 20 2d 3e 20 50 72 65 76 28 29 20 69 73 20 61 20   -> Prev() is a 
5890: 6e 6f 2d 6f 70 2e 20 28 73 6b 69 70 3e 30 29 20  no-op. (skip>0) 
58a0: 2d 3e 20 4e 65 78 74 28 29 20 69 73 20 2a 2f 0a  -> Next() is */.
58b0: 23 69 66 6e 64 65 66 20 53 51 4c 49 54 45 5f 4f  #ifndef SQLITE_O
58c0: 4d 49 54 5f 49 4e 43 52 42 4c 4f 42 0a 20 20 75  MIT_INCRBLOB.  u
58d0: 38 20 69 73 49 6e 63 72 62 6c 6f 62 48 61 6e 64  8 isIncrblobHand
58e0: 6c 65 3b 20 20 20 20 20 20 2f 2a 20 54 72 75 65  le;      /* True
58f0: 20 69 66 20 74 68 69 73 20 63 75 72 73 6f 72 20   if this cursor 
5900: 69 73 20 61 6e 20 69 6e 63 72 2e 20 69 6f 20 68  is an incr. io h
5910: 61 6e 64 6c 65 20 2a 2f 0a 20 20 50 67 6e 6f 20  andle */.  Pgno 
5920: 2a 61 4f 76 65 72 66 6c 6f 77 3b 20 20 20 20 20  *aOverflow;     
5930: 20 20 20 20 20 2f 2a 20 43 61 63 68 65 20 6f 66       /* Cache of
5940: 20 6f 76 65 72 66 6c 6f 77 20 70 61 67 65 20 6c   overflow page l
5950: 6f 63 61 74 69 6f 6e 73 20 2a 2f 0a 23 65 6e 64  ocations */.#end
5960: 69 66 0a 20 20 69 31 36 20 69 50 61 67 65 3b 20  if.  i16 iPage; 
5970: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
5980: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 49 6e             /* In
5990: 64 65 78 20 6f 66 20 63 75 72 72 65 6e 74 20 70  dex of current p
59a0: 61 67 65 20 69 6e 20 61 70 50 61 67 65 20 2a 2f  age in apPage */
59b0: 0a 20 20 4d 65 6d 50 61 67 65 20 2a 61 70 50 61  .  MemPage *apPa
59c0: 67 65 5b 42 54 43 55 52 53 4f 52 5f 4d 41 58 5f  ge[BTCURSOR_MAX_
59d0: 44 45 50 54 48 5d 3b 20 20 2f 2a 20 50 61 67 65  DEPTH];  /* Page
59e0: 73 20 66 72 6f 6d 20 72 6f 6f 74 20 74 6f 20 63  s from root to c
59f0: 75 72 72 65 6e 74 20 70 61 67 65 20 2a 2f 0a 20  urrent page */. 
5a00: 20 75 31 36 20 61 69 49 64 78 5b 42 54 43 55 52   u16 aiIdx[BTCUR
5a10: 53 4f 52 5f 4d 41 58 5f 44 45 50 54 48 5d 3b 20  SOR_MAX_DEPTH]; 
5a20: 20 20 20 20 20 20 20 2f 2a 20 43 75 72 72 65 6e         /* Curren
5a30: 74 20 69 6e 64 65 78 20 69 6e 20 61 70 50 61 67  t index in apPag
5a40: 65 5b 69 5d 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a  e[i] */.};../*.*
5a50: 2a 20 50 6f 74 65 6e 74 69 61 6c 20 76 61 6c 75  * Potential valu
5a60: 65 73 20 66 6f 72 20 42 74 43 75 72 73 6f 72 2e  es for BtCursor.
5a70: 65 53 74 61 74 65 2e 0a 2a 2a 0a 2a 2a 20 43 55  eState..**.** CU
5a80: 52 53 4f 52 5f 56 41 4c 49 44 3a 0a 2a 2a 20 20  RSOR_VALID:.**  
5a90: 20 43 75 72 73 6f 72 20 70 6f 69 6e 74 73 20 74   Cursor points t
5aa0: 6f 20 61 20 76 61 6c 69 64 20 65 6e 74 72 79 2e  o a valid entry.
5ab0: 20 67 65 74 50 61 79 6c 6f 61 64 28 29 20 65 74   getPayload() et
5ac0: 63 2e 20 6d 61 79 20 62 65 20 63 61 6c 6c 65 64  c. may be called
5ad0: 2e 0a 2a 2a 0a 2a 2a 20 43 55 52 53 4f 52 5f 49  ..**.** CURSOR_I
5ae0: 4e 56 41 4c 49 44 3a 0a 2a 2a 20 20 20 43 75 72  NVALID:.**   Cur
5af0: 73 6f 72 20 64 6f 65 73 20 6e 6f 74 20 70 6f 69  sor does not poi
5b00: 6e 74 20 74 6f 20 61 20 76 61 6c 69 64 20 65 6e  nt to a valid en
5b10: 74 72 79 2e 20 54 68 69 73 20 63 61 6e 20 68 61  try. This can ha
5b20: 70 70 65 6e 20 28 66 6f 72 20 65 78 61 6d 70 6c  ppen (for exampl
5b30: 65 29 20 0a 2a 2a 20 20 20 62 65 63 61 75 73 65  e) .**   because
5b40: 20 74 68 65 20 74 61 62 6c 65 20 69 73 20 65 6d   the table is em
5b50: 70 74 79 20 6f 72 20 62 65 63 61 75 73 65 20 42  pty or because B
5b60: 74 72 65 65 43 75 72 73 6f 72 46 69 72 73 74 28  treeCursorFirst(
5b70: 29 20 68 61 73 20 6e 6f 74 20 62 65 65 6e 0a 2a  ) has not been.*
5b80: 2a 20 20 20 63 61 6c 6c 65 64 2e 0a 2a 2a 0a 2a  *   called..**.*
5b90: 2a 20 43 55 52 53 4f 52 5f 52 45 51 55 49 52 45  * CURSOR_REQUIRE
5ba0: 53 45 45 4b 3a 0a 2a 2a 20 20 20 54 68 65 20 74  SEEK:.**   The t
5bb0: 61 62 6c 65 20 74 68 61 74 20 74 68 69 73 20 63  able that this c
5bc0: 75 72 73 6f 72 20 77 61 73 20 6f 70 65 6e 65 64  ursor was opened
5bd0: 20 6f 6e 20 73 74 69 6c 6c 20 65 78 69 73 74 73   on still exists
5be0: 2c 20 62 75 74 20 68 61 73 20 62 65 65 6e 20 0a  , but has been .
5bf0: 2a 2a 20 20 20 6d 6f 64 69 66 69 65 64 20 73 69  **   modified si
5c00: 6e 63 65 20 74 68 65 20 63 75 72 73 6f 72 20 77  nce the cursor w
5c10: 61 73 20 6c 61 73 74 20 75 73 65 64 2e 20 54 68  as last used. Th
5c20: 65 20 63 75 72 73 6f 72 20 70 6f 73 69 74 69 6f  e cursor positio
5c30: 6e 20 69 73 20 73 61 76 65 64 0a 2a 2a 20 20 20  n is saved.**   
5c40: 69 6e 20 76 61 72 69 61 62 6c 65 73 20 42 74 43  in variables BtC
5c50: 75 72 73 6f 72 2e 70 4b 65 79 20 61 6e 64 20 42  ursor.pKey and B
5c60: 74 43 75 72 73 6f 72 2e 6e 4b 65 79 2e 20 57 68  tCursor.nKey. Wh
5c70: 65 6e 20 61 20 63 75 72 73 6f 72 20 69 73 20 69  en a cursor is i
5c80: 6e 20 0a 2a 2a 20 20 20 74 68 69 73 20 73 74 61  n .**   this sta
5c90: 74 65 2c 20 72 65 73 74 6f 72 65 43 75 72 73 6f  te, restoreCurso
5ca0: 72 50 6f 73 69 74 69 6f 6e 28 29 20 63 61 6e 20  rPosition() can 
5cb0: 62 65 20 63 61 6c 6c 65 64 20 74 6f 20 61 74 74  be called to att
5cc0: 65 6d 70 74 20 74 6f 0a 2a 2a 20 20 20 73 65 65  empt to.**   see
5cd0: 6b 20 74 68 65 20 63 75 72 73 6f 72 20 74 6f 20  k the cursor to 
5ce0: 74 68 65 20 73 61 76 65 64 20 70 6f 73 69 74 69  the saved positi
5cf0: 6f 6e 2e 0a 2a 2a 0a 2a 2a 20 43 55 52 53 4f 52  on..**.** CURSOR
5d00: 5f 46 41 55 4c 54 3a 0a 2a 2a 20 20 20 41 20 75  _FAULT:.**   A u
5d10: 6e 72 65 63 6f 76 65 72 61 62 6c 65 20 65 72 72  nrecoverable err
5d20: 6f 72 20 28 61 6e 20 49 2f 4f 20 65 72 72 6f 72  or (an I/O error
5d30: 20 6f 72 20 61 20 6d 61 6c 6c 6f 63 20 66 61 69   or a malloc fai
5d40: 6c 75 72 65 29 20 68 61 73 20 6f 63 63 75 72 72  lure) has occurr
5d50: 65 64 0a 2a 2a 20 20 20 6f 6e 20 61 20 64 69 66  ed.**   on a dif
5d60: 66 65 72 65 6e 74 20 63 6f 6e 6e 65 63 74 69 6f  ferent connectio
5d70: 6e 20 74 68 61 74 20 73 68 61 72 65 73 20 74 68  n that shares th
5d80: 65 20 42 74 53 68 61 72 65 64 20 63 61 63 68 65  e BtShared cache
5d90: 20 77 69 74 68 20 74 68 69 73 0a 2a 2a 20 20 20   with this.**   
5da0: 63 75 72 73 6f 72 2e 20 20 54 68 65 20 65 72 72  cursor.  The err
5db0: 6f 72 20 68 61 73 20 6c 65 66 74 20 74 68 65 20  or has left the 
5dc0: 63 61 63 68 65 20 69 6e 20 61 6e 20 69 6e 63 6f  cache in an inco
5dd0: 6e 73 69 73 74 65 6e 74 20 73 74 61 74 65 2e 0a  nsistent state..
5de0: 2a 2a 20 20 20 44 6f 20 6e 6f 74 68 69 6e 67 20  **   Do nothing 
5df0: 65 6c 73 65 20 77 69 74 68 20 74 68 69 73 20 63  else with this c
5e00: 75 72 73 6f 72 2e 20 20 41 6e 79 20 61 74 74 65  ursor.  Any atte
5e10: 6d 70 74 20 74 6f 20 75 73 65 20 74 68 65 20 63  mpt to use the c
5e20: 75 72 73 6f 72 0a 2a 2a 20 20 20 73 68 6f 75 6c  ursor.**   shoul
5e30: 64 20 72 65 74 75 72 6e 20 74 68 65 20 65 72 72  d return the err
5e40: 6f 72 20 63 6f 64 65 20 73 74 6f 72 65 64 20 69  or code stored i
5e50: 6e 20 42 74 43 75 72 73 6f 72 2e 73 6b 69 70 0a  n BtCursor.skip.
5e60: 2a 2f 0a 23 64 65 66 69 6e 65 20 43 55 52 53 4f  */.#define CURSO
5e70: 52 5f 49 4e 56 41 4c 49 44 20 20 20 20 20 20 20  R_INVALID       
5e80: 20 20 20 20 30 0a 23 64 65 66 69 6e 65 20 43 55      0.#define CU
5e90: 52 53 4f 52 5f 56 41 4c 49 44 20 20 20 20 20 20  RSOR_VALID      
5ea0: 20 20 20 20 20 20 20 31 0a 23 64 65 66 69 6e 65         1.#define
5eb0: 20 43 55 52 53 4f 52 5f 52 45 51 55 49 52 45 53   CURSOR_REQUIRES
5ec0: 45 45 4b 20 20 20 20 20 20 20 32 0a 23 64 65 66  EEK       2.#def
5ed0: 69 6e 65 20 43 55 52 53 4f 52 5f 46 41 55 4c 54  ine CURSOR_FAULT
5ee0: 20 20 20 20 20 20 20 20 20 20 20 20 20 33 0a 0a               3..
5ef0: 2f 2a 20 0a 2a 2a 20 54 68 65 20 64 61 74 61 62  /* .** The datab
5f00: 61 73 65 20 70 61 67 65 20 74 68 65 20 50 45 4e  ase page the PEN
5f10: 44 49 4e 47 5f 42 59 54 45 20 6f 63 63 75 70 69  DING_BYTE occupi
5f20: 65 73 2e 20 54 68 69 73 20 70 61 67 65 20 69 73  es. This page is
5f30: 20 6e 65 76 65 72 20 75 73 65 64 2e 0a 2a 2f 0a   never used..*/.
5f40: 23 20 64 65 66 69 6e 65 20 50 45 4e 44 49 4e 47  # define PENDING
5f50: 5f 42 59 54 45 5f 50 41 47 45 28 70 42 74 29 20  _BYTE_PAGE(pBt) 
5f60: 50 41 47 45 52 5f 4d 4a 5f 50 47 4e 4f 28 70 42  PAGER_MJ_PGNO(pB
5f70: 74 29 0a 0a 2f 2a 0a 2a 2a 20 54 68 65 73 65 20  t)../*.** These 
5f80: 6d 61 63 72 6f 73 20 64 65 66 69 6e 65 20 74 68  macros define th
5f90: 65 20 6c 6f 63 61 74 69 6f 6e 20 6f 66 20 74 68  e location of th
5fa0: 65 20 70 6f 69 6e 74 65 72 2d 6d 61 70 20 65 6e  e pointer-map en
5fb0: 74 72 79 20 66 6f 72 20 61 20 0a 2a 2a 20 64 61  try for a .** da
5fc0: 74 61 62 61 73 65 20 70 61 67 65 2e 20 54 68 65  tabase page. The
5fd0: 20 66 69 72 73 74 20 61 72 67 75 6d 65 6e 74 20   first argument 
5fe0: 74 6f 20 65 61 63 68 20 69 73 20 74 68 65 20 6e  to each is the n
5ff0: 75 6d 62 65 72 20 6f 66 20 75 73 61 62 6c 65 0a  umber of usable.
6000: 2a 2a 20 62 79 74 65 73 20 6f 6e 20 65 61 63 68  ** bytes on each
6010: 20 70 61 67 65 20 6f 66 20 74 68 65 20 64 61 74   page of the dat
6020: 61 62 61 73 65 20 28 6f 66 74 65 6e 20 31 30 32  abase (often 102
6030: 34 29 2e 20 54 68 65 20 73 65 63 6f 6e 64 20 69  4). The second i
6040: 73 20 74 68 65 0a 2a 2a 20 70 61 67 65 20 6e 75  s the.** page nu
6050: 6d 62 65 72 20 74 6f 20 6c 6f 6f 6b 20 75 70 20  mber to look up 
6060: 69 6e 20 74 68 65 20 70 6f 69 6e 74 65 72 20 6d  in the pointer m
6070: 61 70 2e 0a 2a 2a 0a 2a 2a 20 50 54 52 4d 41 50  ap..**.** PTRMAP
6080: 5f 50 41 47 45 4e 4f 20 72 65 74 75 72 6e 73 20  _PAGENO returns 
6090: 74 68 65 20 64 61 74 61 62 61 73 65 20 70 61 67  the database pag
60a0: 65 20 6e 75 6d 62 65 72 20 6f 66 20 74 68 65 20  e number of the 
60b0: 70 6f 69 6e 74 65 72 2d 6d 61 70 0a 2a 2a 20 70  pointer-map.** p
60c0: 61 67 65 20 74 68 61 74 20 73 74 6f 72 65 73 20  age that stores 
60d0: 74 68 65 20 72 65 71 75 69 72 65 64 20 70 6f 69  the required poi
60e0: 6e 74 65 72 2e 20 50 54 52 4d 41 50 5f 50 54 52  nter. PTRMAP_PTR
60f0: 4f 46 46 53 45 54 20 72 65 74 75 72 6e 73 0a 2a  OFFSET returns.*
6100: 2a 20 74 68 65 20 6f 66 66 73 65 74 20 6f 66 20  * the offset of 
6110: 74 68 65 20 72 65 71 75 65 73 74 65 64 20 6d 61  the requested ma
6120: 70 20 65 6e 74 72 79 2e 0a 2a 2a 0a 2a 2a 20 49  p entry..**.** I
6130: 66 20 74 68 65 20 70 67 6e 6f 20 61 72 67 75 6d  f the pgno argum
6140: 65 6e 74 20 70 61 73 73 65 64 20 74 6f 20 50 54  ent passed to PT
6150: 52 4d 41 50 5f 50 41 47 45 4e 4f 20 69 73 20 61  RMAP_PAGENO is a
6160: 20 70 6f 69 6e 74 65 72 2d 6d 61 70 20 70 61 67   pointer-map pag
6170: 65 2c 0a 2a 2a 20 74 68 65 6e 20 70 67 6e 6f 20  e,.** then pgno 
6180: 69 73 20 72 65 74 75 72 6e 65 64 2e 20 53 6f 20  is returned. So 
6190: 28 70 67 6e 6f 3d 3d 50 54 52 4d 41 50 5f 50 41  (pgno==PTRMAP_PA
61a0: 47 45 4e 4f 28 70 67 73 7a 2c 20 70 67 6e 6f 29  GENO(pgsz, pgno)
61b0: 29 20 63 61 6e 20 62 65 0a 2a 2a 20 75 73 65 64  ) can be.** used
61c0: 20 74 6f 20 74 65 73 74 20 69 66 20 70 67 6e 6f   to test if pgno
61d0: 20 69 73 20 61 20 70 6f 69 6e 74 65 72 2d 6d 61   is a pointer-ma
61e0: 70 20 70 61 67 65 2e 20 50 54 52 4d 41 50 5f 49  p page. PTRMAP_I
61f0: 53 50 41 47 45 20 69 6d 70 6c 65 6d 65 6e 74 73  SPAGE implements
6200: 0a 2a 2a 20 74 68 69 73 20 74 65 73 74 2e 0a 2a  .** this test..*
6210: 2f 0a 23 64 65 66 69 6e 65 20 50 54 52 4d 41 50  /.#define PTRMAP
6220: 5f 50 41 47 45 4e 4f 28 70 42 74 2c 20 70 67 6e  _PAGENO(pBt, pgn
6230: 6f 29 20 70 74 72 6d 61 70 50 61 67 65 6e 6f 28  o) ptrmapPageno(
6240: 70 42 74 2c 20 70 67 6e 6f 29 0a 23 64 65 66 69  pBt, pgno).#defi
6250: 6e 65 20 50 54 52 4d 41 50 5f 50 54 52 4f 46 46  ne PTRMAP_PTROFF
6260: 53 45 54 28 70 67 70 74 72 6d 61 70 2c 20 70 67  SET(pgptrmap, pg
6270: 6e 6f 29 20 28 35 2a 28 70 67 6e 6f 2d 70 67 70  no) (5*(pgno-pgp
6280: 74 72 6d 61 70 2d 31 29 29 0a 23 64 65 66 69 6e  trmap-1)).#defin
6290: 65 20 50 54 52 4d 41 50 5f 49 53 50 41 47 45 28  e PTRMAP_ISPAGE(
62a0: 70 42 74 2c 20 70 67 6e 6f 29 20 28 50 54 52 4d  pBt, pgno) (PTRM
62b0: 41 50 5f 50 41 47 45 4e 4f 28 28 70 42 74 29 2c  AP_PAGENO((pBt),
62c0: 28 70 67 6e 6f 29 29 3d 3d 28 70 67 6e 6f 29 29  (pgno))==(pgno))
62d0: 0a 0a 2f 2a 0a 2a 2a 20 54 68 65 20 70 6f 69 6e  ../*.** The poin
62e0: 74 65 72 20 6d 61 70 20 69 73 20 61 20 6c 6f 6f  ter map is a loo
62f0: 6b 75 70 20 74 61 62 6c 65 20 74 68 61 74 20 69  kup table that i
6300: 64 65 6e 74 69 66 69 65 73 20 74 68 65 20 70 61  dentifies the pa
6310: 72 65 6e 74 20 70 61 67 65 20 66 6f 72 0a 2a 2a  rent page for.**
6320: 20 65 61 63 68 20 63 68 69 6c 64 20 70 61 67 65   each child page
6330: 20 69 6e 20 74 68 65 20 64 61 74 61 62 61 73 65   in the database
6340: 20 66 69 6c 65 2e 20 20 54 68 65 20 70 61 72 65   file.  The pare
6350: 6e 74 20 70 61 67 65 20 69 73 20 74 68 65 20 70  nt page is the p
6360: 61 67 65 20 74 68 61 74 0a 2a 2a 20 63 6f 6e 74  age that.** cont
6370: 61 69 6e 73 20 61 20 70 6f 69 6e 74 65 72 20 74  ains a pointer t
6380: 6f 20 74 68 65 20 63 68 69 6c 64 2e 20 20 45 76  o the child.  Ev
6390: 65 72 79 20 70 61 67 65 20 69 6e 20 74 68 65 20  ery page in the 
63a0: 64 61 74 61 62 61 73 65 20 63 6f 6e 74 61 69 6e  database contain
63b0: 73 0a 2a 2a 20 30 20 6f 72 20 31 20 70 61 72 65  s.** 0 or 1 pare
63c0: 6e 74 20 70 61 67 65 73 2e 20 20 28 49 6e 20 74  nt pages.  (In t
63d0: 68 69 73 20 63 6f 6e 74 65 78 74 20 27 64 61 74  his context 'dat
63e0: 61 62 61 73 65 20 70 61 67 65 27 20 72 65 66 65  abase page' refe
63f0: 72 73 0a 2a 2a 20 74 6f 20 61 6e 79 20 70 61 67  rs.** to any pag
6400: 65 20 74 68 61 74 20 69 73 20 6e 6f 74 20 70 61  e that is not pa
6410: 72 74 20 6f 66 20 74 68 65 20 70 6f 69 6e 74 65  rt of the pointe
6420: 72 20 6d 61 70 20 69 74 73 65 6c 66 2e 29 20 20  r map itself.)  
6430: 45 61 63 68 20 70 6f 69 6e 74 65 72 20 6d 61 70  Each pointer map
6440: 0a 2a 2a 20 65 6e 74 72 79 20 63 6f 6e 73 69 73  .** entry consis
6450: 74 73 20 6f 66 20 61 20 73 69 6e 67 6c 65 20 62  ts of a single b
6460: 79 74 65 20 27 74 79 70 65 27 20 61 6e 64 20 61  yte 'type' and a
6470: 20 34 20 62 79 74 65 20 70 61 72 65 6e 74 20 70   4 byte parent p
6480: 61 67 65 20 6e 75 6d 62 65 72 2e 0a 2a 2a 20 54  age number..** T
6490: 68 65 20 50 54 52 4d 41 50 5f 58 58 58 20 69 64  he PTRMAP_XXX id
64a0: 65 6e 74 69 66 69 65 72 73 20 62 65 6c 6f 77 20  entifiers below 
64b0: 61 72 65 20 74 68 65 20 76 61 6c 69 64 20 74 79  are the valid ty
64c0: 70 65 73 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 70  pes..**.** The p
64d0: 75 72 70 6f 73 65 20 6f 66 20 74 68 65 20 70 6f  urpose of the po
64e0: 69 6e 74 65 72 20 6d 61 70 20 69 73 20 74 6f 20  inter map is to 
64f0: 66 61 63 69 6c 69 74 79 20 6d 6f 76 69 6e 67 20  facility moving 
6500: 70 61 67 65 73 20 66 72 6f 6d 20 6f 6e 65 0a 2a  pages from one.*
6510: 2a 20 70 6f 73 69 74 69 6f 6e 20 69 6e 20 74 68  * position in th
6520: 65 20 66 69 6c 65 20 74 6f 20 61 6e 6f 74 68 65  e file to anothe
6530: 72 20 61 73 20 70 61 72 74 20 6f 66 20 61 75 74  r as part of aut
6540: 6f 76 61 63 75 75 6d 2e 20 20 57 68 65 6e 20 61  ovacuum.  When a
6550: 20 70 61 67 65 0a 2a 2a 20 69 73 20 6d 6f 76 65   page.** is move
6560: 64 2c 20 74 68 65 20 70 6f 69 6e 74 65 72 20 69  d, the pointer i
6570: 6e 20 69 74 73 20 70 61 72 65 6e 74 20 6d 75 73  n its parent mus
6580: 74 20 62 65 20 75 70 64 61 74 65 64 20 74 6f 20  t be updated to 
6590: 70 6f 69 6e 74 20 74 6f 20 74 68 65 0a 2a 2a 20  point to the.** 
65a0: 6e 65 77 20 6c 6f 63 61 74 69 6f 6e 2e 20 20 54  new location.  T
65b0: 68 65 20 70 6f 69 6e 74 65 72 20 6d 61 70 20 69  he pointer map i
65c0: 73 20 75 73 65 64 20 74 6f 20 6c 6f 63 61 74 65  s used to locate
65d0: 20 74 68 65 20 70 61 72 65 6e 74 20 70 61 67 65   the parent page
65e0: 20 71 75 69 63 6b 6c 79 2e 0a 2a 2a 0a 2a 2a 20   quickly..**.** 
65f0: 50 54 52 4d 41 50 5f 52 4f 4f 54 50 41 47 45 3a  PTRMAP_ROOTPAGE:
6600: 20 54 68 65 20 64 61 74 61 62 61 73 65 20 70 61   The database pa
6610: 67 65 20 69 73 20 61 20 72 6f 6f 74 2d 70 61 67  ge is a root-pag
6620: 65 2e 20 54 68 65 20 70 61 67 65 2d 6e 75 6d 62  e. The page-numb
6630: 65 72 20 69 73 20 6e 6f 74 0a 2a 2a 20 20 20 20  er is not.**    
6640: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 75 73                us
6650: 65 64 20 69 6e 20 74 68 69 73 20 63 61 73 65 2e  ed in this case.
6660: 0a 2a 2a 0a 2a 2a 20 50 54 52 4d 41 50 5f 46 52  .**.** PTRMAP_FR
6670: 45 45 50 41 47 45 3a 20 54 68 65 20 64 61 74 61  EEPAGE: The data
6680: 62 61 73 65 20 70 61 67 65 20 69 73 20 61 6e 20  base page is an 
6690: 75 6e 75 73 65 64 20 28 66 72 65 65 29 20 70 61  unused (free) pa
66a0: 67 65 2e 20 54 68 65 20 70 61 67 65 2d 6e 75 6d  ge. The page-num
66b0: 62 65 72 20 0a 2a 2a 20 20 20 20 20 20 20 20 20  ber .**         
66c0: 20 20 20 20 20 20 20 20 20 69 73 20 6e 6f 74 20           is not 
66d0: 75 73 65 64 20 69 6e 20 74 68 69 73 20 63 61 73  used in this cas
66e0: 65 2e 0a 2a 2a 0a 2a 2a 20 50 54 52 4d 41 50 5f  e..**.** PTRMAP_
66f0: 4f 56 45 52 46 4c 4f 57 31 3a 20 54 68 65 20 64  OVERFLOW1: The d
6700: 61 74 61 62 61 73 65 20 70 61 67 65 20 69 73 20  atabase page is 
6710: 74 68 65 20 66 69 72 73 74 20 70 61 67 65 20 69  the first page i
6720: 6e 20 61 20 6c 69 73 74 20 6f 66 20 0a 2a 2a 20  n a list of .** 
6730: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
6740: 20 20 6f 76 65 72 66 6c 6f 77 20 70 61 67 65 73    overflow pages
6750: 2e 20 54 68 65 20 70 61 67 65 20 6e 75 6d 62 65  . The page numbe
6760: 72 20 69 64 65 6e 74 69 66 69 65 73 20 74 68 65  r identifies the
6770: 20 70 61 67 65 20 74 68 61 74 0a 2a 2a 20 20 20   page that.**   
6780: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
6790: 63 6f 6e 74 61 69 6e 73 20 74 68 65 20 63 65 6c  contains the cel
67a0: 6c 20 77 69 74 68 20 61 20 70 6f 69 6e 74 65 72  l with a pointer
67b0: 20 74 6f 20 74 68 69 73 20 6f 76 65 72 66 6c 6f   to this overflo
67c0: 77 20 70 61 67 65 2e 0a 2a 2a 0a 2a 2a 20 50 54  w page..**.** PT
67d0: 52 4d 41 50 5f 4f 56 45 52 46 4c 4f 57 32 3a 20  RMAP_OVERFLOW2: 
67e0: 54 68 65 20 64 61 74 61 62 61 73 65 20 70 61 67  The database pag
67f0: 65 20 69 73 20 74 68 65 20 73 65 63 6f 6e 64 20  e is the second 
6800: 6f 72 20 6c 61 74 65 72 20 70 61 67 65 20 69 6e  or later page in
6810: 20 61 20 6c 69 73 74 20 6f 66 0a 2a 2a 20 20 20   a list of.**   
6820: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
6830: 6f 76 65 72 66 6c 6f 77 20 70 61 67 65 73 2e 20  overflow pages. 
6840: 54 68 65 20 70 61 67 65 2d 6e 75 6d 62 65 72 20  The page-number 
6850: 69 64 65 6e 74 69 66 69 65 73 20 74 68 65 20 70  identifies the p
6860: 72 65 76 69 6f 75 73 0a 2a 2a 20 20 20 20 20 20  revious.**      
6870: 20 20 20 20 20 20 20 20 20 20 20 20 20 70 61 67               pag
6880: 65 20 69 6e 20 74 68 65 20 6f 76 65 72 66 6c 6f  e in the overflo
6890: 77 20 70 61 67 65 20 6c 69 73 74 2e 0a 2a 2a 0a  w page list..**.
68a0: 2a 2a 20 50 54 52 4d 41 50 5f 42 54 52 45 45 3a  ** PTRMAP_BTREE:
68b0: 20 54 68 65 20 64 61 74 61 62 61 73 65 20 70 61   The database pa
68c0: 67 65 20 69 73 20 61 20 6e 6f 6e 2d 72 6f 6f 74  ge is a non-root
68d0: 20 62 74 72 65 65 20 70 61 67 65 2e 20 54 68 65   btree page. The
68e0: 20 70 61 67 65 20 6e 75 6d 62 65 72 0a 2a 2a 20   page number.** 
68f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 69 64                id
6900: 65 6e 74 69 66 69 65 73 20 74 68 65 20 70 61 72  entifies the par
6910: 65 6e 74 20 70 61 67 65 20 69 6e 20 74 68 65 20  ent page in the 
6920: 62 74 72 65 65 2e 0a 2a 2f 0a 23 64 65 66 69 6e  btree..*/.#defin
6930: 65 20 50 54 52 4d 41 50 5f 52 4f 4f 54 50 41 47  e PTRMAP_ROOTPAG
6940: 45 20 31 0a 23 64 65 66 69 6e 65 20 50 54 52 4d  E 1.#define PTRM
6950: 41 50 5f 46 52 45 45 50 41 47 45 20 32 0a 23 64  AP_FREEPAGE 2.#d
6960: 65 66 69 6e 65 20 50 54 52 4d 41 50 5f 4f 56 45  efine PTRMAP_OVE
6970: 52 46 4c 4f 57 31 20 33 0a 23 64 65 66 69 6e 65  RFLOW1 3.#define
6980: 20 50 54 52 4d 41 50 5f 4f 56 45 52 46 4c 4f 57   PTRMAP_OVERFLOW
6990: 32 20 34 0a 23 64 65 66 69 6e 65 20 50 54 52 4d  2 4.#define PTRM
69a0: 41 50 5f 42 54 52 45 45 20 35 0a 0a 2f 2a 20 41  AP_BTREE 5../* A
69b0: 20 62 75 6e 63 68 20 6f 66 20 61 73 73 65 72 74   bunch of assert
69c0: 28 29 20 73 74 61 74 65 6d 65 6e 74 73 20 74 6f  () statements to
69d0: 20 63 68 65 63 6b 20 74 68 65 20 74 72 61 6e 73   check the trans
69e0: 61 63 74 69 6f 6e 20 73 74 61 74 65 20 76 61 72  action state var
69f0: 69 61 62 6c 65 73 0a 2a 2a 20 6f 66 20 68 61 6e  iables.** of han
6a00: 64 6c 65 20 70 20 28 74 79 70 65 20 42 74 72 65  dle p (type Btre
6a10: 65 2a 29 20 61 72 65 20 69 6e 74 65 72 6e 61 6c  e*) are internal
6a20: 6c 79 20 63 6f 6e 73 69 73 74 65 6e 74 2e 0a 2a  ly consistent..*
6a30: 2f 0a 23 64 65 66 69 6e 65 20 62 74 72 65 65 49  /.#define btreeI
6a40: 6e 74 65 67 72 69 74 79 28 70 29 20 5c 0a 20 20  ntegrity(p) \.  
6a50: 61 73 73 65 72 74 28 20 70 2d 3e 70 42 74 2d 3e  assert( p->pBt->
6a60: 69 6e 54 72 61 6e 73 61 63 74 69 6f 6e 21 3d 54  inTransaction!=T
6a70: 52 41 4e 53 5f 4e 4f 4e 45 20 7c 7c 20 70 2d 3e  RANS_NONE || p->
6a80: 70 42 74 2d 3e 6e 54 72 61 6e 73 61 63 74 69 6f  pBt->nTransactio
6a90: 6e 3d 3d 30 20 29 3b 20 5c 0a 20 20 61 73 73 65  n==0 ); \.  asse
6aa0: 72 74 28 20 70 2d 3e 70 42 74 2d 3e 69 6e 54 72  rt( p->pBt->inTr
6ab0: 61 6e 73 61 63 74 69 6f 6e 3e 3d 70 2d 3e 69 6e  ansaction>=p->in
6ac0: 54 72 61 6e 73 20 29 3b 20 0a 0a 0a 2f 2a 0a 2a  Trans ); .../*.*
6ad0: 2a 20 54 68 65 20 49 53 41 55 54 4f 56 41 43 55  * The ISAUTOVACU
6ae0: 55 4d 20 6d 61 63 72 6f 20 69 73 20 75 73 65 64  UM macro is used
6af0: 20 77 69 74 68 69 6e 20 62 61 6c 61 6e 63 65 5f   within balance_
6b00: 6e 6f 6e 72 6f 6f 74 28 29 20 74 6f 20 64 65 74  nonroot() to det
6b10: 65 72 6d 69 6e 65 0a 2a 2a 20 69 66 20 74 68 65  ermine.** if the
6b20: 20 64 61 74 61 62 61 73 65 20 73 75 70 70 6f 72   database suppor
6b30: 74 73 20 61 75 74 6f 2d 76 61 63 75 75 6d 20 6f  ts auto-vacuum o
6b40: 72 20 6e 6f 74 2e 20 42 65 63 61 75 73 65 20 69  r not. Because i
6b50: 74 20 69 73 20 75 73 65 64 0a 2a 2a 20 77 69 74  t is used.** wit
6b60: 68 69 6e 20 61 6e 20 65 78 70 72 65 73 73 69 6f  hin an expressio
6b70: 6e 20 74 68 61 74 20 69 73 20 61 6e 20 61 72 67  n that is an arg
6b80: 75 6d 65 6e 74 20 74 6f 20 61 6e 6f 74 68 65 72  ument to another
6b90: 20 6d 61 63 72 6f 20 0a 2a 2a 20 28 73 71 6c 69   macro .** (sqli
6ba0: 74 65 4d 61 6c 6c 6f 63 52 61 77 29 2c 20 69 74  teMallocRaw), it
6bb0: 20 69 73 20 6e 6f 74 20 70 6f 73 73 69 62 6c 65   is not possible
6bc0: 20 74 6f 20 75 73 65 20 63 6f 6e 64 69 74 69 6f   to use conditio
6bd0: 6e 61 6c 20 63 6f 6d 70 69 6c 61 74 69 6f 6e 2e  nal compilation.
6be0: 0a 2a 2a 20 53 6f 2c 20 74 68 69 73 20 6d 61 63  .** So, this mac
6bf0: 72 6f 20 69 73 20 64 65 66 69 6e 65 64 20 69 6e  ro is defined in
6c00: 73 74 65 61 64 2e 0a 2a 2f 0a 23 69 66 6e 64 65  stead..*/.#ifnde
6c10: 66 20 53 51 4c 49 54 45 5f 4f 4d 49 54 5f 41 55  f SQLITE_OMIT_AU
6c20: 54 4f 56 41 43 55 55 4d 0a 23 64 65 66 69 6e 65  TOVACUUM.#define
6c30: 20 49 53 41 55 54 4f 56 41 43 55 55 4d 20 28 70   ISAUTOVACUUM (p
6c40: 42 74 2d 3e 61 75 74 6f 56 61 63 75 75 6d 29 0a  Bt->autoVacuum).
6c50: 23 65 6c 73 65 0a 23 64 65 66 69 6e 65 20 49 53  #else.#define IS
6c60: 41 55 54 4f 56 41 43 55 55 4d 20 30 0a 23 65 6e  AUTOVACUUM 0.#en
6c70: 64 69 66 0a 0a 0a 2f 2a 0a 2a 2a 20 54 68 69 73  dif.../*.** This
6c80: 20 73 74 72 75 63 74 75 72 65 20 69 73 20 70 61   structure is pa
6c90: 73 73 65 64 20 61 72 6f 75 6e 64 20 74 68 72 6f  ssed around thro
6ca0: 75 67 68 20 61 6c 6c 20 74 68 65 20 73 61 6e 69  ugh all the sani
6cb0: 74 79 20 63 68 65 63 6b 69 6e 67 20 72 6f 75 74  ty checking rout
6cc0: 69 6e 65 73 0a 2a 2a 20 69 6e 20 6f 72 64 65 72  ines.** in order
6cd0: 20 74 6f 20 6b 65 65 70 20 74 72 61 63 6b 20 6f   to keep track o
6ce0: 66 20 73 6f 6d 65 20 67 6c 6f 62 61 6c 20 73 74  f some global st
6cf0: 61 74 65 20 69 6e 66 6f 72 6d 61 74 69 6f 6e 2e  ate information.
6d00: 0a 2a 2f 0a 74 79 70 65 64 65 66 20 73 74 72 75  .*/.typedef stru
6d10: 63 74 20 49 6e 74 65 67 72 69 74 79 43 6b 20 49  ct IntegrityCk I
6d20: 6e 74 65 67 72 69 74 79 43 6b 3b 0a 73 74 72 75  ntegrityCk;.stru
6d30: 63 74 20 49 6e 74 65 67 72 69 74 79 43 6b 20 7b  ct IntegrityCk {
6d40: 0a 20 20 42 74 53 68 61 72 65 64 20 2a 70 42 74  .  BtShared *pBt
6d50: 3b 20 20 20 20 2f 2a 20 54 68 65 20 74 72 65 65  ;    /* The tree
6d60: 20 62 65 69 6e 67 20 63 68 65 63 6b 65 64 20 6f   being checked o
6d70: 75 74 20 2a 2f 0a 20 20 50 61 67 65 72 20 2a 70  ut */.  Pager *p
6d80: 50 61 67 65 72 3b 20 20 20 20 2f 2a 20 54 68 65  Pager;    /* The
6d90: 20 61 73 73 6f 63 69 61 74 65 64 20 70 61 67 65   associated page
6da0: 72 2e 20 20 41 6c 73 6f 20 61 63 63 65 73 73 69  r.  Also accessi
6db0: 62 6c 65 20 62 79 20 70 42 74 2d 3e 70 50 61 67  ble by pBt->pPag
6dc0: 65 72 20 2a 2f 0a 20 20 50 67 6e 6f 20 6e 50 61  er */.  Pgno nPa
6dd0: 67 65 3b 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d  ge;       /* Num
6de0: 62 65 72 20 6f 66 20 70 61 67 65 73 20 69 6e 20  ber of pages in 
6df0: 74 68 65 20 64 61 74 61 62 61 73 65 20 2a 2f 0a  the database */.
6e00: 20 20 69 6e 74 20 2a 61 6e 52 65 66 3b 20 20 20    int *anRef;   
6e10: 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66      /* Number of
6e20: 20 74 69 6d 65 73 20 65 61 63 68 20 70 61 67 65   times each page
6e30: 20 69 73 20 72 65 66 65 72 65 6e 63 65 64 20 2a   is referenced *
6e40: 2f 0a 20 20 69 6e 74 20 6d 78 45 72 72 3b 20 20  /.  int mxErr;  
6e50: 20 20 20 20 20 20 2f 2a 20 53 74 6f 70 20 61 63        /* Stop ac
6e60: 63 75 6d 75 6c 61 74 69 6e 67 20 65 72 72 6f 72  cumulating error
6e70: 73 20 77 68 65 6e 20 74 68 69 73 20 72 65 61 63  s when this reac
6e80: 68 65 73 20 7a 65 72 6f 20 2a 2f 0a 20 20 69 6e  hes zero */.  in
6e90: 74 20 6e 45 72 72 3b 20 20 20 20 20 20 20 20 20  t nErr;         
6ea0: 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 6d 65 73  /* Number of mes
6eb0: 73 61 67 65 73 20 77 72 69 74 74 65 6e 20 74 6f  sages written to
6ec0: 20 7a 45 72 72 4d 73 67 20 73 6f 20 66 61 72 20   zErrMsg so far 
6ed0: 2a 2f 0a 20 20 69 6e 74 20 6d 61 6c 6c 6f 63 46  */.  int mallocF
6ee0: 61 69 6c 65 64 3b 20 2f 2a 20 41 20 6d 65 6d 6f  ailed; /* A memo
6ef0: 72 79 20 61 6c 6c 6f 63 61 74 69 6f 6e 20 65 72  ry allocation er
6f00: 72 6f 72 20 68 61 73 20 6f 63 63 75 72 72 65 64  ror has occurred
6f10: 20 2a 2f 0a 20 20 53 74 72 41 63 63 75 6d 20 65   */.  StrAccum e
6f20: 72 72 4d 73 67 3b 20 20 2f 2a 20 41 63 63 75 6d  rrMsg;  /* Accum
6f30: 75 6c 61 74 65 20 74 68 65 20 65 72 72 6f 72 20  ulate the error 
6f40: 6d 65 73 73 61 67 65 20 74 65 78 74 20 68 65 72  message text her
6f50: 65 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 52  e */.};../*.** R
6f60: 65 61 64 20 6f 72 20 77 72 69 74 65 20 61 20 74  ead or write a t
6f70: 77 6f 2d 20 61 6e 64 20 66 6f 75 72 2d 62 79 74  wo- and four-byt
6f80: 65 20 62 69 67 2d 65 6e 64 69 61 6e 20 69 6e 74  e big-endian int
6f90: 65 67 65 72 20 76 61 6c 75 65 73 2e 0a 2a 2f 0a  eger values..*/.
6fa0: 23 64 65 66 69 6e 65 20 67 65 74 32 62 79 74 65  #define get2byte
6fb0: 28 78 29 20 20 20 28 28 78 29 5b 30 5d 3c 3c 38  (x)   ((x)[0]<<8
6fc0: 20 7c 20 28 78 29 5b 31 5d 29 0a 23 64 65 66 69   | (x)[1]).#defi
6fd0: 6e 65 20 70 75 74 32 62 79 74 65 28 70 2c 76 29  ne put2byte(p,v)
6fe0: 20 28 28 70 29 5b 30 5d 20 3d 20 28 75 38 29 28   ((p)[0] = (u8)(
6ff0: 28 76 29 3e 3e 38 29 2c 20 28 70 29 5b 31 5d 20  (v)>>8), (p)[1] 
7000: 3d 20 28 75 38 29 28 76 29 29 0a 23 64 65 66 69  = (u8)(v)).#defi
7010: 6e 65 20 67 65 74 34 62 79 74 65 20 73 71 6c 69  ne get4byte sqli
7020: 74 65 33 47 65 74 34 62 79 74 65 0a 23 64 65 66  te3Get4byte.#def
7030: 69 6e 65 20 70 75 74 34 62 79 74 65 20 73 71 6c  ine put4byte sql
7040: 69 74 65 33 50 75 74 34 62 79 74 65 0a 0a        ite3Put4byte..