/ Hex Artifact Content
Login

Artifact f038e818bfadf75afbd09819ed93c26a333d39e0:


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 28 31  ze in bytes.  (1
0aa0: 20 6d 65 61 6e 73 20 36 35 35 33 36 29 0a 2a 2a   means 65536).**
0ab0: 20 20 20 20 20 31 38 20 20 20 20 20 20 20 31 20       18       1 
0ac0: 20 20 20 20 46 69 6c 65 20 66 6f 72 6d 61 74 20      File format 
0ad0: 77 72 69 74 65 20 76 65 72 73 69 6f 6e 0a 2a 2a  write version.**
0ae0: 20 20 20 20 20 31 39 20 20 20 20 20 20 20 31 20       19       1 
0af0: 20 20 20 20 46 69 6c 65 20 66 6f 72 6d 61 74 20      File format 
0b00: 72 65 61 64 20 76 65 72 73 69 6f 6e 0a 2a 2a 20  read version.** 
0b10: 20 20 20 20 32 30 20 20 20 20 20 20 20 31 20 20      20       1  
0b20: 20 20 20 42 79 74 65 73 20 6f 66 20 75 6e 75 73     Bytes of unus
0b30: 65 64 20 73 70 61 63 65 20 61 74 20 74 68 65 20  ed space at the 
0b40: 65 6e 64 20 6f 66 20 65 61 63 68 20 70 61 67 65  end of each page
0b50: 0a 2a 2a 20 20 20 20 20 32 31 20 20 20 20 20 20  .**     21      
0b60: 20 31 20 20 20 20 20 4d 61 78 20 65 6d 62 65 64   1     Max embed
0b70: 64 65 64 20 70 61 79 6c 6f 61 64 20 66 72 61 63  ded payload frac
0b80: 74 69 6f 6e 20 28 6d 75 73 74 20 62 65 20 36 34  tion (must be 64
0b90: 29 0a 2a 2a 20 20 20 20 20 32 32 20 20 20 20 20  ).**     22     
0ba0: 20 20 31 20 20 20 20 20 4d 69 6e 20 65 6d 62 65    1     Min embe
0bb0: 64 64 65 64 20 70 61 79 6c 6f 61 64 20 66 72 61  dded payload fra
0bc0: 63 74 69 6f 6e 20 28 6d 75 73 74 20 62 65 20 33  ction (must be 3
0bd0: 32 29 0a 2a 2a 20 20 20 20 20 32 33 20 20 20 20  2).**     23    
0be0: 20 20 20 31 20 20 20 20 20 4d 69 6e 20 6c 65 61     1     Min lea
0bf0: 66 20 70 61 79 6c 6f 61 64 20 66 72 61 63 74 69  f payload fracti
0c00: 6f 6e 20 28 6d 75 73 74 20 62 65 20 33 32 29 0a  on (must be 32).
0c10: 2a 2a 20 20 20 20 20 32 34 20 20 20 20 20 20 20  **     24       
0c20: 34 20 20 20 20 20 46 69 6c 65 20 63 68 61 6e 67  4     File chang
0c30: 65 20 63 6f 75 6e 74 65 72 0a 2a 2a 20 20 20 20  e counter.**    
0c40: 20 32 38 20 20 20 20 20 20 20 34 20 20 20 20 20   28       4     
0c50: 52 65 73 65 72 76 65 64 20 66 6f 72 20 66 75 74  Reserved for fut
0c60: 75 72 65 20 75 73 65 0a 2a 2a 20 20 20 20 20 33  ure use.**     3
0c70: 32 20 20 20 20 20 20 20 34 20 20 20 20 20 46 69  2       4     Fi
0c80: 72 73 74 20 66 72 65 65 6c 69 73 74 20 70 61 67  rst freelist pag
0c90: 65 0a 2a 2a 20 20 20 20 20 33 36 20 20 20 20 20  e.**     36     
0ca0: 20 20 34 20 20 20 20 20 4e 75 6d 62 65 72 20 6f    4     Number o
0cb0: 66 20 66 72 65 65 6c 69 73 74 20 70 61 67 65 73  f freelist pages
0cc0: 20 69 6e 20 74 68 65 20 66 69 6c 65 0a 2a 2a 20   in the file.** 
0cd0: 20 20 20 20 34 30 20 20 20 20 20 20 36 30 20 20      40      60  
0ce0: 20 20 20 31 35 20 34 2d 62 79 74 65 20 6d 65 74     15 4-byte met
0cf0: 61 20 76 61 6c 75 65 73 20 70 61 73 73 65 64 20  a values passed 
0d00: 74 6f 20 68 69 67 68 65 72 20 6c 61 79 65 72 73  to higher layers
0d10: 0a 2a 2a 0a 2a 2a 20 20 20 20 20 34 30 20 20 20  .**.**     40   
0d20: 20 20 20 20 34 20 20 20 20 20 53 63 68 65 6d 61      4     Schema
0d30: 20 63 6f 6f 6b 69 65 0a 2a 2a 20 20 20 20 20 34   cookie.**     4
0d40: 34 20 20 20 20 20 20 20 34 20 20 20 20 20 46 69  4       4     Fi
0d50: 6c 65 20 66 6f 72 6d 61 74 20 6f 66 20 73 63 68  le format of sch
0d60: 65 6d 61 20 6c 61 79 65 72 0a 2a 2a 20 20 20 20  ema layer.**    
0d70: 20 34 38 20 20 20 20 20 20 20 34 20 20 20 20 20   48       4     
0d80: 53 69 7a 65 20 6f 66 20 70 61 67 65 20 63 61 63  Size of page cac
0d90: 68 65 0a 2a 2a 20 20 20 20 20 35 32 20 20 20 20  he.**     52    
0da0: 20 20 20 34 20 20 20 20 20 4c 61 72 67 65 73 74     4     Largest
0db0: 20 72 6f 6f 74 2d 70 61 67 65 20 28 61 75 74 6f   root-page (auto
0dc0: 2f 69 6e 63 72 5f 76 61 63 75 75 6d 29 0a 2a 2a  /incr_vacuum).**
0dd0: 20 20 20 20 20 35 36 20 20 20 20 20 20 20 34 20       56       4 
0de0: 20 20 20 20 31 3d 55 54 46 2d 38 20 32 3d 55 54      1=UTF-8 2=UT
0df0: 46 31 36 6c 65 20 33 3d 55 54 46 31 36 62 65 0a  F16le 3=UTF16be.
0e00: 2a 2a 20 20 20 20 20 36 30 20 20 20 20 20 20 20  **     60       
0e10: 34 20 20 20 20 20 55 73 65 72 20 76 65 72 73 69  4     User versi
0e20: 6f 6e 0a 2a 2a 20 20 20 20 20 36 34 20 20 20 20  on.**     64    
0e30: 20 20 20 34 20 20 20 20 20 49 6e 63 72 65 6d 65     4     Increme
0e40: 6e 74 61 6c 20 76 61 63 75 75 6d 20 6d 6f 64 65  ntal vacuum mode
0e50: 0a 2a 2a 20 20 20 20 20 36 38 20 20 20 20 20 20  .**     68      
0e60: 20 34 20 20 20 20 20 41 70 70 6c 69 63 61 74 69   4     Applicati
0e70: 6f 6e 2d 49 44 0a 2a 2a 20 20 20 20 20 37 32 20  on-ID.**     72 
0e80: 20 20 20 20 20 32 30 20 20 20 20 20 75 6e 75 73       20     unus
0e90: 65 64 0a 2a 2a 20 20 20 20 20 39 32 20 20 20 20  ed.**     92    
0ea0: 20 20 20 34 20 20 20 20 20 54 68 65 20 76 65 72     4     The ver
0eb0: 73 69 6f 6e 2d 76 61 6c 69 64 2d 66 6f 72 20 6e  sion-valid-for n
0ec0: 75 6d 62 65 72 0a 2a 2a 20 20 20 20 20 39 36 20  umber.**     96 
0ed0: 20 20 20 20 20 20 34 20 20 20 20 20 53 51 4c 49        4     SQLI
0ee0: 54 45 5f 56 45 52 53 49 4f 4e 5f 4e 55 4d 42 45  TE_VERSION_NUMBE
0ef0: 52 0a 2a 2a 0a 2a 2a 20 41 6c 6c 20 6f 66 20 74  R.**.** All of t
0f00: 68 65 20 69 6e 74 65 67 65 72 20 76 61 6c 75 65  he integer value
0f10: 73 20 61 72 65 20 62 69 67 2d 65 6e 64 69 61 6e  s are big-endian
0f20: 20 28 6d 6f 73 74 20 73 69 67 6e 69 66 69 63 61   (most significa
0f30: 6e 74 20 62 79 74 65 20 66 69 72 73 74 29 2e 0a  nt byte first)..
0f40: 2a 2a 0a 2a 2a 20 54 68 65 20 66 69 6c 65 20 63  **.** The file c
0f50: 68 61 6e 67 65 20 63 6f 75 6e 74 65 72 20 69 73  hange counter is
0f60: 20 69 6e 63 72 65 6d 65 6e 74 65 64 20 77 68 65   incremented whe
0f70: 6e 20 74 68 65 20 64 61 74 61 62 61 73 65 20 69  n the database i
0f80: 73 20 63 68 61 6e 67 65 64 0a 2a 2a 20 54 68 69  s changed.** Thi
0f90: 73 20 63 6f 75 6e 74 65 72 20 61 6c 6c 6f 77 73  s counter allows
0fa0: 20 6f 74 68 65 72 20 70 72 6f 63 65 73 73 65 73   other processes
0fb0: 20 74 6f 20 6b 6e 6f 77 20 77 68 65 6e 20 74 68   to know when th
0fc0: 65 20 66 69 6c 65 20 68 61 73 20 63 68 61 6e 67  e file has chang
0fd0: 65 64 0a 2a 2a 20 61 6e 64 20 74 68 75 73 20 77  ed.** and thus w
0fe0: 68 65 6e 20 74 68 65 79 20 6e 65 65 64 20 74 6f  hen they need to
0ff0: 20 66 6c 75 73 68 20 74 68 65 69 72 20 63 61 63   flush their cac
1000: 68 65 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 6d 61  he..**.** The ma
1010: 78 20 65 6d 62 65 64 64 65 64 20 70 61 79 6c 6f  x embedded paylo
1020: 61 64 20 66 72 61 63 74 69 6f 6e 20 69 73 20 74  ad fraction is t
1030: 68 65 20 61 6d 6f 75 6e 74 20 6f 66 20 74 68 65  he amount of the
1040: 20 74 6f 74 61 6c 20 75 73 61 62 6c 65 0a 2a 2a   total usable.**
1050: 20 73 70 61 63 65 20 69 6e 20 61 20 70 61 67 65   space in a page
1060: 20 74 68 61 74 20 63 61 6e 20 62 65 20 63 6f 6e   that can be con
1070: 73 75 6d 65 64 20 62 79 20 61 20 73 69 6e 67 6c  sumed by a singl
1080: 65 20 63 65 6c 6c 20 66 6f 72 20 73 74 61 6e 64  e cell for stand
1090: 61 72 64 0a 2a 2a 20 42 2d 74 72 65 65 20 28 6e  ard.** B-tree (n
10a0: 6f 6e 2d 4c 45 41 46 44 41 54 41 29 20 74 61 62  on-LEAFDATA) tab
10b0: 6c 65 73 2e 20 20 41 20 76 61 6c 75 65 20 6f 66  les.  A value of
10c0: 20 32 35 35 20 6d 65 61 6e 73 20 31 30 30 25 2e   255 means 100%.
10d0: 20 20 54 68 65 20 64 65 66 61 75 6c 74 0a 2a 2a    The default.**
10e0: 20 69 73 20 74 6f 20 6c 69 6d 69 74 20 74 68 65   is to limit the
10f0: 20 6d 61 78 69 6d 75 6d 20 63 65 6c 6c 20 73 69   maximum cell si
1100: 7a 65 20 73 6f 20 74 68 61 74 20 61 74 20 6c 65  ze so that at le
1110: 61 73 74 20 34 20 63 65 6c 6c 73 20 77 69 6c 6c  ast 4 cells will
1120: 20 66 69 74 0a 2a 2a 20 6f 6e 20 6f 6e 65 20 70   fit.** on one p
1130: 61 67 65 2e 20 20 54 68 75 73 20 74 68 65 20 64  age.  Thus the d
1140: 65 66 61 75 6c 74 20 6d 61 78 20 65 6d 62 65 64  efault max embed
1150: 64 65 64 20 70 61 79 6c 6f 61 64 20 66 72 61 63  ded payload frac
1160: 74 69 6f 6e 20 69 73 20 36 34 2e 0a 2a 2a 0a 2a  tion is 64..**.*
1170: 2a 20 49 66 20 74 68 65 20 70 61 79 6c 6f 61 64  * If the payload
1180: 20 66 6f 72 20 61 20 63 65 6c 6c 20 69 73 20 6c   for a cell is l
1190: 61 72 67 65 72 20 74 68 61 6e 20 74 68 65 20 6d  arger than the m
11a0: 61 78 20 70 61 79 6c 6f 61 64 2c 20 74 68 65 6e  ax payload, then
11b0: 20 65 78 74 72 61 0a 2a 2a 20 70 61 79 6c 6f 61   extra.** payloa
11c0: 64 20 69 73 20 73 70 69 6c 6c 65 64 20 74 6f 20  d is spilled to 
11d0: 6f 76 65 72 66 6c 6f 77 20 70 61 67 65 73 2e 20  overflow pages. 
11e0: 20 4f 6e 63 65 20 61 6e 20 6f 76 65 72 66 6c 6f   Once an overflo
11f0: 77 20 70 61 67 65 20 69 73 20 61 6c 6c 6f 63 61  w page is alloca
1200: 74 65 64 2c 0a 2a 2a 20 61 73 20 6d 61 6e 79 20  ted,.** as many 
1210: 62 79 74 65 73 20 61 73 20 70 6f 73 73 69 62 6c  bytes as possibl
1220: 65 20 61 72 65 20 6d 6f 76 65 64 20 69 6e 74 6f  e are moved into
1230: 20 74 68 65 20 6f 76 65 72 66 6c 6f 77 20 70 61   the overflow pa
1240: 67 65 73 20 77 69 74 68 6f 75 74 20 6c 65 74 74  ges without lett
1250: 69 6e 67 0a 2a 2a 20 74 68 65 20 63 65 6c 6c 20  ing.** the cell 
1260: 73 69 7a 65 20 64 72 6f 70 20 62 65 6c 6f 77 20  size drop below 
1270: 74 68 65 20 6d 69 6e 20 65 6d 62 65 64 64 65 64  the min embedded
1280: 20 70 61 79 6c 6f 61 64 20 66 72 61 63 74 69 6f   payload fractio
1290: 6e 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 6d 69 6e  n..**.** The min
12a0: 20 6c 65 61 66 20 70 61 79 6c 6f 61 64 20 66 72   leaf payload fr
12b0: 61 63 74 69 6f 6e 20 69 73 20 6c 69 6b 65 20 74  action is like t
12c0: 68 65 20 6d 69 6e 20 65 6d 62 65 64 64 65 64 20  he min embedded 
12d0: 70 61 79 6c 6f 61 64 20 66 72 61 63 74 69 6f 6e  payload fraction
12e0: 0a 2a 2a 20 65 78 63 65 70 74 20 74 68 61 74 20  .** except that 
12f0: 69 74 20 61 70 70 6c 69 65 73 20 74 6f 20 6c 65  it applies to le
1300: 61 66 20 6e 6f 64 65 73 20 69 6e 20 61 20 4c 45  af nodes in a LE
1310: 41 46 44 41 54 41 20 74 72 65 65 2e 20 20 54 68  AFDATA tree.  Th
1320: 65 20 6d 61 78 69 6d 75 6d 0a 2a 2a 20 70 61 79  e maximum.** pay
1330: 6c 6f 61 64 20 66 72 61 63 74 69 6f 6e 20 66 6f  load fraction fo
1340: 72 20 61 20 4c 45 41 46 44 41 54 41 20 74 72 65  r a LEAFDATA tre
1350: 65 20 69 73 20 61 6c 77 61 79 73 20 31 30 30 25  e is always 100%
1360: 20 28 6f 72 20 32 35 35 29 20 61 6e 64 20 69 74   (or 255) and it
1370: 0a 2a 2a 20 6e 6f 74 20 73 70 65 63 69 66 69 65  .** not specifie
1380: 64 20 69 6e 20 74 68 65 20 68 65 61 64 65 72 2e  d in the header.
1390: 0a 2a 2a 0a 2a 2a 20 45 61 63 68 20 62 74 72 65  .**.** Each btre
13a0: 65 20 70 61 67 65 73 20 69 73 20 64 69 76 69 64  e pages is divid
13b0: 65 64 20 69 6e 74 6f 20 74 68 72 65 65 20 73 65  ed into three se
13c0: 63 74 69 6f 6e 73 3a 20 20 54 68 65 20 68 65 61  ctions:  The hea
13d0: 64 65 72 2c 20 74 68 65 0a 2a 2a 20 63 65 6c 6c  der, the.** cell
13e0: 20 70 6f 69 6e 74 65 72 20 61 72 72 61 79 2c 20   pointer array, 
13f0: 61 6e 64 20 74 68 65 20 63 65 6c 6c 20 63 6f 6e  and the cell con
1400: 74 65 6e 74 20 61 72 65 61 2e 20 20 50 61 67 65  tent area.  Page
1410: 20 31 20 61 6c 73 6f 20 68 61 73 20 61 20 31 30   1 also has a 10
1420: 30 2d 62 79 74 65 0a 2a 2a 20 66 69 6c 65 20 68  0-byte.** file h
1430: 65 61 64 65 72 20 74 68 61 74 20 6f 63 63 75 72  eader that occur
1440: 73 20 62 65 66 6f 72 65 20 74 68 65 20 70 61 67  s before the pag
1450: 65 20 68 65 61 64 65 72 2e 0a 2a 2a 0a 2a 2a 20  e header..**.** 
1460: 20 20 20 20 20 7c 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d       |----------
1470: 2d 2d 2d 2d 2d 2d 7c 0a 2a 2a 20 20 20 20 20 20  ------|.**      
1480: 7c 20 66 69 6c 65 20 68 65 61 64 65 72 20 20 20  | file header   
1490: 20 7c 20 20 20 31 30 30 20 62 79 74 65 73 2e 20   |   100 bytes. 
14a0: 20 50 61 67 65 20 31 20 6f 6e 6c 79 2e 0a 2a 2a   Page 1 only..**
14b0: 20 20 20 20 20 20 7c 2d 2d 2d 2d 2d 2d 2d 2d 2d        |---------
14c0: 2d 2d 2d 2d 2d 2d 2d 7c 0a 2a 2a 20 20 20 20 20  -------|.**     
14d0: 20 7c 20 70 61 67 65 20 68 65 61 64 65 72 20 20   | page header  
14e0: 20 20 7c 20 20 20 38 20 62 79 74 65 73 20 66 6f    |   8 bytes fo
14f0: 72 20 6c 65 61 76 65 73 2e 20 20 31 32 20 62 79  r leaves.  12 by
1500: 74 65 73 20 66 6f 72 20 69 6e 74 65 72 69 6f 72  tes for interior
1510: 20 6e 6f 64 65 73 0a 2a 2a 20 20 20 20 20 20 7c   nodes.**      |
1520: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
1530: 7c 0a 2a 2a 20 20 20 20 20 20 7c 20 63 65 6c 6c  |.**      | cell
1540: 20 70 6f 69 6e 74 65 72 20 20 20 7c 20 20 20 7c   pointer   |   |
1550: 20 20 32 20 62 79 74 65 73 20 70 65 72 20 63 65    2 bytes per ce
1560: 6c 6c 2e 20 20 53 6f 72 74 65 64 20 6f 72 64 65  ll.  Sorted orde
1570: 72 2e 0a 2a 2a 20 20 20 20 20 20 7c 20 61 72 72  r..**      | arr
1580: 61 79 20 20 20 20 20 20 20 20 20 20 7c 20 20 20  ay          |   
1590: 7c 20 20 47 72 6f 77 73 20 64 6f 77 6e 77 61 72  |  Grows downwar
15a0: 64 0a 2a 2a 20 20 20 20 20 20 7c 20 20 20 20 20  d.**      |     
15b0: 20 20 20 20 20 20 20 20 20 20 20 7c 20 20 20 76             |   v
15c0: 0a 2a 2a 20 20 20 20 20 20 7c 2d 2d 2d 2d 2d 2d  .**      |------
15d0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 7c 0a 2a 2a 20 20  ----------|.**  
15e0: 20 20 20 20 7c 20 75 6e 61 6c 6c 6f 63 61 74 65      | unallocate
15f0: 64 20 20 20 20 7c 0a 2a 2a 20 20 20 20 20 20 7c  d    |.**      |
1600: 20 73 70 61 63 65 20 20 20 20 20 20 20 20 20 20   space          
1610: 7c 0a 2a 2a 20 20 20 20 20 20 7c 2d 2d 2d 2d 2d  |.**      |-----
1620: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 7c 20 20 20 5e  -----------|   ^
1630: 20 20 47 72 6f 77 73 20 75 70 77 61 72 64 73 0a    Grows upwards.
1640: 2a 2a 20 20 20 20 20 20 7c 20 63 65 6c 6c 20 63  **      | cell c
1650: 6f 6e 74 65 6e 74 20 20 20 7c 20 20 20 7c 20 20  ontent   |   |  
1660: 41 72 62 69 74 72 61 72 79 20 6f 72 64 65 72 20  Arbitrary order 
1670: 69 6e 74 65 72 73 70 65 72 73 65 64 20 77 69 74  interspersed wit
1680: 68 20 66 72 65 65 62 6c 6f 63 6b 73 2e 0a 2a 2a  h freeblocks..**
1690: 20 20 20 20 20 20 7c 20 61 72 65 61 20 20 20 20        | area    
16a0: 20 20 20 20 20 20 20 7c 20 20 20 7c 20 20 61 6e         |   |  an
16b0: 64 20 66 72 65 65 20 73 70 61 63 65 20 66 72 61  d free space fra
16c0: 67 6d 65 6e 74 73 2e 0a 2a 2a 20 20 20 20 20 20  gments..**      
16d0: 7c 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  |---------------
16e0: 2d 7c 0a 2a 2a 0a 2a 2a 20 54 68 65 20 70 61 67  -|.**.** The pag
16f0: 65 20 68 65 61 64 65 72 73 20 6c 6f 6f 6b 73 20  e headers looks 
1700: 6c 69 6b 65 20 74 68 69 73 3a 0a 2a 2a 0a 2a 2a  like this:.**.**
1710: 20 20 20 4f 46 46 53 45 54 20 20 20 53 49 5a 45     OFFSET   SIZE
1720: 20 20 20 20 20 44 45 53 43 52 49 50 54 49 4f 4e       DESCRIPTION
1730: 0a 2a 2a 20 20 20 20 20 20 30 20 20 20 20 20 20  .**      0      
1740: 20 31 20 20 20 20 20 20 46 6c 61 67 73 2e 20 31   1      Flags. 1
1750: 3a 20 69 6e 74 6b 65 79 2c 20 32 3a 20 7a 65 72  : intkey, 2: zer
1760: 6f 64 61 74 61 2c 20 34 3a 20 6c 65 61 66 64 61  odata, 4: leafda
1770: 74 61 2c 20 38 3a 20 6c 65 61 66 0a 2a 2a 20 20  ta, 8: leaf.**  
1780: 20 20 20 20 31 20 20 20 20 20 20 20 32 20 20 20      1       2   
1790: 20 20 20 62 79 74 65 20 6f 66 66 73 65 74 20 74     byte offset t
17a0: 6f 20 74 68 65 20 66 69 72 73 74 20 66 72 65 65  o the first free
17b0: 62 6c 6f 63 6b 0a 2a 2a 20 20 20 20 20 20 33 20  block.**      3 
17c0: 20 20 20 20 20 20 32 20 20 20 20 20 20 6e 75 6d        2      num
17d0: 62 65 72 20 6f 66 20 63 65 6c 6c 73 20 6f 6e 20  ber of cells on 
17e0: 74 68 69 73 20 70 61 67 65 0a 2a 2a 20 20 20 20  this page.**    
17f0: 20 20 35 20 20 20 20 20 20 20 32 20 20 20 20 20    5       2     
1800: 20 66 69 72 73 74 20 62 79 74 65 20 6f 66 20 74   first byte of t
1810: 68 65 20 63 65 6c 6c 20 63 6f 6e 74 65 6e 74 20  he cell content 
1820: 61 72 65 61 0a 2a 2a 20 20 20 20 20 20 37 20 20  area.**      7  
1830: 20 20 20 20 20 31 20 20 20 20 20 20 6e 75 6d 62       1      numb
1840: 65 72 20 6f 66 20 66 72 61 67 6d 65 6e 74 65 64  er of fragmented
1850: 20 66 72 65 65 20 62 79 74 65 73 0a 2a 2a 20 20   free bytes.**  
1860: 20 20 20 20 38 20 20 20 20 20 20 20 34 20 20 20      8       4   
1870: 20 20 20 52 69 67 68 74 20 63 68 69 6c 64 20 28     Right child (
1880: 74 68 65 20 50 74 72 28 4e 29 20 76 61 6c 75 65  the Ptr(N) value
1890: 29 2e 20 20 4f 6d 69 74 74 65 64 20 6f 6e 20 6c  ).  Omitted on l
18a0: 65 61 76 65 73 2e 0a 2a 2a 0a 2a 2a 20 54 68 65  eaves..**.** The
18b0: 20 66 6c 61 67 73 20 64 65 66 69 6e 65 20 74 68   flags define th
18c0: 65 20 66 6f 72 6d 61 74 20 6f 66 20 74 68 69 73  e format of this
18d0: 20 62 74 72 65 65 20 70 61 67 65 2e 20 20 54 68   btree page.  Th
18e0: 65 20 6c 65 61 66 20 66 6c 61 67 20 6d 65 61 6e  e leaf flag mean
18f0: 73 20 74 68 61 74 0a 2a 2a 20 74 68 69 73 20 70  s that.** this p
1900: 61 67 65 20 68 61 73 20 6e 6f 20 63 68 69 6c 64  age has no child
1910: 72 65 6e 2e 20 20 54 68 65 20 7a 65 72 6f 64 61  ren.  The zeroda
1920: 74 61 20 66 6c 61 67 20 6d 65 61 6e 73 20 74 68  ta flag means th
1930: 61 74 20 74 68 69 73 20 70 61 67 65 20 63 61 72  at this page car
1940: 72 69 65 73 0a 2a 2a 20 6f 6e 6c 79 20 6b 65 79  ries.** only key
1950: 73 20 61 6e 64 20 6e 6f 20 64 61 74 61 2e 20 20  s and no data.  
1960: 54 68 65 20 69 6e 74 6b 65 79 20 66 6c 61 67 20  The intkey flag 
1970: 6d 65 61 6e 73 20 74 68 61 74 20 74 68 65 20 6b  means that the k
1980: 65 79 20 69 73 20 61 20 69 6e 74 65 67 65 72 0a  ey is a integer.
1990: 2a 2a 20 77 68 69 63 68 20 69 73 20 73 74 6f 72  ** which is stor
19a0: 65 64 20 69 6e 20 74 68 65 20 6b 65 79 20 73 69  ed in the key si
19b0: 7a 65 20 65 6e 74 72 79 20 6f 66 20 74 68 65 20  ze entry of the 
19c0: 63 65 6c 6c 20 68 65 61 64 65 72 20 72 61 74 68  cell header rath
19d0: 65 72 20 74 68 61 6e 20 69 6e 0a 2a 2a 20 74 68  er than in.** th
19e0: 65 20 70 61 79 6c 6f 61 64 20 61 72 65 61 2e 0a  e payload area..
19f0: 2a 2a 0a 2a 2a 20 54 68 65 20 63 65 6c 6c 20 70  **.** The cell p
1a00: 6f 69 6e 74 65 72 20 61 72 72 61 79 20 62 65 67  ointer array beg
1a10: 69 6e 73 20 6f 6e 20 74 68 65 20 66 69 72 73 74  ins on the first
1a20: 20 62 79 74 65 20 61 66 74 65 72 20 74 68 65 20   byte after the 
1a30: 70 61 67 65 20 68 65 61 64 65 72 2e 0a 2a 2a 20  page header..** 
1a40: 54 68 65 20 63 65 6c 6c 20 70 6f 69 6e 74 65 72  The cell pointer
1a50: 20 61 72 72 61 79 20 63 6f 6e 74 61 69 6e 73 20   array contains 
1a60: 7a 65 72 6f 20 6f 72 20 6d 6f 72 65 20 32 2d 62  zero or more 2-b
1a70: 79 74 65 20 6e 75 6d 62 65 72 73 20 77 68 69 63  yte numbers whic
1a80: 68 20 61 72 65 0a 2a 2a 20 6f 66 66 73 65 74 73  h are.** offsets
1a90: 20 66 72 6f 6d 20 74 68 65 20 62 65 67 69 6e 6e   from the beginn
1aa0: 69 6e 67 20 6f 66 20 74 68 65 20 70 61 67 65 20  ing of the page 
1ab0: 74 6f 20 74 68 65 20 63 65 6c 6c 20 63 6f 6e 74  to the cell cont
1ac0: 65 6e 74 20 69 6e 20 74 68 65 20 63 65 6c 6c 0a  ent in the cell.
1ad0: 2a 2a 20 63 6f 6e 74 65 6e 74 20 61 72 65 61 2e  ** content area.
1ae0: 20 20 54 68 65 20 63 65 6c 6c 20 70 6f 69 6e 74    The cell point
1af0: 65 72 73 20 6f 63 63 75 72 20 69 6e 20 73 6f 72  ers occur in sor
1b00: 74 65 64 20 6f 72 64 65 72 2e 20 20 54 68 65 20  ted order.  The 
1b10: 73 79 73 74 65 6d 20 73 74 72 69 76 65 73 0a 2a  system strives.*
1b20: 2a 20 74 6f 20 6b 65 65 70 20 66 72 65 65 20 73  * to keep free s
1b30: 70 61 63 65 20 61 66 74 65 72 20 74 68 65 20 6c  pace after the l
1b40: 61 73 74 20 63 65 6c 6c 20 70 6f 69 6e 74 65 72  ast cell pointer
1b50: 20 73 6f 20 74 68 61 74 20 6e 65 77 20 63 65 6c   so that new cel
1b60: 6c 73 20 63 61 6e 0a 2a 2a 20 62 65 20 65 61 73  ls can.** be eas
1b70: 69 6c 79 20 61 64 64 65 64 20 77 69 74 68 6f 75  ily added withou
1b80: 74 20 68 61 76 69 6e 67 20 74 6f 20 64 65 66 72  t having to defr
1b90: 61 67 6d 65 6e 74 20 74 68 65 20 70 61 67 65 2e  agment the page.
1ba0: 0a 2a 2a 0a 2a 2a 20 43 65 6c 6c 20 63 6f 6e 74  .**.** Cell cont
1bb0: 65 6e 74 20 69 73 20 73 74 6f 72 65 64 20 61 74  ent is stored at
1bc0: 20 74 68 65 20 76 65 72 79 20 65 6e 64 20 6f 66   the very end of
1bd0: 20 74 68 65 20 70 61 67 65 20 61 6e 64 20 67 72   the page and gr
1be0: 6f 77 73 20 74 6f 77 61 72 64 20 74 68 65 0a 2a  ows toward the.*
1bf0: 2a 20 62 65 67 69 6e 6e 69 6e 67 20 6f 66 20 74  * beginning of t
1c00: 68 65 20 70 61 67 65 2e 0a 2a 2a 0a 2a 2a 20 55  he page..**.** U
1c10: 6e 75 73 65 64 20 73 70 61 63 65 20 77 69 74 68  nused space with
1c20: 69 6e 20 74 68 65 20 63 65 6c 6c 20 63 6f 6e 74  in the cell cont
1c30: 65 6e 74 20 61 72 65 61 20 69 73 20 63 6f 6c 6c  ent area is coll
1c40: 65 63 74 65 64 20 69 6e 74 6f 20 61 20 6c 69 6e  ected into a lin
1c50: 6b 65 64 20 6c 69 73 74 20 6f 66 0a 2a 2a 20 66  ked list of.** f
1c60: 72 65 65 62 6c 6f 63 6b 73 2e 20 20 45 61 63 68  reeblocks.  Each
1c70: 20 66 72 65 65 62 6c 6f 63 6b 20 69 73 20 61 74   freeblock is at
1c80: 20 6c 65 61 73 74 20 34 20 62 79 74 65 73 20 69   least 4 bytes i
1c90: 6e 20 73 69 7a 65 2e 20 20 54 68 65 20 62 79 74  n size.  The byt
1ca0: 65 20 6f 66 66 73 65 74 0a 2a 2a 20 74 6f 20 74  e offset.** to t
1cb0: 68 65 20 66 69 72 73 74 20 66 72 65 65 62 6c 6f  he first freeblo
1cc0: 63 6b 20 69 73 20 67 69 76 65 6e 20 69 6e 20 74  ck is given in t
1cd0: 68 65 20 68 65 61 64 65 72 2e 20 20 46 72 65 65  he header.  Free
1ce0: 62 6c 6f 63 6b 73 20 6f 63 63 75 72 20 69 6e 0a  blocks occur in.
1cf0: 2a 2a 20 69 6e 63 72 65 61 73 69 6e 67 20 6f 72  ** increasing or
1d00: 64 65 72 2e 20 20 42 65 63 61 75 73 65 20 61 20  der.  Because a 
1d10: 66 72 65 65 62 6c 6f 63 6b 20 6d 75 73 74 20 62  freeblock must b
1d20: 65 20 61 74 20 6c 65 61 73 74 20 34 20 62 79 74  e at least 4 byt
1d30: 65 73 20 69 6e 20 73 69 7a 65 2c 0a 2a 2a 20 61  es in size,.** a
1d40: 6e 79 20 67 72 6f 75 70 20 6f 66 20 33 20 6f 72  ny group of 3 or
1d50: 20 66 65 77 65 72 20 75 6e 75 73 65 64 20 62 79   fewer unused by
1d60: 74 65 73 20 69 6e 20 74 68 65 20 63 65 6c 6c 20  tes in the cell 
1d70: 63 6f 6e 74 65 6e 74 20 61 72 65 61 20 63 61 6e  content area can
1d80: 6e 6f 74 0a 2a 2a 20 65 78 69 73 74 20 6f 6e 20  not.** exist on 
1d90: 74 68 65 20 66 72 65 65 62 6c 6f 63 6b 20 63 68  the freeblock ch
1da0: 61 69 6e 2e 20 20 41 20 67 72 6f 75 70 20 6f 66  ain.  A group of
1db0: 20 33 20 6f 72 20 66 65 77 65 72 20 66 72 65 65   3 or fewer free
1dc0: 20 62 79 74 65 73 20 69 73 20 63 61 6c 6c 65 64   bytes is called
1dd0: 0a 2a 2a 20 61 20 66 72 61 67 6d 65 6e 74 2e 20  .** a fragment. 
1de0: 20 54 68 65 20 74 6f 74 61 6c 20 6e 75 6d 62 65   The total numbe
1df0: 72 20 6f 66 20 62 79 74 65 73 20 69 6e 20 61 6c  r of bytes in al
1e00: 6c 20 66 72 61 67 6d 65 6e 74 73 20 69 73 20 72  l fragments is r
1e10: 65 63 6f 72 64 65 64 2e 0a 2a 2a 20 69 6e 20 74  ecorded..** in t
1e20: 68 65 20 70 61 67 65 20 68 65 61 64 65 72 20 61  he page header a
1e30: 74 20 6f 66 66 73 65 74 20 37 2e 0a 2a 2a 0a 2a  t offset 7..**.*
1e40: 2a 20 20 20 20 53 49 5a 45 20 20 20 20 44 45 53  *    SIZE    DES
1e50: 43 52 49 50 54 49 4f 4e 0a 2a 2a 20 20 20 20 20  CRIPTION.**     
1e60: 20 32 20 20 20 20 20 42 79 74 65 20 6f 66 66 73   2     Byte offs
1e70: 65 74 20 6f 66 20 74 68 65 20 6e 65 78 74 20 66  et of the next f
1e80: 72 65 65 62 6c 6f 63 6b 0a 2a 2a 20 20 20 20 20  reeblock.**     
1e90: 20 32 20 20 20 20 20 42 79 74 65 73 20 69 6e 20   2     Bytes in 
1ea0: 74 68 69 73 20 66 72 65 65 62 6c 6f 63 6b 0a 2a  this freeblock.*
1eb0: 2a 0a 2a 2a 20 43 65 6c 6c 73 20 61 72 65 20 6f  *.** Cells are o
1ec0: 66 20 76 61 72 69 61 62 6c 65 20 6c 65 6e 67 74  f variable lengt
1ed0: 68 2e 20 20 43 65 6c 6c 73 20 61 72 65 20 73 74  h.  Cells are st
1ee0: 6f 72 65 64 20 69 6e 20 74 68 65 20 63 65 6c 6c  ored in the cell
1ef0: 20 63 6f 6e 74 65 6e 74 20 61 72 65 61 20 61 74   content area at
1f00: 0a 2a 2a 20 74 68 65 20 65 6e 64 20 6f 66 20 74  .** the end of t
1f10: 68 65 20 70 61 67 65 2e 20 20 50 6f 69 6e 74 65  he page.  Pointe
1f20: 72 73 20 74 6f 20 74 68 65 20 63 65 6c 6c 73 20  rs to the cells 
1f30: 61 72 65 20 69 6e 20 74 68 65 20 63 65 6c 6c 20  are in the cell 
1f40: 70 6f 69 6e 74 65 72 20 61 72 72 61 79 0a 2a 2a  pointer array.**
1f50: 20 74 68 61 74 20 69 6d 6d 65 64 69 61 74 65 6c   that immediatel
1f60: 79 20 66 6f 6c 6c 6f 77 73 20 74 68 65 20 70 61  y follows the pa
1f70: 67 65 20 68 65 61 64 65 72 2e 20 20 43 65 6c 6c  ge header.  Cell
1f80: 73 20 69 73 20 6e 6f 74 20 6e 65 63 65 73 73 61  s is not necessa
1f90: 72 69 6c 79 0a 2a 2a 20 63 6f 6e 74 69 67 75 6f  rily.** contiguo
1fa0: 75 73 20 6f 72 20 69 6e 20 6f 72 64 65 72 2c 20  us or in order, 
1fb0: 62 75 74 20 63 65 6c 6c 20 70 6f 69 6e 74 65 72  but cell pointer
1fc0: 73 20 61 72 65 20 63 6f 6e 74 69 67 75 6f 75 73  s are contiguous
1fd0: 20 61 6e 64 20 69 6e 20 6f 72 64 65 72 2e 0a 2a   and in order..*
1fe0: 2a 0a 2a 2a 20 43 65 6c 6c 20 63 6f 6e 74 65 6e  *.** Cell conten
1ff0: 74 20 6d 61 6b 65 73 20 75 73 65 20 6f 66 20 76  t makes use of v
2000: 61 72 69 61 62 6c 65 20 6c 65 6e 67 74 68 20 69  ariable length i
2010: 6e 74 65 67 65 72 73 2e 20 20 41 20 76 61 72 69  ntegers.  A vari
2020: 61 62 6c 65 0a 2a 2a 20 6c 65 6e 67 74 68 20 69  able.** length i
2030: 6e 74 65 67 65 72 20 69 73 20 31 20 74 6f 20 39  nteger is 1 to 9
2040: 20 62 79 74 65 73 20 77 68 65 72 65 20 74 68 65   bytes where the
2050: 20 6c 6f 77 65 72 20 37 20 62 69 74 73 20 6f 66   lower 7 bits of
2060: 20 65 61 63 68 20 0a 2a 2a 20 62 79 74 65 20 61   each .** byte a
2070: 72 65 20 75 73 65 64 2e 20 20 54 68 65 20 69 6e  re used.  The in
2080: 74 65 67 65 72 20 63 6f 6e 73 69 73 74 73 20 6f  teger consists o
2090: 66 20 61 6c 6c 20 62 79 74 65 73 20 74 68 61 74  f all bytes that
20a0: 20 68 61 76 65 20 62 69 74 20 38 20 73 65 74 20   have bit 8 set 
20b0: 61 6e 64 0a 2a 2a 20 74 68 65 20 66 69 72 73 74  and.** the first
20c0: 20 62 79 74 65 20 77 69 74 68 20 62 69 74 20 38   byte with bit 8
20d0: 20 63 6c 65 61 72 2e 20 20 54 68 65 20 6d 6f 73   clear.  The mos
20e0: 74 20 73 69 67 6e 69 66 69 63 61 6e 74 20 62 79  t significant by
20f0: 74 65 20 6f 66 20 74 68 65 20 69 6e 74 65 67 65  te of the intege
2100: 72 0a 2a 2a 20 61 70 70 65 61 72 73 20 66 69 72  r.** appears fir
2110: 73 74 2e 20 20 41 20 76 61 72 69 61 62 6c 65 2d  st.  A variable-
2120: 6c 65 6e 67 74 68 20 69 6e 74 65 67 65 72 20 6d  length integer m
2130: 61 79 20 6e 6f 74 20 62 65 20 6d 6f 72 65 20 74  ay not be more t
2140: 68 61 6e 20 39 20 62 79 74 65 73 20 6c 6f 6e 67  han 9 bytes long
2150: 2e 0a 2a 2a 20 41 73 20 61 20 73 70 65 63 69 61  ..** As a specia
2160: 6c 20 63 61 73 65 2c 20 61 6c 6c 20 38 20 62 79  l case, all 8 by
2170: 74 65 73 20 6f 66 20 74 68 65 20 39 74 68 20 62  tes of the 9th b
2180: 79 74 65 20 61 72 65 20 75 73 65 64 20 61 73 20  yte are used as 
2190: 64 61 74 61 2e 20 20 54 68 69 73 0a 2a 2a 20 61  data.  This.** a
21a0: 6c 6c 6f 77 73 20 61 20 36 34 2d 62 69 74 20 69  llows a 64-bit i
21b0: 6e 74 65 67 65 72 20 74 6f 20 62 65 20 65 6e 63  nteger to be enc
21c0: 6f 64 65 64 20 69 6e 20 39 20 62 79 74 65 73 2e  oded in 9 bytes.
21d0: 0a 2a 2a 0a 2a 2a 20 20 20 20 30 78 30 30 20 20  .**.**    0x00  
21e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
21f0: 20 20 20 20 62 65 63 6f 6d 65 73 20 20 30 78 30      becomes  0x0
2200: 30 30 30 30 30 30 30 0a 2a 2a 20 20 20 20 30 78  0000000.**    0x
2210: 37 66 20 20 20 20 20 20 20 20 20 20 20 20 20 20  7f              
2220: 20 20 20 20 20 20 20 20 62 65 63 6f 6d 65 73 20          becomes 
2230: 20 30 78 30 30 30 30 30 30 37 66 0a 2a 2a 20 20   0x0000007f.**  
2240: 20 20 30 78 38 31 20 30 78 30 30 20 20 20 20 20    0x81 0x00     
2250: 20 20 20 20 20 20 20 20 20 20 20 20 62 65 63 6f              beco
2260: 6d 65 73 20 20 30 78 30 30 30 30 30 30 38 30 0a  mes  0x00000080.
2270: 2a 2a 20 20 20 20 30 78 38 32 20 30 78 30 30 20  **    0x82 0x00 
2280: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2290: 62 65 63 6f 6d 65 73 20 20 30 78 30 30 30 30 30  becomes  0x00000
22a0: 31 30 30 0a 2a 2a 20 20 20 20 30 78 38 30 20 30  100.**    0x80 0
22b0: 78 37 66 20 20 20 20 20 20 20 20 20 20 20 20 20  x7f             
22c0: 20 20 20 20 62 65 63 6f 6d 65 73 20 20 30 78 30      becomes  0x0
22d0: 30 30 30 30 30 37 66 0a 2a 2a 20 20 20 20 30 78  000007f.**    0x
22e0: 38 61 20 30 78 39 31 20 30 78 64 31 20 30 78 61  8a 0x91 0xd1 0xa
22f0: 63 20 30 78 37 38 20 20 62 65 63 6f 6d 65 73 20  c 0x78  becomes 
2300: 20 30 78 31 32 33 34 35 36 37 38 0a 2a 2a 20 20   0x12345678.**  
2310: 20 20 30 78 38 31 20 30 78 38 31 20 30 78 38 31    0x81 0x81 0x81
2320: 20 30 78 38 31 20 30 78 30 31 20 20 62 65 63 6f   0x81 0x01  beco
2330: 6d 65 73 20 20 30 78 31 30 32 30 34 30 38 31 0a  mes  0x10204081.
2340: 2a 2a 0a 2a 2a 20 56 61 72 69 61 62 6c 65 20 6c  **.** Variable l
2350: 65 6e 67 74 68 20 69 6e 74 65 67 65 72 73 20 61  ength integers a
2360: 72 65 20 75 73 65 64 20 66 6f 72 20 72 6f 77 69  re used for rowi
2370: 64 73 20 61 6e 64 20 74 6f 20 68 6f 6c 64 20 74  ds and to hold t
2380: 68 65 20 6e 75 6d 62 65 72 20 6f 66 0a 2a 2a 20  he number of.** 
2390: 62 79 74 65 73 20 6f 66 20 6b 65 79 20 61 6e 64  bytes of key and
23a0: 20 64 61 74 61 20 69 6e 20 61 20 62 74 72 65 65   data in a btree
23b0: 20 63 65 6c 6c 2e 0a 2a 2a 0a 2a 2a 20 54 68 65   cell..**.** The
23c0: 20 63 6f 6e 74 65 6e 74 20 6f 66 20 61 20 63 65   content of a ce
23d0: 6c 6c 20 6c 6f 6f 6b 73 20 6c 69 6b 65 20 74 68  ll looks like th
23e0: 69 73 3a 0a 2a 2a 0a 2a 2a 20 20 20 20 53 49 5a  is:.**.**    SIZ
23f0: 45 20 20 20 20 44 45 53 43 52 49 50 54 49 4f 4e  E    DESCRIPTION
2400: 0a 2a 2a 20 20 20 20 20 20 34 20 20 20 20 20 50  .**      4     P
2410: 61 67 65 20 6e 75 6d 62 65 72 20 6f 66 20 74 68  age number of th
2420: 65 20 6c 65 66 74 20 63 68 69 6c 64 2e 20 4f 6d  e left child. Om
2430: 69 74 74 65 64 20 69 66 20 6c 65 61 66 20 66 6c  itted if leaf fl
2440: 61 67 20 69 73 20 73 65 74 2e 0a 2a 2a 20 20 20  ag is set..**   
2450: 20 20 76 61 72 20 20 20 20 4e 75 6d 62 65 72 20    var    Number 
2460: 6f 66 20 62 79 74 65 73 20 6f 66 20 64 61 74 61  of bytes of data
2470: 2e 20 4f 6d 69 74 74 65 64 20 69 66 20 74 68 65  . Omitted if the
2480: 20 7a 65 72 6f 64 61 74 61 20 66 6c 61 67 20 69   zerodata flag i
2490: 73 20 73 65 74 2e 0a 2a 2a 20 20 20 20 20 76 61  s set..**     va
24a0: 72 20 20 20 20 4e 75 6d 62 65 72 20 6f 66 20 62  r    Number of b
24b0: 79 74 65 73 20 6f 66 20 6b 65 79 2e 20 4f 72 20  ytes of key. Or 
24c0: 74 68 65 20 6b 65 79 20 69 74 73 65 6c 66 20 69  the key itself i
24d0: 66 20 69 6e 74 6b 65 79 20 66 6c 61 67 20 69 73  f intkey flag is
24e0: 20 73 65 74 2e 0a 2a 2a 20 20 20 20 20 20 2a 20   set..**      * 
24f0: 20 20 20 20 50 61 79 6c 6f 61 64 0a 2a 2a 20 20      Payload.**  
2500: 20 20 20 20 34 20 20 20 20 20 46 69 72 73 74 20      4     First 
2510: 70 61 67 65 20 6f 66 20 74 68 65 20 6f 76 65 72  page of the over
2520: 66 6c 6f 77 20 63 68 61 69 6e 2e 20 20 4f 6d 69  flow chain.  Omi
2530: 74 74 65 64 20 69 66 20 6e 6f 20 6f 76 65 72 66  tted if no overf
2540: 6c 6f 77 0a 2a 2a 0a 2a 2a 20 4f 76 65 72 66 6c  low.**.** Overfl
2550: 6f 77 20 70 61 67 65 73 20 66 6f 72 6d 20 61 20  ow pages form a 
2560: 6c 69 6e 6b 65 64 20 6c 69 73 74 2e 20 20 45 61  linked list.  Ea
2570: 63 68 20 70 61 67 65 20 65 78 63 65 70 74 20 74  ch page except t
2580: 68 65 20 6c 61 73 74 20 69 73 20 63 6f 6d 70 6c  he last is compl
2590: 65 74 65 6c 79 0a 2a 2a 20 66 69 6c 6c 65 64 20  etely.** filled 
25a0: 77 69 74 68 20 64 61 74 61 20 28 70 61 67 65 73  with data (pages
25b0: 69 7a 65 20 2d 20 34 20 62 79 74 65 73 29 2e 20  ize - 4 bytes). 
25c0: 20 54 68 65 20 6c 61 73 74 20 70 61 67 65 20 63   The last page c
25d0: 61 6e 20 68 61 76 65 20 61 73 20 6c 69 74 74 6c  an have as littl
25e0: 65 0a 2a 2a 20 61 73 20 31 20 62 79 74 65 20 6f  e.** as 1 byte o
25f0: 66 20 64 61 74 61 2e 0a 2a 2a 0a 2a 2a 20 20 20  f data..**.**   
2600: 20 53 49 5a 45 20 20 20 20 44 45 53 43 52 49 50   SIZE    DESCRIP
2610: 54 49 4f 4e 0a 2a 2a 20 20 20 20 20 20 34 20 20  TION.**      4  
2620: 20 20 20 50 61 67 65 20 6e 75 6d 62 65 72 20 6f     Page number o
2630: 66 20 6e 65 78 74 20 6f 76 65 72 66 6c 6f 77 20  f next overflow 
2640: 70 61 67 65 0a 2a 2a 20 20 20 20 20 20 2a 20 20  page.**      *  
2650: 20 20 20 44 61 74 61 0a 2a 2a 0a 2a 2a 20 46 72     Data.**.** Fr
2660: 65 65 6c 69 73 74 20 70 61 67 65 73 20 63 6f 6d  eelist pages com
2670: 65 20 69 6e 20 74 77 6f 20 73 75 62 74 79 70 65  e in two subtype
2680: 73 3a 20 74 72 75 6e 6b 20 70 61 67 65 73 20 61  s: trunk pages a
2690: 6e 64 20 6c 65 61 66 20 70 61 67 65 73 2e 20 20  nd leaf pages.  
26a0: 54 68 65 0a 2a 2a 20 66 69 6c 65 20 68 65 61 64  The.** file head
26b0: 65 72 20 70 6f 69 6e 74 73 20 74 6f 20 74 68 65  er points to the
26c0: 20 66 69 72 73 74 20 69 6e 20 61 20 6c 69 6e 6b   first in a link
26d0: 65 64 20 6c 69 73 74 20 6f 66 20 74 72 75 6e 6b  ed list of trunk
26e0: 20 70 61 67 65 2e 20 20 45 61 63 68 20 74 72 75   page.  Each tru
26f0: 6e 6b 0a 2a 2a 20 70 61 67 65 20 70 6f 69 6e 74  nk.** page point
2700: 73 20 74 6f 20 6d 75 6c 74 69 70 6c 65 20 6c 65  s to multiple le
2710: 61 66 20 70 61 67 65 73 2e 20 20 54 68 65 20 63  af pages.  The c
2720: 6f 6e 74 65 6e 74 20 6f 66 20 61 20 6c 65 61 66  ontent of a leaf
2730: 20 70 61 67 65 20 69 73 0a 2a 2a 20 75 6e 73 70   page is.** unsp
2740: 65 63 69 66 69 65 64 2e 20 20 41 20 74 72 75 6e  ecified.  A trun
2750: 6b 20 70 61 67 65 20 6c 6f 6f 6b 73 20 6c 69 6b  k page looks lik
2760: 65 20 74 68 69 73 3a 0a 2a 2a 0a 2a 2a 20 20 20  e this:.**.**   
2770: 20 53 49 5a 45 20 20 20 20 44 45 53 43 52 49 50   SIZE    DESCRIP
2780: 54 49 4f 4e 0a 2a 2a 20 20 20 20 20 20 34 20 20  TION.**      4  
2790: 20 20 20 50 61 67 65 20 6e 75 6d 62 65 72 20 6f     Page number o
27a0: 66 20 6e 65 78 74 20 74 72 75 6e 6b 20 70 61 67  f next trunk pag
27b0: 65 0a 2a 2a 20 20 20 20 20 20 34 20 20 20 20 20  e.**      4     
27c0: 4e 75 6d 62 65 72 20 6f 66 20 6c 65 61 66 20 70  Number of leaf p
27d0: 6f 69 6e 74 65 72 73 20 6f 6e 20 74 68 69 73 20  ointers on this 
27e0: 70 61 67 65 0a 2a 2a 20 20 20 20 20 20 2a 20 20  page.**      *  
27f0: 20 20 20 7a 65 72 6f 20 6f 72 20 6d 6f 72 65 20     zero or more 
2800: 70 61 67 65 73 20 6e 75 6d 62 65 72 73 20 6f 66  pages numbers of
2810: 20 6c 65 61 76 65 73 0a 2a 2f 0a 23 69 6e 63 6c   leaves.*/.#incl
2820: 75 64 65 20 22 73 71 6c 69 74 65 49 6e 74 2e 68  ude "sqliteInt.h
2830: 22 0a 0a 0a 2f 2a 20 54 68 65 20 66 6f 6c 6c 6f  ".../* The follo
2840: 77 69 6e 67 20 76 61 6c 75 65 20 69 73 20 74 68  wing value is th
2850: 65 20 6d 61 78 69 6d 75 6d 20 63 65 6c 6c 20 73  e maximum cell s
2860: 69 7a 65 20 61 73 73 75 6d 69 6e 67 20 61 20 6d  ize assuming a m
2870: 61 78 69 6d 75 6d 20 70 61 67 65 0a 2a 2a 20 73  aximum page.** s
2880: 69 7a 65 20 67 69 76 65 20 61 62 6f 76 65 2e 0a  ize give above..
2890: 2a 2f 0a 23 64 65 66 69 6e 65 20 4d 58 5f 43 45  */.#define MX_CE
28a0: 4c 4c 5f 53 49 5a 45 28 70 42 74 29 20 20 28 28  LL_SIZE(pBt)  ((
28b0: 69 6e 74 29 28 70 42 74 2d 3e 70 61 67 65 53 69  int)(pBt->pageSi
28c0: 7a 65 2d 38 29 29 0a 0a 2f 2a 20 54 68 65 20 6d  ze-8))../* The m
28d0: 61 78 69 6d 75 6d 20 6e 75 6d 62 65 72 20 6f 66  aximum number of
28e0: 20 63 65 6c 6c 73 20 6f 6e 20 61 20 73 69 6e 67   cells on a sing
28f0: 6c 65 20 70 61 67 65 20 6f 66 20 74 68 65 20 64  le page of the d
2900: 61 74 61 62 61 73 65 2e 20 20 54 68 69 73 0a 2a  atabase.  This.*
2910: 2a 20 61 73 73 75 6d 65 73 20 61 20 6d 69 6e 69  * assumes a mini
2920: 6d 75 6d 20 63 65 6c 6c 20 73 69 7a 65 20 6f 66  mum cell size of
2930: 20 36 20 62 79 74 65 73 20 20 28 34 20 62 79 74   6 bytes  (4 byt
2940: 65 73 20 66 6f 72 20 74 68 65 20 63 65 6c 6c 20  es for the cell 
2950: 69 74 73 65 6c 66 0a 2a 2a 20 70 6c 75 73 20 32  itself.** plus 2
2960: 20 62 79 74 65 73 20 66 6f 72 20 74 68 65 20 69   bytes for the i
2970: 6e 64 65 78 20 74 6f 20 74 68 65 20 63 65 6c 6c  ndex to the cell
2980: 20 69 6e 20 74 68 65 20 70 61 67 65 20 68 65 61   in the page hea
2990: 64 65 72 29 2e 20 20 53 75 63 68 0a 2a 2a 20 73  der).  Such.** s
29a0: 6d 61 6c 6c 20 63 65 6c 6c 73 20 77 69 6c 6c 20  mall cells will 
29b0: 62 65 20 72 61 72 65 2c 20 62 75 74 20 74 68 65  be rare, but the
29c0: 79 20 61 72 65 20 70 6f 73 73 69 62 6c 65 2e 0a  y are possible..
29d0: 2a 2f 0a 23 64 65 66 69 6e 65 20 4d 58 5f 43 45  */.#define MX_CE
29e0: 4c 4c 28 70 42 74 29 20 28 28 70 42 74 2d 3e 70  LL(pBt) ((pBt->p
29f0: 61 67 65 53 69 7a 65 2d 38 29 2f 36 29 0a 0a 2f  ageSize-8)/6)../
2a00: 2a 20 46 6f 72 77 61 72 64 20 64 65 63 6c 61 72  * Forward declar
2a10: 61 74 69 6f 6e 73 20 2a 2f 0a 74 79 70 65 64 65  ations */.typede
2a20: 66 20 73 74 72 75 63 74 20 4d 65 6d 50 61 67 65  f struct MemPage
2a30: 20 4d 65 6d 50 61 67 65 3b 0a 74 79 70 65 64 65   MemPage;.typede
2a40: 66 20 73 74 72 75 63 74 20 42 74 4c 6f 63 6b 20  f struct BtLock 
2a50: 42 74 4c 6f 63 6b 3b 0a 0a 2f 2a 0a 2a 2a 20 54  BtLock;../*.** T
2a60: 68 69 73 20 69 73 20 61 20 6d 61 67 69 63 20 73  his is a magic s
2a70: 74 72 69 6e 67 20 74 68 61 74 20 61 70 70 65 61  tring that appea
2a80: 72 73 20 61 74 20 74 68 65 20 62 65 67 69 6e 6e  rs at the beginn
2a90: 69 6e 67 20 6f 66 20 65 76 65 72 79 0a 2a 2a 20  ing of every.** 
2aa0: 53 51 4c 69 74 65 20 64 61 74 61 62 61 73 65 20  SQLite database 
2ab0: 69 6e 20 6f 72 64 65 72 20 74 6f 20 69 64 65 6e  in order to iden
2ac0: 74 69 66 79 20 74 68 65 20 66 69 6c 65 20 61 73  tify the file as
2ad0: 20 61 20 72 65 61 6c 20 64 61 74 61 62 61 73 65   a real database
2ae0: 2e 0a 2a 2a 0a 2a 2a 20 59 6f 75 20 63 61 6e 20  ..**.** You can 
2af0: 63 68 61 6e 67 65 20 74 68 69 73 20 76 61 6c 75  change this valu
2b00: 65 20 61 74 20 63 6f 6d 70 69 6c 65 2d 74 69 6d  e at compile-tim
2b10: 65 20 62 79 20 73 70 65 63 69 66 79 69 6e 67 20  e by specifying 
2b20: 61 0a 2a 2a 20 2d 44 53 51 4c 49 54 45 5f 46 49  a.** -DSQLITE_FI
2b30: 4c 45 5f 48 45 41 44 45 52 3d 22 2e 2e 2e 22 20  LE_HEADER="..." 
2b40: 6f 6e 20 74 68 65 20 63 6f 6d 70 69 6c 65 72 20  on the compiler 
2b50: 63 6f 6d 6d 61 6e 64 2d 6c 69 6e 65 2e 20 20 54  command-line.  T
2b60: 68 65 0a 2a 2a 20 68 65 61 64 65 72 20 6d 75 73  he.** header mus
2b70: 74 20 62 65 20 65 78 61 63 74 6c 79 20 31 36 20  t be exactly 16 
2b80: 62 79 74 65 73 20 69 6e 63 6c 75 64 69 6e 67 20  bytes including 
2b90: 74 68 65 20 7a 65 72 6f 2d 74 65 72 6d 69 6e 61  the zero-termina
2ba0: 74 6f 72 20 73 6f 0a 2a 2a 20 74 68 65 20 73 74  tor so.** the st
2bb0: 72 69 6e 67 20 69 74 73 65 6c 66 20 73 68 6f 75  ring itself shou
2bc0: 6c 64 20 62 65 20 31 35 20 63 68 61 72 61 63 74  ld be 15 charact
2bd0: 65 72 73 20 6c 6f 6e 67 2e 20 20 49 66 20 79 6f  ers long.  If yo
2be0: 75 20 63 68 61 6e 67 65 0a 2a 2a 20 74 68 65 20  u change.** the 
2bf0: 68 65 61 64 65 72 2c 20 74 68 65 6e 20 79 6f 75  header, then you
2c00: 72 20 63 75 73 74 6f 6d 20 6c 69 62 72 61 72 79  r custom library
2c10: 20 77 69 6c 6c 20 6e 6f 74 20 62 65 20 61 62 6c   will not be abl
2c20: 65 20 74 6f 20 72 65 61 64 20 0a 2a 2a 20 64 61  e to read .** da
2c30: 74 61 62 61 73 65 73 20 67 65 6e 65 72 61 74 65  tabases generate
2c40: 64 20 62 79 20 74 68 65 20 73 74 61 6e 64 61 72  d by the standar
2c50: 64 20 74 6f 6f 6c 73 20 61 6e 64 20 74 68 65 20  d tools and the 
2c60: 73 74 61 6e 64 61 72 64 20 74 6f 6f 6c 73 0a 2a  standard tools.*
2c70: 2a 20 77 69 6c 6c 20 6e 6f 74 20 62 65 20 61 62  * will not be ab
2c80: 6c 65 20 74 6f 20 72 65 61 64 20 64 61 74 61 62  le to read datab
2c90: 61 73 65 73 20 63 72 65 61 74 65 64 20 62 79 20  ases created by 
2ca0: 79 6f 75 72 20 63 75 73 74 6f 6d 20 6c 69 62 72  your custom libr
2cb0: 61 72 79 2e 0a 2a 2f 0a 23 69 66 6e 64 65 66 20  ary..*/.#ifndef 
2cc0: 53 51 4c 49 54 45 5f 46 49 4c 45 5f 48 45 41 44  SQLITE_FILE_HEAD
2cd0: 45 52 20 2f 2a 20 31 32 33 34 35 36 37 38 39 20  ER /* 123456789 
2ce0: 31 32 33 34 35 36 20 2a 2f 0a 23 20 20 64 65 66  123456 */.#  def
2cf0: 69 6e 65 20 53 51 4c 49 54 45 5f 46 49 4c 45 5f  ine SQLITE_FILE_
2d00: 48 45 41 44 45 52 20 22 53 51 4c 69 74 65 20 66  HEADER "SQLite f
2d10: 6f 72 6d 61 74 20 33 22 0a 23 65 6e 64 69 66 0a  ormat 3".#endif.
2d20: 0a 2f 2a 0a 2a 2a 20 50 61 67 65 20 74 79 70 65  ./*.** Page type
2d30: 20 66 6c 61 67 73 2e 20 20 41 6e 20 4f 52 65 64   flags.  An ORed
2d40: 20 63 6f 6d 62 69 6e 61 74 69 6f 6e 20 6f 66 20   combination of 
2d50: 74 68 65 73 65 20 66 6c 61 67 73 20 61 70 70 65  these flags appe
2d60: 61 72 20 61 73 20 74 68 65 0a 2a 2a 20 66 69 72  ar as the.** fir
2d70: 73 74 20 62 79 74 65 20 6f 66 20 6f 6e 2d 64 69  st byte of on-di
2d80: 73 6b 20 69 6d 61 67 65 20 6f 66 20 65 76 65 72  sk image of ever
2d90: 79 20 42 54 72 65 65 20 70 61 67 65 2e 0a 2a 2f  y BTree page..*/
2da0: 0a 23 64 65 66 69 6e 65 20 50 54 46 5f 49 4e 54  .#define PTF_INT
2db0: 4b 45 59 20 20 20 20 30 78 30 31 0a 23 64 65 66  KEY    0x01.#def
2dc0: 69 6e 65 20 50 54 46 5f 5a 45 52 4f 44 41 54 41  ine PTF_ZERODATA
2dd0: 20 20 30 78 30 32 0a 23 64 65 66 69 6e 65 20 50    0x02.#define P
2de0: 54 46 5f 4c 45 41 46 44 41 54 41 20 20 30 78 30  TF_LEAFDATA  0x0
2df0: 34 0a 23 64 65 66 69 6e 65 20 50 54 46 5f 4c 45  4.#define PTF_LE
2e00: 41 46 20 20 20 20 20 20 30 78 30 38 0a 0a 2f 2a  AF      0x08../*
2e10: 0a 2a 2a 20 41 73 20 65 61 63 68 20 70 61 67 65  .** As each page
2e20: 20 6f 66 20 74 68 65 20 66 69 6c 65 20 69 73 20   of the file is 
2e30: 6c 6f 61 64 65 64 20 69 6e 74 6f 20 6d 65 6d 6f  loaded into memo
2e40: 72 79 2c 20 61 6e 20 69 6e 73 74 61 6e 63 65 20  ry, an instance 
2e50: 6f 66 20 74 68 65 20 66 6f 6c 6c 6f 77 69 6e 67  of the following
2e60: 0a 2a 2a 20 73 74 72 75 63 74 75 72 65 20 69 73  .** structure is
2e70: 20 61 70 70 65 6e 64 65 64 20 61 6e 64 20 69 6e   appended and in
2e80: 69 74 69 61 6c 69 7a 65 64 20 74 6f 20 7a 65 72  itialized to zer
2e90: 6f 2e 20 20 54 68 69 73 20 73 74 72 75 63 74 75  o.  This structu
2ea0: 72 65 20 73 74 6f 72 65 73 0a 2a 2a 20 69 6e 66  re stores.** inf
2eb0: 6f 72 6d 61 74 69 6f 6e 20 61 62 6f 75 74 20 74  ormation about t
2ec0: 68 65 20 70 61 67 65 20 74 68 61 74 20 69 73 20  he page that is 
2ed0: 64 65 63 6f 64 65 64 20 66 72 6f 6d 20 74 68 65  decoded from the
2ee0: 20 72 61 77 20 66 69 6c 65 20 70 61 67 65 2e 0a   raw file page..
2ef0: 2a 2a 0a 2a 2a 20 54 68 65 20 70 50 61 72 65 6e  **.** The pParen
2f00: 74 20 66 69 65 6c 64 20 70 6f 69 6e 74 73 20 62  t field points b
2f10: 61 63 6b 20 74 6f 20 74 68 65 20 70 61 72 65 6e  ack to the paren
2f20: 74 20 70 61 67 65 2e 20 20 54 68 69 73 20 61 6c  t page.  This al
2f30: 6c 6f 77 73 20 75 73 20 74 6f 0a 2a 2a 20 77 61  lows us to.** wa
2f40: 6c 6b 20 75 70 20 74 68 65 20 42 54 72 65 65 20  lk up the BTree 
2f50: 66 72 6f 6d 20 61 6e 79 20 6c 65 61 66 20 74 6f  from any leaf to
2f60: 20 74 68 65 20 72 6f 6f 74 2e 20 20 43 61 72 65   the root.  Care
2f70: 20 6d 75 73 74 20 62 65 20 74 61 6b 65 6e 20 74   must be taken t
2f80: 6f 0a 2a 2a 20 75 6e 72 65 66 28 29 20 74 68 65  o.** unref() the
2f90: 20 70 61 72 65 6e 74 20 70 61 67 65 20 70 6f 69   parent page poi
2fa0: 6e 74 65 72 20 77 68 65 6e 20 74 68 69 73 20 70  nter when this p
2fb0: 61 67 65 20 69 73 20 6e 6f 20 6c 6f 6e 67 65 72  age is no longer
2fc0: 20 72 65 66 65 72 65 6e 63 65 64 2e 0a 2a 2a 20   referenced..** 
2fd0: 54 68 65 20 70 61 67 65 44 65 73 74 72 75 63 74  The pageDestruct
2fe0: 6f 72 28 29 20 72 6f 75 74 69 6e 65 20 68 61 6e  or() routine han
2ff0: 64 6c 65 73 20 74 68 61 74 20 63 68 6f 72 65 2e  dles that chore.
3000: 0a 2a 2a 0a 2a 2a 20 41 63 63 65 73 73 20 74 6f  .**.** Access to
3010: 20 61 6c 6c 20 66 69 65 6c 64 73 20 6f 66 20 74   all fields of t
3020: 68 69 73 20 73 74 72 75 63 74 75 72 65 20 69 73  his structure is
3030: 20 63 6f 6e 74 72 6f 6c 6c 65 64 20 62 79 20 74   controlled by t
3040: 68 65 20 6d 75 74 65 78 0a 2a 2a 20 73 74 6f 72  he mutex.** stor
3050: 65 64 20 69 6e 20 4d 65 6d 50 61 67 65 2e 70 42  ed in MemPage.pB
3060: 74 2d 3e 6d 75 74 65 78 2e 0a 2a 2f 0a 73 74 72  t->mutex..*/.str
3070: 75 63 74 20 4d 65 6d 50 61 67 65 20 7b 0a 20 20  uct MemPage {.  
3080: 75 38 20 69 73 49 6e 69 74 3b 20 20 20 20 20 20  u8 isInit;      
3090: 20 20 20 20 20 2f 2a 20 54 72 75 65 20 69 66 20       /* True if 
30a0: 70 72 65 76 69 6f 75 73 6c 79 20 69 6e 69 74 69  previously initi
30b0: 61 6c 69 7a 65 64 2e 20 4d 55 53 54 20 42 45 20  alized. MUST BE 
30c0: 46 49 52 53 54 21 20 2a 2f 0a 20 20 75 38 20 6e  FIRST! */.  u8 n
30d0: 4f 76 65 72 66 6c 6f 77 3b 20 20 20 20 20 20 20  Overflow;       
30e0: 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 6f 76   /* Number of ov
30f0: 65 72 66 6c 6f 77 20 63 65 6c 6c 20 62 6f 64 69  erflow cell bodi
3100: 65 73 20 69 6e 20 61 43 65 6c 6c 5b 5d 20 2a 2f  es in aCell[] */
3110: 0a 20 20 75 38 20 69 6e 74 4b 65 79 3b 20 20 20  .  u8 intKey;   
3120: 20 20 20 20 20 20 20 20 2f 2a 20 54 72 75 65 20          /* True 
3130: 69 66 20 69 6e 74 6b 65 79 20 66 6c 61 67 20 69  if intkey flag i
3140: 73 20 73 65 74 20 2a 2f 0a 20 20 75 38 20 6c 65  s set */.  u8 le
3150: 61 66 3b 20 20 20 20 20 20 20 20 20 20 20 20 20  af;             
3160: 2f 2a 20 54 72 75 65 20 69 66 20 6c 65 61 66 20  /* True if leaf 
3170: 66 6c 61 67 20 69 73 20 73 65 74 20 2a 2f 0a 20  flag is set */. 
3180: 20 75 38 20 68 61 73 44 61 74 61 3b 20 20 20 20   u8 hasData;    
3190: 20 20 20 20 20 20 2f 2a 20 54 72 75 65 20 69 66        /* True if
31a0: 20 74 68 69 73 20 70 61 67 65 20 73 74 6f 72 65   this page store
31b0: 73 20 64 61 74 61 20 2a 2f 0a 20 20 75 38 20 68  s data */.  u8 h
31c0: 64 72 4f 66 66 73 65 74 3b 20 20 20 20 20 20 20  drOffset;       
31d0: 20 2f 2a 20 31 30 30 20 66 6f 72 20 70 61 67 65   /* 100 for page
31e0: 20 31 2e 20 20 30 20 6f 74 68 65 72 77 69 73 65   1.  0 otherwise
31f0: 20 2a 2f 0a 20 20 75 38 20 63 68 69 6c 64 50 74   */.  u8 childPt
3200: 72 53 69 7a 65 3b 20 20 20 20 20 2f 2a 20 30 20  rSize;     /* 0 
3210: 69 66 20 6c 65 61 66 3d 3d 31 2e 20 20 34 20 69  if leaf==1.  4 i
3220: 66 20 6c 65 61 66 3d 3d 30 20 2a 2f 0a 20 20 75  f leaf==0 */.  u
3230: 38 20 6d 61 78 31 62 79 74 65 50 61 79 6c 6f 61  8 max1bytePayloa
3240: 64 3b 20 20 2f 2a 20 6d 69 6e 28 6d 61 78 4c 6f  d;  /* min(maxLo
3250: 63 61 6c 2c 31 32 37 29 20 2a 2f 0a 20 20 75 31  cal,127) */.  u1
3260: 36 20 6d 61 78 4c 6f 63 61 6c 3b 20 20 20 20 20  6 maxLocal;     
3270: 20 20 20 2f 2a 20 43 6f 70 79 20 6f 66 20 42 74     /* Copy of Bt
3280: 53 68 61 72 65 64 2e 6d 61 78 4c 6f 63 61 6c 20  Shared.maxLocal 
3290: 6f 72 20 42 74 53 68 61 72 65 64 2e 6d 61 78 4c  or BtShared.maxL
32a0: 65 61 66 20 2a 2f 0a 20 20 75 31 36 20 6d 69 6e  eaf */.  u16 min
32b0: 4c 6f 63 61 6c 3b 20 20 20 20 20 20 20 20 2f 2a  Local;        /*
32c0: 20 43 6f 70 79 20 6f 66 20 42 74 53 68 61 72 65   Copy of BtShare
32d0: 64 2e 6d 69 6e 4c 6f 63 61 6c 20 6f 72 20 42 74  d.minLocal or Bt
32e0: 53 68 61 72 65 64 2e 6d 69 6e 4c 65 61 66 20 2a  Shared.minLeaf *
32f0: 2f 0a 20 20 75 31 36 20 63 65 6c 6c 4f 66 66 73  /.  u16 cellOffs
3300: 65 74 3b 20 20 20 20 20 20 2f 2a 20 49 6e 64 65  et;      /* Inde
3310: 78 20 69 6e 20 61 44 61 74 61 20 6f 66 20 66 69  x in aData of fi
3320: 72 73 74 20 63 65 6c 6c 20 70 6f 69 6e 74 65 72  rst cell pointer
3330: 20 2a 2f 0a 20 20 75 31 36 20 6e 46 72 65 65 3b   */.  u16 nFree;
3340: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4e 75             /* Nu
3350: 6d 62 65 72 20 6f 66 20 66 72 65 65 20 62 79 74  mber of free byt
3360: 65 73 20 6f 6e 20 74 68 65 20 70 61 67 65 20 2a  es on the page *
3370: 2f 0a 20 20 75 31 36 20 6e 43 65 6c 6c 3b 20 20  /.  u16 nCell;  
3380: 20 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62           /* Numb
3390: 65 72 20 6f 66 20 63 65 6c 6c 73 20 6f 6e 20 74  er of cells on t
33a0: 68 69 73 20 70 61 67 65 2c 20 6c 6f 63 61 6c 20  his page, local 
33b0: 61 6e 64 20 6f 76 66 6c 20 2a 2f 0a 20 20 75 31  and ovfl */.  u1
33c0: 36 20 6d 61 73 6b 50 61 67 65 3b 20 20 20 20 20  6 maskPage;     
33d0: 20 20 20 2f 2a 20 4d 61 73 6b 20 66 6f 72 20 70     /* Mask for p
33e0: 61 67 65 20 6f 66 66 73 65 74 20 2a 2f 0a 20 20  age offset */.  
33f0: 75 31 36 20 61 69 4f 76 66 6c 5b 35 5d 3b 20 20  u16 aiOvfl[5];  
3400: 20 20 20 20 20 2f 2a 20 49 6e 73 65 72 74 20 74       /* Insert t
3410: 68 65 20 69 2d 74 68 20 6f 76 65 72 66 6c 6f 77  he i-th overflow
3420: 20 63 65 6c 6c 20 62 65 66 6f 72 65 20 74 68 65   cell before the
3430: 20 61 69 4f 76 66 6c 2d 74 68 0a 20 20 20 20 20   aiOvfl-th.     
3440: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
3450: 20 20 2a 2a 20 6e 6f 6e 2d 6f 76 65 72 66 6c 6f    ** non-overflo
3460: 77 20 63 65 6c 6c 20 2a 2f 0a 20 20 75 38 20 2a  w cell */.  u8 *
3470: 61 70 4f 76 66 6c 5b 35 5d 3b 20 20 20 20 20 20  apOvfl[5];      
3480: 20 2f 2a 20 50 6f 69 6e 74 65 72 73 20 74 6f 20   /* Pointers to 
3490: 74 68 65 20 62 6f 64 79 20 6f 66 20 6f 76 65 72  the body of over
34a0: 66 6c 6f 77 20 63 65 6c 6c 73 20 2a 2f 0a 20 20  flow cells */.  
34b0: 42 74 53 68 61 72 65 64 20 2a 70 42 74 3b 20 20  BtShared *pBt;  
34c0: 20 20 20 20 20 2f 2a 20 50 6f 69 6e 74 65 72 20       /* Pointer 
34d0: 74 6f 20 42 74 53 68 61 72 65 64 20 74 68 61 74  to BtShared that
34e0: 20 74 68 69 73 20 70 61 67 65 20 69 73 20 70 61   this page is pa
34f0: 72 74 20 6f 66 20 2a 2f 0a 20 20 75 38 20 2a 61  rt of */.  u8 *a
3500: 44 61 74 61 3b 20 20 20 20 20 20 20 20 20 20 20  Data;           
3510: 2f 2a 20 50 6f 69 6e 74 65 72 20 74 6f 20 64 69  /* Pointer to di
3520: 73 6b 20 69 6d 61 67 65 20 6f 66 20 74 68 65 20  sk image of the 
3530: 70 61 67 65 20 64 61 74 61 20 2a 2f 0a 20 20 75  page data */.  u
3540: 38 20 2a 61 44 61 74 61 45 6e 64 3b 20 20 20 20  8 *aDataEnd;    
3550: 20 20 20 20 2f 2a 20 4f 6e 65 20 62 79 74 65 20      /* One byte 
3560: 70 61 73 74 20 74 68 65 20 65 6e 64 20 6f 66 20  past the end of 
3570: 75 73 61 62 6c 65 20 64 61 74 61 20 2a 2f 0a 20  usable data */. 
3580: 20 75 38 20 2a 61 43 65 6c 6c 49 64 78 3b 20 20   u8 *aCellIdx;  
3590: 20 20 20 20 20 20 2f 2a 20 54 68 65 20 63 65 6c        /* The cel
35a0: 6c 20 69 6e 64 65 78 20 61 72 65 61 20 2a 2f 0a  l index area */.
35b0: 20 20 44 62 50 61 67 65 20 2a 70 44 62 50 61 67    DbPage *pDbPag
35c0: 65 3b 20 20 20 20 20 2f 2a 20 50 61 67 65 72 20  e;     /* Pager 
35d0: 70 61 67 65 20 68 61 6e 64 6c 65 20 2a 2f 0a 20  page handle */. 
35e0: 20 50 67 6e 6f 20 70 67 6e 6f 3b 20 20 20 20 20   Pgno pgno;     
35f0: 20 20 20 20 20 20 2f 2a 20 50 61 67 65 20 6e 75        /* Page nu
3600: 6d 62 65 72 20 66 6f 72 20 74 68 69 73 20 70 61  mber for this pa
3610: 67 65 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20  ge */.};../*.** 
3620: 54 68 65 20 69 6e 2d 6d 65 6d 6f 72 79 20 69 6d  The in-memory im
3630: 61 67 65 20 6f 66 20 61 20 64 69 73 6b 20 70 61  age of a disk pa
3640: 67 65 20 68 61 73 20 74 68 65 20 61 75 78 69 6c  ge has the auxil
3650: 69 61 72 79 20 69 6e 66 6f 72 6d 61 74 69 6f 6e  iary information
3660: 20 61 70 70 65 6e 64 65 64 0a 2a 2a 20 74 6f 20   appended.** to 
3670: 74 68 65 20 65 6e 64 2e 20 20 45 58 54 52 41 5f  the end.  EXTRA_
3680: 53 49 5a 45 20 69 73 20 74 68 65 20 6e 75 6d 62  SIZE is the numb
3690: 65 72 20 6f 66 20 62 79 74 65 73 20 6f 66 20 73  er of bytes of s
36a0: 70 61 63 65 20 6e 65 65 64 65 64 20 74 6f 20 68  pace needed to h
36b0: 6f 6c 64 0a 2a 2a 20 74 68 61 74 20 65 78 74 72  old.** that extr
36c0: 61 20 69 6e 66 6f 72 6d 61 74 69 6f 6e 2e 0a 2a  a information..*
36d0: 2f 0a 23 64 65 66 69 6e 65 20 45 58 54 52 41 5f  /.#define EXTRA_
36e0: 53 49 5a 45 20 73 69 7a 65 6f 66 28 4d 65 6d 50  SIZE sizeof(MemP
36f0: 61 67 65 29 0a 0a 2f 2a 0a 2a 2a 20 41 20 6c 69  age)../*.** A li
3700: 6e 6b 65 64 20 6c 69 73 74 20 6f 66 20 74 68 65  nked list of the
3710: 20 66 6f 6c 6c 6f 77 69 6e 67 20 73 74 72 75 63   following struc
3720: 74 75 72 65 73 20 69 73 20 73 74 6f 72 65 64 20  tures is stored 
3730: 61 74 20 42 74 53 68 61 72 65 64 2e 70 4c 6f 63  at BtShared.pLoc
3740: 6b 2e 0a 2a 2a 20 4c 6f 63 6b 73 20 61 72 65 20  k..** Locks are 
3750: 61 64 64 65 64 20 28 6f 72 20 75 70 67 72 61 64  added (or upgrad
3760: 65 64 20 66 72 6f 6d 20 52 45 41 44 5f 4c 4f 43  ed from READ_LOC
3770: 4b 20 74 6f 20 57 52 49 54 45 5f 4c 4f 43 4b 29  K to WRITE_LOCK)
3780: 20 77 68 65 6e 20 61 20 63 75 72 73 6f 72 20 0a   when a cursor .
3790: 2a 2a 20 69 73 20 6f 70 65 6e 65 64 20 6f 6e 20  ** is opened on 
37a0: 74 68 65 20 74 61 62 6c 65 20 77 69 74 68 20 72  the table with r
37b0: 6f 6f 74 20 70 61 67 65 20 42 74 53 68 61 72 65  oot page BtShare
37c0: 64 2e 69 54 61 62 6c 65 2e 20 4c 6f 63 6b 73 20  d.iTable. Locks 
37d0: 61 72 65 20 72 65 6d 6f 76 65 64 0a 2a 2a 20 66  are removed.** f
37e0: 72 6f 6d 20 74 68 69 73 20 6c 69 73 74 20 77 68  rom this list wh
37f0: 65 6e 20 61 20 74 72 61 6e 73 61 63 74 69 6f 6e  en a transaction
3800: 20 69 73 20 63 6f 6d 6d 69 74 74 65 64 20 6f 72   is committed or
3810: 20 72 6f 6c 6c 65 64 20 62 61 63 6b 2c 20 6f 72   rolled back, or
3820: 20 77 68 65 6e 0a 2a 2a 20 61 20 62 74 72 65 65   when.** a btree
3830: 20 68 61 6e 64 6c 65 20 69 73 20 63 6c 6f 73 65   handle is close
3840: 64 2e 0a 2a 2f 0a 73 74 72 75 63 74 20 42 74 4c  d..*/.struct BtL
3850: 6f 63 6b 20 7b 0a 20 20 42 74 72 65 65 20 2a 70  ock {.  Btree *p
3860: 42 74 72 65 65 3b 20 20 20 20 20 20 20 20 2f 2a  Btree;        /*
3870: 20 42 74 72 65 65 20 68 61 6e 64 6c 65 20 68 6f   Btree handle ho
3880: 6c 64 69 6e 67 20 74 68 69 73 20 6c 6f 63 6b 20  lding this lock 
3890: 2a 2f 0a 20 20 50 67 6e 6f 20 69 54 61 62 6c 65  */.  Pgno iTable
38a0: 3b 20 20 20 20 20 20 20 20 20 20 2f 2a 20 52 6f  ;          /* Ro
38b0: 6f 74 20 70 61 67 65 20 6f 66 20 74 61 62 6c 65  ot page of table
38c0: 20 2a 2f 0a 20 20 75 38 20 65 4c 6f 63 6b 3b 20   */.  u8 eLock; 
38d0: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 52              /* R
38e0: 45 41 44 5f 4c 4f 43 4b 20 6f 72 20 57 52 49 54  EAD_LOCK or WRIT
38f0: 45 5f 4c 4f 43 4b 20 2a 2f 0a 20 20 42 74 4c 6f  E_LOCK */.  BtLo
3900: 63 6b 20 2a 70 4e 65 78 74 3b 20 20 20 20 20 20  ck *pNext;      
3910: 20 20 2f 2a 20 4e 65 78 74 20 69 6e 20 42 74 53    /* Next in BtS
3920: 68 61 72 65 64 2e 70 4c 6f 63 6b 20 6c 69 73 74  hared.pLock list
3930: 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 20 43 61 6e 64 69   */.};../* Candi
3940: 64 61 74 65 20 76 61 6c 75 65 73 20 66 6f 72 20  date values for 
3950: 42 74 4c 6f 63 6b 2e 65 4c 6f 63 6b 20 2a 2f 0a  BtLock.eLock */.
3960: 23 64 65 66 69 6e 65 20 52 45 41 44 5f 4c 4f 43  #define READ_LOC
3970: 4b 20 20 20 20 20 31 0a 23 64 65 66 69 6e 65 20  K     1.#define 
3980: 57 52 49 54 45 5f 4c 4f 43 4b 20 20 20 20 32 0a  WRITE_LOCK    2.
3990: 0a 2f 2a 20 41 20 42 74 72 65 65 20 68 61 6e 64  ./* A Btree hand
39a0: 6c 65 0a 2a 2a 0a 2a 2a 20 41 20 64 61 74 61 62  le.**.** A datab
39b0: 61 73 65 20 63 6f 6e 6e 65 63 74 69 6f 6e 20 63  ase connection c
39c0: 6f 6e 74 61 69 6e 73 20 61 20 70 6f 69 6e 74 65  ontains a pointe
39d0: 72 20 74 6f 20 61 6e 20 69 6e 73 74 61 6e 63 65  r to an instance
39e0: 20 6f 66 0a 2a 2a 20 74 68 69 73 20 6f 62 6a 65   of.** this obje
39f0: 63 74 20 66 6f 72 20 65 76 65 72 79 20 64 61 74  ct for every dat
3a00: 61 62 61 73 65 20 66 69 6c 65 20 74 68 61 74 20  abase file that 
3a10: 69 74 20 68 61 73 20 6f 70 65 6e 2e 20 20 54 68  it has open.  Th
3a20: 69 73 20 73 74 72 75 63 74 75 72 65 0a 2a 2a 20  is structure.** 
3a30: 69 73 20 6f 70 61 71 75 65 20 74 6f 20 74 68 65  is opaque to the
3a40: 20 64 61 74 61 62 61 73 65 20 63 6f 6e 6e 65 63   database connec
3a50: 74 69 6f 6e 2e 20 20 54 68 65 20 64 61 74 61 62  tion.  The datab
3a60: 61 73 65 20 63 6f 6e 6e 65 63 74 69 6f 6e 20 63  ase connection c
3a70: 61 6e 6e 6f 74 0a 2a 2a 20 73 65 65 20 74 68 65  annot.** see the
3a80: 20 69 6e 74 65 72 6e 61 6c 73 20 6f 66 20 74 68   internals of th
3a90: 69 73 20 73 74 72 75 63 74 75 72 65 20 61 6e 64  is structure and
3aa0: 20 6f 6e 6c 79 20 64 65 61 6c 73 20 77 69 74 68   only deals with
3ab0: 20 70 6f 69 6e 74 65 72 73 20 74 6f 0a 2a 2a 20   pointers to.** 
3ac0: 74 68 69 73 20 73 74 72 75 63 74 75 72 65 2e 0a  this structure..
3ad0: 2a 2a 0a 2a 2a 20 46 6f 72 20 73 6f 6d 65 20 64  **.** For some d
3ae0: 61 74 61 62 61 73 65 20 66 69 6c 65 73 2c 20 74  atabase files, t
3af0: 68 65 20 73 61 6d 65 20 75 6e 64 65 72 6c 79 69  he same underlyi
3b00: 6e 67 20 64 61 74 61 62 61 73 65 20 63 61 63 68  ng database cach
3b10: 65 20 6d 69 67 68 74 20 62 65 20 0a 2a 2a 20 73  e might be .** s
3b20: 68 61 72 65 64 20 62 65 74 77 65 65 6e 20 6d 75  hared between mu
3b30: 6c 74 69 70 6c 65 20 63 6f 6e 6e 65 63 74 69 6f  ltiple connectio
3b40: 6e 73 2e 20 20 49 6e 20 74 68 61 74 20 63 61 73  ns.  In that cas
3b50: 65 2c 20 65 61 63 68 20 63 6f 6e 6e 65 63 74 69  e, each connecti
3b60: 6f 6e 0a 2a 2a 20 68 61 73 20 69 74 20 6f 77 6e  on.** has it own
3b70: 20 69 6e 73 74 61 6e 63 65 20 6f 66 20 74 68 69   instance of thi
3b80: 73 20 6f 62 6a 65 63 74 2e 20 20 42 75 74 20 65  s object.  But e
3b90: 61 63 68 20 69 6e 73 74 61 6e 63 65 20 6f 66 20  ach instance of 
3ba0: 74 68 69 73 20 6f 62 6a 65 63 74 0a 2a 2a 20 70  this object.** p
3bb0: 6f 69 6e 74 73 20 74 6f 20 74 68 65 20 73 61 6d  oints to the sam
3bc0: 65 20 42 74 53 68 61 72 65 64 20 6f 62 6a 65 63  e BtShared objec
3bd0: 74 2e 20 20 54 68 65 20 64 61 74 61 62 61 73 65  t.  The database
3be0: 20 63 61 63 68 65 20 61 6e 64 20 74 68 65 0a 2a   cache and the.*
3bf0: 2a 20 73 63 68 65 6d 61 20 61 73 73 6f 63 69 61  * schema associa
3c00: 74 65 64 20 77 69 74 68 20 74 68 65 20 64 61 74  ted with the dat
3c10: 61 62 61 73 65 20 66 69 6c 65 20 61 72 65 20 61  abase file are a
3c20: 6c 6c 20 63 6f 6e 74 61 69 6e 65 64 20 77 69 74  ll contained wit
3c30: 68 69 6e 0a 2a 2a 20 74 68 65 20 42 74 53 68 61  hin.** the BtSha
3c40: 72 65 64 20 6f 62 6a 65 63 74 2e 0a 2a 2a 0a 2a  red object..**.*
3c50: 2a 20 41 6c 6c 20 66 69 65 6c 64 73 20 69 6e 20  * All fields in 
3c60: 74 68 69 73 20 73 74 72 75 63 74 75 72 65 20 61  this structure a
3c70: 72 65 20 61 63 63 65 73 73 65 64 20 75 6e 64 65  re accessed unde
3c80: 72 20 73 71 6c 69 74 65 33 2e 6d 75 74 65 78 2e  r sqlite3.mutex.
3c90: 0a 2a 2a 20 54 68 65 20 70 42 74 20 70 6f 69 6e  .** The pBt poin
3ca0: 74 65 72 20 69 74 73 65 6c 66 20 6d 61 79 20 6e  ter itself may n
3cb0: 6f 74 20 62 65 20 63 68 61 6e 67 65 64 20 77 68  ot be changed wh
3cc0: 69 6c 65 20 74 68 65 72 65 20 65 78 69 73 74 73  ile there exists
3cd0: 20 63 75 72 73 6f 72 73 20 0a 2a 2a 20 69 6e 20   cursors .** in 
3ce0: 74 68 65 20 72 65 66 65 72 65 6e 63 65 64 20 42  the referenced B
3cf0: 74 53 68 61 72 65 64 20 74 68 61 74 20 70 6f 69  tShared that poi
3d00: 6e 74 20 62 61 63 6b 20 74 6f 20 74 68 69 73 20  nt back to this 
3d10: 42 74 72 65 65 20 73 69 6e 63 65 20 74 68 6f 73  Btree since thos
3d20: 65 0a 2a 2a 20 63 75 72 73 6f 72 73 20 68 61 76  e.** cursors hav
3d30: 65 20 74 6f 20 67 6f 20 74 68 72 6f 75 67 68 20  e to go through 
3d40: 74 68 69 73 20 42 74 72 65 65 20 74 6f 20 66 69  this Btree to fi
3d50: 6e 64 20 74 68 65 69 72 20 42 74 53 68 61 72 65  nd their BtShare
3d60: 64 20 61 6e 64 0a 2a 2a 20 74 68 65 79 20 6f 66  d and.** they of
3d70: 74 65 6e 20 64 6f 20 73 6f 20 77 69 74 68 6f 75  ten do so withou
3d80: 74 20 68 6f 6c 64 69 6e 67 20 73 71 6c 69 74 65  t holding sqlite
3d90: 33 2e 6d 75 74 65 78 2e 0a 2a 2f 0a 73 74 72 75  3.mutex..*/.stru
3da0: 63 74 20 42 74 72 65 65 20 7b 0a 20 20 73 71 6c  ct Btree {.  sql
3db0: 69 74 65 33 20 2a 64 62 3b 20 20 20 20 20 20 20  ite3 *db;       
3dc0: 2f 2a 20 54 68 65 20 64 61 74 61 62 61 73 65 20  /* The database 
3dd0: 63 6f 6e 6e 65 63 74 69 6f 6e 20 68 6f 6c 64 69  connection holdi
3de0: 6e 67 20 74 68 69 73 20 62 74 72 65 65 20 2a 2f  ng this btree */
3df0: 0a 20 20 42 74 53 68 61 72 65 64 20 2a 70 42 74  .  BtShared *pBt
3e00: 3b 20 20 20 20 20 2f 2a 20 53 68 61 72 61 62 6c  ;     /* Sharabl
3e10: 65 20 63 6f 6e 74 65 6e 74 20 6f 66 20 74 68 69  e content of thi
3e20: 73 20 62 74 72 65 65 20 2a 2f 0a 20 20 75 38 20  s btree */.  u8 
3e30: 69 6e 54 72 61 6e 73 3b 20 20 20 20 20 20 20 20  inTrans;        
3e40: 2f 2a 20 54 52 41 4e 53 5f 4e 4f 4e 45 2c 20 54  /* TRANS_NONE, T
3e50: 52 41 4e 53 5f 52 45 41 44 20 6f 72 20 54 52 41  RANS_READ or TRA
3e60: 4e 53 5f 57 52 49 54 45 20 2a 2f 0a 20 20 75 38  NS_WRITE */.  u8
3e70: 20 73 68 61 72 61 62 6c 65 3b 20 20 20 20 20 20   sharable;      
3e80: 20 2f 2a 20 54 72 75 65 20 69 66 20 77 65 20 63   /* True if we c
3e90: 61 6e 20 73 68 61 72 65 20 70 42 74 20 77 69 74  an share pBt wit
3ea0: 68 20 61 6e 6f 74 68 65 72 20 64 62 20 2a 2f 0a  h another db */.
3eb0: 20 20 75 38 20 6c 6f 63 6b 65 64 3b 20 20 20 20    u8 locked;    
3ec0: 20 20 20 20 20 2f 2a 20 54 72 75 65 20 69 66 20       /* True if 
3ed0: 64 62 20 63 75 72 72 65 6e 74 6c 79 20 68 61 73  db currently has
3ee0: 20 70 42 74 20 6c 6f 63 6b 65 64 20 2a 2f 0a 20   pBt locked */. 
3ef0: 20 69 6e 74 20 77 61 6e 74 54 6f 4c 6f 63 6b 3b   int wantToLock;
3f00: 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66      /* Number of
3f10: 20 6e 65 73 74 65 64 20 63 61 6c 6c 73 20 74 6f   nested calls to
3f20: 20 73 71 6c 69 74 65 33 42 74 72 65 65 45 6e 74   sqlite3BtreeEnt
3f30: 65 72 28 29 20 2a 2f 0a 20 20 69 6e 74 20 6e 42  er() */.  int nB
3f40: 61 63 6b 75 70 3b 20 20 20 20 20 20 20 2f 2a 20  ackup;       /* 
3f50: 4e 75 6d 62 65 72 20 6f 66 20 62 61 63 6b 75 70  Number of backup
3f60: 20 6f 70 65 72 61 74 69 6f 6e 73 20 72 65 61 64   operations read
3f70: 69 6e 67 20 74 68 69 73 20 62 74 72 65 65 20 2a  ing this btree *
3f80: 2f 0a 20 20 42 74 72 65 65 20 2a 70 4e 65 78 74  /.  Btree *pNext
3f90: 3b 20 20 20 20 20 20 2f 2a 20 4c 69 73 74 20 6f  ;      /* List o
3fa0: 66 20 6f 74 68 65 72 20 73 68 61 72 61 62 6c 65  f other sharable
3fb0: 20 42 74 72 65 65 73 20 66 72 6f 6d 20 74 68 65   Btrees from the
3fc0: 20 73 61 6d 65 20 64 62 20 2a 2f 0a 20 20 42 74   same db */.  Bt
3fd0: 72 65 65 20 2a 70 50 72 65 76 3b 20 20 20 20 20  ree *pPrev;     
3fe0: 20 2f 2a 20 42 61 63 6b 20 70 6f 69 6e 74 65 72   /* Back pointer
3ff0: 20 6f 66 20 74 68 65 20 73 61 6d 65 20 6c 69 73   of the same lis
4000: 74 20 2a 2f 0a 23 69 66 6e 64 65 66 20 53 51 4c  t */.#ifndef SQL
4010: 49 54 45 5f 4f 4d 49 54 5f 53 48 41 52 45 44 5f  ITE_OMIT_SHARED_
4020: 43 41 43 48 45 0a 20 20 42 74 4c 6f 63 6b 20 6c  CACHE.  BtLock l
4030: 6f 63 6b 3b 20 20 20 20 20 20 20 2f 2a 20 4f 62  ock;       /* Ob
4040: 6a 65 63 74 20 75 73 65 64 20 74 6f 20 6c 6f 63  ject used to loc
4050: 6b 20 70 61 67 65 20 31 20 2a 2f 0a 23 65 6e 64  k page 1 */.#end
4060: 69 66 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 42 74 72  if.};../*.** Btr
4070: 65 65 2e 69 6e 54 72 61 6e 73 20 6d 61 79 20 74  ee.inTrans may t
4080: 61 6b 65 20 6f 6e 65 20 6f 66 20 74 68 65 20 66  ake one of the f
4090: 6f 6c 6c 6f 77 69 6e 67 20 76 61 6c 75 65 73 2e  ollowing values.
40a0: 0a 2a 2a 0a 2a 2a 20 49 66 20 74 68 65 20 73 68  .**.** If the sh
40b0: 61 72 65 64 2d 64 61 74 61 20 65 78 74 65 6e 73  ared-data extens
40c0: 69 6f 6e 20 69 73 20 65 6e 61 62 6c 65 64 2c 20  ion is enabled, 
40d0: 74 68 65 72 65 20 6d 61 79 20 62 65 20 6d 75 6c  there may be mul
40e0: 74 69 70 6c 65 20 75 73 65 72 73 0a 2a 2a 20 6f  tiple users.** o
40f0: 66 20 74 68 65 20 42 74 72 65 65 20 73 74 72 75  f the Btree stru
4100: 63 74 75 72 65 2e 20 41 74 20 6d 6f 73 74 20 6f  cture. At most o
4110: 6e 65 20 6f 66 20 74 68 65 73 65 20 6d 61 79 20  ne of these may 
4120: 6f 70 65 6e 20 61 20 77 72 69 74 65 20 74 72 61  open a write tra
4130: 6e 73 61 63 74 69 6f 6e 2c 0a 2a 2a 20 62 75 74  nsaction,.** but
4140: 20 61 6e 79 20 6e 75 6d 62 65 72 20 6d 61 79 20   any number may 
4150: 68 61 76 65 20 61 63 74 69 76 65 20 72 65 61 64  have active read
4160: 20 74 72 61 6e 73 61 63 74 69 6f 6e 73 2e 0a 2a   transactions..*
4170: 2f 0a 23 64 65 66 69 6e 65 20 54 52 41 4e 53 5f  /.#define TRANS_
4180: 4e 4f 4e 45 20 20 30 0a 23 64 65 66 69 6e 65 20  NONE  0.#define 
4190: 54 52 41 4e 53 5f 52 45 41 44 20 20 31 0a 23 64  TRANS_READ  1.#d
41a0: 65 66 69 6e 65 20 54 52 41 4e 53 5f 57 52 49 54  efine TRANS_WRIT
41b0: 45 20 32 0a 0a 2f 2a 0a 2a 2a 20 41 6e 20 69 6e  E 2../*.** An in
41c0: 73 74 61 6e 63 65 20 6f 66 20 74 68 69 73 20 6f  stance of this o
41d0: 62 6a 65 63 74 20 72 65 70 72 65 73 65 6e 74 73  bject represents
41e0: 20 61 20 73 69 6e 67 6c 65 20 64 61 74 61 62 61   a single databa
41f0: 73 65 20 66 69 6c 65 2e 0a 2a 2a 20 0a 2a 2a 20  se file..** .** 
4200: 41 20 73 69 6e 67 6c 65 20 64 61 74 61 62 61 73  A single databas
4210: 65 20 66 69 6c 65 20 63 61 6e 20 62 65 20 69 6e  e file can be in
4220: 20 75 73 65 20 61 74 20 74 68 65 20 73 61 6d 65   use at the same
4230: 20 74 69 6d 65 20 62 79 20 74 77 6f 0a 2a 2a 20   time by two.** 
4240: 6f 72 20 6d 6f 72 65 20 64 61 74 61 62 61 73 65  or more database
4250: 20 63 6f 6e 6e 65 63 74 69 6f 6e 73 2e 20 20 57   connections.  W
4260: 68 65 6e 20 74 77 6f 20 6f 72 20 6d 6f 72 65 20  hen two or more 
4270: 63 6f 6e 6e 65 63 74 69 6f 6e 73 20 61 72 65 0a  connections are.
4280: 2a 2a 20 73 68 61 72 69 6e 67 20 74 68 65 20 73  ** sharing the s
4290: 61 6d 65 20 64 61 74 61 62 61 73 65 20 66 69 6c  ame database fil
42a0: 65 2c 20 65 61 63 68 20 63 6f 6e 6e 65 63 74 69  e, each connecti
42b0: 6f 6e 20 68 61 73 20 69 74 20 6f 77 6e 0a 2a 2a  on has it own.**
42c0: 20 70 72 69 76 61 74 65 20 42 74 72 65 65 20 6f   private Btree o
42d0: 62 6a 65 63 74 20 66 6f 72 20 74 68 65 20 66 69  bject for the fi
42e0: 6c 65 20 61 6e 64 20 65 61 63 68 20 6f 66 20 74  le and each of t
42f0: 68 6f 73 65 20 42 74 72 65 65 73 20 70 6f 69 6e  hose Btrees poin
4300: 74 73 0a 2a 2a 20 74 6f 20 74 68 69 73 20 6f 6e  ts.** to this on
4310: 65 20 42 74 53 68 61 72 65 64 20 6f 62 6a 65 63  e BtShared objec
4320: 74 2e 20 20 42 74 53 68 61 72 65 64 2e 6e 52 65  t.  BtShared.nRe
4330: 66 20 69 73 20 74 68 65 20 6e 75 6d 62 65 72 20  f is the number 
4340: 6f 66 0a 2a 2a 20 63 6f 6e 6e 65 63 74 69 6f 6e  of.** connection
4350: 73 20 63 75 72 72 65 6e 74 6c 79 20 73 68 61 72  s currently shar
4360: 69 6e 67 20 74 68 69 73 20 64 61 74 61 62 61 73  ing this databas
4370: 65 20 66 69 6c 65 2e 0a 2a 2a 0a 2a 2a 20 46 69  e file..**.** Fi
4380: 65 6c 64 73 20 69 6e 20 74 68 69 73 20 73 74 72  elds in this str
4390: 75 63 74 75 72 65 20 61 72 65 20 61 63 63 65 73  ucture are acces
43a0: 73 65 64 20 75 6e 64 65 72 20 74 68 65 20 42 74  sed under the Bt
43b0: 53 68 61 72 65 64 2e 6d 75 74 65 78 0a 2a 2a 20  Shared.mutex.** 
43c0: 6d 75 74 65 78 2c 20 65 78 63 65 70 74 20 66 6f  mutex, except fo
43d0: 72 20 6e 52 65 66 20 61 6e 64 20 70 4e 65 78 74  r nRef and pNext
43e0: 20 77 68 69 63 68 20 61 72 65 20 61 63 63 65 73   which are acces
43f0: 73 65 64 20 75 6e 64 65 72 20 74 68 65 0a 2a 2a  sed under the.**
4400: 20 67 6c 6f 62 61 6c 20 53 51 4c 49 54 45 5f 4d   global SQLITE_M
4410: 55 54 45 58 5f 53 54 41 54 49 43 5f 4d 41 53 54  UTEX_STATIC_MAST
4420: 45 52 20 6d 75 74 65 78 2e 20 20 54 68 65 20 70  ER mutex.  The p
4430: 50 61 67 65 72 20 66 69 65 6c 64 0a 2a 2a 20 6d  Pager field.** m
4440: 61 79 20 6e 6f 74 20 62 65 20 6d 6f 64 69 66 69  ay not be modifi
4450: 65 64 20 6f 6e 63 65 20 69 74 20 69 73 20 69 6e  ed once it is in
4460: 69 74 69 61 6c 6c 79 20 73 65 74 20 61 73 20 6c  itially set as l
4470: 6f 6e 67 20 61 73 20 6e 52 65 66 3e 30 2e 0a 2a  ong as nRef>0..*
4480: 2a 20 54 68 65 20 70 53 63 68 65 6d 61 20 66 69  * The pSchema fi
4490: 65 6c 64 20 6d 61 79 20 62 65 20 73 65 74 20 6f  eld may be set o
44a0: 6e 63 65 20 75 6e 64 65 72 20 42 74 53 68 61 72  nce under BtShar
44b0: 65 64 2e 6d 75 74 65 78 20 61 6e 64 0a 2a 2a 20  ed.mutex and.** 
44c0: 74 68 65 72 65 61 66 74 65 72 20 69 73 20 75 6e  thereafter is un
44d0: 63 68 61 6e 67 65 64 20 61 73 20 6c 6f 6e 67 20  changed as long 
44e0: 61 73 20 6e 52 65 66 3e 30 2e 0a 2a 2a 0a 2a 2a  as nRef>0..**.**
44f0: 20 69 73 50 65 6e 64 69 6e 67 3a 0a 2a 2a 0a 2a   isPending:.**.*
4500: 2a 20 20 20 49 66 20 61 20 42 74 53 68 61 72 65  *   If a BtShare
4510: 64 20 63 6c 69 65 6e 74 20 66 61 69 6c 73 20 74  d client fails t
4520: 6f 20 6f 62 74 61 69 6e 20 61 20 77 72 69 74 65  o obtain a write
4530: 2d 6c 6f 63 6b 20 6f 6e 20 61 20 64 61 74 61 62  -lock on a datab
4540: 61 73 65 0a 2a 2a 20 20 20 74 61 62 6c 65 20 28  ase.**   table (
4550: 62 65 63 61 75 73 65 20 74 68 65 72 65 20 65 78  because there ex
4560: 69 73 74 73 20 6f 6e 65 20 6f 72 20 6d 6f 72 65  ists one or more
4570: 20 72 65 61 64 2d 6c 6f 63 6b 73 20 6f 6e 20 74   read-locks on t
4580: 68 65 20 74 61 62 6c 65 29 2c 0a 2a 2a 20 20 20  he table),.**   
4590: 74 68 65 20 73 68 61 72 65 64 2d 63 61 63 68 65  the shared-cache
45a0: 20 65 6e 74 65 72 73 20 27 70 65 6e 64 69 6e 67   enters 'pending
45b0: 2d 6c 6f 63 6b 27 20 73 74 61 74 65 20 61 6e 64  -lock' state and
45c0: 20 69 73 50 65 6e 64 69 6e 67 20 69 73 0a 2a 2a   isPending is.**
45d0: 20 20 20 73 65 74 20 74 6f 20 74 72 75 65 2e 0a     set to true..
45e0: 2a 2a 0a 2a 2a 20 20 20 54 68 65 20 73 68 61 72  **.**   The shar
45f0: 65 64 2d 63 61 63 68 65 20 6c 65 61 76 65 73 20  ed-cache leaves 
4600: 74 68 65 20 27 70 65 6e 64 69 6e 67 20 6c 6f 63  the 'pending loc
4610: 6b 27 20 73 74 61 74 65 20 77 68 65 6e 20 65 69  k' state when ei
4620: 74 68 65 72 20 6f 66 0a 2a 2a 20 20 20 74 68 65  ther of.**   the
4630: 20 66 6f 6c 6c 6f 77 69 6e 67 20 6f 63 63 75 72   following occur
4640: 3a 0a 2a 2a 0a 2a 2a 20 20 20 20 20 31 29 20 54  :.**.**     1) T
4650: 68 65 20 63 75 72 72 65 6e 74 20 77 72 69 74 65  he current write
4660: 72 20 28 42 74 53 68 61 72 65 64 2e 70 57 72 69  r (BtShared.pWri
4670: 74 65 72 29 20 63 6f 6e 63 6c 75 64 65 73 20 69  ter) concludes i
4680: 74 73 20 74 72 61 6e 73 61 63 74 69 6f 6e 2c 20  ts transaction, 
4690: 4f 52 0a 2a 2a 20 20 20 20 20 32 29 20 54 68 65  OR.**     2) The
46a0: 20 6e 75 6d 62 65 72 20 6f 66 20 6c 6f 63 6b 73   number of locks
46b0: 20 68 65 6c 64 20 62 79 20 6f 74 68 65 72 20 63   held by other c
46c0: 6f 6e 6e 65 63 74 69 6f 6e 73 20 64 72 6f 70 73  onnections drops
46d0: 20 74 6f 20 7a 65 72 6f 2e 0a 2a 2a 0a 2a 2a 20   to zero..**.** 
46e0: 20 20 77 68 69 6c 65 20 69 6e 20 74 68 65 20 27    while in the '
46f0: 70 65 6e 64 69 6e 67 2d 6c 6f 63 6b 27 20 73 74  pending-lock' st
4700: 61 74 65 2c 20 6e 6f 20 63 6f 6e 6e 65 63 74 69  ate, no connecti
4710: 6f 6e 20 6d 61 79 20 73 74 61 72 74 20 61 20 6e  on may start a n
4720: 65 77 0a 2a 2a 20 20 20 74 72 61 6e 73 61 63 74  ew.**   transact
4730: 69 6f 6e 2e 0a 2a 2a 0a 2a 2a 20 20 20 54 68 69  ion..**.**   Thi
4740: 73 20 66 65 61 74 75 72 65 20 69 73 20 69 6e 63  s feature is inc
4750: 6c 75 64 65 64 20 74 6f 20 68 65 6c 70 20 70 72  luded to help pr
4760: 65 76 65 6e 74 20 77 72 69 74 65 72 2d 73 74 61  event writer-sta
4770: 72 76 61 74 69 6f 6e 2e 0a 2a 2f 0a 73 74 72 75  rvation..*/.stru
4780: 63 74 20 42 74 53 68 61 72 65 64 20 7b 0a 20 20  ct BtShared {.  
4790: 50 61 67 65 72 20 2a 70 50 61 67 65 72 3b 20 20  Pager *pPager;  
47a0: 20 20 20 20 20 20 2f 2a 20 54 68 65 20 70 61 67        /* The pag
47b0: 65 20 63 61 63 68 65 20 2a 2f 0a 20 20 73 71 6c  e cache */.  sql
47c0: 69 74 65 33 20 2a 64 62 3b 20 20 20 20 20 20 20  ite3 *db;       
47d0: 20 20 20 2f 2a 20 44 61 74 61 62 61 73 65 20 63     /* Database c
47e0: 6f 6e 6e 65 63 74 69 6f 6e 20 63 75 72 72 65 6e  onnection curren
47f0: 74 6c 79 20 75 73 69 6e 67 20 74 68 69 73 20 42  tly using this B
4800: 74 72 65 65 20 2a 2f 0a 20 20 42 74 43 75 72 73  tree */.  BtCurs
4810: 6f 72 20 2a 70 43 75 72 73 6f 72 3b 20 20 20 20  or *pCursor;    
4820: 2f 2a 20 41 20 6c 69 73 74 20 6f 66 20 61 6c 6c  /* A list of all
4830: 20 6f 70 65 6e 20 63 75 72 73 6f 72 73 20 2a 2f   open cursors */
4840: 0a 20 20 4d 65 6d 50 61 67 65 20 2a 70 50 61 67  .  MemPage *pPag
4850: 65 31 3b 20 20 20 20 20 20 2f 2a 20 46 69 72 73  e1;      /* Firs
4860: 74 20 70 61 67 65 20 6f 66 20 74 68 65 20 64 61  t page of the da
4870: 74 61 62 61 73 65 20 2a 2f 0a 20 20 75 38 20 6f  tabase */.  u8 o
4880: 70 65 6e 46 6c 61 67 73 3b 20 20 20 20 20 20 20  penFlags;       
4890: 20 20 2f 2a 20 46 6c 61 67 73 20 74 6f 20 73 71    /* Flags to sq
48a0: 6c 69 74 65 33 42 74 72 65 65 4f 70 65 6e 28 29  lite3BtreeOpen()
48b0: 20 2a 2f 0a 23 69 66 6e 64 65 66 20 53 51 4c 49   */.#ifndef SQLI
48c0: 54 45 5f 4f 4d 49 54 5f 41 55 54 4f 56 41 43 55  TE_OMIT_AUTOVACU
48d0: 55 4d 0a 20 20 75 38 20 61 75 74 6f 56 61 63 75  UM.  u8 autoVacu
48e0: 75 6d 3b 20 20 20 20 20 20 20 20 2f 2a 20 54 72  um;        /* Tr
48f0: 75 65 20 69 66 20 61 75 74 6f 2d 76 61 63 75 75  ue if auto-vacuu
4900: 6d 20 69 73 20 65 6e 61 62 6c 65 64 20 2a 2f 0a  m is enabled */.
4910: 20 20 75 38 20 69 6e 63 72 56 61 63 75 75 6d 3b    u8 incrVacuum;
4920: 20 20 20 20 20 20 20 20 2f 2a 20 54 72 75 65 20          /* True 
4930: 69 66 20 69 6e 63 72 2d 76 61 63 75 75 6d 20 69  if incr-vacuum i
4940: 73 20 65 6e 61 62 6c 65 64 20 2a 2f 0a 20 20 75  s enabled */.  u
4950: 38 20 62 44 6f 54 72 75 6e 63 61 74 65 3b 20 20  8 bDoTruncate;  
4960: 20 20 20 20 20 2f 2a 20 54 72 75 65 20 74 6f 20       /* True to 
4970: 74 72 75 6e 63 61 74 65 20 64 62 20 6f 6e 20 63  truncate db on c
4980: 6f 6d 6d 69 74 20 2a 2f 0a 23 65 6e 64 69 66 0a  ommit */.#endif.
4990: 20 20 75 38 20 69 6e 54 72 61 6e 73 61 63 74 69    u8 inTransacti
49a0: 6f 6e 3b 20 20 20 20 20 2f 2a 20 54 72 61 6e 73  on;     /* Trans
49b0: 61 63 74 69 6f 6e 20 73 74 61 74 65 20 2a 2f 0a  action state */.
49c0: 20 20 75 38 20 6d 61 78 31 62 79 74 65 50 61 79    u8 max1bytePay
49d0: 6c 6f 61 64 3b 20 20 20 2f 2a 20 4d 61 78 69 6d  load;   /* Maxim
49e0: 75 6d 20 66 69 72 73 74 20 62 79 74 65 20 6f 66  um first byte of
49f0: 20 63 65 6c 6c 20 66 6f 72 20 61 20 31 2d 62 79   cell for a 1-by
4a00: 74 65 20 70 61 79 6c 6f 61 64 20 2a 2f 0a 20 20  te payload */.  
4a10: 75 31 36 20 62 74 73 46 6c 61 67 73 3b 20 20 20  u16 btsFlags;   
4a20: 20 20 20 20 20 20 2f 2a 20 42 6f 6f 6c 65 61 6e        /* Boolean
4a30: 20 70 61 72 61 6d 65 74 65 72 73 2e 20 20 53 65   parameters.  Se
4a40: 65 20 42 54 53 5f 2a 20 6d 61 63 72 6f 73 20 62  e BTS_* macros b
4a50: 65 6c 6f 77 20 2a 2f 0a 20 20 75 31 36 20 6d 61  elow */.  u16 ma
4a60: 78 4c 6f 63 61 6c 3b 20 20 20 20 20 20 20 20 20  xLocal;         
4a70: 2f 2a 20 4d 61 78 69 6d 75 6d 20 6c 6f 63 61 6c  /* Maximum local
4a80: 20 70 61 79 6c 6f 61 64 20 69 6e 20 6e 6f 6e 2d   payload in non-
4a90: 4c 45 41 46 44 41 54 41 20 74 61 62 6c 65 73 20  LEAFDATA tables 
4aa0: 2a 2f 0a 20 20 75 31 36 20 6d 69 6e 4c 6f 63 61  */.  u16 minLoca
4ab0: 6c 3b 20 20 20 20 20 20 20 20 20 2f 2a 20 4d 69  l;         /* Mi
4ac0: 6e 69 6d 75 6d 20 6c 6f 63 61 6c 20 70 61 79 6c  nimum local payl
4ad0: 6f 61 64 20 69 6e 20 6e 6f 6e 2d 4c 45 41 46 44  oad in non-LEAFD
4ae0: 41 54 41 20 74 61 62 6c 65 73 20 2a 2f 0a 20 20  ATA tables */.  
4af0: 75 31 36 20 6d 61 78 4c 65 61 66 3b 20 20 20 20  u16 maxLeaf;    
4b00: 20 20 20 20 20 20 2f 2a 20 4d 61 78 69 6d 75 6d        /* Maximum
4b10: 20 6c 6f 63 61 6c 20 70 61 79 6c 6f 61 64 20 69   local payload i
4b20: 6e 20 61 20 4c 45 41 46 44 41 54 41 20 74 61 62  n a LEAFDATA tab
4b30: 6c 65 20 2a 2f 0a 20 20 75 31 36 20 6d 69 6e 4c  le */.  u16 minL
4b40: 65 61 66 3b 20 20 20 20 20 20 20 20 20 20 2f 2a  eaf;          /*
4b50: 20 4d 69 6e 69 6d 75 6d 20 6c 6f 63 61 6c 20 70   Minimum local p
4b60: 61 79 6c 6f 61 64 20 69 6e 20 61 20 4c 45 41 46  ayload in a LEAF
4b70: 44 41 54 41 20 74 61 62 6c 65 20 2a 2f 0a 20 20  DATA table */.  
4b80: 75 33 32 20 70 61 67 65 53 69 7a 65 3b 20 20 20  u32 pageSize;   
4b90: 20 20 20 20 20 20 2f 2a 20 54 6f 74 61 6c 20 6e        /* Total n
4ba0: 75 6d 62 65 72 20 6f 66 20 62 79 74 65 73 20 6f  umber of bytes o
4bb0: 6e 20 61 20 70 61 67 65 20 2a 2f 0a 20 20 75 33  n a page */.  u3
4bc0: 32 20 75 73 61 62 6c 65 53 69 7a 65 3b 20 20 20  2 usableSize;   
4bd0: 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66      /* Number of
4be0: 20 75 73 61 62 6c 65 20 62 79 74 65 73 20 6f 6e   usable bytes on
4bf0: 20 65 61 63 68 20 70 61 67 65 20 2a 2f 0a 20 20   each page */.  
4c00: 69 6e 74 20 6e 54 72 61 6e 73 61 63 74 69 6f 6e  int nTransaction
4c10: 3b 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20  ;     /* Number 
4c20: 6f 66 20 6f 70 65 6e 20 74 72 61 6e 73 61 63 74  of open transact
4c30: 69 6f 6e 73 20 28 72 65 61 64 20 2b 20 77 72 69  ions (read + wri
4c40: 74 65 29 20 2a 2f 0a 20 20 75 33 32 20 6e 50 61  te) */.  u32 nPa
4c50: 67 65 3b 20 20 20 20 20 20 20 20 20 20 20 20 2f  ge;            /
4c60: 2a 20 4e 75 6d 62 65 72 20 6f 66 20 70 61 67 65  * Number of page
4c70: 73 20 69 6e 20 74 68 65 20 64 61 74 61 62 61 73  s in the databas
4c80: 65 20 2a 2f 0a 20 20 76 6f 69 64 20 2a 70 53 63  e */.  void *pSc
4c90: 68 65 6d 61 3b 20 20 20 20 20 20 20 20 2f 2a 20  hema;        /* 
4ca0: 50 6f 69 6e 74 65 72 20 74 6f 20 73 70 61 63 65  Pointer to space
4cb0: 20 61 6c 6c 6f 63 61 74 65 64 20 62 79 20 73 71   allocated by sq
4cc0: 6c 69 74 65 33 42 74 72 65 65 53 63 68 65 6d 61  lite3BtreeSchema
4cd0: 28 29 20 2a 2f 0a 20 20 76 6f 69 64 20 28 2a 78  () */.  void (*x
4ce0: 46 72 65 65 53 63 68 65 6d 61 29 28 76 6f 69 64  FreeSchema)(void
4cf0: 2a 29 3b 20 20 2f 2a 20 44 65 73 74 72 75 63 74  *);  /* Destruct
4d00: 6f 72 20 66 6f 72 20 42 74 53 68 61 72 65 64 2e  or for BtShared.
4d10: 70 53 63 68 65 6d 61 20 2a 2f 0a 20 20 73 71 6c  pSchema */.  sql
4d20: 69 74 65 33 5f 6d 75 74 65 78 20 2a 6d 75 74 65  ite3_mutex *mute
4d30: 78 3b 20 2f 2a 20 4e 6f 6e 2d 72 65 63 75 72 73  x; /* Non-recurs
4d40: 69 76 65 20 6d 75 74 65 78 20 72 65 71 75 69 72  ive mutex requir
4d50: 65 64 20 74 6f 20 61 63 63 65 73 73 20 74 68 69  ed to access thi
4d60: 73 20 6f 62 6a 65 63 74 20 2a 2f 0a 20 20 42 69  s object */.  Bi
4d70: 74 76 65 63 20 2a 70 48 61 73 43 6f 6e 74 65 6e  tvec *pHasConten
4d80: 74 3b 20 20 2f 2a 20 53 65 74 20 6f 66 20 70 61  t;  /* Set of pa
4d90: 67 65 73 20 6d 6f 76 65 64 20 74 6f 20 66 72 65  ges moved to fre
4da0: 65 2d 6c 69 73 74 20 74 68 69 73 20 74 72 61 6e  e-list this tran
4db0: 73 61 63 74 69 6f 6e 20 2a 2f 0a 23 69 66 6e 64  saction */.#ifnd
4dc0: 65 66 20 53 51 4c 49 54 45 5f 4f 4d 49 54 5f 53  ef SQLITE_OMIT_S
4dd0: 48 41 52 45 44 5f 43 41 43 48 45 0a 20 20 69 6e  HARED_CACHE.  in
4de0: 74 20 6e 52 65 66 3b 20 20 20 20 20 20 20 20 20  t nRef;         
4df0: 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66      /* Number of
4e00: 20 72 65 66 65 72 65 6e 63 65 73 20 74 6f 20 74   references to t
4e10: 68 69 73 20 73 74 72 75 63 74 75 72 65 20 2a 2f  his structure */
4e20: 0a 20 20 42 74 53 68 61 72 65 64 20 2a 70 4e 65  .  BtShared *pNe
4e30: 78 74 3b 20 20 20 20 20 20 2f 2a 20 4e 65 78 74  xt;      /* Next
4e40: 20 6f 6e 20 61 20 6c 69 73 74 20 6f 66 20 73 68   on a list of sh
4e50: 61 72 61 62 6c 65 20 42 74 53 68 61 72 65 64 20  arable BtShared 
4e60: 73 74 72 75 63 74 73 20 2a 2f 0a 20 20 42 74 4c  structs */.  BtL
4e70: 6f 63 6b 20 2a 70 4c 6f 63 6b 3b 20 20 20 20 20  ock *pLock;     
4e80: 20 20 20 2f 2a 20 4c 69 73 74 20 6f 66 20 6c 6f     /* List of lo
4e90: 63 6b 73 20 68 65 6c 64 20 6f 6e 20 74 68 69 73  cks held on this
4ea0: 20 73 68 61 72 65 64 2d 62 74 72 65 65 20 73 74   shared-btree st
4eb0: 72 75 63 74 20 2a 2f 0a 20 20 42 74 72 65 65 20  ruct */.  Btree 
4ec0: 2a 70 57 72 69 74 65 72 3b 20 20 20 20 20 20 20  *pWriter;       
4ed0: 2f 2a 20 42 74 72 65 65 20 77 69 74 68 20 63 75  /* Btree with cu
4ee0: 72 72 65 6e 74 6c 79 20 6f 70 65 6e 20 77 72 69  rrently open wri
4ef0: 74 65 20 74 72 61 6e 73 61 63 74 69 6f 6e 20 2a  te transaction *
4f00: 2f 0a 23 65 6e 64 69 66 0a 20 20 75 38 20 2a 70  /.#endif.  u8 *p
4f10: 54 6d 70 53 70 61 63 65 3b 20 20 20 20 20 20 20  TmpSpace;       
4f20: 20 2f 2a 20 42 74 53 68 61 72 65 64 2e 70 61 67   /* BtShared.pag
4f30: 65 53 69 7a 65 20 62 79 74 65 73 20 6f 66 20 73  eSize bytes of s
4f40: 70 61 63 65 20 66 6f 72 20 74 6d 70 20 75 73 65  pace for tmp use
4f50: 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 41 6c   */.};../*.** Al
4f60: 6c 6f 77 65 64 20 76 61 6c 75 65 73 20 66 6f 72  lowed values for
4f70: 20 42 74 53 68 61 72 65 64 2e 62 74 73 46 6c 61   BtShared.btsFla
4f80: 67 73 0a 2a 2f 0a 23 64 65 66 69 6e 65 20 42 54  gs.*/.#define BT
4f90: 53 5f 52 45 41 44 5f 4f 4e 4c 59 20 20 20 20 20  S_READ_ONLY     
4fa0: 20 20 20 30 78 30 30 30 31 20 20 20 2f 2a 20 55     0x0001   /* U
4fb0: 6e 64 65 72 6c 79 69 6e 67 20 66 69 6c 65 20 69  nderlying file i
4fc0: 73 20 72 65 61 64 6f 6e 6c 79 20 2a 2f 0a 23 64  s readonly */.#d
4fd0: 65 66 69 6e 65 20 42 54 53 5f 50 41 47 45 53 49  efine BTS_PAGESI
4fe0: 5a 45 5f 46 49 58 45 44 20 20 20 30 78 30 30 30  ZE_FIXED   0x000
4ff0: 32 20 20 20 2f 2a 20 50 61 67 65 20 73 69 7a 65  2   /* Page size
5000: 20 63 61 6e 20 6e 6f 20 6c 6f 6e 67 65 72 20 62   can no longer b
5010: 65 20 63 68 61 6e 67 65 64 20 2a 2f 0a 23 64 65  e changed */.#de
5020: 66 69 6e 65 20 42 54 53 5f 53 45 43 55 52 45 5f  fine BTS_SECURE_
5030: 44 45 4c 45 54 45 20 20 20 20 30 78 30 30 30 34  DELETE    0x0004
5040: 20 20 20 2f 2a 20 50 52 41 47 4d 41 20 73 65 63     /* PRAGMA sec
5050: 75 72 65 5f 64 65 6c 65 74 65 20 69 73 20 65 6e  ure_delete is en
5060: 61 62 6c 65 64 20 2a 2f 0a 23 64 65 66 69 6e 65  abled */.#define
5070: 20 42 54 53 5f 49 4e 49 54 49 41 4c 4c 59 5f 45   BTS_INITIALLY_E
5080: 4d 50 54 59 20 20 30 78 30 30 30 38 20 20 20 2f  MPTY  0x0008   /
5090: 2a 20 44 61 74 61 62 61 73 65 20 77 61 73 20 65  * Database was e
50a0: 6d 70 74 79 20 61 74 20 74 72 61 6e 73 20 73 74  mpty at trans st
50b0: 61 72 74 20 2a 2f 0a 23 64 65 66 69 6e 65 20 42  art */.#define B
50c0: 54 53 5f 4e 4f 5f 57 41 4c 20 20 20 20 20 20 20  TS_NO_WAL       
50d0: 20 20 20 20 30 78 30 30 31 30 20 20 20 2f 2a 20      0x0010   /* 
50e0: 44 6f 20 6e 6f 74 20 6f 70 65 6e 20 77 72 69 74  Do not open writ
50f0: 65 2d 61 68 65 61 64 2d 6c 6f 67 20 66 69 6c 65  e-ahead-log file
5100: 73 20 2a 2f 0a 23 64 65 66 69 6e 65 20 42 54 53  s */.#define BTS
5110: 5f 45 58 43 4c 55 53 49 56 45 20 20 20 20 20 20  _EXCLUSIVE      
5120: 20 20 30 78 30 30 32 30 20 20 20 2f 2a 20 70 57    0x0020   /* pW
5130: 72 69 74 65 72 20 68 61 73 20 61 6e 20 65 78 63  riter has an exc
5140: 6c 75 73 69 76 65 20 6c 6f 63 6b 20 2a 2f 0a 23  lusive lock */.#
5150: 64 65 66 69 6e 65 20 42 54 53 5f 50 45 4e 44 49  define BTS_PENDI
5160: 4e 47 20 20 20 20 20 20 20 20 20 20 30 78 30 30  NG          0x00
5170: 34 30 20 20 20 2f 2a 20 57 61 69 74 69 6e 67 20  40   /* Waiting 
5180: 66 6f 72 20 72 65 61 64 2d 6c 6f 63 6b 73 20 74  for read-locks t
5190: 6f 20 63 6c 65 61 72 20 2a 2f 0a 0a 2f 2a 0a 2a  o clear */../*.*
51a0: 2a 20 41 6e 20 69 6e 73 74 61 6e 63 65 20 6f 66  * An instance of
51b0: 20 74 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 20 73   the following s
51c0: 74 72 75 63 74 75 72 65 20 69 73 20 75 73 65 64  tructure is used
51d0: 20 74 6f 20 68 6f 6c 64 20 69 6e 66 6f 72 6d 61   to hold informa
51e0: 74 69 6f 6e 0a 2a 2a 20 61 62 6f 75 74 20 61 20  tion.** about a 
51f0: 63 65 6c 6c 2e 20 20 54 68 65 20 70 61 72 73 65  cell.  The parse
5200: 43 65 6c 6c 50 74 72 28 29 20 66 75 6e 63 74 69  CellPtr() functi
5210: 6f 6e 20 66 69 6c 6c 73 20 69 6e 20 74 68 69 73  on fills in this
5220: 20 73 74 72 75 63 74 75 72 65 0a 2a 2a 20 62 61   structure.** ba
5230: 73 65 64 20 6f 6e 20 69 6e 66 6f 72 6d 61 74 69  sed on informati
5240: 6f 6e 20 65 78 74 72 61 63 74 20 66 72 6f 6d 20  on extract from 
5250: 74 68 65 20 72 61 77 20 64 69 73 6b 20 70 61 67  the raw disk pag
5260: 65 2e 0a 2a 2f 0a 74 79 70 65 64 65 66 20 73 74  e..*/.typedef st
5270: 72 75 63 74 20 43 65 6c 6c 49 6e 66 6f 20 43 65  ruct CellInfo Ce
5280: 6c 6c 49 6e 66 6f 3b 0a 73 74 72 75 63 74 20 43  llInfo;.struct C
5290: 65 6c 6c 49 6e 66 6f 20 7b 0a 20 20 69 36 34 20  ellInfo {.  i64 
52a0: 6e 4b 65 79 3b 20 20 20 20 20 20 2f 2a 20 54 68  nKey;      /* Th
52b0: 65 20 6b 65 79 20 66 6f 72 20 49 4e 54 4b 45 59  e key for INTKEY
52c0: 20 74 61 62 6c 65 73 2c 20 6f 72 20 6e 75 6d 62   tables, or numb
52d0: 65 72 20 6f 66 20 62 79 74 65 73 20 69 6e 20 6b  er of bytes in k
52e0: 65 79 20 2a 2f 0a 20 20 75 38 20 2a 70 43 65 6c  ey */.  u8 *pCel
52f0: 6c 3b 20 20 20 20 20 2f 2a 20 50 6f 69 6e 74 65  l;     /* Pointe
5300: 72 20 74 6f 20 74 68 65 20 73 74 61 72 74 20 6f  r to the start o
5310: 66 20 63 65 6c 6c 20 63 6f 6e 74 65 6e 74 20 2a  f cell content *
5320: 2f 0a 20 20 75 33 32 20 6e 44 61 74 61 3b 20 20  /.  u32 nData;  
5330: 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20     /* Number of 
5340: 62 79 74 65 73 20 6f 66 20 64 61 74 61 20 2a 2f  bytes of data */
5350: 0a 20 20 75 33 32 20 6e 50 61 79 6c 6f 61 64 3b  .  u32 nPayload;
5360: 20 20 2f 2a 20 54 6f 74 61 6c 20 61 6d 6f 75 6e    /* Total amoun
5370: 74 20 6f 66 20 70 61 79 6c 6f 61 64 20 2a 2f 0a  t of payload */.
5380: 20 20 75 31 36 20 6e 48 65 61 64 65 72 3b 20 20    u16 nHeader;  
5390: 20 2f 2a 20 53 69 7a 65 20 6f 66 20 74 68 65 20   /* Size of the 
53a0: 63 65 6c 6c 20 63 6f 6e 74 65 6e 74 20 68 65 61  cell content hea
53b0: 64 65 72 20 69 6e 20 62 79 74 65 73 20 2a 2f 0a  der in bytes */.
53c0: 20 20 75 31 36 20 6e 4c 6f 63 61 6c 3b 20 20 20    u16 nLocal;   
53d0: 20 2f 2a 20 41 6d 6f 75 6e 74 20 6f 66 20 70 61   /* Amount of pa
53e0: 79 6c 6f 61 64 20 68 65 6c 64 20 6c 6f 63 61 6c  yload held local
53f0: 6c 79 20 2a 2f 0a 20 20 75 31 36 20 69 4f 76 65  ly */.  u16 iOve
5400: 72 66 6c 6f 77 3b 20 2f 2a 20 4f 66 66 73 65 74  rflow; /* Offset
5410: 20 74 6f 20 6f 76 65 72 66 6c 6f 77 20 70 61 67   to overflow pag
5420: 65 20 6e 75 6d 62 65 72 2e 20 20 5a 65 72 6f 20  e number.  Zero 
5430: 69 66 20 6e 6f 20 6f 76 65 72 66 6c 6f 77 20 2a  if no overflow *
5440: 2f 0a 20 20 75 31 36 20 6e 53 69 7a 65 3b 20 20  /.  u16 nSize;  
5450: 20 20 20 2f 2a 20 53 69 7a 65 20 6f 66 20 74 68     /* Size of th
5460: 65 20 63 65 6c 6c 20 63 6f 6e 74 65 6e 74 20 6f  e cell content o
5470: 6e 20 74 68 65 20 6d 61 69 6e 20 62 2d 74 72 65  n the main b-tre
5480: 65 20 70 61 67 65 20 2a 2f 0a 7d 3b 0a 0a 2f 2a  e page */.};../*
5490: 0a 2a 2a 20 4d 61 78 69 6d 75 6d 20 64 65 70 74  .** Maximum dept
54a0: 68 20 6f 66 20 61 6e 20 53 51 4c 69 74 65 20 42  h of an SQLite B
54b0: 2d 54 72 65 65 20 73 74 72 75 63 74 75 72 65 2e  -Tree structure.
54c0: 20 41 6e 79 20 42 2d 54 72 65 65 20 64 65 65 70   Any B-Tree deep
54d0: 65 72 20 74 68 61 6e 0a 2a 2a 20 74 68 69 73 20  er than.** this 
54e0: 77 69 6c 6c 20 62 65 20 64 65 63 6c 61 72 65 64  will be declared
54f0: 20 63 6f 72 72 75 70 74 2e 20 54 68 69 73 20 76   corrupt. This v
5500: 61 6c 75 65 20 69 73 20 63 61 6c 63 75 6c 61 74  alue is calculat
5510: 65 64 20 62 61 73 65 64 20 6f 6e 20 61 0a 2a 2a  ed based on a.**
5520: 20 6d 61 78 69 6d 75 6d 20 64 61 74 61 62 61 73   maximum databas
5530: 65 20 73 69 7a 65 20 6f 66 20 32 5e 33 31 20 70  e size of 2^31 p
5540: 61 67 65 73 20 61 20 6d 69 6e 69 6d 75 6d 20 66  ages a minimum f
5550: 61 6e 6f 75 74 20 6f 66 20 32 20 66 6f 72 20 61  anout of 2 for a
5560: 0a 2a 2a 20 72 6f 6f 74 2d 6e 6f 64 65 20 61 6e  .** root-node an
5570: 64 20 33 20 66 6f 72 20 61 6c 6c 20 6f 74 68 65  d 3 for all othe
5580: 72 20 69 6e 74 65 72 6e 61 6c 20 6e 6f 64 65 73  r internal nodes
5590: 2e 0a 2a 2a 0a 2a 2a 20 49 66 20 61 20 74 72 65  ..**.** If a tre
55a0: 65 20 74 68 61 74 20 61 70 70 65 61 72 73 20 74  e that appears t
55b0: 6f 20 62 65 20 74 61 6c 6c 65 72 20 74 68 61 6e  o be taller than
55c0: 20 74 68 69 73 20 69 73 20 65 6e 63 6f 75 6e 74   this is encount
55d0: 65 72 65 64 2c 20 69 74 20 69 73 0a 2a 2a 20 61  ered, it is.** a
55e0: 73 73 75 6d 65 64 20 74 68 61 74 20 74 68 65 20  ssumed that the 
55f0: 64 61 74 61 62 61 73 65 20 69 73 20 63 6f 72 72  database is corr
5600: 75 70 74 2e 0a 2a 2f 0a 23 64 65 66 69 6e 65 20  upt..*/.#define 
5610: 42 54 43 55 52 53 4f 52 5f 4d 41 58 5f 44 45 50  BTCURSOR_MAX_DEP
5620: 54 48 20 32 30 0a 0a 2f 2a 0a 2a 2a 20 41 20 63  TH 20../*.** A c
5630: 75 72 73 6f 72 20 69 73 20 61 20 70 6f 69 6e 74  ursor is a point
5640: 65 72 20 74 6f 20 61 20 70 61 72 74 69 63 75 6c  er to a particul
5650: 61 72 20 65 6e 74 72 79 20 77 69 74 68 69 6e 20  ar entry within 
5660: 61 20 70 61 72 74 69 63 75 6c 61 72 0a 2a 2a 20  a particular.** 
5670: 62 2d 74 72 65 65 20 77 69 74 68 69 6e 20 61 20  b-tree within a 
5680: 64 61 74 61 62 61 73 65 20 66 69 6c 65 2e 0a 2a  database file..*
5690: 2a 0a 2a 2a 20 54 68 65 20 65 6e 74 72 79 20 69  *.** The entry i
56a0: 73 20 69 64 65 6e 74 69 66 69 65 64 20 62 79 20  s identified by 
56b0: 69 74 73 20 4d 65 6d 50 61 67 65 20 61 6e 64 20  its MemPage and 
56c0: 74 68 65 20 69 6e 64 65 78 20 69 6e 0a 2a 2a 20  the index in.** 
56d0: 4d 65 6d 50 61 67 65 2e 61 43 65 6c 6c 5b 5d 20  MemPage.aCell[] 
56e0: 6f 66 20 74 68 65 20 65 6e 74 72 79 2e 0a 2a 2a  of the entry..**
56f0: 0a 2a 2a 20 41 20 73 69 6e 67 6c 65 20 64 61 74  .** A single dat
5700: 61 62 61 73 65 20 66 69 6c 65 20 63 61 6e 20 62  abase file can b
5710: 65 20 73 68 61 72 65 64 20 62 79 20 74 77 6f 20  e shared by two 
5720: 6d 6f 72 65 20 64 61 74 61 62 61 73 65 20 63 6f  more database co
5730: 6e 6e 65 63 74 69 6f 6e 73 2c 0a 2a 2a 20 62 75  nnections,.** bu
5740: 74 20 63 75 72 73 6f 72 73 20 63 61 6e 6e 6f 74  t cursors cannot
5750: 20 62 65 20 73 68 61 72 65 64 2e 20 20 45 61 63   be shared.  Eac
5760: 68 20 63 75 72 73 6f 72 20 69 73 20 61 73 73 6f  h cursor is asso
5770: 63 69 61 74 65 64 20 77 69 74 68 20 61 0a 2a 2a  ciated with a.**
5780: 20 70 61 72 74 69 63 75 6c 61 72 20 64 61 74 61   particular data
5790: 62 61 73 65 20 63 6f 6e 6e 65 63 74 69 6f 6e 20  base connection 
57a0: 69 64 65 6e 74 69 66 69 65 64 20 42 74 43 75 72  identified BtCur
57b0: 73 6f 72 2e 70 42 74 72 65 65 2e 64 62 2e 0a 2a  sor.pBtree.db..*
57c0: 2a 0a 2a 2a 20 46 69 65 6c 64 73 20 69 6e 20 74  *.** Fields in t
57d0: 68 69 73 20 73 74 72 75 63 74 75 72 65 20 61 72  his structure ar
57e0: 65 20 61 63 63 65 73 73 65 64 20 75 6e 64 65 72  e accessed under
57f0: 20 74 68 65 20 42 74 53 68 61 72 65 64 2e 6d 75   the BtShared.mu
5800: 74 65 78 0a 2a 2a 20 66 6f 75 6e 64 20 61 74 20  tex.** found at 
5810: 73 65 6c 66 2d 3e 70 42 74 2d 3e 6d 75 74 65 78  self->pBt->mutex
5820: 2e 20 0a 2a 2f 0a 73 74 72 75 63 74 20 42 74 43  . .*/.struct BtC
5830: 75 72 73 6f 72 20 7b 0a 20 20 42 74 72 65 65 20  ursor {.  Btree 
5840: 2a 70 42 74 72 65 65 3b 20 20 20 20 20 20 20 20  *pBtree;        
5850: 20 20 20 20 2f 2a 20 54 68 65 20 42 74 72 65 65      /* The Btree
5860: 20 74 6f 20 77 68 69 63 68 20 74 68 69 73 20 63   to which this c
5870: 75 72 73 6f 72 20 62 65 6c 6f 6e 67 73 20 2a 2f  ursor belongs */
5880: 0a 20 20 42 74 53 68 61 72 65 64 20 2a 70 42 74  .  BtShared *pBt
5890: 3b 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20  ;            /* 
58a0: 54 68 65 20 42 74 53 68 61 72 65 64 20 74 68 69  The BtShared thi
58b0: 73 20 63 75 72 73 6f 72 20 70 6f 69 6e 74 73 20  s cursor points 
58c0: 74 6f 20 2a 2f 0a 20 20 42 74 43 75 72 73 6f 72  to */.  BtCursor
58d0: 20 2a 70 4e 65 78 74 2c 20 2a 70 50 72 65 76 3b   *pNext, *pPrev;
58e0: 20 20 2f 2a 20 46 6f 72 6d 73 20 61 20 6c 69 6e    /* Forms a lin
58f0: 6b 65 64 20 6c 69 73 74 20 6f 66 20 61 6c 6c 20  ked list of all 
5900: 63 75 72 73 6f 72 73 20 2a 2f 0a 20 20 73 74 72  cursors */.  str
5910: 75 63 74 20 4b 65 79 49 6e 66 6f 20 2a 70 4b 65  uct KeyInfo *pKe
5920: 79 49 6e 66 6f 3b 20 2f 2a 20 41 72 67 75 6d 65  yInfo; /* Argume
5930: 6e 74 20 70 61 73 73 65 64 20 74 6f 20 63 6f 6d  nt passed to com
5940: 70 61 72 69 73 6f 6e 20 66 75 6e 63 74 69 6f 6e  parison function
5950: 20 2a 2f 0a 23 69 66 6e 64 65 66 20 53 51 4c 49   */.#ifndef SQLI
5960: 54 45 5f 4f 4d 49 54 5f 49 4e 43 52 42 4c 4f 42  TE_OMIT_INCRBLOB
5970: 0a 20 20 50 67 6e 6f 20 2a 61 4f 76 65 72 66 6c  .  Pgno *aOverfl
5980: 6f 77 3b 20 20 20 20 20 20 20 20 20 20 2f 2a 20  ow;          /* 
5990: 43 61 63 68 65 20 6f 66 20 6f 76 65 72 66 6c 6f  Cache of overflo
59a0: 77 20 70 61 67 65 20 6c 6f 63 61 74 69 6f 6e 73  w page locations
59b0: 20 2a 2f 0a 23 65 6e 64 69 66 0a 20 20 50 67 6e   */.#endif.  Pgn
59c0: 6f 20 70 67 6e 6f 52 6f 6f 74 3b 20 20 20 20 20  o pgnoRoot;     
59d0: 20 20 20 20 20 20 20 2f 2a 20 54 68 65 20 72 6f         /* The ro
59e0: 6f 74 20 70 61 67 65 20 6f 66 20 74 68 69 73 20  ot page of this 
59f0: 74 72 65 65 20 2a 2f 0a 20 20 73 71 6c 69 74 65  tree */.  sqlite
5a00: 33 5f 69 6e 74 36 34 20 63 61 63 68 65 64 52 6f  3_int64 cachedRo
5a10: 77 69 64 3b 20 2f 2a 20 4e 65 78 74 20 72 6f 77  wid; /* Next row
5a20: 69 64 20 63 61 63 68 65 2e 20 20 30 20 6d 65 61  id cache.  0 mea
5a30: 6e 73 20 6e 6f 74 20 76 61 6c 69 64 20 2a 2f 0a  ns not valid */.
5a40: 20 20 43 65 6c 6c 49 6e 66 6f 20 69 6e 66 6f 3b    CellInfo info;
5a50: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 41              /* A
5a60: 20 70 61 72 73 65 20 6f 66 20 74 68 65 20 63 65   parse of the ce
5a70: 6c 6c 20 77 65 20 61 72 65 20 70 6f 69 6e 74 69  ll we are pointi
5a80: 6e 67 20 61 74 20 2a 2f 0a 20 20 69 36 34 20 6e  ng at */.  i64 n
5a90: 4b 65 79 3b 20 20 20 20 20 20 20 20 2f 2a 20 53  Key;        /* S
5aa0: 69 7a 65 20 6f 66 20 70 4b 65 79 2c 20 6f 72 20  ize of pKey, or 
5ab0: 6c 61 73 74 20 69 6e 74 65 67 65 72 20 6b 65 79  last integer key
5ac0: 20 2a 2f 0a 20 20 76 6f 69 64 20 2a 70 4b 65 79   */.  void *pKey
5ad0: 3b 20 20 20 20 20 20 2f 2a 20 53 61 76 65 64 20  ;      /* Saved 
5ae0: 6b 65 79 20 74 68 61 74 20 77 61 73 20 63 75 72  key that was cur
5af0: 73 6f 72 27 73 20 6c 61 73 74 20 6b 6e 6f 77 6e  sor's last known
5b00: 20 70 6f 73 69 74 69 6f 6e 20 2a 2f 0a 20 20 69   position */.  i
5b10: 6e 74 20 73 6b 69 70 4e 65 78 74 3b 20 20 20 20  nt skipNext;    
5b20: 2f 2a 20 50 72 65 76 28 29 20 69 73 20 6e 6f 6f  /* Prev() is noo
5b30: 70 20 69 66 20 6e 65 67 61 74 69 76 65 2e 20 4e  p if negative. N
5b40: 65 78 74 28 29 20 69 73 20 6e 6f 6f 70 20 69 66  ext() is noop if
5b50: 20 70 6f 73 69 74 69 76 65 20 2a 2f 0a 20 20 75   positive */.  u
5b60: 38 20 77 72 46 6c 61 67 3b 20 20 20 20 20 20 20  8 wrFlag;       
5b70: 20 20 20 20 20 20 20 20 20 2f 2a 20 54 72 75 65           /* True
5b80: 20 69 66 20 77 72 69 74 61 62 6c 65 20 2a 2f 0a   if writable */.
5b90: 20 20 75 38 20 61 74 4c 61 73 74 3b 20 20 20 20    u8 atLast;    
5ba0: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 43              /* C
5bb0: 75 72 73 6f 72 20 70 6f 69 6e 74 69 6e 67 20 74  ursor pointing t
5bc0: 6f 20 74 68 65 20 6c 61 73 74 20 65 6e 74 72 79  o the last entry
5bd0: 20 2a 2f 0a 20 20 75 38 20 76 61 6c 69 64 4e 4b   */.  u8 validNK
5be0: 65 79 3b 20 20 20 20 20 20 20 20 20 20 20 20 20  ey;             
5bf0: 2f 2a 20 54 72 75 65 20 69 66 20 69 6e 66 6f 2e  /* True if info.
5c00: 6e 4b 65 79 20 69 73 20 76 61 6c 69 64 20 2a 2f  nKey is valid */
5c10: 0a 20 20 75 38 20 65 53 74 61 74 65 3b 20 20 20  .  u8 eState;   
5c20: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
5c30: 4f 6e 65 20 6f 66 20 74 68 65 20 43 55 52 53 4f  One of the CURSO
5c40: 52 5f 58 58 58 20 63 6f 6e 73 74 61 6e 74 73 20  R_XXX constants 
5c50: 28 73 65 65 20 62 65 6c 6f 77 29 20 2a 2f 0a 23  (see below) */.#
5c60: 69 66 6e 64 65 66 20 53 51 4c 49 54 45 5f 4f 4d  ifndef SQLITE_OM
5c70: 49 54 5f 49 4e 43 52 42 4c 4f 42 0a 20 20 75 38  IT_INCRBLOB.  u8
5c80: 20 69 73 49 6e 63 72 62 6c 6f 62 48 61 6e 64 6c   isIncrblobHandl
5c90: 65 3b 20 20 20 20 20 20 2f 2a 20 54 72 75 65 20  e;      /* True 
5ca0: 69 66 20 74 68 69 73 20 63 75 72 73 6f 72 20 69  if this cursor i
5cb0: 73 20 61 6e 20 69 6e 63 72 2e 20 69 6f 20 68 61  s an incr. io ha
5cc0: 6e 64 6c 65 20 2a 2f 0a 23 65 6e 64 69 66 0a 20  ndle */.#endif. 
5cd0: 20 75 38 20 68 69 6e 74 73 3b 20 20 20 20 20 20   u8 hints;      
5ce0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
5cf0: 20 20 20 20 20 20 20 2f 2a 20 41 73 20 63 6f 6e         /* As con
5d00: 66 69 67 75 72 65 64 20 62 79 20 43 75 72 73 6f  figured by Curso
5d10: 72 53 65 74 48 69 6e 74 73 28 29 20 2a 2f 0a 20  rSetHints() */. 
5d20: 20 69 31 36 20 69 50 61 67 65 3b 20 20 20 20 20   i16 iPage;     
5d30: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
5d40: 20 20 20 20 20 20 20 2f 2a 20 49 6e 64 65 78 20         /* Index 
5d50: 6f 66 20 63 75 72 72 65 6e 74 20 70 61 67 65 20  of current page 
5d60: 69 6e 20 61 70 50 61 67 65 20 2a 2f 0a 20 20 75  in apPage */.  u
5d70: 31 36 20 61 69 49 64 78 5b 42 54 43 55 52 53 4f  16 aiIdx[BTCURSO
5d80: 52 5f 4d 41 58 5f 44 45 50 54 48 5d 3b 20 20 20  R_MAX_DEPTH];   
5d90: 20 20 20 20 20 2f 2a 20 43 75 72 72 65 6e 74 20       /* Current 
5da0: 69 6e 64 65 78 20 69 6e 20 61 70 50 61 67 65 5b  index in apPage[
5db0: 69 5d 20 2a 2f 0a 20 20 4d 65 6d 50 61 67 65 20  i] */.  MemPage 
5dc0: 2a 61 70 50 61 67 65 5b 42 54 43 55 52 53 4f 52  *apPage[BTCURSOR
5dd0: 5f 4d 41 58 5f 44 45 50 54 48 5d 3b 20 20 2f 2a  _MAX_DEPTH];  /*
5de0: 20 50 61 67 65 73 20 66 72 6f 6d 20 72 6f 6f 74   Pages from root
5df0: 20 74 6f 20 63 75 72 72 65 6e 74 20 70 61 67 65   to current page
5e00: 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 50 6f   */.};../*.** Po
5e10: 74 65 6e 74 69 61 6c 20 76 61 6c 75 65 73 20 66  tential values f
5e20: 6f 72 20 42 74 43 75 72 73 6f 72 2e 65 53 74 61  or BtCursor.eSta
5e30: 74 65 2e 0a 2a 2a 0a 2a 2a 20 43 55 52 53 4f 52  te..**.** CURSOR
5e40: 5f 49 4e 56 41 4c 49 44 3a 0a 2a 2a 20 20 20 43  _INVALID:.**   C
5e50: 75 72 73 6f 72 20 64 6f 65 73 20 6e 6f 74 20 70  ursor does not p
5e60: 6f 69 6e 74 20 74 6f 20 61 20 76 61 6c 69 64 20  oint to a valid 
5e70: 65 6e 74 72 79 2e 20 54 68 69 73 20 63 61 6e 20  entry. This can 
5e80: 68 61 70 70 65 6e 20 28 66 6f 72 20 65 78 61 6d  happen (for exam
5e90: 70 6c 65 29 20 0a 2a 2a 20 20 20 62 65 63 61 75  ple) .**   becau
5ea0: 73 65 20 74 68 65 20 74 61 62 6c 65 20 69 73 20  se the table is 
5eb0: 65 6d 70 74 79 20 6f 72 20 62 65 63 61 75 73 65  empty or because
5ec0: 20 42 74 72 65 65 43 75 72 73 6f 72 46 69 72 73   BtreeCursorFirs
5ed0: 74 28 29 20 68 61 73 20 6e 6f 74 20 62 65 65 6e  t() has not been
5ee0: 0a 2a 2a 20 20 20 63 61 6c 6c 65 64 2e 0a 2a 2a  .**   called..**
5ef0: 0a 2a 2a 20 43 55 52 53 4f 52 5f 56 41 4c 49 44  .** CURSOR_VALID
5f00: 3a 0a 2a 2a 20 20 20 43 75 72 73 6f 72 20 70 6f  :.**   Cursor po
5f10: 69 6e 74 73 20 74 6f 20 61 20 76 61 6c 69 64 20  ints to a valid 
5f20: 65 6e 74 72 79 2e 20 67 65 74 50 61 79 6c 6f 61  entry. getPayloa
5f30: 64 28 29 20 65 74 63 2e 20 6d 61 79 20 62 65 20  d() etc. may be 
5f40: 63 61 6c 6c 65 64 2e 0a 2a 2a 0a 2a 2a 20 43 55  called..**.** CU
5f50: 52 53 4f 52 5f 53 4b 49 50 4e 45 58 54 3a 0a 2a  RSOR_SKIPNEXT:.*
5f60: 2a 20 20 20 43 75 72 73 6f 72 20 69 73 20 76 61  *   Cursor is va
5f70: 6c 69 64 20 65 78 63 65 70 74 20 74 68 61 74 20  lid except that 
5f80: 74 68 65 20 43 75 72 73 6f 72 2e 73 6b 69 70 4e  the Cursor.skipN
5f90: 65 78 74 20 66 69 65 6c 64 20 69 73 20 6e 6f 6e  ext field is non
5fa0: 2d 7a 65 72 6f 0a 2a 2a 20 20 20 69 6e 64 69 63  -zero.**   indic
5fb0: 61 74 69 6e 67 20 74 68 61 74 20 74 68 65 20 6e  ating that the n
5fc0: 65 78 74 20 73 71 6c 69 74 65 33 42 74 72 65 65  ext sqlite3Btree
5fd0: 4e 65 78 74 28 29 20 6f 72 20 73 71 6c 69 74 65  Next() or sqlite
5fe0: 33 42 74 72 65 65 50 72 65 76 69 6f 75 73 28 29  3BtreePrevious()
5ff0: 0a 2a 2a 20 20 20 6f 70 65 72 61 74 69 6f 6e 20  .**   operation 
6000: 73 68 6f 75 6c 64 20 62 65 20 61 20 6e 6f 2d 6f  should be a no-o
6010: 70 2e 0a 2a 2a 0a 2a 2a 20 43 55 52 53 4f 52 5f  p..**.** CURSOR_
6020: 52 45 51 55 49 52 45 53 45 45 4b 3a 0a 2a 2a 20  REQUIRESEEK:.** 
6030: 20 20 54 68 65 20 74 61 62 6c 65 20 74 68 61 74    The table that
6040: 20 74 68 69 73 20 63 75 72 73 6f 72 20 77 61 73   this cursor was
6050: 20 6f 70 65 6e 65 64 20 6f 6e 20 73 74 69 6c 6c   opened on still
6060: 20 65 78 69 73 74 73 2c 20 62 75 74 20 68 61 73   exists, but has
6070: 20 62 65 65 6e 20 0a 2a 2a 20 20 20 6d 6f 64 69   been .**   modi
6080: 66 69 65 64 20 73 69 6e 63 65 20 74 68 65 20 63  fied since the c
6090: 75 72 73 6f 72 20 77 61 73 20 6c 61 73 74 20 75  ursor was last u
60a0: 73 65 64 2e 20 54 68 65 20 63 75 72 73 6f 72 20  sed. The cursor 
60b0: 70 6f 73 69 74 69 6f 6e 20 69 73 20 73 61 76 65  position is save
60c0: 64 0a 2a 2a 20 20 20 69 6e 20 76 61 72 69 61 62  d.**   in variab
60d0: 6c 65 73 20 42 74 43 75 72 73 6f 72 2e 70 4b 65  les BtCursor.pKe
60e0: 79 20 61 6e 64 20 42 74 43 75 72 73 6f 72 2e 6e  y and BtCursor.n
60f0: 4b 65 79 2e 20 57 68 65 6e 20 61 20 63 75 72 73  Key. When a curs
6100: 6f 72 20 69 73 20 69 6e 20 0a 2a 2a 20 20 20 74  or is in .**   t
6110: 68 69 73 20 73 74 61 74 65 2c 20 72 65 73 74 6f  his state, resto
6120: 72 65 43 75 72 73 6f 72 50 6f 73 69 74 69 6f 6e  reCursorPosition
6130: 28 29 20 63 61 6e 20 62 65 20 63 61 6c 6c 65 64  () can be called
6140: 20 74 6f 20 61 74 74 65 6d 70 74 20 74 6f 0a 2a   to attempt to.*
6150: 2a 20 20 20 73 65 65 6b 20 74 68 65 20 63 75 72  *   seek the cur
6160: 73 6f 72 20 74 6f 20 74 68 65 20 73 61 76 65 64  sor to the saved
6170: 20 70 6f 73 69 74 69 6f 6e 2e 0a 2a 2a 0a 2a 2a   position..**.**
6180: 20 43 55 52 53 4f 52 5f 46 41 55 4c 54 3a 0a 2a   CURSOR_FAULT:.*
6190: 2a 20 20 20 41 20 75 6e 72 65 63 6f 76 65 72 61  *   A unrecovera
61a0: 62 6c 65 20 65 72 72 6f 72 20 28 61 6e 20 49 2f  ble error (an I/
61b0: 4f 20 65 72 72 6f 72 20 6f 72 20 61 20 6d 61 6c  O error or a mal
61c0: 6c 6f 63 20 66 61 69 6c 75 72 65 29 20 68 61 73  loc failure) has
61d0: 20 6f 63 63 75 72 72 65 64 0a 2a 2a 20 20 20 6f   occurred.**   o
61e0: 6e 20 61 20 64 69 66 66 65 72 65 6e 74 20 63 6f  n a different co
61f0: 6e 6e 65 63 74 69 6f 6e 20 74 68 61 74 20 73 68  nnection that sh
6200: 61 72 65 73 20 74 68 65 20 42 74 53 68 61 72 65  ares the BtShare
6210: 64 20 63 61 63 68 65 20 77 69 74 68 20 74 68 69  d cache with thi
6220: 73 0a 2a 2a 20 20 20 63 75 72 73 6f 72 2e 20 20  s.**   cursor.  
6230: 54 68 65 20 65 72 72 6f 72 20 68 61 73 20 6c 65  The error has le
6240: 66 74 20 74 68 65 20 63 61 63 68 65 20 69 6e 20  ft the cache in 
6250: 61 6e 20 69 6e 63 6f 6e 73 69 73 74 65 6e 74 20  an inconsistent 
6260: 73 74 61 74 65 2e 0a 2a 2a 20 20 20 44 6f 20 6e  state..**   Do n
6270: 6f 74 68 69 6e 67 20 65 6c 73 65 20 77 69 74 68  othing else with
6280: 20 74 68 69 73 20 63 75 72 73 6f 72 2e 20 20 41   this cursor.  A
6290: 6e 79 20 61 74 74 65 6d 70 74 20 74 6f 20 75 73  ny attempt to us
62a0: 65 20 74 68 65 20 63 75 72 73 6f 72 0a 2a 2a 20  e the cursor.** 
62b0: 20 20 73 68 6f 75 6c 64 20 72 65 74 75 72 6e 20    should return 
62c0: 74 68 65 20 65 72 72 6f 72 20 63 6f 64 65 20 73  the error code s
62d0: 74 6f 72 65 64 20 69 6e 20 42 74 43 75 72 73 6f  tored in BtCurso
62e0: 72 2e 73 6b 69 70 0a 2a 2f 0a 23 64 65 66 69 6e  r.skip.*/.#defin
62f0: 65 20 43 55 52 53 4f 52 5f 49 4e 56 41 4c 49 44  e CURSOR_INVALID
6300: 20 20 20 20 20 20 20 20 20 20 20 30 0a 23 64 65             0.#de
6310: 66 69 6e 65 20 43 55 52 53 4f 52 5f 56 41 4c 49  fine CURSOR_VALI
6320: 44 20 20 20 20 20 20 20 20 20 20 20 20 20 31 0a  D             1.
6330: 23 64 65 66 69 6e 65 20 43 55 52 53 4f 52 5f 53  #define CURSOR_S
6340: 4b 49 50 4e 45 58 54 20 20 20 20 20 20 20 20 20  KIPNEXT         
6350: 20 32 0a 23 64 65 66 69 6e 65 20 43 55 52 53 4f   2.#define CURSO
6360: 52 5f 52 45 51 55 49 52 45 53 45 45 4b 20 20 20  R_REQUIRESEEK   
6370: 20 20 20 20 33 0a 23 64 65 66 69 6e 65 20 43 55      3.#define CU
6380: 52 53 4f 52 5f 46 41 55 4c 54 20 20 20 20 20 20  RSOR_FAULT      
6390: 20 20 20 20 20 20 20 34 0a 0a 2f 2a 20 0a 2a 2a         4../* .**
63a0: 20 54 68 65 20 64 61 74 61 62 61 73 65 20 70 61   The database pa
63b0: 67 65 20 74 68 65 20 50 45 4e 44 49 4e 47 5f 42  ge the PENDING_B
63c0: 59 54 45 20 6f 63 63 75 70 69 65 73 2e 20 54 68  YTE occupies. Th
63d0: 69 73 20 70 61 67 65 20 69 73 20 6e 65 76 65 72  is page is never
63e0: 20 75 73 65 64 2e 0a 2a 2f 0a 23 20 64 65 66 69   used..*/.# defi
63f0: 6e 65 20 50 45 4e 44 49 4e 47 5f 42 59 54 45 5f  ne PENDING_BYTE_
6400: 50 41 47 45 28 70 42 74 29 20 50 41 47 45 52 5f  PAGE(pBt) PAGER_
6410: 4d 4a 5f 50 47 4e 4f 28 70 42 74 29 0a 0a 2f 2a  MJ_PGNO(pBt)../*
6420: 0a 2a 2a 20 54 68 65 73 65 20 6d 61 63 72 6f 73  .** These macros
6430: 20 64 65 66 69 6e 65 20 74 68 65 20 6c 6f 63 61   define the loca
6440: 74 69 6f 6e 20 6f 66 20 74 68 65 20 70 6f 69 6e  tion of the poin
6450: 74 65 72 2d 6d 61 70 20 65 6e 74 72 79 20 66 6f  ter-map entry fo
6460: 72 20 61 20 0a 2a 2a 20 64 61 74 61 62 61 73 65  r a .** database
6470: 20 70 61 67 65 2e 20 54 68 65 20 66 69 72 73 74   page. The first
6480: 20 61 72 67 75 6d 65 6e 74 20 74 6f 20 65 61 63   argument to eac
6490: 68 20 69 73 20 74 68 65 20 6e 75 6d 62 65 72 20  h is the number 
64a0: 6f 66 20 75 73 61 62 6c 65 0a 2a 2a 20 62 79 74  of usable.** byt
64b0: 65 73 20 6f 6e 20 65 61 63 68 20 70 61 67 65 20  es on each page 
64c0: 6f 66 20 74 68 65 20 64 61 74 61 62 61 73 65 20  of the database 
64d0: 28 6f 66 74 65 6e 20 31 30 32 34 29 2e 20 54 68  (often 1024). Th
64e0: 65 20 73 65 63 6f 6e 64 20 69 73 20 74 68 65 0a  e second is the.
64f0: 2a 2a 20 70 61 67 65 20 6e 75 6d 62 65 72 20 74  ** page number t
6500: 6f 20 6c 6f 6f 6b 20 75 70 20 69 6e 20 74 68 65  o look up in the
6510: 20 70 6f 69 6e 74 65 72 20 6d 61 70 2e 0a 2a 2a   pointer map..**
6520: 0a 2a 2a 20 50 54 52 4d 41 50 5f 50 41 47 45 4e  .** PTRMAP_PAGEN
6530: 4f 20 72 65 74 75 72 6e 73 20 74 68 65 20 64 61  O returns the da
6540: 74 61 62 61 73 65 20 70 61 67 65 20 6e 75 6d 62  tabase page numb
6550: 65 72 20 6f 66 20 74 68 65 20 70 6f 69 6e 74 65  er of the pointe
6560: 72 2d 6d 61 70 0a 2a 2a 20 70 61 67 65 20 74 68  r-map.** page th
6570: 61 74 20 73 74 6f 72 65 73 20 74 68 65 20 72 65  at stores the re
6580: 71 75 69 72 65 64 20 70 6f 69 6e 74 65 72 2e 20  quired pointer. 
6590: 50 54 52 4d 41 50 5f 50 54 52 4f 46 46 53 45 54  PTRMAP_PTROFFSET
65a0: 20 72 65 74 75 72 6e 73 0a 2a 2a 20 74 68 65 20   returns.** the 
65b0: 6f 66 66 73 65 74 20 6f 66 20 74 68 65 20 72 65  offset of the re
65c0: 71 75 65 73 74 65 64 20 6d 61 70 20 65 6e 74 72  quested map entr
65d0: 79 2e 0a 2a 2a 0a 2a 2a 20 49 66 20 74 68 65 20  y..**.** If the 
65e0: 70 67 6e 6f 20 61 72 67 75 6d 65 6e 74 20 70 61  pgno argument pa
65f0: 73 73 65 64 20 74 6f 20 50 54 52 4d 41 50 5f 50  ssed to PTRMAP_P
6600: 41 47 45 4e 4f 20 69 73 20 61 20 70 6f 69 6e 74  AGENO is a point
6610: 65 72 2d 6d 61 70 20 70 61 67 65 2c 0a 2a 2a 20  er-map page,.** 
6620: 74 68 65 6e 20 70 67 6e 6f 20 69 73 20 72 65 74  then pgno is ret
6630: 75 72 6e 65 64 2e 20 53 6f 20 28 70 67 6e 6f 3d  urned. So (pgno=
6640: 3d 50 54 52 4d 41 50 5f 50 41 47 45 4e 4f 28 70  =PTRMAP_PAGENO(p
6650: 67 73 7a 2c 20 70 67 6e 6f 29 29 20 63 61 6e 20  gsz, pgno)) can 
6660: 62 65 0a 2a 2a 20 75 73 65 64 20 74 6f 20 74 65  be.** used to te
6670: 73 74 20 69 66 20 70 67 6e 6f 20 69 73 20 61 20  st if pgno is a 
6680: 70 6f 69 6e 74 65 72 2d 6d 61 70 20 70 61 67 65  pointer-map page
6690: 2e 20 50 54 52 4d 41 50 5f 49 53 50 41 47 45 20  . PTRMAP_ISPAGE 
66a0: 69 6d 70 6c 65 6d 65 6e 74 73 0a 2a 2a 20 74 68  implements.** th
66b0: 69 73 20 74 65 73 74 2e 0a 2a 2f 0a 23 64 65 66  is test..*/.#def
66c0: 69 6e 65 20 50 54 52 4d 41 50 5f 50 41 47 45 4e  ine PTRMAP_PAGEN
66d0: 4f 28 70 42 74 2c 20 70 67 6e 6f 29 20 70 74 72  O(pBt, pgno) ptr
66e0: 6d 61 70 50 61 67 65 6e 6f 28 70 42 74 2c 20 70  mapPageno(pBt, p
66f0: 67 6e 6f 29 0a 23 64 65 66 69 6e 65 20 50 54 52  gno).#define PTR
6700: 4d 41 50 5f 50 54 52 4f 46 46 53 45 54 28 70 67  MAP_PTROFFSET(pg
6710: 70 74 72 6d 61 70 2c 20 70 67 6e 6f 29 20 28 35  ptrmap, pgno) (5
6720: 2a 28 70 67 6e 6f 2d 70 67 70 74 72 6d 61 70 2d  *(pgno-pgptrmap-
6730: 31 29 29 0a 23 64 65 66 69 6e 65 20 50 54 52 4d  1)).#define PTRM
6740: 41 50 5f 49 53 50 41 47 45 28 70 42 74 2c 20 70  AP_ISPAGE(pBt, p
6750: 67 6e 6f 29 20 28 50 54 52 4d 41 50 5f 50 41 47  gno) (PTRMAP_PAG
6760: 45 4e 4f 28 28 70 42 74 29 2c 28 70 67 6e 6f 29  ENO((pBt),(pgno)
6770: 29 3d 3d 28 70 67 6e 6f 29 29 0a 0a 2f 2a 0a 2a  )==(pgno))../*.*
6780: 2a 20 54 68 65 20 70 6f 69 6e 74 65 72 20 6d 61  * The pointer ma
6790: 70 20 69 73 20 61 20 6c 6f 6f 6b 75 70 20 74 61  p is a lookup ta
67a0: 62 6c 65 20 74 68 61 74 20 69 64 65 6e 74 69 66  ble that identif
67b0: 69 65 73 20 74 68 65 20 70 61 72 65 6e 74 20 70  ies the parent p
67c0: 61 67 65 20 66 6f 72 0a 2a 2a 20 65 61 63 68 20  age for.** each 
67d0: 63 68 69 6c 64 20 70 61 67 65 20 69 6e 20 74 68  child page in th
67e0: 65 20 64 61 74 61 62 61 73 65 20 66 69 6c 65 2e  e database file.
67f0: 20 20 54 68 65 20 70 61 72 65 6e 74 20 70 61 67    The parent pag
6800: 65 20 69 73 20 74 68 65 20 70 61 67 65 20 74 68  e is the page th
6810: 61 74 0a 2a 2a 20 63 6f 6e 74 61 69 6e 73 20 61  at.** contains a
6820: 20 70 6f 69 6e 74 65 72 20 74 6f 20 74 68 65 20   pointer to the 
6830: 63 68 69 6c 64 2e 20 20 45 76 65 72 79 20 70 61  child.  Every pa
6840: 67 65 20 69 6e 20 74 68 65 20 64 61 74 61 62 61  ge in the databa
6850: 73 65 20 63 6f 6e 74 61 69 6e 73 0a 2a 2a 20 30  se contains.** 0
6860: 20 6f 72 20 31 20 70 61 72 65 6e 74 20 70 61 67   or 1 parent pag
6870: 65 73 2e 20 20 28 49 6e 20 74 68 69 73 20 63 6f  es.  (In this co
6880: 6e 74 65 78 74 20 27 64 61 74 61 62 61 73 65 20  ntext 'database 
6890: 70 61 67 65 27 20 72 65 66 65 72 73 0a 2a 2a 20  page' refers.** 
68a0: 74 6f 20 61 6e 79 20 70 61 67 65 20 74 68 61 74  to any page that
68b0: 20 69 73 20 6e 6f 74 20 70 61 72 74 20 6f 66 20   is not part of 
68c0: 74 68 65 20 70 6f 69 6e 74 65 72 20 6d 61 70 20  the pointer map 
68d0: 69 74 73 65 6c 66 2e 29 20 20 45 61 63 68 20 70  itself.)  Each p
68e0: 6f 69 6e 74 65 72 20 6d 61 70 0a 2a 2a 20 65 6e  ointer map.** en
68f0: 74 72 79 20 63 6f 6e 73 69 73 74 73 20 6f 66 20  try consists of 
6900: 61 20 73 69 6e 67 6c 65 20 62 79 74 65 20 27 74  a single byte 't
6910: 79 70 65 27 20 61 6e 64 20 61 20 34 20 62 79 74  ype' and a 4 byt
6920: 65 20 70 61 72 65 6e 74 20 70 61 67 65 20 6e 75  e parent page nu
6930: 6d 62 65 72 2e 0a 2a 2a 20 54 68 65 20 50 54 52  mber..** The PTR
6940: 4d 41 50 5f 58 58 58 20 69 64 65 6e 74 69 66 69  MAP_XXX identifi
6950: 65 72 73 20 62 65 6c 6f 77 20 61 72 65 20 74 68  ers below are th
6960: 65 20 76 61 6c 69 64 20 74 79 70 65 73 2e 0a 2a  e valid types..*
6970: 2a 0a 2a 2a 20 54 68 65 20 70 75 72 70 6f 73 65  *.** The purpose
6980: 20 6f 66 20 74 68 65 20 70 6f 69 6e 74 65 72 20   of the pointer 
6990: 6d 61 70 20 69 73 20 74 6f 20 66 61 63 69 6c 69  map is to facili
69a0: 74 79 20 6d 6f 76 69 6e 67 20 70 61 67 65 73 20  ty moving pages 
69b0: 66 72 6f 6d 20 6f 6e 65 0a 2a 2a 20 70 6f 73 69  from one.** posi
69c0: 74 69 6f 6e 20 69 6e 20 74 68 65 20 66 69 6c 65  tion in the file
69d0: 20 74 6f 20 61 6e 6f 74 68 65 72 20 61 73 20 70   to another as p
69e0: 61 72 74 20 6f 66 20 61 75 74 6f 76 61 63 75 75  art of autovacuu
69f0: 6d 2e 20 20 57 68 65 6e 20 61 20 70 61 67 65 0a  m.  When a page.
6a00: 2a 2a 20 69 73 20 6d 6f 76 65 64 2c 20 74 68 65  ** is moved, the
6a10: 20 70 6f 69 6e 74 65 72 20 69 6e 20 69 74 73 20   pointer in its 
6a20: 70 61 72 65 6e 74 20 6d 75 73 74 20 62 65 20 75  parent must be u
6a30: 70 64 61 74 65 64 20 74 6f 20 70 6f 69 6e 74 20  pdated to point 
6a40: 74 6f 20 74 68 65 0a 2a 2a 20 6e 65 77 20 6c 6f  to the.** new lo
6a50: 63 61 74 69 6f 6e 2e 20 20 54 68 65 20 70 6f 69  cation.  The poi
6a60: 6e 74 65 72 20 6d 61 70 20 69 73 20 75 73 65 64  nter map is used
6a70: 20 74 6f 20 6c 6f 63 61 74 65 20 74 68 65 20 70   to locate the p
6a80: 61 72 65 6e 74 20 70 61 67 65 20 71 75 69 63 6b  arent page quick
6a90: 6c 79 2e 0a 2a 2a 0a 2a 2a 20 50 54 52 4d 41 50  ly..**.** PTRMAP
6aa0: 5f 52 4f 4f 54 50 41 47 45 3a 20 54 68 65 20 64  _ROOTPAGE: The d
6ab0: 61 74 61 62 61 73 65 20 70 61 67 65 20 69 73 20  atabase page is 
6ac0: 61 20 72 6f 6f 74 2d 70 61 67 65 2e 20 54 68 65  a root-page. The
6ad0: 20 70 61 67 65 2d 6e 75 6d 62 65 72 20 69 73 20   page-number is 
6ae0: 6e 6f 74 0a 2a 2a 20 20 20 20 20 20 20 20 20 20  not.**          
6af0: 20 20 20 20 20 20 20 20 75 73 65 64 20 69 6e 20          used in 
6b00: 74 68 69 73 20 63 61 73 65 2e 0a 2a 2a 0a 2a 2a  this case..**.**
6b10: 20 50 54 52 4d 41 50 5f 46 52 45 45 50 41 47 45   PTRMAP_FREEPAGE
6b20: 3a 20 54 68 65 20 64 61 74 61 62 61 73 65 20 70  : The database p
6b30: 61 67 65 20 69 73 20 61 6e 20 75 6e 75 73 65 64  age is an unused
6b40: 20 28 66 72 65 65 29 20 70 61 67 65 2e 20 54 68   (free) page. Th
6b50: 65 20 70 61 67 65 2d 6e 75 6d 62 65 72 20 0a 2a  e page-number .*
6b60: 2a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  *               
6b70: 20 20 20 69 73 20 6e 6f 74 20 75 73 65 64 20 69     is not used i
6b80: 6e 20 74 68 69 73 20 63 61 73 65 2e 0a 2a 2a 0a  n this case..**.
6b90: 2a 2a 20 50 54 52 4d 41 50 5f 4f 56 45 52 46 4c  ** PTRMAP_OVERFL
6ba0: 4f 57 31 3a 20 54 68 65 20 64 61 74 61 62 61 73  OW1: The databas
6bb0: 65 20 70 61 67 65 20 69 73 20 74 68 65 20 66 69  e page is the fi
6bc0: 72 73 74 20 70 61 67 65 20 69 6e 20 61 20 6c 69  rst page in a li
6bd0: 73 74 20 6f 66 20 0a 2a 2a 20 20 20 20 20 20 20  st of .**       
6be0: 20 20 20 20 20 20 20 20 20 20 20 20 6f 76 65 72              over
6bf0: 66 6c 6f 77 20 70 61 67 65 73 2e 20 54 68 65 20  flow pages. The 
6c00: 70 61 67 65 20 6e 75 6d 62 65 72 20 69 64 65 6e  page number iden
6c10: 74 69 66 69 65 73 20 74 68 65 20 70 61 67 65 20  tifies the page 
6c20: 74 68 61 74 0a 2a 2a 20 20 20 20 20 20 20 20 20  that.**         
6c30: 20 20 20 20 20 20 20 20 20 20 63 6f 6e 74 61 69            contai
6c40: 6e 73 20 74 68 65 20 63 65 6c 6c 20 77 69 74 68  ns the cell with
6c50: 20 61 20 70 6f 69 6e 74 65 72 20 74 6f 20 74 68   a pointer to th
6c60: 69 73 20 6f 76 65 72 66 6c 6f 77 20 70 61 67 65  is overflow page
6c70: 2e 0a 2a 2a 0a 2a 2a 20 50 54 52 4d 41 50 5f 4f  ..**.** PTRMAP_O
6c80: 56 45 52 46 4c 4f 57 32 3a 20 54 68 65 20 64 61  VERFLOW2: The da
6c90: 74 61 62 61 73 65 20 70 61 67 65 20 69 73 20 74  tabase page is t
6ca0: 68 65 20 73 65 63 6f 6e 64 20 6f 72 20 6c 61 74  he second or lat
6cb0: 65 72 20 70 61 67 65 20 69 6e 20 61 20 6c 69 73  er page in a lis
6cc0: 74 20 6f 66 0a 2a 2a 20 20 20 20 20 20 20 20 20  t of.**         
6cd0: 20 20 20 20 20 20 20 20 20 20 6f 76 65 72 66 6c            overfl
6ce0: 6f 77 20 70 61 67 65 73 2e 20 54 68 65 20 70 61  ow pages. The pa
6cf0: 67 65 2d 6e 75 6d 62 65 72 20 69 64 65 6e 74 69  ge-number identi
6d00: 66 69 65 73 20 74 68 65 20 70 72 65 76 69 6f 75  fies the previou
6d10: 73 0a 2a 2a 20 20 20 20 20 20 20 20 20 20 20 20  s.**            
6d20: 20 20 20 20 20 20 20 70 61 67 65 20 69 6e 20 74         page in t
6d30: 68 65 20 6f 76 65 72 66 6c 6f 77 20 70 61 67 65  he overflow page
6d40: 20 6c 69 73 74 2e 0a 2a 2a 0a 2a 2a 20 50 54 52   list..**.** PTR
6d50: 4d 41 50 5f 42 54 52 45 45 3a 20 54 68 65 20 64  MAP_BTREE: The d
6d60: 61 74 61 62 61 73 65 20 70 61 67 65 20 69 73 20  atabase page is 
6d70: 61 20 6e 6f 6e 2d 72 6f 6f 74 20 62 74 72 65 65  a non-root btree
6d80: 20 70 61 67 65 2e 20 54 68 65 20 70 61 67 65 20   page. The page 
6d90: 6e 75 6d 62 65 72 0a 2a 2a 20 20 20 20 20 20 20  number.**       
6da0: 20 20 20 20 20 20 20 20 69 64 65 6e 74 69 66 69          identifi
6db0: 65 73 20 74 68 65 20 70 61 72 65 6e 74 20 70 61  es the parent pa
6dc0: 67 65 20 69 6e 20 74 68 65 20 62 74 72 65 65 2e  ge in the btree.
6dd0: 0a 2a 2f 0a 23 64 65 66 69 6e 65 20 50 54 52 4d  .*/.#define PTRM
6de0: 41 50 5f 52 4f 4f 54 50 41 47 45 20 31 0a 23 64  AP_ROOTPAGE 1.#d
6df0: 65 66 69 6e 65 20 50 54 52 4d 41 50 5f 46 52 45  efine PTRMAP_FRE
6e00: 45 50 41 47 45 20 32 0a 23 64 65 66 69 6e 65 20  EPAGE 2.#define 
6e10: 50 54 52 4d 41 50 5f 4f 56 45 52 46 4c 4f 57 31  PTRMAP_OVERFLOW1
6e20: 20 33 0a 23 64 65 66 69 6e 65 20 50 54 52 4d 41   3.#define PTRMA
6e30: 50 5f 4f 56 45 52 46 4c 4f 57 32 20 34 0a 23 64  P_OVERFLOW2 4.#d
6e40: 65 66 69 6e 65 20 50 54 52 4d 41 50 5f 42 54 52  efine PTRMAP_BTR
6e50: 45 45 20 35 0a 0a 2f 2a 20 41 20 62 75 6e 63 68  EE 5../* A bunch
6e60: 20 6f 66 20 61 73 73 65 72 74 28 29 20 73 74 61   of assert() sta
6e70: 74 65 6d 65 6e 74 73 20 74 6f 20 63 68 65 63 6b  tements to check
6e80: 20 74 68 65 20 74 72 61 6e 73 61 63 74 69 6f 6e   the transaction
6e90: 20 73 74 61 74 65 20 76 61 72 69 61 62 6c 65 73   state variables
6ea0: 0a 2a 2a 20 6f 66 20 68 61 6e 64 6c 65 20 70 20  .** of handle p 
6eb0: 28 74 79 70 65 20 42 74 72 65 65 2a 29 20 61 72  (type Btree*) ar
6ec0: 65 20 69 6e 74 65 72 6e 61 6c 6c 79 20 63 6f 6e  e internally con
6ed0: 73 69 73 74 65 6e 74 2e 0a 2a 2f 0a 23 64 65 66  sistent..*/.#def
6ee0: 69 6e 65 20 62 74 72 65 65 49 6e 74 65 67 72 69  ine btreeIntegri
6ef0: 74 79 28 70 29 20 5c 0a 20 20 61 73 73 65 72 74  ty(p) \.  assert
6f00: 28 20 70 2d 3e 70 42 74 2d 3e 69 6e 54 72 61 6e  ( p->pBt->inTran
6f10: 73 61 63 74 69 6f 6e 21 3d 54 52 41 4e 53 5f 4e  saction!=TRANS_N
6f20: 4f 4e 45 20 7c 7c 20 70 2d 3e 70 42 74 2d 3e 6e  ONE || p->pBt->n
6f30: 54 72 61 6e 73 61 63 74 69 6f 6e 3d 3d 30 20 29  Transaction==0 )
6f40: 3b 20 5c 0a 20 20 61 73 73 65 72 74 28 20 70 2d  ; \.  assert( p-
6f50: 3e 70 42 74 2d 3e 69 6e 54 72 61 6e 73 61 63 74  >pBt->inTransact
6f60: 69 6f 6e 3e 3d 70 2d 3e 69 6e 54 72 61 6e 73 20  ion>=p->inTrans 
6f70: 29 3b 20 0a 0a 0a 2f 2a 0a 2a 2a 20 54 68 65 20  ); .../*.** The 
6f80: 49 53 41 55 54 4f 56 41 43 55 55 4d 20 6d 61 63  ISAUTOVACUUM mac
6f90: 72 6f 20 69 73 20 75 73 65 64 20 77 69 74 68 69  ro is used withi
6fa0: 6e 20 62 61 6c 61 6e 63 65 5f 6e 6f 6e 72 6f 6f  n balance_nonroo
6fb0: 74 28 29 20 74 6f 20 64 65 74 65 72 6d 69 6e 65  t() to determine
6fc0: 0a 2a 2a 20 69 66 20 74 68 65 20 64 61 74 61 62  .** if the datab
6fd0: 61 73 65 20 73 75 70 70 6f 72 74 73 20 61 75 74  ase supports aut
6fe0: 6f 2d 76 61 63 75 75 6d 20 6f 72 20 6e 6f 74 2e  o-vacuum or not.
6ff0: 20 42 65 63 61 75 73 65 20 69 74 20 69 73 20 75   Because it is u
7000: 73 65 64 0a 2a 2a 20 77 69 74 68 69 6e 20 61 6e  sed.** within an
7010: 20 65 78 70 72 65 73 73 69 6f 6e 20 74 68 61 74   expression that
7020: 20 69 73 20 61 6e 20 61 72 67 75 6d 65 6e 74 20   is an argument 
7030: 74 6f 20 61 6e 6f 74 68 65 72 20 6d 61 63 72 6f  to another macro
7040: 20 0a 2a 2a 20 28 73 71 6c 69 74 65 4d 61 6c 6c   .** (sqliteMall
7050: 6f 63 52 61 77 29 2c 20 69 74 20 69 73 20 6e 6f  ocRaw), it is no
7060: 74 20 70 6f 73 73 69 62 6c 65 20 74 6f 20 75 73  t possible to us
7070: 65 20 63 6f 6e 64 69 74 69 6f 6e 61 6c 20 63 6f  e conditional co
7080: 6d 70 69 6c 61 74 69 6f 6e 2e 0a 2a 2a 20 53 6f  mpilation..** So
7090: 2c 20 74 68 69 73 20 6d 61 63 72 6f 20 69 73 20  , this macro is 
70a0: 64 65 66 69 6e 65 64 20 69 6e 73 74 65 61 64 2e  defined instead.
70b0: 0a 2a 2f 0a 23 69 66 6e 64 65 66 20 53 51 4c 49  .*/.#ifndef SQLI
70c0: 54 45 5f 4f 4d 49 54 5f 41 55 54 4f 56 41 43 55  TE_OMIT_AUTOVACU
70d0: 55 4d 0a 23 64 65 66 69 6e 65 20 49 53 41 55 54  UM.#define ISAUT
70e0: 4f 56 41 43 55 55 4d 20 28 70 42 74 2d 3e 61 75  OVACUUM (pBt->au
70f0: 74 6f 56 61 63 75 75 6d 29 0a 23 65 6c 73 65 0a  toVacuum).#else.
7100: 23 64 65 66 69 6e 65 20 49 53 41 55 54 4f 56 41  #define ISAUTOVA
7110: 43 55 55 4d 20 30 0a 23 65 6e 64 69 66 0a 0a 0a  CUUM 0.#endif...
7120: 2f 2a 0a 2a 2a 20 54 68 69 73 20 73 74 72 75 63  /*.** This struc
7130: 74 75 72 65 20 69 73 20 70 61 73 73 65 64 20 61  ture is passed a
7140: 72 6f 75 6e 64 20 74 68 72 6f 75 67 68 20 61 6c  round through al
7150: 6c 20 74 68 65 20 73 61 6e 69 74 79 20 63 68 65  l the sanity che
7160: 63 6b 69 6e 67 20 72 6f 75 74 69 6e 65 73 0a 2a  cking routines.*
7170: 2a 20 69 6e 20 6f 72 64 65 72 20 74 6f 20 6b 65  * in order to ke
7180: 65 70 20 74 72 61 63 6b 20 6f 66 20 73 6f 6d 65  ep track of some
7190: 20 67 6c 6f 62 61 6c 20 73 74 61 74 65 20 69 6e   global state in
71a0: 66 6f 72 6d 61 74 69 6f 6e 2e 0a 2a 2a 0a 2a 2a  formation..**.**
71b0: 20 54 68 65 20 61 52 65 66 5b 5d 20 61 72 72 61   The aRef[] arra
71c0: 79 20 69 73 20 61 6c 6c 6f 63 61 74 65 64 20 73  y is allocated s
71d0: 6f 20 74 68 61 74 20 74 68 65 72 65 20 69 73 20  o that there is 
71e0: 31 20 62 69 74 20 66 6f 72 20 65 61 63 68 20 70  1 bit for each p
71f0: 61 67 65 20 69 6e 0a 2a 2a 20 74 68 65 20 64 61  age in.** the da
7200: 74 61 62 61 73 65 2e 20 41 73 20 74 68 65 20 69  tabase. As the i
7210: 6e 74 65 67 72 69 74 79 2d 63 68 65 63 6b 20 70  ntegrity-check p
7220: 72 6f 63 65 65 64 73 2c 20 66 6f 72 20 65 61 63  roceeds, for eac
7230: 68 20 70 61 67 65 20 75 73 65 64 20 69 6e 0a 2a  h page used in.*
7240: 2a 20 74 68 65 20 64 61 74 61 62 61 73 65 20 74  * the database t
7250: 68 65 20 63 6f 72 72 65 73 70 6f 6e 64 69 6e 67  he corresponding
7260: 20 62 69 74 20 69 73 20 73 65 74 2e 20 54 68 69   bit is set. Thi
7270: 73 20 61 6c 6c 6f 77 73 20 69 6e 74 65 67 72 69  s allows integri
7280: 74 79 2d 63 68 65 63 6b 20 74 6f 20 0a 2a 2a 20  ty-check to .** 
7290: 64 65 74 65 63 74 20 70 61 67 65 73 20 74 68 61  detect pages tha
72a0: 74 20 61 72 65 20 75 73 65 64 20 74 77 69 63 65  t are used twice
72b0: 20 61 6e 64 20 6f 72 70 68 61 6e 65 64 20 70 61   and orphaned pa
72c0: 67 65 73 20 28 62 6f 74 68 20 6f 66 20 77 68 69  ges (both of whi
72d0: 63 68 20 0a 2a 2a 20 69 6e 64 69 63 61 74 65 20  ch .** indicate 
72e0: 63 6f 72 72 75 70 74 69 6f 6e 29 2e 0a 2a 2f 0a  corruption)..*/.
72f0: 74 79 70 65 64 65 66 20 73 74 72 75 63 74 20 49  typedef struct I
7300: 6e 74 65 67 72 69 74 79 43 6b 20 49 6e 74 65 67  ntegrityCk Integ
7310: 72 69 74 79 43 6b 3b 0a 73 74 72 75 63 74 20 49  rityCk;.struct I
7320: 6e 74 65 67 72 69 74 79 43 6b 20 7b 0a 20 20 42  ntegrityCk {.  B
7330: 74 53 68 61 72 65 64 20 2a 70 42 74 3b 20 20 20  tShared *pBt;   
7340: 20 2f 2a 20 54 68 65 20 74 72 65 65 20 62 65 69   /* The tree bei
7350: 6e 67 20 63 68 65 63 6b 65 64 20 6f 75 74 20 2a  ng checked out *
7360: 2f 0a 20 20 50 61 67 65 72 20 2a 70 50 61 67 65  /.  Pager *pPage
7370: 72 3b 20 20 20 20 2f 2a 20 54 68 65 20 61 73 73  r;    /* The ass
7380: 6f 63 69 61 74 65 64 20 70 61 67 65 72 2e 20 20  ociated pager.  
7390: 41 6c 73 6f 20 61 63 63 65 73 73 69 62 6c 65 20  Also accessible 
73a0: 62 79 20 70 42 74 2d 3e 70 50 61 67 65 72 20 2a  by pBt->pPager *
73b0: 2f 0a 20 20 75 38 20 2a 61 50 67 52 65 66 3b 20  /.  u8 *aPgRef; 
73c0: 20 20 20 20 20 20 2f 2a 20 31 20 62 69 74 20 70        /* 1 bit p
73d0: 65 72 20 70 61 67 65 20 69 6e 20 74 68 65 20 64  er page in the d
73e0: 62 20 28 73 65 65 20 61 62 6f 76 65 29 20 2a 2f  b (see above) */
73f0: 0a 20 20 50 67 6e 6f 20 6e 50 61 67 65 3b 20 20  .  Pgno nPage;  
7400: 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f       /* Number o
7410: 66 20 70 61 67 65 73 20 69 6e 20 74 68 65 20 64  f pages in the d
7420: 61 74 61 62 61 73 65 20 2a 2f 0a 20 20 69 6e 74  atabase */.  int
7430: 20 6d 78 45 72 72 3b 20 20 20 20 20 20 20 20 2f   mxErr;        /
7440: 2a 20 53 74 6f 70 20 61 63 63 75 6d 75 6c 61 74  * Stop accumulat
7450: 69 6e 67 20 65 72 72 6f 72 73 20 77 68 65 6e 20  ing errors when 
7460: 74 68 69 73 20 72 65 61 63 68 65 73 20 7a 65 72  this reaches zer
7470: 6f 20 2a 2f 0a 20 20 69 6e 74 20 6e 45 72 72 3b  o */.  int nErr;
7480: 20 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62           /* Numb
7490: 65 72 20 6f 66 20 6d 65 73 73 61 67 65 73 20 77  er of messages w
74a0: 72 69 74 74 65 6e 20 74 6f 20 7a 45 72 72 4d 73  ritten to zErrMs
74b0: 67 20 73 6f 20 66 61 72 20 2a 2f 0a 20 20 69 6e  g so far */.  in
74c0: 74 20 6d 61 6c 6c 6f 63 46 61 69 6c 65 64 3b 20  t mallocFailed; 
74d0: 2f 2a 20 41 20 6d 65 6d 6f 72 79 20 61 6c 6c 6f  /* A memory allo
74e0: 63 61 74 69 6f 6e 20 65 72 72 6f 72 20 68 61 73  cation error has
74f0: 20 6f 63 63 75 72 72 65 64 20 2a 2f 0a 20 20 53   occurred */.  S
7500: 74 72 41 63 63 75 6d 20 65 72 72 4d 73 67 3b 20  trAccum errMsg; 
7510: 20 2f 2a 20 41 63 63 75 6d 75 6c 61 74 65 20 74   /* Accumulate t
7520: 68 65 20 65 72 72 6f 72 20 6d 65 73 73 61 67 65  he error message
7530: 20 74 65 78 74 20 68 65 72 65 20 2a 2f 0a 7d 3b   text here */.};
7540: 0a 0a 2f 2a 0a 2a 2a 20 52 6f 75 74 69 6e 65 73  ../*.** Routines
7550: 20 74 6f 20 72 65 61 64 20 6f 72 20 77 72 69 74   to read or writ
7560: 65 20 61 20 74 77 6f 2d 20 61 6e 64 20 66 6f 75  e a two- and fou
7570: 72 2d 62 79 74 65 20 62 69 67 2d 65 6e 64 69 61  r-byte big-endia
7580: 6e 20 69 6e 74 65 67 65 72 20 76 61 6c 75 65 73  n integer values
7590: 2e 0a 2a 2f 0a 23 64 65 66 69 6e 65 20 67 65 74  ..*/.#define get
75a0: 32 62 79 74 65 28 78 29 20 20 20 28 28 78 29 5b  2byte(x)   ((x)[
75b0: 30 5d 3c 3c 38 20 7c 20 28 78 29 5b 31 5d 29 0a  0]<<8 | (x)[1]).
75c0: 23 64 65 66 69 6e 65 20 70 75 74 32 62 79 74 65  #define put2byte
75d0: 28 70 2c 76 29 20 28 28 70 29 5b 30 5d 20 3d 20  (p,v) ((p)[0] = 
75e0: 28 75 38 29 28 28 76 29 3e 3e 38 29 2c 20 28 70  (u8)((v)>>8), (p
75f0: 29 5b 31 5d 20 3d 20 28 75 38 29 28 76 29 29 0a  )[1] = (u8)(v)).
7600: 23 64 65 66 69 6e 65 20 67 65 74 34 62 79 74 65  #define get4byte
7610: 20 73 71 6c 69 74 65 33 47 65 74 34 62 79 74 65   sqlite3Get4byte
7620: 0a 23 64 65 66 69 6e 65 20 70 75 74 34 62 79 74  .#define put4byt
7630: 65 20 73 71 6c 69 74 65 33 50 75 74 34 62 79 74  e sqlite3Put4byt
7640: 65 0a                                            e.