/ Hex Artifact Content
Login

Artifact 6714ce2f5e879eb9a904a6a4575dc4faa4f29991:


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 54 68 69 73 20 66 69 6c 65 20 69  *.** This file i
0180: 6d 70 6c 65 6d 65 6e 74 73 20 61 20 65 78 74 65  mplements a exte
0190: 72 6e 61 6c 20 28 64 69 73 6b 2d 62 61 73 65 64  rnal (disk-based
01a0: 29 20 64 61 74 61 62 61 73 65 20 75 73 69 6e 67  ) database using
01b0: 20 42 54 72 65 65 73 2e 0a 2a 2a 20 46 6f 72 20   BTrees..** For 
01c0: 61 20 64 65 74 61 69 6c 65 64 20 64 69 73 63 75  a detailed discu
01d0: 73 73 69 6f 6e 20 6f 66 20 42 54 72 65 65 73 2c  ssion of BTrees,
01e0: 20 72 65 66 65 72 20 74 6f 0a 2a 2a 0a 2a 2a 20   refer to.**.** 
01f0: 20 20 20 20 44 6f 6e 61 6c 64 20 45 2e 20 4b 6e      Donald E. Kn
0200: 75 74 68 2c 20 54 48 45 20 41 52 54 20 4f 46 20  uth, THE ART OF 
0210: 43 4f 4d 50 55 54 45 52 20 50 52 4f 47 52 41 4d  COMPUTER PROGRAM
0220: 4d 49 4e 47 2c 20 56 6f 6c 75 6d 65 20 33 3a 0a  MING, Volume 3:.
0230: 2a 2a 20 20 20 20 20 22 53 6f 72 74 69 6e 67 20  **     "Sorting 
0240: 41 6e 64 20 53 65 61 72 63 68 69 6e 67 22 2c 20  And Searching", 
0250: 70 61 67 65 73 20 34 37 33 2d 34 38 30 2e 20 41  pages 473-480. A
0260: 64 64 69 73 6f 6e 2d 57 65 73 6c 65 79 0a 2a 2a  ddison-Wesley.**
0270: 20 20 20 20 20 50 75 62 6c 69 73 68 69 6e 67 20       Publishing 
0280: 43 6f 6d 70 61 6e 79 2c 20 52 65 61 64 69 6e 67  Company, Reading
0290: 2c 20 4d 61 73 73 61 63 68 75 73 65 74 74 73 2e  , Massachusetts.
02a0: 0a 2a 2a 0a 2a 2a 20 54 68 65 20 62 61 73 69 63  .**.** The basic
02b0: 20 69 64 65 61 20 69 73 20 74 68 61 74 20 65 61   idea is that ea
02c0: 63 68 20 70 61 67 65 20 6f 66 20 74 68 65 20 66  ch page of the f
02d0: 69 6c 65 20 63 6f 6e 74 61 69 6e 73 20 4e 20 64  ile contains N d
02e0: 61 74 61 62 61 73 65 0a 2a 2a 20 65 6e 74 72 69  atabase.** entri
02f0: 65 73 20 61 6e 64 20 4e 2b 31 20 70 6f 69 6e 74  es and N+1 point
0300: 65 72 73 20 74 6f 20 73 75 62 70 61 67 65 73 2e  ers to subpages.
0310: 0a 2a 2a 0a 2a 2a 20 20 20 2d 2d 2d 2d 2d 2d 2d  .**.**   -------
0320: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
0330: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
0340: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
0350: 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 2a 2a 20 20 20 7c  ---------.**   |
0360: 20 20 50 74 72 28 30 29 20 7c 20 4b 65 79 28 30    Ptr(0) | Key(0
0370: 29 20 7c 20 50 74 72 28 31 29 20 7c 20 4b 65 79  ) | Ptr(1) | Key
0380: 28 31 29 20 7c 20 2e 2e 2e 20 7c 20 4b 65 79 28  (1) | ... | Key(
0390: 4e 2d 31 29 20 7c 20 50 74 72 28 4e 29 20 7c 0a  N-1) | Ptr(N) |.
03a0: 2a 2a 20 20 20 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  **   -----------
03b0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
03c0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
03d0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
03e0: 2d 2d 2d 2d 2d 0a 2a 2a 0a 2a 2a 20 41 6c 6c 20  -----.**.** All 
03f0: 6f 66 20 74 68 65 20 6b 65 79 73 20 6f 6e 20 74  of the keys on t
0400: 68 65 20 70 61 67 65 20 74 68 61 74 20 50 74 72  he page that Ptr
0410: 28 30 29 20 70 6f 69 6e 74 73 20 74 6f 20 68 61  (0) points to ha
0420: 76 65 20 76 61 6c 75 65 73 20 6c 65 73 73 0a 2a  ve values less.*
0430: 2a 20 74 68 61 6e 20 4b 65 79 28 30 29 2e 20 20  * than Key(0).  
0440: 41 6c 6c 20 6f 66 20 74 68 65 20 6b 65 79 73 20  All of the keys 
0450: 6f 6e 20 70 61 67 65 20 50 74 72 28 31 29 20 61  on page Ptr(1) a
0460: 6e 64 20 69 74 73 20 73 75 62 70 61 67 65 73 20  nd its subpages 
0470: 68 61 76 65 0a 2a 2a 20 76 61 6c 75 65 73 20 67  have.** values g
0480: 72 65 61 74 65 72 20 74 68 61 6e 20 4b 65 79 28  reater than Key(
0490: 30 29 20 61 6e 64 20 6c 65 73 73 20 74 68 61 6e  0) and less than
04a0: 20 4b 65 79 28 31 29 2e 20 20 41 6c 6c 20 6f 66   Key(1).  All of
04b0: 20 74 68 65 20 6b 65 79 73 0a 2a 2a 20 6f 6e 20   the keys.** on 
04c0: 50 74 72 28 4e 29 20 61 6e 64 20 69 74 73 20 73  Ptr(N) and its s
04d0: 75 62 70 61 67 65 73 20 68 61 76 65 20 76 61 6c  ubpages have val
04e0: 75 65 73 20 67 72 65 61 74 65 72 20 74 68 61 6e  ues greater than
04f0: 20 4b 65 79 28 4e 2d 31 29 2e 20 20 41 6e 64 0a   Key(N-1).  And.
0500: 2a 2a 20 73 6f 20 66 6f 72 74 68 2e 0a 2a 2a 0a  ** so forth..**.
0510: 2a 2a 20 46 69 6e 64 69 6e 67 20 61 20 70 61 72  ** Finding a par
0520: 74 69 63 75 6c 61 72 20 6b 65 79 20 72 65 71 75  ticular key requ
0530: 69 72 65 73 20 72 65 61 64 69 6e 67 20 4f 28 6c  ires reading O(l
0540: 6f 67 28 4d 29 29 20 70 61 67 65 73 20 66 72 6f  og(M)) pages fro
0550: 6d 20 74 68 65 20 0a 2a 2a 20 64 69 73 6b 20 77  m the .** disk w
0560: 68 65 72 65 20 4d 20 69 73 20 74 68 65 20 6e 75  here M is the nu
0570: 6d 62 65 72 20 6f 66 20 65 6e 74 72 69 65 73 20  mber of entries 
0580: 69 6e 20 74 68 65 20 74 72 65 65 2e 0a 2a 2a 0a  in the tree..**.
0590: 2a 2a 20 49 6e 20 74 68 69 73 20 69 6d 70 6c 65  ** In this imple
05a0: 6d 65 6e 74 61 74 69 6f 6e 2c 20 61 20 73 69 6e  mentation, a sin
05b0: 67 6c 65 20 66 69 6c 65 20 63 61 6e 20 68 6f 6c  gle file can hol
05c0: 64 20 6f 6e 65 20 6f 72 20 6d 6f 72 65 20 73 65  d one or more se
05d0: 70 61 72 61 74 65 20 0a 2a 2a 20 42 54 72 65 65  parate .** BTree
05e0: 73 2e 20 20 45 61 63 68 20 42 54 72 65 65 20 69  s.  Each BTree i
05f0: 73 20 69 64 65 6e 74 69 66 69 65 64 20 62 79 20  s identified by 
0600: 74 68 65 20 69 6e 64 65 78 20 6f 66 20 69 74 73  the index of its
0610: 20 72 6f 6f 74 20 70 61 67 65 2e 20 20 54 68 65   root page.  The
0620: 0a 2a 2a 20 6b 65 79 20 61 6e 64 20 64 61 74 61  .** key and data
0630: 20 66 6f 72 20 61 6e 79 20 65 6e 74 72 79 20 61   for any entry a
0640: 72 65 20 63 6f 6d 62 69 6e 65 64 20 74 6f 20 66  re combined to f
0650: 6f 72 6d 20 74 68 65 20 22 70 61 79 6c 6f 61 64  orm the "payload
0660: 22 2e 20 20 41 0a 2a 2a 20 66 69 78 65 64 20 61  ".  A.** fixed a
0670: 6d 6f 75 6e 74 20 6f 66 20 70 61 79 6c 6f 61 64  mount of payload
0680: 20 63 61 6e 20 62 65 20 63 61 72 72 69 65 64 20   can be carried 
0690: 64 69 72 65 63 74 6c 79 20 6f 6e 20 74 68 65 20  directly on the 
06a0: 64 61 74 61 62 61 73 65 0a 2a 2a 20 70 61 67 65  database.** page
06b0: 2e 20 20 49 66 20 74 68 65 20 70 61 79 6c 6f 61  .  If the payloa
06c0: 64 20 69 73 20 6c 61 72 67 65 72 20 74 68 61 6e  d is larger than
06d0: 20 74 68 65 20 70 72 65 73 65 74 20 61 6d 6f 75   the preset amou
06e0: 6e 74 20 74 68 65 6e 20 73 75 72 70 6c 75 73 0a  nt then surplus.
06f0: 2a 2a 20 62 79 74 65 73 20 61 72 65 20 73 74 6f  ** bytes are sto
0700: 72 65 64 20 6f 6e 20 6f 76 65 72 66 6c 6f 77 20  red on overflow 
0710: 70 61 67 65 73 2e 20 20 54 68 65 20 70 61 79 6c  pages.  The payl
0720: 6f 61 64 20 66 6f 72 20 61 6e 20 65 6e 74 72 79  oad for an entry
0730: 0a 2a 2a 20 61 6e 64 20 74 68 65 20 70 72 65 63  .** and the prec
0740: 65 64 69 6e 67 20 70 6f 69 6e 74 65 72 20 61 72  eding pointer ar
0750: 65 20 63 6f 6d 62 69 6e 65 64 20 74 6f 20 66 6f  e combined to fo
0760: 72 6d 20 61 20 22 43 65 6c 6c 22 2e 20 20 45 61  rm a "Cell".  Ea
0770: 63 68 20 0a 2a 2a 20 70 61 67 65 20 68 61 73 20  ch .** page has 
0780: 61 20 73 6d 61 6c 6c 20 68 65 61 64 65 72 20 77  a small header w
0790: 68 69 63 68 20 63 6f 6e 74 61 69 6e 73 20 74 68  hich contains th
07a0: 65 20 50 74 72 28 4e 29 20 70 6f 69 6e 74 65 72  e Ptr(N) pointer
07b0: 20 61 6e 64 20 6f 74 68 65 72 0a 2a 2a 20 69 6e   and other.** in
07c0: 66 6f 72 6d 61 74 69 6f 6e 20 73 75 63 68 20 61  formation such a
07d0: 73 20 74 68 65 20 73 69 7a 65 20 6f 66 20 6b 65  s the size of ke
07e0: 79 20 61 6e 64 20 64 61 74 61 2e 0a 2a 2a 0a 2a  y and data..**.*
07f0: 2a 20 46 4f 52 4d 41 54 20 44 45 54 41 49 4c 53  * FORMAT DETAILS
0800: 0a 2a 2a 0a 2a 2a 20 54 68 65 20 66 69 6c 65 20  .**.** The file 
0810: 69 73 20 64 69 76 69 64 65 64 20 69 6e 74 6f 20  is divided into 
0820: 70 61 67 65 73 2e 20 20 54 68 65 20 66 69 72 73  pages.  The firs
0830: 74 20 70 61 67 65 20 69 73 20 63 61 6c 6c 65 64  t page is called
0840: 20 70 61 67 65 20 31 2c 0a 2a 2a 20 74 68 65 20   page 1,.** the 
0850: 73 65 63 6f 6e 64 20 69 73 20 70 61 67 65 20 32  second is page 2
0860: 2c 20 61 6e 64 20 73 6f 20 66 6f 72 74 68 2e 20  , and so forth. 
0870: 20 41 20 70 61 67 65 20 6e 75 6d 62 65 72 20 6f   A page number o
0880: 66 20 7a 65 72 6f 20 69 6e 64 69 63 61 74 65 73  f zero indicates
0890: 0a 2a 2a 20 22 6e 6f 20 73 75 63 68 20 70 61 67  .** "no such pag
08a0: 65 22 2e 20 20 54 68 65 20 70 61 67 65 20 73 69  e".  The page si
08b0: 7a 65 20 63 61 6e 20 62 65 20 61 6e 79 20 70 6f  ze can be any po
08c0: 77 65 72 20 6f 66 20 32 20 62 65 74 77 65 65 6e  wer of 2 between
08d0: 20 35 31 32 20 61 6e 64 20 36 35 35 33 36 2e 0a   512 and 65536..
08e0: 2a 2a 20 45 61 63 68 20 70 61 67 65 20 63 61 6e  ** Each page can
08f0: 20 62 65 20 65 69 74 68 65 72 20 61 20 62 74 72   be either a btr
0900: 65 65 20 70 61 67 65 2c 20 61 20 66 72 65 65 6c  ee page, a freel
0910: 69 73 74 20 70 61 67 65 2c 20 61 6e 20 6f 76 65  ist page, an ove
0920: 72 66 6c 6f 77 0a 2a 2a 20 70 61 67 65 2c 20 6f  rflow.** page, o
0930: 72 20 61 20 70 6f 69 6e 74 65 72 2d 6d 61 70 20  r a pointer-map 
0940: 70 61 67 65 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20  page..**.** The 
0950: 66 69 72 73 74 20 70 61 67 65 20 69 73 20 61 6c  first page is al
0960: 77 61 79 73 20 61 20 62 74 72 65 65 20 70 61 67  ways a btree pag
0970: 65 2e 20 20 54 68 65 20 66 69 72 73 74 20 31 30  e.  The first 10
0980: 30 20 62 79 74 65 73 20 6f 66 20 74 68 65 20 66  0 bytes of the f
0990: 69 72 73 74 0a 2a 2a 20 70 61 67 65 20 63 6f 6e  irst.** page con
09a0: 74 61 69 6e 20 61 20 73 70 65 63 69 61 6c 20 68  tain a special h
09b0: 65 61 64 65 72 20 28 74 68 65 20 22 66 69 6c 65  eader (the "file
09c0: 20 68 65 61 64 65 72 22 29 20 74 68 61 74 20 64   header") that d
09d0: 65 73 63 72 69 62 65 73 20 74 68 65 20 66 69 6c  escribes the fil
09e0: 65 2e 0a 2a 2a 20 54 68 65 20 66 6f 72 6d 61 74  e..** The format
09f0: 20 6f 66 20 74 68 65 20 66 69 6c 65 20 68 65 61   of the file hea
0a00: 64 65 72 20 69 73 20 61 73 20 66 6f 6c 6c 6f 77  der is as follow
0a10: 73 3a 0a 2a 2a 0a 2a 2a 20 20 20 4f 46 46 53 45  s:.**.**   OFFSE
0a20: 54 20 20 20 53 49 5a 45 20 20 20 20 44 45 53 43  T   SIZE    DESC
0a30: 52 49 50 54 49 4f 4e 0a 2a 2a 20 20 20 20 20 20  RIPTION.**      
0a40: 30 20 20 20 20 20 20 31 36 20 20 20 20 20 48 65  0      16     He
0a50: 61 64 65 72 20 73 74 72 69 6e 67 3a 20 22 53 51  ader string: "SQ
0a60: 4c 69 74 65 20 66 6f 72 6d 61 74 20 33 5c 30 30  Lite format 3\00
0a70: 30 22 0a 2a 2a 20 20 20 20 20 31 36 20 20 20 20  0".**     16    
0a80: 20 20 20 32 20 20 20 20 20 50 61 67 65 20 73 69     2     Page si
0a90: 7a 65 20 69 6e 20 62 79 74 65 73 2e 20 20 0a 2a  ze in bytes.  .*
0aa0: 2a 20 20 20 20 20 31 38 20 20 20 20 20 20 20 31  *     18       1
0ab0: 20 20 20 20 20 46 69 6c 65 20 66 6f 72 6d 61 74       File format
0ac0: 20 77 72 69 74 65 20 76 65 72 73 69 6f 6e 0a 2a   write version.*
0ad0: 2a 20 20 20 20 20 31 39 20 20 20 20 20 20 20 31  *     19       1
0ae0: 20 20 20 20 20 46 69 6c 65 20 66 6f 72 6d 61 74       File format
0af0: 20 72 65 61 64 20 76 65 72 73 69 6f 6e 0a 2a 2a   read version.**
0b00: 20 20 20 20 20 32 30 20 20 20 20 20 20 20 31 20       20       1 
0b10: 20 20 20 20 42 79 74 65 73 20 6f 66 20 75 6e 75      Bytes of unu
0b20: 73 65 64 20 73 70 61 63 65 20 61 74 20 74 68 65  sed space at the
0b30: 20 65 6e 64 20 6f 66 20 65 61 63 68 20 70 61 67   end of each pag
0b40: 65 0a 2a 2a 20 20 20 20 20 32 31 20 20 20 20 20  e.**     21     
0b50: 20 20 31 20 20 20 20 20 4d 61 78 20 65 6d 62 65    1     Max embe
0b60: 64 64 65 64 20 70 61 79 6c 6f 61 64 20 66 72 61  dded payload fra
0b70: 63 74 69 6f 6e 0a 2a 2a 20 20 20 20 20 32 32 20  ction.**     22 
0b80: 20 20 20 20 20 20 31 20 20 20 20 20 4d 69 6e 20        1     Min 
0b90: 65 6d 62 65 64 64 65 64 20 70 61 79 6c 6f 61 64  embedded payload
0ba0: 20 66 72 61 63 74 69 6f 6e 0a 2a 2a 20 20 20 20   fraction.**    
0bb0: 20 32 33 20 20 20 20 20 20 20 31 20 20 20 20 20   23       1     
0bc0: 4d 69 6e 20 6c 65 61 66 20 70 61 79 6c 6f 61 64  Min leaf payload
0bd0: 20 66 72 61 63 74 69 6f 6e 0a 2a 2a 20 20 20 20   fraction.**    
0be0: 20 32 34 20 20 20 20 20 20 20 34 20 20 20 20 20   24       4     
0bf0: 46 69 6c 65 20 63 68 61 6e 67 65 20 63 6f 75 6e  File change coun
0c00: 74 65 72 0a 2a 2a 20 20 20 20 20 32 38 20 20 20  ter.**     28   
0c10: 20 20 20 20 34 20 20 20 20 20 52 65 73 65 72 76      4     Reserv
0c20: 65 64 20 66 6f 72 20 66 75 74 75 72 65 20 75 73  ed for future us
0c30: 65 0a 2a 2a 20 20 20 20 20 33 32 20 20 20 20 20  e.**     32     
0c40: 20 20 34 20 20 20 20 20 46 69 72 73 74 20 66 72    4     First fr
0c50: 65 65 6c 69 73 74 20 70 61 67 65 0a 2a 2a 20 20  eelist page.**  
0c60: 20 20 20 33 36 20 20 20 20 20 20 20 34 20 20 20     36       4   
0c70: 20 20 4e 75 6d 62 65 72 20 6f 66 20 66 72 65 65    Number of free
0c80: 6c 69 73 74 20 70 61 67 65 73 20 69 6e 20 74 68  list pages in th
0c90: 65 20 66 69 6c 65 0a 2a 2a 20 20 20 20 20 34 30  e file.**     40
0ca0: 20 20 20 20 20 20 36 30 20 20 20 20 20 31 35 20        60     15 
0cb0: 34 2d 62 79 74 65 20 6d 65 74 61 20 76 61 6c 75  4-byte meta valu
0cc0: 65 73 20 70 61 73 73 65 64 20 74 6f 20 68 69 67  es passed to hig
0cd0: 68 65 72 20 6c 61 79 65 72 73 0a 2a 2a 0a 2a 2a  her layers.**.**
0ce0: 20 20 20 20 20 34 30 20 20 20 20 20 20 20 34 20       40       4 
0cf0: 20 20 20 20 53 63 68 65 6d 61 20 63 6f 6f 6b 69      Schema cooki
0d00: 65 0a 2a 2a 20 20 20 20 20 34 34 20 20 20 20 20  e.**     44     
0d10: 20 20 34 20 20 20 20 20 46 69 6c 65 20 66 6f 72    4     File for
0d20: 6d 61 74 20 6f 66 20 73 63 68 65 6d 61 20 6c 61  mat of schema la
0d30: 79 65 72 0a 2a 2a 20 20 20 20 20 34 38 20 20 20  yer.**     48   
0d40: 20 20 20 20 34 20 20 20 20 20 53 69 7a 65 20 6f      4     Size o
0d50: 66 20 70 61 67 65 20 63 61 63 68 65 0a 2a 2a 20  f page cache.** 
0d60: 20 20 20 20 35 32 20 20 20 20 20 20 20 34 20 20      52       4  
0d70: 20 20 20 4c 61 72 67 65 73 74 20 72 6f 6f 74 2d     Largest root-
0d80: 70 61 67 65 20 28 61 75 74 6f 2f 69 6e 63 72 5f  page (auto/incr_
0d90: 76 61 63 75 75 6d 29 0a 2a 2a 20 20 20 20 20 35  vacuum).**     5
0da0: 36 20 20 20 20 20 20 20 34 20 20 20 20 20 31 3d  6       4     1=
0db0: 55 54 46 2d 38 20 32 3d 55 54 46 31 36 6c 65 20  UTF-8 2=UTF16le 
0dc0: 33 3d 55 54 46 31 36 62 65 0a 2a 2a 20 20 20 20  3=UTF16be.**    
0dd0: 20 36 30 20 20 20 20 20 20 20 34 20 20 20 20 20   60       4     
0de0: 55 73 65 72 20 76 65 72 73 69 6f 6e 0a 2a 2a 20  User version.** 
0df0: 20 20 20 20 36 34 20 20 20 20 20 20 20 34 20 20      64       4  
0e00: 20 20 20 49 6e 63 72 65 6d 65 6e 74 61 6c 20 76     Incremental v
0e10: 61 63 75 75 6d 20 6d 6f 64 65 0a 2a 2a 20 20 20  acuum mode.**   
0e20: 20 20 36 38 20 20 20 20 20 20 20 34 20 20 20 20    68       4    
0e30: 20 75 6e 75 73 65 64 0a 2a 2a 20 20 20 20 20 37   unused.**     7
0e40: 32 20 20 20 20 20 20 20 34 20 20 20 20 20 75 6e  2       4     un
0e50: 75 73 65 64 0a 2a 2a 20 20 20 20 20 37 36 20 20  used.**     76  
0e60: 20 20 20 20 20 34 20 20 20 20 20 75 6e 75 73 65       4     unuse
0e70: 64 0a 2a 2a 0a 2a 2a 20 41 6c 6c 20 6f 66 20 74  d.**.** All of t
0e80: 68 65 20 69 6e 74 65 67 65 72 20 76 61 6c 75 65  he integer value
0e90: 73 20 61 72 65 20 62 69 67 2d 65 6e 64 69 61 6e  s are big-endian
0ea0: 20 28 6d 6f 73 74 20 73 69 67 6e 69 66 69 63 61   (most significa
0eb0: 6e 74 20 62 79 74 65 20 66 69 72 73 74 29 2e 0a  nt byte first)..
0ec0: 2a 2a 0a 2a 2a 20 54 68 65 20 66 69 6c 65 20 63  **.** The file c
0ed0: 68 61 6e 67 65 20 63 6f 75 6e 74 65 72 20 69 73  hange counter is
0ee0: 20 69 6e 63 72 65 6d 65 6e 74 65 64 20 77 68 65   incremented whe
0ef0: 6e 20 74 68 65 20 64 61 74 61 62 61 73 65 20 69  n the database i
0f00: 73 20 63 68 61 6e 67 65 64 0a 2a 2a 20 54 68 69  s changed.** Thi
0f10: 73 20 63 6f 75 6e 74 65 72 20 61 6c 6c 6f 77 73  s counter allows
0f20: 20 6f 74 68 65 72 20 70 72 6f 63 65 73 73 65 73   other processes
0f30: 20 74 6f 20 6b 6e 6f 77 20 77 68 65 6e 20 74 68   to know when th
0f40: 65 20 66 69 6c 65 20 68 61 73 20 63 68 61 6e 67  e file has chang
0f50: 65 64 0a 2a 2a 20 61 6e 64 20 74 68 75 73 20 77  ed.** and thus w
0f60: 68 65 6e 20 74 68 65 79 20 6e 65 65 64 20 74 6f  hen they need to
0f70: 20 66 6c 75 73 68 20 74 68 65 69 72 20 63 61 63   flush their cac
0f80: 68 65 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 6d 61  he..**.** The ma
0f90: 78 20 65 6d 62 65 64 64 65 64 20 70 61 79 6c 6f  x embedded paylo
0fa0: 61 64 20 66 72 61 63 74 69 6f 6e 20 69 73 20 74  ad fraction is t
0fb0: 68 65 20 61 6d 6f 75 6e 74 20 6f 66 20 74 68 65  he amount of the
0fc0: 20 74 6f 74 61 6c 20 75 73 61 62 6c 65 0a 2a 2a   total usable.**
0fd0: 20 73 70 61 63 65 20 69 6e 20 61 20 70 61 67 65   space in a page
0fe0: 20 74 68 61 74 20 63 61 6e 20 62 65 20 63 6f 6e   that can be con
0ff0: 73 75 6d 65 64 20 62 79 20 61 20 73 69 6e 67 6c  sumed by a singl
1000: 65 20 63 65 6c 6c 20 66 6f 72 20 73 74 61 6e 64  e cell for stand
1010: 61 72 64 0a 2a 2a 20 42 2d 74 72 65 65 20 28 6e  ard.** B-tree (n
1020: 6f 6e 2d 4c 45 41 46 44 41 54 41 29 20 74 61 62  on-LEAFDATA) tab
1030: 6c 65 73 2e 20 20 41 20 76 61 6c 75 65 20 6f 66  les.  A value of
1040: 20 32 35 35 20 6d 65 61 6e 73 20 31 30 30 25 2e   255 means 100%.
1050: 20 20 54 68 65 20 64 65 66 61 75 6c 74 0a 2a 2a    The default.**
1060: 20 69 73 20 74 6f 20 6c 69 6d 69 74 20 74 68 65   is to limit the
1070: 20 6d 61 78 69 6d 75 6d 20 63 65 6c 6c 20 73 69   maximum cell si
1080: 7a 65 20 73 6f 20 74 68 61 74 20 61 74 20 6c 65  ze so that at le
1090: 61 73 74 20 34 20 63 65 6c 6c 73 20 77 69 6c 6c  ast 4 cells will
10a0: 20 66 69 74 0a 2a 2a 20 6f 6e 20 6f 6e 65 20 70   fit.** on one p
10b0: 61 67 65 2e 20 20 54 68 75 73 20 74 68 65 20 64  age.  Thus the d
10c0: 65 66 61 75 6c 74 20 6d 61 78 20 65 6d 62 65 64  efault max embed
10d0: 64 65 64 20 70 61 79 6c 6f 61 64 20 66 72 61 63  ded payload frac
10e0: 74 69 6f 6e 20 69 73 20 36 34 2e 0a 2a 2a 0a 2a  tion is 64..**.*
10f0: 2a 20 49 66 20 74 68 65 20 70 61 79 6c 6f 61 64  * If the payload
1100: 20 66 6f 72 20 61 20 63 65 6c 6c 20 69 73 20 6c   for a cell is l
1110: 61 72 67 65 72 20 74 68 61 6e 20 74 68 65 20 6d  arger than the m
1120: 61 78 20 70 61 79 6c 6f 61 64 2c 20 74 68 65 6e  ax payload, then
1130: 20 65 78 74 72 61 0a 2a 2a 20 70 61 79 6c 6f 61   extra.** payloa
1140: 64 20 69 73 20 73 70 69 6c 6c 65 64 20 74 6f 20  d is spilled to 
1150: 6f 76 65 72 66 6c 6f 77 20 70 61 67 65 73 2e 20  overflow pages. 
1160: 20 4f 6e 63 65 20 61 6e 20 6f 76 65 72 66 6c 6f   Once an overflo
1170: 77 20 70 61 67 65 20 69 73 20 61 6c 6c 6f 63 61  w page is alloca
1180: 74 65 64 2c 0a 2a 2a 20 61 73 20 6d 61 6e 79 20  ted,.** as many 
1190: 62 79 74 65 73 20 61 73 20 70 6f 73 73 69 62 6c  bytes as possibl
11a0: 65 20 61 72 65 20 6d 6f 76 65 64 20 69 6e 74 6f  e are moved into
11b0: 20 74 68 65 20 6f 76 65 72 66 6c 6f 77 20 70 61   the overflow pa
11c0: 67 65 73 20 77 69 74 68 6f 75 74 20 6c 65 74 74  ges without lett
11d0: 69 6e 67 0a 2a 2a 20 74 68 65 20 63 65 6c 6c 20  ing.** the cell 
11e0: 73 69 7a 65 20 64 72 6f 70 20 62 65 6c 6f 77 20  size drop below 
11f0: 74 68 65 20 6d 69 6e 20 65 6d 62 65 64 64 65 64  the min embedded
1200: 20 70 61 79 6c 6f 61 64 20 66 72 61 63 74 69 6f   payload fractio
1210: 6e 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 6d 69 6e  n..**.** The min
1220: 20 6c 65 61 66 20 70 61 79 6c 6f 61 64 20 66 72   leaf payload fr
1230: 61 63 74 69 6f 6e 20 69 73 20 6c 69 6b 65 20 74  action is like t
1240: 68 65 20 6d 69 6e 20 65 6d 62 65 64 64 65 64 20  he min embedded 
1250: 70 61 79 6c 6f 61 64 20 66 72 61 63 74 69 6f 6e  payload fraction
1260: 0a 2a 2a 20 65 78 63 65 70 74 20 74 68 61 74 20  .** except that 
1270: 69 74 20 61 70 70 6c 69 65 73 20 74 6f 20 6c 65  it applies to le
1280: 61 66 20 6e 6f 64 65 73 20 69 6e 20 61 20 4c 45  af nodes in a LE
1290: 41 46 44 41 54 41 20 74 72 65 65 2e 20 20 54 68  AFDATA tree.  Th
12a0: 65 20 6d 61 78 69 6d 75 6d 0a 2a 2a 20 70 61 79  e maximum.** pay
12b0: 6c 6f 61 64 20 66 72 61 63 74 69 6f 6e 20 66 6f  load fraction fo
12c0: 72 20 61 20 4c 45 41 46 44 41 54 41 20 74 72 65  r a LEAFDATA tre
12d0: 65 20 69 73 20 61 6c 77 61 79 73 20 31 30 30 25  e is always 100%
12e0: 20 28 6f 72 20 32 35 35 29 20 61 6e 64 20 69 74   (or 255) and it
12f0: 0a 2a 2a 20 6e 6f 74 20 73 70 65 63 69 66 69 65  .** not specifie
1300: 64 20 69 6e 20 74 68 65 20 68 65 61 64 65 72 2e  d in the header.
1310: 0a 2a 2a 0a 2a 2a 20 45 61 63 68 20 62 74 72 65  .**.** Each btre
1320: 65 20 70 61 67 65 73 20 69 73 20 64 69 76 69 64  e pages is divid
1330: 65 64 20 69 6e 74 6f 20 74 68 72 65 65 20 73 65  ed into three se
1340: 63 74 69 6f 6e 73 3a 20 20 54 68 65 20 68 65 61  ctions:  The hea
1350: 64 65 72 2c 20 74 68 65 0a 2a 2a 20 63 65 6c 6c  der, the.** cell
1360: 20 70 6f 69 6e 74 65 72 20 61 72 72 61 79 2c 20   pointer array, 
1370: 61 6e 64 20 74 68 65 20 63 65 6c 6c 20 63 6f 6e  and the cell con
1380: 74 65 6e 74 20 61 72 65 61 2e 20 20 50 61 67 65  tent area.  Page
1390: 20 31 20 61 6c 73 6f 20 68 61 73 20 61 20 31 30   1 also has a 10
13a0: 30 2d 62 79 74 65 0a 2a 2a 20 66 69 6c 65 20 68  0-byte.** file h
13b0: 65 61 64 65 72 20 74 68 61 74 20 6f 63 63 75 72  eader that occur
13c0: 73 20 62 65 66 6f 72 65 20 74 68 65 20 70 61 67  s before the pag
13d0: 65 20 68 65 61 64 65 72 2e 0a 2a 2a 0a 2a 2a 20  e header..**.** 
13e0: 20 20 20 20 20 7c 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d       |----------
13f0: 2d 2d 2d 2d 2d 2d 7c 0a 2a 2a 20 20 20 20 20 20  ------|.**      
1400: 7c 20 66 69 6c 65 20 68 65 61 64 65 72 20 20 20  | file header   
1410: 20 7c 20 20 20 31 30 30 20 62 79 74 65 73 2e 20   |   100 bytes. 
1420: 20 50 61 67 65 20 31 20 6f 6e 6c 79 2e 0a 2a 2a   Page 1 only..**
1430: 20 20 20 20 20 20 7c 2d 2d 2d 2d 2d 2d 2d 2d 2d        |---------
1440: 2d 2d 2d 2d 2d 2d 2d 7c 0a 2a 2a 20 20 20 20 20  -------|.**     
1450: 20 7c 20 70 61 67 65 20 68 65 61 64 65 72 20 20   | page header  
1460: 20 20 7c 20 20 20 38 20 62 79 74 65 73 20 66 6f    |   8 bytes fo
1470: 72 20 6c 65 61 76 65 73 2e 20 20 31 32 20 62 79  r leaves.  12 by
1480: 74 65 73 20 66 6f 72 20 69 6e 74 65 72 69 6f 72  tes for interior
1490: 20 6e 6f 64 65 73 0a 2a 2a 20 20 20 20 20 20 7c   nodes.**      |
14a0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
14b0: 7c 0a 2a 2a 20 20 20 20 20 20 7c 20 63 65 6c 6c  |.**      | cell
14c0: 20 70 6f 69 6e 74 65 72 20 20 20 7c 20 20 20 7c   pointer   |   |
14d0: 20 20 32 20 62 79 74 65 73 20 70 65 72 20 63 65    2 bytes per ce
14e0: 6c 6c 2e 20 20 53 6f 72 74 65 64 20 6f 72 64 65  ll.  Sorted orde
14f0: 72 2e 0a 2a 2a 20 20 20 20 20 20 7c 20 61 72 72  r..**      | arr
1500: 61 79 20 20 20 20 20 20 20 20 20 20 7c 20 20 20  ay          |   
1510: 7c 20 20 47 72 6f 77 73 20 64 6f 77 6e 77 61 72  |  Grows downwar
1520: 64 0a 2a 2a 20 20 20 20 20 20 7c 20 20 20 20 20  d.**      |     
1530: 20 20 20 20 20 20 20 20 20 20 20 7c 20 20 20 76             |   v
1540: 0a 2a 2a 20 20 20 20 20 20 7c 2d 2d 2d 2d 2d 2d  .**      |------
1550: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 7c 0a 2a 2a 20 20  ----------|.**  
1560: 20 20 20 20 7c 20 75 6e 61 6c 6c 6f 63 61 74 65      | unallocate
1570: 64 20 20 20 20 7c 0a 2a 2a 20 20 20 20 20 20 7c  d    |.**      |
1580: 20 73 70 61 63 65 20 20 20 20 20 20 20 20 20 20   space          
1590: 7c 0a 2a 2a 20 20 20 20 20 20 7c 2d 2d 2d 2d 2d  |.**      |-----
15a0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 7c 20 20 20 5e  -----------|   ^
15b0: 20 20 47 72 6f 77 73 20 75 70 77 61 72 64 73 0a    Grows upwards.
15c0: 2a 2a 20 20 20 20 20 20 7c 20 63 65 6c 6c 20 63  **      | cell c
15d0: 6f 6e 74 65 6e 74 20 20 20 7c 20 20 20 7c 20 20  ontent   |   |  
15e0: 41 72 62 69 74 72 61 72 79 20 6f 72 64 65 72 20  Arbitrary order 
15f0: 69 6e 74 65 72 73 70 65 72 73 65 64 20 77 69 74  interspersed wit
1600: 68 20 66 72 65 65 62 6c 6f 63 6b 73 2e 0a 2a 2a  h freeblocks..**
1610: 20 20 20 20 20 20 7c 20 61 72 65 61 20 20 20 20        | area    
1620: 20 20 20 20 20 20 20 7c 20 20 20 7c 20 20 61 6e         |   |  an
1630: 64 20 66 72 65 65 20 73 70 61 63 65 20 66 72 61  d free space fra
1640: 67 6d 65 6e 74 73 2e 0a 2a 2a 20 20 20 20 20 20  gments..**      
1650: 7c 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  |---------------
1660: 2d 7c 0a 2a 2a 0a 2a 2a 20 54 68 65 20 70 61 67  -|.**.** The pag
1670: 65 20 68 65 61 64 65 72 73 20 6c 6f 6f 6b 73 20  e headers looks 
1680: 6c 69 6b 65 20 74 68 69 73 3a 0a 2a 2a 0a 2a 2a  like this:.**.**
1690: 20 20 20 4f 46 46 53 45 54 20 20 20 53 49 5a 45     OFFSET   SIZE
16a0: 20 20 20 20 20 44 45 53 43 52 49 50 54 49 4f 4e       DESCRIPTION
16b0: 0a 2a 2a 20 20 20 20 20 20 30 20 20 20 20 20 20  .**      0      
16c0: 20 31 20 20 20 20 20 20 46 6c 61 67 73 2e 20 31   1      Flags. 1
16d0: 3a 20 69 6e 74 6b 65 79 2c 20 32 3a 20 7a 65 72  : intkey, 2: zer
16e0: 6f 64 61 74 61 2c 20 34 3a 20 6c 65 61 66 64 61  odata, 4: leafda
16f0: 74 61 2c 20 38 3a 20 6c 65 61 66 0a 2a 2a 20 20  ta, 8: leaf.**  
1700: 20 20 20 20 31 20 20 20 20 20 20 20 32 20 20 20      1       2   
1710: 20 20 20 62 79 74 65 20 6f 66 66 73 65 74 20 74     byte offset t
1720: 6f 20 74 68 65 20 66 69 72 73 74 20 66 72 65 65  o the first free
1730: 62 6c 6f 63 6b 0a 2a 2a 20 20 20 20 20 20 33 20  block.**      3 
1740: 20 20 20 20 20 20 32 20 20 20 20 20 20 6e 75 6d        2      num
1750: 62 65 72 20 6f 66 20 63 65 6c 6c 73 20 6f 6e 20  ber of cells on 
1760: 74 68 69 73 20 70 61 67 65 0a 2a 2a 20 20 20 20  this page.**    
1770: 20 20 35 20 20 20 20 20 20 20 32 20 20 20 20 20    5       2     
1780: 20 66 69 72 73 74 20 62 79 74 65 20 6f 66 20 74   first byte of t
1790: 68 65 20 63 65 6c 6c 20 63 6f 6e 74 65 6e 74 20  he cell content 
17a0: 61 72 65 61 0a 2a 2a 20 20 20 20 20 20 37 20 20  area.**      7  
17b0: 20 20 20 20 20 31 20 20 20 20 20 20 6e 75 6d 62       1      numb
17c0: 65 72 20 6f 66 20 66 72 61 67 6d 65 6e 74 65 64  er of fragmented
17d0: 20 66 72 65 65 20 62 79 74 65 73 0a 2a 2a 20 20   free bytes.**  
17e0: 20 20 20 20 38 20 20 20 20 20 20 20 34 20 20 20      8       4   
17f0: 20 20 20 52 69 67 68 74 20 63 68 69 6c 64 20 28     Right child (
1800: 74 68 65 20 50 74 72 28 4e 29 20 76 61 6c 75 65  the Ptr(N) value
1810: 29 2e 20 20 4f 6d 69 74 74 65 64 20 6f 6e 20 6c  ).  Omitted on l
1820: 65 61 76 65 73 2e 0a 2a 2a 0a 2a 2a 20 54 68 65  eaves..**.** The
1830: 20 66 6c 61 67 73 20 64 65 66 69 6e 65 20 74 68   flags define th
1840: 65 20 66 6f 72 6d 61 74 20 6f 66 20 74 68 69 73  e format of this
1850: 20 62 74 72 65 65 20 70 61 67 65 2e 20 20 54 68   btree page.  Th
1860: 65 20 6c 65 61 66 20 66 6c 61 67 20 6d 65 61 6e  e leaf flag mean
1870: 73 20 74 68 61 74 0a 2a 2a 20 74 68 69 73 20 70  s that.** this p
1880: 61 67 65 20 68 61 73 20 6e 6f 20 63 68 69 6c 64  age has no child
1890: 72 65 6e 2e 20 20 54 68 65 20 7a 65 72 6f 64 61  ren.  The zeroda
18a0: 74 61 20 66 6c 61 67 20 6d 65 61 6e 73 20 74 68  ta flag means th
18b0: 61 74 20 74 68 69 73 20 70 61 67 65 20 63 61 72  at this page car
18c0: 72 69 65 73 0a 2a 2a 20 6f 6e 6c 79 20 6b 65 79  ries.** only key
18d0: 73 20 61 6e 64 20 6e 6f 20 64 61 74 61 2e 20 20  s and no data.  
18e0: 54 68 65 20 69 6e 74 6b 65 79 20 66 6c 61 67 20  The intkey flag 
18f0: 6d 65 61 6e 73 20 74 68 61 74 20 74 68 65 20 6b  means that the k
1900: 65 79 20 69 73 20 61 20 69 6e 74 65 67 65 72 0a  ey is a integer.
1910: 2a 2a 20 77 68 69 63 68 20 69 73 20 73 74 6f 72  ** which is stor
1920: 65 64 20 69 6e 20 74 68 65 20 6b 65 79 20 73 69  ed in the key si
1930: 7a 65 20 65 6e 74 72 79 20 6f 66 20 74 68 65 20  ze entry of the 
1940: 63 65 6c 6c 20 68 65 61 64 65 72 20 72 61 74 68  cell header rath
1950: 65 72 20 74 68 61 6e 20 69 6e 0a 2a 2a 20 74 68  er than in.** th
1960: 65 20 70 61 79 6c 6f 61 64 20 61 72 65 61 2e 0a  e payload area..
1970: 2a 2a 0a 2a 2a 20 54 68 65 20 63 65 6c 6c 20 70  **.** The cell p
1980: 6f 69 6e 74 65 72 20 61 72 72 61 79 20 62 65 67  ointer array beg
1990: 69 6e 73 20 6f 6e 20 74 68 65 20 66 69 72 73 74  ins on the first
19a0: 20 62 79 74 65 20 61 66 74 65 72 20 74 68 65 20   byte after the 
19b0: 70 61 67 65 20 68 65 61 64 65 72 2e 0a 2a 2a 20  page header..** 
19c0: 54 68 65 20 63 65 6c 6c 20 70 6f 69 6e 74 65 72  The cell pointer
19d0: 20 61 72 72 61 79 20 63 6f 6e 74 61 69 6e 73 20   array contains 
19e0: 7a 65 72 6f 20 6f 72 20 6d 6f 72 65 20 32 2d 62  zero or more 2-b
19f0: 79 74 65 20 6e 75 6d 62 65 72 73 20 77 68 69 63  yte numbers whic
1a00: 68 20 61 72 65 0a 2a 2a 20 6f 66 66 73 65 74 73  h are.** offsets
1a10: 20 66 72 6f 6d 20 74 68 65 20 62 65 67 69 6e 6e   from the beginn
1a20: 69 6e 67 20 6f 66 20 74 68 65 20 70 61 67 65 20  ing of the page 
1a30: 74 6f 20 74 68 65 20 63 65 6c 6c 20 63 6f 6e 74  to the cell cont
1a40: 65 6e 74 20 69 6e 20 74 68 65 20 63 65 6c 6c 0a  ent in the cell.
1a50: 2a 2a 20 63 6f 6e 74 65 6e 74 20 61 72 65 61 2e  ** content area.
1a60: 20 20 54 68 65 20 63 65 6c 6c 20 70 6f 69 6e 74    The cell point
1a70: 65 72 73 20 6f 63 63 75 72 20 69 6e 20 73 6f 72  ers occur in sor
1a80: 74 65 64 20 6f 72 64 65 72 2e 20 20 54 68 65 20  ted order.  The 
1a90: 73 79 73 74 65 6d 20 73 74 72 69 76 65 73 0a 2a  system strives.*
1aa0: 2a 20 74 6f 20 6b 65 65 70 20 66 72 65 65 20 73  * to keep free s
1ab0: 70 61 63 65 20 61 66 74 65 72 20 74 68 65 20 6c  pace after the l
1ac0: 61 73 74 20 63 65 6c 6c 20 70 6f 69 6e 74 65 72  ast cell pointer
1ad0: 20 73 6f 20 74 68 61 74 20 6e 65 77 20 63 65 6c   so that new cel
1ae0: 6c 73 20 63 61 6e 0a 2a 2a 20 62 65 20 65 61 73  ls can.** be eas
1af0: 69 6c 79 20 61 64 64 65 64 20 77 69 74 68 6f 75  ily added withou
1b00: 74 20 68 61 76 69 6e 67 20 74 6f 20 64 65 66 72  t having to defr
1b10: 61 67 6d 65 6e 74 20 74 68 65 20 70 61 67 65 2e  agment the page.
1b20: 0a 2a 2a 0a 2a 2a 20 43 65 6c 6c 20 63 6f 6e 74  .**.** Cell cont
1b30: 65 6e 74 20 69 73 20 73 74 6f 72 65 64 20 61 74  ent is stored at
1b40: 20 74 68 65 20 76 65 72 79 20 65 6e 64 20 6f 66   the very end of
1b50: 20 74 68 65 20 70 61 67 65 20 61 6e 64 20 67 72   the page and gr
1b60: 6f 77 73 20 74 6f 77 61 72 64 20 74 68 65 0a 2a  ows toward the.*
1b70: 2a 20 62 65 67 69 6e 6e 69 6e 67 20 6f 66 20 74  * beginning of t
1b80: 68 65 20 70 61 67 65 2e 0a 2a 2a 0a 2a 2a 20 55  he page..**.** U
1b90: 6e 75 73 65 64 20 73 70 61 63 65 20 77 69 74 68  nused space with
1ba0: 69 6e 20 74 68 65 20 63 65 6c 6c 20 63 6f 6e 74  in the cell cont
1bb0: 65 6e 74 20 61 72 65 61 20 69 73 20 63 6f 6c 6c  ent area is coll
1bc0: 65 63 74 65 64 20 69 6e 74 6f 20 61 20 6c 69 6e  ected into a lin
1bd0: 6b 65 64 20 6c 69 73 74 20 6f 66 0a 2a 2a 20 66  ked list of.** f
1be0: 72 65 65 62 6c 6f 63 6b 73 2e 20 20 45 61 63 68  reeblocks.  Each
1bf0: 20 66 72 65 65 62 6c 6f 63 6b 20 69 73 20 61 74   freeblock is at
1c00: 20 6c 65 61 73 74 20 34 20 62 79 74 65 73 20 69   least 4 bytes i
1c10: 6e 20 73 69 7a 65 2e 20 20 54 68 65 20 62 79 74  n size.  The byt
1c20: 65 20 6f 66 66 73 65 74 0a 2a 2a 20 74 6f 20 74  e offset.** to t
1c30: 68 65 20 66 69 72 73 74 20 66 72 65 65 62 6c 6f  he first freeblo
1c40: 63 6b 20 69 73 20 67 69 76 65 6e 20 69 6e 20 74  ck is given in t
1c50: 68 65 20 68 65 61 64 65 72 2e 20 20 46 72 65 65  he header.  Free
1c60: 62 6c 6f 63 6b 73 20 6f 63 63 75 72 20 69 6e 0a  blocks occur in.
1c70: 2a 2a 20 69 6e 63 72 65 61 73 69 6e 67 20 6f 72  ** increasing or
1c80: 64 65 72 2e 20 20 42 65 63 61 75 73 65 20 61 20  der.  Because a 
1c90: 66 72 65 65 62 6c 6f 63 6b 20 6d 75 73 74 20 62  freeblock must b
1ca0: 65 20 61 74 20 6c 65 61 73 74 20 34 20 62 79 74  e at least 4 byt
1cb0: 65 73 20 69 6e 20 73 69 7a 65 2c 0a 2a 2a 20 61  es in size,.** a
1cc0: 6e 79 20 67 72 6f 75 70 20 6f 66 20 33 20 6f 72  ny group of 3 or
1cd0: 20 66 65 77 65 72 20 75 6e 75 73 65 64 20 62 79   fewer unused by
1ce0: 74 65 73 20 69 6e 20 74 68 65 20 63 65 6c 6c 20  tes in the cell 
1cf0: 63 6f 6e 74 65 6e 74 20 61 72 65 61 20 63 61 6e  content area can
1d00: 6e 6f 74 0a 2a 2a 20 65 78 69 73 74 20 6f 6e 20  not.** exist on 
1d10: 74 68 65 20 66 72 65 65 62 6c 6f 63 6b 20 63 68  the freeblock ch
1d20: 61 69 6e 2e 20 20 41 20 67 72 6f 75 70 20 6f 66  ain.  A group of
1d30: 20 33 20 6f 72 20 66 65 77 65 72 20 66 72 65 65   3 or fewer free
1d40: 20 62 79 74 65 73 20 69 73 20 63 61 6c 6c 65 64   bytes is called
1d50: 0a 2a 2a 20 61 20 66 72 61 67 6d 65 6e 74 2e 20  .** a fragment. 
1d60: 20 54 68 65 20 74 6f 74 61 6c 20 6e 75 6d 62 65   The total numbe
1d70: 72 20 6f 66 20 62 79 74 65 73 20 69 6e 20 61 6c  r of bytes in al
1d80: 6c 20 66 72 61 67 6d 65 6e 74 73 20 69 73 20 72  l fragments is r
1d90: 65 63 6f 72 64 65 64 2e 0a 2a 2a 20 69 6e 20 74  ecorded..** in t
1da0: 68 65 20 70 61 67 65 20 68 65 61 64 65 72 20 61  he page header a
1db0: 74 20 6f 66 66 73 65 74 20 37 2e 0a 2a 2a 0a 2a  t offset 7..**.*
1dc0: 2a 20 20 20 20 53 49 5a 45 20 20 20 20 44 45 53  *    SIZE    DES
1dd0: 43 52 49 50 54 49 4f 4e 0a 2a 2a 20 20 20 20 20  CRIPTION.**     
1de0: 20 32 20 20 20 20 20 42 79 74 65 20 6f 66 66 73   2     Byte offs
1df0: 65 74 20 6f 66 20 74 68 65 20 6e 65 78 74 20 66  et of the next f
1e00: 72 65 65 62 6c 6f 63 6b 0a 2a 2a 20 20 20 20 20  reeblock.**     
1e10: 20 32 20 20 20 20 20 42 79 74 65 73 20 69 6e 20   2     Bytes in 
1e20: 74 68 69 73 20 66 72 65 65 62 6c 6f 63 6b 0a 2a  this freeblock.*
1e30: 2a 0a 2a 2a 20 43 65 6c 6c 73 20 61 72 65 20 6f  *.** Cells are o
1e40: 66 20 76 61 72 69 61 62 6c 65 20 6c 65 6e 67 74  f variable lengt
1e50: 68 2e 20 20 43 65 6c 6c 73 20 61 72 65 20 73 74  h.  Cells are st
1e60: 6f 72 65 64 20 69 6e 20 74 68 65 20 63 65 6c 6c  ored in the cell
1e70: 20 63 6f 6e 74 65 6e 74 20 61 72 65 61 20 61 74   content area at
1e80: 0a 2a 2a 20 74 68 65 20 65 6e 64 20 6f 66 20 74  .** the end of t
1e90: 68 65 20 70 61 67 65 2e 20 20 50 6f 69 6e 74 65  he page.  Pointe
1ea0: 72 73 20 74 6f 20 74 68 65 20 63 65 6c 6c 73 20  rs to the cells 
1eb0: 61 72 65 20 69 6e 20 74 68 65 20 63 65 6c 6c 20  are in the cell 
1ec0: 70 6f 69 6e 74 65 72 20 61 72 72 61 79 0a 2a 2a  pointer array.**
1ed0: 20 74 68 61 74 20 69 6d 6d 65 64 69 61 74 65 6c   that immediatel
1ee0: 79 20 66 6f 6c 6c 6f 77 73 20 74 68 65 20 70 61  y follows the pa
1ef0: 67 65 20 68 65 61 64 65 72 2e 20 20 43 65 6c 6c  ge header.  Cell
1f00: 73 20 69 73 20 6e 6f 74 20 6e 65 63 65 73 73 61  s is not necessa
1f10: 72 69 6c 79 0a 2a 2a 20 63 6f 6e 74 69 67 75 6f  rily.** contiguo
1f20: 75 73 20 6f 72 20 69 6e 20 6f 72 64 65 72 2c 20  us or in order, 
1f30: 62 75 74 20 63 65 6c 6c 20 70 6f 69 6e 74 65 72  but cell pointer
1f40: 73 20 61 72 65 20 63 6f 6e 74 69 67 75 6f 75 73  s are contiguous
1f50: 20 61 6e 64 20 69 6e 20 6f 72 64 65 72 2e 0a 2a   and in order..*
1f60: 2a 0a 2a 2a 20 43 65 6c 6c 20 63 6f 6e 74 65 6e  *.** Cell conten
1f70: 74 20 6d 61 6b 65 73 20 75 73 65 20 6f 66 20 76  t makes use of v
1f80: 61 72 69 61 62 6c 65 20 6c 65 6e 67 74 68 20 69  ariable length i
1f90: 6e 74 65 67 65 72 73 2e 20 20 41 20 76 61 72 69  ntegers.  A vari
1fa0: 61 62 6c 65 0a 2a 2a 20 6c 65 6e 67 74 68 20 69  able.** length i
1fb0: 6e 74 65 67 65 72 20 69 73 20 31 20 74 6f 20 39  nteger is 1 to 9
1fc0: 20 62 79 74 65 73 20 77 68 65 72 65 20 74 68 65   bytes where the
1fd0: 20 6c 6f 77 65 72 20 37 20 62 69 74 73 20 6f 66   lower 7 bits of
1fe0: 20 65 61 63 68 20 0a 2a 2a 20 62 79 74 65 20 61   each .** byte a
1ff0: 72 65 20 75 73 65 64 2e 20 20 54 68 65 20 69 6e  re used.  The in
2000: 74 65 67 65 72 20 63 6f 6e 73 69 73 74 73 20 6f  teger consists o
2010: 66 20 61 6c 6c 20 62 79 74 65 73 20 74 68 61 74  f all bytes that
2020: 20 68 61 76 65 20 62 69 74 20 38 20 73 65 74 20   have bit 8 set 
2030: 61 6e 64 0a 2a 2a 20 74 68 65 20 66 69 72 73 74  and.** the first
2040: 20 62 79 74 65 20 77 69 74 68 20 62 69 74 20 38   byte with bit 8
2050: 20 63 6c 65 61 72 2e 20 20 54 68 65 20 6d 6f 73   clear.  The mos
2060: 74 20 73 69 67 6e 69 66 69 63 61 6e 74 20 62 79  t significant by
2070: 74 65 20 6f 66 20 74 68 65 20 69 6e 74 65 67 65  te of the intege
2080: 72 0a 2a 2a 20 61 70 70 65 61 72 73 20 66 69 72  r.** appears fir
2090: 73 74 2e 20 20 41 20 76 61 72 69 61 62 6c 65 2d  st.  A variable-
20a0: 6c 65 6e 67 74 68 20 69 6e 74 65 67 65 72 20 6d  length integer m
20b0: 61 79 20 6e 6f 74 20 62 65 20 6d 6f 72 65 20 74  ay not be more t
20c0: 68 61 6e 20 39 20 62 79 74 65 73 20 6c 6f 6e 67  han 9 bytes long
20d0: 2e 0a 2a 2a 20 41 73 20 61 20 73 70 65 63 69 61  ..** As a specia
20e0: 6c 20 63 61 73 65 2c 20 61 6c 6c 20 38 20 62 79  l case, all 8 by
20f0: 74 65 73 20 6f 66 20 74 68 65 20 39 74 68 20 62  tes of the 9th b
2100: 79 74 65 20 61 72 65 20 75 73 65 64 20 61 73 20  yte are used as 
2110: 64 61 74 61 2e 20 20 54 68 69 73 0a 2a 2a 20 61  data.  This.** a
2120: 6c 6c 6f 77 73 20 61 20 36 34 2d 62 69 74 20 69  llows a 64-bit i
2130: 6e 74 65 67 65 72 20 74 6f 20 62 65 20 65 6e 63  nteger to be enc
2140: 6f 64 65 64 20 69 6e 20 39 20 62 79 74 65 73 2e  oded in 9 bytes.
2150: 0a 2a 2a 0a 2a 2a 20 20 20 20 30 78 30 30 20 20  .**.**    0x00  
2160: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2170: 20 20 20 20 62 65 63 6f 6d 65 73 20 20 30 78 30      becomes  0x0
2180: 30 30 30 30 30 30 30 0a 2a 2a 20 20 20 20 30 78  0000000.**    0x
2190: 37 66 20 20 20 20 20 20 20 20 20 20 20 20 20 20  7f              
21a0: 20 20 20 20 20 20 20 20 62 65 63 6f 6d 65 73 20          becomes 
21b0: 20 30 78 30 30 30 30 30 30 37 66 0a 2a 2a 20 20   0x0000007f.**  
21c0: 20 20 30 78 38 31 20 30 78 30 30 20 20 20 20 20    0x81 0x00     
21d0: 20 20 20 20 20 20 20 20 20 20 20 20 62 65 63 6f              beco
21e0: 6d 65 73 20 20 30 78 30 30 30 30 30 30 38 30 0a  mes  0x00000080.
21f0: 2a 2a 20 20 20 20 30 78 38 32 20 30 78 30 30 20  **    0x82 0x00 
2200: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2210: 62 65 63 6f 6d 65 73 20 20 30 78 30 30 30 30 30  becomes  0x00000
2220: 31 30 30 0a 2a 2a 20 20 20 20 30 78 38 30 20 30  100.**    0x80 0
2230: 78 37 66 20 20 20 20 20 20 20 20 20 20 20 20 20  x7f             
2240: 20 20 20 20 62 65 63 6f 6d 65 73 20 20 30 78 30      becomes  0x0
2250: 30 30 30 30 30 37 66 0a 2a 2a 20 20 20 20 30 78  000007f.**    0x
2260: 38 61 20 30 78 39 31 20 30 78 64 31 20 30 78 61  8a 0x91 0xd1 0xa
2270: 63 20 30 78 37 38 20 20 62 65 63 6f 6d 65 73 20  c 0x78  becomes 
2280: 20 30 78 31 32 33 34 35 36 37 38 0a 2a 2a 20 20   0x12345678.**  
2290: 20 20 30 78 38 31 20 30 78 38 31 20 30 78 38 31    0x81 0x81 0x81
22a0: 20 30 78 38 31 20 30 78 30 31 20 20 62 65 63 6f   0x81 0x01  beco
22b0: 6d 65 73 20 20 30 78 31 30 32 30 34 30 38 31 0a  mes  0x10204081.
22c0: 2a 2a 0a 2a 2a 20 56 61 72 69 61 62 6c 65 20 6c  **.** Variable l
22d0: 65 6e 67 74 68 20 69 6e 74 65 67 65 72 73 20 61  ength integers a
22e0: 72 65 20 75 73 65 64 20 66 6f 72 20 72 6f 77 69  re used for rowi
22f0: 64 73 20 61 6e 64 20 74 6f 20 68 6f 6c 64 20 74  ds and to hold t
2300: 68 65 20 6e 75 6d 62 65 72 20 6f 66 0a 2a 2a 20  he number of.** 
2310: 62 79 74 65 73 20 6f 66 20 6b 65 79 20 61 6e 64  bytes of key and
2320: 20 64 61 74 61 20 69 6e 20 61 20 62 74 72 65 65   data in a btree
2330: 20 63 65 6c 6c 2e 0a 2a 2a 0a 2a 2a 20 54 68 65   cell..**.** The
2340: 20 63 6f 6e 74 65 6e 74 20 6f 66 20 61 20 63 65   content of a ce
2350: 6c 6c 20 6c 6f 6f 6b 73 20 6c 69 6b 65 20 74 68  ll looks like th
2360: 69 73 3a 0a 2a 2a 0a 2a 2a 20 20 20 20 53 49 5a  is:.**.**    SIZ
2370: 45 20 20 20 20 44 45 53 43 52 49 50 54 49 4f 4e  E    DESCRIPTION
2380: 0a 2a 2a 20 20 20 20 20 20 34 20 20 20 20 20 50  .**      4     P
2390: 61 67 65 20 6e 75 6d 62 65 72 20 6f 66 20 74 68  age number of th
23a0: 65 20 6c 65 66 74 20 63 68 69 6c 64 2e 20 4f 6d  e left child. Om
23b0: 69 74 74 65 64 20 69 66 20 6c 65 61 66 20 66 6c  itted if leaf fl
23c0: 61 67 20 69 73 20 73 65 74 2e 0a 2a 2a 20 20 20  ag is set..**   
23d0: 20 20 76 61 72 20 20 20 20 4e 75 6d 62 65 72 20    var    Number 
23e0: 6f 66 20 62 79 74 65 73 20 6f 66 20 64 61 74 61  of bytes of data
23f0: 2e 20 4f 6d 69 74 74 65 64 20 69 66 20 74 68 65  . Omitted if the
2400: 20 7a 65 72 6f 64 61 74 61 20 66 6c 61 67 20 69   zerodata flag i
2410: 73 20 73 65 74 2e 0a 2a 2a 20 20 20 20 20 76 61  s set..**     va
2420: 72 20 20 20 20 4e 75 6d 62 65 72 20 6f 66 20 62  r    Number of b
2430: 79 74 65 73 20 6f 66 20 6b 65 79 2e 20 4f 72 20  ytes of key. Or 
2440: 74 68 65 20 6b 65 79 20 69 74 73 65 6c 66 20 69  the key itself i
2450: 66 20 69 6e 74 6b 65 79 20 66 6c 61 67 20 69 73  f intkey flag is
2460: 20 73 65 74 2e 0a 2a 2a 20 20 20 20 20 20 2a 20   set..**      * 
2470: 20 20 20 20 50 61 79 6c 6f 61 64 0a 2a 2a 20 20      Payload.**  
2480: 20 20 20 20 34 20 20 20 20 20 46 69 72 73 74 20      4     First 
2490: 70 61 67 65 20 6f 66 20 74 68 65 20 6f 76 65 72  page of the over
24a0: 66 6c 6f 77 20 63 68 61 69 6e 2e 20 20 4f 6d 69  flow chain.  Omi
24b0: 74 74 65 64 20 69 66 20 6e 6f 20 6f 76 65 72 66  tted if no overf
24c0: 6c 6f 77 0a 2a 2a 0a 2a 2a 20 4f 76 65 72 66 6c  low.**.** Overfl
24d0: 6f 77 20 70 61 67 65 73 20 66 6f 72 6d 20 61 20  ow pages form a 
24e0: 6c 69 6e 6b 65 64 20 6c 69 73 74 2e 20 20 45 61  linked list.  Ea
24f0: 63 68 20 70 61 67 65 20 65 78 63 65 70 74 20 74  ch page except t
2500: 68 65 20 6c 61 73 74 20 69 73 20 63 6f 6d 70 6c  he last is compl
2510: 65 74 65 6c 79 0a 2a 2a 20 66 69 6c 6c 65 64 20  etely.** filled 
2520: 77 69 74 68 20 64 61 74 61 20 28 70 61 67 65 73  with data (pages
2530: 69 7a 65 20 2d 20 34 20 62 79 74 65 73 29 2e 20  ize - 4 bytes). 
2540: 20 54 68 65 20 6c 61 73 74 20 70 61 67 65 20 63   The last page c
2550: 61 6e 20 68 61 76 65 20 61 73 20 6c 69 74 74 6c  an have as littl
2560: 65 0a 2a 2a 20 61 73 20 31 20 62 79 74 65 20 6f  e.** as 1 byte o
2570: 66 20 64 61 74 61 2e 0a 2a 2a 0a 2a 2a 20 20 20  f data..**.**   
2580: 20 53 49 5a 45 20 20 20 20 44 45 53 43 52 49 50   SIZE    DESCRIP
2590: 54 49 4f 4e 0a 2a 2a 20 20 20 20 20 20 34 20 20  TION.**      4  
25a0: 20 20 20 50 61 67 65 20 6e 75 6d 62 65 72 20 6f     Page number o
25b0: 66 20 6e 65 78 74 20 6f 76 65 72 66 6c 6f 77 20  f next overflow 
25c0: 70 61 67 65 0a 2a 2a 20 20 20 20 20 20 2a 20 20  page.**      *  
25d0: 20 20 20 44 61 74 61 0a 2a 2a 0a 2a 2a 20 46 72     Data.**.** Fr
25e0: 65 65 6c 69 73 74 20 70 61 67 65 73 20 63 6f 6d  eelist pages com
25f0: 65 20 69 6e 20 74 77 6f 20 73 75 62 74 79 70 65  e in two subtype
2600: 73 3a 20 74 72 75 6e 6b 20 70 61 67 65 73 20 61  s: trunk pages a
2610: 6e 64 20 6c 65 61 66 20 70 61 67 65 73 2e 20 20  nd leaf pages.  
2620: 54 68 65 0a 2a 2a 20 66 69 6c 65 20 68 65 61 64  The.** file head
2630: 65 72 20 70 6f 69 6e 74 73 20 74 6f 20 74 68 65  er points to the
2640: 20 66 69 72 73 74 20 69 6e 20 61 20 6c 69 6e 6b   first in a link
2650: 65 64 20 6c 69 73 74 20 6f 66 20 74 72 75 6e 6b  ed list of trunk
2660: 20 70 61 67 65 2e 20 20 45 61 63 68 20 74 72 75   page.  Each tru
2670: 6e 6b 0a 2a 2a 20 70 61 67 65 20 70 6f 69 6e 74  nk.** page point
2680: 73 20 74 6f 20 6d 75 6c 74 69 70 6c 65 20 6c 65  s to multiple le
2690: 61 66 20 70 61 67 65 73 2e 20 20 54 68 65 20 63  af pages.  The c
26a0: 6f 6e 74 65 6e 74 20 6f 66 20 61 20 6c 65 61 66  ontent of a leaf
26b0: 20 70 61 67 65 20 69 73 0a 2a 2a 20 75 6e 73 70   page is.** unsp
26c0: 65 63 69 66 69 65 64 2e 20 20 41 20 74 72 75 6e  ecified.  A trun
26d0: 6b 20 70 61 67 65 20 6c 6f 6f 6b 73 20 6c 69 6b  k page looks lik
26e0: 65 20 74 68 69 73 3a 0a 2a 2a 0a 2a 2a 20 20 20  e this:.**.**   
26f0: 20 53 49 5a 45 20 20 20 20 44 45 53 43 52 49 50   SIZE    DESCRIP
2700: 54 49 4f 4e 0a 2a 2a 20 20 20 20 20 20 34 20 20  TION.**      4  
2710: 20 20 20 50 61 67 65 20 6e 75 6d 62 65 72 20 6f     Page number o
2720: 66 20 6e 65 78 74 20 74 72 75 6e 6b 20 70 61 67  f next trunk pag
2730: 65 0a 2a 2a 20 20 20 20 20 20 34 20 20 20 20 20  e.**      4     
2740: 4e 75 6d 62 65 72 20 6f 66 20 6c 65 61 66 20 70  Number of leaf p
2750: 6f 69 6e 74 65 72 73 20 6f 6e 20 74 68 69 73 20  ointers on this 
2760: 70 61 67 65 0a 2a 2a 20 20 20 20 20 20 2a 20 20  page.**      *  
2770: 20 20 20 7a 65 72 6f 20 6f 72 20 6d 6f 72 65 20     zero or more 
2780: 70 61 67 65 73 20 6e 75 6d 62 65 72 73 20 6f 66  pages numbers of
2790: 20 6c 65 61 76 65 73 0a 2a 2f 0a 23 69 6e 63 6c   leaves.*/.#incl
27a0: 75 64 65 20 22 73 71 6c 69 74 65 49 6e 74 2e 68  ude "sqliteInt.h
27b0: 22 0a 0a 0a 2f 2a 20 54 68 65 20 66 6f 6c 6c 6f  ".../* The follo
27c0: 77 69 6e 67 20 76 61 6c 75 65 20 69 73 20 74 68  wing value is th
27d0: 65 20 6d 61 78 69 6d 75 6d 20 63 65 6c 6c 20 73  e maximum cell s
27e0: 69 7a 65 20 61 73 73 75 6d 69 6e 67 20 61 20 6d  ize assuming a m
27f0: 61 78 69 6d 75 6d 20 70 61 67 65 0a 2a 2a 20 73  aximum page.** s
2800: 69 7a 65 20 67 69 76 65 20 61 62 6f 76 65 2e 0a  ize give above..
2810: 2a 2f 0a 23 64 65 66 69 6e 65 20 4d 58 5f 43 45  */.#define MX_CE
2820: 4c 4c 5f 53 49 5a 45 28 70 42 74 29 20 20 28 70  LL_SIZE(pBt)  (p
2830: 42 74 2d 3e 70 61 67 65 53 69 7a 65 2d 38 29 0a  Bt->pageSize-8).
2840: 0a 2f 2a 20 54 68 65 20 6d 61 78 69 6d 75 6d 20  ./* The maximum 
2850: 6e 75 6d 62 65 72 20 6f 66 20 63 65 6c 6c 73 20  number of cells 
2860: 6f 6e 20 61 20 73 69 6e 67 6c 65 20 70 61 67 65  on a single page
2870: 20 6f 66 20 74 68 65 20 64 61 74 61 62 61 73 65   of the database
2880: 2e 20 20 54 68 69 73 0a 2a 2a 20 61 73 73 75 6d  .  This.** assum
2890: 65 73 20 61 20 6d 69 6e 69 6d 75 6d 20 63 65 6c  es a minimum cel
28a0: 6c 20 73 69 7a 65 20 6f 66 20 36 20 62 79 74 65  l size of 6 byte
28b0: 73 20 20 28 34 20 62 79 74 65 73 20 66 6f 72 20  s  (4 bytes for 
28c0: 74 68 65 20 63 65 6c 6c 20 69 74 73 65 6c 66 0a  the cell itself.
28d0: 2a 2a 20 70 6c 75 73 20 32 20 62 79 74 65 73 20  ** plus 2 bytes 
28e0: 66 6f 72 20 74 68 65 20 69 6e 64 65 78 20 74 6f  for the index to
28f0: 20 74 68 65 20 63 65 6c 6c 20 69 6e 20 74 68 65   the cell in the
2900: 20 70 61 67 65 20 68 65 61 64 65 72 29 2e 20 20   page header).  
2910: 53 75 63 68 0a 2a 2a 20 73 6d 61 6c 6c 20 63 65  Such.** small ce
2920: 6c 6c 73 20 77 69 6c 6c 20 62 65 20 72 61 72 65  lls will be rare
2930: 2c 20 62 75 74 20 74 68 65 79 20 61 72 65 20 70  , but they are p
2940: 6f 73 73 69 62 6c 65 2e 0a 2a 2f 0a 23 64 65 66  ossible..*/.#def
2950: 69 6e 65 20 4d 58 5f 43 45 4c 4c 28 70 42 74 29  ine MX_CELL(pBt)
2960: 20 28 28 70 42 74 2d 3e 70 61 67 65 53 69 7a 65   ((pBt->pageSize
2970: 2d 38 29 2f 36 29 0a 0a 2f 2a 20 46 6f 72 77 61  -8)/6)../* Forwa
2980: 72 64 20 64 65 63 6c 61 72 61 74 69 6f 6e 73 20  rd declarations 
2990: 2a 2f 0a 74 79 70 65 64 65 66 20 73 74 72 75 63  */.typedef struc
29a0: 74 20 4d 65 6d 50 61 67 65 20 4d 65 6d 50 61 67  t MemPage MemPag
29b0: 65 3b 0a 74 79 70 65 64 65 66 20 73 74 72 75 63  e;.typedef struc
29c0: 74 20 42 74 4c 6f 63 6b 20 42 74 4c 6f 63 6b 3b  t BtLock BtLock;
29d0: 0a 0a 2f 2a 0a 2a 2a 20 54 68 69 73 20 69 73 20  ../*.** This is 
29e0: 61 20 6d 61 67 69 63 20 73 74 72 69 6e 67 20 74  a magic string t
29f0: 68 61 74 20 61 70 70 65 61 72 73 20 61 74 20 74  hat appears at t
2a00: 68 65 20 62 65 67 69 6e 6e 69 6e 67 20 6f 66 20  he beginning of 
2a10: 65 76 65 72 79 0a 2a 2a 20 53 51 4c 69 74 65 20  every.** SQLite 
2a20: 64 61 74 61 62 61 73 65 20 69 6e 20 6f 72 64 65  database in orde
2a30: 72 20 74 6f 20 69 64 65 6e 74 69 66 79 20 74 68  r to identify th
2a40: 65 20 66 69 6c 65 20 61 73 20 61 20 72 65 61 6c  e file as a real
2a50: 20 64 61 74 61 62 61 73 65 2e 0a 2a 2a 0a 2a 2a   database..**.**
2a60: 20 59 6f 75 20 63 61 6e 20 63 68 61 6e 67 65 20   You can change 
2a70: 74 68 69 73 20 76 61 6c 75 65 20 61 74 20 63 6f  this value at co
2a80: 6d 70 69 6c 65 2d 74 69 6d 65 20 62 79 20 73 70  mpile-time by sp
2a90: 65 63 69 66 79 69 6e 67 20 61 0a 2a 2a 20 2d 44  ecifying a.** -D
2aa0: 53 51 4c 49 54 45 5f 46 49 4c 45 5f 48 45 41 44  SQLITE_FILE_HEAD
2ab0: 45 52 3d 22 2e 2e 2e 22 20 6f 6e 20 74 68 65 20  ER="..." on the 
2ac0: 63 6f 6d 70 69 6c 65 72 20 63 6f 6d 6d 61 6e 64  compiler command
2ad0: 2d 6c 69 6e 65 2e 20 20 54 68 65 0a 2a 2a 20 68  -line.  The.** h
2ae0: 65 61 64 65 72 20 6d 75 73 74 20 62 65 20 65 78  eader must be ex
2af0: 61 63 74 6c 79 20 31 36 20 62 79 74 65 73 20 69  actly 16 bytes i
2b00: 6e 63 6c 75 64 69 6e 67 20 74 68 65 20 7a 65 72  ncluding the zer
2b10: 6f 2d 74 65 72 6d 69 6e 61 74 6f 72 20 73 6f 0a  o-terminator so.
2b20: 2a 2a 20 74 68 65 20 73 74 72 69 6e 67 20 69 74  ** the string it
2b30: 73 65 6c 66 20 73 68 6f 75 6c 64 20 62 65 20 31  self should be 1
2b40: 35 20 63 68 61 72 61 63 74 65 72 73 20 6c 6f 6e  5 characters lon
2b50: 67 2e 20 20 49 66 20 79 6f 75 20 63 68 61 6e 67  g.  If you chang
2b60: 65 0a 2a 2a 20 74 68 65 20 68 65 61 64 65 72 2c  e.** the header,
2b70: 20 74 68 65 6e 20 79 6f 75 72 20 63 75 73 74 6f   then your custo
2b80: 6d 20 6c 69 62 72 61 72 79 20 77 69 6c 6c 20 6e  m library will n
2b90: 6f 74 20 62 65 20 61 62 6c 65 20 74 6f 20 72 65  ot be able to re
2ba0: 61 64 20 0a 2a 2a 20 64 61 74 61 62 61 73 65 73  ad .** databases
2bb0: 20 67 65 6e 65 72 61 74 65 64 20 62 79 20 74 68   generated by th
2bc0: 65 20 73 74 61 6e 64 61 72 64 20 74 6f 6f 6c 73  e standard tools
2bd0: 20 61 6e 64 20 74 68 65 20 73 74 61 6e 64 61 72   and the standar
2be0: 64 20 74 6f 6f 6c 73 0a 2a 2a 20 77 69 6c 6c 20  d tools.** will 
2bf0: 6e 6f 74 20 62 65 20 61 62 6c 65 20 74 6f 20 72  not be able to r
2c00: 65 61 64 20 64 61 74 61 62 61 73 65 73 20 63 72  ead databases cr
2c10: 65 61 74 65 64 20 62 79 20 79 6f 75 72 20 63 75  eated by your cu
2c20: 73 74 6f 6d 20 6c 69 62 72 61 72 79 2e 0a 2a 2f  stom library..*/
2c30: 0a 23 69 66 6e 64 65 66 20 53 51 4c 49 54 45 5f  .#ifndef SQLITE_
2c40: 46 49 4c 45 5f 48 45 41 44 45 52 20 2f 2a 20 31  FILE_HEADER /* 1
2c50: 32 33 34 35 36 37 38 39 20 31 32 33 34 35 36 20  23456789 123456 
2c60: 2a 2f 0a 23 20 20 64 65 66 69 6e 65 20 53 51 4c  */.#  define SQL
2c70: 49 54 45 5f 46 49 4c 45 5f 48 45 41 44 45 52 20  ITE_FILE_HEADER 
2c80: 22 53 51 4c 69 74 65 20 66 6f 72 6d 61 74 20 33  "SQLite format 3
2c90: 22 0a 23 65 6e 64 69 66 0a 0a 2f 2a 0a 2a 2a 20  ".#endif../*.** 
2ca0: 50 61 67 65 20 74 79 70 65 20 66 6c 61 67 73 2e  Page type flags.
2cb0: 20 20 41 6e 20 4f 52 65 64 20 63 6f 6d 62 69 6e    An ORed combin
2cc0: 61 74 69 6f 6e 20 6f 66 20 74 68 65 73 65 20 66  ation of these f
2cd0: 6c 61 67 73 20 61 70 70 65 61 72 20 61 73 20 74  lags appear as t
2ce0: 68 65 0a 2a 2a 20 66 69 72 73 74 20 62 79 74 65  he.** first byte
2cf0: 20 6f 66 20 6f 6e 2d 64 69 73 6b 20 69 6d 61 67   of on-disk imag
2d00: 65 20 6f 66 20 65 76 65 72 79 20 42 54 72 65 65  e of every BTree
2d10: 20 70 61 67 65 2e 0a 2a 2f 0a 23 64 65 66 69 6e   page..*/.#defin
2d20: 65 20 50 54 46 5f 49 4e 54 4b 45 59 20 20 20 20  e PTF_INTKEY    
2d30: 30 78 30 31 0a 23 64 65 66 69 6e 65 20 50 54 46  0x01.#define PTF
2d40: 5f 5a 45 52 4f 44 41 54 41 20 20 30 78 30 32 0a  _ZERODATA  0x02.
2d50: 23 64 65 66 69 6e 65 20 50 54 46 5f 4c 45 41 46  #define PTF_LEAF
2d60: 44 41 54 41 20 20 30 78 30 34 0a 23 64 65 66 69  DATA  0x04.#defi
2d70: 6e 65 20 50 54 46 5f 4c 45 41 46 20 20 20 20 20  ne PTF_LEAF     
2d80: 20 30 78 30 38 0a 0a 2f 2a 0a 2a 2a 20 41 73 20   0x08../*.** As 
2d90: 65 61 63 68 20 70 61 67 65 20 6f 66 20 74 68 65  each page of the
2da0: 20 66 69 6c 65 20 69 73 20 6c 6f 61 64 65 64 20   file is loaded 
2db0: 69 6e 74 6f 20 6d 65 6d 6f 72 79 2c 20 61 6e 20  into memory, an 
2dc0: 69 6e 73 74 61 6e 63 65 20 6f 66 20 74 68 65 20  instance of the 
2dd0: 66 6f 6c 6c 6f 77 69 6e 67 0a 2a 2a 20 73 74 72  following.** str
2de0: 75 63 74 75 72 65 20 69 73 20 61 70 70 65 6e 64  ucture is append
2df0: 65 64 20 61 6e 64 20 69 6e 69 74 69 61 6c 69 7a  ed and initializ
2e00: 65 64 20 74 6f 20 7a 65 72 6f 2e 20 20 54 68 69  ed to zero.  Thi
2e10: 73 20 73 74 72 75 63 74 75 72 65 20 73 74 6f 72  s structure stor
2e20: 65 73 0a 2a 2a 20 69 6e 66 6f 72 6d 61 74 69 6f  es.** informatio
2e30: 6e 20 61 62 6f 75 74 20 74 68 65 20 70 61 67 65  n about the page
2e40: 20 74 68 61 74 20 69 73 20 64 65 63 6f 64 65 64   that is decoded
2e50: 20 66 72 6f 6d 20 74 68 65 20 72 61 77 20 66 69   from the raw fi
2e60: 6c 65 20 70 61 67 65 2e 0a 2a 2a 0a 2a 2a 20 54  le page..**.** T
2e70: 68 65 20 70 50 61 72 65 6e 74 20 66 69 65 6c 64  he pParent field
2e80: 20 70 6f 69 6e 74 73 20 62 61 63 6b 20 74 6f 20   points back to 
2e90: 74 68 65 20 70 61 72 65 6e 74 20 70 61 67 65 2e  the parent page.
2ea0: 20 20 54 68 69 73 20 61 6c 6c 6f 77 73 20 75 73    This allows us
2eb0: 20 74 6f 0a 2a 2a 20 77 61 6c 6b 20 75 70 20 74   to.** walk up t
2ec0: 68 65 20 42 54 72 65 65 20 66 72 6f 6d 20 61 6e  he BTree from an
2ed0: 79 20 6c 65 61 66 20 74 6f 20 74 68 65 20 72 6f  y leaf to the ro
2ee0: 6f 74 2e 20 20 43 61 72 65 20 6d 75 73 74 20 62  ot.  Care must b
2ef0: 65 20 74 61 6b 65 6e 20 74 6f 0a 2a 2a 20 75 6e  e taken to.** un
2f00: 72 65 66 28 29 20 74 68 65 20 70 61 72 65 6e 74  ref() the parent
2f10: 20 70 61 67 65 20 70 6f 69 6e 74 65 72 20 77 68   page pointer wh
2f20: 65 6e 20 74 68 69 73 20 70 61 67 65 20 69 73 20  en this page is 
2f30: 6e 6f 20 6c 6f 6e 67 65 72 20 72 65 66 65 72 65  no longer refere
2f40: 6e 63 65 64 2e 0a 2a 2a 20 54 68 65 20 70 61 67  nced..** The pag
2f50: 65 44 65 73 74 72 75 63 74 6f 72 28 29 20 72 6f  eDestructor() ro
2f60: 75 74 69 6e 65 20 68 61 6e 64 6c 65 73 20 74 68  utine handles th
2f70: 61 74 20 63 68 6f 72 65 2e 0a 2a 2a 0a 2a 2a 20  at chore..**.** 
2f80: 41 63 63 65 73 73 20 74 6f 20 61 6c 6c 20 66 69  Access to all fi
2f90: 65 6c 64 73 20 6f 66 20 74 68 69 73 20 73 74 72  elds of this str
2fa0: 75 63 74 75 72 65 20 69 73 20 63 6f 6e 74 72 6f  ucture is contro
2fb0: 6c 6c 65 64 20 62 79 20 74 68 65 20 6d 75 74 65  lled by the mute
2fc0: 78 0a 2a 2a 20 73 74 6f 72 65 64 20 69 6e 20 4d  x.** stored in M
2fd0: 65 6d 50 61 67 65 2e 70 42 74 2d 3e 6d 75 74 65  emPage.pBt->mute
2fe0: 78 2e 0a 2a 2f 0a 73 74 72 75 63 74 20 4d 65 6d  x..*/.struct Mem
2ff0: 50 61 67 65 20 7b 0a 20 20 75 38 20 69 73 49 6e  Page {.  u8 isIn
3000: 69 74 3b 20 20 20 20 20 20 20 20 20 20 20 2f 2a  it;           /*
3010: 20 54 72 75 65 20 69 66 20 70 72 65 76 69 6f 75   True if previou
3020: 73 6c 79 20 69 6e 69 74 69 61 6c 69 7a 65 64 2e  sly initialized.
3030: 20 4d 55 53 54 20 42 45 20 46 49 52 53 54 21 20   MUST BE FIRST! 
3040: 2a 2f 0a 20 20 75 38 20 6e 4f 76 65 72 66 6c 6f  */.  u8 nOverflo
3050: 77 3b 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d  w;        /* Num
3060: 62 65 72 20 6f 66 20 6f 76 65 72 66 6c 6f 77 20  ber of overflow 
3070: 63 65 6c 6c 20 62 6f 64 69 65 73 20 69 6e 20 61  cell bodies in a
3080: 43 65 6c 6c 5b 5d 20 2a 2f 0a 20 20 75 38 20 69  Cell[] */.  u8 i
3090: 6e 74 4b 65 79 3b 20 20 20 20 20 20 20 20 20 20  ntKey;          
30a0: 20 2f 2a 20 54 72 75 65 20 69 66 20 69 6e 74 6b   /* True if intk
30b0: 65 79 20 66 6c 61 67 20 69 73 20 73 65 74 20 2a  ey flag is set *
30c0: 2f 0a 20 20 75 38 20 6c 65 61 66 3b 20 20 20 20  /.  u8 leaf;    
30d0: 20 20 20 20 20 20 20 20 20 2f 2a 20 54 72 75 65           /* True
30e0: 20 69 66 20 6c 65 61 66 20 66 6c 61 67 20 69 73   if leaf flag is
30f0: 20 73 65 74 20 2a 2f 0a 20 20 75 38 20 68 61 73   set */.  u8 has
3100: 44 61 74 61 3b 20 20 20 20 20 20 20 20 20 20 2f  Data;          /
3110: 2a 20 54 72 75 65 20 69 66 20 74 68 69 73 20 70  * True if this p
3120: 61 67 65 20 73 74 6f 72 65 73 20 64 61 74 61 20  age stores data 
3130: 2a 2f 0a 20 20 75 38 20 68 64 72 4f 66 66 73 65  */.  u8 hdrOffse
3140: 74 3b 20 20 20 20 20 20 20 20 2f 2a 20 31 30 30  t;        /* 100
3150: 20 66 6f 72 20 70 61 67 65 20 31 2e 20 20 30 20   for page 1.  0 
3160: 6f 74 68 65 72 77 69 73 65 20 2a 2f 0a 20 20 75  otherwise */.  u
3170: 38 20 63 68 69 6c 64 50 74 72 53 69 7a 65 3b 20  8 childPtrSize; 
3180: 20 20 20 20 2f 2a 20 30 20 69 66 20 6c 65 61 66      /* 0 if leaf
3190: 3d 3d 31 2e 20 20 34 20 69 66 20 6c 65 61 66 3d  ==1.  4 if leaf=
31a0: 3d 30 20 2a 2f 0a 20 20 75 31 36 20 6d 61 78 4c  =0 */.  u16 maxL
31b0: 6f 63 61 6c 3b 20 20 20 20 20 20 20 20 2f 2a 20  ocal;        /* 
31c0: 43 6f 70 79 20 6f 66 20 42 74 53 68 61 72 65 64  Copy of BtShared
31d0: 2e 6d 61 78 4c 6f 63 61 6c 20 6f 72 20 42 74 53  .maxLocal or BtS
31e0: 68 61 72 65 64 2e 6d 61 78 4c 65 61 66 20 2a 2f  hared.maxLeaf */
31f0: 0a 20 20 75 31 36 20 6d 69 6e 4c 6f 63 61 6c 3b  .  u16 minLocal;
3200: 20 20 20 20 20 20 20 20 2f 2a 20 43 6f 70 79 20          /* Copy 
3210: 6f 66 20 42 74 53 68 61 72 65 64 2e 6d 69 6e 4c  of BtShared.minL
3220: 6f 63 61 6c 20 6f 72 20 42 74 53 68 61 72 65 64  ocal or BtShared
3230: 2e 6d 69 6e 4c 65 61 66 20 2a 2f 0a 20 20 75 31  .minLeaf */.  u1
3240: 36 20 63 65 6c 6c 4f 66 66 73 65 74 3b 20 20 20  6 cellOffset;   
3250: 20 20 20 2f 2a 20 49 6e 64 65 78 20 69 6e 20 61     /* Index in a
3260: 44 61 74 61 20 6f 66 20 66 69 72 73 74 20 63 65  Data of first ce
3270: 6c 6c 20 70 6f 69 6e 74 65 72 20 2a 2f 0a 20 20  ll pointer */.  
3280: 75 31 36 20 6e 46 72 65 65 3b 20 20 20 20 20 20  u16 nFree;      
3290: 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f       /* Number o
32a0: 66 20 66 72 65 65 20 62 79 74 65 73 20 6f 6e 20  f free bytes on 
32b0: 74 68 65 20 70 61 67 65 20 2a 2f 0a 20 20 75 31  the page */.  u1
32c0: 36 20 6e 43 65 6c 6c 3b 20 20 20 20 20 20 20 20  6 nCell;        
32d0: 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20     /* Number of 
32e0: 63 65 6c 6c 73 20 6f 6e 20 74 68 69 73 20 70 61  cells on this pa
32f0: 67 65 2c 20 6c 6f 63 61 6c 20 61 6e 64 20 6f 76  ge, local and ov
3300: 66 6c 20 2a 2f 0a 20 20 75 31 36 20 6d 61 73 6b  fl */.  u16 mask
3310: 50 61 67 65 3b 20 20 20 20 20 20 20 20 2f 2a 20  Page;        /* 
3320: 4d 61 73 6b 20 66 6f 72 20 70 61 67 65 20 6f 66  Mask for page of
3330: 66 73 65 74 20 2a 2f 0a 20 20 73 74 72 75 63 74  fset */.  struct
3340: 20 5f 4f 76 66 6c 43 65 6c 6c 20 7b 20 20 20 2f   _OvflCell {   /
3350: 2a 20 43 65 6c 6c 73 20 74 68 61 74 20 77 69 6c  * Cells that wil
3360: 6c 20 6e 6f 74 20 66 69 74 20 6f 6e 20 61 44 61  l not fit on aDa
3370: 74 61 5b 5d 20 2a 2f 0a 20 20 20 20 75 38 20 2a  ta[] */.    u8 *
3380: 70 43 65 6c 6c 3b 20 20 20 20 20 20 20 20 20 20  pCell;          
3390: 2f 2a 20 50 6f 69 6e 74 65 72 73 20 74 6f 20 74  /* Pointers to t
33a0: 68 65 20 62 6f 64 79 20 6f 66 20 74 68 65 20 6f  he body of the o
33b0: 76 65 72 66 6c 6f 77 20 63 65 6c 6c 20 2a 2f 0a  verflow cell */.
33c0: 20 20 20 20 75 31 36 20 69 64 78 3b 20 20 20 20      u16 idx;    
33d0: 20 20 20 20 20 20 20 20 2f 2a 20 49 6e 73 65 72          /* Inser
33e0: 74 20 74 68 69 73 20 63 65 6c 6c 20 62 65 66 6f  t this cell befo
33f0: 72 65 20 69 64 78 2d 74 68 20 6e 6f 6e 2d 6f 76  re idx-th non-ov
3400: 65 72 66 6c 6f 77 20 63 65 6c 6c 20 2a 2f 0a 20  erflow cell */. 
3410: 20 7d 20 61 4f 76 66 6c 5b 35 5d 3b 0a 20 20 42   } aOvfl[5];.  B
3420: 74 53 68 61 72 65 64 20 2a 70 42 74 3b 20 20 20  tShared *pBt;   
3430: 20 20 20 20 2f 2a 20 50 6f 69 6e 74 65 72 20 74      /* Pointer t
3440: 6f 20 42 74 53 68 61 72 65 64 20 74 68 61 74 20  o BtShared that 
3450: 74 68 69 73 20 70 61 67 65 20 69 73 20 70 61 72  this page is par
3460: 74 20 6f 66 20 2a 2f 0a 20 20 75 38 20 2a 61 44  t of */.  u8 *aD
3470: 61 74 61 3b 20 20 20 20 20 20 20 20 20 20 20 2f  ata;           /
3480: 2a 20 50 6f 69 6e 74 65 72 20 74 6f 20 64 69 73  * Pointer to dis
3490: 6b 20 69 6d 61 67 65 20 6f 66 20 74 68 65 20 70  k image of the p
34a0: 61 67 65 20 64 61 74 61 20 2a 2f 0a 20 20 44 62  age data */.  Db
34b0: 50 61 67 65 20 2a 70 44 62 50 61 67 65 3b 20 20  Page *pDbPage;  
34c0: 20 20 20 2f 2a 20 50 61 67 65 72 20 70 61 67 65     /* Pager page
34d0: 20 68 61 6e 64 6c 65 20 2a 2f 0a 20 20 50 67 6e   handle */.  Pgn
34e0: 6f 20 70 67 6e 6f 3b 20 20 20 20 20 20 20 20 20  o pgno;         
34f0: 20 20 2f 2a 20 50 61 67 65 20 6e 75 6d 62 65 72    /* Page number
3500: 20 66 6f 72 20 74 68 69 73 20 70 61 67 65 20 2a   for this page *
3510: 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 54 68 65 20  /.};../*.** The 
3520: 69 6e 2d 6d 65 6d 6f 72 79 20 69 6d 61 67 65 20  in-memory image 
3530: 6f 66 20 61 20 64 69 73 6b 20 70 61 67 65 20 68  of a disk page h
3540: 61 73 20 74 68 65 20 61 75 78 69 6c 69 61 72 79  as the auxiliary
3550: 20 69 6e 66 6f 72 6d 61 74 69 6f 6e 20 61 70 70   information app
3560: 65 6e 64 65 64 0a 2a 2a 20 74 6f 20 74 68 65 20  ended.** to the 
3570: 65 6e 64 2e 20 20 45 58 54 52 41 5f 53 49 5a 45  end.  EXTRA_SIZE
3580: 20 69 73 20 74 68 65 20 6e 75 6d 62 65 72 20 6f   is the number o
3590: 66 20 62 79 74 65 73 20 6f 66 20 73 70 61 63 65  f bytes of space
35a0: 20 6e 65 65 64 65 64 20 74 6f 20 68 6f 6c 64 0a   needed to hold.
35b0: 2a 2a 20 74 68 61 74 20 65 78 74 72 61 20 69 6e  ** that extra in
35c0: 66 6f 72 6d 61 74 69 6f 6e 2e 0a 2a 2f 0a 23 64  formation..*/.#d
35d0: 65 66 69 6e 65 20 45 58 54 52 41 5f 53 49 5a 45  efine EXTRA_SIZE
35e0: 20 73 69 7a 65 6f 66 28 4d 65 6d 50 61 67 65 29   sizeof(MemPage)
35f0: 0a 0a 2f 2a 0a 2a 2a 20 41 20 6c 69 6e 6b 65 64  ../*.** A linked
3600: 20 6c 69 73 74 20 6f 66 20 74 68 65 20 66 6f 6c   list of the fol
3610: 6c 6f 77 69 6e 67 20 73 74 72 75 63 74 75 72 65  lowing structure
3620: 73 20 69 73 20 73 74 6f 72 65 64 20 61 74 20 42  s is stored at B
3630: 74 53 68 61 72 65 64 2e 70 4c 6f 63 6b 2e 0a 2a  tShared.pLock..*
3640: 2a 20 4c 6f 63 6b 73 20 61 72 65 20 61 64 64 65  * Locks are adde
3650: 64 20 28 6f 72 20 75 70 67 72 61 64 65 64 20 66  d (or upgraded f
3660: 72 6f 6d 20 52 45 41 44 5f 4c 4f 43 4b 20 74 6f  rom READ_LOCK to
3670: 20 57 52 49 54 45 5f 4c 4f 43 4b 29 20 77 68 65   WRITE_LOCK) whe
3680: 6e 20 61 20 63 75 72 73 6f 72 20 0a 2a 2a 20 69  n a cursor .** i
3690: 73 20 6f 70 65 6e 65 64 20 6f 6e 20 74 68 65 20  s opened on the 
36a0: 74 61 62 6c 65 20 77 69 74 68 20 72 6f 6f 74 20  table with root 
36b0: 70 61 67 65 20 42 74 53 68 61 72 65 64 2e 69 54  page BtShared.iT
36c0: 61 62 6c 65 2e 20 4c 6f 63 6b 73 20 61 72 65 20  able. Locks are 
36d0: 72 65 6d 6f 76 65 64 0a 2a 2a 20 66 72 6f 6d 20  removed.** from 
36e0: 74 68 69 73 20 6c 69 73 74 20 77 68 65 6e 20 61  this list when a
36f0: 20 74 72 61 6e 73 61 63 74 69 6f 6e 20 69 73 20   transaction is 
3700: 63 6f 6d 6d 69 74 74 65 64 20 6f 72 20 72 6f 6c  committed or rol
3710: 6c 65 64 20 62 61 63 6b 2c 20 6f 72 20 77 68 65  led back, or whe
3720: 6e 0a 2a 2a 20 61 20 62 74 72 65 65 20 68 61 6e  n.** a btree han
3730: 64 6c 65 20 69 73 20 63 6c 6f 73 65 64 2e 0a 2a  dle is closed..*
3740: 2f 0a 73 74 72 75 63 74 20 42 74 4c 6f 63 6b 20  /.struct BtLock 
3750: 7b 0a 20 20 42 74 72 65 65 20 2a 70 42 74 72 65  {.  Btree *pBtre
3760: 65 3b 20 20 20 20 20 20 20 20 2f 2a 20 42 74 72  e;        /* Btr
3770: 65 65 20 68 61 6e 64 6c 65 20 68 6f 6c 64 69 6e  ee handle holdin
3780: 67 20 74 68 69 73 20 6c 6f 63 6b 20 2a 2f 0a 20  g this lock */. 
3790: 20 50 67 6e 6f 20 69 54 61 62 6c 65 3b 20 20 20   Pgno iTable;   
37a0: 20 20 20 20 20 20 20 2f 2a 20 52 6f 6f 74 20 70         /* Root p
37b0: 61 67 65 20 6f 66 20 74 61 62 6c 65 20 2a 2f 0a  age of table */.
37c0: 20 20 75 38 20 65 4c 6f 63 6b 3b 20 20 20 20 20    u8 eLock;     
37d0: 20 20 20 20 20 20 20 20 2f 2a 20 52 45 41 44 5f          /* READ_
37e0: 4c 4f 43 4b 20 6f 72 20 57 52 49 54 45 5f 4c 4f  LOCK or WRITE_LO
37f0: 43 4b 20 2a 2f 0a 20 20 42 74 4c 6f 63 6b 20 2a  CK */.  BtLock *
3800: 70 4e 65 78 74 3b 20 20 20 20 20 20 20 20 2f 2a  pNext;        /*
3810: 20 4e 65 78 74 20 69 6e 20 42 74 53 68 61 72 65   Next in BtShare
3820: 64 2e 70 4c 6f 63 6b 20 6c 69 73 74 20 2a 2f 0a  d.pLock list */.
3830: 7d 3b 0a 0a 2f 2a 20 43 61 6e 64 69 64 61 74 65  };../* Candidate
3840: 20 76 61 6c 75 65 73 20 66 6f 72 20 42 74 4c 6f   values for BtLo
3850: 63 6b 2e 65 4c 6f 63 6b 20 2a 2f 0a 23 64 65 66  ck.eLock */.#def
3860: 69 6e 65 20 52 45 41 44 5f 4c 4f 43 4b 20 20 20  ine READ_LOCK   
3870: 20 20 31 0a 23 64 65 66 69 6e 65 20 57 52 49 54    1.#define WRIT
3880: 45 5f 4c 4f 43 4b 20 20 20 20 32 0a 0a 2f 2a 20  E_LOCK    2../* 
3890: 41 20 42 74 72 65 65 20 68 61 6e 64 6c 65 0a 2a  A Btree handle.*
38a0: 2a 0a 2a 2a 20 41 20 64 61 74 61 62 61 73 65 20  *.** A database 
38b0: 63 6f 6e 6e 65 63 74 69 6f 6e 20 63 6f 6e 74 61  connection conta
38c0: 69 6e 73 20 61 20 70 6f 69 6e 74 65 72 20 74 6f  ins a pointer to
38d0: 20 61 6e 20 69 6e 73 74 61 6e 63 65 20 6f 66 0a   an instance of.
38e0: 2a 2a 20 74 68 69 73 20 6f 62 6a 65 63 74 20 66  ** this object f
38f0: 6f 72 20 65 76 65 72 79 20 64 61 74 61 62 61 73  or every databas
3900: 65 20 66 69 6c 65 20 74 68 61 74 20 69 74 20 68  e file that it h
3910: 61 73 20 6f 70 65 6e 2e 20 20 54 68 69 73 20 73  as open.  This s
3920: 74 72 75 63 74 75 72 65 0a 2a 2a 20 69 73 20 6f  tructure.** is o
3930: 70 61 71 75 65 20 74 6f 20 74 68 65 20 64 61 74  paque to the dat
3940: 61 62 61 73 65 20 63 6f 6e 6e 65 63 74 69 6f 6e  abase connection
3950: 2e 20 20 54 68 65 20 64 61 74 61 62 61 73 65 20  .  The database 
3960: 63 6f 6e 6e 65 63 74 69 6f 6e 20 63 61 6e 6e 6f  connection canno
3970: 74 0a 2a 2a 20 73 65 65 20 74 68 65 20 69 6e 74  t.** see the int
3980: 65 72 6e 61 6c 73 20 6f 66 20 74 68 69 73 20 73  ernals of this s
3990: 74 72 75 63 74 75 72 65 20 61 6e 64 20 6f 6e 6c  tructure and onl
39a0: 79 20 64 65 61 6c 73 20 77 69 74 68 20 70 6f 69  y deals with poi
39b0: 6e 74 65 72 73 20 74 6f 0a 2a 2a 20 74 68 69 73  nters to.** this
39c0: 20 73 74 72 75 63 74 75 72 65 2e 0a 2a 2a 0a 2a   structure..**.*
39d0: 2a 20 46 6f 72 20 73 6f 6d 65 20 64 61 74 61 62  * For some datab
39e0: 61 73 65 20 66 69 6c 65 73 2c 20 74 68 65 20 73  ase files, the s
39f0: 61 6d 65 20 75 6e 64 65 72 6c 79 69 6e 67 20 64  ame underlying d
3a00: 61 74 61 62 61 73 65 20 63 61 63 68 65 20 6d 69  atabase cache mi
3a10: 67 68 74 20 62 65 20 0a 2a 2a 20 73 68 61 72 65  ght be .** share
3a20: 64 20 62 65 74 77 65 65 6e 20 6d 75 6c 74 69 70  d between multip
3a30: 6c 65 20 63 6f 6e 6e 65 63 74 69 6f 6e 73 2e 20  le connections. 
3a40: 20 49 6e 20 74 68 61 74 20 63 61 73 65 2c 20 65   In that case, e
3a50: 61 63 68 20 63 6f 6e 6e 65 63 74 69 6f 6e 0a 2a  ach connection.*
3a60: 2a 20 68 61 73 20 69 74 20 6f 77 6e 20 69 6e 73  * has it own ins
3a70: 74 61 6e 63 65 20 6f 66 20 74 68 69 73 20 6f 62  tance of this ob
3a80: 6a 65 63 74 2e 20 20 42 75 74 20 65 61 63 68 20  ject.  But each 
3a90: 69 6e 73 74 61 6e 63 65 20 6f 66 20 74 68 69 73  instance of this
3aa0: 20 6f 62 6a 65 63 74 0a 2a 2a 20 70 6f 69 6e 74   object.** point
3ab0: 73 20 74 6f 20 74 68 65 20 73 61 6d 65 20 42 74  s to the same Bt
3ac0: 53 68 61 72 65 64 20 6f 62 6a 65 63 74 2e 20 20  Shared object.  
3ad0: 54 68 65 20 64 61 74 61 62 61 73 65 20 63 61 63  The database cac
3ae0: 68 65 20 61 6e 64 20 74 68 65 0a 2a 2a 20 73 63  he and the.** sc
3af0: 68 65 6d 61 20 61 73 73 6f 63 69 61 74 65 64 20  hema associated 
3b00: 77 69 74 68 20 74 68 65 20 64 61 74 61 62 61 73  with the databas
3b10: 65 20 66 69 6c 65 20 61 72 65 20 61 6c 6c 20 63  e file are all c
3b20: 6f 6e 74 61 69 6e 65 64 20 77 69 74 68 69 6e 0a  ontained within.
3b30: 2a 2a 20 74 68 65 20 42 74 53 68 61 72 65 64 20  ** the BtShared 
3b40: 6f 62 6a 65 63 74 2e 0a 2a 2a 0a 2a 2a 20 41 6c  object..**.** Al
3b50: 6c 20 66 69 65 6c 64 73 20 69 6e 20 74 68 69 73  l fields in this
3b60: 20 73 74 72 75 63 74 75 72 65 20 61 72 65 20 61   structure are a
3b70: 63 63 65 73 73 65 64 20 75 6e 64 65 72 20 73 71  ccessed under sq
3b80: 6c 69 74 65 33 2e 6d 75 74 65 78 2e 0a 2a 2a 20  lite3.mutex..** 
3b90: 54 68 65 20 70 42 74 20 70 6f 69 6e 74 65 72 20  The pBt pointer 
3ba0: 69 74 73 65 6c 66 20 6d 61 79 20 6e 6f 74 20 62  itself may not b
3bb0: 65 20 63 68 61 6e 67 65 64 20 77 68 69 6c 65 20  e changed while 
3bc0: 74 68 65 72 65 20 65 78 69 73 74 73 20 63 75 72  there exists cur
3bd0: 73 6f 72 73 20 0a 2a 2a 20 69 6e 20 74 68 65 20  sors .** in the 
3be0: 72 65 66 65 72 65 6e 63 65 64 20 42 74 53 68 61  referenced BtSha
3bf0: 72 65 64 20 74 68 61 74 20 70 6f 69 6e 74 20 62  red that point b
3c00: 61 63 6b 20 74 6f 20 74 68 69 73 20 42 74 72 65  ack to this Btre
3c10: 65 20 73 69 6e 63 65 20 74 68 6f 73 65 0a 2a 2a  e since those.**
3c20: 20 63 75 72 73 6f 72 73 20 68 61 76 65 20 74 6f   cursors have to
3c30: 20 67 6f 20 74 68 72 6f 75 67 68 20 74 68 69 73   go through this
3c40: 20 42 74 72 65 65 20 74 6f 20 66 69 6e 64 20 74   Btree to find t
3c50: 68 65 69 72 20 42 74 53 68 61 72 65 64 20 61 6e  heir BtShared an
3c60: 64 0a 2a 2a 20 74 68 65 79 20 6f 66 74 65 6e 20  d.** they often 
3c70: 64 6f 20 73 6f 20 77 69 74 68 6f 75 74 20 68 6f  do so without ho
3c80: 6c 64 69 6e 67 20 73 71 6c 69 74 65 33 2e 6d 75  lding sqlite3.mu
3c90: 74 65 78 2e 0a 2a 2f 0a 73 74 72 75 63 74 20 42  tex..*/.struct B
3ca0: 74 72 65 65 20 7b 0a 20 20 73 71 6c 69 74 65 33  tree {.  sqlite3
3cb0: 20 2a 64 62 3b 20 20 20 20 20 20 20 2f 2a 20 54   *db;       /* T
3cc0: 68 65 20 64 61 74 61 62 61 73 65 20 63 6f 6e 6e  he database conn
3cd0: 65 63 74 69 6f 6e 20 68 6f 6c 64 69 6e 67 20 74  ection holding t
3ce0: 68 69 73 20 62 74 72 65 65 20 2a 2f 0a 20 20 42  his btree */.  B
3cf0: 74 53 68 61 72 65 64 20 2a 70 42 74 3b 20 20 20  tShared *pBt;   
3d00: 20 20 2f 2a 20 53 68 61 72 61 62 6c 65 20 63 6f    /* Sharable co
3d10: 6e 74 65 6e 74 20 6f 66 20 74 68 69 73 20 62 74  ntent of this bt
3d20: 72 65 65 20 2a 2f 0a 20 20 75 38 20 69 6e 54 72  ree */.  u8 inTr
3d30: 61 6e 73 3b 20 20 20 20 20 20 20 20 2f 2a 20 54  ans;        /* T
3d40: 52 41 4e 53 5f 4e 4f 4e 45 2c 20 54 52 41 4e 53  RANS_NONE, TRANS
3d50: 5f 52 45 41 44 20 6f 72 20 54 52 41 4e 53 5f 57  _READ or TRANS_W
3d60: 52 49 54 45 20 2a 2f 0a 20 20 75 38 20 73 68 61  RITE */.  u8 sha
3d70: 72 61 62 6c 65 3b 20 20 20 20 20 20 20 2f 2a 20  rable;       /* 
3d80: 54 72 75 65 20 69 66 20 77 65 20 63 61 6e 20 73  True if we can s
3d90: 68 61 72 65 20 70 42 74 20 77 69 74 68 20 61 6e  hare pBt with an
3da0: 6f 74 68 65 72 20 64 62 20 2a 2f 0a 20 20 75 38  other db */.  u8
3db0: 20 6c 6f 63 6b 65 64 3b 20 20 20 20 20 20 20 20   locked;        
3dc0: 20 2f 2a 20 54 72 75 65 20 69 66 20 64 62 20 63   /* True if db c
3dd0: 75 72 72 65 6e 74 6c 79 20 68 61 73 20 70 42 74  urrently has pBt
3de0: 20 6c 6f 63 6b 65 64 20 2a 2f 0a 20 20 69 6e 74   locked */.  int
3df0: 20 77 61 6e 74 54 6f 4c 6f 63 6b 3b 20 20 20 20   wantToLock;    
3e00: 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 6e 65 73  /* Number of nes
3e10: 74 65 64 20 63 61 6c 6c 73 20 74 6f 20 73 71 6c  ted calls to sql
3e20: 69 74 65 33 42 74 72 65 65 45 6e 74 65 72 28 29  ite3BtreeEnter()
3e30: 20 2a 2f 0a 20 20 69 6e 74 20 6e 42 61 63 6b 75   */.  int nBacku
3e40: 70 3b 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62  p;       /* Numb
3e50: 65 72 20 6f 66 20 62 61 63 6b 75 70 20 6f 70 65  er of backup ope
3e60: 72 61 74 69 6f 6e 73 20 72 65 61 64 69 6e 67 20  rations reading 
3e70: 74 68 69 73 20 62 74 72 65 65 20 2a 2f 0a 20 20  this btree */.  
3e80: 42 74 72 65 65 20 2a 70 4e 65 78 74 3b 20 20 20  Btree *pNext;   
3e90: 20 20 20 2f 2a 20 4c 69 73 74 20 6f 66 20 6f 74     /* List of ot
3ea0: 68 65 72 20 73 68 61 72 61 62 6c 65 20 42 74 72  her sharable Btr
3eb0: 65 65 73 20 66 72 6f 6d 20 74 68 65 20 73 61 6d  ees from the sam
3ec0: 65 20 64 62 20 2a 2f 0a 20 20 42 74 72 65 65 20  e db */.  Btree 
3ed0: 2a 70 50 72 65 76 3b 20 20 20 20 20 20 2f 2a 20  *pPrev;      /* 
3ee0: 42 61 63 6b 20 70 6f 69 6e 74 65 72 20 6f 66 20  Back pointer of 
3ef0: 74 68 65 20 73 61 6d 65 20 6c 69 73 74 20 2a 2f  the same list */
3f00: 0a 23 69 66 6e 64 65 66 20 53 51 4c 49 54 45 5f  .#ifndef SQLITE_
3f10: 4f 4d 49 54 5f 53 48 41 52 45 44 5f 43 41 43 48  OMIT_SHARED_CACH
3f20: 45 0a 20 20 42 74 4c 6f 63 6b 20 6c 6f 63 6b 3b  E.  BtLock lock;
3f30: 20 20 20 20 20 20 20 2f 2a 20 4f 62 6a 65 63 74         /* Object
3f40: 20 75 73 65 64 20 74 6f 20 6c 6f 63 6b 20 70 61   used to lock pa
3f50: 67 65 20 31 20 2a 2f 0a 23 65 6e 64 69 66 0a 7d  ge 1 */.#endif.}
3f60: 3b 0a 0a 2f 2a 0a 2a 2a 20 42 74 72 65 65 2e 69  ;../*.** Btree.i
3f70: 6e 54 72 61 6e 73 20 6d 61 79 20 74 61 6b 65 20  nTrans may take 
3f80: 6f 6e 65 20 6f 66 20 74 68 65 20 66 6f 6c 6c 6f  one of the follo
3f90: 77 69 6e 67 20 76 61 6c 75 65 73 2e 0a 2a 2a 0a  wing values..**.
3fa0: 2a 2a 20 49 66 20 74 68 65 20 73 68 61 72 65 64  ** If the shared
3fb0: 2d 64 61 74 61 20 65 78 74 65 6e 73 69 6f 6e 20  -data extension 
3fc0: 69 73 20 65 6e 61 62 6c 65 64 2c 20 74 68 65 72  is enabled, ther
3fd0: 65 20 6d 61 79 20 62 65 20 6d 75 6c 74 69 70 6c  e may be multipl
3fe0: 65 20 75 73 65 72 73 0a 2a 2a 20 6f 66 20 74 68  e users.** of th
3ff0: 65 20 42 74 72 65 65 20 73 74 72 75 63 74 75 72  e Btree structur
4000: 65 2e 20 41 74 20 6d 6f 73 74 20 6f 6e 65 20 6f  e. At most one o
4010: 66 20 74 68 65 73 65 20 6d 61 79 20 6f 70 65 6e  f these may open
4020: 20 61 20 77 72 69 74 65 20 74 72 61 6e 73 61 63   a write transac
4030: 74 69 6f 6e 2c 0a 2a 2a 20 62 75 74 20 61 6e 79  tion,.** but any
4040: 20 6e 75 6d 62 65 72 20 6d 61 79 20 68 61 76 65   number may have
4050: 20 61 63 74 69 76 65 20 72 65 61 64 20 74 72 61   active read tra
4060: 6e 73 61 63 74 69 6f 6e 73 2e 0a 2a 2f 0a 23 64  nsactions..*/.#d
4070: 65 66 69 6e 65 20 54 52 41 4e 53 5f 4e 4f 4e 45  efine TRANS_NONE
4080: 20 20 30 0a 23 64 65 66 69 6e 65 20 54 52 41 4e    0.#define TRAN
4090: 53 5f 52 45 41 44 20 20 31 0a 23 64 65 66 69 6e  S_READ  1.#defin
40a0: 65 20 54 52 41 4e 53 5f 57 52 49 54 45 20 32 0a  e TRANS_WRITE 2.
40b0: 0a 2f 2a 0a 2a 2a 20 41 6e 20 69 6e 73 74 61 6e  ./*.** An instan
40c0: 63 65 20 6f 66 20 74 68 69 73 20 6f 62 6a 65 63  ce of this objec
40d0: 74 20 72 65 70 72 65 73 65 6e 74 73 20 61 20 73  t represents a s
40e0: 69 6e 67 6c 65 20 64 61 74 61 62 61 73 65 20 66  ingle database f
40f0: 69 6c 65 2e 0a 2a 2a 20 0a 2a 2a 20 41 20 73 69  ile..** .** A si
4100: 6e 67 6c 65 20 64 61 74 61 62 61 73 65 20 66 69  ngle database fi
4110: 6c 65 20 63 61 6e 20 62 65 20 69 6e 20 75 73 65  le can be in use
4120: 20 61 73 20 74 68 65 20 73 61 6d 65 20 74 69 6d   as the same tim
4130: 65 20 62 79 20 74 77 6f 0a 2a 2a 20 6f 72 20 6d  e by two.** or m
4140: 6f 72 65 20 64 61 74 61 62 61 73 65 20 63 6f 6e  ore database con
4150: 6e 65 63 74 69 6f 6e 73 2e 20 20 57 68 65 6e 20  nections.  When 
4160: 74 77 6f 20 6f 72 20 6d 6f 72 65 20 63 6f 6e 6e  two or more conn
4170: 65 63 74 69 6f 6e 73 20 61 72 65 0a 2a 2a 20 73  ections are.** s
4180: 68 61 72 69 6e 67 20 74 68 65 20 73 61 6d 65 20  haring the same 
4190: 64 61 74 61 62 61 73 65 20 66 69 6c 65 2c 20 65  database file, e
41a0: 61 63 68 20 63 6f 6e 6e 65 63 74 69 6f 6e 20 68  ach connection h
41b0: 61 73 20 69 74 20 6f 77 6e 0a 2a 2a 20 70 72 69  as it own.** pri
41c0: 76 61 74 65 20 42 74 72 65 65 20 6f 62 6a 65 63  vate Btree objec
41d0: 74 20 66 6f 72 20 74 68 65 20 66 69 6c 65 20 61  t for the file a
41e0: 6e 64 20 65 61 63 68 20 6f 66 20 74 68 6f 73 65  nd each of those
41f0: 20 42 74 72 65 65 73 20 70 6f 69 6e 74 73 0a 2a   Btrees points.*
4200: 2a 20 74 6f 20 74 68 69 73 20 6f 6e 65 20 42 74  * to this one Bt
4210: 53 68 61 72 65 64 20 6f 62 6a 65 63 74 2e 20 20  Shared object.  
4220: 42 74 53 68 61 72 65 64 2e 6e 52 65 66 20 69 73  BtShared.nRef is
4230: 20 74 68 65 20 6e 75 6d 62 65 72 20 6f 66 0a 2a   the number of.*
4240: 2a 20 63 6f 6e 6e 65 63 74 69 6f 6e 73 20 63 75  * connections cu
4250: 72 72 65 6e 74 6c 79 20 73 68 61 72 69 6e 67 20  rrently sharing 
4260: 74 68 69 73 20 64 61 74 61 62 61 73 65 20 66 69  this database fi
4270: 6c 65 2e 0a 2a 2a 0a 2a 2a 20 46 69 65 6c 64 73  le..**.** Fields
4280: 20 69 6e 20 74 68 69 73 20 73 74 72 75 63 74 75   in this structu
4290: 72 65 20 61 72 65 20 61 63 63 65 73 73 65 64 20  re are accessed 
42a0: 75 6e 64 65 72 20 74 68 65 20 42 74 53 68 61 72  under the BtShar
42b0: 65 64 2e 6d 75 74 65 78 0a 2a 2a 20 6d 75 74 65  ed.mutex.** mute
42c0: 78 2c 20 65 78 63 65 70 74 20 66 6f 72 20 6e 52  x, except for nR
42d0: 65 66 20 61 6e 64 20 70 4e 65 78 74 20 77 68 69  ef and pNext whi
42e0: 63 68 20 61 72 65 20 61 63 63 65 73 73 65 64 20  ch are accessed 
42f0: 75 6e 64 65 72 20 74 68 65 0a 2a 2a 20 67 6c 6f  under the.** glo
4300: 62 61 6c 20 53 51 4c 49 54 45 5f 4d 55 54 45 58  bal SQLITE_MUTEX
4310: 5f 53 54 41 54 49 43 5f 4d 41 53 54 45 52 20 6d  _STATIC_MASTER m
4320: 75 74 65 78 2e 20 20 54 68 65 20 70 50 61 67 65  utex.  The pPage
4330: 72 20 66 69 65 6c 64 0a 2a 2a 20 6d 61 79 20 6e  r field.** may n
4340: 6f 74 20 62 65 20 6d 6f 64 69 66 69 65 64 20 6f  ot be modified o
4350: 6e 63 65 20 69 74 20 69 73 20 69 6e 69 74 69 61  nce it is initia
4360: 6c 6c 79 20 73 65 74 20 61 73 20 6c 6f 6e 67 20  lly set as long 
4370: 61 73 20 6e 52 65 66 3e 30 2e 0a 2a 2a 20 54 68  as nRef>0..** Th
4380: 65 20 70 53 63 68 65 6d 61 20 66 69 65 6c 64 20  e pSchema field 
4390: 6d 61 79 20 62 65 20 73 65 74 20 6f 6e 63 65 20  may be set once 
43a0: 75 6e 64 65 72 20 42 74 53 68 61 72 65 64 2e 6d  under BtShared.m
43b0: 75 74 65 78 20 61 6e 64 0a 2a 2a 20 74 68 65 72  utex and.** ther
43c0: 65 61 66 74 65 72 20 69 73 20 75 6e 63 68 61 6e  eafter is unchan
43d0: 67 65 64 20 61 73 20 6c 6f 6e 67 20 61 73 20 6e  ged as long as n
43e0: 52 65 66 3e 30 2e 0a 2a 2a 0a 2a 2a 20 69 73 50  Ref>0..**.** isP
43f0: 65 6e 64 69 6e 67 3a 0a 2a 2a 0a 2a 2a 20 20 20  ending:.**.**   
4400: 49 66 20 61 20 42 74 53 68 61 72 65 64 20 63 6c  If a BtShared cl
4410: 69 65 6e 74 20 66 61 69 6c 73 20 74 6f 20 6f 62  ient fails to ob
4420: 74 61 69 6e 20 61 20 77 72 69 74 65 2d 6c 6f 63  tain a write-loc
4430: 6b 20 6f 6e 20 61 20 64 61 74 61 62 61 73 65 0a  k on a database.
4440: 2a 2a 20 20 20 74 61 62 6c 65 20 28 62 65 63 61  **   table (beca
4450: 75 73 65 20 74 68 65 72 65 20 65 78 69 73 74 73  use there exists
4460: 20 6f 6e 65 20 6f 72 20 6d 6f 72 65 20 72 65 61   one or more rea
4470: 64 2d 6c 6f 63 6b 73 20 6f 6e 20 74 68 65 20 74  d-locks on the t
4480: 61 62 6c 65 29 2c 0a 2a 2a 20 20 20 74 68 65 20  able),.**   the 
4490: 73 68 61 72 65 64 2d 63 61 63 68 65 20 65 6e 74  shared-cache ent
44a0: 65 72 73 20 27 70 65 6e 64 69 6e 67 2d 6c 6f 63  ers 'pending-loc
44b0: 6b 27 20 73 74 61 74 65 20 61 6e 64 20 69 73 50  k' state and isP
44c0: 65 6e 64 69 6e 67 20 69 73 0a 2a 2a 20 20 20 73  ending is.**   s
44d0: 65 74 20 74 6f 20 74 72 75 65 2e 0a 2a 2a 0a 2a  et to true..**.*
44e0: 2a 20 20 20 54 68 65 20 73 68 61 72 65 64 2d 63  *   The shared-c
44f0: 61 63 68 65 20 6c 65 61 76 65 73 20 74 68 65 20  ache leaves the 
4500: 27 70 65 6e 64 69 6e 67 20 6c 6f 63 6b 27 20 73  'pending lock' s
4510: 74 61 74 65 20 77 68 65 6e 20 65 69 74 68 65 72  tate when either
4520: 20 6f 66 0a 2a 2a 20 20 20 74 68 65 20 66 6f 6c   of.**   the fol
4530: 6c 6f 77 69 6e 67 20 6f 63 63 75 72 3a 0a 2a 2a  lowing occur:.**
4540: 0a 2a 2a 20 20 20 20 20 31 29 20 54 68 65 20 63  .**     1) The c
4550: 75 72 72 65 6e 74 20 77 72 69 74 65 72 20 28 42  urrent writer (B
4560: 74 53 68 61 72 65 64 2e 70 57 72 69 74 65 72 29  tShared.pWriter)
4570: 20 63 6f 6e 63 6c 75 64 65 73 20 69 74 73 20 74   concludes its t
4580: 72 61 6e 73 61 63 74 69 6f 6e 2c 20 4f 52 0a 2a  ransaction, OR.*
4590: 2a 20 20 20 20 20 32 29 20 54 68 65 20 6e 75 6d  *     2) The num
45a0: 62 65 72 20 6f 66 20 6c 6f 63 6b 73 20 68 65 6c  ber of locks hel
45b0: 64 20 62 79 20 6f 74 68 65 72 20 63 6f 6e 6e 65  d by other conne
45c0: 63 74 69 6f 6e 73 20 64 72 6f 70 73 20 74 6f 20  ctions drops to 
45d0: 7a 65 72 6f 2e 0a 2a 2a 0a 2a 2a 20 20 20 77 68  zero..**.**   wh
45e0: 69 6c 65 20 69 6e 20 74 68 65 20 27 70 65 6e 64  ile in the 'pend
45f0: 69 6e 67 2d 6c 6f 63 6b 27 20 73 74 61 74 65 2c  ing-lock' state,
4600: 20 6e 6f 20 63 6f 6e 6e 65 63 74 69 6f 6e 20 6d   no connection m
4610: 61 79 20 73 74 61 72 74 20 61 20 6e 65 77 0a 2a  ay start a new.*
4620: 2a 20 20 20 74 72 61 6e 73 61 63 74 69 6f 6e 2e  *   transaction.
4630: 0a 2a 2a 0a 2a 2a 20 20 20 54 68 69 73 20 66 65  .**.**   This fe
4640: 61 74 75 72 65 20 69 73 20 69 6e 63 6c 75 64 65  ature is include
4650: 64 20 74 6f 20 68 65 6c 70 20 70 72 65 76 65 6e  d to help preven
4660: 74 20 77 72 69 74 65 72 2d 73 74 61 72 76 61 74  t writer-starvat
4670: 69 6f 6e 2e 0a 2a 2f 0a 73 74 72 75 63 74 20 42  ion..*/.struct B
4680: 74 53 68 61 72 65 64 20 7b 0a 20 20 50 61 67 65  tShared {.  Page
4690: 72 20 2a 70 50 61 67 65 72 3b 20 20 20 20 20 20  r *pPager;      
46a0: 20 20 2f 2a 20 54 68 65 20 70 61 67 65 20 63 61    /* The page ca
46b0: 63 68 65 20 2a 2f 0a 20 20 73 71 6c 69 74 65 33  che */.  sqlite3
46c0: 20 2a 64 62 3b 20 20 20 20 20 20 20 20 20 20 2f   *db;          /
46d0: 2a 20 44 61 74 61 62 61 73 65 20 63 6f 6e 6e 65  * Database conne
46e0: 63 74 69 6f 6e 20 63 75 72 72 65 6e 74 6c 79 20  ction currently 
46f0: 75 73 69 6e 67 20 74 68 69 73 20 42 74 72 65 65  using this Btree
4700: 20 2a 2f 0a 20 20 42 74 43 75 72 73 6f 72 20 2a   */.  BtCursor *
4710: 70 43 75 72 73 6f 72 3b 20 20 20 20 2f 2a 20 41  pCursor;    /* A
4720: 20 6c 69 73 74 20 6f 66 20 61 6c 6c 20 6f 70 65   list of all ope
4730: 6e 20 63 75 72 73 6f 72 73 20 2a 2f 0a 20 20 4d  n cursors */.  M
4740: 65 6d 50 61 67 65 20 2a 70 50 61 67 65 31 3b 20  emPage *pPage1; 
4750: 20 20 20 20 20 2f 2a 20 46 69 72 73 74 20 70 61       /* First pa
4760: 67 65 20 6f 66 20 74 68 65 20 64 61 74 61 62 61  ge of the databa
4770: 73 65 20 2a 2f 0a 20 20 75 38 20 72 65 61 64 4f  se */.  u8 readO
4780: 6e 6c 79 3b 20 20 20 20 20 20 20 20 20 20 2f 2a  nly;          /*
4790: 20 54 72 75 65 20 69 66 20 74 68 65 20 75 6e 64   True if the und
47a0: 65 72 6c 79 69 6e 67 20 66 69 6c 65 20 69 73 20  erlying file is 
47b0: 72 65 61 64 6f 6e 6c 79 20 2a 2f 0a 20 20 75 38  readonly */.  u8
47c0: 20 70 61 67 65 53 69 7a 65 46 69 78 65 64 3b 20   pageSizeFixed; 
47d0: 20 20 20 20 2f 2a 20 54 72 75 65 20 69 66 20 74      /* True if t
47e0: 68 65 20 70 61 67 65 20 73 69 7a 65 20 63 61 6e  he page size can
47f0: 20 6e 6f 20 6c 6f 6e 67 65 72 20 62 65 20 63 68   no longer be ch
4800: 61 6e 67 65 64 20 2a 2f 0a 20 20 75 38 20 73 65  anged */.  u8 se
4810: 63 75 72 65 44 65 6c 65 74 65 3b 20 20 20 20 20  cureDelete;     
4820: 20 2f 2a 20 54 72 75 65 20 69 66 20 73 65 63 75   /* True if secu
4830: 72 65 5f 64 65 6c 65 74 65 20 69 73 20 65 6e 61  re_delete is ena
4840: 62 6c 65 64 20 2a 2f 0a 20 20 75 38 20 69 6e 69  bled */.  u8 ini
4850: 74 69 61 6c 6c 79 45 6d 70 74 79 3b 20 20 20 20  tiallyEmpty;    
4860: 2f 2a 20 44 61 74 61 62 61 73 65 20 69 73 20 65  /* Database is e
4870: 6d 70 74 79 20 61 74 20 73 74 61 72 74 20 6f 66  mpty at start of
4880: 20 74 72 61 6e 73 61 63 74 69 6f 6e 20 2a 2f 0a   transaction */.
4890: 20 20 75 38 20 6f 70 65 6e 46 6c 61 67 73 3b 20    u8 openFlags; 
48a0: 20 20 20 20 20 20 20 20 2f 2a 20 46 6c 61 67 73          /* Flags
48b0: 20 74 6f 20 73 71 6c 69 74 65 33 42 74 72 65 65   to sqlite3Btree
48c0: 4f 70 65 6e 28 29 20 2a 2f 0a 23 69 66 6e 64 65  Open() */.#ifnde
48d0: 66 20 53 51 4c 49 54 45 5f 4f 4d 49 54 5f 41 55  f SQLITE_OMIT_AU
48e0: 54 4f 56 41 43 55 55 4d 0a 20 20 75 38 20 61 75  TOVACUUM.  u8 au
48f0: 74 6f 56 61 63 75 75 6d 3b 20 20 20 20 20 20 20  toVacuum;       
4900: 20 2f 2a 20 54 72 75 65 20 69 66 20 61 75 74 6f   /* True if auto
4910: 2d 76 61 63 75 75 6d 20 69 73 20 65 6e 61 62 6c  -vacuum is enabl
4920: 65 64 20 2a 2f 0a 20 20 75 38 20 69 6e 63 72 56  ed */.  u8 incrV
4930: 61 63 75 75 6d 3b 20 20 20 20 20 20 20 20 2f 2a  acuum;        /*
4940: 20 54 72 75 65 20 69 66 20 69 6e 63 72 2d 76 61   True if incr-va
4950: 63 75 75 6d 20 69 73 20 65 6e 61 62 6c 65 64 20  cuum is enabled 
4960: 2a 2f 0a 23 65 6e 64 69 66 0a 20 20 75 38 20 69  */.#endif.  u8 i
4970: 6e 54 72 61 6e 73 61 63 74 69 6f 6e 3b 20 20 20  nTransaction;   
4980: 20 20 2f 2a 20 54 72 61 6e 73 61 63 74 69 6f 6e    /* Transaction
4990: 20 73 74 61 74 65 20 2a 2f 0a 20 20 75 38 20 64   state */.  u8 d
49a0: 6f 4e 6f 74 55 73 65 57 41 4c 3b 20 20 20 20 20  oNotUseWAL;     
49b0: 20 20 2f 2a 20 49 66 20 74 72 75 65 2c 20 64 6f    /* If true, do
49c0: 20 6e 6f 74 20 6f 70 65 6e 20 77 72 69 74 65 2d   not open write-
49d0: 61 68 65 61 64 2d 6c 6f 67 20 66 69 6c 65 20 2a  ahead-log file *
49e0: 2f 0a 20 20 75 31 36 20 6d 61 78 4c 6f 63 61 6c  /.  u16 maxLocal
49f0: 3b 20 20 20 20 20 20 20 20 20 2f 2a 20 4d 61 78  ;         /* Max
4a00: 69 6d 75 6d 20 6c 6f 63 61 6c 20 70 61 79 6c 6f  imum local paylo
4a10: 61 64 20 69 6e 20 6e 6f 6e 2d 4c 45 41 46 44 41  ad in non-LEAFDA
4a20: 54 41 20 74 61 62 6c 65 73 20 2a 2f 0a 20 20 75  TA tables */.  u
4a30: 31 36 20 6d 69 6e 4c 6f 63 61 6c 3b 20 20 20 20  16 minLocal;    
4a40: 20 20 20 20 20 2f 2a 20 4d 69 6e 69 6d 75 6d 20       /* Minimum 
4a50: 6c 6f 63 61 6c 20 70 61 79 6c 6f 61 64 20 69 6e  local payload in
4a60: 20 6e 6f 6e 2d 4c 45 41 46 44 41 54 41 20 74 61   non-LEAFDATA ta
4a70: 62 6c 65 73 20 2a 2f 0a 20 20 75 31 36 20 6d 61  bles */.  u16 ma
4a80: 78 4c 65 61 66 3b 20 20 20 20 20 20 20 20 20 20  xLeaf;          
4a90: 2f 2a 20 4d 61 78 69 6d 75 6d 20 6c 6f 63 61 6c  /* Maximum local
4aa0: 20 70 61 79 6c 6f 61 64 20 69 6e 20 61 20 4c 45   payload in a LE
4ab0: 41 46 44 41 54 41 20 74 61 62 6c 65 20 2a 2f 0a  AFDATA table */.
4ac0: 20 20 75 31 36 20 6d 69 6e 4c 65 61 66 3b 20 20    u16 minLeaf;  
4ad0: 20 20 20 20 20 20 20 20 2f 2a 20 4d 69 6e 69 6d          /* Minim
4ae0: 75 6d 20 6c 6f 63 61 6c 20 70 61 79 6c 6f 61 64  um local payload
4af0: 20 69 6e 20 61 20 4c 45 41 46 44 41 54 41 20 74   in a LEAFDATA t
4b00: 61 62 6c 65 20 2a 2f 0a 20 20 75 33 32 20 70 61  able */.  u32 pa
4b10: 67 65 53 69 7a 65 3b 20 20 20 20 20 20 20 20 20  geSize;         
4b20: 2f 2a 20 54 6f 74 61 6c 20 6e 75 6d 62 65 72 20  /* Total number 
4b30: 6f 66 20 62 79 74 65 73 20 6f 6e 20 61 20 70 61  of bytes on a pa
4b40: 67 65 20 2a 2f 0a 20 20 75 33 32 20 75 73 61 62  ge */.  u32 usab
4b50: 6c 65 53 69 7a 65 3b 20 20 20 20 20 20 20 2f 2a  leSize;       /*
4b60: 20 4e 75 6d 62 65 72 20 6f 66 20 75 73 61 62 6c   Number of usabl
4b70: 65 20 62 79 74 65 73 20 6f 6e 20 65 61 63 68 20  e bytes on each 
4b80: 70 61 67 65 20 2a 2f 0a 20 20 69 6e 74 20 6e 54  page */.  int nT
4b90: 72 61 6e 73 61 63 74 69 6f 6e 3b 20 20 20 20 20  ransaction;     
4ba0: 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 6f 70 65  /* Number of ope
4bb0: 6e 20 74 72 61 6e 73 61 63 74 69 6f 6e 73 20 28  n transactions (
4bc0: 72 65 61 64 20 2b 20 77 72 69 74 65 29 20 2a 2f  read + write) */
4bd0: 0a 20 20 75 33 32 20 6e 50 61 67 65 3b 20 20 20  .  u32 nPage;   
4be0: 20 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62           /* Numb
4bf0: 65 72 20 6f 66 20 70 61 67 65 73 20 69 6e 20 74  er of pages in t
4c00: 68 65 20 64 61 74 61 62 61 73 65 20 2a 2f 0a 20  he database */. 
4c10: 20 76 6f 69 64 20 2a 70 53 63 68 65 6d 61 3b 20   void *pSchema; 
4c20: 20 20 20 20 20 20 20 2f 2a 20 50 6f 69 6e 74 65         /* Pointe
4c30: 72 20 74 6f 20 73 70 61 63 65 20 61 6c 6c 6f 63  r to space alloc
4c40: 61 74 65 64 20 62 79 20 73 71 6c 69 74 65 33 42  ated by sqlite3B
4c50: 74 72 65 65 53 63 68 65 6d 61 28 29 20 2a 2f 0a  treeSchema() */.
4c60: 20 20 76 6f 69 64 20 28 2a 78 46 72 65 65 53 63    void (*xFreeSc
4c70: 68 65 6d 61 29 28 76 6f 69 64 2a 29 3b 20 20 2f  hema)(void*);  /
4c80: 2a 20 44 65 73 74 72 75 63 74 6f 72 20 66 6f 72  * Destructor for
4c90: 20 42 74 53 68 61 72 65 64 2e 70 53 63 68 65 6d   BtShared.pSchem
4ca0: 61 20 2a 2f 0a 20 20 73 71 6c 69 74 65 33 5f 6d  a */.  sqlite3_m
4cb0: 75 74 65 78 20 2a 6d 75 74 65 78 3b 20 2f 2a 20  utex *mutex; /* 
4cc0: 4e 6f 6e 2d 72 65 63 75 72 73 69 76 65 20 6d 75  Non-recursive mu
4cd0: 74 65 78 20 72 65 71 75 69 72 65 64 20 74 6f 20  tex required to 
4ce0: 61 63 63 65 73 73 20 74 68 69 73 20 6f 62 6a 65  access this obje
4cf0: 63 74 20 2a 2f 0a 20 20 42 69 74 76 65 63 20 2a  ct */.  Bitvec *
4d00: 70 48 61 73 43 6f 6e 74 65 6e 74 3b 20 20 2f 2a  pHasContent;  /*
4d10: 20 53 65 74 20 6f 66 20 70 61 67 65 73 20 6d 6f   Set of pages mo
4d20: 76 65 64 20 74 6f 20 66 72 65 65 2d 6c 69 73 74  ved to free-list
4d30: 20 74 68 69 73 20 74 72 61 6e 73 61 63 74 69 6f   this transactio
4d40: 6e 20 2a 2f 0a 23 69 66 6e 64 65 66 20 53 51 4c  n */.#ifndef SQL
4d50: 49 54 45 5f 4f 4d 49 54 5f 53 48 41 52 45 44 5f  ITE_OMIT_SHARED_
4d60: 43 41 43 48 45 0a 20 20 69 6e 74 20 6e 52 65 66  CACHE.  int nRef
4d70: 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a  ;             /*
4d80: 20 4e 75 6d 62 65 72 20 6f 66 20 72 65 66 65 72   Number of refer
4d90: 65 6e 63 65 73 20 74 6f 20 74 68 69 73 20 73 74  ences to this st
4da0: 72 75 63 74 75 72 65 20 2a 2f 0a 20 20 42 74 53  ructure */.  BtS
4db0: 68 61 72 65 64 20 2a 70 4e 65 78 74 3b 20 20 20  hared *pNext;   
4dc0: 20 20 20 2f 2a 20 4e 65 78 74 20 6f 6e 20 61 20     /* Next on a 
4dd0: 6c 69 73 74 20 6f 66 20 73 68 61 72 61 62 6c 65  list of sharable
4de0: 20 42 74 53 68 61 72 65 64 20 73 74 72 75 63 74   BtShared struct
4df0: 73 20 2a 2f 0a 20 20 42 74 4c 6f 63 6b 20 2a 70  s */.  BtLock *p
4e00: 4c 6f 63 6b 3b 20 20 20 20 20 20 20 20 2f 2a 20  Lock;        /* 
4e10: 4c 69 73 74 20 6f 66 20 6c 6f 63 6b 73 20 68 65  List of locks he
4e20: 6c 64 20 6f 6e 20 74 68 69 73 20 73 68 61 72 65  ld on this share
4e30: 64 2d 62 74 72 65 65 20 73 74 72 75 63 74 20 2a  d-btree struct *
4e40: 2f 0a 20 20 42 74 72 65 65 20 2a 70 57 72 69 74  /.  Btree *pWrit
4e50: 65 72 3b 20 20 20 20 20 20 20 2f 2a 20 42 74 72  er;       /* Btr
4e60: 65 65 20 77 69 74 68 20 63 75 72 72 65 6e 74 6c  ee with currentl
4e70: 79 20 6f 70 65 6e 20 77 72 69 74 65 20 74 72 61  y open write tra
4e80: 6e 73 61 63 74 69 6f 6e 20 2a 2f 0a 20 20 75 38  nsaction */.  u8
4e90: 20 69 73 45 78 63 6c 75 73 69 76 65 3b 20 20 20   isExclusive;   
4ea0: 20 20 20 20 2f 2a 20 54 72 75 65 20 69 66 20 70      /* True if p
4eb0: 57 72 69 74 65 72 20 68 61 73 20 61 6e 20 45 58  Writer has an EX
4ec0: 43 4c 55 53 49 56 45 20 6c 6f 63 6b 20 6f 6e 20  CLUSIVE lock on 
4ed0: 74 68 65 20 64 62 20 2a 2f 0a 20 20 75 38 20 69  the db */.  u8 i
4ee0: 73 50 65 6e 64 69 6e 67 3b 20 20 20 20 20 20 20  sPending;       
4ef0: 20 20 2f 2a 20 49 66 20 77 61 69 74 69 6e 67 20    /* If waiting 
4f00: 66 6f 72 20 72 65 61 64 2d 6c 6f 63 6b 73 20 74  for read-locks t
4f10: 6f 20 63 6c 65 61 72 20 2a 2f 0a 20 20 75 31 36  o clear */.  u16
4f20: 20 69 4d 75 74 65 78 43 6f 75 6e 74 65 72 3b 20   iMutexCounter; 
4f30: 20 20 20 2f 2a 20 54 68 65 20 6e 75 6d 62 65 72     /* The number
4f40: 20 6f 66 20 6d 75 74 65 78 5f 6c 65 61 76 65 28   of mutex_leave(
4f50: 6d 75 74 65 78 29 20 63 61 6c 6c 73 20 2a 2f 0a  mutex) calls */.
4f60: 23 65 6e 64 69 66 0a 20 20 75 38 20 2a 70 54 6d  #endif.  u8 *pTm
4f70: 70 53 70 61 63 65 3b 20 20 20 20 20 20 20 20 2f  pSpace;        /
4f80: 2a 20 42 74 53 68 61 72 65 64 2e 70 61 67 65 53  * BtShared.pageS
4f90: 69 7a 65 20 62 79 74 65 73 20 6f 66 20 73 70 61  ize bytes of spa
4fa0: 63 65 20 66 6f 72 20 74 6d 70 20 75 73 65 20 2a  ce for tmp use *
4fb0: 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 41 6e 20 69  /.};../*.** An i
4fc0: 6e 73 74 61 6e 63 65 20 6f 66 20 74 68 65 20 66  nstance of the f
4fd0: 6f 6c 6c 6f 77 69 6e 67 20 73 74 72 75 63 74 75  ollowing structu
4fe0: 72 65 20 69 73 20 75 73 65 64 20 74 6f 20 68 6f  re is used to ho
4ff0: 6c 64 20 69 6e 66 6f 72 6d 61 74 69 6f 6e 0a 2a  ld information.*
5000: 2a 20 61 62 6f 75 74 20 61 20 63 65 6c 6c 2e 20  * about a cell. 
5010: 20 54 68 65 20 70 61 72 73 65 43 65 6c 6c 50 74   The parseCellPt
5020: 72 28 29 20 66 75 6e 63 74 69 6f 6e 20 66 69 6c  r() function fil
5030: 6c 73 20 69 6e 20 74 68 69 73 20 73 74 72 75 63  ls in this struc
5040: 74 75 72 65 0a 2a 2a 20 62 61 73 65 64 20 6f 6e  ture.** based on
5050: 20 69 6e 66 6f 72 6d 61 74 69 6f 6e 20 65 78 74   information ext
5060: 72 61 63 74 20 66 72 6f 6d 20 74 68 65 20 72 61  ract from the ra
5070: 77 20 64 69 73 6b 20 70 61 67 65 2e 0a 2a 2f 0a  w disk page..*/.
5080: 74 79 70 65 64 65 66 20 73 74 72 75 63 74 20 43  typedef struct C
5090: 65 6c 6c 49 6e 66 6f 20 43 65 6c 6c 49 6e 66 6f  ellInfo CellInfo
50a0: 3b 0a 73 74 72 75 63 74 20 43 65 6c 6c 49 6e 66  ;.struct CellInf
50b0: 6f 20 7b 0a 20 20 69 36 34 20 6e 4b 65 79 3b 20  o {.  i64 nKey; 
50c0: 20 20 20 20 20 2f 2a 20 54 68 65 20 6b 65 79 20       /* The key 
50d0: 66 6f 72 20 49 4e 54 4b 45 59 20 74 61 62 6c 65  for INTKEY table
50e0: 73 2c 20 6f 72 20 6e 75 6d 62 65 72 20 6f 66 20  s, or number of 
50f0: 62 79 74 65 73 20 69 6e 20 6b 65 79 20 2a 2f 0a  bytes in key */.
5100: 20 20 75 38 20 2a 70 43 65 6c 6c 3b 20 20 20 20    u8 *pCell;    
5110: 20 2f 2a 20 50 6f 69 6e 74 65 72 20 74 6f 20 74   /* Pointer to t
5120: 68 65 20 73 74 61 72 74 20 6f 66 20 63 65 6c 6c  he start of cell
5130: 20 63 6f 6e 74 65 6e 74 20 2a 2f 0a 20 20 75 33   content */.  u3
5140: 32 20 6e 44 61 74 61 3b 20 20 20 20 20 2f 2a 20  2 nData;     /* 
5150: 4e 75 6d 62 65 72 20 6f 66 20 62 79 74 65 73 20  Number of bytes 
5160: 6f 66 20 64 61 74 61 20 2a 2f 0a 20 20 75 33 32  of data */.  u32
5170: 20 6e 50 61 79 6c 6f 61 64 3b 20 20 2f 2a 20 54   nPayload;  /* T
5180: 6f 74 61 6c 20 61 6d 6f 75 6e 74 20 6f 66 20 70  otal amount of p
5190: 61 79 6c 6f 61 64 20 2a 2f 0a 20 20 75 31 36 20  ayload */.  u16 
51a0: 6e 48 65 61 64 65 72 3b 20 20 20 2f 2a 20 53 69  nHeader;   /* Si
51b0: 7a 65 20 6f 66 20 74 68 65 20 63 65 6c 6c 20 63  ze of the cell c
51c0: 6f 6e 74 65 6e 74 20 68 65 61 64 65 72 20 69 6e  ontent header in
51d0: 20 62 79 74 65 73 20 2a 2f 0a 20 20 75 31 36 20   bytes */.  u16 
51e0: 6e 4c 6f 63 61 6c 3b 20 20 20 20 2f 2a 20 41 6d  nLocal;    /* Am
51f0: 6f 75 6e 74 20 6f 66 20 70 61 79 6c 6f 61 64 20  ount of payload 
5200: 68 65 6c 64 20 6c 6f 63 61 6c 6c 79 20 2a 2f 0a  held locally */.
5210: 20 20 75 31 36 20 69 4f 76 65 72 66 6c 6f 77 3b    u16 iOverflow;
5220: 20 2f 2a 20 4f 66 66 73 65 74 20 74 6f 20 6f 76   /* Offset to ov
5230: 65 72 66 6c 6f 77 20 70 61 67 65 20 6e 75 6d 62  erflow page numb
5240: 65 72 2e 20 20 5a 65 72 6f 20 69 66 20 6e 6f 20  er.  Zero if no 
5250: 6f 76 65 72 66 6c 6f 77 20 2a 2f 0a 20 20 75 31  overflow */.  u1
5260: 36 20 6e 53 69 7a 65 3b 20 20 20 20 20 2f 2a 20  6 nSize;     /* 
5270: 53 69 7a 65 20 6f 66 20 74 68 65 20 63 65 6c 6c  Size of the cell
5280: 20 63 6f 6e 74 65 6e 74 20 6f 6e 20 74 68 65 20   content on the 
5290: 6d 61 69 6e 20 62 2d 74 72 65 65 20 70 61 67 65  main b-tree page
52a0: 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 4d 61   */.};../*.** Ma
52b0: 78 69 6d 75 6d 20 64 65 70 74 68 20 6f 66 20 61  ximum depth of a
52c0: 6e 20 53 51 4c 69 74 65 20 42 2d 54 72 65 65 20  n SQLite B-Tree 
52d0: 73 74 72 75 63 74 75 72 65 2e 20 41 6e 79 20 42  structure. Any B
52e0: 2d 54 72 65 65 20 64 65 65 70 65 72 20 74 68 61  -Tree deeper tha
52f0: 6e 0a 2a 2a 20 74 68 69 73 20 77 69 6c 6c 20 62  n.** this will b
5300: 65 20 64 65 63 6c 61 72 65 64 20 63 6f 72 72 75  e declared corru
5310: 70 74 2e 20 54 68 69 73 20 76 61 6c 75 65 20 69  pt. This value i
5320: 73 20 63 61 6c 63 75 6c 61 74 65 64 20 62 61 73  s calculated bas
5330: 65 64 20 6f 6e 20 61 0a 2a 2a 20 6d 61 78 69 6d  ed on a.** maxim
5340: 75 6d 20 64 61 74 61 62 61 73 65 20 73 69 7a 65  um database size
5350: 20 6f 66 20 32 5e 33 31 20 70 61 67 65 73 20 61   of 2^31 pages a
5360: 20 6d 69 6e 69 6d 75 6d 20 66 61 6e 6f 75 74 20   minimum fanout 
5370: 6f 66 20 32 20 66 6f 72 20 61 0a 2a 2a 20 72 6f  of 2 for a.** ro
5380: 6f 74 2d 6e 6f 64 65 20 61 6e 64 20 33 20 66 6f  ot-node and 3 fo
5390: 72 20 61 6c 6c 20 6f 74 68 65 72 20 69 6e 74 65  r all other inte
53a0: 72 6e 61 6c 20 6e 6f 64 65 73 2e 0a 2a 2a 0a 2a  rnal nodes..**.*
53b0: 2a 20 49 66 20 61 20 74 72 65 65 20 74 68 61 74  * If a tree that
53c0: 20 61 70 70 65 61 72 73 20 74 6f 20 62 65 20 74   appears to be t
53d0: 61 6c 6c 65 72 20 74 68 61 6e 20 74 68 69 73 20  aller than this 
53e0: 69 73 20 65 6e 63 6f 75 6e 74 65 72 65 64 2c 20  is encountered, 
53f0: 69 74 20 69 73 0a 2a 2a 20 61 73 73 75 6d 65 64  it is.** assumed
5400: 20 74 68 61 74 20 74 68 65 20 64 61 74 61 62 61   that the databa
5410: 73 65 20 69 73 20 63 6f 72 72 75 70 74 2e 0a 2a  se is corrupt..*
5420: 2f 0a 23 64 65 66 69 6e 65 20 42 54 43 55 52 53  /.#define BTCURS
5430: 4f 52 5f 4d 41 58 5f 44 45 50 54 48 20 32 30 0a  OR_MAX_DEPTH 20.
5440: 0a 2f 2a 0a 2a 2a 20 41 20 63 75 72 73 6f 72 20  ./*.** A cursor 
5450: 69 73 20 61 20 70 6f 69 6e 74 65 72 20 74 6f 20  is a pointer to 
5460: 61 20 70 61 72 74 69 63 75 6c 61 72 20 65 6e 74  a particular ent
5470: 72 79 20 77 69 74 68 69 6e 20 61 20 70 61 72 74  ry within a part
5480: 69 63 75 6c 61 72 0a 2a 2a 20 62 2d 74 72 65 65  icular.** b-tree
5490: 20 77 69 74 68 69 6e 20 61 20 64 61 74 61 62 61   within a databa
54a0: 73 65 20 66 69 6c 65 2e 0a 2a 2a 0a 2a 2a 20 54  se file..**.** T
54b0: 68 65 20 65 6e 74 72 79 20 69 73 20 69 64 65 6e  he entry is iden
54c0: 74 69 66 69 65 64 20 62 79 20 69 74 73 20 4d 65  tified by its Me
54d0: 6d 50 61 67 65 20 61 6e 64 20 74 68 65 20 69 6e  mPage and the in
54e0: 64 65 78 20 69 6e 0a 2a 2a 20 4d 65 6d 50 61 67  dex in.** MemPag
54f0: 65 2e 61 43 65 6c 6c 5b 5d 20 6f 66 20 74 68 65  e.aCell[] of the
5500: 20 65 6e 74 72 79 2e 0a 2a 2a 0a 2a 2a 20 41 20   entry..**.** A 
5510: 73 69 6e 67 6c 65 20 64 61 74 61 62 61 73 65 20  single database 
5520: 66 69 6c 65 20 63 61 6e 20 73 68 61 72 65 64 20  file can shared 
5530: 62 79 20 74 77 6f 20 6d 6f 72 65 20 64 61 74 61  by two more data
5540: 62 61 73 65 20 63 6f 6e 6e 65 63 74 69 6f 6e 73  base connections
5550: 2c 0a 2a 2a 20 62 75 74 20 63 75 72 73 6f 72 73  ,.** but cursors
5560: 20 63 61 6e 6e 6f 74 20 62 65 20 73 68 61 72 65   cannot be share
5570: 64 2e 20 20 45 61 63 68 20 63 75 72 73 6f 72 20  d.  Each cursor 
5580: 69 73 20 61 73 73 6f 63 69 61 74 65 64 20 77 69  is associated wi
5590: 74 68 20 61 0a 2a 2a 20 70 61 72 74 69 63 75 6c  th a.** particul
55a0: 61 72 20 64 61 74 61 62 61 73 65 20 63 6f 6e 6e  ar database conn
55b0: 65 63 74 69 6f 6e 20 69 64 65 6e 74 69 66 69 65  ection identifie
55c0: 64 20 42 74 43 75 72 73 6f 72 2e 70 42 74 72 65  d BtCursor.pBtre
55d0: 65 2e 64 62 2e 0a 2a 2a 0a 2a 2a 20 46 69 65 6c  e.db..**.** Fiel
55e0: 64 73 20 69 6e 20 74 68 69 73 20 73 74 72 75 63  ds in this struc
55f0: 74 75 72 65 20 61 72 65 20 61 63 63 65 73 73 65  ture are accesse
5600: 64 20 75 6e 64 65 72 20 74 68 65 20 42 74 53 68  d under the BtSh
5610: 61 72 65 64 2e 6d 75 74 65 78 0a 2a 2a 20 66 6f  ared.mutex.** fo
5620: 75 6e 64 20 61 74 20 73 65 6c 66 2d 3e 70 42 74  und at self->pBt
5630: 2d 3e 6d 75 74 65 78 2e 20 0a 2a 2f 0a 73 74 72  ->mutex. .*/.str
5640: 75 63 74 20 42 74 43 75 72 73 6f 72 20 7b 0a 20  uct BtCursor {. 
5650: 20 42 74 72 65 65 20 2a 70 42 74 72 65 65 3b 20   Btree *pBtree; 
5660: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 54 68             /* Th
5670: 65 20 42 74 72 65 65 20 74 6f 20 77 68 69 63 68  e Btree to which
5680: 20 74 68 69 73 20 63 75 72 73 6f 72 20 62 65 6c   this cursor bel
5690: 6f 6e 67 73 20 2a 2f 0a 20 20 42 74 53 68 61 72  ongs */.  BtShar
56a0: 65 64 20 2a 70 42 74 3b 20 20 20 20 20 20 20 20  ed *pBt;        
56b0: 20 20 20 20 2f 2a 20 54 68 65 20 42 74 53 68 61      /* The BtSha
56c0: 72 65 64 20 74 68 69 73 20 63 75 72 73 6f 72 20  red this cursor 
56d0: 70 6f 69 6e 74 73 20 74 6f 20 2a 2f 0a 20 20 42  points to */.  B
56e0: 74 43 75 72 73 6f 72 20 2a 70 4e 65 78 74 2c 20  tCursor *pNext, 
56f0: 2a 70 50 72 65 76 3b 20 20 2f 2a 20 46 6f 72 6d  *pPrev;  /* Form
5700: 73 20 61 20 6c 69 6e 6b 65 64 20 6c 69 73 74 20  s a linked list 
5710: 6f 66 20 61 6c 6c 20 63 75 72 73 6f 72 73 20 2a  of all cursors *
5720: 2f 0a 20 20 73 74 72 75 63 74 20 4b 65 79 49 6e  /.  struct KeyIn
5730: 66 6f 20 2a 70 4b 65 79 49 6e 66 6f 3b 20 2f 2a  fo *pKeyInfo; /*
5740: 20 41 72 67 75 6d 65 6e 74 20 70 61 73 73 65 64   Argument passed
5750: 20 74 6f 20 63 6f 6d 70 61 72 69 73 6f 6e 20 66   to comparison f
5760: 75 6e 63 74 69 6f 6e 20 2a 2f 0a 20 20 50 67 6e  unction */.  Pgn
5770: 6f 20 70 67 6e 6f 52 6f 6f 74 3b 20 20 20 20 20  o pgnoRoot;     
5780: 20 20 20 20 20 20 20 2f 2a 20 54 68 65 20 72 6f         /* The ro
5790: 6f 74 20 70 61 67 65 20 6f 66 20 74 68 69 73 20  ot page of this 
57a0: 74 72 65 65 20 2a 2f 0a 20 20 73 71 6c 69 74 65  tree */.  sqlite
57b0: 33 5f 69 6e 74 36 34 20 63 61 63 68 65 64 52 6f  3_int64 cachedRo
57c0: 77 69 64 3b 20 2f 2a 20 4e 65 78 74 20 72 6f 77  wid; /* Next row
57d0: 69 64 20 63 61 63 68 65 2e 20 20 30 20 6d 65 61  id cache.  0 mea
57e0: 6e 73 20 6e 6f 74 20 76 61 6c 69 64 20 2a 2f 0a  ns not valid */.
57f0: 20 20 43 65 6c 6c 49 6e 66 6f 20 69 6e 66 6f 3b    CellInfo info;
5800: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 41              /* A
5810: 20 70 61 72 73 65 20 6f 66 20 74 68 65 20 63 65   parse of the ce
5820: 6c 6c 20 77 65 20 61 72 65 20 70 6f 69 6e 74 69  ll we are pointi
5830: 6e 67 20 61 74 20 2a 2f 0a 20 20 69 36 34 20 6e  ng at */.  i64 n
5840: 4b 65 79 3b 20 20 20 20 20 20 20 20 2f 2a 20 53  Key;        /* S
5850: 69 7a 65 20 6f 66 20 70 4b 65 79 2c 20 6f 72 20  ize of pKey, or 
5860: 6c 61 73 74 20 69 6e 74 65 67 65 72 20 6b 65 79  last integer key
5870: 20 2a 2f 0a 20 20 76 6f 69 64 20 2a 70 4b 65 79   */.  void *pKey
5880: 3b 20 20 20 20 20 20 2f 2a 20 53 61 76 65 64 20  ;      /* Saved 
5890: 6b 65 79 20 74 68 61 74 20 77 61 73 20 63 75 72  key that was cur
58a0: 73 6f 72 27 73 20 6c 61 73 74 20 6b 6e 6f 77 6e  sor's last known
58b0: 20 70 6f 73 69 74 69 6f 6e 20 2a 2f 0a 20 20 69   position */.  i
58c0: 6e 74 20 73 6b 69 70 4e 65 78 74 3b 20 20 20 20  nt skipNext;    
58d0: 2f 2a 20 50 72 65 76 28 29 20 69 73 20 6e 6f 6f  /* Prev() is noo
58e0: 70 20 69 66 20 6e 65 67 61 74 69 76 65 2e 20 4e  p if negative. N
58f0: 65 78 74 28 29 20 69 73 20 6e 6f 6f 70 20 69 66  ext() is noop if
5900: 20 70 6f 73 69 74 69 76 65 20 2a 2f 0a 20 20 75   positive */.  u
5910: 38 20 77 72 46 6c 61 67 3b 20 20 20 20 20 20 20  8 wrFlag;       
5920: 20 20 20 20 20 20 20 20 20 2f 2a 20 54 72 75 65           /* True
5930: 20 69 66 20 77 72 69 74 61 62 6c 65 20 2a 2f 0a   if writable */.
5940: 20 20 75 38 20 61 74 4c 61 73 74 3b 20 20 20 20    u8 atLast;    
5950: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 43              /* C
5960: 75 72 73 6f 72 20 70 6f 69 6e 74 69 6e 67 20 74  ursor pointing t
5970: 6f 20 74 68 65 20 6c 61 73 74 20 65 6e 74 72 79  o the last entry
5980: 20 2a 2f 0a 20 20 75 38 20 76 61 6c 69 64 4e 4b   */.  u8 validNK
5990: 65 79 3b 20 20 20 20 20 20 20 20 20 20 20 20 20  ey;             
59a0: 2f 2a 20 54 72 75 65 20 69 66 20 69 6e 66 6f 2e  /* True if info.
59b0: 6e 4b 65 79 20 69 73 20 76 61 6c 69 64 20 2a 2f  nKey is valid */
59c0: 0a 20 20 75 38 20 65 53 74 61 74 65 3b 20 20 20  .  u8 eState;   
59d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
59e0: 4f 6e 65 20 6f 66 20 74 68 65 20 43 55 52 53 4f  One of the CURSO
59f0: 52 5f 58 58 58 20 63 6f 6e 73 74 61 6e 74 73 20  R_XXX constants 
5a00: 28 73 65 65 20 62 65 6c 6f 77 29 20 2a 2f 0a 23  (see below) */.#
5a10: 69 66 6e 64 65 66 20 53 51 4c 49 54 45 5f 4f 4d  ifndef SQLITE_OM
5a20: 49 54 5f 49 4e 43 52 42 4c 4f 42 0a 20 20 50 67  IT_INCRBLOB.  Pg
5a30: 6e 6f 20 2a 61 4f 76 65 72 66 6c 6f 77 3b 20 20  no *aOverflow;  
5a40: 20 20 20 20 20 20 20 20 2f 2a 20 43 61 63 68 65          /* Cache
5a50: 20 6f 66 20 6f 76 65 72 66 6c 6f 77 20 70 61 67   of overflow pag
5a60: 65 20 6c 6f 63 61 74 69 6f 6e 73 20 2a 2f 0a 20  e locations */. 
5a70: 20 75 38 20 69 73 49 6e 63 72 62 6c 6f 62 48 61   u8 isIncrblobHa
5a80: 6e 64 6c 65 3b 20 20 20 20 20 20 2f 2a 20 54 72  ndle;      /* Tr
5a90: 75 65 20 69 66 20 74 68 69 73 20 63 75 72 73 6f  ue if this curso
5aa0: 72 20 69 73 20 61 6e 20 69 6e 63 72 2e 20 69 6f  r is an incr. io
5ab0: 20 68 61 6e 64 6c 65 20 2a 2f 0a 23 65 6e 64 69   handle */.#endi
5ac0: 66 0a 20 20 69 31 36 20 69 50 61 67 65 3b 20 20  f.  i16 iPage;  
5ad0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
5ae0: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 49 6e 64            /* Ind
5af0: 65 78 20 6f 66 20 63 75 72 72 65 6e 74 20 70 61  ex of current pa
5b00: 67 65 20 69 6e 20 61 70 50 61 67 65 20 2a 2f 0a  ge in apPage */.
5b10: 20 20 75 31 36 20 61 69 49 64 78 5b 42 54 43 55    u16 aiIdx[BTCU
5b20: 52 53 4f 52 5f 4d 41 58 5f 44 45 50 54 48 5d 3b  RSOR_MAX_DEPTH];
5b30: 20 20 20 20 20 20 20 20 2f 2a 20 43 75 72 72 65          /* Curre
5b40: 6e 74 20 69 6e 64 65 78 20 69 6e 20 61 70 50 61  nt index in apPa
5b50: 67 65 5b 69 5d 20 2a 2f 0a 20 20 4d 65 6d 50 61  ge[i] */.  MemPa
5b60: 67 65 20 2a 61 70 50 61 67 65 5b 42 54 43 55 52  ge *apPage[BTCUR
5b70: 53 4f 52 5f 4d 41 58 5f 44 45 50 54 48 5d 3b 20  SOR_MAX_DEPTH]; 
5b80: 20 2f 2a 20 50 61 67 65 73 20 66 72 6f 6d 20 72   /* Pages from r
5b90: 6f 6f 74 20 74 6f 20 63 75 72 72 65 6e 74 20 70  oot to current p
5ba0: 61 67 65 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a  age */.};../*.**
5bb0: 20 50 6f 74 65 6e 74 69 61 6c 20 76 61 6c 75 65   Potential value
5bc0: 73 20 66 6f 72 20 42 74 43 75 72 73 6f 72 2e 65  s for BtCursor.e
5bd0: 53 74 61 74 65 2e 0a 2a 2a 0a 2a 2a 20 43 55 52  State..**.** CUR
5be0: 53 4f 52 5f 56 41 4c 49 44 3a 0a 2a 2a 20 20 20  SOR_VALID:.**   
5bf0: 43 75 72 73 6f 72 20 70 6f 69 6e 74 73 20 74 6f  Cursor points to
5c00: 20 61 20 76 61 6c 69 64 20 65 6e 74 72 79 2e 20   a valid entry. 
5c10: 67 65 74 50 61 79 6c 6f 61 64 28 29 20 65 74 63  getPayload() etc
5c20: 2e 20 6d 61 79 20 62 65 20 63 61 6c 6c 65 64 2e  . may be called.
5c30: 0a 2a 2a 0a 2a 2a 20 43 55 52 53 4f 52 5f 49 4e  .**.** CURSOR_IN
5c40: 56 41 4c 49 44 3a 0a 2a 2a 20 20 20 43 75 72 73  VALID:.**   Curs
5c50: 6f 72 20 64 6f 65 73 20 6e 6f 74 20 70 6f 69 6e  or does not poin
5c60: 74 20 74 6f 20 61 20 76 61 6c 69 64 20 65 6e 74  t to a valid ent
5c70: 72 79 2e 20 54 68 69 73 20 63 61 6e 20 68 61 70  ry. This can hap
5c80: 70 65 6e 20 28 66 6f 72 20 65 78 61 6d 70 6c 65  pen (for example
5c90: 29 20 0a 2a 2a 20 20 20 62 65 63 61 75 73 65 20  ) .**   because 
5ca0: 74 68 65 20 74 61 62 6c 65 20 69 73 20 65 6d 70  the table is emp
5cb0: 74 79 20 6f 72 20 62 65 63 61 75 73 65 20 42 74  ty or because Bt
5cc0: 72 65 65 43 75 72 73 6f 72 46 69 72 73 74 28 29  reeCursorFirst()
5cd0: 20 68 61 73 20 6e 6f 74 20 62 65 65 6e 0a 2a 2a   has not been.**
5ce0: 20 20 20 63 61 6c 6c 65 64 2e 0a 2a 2a 0a 2a 2a     called..**.**
5cf0: 20 43 55 52 53 4f 52 5f 52 45 51 55 49 52 45 53   CURSOR_REQUIRES
5d00: 45 45 4b 3a 0a 2a 2a 20 20 20 54 68 65 20 74 61  EEK:.**   The ta
5d10: 62 6c 65 20 74 68 61 74 20 74 68 69 73 20 63 75  ble that this cu
5d20: 72 73 6f 72 20 77 61 73 20 6f 70 65 6e 65 64 20  rsor was opened 
5d30: 6f 6e 20 73 74 69 6c 6c 20 65 78 69 73 74 73 2c  on still exists,
5d40: 20 62 75 74 20 68 61 73 20 62 65 65 6e 20 0a 2a   but has been .*
5d50: 2a 20 20 20 6d 6f 64 69 66 69 65 64 20 73 69 6e  *   modified sin
5d60: 63 65 20 74 68 65 20 63 75 72 73 6f 72 20 77 61  ce the cursor wa
5d70: 73 20 6c 61 73 74 20 75 73 65 64 2e 20 54 68 65  s last used. The
5d80: 20 63 75 72 73 6f 72 20 70 6f 73 69 74 69 6f 6e   cursor position
5d90: 20 69 73 20 73 61 76 65 64 0a 2a 2a 20 20 20 69   is saved.**   i
5da0: 6e 20 76 61 72 69 61 62 6c 65 73 20 42 74 43 75  n variables BtCu
5db0: 72 73 6f 72 2e 70 4b 65 79 20 61 6e 64 20 42 74  rsor.pKey and Bt
5dc0: 43 75 72 73 6f 72 2e 6e 4b 65 79 2e 20 57 68 65  Cursor.nKey. Whe
5dd0: 6e 20 61 20 63 75 72 73 6f 72 20 69 73 20 69 6e  n a cursor is in
5de0: 20 0a 2a 2a 20 20 20 74 68 69 73 20 73 74 61 74   .**   this stat
5df0: 65 2c 20 72 65 73 74 6f 72 65 43 75 72 73 6f 72  e, restoreCursor
5e00: 50 6f 73 69 74 69 6f 6e 28 29 20 63 61 6e 20 62  Position() can b
5e10: 65 20 63 61 6c 6c 65 64 20 74 6f 20 61 74 74 65  e called to atte
5e20: 6d 70 74 20 74 6f 0a 2a 2a 20 20 20 73 65 65 6b  mpt to.**   seek
5e30: 20 74 68 65 20 63 75 72 73 6f 72 20 74 6f 20 74   the cursor to t
5e40: 68 65 20 73 61 76 65 64 20 70 6f 73 69 74 69 6f  he saved positio
5e50: 6e 2e 0a 2a 2a 0a 2a 2a 20 43 55 52 53 4f 52 5f  n..**.** CURSOR_
5e60: 46 41 55 4c 54 3a 0a 2a 2a 20 20 20 41 20 75 6e  FAULT:.**   A un
5e70: 72 65 63 6f 76 65 72 61 62 6c 65 20 65 72 72 6f  recoverable erro
5e80: 72 20 28 61 6e 20 49 2f 4f 20 65 72 72 6f 72 20  r (an I/O error 
5e90: 6f 72 20 61 20 6d 61 6c 6c 6f 63 20 66 61 69 6c  or a malloc fail
5ea0: 75 72 65 29 20 68 61 73 20 6f 63 63 75 72 72 65  ure) has occurre
5eb0: 64 0a 2a 2a 20 20 20 6f 6e 20 61 20 64 69 66 66  d.**   on a diff
5ec0: 65 72 65 6e 74 20 63 6f 6e 6e 65 63 74 69 6f 6e  erent connection
5ed0: 20 74 68 61 74 20 73 68 61 72 65 73 20 74 68 65   that shares the
5ee0: 20 42 74 53 68 61 72 65 64 20 63 61 63 68 65 20   BtShared cache 
5ef0: 77 69 74 68 20 74 68 69 73 0a 2a 2a 20 20 20 63  with this.**   c
5f00: 75 72 73 6f 72 2e 20 20 54 68 65 20 65 72 72 6f  ursor.  The erro
5f10: 72 20 68 61 73 20 6c 65 66 74 20 74 68 65 20 63  r has left the c
5f20: 61 63 68 65 20 69 6e 20 61 6e 20 69 6e 63 6f 6e  ache in an incon
5f30: 73 69 73 74 65 6e 74 20 73 74 61 74 65 2e 0a 2a  sistent state..*
5f40: 2a 20 20 20 44 6f 20 6e 6f 74 68 69 6e 67 20 65  *   Do nothing e
5f50: 6c 73 65 20 77 69 74 68 20 74 68 69 73 20 63 75  lse with this cu
5f60: 72 73 6f 72 2e 20 20 41 6e 79 20 61 74 74 65 6d  rsor.  Any attem
5f70: 70 74 20 74 6f 20 75 73 65 20 74 68 65 20 63 75  pt to use the cu
5f80: 72 73 6f 72 0a 2a 2a 20 20 20 73 68 6f 75 6c 64  rsor.**   should
5f90: 20 72 65 74 75 72 6e 20 74 68 65 20 65 72 72 6f   return the erro
5fa0: 72 20 63 6f 64 65 20 73 74 6f 72 65 64 20 69 6e  r code stored in
5fb0: 20 42 74 43 75 72 73 6f 72 2e 73 6b 69 70 0a 2a   BtCursor.skip.*
5fc0: 2f 0a 23 64 65 66 69 6e 65 20 43 55 52 53 4f 52  /.#define CURSOR
5fd0: 5f 49 4e 56 41 4c 49 44 20 20 20 20 20 20 20 20  _INVALID        
5fe0: 20 20 20 30 0a 23 64 65 66 69 6e 65 20 43 55 52     0.#define CUR
5ff0: 53 4f 52 5f 56 41 4c 49 44 20 20 20 20 20 20 20  SOR_VALID       
6000: 20 20 20 20 20 20 31 0a 23 64 65 66 69 6e 65 20        1.#define 
6010: 43 55 52 53 4f 52 5f 52 45 51 55 49 52 45 53 45  CURSOR_REQUIRESE
6020: 45 4b 20 20 20 20 20 20 20 32 0a 23 64 65 66 69  EK       2.#defi
6030: 6e 65 20 43 55 52 53 4f 52 5f 46 41 55 4c 54 20  ne CURSOR_FAULT 
6040: 20 20 20 20 20 20 20 20 20 20 20 20 33 0a 0a 2f              3../
6050: 2a 20 0a 2a 2a 20 54 68 65 20 64 61 74 61 62 61  * .** The databa
6060: 73 65 20 70 61 67 65 20 74 68 65 20 50 45 4e 44  se page the PEND
6070: 49 4e 47 5f 42 59 54 45 20 6f 63 63 75 70 69 65  ING_BYTE occupie
6080: 73 2e 20 54 68 69 73 20 70 61 67 65 20 69 73 20  s. This page is 
6090: 6e 65 76 65 72 20 75 73 65 64 2e 0a 2a 2f 0a 23  never used..*/.#
60a0: 20 64 65 66 69 6e 65 20 50 45 4e 44 49 4e 47 5f   define PENDING_
60b0: 42 59 54 45 5f 50 41 47 45 28 70 42 74 29 20 50  BYTE_PAGE(pBt) P
60c0: 41 47 45 52 5f 4d 4a 5f 50 47 4e 4f 28 70 42 74  AGER_MJ_PGNO(pBt
60d0: 29 0a 0a 2f 2a 0a 2a 2a 20 54 68 65 73 65 20 6d  )../*.** These m
60e0: 61 63 72 6f 73 20 64 65 66 69 6e 65 20 74 68 65  acros define the
60f0: 20 6c 6f 63 61 74 69 6f 6e 20 6f 66 20 74 68 65   location of the
6100: 20 70 6f 69 6e 74 65 72 2d 6d 61 70 20 65 6e 74   pointer-map ent
6110: 72 79 20 66 6f 72 20 61 20 0a 2a 2a 20 64 61 74  ry for a .** dat
6120: 61 62 61 73 65 20 70 61 67 65 2e 20 54 68 65 20  abase page. The 
6130: 66 69 72 73 74 20 61 72 67 75 6d 65 6e 74 20 74  first argument t
6140: 6f 20 65 61 63 68 20 69 73 20 74 68 65 20 6e 75  o each is the nu
6150: 6d 62 65 72 20 6f 66 20 75 73 61 62 6c 65 0a 2a  mber of usable.*
6160: 2a 20 62 79 74 65 73 20 6f 6e 20 65 61 63 68 20  * bytes on each 
6170: 70 61 67 65 20 6f 66 20 74 68 65 20 64 61 74 61  page of the data
6180: 62 61 73 65 20 28 6f 66 74 65 6e 20 31 30 32 34  base (often 1024
6190: 29 2e 20 54 68 65 20 73 65 63 6f 6e 64 20 69 73  ). The second is
61a0: 20 74 68 65 0a 2a 2a 20 70 61 67 65 20 6e 75 6d   the.** page num
61b0: 62 65 72 20 74 6f 20 6c 6f 6f 6b 20 75 70 20 69  ber to look up i
61c0: 6e 20 74 68 65 20 70 6f 69 6e 74 65 72 20 6d 61  n the pointer ma
61d0: 70 2e 0a 2a 2a 0a 2a 2a 20 50 54 52 4d 41 50 5f  p..**.** PTRMAP_
61e0: 50 41 47 45 4e 4f 20 72 65 74 75 72 6e 73 20 74  PAGENO returns t
61f0: 68 65 20 64 61 74 61 62 61 73 65 20 70 61 67 65  he database page
6200: 20 6e 75 6d 62 65 72 20 6f 66 20 74 68 65 20 70   number of the p
6210: 6f 69 6e 74 65 72 2d 6d 61 70 0a 2a 2a 20 70 61  ointer-map.** pa
6220: 67 65 20 74 68 61 74 20 73 74 6f 72 65 73 20 74  ge that stores t
6230: 68 65 20 72 65 71 75 69 72 65 64 20 70 6f 69 6e  he required poin
6240: 74 65 72 2e 20 50 54 52 4d 41 50 5f 50 54 52 4f  ter. PTRMAP_PTRO
6250: 46 46 53 45 54 20 72 65 74 75 72 6e 73 0a 2a 2a  FFSET returns.**
6260: 20 74 68 65 20 6f 66 66 73 65 74 20 6f 66 20 74   the offset of t
6270: 68 65 20 72 65 71 75 65 73 74 65 64 20 6d 61 70  he requested map
6280: 20 65 6e 74 72 79 2e 0a 2a 2a 0a 2a 2a 20 49 66   entry..**.** If
6290: 20 74 68 65 20 70 67 6e 6f 20 61 72 67 75 6d 65   the pgno argume
62a0: 6e 74 20 70 61 73 73 65 64 20 74 6f 20 50 54 52  nt passed to PTR
62b0: 4d 41 50 5f 50 41 47 45 4e 4f 20 69 73 20 61 20  MAP_PAGENO is a 
62c0: 70 6f 69 6e 74 65 72 2d 6d 61 70 20 70 61 67 65  pointer-map page
62d0: 2c 0a 2a 2a 20 74 68 65 6e 20 70 67 6e 6f 20 69  ,.** then pgno i
62e0: 73 20 72 65 74 75 72 6e 65 64 2e 20 53 6f 20 28  s returned. So (
62f0: 70 67 6e 6f 3d 3d 50 54 52 4d 41 50 5f 50 41 47  pgno==PTRMAP_PAG
6300: 45 4e 4f 28 70 67 73 7a 2c 20 70 67 6e 6f 29 29  ENO(pgsz, pgno))
6310: 20 63 61 6e 20 62 65 0a 2a 2a 20 75 73 65 64 20   can be.** used 
6320: 74 6f 20 74 65 73 74 20 69 66 20 70 67 6e 6f 20  to test if pgno 
6330: 69 73 20 61 20 70 6f 69 6e 74 65 72 2d 6d 61 70  is a pointer-map
6340: 20 70 61 67 65 2e 20 50 54 52 4d 41 50 5f 49 53   page. PTRMAP_IS
6350: 50 41 47 45 20 69 6d 70 6c 65 6d 65 6e 74 73 0a  PAGE implements.
6360: 2a 2a 20 74 68 69 73 20 74 65 73 74 2e 0a 2a 2f  ** this test..*/
6370: 0a 23 64 65 66 69 6e 65 20 50 54 52 4d 41 50 5f  .#define PTRMAP_
6380: 50 41 47 45 4e 4f 28 70 42 74 2c 20 70 67 6e 6f  PAGENO(pBt, pgno
6390: 29 20 70 74 72 6d 61 70 50 61 67 65 6e 6f 28 70  ) ptrmapPageno(p
63a0: 42 74 2c 20 70 67 6e 6f 29 0a 23 64 65 66 69 6e  Bt, pgno).#defin
63b0: 65 20 50 54 52 4d 41 50 5f 50 54 52 4f 46 46 53  e PTRMAP_PTROFFS
63c0: 45 54 28 70 67 70 74 72 6d 61 70 2c 20 70 67 6e  ET(pgptrmap, pgn
63d0: 6f 29 20 28 35 2a 28 70 67 6e 6f 2d 70 67 70 74  o) (5*(pgno-pgpt
63e0: 72 6d 61 70 2d 31 29 29 0a 23 64 65 66 69 6e 65  rmap-1)).#define
63f0: 20 50 54 52 4d 41 50 5f 49 53 50 41 47 45 28 70   PTRMAP_ISPAGE(p
6400: 42 74 2c 20 70 67 6e 6f 29 20 28 50 54 52 4d 41  Bt, pgno) (PTRMA
6410: 50 5f 50 41 47 45 4e 4f 28 28 70 42 74 29 2c 28  P_PAGENO((pBt),(
6420: 70 67 6e 6f 29 29 3d 3d 28 70 67 6e 6f 29 29 0a  pgno))==(pgno)).
6430: 0a 2f 2a 0a 2a 2a 20 54 68 65 20 70 6f 69 6e 74  ./*.** The point
6440: 65 72 20 6d 61 70 20 69 73 20 61 20 6c 6f 6f 6b  er map is a look
6450: 75 70 20 74 61 62 6c 65 20 74 68 61 74 20 69 64  up table that id
6460: 65 6e 74 69 66 69 65 73 20 74 68 65 20 70 61 72  entifies the par
6470: 65 6e 74 20 70 61 67 65 20 66 6f 72 0a 2a 2a 20  ent page for.** 
6480: 65 61 63 68 20 63 68 69 6c 64 20 70 61 67 65 20  each child page 
6490: 69 6e 20 74 68 65 20 64 61 74 61 62 61 73 65 20  in the database 
64a0: 66 69 6c 65 2e 20 20 54 68 65 20 70 61 72 65 6e  file.  The paren
64b0: 74 20 70 61 67 65 20 69 73 20 74 68 65 20 70 61  t page is the pa
64c0: 67 65 20 74 68 61 74 0a 2a 2a 20 63 6f 6e 74 61  ge that.** conta
64d0: 69 6e 73 20 61 20 70 6f 69 6e 74 65 72 20 74 6f  ins a pointer to
64e0: 20 74 68 65 20 63 68 69 6c 64 2e 20 20 45 76 65   the child.  Eve
64f0: 72 79 20 70 61 67 65 20 69 6e 20 74 68 65 20 64  ry page in the d
6500: 61 74 61 62 61 73 65 20 63 6f 6e 74 61 69 6e 73  atabase contains
6510: 0a 2a 2a 20 30 20 6f 72 20 31 20 70 61 72 65 6e  .** 0 or 1 paren
6520: 74 20 70 61 67 65 73 2e 20 20 28 49 6e 20 74 68  t pages.  (In th
6530: 69 73 20 63 6f 6e 74 65 78 74 20 27 64 61 74 61  is context 'data
6540: 62 61 73 65 20 70 61 67 65 27 20 72 65 66 65 72  base page' refer
6550: 73 0a 2a 2a 20 74 6f 20 61 6e 79 20 70 61 67 65  s.** to any page
6560: 20 74 68 61 74 20 69 73 20 6e 6f 74 20 70 61 72   that is not par
6570: 74 20 6f 66 20 74 68 65 20 70 6f 69 6e 74 65 72  t of the pointer
6580: 20 6d 61 70 20 69 74 73 65 6c 66 2e 29 20 20 45   map itself.)  E
6590: 61 63 68 20 70 6f 69 6e 74 65 72 20 6d 61 70 0a  ach pointer map.
65a0: 2a 2a 20 65 6e 74 72 79 20 63 6f 6e 73 69 73 74  ** entry consist
65b0: 73 20 6f 66 20 61 20 73 69 6e 67 6c 65 20 62 79  s of a single by
65c0: 74 65 20 27 74 79 70 65 27 20 61 6e 64 20 61 20  te 'type' and a 
65d0: 34 20 62 79 74 65 20 70 61 72 65 6e 74 20 70 61  4 byte parent pa
65e0: 67 65 20 6e 75 6d 62 65 72 2e 0a 2a 2a 20 54 68  ge number..** Th
65f0: 65 20 50 54 52 4d 41 50 5f 58 58 58 20 69 64 65  e PTRMAP_XXX ide
6600: 6e 74 69 66 69 65 72 73 20 62 65 6c 6f 77 20 61  ntifiers below a
6610: 72 65 20 74 68 65 20 76 61 6c 69 64 20 74 79 70  re the valid typ
6620: 65 73 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 70 75  es..**.** The pu
6630: 72 70 6f 73 65 20 6f 66 20 74 68 65 20 70 6f 69  rpose of the poi
6640: 6e 74 65 72 20 6d 61 70 20 69 73 20 74 6f 20 66  nter map is to f
6650: 61 63 69 6c 69 74 79 20 6d 6f 76 69 6e 67 20 70  acility moving p
6660: 61 67 65 73 20 66 72 6f 6d 20 6f 6e 65 0a 2a 2a  ages from one.**
6670: 20 70 6f 73 69 74 69 6f 6e 20 69 6e 20 74 68 65   position in the
6680: 20 66 69 6c 65 20 74 6f 20 61 6e 6f 74 68 65 72   file to another
6690: 20 61 73 20 70 61 72 74 20 6f 66 20 61 75 74 6f   as part of auto
66a0: 76 61 63 75 75 6d 2e 20 20 57 68 65 6e 20 61 20  vacuum.  When a 
66b0: 70 61 67 65 0a 2a 2a 20 69 73 20 6d 6f 76 65 64  page.** is moved
66c0: 2c 20 74 68 65 20 70 6f 69 6e 74 65 72 20 69 6e  , the pointer in
66d0: 20 69 74 73 20 70 61 72 65 6e 74 20 6d 75 73 74   its parent must
66e0: 20 62 65 20 75 70 64 61 74 65 64 20 74 6f 20 70   be updated to p
66f0: 6f 69 6e 74 20 74 6f 20 74 68 65 0a 2a 2a 20 6e  oint to the.** n
6700: 65 77 20 6c 6f 63 61 74 69 6f 6e 2e 20 20 54 68  ew location.  Th
6710: 65 20 70 6f 69 6e 74 65 72 20 6d 61 70 20 69 73  e pointer map is
6720: 20 75 73 65 64 20 74 6f 20 6c 6f 63 61 74 65 20   used to locate 
6730: 74 68 65 20 70 61 72 65 6e 74 20 70 61 67 65 20  the parent page 
6740: 71 75 69 63 6b 6c 79 2e 0a 2a 2a 0a 2a 2a 20 50  quickly..**.** P
6750: 54 52 4d 41 50 5f 52 4f 4f 54 50 41 47 45 3a 20  TRMAP_ROOTPAGE: 
6760: 54 68 65 20 64 61 74 61 62 61 73 65 20 70 61 67  The database pag
6770: 65 20 69 73 20 61 20 72 6f 6f 74 2d 70 61 67 65  e is a root-page
6780: 2e 20 54 68 65 20 70 61 67 65 2d 6e 75 6d 62 65  . The page-numbe
6790: 72 20 69 73 20 6e 6f 74 0a 2a 2a 20 20 20 20 20  r is not.**     
67a0: 20 20 20 20 20 20 20 20 20 20 20 20 20 75 73 65               use
67b0: 64 20 69 6e 20 74 68 69 73 20 63 61 73 65 2e 0a  d in this case..
67c0: 2a 2a 0a 2a 2a 20 50 54 52 4d 41 50 5f 46 52 45  **.** PTRMAP_FRE
67d0: 45 50 41 47 45 3a 20 54 68 65 20 64 61 74 61 62  EPAGE: The datab
67e0: 61 73 65 20 70 61 67 65 20 69 73 20 61 6e 20 75  ase page is an u
67f0: 6e 75 73 65 64 20 28 66 72 65 65 29 20 70 61 67  nused (free) pag
6800: 65 2e 20 54 68 65 20 70 61 67 65 2d 6e 75 6d 62  e. The page-numb
6810: 65 72 20 0a 2a 2a 20 20 20 20 20 20 20 20 20 20  er .**          
6820: 20 20 20 20 20 20 20 20 69 73 20 6e 6f 74 20 75          is not u
6830: 73 65 64 20 69 6e 20 74 68 69 73 20 63 61 73 65  sed in this case
6840: 2e 0a 2a 2a 0a 2a 2a 20 50 54 52 4d 41 50 5f 4f  ..**.** PTRMAP_O
6850: 56 45 52 46 4c 4f 57 31 3a 20 54 68 65 20 64 61  VERFLOW1: The da
6860: 74 61 62 61 73 65 20 70 61 67 65 20 69 73 20 74  tabase page is t
6870: 68 65 20 66 69 72 73 74 20 70 61 67 65 20 69 6e  he first page in
6880: 20 61 20 6c 69 73 74 20 6f 66 20 0a 2a 2a 20 20   a list of .**  
6890: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
68a0: 20 6f 76 65 72 66 6c 6f 77 20 70 61 67 65 73 2e   overflow pages.
68b0: 20 54 68 65 20 70 61 67 65 20 6e 75 6d 62 65 72   The page number
68c0: 20 69 64 65 6e 74 69 66 69 65 73 20 74 68 65 20   identifies the 
68d0: 70 61 67 65 20 74 68 61 74 0a 2a 2a 20 20 20 20  page that.**    
68e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 63                 c
68f0: 6f 6e 74 61 69 6e 73 20 74 68 65 20 63 65 6c 6c  ontains the cell
6900: 20 77 69 74 68 20 61 20 70 6f 69 6e 74 65 72 20   with a pointer 
6910: 74 6f 20 74 68 69 73 20 6f 76 65 72 66 6c 6f 77  to this overflow
6920: 20 70 61 67 65 2e 0a 2a 2a 0a 2a 2a 20 50 54 52   page..**.** PTR
6930: 4d 41 50 5f 4f 56 45 52 46 4c 4f 57 32 3a 20 54  MAP_OVERFLOW2: T
6940: 68 65 20 64 61 74 61 62 61 73 65 20 70 61 67 65  he database page
6950: 20 69 73 20 74 68 65 20 73 65 63 6f 6e 64 20 6f   is the second o
6960: 72 20 6c 61 74 65 72 20 70 61 67 65 20 69 6e 20  r later page in 
6970: 61 20 6c 69 73 74 20 6f 66 0a 2a 2a 20 20 20 20  a list of.**    
6980: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 6f                 o
6990: 76 65 72 66 6c 6f 77 20 70 61 67 65 73 2e 20 54  verflow pages. T
69a0: 68 65 20 70 61 67 65 2d 6e 75 6d 62 65 72 20 69  he page-number i
69b0: 64 65 6e 74 69 66 69 65 73 20 74 68 65 20 70 72  dentifies the pr
69c0: 65 76 69 6f 75 73 0a 2a 2a 20 20 20 20 20 20 20  evious.**       
69d0: 20 20 20 20 20 20 20 20 20 20 20 20 70 61 67 65              page
69e0: 20 69 6e 20 74 68 65 20 6f 76 65 72 66 6c 6f 77   in the overflow
69f0: 20 70 61 67 65 20 6c 69 73 74 2e 0a 2a 2a 0a 2a   page list..**.*
6a00: 2a 20 50 54 52 4d 41 50 5f 42 54 52 45 45 3a 20  * PTRMAP_BTREE: 
6a10: 54 68 65 20 64 61 74 61 62 61 73 65 20 70 61 67  The database pag
6a20: 65 20 69 73 20 61 20 6e 6f 6e 2d 72 6f 6f 74 20  e is a non-root 
6a30: 62 74 72 65 65 20 70 61 67 65 2e 20 54 68 65 20  btree page. The 
6a40: 70 61 67 65 20 6e 75 6d 62 65 72 0a 2a 2a 20 20  page number.**  
6a50: 20 20 20 20 20 20 20 20 20 20 20 20 20 69 64 65               ide
6a60: 6e 74 69 66 69 65 73 20 74 68 65 20 70 61 72 65  ntifies the pare
6a70: 6e 74 20 70 61 67 65 20 69 6e 20 74 68 65 20 62  nt page in the b
6a80: 74 72 65 65 2e 0a 2a 2f 0a 23 64 65 66 69 6e 65  tree..*/.#define
6a90: 20 50 54 52 4d 41 50 5f 52 4f 4f 54 50 41 47 45   PTRMAP_ROOTPAGE
6aa0: 20 31 0a 23 64 65 66 69 6e 65 20 50 54 52 4d 41   1.#define PTRMA
6ab0: 50 5f 46 52 45 45 50 41 47 45 20 32 0a 23 64 65  P_FREEPAGE 2.#de
6ac0: 66 69 6e 65 20 50 54 52 4d 41 50 5f 4f 56 45 52  fine PTRMAP_OVER
6ad0: 46 4c 4f 57 31 20 33 0a 23 64 65 66 69 6e 65 20  FLOW1 3.#define 
6ae0: 50 54 52 4d 41 50 5f 4f 56 45 52 46 4c 4f 57 32  PTRMAP_OVERFLOW2
6af0: 20 34 0a 23 64 65 66 69 6e 65 20 50 54 52 4d 41   4.#define PTRMA
6b00: 50 5f 42 54 52 45 45 20 35 0a 0a 2f 2a 20 41 20  P_BTREE 5../* A 
6b10: 62 75 6e 63 68 20 6f 66 20 61 73 73 65 72 74 28  bunch of assert(
6b20: 29 20 73 74 61 74 65 6d 65 6e 74 73 20 74 6f 20  ) statements to 
6b30: 63 68 65 63 6b 20 74 68 65 20 74 72 61 6e 73 61  check the transa
6b40: 63 74 69 6f 6e 20 73 74 61 74 65 20 76 61 72 69  ction state vari
6b50: 61 62 6c 65 73 0a 2a 2a 20 6f 66 20 68 61 6e 64  ables.** of hand
6b60: 6c 65 20 70 20 28 74 79 70 65 20 42 74 72 65 65  le p (type Btree
6b70: 2a 29 20 61 72 65 20 69 6e 74 65 72 6e 61 6c 6c  *) are internall
6b80: 79 20 63 6f 6e 73 69 73 74 65 6e 74 2e 0a 2a 2f  y consistent..*/
6b90: 0a 23 64 65 66 69 6e 65 20 62 74 72 65 65 49 6e  .#define btreeIn
6ba0: 74 65 67 72 69 74 79 28 70 29 20 5c 0a 20 20 61  tegrity(p) \.  a
6bb0: 73 73 65 72 74 28 20 70 2d 3e 70 42 74 2d 3e 69  ssert( p->pBt->i
6bc0: 6e 54 72 61 6e 73 61 63 74 69 6f 6e 21 3d 54 52  nTransaction!=TR
6bd0: 41 4e 53 5f 4e 4f 4e 45 20 7c 7c 20 70 2d 3e 70  ANS_NONE || p->p
6be0: 42 74 2d 3e 6e 54 72 61 6e 73 61 63 74 69 6f 6e  Bt->nTransaction
6bf0: 3d 3d 30 20 29 3b 20 5c 0a 20 20 61 73 73 65 72  ==0 ); \.  asser
6c00: 74 28 20 70 2d 3e 70 42 74 2d 3e 69 6e 54 72 61  t( p->pBt->inTra
6c10: 6e 73 61 63 74 69 6f 6e 3e 3d 70 2d 3e 69 6e 54  nsaction>=p->inT
6c20: 72 61 6e 73 20 29 3b 20 0a 0a 0a 2f 2a 0a 2a 2a  rans ); .../*.**
6c30: 20 54 68 65 20 49 53 41 55 54 4f 56 41 43 55 55   The ISAUTOVACUU
6c40: 4d 20 6d 61 63 72 6f 20 69 73 20 75 73 65 64 20  M macro is used 
6c50: 77 69 74 68 69 6e 20 62 61 6c 61 6e 63 65 5f 6e  within balance_n
6c60: 6f 6e 72 6f 6f 74 28 29 20 74 6f 20 64 65 74 65  onroot() to dete
6c70: 72 6d 69 6e 65 0a 2a 2a 20 69 66 20 74 68 65 20  rmine.** if the 
6c80: 64 61 74 61 62 61 73 65 20 73 75 70 70 6f 72 74  database support
6c90: 73 20 61 75 74 6f 2d 76 61 63 75 75 6d 20 6f 72  s auto-vacuum or
6ca0: 20 6e 6f 74 2e 20 42 65 63 61 75 73 65 20 69 74   not. Because it
6cb0: 20 69 73 20 75 73 65 64 0a 2a 2a 20 77 69 74 68   is used.** with
6cc0: 69 6e 20 61 6e 20 65 78 70 72 65 73 73 69 6f 6e  in an expression
6cd0: 20 74 68 61 74 20 69 73 20 61 6e 20 61 72 67 75   that is an argu
6ce0: 6d 65 6e 74 20 74 6f 20 61 6e 6f 74 68 65 72 20  ment to another 
6cf0: 6d 61 63 72 6f 20 0a 2a 2a 20 28 73 71 6c 69 74  macro .** (sqlit
6d00: 65 4d 61 6c 6c 6f 63 52 61 77 29 2c 20 69 74 20  eMallocRaw), it 
6d10: 69 73 20 6e 6f 74 20 70 6f 73 73 69 62 6c 65 20  is not possible 
6d20: 74 6f 20 75 73 65 20 63 6f 6e 64 69 74 69 6f 6e  to use condition
6d30: 61 6c 20 63 6f 6d 70 69 6c 61 74 69 6f 6e 2e 0a  al compilation..
6d40: 2a 2a 20 53 6f 2c 20 74 68 69 73 20 6d 61 63 72  ** So, this macr
6d50: 6f 20 69 73 20 64 65 66 69 6e 65 64 20 69 6e 73  o is defined ins
6d60: 74 65 61 64 2e 0a 2a 2f 0a 23 69 66 6e 64 65 66  tead..*/.#ifndef
6d70: 20 53 51 4c 49 54 45 5f 4f 4d 49 54 5f 41 55 54   SQLITE_OMIT_AUT
6d80: 4f 56 41 43 55 55 4d 0a 23 64 65 66 69 6e 65 20  OVACUUM.#define 
6d90: 49 53 41 55 54 4f 56 41 43 55 55 4d 20 28 70 42  ISAUTOVACUUM (pB
6da0: 74 2d 3e 61 75 74 6f 56 61 63 75 75 6d 29 0a 23  t->autoVacuum).#
6db0: 65 6c 73 65 0a 23 64 65 66 69 6e 65 20 49 53 41  else.#define ISA
6dc0: 55 54 4f 56 41 43 55 55 4d 20 30 0a 23 65 6e 64  UTOVACUUM 0.#end
6dd0: 69 66 0a 0a 0a 2f 2a 0a 2a 2a 20 54 68 69 73 20  if.../*.** This 
6de0: 73 74 72 75 63 74 75 72 65 20 69 73 20 70 61 73  structure is pas
6df0: 73 65 64 20 61 72 6f 75 6e 64 20 74 68 72 6f 75  sed around throu
6e00: 67 68 20 61 6c 6c 20 74 68 65 20 73 61 6e 69 74  gh all the sanit
6e10: 79 20 63 68 65 63 6b 69 6e 67 20 72 6f 75 74 69  y checking routi
6e20: 6e 65 73 0a 2a 2a 20 69 6e 20 6f 72 64 65 72 20  nes.** in order 
6e30: 74 6f 20 6b 65 65 70 20 74 72 61 63 6b 20 6f 66  to keep track of
6e40: 20 73 6f 6d 65 20 67 6c 6f 62 61 6c 20 73 74 61   some global sta
6e50: 74 65 20 69 6e 66 6f 72 6d 61 74 69 6f 6e 2e 0a  te information..
6e60: 2a 2f 0a 74 79 70 65 64 65 66 20 73 74 72 75 63  */.typedef struc
6e70: 74 20 49 6e 74 65 67 72 69 74 79 43 6b 20 49 6e  t IntegrityCk In
6e80: 74 65 67 72 69 74 79 43 6b 3b 0a 73 74 72 75 63  tegrityCk;.struc
6e90: 74 20 49 6e 74 65 67 72 69 74 79 43 6b 20 7b 0a  t IntegrityCk {.
6ea0: 20 20 42 74 53 68 61 72 65 64 20 2a 70 42 74 3b    BtShared *pBt;
6eb0: 20 20 20 20 2f 2a 20 54 68 65 20 74 72 65 65 20      /* The tree 
6ec0: 62 65 69 6e 67 20 63 68 65 63 6b 65 64 20 6f 75  being checked ou
6ed0: 74 20 2a 2f 0a 20 20 50 61 67 65 72 20 2a 70 50  t */.  Pager *pP
6ee0: 61 67 65 72 3b 20 20 20 20 2f 2a 20 54 68 65 20  ager;    /* The 
6ef0: 61 73 73 6f 63 69 61 74 65 64 20 70 61 67 65 72  associated pager
6f00: 2e 20 20 41 6c 73 6f 20 61 63 63 65 73 73 69 62  .  Also accessib
6f10: 6c 65 20 62 79 20 70 42 74 2d 3e 70 50 61 67 65  le by pBt->pPage
6f20: 72 20 2a 2f 0a 20 20 50 67 6e 6f 20 6e 50 61 67  r */.  Pgno nPag
6f30: 65 3b 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62  e;       /* Numb
6f40: 65 72 20 6f 66 20 70 61 67 65 73 20 69 6e 20 74  er of pages in t
6f50: 68 65 20 64 61 74 61 62 61 73 65 20 2a 2f 0a 20  he database */. 
6f60: 20 69 6e 74 20 2a 61 6e 52 65 66 3b 20 20 20 20   int *anRef;    
6f70: 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20     /* Number of 
6f80: 74 69 6d 65 73 20 65 61 63 68 20 70 61 67 65 20  times each page 
6f90: 69 73 20 72 65 66 65 72 65 6e 63 65 64 20 2a 2f  is referenced */
6fa0: 0a 20 20 69 6e 74 20 6d 78 45 72 72 3b 20 20 20  .  int mxErr;   
6fb0: 20 20 20 20 20 2f 2a 20 53 74 6f 70 20 61 63 63       /* Stop acc
6fc0: 75 6d 75 6c 61 74 69 6e 67 20 65 72 72 6f 72 73  umulating errors
6fd0: 20 77 68 65 6e 20 74 68 69 73 20 72 65 61 63 68   when this reach
6fe0: 65 73 20 7a 65 72 6f 20 2a 2f 0a 20 20 69 6e 74  es zero */.  int
6ff0: 20 6e 45 72 72 3b 20 20 20 20 20 20 20 20 20 2f   nErr;         /
7000: 2a 20 4e 75 6d 62 65 72 20 6f 66 20 6d 65 73 73  * Number of mess
7010: 61 67 65 73 20 77 72 69 74 74 65 6e 20 74 6f 20  ages written to 
7020: 7a 45 72 72 4d 73 67 20 73 6f 20 66 61 72 20 2a  zErrMsg so far *
7030: 2f 0a 20 20 69 6e 74 20 6d 61 6c 6c 6f 63 46 61  /.  int mallocFa
7040: 69 6c 65 64 3b 20 2f 2a 20 41 20 6d 65 6d 6f 72  iled; /* A memor
7050: 79 20 61 6c 6c 6f 63 61 74 69 6f 6e 20 65 72 72  y allocation err
7060: 6f 72 20 68 61 73 20 6f 63 63 75 72 72 65 64 20  or has occurred 
7070: 2a 2f 0a 20 20 53 74 72 41 63 63 75 6d 20 65 72  */.  StrAccum er
7080: 72 4d 73 67 3b 20 20 2f 2a 20 41 63 63 75 6d 75  rMsg;  /* Accumu
7090: 6c 61 74 65 20 74 68 65 20 65 72 72 6f 72 20 6d  late the error m
70a0: 65 73 73 61 67 65 20 74 65 78 74 20 68 65 72 65  essage text here
70b0: 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 52 65   */.};../*.** Re
70c0: 61 64 20 6f 72 20 77 72 69 74 65 20 61 20 74 77  ad or write a tw
70d0: 6f 2d 20 61 6e 64 20 66 6f 75 72 2d 62 79 74 65  o- and four-byte
70e0: 20 62 69 67 2d 65 6e 64 69 61 6e 20 69 6e 74 65   big-endian inte
70f0: 67 65 72 20 76 61 6c 75 65 73 2e 0a 2a 2f 0a 23  ger values..*/.#
7100: 64 65 66 69 6e 65 20 67 65 74 32 62 79 74 65 28  define get2byte(
7110: 78 29 20 20 20 28 28 78 29 5b 30 5d 3c 3c 38 20  x)   ((x)[0]<<8 
7120: 7c 20 28 78 29 5b 31 5d 29 0a 23 64 65 66 69 6e  | (x)[1]).#defin
7130: 65 20 70 75 74 32 62 79 74 65 28 70 2c 76 29 20  e put2byte(p,v) 
7140: 28 28 70 29 5b 30 5d 20 3d 20 28 75 38 29 28 28  ((p)[0] = (u8)((
7150: 76 29 3e 3e 38 29 2c 20 28 70 29 5b 31 5d 20 3d  v)>>8), (p)[1] =
7160: 20 28 75 38 29 28 76 29 29 0a 23 64 65 66 69 6e   (u8)(v)).#defin
7170: 65 20 67 65 74 34 62 79 74 65 20 73 71 6c 69 74  e get4byte sqlit
7180: 65 33 47 65 74 34 62 79 74 65 0a 23 64 65 66 69  e3Get4byte.#defi
7190: 6e 65 20 70 75 74 34 62 79 74 65 20 73 71 6c 69  ne put4byte sqli
71a0: 74 65 33 50 75 74 34 62 79 74 65 0a              te3Put4byte.